基于網絡編碼的TDMA移動自組網MAC協議設計

鄭博文，劉麗哲

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

0 引言

移動自組織網絡(Mobile Ad Hoc Network,MANET)作為一種不借助基礎實施的移動通信網絡，在地震救援、火災救援、林區通信和安保通信等多個領域有廣泛的應用。移動自組織網絡的業務類型主要有單播、廣播和多播。單播源節點和目的節點都分別只有一個，廣播是一個源節點以洪泛的方式向網絡中的所有節點發送消息，廣播業務資源利用率高，但是造成網絡擁塞。多播是源節點向部分多個目的節點發送消息。多播通信在移動自組網中具有廣泛的應用[1]，如文件分發、視頻會議、分組話音及事件通知等。MANET資源調度的好壞直接影響了服務質量，如何對MANET進行有效的資源調度，提高多播業務吞吐率和服務質量，是當前亟待解決的研究問題。

針對多播業務的資源調度問題，傳統的做法是在多跳網絡構建到達各節點的調度樹。多播業務所能取得的理論最高速率由最大流最小割定理(Max-Flow Min-Cut Theorem)[2]決定。傳統的存儲轉發方式無法取得最大流最小割定理下的網絡容量上限。2000年AHLSWEDE R[3]等人提出了網絡編碼理論，對來自不同節點的數據包進行編碼，并理論證明在多播場景下可以取得由最大流最小割定理決定的網絡容量上限。由于機會路由[4-6]和網絡編碼可以通過創造性地利用無線介質的廣播性質來顯著提高無線網絡的性能[7]，網絡編碼一直是學術界的研究熱點之一。針對網絡編碼在移動自組網MAC協議設計方面的應用，文獻[8]將基于網絡編碼的MAC機制相關研究工作歸納為3個方面：① 通過合理的MAC機制設計以尋求更多的潛在編碼機會；② 網絡編碼和MAC機制進行聯合設計，使編碼增益和網絡吞吐量達到最優化；③ 改進MAC機制解決網絡編碼中機會偵聽、偽廣播等引起的沖突問題。Mendoza-Almanza J等人[9]提出了一種基于機器學習技術的協作網絡動態編碼系統，將動態網絡編碼與機器學習技術相結合，使用決策樹協調節點在網絡編碼中的角色。Sun B等人[10]提出了一種基于網絡編碼的無線傳感器網絡滑動窗口最大壽命算法，仿真表明該算法提高了無線傳感器網絡的吞吐量和網絡壽命。GU J等人[11]提出基于緩沖區輔助的物理層網絡編碼(Physical Layer Network Coding,PLNC)技術，根據最大似然和最小均方誤差設計標準設計基于最佳線性網絡編碼矩陣，以改善協作網絡上的數據傳輸。Xing H等人[12]研究了基于網絡編碼的組播中的負載均衡優化問題，并提出了一種改進的人工蜂群算法(Modied Articial Bee Colony algorithm,MABC)。

KATTI S等人[13]首次提出了機會網絡編碼架構(Completely Opportunistic Network Coding,COPE)，并通過實驗證明了COPE方案的有效性。COPE方案使用的MAC協議是IEEE802.11。IEEE802.11協議采用CSMA/CA機制來競爭無線信道的使用權，從而實現接入控制，但是CSMA/CA網絡在節點數量較大時，可能造成網絡中節點傳輸沖突頻繁，等待時間長，信道利用率低等問題。因此，對于高并發且業務量較大的網絡，更適合采用時分多址接入協議(Time Division Multiple Access，TDMA)。近來已有一些研究者[8-16]考慮在MAC層采用TDMA的方式來支持無線多跳網中基于網絡編碼的數據傳輸。但目前在無線多跳網絡中，基于TDMA的網絡編碼傳輸機制研究還比較少，已有的研究還是將網絡編碼與TDMA機制進行簡單的結合。很少有研究者針對基于TDMA的無線多跳網絡，研究動態時變的無線鏈路以及受限的無線節點資源，對網絡中網絡編碼數據傳輸性能的影響，并設計與之相適應的通信傳輸協議。為了得到高效的網絡編碼傳輸協議，本文將COPE機會網絡編碼機制與TDMA自組網相互結合，提出了一種基于網絡編碼的TDMA移動自組網MAC協議，并通過仿真驗證了算法的有效性。

1 網絡編碼技術

網絡編碼的基本思想是對來自不同節點的多個數據包進行編碼傳輸，從而提高了單次傳輸的信息量，減少發送次數，從而達到提高網絡吞吐量的目的。網絡編碼的基本思想如圖1所示，考慮網絡中節點A、節點C和節點B組成鏈狀網絡，節點A和節點B均有業務發給對方，傳統的存儲轉發方法需要4個時隙，如圖1 (a)所示；采用網絡編碼的方法如圖1(b)所示，節點A和節點B分別發送數據包至及節點C，節點C將需要中繼轉發的數據包a和數據包b進行異或運算得到a?b后進行發送，節點A收到后與本地數據包a異或后得到b，節點B同理，完成整個傳輸過程需要3個時隙。

圖1 網絡編碼示例Fig.1 An example of Network coding

KATTI S[13]等人提出的COPE方案的基本操作為：每個節點對整個信道進行偵聽并緩存偵聽到的數據包；同時，一跳范圍內的節點相互交換信息，以掌握其鄰居節點的緩存數據信息；每個節點根據其一跳范圍內各鄰居節點的緩存數據信息來確定編碼機會，執行編碼操作，并以偽廣播的方式來發送編碼包。由于COPE方案采用逐比特異或操作，算法復雜度低，易于實現和大規模部署。

2 MAC協議設計

基于機會網絡編碼的思想，本文提出了基于網絡編碼的TDMA移動自組網MAC協議，基本思想是：將整個TDMA周期分為信令階段和數據階段，在信令階段實現網絡的內同步、鄰居發現并向一跳鄰居節點廣播解碼包池緩存的數據包，在數據階段依據鄰居節點的解碼包池緩存的數據包情況，通過機會網絡編碼與解碼，進行數據通信。

整個TDMA周期分為N個子周期，每個子周期分為信令階段和數據階段，其幀結構如圖2所示。其中信令階段包含N個時隙，數據階段共有M個數據時隙，每個數據時隙又包含1個數據子時隙和1個ACK子時隙。

圖2 TDMA幀結構Fig.2 Time slots of TDMA

信令階段為每個節點固定分配時隙，每個節點在信令階段向一跳范圍內的節點廣播HELLO包，其中HELLO包中包含本機節點信息、同步信息、數據時隙請求與應答信息和解碼包池緩存的數據包。信令階段實現全網的時間同步、數據時隙分配并向全網廣播解碼包池緩存的數據包，信令階段處理流程如圖3所示。

圖3 信令階段處理流程圖Fig.3 Flow chart of signaling phase

數據階段實現數據傳輸和ACK確認，數據階段處理流程如圖4所示。數據階段，在本節點的發送時隙，從當前緩存隊列中取出數據包，如果是編碼包則直接發送，否則進行編碼機會判斷，然后發送。編碼層機會的判斷規則為：一是當上層的數據包到達時，如果能編碼則編碼后立即發送；二是當發送隊列里的數據包等待時間為0時，會再一次判斷是否有編碼機會的存在，如果有則編碼后發送，如果沒有也不再等待，直接發送數據包。

圖4 數據階段處理流程圖Fig.4 Flow chart of data phase

與傳統的COPE網絡編碼機制[13]一樣，考慮節點在進行數據傳輸時，判斷是否進行網絡編碼以及將哪些數據包進行編碼遵循以下一些原則：

① 待編碼的數據包應是中轉發送的包，而不是由該節點初始發送的數據包；

② 待編碼的數據包的下一跳節點應各不相同；

③ 待編碼的數據包應為原始數據包。

編碼機會的判斷是通過要發送數據包下一跳節點的解碼包池中緩存數據包信息判斷的。遍歷本節點的發送隊列的數據包pk(i)，如果發送數據包pk下一跳節點的解碼包池中有數據包pk(i)的信息，并且pk(i)下一跳節點的解碼包池中也有pk的信息，表示pk和pk(i)兩個包有編碼機會，兩個數據包可以編碼在一起后發送。本文采用異或編碼，由于本文采用TDMA的MAC機制，數據包的大小相同，因此直接將兩個數據包的信息進行異或操作，pkencode=pk?pk(i)。

3 仿真驗證

本文采用OPNET進行仿真，仿真環境為20 km×20 km的區域內，分布的16個節點，保證無孤立節點。仿真網絡初始場景如圖5所示。仿真參數設置如表1所示。

圖5 仿真網絡場景Fig.5 Simulation scenario

表1 仿真參數
Tab.1 Simulation parameters

參數數值工作頻率600 MHz信道帶寬4.0 MHzN16M256ACK時隙長度200 μs數據時隙長度2.0 ms控制時隙長度200 μs移動模型Random Waypoint

節點采用通用7層結構，如圖6所示，各模塊實現不同的協議。

節點的業務由application模塊產生，業務包括數據訪問、電子郵件、網頁瀏覽和文件傳輸等業務類型。

圖6 OPNET仿真流程圖Fig.6 Flow chart of the OPNET simulation

為了仿真業務負載對網絡編碼增益的影響，本文仿真了低業務負載、中等業務負載和高業務負載3種等級，分別觀察3種業務量下的吞吐量的提升。吞吐量的計算同上，為方便比較性能的提升，將吞吐量歸一化輸出。編碼層數據包的等待時間為固定值0.7 s，解碼池的緩存時間也為固定值6 s。低業務量、中等業務量和高業務量時得到的仿真結果如圖7～圖9所示。未使用編碼時，采用MAC層的端到端時延來表示編碼層的端到端時延。

圖7 低業務量負載時歸一化吞吐量和時延對比Fig.7 Comparison of normalized throughput and delay under low traffic load

圖8 中等業務量負載時歸一化吞吐量和時延對比Fig.8 Comparison of normalized throughput and delay under medium traffic load

圖9 高業務量負載時歸一化吞吐量和時延對比Fig.9 Comparison of normalized throughput and delay under high traffic load

通過對比圖7～圖9中的歸一化吞吐量可以發現，編碼技術的引進確實能提高系統的吞吐量。當業務負載為輕時，所提升的性能大約為10%，而隨著業務量的增加，網絡拓撲的吞吐量也隨之提高，可穩定到20%。當業務量進一步增加時會穩定為21%。而我們編碼的理論上界為33.3%，這是由于在網絡中，存在大量的路由協議數據包，該類數據包為廣播數據包，而廣播的數據包是不存在編碼機會的。對比圖7～圖9中的時延可以發現，在引入網絡編碼技術后，節點之間端到端的時延有所增加。當業務量越少，端到端的時延也就越小，隨著業務的增加，編碼的機會也越來越多，此時端到端的時延也隨之增加。

4 結束語

網絡編碼作為提升無線網絡吞吐量的重要手段之一，一直是學術界的研究熱點，本文首先介紹了網絡編碼技術的研究現狀；然后基于COPE機會網絡編碼的思想，提出了一種基于網絡編碼的TDMA移動自組網MAC協議，在信令階段廣播本地解碼包池緩存的數據包，在數據階段采用機會網絡編碼進行數據傳輸，并分別給出了TDMA時隙結構、MAC層處理流程和編碼層的具體實現細節；最后通過OPNET在低業務負載、中等業務負載和高業務負載的情況下進行了仿真，仿真結果表明本文提出的基于網絡編碼的TDMA移動自組網MAC協議能夠提升網絡吞吐量。