# Node Placement for Long Bounded Belt Complete 2-Coverage in Wireless Sensor Networks

Authors: Tingting Wang; Yanjing Sun; Zhao Xu; Wenyan Zhai; Ran Zhuo
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Based on Isosceles Triangle (Iso-Tri) placement and the extended Equalization Strip theory, we propose an Isosceles Trapezoid complete 2-coverage (Iso-TraC2) placement method for completely covering a long bounded belt area, which requires that any point within the belt is covered by at least two nodes. Coverage density and coverage efficiency are calculated to evaluate the degree of complete coverage, which can reflect the number of nodes needed and the degree of redundancy, respectively. The extreme ratio of sensing radius to belt width is deduced when the coverage density reaches the minimal value. Results demonstrate that when a belt with widthw is given, the node sensing radius r had better satisfied w<r<2w to guarantee a higher coverage efficiency and lower coverage density for bounded belt compete coverage. Mathematical analysis shows that the proposed method performs better than the existing ones with smaller nodes number and less coverage redundancy.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are currently concerned in a variety of applications dealing with monitoring, control, and surveillance [1, 2]. For instance, multifunctional sensors have been deployed at predetermined locations within the highway, subway, railway, or even a coal mine tunnel for security management, such as environment monitoring and vehicle localization and velocity measurement [3]. These regions are usually kilometers long, but only a few meters to tens of meters wide. And we only consider the coverage within the long bounded channel because the area covered by sensors outside of the bound is useless. In this paper, this kind of channel which is narrow and long is abstracted as long bounded belts from the engineering viewpoint. In order to fully exploit the monitoring capabilities of networks, deterministic deployment has been designed to deploy sensor nodes over a long bounded belt area for complete k-coverage [4–6], which requires that any point within the region is covered by at least k nodes. Network coverage is the key to reflect how the interesting region is apperceived [7]. Finding an optimal node placement strategy that has invulnerability to node failures, minimizes cost, and provides a high degree of coverage with network connectivity is extremely challenging [8].In this paper, we investigate the optimal node deployment for complete belt 2-coverage. Once there is a coverage hole caused by battery exhaustion, sensor networks will break down when WSN is under 1-coverage. Therefore redundant coverage supplied by multicoverage placement method can promote the robustness of networks connectivity, while too much redundancy will cause energy dissipation [9]. Hence, complete 2-coverage for a long bounded belt is considered in this paper, and it requires that any point within the region should be covered by at least two nodes. Here disc sensing model is adopted to describe the sensing range and monitoring capability of sensor node. The area covered by each node is assumed to be a disc centered at itself with a sensing radius r.In existing node deployment methods [4–6, 10, 11], sensor nodes are commonly deployed along center line of long belt. Actually, sensor nodes should be placed along two sides of the subway or railway instead of center line, for there are vehicles passing through. Several strip-based node placements are designed to cover long belt region under the condition that sensing radius is much smaller than width of region. Meanwhile the radius r of a sensor node is much larger than the width w of bounded belt area in many cases. For example, the standard width of a six-lane highway in both directions is 25 meters, the width of coal mine tunnel is about 5 meters [10], and the tunnel excavation diameter of Nanjing Yangtze River highway is only 15 meters. Nowadays the coverage radius of sensor node in WSNs varies from dozens to hundreds of meters, which is larger than width of belt channel. Research on sensor nodes placement for bounded belt when the sensing radius r is larger than the belt width w is only mentioned in [3, 11]. Although Fang and Chen [11] propose Isosceles Triangle once and twice coverage placement methods for tunnel complete coverage with lower coverage redundancy than Square and Hexagon coverage models [9], the cost of 3-coverage redundancy can be further reduced.In this paper, we put forward the complete 2-coverage problem based on disc sensing model for long bounded belt in WSNs. Our contributions are as follows. First, an explicit coverage model under the condition that node sensing radius is larger than belt width is proposed to depict the situation in real case, such as highways, subways, and underground coal mine tunnels. After that we evaluate the Isosceles Triangle placement for belt complete 1-coverage. Before this paper, we obtained the concept of Triangle 1-coverage deployment in [11], but it has not been quantified yet. Then we propose the Isosceles Trapezoid complete 2-coverage deployment method based on Equalization Strip-based theory, which guarantees that every target within the belt region can be monitored by at least two sensors with smaller number of sensors and less redundancy than existing ones. Thirdly, in the particular case of r/w=2/3, our Iso-TraC2 placement can provide another novel solution besides “three-disk overlap” solution [12] in constructing 2-coverage honeycomb grid lattice for large area coverage problem.The rest of the paper is organized as follows. Section2 introduces related works. Section 3 describes preliminary definitions. Section 4 presents our placement method. Then performance evaluation and analysis are presented in Section 5. Finally, Section 6 concludes the paper.


## 2. Related Works

In this section, we summarize existing works on node placement methods for complete coverage in WSN, particularly those strip-based placement methods and those for long bounded belt coverage like tunnels.Coverage reflects surveillance capability provided by sensor networks. According to difference objects to be covered, static coverage can be categorized as point coverage, barrier coverage, and area coverage [13–15]. For area coverage, any point in the service area must be covered by at least one node. For point coverage, several discretely located points are needed to be covered, and for barrier coverage, any moving target should be monitored whichever path it comes through. When WSN is used in a long bounded belt field, the field should be entirely covered to maintain the connectivity of wireless communication or supply wireless network access to equipment. Huang and Tseng [16] propose a multicoverage placement requiring that every point in the service area of the sensor network is covered by at least k sensors, where k is a predefined value. Also multiconnection proposed by k-coverage can be applied in scenarios which impose more stringent fault-tolerant capability. Otherwise too much redundancy supplied by multicoverage placement will cause energy dissipation [17]. Hence, some efficient coverage placement strategies need to be put forward for energy conservation and cost saving in WSNs.It is known that the optimal node placement for very large plane coverage without boundary effect has been proven to be the Regular Triangle lattice pattern in Figure1(a), which can achieve the lowest node density for complete 1-coverage [18]. For 2-coverage, Browna et al. [12] propose “three-disk overlap” solutions by taking three-disk overlap as a unit in covering progress, and the disk centers constitute a honeycomb-like structure. In this 2-coverage placement, the width of belt area covered by one overlap unit is equal to 2r. Therefore it is not suitable to be taken directly into long and narrow belt coverage in case of r>w; that is, the sensing radius is larger than the belt width.Figure 1
Three common placement methods. (a) Regular Triangle pattern. (b) Equ-Strip pattern. (c) Square placement pattern. (d) Iso-TriC1 pattern. (e) Iso-TriC2 pattern.Recently, some researchers have proposed new strip-based placement patterns for guaranteeing both coverage and connectivity [4–6, 19, 20]. In strip-based deployment methods, nodes are first placed as horizontal strips, and then strips are placed one by one to provide complete coverage [19, 20]. In order to completely cover a long belt, Wang et al. proposed Equalization Strip placement method and Divide-into-Rows method in [4, 6], respectively. In Equalization Strip placement method, a belt with height H is first divided into k equal subbelts by (k-1) lines parallel along the longer side of the belt, and one strip is placed in each subbelt such that the strip center line is on the bisector of this subbelt with a given strip disk distance. In [4], Wang et al. extend their study of optimal node placement pattern to Divide-and-Cover placement method which combines Regular Triangle [21] node placement method with the theory of Equalization Strip (Equ-Strip) [5], shown in Figure 1(b). In Divide-and-Cover method, the belt is divided into many subbelts which are parallel to belt long side. Each subbelt is then covered by placing equal strip on the center line of subbelt with a given strip distance, and the width w of each subbelt should be less than 2r, that is, twice of sensing radius r. In the case w<r, the pattern combining Equ-Strip placement and Reg-Tri placement is optimal when nodes’ distance is 3r. And it is better than the square placement pattern in Figure 1(c) with smaller number of nodes [22]. In node placement patterns mentioned above, sensor nodes are all deployed inside the region to be covered. The nodes in a row being paced along the centerline of subbelt can achieve a maximum coverage range. However, there are usually vehicles passing through the long bounded belt region which could be a highway, a subway, a railway, and even a coal mine tunnel. To solve this problem, we propose a novel node deployment method that aims at complete 2-coverage for bounded belt region in the context of engineering application.Nowadays research on node placement in such a bounded belt area for both coverage and localization has attracted some attention [3, 10, 11]. In case the radius r of a sensor node is larger than the width w of bounded belt area, the Isosceles Triangle 1-coverage (Iso-TriC1) placement and Isosceles Triangle 2-coverage (Iso-TriC2) placement methods shown in Figures 1(d) and 1(e), respectively, are proposed for completely covering a tunnel field [11], in which each three adjacent nodes form a triangle. Ding et al. [3] propose three patterns including grid placement consisting of two lines of anchor nodes, random mesh placement, and their hybrid placement pattern. But these placement patterns have larger node densities than the Iso-Tri pattern in which nodes are placed along two sides of belt. Wang et al. [23] propose two placements of anchor nodes: one is placing a row of anchor nodes along the centerline of tunnel; another is placing two rows of anchors along the two sides of tunnel. Experimental results show that the energy consumption in the second pattern is lower than the first one by 35% in wireless positioning process. From the above, we can say that the placement methods of putting nodes along the two sides of tunnels present a better performance than others.In this paper, we expect that our placement can not only completely cover the belt region but also minimize the total number of sensors needed.


## 3. Preliminaries

The solutions to coverage issues in WSNs involve a lot of basic theories and assumptions. In this section, we describe the bounded belt plane in 2-dimension, sensing models, sensor node properties, Equalization Strip theory and Iso-Tri strip, and the evaluation metrics of coverage quality. The bounded belt is considered as a rectangular region with lengthL and width w, and L≫w. Each sensor node is assumed to be able to cover a disk area centered at itself with a radius r of its sensing range. All the nodes are homogeneous with the identical sensing radius. All the works in the following paper are taken under the assumption of r>w; that is, the sensing radius r is larger than the belt width w.


### 3.1. Models

#### 3.1.1. Bounded Belt Model

Those areas whose length is much larger than width are often abstracted as long bounded belt from the engineering viewpoint, such as a highway, a railway, a subway, and a coal mine tunnel, shown in Figure2(a). The long belt is assumed to be a bounded rectangular zone with area A, length L, and width w. There are A=L×w and L≫w. As a subway, its 2-dimensional middle plane can also be considered as a bounded rectangular zone. Even in an underground tube, research on characteristics of electromagnetic propagation shows that horizontally polarized wave reflected on the side walls of tunnel plays a leading role in electromagnetic wave propagation. Huo et al. [24] also demonstrate that electromagnetic wave modes are easier to be motivated inside a tunnel, for the transmission attenuation rate is small when the antennas are placed in centerlines of the side walls; that is, they are the sides of the 2-dimensional middle plane. Thus it is reasonable to place sensor nodes along the two sides of the bounded belt instead of the centerline in traditional node placement methods.Figure 2
(a) Long bounded belt 2D model. (b) Disk sensing model.
(a)
(b)


#### 3.1.2. Sensing Model

Disc sensing model is adopted to describe the sensing range of sensor node. Each node is assumed to cover a disk area centered at itself with an identical radiusr, shown in Figure 2(b). A target point can be monitored only if the Euclidean distance between sensor and a target is smaller than the radius r of sensing range.


### 3.2. Node Properties

The bounded belt region is considered as a rectangular zone with lengthL, width w, and area A, where A=L×w and L≫w. In this paper, we place all nodes along two sides of the belt. To completely cover a belt area, at least N nodes are needed.Definition 1.
Coverage density [4] is defined as the ratio of the sum of area covered by each node to the area of the region:(1)ρ=Nπr2A,ρ>1.Here,N is the number of nodes within the region, and Nπr2 is the sum of the area covered by all nodes. If a node placement method can provide complete coverage, which means that any point in target region is covered by at least one node, the coverage ratio is 100%, and coverage density satisfies ρ>1. Less coverage density implies more efficient nodes’ usage. Finding an optimal node placement for bounded belt complete coverage is to minimize the number of nodes needed. According to formula (1), when r and A are constant, minimizing N is obviously equivalent to minimizing ρ.Definition 2.
Coverage efficiency is defined as the ratio of the union area to the sum of area covered by each node in the region. It is defined by(2)η=⋃i=1⋯NSi∑i=1NSi,η<1.HereSi denotes the area covered by each node within the belt region. The union of area is the efficient coverage area, which is the coverage area that is overlapping coverage zone subtracted from the complete coverage area. The sum of area is the area covered by nodes within the target region. When in complete coverage, considering both coverage region and energy consuming, coverage efficiency reflects the degree of overlap. When it is low, it means that there is too much overlap. It is known that redundant overlap will cause waste of energy dissipated in sensing progress and will increase the cost of network placement. The coverage efficiency η is the higher the better, but it is always smaller than 1.Definition 3 (adjacent distance and offset distance [5]).
The adjacent distanced is defined as the vertical distance along the length of the strip between any two adjacent nodes in each strip, and 0<d≤2r. Deploy two strips of nodes along two sides parallel to each other. The offset distance φ of the two strips is defined as the smaller vertical distance along length of belt between any two adjacent nodes in different strips, and 0<φ≤d/2 [5].Definition 4 (Isosceles Triangle (Iso-Tri) strip).
It is a string of identical disks placed along the direction of belt length with the vertical node distanced, and each three centers of adjacent nodes compose an Isosceles Triangle.


### 3.3. Equalization Strip Theory

In Equ-Strip placement [4], strips are placed parallel to the long side of the belt region with proper adjacent distance d and offset distance φ. A (d,r)-strip is a string of identical disks placed in a line along the length of belt with the distance d between the centers of any two adjacent disks and requiring 0<d<2r to guarantee the network connectivity. Each string which consists of homogeneous disks is considered as a unit for belt region coverage. The nodes placements deployed based on Equ-Strip theory with (d,r)-strips for once and twice complete coverage are illustrated in the following.Assumingr>w, in Equipartition strip 1-coverage (Equ-StripC1) placement, one (d,r)-strip is placed along the side of belt to achieve complete coverage, shown in Figure 3(a). The distance d between adjacent nodes is(3)dequ_strip=2r2-w2,r>w.Figure 3
Equ-Strip: (a) 1-coverage deployment with one(d,r)-strip, (b) 2-coverage placement with two (d,r)-strips, equal to Iso-TriC2.
(a)
(b)In Equipartition strip 2-coverage (Equ-StripC2) placement which equals the Isosceles Triangle 2-coverage (Iso-TriC2) placement in [11], shown in Figure 3(b), two strips are placed parallel to each other and keep apart with distance d=w, and the offset distance φ is(4)φequ_strip=r2-w2,r>w.Based on Equ-Strip theory above, also we can consider the Iso-Tri strip in Definition4 as a whole in coverage. Equ-Strip theory is expanded to achieve belt complete coverage by using equal Iso-Tri strips, instead of (d,r)-strips. We then propose a placement for 2-coverage by placing two Iso-Tri strips parallel along the sides of bounded belt region in Section 4.


## 3.1. Models

### 3.1.1. Bounded Belt Model

Those areas whose length is much larger than width are often abstracted as long bounded belt from the engineering viewpoint, such as a highway, a railway, a subway, and a coal mine tunnel, shown in Figure2(a). The long belt is assumed to be a bounded rectangular zone with area A, length L, and width w. There are A=L×w and L≫w. As a subway, its 2-dimensional middle plane can also be considered as a bounded rectangular zone. Even in an underground tube, research on characteristics of electromagnetic propagation shows that horizontally polarized wave reflected on the side walls of tunnel plays a leading role in electromagnetic wave propagation. Huo et al. [24] also demonstrate that electromagnetic wave modes are easier to be motivated inside a tunnel, for the transmission attenuation rate is small when the antennas are placed in centerlines of the side walls; that is, they are the sides of the 2-dimensional middle plane. Thus it is reasonable to place sensor nodes along the two sides of the bounded belt instead of the centerline in traditional node placement methods.Figure 2
(a) Long bounded belt 2D model. (b) Disk sensing model.
(a)
(b)


### 3.1.2. Sensing Model

Disc sensing model is adopted to describe the sensing range of sensor node. Each node is assumed to cover a disk area centered at itself with an identical radiusr, shown in Figure 2(b). A target point can be monitored only if the Euclidean distance between sensor and a target is smaller than the radius r of sensing range.


## 3.1.1. Bounded Belt Model

Those areas whose length is much larger than width are often abstracted as long bounded belt from the engineering viewpoint, such as a highway, a railway, a subway, and a coal mine tunnel, shown in Figure2(a). The long belt is assumed to be a bounded rectangular zone with area A, length L, and width w. There are A=L×w and L≫w. As a subway, its 2-dimensional middle plane can also be considered as a bounded rectangular zone. Even in an underground tube, research on characteristics of electromagnetic propagation shows that horizontally polarized wave reflected on the side walls of tunnel plays a leading role in electromagnetic wave propagation. Huo et al. [24] also demonstrate that electromagnetic wave modes are easier to be motivated inside a tunnel, for the transmission attenuation rate is small when the antennas are placed in centerlines of the side walls; that is, they are the sides of the 2-dimensional middle plane. Thus it is reasonable to place sensor nodes along the two sides of the bounded belt instead of the centerline in traditional node placement methods.Figure 2
(a) Long bounded belt 2D model. (b) Disk sensing model.
(a)
(b)


## 3.1.2. Sensing Model

Disc sensing model is adopted to describe the sensing range of sensor node. Each node is assumed to cover a disk area centered at itself with an identical radiusr, shown in Figure 2(b). A target point can be monitored only if the Euclidean distance between sensor and a target is smaller than the radius r of sensing range.


## 3.2. Node Properties

The bounded belt region is considered as a rectangular zone with lengthL, width w, and area A, where A=L×w and L≫w. In this paper, we place all nodes along two sides of the belt. To completely cover a belt area, at least N nodes are needed.Definition 1.
Coverage density [4] is defined as the ratio of the sum of area covered by each node to the area of the region:(1)ρ=Nπr2A,ρ>1.Here,N is the number of nodes within the region, and Nπr2 is the sum of the area covered by all nodes. If a node placement method can provide complete coverage, which means that any point in target region is covered by at least one node, the coverage ratio is 100%, and coverage density satisfies ρ>1. Less coverage density implies more efficient nodes’ usage. Finding an optimal node placement for bounded belt complete coverage is to minimize the number of nodes needed. According to formula (1), when r and A are constant, minimizing N is obviously equivalent to minimizing ρ.Definition 2.
Coverage efficiency is defined as the ratio of the union area to the sum of area covered by each node in the region. It is defined by(2)η=⋃i=1⋯NSi∑i=1NSi,η<1.HereSi denotes the area covered by each node within the belt region. The union of area is the efficient coverage area, which is the coverage area that is overlapping coverage zone subtracted from the complete coverage area. The sum of area is the area covered by nodes within the target region. When in complete coverage, considering both coverage region and energy consuming, coverage efficiency reflects the degree of overlap. When it is low, it means that there is too much overlap. It is known that redundant overlap will cause waste of energy dissipated in sensing progress and will increase the cost of network placement. The coverage efficiency η is the higher the better, but it is always smaller than 1.Definition 3 (adjacent distance and offset distance [5]).
The adjacent distanced is defined as the vertical distance along the length of the strip between any two adjacent nodes in each strip, and 0<d≤2r. Deploy two strips of nodes along two sides parallel to each other. The offset distance φ of the two strips is defined as the smaller vertical distance along length of belt between any two adjacent nodes in different strips, and 0<φ≤d/2 [5].Definition 4 (Isosceles Triangle (Iso-Tri) strip).
It is a string of identical disks placed along the direction of belt length with the vertical node distanced, and each three centers of adjacent nodes compose an Isosceles Triangle.


## 3.3. Equalization Strip Theory

In Equ-Strip placement [4], strips are placed parallel to the long side of the belt region with proper adjacent distance d and offset distance φ. A (d,r)-strip is a string of identical disks placed in a line along the length of belt with the distance d between the centers of any two adjacent disks and requiring 0<d<2r to guarantee the network connectivity. Each string which consists of homogeneous disks is considered as a unit for belt region coverage. The nodes placements deployed based on Equ-Strip theory with (d,r)-strips for once and twice complete coverage are illustrated in the following.Assumingr>w, in Equipartition strip 1-coverage (Equ-StripC1) placement, one (d,r)-strip is placed along the side of belt to achieve complete coverage, shown in Figure 3(a). The distance d between adjacent nodes is(3)dequ_strip=2r2-w2,r>w.Figure 3
Equ-Strip: (a) 1-coverage deployment with one(d,r)-strip, (b) 2-coverage placement with two (d,r)-strips, equal to Iso-TriC2.
(a)
(b)In Equipartition strip 2-coverage (Equ-StripC2) placement which equals the Isosceles Triangle 2-coverage (Iso-TriC2) placement in [11], shown in Figure 3(b), two strips are placed parallel to each other and keep apart with distance d=w, and the offset distance φ is(4)φequ_strip=r2-w2,r>w.Based on Equ-Strip theory above, also we can consider the Iso-Tri strip in Definition4 as a whole in coverage. Equ-Strip theory is expanded to achieve belt complete coverage by using equal Iso-Tri strips, instead of (d,r)-strips. We then propose a placement for 2-coverage by placing two Iso-Tri strips parallel along the sides of bounded belt region in Section 4.


## 4. Equalization Strip Theory-Based Placement with Isosceles Triangle Strips

Given a bounded belt field which is initially uncovered, the complete coverage problem is desiring a placement which can cover every point in the field with the smallest number of nodes. In this section, we introduce a novel node placement method for bounded belt complete 2-coverage, based on Equalization Strip theory and Isosceles Triangle (Iso-Tri) strip, which requires that each point in the bounded belt is covered by at least 2 nodes. Assuming that the radiusr is larger than the width w of belt (r>w) and nodes in strips are placed along sides of belt, 1-coverage placement method is evaluated first. The string is not limited to (d,r)-strip, but also the Iso-Tri strip, which is considered as a unit in deployment progress. In our method, we place Iso-Tri strips parallel to the long side of the belt region with certain node distance to provide 1-coverage and 2-coverage. Some proofs are done to calculate the minimal value of coverage density, and the formulas of coverage efficiency are deduced as follows.


### 4.1. Isosceles Triangle Complete 1-Coverage Placement

As shown in Figure4, we define the 1-coverage placement using one Isosceles Triangle strip in completely covering a bounded belt field, requiring that every point within the region is covered by at least one node.Figure 4
Iso-TriC1 placement.Definition 5 (Isosceles Triangle complete 1-coverage placement (Iso-TriC1)).
If one Iso-Tri strip is used for bounded belt complete coverage, each three adjacent sensors compose Isosceles Triangle, shown in Figure4. The centers of disks are placed along two sides of belt, and adjacent disks are put in different sides and keep apart from each other with distance d. To keep the connectivity of networks in Iso-TriC1 placement, communication radius R should be bigger than twice of sensing radius r, which is R≥2r.Lemma 6.
If the Iso-Tri strip placement is used for a belt with widthw achieving complete 1-coverage, when the ratio w/r is r/w=2/3 and the distance is diso-triC1=1.5r, one can get the minimum value of coverage density, which is ρiso-triC1_min=0.7π.Proof.
In the Iso-TriC1 placement, an Iso-Tri strip is used for a belt with widthw achieving complete 1-coverage. The centers of each three adjacent disks constitute an Isosceles Triangle, shown in Figure 4. When achieving complete coverage, the distance d between two adjacent disks along the length of belt is(5)diso-triC1=r+r2-w2.Since each disk is able to cover an area with length diso-triC1, to cover the whole area with length L, about N nodes are needed; we have L=N×diso-triC1. Then the number of nodes can be calculated by(6)Niso-triC1=Lr+r2-w2.According to Definition 1, and A=L×w, after taking the approximation L=N×diso-triC1 into (1), we can get the expression of coverage density in Iso-TriC1 placement, as follows:(7)ρiso-triC1=Nπr2A=πr2wr+r2-w2=πr/w2r/w+r/w2-1.In order to get the minimal ρiso-triC1, the extreme ratio r/w can be computed by its derived function, which is (8)dπr/w2/r/w+r/w2-1dr/w=0,rw>1.Then we can get the extreme value r/w, which is(9)rw=23.After taking (9) into (7), we can get (10)ρiso-triC1_min=4π33≈0.77π.Therefore, we obtain the fact that the coverage density by Iso-TriC1 placement is about 0.77π. The proof which refers to Lemma 6 has been done.Lemma 7.
When one uses an Iso-TriC1 placement pattern, the distanced between two adjacent disks along the length of belt is diso-triC1=r+r2-w2, r>h. Supposing that r/w=x, coverage efficiency can be calculated. When the coverage density achieves minimum value, coverage efficiency is ηiso-triC1=91%.Proof.
In Iso-TriC1 placement, one strip is enough to achieve belt complete coverage whenr>w. According to Definition 2, the coverage efficiency can be computed by(11)ηiso-triC1=⋃i=1⋯NSi∑i=1NSi=N×πr2/2-N×So1-2N-1So2N×πr2/2-N×So1=1-2So2-2So2/Nπr2/2-So1.Here, So1 is the area covered by each node outside of belt region, and So2 is the overlapping areas which have been marked out with black color in Figure 5. The areas So1 and So2 can be calculated by cutting the Isosceles Triangle area from the sector. The angles α and β are half of the center angles in the corresponding sectors, which can be calculated by (12). According to d=r+r2-w2, we get(12)So1=αr2-12w×r2-w2,α=arcsin⁡r2-w2r,So2=βr2-rw2,β=arcsin⁡w2r2+2rr2-w2.Supposing N→∝, we have limN→∞⁡(2So2/N)=0. Thus the efficiency can be approximated as(13)limN→∞⁡ηiso-triC1≅1-2So2πr2/2-So1.Supposing r/w=x, taking (12) into (13), we can get(14)ηiso-triC1=1-4x2arcsin⁡1-x2-1/2x-2xπx2-2x2arcsin⁡1-1/x2+2x2-1Herex>1.When the coverage density of Iso-TriC1 placement achieves minimum value, we have x=2√3/3 in (9). After taking (9) into (14), we get ηiso-triC1≈91%. Therefore, we obtain the fact that the coverage efficiency by Iso-TriC1 placement is about 91%. The proof which refers to Lemma 7 has been done.Figure 5
AreasSo1 and So2 in Iso-Tri placement pattern.


### 4.2. The Proposed Isosceles Trapezoid Complete 2-Coverage Placement

Based on Equalization Strip theory, we place two Iso-Tri strips parallel to the long side of belt for complete 2-coverage and keep a certain distancew, shown in Figure 6.Figure 6
The Iso-TraC2 pattern with two Iso-Tri strips.Definition 8 (Isosceles Trapezoid complete 2-coverage (Iso-TraC2) placement).
In this placement, two Iso-Tri strips are placed parallel to each other, keeping apart with a distanced=w and offset distances φ1 and φ2; each four centers of adjacent disks constitute an Isosceles Trapezoid pattern. We call this method Iso-TraC2 placement pattern, which can distinguish Iso-TraC2 from Iso-TriC2. In this placement method, every point in the belt field is covered by at least two sensors. When achieving complete 2-coverage, the offset distances φ1 and φ2 are(15)φ1=2r,φ2=2r2-w2,r>w.When communication radiusR is bigger than twice of sensing radius r, which is R>2r, the network in Iso-TraC2 placement can achieve a higher connectivity requirement (up to 3-connectivity). A sensor network is said to be 3-connected if for every two interior nodes of N, there are at least three node disjoint paths joining them.Lemma 9.
If the Iso-TraC2 pattern is used for belt complete 2-coverage, when the ratiow/r is r/w=2/3 and the smaller offset distance is φ2=r, one gets the minimum value of coverage density, which is ρiso-traC2_min=1.54π.Proof.
In the Iso-TraC2 placement pattern, two Iso-Tri strips are parallel to the length of belt and keep apart with a distanced=w for complete 2-coverage. The centers of every four adjacent disks constitute an Isosceles Trapezoid. We define the four adjacent disks as an Isosceles Trapezoid unit. An isosceles trapezium shape is an inhomogeneous model because the distances between adjacent disks are not always the same. According to Figure 6, the expression of offset distances φ1 and φ2 can be expressed by (16)φ1=2r,φ2=2r2-w2.Each unit can completely cover a belt area twice with length diso-traC2, which is(17)diso-traC2=φ1+φ2=r+r2-w2.To guarantee a bounded belt with length L being completely covered twice, the number of disks needed is(18)Niso-traC2=Ldiso-traC2×4=2Lr+r2-w2.Supposing that the number of isosceles trapezium units is m, we can get the number of disks; that is, Niso-traC2=4m. According to Definition 1 in (1), and A=L×w, after taking the approximation L=m×So2 and Niso-traC2=4m into (1), we can get the expression of coverage density in Iso-TriC2 pattern, as follows:(19)ρiso-traC2=Nπr2A=4mπr2mdiso-traC2w=2πr2wr+r2-w2=2πr/w2r/w+r/w2-1.To minimize ρiso-traC2, we can work out the minimum value at extreme value r/w by its derived function, which can be computed by (20)d2πr/w2/r/w+r/w2-1dr/w=0,rw>1.Thus the extreme value r/w is(21)rw=23.In case of that, the smaller offset distance φ2 between two Iso-Tri strips is(22)φ2=r.Taking (21) into (19), we can get (23)ρiso-traC2_min=8π33≈1.54π.Therefore, we obtain the fact that the coverage density by Iso-TraC2 placement is about 1.54π. The proof which refers to Lemma 9 has been done.Lemma 10.
In Iso-TraC2 placement pattern, two Iso-Tri strips are parallel along the length of belt for complete 2-coverage; the offset distanceφ between two strips is φ=r, r>w. Supposing that r/w=x, coverage efficiency can be calculated. When the coverage density of Iso-TraC2 placement gets minimum value, coverage efficiency is ηiso-traC2=37%.Proof.
In Iso-TraC2 placement, two Iso-Tri strips are parallel along two sides of the belt region with offset distanceφ2=r, when r>w.
According to Definition2, the coverage efficiency in Iso-TraC2 placement can be computed by(24)ηiso-traC2=⋃i=1⋯NSi∑i=1NSi=N/2×πr2/2-So1-2N-1So2N×πr2/2-N×So1=12-2So2-2So2/Nπr2/2-So1.Here, So1 is the area covered by each node outside of belt region, and So2 is the overlapping areas. The areas So1 and So2 can be calculated by cutting the Isosceles Triangle area from the sector, which can be calculated by (12).
WhenN→∝, the efficiency can be approximated to the following formula:(25)limN→∞⁡ηiso-traC2≅12-2So2πr2/2-So1.Supposing that r/w=x, taking (12) into (24), we can get(26)ηiso-traC2=12-4x2arcsin⁡1-x2-1/2x-xπx2-2x2arcsin⁡1-1/x2+2x2-1x>1.When the coverage density of Iso-TriC1 placement achieves minimum value, we got r/w=2/√3 in (21). After taking it into (26), we get ηiso-traC2=37%. Therefore, we obtain that the coverage efficiency by Iso-TraC2 placement is about 37%. The proof which refers to Lemma 10 has been done.


### 4.3. Isosceles Trapezoid Overlap Solution of Honeycomb Grid Lattice 2-Coverage

In this section, we deploy our Isosceles Trapezoid solution into unbounded region for 2-coverage.Whenr/w=2/√3, the Isosceles Triangle unit can be a solution of honeycomb grid structure for 2-coverage.Proof.
Suppose that(27)O2A-=w,O1O3-=O2O4-=r,O3B-=O4B-=r,O2A⊥O4B.Once r/w=2/√3, as shown in Figure 7(a), we have(28)O2O4-O2A-=23.In Rectangular Triangle O2AO4, we get(29)sin∠O2O4A=32.Then we have (30)arcsin∠O2O4A=π3,∠O2O4A=60°.It is known from (30) and the supposition O2O4-=BO4-=r that triangle O2BO4 is Regular Triangle. In the same way, triangle O1BO3 can be proved to be Regular Triangle too. We have O1B=O2B=r, and ∠O1BO3=∠O2BO4=60°. And we can calculate that ∠O1BO2=180°-∠O1BO3-∠O2BO4=60°. From the above, we can deduce that triangle O1BO2 is a Regular Triangle, and O1O2-=r. Consider(31)O3O1-=O1O2-=O2O3-=O3O4-.When a number of nodes deployed in Isosceles Triangle overlap solution to completely cover an unbounded area twice, each six adjacent nodes can consist of an equilateral hexagon which is called honeycomb grid lattice. In summary, our Iso-TraC2 placement proposes another novel solution besides “three-disk overlap” solution [12] in constructing 2-coverage honeycomb grid lattice only when r/w=2/√3.Figure 7
(a) Isosceles Trapezoid overlap solution. (b) Honeycomb grid lattice.
(a)
Isosceles Trapezoid overlap solution
(b)
Honeycomb grid lattice


## 4.1. Isosceles Triangle Complete 1-Coverage Placement

As shown in Figure4, we define the 1-coverage placement using one Isosceles Triangle strip in completely covering a bounded belt field, requiring that every point within the region is covered by at least one node.Figure 4
Iso-TriC1 placement.Definition 5 (Isosceles Triangle complete 1-coverage placement (Iso-TriC1)).
If one Iso-Tri strip is used for bounded belt complete coverage, each three adjacent sensors compose Isosceles Triangle, shown in Figure4. The centers of disks are placed along two sides of belt, and adjacent disks are put in different sides and keep apart from each other with distance d. To keep the connectivity of networks in Iso-TriC1 placement, communication radius R should be bigger than twice of sensing radius r, which is R≥2r.Lemma 6.
If the Iso-Tri strip placement is used for a belt with widthw achieving complete 1-coverage, when the ratio w/r is r/w=2/3 and the distance is diso-triC1=1.5r, one can get the minimum value of coverage density, which is ρiso-triC1_min=0.7π.Proof.
In the Iso-TriC1 placement, an Iso-Tri strip is used for a belt with widthw achieving complete 1-coverage. The centers of each three adjacent disks constitute an Isosceles Triangle, shown in Figure 4. When achieving complete coverage, the distance d between two adjacent disks along the length of belt is(5)diso-triC1=r+r2-w2.Since each disk is able to cover an area with length diso-triC1, to cover the whole area with length L, about N nodes are needed; we have L=N×diso-triC1. Then the number of nodes can be calculated by(6)Niso-triC1=Lr+r2-w2.According to Definition 1, and A=L×w, after taking the approximation L=N×diso-triC1 into (1), we can get the expression of coverage density in Iso-TriC1 placement, as follows:(7)ρiso-triC1=Nπr2A=πr2wr+r2-w2=πr/w2r/w+r/w2-1.In order to get the minimal ρiso-triC1, the extreme ratio r/w can be computed by its derived function, which is (8)dπr/w2/r/w+r/w2-1dr/w=0,rw>1.Then we can get the extreme value r/w, which is(9)rw=23.After taking (9) into (7), we can get (10)ρiso-triC1_min=4π33≈0.77π.Therefore, we obtain the fact that the coverage density by Iso-TriC1 placement is about 0.77π. The proof which refers to Lemma 6 has been done.Lemma 7.
When one uses an Iso-TriC1 placement pattern, the distanced between two adjacent disks along the length of belt is diso-triC1=r+r2-w2, r>h. Supposing that r/w=x, coverage efficiency can be calculated. When the coverage density achieves minimum value, coverage efficiency is ηiso-triC1=91%.Proof.
In Iso-TriC1 placement, one strip is enough to achieve belt complete coverage whenr>w. According to Definition 2, the coverage efficiency can be computed by(11)ηiso-triC1=⋃i=1⋯NSi∑i=1NSi=N×πr2/2-N×So1-2N-1So2N×πr2/2-N×So1=1-2So2-2So2/Nπr2/2-So1.Here, So1 is the area covered by each node outside of belt region, and So2 is the overlapping areas which have been marked out with black color in Figure 5. The areas So1 and So2 can be calculated by cutting the Isosceles Triangle area from the sector. The angles α and β are half of the center angles in the corresponding sectors, which can be calculated by (12). According to d=r+r2-w2, we get(12)So1=αr2-12w×r2-w2,α=arcsin⁡r2-w2r,So2=βr2-rw2,β=arcsin⁡w2r2+2rr2-w2.Supposing N→∝, we have limN→∞⁡(2So2/N)=0. Thus the efficiency can be approximated as(13)limN→∞⁡ηiso-triC1≅1-2So2πr2/2-So1.Supposing r/w=x, taking (12) into (13), we can get(14)ηiso-triC1=1-4x2arcsin⁡1-x2-1/2x-2xπx2-2x2arcsin⁡1-1/x2+2x2-1Herex>1.When the coverage density of Iso-TriC1 placement achieves minimum value, we have x=2√3/3 in (9). After taking (9) into (14), we get ηiso-triC1≈91%. Therefore, we obtain the fact that the coverage efficiency by Iso-TriC1 placement is about 91%. The proof which refers to Lemma 7 has been done.Figure 5
AreasSo1 and So2 in Iso-Tri placement pattern.


## 4.2. The Proposed Isosceles Trapezoid Complete 2-Coverage Placement

Based on Equalization Strip theory, we place two Iso-Tri strips parallel to the long side of belt for complete 2-coverage and keep a certain distancew, shown in Figure 6.Figure 6
The Iso-TraC2 pattern with two Iso-Tri strips.Definition 8 (Isosceles Trapezoid complete 2-coverage (Iso-TraC2) placement).
In this placement, two Iso-Tri strips are placed parallel to each other, keeping apart with a distanced=w and offset distances φ1 and φ2; each four centers of adjacent disks constitute an Isosceles Trapezoid pattern. We call this method Iso-TraC2 placement pattern, which can distinguish Iso-TraC2 from Iso-TriC2. In this placement method, every point in the belt field is covered by at least two sensors. When achieving complete 2-coverage, the offset distances φ1 and φ2 are(15)φ1=2r,φ2=2r2-w2,r>w.When communication radiusR is bigger than twice of sensing radius r, which is R>2r, the network in Iso-TraC2 placement can achieve a higher connectivity requirement (up to 3-connectivity). A sensor network is said to be 3-connected if for every two interior nodes of N, there are at least three node disjoint paths joining them.Lemma 9.
If the Iso-TraC2 pattern is used for belt complete 2-coverage, when the ratiow/r is r/w=2/3 and the smaller offset distance is φ2=r, one gets the minimum value of coverage density, which is ρiso-traC2_min=1.54π.Proof.
In the Iso-TraC2 placement pattern, two Iso-Tri strips are parallel to the length of belt and keep apart with a distanced=w for complete 2-coverage. The centers of every four adjacent disks constitute an Isosceles Trapezoid. We define the four adjacent disks as an Isosceles Trapezoid unit. An isosceles trapezium shape is an inhomogeneous model because the distances between adjacent disks are not always the same. According to Figure 6, the expression of offset distances φ1 and φ2 can be expressed by (16)φ1=2r,φ2=2r2-w2.Each unit can completely cover a belt area twice with length diso-traC2, which is(17)diso-traC2=φ1+φ2=r+r2-w2.To guarantee a bounded belt with length L being completely covered twice, the number of disks needed is(18)Niso-traC2=Ldiso-traC2×4=2Lr+r2-w2.Supposing that the number of isosceles trapezium units is m, we can get the number of disks; that is, Niso-traC2=4m. According to Definition 1 in (1), and A=L×w, after taking the approximation L=m×So2 and Niso-traC2=4m into (1), we can get the expression of coverage density in Iso-TriC2 pattern, as follows:(19)ρiso-traC2=Nπr2A=4mπr2mdiso-traC2w=2πr2wr+r2-w2=2πr/w2r/w+r/w2-1.To minimize ρiso-traC2, we can work out the minimum value at extreme value r/w by its derived function, which can be computed by (20)d2πr/w2/r/w+r/w2-1dr/w=0,rw>1.Thus the extreme value r/w is(21)rw=23.In case of that, the smaller offset distance φ2 between two Iso-Tri strips is(22)φ2=r.Taking (21) into (19), we can get (23)ρiso-traC2_min=8π33≈1.54π.Therefore, we obtain the fact that the coverage density by Iso-TraC2 placement is about 1.54π. The proof which refers to Lemma 9 has been done.Lemma 10.
In Iso-TraC2 placement pattern, two Iso-Tri strips are parallel along the length of belt for complete 2-coverage; the offset distanceφ between two strips is φ=r, r>w. Supposing that r/w=x, coverage efficiency can be calculated. When the coverage density of Iso-TraC2 placement gets minimum value, coverage efficiency is ηiso-traC2=37%.Proof.
In Iso-TraC2 placement, two Iso-Tri strips are parallel along two sides of the belt region with offset distanceφ2=r, when r>w.
According to Definition2, the coverage efficiency in Iso-TraC2 placement can be computed by(24)ηiso-traC2=⋃i=1⋯NSi∑i=1NSi=N/2×πr2/2-So1-2N-1So2N×πr2/2-N×So1=12-2So2-2So2/Nπr2/2-So1.Here, So1 is the area covered by each node outside of belt region, and So2 is the overlapping areas. The areas So1 and So2 can be calculated by cutting the Isosceles Triangle area from the sector, which can be calculated by (12).
WhenN→∝, the efficiency can be approximated to the following formula:(25)limN→∞⁡ηiso-traC2≅12-2So2πr2/2-So1.Supposing that r/w=x, taking (12) into (24), we can get(26)ηiso-traC2=12-4x2arcsin⁡1-x2-1/2x-xπx2-2x2arcsin⁡1-1/x2+2x2-1x>1.When the coverage density of Iso-TriC1 placement achieves minimum value, we got r/w=2/√3 in (21). After taking it into (26), we get ηiso-traC2=37%. Therefore, we obtain that the coverage efficiency by Iso-TraC2 placement is about 37%. The proof which refers to Lemma 10 has been done.


## 4.3. Isosceles Trapezoid Overlap Solution of Honeycomb Grid Lattice 2-Coverage

In this section, we deploy our Isosceles Trapezoid solution into unbounded region for 2-coverage.Whenr/w=2/√3, the Isosceles Triangle unit can be a solution of honeycomb grid structure for 2-coverage.Proof.
Suppose that(27)O2A-=w,O1O3-=O2O4-=r,O3B-=O4B-=r,O2A⊥O4B.Once r/w=2/√3, as shown in Figure 7(a), we have(28)O2O4-O2A-=23.In Rectangular Triangle O2AO4, we get(29)sin∠O2O4A=32.Then we have (30)arcsin∠O2O4A=π3,∠O2O4A=60°.It is known from (30) and the supposition O2O4-=BO4-=r that triangle O2BO4 is Regular Triangle. In the same way, triangle O1BO3 can be proved to be Regular Triangle too. We have O1B=O2B=r, and ∠O1BO3=∠O2BO4=60°. And we can calculate that ∠O1BO2=180°-∠O1BO3-∠O2BO4=60°. From the above, we can deduce that triangle O1BO2 is a Regular Triangle, and O1O2-=r. Consider(31)O3O1-=O1O2-=O2O3-=O3O4-.When a number of nodes deployed in Isosceles Triangle overlap solution to completely cover an unbounded area twice, each six adjacent nodes can consist of an equilateral hexagon which is called honeycomb grid lattice. In summary, our Iso-TraC2 placement proposes another novel solution besides “three-disk overlap” solution [12] in constructing 2-coverage honeycomb grid lattice only when r/w=2/√3.Figure 7
(a) Isosceles Trapezoid overlap solution. (b) Honeycomb grid lattice.
(a)
Isosceles Trapezoid overlap solution
(b)
Honeycomb grid lattice


## 5. Performance Evaluation and Analysis

In this section, we compare our node placement methods with Equalization Strip placement methods. In case of complete coverage, we use coverage density in (1) and coverage efficiency in (2) to evaluate the performance of placement methods. Coverage density indicates the area in covering per unit area. Thus minimizing the number of nodes is equivalent to minimizing the coverage density. When the size of belt is given, the minimal coverage density and the threshold radius can be calculated. Coverage efficiency can reflect the degree of overlap. It is an indicator of measuring the energy utilization of networks.


### 5.1. Performance Evaluation

Figures8 and 9 display the coverage density ρ and coverage efficiency η versus different r/w. When a bounded belt is given, the width w is constant. The node sensing range can be selected according to our results to achieve complete coverage with minimal coverage density. From Figures 8 and 9, we make the following conclusion.Figure 8
Coverage densityρ versus r/w.Figure 9
Coverage efficiencyη versus r/w.Figure8 shows that the curves of coverage density are concave, and there must be a minimal value of coverage density in each placement pattern. When radius is larger than the extreme value, ρ gets larger when radius r of sensor’s coverage range is increasing. From the figures, we observe that the coverage density by (d,r)-strip-based placement methods is always larger than that by Iso-Tri strip-based placement methods proposed in this paper. In other words, the number of nodes needed by Iso-Tri strip-based placement methods is smaller than that needed by (d,r)-strip-based placement methods used in complete coverage of the same area.Figure9 plots the relationship between coverage efficiency and r/w by different node placement patterns. It is shown that, after normalizing w, coverage efficiency η is a monotone increasing function to sensing radius r. However it is different from coverage density; coverage efficiency converges in each placement pattern when r is increasing. Although the coverage radius of node can be increased by promoting transmission power, there will be a rise in energy consumption in communication. When r>2w, the efficiencies in 2-coverage placement are getting larger slowly and both converge to 50%. It shows that half of the power is wasted. Therefore, the radius r of sensor coverage range will satisfy w<r<2w to guarantee bounded belt complete coverage width a higher efficiency and lower density. It is obvious that the coverage efficiency by Iso-Tri strip-based placement methods proposed in this paper is always higher than by (d,r)-strip-based placement methods when sensing radius is the same.We find that the expression ofρ is concave function of r/w. Thus, there is an extreme value of r/w which can minimize ρ. The minimal coverage densities are deduced by different patterns. When the belt width w is given, the extreme value of node radius r can be calculated. Comparison result of metrics at extreme values by different placement methods is shown in Table 1.Table 1
Patterns, ratior/w, ρmin⁡, and η, when r>w.
Pattern
r
/
w
ρ
m
i
n
η
Equ-StripC1
2
π
78%
Iso-TriC1
2
/
3
0.77π
91%
Equ-StripC2
2
2π
39%
Iso-TraC2
2
/
3
1.54π
37%(
1
) In Equ-StripC1 and Equ-StripC2 pattern, the coverage density is minimal when r/w=2. Similarly, in Iso-TriC1 and Iso-TraC2 pattern, the coverage densities get minimal values when r/w=2/√3. So we can conclude that an optimal 2-coverage model can be constructed by two strips of 1-coverage being shifted in a proper offset distance φ based on Equalization Strip theory. And the placement methods for 1-coverage and 2-coverage have the same ratio r/w when coverage densities achieve minimal values.(
2
) Densities in 2-coverage methods are double the densities in 1-coverage methods. It is different from Equ-Strip-based placement methods; the coverage efficiency in Iso-TraC2 placement is not an integer multiple to that in Iso-TriC1 placement. This phenomenon is caused by its asymmetric structure in Iso-Tri strip-based placement methods.(
3
) In case of 1-coverage, the minimal coverage density of Iso-TriC1 placement is about 0.77π, when r/w=2/√3. However, the minimal coverage density in Equ-StripC1 placement is π. Calculation results in Table 1 also show that the minimal coverage efficiency of Iso-TriC1 and Equ-StripC1 pattern is 91% and 78%, respectively.(
4
) In case of 2-coverage, the minimal coverage density of Iso-TraC2 patternis1.54π, while the minimal coverage density of Equ-StripC2 pattern is 2π. But figures in Table 1 show that, under the minimal coverage densities situation, the Iso-TraC2 pattern only achieves a coverage efficiency of 37%, while coverage efficiency in Equ-StripC2 pattern is 39%. Coverage density can achieve minimum value at the extreme value r/w. But the value of coverage efficiency at this extreme r/w is not optimal. From Figures 7 and 8, we can see that coverage efficiency gets better with sensing radius increasing. Therefore, to improve the performance of Iso-TraC2 placement, both coverage density and efficiency should be considered.


### 5.2. Mathematical Analysis

When the bounded belt length isL=1000 m and width is w=10 m, the number of nodes needed for area complete coverage by different placement is given in Figure 10 versus different size of sensing radius r.Figure 10
The number of nodes needed. Here the length of the belt isL=1000 m, the belt width is w=10 m, and the coverage radius of nodes varies from 10 to 50 m.Figure10 plots the relationship between the disks radius and the nodes number in each placement scheme. Figure 8 shows that the number of nodes needed by Equ-StripC1 placement is always larger than by Iso-TriC1 placement in 1-coverage, and the number of nodes needed by Equ-StripC2 placement is always larger than by the Iso-TraC2 placement proposed in this paper in 2-coverage.In order to completely cover a bounded area with lengthL=1000 m and width w=10 m, the number of nodes and coverage density and efficiency are listed in Table 2 in terms of different sensing radius r.Table 2
Metrics comparison between two methods in different radiusr.
(a)
r
=
12 m
Pattern
N
ρ
η
N
ρ
η
k
1
2
Equ-Strip
76
3.41
64%
152
6.82
32%
Iso-Tri/Iso-Tra
54
2.43
92%
108
4.86
40%
(b)
r
=
14 m
Pattern
N
ρ
η
N
ρ
η
k
1
2
Equ-Strip
51
3.14
77%
102
6.28
39%
Iso-Tri/Iso-Tra
42
2.59
95%
84
5.18
44%
(c)
r
=
20 m
Pattern
N
ρ
η
N
ρ
η
k
1
2
Equ-Strip
29
3.63
91%
58
7.26
45%
Iso-Tri/Iso-Tra
28
3.37
98%
54
6.74
48%Table2 shows that when r=12 m, Iso-TraC2 placement pattern can save 44 nodes, about 30% less than by Equ-StipC2 pattern at the extreme sensing radius of Iso-TraC2 placement pattern. When r=12 m, Iso-TraC2 placement pattern can save 18 nodes compared to Equ-StripC2 pattern at the extreme sensing radius of Equ-StripC2 placement pattern. When r=20 m, the numbers of sensor nodes required by Iso-TraC2 and Equ-StripC2 pattern are nearly the same. Although the number of nodes needed is getting fewer when sensing radius increases, the coverage density is getting larger. In order to utilize the sensors in an efficient manner for keeping coverage quality and connectivity to increase the life time of the network, we choose the sensing radius which is a little bit larger than the extreme value by considering the power limitation in specific applications.Our proposed 2-coverage placement can provide data redundancy, which can improve the reliability of data transmission. The redundancy coverage also improves the robustness of network transmission while each point within the area is covered by at least two nodes. The topology will be segmented when, and only when, the two nodes in the waist of trapezoidal unit fail at the same time. To save cost of WSN deployment, we put forward a complete 2-coverage placement with minimum coverage density. Although the Isosceles Triangle complete 2-coverage placement pattern proposed by Fang and Chen [11] has stronger antidestroying ability, the price is the 3-coverage redundancy.In summary, the Iso-TriC1 has obvious advantages compared to Equ-StripC1 placements for once complete coverage. The Iso-TraC2 placement performs better than the Equ-StripC2 which is equal to the Iso-TriC2 placement pattern in [11] for bounded belt complete 2-coverage, in terms of less sensor node, smaller coverage density, and higher coverage efficiency.


### 5.3. Other Node Placements for Belt 2-Coverage

In this section, we analyze existing node placement schemes for belt 2-coverage, including Triangle 2-coverage (TriC2) placement pattern and Rectangle 2-coverage (RecC2) placement pattern shown in Figure11. Regular Triangle placement and Square placement pattern are particular cases, respectively. It is obvious that the relation between sensing radius of sensor node and width of belt should be satisfied with r<w; otherwise it will be the same as Equ-Strip placement above. To simplify the calculation, only the case of r<w<2r is considered in this paper.Figure 11
Placement schemes for whenr<w<2r.
(a)
Triangle placement pattern
(b)
Triangle 2-coverage pattern
(c)
Rectangle placement pattern
(d)
Rectangle 2-coverage patternFigure12 plots the relationships between coverage efficiency and w/r by Triangle and Rectangle placement patterns when r<w<2r. For both patterns, the extreme values of w/r are equal for once coverage and twice coverage, respectively, which are shown in Table 3.Table 3
Patterns, ratiow/r, and η, when r<w<2r.
Pattern
w
/
r
η
TriC1
3
/
2
85%
RecC1
2
82%
TriC2
3
/
2
43%
RecC2
2
41%Figure 12
Coverage efficiency versusw/r.In order to completely cover a bounded area with lengthL=1000 m and width w=10 m, the number of nodes needed is figured out at the extreme sensing radius r, which is about 8 m, shown in Table 4.Table 4
Number of nodes needed whenr=8 m.
Pattern
Number of nodes
k
1
2
Triangle
130
260
Rectangle
161
322The number of nodes needed to completely cover the belt region by Triangle and Rectangle placements is much larger than that by our proposed method. On the one hand, the sensing radius is smaller than the belt width. On the other hand, the coverage efficiency is lower than our node deployment. In summary, the Iso-TriC1 has obvious advantages compared to existing node placements [5, 11, 18, 22] for a long bounded belt complete 2-coverage, in terms of less sensor node and higher coverage efficiency. If possible, the sensing radius of node had better be set as w<r<2w in saving cost for WSNs application.


## 5.1. Performance Evaluation

Figures8 and 9 display the coverage density ρ and coverage efficiency η versus different r/w. When a bounded belt is given, the width w is constant. The node sensing range can be selected according to our results to achieve complete coverage with minimal coverage density. From Figures 8 and 9, we make the following conclusion.Figure 8
Coverage densityρ versus r/w.Figure 9
Coverage efficiencyη versus r/w.Figure8 shows that the curves of coverage density are concave, and there must be a minimal value of coverage density in each placement pattern. When radius is larger than the extreme value, ρ gets larger when radius r of sensor’s coverage range is increasing. From the figures, we observe that the coverage density by (d,r)-strip-based placement methods is always larger than that by Iso-Tri strip-based placement methods proposed in this paper. In other words, the number of nodes needed by Iso-Tri strip-based placement methods is smaller than that needed by (d,r)-strip-based placement methods used in complete coverage of the same area.Figure9 plots the relationship between coverage efficiency and r/w by different node placement patterns. It is shown that, after normalizing w, coverage efficiency η is a monotone increasing function to sensing radius r. However it is different from coverage density; coverage efficiency converges in each placement pattern when r is increasing. Although the coverage radius of node can be increased by promoting transmission power, there will be a rise in energy consumption in communication. When r>2w, the efficiencies in 2-coverage placement are getting larger slowly and both converge to 50%. It shows that half of the power is wasted. Therefore, the radius r of sensor coverage range will satisfy w<r<2w to guarantee bounded belt complete coverage width a higher efficiency and lower density. It is obvious that the coverage efficiency by Iso-Tri strip-based placement methods proposed in this paper is always higher than by (d,r)-strip-based placement methods when sensing radius is the same.We find that the expression ofρ is concave function of r/w. Thus, there is an extreme value of r/w which can minimize ρ. The minimal coverage densities are deduced by different patterns. When the belt width w is given, the extreme value of node radius r can be calculated. Comparison result of metrics at extreme values by different placement methods is shown in Table 1.Table 1
Patterns, ratior/w, ρmin⁡, and η, when r>w.
Pattern
r
/
w
ρ
m
i
n
η
Equ-StripC1
2
π
78%
Iso-TriC1
2
/
3
0.77π
91%
Equ-StripC2
2
2π
39%
Iso-TraC2
2
/
3
1.54π
37%(
1
) In Equ-StripC1 and Equ-StripC2 pattern, the coverage density is minimal when r/w=2. Similarly, in Iso-TriC1 and Iso-TraC2 pattern, the coverage densities get minimal values when r/w=2/√3. So we can conclude that an optimal 2-coverage model can be constructed by two strips of 1-coverage being shifted in a proper offset distance φ based on Equalization Strip theory. And the placement methods for 1-coverage and 2-coverage have the same ratio r/w when coverage densities achieve minimal values.(
2
) Densities in 2-coverage methods are double the densities in 1-coverage methods. It is different from Equ-Strip-based placement methods; the coverage efficiency in Iso-TraC2 placement is not an integer multiple to that in Iso-TriC1 placement. This phenomenon is caused by its asymmetric structure in Iso-Tri strip-based placement methods.(
3
) In case of 1-coverage, the minimal coverage density of Iso-TriC1 placement is about 0.77π, when r/w=2/√3. However, the minimal coverage density in Equ-StripC1 placement is π. Calculation results in Table 1 also show that the minimal coverage efficiency of Iso-TriC1 and Equ-StripC1 pattern is 91% and 78%, respectively.(
4
) In case of 2-coverage, the minimal coverage density of Iso-TraC2 patternis1.54π, while the minimal coverage density of Equ-StripC2 pattern is 2π. But figures in Table 1 show that, under the minimal coverage densities situation, the Iso-TraC2 pattern only achieves a coverage efficiency of 37%, while coverage efficiency in Equ-StripC2 pattern is 39%. Coverage density can achieve minimum value at the extreme value r/w. But the value of coverage efficiency at this extreme r/w is not optimal. From Figures 7 and 8, we can see that coverage efficiency gets better with sensing radius increasing. Therefore, to improve the performance of Iso-TraC2 placement, both coverage density and efficiency should be considered.


## 5.2. Mathematical Analysis

When the bounded belt length isL=1000 m and width is w=10 m, the number of nodes needed for area complete coverage by different placement is given in Figure 10 versus different size of sensing radius r.Figure 10
The number of nodes needed. Here the length of the belt isL=1000 m, the belt width is w=10 m, and the coverage radius of nodes varies from 10 to 50 m.Figure10 plots the relationship between the disks radius and the nodes number in each placement scheme. Figure 8 shows that the number of nodes needed by Equ-StripC1 placement is always larger than by Iso-TriC1 placement in 1-coverage, and the number of nodes needed by Equ-StripC2 placement is always larger than by the Iso-TraC2 placement proposed in this paper in 2-coverage.In order to completely cover a bounded area with lengthL=1000 m and width w=10 m, the number of nodes and coverage density and efficiency are listed in Table 2 in terms of different sensing radius r.Table 2
Metrics comparison between two methods in different radiusr.
(a)
r
=
12 m
Pattern
N
ρ
η
N
ρ
η
k
1
2
Equ-Strip
76
3.41
64%
152
6.82
32%
Iso-Tri/Iso-Tra
54
2.43
92%
108
4.86
40%
(b)
r
=
14 m
Pattern
N
ρ
η
N
ρ
η
k
1
2
Equ-Strip
51
3.14
77%
102
6.28
39%
Iso-Tri/Iso-Tra
42
2.59
95%
84
5.18
44%
(c)
r
=
20 m
Pattern
N
ρ
η
N
ρ
η
k
1
2
Equ-Strip
29
3.63
91%
58
7.26
45%
Iso-Tri/Iso-Tra
28
3.37
98%
54
6.74
48%Table2 shows that when r=12 m, Iso-TraC2 placement pattern can save 44 nodes, about 30% less than by Equ-StipC2 pattern at the extreme sensing radius of Iso-TraC2 placement pattern. When r=12 m, Iso-TraC2 placement pattern can save 18 nodes compared to Equ-StripC2 pattern at the extreme sensing radius of Equ-StripC2 placement pattern. When r=20 m, the numbers of sensor nodes required by Iso-TraC2 and Equ-StripC2 pattern are nearly the same. Although the number of nodes needed is getting fewer when sensing radius increases, the coverage density is getting larger. In order to utilize the sensors in an efficient manner for keeping coverage quality and connectivity to increase the life time of the network, we choose the sensing radius which is a little bit larger than the extreme value by considering the power limitation in specific applications.Our proposed 2-coverage placement can provide data redundancy, which can improve the reliability of data transmission. The redundancy coverage also improves the robustness of network transmission while each point within the area is covered by at least two nodes. The topology will be segmented when, and only when, the two nodes in the waist of trapezoidal unit fail at the same time. To save cost of WSN deployment, we put forward a complete 2-coverage placement with minimum coverage density. Although the Isosceles Triangle complete 2-coverage placement pattern proposed by Fang and Chen [11] has stronger antidestroying ability, the price is the 3-coverage redundancy.In summary, the Iso-TriC1 has obvious advantages compared to Equ-StripC1 placements for once complete coverage. The Iso-TraC2 placement performs better than the Equ-StripC2 which is equal to the Iso-TriC2 placement pattern in [11] for bounded belt complete 2-coverage, in terms of less sensor node, smaller coverage density, and higher coverage efficiency.


## 5.3. Other Node Placements for Belt 2-Coverage

In this section, we analyze existing node placement schemes for belt 2-coverage, including Triangle 2-coverage (TriC2) placement pattern and Rectangle 2-coverage (RecC2) placement pattern shown in Figure11. Regular Triangle placement and Square placement pattern are particular cases, respectively. It is obvious that the relation between sensing radius of sensor node and width of belt should be satisfied with r<w; otherwise it will be the same as Equ-Strip placement above. To simplify the calculation, only the case of r<w<2r is considered in this paper.Figure 11
Placement schemes for whenr<w<2r.
(a)
Triangle placement pattern
(b)
Triangle 2-coverage pattern
(c)
Rectangle placement pattern
(d)
Rectangle 2-coverage patternFigure12 plots the relationships between coverage efficiency and w/r by Triangle and Rectangle placement patterns when r<w<2r. For both patterns, the extreme values of w/r are equal for once coverage and twice coverage, respectively, which are shown in Table 3.Table 3
Patterns, ratiow/r, and η, when r<w<2r.
Pattern
w
/
r
η
TriC1
3
/
2
85%
RecC1
2
82%
TriC2
3
/
2
43%
RecC2
2
41%Figure 12
Coverage efficiency versusw/r.In order to completely cover a bounded area with lengthL=1000 m and width w=10 m, the number of nodes needed is figured out at the extreme sensing radius r, which is about 8 m, shown in Table 4.Table 4
Number of nodes needed whenr=8 m.
Pattern
Number of nodes
k
1
2
Triangle
130
260
Rectangle
161
322The number of nodes needed to completely cover the belt region by Triangle and Rectangle placements is much larger than that by our proposed method. On the one hand, the sensing radius is smaller than the belt width. On the other hand, the coverage efficiency is lower than our node deployment. In summary, the Iso-TriC1 has obvious advantages compared to existing node placements [5, 11, 18, 22] for a long bounded belt complete 2-coverage, in terms of less sensor node and higher coverage efficiency. If possible, the sensing radius of node had better be set as w<r<2w in saving cost for WSNs application.


## 6. Conclusion and Future Work

In this paper, based on Equalization Strip theory, we propose a deployment for completely covering the long bounded belt field twice in WSN. The goal of our work is to find the optimal node placement method and the ratio of node sensing radius to a certain belt width in order to guarantee the complete 2-coverage with least nodes. In this paper, we defined and proposed an Isosceles Trapezoid complete 2-coverage placement method based on Equalization Strip placement theory and Isosceles Triangle strip pattern. Theoretical analysis demonstrates that Isosceles Triangle complete 1-coverage and Isosceles Trapezoid complete 2-coverage pattern are, respectively, optimal in once and twice complete coverage problem. Mathematical results show that our placement method needs smaller nodes number than existing ones. According to our results, the number of nodes needed by the Isosceles Trapezoid 2-coverage placement is 30% less than that needed by Equalization Strip 2-coverage or Isosceles Triangle 2-coverage placement when the sensing radius is approximate to but a little bit bigger than the belt width.It is well known that the spatial correlation between all nodes is strong when the multicovered area is big [25]. On the contrary, the spatial correlation between all nodes is weak. The coverage efficiency graph in Figure 9 shows that the redundancy of 3-coverage in our Iso-TraC2 placement is less than existing ones. Also the multicovered area can be minimized by effective sleep scheduling algorithm while the interest of area (IOA) is guaranteed to be completely covered by as few activated nodes as possible. Therefore, the computational cost of correlation between nodes within the same cluster can be effectively reduced by our placement with lowest coverage redundancy. There is also lower redundant data transmission in WSNs, which can reduce computational cost of data fusion.Furthermore, our Iso-TraC2 placement proposes another novel solution in constructing 2-coverage honeycomb grid lattice for large area coverage only whenr/w=2/√3.In the future, we will consider different sensing model which is more accurate in describing the node sensing ability in bounded space. And we will integrate the sensor network connectivity requirement in completek-coverage problem for long bounded belt area.



---

*Source: 672768-2015-11-05.xml*