Smallest Number of Sensors for k-Covering


  • Tatiana Tabirca School of Computer Science, MISL and 4C Centre University College Cork, College Road, Cork, Ireland
  • Laurence T. Yang Department of Computer Science St. Francis Xavier University, Antigonish, NS, B2G 2W5, Canada
  • Sabin Tabirca School of Computer Science, MISL and 4C Centre University College Cork, College Road, Cork, Ireland


WSN Networks, Coverage, Range.


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.


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.

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.

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.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.