有線/無線Ad Hoc混合網絡的路徑帶寬測量

摘 要:Ad Hoc Probe是目前測量無線網絡路徑帶寬的主要方法，由于發送探測分組數目固定，當負載較輕時，僅需要幾組探測報文就能夠獲得正確的樣本，所以限制了無線Ad Hoc網絡的動態性。針對Ad Hoc Probe算法的不足，提出了Ad Hoc TP算法，一次發送三個報文，組成兩個報文對，通過比較兩個報文對的時間間隔和最小時延和提高樣本的過濾速度，從而使測量速度更快。QualNet仿真的結果表明，Ad Hoc TP算法能夠正確地測量出有線/無線Ad Hoc混合網絡的帶寬，而且測量速度較快。

關鍵詞:包對; 路徑帶寬; Ad Hoc網絡; Ad Hoc Probe

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

文章編號:1004-373X(2010)07-0081-04

Measurement of Path Bandwidth in Wired/Wireless Ad Hoc Hybird Networks

LI Wei-ping， ZHANG Lei

(Institute of Communication Engineering， PLA Science and Technology University， Nanjing 210007， China)

Abstract: Ad Hoc Probe is a main method for the path bandwidth measurement in wireless network. Since the number of sending probing packets in the Ad Hoc Probe algorithm is fixed， a few probing packets is needed when the load is light， so it limits the dynamics of Ad Hoc network. To solve these problems， a new model of Ad Hoc TP algorithm is proposed. The Ad Hoc Probe sends three back-to-back packets to form two pairs， at the same time， and the filtering velocity of samples and accelerate the measuring speed is improved by comparing with the time-interval and the minimum one-way delay of two parirs. The results of Qualnet simulation prove that the Ad Hoc TP can measure the bandwidth accurately in wired/Ad Hoc networks and has fast measuring velocity.

Keywords: packet pair; link bandwidth; Ad Hoc network; Ad Hoc Probe

0 引 言

Ad Hoc網絡是一種不需要中心控制以及基礎設施支持，由移動節點構成的無線網絡[1]。它具有組網靈活、快捷等特點，被認為是將來最有競爭力的通信方式之一。Ad Hoc網絡在國防戰備、災難救助、臨時性的會議等場合下具有無法比擬的優勢，具有廣闊的應用前景。

隨著針對Ad Hoc網絡的研究逐步深入，人們發現Ad Hoc網絡作為一個獨立網絡時，應用十分有限，不能發揮它的最大優勢。如果把它接入有線網作為延伸，那么對于Ad Hoc網絡的應用將有一個質的飛躍。比如:在軍事應用中，高層指揮所的指揮網絡通常由高速局域網和Ad Hoc組成;民用的Ad Hoc網絡通過無線路由器接入因特網等。如何了解混合網絡的性能，如何發現瓶頸鏈路等一些問題，這都對混合網絡測量提出了新的要求，例如從單一的Ad Hoc網絡測量拓展到Ad Hoc網絡及有線網組成的混合網絡測量。

本文對有線網絡和Ad Hoc組成的混合網絡的帶寬測量進行研究，提出了Ad Hoc TP測量算法并進行了驗證。結果表明，此方法能夠快速、準確地測量出路徑帶寬。

1 測量原理

PP模型最早用于網絡擁塞控制[2]，后來經過R.Carte，V.Paxson，K.Lai和C.Dovrolis等人對模型的不斷完善和發展[3-6]，使得PP模型成為測量網絡帶寬最有效的模型之一。Ad Hoc Probe[7]是目前測量Ad Hoc網絡路徑帶寬的最常用方法，它以PP模型為基礎，繼承了Capprobe[8]的優點，不僅克服了報文對技術在重負載時測量不精確的缺點，而且保證了測量精度。

在網絡負載較輕時，一般僅僅需要幾個報文對就能夠獲得正確的樣本，但是Ad Hoc Probe仍然固定地進行200次采樣來尋找時延和最小的樣本，這樣造成測量時間固定且較長，因而不能適應Ad Hoc網絡的動態性。如果能夠實時地知道已經獲得了正確的樣本，就不需要再繼續發送額外的探測報文，這樣既可以縮短測量時間，又可以減小對帶寬資源的浪費。縮短測量時間，可以更好地適應Ad Hoc網絡的動態性，更好地滿足Ad Hoc帶寬受限的特點。針對Ad Hoc Probe的缺點，提出了Ad Hoc TP(Triple-probe Packets)算法。

先來分析一個報文對的測量:設第二個報文大小為L，所經過的鏈路帶寬為C0，則報文對經過這條鏈路后的時間間隔變為Δ0=L/C0，在一般情況下，如果在進入一條容量為Ci的鏈路前，報文對的間隔為Δin，則通過這條鏈路后，時間間隔為Δout=max(Δin，L/Ci)。在報文對經過一條路徑上的若干條鏈路后，在接收方得到的間隔為ΔR=maxi=0，1，…，HLCi=Lmini=0，1，…，H(Ci)=LC，其中C就是這條路徑端到端的路徑帶寬，即C=L/ΔR。

TP算法描述:TP算法在發送端所使用的測量分組不再是單個的分組對，而是由三個連續數據包組成，稱之為三元組。三元組中每個包的長度分別是L1，L2，L3，其中L1

Cb=L2+βΔ1=L3+βΔ2

(1)

并且向發送端報告結果。發送端收到結果后結束測量，如果時延和不是最小的，則繼續測量。

測量過程中的問題處理:

(1) 如果兩個探測包對中插入相同的背景流量

這里認為當兩個探測包對沒有受到背景流量的影響時，在接收端兩個探測包對的間隔就會相等。但是還有一種情況，就是當兩個探測包對中插入相同的背景流量時，在接收端兩個探測包對的間隔也是相等的。所以仍保留單向時延和最小的判斷標準。這樣就可以排查出雖然兩個時間間隔相等，但實際收到相同背景流量影響的樣本。

(2) 長時間內一直找不到符合條件的樣本

在網絡負載較重的情況下，探測包對受到背景流量的影響概率將會很大，所以有可能很長時間內一直找不到符合條件的樣本。為了減小測量工作對網絡的影響，將設定一個探測報文對發送上限，以控制測量的時間。將這個上限設置為100，發送端只發送100組探測報文對，如果接收端一直沒有接收到正確的樣本，則在接收到第100組報文組合后(根據序列號)，根據已有的測量數據，選取時延和最小的那個樣本，并將其作為正確的樣本，計算路徑帶寬。

(3) 探測報文對發送速率問題

如果探測報文的發送速率過快，雖然可以縮短測量時間，但會對網絡產生較大的干擾，并且容易引起網絡擁塞，從而可能影響測量的準確性。相反，如果發送的速率過慢，則會延長測量時間，不能滿足Ad Hoc網絡拓撲動態性的特點。在Ad Hoc Probe中，每一組探測報文對由2個報文組成，其發送速率為4組/s，改進后的報文對由3個報文組成。參考Ad Hoc Probe并通過實際仿真分析，探測報文對發送速率定為2組/s。因為設定了探測報文對的發送上限為100組，所以測量時間最大不超過50 s。

(4) 系統時鐘同步問題

Ad Hoc TP算法不需要發送方、接收方的時間同步，假設他們兩者的時間差為u，對于第i個包來說，發送時間為Tsend，i。接收時間:第一個包為Trecv1，i，第二個包為Trecv2，i，所以測量的時延和為

S′i及實際的時延和Si為:

S′i= (Trecv1，i-Tsend，i) + (Trecv2，i-Tsend，i)

Si=(Trecv1，i-Tsend，i-u)+(Trecv2，i-Tsend，i-u)

=S′i-2u

由上式可知，S′i，Si兩者的差值恒定為2u。如果Sk最小，則S′k也是最小，過濾不是最小值的S′k就可以得到正確的樣本，而計算路徑容量時，用的是差值，即:

Δ=(Trecv1，i-Tsend，i-u)-(Trecv2，i-Tsend，i-u)

=(Trecv1，i-Tsend，i)-(Trecv2，i-Tsend，i)

這樣就消除了u的差值，對最終的路徑容量的測量沒有影響，因此Ad Hoc TP算法不必在乎發送方和接收方的時間同步，這對最終的測量結果沒有影響。

2 仿真驗證

2.1 無線Ad Hoc網絡帶寬的理論分析

Ad Hoc網絡路徑帶寬不同于傳統的有線網。在有線網中，一條路徑的帶寬是由組成該條路徑的所有鏈路中帶寬最“窄”的那段鏈路所決定的。當一條路徑確定后，其路徑帶寬就是一個確定的值。但是在Ad Hoc網絡中，路徑帶寬并不是簡單地等于最“窄”的那段鏈路的帶寬。由于所有節點共享無線信道，所以在多跳的情況下，必須考慮到無線信道復用對于路徑帶寬的影響。要對Ad Hoc網絡路徑帶寬的測量技術進行研究，就必須首先確定Ad Hoc網絡路徑帶寬的理論值，否則將無法判斷測量結果是否正確。

先對鏈狀拓撲的路徑帶寬進行分析。如圖1所示，節點間距離為200 m，節點的傳輸范圍均是250 m，干擾范圍是550 m。只有1號節點發送數據，其他節點只進行接收或是轉發。

圖1 鏈形Ad Hoc網絡拓撲

當場景中只有兩個節點，不存在信道復用，也就是沒有節點沖突的影響時，則在多跳網絡中，所有節點共享無線信道，此時，路徑帶寬一定會受到影響。由文獻[10]中，對于多跳鏈路路徑帶寬進行分析可知:當1號節點發送，3號節點接收時路徑鏈路帶寬也就是一跳路徑帶寬的1/2;當1號節點發送，4號節點接收時，路徑鏈路帶寬也就是1跳路徑帶寬的1/3;當1號節點發送，5號節點接收時，路徑鏈路帶寬也就是一跳路徑帶寬的1/4;當1號節點發送，6號節點接收時，路徑鏈路帶寬也就是一跳路徑帶寬的1/4;跳數再增大時，由于距離較遠的節點可以同時使用信道，所以路徑帶寬的最小理論值就是一跳路徑帶寬的1/4。

2.2 驗證鏈狀混合網絡中TP算法的可行性

把這種鏈狀拓撲的Ad Hoc網絡接入有線網后，不難發現，在Ad Hoc網絡內部，路徑帶寬并不會受到這種接入的影響，也就是說路徑帶寬理論值不會發生變化。下面驗證TP算法的可行性。

使用QualNet仿真軟件[11]對算法的有效性進行了仿真驗證。IEEE 802.11b的傳輸范圍設為250 m，干擾范圍設為550 m。信道衰減模型選擇的是TWO-RAY GROUND，網絡負載設置為符合泊松分布的VBR流。

仿真場景如圖2所示，節點1到AP之間為有線網絡，假設為100 Mb/s以太網。Ad Hoc網絡部分各節點之間的距離都是200 m，各鏈路都基于IEEE 802.11b協議，傳輸速率為2 Mb/s，網絡層使用AODV協議，傳輸層使用UDP協議。IEEE 802.11協議默認參數值見表1。

表1 IEEE 802.11協議參數表

參數名稱參數值參數名稱參數值

DIFS /μs50HMAC /B34

SIFS /μs10HIP /B20

RTS /B20HUDP /B8

CTS /B14CWmin /B31

ACK /B14Slot /μs20

圖2 混合網絡拓撲圖

當Ad Hoc網絡路徑為一跳時，也就是節點1經過AP到節點2這條路徑上，在沒有背景流量干擾的情況下，發起測量的仿真結果如圖3，圖4所示。

圖3 一跳路徑帶寬理論值及不同大小

探測包對測量值

圖4 一跳路徑帶寬理論值及無線網絡

部分發起的測量值

從圖3中可以看到，從節點1發起的混合網絡測量與從AP發起的純Ad Hoc網絡測量基本一致。說明基于包對的路徑帶寬測量技術能夠很好地適用于上述混合網絡。隨著應用層數據的增大，路徑帶寬也隨之增大，但是測量值與理論值之間存在著一定的偏差。經分析認為，偏差是由于幀間間隔引起的，在前面的理論值分析過程中忽略了幀間間隔的影響。圖4是從無線節點2發起的對混合網絡的測量，從結果看算法仍然有效。綜合來看，該算法不論是從有線網絡部分發起測量，還是從Ad Hoc網絡部分發起測量，在一跳情況下都能夠正確測量出網絡路徑帶寬。

再來看看多跳情況下TP算法的效果。網絡拓撲如圖2不變，網絡各參數保持不變。使用固定大小的探測包對，設置為1 472 B。在多跳情況下的測量結果如圖5，圖6所示。

從圖5中可以看出，在不同跳數的情況下，從節點1發起的混合網絡測量結果與從AP發起的純Ad Hoc網絡測量結果仍然基本保持一致。說明該路徑帶寬測量算法在混合網絡中確實是正確有效的。隨著跳數的不斷增加，測量結果也正確地反映了路徑帶寬的變化趨勢，與前面的理論推導基本吻合。同理從Ad Hoc網絡部分發起測量的仿真結果，如圖6所示。從仿真結果看，在不同跳數的情況下，從Ad Hoc網絡部分發起的測量結果與從有線網絡部分發起測量結果基本一致，都能較為準確地測量出網絡路徑帶寬。

圖5 不同跳數下，固定大小探測包對仿真結果

圖6 不同跳數下，Ad Hoc網絡部分

發起的測量仿真結果

綜合以上結果，當有線網絡部分的鏈路帶寬遠遠大于Ad Hoc網絡部分的鏈路帶寬時，混合網絡路徑帶寬基本不受有線網絡部分的影響，不論是從有線網絡部分發起測量，還是從Ad Hoc網絡部分發起測量，在假設的這種基于IEEE 802.11b的多跳混合網絡模型中，基于包對的路徑帶寬測量技術完全適用，能夠準確、有效地測量出網絡路徑帶寬。

2.3 改進算法的優勢

在不同的網絡負載情況下，分別對一跳和三跳混合網絡進行路徑帶寬測量，比較Ad Hoc Probe算法與改進后的Ad Hoc TP算法測量結果，如圖7和圖8所示。

圖7 一跳時，改進后的Ad Hoc Probe和

Ad Hoc Probe的比較

由仿真結果可以清楚地看到，在測量精度方面，改進后的TP算法與Ad Hoc Probe算法基本一致，證明了對算法改進的正確性。圖9，圖10分別給出兩種算法的測量所需要的數據包和耗時對比。

圖8 三跳時，改進后的Ad Hoc Probe

和Ad Hoc Probe的比較

圖9 發送探測報文數量圖

圖10 測量周期圖

顯而易見，改進后的算法在保證測量精確度的前提下，大大縮短了測量路徑帶寬所需的時間，并且減少了探測報文的發送數量，降低了測量算法對網絡的干擾。

2.4 性能分析

由Ad Hoc TP算法原理可知，L1很小，第一個分組傳輸很快，可以有效地解決插入背景流的影響，僅用式(1)就可以快速地過濾出正確的樣本，從而縮短了測量周期，在保證精度的前提下，能夠快速地得到測量結果。在負載較輕時，僅需要幾個分組就能夠快速地測量出帶寬值，從而大大提高了效率。在負載很高的情況下，也能夠在一定程度上減少測量報文的個數，降低測量算法對網絡的干擾，得到正確的結果。

3 結 語

本文對基于IEEE 802.11b的Ad Hoc網絡鏈路帶寬進行了理論分析，在此基礎之上，深入研究了路徑帶寬測量技術，并將以往的純Ad Hoc網絡測量拓展到由Ad Hoc網絡與有線網所組成的混合網絡測量。不僅通過仿真驗證了基于包對的路徑帶寬測量技術在混合網絡測量中的正確性，還改進了Ad Hoc Probe測量算法，使得測量更加快速、高效，同時還減小了對網絡的干擾，通過多個不同場景的仿真驗證了算法，結果表明算法是有效可行的。

參考文獻

[1]PAXSON V. RFC-2330: Framework for IP performance metrics[S].[S.l.]: Internet Society， 1998.

[2]JACOBSON V. Congestion avoidance and control[C]//Stanford: Proceedings of the ACMSIGCOMM， 1988: 314-329.

[3]CARTER R L， ROVELLA M E.Measuring bottleneck link speed in packet-switched networks[J]. Performance Evaluation， 1996， 27(28): 297-318.

[4]PAXSON V. Measurement and analysis of end-to-end internet dynamics[D]. [S.l.]:[s.n.]， 1997.

[5]LAI K， BAKER M. Ettimer: a tool for measuring bottleneck link bandwidth[DB/OL]. http://mosquitonet. stanford. edu/laik. 2001.

[6]DOVROLIS C， RAMANATHAN P， MOORE D. What do packet dispersion techniques measure[C]//AK. Proceeding of IEEE INFOCOM， USA: AK， 2001:905-914.

[7]RENESSE R， GHASSEMIAN M， FRIDERIKOS V. Adaptive admission control for Ad Hoc and sensor networks providing quality of service[R]. London: King College， 2005.

[8]ARLOS P， FIEDLLER M， NILLSON A. A distributed passive measurement infrastructure[J]. Passive and Active Network Measurement， 2005， 3431: 215-227.

[9]張文杰，錢德沛，伍衛國，等.一種非均勻包對序列帶寬測量方法[J].西安交通大學學報，2002，36(10): 1045-1048.

[10]OZDEMIR M， MCDONALD A B. A queueing theoretic model for IEEE 802.11 DCF using RTS/CTS. Local and Metropolitan Area Networks， 2004: 33-38.

[11]SNT. QualNet Simulator[EB/OL]. [2006-06-14]. http://www.qualnet.com.