基于動態優先級表的TDMA時隙分配

劉慶剛

(海司信息化部，北京 100841)

0 引言

移動Ad Hoc網絡由于其自組織，無中心，分布式[1]等特點現在越來越受到人們的關注，其廣泛應用于搶險救災、臨時會議、應急通信等領域。網絡在通信過程中各節點既有通信終端的功能，又有路由功能[2-3]。基于TDMA的信道接入策略具有分組無沖突、最大分組時延有限等優點，因此在Ad Hoc網絡的組網協議中大多采用基于TDMA的組網協議。

文獻[4]提出了一種基于固定TDMA的無沖突動態時隙分配算法，即P_TDMA算法。該算法綜合了固定時隙資源分配和動態使用空閑時隙資源的優點，能保證業務傳輸的最小時延。但是P_TDMA算法沒有考慮各節點產生業務不均衡的情況，該算法決定競爭時隙資源成敗的唯一依據就是節點的優先級，而不能結合節點本身業務量的大小，因此不能充分利用時隙資源。 文獻[5]基于P_TDMA算法提出了一種改進型動態TDMA算法，即EP_TDMA算法，該算法事先給出一個固定的優先級表，該表在整個通信過程中保持不變，所以對于節點競爭時隙資源來說存在一定的不公平性。

由于以上原因本文提出了另一種基于固定TDMA的無沖突動態時隙分配算法,即基于動態優先級表的時隙分配算法，起名為DP_TDMA算法。

1 動態優先級表的TDMA時隙分配算法

1.1 優先級表介紹

這里給出一種8節點網絡的優先級表。

如表1所示，優先級表中每行和每列的元素都不相同。其中列元素不相同是為了節點競爭時隙時避免沖突；行元素不同是為了保證競爭時隙的公平性。若節點時隙需求情況存在很大差異，采用固定優先級表將存在一定的弊端。例如，若網絡中只有節點3可以讓出自己的主時隙(與節點號相同的時隙)供其余節點競爭使用，那么由于節點4在3號時隙處始終具有最低優先權，因此將永遠競爭不到時隙，存在一定的不公平性。鑒于以上原因，本文提出了基于動態優先級表的時隙分配策略。

表1 8節點優先級表

1.2 DP_TDMA算法介紹

假設網絡中有 N個節點，編號為0～N-1，則DP_TDMA算法的時幀結構如圖1所示。

圖1 DP_TDMA算法時幀結構

1.2.1 聲明階段

聲明階段的主要作用是網內節點根據本地待發送的業務量通知鄰居節點自己對時隙資源的需求情況。根據節點的業務量、業務的優先級把節點對時隙的需求分為三種情況，分別為節點不需要使用時隙資源、需要使用一個時隙資源和需要使用多個時隙資源。

1.2.2 回復階段

經過聲明階段后，各節點收到了鄰節點時隙的需求情況信息，接下來的回復階段各節點將收到的信息組成一個分組，在此稱為回復分組。回復階段各節點在自己對應的時隙依次發送回復分組，發送完成后各節點對自己一跳鄰域內節點的時隙需求情況擴展到了兩跳范圍內。

1.2.3 競爭階段

基于動態優先級表的競爭策略的基本思想:在時隙競爭過程中決定時隙競爭獲勝方的唯一因素是節點在優先級表中的優先級，由于優先級表中的所有列元素不同，因此每次競爭只可能有一個贏家；在算法的運行過程中優先級表是變化的，變化的時間間隔可以根據具體的情況而定，如可以根據時隙的個數而定，也可以根據具體的時間間隔而定。

1.2.4 數據發送階段

經過競爭階段后各節點獲知自己可以用來發送數據的時隙。由于競爭階段采用的是無沖突的競爭算法，因此發送過程中不存在沖突，不發送數據的節點處于接收狀態。

2 DP_TDMA算法仿真及性能分析

DP_TDMA算法的仿真采用OPNET仿真軟件[6]。

2.1 具體仿真實例時隙結構

圖2為仿真中采用的固定TDMA時幀結構，各節點在與自己節點號相同的時隙內發送數據。

圖2 固定TDMA時隙結構

圖3為仿真中采用的動態TDMA時幀結構，其中聲明階段和回復階段的時隙長度為2 ms，各節點在聲明階段和回復階段固定使用各個時隙，數據發送階段的時隙長度為32 ms，各節點動態使用該階段的時隙。

圖3 動態TDMA時隙結構

2.2 仿真結果及性能分析

2.21 固定優先級表的情況

優先級表采用表1。表2所示為仿真階段所有節點的業務類型情況，由該表可知所有節點每隔0.2s產生一個數據包，產生數據包的時間范圍為0～60s。

表2 8節點均衡全飽和業務

從圖4可以看出，當網絡中的節點業務量均勻時采用固定TDMA的時隙分配算法在網絡吞吐量和端到端時延方面取得了較好的結果。

圖4 固定TDMA與動態TDMA吞吐量對比

原因分析:由于全網節點都達到了飽和業務量，因此節點都需要使用主時隙發送數據。對于固定TDMA來說，所有的時隙用來發送數據，無浪費的時隙資源；但是對于動態TDMA來說由于算法的前兩個階段用于節點使用時隙需求的交互，在節點都達到飽和傳輸時，時隙分配的結果是各個節點只能使用自己的主時隙，因此這種情況下前兩個階段相對于同等業務情況下的固定TDMA算法來說浪費了時隙資源，所以在各節點飽和傳輸的情況下動態TDMA算法相對于固定 TDMA算法來說性能較為拙劣。表3所示為仿真階段所有節點的業務類型情況，由該表可知0～3號節點每隔0.2s產生一個數據包，達到飽和傳輸狀態，4～7號節點每隔0.6 s產生一個數據包，沒有達到飽和傳輸狀態，產生數據包的時間范圍為0～60s。

表3 8節點非均衡全飽和業務

由圖 5可以看出當節點業務量不均衡時動態TDMA時隙分配算法在吞吐量方面較固定 TDMA時隙分配算法取得了較好的結果。

圖5 固定TDMA與動態TDMA吞吐量對比

結果分析:由于網絡節點中0、1、2、3號節點業務量處于飽和狀態，若只使用主時隙發送數據將造成數據包的積壓；節點4、5、6、7每隔0.6 s產生一個數據包，時間間隔較長不會造成數據包的積壓。對于固定TDMA時隙分配算法而言，雖然0、1、2、3號節點存在數據包的積壓，4、5、6、7號節點存在主時隙空閑的情況，但是業務量大的節點不能使用業務量小的節點空閑出來的時隙，造成時隙資源的浪費；對于動態TDMA而言業務量大的節點可以占用業務量小的節點的主時隙，充分利用了時隙資源，因此在節點業務量不均衡的情況下就吞吐量而言動態TDMA算法效果較好。

總結:由以上的仿真結果可知，對于節點業務量不均衡的網絡而言采用動態TDMA時隙分配算法將取得較好的結果。

2.2.2 采用動態優先級表的情況

接下來的仿真中采用動態優先級表代替之前的固定優先級表。表4所示為仿真階段所有節點的業務類型情況，由該表可知所有節點的業務量均不相同，這樣是為了充分保證產生數據包的隨機性，產生數據包的時間范圍為0s到仿真結束的時間段內。

表4 8節點非均衡業務量

由圖6可見，采用動態優先級表的動態TDMA時隙分配算法在吞吐量方面取得了較好的結果。

圖6 采用動態優先級表和固定態優先級表的動態TDMA算法吞吐量比較

結果分析:采用固定優先級表行和列的所有元素均不相同，取一個固定優先級表1加以詳細分析。

從表1可以看出，雖然各個節點對所有時隙的優先權綜合考慮的情況下看似是公平的，但是存在這種情況，即有的節點時隙可能存在長期空出的情況。舉例說明如下:比如0號時隙長期空出，若此時1、2號節點需要長期競爭0號時隙，根據以上優先級表可以看出，在節點1、2業務量相當的情況下，1號節點將在競爭中長期處于優勝的地位，這樣對于業務量相當的2號節點來說是不公平的，可以稱這種情況為同等業務量情況下個別節點的時隙壟斷。當加入動態優先級表以后各節點對各時隙的優先級處于不斷地變化之中，打破了節點對時隙的壟斷，增進了公平，進而增加了網絡的吞吐量。

3 結語

基于動態優先級表的TDMA時隙分配算法在時隙分配過程中

避免了節點對某些時隙資源存在的壟斷性，保證在時間維上各節點對所有時隙資源競爭的公平性，進而提高了時隙資源的利用率。

[1]吉彬,蘇旸.基于哈希函數的動態TDMA時隙分配研究[J].通信技術,2012,45(08):47-49.

[2]陳林星,曾曦,曹毅.移動Ad Hoc網絡——自組織分組無線網絡技術[M].北京:電子工業出版社,2006.

[3]張弛.基于TDMA的Ad Hoc網絡MAC協議比較[D].西安:西安電子科技大學,2007.

[4]彭革新,謝勝利,陳彩云.一種基于固定TDMA的無沖突動態時隙分配算法[J].信息安全與通信保密,2005(11):116-121.

[5]聶建耀,許勇.一種應用于Ad Hoc網絡的改進型TDMA動態時隙分配算法[J].移動通信,2008(10):83-86.

[6]丁銳,鄭龍,王玉文,等.動態TDMA時隙分配算法在數據鏈中的仿真[J].通信技術,2011,44(02):105-107.