基于K-最近鄰基站的移動手機自組網路由協議

摘 要:通過分析AODV算法及其存在的問題，結合節點的移動速度和方向等信息， 提出了一種基于K-最近鄰基站的移動手機自組網混合路由協議。在新協議中， 當網絡的本地基礎設施發生故障時，每個本地節點首先生成并維護一個K-最近鄰基站信息表，然后基于該K-最近鄰基站信息表，利用改進的AODV協議來進行按需路由。理論分析與仿真結果表明， 新算法的性能要優于傳統的按需路由協議AODV，因此，更適合移動手機自組網中的路由。

關鍵詞:移動手機自組網; 按需路由; 表驅動路由; 混合路由; K-最近鄰基站

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1163-04

doi:10.3969/j.issn.1001-3695.2010.03.100

Routing protocol for mobile Ad hoc cell phone networkbased on K-nearest neighboring base stations

HU Jun1，XU Shu-hua1，WANG Lei2

(1.College of Software， Hunan Vocational College of Science Technology， Changsha 410118， China;2.College of Software， Hunan University， Changsha 410082， China)

Abstract:By analysing the AODV protocol and its defect，then considerded the information about the moving speed and direction of nodes，this paper presented a new hybrid routing protocol for mobile Ad hoc cell phone network based on K-nearest neighboring base stations， in which， when the local network infrastructures fail or was destroyed，each local node would generate and maintenance a K-nearest neighboring base stations information table， and then， based on the table，used the improved AODV protocol to do on-demand routing.Theoretical analyses and simulation results show that， the newly proposed protocol has better performance than the traditional on-demand routing protocol AODV， so it is more suitable for routing in mobile Ad hoc cell phone networks.

Key words:mobile Ad hoc cell phone network; on-demand routing; table-driven routing; hybrid routing; K-nearest neighboring base stations

0 引言

Ad hoc網絡由一組帶有無線收發裝置的移動終端組成的一個多跳的、臨時性、自創建(self-creating)、自組織(self-organizing)、自管理(self-administering)系統， 具有較強的容錯性和魯棒性， 能夠在戰場、救災等場合快速部署，具有廣闊的應用前景。但由于其能量由主機所帶電池決定， 帶寬受無線網絡限制， 并且由于主機具有移動性，網絡拓撲結構變化頻繁。因此， 路由協議成為移動自組網絡研究中關鍵的問題之一[1~3]。目前， 國際上關于Ad hoc網絡的路由協議研究正在逐步深入， 根據節點獲得路由信息的途徑， Ad hoc網絡的路由協議可分為按需(on-demand)、表驅動(table-driven)和混合式(hybrid)三大類[4，5]。

1)按需路由協議 又稱為反應式(reactive)路由協議，這類協議的主要代表有AODV(Ad hoc on-demand distance vector)[6]等。其優點是不需要周期性地廣播路由信息、感測鏈路狀態及進行鄰居檢測;缺點是分組存在較大的時延， 而且每個分組包含的路由信息太多。

2)表驅動路由協議 又稱為先應式(proactive)路由協議，典型的表驅動路由協議有DSDV(destination-sequenced distance vector)[7]等。其優點是當節點需要發送數據分組時， 只要去往目的節點的路由存在，所需的延時就很小;缺點是維護的路由可能從來不用，即使網絡拓撲沒有變化也會產生通信開銷。

3)混合式路由協議 它對上兩種類型的折中，一般采用分級路由體系，一些節點組成一個cluster或者Zone，cluster或者zone內節點采用表驅動路由策略，其間的節點采用按需路由策略。

在由于自然災難或其他各種原因導致網絡基礎設施出現故障而無法使用時，快速恢復通信是非常重要的。借助于移動自組網絡技術，能夠快速建立臨時手機自組網絡，延伸網絡基礎設施，從而減少營救時間和災難帶來的危害。與傳統移動自組網絡相比，手機自組網絡除了具有移動自組網的普遍性質之外，還具有節點稠密分布，信息交換頻繁、存在遠程網絡基礎設施等獨特性質，因此，上述傳統移動自組網絡中的路由技術不能直接應用于手機自組網絡。

1 相關概念及定義

手機自組網作為一種分布式網絡，是一種自治、多跳網絡，整個網絡沒有本地的基礎設施，能夠在不能利用或者不便利用現有本地網絡基礎設施(如基站)的情況下，提供終端之間的相互通信。由于終端的發射功率和無線覆蓋范圍有限，距離較遠的兩個終端如果要進行通信就必須借助于其他節點進行分組轉發，這樣節點之間構成了一種無線多跳網絡。其中所有手機終端均具有路由和分組轉發功能，可以通過無線連接構成任意的網絡拓撲。手機自組網既可以作為單獨的網絡獨立工作，也可以作為末端子網的形式接入現有蜂窩網絡。手機自組網能夠利用手機終端的路由轉發功能，在無基礎設施的情況下進行數據通信， 從而彌補了無本地網絡通信基礎設施可使用的缺陷。

定義1 信號盲區。某個區域， 若本地移動網絡基礎設施出現故障而無法使用， 或不存在本地移動網絡基礎設施時， 則稱該區域為信號盲區。

定義2 K-最近鄰基站。假定區域A為信號盲區， 節點i為區域A中的任意一臺移動終端，則稱與節點i的聯系頻度F最大的K個基站為節點i的K-最近鄰基站。其中，初始時i與任意基站A的聯系頻度F(A，i)=0，當i與A之間成功建立一次路由，則F(A，i)=F(A，i)+1。

2 基于K-最近鄰基站路由協議(KNNBSR)

2.1 節點對之間通信維持時間的計算方法

假定任意節點的通信半徑均為R，節點a、b的移動速度與移動方向角分別為va、vb、θa、θb，如圖1所示，節點a、b的剩余生存時間分別為Ta、Tb，節點a的初始位置為(0，0)，節點b相對于a的初始位置為(xb，yb)，則經過時間t，節點a、b分別到達a′、b′，則a′、b′的位置分別為(x′a，y′a)、(x′b，y′b)。其中:

x′a=va×t×cos θa

y′a=va×t×sin θa

x′b=xb+vb×t×cos θb

y′b=yb+vb×t×sin θb(1)

顯然，若節點a、b在初始時刻處于雙方的通信半徑之內， 即x2b+y2b≤R，則經過時間t，節點a、b之間仍能維持通信，則a、b在時刻t的坐標(x′a，y′a)、(x′b，y′b)及t應滿足以下關系:

(x′b-x′a)2+(y′b-y′a)2≤R

t≤min{Ta，Tb}(2)

將式(1)代入式(2)即有

M=(xb+vb×t×cos θb-va×t×cos θa)2

N=(yb+vb×t×sin θb-va×t×sin θa)2

M+N≤R (3)

求解式(3)即可得到節點a、b之間的最大通信維持時間tmax(a，b)，顯然，當va=vb且θa=θb時， 有tmax(a，b)=min{Ta，Tb}。

2.2 AODV算法原理及其改進

1)AODV算法原理簡介 在AODV算法中，節點間通過廣播和接收路由接受請求(RREQ)分組以及路徑響應分組(RREP)來構建路由表，并根據它們的路由表建立起從源節點通向目的節點的路徑以便進行數據傳輸。

在數據傳輸過程中，如果有效路由發生鏈路中斷，AODV的路由算法將進行局部修復，重新建立一條繞過故障節點的新路由。

2)AODV路由算法的改進 由于手機自組網具有信息交換頻繁的特性，在節點i發送消息給節點j的同時，節點j也可能正在發送消息給節點i。假定L(i， j)表示節點i發起的查詢到節點j的路由路徑，L(j，i)表示節點j發起的查詢到節點i的路由路徑，則基于Rumor算法[8]原理可知，L(i，j)與L(j，i)將具有極大概率在某個節點k處相交。另外，在AODV算法中沒有考慮節點的移動性和移動的方向性。由于在手機自組網中，手機節點具有一定的移動性，若中間節點僅僅在自己的路由表中記錄第一個轉發給自己RREQ的鄰節點來建立反向路徑，則可能導致建立的路徑非常脆弱，會因節點的移動而快速失效。為此，本節結合2.1節中給出的節點對之間通信維持時間的計算方法和Rumor算法原理， 從以上兩個方面出發， 對AODV路由算法進行如下改進:

當某一節點i欲發送一個分組給節點j時，首先檢查它的路由表，如果沒有發現相應的路由信息，則廣播路由請求(RREQ)分組。當任意中間節點m收到RREQ時， 先檢查是否已接收過該分組，若是，則將該分組信息丟棄;否則，將檢查請求分組的目的地址是否為自己，如不是，則再檢查在自己的路由表中是否有一條有效的路徑可以到達目的節點，或者存在一條從目的節點到達自己的有效路徑。如果沒有， 則首先計算m與每個鄰節點之間的最大通信維持時間tmax;然后，在自己的路由表中記錄滿足tmax≥Tv的第一個轉發給自己RREQ分組的鄰節點，其中Tv為通信維持時間閾值，從而通過這樣的方法來建立一條反向路徑。目的節點和中間節點通過建立的反向路徑單播一個路徑響應分組(RREP)給轉發給它的RREQ拷貝的鄰節點。當RREP通過反向路徑到達源節點，則表明這條路徑上的中間節點在它們的路由表中建立起了一條從源節點通向目的節點的正向路徑。

3)AODV路由局部修復方法的改進 當節點源節點到目的節點的路徑失效時需要進行局部修復。文獻[9]通過要求在節點保存的路由表項及RREQ，RREP分組中增加下兩跳節點的地址，對AODV進行了改進， 具體改進方法如圖2所示。

在圖2中，節點A發送或者轉發數據分組到節點D時，檢查路由表，如果沒有找到路由表項或者路由表項已經過期，則發送RREQ消息。當到節點D的路由表項的下一跳B失效或者運動出節點A的通信范圍時，A到D的路徑失效， 則進行局部修復。A并不直接發送目的為D的RREQ消息，而是查找A的目的為D的路由表項中的下兩跳節點C。如果路由表項中下兩跳節點C地址存在，則A發送目的為C的路由修復請求分組Repair-RREQ，當Repair-RREQ經過E到達C，且節點C到D的路由有效，則C發送路由修復應答分組Repair-RREP，經反向路由通過節點E將Repair-RREP發送回節點A。這樣就重新建立了一條從節點A途經節點E到節點D的路由。顯然，文獻[9]的改進方法在對節點E的選擇過程中，沒有考慮E的移動性和移動的方向性，因此無法保證新局部路徑A→E→C能盡可能長時間地保持有效。

為此，本文結合2.1節中給出的節點對之間通信維持時間的計算方法， 對文獻[9]中從節點A發送目的為節點C的路由修復請求分組Repair-RREQ增加A的移動速度和方向信息， 當Repair-RREQ經過節點E1，E2，…，En到達C，且C到D的路由有效，則C從E1，E2，…，En中選擇min{tmax(A，Ei)，tmax(Ei，C)}最大的節點E，并發送路由修復應答分組Repair-RREP，經反向路由通過節點E將Repair-RREP發送回節點A。這樣就重新建立了一條從節點A途經E到D的路由。

顯然，經過以上改進， 能更加有效地保證新局部路徑A→E→C能盡可能長時間地保持有效。

2.3 信號盲區外節點到信號盲區內節點的路由

假定源節點i位于信號盲區A之外，目的節點j位于信號盲區A之內，源節點i向目的節點j發送信息，則其路由過程如下:

a)源節點i首先通過本地基站Bi接入本地交換中心MSCi(mobile switching center)，然后MSCi將消息轉發到本地短信中心SMSCi(short message service center)。

b)SMSCi通過匯接網關GNS(gateway name server)向HLR(home location register)查詢路由，并通過該路由將消息轉發給目的交換中心MSCj，然后MSCj將消息轉發給本地短信中心SMSCj。

c)SMSCj判斷短信目的路由，試圖將消息轉發給節點j所在的基站Bj。若判斷Bj因故障或不存在而不可達，則將消息轉發給離目的節點j最近的基站B′j。

d)B′j發現節點j不在自己的區域之內，將啟動自組路由查詢過程，激活本區域內所有移動終端的路由功能，并依據2.2節中給出的改進AODV算法進行路由查詢。在路由查詢過程中，各中間節點收到轉發的消息后，若發現自己不處于B′j區域，則還要維護一張K-最近鄰基站表(按與自己的聯系頻度從大到小排列);若計算發現B′j與自己的聯系頻度大于自己K-最近鄰基站表中的某個基站X與自己的聯系頻度，則將B′j插入到X之前，而刪除與自己聯系頻度最小的那個基站(即排名最后的基站)信息。

e)若成功發現一條與目的節點j之間的路由，則B′j將消息沿該路由發送給目的節點j。算法結束。

2.4 信號盲區內節點到信號盲區內外節點的路由

假定源節點i位于信號盲區A之內，目的節點j位于信號盲區A之內或之外，源節點i向目的節點j發送信息，則其路由過程如下:

a)源節點i發現無法檢測到本地基站信息，將激活自己的路由功能;然后從自己維護的K-最近鄰基站表中選擇聯系頻度最大(即第一個)的基站，將其地址與目的節點j的地址一起作為RREQ的目的地址;再依據給出改進的AODV算法進行路由查詢。

b)若成功發現一條與目的節點j之間的路由，則i將消息沿該路由發送給目的節點j。算法結束。

c)若某個中間節點檢測到自己與目的基站或目的節點之間存在直接連接， 則通過建立的反向路徑單播一個路徑響應分組(RREP)給轉發給它的RREQ拷貝的鄰節點。當RREP通過反向路徑到達源節點， 則表明這條路徑上的中間節點在它們的路由表中建立起了一條從源節點通向目的基站或目的節點的正向路徑。

d)若源節點發現存在一條到目的基站或目的節點的正向路徑，則將消息發送給該目的基站或目的節點;否則，從自己維護的K-最近鄰基站表中選擇下一個基站， 并重復上述路由查詢過程。

e)目的基站接收到源節點i發送的消息，將通過其所屬的本地交換中心將消息轉發到本地短信中心;該本地短信中心再通過匯接網關向HLR查詢路由， 若目標節點j也位于信號盲區A之內，則目的基站將利用2.3節的算法進行路由查詢，否則通過向HLR查詢得到的路由將消息轉發給目標節點j所屬的目標交換中心MSCj;然后MSCj再將消息轉發給其本地短信中心SMSCj，并通過SMSCj最終將消息轉發給目標節點j。

3 算法性能分析與仿真實驗

為了評價路由協議KNNBSR的性能，本章分別從路由協議開銷、分組成功傳送率、平均端到端時延和網絡的吞吐率這四項指標進行了檢驗。它們的定義分別為:

a)路由協議開銷routing costs(%)=(RREQ包個數×RREQ包長度+RREP包個數×RREP包長度+RERR包個數×RERR包長度)/(RREQ包個數×RREQ包長度+RREP包個數×RREP包長度+RERR包個數×RERR包長度+DATA包個數×DATA包長度)。

b)分組成功投遞率successful packet delivery rate(%)。它是指接收端收到的分組總數和發送端產生的分組總數之比，可以反映網絡所能支持的最大吞吐量， 從而在一定程度上刻畫了協議的完整性和正確性。

c)平均端到端時延average end-to-end delay(s)。該參數是在接收數據時由網絡層統計的，它統計的是一個數據包從源節點網絡層成功到達目的節點網絡層平均經過的時間。該參數能夠反映網絡是否通暢，時延越小證明網絡越通暢。

d)網絡吞吐率throughput(packets/s)。統計所有目的節點在單位時間內接收到的分組個數，并反映了網絡對數據業務的承載能力。

本仿真實驗的軟硬件環境為Intel Core 2 Quad Q6600四核處理器，2.4 GHz，4 GB內存的DELL PC，操作系統為Windows Vista SP1，仿真工具為OPNET 10.0.A PL1。仿真場景為500個節點隨機分布在1 000 m×2 000 m的矩形區域內以不同速度向隨機選擇的目的位置運動，每個節點的無線傳輸半徑為100 m，MAC層使用802.11協議，仿真時間為1 200 s。網絡中的每個節點都是數據業務源，業務分組的長度為1 KB，分組產生時間間隔服從0.25 s泊松分布。仿真實驗結果數據為多次試驗的平均值， 具體結果如圖3~6所示。

圖3給出了KNNBSR和AODV這兩種路由協議的平均端到端時延的仿真結果。由于KNNBSR提高了路由的穩定程度，從而減少了因為斷鏈重新路由的概率，使其平均端到端時延小于AODV。

圖4給出了這兩種路由協議的分組成功投遞率的仿真結果。由于KNNBSR協議考慮了節點的移動性而減少了因斷鏈導致的數據包丟棄，其分組成功投遞率高于AODV。

圖5給出了兩種路由算法協議開銷的仿真結果。KNNBSR協議由于路由維持時間更長， 減少了路由開銷以及路由局部修復的開銷，其開銷低于AODV。

圖6給出這兩種路由協議的網絡吞吐率的仿真結果。由于KNNBSR的路由維持時間更長，縮短了重新路由需要花費的時間，因此，其網絡吞吐率也要高于AODV。綜上所述，KNNBSR協議比AODV更適用于移動手機自組網。

4 結束語

根據上述分析，基于K-最近鄰基站的移動手機自組網混合路由協議在路由協議開銷、分組成功傳送率、平均端到端時延和網絡的吞吐率四個關鍵指標上均優于傳統的按需路由協議AODV， 具有更好的適用性。

參考文獻:

[1]

CHLAMTAC I，CONTI M，LIU J.Mobile Ad hoc networking:imperatives and challenges[J].Ad hoc Networks，2003，1(1):13-64.

[2]胡華平，胡光明，董攀，等.大規模移動自組網絡安全技術綜述[J].計算機研究與發展，2007，44(4):545-552.

[3]HU Y C，PERRIG A.A survey of secure wireless Ad hoc routing[J].Security and Privacy，2004，2(3):28-39.

[4]BAI Fan， SADAGOPAN N，KRISHNAMACHARI B， et al.Modeling path duration distributions in MANETs and their impact on reactive routing protocols[J]. IEEE Journal on Selected Areas in Communication，2004，22(7):1357-1373.

[5]臧婉瑜，于勐，謝立.按需式Ad hoc移動網絡路由協議的研究進展[J].計算機學報，2002，25(10):1009-1017.

[6]PERKINS C E，ROYER E M.Ad hoc on demand distance vector routing[C]//Proc of IEEE Work Shop on Mobile Computing Systems and Applications.New Orleans:[s.n.]，1999:90-100.

[7]PERKINS C E，BHAGWAT P.Highly dynamic destination-sequenced distance-vector routing(DSDV)for mobile computers[C]//Proc of SIGCOMM.New York:ACM Press，1994:234-244.

[8]BRAGINSKY D，ESTRIN D.Rumor routing algorithm for sensor networks[C]//Proc of the 1st Workshop on Sensor Networks and Applications. Atlanta:ACM Press，2002:22-31.

[9]肖百龍，郭偉，劉軍，等.移動自組網路由局部修復算法的研究[J].計算機研究與發展，2007，44(8):1383-1389.