Enhancing Coverage of a Sensor Field using Augmented Lagrange Optimization

Enhancing Coverage of a Sensor Field using Augmented Lagrange Optimization

Shivani Dadwal

Baba Banda Singh Bahadur Engineering College Fatehgarh Sahib, India

Tripatjot Panag

Baba Banda Singh Bahadur Engineering College Fatehgarh Sahib, India

Abstract In an inaccessible area, sensor laden mobile robots can be used for observation and for collecting information. Repositioning these sensors after an initial random deployment can be done using average distance based self- relocation method which produces a good final coverage. This

the sensors as well as the obstacles. Each sensor will exert a force on the other sensors and hence each sensor will be impacted upon by a force which a composition force from all the other sensors in the potential field. The forces can be calculated from the following formulae:

coverage can further be improved by containing the sensors

=

1 .

(1)

within the boundary using Augmented Lagrange method.

Keywords Sensors, average distance based self-relocation,

2

1

augmented Lagrange method

1. INTRODUCTION

   Sensor network is a popular field and a lot of research has been done on various aspects of this field like deployment schemes, communication among sensors, energy constraints etc. the wireless sensor area can be classified as accessible and inaccessible. In an accessible area, the sensors can be kept at fixed positions in any for like square, rhombus, hexagonal etc. in order to cover the field with their sensing range. For an inaccessible area, sensor deployment becomes a problem. Examples of inaccessible areas can be enemy area, areas hampered by natural calamity, areas having extreme climatic conditions etc. for extracting information in these areas, aerial deployment of sensors are done. Sensors position randomly in the required field and hence require redeployment.

   A lot of redeployment algorithms have been introduced in the past. [1], [2] and [3] have discussed these various contexts. Work in [4] has proposed coarse grained and fine grained localization techniques for spatial and adaptive beacon placement.

   In the area of military applications [5] discussed various methods that could help in planning sensor placement. In this paper a sensor model has been described which can detect indefinable targets in the battlefield. The drawback of this approach was that it required a lot of former knowledge of the area in which the sensors are to be deployed. This is practically not possible in case of battlefield where field terrain and conditions are unpredictable. Hence, this distributed sensor network format cannot be used in the field whose prior knowledge is unknown.

   For multi robot exploration, sensor deployment was discussed [6]. A framework was introduced in which the robots are considered to be sensors. The robots are deployed one by one in a particular fashion. This method of sensor placement had a drawback that a lot of computation was required in it. If the number of robots alias sensors are to be increased then the computation becomes even more complex. In this potential field method, a virtual field is created by all

   = 2 . (2)

   Here, and are the notations for the forces exerted by other sensors and the obstacles in the area. denotes the directional vector which is pointing towards the sensors or the obstacles in the area with its magnitude. The negative sign before both the equation signify that they are repulsive forces. All the sensors in the area are assigned a particular weight so that they move in the specified area which depends on the amount of force applied to them. Through this work, sensors make a uniform distribution in their field after random deployment and hence the coverage is increased. Virtual frictional effects are also applied so that the algorithm can converge faster. It has been proved that equilibrium state can

   be achieved in a sensing field with boundaries. As a result, the sensors in the sensing field will rearrange themselves into a more uniform distribution after being randomly deployed, and also, the networks coverage can be significantly increased.

   In [7] the problem of coverage evaluation once the sensors are deployed has been discussed. This work considers the sensors to be mobile and hence the coverage of sensors keep changing. A polynomial time algorithm has been introduced in this work taking the best and worst cases into consideration.

   In the area of surveillance, sensor deployment in the form of radar and sonar has also been worked upon. In work done by [8], various challenges have been discussed that come in the path of radar and sonar coverage. A method has been introduced in this work for proper tailing with limited number of radars, based on cross section and coverage of each radar.

   Integer linear programming has been used to solve the sensor placement problem in two and three dimensional grids in work done by [9], [10]. There are mainly two drawbacks in this method. First is the computational complexity. Secondly, perfect sensor detection is required i.e. yes/no is required as the outcome of each detection by the sensors. However, a probabilistic model should be used for sensor detection for appropriate results.

   A probabilistic optimization framework for minimizing the number of sensors for a two-dimensional grid has been

   proposed recently by [11]. This algorithm attempts to maximize the average coverage of the grid points. Finally, there exists a close resemblance between the sensor placement problem and the art gallery problem (AGP) addressed by the art gallery theorem by [12].

   Various other works has been done on sensor deployment which aims at improving the performance of sensor network in pretext of communication cost or energy consumption etc.

   Work done in [13], introduced a virtual force algorithm. The major difference between [6] and [13] is that [13] has both repulsive and attractive forces between sensors, whereas

   [6] only has the repulsive force. The force depends on the distance between sensors and their relative position.

   Different force models have been derived, including the impact of hotspots and obstacles model by Li et al.,[14]. A ranking system has also been applied to the force model, so that the algorithm can be used for varying application requirements.

   In [15] improved virtual force algorithm was discussed by applying a back-off delay time in the virtual force algorithm. The back-off delay time is used such that the sensors relocate themselves one-at-a-time in each round of movement. Thus, each sensor will have the most updated position information of the other sensors, including the movement of previous sensors within the current round. In this way, the sensors can move less than if they use the aged location information.

   It should be pointed out that the virtual force related algorithms described above require that each sensor knows the exact or relative positions of all other sensors in the network.

   eight, hexagonal subareas, according to the relative direction. Then, the sensor density of each subarea was calculated, according to the number of sensors and the area of obstacles in that subarea. Then, the sensors moved toward the subarea that has the least density.

   The deployment algorithms above are not designed to converge fast. However, the convergence speed is an important factor in real time applications.

2. ASSUMPTIONS AND MODELS

   1. Assumptions

      or simplicity and for structuring the model, a few assumptions are taken as stated below:

      1. All the sensors are movable and are capable of moving to positions they are instructed to.

      2. All the sensors have a circular sensing area and communication area. The sensing radii is and the communication radii is . Also, > , which helps in providing better connectivity in the wireless sensor network.

      3. All the sensors are geo- location capable.

      4. The sensor has pre- knowledge installation about the sensing field boundary.

   2. Sensing Models

      Different sensing models have been discussed in [13]. The two basic models are the binary sensing model and probability sensing model:

      1

      In other words, location information for sensors is required,

      = { < +

      (3)

      and must somehow be communicated throughout the network. Other deployment algorithms for randomly distributed mobile sensor networks were proposed by [16], [17], and [18]. These algorithms require that each sensor knows only the relative locations of sensors that are in its communication

      range, or its neighborhood.

      Specifically, [16], used Voronoi diagrams to detect areas that are not covered, or the sensing holes, and determined the

      0 + <

      For a binary model = 0 and for a probability model,

      > 0. and are the locations of target and sensor respectively. is the distance between target and sensor. a = , and are the constants that are related to hardware properties of sensors.

      The joint detection probability of sensors can be calculated from the following equation:

      way the sensors should move to cover those areas. Three

      = 1 =(1 )

      (4)

      different optimization algorithms have been developed: vector based optimization (VEC), Voronoi diagram based

      =1

      In the above equatio

      n, can be calculated from Eq (3).

      optimization (VOR), and Minimax optimization. The VOR and Minimax have similar performances that are better than the VEC when sensor nodes have low density. These algorithms also used a virtual movement method. With this method, each sensor calculates the future movements of all neighboring sensors and tracks these virtual movements to predict their future locations using the virtual locations. This prediction technique is repeated several times, and then the sensor moves only once. By using the virtual movement method, the total distance of sensor relocation is greatly decreased, along with the energy consumed.

      Furthermore, [17], used a fluid model for sensor relocation. In this algorithm, the author compared the mobile sensor network to a fluid model. The sensors are treated as fluid elements in a continuous medium, which represents the unknown sensing field. This algorithm can optimize the sensing coverage.

      In [18], a density control coverage optimization algorithm was discussed. Each sensor divided its surrounding area into

   3. Ideal Coverage model

   The problem of seamless coverage in sensor networks was analyzed by [19]. Optimal deployment of sensors is achieved when all sensors have the same equal sensing radius. The optimal layout is shown Fig.1. This is an ideal coverage model for the binary sensing model. This can be used for the deterministic deployment of sensors when the boundary of sensing field has are gular shape and there are no obstacles in the sensing field.

   Fig.1 shows that in the ideal coverage model, sensors are deployed regularly with same distance between them. The distance between sensors can be calculated by the sensing radius:

   = 3. (5)

   Fig.1: Ideal coverage model

3. ALGORITHM DESCRIPTION

   The algorithm comprises of a continuous moving process of all the sensors periodically. Each period of the algorithm is called a round. The average distance algorithm is modified by augmented Lagrange method. The algorithm steps can be described in a form of a flowchart given in figure 2.

   The algorithm consists of two different parts. The first part is the average distance self- relocation process for the sensors that are at random position initially. They are assigned a proper position after the program is executed. The second part is optimization using augmented Lagrange method. In this the sensors are stopped from crossing the boundary while relocating themselves.

   1. Average distance based self -relocation process

      In this process, virtual nodes are considered outside the boundary, so that the sensors do not overlap the boundary and decrease the overall coverage. This has been discussed in [20] and [21]. In this algorithm, the concept of virtual nodes is omitted as augmented Lagrange is applied to the deserving sensors.

      The steps of average distance algorithm are described below:

      Step 1: Pre-knowledge installation

      • Load sensing range, sensing area and sensors number to sensors memory.

      • Load desired round number, set the current round to be round 1.

      • Calculate dth, r.

        Step 2: Round Initialization

      • Calculate the average distance d between sensors

      • Compare the distance condition with the criteria condition and make a moving decision

      • Calculated travel if needed

      • Broad cast moving decision

      • Receive moving decision from other sensors

      • Record the number of neighboring sensors that need to move

        Step 3: Self-relocation

      • If no other sensor nodes declared moving direction choosing process, set random time T (conflict avoidance)

        • Broadcast Self-relocation ON

        • Choose random direction and move short distance

        • Broad cast message Reference node

        • Receive hello message respond to message Reference node

        • Re-calculate average distance d

        • Decide moving direction according to the criteria objective

        • Move to destination position and send message Self-relocation OFF.

      • If a Self-relocation ON is received, a sensor will not start the timer T. It will wait until a message Self-relocation OFF is received.

      • When all sensors finish relocating, this round of the algorithm is finished.

        • If the round number is equal to maximum allowed round number, go tostep4.

        • Otherwise, go to step2 and start a new relocation round.

          Step 4: All sensors stop.

          Fig.2: Flowchart for augmented Lagrange process

   2. Coverage Optimization using Augmented Lagrange method

      The augmented Lagrange method is followed when sensors go out of the boundary while relocating themselves. The augmented Lagrange process helps these sensors to get back into the boundary. The steps algorithm steps for augmented Lagrange are given below:

      • The [X] co-ordinates of all the sensors in the sensing field are obtained after the execution of first iteration of average distance based relocation algorithm.

      • The boundary constraint violations are checked i.e. it is checked if any sensor is lying on the boundary or beyond the boundary. The constraints are checked n times which is equal to the number of sensors in the field.

      • If any constraint is violated, let us say for nth sensor, [g1]i 0, which means that constraintg1is violated by ith sensor and the sensor is moving beyond the boundary of sensing field. Hence, the distance Di is calculated between g1 and [X, Y]i. X and Y are the co-ordinated of ith sensor lying outside the boundary.

      • To compensate for distance and to bring the sensor back inside the field, negative of distance Di is added in g1 and the new co-ordinates of ith sensor are calculated.

      • Now, all the co-ordinates serve as initial solutio for average distance based algorithm which is run again.

      • The threshold distances are again checked in the self -relocation algorithm.

4. SIMULATION AND RESULT ANALYSIS

   In simulation process of average distance algorithm, a 60 m by 60 m square sensing field is used. The minimum distance between grid points is 1 m. A total of 20 sensors are considered in the sensing field. The sensing range of sensors is usually between 18 25 m. Therefore, we set the maximum sensing range for our algorithm to be 25 m. The communication range is set to be 55 m, i.e., two times larger than the sensing range in order to guarantee network connectivity.

   In the first one the sensors are deployed randomly such that they accumulate at the same place. The coverage initially is 49%. In the second condition, the sensors are deployed or scattered in the whole sensing area with initial coverage of 61%. In the third condition, sensors are divided into 2 groups which are separately placed in the sensing field having initial coverage 50%. All the cases in the optimization algorithm converge to almost 96% coverage. Thus, the coverage increases by 2% as compared to average distance based deployment [20].

   Fig.3: Initial deployment with sensors scattered in the sensing field

   Fig.4: Final deployment after the execution of algorithm

   REFERENCES

5. CONCLUSION

The average distance based self-relocation algorithm is made better taking the factors coverage and energy consumption into account. It is realized that the coverage of average distance algorithm improves by using augmented Lagrange approach.

This work focuses on algorithms tested in the software simulations. These simulations can be expanded to experimental works with deployment of real mobile wireless sensor networks. Programmable mobile sensor kits can be used and relocation algorithms can be tested in indoor as well as outdoor locations. Different hardware modules can be added or removed from sensor nodes for specific applications. An attempt can be made to redeploy sensors without GPS.

1. H. Qi, S. S. Iyengar, and K. Chakrabarty, Multi-resolution data integration using mobile agents in distributed sensor networks, IEEE Transactions on System, Man and Cybernetics (Part C), vol. 31, pp: 383-391, August 2001.

2. S. S. Iyengar, L. Prasad and H. Min, Adances in Distributed Sensor Technology, Prentice Hall, Englewood Cliffs, NJ, 1995.

3. D. Estrin, R, Govindan and J. Heidemann, Scalable coordination in sensor networks, Technical Report 99-692, University of South California, 1999.

4. N. Bulusu, J. Heidemann and D. Estrin, Adaptive beacon placement, Proceedings International Conference on Distributed Computing Systems, pp: 489-498, 2001.

5. S. A. Musman, P. E. Lehner and C. Elsaesser, Sensor Planning for Elusive Targets, Journal of Computer & Mathematical Modeling, vol. 25, no. 3, pp: 103-115, 1997.

6. A. Howard, M. J. Mataric´ and G. S. Sukhatme, Mobile Sensor Network Deployment Using Potential Field: a distributed scalable solution to the area coverage problem, to appear in Proceedings International Conference on Distributed Autonomous Robotic Systems, June 2002.

7. S. Meguerdichian, S. Slijepcevic, V. Karayan and M. Potkonjak, Coverage problems in wireless ad-hoc sensor networks, Proceedings of IEEE Infocom, vol. 3, pp: 1380-1387, 2001.

8. N. B. Priyantha, A. Chakraborty and H. Balakrishnan, The cricket location-support system, Proceedins ACM/IEEE International Conference on Mobile Computing and Networking, pp: 32-43, 2000.

9. K. Chakrabarty, S. S. Iyengar, H. Qi and E. Cho, Grid coverage for surveillance and target location in distributed sensor networks, IEEE Transactions on Computers, vol. 51, pp: 1448-1453, 2002.

10. K. Chakrabarty, S. S. Iyengar, H. Qi and E. Cho, Coding Theory Framework for Target Location in Distributed Sensor Networks, Proceedings International Symposium on Information Technology: Coding and Computing, pp: 130-134, 2001.

11. S. S. Dhillon, K. Chakrabarty and S. S. Iyengar, Sensor placement algorithms for grid coverage, Proceedings International Conference on Information Fusion, pp: 1581-1587, 2002.

12. J. ORourke, Art Gallery Theorems and Algorithms, Oxford University Press, New York, NY, 1987.

13. Yi. Zou and K. Chakrabarty, Sensor deployment and Target Localization Based on Virtual Forces, IEEE Societies Twenty Second Annual Joint Conference of the IEEE Computer and Communications (INFOCOM), San Fransisco, pp: 1293-1303, 1-3 April 2003.

14. S. Li, C. Xu, W. Pan and Y. Pan, "Sensor deployment optimization for detecting maneuvering targets," in 8th International Conference on Information Fusion, PA, USA, July 25-29, 2005.

15. T. Wong, T. Tsuchiya and T. Kikuno, "A self-organizing technique for sensor placement in wireless micro-sensor networks," in 18th

    International Conference on Advanced Information Networking and Applications, Fukuoka, Japan, March 26-29, 2004.

16. G. Wang, G. Cao and T. F. Porta, "Movement-Assisted Sensor Deployment, Transactions on mobile computing, vol. 5, pp. 640-652, 2006.

17. M. R. Pac, A. M. Erkmen and I. Erkmen, "Scalable Self-Deployment of Mobile Sensor Networks: A Fluid Dynamics Approach," in Proceeding of IEEE International Conference on intelligent Robots and Systems (RSJ), Beijing, China, October 9-15, 2006.

18. R.-S. Chang and S.-H. Wang, "Self-Deployment by Density Control in Sensor Networks," IEEE transactions on vehicular technology, vol. 57, pp: 1745-1755, 2008.

19. X. Wang, F. Sun and X. Kong, "Research on Optimal Coverage Problem of Wireless Sensor Networks," in WRI International Conference on Communications and Mobile Computing, Kunming, China, pp: 548-551, January 6-8, 2009.

20. Y.Qu, S.V. Georgakopoulos, An average Distance Based Self- Relocation and Self-Healing Algorithm for Mobile Sensor Networks, Journal of Wireless Sensor Network, vol. 4, no. 11, pp: 257-263, 2012.

21. Dadwal Shivani, T.S. Panag,Optimization of average distance based self-relocation algorithm using augmented lagrangian method, 2nd International Conference on Computer Science and Information Technolohgy, Chennai, pp: 193197, 2015.