양자 처리 장치를 사용한 대규모 에너지 효율적인 센서 네트워크 라우팅

Summary

이 연구는 양자 프로세서 장치를 사용하여 네트워크 수명을 최대화하기 위해 문헌의 기존 방법을 능가하는 다양한 트래픽 역학에 대한 경로를 계산하는 방법을 제공합니다.

Abstract

클래식 컴퓨터와 양자 프로세서의 하이브리드 사용인 센서 네트워크 에너지 보존 방법은 클래식 컴퓨터를 사용하는 휴리스틱 알고리즘보다 더 나은 성능을 발휘하는 것으로 입증되었습니다. 이 원고에서는 방법의 중요성에 대한 기술적 맥락을 제시하고 정당화합니다. 그런 다음 실험 단계는 필요한 경우 그림과 함께 작동 순서로 시연됩니다. 이 방법은 무작위로 생성된 네트워크 토폴로지 샘플 세트에서 긍정적인 결과로 검증되었습니다. 이 방법의 성공적인 실험 결과는 센서 네트워크 수명 최대화 문제에 대한 더 나은 접근 방식을 제공했으며 현재 최첨단 양자 프로세서가 문헌의 현재 방법을 무시하는 장점으로 큰 실용적인 엔지니어링 문제를 해결할 수 있음을 입증했습니다. 즉, 양자 우위를 최대한 활용할 수 있습니다. 개념 증명의 단계를 넘어 실현 가능성의 증명으로 넘어갔습니다.

Introduction

센서 네트워크의 에너지 보존은 설계¹에서 매우 중요한 문제였습니다. 고전적인 방법은 일반적으로 임시 접근 방식 ^2,3,4,5,6을 사용하여 문제를 해결합니다. 즉, 이러한 방법은 센서 노드를 개인과 커뮤니티의 이익 모두에 봉사하기 위해 협력할 수 있는 개별적으로 관리되는 지능형 자산으로 에뮬레이트합니다. 센서가 작동하는 불안정한 환경으로 인해 일부 작업에서는 환경의 불확실성을 포착하기 위해 무작위 알고리즘을 도입하는 반면, 다른 작업에서는 상식적으로 수용 가능한 결과를 얻을 수 있는 휴리스틱 알고리즘을 고안하기 위해 생체 지능을 차용합니다⁷. 더 자세히 설명하자면, 이러한 랜덤 알고리즘의 경우 환경 불확실성은 기존 CPU에 의해 생성된 랜덤 시퀀스만큼 무작위적이지 않을 수 있고, 다른 한편으로는 환경 불확실성이 절대적으로 랜덤하더라도 클래식 CPU에 의해 생성된 랜덤 프로세스 시뮬레이터에 의해 캡처될 수 없습니다. 이러한 생체 지능 알고리즘의 경우, 첫째, 개념적 증명 작업을 수행하기 위한 엄격한 수학적 분석이 도출되지 않았으며, 둘째, 진리에 대한 수렴 또는 오류 허용 경계는 정보에 입각한 실측 자료가 주어졌을 때만 구성될 수 있습니다. 우선, 이러한 알고리즘은 잘 정의된 사용 사례 시나리오에 대해 분석(시뮬레이션되지 않음)되고, 추가 연구에서 여전히 숙고할 가치가 있는 특정 기준에서 멈추고, 다른 하나는 앞서 말했듯이 대부분의 알고리즘이 센서를⁸로 만드는 마이크로프로세서에 더 쉽게 배포할 수 있는 소프트웨어 시뮬레이션에 대해 검증되지 않았습니다.

여기서 기계 학습(ML)은^{센서 장치9}에서 이식할 수 없는 상대적으로 많은 양의 계산 능력을 필요로 하는 데이터 분석을 사용해야 하기 때문에 고려하지 않는다.

위에서 언급한 문제를 해결하기 위해 하이브리드 양자 알고리즘을 제공합니다. 이 알고리즘은 네트워크 토폴로지가 설정되면 양자 프로세서를 사용하여 수행되는 라우팅 계산 중에 클러스터 헤드 선택 메커니즘이 고전적인 임의 알고리즘을 사용하여 구현된다는 점에서 하이브리드입니다. 이 방법은 다음과 같이 정당화됩니다 : (1) 환경 불확실성에 관한 첫 번째 단락에서 논의 된 바와 같이, 우리는 역사적으로 추적 가능할 수 있기 때문에 환경 역학을 포착하기 위해 양자 시퀀스 생성기를 적용하기 위해 더 이상 노력하고 싶지 않습니다. 역사적으로 추적할 수 있는 환경 역학은 네트워크 과학의 다양한 기계 학습 연구 작업에 의해 정당화되었습니다. 현재 단계에서는 고전적인 접근 방식을 유지합니다. (2) 추상적인 수학적 분석에 의존하는 정확한 방법은 실측 자료에 도달하는 것을 보장합니다. 양자 실험 물리학은 지금까지 물리 수학에 의해 정교하게 지원되었습니다. 더욱이, Shor 알고리즘¹⁰ 과 같은 알고리즘 응용 프로그램은 이 둥근 이론을 증명하기 위해 존재했습니다.

비교를 위해 적절한 양의 문헌 조사가 아래에 제공됩니다. 제안된^{HEESR 프로토콜 11} 은 결과에서 입증 가능한 장점이 있지만 저자는 노드 위치의 정확한 무작위 분포 함수, 클러스터 헤드 백분율 p(0.2%)의 적절한 정당성 및 노드 a_i 간 에너지 수준 분포(1-2줄)에 대한 스케일링 매개변수와 같은 시뮬레이션 구성 매개변수를 잘 지정했습니다. 저자가 실험을 복제하고 비교를 수행하기 위해 더 이상 진행하는 것을 금지했습니다. 전력 라우팅 메카니즘(¹² )은 최적의 네트워크 라우팅의 결정 과정에 영향을 미치는 결정요인에 대해 지정되지 않은 샘플 공간으로부터 수득된 이산 데이터 세트로부터 수렴된 연속 함수를 근사하기 위해 곡선 피팅 방법을 채용한다. 곡선 피팅 방법⁽¹³ )은 네트워크 토폴로지에 대한 사전 정보를 필요로 한다. 실제 상황에서는 사전 정보를 쉽게 얻을 수 없을 수 있습니다. 사전 정보가 있더라도 네트워크 토폴로지는 도함수 계산을 용이하게 할 수 있는 피팅 곡선에 매핑할 수 있을 만큼 규칙적이지 않을 수 있습니다. 동일한 논리에 따라, DORAF 프로토콜¹⁴ 는 네트워크 결정 요인을 근사화하기 위해 볼츠만 함수와 로지스틱 함수를 차용하는 방법과 이유를 정당화하지 않았습니다. Ismail et ^al.15 은 수중 네트워크에서 에너지 효율적인 라우팅 프로토콜 설계에 대한 향후 연구 노력을 위한 건전한 참고 자료를 제공했습니다.

Protocol

1. Dwave 해양 환경 설정

1. 링크에서 해양 도구를 다운로드하여 설치하십시오 : https://docs.ocean.dwavesys.com/en/stable/overview/install.html
   1. 터미널에서 python -m venv ocean을 입력합니다.
   2. 터미널에서 그림 1과 같이 ocean/bin/activate를 입력합니다.
   3. 터미널에서 git clone https://github.com/dwavesystems/dwave-ocean-sdk.git 를 입력합니다.
      그런 다음 그림 2와 같이 cd dwave-ocean-sdk를 입력합니다.
      그런 다음 python setup.py install

그림 1: 해양 가상 환경 활성화. D-wave API가 통합된 Ocean 패키지는 사용자 자신의 컴퓨터를 통해 D-wave 기계 구내에 흐린 사용자 경험을 제공합니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

그림 2: Ocean SDK 설치. Ocean 패키지는 편리한 Cplex 설치를 포함하여 개발자에게 필요한 도구 키트를 제공합니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

2. Cplex Python API 인터페이스 설치

1. Cplex: https://pypi.org/project/cplex/ 다운로드 및 설치
   1. 터미널에서 pip install cplex를 입력합니다.

3. 실험 구성 매개변수

1. 보충 그림 1과 같이 스크립트에서 Python 프로그래밍 표기법을 사용하여 표 1에 언급된 실험 구성 매개변수를 설정합니다. 스크립트가 실행되고 실행되면 기본 언어가 RAM에 변수를 저장하도록 처리됩니다. 매개 변수에 각각 값이 할당되는 Python 코드의 스크린샷이 첨부되어 있습니다(보충 그림 1).

d0	87.7085 미터
E	50 * 1 x 10-09 줄
epson_fs	1 * 10-12* 10줄
epson_mp	0.0013 * 1 * 10-12 줄
패킷 크기	4000비트

표 1: 에너지 모델 매개변수 및 패킷 크기 설정.

보충 그림 1: 스크립트1. 실험 매개 변수를 설정하는 스크립트입니다. 이 파일을 다운로드하려면 여기를 클릭하십시오.

4. Python 스크립트

1. 반경 50m의 원형 영역을 분할하는 6개의 섹터로 균등하게 흩어져 있는 198개의 센서 노드 2D 위치를 생성하도록 Python 스크립트를 준비합니다.
   참고: 원형 그래프는 6개의 섹터로 나뉩니다. 각 섹터에서 각 노드의 위치는 두 개의 해당 변수로 처리됩니다. 하나는 각도이고 다른 하나는 반지름입니다. 균일 랜덤 분포 생성기를 사용하여 각도와 반지름 모두에 값을 할당합니다. 자세한 절차는 보충 그림 2 및 보충 그림 3에 나와 있습니다.
2. 각 섹터 내에서 33개의 센서 노드가 정규 분포에 의해 랜덤하게 흩어져 있는지 확인합니다. 2D 위치를 'posdata'+sector_no+'.txt' 라는 이름 철자 규칙 아래 각 섹터별로 텍스트 파일에 저장합니다(그림 3 및 그림 4).
   1. 반경이 50m인 원형 영역을 6개의 섹터로 분할합니다. 이 6개 섹터의 시작 각도 값은 벡터 A= [60,120,180,240,300,360]이 됩니다.
      1. 섹터 인덱스가 i라고 가정하고 j^번째 센서 노드의 극점 길이를 l_{i,j}=50*random.random()으로 설정합니다.
      2. 섹터 인덱스가 i라고 가정하고 j^번째 센서 노드의 각도 값을 ang_{i,j}=(60*random.random() + A_i - 60) * 2 * pi / 360으로 설정합니다.
      3. i^번째 섹터에서 j^번째 센서 노드의 데카르트 좌표를 다음과 같이 설정합니다.
         x_{i,j}=l_{i,j}*cos(ang_{i,j})
         y_{i,j}=l_{i,j}*sin(ang_{i,j})

보충 그림 2: 스크립트2. 섹터별로 각 노드에 대한 두 차원 위치 위치를 구성하는 스크립트입니다. 이 파일을 다운로드하려면 여기를 클릭하십시오.

보충 그림 3: 스크립트3. 1 섹터 내에서 각 노드 위치 값을 구성하는 스크립트입니다. 이 파일을 다운로드하려면 여기를 클릭하십시오.

그림 3: 생성 및 저장된 노드 위치는 각각 하나의 섹터에 해당하는 6개의 파일로 분리됩니다. 2차원 위치 위치는 6개의 posdata+'idx' 파일에 저장됩니다. 각각은 섹터를 나타냅니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

그림 4: 섹터 0에 저장된 노드 위치. 위치는 2차원이며 균일 랜덤 생성기를 사용하여 생성됩니다. 첫 번째 열은 수평 위치이고 두 번째 열은 수직 위치입니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

5. 초기 에너지 레벨 준비

1. 198개 센서 노드 모두에 대한 초기 에너지 레벨을 준비합니다. 그 중 절반은 0.5J의 초기 에너지로, 나머지 절반은 1J의 초기 에너지로 할당합니다. 각 노드의 에너지 준위를 저장할 배열을 만들고 루프를 사용하여 짝수로 배열된 셀에는 값 1을, 홀수로 배열된 셀에는 값 0.5를 할당합니다. 보충 그림 4 는 Python 코드를 보여 주며 결과는 그림 5에 나와 있습니다.

보충 그림 4: Script4. 노드 에너지의 절반인 1줄과 다른 0.5줄을 할당하는 스크립트입니다. 이 파일을 다운로드하려면 여기를 클릭하십시오.

그림 5: Energy_buffer 초기 할당. 노드의 절반에는 에너지 1줄이 할당되고 나머지 절반에는 0.5줄이 할당됩니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

6. 알고리즘 스크립트 준비Advanced_Leach (그림 6 및 그림 7)

1. 클러스터 헤드가 선택되고 클러스터가 형성되는 기능 스크립트를 준비합니다.
   참고: 클러스터는 선택한 클러스터 헤드의 수가 전체 노드 수를 6으로 나눈 값보다 작은 조건에서 루프를 사용하여 선택됩니다. 조건은 각 클러스터 내에서 소스 노드 양이 6보다 작거나 같도록 하는 것입니다. 루프 내에서 각 노드에는 [0,1] 사이의 난수가 할당됩니다. 지정된 기준 번호보다 작은 노드는 클러스터 헤드가 되고 다른 노드는 소스 노드가 됩니다. 자세한 절차는 보충 그림 5에 나와 있습니다. 그런 다음 클러스터 헤드의 고정된 풀이 주어지면 나머지 소스 노드는 클러스터 헤드가 아직 6개 이상의 소스 노드를 호스팅하지 않은 경우 최단 거리 내에서 클러스터 헤드를 선택합니다. 자세한 절차는 보충 그림 6에 나와 있습니다.
   1. T_n=P/(1-P*(count%(1/P)))를 설정하고, 여기서 P = 0.2(전체 네트워크 크기에 대한 클러스터 헤드 수의 비례 비율)이고 count는 현재까지 반올림된 전송량입니다.
   2. 각 센서 노드에 대해 [0,1] threshold_rm = random.random() 사이의 난수를 얻습니다.
      1. threshold_rm가 T_n 미만인 경우 이 센서 노드를 클러스터 헤드로 선택합니다.
   3. cluster_head되지 않은 각 노드에 대해 가장 가까운 클러스터 헤드 센서 노드를 클러스터 헤드로 선택합니다. 클러스터 헤드의 고정된 풀이 주어지면 나머지 소스 노드는 클러스터 헤드가 아직 6개 이상의 소스 노드를 호스팅하지 않은 경우 최단 거리 내에서 클러스터 헤드를 선택합니다. 자세한 절차는 보충 그림 6에 나와 있습니다.
2. 이 라운드의 전체 네트워크에서 에너지 고갈 프로세스를 계산하기 위해 명령줄을 준비합니다. 소스 노드에서 싱크로 패킷의 한 배치 전달을 완료하는 알고리즘이 실행될 때마다 준비된 에너지 저장 어레이가 셀별로 값을 줄이도록 업데이트됩니다. 경로를 따라 에너지 소비는 에너지 모델¹에 따라 계산되는 노드 간 경로당 에너지 소비의 합계가 됩니다. 자세한 절차는 보충 그림 7에 나와 있습니다.
3. 필요한 전송 라운드 메트릭을 계산합니다.
   참고: 한 배치의 패킷 전달을 완료하기 위해 알고리즘을 실행할 때마다 에너지 어레이가 업데이트되고 실행량 및 드레이닝된 노드 수가 계산됩니다. 값이 1보다 크거나 같으면 FND(첫 번째 노드 다이)는 현재 실행량과 같습니다. 값이 노드 양의 절반보다 크거나 같으면 HND(절반 노드 다이)는 현재 실행량과 같습니다. 값이 전체 노드 양과 같으면 AND(모든 노드 소멸)은 현재 실행 양과 같습니다. 자세한 절차는 보충 그림 8에 나와 있습니다.

그림 6: 클러스터 헤드 배열. 클러스터 헤드로 선택된 노드의 시퀀스 번호입니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

그림 7: 클러스터 헤드 인덱스 배열. 클러스터 헤드 인덱스 어레이에는 각각 33개의 센서 노드가 있는 6개의 섹터가 있으므로 숫자는 해당 센서 노드가 속한 클러스터 헤드의 시퀀스 번호를 나타냅니다. 어레이의 위치 인덱스는 각 센서 노드의 시퀀스 번호에 해당합니다. 클러스터 헤드로 선택된 센서 노드의 경우, 어레이의 해당 슬롯에 할당된 번호는 그 자체의 시퀀스 번호입니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

보충 그림 5: 스크립트5. 클러스터 헤드를 선택하는 스크립트입니다. 이 파일을 다운로드하려면 여기를 클릭하십시오.

보충 그림 6: 스크립트6. 원본 노드를 클러스터에 할당하는 스크립트입니다. 이 파일을 다운로드하려면 여기를 클릭하십시오.

보충 그림 7: Script7. 전송을 통해 소비되는 에너지의 양을 줄여 모든 소스 노드에 대한 에너지 버퍼를 업데이트하는 스크립트입니다. 이 파일을 다운로드하려면 여기를 클릭하십시오.

보충 그림 8: Script8. 첫 번째 노드가 죽고 노드의 절반이 소멸되는 반올림의 양을 계산하는 스크립트입니다. 이 파일을 다운로드하려면 여기를 클릭하십시오.

7. 하이브리드 양자 알고리즘 스크립트 준비

1. 클러스터 헤드가 선택되고 클러스터 헤드가 형성되는 작동하는 스크립트를 준비합니다.
   1. 이 실험¹에서 최대 클러스터 크기가 6이므로 클러스터 헤드의 양이 current_valid_node_amount/6 이상인지 확인하고 이 기준이 충족될 때까지 선택 절차가 루프에서 실행됩니다.
      참고: current_valid_node_amount가 6보다 크지 않으면 이러한 유효한 노드는 하나의 클러스터를 형성합니다.
   2. cluster_head_valid되지 않은 각 노드에 대해 선택한 각 클러스터 헤드까지의 거리를 계산하고 클러스터 크기가 6을 초과하지 않고 거리 값이 가장 작은 클러스터 헤드를 할당합니다.
      참고: 그림 8에서는 선택된 클러스터 헤드(24)까지의 모든 비cluster_head_valid 노드의 거리가 계산되고 선택된 모든 클러스터 헤드가 그림 9에 표시됩니다. 그림 10 은 해당 클러스터 헤드에 할당된 모든 노드를 보여주고, 그림 11 은 각 클러스터의 멤버 노드를 벡터 배열로 그룹화한 것을 보여줍니다.
2. 클러스터당 라우팅 최적화 문제가 형성되어 D-wave API에 제출되는 하위 함수 스크립트를 준비합니다(그림 12). 라우팅 경로는 클러스터별로 계산됩니다.
3. Python 스크립트를 사용하여 전체 네트워크의 에너지 고갈 프로세스를 계산하여 전송 라운드 수 측면에서 네트워크 수명 기준으로 알고리즘을 정량적으로 평가합니다.
   참고: 소스 노드에서 싱크로 패킷의 한 배치 전달을 완료하는 알고리즘이 실행될 때마다 준비된 에너지 저장 배열이 셀 단위로 값을 줄이도록 업데이트됩니다. 경로를 따른 에너지 소비는 에너지 모델¹에 따라 계산된 노드 간 경로당 에너지 소비의 합계가 됩니다. 자세한 절차는 보충 그림 7에 나와 있습니다.
4. Python 스크립트를 사용하여 첫 번째 노드가 드레이닝되는 순간과 노드의 절반이 드레이닝되는 순간을 기록합니다. 자세한 절차는 보충 그림 8에 나와 있습니다.

그림 8: 인덱스가 24인 cluster_head 노드가 아닌 노드에 대한 toClusterHeadDistance 배열. 첫 번째 열은 거리이고 두 번째 열은 클러스터 헤드 인덱스 번호입니다 . 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

그림 9: CHID_buff 배열. 클러스터 헤드로 선택된 센서 노드의 시퀀스 번호입니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

그림 10 CHIdx_buff 배열. 클러스터 헤드 센서 노드의 시퀀스 번호를 각 해당 센서 노드에 할당했습니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

그림 11: CH_BUFF 배열 어레이 CHID_buff에 해당하는 클러스터 헤드 센서 노드당 클러스터 그룹입니다. 각 클러스터 그룹은 0개 이상의 센서 노드로 구성됩니다. 각 클러스터 그룹 배열은 그 안에 있는 센서 노드의 시퀀스 번호를 표시합니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

그림 12: 섹터별 라우팅 경로 계산. 각 섹터에 대해 모든 소스 노드의 라우팅 경로가 계산됩니다. 이 그림의 더 큰 버전을 보려면 여기를 클릭하십시오.

Results

하나의 실행 샘플의 결과를 표 2, 표 3 및 표 4에 나타내었습니다. 세 가지 데이터 배치에 대한 자세한 데이터 집합은 보조 데이터 1 폴더에서 사용할 수 있습니다.

데이터셋 1
반경 50m의 원형 영역에 198개의 노드	하이브리드 양자 알고리즘	Advanced_Leach 알고리즘
에프엔드	1442	727
한드(HND)	2499	19...

Discussion

현재의 최첨단 상용 양자 프로세서는 모든 네트워크 토폴로지¹의 계산 문제에서 사용할 수 있습니다. 양자 프로세서 응용 프로그램은 양자 프로세서가 구현할 수 있는 물리적 qbits 수에 의해 제한되지 않습니다.

센서 네트워크 수명 연장 설계에서 결과는 양자 프로세서를 사용하여 훨씬 더 긴 네트워크 수명을 달성하는 방법의 발전을 보여줍니다. 이 결과는 양자 우위가 공공 및 민간 부문 모두에서 상업적으로 활용될 준비가 되었음을 의미합니다.

경영적 측면에서 Quantum Advantage는 가까운 미래의 하이테크 지속 가능한 번영을 위한 유망한 길을 닦는 다음 이정표가 될 수 있습니다. 학습 전략 및/또는 인공 지능(AI) 측면에서 현재의 하이테크는 어떤 방식으로든 데이터를 처리/유지하기 위한 동력 구동이 필요합니다. Green Globe의 높은 수준에서 볼 때 좋은 후보로 눈에 띄지 않습니다...

Materials

List of materials used in this article

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