|
||||||
|
||||||
| Undergraduate Honours Projects | ||||||
|
Carleton University - School of Computer Science Undergraduate Honours Project Fall 2010 orithmic Approach to Geographic Routing in Sensor Networks Elmunir Elgajiji 
ABSTRACT Abstract This paper will focus on one type of routing in sensor networks, geographic routing, that relies on geographic position information. It is only an introduction to the problematic field of geographic routing that presents some specific routing algorithms based on a synthesis of the greedy forwarding and face routing approaches. These algorithms refer to nodes by their location and use those coordinates to route greedily towards the destination. An analysisof the presented algorithms will also be provided from both a worst-case and an average-case perspective. Geographic routing is based on two principal assumptions. First, every node knows its location and its neighboursâÃÂàpositions. Second, the source of a message is assumed to be informed about the position of the destination. One particular issue in geographic routing is how to deal with dead-ends. The greedy algorithm chooses the neighbour closest to destination node to be next node for routing. It can be easily stuck at some local minimum, because there is no neighbour closer to the destination than the current node. Face routing, on the other hand, helps to recover from the previously mentioned situation and find a path to another node. The message is routed from the source to destination by traversing of face boundaries. Keywords: Greedy algorithms routing, face traversal, flooding, greedy routing. Wireless networks, ad hoc networks. |
||||||
|
