陶 洋 ，喬會學，譚 鵬，羅啟涵

(重慶郵電大學通信與信息工程學院，重慶400065)

AdHoc網(wǎng)絡(luò)的分布式和自組織特性使得它的媒體接入控制(MAC)協(xié)議設(shè)計極具挑戰(zhàn)性，時分多址接入(TDMA)技術(shù)在自由競爭的基礎(chǔ)上通過對無線信道資源進行時隙劃分，可以高效地利用有限的無線信道資源，目前，已經(jīng)有許多基于TDMA的分布式MAC方案［1-3］。例如，五階段預(yù)留協(xié)議(FPRP)需要5個階段預(yù)留過程來完成TDMA時隙的分配［4］;E-TDMA協(xié)議需要節(jié)點為一跳范圍內(nèi)的鄰居節(jié)點預(yù)留無沖突時隙，并利用預(yù)留時隙向鄰居節(jié)點單播、多播、廣播數(shù)據(jù)包［5］。在分布式分組預(yù)留多址接入(D-PRMA)協(xié)議中，節(jié)點分為傳輸語音和數(shù)據(jù)的節(jié)點，同時一個時隙被分為多個微時隙。但是，這些協(xié)議都不支持超過兩跳的多跳實時數(shù)據(jù)包傳輸，同時，D-PRMA沒有考慮節(jié)點的移動性，F(xiàn)PRP和E-TDMA只是限制性地考慮了節(jié)點移動性，F(xiàn)PRP假定節(jié)點在網(wǎng)絡(luò)拓撲不發(fā)生變化的網(wǎng)絡(luò)中移動，且要求節(jié)點移動速度非常慢，E-TDMA假定網(wǎng)絡(luò)沒有被分隔，如果在一個節(jié)點的通信范圍內(nèi)沒有其他節(jié)點，該節(jié)點將會隨機選擇一個新的目的節(jié)點，并且強制性地移向這個節(jié)點。這在實際應(yīng)用中很不實用，因此，本文提出一種MANET中支持實時應(yīng)用的基于TDMA的時隙預(yù)留協(xié)議(TMSR)，TMSR為多跳數(shù)據(jù)包傳輸進行信道資源預(yù)留，同時，當一個節(jié)點丟失時，TMSR通過快速故障點檢測和高效的資源釋放機制來支持節(jié)點移動性。

1 TMSR協(xié)議

TMSR超幀結(jié)構(gòu)，如圖1所示，關(guān)于超幀的基本概念請參考文獻［6］，在TMSR協(xié)議中，信道時間被分成多個超幀，每個超幀由3個主要部分組成，分別是beacon期(BP)、數(shù)據(jù)傳輸期(DTP)和時隙預(yù)留期(SRP)，每個超幀以BP開始，一個BP由m個競爭時隙和n個beacon時隙組成，節(jié)點加入網(wǎng)絡(luò)，首先通過競爭時隙獲得一個beacon時隙，一個競爭時隙包括1 byte的前同步碼、6 byte的節(jié)點MAC地址、1 byte的beacon時隙索引(BSI)和4 byte的前向錯誤控制(FEC)域，其中，BSI是在BP期為節(jié)點分配的時隙號，如果一個節(jié)點被分配了beacon時隙，那么節(jié)點將在每個超級幀中傳輸其beacon。一個beacon時隙包括1 byte的前同步碼，6 byte的節(jié)點MAC地址，112 byte(7 byte×16 neighbors)的一跳范圍內(nèi)鄰居節(jié)點列表、32 byte的資源映射表和4 byte的前向錯誤控制(FEC)域，其中，節(jié)點一跳范圍內(nèi)的鄰居節(jié)點列表由6 byte的節(jié)點MAC地址和1 byte的BSI組成，資源映射表顯示DTP中處于激活的每個時隙的預(yù)留狀態(tài)。節(jié)點根據(jù)它在beacon時隙監(jiān)聽的鄰居節(jié)點的beacons更新它的鄰居表和資源映射表。在節(jié)點被成功分配了beacon時隙后，當有數(shù)據(jù)需要傳輸時，節(jié)點首先在BP和DTP沒有預(yù)留的時隙中，通過載波監(jiān)聽多路訪問(CSMA)方式執(zhí)行多跳信道時隙預(yù)留過程。如果在BP和DTP沒有可用的時隙，節(jié)點將會在RRP中執(zhí)行多跳時隙預(yù)留過程，最后，如果多跳信道預(yù)留過程完成，節(jié)點將會通過DTP預(yù)留的時隙進行數(shù)據(jù)傳輸。

圖1 TMSR協(xié)議超幀結(jié)構(gòu)圖［6］

1.1 BP創(chuàng)建和beacon時隙分配過程

首先，本文假定每個節(jié)點保持全球時隙同步，因此，所有節(jié)點都知道每個超幀的起始時刻，節(jié)點為了能夠被分配一個beacon時隙，首先將掃描至少一個超幀的beacons，如果在掃描過程中，沒有接收到beacon，那么該節(jié)點將創(chuàng)建一個新的BP，并且發(fā)送第一個時隙中不是beacon時隙的其他beacon。然而，如果節(jié)點接收到來自鄰近節(jié)點的beacon，它將啟動beacon時隙分配過程，圖2演示了節(jié)點E在競爭時隙數(shù)為2的條件下beacon時隙的分配過程。例如，假定有兩個現(xiàn)存節(jié)點，節(jié)點C的BSI為3，節(jié)點B的BSI為4，初始時刻，因為節(jié)點B與節(jié)點E相距兩跳，所以節(jié)點E不知道節(jié)點B的存在，但是通過所有節(jié)點的beacons廣播(包含一跳范圍內(nèi)鄰居列表)，節(jié)點E能夠知道節(jié)點B的存在。其中斜體字母表示距離節(jié)點E兩跳的節(jié)點。節(jié)點E在收到來自節(jié)點C的beacon后，發(fā)送一個BSI請求的原始beacon，節(jié)點從n個beacon時隙中隨機地選擇它的初始BSI，本例中，假定節(jié)點E選擇的BSI為5，其中，原始beacon包括節(jié)點的MAC地址和BSI，原始beacon通過在競爭時隙中隨機獲得的時隙進行傳輸，如果節(jié)點E的鄰居節(jié)點C能夠成功地接收到來自節(jié)點E的原始beacon，那么節(jié)點C將發(fā)送它一跳鄰居節(jié)點表中包含節(jié)點E的beacon，因此，當節(jié)點E監(jiān)聽到來自節(jié)點C的beacon，并且在多個超幀中，節(jié)點E的MAC地址被包含在節(jié)點C的beacon中，那么節(jié)點E將正式地發(fā)送它在第5個時隙中的beacon。

1.2 beacon 沖突

在TMSR協(xié)議中，多個節(jié)點周期性地發(fā)送beacon，當這些節(jié)點處于活動狀態(tài)后，節(jié)點在beacon時隙分配過程中本地、獨立地選擇BSI，因為是本地分配的BSI，所以可能存在多個節(jié)點擁有相同的BSI，在靜態(tài)網(wǎng)絡(luò)環(huán)境，這種情況是沒有影響的，但是，當具有相同BSI的多個節(jié)點定期或非定期地移動到網(wǎng)絡(luò)中某個位置時，可能會產(chǎn)生beacon沖突。TMSR提出一個簡單的規(guī)則來解決這個問題，節(jié)點通過利用來自鄰居節(jié)點的beacon來檢測beacon沖突，如果在多個超幀中，節(jié)點接收到來自鄰居節(jié)點的beacon中都沒有自身的MAC地址，節(jié)點就認為有一個或多個其他節(jié)點使用了與自己相同的BSI，因此，這個節(jié)點就會暫停它的beacon傳輸，并且如果該節(jié)點檢測到它的beacon與其他節(jié)點的beacon產(chǎn)生重復的沖突，該節(jié)點將再次執(zhí)行beacon時隙分配過程。盡管它的beacon傳輸被終止，但是，只要該節(jié)點能夠接收到與既定流(如音、視頻)相關(guān)的節(jié)點的beacon，該節(jié)點將繼續(xù)進行數(shù)據(jù)傳輸，如果在beacon時隙分配過程中，該節(jié)點在多個超幀中都沒有接收到與既定流相關(guān)的beacon，該節(jié)點將會釋放與丟失節(jié)點相關(guān)的時隙。

圖2 節(jié)點的信標時隙分配過程

1.3 多跳信道時隙預(yù)留

在TMSR中，節(jié)點在傳輸數(shù)據(jù)時，先進行多跳信道時隙預(yù)留，引入兩個控制包，分別是預(yù)留請求(SREQ)和預(yù)留響應(yīng)(SRES)，同時引入了專用術(shù)語，如表1所示。

如果源節(jié)點需要預(yù)定到目的節(jié)點的時隙，它將廣播初始躍點計數(shù)設(shè)置為0的SREQ包，SREQ包的轉(zhuǎn)發(fā)信息包括源節(jié)點地址、目的節(jié)點地址、預(yù)約尺寸和躍點計數(shù)。當節(jié)點接收到新的SREQ包時，將檢測接收到的SREQ包中的躍點計數(shù)是否比跳數(shù)最大值小，如果不滿足此條件，節(jié)點將丟棄接收到的SREQ包。如果滿足此條件，節(jié)點將創(chuàng)建包含到源節(jié)點路徑信息的反向路徑表，反向路徑表由源節(jié)點地址、目的節(jié)點地址和SRES包單播到的下一跳節(jié)點地址組成，在創(chuàng)建了反向路徑表之后，中間節(jié)點轉(zhuǎn)發(fā)SREQ包給它的鄰居節(jié)點，同時對躍點計數(shù)加1。同時，中間節(jié)點和目的節(jié)點可能收到同一媒體流的SREQ包的多個副本，這些節(jié)點選擇第一個到達節(jié)點的MAC地址作為目的節(jié)點，這些節(jié)點將以反向路徑發(fā)送SRES包給最先到達的節(jié)點。在TMSR協(xié)議中，實際上多跳信道時隙預(yù)留在傳輸RRES包的反向路徑上執(zhí)行。

表1 專用術(shù)語對照表

下面通過一個例子對多跳信道時隙預(yù)留術(shù)語進行說明，圖3中，考慮了這樣一個場景，目的節(jié)點d，源節(jié)點s和中間節(jié)點i，其中1≤i≤n，n表示與特定流相關(guān)的中間節(jié)點數(shù)目，如果節(jié)點接收到一個目的節(jié)點地址是自己的MAC地址的REQ包，該節(jié)點將創(chuàng)建一個反向路徑表，同時由于所有的節(jié)點不僅知道自己的資源映射表，而且通過beacon還知道一跳范圍內(nèi)鄰居節(jié)點的資源映射表，所以，目的節(jié)點d將在中間節(jié)點i和目的節(jié)點d的資源映射表中搜索和預(yù)留常用的非預(yù)約時隙，對于被目的節(jié)點預(yù)留的時隙，中間節(jié)點i將變成TN，目的節(jié)點變成RN，在TMSR中，它們被叫做一對預(yù)留對。作為TN預(yù)留的時隙包括源節(jié)點地址、目的節(jié)點地址、TN的MAC地址和單播的數(shù)據(jù)包的下一跳地址等信息，同時，作為RN預(yù)留的時隙包括源節(jié)點地址、目的節(jié)點地址、將要轉(zhuǎn)發(fā)數(shù)據(jù)包節(jié)點的MAC地址和RN的MAC地址等信息。在成功預(yù)留時隙后，目的節(jié)點將向源節(jié)點發(fā)送SRES包。其中SRES包包含由源節(jié)點地址、目的節(jié)點地址、選定的時隙索引和單播SRES包的下一跳節(jié)點地址組成的前向轉(zhuǎn)發(fā)信息。

圖3 多跳信道時隙預(yù)留術(shù)語示意圖

算法1是針對源節(jié)點/中間節(jié)點的多跳信道時隙預(yù)留，算法描述(偽代碼)具體如下:

//其前提要求:

a1:當中間節(jié)點1接收到來自節(jié)點2的RRES包時，中間節(jié)點1將檢測在其與源節(jié)點S之間是否有常用的非預(yù)留時隙。

a2:當中間節(jié)點i-1接收到來自中間節(jié)點i的RRES包時，中間節(jié)點i-1將檢查其與節(jié)點i-2之間是否有常用的非預(yù)留時隙。

a1，a2={AVAILABLE or NOT_AVAILABLE}

1:if i=1 then

2:根據(jù)選定的時隙索引，源節(jié)點將為它與作為TN的中間節(jié)點1之間的通信預(yù)留時隙。

3:源節(jié)點s在預(yù)留時隙內(nèi)開始發(fā)送數(shù)據(jù)。

4:else if i=2 then

5:根據(jù)選定的時隙索引，中間節(jié)點1將為它與作為TN的中間節(jié)點2之間的通信預(yù)留時隙。

6:if a1=AVAILABLE then

7:中間節(jié)點1為源節(jié)點與作為RN的自己之間的通信預(yù)留時隙。

8:中間節(jié)點1向源節(jié)點s發(fā)送帶有選定時隙索引的RRES包。

9:else

10:不做任何操作

11:end if

12:else if2 ＜i＜n，then

13:根據(jù)選定的時隙索引，中間節(jié)點i-1為其與中間節(jié)點i之間的通信預(yù)留時隙，自己作為TN。

14:if a2=AVAILABLE then

15:中間節(jié)點i-1為其與中間節(jié)點i-2之間的通信預(yù)留時隙

自己作為RN.

16:中間節(jié)點i-1向中間節(jié)點i-2發(fā)送帶有選定時隙索引的RRES包。

17:else

18:不做任何操作

19:end if

20:end if

算法1中，展示了中間節(jié)點或源節(jié)點接收到來自中間節(jié)點i的SRES包時執(zhí)行多跳信道時隙預(yù)留過程。當中間節(jié)點或源節(jié)點接收到下一跳節(jié)點地址是自己MAC地址的SRES包時調(diào)用算法1，算法中，當中間節(jié)點作為RN預(yù)留時隙時，中間節(jié)點將優(yōu)先預(yù)留接收到的SRES包中選定時隙索引左邊的時隙，這樣使SRES包在通過多跳鏈路的超幀中變得連續(xù)有序。

圖4中，演示了在有1個源節(jié)點、2個中間節(jié)點和1個目的節(jié)點的場景中多跳信道時隙預(yù)留過程。

圖4 TMSR協(xié)議多跳時隙預(yù)留過程示意圖

1.4 故障節(jié)點檢測

TMSR故障點檢測的基本思想是利用beacon，當節(jié)點接收到來自一跳范圍內(nèi)鄰居節(jié)點的beacon時，它將創(chuàng)建鄰居列表，并且將鄰居的資源映射表保存到內(nèi)存中，當有節(jié)點移開時，節(jié)點將根據(jù)檢測閾值來決定是否繼續(xù)維持關(guān)于離開節(jié)點的數(shù)據(jù)流。如果節(jié)點通過檢測閾值決定不再維持丟失節(jié)點的流，那么該節(jié)點將釋放所有與丟失節(jié)點相關(guān)的預(yù)約時隙，而其他與丟失節(jié)點相關(guān)的節(jié)點將會在達到生存期后釋放它們的預(yù)約時隙，在沒有任何包傳輸?shù)那闆r下，信道時隙釋放過程依次蔓延到整個網(wǎng)絡(luò)，在節(jié)點釋放預(yù)留時隙過程中，如果流的源節(jié)點地址是自己的MAC地址時，該節(jié)點將再次發(fā)送SREQ包。

2 性能仿真

2.1 TMSR協(xié)議的實現(xiàn)

通過NS2實現(xiàn)TMSR協(xié)議，一個超幀由272個時隙組成，包括6個競爭時隙、90個beacon時隙、160個數(shù)據(jù)時隙和16個信道資源預(yù)留時隙，假設(shè)每20 ms產(chǎn)生一個語音包，超幀中預(yù)留空間大小至少為4，表1列出了TMSR的仿真參數(shù)。

2.2 仿真場景

假設(shè)網(wǎng)絡(luò)中有25個節(jié)點隨機分布在1 km×1 km的方形區(qū)域內(nèi)，節(jié)點的傳輸范圍是150 m，考慮了10種不同的網(wǎng)絡(luò)拓撲，每個場景有兩個不同的流量模式，仿真結(jié)果取它們的平均值，其中節(jié)點按照隨機行走移動模型在網(wǎng)絡(luò)內(nèi)移動，考慮了速度為v1=0 m/s，v2=4 m/s，v3=8 m/s三個移動場景，其中v1=0 m/s表示靜態(tài)網(wǎng)絡(luò)，v2=4 m/s，v3=8 m/s表示節(jié)點以在0～v之間的速度在網(wǎng)絡(luò)內(nèi)移動。為了性能評價，考慮了以下性能參數(shù)，一個是平均端到端時延，其中端到端時延是目的節(jié)點接收到包的時間與源節(jié)點發(fā)送包的時間的差值，另一個是平均吞吐量，其中吞吐量是成功接收到的包的數(shù)量與網(wǎng)絡(luò)中傳輸?shù)陌臄?shù)量的比值。

表1 仿真參數(shù)

2.3 仿真結(jié)果

首先討論單跳場景的仿真結(jié)果，為了驗證TMSR協(xié)議的性能，對使用TMSR協(xié)議和使用E-TDMA協(xié)議的單跳場景的仿真結(jié)果進行比較，然后，對使用TMRR協(xié)議的多跳場景的仿真結(jié)果進行分析，因為E-TDMA不支持多跳場景，所以沒有考慮在多跳場景中使用E-TDMA協(xié)議的情況。

圖5和圖6是在不同流量負載和節(jié)點移動速度下，TMSR協(xié)議和E-TDMA協(xié)議的平均端到端時延和平均吞吐量仿真圖。當網(wǎng)絡(luò)流量負載比較輕時，這兩個協(xié)議都傳輸了幾乎所有的包，在靜態(tài)網(wǎng)絡(luò)環(huán)境中，初始時，TMSR的平均端到端時延略高于E-TDMA的平均端到端時延，直到傳輸?shù)臄?shù)據(jù)包達到105個時，這種情況才發(fā)送改變，這是因為所有的TMSR節(jié)點經(jīng)歷了BP和SRP這兩個階段的固定時間延遲，此外，在執(zhí)行時隙預(yù)留的過程中，目的節(jié)點隨機選擇DTP的后半部分作為預(yù)約點，因此，根據(jù)目的節(jié)點選擇哪部分作為預(yù)留點，也會造成不同的額外時延。盡管TMSR起始階段經(jīng)歷了一段時延，但是隨著數(shù)據(jù)流量的增加，TMSR在包吞吐量和時延方面的性能都優(yōu)于ETDMA。

圖7是多跳場景中TMSR協(xié)議的平均端到端時延仿真圖，在多跳場景中，本文評估了在流量恒定時，由于節(jié)點移動而引起TMSR協(xié)議性能的變化，仿真開始時，由于許多節(jié)點同時預(yù)留信道時隙，所以使得TMSR的平均端到端時延顯著增加，而隨著TMSR網(wǎng)絡(luò)趨于穩(wěn)定，平均端到端時延開始下降。在飽和點，語音包的平均端到端時延小于250 ms，滿足表2中所列出的實時業(yè)務(wù)多跳端到端時延要求。

圖5 單跳場景下平均端到端時延

圖6 單跳場景下平均吞吐量

圖7 多跳條件下平均端到端時延

表2 多跳端到端時延要求

3 結(jié)論

為了支持實時應(yīng)用，本文提出了一種新的MANET中的TMSR MAC協(xié)議，盡管節(jié)點由于BP和SRP都經(jīng)歷了固定的時延，但是，TMSR節(jié)點的平均端到端時延都滿足節(jié)點在靜態(tài)和移動環(huán)境中多跳端到端時延要求，因此，提出的TMSR協(xié)議可以應(yīng)用在MANET中以支持實時應(yīng)用。

［1］JURDAK R，LOPES C V，BALDI P.A survey，classification，and comparative analysis of medium access control protocols for Ad Hoc networks［J］.IEEE Communications Surveys and Tutorials，2004，6(1):2-16.

［2］BRATEN L E，VOLDHAUG J E，OVSTHUYS K.Medium access for a military narrowband wireless ad-hoc network;requirements and initial approaches［C］//Proc.MILCOM 2008.San Diego:IEEE Press，2008:1-7.

［3］DJUKIC P，MOHAPATRA P.Soft-TDMAC:a software TDMA-based MAC over commodity 802.11 hardware［C］//Proc.INFOCOM 2009，［S.l.］:IEEE Press，2009:1836-1844.

［4］ZHU C，CORSON M S.A five-phase reservation protocol(FPRP)for Mobile Ad Hoc networks［C］//Proc.17th Annual Joint Conf.IEEE Comp.and Commun.Societies.［S.l.］:IEEE Press，1998:322-331.

［5］ZHU C，CORSON M S.An evolutionary-TDMA scheduling protocol(ETDMA)for mobile ad hoc networks［R］.［S.l.］:The University of Maryland，2000.

［6］WiMedia Alliance.Distributed Medium Access Control(MAC)for Wireless Networks［EB/OL］.［2013-07-12］.http://www.wimedia.org/en/docs/091819r01aWM_BOD-only-Specification_1.5.pdf.

［7］DJUKIC P，MOHAPATRA P.Soft-tdmac:a software-based 802.11overlay tdma mac with microsecond synchronization［J］.IEEE Trans.Mobile Computing，2012，11(3):478-491.

［8］陶洋，張詢.MANET中的高準確度地址沖突檢測算法［J］.計算機工程，2009，35(5):94-96.