基于TDMA的空中自組網MAC層資源調度算法研究

張子東，宋志群，劉玉濤，段嘯寒，于子婷

(中國電子科技集團公司 第54研究所，石家莊 050081)

0 引言

空中移動無線自組織網絡是一個新的研究領域，其基本思路是在空中的節點通過多跳的方式，遠距離傳輸控制信息及數據信息從而達到遠距離通信的目的[1]。在一定范圍內的航空飛行器之間相互轉發控制指令信息，交換各自的飛行狀態、感知信息等數據，并自動連接，以建立一個移動自組網(MANET[2]，mobile ad hoc network)。空中組網具有組網靈活擴展且無需網絡基礎設施等優勢，在航空通信中有著廣闊的發展前景。其具備的自組織、自恢復、高動態、低時延等特點可以滿足高空無線通信的特定需求，是高空通信的重要發展方向，也是現代無線通信的重要組成部分[3]。

近些年針對空中自組網的媒體接入控制(MAC，media access control)協議研究較少，其中文獻[4]是無中心節點的分布式時分多址(TDMA，time division multiple access)協議，各個節點使用分配的時隙進行數據傳輸。文獻[5]的無沖突MAC協議(CF-MAC，collision free media access control)通過載波監聽控制時隙的分配。文獻[6]通過規定不同節點有不同優先級占用時隙，但是沒有考慮不同時隙的不同業務需求。文獻[7]提出的自組織時分多址接入協議(ESTDMA，evolutionary self-organized time division multiple access)可以通過對閑置時隙的二次預約合理的分配時隙。但是二次分配也會導致傳輸失敗增多使網絡時延難以控制。文獻[8]設計的并發傳輸MAC協議(CTMAC，concurrent transmission media access control)通過載波監聽與隨機退避機制。雖然可以提高TDMA協議的信道利用率，但是隨之而來的便是吞吐量的降低以及時延的增大。優先級競爭時分多址(P-TDMA，priority-based time division multiple access)協議[9]本質上是動態時隙分配算法，但是卻融合了靜態時隙分配的特點，構造了一種特殊的幀結構，避免了多節點的沖突碰撞問題。P-TDMA 協議的缺點是沒有到考慮不同節點業務量不同。且混合分配模式在不同業務量下網絡性能不穩定。

TDMA[10]協議的基本思想是將時間分割為幀的形式，每一幀將不同的信息儲存在不同的時隙之中，每個用戶通過算法被分配不同的時隙[11]。在不同時隙發送數據就表示發送的時間是何時，即數據傳輸的等待時延。傳輸時延主要受時隙分配結果、無線傳輸時延、處理時延以及總幀長大小等因素的影響[12]。目前常見的TDMA時隙分配方法主要包含兩種：靜態分配法與動態分配法。靜態分配法是給每個節點分配一定數量的時隙來保證數據發送與接收的及時性，擁有穩定的時延；動態分配法則是根據不同節點的需求不同，動態調整時隙的分配數量，提高時隙的利用率，以此來適應更大規模的網絡。本文采用的混合分配法綜合了靜態分配與動態分配兩種分配方式的優點具有更高的網絡效率。

針對高空高動態遠距離通信的場景，現有多跳TDMA協議存在的時延過大、吞吐量不足等問題。本文結合定向天線的通信特點，參考P-TDMA協議算法設計了一種基于TDMA的定向分布式資源調度算法(M-TDMA，mix time division multiple access)。本文設計的M-TDMA算法有如下改進創新：1)設計了一種基于拓撲的鄰居節點分配算法，根據動態變化的節點拓撲信息，尋找各個節點的鄰居節點，按照點號依次為每個在網節點分配時隙。由于定向自組網是根據時隙對來通信，在網節點固定分并不適用，因此采用鄰居節點固定分策略。并通過靜態分配與動態分配相結合的混合模式，提升了網絡吞吐量；2)靜態分配策略：為各個節點設置時延保障靜態時隙以應對突發的業務需求，引入分配系數，分配系數隨節點空閑時隙的數量變化進行動態調整，以此來均衡靜態與動態分配的的時隙數量有效降低了傳輸時延；3)動態分配策略：在業務優先級的基礎上設計節點流量預測算法，MAC層識別業務信息量不同，首先根據流量預測算法，通過歷史周期的鄰居節點業務量大小，預測本周期業務量大小，從而給不同業務需求的節點分配不同數量的時隙。隨后動態分配時隙數量，當預測到節點有大量業務需求時，優先將空閑時隙分給預測業務量大的節點傳輸業務，剩余時隙分配給其它低業務量節點。節點分配的時隙數量隨著調度周期進行動態變化，最后根據業務優先級算法，為各優先級的業務分配不同數量的時隙。

1 自組網MAC協議

1.1 MAC協議原理

MAC層協議作為無線通信的基礎，在無線網絡通信中起著至關重要的作用，通過分配各個節點無線信道資源，在提升傳輸效率的基礎上保障公平性。對傳輸時延、網絡吞吐量等網絡性能指標起著關鍵性作用[13]。隨著現代無線自組織網絡規模越來越大，服務質量 (QoS，quality of service)指標的保證顯得愈發關鍵，如何更好地進行資源調度是MAC協議研究的熱點之一[14-22]。

通常MAC協議多采用集中式的調度方式，通過交互整個網絡拓撲的節點信息，根據節點優先級不同分配不同的時隙，并使用中心節點廣播分配時隙。但由于高空環境下通信距離遠，網絡拓撲動態變化快，又有高帶寬的傳輸需求，需要采用定向天線。而定向天線同一時刻需要點對點收發波束朝向一致才可以通信，集中式協議不適用。因此只能使用無中心節點的分布式時隙分配方法[23]。這種方法不需要中心節點的參與，只通過部分節點的信息交互就可以完成網絡時隙的合理分配。

1.2 幀結構設計

本文M-TDMA算法有3種幀類型，分別為鄰居發現幀、預約幀和數據幀。分別對應鄰居發現、預約、數據傳輸3個階段。鄰居發現幀用于實現節點之間的波束對準及網絡同步，預約幀用于實現節點間的分布式業務預約，數據幀用于業務傳輸。算法的時隙結構如圖1所示。其中SYN為鄰居發現幀，DATA為數據幀，R1、R2為預約幀。每個調度周期有4個鄰居發現幀可以進行4次鄰居發現。一個周期內各種幀的幀長與數量如表1所示。一個調度周期總共1 s。調度周期包含的各幀信息如下：

圖1 M-TDMA算法時隙結構

表1 幀長設計

1)鄰居發現幀的長度。4個鄰居發現幀幀長為10 ms。

2)預約幀的長度。R1與R2長度相同，本文設計為1.5 ms。

3)數據幀的長度。由于數據時隙數量較多，每個數據幀長度不能超過10 ms否則將會無空余時隙設置預約幀，本文數據幀長為5 ms。

預約幀結構如圖2所示，當節點入網后，MAC層有數據需要傳輸，此時節點通過預約幀發送請求信息，其攜帶的信息有數據大小、優先級節點ID、鄰居節點信息等。接收節點收到其他節點發送的預約幀后，將預約幀內容匯總儲存并在預約確認幀中發出反饋。預約確認幀結構與預約幀相同，二者使得全網鄰居信息互通。本文每個預約幀長度均為1.5 ms，由預約時隙R1、預約確認時隙R2和保護間隔組成。R1時隙和R2時隙長度相同。每個預約幀中的發送節點對互相綁定，兩個節點互為目的節點。保護間隔長度約占預約幀總長度的10%，用以確保節點收到R1后能夠有充足時間解調并計算時隙資源，最終將結果附在R2中發出。

圖2 預約幀結構

數據階段，節點間按照上個預約階段的預約結果進行數據傳輸。在一個數據時隙進行信息交互的兩個節點分別為發送數據節點和接收數據節點，二者已經在之前的預約階段互相確定。在數據傳輸過程通信雙方的收發天線按照鄰居發現的結果相互對準。為保證協議層數據的正確接收，數據幀應預留一定的長度間隔作為保護間隔，用于補償遠距離數據的傳輸時延。剩余的時隙根據物理層幀結構進行靈活改動，設計為一個或多個時隙，并根據需求發送至一個或多個目的節點。

2 資源調度算法

2.1 MAC協議資源調度算法

資源調度算法包括時隙預約、業務量統計、時隙排布三部分，業務量統計用于確定本次調度分配的時隙數量，隨后根據業務量統計的結果進行預約，預約過程使用時隙排布策略以確保時隙的均勻分配。

資源調度算法流程為：首先進行節點初始化，隨后的時隙請求階段，節點根據緩存的時隙需求，在對應時隙發送請求并接受其他節點的請求信息。在響應階段，節點依據之前階段的節點信息，與自身時隙狀態整合匯總，通過本文的資源調度算法分配時隙。最后進入數據發送階段，各個節點根據資源調度算法分配的時隙發送數據。本文具體算法基本流程如圖3所示。

圖3 MAC協議算法流程

2.2 業務量統計策略

圖4 流量預測示意圖

(1)

(2)

節點根據鄰居節點的預測流量大小，對可分配時隙按比例進行劃分，歷史業務量大的節點會分配更多的時隙，業務量小的節點會分配相對較少的時隙。此時由于分配比例系數與分配時隙總數無法整除可能會產生一定的時隙余量，將剩余時隙統一分配給預測業務量最大的節點。由于網絡拓撲的動態變化，當有新節點入網時，會分配一定比例的時隙。由于節點時隙分配比例是周期變化的，對于每個節點來說，時隙的分配是公平的。最后給不同優先級的業務劃分不同的時隙數目xi，業務優先級越高分配時隙越多業務發送越快信道等待時延越低。業務量統計策略流程如圖5所示。

圖5 業務量統計流程

2.3 時隙預約策略

兩個節點之間的時隙分配通過預約時隙對，即預約時隙R1和預約時隙R2實現，如下為數據時隙分配過程，節點A和節點B互為鄰居業務傳輸節點。節點A為R1發送節點，節點B為R2發送節點。

2.3.1 節點A時隙預約步驟

步驟1：節點A在進入自己的預約時隙后發送預約幀R1。節點A查看自己的緩存中是否有數據等待發送至節點B，如果需要預約數據時隙，則計算需要的時隙數，在預約幀R1中填充需要的時隙和本節點在數據階段的空閑時隙表。發送預約幀R1后，轉至步驟2。

步驟2：節點A持續收聽信道，如果能夠正確接收預約確認幀R2，則說明在預約時隙節點A與節點B成功的進行了信息交互。節點A讀取預約確認幀R2中節點B回復的成功分配的時隙和數據時隙編號，在下一個數據階段，節點A將在數據時隙向節點B發送數據。同時節點A查看節點B是否有時隙需求。如果節點B有數據時隙需求，則讀取節點B的數據時隙需求和數據時隙號。在下一個數據階段，節點B將在這些數據時隙向節點A發送數據，在這些時隙節點A將切換為對節點B的接收狀態。

2.3.2 節點B時隙預約步驟

步驟1：在進入預約時隙后持續收聽信道。若接收到節點A發送的R1，則查看節點A是否申請分配數據時隙，若申請數據時隙，則查看需求的時隙數量，節點B根據自己的空閑時隙情況，安排盡可能符合需求的時隙。若節點A發送的R1幀中沒有申請分配數據時隙，則節點B根據自己緩存中待發數據的情況判斷是否需要申請數據時隙以及計算需要申請的數據時隙的數目，然后讀取預約幀R1中節點A的空閑時隙情況，同時根據自身的空閑時隙情況安排盡可能符合需求的時隙。

步驟2：進入步驟2，節點B發送預約幀R2，告知節點A成功分配的數據時隙數目和數據時隙編號。時隙預約示意圖如圖6所示。

圖6 時隙預約示意圖

2.4 時隙排布策略

當確定要分配的時隙數后，將確定分配的時隙排布到互相預約的兩個節點的空閑時隙交集中。時隙排布需要考慮的因素是時延抖動。抖動越大，說明通信網絡越不穩定。為了降低時延抖動，需實現均勻間隔的時隙分配。本文采用貪心算法(又稱貪婪算法)：在對問題求解時，總是做出在當前看來的最好選擇。即不從整體最優上加以考慮，所做出的僅是某種意義上的局部最優解。貪心算法不是對所有問題都能得到最優解，但針對許多問題，能產生整體最優解或者是整體最優解的近似解。分配時隙時采用貪心策略，只需考慮下個時隙與上個已分時隙的時隙間隔，而無需考慮整個時隙表的排布。

為保證傳輸時延，為每個節點分配的時隙與下個時隙的間隔不能過長。為減小時延抖動，相鄰兩個時隙的間隔數相對固定。由于時隙表的開始部分存在鄰居發現幀，鄰居發現幀會帶來時延，剩余部分只存在預約幀，而預約幀有釋放的可能，所以兩種情況應分別考慮。算法時隙排布流程如圖7(a)所示，其中LAST_NUM為上一次分配的時隙號。S為第一個空閑時隙號T為時隙分配步進即每間隔T個時隙分一個時隙，N為所需分配時隙數。例如T=7時，隔7個數據時隙排布一個時隙。MAXNUM為時隙表數據時隙總數，若業務需求時隙數較少，則使時隙平均分配在總時隙表中。例如只需4個時隙時，時隙分配步進為：

圖7 時隙排布策略流程及結果

(MAXNUM/4)-1

(3)

按照上述策略，節點分配時隙的結果如圖7(b)所示，其中灰色時隙為依據時隙排布策略所分配的時隙。

3 仿真與分析

3.1 仿真原理及參數

使用軟件Visual Studio進行仿真代碼實現，使用Matlab對仿真數據進行處理與分析。通過對算法的時延、吞吐量等性能指標進行優化并與STDMA、P-TDMA等典型協議進行性能對比，由此對M-TDMA算法性能進行驗證。主要仿真參數如表2所示。

表2 仿真參數設置

兩跳傳輸時延仿真首先輸入業務的發送節點和接收節點。根據時隙分配算法，計算出各節點的時隙表。通過產生一個隨機數作為起始時隙，從起始時隙的下一個時隙開始搜尋時隙表，如果時隙表中該時隙的發送節點和業務發送節點相同，該時隙的接收節點與業務接收節點相同，則說明數據會在該時隙發出。如果該時隙不是數據發送時隙，則繼續尋找。從起始時隙向后尋找發送時隙的過程即傳輸時延增加的過程，每過一個時隙，則傳輸時延增加一個時隙的時長。找到發送時隙后，則返回總時長即為傳輸時延。

多跳傳輸時延的計算為兩跳傳輸時延的多次調用。多跳傳輸時延的輸入為業務路徑。產生隨機數作為起始時隙，首先計算第1跳的傳輸時延，得出結果后，將第1跳傳輸時延的發時隙作為第2跳傳輸時延計算的起始時隙，繼續進行第2跳傳輸時延的計算。整條業務路徑的傳輸時延依次疊加，得出總的傳輸時延。

在數據傳輸過程中由于在空中組網節點的網絡拓撲結構變化較快，為保證QoS，通常MAC層仿真的多跳時延通常不能大于1 s，否則將會導致接收端丟包。仿真在統計接收數據包數量占總發送數據包的百分比即為丟包率。每一幀的最大數據載荷是固定的，節點之間有效數據的傳輸是通過數據時隙完成，通過計算在鏈路數據傳輸中使用的數據時隙總數即可計算出仿真數據傳輸過程的吞吐量大小。

3.2 仿真結果與分析

為了評估M-TDMA算法的性能，分別從分配系數、網絡節點個數、數據發送速率等方面進行仿真分析。其中分配系數是對M-TDMA算法進行優化；不同網絡節點個數與發送速率是用于對比M-TDMA與STDMA和P-TDMA三種算法的性能差異。通過網絡平均傳輸時延、網絡吞吐量、網絡丟包率等性能指標對算法進行優化與分析。為了更好地驗證M-TDMA 算法性能，本文進行100次調度周期仿真并取平均值進行結果分析。

3.2.1 不同拓撲場景與分配系數優化

在節點高動態場景下，網絡的拓撲形式多樣化，圖8為3種典型的網絡拓撲狀態，通過分別對比在3種不同拓撲下一跳至十跳的時延大小來驗證M-TDMA算法的網絡拓撲環境適用性。

圖8 3種不同網絡拓撲圖

根據圖9(a)結果可知：鏈狀拓撲由于結構簡單且鄰居節點數相對固定，因此時延最小，且當跳數增大時，時延上升最平穩；而網狀與星狀拓撲由于不同節點的鄰居節點數差異較大，因此時延的變化較為抖動，但是單跳的平均時延仍在60 ms以內，符合單跳傳輸指標。綜上所述本文的M-TDMA算法在不同的拓撲狀態下網絡傳輸性能良好。

圖9 不同分配系數下網絡時延對比圖

分配系數RATTO的作用是：當節點的可用空閑時隙較少時，通過RATTO使節點分配的靜態時隙減少、動態時隙增多，使得傳輸時延相對穩定。分配系數的優化是通過在星狀網絡拓撲下遍歷分配系數，對比不同分配系數4跳傳輸路徑的時延大小。RATTO越小代表在節點可用時隙較少時分配的靜態時隙越少，W為參考靜態時隙閾值，用來設定靜態時隙數，在可用時隙足夠時，通常為總時隙的10%即可滿足靜態時隙需求。NUM為節點最大可分配時隙數。最終分配靜態時隙X為：

(4)

圖9為分配系數RATTO不同時，節點間不同鏈路網絡傳輸時延最大值、最小值以及平均值的變化對比圖，RATTO取值為15%、20%、25%、30%、50%五種不同的策略。不同鏈路路徑見表3所示。

表3 鏈路路徑設置

按照策略5即將當前空閑時隙的一半進行靜態分配，會導致先分配的節點靜態時隙過多而后分配節點出現“餓死”的現象使得時延增大。按照策略1與策略2進行分配時，由于分配系數過小，分配的靜態時隙過少，導致無法及時發送突發業務導致時延增大。策略3與策略4的效果較好，通過對比可知由于策略3的分配系數較小，靜態時隙較少，應對突發業務能力不足，從而導致出現節點傳輸最大時延與最小時延的差值較大，即產生了時延抖動現象。策略4由于靜態時隙相對充足，沒有時延抖動現象，仿真效果最優。因此本文后續均采用策略4進行仿真。

3.2.2 不同網絡節點數

在自組網的網絡性能測試中，節點的數量是衡量MAC協議的負載能力的重要指標，對網絡的性能起著關鍵的影響。本文針對不同的網絡節點數，觀測對比網絡節點數為2，4，6，8，10，12，14，16，18，20時M-TDMA與STDMA、P-TDMA協議的性能差異。

圖10為3種協議在不同節點數時網絡傳輸時延對比，當節點增加時，網絡的傳輸時延逐漸增大，這是因為在多節點的拓撲環境下節點的鄰居節點增多，緩存數據增大使得傳輸時延提升。而STDMA由于是全向天線協議，當節點數量增多時可用時隙減少，當節點數達到14節點后產生明顯的時延增大。P-TDMA算法由于其沒有考慮節點的不同業務量大小，當節點增多時可用時隙減少時延增大加快，而M-TDMA協議獨特的節點流量預測算法，可以有效減少高業務量需求的時延，傳輸時延最低。

圖10 不同協議網絡時延對比圖

圖11為3種不同協議的網絡吞吐量隨節點數增多的變化圖。在節點數較少時，傳輸鏈路隨著節點數增多而增多，3種協議的吞吐量都隨著節點數的提升而提升。STDMA協議由于是全向天線協議，在8節點以上時，時隙數量減少，鏈路沖突幾率增大導致吞吐量開始下降，而由于P-TDMA與M-TDMA協議是定向天線協議，通過空間復用實現同一個時隙多個鏈路同時發送數據，使得網絡吞吐量可以隨著節點的變多而增大。當網絡節點數增大到16個以上時，時隙資源使用充分，節點間可用鏈路減少，各個協議的吞吐量均開始下降。并且M-TDMA由于使用混合分配模式，既有基于分配系數的靜態時隙又可使用預約幀為節點獲取更多的時隙資源發送數據，因此網絡吞吐性能最好。

圖11 不同協議網絡吞吐量對比圖

圖12為3種協議丟包率隨節點個數變化的情況。隨著節點數量增多，網絡拓撲復雜度逐漸增大，由于網絡節點高速動態變化，網絡的傳輸路徑難以穩定，網絡的擁塞度提升，傳輸時延增大，導致丟包現象產生。隨著節點的不斷增多，丟包率也逐步提升。P-TDMA協議由于競爭分配機制，當節點數增大時，沖突概率增加使得出現網絡堵塞，丟包率增大。而STDMA協議由于是全向天線協議沒有空間復用，節點數增大時在一個調度周期內每個節點可用的數據時隙快速下降導致丟包率迅速上升。M-TDMA協議是定向協議，空間復用率高且使用混合資源分配模式，隨著節點增多，由于分配系數的引入，協議的靜態分配時隙隨之減少可用時隙不會快速下降，有效改善了網絡擁堵現象，丟包率相對較小。

圖12 網絡丟包率對比圖

3.2.3 不同的數據發送速率

本文通過改變節點的數據發送速率來觀察MAC協議在不同網絡負載下的性能，依據前文仿真數據將節點數目設置為14，在星狀拓撲下進行仿真。發送速率為100～1 000 kbps。

圖13為3種MAC協議在數據發送速率增大時平均時延的變化圖。數據發送速度在400 kbps以下時，各協議的傳輸時延為500 ms以內。P-TDMA協議由于未考慮不同節點的業務量大小不同，當傳輸速率在400 kbps以上時，大業務量節點的可用時隙減少，傳輸時延快速提升直至2.5 s左右。而STDMA協議的時延隨著發送速率的提升增大，在700 kbps以上時出現網絡擁塞，由于大量數據丟包，時延逐漸穩定。而M-TDMA協議由于考慮了不同節點的業務量不同，按照流量預測結果合理分配時隙并且通過分配系數的引入動態調整了可分配的動態時隙數量。使得網絡平均時延相對較低。

圖13 網絡時延對比圖

數據發送速率在100～1 000 kbps時3種協議的網絡吞吐量變化情況如圖14所示。隨著數據發送速率的提升，所有協議的吞吐量均增大。STDMA協議的吞吐量小于數據發送速率，而定向MAC協議的吞吐量遠大于數據發送速率。這是由于定向天線使得信道同時可以發送多條鏈路的數據，空間復用率增加，網絡吞吐量不斷提升。而相比于P-TDMA協議，本文設計的M-TDMA協議在數據發送速率達到1 000 kbps時，網絡吞吐量可以達到4 Mbps以上。這是因為在網絡負載增大時，節點通過流量預測算法動態調整不同節點分配的時隙數量，預測網絡流量大的節點優先分配更多的時隙資源，吞吐量得以繼續提升。而STDMA與P-TDMA協議在發送速率達到700 kbps后由于沒有有效的資源動態調整策略，吞吐量不再提升，達到滿負載狀態。

圖14 網絡吞吐量對比圖

圖15對比了當數據發送速率提升時3種協議的丟包率變化情況。當數據發送速率增大時，3種協議的丟包率也不斷增大，這是因為隨著數據發送速率的增大網絡負載變大，數據緩存區的等待數據增多，丟包率也隨之增大。在100～300 kbps的發送速率時，3種協議丟包率控制在5%以內。當發送速率達到700 kbps時，P-TDMA協議由于沒有分配系數均衡靜態與動態時隙，導致可用時隙減少丟包率增大。而STDMA協議是全向天線MAC協議，過大的負載使得節點可用時隙減少，由于過長的排隊時間，導致數據大量丟失丟包率增大。而M-TDMA算法由于分配系數存在，可用時隙減少時靜態時隙會轉化為動態時隙，可用時隙充足。且該算法根據預測各節點業務量大小，動態調整各節點分配的時隙數，排隊時間縮短，數據丟包率降低，在1 000 kbps的速率時丟包率仍控制在20%以內，算法性能最好。

圖15 網絡丟包率對比圖

4 結束語

近些年來隨著無線自組網研究與應用的不斷深入，MAC協議作為自組網關鍵的組成部分具有很重要的研究意義。本文在研究過程中針對高空中拓撲高動態變化的分布式定向自組網的特點，提出了一種基于TDMA的定向分布式資源調度算法M-TDMA，通過引入分配系數，有效均衡了動態與靜態分配的效果；并通過流量預測算法對時隙進行合理的分配，有效改善了網絡擁堵現象。仿真對比表明M-TDMA算法很好的應用于多節點高動態場景，有效減少了網絡平均時延，并提升了網絡吞吐量，提升了網絡效率。