無線mesh網絡中編碼感知的跨層優化機制
2016-06-20 09:17:51王偉平王建新
系統工程與電子技術 2016年6期
楊 湘, 王偉平, 王建新
(1. 中南大學信息科學與工程學院, 湖南 長沙 410083;2. 武漢科技大學計算機科學與技術學院, 湖北 武漢 430081)
?
無線mesh網絡中編碼感知的跨層優化機制
楊湘1,2, 王偉平1, 王建新1
(1. 中南大學信息科學與工程學院, 湖南 長沙 410083;2. 武漢科技大學計算機科學與技術學院, 湖北 武漢 430081)
摘要：無線網絡的廣播和易于偵聽的特點,使得網絡編碼技術能夠很好地應用于無線網絡中,以提高無線網絡的吞吐量。通過理論分析和仿真實驗發現,IEEE802.11標準的MAC層機制會使得成功競爭到信道的節點在短時間內在競爭信道方面更具優勢,這會導致編碼節點在短期內獲得的屬于不同編碼流的數據包數目不均衡,從而喪失很多的編碼機會。提出了一種跨層協作的優化機制,在編碼節點根據編碼流的隊列占用情況計算編碼流的優先級別,并將其發送給相應上游節點以調節MAC層參數,進而平衡編碼節點中參與編碼的不同流的隊列占用率,增加編碼機會。仿真實驗結果表明,這種編碼感知的跨層優化機制,能夠很好地協調參與編碼的流的速率,提高了整個網絡的吞吐量。
關鍵詞：無線mesh網絡; MAC協議; 網絡編碼; 跨層優化
0引言
無線網絡天生具有的廣播和易于偵聽的特性,使得網絡編碼技術能夠很好地應用于無線網絡環境,提高了網絡的吞吐能力。流間編碼的研究主要針對網絡局部范圍的編碼和解碼,文獻[1]中首次提出了結合流間編碼的轉發機制COPE,其基本思想是編碼節點通過對編碼條件的判定,將屬于不同單播流的數據包進行編碼操作,然后再進行廣播發送;而參與編碼的單播流的下游節點通過對鄰居節點的偵聽,保證對接收到的編碼包以一個足夠大的概率進行解碼,得到原始數據包。通過這樣的方式,在一次傳輸時間內,發送了多個數據包,從而減少了傳輸次數,提高了網絡的整體吞吐量。
COPE機制提出之后,人們針對流間編碼機制進行了大量的研究。一部分研究工作集中在編碼方案的設計和性能分析上,而另一部分研究工作則集中在基于編碼感知的路由協議方面。在針對編碼方案設計的研究工作中,人們針對各種不同的網絡場景提出了多種編碼方案。其中文獻[2]在2跳局部網絡場景下考慮了2條流進行編碼的情況,對COPE進行建模,并分析了其性能表現以及相對傳統的單徑路由的吞吐量增益;文獻[3]則分析了在2跳局部網絡場景多條流進行編碼的情況下,不同的流數量對吞吐量的影響,并基于“編碼對齊”提出了一種編碼機制,有效地提高了網絡的吞吐量;另外文獻[4-6]則利用“干擾對齊”、“線性規劃”和“整數規劃”等技術討論了編碼方案的設計與實現;文獻[7]則通過建立網絡效用最大化方程,分析并設計了一種結合流間編碼和流內編碼的編碼機制,在考慮鏈路丟包率和不需要鄰居節點偵聽隊列信息的情況下,能很好地提高網絡的吞吐量。目前研究的編碼系統分為兩種:確定編碼系統和隨機編碼系統,確定編碼系統中根據顯式的通知報文來做出編碼決策;而隨機編碼系統根據偵聽鏈路的報文傳輸成功概率來做出編碼決策,文獻[8]推導出了確定編碼系統下的吞吐量區間以及隨機編碼系統下的編碼限制區域,并提出了一種簡單高效的編碼機制,能很好地提高吞吐量。在文獻[9]中作者研究了在考慮一條多播流或多條單播流的不同場景下網絡編碼機制的收益區間。文獻[10]研究了在IEEE802.11s機制下編碼延時對無線mesh網絡吞吐量的影響,并提出了一種自適應調整編碼延時的機制,以提高網絡編碼的吞吐量增益。
此外,大量的研究工作都集中在基于編碼感知的路由協議方面,這類研究工作的出發點在于利用流間網絡編碼提高吞吐量的特點,在尋找路由時將編碼機會作為路由度量值的計算指標之一,更多地增加傳輸路徑上的編碼機會,提出了一系列的基于編碼機會感知的路由協議[11-19]。DCAR[14]提出了一種分布式的基于編碼機會感知的路由協議,在路徑度量值的計算中考慮了鏈路的編碼機會,使得具有更多編碼機會的結點更容易被選為路由的中繼節點,從而利用網絡編碼的優勢提高網絡的整體吞吐量;CORE[15]通過將逐跳機會轉發和流間編碼相結合,達到提高吞吐量的目的;PNCAR[18]在計算鏈路的度量值時考慮了數據流之間的編碼關系,同時將實際網絡映射為一個虛擬網絡以解決了路由協議的等分性問題,能夠在無線多跳的場景下提高網絡的吞吐量。
目前大部分的研究工作都是從路由層面出發,通過改變路由機制使得中間節點獲得更多的編碼機會,或者同時考慮了擁塞、負載均衡等問題,從而提高整體吞吐量。但是很少有人研究MAC層機制對局部網絡編碼機會的影響。文獻[19]指出了現有的MAC層機制會影響編碼流和非編碼流之間的公平性,從而影響編碼機會的產生,提出了一種虛擬隊列的輪詢機制,使得編碼數據包能獲得更多發送機會,從而能更充分發揮網絡編碼提高吞吐量的優勢。但是文獻[19]僅僅考慮了MAC層機制對編碼流與非編碼流之間公平性的影響,并沒有注意到MAC層機制會影響不同編碼流之間的公平性。我們觀察到由于IEEE802.11MAC層的退避窗口調整機制,會導致可編碼流短期內到達編碼節點的數據包數目是不平衡的,從而導致很多編碼機會的喪失。在本文的研究工作中,我們首先分析了IEEE802.11MAC層機制導致短時間內可編碼流到達的不平衡性,并通過仿真實驗驗證了這種不平衡性的存在及對編碼機會的影響。然后,我們基于跨層設計的方法,提出了一種無線mesh網絡中編碼感知的跨層優化機制CACLOM (coding-aware cross-layer optimization mechanism),能有效地增加編碼節點的編碼機會,提高網絡的整體吞吐量。
1IEEE 802.11 MAC機制對編碼機會的影響
流間編碼示意圖如圖1所示,節點存在f1(n1->n3->n2)和f2(n4->n3->n5)兩條流,數據包p1和p2分別屬于流f1和f2,節點n3先后收到p1和p2,由于n5能夠偵聽到n1的數據包p1,而n2能夠偵聽到n4的數據包p2,n3就可以將數據包p1和p2編碼成p1⊕p2數據包進行發送,而當節點n2和n5收到編碼數據包p1⊕p2后就能夠解碼分別得到數據包p1和p2。
圖1 流間編碼示意圖
在IEEE802.11MAC機制中,網絡中的節點共同競爭信道資源,當一個節點競爭到信道并成功發送數據幀之后,它的競爭窗口被設置成最小值CWmin,而發送失敗的節點會將它的競爭窗口增大一倍。這種機制會導致成功競爭到信道的節點比發送失敗的節點在競爭信道方面具備更大的優勢,進而搶占更多的發送機會,從而導致成功獲得信道的流在短期內更易獲得發送機會。在圖1的場景中,節點n1和n4都要向節點n3發送數據包,若節點n1成功競爭到信道則會調低競爭窗口,若此時節點n4發送數據包失敗則會增加自己的競爭窗口,那么節點n1在和節點n4競爭信道時短期會更具備優勢。這樣在節點n3中,短期內屬于流f1的數據包會相對比較多,而屬于流f2的數據包則會相對少甚至沒有,這樣會影響編碼機會的產生。
為了觀察不同鏈路丟包率對吞吐量以及編碼機會的影響,利用圖1的“X”型拓撲網絡做了一個簡單的實驗。節點網絡層采用AODV路由協議,鏈路層采用MAC802.11b協議;節點的通信距離為150m,偵聽距離為330m,無線鏈路帶寬為11Mbps。網絡中節點n1到n2之間有一條UDP流f1,n4到n5之間有一條UDP流f2,速率均為1Mbps,每個數據包大小固定為512字節,按照網絡拓撲結構和偵聽關系,流f1和f2的數據包在節點n3處是可編碼的。除了節點n1到節點n3鏈路之外的其他鏈路丟包率均為0,觀察當n1到n3節點間鏈路的丟包率分別為0、5%、10%、15%、20%,其他鏈路丟包率為0的情況下,吞吐量等一些性能指標的變化。表1記錄了仿真實驗運行20s時間內的測試結果。其中總發送次數是指節點n3發送數據包的次數;緩沖區只存在單流的次數是指節點n3發送數據包時其隊列中只存在編碼流中的某一個單流出現的次數;編碼次數是指節點n3發送編碼數據包的次數;吞吐量是單位時間內數據流f1和f2被成功接收的數據量之和。Q1和Q2分別表示f1和f2兩條流在編碼節點n3緩存隊列中數據包的個數,將隊列中僅存在流f1的情況表示為Q1≠0|Q2=0,而將隊列中僅存在流f2的情況表示為Q1=0|Q2≠0,顯然這兩種情況下n3是沒有編碼機會的。不采用編碼機制是指n3直接轉發;采用COPE機制即n3采用COPE機制對f1和f2的數據包進行編碼發送。
表1 仿真實驗結果
通過表1所示的仿真實驗結果可以看出:
(1) 即使當n1到n3鏈路丟包率為0時,即所有競爭鏈路丟包率一致的情況下,節點n3緩沖隊列中只存在單流的次數占了總發送次數的20%左右,即短期內f1和f2流的數據包到達節點n3是不均衡的,這也驗證了MAC層競爭機制導致短期內流到達的不均衡性,從而影響編碼機會的產生。
(2) 同時我們看到隨著n1到n3鏈路的丟包率逐漸增大,流f1的丟包增多,即節點n3處接收的數據包總數減少,且大部分屬于流f2。由于可編碼包的比例(即編碼次數和總發送次數之比)下降,從而使得吞吐量下降,編碼增益下降。
2CACLOM機制的層級結構
通過第1節的分析和實驗數據,可以看到傳統的IEEE802.11標準MAC層機制不能很好地適應網絡編碼的需要,其引起的可編碼流到達的不平衡性會減少編碼機會,從而不能充分發揮網絡編碼提高吞吐量的優勢。為此設計了CACLOM機制,該機制能夠根據編碼節點中各參與編碼流的隊列占用對比情況,動態地調節各上游節點的MAC層競爭信道能力,使緩沖隊列中各編碼流的數據包更加均衡,獲得更多的編碼機會。
CACLOM機制中,采用了與COPE一樣的數據包編碼方式。所有節點保持偵聽狀態,將偵聽到的數據包緩存在偵聽隊列中用于解碼,每個節點定期廣播自身偵聽隊列中的數據包,同時依據鄰居節點偵聽到的數據包來決定轉發數據包是否能夠編碼,以確保該節點的下一跳節點在接收到編碼數據包之后能解碼。節點接收數據包時,若是編碼數據包,則從偵聽隊列中找到解碼所需的數據包用于解碼還原原始數據包,然后遞交給上層協議進行處理或放入轉發隊列等待調度。與其他基于網絡編碼的轉發機制不同的是,在CACLOM機制中,對數據流賦予了不同的優先級,在MAC層依據數據流的優先級別進行區分處理:MAC層依據該優先級來確定發送數據幀的MAC層參數,使得優先級高的數據幀在競爭信道時具備更強的優勢,以盡快獲得發送機會。CACLOM機制的層級結構如圖2所示,對原有協議棧的改動分為兩個部分,分別為:流優先級的計算與調整和MAC層優先級的處理。
圖2 CACLOM機制層級結構圖
數據流優先級的計算與調整完成的功能是依據發送緩沖隊列中各編碼流數據包的數量,計算得到相對富余的流和相對短缺的流。所謂的富余流是將編碼節點發送隊列中所有能進行編碼的數據包編碼完之后,仍然有數據包需單獨發送的流,與富余流構成編碼關系的流即為短缺流。
根據各編碼流在隊列中數據包個數差值來計算這些編碼流對應的優先級,然后通知上一跳節點,以降低富余流競爭信道的能力同時增強短缺流競爭信道的能力,從而使得到達編碼節點的編碼流的數據包數目趨向平衡,以獲得更多的編碼機會。關于流優先級的計算與調整的詳細描述見第3節。
IP層將數據包遞交給編碼層時,會將該數據包所屬流的優先級值寫入此IP數據包頭部的ToS字段。編碼層按照文獻[1]中的數據包編碼機制對可編碼數據包進行編碼,當參與編碼的原始數據包的優先級別不同的時候,編碼包的優先級別取其中高的優先級別。
IP頭部ToS字段可以在路由層提供區分服務,對優先級別不同的數據包,路由器會區分對待。本文提出的機制是在路由層沒有啟用優先級別的情況下使用,如果路由層已經使用了ToS字段,則應該以路由層的服務質量優先,即保持路由層優先級別高的數據占用較大的傳輸速率,在MAC層維持原來的競爭機制。
MAC層優先級的處理完成的功能是依據攜帶在IP頭部ToS字段中的優先級,將數據幀送入不同的硬件接口隊列。在CACLOM機制中,MAC層采用了IEEE802.11e協議,并對其參數設置進行了一些修改,采用了8個優先級的參數設置,具體每個優先級的參數設置如表2所示,其中AIFS為從檢測到空閑到發送數據幀(進入Contention Window)的間隔時間;CWmin為競爭窗口最小值；CWmax為競爭窗口最大值。可以看出,0號優先級為IEEE802.11b的MAC層采用的參數設置。優先級越高,數據幀就越容易競爭到信道。
表2 修改的IEEE802.11e MAC層參數設置
3數據流優先級的計算與調整
數據流優先級的計算與調整是CACLOM機制的核心。本節中,我們將描述數據流優先級的計算與調整的具體方法。首先定義了節點的流表, 用于保存經過節點的活動流信息;然后引入編碼圖作為分析流之間編碼關系的工具,給出了緩沖隊列中富余流以及富余量的估算方法;在此基礎之上,設計了數據流的優先級計算和調整方法。
3.1流表
CACLOM機制中,每個節點維護一張流表,用以記錄每條經過本節點的“局部流”的信息。在每個節點的流表中,具有相同上一跳節點和下一跳節點的數據流聚合成同一局部數據流。在生成路由表的同時,就根據每條流的上一跳節點、目標節點地址、以及下一跳節點信息生成如表3所示的流表的每條記錄前4項信息。周期性輪詢整個轉發隊列,統計屬于各個流的數據包個數,動態更新queue size表項的值。顯然,對于中間節點進行網絡編碼而言,同一局部流的數據包在可編碼性上是等價的。對應于每一條局部流,流表記錄了<流序號,目的節點,上一跳節點,下一跳節點,數據包數目>五個表項。為了清楚說明流表的含義,我們舉例說明。假設在圖3(a)對應的網絡中,存在7條流,分別為f1(v1->v2->v5->v8->v10)、f2(v1->v2->v5->v7->v9)、f3(v1->v2->v5->v12)、f4(v9->v6->v5->v3->v4)、f5(v6->v5->v8->v11)、f6(v8->v5->v2->v1)、f7(v1->v2->v5->v8->v11)。表3為圖中節點v5的流表,以第一條記錄對應的局部流為例,這條局部流相對于節點v5的上一跳節點為v2,下一跳節點為v8,是由f1和f7兩條端到端數據流匯聚而成的,相應的,數據包數目為f1和f7在節點v5緩沖隊列中的數據包個數總和。
圖3 網絡拓撲結構圖以及對應的編碼圖
流編號目的節點上一跳節點下一跳節點占用隊列長度1v10,v11v2v82+3=52v9v2v763v12v2v1224v4v6v385v11v6v876v1v8v210
3.2編碼圖(coding graph)
基于流表和局部流之間的編碼關系,每個編碼節點可以生成一張編碼圖。編碼圖為一無向圖,反應了經過本節點的局部流之間的編碼關系和局部流的流量大小。編碼圖的構建方法為:局部流fi對應編碼圖中的一個頂點i,頂點i對應的權值Qi表示局部流fi在節點緩存隊列中的數據包的個數,如果兩個局部流具有編碼關系,則相應兩個頂點間增加一條邊,去除沒有任何邊的頂點(即不能與其他任何流進行編碼的局部流)。
這里對局部流具有編碼關系的判定是單純依靠物理位置關系來確定的,即從物理位置關系而言,兩個流的下一跳節點都能得到另一流的上一跳節點的發送數據包,當中間節點編碼后,兩個下一跳節點都能解碼。其定義是:假設存在兩個局部流f1和f2,若f1的下一跳節點即為f2的上一跳節點,或者是其鄰居節點,反之f2的下一跳節點即為f1的上一跳節點,或者是其鄰居節點,就稱f1和f2具有編碼關系。例如圖3(a)中,經過節點v5的兩個流f5(v6->v5->v8->v11)和f6(v8->v5->v2->v1),由于節點v2是節點v6的鄰居,同時f5的下一跳v8即為f6的上一跳節點,因此我們稱f5和f6具有編碼關系。
同樣,多個流之間具有編碼關系是指這多個流中的每個流的下一跳節點從物理位置關系來說能監聽到或者直接獲得其他流上一跳節點發出的數據包,即中間節點將這多個流的數據包做異或編碼后,這多個流的下一跳節點都能解碼。圖3(b)為圖3(a)和表3對應的編碼圖。
3.3富余流估算方法
依據上述編碼圖,給出了估算富余流以及富余量的方法。我們首先通過幾個常見的編碼圖結構簡單說明一下如何利用編碼圖估算富余流及其富余量。
圖4為幾種常見的簡單編碼圖結構。如圖4(a)所示的編碼圖,表示局部流f1和f2具有編碼關系,此時,流f1在該編碼節點的隊列中有10個數據包,而流f2在編碼節點的隊列中有4個數據包。顯然此時流f1為富余流,富余的數據包個數為6。因此,這種情況下的估算方法很簡單,權值大的頂點代表的局部流為富余流,富余量為權值之差6。
圖4 幾種常見的編碼圖結構
類似地,圖4(b)中反映出流f1、f2和f3的數據包能一起編碼的情況。這種情況下,3條流有一部分數據包可以3個編碼在一起發送,在這個例子中,可以形成4個3編碼的編碼包,此后,流f1剩余6個數據包,流f2剩余2個數據包,這時,流f1和流f2的數據包可以進行一起編碼,最后是流f1為富余流,富余的數據包個數為4。這種情況的估算方法是權值最大的頂點代表的流為富余流,富余量為最大權值減去次大的權值。以此類推,同樣的估算方法可以適用于包含多個頂點的全連通編碼圖,即多個數據流可以編碼在一起的情況。
圖4(c)反映的情況稍微復雜一些,流f1不僅能和流f2和f3一起編碼(連通部分1),而且能和流f4進行編碼(連通部分2)。依據采用的COPE編碼機制,總是取隊首數據包與緊接其后的可編碼數據包編碼,并逐個判定是否可以多個編碼在一起。因此f1的數據包是與f2和f3的編碼在一起,還是與f4的數據包編碼在一起,取決于數據包在緩沖隊列中的位置。因此為了估算的合理性,首先分別計算兩個全連通部分的可編碼流量,連通部分1的可編碼流量為6(即為該連通部分的次大頂點權值Q3=6),連通部分2的可編碼流量也是6(Q4=6),我們將f1的流量按比例與可編碼流的權值相消,即相當于將頂點1虛擬成兩個不相連的頂點,將頂點1的權值按比例分配給這兩個虛擬節點。在這個例子中,我們將權值均分。這時,圖4(c)就變成了圖5所示的分解圖,然后再按照圖4(a)和圖4(b)的估算方法,可以得到富余流為f4和f3,富余量分別都是1。
圖4(d)與圖4(c)不同的是,除了權值最大的頂點1在多個連通部分外,該點的鄰居頂點2也在多個連通部分。
為了簡化估算,先將位于多個連通部分的鄰居點2分解成多個虛擬點,分解的方法同樣按比例劃分,即分別計算所在的幾個連通部分的不包含自身的次大頂點權值,按比例分解分配權值。接著按圖4(c)的方法估算富裕流,得到如圖6所示的分解圖。觀察此圖6(b)可知,頂點4和頂點3對應的流為富余流,它們的富余量均為1。
圖5 圖4(c)對應的分解圖
圖6 圖4(d)對應的分解圖
CACLOM機制中,首先依據編碼節點當時的緩存隊列中數據流的編碼關系生成編碼圖CG(V,E,W)。當一個節點的局部流較多時,可能會出現比較復雜的編碼圖。在這種更為一般的編碼圖中,富裕流估算的基本方法和步驟如下：
步驟 1在編碼圖中選擇權值最大的頂點,由該頂點與其直接鄰居點構成局部的編碼圖,在局部編碼圖中對權值相抵消;
步驟 2在權值抵消后,對編碼圖進行裁剪,具體的方法是去除權值為0的頂點及該頂點的所有的邊,合并相應的虛擬節點,其權值為相應虛擬節點剩余權值之和;
步驟 3在裁剪后的殘圖中,遞歸執行步驟1和步驟2,直至殘圖中不存在邊;
步驟 4輸出殘圖中權值不為0的頂點和相應剩余權值,輸出原圖中這些點的鄰居節點。這些權值不為0的頂點代表的流就是富余流,富余量即為該點相消后的剩余權值,其鄰居點代表的流為短缺流。
步驟1中局部編碼圖權值相抵消的具體方法如下:
(1) 若某個點的局部編碼圖包含多個全連通部分。首先,若該點的某個鄰居點屬于多個全連通部分,則為該點生成多個虛擬節點,并將該鄰居點權值分配給虛擬節點,用虛擬節點將多個全連通部分在該鄰居點分離。若僅有該節點被包含在多個全聯通部分,為該點生成相應的虛擬點,權值分配給虛擬節點,將局部編碼圖在該點出分拆成多個獨立的全連通部分。
(2) 對于大于等于3個頂點的連通部分,即如圖4(b)的情況,相抵消的具體方法是將權值最大的頂點的權值改為最大權值減去次大權值,其他點權值都改為0。
(3) 對于只有兩個點的全連通部分,將原來權值大的頂點的權值改為權值之差,原來權值小的點賦值為0。
關于在編碼圖中查找富余流的算法描述如圖7～圖9所示。
圖7 Finding _Richflow(CG)查找富余流方法
圖8 Weight_offset(G)權值抵消算法
3.4流優先級的計算與調整
CACLOM機制中,各流的優先級初始時刻均設置為0。當編碼節點根據估算方法得到了剩余權值不為0的頂點和其權值后,將通知上一跳節點降低這些頂點對應的流的發送優先級,同時提升與其鄰居節點對應的流的優先級別。為了盡量減少這種調節機制對整體信道競爭激烈程度的影響,我們在參數調節上盡量讓富余流與其對應的短缺流的優先級調整量是平衡的,使得所有流競爭信道的能力維持在一定水平,保證CACLOM機制不會帶來更多的MAC層沖突。
具體的優先級計算方法如下:
假設估算得到的剩余編碼圖中頂點k對應剩余權值為Qk(Qk>0),計算頂點k對應的局部編碼流fk的優先級調整量公式為
(1)
式中,N為編碼節點緩沖隊列的最大長度;Δ為CACLOM機制中設定的優先級的個數，如表2所示,Δ=8。
同時計算在原始編碼圖中頂點k的鄰居i所對應流fi的優先級調整量。由于可能存在多個鄰居點,意味著多個流可以與流fk編碼,這里的策略是同時提高這些流的優先級別,只是提高量作了平均。因此流fi的優先級調整量計算公式為
(2)
式中,m為頂點k的鄰居節點的數目。
圖9 Decompose(G)分解子圖算法
當編碼節點有數據包要發送時,將計算得到的流的優先級調整量信息攜帶在數據包中;鄰居節點偵聽到此數據包時,將對應本節點的流調整信息取出,并將相應的流優先級調整為Δ/2+η。
圖10 編碼圖中查找富余流算法示例圖
在CACLOM機制中,優先級信息的傳輸是采用攜帶的方式,在編碼節點定期生成編碼圖計算出優先級調整量后,用一個發送數據包攜帶相應的調整信息。數據包格式如圖11所示。CACLOM數據包格式與COPE數據包格式基本相同,只是在COPE數據包格式的基礎上增加了“優先級調整信息”字段,其中PRI_REPORT_NUM為攜帶的優先級調整記錄的條數,每條記錄是針對某個上游節點的一條流的調整信息,對應一個
仍然是以圖3和表3所示的網絡為例,在第3.3節最后得到Q1=2.5、Q5=3.5,其他頂點的權值均為0,節點隊列的最大長度N為10,設定的優先級的個數Δ=8。針對Q1=2.5,首先根據式(1)計算頂點1對應的流的優先級調整值h1=-|2.5×8/(10×2)|=-1,根據式(2)計算頂點1的鄰居頂點6對應的流的優先級調整值h6=|2.5×8/(10×2)|=1。類似的計算頂點5及其鄰居頂點6對應的流的優先級調整值分別為h5=-|3.5×8/(10×2)|=-1和h6=|3.5×8/(10×2)|=1,合并頂點6對應的流的優先級調整值h6=2。所以流f1和f5的優先級將被調整為4-1=3,而流f6的優先級將被調整為4+2=6。
圖11 CACLOM數據包格式圖
4仿真實驗
在本節中,將在簡單的“X”型簡單拓撲結構網絡和隨機部署節點的復雜拓撲結構網絡中,測試CACLOM機制的性能表現。在下面的仿真實驗中,如無特別說明,各參數設置如表4所示。
表4 仿真實驗參數設置
4.1簡單網絡拓撲下仿真實驗
為了驗證CACLOM機制的有效性,模擬仿真了CACLOM機制,將其性能與COPE機制作了比較。我們首先在如圖1所示的簡單網絡拓撲下進行仿真。網絡中存在兩條交匯于節點n3的UDP流,分別是n1到n2的流f1,n4到n5的流f2,速率均為1 Mbps。
在仿真中兩者的網絡層均采用按需路由機制AODV,不同的是COPE機制中MAC層采用IEEE802.11b,而CACLOM機制采用了結合流量估算和優先級調整的改進IEEE802.11e機制。測試中改變n1到n3節點間鏈路的丟包率,分別為0、5%、10%、15%、20%,將COPE協議與CACLOM機制相比較,觀察在此過程中網絡總吞吐量(所有流吞吐量的總和)、公平系數(兩條參與編碼流的吞吐量比值)、編碼節點參與編碼流的隊列占用對比情況，具體如圖12所示。
從圖12(a)可以看出,CACLOM機制較單純的COPE機制在吞吐能力上面提升了大概20%～80%,鏈路質量差異越大,吞吐量提升越明顯。這是因為隨著n1->n3鏈路丟包率的增加,使得編碼節點n3成功接收到f1的數據包數目與f2的數據包數目的差異越來越大,造成編碼機會的減少。而CACLOM機制在這種情況下,會適當提高f1的競爭信道能力,使得n3節點上流f1和f2的數據包數目趨向平衡,從而提高了網絡編碼的機會,從而使得吞吐量是能夠得到提高的。
圖12(b)給出了本次仿真實驗中兩種機制公平性的比較,其中公平系數的計算方法是兩條流所獲得的平均帶寬的比值。
圖12(c)給出了兩種機制中流f1和f2的端到端延時的對比,其中流f2為富余流,流f1為與其對應的短缺流。可以看出,在部署了CACLOM機制之后,流f2的端到端延時基本沒有發生變化,而流f1的延時則減小了很多。之所以能夠不影響流f2的延時,是因為在編碼轉發的情況下,流f2數據包會與流f1數據包編碼發送,從而不會對流f2數據包的轉發造成影響。
表5給出的仿真實驗中的編碼次數和隊列中數據包數目統計結果也驗證了CACLOM機制可以調節參與編碼的數據流到達速率,使得編碼節點n3上的編碼機會增多,從而提高了網絡的吞吐量。
如表5所示,我們可以看到CACLOM在Q1=0|Q2≠0和Q1≠0|Q2=0出現的次數上都有非常明顯的減少且更加趨近平衡,說明f1和f2兩條流在隊列占用率上面更加平衡,不能編碼的情況減少;從編碼次數的指標上來看,CACLOM機制增加了編碼節點的編碼次數,能更好地發揮網絡編碼的優勢。
為了測試節點緩存大小N對網絡性能的影響,在上述仿真實驗場景中,固定n1到n3節點間鏈路的丟包率為10%,僅改變節點緩存大小N的值,觀察其對網絡編碼次數以及總吞吐量的影響，具體如圖13所示。
圖12 總吞吐量、公平指數和端到端延時對比圖
圖13 不同節點緩存大小對性能的影響
通過圖13可以看出,當節點緩存大小變化時,相對于COPE機制,CACLOM機制均能獲得更多的編碼機會,以及很好的吞吐量增益。在接下來的仿真實驗中,節點緩存大小取NS2中的默認值50 packets。
表5 編碼次數以及隊列情況
在CACLOM機制中,對參與編碼的數據流中速率較小的流賦予了較高的優先級,而速率較大的流賦予了較低的優先級。為了觀察CACLOM機制對于速率不同的編碼流的影響, 我們在上述實驗中僅改變編碼流的發送速率,同時固定所有鏈路的丟包率為0,觀察在各種情況下兩條流所獲得的帶寬對比情況。
仿真實驗結果如表6所示,當網絡比較空閑的時候(表6中的前兩條記錄對應的情況),CACLOM機制下流f1和f2所獲得的帶寬與其發送速率成比例。這是因為盡管提高了速率較低流的信道競爭能力,但是由于網絡中有足夠的帶寬資源,使得被賦予較低優先級的數據流仍然能獲得足夠的帶寬。同時,當網絡較擁塞的時候(表6中的后兩條記錄對應的情況),流f1和f2所獲得的帶寬都高于COPE機制,但流f2獲得了更好地帶寬/速率比,這說明了CACLOM機制能提高流速較低的流搶占信道的能力,使得網絡中產生了更多的編碼機會,從而能夠更好地發揮網絡編碼提高網絡吞吐量的優勢。
4.2復雜網絡拓撲下仿真實驗
為了測試更為一般的網絡拓撲、多流并存情況下協議的特征,我們仿真了更為一般的網絡拓撲場景,在1 000×1 000的區域內隨機部署25個節點,然后每隔30 s加入一條UDP流,部署多條UDP流,流數為3～12條不等,速度為100 kbps,每條鏈路丟包率在0%～10%之間隨機取值。
表6 編碼流速率不同情況下帶寬占用情況
由于一些相關研究已經在COPE機制上改進并提出了編碼感知的路由協議,為了驗證CACLOM機制與這些已經考慮了編碼機會的路由機制結合之后的有效性,在測試中選擇了文獻[15]提出的編碼感知路由協議PNCAR,并且在其上結合了MAC層優先級調整機制,對結合前后的性能進行了比較。(PNCAR是一個編碼感知的路由協議,它在選擇路由時考慮了編碼機會的因素,同時解決了路由選擇的等分性(isotonic)問題,性能上比單純的COPE機制要好。)用PNCAR+CACLOM表示結合了MAC層優先級調整之后的機制。
仿真實驗在10種不同的隨機網絡場景下進行,實驗結果取10次實驗的均值,同時我們給出了當流的數目為9時,10種隨機網絡場景下各“路由協議+編碼機制”組合在總吞吐量和編碼次數上的對比情況。測試的性能指標包括:
(1) 網絡總吞吐量(所有流吞吐量的綜合);
(2) 總編碼次數(所有編碼節點編碼次數之和);
圖14為不同網絡負載情況下,網絡總吞吐量和編碼次數均值的變化情況,而圖15為當網絡中存在9個流時,各個不同網絡場景下的吞吐量和編碼次數。
圖14 平均吞吐量和編碼次數的對比圖
圖15 流數目為9時不同網絡場景的吞吐量和編碼次數的對比圖
觀察圖14和圖15可得:
(1) 從圖14可以看出,采用同樣的路由協議,引入CACLOM機制之后(即COPE與CACLOM相比較,PNCAR與PNCAR+CACLOM相比較),在流的數目超過6以后,吞吐量和編碼包數目都有很明顯的提升。說明CACLOM機制能夠有效地增加網絡中的編碼機會,更好地發揮網絡編碼提高吞吐量的優勢。圖15中給出了不同場景下的吞吐量和編碼次數的比較,可以看出在測試的所有場景中,引入MAC層優先級別調整機制CACLOM后,網絡中的編碼次數和整體吞吐量都得到了有效的提高。
(2) PNCAR與CACLOM的結合較單純采用一種機制進一步提高了吞吐量。這是因為PNCAR在選擇路由時考慮鏈路的編碼機會,能夠將更多的網絡流量聚合到具有編碼機會的鏈路上來,使得網絡擁有更多的編碼節點。同時,CACLOM機制能夠增加編碼節點上的編碼機會,也就是說,CACLOM機制能夠進一步放大基于編碼感知的路由協議相對于最短路徑路由協議的優勢。
圖16為4種機制的公平性比較。由于PNCAR有流量匯聚的特點,流量匯聚之后會使得流之間競爭帶寬資源的情況加劇,故采用了PNCAR的機制的公平性比采用COPE機制公平性要稍差一些。而CACLOM機制和PNCAR+CACLOM則有比較好的公平性表現。這是因為進行網絡編碼的節點在發送一個數據包時,如果隊列中有符合編碼條件的數據包,節點會將多個數據包編碼進行發送,這種行為會改善網絡流之間的公平性,并且編碼次數越多,這種改善公平性的效果會越明顯。這也從側面說明了本文提出的CACLOM機制能夠有效地增加編碼機會,從而提升吞吐量。
圖16 流的數目 vs. Jain公平指數
5結論
本文首先分析了IEEE802.11標準的MAC機制帶來的短期競爭信道不公平的特點,并指出這會減少編碼機會的產生,進而結合跨層優化的思想,提出了一種具有編碼機會感知的跨層協作機制CACLOM。這種機制通過檢查參與編碼流在編碼節點隊列中的占用情況以通知相應上游結點調整MAC參數,從而調節參與編碼流的速率,使得編碼節點上不同編碼流的數據包數目更加平衡,最終達到增加編碼次數,提高網絡整體吞吐量的目的。通過NS2上的仿真實驗表明,CACLOM機制能夠平衡編碼流競爭信道的能力,有效地增加了編碼機會,提高了網絡的整體吞吐量。
參考文獻：
[1] Katti S, Rahul H, Hu W, et al. XORs in the air: practical wireless network coding[J].IEEE/ACMTrans.onNetworking, 2008, 16(3): 497-510.
[2] Wang C C, Shroff N, Khreishah A. Cross-layer optimizations for intersession network coding on practical 2-hop relay networks[C]∥Proc.oftheIEEEAsilomarConferenceonSignals,SystemsandComputers, 2009: 771-775.
[3] Wang C C. On the capacity of wireless 1-hop intersession network coding—a broadcast packet erasure channel approach[J].IEEETrans.onInformationTheory, 2012, 58(2): 957-988.
[4] Ramakrishnan A, Das A, Maleki H, et al. Network coding for three unicast sessions: interference alignment approaches[C]∥Proc.ofthe48thIEEEAnnualAllertonConferenceonCommunication,Control,andComputing, 2010: 1054-1061.
[5] Eryilmaz A, Lun D S. Control for inter-session network coding[C]∥Proc.ofthe3rdIEEEWorkshoponNetworkCoding,Theory&Applications, 2007: 1-9.
[6] Traskov D, Ratnakar N, Lun D S, et al. Network coding for multiple unicasts: an approach based on linear optimization[C]∥Proc.oftheIEEEInternationalSymposiumonInformationTheory, 2006: 1758-1762.
[7] Seferoglu H, Markopoulou A, Ramakrishnan K K. I2NC: intra-and inter-session network coding for unicast flows in wireless networks[C]∥Proc.ofthe30thIEEEInternationalConferenceonComputerCommunications, 2011: 1035-1043.
[8] Paschos G S, Fragiadakis C, Georgiadis L. Wireless network coding with partial overhearing information[C]∥Proc.ofthe32ndIEEEInternationalConferenceonComputerCommunications, 2013: 2337-2345.
[9] Keshavarz-Haddad A, Riedi R H. Bounds on the benefit of network coding for wireless multicast and unicast[J].IEEETrans.onComputing, 2014, 13(1): 102-115.
[10] Carrillo E, Ramos V. On the impact of network coding delay for IEEE 802.11 s infrastructure wireless mesh networks[C]∥Proc.ofthe28thIEEEInternationalConferenceonAdvancedInformationNetworkingandApplications, 2014: 305-312.
[11] Wei X, Zhao L, Xi J, et al. Network coding-aware routing protocol for lossy wireless networks[C]∥Proc.ofthe5thIEEEInternationalConferenceonWirelessCommunicationsNetworkingandMobileComputing, 2009: 1-4.
[12] Fan K, Li L, Long D. Study of on-demand cope-aware routing protocol in wireless mesh networks[J].JournalonCommunications, 2009, 30(1):128-34.
[13] Wu Y, Das S M, Chandra R. Routing with a Markovian metric to promote local mixing[C]∥Proc.ofthe26thIEEEInternationalConferenceonComputerCommunications, 2007: 2381-2385.
[14] Le J, Lui J C S, Chiu D M. DCAR: distributed coding-aware routing in wireless networks[J].IEEETrans.onMobileComputing, 2010, 9(4): 596-608.
[15] Yan Y, Zhang B, Zheng J, et al. CORE: a coding-aware opportunistic routing mechanism for wireless mesh networks[J].IEEEWirelessCommunications, 2010, 17(3): 96-103.
[16] Zhang J, Zhang Q. Cooperative network coding-aware routing for multi-rate wireless networks[C]∥Proc.ofthe28thIEEEInternationalConferenceonComputerCommunications, 2009: 181-189.
[17] Jhang M F, Lin S W, Liao W. C2AR: coding and capacity aware routing for wireless ad hoc networks[C]∥Proc.oftheIEEEInternationalConferenceonCommunications, 2010: 1-5.
[18] Peng Y, Yang Y, Lu X, et al. Coding-aware routing for unicast sessions in multi-hop wireless networks[C]∥Proc.oftheIEEEGlobalTelecommunicationsConference, 2010: 1-5.
[19] Zhao F, Médard M. On analyzing and improving COPE performance[C]∥Proc.ofInformationTheoryandApplicationsWorkshop, 2010: 1-6.
[20] Jain R, Chiu D M, Hawe W R.Aquantitativemeasureoffairnessanddiscriminationforresourceallocationinsharedcomputersystem[M]. Eastern Research Laboratory: Digital Equipment Corporation, 1984: 5-10.
楊湘(1980-),男,博士研究生,主要研究方向為網絡協議性能優化、網絡編碼。
E-mail:yangxiang1027@163.com
王偉平(1969-),女,教授,博士研究生導師,博士,主要研究方向為網絡優化、網絡編碼、網絡安全、匿名通信。
E-mail:wpwang@mail.csu.edu.cn
王建新(1969-),男,教授,博士研究生導師,博士,主要研究方向為參數計算理論、網絡優化理論。
E-mail:jxwang@mail.csu.edu.cn
A coding-aware cross-layer optimization mechanism for wireless mesh network
YANG Xiang1,2, WANG Wei-ping1, WANG Jian-xin1
(1.SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China;2.SchoolofComputerScienceandTechnology,WuhanUniversityofScienceandTechnology,Wuhan430081,China)
Abstract:Due to the inherent broadcast and overhearing capabilities of wireless network, the network coding technique is very suitable for the wireless mesh network. Through the theoretical analysis and simulation results, it is observed that the MAC mechanism of the IEEE802.11 standard may make the node more competitive after accessing the channel successfully, which unbalances the amount of packets of different coding flows in the buffer of the coding node in a short period, and finally, some coding opportunities are lost. A cross-layer optimization mechanism is proposed. In the mechanism, the priorities of coding flows are calculated by using the buffer occupancy information and are sent to the upstream node, and then the corresponding upstream node adjusts its MAC parameters, which yields more coding opportunities. Simulation results show that the proposed mechanism can adjust the rate of flows whose packets can be encoded together adaptively, and improve the total throughput of network.
Keywords:wireless mesh network; MAC protocol; network coding; cross-layer optimization
收稿日期：2015-02-05；修回日期：2015-05-09；網絡優先出版日期：2015-12-29。
基金項目：國家自然科學基金(61173169)資助課題
中圖分類號：TP 393
文獻標志碼：A
DOI:10.3969/j.issn.1001-506X.2016.06.29
作者簡介：
網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20151229.1142.004.html
