Ad Hoc網絡中基于概率預測的擁塞控制算法

彭玉艷，杜文才，任 佳

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

0 引 言

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

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

1 問題分析

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

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

本文使用的參數定義如下：

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

2 概率預測擁塞控制算法

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

圖1 PPCC算法過程

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

2.1 貝葉斯網絡的構建

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

（1）數據處理

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

式中：a，b，c——常數，通常根據實踐經驗進行指派。

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

（2）貝葉斯網絡結構及參數的學習

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

2.2 概率預測模型的構建

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

（1）數據處理

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

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

（2）貝葉斯網絡推理的改進

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

根據構建的貝葉斯網絡和式 （3）可以推導得出使用實時數據進行貝葉斯網絡推理式 （4）

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

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

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

2.3 擁塞控制算法的實現

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

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

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

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

3 實驗仿真

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

圖3 貝葉斯網絡結構

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

圖4 預測網絡出現狀態3的概率變化情況

圖5 發送速率變化情況

根據每個時段預測網絡狀態3 的概率對網絡的發送速率進行調整，得到發送速率變化情況 （如圖5所示）。

圖5顯示發送速率在開始調整時出現阻尼振蕩的狀況，但是經調整很快就獲得了相對較優的發送速率后進入穩定狀態。

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

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

圖6 平均延時變化情況

圖7 平均吞吐量變化情況

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

4 結束語

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

［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）.［易發勝，趙繼東.利用時延特性的模糊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網絡的跨層優化擁塞控制 ［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）.［肖秦琨，高嵩.貝葉斯網絡在智能信息處理中的應用 ［M］.北京：國防工業出版社，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－hop 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.