含網關節點的高時隙復用率TDMA協議

韋 亮，任 智，陳 凱，張關鑫

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

較于移動自組網，無人機自組網[1-7]的研究起步較晚。早期MAC層采用ALOHA協議，隨后被載波偵聽多路訪問/沖突避免協議(carrier sense multiple access with collision avoid，CSMA/CA)取代，文獻[8]對CSMA/CA協議的結構做了部分調整，但調整后仍不能滿足無人機自組網的需求。文獻[9]保證控制信息的及時交付，但其沒考慮新節點的入網，靈活性較差。文獻[10]采用定向天線，把每個節點的一跳鄰域劃分為完全連接的一跳鄰域，在一定的程度下提高了時隙復用率，但該協議的幀結構較為復雜，且控制開銷較大，并不適合無人機自組網。文獻[11]中每個節點僅需要自己鄰居節點的節點信息，不需要整個網絡的拓撲和流量信息，因此降低了控制開銷，但是由于無人機的移動性，使得天線難以實時校準。文獻[12]提出一種基于閑置時隙預約傳輸機制的ISR-TDMA協議，但并未充分考慮業務優先級且靈活性不高。文獻[13]動態地切換CSMA和TDMA狀態，但僅適用于星型網絡，仍不能較好滿足無人機多跳網絡的需求。文獻[14]提出了一種雙向管道TDMA協議，能夠較好保障無人機節點在多跳網絡場景中數據傳輸的可靠性，但也產生了一定的控制開銷、部分信道資源的浪費和數據時隙沖突問題。文獻[15]減少了現有協議的部分控制開銷，改進了現有的TDMA協議在節點高速移動的情況下未及時更新時隙請求參數的問題，但也增加了節點時隙沖突的可能性。

為解決現有文獻存在的問題，在文獻[14，15]的基礎上，提出了FU-TDMA協議。本文的貢獻如下：①提出時隙請求時期快速收斂機制，對現有相關TDMA協議中的控制時期網絡收斂慢問題進行改進；②空閑時隙公平重用機制，解決了現有相關TDMA協議中的中心節點時隙分配沖突的問題，提高了時隙的復用率；③一跳鄰居多層次調度機制，保障了節點的公平性，降低了節點調度的時延性，增強了網絡的可靠性。

1 網絡模型、幀結構及問題描述

1.1 網絡模型

網絡拓撲如圖1所示。由一個中心節點(central node，CN)、部分普通節點、個別網關節點(gateway node，GN)和一個地面站(ground station，GS)構成。CN負責在時隙分配時期廣播全網時隙表；GN負責傳遞GS的指控信息給網絡其余節點和把其余節點采集的數據信息發送給GS；普通節點負責數據的采集及其余信息的中繼；GS負責控制空中無人機集群執行任務。

圖1 網絡拓撲

1.2 幀結構

協議的幀結構如圖2所示。該幀結構由CMOP時期(CP)、Data時期(DP)和SMOP時期(SP)組成且各個時期長度受CN控制。在每個幀開始，CN在CP的第一個時隙廣播新的時隙分配表，收到這個CMOP幀的節點更新自己在當前幀內新分配的時隙信息及梯度值(CN的梯度值為0，距離CN跳數為n跳的節點梯度值為n)，然后在自己的CP時隙廣播CMOP幀。在DP期間，節點根據在當前幀內的CP接收的時隙分配表，在自己的時隙傳輸上行監視、偵察數據和下行命令數據。在SP期間，節點發出SMOP幀，在自己的SP時隙傳遞自己的時隙請求和中繼子節點的時隙請求；對于多個父節點存在的情況時，子節點依據上一幀收到的父節點的時隙請求消息，按照負載均衡的思想，選擇目的父節點。在SP的競爭時期，用于處理新節點的入網請求及失敗節點的重傳。在CP期間，節點梯度值越大，時隙越靠前；在SP期間，反之。CMOP幀格式及SMOP幀格式如圖3所示。

圖2 幀結構

圖3 幀格式

1.3 問題描述

(1)中心節點在全網廣播CMOP幀之前(即在SP時期)，其余節點會向中心節點發送SMOP幀用于申請時隙，其中申請的時隙信息包括節點自身和子節點的時隙請求。在此過程中，若網絡節點數為N，SP時隙長度為L，因為在每個SP時隙，僅有一個節點占用該時隙并發送SMOP幀，那么SP時期則需要(N-1)*L個SP時隙。如圖1所示，當節點信息傳輸滿足一定范圍互不影響時，帶有粗線的節點9、節點11及節點13和帶有粗線的節點4及網關節點就可以在兩個SP時隙分別調度，因為在節點9、節點11及節點13同時發送SMOP幀時，不會產生沖突，不會造成節點重新發送時隙請求信息。此時原本需要5個SP時隙而現在僅需2個SP時隙就能把節點時隙請求傳遞成功，極大地節約了信道資源。在現有協議的標準中，由于在一個SP時隙僅由一個節點占用，浪費了大量的時隙資源，造成了網絡在SP階段收斂較慢。

(2)節點在發送SMOP幀時，采用單跳廣播方式。節點梯度值小于SMOP幀字段Hop Count時，節點會聚合大于自身梯度值且與其為一跳鄰居的節點發送的時隙請求消息，當部分節點存在多個小于其梯度值的一跳鄰居時，節點廣播SMOP幀，多個小于其梯度值的鄰居節點都會中繼其時隙請求。如圖1所示，節點10廣播時隙請求，節點5、節點6收到時隙請求信息并中繼時隙請求信息。雖然現有的研究通過增加一個中繼字段，采用負載均衡的方式，有效地解決了這個問題，但也增加了節點時隙沖突的可能性。在中心節點調度節點的時隙分配時，由于形成的拓撲存在偶爾不完整的情況，致使在拓撲圖內三跳及以上跳數的節點在同一時隙發包時會產生沖突。如圖1所示，節點2收到了節點5、節點6廣播的時隙請求信息，因為節點5和節點6廣播的時隙請求信息里都包括了節點10的時隙請求，然而節點2僅會留下節點10的一個時隙請求，在中心節點收到全網節點的時隙請求時，可能會誤判節點10與節點5為一跳鄰居而與節點6為3跳鄰居或節點10是與節點6為一跳鄰居而與節點5為3跳鄰居，導致分配同一個時隙給節點10和節點5或節點10和節點6，發生時隙分配沖突。

(3)在競爭時期，節點調度形式過于單一化，時隙爭用僅按照梯度值作為信道的訪問優先級，極大可能存在部分同梯度節點同時發送SMOP幀，致使沖突，延長節點SMOP幀的重傳時間，嚴重時可導致當前競爭時隙損壞，使得節點在下一幀無時隙分配。

2 FU-TDMA

針對上述問題，提出了FU-TDMA協議。該協議包含3個新機制：①時隙請求時期快速收斂機制，中心節點并行調度節點上傳時隙請求，減少網絡收斂時間；②空閑時隙公平重用機制，消除因中心節點維護的拓撲表不完整時所造成的沖突問題，挖掘出所有空閑時隙，提高信道利用率；③一跳鄰居多層次調度機制，節點計算所有一跳鄰居的優先級，使較高優先級節點先重傳，降低碰撞概率。

2.1 時隙請求時期快速收斂機制

針對1.3節問題描述(1)，本文提出時隙請求時期快速收斂機制。該機制的核心思想是：在SP階段，考慮各節點控制時隙調度順序。中心節點建立并維護全網拓撲后，制訂一個用于觸發部分節點并行調度的閾值，用于通知節點傳遞位置信息，然后再根據中心節點維護的包含位置信息的拓撲，采用基于距離的并行調度算法，快速地調度各節點控制時隙，以較短的時間獲取全網拓撲及時隙請求信息。

2.1.1 基于距離的并行調度算法

基于距離的并行調度算法具體流程如下：

步驟1 從拓撲圖中選出葉子節點及相連的父節點構建二部圖G(v，e)，記梯度值為奇數的節點集為V奇，梯度值為偶數的節點集為V偶，其中X∈V奇，Y∈V偶。

步驟2 根據形成的二部圖，每個葉子節點計算與其余不相連的父節點的距離da→b，表示為

(1)

(2)

(3)

步驟4 在拓撲圖中剔除篩選邊的葉子節點，更新拓撲圖。

步驟5 若在拓撲圖中只剩下CN，則結束；否則，轉步驟1。

2.1.2 時隙請求時期快速收斂機制具體流程

時隙請求時期快速收斂機制具體流程如下：

步驟1 在SP期間，由梯度值最大的節點發起時隙請求，該節點創建自己的所需時隙請求的聚合信息，廣播SMOP幀。上層父節點收到子節點的SMOP幀后，更新自己的一跳鄰居表，查看收到的SMOP幀里的ECG字段信息，將子節點發送的SMOP幀里的ECG字段的信息聚合在本節點待發送的SMOP幀里的ECG字段里，然后廣播SMOP幀。

步驟2 CN收到所有下層普通節點發出的SMOP幀后，查看各普通節點的時隙申請信息并匯總創建維護全網節點拓撲圖。根據其拓撲圖的復雜程度及其規模來確定是否在當前幀內節點上傳地理位置信息。若全網拓撲圖還沒到達閾值，繼續執行步驟3，否則轉步驟4。

步驟3 若不需要節點上傳地理位置信息，在下一幀的CP，CN廣播一個更新后的時隙分配圖且在CMOP幀中的時隙分配字段按照節點梯度值順序排列。普通節點收到CN發出的CMOP幀后，首先更新自己的一跳鄰居信息表，然后查看自己申請的時隙位并在自己的CP時隙廣播CMOP幀。轉步驟1。

步驟4 若需要節點上傳地理位置信息，在下一幀的CP，CN發放全網節點時隙分配圖。其時隙分配圖按照節點梯度值逆序排列，表明在當前幀的SP，如果各普通節點廣播SMOP幀，不僅需要在ECG字段聚合子節點和自己的時隙請求信息還需要聚合當前所在的位置信息。然后節點在自己的CP時隙廣播CMOP幀，轉步驟5。

步驟5 各普通節點收到其由CN廣播的CMOP幀，在當前SP，由梯度值最大的節點開始調度，向網絡廣播包含時隙請求和地理位置的SMOP幀。父節點收到子節點發送的SMOP幀，匯總自己的時隙請求、地理位置和子節點的時隙請求、地理位置，在自己的SP時隙廣播聚合的SMOP幀。

步驟6 所有節點在SP期間上傳地理位置，CN收到所有子節點發的SMOP幀。在形成新的全網拓撲圖的基礎上，CN根據各節點的位置信息，采用并行調度算法，在下一幀的SP，并行調度部分節點的時隙請求。

步驟7 CN按照所維護的全網拓撲圖，在節點不沖突的情況下，計算普通節點SP時隙的分配。在下一個CP期間，CN廣播CMOP幀，若其中時隙分配字段里節點時隙分配按照調度順序順序排列，則表明在當前SP，普通節點聚合的信息字段里，仍然需要包含節點當前所在的地理位置信息；如果時隙分配字段里的節點時隙分配按照調度順序逆序排列，則表明在當前SP，普通節點不需要再上傳自己當前所在地理位置信息。在時隙分配圖中，節點ID、上行時隙和下行時隙順序排列表示節點占一個調度時隙；節點ID、下行時隙和上行時隙逆序排列表示此節點同上一個節點一起調度。

步驟8 普通節點收到了CN廣播的CMOP幀，記錄自己的時隙信息，發現時隙分配圖按照調度順序順序排列，繼續在即將到來的SP聚合自己的位置信息；若發現時隙分配圖按照調度順序逆序排列，則在SP不聚合節點所在位置信息，并在自己的CP時隙廣播CMOP幀。

步驟9 普通節點根據在CP時隙收到的CMOP幀里的時隙分配圖的順序，在SP時隙開始其節點的調度。并行調度的節點創建自己的時隙請求聚合信息，至SP結束。轉步驟2。

基于上述方案設計的時隙請求時期快速收斂流程如圖4所示。

圖4 時隙請求時期快速收斂流程

2.2 空閑時隙公平重用機制

針對1.3節問題描述(2)，為了充分地使用信道和消除中心節點分配時隙時導致的沖突問題，本文提出空閑時隙公平重用機制。該機制的核心思想是：CN根據分配給各個節點的時隙，詳細地挖掘出每個節點的空閑時隙。針對空閑時隙，CN消除其中會致使沖突的時隙，進行公平的時隙分配。

空閑時隙公平重用機制具體步驟如下：

步驟1 普通節點在SP上傳時隙請求信息且攜帶位置信息，SP結束，中心節點查看各節點的時隙請求。

步驟2 CN依據各節點時隙請求分配時隙。

步驟3 針對已分配的時隙，CN記錄給每個節點分配的時隙ASk。

步驟4 對各個節點，計算各節點未使用的時隙NASk，則NASk表示為

NASk=Ttotal-ASk

(4)

Ttotal為數據時期的總時隙數。

步驟5 根據節點傳遞的位置信息，計算dk->i≤2R，找出該節點所有兩跳內的節點，并求出節點可采用時隙PUSk。dk->i≤2R、PUSk表示如下

(5)

(6)

圖5 兩跳內鄰居數計算

(7)

步驟7 對于兩跳內節點共有的部分時隙，CN按照每個節點申請時隙權重的比值進行公平的分配，故所有時隙已完全分配。

基于上述方案設計的空閑時隙公平重用算法流程如圖6所示。

圖6 空閑時隙公平重用算法流程

2.3 一跳鄰居多層次調度機制

針對1.3節問題描述(3)，本文提出一跳鄰居多層次調度機制。該機制的核心思想是：相鄰的一跳鄰居節點分別計算各自鄰居的優先級，依據優先級的多樣性，使優先級高的節點優先使用時隙，增強了網絡可靠性。

考慮節點在競爭時期調度單一的問題，加入鄰居節點請求時隙數量、子節點數量、平均時隙請求數量及子節點變化率(sub-node change rate，SCR)，多層次調度節點爭用順序，保證各節點公平性。一跳鄰居多層次調度機制具體步驟如下：

(8)

其中，Nrn為節點n的一跳鄰居集、Subk為節點k的子節點集。在競爭階段，對于鄰居節點時隙請求數量、鄰居攜帶子節點數量及平均時隙數量較大的鄰居節點優先級更高，這些節點可以獲得較低的端到端時延，從而降低整個網絡的時延。

(9)

子節點變化率反映了鄰居節點部分的拓撲變化狀況，變化率越大，說明拓撲穩定性較差，對于變化率較小的優先級越高，可以減少節點因為不穩定因素導致的數據丟失，提升網絡穩定性。

步驟3 在競爭階段，一跳鄰居節點內優先級表示為

(10)

步驟4 在一跳鄰域內，節點按照梯度值和Pk的大小及優先級大小對時隙爭用，梯度值越大節點優先爭用，同梯度值節點，Pk越大的節點在競爭階段優先爭用。

基于上述方案設計的一跳鄰居多層次調度算法流程如圖7所示。

圖7 一跳鄰居多層次調度算法流程

3 仿真驗證

本文使用OPNET14.5通信網絡仿真軟件，對比CSMA協議、BiPi-TMAC協議、ERMH-TDMA協議以及FU-TDMA協議的性能，分析仿真結果。

3.1 仿真流程

(1)設置MAC層進程模型及應用層模型。其中MAC層進程模型包括INIT、CMOP、Data及SMOP狀態機，用于完成初始化和時幀的控制信息及業務信息傳輸；應用層模型包括Sink和Source模塊，用于數據包的發送與接收。

(2)設置節點模型。物理層采用全向天線，網絡層采用OLSR協議，傳輸層采用透傳模塊。

(3)設置網絡模型。4種協議采用一樣的場景，中心節點處于網絡中心，其余普通節點圍繞中心節點層層擺放，地面站與網絡邊界的網關節點通信。

(4)收集所需的統計量。

(5)仿真結果分析。對收集的統計量進一步分析，得出吞吐量、數據傳輸時延及時隙利用率。

3.2 仿真參數設置

仿真參數設置見表1。

表1 主要的仿真參數設置

3.3 仿真結果分析

本文通過以下性能指標來驗證網絡性能：

(1)SP時期網絡收斂時間：全網節點在上傳SMOP幀至中心節點所需的總時間。

(2)數據傳輸平均時延：數據包從源傳輸到目的地的平均時間。

(3)數據傳輸成功率：目的地收到的數據包與源產生的數據包之間的平均比值。

3.3.1 SP時期節點收斂時間

圖8為不同網絡規模下FU-TDMA、ERMH-TDMA、BiPi-TMAC和CSMA協議的SP時期網絡收斂時間對比。由圖可知，隨著節點個數增加，SP時期收斂時間逐漸增大，這是因為更多的節點上傳時隙請求。仿真結果表明，在節點數低于7時CSMA在SP時期是最快收斂的，但是隨著節點數的增多，導致SMOP幀的數量增多，從而導致無線信道中碰撞概率增大，因此在節點數8及其以后網絡的收斂時間是偏高于另3種協議。ERMH-TDMA與BiPi-TMAC收斂時間一致，其原因為：在SP時期中心節點會給各節點分配一個不同的SMOP時隙(分配的總時隙數為節點數減一)。在節點數為30時，FU-TDMA相比于ERMH-TDMA和BiPi-TMAC下降了17.2%，其原因為：FU-TDMA的時期請求時期快速收斂機制采用基于距離的并行調度算法相比于ERMH-TDMA和BiPi-TMAC的每個節點分配一個不同的SMOP時隙的方式，FU-TDMA在一個SMOP時隙并行調度節點上傳時隙請求信息，因此收斂更快。注意在節點數25時，FU-TDMA相比于ERMH-TDMA 和BiPi-TMAC降低了20.8%，比節點數30時更小，這是因為基于距離的并行調度算法計算的結果不一定是全局最優的，但整體而言FU-TDMA的收斂時間低于ERMH-TDMA和BiPi-TMAC。

圖8 SP時期網絡收斂時間

3.3.2 數據傳輸平均時延

圖9為節點數20時，3種協議的數據傳輸平均時延對比。由圖可知，隨著節點速率的增加，端到端時延逐漸增大，這是因為節點移動過快，導致鏈路穩定性下降，從而導致部分幀重傳。上行端到端時延與下行端到端時延有顯著差距是因為上行優先級高于下行，可能會導致部分節點上行數據隊列更長。況且時隙請求大小與隊列長度成正比，這使得節點為上行業務存儲更長的時間，從而增大了下行業務的傳輸時延。仿真結果表明，在上行端到端平均時延中，BiPi-TMAC較CSMA下降了32.2%～36.1%，ERMH-TDMA較BiPi-TMAC下降了3.2%～4.7%，FU-TDMA較ERMH-TDMA下降了5.5%～8.9%；在下行端到端時延中，BiPi-TMAC較CSMA下降了47.1%～50.8%，ERMH-TDMA較BiPi-TMAC下降了2.6%～7.7%，FU-TDMA較ERMH-TDMA下降了4.5%～11.1%。主要原因有如下3點：①CSMA通過競爭的方式爭用信道，隨著節點移動性的增大，使得業務在隊列里持久堆積，所以端到端時延較大，且調度類的BiPi-TMAC有時隙的分配，所以時延較??；②ERMH-TDMA相比于BiPi-TMAC及時更新節點時隙請求信息，減少重傳次數及丟包率，從而降低了時延；③FU-TDMA相比于ERMH-TDMA采用“SP時期快速收斂”新機制，中心節點基于距離的并行調度算法，使得網絡在SP時期快速收斂，縮短時幀長度，從而導致中心節點更新拓撲快，增強鏈路的實時性，可有效降低時延；采用“空閑時隙公平重用”新機制，消除了中心節點調度節點時隙時產生的沖突問題，使節點充分公平地利用時隙，提高了時隙復用率，減少了數據和指控業務的排隊時延，增加了網絡的吞吐量；采用“一跳鄰居多層次調度”新機制，讓優先級高的節點優先爭用競爭時隙，防止因節點調度太過單一造成碰撞，降低了節點重傳和節點入網的時延。

圖9 數據傳輸平均時延

3.3.3 數據傳輸成功率

圖10為節點數為20時，數據傳輸成功率在不同的移動性下的映射。因為節點移動性越高會導致節點鄰居關系變化越快，丟包率越大，所以隨著節點移動性的增加，4種協議的數據傳輸成功率呈下降趨勢。由圖可知，BiPi-TMAC較CSMA成功率提高了7.2%～17.3%，ERMH-TDMA較BiPi-TMAC提高了0.9%～2.1%，FU-TDMA較ERMH-TDMA提高了2.2%～3.9%，其原因為：①由于節點移動性，相對于CSMA，調度類的ERMH-TDMA、BiPi-TMAC和FU-TDMA協議有動態分配的屬于節點的時隙，且在SMOP時期緊隨一個競爭時期，所以具有更高的可靠性；②相比于BiPi-TMAC，ERMH-TDMA降低了時隙請求的開銷，實時讓節點更新拓撲，提高了時隙請求成功率，從而提高了數據傳輸成功率；③FU-TDMA相比于ERMH-TDMA，使得網絡快速收斂，縮短了時幀長度，提高了拓撲更新頻率，鏈路實時性更高，從而提高了數據傳輸成功率；解決了時隙復用導致的沖突問題，提高了時隙復用率，增強了網絡可靠性，從而提高了成功率；通過在競爭階段，計算一跳鄰居優先級，降低了節點的碰撞率，增加了時隙請求成功率，進一步增強網絡可靠性，從而提高成功率。

圖10 數據傳輸成功率

4 結束語

針對無人機自組網控制時隙收斂慢，時隙沖突，時隙未充分利用及SMOP幀重傳易碰撞等問題，提出了一種名為FU-TDMA協議。機制一中心節點通過維護的全網拓撲圖，依據位置信息計算并行調度的節點。機制二中心節點消除了時隙分配時產生的沖突問題，挖掘出浪費的時隙并對此時隙公平的利用。機制三普通節點計算自己一跳鄰居內節點的優先級，降低了碰撞概率，保證了更高的可靠性。仿真驗證了FU-TDMA協議的有效性，可應用在無人機移動場景。在未來的研究中，可針對TDMA協議仍然存在的問題，深入挖掘時隙的復用性，進一步提高網絡性能。