【作者】 张红武；

【导师】 王宏远；

【作者基本信息】 华中科技大学 ， 通信与信息系统， 2009， 博士

【摘要】 目标覆盖是无线传感器网络的一个基本问题。它主要研究传感器感知物理目标的监测程度,如何调度各传感器节点来完成覆盖任务,延长网络覆盖的生命期。为了最大化目标覆盖的生命期,本文对无线传感器网络的目标覆盖问题作了如下研究：1.在集合分割算法的基础上,提出一种线性规划算法来解决目标覆盖问题。首先,本文将传感器网络的工作时间分割成一个个小的时隙。在每个时隙中,选定一个目标覆盖集执行目标覆盖任务。一个传感器节点可以属于多个不同的目标覆盖集。这种传感器节点分配给多个目标覆盖集的方法,突破了整数规划的思想,引入了线性规划的算法思路。接着,深入地分析了目标覆盖的网络模型,设计了传感器节点初始能量不完全相等的网络模型,并提出一种线性规划的表达式来描述目标覆盖问题。最后,设计了一种线性规划算法来解决目标覆盖问题。线性规划方法来描述和分析目标覆盖问题,并证明目标覆盖问题是一个NP完全问题,为目标覆盖问题建立了理论基础。2.为了降低算法的复杂度,提出一种集中式的启发式贪心最优目标覆盖算法来解决目标覆盖问题。在实际应用中,在传感器节点的处理能力、通信能力、电源能量都严重受限的条件下,要求传感器节点执行算法的复杂计算比较小。为了降低算法的复杂度,在分析无线传感器网络的目标覆盖能量模型的基础上,找出目标覆盖生命期的关键约束,引入关键目标的概念,在关键目标优先和最大化关键目标生命期的基础上,提出一种启发式贪心最优覆盖算法。从目标的覆盖能量和覆盖生命期的角度,来设计启发式贪心策略,克服了传统的剩余能量优先和能量效率优先的贪心策略的缺陷,取得很好的算法效果。3.针对无线传感器网络的分布式自组织特点,设计了一种目标覆盖问题的分布式最优覆盖算法。用线性规划算法和集中式启发式贪心算法来求目标覆盖问题,都属于集中式算法。在集中式算法中,汇节点或基站要取得全网的信息,成为全网的瓶颈。同时,全网管理信息的集中和分发要增加网络流量,增大通信能耗。为了克服集中式算法的缺陷,针对无线传感器网络的分布式和自组织特点,设计一种分布式最优覆盖算法来解决点目标覆盖问题。首先,提出本地h-跳的目标覆盖问题,并证明了1-跳分布式算法的可行性。接着,在分析目标覆盖能量模型的基础上,引入了关键目标的概念,设计了基于目标覆盖能量的能量效用函数,在关键目标优先和能效优先的原则的基础上设置节点等待时间,并建立了节点等待时间自适应调整的机制。最后,设计了一种分布式最优覆盖算法。4.针对覆盖半径可调的无线传感器网络模型,进一步提出用线性规划算法来解决覆盖半径可调的目标覆盖问题。调整覆盖半径,是减小覆盖能耗的重要技术之一。在覆盖半径可调的无线传感器网络中,传感器节点通过调整覆盖半径,减少重叠覆盖率,减少覆盖能耗,延长目标覆盖的生命期。同时,通过调整传感器节点的覆盖半径,也可以实现各目标之间的能耗均衡,从总体上延长网络覆盖的生命期。首先,在分析覆盖半径可调的目标覆盖问题,用线性规划表达式描述覆盖半径可调的目标覆盖问题,并提出一种高效的启发法,最后设计模仿实验来证明算法的有效性。5.设计一种基于能量均衡和覆盖半径自适应调整的目标覆盖的分布式启发算法来解决半径可调的目标覆盖问题。覆盖半径可调的目标覆盖问题是一个NP完全问题。为了降低算法的复杂度,考虑到无线传感器网络的动态拓扑和分布式自组织的特点,本文采用分布式算法求局部h-跳的局部网络的目标覆盖的生命期,来逼近整个网络的目标覆盖生命期的全局最优解。为此,在能量平衡和自适应调整覆盖半径的基础上,我们提出一种基于能量均衡和覆盖半径自适应调整的目标覆盖分布式启发算法。更多还原

【Abstract】 Target coverage is a basic problem in wireless sensor networks. Its researches includes the monitoring quality of target coverage, how to schedule sensor nodes to cover targets in order to extend network lifetime. To maximize the network lifetime of target coverage, this paper has done the following researches on the target coverage problem in wireless sensor networks.1. Improving on the algorithm of disjoint set covers, this paper proposes a linear programming algorithm to solve the target coverage problem.Firstly, we divide operate time into time slices, in which a time slice is called to be a timeslot. In every timeslot, only a set cover is chosen to monitor the targets. A sensor node may be dispatched into several cover sets, which breaks the integer programming ideas and introduces the linear programming idea. Then, we design the network model in which the initial energies of sensor nodes are not completely unequal, deeply analyze the network model of target coverage, and propose a linear programming expression to describe the target coverage problem. Finally, proposed a linear programming algorithm to solve the target coverage problem. Furthermore, we prove the target coverage problem to be a NP-complete. All of these establish the theoretical foundation of the target coverage problem.2. To reduce the computational complexity, we proposed a centralized heuristic greedy optimum target coverage algorithm to solve the target coverage problem.The target coverage problem is a NP-completely problem. In practice, under the condition that sensor nodes’processing power, communicating capacity, energy supply is serious restricted, it is difficult for sink node to execute the linear programming algorithm. In order to reduce the computational complexity, we analyze the energy model of target coverage, present the concept of the key target and the prior coverage of key target. Moreover, we choose sensor with most energy utility as active sensor. In the end, we present a centralized heuristic greedy optimum target coverage algorithm. Measurement results show that the new algorithm could increase network lifetime and achieve more adaptability and stability. 3. Considering the distributed and self-organizing features of wireless, we proposed a distributed optimum algorithm for target coverage problem.Above the linear programming algorithm and the heuristic greedy optimum target coverage algorithm are centralized executed, in which sink node or base station must get all the information of the whole network and becomes the bottleneck of the whole network. Meanwhile, it would increase the network flow and increase the energy consumption for the information of the network management to be concentrated and dispatched. In order to overcome these shortcomings of the centralized algorithms, considering the distributed and self-organizing feature of wireless sensor networks, we design a distributed optimum algorithm for target coverage.Firstly, we put forward the local h-hop target coverage problem, and prove the feasibility of the 1-hop distributed algorithm. Then, on the basis of analyzing the energy model of the target coverage, we introduce the concept of the key target, and design the energy utility function of sensor node, and establish an adaptive adjustment mechanism of the waiting time.4. In view of the network model of wireless sensor networks with adjustable sensing ranges, we further proposed a linear programming algorithm to solve the target coverage problem with adjustable sensing ranges.Adjusting sensing range is an important approach to reduce energy consumption. In wireless sensor networks with adjustable sensing ranges, by adjusting its sensing range, sensor nodes reduce overlapping coverage, reduce energy consumption, and extend the network lifetime of the target coverage. At the same time, by adjusting its sensing ranges, energy consumption can be balanced between the targets, consequently to prolong the network lifetime of target coverage.Firstly, we analyze the target coverage problem with adjustable sensing ranges. Then we use linear programming expressions to describe the target coverage problem with adjustable sensing ranges, and propose an energy-efficient heuristic algorithm. Finally, we design simulation experiment experiments to evaluate the performance of our algorithm.5. Propose an Energy-Balance Heuristic Distributed Algorithm for Target Coverage with Adjustable Sensing Ranges. The target coverage problem with adjustable sensing ranges is NP-complete. In order to reduce the computational complexity, taking into account the dynamic topology, distributed, and self-organizing characteristics, we adopt a distributed algorithm to seek the network lifetime of target coverage in the local h-hop network, consequently the whole optimum solution is approached by local optimum solution. Finally, we propose an Energy-Balance Heuristic Distributed Algorithm for Target Coverage with Adjustable Sensing Ranges based on the energy balance and adaptively adjusting sensing ranges.更多还原