无线传感器网络拓扑控制算法研究

【作者】 赵楠楠；

【导师】 武穆清；

【作者基本信息】 北京邮电大学 ， 通信与信息系统， 2011， 博士

【摘要】 无线传感器网络能够协作感知,采集网络分布区域内各种监测对象的信息,并对这些信息进行处理,最终传送到用户端,在新一代网络中具有关键性作用。由于传感器网络节点能量受限,为延长网络生存周期,拓扑控制算法成为近年来无线传感器网络的研究热点。这类算法的作用是通过种种手段对网络拓扑进行改造,减小节点的能耗,延长网络的生存周期。无线传感器网络的另一特点是没有基站一类的基础设施,众多节点在软硬件上同构,通过自组织而形成网络。分布式算法非常适合这一特点。因此,本文重点研究基于本地信息的分布式拓扑控制算法。我们称基于常数跳内收集到的信息而运行的算法为本地化算法。拓扑控制算法改造网络拓扑的方式主要有两大类：一种是通过调整节点发射功率来减小节点能耗,降低通信干扰。另一种是通过构造骨干网将网络分层,网络中的节点轮流负责转发数据,均衡节点间能量消耗,延长网络寿命。前一类算法形成的网络拓扑是平面的,后一类算法构造了层次型的拓扑。通过研究拓扑形态对拓扑控制算法在网络生存周期内的能耗的影响,我们发现层次型的拓扑结构,使得算法的能耗更优,进一步的分析表明,树型结构的骨干网不能实现本地化维护,能耗较差。以这两个结论为依据,我们提出了构建网状的连通控制集作为骨干网的Meshed CDS算法,它在大多数情况下能够实现本地化拓扑维护,算法运行的能耗较低。考虑到骨干网节点能耗高于其它节点,减小骨干网节点数量也是延长网络生存时间的必要手段。我们提出的网状连通控制集MESH-CDS算法,不但能够实现完全的本地化拓扑维护,而且骨干网节点数量相对于网状结构的连通控制集Meshed CDS算法大大减小。更有价值的是,该算法不需要节点在之间同步运行,这非常适合节点能量动态变化的无线传感器网络。最后我们提出节点数量缩减的网状连通控制集DMESH-CDS算法,它优先选择节点度数更大的节点成为骨干网节点,在网状连通控制集MESH-CDS算法基础上对骨干网的大小做了进一步的削减。更多还原

【Abstract】 Wireless sensor network (WSN) which is able to perceive and collect the information of objects under monitoring in the distribution of WSN, process and send them to the client, plays a key role in the next generation of networks. Since WSN is energy constrained, topology control algorithms which are designed to save energy have become the research hotspot in recent years. Topology control algorithms archieve their goals by making special modifications to the network topology. Another feature of WSN is that there is not any network infrastructure, such as base stations, in it. All the sensor nodes have been built equally in hardware and software, which makes them self-organized to form the network topology. Obviously, distributive algorithms are applicable to WSN. So, this article focuses on localized distributive algorithms of topology control. An algorithm which only needs information within a constant number of hops is called "localized".Topology control algorithms modificate the network topology in mainly two ways:One way is to adjust the transmit power of sensor nodes, in order to save energy; the other one is to construct a backbone of network, which divide the nodes into different levels so that the energy consumption will be balanced among them. Finally, the lifetime of the network will be prolonged. We noticed that the first kind of algorithms make a flat topology as well as the latter kind makes a hierarchical network.According to the research on the relationships between topology structure and energy cost of topology algorithms, we find that the hierarchical structures lead to a better performance on energy cost of algorithms. Further more, we conclude that the tree-type backbone has a large energy cost because there is no localized maintenance scheme. Under these two conlusions, we proposed an algorithm, "Meshed CDS", which makes a mesh connected dominating sets (CDS) to be the backbone. It has a low energy cost since in most cases, the backbone can be maintained using localized manner.Reducing the number of backbone is essential for WSN because the backbone nodes on backbone consume more energy than the other nodes. We proposed a "MESH-CDS" algorithms which is not only has a completely localized topology maintenance scheme, but also much less number of backbone nodes. In addition, it can be run asynchronously among all the nodes in the network.At last, we proposed an algorithm which is named "DMESH-CDS". This proposal selects the nodes with lager degrees to be backbone nodes. The simulation result shows that the backbone’s size has been decreased compared with "MESH-CDS".更多还原