面向无线ad hoc网络的一种平面t-支撑图

Planar t-spanner for wireless ad hoc network

拓扑控制算法的目标是为无线adhoc网络确定合适的底层拓扑。在无线adhoc网络中,几何路由协议是一类重要的路由协议,为了保证消息转发的可达性和限制路由长度,它要求底层拓扑满足连通性、平面性和稀疏性,并且是原拓扑的t-支撑图。本文提出了一种新的几何结构AUDel图,并提出了两种低通信开销的构造AUDel图的局部拓扑控制算法。理论分析表明,AUDel图满足上述要求,我们提出的拓扑控制算法的通信开销小于其它构造平面t-支撑图的拓扑控制算法。模拟实验验证了以上结论。

The aim of topology control was determining an appropriate topology for wireless ad hoc networks. In wireless ad hoc networks geometric routing protocol was a kind of important routing protocols, which requires the underlying topology be planar, sparse, connected and t-spanner in order to guarantee the delivery of message and bound the routing length. A new geometry structure named AUDel was proposed and two efficient algorithms to construct the new structure were proposed. Theoretic analysis showed that AUDel satisfies those properties, and our algorithms are much more communication efficient than previous algorithms which construct planar t-spanner of the original topology. These conclusions are confirmed by simulation results.