CT-TDMA：水下傳感器網絡高效TDMA協議

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

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

1 引言

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

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

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

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

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

為了提高網絡流量，研究者提出了允許跨時隙完成數據傳輸的ST-MAC協議[13]。該協議假設所有的鏈路時延都是幀時的整數倍，利用啟發式規則完成多跳網絡的時隙分配，實現了較高的網絡流量。

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

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

本文的主要貢獻如下。

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

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

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

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

2 CT-TDMA設計

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

2.1 設計出發點

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

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

圖1 TDMA不同策略下的發送時間的分配

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

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

2.2 連續沖突狀態模型

為了清晰地描述CT-TDMA的連續沖突狀態模型，本節首先對運行環境做一些基本設定。

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

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

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

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

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

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

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

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

① 物理拓撲條件：

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

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

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

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

圖2 節點i的局部網絡拓撲結構

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

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

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

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

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

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

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

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

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

圖3 禁止時間的計算

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

2.3 CT-TDMA的主要算法

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

2.3.1 LCG生成算法

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

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

算法1 createLCG ()

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

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

圖4 節點i的局部沖突狀態圖（LCG）

2.3.2 CT-TDMA算法流程

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

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

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

1) 節點生成自己的LCG并計算自己的標定優先級。

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

3) 如果當前節點在其LCG圖中的所有未標定鄰居中擁有最高的優先級，則節點根據由 LCG得到的所有禁止時間段，選擇最早的可發送時刻作為自己的發送時刻，并將其廣播給所有的LCG鄰居，并將狀態置為“labeled”。

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

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

6) 隨機標定的節點選定發送時刻并與所有同優先級鄰居交換選定結果后，運行Judge()函數判斷是否會產生沖突，若無沖突，則置為“labeled”，否則置為“unlabeled”，并返回第5)步。

7) LCG圖中的所有節點狀態均為“labeled”時，算法結束。

算法2 Label()

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

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

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

算法3 Judge()

2.3.3 標定優先級確定

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

CT-TDMA的算法目的是提高網絡流量，即所有節點均發送一次數據所使用的總時間越短越好。針對這個設計目標，提出重要性依次降低的3條啟發式的優先級制定規則如下。

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

2)負載較重的節點優先發送。負載較重的節點優先發送有助于縮短每個分組端到端的平均時延，實現網絡的公平性。

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

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

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

2.4 算法實例

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

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

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

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

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

本例說明，CT-TDMA提高了數據發送的并行度。例如，A和B節點都在0時刻發送而不會沖突，這在傳統的WSN中是無法實現的。UWSN正是由于傳播時延高、通信距離長和數據分組短，導致了不同發送節點的數據分組到達接收端的時刻存在差異。CT-TDMA利用UWSN的這種特性，避免了沖突，提高了網絡中數據傳輸的并行度，達到提高網絡流量的目的。

3 仿真

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

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

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

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

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

4) S-TDMA: 傳統的UWSN單時隙TDMA。

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

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

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

圖6 4種協議在不同網絡規模和拓撲結構下的流量對比

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

圖7 4種協議的平均端到端時延

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

4 相關工作

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

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

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

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

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

5 結束語

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

[1] 李建中, 高宏. 無線傳感網絡的研究進展[J]. 計算機研究與發展,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] 李瑞芳, 李仁發, 羅娟. 無線多媒體傳感器網絡 MAC 協議研究綜述[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.