一種新的競(jìng)爭(zhēng)與分配相結(jié)合的MAC協(xié)議

潘 鵬，郭達(dá)偉，劉 航，王 鵬

一種新的競(jìng)爭(zhēng)與分配相結(jié)合的MAC協(xié)議

潘 鵬，郭達(dá)偉，劉 航，王 鵬

針對(duì)IEEE 802.11在高競(jìng)爭(zhēng)下吞吐量低，以及TDMA協(xié)議在低負(fù)載下吞吐量低的問題，提出了一種新的TDMA MAC協(xié)議：Q-TDMA。結(jié)合TDMA協(xié)議可以保證節(jié)點(diǎn)在每個(gè)周期內(nèi)有一個(gè)發(fā)送機(jī)會(huì)，而同步CSMA/CA機(jī)制可以解決隱藏終端和暴露終端的問題，Q-TDMA協(xié)議要求節(jié)點(diǎn)根據(jù)本身的隊(duì)列長(zhǎng)度來競(jìng)爭(zhēng)復(fù)用時(shí)隙。仿真實(shí)驗(yàn)結(jié)果表明，Q-TDMA提高了網(wǎng)絡(luò)吞吐量，降低了端到端的延遲。

Ad hoc網(wǎng)絡(luò)；時(shí)分多址；媒介接入控制；Q-TDMA協(xié)議

1 引言

Ad hoc網(wǎng)絡(luò)是一種不依賴于任何固定基礎(chǔ)網(wǎng)絡(luò)設(shè)施的自組織、分布式的多跳無(wú)線網(wǎng)絡(luò)。它可以由無(wú)線移動(dòng)終端在一定的范圍內(nèi)自由搭建。Ad hoc網(wǎng)絡(luò)中節(jié)點(diǎn)直接通過無(wú)線共享媒介，進(jìn)行交換數(shù)據(jù)包。媒體接入控制（MAC）主要作用是提供有效的調(diào)度機(jī)制來分配有限的無(wú)線共享信道資源。MAC層控制網(wǎng)絡(luò)節(jié)點(diǎn)接入無(wú)線信道，是所有數(shù)據(jù)報(bào)文和控制信息在無(wú)線信道上發(fā)送和接收的直接支配者。因此，MAC層高效地使用無(wú)線信道的有限帶寬是至關(guān)重要的。

根據(jù)信道接入的策略，Ad hoc網(wǎng)絡(luò)的MAC協(xié)議可以分為競(jìng)爭(zhēng)類和分配類。競(jìng)爭(zhēng)類協(xié)議主要包括：Aloha、 CSMA、MACA、FAMA和802.11[1-5]。它們一般采用沖突避免機(jī)制和隨機(jī)重傳，在網(wǎng)絡(luò)負(fù)載較輕時(shí)比較有效。但隨著負(fù)載增加沖突增多，吞吐量可能降低至零，網(wǎng)絡(luò)不穩(wěn)定，不能保證有界的端到端延遲。其優(yōu)點(diǎn)是移動(dòng)透明性，即協(xié)議不會(huì)根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓瘉砀淖児ぷ鞣绞健７峙漕悈f(xié)議主要包括：傳統(tǒng)的TDMA、E-TDMA[6]和ADAPT[7]等。傳統(tǒng)TDMA具有移動(dòng)透明性優(yōu)點(diǎn)，但是它不能復(fù)用時(shí)隙，吞吐量低；E-TDMA適用于大負(fù)載網(wǎng)絡(luò)，缺點(diǎn)是不具有移動(dòng)透明性，不能適應(yīng)于拓?fù)渥兓斓木W(wǎng)絡(luò)；ADAPT是一個(gè)競(jìng)爭(zhēng)分配相結(jié)合的MAC協(xié)議，有效地增加了吞吐量，但同時(shí)引入了隱藏終端和暴露終端的問題。

為了解決這些協(xié)議中存在的上述缺點(diǎn)，本文提出了Q-TDMA協(xié)議。

2 Q-TDMA協(xié)議描述

Q-TDMA協(xié)議是一種TDMA與同步CSMA/CA機(jī)制相結(jié)合的協(xié)議。每個(gè)節(jié)點(diǎn)固定擁有一個(gè)屬于自己的時(shí)隙，引入同步競(jìng)爭(zhēng)機(jī)制對(duì)未使用的時(shí)隙進(jìn)行管理，在自己時(shí)隙上節(jié)點(diǎn)有優(yōu)先發(fā)送RTS的權(quán)力；當(dāng)其他節(jié)點(diǎn)發(fā)現(xiàn)時(shí)隙的擁有者沒有數(shù)據(jù)發(fā)送時(shí)，它則根據(jù)本節(jié)點(diǎn)隊(duì)列的長(zhǎng)度，對(duì)該時(shí)隙進(jìn)行分優(yōu)先級(jí)競(jìng)爭(zhēng)復(fù)用時(shí)隙。

網(wǎng)絡(luò)中存在N個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)固定分配一個(gè)時(shí)隙，每個(gè)時(shí)隙包括監(jiān)聽、競(jìng)爭(zhēng)和數(shù)據(jù)3個(gè)階段；其中監(jiān)聽階段又分為兩個(gè)子微時(shí)隙。競(jìng)爭(zhēng)階段包括競(jìng)爭(zhēng)1和競(jìng)爭(zhēng)2兩個(gè)階段。每個(gè)競(jìng)爭(zhēng)階段分為n個(gè)微時(shí)隙，每個(gè)微時(shí)隙再分為兩個(gè)子微時(shí)隙。競(jìng)爭(zhēng)階段和監(jiān)聽階段的微時(shí)隙、子微時(shí)隙相等。具體幀和時(shí)隙結(jié)構(gòu)如圖1所示。

圖1 幀和時(shí)隙結(jié)構(gòu)

本文將從時(shí)隙的監(jiān)聽、競(jìng)爭(zhēng)、數(shù)據(jù)階段來介紹Q-TDMA協(xié)議。假設(shè)目前正處在時(shí)隙i，各個(gè)節(jié)點(diǎn)在這個(gè)時(shí)隙內(nèi)的具體動(dòng)作如下。

監(jiān)聽階段：在時(shí)隙i中，節(jié)點(diǎn)i如果有數(shù)據(jù)要發(fā)送，則在第一個(gè)子微時(shí)隙發(fā)送RTS。收到RTS的目的節(jié)點(diǎn)在第二個(gè)子微時(shí)隙回復(fù)CTS，節(jié)點(diǎn)i收到CTS回復(fù)，則節(jié)點(diǎn)i在數(shù)據(jù)階段發(fā)送數(shù)據(jù)。如果非目的節(jié)點(diǎn)收到RTS，則這些節(jié)點(diǎn)標(biāo)記在時(shí)隙i內(nèi)不接收數(shù)據(jù)。如果非發(fā)送節(jié)點(diǎn)收到CTS，則這些節(jié)點(diǎn)標(biāo)記在時(shí)隙i內(nèi)不發(fā)送數(shù)據(jù)。這樣可以保證在發(fā)送端不存在其他的接收節(jié)點(diǎn)，在接收端不存在其他的發(fā)送節(jié)點(diǎn)。

如果節(jié)點(diǎn)i沒有數(shù)據(jù)要發(fā)送，則它不競(jìng)爭(zhēng)信道。其中RTS、CTS幀格式如圖2、圖3所示。

圖2 RTS幀

圖3 CTS幀

競(jìng)爭(zhēng)階段：在時(shí)隙i的監(jiān)聽階段，節(jié)點(diǎn)j如果沒有監(jiān)聽到CTS，且有數(shù)據(jù)要發(fā)送，則可以根據(jù)本節(jié)點(diǎn)隊(duì)列的長(zhǎng)度，來判斷選擇在競(jìng)爭(zhēng)1或競(jìng)爭(zhēng)2階段中來進(jìn)行競(jìng)爭(zhēng)信道。節(jié)點(diǎn)在所選擇的競(jìng)爭(zhēng)階段隨機(jī)選擇一個(gè)微時(shí)隙來競(jìng)爭(zhēng)信道，具體流程如下（給定隊(duì)列長(zhǎng)度的閾值為L(zhǎng)）：

在時(shí)隙i內(nèi)，如果節(jié)點(diǎn)j的隊(duì)列長(zhǎng)度為M，且大于給定的閾值L，則它在競(jìng)爭(zhēng)1階段中隨機(jī)選擇一個(gè)微時(shí)隙，來競(jìng)爭(zhēng)信道。假設(shè)節(jié)點(diǎn)j選擇在微時(shí)隙q(1≤q≤n)中進(jìn)行競(jìng)爭(zhēng)信道。如果節(jié)點(diǎn)j在前q-1個(gè)時(shí)隙內(nèi)沒有收到過其他節(jié)點(diǎn)發(fā)送的CTS，則節(jié)點(diǎn)j在微時(shí)隙q的第一個(gè)子微時(shí)隙中發(fā)送RTS，如果目的節(jié)點(diǎn)收到RTS，且在前q-1時(shí)隙內(nèi)沒有收到其他節(jié)點(diǎn)發(fā)送的RTS，則目的節(jié)點(diǎn)在第二個(gè)子微時(shí)隙回復(fù)CTS。如果節(jié)點(diǎn)j收到CTS回復(fù)，則說明節(jié)點(diǎn)j成功地占用了信道，它將會(huì)在數(shù)據(jù)階段發(fā)送數(shù)據(jù)。收到RTS的非目的節(jié)點(diǎn)標(biāo)記在時(shí)隙i中不接收數(shù)據(jù)。

如果節(jié)點(diǎn)j的隊(duì)列長(zhǎng)度M小于等于給定的閾值L，則它在競(jìng)爭(zhēng)2階段隨機(jī)選擇微時(shí)隙競(jìng)爭(zhēng)信道，同上所述。

數(shù)據(jù)階段：競(jìng)爭(zhēng)到信道的節(jié)點(diǎn)，在此階段發(fā)送數(shù)據(jù)。

3 協(xié)議性能分析

3.1 吞吐量

為了簡(jiǎn)化分析，本文假設(shè)網(wǎng)絡(luò)拓?fù)涫庆o態(tài)的，流量負(fù)載均勻分布。網(wǎng)絡(luò)中存在N個(gè)節(jié)點(diǎn)，一個(gè)周期內(nèi)包含N個(gè)時(shí)隙。

對(duì)于一個(gè)給定的節(jié)點(diǎn)i，需要分析討論兩種情況的吞吐量：一種是時(shí)隙分配給節(jié)點(diǎn)i，另一種是時(shí)隙未分配給節(jié)點(diǎn)i。用φ表示節(jié)點(diǎn)i有數(shù)據(jù)包傳輸?shù)母怕剩斜硎竟?jié)點(diǎn)i的鄰居平均個(gè)數(shù)（不包括有數(shù)據(jù)向節(jié)點(diǎn)i的兩跳鄰居傳輸?shù)墓?jié)點(diǎn)）。由于每個(gè)時(shí)隙分配給節(jié)點(diǎn)i的概率為1/N，所以節(jié)點(diǎn)i在自己的時(shí)隙上傳輸數(shù)據(jù)包的概率為：

另一種情況是節(jié)點(diǎn)i嘗試在未分配給自己的時(shí)隙上發(fā)送數(shù)據(jù)。節(jié)點(diǎn)競(jìng)爭(zhēng)未分配給自己的時(shí)隙的概率可以表示為：

其中，t是節(jié)點(diǎn)在一個(gè)時(shí)隙內(nèi)傳輸?shù)母怕省９?jié)點(diǎn)i競(jìng)爭(zhēng)成功的概率為：

通過聯(lián)合兩種情況的傳輸數(shù)據(jù)包概率，得到一個(gè)節(jié)點(diǎn)的近似吞吐量：

通過計(jì)算，得出，當(dāng)t=1/(π(1-φ/N)π)時(shí)，Q-TDMA的節(jié)點(diǎn)的吞吐量上界為：

3.2 同步RTS/CTS消除隱藏終端和暴露終端

IEEE 802.11 DCF通過引入異步RTS/CTS握手機(jī)制來減少隱藏終端問題，但是它并沒有完全消除隱藏終端問題，同時(shí)又帶來了暴露終端問題。

在圖4中，Si是發(fā)送節(jié)點(diǎn)，Ri是接收節(jié)點(diǎn)。在802.11方式下，可能會(huì)出現(xiàn)如下情況：當(dāng)節(jié)點(diǎn)S2正在給節(jié)點(diǎn)R2發(fā)送RTS，同時(shí)節(jié)點(diǎn)R1在給節(jié)點(diǎn)S1回復(fù)CTS時(shí)，節(jié)點(diǎn)R1無(wú)法檢測(cè)來自節(jié)點(diǎn)S2的RTS，節(jié)點(diǎn)S2無(wú)法檢測(cè)來自節(jié)點(diǎn)R1的CTS，這樣就會(huì)出現(xiàn)節(jié)點(diǎn)S1向節(jié)點(diǎn)R1發(fā)送數(shù)據(jù)時(shí)，節(jié)點(diǎn)S2向節(jié)點(diǎn)R2發(fā)送數(shù)據(jù)或CTS，數(shù)據(jù)在節(jié)點(diǎn)R1處發(fā)生碰撞。這就是隱藏終端問題。

圖4 隱藏終端和暴露終端問題

這里引入同步RTS/CTS方式[8]進(jìn)行握手交換，從而來解決隱藏終端問題。假設(shè)節(jié)點(diǎn)S1、S2選擇同一等級(jí)的競(jìng)爭(zhēng)階段，競(jìng)爭(zhēng)向節(jié)點(diǎn)R1、R2發(fā)送數(shù)據(jù)，其中節(jié)點(diǎn)S1、S2選擇在T1、T2微時(shí)隙內(nèi)競(jìng)爭(zhēng)。

當(dāng)T1＜T2時(shí)，在T1微時(shí)隙的第一個(gè)子微時(shí)隙內(nèi)，節(jié)點(diǎn)S1發(fā)送RTS給節(jié)點(diǎn)R1，收到RTS的節(jié)點(diǎn)R1在第二個(gè)子微時(shí)隙內(nèi)回復(fù)CTS，節(jié)點(diǎn)S1收到節(jié)點(diǎn)R1回復(fù)的CTS，在數(shù)據(jù)階段，節(jié)點(diǎn)S1向節(jié)點(diǎn)R1發(fā)送數(shù)據(jù)。由于節(jié)點(diǎn)S2收到節(jié)點(diǎn)R1回復(fù)給節(jié)點(diǎn)S1的CTS，所以在這個(gè)時(shí)隙內(nèi)節(jié)點(diǎn)S2標(biāo)記不發(fā)送數(shù)據(jù)。

當(dāng)T1=T2時(shí)，在T1微時(shí)隙內(nèi)的第一個(gè)子微時(shí)隙內(nèi)，節(jié)點(diǎn)S1、S2發(fā)送RTS，節(jié)點(diǎn)R1感知到RTS的碰撞，將不回復(fù)CTS；節(jié)點(diǎn)R2收到節(jié)點(diǎn)S2的RTS，在第二個(gè)子微時(shí)隙內(nèi)回復(fù)CTS，節(jié)點(diǎn)S2收到節(jié)點(diǎn)R2回復(fù)的CTS，則在數(shù)據(jù)階段節(jié)點(diǎn)S2向節(jié)點(diǎn)R2發(fā)送數(shù)據(jù)。

類似地，當(dāng)T1＞T2時(shí)，節(jié)點(diǎn)S2在數(shù)據(jù)階段向節(jié)點(diǎn)R2發(fā)送數(shù)據(jù)。

如果節(jié)點(diǎn)S1、S2在不同競(jìng)爭(zhēng)階段下，競(jìng)爭(zhēng)向節(jié)點(diǎn)R1、R2發(fā)送數(shù)據(jù)，則更為簡(jiǎn)單，同上所述。

另一個(gè)問題是802.11方式存在暴露終端問題。如圖4所示，如果節(jié)點(diǎn)S1向節(jié)點(diǎn)R1發(fā)送RTS，則節(jié)點(diǎn)S3收到節(jié)點(diǎn)S1的RTS并會(huì)保持沉默，同一時(shí)間內(nèi)不會(huì)發(fā)送數(shù)據(jù)。但在實(shí)際情況下，節(jié)點(diǎn)S3向節(jié)點(diǎn)R3發(fā)送數(shù)據(jù)，并不影響節(jié)點(diǎn)S1向節(jié)點(diǎn)R1發(fā)送數(shù)據(jù)。Q-TDMA協(xié)議可以保證節(jié)點(diǎn)S3在收到RTS后，仍能發(fā)送RTS或數(shù)據(jù)給節(jié)點(diǎn)R3。這樣就解決了暴露終端問題。

3.3 延遲分析

Ad hoc網(wǎng)絡(luò)中傳遞一個(gè)分組，其每跳傳遞的延遲[8]包括如下：

載波偵聽時(shí)延（Tcs）為發(fā)送節(jié)點(diǎn)進(jìn)行載波偵聽時(shí)花費(fèi)的時(shí)間，載波偵聽時(shí)延大小由競(jìng)爭(zhēng)窗口大小決定。

退避時(shí)延（Tb）為節(jié)點(diǎn)偵聽到另外一個(gè)或者發(fā)生碰撞而導(dǎo)致載波偵聽時(shí)所產(chǎn)生的時(shí)延。

傳輸時(shí)延（Ttx）由信道帶寬以及所采用的分組長(zhǎng)度和編碼方案決定。

傳播時(shí)延（Tprop）由發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離決定。在Ad hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)通信距離通常很短，因此通常忽略傳播延遲。

處理時(shí)延（Tproc）為節(jié)點(diǎn)在將所收分組轉(zhuǎn)發(fā)到下一個(gè)轉(zhuǎn)發(fā)跳之前對(duì)該分組所作處理而花費(fèi)的時(shí)間。

排隊(duì)時(shí)延（Tqueue）依賴于流量載荷。在重載荷情形下，排隊(duì)延遲變成一個(gè)支配因素。

上述時(shí)延是采用IEEE 802.11協(xié)議的多跳網(wǎng)絡(luò)的固有時(shí)延。

TDMA協(xié)議時(shí)延主要包括排隊(duì)延遲Tqueue，傳輸時(shí)延（時(shí)隙的大小Tslot），第n個(gè)轉(zhuǎn)發(fā)跳的時(shí)隙等待時(shí)延（Twait，n），處理時(shí)延Tproc。

Q-TDMA協(xié)議時(shí)延主要包括排隊(duì)延遲Tqueue，固定大小的監(jiān)聽競(jìng)爭(zhēng)延遲Tfixed，傳輸時(shí)延（數(shù)據(jù)時(shí)隙的大小TDATAslot），第n個(gè)轉(zhuǎn)發(fā)跳的時(shí)隙等待延遲（Twait，n），處理時(shí)延Tproc。

下面將從不同負(fù)載下分析在M跳網(wǎng)絡(luò)中MAC協(xié)議的時(shí)延。首先假設(shè)3種協(xié)議的傳輸時(shí)延相等。在流量負(fù)載較小（一個(gè)幀周期內(nèi)有一個(gè)數(shù)據(jù)包）時(shí)，沒有排隊(duì)延遲和退避延遲，另外假定傳播延遲和處理延遲可以忽略不計(jì)。在這種情形下，Q-TDMA協(xié)議的延遲為：

從公式（6）、（7）、（8），可以得到TDMA協(xié)議與IEEE 802.11協(xié)議的端到端延遲比較取決于M跳的時(shí)隙等待時(shí)延和M跳的載波偵聽時(shí)延；Q-TDMA協(xié)議的端到端延遲比TDMA多了M個(gè)固定大小的監(jiān)聽競(jìng)爭(zhēng)時(shí)延。

在流量負(fù)載較大時(shí)，IEEE 802.11因?yàn)榕鲎矊?dǎo)致偵聽時(shí)延Tcs，n（第n個(gè)轉(zhuǎn)發(fā)的偵聽時(shí)延）和退避時(shí)延Tb增大，使得端到端的延遲很大。Q-TDMA協(xié)議能夠根據(jù)隊(duì)列的長(zhǎng)度來復(fù)用時(shí)隙，從而可以有效地減少隊(duì)列延遲，并彌補(bǔ)了固定大小的監(jiān)聽競(jìng)爭(zhēng)時(shí)延。

在低負(fù)載下，Q-TDMA協(xié)議端到端延遲高于TDMA協(xié)議。在高負(fù)載下，Q-TDMA協(xié)議端到端延遲低于TDMA協(xié)議和IEEE 802.11協(xié)議（見仿真實(shí)驗(yàn)圖9）。

4 仿真及分析

將該協(xié)議與IEEE 802.11和傳統(tǒng)的TDMA進(jìn)行對(duì)比。

4.1 評(píng)價(jià)指標(biāo)

網(wǎng)絡(luò)吞吐量：網(wǎng)絡(luò)中所有節(jié)點(diǎn)每秒成功接收位數(shù)。端到端延遲：數(shù)據(jù)包從源節(jié)點(diǎn)發(fā)送出去，到目的節(jié)點(diǎn)收到數(shù)據(jù)包所消耗的時(shí)間。

4.2 仿真參數(shù)的設(shè)定

仿真工具采用NS2[9]，仿真的參數(shù)如表1。

表1 仿真參數(shù)表

4.3 仿真結(jié)果分析

本文在不同場(chǎng)景設(shè)置下仿真，并對(duì)吞吐量、端到端延遲進(jìn)行分析。

4.3.1 吞吐量仿真及分析

26個(gè)節(jié)點(diǎn)隨機(jī)分布在500 m×500 m場(chǎng)景下，仿真時(shí)間為80 s。本文根據(jù)不同數(shù)目的發(fā)送節(jié)點(diǎn)（不同負(fù)載和競(jìng)爭(zhēng)下），來分析比較在不同的生成數(shù)據(jù)包時(shí)間間隔下，3種協(xié)議吞吐量的變化。

圖5所示，當(dāng)生成數(shù)據(jù)包時(shí)間間隔在[0.13，0.11]之間時(shí)，3種協(xié)議隨著生成數(shù)據(jù)包間隔的減少，吞吐量呈線性增加。生成數(shù)據(jù)包時(shí)間間隔在[0.11，0.01]之間時(shí)，TDMA的吞吐量不變，且非常低，這是因?yàn)閭鹘y(tǒng)的TDMA只能在自己時(shí)隙內(nèi)發(fā)送數(shù)據(jù)，不能復(fù)用時(shí)隙，信道利用率低。由于網(wǎng)絡(luò)中發(fā)送節(jié)點(diǎn)很少，競(jìng)爭(zhēng)強(qiáng)度很低，802.11充分利用信道，所以802.11吞吐量要高于TDMA。由于Q-TDMA存在固定監(jiān)聽和競(jìng)爭(zhēng)時(shí)間，并比802.11的握手交換消耗的時(shí)間要長(zhǎng)，所以Q-TDMA的吞吐量低于802.11的吞吐量。與TDMA相比，Q-TDMA復(fù)用了時(shí)隙，因此Q-TDMA吞吐量高于TDMA。

圖5 發(fā)送節(jié)點(diǎn)為5個(gè)時(shí)的吞吐量

圖6所示，當(dāng)生成數(shù)據(jù)包時(shí)間間隔在[0.15，0.11]之間時(shí)，Q-TDMA、802.11和TDMA的吞吐量隨著生成數(shù)據(jù)包時(shí)間間隔的減少而增加，并且3種協(xié)議的吞吐量大致相等。這是由于在這個(gè)時(shí)間間隔范圍內(nèi)，產(chǎn)生數(shù)據(jù)包的能力低于節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的能力。生成數(shù)據(jù)包間隔在[0.11，0.01]之間時(shí)，Q-TDMA的每個(gè)節(jié)點(diǎn)可以保證在一個(gè)周期有一個(gè)固定的時(shí)隙來發(fā)送數(shù)據(jù)，同時(shí)也可以復(fù)用時(shí)隙發(fā)送數(shù)據(jù)，因此它的吞吐量要高于802.11和TDMA。

圖6 發(fā)送節(jié)點(diǎn)為20個(gè)時(shí)的吞吐量

圖7表示網(wǎng)絡(luò)中存在25個(gè)發(fā)送節(jié)點(diǎn)時(shí)，在這種高競(jìng)爭(zhēng)、高負(fù)載的網(wǎng)絡(luò)中，3種協(xié)議吞吐量的變化。由于802.11發(fā)送碰撞的概率非常大，它消耗大量的時(shí)間在數(shù)據(jù)重傳上，Q-TDMA和TDMA中每個(gè)節(jié)點(diǎn)在一個(gè)周期內(nèi)有一次固定的發(fā)送機(jī)會(huì)，所以在整個(gè)的發(fā)送間隔[0.14，0.05]中，Q-TDMA和TDMA的吞吐量都高于802.11。又由于Q-TDMA還可以根據(jù)節(jié)點(diǎn)的負(fù)載情況競(jìng)爭(zhēng)復(fù)用時(shí)隙，所以Q-TDMA的吞吐量比TDMA要高。

圖7 發(fā)送節(jié)點(diǎn)為25個(gè)時(shí)的吞吐量

4.3.2 延遲仿真及分析

18個(gè)節(jié)點(diǎn)分布在1 000 m×500 m的場(chǎng)景下，如圖8所示。

圖8 網(wǎng)絡(luò)拓?fù)鋱D

從0 s開始，網(wǎng)絡(luò)中啟動(dòng)第一條數(shù)據(jù)流（0～5）。隨后，每50 s增加一條的數(shù)據(jù)流（7～6，8～7，12～6，13～7，14～8，4～10，15～9，16～10），本文統(tǒng)計(jì)不同數(shù)目數(shù)據(jù)流下，節(jié)點(diǎn)0到節(jié)點(diǎn)5數(shù)據(jù)包的平均端到端延遲，仿真時(shí)間為450 s。

圖9表示隨著數(shù)據(jù)流數(shù)目的增加，網(wǎng)絡(luò)中平均端到端延遲的變化。在整個(gè)過程中，802.11隨著數(shù)據(jù)流個(gè)數(shù)的增加，競(jìng)爭(zhēng)節(jié)點(diǎn)會(huì)相繼增加，平均的端到端延遲逐漸增加。當(dāng)數(shù)據(jù)流數(shù)目增加到7條時(shí)，TDMA協(xié)議延遲突然增大，這是因?yàn)閿?shù)據(jù)包在節(jié)點(diǎn)4上出現(xiàn)了隊(duì)列排隊(duì)延遲，導(dǎo)致數(shù)據(jù)包的端到端延遲增加；與TDMA相比，由于Q-TDMA可以復(fù)用時(shí)隙，數(shù)據(jù)包在節(jié)點(diǎn)4上沒有產(chǎn)生額外的隊(duì)列排隊(duì)延遲，所以Q-TDMA的延遲保持不變。

圖9 平均端到端延遲

5 結(jié)論

本文提出了一種競(jìng)爭(zhēng)與固定分配相結(jié)合的Q-TDMA協(xié)議。它將TDMA與同步CSMA/CA機(jī)制相結(jié)合，并根據(jù)本節(jié)點(diǎn)的負(fù)載情況來選擇競(jìng)爭(zhēng)信道。從NS2仿真實(shí)驗(yàn)可以看出，與IEEE 802.11和傳統(tǒng)的TDMA相比，Q-TDMA協(xié)議有效地提高了網(wǎng)絡(luò)的吞吐量，降低了端到端的延遲。在今后的研究中，還需要對(duì)Q-TDMA做進(jìn)一步的理論分析和驗(yàn)證，設(shè)計(jì)更加復(fù)雜的仿真和實(shí)驗(yàn)?zāi)Ｐ汀?/p>

[1]Abramson N.TheALOHA system-anotheralternative for computer communications[C]//Proceedings of the Fall Joint Computer Conference，1970：281-285.

[2]Tobagi F，Kleinrock L.Packet switching in radio channels I. Carrier sense multiple access models and their throughput delay characteristics[J].IEEE Transactions on Communications COM，1975，23（12）：1400-1416.

[3]Fullmerc L，Garcia-Luna-Acevje S.Floor Acquisition Multiple Access（FAMA）for packet-radio networks[C]//Proceedings of ACM SIGCOMM，1995.

[4]Karn P.MACA-a new channel access protocol for packet radio[C]//ARRUCRRL Amateur Radio Ninth Computer Networking Conference，1990：134-140.

[5]IEEE Draft Standard P802.11 Wireless LAN Wireless Medium Access Control and Physical Layer WG[S].IEEE Standards Department，1996-01.

[6]Zhu C，Corson M S.An evolutionary-TDMA scheduling protocol（ETDMA） formobile Adhocnetworks，Technical Research Report CSHCN TR 2001-17[R].2001.

[7]Chlamtac I.ADAPT：a dynamically self-adjusting media access controlprotocolforAd hoc networks[C]//Proceedings of the IEEE Globecom，1999.

[8]Ye W，Heidemann J，Estrin D.An energy-efficient MAC protocol for wireless sensor networks[C]//Proc IEEE INFOCOM，New York，NY，June 2002：1567-1576.

[9]NS2[EB/OL].[2011-07].http：//www.isi.edu/nsnam/ns.

[10]Ni J，Tan B R，Srikant R.Q-CSMA：queue-length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[C]//Proceedings of the 29th International Conference on Information Communication，March 14-19，2010：271-275.

[11]Durvy M，Thiran P.Packing approach to compare slotted and nonslotted medium access control[C]//Proceedings of IEEE INFOCOM，April 2006.

[12]Wu X，Srikant R，Perkins J R.Queue-length stability of maximalgreedy schedules in wireless networks[J].IEEE Transactions on Mobile Computing，2007：595-605.

PAN Peng,GUO Dawei,LIU Hang,WANG Peng

西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，西安 710129

School of Automation,Northwestern Polytechnical University,Xi'an 710129,China

Queue-length based Time Division Multiple Access（Q-TDMA）is a new Media Access Control（MAC）protocol.Its purpose is to resolve poor throughput for IEEE 802.11 with high competition and TDMA with low loads.TDMA protocol can guarantee that each node has a chance to send in a cycle,while synchronous Carrier Sense Multiple Access with Collision Avoidance（CSMA/CA）mechanism can solve the hidden terminal and exposed terminal problem.Combining with the advantages of TDMA and synchronous CSMA/CA mechanism,Q-TDMA demands that node needs to contend to access channel based on its'own queue length.According to the simulation results,Q-TDMA improves the network throughput and reduces end to end delay.

Ad hoc network;Time Division Multiple Access（TDMA）;Media Access Control（MAC）;Queue-length based TDMA（Q-TDMA）

A

TP393

10.3778/j.issn.1002-8331.1109-0068

PAN Peng,GUO Dawei,LIU Hang,et al.New combination of contention and allocation MAC protocol.Computer Engineering and Applications,2013,49（7）：76-80.

西北工業(yè)大學(xué)研究生創(chuàng)業(yè)種子基金資助項(xiàng)目（No.Z2011052）。

潘鵬（1985—），男，碩士研究生，研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)MAC協(xié)議以及路由協(xié)議；郭達(dá)偉（1968—），男，副教授，碩士生導(dǎo)師，主要從事信息安全、網(wǎng)絡(luò)化控制、無(wú)線傳感器網(wǎng)絡(luò)等方向的研究工作；劉航（1973—），男，副教授，碩士生導(dǎo)師，主要從事密碼硬件與嵌入式系統(tǒng)、嵌入式網(wǎng)絡(luò)系統(tǒng)、嵌入式系統(tǒng)軟硬件協(xié)同開發(fā)的研究與應(yīng)用；王鵬（1985—），男，碩士研究生，主要研究領(lǐng)域?yàn)闊o(wú)線自組網(wǎng)網(wǎng)絡(luò)路由協(xié)議。E-mail：5829panpeng@163.com

2011-09-05

2011-10-30

1002-8331（2013）07-0076-05

CNKI出版日期：2012-01-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120116.0928.063.html