We study the problem of constructing a cost-effective regular cover of a strip with identical sectors. Three effective coverage models are considered and their comparative analysis is performed which allows to obtain an upper bound for the minimum number of the sectors per unit length of the strip.
Sensor networks are designed to monitor the areas and/or the objects. Each sensor
in the network collects data within a certain area, which is called a coverage domain
of the sensor. In the case of monitoring the plane region each point of the region
should be covered, i.e. it (point) should belong to the coverage domain of at least one
sensor. Sensing energy consumption is proportional to the coverage area, and multiple
coverage involves unnecessary loss of the energy. Therefore, the problem of constructing
an energy efficient sensor network is reduced to the problem of finding the least dense
cover [
The number of the papers devoted to the covering of the bounded regions is
substantially less. The first attempts to construct a strip covers were made in [
Evidently that the density of a cover is at least 1, and the deviation from 1
characterizes the effectiveness of the cover. More types of figures used in the cover, the lower
density of the coverage can be. Of course, it is legitimate to compare the covers, which
use the same set of figures. For simplicity of analysis the researchers, as a rule, consider
the regular covers, in which the whole area is split into the equal polygons (tiles ), and
all the tiles are covered equally [
The need to monitor the strip occurs when observing the objects such as roads,
pipelines, perimeters of the objects, etc. In the case when camera is located at a certain
height above the surface, on the surface it covers an ellipse. The coverage problems
with ellipses are considered, for example, in [
In this paper, as well as in [
The paper is organized as follows. In the next section a formulation of the problem is provided. The covering models are proposed in the section 3, and for each model the objective function is provided. Section 4 presents a comparative analysis of the proposed coverings, allowing to select a concrete cover depending on the parameters of the sector. Section 5 concludes the paper. 1
To denote the sector, we use the couple (R, α), where R > 0 is the radius and α ∈ (0, π/2] is the angle of the sector. Let strip be given and, without loss of generality, let its width be equal to 1. Assume that there is an unlimited collection of the identical sectors (R, α) each of which can be arbitrary placed and oriented.
Definition 1. A collection C of the placed and oriented sectors is called a cover of the strip S if every point of S belongs to at least one sector in C.
Definition 2. A cover C of the strip S is called regular if S is split into the equal rectangles (tiles), and all tiles are covered identically.
The height of a tile is 1, but its length depends on the cover. Let us denote the minimal length of a tile in the cover C as L(C), and the number of sectors covering one tile denote as Q(C).
Problem P. It is required to construct a regular cover C = C(R, α) of the strip with equal sectors (R, α) in which the ratio σ(C) = Q(C)/L(C) is minimal. 2
As an approximate solutions of the problem P, we consider the same three models of
covers as in [
Suppose that 0.5 < R sin α ≤ 1. Let us define the pair of sectors inside the strip such that two of their sides (one side of each sector) lie on the opposite boundaries of the strip, while the other two are tangent to each other. The pair of sectors cover the rectangle (tile) GBCF in Fig. 1 that is a part of the strip. Cover M1 is constructed with these pairs of sectors as shown in Fig. 1, so the number of sectors covering one tile is Q(M 1) = 2. In this regular cover the tile is the rectangle GBCF whose height coincides with the strip width and equals to 1. At that, the strip is subdivided into identical tiles, and all tiles are covered in the same fashion by the pairs of sectors.
D q(1 − x)2 − x2 sin2 α − x sin2 α cos α .
Since the functions sin α, sin2 α and sin2 α cos α are all positive, the function σ(M 1(x, α)) is increasing by x. Then (1) takes its minimum when R sin α = 1. By substituting this value in the formula (1), we get a minimum equals 2 sin α. The proof is over. Remark 1. If the sector (R, α) is given, then we cannot choose arbitrary R and α, but the value 2 sin α is the lower bound for the functional (1), which decreases with decreasing α.
If the sensor is a camcorders, then the greater the angle the smaller the radius and vice versa, but the area of the sector can be fixed, for example,
R2α/2 = S = const. (2) If so, then we cannot set always R sin α = 1 (x = 0). In this case we can take the minimal possible positive x = 1−R sin α = 1−p2S/α sin α. Then it is necessary to find maximum for p2S/α sin α which is at most 1. The function f (α) = sin α/√α is concave and positive having maximum equals f¯ ≈ 0.8512 when α = α¯ ≈ π/2.6953 ≈ 66.78◦. Therefore, if √2Sf¯ ≤ 1, then we set α = α¯, else set α = αˆ, where αˆ is such that p2S/αˆ sin αˆ = 1.
Substituting the equality (2) into the formula (1), we obtain σ(M 1(S, α)) = 2 sin α
2 sin α r 2S α − 1 − q 2αS sin α − 1 − q 2αS sin α cos α
For any feasible value of S the function σ(M 1(S, α)) is increasing. Then the minimal feasible angle α gives minimum to the σ(M 1(S, α)). For example, if S = 2, then α min α {α: 8 sin2 α <S≤ 2 sin2 α }
σ(M 2(S, α)) ≈ 0.2523 when α ≈ π/49.9458 ≈ 3.6◦. 2.2
Suppose now that R sin α ≥ 1, and let us consider the cover in Fig. 2 and denote it as M2. The cover model M2 has much in common with model M1. One side of each sector of the pair of sectors lies on the strip boundary, and the sectors of the same pair do not intersect, but in M2 a portion of each sector goes beyond the strip. Lemma 2. The objective function for the cover M2 is
Then the objective function for M2 is
Remark 2. If the sector (R, α) is given, then we cannot take always both R and α the greatest possible.
If equality (2) holds, then R = p2S/α, and σ(M 2(S, α)) = sin α p2S/α − 1 + p2S/α − cos α assuming that 2S/α ≥ 1 and sin α p2S/α − 1 + p2S/α − cos α > 0. For each feasible value of S the function σ(M 2(S, α)) has one minimum. For example, if S = 2, then
minα {α:S≥ 2 sin2 α }
σ(M 2(S, α)) ≈ 0.5055 when α ≈ π/12.2958 ≈ 14.64◦. 2.3
Let none of the sector side lie on the boundary of the strip, and let R cos(α/2) ≥ 1. We denote the cover in Fig. 3 as M3. Each of the sectors leans upon the boundary of the strip by at least one end of the arc, and the sector axis is at some angle to the strip boundary, whereas the tangent sectors in the pair is directed oppositely.
Let us introduce the parameter β, the angle between the sector axis and the line orthogonal to the strip boundaries (Fig. 3). Then 0 ≤ β ≤ π/2 − α/2 − arcsin(1/R). ,
A. Erzin Lemma 3. The objective function for the cover M3 is σ(M 3(R, α)) =
min
Function σ(M 3(R, α, β)) is concave with respect to β for each values of α and R, then it reaches minimum at the boundary of the feasible region, i.e.
σ(M 3(R, α)) = min {f1(R, α); f2(R, α)} , where and f2(R, α) = f1(R, α) =
2 cos2(α/2) sin α(2R cos(α/2) − 1) 2 sin2(α + arcsin R1 ) sin α(2R sin(α + arcsin R1 ) − 1) .
The functions f1(R, α) and f2(R, α) are decreasing, first f1(R, α) ≥ f2(R, α), then vice-versa. Then min σ(M 3(R, α)) = f1(R, π/2) = α≤π/2
1 Function (4) is concave with respect to β, then it takes minimum value on the boundary of the feasible region, i.e.
min 0≤β≤π/2−α/2−arcsin √ 2αS
σ(M 3(S, α, β)) = min σ(M 3(S, α, 0)), σ
M 3 S, α, π/2 − α/2 − arcsin 2 sin α min ( cos2(α/2) ;
sin2 α + arcsin p 2αS p8S/α cos(α/2) − 1 p8S/α sin α + arcsin p 2αS − 1 = )
. r α 2S Let us fix any feasible S. When α is small, the decreasing function is greater than the increasing function f3(S, α) =
2 cos2(α/2) sin α(p8S/α cos(α/2) − 1) f4(S, α) =
2 sin2(α + arcsin p 2αS ) sin α(p8S/α sin(α + arcsin p 2αS ) − 1) .
Then in order to minimize the objective function one should take minimal feasible angle, and function f4(S, α) gives the minimum.
For example, if S = 2, then
min 0≤β≤π/2−α/2−arcsin √ 2αS
σ(M 3(S, α, β)) = f4(2, α) → 0.5 when α → 0.
The objectives of this section is to find out which of the three considered cover models M1, M2, or M3 has minimum objective function σ(M 1(R, α)), σ(M 2(R, α)) or σ(M 3(R, α)) for arbitrary R and α. Definition 3. By the best cover we understand the cover among models M1, M2, and M3 with least objective function.
Since the analytical calculation of the objective functions turned out to be a hard problem, the subsequent results were obtained numerically using Maple 17.02 package.
At each point (α, R), α ∈ [1◦, 90◦], 0 < R ≤ Rmax we calculate the values of the objective functions σ(M 1(R, α)), σ(M 2(R, α)) and σ(M 3(R, α)) and select the minimum among them. The model of the strip cover that corresponds to this value is the best among M1, M2, and M3.
The preference areas are indicated in Fig. 4 for each coverage model. Given different values of the regions of admissibility of the sector parameters, we obtain different zones, but the character of the pattern will not change. The image in Fig. 4 is obtained when R = 0.1, 0.2, . . . , Rmax = 6.0 and α = 1◦, 2◦, . . . , 90◦.
It is obvious that for any fixed value of the angle α the values of the objective functions decrease with increasing radius R. Therefore, assuming the radius R = Rmax we reduce maximally the value of the objective function. Fig. 5 depicts a graph of the
Fig. 5. Function Σ(α). function
Σ(α) = min {σ(M 1(Rmax, α)), σ(M 2(Rmax, α)), σ(M 3(Rmax, α))} , when Rmax = 6. Its minimum equals Σ(α) = σ(M 3(Rmax, α)) ≈ 0.1678 when α = 90◦. If, for example, Rmax = 2, then Σ(α) = σ(M 2(Rmax, α)) ≈ 0.5359 when α = 90◦.
Suppose equality (2) holds. Then we cannot set R = Rmax, because R = p2S/α depends on S and α. Depending on the value of S, we get different results, but the character of graphics remains like in Fig. 6 and Fig. 7.
Fig. 7 depicts a graph of the function
ΣS(α) = min {σ(M 1(S, α)), σ(M 2(S, α)), σ(M 3(S, α))} , when S = 2. Its minimum equals ΣS(α) = σ(M 1(S, α)) ≈ 0.5049 when α = 14◦. If, for example, S = 6, then ΣS(α) = σ(M 2(S, α)) ≈ 0.1669 when α = 5◦. 4
Since the identical directed sensors (when the coverage domain is the sector) have equal cost, in this paper we consider the problem of constructing the optimal cover of a strip with identical sectors object to the minimum number of sensors used to cover a strip. Three regular covers are studied, and their cost-effective comparative analysis is carried out.
Technique, which we have used, is similar to what was used in [
Moreover, we have considered the case when the angle and radius of the sector are related the natural relation (2), where S is the area of the sector. If the area S is fixed, then by increasing the angle α of the sector radius R decreases, and vice versa. In particular, we can find the optimal angle and the best coverage model for any S. Acknowledgments. This research is supported in part by the Russian Foundation for Basic Research (grant No. 16-07-00552) and the Ministry of Education and Science of the Republic Kazakhstan (project No. 0115PK00550). For the numerical calculations we used the Maple 17.02 package licensed to the Novosibirsk State University (serial No. S2AJ447HV7HAJY5V).