一種改進的Ad hoc網(wǎng)絡(luò)中動態(tài)TDMA時隙分配方法

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

總參謀部第61研究所 陳 強

1.引言

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

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

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

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

2.USAP和FPRP簡介

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

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

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

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

3.E-DTSAP協(xié)議

3.1 簡介

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

圖1 USAP下的TDMA時隙示意圖[4]

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

圖3 E-DTSAP的幀格式

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

圖5 控制包格式

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

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

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

3.2 幀格式

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

3.3 包格式

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

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

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

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

3.4 時隙分配

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

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

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

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

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

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

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

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

4.仿真分析

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

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

5.結(jié)束語

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

[1]郝莉,陳彥輝,張彪.一種適于Ad hoc網(wǎng)的改進型TDMA協(xié)議[J].北京電子科技學(xué)院學(xué)報,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ò)中的動態(tài)TDMA時隙分配[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.