无线传感器网络基于连通性的平面化算法

构建平面拓扑结构是无线传感器网络中一个重要的问题,它是设计许多高效网络协议的基础。传感器网络中许多重要的协议和应用都依赖于平面拓扑结构,比如著名的地理路由协议GPSR、GOAFR等。目前的平面化技术往往都需要网络中节点具有精确的位置测量信息。精确的位置或测距信息在资源受限的传感器网络中往往很难得到,因此基于位置的平面化技术的可应用性受到了很大的限制。设计有效的位置无关的平面化算法成为目前平面化技术研究面临的重要问题。本文提出了一种新的位置无关的分布式平面化算法。该方法仅基于网络的通讯连接关系信息,且运行复杂度低,便于分布式执行。本文通过证明确保所构建拓扑的平面性,并通过仿真实验验证了算法在随机生成网络中的有效性。

A Connectivity-Based Planarization Algorithm for Wireless Sensor Networks

Extracting planar graph from network topologies is of great importance for efficient protocol design in wireless sensor networks. It has become the foundation of many important protocols and applications, such as geographic routing including GPSR, GOAFR, etc. Previous techniques of planar topology extraction are often based on the assumption of accurate node location measurements. It is highly desirable to relax assumptions and extract a planar topology in a location-free and distributed manner. We present a novel method to construct a planar structure for wireless sensor networks in a distributed manner, merely using connectivity information. Our method can extract a provably planar graph from communication graphs. The extensive simulations also show the effectiveness of this design in randomly generated networks.