Improved Virtual Potential Field Algorithm Based on Probability Model in Three-Dimensional Directional Sensor Networks

Abstract

In conventional directional sensor networks, coverage control for each sensor is based on a 2D directional sensing model. However, 2D directional sensing model failed to accurately characterize the actual application scene of image/video sensor networks. To remedy this deficiency, we propose a 3D directional sensor coverage-control model with tunable orientations. Besides, a novel criterion for judgment is proposed in view of the irrationality that traditional virtual potential field algorithms brought about on the criterion for the generation of virtual force. Furthermore, cross-set test is used to determine whether the sensory region has any overlap and coverage impact factor is introduced to reduce profitless rotation from coverage optimization, thereby the energy cost of nodes was restrained and the performance of the algorithm was improved. The extensive simulations results demonstrate the effectiveness of our proposed 3D sensing model and IPA3D (improved virtual potential field based algorithm in three-dimensional directional sensor networks).

1. Introduction

The sensory ability of WSNs to physical world is embodied in coverage which is often used to describe the monitoring standard of Quality of Service (QoS) [1, 2]. Coverage optimization in sensor networks plays a significant role in allocating network space, realizing context awareness and information acquisition, and enhancing the viability of networks [3].

Early studies on coverage optimization were based on two-dimensional sensory domain model [4, 5], or 0-1 probability sensory model. For instance, the virtual force algorithm (VFA) proposed by Zou and Chakrabarty [6] moves nodes after all nodes' moving paths have been determined. The authors of [7] proposed an approximate centralized greed algorithm to solve the maximum coverage problem with minimum sensors. Coverage in terms of the number of targets to be covered is maximized, whereas the number of sensors to be activated is minimized. The target involved virtual force algorithm (TIVFA) is proposed by Li et al. [8] and potential field-based coverage-enhancing algorithm (PFCEA) aiming at directional sensor model is proposed by Tao et al. [9]. The authors of [10] discussed multiple directional cover sets problem of organizing the directions of sensors into a group of nondisjoint cover sets in each of which the directions cover all the targets so as to maximize the network lifetime. In [11], which is written by me, I improved the criterion for judging the generation of virtual potential field via cross-set test. However, probability-based three-dimensional sensor networks model is more tending to be in conformity with practical application, for example, the recently arisen multimedia sensor networks [3, 12–16] and underwater networks [17]. In view of three-dimensional sensory model and probability sensory model, overseas and domestic researchers have yielded some research achievements on coverage algorithms in recent years. I proposed a virtual force algorithm which is applicable with three-dimensional omnidirectional sensory model in [18]. Authors of [19] put forward a three-dimensional directional sensory model and optimized coverage performance using virtual potential field and simulated annealing algorithm. Reference [20] proposed a coverage configuration algorithm based on probability detection model (CCAP). Reference [21] proposed a coverage preservation protocol based on probability detection model (CPP) that makes working nodes in sensor networks as few as possible when network coverage is guaranteed. However, this protocol configures network using centred control algorithm which limits the network scale, and at present most of the literatures have not introduced this probability coverage model into three-dimensional sensor networks. In fact, most practical applied wireless sensor networks are deposited in three-dimensional sensor networks so that it will be more accurate if it is simulated in a three-dimensional space [22, 23]. In [22], Bai et al. proposed and designed a series of connected coverage model in three-dimensional wireless sensor networks with low connectivity and full coverage. In [23], Alam and Haas studied truncated octahedron deployment strategy to monitor network coverage situation. But in most studies, the criterion for the generation of repulsion between two points is simply defined as the situation that the distance between nodes is less than twice the sensory radius, which has been proved inappropriate to directional sensor networks in [11] by me. Therefore, first we analyze the sensory ability of three-dimensional directional sensor based on probability model to design a novel direction-steerable three-dimensional directional sensor model and make use of virtual potential algorithm to adjust node direction to improve coverage effect. In particular, in this paper we proposed a more rational criterion for generation of repulsion in three-dimensional directional sensor networks and introduced a factor called coverage impact factor to estimate the impact on network coverage from the change of sensing direction in advance, to reduce profitless adjustment of sensing direction, save node energy, enhance algorithm performance, and optimize coverage effect.

This paper is organized as follows: Section 2 gives the problem description and related definition. Section 3 describes the improved virtual potential field-based algorithm in three-dimensional directional sensor networks based on probability model. Section 4 describes in detail the algorithm flow. Section 5 verifies the validity of the algorithm via simulation experiments and makes contrast. Section 6 draws conclusion.

2. Coverage Enhancement Issues of Three Directional Sensor Networks

2.1. Problem Formulation

The coverage enhancement issue of three directional sensor networks that is constituted by direction-steerable nodes can be described as follow: how to enhance the degree of coverage by changing the sensing direction so that degree of coverage in target area approaches maximum in condition that a certain number of nodes are randomly distributed in a given three-dimensional target area and part of the area is not covered by nodes and the number and position of nodes are stable.

2.2. Analysis and Definitions on Coverage Enhancement Issue in Directional Sensor Networks

For the purpose of later research, we give the consumptions beforehand, shown as follows. (1)

Every node works independently, namely, sensory task of each node does not depend on others'.

(2)

All nodes are isomorphic, namely, all the maximum sensory distance $R_{S}$ , sensory deviation angle α, and communication radius $R_{C}$ are equal, respectively, and the communication radius is no less than twice of the maximum sensory distance.

(3)

Every node can get the information of its location and sensing direction and the direction is steerable.

Limited by the angle of view, the sensory area of the directional sensor model is abstracted to a tetrad $〈 L, R_{S}, \vec{D}, α 〉$ in three-dimensional space. As shown in Figure 1.

Figure 1

Directional sensor model.

Definition 1 (directional sensor model $〈 L, R_{S}, \vec{D}, α 〉$ ).

L is location of nodes, that corresponds to ( $x, y, z$ ) in a three-dimensional rectangular coordinate system. $R_{S}$ is maximum sensory distance of nodes. $\vec{D}$ is unit vector of sensing direction, denoted by ( $d x, d y, d z$ ), whose direction and central axis of sensory region is collinear. α is called sensory deviation angle and $0 \leq α \leq π$ .

In particular, when $α = π$ , the sensory region is a sphere thus the traditional omnidirectional sensor model can be considered as a special case of directional sensor model.

Definition 2 (probability detection model).

In this part, we define the sensor sensing accuracy model. Sensing accuracy of sensor $S_{i}$ at point t is defined as the probability of sensor $S_{i}$ to successfully detect an event happening at point t. A point here means a physical location in the covered area.

We assume that a sensor can always detect an event happening at the point with distance 0 from the sensor, and the sensing accuracy attenuates with the increase of the distance. One possible sensing accuracy model is [24]

P_{i t} = \frac{1}{{(1 + \partial d_{i t})}^{β}},

(1)

where

P_{i t}

is the sensing accuracy of sensor

S_{i}

at point t,

d_{i t}

is the distance between sensor

S_{i}

and point t, and constants ∂ and β are device-dependent parameters reflecting the physical features of a sensor. Generally, β ranges from 1 to 4. And ∂ is used as an adjustment parameter.

Sensor node density is usually higher. Assume that N sensor nodes are randomly distributed in a three-dimensional monitoring area. Therefore, events in the monitoring area are detected by multiple sensor nodes simultaneously. The sense probability is expressed as follow:

P_{t} = 1 - \prod_{i = 1}^{N} (1 - P_{i t}) .

(2)

Substitute into Formula (1)

P_{t} = 1 - \prod_{i = 1}^{N} (1 - \frac{1}{{(1 + \partial d_{i t})}^{β}}) .

(3)

According to (3), $P_{t} \geq P_{i t}$ , because multiple sensor nodes may sense the same events simultaneously.

Definition 3 (maximum sensory distance $R_{S}$ ).

The maximum sensory distance of nodes is defined as

R_{S} = \frac{1}{\partial} (λ^{- 1 / β} - 1) .

(4)

In condition of node $s_{i}$ working independently, if $d_{i t} \geq R_{S}$ , the probability of node $s_{i}$ being detected is $P_{i t} = 1 / (1 + \partial d_{i t})^{β} \leq λ$ . In this case, the effect on system detection probability from node $s_{i}$ to target point can be ignored. λ is the minimum probability of target found, which is determined by the actual application environment, hardware and software conditions and quality of service required, and other factors. λ is usually specified by user.

Definition 4 (sensory domain of node $s_{i}$ ).

For ease of later calculation, we translate the directional sensor model in Figure 1 into that in Figure 2 and give the following definition.

The sensory region is part of a sphere that centred on $\vec{D}$ with radius $R_{S}$ and maximum rotation angle which is denoted by $S D_{i}$ . In other words, sensory region is constituted by all spots that satisfy Formula (1) in which x represents spots in space, $θ_{i}$ represents the intersection angle with sensing direction vector $\vec{D}$

S D_{i} = {x | ‖ x - s_{i} ‖ \leq R_{S}, | θ_{i} (x) | \leq α} .

(5)

Figure 2

Sensory domain of node.

Definition 5 (Set of neighbor nodes $ψ_{i}$ ).

In sensor network, two nodes are called neighbors when Euclidean distance is less than twice the maximum sensory distance $R_{S}$ . The set of neighbor nodes of node $s_{i}$ is $ψ_{i}$

ψ_{i} = {s_{j} | D (s_{i}, s_{j}) < 2 R_{s}, i \neq j} .

(6)

Definition 6 (γ-probability coverage).

In a set of active nodes located at ( $x_{i}, y_{i}, z_{i}$ ), $i = 1,2, \dots, N$ , system detection probability of target point located at ( $x_{t}, y_{t}, z_{t}$ ) is $P_{t}$ . If $P_{t} ⩾ γ$ , the target point located at ( $x_{t}, y_{t}, z_{t}$ ) is satisfied with γ probability coverage. If all points in a region are satisfied with γ probability coverage, then this region is called complete γ probability coverage.

Definition 7 (degree of coverage).

A given area S is equally divided into M small areas which can be assumed as points as M is large enough. If there are Q points in the M points that accord with γ-probability coverage, coverage rate of area S is defined as

DoC (S) = \frac{Q}{M} .

(7)

Definition 8 (coverage impact factor).

Coverage impact factor μ characterizes the impact on network coverage when the sensing direction angle has been changed. We define it as follows:

μ = {\begin{cases} \begin{matrix} 1, & {DoC}_{i}^{'} (S) > {DoC}_{i} (S), \\ 0, & {DoC}_{i}^{'} (S) \leq {DoC}_{i} (S) . \end{matrix} \end{cases}

(8)

{DoC}_{i}^{'} (S)

represents the network coverage after node

s_{i}

has been changed.

3. The Improved Virtual Potential Field-Based Algorithm in Three-Dimensional Directional Sensor Networks

Taking the deployment cost of sensor network into consideration, it would be unpractical that all nodes are capable of moving. Moreover, the movement of sensor nodes usually causes the invalidation of part of sensor nodes and in turn changes the topology of the whole sensor network. All these factors raise the maintenance cost of network. Therefore, we assume that all nodes remain at the same location as initial and coverage can be enhanced by changing sensing direction of nodes. We introduce the concept of centroid. $c_{i}$ represents the centroid that is relative to node $s_{i}$ and locates in a spot in central axis of sensory region with a distance of $2 R \sin α / 3 α$ apart from the node. Now the issue is translated into the virtual force issue between centroids. We assume that there is virtual repulsion $F_{rep}$ between centroids. Under the action of repulsion, two nodes rotate in opposite direction to avoid the formation of sensory overlap region. At the same time of reducing the redundant coverage, a sufficient and efficient coverage of the monitoring area is achieved. Under the action of virtual potential field, every node gets the repulsion from one or more adjacent nodes.

3.1. Judgement on Overlap Situation of Sensory Area

In traditional algorithms, which use the virtual potential field to enhance coverage, the criterion for the generation of repulsion between two points is that the distance between nodes is less than $2 R_{S}$ [7] which is applicable to omnidirectional sensor model in that when the distance between nodes is less than $2 R_{S}$ , there bound to be some overlap in sensory area. But with regard to directional sensor model, the above conclusion is obviously incorrect. As shown in Figure 3, two nodes are less than $2 R_{S}$ apart from each other; however, with no sensory overlapped region for the difference of sensing direction angle. As a case by case, Figure 3 reflects a common situation in many cases which causes profitless adjustment of deployment, wastes energy of nodes, and shortens network lifetime.

Figure 3

A case that distance is less than $2 R_{S}$ without overlapped sensory region.

Therefore, in this paper, the criterion for generation of repulsion between two nodes is defined as whether or not there is overlap sensory region between two nodes.

To three-dimensional directional sensor networks model, when judging whether there is overlapped sensory region between two nodes, we project the sensory region onto planes $x o y$ , $x o z$ , and $y o z$ in a three-dimensional rectangular coordinate system. If and only if all projections on three planes has overlapped region, does the sensory region has overlapped region. So the overlap decision problem of three-dimensional sensor model has translated into that of two-dimensional model. I put forward an approach in [11] to decide if there is overlapped region in a two-dimensional directional sensor network model using cross-set test. Reference [25] demonstrates the 11 kinds of overlapped situations of sensory region with two-dimensional directional sensor model, as shown in Figure 4.

Figure 4

The situations of overlap of sensory region in directional sensor model.

We simplify the sectorial sensor model of a two-dimensional space into a triangle by replacing the arc in sector by line, because only under the circumstances of (c) and (d) in Figure 4 can the decision outcome be different. It can be seen in Figure 4 that the area of the overlap region under the two circumstances is small compared to the whole sensory region, so it is inefficient to waste energy and adjust deployment of nodes for that purpose.

After simplifying, we can determine whether the two triangles have overlap region according to whether they have intersecting sides by mean of cross-set test. As shown in Figure 5, a triangle with overlap region must have intersecting sides. For example, in Figure 5, $S_{1} a_{1}$ and $S_{2} a_{2}$ intersect, the following must be satisfied:

\begin{gathered} [(a_{2} - S_{1}) \times (a_{1} - S_{1})] * [(a_{1} - S_{1}) \times (S_{2} - S_{1})] \geq 0, \\ [(S_{1} - a_{2}) \times (S_{2} - a_{2})] * [(S_{2} - a_{2}) \times (a_{1} - a_{2})] \geq 0 . \end{gathered}

(9)

Figure 5

Two sensor models with overlap sensory region.

3.2. Analysis on Regulation of Node Rotation

3.2.1. Analysis on Regulation of Centroids

Nodes $s_{i}$ and $s_{j}$ are neighbors, the centroid $c_{i}$ at location $X_{i}$ is under action of the repulsion of $c_{j}$ at location $X_{j}$ which is defined as follows:

F_{rep} (i, j) = {\begin{cases} \frac{k_{rep}}{D {(c_{i}, c_{j})}^{2}} (\frac{x_{i} - x_{j}}{D (c_{i}, c_{j})}), & S D_{i} \cap S D_{j} \neq \emptyset, \\ 0, & S D_{i} \cap S D_{j} = \emptyset . \end{cases}

(10)

Using the method of Section 3.1, only when there is overlap region between two nodes, repulsion between centroids of two nodes exists. $D (c_{i}, c_{j})$ represents the Euclidean distance between centroid $c_{i}$ and $c_{j}$ . $k_{rep}$ represents the repulsion coefficient which is a positive constant. $S D_{i} / S D_{j}$ represent sensory domain of node $s_{i} / s_{j}$ . The magnitude of repulsion of centroid is inversely proportional to the Euclidean distance between them and the direction of repulsion that the centroid $c_{i}$ taking action is determined by the location of $c_{i}$ and $c_{j}$ . The resultant force $F_{rep} (i)$ of repulsion at centroid $c_{i}$ is

F_{rep} (i) = \sum_{n_{j} \in ψ_{i}} F_{rep} (i, j),

(11)

ψ_{i}

represents the set of all the neighbors of node

s_{i}

3.2.2. Analysis on Rotation Angle

The resultant repulse force actions on centroid $c_{i}$ and node single rotation angle θ jointly decide the later target location $X_{i}^{'}$ of centroid $c_{i}$ . Thereby, the later target location of centroid $c_{i}$ can be described as rotating a certain angle θ along the direction of resultant force $F_{rep}$ . Use Formula (5) to calculate the coverage impact factor. If $μ = 1$ , which means the movement is beneficial to coverage optimization, proceed the node rotation. Otherwise, the current sensing direction remain unchanged. Repeatedly, optimal solution approaches by fine adjustment. Meanwhile, we set the force threshold ε. When $∥ F_{T} ∥ \leq ε$ , centroid will oscillate repeatedly around a certain point which can be regarded as a stable state of centroid and no more actions is required. When all centroids come to the stable state within the network, the whole sensor network is considered as having reached the stable state.

4. Algorithm Description

According to the virtual force of the centroid of each node, a node deployment adjustment algorithm is proposed as follows in this paper. The algorithm is a distributed algorithm and executes simultaneously in each node. We equally divided the sensing area S into M small areas. M is large enough so that the small areas could be assumed as points. When area degree of coverage is calculated according to formula (7), the target point should be satisfied with γ-probability coverage. Take node $s_{i}$ for example, Formalized description of the algorithm is as in Algorithm 1.

Algorithm 1

$/ /$ initialization

(1) t←0;

(2) set the maximum cycle index $t_{\max}$ ;

(3) determine the initial position of corresponding centroid $c_{i}$

of $s_{i}$ and neighbor nodes set $ψ_{i}$ .

(4) while ( $t < t_{\max}$ ) do

(5) renew the current coordinate position of centroid $c_{i}$ ;

(6) determine the repulsion force $F_{rep} (i)$ acting on centroid $c_{i}$ from other nodes according to formula (10) and (11)

(7) if $(∥ F_{rep} (i) ∥ \geq ε$ ) then

(8) determine the later target location $X_{i}^{'}$ of centroid $c_{i}$ decided by the resultant repulse force actions on

centroid $c_{i}$ and node single rotation angle θ

(9) calculate the coverage impact factor μ of angle rotation this time according to Formula (8)

(10) if $μ = 1$ , proceed the angle rotation, else remain the sensing direction unchanged

(11) else break;

(12) t← $t + 1$

(13) end.

5. Algorithm Simulations and Performance Analysis

We developed the simulation software Sencov3.0 that applicable to the research of sensor network deployment and coverage with VC++6.0, using which we verify the validity of IPA3D algorithm through extensive simulation experiments. Values of specific parameters are shown in Table 1. We can see from formula (4) that $R_{S}$ is determined by ∂, β, λ. In all simulation experiments of this paper, we set $\partial = 1$ and $β = 1$ , so the value of $R_{S}$ is only determined by λ.

Table 1

Experiment parameters.

Parameter name	Parameter values
Target region	$100 * 100 * 100$ m³
Distribution mode	Uniform distribution
Number of nodes N	100–300
Device-dependent parameter ∂, β	1, 1
Minimum probability of target found λ	0.32–0.91
γ-probability coverage	0.90
Sensory angle of deviation α	$π / 6$ , $π / 5$ , $π / 4$ , $π / 3$ , $π / 2$ , π
Repulsion coefficient $k_{rep}$	100

5.1. Case Study

250 nodes are randomly deployed in a $100 * 100 * 100$ m³ region for monitoring the environment. The maximum sensory distance $R_{S} = 20$ m and sensory deviation angle $α = π / 4$ . As shown in Figure 6, we record the quality of coverage in directional sensor networks as IPA3D algorithm is running in different time step. The asterisks represent sensor nodes. Due to that the simulation environment is a 3D cube; it is difficult to present the variation of global coverage intuitively from the 3D figure. Therefore, I chose to give the coverage variation of bottom side in Figure 6. During the initialization, only a few nodes cover the bottom of cube, which is shown in Figure 6(a), where the asterisks represent the nodes. Along with the running of IPA3D algorithm, some nodes that did not cover the bottom of the cube at first change their sensing directions, which results in that their sensing region now covers the bottom of the cube. At this moment, new asterisks representing those nodes appear. In a word, no extra nodes are added into that region, neither have they moved. We can see from Figure 6(a), the initial degree of coverage is 45.3%, overlap region and fade zone are significant in network for the randomness of deployment. By means of the optimization algorithm, the direction of nodes adjusts continuously as time goes on, which in consequence improves the network coverage extent, as shown in Figures 6(b) and 6(c). When the time step comes up to 60 times, the degree of coverage reaches 94.29% which increases 49 percentage points to the initial coverage, as shown in Figure 6(d).

Figure 6

Coverage optimization under IPA3D algorithm.

5.2. Algorithm Convergence Analysis

We carry out a group of experiments with five kinds of network node scale so as to analyze IPA3D algorithm convergence. According to every network node scale, we randomly produce 20 topological structures, respectively, and calculate the algorithm convergence times and average. Experimental data are shown in Table 2 with parameters $R_{S} = 20$ m, $α = π / 4$ .

Table 2

Convergence analysis on experimental data.

Number of nodes N	Initial degree of coverage %	Ultimate degree of coverage %	Cycle index t
100	18.30	42.15	74.5
150	27.42	61.53	77.7
200	38.65	81.77	75.6
250	46.32	93.59	78.9
300	52.51	95.14	72.3

Based on the above analysis we can reach a conclusion that the convergence of IPA3D algorithm, that is, the adjustment number of times, does not change conspicuously along with sensor network node scale. The value ranges from 70 to 80; thus IPA3D algorithm has a nice convergence.

5.3. Comparative Analysis of Algorithms

In this section, a series of simulation experiments are conducted to illustrate the effect on the performance of IPA3D algorithm from the three key parameters. They are node scale N, maximum sensory distance $R_{S}$ , and sensory deviation angle α. Reference [9] takes traditional basis as the criterion for the generation of repulsion. We compare it to the coverage enhancement algorithm proposed in this paper and analyze their performances.

It can be seen from the curve in Figure 7 that when $R_{S}$ and α are fixed, smaller value leads to less initial degree of coverage. With the increasing of node scale N, the value of $Δ p$ shows an upward trend. $Δ p$ means the difference between the final degree of coverage and the initial state. When $N = 250$ , the degree of coverage increases 49 percentage points and afterwards value of $Δ p$ decreases to some extent. The reason is that when nodes number reaches a certain scale, optimized network degree of coverage has approached extreme and increase of node number can no longer enhance network coverage conspicuously. Meanwhile, the increase of nodes leads to a higher initial degree of coverage and greatly decreases the probability that several communicational adjacent nodes form coverage fade zone which undoubtedly weakens the performance of IPA3D algorithm.

Figure 7

Effect on node scale N on condition of $R_{S} = 20$ m, $α = π / 4$ .

We can see from the curve in Figures 8 and 9 that the effect on this algorithm from maximum sensory distance of nodes $R_{S}$ and sensory deviation angle α is in accordance with the node scale. When the node scale is fixed, the smaller maximum sensory distance of nodes $R_{S}$ and sensory deviation angle α are, the less possible that adjacent nodes are form an overlap region, and the less improvement is done to the network coverage performance. As the increase of maximum sensory distance of nodes, $Δ p$ increases constantly too. The network degree of coverage reaches the climax when $R_{S}$ and α are at a particular value. However, with the increase of the value of $R_{S}$ and α, the probability of creating coverage fade zone becomes smaller which leads to less significant effect on network degree of coverage enhancement.

Figure 8

Effect on maximum sensory distance of nodes $R_{S}$ on condition of $N = 200$ , $α = π / 4$ .

Figure 9

Effect on sensory angle of deviation α on condition of $N = 200, R_{S} = 20$ m.

As can be seen from Figures 7, 8, and 9 that compared to the PECEA algorithm in [9], under the same parameter value, the proposed IPA3D algorithm increases the coverage quality most significantly after the optimization of the initial deployment, which illustrates the superiority of this algorithm.

5.4. Analysis on Coverage Impact Factor

In this paper, we introduced coverage impact factor and use it to judge the impact on degree of coverage from the change of sensing direction angle and thereby to decide whether the node sensing direction angle should rotate. We illustrate the impact through a series of simulation experiments with $R_{S} = 20$ m, $α = π / 4$ .

Figure 10 shows the impact from coverage impact factor on algorithm in different node scales. According to three different network node scales, 10 topologic structures are randomly generated. Record the changes of network degree of coverage when algorithm is running and average. From the curves in Figure 10 we can see, in the first 30 loops of algorithm that the degree of coverage increases sharply and exponentially. So adding coverage impact factor or not has little impact on algorithm performance. However, with the increase of algorithm execution time, algorithm degree of coverage without coverage impact factor presents a fluctuating state and overall degree of coverage stops increasing while algorithm degree of coverage with coverage impact factor shows a gentle rising trend and finally reaches stable state with degree of coverage remaining unchanged. The reason is that, without coverage impact factor, the force on a single node is according to neighbor nodes set $ψ_{i}$ and the change of sensing direction angle of a single node cannot take the impact on overall network coverage into account and may reduce network degree of coverage. And algorithm with coverage impact factor will evaluate the impact on overall coverage every time before sensing direction is changed to get rid of profitless rotation. Though it may increase algorithm complexity and cost node energy, it is greatly less than the energy cost of profitless rotation which means movements that cannot give beneficial effect to network coverage. As shown in Figure 10, to add coverage impact factor efficiently improved the performance of coverage enhancement algorithm and overcame the fault of the unstable state in later stage.

Figure 10

Impact on algorithm performance from coverage impact factor in different node scale.

6. Conclusions

This paper proposed a probability-based three-dimensional directional sensory model, and based on which a novel criterion for judgment is proposed in view of the irrationality that traditional virtual potential field algorithms brought about on the criterion for the generation of virtual force. Cross-set test was used to determine whether the sensory region has any overlap and coverage impact factor is introduced to reduce profitless rotation from coverage optimization, thereby the energy cost of nodes was restrained and the performance of the algorithm was improved. In simulation experiment, first we verified the convergence of the algorithm and then the effect on the algorithm from the key parameters and the validity of IPA3D were demonstrated by the comparison between IPA3D and PECEA under the effect of key parameters. Also, we confirmed and analyzed the impact on IPA3D algorithm from coverage impact factor through simulation experiment. The proposed algorithm effectively improved the coverage performance of traditional virtual potential field algorithms but the energy consumption caused by the change of sensing direction angle were not taken into account which is for further study.

Footnotes

Acknowledgments

The subject is sponsored by the National Natural Science Foundation of China (Nos. 60973139, 61003039, 61170065, and 61171053), Scientific and Technological Support Project (Industry) of Jiangsu Province (Nos. BE2010197, BE2010198), Natural Science Key Fund for Colleges and Universities in Jiangsu Province (11KJA520001), the Natural Science Foundation for Higher Education Institutions of Jiangsu Province (10KJB520013, 10KJB520014), Academical Scientific Research Industrialization Promoting Project (JH2010-14), Fund of Jiangsu Provincial Key Laboratory for Computer Information Processing Technology (KJS1022), Postdoctoral Foundation (1101011B), Science and Technology Innovation Fund for Higher Education Institutions of Jiangsu Province (CXZZ11-0409), the Six Kinds of Top Talent of Jiangsu Province (2008118), Doctoral Fund of Ministry of Education of China (20103223120007, 20113223110002), and the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions (yx002001).

References

Meguerdichian

Koushanfar

Potkonjak

Srivastava

M. B.

Coverage problems in wireless ad-hoc sensor networks

Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '01)

April 2001

New York, NY, USA

IEEE Press

1380 1387

10.1109/INFCOM.2001.916633

2-s2.0-0034997317

Tao

Sun

Chen

H. J.

Worst-case coverage detection and repair algorithm for video sensor networks

Acta Electronica Sinica 2009 37 10 2284 2290

2-s2.0-70749133657

Akyildiz

I. F.

Melodia

Chowdhury

K. R.

A survey on wireless multimedia sensor networks

Computer Networks 2007 51 4 921 960

2-s2.0-33845708421

10.1016/j.comnet.2006.10.002

Howard

Mataric

M. J.

Sukhatme

G. S.

Mobile sensor network deployment using potential field: a distributed scalable solution to the area coverage problem

Proceedings of the 6th International Symposium on Distributed Autonomous Robotics Systems (DARS '02)

June 2002

Fukuoka, Japan

299 308

Poduri

Sukhatme

G. S.

Constrained coverage for mobile sensor networks

Proceedings of the IEEE International Conference on Robotics and Automation

May 2004

New York, NY, USA

IEEE Press

165 171

2-s2.0-3042582668

Zou

Chakrabarty

Sensor deployment and target localization in distributed sensor networks

ACM Transactions on Embedded Computing Systems 2004 3 1 61 91

Abouzeid

A. A.

Coverage by directional sensors in randomly deployed wireless sensor networks

Journal of Combinatorial Optimization 2006 11 1 21 41

2-s2.0-32944460423

10.1007/s10878-006-5975-x

S. J.

C. F.

Z. H.

Pan

Y. H.

Optimal deployment and protection strategy in sensor network for target tracking

Acta Electronica Sinica 2006 34 1 71 76

2-s2.0-33646336908

Tao

H. D.

Liu

A virtual potential field based coverage-enhancing algorithm for directional sensor networks

Journal of Software 2007 18 5 1151 1162

2-s2.0-34347213027

10.1360/jos181152

10.

Cai

Y. L.

Lou

M. L.

X. Y.

Target-oriented scheduling in directional sensor networks

Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM '07)

May 2007

Anchorage, Alaska, USA

1550 1558

2-s2.0-34548314593

10.1109/INFCOM.2007.182

11.

Huang

J. J.

Shi

Sun

L. J.

Wang

R. C.

Huang

H. P.

An improved algorithm of virtual potential field in directional sensor networks

Key Engineering Materials Journal 2011 467–469 1562 1568

2-s2.0-79952557756

10.4028/www.scientific.net/KEM.467-469.1562

12.

H. D.

Liu

Y. H.

Correlation based video processing in video sensor networks

Proceedings of the IEEE International Conference on Wireless Networks, Communications and Mobile Computing (WirelessCom '05)

June 2005

Beijing, China

987 992

2-s2.0-34547648195

10.1109/WIRLES.2005.1549547

13.

H. D.

Tao

Multimedia sensor network and its research progresses

Journal of Software 2006 17 9 2013 2028

2-s2.0-33750457389

10.1360/jos172013

14.

Zhao

M. C.

Lei

J. Y.

M. Y.

Liu

Shu

Surface coverage in wireless sensor networks

Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM '09)

April 2009

Rio de Janeiro, Brazil

109 117

2-s2.0-70349675589

10.1109/INFCOM.2009.5061912

15.

Adriaens

Megerian

Potkonjak

Optimal worst-case coverage of directional field-of-view sensor networks

Proceedings of the 3rd Annual IEEE Communications Society on Sensor and Ad hoc Communications and Networks (Secon '06)

September 2006

336 345

2-s2.0-43849097383

10.1109/SAHCN.2006.288438

16.

Cardei

Thai

M. T.

Energy-efficient target coverage in wireless sensor networks

Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05)

March 2005

Boca Raton, Fla, USA

1976 1984

2-s2.0-25844504705

17.

Xiao

Huang

Shi

J. H.

Yang

Peng

Full connectivity and probabilistic coverage in random deployed 3D WSNs

Procedings of the International Conference on Wireless Communications and Signal Processing, (WCSP '09)

November 2009

Kunming, China

12 1 4

2-s2.0-77749331969

10.1109/WCSP.2009.5371666

18.

Huang

J. J.

Sun

L. J.

Wang

R. C.

Huang

H. P.

Virtual potential field and covering factor based coverage-enhancing algorithm for three-dimensional wireless sensor networks

Journal on Communications 2010 31 9 16 21

2-s2.0-78149490662

19.

H. D.

Zhang

Ming

A. L.

A coverage-enhancing method for 3D directional sensor networks

Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM '09)

April 2009

Rio de Janeiro, Brazil

2791 2795

2-s2.0-70349675308

10.1109/INFCOM.2009.5062233

20.

Zhang

D. X.

Chen

Y. W.

Wang

Probabilistic coverage configuration for wireless sensor networks

Proceedings of the International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM '06)

September 2006

Changsha, China

1 4

2-s2.0-37649031819

10.1109/WiCOM.2006.261

21.

Sheu

J. P.

Lin

H. F.

Probabilistic coverage preserving protocol with energy efficiency in wireless sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '07)

March 2007

Kowloon, China

2631 2636

2-s2.0-36348967336

10.1109/WCNC.2007.489

22.

Bai

Zhang

Xuan

Jia

Full-coverage and k-connectivity (

k = 14, 6

) three dimensional networks

Proceedings of the IEEE Annual Conference on Computer Communications (INFOCOM '09)

April 2009

Rio de Janeiro, Brazil

145 154

10.1109/INFCOM.2009.5061943

23.

Alam

S. M. N.

Haas

Z. J.

Coverage and connectivity in three-dimensional networks

Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MOBICOM '06)

September 2006

Los Angeles, Calif, USA

346 357

2-s2.0-33751061514

24.

Suda

Coverage-aware self-scheduling in sensor networks

Proceedings of the Annual Workshop on Computer Communications (CCW '03)

October 2003

California, Calif, USA

IEEE

117 123

2-s2.0-1542318357

25.

Pescaru

Istin

Curiac

Doboli

Energy saving strategy for video-based wireless sensor networks under field coverage preservation

Proceedings of the IEEE International Conference on Automation, Quality and Testing, Robotics (AQTR '08)

May 2008

Cluj-Napoca, Romania

289 294

2-s2.0-51949087325

10.1109/AQTR.2008.4588754

Improved Virtual Potential Field Algorithm Based on Probability Model in Three-Dimensional Directional Sensor Networks

Abstract

1. Introduction

2. Coverage Enhancement Issues of Three Directional Sensor Networks

2.1. Problem Formulation

2.2. Analysis and Definitions on Coverage Enhancement Issue in Directional Sensor Networks

Definition 1 (directional sensor model 〈 L , R S , D ⃗ , α 〉 ).

Definition 2 (probability detection model).

Definition 3 (maximum sensory distance R S ).

Definition 4 (sensory domain of node s i ).

Definition 5 (Set of neighbor nodes ψ i ).

Definition 6 (γ-probability coverage).

Definition 7 (degree of coverage).

Definition 8 (coverage impact factor).

3. The Improved Virtual Potential Field-Based Algorithm in Three-Dimensional Directional Sensor Networks

3.1. Judgement on Overlap Situation of Sensory Area

3.2. Analysis on Regulation of Node Rotation

3.2.1. Analysis on Regulation of Centroids

3.2.2. Analysis on Rotation Angle

4. Algorithm Description

Algorithm 1

5. Algorithm Simulations and Performance Analysis

5.1. Case Study

5.2. Algorithm Convergence Analysis

5.3. Comparative Analysis of Algorithms

5.4. Analysis on Coverage Impact Factor

6. Conclusions

Footnotes

Acknowledgments

References

Definition 1 (directional sensor model $〈 L, R_{S}, \vec{D}, α 〉$ ).

Definition 3 (maximum sensory distance $R_{S}$ ).

Definition 4 (sensory domain of node $s_{i}$ ).

Definition 5 (Set of neighbor nodes $ψ_{i}$ ).