CT-TDMA：水下傳感器網(wǎng)絡(luò)高效TDMA協(xié)議

洪璐，洪鋒，李正寶，郭忠文

（中國(guó)海洋大學(xué) 信息科學(xué)與工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，山東 青島 266100）

1 引言

水下無線傳感器網(wǎng)絡(luò)（UWSN, underwater sensor networks）將采集到的海洋環(huán)境數(shù)據(jù)發(fā)送給用戶來輔助決策，在環(huán)境監(jiān)測(cè)、資源勘探、災(zāi)害預(yù)警和潛艇探測(cè)等民用和軍用領(lǐng)域均具有廣闊的應(yīng)用前景[1～3]。

UWSN的重要特點(diǎn)是，主要通信方式只能采用水聲通信。這是因?yàn)楦哳l無線信號(hào)會(huì)被海水吸收，光信號(hào)也會(huì)因海水散射和反射而大量損耗，兩者均不能滿足水下長(zhǎng)距離通信的要求。與無線電信號(hào)相比，水聲通信的主要特點(diǎn)是：傳播時(shí)延大，水聲信號(hào)的傳播速率僅為1 500m/s；通信距離長(zhǎng)且?guī)挼?，通信距離一般在1～10km級(jí)別，通信帶寬僅在10kHz級(jí)別；誤碼率高、多途現(xiàn)象和多普勒頻移現(xiàn)象均會(huì)導(dǎo)致傳輸錯(cuò)誤[4,5]。

由于水聲通信的傳播時(shí)延高和通信距離長(zhǎng)，發(fā)送端無法判斷信道是否沖突；同時(shí)，由于低帶寬和誤碼率高的特性，使得 UWSN中每次通信的分組長(zhǎng)度必須受到限制。因此，解決UWSN的MAC問題的關(guān)鍵在于接收端判斷沖突是否發(fā)生。

目前，國(guó)內(nèi)外的研究者在UWSN的MAC問題上展開了深入的研究，主要包括接入競(jìng)爭(zhēng)控制協(xié)議和無沖突接入?yún)f(xié)議2種。接入競(jìng)爭(zhēng)控制協(xié)議，通過以接收端為中心的虛擬載波監(jiān)聽協(xié)議來解決 MAC問題[6～10]，但由于水聲通信的時(shí)延長(zhǎng)，虛擬載波監(jiān)聽的握手機(jī)制降低了數(shù)據(jù)通信時(shí)間的比例，導(dǎo)致網(wǎng)絡(luò)流量較低。

無沖突接入?yún)f(xié)議主要采用時(shí)分復(fù)用接入（TDMA），即采用集中式的方式來向 UWSN內(nèi)各個(gè)節(jié)點(diǎn)分配通信時(shí)間片[11～14]。此類協(xié)議可根據(jù)數(shù)據(jù)傳輸完成需要的時(shí)隙數(shù)分為2種。第一種TDMA算法要求，一跳范圍內(nèi)的數(shù)據(jù)傳輸必須在一個(gè)時(shí)隙完成，稱之為單時(shí)隙協(xié)議[11,12]。單時(shí)隙協(xié)議的主要問題在于，為了保證不同距離的節(jié)點(diǎn)對(duì)在一個(gè)時(shí)隙內(nèi)均能完成通信，時(shí)隙必須由最大的鏈路時(shí)延決定。時(shí)隙的長(zhǎng)度是發(fā)送幀時(shí)和網(wǎng)絡(luò)中最大鏈路時(shí)延之和，該問題同樣影響了網(wǎng)絡(luò)流量的提高。

為了提高網(wǎng)絡(luò)流量，研究者提出了允許跨時(shí)隙完成數(shù)據(jù)傳輸?shù)腟T-MAC協(xié)議[13]。該協(xié)議假設(shè)所有的鏈路時(shí)延都是幀時(shí)的整數(shù)倍，利用啟發(fā)式規(guī)則完成多跳網(wǎng)絡(luò)的時(shí)隙分配，實(shí)現(xiàn)了較高的網(wǎng)絡(luò)流量。

基于時(shí)隙的分配本質(zhì)上是分配各個(gè)節(jié)點(diǎn)的發(fā)送時(shí)刻。如果能不采用按時(shí)隙分配，而直接在連續(xù)時(shí)間軸上對(duì)每個(gè)節(jié)點(diǎn)分配發(fā)送時(shí)刻，將更好地利用UWSN網(wǎng)絡(luò)中同一接收節(jié)點(diǎn)與不同發(fā)送節(jié)點(diǎn)之間鏈路時(shí)延的差異性，降低接收幀之間的空閑時(shí)間，提高網(wǎng)絡(luò)流量。因此，本文提出了以連續(xù)時(shí)間分配為出發(fā)點(diǎn)的水下傳感器網(wǎng)絡(luò)的 TDMA協(xié)議（CT-TDMA, continuous time based TDMA）。

CT-TDMA的核心思想是，每個(gè)節(jié)點(diǎn)利用收集到的局部網(wǎng)絡(luò)拓?fù)湫畔?，以自身的發(fā)送行為可能引起的沖突為依據(jù)，分布式地計(jì)算局部沖突狀態(tài)圖（LCG, local conflict graph）。所有節(jié)點(diǎn)按照啟發(fā)式規(guī)則計(jì)算自己的優(yōu)先級(jí)，然后根據(jù) LCG圖中的所有鄰居的優(yōu)先級(jí)順序完成發(fā)送時(shí)刻的標(biāo)定。優(yōu)先級(jí)計(jì)算的啟發(fā)式規(guī)則綜合了節(jié)點(diǎn)的度、負(fù)載和鏈路時(shí)延等重要因素，在有效縮短連續(xù)時(shí)間軸上時(shí)刻分配問題的計(jì)算時(shí)間的同時(shí)，保證了 TDMA協(xié)議的流量和端到端時(shí)延等性能指標(biāo)。

本文的主要貢獻(xiàn)如下。

1) 針對(duì)水下傳感器網(wǎng)絡(luò)在MAC層設(shè)計(jì)上的獨(dú)特問題——同一接收節(jié)點(diǎn)與不同發(fā)送節(jié)點(diǎn)之間鏈路時(shí)延的差異性不可忽略，設(shè)計(jì)了以發(fā)送端為中心以連續(xù)時(shí)間為計(jì)量單位的沖突狀態(tài)模型——局部沖突狀態(tài)圖。在此基礎(chǔ)上，本文提出了分布式的局部沖突狀態(tài)圖構(gòu)建算法：每個(gè)節(jié)點(diǎn)利用以通信半徑和干擾半徑之和為半徑的覆蓋圓內(nèi)的網(wǎng)絡(luò)拓?fù)湫畔?，分布式?jì)算局部沖突狀態(tài)圖。

2) 提出了基于啟發(fā)式規(guī)則的水下傳感器網(wǎng)絡(luò)TDMA協(xié)議，即節(jié)點(diǎn)以其局部沖突狀態(tài)圖為分配依據(jù)，以節(jié)點(diǎn)的度、負(fù)載和鏈路時(shí)延計(jì)算優(yōu)先級(jí)，按照優(yōu)先級(jí)順序進(jìn)行發(fā)送時(shí)刻標(biāo)定。該啟發(fā)式算法有效縮短了連續(xù)時(shí)間軸上時(shí)刻分配問題的運(yùn)行時(shí)間。

3) CT-TDMA協(xié)議采用基于連續(xù)時(shí)間的接入分配算法，與基于時(shí)隙的 TDMA協(xié)議相比，縮短了目的端的接收幀之間的空閑時(shí)間，提高了接收端的信道利用率及整個(gè)網(wǎng)絡(luò)的流量。模擬實(shí)驗(yàn)證明：在實(shí)驗(yàn)時(shí)間段內(nèi)，CT-TDMA方案與以ST-MAC為代表的TDMA方案相比，網(wǎng)絡(luò)流量提高了20%，數(shù)據(jù)分組的端到端時(shí)延降低了18%；與由全局知識(shí)所計(jì)算出的最優(yōu)分配策略相比，網(wǎng)絡(luò)流量達(dá)到了80%，數(shù)據(jù)分組的端到端時(shí)延僅延長(zhǎng)了12%。

本文其余部分組織如下：第2節(jié)對(duì)CT-TDMA設(shè)計(jì)方案進(jìn)行詳細(xì)介紹；第3節(jié)分析CT-TDMA的仿真實(shí)驗(yàn)結(jié)果，第4節(jié)概述近幾年UWSN的MAC問題的相關(guān)研究成；第5節(jié)是結(jié)束語。

2 CT-TDMA設(shè)計(jì)

本節(jié)首先通過示例說明CT-TDMA的設(shè)計(jì)出發(fā)點(diǎn)，進(jìn)而對(duì)基于連續(xù)時(shí)間的沖突狀態(tài)模型——局部沖突狀態(tài)圖進(jìn)行了詳細(xì)說明。其次詳細(xì)介紹CT-TDMA的執(zhí)行過程，并給出關(guān)鍵函數(shù)和過程的偽代碼描述。然后討論了CT-TDMA中用于判斷節(jié)點(diǎn)接入優(yōu)先級(jí)的啟發(fā)式規(guī)則。最后，結(jié)合實(shí)例來展示CT-TDMA的運(yùn)行過程和運(yùn)行結(jié)果。

2.1 設(shè)計(jì)出發(fā)點(diǎn)

解決UWSN的MAC問題的關(guān)鍵在于，唯有接收端才能判斷數(shù)據(jù)分組沖突是否發(fā)生。如圖1(a)所示，節(jié)點(diǎn)A和B向節(jié)點(diǎn)C發(fā)送數(shù)據(jù)。設(shè)DAC和DBC為鏈路AC和BC的傳播時(shí)延且DAC＜DBC，T為數(shù)據(jù)分組發(fā)送時(shí)間即幀時(shí)，ta和tb為節(jié)點(diǎn)A和B的傳輸時(shí)刻。

在陸地傳感器網(wǎng)絡(luò)中，由于無線電信號(hào)的傳播時(shí)延可以忽略，因此TDMA方案的時(shí)隙長(zhǎng)度為T。只要由發(fā)送端A和B選擇不同的時(shí)隙發(fā)送即可避免沖突。然而，UWSN的鏈路的傳播時(shí)延不可忽略，為了保證相鄰時(shí)隙發(fā)送的幀無沖突，在本例中時(shí)隙長(zhǎng)度至少為DBC+T。因此，接收端C接收到的幀序列在時(shí)間軸將變得稀疏，如圖1(b)所示。

圖1 TDMA不同策略下的發(fā)送時(shí)間的分配

而理想的TDMA效果應(yīng)如圖1(c)所示，A選擇ta時(shí)刻發(fā)送數(shù)據(jù)幀，則該幀到達(dá)C的時(shí)刻為ta+DAC。為使得C接收到的幀序列間的空閑盡可能小，那么B發(fā)送的幀到達(dá)C的時(shí)刻應(yīng)為ta+DAC+T（即A發(fā)送幀的幀尾和B發(fā)送幀的幀頭相接），所以B節(jié)點(diǎn)的發(fā)送時(shí)刻應(yīng)為tb=ta+DAC+T-DBC。

圖1給出了UWSN網(wǎng)絡(luò)的普通拓?fù)淝闆r。該例說明基于連續(xù)時(shí)間的接入分配相比于基于時(shí)隙的TDMA方案，能夠提高接收端的流量?；谶B續(xù)時(shí)間的分配充分利用了UWSN的鏈路時(shí)延長(zhǎng)和數(shù)據(jù)分組短的特性，這正是CT-TDMA設(shè)計(jì)的出發(fā)點(diǎn)。

2.2 連續(xù)沖突狀態(tài)模型

為了清晰地描述CT-TDMA的連續(xù)沖突狀態(tài)模型，本節(jié)首先對(duì)運(yùn)行環(huán)境做一些基本設(shè)定。

1) 使用圓型通信和干擾模型，即節(jié)點(diǎn)的通信范圍和干擾范圍都是一個(gè)以自己為圓心的圓。網(wǎng)絡(luò)中節(jié)點(diǎn)都是同構(gòu)的，具有相同的通信半徑 RT(transmission radius)和干擾半徑RI(interference radius)。傳感器網(wǎng)絡(luò)中的干擾半徑 RI是對(duì)節(jié)點(diǎn)信號(hào)的干擾覆蓋范圍的一種描述：當(dāng)源節(jié)點(diǎn)進(jìn)行發(fā)送時(shí)，以源節(jié)點(diǎn)為圓心、RI為半徑的覆蓋圓內(nèi)的所有節(jié)點(diǎn)都由于源節(jié)點(diǎn)發(fā)送數(shù)據(jù)所帶來的干擾，而不能正常接收來自其他節(jié)點(diǎn)的數(shù)據(jù)分組[15,16]。RI在網(wǎng)絡(luò)部署前進(jìn)行測(cè)定，并與通信半徑一樣作為協(xié)議的初始化參數(shù)進(jìn)行設(shè)定。

2) 節(jié)點(diǎn)通過時(shí)鐘同步算法，保證足夠的同步精確度。

CT-TDMA的連續(xù)沖突狀態(tài)模型包括局部沖突狀態(tài)圖和禁止時(shí)間計(jì)算規(guī)則。其關(guān)鍵術(shù)語的定義如下。

定義1 覆蓋范圍函數(shù)Cov(N, R)：以節(jié)點(diǎn)N為圓心，以R為半徑的區(qū)域。如節(jié)點(diǎn)N(xn, yn)通信范圍 Cov(N, RT)={(x,y)|(x-xn)2+(y-yn)2≤RT2}；干擾范圍Cov(N, RI)={(x,y)|(x-xn)2+(y-yn)2≤RI2}

定義 2 求取某區(qū)域內(nèi)的節(jié)點(diǎn)集的操作 Nodeset(C)：C為水下傳感器網(wǎng)絡(luò)的某個(gè)部署區(qū)域，操作返回屬于該區(qū)域的節(jié)點(diǎn)集，即Nodeset(C)={N| (xn,yn)∈C}。

定義 3 沖突：節(jié)點(diǎn)不能夠同時(shí)發(fā)送和接收，不能夠同時(shí)接收2個(gè)以上的數(shù)據(jù)分組，所有違反這2條原則的發(fā)送和接收均稱為沖突。以圖2為例，如果i和j的信號(hào)同時(shí)到達(dá)k，k將無法正常接收i的數(shù)據(jù)分組；如果i的信號(hào)到達(dá)k時(shí)k正在發(fā)送，k也無法正常接收i的數(shù)據(jù)分組，此2種情形均稱為沖突。

定義 4 沖突鄰居、沖突目標(biāo)節(jié)點(diǎn)：節(jié)點(diǎn)之間的沖突關(guān)系是網(wǎng)絡(luò)物理拓?fù)浜瓦壿嬐負(fù)涞闹苯臃从场ＴO(shè)N為網(wǎng)絡(luò)中的任一發(fā)送節(jié)點(diǎn)，節(jié)點(diǎn)N的發(fā)送操作對(duì)周圍節(jié)點(diǎn)可能造成的沖突主要表現(xiàn)在：對(duì)于不同于N的節(jié)點(diǎn)M而言，如果存在節(jié)點(diǎn)P，滿足P的位置在物理拓?fù)渲形挥贛和N其中一個(gè)節(jié)點(diǎn)的通信范圍內(nèi)，同時(shí)位于另一節(jié)點(diǎn)的干擾范圍內(nèi)，并且，在邏輯拓?fù)渲写嬖阪溌種-＞P或者M(jìn)-＞P，那么P節(jié)點(diǎn)在接收N或者M(jìn)其中一個(gè)節(jié)點(diǎn)的數(shù)據(jù)分組時(shí)，可能會(huì)受到來自另一節(jié)點(diǎn)的發(fā)送信號(hào)的干擾而無法接收，即在P點(diǎn)形成沖突。

對(duì)于節(jié)點(diǎn)N來說，其干擾范圍內(nèi)的所有鄰居都有可能由于節(jié)點(diǎn)N的發(fā)送而成為沖突發(fā)生點(diǎn)。因此，節(jié)點(diǎn)N的沖突目標(biāo)節(jié)點(diǎn)和沖突鄰居定義如下：

當(dāng)節(jié)點(diǎn)P、M同時(shí)滿足下列拓?fù)錀l件時(shí)，節(jié)點(diǎn)P是節(jié)點(diǎn)N的沖突目標(biāo)節(jié)點(diǎn)，節(jié)點(diǎn)M是節(jié)點(diǎn)N的沖突鄰居：

① 物理拓?fù)錀l件：

P∈Nodeset(Cov(N, RT)∩Cov(M, RI)) ||

P∈Nodeset(Cov(N, RI)∩Cov(M, RT))

② 邏輯拓?fù)錀l件：(N-＞P) || (M-＞P)

該定義說明，節(jié)點(diǎn)的沖突鄰居必位于它的(RI+RT)的覆蓋范圍內(nèi)。如圖2中，節(jié)點(diǎn)k處于節(jié)點(diǎn)i的通信范圍和節(jié)點(diǎn)j的干擾范圍內(nèi)，同時(shí)鏈路i-＞k存在，因此節(jié)點(diǎn)j是節(jié)點(diǎn)i的沖突鄰居，節(jié)點(diǎn)k為相應(yīng)的沖突目標(biāo)節(jié)點(diǎn)。對(duì)于節(jié)點(diǎn)n來說，節(jié)點(diǎn)n和節(jié)點(diǎn)i相距較遠(yuǎn)，且兩者的通信范圍和干擾范圍的交集范圍內(nèi)不存在節(jié)點(diǎn)，因此不滿足上述定義中的物理拓?fù)錀l件，所以節(jié)點(diǎn)n不是節(jié)點(diǎn)i的沖突鄰居。

圖2 節(jié)點(diǎn)i的局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

定義5 局部沖突狀態(tài)圖（LCG，local conflict graph）：節(jié)點(diǎn)i的沖突狀態(tài)圖是一個(gè)以節(jié)點(diǎn)i為中心的帶權(quán)多重圖，描述所有和i的發(fā)送行為有關(guān)的沖突。LCG中的頂點(diǎn)為i及其所有的沖突鄰居。LCG圖中邊的權(quán)值定義為：如果節(jié)點(diǎn)j為節(jié)點(diǎn)i的沖突鄰居，其沖突目標(biāo)節(jié)點(diǎn)為k，且鏈路ik和jk的時(shí)延分別為Dik和Djk，則邊i-j的權(quán)值為

為了表達(dá)式的一般性，定義 Dii=0。

Wij(k)用來描述節(jié)點(diǎn)i和節(jié)點(diǎn)j發(fā)送的數(shù)據(jù)在接收點(diǎn)k產(chǎn)生沖突的狀態(tài)。Wij(k)取正值表示，如果節(jié)點(diǎn)i選擇比節(jié)點(diǎn)j早Wij(k)的時(shí)間進(jìn)行發(fā)送，則會(huì)在k產(chǎn)生沖突。相應(yīng)地，如果Wij(k)為負(fù)值，表示節(jié)點(diǎn)i選擇比節(jié)點(diǎn)j晚|Wij(k)|的時(shí)間進(jìn)行發(fā)送時(shí)會(huì)產(chǎn)生沖突。由于節(jié)點(diǎn)的所有沖突鄰居均位于該節(jié)點(diǎn)的LCG中，因此沖突鄰居也就是節(jié)點(diǎn)的LCG鄰居。

以圖2為例，節(jié)點(diǎn)k是節(jié)點(diǎn)i和節(jié)點(diǎn)j的沖突目標(biāo)節(jié)點(diǎn)，那么節(jié)點(diǎn)i的LCG圖中存在邊i-j，權(quán)值為 Wij(k)=Dik-Djk=-0.2。其含義為：如果節(jié)點(diǎn) i選擇比節(jié)點(diǎn)j晚0.2s進(jìn)行發(fā)送，則在節(jié)點(diǎn)k將同時(shí)接收到節(jié)點(diǎn)i的發(fā)送信號(hào)和節(jié)點(diǎn)j發(fā)向其他節(jié)點(diǎn)的數(shù)據(jù)信號(hào)的干擾能量，從而發(fā)生沖突。

對(duì)于節(jié)點(diǎn)i和節(jié)點(diǎn)k來說，Nodeset(Cov(i,RT)∩Cov(k, RI))={i , k}，并且僅鏈路i-＞k存在，由定義4可得，節(jié)點(diǎn)k既是節(jié)點(diǎn)i的沖突鄰居，也是節(jié)點(diǎn)i和節(jié)點(diǎn)k沖突的目標(biāo)節(jié)點(diǎn)，且Wik(k)=Wik-Wkk= 3.2。這說明如果節(jié)點(diǎn)i選擇比節(jié)點(diǎn)k早3.2s進(jìn)行發(fā)送，那么當(dāng)節(jié)點(diǎn)i的數(shù)據(jù)信號(hào)到達(dá)節(jié)點(diǎn)k時(shí)，節(jié)點(diǎn)k正在向其他節(jié)點(diǎn)發(fā)送信號(hào)，無法接收節(jié)點(diǎn)i的數(shù)據(jù)，產(chǎn)生沖突。

再分析節(jié)點(diǎn)i和節(jié)點(diǎn) f的沖突情況，由定義4的物理?xiàng)l件得到，Nodeset(Cov(i, RT)∩Cov(f, RI))={i,k, f}。由于鏈路i-＞f不存在，根據(jù)定義4的邏輯拓?fù)錀l件，f不是沖突目標(biāo)節(jié)點(diǎn)。該論斷的含義是，f不接收i的數(shù)據(jù)分組，因此i發(fā)送的信號(hào)到達(dá)f時(shí)，f可以進(jìn)行發(fā)送，即在f節(jié)點(diǎn)處不會(huì)產(chǎn)生i和f的沖突。但是鏈路i-＞k存在，說明k是i和f的沖突目標(biāo)節(jié)點(diǎn)，其含義是i和f的信號(hào)可能同時(shí)到達(dá)節(jié)點(diǎn)k。同時(shí)，鏈路f-＞i存在，說明i同樣是i和f的沖突目標(biāo)節(jié)點(diǎn)，其含義是i在接收f的信號(hào)時(shí)，不能向其他節(jié)點(diǎn)發(fā)送數(shù)據(jù)。因此節(jié)點(diǎn) i的 LCG圖中， i和f之間存在2條邊，其權(quán)值分別為Wif(k)=Dik-Dfk=-2.2和Wif(i)=Dii-Dif= -4.5。

定義6 禁止時(shí)間：節(jié)點(diǎn)的禁止時(shí)間是指在時(shí)間軸上的一個(gè)時(shí)間片段內(nèi)，節(jié)點(diǎn)不能夠選擇發(fā)送時(shí)刻，否則會(huì)引起沖突。

為保證2個(gè)節(jié)點(diǎn)的幀到達(dá)目標(biāo)時(shí)不沖突（即在接收端的時(shí)間軸上不重疊），對(duì)每個(gè)發(fā)送節(jié)點(diǎn)來說均有一段時(shí)間不能發(fā)送，稱為禁止時(shí)間。以圖3為例，在節(jié)點(diǎn)i的LCG中，如果其鄰居j選擇發(fā)送時(shí)刻tj，則由節(jié)點(diǎn)j決定的節(jié)點(diǎn)i的禁止時(shí)間定義為(Fl(i,j, k)，F(xiàn)r(i, j, k))。其中

禁止時(shí)間的物理含義為，由于節(jié)點(diǎn)j的存在和其發(fā)送時(shí)刻tj的確定，節(jié)點(diǎn)i在(Fl(i, j, k)，F(xiàn)r(i, j, k))時(shí)間段內(nèi)不能發(fā)送數(shù)據(jù)幀。如圖3所示，如果節(jié)點(diǎn)i選取的發(fā)送時(shí)刻大于Fl(i, j, k)，i發(fā)送的幀尾將與j發(fā)送的幀頭在相關(guān)接收點(diǎn)k產(chǎn)生沖突；當(dāng)i選取的發(fā)送時(shí)刻稍小于Fr(i, j, k)，i發(fā)送的幀頭將與j發(fā)送的幀尾在相關(guān)接收點(diǎn)k產(chǎn)生沖突。

圖3 禁止時(shí)間的計(jì)算

以圖2中的節(jié)點(diǎn)i和j的沖突為例，Wij(k)= -0.2，假設(shè)節(jié)點(diǎn)j選擇第2s發(fā)送(tj=2)，幀時(shí)T=1s，則根據(jù)式(2)和式(3)可得節(jié)點(diǎn)j給節(jié)點(diǎn)i帶來的禁止時(shí)間為(1.2, 3.2)。以節(jié)點(diǎn)i和f為例，根據(jù)前面的分析，沖突狀態(tài)圖中邊i-f的權(quán)值有2個(gè)，因此假設(shè)f選擇0s開始發(fā)送，根據(jù)公式計(jì)算出的f給i帶來的禁止時(shí)間也是2段，為(3.5, 5.5)∪(1.2, 3.2)。

2.3 CT-TDMA的主要算法

本節(jié)首先介紹局部沖突狀態(tài)圖的生成過程，然后介紹CT-TDMA的算法流程。CT-TDMA可以適用于任何網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，但為了簡(jiǎn)化說明，本節(jié)針對(duì)最廣泛使用的樹形拓?fù)浣Y(jié)構(gòu)進(jìn)行介紹。

2.3.1 LCG生成算法

在初始化階段，每個(gè)節(jié)點(diǎn)i收集Cov(i，RT+RI)范圍內(nèi)的鄰居節(jié)點(diǎn)的地理位置信息和邏輯鏈路信息，并計(jì)算其沖突區(qū)域內(nèi)所有節(jié)點(diǎn)對(duì)的信號(hào)傳播時(shí)延，得到以該節(jié)點(diǎn)為中心的局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。對(duì)于位于節(jié)點(diǎn)通信半徑之外的鄰居，節(jié)點(diǎn)通過多跳傳輸?shù)姆绞将@得其對(duì)應(yīng)鄰居的相關(guān)信息。在計(jì)算得到Cov (i，RT+RI)內(nèi)的局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)后，節(jié)點(diǎn)運(yùn)行createLCG()函數(shù)，按照定義5中給出的規(guī)則生成自己的LCG。

利用定義4驗(yàn)證j是否是i的沖突鄰居。PTC()和 LTC()函數(shù)用來對(duì)節(jié)點(diǎn)是否符合沖突的物理拓?fù)錀l件(physical topology condition)和邏輯拓?fù)錀l件(logical topology condition)進(jìn)行判定。針對(duì)每一個(gè)鄰居j進(jìn)行分析：如果存在某個(gè)節(jié)點(diǎn)k，使得k、j符合沖突的2個(gè)條件，滿足節(jié)點(diǎn)j是節(jié)點(diǎn)i的沖突鄰居，k是 i和 j沖突的目標(biāo)節(jié)點(diǎn)，則計(jì)算Wij(k)=Dik-Djk，并記錄到i的LCG中。

算法1 createLCG ()

令V(i)是節(jié)點(diǎn)i的所有Cov(I, RT+RI)內(nèi)的鄰居節(jié)點(diǎn)的集合，SLCG(i)為 i的沖突狀態(tài)圖內(nèi)所有的邊的權(quán)值集合，算法1描述了節(jié)點(diǎn)局部沖突狀態(tài)圖的生成過程。

以圖2的拓?fù)錇槔?，?jié)點(diǎn)i運(yùn)行createLCG()算法后，生成的LCG如圖4所示。根據(jù)前面的分析，節(jié)點(diǎn)f和i沖突的目標(biāo)節(jié)點(diǎn)有2個(gè)，根據(jù)定義5計(jì)算出邊i-f有2個(gè)權(quán)值，因此在局部沖突狀態(tài)圖中體現(xiàn)為具有不同權(quán)值的多重邊。如果2個(gè)節(jié)點(diǎn)對(duì)會(huì)在多個(gè)節(jié)點(diǎn)處產(chǎn)生沖突，則LCG圖中這2個(gè)節(jié)點(diǎn)對(duì)之間就會(huì)有多重邊，且多重邊的個(gè)數(shù)即為沖突目標(biāo)節(jié)點(diǎn)的個(gè)數(shù)。因此，由于節(jié)點(diǎn)沖突的多樣性，LCG為帶權(quán)的多重圖。

圖4 節(jié)點(diǎn)i的局部沖突狀態(tài)圖（LCG）

2.3.2 CT-TDMA算法流程

每個(gè)節(jié)點(diǎn)生成自己的LCG圖后，就根據(jù)由LCG圖每條邊所對(duì)應(yīng)的各個(gè)禁止時(shí)間，來選擇自己的發(fā)送時(shí)刻。即選擇和所有禁止時(shí)間不沖突的最早時(shí)刻，作為自己的發(fā)送時(shí)刻。

但是，當(dāng)前節(jié)點(diǎn)的發(fā)送時(shí)刻的確定，取決于其LCG鄰居的發(fā)送時(shí)刻。CT-TDMA采用優(yōu)先級(jí)和隨機(jī)選擇相結(jié)合的方式，安排節(jié)點(diǎn)的發(fā)送時(shí)刻標(biāo)定順序。即優(yōu)先級(jí)最高的節(jié)點(diǎn)最先選擇發(fā)送時(shí)刻，選擇的基本策略是在所有可用的時(shí)間段內(nèi)選擇一個(gè)最早的時(shí)間點(diǎn)（選擇的過程稱為標(biāo)定）。如果 LCG圖中所有未標(biāo)定節(jié)點(diǎn)的優(yōu)先級(jí)相同，各個(gè)節(jié)點(diǎn)隨機(jī)選擇發(fā)送時(shí)刻。優(yōu)先級(jí)的計(jì)算方法，將直接影響CT-TDMA的執(zhí)行效率。本節(jié)先介紹CT-TDMA的算法流程，而計(jì)算優(yōu)先級(jí)的啟發(fā)式規(guī)則將在 2.3.3節(jié)中進(jìn)行討論。

CT-TDMA的完整算法流程包括以下7步。

1) 節(jié)點(diǎn)生成自己的LCG并計(jì)算自己的標(biāo)定優(yōu)先級(jí)。

2) 每個(gè)節(jié)點(diǎn)向所有的LCG鄰居廣播自己的標(biāo)定優(yōu)先級(jí)，并將自己的狀態(tài)置為“unlabeled”。然后，每個(gè)節(jié)點(diǎn)以分布式方式運(yùn)行3)～6)步。

3) 如果當(dāng)前節(jié)點(diǎn)在其LCG圖中的所有未標(biāo)定鄰居中擁有最高的優(yōu)先級(jí)，則節(jié)點(diǎn)根據(jù)由 LCG得到的所有禁止時(shí)間段，選擇最早的可發(fā)送時(shí)刻作為自己的發(fā)送時(shí)刻，并將其廣播給所有的LCG鄰居，并將狀態(tài)置為“l(fā)abeled”。

4) 如果當(dāng)前節(jié)點(diǎn)的所有未標(biāo)定鄰居中存在優(yōu)先級(jí)高于自己的鄰居，則等待優(yōu)先級(jí)高的節(jié)點(diǎn)先標(biāo)定，等待接收相關(guān)節(jié)點(diǎn)的發(fā)送時(shí)刻結(jié)果并更新自己的禁止時(shí)間，返回第3)步。

5) 如果當(dāng)前節(jié)點(diǎn)在其LCG圖中與其他未標(biāo)定的節(jié)點(diǎn)擁有相同的優(yōu)先級(jí)，則該節(jié)點(diǎn)在時(shí)間軸上除禁止時(shí)間之外的時(shí)刻隨機(jī)選擇其發(fā)送時(shí)刻，并廣播給所有同優(yōu)先級(jí)的未標(biāo)定狀態(tài)的LCG鄰居。

6) 隨機(jī)標(biāo)定的節(jié)點(diǎn)選定發(fā)送時(shí)刻并與所有同優(yōu)先級(jí)鄰居交換選定結(jié)果后，運(yùn)行Judge()函數(shù)判斷是否會(huì)產(chǎn)生沖突，若無沖突，則置為“l(fā)abeled”，否則置為“unlabeled”，并返回第5)步。

7) LCG圖中的所有節(jié)點(diǎn)狀態(tài)均為“l(fā)abeled”時(shí)，算法結(jié)束。

算法2 Label()

節(jié)點(diǎn)使用Label()函數(shù)實(shí)現(xiàn)標(biāo)定功能，即上面的3)～6)步，Judge()函數(shù)被 Label()調(diào)用，用來判斷一次隨機(jī)選擇時(shí)間以后是否會(huì)產(chǎn)生沖突。在隨機(jī)標(biāo)定中，節(jié)點(diǎn)獲得鄰居隨機(jī)選定的時(shí)刻后仍然使用定義6計(jì)算禁止時(shí)間。Judge()函數(shù)判斷沖突的方式是，如果節(jié)點(diǎn)自己隨機(jī)選定的時(shí)刻處于計(jì)算出的“禁止時(shí)間”之內(nèi)，則認(rèn)為會(huì)產(chǎn)生沖突，此次隨機(jī)標(biāo)定即作廢，節(jié)點(diǎn)及其鄰居重新進(jìn)行隨機(jī)標(biāo)定。

定義 Sc(i)為節(jié)點(diǎn) i的已經(jīng)標(biāo)定的 LCG鄰居集合，Suc(i)為節(jié)點(diǎn)i的所有未標(biāo)定的LCG鄰居的集合，ST(i)為節(jié)點(diǎn)i的標(biāo)定狀態(tài)(labeled或unlabeled)，P(i)為節(jié)點(diǎn)i的標(biāo)定優(yōu)先級(jí)。算法2和算法3分別給出了Label()和Judge()函數(shù)的偽代碼描述。

在Label()函數(shù)中引入隨機(jī)標(biāo)定的設(shè)計(jì)，是因?yàn)樵谀承┚W(wǎng)絡(luò)中可能存在大量節(jié)點(diǎn)的優(yōu)先級(jí)相同。雖然可以采用節(jié)點(diǎn) ID等強(qiáng)制優(yōu)先級(jí)方式，但類似的優(yōu)先級(jí)策略對(duì)優(yōu)化最終的總傳輸時(shí)間沒有幫助。隨機(jī)標(biāo)定可以減少算法的執(zhí)行時(shí)間。比如，在極端的網(wǎng)絡(luò)拓?fù)錀l件下（如線形、星形），當(dāng)節(jié)點(diǎn)的優(yōu)先級(jí)均相同時(shí)，順序標(biāo)定算法的時(shí)間復(fù)雜度為 O(n)而隨機(jī)標(biāo)定的時(shí)間復(fù)雜度為O(logn)[17]。其中，n為網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)。

算法3 Judge()

2.3.3 標(biāo)定優(yōu)先級(jí)確定

在 UWSN環(huán)境下，對(duì)于所有節(jié)點(diǎn)的連續(xù)時(shí)間的接入分配，等價(jià)于一個(gè)連續(xù)軸上的分布式著色問題，因此確定最優(yōu)全局分配策略是 NP-hard問題。于是，在上一小節(jié)介紹的CT-TDMA算法流程中，使用了按照優(yōu)先級(jí)順序進(jìn)行標(biāo)定的算法。這樣，優(yōu)先級(jí)的確定直接影響CT-TDMA算法本身的執(zhí)行效率。本節(jié)對(duì)優(yōu)先級(jí)的計(jì)算方法進(jìn)行詳細(xì)說明。

CT-TDMA的算法目的是提高網(wǎng)絡(luò)流量，即所有節(jié)點(diǎn)均發(fā)送一次數(shù)據(jù)所使用的總時(shí)間越短越好。針對(duì)這個(gè)設(shè)計(jì)目標(biāo)，提出重要性依次降低的3條啟發(fā)式的優(yōu)先級(jí)制定規(guī)則如下。

1) 在沖突狀態(tài)圖中擁有最大度的節(jié)點(diǎn)應(yīng)該優(yōu)先分配發(fā)送時(shí)刻。節(jié)點(diǎn)的度越大意味著它潛在的沖突節(jié)點(diǎn)越多。度最大的節(jié)點(diǎn)首先分配發(fā)送時(shí)間，可以使受其影響的大量節(jié)點(diǎn)的禁止時(shí)間盡可能地靠前，從而縮短最后算法選定的總時(shí)間。

2)負(fù)載較重的節(jié)點(diǎn)優(yōu)先發(fā)送。負(fù)載較重的節(jié)點(diǎn)優(yōu)先發(fā)送有助于縮短每個(gè)分組端到端的平均時(shí)延，實(shí)現(xiàn)網(wǎng)絡(luò)的公平性。

3)網(wǎng)絡(luò)中擁有較大鏈路時(shí)延的節(jié)點(diǎn)優(yōu)先發(fā)送。時(shí)延較高的鏈路如果發(fā)送的較晚，到達(dá)目標(biāo)時(shí)的時(shí)間就會(huì)更晚。而優(yōu)先分配時(shí)延較高的鏈路，使得高時(shí)延的鏈路早發(fā)送，低時(shí)延的鏈路晚發(fā)送，有助于提高節(jié)點(diǎn)的傳輸并行度。

以上述3條啟發(fā)式規(guī)則為依據(jù)，可以實(shí)現(xiàn)定量計(jì)算節(jié)點(diǎn)的優(yōu)先級(jí)指標(biāo)。P(i)表示節(jié)點(diǎn)i的標(biāo)定優(yōu)先級(jí)，采用式(4)進(jìn)行計(jì)算。式(4)中使用的主要變量定義為：di為i在它自己的LCG圖中的度，Lmax為節(jié)點(diǎn)緩沖區(qū)的大小，Li為節(jié)點(diǎn)i的緩沖區(qū)隊(duì)列長(zhǎng)度。定義從節(jié)點(diǎn) i到基站的傳輸路徑上的下一跳節(jié)點(diǎn) k為節(jié)點(diǎn)i的父節(jié)點(diǎn)，Dik為節(jié)點(diǎn)i到其父節(jié)點(diǎn)k的鏈路傳播時(shí)延。定義Dmax是整個(gè)網(wǎng)絡(luò)中的最大的鏈路傳播時(shí)延，即網(wǎng)絡(luò)中距離最長(zhǎng)的一跳鏈路長(zhǎng)度與水聲信號(hào)的傳播速度的比值，該值在網(wǎng)絡(luò)部署時(shí)可以進(jìn)行估計(jì)并設(shè)定在所有節(jié)點(diǎn)中。由于CT-TDMA協(xié)議運(yùn)行的環(huán)境為靜態(tài)網(wǎng)絡(luò)，該值在協(xié)議運(yùn)行過程中不會(huì)改變。而且，該值僅涉及到優(yōu)先級(jí)的計(jì)算，對(duì)于所有節(jié)點(diǎn)的計(jì)算效果是等價(jià)的，因此該值的估計(jì)精度對(duì)于本文提出的CT-TDMA協(xié)議的運(yùn)行效果沒有直接影響。

3條啟發(fā)式規(guī)則的重要性在式(4)中直接體現(xiàn)：擁有最大度的節(jié)點(diǎn)擁有最高的標(biāo)定優(yōu)先級(jí)；如果節(jié)點(diǎn)的度相同則負(fù)載較重的節(jié)點(diǎn)優(yōu)先級(jí)高；如果節(jié)點(diǎn)的負(fù)載也相同，則擁有最長(zhǎng)鏈路時(shí)延的節(jié)點(diǎn)優(yōu)先級(jí)高。當(dāng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，節(jié)點(diǎn)負(fù)載等條件不發(fā)生變化時(shí)，網(wǎng)絡(luò)可以根據(jù)CT-TDMA計(jì)算出的調(diào)度順序持續(xù)的運(yùn)行。而當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或者節(jié)點(diǎn)負(fù)載等條件發(fā)生變化時(shí)，即節(jié)點(diǎn)的標(biāo)定優(yōu)先級(jí)發(fā)生變化時(shí)，協(xié)議將在整個(gè)網(wǎng)絡(luò)重新運(yùn)行，以保持節(jié)點(diǎn)的發(fā)送時(shí)間分配始終為當(dāng)前的最優(yōu)策略。

2.4 算法實(shí)例

為了清晰地說明CT-TDMA的基本思想、工作流程及特點(diǎn)，本節(jié)給出一個(gè)簡(jiǎn)單的網(wǎng)絡(luò)實(shí)例進(jìn)行說明，如圖5(a)所示。鏈路上的標(biāo)記為該條鏈路的時(shí)延（單位為s），設(shè)幀時(shí)T為1s。

各節(jié)點(diǎn)首先運(yùn)行 createLCG()函數(shù)生成自己的局部沖突狀態(tài)圖，4個(gè)節(jié)點(diǎn)的LCG如圖5(b)所示。

圖5 CT-TDMA的執(zhí)行過程(實(shí)線表示邏輯鏈路，虛線表示點(diǎn)到點(diǎn)之間的時(shí)延)

然后，所有節(jié)點(diǎn)計(jì)算自己的優(yōu)先級(jí)。在圖5(b)中4個(gè)節(jié)點(diǎn)的度相同，在所有節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)分組的頻率相同的情況下，對(duì)于A節(jié)點(diǎn)來說，它不僅要發(fā)送自己的數(shù)據(jù)分組，還要轉(zhuǎn)發(fā)來自 B和 D的分組，A節(jié)點(diǎn)的緩沖區(qū)隊(duì)列長(zhǎng)度必將比B、C、D節(jié)點(diǎn)的更長(zhǎng)，因此A節(jié)點(diǎn)的負(fù)載最重，優(yōu)先級(jí)最高。B、C、D負(fù)載相同，因此按鏈路的時(shí)延排序，相關(guān)鏈路時(shí)延高者優(yōu)先級(jí)高，最終標(biāo)定順序?yàn)?A、B、D、C。

因此，A首先選擇0時(shí)刻并廣播給B、C、D。B根據(jù)公式計(jì)算出A對(duì)B的禁止時(shí)間為(-3.9, -1.9)∪(-4.5, -2.5)，所以B也可選擇0時(shí)刻。D根據(jù)A和B的標(biāo)定結(jié)果，計(jì)算A和B對(duì)自己的禁止時(shí)間為(-5, -3)∪(-1.5, 0.5)，于是D選擇自己的發(fā)送時(shí)刻為0.5。最后，C計(jì)算A、B、D對(duì)自己帶來的禁止時(shí)間為(-2.7, -0.7) ∪(0.2, 2.2) ∪(-0.8, 1.2)，C 選擇自己的發(fā)送時(shí)刻為 2.2s。4個(gè)節(jié)點(diǎn)的正數(shù)禁止時(shí)間在圖5(c)中給出。禁止時(shí)間的負(fù)數(shù)部分不影響節(jié)點(diǎn)發(fā)送時(shí)刻的選擇，故未給出。最后，A、B、C和D 4個(gè)節(jié)點(diǎn)分別確定自己的發(fā)送時(shí)刻為 0s、0s、2.2s和0.5s。

本例說明，CT-TDMA提高了數(shù)據(jù)發(fā)送的并行度。例如，A和B節(jié)點(diǎn)都在0時(shí)刻發(fā)送而不會(huì)沖突，這在傳統(tǒng)的WSN中是無法實(shí)現(xiàn)的。UWSN正是由于傳播時(shí)延高、通信距離長(zhǎng)和數(shù)據(jù)分組短，導(dǎo)致了不同發(fā)送節(jié)點(diǎn)的數(shù)據(jù)分組到達(dá)接收端的時(shí)刻存在差異。CT-TDMA利用UWSN的這種特性，避免了沖突，提高了網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)牟⑿卸?，達(dá)到提高網(wǎng)絡(luò)流量的目的。

3 仿真

本節(jié)介紹CT-TDMA的仿真結(jié)果，并對(duì)算法的性能進(jìn)行分析和對(duì)比。使用了MATLAB等軟件對(duì)算法進(jìn)行了仿真，在仿真過程中，幀時(shí)T設(shè)定為1s，節(jié)點(diǎn)的通信半徑為3 000m，干擾半徑為3 500m，網(wǎng)絡(luò)包括從5個(gè)節(jié)點(diǎn)到60個(gè)節(jié)點(diǎn)的4種規(guī)模。根據(jù)網(wǎng)絡(luò)規(guī)模的變化，節(jié)點(diǎn)被部署在最大 12km×12km的范圍內(nèi)，通過隨機(jī)部署的方式，利用部署密度限制節(jié)點(diǎn)和鄰居節(jié)點(diǎn)之間的距離在450m到3 000m之間。因?yàn)樗曅盘?hào)的速度為1 500m/s，所以網(wǎng)絡(luò)中鏈路的時(shí)延被控制在0.3s～2s之間。

由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)節(jié)點(diǎn)的傳輸并行度有重要影響，因此對(duì)比了一般的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)（節(jié)點(diǎn)隨機(jī)投放并自組織成樹形拓?fù)浣Y(jié)構(gòu)），以及特殊的星形、線形和網(wǎng)格，共4種拓?fù)浣Y(jié)構(gòu)對(duì)算法的影響。在4種拓?fù)浣Y(jié)構(gòu)下，均采用4種網(wǎng)絡(luò)規(guī)模完成了16組實(shí)驗(yàn)。在仿真中使用平均每秒鐘整個(gè)網(wǎng)絡(luò)發(fā)送的有效信息量作為評(píng)價(jià)網(wǎng)絡(luò)流量的指標(biāo)，即節(jié)點(diǎn)發(fā)送的數(shù)據(jù)信息字節(jié)數(shù)。ST-MAC幀長(zhǎng)度為 45byte[13](40byte有效數(shù)據(jù))，CT-TDMA的幀長(zhǎng)度為105byte(100byte有效數(shù)據(jù))。在仿真中模擬了4種不同的接入分配算法。

1) Optimal: 實(shí)驗(yàn)網(wǎng)絡(luò)部署情況下的理論上最優(yōu)的分配策略，該策略能夠最大限度地利用信道和提高節(jié)點(diǎn)的傳輸并行度，為其他算法提供理論的最佳上界。最優(yōu)策略的求解，即針對(duì)實(shí)驗(yàn)環(huán)境下的網(wǎng)絡(luò)拓?fù)?，在所有可能的?jié)點(diǎn)接入方案中，選取全部節(jié)點(diǎn)的一輪接入時(shí)間最短的接入方案。

2) CT-TDMA: 本文提出的分配策略。

3) ST-MAC: 文獻(xiàn)[13]提出的跨時(shí)隙TDMA分配策略。

4) S-TDMA: 傳統(tǒng)的UWSN單時(shí)隙TDMA。

圖6中對(duì)比了4種調(diào)度算法在4種不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的流量情況。可以看出，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)流量有明顯的影響，線形、樹形、網(wǎng)格到星形網(wǎng)絡(luò)流量依次降低，這是由于隨著拓?fù)涞淖兓?jié)點(diǎn)的密度逐漸增加，即共享同一個(gè)信道的節(jié)點(diǎn)數(shù)目越來越多，因此能夠同時(shí)并行傳輸?shù)墓?jié)點(diǎn)數(shù)目就變得越來越少。除星形拓?fù)渲?，在其他拓?fù)浣Y(jié)構(gòu)和協(xié)議下，網(wǎng)絡(luò)流量均隨著網(wǎng)絡(luò)規(guī)模的增加而增加。星形拓?fù)浣Y(jié)構(gòu)表現(xiàn)特殊的原因是，在該環(huán)境中所有節(jié)點(diǎn)均一跳傳向基站，因此任意2個(gè)節(jié)點(diǎn)均互為沖突鄰居，所有的節(jié)點(diǎn)共享同一個(gè)信道，無法提高數(shù)據(jù)傳輸?shù)牟⑿卸取?/p>

圖 6顯示，當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，CT-TDMA和ST-MAC均能夠達(dá)到或接近理論最優(yōu)的效果。當(dāng)網(wǎng)絡(luò)規(guī)模逐漸增大時(shí)，CT-TDMA和ST-MAC的流量均不能達(dá)到理論最優(yōu)值，但CT-TDMA的性能始終優(yōu)于ST-MAC（平均高20%以上），并達(dá)到理論最優(yōu)值的 80%左右。而 S-TDMA的表現(xiàn)最差，因?yàn)樵摲桨篙^長(zhǎng)的時(shí)隙給接收端帶來大量空閑時(shí)間。

CT-TDMA優(yōu)于 ST-MAC的原因在于，ST-MAC采用時(shí)隙調(diào)度策略為節(jié)點(diǎn)分配發(fā)送時(shí)間，這種策略規(guī)定節(jié)點(diǎn)只能在每個(gè)時(shí)隙的開始時(shí)刻發(fā)送幀。此外，ST-MAC要求所有鏈路時(shí)延是幀時(shí)的整數(shù)倍。為了確保這一點(diǎn)，ST-MAC協(xié)議中的分組長(zhǎng)度必須盡可能小，進(jìn)一步引起幀中有效數(shù)據(jù)比例下降。其原因是，雖然幀長(zhǎng)度縮短，幀中的校驗(yàn)和確認(rèn)位并不減少。CT-TDMA采用連續(xù)時(shí)間分配策略，并不需要ST-MAC的上述設(shè)定，因此可以應(yīng)用更長(zhǎng)的數(shù)據(jù)幀，從而提高了網(wǎng)絡(luò)流量。

圖6 4種協(xié)議在不同網(wǎng)絡(luò)規(guī)模和拓?fù)浣Y(jié)構(gòu)下的流量對(duì)比

圖7記錄了4種協(xié)議在一般網(wǎng)絡(luò)情況即樹形拓?fù)浣Y(jié)構(gòu)下的端到端時(shí)延情況。傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸模式為所有的節(jié)點(diǎn)向基站傳輸數(shù)據(jù)，因此端到端時(shí)延即為數(shù)據(jù)分組從源節(jié)點(diǎn)到基站的傳播時(shí)延。從圖7可以看出，隨著網(wǎng)絡(luò)規(guī)模的增大，節(jié)點(diǎn)到基站的平均跳數(shù)增加，端到端時(shí)延也相應(yīng)增加。由于CT-TDMA使用了連續(xù)時(shí)間分配策略，在接收節(jié)點(diǎn)處縮短了幀與幀之間的空閑時(shí)間，提高了傳輸效率，其平均端到端時(shí)延比ST-MAC降低了約18%，并且只比理論最優(yōu)策略的時(shí)延高 12%。可見，CT-TDMA不僅網(wǎng)絡(luò)流量要高于傳統(tǒng)協(xié)議，平均的端到端時(shí)延也更低，實(shí)時(shí)性更好。

圖7 4種協(xié)議的平均端到端時(shí)延

從計(jì)算代價(jià)的角度分析，ST-MAC為集中式算法，需要從所有的全局調(diào)度方案中尋找最優(yōu)方案，而CT-TDMA采用分布式的調(diào)度策略，每個(gè)節(jié)點(diǎn)的計(jì)算代價(jià)都比 ST-MAC小很多，因此計(jì)算時(shí)間更短。從能量消耗的角度分析，ST-MAC和CT-TDMA均屬于 TDMA協(xié)議，數(shù)據(jù)傳輸階段沒有沖突，因此能量效率都很高。額外的能量消耗僅在于協(xié)議的初始化階段，ST-MAC需要基站收集全網(wǎng)絡(luò)的信息和分發(fā)調(diào)度策略，CT-TDMA僅需要各個(gè)節(jié)點(diǎn)與其Cov(RI+RT)范圍內(nèi)的鄰居進(jìn)行信息交換。當(dāng)網(wǎng)絡(luò)規(guī)模急劇增大時(shí)，ST-MAC洪泛和廣播的通信開銷要遠(yuǎn)大于CT-TDMA的分布式信息交互。

4 相關(guān)工作

近年來，UWSN的MAC問題由于水聲通信的獨(dú)特特點(diǎn)引起廣泛關(guān)注。相關(guān)研究成果可分為基于競(jìng)爭(zhēng)的接入控制協(xié)議和無沖突的接入?yún)f(xié)議2類。

接入競(jìng)爭(zhēng)控制協(xié)議，通過以接收端為中心的虛擬載波監(jiān)聽協(xié)議來解決 MAC問題。文獻(xiàn)[9]使用RTS/CTS握手機(jī)制來建立信道預(yù)約。節(jié)點(diǎn)通過截獲鄰居信息的方式計(jì)算各個(gè)鄰居節(jié)點(diǎn)的忙時(shí)間，然后在這段時(shí)間內(nèi)停止偵聽信道。文獻(xiàn)[6]研究了水聲信道特征對(duì)Aloha協(xié)議的影響，進(jìn)而提出水聲通信的沖突狀態(tài)具有時(shí)空不確定性的特點(diǎn)。文獻(xiàn)[8]和文獻(xiàn)[10]基于 Aloha協(xié)議，使用一個(gè)短幀來預(yù)約信道，避免數(shù)據(jù)分組的沖突。T-Lohi協(xié)議[7]針對(duì)水聲信道沖突的時(shí)空不確定性設(shè)計(jì)了一個(gè)特殊的退避算法，在高負(fù)載的環(huán)境中具有較高的流量。

無沖突的接入?yún)f(xié)議基于TDMA和CDMA。針對(duì)UWSN設(shè)計(jì)的TDMA協(xié)議分為單時(shí)隙和跨時(shí)隙2種，單時(shí)隙協(xié)議要求一跳范圍內(nèi)的數(shù)據(jù)傳輸必須在一個(gè)時(shí)隙完成。UWAN-MAC[11]允許節(jié)點(diǎn)隨機(jī)地選擇時(shí)隙進(jìn)行傳輸。文獻(xiàn)[12]提出的混合協(xié)議將TDMA和競(jìng)爭(zhēng)協(xié)議相結(jié)合，充分利用了競(jìng)爭(zhēng)協(xié)議時(shí)延較低而TDMA流量較高的優(yōu)點(diǎn)。

跨時(shí)隙的協(xié)議允許使用多個(gè)時(shí)隙完成數(shù)據(jù)分組傳輸。最近提出的ST-MAC[13]是第一個(gè)跨時(shí)隙的TDMA協(xié)議，該協(xié)議以整個(gè)網(wǎng)絡(luò)的沖突狀態(tài)圖為基礎(chǔ)，采用集中式算法計(jì)算各個(gè)節(jié)點(diǎn)的最優(yōu)發(fā)送時(shí)隙。ST-MAC需要收集全局信息并且假設(shè)網(wǎng)絡(luò)中的任意鏈路時(shí)延都是發(fā)送幀時(shí)的整數(shù)倍，通過分配時(shí)隙的方式，使得不同節(jié)點(diǎn)的幀到達(dá)目的端的時(shí)隙不相同（即不會(huì)產(chǎn)生沖突）。該協(xié)議的時(shí)隙長(zhǎng)度比傳統(tǒng)協(xié)議要短的多，利用鏈路時(shí)延的差異性減少了接收幀之間的空閑時(shí)間，與傳統(tǒng)的單時(shí)隙的 TDMA相比提高了網(wǎng)絡(luò)流量。本文提出的 CT-TDMA和ST-MAC相比，不依賴于時(shí)延與幀時(shí)關(guān)系的假設(shè)，并且采用連續(xù)時(shí)間的分配方式代替時(shí)隙分配，減少了信道空閑時(shí)間，提高了網(wǎng)絡(luò)流量。

除了 TDMA之外，研究者還提出了針對(duì)水下環(huán)境的改進(jìn)CDMA協(xié)議[18,19]，文獻(xiàn)[19]提出的混合協(xié)議使用對(duì)節(jié)點(diǎn)分簇的策略，簇內(nèi)節(jié)點(diǎn)通信使用TDMA協(xié)議，不同的簇之間的節(jié)點(diǎn)通信則使用CDMA協(xié)議。然而目前在UWSN中使用CDMA協(xié)議還面臨很多困難，對(duì)大規(guī)模的傳感器節(jié)點(diǎn)分配偽隨機(jī)碼是一項(xiàng)艱巨的挑戰(zhàn)，此外，水聲通信中使用CDMA的遠(yuǎn)近效應(yīng)問題也沒有得到很好地解決[18]。

5 結(jié)束語

針對(duì)水下無線傳感器網(wǎng)絡(luò)時(shí)延高、帶寬低和誤碼率高的特性，本文提出了以發(fā)送端為中心以連續(xù)時(shí)間為計(jì)量單位的沖突狀態(tài)模型——局部沖突狀態(tài)圖（LCG）及其分布式構(gòu)建算法，并在此基礎(chǔ)上設(shè)計(jì)了基于啟發(fā)式規(guī)則的水下傳感器網(wǎng)絡(luò) TDMA協(xié)議。CT-TDMA利用UWSN中同一接收節(jié)點(diǎn)與不同發(fā)送節(jié)點(diǎn)之間鏈路時(shí)延的差異性，與現(xiàn)有協(xié)議相比進(jìn)一步減少了節(jié)點(diǎn)接收幀序列的空閑時(shí)間，提高了網(wǎng)絡(luò)流量。并且，基于啟發(fā)式規(guī)則的分配算法，有效縮短了節(jié)點(diǎn)在連續(xù)時(shí)間軸上進(jìn)行時(shí)刻分配的運(yùn)行時(shí)間。仿真表明，與ST-MAC和S-TDMA等基于時(shí)隙分配的水下傳感器網(wǎng)絡(luò) TDMA協(xié)議相比，CT-TDMA能夠?qū)崿F(xiàn)更高的網(wǎng)絡(luò)流量和更低的端到端傳播時(shí)延。

[1] 李建中, 高宏. 無線傳感網(wǎng)絡(luò)的研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展,2008,45(1): 1-15.LI J Z, GAO H. Research progress of wireless sensor networks[J].Journal of Computer Research and Development, 2008,45 (1): 1-15.

[2] 李瑞芳, 李仁發(fā), 羅娟. 無線多媒體傳感器網(wǎng)絡(luò) MAC 協(xié)議研究綜述[J] . 通信學(xué)報(bào), 2008,29 (8): 111-123.LI R F, LI R F, LUO J. Research review on MAC protocols of wireless multimedia sensor networks[J]. Journal on Communications, 2008.29 (8): 111-123.

[3] HEIDEMANN J, LI Y, SYED A. Research challenges and applications for underwater sensor networking[A]. Proc WCNC[C]. Las Vegas, NV, USA, 2006.228-235.

[4] SYED A, HEIDEMANN J. Time synchronization for high latency acoustic networks[A]. Proc INFOCOM 2006[C]. Barcelona, Catalunya,Spain, 2006.1-12.

[5] HARRIS A F III, STOJANOVIC M, ZORZI M. When underwater acoustic nodes should sleep with one eye open: Idle-time power management in underwater sensor networks[A]. Proc ACM WUWNET[C].Los Angeles, CA, USA, 2006.105-108.

[6] SYED A, YE W, HEIDEMANN J. Understanding spatial-temporal uncertainty in medium access with ALOHA protocols[A]. Proc ACM WUWNET[C]. Montréal, Québec, Canada, 2007.41-48.

[7] SYED A, YE W, HEIDEMANN J. T-lohi: a new class of MAC protocols for underwater acoustic sensor networks[A]. IEEE INFOCOM[C]. Phoenix, AZ, USA, 2008.231-235.

[8] GUO X, FRATER M, RYAN M. A propagation-delay-tolerant collision avoidance protocol for underwater acoustic sensor networks[A].OCEANS 2006-Asia Pacific[C]. Singapore, 2006.1-6.

[9] MOLINS M, STOJANOVIC M. Slotted FAMA: a MAC protocol for underwater acoustic networks[A]. OCEANS 2006-Asia Pacific[C].Singapore, 2006.1-7.

[10] CHIRDCHOO N, SOH W, CHUA K. Aloha-based MAC protocols with collision avoidance for underwater acoustic networks[A]. Proc IEEE INFOCOM[C]. Anchorage, Alaska, USA, 2007.2271-2275.

[11] PARK M, RODOPLU V. UWAN-MAC: an energy-efficient MAC protocol for underwater acoustic wireless sensor networks[J]. IEEE Journal of Oceanic Engineering, 2007, 32(3): 710-720.

[12] KURTIS I, KREDO B, MOHAPATRA P. A hybrid medium access control protocol for underwater wireless networks[A].Proc ACM WUWNET[C]. Montréal, Québec, Canada, 2007.33-40.

[13] HSU C C, LAI K F, CHOU C F. ST-MAC: spatial-temporal MAC scheduling for underwater sensor networks[A]. Proc IEEE INFOCOM[C]. Rio de Janeiro, Brazil, 2009.1827-1835.

[14] HONG L, HONG F, GUO Z W. A TDMA-based MAC protocol in underwater sensor networks[A]. The 4th International Conference on Wireless Communications, Networking, and Mobile Computing(WICOM’08)[C]. Dalian, China, 2008.1-4.

[15] DOWNEY P. The Behavior of a Flooding Protocol in a Wireless Sensor Network[R]. Report for the Honours Programme of the School of Computer Science and Software Engineering, the University of Western Australia, 2003.

[16] LIU YH, LIONEL M. Ni: a generalized probabilistic topology control for wireless sensor networks[A]. INFOCOM 2009[C]. Rio de Janeiro,Brazil, 2009.2776-2780.

[17] LUBY M. A simple parallel algorithm for the maximal independent set problem[J]. SIAM Journal on Computing, 1986, 15(4):1036-1053.

[18] TAN H X, SEAH W K G. Distributed CDMA-based MAC protocol for underwater sensor networks[A]. LCN[C]. Clontarf Castle, Dublin,Ireland, 2007.26-36.

[19] SALVA-GARAU F, STOJANOVIC M. Multi-cluster protocol for ad hoc mobile underwater acoustic networks[A]. Proc IEEE Oceans Conf[C]. San Diego, CA, USA, 2003.91-98.