【作者】 裴智强；

【导师】 范平志； 徐昌庆；

【作者基本信息】 上海交通大学 ， 通信与信息系统， 2013， 博士

【摘要】 无线传感器网络是将传感器节点布局在目标区域内用于监视特定对象的一种面向应用的网络体系结构。在面向区域覆盖的应用中，无线传感器网络分为毯状覆盖网络和带状覆盖网络。毯状覆盖是指目标区域内任何一点被至少一个或k个节点所覆盖，也被称之为全覆盖或k-覆盖网络；带状覆盖是指穿过目标区域的任何路径与至少一个或者k个节点的覆盖区域相交，也被称之为k-带状覆盖。节点布局是形成无线传感器网络初始拓扑结构的一个非常重要的阶段，分为非随机布局和随机布局。在原始森林中布局毯状传感器网络预警火灾，或者在边境线上布局带状传感器网络预警偷渡者，通常采用飞机抛洒或者火箭投掷的随机布局方式。随机抛洒的传感器节点具有位置不确定性，再加上无线传感器网络具有的冗余特性，需要通过拓扑控制策略周期性地选择其中的一部分节点处于工作状态，或者需要通过调整某些传感器节点位置使网络具有合适的拓扑结构。无线传感器网络拓扑控制领域目前主要存在下列问题：1.覆盖率最大化。覆盖率是被传感器网络覆盖的区域面积与目标区域总面积的比值。针对随机布局的网络，难免存在一部分区域仅仅被一个传感器节点所覆盖，那么覆盖这部分区域的节点必须要求一直处于工作状态，否则将降低网络覆盖率，而目前的研究成果中没有有效的机制使这部分节点一直处于工作状态。2.1-覆盖占比最大化。1-覆盖占比是被1个节点覆盖的区域面积与目标区域总面积的比值。使1-覆盖占比最大能够减少工作节点数量从而延长网络生命周期，而目前的研究成果没有将其作为拓扑控制优化的约束条件，因此将会影响到网络生命周期。3.采用可移动传感器进行拓扑控制的能耗最小化。能耗最小化包括节点消耗能量之和最小化以及各个节点消耗能量的方差最小化两个方面，其中后者能够使网络中的剩余能量分布更为均衡从而延长网络生命周期，但是目前的研究成果忽略了将此作为网络拓扑控制优化的约束条件。4.完全带状覆盖网络。完全带状覆盖网络是以概率为1检测入侵目标的网络。该类网络能够确保网络监视目标的效果，提高网络的可靠性。但是目前的研究成果仅仅实现了非完全带状覆盖网络，即网络中存在漏检的现象。针对上述问题，本课题主要研究无线传感器网络的拓扑结构控制和优化，其目的在于找到更接近于预期结果的网络拓扑结构，提高网络覆盖率，减少工作节点数量，节省网络能量，或者延长网络生命周期。本文的主要研究内容和成果如下：1.毯状网络中基于工作节点选择的拓扑控制。研究了高冗余度网络的拓扑控制，主要是分析如何选择工作状态节点以降低网络冗余，减少工作节点数量，从而延长网络生命周期。①提出了CDBANS中心式算法。该算法以覆盖度为参数，采用二部图的原理选择工作节点，最终延长了网络生命周期；②提出了CBANS分布式算法。该算法通过减小相邻两个工作节点的重叠区域面积的方法，减少了工作节点数量，提高了1-覆盖占比，最终有利于延长网络生命周期。仿真结果表明：①与SSR算法相比，CDBANS算法分别将网络生命周期和1-覆盖占比提高了20%和5%，而与LWS算法相比，CDBANS算法保持了基本一致的网络覆盖率，但是将网络生命周期延长了至少60%；②与DMS算法相比，CBANS算法分别将网络生命周期和1-覆盖占比提高了60%和20%，而与GTC算法相比，CBANS算法保持了基本一致的网络覆盖率和网络生命周期，但是将1-覆盖占比提高了约13%。2.毯状网络中基于传感器有限移动的拓扑控制。研究了无线传感器网络转换为voronoi图的过程和voronoi图的特征，主要分析了如何确定节点的移动策略，目的是减小网络覆盖盲区。提出了VBMC算法。该算法以voronoi多边形判断节点自身是否在覆盖盲区边缘，然后依据该多边形的顶点确定移动方向，实现了以较低能耗提高网络覆盖率的目标。仿真结果表明，与MiniMax算法相比，VBMC算法将能耗减少了至少80%，而与基于网格的算法相比，VBMC算法保持了基本一致的能耗，但是将网络覆盖率提高了约13%。3.带状网络中基于工作节点选择的拓扑控制。研究了衡量带状覆盖性能的关键指标，包括带状覆盖度和覆盖盲区，目的是判断随机布局的带状网络是否满足应用需求，以及简化带状网络拓扑控制的算法。提出了SMCS算法和LTNWB算法，两种算法分别是依据图论中最小割集的概念和DFS算法而提出的，其中SMCS算法确定了带状网络的覆盖度和覆盖盲区，而LTNWB算法确定了带状网络的覆盖度和带状覆盖。本文不仅从理论上证明了两种算法的收敛性和有效性，而且在仿真实验中得到证实。4.带状网络中基于传感器有限移动的拓扑控制。研究了如何局部确定带状网络度，使每个节点仅仅依据局部信息即可确定移动策略，从而提高带状覆盖度。对MobiBar算法进行改进，形成了VMB_MobiBar算法。改进之处主要体现在限制节点的移动次数从而减少节点的能耗。仿真结果表明，与MobiBar算法相比，VMB_MobiBar算法能够保持一致的带状覆盖度，但是将能耗减少了10%～50%（与布局的节点数量有关）。综上所述，在随机布局的无线传感器网络应用中，本文主要针对毯状和带状网络的拓扑控制和优化进行了研究，采用的方法主要是基于工作节点选择和传感器有限移动，目标是提高网络覆盖性能。更多还原

【Abstract】 Wireless Sensor Network (Wireless Sensor Network) is a kind of application-oriented Network architecture withinwhich a Sensor node is distributed in the target area to monitor a particular object. In the applications of area coverage,wireless sensor network is composed of blanket coverage network and barrier coverage network. Blanket coveragenetwork is that any point over the target area is covered by at least a or k nodes, also known as full coverage ork-coverage network, and barrier coverage refers to that any path passing through the target area is intersected with theregion covered by at least one or k nodes, which is also known as k-barrier coverage.Node deployment, which is divided into non-random layout and random layout, is a very important stage for theformation of wireless sensor network topology structure. In the primeval forest, the deployment of blanket sensornetworks makes early warning of fire, or in the border, the deployment of barrier sensor network makes early warning ofstowaways, they usually choose to drip sensors randomly by plane or throw rockets. Sensor nodes of random drippinghave positional uncertainty, coupled with the redundant features of WSN, and it is necessary to periodically select a partof sensors in working status through the topology control strategy, or to relocate some sensor nodes in order to constructsuitable topology structure.The following problems concerning the present wireless sensor network topology control:1. Maximum coverage. The coverage is the ratio of the region area covered by wireless sensor network to the wholearea. The part of area of the random deployment is unavoidably covered by a sensor node, and therefore, these sensornodes need to be in the active state, or it will reduce network coverage. There is no such mechanism in the currentresearch results to make these sensors in the active state.2. The maximization of1-coverage ratio.1-coverage ratis is the ratio of the region area covered by only one sensor tothe whole area. Except to set the coverage as1, the objectives of the optimization of ideal blanket network topology alsoinclude the maximization of the proportion of1-coverage in order to reduce the number of the active sensors and toprolong the network lifetime. There is no research to the latter as topology control and the optimization target, so therewill effect the network lifetime.3. To minimize the energy consumption for topology control by mobile sensor. Existing research is mainly aimed atminimizing the sum of the node energy consumption as the optimization goal, but ignored the minimization of thevariance of energy consumed by every sensor, leading to the unbalanced distribution of node residual energy, andultimately, it will reduce the network lifetime.4. Full barrier coverage network. It is a full barrier network for the intrusion detection with the probability being1.This network ensures the effect of monitoring target, and improves the reliability of network. For topology control ofnode selection, this condition is ignored and results in the non-full barrier coverage.For the above problem, this project mainly makes research of wireless sensor network topology control, and its aim isto find a network topology structure more close to the expected results to improve the network coverage, to save network energy and to prolong thenetwork lifetime. In this paper, the main research contents and results are as follows:1. Topology control of blanket network based on node selection. It studies high redundancy network topology control,mainly analyzes how to choose the active sensors, to reduce the number of active sensors, and to prolong the networklifetime.(1) CDBANS center algorithm is proposed. It puts coverage degree as parameter, user the two-part graph forselecting the active sensors, and to extend the network lifetime up to the hilt.(2) CBANS distributed algorithm isproposed. The algorithm put the minimization of the overlap area of the adjacent two working node as the optimizationgoal, reduce the number of active sensors, and improve the1-coverage ratio. The simulation results indicates:(1)compared with SSR algorithm, CDBANS algorithm improves20%and5%respectively for network lifetime and1-coveage ratio, and compared with LWS algorithm, CDBANS algorithm have the same network lifetime and thecoveage, but improve13%for1-coveage ratio.2. Topology control of limited-mobile-sensor-based blanket network. It studied the the process of wireless sensornetwork’s converting into a voronoi diagram and the characteristics of the voronoi diagram, mainly analyzing how todetermine the node mobile strategy.The purpose is to improve the coverage. VBMC algorithm is proposed. It aims atvoronoi polygon for the algorithm to determine whether a node itself on the edge of the blind area, and then to determinethe direction of movement according to the polygon vertices, thus achieving the goal of maximizing the networkcoverage with the minimum energy consumption. Compared with MiniMax algorithm, VBMC algorithm reduce80%forenergy consumption, and compared with grid-based algorithm, VBMC algorithm improve13%for network coverage.3. Topology control of barrier coverage which is based on active sensor selection. It studied the key indicators ofmeasuring the performance of barrier coverage, including barrier coverage degree and blind area, with the purpose ofdetermining whether layout ribbon network meet the application requirements to simplify the ribbon network topologycontrol algorithm. SMCS algorithm and LTNWB algorithm are proposed, and they are based on the concept of minimumcut set in graph theory and DFS algorithm, independently. SMCS algorithm determines the barrier coverage and blindarea, and LTNWB algorithm determines barrier coverage degree and belt cover. This article not only theoretically provedthat the convergence and effectiveness of the two kinds of algorithm, and confirmed in the simulation experiment.4. Topology control of barrier coverage based on limited mobile sensor. It studies how to locally determine the barriercoverage degree, to make decision of movement strategy only depmending on the local information, and to improve thebarrier coverage degree. It improved MobiBar algorithm to be VMB_MobiBar algorithm, which can achieve the samebarrier coverage as the MobiBar algorithm, and consume less energy in the process of topology control. Simulationresults indicate that, compared with MobiBar algorithm, the algorithm of VMB_MobiBar has the same barrier coveragedegree, but reduce10%~50%for energy consumption.To sum up, the author studied topology control and optimization of blanket and barrier network in the applications ofwireless sensor network of the random layout. The method adopted is mainly based on the working node selection andlimited mobile sensors. The goal is to guarantee the optimal network performance, including higher network coverageand1-coverage ratio to reduce and balance energy consumption of each node or to extend the network life cycle.更多还原