Ant Colony Based Sleep/Wakeup Scheme with Added Heuristic Information (AC – SWSH)

Ant Colony Based Sleep/Wakeup Scheme with Added Heuristic Information (AC – SWSH)

Devi Dayal Vinayakhi J

Abstract

An effective method is proposed to maximize the lifetime of Wireless Sensor network as well as providing the point coverage in the target area. In addition to the pheromone trails, coverage and energy heuristics are used to improve the results by ants. Inspired by the performing behaviour of ants, simulated ants are used to find the subset of sensors by traversing through the subset building graph.

Keywords Ant Colony Based Sleep/Wakeup Scheme with added Heuristic information (AC_SWSH), subset building graph, coverage heuristic, energy heuristic and pheromone trails.

1. Introduction

   With the advancement of wireless devices, the communication becomes easy. Wireless communication is of major concern in the communication field. There are many wireless devices available. Among those, one of the most advantageous devices is sensor. The sensors are the devices that sense the environment or monitor the specific point of interest and transmit that information to the base station which acts as a gateway between the sensors and the end users.

   The coverage can be of three major types area coverage, point coverage and barrier coverage. Area coverage means that every single point inside the target area is monitored fully i.e. it falls inside the sensing range of at least one sensor. Point coverage is to monitor specific point of interests in the target area. Barrier coverage is to look for breach among a barrier. Here we concentrate on point coverage. The specific Point of Interest (PoI)s are monitored effectively and at the same time maximizing the network lifetime.

   The point coverage has many applications such as in detecting forest fire and much kind of surveillance applications. These PoIs are monitored by the sensors. As the sensors continue monitoring, its energy level decreases. Here the energy source used is the battery. However the battery used in the sensors is non-replenishable battery. Hence the energy used by the sensors should be minimized

   without reducing the coverage of the point of interests.

   Optimization is finding a perfect solution by maximizing the desired parameters while reducing the undesired parameters.

   The Ant Colony Optimization (ACO) is a technique for solving computational problems. From the observation of the exploitation of food resources among ants, a method to find the shortest path is developed.

   In nature, initially the ants wander randomly in the search of their food source. Upon finding the food, they return to their nest by laying down pheromone (a chemical secreted by an ant that influence the behavior or development of the same species) trails. If other ants find such a path, they mostly follow these trails instead of travelling at random.

   These pheromone trails evaporate at constant rate over time. If an ant takes more time to travel back and forth in a path, then the evaporation rate will be more. Hence the following ants will eventually follow the shortest path in which the density of the pheromone trails will be more compared to the longer path. In computer science, this is done by

   simulated ants walking around a graph which represents the problem to be solved.

2. Related works

   There are a number of mechanisms to solve Efficient Energy Coverage (EEC) problem. Many Ant Colony approaches are also possible to solve the above problem. Among them some of the techniques are listed below.

   The Any System was proposed by M. Dorigo [26] based on distributed auto-cyclic process and its application to the solution of classical optimization problem. Later, a novel approach of Ant Colony System to travelling salesman problem was proposed [25]. But in this the shuffling of both local and global pheromones is a disadvantage.

   Many approaches are proposed to maintain sensing coverage and connectivity, such as keeping a minimal number of active sensor nodes [19], using Optimal Geographical Density Control (OGDC) algorithm and Optimal Coverage-Preserving Scheme (OCoPS) to resolve off-duty conflict.

   To maximize the lifetime of wireless sensor networks, methods such as Schedule Transition

   Hybrid Genetic Algorithm (STHGA) [10] by finding maximum number of disjoint complete cover sets of sensors and an anycast packet forwarding scheme

   [14] by reducing the event-reporting delay are introduced. Using these, sleep-wake scheduling policy has some drawbacks such as the correlation between the hop count and delay is weak.

   The recent techniques to improve the coverage such as using connected dominating set [21], Scheduling based Coordinated Sleep Protocol (S-CSP) [27], Three Pheromone Ant Colony Optimization (TPACO) [2] and Ant Colony Based Scheduling Algorithm (ACB-SA) [3] are proposed to solve EEC problem in point covered network.

   Many other techniques such as coverage and connectivity in duty-cycled WSN [7], reliable and efficient target coverage [5] using heat maps [6], probabilistic sensing model [8], relay node placement [4], connected sensor cover [16] with fault tolerance [18] and improved approximation [20] and a localized approach [9] are proposed for energy efficient area monitoring and coverage [24]. Also the ant colony approaches like energy consumption optimization for WSN [11], optimized discounted cash flow [12] and grid work flow [13] are proposed to improve the coverage.

3. Methodology

   The Ant Colony based Sleep/Wakeup Scheme with added Heuristic information (AC SWSH) is an efficient method for solving the Energy Efficient Coverage (EEC) problem

   .

   3.1 Problem description

   In the target area , randomly deploy a set of sensors where is the

   total number of sensors. The sensing and transmission range of the sensors are and respectively. The problem is to find the maximum number of subset that fully covers all the Point of

   Interest (PoI)s in the

   target such that satisfies the following 4 constraints:

   1. Sensing constraint:

      The sensors in the subset should fully cover all the Point of Interests in the target area .

   2. Transmission constraint:

      It is assumed that at least there is a sensor within the transmission range of the sensors so that they all can form a path to reach the base station.

   3. Energy constraint

      Any sensor can be in the subset until its energy level is completely depleted.

      1. Subset Building Graph

         In the proposed method, the ants construct the solution not only based on the pheromone trails but also includes additional parameter the coverage heuristic. The traverses through the subset building graph. The subset building graph consists of vertices which can be arranged into a . The ant traversal starts from the sensor which covers the first PoI. The sensor with maximum probability is chosen from each column of the graph. The probability is calculated from the pheromone and coverage heuristic values. The vertices selected by the ant are included in the Solution subset. Then the solution is checked whether it covers all the PoIs. If it satisfies, then it is included in the Final-Solution subset. Finally the pheromone is updated by the ant.

         Fig. 1 An example subset building graph with =3 and =5. The ant traversal is shown

         by the line

         The ant starts the tour by traversing on the subset building graph and selects the sensors based on the pheromone trails and the heuristic information. The selected sensors are added to the solution subset. If thissubset covers all the PoIs then the solution is added to the final-solution subset. The procedure is repeated for all the ants in the ant colony.

         Fig.1 shows an example of the subset building graph. Here the green colour represents the PoI is covered by the corresponding sensor.

         The architecture diagram for the proposed method is shown in fig. 2. The ants constructs solution and the best solution from the colony of ants are selected and made active at time

         In this algorithm, the two user parameters of the

         ant colony are reduced to only one user parameter. Also it uses two types of pheromone values which further improve search efficiency.

         The energy level of the sensors is used to decide whether or not to use the sensor in the active sensors list. The sensors are used until their battery level is depleted completely. This is the termination condition used in the proposed method.

         The PoI are covered fully by using this method and the subset of sensors provides full point coverage as well as maximizes the lifetime of sensor network by efficiently scheduling the sensors based on their coverage and energy heuristics.

         Fig. 2 Architecture diagram of proposed method

      2. Algorithm

   4. Implementation and results

      1. Implementaion

         The experiments are done in MATLAB and the lifetime of the WSN are given in the results section.

      2. Results

         The proposed AC-SWSH scheme is evaluated based on the experiments done to maximize the lifetime of WSN.

         TABLE I LIFETIME OF WSN

         Testcase No.	No. Of nodes	Lifetime of WSN
         1	10	15
         2	20	28
         3	30	37
         4	40	42
         5	50	54

         Fig. 3 Lifetime of WSN

   5. Conclusion

The proposed method improves the performance by added energy and coverage heuristic values. Also the two user parameters of the ant colony are reduced to only one parameter. By using the method the lifetime of Wireless Sensors are improved.

References

1. Ying Lin, Jun Zhang, Henry Shu-Hung Chung, Wai Hung Ip, Yun Li and Yu-Hui Shi, An Ant Colony Optimization Approach for Maximizing the Lifetime of Heterogeneous Wireless Sensor Networks, IEEE Transactions on Systems, Man, and CyberneticsPart C: Applications and Reviews, VOL. 42, NO. 3, May 2012.

2. Joon-Woo Lee, Byoung-Suk Choi, and Ju-Jang Lee, Energy- Efficient Coverage of Wireless Sensor Networks Using Ant Colony Optimization with Three Types of Pheromones, IEEE Transactions on Industrial Informatics, VOL. 7, NO. 3, Aug. 2011.

3. Lee, J.-W.; Lee, J.-J., Ant-Colony-Based Scheduling Algorithm for Energy-Efficient Coverage of WSN, IEEE Journal on sensors, 2012.

4. Yang, Dejun; Misra, Satyajayant; Fang, Xi; Xue, Guoliang; Zhang, Junshan, Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks: Computational Complexity and Efficient Approximations, IEEE Transactions on Mobile Computing, 2012.

5. He, Jing; Ji, Shouling; Pan, Yi; Li, Yingshu, Reliable and energy efficient target coverage for wireless sensor networks, Tsinghua Science and Technology, 2011.

6. Jeong, Y.S.; Chung, Y.J.; Park, J.H., Visualisation of efficiency coverage and energy consumption of sensors in wireless sensor networks using heat map, Communications, IET, 2011.

7. Shibo He; Jiming Chen; Youxian Sun, Coverage and Connectivity in Duty-Cycled Wireless Sensor Networks for Event Monitoring, IEEE Transactions on Parallel and Distributed Systems, 2012.

8. Jiming Chen; Junkun Li; Shibo He; un; Hsiao-Hwa Chen, Energy-Efficient Coverage Based on Probabilistic Sensing Model in Wireless Sensor Networks, Communications Letters, IEEE , 2010.

9. Pervin, N.; Layek, D.; Das, N., Localized algorithm for connected set cover partitioning in wireless sensor networks, International Conference on Parallel Distributed and Grid Computing (PDGC), IEEE Conference Publications, 2010.

10. Xiao-Min Hu; Jun Zhang; Yan Yu; Chung, H.S.-H.; Yuan- Long Li; Yu-Hui Shi; Xiao-Nan Luo, Hybrid Genetic Algorithm Using a Forward Encoding Scheme for Lifetime Maximization of Wireless Sensor Networks, IEEE Transactions on Evolutionary Computation, 2010.

11. Lianyu Wang, Qinglin Sun, Hongwen Mal, Energy Consumption Optimize Based On Ant Colony Algorithm for Wireless Sensor Networks,2010 2nd International Asia

    Conference on Informatics in Control, Automation and Robotics,

    2010.

12. W.-N. Chen, J. Zhang, H. S.-H. Chung, R.-Z. Huang, and O. Liu, Optimizaing discounted cash flow in project scheduling: An ant colony optimization approach, IEEE Trans. Syst., Man,

    Cybern., Part C, vol. 40,no. 1, pp. 6477, Jan. 2010

13. W.-N. Chen and J. Zhang, An ant colony optimization approach to a grid flow scheduling problem with various QoS requirements, IEEE Trans.Syst., Man, Cybern., Part C, vol. 39, no. 1, pp. 2943, Jan. 2009

14. Joohwan Kim, Xiaojun Lin, Member, IEEE, Ness B. Shroff, Fellow, IEEE, and Prasun Sinha, Minimizing Delay and Maximizing Lifetime for Wireless Sensor Networks with Anycast, IEEE Infocom, 2008.

15. F. Ge, Y. Wang, Q. Wang, and J. Wang, Energy efficient broadcasting based on ant colony optimization in wireless sensor networks, in Proc. IEEE Int. Conf. Nat. Comput., Haiko, China, 2007, pp. 129133

16. Gupta, H.; Zongheng Zhou; Das, S.R.; Gu, Q., Connected sensor cover: self-organization of sensor networks for efficient query execution, IEEE/ACM Transactions on Networking, 2006.

17. Yi Zou; Chakrabarty, K., A distributed coverage- and connectivity-centric technique for selecting active nodes in wireless sensor networks, IEEE Transactions on Computers, 2005.

18. Zongheng Zhou; Das, S.; Gupta, H., Fault tolerant connected sensor cover with variable sensing and transmission ranges, Sensor and Ad Hoc Communications and Networks, 2005. IEEE SECON 2005. 2005 Second Annual IEEE Communications Society Conference.

19. H. Zhang and J. Hou, Maintaining sensing coverage and connectivity in large sensor networks, Ad Hoc Sensor Wireless Networks, vol. 1, pp. 89124, Mar. 2005.

20. S. Funke, A. Kesselman, F. Kuhn, Z. Lotker, and M. Segal, Improved approximation for connected sensor cover, Wireless Networks, vol. 13, no. 2, pp. 153164, Apr. 2007.

21. Fei Dai, Student Member, IEEE, and Jie Wu, Senior Member, IEEE, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions On Parallel And Distributed Systems, VOL. 15, NO. 10, OCTOBER 2004.

22. Carle, J.; Simplot-Ryl, D., Energy-efficient area monitoring for sensor networks, IEEE Computer Society, 2004.

23. K. R¨omer, F.Mattern, and E. Zurich, The design space of wireless sensor networks, IEEE Wireless Commun., vol. 11, no. 6, pp. 5461, Dec. 2004.

24. Xiang-Yang Li; Peng-Jun Wan; Frieder O., Coverage in wireless ad hoc sensor networks, IEEE Transactions on Computers, 2003.

25. M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 5366, Aug. 1997

26. M. Dorigo, V. Maniezzo, and A. Colorni, The ant system: Optimization by a colony of cooperating agents, IEEE Trans. Syst., Man, Cybern., Part B, vol. 26, no. 1, pp. 113, Feb. 1996

27. Shibo He; Jiming Chen; Yau, D.K.Y.; Huanyu Shao; Youxian Sun, Energy-Efficient Capture of Stochastic Events under Periodic Network Coverage and Coordinated Sleep, IEEE Transactions on Parallel nd Distributed Systems,2012.