A Discrete Imperialist Competitive Algorithm for WSN Deployment
About this article
Keywords:
Deployment, Evolutionary Algorithms, ICA, ICDA, WSN.Abstract
The WSN deployment problem is addressed in this paper. The problem applies to the monitored areas with different detection needs at different points. In this problem, every point of the terrain is assigned with a predefined minimum probability of event detection. The objective is providing the best position for the network nodes and at the same time assuring event detection, detection message delivery, and reducing deployment cost. We have formulated the problem as an optimization problem with three objectives, which is NP-complete. Because of the huge solution space for the problem and the exponential computational complexity, none of the exact methods known yet can solve the problem unless for a pretty small scaled case. To battle the complexity of the solution, a new scalable solution is proposed based on imperialist competitive algorithm namely imperialist competitive deployment algorithm (ICDA). We compare the proposal to the related deployment strategies, and the results show that ICDA outperforms them.
References
Al-Karaki, J.N., Kamal, A.E., “Routing techniques in wireless sen-sor networks: a survey”, Wireless Communications, IEEE, Vol. 11, No.6, (2004). doi:10.1109/MWC.2004.1368893
Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E., “Wire-less sensor networks: a survey”, Computer Networks, Vol. 38, No. 4, (2002). doi:http://dx.doi.org/10.1016/S1389-1286(01)00302-4
Atashpaz-Gargari, E., Lucas, C., “Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition”, IEEE Congress on Evolutionary Computation, (2007), pp: 4661-4667
Howard, A., Mataric, M., Sukhatme, G., “Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem”, Proceedings of the 6th International Symposium on Distributed Autonomous Robotics Systems (DARS02), (2002), pp: 299-308
Zou, Y., Krishnendu, C., “Sensor deployment and target localiza-tion based on virtual forces” Twenty-Second Annual Joint Confer-ence of the IEEE Computer and Communications. IEEE Socie-ties,(2003), pp: 1293-1303
View more references (12)
Wang, G., Cao, G., Porta, T.F.L. “Movement-Assisted Sensor De-ployment”, IEEE Transactions on Mobile Computing, Vol. 5, No. 6, (2006), doi:10.1109/TMC.2006.80
Wang, X., Wang, S., Ma, J.J., “An improved co-evolutionary parti-cle swarm optimization for wireless sensor networks with dynamic deployment”, Sensors, Vol. 7, No. 3, (2007), pp: 354-370
Dhillon, S.S., Chakrabarty, K., “Sensor placement for effective coverage and surveillance in distributed sensor networks”, Wireless Communications and Networking, Vol. 1603, (2003), pp: 1609-1614
Zou, Y., Chakrabarty, K., “Uncertainty-aware and coverage-oriented deployment for sensor networks”, Journal of Parallel and Distributed Computing, Vol. 64, No. 7, (2004), pp: 788-798
Jingbin, Z., Ting, Y., Son, S.H., “Deployment Strategies for Differ-entiated Detection in Wireless Sensor Networks”, Sensor and Ad Hoc Communications and Networks, (2006), pp: 316-325
Aitsaadi, N., Achirt, N., Boussetta, K., Pujolle, G. “A Tabu Search Approach for Differentiated Sensor Network Deployment” Con-sumer Communications and Networking Conference, (2008), pp: 163-167
Aitsaadi, N., Achir, N., Boussetta, K., Pujolle, G., “A tabu search wsn deployment method for monitoring geographically irregular distributed events”, Sensors, Vol. 9, No. 3, (2009), pp: 1625-1643
Aitsaadi, N., Achir, N., Boussetta, K., Pujolle, G., “Artificial poten-tial field approach in WSN deployment: Cost, QoM, connectivity, and lifetime constraints”, Computer Networks, Vol. 55, No. 1, (2011). doi:http://dx.doi.org/10.1016/j.comnet.2010.07.017
Tsai, Chun-Wei, et al., “Metaheuristics for the deployment problem of WSN: A review”, Microprocessors and Microsystems, Vol. 39, No. 8, (2015), pp: 1305-1317
Zou, Y., Chakrabarty, K., “Sensor deployment and target localiza-tion in distributed sensor networks”, ACM Trans. Embed. Comput. Syst., Vol. 3, No. 1, (2004). doi:10.1145/972627.972631
Zuniga, M., Krishnamachari, B., “Analyzing the transitional region in low power wireless links”, First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, (2004), pp: 517-526
Li, Y., Song, Y.-Q., Zhu, Y.-h., Schott, R., “Deploying wireless sensors for differentiated coverage and probabilistic connectivity”, Wireless Communications and Networking Conference, (2010), pp: 1-6