SGF: A state-free gradient-based forwarding protocol for wireless sensor networks

ABSTRACT

Limitation on available resources is a major challenge in wireless sensor networks. Due to high rates of unexpected node/link failures, robust data delivery through multiple hops also becomes a critical issue. In this article we present a state-free gradient-based forwarding (SGF) protocol to address these challenges. Nodes running SGF do not maintain states of neighbors or network topology and thus can scale to very large networks. Without using routing tables, SGF builds a cost field called gradient that provides each node the direction to forward data. The maintenance of gradient is purely driven by data transmissions and hence incurs little overhead. To adapt to transient channel variations and topology changes, the forwarder of a routing node is selected opportunistically among multiple candidate nodes through a distributed contention process. Simulation results show that SGF achieves significant energy savings and outperforms several existing data forwarding protocols in terms of packet delivery ratio and end-to-end delay.

REFERENCES

• 1: Suman Banerjee , Archan Misra, Minimum energy paths for reliable communication in multi-hop wireless networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513818]
• 2: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 3: Blum, B., He, T., Son, S., and Stankovic, J. 2003. IGF: A state-free robust communication protocol for wireless sensor networks. Tech. rep. CS-2003-11, Department of Computer Science, University of Virginia.
• 4: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 5: Qing Cao , Tarek Abdelzaher, Scalable logical coordinates framework for routing in wireless sensor networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.4, p.557-593, November 2006 [doi>10.1145/1218556.1218561]
• 6: Chang, J.-H. and Tassiulas, L. 2000. Energy conserving routing in wireless ad-hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). vol. 1. 22--31.
• 7: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 8: 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]
• 9: Crossbow. 2003. Mica/mica2/micaz wireless measurement system datasheets. http://inf.tu-dresen.de/dargie/wsn/slides/students/MICA.ppt.
• 10: Qunfeng Dong , Suman Banerjee , Micah Adler , Archan Misra, Minimum energy reliable paths using unreliable wireless links, 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.1062744]
• 11: Sheetalkumar Doshi , Shweta Bhandare , Timothy X Brown, An on-demand minimum energy routing protocol for a wireless ad hoc network, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.3, July 2002 [doi>10.1145/581291.581300]
• 12: Füssler, H., Widmer, J., Mauve, M., and Hartenstein, H. 2003. A novel forwarding paradigm for position-based routing (with implicit addressing). In Proceedings of IEEE 18th Annual Workshop on Computer Communications (CCW'03), 194--200.
• 13: Javier Gomez , Andrew T. Campbell , Mahmoud Naghshineh , Chatschik Bisdikian, PARO: supporting dynamic power controlled routing in wireless ad hoc networks, Wireless Networks, v.9 n.5, p.443-460, September 2003 [doi>10.1023/A:1024636132348]
• 14: Han, K.-H., Ko, Y.-B., and Kim, J.-H. 2004. A novel gradient approach for efficient data dissemination in wireless sensor networks. In Proceedings of the 60th IEEE Vehicular Technology Conference (VTC Fall), vol. 4, 2979--2983.
• 15: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 16: Heissenbüttel, M., Braun, T., Bernoulli, T., and Wälchli, M. 2004. BLR: Beacon-Less routing algorithm for mobile ad-hoc networks. Elsevier's Comput. Commun. J. 27, 11, 1076--1086.
• 17: Huang, P., Yang, X., and Tan, Y. 2008. A Robust and Energy-Efficient Approach for Image/Video Dissemination in WSNs. In Proceedings of the 5th Annual IEEE Consumer Communications and Networking Conference (CCNC'08).
• 18: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 19: Shweta Jain , Samir R. Das, Exploiting Path Diversity in the Link Layer in Wireless Ad Hoc Networks, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.22-30, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.42]
• 20: Lee, S.-J. and Gerla, M. 2000. AODV-BR: Backup routing in ad hoc networks. In Proceedings of the IEEE Wireless Communication and Networking Conference (WCNC'00), vol. 3, 1311--1316.
• 21: Lee, S.-J. and Gerla, M. 2001. Split multipath routing with maximally disjoint paths in ad hoc networks. In Proceedings of the IEEE International Conference on Communications (ICC'01), vol. 10, 3201--3205.
• 22: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, A cone-based distributed topology-control algorithm for wireless multi-hop networks, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.147-159, February 2005 [doi>10.1109/TNET.2004.842229]
• 23: Li, X.-Y., Chen, H., Shu, Y., Chu, X., and Wu, Y.-W. 2006. Energy efficient routing with unreliable links in wireless networks. In Proceedings of the IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS'06), 160--169.
• 24: Li, Z., Nandi, S., and Gupta, A. K. 2005. ECS: An enhanced carrier sensing mechanism for wireless ad hoc networks. Elsevier's Comput. Commun. 28, 17, 1970--1984.
• 25: 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]
• 26: On-Demand Multi Path Distance Vector Routing in Ad Hoc Networks, Proceedings of the Ninth International Conference on Network Protocols, p.14, November 11-14, 2001
• 27: Monks, J. P., Bharghavan, V., and Hwu, W.-M. W. 2001. A power controlled multiple access protocol for wireless packet networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom), vol. 1, 219--228.
• 28: Muqattash, A. and Krunz, M. 2003. Power controlled dual channel (PCDC) medium access protocol for wireless ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom), vol. 1, 470--480.
• 29: Muqattash, A. and Krunz, M. 2005. POWMAC: A single-channel power-control protocol for throughput enhancement in wireless ad hoc networks. IEEE J. Selected Areas Commun. 23, 5, 1067--1084.
• 30: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 31: Qiao, D., Choi, S., Jain, A., and Shin, K. G. 2003. Adaptive transmit power control in IEEE 802.11a wireless LANs. In Proceedings of the 57th IEEE Semiannual Vehicular Technology Conference (VTC Spring), vol. 1, 433--437.
• 32: Ramanathan, R. and Rosales-Hain, R. 2000. Topology control of multihop wireless networks using transmit power adjustment. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom), vol. 2, 404--413.
• 33: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 34: Elizabeth M. Royer , Charles E. Perkins, Multicast operation of the ad-hoc on-demand distance vector routing protocol, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.207-218, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313538]
• 35: Paolo Santi, Topology control in wireless ad hoc and sensor networks, ACM Computing Surveys (CSUR), v.37 n.2, p.164-194, June 2005 [doi>10.1145/1089733.1089736]
• 36: Schurgers, C. and Srivastava, M. B. 2001. Energy efficient routing in wireless sensor networks. In Proceedings of the IEEE Military Communications Conference (MilCom), vol. 1, 357--361.
• 37: Shah, R., Wolisz, A., and Rabaey, J. 2005. On the performance of geographical routing in the presence of localization errors. In Proceedings of the IEEE International Conference on Communications (ICC'05), 2979--2985.
• 38: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 39: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 40: Son, D., Krishnamachari, B., and Heidemann, J. 2004. Experimental study of the effects of transmission power control and blacklisting in wireless sensor networks. In Proceedings of the 1st Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (IEEE SECON'04), 289--298.
• 41: Matthias Witt , Volker Turau, The Impact of Location Errors on Geographic Routing in Sensor Networks, Proceedings of the International Multi-Conference on Computing in the Global Information Technology, p.76, August 01-03, 2006 [doi>10.1109/ICCGI.2006.87]
• 42: 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]
• 43: Guoliang Xing , Chenyang Lu , Ying Zhang , Qingfeng Huang , Robert Pless, Minimum power configuration 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.1062738]
• 44: Xu, Y., Bien, S., Mori, Y., Heidemann, J., and Estrin, D. 2003. Topology control protocols to conserve energy in wireless ad hoc networks. Tech. rep. 6, University of California, Los Angeles, Center for Embedded Networked Computing. January.
• 45: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 46: Ye, F., Chen, A., Lu, S., and Zhang, L. 2001. A scalable solution to minimum cost forwarding in large sensor networks. In Proceedings of the 10th International Conference on Computer Communications and Networks (ICCCN'01), 304--309.
• 47: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003
• 48: Fan Ye , Gary Zhong , Songwu Lu , Lixia Zhang, GRAdient broadcast: a robust data delivery protocol for large scale sensor networks, Wireless Networks, v.11 n.3, p.285-298, May 2005 [doi>10.1007/s11276-005-6612-9]
• 49: Ye, W., Heidemann, J., and Estrin, D. 2002. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom), vol. 3, 1567--1576.

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
Sensor networks, energy conservation, gradient, power control, robust performance, state-free