HTDMA協議自協調分布式運行機制研究*

魏小龍,李建海,楊海東

（空軍工程大學 工程學院，陜西 西安710038）

移動Ad Hoc網絡由于抗毀性和分布式等特點，得到了越來越廣泛的應用，不斷有新的MAC協議被提出，以適應不同的應用環境。動態時隙混合類協議（HTDMA）[1]一般先通過碰撞回避[2]、虛擬載波監聽[3]等方式探測網絡的局部拓撲信息，據此接入新節點，同時保留現有節點的傳輸安排，這種方式降低了大量的競爭開銷，更易為Ad Hoc網絡提供QoS保障。國內外已提出多種動態時隙混合類TDMA協議。在參考文獻[4]中提出一種集總式消除沖突的HTDMA協議——CCS-QR協議，它在一個控制時隙內將多個發射節點的接入請求集中處理，從而預約多個數據分組，之后再根據酬金類優先級算法和接入順序分配數據時隙。它具有平均時延小、吞吐量穩定等優點，很適合為實時業務提供QoS保障，但卻不能完全支持分布式運行。這類問題還廣泛存在于非耦合式HTDMA協議中[5]。

1 分布式運行約束條件

在CCS-QR協議中,控制時隙只完成虛擬載波監聽，并不為節點分配數據時隙,這種完全解耦的業務關系，減少了很多控制開銷。但其帶來另一個問題是，如果不提前發送時隙分配表，在數據時隙內由各節點根據優先級確定發送次序，則節點之間就不能相互協調地發送數據分組，就會引發沖突。

CCS-QR協議的數據時隙如圖1所示，結合圖2，例如在第1個數據時隙內，兩跳范圍內業務①②③會同時發送，而相互沖突導致失敗。原因是分布式網絡結構下，節點覆蓋范圍有限，無法得到所有節點的業務信息，所以每個節點所維持的預約序列都不相同[6]。

構建此問題的數學模型可以得到分布式Ad Hoc網絡正常通信的制約條件。根據圖2，可以用一個N×N的二維矩陣C=Cij來表示網絡拓撲結構,其中N=|V|為網絡中節點個數：

假設一個時幀劃分為M個時隙，一個時幀內每個節點至少分配到一個時隙，用M×N二維矩陣X=Xmi來表示時隙分配方案，其中

綜上可以將時隙分配問題規劃為一個數學模型：

目標函數為：min M and max ρ

約束條件為：

式(4)中的第一個約束條件表示一個時幀內節點至少分配一個時隙，第二個約束條件表示相距一跳的節點不能分配同一時隙，第三個約束條件表示兩個節點與同一節點相距一跳時不能分配同一時隙。以上說明，如果要滿足目標函數，無沖突發送數據，則必須保證相距兩跳范圍內的節點分配不同的時隙。

2 分布式隊列運行機制與分析

本文針對解耦關系的HTDMA，提出一種自協調分布式運行解決方案。下面對圖2所示的網絡模型和CCS-QR協議[4]進行分析和說明。

在圖2中，網絡由14個節點組成，實線表示兩個節點在對方覆蓋范圍內，箭頭表示兩個節點已在信令時隙完成數據時隙的預約，序號表示節點發送RTS/CTS分組的順序，為了簡化模型，省略了CCS-QR協議里優先級的表達。

2.1 業務管理樹算法原理

定義1：各個發射節點將所有兩跳范圍內的發送業務排成預約隊列，稱為不完全隊列,用Ci={ci-a,ci-b…ci}表示，Li為不完全隊列的長度。

定義2：根據協議安排，把控制時隙里允許接入的最大業務量按照優先級或接入次序進行排隊，稱之為完全隊列，用 Call={c1,c2…cn}表示，Lall為完全隊列的長度。

定義 3：設 Ci為節點 i的不完全隊列，Ni為節點 i在Ci中的序號，每當Ci中的一個節點發送了相應的數據業務，有 Li=Li-1，則稱使 Li=Ni-1的節點為節點 i的業務觸發節點，其相應的數據業務稱為觸發業務，將此時節點i的業務稱為待發業務。

定義4：將所有發送業務按照預約順序的方向排成隊列，該隊列會從觸發業務和待發業務處產生樹形結構，稱它為業務管理樹，其模型如圖3。業務管理樹的長度Lall等于所有業務發送完畢所需時隙的個數。

當某個業務同時作為兩個預約隊列中不同節點的觸發業務時，業務樹將產生分支結構，分支點位于當前業務之后，即某兩個待發業務之前；當不同分支的兩個節點同時作為某個業務的觸發業務時，業務樹將產生匯聚結構，匯聚點位于當前業務之前。

業務樹出現分支意味著將有多個子序列同時發送數據，而業務樹的匯聚表示在某個節點接入信道前，其預約隊列中同時有多個節點發送了數據。

前面已經通過數學模型論證，協議只需要將發射節點兩跳范圍之內的業務進行協調就可以防止此類沖突的發生。而兩跳之內的節點必處于同一業務樹分支當中，業務樹中不同分支上的節點至少相距兩跳以上，不在同一分支的節點可以同時隙發送業務,發送次序為Li。

2.2 算法描述

一個業務管理樹運行過程面向業務序列，而不是節點。具體工作過程為：

(1)收集發射狀態（Collection Phase）：在控制時 隙，通過對所有RTS分組和對應CTS分組的監聽，接收節點將所有相鄰發射節點納入自身隊列，發射節點也將相應接收節點的所有相鄰發射節點納入自身隊列。大多數HTDMA協議都能滿足此條件。

(2)接入順序表達（Sequence Phase）：此階段，依據協議里優先級設置和節點的接入次序為每項業務分配權重，即發送次序，并由此產生一個相同的完全隊列，包含所有業務信息。

(3)隊列形成（Establishing Phase）：在此階段，節點依據已得到兩跳范圍內其他節點的發射狀態來形成不完全預約隊列，這個隊列只關心發送次序在自己之前的業務。

(4)確認發送次序（Approval Phase）：根據業務管理樹算法，得到不完全隊列的補集，并將自身不完全隊列接入自己的觸發節點，業務將在不同分支間并行傳輸，而業務在不完全隊列中的次序即為發送次序。

2.3 算例分析

經過隊列調整后，各節點的預約隊列分別如表1所示。在此為了便于說明，隊列中業務序列按其序號排列。

根據業務樹算法，在各預約隊列中，只有當序列中排在前面的所有節點都發送了數據，當前節點才能發送數據。得到整個系統的業務發送次序如圖2箭頭表示信道使用權的傳遞方向。

表1 圖2中各發射節點所維護的預約隊列

因此，對于圖2的模型，分布式隊列的路徑可以用圖 4(a)、(b)所示的業務樹來表示。

對照圖2可以看出，在圖4中的業務樹中，不同分支上的業務可以在同時隙發送，而不引起分組碰撞。如圖4(a)中的業務②和業務③，以及圖4(b)中的業務④和業務③。

對照圖1，從圖5新業務的發送次序上看，在兩組兩跳節點間，數據發送無沖突，空間可復用。可見，通過業務樹管理算法，節點能夠依據自身在隊列中的次序依次接入信道。這種機制完全可以代替預約時隙表，可以在不增加任何協議開銷的情況下，實現節點的自協調、無沖突的分布式傳輸。

3 仿真實驗

為了進一步驗證業務樹算法在改善分布式網絡性能中起到的作用，通過網絡仿真軟件OPNET，對該算法使用前后 CCT—QR協議/DCT—QR協議（Distributed CCT—QR）的丟包率和吞吐量進行了仿真和對比。

仿真網絡環境參數和協議參數見表2。

表2 仿真參數表

3.1 吞吐量分析

圖6顯示了不同網絡負載下三種協議的吞吐量變化曲線。從圖中可以看出,CSMA/CA協議網絡吞吐量較低，這是由于競爭接入產生沖突所導致；而CCT—QR協議基于預留方式分配資源，產生的沖突很小，且控制開銷不大，所以網絡吞吐量較高；DCT—QR協議由于消除了CCT—QR協議數據時隙內的沖突，所以吞吐量更高且更穩定。但由于接入容量有限，所以在網絡載荷增多的情況下，吞吐量會出現飽和。

3.2 丟包率分析

圖7顯示了兩種協議的數據包丟失情況。當網絡負載并不高時，CCT—QR協議和改進后的DCT—QR協議的丟包率相當。但當輸入量達到一定值時(480 packet/s)，分布式運行機制就會體現出它的作用，它消除了業務密集后帶來的分組碰撞，降低了原協議的丟包率，但當業務量超過控制時隙容量時，丟包率將無可避免地增加。

本文提出了解決Ad Hoc網絡非耦合HTDMA協議分布式運行沖突的自協調式的業務管理樹算法，通過舉例分析和仿真實驗可以看出，該算法能夠達到預期效果。但這種算法在復雜網絡環境下，會增加分組時延，這將是下一步研究工作的重點。

[1]Li Wei,Wei Jibo,Wang Shan.An evolutionai-dynamic TDMA slot assignment protocol for Ad Hoc networks[C].IEEE Communications Society subject matter experts for publication in the WCNC 2007 proceedings,2007:138-142.

[2]嚴少虎，卓永寧，吳詩其,等．IEEE 802.11 DCF中帶優先級的退避算法[J]．電子與信息學報，2005，27(8):1315-1319．

[3]KAYNIA M,JINDAL N.Improving the performance of wireless Ad Hoc networks through MAC layer design[C].IEEE transactions on wireless communication:January 2011.

[4]楊海東，李建海，鄧勇.采用集總式沖突消除算法的Ad Hoc網絡MAC協議[J].系統工程與電子技術,2009,31(5):1241-1245.

[5]葉林容，余敬東．基于 TDMA的 Ad Hoc網絡MAC協議研究[D].成都：電子科技大學,2011．

[6]FULLERTON P S.Dynamic control slot scheduling algorithm for TDMA based mobile Ad Hoc networks[C].Military Communications Conference,2008:1-7.