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

Authors: Tripatjot S. Panag, J. S. Dhillon

Abstract:

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.

Keywords: Coverage, disjoint sets, heuristic, lifetime, scheduling, wireless sensor networks, WSN.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1107892

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.