Smallest Number of Sensors for k-Covering
Keywords:
WSN Networks, Coverage, Range.Abstract
This paper presents some theoretical results on the smaller number Nk(a, b) of sensors to achieve k coverage for the rectangular area [0, a] í— [0, b]. The first properties show the numbers Nk(a, b) are sub-additive and increasing on each variable. Based on these results, some lower and upper bounds for Nk(a, b) are introduced. The main result of the article proves that the minimal density of sensors to achieve k-coverage is (k) ≤ k/2 improving a previous result of Ammari and Das [2]. Finally, the numbers N1(a, b) are tabled for some small values of a, b.References
Adlakha, S., Srivastava M., Critical Density Threshold for Coverage in Wireless Sensor Networks, Proc. 2003 IEEE WCNC, 1615-1629, 2003.
Ammari, H.M., Das, S.K, Clustering-Based Minimum Energy Wireless m-Connected k- Covered Sensor Networks, Proc. of 2008 EWSN Sensor, LNCS 4913, 1-6, 2008.
Huang, C.F., Tseng, Y.C. The coverage problem in a wireless sensor network, Proc.of the 2nd ACM Int. Conf. WSNA, 115-121, 2003.
Kershner, R. The Number of Circles Covering a Set, American J. of Math., 61: 665-671, 1939. http://dx.doi.org/10.2307/2371320
Fowler, R.J., Paterson, M.S., Tanimoto, S.L., Optimal Packing and Covering in the Plane are NP-Complete, Information Processing Letters, 12: 133-137, 1981. http://dx.doi.org/10.1016/0020-0190(81)90111-3
Melisen, J.B.M., Shuur, P.C., Covering a Rectangle with 6 and 7 Circles, Discrete Applied Mathematics, 99: 146-156, 2000.
Milenkivic, V.J., Translational Polygon Containment and Minimal Enclosure Using Linear Programming Based Restriction, Proc. of the ACM Symposium on Theory of Computing, 109-118, 1996.
Nurmela, K.J., Ostergard, P.R.J., Covering a Square with up to 36 Equal Circles, Research Report HUT-TCS-A64, Laboratory of Theoretical Computer Science, Helsinky University of Technology, 2000.
Tarnai, T., Gasper, Z., Covering a Square by Equal Circles, Elementary Math., 167-170, 1995.
Verblunsky, S., On the Least Number of Unit Circles Which Can Cover a Square, Journal of London Math Society, 24: 164-170, 1949. http://dx.doi.org/10.1112/jlms/s1-24.3.164
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
