无线自组织量子通信网络的Grover路由算法研究

，

(浙江工业大学 信息工程学院，浙江 杭州 310023)

随着对量子通信研究的不断深入，量子通信网络的发展也在快速的进行.2008年欧洲联合小组在维也纳建立了量子安全通信网络[1].在我国，2007年中国科学技术大学实现了基于波分复用的四用户量子通信网络[2].以上量子通信网络的建立验证了构建量子通信网络的可行性，但其中大部分为有线量子通信网络，复杂结构的无线量子通信网络尚处于理论研究阶段.2005年Cheng等首次提出了无线量子通信网络中的量子路由机制[3]，首次在量子领域内对无线通信问题进行了研究，但并未涉及路由的选择方面的研究.2012年余旭涛等对无线自组织量子通信网络的模型与路由协议进行了研究[4]，提出了适用于复杂的无线自组织量子通信网络的按需路由协议，并在路由寻找成功后采用两端逼近的方法建立量子信道，首次对量子领域内无线通信网的路由选择和建立进行了研究，但该协议在寻找路由时采用了洪泛的方法，容易造成网络资源的浪费，增加不必要的转发，这是本文着重要解决的问题.在研究了Ad Hoc网络路由[5]和量子通信的特点后，笔者在无线自组织量子通信网络的路由查找中结合Grover量子搜索算法，在保证了路由建立成功率和纠缠量子对数目的基础上减少了网络计算量，节省了网络资源，使路由快速收敛.

1 无线自组织量子通信网络中量子信道的建立

(1)

图1 量子信道的建立过程

2 运用Grover算法寻找路由

Grover量子搜索算法通过一系列的幺正变换，使得原来相等的各量子基态的概率幅发生改变，从而在对量子态的测量中能以较大的概率得到正确的解[6-7].每次Grover迭代运算可分解为两个步骤，首先将目标解的态相位旋转π弧度，从而达到标记解径的目的，然后通过与概率扩散矩阵相乘重新分配概率，将非解集上的概率幅转移到解集上去[8].

由于采用量子隐形传态来传递信息，需要消耗纠缠量子对，使得纠缠量子对成为网络资源.为避免因纠缠量子对的消耗而导致的量子信道断开，路由算法将纠缠量子对数目作为路由度量，而不用传统路由中的跳数作为路由度量[4]，以保证建立的路由路径的纠缠量子对数目尽量多.路由度量表示为

P=minNj1≤j≤n-1

(2)

式中：P为路由度量；n为一条路径中的节点数；Nj为路径上第j跳所对应的两节点间的纠缠量子对数目.

在无线自组织量子通信网络中，节点i和节点j之间的距离表示为dij.量子态测量结果传递需要使用无线信道，我们称两节点间能正确接收信号的最大距离为最大有效距离R.由N个节点构成的无线自组织量子通信网可以构成一个N×N的邻接矩阵A=(aij)N×N，其元素应满足如下关系式：

(3)

两节点间的纠缠量子对数目记为numij，根据邻接矩阵可以构建N×N的操作矩阵U，网络中的任意一个节点i都维护一个操作矩阵Ui=(uimn)N×N，其元素应满足如下关系式:

(4)

uimn为负数表示两节点间同时拥有无线信道和量子信道，节点m是下一跳的解径之一.为了避免产生环路，路径上已被搜索过的节点都被记录下来，不会作为下一跳的解径.

概率扩散矩阵D的作用是放大解径的概率、缩小非解径的概率，使路由搜索快速收敛，其构建方法参考文献[9].

(5)

由于操作矩阵不是单位矩阵，故得到的概率矢量要进行归一化处理.经过上式计算，解径的概率被放大，非解径的概率被减小，最终将以最大的概率可能性得到我们所需要的路由.

3 仿真实验

路由建立的流程如图2所示.

图2 路由建立流程图

采用MATLAB构建网络进行仿真，在一个1 000 m×1 000 m的无线自组织量子通信网络中随机散布着100个节点，任意两节点间的无线信道都是双向的，可通信范围为150 m，且在通信范围内的任意两节点都拥有纠缠量子对，数目为100到200间的随机整数.

图3 不同节点选择概率下的路由建立成功率

在无线自组织量子通信网络中，将Grover算法建立路由和文献[4]中建立路由的方法进行比较.在相同的网络环境下，发起1 800次路由寻找，文献[4]中方法建立路由成功率为92%，Grover算法建立路由成功率为89%.图3展示了使用Grover算法在不同的转发选择概率下路由建立的成功率.定义计算量为转发路由请求的节点数目，使用Grover搜索算法可以减少网络计算量.图4是两种算法的计算量之比.

图4 两种算法的计算量之比

笔者对给定空间内不同节点数对路由建立的成功率的影响做了研究，仿真的背景条件是1 000 m×1 000 m的无线自组织量子通信网络，可通信范围为150 m.仿真结果如图5所示.图6为在给定空间内，节点数分别为50和150的情况下，纠缠量子对数目对路由性能的影响.其中较少的范围定义为(0,100)，中等的范围定义为(100,200)，较多的范围定义为(200,300).由于节点间的纠缠量子对数目直接影响了路由的建立和通信时交换信息的多少，所以路由性能由路由建立后的最小度量来表示.

图5 不同节点密度下的路由建立成功率

图6 纠缠量子对数目对路由性能的影响

4 结 论

定义计算量为转发路由请求的节点数目，对于所有成功建立路由的情况，两种方法建立的路由所对应的路由度量基本相等.就是说使用Grover搜索算法来寻找建立路由，能够在保证建立成功率和路由度量的前提下降低网络计算量，弥补已有算法的不足.从仿真结果可以看出，节点密度较大时，路由建立的成功率也相应升高，节点间纠缠量子对越多，路由的性能也会越好.

参考文献：

[1] PEEV M, PACHER C, ALLEAUME R, et al. The SECOQC quantum key distribution network in Vienna[J]. New Journal of Physics,2009,11(7):075001.

[2] CHEN Teng-yun, LIANG Hao, LIU Yang, et al. Field test of a practical secure communication network with decoy-state quantum cryptography[J]. Optics express,2009,17(8):6540-6549.

[3] 许方星,陈巍,王双,等.多层级量子密码城域网[J].科学通报,2009(16):2277-2283.

[4] 余旭涛,徐进,张在琛.基于量子远程传态的无线自组织量子通信网络路由协议[J].物理学报,2012,61(22):62-69.

[5] 陈迪,孟利民.无线Ad Hoc网络中的多目标规划路由算法研究[J].浙江工业大学学报,2009,37(4):441-444.

[6] ANASTASI G, CONTI M, GREGORI E, et al. An energy-efficient protocol for multimedia streaming in a mobile environment[J]. International Journal of Pervasive Computing and Communications,2005,1(4):301-312.

[7] 孙吉贵,何雨果.量子搜索算法[J].软件学报,2003,14(3):334-344.

[8] 孟利民,周凯,沈鑫宇,等.基于Grover搜索思想的无线自组网络路由算法研究[J].传感技术学报,2010,23(2):251-255.

[9] 邬学军,孟利民,华惊宇,等.基于能量控制的无线传感网络最优化算法研究[J].传感技术学报,2011,24(3):436-439.