鄭博文，劉麗哲

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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