Routage de réseau de capteurs économes en énergie à grande échelle à l’aide d’une unité de processeur quantique

Résumé

Cette étude fournit une méthode permettant d’utiliser une unité de processeur quantique pour calculer les itinéraires pour diverses dynamiques de trafic qui fonctionnent pour surpasser les méthodes classiques dans la littérature afin de maximiser la durée de vie du réseau.

Résumé

La méthode de conservation de l’énergie des réseaux de capteurs, qui est un hybride d’utilisation d’un ordinateur classique et d’un processeur quantique, s’est avérée plus performante que l’algorithme heuristique utilisant un ordinateur classique. Dans ce manuscrit, le contexte technique de l’importance de la méthode est présenté et justifié. Ensuite, les étapes expérimentales sont démontrées dans une séquence opérationnelle avec des illustrations si nécessaire. La méthode a été validée par des résultats positifs sur un ensemble d’échantillons de topologies de réseau générés aléatoirement. Les résultats expérimentaux positifs de cette méthode ont fourni une meilleure approche pour les problèmes de maximisation de la durée de vie des réseaux de capteurs et ont démontré que l’état de l’art actuel des processeurs quantiques a été capable de résoudre de grands problèmes d’ingénierie pratiques avec des mérites qui remplacent les méthodes actuelles dans la littérature. En d’autres termes, l’avantage quantique peut être exploité au mieux. Il est passé du stade de la preuve de concept à celui de la preuve de faisabilité.

Introduction

La conservation de l’énergie dans les réseaux de capteurs a été une question très critique dans la conception¹. Les méthodes classiques abordent normalement le problème en utilisant une approche ad hoc 2,3,4,5,6. Cela dit, ces méthodes émulent les nœuds de capteurs en tant qu’actifs intelligents gérés individuellement qui pourraient également coopérer pour servir à la fois les intérêts de l’individu et de la communauté. En raison de l’environnement instable dans lequel fonctionnent les capteurs, dans certains travaux, des algorithmes aléatoires sont introduits afin de capturer les incertitudes environnementales, tandis que dans d’autres, la bio-intelligence est empruntée pour concevoir des algorithmes heuristiques qui pourraient atteindre des résultats acceptables de bon sens⁷. Pour illustrer davantage, pour ces algorithmes aléatoires, d’une part, les incertitudes environnementales peuvent ne pas être aussi aléatoires que la séquence aléatoire générée par un processeur classique, d’autre part, même si les incertitudes environnementales sont absolument aléatoires, elles ne pourraient pas être capturées par le simulateur de processus aléatoire généré par un processeur classique ; Pour ces algorithmes de bio-intelligence, tout d’abord, aucune analyse mathématique rigoureuse n’a été dérivée pour faire fonctionner une preuve conceptuelle, deuxièmement, la convergence vers la vérité ou la limite de tolérance d’erreur ne peut être configurée qu’à partir d’une vérité terrain informée - bien qu’un nombre important de travaux dans la littérature aient démontré dans une certaine mesure que ces algorithmes heuristiques fonctionnent, D’une part, ces algorithmes sont analysés (et non simulés) par rapport à des scénarios d’utilisation bien définis, ils s’arrêtent à certains critères qui méritent encore d’être médités dans des recherches ultérieures, d’autre part, comme indiqué précédemment, la majorité des algorithmes n’ont pas été validés par rapport à la simulation logicielle qui peut être plus facilement déployée dans les microprocesseurs qui font d’un capteur son être⁸.

Nous ne prenons pas en compte l’apprentissage automatique (ML) ici car il doit utiliser l’analyse de données qui nécessite un volume relativement important de puissance de calcul qui n’est pas portable dans les dispositifs de détection⁹.

Pour répondre aux préoccupations mentionnées ci-dessus, nous fournissons un algorithme quantique hybride. L’algorithme est hybride en ce sens que le mécanisme de sélection de la tête de cluster est implémenté à l’aide d’un algorithme aléatoire classique lors des calculs de routage effectués à l’aide d’un processeur quantique une fois la topologie du réseau configurée. La méthode est justifiée comme suit : (1) Comme nous l’avons vu dans le premier paragraphe concernant les incertitudes environnementales, nous ne voulons pas nous efforcer d’appliquer un générateur de séquences quantiques pour capturer la dynamique environnementale parce qu’elle pourrait être historiquement traçable. La dynamique environnementale qui peut être historiquement traçable a été justifiée par divers travaux de recherche sur l’apprentissage automatique en science des réseaux. Pour l’étape actuelle, nous restons avec l’approche classique. (2) La méthode exacte qui s’appuie sur l’analyse mathématique abstraite garantit d’arriver à la vérité terrain. Jusqu’à présent, la physique expérimentale quantique a été soutenue de manière sophistiquée par les mathématiques physiques. De plus, des applications algorithmiques comme l’algorithme de Shor¹⁰ ont existé pour prouver cette théorie arrondie.

Une quantité adéquate d’études bibliographiques est fournie ci-dessous à des fins de comparaison. Le protocole HEESR proposé¹¹ a des mérites démontrables dans les résultats, mais les auteurs ont bien spécifié les paramètres de configuration de la simulation, par exemple, la fonction de distribution aléatoire exacte de la position du nœud, la justification correcte du pourcentage de tête d’amas p (0,2%) et le paramètre d’échelle pour la distribution du niveau d’énergie (1-2 joules) entre les nœuds a_i. Il a interdit à l’auteur de procéder à la duplication des expériences et à la comparaison. Le mécanisme de routage de puissance¹² utilise la méthode d’ajustement de courbe pour approximer les fonctions continues convergées à partir d’ensembles de données discrets obtenus à partir d’un espace d’échantillonnage non spécifié pour les déterminants qui ont un impact sur le processus de décision du routage réseau optimal. La méthode d’ajustement de courbe¹³ nécessite des informations préalables sur la topologie du réseau. Dans des circonstances réelles, il se peut que les informations préalables ne soient pas facilement disponibles. Même lorsqu’il existe des informations préalables, la topologie du réseau peut ne pas être suffisamment régulière pour pouvoir être mappée sur des courbes d’ajustement capables de faciliter les calculs dérivables. Suivant la même logique, le protocole DORAF¹⁴ n’a pas justifié comment et pourquoi emprunter la fonction de Boltzmann et la fonction logistique pour approximer les déterminants du réseau. Ismail et ^al.15 ont fourni une référence solide pour les futurs efforts de recherche sur la conception de protocoles de routage économes en énergie dans le réseau sous-marin.

Protocole

1. Mise en place de Dwave Ocean Environment

1. Téléchargez et installez les outils océaniques à partir du lien : https://docs.ocean.dwavesys.com/en/stable/overview/install.html
   1. Au terminal, tapez python -m venv ocean.
   2. Sur le terminal, tapez . ocean/bin/activate, comme illustré à la Figure 1.
   3. Dans le terminal, tapez git clone https://github.com/dwavesystems/dwave-ocean-sdk.git
      Ensuite, tapez cd dwave-ocean-sdk, comme illustré à la figure 2.
      Ensuite, tapez python setup.py installer

Figure 1 : Activation de l’environnement virtuel de l’océan. Le package Ocean, en tant qu’API D-wave intégrée, offre une expérience utilisateur nuageuse sur l’ordinateur de l’utilisateur jusqu’au site de la machine D-wave. Veuillez cliquer ici pour voir une version agrandie de cette figure.

Figure 2 : Installation du SDK Ocean. Le forfait Ocean fournit les kits d’outils nécessaires pour les développeurs, y compris une installation pratique de Cplex. Veuillez cliquer ici pour voir une version agrandie de cette figure.

2. Installation de l’interface de l’API Python de Cplex

1. Téléchargez et installez Cplex : https://pypi.org/project/cplex/
   1. Sur le terminal, tapez pip install cplex.

3. Paramètres de configuration de l’expérience

1. Configurez les paramètres de configuration de l’expérience mentionnés dans le tableau 1 à l’aide de la notation de programmation Python dans le script, comme illustré dans la figure supplémentaire 1. Une fois le script exécuté et exécuté, le langage sous-jacent stocke les variables dans la RAM. Vous trouverez ci-joint une capture d’écran des codes Python auxquels les paramètres sont respectivement affectés (Figure 1 supplémentaire).

d0	87,7085 m d’altitude
E	50 * 1 x 10-09 joules
epson_fs	1 * 10-12 * 10 joules
epson_mp	0,0013 * 1 * 10-12 joules
Taille du paquet	4000 bits

Tableau 1 : Paramètres du modèle énergétique et paramètres de taille des paquets.

Figure supplémentaire 1 : Script1. Script pour configurer les paramètres de l’expérience. Veuillez cliquer ici pour télécharger ce fichier.

4. Scripts Python

1. Préparez les scripts Python pour générer 198 positions 2D de nœud de capteur qui sont également dispersées en six secteurs qui divisent la zone circulaire avec un rayon de 50 m.
   REMARQUE : Le graphique circulaire est segmenté en 6 secteurs. Dans chaque secteur, la position de chaque nœud est traitée avec deux variables correspondantes. L’un est l’angle et l’autre est le rayon. Attribuez des valeurs à l’angle et au rayon à l’aide d’un générateur de distribution aléatoire uniforme. La procédure détaillée est illustrée à la figure supplémentaire 2 et à la figure supplémentaire 3.
2. À l’intérieur de chaque secteur, assurez-vous que les 33 nœuds de capteurs sont dispersés de manière aléatoire selon une distribution normale. Enregistrez les positions 2D dans des fichiers texte pour chaque secteur sous la règle d’orthographe du nom sous la forme 'posdata'+sector_no+'.txt' (Figure 3 et Figure 4).
   1. Segmentez la zone circulaire d’un rayon de 50 m en six secteurs. Les valeurs angulaires de départ pour ces six secteurs donnent le vecteur A= [60,120,180,240,300,360].
      1. Supposons que l’index sectoriel soit i, définissez la longueur du pôle pour le j^ème nœud du capteur comme l_{i,j}=50*random.random()
      2. Supposons que l’indice sectoriel soit i, définissez la valeur angulaire pour j^ème nœud de capteur comme ang_{i,j}=(60*random.random() + A_i - 60) * 2 * pi / 360
      3. Définissez les coordonnées cartésiennes du j^ème noeud du capteur dans i^ème secteur comme suit :
         x_{i,j}=l_{i,j}*cos(ang_{i,j})
         y_{i,j}=l_{i,j}*sin(ang_{i,j})

Figure supplémentaire 2 : Script2. Script permettant de configurer les deux emplacements de position de cote pour chaque noeud par secteur. Veuillez cliquer ici pour télécharger ce fichier.

Figure supplémentaire 3 : Script3. Script permettant de configurer les valeurs de position de chaque nœud dans 1 secteur. Veuillez cliquer ici pour télécharger ce fichier.

Figure 3 : Positions de noeuds générées et stockées séparées en 6 fichiers, chacun correspondant à un secteur. Les positions en deux dimensions sont enregistrées dans 6 fichiers posdata+'idx'. Chacune présente un secteur. Veuillez cliquer ici pour voir une version agrandie de cette figure.

Figure 4 : Positions des noeuds stockées dans le secteur 0. Les positions sont en deux dimensions et générées à l’aide d’un générateur aléatoire uniforme. La première colonne représente les emplacements horizontaux et la deuxième colonne les emplacements verticaux. Veuillez cliquer ici pour voir une version agrandie de cette figure.

5. Préparer les niveaux d’énergie initiaux

1. Préparez les niveaux d’énergie initiaux pour les 198 nœuds de capteurs. Attribuez à la moitié d’entre eux une énergie initiale de 0,5 J et à l’autre moitié une énergie initiale de 1 J. Créez un tableau pour stocker le niveau d’énergie de chaque nœud et utilisez une boucle pour attribuer aux cellules séquencées en nombres pairs la valeur 1 et à celles séquencées en nombres impairs la valeur 0,5. La figure 4 supplémentaire montre les codes Python, et le résultat est illustré à la figure 5.

Figure supplémentaire 4 : Script4. Script pour assigner la moitié de l’énergie du nœud de 1 joule et l’autre 0,5 joule. Veuillez cliquer ici pour télécharger ce fichier.

Figure 5 : Energy_buffer affectation initiale. La moitié des nœuds sont affectés avec une énergie de 1 joule, tandis que les autres moitiés sont affectées avec 0,5 joule. Veuillez cliquer ici pour voir une version agrandie de cette figure.

6. Préparation Advanced_Leach script d’algorithme (Figure 6 et Figure 7)

1. Préparez un script fonctionnel dans lequel la tête de cluster est sélectionnée et le cluster est formé.
   REMARQUE : Le cluster est sélectionné à l’aide d’une boucle à condition que le nombre de têtes de cluster sélectionnées soit inférieur au nombre total de nœuds divisé par 6. La condition consiste à s’assurer qu’au sein de chaque cluster, la quantité de nœuds source est égale ou inférieure à 6. Dans la boucle, chaque nœud se voit attribuer un nombre aléatoire compris entre [0,1]. Ceux qui sont plus petits qu’un nombre de critères donné deviennent la tête du cluster, tandis que d’autres deviennent les nœuds source. La procédure détaillée est illustrée à la figure supplémentaire 5. Ensuite, étant donné un pool fixe de têtes de cluster, le reste des nœuds sources sélectionne leurs têtes de cluster sur la distance la plus courte, étant donné que la tête de cluster n’a pas encore hébergé plus de 6 nœuds source. La procédure détaillée est illustrée à la figure supplémentaire 6.
   1. Définissez T_n=P/(1-P*(count%(1/P)))), où P = 0,2 (le taux proportionnel du nombre de têtes de cluster à la taille globale du réseau) et le nombre est la quantité d’arrondi de transmission à ce jour.
   2. Pour chaque noeud de capteur, atteindre un nombre aléatoire entre [0,1] threshold_rm = random.random()
      1. Si threshold_rm est inférieur à T_n, sélectionnez ce nœud de capteur comme tête de cluster.
   3. Pour chacun des noeuds non cluster_head, sélectionnez le noeud de capteur de tête de cluster le plus proche de celui-ci en tant que tête de cluster. Étant donné un pool fixe de têtes de cluster, le reste des nœuds source sélectionne leurs têtes de cluster à la distance la plus courte, étant donné que la tête de cluster n’a pas encore hébergé plus de 6 nœuds source. La procédure détaillée est illustrée à la figure supplémentaire 6.
2. Préparez les lignes de commande pour calculer le processus d’épuisement de l’énergie sur l’ensemble du réseau pour ce tour. Pour chaque exécution de l’algorithme qui effectue un lot de livraisons de paquets des nœuds sources vers le récepteur, la baie de stockage d’énergie telle qu’elle a été préparée sera mise à jour pour avoir des valeurs réduites cellule par cellule. La consommation d’énergie le long du chemin sera la somme de la consommation d’énergie par route nœud à nœud, qui est calculée selon un modèle énergétique¹. La procédure détaillée est illustrée à la figure supplémentaire 7.
3. Calculez les métriques de cycle de transmission requises.
   REMARQUE : À chaque exécution de l’algorithme pour effectuer un lot de livraison de paquets, le réseau d’énergie est mis à jour, la quantité d’exécution et le nombre de nœuds vidés sont comptés. Si la valeur est supérieure ou égale à 1, FND (premier nœud dé) est égal à la quantité d’exécution actuelle. Si la valeur est supérieure ou égale à la moitié de la valeur du nœud, la valeur HND (demi-matrice de nœud) est égale à la valeur d’exécution actuelle. Si la valeur est égale à la quantité totale de noeud, alors ET(matrice de tous les noeuds) est égale à la quantité d’exécution actuelle. La procédure détaillée est illustrée à la figure supplémentaire 8.

Figure 6 : Réseau de têtes de cluster. Numéros de séquence des noeuds qui ont été sélectionnés pour être les têtes de cluster. Veuillez cliquer ici pour voir une version agrandie de cette figure.

Figure 7 : Tableau d’index de tête de cluster. Étant donné qu’il y a six secteurs, chacun avec 33 noeuds de capteur, dans le tableau d’index de tête de cluster, le nombre indique le numéro de séquence de la tête de cluster à laquelle appartient le noeud de capteur correspondant. L’indice de position du réseau correspond au numéro de séquence de chaque nœud de capteur. Pour le noeud de capteur sélectionné comme tête de cluster, le numéro attribué à son emplacement dans la matrice est le numéro de séquence de lui-même. Veuillez cliquer ici pour voir une version agrandie de cette figure.

Figure supplémentaire 5 : Script5. Script pour sélectionner la tête de cluster. Veuillez cliquer ici pour télécharger ce fichier.

Figure supplémentaire 6 : Script6. Script permettant d’affecter des noeuds sources à des clusters. Veuillez cliquer ici pour télécharger ce fichier.

Figure supplémentaire 7 : Script7. Script permettant de mettre à jour le tampon d’énergie pour tous les nœuds source via la réduction de la quantité d’énergie consommée par la transmission. Veuillez cliquer ici pour télécharger ce fichier.

Figure supplémentaire 8 : Script8. Script pour calculer le nombre d’arrondis jusqu’à laquelle le premier noeud meurt et la moitié des noeuds meurent. Veuillez cliquer ici pour télécharger ce fichier.

7. Préparation d’un script d’algorithme quantique hybride

1. Préparez un script fonctionnel dans lequel la tête de cluster est sélectionnée et la tête de cluster est formée.
   1. Comme la taille maximale de la grappe est de 6 dans cette expérience¹, assurez-vous que le nombre de têtes de grappe n’est pas inférieur à current_valid_node_amount/6, la procédure de sélection sera exécutée en boucle jusqu’à ce que ce critère soit rempli.
      REMARQUE : Si current_valid_node_amount n’est pas supérieur à 6, ces nœuds valides forment eux-mêmes un seul et unique cluster.
   2. Pour chacun des noeuds non cluster_head_valid, calculez la distance de celui-ci par rapport à chacune des têtes de cluster sélectionnées et affectez-lui la tête de cluster dont la taille de cluster n’a pas dépassé 6 où la valeur de distance est la plus petite.
      REMARQUE : Dans la Figure 8, les distances de tous les noeuds non cluster_head_valid par rapport à la tête de cluster sélectionnée 24 sont calculées, et toutes les têtes de cluster sélectionnées sont affichées dans la Figure 9. La figure 10 montre que tous les noeuds sont affectés à leur tête de cluster correspondante, et la figure 11 montre le regroupement des noeuds membres de chaque cluster dans un réseau vectoriel.
2. Préparez le script de sous-fonction, où le problème d’optimisation du routage par cluster est formé et soumis à l’API D-wave (Figure 12). Les chemins de routage sont calculés cluster par cluster.
3. À l’aide d’un script Python, calculez le processus d’épuisement de l’énergie sur l’ensemble du réseau pour évaluer quantitativement l’algorithme en fonction de la durée de vie du réseau en termes de nombre de cycles de transmission.
   REMARQUE : Pour chaque exécution de l’algorithme qui effectue un lot de livraisons des paquets des nœuds sources vers le récepteur, la baie de stockage d’énergie telle qu’elle a été préparée sera mise à jour pour avoir des valeurs réduites cellule par cellule. La consommation d’énergie le long du chemin sera la somme de la consommation d’énergie par route nœud à nœud, calculée selon un modèle énergétique¹. La procédure détaillée est illustrée à la figure supplémentaire 7.
4. À l’aide d’un script Python, enregistrez le moment où le premier nœud est vidé et où la moitié des nœuds sont vidangés. La procédure détaillée est illustrée à la figure supplémentaire 8.

Figure 8 : toClusterHeadDistance Array pour un nœud non cluster_head avec l’index 24. La première colonne est la distance et la deuxième colonne est le numéro d’index de la tête de grappe Veuillez cliquer ici pour voir une version agrandie de cette figure.

Figure 9 : CHID_buff tableau. Numéros de séquence des noeuds de capteur sélectionnés en tant que têtes de cluster. Veuillez cliquer ici pour voir une version agrandie de cette figure.

Figure 10 CHIdx_buff tableau. Attribuez le numéro de séquence des noeuds de capteur de tête de cluster à chaque noeud de capteur correspondant. Veuillez cliquer ici pour voir une version agrandie de cette figure.

Figure 11 : tableau CH_BUFF. Groupe de clusters par noeuds de capteur de tête de cluster correspondant à la CHID_buff de la matrice. Chaque groupe de clusters se compose de 0 ou de 0 nœud de capteur. Chaque tableau de groupe de clusters affiche les numéros de séquence des nœuds de capteurs qui s’y trouvent. Veuillez cliquer ici pour voir une version agrandie de cette figure.

Figure 12 : Calcul du chemin de routage par secteur. Pour chaque secteur, les chemins de routage de tous les noeuds sources sont calculés. Veuillez cliquer ici pour voir une version agrandie de cette figure.

Résultats

Les résultats d’un échantillon d’essai sont présentés dans les tableaux 2, 3 et 4. Les jeux de données détaillés pour les trois lots de données sont disponibles dans le dossier Données supplémentaires 1 .

...

Jeu de données 1

198 nœuds dans une zone circulaire d’un rayon de 50 m

Discussion

Le processeur quantique commercial de pointe actuel peut être utilisé dans des problèmes de calcul de n’importe quelle topologie de réseau¹. L’application des processeurs quantiques n’est pas limitée par le nombre de qbits physiques que l’un des processeurs quantiques a été capable d’implémenter.

Dans la conception de la prolongation de la durée de vie des réseaux de capteurs, les résultats montrent une avancée dans la méthode permettant d’obte...

matériels

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