Weitere Artikel dieser Ausgabe durch Wischen aufrufen
An important challenge facing many large-scale surveillance applications is how to schedule sensors into disjoint subsets to maximize the coverage time span. Due to its NP-hard complexity, the problem of finding the largest number of disjoint set covers (DSC) of sensors has been addressed by many researchers. Majority of these studies employs the Boolean sensing model where a sensor covers a target if it lies within its sensing range. In reality, however, the sensing reliability may be affected by several parameters, e.g., strength of the generated signals, environmental conditions and the sensor’s hardware. To the best of our knowledge, improving coverage reliability of Wireless Sensor Networks (WSNs) has not been explored while solving DSC problem. This paper addresses the problem of improving coverage reliability of WSNs while simultaneously maximizing the number of DSC. Thus, in the context of WSNs design problem, our main contribution is to turn the definition of single-objective DSC problem into a multi-objective problem (MOP) by adopting an additional conflicting objective to be optimized. Specifically, we investigate the performance of two multi-objective evolutionary algorithms in terms of diversity and quality of the Pareto optimal set for the modeled MOP. The simulation results indicate that multi-objective approach results in achieving reliable coverage and large number of DSC compared to a single-objective approach.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability. A guide to the theory of NP-completeness. New York: Freeman. MATH
Slijepcevic, S., & Potkonjak, M. (2001). Power efficient organization of wireless sensor networks. In Proceedings of IEEE international conference communications, Vol. 2. Finland, pp. 472–476.
Cardei, M., Thai, M., Li, Y., & Wu, W. (2005). Energy-efficient target coverage in wireless sensor networks. In IEEE INFOCOM 2005, Mar. 2005, pp. 1976–1984.
Tian, D., & Georganas, N. D. (2002). A coverage-preserving node scheduling scheme for large wireless sensor networks. In Proceedings of 1st association computing machinery international workshop wireless sensor networks and applications, pp. 32–41.
Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., & Gill, C. (2003). Integrated coverage and connectivity configuration in wireless sensor networks. In Proceedings of 1st international conference on embedded network sensor systems, Los Angeles, CA, pp. 28–39.
Liu, Y., & Liang, W. (2005). Approximate coverage in wireless sensor networks. In Proceedings of IEEE conference on local computing network, 30th anniversary, pp. 68–75.
Gupta, H., Zhou, Z., Das, S. R., & Gu, Q. (2006). Connected sensor cover: Self-organization of sensor networks for efficient query execution. IEEE, Association for Computing Machinery Transactions on Networking, 14(1), 55–67. CrossRef
Funke, S., Kesselman, A., Kuhn, F., Lotker, Z., & Segal, M. (2007). Improved approximation algorithms for connected sensor cover. Wireless Networks, 13(2), 153–164. CrossRef
Zhou, Z., Das, S. R., & Gupta, H. (2009). Variable radii connected sensor cover in sensor networks. Association Computing Machinery Transactions on Sensor Networks, 5(1, article 8), 1–36.
Martins, F. V. C., Carrano, E. G., Wanner, E. F., Takahashi, R. H. C., & Mateus, G. R. (2009). A dynamic multiobjective hybrid approach for designing wireless sensor networks. In Proceedings on IEEE congress on evolutionary computation, pp. 1145–1152.
Cardei, M., & Du, D.-Z. (2005). Improving wireless sensor network lifetime through power aware organization. Wireless Netwoks, 11(3), 333–340. CrossRef
Cardei, I., & Cardei, M. (2008). Energy-efficient connected-coverage in wireless sensor networks. International Jounal on Sensor Networks, 3(3), 201–210.
He, J., Xiong, N., Xiao, Y., & Pan, Y. (2010). A reliable energy efficient algorithm for target coverage in wireless sensor networks. In IEEE 30th international conference on distributed computing systems workshops (ICDCSW), 2010, pp. 180–188.
Lai, C., Ting, C., & Ko, R. (2007). An effective genetic algorithm to improve wireless sensor network lifetime for large-scale surveillance applications. In IEEE congress on evolutionary computation, 2007. CEC 2007. IEEE, 2007.
Hu, X. M., Zhang, J., Yu, Y., Chung, H. H., Li, Y. L., Shi, Y. H., et al. (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. CrossRef
Gil, J. M., & Han, Y. H. (2011). A target coverage scheduling scheme based on genetic algorithms in directional sensor networks. Sensors 11, 11(2), 1888–1906. CrossRef
Elfes, A. (1987). Sonar-based real-world mapping and navigation. IEEE Journal of Robotics and Automation, RA–3(3), 249–265. CrossRef
Ghosh, A., & Das, S. K. (2006). Coverage and connectivity issues in wireless sensor networks. In Mobile, wireless, and sensor networks: Technology, applications, and future directions, pp. 221–256.
Hossain, A., Biswas, P. K., & Chakrabarti, S. (2008). Sensing models and its impact on network coverage in wireless sensor network. In IEEE region 10 and the third international conference on Industrial and information systems, 2008. ICIIS 2008, (pp. 1–5). IEEE.
Rajagopalan, R. (2010). A multi-objective optimization approach for data fusion in mobile agent based distributed sensor networks. In Instrumentation and measurement technology Conference (I2MTC), 2010 IEEE, pp. 208–212.
Rajagopalan, R., Mohan, C. K., Varshney, P., & Mehrotra, K. (2005). Multi-objective mobile agent routing in wireless sensor networks. In The 2005 IEEE congress on evolutionary computation, 2005, Vol. 2, pp. 1730–1737.
Özdemir, S., Attea, B. A., & Khalil, Ö. A. (2012). Multi-objective clustered-based routing with coverage control in wireless sensor networks. Soft computing, (pp. 1–12). Berlin: Springer. doi: 10.1007/s00500-012-0970-x.
Özdemir, S., Attea, B. A., & Khalil, Ö. A. (2012). Multi-objective evolutionary algorithm based on decomposition for energy eefficient coverage in wireless sensor networks. Wireless personal communications. Berlin: Springer. doi: 10.1007/s11277-012-0811-3.
Konstantinidis, A. (2009). Multiobjective deployment and power assignment in wireless sensor networks using metaheuristics. University of Essex.
Konstantinidis, A., Yang, K., Zhang, Q., & Zeinalipour-Yazti, D. (2009). A multi-objective evolutionary algorithm for the deployment and power assignment problem in wireless sensor networks. Computer Networks, 54(6), 960–976. CrossRef
Konstantinidis, A., & Yang, K. (2011). Multi-objective energy-efficient dense deployment in wireless sensor networks using a hybrid problem-specific MOEA/D. Applied Soft Computing, 11(6), 4117–4134. CrossRef
Abdulhalim, M. F., & Attea, B. A. (2014). Multi-layer genetic algorithm for maximum disjoint reliable set covers problem in wireless sensor networks. Accepted in Wireless Personal Communications. Berlin: Springer.
Srinivas, N., & Deb, K. (1994). Multi-objective function optimization using non-dominated sorting genetic algorithms. Evolutionary Computation, 2(3), 221–248. CrossRef
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2000). A fast and elitist multi-objective genetic algorithm: NSGA-II. In Proceedings parallel problem solving from nature VI, pp. 849–858.
Deb, K. (2001). Multi-objective optimization using evolutionary algorithms. Chichester: Wiley. MATH
Zhang, Q., & Li, H. (2007). MOEA/D: A multi-objective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712–731. CrossRef
Zitzler, E. (1999). Evolutionary algorithms for multi-objective optimization: Methods and applications. Doctoral dissertation, Zurich: Swiss Federal Institute of Technology.
- A Multi-objective Disjoint Set Covers for Reliable Lifetime Maximization of Wireless Sensor Networks
Bara’a A. Attea
Enan A. Khalil
- Springer US