HTDMA協(xié)議自協(xié)調(diào)分布式運(yùn)行機(jī)制研究*

魏小龍,李建海,楊海東

（空軍工程大學(xué) 工程學(xué)院，陜西 西安710038）

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

1 分布式運(yùn)行約束條件

在CCS-QR協(xié)議中,控制時(shí)隙只完成虛擬載波監(jiān)聽，并不為節(jié)點(diǎn)分配數(shù)據(jù)時(shí)隙,這種完全解耦的業(yè)務(wù)關(guān)系，減少了很多控制開銷。但其帶來(lái)另一個(gè)問(wèn)題是，如果不提前發(fā)送時(shí)隙分配表，在數(shù)據(jù)時(shí)隙內(nèi)由各節(jié)點(diǎn)根據(jù)優(yōu)先級(jí)確定發(fā)送次序，則節(jié)點(diǎn)之間就不能相互協(xié)調(diào)地發(fā)送數(shù)據(jù)分組，就會(huì)引發(fā)沖突。

CCS-QR協(xié)議的數(shù)據(jù)時(shí)隙如圖1所示，結(jié)合圖2，例如在第1個(gè)數(shù)據(jù)時(shí)隙內(nèi)，兩跳范圍內(nèi)業(yè)務(wù)①②③會(huì)同時(shí)發(fā)送，而相互沖突導(dǎo)致失敗。原因是分布式網(wǎng)絡(luò)結(jié)構(gòu)下，節(jié)點(diǎn)覆蓋范圍有限，無(wú)法得到所有節(jié)點(diǎn)的業(yè)務(wù)信息，所以每個(gè)節(jié)點(diǎn)所維持的預(yù)約序列都不相同[6]。

構(gòu)建此問(wèn)題的數(shù)學(xué)模型可以得到分布式Ad Hoc網(wǎng)絡(luò)正常通信的制約條件。根據(jù)圖2，可以用一個(gè)N×N的二維矩陣C=Cij來(lái)表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),其中N=|V|為網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)：

假設(shè)一個(gè)時(shí)幀劃分為M個(gè)時(shí)隙，一個(gè)時(shí)幀內(nèi)每個(gè)節(jié)點(diǎn)至少分配到一個(gè)時(shí)隙，用M×N二維矩陣X=Xmi來(lái)表示時(shí)隙分配方案，其中

綜上可以將時(shí)隙分配問(wèn)題規(guī)劃為一個(gè)數(shù)學(xué)模型：

目標(biāo)函數(shù)為：min M and max ρ

約束條件為：

式(4)中的第一個(gè)約束條件表示一個(gè)時(shí)幀內(nèi)節(jié)點(diǎn)至少分配一個(gè)時(shí)隙，第二個(gè)約束條件表示相距一跳的節(jié)點(diǎn)不能分配同一時(shí)隙，第三個(gè)約束條件表示兩個(gè)節(jié)點(diǎn)與同一節(jié)點(diǎn)相距一跳時(shí)不能分配同一時(shí)隙。以上說(shuō)明，如果要滿足目標(biāo)函數(shù)，無(wú)沖突發(fā)送數(shù)據(jù)，則必須保證相距兩跳范圍內(nèi)的節(jié)點(diǎn)分配不同的時(shí)隙。

2 分布式隊(duì)列運(yùn)行機(jī)制與分析

本文針對(duì)解耦關(guān)系的HTDMA，提出一種自協(xié)調(diào)分布式運(yùn)行解決方案。下面對(duì)圖2所示的網(wǎng)絡(luò)模型和CCS-QR協(xié)議[4]進(jìn)行分析和說(shuō)明。

在圖2中，網(wǎng)絡(luò)由14個(gè)節(jié)點(diǎn)組成，實(shí)線表示兩個(gè)節(jié)點(diǎn)在對(duì)方覆蓋范圍內(nèi)，箭頭表示兩個(gè)節(jié)點(diǎn)已在信令時(shí)隙完成數(shù)據(jù)時(shí)隙的預(yù)約，序號(hào)表示節(jié)點(diǎn)發(fā)送RTS/CTS分組的順序，為了簡(jiǎn)化模型，省略了CCS-QR協(xié)議里優(yōu)先級(jí)的表達(dá)。

2.1 業(yè)務(wù)管理樹算法原理

定義1：各個(gè)發(fā)射節(jié)點(diǎn)將所有兩跳范圍內(nèi)的發(fā)送業(yè)務(wù)排成預(yù)約隊(duì)列，稱為不完全隊(duì)列,用Ci={ci-a,ci-b…ci}表示，Li為不完全隊(duì)列的長(zhǎng)度。

定義2：根據(jù)協(xié)議安排，把控制時(shí)隙里允許接入的最大業(yè)務(wù)量按照優(yōu)先級(jí)或接入次序進(jìn)行排隊(duì)，稱之為完全隊(duì)列，用 Call={c1,c2…cn}表示，Lall為完全隊(duì)列的長(zhǎng)度。

定義 3：設(shè) Ci為節(jié)點(diǎn) i的不完全隊(duì)列，Ni為節(jié)點(diǎn) i在Ci中的序號(hào)，每當(dāng)Ci中的一個(gè)節(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ù)，將此時(shí)節(jié)點(diǎn)i的業(yè)務(wù)稱為待發(fā)業(yè)務(wù)。

定義4：將所有發(fā)送業(yè)務(wù)按照預(yù)約順序的方向排成隊(duì)列，該隊(duì)列會(huì)從觸發(fā)業(yè)務(wù)和待發(fā)業(yè)務(wù)處產(chǎn)生樹形結(jié)構(gòu)，稱它為業(yè)務(wù)管理樹，其模型如圖3。業(yè)務(wù)管理樹的長(zhǎng)度Lall等于所有業(yè)務(wù)發(fā)送完畢所需時(shí)隙的個(gè)數(shù)。

當(dāng)某個(gè)業(yè)務(wù)同時(shí)作為兩個(gè)預(yù)約隊(duì)列中不同節(jié)點(diǎn)的觸發(fā)業(yè)務(wù)時(shí)，業(yè)務(wù)樹將產(chǎn)生分支結(jié)構(gòu)，分支點(diǎn)位于當(dāng)前業(yè)務(wù)之后，即某兩個(gè)待發(fā)業(yè)務(wù)之前；當(dāng)不同分支的兩個(gè)節(jié)點(diǎn)同時(shí)作為某個(gè)業(yè)務(wù)的觸發(fā)業(yè)務(wù)時(shí)，業(yè)務(wù)樹將產(chǎn)生匯聚結(jié)構(gòu)，匯聚點(diǎn)位于當(dāng)前業(yè)務(wù)之前。

業(yè)務(wù)樹出現(xiàn)分支意味著將有多個(gè)子序列同時(shí)發(fā)送數(shù)據(jù)，而業(yè)務(wù)樹的匯聚表示在某個(gè)節(jié)點(diǎn)接入信道前，其預(yù)約隊(duì)列中同時(shí)有多個(gè)節(jié)點(diǎn)發(fā)送了數(shù)據(jù)。

前面已經(jīng)通過(guò)數(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)可以同時(shí)隙發(fā)送業(yè)務(wù),發(fā)送次序?yàn)長(zhǎng)i。

2.2 算法描述

一個(gè)業(yè)務(wù)管理樹運(yùn)行過(guò)程面向業(yè)務(wù)序列，而不是節(jié)點(diǎn)。具體工作過(guò)程為：

(1)收集發(fā)射狀態(tài)（Collection Phase）：在控制時(shí) 隙，通過(guò)對(duì)所有RTS分組和對(duì)應(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)先級(jí)設(shè)置和節(jié)點(diǎn)的接入次序?yàn)槊宽?xiàng)業(yè)務(wù)分配權(quán)重，即發(fā)送次序，并由此產(chǎn)生一個(gè)相同的完全隊(duì)列，包含所有業(yè)務(wù)信息。

(3)隊(duì)列形成（Establishing Phase）：在此階段，節(jié)點(diǎn)依據(jù)已得到兩跳范圍內(nèi)其他節(jié)點(diǎn)的發(fā)射狀態(tài)來(lái)形成不完全預(yù)約隊(duì)列，這個(gè)隊(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)過(guò)隊(duì)列調(diào)整后，各節(jié)點(diǎn)的預(yù)約隊(duì)列分別如表1所示。在此為了便于說(shuō)明，隊(duì)列中業(yè)務(wù)序列按其序號(hào)排列。

根據(jù)業(yè)務(wù)樹算法，在各預(yù)約隊(duì)列中，只有當(dāng)序列中排在前面的所有節(jié)點(diǎn)都發(fā)送了數(shù)據(jù)，當(dāng)前節(jié)點(diǎn)才能發(fā)送數(shù)據(jù)。得到整個(gè)系統(tǒng)的業(yè)務(wù)發(fā)送次序如圖2箭頭表示信道使用權(quán)的傳遞方向。

表1 圖2中各發(fā)射節(jié)點(diǎn)所維護(hù)的預(yù)約隊(duì)列

因此，對(duì)于圖2的模型，分布式隊(duì)列的路徑可以用圖 4(a)、(b)所示的業(yè)務(wù)樹來(lái)表示。

對(duì)照?qǐng)D2可以看出，在圖4中的業(yè)務(wù)樹中，不同分支上的業(yè)務(wù)可以在同時(shí)隙發(fā)送，而不引起分組碰撞。如圖4(a)中的業(yè)務(wù)②和業(yè)務(wù)③，以及圖4(b)中的業(yè)務(wù)④和業(yè)務(wù)③。

對(duì)照?qǐng)D1，從圖5新業(yè)務(wù)的發(fā)送次序上看，在兩組兩跳節(jié)點(diǎn)間，數(shù)據(jù)發(fā)送無(wú)沖突，空間可復(fù)用?？梢?jiàn)，通過(guò)業(yè)務(wù)樹管理算法，節(jié)點(diǎn)能夠依據(jù)自身在隊(duì)列中的次序依次接入信道。這種機(jī)制完全可以代替預(yù)約時(shí)隙表，可以在不增加任何協(xié)議開銷的情況下，實(shí)現(xiàn)節(jié)點(diǎn)的自協(xié)調(diào)、無(wú)沖突的分布式傳輸。

3 仿真實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證業(yè)務(wù)樹算法在改善分布式網(wǎng)絡(luò)性能中起到的作用，通過(guò)網(wǎng)絡(luò)仿真軟件OPNET，對(duì)該算法使用前后 CCT—QR協(xié)議/DCT—QR協(xié)議（Distributed CCT—QR）的丟包率和吞吐量進(jìn)行了仿真和對(duì)比。

仿真網(wǎng)絡(luò)環(huán)境參數(shù)和協(xié)議參數(shù)見(jiàn)表2。

表2 仿真參數(shù)表

3.1 吞吐量分析

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

3.2 丟包率分析

圖7顯示了兩種協(xié)議的數(shù)據(jù)包丟失情況。當(dāng)網(wǎng)絡(luò)負(fù)載并不高時(shí)，CCT—QR協(xié)議和改進(jìn)后的DCT—QR協(xié)議的丟包率相當(dāng)。但當(dāng)輸入量達(dá)到一定值時(shí)(480 packet/s)，分布式運(yùn)行機(jī)制就會(huì)體現(xiàn)出它的作用，它消除了業(yè)務(wù)密集后帶來(lái)的分組碰撞，降低了原協(xié)議的丟包率，但當(dāng)業(yè)務(wù)量超過(guò)控制時(shí)隙容量時(shí)，丟包率將無(wú)可避免地增加。

本文提出了解決Ad Hoc網(wǎng)絡(luò)非耦合HTDMA協(xié)議分布式運(yùn)行沖突的自協(xié)調(diào)式的業(yè)務(wù)管理樹算法，通過(guò)舉例分析和仿真實(shí)驗(yàn)可以看出，該算法能夠達(dá)到預(yù)期效果。但這種算法在復(fù)雜網(wǎng)絡(luò)環(huán)境下，會(huì)增加分組時(shí)延，這將是下一步研究工作的重點(diǎ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)少虎，卓永寧，吳詩(shī)其,等．IEEE 802.11 DCF中帶優(yōu)先級(jí)的退避算法[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.