TY  - JOUR
T1  - WIRELESS SENSOR DEPLOYMENT ON 3-D SURFACE OF MOON TO MAXIMIZE COVERAGE BY USING A HYBRID MEMETIC ALGORITHM
TT  - Üç Boyutlu Ay Yüzeyine Kapsamayı Enbüyüklemek Üzere Melez Memetik Algoritma Kullanarak Kablosuz Algılayıcı Yerleştirilmesi
AU  - Özkan, Ömer
PY  - 2020
DA  - April
Y2  - 2020
DO  - 10.17482/uumfd.632815
JF  - Uludağ Üniversitesi Mühendislik Fakültesi Dergisi
JO  - UUJFE
PB  - Bursa Uludağ University
WT  - DergiPark
SN  - 2148-4155
SP  - 303
EP  - 324
VL  - 25
IS  - 1
LA  - en
AB  - The moon has always been a goal for humanity in history to reach and discover. Since the 1950s, many missions have been carried out in order to achieve this goal. Wireless sensor networks can be a good tool for discovering some of the features of the moon and acquiring very important information for the missions to the moon and beyond to be performed soon. The deployed seismic, monitoring, light, temperature, pressure, etc. types of sensors on the surface of the Moon can collect vital data for the missions. Therefore, in this paper, the wireless sensor deployment problem on the surface of the Moon is studied to maximize coverage. Since the deployment of sensors on 3-D terrain is an NP-hard problem, a hybrid memetic algorithm is developed to solve. The real 3-D digital elevation model of the surface of the Moon for two different terrains near the South Pole is used to test the performance of the proposed algorithm with 64 scenarios and the results are compared with local search and simulated annealing algorithms. According to the results, the proposed hybrid memetic algorithm has better coverage values than the others in acceptable CPU times.
KW  - Local search
KW  - memetic algorithm
KW  - moon
KW  - sensor coverage
KW  - simulated annealing
KW  - wireless sensor deployment
N2  - Ay, tarihte insanlığın her zaman ulaşması ve keşfetmesi için bir amaç olmuştur. 1950'lerden bu yana, bu hedefe ulaşmak için birçok görev gerçekleştirilmiştir. Kablosuz algılayıcı ağlar, ayın bazı özelliklerini keşfetmek ve yakında gerçekleştirilecek olan ay ve ötesindeki görevler için çok önemli bilgiler edinmek için iyi bir araç olarak görünmektedir. Ay yüzeyine konuşlandırılabilecek sismik, izleme, ışık, sıcaklık, basınç vb. algılayıcı tipleri görevler için hayati veriler toplayabilecektir. Bu nedenle, bu çalışmada kapsamayı en üst düzeye çıkarmak için Ay yüzeyine kablosuz algılayıcı konuşlandırma problemi incelenmiştir. Algılayıcıların üç boyutlu arazide konuşlandırılması NP-zor bir problem olduğundan, çözmek için melez bir memetik algoritma geliştirilmiştir. Güney Kutbu yakınındaki iki farklı arazi için Ay yüzeyinin gerçek üç boyutlu dijital yükseklik modeli 64 senaryo ile önerilen algoritmanın performansını test etmek için kullanılmış ve sonuçlar yerel arama ve tavlama benzetimi algoritmaları ile karşılaştırılmıştır. Sonuçlara göre, önerilen melez memetik algoritma kabul edilebilir CPU zamanlarında diğerlerinden daha iyi kapsama değerlerine sahiptir.
CR  - 1. Aarts, E., and Korst, J. (1989) Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, Wiley, New York.
CR  - 2. Abdollahzadeh, S., and Navimipour, N.J. (2016) Deployment strategies in the wireless sensor network: a comprehensive review, Computer Communications, 91–92, 1–16. doi:10.1016/j.comcom.2016.06.003
CR  - 3. Akyildiz, I.F., Su., W., Sankarasubramaniam, Y., and Cayirci, E. (2002) Wireless sensor networks: a survey, Computer Networks, 38, 393-422. doi:10.1016/S1389-1286(01)00302-4
CR  - 4. Bresenham, J.E. (1965) Algorithm for computer control of a digital plotter, IBM Systems Journal, 4(1), 25-30. doi:10.1147/sj.41.0025
CR  - 5. Chakrabarty, K., Iyengar, S.S., Qi, H., and Cho, E. (2002) Grid coverage for surveillance and target location in distributed sensor networks, IEEE Transactions on Computers, 
51(12), 1448-1453. doi:10.1109/TC.2002.1146711
CR  - 6. Cheng, L., Wu, C., Zhang, Y., Wu, H., Li, M., and Maple, C. (2012) A survey of localization in wireless sensor network, International Journal of Distributed Sensor Networks, 8(12), id. 962523. doi:10.1155/2012/962523
CR  - 7. Deif, D.S., and Gadallah, Y. (2014) Classification of wireless sensor networks deployment techniques, IEEE Communications Surveys & Tutorials, 16(2), 834-855. doi:10.1109/SURV.2013.091213.00018
CR  - 8. Del Re, E., Pucci, R., and Ronga, L.S. (2009) IEEE802.15.4 wireless sensor network in mars exploration scenario, in Proc. International Workshop on Satellite and Space Communications (IWSSC), Sep. 09-11, Tuscany, Italy, 284-288. doi:10.1109/IWSSC.2009.5286366
CR  - 9. Dubois, P., Botteron, C., Mitev, V., Menon, C., Farine, P.-A., Dainesi, P., Ionescu, A., and Shea, H. (2009) Ad-hoc wireless sensor networks for exploration of solar-system bodies, Acta Astronautica, 64, 626–643. doi:10.1016/j.actaastro.2008.11.012
CR  - 10. Fan, G.J., and Jin, S.Y. (2010) Coverage problem in wireless sensor network: a survey, Journal of Networks, 5(9), 1033-1040. doi:10.4304/jnw.5.9.1033-1040
CR  - 11. Gaura, E., and Newman, R.M. (2006) Wireless sensor networks: the quest for planetary field sensing, in Proc. 31st IEEE Conference on Local Computer Networks, Nov. 14-16, Tampa, FL, USA, 596-603. doi:10.1109/LCN.2006.322021
CR  - 12. Ghosh, A., and Das, S.K. (2008) Coverage and connectivity issues in wireless sensor networks: a survey, Pervasive and Mobile Computing, 4, 303–334. doi:10.1016/j.pmcj.2008.02.001
CR  - 13. Guerriero, F., Violi, A., Natalizio, E., Loscri, V., and Costanzo, C. (2011) Modelling and solving optimal placement problems in wireless sensor networks, Applied Mathematical Modelling, 35, 230–241. doi:10.1016/j.apm.2010.05.020
CR  - 14. Guo, H., Ye, H., Liu, G., Dou, C., and Huang, J. (2020) Error analysis of exterior orientation elements on geolocation for a moon-based earth observation optical sensor, International Journal of Digital Earth, 13(3), 374-392. doi: 10.1080/17538947.2018.1513088
CR  - 15. Hamill, P. (2016) Atmospheric observations from the moon: A lunar earth-observatory, in Proc. IEEE International Geoscience and Remote Sensing Symposium (IGARSS), July 10-15, Beijing, China, 3719-3722.
CR  - 16. Holland, J.H. (1975) Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.
CR  - 17. Jia, Y., Zou, Y., Ping, J., Xue, C., Yan, J., and Ning, Y. (2018) The scientific objectives and payloads of Chang’E_4 mission, Planetary and Space Science, 162, 207–215. doi:10.1016/j.pss.2018.02.011
CR  - 18. Kulkarni, R.V., Förster, A., and Venayagamoorthy, G.K. (2011) Computational intelligence in wireless sensor networks: a survey, IEEE Communications Surveys & Tutorials, 13(1), 68-96. doi:10.1109/SURV.2011.040310.00002
CR  - 19. Lopez-Matencio, P. (2016) An ACOR-based multi-objective WSN deployment example for lunar surveying, Sensors, 16(2), 209. doi:10.3390/s16020209
CR  - 20. Map, https://www.mapaplanet.org/, Accessed on: Sep. 17, 2019.
CR  - 21. MATLAB, ver. R2014a.
CR  - 22. Medina, A., de Negueruela, C., Mollinedo, L., Gandía, F., Barrientos, A., Rossi, C., Sanz, D., Puiatti, A., and Dufour, J.F. (2010) Wireless sensor web for rover planetary exploration, in Proc. 10th International Symposium on Artificial Intelligence, Robotics and Automation in Space (iSAIRAS), Aug. 29-Sep.01, Sapporo, Japan, 531-537.
CR  - 23. Mini, S., Udgata, S.K., and Sabat, S.L. (2014) Sensor deployment and scheduling for target coverage problem in wireless sensor networks, IEEE Sensors Journal, 14(3), 636-644. doi:10.1109/JSEN.2013.2286332
CR  - 24. Molina, G., Alba, E., and Talbi, E.-G. (2008) Optimal sensor network layout using multi-objective metaheuristics, Journal of Universal Computer Science, 14(15), 2549-2565. doi:10.3217/jucs-014-15-2549
CR  - 25. Molina, G., and Alba, E. (2011) Location discovery in wireless sensor networks using metaheuristics, Applied Soft Computing, 11, 1223–1240. doi:10.1016/j.asoc.2010.02.021
CR  - 26. NASA, Moon Missions, https://moon.nasa.gov/exploration/moon-missions/, Accessed on: Sep. 17, 2019.
CR  - 27. Oddi, G., Pietrabissa, A., Liberati, F., Di Giorgio, A., Gambuti, R., Lanna, A., Suraci, V., and Priscoli, F.D. (2017) An any-sink energy-efficient routing protocol in multi-hop wireless sensor networks for planetary exploration, Int. J. Commun. Syst., 30(7), 1-25. doi:10.1002/dac.3020
CR  - 28. Pabari, J.P., Acharya, Y.B., and Desai, U.B. (2009) Investigation of wireless sensor deployment schemes for in-situ measurement of water ice near lunar south pole, Sensors & Transducers Journal, 111(12), 86-105.
CR  - 29. Pabari, J.P., Acharya, Y.B., Desai, U.B., Merchant, S.N., and Krishna, B.G. (2010) Radio frequency modelling for future wireless sensor network on surface of the moon, Int. J. Communications, Network and System Sciences, 3, 395-401. doi:10.4236/ijcns.2010.34050
CR  - 30. Pabari, J.P., Acharya, Y.B., Desai, U.B., and Merchant, S.N. (2012) Development of impedance-based miniaturized wireless water ice sensor for future planetary applications, IEEE Transactions on Instrumentation and Measurement, 61(2), 521-529. doi:10.1109/TIM.2011.2164292
CR  - 31. Pabari, J.P., Acharya, Y.B., Desai, U.B., and Merchant, S.N. (2013) Concept of wireless sensor network for future in-situ exploration of lunar ice using wireless impedance sensor, Advances in Space Research, 52, 321–331. doi:10.1016/j.asr.2012.09.006
CR  - 32. Parrado-Garcia, F.J., Vales-Alonso, J., and Alcaraz, J.J. (2017) Optimal planning of WSN deployments for in situ lunar surveys, IEEE Transactions on Aerospace and Electronic Systems, 53(4), 1866-1879. doi:10.1109/TAES.2017.2674258
CR  - 33. Prasad, K.D., and Murty, S.V.S. (2011) Wireless sensor networks – a potential tool to probe for water on moon, Advances in Space Research, 48, 601–612. doi:10.1016/j.asr.2011.04.004
CR  - 34. Prasad, K.D., Bhattacharya, A., and Murty, S.V.S. (2012) An ambient light sensing module for wireless sensor networks for planetary exploration, Planetary and Space Science, 70, 10–19. doi:10.1016/j.pss.2012.06.012
CR  - 35. Rodrigues, P., Oliveira, A., Alvarez, F., Cabas, R., Oddi, G., Liberati, F., Vladimirova, T., Zhai, X., Jing, H., and Crosnier, M. (2014) Space wireless sensor networks for planetary exploration: node and network architectures, in Proc. NASA/ESA Conference on Adaptive Hardware and Systems (AHS), July 14-17, Leicester, UK, 180-187. doi:10.1109/AHS.2014.6880175
CR  - 36. Sanz, D., Barrientos, A., Garzon, M., Rossi, C., Mura, M., Puccinelli, D., Puiatti, A., Graziano, M., Medina, A., Mollinedo, L., and de Negueruela, C. (2013) Wireless sensor networks for planetary exploration: experimental assessment of communication and deployment, Advances in Space Research, 52, 1029–1046. doi:10.1016/j.asr.2013.06.007
CR  - 37. Seok, J.-H., Lee, J.-Y., Kim, W., and Lee, J.-J. (2013) A bipopulation-based evolutionary algorithm for solving full area coverage problems, IEEE Sensors Journal, 13(12) 4796-4807. doi:10.1109/JSEN.2013.2274693
CR  - 38. Sun, R., Guo, J., and Gill, E.K.A. (2010) Opportunities and challenges of wireless sensor networks in space, in Proc. 61st International Astronautical Congress, Sep. 27 – Oct. 01, Prague, Czech Republic, 1-12.
CR  - 39. Tsai, C.-W., Tsai, P.-W., Pan, J.-S., and Chao, H.-C. (2015) Metaheuristics for the deployment problem of WSN: a review, Microprocessors and Microsystems, 39, 1305–1317. doi:10.1016/j.micpro.2015.07.003
CR  - 40. Türkoğulları, Y.B., Aras, N., Altınel, İ.K., and Ersoy, C. (2010) An efficient heuristic for placement, scheduling and routing in wireless sensor networks, Ad Hoc Networks, 8, 654–667. doi:10.1016/j.adhoc.2010.01.005
CR  - 41. Ulmer, C., Yalamanchili, S., and Alkalai, L. (2000) Wireless distributed sensor networks for in-situ exploration of mars, NASA Technical Report, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.116.324&rep=rep1&type=pdf, Accessed on: Sep. 17, 2019.
CR  - 42. Wang, H., Guo, Q., Li, A., Liu, G., Guo, H., and Huang, J. (2019) Impact of lunar terrain on moon-based earth observation, in Proc. IEEE International Geoscience and Remote Sensing Symposium (IGARSS), July 28-Aug. 02, Yokohama, Japan, 9260-9262.
CR  - 43. Wang, Q., and Liu, J. (2016) A Chang’e-4 mission concept and vision of future Chinese lunar exploration activities, Acta Astronautica, 127, 678–683. doi:10.1016/j.actaastro.2016.06.024
CR  - 44. Wilson, W.C., and Atkinson, G.M. (2011) Space applications for wireless sensors, in Proc. NSTI Nanotechnology Conference & Expo (Nanotech), June 13-16, Boston, MA, USA, 298-301.
CR  - 45. Wu, C.-H., Lee, K.-C., and Chung, Y.-C. (2006) A Delaunay triangulation based method for wireless sensor network deployment, in Proc. 12th International Conference on Parallel and Distributed Systems (ICPADS), July 12-15, Minneapolis, USA, 1-8. doi:10.1109/ICPADS.2006.11
CR  - 46. Ye, H., Guo, H., and Liu, G. (2017) Observation parameters design of moon-based earth observation sensors for monitoring three-polar regions, in Proc. IEEE International Geoscience and Remote Sensing Symposium (IGARSS), July 23-28, Fort Worth, Texas, USA, 5755-5758. doi:10.1109/IGARSS.2017.8128315
CR  - 47. Ye, H., Guo, H., Liu, G., and Ren, Y. (2018a) Observation scope and spatial coverage analysis for earth observation from a Moon-based platform, International Journal of Remote Sensing, 39(18), 5809-5833. doi:10.1080/01431161.2017.1395976
CR  - 48. Ye, H., Guo, H., Liu, G., and Ren, Y. (2018b) Observation duration analysis for Earth surface features from a Moon-based platform, Advances in Space Research, 62, 274-287. doi:10.1016/j.asr.2018.04.029
CR  - 49. Yick, J., Mukherjee, B., and Ghosal, D. (2008) Wireless sensor network survey, Computer Networks, 52, 2292-2330. doi:10.1016/j.comnet.2008.04.002
CR  - 50. Younis, M., and Akkaya, K. (2008) Strategies and techniques for node placement in wireless sensor networks: a survey, Ad Hoc Networks, 6, 621–655. doi:10.1016/j.adhoc.2007.05.003
CR  - 51. Zhai, X., and Vladimirova, T. (2015) Data aggregation in wireless sensor networks for lunar exploration, in Proc. Sixth International Conference on Emerging Security Technologies, Sep. 03-05, Braunschweig, Germany, 30-37. doi:10.1109/EST.2015.9
CR  - 52. Zhai, X., and Vladimirova, T. (2016) Efficient data-processing algorithms for wireless-sensor-networks-based planetary exploration, Journal of Aerospace Information Systems, 13(1), 46-66. doi:10.2514/1.I010373
CR  - 53. Zou, Y., and Chakrabarty, K. (2003) Sensor deployment and target localization based on virtual forces, in Proc. 22nd Annual Joint Conference of the IEEE Computer and Communication Societies (IEEE INFOCOM), Mar. 30 - Apr. 03, San Francisco, USA, 1293-1303. doi:10.1109/INFCOM.2003.1208965
UR  - https://doi.org/10.17482/uumfd.632815
L1  - https://dergipark.org.tr/en/download/article-file/1060250
ER  -