【作者】 班冬松；

【导师】 窦文华；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2011， 博士

【摘要】 无线传感器网络是由大量低功耗、低成本、集信息获取、处理和传输于一体的微型传感器节点通过自组织方式形成的网络,在军事国防、工农业控制、环境监控、生物医疗、抢险救灾等领域有着非常广泛的应用前景,近年受到广泛关注。覆盖控制是无线传感器网络的基本研究问题。通过覆盖控制技术,能够有效地利用无线传感器网络的有限资源,实现改善感知服务质量或延长网络生存周期等目的。栅栏覆盖是无线传感器网络覆盖控制的研究热点之一。栅栏覆盖考虑移动目标沿任意路径穿越无线传感器网络的部署区域时,如何保证移动目标被网络检测的问题,在边境监测、阵地布防、工业安保等方面具有广泛的应用需求。栅栏覆盖与传统的区域覆盖相比,在部署区域、监控目标、监控方式等方面显著不同,传统区域覆盖领域的研究工作不能直接应用于栅栏覆盖,栅栏覆盖目前仍是开放的研究领域,因此对无线传感器网络栅栏覆盖关键技术进行研究具有积极的理论意义和应用价值。本文在弱栅栏覆盖节点调度策略、支持多节点信息融合的栅栏信息覆盖、全移动传感器网络k-栅栏覆盖、混合传感器网络k-栅栏覆盖等方面展开研究,主要研究工作包括:(1)针对无线传感器网络节点能量有限、能量补充困难的特点,本文研究了无线传感器网络弱栅栏覆盖最大化网络生存周期的节点调度问题。首先引入条格划分思想,提出了面向弱k-栅栏覆盖应用的栅栏覆盖调度问题BCSP,证明了该问题是NP-Hard的。然后提出了一种集中式的启发式节点调度算法HBCS,该算法优先选择能够栅栏覆盖最多条格的节点加入栅栏覆盖集。最后提出了一种完全分布式的最大化生存周期调度算法DBCS,该算法中各节点仅需通过获取邻居节点所覆盖条格的信息即可确定自身工作状态,计算简单、通信开销小,适合于大规模无线传感器网络应用。仿真实验表明两种调度算法均能够有效地调度冗余节点实现弱k-栅栏覆盖,节省网络能量,显著延长网络生存周期。(2)相邻多个物理传感器节点通过感知信息的融合,组成虚拟节点,将能够弥补节点间的物理覆盖空隙,增加栅栏投影长度,提高栅栏覆盖性能。本文研究了如何进行虚拟节点组合以最大化栅栏投影长度的栅栏信息覆盖虚拟节点组合问题。主要工作包括:1)针对虚拟节点协作度的情况,推导出了虚拟节点信息覆盖区域的栅栏投影长度的近似下界,提出了一种对协作度k无限制的计算栅栏投影近似下界的通用方法。2)基于合作博弈理论,建立了虚拟节点组合博弈模型,提出了一种分布式的虚拟节点组合算法DVSF,证明了DVSF算法的收敛性和最终网络结构的稳定性。3)仿真实验证明DVSF算法能够显著增加网络的栅栏投影长度之和,提高栅栏信息覆盖性能,DVSF能够与分布式的节点调度机制良好地结合,大幅增加网络生存时间。(3)针对所有节点都具有有限移动能力的全移动传感器网络,目前尚无解决能量高效的k-栅栏覆盖构建问题的研究工作。本文研究了随机部署的全移动传感器网络能量高效地构建k-栅栏覆盖的问题,主要工作包括:1)提出了1-栅栏覆盖最小移动距离和问题(1-BCMS问题)。基于网格划分模型,将1-BCMS问题近似为1-网格栅栏最小移动距离和问题(1-GBMS问题),给出了1-GBMS问题的整数线性规划描述,证明了1-GBMS问题是NP-hard的。2)提出了一种能量高效的1-栅栏覆盖构建算法CBGB。仿真实验表明CBGB算法的求解结果与最优解接近,有效减少了节点移动距离。与CBarrier算法相比,CBGB算法性能更优。3)提出了基于分治策略的k-栅栏覆盖构建算法。与全局算法相比,该算法大幅减小了通信和计算开销。仿真实验表明该算法能够有效地形成k-栅栏覆盖,节点平均移动距离不随网络规模的扩大而增加,具有良好的可扩展性,适用于大规模无线传感器网络(4)针对由大量静态节点和少量移动传感器节点组成的混合传感器网络,本文研究了移动节点辅助下的k-栅栏覆盖构建问题。主要工作包括:1)提出了一种集中式的混合传感器网络k-栅栏覆盖构建算法BCHN。该算法首先利用最小费用流算法寻找最少数量的待修补空隙,然后对每个待修补空隙,选取具有最短移动距离的邻近移动节点进行修补。2)提出了一种分布式的L-局部k-栅栏覆盖构建算法DLBC。各静态节点首先计算自身局部2d长度范围内的待修补空隙集合,然后利用移动节点修补空隙,在自身局部2d长度范围内形成k-栅栏覆盖,整个网络即可形成L-局部k-栅栏覆盖。3)基于渗透理论,分析了移动节点的部署条件:如果监控区域宽度与长度满足条件,则当静态节点密度时,无须部署移动节点。如果,则必须部署移动节点,才能保证形成栅栏覆盖。4)实验结果表明BCHN算法在平均移动距离、平均使用的移动节点数量等方面均优于MB算法;DLBC算法在较大d值的情况下,能够通过形成L-局部k-栅栏覆盖,间接保证全局k-栅栏覆盖的形成。综上,本文针对栅栏覆盖如何与节点调度、信息融合、移动传感器等技术紧密结合提出了相应的解决方案,充分发挥了栅栏覆盖的优势,有效利用了无线传感器的有限资源,达到节省无线传感器节点数量、延长无线传感器网络生存周期的目的,对进一步推动无线传感器网络的研究和实用化具有一定的理论意义和应用价值。更多还原

【Abstract】 Wireless sensor networks (WSNs),which consist of hundreds to thousands of low-power, low-cost tiny sensor nodes,can perform various tasks including information gathering, processing, and delivering. Recently, WSNs have attracted great attention due to their broad applications in military affairs, industry and agriculture automation, environment monitoring, biomedicine, and disaster succoring. Among the techniques in WSNs, coverage control acts as a fundamental method to improve the sensing quality or prolong the network lifetime, via exploring the limited resources in WSNs efficiently. This thesis focuses on a hot issue in the research areas of coverage control, namely, the barrier coverage. Barrier coverage, which guarantees that every movement that is crossing a barrier of sensors to be detected right away, is known as an appropriate coverage model for movement detection applications, such as border detection, bastion defense, and security of industry, etc. Comparing with the traditional area coverage model, barrier coverage is different in the shape of the deployment region, the goal of coverage, and the manner of surveillance. Note that the previous work on area coverage can not be transplanted to barrier coverage, and barrier coverage is still an open research topic. Thus, the research on barrier coverage in WSNs has its academic and practical value.This thesis studies several important problems in barrier coverage, which includes the scheduling strategy for weak barrier coverage, barrier information coverage that supports information fusion of more than two sensors, k-barrier coverage in all mobile sensor networks, and k-barrier coverage in hybrid sensor networks. The main contributions are summarized as follows:(1) Since the energy of wireless sensors is limited and it is very difficult to recharge, we propose a scheduling problem on how to prolong the network lifetime for weak barrier coverage. Firstly, the surveillance region is divided into small vertical segment, which is called‘slice’. Based on this discretization, we address a problem of how to schedule sensors to achieve weak barrier coverage, such that the network lifetime is maximized. We then formulate the problem as BCSP (Barrier Coverage Scheduling Problem). Secondly, a heuristic scheduling algorithm HBCS is proposed. The idea behind the proposed algorithm is to ensure the node which covers more slices has higher priority to join the set of barrier coverage in HBCS. Finally, a distributed scheduling algorithm DBCS is presented, in which each node can decide to be active or sleep only by its neighbors’information. DBCS is applicable for large scale wireless sensor network. Extensive simulations demonstrate that HBCS and DBCS can both prolong the network lifetime significantly while maintain the quality of weak barrier coverage. (2) Adjacent physical sensors can form a virtual sensor based on the technique of sensing information fusion, thus the sensing gap between neighboring physical nodes can be covered,. the projection length of sensor barriers can be increased and the performance of barrier coverage can be finally improved. This thesis addresses a virtual sensor formation problem to maximize the barrier projection length in barrier information coverage. The main works are as follows. (1) We first derive the lower bound of the barrier projection length of a virtual sensor when collaboration degree k>2. A generic calculation algorithm for is presented at last. (2) Based on coalitional game, we establish a virtual sensor formation game model and devise a distributed algorithm DVSF for virtual sensor formation in barrier information coverage. It is proved that the final network structure resulting from algorithm DVSF is stable. Simulations show that DVSF significantly increases the total barrier projection length and prolongs the network lifetime, on condition that the distributed scheduling algorithm DBCS described above is jointed exploited.(3) We observe that there are no works dealing with constructing k-barriers of sensors energy-efficiently for mobile sensor networks where all nodes have limited mobility. Thus, this thesis studies the problem of how to relocate mobile sensors to construct k sensor barriers with minimum energy consumption in randomly deployed sensor networks. The main works are as follows.(1) First, we formulate this problem as an 1-BCMS problem, then approximate it to the 1-GBMS problem based on grid division and give the Integer Linear Programming Model of 1-GBMS. (2) Second, we devise an approximation algorithm CBGB to construct one sensor barrier energy-efficiently. Simulations show that CBGB delivers a solution that is extremely close to the optimal solution, and performs better than that gained by the CBarrier algorithm. (3) Last, a divide-and-conquer algorithm for constructing k-barrier coverage is presented. Comparing with the global algorithm, the proposed algorithm reduces the communication overhead and computation cost significantly. Moreover, simulation results demonstrate that the Divide-and-Conquer algorithm can construct k-barrier coverage effectively and is applicable to large scale sensor networks.(4) This thesis also studies the problem of how to achieve k-barrier coverage assisted by mobile sensors in hybrid sensor networks, which consist of lots of static sensors and few mobile sensors. The main contributions are as follows. (1) We propose a centralized algorithm BCHN for constructing k sensor barriers in hybrid sensor networks. BCHN firstly finds the minimum gaps that is required to repair by the minimum cost flow algorithm, then for each gap, it selects the nearest node to repair it. (2) A distributed algorithm DLBC for achieving L-local k-barrier coverage is then presented. To achieve k-barrier coverage in 2d region, each static node first calculates the set of repairing gaps in its 2d region, what followed is by scheduling the movement of mobile sensors, thus in the whole networks , L-local k-barrier coverage.is achieved. (3) Based on percolation theory, we analyze the condition of deployment of mobile sensors: If the width of the surveillance region is , it is not necessary to deploy mobile sensors when static deployment density meets , while if , it is required to deploy mobile sensors so that k-barrier coverage is guaranteed. (4) Simulation results show that algorithm BCHN not only outperforms algorithm MB in average moving distance, but decreases the number of average mobile nodes required. If algorithm DLBC achieves L-local k-barrier coverage, the global k-barrier coverage can be achieved with large probability, provided that d is large enough.In summary, in order to improve the quality of barrier coverage and prolong the network lifetime of wireless sensor networks, this thesis proposes effective solutions for barrier coverage that incorperates the state-of-the-art technologies including the node scheduling, information fusion, and mobile sensors. Our works have their academic and practical value on promoting the advancement of the researches and applications in wireless sensor networks.更多还原