Ad Hoc網絡性能測試關鍵技術研究

本文首先介紹了Ad Hoc網絡及其相關協(xié)議的主要特點，根據網絡特性提出了性能測試的體系結構。圍繞體系結構中的不同測試內容，提出相關的測試方法，并詳細討論了網絡性能的評估手段和測試環(huán)境的設計。

隨著現(xiàn)代通信技術的進步，人們對移動通信需求的不斷增加，移動通信系統(tǒng)，如個人筆記本計算機，掌上型PDA設備等得到了迅速普及。但目前多數的移動通信系統(tǒng)是集中式控制的(有中心的)，網絡的運行要基于預先架設好的網絡設施。這兩個特點使得有中心的移動通信系統(tǒng)對有些特殊場合來說并不適用。例如，戰(zhàn)場上部隊快速展開和推進、發(fā)生地震或水災后的營救。這些場合的通信不能依賴于任何預先架設的網絡設施。此時，需要系統(tǒng)能實現(xiàn)臨時快速自動組網，結點要能移動。

Ad hoc網絡是一種有特殊用途的對等式網絡。它使用無線通信技術，網絡中的結點互相作為其鄰居(在其直接通信范圍內的結點)的路由器，通過結點轉發(fā)實現(xiàn)結點間的通信。它又被稱為多跳網絡(multi-hop network)、無固定網絡設施的網絡(infrastructure less network)或自組織網絡(self-organized network)[1]。

由于Ad

12 ALT="圖1：網絡接入時延的測試方法。"> hoc網絡工作在分布式移動環(huán)境中，并且網絡帶寬非常有限，所以要盡量減少通信對端的交互信息數量。多跳特性是Ad hoc網絡的另一個顯著標志。由于結點的無線通信距離有限，Ad hoc網絡中的結點不一定都在其它所有結點的直接通信范圍之內，而且受電磁干擾，地形干擾或天氣影響，結點的通信距離也會有所改變。所以當結點并非直接可達時，需要中間結點的轉發(fā)才能實現(xiàn)通信。也就是說從源結點到目的結點是多跳(multi-hop)連接的。

傳統(tǒng)的基于有線網絡的共享廣播信道接入技術(ALOHA、CSMA系列)只能在共享的信道上使用。而Ad hoc網絡具有多跳性，不是共享網絡。所以Ad hoc網絡的信道接入協(xié)議要充分考慮多跳帶來的隱終端、暴露終端和公平性等問題[2,3]。Ad hoc網絡中結點是移動的。結點的移動性造成網絡的拓撲結構不斷變化，這對接入協(xié)議和路由協(xié)議都提出了新的要求。首先接入協(xié)議要能夠感知到結點移動造成的鏈路通斷，并把這些信息報告給路由協(xié)議。路由協(xié)議要根據鏈路狀態(tài)的變化修改自己的路由表。傳統(tǒng)的基于固定網絡的路由協(xié)議顯然不能直接用于拓撲變化頻繁的 Ad hoc網絡。所以Ad hoc網絡路由協(xié)議成了研究的焦點。Ad hoc網絡中，結點的移動性也會影響網絡的性能[4]，這需要相應的機制來解決。

由于影響Ad Hoc性能的因素很多，并且錯綜復雜，僅僅考慮有限的測試指標并不能夠反映網絡的真實性能, 所以Ad Hoc網絡性能測試系統(tǒng)需要對網絡進行全面的分析與理解，根據網絡特性確定測試內容，有針對性地選擇測試方法，進而構建與具體網絡應用相適應的網絡測試環(huán)境。

網絡性能測試體系結構

Ad Hoc網絡協(xié)議主要包括網絡接入層協(xié)議(MAC)和路由協(xié)議。不同層次的協(xié)議由于所完成的功能不同，所以具有不同的測試指針。在網絡測試中，要合理評價網絡性能必須充分考慮不同層次的協(xié)議在性能上的差別。同時，對于不同的網絡應用來說，各個層次協(xié)議性能對網絡整體性能的影響也不盡相同。

Ad Hoc網絡性能測試按照網絡功能層次進行區(qū)分，主要分為以下三個方面的內容：通信終端物理性能測試，接入層協(xié)議測試和路由協(xié)議測試。

1. 通信終端物理性能測試

通信終端種類很多，包括數字電臺、PDA、移動筆記本電腦等等。不同的無線終端由于硬件配置不同，其物理性能也不盡相同。物理性能測試內容主要包括：

12 ALT="圖2：路由重建時間的計算方法。">

* 數據發(fā)送速率：即終端設備可支持的最大傳輸帶寬，對于多信道系統(tǒng)而言，還需要測試最大可用帶寬。

* 傳播距離：即設備的通信范圍，主要與終端的發(fā)送功率，接收門限(信噪比)有關。多跳網絡中，傳播距離會對網絡的拓撲關系產生重大的影響，也是MAC層協(xié)議設計通常需要考慮的問題[2][3]，也是影響網絡吞吐量的因素之一。

* 差錯控制能力：無線信道通常是不可靠信道，所以需要相應的差錯控制能力，保證在一定的信道誤碼率下，可以完成正常數據通信。

2. 網絡接入層性能測試

網絡接入層(MAC)解決了隱終端和暴露終端的問題[2][3]。MAC層協(xié)議的性能會直接影響網絡的整體性能。MAC層協(xié)議是Ad Hoc網絡組網協(xié)議的基礎，也是網絡結點通信的第一步，只有高效、公平、有序地組織網絡中的所有通信結點的鏈路層通信能力，才能保證上層網絡互聯(lián)協(xié)議(路由協(xié)議)的正常運行。網絡接入層性能測試內容主要有：

* 接入時延：結點從有數據需要發(fā)送到數據的實際發(fā)送的時間間隔。是反映單個結點接入效率的重要參數，但是不能反映網絡整體性能。

* 網絡吞吐量：接入協(xié)議的性能還體現(xiàn)在網絡吞吐量上，由于無線網絡數據幀的碰撞會導致所有的發(fā)送方都要退避一段時間，然后重新發(fā)送數據，這就必然對系統(tǒng)的吞吐量產生影響。

* 優(yōu)先級：網絡中的結點按照優(yōu)先級排序，優(yōu)先級高的結點比優(yōu)先級低的結點有更低的平均接入時延，這一點在同時承載數據業(yè)務和話音業(yè)務的網絡中顯得尤為重要。

* 公平性：優(yōu)先級然保證了優(yōu)先級高的結點有更低的接入時延，但是網絡接入協(xié)議還必須同時保證優(yōu)先級低的結點不會“餓死”，同等優(yōu)先級的結點還要有相同或接近的接入時延參數。

3. 路由協(xié)議性能測試

路由協(xié)議的任務是維護網絡拓撲，為結點之間的通信提供及時準確的路由信息，保證報文按照協(xié)議所提供的路徑正確到達目的結點。針對現(xiàn)有Ad Hoc網絡路由協(xié)議的特點，性能測試主要包括以下幾個方面：

* 端到端時延與吞吐量：路由協(xié)議所處理的是源結點到目的結點之間的路徑選擇信息，所以源結點到目的結點之間(端到端)的行為最直接的測試內容就是時延和吞吐量。但是，這兩個參數都與MAC層協(xié)議的效率直接相關。

* 路由發(fā)現(xiàn)時間(也稱為路由重建時間)：直接說明了路由算法的效率，即從無法根據路由表得到路由到得到可用路由的時間。需要注意的是，這個測試參數適用于需求驅動路由算法(反應式)[1][5]和具有事件觸發(fā)更新功能的路由表驅動型路由算法(先應式)[1][6]。

* 路由表收斂時間：對于路由表驅動型路由算法而言，路由協(xié)議在運行期間，路由表從初始狀態(tài)到路由表穩(wěn)定狀態(tài)通常會有一個自動更新的過程，這個時間通常稱為路由表收斂時間。

* 路由協(xié)議的效率：任何路由協(xié)議在運行過程中，都要有一定的路由協(xié)議開銷，用于在結點之間維護網絡的拓撲信息。對于無線網絡而言，網絡帶寬非常有限，協(xié)議開銷直接影響網絡帶寬的利用率，進而影響網絡的擴展性。所以路由協(xié)議的效率也是我們重點考慮的測試參數之一。

性能測試的基本方法

Ad Hoc網絡的性能測試的主要內容已經在第二節(jié)中進行了闡述，由于物理層的測試內容只涉及到點對點之間的通信。而且，無線終端設備廠商一般會事先提供相應的物理層參數，所以下面討論的性能測試方法只與網絡接入層和路由協(xié)議有關。

1. 接入層協(xié)議性能測試方法

(a) 接入時延測試

12 ALT="表1：給網絡不同的性能測試內容賦予不同的加權值可以更加客觀地反映網絡的性能。">

結點對所有到達發(fā)送緩沖區(qū)的數據包用時間戳進行標記，在該數據可以發(fā)送后，即滿足下列條件，收到CTS數據幀并且是緩沖區(qū)最先要發(fā)送的報文，再記錄下數據可以成功發(fā)送的時間。這個時間與時間戳記錄的時間相減即接入時延，在系統(tǒng)測試時，通常計算結點所有數據包的平均時延。接入時延測試如圖1所示：

(b) 優(yōu)先級測試

網絡中的優(yōu)先級可以分為結點優(yōu)先級和報文優(yōu)先級。在統(tǒng)計意義下，優(yōu)先級的測試要依賴于平均接入時延的計算。如果是對網絡結點按照優(yōu)先級進行區(qū)分，性能測試就計算不同結點的平均接入時延。如果網絡只支持報文優(yōu)先級，就要對不同類型的報文進行區(qū)分，分別計算平均接入時延。對于同時支持結點優(yōu)先級和報文優(yōu)先級的網絡，測試要更加復雜。

(c) 公平性測試

公平性測試的依據主要是平均網絡接入時延，優(yōu)先級高的結點比優(yōu)先級低的結點具有更小的平均接入時延。同時，不同優(yōu)先級結點之間的時延差距要相對明顯。例如，最高優(yōu)先級結點與最低優(yōu)先級結點之間的時延差距不到5%，就說明MAC層的網絡優(yōu)先級機制是失敗的。

2. 路由協(xié)議性能測試方法

路由協(xié)議所有的性能測試參數都需要在多跳網絡中實際測量得到，要根據Ad Hoc網絡的特點合理運用路由協(xié)議的性能測試方法。需要特別指出的是，網絡的覆蓋范圍，網絡結點的移動性等對網絡路由協(xié)議的參數會產生較為明顯的影響 [4]，上述問題將在第4節(jié)進行討論。Ad Hoc網絡的路由協(xié)議主要有如下幾方面的特征[8]：

*分布式特征：該特征是Ad Hoc網絡最突出的特征。

*無環(huán)路：路由協(xié)議的重要約束條件之一，可以簡單地采用TTL(生存時間)來對“兜圈子”的報文進行控制，但是考慮協(xié)議的效率通常采用更好的辦法。

*需求驅動(反應式)：路由協(xié)議并不主動維護路由表，當發(fā)現(xiàn)無法得到目的結點路由后，需求驅動路由協(xié)議發(fā)送路由請求信息。

*路由表驅動(先應式)：路由協(xié)議主動維護網絡中的拓撲，定時更新路由表，有的協(xié)議還有更新觸發(fā)功能，可以更快地發(fā)現(xiàn)新的可用路由。

*安全問題：安全性是Ad hoc網絡面臨的另一個大難題。Ad hoc網絡使用無線通信技術，容易被監(jiān)聽和干擾。加上Ad hoc網絡一般被使用在特殊場合(軍事、救災等)，安全問題更加突出。在無線鏈路安全性非常脆弱的情況下，路由協(xié)議的安全性對于網絡尤為重要。

*休眠期：電源能量對于基于移動網絡的終端非常重要，路由協(xié)議需要支持設備的休眠功能，不要在休眠期仍然進行路由信息的交互。

*非對稱鏈路支持：無線網絡的非對稱性必然會導致非對稱性路由，路由協(xié)議必須能夠在源結點和目的結點之間建立非對稱路由，這樣就增加了協(xié)議的復雜性。

根據路由協(xié)議的特點，提出路由協(xié)議性能測試方法。

(a) 路由協(xié)議端到端時延

測量主機之間時鐘同步是端到端測量重要的技術基礎。利用GPS、PSTN、CDMA等網絡的外部時鐘源來實現(xiàn)測量主機間同步。雖然精度高，但費用昂貴且在測量主機數量很大時難于實現(xiàn)。一般端到端時延測量可以通過RTT(Round Trip Time)獲得，但是由于無線鏈路廣泛存在著鏈路非對稱的情況，所以需要測量端到端的單向時延。[10][11][12]對單向時延的測量提出了基于某種最優(yōu)化目標來確定測量參數的方法。根據不同的要求，提出相應的優(yōu)化目標，利用線性規(guī)劃模型進行求解，最終到達提高單向時延參數精度的目的。

(b) 路由發(fā)現(xiàn)時間

12 ALT="圖3：“直線型”結點分布。">

當路由協(xié)議發(fā)現(xiàn)當前維護的路由條目失效或無法為目的結點提供可用路由時，會主動發(fā)出路由請求，網絡中的鄰居結點會根據路由請求的內容或者轉發(fā)路由請求，或者向源結點報告可用路由，或者什么都不做[1][7]。從發(fā)送路由請求到得到可用路由的時間就是路由重建時間，如圖2所示。

(c) 路由協(xié)議的效率

網絡中路由信息占信息傳輸總量的百分比。對于路由協(xié)議的效率參數，可以利用外部測量的方法，即在網絡中加入監(jiān)聽結點并分析數據內容的方法來計算路由協(xié)議效率。但是這種方法的開銷較大，如果對協(xié)議本身進行修改，本地計算可以大大減少網絡開銷。在路由協(xié)議中，在路由維護信息送到發(fā)送緩沖區(qū)之前進行修改：

#IFDEF CACULATE_EFFECIECY

int num_of_routing_message++

#ENDIF

這樣利用下面的公式：

12 ALT="">

可以得到路由協(xié)議的效率參數。

網絡綜合性能評估

網絡綜合性能評估必須充分考慮不同網絡環(huán)境對網絡性能的影響，結合網絡應用背景對網絡性能進行綜合評估。

網絡環(huán)境對網絡性能的影響主要有以下幾個方面：

(a) 網絡覆蓋范圍：結點的數目和分布率(通常結點較多的情況下)決定了網絡覆蓋范圍，

(b) 網絡連通性：通常是網絡結點的平均鄰居數目，在圖論的意義下，也就是網絡結點的“度”[13]。

(c) 拓撲變化頻率：表征了網絡拓撲變化速率。

(d) 鏈路容量：有效的鏈路帶寬，即可利用的鏈路帶寬，標稱帶寬與可用帶寬的差別主要由于接入協(xié)議，編碼和數據幀封裝時導致的錯誤。

(e) 非對稱鏈路：網絡中非對稱鏈路數量會對網絡性能產生影響。同時，不同的路由協(xié)議在非對稱鏈路網絡中的工作效率也是不同的。

(f) 網絡流量模型：路由協(xié)議在平衡流量網絡或突發(fā)性網絡中的表現(xiàn)是不同的。

(g) 移動性：結點的移動特性對網絡的性能也會產生影響，例如在軍事上，通信結點一般都以集群的方式向某一方向或地域運動，所以同一集群各個結點之間移動的相關性較強，而不同集群之間的移動相關性則不是十分明顯。這一點對路由協(xié)議性能產生重要影響。

(h) 休眠結點數量：網絡中休眠結點數量多可以延長終端的待機時間，同時可以有效地減小網絡中路由協(xié)議的開銷。協(xié)議對休眠結點的處理方法以及效率也是影響網絡性能的因素之一。

在特定的網絡應用環(huán)境中，可能會具有上述某些重要特征，不同的網絡應用會對不同層次的協(xié)議有不同的性能要求。對同一層次的協(xié)議，不同的應用也會對各個網絡性能參數有不同的要求。例如：協(xié)議A在大規(guī)模網絡中性能非常好，協(xié)議B在小規(guī)模網絡中性能優(yōu)于A，如果應用場合是一個小規(guī)模網絡，應該優(yōu)先選擇B協(xié)議。實際測量中的情況不是這個簡單，需要多方面的性能綜合考慮，可以根據應用特點的不同，給網絡不同的性能測試內容賦予不同的加權值，這樣可以更加客觀地反映網絡的性能，如表1所示。

其中，

12 ALT="">

所以加權值是歸一化參數。

如果各個參數之間具有相關性，如移動性和連通性之間相互影響，簡單地用加權值并不能科學地反映網絡性能差別，利用層次分析法[9]，可以更加準確地對不同網絡的性能進行評估。

網絡測試環(huán)境設計

1. 結點分布范圍與移動特性

分布范圍一般有三種模式：

(a) 均勻分布(隨機分布)

所有結點的地理位置是完全隨機的。在給定范圍內，如30km*30km或50km*50km，結點可以在任何位置請求與其它結點進行通信，同時網絡結點以隨機的方式移動。

(b) 直線型分布

12 ALT="圖4：“星型”分布。">

直線型分布也是一種非常常用的結點分布形式，如車隊在高速公路行進中的情況就符合這種分布特征。實現(xiàn)的這種分布式特征的方法是，讓結點在一個狹長區(qū)域隨機移動。用這種方式下，結點之間的通信主要依靠直線拓撲結構的網絡，如圖3所示。。

(c) 星型分布

在許多分區(qū)結構的網絡中，成員結點與群首通信組成了本地網絡，也稱為“群”或“簇”。這樣的網絡，結點分布是一種星形分布。如圖4所示：

分群網絡中，可以構造多個星型分布的子網，這樣可以測試網絡在分群網絡的性能。

2. 網絡結點的流量

網絡結點的流量也會對網絡性能產生影響。在測試平臺中，針對不同的應用環(huán)境，應該配置不同的結點數據流量規(guī)則，以合理地對網絡性能進行測試。

(a) 均衡流量

這種方式下，各個結點流量均相同，從應用層看，就是各個結點的業(yè)務類型相同或相近，需要提供相同的數據傳輸業(yè)務保障能力。

(b) 非均衡流量

在某些應用場合，如軍事應用中，各個結點之間所承擔的任務不同，結點的數據業(yè)務需求也不相同。例如，指揮官所在的網絡結點可能需要大容量的實時數據業(yè)務，而單兵使用的通信結點可能數據量較小。對應于分群網絡，群首結點的數據通信需求要遠大于成員結點。

本文小結

由于網絡的分布性，結點移動的不確定性和無線鏈路的不可靠性，Ad Hoc網絡性能測試成為目前無線網絡技術中的難點之一，本文討論了Ad Hoc網絡測試的體系結構。同時認為由于Ad Hoc網絡的具體應用場合不同，要根據網絡特點對相關內容進行測試，同時要對測試內容綜合評估。網絡測試環(huán)境對網絡性能有重要影響，所以要針對具體的網絡應用背景選擇網絡環(huán)境進行性能測試。只有各個方面的因素綜合考慮，并采用不同的測試環(huán)境和測試手段才能夠準確地評估Ad Hoc網絡的性能。

參考文獻

[1]、 Elizabeth M.Royer and C-K Toh. A Review of Current Routing Protocols for Ad hoc Mobile Wireless Networks. IEEE Personal Communications Magazine, April 1999

[2]、V.Bharghavan,A.Demers,S.Shenker,and L.Zhang. MACAW:A Media Access Protocol for Wireless LANs. Proceeding of ACM SIGCOMM 1994

[3]、 J.Deng and Z.J.Haas. Dual Busy Tone Multiple Access: A New Medium Access Control for Packet Radio Networks. IEEE ICUPC'98, October 1998

[4]、Matthias Grossglauser, Davis Tse, Mobility Increases the Capability of Ad Hoc Wireless Networks, INFOCOM2001.

[5]、Zygmunt. J. Hass, A New Routing Protocol for the Reconfigurable Wireless Networks, http://www.ee.cornell.edu/~hass/wnl.html

[6]、 Josh Broch , David A Maltz, etc . A Performance Comparison Of Multi-Hop Wireless Ad Hoc Network Routing Protocols, MobiCom'98 1998 ACM

[7]、David B. Johnson . "Routing in Ad Hoc Networks of Mobile Hosts" Computer Science Department 1991

[8]、RFC 2501 Ad Hoc Network Route Measurement

[9]、姜啟源編著 《數學模型》清華大學出版社 北京 1999年

[10]、 MOON, S.B., SKELLY, P.AND TOWSLEY, D., Estimation and Removal of Clock Skew form Network Delay Measurements. In proceedings of the IEEE INFOCOM Conference on Computer Communications, page 227-234, March 1999

[11]、 DYER, M.E., Linear Time Algorithms for Two and Three Variable Linear Programs. SIAM Journal on Computing. 14 (1983) , 759-776.

[12]、 MEGIDDO, N., Linear Time Algorithms for Linear Programs in R3 and Related Problems. SIAM Journal on Computing 12 (4) (1983) , 759-776.

[13]、陳志平，徐宗本編著 《計算機數學－計算復雜性理論與NPC、NP難問題的求解》科學出版社　北京　2001年