Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2017 Oct 10;17(10):2304.
doi: 10.3390/s17102304.

On Efficient Deployment of Wireless Sensors for Coverage and Connectivity in Constrained 3D Space

Chase Q Wu  1 , Li Wang  2
Affiliations

On Efficient Deployment of Wireless Sensors for Coverage and Connectivity in Constrained 3D Space

Chase Q Wu et al. Sensors (Basel). .

Abstract

Sensor networks have been used in a rapidly increasing number of applications in many fields. This work generalizes a sensor deployment problem to place a minimum set of wireless sensors at candidate locations in constrained 3D space to k-cover a given set of target objects. By exhausting the combinations of discreteness/continuousness constraints on either sensor locations or target objects, we formulate four classes of sensor deployment problems in 3D space: deploy sensors at Discrete/Continuous Locations (D/CL) to cover Discrete/Continuous Targets (D/CT). We begin with the design of an approximate algorithm for DLDT and then reduce DLCT, CLDT, and CLCT to DLDT by discretizing continuous sensor locations or target objects into a set of divisions without sacrificing sensing precision. Furthermore, we consider a connected version of each problem where the deployed sensors must form a connected network, and design an approximation algorithm to minimize the number of deployed sensors with connectivity guarantee. For performance comparison, we design and implement an optimal solution and a genetic algorithm (GA)-based approach. Extensive simulation results show that the proposed deployment algorithms consistently outperform the GA-based heuristic and achieve a close-to-optimal performance in small-scale problem instances and a significantly superior overall performance than the theoretical upper bound.

Keywords: approximation algorithm; k-coverage; network connectivity; sensor deployment.

PubMed Disclaimer

Conflict of interest statement

The authors declare no conflict of interest.

Figures

Figure 1
Figure 1
Illustration of two intersection cases between a new circle and the existing circles: (a) the new circle c′ intersects only one arc of an existing circle; (b) the new circle c′ intersects two arcs of an existing circle.
Figure 2
Figure 2
An example of Algorithm 2.
Figure 3
Figure 3
Intersected circles and divisions.
Figure 4
Figure 4
A tight example of Theorem 6.
Figure 5
Figure 5
Comparison of the average performance with the standard deviation between GreedyDLDT (Greedy), Genetic Algorithm (GA), and Optimal Algorithm (OPT) for DLDT in response to a varying number of target points.
Figure 6
Figure 6
Measured average approximation ratio of GreedyDLDT for DLDT in response to a varying number of target points.
Figure 7
Figure 7
Comparison of the average performance with the standard deviation between GreedyDLDT (Greedy), Genetic Algorithm (GA), and Optimal Algorithm (OPT) for DLDT in response to varying k values.
Figure 8
Figure 8
Measured average approximation ratio of GreedyDLDT for DLDT in response to varying k values.
Figure 9
Figure 9
Performance comparison of GreedyDLDT (Greedy), Genetic Algorithm (GA), and Optimal Algorithm (OPT) for a museum exhibition hall with sensor mounting constraints in response to a varying number of exhibition items.
Figure 10
Figure 10
Comparison of the average performance with the standard deviation between the 2-stage Greedy Algorithm, Genetic Algorithm (GA), and the Optimal Algorithm (OPT) for C-DLDT in response to a varying number of target points.
Figure 11
Figure 11
Comparison of the average performance with the standard deviation between the 2-stage Greedy Algorithm, Genetic Algorithm (GA), and the Optimal Algorithm (OPT) for C-DLDT in response to varying k values.
See this image and copyright information in PMC

References

    1. Chakrabarty K., Iyengar S., Qi H., Cho E. Grid coverage for surveillance and target location in DSNs. IEEE Trans. Comput. 2002;51:1448–1453. doi: 10.1109/TC.2002.1146711. - DOI
    1. Vales-Alonso J., Parrado-García F., López-Matencio P., Alcaraz J., González-Castañob F.J. On the optimal random deployment of wireless sensor networks in non-homogeneous scenarios. Ad Hoc Netw. 2013;11:846–860. doi: 10.1016/j.adhoc.2012.10.001. - DOI
    1. Xia M., Dong Y., Lu D., Xue P., Liu G. A Wireless Sensor System for Long-Term Microclimate Monitoring in Wildland Cultural Heritage Sites; Proceedings of the IEEE International Symposium on Parallel and Distributed Processing with Applications; Sydney, NSW, Australia. 10–12 December 2008; pp. 207–214.
    1. Jooa J., Yimb J., Leec C.K. Protecting cultural heritage tourism sites with the ubiquitous sensor network. J. Sustain. Tour. 2009;17:397–406. doi: 10.1080/09669580802582498. - DOI
    1. Lin Y., Wu Q. Approximate Algorithms for Sensor Deployment with k-coverage in Constrained 3D Space; Proceedings of the 16th International Conference on Parallel and Distributed Systems; Shanghai, China. 8–10 December 2010.

LinkOut - more resources