《電子技術應用》
您所在的位置：首頁 > 通信與網(wǎng)絡 > 設計應用 > HTDMA協(xié)議自協(xié)調分布式運行機制研究
HTDMA協(xié)議自協(xié)調分布式運行機制研究
來源：電子技術應用2012年第8期
魏小龍, 李建海, 楊海東
空軍工程大學 工程學院，陜西 西安710038
摘要： 提出了一種適用于HTDMA協(xié)議的業(yè)務樹管理算法,，它可以在不增加任何控制開銷的情況下,，依靠RTS/CTS分組，通過節(jié)點間自身的相互協(xié)調實現(xiàn)整個網(wǎng)絡無沖突分布式運行。該機制可以代替預約時隙表的功能。以CCS-QR協(xié)議為例，詳細介紹了該機制的運行過程,。仿真結果表明,，該算法能夠有效降低CCS-QR協(xié)議的丟包率，并能提高網(wǎng)絡吞吐量,。
中圖分類號： TN929.5
文獻標識碼： A
文章編號： 0258-7998(2012)08-0109-03
Self adaptive mechanism for distributed operation of the HTDMA
Wei Xiaolong, Li Jianhai, Yang haidong
Engineering Inst, Air Force Engineering University, Xi′an 710038,， China
Abstract： This paper proposes a queuetree_control algorithm adapted uncoupled HTDMA protocol. It realizes the distributed network works without space division conflict through virtual carrier sense, which can substitute the reservation time table and don’t increase any control overhead. The algorithms are detailed in the paper through the example of CCS-QR protocol. Simulation result shows that queuetree_control algorithm can improve throughput and reduce the packet loss ratio.
Key words : distributed network; queuetree_control ;HTDMA ; CCS-QR protocol

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

1 分布式運行約束條件
    在CCS-QR協(xié)議中,控制時隙只完成虛擬載波監(jiān)聽，并不為節(jié)點分配數(shù)據(jù)時隙,這種完全解耦的業(yè)務關系,，減少了很多控制開銷,。但其帶來另一個問題是，如果不提前發(fā)送時隙分配表,，在數(shù)據(jù)時隙內由各節(jié)點根據(jù)優(yōu)先級確定發(fā)送次序,，則節(jié)點之間就不能相互協(xié)調地發(fā)送數(shù)據(jù)分組，就會引發(fā)沖突,。
    CCS-QR協(xié)議的數(shù)據(jù)時隙如圖1所示,，結合圖2，例如在第1個數(shù)據(jù)時隙內,，兩跳范圍內業(yè)務①②③會同時發(fā)送,，而相互沖突導致失敗。原因是分布式網(wǎng)絡結構下,，節(jié)點覆蓋范圍有限,，無法得到所有節(jié)點的業(yè)務信息,，所以每個節(jié)點所維持的預約序列都不相同[6]。

   式(4)中的第一個約束條件表示一個時幀內節(jié)點至少分配一個時隙,，第二個約束條件表示相距一跳的節(jié)點不能分配同一時隙,，第三個約束條件表示兩個節(jié)點與同一節(jié)點相距一跳時不能分配同一時隙。以上說明,，如果要滿足目標函數(shù),，無沖突發(fā)送數(shù)據(jù)，則必須保證相距兩跳范圍內的節(jié)點分配不同的時隙,。
2 分布式隊列運行機制與分析
    本文針對解耦關系的HTDMA,，提出一種自協(xié)調分布式運行解決方案。下面對圖2所示的網(wǎng)絡模型和CCS-QR協(xié)議[4]進行分析和說明,。
    在圖2中,，網(wǎng)絡由14個節(jié)點組成，實線表示兩個節(jié)點在對方覆蓋范圍內,，箭頭表示兩個節(jié)點已在信令時隙完成數(shù)據(jù)時隙的預約,，序號表示節(jié)點發(fā)送RTS/CTS分組的順序，為了簡化模型,，省略了CCS-QR協(xié)議里優(yōu)先級的表達,。
2.1業(yè)務管理樹算法原理
    定義1：各個發(fā)射節(jié)點將所有兩跳范圍內的發(fā)送業(yè)務排成預約隊列，稱為不完全隊列,用Ci={ci-a,ci-b…ci}表示,，Li為不完全隊列的長度,。
    定義2：根據(jù)協(xié)議安排，把控制時隙里允許接入的最大業(yè)務量按照優(yōu)先級或接入次序進行排隊,，稱之為完全隊列,，用Call={c1,c2…cn}表示，Lall為完全隊列的長度,。
    定義3：設Ci為節(jié)點i的不完全隊列,，Ni為節(jié)點i在Ci中的序號，每當Ci中的一個節(jié)點發(fā)送了相應的數(shù)據(jù)業(yè)務,，有Li=Li-1,，則稱使Li=Ni-1的節(jié)點為節(jié)點i的業(yè)務觸發(fā)節(jié)點，其相應的數(shù)據(jù)業(yè)務稱為觸發(fā)業(yè)務,，將此時節(jié)點i的業(yè)務稱為待發(fā)業(yè)務,。
    定義4：將所有發(fā)送業(yè)務按照預約順序的方向排成隊列，該隊列會從觸發(fā)業(yè)務和待發(fā)業(yè)務處產生樹形結構,，稱它為業(yè)務管理樹,，其模型如圖3。業(yè)務管理樹的長度Lall等于所有業(yè)務發(fā)送完畢所需時隙的個數(shù),。

    當某個業(yè)務同時作為兩個預約隊列中不同節(jié)點的觸發(fā)業(yè)務時,，業(yè)務樹將產生分支結構,，分支點位于當前業(yè)務之后，即某兩個待發(fā)業(yè)務之前,；當不同分支的兩個節(jié)點同時作為某個業(yè)務的觸發(fā)業(yè)務時,，業(yè)務樹將產生匯聚結構，匯聚點位于當前業(yè)務之前,。
    業(yè)務樹出現(xiàn)分支意味著將有多個子序列同時發(fā)送數(shù)據(jù),，而業(yè)務樹的匯聚表示在某個節(jié)點接入信道前，其預約隊列中同時有多個節(jié)點發(fā)送了數(shù)據(jù),。
    前面已經通過數(shù)學模型論證,，協(xié)議只需要將發(fā)射節(jié)點兩跳范圍之內的業(yè)務進行協(xié)調就可以防止此類沖突的發(fā)生。而兩跳之內的節(jié)點必處于同一業(yè)務樹分支當中,，業(yè)務樹中不同分支上的節(jié)點至少相距兩跳以上,，不在同一分支的節(jié)點可以同時隙發(fā)送業(yè)務,發(fā)送次序為Li。
2.2 算法描述


    一個業(yè)務管理樹運行過程面向業(yè)務序列,，而不是節(jié)點,。具體工作過程為：
    (1)收集發(fā)射狀態(tài)（Collection  Phase）：在控制時隙，通過對所有RTS分組和對應CTS分組的監(jiān)聽,，接收節(jié)點將所有相鄰發(fā)射節(jié)點納入自身隊列,，發(fā)射節(jié)點也將相應接收節(jié)點的所有相鄰發(fā)射節(jié)點納入自身隊列。大多數(shù)HTDMA協(xié)議都能滿足此條件,。
    (2)接入順序表達（Sequence Phase）：此階段,，依據(jù)協(xié)議里優(yōu)先級設置和節(jié)點的接入次序為每項業(yè)務分配權重，即發(fā)送次序,，并由此產生一個相同的完全隊列,，包含所有業(yè)務信息。
　(3)隊列形成（Establishing Phase）：在此階段,，節(jié)點依據(jù)已得到兩跳范圍內其他節(jié)點的發(fā)射狀態(tài)來形成不完全預約隊列,，這個隊列只關心發(fā)送次序在自己之前的業(yè)務。
　(4)確認發(fā)送次序（Approval Phase）：根據(jù)業(yè)務管理樹算法,，得到不完全隊列的補集，并將自身不完全隊列接入自己的觸發(fā)節(jié)點,，業(yè)務將在不同分支間并行傳輸,，而業(yè)務在不完全隊列中的次序即為發(fā)送次序。
2.3 算例分析
　經過隊列調整后,，各節(jié)點的預約隊列分別如表1所示,。在此為了便于說明，隊列中業(yè)務序列按其序號排列,。

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

    本文提出了解決Ad Hoc網(wǎng)絡非耦合HTDMA協(xié)議分布式運行沖突的自協(xié)調式的業(yè)務管理樹算法,，通過舉例分析和仿真實驗可以看出,，該算法能夠達到預期效果。但這種算法在復雜網(wǎng)絡環(huán)境下,，會增加分組時延,，這將是下一步研究工作的重點。
參考文獻
[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 中帶優(yōu)先級的退避算法[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網(wǎng)絡MAC協(xié)議[J]. 系統(tǒng)工程與電子技術, 2009,31(5):1241-1245.
[5] 葉林容,，余敬東．基于TDMA的Ad Hoc網(wǎng)絡MAC協(xié)議研究[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.

此內容為AET網(wǎng)站原創(chuàng),，未經授權禁止轉載。