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

2015-02-24 03:25:54劉永廣

通信技術 2015年5期

劉永廣

(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→時，

(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

1002-0802(2015)05-0594-04