A grid-based sink location service for large-scale wireless sensor networks

ABSTRACT

Location-based routing (LBR) is one of the most widely used routing strategies in large-scale wireless sensor networks (WSN). With LBR, small, cheap and resource constrained nodes can perform the routing function without the need of complex computations and large amount of memory space. Further, the nodes don't need to incur in energy consuming periodic advertisements because routing tables, in the traditional sense, are not needed. One important assumption made on most LBR protocols is the availability of a location service or mechanism that the nodes can utilize to find other nodes positions. Although several mechanisms exist in the literature, no efficient mechanism is available for a source to find the location of the sink or sinks. In this paper, we introduce the Anchor Location Service (ALS) protocol, a grid-based location service strategy for source nodes to find the sinks' locations and support location-based routing in large-scale wireless sensor networks. We describe the grid set up and query processes and evaluate the delay and overhead of this mechanism by varying the number of sinks, considering networks of different sizes, and the case where the sink nodes move, not common in the literature. Using simulations, we demonstrate that ALS provides the required service in a scalable and efficient manner.

REFERENCES

• 1: 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]
• 2: George Lukachan , Miguel A. Labrador, SELAR: Scalable Energy-Efficient Location Aided Routing Protocol for Wireless Sensor Networks, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04), p.694-695, November 16-18, 2004 [doi>10.1109/LCN.2004.111]
• 3: H. Luo, F. Ye, J. Cheng, S. Lu, and L. Zhang. TTDD: A Two-tier Data Dissemination Model for Large-Scale Wireless Sensor Networks. In Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications, 2003.
• 4: M. Mauve, A. Widmer, and H. Hartenstein. A Survey on Position-Based Routing in Mobile Ad Hoc Networks. IEEE Network, 15(6):30--39, 2001.
• 5: NS-2 Network Simulator. http://www.isi.edu/nsnam/ns/.
• 6: I. Stojmenovic. Position-based Routing in Ad Hoc Networks. IEEE Communications Magazine, 40(7):128--134, 2002.

INDEX TERMS

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

General Terms:
Performance

Keywords:
energy efficiency, location-based routing, multiple sinks