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

劉永廣

(1.廣東輕工職業(yè)技術(shù)學(xué)院，廣東 廣州 510300；2.中國電子科技集團(tuán)第七研究所， 廣東 廣州 510310)

?

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

劉永廣1,2

(1.廣東輕工職業(yè)技術(shù)學(xué)院，廣東 廣州 510300；2.中國電子科技集團(tuán)第七研究所， 廣東 廣州 510310)

尋找滿足多約束條件的QoS路由是網(wǎng)絡(luò)業(yè)務(wù)能否順利實(shí)施的關(guān)鍵，在研究和分析了當(dāng)前多種典型相關(guān)算法的基礎(chǔ)上，提出了一種基于Grover量子搜索思想的多約束路由算法。算法對(duì)路徑采用了非線性路徑長度的度量方法，分析了Grover搜索的特點(diǎn)和優(yōu)勢(shì)，根據(jù)Grover迭代的實(shí)現(xiàn)過程構(gòu)建了操作矩陣和概率擴(kuò)散矩陣，通過選擇高概率的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。仿真表明，該算法在最短路徑獲取和路由發(fā)現(xiàn)成功率方面都有高效的表現(xiàn)。

Grover搜索；多約束；路由

0 引 言

在下一代通信網(wǎng)絡(luò)中，QoS保障作為通信網(wǎng)絡(luò)的重要特征之一，是突破互聯(lián)網(wǎng)發(fā)展瓶頸的關(guān)鍵。由于尋找滿足多種度量的QoS最優(yōu)路由問題被證明是NP完全問題[1]，因此給實(shí)際應(yīng)用帶來難度，引起了廣泛的研究。目前對(duì)該類問題的研究算法主要集中在3個(gè)方向[2]：確定性算法、啟發(fā)式算法以及優(yōu)化算法。文獻(xiàn)[3-4]是典型的確切性算法，算法的特點(diǎn)是當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，給算法的應(yīng)用帶來困難，比如文獻(xiàn)[3]在最壞情況下k值會(huì)呈指數(shù)增長，所以k值的大小對(duì)該算法的復(fù)雜度起著決定性的影響，甚至使該算法失去使用價(jià)值。考慮了確定性算法的這些缺點(diǎn)，文獻(xiàn)[5-7]中提出的啟發(fā)式算法在多項(xiàng)式計(jì)算時(shí)間內(nèi)近似逼近最優(yōu)解，如文獻(xiàn)[5]在搜索的路徑的過程中會(huì)隨機(jī)決策，避免一些無法預(yù)料的陷阱，文獻(xiàn)[6]則采用了非線性路徑長度來發(fā)現(xiàn)滿足約束的路徑，并尋找一條近似最短的路徑以獲得近似最優(yōu)路徑。文獻(xiàn)[8-11]則是把當(dāng)前一些主流優(yōu)化算法和該NP難問題結(jié)合來進(jìn)行研究，希望獲得最優(yōu)解，如蟻群算法[8-9]、神經(jīng)網(wǎng)絡(luò)[10]、遺傳算法[11]等。這些算法的優(yōu)點(diǎn)是提高了路由發(fā)現(xiàn)的成功率，缺點(diǎn)是所要設(shè)置的參數(shù)較多，且參數(shù)隨機(jī)性強(qiáng)，計(jì)算量較大，給實(shí)際應(yīng)用帶來不便。

為了降低算法的運(yùn)算復(fù)雜度，把NP復(fù)雜度減低到多項(xiàng)式時(shí)間，本研究把Grover量子搜索算法[12]引入到最優(yōu)路徑搜尋中來，收到較好的效果。

1 算法理論基礎(chǔ)

關(guān)于多約束路徑問題的描述，包括MCP(Multi-constrained Path)問題和MCOP(Multi-constrained Optimal Path)問題，在上述部分的文獻(xiàn)里都有相同的定義，在此不再贅述。本文要解決的是存在多條滿足多約束的路徑的情況下，怎樣獲得最優(yōu)的一條路徑的問題，即MCOP問題。針對(duì)多個(gè)約束條件，需要給出一個(gè)路徑的度量標(biāo)準(zhǔn)，為此，文獻(xiàn)[6]給出了一種非線性路徑長度來降低MCOP問題的復(fù)雜度，該路徑長度表示如下：

(1)

式中，ci—第i個(gè)約束；wi(p)—路徑p的第i個(gè)權(quán)重；q—Holder范式的向量維數(shù)。特別地，當(dāng)q→時(shí)，

l

(2)

則本文的研究就是在源和目的間找到一條滿足所有約束的路徑，并且使式(2)的值最小，即找到一條路徑p∈P：

(3)

于是MCOP問題就轉(zhuǎn)化成一個(gè)Max-Min問題，由于該路徑長度是非加性的，無法用傳統(tǒng)的Dijkstra算法來求解，必須用啟發(fā)式算法或更高效的搜索技術(shù)來求解。

2 Grover搜索算法

Grover算法[12]在量子計(jì)算中有著很重要的地位，它適合于對(duì)無序數(shù)據(jù)集進(jìn)行搜索。依靠量子并行計(jì)算的優(yōu)勢(shì)，在遍歷搜索中可以減少搜索的運(yùn)算次數(shù)。量子Grover搜索算法自誕生以來，一直受到國內(nèi)外學(xué)者的關(guān)注和研究，并被應(yīng)用于解決一些NP難問題，如旅行商問題和背包問題[13]。文獻(xiàn)[14]分析了傳統(tǒng)搜索算法和量子搜索算法在路徑搜索上的區(qū)別，并給出了應(yīng)用到路由搜索中的步驟：

(1)對(duì)集合中的無序元素，用一個(gè)等概率幅的量子組合來表示，系統(tǒng)的初始態(tài)為：

(4)

(2)通過量子態(tài)的幺正變換，對(duì)每個(gè)量子基態(tài)進(jìn)行運(yùn)算，使得原來相同的概率幅發(fā)生不同改變，從而對(duì)變化后的量子態(tài)進(jìn)行測(cè)量以較大概率得到正確解。

因此，每次Grover迭代過程包括兩次變換，第一次使所要查找的態(tài)相位旋轉(zhuǎn)180度，用于標(biāo)注目標(biāo)解。第二次通過概率擴(kuò)散矩陣將該解的概率放大，同時(shí)將非解概率縮小。

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

首先在源節(jié)點(diǎn)構(gòu)建一個(gè)網(wǎng)絡(luò)拓?fù)渚仃嘇：

(5)

將 Grover 搜索算法引入到移動(dòng)自組網(wǎng)的路由選擇中，關(guān)鍵是將Grover 算子引入到路由選擇中，根據(jù)式(5)中的鄰接矩陣可以構(gòu)造操作矩陣U，該矩陣的作用就是標(biāo)注目標(biāo)解，使概率幅發(fā)生改變，根據(jù)式(3)的最小化優(yōu)化目標(biāo)，則節(jié)點(diǎn)i的該操作矩陣構(gòu)造如下：

(6)

式中，wk(p)—當(dāng)前路徑p在第k個(gè)約束上的路徑權(quán)重；wk(i,m)—節(jié)點(diǎn)m和i之間鏈路第k個(gè)約束上的權(quán)重；ck—第k個(gè)約束； Aim—拓?fù)渚仃嚨趇行m列元素的值。

此外，需要構(gòu)造概率擴(kuò)散矩陣D，該矩陣構(gòu)造如下：

(7)

設(shè)計(jì)了操作矩陣和概率擴(kuò)散矩陣后，網(wǎng)關(guān)節(jié)點(diǎn)即可構(gòu)建到各個(gè)請(qǐng)求節(jié)點(diǎn)的路徑，以下是求解過程。

(1)初始化：

通過式(6)和式(7)構(gòu)造U和D，對(duì)于有N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，設(shè)定每個(gè)節(jié)點(diǎn)在初始時(shí)被搜索到的概率相等，則構(gòu)造初始概率幅矩陣為：

(2)進(jìn)行Grover迭代：

按照Grover算法理論[12]，通過N次迭代，計(jì)算出下一跳節(jié)點(diǎn)的概率幅矩陣，并按照一定概率選擇下一跳節(jié)點(diǎn)，本研究中選擇概率較大的前50%作為下一跳節(jié)點(diǎn)。

(3)若所得下一跳節(jié)點(diǎn)v為目的節(jié)點(diǎn)：

1)如果沒有到該節(jié)點(diǎn)的路徑，則保存當(dāng)前路徑p并獲得當(dāng)前路徑長度l(p)。

2)如果已保存有到目的地的前路徑p，則比較當(dāng)前路徑的路徑長度l(p′)和l(p)的大小，如果l(p′)

(4)若所得下一跳節(jié)點(diǎn)v不為目的節(jié)點(diǎn)：

并轉(zhuǎn)到2)。

(5)若計(jì)算結(jié)束，則輸出路徑p。

4 算法仿真和性能評(píng)估

在這一部分，通過仿真對(duì)本文的基于Grover搜索的多約束路由算法(GS_MCOP)和兩種同類算法進(jìn)行比較，對(duì)性能進(jìn)行評(píng)估。

參與比較的一種是文獻(xiàn)[6]中的啟發(fā)式算法H_MCOP，另一種是文獻(xiàn)[8]中采用了蟻群優(yōu)化算法的ANT_MCOP算法。為便于比較，仿真網(wǎng)絡(luò)的拓?fù)?、每條邊的權(quán)重和兩個(gè)約束的產(chǎn)生均使用文獻(xiàn)[6]中的模型來進(jìn)行。在整個(gè)模型中，拓?fù)洳捎玫氖荳axman網(wǎng)絡(luò)模型，在一個(gè)矩形區(qū)域內(nèi)隨機(jī)的產(chǎn)生需要的節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)之間存在連接的概率用下式來表示：

(8)

式中，d(u,v)—節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的距離；L—所有節(jié)點(diǎn)間的最大長度；α,β—介于(0,1]之間的數(shù)。

對(duì)于每個(gè)有連接的邊使用了兩個(gè)不相關(guān)的權(quán)重：w1(u,v)～uniform(1,100)和w2(u,v)～uniform(1,200)。根據(jù)邊的權(quán)重，產(chǎn)生如下兩個(gè)隨機(jī)的路徑約束c1～uniform(0.8×w1(p2)，1.2×w1(p2))和c2～uniform(0.8×w2(p1),1.2×w2(p1))。其中p1、p2是分別以w1和w2作為權(quán)重采用Dijkstra算法求得的最短路徑。則w1(p2)指的是在p2這條路徑上權(quán)重w1的和，w2(p1)指的是在p1這條路徑上權(quán)重w2的和。

在仿真中每一種場景產(chǎn)生不同的節(jié)點(diǎn)數(shù)，在每個(gè)場景中隨機(jī)產(chǎn)生100個(gè)源和目的間的路由請(qǐng)求。圖1和圖2是在兩個(gè)約束條件下對(duì)路由成功率和路徑長度(式(2))進(jìn)行比較的結(jié)果，可以看出，本文的算法在路由成功率方面有更好的表現(xiàn)，并且獲得的路徑長度也最小。

在上述仿真條件下，固定節(jié)點(diǎn)個(gè)數(shù)，變化約束個(gè)數(shù)來觀察算法的性能。圖3是100個(gè)節(jié)點(diǎn)的場景下不同約束個(gè)數(shù)時(shí)算法性能的一個(gè)比較，可以看出，約束個(gè)數(shù)增加時(shí)，算法的性能均有所下降，但本文提出的算法在約個(gè)個(gè)數(shù)增加時(shí)依然保持更好的性能。

圖1 兩個(gè)約束條件下路由成功率的比較

圖2 兩個(gè)約束條件下路徑長度的比較

圖3 多個(gè)約束條件下路由成功率的比較

5 結(jié) 語

針對(duì)多約束條件下路由選擇的NP難特點(diǎn)，本文提出了一種基于Grover搜索算法的多約束路由算法，算法根據(jù)Grover搜索的特點(diǎn)構(gòu)建了操作矩陣和概率擴(kuò)散矩陣，并依據(jù)迭代結(jié)果選擇概率幅大的節(jié)點(diǎn)進(jìn)行路由選擇，由于量子搜索的并行計(jì)算特性，提高了滿足條件可行解的搜索范圍和搜索效率，能以更大概率獲得最優(yōu)解。和同類算法相比較，算法運(yùn)行中涉及的不確定性參數(shù)較少，增加了算法的普適性和實(shí)用性。仿真結(jié)果也表明，該算法可以有效的減小所選路徑的長度，提高成功選路的次數(shù)。

[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]. 通信技術(shù), 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] 亓?xí)x,張順頤,孫雁飛等.基于自主蟻群算法的認(rèn)知網(wǎng)絡(luò)多約束QoS路由算法[J].南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版,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] 聶仁燦,周冬明,趙東風(fēng)等.競爭型脈沖耦合神經(jīng)網(wǎng)絡(luò)及用于多約束QoS路由求解[J].通信學(xué)報(bào), 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路由的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究,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ì)算算法[J].計(jì)算機(jī)工程與應(yīng)用, 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—)，男，博士，研究員，主要研究方向?yàn)樾畔⒕W(wǎng)絡(luò)理論與技術(shù)、路由算法及優(yōu)化等。