Research On The Problems Of Sweep Coverage In Wireless Sensor Networks

Wireless Sensor Networks(WSNs) have atrracted a lot of attention from the researchers in recent years. With the development of related techniques, sweep coverage has been widely applied in environment monitoring, smart home, security protection, and many other fields. In wireless sensor networks, the target should be in the sensing range of the sensors, which is covered by the sensors. The coverage problem is one of the most important issues in the study of wireless sensor networks. The coverage problem can be categorized into different classes in different applications. Full coverage requires the distribution of static sensors to monitor the targets all the time. Barrier coverage uses sensors to form a virtual barrier which can detect the object going through the barrier. Both of the former two coverage are static while sweep coverage is dynamic coverage. In some monitoring tasks, there is no need to monitor the targets all the time, and collecting data periodically is sufficient. Therefore, sweep coverage can utilize less mobile sensor nodes to cover more targets.Many researches have been studied in the field of sweep coverage. However, few researchers considered the procedure of data transmission to base station in sweep coverage. Since some data are time-sensitive, the time from the target to the base station is an important constraint. Additionally, wireless sensors can usually communicate in a distance. But most existing research ignored this and assumed that the target can only be covered when the sensor is at the location of the target.Based on the observation above, sweep coverage with return time constraints and distance-sensitive sweep coverage are studied in this paper. For the sweep coverage with return time constraints, the problem of determining the minimum number of mobile sensors required is studied and the NP-hardness is analyzed. Two heuristic algorithms, G-MSCR and Min D-Expand, are proposed to solve this problem. G-MSCR has a more strict constraint on the return time while requiring more mobile sensor nodes. For the distance-sensitive sweep coverage, the problem is described in detail and an algorithm named Circle Expand is also proposed. The algorithm divides the area into subareas and arranges mobile sensor nodes to cover these subareas, and thus ensures the sweep coverage of the points of interest.Finally, all the algorithms proposed in this paper are implemented. Some state-of-the-art algorithms are also implemented, which are compared with by the algorithms proposed in this paper. All the algorithms are simulated using the ONE simulator. In the problem of sweep coverage with return time constraints, existing sweep coverage algorithms cannot return to the base station without exceeding the return time constraints. The algorithm G-MSCR and Min D-Expand can return to the base station with the collected data under return time constraints. In the problem of distance-sensitive sweep coverage, since the Circle Expand algorithm takes the communication range into consideration, the simulation result shows that the Circle Expand algorithm outperforms existing sweep coverage algorithms in terms of the number of mobile sensor nodes required.