Research On Barrier Coverage In Wireless Sensor Networks

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.