盧 軍，鄔學軍，周 凱

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

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

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

1 相關研究

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

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

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

2 網絡節(jié)點度值模型

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

因此在MANET網絡中，在時刻t節(jié)點i和節(jié)點j之間的距離可以表示如下:

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

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

3 Grover網絡搜索模型

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

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

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

根據聯(lián)通矩陣可以構建N×N的操作矩陣U，對于網絡中任一本地節(jié)點i，都維護矩陣U=(uimn)N×N。構建方法如下:

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

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

當本地節(jié)點i需要確定后續(xù)節(jié)點發(fā)送數(shù)據報時，首先通過鄰接矩陣構造操作矩陣和擴散矩陣。在上一跳時，節(jié)點的振幅矢量為γk，本地節(jié)點運算后，每個節(jié)點的振幅γk+1。

因為操作矩陣不是單位矩陣，所以得到的概率矢量需要進行歸一化處理。本地節(jié)點的歸一化概率計算公式如下:

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

4 網絡仿真

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

圖1 算法流程框圖

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

圖2 某時刻網絡節(jié)點位置分布圖

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

圖3 網絡數(shù)據傳輸?shù)某晒β史抡鎴D

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

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

圖4 網絡計算量仿真圖

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

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

5 結束語

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

［1］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.清華大學出版社，2005.

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

［3］鄭祖全.無線自組網技術實用教程［M］.北京:清華大學出版社，2004.

［4］于宏毅.無線移動自組織網［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搜索思想的無線自組網絡路由算法研究［J］.傳感技術學報，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］薛小平，李欣，張思東.基于路由生存時間的Ad Hoc Qos路由［J］.北京交通大學學報(自然科學版)，2007，31(2):23－28.

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

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

［12］王敏強，鄭寶玉.一種新的應用于Ad Hoc網絡的能量感知路由協(xié)議［J］.南京郵電學院學報，2005，25(1):13－17.