Abstract
Wireless Sensor Networks are used in several practical applications such as environmental monitoring and risk detection. In this work, we deal with the problem of organizing the network topology into clusters in order to minimize the total energy consumption. The problem is modeled as an Independent Dominating Problem with Connecting requirements. We first present a state-of-the-art on the problems to optimize energy consumption in WSN. Then, we propose a mixed integer linear programming formulation, constructive heuristics, a local search procedure, and a GRASP-based metaheuristic. Results are provided for large scale WSN instances.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abbasi, A.A., Younis, M.: A survey on clustering algorithms for wireless sensor networks. Comput. Commun. 30, 2826–2841 (2007)
Aguiar, A., Pinheiro, P.R., Coelho, A.L.V., Nepomuceno, N., Neto, A., Cunha, R.P.P.: Scalability analysis of a novel integer programming model to deal with energy consumption in heterogeneous wireless sensor networks. Lect. Notes Comput. Sci. 14, 11–20 (2008)
Aioffi, W., Mateus, G.R., Quintão, F.P.: Optimization issues and algorithms for wireless sensor networks with mobile sink. In: Proceedings of International Network Optimization Conference (INOC), Spa, Belgium (2007)
Al-Karaki, J.N., Kamal, A.E.: Routing techniques in wireless sensor networks: a survey. IEEE Wirel. Commun. 11(6), 6–28 (2004)
Belisario, L.S., Guedes, L.S.M., Santos, A.C., Duhamel, C., Hou, K.-M.: Heuristiques pour la conception de rseaux wsn. In: Proceedings of 5th International Conference on Operations Research (CIRO), Marrakech, Maroc, pp. 91–92 (2010)
Cardei, M., Wu, J., Lu, M., Pervaiz, M.O.: Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In: Proceedings of IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Montreal, Canada, pp. 438–445 (2005)
Clark, B.N., Colbourn, C.J., Johnson, D.J.: Unit disk graphs. Discrete Math. 86, 165–177 (1991)
Dhawan, A., Vu, C.T., Zelikovsky, A., Li, Y., Prasad, S.K.: Maximum lifetime of sensor networks with adjustable sensing range. In: Proceedings of the International Workshop on Self-Assembling Wireless Networks (SAWN’06), Las Vegas, EUA (2006)
Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989)
Feo, T.A., Resende, M.G.C.: Greedy randomized adaptative search procedures. J. Glob. Optim. 6, 109–133 (1995)
Hajiaghayi, M.T., Immorlica, N., Mirrokni, V.S.: Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. IEEE/ACM Trans. Netw. 15, 1345–1358 (2007)
Hou, K.-M., Mailfert, J., Bendali, F., Duhamel, C., Santos, A.C.: An optimization approach for designing wireless sensor networks. In: The NTMS Workshop on Wireless Sensor Networks: Theory and Practice, Tanger, Maroc (2008). Page Eletronic diffusion
Hurinka, J.L., Niebergb, T.: Approximating minimum independent dominating sets in wireless networks. Inf. Process. Lett. 109, 155–160 (2008)
Jia, J., Chena, J., Changa, G., Wena, Y., Songa, J.: Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius. Comput. Math. Appl. 57(11–12), 1767–1775 (2009)
Li, X., Wang, P., Frieder, O.: Coverage in wireless ad hoc sensor networks. IEEE Trans. Comput. 52(6), 753–763 (2002)
Li, D., Wu, W., Du, D.-Z., Cheng, X., Huang, X.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42, 202–208 (2003)
Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. Trans. Model. Comput. Simul. 8(1), 3–30 (1998)
Meguerdichian, S., Potkonjak, M.: Low power 0/1 coverage and scheduling techniques in sensor networks. Technical Report 030001, University of California, Los Angeles (2003)
Moraes, R.E.N., Ribeiro, C.C., Duhamel, C.: Optimal solutions for fault-tolerant topology control in wireless ad hoc networks. In: IEEE Transactions on Wireless Communications, vol. 8, pp. 5970–5981 (2009)
Rossi, A., Singh, A., Sevaux, M.: A column generation scheme for a collection of sensor network scheduling problems. In: Proceedings of 11ème Congrés de la Société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF), Toulouse, France (2010)
Rossi, A., Sevaux, M., Singh, A., Geiger, M.J.: On the cover scheduling problem in wireless sensor networks. In: Proceedings of the 5th International Conference on Network Optimization (INOC), Hamburg, Germany, pp. 657–668 (2011a)
Rossi, A., Singh, A., Sevaux, M.: Column generation algorithm for sensor coverage scheduling under bandwidth constraints. Networks (2011b, to appear). doi:10.1002/net.20466
Santos, A.C., Bendali, F., Mailfert, J., Duhamel, C., Hou, K.-M.: Heuristics for designing energy-efficient wireless sensor network topologies. J. Netw. 4(6), 436–444 (2009)
Vlajic, N., Xia, D.: Wireless sensor networks: to cluster or not to cluster. In: Proceedings of the International Symposium on a World of Wireless, Mobile and Multimedia Networks, Buffalo, New York, pp. 258–268. IEEE Comput. Soc., Los Alamitos (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Santos, A.C., Duhamel, C., Belisário, L.S. et al. Strategies for designing energy-efficient clusters-based WSN topologies. J Heuristics 18, 657–675 (2012). https://doi.org/10.1007/s10732-012-9202-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-012-9202-x