Ad Hoc網(wǎng)絡中基于概率預測的擁塞控制算法

彭玉艷，杜文才，任 佳

（海南大學 信息科學技術學院，海南 海口570228）

0 引 言

在無線Ad Hoc網(wǎng)絡中，由于資源的限制，數(shù)據(jù)包經(jīng)常會在任意的轉發(fā)節(jié)點出現(xiàn)擁塞。擁塞會導致高丟包率、長延時，浪費網(wǎng)絡可用資源［1］。TCP 協(xié)議中的擁塞控制算法有效地避免了網(wǎng)絡擁塞崩潰，但是TCP擁塞控制策略趨于保守，限制了網(wǎng)絡的吞吐量［2］，針對這個問題，研究者提出多種改進的擁塞控制協(xié)議，其中有TCP NewReno［3］、TCP SACK［4］、TCP Vegas［5－6］等。TCP NewReno 和TCP SACK 協(xié)議通過發(fā)送節(jié)點接收到的ACK 確認包來判斷網(wǎng)絡狀態(tài)。但在Ad Hoc網(wǎng)絡中，可能由于鏈路問題發(fā)生丟包使網(wǎng)絡不能及時接收到應答，因此，這些協(xié)議不能準確判斷Ad Hoc網(wǎng)絡擁塞狀態(tài)。TCP Vegas協(xié)議通過觀測往返時延比較實際吞吐量與期望吞吐量的差值，以判斷網(wǎng)絡狀態(tài)［5，6］，更適合于無線Ad Hoc網(wǎng)絡。近年來，一些學者針對Ad Hoc網(wǎng)絡提出了IEDCA［7］、CL－QF［8］、CCOC［9］等跨層擁塞控制方法，但這些算法需要增加更多的專用接口，設計難度較大，擴展性較差。而貝葉斯網(wǎng)絡采用有向圖來描述概率關系的理論［10］，在解決許多實際問題的過程中，貝葉斯網(wǎng)絡可以從不完全的、不精確的或不確定的知識和信息中做出推理和判斷，具有很強的魯棒性和通用性［10，11］。由于無線Ad Hoc網(wǎng)絡獲得的數(shù)據(jù)并不十分精確，有學者提出使用貝葉斯網(wǎng)絡擁塞識別方法進行擁塞控制［12，13］，并已驗證該方法能夠判斷網(wǎng)絡的擁塞。但是，現(xiàn)有的方法并沒有考慮到所獲得參數(shù)具有很多種數(shù)值狀態(tài)，如果直接使用這樣的數(shù)據(jù)構建貝葉斯網(wǎng)絡具有很大的難度，而使用簡單分類的數(shù)據(jù)進行推理又不能夠利用網(wǎng)絡實時數(shù)據(jù)的微小差別提前預測，避免網(wǎng)絡發(fā)生擁塞。

因此，本文針對使用TCP Vegas協(xié)議的Ad Hoc網(wǎng)絡進行分析，提出了基于概率預測的擁塞控制算法 （PPCC）。該算法首先利用模糊方法處理數(shù)據(jù)，然后，根據(jù)處理后的數(shù)據(jù)構建貝葉斯網(wǎng)絡。為了更好地利用網(wǎng)絡實時參數(shù)的微小差別來預測網(wǎng)絡擁塞狀態(tài)概率，本文改進了貝葉斯網(wǎng)絡的推理過程。最后根據(jù)預測概率調整網(wǎng)絡參數(shù)，達到擁塞控制的目的。

1 問題分析

在無線Ad Hoc網(wǎng)絡中，當?shù)竭_某一節(jié)點的數(shù)據(jù)包總量大于它的緩存空間時，節(jié)點就會出現(xiàn)擁塞，然后開始丟包［14］。TCP擁塞控制協(xié)議通過重傳可以避免數(shù)據(jù)包丟失，但是會增加數(shù)據(jù)包的延時，造成網(wǎng)絡資源浪費和降低網(wǎng)絡服務質量。為了提高網(wǎng)絡服務質量，需要提前檢測網(wǎng)絡狀態(tài)，避免網(wǎng)絡由于負載過重產(chǎn)生擁塞。目前，研究者提出很多檢測網(wǎng)絡擁塞狀態(tài)的指標，如平均隊列長度、數(shù)據(jù)包延時、剩余緩存空間等［14］。但是，單獨使用某一指標不能準確判斷網(wǎng)絡擁塞狀態(tài)，同時，考慮到某一刻的參數(shù)具有多種誤差對網(wǎng)絡狀態(tài)有很大影響。因此，本文使用指定時間段的多個指標構建貝葉斯網(wǎng)絡找出它們之間的關系，用于預測出網(wǎng)絡擁塞狀態(tài)。

通過對無線Ad Hoc網(wǎng)絡進行分析發(fā)現(xiàn)網(wǎng)絡的擁塞狀態(tài)與平均延時、抖動、平均吞吐量和平均隊列長度有關，所以可用平均延時和抖動表示當前網(wǎng)絡的運行狀態(tài)，用平均吞吐量表示網(wǎng)絡資源的利用情況，用平均隊列長度表示網(wǎng)絡緩存中的數(shù)據(jù)量。因此，使用這些參數(shù)構建貝葉斯網(wǎng)絡。

本文使用的參數(shù)定義如下：

平均時延：在定義時間段內，統(tǒng)計目的節(jié)點接收到的所有數(shù)據(jù)包時延的平均值。其中，本文使用的數(shù)據(jù)包時延定義為源節(jié)點發(fā)送出一個數(shù)據(jù)包到目的節(jié)點接收到該數(shù)據(jù)包之間的時間差，記為x1；抖動：在定義時間段內，數(shù)據(jù)包時延最大值減去平均時延與平均時延減去時延最小值的較大值，記為x2；平均吞吐量：在定義時間段內，目的節(jié)點接收到的數(shù)據(jù)量除以該時間段的時間，記為x3；平均隊列長度：在定義時間段內，每一次發(fā)送、接收或丟失數(shù)據(jù)包時，都統(tǒng)計沒有被發(fā)送節(jié)點接收的數(shù)據(jù)包的數(shù)量，最后將所有的數(shù)據(jù)包數(shù)相加除以統(tǒng)計次數(shù)，記為x4。

2 概率預測擁塞控制算法

PPCC算法是基于貝葉斯網(wǎng)絡的概率預測模型算法。該算法需要利用網(wǎng)絡參數(shù)構建貝葉斯網(wǎng)絡的概率預測模型以用于對網(wǎng)絡的實時參數(shù)進行推理預測來調整網(wǎng)絡參數(shù)。該算法過程如圖1所示。

圖1 PPCC算法過程

其中，PPCC算法由3個部分構成：第1部分通過對已有網(wǎng)絡參數(shù)進行處理和學習，構建貝葉斯網(wǎng)絡；第2部分通過對實時網(wǎng)絡參數(shù)進行處理，然后使用改進的貝葉斯網(wǎng)絡推理方法來預測網(wǎng)絡的實時擁塞狀態(tài)；第3部分根據(jù)預測得到的網(wǎng)絡擁塞狀態(tài)，調整實時運行網(wǎng)絡的參數(shù)，緩解網(wǎng)絡擁塞。下面將詳細介紹PPCC算法的實現(xiàn)過程。

2.1 貝葉斯網(wǎng)絡的構建

貝葉斯網(wǎng)絡是由節(jié)點和數(shù)條有向邊組成的帶有概率注釋的無環(huán)圖。雖然通過問題分析可以得到構建貝葉斯網(wǎng)絡的節(jié)點，但是，不能直接使用這些參數(shù)來構建貝葉斯網(wǎng)絡。因此，需要首先對數(shù)據(jù)進行處理；對處理后的數(shù)據(jù)進行學習，才能得到貝葉斯網(wǎng)絡。

（1）數(shù)據(jù)處理

由于網(wǎng)絡運行獲得的數(shù)據(jù)有太多種數(shù)值狀態(tài)，使用這樣的數(shù)據(jù)構建貝葉斯網(wǎng)絡具有一定的難度，所以，使用三角模糊化隸屬函數(shù)對數(shù)據(jù)進行了模糊化處理，公式如下

式中：a，b，c——常數(shù)，通常根據(jù)實踐經(jīng)驗進行指派。

對以上4個參數(shù)分別指定模糊區(qū)間進行三角模糊化處理，求得其隸屬度，記為d（xij）。d（xij）表示參數(shù)xj為狀態(tài)i的隸屬度，其中xij表示參數(shù)xj為狀態(tài)i。使用隸屬度最大的狀態(tài)ij為參數(shù)xj的狀態(tài)，這樣就獲得了貝葉斯網(wǎng)絡的輸入?yún)?shù)（i1，i2，…，im）（其中，m＝4），將所有已知的參數(shù)進行處理后就可以得到輸入矩陣Im。

（2）貝葉斯網(wǎng)絡結構及參數(shù)的學習

通過對已有網(wǎng)絡參數(shù)進行處理獲得構建貝葉斯網(wǎng)絡的輸入矩陣Im，就可以使用已有成熟貝葉斯網(wǎng)絡學習算法來構建貝葉斯網(wǎng)絡。貝葉斯網(wǎng)絡的構建過程為：使用K2算法獲得貝葉斯網(wǎng)絡結構；使用最大似然估計算法進行參數(shù)學習，獲得貝葉斯網(wǎng)絡。由于K2算法和最大似然估計算法是貝葉斯網(wǎng)絡中大家比較熟悉和常用的算法，具體的過程可見文獻 ［13，14］。

2.2 概率預測模型的構建

文獻 ［1］提出使用估計隊列長度來識別網(wǎng)絡的擁塞等級，以為網(wǎng)絡的平均隊列長度能夠表示網(wǎng)絡的擁塞程度。但在實時運行的系統(tǒng)中獲得網(wǎng)絡的平均隊列長度具有一定的難度。因此，本文考慮使用貝葉斯網(wǎng)絡來推理預測網(wǎng)絡的平均隊列長度。

（1）數(shù)據(jù)處理

為了更準確地使用獲得的實時參數(shù)進行推理，使用式（2）將隸屬度d（）進行歸一化處理，得到參數(shù)xj為狀態(tài)i的概率p（）；然后，使用所得到的概率值進行推理對參數(shù)進行模糊處理后，可以獲得已知所有參數(shù)分別屬于某個狀態(tài)的概率為

式中：p（xi11，xi22，…，xinn）——對于所有的j∈｛1，2，…，n｝，參數(shù)xj——狀態(tài)ij時的概率。

（2）貝葉斯網(wǎng)絡推理的改進

貝葉斯網(wǎng)絡推理是在給定貝葉斯網(wǎng)絡模型的條件下，根據(jù)已知參數(shù)，利用條件概率的計算方法，計算出感興趣節(jié)點的概率。如果利用已有的貝葉斯網(wǎng)絡推理方法，只能計算出平均隊列長度在雙親節(jié)點屬于某一狀態(tài)時的概率值，即p（yk｜i1，i2，…，in）。然而，在實時運行的網(wǎng)絡系統(tǒng)所獲得參數(shù)可能屬于多個狀態(tài)，因此，為了更好地利用實時數(shù)據(jù)，必要對貝葉斯網(wǎng)絡推理進行改進。

根據(jù)構建的貝葉斯網(wǎng)絡和式 （3）可以推導得出使用實時數(shù)據(jù)進行貝葉斯網(wǎng)絡推理式 （4）

式中：y——要預測的節(jié)點 （這里為平均隊列長度，即x4），x1，x2，…，xn——y 的雙親節(jié)點的值。

例如：已知y 的雙親節(jié)點x1，x2且均有2 種狀態(tài) （1，2），根據(jù)式 （4）可以求得y 為狀態(tài)1的概率計算公式如式（5）。

根據(jù)上一部分構建的網(wǎng)絡可以得到p（yk｜i1，i2，…，in），同時使用式 （2）獲得實時數(shù)據(jù)屬于每個狀態(tài)的概率p（xij）；然后，使用式 （4）就可以計算得到Ad Hoc網(wǎng)絡在實時數(shù)據(jù)情況下平均隊列長度分別屬于各種狀態(tài)的概率值。

2.3 擁塞控制算法的實現(xiàn)

擁塞控制的主要目的就是最好地利用網(wǎng)絡中的可用資源，同時，保持網(wǎng)絡的負載量低于且盡可能接近網(wǎng)絡可以承受容量的限度。本文通過對使用CBR 流量發(fā)生器的發(fā)送速率進行調整，使得網(wǎng)絡負載量滿足擁塞控制的目的。根據(jù)網(wǎng)絡運行獲取的實時數(shù)據(jù)使用上一部分構建的概率預測模型來預測網(wǎng)絡中平均隊列長度所屬狀態(tài)概率；根據(jù)預測結果實時調整網(wǎng)絡的發(fā)送速率，緩解網(wǎng)絡擁塞。調整實時網(wǎng)絡參數(shù)的擁塞控制算法實現(xiàn)偽代碼如圖2所示。

圖2 基于概率預測模型的擁塞控制算法偽代碼

其中：vmax為最大發(fā)送速率；vmin為最小發(fā)送速率；Δv為調整步長；p30為當前時段平均隊列長度為狀態(tài)3的概率；p3i為前i時段平均隊列長度為狀態(tài)3的概率 （i＝1，2，…，5）；count為調整階段用來判斷網(wǎng)絡是否進入穩(wěn)定狀態(tài)的指標；vnext為下一時段網(wǎng)絡的發(fā)送速率；vcurrent為當前時段網(wǎng)絡的發(fā)送速率；vpast為前一時段網(wǎng)絡的發(fā)送速率。

參數(shù)調整算法分為了調整和穩(wěn)定2個階段，這2個階段是不可逆的。在調整階段，根據(jù)網(wǎng)絡平均隊列長度為3的概率，依據(jù)條件調整網(wǎng)絡的發(fā)送速率和相關參數(shù)，同時保證網(wǎng)絡的發(fā)送速率在最小發(fā)送速率與最大發(fā)送速率之間；而調整步長的變化使得網(wǎng)絡可以在一定時間獲得較優(yōu)發(fā)送速率，進入穩(wěn)定階段。在穩(wěn)定階段，網(wǎng)絡根據(jù)6 個時段網(wǎng)絡平均隊列長度為3的概率，判斷是否將要發(fā)生擁塞來調整發(fā)送速率。為了確保服務質量，調整步長不宜過大，以避免網(wǎng)絡發(fā)送速率大幅度變化引起網(wǎng)絡振蕩，降低服務質量。

3 實驗仿真

本文使用NS2.35 軟件進行實驗仿真。網(wǎng)絡拓撲結構為3個節(jié)點的線性結構。其中，節(jié)點1 為發(fā)送節(jié)點，節(jié)點2為轉發(fā)節(jié)點，節(jié)點3 為接收節(jié)點。同時，網(wǎng)絡的發(fā)送范圍半徑為250 m，干擾范圍半徑為550 m，網(wǎng)絡可用帶寬為1 Mb。在進行仿真時，路由層使用AODV路由協(xié)議，傳輸層使用TCP Vegas協(xié)議。設定獲取數(shù)據(jù)的 時 間 段 為1s，將x1，x2，x3模 糊 化 為2 類，x4模 糊 化為3類。使用模糊化的數(shù)據(jù)構建貝葉斯網(wǎng)絡，得到如圖3所示的網(wǎng)絡結構。

圖3 貝葉斯網(wǎng)絡結構

為了驗證PPCC 算法，設定最大發(fā)送速率vmax為400 KB／s，最小發(fā)送速率vmin為200KB／s，調整步長初始值Δv為20KB／s。分別針對網(wǎng)絡初始發(fā)送速率為200KB／s，337 KB／s和400KB／s進行仿真。其中，337KB／s是經(jīng)過多次仿真實驗獲得此網(wǎng)絡結構下的較優(yōu)發(fā)送速率。在仿真過程所有時段中，根據(jù)概率預測模型計算得到實時運行網(wǎng)絡中平均隊列長度為狀態(tài)3的概率，結果如圖4所示。

圖4 預測網(wǎng)絡出現(xiàn)狀態(tài)3的概率變化情況

圖5 發(fā)送速率變化情況

根據(jù)每個時段預測網(wǎng)絡狀態(tài)3 的概率對網(wǎng)絡的發(fā)送速率進行調整，得到發(fā)送速率變化情況 （如圖5所示）。

圖5顯示發(fā)送速率在開始調整時出現(xiàn)阻尼振蕩的狀況，但是經(jīng)調整很快就獲得了相對較優(yōu)的發(fā)送速率后進入穩(wěn)定狀態(tài)。

使用本文提出算法 （PPCC）調整網(wǎng)絡發(fā)送速率與未用本文算法 （PPCC－N）進行仿真，獲得的網(wǎng)絡平均延時和平均吞吐量的變化情況如圖6、圖7所示。

根據(jù)圖6 發(fā)現(xiàn)使用PPCC 算法對發(fā)送速率進行調整，使得網(wǎng)絡達到穩(wěn)定狀態(tài)后，平均延時處于相對較小的值；而未使用PPCC算法的情況下，當網(wǎng)絡的負載大于其承受能力范圍時，網(wǎng)絡的平均延時會處于較大值狀態(tài)。從圖7可以看出，使用PPCC算法可以使網(wǎng)絡在達到穩(wěn)定狀態(tài)后，平均吞吐量保持相對較大的值；而對于未用PPCC 算法的情況，當網(wǎng)絡的負載遠小于其承受能力時，會使網(wǎng)絡的吞吐量較小，導致網(wǎng)絡資源浪費。

圖6 平均延時變化情況

圖7 平均吞吐量變化情況

綜上所述，PPCC 算法能夠很好地利用網(wǎng)絡實時運行中獲取的數(shù)據(jù)，準確地預測網(wǎng)絡擁塞情況；能夠在一定時間內將網(wǎng)絡調整到穩(wěn)定狀態(tài)，使網(wǎng)絡達到平均吞吐量較高、平均延時較低的理想狀態(tài)，能滿足對服務質量要求較高的數(shù)據(jù)流，使網(wǎng)絡資源得到更好的利用。

4 結束語

為了更好的利用網(wǎng)絡的實時數(shù)據(jù)，對貝葉斯網(wǎng)絡的推理進行改進，利用預測結果使用本文提出的速率調整方法對網(wǎng)絡發(fā)送速率進行調整，避免網(wǎng)絡由于負載過重發(fā)生擁塞的情況。仿真實驗結果表明：PPCC算法能夠根據(jù)實時網(wǎng)絡擁塞狀況自適應的調整網(wǎng)絡發(fā)送速率，在短時間內使得網(wǎng)絡獲得較優(yōu)的發(fā)送速率，且保持網(wǎng)絡的平均延時較小，平均吞吐量較高，從而使網(wǎng)絡獲得較高的服務質量。同時，PPCC算法不局限于TCP Vegas中，還可以用于使用CBR數(shù)據(jù)流的任何傳輸協(xié)議中。然而，該算法需要對數(shù)據(jù)進行模糊化處理，不同網(wǎng)絡結構的模糊處理區(qū)間不同對網(wǎng)絡發(fā)送速率的影響，還需要進一步研究。

［1］Senthikumaran T，Sankaranarayanan V.Dynamic congestion detection and control routing in Ad Hoc networks［J］.Journal of King Saud University－Computer and Information Sciences，2013，25 （1）：25－34.

［2］YI Fasheng，ZHAO Jidong.Fuzzy TCP congestion control algorithm using delay ［J］.Journal of University of Electronic Science and Technology of China，2010，39 （2）：260－265 （in Chinese）.［易發(fā)勝，趙繼東.利用時延特性的模糊TCP 擁塞控制算法［J］.電子科技大學學報，2010，39 （2）：260－265.］

［3］Nadim Parvez，Anirban Mahanti，Carey Williamson.An analytic throughput model for TCP NewReno ［J］.IEEE／ACM Transactions on Networking，2010，18 （2）：448－461.

［4］Mehta RD，Vithalani CH.Distinguishing congestion loss from random loss on wireless erroneous links to improve performance of wireless TCP－SACK ［C］／／International Conference on Communication Systems and Network Technologies，2012：383－387.

［5］Neda Alipasandi，Shahram Jamali.An improvement over TCP Vegas by solving rerouting problem ［C］／／AWERProcedia Information Technology ＆Computer Science，2011：82－86.

［6］Shubhada P Deshmukh，Sanjesh S Pawale.TCP Vegas rerouting detection and improving performance ［J］.International Journal of Wired and Wireless Communications，2012，1 （1）：11－14.

［7］Mbarushimana C.A cross－layer TCP enhancement in QoS－aware mobile Ad Hoc networks ［J］.Computer Networks，2013，57 （1）：286－301.

［8］Evangelos Papapetrou，Panos Vassiliadis，Efthymia Rova，et al.Cross－layer routing for peer database querying over mobile Ad Hoc networks［J］.Computer Networks，2012，56 （2）：504－520.

［9］XU Weiqiang，WANG Yaming，YU Chenghai，et al.Crosslayer optimal congestion control scheme in mobile Ad Hoc networks［J］.Journal of Software，2010，21 （7）：1667－1678（in Chinese）.［徐偉強，汪亞明，俞成海，等.移動Ad Hoc網(wǎng)絡的跨層優(yōu)化擁塞控制 ［J］.軟件學報，2010，21 （7）：1667－1678.］

［10］XIAO Qinkun，GAO Song.Application of Bayesian network in intelligent information processing ［M］.Beijng：National Defence Industry Press，2012 （in Chinese）.［肖秦琨，高嵩.貝葉斯網(wǎng)絡在智能信息處理中的應用 ［M］.北京：國防工業(yè)出版社，2012.］

［11］Dojer N，Bednarz P，Podsiadlo A，et al.BNFinder2：Faster Bayesian network learning and Bayesian classification ［J］.Bioinformatics，2013，29 （16）：2068－2070.

［12］Ersyhad Sharifahmadian，Shahram Latifi.Cognitive congestion control for data portals with variable link capacity ［J］.Int Jouranl Communications Network and System Sciences，2012，5 （8）：481－489.

［13］Giorgio Quer，Henmanth Meenakshisundaram，Bheemarjuna R Tamma，et al.Using Bayesian networks for congnitive control of multi－h(huán)op wireless networks［C］／／Military Communications Conference，2010：201－206.

［14］Senthil Kumaran T，Sankaranarayanan V.Early congestion detection and adaptive routing in MANET ［J］.Egyptian Informatics Journal，2011，12 （3）：165－175.