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

程德懌 喬 健* 朱俊峰

1(上海市信息網(wǎng)絡(luò)有限公司 上海 200081)

2(上海自足網(wǎng)絡(luò)科技有限公司 上海 200082)

0 引 言

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

1 算法的關(guān)鍵技術(shù)創(chuàng)新

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

2 擁塞避免算法設(shè)計

2.1 概 要

構(gòu)建基于虛擬傳輸協(xié)議的無線ad hoc網(wǎng)絡(luò)擁塞控制機制，包括以下步驟：

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

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

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

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

5) 建立VTP的分組丟棄重傳機制，通過最大分組丟棄參數(shù)的設(shè)置，實現(xiàn)VTP虛擬傳輸協(xié)議的網(wǎng)絡(luò)媒體通道。

2.2 系統(tǒng)架構(gòu)

VTP是虛擬傳輸協(xié)議，其介于網(wǎng)絡(luò)IO層和應(yīng)用層之間，實現(xiàn)了網(wǎng)絡(luò)擁塞控制等功能，VTP建立在用戶數(shù)據(jù)報協(xié)議層之上，實現(xiàn)了向操作系統(tǒng)開放Socket接口，同時也為應(yīng)用層提供了VTP Interface的接口，通過VTP可以為應(yīng)用提供可靠的擁塞控制虛擬連接。VTP協(xié)議的層次結(jié)構(gòu)如圖1所示。

圖1 VTP協(xié)議的層次結(jié)構(gòu)

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

圖2 基于VTP協(xié)議的擁塞控制系統(tǒng)結(jié)構(gòu)

2.3 擁塞避免算法模型

2.3.1建立時間到達模型

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

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

(1)

發(fā)送長度為L的數(shù)據(jù)幀到鏈路容量為C的路徑中，所用時間ts為：

(2)

內(nèi)部時間建模如下：

(3)

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

(4)

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

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

(5)

(6)

(7)

(8)

式中：Zi是觀測值與預(yù)測值之間差值。

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

(9)

(10)

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

(11)

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

(12)

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

2.3.2模型的帶寬判斷和控制

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

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

圖3 速率控制系統(tǒng)狀態(tài)轉(zhuǎn)換

(13)

(14)

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

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

(15)

(16)

式中：Ni是過去T秒接收到的幀數(shù)量；Lj是幀j的大小。當(dāng)帶寬過用被觸發(fā)時，系統(tǒng)就轉(zhuǎn)移到遞減狀態(tài)，接收端可用帶寬估計將會遞減：

(17)

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

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

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

(18)

Asi≤Ai

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

3 實 驗

3.1 實驗環(huán)境

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

3.2 算法模型性能測試

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

圖4 帶寬估計曲線擬合圖

從實驗仿真結(jié)果來看，基于虛擬傳輸協(xié)議的無線ad hoc網(wǎng)絡(luò)擁塞控制機制能較精確地估計帶寬，在此基礎(chǔ)上達到帶寬自適應(yīng)，擁塞控制目的。

3.3 網(wǎng)絡(luò)轉(zhuǎn)發(fā)速率對比測試

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

圖5 20 Mbit/s流量下網(wǎng)絡(luò)轉(zhuǎn)發(fā)速率對比測試

圖6 60 Mbit/s流量下網(wǎng)絡(luò)速率對比測試

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

3.4 分組丟棄測試

使用網(wǎng)絡(luò)流量測試儀分別以20 Mbit/s和60 Mbit/s帶寬發(fā)送多路模擬H.264編碼視頻和G711編碼語音，持續(xù)時間為1 h。結(jié)果如表1所示。

表1 分組丟棄測試表

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

4 結(jié) 語

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