The Deterministic Sensor Deployment Problem for Barrier Coverage in WSNs With Irregular Shape Areas

Abstract

Most extant studies of barrier coverage in wireless sensor networks (WSNs) have assumed that the region of interest (RoI) is in a rectangular shape and sensors are randomly deployed. They construct a barriermainly by selecting appropriate sensors from randomly deployed sensors. Although these barrier construction algorithms for randomly deployed sensors in rectangular shape areas can also work for irregular shape areas, they will inevitably use a large number of sensors. In real-world scenarios, most RoIs are in an irregular shape. For example, the geographical contour of a country is irregular. To reduce the number of deployed sensors, we propose a new deterministic sensor deployment algorithm for the barrier coverage problem in WSNs with irregular shape areas. The irregular shape area was limited within an area of a L x W virtual rectangle, where L and W are constants. We focus on the problem of minimizing the number of sensorsrequiredto forma barrier. Comparedto randomdeployment of sensors, using deterministicdeployment to deploy sensors can reduce the hardware cost of sensors drastically. The proposed algorithm is based on the concept of convex hull and turning point selection. To the best of our knowledge, this paper is the first work that utilizes the inflection points of the entry side of the RoI to address the problem. Compared to other algorithms, the experimental results confirm that the proposed algorithm can effectively reduce the number of sensors required to construct a barrier in WSNs with irregular shape areas.