基于動態(tài)優(yōu)先級表的TDMA時隙分配

劉慶剛

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

0 引言

移動Ad Hoc網(wǎng)絡(luò)由于其自組織，無中心，分布式[1]等特點現(xiàn)在越來越受到人們的關(guān)注，其廣泛應(yīng)用于搶險救災(zāi)、臨時會議、應(yīng)急通信等領(lǐng)域。網(wǎng)絡(luò)在通信過程中各節(jié)點既有通信終端的功能，又有路由功能[2-3]?；赥DMA的信道接入策略具有分組無沖突、最大分組時延有限等優(yōu)點，因此在Ad Hoc網(wǎng)絡(luò)的組網(wǎng)協(xié)議中大多采用基于TDMA的組網(wǎng)協(xié)議。

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

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

1 動態(tài)優(yōu)先級表的TDMA時隙分配算法

1.1 優(yōu)先級表介紹

這里給出一種8節(jié)點網(wǎng)絡(luò)的優(yōu)先級表。

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

表1 8節(jié)點優(yōu)先級表

1.2 DP_TDMA算法介紹

假設(shè)網(wǎng)絡(luò)中有 N個節(jié)點，編號為0～N-1，則DP_TDMA算法的時幀結(jié)構(gòu)如圖1所示。

圖1 DP_TDMA算法時幀結(jié)構(gòu)

1.2.1 聲明階段

聲明階段的主要作用是網(wǎng)內(nèi)節(jié)點根據(jù)本地待發(fā)送的業(yè)務(wù)量通知鄰居節(jié)點自己對時隙資源的需求情況。根據(jù)節(jié)點的業(yè)務(wù)量、業(yè)務(wù)的優(yōu)先級把節(jié)點對時隙的需求分為三種情況，分別為節(jié)點不需要使用時隙資源、需要使用一個時隙資源和需要使用多個時隙資源。

1.2.2 回復(fù)階段

經(jīng)過聲明階段后，各節(jié)點收到了鄰節(jié)點時隙的需求情況信息，接下來的回復(fù)階段各節(jié)點將收到的信息組成一個分組，在此稱為回復(fù)分組?；貜?fù)階段各節(jié)點在自己對應(yīng)的時隙依次發(fā)送回復(fù)分組，發(fā)送完成后各節(jié)點對自己一跳鄰域內(nèi)節(jié)點的時隙需求情況擴展到了兩跳范圍內(nèi)。

1.2.3 競爭階段

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

1.2.4 數(shù)據(jù)發(fā)送階段

經(jīng)過競爭階段后各節(jié)點獲知自己可以用來發(fā)送數(shù)據(jù)的時隙。由于競爭階段采用的是無沖突的競爭算法，因此發(fā)送過程中不存在沖突，不發(fā)送數(shù)據(jù)的節(jié)點處于接收狀態(tài)。

2 DP_TDMA算法仿真及性能分析

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

2.1 具體仿真實例時隙結(jié)構(gòu)

圖2為仿真中采用的固定TDMA時幀結(jié)構(gòu)，各節(jié)點在與自己節(jié)點號相同的時隙內(nèi)發(fā)送數(shù)據(jù)。

圖2 固定TDMA時隙結(jié)構(gòu)

圖3為仿真中采用的動態(tài)TDMA時幀結(jié)構(gòu)，其中聲明階段和回復(fù)階段的時隙長度為2 ms，各節(jié)點在聲明階段和回復(fù)階段固定使用各個時隙，數(shù)據(jù)發(fā)送階段的時隙長度為32 ms，各節(jié)點動態(tài)使用該階段的時隙。

圖3 動態(tài)TDMA時隙結(jié)構(gòu)

2.2 仿真結(jié)果及性能分析

2.21 固定優(yōu)先級表的情況

優(yōu)先級表采用表1。表2所示為仿真階段所有節(jié)點的業(yè)務(wù)類型情況，由該表可知所有節(jié)點每隔0.2s產(chǎn)生一個數(shù)據(jù)包，產(chǎn)生數(shù)據(jù)包的時間范圍為0～60s。

表2 8節(jié)點均衡全飽和業(yè)務(wù)

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

圖4 固定TDMA與動態(tài)TDMA吞吐量對比

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

表3 8節(jié)點非均衡全飽和業(yè)務(wù)

由圖 5可以看出當節(jié)點業(yè)務(wù)量不均衡時動態(tài)TDMA時隙分配算法在吞吐量方面較固定 TDMA時隙分配算法取得了較好的結(jié)果。

圖5 固定TDMA與動態(tài)TDMA吞吐量對比

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

總結(jié):由以上的仿真結(jié)果可知，對于節(jié)點業(yè)務(wù)量不均衡的網(wǎng)絡(luò)而言采用動態(tài)TDMA時隙分配算法將取得較好的結(jié)果。

2.2.2 采用動態(tài)優(yōu)先級表的情況

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

表4 8節(jié)點非均衡業(yè)務(wù)量

由圖6可見，采用動態(tài)優(yōu)先級表的動態(tài)TDMA時隙分配算法在吞吐量方面取得了較好的結(jié)果。

圖6 采用動態(tài)優(yōu)先級表和固定態(tài)優(yōu)先級表的動態(tài)TDMA算法吞吐量比較

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

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

3 結(jié)語

基于動態(tài)優(yōu)先級表的TDMA時隙分配算法在時隙分配過程中

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

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

[2]陳林星,曾曦,曹毅.移動Ad Hoc網(wǎng)絡(luò)——自組織分組無線網(wǎng)絡(luò)技術(shù)[M].北京:電子工業(yè)出版社,2006.

[3]張弛.基于TDMA的Ad Hoc網(wǎng)絡(luò)MAC協(xié)議比較[D].西安:西安電子科技大學,2007.

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

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

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