On biased link sampling in data-driven link estimation and routing in low-power wireless networks

ABSTRACT

The wireless network community has become increasingly aware of the benefits of data-driven link estimation and routing as compared with beacon-based approaches, but the issue of biased link sampling (BLS) has not been well studied even though it affects routing convergence in the presence of network and environment dynamics. Focusing on traffic-induced dynamics, we examine the open, unexplored question of how serious the BLS issue is and how to effectively address it when the routing metric ETX is used. For a wide range of traffic patterns and network topologies and using both node-oriented and network-wide analysis and experimentation, we discover that the optimal routing structure remains quite stable even though the properties of individual links and routes vary significantly as traffic pattern changes. In cases where the optimal routing structure does change, data-driven link estimation and routing is either guaranteed to converge to the optimal structure or empirically shown to converge to a close-to-optimal structure. These findings provide the foundation for addressing the BLS issue in the presence of traffic-induced dynamics and suggest approaches other than existing ones. These findings also demonstrate that it is possible to maintain an optimal, stable routing structure despite the fact that the properties of individual links and paths vary in response to network dynamics.

REFERENCES

• 1: Chipcon CC100 RF transceiver. http://focus.ti.com/lit/ds/symlink/cc1000.pdf.
• 2: Crossbow Mica2 motes. http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/MICA2_Datasheet.pdf.
• 3: An event traffic trace for sensor networks. http://www.cs.wayne.edu/~hzhang/group/publications/Lites-trace.txt.
• 4: TinyOS. http://www.tinyos.net/.
• 5: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 6: I. Chakeres and E. Belding-Royer. The utility of hello messages for determining link connectivity. In WPMC, 2002.
• 7: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 8: Saumitra M. Das , Himabindu Pucha , Konstantina Papagiannaki , Y. Charlie Hu, Studying wireless routing link metric dynamics, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298352]
• 9: Richard Draves , Jitendra Padhye , Brian Zill, Comparison of routing metrics for static multi-hop wireless networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 10: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 11: Prabal Dutta , Mike Grimmer , Anish Arora , Steven Bibyk , David Culler, Design of a wireless sensor network platform for detecting rare, random, and ephemeral events, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 12: Emre Ertin , Anish Arora , Rajiv Ramnath , Vinayak Naik , Sandip Bapat , Vinod Kulathumani , Mukundan Sridharan , Hongwei Zhang , Hui Cao , Mikhail Nesterenko, Kansei: a testbed for sensing at scale, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127838]
• 13: R. Fonseca, O. Gnawali, K. Jamieson, and P. Levis. Four-bit wireless link estimation. In ACM HotNets, 2007.
• 14: Tian He , John A. Stankovic , Chenyang Lu , Tarek Abdelzaher, SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.46, May 19-22, 2003
• 15: M. Hollander. Nonparametric statistical methods. Wiley, 1999.
• 16: R. Jain. The Art of Computer Systems Performance Analysis. John Wiley & Sons, Inc., 1991.
• 17: Kyu-Han Kim , Kang G. Shin, On accurate measurement of link quality in multi-hop 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.1161095]
• 18: D. Kotz, C. Newport, and C. Elliott. The mistaken axioms of wireless-network research. Technical Report TR2003-467, Dartmouth College, Computer Science, July 2003.
• 19: R. Krishnan, A. Raniwala, and T. cker Chiueh. Design of a channel characteristics-aware routing protocol. In IEEE INFOCOM miniconference, 2008.
• 20: Seungjoon Lee , Bobby Bhattacharjee , Suman Banerjee, Efficient geographic routing in multihop wireless networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062720]
• 21: Shan Lin , Jingbin Zhang , Gang Zhou , Lin Gu , John A. Stankovic , Tian He, ATPC: adaptive transmission power control for 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.1182830]
• 22: Henrik Lundgren , Erik Nordströ , Christian Tschudin, Coping with communication gray zones in IEEE 802.11b based ad hoc networks, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570799]
• 23: Ping Chung Ng , Soung Chang Liew, Throughput analysis of IEEE802.11 multi-hop ad hoc networks, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.309-322, April 2007 [doi>10.1109/TNET.2007.892848]
• 24: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 25: 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]
• 26: K. Ramachandran, I. Sheriff, E. Belding, and K. Almeroth. Routing stability in static wireless mesh networks. In PAM, 2007.
• 27: A. Willig. A new class of packet- and bit-level models for wireless channels. In IEEE PIMRC, 2002.
• 28: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 29: H. Zhang, A. Arora, and P. Sinha. Learn on the fly: Data-driven link estimation and routing in sensor network backbones. In IEEE INFOCOM, 2006.
• 30: H. Zhang, L. Sang, and A. Arora. Data-driven link estimation in sensor networks: An accuracy perspective. Technical report, Wayne State University (http://www.cs.wayne.edu/~hzhang/group/TR/DNC-TR-08-02.pdf), 2008.
• 31: H. Zhang, L. Sang, and A. Arora. On the convergence and stability of data-driven link estimation and routing in sensor networks. Technical report, Wayne State University (http://www.cs.wayne.edu/~hzhang/group/TR/DNC-TR-08-03.pdf), 2008.
• 32: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 33: Marco Zúñiga Zamalloa , Bhaskar Krishnamachari, An analysis of unreliability and asymmetry in low-power wireless links, ACM Transactions on Sensor Networks (TOSN), v.3 n.2, p.7-es, June 2007 [doi>10.1145/1240226.1240227]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Measurement, Performance

Keywords:
biased link sampling, convergence, data-driven link estimation and routing, low-power wireless networks, sensor networks, stability