Roteamento de rede de sensores energeticamente eficiente em larga escala usando uma unidade de processador quântico

Summary

Este estudo fornece um método para usar uma unidade de processador quântico para calcular as rotas para várias dinâmicas de tráfego que trabalham para superar os métodos clássicos na literatura para maximizar a vida útil da rede.

Abstract

O método de conservação de energia da rede de sensores, que é um híbrido de uso de um computador clássico e processador quântico, provou ter um desempenho melhor do que o algoritmo heurístico usando um computador clássico. Neste manuscrito, o contexto técnico para a significância do método é apresentado e justificado. Em seguida, as etapas experimentais são demonstradas em uma sequência operacional com ilustrações, se necessário. O método foi validado por resultados positivos em um conjunto de amostras de topologias de rede gerado aleatoriamente. Os resultados experimentais bem-sucedidos deste método forneceram uma melhor abordagem para problemas de maximização da vida útil da rede de sensores e demonstraram que o atual processador quântico de última geração tem sido capaz de resolver grandes problemas práticos de engenharia com méritos que se sobrepõem aos métodos atuais na literatura. Em outras palavras, a vantagem quântica pode ser explorada para melhores esforços. Passou da fase de prova de conceito para a prova de viabilidade.

Introduction

A conservação de energia em redes de sensores tem sido uma questão muito crítica no projeto¹. Os métodos clássicos normalmente abordam o problema usando uma abordagem ad hoc 2,3,4,5,6. Dito isso, esses métodos emulam os nós de sensor como ativos inteligentes gerenciados individualmente que também poderiam cooperar para servir aos interesses do indivíduo e da comunidade. Devido ao ambiente volátil onde os sensores trabalham, em alguns trabalhos algoritmos aleatórios são introduzidos para capturar as incertezas ambientais, enquanto em outros, a biointeligência é emprestada para elaborar algoritmos heurísticos que possam alcançar resultados aceitáveis no senso comum⁷. Para ilustrar melhor, para esses algoritmos aleatórios, por um lado, as incertezas ambientais podem não ser tão aleatórias quanto a sequência aleatória gerada por uma CPU clássica, por outro lado, mesmo que as incertezas ambientais sejam absolutamente aleatórias, elas não poderiam ser capturadas pelo simulador de processo aleatório gerado pela CPU clássica; para esses algoritmos de bio-inteligência, em primeiro lugar, nenhuma análise matemática rigorosa foi derivada para fazer uma prova conceitual funcionar, em segundo lugar, a convergência para a verdade ou o limite de tolerância ao erro só pode ser configurado dada uma verdade fundamentada informada - embora uma quantidade significativa de trabalhos na literatura tenha demonstrado até certo ponto que esses algoritmos heurísticos funcionam, Por um lado, esses algoritmos são analisados (não simulados) contra cenários de casos de uso bem definidos, eles param em certos critérios que ainda valem a pena ponderar em pesquisas futuras, por outro, como dito anteriormente, a maioria dos algoritmos não foi validada contra simulação de software que pode ser mais prontamente implantada nos microprocessadores que fazem um sensor em seu ser⁸.

Não consideramos o aprendizado de máquina (ML) aqui porque ele precisa empregar análise de dados, o que requer um volume relativamente grande de poder computacional que não é portátil em dispositivos de sensor⁹.

Para abordar as preocupações acima mencionadas, fornecemos um algoritmo quântico híbrido. O algoritmo é híbrido em que o mecanismo de seleção da cabeça do cluster é implementado usando um algoritmo aleatório clássico durante os cálculos de roteamento conduzidos usando um processador quântico uma vez que a topologia de rede é configurada. O método é justificado da seguinte forma: (1) Como discutido no primeiro parágrafo em relação às incertezas ambientais, não queremos nos esforçar mais para aplicar um gerador de sequência quântica para capturar a dinâmica ambiental, porque ele pode ser historicamente rastreável. A dinâmica ambiental que pode ser historicamente rastreável tem sido justificada por vários trabalhos de pesquisa de aprendizado de máquina em ciência de redes. Para o estágio atual, permanecemos com a abordagem clássica. (2) O método exato que se baseia na análise matemática abstrata garante chegar à verdade fundamental. A física experimental quântica tem sido até agora sofisticadamente apoiada pela matemática física. Além disso, aplicações de algoritmos como o algoritmo Shor¹⁰ existiram para provar essa teoria arredondada.

Uma quantidade adequada de levantamento da literatura é fornecida abaixo para comparação. O protocolo HEESR proposto¹¹ tem méritos demonstráveis nos resultados, mas os autores especificaram bem os parâmetros de configuração da simulação, por exemplo, a função exata de distribuição aleatória da posição do nó, a justificativa adequada do percentual de cabeça de cluster p (0,2%) e o parâmetro de escala para distribuição do nível de energia (1-2 joules) entre nós a_i. Proibiu o autor de continuar a duplicar os experimentos e realizar a comparação. O mecanismo de roteamento de potência¹² emprega o método de ajuste de curva para aproximar funções contínuas convergentes de conjuntos de dados discretos obtidos de espaço amostral não especificado para determinantes que afetam o processo de decisão do roteamento de rede ideal. O método de ajuste de curva¹³ requer informações prévias sobre a topologia da rede. Circunstâncias reais podem não ter informações prévias prontamente disponíveis. Mesmo quando existem informações anteriores, a topologia de rede pode não ser regular o suficiente para poder ser mapeada em curvas de ajuste que são capazes de facilitar a computação derivável. Seguindo a mesma lógica, o protocolo DORAF¹⁴ não justificou como e por que tomar emprestado a função de Boltzmann e a função logística para aproximar os determinantes da rede. Ismail et ^al.15 forneceram uma referência sólida para futuros esforços de pesquisa em projetos de protocolos de roteamento energeticamente eficientes na rede subaquática.

Protocol

1. Configurando o Dwave Ocean Environment

1. Baixe e instale as ferramentas do oceano no link: https://docs.ocean.dwavesys.com/en/stable/overview/install.html
   1. No terminal, digite python -m venv ocean.
   2. No terminal, digite ocean/bin/activate, como mostra a Figura 1.
   3. No terminal, digite git clone https://github.com/dwavesystems/dwave-ocean-sdk.git
      Em seguida, digite cd dwave-ocean-sdk, como mostra a Figura 2.
      Em seguida, digite python setup.py instalar

Figura 1: Ativação do ambiente virtual oceânico. O pacote Ocean, como API D-wave integrada, fornece uma experiência de usuário nublada sobre o próprio computador do usuário para a premissa da máquina D-wave. Clique aqui para ver uma versão maior desta figura.

Figura 2: Instalação do Ocean SDK. O pacote Ocean fornece kits de ferramentas necessários para desenvolvedores, incluindo uma instalação prática do Cplex. Clique aqui para ver uma versão maior desta figura.

2. Instalação da interface da API Python do Cplex

1. Baixe e instale o Cplex: https://pypi.org/project/cplex/
   1. No terminal, digite pip install cplex.

3. Parâmetros de configuração do experimento

1. Configure os parâmetros de configuração do experimento mencionados na Tabela 1 usando a notação de programação Python no script, conforme mostrado na Figura 1 Suplementar. Depois que o script for executado e executado, a linguagem subjacente será processada para armazenar as variáveis na RAM. Uma captura de tela dos códigos Python onde os parâmetros são atribuídos valores respectivamente é anexada (Figura Suplementar 1).

d0	87.7085 milh
E	50 * 1 x 10-09 joules
epson_fs	1 * 10-12* 10 joules
epson_mp	0,0013 * 1 * 10-12 joules
tamanho do pacote	4000 bits

Tabela 1: Parâmetro do modelo de energia e configurações de tamanho do pacote.

Figura suplementar 1: Script1. Script para configurar os parâmetros do experimento. Clique aqui para baixar este arquivo.

4. Scripts Python

1. Prepare os scripts Python para gerar 198 posições 2D do nó do sensor que estão igualmente espalhadas em seis setores que dividem a área circular com um raio de 50 m.
   NOTA: O gráfico circular é segmentado em 6 setores. Em cada setor, a posição de cada nó é tratada com duas variáveis correspondentes. Um é o ângulo e o outro é o raio. Atribua valores ao ângulo e ao raio usando um gerador de distribuição aleatória uniforme. O procedimento detalhado é mostrado na Figura Suplementar 2 e na Figura Suplementar 3.
2. Dentro de cada setor, certifique-se de que os 33 nós do sensor estejam espalhados aleatoriamente por uma distribuição normal. Salve as posições 2D em arquivos de texto por cada setor sob a regra de ortografia do nome como 'posdata'+sector_no+'.txt' (Figura 3 e Figura 4).
   1. Segmente a área circular com um raio de 50 m em seis setores. Os valores angulares iniciais para esses seis setores formam o vetor A= [60,120,180,240,300,360].
      1. Suponha que o índice de setor seja i, defina o comprimento do polo para j^ésimo nó do sensor como l_{i,j}=50*random.random()
      2. Suponha que o índice do setor seja i, defina o valor angular para j^ésimo nó do sensor como ang_{i,j}=(60*random.random() + A_i - 60) * 2 * pi / 360
      3. Defina as coordenadas cartesianas do^{j ésimo} nó do sensor no^i-ésimo setor como
         x_{i,j}=l_{i,j}*cos(ang_{i,j})
         y_{i,j}=l_{i,j}*sin(ang_{i,j})

Figura suplementar 2: Script2. Script para configurar os dois locais de posição de dimensão para cada nó por setor. Clique aqui para baixar este arquivo.

Figura Suplementar 3: Script3. Script para configurar os valores de posição de cada nó dentro de 1 setor. Clique aqui para baixar este arquivo.

Figura 3: Posições de nó geradas e armazenadas separadas em 6 arquivos cada um correspondendo a um setor. Os locais de posição bidimensionais são salvos em 6 arquivos posdata+'idx'. Cada um apresenta um setor. Clique aqui para ver uma versão maior desta figura.

Figura 4: Posições do nó armazenadas no setor 0. As posições são em duas dimensões e geradas usando um gerador aleatório uniforme. A primeira coluna são os locais horizontais e a segunda coluna são os locais verticais. Clique aqui para ver uma versão maior desta figura.

5. Preparação dos níveis iniciais de energia

1. Prepare os níveis de energia iniciais para todos os 198 nós do sensor. Atribua metade deles com energia inicial em 0,5 J e a outra metade com energia inicial em 1 J. Crie uma matriz para armazenar o nível de energia de cada nó e use um loop para atribuir às células sequenciadas em números pares o valor 1 e aquelas sequenciadas em números ímpares o valor de 0,5. A Figura 4 suplementar mostra os códigos Python e o resultado é mostrado na Figura 5.

Figura Suplementar 4: Script4. Script para atribuir metade da energia do nó de 1 joule e os outros 0,5 joules. Clique aqui para baixar este arquivo.

Figura 5: Energy_buffer atribuição inicial. Metade dos nós são atribuídos com energia 1 joule, enquanto as outras metades são atribuídas com 0,5 joules. Clique aqui para ver uma versão maior desta figura.

6. Preparando Advanced_Leach script de algoritmo (Figura 6 e Figura 7)

1. Prepare um script funcional onde o cabeçalho do cluster é selecionado e o cluster é formado.
   Observação : o cluster é selecionado usando um loop na condição de que o número de cabeças de cluster selecionadas é menor do que o número total de nós dividido por 6. A condição é garantir que, dentro de cada cluster, a quantidade de nó de origem seja igual ou menor que 6. Dentro do loop, a cada nó é atribuído um número aleatório entre [0,1]. Aqueles menores do que um determinado número de critérios tornam-se a cabeça do cluster, enquanto outros se tornam os nós de origem. O procedimento detalhado é mostrado na Figura Suplementar 5. Em seguida, dado um pool fixo de cabeças de cluster, o restante dos nós de origem seleciona suas cabeças de cluster dentro da menor distância, dado que o cabeçalho de cluster ainda não hospedou mais de 6 nós de origem. O procedimento detalhado é mostrado na Figura 6 Suplementar.
   1. Defina T_n=P/(1-P*(count%(1/P))), onde P = 0,2 (a taxa proporcional do número de cabeças de cluster ao tamanho geral da rede) e a contagem é a quantidade de arredondamento de transmissão atualizada.
   2. Para cada nó do sensor, obtenha um número aleatório entre[0,1] threshold_rm = random.random()
      1. Se threshold_rm for menor que T_n, selecione esse nó do sensor como o cabeçalho do cluster.
   3. Para cada um dos nós não cluster_head, selecione o nó do sensor de cabeça de cluster mais próximo dele como sua cabeça de cluster. Dado um pool fixo de cabeças de cluster, o restante dos nós de origem seleciona suas cabeças de cluster dentro da menor distância, dado que a cabeça de cluster ainda não hospedou mais de 6 nós de origem. O procedimento detalhado é mostrado na Figura 6 Suplementar.
2. Prepare as linhas de comando para calcular o processo de esgotamento de energia em toda a rede para esta rodada. Para cada execução do algoritmo que completa um lote de entregas dos pacotes dos nós de origem para o coletor, a matriz de armazenamento de energia preparada será atualizada para ter reduzido célula por célula em valores. O consumo de energia ao longo do caminho será a soma do consumo de energia por rota nó-a-nó, que é calculado de acordo com um modelo de energia¹. O procedimento detalhado é mostrado na Figura Suplementar 7.
3. Calcule as métricas de transmissão redondas necessárias.
   Observação : por cada execução do algoritmo para concluir um lote de entrega de pacotes, a matriz de energia é atualizada, a quantidade de execução e o número de nós drenados são contados. Se o valor for maior ou igual a 1, o FND (primeiro dado do nó) será igual ao valor de execução atual. Se o valor for maior ou igual à metade da quantidade do nó, HND (half node die) será igual à quantidade de execução atual. Se o valor for igual à quantidade total do nó, AND (all node die) será igual à quantidade de execução atual. O procedimento detalhado é mostrado na Figura Suplementar 8.

Figura 6: Matriz de cabeçalho de cluster. Os números de sequência dos nós que foram selecionados para serem os cabeçalhos do cluster. Clique aqui para ver uma versão maior desta figura.

Figura 7: Matriz de índice de cabeça de cluster. Como há seis setores, cada um com 33 nós de sensor, na matriz de índice de cabeça de cluster, o número indica o número de sequência da cabeça de cluster ao qual o nó de sensor correspondente pertence. O índice de posição da matriz corresponde ao número de sequência de cada nó do sensor. Para o nó do sensor selecionado como cabeça do cluster, o número atribuído ao seu slot na matriz é o número de sequência de si mesmo. Clique aqui para ver uma versão maior desta figura.

Figura Suplementar 5: Script5. Script para selecionar o cabeçalho do cluster. Clique aqui para baixar este arquivo.

Figura 6 suplementar: Script6. Script para atribuir nós de origem a clusters. Clique aqui para baixar este arquivo.

Figura Suplementar 7: Script7. Script para atualizar o buffer de energia para todos os nós de origem através da redução da quantidade de energia consumida através da transmissão. Clique aqui para baixar este arquivo.

Figura suplementar 8: Script8. Script para calcular a quantidade de arredondamentos até que o primeiro nó morre e metade dos nós morre. Clique aqui para baixar este arquivo.

7. Preparando script de algoritmo quântico híbrido

1. Prepare um script funcional onde o cabeçalho do cluster é selecionado e o cabeçalho do cluster é formado.
   1. Como o tamanho máximo do cluster é 6 neste experimento¹, certifique-se de que a quantidade de cabeças de cluster não seja inferior a current_valid_node_amount/6, o procedimento de seleção será executado em um loop até que esse critério seja atendido.
      Observação : se current_valid_node_amount não for maior do que 6, esses nós válidos formam um e somente cluster próprios.
   2. Para cada um dos nós não cluster_head_valid, calcule a distância dele para cada um dos cabeçalhos de cluster selecionados e atribua a ele a cabeça de cluster cujo tamanho de cluster não excedeu 6, onde o valor de distância é o menor.
      NOTA: Na Figura 8, todas as distâncias dos nós não cluster_head_valid até a cabeça de cluster selecionada 24 são calculadas e toda a cabeça de cluster selecionada é exibida na Figura 9. A Figura 10 mostra todos os nós atribuídos à cabeça de cluster correspondente, e a Figura 11 mostra o agrupamento dos nós membros de cada cluster em uma matriz vetorial.
2. Prepare o script de subfunção, onde o problema de otimização de roteamento por cluster é formado e enviado para a API D-wave (Figura 12). Os caminhos de roteamento são computados cluster por cluster.
3. Usando o script Python, calcule o processo de depleção de energia em toda a rede para avaliar quantitativamente o algoritmo por tempo de vida da rede em termos do número de rodadas de transmissão.
   Observação : para cada execução do algoritmo que conclui um lote de entregas dos pacotes dos nós de origem para o coletor, a matriz de armazenamento de energia conforme preparado será atualizado para ter célula por célula reduzida em valores. O consumo de energia ao longo do caminho será a soma do consumo de energia por rota nó-a-nó, calculado de acordo com um modelo de energia¹. O procedimento detalhado é mostrado na Figura Suplementar 7.
4. Usando o script Python, registre o momento em que o primeiro nó é drenado e quando metade dos nós é drenada. O procedimento detalhado é mostrado na Figura Suplementar 8.

Figura 8: toClusterHeadDistance Array para nó não cluster_head com índice 24. A primeira coluna é a distância e a segunda coluna é o número do índice de cabeça do cluster Clique aqui para ver uma versão maior desta figura.

Figura 9: CHID_buff matriz. Números de sequência dos nós do sensor que são selecionados como cabeçalhos de cluster. Clique aqui para ver uma versão maior desta figura.

Figura 10 CHIdx_buff matriz. Número de sequência atribuído aos nós do sensor de cabeça de cluster para cada nó de sensor correspondente. Clique aqui para ver uma versão maior desta figura.

Figura 11: CH_BUFF matriz. Grupo de cluster por nós de sensor de cabeça de cluster correspondentes ao CHID_buff de matriz. Cada grupo de cluster consiste em 0 ou mais de 0 nós de sensor. Cada matriz de grupo de cluster exibe os números de sequência dos nós de sensor que estão nela. Clique aqui para ver uma versão maior desta figura.

Figura 12: Cálculo do caminho de roteamento por setor. Para cada setor, os caminhos de roteamento para todos os nós de origem são computados. Clique aqui para ver uma versão maior desta figura.

Results

Os resultados de uma amostra de corrida são mostrados na Tabela 2, Tabela 3 e Tabela 4. Os conjuntos de dados detalhados para os três lotes de dados estão disponíveis na pasta Dados Suplementares 1 .

Conjunto de dados 1
198 nós em uma área circular com um raio de 50m	Algoritmo Quântico H...

Discussion

O atual processador quântico comercial de última geração pode ser usado em problemas computacionais de qualquer topologia de rede¹. A aplicação do processador quântico não é limitada pelo número de qbits físicos que qualquer um dos processadores quânticos foi capaz de implementar.

No projeto de prolongamento da vida útil da rede de sensores, os resultados mostram um avanço no método para alcançar uma vida útil de rede ainda mais longa usando um processador quântico. Os...

Materials

List of materials used in this article

Name	Company	Catalog Number	Comments
Notebook Dell	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