楊茂保，徐利亞，葛明珠，陳 希，舒長(zhǎng)興

(1.九江學(xué)院電子商務(wù)學(xué)院，江西 九江 332005；2.九江學(xué)院信息科學(xué)與技術(shù)學(xué)院，江西 九江 332005；3.九江學(xué)院信息技術(shù)中心，江西 九江 332005；4.軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430072)

0 引言

無(wú)人機(jī)是一種可以自主飛行不需人為操作的飛行器，在軍用和民用領(lǐng)域有廣泛用途，如森林火災(zāi)監(jiān)測(cè)[1]，災(zāi)害救援[2]，無(wú)線(xiàn)網(wǎng)絡(luò)中繼[3]， 增加網(wǎng)絡(luò)容量[4]等。盡管單無(wú)人機(jī)系統(tǒng)已經(jīng)使用了很多年，但是多無(wú)人機(jī)系統(tǒng)與單無(wú)人機(jī)系統(tǒng)相比有很多優(yōu)勢(shì)。而多無(wú)人機(jī)系統(tǒng)面臨的一個(gè)重要挑戰(zhàn)就是它們之間的通信[5-7]，包括無(wú)人機(jī)之間的通信，以及無(wú)人機(jī)與基站之間的通信。在某些場(chǎng)景中，通信鏈路可能長(zhǎng)達(dá)幾百公里，這樣的遠(yuǎn)距離通信鏈路可能會(huì)導(dǎo)致：1)低服務(wù)質(zhì)量，信號(hào)質(zhì)量和通信距離成反比，遠(yuǎn)距離鏈路將導(dǎo)致更高的丟包率。2)信道利用率低，遠(yuǎn)距離引起較大的信號(hào)傳播延遲，對(duì)于高速網(wǎng)絡(luò)來(lái)說(shuō)這種延遲不能被忽略。傳統(tǒng)網(wǎng)絡(luò)協(xié)議設(shè)計(jì)時(shí)，單信道通常只允許單個(gè)信號(hào)進(jìn)行傳輸，這種方式在傳播延遲較大時(shí)將引起很大的浪費(fèi)。

針對(duì)近距離無(wú)線(xiàn)網(wǎng)絡(luò)設(shè)計(jì)的MAC協(xié)議，如802.11系列，不能被直接應(yīng)用于這種遠(yuǎn)距離鏈路場(chǎng)景中。載波偵聽(tīng)/沖突避免(CSMA/CA)通過(guò)偵聽(tīng)信道是否空閑來(lái)決定數(shù)據(jù)發(fā)送與否，這種方式在遠(yuǎn)距離鏈路中需要花費(fèi)較大的時(shí)間開(kāi)銷(xiāo)，且容易出現(xiàn)隱藏終端等問(wèn)題。文獻(xiàn)[8—9]通過(guò)修改802.11無(wú)線(xiàn)網(wǎng)卡，將之用到遠(yuǎn)距離網(wǎng)絡(luò)中，但實(shí)驗(yàn)證明這并不是一個(gè)理想的選擇[10]。與競(jìng)爭(zhēng)型協(xié)議相比，預(yù)約型MAC協(xié)議通常通過(guò)集中調(diào)度以一定的代價(jià)可以提供相對(duì)較好的網(wǎng)絡(luò)服務(wù)質(zhì)量，如Jang等[11]提出了一種基于TDMA的可靠航空通信的協(xié)議LBTM，Temel等[12]提出一種根據(jù)地理位置來(lái)動(dòng)態(tài)分配時(shí)隙的方法，Araghizadeh等[13]根據(jù)距離遠(yuǎn)近為傳感器節(jié)點(diǎn)設(shè)計(jì)了一種公平的接入方案。另外，現(xiàn)在更多的研究側(cè)重于混合式協(xié)議或者跨層協(xié)議設(shè)計(jì)，以此獲得更好的網(wǎng)絡(luò)性能。Cai等[14]利用全雙工以及多包接收技術(shù)，設(shè)計(jì)了一種針對(duì)無(wú)人機(jī)自組織網(wǎng)絡(luò)的MAC協(xié)議，而Alshbatat等[15]則混合利用全向天線(xiàn)和定向天線(xiàn)，提出了一種無(wú)人機(jī)網(wǎng)絡(luò)的自適應(yīng)MAC協(xié)議。但這些協(xié)議都沒(méi)有考慮傳播延遲對(duì)網(wǎng)絡(luò)的影響，設(shè)計(jì)的MAC協(xié)議也基本忽略傳播延遲。

針對(duì)上述問(wèn)題，需要一個(gè)更合適的MAC協(xié)議來(lái)改善具有遠(yuǎn)距離鏈路的無(wú)人機(jī)網(wǎng)絡(luò)的通信問(wèn)題，本文主要側(cè)重于傳播延遲不可忽略的無(wú)線(xiàn)MAC協(xié)議設(shè)計(jì)與優(yōu)化。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

本文考慮的場(chǎng)景包括一個(gè)基站以及若干無(wú)人機(jī)組成的無(wú)線(xiàn)網(wǎng)絡(luò)。無(wú)人機(jī)隨機(jī)均勻分布，且都接入全球?qū)Ш叫l(wèi)星系統(tǒng)(GNSS)。GNSS可以提供時(shí)鐘同步以及地理位置信息服務(wù)。無(wú)人機(jī)搜集數(shù)據(jù)后傳輸給基站，基站負(fù)責(zé)接入調(diào)度。假設(shè)在某一時(shí)刻，無(wú)人機(jī)個(gè)數(shù)為M，mi表示編號(hào)為i的無(wú)人機(jī)?；竞蜔o(wú)人機(jī)的最大通信范圍都為Dmax，當(dāng)無(wú)人機(jī)和基站的距離小于Dmax時(shí)，無(wú)人機(jī)可以請(qǐng)求接入并進(jìn)行通信。另外，無(wú)人機(jī)和基站之間進(jìn)行視距通信，并且通信信道為理想信道，即不存在因?yàn)樾诺罓顩r而導(dǎo)致的丟包問(wèn)題。

1.2 數(shù)據(jù)流模型

本節(jié)介紹無(wú)人機(jī)數(shù)據(jù)流產(chǎn)生模型。上層應(yīng)用產(chǎn)生數(shù)據(jù)包后排隊(duì)進(jìn)入一個(gè)數(shù)據(jù)緩存區(qū)供數(shù)據(jù)鏈路層調(diào)度，假設(shè)緩存區(qū)容量為Cbuf，即緩存區(qū)最多可以保存Cbuf個(gè)數(shù)據(jù)包。當(dāng)緩存區(qū)滿(mǎn)時(shí)，再產(chǎn)生的數(shù)據(jù)包將被丟棄。

2 MAC協(xié)議

2.1 MAC協(xié)議框架

本文采用動(dòng)態(tài)時(shí)分復(fù)用的方法設(shè)計(jì)MAC協(xié)議。如圖1所示，時(shí)間被劃分為幀，每一幀包含若干時(shí)隙，我們定義一個(gè)時(shí)隙為最小的通信時(shí)間單位。假設(shè)在一個(gè)時(shí)隙內(nèi)，可以成功發(fā)送或者接收一個(gè)數(shù)據(jù)包。

每一幀包括兩部分：控制域和數(shù)據(jù)傳輸域。在控制域，無(wú)人機(jī)如果有數(shù)據(jù)要發(fā)送，則發(fā)送請(qǐng)求包，向基站申請(qǐng)時(shí)隙資源。在基站收到所有請(qǐng)求包后，發(fā)送一個(gè)廣播信息包，用于確認(rèn)以及指示數(shù)據(jù)區(qū)域的時(shí)隙分配情況。在數(shù)據(jù)傳輸域，無(wú)人機(jī)按照基站的分配信息在所在的時(shí)隙發(fā)送數(shù)據(jù)包。

圖1 MAC幀結(jié)構(gòu)Fig.1 Frame Structure

假設(shè)每一幀的長(zhǎng)度為L(zhǎng)f，每一幀包含N個(gè)時(shí)隙，那么每個(gè)時(shí)隙的長(zhǎng)度Ls就是Lf/N?？刂茀^(qū)域和數(shù)據(jù)區(qū)域的時(shí)隙數(shù)分別是Nc和Nd。當(dāng)mi有數(shù)據(jù)要發(fā)送時(shí)，向基站申請(qǐng)nreq,i個(gè)時(shí)隙，nreq,i是當(dāng)前數(shù)據(jù)緩存區(qū)中的數(shù)據(jù)包個(gè)數(shù)。

借助GNSS，mi可以獲取當(dāng)前的地理位置坐標(biāo)，那么其與基站之間的距離di也可以計(jì)算出來(lái)，相應(yīng)地，信號(hào)傳播延遲ti也可以根據(jù)距離di和無(wú)線(xiàn)電傳播速度c計(jì)算出來(lái)。

2.2 網(wǎng)絡(luò)初始化

基站在控制域周期性地廣播接入信息，當(dāng)一架無(wú)人機(jī)進(jìn)入基站的通信范圍并收到基站的接入信息時(shí)，向基站發(fā)送一個(gè)接入請(qǐng)求，包含認(rèn)證信息。一旦收到來(lái)自無(wú)人機(jī)的接入請(qǐng)求，基站會(huì)在下一個(gè)控制區(qū)域回復(fù)一個(gè)ACK包。無(wú)人機(jī)成功接受ACK包后，接入過(guò)程完成。接入過(guò)程至少需要N+Nc個(gè)時(shí)隙，而發(fā)送數(shù)據(jù)則至少在兩幀之后。

2.3 時(shí)間重用機(jī)制

遠(yuǎn)距離鏈路較大的傳播延遲使得時(shí)間重用成為可能，可使多個(gè)信號(hào)在同一競(jìng)爭(zhēng)域內(nèi)并發(fā)進(jìn)行傳輸。圖2描述了時(shí)間重用的基本思想。有兩個(gè)節(jié)點(diǎn)，nodei和nodej同時(shí)向基站BaseStation發(fā)送數(shù)據(jù)。由于兩節(jié)點(diǎn)與基站的距離不一樣，兩個(gè)同一時(shí)間點(diǎn)發(fā)送的數(shù)據(jù)包到達(dá)基站的時(shí)間也就不一樣，這樣基站可無(wú)沖突地接收到兩個(gè)數(shù)據(jù)包。而傳統(tǒng)MAC協(xié)議設(shè)計(jì)時(shí)通常假設(shè)是同一競(jìng)爭(zhēng)域內(nèi)只有一個(gè)數(shù)據(jù)包可以傳輸，這就意味著可以通過(guò)這種方式提高網(wǎng)絡(luò)吞吐量。

圖2 時(shí)間重用Fig.2 Temporal Reuse

3 時(shí)隙分配方法

無(wú)人機(jī)在傳輸數(shù)據(jù)之前會(huì)收到來(lái)自基站的分配信息包，分配信息包指定了特定的無(wú)人機(jī)在特定時(shí)隙傳輸數(shù)據(jù)。為了避免信號(hào)沖突以及最大化網(wǎng)絡(luò)吞吐量，有必要研究基站的時(shí)隙分配策略。

由于每一幀被劃分為若干時(shí)隙，并且每一個(gè)時(shí)隙只可以發(fā)送或接收一個(gè)數(shù)據(jù)包，我們定義一個(gè)M×N維的分配矩陣A，A指定了一幀內(nèi)的時(shí)隙如何分配給競(jìng)爭(zhēng)節(jié)點(diǎn)。如果mi在第j個(gè)時(shí)隙內(nèi)可以傳輸一個(gè)數(shù)據(jù)包，那么矩陣A中的元素ai,j等于1，否則ai,j等于0。

通過(guò)矩陣A和P，便可以計(jì)算出各個(gè)數(shù)據(jù)包到達(dá)基站的時(shí)間，同樣可以用一個(gè)M×N的0-1矩陣來(lái)表示，假設(shè)該矩陣為B。如果B中的元素bi,j等于1，則表示在第j個(gè)時(shí)隙收到了來(lái)自mi的數(shù)據(jù)包；反之bi,j等于0，則第j個(gè)時(shí)隙沒(méi)有收到來(lái)自mi的數(shù)據(jù)包。

3.1 無(wú)沖突

3.2 吞吐量

3.3 吞吐量最大化

本文的目標(biāo)是無(wú)信號(hào)沖突條件下最大化系統(tǒng)吞吐量，可以形式化如下：

(1)

式中，i∈{1,2,…,Mk}，k∈{1,2,…,K}，j∈{1,2,…,N}，τ是任意一幀的索引。

約束條件(2)限定在接收端一個(gè)時(shí)隙內(nèi)最多只有一個(gè)數(shù)據(jù)包到達(dá)，以此來(lái)滿(mǎn)足無(wú)沖突的要求。約束條件(3)限定分配給mi的時(shí)隙不超過(guò)它申請(qǐng)的時(shí)隙個(gè)數(shù)。約束條件(4)和(5)限制了ai,j,k的值，如果ai,j,k等于1，那么mi可以在第k幀的第j個(gè)時(shí)隙內(nèi)發(fā)送一個(gè)數(shù)據(jù)包，反之如果ai,j,k等于0則不能。其中(5)限定mi在一幀的最后pi個(gè)時(shí)隙不能發(fā)送數(shù)據(jù)，因?yàn)樵谶@段時(shí)間內(nèi)發(fā)送的數(shù)據(jù)包將在下一幀內(nèi)到達(dá)基站，可能會(huì)產(chǎn)生信號(hào)沖突。約束條件(6)和(7)表明了bi,j,k的取值范圍，可以從約束條件(4)和(5)中推導(dǎo)出來(lái)。

3.4 時(shí)隙分配算法

任意K個(gè)時(shí)間幀內(nèi)的吞吐量最大化問(wèn)題是一個(gè)典型的在線(xiàn)算法問(wèn)題，往往得不到最優(yōu)解，所以本節(jié)中將問(wèn)題簡(jiǎn)化為計(jì)算一幀內(nèi)可接收到的最大數(shù)據(jù)量，并提出相應(yīng)的時(shí)隙分配算法。

3.4.1 理論分析

首先把問(wèn)題重新形式化為如下形式：

(8)

式中，ai,j和bi,j是矩陣A和B中的元素，M是申請(qǐng)時(shí)隙的無(wú)人機(jī)個(gè)數(shù)，N是數(shù)據(jù)域內(nèi)的時(shí)隙數(shù)。

給定pi，根據(jù)(12)和(13)，假設(shè)ai,*=(ai,1,…,ai,N-pi,0,…,0)，bi,*=(0,…,0,bi,pi+1,…,bi,N)。由(14)，可以得到ai,*=(bi,pi+1,…,bi,N,0,…,0)以及bi,*=(0,…,0,ai,1,…,ai,N-pi)，那么目標(biāo)函數(shù)(8)可以轉(zhuǎn)換為

(15)

從式(15)中很容易地可以發(fā)現(xiàn)在無(wú)沖突情況下發(fā)送的數(shù)據(jù)包數(shù)量等于接收到的數(shù)據(jù)包數(shù)量。那么可以把問(wèn)題轉(zhuǎn)化為：

(16)

(21)

3.4.2 時(shí)隙分配算法

當(dāng)Bj=1,i>Mp時(shí)，吞吐量達(dá)到最大，也就是在第(Mp+1)到第N個(gè)時(shí)隙基站都能接收到數(shù)據(jù)包。由此提出一個(gè)時(shí)隙分配算法實(shí)現(xiàn)時(shí)隙分配，同時(shí)該算法能保證分配的公平性。

算法1 時(shí)隙分配算法輸入:信號(hào)傳播延遲矩陣P輸出:時(shí)隙分配矩陣A1:對(duì)P進(jìn)行排序,得到非遞減矩陣P'=(p'1,p'2,…,p'M)2:計(jì)算可用的時(shí)隙個(gè)數(shù),nSlotNum=N-p'13:設(shè)置一個(gè)數(shù)組ArraySlotNum,保存分配給每個(gè)節(jié)點(diǎn)的時(shí)隙數(shù)4:while nSlotNum>0 do //把可用時(shí)隙分配給競(jìng)爭(zhēng)節(jié)點(diǎn)5:for i=1;i0 then7:ArraySlotNum[i]++;8:nSlotNum--;9:else10:nSlotNum--;11:endif12:endfor13:endwhile14:得到最小傳播延遲Mp=p'115:for i=1;i

算法1中所有的操作都可以在多項(xiàng)式時(shí)間內(nèi)完成，其中步驟4-13以及步驟15-20的循環(huán)操作的時(shí)間復(fù)雜度都是O(M×N)，那么該算法的時(shí)間復(fù)雜度也就是O(M×N)，M是競(jìng)爭(zhēng)節(jié)點(diǎn)的個(gè)數(shù)，N是待分配的時(shí)隙個(gè)數(shù)。

3.4.3 吞吐量理論分析

分析網(wǎng)絡(luò)在不同狀態(tài)下的吞吐量，分網(wǎng)絡(luò)飽和和網(wǎng)絡(luò)不飽和兩種情況。

網(wǎng)絡(luò)飽和情況：飽和情況下，除由于信號(hào)傳播延遲導(dǎo)致的時(shí)隙浪費(fèi)，其他時(shí)隙都能接收到數(shù)據(jù)包，那么在K個(gè)幀內(nèi)的吞吐量可以表示為：

(22)

由式(22)，可以得到

(23)

以及

(24)

式(23)和式(24)分別給出了網(wǎng)絡(luò)飽和情況下吞吐量的上下界。

網(wǎng)絡(luò)不飽和情況：網(wǎng)絡(luò)不飽和情況下無(wú)人機(jī)可以傳輸所有的數(shù)據(jù)包，接收端還有時(shí)隙空閑，部分時(shí)隙沒(méi)有數(shù)據(jù)包到達(dá)。這種情況下，根據(jù)數(shù)據(jù)流模型來(lái)計(jì)算吞吐量Thusa。

(28)

4 實(shí)驗(yàn)仿真

4.1 仿真環(huán)境

本文使用OMNeT++5.0對(duì)提出的MAC協(xié)議進(jìn)行了仿真。協(xié)議主要實(shí)現(xiàn)了數(shù)據(jù)鏈路層和應(yīng)用層的功能，應(yīng)用層產(chǎn)生數(shù)據(jù)包，而數(shù)據(jù)鏈路層實(shí)現(xiàn)對(duì)數(shù)據(jù)包進(jìn)行調(diào)度。關(guān)于數(shù)據(jù)流模型，假設(shè)數(shù)據(jù)緩存區(qū)容量Cbuf為20 000，并且對(duì)于任意i∈{1,2,…,M}，有λi=λ，μi=μ以及σi2=σ2。每個(gè)數(shù)據(jù)包的長(zhǎng)度為4 096 bits，發(fā)送速率和接收速率均為100 Mbps。如果mi和基站的距離超過(guò)Dmax，兩者失去連接，mi會(huì)清空緩存區(qū)，并且不能發(fā)送數(shù)據(jù)包。通過(guò)這種方法實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化

本文的方法與兩種不同類(lèi)型的MAC協(xié)議進(jìn)行了對(duì)比，分別是基于競(jìng)爭(zhēng)的IRSA(Irregular Repetition Slotted Aloha)以及動(dòng)態(tài)時(shí)分多址接入D-TDMA(Dynamic Time Division Multiple Access)。IRSA利用干擾消除技術(shù)實(shí)現(xiàn)接收端的多包接收，相比傳統(tǒng)的Aloha協(xié)議，可以成倍地提高吞吐量。D-TDMA由基站把時(shí)隙資源按需分配給競(jìng)爭(zhēng)節(jié)點(diǎn)。主要比較了以下性能參數(shù)：1)吞吐量，單位時(shí)間內(nèi)接收端接收到的數(shù)據(jù)包數(shù)量。吞吐量反映了信道的利用率。2)調(diào)度時(shí)間，每個(gè)包從進(jìn)入數(shù)據(jù)緩存區(qū)到被調(diào)度離開(kāi)節(jié)點(diǎn)的時(shí)間間隔，調(diào)度時(shí)間是體現(xiàn)服務(wù)質(zhì)量的一個(gè)重要方面。

所有的仿真參數(shù)如表1所示。

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

4.2 仿真結(jié)果

1)吞吐量

首先研究利用時(shí)空復(fù)用方法進(jìn)行多數(shù)據(jù)包并發(fā)傳輸對(duì)吞吐量的影響。圖3為吞吐量和節(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系。當(dāng)節(jié)點(diǎn)個(gè)數(shù)增加時(shí)，吞吐量也隨之增加，而當(dāng)節(jié)點(diǎn)個(gè)數(shù)到達(dá)70后，吞吐量趨于穩(wěn)定，表明網(wǎng)絡(luò)達(dá)到飽和。當(dāng)節(jié)點(diǎn)個(gè)數(shù)不多時(shí)，本文的協(xié)議和其他兩個(gè)協(xié)議性能相當(dāng)，而當(dāng)節(jié)點(diǎn)個(gè)數(shù)增加，系統(tǒng)達(dá)到飽和時(shí)，D-TDMA的吞吐量呈明顯下降趨勢(shì)，這是由于隨著節(jié)點(diǎn)的增多，D-TDMA協(xié)議導(dǎo)致每個(gè)節(jié)點(diǎn)浪費(fèi)的時(shí)隙也變多。而IRSA由于節(jié)點(diǎn)增多后，信號(hào)沖突加劇，吞吐量也急劇下降。

另外，我們改變數(shù)據(jù)流模型中的參數(shù)，改變數(shù)據(jù)包生成速率，觀(guān)察對(duì)吞吐量的影響，結(jié)果如圖4所示。可以發(fā)現(xiàn)，在網(wǎng)絡(luò)飽和情況下，本文的協(xié)議和D-TDMA都能達(dá)到穩(wěn)定的吞吐量，但本文提出的協(xié)議要比其他兩種協(xié)議都具有更好的性能；而當(dāng)網(wǎng)絡(luò)不飽和情況下，本文提出的協(xié)議與其他兩個(gè)協(xié)議的性能幾乎一樣。

從圖3和圖4我們可以發(fā)現(xiàn)網(wǎng)絡(luò)飽和情況下，本文提出的MAC協(xié)議比其他協(xié)議都有更大的吞吐量，說(shuō)明對(duì)于基站來(lái)說(shuō)，可以接收到更多的數(shù)據(jù)包。而對(duì)于節(jié)點(diǎn)來(lái)說(shuō)，網(wǎng)絡(luò)達(dá)到飽和意味著丟包，用戶(hù)體驗(yàn)的下降，我們通過(guò)觀(guān)察調(diào)度時(shí)間來(lái)進(jìn)行評(píng)價(jià)。

2)調(diào)度時(shí)間

圖3 吞吐量與節(jié)點(diǎn)個(gè)數(shù)的關(guān)系Fig.3 Throughput V.S. Number of host number

圖4 吞吐量與數(shù)據(jù)包生成間隔的關(guān)系Fig.4 Throughput V.S. Interval

圖5 調(diào)度時(shí)間與節(jié)點(diǎn)個(gè)數(shù)的關(guān)系Fig.5 Scheduling time V.S. Number of host number

圖6 調(diào)度時(shí)間與數(shù)據(jù)包生成間隔的關(guān)系Fig.6 Scheduling time V.S. Interval

5 結(jié)論

本文提出了面向無(wú)人機(jī)網(wǎng)絡(luò)的MAC協(xié)議。該協(xié)議基于時(shí)間重用思想，利用較大的傳播延遲使并發(fā)傳輸成為可能，通過(guò)這種方法提高了信道利用率和網(wǎng)絡(luò)吞吐量。進(jìn)一步提出了一種無(wú)沖突的時(shí)隙分配算法。仿真及實(shí)驗(yàn)結(jié)果表明，該協(xié)議的系統(tǒng)吞吐量?jī)?yōu)于動(dòng)態(tài)TDMA和IRSA，特別是網(wǎng)絡(luò)趨于飽和的情況下，符合理論分析結(jié)果，而調(diào)度時(shí)間優(yōu)于動(dòng)態(tài)TDMA，劣于IRSA。