基于信道占用率的Ad Hoc網絡自適應公平性算法

賴 曉 晨，　劉 全 利，　任 志 磊，　趙 　 瑩

( 1.大連理工大學 電子信息與電氣工程學部，遼寧 大連 116024；

2.大連理工大學 軟件學院 遼寧省泛在網絡與服務軟件重點實驗室，遼寧 大連 116620 )

?

基于信道占用率的Ad Hoc網絡自適應公平性算法

賴 曉 晨1，2，劉 全 利*1，任 志 磊2，趙 瑩2

( 1.大連理工大學 電子信息與電氣工程學部，遼寧 大連 116024；

2.大連理工大學 軟件學院 遼寧省泛在網絡與服務軟件重點實驗室，遼寧 大連 116620 )

摘要：Ad Hoc網絡中，節點通過競爭信道完成通信，如果競爭窗口值選取策略不合理，則容易造成公平性問題．在分析現存典型公平性算法的實現機制基礎上，提出了信道占用率的概念，設計了一種基于信道占用率的Ad Hoc網絡自適應公平性算法．根據節點對通信歷史及當前信道占用率與理想信道占用率之間的關系，將通信情況分為4種類別，再結合當前網絡負載情況，動態設置競爭窗口值．仿真結果表明，該算法在改善吞吐量的同時，顯著提高了節點信道接入公平性，在各種負載條件下表現良好，優于BEB、MILD、MIMD和NAVB等算法．

關鍵詞：Ad Hoc網絡；公平性；競爭窗口；吞吐量

0引言

AdHoc網絡中，隨著接入節點增多，節點對信道的競爭趨向激烈，導致不同節點獲得的通信機會并不相等，即產生所謂公平性問題．公平性反映了不同的用戶、節點或應用共享信道的公平程度，實現公平性是無線網絡資源分配的主要目標之一．讓每個節點都平等地接入信道，獲得平等的帶寬是一個非常重要的任務．當公平性得不到保證時，成功發送數據的節點總是可以得到更多的信道占用機會，而失敗的節點一直處于忙等狀態，出現“餓死”狀況，導致現實中有些數據流會因為其他流的惡意破壞而失去發送機會，這在軍事通信和緊急醫療通信中是不允許出現的，所以實現公平性顯得格外重要．

AdHoc網絡中，節點接入信道的機制由MAC(mediaaccesscontrol)協議實現，信道獲取能力主要取決于各節點的退避時間，因此退避算法起著關鍵性的作用．如何合理設計退避算法，在不顯著降低網絡吞吐量的同時提高節點通信的公平性，是一直以來研究的熱點問題．

IEEE802.11無線網絡協議MAC中采用DCF(distributedcoordinationfunction)機制實現信道無線接入，基于DCF的公平性改進策略主要調整協議中的二進制指數退避(BEB，binaryexponentialbackoff)算法，這是目前網絡公平性研究的主要方法．本文提出信道占用率(channeloccupancyrate)的概念，在單沖突域中，根據發包間隔內節點對占用信道的時間比例與理想信道占用率間的關系，在不同網絡負載情況下自適應調整窗口退避值，減少碰撞概率，在保證網絡吞吐量的同時，提高節點接入信道的公平性．

1研究現狀

1.1退避算法

應用在IEEE 802.11 MAC協議中的二進制指數退避算法能有效解決節點競爭信道的沖突問題[1]．其核心思想是節點的退避時間反映了網絡中不同節點接入信道的先后順序，退避時間較短的節點比退避時間較長的節點獲得更大的信道接入機會．初始時節點選取競爭窗口(collision window) 的最小值Wmin，如果數據傳輸失敗，則將W增加一倍，直至達到競爭窗口的最大值Wmax；如果數據發送成功，則重新將W置為最小值Wmin，W取值如式(1)所示[2]：

(1)

Wmax與Wmin的定義是為了約束W變化的范圍．W確定之后，節點在0和W之間隨機選擇一個整數，即退避窗口，用此整數乘以物理層時隙長度s，可以得到退避時間t，如式(2)所示[3]：

t=Random(0，W)×s

(2)

由上可知，BEB算法簡單、高效，但是缺點也十分明顯：總是傾向于將信道使用權交給最近成功傳輸信息的節點，造成信道競爭不公平的現象．

為了解決上述不公平問題，Bharghavan等在MACAW(multipleaccesswithcollisionavoidanceforwireless)協議中提出了倍數增加線性減少(MILD，multiplicativeincreaselineardecrease)算法[4]，按照式(3)選取競爭窗口值[2]：

(3)

式中：a與b是兩個可變參數，在MACAW協議中分別取值為1.5和1．可以看出，當傳輸成功時，MILD算法并未將W立即減到最小，因此克服了BEB算法的缺點．但是，在活躍節點個數由多到少迅速減少的特定場景中，MILD算法線性遞減的特點導致其無法快速調整W，造成無謂等待，降低了吞吐量．針對這種情況，文獻[5]提出了積式增加和減少(MIMD，multiplicative increase and multiplicative decrease)算法，按照式(4)選取競爭窗口值[2]：

(4)

式中：a的取值為2．可見，由于競爭窗口呈倍數變化，多次沖突后W快速增大，多次成功傳輸后W快速減小，W的調整幅度較大，相對于BEB算法來說，克服了成功節點長期占用信道的缺陷；相對于MILD算法來說，克服了節點較長時間的無謂等待．但是，MIMD算法中W的變化方法均采用同一個公式，未考慮不同的網絡負載情況，造成該算法不能同時適應各種網絡負載．文獻[6]提出一種自適應退避(AEFT，adaptive efficiency-fairness tradeoff)算法，網絡中每個節點維持一個連續成功傳輸次數計數器和一個連續沖突次數計數器，通過比較計數器當前值與閾值來調整W，閾值由負載決定，因而可以體現網絡狀態．但是，閾值為固定值，當網絡負載不斷變化時公平性表現不佳．文獻[7]提出的算法也具有自適應特點，通過對RTS(request to send)和CTS(clear to send)的計數，來估計節點周圍數據沖突情況，并相應修改退避值．該算法有助于降低沖突，提高吞吐量，但是公平性會受到影響．除上述方法外，還有研究者提出其他的退避算法，如帶有動態分級緩沖的自適應二進制指數退避算法、擴展非重疊二進制指數退避算法以及增強型二進制指數退避算法等[8-10]，然而，這些算法均未考慮到信道接入的公平性問題．

文獻[2]提出一種新的自適應網絡負載變化的退避算法NAVB．利用競爭窗口W的值作為一個隱式計數器來反映網絡負載程度，將W的取值范圍劃分為3個連續區間：[Wmin，h1)、[h1，h2)和[h2，Wmax]，h1和h2為區間分段閾值，且h1

(5)

其中a、b和c為常數，并且a

(6)

其中a、b和c為常數，并且a

NAVB算法中，W不會迅速變大或變小，而是根據網絡負載的情況做出適當調整．該算法并不偏向任何節點，每個節點在選擇退避時間時都是相對獨立的．根據當前負載情況，所有節點退避時間都是在同一個范圍內隨機取得的，對于每個節點來說是相對公平的．但是，NAVB算法也有一些不足之處．首先，對于吞吐量較低的節點，該算法沒有區別對待，沒有為此類節點提供更多通信機會，以提高公平性；其次，競爭窗口調整時，未考慮本節點吞吐量與網絡平均吞吐量之間的關系，不利于進一步提高公平性；再次，NAVB算法的競爭窗口范圍均為從0到W，實際的隨機退避時間有可能很小，在網絡負載較重的場景下容易導致較大沖突．

1.2公平性評價指數

為了衡量一種算法對節點信道接入公平性的影響，文獻[11]提出了公平性指數(fairness index) 概念，如式(7)所示：

F=Pmax/Pmin

(7)

其中F表示公平性指數，Pmax表示節點對最大的吞吐量，Pmin表示節點對最小的吞吐量．F為1時信道資源分配完全公平，F值越大，節點競爭信道能力越懸殊，公平性越差．

也有學者提出用改進的公平性指數(improved fairness index)衡量算法公平性[12]，如式(8)所示：

F′=(Pmax-Pmin)/Ptotal

(8)

其中F′表示改進的公平性指數，Ptotal表示網絡中所有節點對吞吐量的總和．F′為0時網絡公平性最好，此時每個節點對具有相同的吞吐量，信道資源分配完全公平．然而式(7)與(8)具有明顯的缺陷，單從網絡節點對最大吞吐量和節點對最小吞吐量來衡量信道競爭公平性不能完整反映網絡整體的公平性情況，因而得到的結果也不夠準確．

基于標準偏差概念，文獻[13]提出了全路徑公平性指數(fairness index of all links)的概念，能反映全網所有節點對競爭的公平性，如式(9)所示：

(9)

NAVB算法采用式(7)作為公平性評價指數，不能反映每一個節點對的實際情況，具有較明顯缺陷．本文在NAVB算法基礎上提出基于信道占用率的自適應公平算法(CORAFA算法)，以有效克服NAVB算法的不利因素，既保證較高的網絡吞吐量，又在一定程度上提高網絡公平性．

2基于信道占用率的自適應公平性算法(CORAFA算法)

CORAFA算法借鑒了NAVB算法隨網絡負載變化調整競爭窗口值的方法，但采用更合理的方式選取競爭窗口值，以改善吞吐量和公平性指標．

2.1CORAFA算法介紹

假設網絡中節點對數目為n，對于某節點對，定義從其中發送節點收到ACK確認包開始，到該節點下次收到ACK確認包為止，其間經歷的時間為發包間隔T．定義發包間隔過程中，發送節點發送RTS包和DATA包，接收節點發送CTS包和ACK包所用時間之和為有效時間V．定義有效時間與發包間隔的比值為該發送節點在該發包間隔內的信道占用率，記作S，則有

S=V/T

(10)

在絕對公平的情況下，每一個節點對的信道占用率應為1/n，定義其為理想信道占用率．當S=1/n時，說明該節點對獲得了公平的信道接入機會．如果S>1/n，則說明該節點對獲得的信道占用率偏大，需適當增加競爭窗口值，以降低其成功接入信道的概率．如果S<1/n，則說明該節點對獲得的信道占用率偏小，此時，記錄發送節點的當前競爭窗口值為W*，然后將競爭窗口值置為0，以使發送節點可以立即發送RTS包，增加節點對的有效時間V，從而增大該節點對的信道占用率S．循環執行此過程，直至S≥1/n，恢復競爭窗口值為W*．CORAFA算法的目標是通過對W的調整，改變節點對接入信道的能力，最終實現所有節點對的信道占用率趨向1/n發展的相對公平狀態．

式(10)說明了當前發包間隔內節點對的信道占用率情況，但是不應僅僅以此為依據來調整競爭窗口值，因為此前發包間隔內節點對的信道占用率情況也對公平性有影響．因此，應將式(10)改為遞推公式，得到式(11)：

(11)

式中：Sk為本次計算得到的信道占用率；Sk-1為前一個發包間隔內的信道占用率；α為比例因子，其值由實驗確定．

CORAFA算法考慮了節點對的信道占用率與理想信道占用率1/n間的關系，據此對NAVB算法中W的計算方法做出調整，使各節點對的實際吞吐量趨近于平均吞吐量．

當節點發包失敗時，如果當前信道占用率S<1/n，此時根據式(12)計算競爭窗口值．通過W判斷當前網絡負載等級，當W在[Wmin，h1)時，以較小幅度線性增大W；當W在[h1，h2)時，以較大幅度線性增大W；當W在[h2，Wmax]時，以較小倍數增加W．相對于NAVB算法的同一區間而言，W的增量相對較小，因此增大了信道占用率小的節點對接入信道的機會．如果當前信道占用率S≥1/n，此時為了不顯著降低網絡總吞吐量，競爭窗口值的計算方法不變，仍采用式(5)．

(12)

其中a、c和d為常數，并且c

當節點發包成功時，如果當前信道占用率S<1/n，說明該節點吞吐量較低，此時如前所述立即將W置為0，使節點對能夠以最大概率接入信道，提高信道占用率．如果當前信道占用率S≥1/n，此時根據式(13)計算競爭窗口值．通過W判斷當前網絡負載等級，當W在[Wmin，h1)內時，以較小幅度減小W；當W在[h1，h2)內時，以較大幅度線性減小W；當W在[h2，Wmax]內時，以較小幅度線性減小W．相對于NAVB算法的同一區間而言，W的減小量相對較小，使該節點對成功接入信道的機會減小，其他節點接入信道的機會增大．

(13)

其中a、c和d為常數，并且c

與競爭窗口值分段計算的做法類似，CORAFA算法的退避時間也分段計算，以適應各種網絡負載情況，如式(14)所示．當W在[Wmin，h1)時，網絡負載較小，此時退避隨機數在(0，W)選取，保證節點有較大吞吐量；當W在[h1，h2)時，網絡負載中等，如在(0，W)內選取退避隨機數，該數值有可能接近0，此時較易引起沖突，因此在(h1，W)內選取退避隨機數；當W在[h2，Wmax]內時，網絡負載較重，基于同樣理由，在(h2，W)內選取退避隨機數．

(14)

CORAFA算法中，公平性評價指數采用式(9)，相對于NAVB算法而言，更全面地考慮到每一個節點對的具體情況．

2.2CORAFA算法的參數選擇

CORAFA算法中，按照式(11)求某節點對的信道占用率時，需要確定α的值．圖1為16個節點組成的簡單矩形拓撲場景，隨機選擇通信節點對為(3，4)、(1，10)、(9，0)、(7，13)、(6，15)、(2，11)、(5，8)和(12，14)，括號中前者為發送節點，后者為接收節點．分別將α在0和1之間等間隔取值，按照式(9)定義的公平性評價指數，通過實驗比較求得最佳α值為0.8，如圖2所示．

圖1簡單矩形拓撲場景

Fig.1Simple rectangular topology scene

圖2　α值對比圖

3算法實例分析

假設在單沖突域內有8個通信節點對，分別為節點對A、B、C、D、E、F、G和H．每個節點對均持續發送數據包，包大小為1 024 B，發包速率為1 Mb/s，s設置為20 μs，節點對隨機選擇發包前的退避窗口τ，取值如式(15)所示：

τ=Random(0，W)

(15)

在實際工作時，τ按照如下方式選取．不失一般性，將當前時間設為隨機數種子，生成8個隨機數，將這8個隨機數再次作為種子，在[0，1]內分別生成8個隨機數序列，每個隨機數序列對應一個節點對．用各序列中的每個隨機數，乘以競爭窗口值W，可以得到該節點對當前的退避窗口τ．分析中，NAVB算法和CORAFA算法采用相同的隨機數序列．

表1為8個節點對的部分退避窗口值，由于兩種算法的對應節點對采用相同隨機數序列，并且兩種算法有相似之處，因此退避窗口的前24列取值相同．初始時刻，用8個隨機數序列的第1個數字乘以Wmin，得到各節點的初始退避窗口值．此后，每經過一個退避時隙s，各節點對的退避窗口值均減1，直至減為0，表示該節點對退避結束，可以發送RTS包．之后，該節點對從自己的隨機數序列中選取下一個數，乘以當前競爭窗口值W，得到該節點對的下一個退避窗口值，如表中斜線后的數字所示．如果有兩個節點對的退避窗口值同時減為0，此時發生沖突，兩個節點對都不能發起通信，而是按照如上方法重新選取下一個退避窗口值，繼續退避．

表1　退避窗口值

初始時刻，τA~τH的初始退避窗口值分別為6、3、13、16、26、30、21和21，如表1中的第1列所示．節點對根據式(2)計算實際退避時間．節點對B首先退避到0，并且與其他節點對無沖突，因此在第1次信道競爭中，節點對B成功接入信道，如表1第2列所示．

對于NAVB算法來說，節點對B本次傳輸成功，因此根據式(6)計算新的競爭窗口值．由于W在[Wmin，h1)內，所以新的W仍為Wmin．節點對B的下一個退避窗口值由式(15)計算得到，其值為30，如表1第2列所示．

對于CORAFA算法，由于節點對B本次傳輸成功，根據式(11)計算信道占用率S為1．因為S>1/n，采用式(13)計算新的競爭窗口值．由于W在[Wmin，h1)內，所以新的W值仍為Wmin．節點對B的下一個退避窗口值由式(15)計算得到，其值為30，如表1中的第2列所示，與NAVB算法計算的結果相同．

圖3為NAVB和CORAFA兩種算法前80個時隙的時序圖，坐標表示時間，坐標的刻度單位為一個退避時隙s，每一個矩形代表一次成功傳輸，其中的字母代表成功傳輸的節點對名稱．傳輸過程中所有節點停止退避計數，因此在不考慮節點對成功傳輸的條件下，坐標軸刻度連續．圖3中，用向下箭頭單獨標注節點對的沖突時刻．在坐標為0時，所有節點開始退避計數，節點對B經過3次退避后，成功傳輸數據．根據表1可知，后續成功傳輸的節點對依次為A、C和D，在第21個時隙處，節點對G和H同時退避到0，發生沖突，如表1第6列所示．

圖3　算法時序圖

對于NAVB算法，由于節點對G和H發生沖突，因此均需要根據式(5)計算新的競爭窗口值．由于W在[Wmin，h1)內，所以新的W線性增加為36．節點對G的下一個退避窗口值由式(15)計算得到，其值為19；節點對H的下一個退避窗口值也由式(15)計算得到，其值恰好也為19．

對于CORAFA算法，發送沖突時，先根據式(11)計算節點對G和H的信道占用率S均為1，因為S>1/n，選擇式(12)計算新的競爭窗口值．由于W在[Wmin，h1)內，新的W應在原基礎上加5，其值為36．節點對G的下一個退避窗口值由式(15)計算得到，其值為19；節點對H的下一個退避窗口值也為19，與NAVB算法計算的結果相同．

由于前幾次競爭中，節點對的信道占用率均大于1/n，且W在[Wmin，h1)內，因此在NAVB與CORAFA算法中，節點接入信道順序一致，直到表1中的第24列為止．

圖4表示的是NAVB算法中節點對C的接入時序圖．節點對C在第13個時隙成功傳輸，在第40個時隙發生沖突，之后在第80個時隙成功傳輸．根據表1的第24列可知，節點對A剩余的退避窗口值最小，其值為3，因此第83個時隙時，節點對A接入信道．

圖4　NAVB算法中節點對C接入時序圖

圖5是CORAFA算法中節點對C的接入時序圖．在節點對C的第1個發包間隔T1內，共有7個節點對成功發包，因此在第40個時隙時，根據式(11)，可求得節點對C的信道占用率S2=1/8．在節點對C的第2個發包間隔T2內，共有8個節點對成功發包，根據式(11)，可求得節點對C的信道占用率S3=(1/8)×0.2+(1/9)×0.8=0.114．由于S3<1/n，說明節點對C在這個過程中接入信道的機會偏低．為了提高C的信道占用率，立即將節點對C的競爭窗口W置為0，讓節點對C連續傳輸數據，直至信道占用率大于1/n，以此提高公平性．

圖5　CORAFA算法中節點對C接入時序圖

(16)

圖6體現了信道占用率標準差隨時間變化情況，由圖可知，CORAFA算法中，各節點對的信道占用率較為接近，明顯優于NAVB算法，說明CORAFA算法的公平性明顯好于NAVB算法．

圖6　信道占用率標準差σ隨時間變化

將仿真時間延長到1 000 s，CORAFA算法的信道占用率標準差σ可收斂到0.08~0.22，可知該算法比較穩定．

4協議仿真

利用NS2仿真平臺，將CORAFA算法與BEB算法、MILD算法、MIMD算法及NAVB算法的吞吐量和公平性進行比較，其中公平性評價指數采用式(9)計算．實驗共分為3組，分別比較各算法在節點對數為4、8和12時的表現．

4.1仿真場景

仿真場景中，節點間仍采用簡單矩形拓撲結構，節點位置隨機安排；CORAFA、BEB、MILD、MIMD和NAVB等幾種算法采用相同實驗參數，如表2所示．

表2　仿真參數

4.2仿真結果及分析

第1組實驗選取4對節點，比較幾種算法吞吐量和公平性隨時間變化的情況，分別如圖7和8所示．圖7中，由于BEB算法僅僅為了提高網絡吞吐量性能，不考慮公平性，因此BEB算法的吞吐量較高．MIMD、NAVB和CORAFA算法也能保證較高吞吐量，這是因為當前網絡負載較低，沖突較少．MILD吞吐量指標明顯偏低，這是由于其倍數增加線性減少W，導致其W值長期偏大，在低負載情況下無謂等待時間很長，因此吞吐量較低．

圖7　4對節點時吞吐量隨時間變化情況

圖8中，由于MILD算法倍數增加線性減少W，導致節點長期無法接入信道，嚴重影響公平性．BEB算法每次成功傳輸后，W均取為Wmin，這在低負載情況下對其他節點通信影響不大，因此BEB算法表現優于MILD算法．NAVB算法能夠根據負載情況動態調整W，公平性優于BEB算法．MIMD算法采用倍數增加倍數減少W，對W調整較為迅速，與CORAFA算法一樣，表現最好．

圖8　4對節點時公平性隨時間變化情況

第2組實驗選取8對節點，比較幾種算法吞吐量和公平性隨時間變化情況，分別如圖9和10所示．圖9中，由于網絡負載增加，沖突增大，幾種算法的吞吐量普遍稍有下降．基于同樣原因，BEB算法在吞吐量方面表現仍舊較好，CORAFA算法表現與其相當，在考慮公平性的同時，吞吐量損失不大．MIMD和NAVB算法的吞吐量受負載影響較大，表現有所降低．但是，MILD算法線性減少W的方法能夠降低沖突，因此相對低負載情況而言，吞吐量緩慢上升．

圖9　8對節點時吞吐量隨時間變化情況

圖10為幾種算法的公平性表現．與4對節點的低負載環境相比，MIMD算法不能根據當前負載情況隨時調整W，因此表現較差．MILD算法隨著沖突增加，節點接入信道的平均時間變長，表現更差．其他幾種算法與低負載情況相差不大，但是CORAFA算法的公平性指數值最低，即表現最好．

第3組實驗選取12對節點，比較幾種算法吞吐量和公平性隨時間變化的情況，分別如圖11和12所示．圖11中，由于CORAFA算法考慮了節點吞吐量和平均吞吐量之間的關系，能夠動態調整競爭窗口值，因此在高網絡負載條件下表現仍然最好．BEB算法僅考慮吞吐量，不考慮公平性，因此吞吐量仍舊較大．MIMD算法在成功傳輸之后倍數減少W，造成較大沖突，降低了吞吐量．MILD算法線性減少W，當負載高時，受沖突影響較小．NAVB算法注重公平性，吞吐量對不同負載的適應性較差，因此吞吐量有明顯下降．

圖12為幾種算法在高負載時的公平性表現．BEB算法不考慮公平性，表現最差．MILD算法的競爭窗口取值變化幅度很小，各節點間相差不大，因此公平性最好，但是這是以犧牲吞吐量為代價的．MIMD、NAVB和CORAFA算法的表現介于前述二者之間，但是CORAFA算法吞吐量指標優于其他兩種算法，綜合表現最好．

圖10　8對節點時公平性隨時間變化情況

圖11　12對節點時吞吐量隨時間變化情況

圖12　12對節點時公平性隨時間變化情況

綜上所述，在吞吐量方面，CORAFA算法與BEB算法相似，遠優于其他3種公平性算法；在公平性方面，CORAFA算法遠優于BEB算法，并且在低負載場景下表現最佳，在高負載下與NAVB和MIMD算法表現類似．綜合考慮吞吐量和公平性，CORAFA算法較其他幾種算法表現更好．

5結語

本文提出了CORAFA算法，節點根據當前網絡負載與信道占用率情況，動態調整競爭窗口值，并合理確定隨機退避時間選擇范圍，減少了通信沖突．仿真結果表明，相對于BEB、MIMD、MILD和NAVB等算法，本算法在保證吞吐量的同時提高了網絡公平性，具有一定優勢．今后可研究根據網絡負載動態調整區間分段閾值h1和h2的方法，以更靈活地適應負載變化情況，進一步減少沖突，改善吞吐量和公平性．

參考文獻：

[1]LAN/MAN Standards Committee of IEEE Computer Society. IEEE Std 802.11-2007 Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications [S]. Piscataway:IEEE, 2007.

[2]Gafur M A, Upadhayaya N, Sattar S A. Enhancing the performance of Ad Hoc networks using new adaptively varying backoff technique [J]. International Journal of Engineering Science and Technology, 2010, 2(12):7078-7086.

[3]吳傳霞,范平志,馮軍煥. 一種Ad Hoc網絡信道接入排隊退避公平算法[J]. 系統仿真學報, 2004, 16(5):1111-1114.

WU Chuan-xia, FAN Ping-zhi, FENG Jun-huan. On a queue backoff fair algorithm for channel access in Ad Hoc network [J]. Journal of System Simulation, 2004, 16(5):1111-1114. (in Chinese)

[4]Bharghavan V, Demers A, Shenker S,etal. MACAW:A media access protocol for wireless LANs [J]. Computer Communications Review, 1994, 24(4):212.

[5]WU Hai-tao, CHENG Shi-duan, PENG Yong,etal. IEEE 802.11 distributed coordination function(DCF):analysis and enhancement [C] // 2002 IEEE International Conference on Communications. Piscataway:IEEE, 2002:605-609.

[6]CUI Hai-xia, WEI Gang. A novel backoff algorithm based on the tradeoff of efficiency and fairness for Ad Hoc networks [C] // Proceedings-2009 WRI International Conference on Communications and Mobile Computing, CMC 2009. Piscataway:IEEE Computer Society, 2009:81-86.

[7]趙志峰,鄭少仁. Ad Hoc網絡信道接入技術研究[J]. 解放軍理工大學學報(自然科學版), 2001, 2(3):47-51.

ZHAO Zhi-feng, ZHENG Shao-ren. Research about Ad Hoc network channel access technology [J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2001, 2(3):47-51. (in Chinese)

[8]Chekka R T, Miao T, Kim K H. Implementation of adaptive binary exponential backoff (ABEB) algorithm with dynamical sizing buffer for load-balanced RPL [C] // 2014 Sixth International Conference on Ubiquitous and Future Networks (ICUFN). Piscataway:IEEE, 2014:562-564.

[9]Lee S Y, Shin Y S, Lee K W,etal. Performance analysis of extended non-overlapping binary exponential backoff algorithm over IEEE 802.15.4 [J]. Telecommunication Systems, 2014, 55(1):39-46.

[10]Chin H H, Lin C C, Deng D J. E-BEB:Enhanced binary exponential backoff algorithm for multi-hop wireless ad-hoc networks [J]. Wireless Personal Communications, 2014, 76(2):193-207.

[11]Ozugur T, Naghshineh M, Kermani P,etal. Fair media access for wireless LANs [C] // Conference Record/IEEE Global Telecommunications Conference. Piscataway:IEEE, 1999:570 -579.

[12]李瑞芳,李仁發. Ad Hoc網絡信道接入退避算法研究[J]. 科學技術與工程, 2006, 6(15):2358-2363.

LI Rui-fang, LI Ren-fa. The backoff algorithm for channel access in Ad Hoc networks [J]. Science Technology and Engineering, 2006, 6(15):2358-2363. (in Chinese)

[13]李 廣. Ad Hoc網絡多信道MAC協議研究與實現[D]. 武漢:武漢理工大學, 2009.

LI Guang. Research and realization of the multi-channel MAC protocol in Ad Hoc network [D]. Wuhan:Wuhan University of Technology, 2009. (in Chinese)

Channel occupancy rate-based adaptive fairness algorithm for Ad Hoc network

LAIXiao-chen1,2,LIUQuan-li*1,RENZhi-lei2,ZHAOYing2

( 1.Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China；2.Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, School of Software Technology,Dalian University of Technology, Dalian 116620, China )

Abstract：In Ad Hoc network, nodes compete channels to communicate. It is likely to cause fairness problems if the selection strategy of collision window value is unreasonable. With the analyses of the implementation mechanisms of existing typical fairness algorithms, a concept of channel occupancy rate is raised. Based on this concept, an adaptive fairness algorithm for Ad Hoc network is proposed. The network correspondence is classified into four types according to the history of correspondence and the relationship between the current channel occupancy rate and the ideal channel occupancy rate. In each type, the collision window value of node is set dynamically based on the current network load. Simulation results show that the proposed algorithm performs well under various load conditions. It can significantly improve fairness of channel access among nodes as well as throughput, so it is better than BEB, MILD, MIMD and NAVB algorithms.

Key words：Ad Hoc network; fairness; collision window; throughput

作者簡介:賴曉晨(1977-)，男，副教授，E-mail:laixiaochen@dlut.edu.cn；劉全利*(1976-)，男，教授，博士生導師，E-mail:liuql@dlut.edu.cn.

基金項目:“九七三”國家重點基礎研究發展計劃資助項目(2013CB035906)；國家自然科學基金資助項目(61273037，61403057).

收稿日期：2015-04-10；修回日期: 2015-09-28．

中圖分類號：TP393.1

文獻標識碼：A

doi:10.7511/dllgxb201601007

文章編號：1000-8608(2016)01-0041-09