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.