Heuristic Search Algorithm (HSA) for Enhancing the Lifetime of Wireless Sensor Networks

The lifetime of a wireless sensor network can be effectively increased by using scheduling operations. Once the sensors are randomly deployed, the task at hand is to find the largest number of disjoint sets of sensors such that every sensor set provides complete coverage of the target area. At any instant, only one of these disjoint sets is switched on, while all other are switched off. This paper proposes a heuristic search method to find the maximum number of disjoint sets that completely cover the region. A population of randomly initialized members is made to explore the solution space. A set of heuristics has been applied to guide the members to a possible solution in their neighborhood. The heuristics escalate the convergence of the algorithm. The best solution explored by the population is recorded and is continuously updated. The proposed algorithm has been tested for applications which require sensing of multiple target points, referred to as point coverage applications. Results show that the proposed algorithm outclasses the existing algorithms. It always finds the optimum solution, and that too by making fewer number of fitness function evaluations than the existing approaches.

Authors:

• Tripatjot S. Panag
• J. S. Dhillon

Keywords:

• Coverage
• disjoint sets
• heuristic
• lifetime
• scheduling
• wireless sensor networks
• WSN.

References:

[1] Zheng, J., and Jamalipour, A. (2009). Wireless sensor networks – a
networking perspective. John Wiley & Sons, ISBN: 978-0-470-16763-2.
[2] Anastasi, G., Conti, M., Francesco, M. Di, and Passarella, A. (2009).
Energy conservation in wireless sensor networks: A survey. Ad Hoc
Networks, 7(3), 537-568.
[3] Younis, M., and Akkaya, K. (2008). Strategies and techniques for node
placement in wireless sensor networks: A survey. Ad Hoc Networks,
6(4), 621-655.
[4] Yick, J., Mukherjee, B., and Ghosal, D. (2008). Wireless sensor network
survey. Computer Networks, 52(12), 2292-2330.
[5] Akyildiz, I. F., Melodia, T., and Chowdhury, K. R. (2007). A survey on
wireless multimedia sensor networks. Computer Networks, 51(4), 921-
960.
[6] Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., and Cayirci, E. (2002).
A survey on sensor networks. IEEE Communications Magazine, 40(8),
102-114.
[7] Wand, X. and Wang, S. (2011). Hierarchical deployment optimization
for wireless sensor networks. IEEE Transactions on Mobile Computing,
10(7), 1028-1041.
[8] Lai, C.-C., Ting, C.-K., and Ko, R.-S. (2007). An effective genetic
algorithm to improve wireless sensor network lifetime for large-scale
surveillance applications. In proceedings of IEEE Congress on
Evolutionary Computation, pp. 3531-3538, September 25 – 28.
[9] Hu, X.-M., Zhang, J., Yu, Y., Chung, H. S.-H., Li, Y.-L., Shi, Y.-H., and
Luo, X.-N. (2010). Hybrid genetic algorithm using a forward encoding
scheme for lifetime maximization of wireless sensor networks. IEEE
Transactions on Evolutionary Computation, 14(5), 766-781.
[10] Cardei, M., and Du, D.-Z. (2005). Improving wireless sensor network
lifetime through power aware organization. Wireless Networks, 11(3),
333-340.
[11] Gaur, B., and Kumar, P. (2013). Wireless sensor deployment using
modified discrete binary PSO method. International Journal of
Innovative Research in Electrical, Electronics, Instrumentation and
Control Engineering, 1(3), 82-89.
[12] Lin, F. Y. S., and Chiu, P. L. (2005). A near-optimal sensor placement
algorithm to achieve complete coverage/discrimination in sensor
networks. IEEE Communications Letters, 9(1), 43-45.
[13] Huang, C.-F., and Tseng, Y.-C. (2005). The coverage problem in a
wireless sensor network. Mobile Networks and Applications, 10(4), 519-
528.
[14] Chakrabarty, K., Iyengar, S. S., Qi H., and Cho, E. (2002). Grid
coverage for surveillance and target location in distributed sensor
networks. IEEE Transactions on Computers, 51(12), 1448-1453.
[15] Dhillon, S. S., and Chakrabarty, K. (2003). Sensor placement for
effective coverage and surveillance in distributed sensor networks. In
proceedings of IEEE Wireless Communications and Networking
Conference, WCNC 2013, LA USA, vol. 3, pp. 1609-1614, March 20.
[16] Wang, Y.-C., Hu, C.-C., and Tseng, Y.-C. (2008). Efficient placement
and dispatch of sensors in a wireless sensor network. IEEE Transactions
on Mobile Computing, 7(2), 262-274.
[17] Khanjary, M., Sabaei, M., and Meybodi, M. R. (2014). Critical density
for coverage and connectivity in two-dimensional aligned-orientation
directional sensor networks using continuum percolation. IEEE Sensors
Journal, 14(8), 2856-2863.
[18] Howard, A., Matarić, M. J., and Sukhatme, G. S. (2002). An incremental
self deployment algorithm for mobile sensor networks. Autonomous
Robots, 13(2), 113-126.
[19] Heo, N., and Varshney, P. K. (2005). Energy-efficient deployment of
intelligent mobile sensor networks. IEEE Transactions on Systems, Man,
Cybernetics, Part A: Systems and Humans, 35(1), 78–92.
[20] Kulkarni, R.V., and Venayagamoorthy, G.K. (2010). Bio-inspired
algorithms for autonomous deployment and localization of sensor nodes.
IEEE Transactions on Systems, Man, and Cybernetics, Part C:
Applications and Reviews, 40(6), 663-675.
[21] Shwe, H. Y., Jiang, X.-H., and Horiguchi, S. (2009). Energy saving in
wireless sensor networks. Journal of Communication and Computer,
6(5), 20-28.
[22] Chang, C.-Y., and Chang, H.-R. (2008). Energy-aware node placement,
topology control and MAC scheduling for wireless sensor networks.
Computer Networks, 52(11), 2189-2204.
[23] Leung, H., Chandana, S., and Wei, S. (2008). Distributed sensing based
on intelligent sensor networks. IEEE Circuits and Systems Magazine,
8(2), 38-52.
[24] Iyengar, S. S., Wu, H.-C., Balakrishnan, N., and Chang, S. Y. (2007).
Biologically inspired cooperative routing for wireless mobile sensor
networks, IEEE Systems Journal, 1(1), 29-37.
[25] Cui, S., Madan, R., Goldsmith, A. J., and Lall, S. (2007). Cross-layer
energy and delay optimization in small-scale sensor networks. IEEE
Transactions on Wireless Communication, 6(10), 3688-3699.
[26] Yu, Y., Prasanna, V. K., and Krishnamachari, B. (2006). Energy
minimization for real-time data gathering in wireless sensor networks.
IEEE Transactions on Wireless Communication, 5(11), 3087-3096. [27] Cardei, M., and Wu, J. (2006). Energy-efficient coverage problems in
wireless ad-hoc sensor networks. Computer Communications, 29(4),
413-420.
[28] Cardei, M., and Wu, J. (2004). Coverage in wireless sensor networks.
Handbook of Sensor Networks: Compact Wireless and Wired Sensing
Systems, Ilyas M. and Mahgoub I., CRC Press (pp. 432-446), ISBN 0-
8493-1968-4.
[29] Baek, S. J., Veciana, G. de, and Su, X. (2004). Minimizing energy
consumption in large-scale sensor networks through distributed data
compression and hierarchical aggregation. IEEE Journal on Selected
Areas in Communication, 22(6), 1130-1140.
[30] Ahn, N., and Park, S. (2014). An optimization algorithm for minimum kconnected
m-dominating set problem in wireless sensor networks.
Wireless Networks, doi: 10.1007/s11276-014-0819-6.
[31] Slijepcevic, S., and Potkonjak, M. (2001). Power efficient organization
of wireless sensor networks. In proceedings of IEEE International
Conference on Communications, Helsinki, vol. 2, pp. 472-476.
[32] Schurgers, C., Tsiatsis, V., Ganeriwal, S., and Srivastava, M. (2002).
Optimizing sensor networks in the energy-latency-density design space.
IEEE Transactions on Mobile Computing, 1(1), 70-80.
[33] Raghunathan, V., Schurghers, C., Park, S., and Srivastava, M.B. (2002).
Energy-aware wireless microsensor networks. IEEE Signal Processing
Magazine, 19(2), 40-50.
[34] Lin, Y., Zhang, J., Chung, H.S.-H., Ip, W.H., Li, Y., and Shi, Y.-H.
(2012). An ant colony optimization approach for maximizing the
lifetime of heterogeneous wireless sensor networks. IEEE Transactions
on Systems, Man and Cybernetics, Part C: Applications and Reviews,
42(3), 408-420.
[35] Ashouri, M., Zali, Z., Mousvi, S.R., and Hashemi, M.R. (2012). New
optimal solution to disjoint set k-coverage for lifetime extension in
wireless sensor networks. IET Wireless Sensor Systems, 2(1), 31-39.
[36] Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., and Gill, C. (2003).
Integrated coverage and connectivity configuration in wireless sensor
networks. In proceedings of the First ACM Conference on Embedded
Networked Sensor Systems, SenSys’03, Los Angeles, USA, pp. 28-39,
November 5 – 7.
[37] Wang, L., and Xiao, Y. (2006). A survey of energy-efficient scheduling
mechanisms in sensor networks. Mobile Networks and Applications,
11(5), 723-740.
[38] Funke, S., Kesselman, A., Kuhn, F., Lotker, Z., and Segal, M. (2007).
Improved approximation algorithms for connected sensor cover.
Wireless Networks, 13(2), 153-164.
[39] Martins, F.V.C., Carrano, E.G., Wanner, E.F., Takahashi, R.H.C., and
Mateus, G.R. (2009). A dynamic multiobjective hybrid approach for
designing wireless sensor networks. In proceedings of IEEE Congress
on Evolutionary Computation, CEC’09, Trondheim, pp. 1145-1152,
May 18 - 21.
[40] Liu, C., Wu, K., Xiao, Y., and Sun, B. (2006). Random coverage with
guaranteed connectivity: Joint scheduling for wireless sensor networks.
IEEE Transactions on Parallel Distributed Systems, 17(6), 562-575.
[41] Lin, J.-W., and Chen, Y.-T. (2008). Improving the coverage of
randomized scheduling in wireless sensor networks. IEEE Transactions
on Wireless Communications, 7(12), 4807–4812.
[42] Abrams, Z., Goel, A., and Plotkin, S. (2004). Set k-cover algorithms for
energy efficient monitoring in wireless sensor networks. In proceedings
of 3rd International Symposium on Information Processing in Sensor
Networks, Berkley, USA, pp. 424–432, April.
[43] Berman, P., Calinescu, G., Shah, C., and Zelikovsky, A. (2005).
Efficient energy management in sensor networks. in Ad Hoc and Sensor
Networks, Wireless Networking and Mobile Computing, Edited by Pan
Y. and Xiao Y., Nova Science Publishers (pp 71–90), ISBN: 1-59454-
396-8.
[44] Cardei, M., MacCallum, D., Cheng, M. X., Min, M., Jia, X., Li, D., and
Du, D.-Z. (2002). Wireless sensor networks with energy efficient
organization. Journal of Interconnection Networks, 3(3–4), 213–229.
[45] Mohamadi, H., Salleh, S., Ismail, A. S., and Marouf S. (2014).
Scheduling algorithms for extending directional sensor network lifetime.
Wireless Networks, doi: 10.1007/s11276-014-0808-9.
[46] Benini, L., Castelli, G., Macii, A., Macii, E., Poncino, M., and Scarsi, R.
(2000). A discrete-time battery model for high-level power estimation.
In proceedings of Design, Automation and Test in Europe Conference
and Exhibition, Paris, pp 35-39.
[47] Lai, C.-C., Ting, C.-K., and Ko R.-S. (2007). An effective genetic
algorithm to improve wireless sensor network lifetime for large-scale
surveillance applications. In proceedings of IEEE Congress on
Evolutionary Computation, CEC 2007, Singapore, pp. 3531–3538
[48] Holland, J. H. (1975). Adaptation in Natural and Artificial Systems.
University of Michigan Press, Ann Arbor, MI.
[49] Michalewicz Z. (1996). Genetic Algorithm + Data Structures =
Evolution Programs. Springer-Verlag, Berlin, Germany.
[50] Brabazon A. and O’Neill M. (2008). An introduction to evolutionary
computation in finance. IEEE Computational Intelligence Magazine,
3(4), 42–55.
[51] Zhang 'J., Chung H. S.-H., and Lo W.-L. (2007). Clustering-based
adaptivecrossover and mutation probabilities for genetic algorithms.
IEEE Transactions on Evolutionary Computation, 11(3), 326–335.
[52] Zhang M., Gao X., and Lou W. (2007). A new crossover operator in
genetic programming for object classification. IEEE Transaction on
Systems, Man, Cybernetics, Part B: Cybernetics, 37(5), 1332–1343.
[53] Zhang J., Chung H. S.-H., Lo W.-L., Hui S. Y., and Wu A. K.-M.
(2001). Implementation of a decoupled optimization technique for
design of switching regulators using genetic algorithms. IEEE
Transactions on Power Electronics, 16(6), 752–763.