On the convergence and stability of data-driven link estimation and routing in sensor 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) estimation 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: 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
• 2: Chakeres, I. and Belding-Royer, E. 2002. The utility of hello messages for determining link connectivity. In Proceedings of the International Symposium on Wireless Personal Multimedia Communications (WPMC).
• 3: 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]
• 4: CrossBow Technology, Inc. 2009. Crossbow Mica2 motes. http://www.xbow.com/Products/Productpdffiles/Wirelesspdf/MICA2Datasheet.pdf.
• 5: 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]
• 6: 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
• 7: 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]
• 8: 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
• 9: 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]
• 10: Fonseca, R., Gnawali, O., Jamieson, K., and Levis, P. 2007. Four-bit wireless link estimation. In Proceedings of the ACM Workshop on Hot Topics in Networks (HotNets).
• 11: 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
• 12: Hollander, M. 1999. Nonparametric Statistical Methods. John Wiley&Sons.
• 13: IEEE 802.15.4 Working Group. 2006. IEEE Std 802.15.4-2006. Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs). http://webstore.ansi.org/RecordDetail.aspx?sku=IEEE+Std+802.15.4-2006&source=google&adgroup=ieee&keyword=ieee%20802.15.4-2006&gclid=CLrH252ripsCFQJN5QodNkT4og.
• 14: Jain, R. 1991. The Art of Computer Systems Performance Analysis. John Wiley&Sons.
• 15: 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]
• 16: Kotz, D., Newport, C., and Elliott, C. 2003. The mistaken axioms of wireless-network research. Tech. rep. TR2003-467, Dartmouth College, Department of Computer Science.
• 17: Krishnan, R., Raniwala, A., and Ckerchiueh, T. 2008. Design of a channel characteristics-aware routing protocol. In Proceedings of the IEEE INFOCOM MiniConference.
• 18: 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]
• 19: 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]
• 20: 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]
• 21: 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]
• 22: 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]
• 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: Ramachandran, K., Sheriff, I., Belding, E., and Almeroth, K. 2007. Routing stability in static wireless mesh networks. In Proceedings of the IEEE Passive and Active Measurement Conference (PAM).
• 25: Texas Instruments. 2009. Chipcon CC1 0 0 RF transceiver. http://focus.ti.com/lit/ds/symlink/cc1000.pdf.
• 26: Tiny OS Team. 2009. TinyOS. http://www.tinyos.net/.
• 27: Willig, A. 2002. A new class of packet- and bit-level models for wireless channels. In Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC).
• 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: Zhang, H. 2004. An event traffic trace for sensor networks. http://www.cs.wayne.edu/~hzhang/group/publications/Lites-trace.txt.
• 30: Hongwei Zhang , Anish Arora , Young-ri Choi , Mohamed G. Gouda, Reliable bursty convergecast in wireless sensor 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.1062724]
• 31: Hongwei Zhang , Anish Arora , Prasun Sinha, Link Estimation and Routing in Sensor Network Backbones: Beacon-Based or Data-Driven?, IEEE Transactions on Mobile Computing, v.8 n.5, p.653-667, May 2009 [doi>10.1109/TMC.2008.155]
• 32: Zhang, H., Sang, L., and Arora, A. 2008a. Data-driven link estimation in sensor networks: An accuracy perspective. Tech. rep., Wayne State University. http://www.cs.wayne.edu/~hzhang/group/TR/DNC-TR-08-02.pdf.
• 33: Zhang, H., Sang, L., and Arora, A. 2008b. Link estimation and routing in low-power wireless networks: Beacon-based or data-driven? Tech. rep. DNC-TR-08-06, Wayne State University. http://www.cs.wayne.edu/~hzhang/group/TR/DNC-TR-08-06.pdf.
• 34: 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]
• 35: 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
          Subjects: Routing protocols

General Terms:
Algorithms, Measurement, Performance

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