洪璐,洪鋒,李正寶,郭忠文
(中國(guó)海洋大學(xué) 信息科學(xué)與工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,山東 青島 266100)
水下無線傳感器網(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é)束語。
本節(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é)果。
解決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)。
為了清晰地描述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ù)涞闹苯臃从场TO(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)。
本節(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)策略。
為了清晰地說明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ò)流量的目的。
本節(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的分布式信息交互。
近年來,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]。
針對(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.