A measurement study of interference modeling and scheduling in low-power wireless networks

ABSTRACT

Accurate interference models are important for use in transmission scheduling algorithms in wireless networks. In this work, we perform extensive modeling and experimentation on two 20-node TelosB motes testbeds -- one indoor and the other outdoor -- to compare a suite of interference models for their modeling accuracies. We first empirically build and validate the physical interference model via a packet reception rate vs. SINR relationship using a measurement driven method. We then similarly instantiate other simpler models, such as hop-based, range-based, protocol model, etc. The modeling accuracies are then evaluated on the two testbeds using transmission scheduling experiments. We observe that while the physical interference model is the most accurate, it is still far from perfect, providing a 90-percentile error about 20-25% (and 80 percentile error 7-12%), depending on the scenario. The accuracy of the other models is worse and scenario-specific. The second best model trails the physical model by roughly 12-18 percentile points for similar accuracy targets. Somewhat similar throughput performance differential between models is also observed when used with greedy scheduling algorithms. Carrying on further, we look closely into the the two incarnations of the physical model -- 'thresholded' (conservative, but typically considered in literature) and 'graded' (more realistic). We show via solving the one shot scheduling problem, that the graded version can improve `expected throughput' over the thresholded version by scheduling imperfect links.

REFERENCES

• 1: "Moteiv," http://www.moteiv.com.
• 2: "TinyOS community forum," http://www.tinyos.net.
• 3: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 4: H. Balakrishnan, C. L. Barrett, V. S. A. Kumar, M. V. Marathe, and S. Thite, "The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc networks," IEEE J. Selected Areas of Communication, pp. 1069--1079, 2004.
• 5: S. Borbash and A. Ephremides, "Wireless link scheduling with power control and SINR constraints," IEEE Trans. on Info. Theory, vol. 52, no. 11, pp. 5106--5111, 2006.
• 6: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161092]
• 7: Saumitra M. Das , Dimitrios Koutsonikolas , Y. Charlie Hu , Dimitrios Peroulis, Characterizing multi-way interference in wireless mesh networks, Proceedings of the 1st international workshop on Wireless network testbeds, experimental evaluation & characterization, September 29-29, 2006, Los Angeles, CA, USA [doi>10.1145/1160987.1160999]
• 8: Olga Goussevskaia , Yvonne Anne Oswald , Roger Wattenhofer, Complexity in geometric SINR, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288122]
• 9: B. Greenstein, A. Pesterev, C. Mar, E. Kohler, J. Judy, S. Farshchi, and D. Estrin, "Collecting high-rate data over low-rate sensor network radios," Tech Report. Center for Embedded Network Sensing. Paper 17, 2007. http://repositories.cdlib.org/cens/techrep/17.
• 10: Jimmi Grönkvist , Anders Hansson, Comparison between graph-based and interference-based STDMA scheduling, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501453]
• 11: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388--404, March 2000.
• 12: 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.
• 13: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 14: Anand Kashyap , Samrat Ganguly , Samir R. Das, A measurement-based approach to modeling link capacity in 802.11-based wireless networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287883]
• 15: Jeongkeun Lee , Wonho Kim , Sung-Ju Lee , Daehyung Jo , Jiho Ryu , Taekyoung Kwon , Yanghee Choi, An experimental study on the capture effect in 802.11a networks, Proceedings of the the second ACM international workshop on Wireless network testbeds, experimental evaluation and characterization, September 10-10, 2007, Montreal, Quebec, Canada [doi>10.1145/1287767.1287772]
• 16: Ritesh Maheshwari , Shweta Jain , Samir R. Das, On estimating joint interference for concurrent packet transmissions in low power wireless networks, Proceedings of the third ACM international workshop on Wireless network testbeds, experimental evaluation and characterization, September 19-19, 2008, San Francisco, California, USA [doi>10.1145/1410077.1410094]
• 17: Arunesh Mishra , Vivek Shrivastava , Suman Banerjee , William Arbaugh, Partially overlapped channels not considered harmful, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 18: T. Moscibroda and R. Wattenhofer, "The complexity of connectivity in wireless networks," in Proc. IEEE INFOCOM, 2006.
• 19: Moteiv Corporation, Tmote Sky: Ultra low power IEEE 802.15.4 compliant wireless sensor module, San Fransisco, CA, November 2006.
• 20: 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.
• 21: Dragoş Niculescu, Interference map for 802.11 networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298355]
• 22: Jitendra Padhye , Sharad Agarwal , Venkata N. Padmanabhan , Lili Qiu , Ananth Rao , Brian Zill, Estimation of link interference in static multi-hop wireless networks, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.28-28, October 19-21, 2005, Berkeley, CA
• 23: Lili Qiu , Yin Zhang , Feng Wang , Mi Kyung Han , Ratul Mahajan, A general model of wireless interference, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287874]
• 24: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 25: Charles Reis , Ratul Mahajan , Maya Rodrig , David Wetherall , John Zahorjan, Measurement-based models of delivery and interference in static wireless networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 26: Injong Rhee , Ajit Warrier , Jeongki Min , Lisong Xu, DRAND: distributed randomized TDMA scheduling for wireless ad-hoc networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132927]
• 27: Injong Rhee , Ajit Warrier , Mahesh Aia , Jeongki Min, Z-MAC: a hybrid MAC for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098929]
• 28: Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161116]
• 29: Dongjin Son , Bhaskar Krishnamachari , John Heidemann, Experimental study of concurrent transmission in wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182831]
• 30: K. Srinivasan and P. Levis, "RSSI is Under-Appreciated," in Proc. EmNetS, 2006.
• 31: CC2420 Radio Datasheet, 1st ed., Texas Instruments, October 2005.
• 32: Weizhao Wang , Yu Wang , Xiang-Yang Li , Wen-Zhan Song , Ophir Frieder, Efficient interference-aware TDMA link scheduling for static wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161119]
• 33: K. Whitehouse , A. Woo , F. Jiang , J. Polastre , D. Culler, Exploiting the capture effect for collision detection and recovery, Proceedings of the 2nd IEEE workshop on Embedded Networked Sensors, p.45-52, April 30-May 01, 2005
• 34: X. Wu and R. Srikant, "Bounds on the capacity region of multi-hop wireless networks under distributed greedy scheduling," in Proc. IEEE INFOCOM, 2006.
• 35: G. Zhou, T. He, J. Stankovic, and T. Abdelzaher, "RID: Radio Interference Detection in Wireless Sensor Networks," in Proc. IEEE INFOCOM, 2005.
• 36: M. Zuniga and B. Krishnamachari, "Analyzing the transitional region in low power wireless links," in Proc. IEEE SECON, 2004, pp. 517--526.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Measurement, Performance

Keywords:
interference model, tdma