Üç Boyutlu Ay Yüzeyine Kapsamayı Enbüyüklemek Üzere Melez Memetik Algoritma Kullanarak Kablosuz Algılayıcı Yerleştirilmesi

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.

Anahtar Kelimeler:

Yerel arama, memetik algoritma, ay, algılayıcı kapsaması, tavlama benzetimi, kablosuz algılayıcı yerleştirme

WIRELESS SENSOR DEPLOYMENT ON 3-D SURFACE OF MOON TO MAXIMIZE COVERAGE BY USING A HYBRID MEMETIC ALGORITHM

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.

Keywords:

Local search, memetic algorithm, moon, sensor coverage, simulated annealing, wireless sensor deployment,

PDF

___

1. Aarts, E., and Korst, J. (1989) Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, Wiley, New York.
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
16. Holland, J.H. (1975) Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.
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
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
19. Lopez-Matencio, P. (2016) An ACOR-based multi-objective WSN deployment example for lunar surveying, Sensors, 16(2), 209. doi:10.3390/s16020209
20. Map, https://www.mapaplanet.org/, Accessed on: Sep. 17, 2019.
21. MATLAB, ver. R2014a.
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.
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
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
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
26. NASA, Moon Missions, https://moon.nasa.gov/exploration/moon-missions/, Accessed on: Sep. 17, 2019.
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
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.
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
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
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
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
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
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
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
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
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
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.
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
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
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.
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.
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
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.
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
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
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
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
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
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
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
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
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