Крупномасштабная энергоэффективная маршрутизация сенсорной сети с использованием квантового процессора

Резюме

В этом исследовании представлен метод использования квантового процессора для вычисления маршрутов для различных динамик трафика, которые превосходят классические методы в литературе для максимизации времени жизни сети.

Аннотация

Метод энергосбережения сенсорной сети, представляющий собой гибрид использования классического компьютера и квантового процессора, доказал свою эффективность лучше, чем эвристический алгоритм с использованием классического компьютера. В данной работе представлен и обоснован технический контекст значимости метода. Затем экспериментальные этапы демонстрируются в рабочей последовательности с иллюстрациями, если это необходимо. Метод был проверен положительными результатами на случайно сгенерированном выборочном наборе сетевых топологий. Успешные экспериментальные результаты этого метода обеспечили лучший подход к задачам максимизации времени жизни сенсорной сети и продемонстрировали, что современный квантовый процессор способен решать большие практические инженерные задачи с достоинствами, которые перекрывают существующие в литературе методы. Другими словами, квантовое преимущество может быть использовано наилучшими усилиями. Он вышел за рамки проверки концепции и перешел от доказательства осуществимости.

Введение

Энергосбережение в сенсорных сетях было очень важным вопросом при проектировании¹. Классические методы обычно решают проблему с помощью специального подхода 2,3,4,5,6. Тем не менее, эти методы имитируют сенсорные узлы как индивидуально управляемые интеллектуальные активы, которые также могут сотрудничать, чтобы служить интересам как отдельного человека, так и общества. Из-за изменчивой среды, в которой работают датчики, в некоторых работах вводятся случайные алгоритмы для того, чтобы уловить неопределенности окружающей среды, в то время как в других используется биоинтеллект для разработки эвристических алгоритмов, которые могли бы^{достичь результатов,} приемлемых с точки зрения здравого смысла. Чтобы проиллюстрировать далее, для этих случайных алгоритмов, с одной стороны, неопределенности окружающей среды могут быть не такими случайными, как случайная последовательность, сгенерированная классическим процессором, с другой стороны, даже если неопределенности среды абсолютно случайны, они не могут быть учтены симулятором случайных процессов, сгенерированным классическим процессором; Для этих алгоритмов биоинтеллекта, во-первых, не было проведено строгого математического анализа, чтобы концептуальное доказательство работало, во-вторых, сходимость к истине или граница допустимости ошибок могут быть сконфигурированы только при наличии обоснованной базовой истины - хотя значительное количество работ в литературе продемонстрировало в той или иной степени работу этих эвристических алгоритмов. Во-первых, эти алгоритмы анализируются (а не моделируются) в соответствии с четко определенными сценариями использования, они останавливаются на определенных критериях, над которыми все еще стоит задуматься в дальнейших исследованиях, во-вторых, как было сказано ранее, большинство алгоритмов не были проверены на соответствие программному моделированию, которое может быть легко развернуто в микропроцессорах, которые превращают датчик^{в его} существо.

Мы не рассматриваем здесь машинное обучение (ML), потому что оно должно использовать аналитику данных, которая требует относительно большого объема вычислительной мощности, которая не переносима в сенсорных устройствах⁹.

Для решения вышеупомянутых проблем мы предлагаем гибридный квантовый алгоритм. Алгоритм является гибридным в том смысле, что механизм выбора головы кластера реализован с помощью классического случайного алгоритма во время вычислений маршрутизации, проводимых с помощью квантового процессора после настройки топологии сети. Метод обоснован следующим образом: (1) Как обсуждалось в первом параграфе относительно неопределенностей окружающей среды, мы не хотим дальше пытаться применить генератор квантовых последовательностей для захвата динамики окружающей среды, потому что она может быть исторически прослежена. Динамика окружающей среды, которую можно проследить исторически, была обоснована различными исследовательскими работами в области машинного обучения в области сетевых наук. На данном этапе мы придерживаемся классического подхода. (2) Точный метод, основанный на абстрактном математическом анализе, гарантирует достижение истинной истины. Квантовая экспериментальная физика до сих пор изощренно поддерживалась физической математикой. Более того, существуют приложения алгоритмов, такие как алгоритм Шора¹⁰ , чтобы доказать эту округленную теорию.

Для сравнения ниже приводится достаточное количество литературы для сравнения. Протокол HEESR, предложенный¹¹ , имеет очевидные достоинства в результатах, но авторы хорошо определили параметры конфигурации моделирования, например, точную функцию случайного распределения положения узла, правильное обоснование процента напора кластера p (0,2%) и параметр масштабирования для распределения уровня энергии (1-2 джоуля) между узлами a_i. Это запретило автору продолжать дублировать эксперименты и проводить сравнение. Механизм маршрутизации^{питания 12} использует метод аппроксимации кривой для аппроксимации сходящихся непрерывных функций из дискретных наборов данных, полученных из неопределенного пространства выборок, для детерминант, влияющих на процесс принятия решения об оптимальной маршрутизации сети. Метод аппроксимации кривой¹³ требует предварительной информации о топологии сети. В реальных обстоятельствах предварительная информация может быть недоступна. Даже при наличии предварительной информации топология сети может быть недостаточно регулярной, чтобы ее можно было отобразить на аппроксимирующие кривые, которые могут облегчить выводимые вычисления. Следуя той же логике, протокол¹⁴ DORAF не обосновал, как и зачем заимствовать функцию Больцмана и логистическую функцию для аппроксимации детерминант сети. Исмаил и ^др.15 послужили надежным ориентиром для будущих исследований в области разработки энергоэффективных протоколов маршрутизации в подводной сети.

протокол

1. Настройка Dwave Ocean Environment

1. Скачать и установить ocean tools можно по ссылке: https://docs.ocean.dwavesys.com/en/stable/overview/install.html
   1. В терминале введите python -m venv ocean.
   2. На терминале введите . ocean/bin/activate, как показано на рисунке 1.
   3. В терминале введите git clone https://github.com/dwavesystems/dwave-ocean-sdk.git
      Затем введите cd dwave-ocean-sdk, как показано на рисунке 2.
      Затем введите python setup.py установить

Рисунок 1: Активация виртуальной среды океана. Пакет Ocean, интегрированный в API D-wave, обеспечивает облачный пользовательский интерфейс через собственный компьютер пользователя в помещении машины 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. После того, как сценарий запущен и выполнен, базовый язык будет хранить переменные в оперативной памяти. Прилагается скриншот кодов 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. Подготовьте скрипты Python для генерации 198 2D-положений сенсорных узлов, которые равномерно разбросаны по шести секторам, разделяющим круговую область радиусом 50 м.
   ПРИМЕЧАНИЕ: Круговой график сегментирован на 6 секторов. В каждом секторе положение каждого узла обрабатывается двумя соответствующими переменными. Один из них — угол, а другой — радиус. Присвойте значения как углу, так и радиусу с помощью генератора равномерного случайного распределения. Подробная процедура показана на дополнительном рисунке 2 и дополнительном рисунке 3.
2. В каждом секторе убедитесь, что 33 сенсорных узла разбросаны случайным образом по нормальному распределению. Сохраните 2D-позиции в текстовых файлах по каждому сектору в соответствии с правилом написания имен 'posdata'+sector_no+'.txt' (рисунок 3 и рисунок 4).
   1. Разделите круговую область радиусом 50 м на шесть секторов. Начальные угловые значения для этих шести секторов дают вектор 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. Задайте декартовы координаты узла^j-го датчика в^i-м секторе как
         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 файлов, каждый из которых соответствует одному сектору. Местоположения двухмерных позиций сохраняются в 6 файлах posdata+'idx'. Каждый из них представляет собой сектор. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этого рисунка.

Рисунок 4: Позиции узлов, хранящиеся в секторе 0. Позиции находятся в двух измерениях и генерируются с помощью однородного генератора случайных чисел. Первый столбец — это горизонтальные местоположения, а второй — вертикальные. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этого рисунка.

5. Подготовка начальных энергетических уровней

1. Подготовьте начальные уровни энергии для всех 198 сенсорных узлов. Назначьте половине из них начальную энергию 0,5 Дж, а другой половине — начальную энергию 1 Дж. Создайте массив для хранения уровня энергии каждого узла и с помощью цикла присвойте ячейкам, упорядоченным четными числами, значение 1, а ячейкам, упорядоченным по нечетным числам, значение 0,5. На дополнительном рисунке 4 показаны коды Python, а результат показан на рисунке 5.

Дополнительный рисунок 4: Сценарий4. Скрипт для присвоения половине энергии узла 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 узла датчика, число указывает порядковый номер головки кластера, к которому принадлежит соответствующий узел датчика. Позиционный индекс массива соответствует порядковому номеру каждого узла датчика. Для узла датчика, выбранного в качестве головки кластера, номер, присвоенный его слоту в массиве, является порядковым номером самого датчика. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этого рисунка.

Дополнительный рисунок 5: Сценарий 5. Скрипт для выбора головки кластера. Пожалуйста, нажмите здесь, чтобы скачать этот файл.

Дополнительный рисунок 6: Сценарий6. Скрипт для назначения исходных узлов кластерам. Пожалуйста, нажмите здесь, чтобы скачать этот файл.

Дополнительный рисунок 7: Сценарий 7. Скрипт для обновления буфера энергии для всех исходных узлов за счет уменьшения количества энергии, потребляемой при передаче. Пожалуйста, нажмите здесь, чтобы скачать этот файл.

Дополнительный рисунок 8: Сценарий 8. Скрипт для вычисления количества раундов, до которых умирает первый узел, а половина узлов умирает. Пожалуйста, нажмите здесь, чтобы скачать этот файл.

7. Подготовка сценария гибридного квантового алгоритма

1. Подготовьте функционирующий сценарий, в котором выбирается головка кластера и формируется головка кластера.
   1. Поскольку максимальный размер кластера в этом опыте¹ равен 6, убедитесь, что количество головок кластера не менее current_valid_node_amount/6, процедура выбора будет выполняться в цикле до тех пор, пока этот критерий не будет выполнен.
      ПРИМЕЧАНИЕ: Если current_valid_node_amount не больше 6, то эти допустимые узлы сами образуют один и единственный кластер.
   2. Для каждого из не cluster_head_valid узлов вычислить расстояние от него до каждого из выбранных головок кластера и назначить ему головку кластера, размер кластера которой не превысил 6, где значение расстояния наименьшее.
      ПРИМЕЧАНИЕ: На рисунке 8 вычисляются расстояния всех не cluster_head_valid узлов до выбранной головки кластера 24, и все выбранные головки кластера отображаются на рисунке 9. На рисунке 10 показаны все узлы, назначенные соответствующему головному кластеру, а на рисунке 11 показана группировка узлов-членов каждого кластера в векторный массив.
2. Подготовьте сценарий подфункции, в котором формируется задача оптимизации маршрутизации для каждого кластера и передается в API D-wave (рисунок 12). Пути маршрутизации вычисляются кластер за кластером.
3. Используя скрипт Python, рассчитайте процесс истощения энергии по всей сети, чтобы количественно оценить алгоритм по времени жизни сети с точки зрения количества циклов передачи.
   ПРИМЕЧАНИЕ: При каждом запуске алгоритма, который завершает одну партию доставки пакетов от исходных узлов к приемнику, подготовленный массив хранения энергии будет обновляться для уменьшения значений ячейка за ячейкой. Потребление энергии на пути будет представлять собой сумму энергопотребления на маршрут от узла к узлу, рассчитанную в соответствии с энергетической моделью¹. Подробная процедура показана на дополнительном рисунке 7.
4. Используя скрипт Python, запишите момент, когда первый узел будет опустошен и когда половина узлов будет опустошена. Подробная процедура показана на дополнительном рисунке 8.

Рисунок 8: Массив toClusterHeadDistance для не-cluster_head узла с индексом 24. В первом столбце указано расстояние, а во втором столбце — индекс головки кластера Нажмите здесь, чтобы просмотреть увеличенную версию этого рисунка.

Рисунок 9: CHID_buff массив. Порядковые номера узлов датчиков, выбранных в качестве головок кластера. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этого рисунка.

Figure 10 CHIdx_buff массива. Каждому соответствующему сенсорному узлу присвоен порядковый номер узлов датчика головки кластера. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этого рисунка.

Рисунок 11: CH_BUFF массив. Кластерная группа для каждого узла датчика головки кластера, соответствующего массиву CHID_buff. Каждая кластерная группа состоит из 0 или более 0 сенсорных узлов. В каждом массиве кластерных групп отображаются порядковые номера узлов датчиков, которые в нем находятся. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этого рисунка.

Рисунок 12: Вычисление маршрутного пути для каждого сектора. Для каждого сектора вычисляются пути маршрутизации для всех исходных узлов. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этого рисунка.

Результаты

Результаты одного прогонного образца приведены в таблицах 2, 3 и 4. Подробные наборы данных для трех пакетов данных доступны в папке Дополнительные данные 1 .

<...

Набор данных 1

Обсуждение

Современный коммерческий квантовый процессор может быть использован в вычислительных задачах любой топологии сети¹. Применение квантовых процессоров не ограничено количеством физических кбит, которые может реализовать любой из квантовых процессоров.

Пр?...

Материалы

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