International Journal of Innovative Research in Computer and Communication Engineering
MenuISSN ONLINE(2320-9801) PRINT (2320-9798)
ISSN ONLINE(2320-9801) PRINT (2320-9798)
Manisha J. Nene1, Rajendra S. Deodhar2, Lalit M. Patnaik3
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering
The positioning of sensors in Wireless Sensor Network WSN affects coverage, communication cost and resource management.In non-deterministic deployment, mobility feature of the mobile ad-hoc network can be best exploited to reposition the sensors so as to achieve the best network coverage. The Uncovered Region Exploration Algorithm (UREA) is one such algorithm proposed in [1] for redeployment of the homogeneous nodes after initial random deployment. In this paper we propose generalization of UREA andput forth, two important application scenarios. First, after final deployment of WSNs, they resume to their assigned tasks. The power of some over-utilized nodes in the Field of Interest FoI may get depleted over the time. The nodes get drained, decreasing the sensing radius of the sensors, resulting in the decrease in the network coverage, as a result decrease in Quality of Coverage QoC. A redeployment of sensors leading to an improvement in the coverage is of significant use in practical real life applications. Second, sensor nodes with varying sensing characteristics are often desirable, especially when only a subset of deployed sensors may be mobile. It is show that the generalized version of UREA presented here lead to significant improvement in the coverage. In each case, we present findings from a study of large scale deployment involving ten sets of random deployments over 40to 100 nodes. To the best of our knowledge, this work is the first to study, model simulate the intermediate non-deterministic post deployment scenario and non-deterministic nonhomogeneous sensor node deployments to improve the network coverage.
Keywords |
| Sensor Networks, Deployment Algorithm, Random Deployments, Coverage,Surveillance, Quality of Coverage |
INTRODUCTION |
| Coverage is one of the important characteristic of Wireless Sensor Network (WSN). In last few years various aspects of coverage are studied in the literature. The algorithms are proposed to obtained deployment leading optimum coverage in the given Field of Interest (FoI). Depending on the application, the nature of desired coverage may vary. Total coverage or area coverage, barrier coverage and path coverage are few of the types of coverage problems studied in the literature. Coverage of a WSN is intrinsically linked to its deployment. |
| There are several ways to classify the existing research related to WSN deployment. We categorize the study based on the following aspects: One is thetype of FoI. The kind of FoI, either 2D or 3D, with finite or infinite boundary,influence the state-of-art in research related to deployment aspects [2][3][4][5][6].The second way to classify the existing work is by the type of employed sensors. The static versus mobile and homogeneous versus heterogeneous sensors have always laid a strong impact on the nature of the problem under study [7][8]. The third way to classify the research related to the deployment is based on thesensor deployment scheme. A deterministic scheme [3][9] that has planned deployment, needs fewer nodes to cover a given area but is more time consumingand labour intensive, making it more appropriate for the friendly environments.Another type of deployment is stochastic deployment where nodes are deployed randomly by vehicles oraircrafts [10][11][12][13]. |
| In case of stochastic deployment of mobile WSN, the initial coverage can be improved using mobility feature. There are two types of algorithms proposed in the literature to carry out such redeployment, namelylocalised distributed algorithms [14] and centralized [15]. Crystal-Lattice Permutation Algorithm CLP[14] is a distributed algorithm inspired by Crystal-Lattice formation process innature. A seed node triggers six neighbouring nodes to move to hexagon permutation positions. |
| Virtual Force Algorithm (VFA) [15] is an algorithm proposed to improve the coverage after initial random deployment of homogeneous sensor nodes. This algorithm is based on the virtual forces of attraction and repulsion amongst the sensor nodes, depending on their proximity with each other. An Uncovered Region Exploration Algorithm UREA [1] is an algorithm proposed to improve the coverage after initial random deployment. This algorithm is a greedy algorithm where each sensor moves in the direction of maximum uncovered region. The algorithm presented in [1]is also for the homogeneous mobile WSN. |
Our Work |
| In Reference[1],an algorithm UREA to improve the coverage of mobile WSN, after initial random deployment, using the mobility feature was presented. It was assumed that the WSN is homogeneous and all the sensors have same sensing radius. However,in practice, a WSN may consist of nodes with varying characteristics. In this paper, a generalization of algorithm UREA is proposed to suit the requirement of non-homogeneous WSN. The nonhomogeneity of the nodes we consider here is due to the variation in the sensing radius. Applicability of the modified algorithm is verified in two different scenarios. |
| After initial random deployment of a homogeneous WSN, when the network starts performing the assigned task, the power of the sensor nodes start depleting, resulting in the reduction in the obtained coverage. Hence a redeployment after a certain operating time is suggested which will lead to improvement in the coverage, improving quality of service. As the reduction in the coverage depends on the utilization of each node during the operation, is not same for all the nodes. This is the first scenario in which the applicability of the proposed algorithm is demonstrated. |
| The capability and availability of the nodes along with the cost considerations may lead to the use of heterogeneous WSN for some specific application. This is the second scenario in which the applicability of the proposed algorithm is demonstrated. A heterogeneous network consisting of nodes with different capabilities, in terms of sensing radius is considered in this paper. |
| To best of our knowledge, this work is the first to model the intermediate non deterministic deployment scenario for achieving the improvement in the coverage. Also first time the redeployment of heterogeneous mobile WSN to improve the coverage is considered. |
| Rest of the paper is organized as follows: Section II contains the generalized version of the algorithm UREA. Applications of this algorithm in the scenarios discussed above are presented in section III and IV. Section V presents the simulation results and conclusions are presented in section VI. |
II. PROPOSED ALGORITHM |
| The algorithm UREA presented in[1] is a centralized redeployment algorithm for homogeneous mobile WSN, to be executed at the base station or at cluster head. It is assumed that the sensor nodes are capable of determining their own locations using either GPS like system or through execution of some localization algorithm. After initial random deployment these locations are conveyed to the base station or cluster head. The approach of the algorithm UREA is to determine the uncovered region around each node and suggest the new locations so as to improve the coverage.The proposed generalization follows the same approach; however, it is assumed that the WSN under consideration is nonhomogeneous. The nodes in the network have different sensing capabilities with respect to the sensing range. |
A. Assumptions and Definitions |
| The FoIis represented as a 2 dimensional grid |
 |
III. INT
|
| Consider a deployment of homogeneous mobile WSN in the FoI of size . Since initially all the nodes have same sensing radius, any of the algorithm from [1], [15] or the algorithm presented in Section II can be applied to improve the coverage. However, after carrying out the application specific task for certain period, the over utilized nodes get depleted in power. This may affect their sensing capability. Some of the nodes may even die out. Coverage of such depleted network can be improved using the algorithm presented in section II. The two different phases of redeployment are given below. |
 |
Phase II: Intermediate Redeployment |
| At regular intervals of operating time, the base station will collect the locations as well sensing capability of each node. Here it is assumed that the sensing range at any instance is an indicator of remaining power at that instance. When the coverage is below a predetermined threshold, the nodes with certain minimum sensing radius will be redeployed to improve the coverage and to extend the useful life of the network using following algorithm. |
 |
IV. REDEPLOYMENT IN CASE OF NON HOMOGENEOUS MOBILE WSN |
| A real life WSN may not contain all the nodes of the same type. Few of the nodes may have mobility characteristics and the rest may be stationary. Even those nodes equipped with mobility may have different characteristics in terms of power, sensing range etc. Such network is a Non homogeneous network. Algorithms presented in [1], [15] cannot be applied in this scenario. Algorithm presented section II B helps to use mobility feature of the nodes to improve the coverage after initial random deployment. |
Algorithm for redeployment of Non Homogeneous WSN |
 |
V. SIMULATION RESULTS |
| The algorithm presented in section II B is a generalization of algorithm UREA given in [1]. In the case of homogeneous WSNs, with all sensor nodes having mobility property, the proposed algorithm reduces to UREA as presented in [1]. The extensive simulations are carried out to verify the applicability of the proposed algorithm in the scenarios discussed in section IIIand section IV. |
| The simulation environment was set up similar to that [1] [15]. The dimension FoI considered for simulation of both the scenarios is 50 units × 50 units and a same size grid is used. The metric under observation is network coverage. Multiple simulation runs are carried out and average coverage is observed. The standard deviation in the coverage is measured to check the consistency of the algorithm. |
A. Simulation of Intermediate Re-deployment Scenario |
| In this case, it is assumed that the initial sensing range of each of the sensors is 5 units. For simulation of Phase I, the sensor nodes are randomly deployed in the given FoI. The sensor locations are simulated using 2-dimensional uniform distribution over the FoI. After execution of algorithm presented in section III A, the improvement in the coverage is observed. Simulation experiment was carried out by varying node density from 40 to 100. In each case 10 simulation runs were observed with different initial random deployments. A typical random deployment of homogeneous sensor nodes is shown in Figure 1 and the proposed locations at the end of Phase I, for this initial deployment, are shown in Figure 2. |
 |
 |
| A depleted network as per the probability distribution given in Table 1 is shown in Figure 3. Figure 4 shows the improvement suggested after the execution of algorithm in section III.B. |
 |
| The average results for 10 sets of simulation runs for node density varying from 40 to 100 is presented in Table 2. |
 |
 |
B. Simulation of Re-deployment of Non Homogeneous WSN |
| To verify the applicability of the algorithm in section II B, we simulate deployment of a non-homogeneous WSN with two types of sensor nodes. The first types of nodes are assumed to have sensing radius 5 units and the second type of nodes are assumed to have sensing radius 4 units. Also it is assumed that both type of sensors are equal in number. A typical initial deployment in one such case is shown in Figure 5 and the corresponding improved coverage is shown in Figure 6. |
 |
| In the simulation experiment the sensor density is varied from 40 nodes to 100 nodes. In each case average results from 30 simulation runs are recorded and are presented in Table 3. |
 |
Column Keys for Table 3: |
| a. Total number of sensor nodes |
| b. Number of sensor nodes with sensing radius rl=5 |
| c. Number of sensor nodes with sensing radius rl=4 |
| d. Computed coverage on initial deployment |
| e. Standard deviation in the initial sensing coverage |
| f. Improved final coverage after execution of algorithm in section III B |
| g. Standard deviation in the final sensing coverage |
| h. Percentage of increase in the final coverage |
| It can be concluded from the above results that the algorithm presented in Section II B improves the coverage of a heterogeneous mobile WSN. The improvement is significant for smaller node densities compared to larger one. In case of high sensor density, the initial coverage is also high and there is a little scope for improvement. |
V. CONCLUSION |
| A generalized version of algorithm UREA is presented in this paper. The algorithm UREA was presented for improving the coverage of a randomly deployed homogeneous mobile WSN. The algorithm presented in this paper does not assume homogeneity of the sensor nodes. The applicability of this algorithm was demonstrated in two different scenarios. First in case of uneven utilization of sensor nodes during application phase, resulting in depletion of coverage, can be improved using the algorithm presented here. Second, in the case when the WSN consist of nonhomogeneous nodes, i.e., nodes with different sensing capabilities this algorithm can be successfully applied to improve the coverage. |
References |
|
ERMEDIATE DEPLOYMENT SCENARIO