使用量子处理器单元的大规模节能传感器网络路由

摘要

本研究提供了一种利用量子处理器单元计算各种交通动态路径的方法，该方法在延长网络寿命方面优于文献中报道的经典方法。

摘要

这种传感器网络节能方法结合了经典计算机与量子处理器的混合使用，已证明其性能优于仅使用经典计算机的启发式算法。本文阐述并论证了该方法具有重要意义的技术背景。随后，以操作顺序展示了实验步骤，并在必要时配以图示说明。该方法已在随机生成的网络拓扑样本集上通过正向结果得到验证。本方法取得的实验成功为延长传感器网络寿命的问题提供了更优的解决方案，并表明当前最先进的量子处理器已能够解决大规模的实际工程问题，其优势超越了现有文献中的各种方法。换句话说，可以充分挖掘和利用量子优势。该技术已超越概念验证阶段，进入可行性验证阶段。

引言

在传感器网络中，能量节约一直是设计中的一个极为关键的问题¹。传统方法通常采用特设方式来解决该问题^2,3,4,5,6。也就是说，这些方法将传感器节点模拟为可独立管理的智能资源，同时也能协作以兼顾个体与群体的利益。由于传感器所处环境具有高度不确定性，在部分研究中引入了随机算法以捕捉环境中的不确定性；而在其他研究中，则借鉴生物智能设计启发式算法，以获得符合常理的可接受结果⁷。进一步说明，对于这些随机算法而言，一方面，环境的不确定性可能并不像经典CPU生成的随机序列那样完全随机；另一方面，即使环境不确定性确实是完全随机的，也无法被经典CPU生成的随机过程模拟器准确捕捉。对于生物智能类算法而言，首先，尚无严格的数学分析能够提供概念上的理论证明；其次，收敛至真实值或误差容忍边界仅能在已知真实基准的前提下进行配置。尽管已有大量文献在一定程度上证明了这些启发式算法的有效性，但一方面，这些算法仅在定义明确的应用场景下进行了分析（而非模拟），且其停止条件仍存在值得进一步研究的疑问；另一方面，如前所述，大多数算法尚未通过可在构建传感器的微处理器上更易部署的软件仿真进行验证⁸。

本文不考虑机器学习（ML），因为它需要采用数据解析，而数据解析需要相对大量的计算能力，这在传感器设备中是不可移植的⁹。

为解决上述问题，我们提出了一种混合型量子算法。该算法的“混合”特性体现在：在网络拓扑结构建立后，路由计算过程在量子处理器上执行，而簇头选择机制则采用经典随机算法实现。该方法的合理性如下：（1）如第一段所述，考虑到环境的不确定性，我们不希望进一步尝试使用量子序列生成器来捕捉环境动态，因为这种动态可能具有历史可追溯性。网络科学研究中的多项机器学习研究成果已证实了具有历史可追溯性的环境动态的存在性。在当前阶段，我们仍采用经典方法。（2）依赖抽象数学分析的精确方法能够保证达到真实结果。迄今为止，量子实验物理学一直得到物理数学的有力支持。此外，诸如Shor算法¹⁰等算法的应用也已证实了这一理论体系的完备性。

以下提供了充分的文献综述以供比较。所提出的HEESR协议¹¹在结果方面具有可验证的优点，但作者对仿真配置参数进行了明确说明，例如节点位置的确切随机分布函数、簇头百分比p（0.2%）的合理依据，以及各节点a_i能量水平分布的缩放参数（1-2焦耳）。然而，这限制了作者进一步重复实验并开展对比研究。功率路由机制¹²采用曲线拟合方法，从影响最优网络路由决策因素的未明确样本空间中获得的离散数据集，逼近收敛的连续函数。曲线拟合方法¹³需要预先掌握网络拓扑信息。而实际情况中，此类先验信息可能无法 readily 获得。即使存在先验信息，网络拓扑也可能不够规则，难以映射到可用于推导计算的拟合曲线上。依此逻辑，DORAF协议¹⁴也未阐明为何以及如何借用玻尔兹曼函数和逻辑函数来逼近网络决定因素。Ismail 等人¹⁵为未来水下网络中能量高效路由协议设计的研究提供了坚实的参考依据。

方案

1. 设置 Dwave Ocean 环境

1. 从以下链接下载并安装海洋工具：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 install

图 1：Ocean 虚拟环境的激活。 Ocean 软件包集成了 D-wave API，可在用户本地计算机上提供通往 D-wave 机器的云端使用体验。请点击此处查看该图的放大版本。

图 2：Ocean SDK 安装。 Ocean 软件包为开发者提供了必要的工具包，包括便捷的 Cplex 安装功能。请点击此处查看此图的放大版本。

2. 安装 Cplex Python API 接口

1. 下载并安装 Cplex：https://pypi.org/project/cplex/
   1. 在终端中输入 pip install cplex。

3. 实验配置参数

1. 使用 Python 编程语法在脚本中设置 表1 中提到的实验配置参数，如 补充图1 所示。运行并执行脚本后，底层语言将处理并将变量存储在内存中。附有参数分别赋值的 Python 代码截图（补充图1）。

d0	87.7085 m
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 个传感器节点的二维位置，这些位置均匀分布在六个扇形区域中，每个区域划分半径为 50 m 的圆形区域。
   注意：圆形图被划分为 6 个扇区。在每个扇区内，每个节点的位置由两个对应的变量表示：一个是角度，另一个是半径。使用均匀随机分布生成器为角度和半径分配数值。详细步骤见补充图 2和补充图 3。
2. 在每个扇区内，确保 33 个传感器节点通过正态分布随机散布。按照命名规则'posdata'+sector_no+'.txt'将各扇区的二维位置保存为文本文件（图 3和图 4）。
   1. 将半径为 50 m 的圆形区域划分为六个扇区。这六个扇区的起始角度值构成向量 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：Script2。按扇区配置每个节点二维位置坐标的脚本。请点击此处下载该文件。

补充 图3：脚本3。用于配置单个扇区内每个节点位置值的脚本。请点击此处下载该文件。

图 3：生成并存储的节点位置，分为 6 个文件，每个文件对应一个扇区。 二维位置坐标保存在 6 个名为 posdata+'idx' 的文件中，每个文件代表一个扇区。 请点击此处查看该图的放大版本。

图 4：存储在扇区 0 中的节点位置。 位置为二维坐标，由均匀随机数生成器生成。第一列为水平坐标，第二列为垂直坐标。请点击此处查看该图的放大版本。

5. 准备初始能级

1. 为所有198个传感器节点准备初始能量值。将其中一半节点的初始能量设为0.5 J，另一半节点的初始能量设为1 J。创建一个数组用于存储每个节点的能量水平，并使用循环将序号为偶数的数组单元赋值为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. 对于每一个非簇头节点，选择距离其最近的簇头传感器节点作为其簇头。在一组固定的簇头基础上，其余源节点在不超过簇头已容纳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. 对于每一个非簇头的有效节点，计算其到各已选簇头的距离，并将其分配给距离最小且簇大小尚未超过 6 的簇头。
      注意：在 图 8 中，计算了所有非簇头有效节点到所选簇头 24 的距离，所有已选簇头在 图 9 中显示。图 10 显示所有节点已分配至其对应的簇头，图 11 展示将每个簇的成员节点按向量数组形式分组。
2. 准备子函数脚本，用于构建每个簇的路由优化问题，并提交至 D-wave API（图 12）。路由路径按簇逐一计算。
3. 使用 Python 脚本，计算整个网络中的能量耗尽过程，通过传输轮数来定量评估算法的网络寿命。
   注意：每次算法运行完成一批数据包从源节点到汇聚节点的传输后，预先准备的能量存储数组将逐单元更新，数值相应减少。路径上的能量消耗为根据能量模型¹计算得出的各节点间路由能耗之和。详细过程见 补充图 7。
4. 使用 Python 脚本，记录第一个节点能量耗尽的时刻以及半数节点能量耗尽的时刻。详细过程见 补充图 8。

图 8：索引为 24 的非簇头节点的 toClusterHeadDistance 数组。 第一列为距离，第二列为簇头索引号 请点击此处查看该图的放大版本。

图 9：CHID_buff 数组。 被选为簇头的传感器节点的序号。请点击此处查看此图的放大版本。

图10 CHIdx_buff 数组。 将指定的簇头传感器节点序号分配给每个相应的传感器节点。请点击此处查看本图的放大版本。

图 11：CH_BUFF 数组。 每个簇头传感器节点对应的簇组，对应于数组 CHID_buff。每个簇组包含 0 个或多个传感器节点。每个簇组数组显示该组内传感器节点的序号。请点击此处查看该图的放大版本。

图 12：每个扇区的路由路径计算。 对于每个扇区，计算所有源节点的路由路径。 请点击此处查看此图的放大版本。

结果

一次运行样本的结果如表2、表3和表4所示。三批数据的详细数据集可在补充数据1文件夹中获取。

数据集 1
半径为 50m 的圆形区域内的 198 个节点	混合量子算法	Advanced_Leach 算法
FND	1442	727
HND	2499	1921

讨论

目前最先进的商用量子处理器可用于解决任何网络拓扑结构的计算问题¹。量子处理器的应用不受限于任何量子处理器所能实现的物理量子比特数量。

在传感器网络寿命延长设计中，研究结果表明，通过使用量子处理器，实现更长网络寿命的方法取得了进展。这些结果意味着量子优势已具备在公共和私营部门进行商业化应用的条件。

在管理层面的意义上，量子优势有望成为推动近未来高科技可持续繁荣的一个重要里程碑。当前的高科技领域，无论是在学习策略和/或人工智能（AI）方面，均需要强大的算力来处理和存储数据。从全球绿色发展的角度来看，这一现状使其并非理想选择¹⁶。尽管机器学习/人工智能（ML/AI）使计算在经济效率上有所提升，但它并未提供根本性的分析解决方案，因为高效的计算是以高功耗的计算设施为代价实现的。因此，它们本质上受限于高性能计算机（HPC）。量子计算彻底改变了传统计算范式，已在多个实际试验应用中证明其计算速度超越传统计算机^17...

材料

本文使用的材料清单

姓名	公司	目录编号	评论
戴尔笔记本电脑	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