Position-Based Routing Protocols for Ad Hoc Networks - Application and Multidisciplinary Aspects of Wireless Sensor Networks - page 46

the closest neighbor to the destination for example [ 1, 6 ]. Similarly, each intermediate
node selects a next hop node until the packet reaches the destination. In order for
the nodes to be enable to do this, they periodically broadcast small packets (called
beacons) to announce their position and enable other nodes maintain a one-hop
neighbor table [ 4, 9, 12 ]. Such an approach is scalable and resilient to topology
changes since it does not need routing discovery and maintenance; however, peri-
odic beaconing creates lot of congestion in the network and consumes nodes'
energy [ 1, 4, 21 ].
While the beaconing frequency can be adapted to the degree of mobility, a fundam
ental problem of inaccurate (outdated) position information always presents: a
neighbor selected as a next hop may no longer be in transmission range. This leads
to a significant decrease in the packet delivery rate with increasing node mobility.
To reduce the inaccuracy of position information, it is possible to increase the bea-
coning frequency. However, this also increases the load on the network by creating
lot of congestion, increasing the probability of collision with data packets, and
consuming nodes' energy [ 1, 4 ].
Unfortunately, greedy routing may not always find the optimum route, even it
may fail to find a path between source and destination when one exists [ 6, 21 ]. An
example of this problem is shown in Fig. 4.1 . Nodes' transmission range is shown
in the figure.
Note that there is a valid path from S to D. The problem here is that S is closer to
the destination D than any of the nodes in its transmission range; therefore, greedy
forwarding will reach a local maximum from which it cannot recover. Generally,
greedy forwarding works well in dense networks, but in sparse networks it fails due
to voids (regions without nodes) [ 1, 9 ].
In restricted directional flooding, the sender will broadcast the packet (whether
the data packet or route request packet) to all single-hop neighbors toward the des-
tination. The node which receives the packet, checks whether it is within the set of
nodes that should forward the packet (according to the used criteria). If yes, it will
retransmit the packet. Otherwise, the packet will be dropped. In restricted direc-
tional flooding, instead of selecting a single node as the next hop, several nodes
participate in forwarding the packet in order to increase the probability of finding
Fig. 4.1 Greedy routing failure example