基于哈希算法的動態(tài)TDMA時隙分配研究

吉 彬，蘇 旸

(中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041)

0 引言

Ad Hoc網(wǎng)絡(luò)是由無線通信設(shè)備組成的分布式網(wǎng)絡(luò)，它不需要基礎(chǔ)通信設(shè)施的支持，在通信過程中節(jié)點既有通信終端的功能,又有路由的功能[1-2]。Ad Hoc網(wǎng)絡(luò)中無線信道多點共享，時隙資源分配是Ad Hoc網(wǎng)絡(luò)的關(guān)鍵技術(shù)，關(guān)系到節(jié)點能否充分利用有限的信道資源，實現(xiàn)節(jié)點對時隙資源的公平競爭。動態(tài)TDMA信道接入?yún)f(xié)議具有分組無沖突、最大分組時延有界等優(yōu)點，在無線通信系統(tǒng)中得到了廣泛應(yīng)用。

文獻(xiàn)[3]提出了一種基于固定TDMA的無沖突動態(tài)時隙分配P_TDMA算法。該算法綜合了固定分配和動態(tài)接入的優(yōu)點，具有最小時延保障。但是這種算法沒有充分考慮節(jié)點業(yè)務(wù)不均衡的情況，在競爭階段節(jié)點都按優(yōu)先級高低盡最大可能占有時隙，而不考慮自身的時隙需求，因此該算法不能充分利用時隙資源。文獻(xiàn)[4]在P_TDMA的基礎(chǔ)上提出了一種改進(jìn)型EP_TDMA算法，該算法在競爭階段采用給出的優(yōu)先級表決定誰是時隙競爭的贏家，由于優(yōu)先級表固定不變，所以該算法存在一定的不公平性。

鑒于以上原因提出了一種基于固定TDMA的無沖突動態(tài)時隙分配HP-TDMA算法。該算法通過聲明階段清晰的時隙需求劃分來避免不必要的時隙資源浪費。經(jīng)過交互信息階段各節(jié)點知悉兩跳范圍內(nèi)節(jié)點時隙的需求情況。在時隙競爭階段，根據(jù)哈希算法得出各競爭節(jié)點對可競爭時隙的優(yōu)先級順序表，優(yōu)先級順序表決定了節(jié)點對時隙的使用權(quán)。

1 HP_TDMA算法

1.1 TDMA時幀結(jié)構(gòu)

假定無線網(wǎng)絡(luò)有N個節(jié)點，各節(jié)點可以與它的一跳相鄰節(jié)點直接通信。幀結(jié)構(gòu)分為聲明階段、交互信息階段、競爭階段、信息發(fā)送階段。

圖1為HP_TDMA時幀結(jié)構(gòu)。各部分分為N個子時隙，對應(yīng)網(wǎng)絡(luò)中N個節(jié)點。信息發(fā)送階段各子時隙稱為各節(jié)點的主時隙。

圖1 HP_TDMA時幀結(jié)構(gòu)

1.2 聲明階段

聲明階段主要作用是各節(jié)點聲明自己時隙需求情況，使用時隙需求是基于節(jié)點業(yè)務(wù)量的情況。節(jié)點需要使用時隙則發(fā)送時隙使用通知分組。聲明分組由3部分組成，即類型、節(jié)點號和標(biāo)志位。標(biāo)志位由2比特組成，標(biāo)志位為00表示節(jié)無需使用時隙；標(biāo)志位為01表示節(jié)點需使用自己的主時隙；標(biāo)志位為10表示節(jié)點需要使用自己的主時隙和競爭額外時隙。

聲明階段通過節(jié)點使用時隙3種情況的劃分避免節(jié)點憑借高優(yōu)先級占有多個無用時隙資源的情況。

1.3 交互信息階段

經(jīng)過聲明階段節(jié)點獲得相鄰節(jié)點時隙使用情況，隨后對獲得的時隙使用信息進(jìn)行分組。交互信息分組分為分組類型、源節(jié)點號、節(jié)點狀態(tài)等部分。節(jié)點狀態(tài)表明節(jié)點收集到的在網(wǎng)節(jié)點對時隙資源的需求情況。

通過交互信息階段N個信息分組的發(fā)送，節(jié)點把一跳范圍內(nèi)各節(jié)點對時隙資源的需求情況信息擴展到兩跳范圍內(nèi)。兩跳范圍內(nèi)各節(jié)點可以競爭使用無需時隙資源節(jié)點的時隙以及兩跳范圍外各節(jié)點的時隙。在此給出如圖2所示的一個網(wǎng)絡(luò)拓?fù)鋵嵗?/p>

圖2 網(wǎng)絡(luò)拓?fù)?/p>

圖2中數(shù)字代表節(jié)點號，其中1、4節(jié)點為只需要使用自己主時隙的節(jié)點，6、7節(jié)點為不僅需要使用自己主時隙而且需要競爭額外時隙的節(jié)點，其余不需要使用時隙。

經(jīng)交互信息階段后各節(jié)點獲得其他節(jié)點時隙需求情況如表1所示。

表1 交互信息階段后節(jié)點獲知的全網(wǎng)節(jié)點時隙需求情況

表1中00表示節(jié)點不需要使用時隙；01表示只需使用主時隙；10表示不僅需要使用主時隙，而且需要競爭額外的時隙。

1.4 競爭階段

此階段節(jié)點擁有一個與其他節(jié)點不同的隨機種子，這里隨機種子為節(jié)點號。隨機種子與時隙號、時幀號進(jìn)行串接輸入名為 inline_smear的哈希函數(shù)生成一個哈希值，該哈希值最終決定誰是時隙競爭的贏家。若出現(xiàn)相同哈希值則取節(jié)點號小者為時隙競爭贏家。給出inline_smear函數(shù)：

inline_smear函數(shù)使輸入值變換為一個不相關(guān)的哈希值，文獻(xiàn)[5]中論述了有關(guān)哈希函數(shù)計算節(jié)點競爭時隙時的公平性。

1.5 信息發(fā)送階段

信息發(fā)送階段，節(jié)點在獲得的時隙發(fā)送業(yè)務(wù)，無業(yè)務(wù)發(fā)送的節(jié)點處于監(jiān)聽狀態(tài)。

2 算法性能分析

仿真場景如圖2所示。在此定義兩個參數(shù)，一個為總的可用時隙數(shù)，一個為時隙利用率?？偟目捎脮r隙數(shù)為一幀內(nèi)總共可以發(fā)送數(shù)據(jù)的時隙總數(shù)量，若同一時刻多個節(jié)點有權(quán)發(fā)送數(shù)據(jù)則時隙數(shù)為發(fā)送數(shù)據(jù)節(jié)點數(shù)之和；時隙利用率為實際發(fā)送業(yè)務(wù)的時隙數(shù)量與總的可用時隙數(shù)的比值。

文獻(xiàn)[4]提出的EP_TDMA算法在競爭階段基于一個固定優(yōu)先級表來展開對時隙資源的競爭，而HP-TDMA算法基于哈希函數(shù)計算節(jié)點對時隙資源的競爭結(jié)果?，F(xiàn)將兩種方法的計算結(jié)果加以對比，如表2所示。

表2 算法性能對比

由表2可以看出EP_TDMA算法分配時隙資源導(dǎo)致只需使用自己主時隙的節(jié)點占用過多時隙。EP_TDMA可用于發(fā)送的總的可用時隙數(shù)為9個，但有3個是浪費的，利用率為6/9=66.7%。只需使用自己主時隙的節(jié)點1和4分別占用了1、6號時隙和2、3、4號時隙，這必將導(dǎo)致網(wǎng)絡(luò)中部分業(yè)務(wù)量大的節(jié)點因為可用時隙被占用而不能傳輸業(yè)務(wù)。然而HP_TDMA算法的動態(tài)時隙分配給出了合理分配結(jié)果。1、4節(jié)點業(yè)務(wù)量不大，只分配了自己的主時隙。6、7節(jié)點因為業(yè)務(wù)量大分別分配了1、2、6和3、5、7等多個時隙。HP_TDMA算法給出可以利用的總的可用時隙數(shù)為8個，這8個時隙都有節(jié)點發(fā)送數(shù)據(jù)，利用率為100%。

由圖3可以看出只需使用自己主時隙的節(jié)點1、4在EP_TDMA算法中分別獲得2個和3個時隙，造成時隙資源的浪費，而在HP_TDMA算法中1、4節(jié)點只分配到主時隙。

圖3 節(jié)點可用時隙數(shù)分配結(jié)果

需使用額外時隙的節(jié)點6、7在EP_TDMA算法中共分得4個時隙資源，而在HP_TDMA算法中6、7節(jié)點共分得6個時隙資源，在整個時幀過程中EP_ TDMA算法分給所有節(jié)點實際使用的時隙數(shù)為6個，而HP_TDMA算法分給節(jié)點實際使用的時隙數(shù)為 8個，可已看出HP_TDMA算法分配的實際使用時隙數(shù)為EP_TDMA算法的8/6=1.33倍。因此使用HP_TDMA算法得出的分配結(jié)果是優(yōu)于EP_TDMA算法的。

3 結(jié)語

HP_TDMA算法在聲明階段通過清晰的時隙需求劃分避免時隙資源的浪費[5-7]，在競爭階段通過哈希算法公平的進(jìn)行時隙資源的競爭，為各節(jié)點公平的得到自己所需的時隙資源數(shù)創(chuàng)造了條件，因此采用基于哈希算法的動態(tài)TDMA時隙分配取得了較好的結(jié)果。但是，由于該算法每個時幀都要運行哈希函數(shù)來計算時隙競爭的贏家，使用HP_TDMA算法相比采用固定優(yōu)先級表的EP_TDMA算法增加了運算量，在網(wǎng)絡(luò)運行中將增加節(jié)點功耗。因此，HP_TDMA算法還有待做出進(jìn)一步的研究，以期獲得更好的結(jié)果。

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

[2] 張弛.基于TDMA的Ad Hoc網(wǎng)絡(luò)MAC協(xié)議比較[D].西安：西安電子科技大學(xué)，2007：1-12.

[3] PENG Gexin, XIE Shengli, CHEN Caiyun. A Collisionavoid Dynamic Slots Assignment Algorithm based on Fixed TDMA[J]. China Information Security,2005(11):115-120.

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

[5] 李翠然,謝健驪.移動自組網(wǎng)MAC協(xié)議的誤碼性能分析[J]. 通信技術(shù),2010,43(05):140-142.

[6] 夏林英,張亞明,陳紹煒.戰(zhàn)術(shù)數(shù)據(jù)鏈網(wǎng)絡(luò)同步技術(shù)的改進(jìn)方案[J].信息安全與通信保密,2007(05):74-75.

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