article

On a vector space representation in genetic algorithms for sensor scheduling in wireless sensor networks

Evolutionary Computation, Volume 22, Issue 3

Pages 361 - 403

https://doi.org/10.1162/EVCO_a_00112

Published: 01 September 2014 Publication History

Abstract

Recent works raised the hypothesis that the assignment of a geometry to the decision variable space of a combinatorial problem could be useful both for providing meaningful descriptions of the fitness landscape and for supporting the systematic construction of evolutionary operators (the geometric operators) that make a consistent usage of the space geometric properties in the search for problem optima. This paper introduces some new geometric operators that constitute the realization of searches along the combinatorial space versions of the geometric entities descent directions and subspaces. The new geometric operators are stated in the specific context of the wireless sensor network dynamic coverage and connectivity problem (WSN-DCCP). A genetic algorithm (GA) is developed for the WSN-DCCP using the proposed operators, being compared with a formulation based on integer linear programming (ILP) which is solved with exact methods. That ILP formulation adopts a proxy objective function based on the minimization of energy consumption in the network, in order to approximate the objective of network lifetime maximization, and a greedy approach for dealing with the system's dynamics. To the authors' knowledge, the proposed GA is the first algorithm to outperform the lifetime of networks as synthesized by the ILP formulation, also running in much smaller computational times for large instances.

References

[1]

Bertsekas, D. P. (1995). Dynamic programming and optimal control. Belmont, MA: Athena Scientific.

[2]

Cardei, M. and Wu, J. (2006). Energy-efficient coverage problems in wireless ad-hoc sensor networks. Computer Communications, 29:413-420.

[3]

Carrano, E. G., Takahashi, R. H. C., Fonseca, C. M., and Neto, O. M. (2010). Nonlinear network optimization: An embedding vector space approach. IEEE Transactions on Evolutionary Computation, 14(2): 206-226.

[4]

Cerpa, A., and Estrin, D. (2002). ASCENT: Adaptive self-configuring sensor networks topologies. In Proceedings of the International Conference of Computer Communications (INFOCOM'02), Vol. 3, pp. 1278-1287.

[5]

Conover, W. (1980). Practical nonparametric statistics, 2nd ed. New York: Wiley.

[6]

CPLEX, I. (2006). Ilog CPLEX source. Available at http://www.ilog.com/products/cplex/

[7]

Dunn, O. J. (1961). Multiple comparisons among means. Journal of American Statistical Association, 56:52-64.

[8]

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:766-781.

[9]

Jiang, H., Chen, L., Wu, J., Chen, S., and Leung, H. (2009). A reliable and high-bandwidth multihop wireless sensor network for mine tunnel monitoring. IEEE Sensors Journal, 9:1511-1517.

[10]

Leung, H., Chandana, S., and Wei, S. (2008). Distributed sensing based on intelligent sensor networks. IEEE Circuits and Systems Magazine, 8:38-52.

[11]

Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., and Anderson, J. (2002). Wireless sensor networks for habitat monitoring. In Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02), pp. 88-97.

[12]

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 the IEEE Congress on Evolutionary Computation.

[13]

Martins, F. V. C., Carrano, E. G., Wanner, E. F., Takahashi, R. H. C., and Mateus, G. R. (2010). An evolutionary dynamic approach for designing wireless sensor networks for real time monitoring. In Proceedings of the IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications.

[14]

Martins, F. V. C., Carrano, E. G., Wanner, E. F., Takahashi, R. H. C., and Mateus, G. R. (2011). A hybrid multiobjective evolutionary approach for improving the performance of wireless sensor networks. IEEE Sensors Journal, 11(3): 545-554.

[15]

Martins, F. V. C., Nakamura, F. G., Quintao, F. P., and Mateus, G. R. (2007). Model and algorithms for the density, coverage and connectivity control problem in flat WSNs. In Proceedings of the International Network Optimization Conference (INOC'07).

[16]

Mascarenas, D., Flynn, E., Farrar, C., Park, G., and Todd, M. (2009). Powering and interrogation of structural health monitoring sensor networks. IEEE Sensors Journal, 9:1719-1726.

[17]

Moraglio, A. (2007). Towards a geometric unification of evolutionary algorithms. PhD thesis, University of Essex, Essex, UK.

[18]

Moraglio, A., Kim, Y., Yoon, Y., and Moon, B. (2007). Geometric crossovers for multiway graph partitioning. Evolutionary Computation, 14:445-474.

[19]

Moraglio, A., and Poli, R. (2004). Topological implementation of crossover. In Proceedings of the Genetic and Evolutionary Computation Conference.

[20]

Nakamura, F. G. (2010). Algoritmos para controle de densidade em redes de sensores sem fio. PhD thesis, Universidade Federal de Minas Gerais. In Portuguese.

[21]

Nakamura, F. G., Quintao, F. P., Menezes, G. C., and Mateus, G. R. (2005). An optimal node scheduling for flat wireless sensor networks. In Proceedings of the IEEE International Conference on Networking (ICN'05), Vol. 3420, pp. 475-483.

[22]

Park, S., Savvides, A., and Srivastava, M. B. (2001). Simulating networks of wireless sensors. In Proceedings of the Conference on Winter Simulation (WSC'01), pp. 1330-1338.

[23]

Podpora, J., Reznik, L., and Von Pless, G. (2008). Intelligent real-time adaptation for power efficiency in sensor networks. IEEE Sensors Journal, 8:2066-2073.

[24]

Rajagopalan, R., Mohan, C., Varshney, P., and Mehrotra, K. (2005). Multi-objective mobile agent routing in wireless sensor networks. In Proceedings of the IEEE Congress on Evolutionary Computation.

[25]

Takahashi, R. H. C., Vasconcelos, J. A., Ramirez, J. A., and Krahenbuhl, L. (2003). A multiobjective methodology for evaluating genetic operators. IEEE Transactions on Magnetics, 3(39): 1321-1324.

[26]

Tilak, S., Abu-Ghazaleh, N. B., and Heinzelman, W. (2002). Infrastructure tradeoffs for sensor networks. In Proceedings of the ACM International Workshop on Wireless Sensor Networks and Application (WSNA'02), pp. 49-58.

[27]

Tsow, F., Forzani, E., Rai, A., Wang, R., Tsui, R., Mastroianni, S., Knobbe, C., Gandolfi, A. J., and Tao, N. J. (2009). A wearable and wireless sensor system for real-time monitoring of toxic environmental volatile organic compounds. IEEE Sensors Journal, 9:1734-1740.

[28]

Williams, R. (1979). The geometrical foundation of natural structure: A source book of design. New York: Dover.

[29]

XBOW. (2006). Mica2, Wireless measurement system. XBOW. Available at http://www.xbow.com/

[30]

Ye, F., Zhong, G., Cheng, J., Lu, S., and Zhang, L. (2003). PEAS: A robust energy conserving protocol for long-lived sensor networks. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS'03), pp. 28-37.

Cited By

Carrano ECampelo FTakahashi R(2021)Diversity-Driven Selection Operator for Combinatorial OptimizationEvolutionary Multi-Criterion Optimization10.1007/978-3-030-72062-9_15(178-190)Online publication date: 28-Mar-2021
https://dl.acm.org/doi/10.1007/978-3-030-72062-9_15
Dornas AMartins FSarubbi JWanner EBosman P(2017)Real-polarized genetic algorithm for the three-dimensional bin packing problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071327(785-792)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071327
Carrano Eda Silva GCardoso ETakahashi R(2016)Subpermutation-Based Evolutionary Multiobjective Algorithm for Load Restoration in Power Distribution NetworksIEEE Transactions on Evolutionary Computation10.1109/TEVC.2015.249736120:4(546-562)Online publication date: 28-Jul-2016
https://dl.acm.org/doi/10.1109/TEVC.2015.2497361

Index Terms

On a vector space representation in genetic algorithms for sensor scheduling in wireless sensor networks

Recommendations

Sensor scheduling for p-percent coverage in wireless sensor networks

We study sensor scheduling problems of p-percent coverage in this paper and propose two scheduling algorithms to prolong network lifetime due to the fact that for some applications full coverage is not necessary and different subareas of the monitored ...
The optimization of sensor relocation in wireless mobile sensor networks

Wireless Sensor Networks (WSNs) have been an active research area these years due to their broad range of potential applications. Several research issues, which include energy-aware routing, sensor deployment problems, data aggregation, etc., have been ...
Coverage and connectivity aware energy efficient scheduling in target based wireless sensor networks: an improved genetic algorithm based approach

Energy efficient scheduling of sensor nodes is one of the most efficient techniques to extend the lifetime of the wireless sensor networks (WSNs). Instead of activating all the deployed sensor nodes, a set of sensor nodes are activated or scheduled to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 22, Issue 3

Fall 2014

164 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 September 2014

Published in EVOL Volume 22, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Carrano ECampelo FTakahashi R(2021)Diversity-Driven Selection Operator for Combinatorial OptimizationEvolutionary Multi-Criterion Optimization10.1007/978-3-030-72062-9_15(178-190)Online publication date: 28-Mar-2021
https://dl.acm.org/doi/10.1007/978-3-030-72062-9_15
Dornas AMartins FSarubbi JWanner EBosman P(2017)Real-polarized genetic algorithm for the three-dimensional bin packing problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071327(785-792)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071327
Carrano Eda Silva GCardoso ETakahashi R(2016)Subpermutation-Based Evolutionary Multiobjective Algorithm for Load Restoration in Power Distribution NetworksIEEE Transactions on Evolutionary Computation10.1109/TEVC.2015.249736120:4(546-562)Online publication date: 28-Jul-2016
https://dl.acm.org/doi/10.1109/TEVC.2015.2497361

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents