10-02-2010, 11:08 PM
With fully directional communications, nodes must track the positions of their neighbors so that communication with these neighbors is feasible when needed. Tracking process introduces an overhead, which increases with the number of discovered neighbors. The overhead can be reduced if nodes maintain only a subset of their neighbors; however, this may increase the length of paths between node pairs in the network. In this work, we study the tradeoffs between node degree and path stretch. We first design a topology control algorithm to optimize this tradeoff. Assuming that nodes communicate with their directional neighbors using circular directional transmissions, we model the original graph as a unit disk graph (UDG). Given a UDG G, our algorithm finds a sparse subgraph G' with a maximum degree of 6, and connecting each node pair u,v by a path of length hops_{G'}(u,v)=O(\hops_G(u,v)+\log\Delta), where Delta is the maximum degree in G, hops_{G}(u,v) denotes length of the shortest path between u, v in G. We show that this result is near-optimal. Based on the insights gained from this design, we next construct a simpler, more practical scheme that integrates fully-directional neighbor discovery and maintenance with topology control strategy. We simulate both algorithms and compare their performances.
