# A Movement-Efficient Deployment Scheme Based on Information Coverage for Mobile Sensor Networks

Authors: Wei Cheng; Yong Li; Yi Jiang; Xipeng Yin
Journal: Journal of Electrical and Computer Engineering
 (2015)

---

## Abstract

Covering the surveillance region is a key task for wireless sensor networks. For mobile sensors, the deployment of sensors at appropriate locations is the key issue for sufficient coverage of surveillance area, and efficient resource management of sensor network. Previous studies most utilize physical coverage model for developing deployment schemes, in that the sensor resources may be wasted during the deployment for coverage. In this paper, a novel movement-efficient deployment scheme for mobile sensor networks is proposed, which adapts the information coverage model and the classical potential field method. The performances of the proposed scheme are evaluated comparing to two other schemes in aspects of coverage rate, coverage hole rate, ideal moving distance, and actual moving distance through extensive simulations. Simulation results show that the proposed scheme performs better than these related schemes in both coverage and movement efficiency.


---

## Body

## 1. Introduction

Mobile sensor networks are sensor networks in which sensors can move under their own control or under the control of the environment. A mobile sensor network is composed of some distributed mobile sensors to collect data. For the efficiency of wireless sensor networks, the appropriate scheme of deployment for mobile sensors is to maximize sensing coverage, which is the key task for a wireless sensor network [1].Recently there is a lot of research about autonomous mobile robot deployment. Batalin and Sukhatme [2] proposed the local dispersion scheme to obtain a better coverage on whole surveillance region. Then a most famous approach, potential field theory scheme, was first proposed by Khatib [3] and then it was adapted for achieving elegant path planning algorithm of mobile robots [4] and multirobot manipulation [5]. Howard et al. [6] and Poduri and Sukhatme [7] employed the potential field-based schemes for area coverage in mobile sensor networks, which had been commonly used for mobile robotics. Tan et al. [8] proposed a floor-based scheme on deployment of mobile sensors. The main idea is to compartmentalize the surveillance region to floors with common height and make mobile sensors stay in floor line in the way in order to reduce the overlap area of the sensing disks. Wang et al. [9] developed some schemes based on Voronoi diagram to maximize coverage of sensing. Once a coverage hole is discovered locally, the target location is estimated to guide the mobile sensors where to move at next round. The Voronoi diagram is used to discover the coverage holes and to develop a series of movement-assisted schemes for sensor deployment. Lee et al. [10] proposed an approach dealing with coverage hole by utilizing local Voronoi diagrams. While mobile sensors are deployed randomly, a sensor calculates the centroid for its local Voronoi polygon to get the next location where it will move to it in next time step. The sensors move round after round while the coverage is increased gradually. Thereafter, Han et al. [11] proposed another improved scheme which adapt centroid-directed virtual force. The same as other existing schemes, this scheme makes mobile sensors move around from high-density region to low-density region and avoid obstacles in surveillance region.For coverage model, these previous works most utilize binary model that the sensing quality is constant within sensing rangers while sensing quality is none outside sensing range. In this case, a given point is deemed to be covered if its physical distance to a sensor is shorter than sensing range. This concept of coverage is commonly regarded asphysical coverage. However, Wang [12, 13] proposed a concept ofinformation coveragebased on estimation theory, in that sensors could cooperate to make estimates on sensing data at a given location of surveillance area. This new concept can reduce the requirements on sensor density for area coverage.Although information coverage model has been used in sensor scheduling [14] and barrier coverage [15], it is rarely employed in the coverage issue for mobile sensor deployment. In this work, we will propose a movement-efficient scheme for mobile sensor deployment, which adapts sensing model based on information coverage and classical potential field method, so as to achieve the coverage requirement more practically and efficiently for mobile sensor networks. The main contribution of this paper is that we propose a novel scheme based on potential field for mobile sensor deployment, which adapts information coverage model. The proposed scheme can further improve coverage rate and avoid coverage hole effectively. Furthermore the proposed scheme could also increase movement efficiency in coverage process for mobile sensors.The rest of this paper is organized as follows. Section2 provides an overview on related works. In Section 3, the network assumptions, adversary model, and evaluation metrics are presented. Section 4 provides the detailed description of the strategies and our proposed deployment scheme. Then in Section 5 we evaluate the performance of the scheme by numeric simulations. Finally, Section 6 concludes this paper.


## 2. Related Work

### 2.1. Potential Field Method

According to potential field theory, a potential field is usually defined in a space so that its minimum could be achieved while all elements of space are nicely at target configuration [4–6, 16]. As objective is on the minimum ideally, all obstacles and borders in this space are all assumed to produce a high potential hill, so that, under this configuration of potential field, mobile sensor could move from the location with higher potential to location with lower potential. Sensors have to cover a target region, which may contain borders and obstacles, and to preserve communication capability between neighbor sensors. The mobile sensor gets attracted from the target locations while being repelled by borders and obstacles simultaneously. Finally the sum of all these potential fields determines the way of movements for the mobile sensor. For coverage issue, the overall potential field is achieved by adding the repulsive potentials that are from all obstacles and borders in surveillance area and the attractive potential from the target: (1)Ux,y=Uattx,y+Urepx,y.The related scheme proposed for maximizing the area coverage based on potential field could be presented as follows: each sensor would find the closest neighbor of its own by computing the distance between all the sensors. Then sensors would attempt to maintain a distance between their closest neighbor and themselves as communication range. The movements of sensors would turn into stable state when they all achieve this distance. Then every sensor would have one communication link leastwise which is established between its closest neighbor and itself.


### 2.2. Voronoi Diagram Method

The Voronoi diagram is one of the basal tools for resolving coverage problem in wireless sensor networks. A Voronoi diagram for a set of seed points divides space into a number of regions. Each region corresponds to one of the seed points, and all the points in one region are closer to the corresponding seed point than to any other seed points. This is a key property for the sensing coverage since if sensor could not sense an expected event occurring in its region of polygon, none of the other sensors could sense it any more. Consequently, every sensor should operate the task of sensing within its local Voronoi polygon.Utilizing property of Voronoi diagram, the area coverage could be transformed into coverage issue of every Voronoi polygon and reduce complexity of issues [17]. In Lee’s scheme [10] and Han’s scheme [11], every sensor utilizes the information locally to compute its local Voronoi polygon and then obtain the location with maximal effectiveness within local Voronoi polygon to enhance the local coverage rate and fix coverage holes at the most, so these schemes can be carried out currently and distributed by all mobile sensors. The centroid of the polygon is intersection point of all lines which divide the polygon into two portions of equal region. Thus this point could be the average of all points in the polygon. For coverage issue, centroid of local Voronoi polygon could be used as the point which is close to the location with maximal effectiveness so that these could efficiently increase the coverage of surveillance area. Assuming a polygon where n vertices (xi,yi) are presented clockwise and y coordinates of all vertices are nonnegative, then the closed-form expression of centroid (Cx,Cy) can be calculated as follows:(2)Cx=16SA∑i=0n-1xi+xi+1xiyi+1-xi+1yi,Cy=16SA∑i=0n-1yi+yi+1xiyi+1-xi+1yi,where area SA of this polygon can be expressed as(3)SA=12∑i=0n-1xiyi+1-xi+1yi.Lee et al. [10] first proposed a novel scheme which deals with coverage hole by utilizing local Voronoi polygon. This scheme can be demonstrated by Figure 1; when all sensors are deployed randomly at first, each sensor computes centroid of its own local Voronoi polygon as possible future location and then moves towards this location. After several movements and iterations, the locations of all sensors are changed step by step; thus the whole coverage of sensing is refined gradually.Figure 1
Snapshot of Centroid-Directed Potential Field.Han et al. [11] utilized three virtual forces from three potential fields independently on every sensor for coverage issue: the first is the repulsive potential Ubr from surrounding borders and external obstacles, the second one is the repulsive potential Ucov from neighbor sensors, and the last one is the attractive cover potential Uv which could draw sensors towards the centroid of their local Voronoi polygons. Each of these potentials has its own direction and magnitude that depend on the relative locations of borders, obstacles, neighbor sensors, or centroid.Thus mobile sensor is driven byU which is the sum of the three potential fields:(4)U=KbrUbr+KcovUcov+KvUv, where Kbr, Kcov, and Kv are corresponding positive scaling factors for each potential field.


## 2.1. Potential Field Method

According to potential field theory, a potential field is usually defined in a space so that its minimum could be achieved while all elements of space are nicely at target configuration [4–6, 16]. As objective is on the minimum ideally, all obstacles and borders in this space are all assumed to produce a high potential hill, so that, under this configuration of potential field, mobile sensor could move from the location with higher potential to location with lower potential. Sensors have to cover a target region, which may contain borders and obstacles, and to preserve communication capability between neighbor sensors. The mobile sensor gets attracted from the target locations while being repelled by borders and obstacles simultaneously. Finally the sum of all these potential fields determines the way of movements for the mobile sensor. For coverage issue, the overall potential field is achieved by adding the repulsive potentials that are from all obstacles and borders in surveillance area and the attractive potential from the target: (1)Ux,y=Uattx,y+Urepx,y.The related scheme proposed for maximizing the area coverage based on potential field could be presented as follows: each sensor would find the closest neighbor of its own by computing the distance between all the sensors. Then sensors would attempt to maintain a distance between their closest neighbor and themselves as communication range. The movements of sensors would turn into stable state when they all achieve this distance. Then every sensor would have one communication link leastwise which is established between its closest neighbor and itself.


## 2.2. Voronoi Diagram Method

The Voronoi diagram is one of the basal tools for resolving coverage problem in wireless sensor networks. A Voronoi diagram for a set of seed points divides space into a number of regions. Each region corresponds to one of the seed points, and all the points in one region are closer to the corresponding seed point than to any other seed points. This is a key property for the sensing coverage since if sensor could not sense an expected event occurring in its region of polygon, none of the other sensors could sense it any more. Consequently, every sensor should operate the task of sensing within its local Voronoi polygon.Utilizing property of Voronoi diagram, the area coverage could be transformed into coverage issue of every Voronoi polygon and reduce complexity of issues [17]. In Lee’s scheme [10] and Han’s scheme [11], every sensor utilizes the information locally to compute its local Voronoi polygon and then obtain the location with maximal effectiveness within local Voronoi polygon to enhance the local coverage rate and fix coverage holes at the most, so these schemes can be carried out currently and distributed by all mobile sensors. The centroid of the polygon is intersection point of all lines which divide the polygon into two portions of equal region. Thus this point could be the average of all points in the polygon. For coverage issue, centroid of local Voronoi polygon could be used as the point which is close to the location with maximal effectiveness so that these could efficiently increase the coverage of surveillance area. Assuming a polygon where n vertices (xi,yi) are presented clockwise and y coordinates of all vertices are nonnegative, then the closed-form expression of centroid (Cx,Cy) can be calculated as follows:(2)Cx=16SA∑i=0n-1xi+xi+1xiyi+1-xi+1yi,Cy=16SA∑i=0n-1yi+yi+1xiyi+1-xi+1yi,where area SA of this polygon can be expressed as(3)SA=12∑i=0n-1xiyi+1-xi+1yi.Lee et al. [10] first proposed a novel scheme which deals with coverage hole by utilizing local Voronoi polygon. This scheme can be demonstrated by Figure 1; when all sensors are deployed randomly at first, each sensor computes centroid of its own local Voronoi polygon as possible future location and then moves towards this location. After several movements and iterations, the locations of all sensors are changed step by step; thus the whole coverage of sensing is refined gradually.Figure 1
Snapshot of Centroid-Directed Potential Field.Han et al. [11] utilized three virtual forces from three potential fields independently on every sensor for coverage issue: the first is the repulsive potential Ubr from surrounding borders and external obstacles, the second one is the repulsive potential Ucov from neighbor sensors, and the last one is the attractive cover potential Uv which could draw sensors towards the centroid of their local Voronoi polygons. Each of these potentials has its own direction and magnitude that depend on the relative locations of borders, obstacles, neighbor sensors, or centroid.Thus mobile sensor is driven byU which is the sum of the three potential fields:(4)U=KbrUbr+KcovUcov+KvUv, where Kbr, Kcov, and Kv are corresponding positive scaling factors for each potential field.


## 3. Problem Formulation

### 3.1. Network Assumptions

We consider A as the surveillance area on a two-dimensional space. The borders of surveillance area can be regarded as wall-like obstacles. GivenN mobile sensors which gather in one place at the beginning, and a target surveillance region, the goal of our work is to maximize the sensing coverage with less coverage hole. However, since sensor movements would cause significant energy consumption, we wish all sensors would move as less as possible to prolong the network lifetime.To address this problem, the following assumptions will be made as follows.(1)
All of sensors have the same sensing rangers and also communication range rc. While sensors are within rc of a sensor, they are counted as the neighbors of sensor.(2)
The mobile sensors could take omnidirectional movement and move at variable velocity in different rounds.(3)
Sensors could know their locations by some scheme and obtain locations of neighbor sensors by communication to each other.(4)
Sensors are assumed to be provided with equipment which could determine the relevant range of borders and obstacles.(5)
No mobile sensor will fail during the coverage process.


### 3.2. Evaluation Metrics

#### 3.2.1. Coverage Rate

This metric is most fundamental for the performance of sensor deployment. This metric could be expressed as follows:(5)ratecov=⋃i=1NCiSA,where Ci denotes the exact area covered by sensor i, the number of sensors is N, and SA is the total area of the surveillance region.


#### 3.2.2. Coverage Hole Rate

For simplicity of cognizance for coverage hole, we believe a point is in the coverage hole for given surveillance area if it satisfies the following conditions: (1) this point is not covered by any sensors in the surveillance area; (2) this point is not in the triangle whose vertexes are three nearest sensor’s locations for this point. So the coverage hole rate can be expressed as(6)ratehole=⋃i=1MHiSA,where Hi is the region of coverage hole i and M is the number of coverage holes.


#### 3.2.3. Ideal Moving Distance

With the mobile sensors, we define ideal moving distance first as the direct distance between initial location and the final location. Then total ideal moving distance over all mobile sensors could be denoted as(7)Lid,tot=∑i=1NxInitial,i-xFinal,i2+yInitial,i-yFinal,i2.


#### 3.2.4.  Actual Moving Distance

As the description above, we define actual moving distance as accumulative distance traveled in rounds from the initial location to the final location. Whenli(t) is accumulative distance of sensor i at round t, actual moving distance over all mobile sensors after time duration T could be exactly expressed as(8)Ltot=∑i=1N∑t=1Tlit.


## 3.1. Network Assumptions

We consider A as the surveillance area on a two-dimensional space. The borders of surveillance area can be regarded as wall-like obstacles. GivenN mobile sensors which gather in one place at the beginning, and a target surveillance region, the goal of our work is to maximize the sensing coverage with less coverage hole. However, since sensor movements would cause significant energy consumption, we wish all sensors would move as less as possible to prolong the network lifetime.To address this problem, the following assumptions will be made as follows.(1)
All of sensors have the same sensing rangers and also communication range rc. While sensors are within rc of a sensor, they are counted as the neighbors of sensor.(2)
The mobile sensors could take omnidirectional movement and move at variable velocity in different rounds.(3)
Sensors could know their locations by some scheme and obtain locations of neighbor sensors by communication to each other.(4)
Sensors are assumed to be provided with equipment which could determine the relevant range of borders and obstacles.(5)
No mobile sensor will fail during the coverage process.


## 3.2. Evaluation Metrics

### 3.2.1. Coverage Rate

This metric is most fundamental for the performance of sensor deployment. This metric could be expressed as follows:(5)ratecov=⋃i=1NCiSA,where Ci denotes the exact area covered by sensor i, the number of sensors is N, and SA is the total area of the surveillance region.


### 3.2.2. Coverage Hole Rate

For simplicity of cognizance for coverage hole, we believe a point is in the coverage hole for given surveillance area if it satisfies the following conditions: (1) this point is not covered by any sensors in the surveillance area; (2) this point is not in the triangle whose vertexes are three nearest sensor’s locations for this point. So the coverage hole rate can be expressed as(6)ratehole=⋃i=1MHiSA,where Hi is the region of coverage hole i and M is the number of coverage holes.


### 3.2.3. Ideal Moving Distance

With the mobile sensors, we define ideal moving distance first as the direct distance between initial location and the final location. Then total ideal moving distance over all mobile sensors could be denoted as(7)Lid,tot=∑i=1NxInitial,i-xFinal,i2+yInitial,i-yFinal,i2.


### 3.2.4.  Actual Moving Distance

As the description above, we define actual moving distance as accumulative distance traveled in rounds from the initial location to the final location. Whenli(t) is accumulative distance of sensor i at round t, actual moving distance over all mobile sensors after time duration T could be exactly expressed as(8)Ltot=∑i=1N∑t=1Tlit.


## 3.2.1. Coverage Rate

This metric is most fundamental for the performance of sensor deployment. This metric could be expressed as follows:(5)ratecov=⋃i=1NCiSA,where Ci denotes the exact area covered by sensor i, the number of sensors is N, and SA is the total area of the surveillance region.


## 3.2.2. Coverage Hole Rate

For simplicity of cognizance for coverage hole, we believe a point is in the coverage hole for given surveillance area if it satisfies the following conditions: (1) this point is not covered by any sensors in the surveillance area; (2) this point is not in the triangle whose vertexes are three nearest sensor’s locations for this point. So the coverage hole rate can be expressed as(6)ratehole=⋃i=1MHiSA,where Hi is the region of coverage hole i and M is the number of coverage holes.


## 3.2.3. Ideal Moving Distance

With the mobile sensors, we define ideal moving distance first as the direct distance between initial location and the final location. Then total ideal moving distance over all mobile sensors could be denoted as(7)Lid,tot=∑i=1NxInitial,i-xFinal,i2+yInitial,i-yFinal,i2.


## 3.2.4.  Actual Moving Distance

As the description above, we define actual moving distance as accumulative distance traveled in rounds from the initial location to the final location. Whenli(t) is accumulative distance of sensor i at round t, actual moving distance over all mobile sensors after time duration T could be exactly expressed as(8)Ltot=∑i=1N∑t=1Tlit.


## 4. Strategies and Proposed Scheme

### 4.1. Information Coverage Concept

ConsideringK distributed sensors, every sensor takes a measurement on an unknown parameter θ of a phenomenon at some location and time [12, 13]. Let dk, k=1,2,…,K, denotes the distance between sensor k and the location with that phenomenon. The parameter θ is assumed to decay with range, while it is θ/dα at distance d, where α is the decay exponent and α>0. Then the measurement zk for the parameter θ, on sensor k, may be disturbed by an additive noise nk. Thus (9)zk=θdkα+nk,k=1,2,…,K. The goal of parameter estimators is to estimate θ by these noisy measurements. Let θ^K and θ~K=θ^K-θ, respectively, denote the estimate and estimation error of θ by K sensors.We can observe that the estimationθ^K and error θ~K are both random variables. The probability that the absolute value of θ~K is less than a constant A could be used to evaluate how well a given point is sensed; the larger this probability is, the more reliable the estimator is. Once it is larger than a scheduled threshold ε, that is, Pr{θ~K≤A}≥ε, this could be defined asinformation coverage with K cooperative sensors: a point is regarded as (K,ε)-covered if there are K sensors to estimate the parameter at a point so that Pr{θ~K≤A}≥ε, where 0≤ε≤1. When K measurements are available, some standard estimators, such as the best linear unbiased estimator (BLUE), could be used to estimate parameter and obtain minimum mean squared error (MSE).The key advantage of adapting this notion is to decrease sensor density and cover surveillance region completely. Assuming that all noises are independent and Gaussian, summation of these noises would still be Gaussian with zero mean and variance:(10)σ~K2=∑k=1KaK2σK2,where ak=BK/dkασk2 and BK=∑k=1K1/dk2ασk2. Assume that all these noises have the same variance σk2=σ2, k=1,2,…,K. Hence there is(11)Prθ~K≤A=1-2QAσ∑k=1Kdk-2α-1, where Q(x)=1/2π∫x∞exp(-t2/2)dt.Define sensing rangers and the range where estimation error would be equal to threshold ε. Thus there is(12)QArsασ=121-ε.For simplicity, we set rs as the unit for range while A=σ and then calculate threshold ε accordingly; hence ε=0.683.


### 4.2. Information Coverage Based Deployment

In Wang et al.’s work [12], they introduced some regular sensor deployments for static sensors. Figure 2 demonstrates the physical coverage and information coverage when deployment pattern is tiling, that is, all equilateral triangles. In this case, with regular tiling and α=1, the information coverage on this area is much larger than that of a physical coverage without coverage hole.Figure 2
(a) Deployment for physical coverage. (b) Case of physical coverage. (c) Deployment for(3,ε) information coverage. (d) Case of (3,ε) information coverage.
(a)
(b)
(c)
(d)There also was some other tiling which was square or hexagon in this work [12], whereas this equilateral triangles’ deployment is more suitable for potential fields design because of its simplest form, such that distances between sensors are all equal in each tiling.


### 4.3. Potential Function Design

For developing a scheme based on this deployment of(3,ε) information coverage for mobile sensors, two potential functions need to be designed. The first one would drive the mobile sensor to maximize the coverage region and the second one would prevent all mobile sensors from the borders and obstacles in surveillance area [6, 16]. These two potentials could be defined as cover potential and boundary potential.The principal goal of cover potential is to drive the sensors to spread as long as the maximum region is covered while the communication connectivity could be still maintained. The distance between sensor and its closest neighbor is mainly used for computing this potential function. Thus this potential function could be formatted as(13)Ucov=∑i=1ndi-dCR2,where di is the distance between sensor i and its closest neighbor.We definedCR as sensor distance of (3,ε) information coverage, which can be computed based on deployment of equilateral triangles as follows. For (3,ε) information coverage, there is(14)1-2QAσ∑k=1KDk-2α-1=ε.SinceK=3 and Dk=D for (3,ε) information coverage, where D is the distance between the vertex and geometric center, of this equilateral triangle, and A=σ, α=1, thus(15)1∑k=13D-2-1=Q-1121-ε, where Q-1(x) is the inverse Q function; then we can deduce that(16)D=3Q-11/21-ε.Considering both coverage and connectivity, we define Dv as the distance between the vertexes of this equilateral triangle; then Dv=2cosπ/6·D and dCR can be expressed as (17)dCR=DvifDv<rcrcifDv≥rc.Based on the potential function in (13), each sensor would attempt to hold on a distance as dCR from its nearest neighbor. Once the distance between sensors is larger than dCR, the cover potential Ucov would produce an attractive force on sensors; while the distance between sensors is smaller than dCR it would produce repulsive force. This scheme could drive spreading of sensors in the surveillance area so that the covered area could be maximized.However, there are possibilities that sensors will move beyond the border of surveillance area, and this may reduce the efficiency of the coverage. Considering this issue, another potential function needs to be considered, which addresses the border of surveillance area and attempts to drive sensors within the surveillance area [6, 16]. If the border is regarded as an obstacle, then this could be regarded as a potential function of obstacle avoidance. Once the distance between sensor and the border or obstacle is smaller than the threshold value, this potential would try to keep the sensor away from border or obstacle at a limiting distance. It would produce a repulsive force that could drive sensors away from obstacles and borders. Once the distance between sensor i and border or obstacle is smaller than threshold dTH, the border potential Ubr would work immediately. So this potential function can be formatted as (18)Ubr,i=λdbr,iifdbr,i<dTH0ifdbr,i≥dTH,Ubr=∑i=1nUbr,i, where λ is a positive scaling factor. Then total potential function U can be computed by accumulating all of cover potentials and the border potentials, which can be expressed as(19)U=KcovUcov+KbrUbr,where Kbr and Kcov are corresponding positive scaling factors for each potential field. The velocity of mobile sensor could be computed by working out the gradient of final potential function. The final potential function is the function of locations of mobile sensors, while the gradient of this potential function can be regarded as the time derivative of the location of each mobile sensor. Thus velocity can be expressed as(20)
v
t
=
-
∇
U
x
,
y
=
-
∂
U
x
,
y
∂
x
-
∂
U
x
,
y
∂
y
.Each sensor calculates its new velocity and will move to next location according to this velocity, and then new locations can be obtained by central difference method.


## 4.1. Information Coverage Concept

ConsideringK distributed sensors, every sensor takes a measurement on an unknown parameter θ of a phenomenon at some location and time [12, 13]. Let dk, k=1,2,…,K, denotes the distance between sensor k and the location with that phenomenon. The parameter θ is assumed to decay with range, while it is θ/dα at distance d, where α is the decay exponent and α>0. Then the measurement zk for the parameter θ, on sensor k, may be disturbed by an additive noise nk. Thus (9)zk=θdkα+nk,k=1,2,…,K. The goal of parameter estimators is to estimate θ by these noisy measurements. Let θ^K and θ~K=θ^K-θ, respectively, denote the estimate and estimation error of θ by K sensors.We can observe that the estimationθ^K and error θ~K are both random variables. The probability that the absolute value of θ~K is less than a constant A could be used to evaluate how well a given point is sensed; the larger this probability is, the more reliable the estimator is. Once it is larger than a scheduled threshold ε, that is, Pr{θ~K≤A}≥ε, this could be defined asinformation coverage with K cooperative sensors: a point is regarded as (K,ε)-covered if there are K sensors to estimate the parameter at a point so that Pr{θ~K≤A}≥ε, where 0≤ε≤1. When K measurements are available, some standard estimators, such as the best linear unbiased estimator (BLUE), could be used to estimate parameter and obtain minimum mean squared error (MSE).The key advantage of adapting this notion is to decrease sensor density and cover surveillance region completely. Assuming that all noises are independent and Gaussian, summation of these noises would still be Gaussian with zero mean and variance:(10)σ~K2=∑k=1KaK2σK2,where ak=BK/dkασk2 and BK=∑k=1K1/dk2ασk2. Assume that all these noises have the same variance σk2=σ2, k=1,2,…,K. Hence there is(11)Prθ~K≤A=1-2QAσ∑k=1Kdk-2α-1, where Q(x)=1/2π∫x∞exp(-t2/2)dt.Define sensing rangers and the range where estimation error would be equal to threshold ε. Thus there is(12)QArsασ=121-ε.For simplicity, we set rs as the unit for range while A=σ and then calculate threshold ε accordingly; hence ε=0.683.


## 4.2. Information Coverage Based Deployment

In Wang et al.’s work [12], they introduced some regular sensor deployments for static sensors. Figure 2 demonstrates the physical coverage and information coverage when deployment pattern is tiling, that is, all equilateral triangles. In this case, with regular tiling and α=1, the information coverage on this area is much larger than that of a physical coverage without coverage hole.Figure 2
(a) Deployment for physical coverage. (b) Case of physical coverage. (c) Deployment for(3,ε) information coverage. (d) Case of (3,ε) information coverage.
(a)
(b)
(c)
(d)There also was some other tiling which was square or hexagon in this work [12], whereas this equilateral triangles’ deployment is more suitable for potential fields design because of its simplest form, such that distances between sensors are all equal in each tiling.


## 4.3. Potential Function Design

For developing a scheme based on this deployment of(3,ε) information coverage for mobile sensors, two potential functions need to be designed. The first one would drive the mobile sensor to maximize the coverage region and the second one would prevent all mobile sensors from the borders and obstacles in surveillance area [6, 16]. These two potentials could be defined as cover potential and boundary potential.The principal goal of cover potential is to drive the sensors to spread as long as the maximum region is covered while the communication connectivity could be still maintained. The distance between sensor and its closest neighbor is mainly used for computing this potential function. Thus this potential function could be formatted as(13)Ucov=∑i=1ndi-dCR2,where di is the distance between sensor i and its closest neighbor.We definedCR as sensor distance of (3,ε) information coverage, which can be computed based on deployment of equilateral triangles as follows. For (3,ε) information coverage, there is(14)1-2QAσ∑k=1KDk-2α-1=ε.SinceK=3 and Dk=D for (3,ε) information coverage, where D is the distance between the vertex and geometric center, of this equilateral triangle, and A=σ, α=1, thus(15)1∑k=13D-2-1=Q-1121-ε, where Q-1(x) is the inverse Q function; then we can deduce that(16)D=3Q-11/21-ε.Considering both coverage and connectivity, we define Dv as the distance between the vertexes of this equilateral triangle; then Dv=2cosπ/6·D and dCR can be expressed as (17)dCR=DvifDv<rcrcifDv≥rc.Based on the potential function in (13), each sensor would attempt to hold on a distance as dCR from its nearest neighbor. Once the distance between sensors is larger than dCR, the cover potential Ucov would produce an attractive force on sensors; while the distance between sensors is smaller than dCR it would produce repulsive force. This scheme could drive spreading of sensors in the surveillance area so that the covered area could be maximized.However, there are possibilities that sensors will move beyond the border of surveillance area, and this may reduce the efficiency of the coverage. Considering this issue, another potential function needs to be considered, which addresses the border of surveillance area and attempts to drive sensors within the surveillance area [6, 16]. If the border is regarded as an obstacle, then this could be regarded as a potential function of obstacle avoidance. Once the distance between sensor and the border or obstacle is smaller than the threshold value, this potential would try to keep the sensor away from border or obstacle at a limiting distance. It would produce a repulsive force that could drive sensors away from obstacles and borders. Once the distance between sensor i and border or obstacle is smaller than threshold dTH, the border potential Ubr would work immediately. So this potential function can be formatted as (18)Ubr,i=λdbr,iifdbr,i<dTH0ifdbr,i≥dTH,Ubr=∑i=1nUbr,i, where λ is a positive scaling factor. Then total potential function U can be computed by accumulating all of cover potentials and the border potentials, which can be expressed as(19)U=KcovUcov+KbrUbr,where Kbr and Kcov are corresponding positive scaling factors for each potential field. The velocity of mobile sensor could be computed by working out the gradient of final potential function. The final potential function is the function of locations of mobile sensors, while the gradient of this potential function can be regarded as the time derivative of the location of each mobile sensor. Thus velocity can be expressed as(20)
v
t
=
-
∇
U
x
,
y
=
-
∂
U
x
,
y
∂
x
-
∂
U
x
,
y
∂
y
.Each sensor calculates its new velocity and will move to next location according to this velocity, and then new locations can be obtained by central difference method.


## 5. Performance Evaluation

We would take comparison between the proposed scheme based on(3,ε) information coverage and the existing schemes: potential field- (PF-) based scheme and Centroid-Directed Potential Field- (CDPF-) based scheme. We run each scheme in 3000 time stamps for one simulation and run it ten times for each parameter set to obtain average value. At the very beginning, we randomly deployed N sensors at the center of surveillance area, which has normalization boundary limits 1, so that the coordinate of mobile sensors (xi,yi) is always in [0,1]. Therefore total area of the surveillance area SA=1. The default sensing range rs=0.1 while communication range of sensor rc is at least one time more than it. The corresponding scaling factors Kbr and Kcov are all equal to 1, while Kv=0.3 for potential by centroid of the local Voronoi polygon, which is in Centroid-Directed Potential Field- (CDPF-) based scheme. Scaling factor for border potential λ=0.0009, and the threshold distance dTH=0.001.


### 5.1. Impact of Communication Range

Deploy 8 mobile sensors in given surveillance area and makerc vary from 1 to 3.5 times of rs. As shown in Figures 3-4, we can observe that the proposed scheme can acquire almost two times larger coverage rate with minimum coverage hole rate, compared to other schemes. We can also observe that coverage rate increases with the communication range increases when the communication range is lower than three times of sensing range. While the communication range is more than three times of sensing range, the coverage rate is decreased and the coverage hole rate is quite large; that occurs because when communication range is very large, the probability of sensors that are far away becomes higher; thus the opportunity that sensors could cooperate with each other to achieve (K,ε) information coverage is reduced.Figure 3
Coverage rate versus communication range(rc/rs).Figure 4
Coverage hole rate versus communication range(rc/rs).As shown in Figures5-6, we can observe that the proposed scheme can acquire the best movement efficiency in terms of actual moving distance, compared to other schemes. Although the ideal moving distance of the proposed scheme is the highest, the actual moving distance is much lower than that of other schemes. That occurs because information coverage could avoid some movements such as coverage hole fixing. When the model of information coverage is adopted, a physical coverage hole could be fixed by utilizing its neighbor sensors without taking any movement of other sensors.Figure 5
Ideal moving distance versus communication range(rc/rs).Figure 6
Actual moving distance versus communication range(rc/rs).


### 5.2. Impact of Number of Sensors

We fixrc as two times of rs and the number of sensors is varied from 3 to 18. As shown in Figures 7-8, we could find that as the amount of sensors changes, the proposed scheme can always acquire the best coverage rate with minimum coverage hole rate, compared to other schemes. One thing that needs to be noticed is that when the number of sensors reaches a certain quantity, the coverage hole rate decreases while the number of sensors increases for PF and CDPF schemes, as in Figure 8. That occurs because when the amount of sensors is quite large as mobile sensors spread, the probability of sensors that move back from the borders becomes higher, so that the opportunity of coverage hole refixing is increased. However, the coverage hole rate of the proposed scheme is always zero in this configuration, which proves that information coverage could fix coverage hole efficiently.Figure 7
Coverage rate versus number of sensors.Figure 8
Coverage hole rate versus number of sensors.As shown in Figures9-10, we can also observe that the proposed scheme can acquire the best movement efficiency compared to other schemes, which indicate that information coverage could improve both coverage rate and movement efficiency.Figure 9
Ideal moving distance versus number of sensors.Figure 10
Actual moving distance versus number of sensors.


### 5.3. Cost of Proposed Scheme

Although the model of information coverage based deployment scheme could improve the performance of coverage for mobile sensors, there is still a cost that the communication cost becomes higher since sensors need to cooperate to achieve information coverage. Therefore, the network-wide trade-off between using sensor movements and using sensor commutation is worthy of further studies.


## 5.1. Impact of Communication Range

Deploy 8 mobile sensors in given surveillance area and makerc vary from 1 to 3.5 times of rs. As shown in Figures 3-4, we can observe that the proposed scheme can acquire almost two times larger coverage rate with minimum coverage hole rate, compared to other schemes. We can also observe that coverage rate increases with the communication range increases when the communication range is lower than three times of sensing range. While the communication range is more than three times of sensing range, the coverage rate is decreased and the coverage hole rate is quite large; that occurs because when communication range is very large, the probability of sensors that are far away becomes higher; thus the opportunity that sensors could cooperate with each other to achieve (K,ε) information coverage is reduced.Figure 3
Coverage rate versus communication range(rc/rs).Figure 4
Coverage hole rate versus communication range(rc/rs).As shown in Figures5-6, we can observe that the proposed scheme can acquire the best movement efficiency in terms of actual moving distance, compared to other schemes. Although the ideal moving distance of the proposed scheme is the highest, the actual moving distance is much lower than that of other schemes. That occurs because information coverage could avoid some movements such as coverage hole fixing. When the model of information coverage is adopted, a physical coverage hole could be fixed by utilizing its neighbor sensors without taking any movement of other sensors.Figure 5
Ideal moving distance versus communication range(rc/rs).Figure 6
Actual moving distance versus communication range(rc/rs).


## 5.2. Impact of Number of Sensors

We fixrc as two times of rs and the number of sensors is varied from 3 to 18. As shown in Figures 7-8, we could find that as the amount of sensors changes, the proposed scheme can always acquire the best coverage rate with minimum coverage hole rate, compared to other schemes. One thing that needs to be noticed is that when the number of sensors reaches a certain quantity, the coverage hole rate decreases while the number of sensors increases for PF and CDPF schemes, as in Figure 8. That occurs because when the amount of sensors is quite large as mobile sensors spread, the probability of sensors that move back from the borders becomes higher, so that the opportunity of coverage hole refixing is increased. However, the coverage hole rate of the proposed scheme is always zero in this configuration, which proves that information coverage could fix coverage hole efficiently.Figure 7
Coverage rate versus number of sensors.Figure 8
Coverage hole rate versus number of sensors.As shown in Figures9-10, we can also observe that the proposed scheme can acquire the best movement efficiency compared to other schemes, which indicate that information coverage could improve both coverage rate and movement efficiency.Figure 9
Ideal moving distance versus number of sensors.Figure 10
Actual moving distance versus number of sensors.


## 5.3. Cost of Proposed Scheme

Although the model of information coverage based deployment scheme could improve the performance of coverage for mobile sensors, there is still a cost that the communication cost becomes higher since sensors need to cooperate to achieve information coverage. Therefore, the network-wide trade-off between using sensor movements and using sensor commutation is worthy of further studies.


## 6. Conclusions

We propose movement-efficient deployment scheme based on potential field method for mobile sensors, which adapts the information coverage model. Since the information coverage model could save sensor resources during deployment, the proposed scheme can improve coverage performance and movement efficiency. Numeric simulations show that the proposed scheme outperforms several previous approaches developed for deployment of mobile sensor networks.



---

*Source: 986956-2015-12-03.xml*