面向無人機網絡的媒體接入控制協議

楊茂保，徐利亞，葛明珠，陳 希，舒長興

(1.九江學院電子商務學院，江西 九江 332005；2.九江學院信息科學與技術學院，江西 九江 332005；3.九江學院信息技術中心，江西 九江 332005；4.軟件工程國家重點實驗室，武漢大學計算機學院，湖北 武漢 430072)

0 引言

無人機是一種可以自主飛行不需人為操作的飛行器，在軍用和民用領域有廣泛用途，如森林火災監測[1]，災害救援[2]，無線網絡中繼[3]， 增加網絡容量[4]等。盡管單無人機系統已經使用了很多年，但是多無人機系統與單無人機系統相比有很多優勢。而多無人機系統面臨的一個重要挑戰就是它們之間的通信[5-7]，包括無人機之間的通信，以及無人機與基站之間的通信。在某些場景中，通信鏈路可能長達幾百公里，這樣的遠距離通信鏈路可能會導致：1)低服務質量，信號質量和通信距離成反比，遠距離鏈路將導致更高的丟包率。2)信道利用率低，遠距離引起較大的信號傳播延遲，對于高速網絡來說這種延遲不能被忽略。傳統網絡協議設計時，單信道通常只允許單個信號進行傳輸，這種方式在傳播延遲較大時將引起很大的浪費。

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

針對上述問題，需要一個更合適的MAC協議來改善具有遠距離鏈路的無人機網絡的通信問題，本文主要側重于傳播延遲不可忽略的無線MAC協議設計與優化。

1 系統模型

1.1 網絡模型

本文考慮的場景包括一個基站以及若干無人機組成的無線網絡。無人機隨機均勻分布，且都接入全球導航衛星系統(GNSS)。GNSS可以提供時鐘同步以及地理位置信息服務。無人機搜集數據后傳輸給基站，基站負責接入調度。假設在某一時刻，無人機個數為M，mi表示編號為i的無人機?；竞蜔o人機的最大通信范圍都為Dmax，當無人機和基站的距離小于Dmax時，無人機可以請求接入并進行通信。另外，無人機和基站之間進行視距通信，并且通信信道為理想信道，即不存在因為信道狀況而導致的丟包問題。

1.2 數據流模型

本節介紹無人機數據流產生模型。上層應用產生數據包后排隊進入一個數據緩存區供數據鏈路層調度，假設緩存區容量為Cbuf，即緩存區最多可以保存Cbuf個數據包。當緩存區滿時，再產生的數據包將被丟棄。

2 MAC協議

2.1 MAC協議框架

本文采用動態時分復用的方法設計MAC協議。如圖1所示，時間被劃分為幀，每一幀包含若干時隙，我們定義一個時隙為最小的通信時間單位。假設在一個時隙內，可以成功發送或者接收一個數據包。

每一幀包括兩部分：控制域和數據傳輸域。在控制域，無人機如果有數據要發送，則發送請求包，向基站申請時隙資源。在基站收到所有請求包后，發送一個廣播信息包，用于確認以及指示數據區域的時隙分配情況。在數據傳輸域，無人機按照基站的分配信息在所在的時隙發送數據包。

圖1 MAC幀結構Fig.1 Frame Structure

假設每一幀的長度為Lf，每一幀包含N個時隙，那么每個時隙的長度Ls就是Lf/N?？刂茀^域和數據區域的時隙數分別是Nc和Nd。當mi有數據要發送時，向基站申請nreq,i個時隙，nreq,i是當前數據緩存區中的數據包個數。

借助GNSS，mi可以獲取當前的地理位置坐標，那么其與基站之間的距離di也可以計算出來，相應地，信號傳播延遲ti也可以根據距離di和無線電傳播速度c計算出來。

2.2 網絡初始化

基站在控制域周期性地廣播接入信息，當一架無人機進入基站的通信范圍并收到基站的接入信息時，向基站發送一個接入請求，包含認證信息。一旦收到來自無人機的接入請求，基站會在下一個控制區域回復一個ACK包。無人機成功接受ACK包后，接入過程完成。接入過程至少需要N+Nc個時隙，而發送數據則至少在兩幀之后。

2.3 時間重用機制

遠距離鏈路較大的傳播延遲使得時間重用成為可能，可使多個信號在同一競爭域內并發進行傳輸。圖2描述了時間重用的基本思想。有兩個節點，nodei和nodej同時向基站BaseStation發送數據。由于兩節點與基站的距離不一樣，兩個同一時間點發送的數據包到達基站的時間也就不一樣，這樣基站可無沖突地接收到兩個數據包。而傳統MAC協議設計時通常假設是同一競爭域內只有一個數據包可以傳輸，這就意味著可以通過這種方式提高網絡吞吐量。

圖2 時間重用Fig.2 Temporal Reuse

3 時隙分配方法

無人機在傳輸數據之前會收到來自基站的分配信息包，分配信息包指定了特定的無人機在特定時隙傳輸數據。為了避免信號沖突以及最大化網絡吞吐量，有必要研究基站的時隙分配策略。

由于每一幀被劃分為若干時隙，并且每一個時隙只可以發送或接收一個數據包，我們定義一個M×N維的分配矩陣A，A指定了一幀內的時隙如何分配給競爭節點。如果mi在第j個時隙內可以傳輸一個數據包，那么矩陣A中的元素ai,j等于1，否則ai,j等于0。

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

3.1 無沖突

3.2 吞吐量

3.3 吞吐量最大化

本文的目標是無信號沖突條件下最大化系統吞吐量，可以形式化如下：

(1)

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

約束條件(2)限定在接收端一個時隙內最多只有一個數據包到達，以此來滿足無沖突的要求。約束條件(3)限定分配給mi的時隙不超過它申請的時隙個數。約束條件(4)和(5)限制了ai,j,k的值，如果ai,j,k等于1，那么mi可以在第k幀的第j個時隙內發送一個數據包，反之如果ai,j,k等于0則不能。其中(5)限定mi在一幀的最后pi個時隙不能發送數據，因為在這段時間內發送的數據包將在下一幀內到達基站，可能會產生信號沖突。約束條件(6)和(7)表明了bi,j,k的取值范圍，可以從約束條件(4)和(5)中推導出來。

3.4 時隙分配算法

任意K個時間幀內的吞吐量最大化問題是一個典型的在線算法問題，往往得不到最優解，所以本節中將問題簡化為計算一幀內可接收到的最大數據量，并提出相應的時隙分配算法。

3.4.1 理論分析

首先把問題重新形式化為如下形式：

(8)

式中，ai,j和bi,j是矩陣A和B中的元素，M是申請時隙的無人機個數，N是數據域內的時隙數。

給定pi，根據(12)和(13)，假設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)，那么目標函數(8)可以轉換為

(15)

從式(15)中很容易地可以發現在無沖突情況下發送的數據包數量等于接收到的數據包數量。那么可以把問題轉化為：

(16)

(21)

3.4.2 時隙分配算法

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

算法1 時隙分配算法輸入:信號傳播延遲矩陣P輸出:時隙分配矩陣A1:對P進行排序,得到非遞減矩陣P'=(p'1,p'2,…,p'M)2:計算可用的時隙個數,nSlotNum=N-p'13:設置一個數組ArraySlotNum,保存分配給每個節點的時隙數4:while nSlotNum>0 do //把可用時隙分配給競爭節點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中所有的操作都可以在多項式時間內完成，其中步驟4-13以及步驟15-20的循環操作的時間復雜度都是O(M×N)，那么該算法的時間復雜度也就是O(M×N)，M是競爭節點的個數，N是待分配的時隙個數。

3.4.3 吞吐量理論分析

分析網絡在不同狀態下的吞吐量，分網絡飽和和網絡不飽和兩種情況。

網絡飽和情況：飽和情況下，除由于信號傳播延遲導致的時隙浪費，其他時隙都能接收到數據包，那么在K個幀內的吞吐量可以表示為：

(22)

由式(22)，可以得到

(23)

以及

(24)

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

網絡不飽和情況：網絡不飽和情況下無人機可以傳輸所有的數據包，接收端還有時隙空閑，部分時隙沒有數據包到達。這種情況下，根據數據流模型來計算吞吐量Thusa。

(28)

4 實驗仿真

4.1 仿真環境

本文使用OMNeT++5.0對提出的MAC協議進行了仿真。協議主要實現了數據鏈路層和應用層的功能，應用層產生數據包，而數據鏈路層實現對數據包進行調度。關于數據流模型，假設數據緩存區容量Cbuf為20 000，并且對于任意i∈{1,2,…,M}，有λi=λ，μi=μ以及σi2=σ2。每個數據包的長度為4 096 bits，發送速率和接收速率均為100 Mbps。如果mi和基站的距離超過Dmax，兩者失去連接，mi會清空緩存區，并且不能發送數據包。通過這種方法實現網絡拓撲的動態變化

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

所有的仿真參數如表1所示。

表1 仿真參數Tab.1 Simulation Parameters

4.2 仿真結果

1)吞吐量

首先研究利用時空復用方法進行多數據包并發傳輸對吞吐量的影響。圖3為吞吐量和節點個數之間的關系。當節點個數增加時，吞吐量也隨之增加，而當節點個數到達70后，吞吐量趨于穩定，表明網絡達到飽和。當節點個數不多時，本文的協議和其他兩個協議性能相當，而當節點個數增加，系統達到飽和時，D-TDMA的吞吐量呈明顯下降趨勢，這是由于隨著節點的增多，D-TDMA協議導致每個節點浪費的時隙也變多。而IRSA由于節點增多后，信號沖突加劇，吞吐量也急劇下降。

另外，我們改變數據流模型中的參數，改變數據包生成速率，觀察對吞吐量的影響，結果如圖4所示?？梢园l現，在網絡飽和情況下，本文的協議和D-TDMA都能達到穩定的吞吐量，但本文提出的協議要比其他兩種協議都具有更好的性能；而當網絡不飽和情況下，本文提出的協議與其他兩個協議的性能幾乎一樣。

從圖3和圖4我們可以發現網絡飽和情況下，本文提出的MAC協議比其他協議都有更大的吞吐量，說明對于基站來說，可以接收到更多的數據包。而對于節點來說，網絡達到飽和意味著丟包，用戶體驗的下降，我們通過觀察調度時間來進行評價。

2)調度時間

圖3 吞吐量與節點個數的關系Fig.3 Throughput V.S. Number of host number

圖4 吞吐量與數據包生成間隔的關系Fig.4 Throughput V.S. Interval

圖5 調度時間與節點個數的關系Fig.5 Scheduling time V.S. Number of host number

圖6 調度時間與數據包生成間隔的關系Fig.6 Scheduling time V.S. Interval

5 結論

本文提出了面向無人機網絡的MAC協議。該協議基于時間重用思想，利用較大的傳播延遲使并發傳輸成為可能，通過這種方法提高了信道利用率和網絡吞吐量。進一步提出了一種無沖突的時隙分配算法。仿真及實驗結果表明，該協議的系統吞吐量優于動態TDMA和IRSA，特別是網絡趨于飽和的情況下，符合理論分析結果，而調度時間優于動態TDMA，劣于IRSA。