QoS-EQ-Routing: dynamisch ad hoc routing algoritme met machine learning
Beeld het je in: een stad getroffen door een tsunami. Mensen die gered moeten worden en nergens is nog een WiFi-verbinding of mobiel netwerk beschikbaar omdat de netwerkinfrastructuur beschadigd is. Om mensen te kunnen redden moeten reddingswerkers met elkaar in contact staan om hun inspanningen te kunnen coördineren. Hoe kan hiervoor gezorgd worden?
Ad hoc draadloze netwerken
De hierboven geschetste situatie is er een waarbij ad hoc draadloze netwerken een praktische oplossing kunnen bieden. Deze netwerken verschillen van WiFi-netwerken die men thuis gebruikt omdat ze werken zonder een vast access point. Een access point laat apparaten toe om verbinding met elkaar en met het internet te maken door te verbinden met het access point. Met deze verbinding is het dan mogelijk om o.a. te chatten, filmpjes te kijken of spelletjes te spelen.
Draadloze netwerken zonder zo’n access point noemen we ad hoc wireless networks of ad hoc draadloze netwerken. Deze netwerken zijn gemakkelijker op te zetten omdat ze geen access points vereisen, maar vragen wel meer rekenkracht en communicatie van de apparaten in het netwerk. De functies van het access point worden verdeeld onder de apparaten in het netwerk om zo onderlinge communicatie mogelijk te maken.
In ad hoc netwerken kan een apparaat netwerkverkeer sturen naar ieder apparaat dat bereikbaar is om zo uiteindelijk een bestemming te bereiken. Het is aan ieder apparaat om voor zichzelf uit te maken welke apparaten hulp kunnen bieden bij het bereiken van een bepaalde eindbestemming en welke apparaten dat niet kunnen.
Toepassingen
Gelukkig zijn tsunami’s een zelden voorkomend probleem, maar ook in gebieden getroffen door bosbranden of orkanen, oorlogsgebieden of in meer algemene situaties zoals een netwerk van sensoren of een IoT-netwerk ( = Internet of Things, waar ieder “ding” gegevens verzamelt en uitwisselt om de ervaring van de gebruiker te verrijken ) kunnen ad hoc draadloze netwerken worden gebruikt. Vanwege hun toepassingen in oorlogsgebieden is zelfs DARPA, de dienst defensie van de Amerikaanse overheid, geïnteresseerd in deze technologie.
Voor netwerken van sensoren en voor IoT-netwerken gaat het om veel apparaten die informatie met elkaar uitwisselen, al dan niet via het internet, waarbij er geen access points hiervoor voorzien kunnen worden. Het is niet praktisch om sensoren in een gebied ter grootte van de stad Antwerpen met elkaar te laten verbinden via een centrale antenne, maar door de sensoren te verbinden in een ad hoc draadloos netwerk kunnen ze probleemloos met elkaar communiceren.
Ad hoc routing algoritmes
Terug naar het tsunami-voorbeeld: stel je voor dat reddingswerkers proberen om met elkaar in contact te blijven via een ad hoc draadloos netwerk. Alle reddingswerkers moeten contact kunnen hebben met alle andere reddingswerkers en niet enkel met de reddingswerkers die dichtbij zijn. Het is daarom dat de keuze van naburig apparaat om een bestemming te bereiken niet zomaar kan vallen op het eerst beschikbare apparaat om mee te communiceren.
Om ad hoc netwerken bruikbaar te maken is er een nood aan algoritmes die met een kleine hoeveelheid energie en communicatie ervoor zorgen dat alle apparaten in het netwerk met elkaar kunnen communiceren. Routing is het nemen van beslissingen om die communicatie te verzorgen. Er zijn routing algoritmes die zorgen dat de communicatie in een ad hoc netwerk vlot verloopt maar met deze beschikbare algoritmes is er nog geen oplossing gevonden die in het algemeen werkt. Voor sensor netwerken is een algoritme nodig met een minimaal gebruik van energie, maar die algoritmes werken dan relatief traag. Trage communicatie is voor reddingswerkers geen optie, dus daar wordt een andere oplossing gebruikt.
De mogelijkheid om een algoritme te ontwerpen dat in ieder ad hoc netwerk in het algemeen gebruikt kan worden zonder voorgenoemde nadelen werd daarom onderzocht.
QoS-EQ-Routing
Het QoS-EQ-Routing algoritme is een algoritme dat tracht om met weinig uitwisseling van informatie alle apparaten steeds de optimale keuze te laten maken voor netwerkverkeer. Om dit te bereiken wordt gebruik gemaakt van C-MARL (Cooperative Multi-Agent Reinforcement Learning). Dit is een tak van de Artificiële Intelligentie waarbij een probleem wordt gemodelleerd als een spel met veel spelers die proberen om op basis van hun ervaringen een optimale manier te vinden om het spel te spelen, rekening houdend met hoe andere spelers het spel spelen.
Deze beschrijving werd toegepast op ad hoc draadloze netwerken. Alle apparaten in het netwerk worden gezien als spelers. Het doel van het spel voor iedere speler is om de optimale keuzes te maken bij het doorsturen van netwerkverkeer. Het uitwisselen van ervaringen en vervolgens daaruit nieuwe dingen leren is het belangrijkste onderdeel van het spel. De kwaliteit van het leren en de manier van uitwisselen van informatie bepaalt hoe goed of hoe slecht het algoritme werkt. QoS-EQ-Routing is in staat om met weinig uitwisseling van informatie toch de optimale keuzes te maken, ook onder variërende omstandigheden in het netwerk. Deze omstandigheden zijn bijvoorbeeld een apparaat dat uitvalt of storing in een bepaald gebied.
QoS-EQ-Routing kan ook omgaan met QoS (= Quality of Service, bepaalde eisen die aan verschillende soorten netwerkverkeer gesteld worden ). Het is deze toevoeging die het een vernieuwend algoritme maakt, geschikt om in het algemene geval ingezet te worden. Voor QoS zijn verschillende indelingen mogelijk, maar vaak worden drie categorieën gehanteerd; voice, video en web. Voice-verkeer wordt gebruikt om mensen met elkaar te laten praten over het netwerk en dit is de belangrijkste categorie. Video is de tweede belangrijkste en web is de derde en minst belangrijke categorie.
In het onderzoek is voor een testnetwerk aangetoond dat met QoS-EQ-routing netwerkverkeer steeds over het beste beschikbare pad gestuurd werd.
Conclusie
De resultaten uit het onderzoek geven aan dat QoS-EQ-Routing in het algemeen inzetbaar kan zijn, maar er moet in het achterhoofd gehouden worden dat experimenten verschillen van de realiteit. Op basis van experimenten kan men geen reddingswerkers of brandweermannen voorzien van ad hoc draadloze netwerkapparatuur die gebruik maakt van QoS-EQ-Routing. De toepasbaarheid van QoS-EQ-Routing zal verder worden onderzocht vooraleer het algoritme in reële situaties wordt toegepast.
Bibliografie
[1] Recommendation ITU-T G.1050: TRANSMISSION SYSTEMS AND MEDIA, DIGITAL SYSTEMS AND NETWORKS:Network model for evaluating multimedia transmission performance over Internet Protocol, July 2016.
[2] 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, 16(4):1996-2018, Fourthquarter 2014.
[3] M. Camelo, C. Lozano-Garzon, P. Vilà, and Y. Donoso. Green routing algorithm for wireless mesh network: A multi-objective evolutionary approach. In International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), 2013, pages 196-202. IEEE, 2013.
[4] M. Camelo, C. Oma~na, and H. Castro. Qos routing algorithms based on multi-objective optimization for mesh networks. IEEE Latin America Transactions, 9(5):875-881, 2011.
[5] A. Alharbi, A. Al-Dhalaan, and M. Al-Rodhaan. A mobile ad hoc network q-routing algorithm: Self-aware approach. International Journal of Computer Applications, 127(7):1-6, 2015.
[6] G. Di Caro, F. Ducatelle, and L. M. Gambardella. Anthocnet: an adaptive nature-inspired algorithm for routing in mobile ad hoc networks. Transactions on Emerging Telecommunications Technologies, 16(5):443-455, 2005.
[7] E. Gelenbe, Z. Xu, and E. Seref. Cognitive packet networks. In Tools with Artificial Intelligence, 1999. Proceedings. 11th IEEE International Conference on, pages 47{54. IEEE, 1999.
[8] G. He. Destination-sequenced distance vector (dsdv) protocol. Technical report, Helsinki University of Technology, Finland, Helsinki, Finland, 06 2002.
[9] T. Stützle. Ant colony optimization. In Ehrgott, M. and Fonseca, C. M. and Gandibleux, X. and Hao, J. and Sevaux, M., editor, Evolutionary Multi-Criterion Optimization, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
[10] J. A. Boyan and M. L. Littman. Packet routing in dynamically changing networks: A reinforcement learning approach. In J. Cowan, D. and Tesauro, G. and Alspector, J., editor, Advances in Neural Information Processing Systems 6 (NIPS), volume 6, pages 671-678. 1994.
[11] I. Woungang, S. K. Dhurandher, A. Anpalagan, and A. V. Vasilakos. Routing in Opportunistic Networks. Springer Publishing Company, Incorporated,2013.
[12] R. Sanchez-Iborra and M. D. Cano. Joker: A novel opportunistic routing protocol. IEEE Journal on Selected Areas in Communications, 34(5):1690-1703, May 2016.
[13] Samuel P. M. C. and Dit-Yan Y. Predictive q-routing: A memory-based reinforcement learning approach to adaptive traffic control. In In Advances in Neural Information Processing Systems 8 (NIPS8, pages 945-951. MIT Press, 1996.
[14] R. Sun, S. Tatsumi, and G. Zhao. Q-map: A novel multicast routing method in wireless ad hoc networks with multiagent reinforcement learning. In TENCON'02. Proceedings. 2002 IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering, volume 1, pages 667-670. IEEE, 2002.
[15] J. A. Boyan and M. L. Littman. A distributed reinforcement learning scheme for network routing. Technical Report CMU-CS-93-165, School of Computer Science, Carnegie Mellon University, 1993.
[16] L. P. Kaelbling, M. L. Littman, and A. W. Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237-285, 1996.
[17] Watkins, C. J. C. H. and Dayan, P. Q-learning. Machine Learning, 8(3):279-292, May 1992.
[18] T. Hu and Y. Fei. Qelar: A machine-learning-based adaptive routing protocol for energy-efficient and lifetime-extended underwater sensor networks. IEEE Transactions on Mobile Computing, 9(6):796-809, June 2010.
[19] S. B. Thrun. The role of exploration in learning control. Handbook of Intelligent Control: Neural, Fuzzy and Adaptive Approaches, pages 1-27, 1992.
[20] Ramroop, S and Adams, R. FINAL REPORT. B.Sc. (Engineering) , THE UNIVERSITY OF THE WEST INDIES, 2010.
[21] K. Nichols, S. Blake, F. Baker, and D. Black. Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers, RFC 2474, DOI 10.17487/RFC2474. https://www.rfc-editor.org/info/rfc2474, December 1998.
[22] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss. An Architecture for Di erentiated Services, RFC 2475, DOI 10.17487/RFC2475. https://www.rfc-editor.org/info/rfc2474, December 1998.
[23] H. Hassan, J. Garcia, and O Brun. Generic modeling of multimedia traffic sources. In 3rd International Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-Nets' 05), Ilkley (Great-Britain), 05 2005.
[24] Recommendation ITU-T G.711: GENERAL ASPECTS OF DIGITAL TRANSMISSION SYSTEMS - TERMINAL EQUIPMENTS:Pulse Code Modulation (PCM) of Voice Frequencies, July 2016.
[25] Ammar, D. and Begin, T. and Lassous, I. A new tool for generating realistic Internet traffic in NS-3. In Proc. of International ICST Conference on Simulation Tools and Techniques, pages 81-83. SIMUTools,03 2011.
[26] M. Zukerman, T. D. Neame, and R. G. Addie. Internet traffic modeling and future technology implications. In IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), volume 1, pages 587-596,March 2003.
[27] G. Ash, A. Morton, M. Dolly, P. Tarapore, C. Dvorak, and Y. El Mghazli. .1541-QOSM: Model for Networks Using Y.1541 Quality-of-
Service Classes", RFC 5976, DOI 10.17487/RFC5976. https://www.rfc-editor.org/info/rfc5976, October 2010.
[28] ITU-T Recommendation Y.1541, "Network Performance Objectives for P-Based Services", February 2006.
[29] C. E. Perkins and E. M. Royer. Ad-hoc on-demand distance vector routing. n Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA '99. Second IEEE Workshop on, pages 90{100, Feb 1999.
[30] A. Ahmed, A. Hanan, and I. Osman. AODV Routing Protocol Working Process. In Journal of Convergence Information Technology (JCIT), volume 10. March 2015.
[31] M. Abolhasan, T. Wysocki, and E. Dutkiewicz. A Review of Routing Protocols for Mobile Ad Hoc Networks. International Journal of Communications, Network and System Sciences, 2(3), June 2009.
[32] N. Srivastava, P Dubey, and N. Yadav. A comparative exploration and analysis of aodv, dsdv and dsr for manet. International Journal of Computer Science and Mobile Computing, 5(3):201{213, 3 2016.
[33] C. Perkins, E. Belding-Royer, and S. Das. Ad hoc On-Demand Distance Vector (AODV) Routing", RFC 3561, DOI 10.17487/RFC3561". https://www.rfc-editor.org/info/rfc3561, July 2003.
[34] Ling L., Lei Z., Long L., and Qihui W. Improvement of aodv routing protocol with qos support in wireless mesh networks. Physics Procedia, 25:1133 - 1140, 2012. International Conference on Solid State Devices and Materials Science, April 1-2, 2012, Macao.
[35] C. E. Perkins and E. M. Belding-Royer. Quality of service for ad hoc on-demand distance vector routing. Internet-Draft draft-perkins-manetaodvqos-00, IETF Secretariat, November 2001.
[36] C. E. Perkins and E. M. Belding-Royer. Quality of service for ad hoc on-demand distance vector routing (2). Internet-Draft draft-perkinsmanet-aodvqos-01, IETF Secretariat, October 2003.
[37] Y. Zhang and T. A. Gulliver. Quality of service for ad hoc on-demand distance vector routing. In Wireless And Mobile Computing, Networking
And Communications, 2005.(WiMob'2005), IEEE International Conference on, volume 3, pages 192-196. IEEE, 2005.
[38] C. E. Perkins and P. Bhagwat. Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers. In Proceedings of the conference on Communications architectures, protocols and applications, pages 234-244, September 1994.
[39] D. B. Johnson, D. A. Maltz, and J. Broch. DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks. In Ad Hoc Networking, chapter DSR: The Dynamic Source Routing Protocol for Multihop Wireless Ad Hoc Networks, pages 139-172. Addison-Wesley Longman Publishing Co., Inc., 2001.
[40] D. A. Maltz, J. Broch, and D. B. Johnson. Experiences Designing and Building a Multi-Hop Wireless Ad Hoc Network Testbed. Technical Report CMU-CS-99-116, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, March 1999.
[41] Freifunk Community. Better Approach To Mobile Ad hoc Networking (B.A.T.M.A.N.)., 2010.
[42] R. Sanchez-Iborra, M. D. Cano, and J. Garcia-Haro. Performance evaluation of batman routing protocol for voip services: A qoe perspective. IEEE Transactions on Wireless Communications, 13(9):4947-4958, Sept 2014.
[43] A. Neumann, C. Aichele, M. Lindner, and S. Wunderlich. Better approach to mobile ad-hoc networking (b.a.t.m.a.n.). Internet-Draft draftwunderlich-openmesh-manet-routing-00, IETF Secretariat, April 2008.
[44] D. Murray, M. Dixon, and T. Koziniec. An experimental comparison of routing protocols in multi hop ad hoc networks. In 2010 Australasian Telecommunication Networks and Applications Conference, pages 159-164, Oct 2010.
[45] E. Kaplan and C. Hegarty. Understanding GPS: principles and applications. Artech house, 2005.
[46] S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward. A distance routing effect algorithm for mobility (dream). In Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, MobiCom '98, pages 76{84, New York, NY, USA, 1998. ACM.
[47] R. L. Bagrodia and W. Liao. Maisie: a language for the design of efficient discrete-event simulations. IEEE Transactions on Software engineering, 20(4):225-238, Apr 1994.
[48] J. E. Wieselthier, C. M. Barnhart, and A. Ephremides. A neural network approach to routing without interference in multihop radio networks. IEEE Transactions on Communications, 42(1):166-177, Jan 1994.
[49] S. Pierre, H. Said, and W. G Probst. Routing in computer networks using artificial neural networks. Artificial Intelligence in Engineering, 14(4):295-305, 2000.
[50] N. Koji´c, I. Reljin, and B. Reljin. A neural networks-based hybrid routing protocol for wireless mesh networks. Sensors, 12(6), 2012.
[51] J. Barbancho, C. León, F. J. Molina, and A. Barbancho. A new qos routing algorithm based on self-organizing maps for wireless sensor networks. Telecommunication Systems, 36(1-3):73-83, 2007.
[52] R. Desai and B. P. Patil. Optimized reinforcement learning based adaptive network routing for manets. Global Journal of Pure and Applied Mathematics, 12(2):1413-1432, 2016.
[53] S. Kumar. Confidence based dual reinforcement q-routing: an on-line adaptive network routing algorithm. Master's thesis, 1998.
[54] S. Kumar and R. Miikkulainen. Dual reinforcement q-routing: An online adaptive routing algorithm. In Proceedings of the artificial neural networks in engineering Conference, pages 231-238, 1997.
[55] S Kumar and R Miikkualainen. Confidence-based q-routing: an onqueue adaptive routing algorithm. In Proceedings of Neural Networks in Engineering, 1998.
[56] C. Toh. A novel distributed routing protocol to support ad-hoc mobile computing. In Computers and Communications, 1996., Conference Proceedings of the 1996 IEEE Fifteenth Annual International Phoenix Conference on, pages 480-486. IEEE, 1996.
[57] A. Vijaya Kumar and A. Jeyapal. Self-adaptive trust based abr protocol for manets using q-learning. The Scientific World Journal, 2014.
[58] S. Dong, P. Agrawal, and K. Sivalingam. Reinforcement learning based geographic routing protocol for uwb wireless sensor network. In Global Telecommunications Conference, 2007. GLOBECOM'07. IEEE, pages 652-656. IEEE, 2007.
[59] M. Wunder, M. L. Littman, and M. Babes. Classes of multiagent qlearning dynamics with epsilon-greedy exploration. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 1167-1174, 2010.
[60] R. Arroyo-Valles, R. Alaiz-Rodriguez, A. Guerrero-Curieses, and J. CidSueiro. Q-probabilistic routing in wireless sensor networks. In Intelligent Sensors, Sensor Networks and Information, 2007. ISSNIP 2007. 3rd International Conference on, pages 1-6. IEEE, 2007.
[61] A. Al-Saadi, R. Setchi, Y. Hicks, and S. M. Allen. Routing protocol for heterogeneous wireless mesh networks. IEEE Transactions on Vehicular Technology, 65(12):9773-9786, 2016.
[62] E. L. Lawler, J. K. Lenstra, A.H.G. R. Kan, and D. B. et al. Shmoys. The traveling salesman problem: a guided tour of combinatorial optimization, volume 3. Wiley New York, 1985.
[63] L. M. Gambardella and M. Dorigo. Ant-q: A reinforcement learning approach to the traveling salesman problem. In Machine Learning Proceedings 1995, pages 252-260. 1995.
[64] G. A. Rummery and M. Niranjan. On-line Q-learning using connectionist systems, volume 37. University of Cambridge, Department of Engineering, 1994.
[65] T. Clausen (ed) and P. Jacquet (ed). Optimized Link State Routing Protocol (OLSR), RFC 3626, DOI 10.17487/RFC3626. https://www.rfc-editor.org/info/rfc3626, October 2003.
[66] T. Clausen (ed), C. Dearlove, P. Jacquet (ed), and U. Herberg. The Optimized Link State Routing Protocol Version 2", RFC 7181, DOI 10.17487/RFC7181. https://www.rfc-editor.org/info/rfc7181, April 2014.
[67] D. Johnson, Y. Hu, , and D. Maltz. The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4", RFC 4728, DOI 10.17487/RFC4728. https://www.rfc-editor.org/info/rfc4728, February 2007.
[68] S. V. Simpson and S. P. John. AODV: Security Consideration. In IJCA Proceedings on International Conference on Advanced Computing and Communication Techniques for High Performance Applications, volume 2, pages 5-12. Foundation of Computer Science (FCS), September 2015.
[69] D. Johnson, N. Ntlatlapa, and C. Aichele. Simple pragmatic approach to mesh routing using batman. In IFIP International Symposium on Wireless Communications and Information Technology in Developing Countries, number 2, Pretoria, South Africa, October 2008.
[70] S. Goss, S. Aron, J. Deneubourg, and J. Pasteels. Self-organized shortcuts in the argentine ant. Naturwissenschaften, 76(12):579-581, 1989.
[71] L. Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3-4):293-321, 1992.
[72] L. Lin. Reinforcement learning for robots using neural networks. Technical report, Carnegie-Mellon Univ Pittsburgh PA School of Computer Science, 1993.
[73] F. S. Melo. Convergence of q-learning: A simple proof. Institute Of Systems and Robotics, Tech. Rep, pages 1-4, 2001.
[74] O. Alagoz, H. Hsu, A. J. Schaefer, and M. S. Roberts. Markov decision processes: a tool for sequential decision making under uncertainty. Medical Decision Making, 30(4):474-483, 2010.
[75] R. C. Biradar and S. S. Manvi. Review of multicast routing mechanisms in mobile ad hoc networks. Journal of Network and Computer Applications, 35(1):221-239, 2012.
[76] B. Karp and H. Kung. Gpsr: Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th annual international conference on Mobile computing and networking, pages 243-254. ACM, 2000.
[77] W. C. Chung and D. Ha. An accurate ultra wideband (uwb) ranging for precision asset location. In Ultra Wideband Systems and Technologies, 2003 IEEE Conference on, pages 383-393. IEEE, 2003.
[78] G. F. Riley and T. R. Henderson. The ns-3 network simulator. In Modeling and tools for network simulation, pages 15-34. 2010.
