基于Grover搜索的多约束路由算法*

刘永广

(1.广东轻工职业技术学院，广东 广州 510300；2.中国电子科技集团第七研究所， 广东 广州 510310)



基于Grover搜索的多约束路由算法*

刘永广1,2

(1.广东轻工职业技术学院，广东 广州 510300；2.中国电子科技集团第七研究所， 广东 广州 510310)

寻找满足多约束条件的QoS路由是网络业务能否顺利实施的关键，在研究和分析了当前多种典型相关算法的基础上，提出了一种基于Grover量子搜索思想的多约束路由算法。算法对路径采用了非线性路径长度的度量方法，分析了Grover搜索的特点和优势，根据Grover迭代的实现过程构建了操作矩阵和概率扩散矩阵，通过选择高概率的节点进行数据转发。仿真表明，该算法在最短路径获取和路由发现成功率方面都有高效的表现。

Grover搜索；多约束；路由

0 引 言

在下一代通信网络中，QoS保障作为通信网络的重要特征之一，是突破互联网发展瓶颈的关键。由于寻找满足多种度量的QoS最优路由问题被证明是NP完全问题[1]，因此给实际应用带来难度，引起了广泛的研究。目前对该类问题的研究算法主要集中在3个方向[2]：确定性算法、启发式算法以及优化算法。文献[3-4]是典型的确切性算法，算法的特点是当网络规模较大时，给算法的应用带来困难，比如文献[3]在最坏情况下k值会呈指数增长，所以k值的大小对该算法的复杂度起着决定性的影响，甚至使该算法失去使用价值。考虑了确定性算法的这些缺点，文献[5-7]中提出的启发式算法在多项式计算时间内近似逼近最优解，如文献[5]在搜索的路径的过程中会随机决策，避免一些无法预料的陷阱，文献[6]则采用了非线性路径长度来发现满足约束的路径，并寻找一条近似最短的路径以获得近似最优路径。文献[8-11]则是把当前一些主流优化算法和该NP难问题结合来进行研究，希望获得最优解，如蚁群算法[8-9]、神经网络[10]、遗传算法[11]等。这些算法的优点是提高了路由发现的成功率，缺点是所要设置的参数较多，且参数随机性强，计算量较大，给实际应用带来不便。

为了降低算法的运算复杂度，把NP复杂度减低到多项式时间，本研究把Grover量子搜索算法[12]引入到最优路径搜寻中来，收到较好的效果。

1 算法理论基础

关于多约束路径问题的描述，包括MCP(Multi-constrained Path)问题和MCOP(Multi-constrained Optimal Path)问题，在上述部分的文献里都有相同的定义，在此不再赘述。本文要解决的是存在多条满足多约束的路径的情况下，怎样获得最优的一条路径的问题，即MCOP问题。针对多个约束条件，需要给出一个路径的度量标准，为此，文献[6]给出了一种非线性路径长度来降低MCOP问题的复杂度，该路径长度表示如下：

(1)

式中，ci—第i个约束；wi(p)—路径p的第i个权重；q—Holder范式的向量维数。特别地，当q→时，

l

(2)

则本文的研究就是在源和目的间找到一条满足所有约束的路径，并且使式(2)的值最小，即找到一条路径p∈P：

(3)

于是MCOP问题就转化成一个Max-Min问题，由于该路径长度是非加性的，无法用传统的Dijkstra算法来求解，必须用启发式算法或更高效的搜索技术来求解。

2 Grover搜索算法

Grover算法[12]在量子计算中有着很重要的地位，它适合于对无序数据集进行搜索。依靠量子并行计算的优势，在遍历搜索中可以减少搜索的运算次数。量子Grover搜索算法自诞生以来，一直受到国内外学者的关注和研究，并被应用于解决一些NP难问题，如旅行商问题和背包问题[13]。文献[14]分析了传统搜索算法和量子搜索算法在路径搜索上的区别，并给出了应用到路由搜索中的步骤：

(1)对集合中的无序元素，用一个等概率幅的量子组合来表示，系统的初始态为：

(4)

(2)通过量子态的幺正变换，对每个量子基态进行运算，使得原来相同的概率幅发生不同改变，从而对变化后的量子态进行测量以较大概率得到正确解。

因此，每次Grover迭代过程包括两次变换，第一次使所要查找的态相位旋转180度，用于标注目标解。第二次通过概率扩散矩阵将该解的概率放大，同时将非解概率缩小。

3 基于Grover搜索的多约束路由算法

首先在源节点构建一个网络拓扑矩阵A：

(5)

将 Grover 搜索算法引入到移动自组网的路由选择中，关键是将Grover 算子引入到路由选择中，根据式(5)中的邻接矩阵可以构造操作矩阵U，该矩阵的作用就是标注目标解，使概率幅发生改变，根据式(3)的最小化优化目标，则节点i的该操作矩阵构造如下：

(6)

式中，wk(p)—当前路径p在第k个约束上的路径权重；wk(i,m)—节点m和i之间链路第k个约束上的权重；ck—第k个约束； Aim—拓扑矩阵第i行m列元素的值。

此外，需要构造概率扩散矩阵D，该矩阵构造如下：

(7)

设计了操作矩阵和概率扩散矩阵后，网关节点即可构建到各个请求节点的路径，以下是求解过程。

(1)初始化：

通过式(6)和式(7)构造U和D，对于有N个节点的网络，设定每个节点在初始时被搜索到的概率相等，则构造初始概率幅矩阵为：

(2)进行Grover迭代：

按照Grover算法理论[12]，通过N次迭代，计算出下一跳节点的概率幅矩阵，并按照一定概率选择下一跳节点，本研究中选择概率较大的前50%作为下一跳节点。

(3)若所得下一跳节点v为目的节点：

1)如果没有到该节点的路径，则保存当前路径p并获得当前路径长度l(p)。

2)如果已保存有到目的地的前路径p，则比较当前路径的路径长度l(p′)和l(p)的大小，如果l(p′)

(4)若所得下一跳节点v不为目的节点：

并转到2)。

(5)若计算结束，则输出路径p。

4 算法仿真和性能评估

在这一部分，通过仿真对本文的基于Grover搜索的多约束路由算法(GS_MCOP)和两种同类算法进行比较，对性能进行评估。

参与比较的一种是文献[6]中的启发式算法H_MCOP，另一种是文献[8]中采用了蚁群优化算法的ANT_MCOP算法。为便于比较，仿真网络的拓扑、每条边的权重和两个约束的产生均使用文献[6]中的模型来进行。在整个模型中，拓扑采用的是Waxman网络模型，在一个矩形区域内随机的产生需要的节点数，节点之间存在连接的概率用下式来表示：

(8)

式中，d(u,v)—节点u和节点v之间的距离；L—所有节点间的最大长度；α,β—介于(0,1]之间的数。

对于每个有连接的边使用了两个不相关的权重：w1(u,v)～uniform(1,100)和w2(u,v)～uniform(1,200)。根据边的权重，产生如下两个随机的路径约束c1～uniform(0.8×w1(p2)，1.2×w1(p2))和c2～uniform(0.8×w2(p1),1.2×w2(p1))。其中p1、p2是分别以w1和w2作为权重采用Dijkstra算法求得的最短路径。则w1(p2)指的是在p2这条路径上权重w1的和，w2(p1)指的是在p1这条路径上权重w2的和。

在仿真中每一种场景产生不同的节点数，在每个场景中随机产生100个源和目的间的路由请求。图1和图2是在两个约束条件下对路由成功率和路径长度(式(2))进行比较的结果，可以看出，本文的算法在路由成功率方面有更好的表现，并且获得的路径长度也最小。

在上述仿真条件下，固定节点个数，变化约束个数来观察算法的性能。图3是100个节点的场景下不同约束个数时算法性能的一个比较，可以看出，约束个数增加时，算法的性能均有所下降，但本文提出的算法在约个个数增加时依然保持更好的性能。

图1 两个约束条件下路由成功率的比较

图2 两个约束条件下路径长度的比较

图3 多个约束条件下路由成功率的比较

5 结 语

针对多约束条件下路由选择的NP难特点，本文提出了一种基于Grover搜索算法的多约束路由算法，算法根据Grover搜索的特点构建了操作矩阵和概率扩散矩阵，并依据迭代结果选择概率幅大的节点进行路由选择，由于量子搜索的并行计算特性，提高了满足条件可行解的搜索范围和搜索效率，能以更大概率获得最优解。和同类算法相比较，算法运行中涉及的不确定性参数较少，增加了算法的普适性和实用性。仿真结果也表明，该算法可以有效的减小所选路径的长度，提高成功选路的次数。

[1] WANG Z, Crowcroft J. Quality-of-Service Routing for Supporting Multimedia Applications[J]. IEEE J.Select. Areas Commun, 1996, 14(7):1228-1234.

[2] HUANG J, Tanaka Y. QoS RoutingAlgorithms using Fully Polynomial Time Approximation Scheme[C]// International Workshop on Quality of Service(IWQoS 2011). New York: IEEE Press, 2011:1-3.

[3] Mieghem P V, Fernando. Concepts of Exact QoS Routing Algorithms[J]. IEEE/ACM TRANSACTIONS ON NETWORKING, 2004, 12(5): 851-864.

[4] CHEN S, SONG M，Sahni S. Two Techniques for Fast Computation of Constrained Shortest Paths[J]. IEEE/ACM Transactions on Networking, 2008, 16(1):105-115.

[5] Korkmaz T, Krunz M. A Randomized Algorithm for Finding a Path Subject to Multiple QoS Requirements[J]. Computer Networks, 2001, 36(2-3): 251-268.

[6] Korkmaz T, Krunz M. Multi-Constrained Optimal Path Selection[C]// IEEE INFOCOM’2001. New York:IEEE Press 2001: 834-843.

[7] XUE G, ZHANG W, TANG J, et al. Polynomial Time Approximation Algorithms for Multi-Constrained QoS Routing[J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 656-669.

[8] 刘永广,叶梧,冯穗力.一种基于蚁群算法和非线性长度的多约束路由算法[J]. 通信技术, 2009, 42(08): 211-213. LIU Yong-guang, YE Wu, FENG Sui-li. A Multi-Constrained Routing Algorithm based on Ant Algorithm and Nonlinear Path Length[J]. Communications Technology, 2009, 42(08):211-213.

[9] 亓晋,张顺颐,孙雁飞等.基于自主蚁群算法的认知网络多约束QoS路由算法[J].南京邮电大学学报：自然科学版,2012,32(06):86-91. QI Jin, ZHANG Shun-yi, SUN Yan-fei, et al. Cognitive Networks Multi-Constrained QoS Routing Algorithm based on Autonomic Ant Colony Algorithm[J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science), 2012, 32(06):86-91.

[10] 聂仁灿,周冬明,赵东风等.竞争型脉冲耦合神经网络及用于多约束QoS路由求解[J].通信学报, 2010,31(01):65-72. NIE Ren-can,ZHOU Dong-ming, ZHAO Dong-feng, et al.CPCNN and Its Application to Multiple Constrained QoS Route[J]. Journal on Communications, 2010, 31(01):65-72.

[11] 方仕勇,邹恩,辛建涛等.新型混沌遗传算法在多约束QoS路由的应用[J].计算机应用研究,2012,29(08):3078-3080. FANG Shi-yong, ZOU En, XIN Jian-tao, et al. New Chaos Genetic Algorithm Applied in Multi-Constrained QoS Routing[J]. Application Research of Computers, 2012, 29(08):3078-3080.

[12] Grover L K. A Fast Quantum Mechanical Algorithm for Database Search [C]// The 28th Annual ACM Symposium on the Theory of Computing. NewYork: IEEE Press, 1996: 212-219.

[13] 钟普查, 鲍皖苏, 范得军等. 背包问题的量子计算算法[J].计算机工程与应用, 2009, 45(20): 63-64. ZHONG Pu-cha, BAO Wan-su, FAN De-jun, et al. Quantum Mechanical Algorithm to Solve Knapsack Problem[J]. Computer Engineering and Applications,2009,45(20):63-64.

[14] MENG L M, SONG W B. Routing Protocol based on Grover’s Searching Algorithm for Mobile Ad-Hoc Networks[J]. China Communications,2013,10(3):145-156.

A Multi-Constrained Routing Algorithm based on Grover Search

LIU Yong-guang1,2

(1. Guangdong Industry Technical College, Guangzhou Guangdong 510300, China;2. NO.7 Institute of CETC, Guangzhou Guangdong 510310, China)

To find a QoS route satisfying multi-constrained conditions is the key to realizing network business smoothly. Based on research and analysis of several classic algorithms, a multi-constrained routing algorithm based on Grover quantum search is proposed. This algorithm,with a measure of nonlinear path length, analyzes the features and advantages of Grover search, constructs operation matrix and probability diffusion matrix according to the implementaion process of Grover iteration, and transmits data by selecting the nodes with high probability. Simulations indicate that the proposed algorithm enjoys high-efficiency in terms of the shortest path acquisition and success ratio of route discovery.

grover search; multi-constrained; routing

10.3969/j.issn.1002-0802.2015.05.017

2014-12-19；

2015-03-02 Received date:2014-12-19；Revised date：2015-03-02

TP393

A

1002-0802(2015)05-0594-04

刘永广(1972—)，男，博士，研究员，主要研究方向为信息网络理论与技术、路由算法及优化等。