Advanced
Practical Node Deployment Scheme Based on Virtual Force for Wireless Sensor Networks in Complex Environment
Practical Node Deployment Scheme Based on Virtual Force for Wireless Sensor Networks in Complex Environment
KSII Transactions on Internet and Information Systems (TIIS). 2015. Mar, 9(3): 990-1013
Copyright © 2015, Korean Society For Internet Information
  • Received : August 02, 2014
  • Accepted : January 26, 2015
  • Published : March 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Lu Wei
School of Computer Science and Engineering, Nanjing University of Science and Technology Nanjing - China
Yang Yuwang
School of Computer Science and Engineering, Nanjing University of Science and Technology Nanjing - China
Zhao Wei
School of Computer Science and Engineering, Nanjing University of Science and Technology Nanjing - China
Wang Lei
School of Computer Science and Engineering, Nanjing University of Science and Technology Nanjing - China

Abstract
Deploying sensors into a target region is a key issue to be solved in building a wireless sensor network. Various deployment algorithms have been proposed by the researchers, and most of them are evaluated under the ideal conditions. Therefore, they cannot reflect the real environment encountered during the deployment. Moreover, it is almost impossible to evaluate an algorithm through practical deployment. Because the deployment of sensor networks require a lot of nodes, and some deployment areas are dangerous for human. This paper proposes a deployment approach to solve the problems mentioned above. Our approach relies on the satellite images and the Virtual Force Algorithm (VFA). It first extracts the topography and elevation information of the deployment area from the high resolution satellite images, and then deploys nodes on them with an improved VFA. The simulation results show that the coverage rate of our method is approximately 15% higher than that of the classical VFA in complex environment.
Keywords
1. Introduction
T his paper is aimed to study the issue of node deployment in Wireless Sensor Networks (WSNs). Deployment is closely related to the accuracy, completeness and efficiency of sensory information retrieval. However, most researches on the sensor network deployment algorithms are confined to the laboratory or on paper because it is very expensive to deploy nodes in a real environment. Fortunately, with the rapid development of high-resolution satellite images, it is possible to deploy sensor nodes on them, which would be more practical than the previous approaches. The geographic information such as elevation and land cover types can be obtained from the satellite images. Therefore, this is a new approach to design and evaluate the deployment algorithms in the practical environment.
Satellite images generally refer to the pictures taken by satellites in space. Satellite images are used in different fields such as the military command, disaster relief, fire protection and other natural disaster monitoring. Senlet et al. [1] used satellite maps for precise localization of a mobile robot on sidewalks. In order to attain globally corrected localization results, they combined the stereo camera images, visual odometry, satellite map matching and a sidewalk probability transfer function obtained from the street maps. When the satellite images are used, the first issue is how to extract the information from the images. Nowadays, the classification and segmentation techniques for satellite images can be used to extract variant land cover types from the satellite images, such as water, grass, rock. Wilkinson et al. [2] presented a classical scheme for feature classification of the satellite images. Recently, there have also been researches [3] [4] on the classification algorithms for high-resolution satellite images. In this paper, we extract the topography information from the satellite images, so some classical methods for classification and segmentation are used.
The deployment problem of mobile WSNs is also encountered during the deployment of mobile robots. Some universities and scientific research institutions have done lots of related work, and many algorithms [5] are proposed. The deployment methods can be roughly classified into three categories: the methods based on the geometric model [8] , the methods based on the virtual potential field [9] and the methods based on the biological intelligence [10] . The method proposed in this paper belongs to the second category. This kind of algorithm uses the artificial potential fields for the self-diffusion of mobile nodes. Each node in the network is regarded as a virtual positive electric charge, which is repelled by the boundaries, obstacles and other nodes. All the nodes in the network area tend to spread to other places under the force of repulsion. In the meantime, these nodes need to avoid spreading out of the boundary. Finally, they reach an equilibrium state, which means the driven force equals to the resistance of each node. The advantage of this algorithm is that it is simple and straightforward to use, which can quickly achieve the purpose of spreading nodes to the whole sensing area. Moreover, each node has a short moving distance. On the other hand, the disadvantage is that it is easy to fall into local optimal solution [12 - 18] .
One of the most classic literatures based on the virtual potential field method was written by Howard et al. [12] , in which they provided a solution to the problem of deploying a mobile sensor network in unknown dynamic environments. Concretely, they described a potential-field-based approach for node deployment, in which nodes are regarded as virtual particles, and these nodes are subject to the virtual forces. These forces repel nodes from each other, and the obstacles. Moreover, these forces ensure that, from an initial compact state, nodes could spread out to maximize the coverage area of the network. In addition to these repulsive forces, nodes are also subject to a viscous friction force. This force is used to ensure that the network will eventually reach the state of static equilibrium. Similarly, the Virtual Force Algorithm (VFA) in [13] and the virtual spring force algorithm in [18] use both the repulsive and attractive force components to maximize coverage and uniformity for sensors.
In traditional VFA scheme, it is assumed that the sensing radius of each sensor node is the same. However, in some practical environment, the sensor nodes may locate in different terrains, so the transmission radius may be different. This paper proposes a deploy method for complex environment. Compared with previous methods, the main innovations and contributions of this paper are listed as follows:
  • 1) We propose a deployment method based on the satellite images. Firstly, we extract the information of land cover types, area and height from the satellite images according to the locations at deployment fields. Then we convert the information into a deployment map, which is provided for the proposed virtual deployment method. In other words, the deployment can provide guidance for the practical deployment.
  • 2) We propose an improved VFA suitable for deployment in the complex environment. The traditional virtual force algorithm is not suitable for deployment in such environment, so we put forward the improved VFA to implement the deployment. Then, through simulation, we evaluate the performance of the algorithm.
The remainder of this paper is organized as follows: Section 2 proposes the improved VFA suitable for virtual deployment in complex environment; Section 3 introduces the procedures for the classification and preprocessing of satellite images; Section 4 presents the virtual deployment scheme in detail. Moreover, we will evaluate both the proposed deployment algorithm and the existing classical algorithms through simulations; finally, Section 5 concludes the paper and points out the direction for future works.
2. VFA for Virtual-Deployment
In our virtual-force-based approach, the sensor nodes are modeled as points subject to the attractive or repulsive force according to the distance between every two sensors. By setting a threshold of desired distances between sensors, each sensor moves following the summation of the force vectors and achieves a uniform deployment eventually [19] .
We try to overcome the limitations of previous approaches. In these approaches, a large communication range, a dense network, the obstacle-free fields and the full knowledge of the field layout are assumed. Based on the literatures [12] , we put forward the new VFA. Each node in the deployment field is subject to four virtual forces:
  • 1) Virtual forceFnamong sensor nodes;
  • 2) Attractive forceFmcaused by uncovered area;
  • 3) Repulsive forceFobetween nodes and obstacles;
  • 4) Repulsive forceFbbetween nodes and boundaries.
- 2.1 VFA for Virtual-Deployment
Assume that there exists attractive and repulsive virtual force between any pair of adjacent nodes in the sensor networks. The virtual force on node si due to sj is Fij ( j = 1,2,..., k sj SNi , and SNi is a collection of Si 's neighbors).
PPT Slide
Lager Image
In Eq. (1), dij denotes the Euclidean distance between nodes si and sj ( sj is an adjacent node of si , so dij < Rc , Rc refers to communication radius), and dth is the threshold distance. ωA and ωR denote the attraction and repulsion coefficients respectively [16] . The total force on node si due to its neighbors can be computed with Eq.(2).
PPT Slide
Lager Image
- 2.2 Attractive Force from Uncovered Area
To calculate the attractive force caused by an uncovered area, we divide the target area uniformly to form discrete virtual grids. Nodes are subject to an attractive force produced by those uncovered grids between the sensing radius Rs and the communication radius Rc . We define M as the total number of virtual grids in a region and um as the m -th grid. Consequently, um attracts sensor si if it is uncovered. Assuming that each virtual grid carries a unit of charge, and the charge number of sensor nodes is equal to the square of the sensing radius Rs , then,
PPT Slide
Lager Image
In Eq. (3), qi and qm denote the electric charges carried by node si and grid um respectively. k is Coulomb's Constant and we set k = 1. Rs refers to the sensing radius, and Rc stands for communication radius, where dim denotes the Euclidean distance between grid um and node si . Note that only the uncovered grids have attractive force on sensor nodes. At the same time, we clip the virtual force to the domain Rs < dim Rc for the purpose of distributed processing of local network. Finally, N stands for the total number of sensor nodes and Si represents the effective coverage of node i .
- 2.3 Repulsive Force from Obstacles
The sensor nodes may be blocked by obstacles, which must be avoided during the deployment. A feasible approach is to regard obstacles as high potential fields. Then, sensor nodes could be repelled and kept away from the obstacles. Assume that the number of charges on per unit length of obstacles is equal to that of sensor node. Thus, Fio can be calculated with Eq. (4).
PPT Slide
Lager Image
In Eq. (4), qi and qo denote the electric charges carried by node si and point o at the obstacles’ edge respectively. The number of electric charges at point o is equal to Rs . dio is the Euclidean distance between node i and point o . doth stands for the obstacle threshold distance, and nodes are subject to the repulsive force if dio < doth . Finally, α represents the proportionality coefficient for force adjustment.
- 2.4 Repulsive Force from Boundaries
During the process of deployment, we need to constrain the size of deployment region to prevent nodes from spreading out of the fields. Similar to the approach for obstacles mentioned above, the region boundaries should also be taken as high potential fields so as to keep the nodes within the area. Assume that the number of charge on per unit length of boundaries is equal to that of the sensor nodes. Thus:
PPT Slide
Lager Image
In Eq. (5), qi and qo denote the electric charges carried by sensor node si and point b at the boundaries respectively. And the number of electric charges at point b is equal to Rs . dib is the Euclidean distance between node i and point b . dbth stands for the boundary threshold distance. Finally, β represents the proportionality coefficient for force adjustment.
- 2.5 Coverage and Threshold Distance Optimization
The concept of coverage was introduced by Gage et al. [20] . Coverage is fundamentally related to the effectiveness of monitoring an environment with a given set of sensors. Generally, coverage is considered as a metric of QoS for a sensor network.
According to the former VFA, we make a collection of discrete grids throughout the deployment area. Assume the total number of grids within deployment area is Mall , and the total number of grids covered by the sensor nodes is Mc . So coverage C can be computed by Eq. (6).
PPT Slide
Lager Image
By setting the values of dth , we can ensure that the nodes cover the deployment area in a certain density, or the deployment area coverage can be adjusted. However, if dth is too small, the sensor node layout will be so tight that there is no guarantee to meet the coverage requirement. Contrarily, if dth is too large, the sensor node will be sparse, and then it may cause coverage holes, as shown in Fig. 1 (a).
PPT Slide
Lager Image
Effect of dth and dbth on coverage
Consider Fig. 1 (b), three sensor nodes s 1 , s 2 and s 3 overlap and intersect at point O . Although there is some overlapped area, Fig. 1 (b) doesn’t have coverage hole as that in the Fig. 1 (a). After calculation, the distance between them in Fig. 1 (b) is
PPT Slide
Lager Image
. Similarly, the distance between nodes and boundaries is 0.5 Rs , so is the distance between nodes and obstacles. Thus, we set the threshold distance dth to be
PPT Slide
Lager Image
, the obstacle threshold distance doth to be 0.5 Rs , and the boundary threshold distance dbth to be 0.5 Rs .
- 2.6 Virtual Force Analysis for Sensors
Consider the scenario shown in Fig. 2 , there are four sensors s 1 , s 2 , s 3 and s 4 randomly deployed in a region, with obstacle O and boundary B . Then we analyze the virtual forces applied on these sensor nodes.
PPT Slide
Lager Image
Virtual force demonstration of 4 sensors
The total force of sensor node s 1 can be represented as
PPT Slide
Lager Image
, where
PPT Slide
Lager Image
denotes the force on s 1 due to other nodes. Assume that the threshold distance dth =
PPT Slide
Lager Image
, d 12 > dth , d 13 > dth , and d 14 = dth . Thus, s 1 is subject to the virtual attractive force due to s 2 and the virtual repulsive force due to s 3 , and there is no force from s 4 .
PPT Slide
Lager Image
stands for the attractive force on s 1 due to the uncovered region represented by the shadow grids, which satisfies the condition Rs < d 1m Rc .
PPT Slide
Lager Image
represents the repulsive force on s 1 due to obstacles, and it is zero because the distance is greater than doth = 0.5 Rs . Finally,
PPT Slide
Lager Image
represents the repulsive force on s 1 due to the boundaries. For the same reason, it is also zero.
3. Satellite Image Classification and Preprocessing
In this section, we introduce how to obtain the information from the satellite images. First of all, these images are used to extract information such as the land cover types and elevation. Then, by using the information, we make a deployment map, and finish our deployment work on it, as described in the next section.
The satellite images represent the real geographic features. Therefore, they can be used to obtain the information of the ground and learn such information as the geography, topography. This kind of information can also be applied for node deployment. The shape of deployment area is varied, and the terrain surface is complex and changeable. We chose Google satellite images as the source of regional information for our deployment work. Concretely, we need to preprocess the satellite images, calculate the deployment area, and extract the information, such as the land cover and elevation. Moreover, the obstacles and boundaries should be marked.
- 3.1 Selecting Deployment Area
We use latitude and longitude to mark the locations on satellite maps. We select two typical areas, as shown in Fig. 3 (a) and Fig. 3 (b) respectively. In region A, there is some area covered by water, which represents the regions with unreachable obstacles. Region B is a fluctuant terrain which includes a number of abrupt slopes. When sensor nodes try to move in such kind of terrain, they require more energy to overcome gravity. Therefore, these two regions are representative in our research.
PPT Slide
Lager Image
Deployment area: Region A and Region B
The detailed parameters of these two regions are listed in Table 1 .
Parameters of the deployment area
PPT Slide
Lager Image
Parameters of the deployment area
- 3.2 Information Extraction from Deployment Area
We need to consider the land cover types of deployment area for the mobile node deployment. For example, the sensor nodes consume different energy in different terrains, and it is not suitable to deploy nodes in water. Therefore, in order to be closer to the real environment, we should classify the satellite images with features. Another important data is the height of the deployment area, which can be obtained through the satellite elevation maps. After getting these information, we can utilize them to make a deployment map for further deployment.
Step 1: Extract the Land Cover
In this section, the goal is to use a classification and segmentation algorithm to extract the land cover types, such as water, rocks, grass, mud.
The algorithm we used is the K-means algorithm of ANN (Artificial Neural Network) [21] . It starts with some clusters of pixels in the feature space, each of them defined by its center. The first step is to allocate each pixel to the nearest cluster. In the second step, the new centers are computed with the new clusters. These two steps are repeated until convergence [22] . Fig. 4 shows the resulting plots of segmentation and classification on Fig. 3 after using the K-means algorithm.
PPT Slide
Lager Image
Resulting plots of segmentation and classification after using K-means Algorithm
Step 2: Obtain Elevation Map
The aim of obtaining the elevation information is to compute the nodes’ energy consumption during the process of deployment. The elevation information is obtained from GE (Google Earth). This software provides us with an interface to download the information of latitude, longitude, altitude, tilt, etc. By specifying a target deployment area of screen coordinates ( x , y ) , we can obtain the elevation information of corresponding points on the satellite map. X × Y represents the size of the satellite image. shows the process:
PPT Slide
Lager Image
Where, Z ( i , j ) denotes the elevation corresponding to the map coordinates ( i , j ) in the picture. After obtaining all ( X , Y , Z ) coordinates, we can plot the 2 D and 3 D figures for Region A and Region B, as shown in Fig. 5 and Fig. 6 respectively.
PPT Slide
Lager Image
2D elevation maps (a) and 3D elevation maps (b) of Region A
PPT Slide
Lager Image
2D contour maps (a) and 3D elevation maps (b) of Region B
These 2D and 3D elevation maps can help us learn the difference in the terrains of the deployment area, which is useful when we plan to deploy nodes in those areas. In accordance with Fig. 5 , the east terrain is high, while west terrain is low. The apex is approximately 40 meters high, and the lowest point is about 20 meters high. Thus, the drop height is about 20 meters. Fig. 6 shows that the highest elevation is about 70 meters, and the lowest is 25 meters, so the drop height is about 45 meters.
- 3.3 Making Deployment Map
In this section, we will make a deployment map that not only contains the land cover information but also the elevation information, and at the same time, the unreachable regions are marked. After putting the land cover map and elevation map together, we could achieve the deployment map, as shown in Fig. 7 .
PPT Slide
Lager Image
Making a deployment map of Region A
Fig. 7 shows that the deployment map which contains both the land cover and elevation information, which also marks the unreachable areas (such as water). This deployment map will be used for the deployment in next section.
4. Deployment and Results
In this section, we will finish the deployment on the deployment map as shown in Fig. 7 . The main contents of this section can be divided into 5 parts. 1) We need to estimate the total number of needed nodes before deployment according to the size of deployment area and the node sensing radius. 2) We introduce the node deployment steps for the VFA. 3) The sensors are deployed with a random deployment strategy and a manual deployment strategy, and the deployment results are compared. 4) The trajectory and the energy consumption of the node deployment are analyzed. 5) Finally, the deployment result is shown on a Google satellite map.
- 4.1 Calculate the Total Number of Needed Nodes
Coverage is critical for WSNs to monitor a region of interest and to provide a good QoS. In many practical scenarios, full coverage is required, which means that every point inside the region (excluding the obstacles) should be covered by at least one sensor. In this paper, one of our aims is to use the sensors to achieve maximal coverage for Region A and Region B.
Literatures [24] and [25] independently drew an important conclusion: if a convex area is completely covered by a set of nodes, these nodes must be connected when the condition Rc ≥ 2 Rs is satisfied, and the coverage and connectivity must be guaranteed. Therefore, they assumed that Rc = 2 Rs . In this paper, we also make the same assumption.
R. Kershner [26] proved the Disc Covering theorem: Let M denote a bounded plane point set and let N ( є ) be the minimum number of circles of radius є which can cover M . Then,
PPT Slide
Lager Image
Where,
PPT Slide
Lager Image
denotes the closure of M . Because the left side of Eq. (7) is simply the total area of the circles covering M , the constant
PPT Slide
Lager Image
can be regarded as measuring the proportion of unavoidable overlapping. In this paper, the sensing radius Rs is equal to radius є in Eq. (7).
Under the ideal propagation conditions, a radio wave propagates in free space and won't produce a reflection or scattering, so the energy cannot be absorbed by the obstacles. However, in the real environment, the communication radius Rc will change in accordance with different terrain surface. Assume that the sensing radius is proportional to the communication radius, thus the sensing radius Rs varies with different terrains. The actual distance of communication relates to the transmission power, receiver sensitivity, the working frequency and the environment, which can be expressed by Eq. (8).
PPT Slide
Lager Image
Where, FL refers to the free space loss, d refers to the distance between two points, f is the working frequency, and EL is the attenuation caused by the environment. Assume that there are K land cover types in the deployment area, and according to Eq. (7), the number of nodes can be calculated by Eq. (9).
PPT Slide
Lager Image
In Eq. (9), N is the total number of required nodes. A ( i ) represents the area of each land cover types, and Rs ( i ) denotes the sensing radius. We list the parameters in Table 2 .
Deployment Parameters
PPT Slide
Lager Image
Deployment Parameters
Now we provide an example of calculating the number of required nodes due to forest in Region A. Put parameters in Table 2 into Eq. (8), and we obtain:
PPT Slide
Lager Image
We can obtain d = Rc = 86.7 m with Eq. (10), so Rs = 43.3 m since Rc = 2 Rs . According to Table 1 and Table 2 , we know that the forest accounts for more than 22.3%, and A=230,153 m 2 . Then, we could compute N (forest)=10.5 ≈ 11 with Eq. (8). Similarly, we could get the number of other corresponding nodes, which are listed in Table 3 .
Sensor number andRc,Rs
PPT Slide
Lager Image
Sensor number and Rc , Rs
- 4.2 Simulation Steps of Deployment
After getting the total number of required nodes for deployment, we can start the deployment work. For convenience, Region A is divided into Mall =539×427 grids, and the division of Region B is Mall =505×421, so that each small grid represents 1 m 2 . In accordance with the proposed improved VFA, we conduct simulation with Matlab. shows the steps of the virtual force algorithm.
PPT Slide
Lager Image
We select Region A and Region B as our target areas, while the dots represent the sensor nodes, and the circles denote the sensing radius. K is set to be 500. The simulation parameters are shown in Table 4 .
Simulation parameters
PPT Slide
Lager Image
Simulation parameters
- 4.3 Manual Deployment and Random Deployment
The scheme of deploying the sensor networks vary in practical application. It can be predetermined when the environment is sufficiently known and under control. The sensors can be strategically deployed manually. In this case, all the sensors will be deployed into an initial position, and then these nodes move to their destinations respectively. And the deployment can also be a priori undetermined when the environment is unknown or hostile. In this case, the sensor deployment cannot be pre-planned and must be performed manually. The sensors may be airdropped from an aircraft or deployed through other means. Such strategy can be considered as random deployment [27] .
In this section, we perform the deployment of Region A and Region B with both the manual and random strategies respectively.
Fig. 8 (a) shows the initial configuration of nodes. All the nodes are randomly deployed in the field. After 500 iterations, all nodes reach the final configuration, as shown in Fig. 8 (b). In accordance with Fig. 8 (b), we observe that the node sensing radius Rs is different in different land cover types. The blue areas in the figure refer to water, marked as obstacles, which are not suitable for deploying nodes. Therefore, the nodes try to avoid these obstacles during the deployment process, and the distance between nodes and obstacles is determined by the threshold distance doth . Thus, the nodes well cover Region A.
PPT Slide
Lager Image
Initial configuration (a) and final configuration (b) of Region A with Random Deployment strategy
In accordance with Fig. 9 , Region B does not have water in its terrain, and therefore, it has no obstacles compared to Region A. Fig. 9 (a) is the initial state of the network, and Fig. 9 (b) shows the final state after 500 iterations. From Fig. 9 (b), we observe that, because there is no obstacle, the nodes have more uniform distribution than those in Region A. By comparing Fig. 8 with Fig. 9 , we note that, although the two regions are of comparable sizes(Region A: 230,153 m 2 , Region B: 212,605 m 2 ), Region A deploys 36 nodes while Region B only deploys 30 nodes. Region B has a larger scope of rocky terrain, and the nodes in the rocky area that sense a radius Rs are larger than those in other areas, so fewer nodes are needed.
PPT Slide
Lager Image
Initial configuration (a) and final configuration (b) of Region B with Random Deployment Strategy
Fig. 10 shows the coverage curves of Region A and Region B. The coverage rate increases as the iteration numbers increases. Fig. 10 (a) is the coverage rate curve of Region A. Because the nodes do not need to cover the water areas, the maximum coverage is close to 97% (see Table 2 , the water area accounting for 2.7%). Fig. 10 (b) is the coverage rate curve of Region B, and coverage is close to 98% with the increasing iteration number. Compared to the traditional VFA and some classical deploy methods [28] , the proposed VFA could provide higher coverage rate in both Regions. The method based on Voronoi Diagram could achieve high coverage rate when the iteration number is less. When the iteration number becomes much, the proposed method outperforms the method based on Voronoi Diagram.
PPT Slide
Lager Image
Coverage of Region A (a) and coverage of Region B (b) with Random Deployment Strategy
Next, we deploy sensors in Region A and Region B with the manual deployment strategy. The initial locations of nodes can be arbitrarily chosen. In our experiments, we selected the lower left corner in the region as the initial position of nodes. With the progress of deployment, the nodes start spreading to other places from the lower left corner, which will cover the whole field at the end.
From Fig. 11 (a), we can see that the nodes are densely distributed in the lower left corner of Region A. At the end of the deployment process, the nodes reach the state as shown in Fig. 11 (b). Compared to Fig. 8 (b), the nodes’ moving tracks are much longer because they need to move farther from the initial position to spread to other areas. Also we can see that during the process of deployment, the nodes can successfully avoid obstacles (water).
PPT Slide
Lager Image
Initial configuration (a) and final configuration (b) of Region A with Manual Deployment Strategy
In Region B, the initial position of nodes is also located at the left bottom corner, as shown in Fig. 12 (a). With the deployment process, the nodes gradually diffuse to the other parts of the region and reach the final state, as shown in Fig. 12 (b). Because there are no obstacles in Region B, compared to Fig. 11 (b), the mobile trajectories of nodes are straighter. In addition, the nodes do not need to avoid the obstacles and change their directions.
PPT Slide
Lager Image
Initial configuration (a) and final configuration (b) of Region B with Manual Deployment Strategy
Fig. 13 (a) and Fig. 13 (b) show the coverage curves of Region A and Region B respectively with the manual deployment mode. Compared to the random deployment mode shown in Fig. 10 , it requires more time to reach the maximum coverage state, because the nodes need to move farther to get to their target place.
PPT Slide
Lager Image
Coverage of Region A (a) and coverage of Region B (b) with Manual Deployment Strategy
Through analysis and comparison of the two deployment modes, we can draw the following conclusion: the manual deployment mode requires longer time to reach the maximum coverage than the random deployment mode, i.e., the nodes need to move a longer distance to reach their final position under the manual deployment mode. In addition, if the initial location of nodes can be more evenly distributed in the deployment area, the deployment time can be reduced.
- 4.4 Trajectory and Energy Consumption Analysis
In this paper, we only focus on the energy consumption of sensor nodes during the deploy process. The proposed scheme and some other similar schemes are centralized schemes. After a powerful computer calculates the destination for each sensor node, these nodes will move to its position. Therefore, the energy required to move will be studied in this subsection.
Through deployment on the satellite map, we can estimate the energy consumption of nodes according to the actual terrain and height during the deployment process. The analysis of energy consumption can provide a valuable reference for practical deployment.
During the process of deployment, the energy consumed by nodes comes from two aspects: firstly, the nodes must consume energy to overcome the ground friction; secondly, the nodes must overcome gravity. The deployment area’s land cover is different, so the friction coefficient will be different. The friction coefficient used during the virtual deployment process is listed in Table 4 and the consumption of friction can be expressed by Eq. (11).
PPT Slide
Lager Image
Where, μ is the friction coefficient, m is the node mass, and g is the acceleration of gravity. L denotes the length of the nodes’ moving trajectory. The friction coefficient μ varies with different land cover types. The energy required to overcome gravity is as follows.
PPT Slide
Lager Image
In Eq. (12), Δ H   stands for height difference between the starting position to the end position. When a node moves from high position to low position, Δ H   is negative. From a practical perspective, Eg   should be set to be zero when Δ H   is negative. If the path from the starting position to the end position includes multiple uphill parts, Eg   is the sum of height differences of each uphill part.
We assume that the i -th node’s total energy consumption is
PPT Slide
Lager Image
, then
PPT Slide
Lager Image
where,
PPT Slide
Lager Image
and
PPT Slide
Lager Image
refer to the energy required by the node i to overcome the friction and gravity respectively. In the random deployment mode, because the initial position of each node i is random, so every distance it moved is not necessarily equal, and
PPT Slide
Lager Image
is not necessarily equal either. Assuming that the initial energy of each node is equal, the minimum value is E min , and we must satisfy Eq. (13) to ensure successful deployment.
PPT Slide
Lager Image
In Eq. (13), N is the total number of nodes within the target region. E min cannot represent the real situation through one virtual deployment, so we should calculate the average E min through multiple virtual deployments. And the more times we do, the closer E min is to the real case. For example, as in Region A, Fig. 14 shows the results after carrying out 500 times of random virtual deployment.
PPT Slide
Lager Image
Energy consumption of Region A with random deployment
Fig. (14) shows the energy consumption of nodes in Region A by using the random deployment mode, where Fig. 14 (a) and Fig. 14 (b) represent the energy required to overcome the gravity and friction respectively. Fig . 14 (c) shows the total energy consumption during the random deployment. Fig. 14 (d), Fig. 14 (e) and Fig. 14 (f) represent the nodes’ average energy consumption histogram after iterating for 500 times. In accordance with Fig. 14 (a), the energy required to overcome gravity is positive when a node moves from a low altitude to a high altitude. Moreover, the energy required to overcome gravity is zero when a node moves from a high altitude to a low altitude.
The selection of E min should refer to the Et mean in Fig. 14 (f). It is meaningful to determine the value of E min before real deployment, which can provide valuable reference to determine how much energy the nodes should carry initially.
Unlike the random deployment mode, the initial position of nodes is known and fixed in the manual deployment mode. The initial position invariant means that the result of each deployment is the same, i.e., the final location of the nodes is changeless. Then the path of each node traversed during the deployment process is also the same, which leads to constant power consumption. We choose Region B as the target area, and the trajectory and power consumption of the node in the manual deployment mode are shown in Fig. 15 .
PPT Slide
Lager Image
Energy consumption of Region B with manual deployment
Fig. 15 (a) shows the nodes’ moving trajectory and moving distance; Fig. 15 (b) shows the energy required for each node to overcome the gravity; Fig. 15 (c) shows the energy consumption for each node to overcome the friction; Fig. 15 (d) shows the straight-line distance between the nodes’ initial position and final position. It is easy to observe that the straight-line distance is shorter than the actual moving trajectory.
When the nodes are pre-deployed, its initial position and final position are prior known and fixed, so we can use the path optimization algorithm to optimize the node’s moving trajectory. This can realize the purpose of saving energy consumption. We use Lumelsky and Stepanov's path planning algorithm [32] called BUG2 to help a sensor move from a starting point to a destination point in a region with obstacles. And then the friction energy consumption Eμ can be optimized. By comparing the energy consumption before optimization in Fig. 15 (c) with the energy consumption after optimization in Fig. 15 (f), we observe that Eμ has significantly decreased after optimization. Finally, the selection of E min should refer to the maximal value of Eg + Eμ . After calculating the energy required for each node, the minimum initial energy E min could be determined. This result guarantees that the deployment method could finish with a high probability.
- 4.5 Deployment Effect on Satellite Image
The final effect of deploying nodes on satellite images is showed in Fig. 16 and Fig. 17 .
PPT Slide
Lager Image
Virtual deployment effect of Region A by using Random Deployment Mode
PPT Slide
Lager Image
Virtual deployment effect of Region B by using Manual Deployment Mode
Fig. 16 shows the initial state, middle state and final state of Region A, and the employed strategy is the random deployment mode. Fig. 17 shows the initial state, middle state, and final state of Region B, and the employed strategy the manual deployment mode.
6. Conclusion and Future Work
In this paper, we provide an improved VFA for node deployment in the complex environment. Moreover, we use the Google satellite maps to extract practical information such as the land cover and elevation. Then, based on these practical information, we evaluate the proposed algorithm. In accordance with the experimental results, the proposed algorithm could provide 15% higher coverage compared to the traditional VFA.
Compared to the real environment, the information obtained through satellite maps still has a few shortages. For example, the newest satellite map can only provide dated photographic images instead of real-time images. But the proposed method could provide a relatively real deployment environment, which is advanced than the software simulation. The future research includes constructing a more accurate wireless signal transmission model. In the new model, the influence of weather should be considered.
BIO
Lu Wei received his bachelor degree from the department of computer science, Shenyang Institute of Aeronautical Engineering, China in 2000, and master degree from Nanjing University of Science & Technology (NUST) in 2008. Currently, he is studying for his Ph.D degree in NUST. His research interests include wireless communication and information security.
Yang Yuwang received his bachelor degree from NorthWestern Polytechnical University in 1988, master degree from University of Science and Technology of China in 1991, and Ph.D degree from Nanjing University of Science and Technology (NUST) in 1996. From 2000 to 2001, he was a visiting scholar in the Department of Computer Science, South Bank University, London. From 2002 to 2009, he is an associate professor of Computer Science Department at NUST. Currently, he is a professor of Computer Science Department at NUST. His research interests are wireless sensor network, industry control network, and intelligent system. His email address is yuwangyang@mail.njust.edu.cn.
Zhao Wei received master degree in computer science from Nanjing University of Science & Technology (NUST) of China in 2006. Currently he is studying for Ph.D. degree in NUST. His research interests are wireless sensor network, routing protocol, network coding. His email address is zhaoweinjust@163.com.
Wang Lei received his bachelor degree from Anhui University of China in 2008. He has been a Master-Doctor combined program graduate student in computer science of Nanjing University of Science &Technology (NUST), China Since 2008. Currently, he is a visiting student in the department of computer and electrical engineering in Michigan State University, USA. His research interests are network coding, wireless sensor network, multipath routing, distributed storage system. His email address is kingstones@live.cn.
References
Senlet T. , Elgammal A. “Satellite image based precise robot localization on sidewalks,” IEEE in Proc. of 2012 IEEE International Conference on Robotics and Automation (ICRA) 2012 2647 - 2653
Wilkinson G. G. 2005 “Results and implications of a study of fifteen years of satellite image classification experiments,” IEEE Transactions on Geoscience and Remote Sensing 43 (3) 433 - 440    DOI : 10.1109/TGRS.2004.837325
Meng Z. , Xiao B. “High-resolution satellite image classification and segmentation using Laplacian graph energy,” Geoscience and Remote Sensing Symposium (IGARSS) 2011 605 - 608
Nguyen T. , Han J. , Park D. C. “Satellite image classification using convolutional learning,” 11th International Conference of Numerical Analysis and Applied Mathematics 2013 2013 vol. 1558, no.1 2237 - 2240
Tuna G. , Gungor V. C. , Gulez K. 2014 “An autonomous wireless sensor network deployment system using mobile robots for human existence detection in case of disasters,” Ad Hoc Networks 13 54 - 68    DOI : 10.1016/j.adhoc.2012.06.006
Sengupta S. , Das S. , Nasir M. D. , Panigrahi B. K. 2013 “Multi-objective node deployment in WSNs: In search of an optimal trade-off among coverage, lifetime, energy consumption, and connectivity” Engineering Applications of Artificial Intelligence 26 (1) 405 - 416    DOI : 10.1016/j.engappai.2012.05.018
Gallart V. , Felici-Castell S. , Delamo M. , Foster A. , Perez J. J. “Evaluation of a real, low cost, urban wsn deployment for accurate environmental monitoring,” in Proc. of IEEE 8th International Conference on Mobile Ad hoc and Sensor Systems (MASS) 2011 634 - 639
Ingle M. R. , Bawane N. “An energy efficient deployment of nodes in wireless sensor network using Voronoi diagram,” in Proc. of 3rd International Conference on Electronics Computer Technology (ICECT) 2011 6 307 - 311
Aitsaadi N. , Achir N. , Boussetta K. , Pujolle G. 2011 “Artificial potential field approach in WSN deployment: Cost, QoM, connectivity, and lifetime constraints,” Computer Networks 55 (1) 84 - 105    DOI : 10.1016/j.comnet.2010.07.017
Ozturk C. , Karaboga D. , Gorkemli B. 2011 “Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm,” Sensors 11 (6) 6056 - 6065    DOI : 10.3390/s110606056
Yiyue W. , Hongmei L. , Hengyang H. “Wireless sensor network deployment using an optimized artificial fish swarm algorithm,” in Proc. of 2012 International Conference on Computer Science and Electronics Engineering (ICCSEE) 2012 vol. 2 90 - 94
Howard A. , Matarić M. J. , Sukhatme G. S. “Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem,” Springer Japan Distributed autonomous robotic systems 5 2002 299 - 308
Zou Y. , Chakrabarty K. “Sensor deployment and target localization based on virtual forces,” INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies 2003 vol. 2
Zou Y. , Chakrabarty K. 2004 “Sensor deployment and target localization in distributed sensor networks,” ACM Transactions on Embedded Computing Systems (TECS) 3 (1) 61 - 91    DOI : 10.1145/972627.972631
Poduri S. , Sukhatme G. “Constrained coverage for mobile sensor networks,” IEEE in Proc. of ICRA'04. IEEE International Conference on Robotics and Automation, 2004 2004 1 165 - 171
Heo N. , Varshney P. K. “A distributed self spreading algorithm for mobile wireless sensor networks,” Wireless Communications and Networking. WCNC 2003 2003 vol. 3
Heo N. , Varshney P. K. 2005 “Energy-efficient deployment of intelligent mobile sensor networks,” IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans 35 (1) 78 - 92    DOI : 10.1109/TSMCA.2004.838486
Shucker B. , Bennett J. K. “Scalable control of distributed robotic macrosensors,” Springer Distributed Autonomous Robotic Systems 6 Japan 2007 379 - 388
Akewar M. C. , Thakur N. V. 2012 “A Study of Wireless Mobile Sensor Network Deployment,” International Journal of Computer Networks and Wireless Communications 2 533 - 541
Gage D. W. 1992 “Command control for many-robot systems,”Naval Command Control And Ocean Surveillance Center RDT And E DIV San Diego CA
Sapkal A. T. , Bokhare C. , Tarapore N. Z. 2006 “Satellite Image Classification using the Back Propagation Algorithm of Artificial Neural Network,”Technical Article 1 - 4
Tan X. , Chen S. , Zhou Z. H. 2005 “Recognizing partially occluded, expression variant faces from single training image per person with SOM and soft k-NN ensemble,” IEEE Transactions on Neural Networks 16 (4) 875 - 886    DOI : 10.1109/TNN.2005.849817
Lu D. , Weng Q. 2007 “A survey of image classification methods and techniques for improving classification performance,” International journal of Remote sensing 28 (5) 823 - 870    DOI : 10.1080/01431160600746456
Wang X. , Xing G. , Zhang Y. “Integrated coverage and connectivity configuration in wireless sensor networks,” ACM in Proc. of the 1st international conference on Embedded networked sensor systems 2003 28 - 39
Zhang H. , Hou J. C. 2005 “Maintaining sensing coverage and connectivity in large sensor networks,” Ad Hoc & Sensor Wireless Networks 1 (1-2) 89 - 124
Kershner R. 1939 “The number of circles covering a set,” American Journal of Mathematics 665 - 671    DOI : 10.2307/2371320
Lee J. , Dharne A. D. , Jayasuriya S. “Potential field based hierarchical structure for mobile sensor network deployment,” IEEE in Proc. of American Control Conference, 2007. ACC'07 2007 5946 - 5951
Wang G. , Cao G. , Porta T. L. 2006 “Movement-assisted sensor deployment,” IEEE Transactions on Mobile Computing 5 (6) 640 - 652    DOI : 10.1109/TMC.2006.80
Bartolini N. , Bongiovanni G. , Porta T. L. “Voronoi-based deployment of mobile sensors in the face of adversaries,” IEEE in Proc. of IEEE International Conference on Communications (ICC) 2014 532 - 537
Wu C. H. , Lee K. C. , Chung Y. C. 2007 “A Delaunay triangulation based method for wireless sensor network deployment,” Computer Communications 30 (14) 2744 - 2752    DOI : 10.1016/j.comcom.2007.05.017
Luo R. C. , Chen O. 2012 “Mobile sensor node deployment and synchronous power management for wireless sensor networks,” IEEE Transactions on Industrial electronics 59 (5) 2377 - 2385    DOI : 10.1109/TIE.2011.2167889
Lumelsky V. J. , Stepanov A. A. 1987 “Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape,” Algorithmica 2 (1-4) 403 - 430    DOI : 10.1007/BF01840369