基于赤字輪詢算法的無線Ｍｅｓｈ網絡公平性研究

(1．同濟大學 電子與信息工程學院， 上海 200092； 2．上海無線通信研究中心， 上海 200050)



摘要：

無線Mesh網絡在負載較重時會出現嚴重的空間不公平現象，即遠離網絡中心的節點很難將其數據傳送到網關。赤字輪詢算法能夠保證節點數據傳輸的公平性要求，但卻存在吞吐量平均化的問題。在分析無線Mesh網絡公平性問題的基礎上，提出基于最小均方的動態赤字輪詢算法，其核心思想是動態調整輪詢權重值。仿真在IEEE 802.11 DCF機制下將所提出的算法與傳統的赤字輪詢及棄尾算法進行比較，結果表明，所提出的方法能夠保證吞吐量需求不同的業務流之間的公平性，并使網絡總吞吐量獲得提高。

關鍵詞：無線Mesh網絡； 公平性； 赤字輪詢； 最小均方算法

中圖分類號：TN92文獻標志碼：A

文章編號：10013695(2009)03102204



Fairness research of wireless Mesh networks based on deficit round robin



WEN Shiqi1，2， RONG Lu2， ZHAO Xiaoqun1， XU Shangzhi1



(1. College of Electronic Information Engineering， Tongji University， Shanghai 200092， China； 2. Shanghai Research Center for Wireless Communications， Shanghai 200050， China)



Abstract:

Serious spatial unfairness occurs when the traffic load of a wireless Mesh network was heavy， what starves the nodes away from the gateway. The deficit roundrobin algorithm could achieve network fairness， but suffered from a problem of average throughput. Based on the analysis of spatial unfairness， this paper proposed a new dynamic deficit roundrobin algorithm using least mean square， which dynamically adjusted the weight of roundrobin. Through simulations compared droptail and deficit roundrobin algorithm under IEEE 802.11 DCF mechanism. And demonstrate that dynamic deficit roundrobin algorithm can give fairer throughput to different flows and slightly improve the overall throughput of wireless Mesh networks.

Key words：wireless Mesh networks(WMN)； fairness； deficit roundrobin； least mean square



0引言

隨著無線寬帶因特網業務需求的增長，無線Mesh網絡（wireless Mesh networks，WMN）已經成為工業界與學術界的研究熱點。WMN是因特網的無線版本，網絡中節點的數據傳輸通過路由器（Mesh router）和網關最終到達因特網，并以靈活的網絡結構實現高速的全網覆蓋。目前IEEE 802.11、IEEE 802.15、IEEE 802.16及IEEE 802.20等多種國際標準均在對WMN進行推進。文獻[1]介紹了IEEE 802.11 WMN的基本原理及其存在的一些問題。在WMN中各節點除了發送自身業務外，還可能中繼轉發其他節點的數據，當網絡資源達到飽和時，靠近網關的節點更容易獲得較多的網絡資源傳送自身業務，而對所要中繼的數據進行排隊甚至丟棄處理，這便是WMN中不公平現象的一種體現。網絡的公平性問題在計算機和無線通信網絡中均有涉及，且是網絡的重要特性之一。通常可以采用一定策略使網絡資源公平地分配到各個用戶，從而在網絡負載較重時依然保證整個網絡總體性能的穩定性。

目前，國內外研究學者已開始關注WMN中的公平性問題。文獻[2]提出沖突域（collision domain）的概念，給出IEEE 802.11 WMN所能獲得的最大容量。文獻[3]分析了WMN中的最大最小公平性問題，提出媒體訪問控制（medium access control，MAC）及上層聯合解決方案。文獻[4]通過使用IEEE 802.11e區分業務類型的方法獲得公平性，但是仍然依賴于MAC協議。文獻[5]針對IEEE 802.11 WMN中同一基本服務集內的公平性問題，提出基于擁塞控制的解決方法，并且與所用的MAC協議無關。文獻[6]分析了IEEE 802.11WMN中不同基本服務集之間的公平性問題，提出基于動態網絡分配矢量和強制切換的聯合解決方案。這些方法均能從不同層面上提高WMN的公平性，但仍不是一種通用的解決方案，理想的方案應該能適用于各種網絡拓撲及協議模型。文獻[7]提出新的隊列模型，通過對隊列轉發概率和節點接入概率的調整來改善公平性，但是該隊列模型與實際中的隊列有較大區別。

經分析研究，隊列機制對于WMN的公平性具有很大的影響。隊列是網絡中各節點用來緩存數據包的地方，在節點通過競爭獲得發送權之前，待發數據包均暫存于隊列中。隊列操作包括隊列管理和隊列調度兩方面。隊列管理是指網絡在發生擁塞時，通過丟棄數據包來控制隊列長度；隊列調度是指選擇隊列的待發數據包。傳統的也是目前應用最廣泛的隊列操作是棄尾（droptail）算法，它在隊列緩沖區已滿時丟棄隊列尾部到達的數據包，并且采用先到先服務（first in first out， FIFO）的隊列調度算法保證排隊意義上的公平性。很明顯，這種被動式的隊列管理方法會造成網絡中某條或某幾條業務流獨占隊列空間并且阻止其他業務流的數據包進入隊列的情況，因而無法滿足WMN公平性要求。文獻[8]提出的隨機早期檢測（random early detection，RED）算法是一種主動式隊列管理算法。文獻[9]將RED算法的思想引入WMN，采用丟棄高數據包到達率較高的流的方法來保證網絡的公平性。RED算法通過監測隊列長度感知網絡擁塞情況并主動丟棄數據包來避免擁塞，但是在隊列調度方法上仍然不適用于WMN。文獻[10]提出的赤字輪詢（deficit roundrobin，DRR）算法，從數據包入隊和出隊的方法上來保證網絡中多條流之間的公平性，是WMN中有效的隊列調度算法。文獻[11]針對變長數據包的情況對DRR算法作出改進，但是各隊列的權重值在每次輪詢時仍然相同，無法提供吞吐量公平性。

1DRR算法原理及其存在的問題

1.1DRR的原理及算法分析

DRR算法本質上是一種輪詢算法，主要從數據包入隊和出隊的方法上來保證網絡中多條業務流之間的公平性。這里的流是指一串具有相同源地址與目的地址并且具有相同路由的數據包，此外每一個數據包也可以在其IP首部預先指定的字段中將其惟一地分配給某一條流。

DRR算法為每一條不同的流分配一個虛擬隊列，在數據包入隊時根據IP首部中提供的信息將隸屬于不同流的數據包存放到相應的虛擬隊列中，這樣做的目的是在隊列內部區分不同的流來為公平的隊列調度做準備。值得注意的是，在數據已入隊時，如果隊列緩沖區已滿，DRR算法并不丟棄新到達的數據包，而是保證這個數據包進入相應的虛擬隊列，并且從已有的虛擬隊列中找出一個最長的隊列將其隊頭的數據包丟棄，從而保證網絡擁塞時新業務流數據包仍能進入隊列。在數據包出隊時，DRR算法兼顧了輪詢算法的優點，保證每條流都能得到調度，同時克服了輪詢算法不區分數據包大小的缺陷，以字節數來限制每次被輪詢時虛擬隊列能夠發送的數據包數量。

DDR算法的核心是引入了赤字的概念，即在較長時間統計平均意義上平衡各條流所獲得的吞吐量。因為各流之間不同業務造成的數據包大小的差異以及各流內部數據包大小的不同都可能造成在一個輪詢周期內各虛擬隊列所發送的字節數具有較大偏差。DRR算法為每個虛擬隊列維護一個赤字字節數，使得本次輪詢未能發送的字節會在下一次甚至下幾次輪詢過程中得到補償。具體過程如下：將有數據包等待發送的虛擬隊列存放于一個鏈表中，輪詢過程即訪問鏈表表頭上的隊列，訪問時先將隊列的當前赤字值（deficit counter）加上一個預先分配的值（quantum size，表示每次輪詢允許發送的字節數），將它作為本次輪詢所能發送的最大字節數Q，然后服務該隊列。服務隊列時先判斷隊頭上的數據包長度（Byte）是否小于Q，如果是，則服務后令Q減去Byte并繼續此循環過程直至Byte＞Q，將最后得到的Q值賦予deficit counter，并將該隊列從鏈表中取出插入鏈表尾部，接著訪問鏈表中的下一個隊列。若從虛擬隊列中取出數據包后隊列為空，則將該虛擬隊列從鏈表中刪除。

DRR算法的偽代碼流程如下：

初始化(假設已有n條數據流，下標i與第i條流相對應)

for(i=0;i

DeficitCounteri=0;

入隊(假設數據包p入隊)

x=HashFlow(p);

if(ExistInActiveList(x)==FALSE)

InsertActiceList(x);

DeficitCounterx=0;

if(no free buffer left)

FreeBuffer();

EnQueue(x，p);

出隊(假設當前隊列為i)

Qi= DeficitCounteri+QuantumSizei;

while(Qi >0 and Queuei is not empty)

Byte=Size(Head(Queuei));

if(Byte≤Qi)

DeQueue(Queuei);

Qi=Qi-Byte;

else break;

if(Queuei is empty)

IdleList(i);

else InsertActiceList(i);

1.2DRR存在的問題及其原因

DRR算法在網絡中各節點的隊列處通過具有相同權重的赤字輪詢機制來保證網絡的公平性，平衡各業務流的吞吐量，這對于各業務流平均數據包大小相似的情況是可行的。但在WMN中，由于提供的是寬帶無線因特網接入服務，網絡中涵蓋了現有因特網中的所有業務，各業務流之間將存在較大差別，這時采用傳統的DRR算法顯然是不合理的。

由1.1節DRR算法隊列調度的原理可知，算法提供相似吞吐量的主要原因在于輪詢時使用的權重值固定且相等。因為當輪詢權重相等時，在多個輪詢周期后各虛擬隊列所發送的總字節數就近似相等，而吞吐量定義為單位時間內業務流的目的節點所收到的字節數，各業務流所獲得的吞吐量也近似相等。由此可見，DRR算法的權重值對于各業務流的吞吐量具有決定性的作用，合理地分配權重值將有助于實現WMN中各業務流間的公平性。

2DDRR算法

2.1DDRR的基本原理

DDRR的主要設計目標是在保證各業務流數據包能夠得到公平調度的基礎上，進一步提高需求較大的業務流的吞吐量。DDRR的主要設計思想是為隊列中現有業務流提供各自的權重值，并且在每次輪詢時根據各業務流所對應的虛擬隊列中的平均數據包大小進行動態調整。使用不同的權重值是為了體現不同業務流之間的區別，而權重值的動態調整能夠及時快速地對單條業務流的變化作出反應，增強網絡的公平性與合理性。

DDRR通過平均數據包大小而不是實際入隊數據包大小來調整隊列權重值，這主要是考慮到因特網數據突發性的本質。如果隊列中的數據包在較長時間內維持在一個平均水平，而突發地收到偏離平均大小的數據包，這并不能體現業務流的真實特性。因此，使用平均數據包大小來過濾掉數據包大小短期的變化，使其體現業務流的長期特性。

對于隊列權重值的調整，采用類似于最小均方（least mean square，LMS）算法[12]的步驟來進行，這主要是考慮到LMS算法的簡單性和高效性。

2.2DDRR的算法分析

為了避免上文中的隊列權重與LMS算法中的權系數調整因子概念的混淆，首先將隊列權重值重新定義為隊列的令牌數，即隊列被輪詢時允許發送的字節數。在DDRR算法中，使用平均隊列長度作為期望令牌數，采用4抽頭權系數調整因子的結構對前4次輪詢時的令牌數進行加權，得到的結果作為本次輪詢的令牌數。調整過程如圖1所示。

設前4次輪詢時的令牌數構成的矩陣為x(n)，權系數矩陣為w(n)，平均隊列長度為d(n)，那么本次輪詢時的令牌數y(n)=xT(n)w(n)，誤差e(n)=d(n)-y(n)。根據LMS算法:

w(n+1)=w(n)+2μe(n)x(n)(1)

其中：參數μ為使權系數矩陣收斂的因子，它可以控制算法的收斂速度，其取值與網絡中實際產生的數據包大小有關。為使權系數矩陣收斂，參數μ必須滿足：

0＜μ＜2/λmax(2)

其中：λmax為x(n)自相關矩陣Γ的最大特征值。因為自相關矩陣是正定的共軛對稱矩陣，并且其最大特征值小于其所有特征值之和，所以:

λmax＜trΓ(3)

其中：trΓ為矩陣Γ的跡。為了使所有虛擬隊列令牌調整過程收斂，令x(n)所有元素均為數據包最大長度L，得到參數μ的范圍為

0＜μ＜1/2L2(4)

DDRR算法采用與DRR算法相同的入隊機制，保證在網絡產生擁塞時隊列不會被個別業務流獨占；在數據包入隊后令牌動態調整機制作用于節點隊列內相應的虛擬隊列上，使得每一個虛擬隊列的令牌數以較快的速度趨近于緩存中的數據包的平均大小，在每次輪詢時允許發送相應的字節數。因此，DDRR算法能夠彌補DRR算法應用于WMN時所產生的問題，有效地提高網絡的公平性。

2.3DDRR算法公平性分析

為了研究DDRR算法在時間統計意義上的公平性，令senti(t1，t2)表示隊列i在[t1，t2]時間內發送的字節數，Xi表示隊列 i的令牌數，X為Xi的最小值:

X=min(Xi)(5)

fi為Xi相對于X的比值:

fi=Xi/X(6)

隊列i與j之間與令牌數相應的發送字節數差異定義為

Diffi，f(t1，t2)=|(senti(t1，t2))/fi-(sentj(t1，t2))/fi|(7)

公平性由式(7)的最大值Diff來衡量。

令Pmax表示隊列中最大數據包的字節數，DCi(k)、Bytei(k)分別表示隊列 i在第k次輪詢時的赤字數與發送字節數，假設[t1，t2]時間內隊列i共被輪詢到m次，隊列j共被輪詢到n次，由此可得:

0≤DCi(k)＜Pmax(8)

Bytei(k)+DCi(k)=Xi+DCi(k-1)(9)

容易得到m， n滿足關系式:

|m-n|≤1(10)

由式(9)可得:

senti(t1，t2)=∑mk=1Bytei(k)=mXi+DCi(0)-DCi(k)(11)

式(11)與(8)聯立可得:

mXi-Pmax＜senti(t1，t2)＜mXi+Pmax/fi(12)

senti(t1，t2)/fi＜mX+Pmax/fi(13)

同理有:

nX-Pmax/fj＜sentj(t1，t2)/fj(14)

式(13)(14)與(10)聯立可得:

Diff=X+Pmax/fi+Pmax/fj(15)

式(15)給出了DDRR算法對于網絡公平性貢獻的一個下界。

3實驗結果

3.1仿真場景

WMN通過網關節點向網絡中的其他節點提供因特網接入服務，其主要業務流經鏈路是來往于用戶終端與網關之間的無線鏈路，這種特殊的業務流向容易造成在靠近網關節點的地區形成瓶頸，造成節點隊列緩沖區填滿而大量丟棄數據包。基于IEEE 802.11的WMN規劃如圖2所示。下面就用戶至接入點的鏈路進行討論，其結論可以推廣到接入點到網關的情形。

仿真采用圖3所示的網絡拓撲結構。其中節點0為網關（或接入點）節點，節點之間的箭頭表示兩個節點在彼此通信范圍之內。為了避免不同傳輸距離對鏈路質量產生的影響，假設節點間的距離相等且小于數據傳輸范圍，載波監聽范圍為數據傳輸范圍的兩倍以上。本文選取圖3中帶有編號的節點進行研究。可見，1890鏈路是網絡中的瓶頸之一。此外，節點1附近的節點由于IEEE 802.11的DCF機制在競爭信道時會較多地進行退避，接入信道的概率較低。

在各種業務中，面向連接的業務由于TCP本身擁塞控制功能的影響，會削弱隊列機制的影響；無連接業務中，固定比特率（CBR）業務無法反映網絡中業務流的時變特性。因此僅對可變比特率（VBR）業務進行分析。

仿真采用NS2工具，以業務流吞吐量為衡量指標，驗證DDRR算法在WMN公平性中的作用，并與Droptail和DRR算法進行比較。仿真產生5條業務流（為了體現業務流之間的差異，數據包的變化范圍較小，實際上在變化范圍較大時DDRR算法仍然適用）。具體仿真參數如表1、2所示。

3.2仿真結果及分析

Droptail算法與DRR算法的仿真結果如圖4、5所示。圖4中0~300 s內業務流1、2、3能夠共享網絡資源，從300s開始瓶頸地區產生的較少跳數的業務流4、5造成其余業務流“餓死”，同時業務流5也嚴重影響了業務流4的吞吐量。圖5中采用DRR算法后，業務流“餓死”現象得到明顯改善。從源節點到網關節點的跳數越多，對單個數據包而言意味著需要在更多節點的隊列中排隊等待并且在發送前競爭信道，因此圖5中各業務流之間的吞吐量略有差異，這與本文的理論分析是一致的。

DRR算法與DDRR算法性能比較如圖6、7所示。圖中只給出300~700 s間的仿真結果。

根據表1中業務流數據包大小，業務流吞吐量從大到小應依次為4＞1＞5＞2＞3。為了最小化遠近效應對性能分析的影響，僅考查跳數接近的業務流。通過對圖6、7的比較可知，業務流2相對于業務流3的吞吐量、業務流4相對于業務流5的吞吐量均有不同程度的提高。其中業務流4的吞吐量與采用DRR算法相比提高了30.3%。此外，從各時間點獲得的吞吐量累計上來看，DDRR算法將網絡總吞吐量提高了約4%。

4結束語

網絡公平性是WMN的關鍵問題之一。WMN中的業務以多跳方式在用戶節點與網關節點之間進行傳輸。若網絡資源的分配不合理，則很容易在網關節點附近產生瓶頸效應，造成網絡的空間不公平性，此現象在網絡負荷較重時尤為明顯。

隊列機制是WMN公平性的一種簡單有效的解決方案。本文分析了DRR算法對于WMN公平性的影響以及存在的問題，提出一種改進的DDRR算法來增強網絡的公平性。這種方法基于LMS算法，以隊列中平均數據包大小來動態調整輪詢算法的權重值，調整吞吐量需求不同的業務流的相對公平性。通過NS2仿真平臺驗證，該算法在提高網絡的公平性的基礎上，區分不同業務流的優先級，并使WMN的整體吞吐量獲得一定的提高。

參考文獻：

[1]

HIERTZ G R， MAX S， ZHAO Rui， et al.Principles of IEEE 802.11s[C]//Proc of the 16th International Conference on Computer Communications and Networks. 2007:10021007.

[2]JANGEUN J， SICHITIU M L. The nominal capacity of wireless Mesh networks[J]. Wrieless Communications， 2003， 10(5): 814.

[3]JAIN S， DAS S R， GUPTA H. Distributed protocols for scheduling and rate control to achieve maxmin fairness in wireless Mesh networks[C]//Proc of IEEE International Symposium on Would of Wireless， Mobile and Multimedia Networks. 2007: 18.

[4]DUFFY K， LEITH D J， LI T， et al. Improving fairness in multihop Mesh networks using 802.11e[C]//Proc of the 4th International Symposium on Modeling and Optimization in Mobile， Ad hoc and Wireless Networks. 2006:18.

[5]RANIWALA A， DE P， SHARMA S， et al. Endtoend flow fairness over IEEE 802.11based wireless Mesh networks[C]//Proc of the 26th IEEE International Conference on Computer Communication. 2007:23612365.

[6]ZHAO Dongmei. Throughput fairness in infrastructurebased IEEE 802.11 Mesh networks[J]. IEEE Trans on Vehicular Technology， 2007， 56(5): 32103219.

[7]LIU T， LIAO Wanjun. Locationdependent throughput and delay in wireless Mesh networks[J]. IEEE Trans on Vehicular Technology， 2008，57(2):11881198.

[8]FLOYD S， JACOBSON V. Random early detection gateways for congestion avoidance[J]. IEEE/ACM Trans on Networking，1993，1(4): 397413.

[9]NANDIRAJU N S， NANDIRAJU D S， SANTHA N L， et al. A cache based traffic regulator for improving performance in IEEE 802.11s based Mesh networks[C]//Proc of IEEE Radio and Wireless Symposium. 2007:293296.

[10]SHREEDHAR M， VARGHESE G. Efficient fair queuing using deficit roundrobin[J]. IEEE/ACM Trans on Networking， 1996， 4(3): 375385.

[11]YAMAKOSHI K， NAKAI K， OKI E， et al. Dynamic deficit roundrobin scheduling scheme for variablelength packets[J]. Electronics Letters， 2002， 38(3): 148149.

[12]WIDROW B， McCOOL J， BALL M. The complex LMS algorithm[J]. Proceedings of the IEEE，1975，63(4): 719720.