Cost-Effective Strip Covering with Identical Directed Sensors Adil Erzin 1 Sobolev Institute of Mathematics, Novosibirsk, Russia 2 Novosibirsk State University, Novosibirsk, Russia adilerzin@math.nsc.ru Abstract. 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. Keywords: sensor networks; video monitoring; regular covering Introduction 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 [1–3]. The most studied are the covers of the plane [4–7]. In particular, √ in [4] the least dense cover with identical disks is proposed, its density is 2π/ 27 ≈ 1.2091. In [5] a cover with disks of two types is proposed, its density tends to 1.0189 with unlimited growth of the number of disks, which radii tends to zero. The number of the papers devoted to the covering of the bounded regions is sub- stantially less. The first attempts to construct a strip covers were made in [8, 9] (the strip can be considered as a semi-bounded domain). Evidently that the density of a cover is at least 1, and the deviation from 1 charac- terizes 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 [2–5, 8, 10]. To evaluate the quality of the regular cover it is sufficient to consider the coverage of one tile. In [3] we introduced a classification of the regular covers, that has allowed to compare the covers in the same class. Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org 702 A. Erzin 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 [10, 11]. If the camcorder lens is positioned horizontally, then the coverage area in this case is a sector. The angle and radius of the sector are determined by the characteristics of the device, and can take different feasible values. The sectors are used in the covers in the several papers [12–22]. In [21], we considered the problem of minimizing the number of identical sectors per unit of the covered area in the case when the vertices of the sectors which cover one tile are located at the same point. In [22], we considered the problem of constructing the least dense cover of a strip with identical sectors. In this paper, as well as in [22], we consider the problem of constructing an optimal cover of the strip with equal sectors, but according to the criterion the minimum number of sectors per unit length of the strip. Since the sectors are equal, such objective function can be considered as a cost function. 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 Problem Formulation 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 The Coverage Models As an approximate solutions of the problem P, we consider the same three models of covers as in [22]. But instead of the density function we consider the objective function σ(C(R, α)). Strip Covering with Identical Directed Sensors 703 2.1 Model M1 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. A B C a 1 D R E K 1 D G F Fig. 1. Model M1 [22]. Lemma 1. The objective function for the cover M1 is 2 sin α σ(M 1(R, α)) = p , (1) sin α R − (1 − R sin α)2 − (1 − R sin α) cos α 2 and it takes the minimum value equals 2 sin α when R sin α = 1. Proof. In [22], we proved the expression p 1 − R sin α L(M 1) = a1 = R2 − (1 − R sin α)2 − . tan α Then the objective function is Q(M 1) 2 sin α σ(M 1(R, α)) = = . L(M 1) p sin α R2 − (1 − R sin α)2 − (1 − R sin α) cos α Denote x = 1 − R sin α ≥ 0. Then R = (1 − x)/ sin α and 2 sin α σ(M 1(x, α)) = 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. 704 A. Erzin 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 α = 1p (x = 0). In this case we can take the minimal possible positive x = 1−R sin α = 1− 2S/α sin α. Then it is necessary to find p √ maximum for 2S/α 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 2S f ≤ 1, then we set α = ᾱ, else set α = α̂, where α̂ is such that p 2S/α̂ sin α̂ = 1. Substituting the equality (2) into the formula (1), we obtain 2 sin α σ(M 1(S, α)) = r  q 2  q  . 2S 2S 2S sin α α − 1− α sin α − 1− α 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 σ(M 2(S, α)) ≈ 0.2523 {α: 8 sinα2 α 0. For each feasible value of S the function σ(M 2(S, α)) has one minimum. For example, if S = 2, then min σ(M 2(S, α)) ≈ 0.5055 {α:S≥ 2 sinα2 α } when α ≈ π/12.2958 ≈ 14.64◦. 2.3 Model M3 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). 706 A. Erzin E D C D 1 R E D A B a 3 Fig. 3. Model M3 [22]. Lemma 3. The objective function for the cover M3 is ( ) 2 cos2 (α/2) sin2 (α + arcsin R1 ) σ(M 3(R, α)) = min ; 1 , (4) sin α 2R cos(α/2) − 1 2R sin(α + arcsin R )−1 and its value is at least 1 √ . R 2−1 Proof. In [22], we proved that R sin α |AB| = cos(β − α/2) and     1 R sin α 1 |DC| = |AB| 1 − = 1− . R cos(β − α/2) cos(β − α/2) R cos(β − α/2) Then the length of the tile is sin α(2R cos(β − α/2) − 1) L(M 3) = a3 = |AB| + |DC| = cos2 (β − α/2) and 2 2 cos2 (β − α/2) σ(M 3(R, α, β)) = = . a3 sin α(2R cos(β − α/2) − 1) 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, α)} , Strip Covering with Identical Directed Sensors 707 where 2 cos2 (α/2) f1 (R, α) = sin α(2R cos(α/2) − 1) and 2 sin2 (α + arcsin R1 ) f2 (R, α) = . sin α(2R sin(α + arcsin R1 ) − 1) The functions f1 (R, α) and f2 (R, α) are decreasing, first f1 (R, α) ≥ f2 (R, α), then vice-versa. Then 1 min σ(M 3(R, α)) = f1 (R, π/2) = √ . α≤π/2 R 2−1 This completes the proof of Lemma 3. If (2) holds, then 2 cos2 (β − α/2) σ(M 3(S, α, β)) =  p , sin α 2 2S/α cos(β − α/2) − 1 r α 0 ≤ β ≤ π/2 − α/2 − arcsin , α ≤ 2S. 2S Function (4) is concave with respect to β, then it takes minimum value on the boundary of the feasible region, i.e. min √ α σ(M 3(S, α, β)) = 0≤β≤π/2−α/2−arcsin 2S    r  α min σ(M 3(S, α, 0)), σ M 3 S, α, π/2 − α/2 − arcsin = 2S ( ) sin2 α + arcsin 2S pα 2 cos2 (α/2) min p ; p pα . sin α 8S/α cos(α/2) − 1 8S/α sin α + arcsin 2S −1 Let us fix any feasible S. When α is small, the decreasing function 2 cos2 (α/2) f3 (S, α) = p sin α( 8S/α cos(α/2) − 1) is greater than the increasing function 2 sin2 (α + arcsin pα 2S ) f4 (S, α) = p pα . sin α( 8S/α sin(α + arcsin 2S ) − 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 √ α σ(M 3(S, α, β)) = f4 (2, α) → 0.5 0≤β≤π/2−α/2−arcsin 2S when α → 0. 708 A. Erzin 3 Comparative Analysis of Models M1, M2, and M3 The objectives of this section is to find out which of the three considered cover mod- els M1, M2, or M3 has minimum objective function σ(M 1(R, α)), σ(M 2(R, α)) or σ(M 3(R, α)) for arbitrary R and α. Fig. 4. The preference regions for the covers M1 (red), M2 (blue), and M3 (green). 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◦ . Strip Covering with Identical Directed Sensors 709 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 ( ) 6D D ± M o d e l M 2 ± M o d e l M 2 ± M o d e l M 3 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 p. Suppose equality (2) holds. Then we cannot set R = Rmax , because R = 2S/α 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 Conclusion 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. 710 A. Erzin Fig. 6. The preference regions for the covers M1 (red), M2 (blue), and M3 (green) when equality (2) holds. ) 6 D S ( D ± M o d e l M 2 ± M o d e l M 2 ± M o d e l M 3 Fig. 7. Function ΣS (α). Strip Covering with Identical Directed Sensors 711 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 [22]. But the results we obtain are new. Using our results, one can choose the cost-effective coverage model for any sector (R, α), 0 < R ≤ Rmax , α ∈ [1◦ , 90◦ ]. 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). References 1. Cardei, M., Wu, J.: Energy-efficient Coverage Problems in Wireless Ad-hoc Sensor Net- works. Computer Communications. 29(4), 413–420 (2006) 2. Fan, G., Jin, S.: Coverage Problem in Wireless Sensor Network: A Survey. J. Networks. 5(9), 1033–1040 (2010) 3. Zalyubovskiy, V., Erzin, A., Astrakov, S., Choo H.: Energy-efficient area coverage by sensors with adjustable ranges. Sensors. 9, 2446–2469 (2009) 4. Kershner, R.: The Number of Circles Covering a Set. American Journal of Mathematics. 61(3), 65–671 (1939) 5. Fejes Tóth, L.: Covering the Plane with Two Kinds of Circles. Discrete & Computational Geometry. 13(3), 445–457 (1995) 6. Böröczky, K. Jr.: Finite Packing and Covering. Cambridge University Press, Cambridge (2004) 7. Ismailescu, D., Kim, B.: Packing and Covering with Centrally Symmetric Convex Disks. Discrete Comput. Geom. 51(2), 495–508 (2014) 8. Erzin, A.I., Astrakov, S.N.: Min-density stripe covering and applications in sensor net- works. In: Murgante, B. et al. (eds.) ICCSA 2011. LNCS, vol. 6784, pp. 152–162. Springer, Heidelberg (2011) 9. Astrakov, S.N., Erzin, A.I.: Efficient band monitoring with sensors outer positioning. Op- timization. 62(10), 1367–1378 (2013) 10. Erzin, A.I., Astrakov, S.N.: Covering a Plane with Ellipses. Optimization. 62(10), 1357– 1366 (2013) 11. Astrakov, S.N., Erzin, A.I.: Sensor Networks and a Strip Cover with Ellipses. Vychisl. Tekhnol. 18(2), 3-11 (2013) (in Russian) 12. Ai, J., Abouzeid, A.A.: Coverage by Directional Sensors in Randomly Deployed Wireless Sensor Networks. J. Combin. Optim. 11(1), 21–41 (2006) 13. Ma, H., Liu, Y.: Some Problems of Directional Sensor Networks. International Journal of Sensor Networks. 2(1/2), 44–52 (2007) 14. Han, X., Cao, X., Lloyd, E.L., Shen, Ch.-Ch: Deploying Directional Sensor Networks with Guaranteed Connectivity and Coverage. In: 5th Annual IEEE Communication Society Conference on Sensors, Mesh and Ad Hoc Communications and Networks, pp. 153–160. IEEE eXpress Conf. Publ., Piscataway (2008) 712 A. Erzin 15. Liu, L., Zhang, X., Ma, H.: Exposure-Path Prevention in Directional Sensor Networks Using Sector Model Based Percolation. In: IEEE International Conference on Communi- cation, pp. 274–278. IEEE eXpress Conf. Publ., Piscataway (2009) 16. Ssu, K.-F., Wang, W.-T., Wu, F,-K., Wu, T.-T.: K-Barrier Coverage with a Directional Sensing Model. Int. J. on Smart Sensing and Intelligent Systems. 2(1), 75–93 (2009) 17. Guvensan, M.A., Yavuz, A.G.: On Coverage Issues in Directional Sensor Networks: A Survey. Ad Hoc Networks. 9(7), 1238–1255 (2011) 18. Deshpande, N., Shaligram, A.: Energy Saving in WSN with Directed Connectivity. Wire- less Sensor Networks. 5(6), 121–125 (2013) 19. Mohamadi, H., Salleh, S., Razali, M.N.: Heuristic methods to maximize network lifetime in directional sensor networks with adjustable sensing ranges. J. of Network and Computer Applications. 46, 26–35 (2014) 20. Liang, C.-K., Lo, Y.-S.: A Deployment Scheme Based Upon Virtual Force for Directional Sensor Networks. Sensors & Transducers. 194(11), 35–41 (2015) 21. Erzin, A.I., Shabelnikova, N.A.: Sensor Networks and Optimal Regular Covering of the Plane with Equal Sectors. Book Series: AER-Advances in Engineering Research. 15, 415– 417 (2015) 22. Erzin, A.I., Shabelnikova, N.A.: On the Density of a Strip Cover with Identical Sectors. J. of Applied and Industrial Mathematics. 9(4), 461–468 (2015)