Grid Based Wireless Mobile Sensor Network Deployment with Obstacle Adaptability

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

GRID B ASED WIRELESS MOBILE SENSOR  NETWORK DEPLOYMENT

WITH

OBSTACLE

DAPTABILITY   A DAPTABILITY 

1

2

Mr. Mayur C. Akewar and Dr. Nileshsing Nileshsingh h V. Thakur Thakur 1

Department of Computer Computer Science & Engineering, Shri R Ramdeobaba amdeobaba College of  Engineering and Management, Nagpur University, Nagpur, India [email protected]

2

Department of Computer Computer Science & Engineering, Shri Ramdeobaba College College of  Engineering and Management, Nagpur University, Nagpur, India [email protected]

 A BSTRACT   Mobile Sensors find their target position and placed themselves over the target field to achieve a certain goal in self deployment with certain additional functionality like sensor relocation. An efficient  deployment scheme guaranteed guaranteed maximum coverage with full connectivity. Certain variance of of coverage could be manageable but loss of connectivity because of failure of some sensor node causes complete isolation of some sensing area which causes loss of data of that area. So it is not enough to be just  connected, it should be K connected (K>1) to control the isolation. Again the obstacles over the target   field should be managed during deployment. A self deployment scheme using mobile sensors is proposed  which achieve K connectivity. The target target area is divided into n × n square grid. The d distributed istributed algorithm deploys a sensor in each square grid cell to maximize the coverage and achieve K connectivity. A square grid deployment pattern is used which guarantee at least (K=4) connectivity. The first algorithm assumed  a plane target area with no obstacle. The second proposed algorithm has the capacity of obstacle adaptabilit adap tabilityy which as assumed sumed a targ target et area with ssome ome obs obstacle. tacle. Simul Simulation ation re result sult sho shows ws maxim maximum um coverage with minimum moving cost and obstacle adaptability.

 K  EYWORDS Wireless Sensor Sensor Network, Wireless Network, Mobile Sensor Networ Network, k, Coverage, Connectivity, Move Movement  ment  Cost, Obstacle Adaptability

1. INTRODUCTION Wireless Sensor Network (WSN) has emerged as an efficient technology for wide variety of  applications such as home automation, military application, environmental monitoring, habitat monitoring monito ring etc. It consist consistss o off distributed distributed autonomous autonomous senso sensors rs to monitor monitor physical physical or environmental conditions and to corporately pass their data through the network to main location. Sensor nodes are severely constrained in terms of storage resources, computational capabilities, communication bandwidth and and power supply. supply. WSN face many challenges due to these many constraints such as life of network, efficiency and the performance of network. An efficient deployment technique handles these challenges. Deployment is very critical issue because it decides the performance of wireless sensor network. Given set of sensors are deployed with a goal of maximizing the area that covered by the sensors sensors.. The deployment can be deterministic [1] or random [11] or incremental [2] or self deployme deployment nt [4-6], [8], [12], [13], [15]. In this paper, paper, follo following wing self deploymen deploymentt problem has been cons considere idered: d: “Given a target sensing   field with an arbitrary initial sensor distribution, how should these sensors self organize into a DOI : 10.5121/ijwmn.2012.4502

21

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

connected ad hoc network that has the maximum coverage, at the cost of a minimum moving

distance?” Uniform distribution of sensor nodes over the target field is very important to cover maximum area. For uniform distribution the node has the additional capability of locomotion such that the sensor moves from high dense area to low dense area. After random deployment, the node self deploy themselves to achieve uniform distribution. Node find its own location and self deploy it to desired location with the capability of mobility. With the help of self  deployment sensorefficient relocate form them to low denseto area to achieve coverage. Self  deployment the is very of the deployment manage the maximum network dynamics. Self  deployment uses mobile sensors for placement placement of ssensor ensor node. Mobility includes different functionality in wireless sensor network like coverage optimization, better lifetime of network, better use of resources and relocation [4]. Sensor nodes may change their location after initial deployment. deploy ment. Mobility Mobility may apply apply to all nodes or only to subsets subsets of nodes nodes.. M. Marks [26] give taxonomy of mobility. Mobility may be active or passive. In active mobility the sensors are intelligent enough to find their path and move while in passive mobility the sensors may move by human or environmental assistance. J. Luo and et al [24] defined two types of mobility; they are U- mobility mobility and C- mobility ccalled alled as double double mob mobility. ility. C- mobility is is controllable controllable w while hile Umobility is uncontrollable. C- mobility is the prope property rty of sensor sensor node and U- mobility is affec affected ted by environmental condition like wind. Mobility is essential for for self deployment [4], [5], [6], [8] [8],, [12], [13], [15], that is to find the position and move to deploy them. Two mobile sensor platforms Racemote [9] and Robomote [22] are used for mobile sensor network deployment. A wireless mobile sensor network deployment approach is proposed by handling the issues of  coverage, connectivity and movement cost of sensor node. In this this paper, paper, distrib distributed uted algorithm algorithm which solve the above above p problem roblemss has b been een p propose roposed d and get the K connected deployment scheme after random deployment. The proposed approach used square deployment pattern for at least K=2 coverage and at most K=4. The sensor nodes should self deployed them after initial distribution of sensor nodes on the target area. We consider a square target area and divided it into square grids. After random deployment the sensor should self deploy them such that each grid cell has exactly one node and each node should connect with at least 2 sensor nodes. We try to reduce the communication overhead to only communicate the sensor nodes within the grid cell and also to reduce the movements of sensor nodes to save the energy which results in increasing network lifetime. The first algorithm assumed a plane target area with no obstacle. In most of the existing work researcher assumed a target field with no obstacle. The second proposed algorithm has the capacity of obstacle adaptability which assumed a target area with some obstacle. The proposed algorithm achieved a self deployment of sensors with minimum moving cost of sensors for minimizing energy consumption with obstacle adaptability. Simulation result shows maximum coverage with minimum moving cost and obstacle adaptability. This paper is organized as follows: Section 2 gives the related work. Section 3 gives the preliminaries of the system. Section 4 gives the proposed scheme. Section 5 gives experimental results. The paper ends with conclusion and future work which is g given iven in section 6.

2. RELATED WORK Different approaches have been proposed for the deployment of mobile sensor for solving above problem. Some proposed approaches used virtual force [27] and [29] approach which considered the mobile nodes as a particle under attractive or repulsive force. The sensor nodes modelled as points subject to attractive or repulsive force according to the distance between two sensors. The virtual force exerted on the sensor is similar to the Coulomb force. By setting the threshold distance between sensors, each each sensor moves in accordance w with ith the summation of the force vectors and eventually a uniform deployment is achieved. The potential force [4] based method which used the method to migrate the node from high density to low density area. 22

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

Computational Geometry based approach which used the popular data structure Voronoi diagram diagr am has bee been n proposed proposed in [27]. According According to F. Aur Aurenham enhammer mer [30], it is b believe elieved d that the Voronoi diagram is a fundamental fundamental construct def defined ined by a discrete set of points. Voronoi diagram is used to discover the e Voronoi diagram is constructed on the basis of neighbors who are in the communication range. If there is less number of nodes in the communication range it will result in improper voronoi diagram diagram construction. Second problem with this approach is that we will not get optimal deployment. Again existing approaches have the problem of optimal deployment high the communication communicate to construct the of voronoi diagram or toand calculate virtual forces.overhead There is to chance of unnecessary movements nodes in the existing approaches. Most of the existing studies mainly considered the issue of coverage, but sensor network is often gets into sensor failure so the sensor should be at least K connected with K>1. Existenc Existencee of coverage hole once all the sensors sensors have been initi initially ally ran randomly domly deployed in the target area. A node needs to know the location of the neighbors to construct the voronoi diagrams. The diagram partition the whole target area into voronoi polygons. Each polygon has a single node with the property that every point in this polygon is closer to this node to estimate any local coverage hole. After each iteration, every sensor node moves to an improved location and then the voronoi diagram diagramss are reconstructed. reconstructed. Another structure that is directly related to Voronoi diagrams is the Delaunay triangulation [29], [13]. The Delaunay triangulation can be obtained by connecting the sites in the Voronoi diagram whose polygons share a common edge. It has been shown that among all possible triangulations, the Delaunay triangulation maximizes the smallest angle in each triangle. N. Azlina and et al [8] proposed coverage optimization algorithm based based on particle swarm optimiza optimization tion (PSO). C. Hsien and et  al [13] and S. Megerian and et al [14] proposed Delaunay triangle based approach. The algorithm eliminates the coverage holes near the boundary of sensing area and obstacles Delaunay triangle is applied for the uncovered regions. G. Tan aand nd et al [6] proposed enhanced form of Virtual force method called as connectivity preserved virtual virt ual force method (CPVF). The authors consider the obstacles during deployment. The given approach is used for mobile sensor network for the self deployment. The authors overcome the limitations of previous approaches where large communication range, dense network and obstacle free field or full knowledge of  the field layout layout have been assumed. assumed. M. Garetto Garetto [15] proposed proposed a virtual forc forcee method use used d for sensor relocation. Upon occurrence of physical phenomenon nodes relocate themselves so as to control the event, while maintaining network connectivity. After event ends all nodes return to the monitoring monitoring configura configuration. tion. J. Lee and and et al [4] proposed a potential field based approach. After initial deployment, group of mobile sensor clusters are formed using potential field method and then cluster heads are used to establish hexagonal structure or achieving coverage. L. Filipe and et al [2] proposed an efficient incremental deployment algorithm using Largest Empty Circle problem. Algorithm indicates position for new nodes to be deployed and number

of new nodes. A network is said to have have k-coverage if every point in it is covered by at at least k  sensors. the k-coverage map for a square square grid and THT. S. Shakkottai and et al [18] proposed unreliable unrelia ble sens sensor or grids by conside considering ring issue of coverage coverage and conne connectivity ctivity.. X. Bai and et al [20] investigate different different deployment models with their performance performance evaluation. B. Liu and et al [21] discuss he question “Is mobility improves coverage of sensor network?”. S. Yang Yang and and et al [23] proposed scan based movement assisted deployment method. By handling the issue of coverage an algorithm named SMART (Scan based movement assisted) is proposed. A unique problem called communication hole is handled here. The algorithm control the moving distance. G. Wang and G. Cao Cao [27] propos proposed ed Coverage Coverage hole detection detection meth method. od. A robot deploy deployment ment algorithm that overcomes obstacle obstacle and employs full coverage with minimal number of sensor sensor node is discussed in [10]. A mobile Robot is used for placing sensors. The robot explores the environment and deploys a stationary sensor to the target t arget location from time to time. Non uniform sensor deployment in mobile sensor network is discussed in [16]. A Jagga and et. proposed an approac approach h for deploy deploying ing mobile mobile agents agents.. G. W Wang ang aand nd et. al. [32] proposed al. [31] proposed an approach for dynamic deployment by using both static stat ic and dynamic sensor nodes. 23

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

Most of the work evaluates the performance of the network on the basis of coverage and number of sensors. sensors. Use of mobility for sensor relocation to improve coverage, aand nd network  lifetimee after failure lifetim failure of some some nodes in in the system system has proposed proposed in some w work. ork. Constr Constrained ained coverage approach for better network performance and energy efficiency has been proposed in some work. Balancing energy consumption by placing sensors in terms of different densities (non uniform deployment) is proposed. Computational geometry data structure like voronoi diagram and Delaunay tringulation is used for finding coverage hole is proposed in most of the work.of Virtual forceCoverage method and movement ass assisted isted used forinmovement of sensors in most the work. is an open issue issue whichmethod can beishandled most most of the approach. Sensor movement also need energy, energy, so cost of sensor m movement ovement should be minimized. Efficient management of mobility towards a better coverage remains an unanswered question. We are using a square deployment pattern and a grid based approa approach ch such that w wee can manage the mobility of the sensor node efficiently. The cost of the movement is minimized considerably in our proposed approach. We achieved nearly hundred percent coverage with maximum K=4 connectivity. So our approach is different from existing approach such that we achieve both maximum coverage and K connectivity with minimum movement cost. Also the obstacle over the target field is handled in i n a better way.

3. PRELIMINARIES 3.1. System System Assumptions Assumptions We assume that the target target area is on a 2D plane. plane. We assume that all the sensor sensor nodes are homogenous with same sensing and communication range. Both ranges are assumed as disk  based model. If the two sensors are in range then they are called as neighbors. A sensor can det determ ermine ine the the positio position n of other other sensor sensor o only nly by ccomm ommunic unicati ation. on. The The se sensin nsing g range range is eq equal ual to

√2 × the length of the side of square grid to achieve optimal coverage and communication range is equal to √2 × to have a connected network. Each sensor node knows the coordinates of  their position by using some localization technique like GPS. Sensor nodes should be able to change their position coordinates after each movement. We may use a mobile sensor node platform Robomote [28] and Racemote [9]. Each sensor node knows the dimension of square target area, also each sensor node knows the dimension of square grid which is fixed for each cell and should be able to get the centre coordinates of the square cell where it is currently deployed. Sensor node moves with uniform speed horizontally or vertically in a straight line for fixed amount of time which we called as time.

3.2. Target Target Field We are using a square target field on 2D plane surface. The target field is divided into equal size square grid cell. The field is divided into 3 × 3 grid. Each cell has given a cell id, starting

from left upper corner. Cell id’s are from 1 to 9. 3.3. Deployment Pattern Pattern for Achieving K Connectivity We have divided the target area into equal length square grids cell to achieve optimal coverage and K connectivity. Reason of using an optimal deployment pattern [1] is that the sensor network could subject to failures, so the sensor node should at least K connected (K>1). If anyone node failed, then other node could serve the purpose. A square grid provides at least 4- con connec nectivi tivity ty [6]. [6]. Wh When en 1.14 ≤    / ≤√2 , the square pattern is better than other deployment pattern [6]. We are assuming assuming the sensing and communication range within the above range. 24

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

3.4. Informatio Information n to Each Sensor Each sensor knows the dimension of target field and the grid cell. Position of the sensor node is known with with the help of GPS GPS device. device. Also the node sh should ould get the centr centree of cell by usin using g its position coordinates. Each cell only communicates to other node within its own cell. Each sensor node has a list of the connected nodes within the cell. By which the nodes within the cell decides the next action by local communication. Each senor node has a list of closest boundary distance and its direction to decide to to thecalculate next move. Each node cost has an counter which hich is decremented after each movement the movement of energy the sensor. Eachw sensor node should move until the goal is reached or to a fixed amount of distance and decides the next action. Each sensor sensor should identify the boundary of the obstacle. After identifica identification tion of obstacle boundary the sensor node should move towards next closest boundary. Each node has a counter for time which set to some threshold value. After random deployment the node starts the timer and wait up to set threshold value. If it migrate to another cell then the timer again set to zero and again start the timer until another event is occur or to a threshold time. Each cell node has a cell id for identification of the cell in which it is currently deployed. The cell cannot return to the previous cell by searching the cell id list.

3.5. Movement Movement of Sensor Sensor Node Each sensor node moves for a fixed amount of time and distance in horizontal or vertical direction. After each move the energy energy is lost which is represe represented nted by an energy counter set to some value. For minimizing the movement cost the sensor node with maximum energy will move and the sensor node with minimum energy stays in the cell. Also the sensor will move towards closest boundary to minimize the movement cost. The sensor node cannot move to the same cell again by looking at the cell id list. For this, each sensor node has the history of cell id.

4. PROPOSED APPROACH 4.1. Problem Problem Definition Definition Given a target sensing field with an arbitrary initial sensor distribution, these sensors should self organize into a k-connected ad hoc network that has the maximum coverage, at the cost of a minimum moving distance. In the the initia initiall pha phase, se, the target target aarea rea iiss divide divided d into n × n equ equal al ssqua quare re gr grids ids aand nd the , val values ues are are decid decided ed on the the ba basis sis o off length length of of the side side of th thee gr grid id ce cell. ll. =√2× side of the cell and =√2 × . The sensor nodes are fixed which is equal to number of cells. If there are 9 cells then the nodes are also 9. The sensor nodes are randomly deployed on the target field. A distributed algorithm is executed in each sensor node to self deploy the sensor node such that each cell reach the center of the grid to achieve optimal deployment. The proposed approach gives maximum coverage with minimum moving distance and obstacle adaptability.

4.2.. Scenar 4.2 Scenario io 1 If after random deployment, each cell has exactly one sensor node then the self deployment is quite simple. The list of connected nodes is empty. So the sensor node decides that my cell does not contain any other node, so the there has not any redundant node for migration or relocation. The sensor node knows the center of the current deployed cell, so the particular sensor just has to move to the center of the cell. Each sensor node will performed following steps.

25

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

1. All the the no nodes des broadcast broadcast hello hello me messag ssagee with their positio position n coordina coordinates tes aand nd wa wait it for acknowledgement and start the timer. 2. If the node node j present present in the same ccell ell then from from positi position on coord coordinates inates it will deci decides des that the node i is in its own cell, it send acknowledgement message and they will connect if  distance (i, j)<=Rc. 3. If the node node does not rec receive eive any aacknow cknowledge ledgement ment me means ans the ccell ell cont contains ains on only ly one node 4. After Afte r timer reaches reaches a th thresho reshold ld value th thee node stop waiting waiting an and d it will then eexecute xecute th thee MovetoCenter Algorithm to reach to center of cell. MovetoCenter algorithm is given below. Consider that a sensor node has the coordinate value Xnode and Ynode. The sensor will move until it reach the center of the cell to maximize the coverage, that is (Xnode, Ynode)=(Xcenter, Ycenter), where Xcenter and Ycenter are the x coordinate aand nd y coordinate of center of a cell. Algorithm 1. do{ 2. If (Xnode (Xnode< < =Xcentre =Xcentre)) && (Yno (Ynode< de<=Yc =Ycent entre) re) 3. {Xnode=Xno {Xnode=Xnode+(X de+(Xcentr centre, e, Xnode);Move Xnode);Moveto(Xno to(Xnode, de, Ynode Ynode); ); 4. Ynode= Ynode= Ynode Ynode+(Y +(Yce centre ntre-- Ynode) Ynode);Mo ;Movet veto(X o(Xnode node,, Yno Ynode) de);; 5. Else Else If ((Xno Xnode< de< = =Xce Xcentr ntre) e) && (Yno (Ynode> de>=Yc =Ycent entre) re) 6. {Xnode=Xno {Xnode=Xnode+(X de+(Xcentr centre-Xno e-Xnode); de); Moveto(Xno Moveto(Xnode, de, Ynode Ynode); ); 7. Ynode= Ynode= Yno Ynodede-(Yn (Ynode ode-- Yce Ycentr ntre); e); Moveto(X Moveto(Xnod node, e, Ynod Ynode); e);} } 8. 9. 10. 11. 12. 13. 14.

Else If (Xnode>=Xc (Xnode>=Xcentre entre)) && && (Ynode>=Yce (Ynode>=Ycentre) ntre) {Xnode=Xno {Xnode=Xnode-( de-(Xnode Xnode-Xce -Xcentre); ntre); Moveto(Xnod Moveto(Xnode, e, Ynode Ynode); ); Ynode= Ynode= Ynode-(Ynode Ynode-(Ynode-- Ycen Ycentre); tre); Moveto(Xno Moveto(Xnode, de, Ynode Ynode);} );} Else If If (Xnode> =Xcentre) & && & (Ynode=<Ycentre) (Ynode=<Ycentre) { Xnode=Xnode-(Xnode-Xcentre); Xnode=Xnode-(Xnode-Xcentre); Moveto(Xnode, Ynode); Ynode= Ynode= Ynode+(Ycentr Ynode+(Ycentree- Ynode); Ynode); Moveto(Xnode Moveto(Xnode,, Ynode);} }while((Xnode, Ynode)==(Xcenter, Ycenter));

4.2.1. Exec Execution ution of Scen Scenario ario 1

Figure Fig ure 1 Initial Initial and Final Final Deploym Deployment ent

4.3.. Scenar 4.3 Scenario io 2 After random deployment if there is more than one sensor is deployed in a cell then it will follow following strategy. a) Identifying Identifying R Redunda edundant nt Node: If If a cell co contains ntains more more than one one node aafter fter init initial ial distribution then each node has to decide the nodes which are redundant. The redundant nodes migrated to other cell which is close to it. Foe identification of redundant nodes, we use some distance measures. For each cell we have decide a fixed location. The 26

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

distance between that location and the location of node is calculated. The node with minimum distance stayed in the cell and the other node will move towards the closest boundary until they will migrate to new cell. If any cell has only one node then that node will move to a threshold distance such that if another node comes then it should be connected to that node. b) Movement Movement of Node: Node: The redundant redundant nodes nodes will move move towar towards ds closes closestt boundar boundary y until migrated to new cell and updated their position coordinates. The direction for movement is towards closest boundary. themove closest cell isthe thenext cellclosest from where the node was coming, in such a case the nodeIfwill towards boundary. For this purpose the node look at the history of cell id. c) Min iniimize movement cost: Each sensor node has two counter one is timer‘t’ and other is

migration counter ‘m’, each one is set to zero. If there is only one node within a given

cell then the counter t is started until a threshold time. time. After that time is reached then the sensor decides that know sensor is migrated in its cell then the node will follow my MovetoCenter algorithm to move to the center. If a node is migrated then the other node and the migrated node set t=0 and decides the next move by communication. The migrated node increment the counter to 1 and push the other node to migrate to other cell which is depends upon the distance between the boundary and the location of the sensor. If there is a tie then the sensor node with maximum distance from center to its location moves and other stays. After each communication within the cell the node set the timer to t=0. The nodes which are deployed on the boundary cell are quite intelligent to decide not to move towards the boundary of the target field. 4.3.1. Steps for Sce Scenario nario 2

1. All the sensor sensor nodes nodes broadcast broadcast he hello llo mess message age with with their position position coo coordinat rdinates es and wa wait it for acknowledgement and start the timer. 2. If the nodes nodes ge gets ts acknowledgem acknowledgement ent then the cell contains contains m more ore than o one ne node an and d they update their connected node list. 3. If the nodes does not get get any ac acknowle knowledgeme dgement nt means the node is isola isolated, ted, then then the nodes will move towards center until it is connected or reach a threshold t hreshold distance. 4. The nodes nodes calculate calculate the dis distance tance from a fixed locatio location n which which is dep depends ends u upon pon the ce cell. ll. 5. The nodes nodes shar sharee their dis distance tance list through through loca locall commun communicatio ication n to all the nodes nodes in the given cell. 6. The node node ccomp ompare aress the the distan distance. ce. 7. The node node with with ma maximum ximum or minimum minimum distance distance ( which is dep depends ends upon th thee ce cell) ll) stay in the cell and the other (redundant (redundant sensors sensors nodes) nodes) migrate migrated d to nearest cell and increment the migration counter, and update cell id and position coordinates. If the nearest cell has already visited then the sensor node will move towards the next nearest cell. 7. After After migration migration the timer timer again again set to ze zero ro and the node node wa waits its for lo local cal communic communication ation by sending hello message in some time interval. 8. If the migrat migrated ed sensor sensor node re receives ceives acknow acknowledgem ledgement ent then it w will ill repe repeat at step 4 to 7 7.. 9. If two two sens sensor or nodes nodes has same migration migration cou counter nter then th thee nods w which hich w will ill mig migrated rated is decides on the basis of energy level. The node with high energy will migrate. 10. If the node has to move to the same ce cell ll again, then from cell cell id it will decides not to move to that cell. It then migrated to the next closest bound boundary. ary. 11. If each cell contains exactly one node and timer=threshold timer=threshold time then the MovetoCenter algorithm will execute.

27

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

4.3.2. Exec Execution ution of Scen Scenario ario 2

Figure 2 IIn nitial Phase

Figure 5 It Iteration 3

Figure 8 It Iteration 6

Figure 3 IItteration 1

Figure 6 It Iteration 4

Figure 9 IItteration 7

Figure 4 IItteration 2

Figure 7 IItteration 5

Figure 10 It Iteration 8

4.4.. Scenar 4.4 Scenario io 3 The target field contains any obstacle. Our previous algorithm will oscillate because at any given time the condition of all the cell contains exactly one node cannot satisfy. 4.4.1. Obstac Obstacle le Adaptability Adaptability

Sensor node knows the boundary of obstacle. During movement of sensor node if any obstacle arrives in the path of sensor node, then the sensor node will turn and move towards the next closest boundary. For achieving stability we set the migration counter to a threshold value and execute the previous algorithm. The sensor migrated only for the fixed count. If the migration count is equal to one then the node will migrate only once. We are assuming that a ce cell ll is totally covered by an obstacle. So during movement of  sensor, if the closest boundary is towards obstacle covered cell, then the sensor node will unable to move or migrate to that cell, so the node calculates the next closest boundary and move towards that cell. We are considering that the obstacle is in center cell as shown in figure. After execution of  the algorithm any cell contains more than one node. In such a case the sensor node with maximum energy will executes the MovetoCenter algorithm while the other node will go to the sleep mode, which could be used for the incremental deployment if the node in the cell has failed.

28

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

Figure shows the movement of sensor if any obstacle comes in the path of sensor node.

Figure Fig ure 11 Obs Obstac tacle le Ada Adaptabi ptability lity 4.4.2. 4.4. 2. Exe Execut cution ion of Sce Scenar nario io 3

Figure Fig ure 12 Ini Initial tial and Fin Final al Configu Configurat ration ion

5. EXPERIMENTAL RESULTS We have used a ‘C’ based simulator for simulating the above mobile deployment scheme. We have considered a 3×3 grid square target field (300 × 300 meter square) with 9 sensors such as each cell must have 1 node deployed. Each cell has a area of 100 ×100 meter square. Sensing range is decided as Rs=71 meter and communication range as Rc=101 meter. Energy counter is initialized as 2000 and migration counter is initialized as m=0. The target area is fully covered with at most K=4 connected sensor sensor node. The performance graph shows shows the energy lost during movement for various scenarios.

5.1. Execution Execution 1 .

Figure 13 Initial and Final Final Configur Configuration ation 29

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

Initially the field does not contain any obstacle. The surface is flat. Figure shows the initial configuration after random deployment. The distributed algorithm is executed and the final configuration is achieved with 100% coverage and at most K=4 connectivity. The performance graph shows the movement movement cost during deployment of the sensors sensors.. The circle shows the sensing range and the connectivity is shown by lines. 5.1.1. Perfor Performanc mancee Graph of Eecution 1

Graph shows the enegy lost during sensor movement.

Figure Fig ure 14 Cos Costt of Node Move Moveme ment nt

5.2. Execution Execution 2 The target field contains obstacle. Figure shows the initial configura configuration tion after random deployment. The performance graph shows the movement cost during deployment of the sensors. The circle shows the sensing range. The middle cell contains obstacle.

Figure Fig ure 15 Ini Initial tial and Fin Final al Configu Configurat ration ion with Obs Obstac tacle le

5.2.1. Perfor Performanc mancee Gr Graph aph of E Executio xecution n2

The graph shows the energy lost during movement of sensors. Performance is evaluated by considering different migration count. We are considering considering maximum migration count m m=4. =4.

30

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

Figure 1 16 6 migration cco ount=1

Figure 18 migration count=3

Figure 17 1 7 migration co count=2

Figure 19 Migration count =4

Figure 20 Energy lost for various migra migration tion counts counts

6. CONCLUSION AND FUTURE WORK We proposed a grid based mobile deployment algorithm which self deploy the fixed number of nodes in each grid cell. The distributed algorithm is efficient to minimize the cost of  movement and communication overhead. The square deployment pattern has at least 4connectivity and coverage. In future work we can have more experiments on the obstacle avoidance strategy while deployment by considering obstacles at different position on the target area and measure the energy lost by setting the migration migration counter. We can use this 3×3 grid as a

31

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

mask for a larger target area and large amount of sensor nodes. Also different deployment patterns like hexagonal and triangular pattern can be used u sed for self deployment scheme.

REFERENCES [1] Ziqiu Yun, Xiaole Bai, Dong Xuan, Ten H. Lai, and Weijia Jia “Optimal Deployment Patterns for Full Coverage and k-Connectivity (k<=6) Wireless Sensor Networks” IEEE/ACM transactions on networking, vol. 18, no. 3, June 2010. [2] Luiz Filipe M. Vieira, Ma Marcos rcos Augusto M. Vie Vieira, ira, Linnyer Beatrys Ruiz, Antonio A.F. A.F. Loureiro,

Di´ogenes Cec´_lio Silva, Ant.onio Ot´avio Fernandes “Efficient Incremental Sensor Network  Deployment Algorithm”.

[3] Kay Romer and Friedemann Mattern “The design Space of Wireless Sensor Networks” IEEE Wireless Communications, Dec. 2004.

[4] Jaeyong Lee, Avinash Dharne and Suhada Jayasuria “Potential Field Based Hierarchical Structure for  Mobile Sensor Network Deployment” Proceedings of the 2007 American Control Conference, July 2007. [5] W. Li, Y. II.. Kamil aand nd A. Ma Manikas nikas

“Wireless Array Based Sensor Relocation in Mobile Sensor 

 Networks” ACM 2009. [6] Guang Tan, Stephen A. Jarvis Jarvis,, Member, and Anne-Marie Kermarrec “Connectivity-Guaranteed and Obstacle-Adaptive Deployment Schemes for Mobile Sensor Networks” IEEE transactions on mobile computing, vol. 8, no. 6, June 2009.

[7] Wint Yi Poe and Jens Schmitt “ Node Deployment in Large Wireless Sensor Networks: Coverage, Energy Consumption, and Worst- Case Delay” ACM November 2009. [8] Nor Nor Az Azlin linaa Bt Bt.. Ab A Aziz ziz , Amm Ammar ar W W.. Moh Mohemm emmed ed and Moh Mohamm ammad ad Yuso Yusoff ff A Alias lias “A Wireless Sensor Network Coverage Optimization Algorithm Based on Particle Swarm Optimization and Voronoi Diagram” Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, Okayama, Japan, March 26-29, 2009.

[9] G. Song, W. Zhuang, Z. Wei, and A. Song, “Racemote: A Mobile Node for Wireless Sensor   Networks,” in Proc. 5th IEEE IEE E Conference on Sensors, IEEE, 2006. [10] Chih-Yung Chang, Jang Jang-Ping -Ping Sheu, Yu-Chieh Chen, and Sheng-Wen Chang “ An Obstacle-Free and Power-Efficient Deployment Algorithm for Wireless Sensor Networks” IEEE transactions on systems, man, and cybernetics — part part a: systems and humans, vol. 39, no. 4, july 2009.

[11] Jiming Chen, Entong Shen and Youxian Sun “The deployment algorithm in Wireless Sensor  Network: A Survey” Information Informati on Technology Journal Journ al 2009. [12] Jun Li, Baihai Zhang and Lingguo Cui “A Restricted Delaunay Tringulation Graph Based Algorithm for Self-Deployment in Mobile Sensor Networks” Journal of Computational Information Systems 2010. [13] Chun-Hsien Wu, Kuo-Chuan Lee, and Yeh- Ching for Wireless Sensor Network Deployment”.

Chung “A Delaunay Triangulation Based Method

[14] Seapahn Megerian, Farinaz Koushanfar, Miodrag Potkonjak, and Mani B. Srivastava “Worst and Best-Case Coverage in Sensor Networks”, IEEE transactions o on n mobile computing, vol. 3, no. no. 4, october-december 2004.

[15] Garetto M, Gribaudo M, Chiasserini CF, Leonardi E (2007) “A distributed sensor relocation scheme for environmental control”, In: The ACM/IEEE Proc. o f MASS [16] Cardei M, Yang Y, Wu J (2008) Non-uniform sensor deployment in mobile wireless sensor networks. In: Proc. Of WoWMoM, pp 1 – 8

[17] W. Li and C. G. Cassandras, “A minimum -power wireless sensor network self-deployment scheme,” in Proc. Annu. IEEE WCNC , New Orleans, LA, Mar. 2005, vol. 3, pp. 1897 – 1902. 1902. 32

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012

[18] Shakkottai, S., Srikant, R., and Shroff, N. Unreliable Sensor “Grids: Coverage, Connectivity and Diameter”. In IEEE Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2003) (New York, NY, USA, Mar. 200 2003), 3), vol. 2, ACM,pp. 1073 – 1083. 1083. [19] Heo N, Varshney P (2005) “Energy-efficient deployment of intelligent IEEE Trans Syst Man Cybern C ybern 35:78 – 9 92. 2. [20] X. Bai, S. Kumar, D. Xuan, Z. Yu n,

mobile sensor networks”,

and T. H. Lai, “Deploying wireless sensors to achieve both

MobiHoc Hoc, 2006, pp. 131 – 142. 142. coverage and connectivity,” in Proc. ACM Mobi [21] B. Liu, P. Brass, and O. Dousse, “Mobility Improves Coverage of Sensor Networks,” Proc. ACM

MobiHoc, 2005. [22] Dantu, K., Rahimi, M., Shah, H., Babel, S., Dhariwal, A., and Sukhatme, G. “Robomote: Enabling Mobility In Sensor Networks ”, IEEE/ACM International Conference Information Processing in Sensor Networks, Apr. 2005.

[23] S. Yang, M. Li, and J. Wu, “Scan -based movement-assisted sensor deployment methods in wireless sensor networks,”  IEEE Trans. On Parallel and Distributed Systems , vol. 18, no. 8, pp. 1108 – 1121, 1121, 2007. [24] Ji Luo, DanWang, Qian Zhang, “ Poster Abstract: Double Mobility: Coverage of the Sea Surface with Mobile Sensor Networks”, Mobile Computing and Communications Review, Volume 13, Number 1 [25]

Lingxuan Hu, David Evans “Localization for Mobile Sensor Networks ”,  MobiCom’04 , Sept. 26. –   –  Oct. 1, 2004, Philadelphia, Pennsylvania, USA. 2004 ACM 1 -58113-868-7/04/0009

[26]

Michałł Marks Micha “A Information, 2010

Survey of Multi Multi-Objective Deployment in Wireless Sensor Networks”, Journal of 

[27] Wang G, Cao G, Porta TL (2006) Movem Movement-assisted ent-assisted sensor deployment. IEEE Trans M Mob ob Comput 6:640 – 652 652 [28] A Sekhar, B. S. Manoj, a nd

C. S. R. Murthy, “Dynamic coverage maintenance algorithms for sensor  networks with limited mobility,” in Proc. 3rd   IEEE Int. Conf. Pervasive Comput. Commun. (PerCom), Kauai Island, HI, Mar. 2005, pp. 51 – 6 60. 0.

[29] Poduri S, Sukhatme GS (2004) Constrained Constrained coverage for mobile sensor networks. In: Proc. of IEEE ICRA

[30] F. Aurenhammer, “Voronoi Diagrams—A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys 23, pp. 345-405, 1991. [31] A. Jagga, Kuldeep, and V. Rana

“A Hybrid Approach for Deploying Mobile Agents in Wireless

Sensor Network”, IJCA, 2012. [32] Networks G. Wang Wang,by , L.Biogeography Guo, H. D Duan, uan, L L.. Optimization Liu and H. W Wang ang, ”Dynamic Deployment of Wireless ”,  J. Sens. Actuator Netw. Based Algorithm 2012, 1, Sensor 86-96; doi:10.3390/jsan1020086.

Authors Mayur Akewar received the Bachelor of Engineering degree in Computer Technology from Karmvir Dadasaheb Kannamwar College of Engineering, Nagpur, India in 2010. Presently he is pursuing his PG (M.Tech) in Computer Science and Engineering from Shri Ramdeobaba College of Engineering & Management, Nagpur, India. His research interest includes Wireless Sensor Network . He is a life member of ISTE New Delhi India.

33

 

Internationa Intern ationall Journal of Wirele Wireless ss & Mobile Netwo Networks rks (IJWMN (IJWMN)) Vol. 4, No. 5, Octob October er 2012 Dr. Nileshsingh V. Thakur received Bachelor of Engineering degree in Computer Science Engineering from Government College of Engineering, Amravati, India and Master of Engineering degree from College of Engineering, Badnera under Amravati University and Sant Gadge Baba Amravati University in 1992 and 2005 respectively. He received Ph.D. degree in Computer Science Engineering under Department of  computer Science Engineering from Visvesvaraya National Institute of Technology, st Nagpur, India on 1 February, 2010. His research interest includes image processing,

sensor network, computer vision, pattern recognition, artificial neural network and evolutionary approaches. He is having over 20 years of teaching and research experience. Presently, he is Associate Professor in Department of Computer Science and Engineering at Shri Ramdeobaba College of  Engineering and Management, Nagpur, India. He is the author or co-author of more than 40 scientific publications in International Journal, International Conferences and National Conferences. Dr. Thakur is a member of editorial board of over eight International journals; also, he is the life member of ISTE, India, IAENG and IAEME. He also worked as the reviewer for international journals and conferences.

34