Paolo Santi
ABSTRACT
In this paper, we revisit the wireless link scheduling problem under a graded version of the SINR interference model. Unlike the traditional thresholded version of the SINR model, the graded SINR model allows use of "imperfect links", where communication is still possible, although with degraded performance (in terms of data rate or PRR). Throughput benefits when graded SINR model is used instead of thresholded SINR model to schedule transmissions have recently been shown in an experimental testbed. Here, we formally define the wireless link scheduling problem under the graded SINR model, where we impose an additional constraint on the minimum quality of the usable links, (expressed as an SNR threshold βQ). Then, we present an approximation algorithm for this problem, which is shown to be within a constant factor from optimal. We also present a more practical greedy algorithm, whose performance bounds are not known, but which is shown through simulation to have much better average performance than the approximation algorithm. Furthermore, we investigate, through both simulation and implementation on an experimental testbed, the tradeoff between the minimum link quality threshold βQ and the resulting network throughput.
- http://ieee802.org/16/Google Scholar
- M. Alicherry, R. Bathia, L. Li, "Joint Channel Assignment and Routing for Throughput Optimization in Multi-Radio Wireless Mesh Networks", Proc. ACM Mobicom, pp. 58--72, 2005. Google ScholarDigital Library
- G. Brar, D. Blough, and P. Santi, "Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks", Proc. ACM MobiCom, pp. 2--13, 2006. Google ScholarDigital Library
- G. Brar, D. Blough, and P. Santi, "The SCREAM Approach for Efficient Distributed Scheduling with Physical Interference in Wireless Mesh Networks", Proc. IEEE ICDCS, 2008. Google ScholarDigital Library
- CC2420 Radio Datasheet, Texas Instruments, Oct. 2005.Google Scholar
- D. Chafekar, V.S. Anil Kumar, M.V. Marathe, S. Parthasarathy, A. Srinivasan, "Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints", Proc. IEEE Infocom, pp. 1166--1174 , 2008.Google Scholar
- R.L. Cruz, A.V. Santhanam, "Optimal Routing, Link Scheduling and Power Control in Multi-Hop Wireless Networks", Proc. IEEE Infocom, pp. 702--711, 2003.Google Scholar
- R.L. Cruz, A.V. Santhanam, "Hierarchical Link Scheduling and Power Control in Multihop Wireless Networks", Proc. Allerton Conference on Communications, Control and Computing, 2002.Google Scholar
- O. Goussevskaia, Y.V. Oswald, R. Wattenhofer, "Complexity in Geometric SINR", Proc. ACM MobiHoc, pp. 100--109, 2007. Google ScholarDigital Library
- P. Gupta and P.R. Kumar, "The Capacity of Wireless Networks," IEEE Trans. on Info. Theory, Vol. 46, No. 2, pp. 388--404, 2000. Google ScholarDigital Library
- IEEE Computer Society LAN/MAN Standards Committee, "802.15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANS)," 2003.Google Scholar
- D.B. Johnson, D.A. Maltz, "Dynamic Source Routing in Ad Hod Wireless Networks", Mobile Computing, n. 353, pp. 153--181, 1996.Google ScholarCross Ref
- A. Keshavarz-Haddad, R. Riedi, "On the Broadcast Capacity of Multihop Wireless Networks: Interplay of Power", Density and Interference, Proc. IEEE Secon, pp. 314-- 323, 2007.Google Scholar
- R. Nelson and L. Kleinrock, "Spatial-TDMA: A Collison-free Multihop Channel Access Protocol," IEEE Transactions on Communication, Vol. 33, pp. 934--944, Sept. 1985.Google ScholarCross Ref
- R. Maheshwari, S. Jain, S.R. Das, "A Measurement Study of Interference Modeling and Scheduling in Low-Power Wireless Networks", Proc. 6th ACM Conference on Embedded Networked Sensor Systems (ACM SenSys 2008), Raleigh, NC, Nov 2008. Google ScholarDigital Library
- R. Maheshwari, J. Cao, S.R. Das, "Physical Interference Modeling for Transmission Scheduling on Commodity WiFi Hardware", Proceedings of Infocom 2009.Google Scholar
- T. Moscibroda and R. Wattenhofer, "The Complexity of Connectivity in Wireless Networks," Proceedings of Infocom 2006.Google Scholar
- Moteiv Corporation, tmote sky: Ultra low power IEEE 802.15.4 compliant wireless sensor module, November 2006.Google Scholar
- C. Perkins, E. Belding-Royer, S. Das, "Ad Hoc On-Demand Distance Vector (AODV) Routing", IETF draft, http://www.ietf.org/rfc/rfc3561.txt, 2003. Google ScholarDigital Library
- T.S. Rappaport, Wireless Communications, Prentice Hall, Upper Saddle River, NJ, 2002. Google ScholarDigital Library
- C. Scheideler, A. Richa, P. Santi, "An O(log n) Dominating Set Protocol for Wireless Ad Hoc Networks under the Physical Interference Model", Proc. ACM MobiHoc, pp. 91--100, 2008. Google ScholarDigital Library
- G. Sharma, R. Mazumdar, N. Shroý, "On the Complexity of Scheduling in Wireless Networks", Proc. ACM Mobicom, pp. 227--238, 2006. Google ScholarDigital Library
- TinyOS community forum, http://www.tinyos.net.Google Scholar
- M. Zuniga, B. Krishnamachari, "Analyzing the Transitional Region in Low Power Wireless Links", Proc. IEEE Secon, pp. 517--526, 2004.Google Scholar
Index Terms
- Wireless link scheduling under a graded SINR interference model
Recommendations
Approximation algorithms for wireless link scheduling with SINR-based interference
In this paper, we consider the classical problem of link scheduling in wireless networks under an accurate interference model, in which correct packet reception at a receiver node depends on the signa-to-interference-plus-noise ratio (SINR). While most ...
Distributed wireless link scheduling in the SINR model
We present an approximation algorithm for wireless link scheduling under the physical SINR interference model. In the link scheduling problem, it is given a set of $$n$$n links in a metric space, each of which is a sender---receiver pair, and the ...
Interference analysis and capacity for forward link 3G CDMA network with adaptive antennas
In code division multiple access (CDMA) systems, the capacity of forward link (FL) communication to mobile receivers is limited primarily by co-channel interference (CCI). Adaptive antenna arrays (AAAs) that use antenna arrays along with advanced signal ...
Comments