Balancing traffic load in wireless networks with curveball routing

ABSTRACT

We address the problem of balancing the traffic load in multi-hop wireless networks. We consider a point-to-point communicating network with a uniform distribution of source-sink pairs. When routing along shortest paths, the nodes that are centrally located forward a disproportionate amount of traffic. This translates into increased congestion and energy consumption. However, the maximum load can be decreased if the packets follow curved paths. We show that the optimum such routing scheme can be expressed in terms of geometric optics and computed by linear programming. We then propose a practical solution, which we call Curveball Routing which achieves results not much worse than the optimum.

We evaluate our solution at three levels of fidelity: a Java high-level simulator, the ns2 simulator, and the Intel Mirage Sensor Network Testbed. Simulation results using the high-level simulator show that our solution successfully avoids the crowded center of the network, and reduces the maximum load by up to 40%. At the same time, the increase of the expected path length is minimal, i.e., only 8% on average. Simulation results using the ns2 simulator show that our solution can increase throughput on moderately loaded networks by up to 15%, while testbed results show a reduction in peak energy usage by up to 25%. Our prototype suggests that our solution is easily deployable.

REFERENCES

• 1: M. Kalantari, M. Shayman, "Design Optimization of Multi-Sink Sensor Networks by Analogy to Electrostatic Theory" IEEE WCNC, 2006
• 2: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, 2000.
• 3: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 4: 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]
• 5: Chieh-Yih Wan , Shane B. Eisenman , Andrew T. Campbell, CODA: congestion detection and avoidance 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.958523]
• 6: Bret Hull , Kyle Jamieson , Hari Balakrishnan, Mitigating congestion in 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.1031512]
• 7: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries 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.958500]
• 8: Demibras, M., Arora, A., AND Gouda, M. A pursuer evader game for sensor networks. In Proc. of the Sixth Symposium on Self-Stabilizing Systems, 2003
• 9: S. Baek and G. de Veciana, Spatial Energy Balancing Large-scale Wireless Multihop Networks, IEEE INFOCOM05
• 10: Karim Seada , Marco Zuniga , Ahmed Helmy , Bhaskar Krishnamachari, Energy-efficient forwarding strategies for geographic routing in lossy 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.1031509]
• 11: ns2 simulator, http://www.isi.edu/nsnam/ns/
• 12: TinyOs, http://www.tinyos.net.
• 13: Jie Gao , Li Zhang, Load-Balanced Short-Path Routing in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.17 n.4, p.377-388, April 2006 [doi>10.1109/TPDS.2006.49]
• 14: G. Yashar and A. Keshavarzian, Load balancing in ad hoc networks: Single-path routing vs. multi-path routing, IEEE Infocom 2004.
• 15: P. Gupta, P. R. Kumar, "Towards an Information Theory of Large Networks: An Achievable Rate Region", IEEE Transactions on Information Theory, 2003
• 16: Karim Seada , Marco Zuniga , Ahmed Helmy , Bhaskar Krishnamachari, Energy-efficient forwarding strategies for geographic routing in lossy 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.1031509]
• 17: Scott Shenker , Sylvia Ratnasamy , Brad Karp , Ramesh Govindan , Deborah Estrin, Data-centric storage in sensornets, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.137-142, January 2003 [doi>10.1145/774763.774785]
• 18: Costas Busch , Malik Magdon-Ismail , Jing Xi, Oblivious routing on geometric networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074022]
• 19: Intel Mirage testbed, http://mirage.berkeley.intel-research.net
• 20: 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]
• 21: Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, Geographic routing made practical, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.217-230, May 02-04, 2005
• 22: Proof for Theorem 1 listed at: www.cs.berkeley.edu/~popa/proof_wireless_disc_load.pdf
• 23: Greenstein B., Estrin, D., Govindan, R., Ratnasamy, S., Shenker, S. DIFS: A distributed index for features in sensor networks. In IEEE WSNA 2003.
• 24: http://research.microsoft.com/mesh/
• 25: P.P. Pham and Sylvie Perreau, "Performance analysis of reactive shortest path and multi-path routing mechanism with load balance", IEEE Infocom 2003
• 26: Esa Hyytia , Pasi Lassila , Jorma Virtamo, Spatial Node Distribution of the Random Waypoint Mobility Model with Applications, IEEE Transactions on Mobile Computing, v.5 n.6, p.680-694, June 2006 [doi>10.1109/TMC.2006.86]
• 27: E. Hyytiä, J. Virtamo, "On Load Balancing in a Dense Wireless Multihop Network", NGI 2006, Valencia, Spain
• 28: Jehoshua Bruck , Jie Gao , Anxiao (Andrew) Jiang, MAP: medial axis based geometric routing in sensor networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080839]
• 29: R. Catanuto, S. Toumpis, G. Morabito, "Opti{c,m}al: Optical/Optimal Routing in Massively Dense Wireless Networks", IEEE Infocom 2007

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
geographic routing, load balancing, wireless networks