【作者】 张晋；

【导师】 刘大昕；

【作者基本信息】 哈尔滨工程大学 ， 计算机应用技术， 2010， 博士

【摘要】 无线传感器网络技术作为多学科交叉的新型技术,由于其广阔的应用前景,得到了广泛的关注。要实现对分布区域内的各种环境或对象的感知与监测,首要的问题就是必须对监控区域进行有效的覆盖控制。国内外研究人员从覆盖能力、网络连通性、能量有效性与算法精确性等方面对无线传感器网络覆盖控制问题进行了研究,并取得了一些成果。但由于无线传感器网络本身的特殊性,再加上被监测环境的变化复杂,导致目前的覆盖算法在实际应用中具有很大的局限性。本文重点研究具有较大实用性的覆盖控制算法,解决能量受限、通信能力有限及复杂环境条件下的监控区域有效覆盖问题。在对现有节能覆盖方式分析的基础上,将多因素优化节能与多重覆盖节能方式相结合,提出了一种能量有效的多重物理覆盖算法,在保障覆盖与连通性的前提下,以能量、覆盖度为衡量指标,采用调度机制实现节点轮换活跃与休眠,有效地提高网络生存时间。仿真实验结果表明,与目前典型算法相比,提出的算法在网络生存时间、能量消耗与消亡节点数上具有显著的优势。分析了不规则区域物理覆盖的连通性问题,对关键区域覆盖控制进行了数学描述,提出了关键区域覆盖启发式优化算法。通过分配不同的权值创建感知区域图和终端集合,创建加权节点Steiner树,形成最少数量格点集并构建覆盖关键区域的传感器放置方法。理论分析证明提出的算法能以优化的传感器节点数量,实现关键区域完全覆盖功能。通过不同场景下、不同参数仿真结果表明,与现有的算法相比,在关键区域格点数、感知范围、发送范围和关键区域格点选择分布概率变化时,提出的算法具有更少的传感器布置数量。针对具有不同传输半径的不规则WSN的物理覆盖与广播数据信息转发,提出了最小单位圆集信息覆盖算法。该算法以覆盖范围的轮廓集为出发点,以时间复杂度O ( nlogn)有效的计算出覆盖范围的轮廓集,并以节点最少数量的邻居节点子集实现所有邻居节点的覆盖。通过理论分析证明该算法找到的最小单位圆覆盖集与其轮廓集是相等的。大量的仿真实验及与现有的覆盖算法的对比,表明了提出的算法在保证物理覆盖的同时,以最少数量的节点实现了全局信息覆盖。最后,给出了信息覆盖的数学描述,并从理论上证明覆盖敏感的信息覆盖问题为NP完全问题。针对该问题,提出了覆盖敏感的分布式信息覆盖算法。该算法在每个节点中运行,节点将通过本地选择最少数量的节点实现信息覆盖,该算法同时具有节能的特点。通过与现有的数据查询处理算法的对比,实验结果表明了提出的算法在充分考虑物理覆盖连通性前提下,不仅实现了信息覆盖,而且明显地降低了节点的能耗与数据查询能耗、提高了网络的生存时间。更多还原

【Abstract】 As a new multi-knowledge technology, wireless sensor network has gained comprehensive attention for its extensive application prospect. In order to monitor and sense the environment and objects efficiently, covering the monitoring and sensing area fully is the first important problem. Many researchers have explored the coverage capacity, connectivity, power efficiency, accuracy of coverage problems of WSN. However, the effectiveness of the existing schemes degrades greatly in actual environment for the characters of WSN and the changeful environment. With the consideration of requirements of actual environment, this dissertation focuses on the coverage control problem in WSN, and designs more efficient coverage control algorithms from physical coverage and information coverage aspects.Based on analyzing current power-saving coverage scheme, and combining the multi-factor optimized power saving scheme and multi-level coverage power saving scheme, an efficient power multi-level coverage algorithm is presented. By measuring energy and coverage degree, it puts redundant sensor nodes to sleep mode to save energy while maintain the sensing field sufficient coverage degree with precondition of coverage and connective of WSN. Detailed simulation results and compared to existing schemes indicate that the proposed EPCA algorithm not only guarantees the network coverage degree, but also prolongs the network lifetime.Then the connectivity problem of physical irregular area coverage is analyzed. It gives the mathematical description of critical area coverage and proposes the critical area coverage heuristic optimization algorithm. By assigning different weight for critical grid points and common grid points to create the graph of sensing filed and terminal set, it establishes node-weighted Steiner tree to form critical areas coverage grids set with minimal number. Theoretic analysis proves that the proposed algorithms can fully cover all critical grids and form a WSN. Detailed simulation results and comparison with an existing algorithm indicate that the proposed algorithms obviously deploy fewer sensors with varying the number of critical grid points, sensing range, transmission range and the selection distribution probability of critical grid points.In order to deal with physical coverage and broadcasting data information forwarding problem in WSN with different transmission radius, a minimum unit disks set information coverage algorithm is proposed, which can calculate skyline set efficiently with the time complexity O ( nlogn). The proposed algorithm covers each node with minimum unit disk cover set, and the minimum unit disk cover set of a node is equivalent to its skyline set. Detailed simulation results and comparisons with existing algorithms indicate that the proposed algorithm not only covers all nodes with minimum nodes, but also prolongs the network lifetime.Finally, the description of information coverage is presented, and we prove that the information covering problem is a NP-complete problem. This paper proposes a coverage-aware data query algorithm, which maintains not only the physical coverage of WSN, but also logical data information coverage. It is executed by each sensor node to locally select the minimum number of k-neighboring nodes in order to achieve information coverage. Detailed experimental study and comparisons with existing algorithms indicate that the energy consumption of EHDQ is less, and the performance of EHDQ is much better in terms of query cost and network lifetime.更多还原