一種改進的Ad hoc網絡中動態TDMA時隙分配方法

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

總參謀部第61研究所 陳 強

1.引言

Ad hoc網絡是一種不依賴基礎設施的網絡，網絡中的節點均是有移動主機構成，它們可以在沒有提前配置的情況下自由進出網絡，這種靈活性促使了相應MAC協議的開發，我們根據他們的發送機制可以將其劃分為兩大類。

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

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

因此，本文提出一種新的TDMA時隙分配協議來克服上述這些缺點，我們的協議不需要提前知道網絡的信息，而且根據競爭區域內節點數量和帶寬需求的變化動態的改變幀長和發送機制，這里競爭區域指的是對于每個節點，兩跳之內的節點的集合。

2.USAP和FPRP簡介

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

節點間通過一系列的信息交換使每個節點了解存在的未分配時隙的狀態并在其中為自己分配一個時隙使用。因為每個節點收到一個新節點管理操作信息包NMOP時都會刷新自己的統一時隙分配協議USAP，所以統一時隙分配協議可以反映出網絡內節點的存在狀況。

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

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

3.E-DTSAP協議

3.1 簡介

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

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

圖2 FPRP協議幀格式

圖3 E-DTSAP的幀格式

圖4 數據包格式

圖5 控制包格式

圖6 初始狀態下時隙分配過程

圖7 發送狀態下時隙分配過程

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

3.2 幀格式

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

3.3 包格式

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

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

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

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

3.4 時隙分配

傳統的第二類MAC協議需要提前知道網絡信息，當網路拓撲動態變化時，在初始狀態下進行的時隙分配并不是一直保持有效，而E-DTSAP協議中，不僅在初始狀態下而且在發送狀態下時隙分配都能隨網絡參數的變化做出相應的調整從而適應網絡變化。

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

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

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

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

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

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

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

4.仿真分析

這里，我們將本協議與傳統的第二類MAC協議及802.11協議做了對比，在仿真環境中，我們假設網絡中有50個節點，節點通信采用CBR，目的節點在鄰居中隨機選擇，我們觀察了平均吞吐量及發送延遲與D的關系，其中D表示的是節點的鄰居節點的最大數目。

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

5.結束語

本文中，我們提出了一種改進的動態TDMA時隙分配協議，它可以根據競爭區域內節點數目動態改變幀長和發送機制，而且我們的協議不需要提前知道網絡的信息，通過與鄰居節點的信息進行相互通知和認證來完成時隙預約。它可以很好的適應于實際的Ad hoc網絡。

[1]郝莉,陳彥輝,張彪.一種適于Ad hoc網的改進型TDMA協議[J].北京電子科技學院學報,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網絡中的動態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網絡技術[M].北京:人民郵電出版社,2005.