Abstract

We propose distributed link reversal algorithms to circumvent communication voids in geographic routing. We also solve the attendant problem of integer overflow in these algorithms. These are achieved in two steps. First, we derive partial and full link reversal algorithms that do not require one-hop neighbor information, and convert a destination-disoriented directed acyclic graph (DAG) to a destination-oriented DAG. We embed these algorithms in the framework of Gafni and Bertsekas [1] in order to establish their termination properties. We also analyze certain key properties exhibited by our neighbor oblivious link reversal algorithms, e.g., for any two neighbors, their t-states are always consecutive integers, and for any node, its t-state size is upper bounded by log(N). In the second step, we resolve the integer overflow problem by analytically deriving one-bit full link reversal and two-bit partial link reversal versions of our neighbor oblivious link reversal algorithms. We also discuss the work and time complexities of the proposed algorithms.

6. Conclusion

600 We proposed neighbor oblivious link reversal (NOLR) schemes to get a destination oriented network out of the local minimum condition in geographic routing. Our algorithms fall within the general class of GB algorithms [1]. We then argued that both the algorithms, GB and NOLR, may suffer the problem of state storage overflow. This led us to modify the NOLR algorithms to obtain 605 one bit full link reversal and two bit partial link reversal algorithms. The finite state algorithms inherit all the properties of NOLR algorithms which in turn inherit the properties of GB algorithms, and are pragmatic link reversal solutions to convert a destination-disoriented DAG to a destination-oriented DAG. The communication is lightweight since only broadcasts (hello packets and new 610 state advertisements) contain state information (acknowledgements need not), and further, acknowledgements are sent only by the neighbors that have lower states than the querying node. We have given order estimates of the resulting savings in computations, communication and storage overheads.