Editorial Notes
The authors have requested minor, non-substantive changes to the VoR and, in accordance with ACM policies, a Corrected Version of Record was published on October 06, 2023. For reference purposes, the VoR may still be accessed via the Supplemental Material section on this citation page.
Abstract
The problem of coverage is one of the most crucial issues among the problems in the lifecycle of the development of wireless sensor networks (WSNs). It is still open and stirs as much concern in the research community in this area. The problem of k-coverage in WSNs is even more challenging. In this article, we investigate the k-coverage problem in planar (or two-dimensional) WSNs, where each point in a field of interest (FoI) is covered by at least k sensors simultaneously, where k ≥ 1. Our contribution is four-fold: First, we determine the optimal planar convex tile that maximizes the usage of the sensors’ sensing range. Then, we propose a few sensor placement strategies based on the degree of coverage k using a hexagonal tiling-based approach. In addition, we compute the sensor density (i.e., number of sensors per unit area) for each of the above sensor placement strategies. Second, we propose a generalized one using irregular hexagons, which are denoted by IRH(r/n), where r stands for the radius of the sensors’ sensing range and n ≥ 2 is a natural number. Also, we derive the corresponding sensor density. Moreover, we prove that IRH(r/n) are capable of tiling the Euclidean plane using a mathematical induction proof. Third, we compute the relationship between the sensing range r of the sensors and their communication range R for the above sensor placement strategies. Fourth, we corroborate our analysis with simulation results.
Supplemental Material
Available for Download
Version of Record for "A Computational Geometry-based Approach for Planar -Coverage in Wireless Sensor Networks" by Habib M. Ammari, ACM Transactions on Sensor Networks, Volume 19, No. 2 (TOSN 19:2).
- 2016. A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks. Information Fusion 30, July 2016 (2016), 36--51. https://www.sciencedirect.com/science/article/abs/pii/S1566253515001037.Google ScholarDigital Library .
- 2004. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. In Proceedings of the ACM/IEEE International Conference on Information Processing in Sensor Networks, 424–432.Google ScholarDigital Library .
- 2019. Achieving sensing k-coverage using hexagonal tiling: Are we done yet? In Proceedings of the 16th International Conference on Mobile Ad-hoc and Smart Systems.Google ScholarCross Ref .
- 2014. Investigating the energy sink-hole problem in connected k-covered wireless sensor networks. IEEE Transactions on Computers 63, 11 (2014), 2729–2742.Google ScholarDigital Library .
- 2012. Centralized and clustered k-coverage protocols for wireless sensor networks. IEEE Transactions on Computers 61, 1 (2012), 118–133.Google ScholarDigital Library .
- 2006. Deploying wireless sensors to achieve both coverage and connectivity. In Proceedings of 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 131–142.Google ScholarDigital Library .
- 2020. Metaheuristics for maximization of obstacles constrained area coverage in heterogeneous wireless sensor networks. Applied Soft Computing 86, January 2020 (2020), 105939. https://www.sciencedirect.com/science/article/abs/pii/S1568494619307203.Google Scholar .
- 2006. The Art of Mathematics: Coffee Time in Memphis. Cambridge University Press.Google ScholarCross Ref .
- 2018. Connectivity and coverage based protocols for wireless sensor networks. Ad Hoc Networks 80, November 2018 (2018), 54--69. https://www.sciencedirect.com/science/article/abs/pii/S1570870518304360.Google ScholarCross Ref .
- 2000. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine 7, 5 (2000), 28–34.Google ScholarCross Ref .
- 2013. RaM - Recycle and Mathematics: The art of tiling for eco-design. In Proceedings of the Bridges 2013: Mathematics, Music, Art, Architecture, Culture. Enschede, the Netherlands, 629–634.Google Scholar .
- 2020. A Monte-Carlo Markov chain approach for coverage-area reliability of mobile wireless sensor networks with multistate nodes. Reliability Engineering and System Safety 193, January 2020 (2020), 106662. https://www.sciencedirect.com/science/article/pii/S0951832019300353.Google ScholarCross Ref .
- 2019. A coverage-aware and energy-efficient protocol for the distributed wireless sensor networks. Computer Communications 137, March 2019 (2019), 15--31. https://www.sciencedirect.com/science/article/pii/S0140366418303682.Google ScholarDigital Library .
- 2017. Energy-efficient coverage protocol based on stable and predictive scheduling in wireless sensor networks. Computer Networks 127, November 2017 (2017), 1--12. https://www.sciencedirect.com/science/article/pii/S1389128617302967.Google ScholarDigital Library .
- 2018. The Art Gallery Problem: An Overview and Extension to Chromatic Coloring and Mobile Guards. Technical Report. https://math.mit.edu/∼apost/courses/18.204_2018/Nicole_Chesnokov_paper.pdf.Google Scholar .
- 1988. Optimum watchman routes. Information Processing Letters 28, 1 (1988), 39–44.Google ScholarDigital Library .
- 2019. Data fusion based coverage optimization in heterogeneous sensor networks: A survey. Information Fusion 52, December 2019 (2019), 90--105. https://www.sciencedirect.com/science/article/abs/pii/S1566253518306535.Google ScholarDigital Library .
- 1989. Using occupancy grids for mobile robot perception and navigation. IEEE Computer 22, 6 (1989), 46–57.Google ScholarDigital Library .
- 2018. Optimizing K-coverage of mobile WSNs. Expert Systems with Applications 92, February 2018 (2018), 142--153. https://www.sciencedirect.com/science/article/pii/S0957417417306115.Google ScholarDigital Library .
- 2019. DACYCLEM: A decentralized algorithm for maximizing coverage and lifetime in a mobile wireless sensor network. Ad Hoc Networks 87, May 2019 (2019), 174--187. https://www.sciencedirect.com/science/article/pii/S1570870518309430.Google ScholarDigital Library .
- 2018. Novel efficient deployment schemes for sensor coverage in mobile wireless sensor networks. Information Fusion 41, May 2018 (2018), 25--36. https://www.sciencedirect.com/science/article/abs/pii/S1566253516302548.Google ScholarDigital Library .
- 1988. Tilings with convex polygons. In Proceedings of the Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman, 162–176.Google Scholar .
- 2017. Solving energy issues for sweep coverage in wireless sensor networks. Discrete Applied Mathematics 228, September 2017 (2017), 130--139. https://www.sciencedirect.com/science/article/pii/S0166218X16304346.Google ScholarDigital Library .
- 1980. Tilings with congruent tiles. Bulletin of the American Mathematical Society 3, 3 (1980), 951–973.Google ScholarCross Ref .
- 2016. Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks. Computers and Electrical Engineering 56, November 2016 (2016), 544--556. https://www.sciencedirect.com/science/article/pii/S0045790615003651.Google Scholar .
- 2006. Connected sensor cover: Self-organization of sensor networks for efficient query execution. IEEE/ACM Transactions on Networking 14, 1 (2006), 55–67.Google ScholarDigital Library .
- 2019. An efficient genetic algorithm for maximizing area coverage in wireless sensor networks. Information Sciences 488, July 2019 (2019), 58–75. https://www.sciencedirect.com/science/article/pii/S0020025519301823?via%3Dihub.Google ScholarDigital Library .
- 2002. An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications 1, 4 (2002), 660–670.Google ScholarDigital Library .
- 1902. Mathematische problem. Bull. Amer. Math. Soc. 8, July 1902 (1901--1902), 437--479. https://www.ams.org/journals/bull/1902-08-10/S0002-9904-1902-00923-3/S0002-9904-1902-00923-3.pdf.Google ScholarCross Ref . 1901--
- 1990. On the rectilinear art gallery problem. Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, Berlin, 717–728.Google ScholarCross Ref .
- 2022. Energy efficiency optimization for multiple chargers in wireless rechargeable sensor networks. Elsevier Theoretical Computer Science 922, June 2022 (2022), 193--205. https://www.sciencedirect.com/science/article/abs/pii/S0304397522002468.Google ScholarDigital Library .
- 2005. The coverage problem in a wireless sensor network. Springer Mobile Networks and Applications 10, 4 (2005), 519–528.Google ScholarDigital Library .
- 2007. Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network. ACM Transactions on Sensor Networks 3, 1 (2007).
DOI: Google ScholarDigital Library . - 2019. Sensor and sink placement, scheduling and routing algorithms for connected coverage of wireless sensor networks. Ad Hoc Networks 86, April 2019 (2019), 83--102. https://www.sciencedirect.com/science/article/pii/S1570870518308199.Google ScholarDigital Library .
- 1968. On paving the plane. The American Mathematical Monthly 75, 8 (1968), 839–844.Google Scholar .
- 1939. The number of circles covering a set. American Journal of Mathematics 1, 3 (1939), 665–671.Google ScholarCross Ref .
- 2015. Critical density for coverage and connectivity in two-dimensional fixed-orientation directional sensor networks using continuum percolation. Journal of Network and Computer Applications 57, November 2015 (2015), 169--181. https://www.sciencedirect.com/science/article/pii/S1084804515001964.Google ScholarDigital Library .
- 2004. On k-coverage in a mostly sleeping sensor network. In Proceedings of the 10th Annual International Conference on Mobile Computing and Networking. ACM New York, 144–158.Google ScholarDigital Library .
- 2017. Adaptive trap coverage in mobile sensor networks. Procedia Computer Science 110 (2017), 102–109. https://www.sciencedirect.com/science/article/pii/S1877050917313054.Google ScholarCross Ref .
- 2013. Best and worst-case coverage problems for arbitrary paths in wireless sensor networks. Ad Hoc Networks 11, 6 (2013), 1699–1714.Google ScholarCross Ref .
- 2019. Monitoring area coverage optimization algorithm based on nodes perceptual mathematical model in wireless sensor networks. Computer Communications (In press, Journal pre-proof Available online), (December 2019). 155, April 2020 (2020), 227--234. https://www.sciencedirect.com/science/article/pii/S0140366419315117.Google Scholar .
- 2016. Autonomous deployment of wireless sensor networks for optimal coverage with directional sensing model. Computer Networks 108, October 2016 (2016), 120--132. https://www.sciencedirect.com/science/article/pii/S1389128616302493.Google ScholarCross Ref .
- 2003. Coverage in wireless ad-hoc sensor networks. IEEE Transactions on Computers 52, 6 (2003), 753–763.Google ScholarDigital Library .
- 2006. Random coverage with guaranteed connectivity: Joint scheduling for wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems 17, 6 (2006), 562–575.Google ScholarDigital Library .
- 2020. Design of coverage algorithm for mobile sensor networks based on virtual molecular force. Computer Communications 150, January 2020 (2020), 269--277. https://www.sciencedirect.com/science/article/pii/S0140366419311879.Google Scholar .
- 2020. Maximizing network lifetime using coverage sets scheduling in wireless sensor networks. Ad Hoc Networks 98, March 2020 (2020). 102037. https://www.sciencedirect.com/science/article/pii/S1570870519304512.Google ScholarDigital Library .
- 2016. On balanced k-coverage in visual sensor networks. Journal of Network and Computer Applications 72, September 2016 (2016), 72--86. https://www.sciencedirect.com/science/article/pii/S1084804516301400.Google Scholar .
- 2005. Worst and best-case coverage in sensor networks. IEEE Transactions on Mobile Computing 4, 1 (2005), 84–92.Google ScholarDigital Library .
- 2001. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies, 1380–1387.Google Scholar .
- 1976. Hilbert's problem 18. In Proceedings of the Symposia of Pure Mathematics, 28, Bulletin of the American Mathematical Society.Google Scholar .
- 2017. Coverage in mobile wireless sensor networks (M-WSN): A survey. Computer Communications 110, September 2017 (2017), 133--150. https://www.sciencedirect.com/science/article/pii/S0140366417307235.Google ScholarDigital Library .
- 2017. A node failure and battery-aware coverage protocol for wireless sensor networks. Computers and Electrical Engineering 64, November 2017 (2017), 200–219. https://www.sciencedirect.com/science/article/pii/S0045790616311570.Google ScholarDigital Library .
- 2017. Game theory based node scheduling as a distributed solution for coverage control in wireless sensor networks. Engineering Applications of Artificial Intelligence 65, October 2017 (2017), 137–146. https://www.sciencedirect.com/science/article/abs/pii/S0952197617301689.Google ScholarDigital Library .
- 2019. Node placement for connected target coverage in wireless sensor networks with dynamic sinks. Pervasive and Mobile Computing 59, October 2019 (2019), 101070. https://www.sciencedirect.com/science/article/abs/pii/S1574119219301415.Google Scholar .
- 2008. Combinatorial Geometry and Its Algorithmic Applications, Chapter 8. American Mathematical Society.Google ScholarCross Ref .
- 1918. Uber die Zerlegung der Ebene in Polygone. Dissertation der Naturwiss. Fakultat. Universitat Frankfurt/Main, Borna.Google Scholar .
- 2017. Maximizing the wireless sensor networks lifetime through energy efficient connected coverage. Ad Hoc Networks 62, July 2017 (2017), 1--10. https://www.sciencedirect.com/science/article/pii/S1570870517300689.Google ScholarDigital Library .
- 2005. Unreliable sensor grids: Coverage, connectivity and diameter. Ad Hoc Networks 3, 6 (2005), 702–716.Google ScholarDigital Library .
- 2017. α-Overlapping area coverage for clustered directional sensor networks. Computer Communications 1091, September 2017 (2017), 89–103. https://www.sciencedirect.com/science/article/pii/S0140366417306072.Google ScholarCross Ref .
- 2018. Coverage control for mobile sensor networks with limited communication ranges on a circle. Automatica 92, June 2018 (2018), 155–161. https://www.sciencedirect.com/science/article/pii/S0005109818301018.Google ScholarCross Ref .
- 2018. A novel connectivity and coverage algorithm based on shortest path for wireless sensor networks. Computers and Electrical Engineering 71, October 2018 (2018), 1025--1039. https://www.sciencedirect.com/science/article/pii/S0045790617312983.Google ScholarCross Ref .
- 1964. Regular Figures. Oxford: Pergamon Press.Google Scholar .
- 2008. Distributed deployment schemes for mobile wireless sensor networks to ensure multi-level coverage. IEEE Transactions on Parallel and Distributed Systems 19, 9 (2008), 1280–1294.Google ScholarDigital Library .
- 2018. An optimized Bidding-based coverage improvement algorithm for hybrid wireless sensor networks. Computers and Electrical Engineering 65, January 2018 (2018), 1--17. https://www.sciencedirect.com/science/article/pii/S0045790617322164.Google ScholarCross Ref .
- 2017. Coverage problem with uncertain properties in wireless sensor networks: A survey. Computer Networks 123, August 2017 (2017), 200–232. https://www.sciencedirect.com/science/article/pii/S1389128617301998.Google ScholarCross Ref .
- 2005. Integrated coverage and connectivity configuration for energy conservation in sensor networks. ACM Transactions on Sensor Networks 1, 1 (2005), 36–72.Google ScholarDigital Library .
- 2018. Hybrid multi-objective evolutionary algorithms based on decomposition for wireless sensor network coverage optimization. Applied Soft Computing 68, July 2018 (2018), 268–282. https://www.sciencedirect.com/science/article/abs/pii/S1568494618301868.Google ScholarDigital Library .
- 2006. On connected multiple point coverage in wireless sensor networks. International Journal of Wireless Information Networks 13, 4 (2006), 289–301.Google ScholarCross Ref .
- 2002. PEAS: A robust energy conserving protocol for long-lived sensor networks. In Proceedings of the 10th IEEE International Conference on Network Protocols.
DOI: Google ScholarCross Ref . - 2007. Joint problem of power optimal connectivity and coverage in wireless sensor networks. ACM Wireless Networks, 13, 4 (2007), 537--550. .Google ScholarDigital Library .
- 2013. CWSC: Connected k-coverage working sets construction algorithm in wireless sensor networks. International Journal of Electronics and Communications 67, 11 (2013), 937–946.Google ScholarCross Ref .
- 2005. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc and Sensor Wireless Networks Journal 1, 1–2 (2005), 89–124.Google Scholar .
- 2006. Models and solutions for radio irregularity in wireless sensor networks. ACM Transactions on Sensor Networks 2, 2 (2006), 221–262.Google ScholarDigital Library .
- 2004. Connected k-coverage problem in sensor networks. In Proceedings of the 24th International Conference on Computer Communications and Networks. Rosemont, Illinois, 373–378.Google Scholar .
- 2005. A distributed coverage- and connectivity-centric technique for selecting active nodes in wireless sensor networks. IEEE Transactions on Computers 54, 8 (2005), 978–991.Google ScholarDigital Library .
- 2005. Fault tolerant connected sensor cover with variable sensing and transmission ranges. In Proceedings of the 1st Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks. California, 594–604.Google Scholar .
- Wilson. 2022. Retrieved May 27, 2022 from http://jwilson.coe.uga.edu/EMAT6680Su12/Carreras/EMAT6690/Essay2/essay2.html.Google Scholar
Index Terms
- A Computational Geometry-based Approach for Planar k-Coverage in Wireless Sensor Networks
Recommendations
An energy-efficient irregular hexagonal tessellation-based approach for connected k-coverage in planar wireless sensor networks
AbstractIn the design of planar wireless sensor networks (PWSNs), the preliminary tasks are to achieve both coverage and connectivity, which are essential for the correct operation of this type of network. A PWSN is said to be in perfect operational ...
k-CSqu: Ensuring connected k-coverage using cusp squares of square tessellation
AbstractIn planar wireless sensor networks (PWSNs), the most essential functionalities of the sensor nodes are both sensing and communication, which are evaluated using two fundamental concepts, namely coverage and connectivity, respectively. However, ...
Highlights- We tessellate a planar field of interest using adjacent and non-intersecting square tiles.
- We provide an optimal characterization of k-coverage in PWSNs using a minimum number of sensors, where k > 1.
- We compute the required sensor ...
Sensor scheduling for p-percent coverage in wireless sensor networks
We study sensor scheduling problems of p-percent coverage in this paper and propose two scheduling algorithms to prolong network lifetime due to the fact that for some applications full coverage is not necessary and different subareas of the monitored ...
Comments