無線自組織量子通信網(wǎng)絡(luò)的Grover路由算法研究

，

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

隨著對(duì)量子通信研究的不斷深入，量子通信網(wǎng)絡(luò)的發(fā)展也在快速的進(jìn)行.2008年歐洲聯(lián)合小組在維也納建立了量子安全通信網(wǎng)絡(luò)[1].在我國，2007年中國科學(xué)技術(shù)大學(xué)實(shí)現(xiàn)了基于波分復(fù)用的四用戶量子通信網(wǎng)絡(luò)[2].以上量子通信網(wǎng)絡(luò)的建立驗(yàn)證了構(gòu)建量子通信網(wǎng)絡(luò)的可行性，但其中大部分為有線量子通信網(wǎng)絡(luò)，復(fù)雜結(jié)構(gòu)的無線量子通信網(wǎng)絡(luò)尚處于理論研究階段.2005年Cheng等首次提出了無線量子通信網(wǎng)絡(luò)中的量子路由機(jī)制[3]，首次在量子領(lǐng)域內(nèi)對(duì)無線通信問題進(jìn)行了研究，但并未涉及路由的選擇方面的研究.2012年余旭濤等對(duì)無線自組織量子通信網(wǎng)絡(luò)的模型與路由協(xié)議進(jìn)行了研究[4]，提出了適用于復(fù)雜的無線自組織量子通信網(wǎng)絡(luò)的按需路由協(xié)議，并在路由尋找成功后采用兩端逼近的方法建立量子信道，首次對(duì)量子領(lǐng)域內(nèi)無線通信網(wǎng)的路由選擇和建立進(jìn)行了研究，但該協(xié)議在尋找路由時(shí)采用了洪泛的方法，容易造成網(wǎng)絡(luò)資源的浪費(fèi)，增加不必要的轉(zhuǎn)發(fā)，這是本文著重要解決的問題.在研究了Ad Hoc網(wǎng)絡(luò)路由[5]和量子通信的特點(diǎn)后，筆者在無線自組織量子通信網(wǎng)絡(luò)的路由查找中結(jié)合Grover量子搜索算法，在保證了路由建立成功率和糾纏量子對(duì)數(shù)目的基礎(chǔ)上減少了網(wǎng)絡(luò)計(jì)算量，節(jié)省了網(wǎng)絡(luò)資源，使路由快速收斂.

1 無線自組織量子通信網(wǎng)絡(luò)中量子信道的建立

(1)

圖1 量子信道的建立過程

2 運(yùn)用Grover算法尋找路由

Grover量子搜索算法通過一系列的幺正變換，使得原來相等的各量子基態(tài)的概率幅發(fā)生改變，從而在對(duì)量子態(tài)的測(cè)量中能以較大的概率得到正確的解[6-7].每次Grover迭代運(yùn)算可分解為兩個(gè)步驟，首先將目標(biāo)解的態(tài)相位旋轉(zhuǎn)π弧度，從而達(dá)到標(biāo)記解徑的目的，然后通過與概率擴(kuò)散矩陣相乘重新分配概率，將非解集上的概率幅轉(zhuǎn)移到解集上去[8].

由于采用量子隱形傳態(tài)來傳遞信息，需要消耗糾纏量子對(duì)，使得糾纏量子對(duì)成為網(wǎng)絡(luò)資源.為避免因糾纏量子對(duì)的消耗而導(dǎo)致的量子信道斷開，路由算法將糾纏量子對(duì)數(shù)目作為路由度量，而不用傳統(tǒng)路由中的跳數(shù)作為路由度量[4]，以保證建立的路由路徑的糾纏量子對(duì)數(shù)目盡量多.路由度量表示為

P=minNj1≤j≤n-1

(2)

式中：P為路由度量；n為一條路徑中的節(jié)點(diǎn)數(shù)；Nj為路徑上第j跳所對(duì)應(yīng)的兩節(jié)點(diǎn)間的糾纏量子對(duì)數(shù)目.

在無線自組織量子通信網(wǎng)絡(luò)中，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離表示為dij.量子態(tài)測(cè)量結(jié)果傳遞需要使用無線信道，我們稱兩節(jié)點(diǎn)間能正確接收信號(hào)的最大距離為最大有效距離R.由N個(gè)節(jié)點(diǎn)構(gòu)成的無線自組織量子通信網(wǎng)可以構(gòu)成一個(gè)N×N的鄰接矩陣A=(aij)N×N，其元素應(yīng)滿足如下關(guān)系式：

(3)

兩節(jié)點(diǎn)間的糾纏量子對(duì)數(shù)目記為numij，根據(jù)鄰接矩陣可以構(gòu)建N×N的操作矩陣U，網(wǎng)絡(luò)中的任意一個(gè)節(jié)點(diǎn)i都維護(hù)一個(gè)操作矩陣Ui=(uimn)N×N，其元素應(yīng)滿足如下關(guān)系式:

(4)

uimn為負(fù)數(shù)表示兩節(jié)點(diǎn)間同時(shí)擁有無線信道和量子信道，節(jié)點(diǎn)m是下一跳的解徑之一.為了避免產(chǎn)生環(huán)路，路徑上已被搜索過的節(jié)點(diǎn)都被記錄下來，不會(huì)作為下一跳的解徑.

概率擴(kuò)散矩陣D的作用是放大解徑的概率、縮小非解徑的概率，使路由搜索快速收斂，其構(gòu)建方法參考文獻(xiàn)[9].

(5)

由于操作矩陣不是單位矩陣，故得到的概率矢量要進(jìn)行歸一化處理.經(jīng)過上式計(jì)算，解徑的概率被放大，非解徑的概率被減小，最終將以最大的概率可能性得到我們所需要的路由.

3 仿真實(shí)驗(yàn)

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

圖2 路由建立流程圖

采用MATLAB構(gòu)建網(wǎng)絡(luò)進(jìn)行仿真，在一個(gè)1 000 m×1 000 m的無線自組織量子通信網(wǎng)絡(luò)中隨機(jī)散布著100個(gè)節(jié)點(diǎn)，任意兩節(jié)點(diǎn)間的無線信道都是雙向的，可通信范圍為150 m，且在通信范圍內(nèi)的任意兩節(jié)點(diǎn)都擁有糾纏量子對(duì)，數(shù)目為100到200間的隨機(jī)整數(shù).

圖3 不同節(jié)點(diǎn)選擇概率下的路由建立成功率

在無線自組織量子通信網(wǎng)絡(luò)中，將Grover算法建立路由和文獻(xiàn)[4]中建立路由的方法進(jìn)行比較.在相同的網(wǎng)絡(luò)環(huán)境下，發(fā)起1 800次路由尋找，文獻(xiàn)[4]中方法建立路由成功率為92%，Grover算法建立路由成功率為89%.圖3展示了使用Grover算法在不同的轉(zhuǎn)發(fā)選擇概率下路由建立的成功率.定義計(jì)算量為轉(zhuǎn)發(fā)路由請(qǐng)求的節(jié)點(diǎn)數(shù)目，使用Grover搜索算法可以減少網(wǎng)絡(luò)計(jì)算量.圖4是兩種算法的計(jì)算量之比.

圖4 兩種算法的計(jì)算量之比

筆者對(duì)給定空間內(nèi)不同節(jié)點(diǎn)數(shù)對(duì)路由建立的成功率的影響做了研究，仿真的背景條件是1 000 m×1 000 m的無線自組織量子通信網(wǎng)絡(luò)，可通信范圍為150 m.仿真結(jié)果如圖5所示.圖6為在給定空間內(nèi)，節(jié)點(diǎn)數(shù)分別為50和150的情況下，糾纏量子對(duì)數(shù)目對(duì)路由性能的影響.其中較少的范圍定義為(0,100)，中等的范圍定義為(100,200)，較多的范圍定義為(200,300).由于節(jié)點(diǎn)間的糾纏量子對(duì)數(shù)目直接影響了路由的建立和通信時(shí)交換信息的多少，所以路由性能由路由建立后的最小度量來表示.

圖5 不同節(jié)點(diǎn)密度下的路由建立成功率

圖6 糾纏量子對(duì)數(shù)目對(duì)路由性能的影響

4 結(jié) 論

定義計(jì)算量為轉(zhuǎn)發(fā)路由請(qǐng)求的節(jié)點(diǎn)數(shù)目，對(duì)于所有成功建立路由的情況，兩種方法建立的路由所對(duì)應(yīng)的路由度量基本相等.就是說使用Grover搜索算法來尋找建立路由，能夠在保證建立成功率和路由度量的前提下降低網(wǎng)絡(luò)計(jì)算量，彌補(bǔ)已有算法的不足.從仿真結(jié)果可以看出，節(jié)點(diǎn)密度較大時(shí)，路由建立的成功率也相應(yīng)升高，節(jié)點(diǎn)間糾纏量子對(duì)越多，路由的性能也會(huì)越好.

參考文獻(xiàn)：

[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í)量子密碼城域網(wǎng)[J].科學(xué)通報(bào),2009(16):2277-2283.

[4] 余旭濤,徐進(jìn),張?jiān)阼?基于量子遠(yuǎn)程傳態(tài)的無線自組織量子通信網(wǎng)絡(luò)路由協(xié)議[J].物理學(xué)報(bào),2012,61(22):62-69.

[5] 陳迪,孟利民.無線Ad Hoc網(wǎng)絡(luò)中的多目標(biāo)規(guī)劃路由算法研究[J].浙江工業(yè)大學(xué)學(xué)報(bào),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].軟件學(xué)報(bào),2003,14(3):334-344.

[8] 孟利民,周凱,沈鑫宇,等.基于Grover搜索思想的無線自組網(wǎng)絡(luò)路由算法研究[J].傳感技術(shù)學(xué)報(bào),2010,23(2):251-255.

[9] 鄔學(xué)軍,孟利民,華驚宇,等.基于能量控制的無線傳感網(wǎng)絡(luò)最優(yōu)化算法研究[J].傳感技術(shù)學(xué)報(bào),2011,24(3):436-439.