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

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

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

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

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

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

    本文提出了解決Ad Hoc網(wǎng)絡(luò)非耦合HTDMA協(xié)議分布式運(yùn)行沖突的自協(xié)調(diào)式的業(yè)務(wù)管理樹算法，通過舉例分析和仿真實(shí)驗(yàn)可以看出,，該算法能夠達(dá)到預(yù)期效果,。但這種算法在復(fù)雜網(wǎng)絡(luò)環(huán)境下，會增加分組時延,，這將是下一步研究工作的重點(diǎn),。
參考文獻(xià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] 嚴(yán)少虎，卓永寧,，吳詩其,等． IEEE 802. 11 DCF 中帶優(yōu)先級的退避算法[J]．電子與信息學(xué)報(bào),，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] 楊海東，李建海,，鄧勇.采用集總式?jīng)_突消除算法的Ad Hoc網(wǎng)絡(luò)MAC協(xié)議[J]. 系統(tǒng)工程與電子技術(shù), 2009,31(5):1241-1245.
[5] 葉林容,，余敬東．基于TDMA的Ad Hoc網(wǎng)絡(luò)MAC協(xié)議研究[D]. 成都：電子科技大學(xué),2011．
[6] FULLERTON P S. Dynamic control slot scheduling algorithm for TDMA based mobile Ad Hoc networks[C]. Military Communications Conference, 2008:1-7.