Routing in outer space: fair traffic load in multi-hop wireless networks

ABSTRACT

In this paper we consider security-related and energy-efficiency issues in multi-hop wireless networks. We start our work from the observation, known in the literature, that shortest path routing creates congested areas in multi-hop wireless networks. These areas are critical - they generate both security and energy efficiency issues. We attack these problems and set out routing in outer space, a new routing mechanism that transforms any shortest path routing protocol (or approximated versions of it) into a new protocol that does not create congested areas, does not have the associated security-related issues, and does not encourage selfish positioning. Moreover, the network lives longer of the same network using the original routing protocol (in spite of using more energy globally), and dies more gracefully.

REFERENCES

• 1: I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. IEEE Communcations Magazine, 40:102--114, August 2002.
• 2: M. Bhardwaj and A. Chandrakasan. Bounding the lifetime of sensor networks via optimal role assignments. In Proceedings of the Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), volume 3, pages 1587--1596, 2002.
• 3: Douglas M. Blough , Paolo Santi, Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570668]
• 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: Nirupama Bulusu , John Heidemann , Deborah Estrin , Tommy Tran, Self-configuring localization systems: Design and Experimental Evaluation, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.24-60, February 2004 [doi>10.1145/972627.972630]
• 7: Y. Ganjali and A. Keshavarzian. Load balancing in ad hoc networks: single-path routing vs. multi-path routing. In Proceedings of the Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), volume 2, pages 1120--1125 vol.2, 2004.
• 8: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions On Information Theory, 46(2), March 2000.
• 9: Z. Haas. A new routing protocol for the reconfigurable wireless networks. In Proc. of the IEEE Int. Conf. on Universal Personal Communications, October 1997.
• 10: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 11: X. Hong, P. Wang, J. Kong, Q. Zheng, and J. Liu. Effective probabilistic approach protecting sensor traffic. Military Communications Conference, 2005. MILCOM 2005. IEEE, 1:169--175, October 2005.
• 12: E. Hyytiä and J. Virtamo. On traffic load distribution and load balancing in dense wireless multihop networks. In NGI 2006, 2006.
• 13: P. Jacquet, P. Mühlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot. Optimized link state routing protocol for ad hoc networks. In Proceedings of the 5th IEEE Multi Topic Conference (INMIC 2001), 2001.
• 14: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 15: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 16: Alexander Kröller , Sándor P. Fekete , Dennis Pfisterer , Stefan Fischer, Deterministic boundary recognition and topology extraction for large sensor networks, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1000-1009, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109668]
• 17: S. Kwon and N. B. Shroff. Paradox of shortest path routing for large multi-hop wireless networks. In IEEE INFOCOM'07 Anchorage, May 2007.
• 18: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 19: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 20: 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
• 21: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 22: P. P. Pham and S. Perreau. Increasing the network performance using multi-path routing mechanism with load balance. Ad Hoc Networks, 2:433--459, October 2004.
• 23: Lucian Popa , Afshin Rostamizadeh , Richard Karp , Christos Papadimitriou , Ion Stoica, Balancing traffic load in wireless networks with curveball routing, 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.1288131]
• 24: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 25: Ananth Rao , Sylvia Ratnasamy , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 26: E. Royer and C. Toh. A review of current routing protocols for ad-hoc mobile wireless networks, April 1999.
• 27: Kimaya Sanzgiri , Bridget Dahill , Brian Neil Levine , Clay Shields , Elizabeth M. Belding-Royer, A Secure Routing Protocol for Ad Hoc Networks, Proceedings of the 10th IEEE International Conference on Network Protocols, p.78-89, November 12-15, 2002
• 28: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 29: K. Seada and A. Helmy. Geographic protocols in sensor networks. Technical report, USC, July 2004.
• 30: V. Srinivasan, P. Neggehalli, C. F. Chiasserini, and R. R. Rao. Cooperation in wireless ad hoc wireless networks. In Proceedings of the Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), 2003.
• 31: WeiZhao Wang , Xiang-Yang Li , Yu Wang, Truthful multicast routing in selfish wireless 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.1023745]
• 32: Yue Wang , Jie Gao , Joseph S.B. Mitchell, Boundary recognition in sensor networks by topological methods, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161104]
• 33: A. Ward, A. Jones, and A. Hopper. A new location technique for the active office, 1997.
• 34: 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]
• 35: Y. Yu, R. Govindan, and D. Estrin. Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks. Technical Report UCLA/CSD-TR-01-0023, UCLA Computer Science Department, May 2001.
• 36: Manel Guerrero Zapata , N. Asokan, Securing ad hoc routing protocols, Proceedings of the 1st ACM workshop on Wireless security, p.1-10, September 28-28, 2002, Atlanta, GA, USA [doi>10.1145/570681.570682]
• 37: A. Zemlianov and G. de Veciana. Capacity of ad hoc wireless networks with infrastructure support. IEEE Journal on selected areas in Communications, 23(3), March 2005.
• 38: Honghai Zhang , Jennifer Hou, On deriving the upper bound of α-lifetime for large sensor networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989475]
• 39: M. Zorzi and R. R. Rao. Geographic random forwarding (geraf) for ad hoc and sensor networks: Energy and latency performance. IEEE Transactions on Mobile Computing, 2(4):349--365, 2003.
• 62: Qing Fang , Jie Gao , Leonidas J. Guibas, Locating and bypassing holes in sensor networks, Mobile Networks and Applications, v.11 n.2, p.187-200, April 2006 [doi>10.1007/s11036-006-4471-y]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications; Wireless communication
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Performance, Security

Keywords:
analysis, energy-efficiency, load-balancing, multi-hop wireless networks, routing, simulations