適用于飛行自組網的閑置時隙預約TDMA 協議

陸 毅，符杰林，仇洪冰，林基明，李燕龍，3

（1.桂林電子科技大學認知無線電與信息處理教育部重點實驗室，廣西桂林 541004；2.桂林電子科技大學衛星導航與位置感知重點實驗室，廣西桂林 541004；3.桂林電子科技大學電子電路國家級實驗教學示范中心，廣西桂林 541004）

0 概述

飛行自組網（Flying Ad-Hoc Networks，FANets）是一種由多個飛行器以自組織形式構成的無中心網絡［1］。在電力巡檢、偵察打擊與森林火警等小規模無人飛行器（Unmanned Aerial Vehicle，UAV）集群應用場景中［2-3］，為滿足飛行器間協同編隊的飛行要求，FANets 通過提供較低時延使得飛行器間能夠實時了解彼此位置，以保持隊形并避免碰撞［4］。此外，為了能使操作人員了解現場情況并做出決策，FANets 應具備較高的吞吐能力，且允許負責感知任務的飛行器回傳數據量較大的感知數據。

介質訪問控制（Medium Access Control，MAC）協議主要解決節點間高效使用信道傳輸數據的問題，對時延、網絡吞吐量等性能指標有重要的影響［5］。在網絡負載較重的情況下，固定分配時分多址接入（Time Division Multiple Access，TDMA）協議在時延及吞吐量方面的性能均優于CSMA 協議［6-7］，更適用于有較多數據需要傳輸的FANets 場景。文獻［8］提出一種采用分布式時隙分配方案的TDMA協議，網絡節點通過局部信息交換與協同完成時隙分配，不需要中心節點的參與，且在完成時隙分配后，節點可一直使用分配的固有時隙進行數據傳輸。文獻［9］對文獻［8］提出的時隙分配方法進行改進，并提出一種CF-MAC 協議。該協議在發送時隙占用申請前先進行載波監聽，降低多個節點在同一個時隙發送申請時發生沖突的幾率。然而，當固定分配TDMA 協議存在節點在已分配的時隙上沒有數據需要傳輸時，將會造成時隙浪費，且該時隙被稱為閑置時隙，而過多的閑置時隙將會導致信道利用率的降低。文獻［10］根據節點ID 計算每個節點使用非固有時隙的優先級，當一個時隙閑置時，優先級最高的節點可以使用該時隙發送數據，這樣雖然允許其他節點使用未被使用的時隙，但僅簡單地根據節點ID計算優先級而未考慮節點的實際傳輸需求，可能會出現優先級最高的節點也沒有數據需要傳輸的情況，從而造成閑置時隙不能被合理使用。文獻［11］提出的ESTDMA 采用基于概率發送的時隙二次分配策略，當出現閑置時隙時，有數據傳輸需求的節點將以一定概率發送RTR 幀與目的節點握手，則目的節點能夠接收數據并應答CTR 幀。ESTDMA 是一種拓撲透明的TDMA 協議，該協議在進行時隙分配時不考慮網絡拓撲，且出現時隙分配沖突的幾率較大［12］。雖然二次分配策略可在時隙沖突情況下使節點以競爭方式嘗試使用時隙，但無法保證節點一定能夠成功傳輸，且與固定分配TDMA 協議相比，其傳輸過程的可控性較差且不利于實現低時延傳輸。文獻［13］設計的CTMAC 在固定分配TDMA 的基礎上引入載波監聽與隨機退避機制，允許節點以競爭的方式使用閑置時隙。當一個時隙開始后，除了時隙所屬節點外的其他所有數據傳輸節點將對信道進行監聽，若監聽期間信道一直保持空閑狀態，則表明時隙所屬節點并未使用該時隙進行數據傳輸，其他存在數據傳輸的節點將進行隨機退避，并在退避結束后嘗試使用該時隙進行數據傳輸。

文獻［13］雖然可在一定程度上提高固定分配TDMA 協議的信道利用率，但是隨機退避機制將會增加時間開銷，特別是當TDMA 的幀長較短時，時間開銷無法忽略不計，對網絡的吞吐性能造成影響。此外，當參與競爭的節點數量較多時，信道的使用沖突幾率將會增加，沖突的加劇將造成閑置時隙無法被成功使用。這些問題限制了以競爭方式使用閑置時隙的方法對信道利用率及網絡吞吐性能的提升。為此，本文設計一種能夠高效使用閑置時隙的TDMA協議——ISR-TDMA。該協議通過在幀結構中加入隨機數字段，用預約協商的方式代替退避競爭，使節點可以無沖突地使用閑置時隙，從而降低閑置時隙使用的開銷，有效提升信道利用率與網絡吞吐性能。

1 問題描述與分析

閑置時隙的存在降低了固定分配TDMA 協議的信道利用率及網絡吞吐性能。通過引入載波監聽與隨機退避機制競爭使用閑置時隙，這在一定程度上提高了信道利用率，但當參與競爭的節點較多時，將面臨與競爭類MAC 協議類似的問題，即競爭的加劇使得閑置時隙無法被成功使用。此外，為了滿足低傳輸時延的要求，TDMA 協議需采用較短的幀長，此時競爭開銷不可忽視，將會對網絡的吞吐性能造成影響。

隨機退避中的退避時間TBO為[0，K)中的一個隨機整數乘以退避單位（Backoff Unit，BU）。根據文獻［14］可知，在n個節點參與競爭且每個節點在[0，K)中等概率選擇隨機整數的情況下，某一閑置時隙能被成功使用的概率P為：

式（1）說明當且僅有一個節點的隨機整數取值為k，而其余節點的隨機整數取值均大于k時，該閑置時隙才能被成功使用。

概率P的計算結果如圖1 所示。從圖1 可以看出：在K不變的情況下，參與競爭的節點數n越大，信道競爭越激烈，發生沖突的可能性變大，閑置時隙使用成功率變小；在n不變的情況下，K越大節點選擇相同數值的可能性越小，發生沖突的幾率越小，閑置時隙使用成功的概率則越大。

圖1 在不同n 與K 下的競爭成功率計算結果Fig.1 Calculation results of competition success rate under different n and K

幀長對TDMA 協議的平均時延有重要的影響，若實現數十毫秒甚至幾毫秒級的平均時延，幀長也應取相似的長度［15］。幀長取值較短時，競爭開銷占比過大將會影響網絡的吞吐性能。以IEEE 802.11的退避參數為參考依據［16］，BU 取值為20 μs，K取值為32，則一個時隙中的競爭開銷為0.62 ms。表1 給出了不同幀長及每幀時隙數下的競爭開銷占比。由此可以看出，在幀長較短的情況下，競爭開銷存在較大的占比。這說明競爭使用閑置時隙雖然在一定程度上增加了信道利用率，但降低了每個時隙實際能夠發送的數據量，且網絡吞吐量也會受到影響。

表1 在不同幀長與每幀時隙下的競爭開銷占比Table 1 The proportion of contention overhead under different frame lengths and different time slots per-frame

上述討論基于以下假設：BU 的長度大于或等于信號傳播至節點最大通信距離處所需要的時間（最大傳播時間），但在BU 小于最大傳播時間的情況下，傳輸成功率未必會急劇下降［17］。假設至少需要c個退避單位可使退避時間大于或等于最大傳播時間，則式（1）可改寫為：

式（2）表明，若一個節點退避k個單位，其余節點至少退避k+c個單位，閑置時隙也可被成功使用，但此時競爭成功率會有所下降。由此可見，在幀長較短的情況下，可通過犧牲競爭成功率的方式降低競爭開銷。

由上述分析可知，在采用短幀長的情況下，通過隨機退避來競爭使用閑置時隙，以提高信道利用率和網絡吞吐性能的做法存在局限性，即競爭成功率和競爭開銷均對網絡吞吐性能造成影響，這2 個因素相互制約的關系限制了網絡性能的改善。此外，隨機退避并不能保證沖突不會發生，在發生沖突的情況下，閑置時隙不能成功傳輸數據，導致信道利用率的提升有限。因此，本文需要設計合理的閑置時隙使用機制，以較小的開銷提高信道利用率及網絡吞吐性能，更好地滿足無人飛行器系統的要求。

2 協議設計

為提高閑置時隙的使用效率，減少額外開銷，本文設計一種使用隨機數預約的閑置時隙使用方案及相應的TDMA 協議——ISR-TDMA。該協議以固定分配TDMA 為基礎，通過為每個節點固定分配時隙的方式，保證節點的基本通信能力，實現高優先級業務的低時延傳輸。節點在各自所分配的時隙中發送信息對閑置時隙的使用進行預約，并根據預約結果有序使用閑置時隙。與以競爭的方式使用閑置時隙相比，ISR-TDMA 不存在閑置時隙使用沖突的情況，可以更充分地使用閑置時隙，且其還省去了隨機退避的時間開銷，增加了每個時隙可以傳輸的數據量，具有更高的吞吐量。

2.1 幀結構

圖2 所示為ISR-TDMA 協議的幀結構。一個ISR-TDMA 幀由若干個時隙組成，為了避免由于傳播時延不同而引起相鄰時隙間的數據沖突，各時隙之間需要加上保護間隔。每個時隙由時隙信息（Slot Information，SI）和數據（Data）兩個部分組成。SI 主要用于節點間的協調以實現分布式時隙分配以及閑置時隙預約，Data 用于數據傳輸。幀長是設計TDMA 協議的一個重要參數，且對時延有重要影響。ISR-TDMA 主要解決固定分配TDMA 時隙浪費較為嚴重的問題，對于幀長并沒有限制，可根據實際需要并結合文獻［18］的相關理論對幀長進行設置。

圖2 ISR-TDMA 協議的幀結構Fig.2 Frame structure of ISR-TDMA protocol

SI 的結構由源ID、目的ID、時隙狀態表與隨機數字段4 個部分組成。其中：源ID 與目的ID 用于標識數據包的收發雙方；時隙狀態表中記錄了節點單跳鄰居對時隙的使用情況，用于分布式時隙分配，并確認其他節點的時隙申請；隨機數字段則用于閑置時隙的預約。

2.2 時隙申請策略

ISR-TDMA 采用與CF-MAC［9］類似的時隙申請策略，使用分布式時隙分配算法為節點獲取一個時隙。節點周期性的發送SI 來交換各自單跳鄰居的時隙使用情況，圖3 給出了節點進行時隙申請的具體流程。新入網節點首先偵聽信道一個幀長的時間，接收網內節點發送的時隙占用表，構建自身的初始時隙占用表。在偵聽一幀信道后，根據鄰居節點發送的時隙占用表以及自身的時隙占用表，新入網節點可以獲知附近節點對時隙的使用情況，選擇與其他節點不會發生沖突的時隙作為候選時隙。候選時隙首次到來時新入網節點將發送SI，若只有一個新入網節點發送SI，則網內節點可以成功收到新入網節點的SI 并更新自身時隙占用表，且添加新入網節點的信息；若有多個新入網節點發送SI，則網內節點由于SI 沖突無法成功接收SI，且不會更新時隙占用表。在發送SI 后，新入網節點將等待一個幀長的時間，在此期間內如果接收到的網內節點發送的SI 的時隙占用表中均有新入網節點信息，則表明時隙申請沒有發生沖突，新入網節點成功申請到時隙；若網內節點的時隙占用表中沒有新入網節點的信息，表明時隙申請存在沖突，新入網節點需要重新選擇時隙并進行申請。將節點成功申請到的時隙稱為節點的主時隙，同時稱節點為該時隙的主節點。

圖3 節點的時隙申請流程Fig.3 Time slot application procedure of the node

2.3 閑置時隙感知

圖4 給出了閑置時隙感知流程。由此可知，在每個時隙開始后，無論主節點有無數據包需要傳輸，都要在時隙開始后傳輸SI。若主節點有數據包需要傳輸，則在目的地址字段填上接收節點的ID，否則填0。其他節點在收到SI 后，根據目的節點ID 數值即可判斷當前時隙是否會被主節點用于傳輸數據。若有數據要傳輸，則主節點在發送SI 后緊接著發送數據包；若沒有數據包要傳輸，當前時隙就是一個閑置時隙，其他有數據包傳輸的節點將根據預約結果使用該時隙進行數據傳輸。

圖4 閑置時隙感知流程Fig.4 Procedure of idle time slot sensing

2.4 閑置時隙預約與使用

圖5 給出了閑置時隙的預約與使用流程。由此可知，當一幀開始后，每個節點接收到其他節點發送的SI，讀取并保存隨機數字段中的數值。主時隙到來時，如果節點的數據包隊列有一個以上的數據包需要傳輸，則生成一個隨機整數填入SI 中的隨機數字段發送，否則將-1 填入隨機數字段發送。當前幀結束時，需要使用閑置時隙的節點對保存的隨機數進行排序，并獲得自身的排名。在下一幀開始后，節點將根據此排名順序使用閑置時隙。閑置時隙的預約與使用并不是在同一幀內完成的，例如節點在第i幀根據自身隊列情況判斷是否需要使用閑置時隙，若需要則對第i+1幀的閑置時隙進行預約。而第i+1幀節點將根據第i幀的預約結果有序使用閑置時隙，同時又根據具體情況決定是否對第i+2 幀的閑置時隙進行預約。隨機數預約方式通過節點間的信息交互協商完成閑置時隙的使用權分配，與隨機退避方式通過競爭使用閑置時隙的做法相比，其僅需在SI 中添加一個隨機數字段，無需預留時間進行隨機退避，減少了相關開銷，提升了每個時隙實際可傳輸的數據量，從而提升網絡吞吐量。此外，隨機退避方式在感知到閑置時隙后立即嘗試競爭使用閑置時隙，存在因多個節點同時嘗試使用閑置時隙而產生沖突的可能性。隨機數預約方式在閑置時隙產生前，已經由節點確定對閑置時隙的使用順序，不存在閑置時隙使用沖突的可能，可以更高效地使用閑置時隙，并提升信道利用率。

圖5 閑置時隙預約與使用流程Fig.5 Procedure of reservation and use of idle time slot

3 仿真分析

實驗使用OMNeT++對ISR-TDMA 協議性能進行仿真分析。仿真場景由1 個地面站節點及19 架無人飛行器節點組成。為了保證每個節點都能接收到其他所有節點的SI，避免隨機數排序結果不同，本文僅考慮節點間均可相互通信的單跳場景。在節點移動模型的選擇上，編隊飛行模型在網絡仿真軟件中較難實現，且相關研究多數采用隨機游走（Random Walk，RW）模型［19-20］，因此，本文也選擇采用隨機游走模型。

網絡中存在高優先級、低優先級兩種業務，高優先級業務要求較低的時延，用于模擬協同及控制業務；而低優先級業務要求較高的吞吐量，用于模擬感知業務。無人飛行器分為高負載、低負載兩類。高負載無人飛行器有高優先級、低優先級兩類業務需要傳輸；低負載無人飛行器只有高優先級業務需要傳輸。地面站節點靜止位于仿真場景最左側的中部，僅有高優先級業務需要傳輸。

實驗的主要仿真參數如表2 所示。高、低優先級業務產生的數據包個數均服從泊松分布。為保證對比的合理性，實驗對CF-MAC、CTMAC 與本文協議進行了適當修改，3 種協議的幀長、時隙數、保護間隔均按照表2 給出的參數進行設定。此外，還為3 種協議設計了優先級機制，當同時有高、低兩種優先級的數據包需要發送時，優先發送高優先級數據包。

表2 仿真參數設置Table 2 Simulation parametes setting

3.1 退避參數的選擇

由前文可知，BU 的長度未必要大于或等于信號最大傳播時間。通過仿真來驗證在參數合理的情況下，載波監聽與隨機退避機制也能為采用短幀結構的TDMA 協議帶來較高的吞吐量，同時也通過仿真尋找一個較為合適的參數，用于CTMAC 協議與其他協議的對比實驗。

圖6 給出了高負載節點數分別為32 和64 時BU 對網絡吞吐量的影響，BU 為0 表示不采用載波監聽與隨機退避機制，仿真場景中信號的最大傳播時間約為48 μs。可以看出，BU 取較小值時，該機制對固定分配TDMA 協議的吞吐量有一定提升。當BU 較大時，競爭開銷在整個時隙中的占比較大，單個時隙可傳輸的數據量變少，使得信道利用率的提升也無法引起吞吐量的增加，反而會降低吞吐量。當BU 為1 μs、K取64 時，吞吐量最高。后續仿真將使用該參數進行協議之間的對比分析。

圖6 退避參數對吞吐量的影響Fig.6 Impact of backoff parameters on throughput

3.2 協議仿真對比

仿真通過改變19 架無人飛行器中高負載無人飛行器的數目，從信道利用率、網絡吞吐量與平均時延3 個方面對ISR-TDMA 與CF-MAC［9］、CTMAC［11］進行對比分析。

3.2.1 信道利用率與網絡吞吐量

圖7、圖8 為3 種協議的信道利用率和網絡吞吐量的對比結果。從圖7、圖8 可以看出，當高負載節點數較少時，ISR-TDMA、CTMAC 可以使用閑置時隙傳輸數據，信道利用率均高于CF-MAC，并且因為這2 個協議能使用更多的時隙傳輸數據，所以其吞吐量也高于CF-MAC。由于ISR-TDMA 比CTMAC少了隨機退避的開銷，同時不存在競爭沖突，因此其信道利用率及網絡吞吐量更高。隨著高負載節點的增加，競爭的加劇使CTMAC 協議的閑置時隙競爭成功率下降，其信道利用率逐漸接近CF-MAC，此時因為CTMAC 存在隨機退避開銷，每個時隙可傳輸的數據量少于CF-MAC，所以其吞吐量反而要低于CF-MAC。當網絡中多數節點均為高負載節點時，閑置時隙越來越少，3 種協議的信道利用率逐漸接近。此時CF-MAC 的額外開銷最少，但其網絡吞吐量最高。

圖7 3 種協議的信道利用率對比Fig.7 Comparison of channel utilization of three protocols

圖8 3 種協議的網絡吞吐量對比Fig.8 Network throughput comparison of three protocols

3.2.2 平均時延

圖9、圖10 分別為高、低優先級平均時延對比結果。由圖9 可知，隨著高負載節點數的變化，3 種協議的高優先級業務平均時延的波動均較小，且均在6.5 ms 左右，這是因為優先級機制保證了高優先級業務的優先傳輸，而仿真結果也說明固定分配TDMA 協議通過采用短幀長的方式，在發包率適當的情況下可提供較低的平均時延。由圖10 可知，當高負載節點較少時，CTMAC 與ISR-TDMA 可以使用閑置時隙傳輸數據，無需每個數據包都等到自身時隙到來時才能傳輸，它們的低優先級業務平均時延均優于CF-MAC，而由于SR-TDMA 對閑置時隙的使用更充分，其低優先級業務平均時延低于CTMAC。在高負載節點較多的情況下，閑置時隙較少，每個節點基本都只能用自身時隙來傳輸數據，此時CF-MAC 的吞吐量最高，而僅需花費較少的時間即可完成一個完整數據包的傳輸，其低優先級業務的平均時延低于其他2 種協議。

圖9 3 種協議的高優先級業務平均時延對比Fig.9 Comparison of average delay of high priority services of three protocols

圖10 3 種協議的低優先級業務平均時延對比Fig.10 Comparison of average delay of low priority services of three protocols

4 結束語

本文設計一種基于閑置時隙預約機制的TDMA協議。該協議為每個節點固定分配一個時隙，以保證節點的基本通信能力，滿足飛行器控制與協同業務的低時延傳輸需求，且允許高負載節點對下一幀出現的閑置時隙進行預約與使用。仿真結果表明，該協議可使協同與控制業務具有較低時延的同時，為感知業務提供較高信道利用率與網絡吞吐量。下一步將采用自適應方法動態調整閑置時隙感知機制，以提高飛行自組網在重負載情況下的吞吐性能。