【作者】 张路桥；

【导师】 朱清新；

【作者基本信息】 电子科技大学 ， 计算机软件与理论， 2013， 博士

【摘要】 无线传感器网络在整个部署、运行过程中都无人值守，要求传感器节点必须通过本地信息以自组织的形式完成网络拓扑构建，并以无线多跳的方式将监测数据发回控制节点。同时，节点失效、新节点加入、无线信道易受环境影响等问题都使无线传感器网络面临着频繁、不可预见的拓扑结构变化。拓扑控制技术所要解决的正是传感器节点如何自组织地构建网络拓扑，何种拓扑结构能够更有效地应对节点失效，何种拓扑结构更有利于完成特定的监测任务等问题。除此之外，拓扑控制还是降低节点能耗、减小节点间通信干扰、延长网络寿命的主要手段之一。最后，稳定的拓扑结构还是路由协议正常、高效运行的基础；适当的拓扑结构对提高媒体访问控制协议效率也有很大帮助。本文在充分考虑传感器节点能量高度受限、部署密度高等特点的情况下，针对不同应用需求和设计目标，提出了多种拓扑控制算法，主要工作与创新点如下：1）对基于图和基于物理层的干扰定义方法进行分析与对比，得出基于图的干扰定义与真实干扰情况有所出入，基于物理层的干扰定义使用复杂度高的结论。为此，在基于链路覆盖的干扰定义基础上加入对累积干扰的考虑，提出“考虑累积效应的链路干扰定义”。实验结果证明在考虑累积效应后，干扰更接近真实情况，同时还保留了基于图的干扰定义复杂度低的优点。2）对无线传感器网络的基本任务进行讨论，归纳出命令广播与数据采集两种最基本的通信方式，以及两类通信对拓扑结构的不同需求。针对现有拓扑控制算法在设计中未能考虑不同通信类型对拓扑结构不同需求的问题，分别设计了“快速消息分发树”和“平衡数据采集树”两种树状拓扑控制算法。并通过“双向可增链路”增强“平衡数据采集树”的鲁棒性，以便更好的完成数据采集任务。实验结果表明平衡数据采集树较好地兼顾了节点能耗、数据采集时延、节点负载均衡、容错能力等设计目标。3）对簇状拓扑结构的一般流程、步骤进行总结，归纳出现有分簇拓扑控制算法中存在的问题：簇头选举需要多次迭代，低剩余能量节点被选举为簇头，拓扑维护过程中全局拓扑重构频率高、开销大，拓扑构建中簇头节点能耗不均衡，单节点簇处理方法开销大。针对上述问题，提出以下解决方法：“带能量限制的簇头选举”，“利用休眠节点降低全局拓扑重构频率”，“动态簇半径控制”和“层次式成簇”。并运用上述方法提出了“能量高效的自适应分簇拓扑控制”与“层次式动态分簇拓扑控制”两种分簇拓扑控制算法。实验结果证明两种算法都具备能量高效的特点；前者通过限制全局拓扑重构频率，有效延长了网络寿命；后者均衡了簇头间能耗，解决了“漏斗”效应带来的簇头节点负载不均衡，网络连通性容易被破坏等问题。更多还原

【Abstract】 WSN (Wireless Sensor Network) is quite different from traditional wired networkand other wireless networks. In WSNs, manual intervention is not available either in thenetwork deployment or operation phase. Thus sensor nodes are required to setup theoverlay network autonomously, and relay the monitored data back to the base station inmultihop manner. Moreover, the unpredictable node failure, joining of new nodes,unstable wireless channel, and other factors also impose new challenges to the topologyconstruction and maintainenance.Topology control in WSN has to deal with the above mentioned problems andchallenges. More specifically, topology control algorithm should form and maintain aconnected global topology by distributed methods using only localized information,adapt to node failures, and evolve with the specific requirements.Topology control is considered as one of the most important techniques in WSN,not only because it forms and maintains the network topology, but also because it is oneof the most effective methods for saving energy, reducing interference, and prolongingnetwork lifespan. Besides the above, the underlying network topology is the foundationfor the execution of routing protocols, and the guarantee for the efficiency of MAC(Media Access Control) protocol.Several algorithms are proposed in this study in order to improve the performanceof topology control. A summary of our work goes as follows.1) Two different types of interference definition, the graph based interference andthe interference under physical model, are discussed. The graph based interference mayfail to reflect the real interference because of ignoring the accumulated interferenceresulted by concurrent transmission. While the computation complexity of interferenceunder physical model makes it not suitable for algorithm design and analysis.The two definitions are combined by adding consideration of accumulatedinterference to link based interference. And thus it can be more accurate and lessexpensive in computation, which is later proved by analysis and simulation.2) Two basic communications, the command broadcast and data collection, are introduced by discussion of WSN’s basic tasks. It is not hard to tell that the twocommunications have very different requirements for the underlying topology.Thereafter, designing different algorithms for particular communication becomes thenatural choice. Then the Fast Dissemination Tree (FDT) and Balanced Data CollectionTree (BDCT) are presented. Furthermore, a mechanism called addable backup link isused to improve the robustness of BDCT. At last, the simulation shows that balance isachieved among different design goals, including energy efficiency, time delay for datacollection, and load balance.3) The process of existed clustering approaches is given. And after a careful lookinside the steps of clustering, several possible problems are revealed, which are listedbelow.First of all, the cluster head election can be done without any iteration. Secondly,there is a possibility that node with less left energy be elected as cluster head rather thanthe node with a higher energy level. Thirdly, maintaining topology by simply periodicalglobal topology reformation can be both energy and time expensive. Moreover, the loadof cluster heads is not evenly distributed. At last, the process of single node cluster isneither effective nor efficient.Our solutions for those problems are cluster head election with energy constraint,restricted global topology reformation by utilizing sleeping nodes, dynamic clusterradius, and hierarchical intra-cluster topology, which are later used in designing AEEC(Adaptive Energy Efficient Clustering) and ACDCR (Adaptive Clustering withDynamic Cluster Radius). It is demonstrated by simulation that AEEC prolongs thenetwork lifespan, and ACDCR alleviates the influence of ‘funneling effect’.更多还原