【作者】 张瑞华；

【导师】 袁东风；

【作者基本信息】 山东大学 ， 通信与信息系统， 2007， 博士

【摘要】 无线传感器网络是由低成本、低功耗、具备感知、数据处理、存储和无线通信能力的微型传感器节点通过自组织方式形成的网络。无线传感器节点作为微小器件,只能配备有限的电源,在有些应用场合下,更换电源是近乎不可能的。这使得传感器节点的寿命在很大程度上依赖于电池的寿命,所以降低功耗以延长系统的寿命是无线传感器网络设计首要考虑的问题。网络分层机制、网络覆盖与能量消耗密切相关,分簇算法在网络分层机制中起决定性作用;节点配置方式、冗余节点查找则是影响网络覆盖的重要因素。本文主要针对无线传感器网络的分簇算法、传感器节点配置和冗余节点查找等问题从能耗效率方面进行深入研究。主要研究内容和成果如下;1、提出了一个能量高效的最大选票和负载平衡的传感器网络分簇算法（anmaximum-Votes and Load-balance Clustering Algorithm,VLCA）,并把该算法应用在实际场景中对能耗进行验证。在大规模的无线传感器网络中,每个节点采集的数据最终都要传输到网关节点,可以直接单跳传输到网关,也可以通过多跳传输到网关。研究表明,将传感器节点组织成簇的形式可以有效地减少网络的能量消耗,延长网络的生命周期。许多能量有效的路由协议都是在簇结构的基础上进行设计的。在分级结构的网络中,簇头节点可以收集成员节点的数据并执行数据融合,将传感器感测的大量数据组合成少量有效的信息集合经多跳路由发送到网关节点。簇头利用TDMA方式管理簇成员,簇成员的功能比较简单,不需要维护复杂的路由信息,大大减少了网络中路由控制消息的数量,具有很好的可扩充性。由于簇头节点可以随时选举产生,分级结构也具有很强的抗毁性。在分析已有的无线传感器网络分簇算法的基础上,本文设计了一种最大选票和负载平衡的高能效的传感器网络分簇算法（VLCA）。传感器节点的重要性应该由其所有邻居（包括自己）反映出来,而不仅仅是由其局部属性决定。传感器节点收集它们邻居的选票并且计算收到的所有选票。传感器节点积累的选票越多,它在整个网络中就越重要。每个节点分发给邻居的选票取决于该节点以及所有邻居节点的剩余能量。本文给出了VLCA算法的伪代码,对其性能进行了理论分析,并和其它经典的分簇算法对比验证。该算法是完全分布的,不依赖网络特定区域、大小和其拓扑结构,模拟结果显示它能减少簇的数量20%到50%。进一步把该算法应用在实际场景中,和其它能量效率的分簇算法相比,结果显示能延长传感器网络的生命周期。2、提出了两种有效可行的无线传感器网络节点配置机制,并进一步把两种线性网络模型推广至大规模网络,设计实现了一种基于非均匀分簇的路由机制,并从能耗角度加以验证。无线传感器网络节点的配置和定位、跟踪一样,是无线传感器网络的一个基本问题,因为它反映了无线传感器网络的成本和监视能力。节点配置策略很大程度上可增强网络检测质量,减少能耗最终延长节点的寿命。本文通过对传感器节点无线通信能耗模型的扩展,在两种线性网络模型下,分析并仿真实现了多数据源负载时,传输信息的能耗、能量效率;通过对比分析,在无线传感器网络节点配置时,提出了两种有效可行的配置机制。当节点等间距放置时,存在一个最优的单跳距离d_opt,它仅仅依赖于传输的数据包长度,收发器的电路特性以及信道损耗,与源节点到sink节点的总距离r无关,与节点的个数无关;按此方式布置的传感器网络,系统能耗最低。为了进一步平衡各节点的负载,延长网络寿命,提出了另一种机制,节点按优化间距布置,优化间距由理论分析以公式形式给出并进行了仿真验证。在无线传感器网络节点布置时,这两种机制对提高能量效率,延长网络的寿命提供了很大的帮助。结合网络分层结构,利用传感器节点的两种配置机制,进一步把两种线性网络模型推广至大规模网络,实现了一种基于非均匀分簇的路由机制,并从能耗角度加以验证。基于分簇的层次路由方法在提高网络的生命周期方面特别有效。由于簇头距离网关节点的距离一般较远,研究表明在簇头与网关节点之间通信时采取多跳的方式更有利于节约能量,然而这种做法带来了一个能量消耗不均衡的问题;在所有传感器节点的数据都发送到网关节点的“多对一”数据传输模式中,靠近网关的簇头节点由于需要转发大量来自其它簇头的数据而负担过重,过早耗尽自身能量而失效,造成网络分割,从而降低整个网络的存活时间。本文在分析网络分簇、网络节点配置等问题的基础上,设计实现了一种非均匀分簇的传感器网络路由协议。对于大规模网络利用第一个创新点提出的基于最大选票的分簇算法进行非均匀分簇,簇头节点利用时分复用机制（TDMA）对成员节点管理;簇头节点收集并融合成员节点数据经多跳路由传输到网关节点。根据无线传感器网络节点配置时两种有效可行的节点配置机制,给定簇头节点和网关节点距离r,存在一个最优跳数k_opt=r/d_opt,当所有k_opt-1个中继节点正好位于簇头到网关间的k_opt等分点位置时,端到端传输的总功耗最小。然而,在实际的网络环境中,受节点密度的限制,在每个k_opt等分点的位置恰好找到中继节点往往是不现实的,但选择最接近最优中继位置的簇头节点作为中继节点,从而最大限度地降低端到端传输的能耗,这正是我们设计的簇头间多跳路由的基本思想。为了验证该路由协议,利用最大选票分簇算法,对大规模无线传感器网络进行均匀分簇和非均匀分簇,利用该路由协议传输簇头节点融合的数据到网关节点,对其能耗、网络生命周期进行对比验证。模拟结果显示该非均匀分簇的路由机制可以平衡网络负载,使各节点的能量均匀消耗,进一步延长整个网络的生命。3、提出了一种基于边界覆盖的冗余传感器节点查找算法EDRNS（EfficientDistributed Redundant Node Search）,用于网络静态覆盖控制;结合无线传感器网络的特点及其应用,提出了一种适用于移动目标跟踪的动态覆盖控制算法——ID-DCC（Information Driven Dynamic Coverage Control）,并把EDRNS算法应用于ID-DCC算法中。每个传感器节点存在一定的传感范围,当大量的传感器节点随机部署在网络的感知区域时,这些传感器节点的传感范围可能存在交叠（overlap）,从而导致覆盖冗余传感器节点的出现,如何寻找这些冗余节点并控制它们定期进入休眠状态是覆盖控制需要解决的问题。因为进入休眠状态的传感器节点基本上不消耗能量,可以大大降低整个传感器网络的能量消耗。为此,本文提出了一种高能效分布式基于边界覆盖的冗余传感器节点查找算法EDRNS（Efficient Distributed Redundant Node Search）,来实现对整个网络的静态覆盖控制。该算法实现了传感器节点的覆盖范围问题由二维空间向一维空间有效地转化,从而降低了解决问题的复杂度;该算法不仅能够保证被监测区域的完全网络覆盖,而且能够快速地找到网络中的冗余节点;各个传感器节点独立执行冗余节点查找算法,若目标区域中传感器节点的冗余度较低时,算法可以提前结束,从而减少额外计算量,节省整体系统能耗。目前大多数的覆盖控制机制是静态的,即在整个网络传感区域内实施静态控制管理,此时的覆盖区域是固定不变的。但在众多的应用场景中,如移动目标跟踪,大量距离目标较远的传感器节点因为检测不到目标而没有必要参与拓扑管理,如果采用静态的覆盖控制机制则会造成较大的能量浪费。此时如果实施动态覆盖控制,只在移动目标的周围实施合适的覆盖控制,并且让覆盖控制的区域随着目标的移动而动态变化,这样将能够有效地避免静态拓扑管理造成的能量浪费。本文实现了用于移动目标跟踪的动态覆盖控制算法ID-DCC（Information DrivenDynamic Coverage Control）。该算法通过在跟踪移动目标的附近动态地构造一个有效的拓扑管理区域,由区域内的传感器节点负责完成所要求的任务,而区域之外的节点均进入休眠状态;同时,ID-DCC算法结合EDRNS算法来进一步对所构造的拓扑管理区域进行覆盖冗余控制,可有效地节省无线传感器网络系统的整体能耗。更多还原

【Abstract】 Wireless sensor network（WSN）is a self-organizing networks consist of low-cost、low-power tiny sensor nodes that can wireless communication with each other to perform sensing,data processing and storage cooperatively.Wireless sensor node is a tiny device with limited power,and change battery is almost impossible in some applications.This makes the lifetime of nodes mostly depend on the battery,so reduced power consumption to extend the lifetime of network is the primary problem in the research.Network hierarchical mechanisms,network coverage have closely related with energy consumption,clustering algorithm play a decisive role in Network hierarchical mechanisms.How to deploy the nodes and how to find out the redundant nodes is an important factor on network coverage.This paper carry a deep research mainly on clustering algorithm,deploy of nodes and search algorithm of the redundant nodes from energy efficient.The main research and contributions are as follows:1.This paper proposes an energy efficient maximum-Votes and Load-balance Clustering Algorithm（VLCA）,and further validates energy consumption by apply the algorithm in practical scenarios.In large-scale wireless sensor networks,all information collected by each node will eventually be to the sink nodes.This information can be transferred to sink by single-hop or multi-hop.Research show that energy consumption of network will be fewer and the lifetime of network will be longer if nodes are organized in the form of cluster.Much energy efficient routing protocols are designed depends on the cluster structure.In hierarchical network,cluster heads can collect and aggregate data from its cluster members,and make the large amount of data to be little effect information,and then send the information to the sink by multi-hop communication.The cluster head managements cluster members by TDMA protocol. Functions of the cluster members are relatively simple,and do not need maintain complicated routing information,greatly reducing routing control information,has a good scalability.Because cluster heads could be elected at any time,hierarchical network have strong ability to withstand destroy.On the base of analysis WSN clustering algorithm,this paper proposes an energy efficient maximum-Votes and Load-balance Clustering Algorithm（VLCA）.A node’s importance should be reflected from all its neighbors（include itself）insead of from its local properties alone.Sensors collect votes from their neighbors and calculate the total vote received.The more votes a sensor accumulates,the more important it is in the whole network.Node casts a vote for its neighbor depends on all residual energy of the node and its neighbor.This paper provides the pseudo code of the algorithm and theoretical analysis,and compares it with sutra clustering algorithm.This algorithm is completely distributed,location-unaware and independent of network size and topology.Simulation results show that our algorithm can reduce the number of clusters by 20%-50%.We further apply the algorithm in practical scenarios,and prolong the lifetime of a sensor over that of existing energy-efficient clustering protocols.2.This paper proposes two valid deployment mechanisms of sensors,and extends further two linear network model to a large-scale networks,and validates an uneven clustering routing mechanism from the perspective of energy consumption.As well as orientation and track,deployment of the nodes is the basic problem,which reflects the cost and monitoring ability of WSN.The strategy of deployment can enhance network monitoring quality and reduce energy consumption,and eventually extend node’s life. Using an extension of energy consumption model of the wireless sensor node and two linear network models,this paper analyzes the energy consumption and energy efficiency by individual nodes and the network as a whole,when there are multiple transmission sources.By contrast,we propose two valid deployment mechanisms of sensors.First,when nodes are deployed with equidistant spacing,there is an optimum one-hop transmission distance d_opt,and it is independent of the physical network topology,the number of transmission sources,and the total transmission distance.It only depends on the propagation environment and the device parameters.Second,more improving energy efficiency,balancing every node’s load,extending a network’s lifetime,another deployment mechanism is that nodes are deployed with optimal spacing;every node optimal spacing formula is present.Two deployment mechanisms of sensor nodes are good useful with energy efficiency in wireless sensor networks.Combining network hierarchical mechanisms with the two deployment mechanisms, we extend further two linear network model to a large-scale networks,and validates an uneven clustering routing mechanism from the perspective of energy consumption.As the distance between cluster head and sink is large,research show that communication between cluster head and sink reduces energy consumption by multi-hop forwording model,but it arises a problem of energy consumption unbalance.On the "many-to-one" traffic patetrn as all sensor nodes send data to the sink node,the cluster heads closer to sink are burdened with every relay traffic,they will die much faster than the other cluster heads,reducing sensing coverage and causing network partitioning,which reduces the network lifetime.Based on the analysis of cluster network,the deployment of the network,this paper design an uneven clustering protocol in wireless sensor network.For large-scale networks we carry out uneven clustering using VLCA,cluster heads manage its members by TDMA mechanism.Cluster heads collect and aggregate the data from its members,and then transmit the data to sink via multi-hop communication. Base on the two valid deployment mechanisms of nodes,and given r from cluster head to sink,there is an optimal hopk_opt=r/d_opt.When k_opt-1 relay nodes lie in k_opt equidistant partition between cluster head and sink,energy consumption of end-to-end transmission is minimized.However,in practical network environment,restricted by the node density,it is not reliable that we find relay node just in each k_optequidistant partition.It is a good choice that we select the nearest node to k_optequidistant partition, thus we maximized to reduce energy consumption of end-to-end transmission.This is the basic idea of our multi-hop routing.In order to validate the routing protocol,we carry out even-clustering and uneven-clustering for the network by VLCA,and transmit data to sink by our routing protocol,and compare its energy consumption and lifetime. Simulation results show that the uneven clustering routing mechanism can balance every node’s load and energy consumption,further extend a network’s lifetime. 3.This paper proposes a redundant node search algorithm based on border coverage, and apply the algorithm to the dynamic coverage control mechanism with tracking mobile target.Each node has a limited sensing range,when a large number of sensors are deployed randomly in the monitoring region,this meight produce the coverage-overlap between sensing range of nodes,thus cause the appearance of redundant nodes. How to search these redundant nodes and control their regular sleep is the problem of coverage control.Because sleep nodes does not consume energy basically,so network energy consumption.can be reduced greatly.Therefore,this paper proposes a redundant nodes search algorithm EDRNS（Efficient Distributed Redundant Node Search）, realizing the static coverage control of the entire network.Through transforming about the coverage range from two-dimensional space to one-dimensional space,The EDRNS algorithm can effectively simplify and reduce the complexity of the problem.The algorithm not only can guarantee the overall coverage of the monitoring region,but also can quickly search redundant nodes in the network. All nodes implement the redundant node search algorithm by themselves,if the redundancy of nodes in the monitoring region is lower,the algorithm can be ended early, thus reducing the additional computation,and the energy consumption of the system.Today most coverage control mechanism is static,it means that we control and manage the entire network by static mechanism,so coverage region is fixed.But in some application scenarios,such as mobile target tracking,most nodes which are farside from the target cannot sense the target or the error of the sensing datas,if these sensor nodes are in active,which will be of no value,moreover this will waste the energy of the sensor node.If we use dynamic coverage control,we only implement coverage control around a mobile target,and the coverage region varied with the mobile target,which can effectively avoid energy waste of static topology management. Therefore,this paper implement a dynamic coverage control algorithm ID-DCC （Information Driven Dynamic Coverage Control）which is suitable for tracking mobile target.Namely through constructing effective management-regions nearby the mobile targets,only the nodes in management-regions responsibly completed the requested task,the rest nodes outside the management-regions were put in sleep;At the same time,the ID-DCC algorithm unified the EDRNS algorithm to further carry on the coverage-redundancy control to the management-regions,therefore effectively reduce the overall energy consumption of the network system.更多还原