Energy Efficient Coverage by Sensor Scheduling in Wireless Sensor Networks

Energy Efficient Coverage by Sensor Scheduling in Wireless Sensor Networks

1. Janani

   Assistant Professor,

   Department of Computer Science& Engineering Jansons Institute of Technology

   Coimbatore, India.

   P. Ravi Kumar Assistant Professor,

   Department of Electrical & Electronics Engineering Jansons Institute of Technology

   Coimbatore, India

   Abstract — In WSN, sensors work with batteries. Sensors have only limited amount of energy in batteries. It is infeasible to recharge or replace batteries in case of discharge. It is necessary to schedule the activities of the sensors in WSN for Energy Efficient Coverage (EEC). By scheduling, the optimal sensor subsets are formed at each timeslot, which covers all the points of interest in the targeted area. So, the limited energy of the sensors can be saved, which prolongs the network lifetime in WSN. In this paper, we propose an Ant Colony Based Sensor Scheduling (ACB-SS) algorithm in order to maximize the network lifetime and the energy coverage of the sensors. The probabilistic sensor detection model is also used. The proposed algorithm is compared with the traditional ACO. Simulation results are performed to verify the effectiveness of the proposed algorithm.

   Keywords -Wireless Sensor Network (WSN); Energy Efficient Coverage (EEC); Ant Colony Based Sensor Scheduling (ACB- SS); Ant Colony Optimization (ACO); Heterogeneous sensor set.

   I INTRODUCTION

   WSNs are the networks consists of autonomous devices that can sense or monitor physical or environmental conditions. Developers of wireless sensor network faced challenges that arise from communication link failures, memory, computational constraints and limited energy. WSNs are networks that consist of many (i.e., few tens to thousands) tiny sensors (or devices). Each device usually has four parts: a processer, sensor, transceiver, and battery. Each device is a low-power, low-cost, multi-functional, small embedded system. A wide variety of sensors (e.g., thermal, mechanical, optical, biological, and magnetic sensors) may

   be included in the device to measure properties of the environment. These sensors sense, measure, or gather information from environment, and they transmit the sensed data, which were acquired through some local decision process to the user. WSN applications are used in a wide range of areas, e.g., military target tracking [12] and surveillance, biomedical health monitoring, smart home management, building environment control, greenhouse monitoring, pollution monitoring, automobile communication, natural disaster relief, and hazardous environment exploration and seismic sensing. WSNs are

   especially used in the control and management of various

   industrial systems. Typically, sensor nodes are grouped in

   clusters, and each cluster has a node that acts as the cluster head. All nodes forward their sensor data to the cluster head,

   which in turn routes it to a specialized node called sink node (or base station) through multi-hop wireless communication.

   The Energy-Efficient Coverage (EEC) problem is an important issue when implementing Wireless Sensor Networks (WSNs) because of the need to limit energy use. It is therefore necessary to schedule the activities of the devices in a WSN so that this can save the networks limited energy and prolong the lifetime of a WSN[16]. In this work, proposed a new approach called Ant Colony Based Sensor Scheduling (ACB-SS) to solve the EEC problem. In this approach, the main aim is the selection of a set of minimal active sensor nodes to be awake to maintain the coverage of an interest area. An optimal subset of the sensors that cover an interest area, or all points of interest then carries out a sensing task, while other devices can be put in to sleep state to save the energy. By scheduling the devices activities from active to sleep or vice versa can prolong the lifetime of WSN by more efficient use of the limited amount of energy. Eventually, to achieve a longer lifetime, it will be important to find the maximum number of disjointed subsets of devices by this scheduling method.

   II ANT COLONY OPTIMIZATION

   The ACO algorithm is a natural metaphor algorithm based on the foraging behavior of real ants.

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

   These pheromone trails evaporate at a constant rate over time. Pheromone decay factor is given by , which is a constant. 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.

   optimized sensor subset which covers all PoIs with a minimum aggregate cost for a time slot. Cost is a kind of a score evaluated after obtaining the sensor subsets for a time slot. Cost associated with each sensor increases in accordance with the energy consumption. The cost for an active sensor node i is calculated as follows,

   Cost = k / ER,i

   (2)

   III ENERGY EFFICIENT COVERAGE (EEC) PROBLEM

   Real sensors detect the event (e.g., changes in heat, force, pressure) being monitored at a Point of Interest (PoI) by measuring the received signal (or energy) intensity[10]. This intensity of this energy is exponentially attenuated with the distance between the PoI and the measuring sensor. The probabilistic sensor detection model is used to solve the EEC problem, also reflects the characteristics of the real sensors and considers the uncertainty of event detection. The detection probability is continuously and exponentially a decreasing function of the distance between the PoI and the center of the sensor node. Let i(j) be the detection probability of sensor node I about events at PoI j.[10]

   (1)

   where dij is the Euclidean distance between the sensor node I and PoI j.The variables a and m are decay factors. Any event occurs at the PoI j are definitely detected if PoI j is within the distance of rs .The detection probability is reduced exponentially when the distance is greater than rs and it is zero if the distance is greater than ru .The variables a, m, rs and ru depend on the characteristics of the sensor and the environment.

   This paper focuses on finding the solution for the EEC problem that occurs mainly in the unstructured WSN, where the sensors are randomly placed in the field. This concerns how to optimally schedule the activities of the sensor devices, so that the energy consumption is limited and it maximize the lifetime of WSN.

   There are two main issues to solve EEC Problem. One is the sensing coverage issue ant the other is the network connectivity issue. The sensing coverage issue requires that the target points are perfectly covered by the sensing range of WSN. The network connectivity issue demands that the sensors form a fully connected network to the base station. The communication range rc of the sensors is at least twice its sensing range.(i.e, rc 2 rs)[17][18].

   The several assumptions are to be maintained to solve EEC problem. Initially the sensors are deployed randomly in the interest area and the position of the sensors and the PoIs are known. The operation time is divided in to timeslots. The scheduling algorithm is recursively performe to select an

   where k is a constant and k (0,1) , which represents the characteristics of the sensor, ER,i is the residual energy of the sensor node i.

   The formation of sensor subsets at a time slot is based on the selection of sensors which were used less at the previous timeslot, or those with a lot of remaining energy, which helps in extending the lifetime of WSN.

   PROBLEM STATEMENT

   Given a targeted region R, a set S of sensors (S

   {s1,s2,…….si,…sN), a set P of PoIs (P {PoI1, PoI 2,…….

   PoI i,… PoI T}), and a cost ci of sensor i (i=1,2,.,N), find a set C of the subsets C ts (ts=1,2,.,TS), of sensors that cover all PoIs in region R with a minimum total cost for a time slot until the WSN fails to cover and PoIs in region A. Then TS is the life time of WSN.

   The sensor subset obtained for each time slot is the optimal solution to the EEC problem, and the number of timeslots gives the lifetime of WSN.

   IV ACB-SS ALGORITHM FOR EEC PROBLEM

   In this section, the proposed ACB-SS algorithm is discussed in detail. The traditional ACO scheduling algorithms are not optimized to solve the EEC problem. The performance of ACO algorithm is determined by how it initializes the pheromone field and how it makes the construction graph. To improve the performance of ACO, the proposed algorithm is developed with the new initialization of the pheromone field and the modified construction graph.

   In the traditional ACO, the pheromone field is initialized with the randomly generated values. In ACB-SS, the position information of sensors and PoIs, residual energy of the sensors and also the number of PoIs covered by each sensor are calculated in the beginning of the process. With these values, the pheromone field is initialized to improve the performance. By doing this there was a strong possibility that the ants can select the sensors that cover more PoIs. Therefore, the initialization method helps to find the optimal solution as time progressed.

   The construction graph is a map that the imaginary ants in ACO algorithm use in order to construct the solution. It gives the performance of the problem. In ACO, the ant randomly selects more than one sensor at a time and is evaluated as to whether it covers all PoIs or not. If the selected sensor set covers all PoIs, then it is stored for the

   pheromone update. Otherwise these sets are thrown away, and then the next ant starts its travel. In ACB-SS, each ant adds one sensor (covers more PoIs) at a time while evaluating selection after each addition. Thus, the ants find solution until the selected sensor set covers all PoIs, by adding one sensor at a time. Therefore, the proposed construction graph helps in finding the optimal solution efficiently.

   In Fig.1, the ants constructs the solution and the best solution from the colony (C) of ants (A) are selected and made active at time ts. For each time slot the sensor active list to be maintained and it gives the optimal sensor subset for that time slot.

   In the algorithm 4.1, uses two types of pheromone values which improve the efficiency of searching process.

   The residual energy of the sensor 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 in the proposed method.

   The architecture diagram for the proposed method is shown in the Fig.1.

   Finally, all PoIs are covered by the optimal sensor subsets at each time slot, which maximizes the lifetime of WSN.

   ACB SS Algorithm Deployment ( );

   Initialize (C max, A max, ); ts 0;

   while C Cmax

   while A Amax Calculate coverage

   Calculate Energy and cost; Initialize Pheromone (S); Calculate probability; sense i= max_probability; Update local pheromone;

   end while

   Add sense i to solution with minimum cost; Add solution to the solution_final;

   Rank the solutions in solution_final;

   Add the best solution to active_list

   while the termination condition not met for every subset in active_list

   make active at ts;

   Update global pheromone;

   ts = ts +1; end for

   end while end while Lifetime Ts;

   V IMPLEMENTATION AND RESULTS

   The experiments are implemented using Network Simulator Version 2 (NS-2) with the Linux OS. The average network lifetimes are calculated for different scenarios and the number of active sensor nodes for a time slot is also evaluated.

   The proposed approach ACB-SS is evaluated based on the experiments done to maximize the lifetime of WSN. Table I shows the different scenarios.

   Individual Ant For each sensor

   Find Coverage, Energy and cost

   Find probability

   Repeat for all ants

   Select sensor

   By scheduling process, minimum number of active sensor nodes which covers all PoIs for each time slot is shown in the Fig.2 (Scenario 1) and the average network lifetime (Ts) is calculated. The aggregate cost for a timeslot is shown in Fig. 3 (Scenario 1).

   Deployment of sensors

   Ant Colony Approach

   Timeslot t

   s

   Individual colony

   Lifetime of WSN

   For every element in active list make

   sensors active at t

   s

   Add best solution to active list

   Update global pheromone

   Rank the solutions

   Add to sensor set

   Update local pheromone

   Fig.1. Architecture Diagram

   The network lifetime is increased in the proposed method by scheduling process.

   TABLE I. DIFFERENT SCENARIOS

   In the Table II, the average network lifetime of the proposed algorithm is compared with the traditional ACO. The network lifetime is improved in the proposed approach.

   Scenario	No.of Sensors	No.of PoIs
   Scenario 1	50	10
   Scenario 2	150	10
   Scenario 3	200	10
   Scenario 4	100	30
   Scenario 5	150	30
   Scenario 6	200	30

   The aggregate cost for each time slot is given in Fig. 3

   Fig.2. Time Slot Vs No. of Active Sensors

   Fig.3. Aggregate Cost Graph

   The average network lifetime for each scenario is given in the Table II.

   TABLE II. AVERAGE NETWORK LIFETIME FOR EACH ALGORITHM

   Scenarios		Average Network Lifetime
   No.of Sensors	No.of PoIs	ACO	ACB-SS
   50	10	53.24	54.98
   150	10	52.09	53.17
   200	10	51.54	52.88
   100	30	52.91	53.94
   150	30	52.27	53.36
   200	30	51.65	54.25

   VI CONCLUSION

   In this paper, the proposed algorithm is optimized to solve the EEC problem. The new pheromone initialization method by the position values, coverage and the energy information of the sensors and modified construction graph improves the performance i.e., network lifetime in ACB- SS.

   REFERENCES

   1. J. Yick, B. Mukherjee, and D. Ghosal, Wireless sensor network survey, Comput Netw., vol. 52, no. 12, pp. 2292 2330, Aug. 2008.

   2. G. Simon, M. Maroti, A. Ledeczi, G. Balogh, B. Kusy, A. Nádas, G. Pap, J. Sallai, and K. Frampton, Sensor network- based countersniper system, in Proc. Int. Conf. Embedded Netw. Sensor Syst., Nov. 2004, pp. 112.

   3. Z.Abrams,A.Goel,S.Plotkin Set K-cover algorithms for energy efficient monitoring in WSN,April 2004

   4. Chen J,Li J,He S,Sun Y and Chen H-H Energy-efficient coverage based on probabilistic sensing model in wireless sensor networks, IEEE Communications.Letters., vol.14,no.9,pp. 833-835,Sep.2010.

   5. Anastasi G, Conti M and Francesco M.D, Extending the lifetime of WSN through adaptive sleep, IEEE Trans. Industrial Informatics, vol.5, no 3, pp.351-365,Aug.2009.

   6. Joon-Woo Lee,Byoung-Suk Choi,Ju-Jang Lee, Energy efficient coverage of wireless sensor networks using ant colony optimization with three types of pheromones IEEE Trans. Industrial Informatics, vol.7, no 3, pp.419 – 427,Aug.2011.

   7. Xing G,Wang X,Zhang Y,Lu C,Pless R,and Gill C, Integrated coverage and connectivity configuration for energy conservation in sensor networks J.ACM Transactions, Sensor networks, vol.1, no 1, pp.36- 72,Aug.2005.

   8. Raghavendra Kulkarni V, Anna Forster ,Ganesh kumar Venayagamoorthy ,Computational intelligence in WSN : A Survey IEEE Communication Surveys & Tutorials, vol. 13, no. 1, pp. 68-96, first quarter 2011.

   9. M. C. Rodríguez-Sánchez, S. Borromeo, and J. A. Hernández-Tamames, Wireless sensor networks for conservation and monitoring cultural assets, IEEE Sensors J., vol. 11, no. 6, pp. 13821389, Jun. 2011.

   10. Joon-Woo Lee and Ju-Jang Lee , Ant-Colony Based Scheduling Algorithm for Energy-Efficient Coverage of WSN , IEEE Sensors J., vol. 12, 2012.

   11. Devi Dayal Vinayaki J , Ant Colony Based Sleep/ Wakeup Scheme with Added Heuristic Information(AC -SWSH) , IJERT., vol. 2, 2013.

   12. G. Simon, M. Maro´ti, A´ . Le´deczi, G. Balogh, B. Kusy, A. Na´das, G. Pap,J. Sallai, and K. Frampton, Sensor Network- Based Countersniper System,International Conference on Embedded Networked Sensor Systems, Nov. 2004, pp. 1-12.

   13. J. Yick, B. Mukherjee, and D. Ghosal, Analysis of a Prediction-based Mobility Adaptive Tracking Algorithm, IEEE International Conference on Broadband Networks, Vol. 1, Oct. 2005, pp. 753-760.

   14. H.-S. Ahn and K. H. Ko, Simple Pedestrian Localization Algorithm Based on Distributed Wireless Sensor Networks,

       IEEE Transactions on Industrial Electronics, Vol. 56, No. 10 Oct. 2009, pp. 4296-4302.

   15. L. Wang, G.-Z. Yang, J. Huang, J. Zhang, L. Yu, Z. Nie, and

2. R. S.Cumming, A Wireless Biomedical Signal Interface System-on-Chip for Body Sensor Networks, IEEE Transactions on Biomedical Circuits and Systems, Vol. 4, No. 2, Apr. 2010, pp. 112-117.

1. K. A. Agha, M.-H. Bertin, T. Dang, A. Guitton, P. Minet, T. Val, and J.-B. Viollet, Which Wireless Technology for Industrial Wireless Sensor Networks? The Development of OCARI Technology, IEEE Transactions on Industrial Electronics, Vol. 56, No. 10, Oct. 2009, pp. 4266-4278

2. D. Tian and N.D. Georganas, Connectivity maintenance and coverage preservation in wireless sensor networks, Journal Ad Hoc Networks, Vol. 3, No. 6, Nov. 2005, pp. 744-761.

3. G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless and C. Gill, Integrated coverage and connectivity configuration for energy conservation in sensor networks, Journal ACM Transactions on Sensor Networks, Vol. 1, No.1, Aug. 2005, pp. 36-72.