Geographic Routing with Constant Stretch in Large Scale Sensor Networks with Holes Conference Paper uri icon

abstract

  • Geographic routing is well suited for large scale sensor networks deployments, because the per node state it maintains is independent of the network size. However, due to the "local minimum" caused by holes/obstacles, the path stretch of geographic routing can grow as O(c 2), where c is the length of the optimal path. Recently, VIGOR, a geographic routing protocol based on the visibility graph, shows that a constant path stretch can be achieved. This, however, is possible with increased overhead. To address this issue, we propose GOAL (Geometric Routing using Abstracted Holes), a routing protocol that provably achieves a constant path stretch, with lower message, space and computational overhead. We develop a novel distributed convex hull construction (DCC) algorithm that compactly describes holes. This compact representation of a hole is leveraged by nodes to make locally optimal routing decisions. Our theoretical analysis proves the constant stretch property and average stretch of GOAL. Through extensive simulations and a hardware implementation, we demonstrate the effectiveness of GOAL and its feasibility for large-scale sensor networks. In our network settings, GOAL reduces the energy consumption by up to 32%, routing table size by an order of magnitude, when compared with VIGOR. 2011 IEEE.

name of conference

  • 2011 IEEE 7th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)

published proceedings

  • 2011 IEEE 7th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)

author list (cited authors)

  • Won, M., Stoleru, R., & Wu, H.

citation count

  • 6

complete list of authors

  • Won, Myounggyu||Stoleru, Radu||Wu, Haijie

publication date

  • October 2011