Konferenzbeitrag
An efficient implementation of the greedy forwarding strategy
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Zusatzinformation
Datum
2004
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik e.V.
Zusammenfassung
A wireless sensor network needs a suitable multihop routing protocol to facilitate the communication between arbitrary sensor nodes. Position-based routing protocols are attractive for large-scale sensor networks due to their location awareness and scalability. A large number of position-based routing protocols use the greedy forwarding strategy. This paper presents an efficient implementation of the greedy forwarding algorithm. The nodes of the sensor network are viewed as points in the plane. Each node uses a Voronoi Diagram to generate a subdivision of the plane, which is solely based upon its local neighborhood. Every node forwards incoming messages to that Voronoi Cell the destination node belongs to, according to its position information. The complexity of our solution is O(n log n) for computing the Voronoi Diagram, which is typically done only once, but only O(log n)$ for finding the nexthop node. Interestingly, n is not the total number of nodes in the network here, but only the number of single hop neighbors.