一種新型的無競爭的基于TDMA的MAC協(xié)議*

任昊翔，郭達(dá)偉*，邵凝寧，毛保磊

(1.西北工業(yè)大學(xué)自動化學(xué)院，西安710129;2.南京北方信息控制集團(tuán)有限責(zé)任公司，南京210000)

在Ad Hoc網(wǎng)絡(luò)[1]中，MAC協(xié)議由于其直接影響網(wǎng)絡(luò)的性能而成為研究熱點(diǎn)。Ad Hoc網(wǎng)絡(luò)中的MAC協(xié)議，按照其自身的發(fā)送機(jī)制，大抵可以劃分為以下兩大類。

第一類是基于競爭的 MAC協(xié)議[2－5]。這類協(xié)議的主要思想是通過網(wǎng)絡(luò)節(jié)點(diǎn)的相互競爭來直接決定信道的使用權(quán)，并且通過一定的策略使得擁有高優(yōu)先級數(shù)據(jù)的節(jié)點(diǎn)能夠更容易的競爭到信道，以使其具有更高的分組投遞率。

第二類是無競爭的 MAC協(xié)議[6－8]。這類協(xié)議的主要思想是先將信道劃分為超幀，又進(jìn)一步將超幀劃分為時隙。整個網(wǎng)絡(luò)通過分配或者競爭的方法來決定時隙的使用權(quán)。一旦節(jié)點(diǎn)獲得了時隙的使用權(quán)，那么這個節(jié)點(diǎn)在以后的超幀內(nèi)也將繼續(xù)使用這個時隙，直到節(jié)點(diǎn)沒有數(shù)據(jù)發(fā)送。

無競爭的MAC協(xié)議為了滿足各種QoS，主要是將競爭的思想融入到無競爭的協(xié)議中。引入競爭思想就可能產(chǎn)生沖突，從而造成數(shù)據(jù)時隙的浪費(fèi)。

本文提出一種新型的無競爭的MAC協(xié)議。通過加入時隙競爭和時隙續(xù)約機(jī)制以避免數(shù)據(jù)時隙的浪費(fèi)并提高數(shù)據(jù)時隙使用率和分組投遞率。而且通過引入虛擬數(shù)據(jù)和競爭時隙交換的機(jī)制，在提高分組投遞率的同時也降低了整個網(wǎng)絡(luò)的傳輸延遲。

1 無競爭的MAC協(xié)議研究現(xiàn)狀

無競爭的MAC協(xié)議，按照不同的QoS要求，大體可以分為兩類。

第1類是指提高分組投遞率的MAC協(xié)議。這類協(xié)議的思想是在TDMA體系中融入競爭的思想。主要是將超幀劃分為如圖1所示的結(jié)構(gòu)。每個超幀都擁有競爭時隙和數(shù)據(jù)時隙[9]。如果節(jié)點(diǎn)有數(shù)據(jù)要發(fā)送，則首先會在超幀中隨機(jī)挑選一個競爭時隙用于發(fā)送申請請求。如果申請請求正確發(fā)送，則這個節(jié)點(diǎn)可以在申請的數(shù)據(jù)時隙發(fā)送數(shù)據(jù)。否則，不能發(fā)送數(shù)據(jù)，且要實(shí)行退避。當(dāng)然，通過對不同優(yōu)先級的數(shù)據(jù)采用不同的競爭算法和退避算法，可以實(shí)現(xiàn)讓擁有高優(yōu)先級數(shù)據(jù)節(jié)點(diǎn)更容易競爭到競爭時隙，以滿足提高其分組投遞率的服務(wù)要求。

圖1 無競爭的MAC協(xié)議超幀格式

第2類是指降低網(wǎng)絡(luò)延遲的 MAC 協(xié)議[10－11]。文獻(xiàn)[10]提出的協(xié)議有著類似于圖1的超幀結(jié)構(gòu)。只是將時隙競爭時期變?yōu)樾艠?biāo)時期。在信標(biāo)時期內(nèi)，每個節(jié)點(diǎn)都有自己的信標(biāo)時隙。節(jié)點(diǎn)想要發(fā)送數(shù)據(jù)時，首先會在自己的信標(biāo)時隙中，廣播這個信息。接收到這個信息的節(jié)點(diǎn)也會在屬于自己的信標(biāo)時隙中繼續(xù)廣播這個消息，并且在這個消息中加入自己的節(jié)點(diǎn)信息。通過不斷的廣播直到目的節(jié)點(diǎn)接收到這個消息。目的節(jié)點(diǎn)在接收到這個消息之后，會選擇一條合適的路徑進(jìn)行單播回復(fù)，并且在回復(fù)中確定這兩個節(jié)點(diǎn)之間數(shù)據(jù)流使用的時隙。最終在這一去一回的消息交換中，以一定的超幀的時間為代價建立起發(fā)送節(jié)點(diǎn)到目的節(jié)點(diǎn)的一條路徑，之后節(jié)點(diǎn)才會發(fā)送數(shù)據(jù)，以獲得較低的網(wǎng)絡(luò)延遲。

而本篇論文，綜合了以上兩種思想的優(yōu)點(diǎn)，提出了一種新型的屬于自己的時隙競爭思想和路徑建立思想，以同時滿足以上兩種QoS要求。

2 CA-TDMA協(xié)議

2.1 超幀格式

CA-TDMA協(xié)議的超幀格式如圖2所示。在CA-TDMA協(xié)議中，超幀劃分為時隙競爭時期和數(shù)據(jù)發(fā)送時期。時隙競爭時期由M個競爭時隙組成。每個節(jié)點(diǎn)有且僅有一個屬于自己的競爭時隙。競爭時隙的作用是使節(jié)點(diǎn)發(fā)送數(shù)據(jù)時隙申請請求，以使節(jié)點(diǎn)獲得數(shù)據(jù)時隙的使用權(quán)。數(shù)據(jù)發(fā)送時期由N個數(shù)據(jù)時隙組成。其中N小于M。數(shù)據(jù)時隙主要用于發(fā)送數(shù)據(jù)。

圖2 CA-TDMA協(xié)議超幀格式

2.2 RTS、CTS、CTR 的消息結(jié)構(gòu)

2.2.1 RTS 消息的結(jié)構(gòu)

圖3為 CA-TDMA協(xié)議中 RTS消息的結(jié)構(gòu)。CA-TDMA協(xié)議中RTS消息按照不同的功能可以劃分為3個部分:時隙申請信息、時隙續(xù)約信息和時隙使用狀態(tài)信息。時隙申請信息用于節(jié)點(diǎn)申請新的數(shù)據(jù)時隙。時隙續(xù)約信息用于節(jié)點(diǎn)續(xù)約舊的數(shù)據(jù)時隙。時隙使用狀態(tài)信息用于填寫與節(jié)點(diǎn)有關(guān)的數(shù)據(jù)時隙使用狀態(tài)的信息，以完成對續(xù)約信息的確認(rèn)和取消。

圖3 CA-TDMA協(xié)議中RTS的幀結(jié)構(gòu)

2.2.2 CTS 消息的結(jié)構(gòu)

圖4為CA-TDMA協(xié)議中CTS的幀結(jié)構(gòu)。CATDMA協(xié)議中的CTS消息按照不同的功能劃分成兩個部分:時隙分配確認(rèn)信息和競爭時隙交換信息。時隙分配確認(rèn)信息用于對接收到的RTS信息進(jìn)行確認(rèn)回復(fù)。競爭時隙交換信息用于進(jìn)行競爭時隙交換。

圖4 CA-TDMA協(xié)議中CTS的幀結(jié)構(gòu)

2.2.3 CTR 消息的結(jié)構(gòu)

圖5為CA-TDMA協(xié)議中CTR的幀結(jié)構(gòu)。CTR消息用于對節(jié)點(diǎn)已確認(rèn)的發(fā)送請求進(jìn)行清除。

圖5 CA-TDMA協(xié)議中CTR的幀結(jié)構(gòu)

2.3 CA-TDMA的時隙競爭和時隙續(xù)約

2.3.1 時隙競爭

CA-TDMA協(xié)議中采用一種變相的競爭方法。首先每個節(jié)點(diǎn)都會依據(jù)算法1來決定如何生成RTS請求。如果節(jié)點(diǎn)發(fā)送有效的RTS信息后，收到有效的CTS信息，則生成相應(yīng)的記錄信息。如果在時隙競爭時期結(jié)束之后，節(jié)點(diǎn)記錄信息依然存在，則該節(jié)點(diǎn)可以在相應(yīng)的數(shù)據(jù)時隙發(fā)送數(shù)據(jù)。否則，節(jié)點(diǎn)會放棄該數(shù)據(jù)時隙，并且將數(shù)據(jù)的優(yōu)先級提升后放回數(shù)據(jù)緩沖區(qū)。這里有效的RTS消息是指RTS消息中有對數(shù)據(jù)時隙的申請請求信息，有效的CTS是指CTS消息是對RTS消息的正確回復(fù)。

算法1 RTS發(fā)送的確定算法

例如，如圖6所示的簡單拓?fù)渲小?/p>

圖6 3節(jié)點(diǎn)的拓?fù)鋱D

假設(shè)節(jié)點(diǎn)1有數(shù)據(jù)發(fā)送給節(jié)點(diǎn)2且優(yōu)先級為2，節(jié)點(diǎn)3也有數(shù)據(jù)發(fā)送給節(jié)點(diǎn)2優(yōu)先級暫且未知，而數(shù)據(jù)時隙的個數(shù)為1。那么當(dāng)超幀開始時，由于數(shù)據(jù)時隙1為空閑，節(jié)點(diǎn)1會在自己的競爭時隙內(nèi)和節(jié)點(diǎn)2交互“有效”的RTS和CTS信息(RTS1和CTS1)以完成數(shù)據(jù)時隙1的申請并做相應(yīng)的記錄信息。由于網(wǎng)絡(luò)是無線網(wǎng)絡(luò)，節(jié)點(diǎn)3也能收到CTS1信息，并會修改數(shù)據(jù)時隙1的狀態(tài)。當(dāng)節(jié)點(diǎn)3的競爭時隙到來后，則根據(jù)算法1，如果節(jié)點(diǎn)3的數(shù)據(jù)優(yōu)先級不大于節(jié)點(diǎn)1，節(jié)點(diǎn)3會發(fā)送“無效”的RTS信息。否則，節(jié)點(diǎn)3會發(fā)送“有效”的RTS信息(RTS2)，以實(shí)現(xiàn)節(jié)點(diǎn)3和節(jié)點(diǎn)2之間的控制信息交互。而節(jié)點(diǎn)1收到CTS2信息后也會得知，有更高優(yōu)先級的節(jié)點(diǎn)“占用”了與自己相同的數(shù)據(jù)時隙，則節(jié)點(diǎn)1刪除記錄信息并放棄數(shù)據(jù)時隙1。通過這種變相的競爭方法，以使得高優(yōu)先級數(shù)據(jù)能夠優(yōu)先發(fā)送。

由于CA-TDMA協(xié)議中的RTS和CTS信息的傳輸范圍只是發(fā)送RTS節(jié)點(diǎn)和發(fā)送CTS節(jié)點(diǎn)的一跳范圍，所以有可能會產(chǎn)生數(shù)據(jù)時隙的沖突。例如在如圖7所示的簡單拓?fù)渲?。假設(shè)節(jié)點(diǎn)1給節(jié)點(diǎn)2發(fā)送數(shù)據(jù)，節(jié)點(diǎn)3給節(jié)點(diǎn)4發(fā)送數(shù)據(jù)并且節(jié)點(diǎn)3的數(shù)據(jù)優(yōu)先級高于節(jié)點(diǎn)1。那么當(dāng)節(jié)點(diǎn)1和節(jié)點(diǎn)3選擇相同的數(shù)據(jù)時隙時就會產(chǎn)生數(shù)據(jù)沖突。

圖7 CTR作用說明拓?fù)鋱D

為了解決這種問題，CA-TDMA協(xié)議引入了CTR消息。當(dāng)出現(xiàn)上述情況時，節(jié)點(diǎn)2會生成CTR消息并發(fā)送給節(jié)點(diǎn)1，以阻止其發(fā)送數(shù)據(jù)。從而避免可能產(chǎn)生的數(shù)據(jù)沖突。

2.3.2 時隙續(xù)約

為了滿足大數(shù)據(jù)量的傳輸要求，CA-TDMA協(xié)議提出了時隙續(xù)約的機(jī)制。時隙續(xù)約也是時隙申請，是指對已經(jīng)成功申請的數(shù)據(jù)時隙再次進(jìn)行申請。

具體來說，例如在圖6拓?fù)渲?，假設(shè)節(jié)點(diǎn)1有大量的數(shù)據(jù)要發(fā)送給節(jié)點(diǎn)2。那么節(jié)點(diǎn)1在第一個超幀會通過RTS的時隙申請信息對節(jié)點(diǎn)2進(jìn)行數(shù)據(jù)時隙申請并做記錄。而在接下來的超幀內(nèi)，如果節(jié)點(diǎn)1還有數(shù)據(jù)要發(fā)送給節(jié)點(diǎn)2，那么節(jié)點(diǎn)1首先會填寫RTS的續(xù)約信息，以告知節(jié)點(diǎn)2我依然會用原來的時隙繼續(xù)發(fā)送數(shù)據(jù)，如果此時節(jié)點(diǎn)1的還有數(shù)據(jù)存在，那么節(jié)點(diǎn)1就會通過RTS中的時隙申請信息向節(jié)點(diǎn)2申請第二個數(shù)據(jù)時隙用來發(fā)送數(shù)據(jù)。之后，如果節(jié)點(diǎn)1的數(shù)據(jù)依然很多，那么節(jié)點(diǎn)1就可以繼續(xù)續(xù)約2個數(shù)據(jù)時隙并且申請第三個數(shù)據(jù)時隙，直到達(dá)到網(wǎng)絡(luò)達(dá)到負(fù)載上限。

當(dāng)節(jié)點(diǎn)1的數(shù)據(jù)變少時，節(jié)點(diǎn)1就必須立刻通告周圍鄰居自己放棄使用數(shù)據(jù)時隙，并刪除自己的續(xù)約信息，以使其他節(jié)點(diǎn)可以使用這些數(shù)據(jù)時隙。

2.4 CA-TDMA的虛擬數(shù)據(jù)和競爭時隙交換

為了降低數(shù)據(jù)的傳輸延遲，CA-TDMA協(xié)議加入虛擬數(shù)據(jù)和競爭時隙交換的思想。虛擬數(shù)據(jù)思想是指節(jié)點(diǎn)在申請數(shù)據(jù)時隙時要考慮到由RTS信息提供的虛擬數(shù)據(jù)信息這個因素。具體來說，例如在圖8拓?fù)渲?，對于?shù)據(jù)流1，當(dāng)節(jié)點(diǎn)N(N=2、3)收到節(jié)點(diǎn)N－1的RTS申請請求之后，節(jié)點(diǎn)N就會根據(jù)RTS信息記錄一個虛擬數(shù)據(jù)信息。而當(dāng)節(jié)點(diǎn)N自己的競爭時隙到來的時候，如果節(jié)點(diǎn)N的虛擬數(shù)據(jù)信息的優(yōu)先級大于數(shù)據(jù)緩沖區(qū)內(nèi)所有數(shù)據(jù)的優(yōu)先級，那么節(jié)點(diǎn)N會依據(jù)虛擬數(shù)據(jù)信息發(fā)送對于虛擬數(shù)據(jù)的申請請求。最終構(gòu)成一個連續(xù)的申請，使得在一個超幀內(nèi)，完成節(jié)點(diǎn)1向節(jié)點(diǎn)4數(shù)據(jù)發(fā)送。

圖8 四節(jié)點(diǎn)拓?fù)鋱D

但是對于圖8中的數(shù)據(jù)流2，那么僅僅依靠虛擬數(shù)據(jù)就沒有辦法降低延遲的。因為節(jié)點(diǎn)N(N=2、3)在收到節(jié)點(diǎn)N+1的RTS申請請求之后，已無法再去申請數(shù)據(jù)時隙。所以CA-TDMA協(xié)議更提出了競爭時隙交換的思想以輔助解決這種情況，競爭時隙交換思想就是決定如何交換競爭時隙，主要由算法2確定。

算法2 競爭時隙交換的確定算法

對于圖8所示的數(shù)據(jù)流2，根據(jù)算法2，就出現(xiàn)如圖9所示的競爭時隙交換。最終節(jié)點(diǎn)1、2、3、4的競爭時隙的位序會改變?yōu)?、3、2、1。在加上虛擬數(shù)據(jù)的思想，就可以實(shí)現(xiàn)在一個超幀內(nèi)對數(shù)據(jù)流2的數(shù)據(jù)進(jìn)行正確的發(fā)送。

圖9 4節(jié)點(diǎn)競爭時隙交換

3 仿真與性能分析

3.1 仿真參數(shù)

使用仿真工具為NS2[12]，具體仿真參數(shù)如表1。

表1

3.2 仿真結(jié)果與性能分析

本文針對不同的發(fā)包頻率，在以20 m/s的移動場景中，對CA-TDMA協(xié)議和DTDMA協(xié)議在性能上做了對比分析，在相同的環(huán)境中，實(shí)驗結(jié)果如下:

結(jié)合圖10和圖11我們可以看出，CA-TDMA協(xié)議和DTDMA協(xié)議的分組投遞率都沒有高于85%。這是由于節(jié)點(diǎn)移動所導(dǎo)致的一定時間內(nèi)路由信息與實(shí)際拓?fù)湫畔⒉粚Φ榷a(chǎn)生的丟包。并且通過仿真結(jié)果來看，這部分丟失的數(shù)據(jù)包大約占到所有數(shù)據(jù)的17%左右。

圖10 整個網(wǎng)絡(luò)的平均分組投遞率

圖11 高優(yōu)先級數(shù)據(jù)的分組投遞率

通過圖10和圖11我們還可以看出，隨著發(fā)包頻率的增加，CA-TDMA協(xié)議在平均分組投遞率和高優(yōu)先級數(shù)據(jù)的分組投遞率上較DTDMA協(xié)議有著更為優(yōu)異的表現(xiàn)，這是由于CA-TDMA協(xié)議是無競爭的，所以不會因為高網(wǎng)絡(luò)負(fù)載而產(chǎn)生競爭時隙的沖突，也就不會造成的數(shù)據(jù)時隙的浪費(fèi)，從而提高了分組的投遞率。并且不產(chǎn)生沖突也就意味著數(shù)據(jù)能夠正常的發(fā)送，會減少數(shù)據(jù)在緩沖區(qū)內(nèi)的停留時間，會減低數(shù)據(jù)的傳輸延遲。

圖12 高優(yōu)先級數(shù)據(jù)的傳輸延遲

通過圖12可以看出，在高優(yōu)先級數(shù)據(jù)的傳輸延遲性能方面，CA-TDMA表現(xiàn)的比DTDMA更為優(yōu)秀，這是因為CA-TDMA協(xié)議可以通過競爭時隙交換和虛擬數(shù)據(jù)的思想，盡量使得高優(yōu)先級數(shù)據(jù)能夠在一個超幀內(nèi)傳輸?shù)侥康墓?jié)點(diǎn)。

4 結(jié)語

本文提出了一種新型的無競爭的MAC協(xié)議CA-TDMA。仿真結(jié)果說明CA-TDMA相比DTDMA協(xié)議，在平均分組投遞率、高優(yōu)先級數(shù)據(jù)分組投遞率、高優(yōu)先級數(shù)據(jù)傳輸延遲性能方面均有明顯的提高。當(dāng)然，MAC協(xié)議的性能和具體的網(wǎng)絡(luò)拓?fù)湎⑾⑾嚓P(guān)，如何使CA-TDMA協(xié)議能夠適用于更多的網(wǎng)絡(luò)拓?fù)?，會是一個重要的后續(xù)需要研究的問題。

[1]王金龍，王呈貴，吳啟輝，等.Ad Hoc移動無線網(wǎng)絡(luò)[M].北京:國防工業(yè)出版社，2004:3－180.

[2]Rehman H，Wolf L.A Multihop IEEE 802.11 MAC Protocol for Wireless Ad Hoc Networks[C]//Distributed Computing Systems Workshops，2009.ICDCS Workshops’09.29th IEEE International Conference on，Braunschweig，Germany，2009:432－439.

[3]Youn-Chul Cho，Sun-Joong Yoon，Young-Bae Ko.Modifying the IEEE 802.11 MAC Protocol for Multi-Hop Reservation in MIMC Tactical Ad Hoc Networks[C]//Advanced Information Networking and Applications(WAINA)，2011 IEEE Workshops of International Conference on，Suwon，South Korea，2011:178－183.

[4]Xiao Yongkang，Yin Xunhe.Performance Modeling and Analysis of IEEE 802.11 MAC Protocol in Multihop Ad Hoc Networks[C]//Wireless CommunicationsNetworkingand MobileComputing(WiCOM)，2010 6th International Conference on，Beijing，China，2010:1－5.

[5]Jian Ni，Bo Tan，Srikant R.Q-CSMA:Queue-Length Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks[C]//Infocom，2010 Proceedings IEEE，Urbana，USA，2010:1－5.

[6]Bokri J，Ouni S，Kamoun F.A Novel Reservation Approach for TDMA-Based Ad Hoc Networks[C]//Communications and Networking(ComNet)，2010 Second International Conference on，Tunis，Tunisia，2010:1－7

[7]Li Jianping，Wakahara Y.Time Slot Assignment for Maximum Bandwidth in a Mobile Ad Hoc Network[C]//Wireless Pervasive Computing，2007.ISWPC 07.2nd InternationalSymposium on，2007.

[8]Djukic P，Valaee S.Link Scheduling for Minimum Delay in Spatial Re-Use TDMA[C]//Infocom 2007，26th IEEE International Conference on Computer Communication，Toronto，Canada，2007:28－36

[9]Kamruzzaman S M，Alam M S.Dynamic TDMA Slot Reservation Protocol for Cognitive Radio Ad Hoc Networks[C]//Computer and Information Technology(ICCIT)，2010 13th International Conference on，Yongin，South Korea.2010.142－147

[10]Jae-Ryong Cha，Kwang-Chun Go，Jae-Hyun Kim.TDMA-Based Multi-Hop Resource Reservation Protocol for Real-Time Applications in Tactical Mobile Ad Hoc Network[C]//MILCOM 2010，Suwon，South Korea，2010:1936－1941

[11]Braten L E，Voldhaug J E，Ovsthus K.Medium Access for a Military Narrowband Wireless Ad-Hoc Network;Requirements and Initial Approaches[C]//Milcom 2008.IEEE 2008:1－7

[12]于斌，孫斌，溫暖，等.NS2與網(wǎng)絡(luò)模擬[M].北京:人民郵電出版社，2007:46－133