TDMA 多跳網絡多接口多信道設計資源優化分配方法*

王亞茜，毛建兵，田 爽，張 浪

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引言

多跳無線Ad Hoc 網絡具備無中心、自組織的特點，無需架設固定的基礎設施，可以快速鋪開，自行完成網絡的組建，具備較強的機動性、靈活性和抗毀性，可以廣泛應用于戰場通信、應急救災通信等場景。

根據節點工作信道數的不同，無線Ad Hoc 網絡MAC 協議可以分為單信道MAC 協議和多信道MAC 協議。隨著無線Ad Hoc 網絡用戶容量、信息吞吐量等需求的不斷提升，采用單信道設計越來越難以滿足無線Ad Hoc 網絡大規模、多樣化業務互聯的應用需求，而采用多信道是解決以上需求與性能之間矛盾的重要手段之一。但是，多信道的使用將帶來更高的頻譜占用消耗，不適用于無線頻譜資源稀缺的場景。

多信道Ad Hoc 網絡MAC 協議按節點配置接口數目的不同，可以分為單接口多信道MAC 協議和多接口多信道網絡MAC 協議。單接口多信道MAC協議有基于跳頻的多信道MAC 協議（Slotted Seeded Channel Hopping，SSCH）[1]和基于時隙劃分的MAC 協議（Multi-channel MAC，MMAC）[2]等。采用多接口多信道技術，可以使得相鄰節點選用不同的信道，從兩個方面提高網絡的理論吞吐量。一方面，多信道多接口可以使一個節點同時進行收發工作，而不是時分復用，以加倍節點的吞吐量；另一方面，利用多接口多信道可以通過給相鄰節點分配不同的發送或接收信道，避免相鄰節點的共信道干擾，消除隱藏節點和暴露節點問題，進而提高網絡的吞吐量。多接口的使用雖然能提高多信道資源的利用率，但也會對硬件設計帶來更高的要求，且成本較高。多接口多信道MAC 協議有動態信道分配（Dynamic Channel Assignment，DCA）協議[3]和基于主信道分配的MAC（Primary Channel Assignment based MAC，PCAM)協議[4]等。

信道資源調度控制是MAC 層設計的主要功能之一。目前，信道資源調度技術主要分為兩類：一類是基于競爭的信道調度，如典型的帶有沖突避免的載波偵聽多路訪問（Carrier Sense Multiple Access With Collision Avoidance，CSMA/CA）；另一類是基于分配的信道調度，如時分復用多址接入（Time Division Multiple Access，TDMA）。基于競爭的信道調度實現簡單、可靠性高、擴展性好、便于分布式實現，也有研究將CSMA/CA 擴展應用到多接口多信道的無線Mesh 網絡當中[5]。但是，基于CSMA/CA 的調度存在隱藏終端和暴露終端的問題，在多跳Ad Hoc 網絡應用中因為其保守的設計而降低了網絡吞吐量。基于TDMA 的信道調度在理想實現的條件下不會發生MAC 層沖突，因為每個節點所分配的時隙不會和它的干擾節點沖突。在業務流穩定的網絡中，TDMA 調度能夠獲得更高的網絡通信容量。此外，TDMA 方式采用的時分結構適合于有時延限制的傳輸，相關的接入公平性、流量控制及預留帶寬等QoS 目標也更容易實現。目前，TDMA 作為一種有效的多址接入方式，廣泛應用于無線Ad Hoc 網絡中。

但是，TDMA 調度算法設計面臨著諸多挑戰，尤其是對多接口多信道的無線Ad Hoc 網絡，尚無統一的協議標準。本文針對多接口多信道無線Ad Hoc 網絡，提出一種基于TDMA 的分布式信道資源動態分配調度方法，適用于無線Ad Hoc 網絡無中心、拓撲動態變化的情形。通過對信道資源采用面向節點和面向鏈路兩者相結合的混合分配機制，在廣播和單播數據傳輸的資源使用上更有針對性，提高了資源利用效率，以適應無線Ad Hoc 網絡日益增大的網絡規模和吞吐量需求。此外，作為多接口多信道網絡的特例，算法設計同樣支持接口數退化為一的單接口條件和信道數退化為一的單信道條件。

1 TDMA 信道幀結構

TDMA 信道幀結構如圖1 所示，將時間按相等的幀長劃分為一個個信道幀，每個信道幀又劃分為L+M 個時隙，每個時隙根據信道的不同劃分為多個時頻資源。后面在不引起歧義的情況下，也將時頻資源稱之為時隙。

網絡中的節點工作在一組正交的信道C0～Cn上，將這組正交的信道稱之為信道集，信道C0同時兼任控制信道。信道幀中時隙由Beacon 信令時隙和Data 數據時隙組成。Beacon 時隙工作在信道C0上，Data 時隙工作在信道C0～Cn上。

接口使用方面，在Beacon 時隙所處時段節點一個接口固定工作在控制信道上，執行Beacon 時隙收發。該接口其余時段以及剩余接口可根據需要調度工作在任一信道上，執行Data 時隙收發。

網絡中的節點唯一無沖突地預分配一個Beacon時隙，用于監聽所有鄰居和時隙的分配情況，同時用于分配Data 時隙進行數據發送和Data 時隙使用結束后的釋放等。

圖1 TDMA 信道幀結構

Data 時隙通過本節點占用的Beacon 時隙與鄰居進行協商申請動態分配，并可在兩跳外復用同一時隙。Data 時隙分配支持面向節點和面向鏈路的按需分配使用方式，用于節點通信有效載荷的發送，并在使用結束后被釋放。

2 信道資源動態分配機制

2.1 分配策略

節點可以采用兩種方式向其鄰居節點傳輸數據分組。第一種方式為面向節點分配資源，并采用一個發射機向其所有的鄰居廣播傳輸一次。第二種方式為面向鏈路分配資源，傳輸節點只可向一個特定的鄰居進行通信，其他節點可能無法保證其正確接收數據。面向節點的資源分配和傳輸特別適合于如地址解析和群組通告信息傳輸之類的廣播應用，而面向鏈路的資源分配和傳輸則更有助于支持大數據量的點對點單播業務流的傳輸。在兩跳鄰域內，單一的面向節點分配策略只允許有一個激活的無線發射機，而單一的面向鏈路或兩者混合的分配策略則可以激活多個發射機。如圖2 所示，當節點1 在信道C1發送時，它的鄰居節點需要做好接收準備，因此不允許節點1 兩跳鄰域內有節點在任何信道上以面向節點的方式激活發射機進行發送，但允許其兩跳鄰域內節點8、9 在另一信道C2上以面向鏈路的方式激活發射機進行發送。此外，當節點8 發送時，它的接收節點是節點7，與其他鄰居節點無關，因此節點9 可以使用與之相同的信道在同一時間向別的節點進行發送。所以，本文的分配策略采取面向節點的分配+面向鏈路的分配兩者相結合的混合分配策略，以分布式按需分配算法來實現TDMA 多跳網絡應用中共存共享的廣播和單播兩類業務。

圖2 面向節點和面向鏈路混合分配傳輸

2.2 分配原則

MAC 層信道資源管理區分統計節點廣播以及到不同目的節點的單播業務量，節點根據統計的業務量大小或是QoS 業務流顯示指定的帶寬需求，對Data 時隙進行按需動態分配。

信道資源動態分配遵循以下原則：

（1）節點不能選擇本節點或目的節點接口已使用的時隙；

（2）節點需要有空閑的接口調度工作在相應分配的時隙上進行發送或是接收；

（3）對特定時隙，節點不能選擇目的節點和自己正在該時隙使用的信道集里的頻率；

（4）對特定時隙，節點不能選擇所有一跳鄰居節點正在該時隙接收使用的信道集；

（5）對特定時隙，節點不能選擇目的節點的所有一跳鄰居節點正在該時隙發送使用的信道集。

（6）沖突避免原則如下：①對于不同的分配策略，遵循面向節點的時隙分配優先級高于面向鏈路的時隙分配的原則；②相同分配策略的時隙沖突采用hash 函數協調分配資源，以幀號/時隙號/頻率號/節點ID 作為輸入參數進行hash 計算，以hash 值最大/最小者取得競爭獲勝，使不同的時頻資源分配產生變化，提高信道資源使用的公平性。

針對單播方式的業務傳輸，算法為其分配面向鏈路的資源，目的節點為特定的接收節點；對于廣播方式的業務傳輸，算法為其分配面向節點的資源，目的節點為其所有的一跳鄰居節點。無論是面向鏈路還是面向節點的資源分配策略，算法設計都只需要遵從上述動態分配原則，即可同時實現兩者混合的分配策略，只是兩者對原則（1）、原則（3）和原則（5）中的目的節點定義不同而已。

2.3 資源申請流程

（1）在N-1 時幀，根據本節點到各個目的節點的業務速率和隊列堆積情況，估計需要的Data 時隙數。廣播業務作為一種到達特殊目的節點的業務，按相同的算法估計需要的時隙數。

（2）選擇本節點、目的節點均有空閑的時隙，空閑定義等同于2.2 中原則（1）～原則（5）；廣播發送節點需選擇本節點、所有一跳鄰居節點均有空閑的時隙。

（3）在N時幀將選擇的時隙封裝人Beacon 分組時隙申請域，發Beacon 通告。

（4）一跳鄰居節點收齊N時幀Beacon 通告后進行沖突處理，并更新本地資源狀態表。

（5）一跳鄰居節點在N+1 時幀Beacon 分組中通告對申請的應答。

（6）本節點收齊N+1 時幀Beacon 通告后確認本節點對時隙的占用/退避情況，并更新本地的資源分配表。

（7）節點在N+2 時幀開始按照新的資源分配表占用相應時隙。

2.4 沖突調解流程

通過Beacon 時隙對Data 時隙進行申請時，因為Data 時隙采用“申請—應答—占用/退避”的過程進行分配，故這類沖突可通過應答階段予以解決。沖突可以分為兩種情況：一是時隙沖突，二是接口沖突。可以通過Beacon 分組的設計和一定的沖突調解算法進行完全的調解。

節點每幀發起或收到網絡中其他節點發起的資源申請，節點每幀對每個時隙均動態記錄以下4 個表項信息。

（1）本節點發送申請記錄表ST，如表1 所示。

表1 本節點發送申請記錄表ST

若本節點在某時隙、某信道發起申請，則該時隙、信道對應的表項標志置起。

（2）鄰節點發送（目的節點為本節點）申請記錄表NT1，如表2 所示。

表2 鄰節點發送申請記錄表NT1

本節點收到鄰節點Beacon 消息中若鄰節點發起發送申請且目的節點為本節點，則將該鄰節點的節點號記錄入其申請占用的時隙、信道對應的NT1表項中，同時該時隙、信道對應的NT1 表項的“申請鄰居總數”加1。

（3）鄰節點發送（目的節點不為本節點）申請記錄表NT2。NT2 表與NT1 表類似，區別僅在于其記錄目的節點不為本節點的鄰節點發送申請。

（4）處理結果表PR，如表3 所示。

表3 處理結果表PR

本節點完成沖突處理后，若本節點在某時隙、信道收，則該時隙、信道對應的PR 表項的“本節點收狀態標志”置起，同時在“本節點處理結果”記錄源節點號。若本節點在某時隙、信道不收，“本節點收狀態標志”不置起，“本節點處理結果”記錄0。

節點根據上述表項記錄的信息進行沖突處理，圖3 為沖突處理的算法設計。

（1）初始化時隙號i=0；

（2）若i＜M（其中M為一個信道幀中的時隙數），則執行（3），否則沖突調解結束；

（3）初始化信道號j=0；

（4）若j＜C（其中C為信道數），則執行（5）；否則，i=i+1，并重新執行（2）；

圖3 沖突處理算法設計

（5）若本節點在時隙i接口有剩余，則執行（6），否則處理結果表信道j至信道C-1 對應本節點收狀態標志不置起，本節點處理結果置0，i=i+1，并重新執行（2）；

（6）若本節點在時隙i、信道j申請發送，執行（7），否則執行（8）；

（7）將本節點記錄入時隙i的NT1 表中信道j對應表項，同時申請鄰居總數相應加1，其中NT1 表包括鄰節點發送且目的節點為本節點的申請記錄；

（8）若時隙i的NT1 表中信道j對應申請鄰居總數大于0，則執行（9），否則PR 表信道j對應本節點收狀態標志不置起，本節點處理結果置0，j=j+1，并重新執行（4）；

（9）對NT1 和NT2 表中記錄的所有鄰節點的節點ID 計算hash 值，其中NT2 表包括鄰節點發送且目的節點不為本節點的申請記錄；對計算的hash值進行排序，將hash 值最大的節點ID 記錄到處理結果表的本節點處理結果；

（10）若hash 值最大的節點為NT1 表中記錄的節點且不為本節點，則執行（11），否則PR 表信道j 對應本節點收狀態標志不置起，j=j+1，并重新執行（4）；

（11）PR 表信道j對應本節點收狀態標志置起，本節點時隙i接口剩余數減1，j=j+1，并重新執行（4）。

2.5 資源釋放流程

Data 時隙資源的釋放分為主動釋放和被動釋放兩種。

2.5.1 主動釋放

主動釋放分為3 種情形。

情形1：本節點空閑時隙釋放，發起方為本節點，主動釋放本節點占用的多余時隙，鄰節點收到釋放通告后，也將時隙的占用記錄清除。流程如下：

（1）在N-1 時幀若節點存在需釋放的空閑時隙，則選擇待釋放的時隙，更新本地維護的本節點時隙占用記錄；

（2）在N時幀將選擇釋放的時隙封裝入Beacon 分組時隙釋放域，發Beacon 通告。

（3）鄰節點收Beacon 通告，解析Beacon 分組中的時隙釋放信息，更新本地維護的鄰節點時隙占用記錄。

情形2：鄰居丟失時隙釋放，節點標記某個鄰節點占用了某些時隙，但該鄰節點可能因為各種原因從本節點的鄰居表中刪除，此時本節點需要初始化本節點維護的該鄰節點的資源占用記錄，完成相應資源的釋放。鄰居丟失時隙釋放發起方為本節點，主動釋放丟失鄰居占用的時隙，流程如下：

（1）在N時幀比較與N-1 時幀的鄰居表，若發現某鄰居丟失，設置等待超時時間為M個時幀。

（2）等待M個時幀，若該鄰居未恢復，進入步驟（3），否則退出。

（3）釋放標記鄰節點占用的時隙。

情形3：本節點時隙內部協調，節點需要申請新的時隙進行業務發送，但節點到該業務的目的節點A 的可用時隙或接口資源已耗盡，而節點已占用的時隙數又高于兩跳鄰域內節點的平均時隙數時，根據節點當前已占用時隙情況，可釋放部分用于向其他目的節點傳輸占用的資源，釋放后的這些資源可用于節點向目的節點A 發送業務。本節點時隙內部協調發起方為本節點，本質上這些資源還是由本節點繼續占用，只是從本節點的一個目的節點釋放給另一個目的節點，因此只需再次對這些資源進行時隙申請通告。通告新的目的節點，這樣舊的目的節點及其一跳鄰居知曉舊的目的節點不再在這些時隙上接收，新的目的節點及其一跳鄰居知曉新的目的節點將在這些時隙上接收，流程如下。

（1）在N-1 時幀選擇要協調目的節點的時隙。

（2）在N時幀將選擇協調時隙的相關信息封裝入Beacon 分組時隙申請域，發送Beacon 通告。

（3）后續流程同2.3 資源申請流程（4）～（7）。

2.5.2 被動釋放

被動釋放發生在節點需要申請新的時隙進行業務發送，但節點到該業務的目的節點的時隙或接口資源已耗盡時，若節點占用的時隙數低于兩跳鄰域內節點的平均時隙數，則節點可以發起時隙釋放申請，收到釋放申請的節點被動釋放相應時隙。被動釋放流程發起方為本節點，鄰節點收到釋放通告后，被動釋放占用的相應時隙。流程如下：

（1）選擇要申請釋放的時隙。

（2）將選擇申請釋放的時隙相關信息封裝入Beacon 分組的時隙釋放申請域，發送Beacon 通告。節點在發出釋放申請的同時，也相當于發起了占用這些時隙的通告，稱為時隙釋放/占用。

（3）鄰節點收到Beacon 通告，解析Beacon 分組中的時隙釋放申請域，一方面要進行資源釋放相關的操作，另一方面要進行時隙沖突檢查和調解。

（4）如果鄰節點在步驟（3）發現沖突，將沖突信息封裝入Beacon 分組中的時隙申請應答域，發Beacon 通告。

（5）兩跳鄰節點收Beacon 通告，解析時隙申請應答域中通告的沖突信息，如有需要則進行退避。

3 仿真驗證

利用MATLAB 平臺對所設計的多接口多信道的信道資源動態分配方法對信道利用率、空間復用率、信道成功接入率、信道沖突概率以及網絡一跳吞吐量等多個方面進行算法仿真分析，并對比本文提出方法所采取的混合分配策略與傳統單一的面向節點或面向鏈路的分配策略相互之間的性能差異。

為了比較本文采取的混合分配策略與單一的面向節點或面向鏈路的分配策略相互之間的性能差異，在動態場景下對3 種策略進行仿真比較。為方便描述，3 種分配策略分別將其簡稱為策略A、策略B 和策略C，如表4 所示。

表4 動態分配策略簡稱

仿真參數設定如表5 所示。節點單播業務的目的接收節點隨機在其一跳鄰居中產生，廣播業務的目的節點為其所有一跳鄰居。

表5 網絡仿真參數設定

初始仿真場景的網絡拓撲形態如圖4 所示。仿真過程中節點位置按照隨機確定的方向不斷移動，移動速率大小在范圍60～100 km/h 內隨機選取。仿真結果如圖5 所示。

圖4 仿真場景網絡拓撲

圖5 3 種分配策略仿真結果對比

對比結果可以看出，采用策略C，無論是在系統成功接入率、節點成功接入率，還是信道沖突概率方面，性能都優于另外兩種分配策略。表6 給出了動態場景下仿真不同分配策略獲得的關于平均系統成功接入率、平均節點成功接入率、平均信道沖突概率的統計平均值，也可得出相同的結論。

表6 不同策略部分指標對比

從圖5 的仿真結果中看到，在信道利用率、空間復用率以及一跳吞吐量方面，策略B 面向鏈路的分配策略要高于策略C，這是因為策略B 將廣播業務全部轉化為單播業務進行發送，而面向鏈路的資源分配占用比面向節點的資源分配更高效，因此其信道利用率和空間復用率更高，且策略B 中節點每次數據發送都計入一跳吞吐量，使得其一跳吞吐量隨之較高。實際應用中，廣播業務被轉化為到每個鄰居節點的單播發送，其實際傳輸效率非常低，因此盡管策略B 有更高的一跳傳輸吞吐量，但其在廣播/單播業務混合傳輸時的實際業務傳輸能力則較低。

4 結語

本文針對多接口多信道的無線Ad Hoc 網絡，提出了一種基于TDMA 的分布式信道資源動態分配調度方法。提出的信道資源動態分配方法支持網絡節點接口數及信道數的彈性可變，適用于無線Ad Hoc網絡靈活多樣的組網場景需求。從仿真結果來看，采用的信道資源面向節點和面向鏈路兩者相結合的混合分配機制，在廣播和單播數據分類傳輸的資源使用上更有針對性，提高了信道資源的利用效率。