Ａｄ ｈｏｃ網絡中的自適應退避算法的研究

摘要：本文提出了一種適用于高等級節點的二進制負指數退避算法BNEB，驗證了競爭窗口平均值較小的節點信道競爭能力較強的結論，并根據此結論，針對多跳 Ad hoc網絡中由于MAC層競爭導致的擁塞問題提出了兩種具有擁塞控制功能的退避算法RBAB和CABEB，在節點發生擁塞時調整其分組進入速率和轉發速率，能夠提高網絡的端到端吞吐量并有效緩解網絡擁塞。

關鍵詞：Ad hoc網絡；二進制負指數退避算法；自適應退避算法

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)27-1899-06

Research on Adaptive Baekoff Algorithms in AD hoc Networks

HE Jun1，2，LI Hui2

(1.Computer Science Technology Department，East China Normal University，Shanghai 200241，China;2.Urumqi Railway Transportation School Xinjiang，Urumqi 830011，China)

Abstract:This paper proposes a binary negative exponential backoff (BNEB) algorithm which applies for high- level node，validate that the node with smaller average contention window has higher channel contending ability. And based on this，two adaptive backoff algorithms RBAB and CABEB are proposed，which can adjust the packet receiving and forwarding rate of the congested node when congestion occurs and can effectively alleviate the network congestion.

Key words: Ad hoc networks; BNEB; adaptive baekoff algorithms

1 引言

基于IEEE802.11的無線多跳Ad hoc網絡中，每個節點都可能充當路由器的角色轉發其他節點的數據。由于節點傳輸數據時需要競爭共享信道，因此每個節點的吞吐量不僅與信道容量有關，還與其鄰居節點的傳輸有關。對于一個多跳業務流來說，不僅要與鄰居節點中的其他流競爭信道，而且在流內部每跳傳輸也要與其上游節點和下游節點競爭，導致一些節點發生擁塞，這對于使用共享信道的 Ad hoc網絡來說，相當于浪費了網絡資源，嚴重影響了 Ad hoc網絡的吞吐量，尤其是端到端的吞吐量。在Ad hoc網絡中，無線鏈路共享相同的信道資源。這樣在 Ad hoc網絡中傳輸業務流時相近的節點就會在MAC層發生競爭。MAC層對共享信道的競爭有兩種情況：一種是流內競爭，一種是流間競爭。

流內競爭是指在同一個流的路徑上在相互干擾范圍之內的節點間的競爭，如圖1所示，其中內環表示節點有效傳輸范圍，外環表示節點的干擾范圍。流間競爭是指不同的流在經過相同區域時出現的競爭，如圖2所示，流間競爭也會嚴重降低網絡的吞吐量。

以上兩種競爭在使用共享信道的多跳Ad hoc網絡中普遍存在，競爭導致一些節點擁塞，而且這些節點由于進入的分組不斷累積造成競爭惡化，最終丟棄分組，浪費了網絡資源。這樣不僅嚴重影響端到端的吞吐量，而且由于引入了大量的排隊時延從而增加了端到端時延。

IEEE802.11中的MAC協議使用退避策略減小發生沖突的可能性。現有的退避算法中，尚沒有考慮節點擁塞問題，本文首先提出了一種適用于高等級節點的退避算法，驗證了平均退避窗口小的節點信道競爭能力強的結論，然后據此提出了兩種擁塞自適應退避算法RBAB和CABEB，它們分別在節點的下一跳發生擁塞時減緩競爭窗口的變化和增大競爭窗口的最小值，以此使得上一跳節點的競爭窗口增大，從而減小其分組發送速率，避免擁塞惡化和帶寬資源浪費，相當于在MAC層引入了簡單的擁塞控制機制。

2 擁塞自適應退避算法思路

2.1 基本原理

IEEE802.11DCF采用了一種隨機訪問機制。當節點有新的數據包需要發送時，它首先監測信道，如果信道持續空閑一段時間(DIFS)在RTS/CTS模式下，發送RTS幀；否則，節點繼續監測信道，在忙時監測期間，當信道空閑的總時間等于DIFS時，節點在發送RTS幀之前在[0，CW]之間隨機選擇一延遲時間（這就是DCF的沖突避免特性)進行退避，其中CW稱為競爭窗口，這一隨機延遲時間我們稱之為退避時間。由于退避時間平均分布在[0，CW]之間，因此競爭窗口CW在總體上反映了退避時間的大小。對于第一次發送嘗試，CW = CWmin，在每次發送失敗之后，CW加倍，直到CW = CWmax=2m* CWmin。(m為最大退避次數)。同時，節點將選擇的退避時間賦值給延時計數器。之后，當節點監測到信道空閑時間達一個時隙時，延時計數器減1；當監測到信道忙時，延時計數器保持，并在信道空閑時間等于DIFS時重新激活延時計數器。當延時計數器的值等于0時，節點發送RTS幀。可見，在節點競爭信道的過程中，退避時間的大小可以反映節點接入信道的能力，退避時間越小，節點搶占信道的能力就越強；相反，退避時間越大，信道競爭能力就越弱。

控制發送節點的分組發送速率是解決擁塞控制的一個重要方法。為了驗證擁有較小退避窗口的節點在網絡中擁有較強的信道競爭能力，提出了一種二進制負指數退避算法BNEB(Binary Negative Exponential Backoff)。該算法應用于高等級節點，將高等級節點的最大競爭窗口設為普通節點的最小競爭窗口，初次接入信道所用的競爭窗口初始值為最大競爭窗口值，發生碰撞時競爭窗口按照二進制負指數規律減小，在發送成功時重置為最大的競爭窗口值。即

可以看出，使用BNEB退避算法時高等級節點的競爭窗口最大值CWmin，最小值為CWmin /2m，競爭窗口在網絡中一直保持最小，因此平均退避時間也最小。

下面分析高等級節點應用BNEB算法時網絡的端到端飽和吞吐量，考慮n個普通等級發送節點和1個高等級節點組成的Ad hoc網絡，所有節點均在相互的傳輸范圍之內。每個節點鏈路處于飽和狀態，即每個節點成功傳輸一個分組后，需要為下一個分組的傳輸立即參與信道的競爭。普通等級節點和高等級節點都可根據文獻[1]建立Markov模型，設τc、ρc為普通等級節點的發送概率和沖突概率，τh、ph為高等級節點的發送概率和沖突概率，可以得出：

pc表示普通等級節點在一個時隙內發生沖突的概率，即n-1個剩余普通等級節點加上高等級節點中至少有一個節點同時也發送分組的概率；ph表示高等級節點在一個時隙內發生沖突的概率，即n個普通等級節點中至少有一個同時也發送分組的概率。因此：

聯立(2)(3)(4)(5)構成一個非線性系統，其中τc、τk、ρc、ρc和ρk為未知變量，可以使用數值方法求解。

設Ptr為在一個隨機選擇的時隙內網絡中至少有一個節點發送分組的概率，則有：

設Ps1，為網絡中所有節點成功發送一個分組的概率，Ps2為高等級節點成功發送一個分組的概率，則有：

設S1、S2為網絡歸一化的系統吞吐量和高等級節點的吞吐量，則有：

其中Ts和Tc分別為信道由于一次成功的發送和一次碰撞所導致的忙期， E[P]表示平均分組長度，σ表示一個空時隙的時間。

下面通過仿真研究BNEB退避算法的性能，使用的仿真工具是美國UCLA大學的GloMosim(Global Mobile Information System Simulator)“全球移動信息系統仿真平臺”[2-3]，該軟件提供了一種靈活的仿真環境，可以有效的利用并行計算來減少大型移動通信網絡的仿真時間。這里使用的仿真場景大小為300m×300m，各個節點都在相互的傳輸范圍之內，分別考慮節點數量為5、10、15、20、25、30的情況下網絡的性能，其中有一個節點為高等級節點，使用BNEB退避算法，其他均為普通等級節點，使用BEB算法。節點物理層采用DSSS，無線鏈路速率為2Mbps，競爭窗口參數為CWmin為32，CWmax為1024，使用RTS/CTS握手方式。每個節點均隨機選擇一個節點發送業務流，業務類型選用CBR業務，分組長度為128Bytes，每個業務流速率為400Kbps，保證網絡處于飽和狀態，每次仿真時間為300秒。

圖3顯示了節點數量不同的情況下網絡的飽和吞吐量，隨著節點數量的增加，碰撞次數增加，網絡的飽和吞吐量有微弱下降。網絡中高等級節點使用BNEB算法或者BEB算法對系統總的飽和吞吐量影響不大。

圖4顯示了高等級節點與普通等級節點的吞吐量，高等級節點使用BNEB算法時，由于競爭窗口在整個網絡中最小，信道競爭力得到提高，吞吐量要比普通節點提高很多，在節點數量較大時高等級節點吞吐量提高也較多，因為節點數量較多導致碰撞概率增加，碰撞使得高等級節點的競爭窗口更小而普通等級節點的競爭窗口更大。

圖5顯示了節點的端到端延遲，高等級節點使用BNEB算法時，端到端的延遲比普通等級節點要小，節點數量越大延遲性能改善越大。另一方面普通等級節點的延遲有所增加，但是總的來說，由于普通節點數量較多，因此結果平均后對普通節點的影響并不大。

2.2 算法思路

在單跳范圍內的Ad hoc網絡中，競爭窗口較小的節點擁有較強的信道競爭能力。將這種思路引入到多跳Ad hoc網絡中的擁塞控制機制中，通過使擁塞節點在網絡中的競爭窗口保持較小的值，使得擁塞節點的信道競爭能力增強，從而能夠增強其分組轉發能力即節點的出口速率。IEEE802.11DCF協議的BEB退避算法的工作過程可以分為兩個部分：1)發生碰撞時，競爭窗口在CW min的基礎上根據退避次數按指數規律增加；2)在分組發送成功后再降為最小值CWmin。因此我們可以通過兩種方法來增加節點的平均競爭窗口：

① 增加CWmin，即增加競爭窗口的基值；

② 使競爭窗口在分組成功發送后變化到較大的值而不是降低到最小值CWmin。

這兩種方法都可以增加擁塞節點的上游節點的競爭窗口，從而使得擁塞節點的競爭窗口在網絡中保持較小的值。

基于這兩種思路，在BEB退避算法的基礎上提出了兩種簡單的適用于多跳Ad hoc網絡的擁塞自適應退避算法。第一種是基于接收方節點控制的自適應退避算法RBAB(Receiver-based Adaptive Baekoff)，第二種是基于網絡擁塞的自適應退避算法CABEB(Congestion Adaptive Binary Exponential Baekoff)。

3 基于節點擁塞改變退避策略的退避算法RBAB(Receiver-based Adaptive Baekoff)

RBAB算法中接收方節點根據自身擁塞程度通過ACK消息反饋控制發送方節點的競爭窗口，在總體上控制節點的退避時間，能夠有效調整節點的分組發送速率，避免擁塞惡化和帶寬資源浪費，相當于在MAC層引入了簡單的擁塞控制機制。

在Ad hoc網絡中實施流量控制機制的難點主要在于兩個方面[4]：1)如何定量界定節點的擁塞程度；2)檢測到擁塞時，采取何種控制策略并盡可能降低系統帶寬開銷。

由接收端控制發送端是擁塞控制常用的方法，本文基于文獻[5]的接收端控制思路提出了一種新的基于接收方的自適應退避控制機制RBAB，在業務流傳輸過程中，接收方節點根據自身擁塞程度，通過ACK消息反饋控制其上游發送方節點的競爭窗口，改變節點的退避時間，從而改變節點的信道競爭能力，控制分組發送速率，達到擁塞控制效果。

3.1 擁塞判斷與信息反饋

節點監控擁塞狀態的方法有很多種，比如統計丟包比例、平均隊列長度、超時重傳的包數量、分組傳輸平均時延等。所有的方法都可用于RBAB算法，本文使用簡單的瞬時隊列長度L作為擁塞判斷的標準，我們參照RED[6]將節點擁塞程度分成三個等級：無擁塞、輕度擁塞和嚴重擁塞。設置兩個控制閾值Lmin和Lmax，當L≤Lmin時，判斷節點無擁塞；當L≥Lmax時，節點發生嚴重擁塞；而當Lmin

為了和IEEE802.11兼容，選擇了ACK捎帶(piggyback)的方式，在ACK消息中攜帶接收方節點的擁塞程度信息，發送方節點接收到ACK后，根據反饋的信息進行相應的競爭窗口操作。在ACK消息后面擴展了擁塞指示字段(簡稱ACK-R)，如圖6所示。

其中CI字段為接收端節點的擁塞程度指示信息，按公式(11)取值：

當接收方節點在接收到DATA后，將自身的隊列擁塞信息加上校驗和添加到ACK消息后面，以基本速率發送給發送方節點。其他監聽節點接收到ACK-R后，把它作為一個標準的ACK消息來看待，只是提取其中的Duration字段更新NAV矢量，忽略后面的擁塞指示字段。而發送方節點收到ACK后，則通過比較Checksum字段驗證CI字段的完整性，然后讀出CI字段的擁塞指示信息。

3.2 算法描述

退避算法的核心思想是在節點發生擁塞的時候，通過控制其上游節點的競爭窗口從而在總體上控制分組進入速率。具體算法如下：

1) 當發生碰撞時，競爭窗口加倍，這和BEB算法一樣

CW=min

2) 當分組發送成功，依據ACK確認消息中攜帶的擁塞指示信息來確定競爭窗口的變化規律

其中α和β是介于0和CWmin之間的常數。可以看出，在接收方節點發生擁塞時，發送方節點的競爭窗口總體上要比BEB算法中的要大，相當于總體上增加了節點的退避時間，減小了發送方節點的信道競爭能力，一定程度上減緩了發送方的發送速率。另一方面，發送方節點競爭能力的減小使得接收方節點競爭能力在一定程度上增加。這相當于降低了接收方節點入口速率，同時增加了出口速率，有利于緩解擁塞。

對于多跳網絡來說，由于減小了業務流路徑上發送方節點的分組發送速率，所以RBAB算法減小了流內競爭，另一方面，如果擁塞節點由于流間競爭使得即使競爭窗口較小仍不能及時將分組轉發出去時，RBAB算法會從擁塞節點處向源節點逐節點進行控制，逐跳減緩分組向擁塞節點的發送速率，最終使得源節點的分組發送速率降低，業務流路徑上的所有節點的擁塞都能夠得到相應的控制。而BEB算法沒有相應的控制機制，如果一個節點的擁塞不能緩解會導致其上游所有節點都會陸續發生嚴重擁塞，嚴重影響網絡的吞吐量。

4 最小競爭窗口自適應的退避算法

CABEB退避算法在節點發生擁塞時通過增大其上游節點競爭窗口的基值來調節其信道競爭力，算法基本工作過程為:在數據傳輸過程中，發送方節點(Sender)向接收方節點(receiver)發送數據，receiver監控自身的隊列擁塞狀態，并將擁塞狀態信息反饋給Sender，然后Sender根據接收到的擁塞狀態信息控制自己的最小競爭窗口，當檢測到receiver擁塞程度加劇時，增大最小競爭窗口。

4.1 擁塞判斷與信息反饋

與RBAB退避算法相同，使用瞬時隊列長度作為擁塞判斷的標準并將擁塞劃分為不擁塞、輕度擁塞和嚴重擁塞三個等級；擁塞信息反饋也使用ACK-R幀稍帶的方式。

4.2 算法描述

節點根據其下一跳節點的擁塞程度來確定最小退避窗口，設競爭窗口缺省最小值為CWmin，最大值為CWmax，CWmax =2m·CWmin，其中m為最大退避階段。CABEB退避算法可以根據下一跳節點擁塞情況描述為以下三種情況：

l) 當節點的下一跳不擁塞即ACK幀中的CI=0時，最小競爭窗口值保持不變，即為BEB退避算法：

2) 節點的下一跳節點發生輕度擁塞即ACK幀中的CI=1時，節點的最小競爭窗口加倍：

3) 節點的下一跳節點發生嚴重擁塞即ACK幀中的CI=2時，節點的最小競爭窗口再一次加倍：

5 仿真結果與分析

本節通過仿真研究RBAB、CABEB退避算法的性能，并與BEB算法作對比，使用的仿真工具是Glomosim，物理層采用DSSS，鏈路速率為2Mbps。

5.1 單跳轉發網絡拓撲仿真

仿真場景如圖7所示，n個數據源通過路由節點向一個接收節點發送數據，網絡采用靜態路由。競爭窗口參數為CWmin=32，CWmax =1024。業務類型選用CBR業務，分組長度為256Bytes，每個節點內隊列的長度為100，隊列閾值Lmin為15，Lmax為80，仿真時間為30秒。

圖8顯示了在發送節點數量n不同的情況下網絡的端到端飽和吞吐量。可以看出，CABEB算法與BEB算法在n較小時(n≤4)吞吐量基本相同，隨著發送節點數量n的增加，網絡端到端吞吐量都下降，而RBAB算法基本穩定在較大的值不變。在發送節點數相同的情況下，使用RBAB算法與CABEB算法時網絡的飽和吞吐量要遠遠大于使用BEB算法時，節點數量較多時CABEB算法的飽和吞吐量較BEB算法增加大約100%，而RBAB算法的飽和吞吐量較RBAB算法的增加量大于200%。這是因為RBAB算法與CABEB算法在路由節點擁塞時自適應地調節發送節點的競爭窗口，增加了路由節點信道競爭力，從而增加了其分組發送速率。在節點數量較多時，雖然CABEB算法通過增加CWmin增加了競爭窗口的基值，但是在節點數量較多的時候仍然不能滿足需求，由于節點數量多導致碰撞也更加頻繁，RBAB算法可以使得發送節點的競爭窗口值較大，因此對擁塞的自適應性更好。

圖9(a-c)顯示了發送節點數量n分別為2、4、6，每個節點業務速率為800KbPs時的路由節點入口速率和出口速率，800Kbps的業務速率使得網絡處于飽和狀態。從圖中可以看出使用BEB算法時路由節點的入口速率都要遠遠大于出口速率，很快造成路由節點的嚴重擁塞。對于CABEB算法，n=2和n=4時，路由節點的入口速率和出口速率大致相等，保證了進入路由節點的分組能夠被有效轉發，擁塞得到較好的控制；而在n=6時，路由節點的入口速率要大于出口速率，因此仍然發生擁塞，但是其出口速率仍然遠大于BEB算法的出口速率，因此其端到端飽和吞吐量得到提高。而對于RBAB算法，路由節點的入口速率和出口速率在發送節點數量不同的情況下都基本保持平衡，這也說明了RBAB算法對擁塞有更好的適應性。

圖10(a-c)顯示了發送節點數量n分別為2、4、6，每個節點業務速率為800Kbps時的路由節點的歸一化隊列長度變化情況，隊列長度的變化與圖10中的速率相對應。使用BEB算法時路由節點都處于嚴重擁塞狀態；對于CABEB算法，n=2時，路由節點在輕度擁塞附近變化，在n=4時在嚴重擁塞附近變化，n=6時一直處于嚴重擁塞；對于RBAB算法，路由節點一直在輕度擁塞范圍內變化。從隊列變化的幅度看，BEB算法和CABEB算法的隊列幅度抖動較小，RBAB隊列抖動幅度較大。

5.2 多跳轉發網絡拓撲仿真

仿真場景如圖11所示，6個數據源兩級轉發節點向一個目的節點10發送業務數據，網絡采用靜態路由。圖中節點9為網絡的瓶頸節點，很可能出現擁塞。協議參數及業務參數設定均與上節相同，仿真時間為30秒。

圖12顯示了網絡的端到端吞吐量隨網絡負載的變化關系，從圖中可以看出，當網絡負載較小時，三種算法的吞吐量相同，這是由于此時網絡中沒有節點發生擁塞，RBAB和CABEB算法都按照BEB算法的模式工作。隨著網絡負載的增加，網絡出現擁塞，由于BEB算法沒有針對擁塞的調整能力，擁塞對吞吐量影響最大，下降約60%；而CABEB算法增大了上游節點的競爭窗口的最小值，促進作用有限，因此吞吐量仍然有所下降，但是較BEB算法還是增加了約100%；RBAB算法對擁塞的適應性較好，吞吐量在負載增大時基本保持最大值不變，較BEB算法增加150%。

圖13顯示了在每條業務速率為400Kbps時節點9的入口速率和出口速率。對于BEB算法來說，節點的入口速率遠大于出口速率，導致很快出現擁塞，而且一直處于擁塞狀態；而CABEB算法相對于BEB算法提高了節點的出口速率，也降低了節點的入口速率，但是入口速率仍然大于出口速率，因此雖然提高了網絡的端到端吞吐量，但是節點9仍然會擁塞；RBAB算法的入口速率和出口速率處于不斷的調整中，在總體上能夠保持相當，因此能夠把接收到的分組及時轉發出去。對于出口速率來說，在總體上RBAB最大，CABEB也比BEB算法大，這與端到端的吞吐量相對應。

6 小結

本文針對多跳Ad hoc網絡中的擁塞問題進行了分析，提出了兩種擁塞自適應退避算法RBAB和CABEB。RBAB算法中競爭窗口的增加主要是靠碰撞來實現的，在碰撞比較頻繁的網絡環境下RBAB算法能夠使得發送節點的競爭窗口保持比較大的值，能夠在網絡中起到較好的擁塞控制效果。而CABEB算法通過增加 。增大競爭窗口的值，在節點數量較多時對吞吐量的提高不如RBAB算法，但是其公平性和抖動能要優于RBAB算法。

RBAB算法與CABEB算法還需要進一步的研究，包括如何優化RBAB算法的參數使其能夠提高公平性和改善系統延遲抖動、如何進一步改進CABEB算法使得其在節點較多時能進一步提高系統吞吐量、如何使兩種算法支持業務分類等。在MAC層實現擁塞控制機制還需要考慮對上層的影響，因此進一步的研究還包括綜合考慮算法對路由協議和TCP層的影響。

參考文獻：

[1] Giuseppe B.Performance analysis of the IEEE802.11 distributed coordination function.IEEE Joumal on Selected Areas in Communications，18(3)，March 2000.

[2] Takai M，Bajaj L，Ahuja R，Bagrodia R，Gerla M.GloMosim: A Scalable Network Simulation Environment.Technical Report 990027，UCLA，Computer Science Department，1999.

[3] UCLA Parallel Computing Laboratory and Wireless Adaptive Mobility Laboratory .GloMosim: A Scalable Simulation Environment for Wireless and Wired Network Systems[EB/OL].http://pcl.cs.ucla.edu/projects/domains/glomosim.html．

[4] 王慶輝，潘學松，王光興.基于帶寬估計的ad hoc網絡擁塞控制機制[J].通信學報，2006，27(4):48-54.

[5] HOLLAND G，VAIDYA N H，BAHL P.A Rate-Adaptive MAC Protocol for Multi-Hop Wireless Networks.Proc MOBICOM01，Rome: IEEE Press，2001:236-251.

[6] Sally F，Van J，Random Early Detection Gateways for Congestion Avoidance.IEEE/ACM Transactions on Networking[C]，Volu.1.Issue 4，Aug.1993 Page(s):397-413.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”