Instradamento di rete di sensori ad alta efficienza energetica su larga scala utilizzando un'unità di processore quantistico

Riepilogo

Questo studio fornisce un metodo per utilizzare un'unità di processore quantistico per calcolare i percorsi per varie dinamiche di traffico che funzionano per superare i metodi classici in letteratura per massimizzare la durata della rete.

Abstract

Il metodo di conservazione dell'energia della rete di sensori, che è un ibrido di utilizzo di un computer classico e di un processore quantistico, ha dimostrato di funzionare meglio dell'algoritmo euristico che utilizza un computer classico. In questo manoscritto, il contesto tecnico per il significato del metodo è presentato e giustificato. Quindi le fasi sperimentali vengono dimostrate in una sequenza operativa con illustrazioni, se necessario. Il metodo è stato convalidato da risultati positivi in un set di campioni di topologie di rete generato in modo casuale. I risultati sperimentali positivi di questo metodo hanno fornito un approccio migliore per i problemi di massimizzazione della durata della rete di sensori e hanno dimostrato che l'attuale processore quantistico allo stato dell'arte è stato in grado di risolvere grandi problemi di ingegneria pratica con meriti che prevalgono sui metodi attuali in letteratura. In altre parole, il vantaggio quantistico può essere sfruttato al meglio. Si è passati dalla fase di prova di concetto alla prova di fattibilità.

Introduzione

Il risparmio energetico nelle reti di sensori è stato un problema molto critico nella progettazione¹. I metodi classici normalmente affrontano il problema utilizzando un approccio ad hoc 2,3,4,5,6. Detto questo, questi metodi emulano i nodi sensori come risorse intelligenti gestite individualmente che potrebbero anche cooperare per servire sia gli interessi dell'individuo che della comunità. A causa dell'ambiente volatile in cui lavorano i sensori, in alcuni lavori vengono introdotti algoritmi casuali al fine di catturare le incertezze ambientali, mentre in altri, la bio-intelligenza viene presa in prestito per ideare algoritmi euristici che potrebbero raggiungere risultati accettabili per il senso comune⁷. Per illustrare ulteriormente, per quegli algoritmi casuali, da un lato, le incertezze ambientali potrebbero non essere così casuali come la sequenza casuale generata da una CPU classica, dall'altro, anche se le incertezze ambientali sono assolutamente casuali, non potrebbero essere catturate dal simulatore di processo casuale generato dalla CPU classica; Per questi algoritmi di bio-intelligenza, prima di tutto, non è stata derivata alcuna analisi matematica rigorosa per far funzionare una dimostrazione concettuale, in secondo luogo, la convergenza alla verità o il limite di tolleranza all'errore possono essere configurati solo data una verità di base informata - anche se una quantità significativa di lavori in letteratura ha dimostrato in una certa misura che questi algoritmi euristici funzionano, Da un lato, questi algoritmi vengono analizzati (non simulati) rispetto a scenari di casi d'uso ben definiti, si fermano a determinati criteri su cui vale comunque la pena riflettere in ulteriori ricerche, dall'altro, come detto prima, la maggior parte degli algoritmi non è stata convalidata rispetto alla simulazione software che può essere più facilmente implementata nei microprocessori che rendono un sensore il suo essere⁸.

Non consideriamo l'apprendimento automatico (ML) perché deve impiegare l'analisi dei dati che richiede un volume relativamente grande di potenza di calcolo che non è portabile nei dispositivi sensore⁹.

Per risolvere i problemi di cui sopra, forniamo un algoritmo quantistico ibrido. L'algoritmo è ibrido in quanto il meccanismo di selezione della testa del cluster viene implementato utilizzando un algoritmo casuale classico durante i calcoli di routing condotti utilizzando un processore quantistico una volta configurata la topologia di rete. Il metodo è giustificato come segue: (1) Come discusso nel primo paragrafo riguardante le incertezze ambientali, non vogliamo tentare ulteriormente di applicare un generatore di sequenze quantistiche per catturare la dinamica ambientale perché potrebbe essere storicamente tracciabile. La dinamica ambientale che può essere storicamente tracciabile è stata giustificata da vari lavori di ricerca sull'apprendimento automatico nella scienza delle reti. Per la fase attuale, rimaniamo con l'approccio classico. (2) Il metodo esatto che si basa sull'analisi matematica astratta garantisce di arrivare alla verità di base. La fisica sperimentale quantistica è stata finora sofisticatamente supportata dalla matematica fisica. Inoltre, sono esistite applicazioni algoritmiche come l'algoritmo^{Shor 10} per dimostrare questa teoria arrotondata.

Di seguito viene fornita un'adeguata quantità di analisi della letteratura per il confronto. Il protocollo HEESR proposto¹¹ ha meriti dimostrabili nei risultati, ma gli autori hanno specificato bene i parametri di configurazione della simulazione, ad esempio, l'esatta funzione di distribuzione casuale della posizione del nodo, la corretta giustificazione della percentuale di carico del cluster p (0,2%) e il parametro di scala per la distribuzione del livello di energia (1-2 joule) tra i nodi a_i. Ha proibito all'autore di procedere ulteriormente per duplicare gli esperimenti e condurre il confronto. Il meccanismo di instradamento dell'alimentazione¹² impiega il metodo di adattamento della curva per approssimare le funzioni continue convergenti da set di dati discreti ottenuti da uno spazio campione non specificato per i determinanti che influiscono sul processo decisionale del routing di rete ottimale. Il metodo di adattamento^{della curva 13} richiede informazioni preliminari sulla topologia della rete. Le circostanze reali potrebbero non avere informazioni preliminari prontamente disponibili. Anche quando esistono informazioni preliminari, la topologia di rete potrebbe non essere abbastanza regolare da poter essere mappata su curve di fitting in grado di facilitare il calcolo derivabile. Seguendo la stessa logica, il protocollo DORAF¹⁴ non ha giustificato come e perché prendere in prestito la funzione di Boltzmann e la funzione logistica per approssimare i determinanti della rete. Ismail et ^al.15 hanno fornito un solido riferimento per i futuri sforzi di ricerca nella progettazione di protocolli di routing efficienti dal punto di vista energetico nella rete sottomarina.

Protocollo

1. Impostazione dell'ambiente oceanico Dwave

1. Scarica e installa gli strumenti oceanici dal link: https://docs.ocean.dwavesys.com/en/stable/overview/install.html
   1. Al terminale, digita python -m venv ocean.
   2. Al terminale, digitare . ocean/bin/activate, come mostrato nella Figura 1.
   3. Al terminale, digita git clone https://github.com/dwavesystems/dwave-ocean-sdk.git
      Digitare quindi cd dwave-ocean-sdk, come illustrato nella Figura 2.
      Quindi, digita python setup.py install

Figura 1: Attivazione dell'ambiente virtuale Ocean. Il pacchetto Ocean, come API D-wave integrata, fornisce un'esperienza utente nebulosa sul computer dell'utente alla premessa della macchina D-wave. Fare clic qui per visualizzare una versione più grande di questa figura.

Figura 2: Installazione di Ocean SDK. Il pacchetto Ocean fornisce i kit di strumenti necessari per gli sviluppatori, inclusa una pratica installazione di Cplex. Fare clic qui per visualizzare una versione più grande di questa figura.

2. Installazione dell'interfaccia API di Cplex Python

1. Scarica e installa Cplex: https://pypi.org/project/cplex/
   1. Al terminale, digita pip install cplex.

3. Parametri di configurazione dell'esperimento

1. Impostare i parametri di configurazione dell'esperimento menzionati nella Tabella 1 usando la notazione di programmazione Python nello script, come illustrato nella Figura 1 supplementare. Una volta che lo script è stato eseguito e eseguito, il linguaggio sottostante eseguirà l'elaborazione per memorizzare le variabili nella RAM. È allegata una schermata dei codici Python in cui ai parametri vengono assegnati rispettivamente i valori (Figura 1 supplementare).

d0	87.7085 m sopra il livello del mare
E	50 * 1 x 10-09 joule
epson_fs	1 * 10-12 * 10 joule
epson_mp	0,0013 * 1 * 10-12 joule
Dimensione del pacchetto	4000 bit

Tabella 1: Impostazioni dei parametri del modello energetico e delle dimensioni del pacchetto.

Figura supplementare 1: Script1. Script per impostare i parametri dell'esperimento. Fare clic qui per scaricare il file.

4. Script Python

1. Preparare gli script Python per generare 198 posizioni 2D dei nodi del sensore equamente distribuite in sei settori che dividono l'area circolare con un raggio di 50 m.
   NOTA: Il grafico circolare è segmentato in 6 settori. In ogni settore, la posizione di ogni nodo viene trattata con due variabili corrispondenti. Uno è l'angolo e l'altro è il raggio. Assegna valori sia all'angolo che al raggio utilizzando un generatore di distribuzione casuale uniforme. La procedura dettagliata è illustrata nella Figura 2 e nella Figura 3 supplementari.
2. All'interno di ogni settore, assicurarsi che i 33 nodi del sensore siano sparsi in modo casuale con una distribuzione normale. Salvare le posizioni 2D in file di testo per ogni settore sotto la regola ortografica del nome come 'posdata'+sector_no+'.txt' (Figura 3 e Figura 4).
   1. Segmentare l'area circolare con un raggio di 50 m in sei settori. I valori angolari iniziali per questi sei settori rendono il vettore A= [60,120,180,240,300,360].
      1. Supponiamo che l'indice del settore sia i, imposta la lunghezza del polo per il nodo del sensore^j-esimo come l_{i,j}=50*random.random()
      2. Supponiamo che l'indice del settore sia i, impostare il valore angolare per j^th nodo sensore come ang_{i,j}=(60*random.random() + A_i - 60) * 2 * pi / 360
      3. Impostare le coordinate cartesiane del nodo^j-esimo del sensore nel^1-esimo settore come
         x_{i,j}=l_{i,j}*cos(ang_{i,j})
         y_{i,j}=l_{i,j}*sin(ang_{i,j})

Figura 2 supplementare: Script2. Script per configurare le posizioni delle due quote per ogni nodo in base al settore. Fare clic qui per scaricare il file.

Figura supplementare 3: Script3. Script per configurare i valori di posizione di ogni nodo all'interno di 1 settore. Fare clic qui per scaricare il file.

Figura 3: Le posizioni dei nodi generate e memorizzate sono separate in 6 file, ciascuno corrispondente a un settore. Le posizioni bidimensionali vengono salvate in 6 file posdata+'idx'. Ognuno presenta un settore. Fare clic qui per visualizzare una versione più grande di questa figura.

Figura 4: Posizioni dei nodi memorizzate nel settore 0. Le posizioni sono in due dimensioni e generate utilizzando un generatore casuale uniforme. La prima colonna è costituita dalle posizioni orizzontali e la seconda colonna dalle posizioni verticali. Fare clic qui per visualizzare una versione più grande di questa figura.

5. Preparazione dei livelli di energia iniziali

1. Preparare i livelli di energia iniziali per tutti i 198 nodi del sensore. Assegna metà di essi con energia iniziale a 0,5 J e l'altra metà con energia iniziale a 1 J. Crea un array per memorizzare il livello di energia di ciascun nodo e usa un ciclo per assegnare alle celle sequenziate in numeri pari il valore 1 e a quelle sequenziate in numeri dispari il valore di 0,5. La Figura 4 supplementare mostra i codici Python e il risultato è illustrato nella Figura 5.

Figura supplementare 4: Script4. Script per assegnare metà dell'energia del nodo di 1 joule e l'altra di 0,5 joule. Fare clic qui per scaricare il file.

Figura 5: Energy_buffer assegnazione iniziale. A metà dei nodi viene assegnata un'energia di 1 joule, mentre alle altre metà viene assegnata un'energia di 0,5 joule. Fare clic qui per visualizzare una versione più grande di questa figura.

6. Preparazione Advanced_Leach script dell'algoritmo (Figura 6 e Figura 7)

1. Preparare uno script funzionale in cui viene selezionata la testa del cluster e viene formato il cluster.
   NOTA: il cluster viene selezionato utilizzando un ciclo a condizione che il numero di teste del cluster selezionate sia inferiore al numero complessivo di nodi diviso per 6. La condizione consiste nel garantire che all'interno di ogni cluster la quantità di nodi di origine sia uguale o inferiore a 6. All'interno del ciclo, a ogni nodo viene assegnato un numero casuale compreso tra [0,1]. Quelli più piccoli di un determinato numero di criteri diventano l'intestazione del cluster, mentre gli altri diventano i nodi di origine. La procedura dettagliata è illustrata nella figura 5 supplementare. Quindi, dato un pool fisso di head di cluster, il resto dei nodi di origine seleziona le proprie head di cluster entro la distanza più breve, dato che l'head di cluster non ha ancora ospitato più di 6 nodi di origine. La procedura dettagliata è illustrata nella figura 6 supplementare.
   1. Impostare T_n=P/(1-P*(count%(1/P))), dove P = 0,2 (la velocità proporzionale del numero di head cluster rispetto alle dimensioni complessive della rete) e count è la quantità di trasmissione arrotondata fino ad oggi.
   2. Per ogni nodo del sensore, ottenere un numero casuale compreso tra [0,1] threshold_rm = random.random()
      1. Se threshold_rm è inferiore a T_n, selezionare questo nodo sensore come testa del cluster.
   3. Per ognuno dei nodi non cluster_head, selezionare il nodo sensore dell'head del cluster più vicino come head del cluster. Dato un pool fisso di head di cluster, il resto dei nodi di origine seleziona i propri head di cluster entro la distanza più breve, dato che l'head di cluster non ha ancora ospitato più di 6 nodi di origine. La procedura dettagliata è illustrata nella figura 6 supplementare.
2. Preparare le righe di comando per calcolare il processo di esaurimento dell'energia nell'intera rete per questo round. Per ogni esecuzione dell'algoritmo che completa un batch di consegne dei pacchetti dai nodi di origine al sink, l'array di accumulo di energia preparato verrà aggiornato in modo da avere valori ridotti cella per cella. Il consumo di energia lungo il percorso sarà la somma del consumo di energia per percorso da nodo a nodo, calcolato in base a un modello energetico¹. La procedura dettagliata è illustrata nella figura 7 supplementare.
3. Calcolare le metriche del ciclo di trasmissione richieste.
   NOTA: per ogni esecuzione dell'algoritmo per completare un batch di consegna dei pacchetti, l'array di energia viene aggiornato, vengono conteggiati la quantità di esecuzione e il numero di nodi esauriti. Se il valore è maggiore o uguale a 1, FND (primo dado del nodo) è uguale alla quantità di esecuzione corrente. Se il valore è maggiore o uguale alla metà della quantità del nodo, HND (half node die) è uguale alla quantità di esecuzione corrente. Se il valore è uguale alla quantità complessiva del nodo, AND(all node die) è uguale alla quantità di esecuzione corrente. La procedura dettagliata è illustrata nella figura 8 supplementare.

Figura 6: Matrice head del cluster. I numeri di sequenza dei nodi che sono stati selezionati come teste del cluster. Fare clic qui per visualizzare una versione più grande di questa figura.

Figura 7: Matrice dell'indice head del cluster. Poiché nell'array dell'indice della testa del cluster sono presenti sei settori, ciascuno con 33 nodi sensore, il numero indica il numero di sequenza della testa del cluster a cui appartiene il nodo sensore corrispondente. L'indice di posizione dell'array corrisponde al numero di sequenza di ciascun nodo del sensore. Per il nodo sensore selezionato come testa del cluster, il numero assegnato al relativo slot nell'array è il numero di sequenza stesso. Fare clic qui per visualizzare una versione più grande di questa figura.

Figura supplementare 5: Script5. Script per selezionare l'intestazione del cluster. Fare clic qui per scaricare il file.

Figura supplementare 6: Script6. Script per assegnare i nodi di origine ai cluster. Fare clic qui per scaricare il file.

Figura supplementare 7: Script7. Script per aggiornare il buffer di energia per tutti i nodi di origine tramite la riduzione della quantità di energia consumata durante la trasmissione. Fare clic qui per scaricare il file.

Figura supplementare 8: Script8. Script per calcolare la quantità di arrotondamenti fino a cui il primo nodo muore e metà dei nodi muore. Fare clic qui per scaricare il file.

7. Preparazione di uno script di algoritmi quantistici ibridi

1. Preparare uno script funzionante in cui viene selezionata la testa del cluster e viene formata la testa del cluster.
   1. Poiché la dimensione massima del cluster è 6 in questo esperimento¹, assicurarsi che la quantità di teste del cluster non sia inferiore a current_valid_node_amount/6, la procedura di selezione verrà eseguita in un ciclo fino a quando questo criterio non viene soddisfatto.
      NOTA: se current_valid_node_amount non è maggiore di 6, questi nodi validi formano un unico cluster.
   2. Per ciascuno dei nodi non cluster_head_valid, calcolare la distanza da ciascuna delle teste del cluster selezionate e assegnarle l'intestazione del cluster la cui dimensione del cluster non ha superato 6 dove il valore della distanza è il più piccolo.
      NOTA: Nella Figura 8 vengono calcolate tutte le distanze dei nodi non cluster_head_valid dall'head del cluster selezionato 24 e nella Figura 9 viene visualizzata tutta la head del cluster selezionata. Nella Figura 10 vengono visualizzati tutti i nodi assegnati all'intestazione del cluster corrispondente, mentre nella Figura 11 viene illustrato il raggruppamento dei nodi membri di ciascun cluster in una matrice vettoriale.
2. Preparare lo script della sottofunzione, in cui viene formato il problema di ottimizzazione del routing per cluster e inviato all'API D-wave (Figura 12). I percorsi di routing vengono calcolati cluster per cluster.
3. Utilizzando lo script Python, calcola il processo di esaurimento dell'energia attraverso l'intera rete per valutare quantitativamente l'algoritmo in base alla durata della rete in termini di numero di cicli di trasmissione.
   NOTA: per ogni esecuzione dell'algoritmo che completa un batch di consegne dei pacchetti dai nodi di origine al sink, l'array di accumulo di energia preparato verrà aggiornato in modo da avere valori ridotti cella per cella. Il consumo di energia lungo il percorso sarà la somma del consumo di energia per percorso da nodo a nodo, calcolato secondo un modello energetico¹. La procedura dettagliata è illustrata nella figura 7 supplementare.
4. Usando lo script Python, registra il momento in cui il primo nodo viene svuotato e quando metà dei nodi viene svuotato. La procedura dettagliata è illustrata nella figura 8 supplementare.

Figura 8: toClusterHeadDistance Array per nodo non cluster_head con indice 24. La prima colonna è la distanza e la seconda colonna è il numero indice della testa del cluster Fare clic qui per visualizzare una versione più grande di questa figura.

Figura 9: CHID_buff matrice. Numeri di sequenza dei nodi sensore selezionati come teste del cluster. Fare clic qui per visualizzare una versione più grande di questa figura.

Figura 10 CHIdx_buff matrice. Assegnato il numero di sequenza dei nodi del sensore della testa del cluster a ciascun nodo del sensore corrispondente. Fare clic qui per visualizzare una versione più grande di questa figura.

Figura 11: CH_BUFF matrice. Gruppo di cluster per ogni nodo del sensore head del cluster corrispondente al CHID_buff dell'array. Ogni gruppo di cluster è costituito da 0 o più nodi sensore. In ogni matrice di gruppi di cluster vengono visualizzati i numeri di sequenza dei nodi sensore in esso contenuti. Fare clic qui per visualizzare una versione più grande di questa figura.

Figura 12: Calcolo del percorso di instradamento per settore. Per ogni settore, vengono calcolati i percorsi di routing per tutti i nodi di origine. Fare clic qui per visualizzare una versione più grande di questa figura.

Risultati

I risultati di un campione di esecuzione sono illustrati nella Tabella 2, Tabella 3 e Tabella 4. I set di dati dettagliati per i tre batch di dati sono disponibili nella cartella Dati supplementari 1 .

Set di dati 1
198 nodi in un'area circolare con un raggio di 50 m	Algoritmo quantistic...

Discussione

L'attuale processore quantistico commerciale all'avanguardia può essere utilizzato in problemi computazionali di qualsiasi topologia di rete¹. L'applicazione del processore quantistico non è vincolata dal numero di qbit fisici che i processori quantistici sono stati in grado di implementare.

Nella progettazione del prolungamento della durata della rete di sensori, i risultati mostrano un progresso nel metodo per ottenere una durata della rete ancora più lunga utiliz...

Materiali

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