INT J COMPUT COMMUN, ISSN 1841-9836
8(2):312-319, April, 2013.

Smallest Number of Sensors for k-Covering

T. Tabirca, L.T. Yang, S. Tabirca

Tatiana Tabirca, Sabin Tabirca
School of Computer Science, MISL and 4C Centre
University College Cork, College Road, Cork, Ireland
E-mail: tabirca1@cs.ucc.ie, tabirca@cs.ucc.ie

Laurence T. Yang
Department of Computer Science
St. Francis Xavier University, Antigonish, NS, B2G 2W5, Canada
E-mail: ltyang@stfx.ca

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.
Keywords: WSN Networks, Coverage, Range.

1 Introduction

Wireless Sensor Networks (WSN) consist of a large number numbers of sensors distributed
uniformly in a target area, which monitor in a cooperative manner the physical word. Sensors
are in fact small devices capable of sensing variations in temperature, light, gas, motion etc,
computing and storing information and communicating with the neighbour sensors. The tech-
nology has nowadays made it possible to produce these devices at a cheap price so that WSN
networks are now involved in various applications from agriculture, surveillance, asset tracking,
health care to building safety and evacuation.

An important aspect in WSN applications is the coverage problem, which investigates how
well the target area is monitored by sensors. If each point of the area is covered by at least k
sensors then the WSN network is said to be k-covered, where k is the degree of the coverage.
For example, tracking WSN networks are at least 3-covered as they use triangulation. Moreover,
most WSN networks must be at least 2-covered to assure the robustness property.

It is clear that the bigger the coverage degree is, the more sensors must be used in WSN
networks. So far, all research works on the WSN coverage problem have assumed that a large
number of sensors is distributed in the target area to assure the network is k-covered. However, no
information has been given about the number of sensors to use for the target area or equivalently
about the sensor density. This article comes to investigate some properties of the minimal number
of sensors and to provide un upper bound for the minimal density of sensors to achieve k-coverage
in a rectangular area.

1.1 Problem Statement

Consider a set of sensors S = {s1, s2, s3, ..., sn} in the 2D plane with the same sensing range
r. The position of each sensor si is known and given by the coordinates (xi, yi). The target
area A to monitor can be of any shape but for simplicity it is considered to be rectangular
A = [0, w]× [0, h] of width w and height h.

Copyright c⃝ 2006-2013 by CCC Publications



Smallest Number of Sensors for k-Covering 313

Definition 1. A point (x, y) ∈ A is covered by a sensor si if
√

(xi −x)2 + (yi −y)2 ≤ r. The
target area A is k-covered by the sensors S if each point (x, y) ∈ A is covered by at least k
different sensors.

It is clear that the number of sensors n to achieve k-coverage increases directly with k. Hence,
the bigger is k the more sensors are needed for k-coverage. So far, the main assumption has been
that sensors are cheap devices and the numbers of them to deploy is not important. Consequently,
it has been considered that the number of sensors to deploy is big enough to achieve k-coverage
on the target area.

1.2 Related Works

Investigating 1-coverage or circle packing has been researched as geometrical combinatorial
since 1939. Researchers have tried to find mathematical equations for the optimal 1-covering
or even to prove that some configurations are optimal. For example Kershner [4] investigated
the problem of covering any 2D set of points with similar circles based on some geometrical
combinatorial techniques. This early work proved that the minimal number of circles N(ε) of
radius ε to cover a close set of point M satisfies

lim
ε→0

N(ε) =
2
√
3

9 ·ε2
· |M|,

where |M| denotes the area of closed by M. The result was proven by using a double inequality
for the quantity πε2N(ε) representing the total area covered by the circles. An important
consequence of this result is that the proportion of unavoidable overlapping can be approximated
by 2π

√
3

9
≃ 1.209. We can also mention the early work of Verblunsky [10] who proved that the

minimum number N(l) of circles of radius 1 to cover a square of length l should satisfy

N(l) ≥
2l2 + l

3
√
3

.

These two results come to suggest that the sensor density for 1-coverage can be estimated by
2
√
3

9
≈ 0.384.

However, these early works [4], [10] do not provide any information about the pattern of
circles used to achieve the minimal coverage. Recently, several articles on circle packing problems
investigated efficient ways to cover a rectangle with similar circles (see [6], [8] or [9] amongst
others). These geometrical combinatorics researches confirmed that optimal packing is difficult
to be achieve even for small number of circles. Furthermore, no pattern was detected for the
packing configuration that gives optimality.

Recently, several papers have dealt with the k-coverage problems in the context of sensor
networks studying conditions when this is achieved or algorithms to detected when this happens.
Some of these contributions have made marginal reference to the minimum number or equiva-
lently to the minimum density of sensors that assures k-covering of a given area. Generally, all
these works have considered that the number of sensors to use is big enough to k-cover the target
area. Adlakha and Srivasyava [1] developed an exposure-based model to find the sensor density
required to achieve full coverage of a given area. They proved that the number of sensors to
achieve 1-covering is in the order of O(A/r2), where A is the area to cover however they did not
provide any constant for the magnitude of A/r2. Ammari and Das [2] investigated the problem
of k-coverage proposing a condition to achieve it. They considered the target area divided in
"Reuleaux" triangles which are formed by the intersection of 3 circles. The main result of their
work states that the target area is k-covered if and only if each "Reuleaux" triangle contains at



314 T. Tabirca, L.T. Yang, S. Tabirca

least k-active sensors. Another important results proposed by Ammari and Das gives that the
minimal density of sensors to guarantee k-coverage is λ(r, k) = 2k

(π−
√
3)·r2

= 1.4188·k
r2

, where r is
the radius of the sensing disks.

Most covering problems present huge difficulties to solve or to derive a polynomial algorithm
even in particular cases like regular or simple shapes and lower dimensional space. The 2D prob-
lem of covering a bounded domain with arbitrary shaped objects was proven to be exponential
on the size of the packing space [7]. The particular case of covering any polygon with n similar
disks is known to be NP-hard [5]. Consequently, the problem of finding the least number of disks
to k-cover a rectangle is NP-hard.

All these works have shown that calculating the minimal number of circles to pack a rectangle
is a hard problem and there is no patter associated with this covering. Moreover, the results
concerning the minimal number of circles for k-coverage are all either asymptotic based on some
limits or approximative based on some inequalities.

2 Minimal Number of Sensors

Consider the following problem "Find the smallest number of sensors Nk(a, b) that should
be used to achieve k-coverage for a rectangular area of sizes a and b with sensors of the same
radius". We can suppose that all the sensors have the coverage radius of 1 unit. By convention
Nk(a, b) = 0 when a ≤ 0 or b ≤ 0. It is clear that a k-coverage with n sensors satisfies

n ≥ Nk(a, b). (1)

The following results can be directly obtained based on Equation 1 and on the definition of
Nk(a, b).

Lemma 1. The function Nk(a, b) is symmetrical on a, b

Nk(a, b) = Nk(b, a), ∀a, b > 0.

Lemma 2. The function Nk(a, b) is monotonically on each variable:

a1 ≤ a2 ⇒ Nk(a1, b) ≤ Nk(a2, b).

b1 ≤ b2 ⇒ Nk(a, b1) ≤ Nk(a, b2).

k1 ≤ k2 ⇒ Nk1(a, b) ≤ Nk2(a, b).

Lemma 3. The function Nk(a, b) is sub-additive on each variable:

Nk(a1 + a2, b) ≤ Nk(a1, b) + Nk(a2, b).

Nk(a, b1 + b2) ≤ Nk(a, b1) + Nk(a, b2).

Nk1+k2(a, b) ≤ Nk1(a, b) + Nk2(a, b).

Proposition 1. N1(
√
2 ·n,

√
2 ·m) ≤ n ·m when n, m ∈ N.

Proof: Consider that the rectangular area of sizes a =
√
2 ·n, b =

√
2 ·m is divided into a grid

of n×m squares of size
√
2. Each square can be 1-covered by its circle as Figure 2 shows. Hence,

N1(
√
2 ·n,

√
2 ·m) ≤ m ·m since there is a 1-coverage with n ·m circles. 2

Evidence shows that N1(
√
2 ·n,

√
2 ·m) = m ·m for many values of m, n. However, we have

not been able to produce a coherent proof of the fact that N1(
√
2 · n,

√
2 · m) ≥ n · m nor a

counterexample to show that N1(
√
2 ·n,

√
2 ·m) < n ·m for some values of m, n.



Smallest Number of Sensors for k-Covering 315

Figure 1: 1-Covering of the Rectangle w =
√
2 ·n, h =

√
2 ·m.

Proposition 2. The numbers N1(a, b) satisfy the following inequality

N1(a, b) ≤⌈
a
√
2
⌉ · ⌈

b
√
2
⌉, ∀a, b ∈ R (2)

where ⌈x⌉ is the ceiling function.

Proof: Consider n = ⌈ a√
2
⌉∈ N so that we have a√

2
≤ n or a ≤ n·

√
2. Similarly, if m = ⌈ b√

2
⌉∈ N

we obtain b ≤ m ·
√
2. Now, the following inequality can be derived based on Lemma 1

N1(a, b) ≤ N1
(
n ·
√
2, m ·

√
2
)
⇒

N1(a, b) ≤ n ·m ⇒ N1(a, b) ≤⌈
a
√
2
⌉ · ⌈

b
√
2
⌉,

which it proves the theorem. 2

The result above gives only an upper bound of values in which the number N1(a, b) can be
located.

Theorem 1. For k-coverage problem, the numbers Nk(a, b) satisfy the following inequality

k ·a · b
π

≤ Nk(a, b) ≤ k · ⌈
a
√
2
⌉ · ⌈

b
√
2
⌉, ∀a, b ∈ R (3)

Proof: The sub-additivity property is used as follows

Nk(a, b) = N1+...+1(a, b) ≤ N1(a, b) + ... + N1(a, b) =

= k ·N1(a, b) ≤ k · ⌈
a
√
2
⌉ · ⌈

b
√
2
⌉,

which proves the right hand side inequality. For the left hand side we considered that each
point of the rectangle is covered by at least k circles. Hence, the Nk(a, b) circles cover the whole
rectangle surface by k times. Hence, the area of the circles is greater than k times the area of
the rectangle.

Nk(a, b) ·π ·12 ≥ k ·a · b ⇒ Nk(a, b) ≥
k ·a · b

π
.



316 T. Tabirca, L.T. Yang, S. Tabirca

2

Assume that the minimal density of sensors Nk(a,b)
a·b does not depend on a, b for large values

of a, b, so that we can write λ(k) ≃ Nk(a,b)
a·b ,∀a, b. In this case the minimal density of sensors can

be evaluated by the following result.
Theorem 2. The minimum density of sensors to achieve k-covering for rectangular areas satisfies

k

π
≤ λ(k) ≤

k

2
. (4)

Proof: Each member of Equation 3 is divided by a · b to obtain

k

π
≤

Nk(a, b)

a · b
≤

k · ⌈ a√
2
⌉ · ⌈ b√

2
⌉

a · b
⇒

k

π
≤

Nk(a, b)

a · b
≤ k ·

⌈ a√
2
⌉

a
·
⌈ b√

2
⌉

b
.

Consider that the minimum density to achieve k-covering is independent of the area to cover
hence it can be denoted by λ(k). So that we have

k

π
≤ λ(k) ≤ k ·

⌈ a√
2
⌉

a
·
⌈ b√

2
⌉

b
, ∀a, b > 0.

If a, b →∞ are big then the fractions become lima→∞
⌈ a√

2
⌉

a
= 1√

2
and limb→∞

⌈ b√
2
⌉

b
= 1√

2
so that

k
π
≤ λ(k) ≤ k

2
. 2

Theorem 2 shows that the minimal density to achieve k-coverage with sensors of radius 1 is
between 0.318109 · k and 0.5 · k. The first conclusion we can extract is that this number is far
smaller than the density proposed in [2] which is 1.4188 · k. This huge difference would raise
serious question marks on the "Reuleaux" triangulation approach developed by Ammari and Das
and hence on the results they proposed. The second conclusion is that, in particular for k = 1,
this result states that the density for 1-covering is between 0.318 and 0.5, which is in concordance
with the early results of Kershner and Verblunsky.

On the other hand, the minimal density of sensors Nk(a,b)
a·b can also have the following upper

bound for any a, b ≥ 2.

Nk(a, b)

a · b
≤ k ·

⌈ a√
2
⌉

a
·
⌈ b√

2
⌉

b
≤ k ·

a√
2
+ 1

a
·

b√
2
+ 1

b
⇒

Nk(a, b)

a · b
≤ k ·

(
1
√
2
+

1

a

)
·
(

1
√
2
+

1

b

)
= k ·

[
1

2
+

1
√
2
· (

1

a
+

1

b
) +

1

a · b

]
⇒

Nk(a, b)

a · b
≤

k

2
·

[
1 +

P + 2
√
2

A

]
,

where P and A are the perimeter and the area of the target region respectively. This provides
an upper bound for the density based on the perimeter and the surface of the target area.

3 Some Computational Results

This section is to find directly or using some computation some of the numbers Nk(a, b).
Firstly, we start with the numbers N1(a, b), which can be calculated for several small values of
a, b. For example, N1(

√
2,
√
2) = 1 and furthermore N1(a, b) = 1, ∀a, b ≤

√
2. This simple case

can be extended to the situation where we have a row of sensors to achieve minimal 1-coverage
(see Figure 3).



Smallest Number of Sensors for k-Covering 317

Figure 2: Optimal 1-Covering of the Rectangle with a ≤
√
2.

Theorem 3. The following two results can apply for the situation when the rectangle has either
the width or the height less than

√
2 (see Figure 3):

N1(a,
√
4−a2 ·m) = m,∀m ∈ N, a ≤

√
2

N1(
√

4− b2 ·n, b) = n,∀n ∈ N, b ≤
√
2.

Proof: The proof only considers the case when a ≤
√
2 as the second one is similar. Figure 3)

shows a 1-covering of the rectangle with m sensors so that N1(a,
√
4−a2 · m) ≤ m. Lets start

from an 1-covering with N1(a,
√
4−a2 · m) sensors of a target area with the sizes w = a, h =

m ·
√
4−a2. Consider the rectangle is divided into m small rectangles R1, R2, ..., Rm each of

sizes w = a, h =
√
4−a2. The focus is now on R1 which is fully covered with some circles from

which there is one with the smallest x coordinate for the centre. This circle is then translated
so that it will fit into the whole rectangle. It is clear that the area of R1, previously covered
by some circles, is now covered by one circle. Hence, this new configuration is still a 1-coverage
with the same number of sensors. Now, R2 must have at least one circle to cover the nodes in
common with R1 so that we can use it to repeat the same type of transformation. After m steps
we find that there are m circles amongst the N1(a,

√
4−a2 ·m) circles that can be positioned as

in Figure 3. Hence, N1(a,
√
4−a2 ·m) ≥ m. 2

This theorem provides directly the following two consequences.

Remark 3.1. N1(1, m) = ⌈ m√
3
⌉,∀m ∈ N.

Remark 3.2. N1(2, m) ≤⌈ m√
2
⌉+⌈ m

4
√
2−2
⌉,∀m ∈ N.

For the second remark it is clear that N1(2, m) = N1(
√
2 + 2 −

√
2, m) ≤ N1(

√
2, m) +

N1(2−
√
2, m) = ⌈ m√

2
⌉+⌈ m

4
√
2−2
⌉. It seems that ⌈ m√

2
⌉+⌈ m

4
√
2−2
⌉ represents the value of N1(2, m)

for several small values of m = 1, 2, 3, 4. However, there is no proof to show that N1(2, m) =
⌈ m√

2
⌉+⌈ m

4
√
2−2
⌉. These simple results help in tabling the numbers N1(n, m) for some small values

of n, m ∈ N when one of the indices is 1 or 2 (see Table 1).

n,m m=1 m=2 m=3 m=4 m=5
n=1 1 2 2 3 3
n=2 2 4 4 6 7
n=3 2 4 6 7 11
n=4 3 6 7 9 11
n=5 3 7 11 11 14

Table 1: Table with the Values N1(n, m), n, m = 1, 2, 3, 4, 5



318 T. Tabirca, L.T. Yang, S. Tabirca

The values of Nk(n, m) for big n, m are not simple to calculate since generating a k-coverage
is NP-complete. A simple generic computation for Nk(n, m) has to go firstly through all the
values between nr = n · m · k/π, n · m · k/2 in order to generate all the possible configurations
of nr circles. Secondly, the k-coverage property should be tested for each configuration of nr
circles. If the property holds for a particular configuration of nr circles then Nk(n, m) = nr (see
Algorithm 1). Testing whether a set of sensors or configuration of circles achieves k-coverage
is a well studied problem with few polynomial solutions (see [3] for an O(nr log nr) solution).
However, the problem of generating all the configurations with nr circles within the target area
[0, n]× [0, m] is computationally hard and it can be solved only by using searching methods like
backtracking. The running time to search exhaustively for the optimal configuration can be in
this case very big but the algorithm provides the correct value for Nk(n, m).

Figure 3: Execution Times for Deterministic and Probabilistic Approaches.

Algorithm 1 Generic Scheme to Calculate Nk(n, m).
function(n,m,k)
for nr= n·m·k

π
to n·m·k

2
do

// generate all the possible nr circles
repeat

generate a new configuration with nr circles
test k-coverage for the circles
if k-coverage holds then

return nr;
end if

until possible
end for

The alternative to this approach is to generate a very large number of random configurations
hoping that the k-coverage with Nk(n, m) circles is reached by one of them. In this case the
number Nk(n, m) is not accurately computed but the execution time can substantially be re-
duced. The following simulations give a good illustration of the trade off between accuracy and
running time. Figure 4 presents the execution times for the deterministic algorithm against the
probabilistic approach with 50000 and 100000 iterations. One can see that the execution times
of the deterministic algorithm grew at an exponential rate when w · h increases. The execution
for the small area of w = 5, h = 5 took more than 18 minutes. On the other hand, the execu-
tion times for the probabilistic approaches have a slow increasing rate far smaller than in the



Smallest Number of Sensors for k-Covering 319

deterministic case. Moreover, the probabilistic version with 100000 iterations provided the same
results as the deterministic solution.

4 Conclusions

This article has investigated some theoretical properties related with the minimum number
of sensors Nk(a, b) to achieve k-covering of a rectangular area. Firstly, the numbers Nk(a, b) have
been proven to be sub-additive on each variable. Secondly, we have found a interval of possible
values for Nk(a, b) numbers between k·a·bπ and k ·⌈

a√
2
⌉·⌈ b√

2
⌉. Based on that the minimal density

of sensors to achieve k-coverage has been proven to be less than k/2 improving a result of [2].
Some computation has been used to generate the numbers N1(a, b) for small values of a, b.

Acknowledgement

The first author would like to acknowledge the financial support provided by the MISL and
4C research centres and to thank to Prof Cormac Sreenan and Dr Ken Brown for the useful
discussions on the WSN topics.

Bibliography

[1] Adlakha, S., Srivastava M., Critical Density Threshold for Coverage in Wireless Sensor Net-
works, Proc. 2003 IEEE WCNC, 1615-1629, 2003.

[2] 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.

[3] 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.

[4] Kershner, R. The Number of Circles Covering a Set, American J. of Math., 61: 665-671,
1939.

[5] 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.

[6] Melisen, J.B.M., Shuur, P.C., Covering a Rectangle with 6 and 7 Circles, Discrete Applied
Mathematics, 99: 146-156, 2000.

[7] 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.

[8] 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.

[9] Tarnai, T., Gasper, Z., Covering a Square by Equal Circles, Elementary Math., 167-170, 1995.

[10] Verblunsky, S., On the Least Number of Unit Circles Which Can Cover a Square, Journal
of London Math Society, 24: 164-170, 1949.