基于連通度的Ａｄ ｈｏｃ網絡路由協議研究與仿真

摘要：對Ad hoc網絡各種路由協議進行仿真評估，分析它們在不同約束條件下不同度量的相對性能，是了解與學習路由協議性能的重要手段。目前的度量標準主要集中在吞吐量、延時、抖動、丟包率等QoS因子或路由負載、尋路時間等外部特性上，還沒有以Ad hoc網絡系統本身的連通度作為度量標準進行仿真，評價各種路由協議在不同試驗條件下對于同一網絡系統連通度的影響的相關研究。基于能量模型、節點密度、停留時間及移動速率四種約束條件對MANET提出的四種路由協議進行了關于網絡連通度的仿真與評估，給出了這方面的初步結論。

關鍵詞：連通度；能量模型；移動模型；無線自組網絡；網絡仿真；網絡協議

中圖分類號：TP393.01文獻標志碼：A

文章編號：1001－3695(2007)05－0273－05

0引言

Ad hoc是一種特殊的無線網絡，沒有中央控制設施。網絡中的節點既是路由器，又是主機，作為對等實體連接在一起。非相鄰的兩兩節點間的通信必須通過網絡中的其他節點進行轉發才能實現。如何在節點間選擇合適的路由，是Ad hoc網絡的核心問題。

目前比較經典的路由算法有距離向量路由協議DSDV[1]和其他三種按需路由協議AODV[2]、DSR[3]、TORA[4]。一般地，后者具有較低的路由負載而前者具有較低的端到端的延時。DSDV是一種表驅動的路由協議，基于改進后的經典的Bellman－Ford算法，它使用序列號的機制，避免了路由環路的產生和無限計數的問題。網絡中的每一個節點維護一張路由表，在該路由表中包含了所有可能到達的目的地以及到達這些目的地之間的跳數。盡管AODV、DSR和TORA同屬于按需路由協議，但它們的路由機制是不同的，AODV使用表驅動的路由框架和目的序列號；DSR使用源路由機制；而TORA使用反向鏈路的路由機制。

對于Ad hoc網絡連通度的研究，目前主要以圖論和連續統滲透理論[5~8]為理論基礎，以移動節點服從泊松分布為前提條件，以N維空間為研究背景，考察節點在什么樣的發射半徑下[9~12]或節點的平均度[12~17]在什么范圍內，整個網絡拓撲是k連通的。這里，假設網絡的拓撲結構為一無向圖G(V，E)。其中V是節點的集合，E是邊的集合(vi，vj)，vi，vj∈V。如果對于圖中任意兩個頂點vi、vj，vi和vj之間至少存在一條路徑，則稱G是連通圖。如果存在k條路徑，則稱G是k連通的。一般地，當發射功率滿足r≥c1×(ln n+c2)/πn，或節點的度d滿足d≥c3×log n，則網絡拓撲是連通的。目前在理論方面存在的開放區域是當N≥2、k≥2時，關鍵的r、d和λc難以界定。這里節點的度指節點鄰居節點的個數。兩種研究方法的側重點恰好相反，前者每個節點的r是固定的，d是變化的；后者每個節點的r是變化的，d是固定的。這種差異性的根本原因在于Ad hoc網絡的移動特性。正是這種移動特性，造成了局部節點密度density(t)的不同。

文獻[18]中同樣對這四種路由協議進行了關于能耗的分析。它們的仿真模型考慮了不同停留時間對上述協議的影響；25個節點隨機放置在大小為500×500的場景中。節點接收包時的能耗為230 mW，發送包時的能耗為330 mW，兩者之比約為0．69：1。文獻[19]構建的仿真場景大小為670×670，節點變化范圍為20~100，節點停留時間為40 s。分析了DSR和DSDV在能耗及節點終止率方面的性能。 文獻[20]構建的仿真場景為1 500×300，節點個數為20，速率為服從[0，20]的均勻分布，源節點個數10，停留時間為0、50、100、250和300s，對DSR、AODV和DSDV進行了關于能耗方面的評價。

由上可看出，文獻[18，20]以停留時間的變化來構建仿真場景，文獻[19]以節點密度為變化來進行仿真分析。本文認為，一方面，他們的仿真模型是不完善的；另一方面，僅僅對能量和節點終止率進行分析，以能耗的多少衡量協議性能的優劣，沒有考慮協議對于節點能耗的平衡性，沒有分析節點終止在不同仿真階段的分布情況，更沒有進一步分析由于節點終止而造成的網絡拓撲結構連通性的變化。此外，文獻[19，20]也沒有給出接收與發送時能耗的比例。這一點在進行關于能耗方面的評估是至關重要的。文獻[18]中雖然給出了一個比例關系，但是據了解[21~23]，這種比例關系是不恰當的?；谏厦娴目紤]，筆者認為對Ad hoc目前這幾種典型的路由協議進行關于網絡連通度方面的評估是非常有必要的。

1相關模型

1.1能耗參數

在試驗中，采用了如下能量消耗計算公式：

Energy=Power×Time

即當一個節點發送或接收一個包時所消耗的能量，是由該節點發送或接收的功率和處理該包所需要的時間決定的。這里，計算處理一個包的時間為

1．2移動模型

1．2．1發射節點的定位問題

發射節點的定位問題是所有移動模型的基礎。因為網絡中的每個節點在不同時刻擔任不同的角色，通過準確定位每個發射節點，進而可以定位網絡中的所有節點。目前有三種比較經典的定位技術，即燈塔定位技術、定向技術和抵達時差技術[24]。燈塔定位技術是在固定點放置大量的接收節點（燈塔），每個接收節點根據收到的信號強度判斷它們與發射節點的相對距離。一般來說，收到最強信號的燈塔距離發射節點最近。該燈塔的位置可以用來估計發射節點的位置。燈塔定位技術的優點在于簡單、耗費低，不需要在各個接收節點同步時鐘；缺點是估計發射節點的位置不夠準確。定向技術是根據接收節點收到信號的抵達角度（AOA）來決定發射節點的位置。明顯地，根據兩個接收節點收到的信號抵達角度，可以劃出兩條到達發射節點的直線，則兩條直線的交點就近似估計為發射節點的位置。因此，定向技術的關鍵問題是要準確判斷信號抵達的角度，而這需要復雜的硬件設施的支持，這是定向技術的不足之處。定向技術的優點在于它只需要兩個接收節點就能判斷發射節點的近似位置，精確性高于燈塔定位技術。定位技術的第三種方法是利用多對(發射節點、接收節點)信號抵達的時間差值(TDOA)。每一次TDOA的測量產生一條可能存在發射節點的雙曲線，兩條雙曲線的交點就近似估計為發射節點的位置。TDOA需要每個接收節點的時鐘同步，根據三個節點的TDOA值，可以近似計算出發射節點的位置：

每個節點在移動過程中需要滿足如下條件的約束：

(1)移動間隔的長度滿足獨立同分布的指數分布，均值為1/λn。

(2)移動的方向為滿足在[0，2π]之間的均勻分布。

(3)移動的速率為滿足均值為μn、方差為σn的獨立同分布的正態分布。

同時，上述三個參數之間沒有必然的聯系。移動模型與節點鏈路的失敗之間相互獨立。由文獻[25]知，兩個節點之間的相互移動速率近似滿足Raleigh分布，移動方向滿足[0，2π]之間的均勻分布。

1．2．3Reference Point Group Model（RPGM）

文獻[26]提出了一種RPGM模型。在這種模型中，節點在仿真的開始階段被劃分為不同的組，每個組有一個邏輯中心；邏輯中心的運動決定組成員的運動。每個節點擁有一個指向組運動的參考點，該參考點隨著組的運動而運動。單個節點的運動由兩個矢量決定，即組運動矢量和單個節點的參考點運動矢量。這兩個矢量決定了單個節點的網絡運動矢量。組的運動由一系列預先指定的檢測點組成，組的中心節點必須遍歷這些檢測點。自然地，通過改變相應的檢測點，可以構造不同的仿真場景。組的運動模式由隨機點線移動模型決定。每當組到達某個目的節點時，組內的所有節點停留一段時間，然后重復上述過程，向下一個目的節點移動。

1．2．4曼哈頓網格移動模型

曼哈頓網格移動模型是由仿真類似市區場景而提出來的。市區一般由相互垂直的街道交織而成。節點在該場景下的移動只能按照水平或垂直方向運動，而不能像上面的兩種移動模型那樣沿斜線運動。單個節點在某條街道隨機選擇一個點開始向目的節點以預先定義好的速率運動，到達目的節點時，停留一段隨機時間；然后向下一個目的節點重復進行上述運動，詳細的描述請參考文獻[27]。

1．3其他參數的設置

試驗中以NS2[28]作為仿真平臺，實驗所需的網絡拓撲由NS2的Setdest工具生成，節點的運行速率和初始位置均隨機設置，在整個仿真時間內模擬出各節點的隨機運行場景。整個實驗場景的區域為1 000 m×1 000 m，仿真時間為300 s，節點運行的最大速率為40 m/s。節點間的數據流由cbrgen工具隨機設置，分別隨機產生6、12、24、30和60對UDP流；每個CBR包的大小為512 Bytes，每秒發送一個包，網絡的初始連通度為0.666，帶寬為2 MB，節點的發射半徑為250 m。本文一共使用了四種仿真場景：①仿真場景的節點停留時間為0，節點個數分別為10、20、40、50和100(改變場景的節點密度)；②仿真場景的節點個數為50，停留時間分別為0、50、100、150、200、250、300 s；③仿真場景的節點個數為100，停留時間與②一致；④仿真場景為節點50，停留時間為0，最大移動速率分別為10、20、30、40 m/s。上述四種場景有一小部分是重疊的，即場景①節點個數為50和100時，分別對應②和③停留時間為0的情況。試驗一共生成210種隨機拓撲，每種情況對應10種，最后的數據為10種拓撲所產生數據的平均值。試驗中使用的無線信道模型是Two Ray Ground Reflection Model[29]。在MAC層使用IEEE 802.11的DCF（Distributed Coordination Function）[30]。此外，假定無線接收裝置的抗干擾性能力較強[31]。 如果信干比 (到達包的信號強度相對于干擾包信號強度的最小比率) [32]大于規定的門閾值，接收到達的分組；否則丟棄。

2仿真結果分析

2．1節點密度對連通度的影響

表1~3顯示了四種路由協議在不同的節點密度下死亡節點總數、網絡存活時間和系統能耗的變化情況。

其中，T表示協議的類型，N表示節點的個數。

由三張表可以看出，隨著節點個數的增多，四種協議的死亡節點總數和能耗均呈上升趨勢，網絡存活時間呈下降趨勢。TORA的死亡節點最多，AODV最少；AODV耗能最多，其次為DSDV、DSR、TORA；TORA的網絡存活時間最短，DSDV的網絡存活時間最長。這說明AODV協議節點能耗平衡性較好，能夠最大限度地保持網絡的連通，而TORA協議節點能耗平衡性則較差，能耗過多地集中在少數幾個節點上，其連通性能也最差。這里筆者豐富了文獻[19]中的結論。文獻[19]只仿真了DSDV和DSR在不同節點密度下的能耗，其結論與表3一致，但沒有分析節點終止對拓撲連通性能的影響。

AODV雖然是一種按需路由協議，但其仍需要定期的HELLO報文來檢查鄰居節點之間鏈路的連通情況，并且這部分HELLO控制報文的數量會隨著節點數目的增加呈冪方的形式遞增。這也是表3中所顯示AODV的能耗隨著節點數的增多上升很快的原因。DSDV是一種表驅動的路由協議，網絡中的控制報文過多，因此DSDV的能耗也很大。也正是由于這種機制，使得它的能耗表現得比較平穩。TORA表現出了最小的能耗特性。由下面的分析可以知道，TORA節點終止時間最早，節點終止個數最多，造成TORA網絡的連通性能最差。由于TORA使用反向鏈路機制，當節點與鄰居節點之間的鏈路發生中斷時，中斷節點把自己的序號設為鄰居節點序號中的最大值，這樣路由就會向水流一樣繞過中斷節點。由于TORA中斷節點個數最多，造成在活躍節點之間的路由數目減小，控制報文自然隨之減少，能耗也最低。

2．2停留時間對連通度的影響

表4~6顯示了節點個數為50時，每種協議在不同停留時間死亡節點、網絡存活時間和能耗的情況。表7~9顯示了節點個數為100時的相應情況。這里T表示協議的類型，P表示停留時間(s)。可以看出，隨著停留時間的增大，四種協議表現出共同的趨勢：節點終止的時間滯后，節點終止的個數減少；AODV和DSDV的能耗略呈下降趨勢，DSR和TORA的能耗略呈上升趨勢。50與100個節點兩種情況相比，后者的差異性減小，在表中表現為各類數據更為接近；不同之處在于DSDV受停留時間的影響較大(表5)，而三種按需協議則較小。這是由于隨著節點停留時間的增加，網絡拓撲由動態逐漸過渡為靜態，拓撲結構趨于穩定，DSDV在靜態拓撲結構下能夠發揮出自身路由機制的優勢，而在動態的拓撲結構中則抖動較大。 同時，與節點密度對相應度量標準的影響相比，在不同停留時間下，死亡節點總數和能耗展現了幾乎完全不同的趨勢：死亡節點個數減少，能耗減少(AODV和DSDV)。但總體說來，依然是AODV能耗最多，死亡節點個數相對較少；TORA能耗最少，死亡節點個數最多，網絡存活時間最短。這說明在不同的停留時間下，AODV協議節點能耗平衡性較好，能夠最大限度地保持網絡的連通，而TORA協議節點能耗平衡性則較差，能耗過多地集中在少數幾個節點上，其連通性能也最差。DSDV和DSR在能耗平衡性方面居中。

在此本文得出了與文獻[18~20]不同的結論。文獻[18]中的結論為DSR耗能最少，TORA耗能最多，并且隨著停留時間的增加，三種按需路由協議呈現下降的趨勢；而從表6和9可以看出，DSR并沒有表現出下降的趨勢，反面有輕微的上升趨勢。文獻[20]中沒有仿真TORA協議，關于能耗的結論與文獻[18]類似，但沒有給出三種按需路由協議呈現下降的趨勢這一結論。文獻[19]中只仿真了DSDV和DSR在不同節點密度下的能耗，結論與表3一致。但沒有仿真兩種協議在不同停留時間下的情況。除此之外，文獻[18，20]并沒有分析節點終止的情況；文獻[18~20]都沒有分析節點終止對拓撲連通性能的影響。

2．3移動速率對連通度的影響

表10~12顯示了上述三種度量在不同移動速率下的變化情況。這里，T表示協議的類型，V表示節點移動的最大速率(m/s)。與節點密度和停留時間下的結論幾乎完全不同(死亡節點個數趨勢相似，但差異性也很小)。從三張表中可以看到，移動速率對三種度量的影響很小，在表中表現為同類數據之間的差值很少。除DSDV的存活時間略呈上升趨勢之外，其他三種路由協議略呈下降趨勢。在能耗方面，雖然依舊是AODV耗能最多，但其他三種則幾乎沒有什么變化。仔細分析三張表之間的數據，發現一個有趣的現象，以速率為30 m/s為界限，表中的數據總體上呈現出兩種不同的趨勢，對于死亡節點總數和網絡存活時間來說，幾乎全部是先下降再上升，或先上升再下降(TORA的存活時間一直下降)。對于能耗來說，則表現為上升趨勢(AODV表現為一直上升，TORA表現為下降趨勢)。因此，在仿真Ad hoc網絡路由協議時，建議速率為30 m/s，它是一個應當值得關注的數字。

總體說來，依然是AODV能耗最多，死亡節點個數相對較少；TORA能耗最少，死亡節點個數最多，網絡存活時間最短。這說明在不同的移動速率下，AODV協議節點能耗平衡性較好，能夠最大限度地保持網絡的連通，而TORA協議節點能耗平衡性則較差，能耗過多地集中在少數幾個節點上，其連通性能也較差。

3結束語

本文與相關文獻的不同點在于，并沒有從理論上證明或驗證Ad hoc網絡保持k連通的各種約束條件，而是從考察協議節點能耗的平衡性出發，仿真分析了目前四種典型的Ad hoc網絡路由協議在保持網絡連通度方面的相對性能。筆者認為： TORA協議節點能耗平衡性差，連通性能最差； AODV協議關于各個節點的能耗比較均勻，能夠最大限度地保持網絡的連通；DSDV節點終止的時間最遲，停留時間對其能耗性能影響較大，停留時間較短時，節點終止個數較少，但能耗卻僅次于AODV。這說明在移動比較頻繁的環境中，DSDV協議節點能耗平衡性好，停留時間長時，節點終止個數多，在相對靜態的環境中，DSDV協議節點能耗平衡性下降；DSR協議在能耗平衡性方面居中。同時應當指出的是，移動速率對系統能耗等度量指標的影響要小于停留時間和節點密度對它的相應影響，并且30 m/s這個數字應當引起人們更多的關注。

參考文獻：

［1］PEKINS CHARLES E， BHAGWAT P. Highly dynamic destination－sequenced distance－vector routing for mobile computers[EB/OL].（2003）.http://www.cs.umd.edu/projects/mcml/papers/Sigcomm94.ps.

[2]PERKINS C. RFC3561 Ad hoc on－demand distance vector routing[S].[S.l.]:[s.n.]， 2003.

[3]JOHNSON D B， MALTZ D A， HU Yih－chun. The dynamic source routing protocol for mobile Ad hoc networks， Internet－Draft，draft－ietf－manet－dsr－10.txt[R].[S.l.]:[s.n.]， 2004.

[4]PARK V D， CORSON M S. Temporally－ordered routing algorithm（TORA） version 1: functional specification， Internet－Draft， draft－ietf－manet－tora－spec－00.txt[R].[S.l.]:[s.n.]，1997.

[5]BROADBENT S R， HAMMERSLEY J M. Percolation processes， I and Ⅱ[C]. London:Cambridge Philos. Soc.，1957: 629－645.

[6]BENJAMINI I， SCHRAMM O. Percolation beyond zd， many questions and a few answers[J]. Electron. Comm. Probab.， 1996，8(1):71－82.

[7]GRIMMETT G. Percolation[M]. Berlin: Springer－Verlag，1999.

[8]BOOTH L， BRUCK J， FRANCESCHETTI M， et al. Covering algorithms， continuum percolation and the geometry of wireless networks[J]. Annals of Applied Probability， 2003，13(2):722－741.

[9]SANTI P. The critical transmitting range for connectivity in mobile Ad hoc networks[J]. IEEE Trans. on Mobile Computing，2005，4(3):310－317.

[10]GUPTA P， KUMAR P R. Critical power for asymptotic connectivity in wireless networks[C]. Boston: Birkhuser， 1998:547－566.

[11]SANTI P， BLOUGH D M.The critical transmitting range for connectivity in sparse wireless Ad hoc networks[J]. IEEE Trans. on Mobile Computing， 2003，2(1):25－39.

[12]WAN P J， YI C W. Asymptotic critical transmission radius and critical neighbor number for k－connectivity in wireless Ad hoc networks[C]. Japan:IEEE Computer Society Press， 2004:1－8.

[13]BETTSTETTER C. On the minimum node degree and connectivity of a wireless multihop network[C]. Switzerland: IEEE Computer Society Press， 2002: 80－91.

[14]HEKMAT R， VANMIEGHEM P. Degree distribution and hopcount in wireless Ad hoc networks[C]. Sydney: IEEE Computer Society Press， 2003: 603－609. 

[15]TONGUZ O K， FERRARI G. Is the number of neighbors in Ad hoc wireless networks a good indicator of connectivity[C]. Switzerland: IEEE Computer Society Press， 2004:40－43.

[16]FERRARI G， TONGUZ O K. Minimum number of neighbors for fully connected uniform Ad hoc wireless networks[EB/OL]. http://www.ece.cmu.edu/~tonguz/paper/ICC2004_Neighbors_CR.pdf.

[17]XUE Feng， KUMAR P R. The number of neighbors needed for connectivity of wireless networks[J]. Wireless Networks， 2004，10(2):169－181.

[18]CANO J C， MANZONI P. A performance comparison of energy consumption for mobile Ad hoc network routing protocols[C]. San Francisco:IEEE Computer Society Press， 2000:57－64.

[19]ANNE A， WENG Jie. Performance comparison of Ad hoc routing protocols for networks with node energy constraints[EB/OL].(2004). http://www.stanford.edu/~amaaron/ee360/EE360_FINAL_PAPER.pdf.

[20]袁明，張連芳，舒炎泰.Ad hoc網絡路由協議能量消耗分析[J].計算機工程與應用，2003，39(15):146－149.

[21]STEMM M， KATZ R H. Measuring and reducing energy consumpsion of network interfaces in hand－held devices[J]. IEICE Transactions on Communications， 1997，E80－B(8):1125－1131.

[22]KASTEN O. Energy consumption[EB/OL].(2001).http://www.inf.ethz.ch /^kasten/Research/bathtub/energy－consumption.html.

[23]CHEN B， JAMIESON K， BALAKRISHNAN H， et al. Span: an energy efficient coordination algorithm for topology maintenance in Ad hoc wireless networks[C]. Rome:ACM， 2001:85－96.

[24]KEVIN J K， THOMAS E B， THEODORE S R. Wireless position location: fundamentals，implementation strategies， and sources of error[C]. America:IEEE， 1997:919－923.

[25]MCDONALD A B. A mobility－based framework for adaptive clustering in wireless Ad hoc networks[J]. IEEE Journal on Selected Areas in Communications， 1999，17(8):1466－1487.

[26]HONG X， GERLA M， PEI G， et al. A group mobility model for Ad hoc wireless networks[C]. Seattle:ACM/IEEE，1999:53－60.

[27]Universal Mobile Telecommunications System(UMTS). Selection procedures for the choice of radio transmission technologies:America， TS 30.03 3GPP[P].1998.

[28]KEVIN F， KANNAN V. The network simulator: NS－2[EB/OL].(2005).http://www.isi.edu/nsnam/ns/index.html.

[29]RAPPAPORT T S. Wireless communications: principles and practice[M]. New Jersey:Prentice Hall， 1996:641－656.

[30]HAYES V， O’HARA B.IEEE Std 802.11－1997 Wireless LAN medium access protocol and physical layer specification[S].New York: The Institute of Electrical and Electronics Engineers， 1997.

[31]LEE S－J， HSU Julian， HAYASHIDA R， et al. Selecting a routing strategy for your Ad hoc networks[J]. Computer Communications， 2003，26(7):723－733.

[32]FRIIS H T. A note on a simple transmission formula: proc. of IRE[C].[S.l.]:[s.n.]，1946:254－256.

[33]祁彪，何建華，楊宗凱.無線Ad hoc網絡協議的仿真評估[J]. 華中科技大學學報:自然科學版，2004，32(8):66－69. 

[34]DAS S R， PEKIN C E， ROYER E M. Performance comparison of two on－demand routing protocols for Ad hoc networks:proc. of INFOCOM[C]. Tel Aviv: IEEE， 2000: 3－12.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”