Grootschalige energie-efficiënte sensornetwerkroutering met behulp van een kwantumprocessoreenheid

Summary

Deze studie biedt een methode om een kwantumprocessoreenheid te gebruiken om de routes te berekenen voor verschillende verkeersdynamieken die werken om beter te presteren dan klassieke methoden in de literatuur om de levensduur van het netwerk te maximaliseren.

Abstract

De energiebehoudsmethode van het sensornetwerk, die een gebruikshybride is van een klassieke computer en een kwantumprocessor, heeft bewezen beter te presteren dan het heuristische algoritme met behulp van een klassieke computer. In dit manuscript wordt de technische context voor de betekenis van de methode gepresenteerd en gemotiveerd. Vervolgens worden de experimentele stappen gedemonstreerd in een operationele sequentie met illustraties indien nodig. De methode is gevalideerd door positieve resultaten in een willekeurig gegenereerde steekproefset van netwerktopologieën. De succesvolle experimentele resultaten van deze methode hebben een betere aanpak opgeleverd voor problemen met het maximaliseren van de levensduur van sensornetwerken en hebben aangetoond dat de huidige state-of-the-art kwantumprocessor in staat is geweest om grote praktische technische problemen op te lossen met verdiensten die de huidige methoden in de literatuur terzijde schuiven. Met andere woorden, kwantumvoordeel kan zo goed mogelijk worden benut. Het is verder gegaan dan het stadium van proof of concept naar proof of haalbaarheid.

Introduction

Energiebesparing in sensornetwerken is een zeer kritisch punt geweest in ontwerp¹. Klassieke methoden pakken het probleem normaal gesproken aan met behulp van een ad-hocbenadering 2,3,4,5,6. Dat gezegd hebbende, emuleren deze methoden de sensorknooppunten als individueel beheerde intelligente activa die ook kunnen samenwerken om zowel de belangen van het individu als de gemeenschap te dienen. Vanwege de vluchtige omgeving waarin sensoren werken, worden in sommige werken willekeurige algoritmen geïntroduceerd om de onzekerheden in de omgeving vast te leggen, terwijl in andere werken bio-intelligentie wordt geleend om heuristische algoritmen te bedenken die op gezond verstand aanvaardbare resultaten kunnen bereiken⁷. Om verder te illustreren: voor die willekeurige algoritmen zijn de omgevingsonzekerheden aan de ene kant misschien niet zo willekeurig als de willekeurige volgorde die wordt gegenereerd door een klassieke CPU, aan de andere kant, zelfs als de omgevingsonzekerheden absoluut willekeurig zijn, kunnen ze niet worden vastgelegd door de willekeurige processimulator die wordt gegenereerd door de klassieke CPU; Voor die bio-intelligentie-algoritmen is ten eerste geen rigoureuze wiskundige analyse afgeleid om een conceptueel bewijs te laten werken, ten tweede kan de convergentie naar waarheid of de fouttolerantiegrens alleen worden geconfigureerd op basis van een geïnformeerde grondwaarheid - hoewel een aanzienlijk aantal werken in de literatuur tot op zekere hoogte hebben aangetoond dat deze heuristische algoritmen werken, Ten eerste worden deze algoritmen geanalyseerd (niet gesimuleerd) aan de hand van goed gedefinieerde use case-scenario's, ze stoppen bij bepaalde criteria die nog steeds de moeite waard zijn om over na te denken in verder onderzoek, ten tweede, zoals eerder gezegd, is een meerderheid van de algoritmen niet gevalideerd tegen softwaresimulatie die gemakkelijker kan worden ingezet in de microprocessors die een sensor tot zijn wezen maken⁸.

We houden hier geen rekening met machine learning (ML) omdat het gebruik moet maken van data-analyse, wat een relatief grote hoeveelheid rekenkracht vereist die niet draagbaar is in sensorapparaten⁹.

Om de bovengenoemde zorgen weg te nemen, bieden we een hybride kwantumalgoritme. Het algoritme is hybride in die zin dat het selectiemechanisme voor clusterkoppen wordt geïmplementeerd met behulp van een klassiek willekeurig algoritme tijdens de routeringsberekeningen die worden uitgevoerd met behulp van een kwantumprocessor zodra de netwerktopologie is ingesteld. De methode wordt als volgt gemotiveerd: (1) Zoals besproken in de eerste paragraaf met betrekking tot de omgevingsonzekerheden, willen we niet verder proberen een kwantumsequentiegenerator toe te passen om de omgevingsdynamiek vast te leggen, omdat deze historisch traceerbaar zou kunnen zijn. De omgevingsdynamiek die historisch traceerbaar is, is gerechtvaardigd door verschillende machine learning-onderzoekswerken in netwerkwetenschap. Voor de huidige fase houden we vast aan de klassieke aanpak. (2) De exacte methode die berust op abstracte wiskundige analyse garandeert dat je tot de waarheid komt. De kwantumexperimentele fysica is tot nu toe geavanceerd ondersteund door de fysische wiskunde. Bovendien hebben er algoritmetoepassingen zoals het Shor-algoritme¹⁰ bestaan om deze afgeronde theorie te bewijzen.

Ter vergelijking wordt hieronder een voldoende hoeveelheid literatuuronderzoek gegeven. Het HEESR-protocol dat¹¹ voorstelt, heeft aantoonbare verdiensten in resultaten, maar de auteurs hebben de configuratieparameters van de simulatie goed gespecificeerd, bijvoorbeeld de exacte willekeurige verdelingsfunctie van de knooppuntpositie, de juiste rechtvaardiging van het clusterkoppercentage p (0,2%) en de schaalparameter voor de verdeling van het energieniveau (1-2 joule) tussen knooppunten a_i. Het verbood de auteur om verder te gaan met het dupliceren van de experimenten en het uitvoeren van de vergelijking. Het Power routing-mechanisme¹² maakt gebruik van de curve-aanpassingsmethode om geconvergeerde continue functies te benaderen op basis van discrete datasets die zijn verkregen uit niet-gespecificeerde steekproefruimte voor determinanten die van invloed zijn op het besluitvormingsproces van de optimale netwerkroutering. De curve-aanpassingsmethode¹³ vereist voorafgaande informatie over de netwerktopologie. Echte omstandigheden hebben misschien geen voorafgaande informatie direct beschikbaar. Zelfs als er eerdere informatie bestaat, is de netwerktopologie mogelijk niet regelmatig genoeg om te kunnen worden toegewezen aan passende curven die afgeleide berekeningen kunnen vergemakkelijken. Volgens dezelfde logica heeft DORAF-protocol¹⁴ niet gerechtvaardigd hoe en waarom de Boltzmann-functie en de logistieke functie moeten worden geleend om de netwerkdeterminanten te benaderen. Ismail et ^al.15 hebben een goede referentie geleverd voor toekomstig onderzoek naar het ontwerpen van energie-efficiënte routeringsprotocollen in het onderwaternetwerk.

Protocol

1. Dwave Ocean Environment opzetten

1. Download en installeer de oceaantools via de link: https://docs.ocean.dwavesys.com/en/stable/overview/install.html
   1. Typ python -m venv ocean bij de terminal.
   2. Typ bij de terminal . ocean/bin/activate, zoals weergegeven in afbeelding 1.
   3. Typ git clone https://github.com/dwavesystems/dwave-ocean-sdk.git in de terminal
      Typ vervolgens cd dwave-ocean-sdk, zoals weergegeven in afbeelding 2.
      Typ vervolgens python setup.py install

Figuur 1: Activering van de virtuele omgeving van de oceaan. Ocean-pakket, als D-wave API geïntegreerd, biedt een troebele gebruikerservaring via de eigen computer van de gebruiker naar het uitgangspunt van de D-wave-machine. Klik hier om een grotere versie van deze figuur te bekijken.

Afbeelding 2: Ocean SDK-installatie. Het Ocean-pakket biedt de nodige toolkits voor ontwikkelaars, waaronder een handige Cplex-installatie. Klik hier om een grotere versie van deze figuur te bekijken.

2. Installatie van Cplex Python API-interface

1. Download en installeer Cplex: https://pypi.org/project/cplex/
   1. Typ pip install cplex op de terminal.

3. Configuratieparameters voor experimenten

1. Stel de configuratieparameters van het experiment in die in tabel 1 worden vermeld met behulp van de Python-programmeernotatie in het script, zoals weergegeven in aanvullende afbeelding 1. Zodra het script is uitgevoerd en uitgevoerd, wordt de onderliggende taal verwerkt om de variabelen in het RAM-geheugen op te slaan. Een screenshot van de Python-codes waaraan respectievelijk waarden zijn toegewezen, is bijgevoegd (aanvullende figuur 1).

d0	87,7085 m boven zeeniveau
E	50 * 1 x 10-09 joule
epson_fs	1 * 10-12 * 10 joule
epson_mp	0,0013 * 1 * 10-12 joule
Grootte van het pakket	4000 beetjes

Tabel 1: Instellingen voor de parameter van het energiemodel en de pakketgrootte.

Aanvullende figuur 1: Script1. Script om de experimentparameters in te stellen. Klik hier om dit bestand te downloaden.

4. Python-scripts

1. Bereid de Python-scripts voor om 198 2D-posities van sensorknooppunten te genereren die gelijkmatig zijn verdeeld in zes sectoren die het cirkelvormige gebied met een straal van 50 m verdelen.
   OPMERKING: De cirkelvormige grafiek is gesegmenteerd in 6 sectoren. In elke sector wordt de positie van elk knooppunt behandeld met twee overeenkomstige variabelen. De ene is de hoek en de andere is de straal. Wijs waarden toe aan zowel hoek als straal met behulp van een uniforme willekeurige verdelingsgenerator. De gedetailleerde procedure is weergegeven in aanvullende figuur 2 en aanvullende figuur 3.
2. Zorg er binnen elke sector voor dat de 33 sensorknooppunten willekeurig worden verspreid door een normale verdeling. Sla de 2D-posities per sector op in tekstbestanden onder de naamspellingsregel 'posdata'+sector_no+'.txt' (Figuur 3 en Figuur 4).
   1. Segmenteer het cirkelvormige gebied met een straal van 50 m in zes sectoren. De beginhoekwaarden voor deze zes sectoren maken de vector A= [60,120,180,240,300,360].
      1. Stel dat de sectorindex i is, stel dan de poollengte voor j^de sensorknoop in op l_{i,j}=50*random.random()
      2. Stel dat de sectorindex i is, stel dan de hoekwaarde voor j^e sensorknooppunt in op ang_{i,j}=(60*willekeurig.willekeurig() + A_i - 60) * 2 * pi / 360
      3. Stel de cartesische coördinaten van het^j-de sensorknooppunt in de^i-de sector in als
         x_{i,j}=l_{i,j}*cos(ang_{i,j})
         y_{i,j}=l_{i,j}*sin(ang_{i,j})

Aanvullende figuur 2: Script2. Script om de twee dimensionale positielocaties voor elk knooppunt per sector te configureren. Klik hier om dit bestand te downloaden.

Aanvullende figuur 3: Script3. Script om de waarden van elke knooppuntpositie binnen 1 sector te configureren. Klik hier om dit bestand te downloaden.

Figuur 3: Knooppuntposities gegenereerd en opgeslagen, gescheiden in 6 bestanden die elk overeenkomen met één sector. Tweedimensionale positielocaties worden opgeslagen in 6 posdata+'idx'-bestanden. Elk presenteert een sector. Klik hier om een grotere versie van deze figuur te bekijken.

Figuur 4: Knooppuntposities opgeslagen in sector 0. De posities zijn in twee dimensies en worden gegenereerd met behulp van een uniforme toevalsgenerator. De eerste kolom zijn de horizontale locaties en de tweede kolom zijn de verticale locaties. Klik hier om een grotere versie van deze figuur te bekijken.

5. Voorbereiding van de initiële energieniveaus

1. Bereid de initiële energieniveaus voor alle 198 sensorknooppunten voor. Wijs de helft van hen toe met initiële energie van 0,5 J en de andere helft met initiële energie van 1 J. Maak een array om het energieniveau van elk knooppunt op te slaan en gebruik een lus om cellen toe te wijzen die in even getallen zijn gesequenced de waarde 1 en die in oneven getallen de waarde 0,5. Aanvullende figuur 4 toont de Python-codes en het resultaat wordt weergegeven in figuur 5.

Aanvullende afbeelding 4: Script4. Script om de helft van de energie van de knoop van 1 joule en de andere 0,5 joule toe te wijzen. Klik hier om dit bestand te downloaden.

Figuur 5: Energy_buffer eerste opdracht. De helft van de knooppunten krijgt energie van 1 joule, terwijl de andere helften 0,5 joule krijgen. Klik hier om een grotere versie van deze figuur te bekijken.

6. Opstellen van Advanced_Leach algoritmescript (Figuur 6 en Figuur 7)

1. Bereid een functioneel script voor waarin de clusterkop wordt geselecteerd en het cluster wordt gevormd.
   OPMERKING: Het cluster wordt geselecteerd met behulp van een lus op voorwaarde dat het aantal geselecteerde clusterkoppen kleiner is dan het totale aantal knooppunten gedeeld door 6. De voorwaarde is om ervoor te zorgen dat binnen elk cluster het aantal bronknooppunten gelijk is aan of kleiner is dan 6. Binnen de lus krijgt elke knoop een willekeurig getal toegewezen tussen [0,1]. Die kleiner dan een bepaald criteriumnummer worden het clusterhoofd, terwijl andere de bronknooppunten worden. De gedetailleerde procedure is weergegeven in aanvullende figuur 5. Op basis van een vaste pool van clusterhoofden selecteren de rest van de bronknooppunten hun clusterhoofden binnen de kortste afstand, aangezien het clusterhoofd nog niet meer dan 6 bronknooppunten heeft gehost. De gedetailleerde procedure is weergegeven in aanvullende figuur 6.
   1. Stel T_n=P/(1-P*(count%(1/P))), waarbij P = 0,2 (de proportionele snelheid van het aantal clusterhoofden ten opzichte van de totale netwerkgrootte) en het aantal is de hoeveelheid transmissie die tot nu toe wordt afgerond.
   2. Bereik voor elk sensorknooppunt een willekeurig getal tussen [0,1] threshold_rm = willekeurig.willekeurig()
      1. Als threshold_rm kleiner is dan T_n, selecteert u dit sensorknooppunt als clusterkop.
   3. Selecteer voor elk van de niet-cluster_head knooppunten het dichtstbijzijnde clusterkopsensorknooppunt als clusterkop. Gegeven een vaste pool van clusterhoofden, selecteren de rest van de bronknooppunten hun clusterhoofden binnen de kortste afstand, aangezien het clusterhoofd nog niet meer dan 6 bronknooppunten heeft gehost. De gedetailleerde procedure is weergegeven in aanvullende figuur 6.
2. Bereid de opdrachtregels voor om het energie-uitputtingsproces over het hele netwerk voor deze ronde te berekenen. Voor elke uitvoering van het algoritme dat een batch leveringen van de pakketten van bronknooppunten naar de gootsteen voltooit, wordt de energieopslagarray zoals voorbereid bijgewerkt om cel voor cel in waarden te worden verminderd. Het energieverbruik langs het pad is de som van het energieverbruik per knooppuntroute, die wordt berekend volgens een energiemodel¹. De gedetailleerde procedure is weergegeven in aanvullende figuur 7.
3. Bereken de vereiste metrische gegevens van de transmissieronde.
   OPMERKING: Per elke run van het algoritme om één batch pakketbezorging te voltooien, wordt de energiearray bijgewerkt, worden de runhoeveelheid en het aantal leeggelopen knooppunten geteld. Als de waarde groter is dan of gelijk is aan 1, dan is FND (first node die) gelijk aan de huidige run-hoeveelheid. Als de waarde groter is of gelijk is aan de helft van het aantal knooppunten, is HND (halve knooppuntdobbelsteen) gelijk aan het huidige uitvoeringsbedrag. Als de waarde gelijk is aan het totale aantal knooppunten, is AND (alle knooppuntdobbelstenen) gelijk aan het huidige uitvoeringsbedrag. De gedetailleerde procedure is weergegeven in aanvullende figuur 8.

Figuur 6: Cluster head array. De volgnummers van de knooppunten die zijn geselecteerd als clusterhoofden. Klik hier om een grotere versie van deze figuur te bekijken.

Figuur 7: Cluster head index array. Aangezien er zes sectoren zijn, elk met 33 sensorknooppunten, in de indexarray van de clusterkop, geeft het nummer het volgnummer aan van de clusterkop waartoe het bijbehorende sensorknooppunt behoort. De positie-index van de array komt overeen met het volgnummer van elk sensorknooppunt. Voor het sensorknooppunt dat is geselecteerd als clusterkop, is het nummer dat is toegewezen aan de sleuf in de array het volgnummer van zichzelf. Klik hier om een grotere versie van deze figuur te bekijken.

Aanvullende figuur 5: Script5. Script om de clusterkop te selecteren. Klik hier om dit bestand te downloaden.

Aanvullende figuur 6: Script6. Script om bronknooppunten toe te wijzen aan clusters. Klik hier om dit bestand te downloaden.

Aanvullende figuur 7: Script7. Script om de energiebuffer voor alle bronknooppunten bij te werken via vermindering van de hoeveelheid energie die wordt verbruikt door transmissie. Klik hier om dit bestand te downloaden.

Aanvullende figuur 8: Script8. Script om het aantal rondes te berekenen waarbij de eerste knoop sterft en de helft van de knooppunten sterft. Klik hier om dit bestand te downloaden.

7. Opstellen van een script voor hybride kwantumalgoritmes

1. Bereid een werkend script voor waarin de clusterkop wordt geselecteerd en de clusterkop wordt gevormd.
   1. Aangezien de maximale clustergrootte in dit experiment⁶ is, moet u ervoor zorgen dat het aantal clusterkoppen niet minder is dan current_valid_node_amount/6, de selectieprocedure zal in een lus worden uitgevoerd totdat aan dit criterium is voldaan.
      OPMERKING: Als current_valid_node_amount niet groter is dan 6, dan vormen deze geldige knooppunten zelf één en enige cluster.
   2. Bereken voor elk van de niet-cluster_head_valid knooppunten de afstand tot elk van de geselecteerde clusterkoppen en wijs er de clusterkop aan toe waarvan de clustergrootte niet groter is dan 6 waarbij de afstandswaarde het kleinst is.
      OPMERKING: In afbeelding 8 worden de afstanden van alle niet-cluster_head_valid knooppunten tot de geselecteerde clusterkop 24 berekend en worden alle geselecteerde clusterkoppen weergegeven in afbeelding 9. Figuur 10 toont alle knooppunten die zijn toegewezen aan hun corresponderende clusterkop, en Figuur 11 toont het groeperen van de lidknooppunten van elk cluster in een vectorarray.
2. Bereid het subfunctiescript voor, waarin het routeringsoptimalisatieprobleem per cluster wordt gevormd en ingediend bij de D-wave-API (Afbeelding 12). De routeringspaden worden cluster voor cluster berekend.
3. Bereken met behulp van het Python-script het energie-uitputtingsproces over het hele netwerk om het algoritme kwantitatief te evalueren op basis van de levensduur van het netwerk in termen van het aantal transmissierondes.
   OPMERKING: Voor elke uitvoering van het algoritme waarmee één batch leveringen van de pakketten van bronknooppunten naar de gootsteen wordt voltooid, wordt de energieopslagarray zoals voorbereid bijgewerkt om cel voor cel in waarden te worden verminderd. Het energieverbruik langs het pad is de som van het energieverbruik per knooppuntroute, berekend volgens een energiemodel¹. De gedetailleerde procedure is weergegeven in aanvullende figuur 7.
4. Leg met behulp van het Python-script het moment vast waarop de eerste node is leeggelopen en wanneer de helft van de nodes is leeggemaakt. De gedetailleerde procedure is weergegeven in aanvullende figuur 8.

Afbeelding 8: toClusterHeadDistance Array voor niet-cluster_head knooppunt met index 24. De eerste kolom is de afstand en de tweede kolom is het indexnummer van het clusterhoofd Klik hier om een grotere versie van deze figuur te bekijken.

Afbeelding 9: CHID_buff array. Volgnummers van de sensorknooppunten die zijn geselecteerd als clusterkoppen. Klik hier om een grotere versie van deze figuur te bekijken.

Figuur 10 CHIdx_buff array. Het volgnummer van de clusterkopsensorknooppunten is toegewezen aan elk corresponderend sensorknooppunt. Klik hier om een grotere versie van deze figuur te bekijken.

Afbeelding 11: CH_BUFF array. Clustergroep per clusterkop sensorknooppunten die overeenkomen met de array CHID_buff. Elke clustergroep bestaat uit 0 of meer dan 0 sensorknooppunten. Elke clustergroeparray geeft de volgnummers weer van sensorknooppunten die zich erin bevinden. Klik hier om een grotere versie van deze figuur te bekijken.

Figuur 12: Berekening van het routeringspad per sector. Voor elke sector worden de routeringspaden voor alle bronknooppunten berekend. Klik hier om een grotere versie van deze figuur te bekijken.

Results

De resultaten van één run-sample worden weergegeven in tabel 2, tabel 3 en tabel 4. De gedetailleerde datasets voor de drie gegevensbatches zijn beschikbaar in de map Aanvullende gegevens 1 .

Gegevensverzameling 1
198 knooppunten in een cirkelvormig gebied met een straal van 50m	Hybride ...

Discussion

De huidige state-of-the-art commerciële kwantumprocessor kan worden gebruikt bij rekenproblemen van elke netwerktopologie¹. De toepassing van kwantumprocessors wordt niet beperkt door het aantal fysieke qbits dat een van de kwantumprocessors heeft kunnen implementeren.

Bij het ontwerp van de verlenging van de levensduur van het sensornetwerk laten de resultaten een vooruitgang zien in de methode om een nog langere levensduur van het netwerk te bereiken door gebruik te ...

Materials

List of materials used in this article

Name	Company	Catalog Number	Comments
Dell Laptop	Dell	N/A
Ubuntu 18.04.6 LTS	Canonical Ltd	18.04.6 LTS
Python3.8	Python Software Foundation	3.8.0
Dwave QPU	Dwave	https://docs.ocean.dwavesys.com/en/stable/overview/install.html