解放軍理工大學(xué)通信工程學(xué)院研三隊(duì) 王寶康

總參謀部第61研究所 陳 強(qiáng)

1.引言

Ad hoc網(wǎng)絡(luò)是一種不依賴(lài)基礎(chǔ)設(shè)施的網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)均是有移動(dòng)主機(jī)構(gòu)成，它們可以在沒(méi)有提前配置的情況下自由進(jìn)出網(wǎng)絡(luò)，這種靈活性促使了相應(yīng)MAC協(xié)議的開(kāi)發(fā)，我們根據(jù)他們的發(fā)送機(jī)制可以將其劃分為兩大類(lèi)。

第一類(lèi)MAC協(xié)議是基于競(jìng)爭(zhēng)的協(xié)議，基于載波偵聽(tīng)/沖突避免（CSMA/CA）的IEEE 802.11協(xié)議就是常見(jiàn)的第一類(lèi)協(xié)議。雖然它被廣泛應(yīng)用，但是它基于競(jìng)爭(zhēng)的機(jī)制使得預(yù)約帶寬難以實(shí)現(xiàn)。

第二類(lèi)MAC協(xié)議是沒(méi)有競(jìng)爭(zhēng)的協(xié)議，如時(shí)分多址（Time division multiple access）協(xié)議，每個(gè)節(jié)點(diǎn)預(yù)先都被安排了一系列時(shí)隙用于滿(mǎn)足發(fā)送要求，同時(shí)較好的適合Qos（Quality of service）要求。但是，即便是知道了準(zhǔn)確詳盡的信息也很難提出一種最優(yōu)的時(shí)隙分配機(jī)制。在前期提出的一些協(xié)議中，節(jié)點(diǎn)依靠提前定義的網(wǎng)絡(luò)信息逐個(gè)進(jìn)行時(shí)隙預(yù)約分配，結(jié)果是這些協(xié)議本身對(duì)網(wǎng)絡(luò)拓?fù)湟蕾?lài)較大，如果網(wǎng)絡(luò)拓?fù)浜蛶捫枨髣?dòng)態(tài)變化的話，則會(huì)導(dǎo)致無(wú)用時(shí)隙的急劇增加。

因此，本文提出一種新的TDMA時(shí)隙分配協(xié)議來(lái)克服上述這些缺點(diǎn)，我們的協(xié)議不需要提前知道網(wǎng)絡(luò)的信息，而且根據(jù)競(jìng)爭(zhēng)區(qū)域內(nèi)節(jié)點(diǎn)數(shù)量和帶寬需求的變化動(dòng)態(tài)的改變幀長(zhǎng)和發(fā)送機(jī)制，這里競(jìng)爭(zhēng)區(qū)域指的是對(duì)于每個(gè)節(jié)點(diǎn)，兩跳之內(nèi)的節(jié)點(diǎn)的集合。

2.USAP和FPRP簡(jiǎn)介

USAP，即統(tǒng)一時(shí)隙分配協(xié)議（Unifying slot assignment protocol）和五階段預(yù)約協(xié)議（five-phase reservation protocol）是兩種傳統(tǒng)的第二類(lèi)MAC協(xié)議。前者由戴維·楊提出，目前在TDMA中大量使用。圖1是TDMA在USAP中的形式，它由N個(gè)幀組成，每幀由M個(gè)時(shí)隙組成，M和N都是定值。每個(gè)幀的第一個(gè)時(shí)隙用于描述該傳送節(jié)點(diǎn)的控制信息包，叫做NMOP(節(jié)點(diǎn)管理操作信息包)。這樣,統(tǒng)一分配時(shí)隙協(xié)議USAP允N個(gè)節(jié)點(diǎn)存在于網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)擁有相應(yīng)的NMOP(節(jié)點(diǎn)管理操作信息包)，這N個(gè)幀組成一個(gè)循環(huán)。

節(jié)點(diǎn)間通過(guò)一系列的信息交換使每個(gè)節(jié)點(diǎn)了解存在的未分配時(shí)隙的狀態(tài)并在其中為自己分配一個(gè)時(shí)隙使用。因?yàn)槊總€(gè)節(jié)點(diǎn)收到一個(gè)新節(jié)點(diǎn)管理操作信息包NMOP時(shí)都會(huì)刷新自己的統(tǒng)一時(shí)隙分配協(xié)議USAP，所以統(tǒng)一時(shí)隙分配協(xié)議可以反映出網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的存在狀況。

圖2給出了FPRP協(xié)議的幀格式，幀中有一個(gè)由一系列信息幀IF（Information frames）組成的預(yù)約幀RF（Reservation frames），每個(gè)信息幀IF內(nèi)有N個(gè)信息時(shí)隙IS（Information slots），每個(gè)RF內(nèi)又有N個(gè)預(yù)約時(shí)隙RS（Reservation slots），每個(gè)RS和相應(yīng)的IS相對(duì)應(yīng)。如果一個(gè)節(jié)點(diǎn)要預(yù)約IS，則首先競(jìng)爭(zhēng)相應(yīng)的RS。一個(gè)RS由M個(gè)預(yù)約循環(huán)RC（Reservation cycle）組成，每個(gè)RC由五個(gè)階段的對(duì)話組成，通過(guò)這五階段對(duì)話競(jìng)爭(zhēng)節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)完成預(yù)約。

有上述可以看出，無(wú)論USAP還是FPRP，網(wǎng)絡(luò)的主要參數(shù)例如節(jié)點(diǎn)數(shù)N和時(shí)隙數(shù)M都需提前知道，這在實(shí)際的Ad hoc網(wǎng)絡(luò)中不易實(shí)現(xiàn)，因?yàn)锳d hoc網(wǎng)絡(luò)最大的特點(diǎn)就是其動(dòng)態(tài)變化這點(diǎn)，因此有必要提出一種新的TDMA時(shí)隙分配協(xié)議，能夠根據(jù)節(jié)點(diǎn)數(shù)目動(dòng)態(tài)的調(diào)整這些參數(shù)的方法。

3.E-DTSAP協(xié)議

3.1 簡(jiǎn)介

E-DTSAP協(xié)議，即改進(jìn)的TDMA時(shí)隙分配協(xié)議（Evolutionary-dynamic TDMA slot assignment protocol），它可以讓節(jié)點(diǎn)隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化相應(yīng)的對(duì)時(shí)隙進(jìn)行重新分配。在此協(xié)議中，所有節(jié)點(diǎn)地位平等，通過(guò)這種方式，E-DTSAP允許存在同時(shí)預(yù)約的現(xiàn)象。如果由于拓?fù)浣Y(jié)構(gòu)變化使得沖突發(fā)生，那么發(fā)送者從接收者那里得知消息并停止在此時(shí)隙的發(fā)送。同時(shí)，如果有必要，可以對(duì)其他未分配的時(shí)隙進(jìn)行預(yù)約。發(fā)送完成后，發(fā)送者釋放被分配的時(shí)隙，此時(shí)隙又可以被其他節(jié)點(diǎn)預(yù)約。

圖1 USAP下的TDMA時(shí)隙示意圖[4]

圖2 FPRP協(xié)議幀格式

圖3 E-DTSAP的幀格式

圖4 數(shù)據(jù)包格式

圖5 控制包格式

圖6 初始狀態(tài)下時(shí)隙分配過(guò)程

圖7 發(fā)送狀態(tài)下時(shí)隙分配過(guò)程

圖8 吞吐量(T)、發(fā)送時(shí)延(Delay)與D的關(guān)系

3.2 幀格式

如圖3所示，在此協(xié)議中，幀長(zhǎng)被設(shè)置為2的冪次數(shù)長(zhǎng)度，其中第一個(gè)時(shí)隙預(yù)留給新節(jié)點(diǎn)用于發(fā)送控制報(bào)文來(lái)完成時(shí)隙分配請(qǐng)求，因此，在此時(shí)隙內(nèi)不發(fā)送任何數(shù)據(jù)。M是一個(gè)正整數(shù)，每個(gè)時(shí)隙都包含4個(gè)子時(shí)隙（Minislot），同時(shí)，minislot 0和minislot 1又可以進(jìn)一步被劃分為兩個(gè)控制域，即RTS和CTS。這些控制域用來(lái)完成預(yù)約未分配時(shí)隙和防止隱藏終端沖突。如果一個(gè)節(jié)點(diǎn)在其分配的時(shí)隙內(nèi)有數(shù)據(jù)要發(fā)送，則首先應(yīng)當(dāng)通過(guò)minislot 0中的RTS和CTS與對(duì)應(yīng)的接收節(jié)點(diǎn)完成握手，當(dāng)握手過(guò)程完成后，節(jié)點(diǎn)在相應(yīng)時(shí)隙的DATA子時(shí)隙內(nèi)發(fā)送數(shù)據(jù)包，同時(shí)在同一時(shí)隙等待數(shù)據(jù)ACK回應(yīng)。如果任何節(jié)點(diǎn)在時(shí)隙的minislot 0時(shí)隙都感知信道是空閑的，那么此時(shí)隙被標(biāo)記為未分配時(shí)隙，可以被預(yù)約。當(dāng)一個(gè)節(jié)點(diǎn)想要預(yù)約未分配時(shí)隙時(shí)，首先應(yīng)當(dāng)通過(guò)RTS的minislot 1向?qū)?yīng)的接收節(jié)點(diǎn)發(fā)送時(shí)隙預(yù)約請(qǐng)求，如果接受者成功接收到這個(gè)請(qǐng)求，它通過(guò)同一時(shí)隙的CTS域向發(fā)送者回復(fù)預(yù)約認(rèn)證信息。只有當(dāng)節(jié)點(diǎn)在minislot 1內(nèi)競(jìng)爭(zhēng)成功后，DATA子時(shí)隙才可以用于發(fā)送數(shù)據(jù)，并且在后繼幀中的相同時(shí)隙都可以預(yù)約給此節(jié)點(diǎn)直至包發(fā)送完成。

3.3 包格式

在E-DTSAP中有兩種數(shù)據(jù)包，發(fā)送包和控制包，不同的方式對(duì)應(yīng)不同的節(jié)點(diǎn)運(yùn)行。在發(fā)送狀態(tài)下，如果有必要，節(jié)點(diǎn)發(fā)送數(shù)據(jù)包和控制包通過(guò)預(yù)約未分配時(shí)隙用于重新安排時(shí)隙分配，另一方面，新節(jié)點(diǎn)在初始狀態(tài)通過(guò)發(fā)送控制包以獲得足夠的信息從而完成時(shí)隙分配。數(shù)據(jù)包的形式如下：

如圖4所示，數(shù)據(jù)包包括數(shù)據(jù)形式、發(fā)送者ID、目的ID、時(shí)隙分配信息及發(fā)送節(jié)點(diǎn)及其鄰居最大幀長(zhǎng)和數(shù)據(jù)。

在E-DTSAP中，總共有12種控制包類(lèi)型，每種包都有不同的作用，如圖5：

請(qǐng)求包只有新節(jié)點(diǎn)發(fā)送，通過(guò)向鄰居發(fā)送此包，新節(jié)點(diǎn)請(qǐng)求競(jìng)爭(zhēng)區(qū)域內(nèi)所有節(jié)點(diǎn)的關(guān)于幀長(zhǎng)和時(shí)隙分配的信息；時(shí)隙信息包包含所有信息；時(shí)隙預(yù)約包同樣由新節(jié)點(diǎn)發(fā)送，通過(guò)發(fā)送此包給鄰居，新節(jié)點(diǎn)通知其他節(jié)點(diǎn)預(yù)約的幀長(zhǎng)和時(shí)隙信息；回復(fù)包是為了作為接收時(shí)隙預(yù)約包的確認(rèn)；時(shí)隙保持包由保持被分配時(shí)隙且沒(méi)有包要發(fā)送的節(jié)點(diǎn)發(fā)送；RTS包由需要發(fā)送包的節(jié)點(diǎn)通過(guò)minislot 0中的RTS域來(lái)發(fā)送；CTS包由相應(yīng)的接收節(jié)點(diǎn)作為發(fā)送包接收請(qǐng)求的回應(yīng)通過(guò)相同子時(shí)隙的CTS域發(fā)送。當(dāng)此握手過(guò)程完成后，節(jié)點(diǎn)在DATA微時(shí)隙發(fā)送相應(yīng)的數(shù)據(jù)包，在ACK微時(shí)隙發(fā)送相應(yīng)的ACK包作為接收包的確認(rèn)信息；當(dāng)節(jié)點(diǎn)需要預(yù)約未分配時(shí)隙時(shí)，在minislot 1的RTS域發(fā)送時(shí)隙重分配包，同理在相應(yīng)的接收節(jié)點(diǎn)會(huì)發(fā)送ACK包作為收到包的確認(rèn)信息。

3.4 時(shí)隙分配

傳統(tǒng)的第二類(lèi)MAC協(xié)議需要提前知道網(wǎng)絡(luò)信息，當(dāng)網(wǎng)路拓?fù)鋭?dòng)態(tài)變化時(shí)，在初始狀態(tài)下進(jìn)行的時(shí)隙分配并不是一直保持有效，而E-DTSAP協(xié)議中，不僅在初始狀態(tài)下而且在發(fā)送狀態(tài)下時(shí)隙分配都能隨網(wǎng)絡(luò)參數(shù)的變化做出相應(yīng)的調(diào)整從而適應(yīng)網(wǎng)絡(luò)變化。

如圖6中所示，如果一個(gè)新節(jié)點(diǎn)需要加入網(wǎng)絡(luò)，它需要知道競(jìng)爭(zhēng)區(qū)域內(nèi)其他節(jié)點(diǎn)的幀長(zhǎng)和時(shí)隙分配的信息。為了得到這些信息，新節(jié)點(diǎn)首先需要偵聽(tīng)信道并且檢查從鄰居節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包，在收集到這些信息后，新節(jié)點(diǎn)就知道了競(jìng)爭(zhēng)區(qū)域內(nèi)一幀中的最大幀長(zhǎng)及第一個(gè)時(shí)隙的位置，然后，新節(jié)點(diǎn)在下一幀的第一個(gè)時(shí)隙廣播發(fā)送一個(gè)請(qǐng)求包并且等待所有接收到此包的鄰居節(jié)點(diǎn)發(fā)送時(shí)隙信息包。

在接收時(shí)隙信息包之前，新節(jié)點(diǎn)應(yīng)當(dāng)通過(guò)minislot 0的RTS和CTS域來(lái)完成握手過(guò)程，如果沒(méi)有沖突發(fā)生，在收集到所有鄰居的時(shí)隙信息包后，新節(jié)點(diǎn)開(kāi)始進(jìn)行時(shí)隙分配過(guò)程，如果有沖突，新節(jié)點(diǎn)回到載波偵聽(tīng)階段，此過(guò)程一致重復(fù)知道新節(jié)點(diǎn)從所有鄰居那收集到時(shí)隙信息包為止。

當(dāng)新節(jié)點(diǎn)開(kāi)始時(shí)隙分配時(shí)，它首先將它的幀長(zhǎng)設(shè)置為競(jìng)爭(zhēng)區(qū)域內(nèi)最大幀長(zhǎng)，這里，F(xiàn)0表示新節(jié)點(diǎn)的幀長(zhǎng)，由于新節(jié)點(diǎn)知道競(jìng)爭(zhēng)區(qū)域內(nèi)時(shí)隙分配的全部信息，因此它可以實(shí)現(xiàn)無(wú)沖突時(shí)隙分配。如果一個(gè)鄰居的幀長(zhǎng)與新節(jié)點(diǎn)幀長(zhǎng)相同，均為F0，則新節(jié)點(diǎn)復(fù)制接收到的時(shí)隙信息包中的內(nèi)容，如果F0=αFi，其中Fi為鄰居的幀長(zhǎng)，α為一個(gè)2的冪次數(shù)的整數(shù)，那么新節(jié)點(diǎn)每隔F0/α?xí)r隙重復(fù)復(fù)制時(shí)隙分配信息，通過(guò)這種方法，新節(jié)點(diǎn)將所有來(lái)自鄰居節(jié)點(diǎn)的信息融合起來(lái)并且形成自己的時(shí)隙分配表。

此時(shí)，如果在時(shí)隙分配表中有未分配的時(shí)隙存在，那么新節(jié)點(diǎn)將預(yù)約其中的一個(gè)給自己使用；如果沒(méi)有發(fā)現(xiàn)未分配的時(shí)隙，新節(jié)點(diǎn)檢查競(jìng)爭(zhēng)區(qū)域內(nèi)的節(jié)點(diǎn)，是否有一個(gè)節(jié)點(diǎn)占有多個(gè)時(shí)隙的情況，如果有，則占有時(shí)隙較多的那個(gè)節(jié)點(diǎn)被要求釋放一個(gè)時(shí)隙給新節(jié)點(diǎn)使用，如果以上兩種情況均未出現(xiàn)，則新節(jié)點(diǎn)需將幀長(zhǎng)加倍，如前所述，由于第一個(gè)節(jié)點(diǎn)不分配給任何節(jié)點(diǎn)，因此，在加倍后，后半部分的第一個(gè)時(shí)隙將為空時(shí)隙，可以被分配給新節(jié)點(diǎn)使用。

在完成時(shí)隙分配后，新節(jié)點(diǎn)想鄰居節(jié)點(diǎn)廣播分送一個(gè)時(shí)隙預(yù)約包，接收到此包的鄰居節(jié)點(diǎn)發(fā)送相應(yīng)的回復(fù)包。在接收回復(fù)包之前，新節(jié)點(diǎn)需要與鄰居節(jié)點(diǎn)通過(guò)mi-nislot 0的RTS和CTS域完成握手。如果沒(méi)有沖突，在收集了所有回復(fù)包之后，新節(jié)點(diǎn)完成它的時(shí)隙分配并準(zhǔn)備發(fā)送數(shù)據(jù)；如果存在沖突，新節(jié)點(diǎn)回到載波偵聽(tīng)階段，此過(guò)程重復(fù)直至新節(jié)點(diǎn)完成自己的時(shí)隙分配。

如圖7所示，在完成時(shí)隙分配后，新節(jié)點(diǎn)準(zhǔn)備在自己的時(shí)隙內(nèi)發(fā)送數(shù)據(jù)，在一個(gè)分配時(shí)隙的初始，首先應(yīng)當(dāng)判斷是否存在數(shù)據(jù)包要發(fā)送，如果有數(shù)據(jù)包需要發(fā)送，則應(yīng)當(dāng)在minislot 0的RTS和CTS域與接收節(jié)點(diǎn)完成握手，當(dāng)此過(guò)程完成后，節(jié)點(diǎn)在被分配的時(shí)隙內(nèi)的DATA子時(shí)隙發(fā)送數(shù)據(jù)包，接收到數(shù)據(jù)包的節(jié)點(diǎn)在同一時(shí)隙的ACK微時(shí)隙發(fā)送數(shù)據(jù)ACK包作為回應(yīng)，如果沒(méi)有接收到ACK包，則發(fā)送者不得不重新進(jìn)行時(shí)隙分配并釋放當(dāng)前時(shí)隙。

在未分配時(shí)隙初始，發(fā)送者估計(jì)網(wǎng)絡(luò)拓?fù)浜妥约旱膸捫枨?，如果發(fā)現(xiàn)信道是空閑的并且需要預(yù)約時(shí)隙時(shí)，應(yīng)當(dāng)通過(guò)mi-nislot 1的RTS域發(fā)送時(shí)隙重分配包，相應(yīng)的接收者收到此包后在CTS域發(fā)送一個(gè)ACK作為回應(yīng)，在接收到ACK后，發(fā)送者進(jìn)行時(shí)隙分配并通過(guò)DATA子時(shí)隙發(fā)送數(shù)據(jù)，否則，發(fā)送者返回等待狀態(tài)并保持原來(lái)的時(shí)隙分配狀態(tài)。

4.仿真分析

這里，我們將本協(xié)議與傳統(tǒng)的第二類(lèi)MAC協(xié)議及802.11協(xié)議做了對(duì)比，在仿真環(huán)境中，我們假設(shè)網(wǎng)絡(luò)中有50個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)通信采用CBR，目的節(jié)點(diǎn)在鄰居中隨機(jī)選擇，我們觀察了平均吞吐量及發(fā)送延遲與D的關(guān)系，其中D表示的是節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的最大數(shù)目。

由圖八（1）的結(jié)果我們得知，隨著D的不斷變化，E-DTSAP協(xié)議的吞吐量在各個(gè)階段都明顯高于其余協(xié)議，這與設(shè)計(jì)目的一致。同時(shí)，隨著D的增加，平均吞吐量降到一定值（大約0.02），而且E-DTSAP的下降比較平滑，這是因?yàn)樵絹?lái)越多的鄰居節(jié)點(diǎn)將會(huì)導(dǎo)致更多的干擾和更少的分配時(shí)隙；圖八（2）顯示出E-DTSAP協(xié)議相比其余協(xié)議，有最低的發(fā)送時(shí)延；在隨D變化過(guò)程中，D越大，將導(dǎo)致更多的干擾和越來(lái)越少的分配時(shí)隙，因此，發(fā)送時(shí)延幾乎呈線性增長(zhǎng)。

5.結(jié)束語(yǔ)

本文中，我們提出了一種改進(jìn)的動(dòng)態(tài)TDMA時(shí)隙分配協(xié)議，它可以根據(jù)競(jìng)爭(zhēng)區(qū)域內(nèi)節(jié)點(diǎn)數(shù)目動(dòng)態(tài)改變幀長(zhǎng)和發(fā)送機(jī)制，而且我們的協(xié)議不需要提前知道網(wǎng)絡(luò)的信息，通過(guò)與鄰居節(jié)點(diǎn)的信息進(jìn)行相互通知和認(rèn)證來(lái)完成時(shí)隙預(yù)約。它可以很好的適應(yīng)于實(shí)際的Ad hoc網(wǎng)絡(luò)。

[1]郝莉,陳彥輝,張彪.一種適于Ad hoc網(wǎng)的改進(jìn)型TDMA協(xié)議[J].北京電子科技學(xué)院學(xué)報(bào),2005.

[2]Wei Li,Ji-Bo Wei,Shan Wang.Dynamic TDMA Slot Assignment Protocol for multihop ad hoc networks,Communication Technology,2006.

[3]C.D.Young.USAP:a unifying dynamic distributed multichannel TDMA slot assignment protocol,in Proc.IEEE MILCOM’96,1996,235-239.

[4]楊棣,梁剛.在Ad hoc網(wǎng)絡(luò)中的動(dòng)態(tài)TDMA時(shí)隙分配[J].電子科技,2009,11.

[5]Chenxi Zhu and M.S.Corson.A Five-Phase Reservation Protocol(FPRP)for Mobile Ad hoc Networks,in Proc.IEEE INFOCOM’98,1998,322-331.

[6]Kanzaki A,et al,Dynamic TDMA Slot Assignment in Ad hoc Networks,in Proc.IEEE AINA’03,2003,300-335.

[7]鄭少仁,王海濤,趙志峰等.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京:人民郵電出版社,2005.