鄭博文，劉麗哲

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

0 引言

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

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

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

1 網(wǎng)絡(luò)編碼技術(shù)

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

圖1 網(wǎng)絡(luò)編碼示例Fig.1 An example of Network coding

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

2 MAC協(xié)議設(shè)計

基于機會網(wǎng)絡(luò)編碼的思想，本文提出了基于網(wǎng)絡(luò)編碼的TDMA移動自組網(wǎng)MAC協(xié)議，基本思想是：將整個TDMA周期分為信令階段和數(shù)據(jù)階段，在信令階段實現(xiàn)網(wǎng)絡(luò)的內(nèi)同步、鄰居發(fā)現(xiàn)并向一跳鄰居節(jié)點廣播解碼包池緩存的數(shù)據(jù)包，在數(shù)據(jù)階段依據(jù)鄰居節(jié)點的解碼包池緩存的數(shù)據(jù)包情況，通過機會網(wǎng)絡(luò)編碼與解碼，進行數(shù)據(jù)通信。

整個TDMA周期分為N個子周期，每個子周期分為信令階段和數(shù)據(jù)階段，其幀結(jié)構(gòu)如圖2所示。其中信令階段包含N個時隙，數(shù)據(jù)階段共有M個數(shù)據(jù)時隙，每個數(shù)據(jù)時隙又包含1個數(shù)據(jù)子時隙和1個ACK子時隙。

圖2 TDMA幀結(jié)構(gòu)Fig.2 Time slots of TDMA

信令階段為每個節(jié)點固定分配時隙，每個節(jié)點在信令階段向一跳范圍內(nèi)的節(jié)點廣播HELLO包，其中HELLO包中包含本機節(jié)點信息、同步信息、數(shù)據(jù)時隙請求與應(yīng)答信息和解碼包池緩存的數(shù)據(jù)包。信令階段實現(xiàn)全網(wǎng)的時間同步、數(shù)據(jù)時隙分配并向全網(wǎng)廣播解碼包池緩存的數(shù)據(jù)包，信令階段處理流程如圖3所示。

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

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

圖4 數(shù)據(jù)階段處理流程圖Fig.4 Flow chart of data phase

與傳統(tǒng)的COPE網(wǎng)絡(luò)編碼機制[13]一樣，考慮節(jié)點在進行數(shù)據(jù)傳輸時，判斷是否進行網(wǎng)絡(luò)編碼以及將哪些數(shù)據(jù)包進行編碼遵循以下一些原則：

① 待編碼的數(shù)據(jù)包應(yīng)是中轉(zhuǎn)發(fā)送的包，而不是由該節(jié)點初始發(fā)送的數(shù)據(jù)包；

② 待編碼的數(shù)據(jù)包的下一跳節(jié)點應(yīng)各不相同；

③ 待編碼的數(shù)據(jù)包應(yīng)為原始數(shù)據(jù)包。

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

3 仿真驗證

本文采用OPNET進行仿真，仿真環(huán)境為20 km×20 km的區(qū)域內(nèi)，分布的16個節(jié)點，保證無孤立節(jié)點。仿真網(wǎng)絡(luò)初始場景如圖5所示。仿真參數(shù)設(shè)置如表1所示。

圖5 仿真網(wǎng)絡(luò)場景Fig.5 Simulation scenario

表1 仿真參數(shù)
Tab.1 Simulation parameters

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

節(jié)點采用通用7層結(jié)構(gòu)，如圖6所示，各模塊實現(xiàn)不同的協(xié)議。

節(jié)點的業(yè)務(wù)由application模塊產(chǎn)生，業(yè)務(wù)包括數(shù)據(jù)訪問、電子郵件、網(wǎng)頁瀏覽和文件傳輸?shù)葮I(yè)務(wù)類型。

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

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

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

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

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

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

4 結(jié)束語

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