مسیریابی چندپخشی در شبکه‌های حسگر بی‌سیم مقیاس وسیع با استفاده از چارچوب یادگیری تقویتی توزیع شده
محورهای موضوعی : آمار
محمدصادق کردافشاری
1
,
علی موقر
2
,
محمدرضا میبدی
3
1 - دانشگاه آزاد اسلامی، واحد علوم و تحقیقات، گروه مهندسی کامپیوتر، تهران، ایران
2 - استاد گروه مهندسی کامپیوتر، دانشگاه صنعتی شریف، تهران، ایران
3 - استاد دانشکده کامپیوتر و فناوری اطلاعات، دانشگاه صنعتی امیرکبیر، تهران، ایران
کلید واژه: Q-Learning, lifeTime, Reliability, Topology-independent,
چکیده مقاله :
یکی از چالش‌های مطرح در شبکه‌های حسگر بی‌سیم، مساله‌ی پیدا کردن مسیر مناسب برای ارسال همزمان بسته‌ی داده به چندین مقصد مختلف یا مسیریابی چندپخشی است به طوریکه مصرف انرژی در کل شبکه توزیع شود و بسته‌های داده با قابلیت اطمینان بالایی به مقصدهای مورد نظر مسیریابی شوند. با توجه به مزیت‌های فراوان استفاده از الگوریتم‌های یادگیری تقویتی، در این مقاله یک روش توزیع‌شده، انعطاف‌پذیر و مستقل از توپولوژی شبکه با استفاده از الگوریتم یادگیریQ برای مسیریابی چندپخشی ارائه شده است. در این الگوریتم هر گره حسگر مجهز به یک الگوریتم یادگیر است که بر اساس اطلاعات محلی تصمیمات مسیریابی خود را اتخاذ می-نماید و بسته‌ها را به مجموعه‌ای از سینک‌های آدرس چندپخشی ارسال می‌کند. الگوریتم یادگیر تلاش می‌کند که مسیرها با قابلیت اطمینان بالا، انرژی بیشتر و تراکم گره‌های بالاتر را برای مسیریابی انتخاب نماید. این الگوریتم در شبکه‌هایی وسیع که گره‌های حسگر اطلاعات کمی از یکدیگر دارد قابل استفاده است. شبیه‌سازی‌های انجام شده، روش پیشنهادی را از لحاظ درصد موفقیت مسیریابی بسته‌های داده، طول عمر شبکه و میزان مصرف حافظه را در دو حالت تراکم گره‌های بالا و افزایش تعداد سینکها مورد ارزیابی قرار داده است. نتایج به دست آمده کارآمدی روش پیشنهادی، به ویژه در شبکه‌هایی با تراکم بالا و درجه چندپخشی بالا را نشان می‌دهد.
Wireless Sensor Networks (WSNs) are consist of independent distributed sensors with storing, processing, sensing and communication capabilities to monitor physical or environmental conditions. There are number of challenges in WSNs because of limitation of battery power, communications, computation and storage space. In the recent years, computational intelligence approaches such as evolutionary algorithms and swarm intelligence are applied successfully to solve many problems in WSNs. Most important of these problems are data aggregation, energy-aware routing, duty cycle scheduling, security and localization. These problem are in form of distributed so distributed approaches are required to solve them. Reinforcement learning is one of the most widely used and most effective methods of computational intelligence. In this paper, we used the reinforcement learning to solve multicast Quality of Service (QoS) routing. The simulation results showed that reinforcement learning is a suitable approach to solve this problem. The algorithm is implemented easy, it has the great flexibility in topology changes and it leads to optimized results. Distributed reinforcement learning provides compatibility mechanisms that show the intelligence behavior in complicate and dynamic environment such as WSNs. Using reinforcement learning, sensors behave autonomously, independently and flexibly during topology and scenario changes.
[1] Ilyas, M., & Mahgoub, I. ,Smart Dust: Sensor network applications, architecture and design. CRC press. 2016.
[2] J.M. Khan, R.H. Katz, and K.S.J. Pister, Next century challenges: mobile networking for Smart Dust, ACM/IEEE (MobiCom), Seattle, WA, USA, pp.271-278,1999.
[3] N. Carrerasa, D. Moureb, S. Gomáriza, D.Mihaia, A. Mànuela, R. Ortizc, Design of a smart and wireless seismometer for volcanology monitoring, Measurement, Vol. 97, pp. 174–185, 2017.
[4] K. Martinez, P. Padhy, A. Riddoch, R. Ong, and J. Hart, Glacial Environment Monitoring using Sensor Networks, in Proc. 1st Workshop on Real-World Wireless Sensor Networks (REALWSN), Stockholm, Sweden, 2005, p. 5pp.
[5] I. Talzi, A. Hasler, S. Gruber, and C. Tschudin, Permasense: investigating permafrost with a WSN in the swiss alps, in Proc. 4th Workshop on Embedded Networked Sensors (EmNets), Cork, Ireland, 2007, pp. 8–12.
[6]M. Ibrahim, M. Kassim, and A. Harun, Precision agriculture applications using wireless moisture sensor network. Communications (MICC), 2015 IEEE 12th Malaysia International Conference on. IEEE, 2015.
[7] A. Ahmed, KA. Bakar, MI. Channa, AW. Khan, K. Haseeb , Energy-aware and secure routing with trust for disaster response wireless sensor network, Peer-to-Peer Networking and Applications, vol. 10(1), 216-37, 2017.
[8] E. Cayirci and T. Coplu, , SENDROM: sensor networks for disaster relief operations management, Wireless Networks, vol. 13, no. 3, pp.409–423, 2007.
[9] I. Akyildiz, O.B. Akan Akan, C. Chen, J.Fang, and W.Su, Interplanetary internet: state of the art and research,” Computer Networks, 43(2):75-112, 2003
[10] E. A. Basha, S. Ravela, and D. Rus, Model-based monitoring for early warning flood detection, in Proc. conf. 6th ACM conf. on Embedded network sensor systems (SenSys), New York, NY, USA, 2008, pp.295–308.
[11] Jiang, D., Li, W., & Lv, H. . An energy-efficient cooperative multicast routing in multi-hop wireless networks for smart medical applications. Neurocomputing, 220, 160-169, 2017.
[12]Zeng, G., Wang, C., Xiao, L., Grid multicast: An energy-efficient multicast algorithm for wireless sensor networks, Proceedings of 4th International Conference on Networked Sensing Systems, pp. 267–274, 2007.
[13]Sanchez, J. A., Ruiz, P. M., Ivan S., GMR: Geographic multicast routing for wireless sensor networks, Sensor and Ad Hoc Communications and Networks (SECON), Reston, Virginia, USA, vol. 1, pp.20–29, 2006.
[14]Dimitrios, K., Saumitra, M. D., Charlie, H. Y., Ivan S., Hierarchical geographic multicast routing for wireless sensor networks, Springer Wireless Networks, vol. 16, pp. 449–466, 2010.
[15]G. Chalkiadakis, Multi-Agent Reinforcement Learning: Stochastic Games with Multiple Learning Players, Department of Computer Science, University of Toronto, 2003.
[16]K. S. Narendra, M. A. L. Thathacharو Learning automata: An introduction, Prentice Hall, 1989.
[17]Song, S., Choi, B., Kim, D., MR. BIN: Multicast routing with branch information nodes for wireless sensor networks, Proceedings of IEEE 19th International Conference on Computer Communications and Networks, pp. 1-6, 2010.
[18]Sanchez, J. A., Marin-Perez, R., Ruiz, P. M., Beacon-less geographic multicast routing in a real-world wireless sensor network testbed, Wireless Networks, Elsevier, vol. 18, no. 5, pp. 565-578, 2011.
[19]Marchiori, A., Han, Q. , PIM-WSN: Efficient multicast for IPv6 wireless sensor networks, IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), pp. 1-6, 2011.
[20]Hwang, S., Lu, K., Su, Y., Hsien, C., Dow, C., Hierarchical multicast in wireless sensor networks with mobile sinks, Wireless Communications and Mobile Computing, vol. 12, pp. 71-84, 2012.
[21]Su, L., Ding, B., Yang, Y., Abdelzaher, T. F., Cao G., Hou, J. C., (2009), oCast: Optimal multicast routing protocol for wireless sensor networks, 17th IEEE International Conference on Network Protocols, Princeton, pp. 151 – 160.
[22] K. S.Narendra and M. A. L.Thathachar, Learning automata: An introduction, Prentice Hall, 1989
[23] Verma K, Gupta M. A Comparitive Study On Location based Multicast Routing Protocols of WSN: HGMR, HRPM, GMR. Global Journal of Computer Science and Technology. 25,15(8), 2016.
[24]Jetcheva, J. G., Johnson, D. B., , Adaptive demand-driven multicast routing in multi-hop wireless Ad hoc networks, ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2001.
[25]Sheth, A., Shucker, B., Han, R., VLM2: A very lightweight mobile multicast system for wireless sensor networks, Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), pp. 1936-1941, 2003.
[26]Ball, M. G., Qela, B., & Wesolkowski, S. . A Review of the Use of Computational Intelligence in the Design of Military Surveillance Networks. In Recent Advances in Computational Intelligence in Defense and Security (pp. 663-693). Springer International Publishing,2016.
[27]Simek, M., Komosny, D., Burget R., Silva, J. S., Multicast routing in wireless sensor networks, International Conference on Telecommunications and Signal Processing, 2008.
[28] Förster, A., & Murphy, A. L. , Froms: A failure tolerant and mobility enabled multicast routing paradigm with reinforcement learning for WSNs. Ad Hoc Networks, 9(5), 940-965, 2011.
[29] S.Lakshmivarahan and M. A. L.Thathachar, Absolutely expedient learning algorithms for stochastic automata, IEEE Transactions on Systems, Man and Cybernetics, vol. 6, pp. 281-286, 1973.
[30] S.Lakshmivarahan and M. A. L.Thathachar, Optimal non-linear reinforcement schemes for stochastic automata, Information Science, vol. 4, pp. 121-128, 1982.
[31] R.Viswanathan and K. S.Narendra, Expedient and optimal variable structure stochastic automata, Technical report CT-31, Dunham Lab., Yale University, New Haven, Connecticut, U.S.A., April 1970.
[32] R.Viswanathan and K. S.Narendra, Stochastic automata models with applications to learning systems, IEEE Transactions on Systems, Man and Cybernetics, pp. 107-11, January 1973.
[33] M. A. Alsheikh, S. Lin, D. Niyato, and H. P. Tan, Machine learning in wireless sensor networks: Algorithms, strategies, and applications, IEEE Communications Surveys & Tutorials, vol. 16(4), 1996-2018, 2014.
[34] Ramli, A. F., Basarudin, Y. H., Sulaiman, M. I., Adam, F. I., and Grace, D, Cooperative and Reinforcement Learning in Energy Efficient Dual Hop Clustered Networks , Sindh University Research Journal-SURJ (Science Series), 48(4D), 2016.