基于節(jié)點(diǎn)度的移動(dòng)自組網(wǎng)絡(luò)Grover路由算法研究*

盧 軍，鄔學(xué)軍，周 凱

(1.浙江工業(yè)大學(xué)之江學(xué)院理學(xué)系，杭州 310024;2.浙江工業(yè)大學(xué)理學(xué)院，杭州 310023)

移動(dòng)自組織網(wǎng)絡(luò)(Mobile ad hoc networks，MANET)是一種具有全新的信息獲取、信息處理與傳輸技術(shù)的通信網(wǎng)絡(luò)，通常包含大量的可自組織成多跳無線網(wǎng)絡(luò)的分布式節(jié)點(diǎn)［1］。MANET具有組網(wǎng)快捷、靈活、不受有線網(wǎng)絡(luò)約束等優(yōu)點(diǎn)，可用于緊急搜索、災(zāi)難救助、軍事、醫(yī)療等環(huán)境中，具有廣泛的應(yīng)用前景。MANET已經(jīng)引起了學(xué)術(shù)界和工業(yè)界的高度重視，被稱為是21世紀(jì)最有發(fā)展前景的技術(shù)之一［2］。作為網(wǎng)絡(luò)層的核心技術(shù)，如何設(shè)計(jì)MANET路由協(xié)議一直是近幾年專家學(xué)者致力研究的熱點(diǎn)問題。對(duì)于MANET這種特殊類型的移動(dòng)通信網(wǎng)絡(luò)而言，節(jié)點(diǎn)通常為筆記本電腦和無線電臺(tái)等便攜式通信設(shè)備。這些裝置雖然重量輕、移動(dòng)性好，但主要靠電池供電，由于電池的能量有限，因此節(jié)點(diǎn)的發(fā)射功率、傳輸距離和處理數(shù)據(jù)的能力都受到限制［3］。因此，在進(jìn)行網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)過程中必須要考慮到節(jié)電問題，以提高網(wǎng)絡(luò)的生存時(shí)間。

移動(dòng)自組織網(wǎng)絡(luò)環(huán)境下，節(jié)點(diǎn)間的無線鏈路及由此而形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨節(jié)點(diǎn)的位置分布和移動(dòng)、信道的變化等因素呈現(xiàn)出動(dòng)態(tài)變化的特性，移動(dòng)自組網(wǎng)絡(luò)的路由技術(shù)面臨挑戰(zhàn)。國(guó)內(nèi)研究無線傳感網(wǎng)絡(luò)最早從1999年開始，研究?jī)?nèi)容包括:無線傳感網(wǎng)絡(luò)多跳路由協(xié)議、廣播和組播協(xié)議、MAC協(xié)議改進(jìn)、無線傳感網(wǎng)絡(luò)的性能分析、網(wǎng)絡(luò)安全和QoS問題等等。QoS是指網(wǎng)絡(luò)為用戶提供的一組可以測(cè)量的預(yù)定義的服務(wù)參數(shù)，包括時(shí)延、帶寬、分組丟失率、能耗和服務(wù)覆蓋范圍等?；谝陨线@些路由協(xié)議的分析和比較，發(fā)現(xiàn)現(xiàn)有無線傳感網(wǎng)絡(luò)路由協(xié)議主要缺點(diǎn)是:分布式節(jié)點(diǎn)計(jì)算能力弱，無法保證在任何時(shí)候都能勝任服務(wù)器角色，節(jié)點(diǎn)計(jì)算不收斂;網(wǎng)絡(luò)延時(shí)大，節(jié)點(diǎn)計(jì)算和存儲(chǔ)量大。因此，研究一種新的、快速收斂的、實(shí)時(shí)性強(qiáng)的、網(wǎng)絡(luò)開銷少的、計(jì)算量小的路由算法一直是無線傳感網(wǎng)絡(luò)路由技術(shù)研究的熱點(diǎn)。

1 相關(guān)研究

MANET路由協(xié)議多是由傳統(tǒng)的距離矢量協(xié)議和鏈路狀態(tài)路由協(xié)議發(fā)展而來。為了適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，首先出現(xiàn)的是周期更新的路由協(xié)議。在這種路由協(xié)議中，每個(gè)節(jié)點(diǎn)維護(hù)一張包含到達(dá)其它節(jié)點(diǎn)的路由信息的路由表。當(dāng)檢測(cè)到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，節(jié)點(diǎn)在網(wǎng)絡(luò)中發(fā)送更新消息，收到更新消息的節(jié)點(diǎn)將更新自己的路由表，以維護(hù)一致的、及時(shí)的、準(zhǔn)確的路由信息，所以路由表可以準(zhǔn)確地反映網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。源節(jié)點(diǎn)一旦要發(fā)送報(bào)文，可以立即獲得到達(dá)目的節(jié)點(diǎn)的路由。因此這種路由協(xié)議的時(shí)延較小，但是路由協(xié)議的開銷較大，占用無線信道時(shí)間長(zhǎng)。基于此，出現(xiàn)了按需更新的路由協(xié)議，它是一種當(dāng)需要發(fā)送數(shù)據(jù)時(shí)才查找路由的路由算法。在這種路由協(xié)議中，節(jié)點(diǎn)不需要維護(hù)及時(shí)準(zhǔn)確的路由信息，當(dāng)需要向目的節(jié)點(diǎn)發(fā)送報(bào)文時(shí)，源節(jié)點(diǎn)才在網(wǎng)絡(luò)中發(fā)起路由查找過程，找到相應(yīng)的路由。與周期式路由協(xié)議相比，按需更新路由協(xié)議的開銷較小，但是數(shù)據(jù)報(bào)傳送的時(shí)延較大。因此在MANET中單純采用周期更新或按需更新路由協(xié)議都不能完全解決路由問題，特別是在網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大的時(shí)候這兩種類型的路由協(xié)議就顯的力不從心了。

動(dòng)態(tài)源路由協(xié)議(Dynamic Source Routing Protocol，DSR)，是一種典型的按需更新反應(yīng)式路由協(xié)議，它使用源路由而不是逐跳路由的算法，數(shù)據(jù)分組頭部攜帶了到達(dá)目的節(jié)點(diǎn)的完整路由，收到分組的移動(dòng)節(jié)點(diǎn)根據(jù)分組攜帶的路由信息轉(zhuǎn)發(fā)分組。協(xié)議運(yùn)作包括兩個(gè)部分:路由發(fā)現(xiàn)和路由維持。路由發(fā)現(xiàn)使網(wǎng)絡(luò)內(nèi)的任一節(jié)點(diǎn)能夠動(dòng)態(tài)地找到到達(dá)網(wǎng)絡(luò)內(nèi)其節(jié)點(diǎn)的路由;路由維持負(fù)責(zé)實(shí)時(shí)監(jiān)測(cè)正在使用的路由是否有效。DSR協(xié)議是基于最小跳數(shù)的路由協(xié)議。基于最小跳數(shù)意味著同樣轉(zhuǎn)發(fā)一個(gè)分組占用最少的移動(dòng)節(jié)點(diǎn)資源和處理時(shí)間，使得分組轉(zhuǎn)發(fā)更具效率。但有時(shí)候必須考慮這樣的問題:在某些區(qū)域內(nèi)移動(dòng)節(jié)點(diǎn)比較稀少，由于節(jié)點(diǎn)之間距離較遠(yuǎn)，節(jié)點(diǎn)之間容易移動(dòng)出彼此的無線覆蓋范圍，基于最小跳數(shù)的DSR路由更容易失效。另一方面，移動(dòng)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組時(shí)，都以跳數(shù)最小的路由為優(yōu)先，在區(qū)域節(jié)點(diǎn)比較稀少的情況下，會(huì)同時(shí)有很多節(jié)點(diǎn)向同一節(jié)點(diǎn)轉(zhuǎn)發(fā)分組，這將造成沖突。

本文在動(dòng)態(tài)源路由協(xié)議的基礎(chǔ)上，提出了基于網(wǎng)絡(luò)節(jié)點(diǎn)度值計(jì)算的路由協(xié)議。在路由建立過程中，計(jì)算網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的度值和節(jié)點(diǎn)能量，通過操作矩陣與概率擴(kuò)散矩陣計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的選擇概率。保留高概率的節(jié)點(diǎn)、使得路由搜索過程可以盡快地收斂到高性能的路由信息上。

2 網(wǎng)絡(luò)節(jié)點(diǎn)度值模型

MANET是一種由移動(dòng)節(jié)點(diǎn)組成的動(dòng)態(tài)網(wǎng)絡(luò)，本節(jié)首先描述網(wǎng)絡(luò)節(jié)點(diǎn)的運(yùn)動(dòng)狀態(tài)。節(jié)點(diǎn)i在時(shí)刻t的位置、速率和運(yùn)動(dòng)方向可以依次表示為(xi(t)，yi(t))、vi(t)、θi(t)。因此節(jié)點(diǎn)運(yùn)動(dòng)模型可以描述如下［4］:

因此在MANET網(wǎng)絡(luò)中，在時(shí)刻t節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離可以表示如下:

MANET中的節(jié)點(diǎn)均處于一個(gè)自由空間的傳播模型中，信號(hào)的強(qiáng)度只與其傳播距離有關(guān)，當(dāng)兩個(gè)相鄰節(jié)點(diǎn)間的距離大到一定程度時(shí)，發(fā)送端的信號(hào)將不能被接收端正確地接收，兩個(gè)節(jié)點(diǎn)間的路由鏈路斷開，此時(shí)兩個(gè)節(jié)點(diǎn)間的距離即為最大有效距離R［5］。由N個(gè)節(jié)點(diǎn)組成的MAENT可以構(gòu)成一個(gè)N×N的鄰接矩陣A=(aij(t))N×N，其元素應(yīng)滿足如下關(guān)系式:

每個(gè)節(jié)點(diǎn)都可以通過一個(gè)度值用于衡量該節(jié)點(diǎn)的連通狀況，節(jié)點(diǎn)i的度值定義如下所示。節(jié)點(diǎn)的度值越高，也說明網(wǎng)絡(luò)中與該節(jié)點(diǎn)相連接的節(jié)點(diǎn)也就越多。由于Ad Hoc網(wǎng)絡(luò)中節(jié)點(diǎn)狀態(tài)隨時(shí)間動(dòng)態(tài)變化，因此網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的度值也在動(dòng)態(tài)變化。

3 Grover網(wǎng)絡(luò)搜索模型

Grover量子搜索算法是Grover在1966年提出的。依靠量子并行計(jì)算的優(yōu)勢(shì)，在遍歷搜索問題中運(yùn)用該算法可以大大減少搜索成功的運(yùn)算次數(shù)。量子算法面臨的主要問題是解集的振幅太小，因此量子搜索算法策略的核心是:如何迅速地使振幅向解集集中，同時(shí)考慮變換的實(shí)現(xiàn)復(fù)雜性和魯棒性。也就是說，傳統(tǒng)搜索算法考慮的是如何避免在無效路徑上進(jìn)行搜索，而對(duì)量子算法來說，搜索所有路徑不是困難所在。量子算法尋求的是如何減少、消除非解路徑上的振幅，并把它轉(zhuǎn)移到解路徑上來［6－7］。

Grover算法的基本思想是通過對(duì)系統(tǒng)量子態(tài)進(jìn)行一系列幺正變換，使得各量子基態(tài)原先相等的概率幅發(fā)生變化，最終使所求解對(duì)應(yīng)量子基態(tài)的概率幅達(dá)到最大，這就保證了對(duì)變化后的量子態(tài)進(jìn)行測(cè)量可以以較大的概率獲得正確的解［8］。正是這種思想，可以被借鑒到MANET網(wǎng)絡(luò)的路由搜索中，用于降低網(wǎng)絡(luò)的計(jì)算量。每一次Grover迭代過程可以等價(jià)為兩次變換:首先使所需要查找的態(tài)相位旋轉(zhuǎn)π弧度，這樣可以用于標(biāo)注目標(biāo)解路徑。然后使用通過概率擴(kuò)散變換矩陣重新分配各個(gè)概率的大小。在之前將解路徑的振幅標(biāo)注以后，通過該擴(kuò)散變換矩陣D可以將其概率放大，同時(shí)將其余非解路徑的振幅縮小。

Grover搜索思想的特點(diǎn)在于利用矩陣運(yùn)算，對(duì)各種解徑的概率進(jìn)行變換，從而達(dá)到放大正確解徑概率的目的。通過選擇高概率的正確解徑，使得搜解過程快速收斂。需要借鑒Grover的思想，最重要的就是構(gòu)造操作矩陣和概率擴(kuò)散矩陣。本節(jié)首先提出了一種適合MANET網(wǎng)絡(luò)的擴(kuò)散矩陣和操作矩陣的構(gòu)造方式，然后定義了適合MANET網(wǎng)絡(luò)的Grover運(yùn)算，建立基于概率計(jì)算的路由模型［9］。

根據(jù)聯(lián)通矩陣可以構(gòu)建N×N的操作矩陣U，對(duì)于網(wǎng)絡(luò)中任一本地節(jié)點(diǎn)i，都維護(hù)矩陣U=(uimn)N×N。構(gòu)建方法如下:

uimn為負(fù)數(shù)表示節(jié)點(diǎn)m和本地節(jié)點(diǎn)i相鄰，是下一跳搜索的解徑之一。需要注意的是:為了避免出現(xiàn)路由環(huán)路，本地節(jié)點(diǎn)i與上一跳節(jié)點(diǎn)j的關(guān)系，反映在操作矩陣中為uijj=1，說明節(jié)點(diǎn)j不是下一跳搜索的解徑。擴(kuò)散矩陣的作用在于放大正確的解徑，使得路由搜索快速收斂。在將解徑的振幅標(biāo)注以后，通過該擴(kuò)散變換矩陣D可以將其概率放大，同時(shí)將其余非解路徑的振幅縮小?？梢宰C明該矩陣滿足幺正矩陣的條件，該概率重分布變換也是幺正變換。構(gòu)建N×N的概率擴(kuò)散矩陣D，矩陣在整個(gè)路由搜索過程中保持恒定不變［10］:

構(gòu)建擴(kuò)散矩陣D和操作矩陣U后，如何定義矩陣運(yùn)算使得正確解徑的概率得以放大，是將Grover搜索思想應(yīng)用于MANET的另一個(gè)難題［11－12］。在路由搜索過程中，定義N×1的節(jié)點(diǎn)振幅矩陣γ，用于記錄各個(gè)節(jié)點(diǎn)的概率。每個(gè)節(jié)點(diǎn)的初始振幅都相等表示如下:

當(dāng)本地節(jié)點(diǎn)i需要確定后續(xù)節(jié)點(diǎn)發(fā)送數(shù)據(jù)報(bào)時(shí)，首先通過鄰接矩陣構(gòu)造操作矩陣和擴(kuò)散矩陣。在上一跳時(shí)，節(jié)點(diǎn)的振幅矢量為γk，本地節(jié)點(diǎn)運(yùn)算后，每個(gè)節(jié)點(diǎn)的振幅γk+1。

因?yàn)椴僮骶仃嚥皇菃挝痪仃嚕缘玫降母怕适噶啃枰M(jìn)行歸一化處理。本地節(jié)點(diǎn)的歸一化概率計(jì)算公式如下:

算法首先將解路徑的相位取反，并在此基礎(chǔ)上，對(duì)初始節(jié)點(diǎn)矢量矩陣進(jìn)行幺正變換，該變換的作用就是將解路徑的振幅放大，同時(shí)縮小非解路徑的振幅，相應(yīng)的增大了解路徑的被測(cè)概率。如此循環(huán)迭代直到找到目的節(jié)點(diǎn)，此時(shí)目的節(jié)點(diǎn)維護(hù)的概率矢量中，解路徑的振幅擴(kuò)大，非解路徑的振幅縮小，將以最大概率可能性得到我們所需要的路由。

4 網(wǎng)絡(luò)仿真

為了進(jìn)一步分析提出的基于網(wǎng)路節(jié)點(diǎn)態(tài)矢量思想的路由協(xié)議的性能，本節(jié)建立了網(wǎng)絡(luò)仿真模型對(duì)協(xié)議進(jìn)行分析。通過前面的分析可以發(fā)現(xiàn)路由搜索過程按照?qǐng)D1進(jìn)行。

圖1 算法流程框圖

在一個(gè)1 200 m×1 200 m的無線傳感網(wǎng)絡(luò)中，散落著90個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)在網(wǎng)絡(luò)中隨機(jī)移動(dòng)。初始時(shí)刻節(jié)點(diǎn)位置分布如圖2所示。移動(dòng)的速度在［0，5 m/s］之間變化，運(yùn)動(dòng)角度在［0，2π］之間隨機(jī)變化，變化概率服從均勻分布。當(dāng)節(jié)點(diǎn)在下一時(shí)刻將要運(yùn)動(dòng)至邊界時(shí)，進(jìn)行反向運(yùn)動(dòng)，在網(wǎng)絡(luò)中假設(shè)每個(gè)節(jié)點(diǎn)的一跳通信范圍是80 m。

圖2 某時(shí)刻網(wǎng)絡(luò)節(jié)點(diǎn)位置分布圖

網(wǎng)絡(luò)數(shù)據(jù)傳送的成功率可以定義如下:當(dāng)兩個(gè)節(jié)點(diǎn)需要通信時(shí)，如果不能找到合適的路由進(jìn)行傳輸，那么就認(rèn)為數(shù)據(jù)傳輸是不成功的?？紤]由于不同的節(jié)點(diǎn)選擇概率對(duì)于網(wǎng)絡(luò)節(jié)點(diǎn)成功率所造成的影響，對(duì)基于網(wǎng)絡(luò)節(jié)點(diǎn)度值計(jì)算思想的路由協(xié)議進(jìn)行仿真分析，得到仿真圖如圖3所示。

圖3 網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)某晒β史抡鎴D

從圖3可以發(fā)現(xiàn)，選擇概率ρ越大，網(wǎng)絡(luò)數(shù)據(jù)成功率也就越大，但是同時(shí)也伴隨著網(wǎng)絡(luò)計(jì)算量的提高。減少計(jì)算量使得路由搜索算法盡快收斂，是基于網(wǎng)絡(luò)節(jié)點(diǎn)度值計(jì)算思想的路由協(xié)議的一個(gè)顯著優(yōu)點(diǎn)，本節(jié)將對(duì)網(wǎng)絡(luò)的業(yè)務(wù)計(jì)算量進(jìn)行仿真。對(duì)網(wǎng)絡(luò)計(jì)算量進(jìn)行定義:路由搜索時(shí)，每一次乘除運(yùn)算都認(rèn)為是一次計(jì)算量。對(duì)于不同的節(jié)點(diǎn)選擇概率，針對(duì)網(wǎng)絡(luò)中3160次網(wǎng)絡(luò)通信業(yè)務(wù)進(jìn)行仿真，統(tǒng)計(jì)網(wǎng)絡(luò)平均計(jì)算量如圖4所示?？梢娋W(wǎng)絡(luò)計(jì)算量隨著節(jié)點(diǎn)選擇概率的增加而增加，因此網(wǎng)絡(luò)需要在網(wǎng)絡(luò)通信成功率和網(wǎng)絡(luò)計(jì)算量之間做一個(gè)均衡。

對(duì)比節(jié)點(diǎn)度值計(jì)算路由協(xié)議與DSR路由協(xié)議，雖然DSR可以獲得較高的數(shù)據(jù)傳輸成功率，得到仿真如圖5所示。但是網(wǎng)絡(luò)計(jì)算量是非常龐大的。為了說明這一點(diǎn)，對(duì)于基于節(jié)點(diǎn)度值計(jì)算思想的路由協(xié)議與DSR協(xié)議在網(wǎng)絡(luò)計(jì)算量上做了比較，得到仿真如圖6所示。

圖4 網(wǎng)絡(luò)計(jì)算量仿真圖

圖5 兩種路由協(xié)議在成功率上的差異仿真圖

圖6 兩種路由協(xié)議在計(jì)算量上的差異仿真圖

5 結(jié)束語(yǔ)

本文結(jié)合動(dòng)態(tài)源路由協(xié)議的特點(diǎn)，提出了一種基于節(jié)點(diǎn)度值計(jì)算的Grover路由算法。本文利用Grover搜索算法構(gòu)造操作矩陣和概率擴(kuò)散矩陣計(jì)算得到網(wǎng)絡(luò)中各節(jié)點(diǎn)選擇概率，進(jìn)而進(jìn)行路由選擇。仿真結(jié)果表明:本文提出的路由算法可以快速收斂、提供服務(wù)質(zhì)量保障等特點(diǎn)，彌補(bǔ)了已有算法的不足。

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.清華大學(xué)出版社，2005.

［2］鄭四海，李臘元.Ad Hoc網(wǎng)絡(luò)QoS多徑路由協(xié)議的研究［J］，武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版)，2008，32(3):450－453.

［3］鄭祖全.無線自組網(wǎng)技術(shù)實(shí)用教程［M］.北京:清華大學(xué)出版社，2004.

［4］于宏毅.無線移動(dòng)自組織網(wǎng)［M］.北京:人民郵電出版社，2005.

［5］Garcia-Luna-Aceves J，Roy S.On-Demand Loop-Free Routing with Link Vectors(OLIVE)［J］.IEEE Journal on Selected Areas in Communications，2005，23(3):533－546.

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

［7］Wu Xiaoxin，Bhargava B.AO2P:Ad Hoc on-Demand Position-Based Private Routing Protocol［J］.IEEE Transactions on Mobile Computing，2005，4(4):335－348.

［8］Anastasi G，Conti M，Gregori E，et al.An Energy-Aware Multimedia Streaming Protocol for Mobile Users［J］.Journal of Pervasive Computing and Communications，2006，1(4):42－50.

［9］薛小平，李欣，張思東.基于路由生存時(shí)間的Ad Hoc Qos路由［J］.北京交通大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，31(2):23－28.

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

［11］袁培燕，李臘元.移動(dòng)模型對(duì)Ad hoc網(wǎng)絡(luò)路由協(xié)議能耗的影響［J］.計(jì)算機(jī)工程，2007，33(11):123－125.

［12］王敏強(qiáng)，鄭寶玉.一種新的應(yīng)用于Ad Hoc網(wǎng)絡(luò)的能量感知路由協(xié)議［J］.南京郵電學(xué)院學(xué)報(bào)，2005，25(1):13－17.