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

（中國海洋大學 信息科學與工程學院 計算機科學與技術系，山東 青島 266100）

1 引言

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

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

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

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

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

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

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

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

本文的主要貢獻如下。

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

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

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

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

2 CT-TDMA設計

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

2.1 設計出發(fā)點

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

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

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

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

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

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

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

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

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

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

定義1 覆蓋范圍函數(shù)Cov(N, R)：以節(jié)點N為圓心，以R為半徑的區(qū)域。如節(jié)點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é)點集的操作 Nodeset(C)：C為水下傳感器網(wǎng)絡的某個部署區(qū)域，操作返回屬于該區(qū)域的節(jié)點集，即Nodeset(C)={N| (xn,yn)∈C}。

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

定義 4 沖突鄰居、沖突目標節(jié)點：節(jié)點之間的沖突關系是網(wǎng)絡物理拓撲和邏輯拓撲的直接反映。設N為網(wǎng)絡中的任一發(fā)送節(jié)點，節(jié)點N的發(fā)送操作對周圍節(jié)點可能造成的沖突主要表現(xiàn)在：對于不同于N的節(jié)點M而言，如果存在節(jié)點P，滿足P的位置在物理拓撲中位于M和N其中一個節(jié)點的通信范圍內(nèi)，同時位于另一節(jié)點的干擾范圍內(nèi)，并且，在邏輯拓撲中存在鏈路N-＞P或者M-＞P，那么P節(jié)點在接收N或者M其中一個節(jié)點的數(shù)據(jù)分組時，可能會受到來自另一節(jié)點的發(fā)送信號的干擾而無法接收，即在P點形成沖突。

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

當節(jié)點P、M同時滿足下列拓撲條件時，節(jié)點P是節(jié)點N的沖突目標節(jié)點，節(jié)點M是節(jié)點N的沖突鄰居：

① 物理拓撲條件：

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

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

② 邏輯拓撲條件：(N-＞P) || (M-＞P)

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

圖2 節(jié)點i的局部網(wǎng)絡拓撲結構

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

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

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

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

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

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

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

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

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

圖3 禁止時間的計算

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

2.3 CT-TDMA的主要算法

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

2.3.1 LCG生成算法

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

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

算法1 createLCG ()

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

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

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

2.3.2 CT-TDMA算法流程

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

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

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

1) 節(jié)點生成自己的LCG并計算自己的標定優(yōu)先級。

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

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

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

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

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

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

算法2 Label()

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

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

在Label()函數(shù)中引入隨機標定的設計，是因為在某些網(wǎng)絡中可能存在大量節(jié)點的優(yōu)先級相同。雖然可以采用節(jié)點 ID等強制優(yōu)先級方式，但類似的優(yōu)先級策略對優(yōu)化最終的總傳輸時間沒有幫助。隨機標定可以減少算法的執(zhí)行時間。比如，在極端的網(wǎng)絡拓撲條件下（如線形、星形），當節(jié)點的優(yōu)先級均相同時，順序標定算法的時間復雜度為 O(n)而隨機標定的時間復雜度為O(logn)[17]。其中，n為網(wǎng)絡中的節(jié)點個數(shù)。

算法3 Judge()

2.3.3 標定優(yōu)先級確定

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

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

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

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

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

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

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

2.4 算法實例

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

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

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

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

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

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

3 仿真

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

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

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

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

3) ST-MAC: 文獻[13]提出的跨時隙TDMA分配策略。

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

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

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

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

圖6 4種協(xié)議在不同網(wǎng)絡規(guī)模和拓撲結構下的流量對比

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

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

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

4 相關工作

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

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

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

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

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

5 結束語

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

[1] 李建中, 高宏. 無線傳感網(wǎng)絡的研究進展[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)絡 MAC 協(xié)議研究綜述[J] . 通信學報, 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.