基于哈希算法的動態TDMA時隙分配研究

吉 彬，蘇 旸

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

0 引言

Ad Hoc網絡是由無線通信設備組成的分布式網絡，它不需要基礎通信設施的支持，在通信過程中節點既有通信終端的功能,又有路由的功能[1-2]。Ad Hoc網絡中無線信道多點共享，時隙資源分配是Ad Hoc網絡的關鍵技術，關系到節點能否充分利用有限的信道資源，實現節點對時隙資源的公平競爭。動態TDMA信道接入協議具有分組無沖突、最大分組時延有界等優點，在無線通信系統中得到了廣泛應用。

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

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

1 HP_TDMA算法

1.1 TDMA時幀結構

假定無線網絡有N個節點，各節點可以與它的一跳相鄰節點直接通信。幀結構分為聲明階段、交互信息階段、競爭階段、信息發送階段。

圖1為HP_TDMA時幀結構。各部分分為N個子時隙，對應網絡中N個節點。信息發送階段各子時隙稱為各節點的主時隙。

圖1 HP_TDMA時幀結構

1.2 聲明階段

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

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

1.3 交互信息階段

經過聲明階段節點獲得相鄰節點時隙使用情況，隨后對獲得的時隙使用信息進行分組。交互信息分組分為分組類型、源節點號、節點狀態等部分。節點狀態表明節點收集到的在網節點對時隙資源的需求情況。

通過交互信息階段N個信息分組的發送，節點把一跳范圍內各節點對時隙資源的需求情況信息擴展到兩跳范圍內。兩跳范圍內各節點可以競爭使用無需時隙資源節點的時隙以及兩跳范圍外各節點的時隙。在此給出如圖2所示的一個網絡拓撲實例。

圖2 網絡拓撲

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

經交互信息階段后各節點獲得其他節點時隙需求情況如表1所示。

表1 交互信息階段后節點獲知的全網節點時隙需求情況

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

1.4 競爭階段

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

inline_smear函數使輸入值變換為一個不相關的哈希值，文獻[5]中論述了有關哈希函數計算節點競爭時隙時的公平性。

1.5 信息發送階段

信息發送階段，節點在獲得的時隙發送業務，無業務發送的節點處于監聽狀態。

2 算法性能分析

仿真場景如圖2所示。在此定義兩個參數，一個為總的可用時隙數，一個為時隙利用率。總的可用時隙數為一幀內總共可以發送數據的時隙總數量，若同一時刻多個節點有權發送數據則時隙數為發送數據節點數之和；時隙利用率為實際發送業務的時隙數量與總的可用時隙數的比值。

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

表2 算法性能對比

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

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

圖3 節點可用時隙數分配結果

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

3 結語

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

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

[2] 張弛.基于TDMA的Ad Hoc網絡MAC協議比較[D].西安：西安電子科技大學，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] 聶建耀，許勇.一種應用于Ad Hoc網絡的改進型TDMA動態時隙分配算法[J].移動通信，2008(10):83-86.

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

[6] 夏林英,張亞明,陳紹煒.戰術數據鏈網絡同步技術的改進方案[J].信息安全與通信保密,2007(05):74-75.

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