An Efficient Algorithm for Constructing Underwater Sensor Barrier

Most existing works on barrier coverage assume that sensors are deployed in a two-dimensional (2D) long thin belt region, where a barrier is a chain of sensors from one end of the region to the other end with overlapping sensing zones of adjacent sensors. However, 2D sensor barrier construction mechanism cannot be directly applied to three-dimensional (3D) sensor barrier construction problem, such as underwater sensor barrier construction, where sensors are finally distributed over a 3D space. In this paper, we investigate how to efficiently construct an underwater sensor barrier with minimum mobile sensors while reducing energy consumption. We first determine the minimum number of sensors needed for an underwater sensor barrier construction. Furthermore, we analyse the relationship between the initial locations of sensors and the optimal location of the underwater sensor barrier, based on which we derive the optimal final locations for all sensors. Finally, we propose an efficient algorithm to move sensors from their initial locations to final locations. Extensive simulations show that, compared with HungarianK approach, the proposed algorithm costs shorter running time and similar maximum movement distance of any one sensor.