大規模移動自組網中穩定的分段式路由協議
2008-12-31 00:00:00陳玉潔王國軍彭三城
計算機應用研究 2008年9期
摘 要：提出了大規模移動自組網中一種穩定的分段式路由協議，該協議中每個節點維護一個K跳鄰域路由表來分段建立路由。模擬研究表明該協議性能良好，具有穩定性強和路由成功率高等特點。
關鍵詞：移動自組網; 穩定性; 分段; 錨點
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2008)09277503
Stabilitybased segmentbysegment routing protocol
in largescale mobile Ad hoc networks
CHEN Yujie， WANG Guojun， PENG Sancheng
(School of Information Science Engineering， Central South University， Changsha 410083， China)
Abstract:This paper proposed a stabilitybased segmentbysegment routing protocol(S3R) in largescale Mobile Ad hoc NETworks(MANETs)， where each node maintains a routing table with khops vicinity information. Simulation studies show good performance of the proposed algorithm， such as good stability and high success ratio for routing.
Key words：mobile Ad hoc networks(MANETs); stability; segmentbysegment; anchor
MANETs是一種無基礎結構支持的多跳通信自組織網絡。網絡中的每一個節點可隨機移動并且可以充當數據轉發設備的角色，節點間的通信可能要經過多個中間節點的轉發。
現有移動自組網中的路由協議可以分為兩類，即基于網絡拓撲結構的路由和基于節點地理位置信息的路由[1]?；诰W絡拓撲結構的路由協議是根據網絡的拓撲結構信息來計算和維護路由的，可進一步劃分為主動式路由、反應式路由和混合式路由。在主動式路由中，每個移動節點都需要維護一個路由表，目的序列距離矢量路由協議DSDV[2]就是一個典型的主動式路由。反應式路由則是當需要時才發起路由查找過程。DSR[3]是一種基于源路由的反應式路由協議，當節點S向節點D發送數據時，它將使用洪泛法發送路由請求消息(RREQ)，目的節點收到請求消息后向S發送路由應答消息（RREP），由此建立路由。ZRP[4]是典型的混合式路由協議。該協議將網絡分為若干個互相重疊的區域，區域內采用傳統的主動式路由算法，區域之間采用反應式路由算法?；谕負浣Y構的路由的缺點是開銷大，難以擴展到大規模的移動自組網環境中。
現在對基于節點地理位置信息的路由研究越來越多，如GPSR[5]和GeoCast[6]。在基于節點地理位置信息的路由協議中，節點在轉發數據包時主要依據的是目的節點的地理位置信息和該節點一跳通信范圍內鄰居節點的地理位置信息。由于在發送數據之前無須預先建立路由，基于節點地理位置信息的路由協議可擴展性好?；诠濣c地理位置信息的路由利用貪婪算法從它的鄰居中找到一個距離目的節點更近的節點做下一跳轉發節點。如果在發送數據包的方向上有洞，即存在無節點的空區域，可能會導致局部最優問題[7]。該問題是指中間節點在它的直接鄰居中找不到比自己距離目的節點更近的節點進行數據轉發，但實際上網絡中可能存在到達目的節點的路由路徑，處理局部最優問題的代表有GPSR和洞影子協議[8]。
1 相關工作
現有的對移動自組網中的穩定路由協議研究主要是從有線網絡中的研究成果移植過來的。許多學者針對該領域開展了大量的研究工作，提出了多路徑路由[9]、基于信號強度的路由SSA[10]、最長生命期路徑[11]、分段式路由[12]以及基于鄰居變化率的路由[13]等。
文獻[9]是在DSR協議的基礎上建立一組完全獨立的多路徑，由于這些路徑是相互獨立的，某條路徑的失效不會給系統的服務質量造成很大的影響，該路由協議的穩定性比DSR協議好。但是，在DSR協議基礎上建立和維護多條獨立路徑的路由開銷比較大，不適合擴展到大規模的移動自組網中。
文獻[10]根據節點接收到的信號強度預測鏈路穩定性，轉發路徑只有在接收信號強度大于門限值時才允許建立，并在路徑中斷前主動進行路徑重建。該方法需要跨層協議設計的支持，在實際設計中，可能難以從底層協議獲取接收信號強度信息。
文獻[11]提出了最長生命期路徑算法，該算法通過預測和收集網絡中所有相鄰兩個節點之間連通的持續時間長度來計算最長生命期路徑，因此，存在系統開銷大、可擴展性不好等不足。
文獻[12]提出了分段式的路由協議，將網絡劃分成Mesh結構，每個網格內選擇一個超級節點作為簇頭節點，每個簇頭節點維護一個K跳范圍的鄰接區域。該協議通過選擇錨點分段地建立路由，可擴展性較好。但是，該協議沒有考慮路徑的穩定性。
文獻[13]提出了基于鄰居變化率的穩定路徑選擇算法。該算法在AODV(Ad hoc ondemand distance vector)協議的基礎上，選擇轉發跳數少并且局部拓撲變化小的路徑進行數據轉發。然而，該路由協議是基于按需路由策略的，因此，系統開銷比較大，難以擴展到大規模的移動自組網環境中。
本文通過基于拓撲結構的路由策略建立穩定的分段路徑和通過基于地理位置信息的路由策略選擇穩定的錨點來解決上述問題。
2 網絡模型
為了便于分析，本文作如下假設：網絡是同構的，即每一個節點的通信和計算能力等基本相同；網絡中節點總數為N，每一個節點以自己為中心，用跳數K作為局部區域的半徑，將整個網絡劃分成N個互相重疊的正方形區域。在網絡初始化時，給K設定一個初始值，以后K值的大小根據每個節點收集到的區域內節點的變化信息的不同而不同。
本文在文獻[13]的鄰居變化率的基礎上進行擴展，定義了節點的區域穩定性，利用S(Ni)來表示節點的區域穩定性，其中：Ni(t0)表示在t0時刻節點i的局部區域內節點集，Ni(t1)表示在t1時刻節點i 的局部區域內節點集。
S(Ni)=(Ni(t0)∩Ni(t1))/(Ni(t0)∪Ni(t1))(1)
S(Ni)的值越大，表示節點i的區域穩定性越強?？梢愿鶕唧w的網絡環境為 S(Ni)設定相應的上限值和下限值。如果S(Ni)小于下限值時，說明該節點的區域穩定性較差，將它的局部區域半徑K減1（若K為1，則不減）；如果S(Ni)大于上限值時，說明該節點的區域穩定性比較好，將它的局部區域半徑K加1（若K達到最大值，則不加）。K值的大小體現了節點的區域穩定性的強弱，K值越大，節點的區域穩定性就越好。
以每個節點為中心，將節點所在的局部區域邏輯上劃分為2K×2K 個大小相同的小正方形區域，其邊長等于節點的傳輸半徑，用(X，Y) 對小正方形區域進行編號，(X，Y) 與節點的地理位置(Xi，Yi) 以及小正方形的中心點位置(Xo，Yo) 的關系如下：
下面以節點A為例來說明如何將一個節點的局部區域劃分成2K×2K個小正方形區域。假設：節點A 的地理位置為（XA，YA），半徑K=2，那么就可以將節點A的局部區域劃分為16個小正方形子區域，根據式（2）和（3）可以得到最靠近節點A 的四個小正方形的編號分別為（1，1）、（-1，1）、（1，-1）、（-1，-1）。同理可計算出其他小正方形的編號。對局部區域進一步劃分的目的是為了在建立路由時可以有效地建立分段路徑以找到目的節點。如果小正方形內沒有任何節點，則將該小正方形定義為洞。本文將在路由發現過程中詳細討論如何處理洞的問題。
3 路由協議
3.1 穩定的局部路由表的生成
該協議中每個節點維護一個局部的正方形區域及其局部路由表。局部路由表的建立采用了文獻[13]的鄰居變化率的路由度量定義方法。其過程如下：
首先，假設t0時刻和t1時刻節點i的鄰居集分別為Si(t0)和Si(t1)，節點信息的更新周期為T=t1-t0。節點i的鄰居變化率用公式表示如下：
NCRi=(Si(t0)∩Si(t1))/Si(t0)∪Si(t1))
(4)將路徑沿途每一個節點的鄰居變化率的乘積定義為鄰居變化率的路由度量， 用公式表示如下：
NCRpath=∏ipathNCRi(5)
每一個節點收集其所在局部區域內所有節點的鄰居變化率，然后計算它到局部區域內其他所有節點的鄰居變化率的路由度量，選擇NCRpath值最大的路徑作為它們之間的通信路徑。通過該算法為每個節點建立一張穩定的局部路由表。
3.2 路由發現
32.1 域內路由發現
在路由發現過程中，如果源節點S發現目的節點D就在源節點的局部區域中，那么源節點利用自己的局部區域路由表就可以完成數據發送。
32.2 域間路由發現
當源節點S要發送數據給目的節點D時，并且D不在S的局部區域內，就通過以下的方法進行路由發現。假設S的地理位置信息為（XS，YS），D的地理位置信息為（XD，YD）。先利用S和D的地理位置信息計算出源節點S的局部區域內離目的節點最近的小正方形的編號；然后在這個小正方形內尋找一個穩定性最強的節點作為錨點來進行轉發數據，如圖1所示的節點A。如果在這個小正方形內有兩個節點的K值相等并且都是最大的，則選離目的節點D最近的節點作為錨點。源節點S通過自己的局部路由表與錨點A進行通信。
同理，在錨點A的局部區域內選出下一個錨點B，依此類推，直到找到一個錨點，即目的節點D 在該錨點的局部區域內。錨點A與C 之間是通過局部路由表轉發數據。圖1描述了域間路由的發現過程。
如果在中繼節點的局部區域內離目的節點最近的小正方形是一個洞，那么就在這個節點的局部區域內重新找一個離目的節點比它本身要近的不為洞的小正方形，再在這個小正方形內找穩定性最強的節點作為錨點轉發數據。如果在中繼節點的局部區域內找不到比它自身離目的節點更近的小正方形，則這次路由發現失敗。
源節點記錄其下游兩個錨點的信息，其余錨點要分別記錄它的上游和下游各兩個錨點的信息。記錄這些信息用于局部路徑修復。通過選擇穩定的錨點逐段建立一條穩定的路徑。
33 路由維護
由于節點的移動、節點能量耗盡以及遭受到外界攻擊而使節點失效等因素導致路徑失效。在路徑失效后，就需要重新建立一條新路徑，這樣會給系統帶來較大的開銷。因此，本文采用路徑局部修復的方法，該方法能快速地進行路徑恢復。
導致路徑失效的因素有以下幾種：a）源節點或目的節點的移動；b）錨點移動；c）局部區域內節點的移動。對于情況a)，可以在源節點和第一個錨點之間或在最后一個錨點與目的節點之間進行一次路由發現過程。對于情況b)，可以在該錨點的前一個錨點與后一個錨點之間進行一次新的路由發現的過程。對于情況c)，可以在該局部區域中重新建立一條新的路徑來替代原來不可用的路徑。
從上面的描述可知，當路徑失效需要進行修復時，都是在局部范圍內進行一次新的路由發現過程，所花費的開銷要比重新建立一條從源節點到目的節點的路徑的開銷要小很多。
4 模擬與分析
本文使用C++模擬實現了穩定的分段式路由協議。假設網絡中的節點分布在一個矩形區域中，節點的傳輸半徑為250 m，節點的移動速度隨機分布在[0，10 m/s]。洞的密度是網絡中洞的總面積與網絡總面積之間的比值。
本文模擬了協議在兩種網絡環境下的性能：a)3 600m×2 400m，節點總數為600;b)6 000m×6 000m，節點總數為2 000。在每一次模擬中，隨機地建立20條路徑。
圖2和3給出了路由的成功率與K的大小的關系。可以看到當K=1時，實際上就是GPSR路由協議，其路徑成功率不高，特別是在洞的密度比較大時，這是因為它不知道洞的信息，會遇到局部最優問題。隨著K值的增大，路徑成功率有了很大的提高。這是因為K值越大，節點維護的局部區域就越大，從而收集到洞周圍更多的節點信息，可以有效地避洞。
圖4和5給出了路徑中斷次數與節點速度以及K的大小的關系?？梢钥吹疆敼濣c速度增大時，路徑的中斷次數持續上升，路徑中斷次數隨K值增大而減少，當K取3、4和5時，本文提出的穩定的分段式路由協議（S3R）協議的路徑中斷次數均小于AODV協議的路徑中斷次數。這是因為S3R協議始終選擇局部拓撲變化小的路徑作為轉發路徑，從而減少了路徑中斷的次數。
5 結束語
本文提出了移動自組網中一種穩定的分段式路由協議。該協議在節點所在的局部范圍內使用網絡拓撲結構信息，而在選擇錨點時使用節點地理位置信息。該協議為每一個節點維護一個K跳鄰域的局部路由表，能夠有效地避免網絡中出現洞而導致的問題。該協議中選擇穩定性較強的節點作為錨點，錨點之間的通信是通過局部路由表，這種方式建立的路徑比較穩定，可以擴展到大規模的移動自組網中。
參考文獻：
［1］ROYER M， TOH C K. A review of current routing protocols for Ad hoc wireless networks[J].IEEE Personal Communications，1999，17(8):4655.
［2］PERKINS C E， BHAGWAT P. Highly dynamic destinationsequenced distancevector routing (DSDV) for mobile computers[C]//Proc ofConference on Communications Architectures， Protocols and Applications.New York: ACM Press， 1994:234244.
［3］JOHNSON D，MALTZ D. Dynamic source routing in Ad hoc wireless networks[M]//IMIELINSKIT， KORTH H. Mobile Computing.[S.l.]:Kluwer，1996:153181.
［4］HAAS Z J， PEARLMAN M R. ZRP: a hybrid framework for routing in Ad hoc networks[M]//PERKINS C E. Ad hoc Networking Reading. MA:AddisonWesley，2001:221253.
［5］KARP B， KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[C]//Proc of the 6th Anual International Conference on Mobile Computing and Networking Boston: ACM Press， 2000:243254.
［6］NAVAS J C， IMIELINSKI T. Geocastgeographic addressing and routing[C]//Proc of ACM/IEEE International Conference on Mobile Computing and Networking Mobile Computing and Networking.1997:6676.
［7］FAYED M， MOUFTAH H T. Characterizing the impact of routing holes on geographic routing[C]//Proc ofSystems Communications.2005:401406.
［8］WANG Guojun， ZHANG Lifan， CAO Jiannong. Logical locationbased routing with holeshadowing in largescale MANETs[C]//Proc ofIEEE International Conference on Communications (ICC 2006).Istanbul: IEEE Computer Society， 2006:35603565.
［9］SHI Jinglun， ZHANG Ling， DONG Shoubin. A stabilitybased multipath routing algorithm for ad hoc networks[C]//Proc ofthe 14th IEEE International Symposium on Personal， Indoor and Mobile Radio Communications.2003:516520.
［10］DUBE R， RAIS C D， WANG K，et al. Signal stabilitybased adaptive routing (SSA) for Ad hoc mobile networks[J].IEEE Personal Communications， 1997，4(1):3645.
［11］魏曉海，陳國良，萬穎瑜，等.移動自組網中的最長生命期路徑[J].軟件學報， 2006，17(3):498508.
［12］CAO Jiannong， ZHANG Lifan， WANG Guojun， et al. SSR: segmentbysegment routing in largescale MANETs[C]//Proc of the 3rd IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS2006). 2006:216224.
［13］蔡一兵，李海波，李忠誠，等.移動自組網基于鄰居變化率穩定路徑選擇方法[J]. 軟件學報，2007，18(3):681692.
