A Discrete Imperialist Competitive Algorithm for WSN Deployment

  • Authors

    • Kamal Jadidy Aval
    • Masumeh Damrudi
    2018-09-12
    https://doi.org/10.14419/ijet.v7i4.1.19481
  • 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

    1. [1] Al-Karaki, J.N., Kamal, A.E., “Routing techniques in wireless sensor networks: a surveyâ€, Wireless Communications, IEEE, Vol. 11, No.6, (2004). doi:10.1109/MWC.2004.1368893

      [2] Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E., “Wireless sensor networks: a surveyâ€, Computer Networks, Vol. 38, No. 4, (2002). doi:http://dx.doi.org/10.1016/S1389-1286(01)00302-4

      [3] 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

      [4] 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

      [5] Zou, Y., Krishnendu, C., “Sensor deployment and target localization based on virtual forces†Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies,(2003), pp: 1293-1303

      [6] Wang, G., Cao, G., Porta, T.F.L. “Movement-Assisted Sensor Deploymentâ€, IEEE Transactions on Mobile Computing, Vol. 5, No. 6, (2006), doi:10.1109/TMC.2006.80

      [7] Wang, X., Wang, S., Ma, J.J., “An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deploymentâ€, Sensors, Vol. 7, No. 3, (2007), pp: 354-370

      [8] 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

      [9] 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

      [10] Jingbin, Z., Ting, Y., Son, S.H., “Deployment Strategies for Differentiated Detection in Wireless Sensor Networksâ€, Sensor and Ad Hoc Communications and Networks, (2006), pp: 316-325

      [11] Aitsaadi, N., Achirt, N., Boussetta, K., Pujolle, G. “A Tabu Search Approach for Differentiated Sensor Network Deployment†Consumer Communications and Networking Conference, (2008), pp: 163-167

      [12] 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

      [13] Aitsaadi, N., Achir, N., Boussetta, K., Pujolle, G., “Artificial potential 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

      [14] 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

      [15] Zou, Y., Chakrabarty, K., “Sensor deployment and target localization in distributed sensor networksâ€, ACM Trans. Embed. Comput. Syst., Vol. 3, No. 1, (2004). doi:10.1145/972627.972631

      [16] 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

      [17] 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

  • Downloads

  • How to Cite

    Jadidy Aval, K., & Damrudi, M. (2018). A Discrete Imperialist Competitive Algorithm for WSN Deployment. International Journal of Engineering & Technology, 7(4.1), 4-8. https://doi.org/10.14419/ijet.v7i4.1.19481

    Received date: 2018-09-11

    Accepted date: 2018-09-11

    Published date: 2018-09-12