基于數據分組到達時間的無線ad hoc擁塞避免算法

程德懌 喬 健* 朱俊峰

1(上海市信息網絡有限公司 上海 200081)

2(上海自足網絡科技有限公司 上海 200082)

0 引 言

在無線ad hoc網絡中由于無線帶寬有限、無線傳輸機制限制，很容易出現帶寬擁塞。通常在網絡發生擁塞時可采取的避免措施主要是減少數據發送速率，技術手段有數據窗口調整和擁塞通告。設計思路是: 如果網絡沒有出現擁塞，逐漸增加發送窗口，當出現網絡擁塞比如分組丟棄時，則縮減發送窗口，由此減少發送到網絡中的通信數據。窗口擁塞控制算法及改進算法無一例外都是將分組丟棄作為擁塞的信號，然后降低發送速率[1]。無線ad hoc網絡中傳輸多媒體流會因為網絡中諸如節點移動、網絡擁塞、信道故障等原因造成帶寬時變。而以不同形式的媒體編碼不能迅速適應帶寬時變，其帶寬的需求通常以離散和大跨度變更，流媒體對于分組丟棄敏感，而實時性又阻止了分組丟棄重傳機制的使用[2]。此外當某個節點發生擁塞而附近節點可能網絡狀況良好時，減少擁塞節點的數據窗口會降低網絡的性能和發送效率，因此特別需要一種新的無線ad hoc網絡擁塞控制算法。本文提出的擁塞避免算法方案，考慮了ad hoc網絡自身的特點，借鑒目前各種擁塞控制技術的優缺點,在滿足通信數據可靠性、實時性指標的前提下可以使得網絡通信性能達到最佳。

1 算法的關鍵技術創新

本文新設計了一種VTP(Virtual Transmission Protocol)虛擬傳輸協議控制模型，其在實時傳輸協議RTP(Real-time Transport Protocol)的基礎上重新封裝了協議的對象(發送端(VTP Sender)，接收端(VTP Receive)，管道(VTP pipe))。并引入了新的擁塞避免算法。新算法針對無線ad hoc網絡，使用基于通信數據分組到達時間的卡爾曼濾波分析預測函數并結合分組丟棄來判斷是否擁塞，使得傳輸協議能在解決帶寬變更帶來的擁塞問題的同時，滿足實時通信的要求。本文算法通過對擁塞控制建模和優化，較好地解決了在無線自組網絡中實時流媒體傳輸的帶寬適應性難題。

2 擁塞避免算法設計

2.1 概 要

構建基于虛擬傳輸協議的無線ad hoc網絡擁塞控制機制，包括以下步驟：

1) 在無線ad hoc網絡中的數據分組接收端觀察報文接收時序，建立時間到達模型，本文認為報文到達時間差分與時間戳差分是一個高斯白噪聲隨機過程。

2) 在數據分組接收端對時間到達模型中偏移量mi估計值與門限值進行比較，作為判斷帶寬過用和帶寬少用指示。

3) 在數據分組接收端建立速率控制器，使其具有3種狀態：遞增，遞減和保持。將鏈路質量估計值與擁塞閾值進行比較和判斷,以遞歸自適應的可用帶寬估計的方法實現狀態轉換。

4) 在數據發送端，擁塞控制器接收端反饋的環回時間、分組丟棄率和可用帶寬估計，通過計算對發送隊列進行帶寬控制，當通道隊列足夠大的時候，由接收端計算出的可用帶寬評估作為有效反饋，而隊列非常短時由網絡分組丟棄檢測作為帶寬過用判斷依據。

5) 建立VTP的分組丟棄重傳機制，通過最大分組丟棄參數的設置，實現VTP虛擬傳輸協議的網絡媒體通道。

2.2 系統架構

VTP是虛擬傳輸協議，其介于網絡IO層和應用層之間，實現了網絡擁塞控制等功能，VTP建立在用戶數據報協議層之上，實現了向操作系統開放Socket接口，同時也為應用層提供了VTP Interface的接口，通過VTP可以為應用提供可靠的擁塞控制虛擬連接。VTP協議的層次結構如圖1所示。

圖1 VTP協議的層次結構

基于VTP協議的擁塞控制系統結構如圖2所示， VTP系統結構由發送端速率控制、VTP發送器、VTP接收器及管道(VTP pipe)組成。發送端速率控制對象內部實現帶寬估計、速率控制、分組丟棄重傳，以及碼率控制等子對象類型，VTP發送端在發送端速率控制下發送數據分組。將不同功能的對象分開獨立設計，實現了RTP的虛擬化，應用層只需要維護數據的完整，由VTP層接管物理連接的所有資源，使得擁塞控制管理更精確和高效。

圖2 基于VTP協議的擁塞控制系統結構

2.3 擁塞避免算法模型

2.3.1建立時間到達模型

為了建立基于時間到達的擁塞避免數學模型，本文通過數據報文的到達時間差異判斷網絡帶寬的擁塞程度，作為發送端速率控制提供擁塞控制的依據[3-5]。基于接收幀的時序，通過連續更新網絡參數的估計值實現自適應濾波。在接收端的輸入數據分組，每個數據幀擁有相同的時間戳Ti。每幀被指定接收時間ti，ti是整個數據幀被接收后所記錄的到達時間并忽略分組丟棄。如果ti-ti-1>Ti-Ti-1，即如果幀的到達時間差分大于時間戳差分，則相對于前一幀，此幀是延遲的。相對內部到達時間di定義為：

di=(ti-ti-1)-(Ti-Ti-1)

(1)

發送長度為L的數據幀到鏈路容量為C的路徑中，所用時間ts為：

(2)

內部時間建模如下：

(3)

式中：wi是高斯白噪聲隨機過程w的樣本，是關于鏈路容量C、當前背景流量Xi和當前發送速率Ri的函數;Li是報文的長度，ΔLi是相鄰西幀報文長度的差值。如果網絡隊列中的數據增加則wi增加、如果網絡隊列中數據正在清空wi將會減少，否則wi為零。從wi中分離mi使得隨機過程零均值，得到等式如下:

(4)

式中：di是相對于前一幀報文到達時延；鏈路容量C、偏移量mi是當時二個隨機過程量；Vi為零均值帶有高斯白噪聲的觀測值。參數di和ΔLi可以通過每一完整的幀fi(i>l)獲取，可以估計C和mi，并利用C和mi檢測是否處于擁塞狀態，這些參數通過卡爾曼濾波得到估計。

對于實時獲得的受噪聲污染的離散觀測時延數據，使用卡爾曼濾波算法進行線性、無偏、最小誤差方差的最優估計。卡爾曼濾波遞推過程，分為預測和更新校正兩階段。其中時間更新方程(預測階段)如式(5)-式(8)所示。

(5)

(6)

(7)

(8)

式中：Zi是觀測值與預測值之間差值。

卡爾曼濾波器狀態更新方程(更新校正階段)如式(9)和式(10)所示。

(9)

(10)

式中：Ei-1和Ei代表i-1和i時刻的后驗估計誤差；I為與狀態向量同維度的單位矩陣；Qi表示過程激勵噪聲的協方差，它是狀態轉移矩陣與實際過程之間的誤差。一般在某些穩定的過程可以假定它是固定的矩陣，通過調整合適的Q值使濾波器獲得更好的性能，Q通常采用對角矩陣并取小值，以利于快速收斂。式(10)得到卡爾曼濾波遞歸更新估計，其計算結果更新校正了誤差協方差及系統的不確定度，并可用于下一個周期的運算。

(11)

利用同樣的方式Qi被設計為主對角矩陣：

(12)

使用幀速率來測量使得帶寬過用探測器能夠在低速率和高速率一樣快速的響應。由此本文建立了時間到達模型。

2.3.2模型的帶寬判斷和控制

擁塞探測工作原理是:將偏移量mi估計值與門限值γ1進行比較，當估計值高于門限值時指示為網絡擁塞[9-11]，僅此信號指示并不能夠使得網絡擁塞探測器觸發速率控制系統，還需要額外附加條件，即至少γ2ms并且至少γ3幀，此時網絡擁塞信號將被觸發，當接收端檢測到網絡擁塞，對于可用帶寬的評估會隨之降低。如果偏移量mi估計在最后一次更新中下降，盡管上述條件全部滿足網絡擁塞檢測依然不會被觸發。同理當估計偏移量mi<γ1,即鏈路質量評估值小于擁塞閾值，指示為非網絡擁塞狀態，這也表示網絡隊列中的數據正在被清空，表明實際可用帶寬大于可用帶寬估計。如果既不是網絡擁塞狀態也不是非網絡擁塞狀態，則探測器將處于正常狀態。只要網絡擁塞探測器處于非擁塞狀態或正常狀態，接收端速率控制系統就會增加在接收端上的可用帶寬估計，通過不斷增加探測器將會檢測到網絡擁塞。通過遞歸的方式實現了自適應的可用帶寬估計[12-14]。

每當接收端報告到來的時候，算法就會被運行，運行的時間間隔一般在Tmin_fb時間間隔和Tmax_fb時間間隔內，如果在2Tmax_fb時間間隔內沒有接收到報告信息，這表明至少丟失兩個返回報告信息，那么算法會認為在這段時間間隔內的分組已經丟失，并將發送速率減半。

圖3 速率控制系統狀態轉換

(13)

(14)

式中：RTT為往返時延；B、b、d、c1和c2為預先設置的參數。

由于速率控制系統依靠通道網絡擁塞狀態來計算當前可用帶寬評估，必須確保估計值不能偏離發送端的實際發送速率，因此，如果發送端不能產生接收端請求的相應的碼率媒體流，那么可用帶寬就保持在一個給定的邊界內。因此定義一個門限：

(15)

(16)

式中：Ni是過去T秒接收到的幀數量；Lj是幀j的大小。當帶寬過用被觸發時，系統就轉移到遞減狀態，接收端可用帶寬估計將會遞減：

(17)

(1) 如果通過接收端的反饋報告信息，計算出2.5%～10%分組丟棄率，發送端可用帶寬Asi將保持不變。

(2) 如果超過10%的分組丟棄，可用帶寬估計將會被更新為Asi=Asi-1(1-0.5p)，其中p是分組丟棄率。

(3) 如果分組丟棄率低于2%，可用帶寬將會被更新為Asi=1.07(Asi-1+1 000)。

(18)

Asi≤Ai

式中：b是ack分組的數量；trto為超時時間；s為平均的報文分組長度；R為環回時間。發送端帶寬估計值不會超過接收端帶寬估計值，不會低于TFRC公式計算出的帶寬估計值。

3 實 驗

3.1 實驗環境

實驗環境主要配置如下：Sprient C50，IXIA 400T 網絡流量測試儀，10個無線ad hoc路由節點，ad hoc無線路由節點基于Cortex-A73，內存64 MB，4 GB存儲，無線射頻采用ADI的HMC系列模塊，OS系統基于OpenWrt搭載擁塞避免算法軟件模塊。將ad hoc無線路由節點組成ad hoc網絡，使用網絡流量測試儀發送網絡流量，對ad hoc網絡進行性能測試。本文的實驗數據來源于Sprient、EFXO和IXIA測試儀表，并根據本實驗需求，通過OriginLab數據分析軟件對原始的結果樣本重新進行了標注和處理。

3.2 算法模型性能測試

通過對ad hoc無線移動網絡設置固定帶寬L1:1 Mbit/s、L2:2 Mbit/s、L3:3 Mbit/s,并設置分組丟棄率為5%，網絡延時為雙向延時，單向延遲為5 ms。圖4描述了不同帶寬下，不同分組長度與延遲的關系。

圖4 帶寬估計曲線擬合圖

從實驗仿真結果來看，基于虛擬傳輸協議的無線ad hoc網絡擁塞控制機制能較精確地估計帶寬，在此基礎上達到帶寬自適應，擁塞控制目的。

3.3 網絡轉發速率對比測試

使用網絡流量測試儀分別以20 Mbit/s和60 Mbit/s流量發送多路模擬H.264編碼視頻和G711編碼語音。測試結果如圖5和圖6所示，其中實線代表使用了擁塞避免算法的測試結果速率，點線代表無擁塞避免算法的測試結果速率。

圖5 20 Mbit/s流量下網絡轉發速率對比測試

圖6 60 Mbit/s流量下網絡速率對比測試

從仿真測試結果分析，使用了擁塞避免算法的網絡吞吐量大，而且抖動較小。無論在小帶寬還是在大帶寬情況下都能更好地估算帶寬使用情況。

3.4 分組丟棄測試

使用網絡流量測試儀分別以20 Mbit/s和60 Mbit/s帶寬發送多路模擬H.264編碼視頻和G711編碼語音，持續時間為1 h。結果如表1所示。

表1 分組丟棄測試表

分組丟棄統計結果顯示在不同帶寬下使用擁塞避免算法具有更低的丟棄率。

4 結 語

本文提出一種適用于無線自組ad hoc網絡的擁塞避免算法，該算法方案充分考慮了無線自組通信網絡自身結構特點和特征，解決了流媒體在無線自組網絡中傳輸要求的實時性難題和帶寬變更帶來的擁塞問題。本文將擁塞控制數學模型與控制器相結合并建立對應關系，通過速率控制系統形成負反饋的閉環控制，提高了系統的穩定性。所采取的控制方法在保證通信數據實時性和可靠性的前提下提高了網絡的通信性能。通過實驗證明了本文算法能有效控制擁塞，同時具備可拓展性。