基于水壓的抑制路由空洞的UWSNs路由算法

尹鴻坦

(黃淮學(xué)院信息工程學(xué)院，河南 駐馬店 463000)

0 引 言

最近，水下傳感網(wǎng)絡(luò)(Underwater Wireless Sensor Networks, UWSNs)受到廣泛關(guān)注，且UWSNs被廣泛應(yīng)用自然災(zāi)害預(yù)防、水特征測(cè)量、水區(qū)域開(kāi)發(fā)和污染控制等[1-3]。由于水域環(huán)境的特殊性，UWSNs引用聲通信。每個(gè)傳感節(jié)點(diǎn)裝備了聲通信模型，這些傳感節(jié)點(diǎn)感測(cè)環(huán)境數(shù)據(jù)，然后將這些數(shù)據(jù)以多跳方式傳輸至最近的信宿(聲納浮標(biāo))。而信宿既裝備了聲通信模型又裝備無(wú)線(xiàn)射頻通信模型[4-5]，它們浮于水面。這些信宿收集數(shù)據(jù)，然后通過(guò)無(wú)線(xiàn)射頻通信傳輸至數(shù)據(jù)控制中心。UWSNs通信示意圖如圖1所示。

圖1 UWSNs通信示意圖

UWSNs中的傳感節(jié)點(diǎn)通過(guò)壓力計(jì)估算自己的水壓，然后再建立數(shù)據(jù)鏈路。然而，由于水域環(huán)境的惡劣，導(dǎo)致數(shù)據(jù)包丟失，致使數(shù)據(jù)包無(wú)法到達(dá)目的節(jié)點(diǎn)。為了提高數(shù)據(jù)包傳遞率，常采用無(wú)線(xiàn)傳感網(wǎng)絡(luò)的路由思想，即利用鄰居信息位置傳輸數(shù)據(jù)包，常用算法有基于地理位置的貪婪轉(zhuǎn)發(fā)策略。在貪婪轉(zhuǎn)發(fā)策略中，總是選擇離信宿最近的節(jié)點(diǎn)作下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。貪婪轉(zhuǎn)發(fā)策略只適用于密集節(jié)點(diǎn)區(qū)域。在稀疏區(qū)域，節(jié)點(diǎn)容易遭遇路由空洞問(wèn)題。

針對(duì)UWSNs路由，研究人員已提出不同的路由算法。Yan等[6]利用節(jié)點(diǎn)深度建立路由，并提出(Depth-based routing，DBR)路由。DBR路由結(jié)合節(jié)點(diǎn)深度，并引用貪婪算法轉(zhuǎn)發(fā)數(shù)據(jù)包，但是DBR并沒(méi)有考慮到路由空洞問(wèn)題。而文獻(xiàn)[7]考慮了路由空洞問(wèn)題。一旦節(jié)點(diǎn)遭遇路由空洞，節(jié)點(diǎn)就簡(jiǎn)單地選擇比自己深度高的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包。文獻(xiàn)[8]也提出了水壓感知路由 (Void-aware pressure routing，VAPR)。信宿周期廣播位置消息，進(jìn)而使得傳感節(jié)點(diǎn)獲取信宿位置。同時(shí)，通過(guò)有向數(shù)據(jù)傳輸路徑，應(yīng)對(duì)路由空洞問(wèn)題。

本文針對(duì)UWSNs數(shù)據(jù)傳輸問(wèn)題，提出HPSRV路由。HPSRV路由先依據(jù)節(jié)點(diǎn)轉(zhuǎn)發(fā)權(quán)值，構(gòu)建轉(zhuǎn)發(fā)節(jié)點(diǎn)集，然后再引用定時(shí)器機(jī)制，擇優(yōu)產(chǎn)生轉(zhuǎn)發(fā)節(jié)點(diǎn)。HPSRV路由考慮了路由空洞問(wèn)題，并利用邊界度量值，產(chǎn)生邊界轉(zhuǎn)發(fā)節(jié)點(diǎn)，減少邊界轉(zhuǎn)發(fā)跳數(shù)。實(shí)驗(yàn)數(shù)據(jù)表明，提出的HPSRV路由有效地提高了數(shù)據(jù)包傳遞率，也降低了傳輸時(shí)延。

2 HPSRV算法

HPSRV路由是基于水壓的路由協(xié)議。在轉(zhuǎn)發(fā)數(shù)據(jù)過(guò)程中，融合了當(dāng)前節(jié)點(diǎn)位置、鄰居信息和信宿位置信息，并引用貪婪轉(zhuǎn)發(fā)策略傳輸數(shù)據(jù)包。實(shí)際上，轉(zhuǎn)發(fā)數(shù)據(jù)包的關(guān)鍵在于如何選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。為此，HPSRV路由先利用網(wǎng)絡(luò)信息建立候選集，再計(jì)算集內(nèi)節(jié)點(diǎn)的轉(zhuǎn)發(fā)權(quán)值，然后依據(jù)權(quán)值設(shè)置轉(zhuǎn)發(fā)定時(shí)器，進(jìn)而減小轉(zhuǎn)發(fā)冗余。同時(shí)，考慮到節(jié)點(diǎn)部署稀疏區(qū)域，可能會(huì)出現(xiàn)路由空洞問(wèn)題，為此，提出基于邊界權(quán)值的邊界轉(zhuǎn)發(fā)策略。

2.1 轉(zhuǎn)發(fā)節(jié)點(diǎn)集

假定N=Nn∪Ns表示網(wǎng)絡(luò)節(jié)點(diǎn)集，其中Nn表示傳感節(jié)點(diǎn)集，即Nn={n1,n2,…,n|Nn|}，而Ns為聲納浮標(biāo)集，即Ns={s1,s2,…,s|Ns|}。其中|·|表示集元素的個(gè)數(shù)。

若節(jié)點(diǎn)ni需要轉(zhuǎn)發(fā)數(shù)據(jù)包，需要建立轉(zhuǎn)發(fā)節(jié)點(diǎn)集。假定此時(shí)刻為t，Ni(t)表示節(jié)點(diǎn)ni的一跳鄰居集，相應(yīng)地，Si(t)表示節(jié)點(diǎn)ni可達(dá)到的信宿集。

對(duì)于任意鄰居節(jié)點(diǎn)nk∈Ni(t)，如果節(jié)點(diǎn)nk滿(mǎn)足式(1)條件，就成為節(jié)點(diǎn)ni的轉(zhuǎn)發(fā)節(jié)點(diǎn)集。

d(nk,s?)|>0}

(1)

接下來(lái)，計(jì)算轉(zhuǎn)發(fā)節(jié)點(diǎn)集Γi內(nèi)每個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)權(quán)值。轉(zhuǎn)發(fā)權(quán)值反映了節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的“適度性”。假定NADV(nc)表示節(jié)點(diǎn)nc∈Γi的轉(zhuǎn)發(fā)權(quán)值，其定義如式(2)所示：

NADV(nc)=ADV(nc)×p(m,d(nc,ni))

(2)

式(2)中的p(m,d(nc,ni))表示數(shù)據(jù)包傳遞概率，其表示傳輸m比特，且傳輸距離為d(nc,ni)的數(shù)據(jù)包傳輸成功率，其定義如式(3)所示：

p(m,d)=(1-pe(d))m

(3)

而pe(d)距離為d的路徑的比特誤碼概率[10]，定義如式(4)所示：

(4)

式(4)中Γ(d)為水下聲信道的平均信噪比，定義如式(5)所示。

(5)

其中f為信號(hào)頻率。A(d,f)表示路徑衰落、a(f)是吸收系數(shù)、k是擴(kuò)頻因子。

2.2 下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)

轉(zhuǎn)發(fā)集內(nèi)節(jié)點(diǎn)均有可能成為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。因此，集內(nèi)節(jié)點(diǎn)通過(guò)設(shè)置定時(shí)器，擇優(yōu)產(chǎn)生下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

假定節(jié)點(diǎn)ni需要選擇轉(zhuǎn)發(fā)數(shù)據(jù)包，并且已形成轉(zhuǎn)發(fā)節(jié)點(diǎn)集Γi。為此，節(jié)點(diǎn)ni將Γi載入數(shù)據(jù)包首部，然后向其鄰居節(jié)點(diǎn)廣播。一旦接收到此數(shù)據(jù)包，鄰居節(jié)點(diǎn)就從首部提取轉(zhuǎn)發(fā)節(jié)點(diǎn)集Γi，并判斷自己是否是集Γi內(nèi)節(jié)點(diǎn)。若不是，則丟棄數(shù)據(jù)包，否則就依據(jù)式(6)設(shè)置定時(shí)器。

Tk=α(rmax-d(nk,ni))

(6)

其中Tk為節(jié)點(diǎn)nk∈Γi的定時(shí)值。其中rmax表示節(jié)點(diǎn)的最大傳輸距離[11]。α為控制參數(shù)。

一旦定時(shí)完畢，且沒(méi)有其它節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包，則節(jié)點(diǎn)nk立即轉(zhuǎn)發(fā)數(shù)據(jù)包。通過(guò)設(shè)置定時(shí)器，能控制數(shù)據(jù)包的冗余。而參數(shù)α值對(duì)定時(shí)值有直接的影響。因此，需要慎重選擇。

圖2 設(shè)置定時(shí)器模型分析

如圖2所示，節(jié)點(diǎn)ni的轉(zhuǎn)發(fā)節(jié)點(diǎn)集Γi內(nèi)有兩個(gè)節(jié)點(diǎn)na、nb，并且na離水面浮標(biāo)距離比節(jié)點(diǎn)nb近。為了能快速傳輸數(shù)據(jù)包，節(jié)點(diǎn)na的定時(shí)時(shí)間Ta應(yīng)小于節(jié)點(diǎn)nb的定時(shí)時(shí)間Tb，而式(6)滿(mǎn)足了此要求。從式(6)可知，離節(jié)點(diǎn)ni距離越大，定時(shí)時(shí)間越短。

2.3 基于邊界轉(zhuǎn)發(fā)的路由空洞

盡管HPSRV協(xié)議在選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，考慮了鄰居信息，但是在節(jié)點(diǎn)密度稀疏時(shí)，仍存在路由空洞問(wèn)題，特別是長(zhǎng)路徑路由，如圖3所示。從圖3可知，源節(jié)點(diǎn)遭遇路由空洞。為此，HPSRV利用邊界轉(zhuǎn)發(fā)數(shù)據(jù)包，最終，將數(shù)據(jù)傳輸至信宿。

圖3 路由空洞示意圖

然而，從圖3可知，利用邊界轉(zhuǎn)發(fā)處理路由空洞，增加了路徑傳輸跳數(shù)，這不利于節(jié)點(diǎn)能耗下降，也增加了傳輸時(shí)延。為此，針對(duì)路由空洞，HPSRV協(xié)議計(jì)算每個(gè)節(jié)點(diǎn)的邊界權(quán)值[12]，并利用邊界權(quán)值轉(zhuǎn)發(fā)數(shù)據(jù)包。

一旦節(jié)點(diǎn)遭遇路由空洞，就啟動(dòng)邊界轉(zhuǎn)發(fā)模型。據(jù)此，節(jié)點(diǎn)就計(jì)算邊界度量值，并選擇邊界度量值最大的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。假定節(jié)點(diǎn)nk的邊界度量值為FS_mk，其定義如式(7)所示：

(7)

其中dk、ds分別表示節(jié)點(diǎn)nk離目的節(jié)點(diǎn)、源節(jié)點(diǎn)離目的節(jié)點(diǎn)的距離。

而θ表示節(jié)點(diǎn)nk與源節(jié)點(diǎn)的連線(xiàn)和節(jié)點(diǎn)nk與目的節(jié)點(diǎn)連線(xiàn)的夾角，如圖4所示。利用三角知識(shí)，可得：

(8)

圖4 夾角示意圖

通過(guò)邊界權(quán)值選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，進(jìn)而處理路由空洞，并減少了傳輸跳數(shù)。如圖5所示，節(jié)點(diǎn)x為源節(jié)點(diǎn)，節(jié)點(diǎn)D為目的節(jié)點(diǎn)。節(jié)點(diǎn)x處于路由空洞狀態(tài)。若采用邊界轉(zhuǎn)發(fā)的策略，傳輸路徑x→a→b→d。盡管此路徑能避開(kāi)路由空洞，但傳輸跳數(shù)過(guò)多。而HPSRV協(xié)議引用邊界度量值選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。即依據(jù)式(7)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，節(jié)點(diǎn)d的邊界度量最大，即節(jié)點(diǎn)x直接選擇節(jié)點(diǎn)d作為下一跳節(jié)點(diǎn)，這樣避開(kāi)了路由空洞，又減少了傳輸跳數(shù)。

圖5 HPSRV路由的邊界轉(zhuǎn)發(fā)模式

2.4 HPSRV路由的數(shù)據(jù)傳輸流程

一旦接收數(shù)據(jù)包，節(jié)點(diǎn)就檢測(cè)自己是否為目的節(jié)點(diǎn)，若是，則結(jié)束，否則就判斷自己是否為路由空洞節(jié)點(diǎn)。若是，就先構(gòu)建轉(zhuǎn)發(fā)節(jié)點(diǎn)集，然后依據(jù)式(6)設(shè)置定時(shí)器，并優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)包；否則，就進(jìn)入邊界轉(zhuǎn)發(fā)，并利用式(7)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，整個(gè)數(shù)據(jù)轉(zhuǎn)發(fā)流程如圖6所示。

圖6 HPSRV路由轉(zhuǎn)發(fā)數(shù)據(jù)包流程圖

3 仿真實(shí)驗(yàn)及性能分析

3.1 仿真環(huán)境

為了更好地分析HPSRV協(xié)議性能，利用MATLAB R2012b建立仿真平臺(tái)，并進(jìn)行仿真。在1500 m×1500 m×1500 m仿真區(qū)域內(nèi)聲納浮標(biāo)(信宿)|Ns|=45、傳感節(jié)點(diǎn)數(shù)|Nn|=150～450變化。假定傳感節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)包率λ從0.01 pkts/min至0.25 pkts/min，數(shù)據(jù)包大小為50kbps。每個(gè)實(shí)驗(yàn)獨(dú)立重復(fù)50次，取平均值作為最終實(shí)驗(yàn)數(shù)據(jù)。

此外，選用DBR和VAPR協(xié)議作為參照，并與HPSRV協(xié)議進(jìn)行比較。同時(shí)，選擇數(shù)據(jù)包傳遞率、數(shù)據(jù)包傳輸時(shí)延和冗余數(shù)據(jù)包數(shù)作為性能指標(biāo)。其中冗余數(shù)據(jù)包數(shù)是指每傳輸一個(gè)數(shù)據(jù)包數(shù)所產(chǎn)生的平均副本數(shù)。

3.2 性能分析

首先分析數(shù)據(jù)包傳遞率。圖7顯示在λ在0.01 pkts/min和0.25 pkts/min兩種環(huán)境下，數(shù)據(jù)包傳輸率隨節(jié)點(diǎn)數(shù)的變化情況。

圖7 數(shù)據(jù)包傳遞率

從圖7可知，節(jié)點(diǎn)數(shù)的增加提高了數(shù)據(jù)包傳遞率。原因在于：節(jié)點(diǎn)數(shù)越多，組建最優(yōu)路徑的概率越高。此外，對(duì)比于0.01 pkts/min和0.25pkts/min兩種環(huán)境數(shù)據(jù)可知，λ=0.25 pkts/min環(huán)境下的數(shù)據(jù)包傳遞率低于λ=0.01 pkts/min環(huán)境，且下降了近38%。換而言之，λ的增加，降低數(shù)據(jù)包傳遞率。與DBR和VAPR協(xié)議相比，提出的HPSRV協(xié)議的數(shù)據(jù)包傳遞率得到有效地提高。

然后，分析數(shù)據(jù)包傳輸?shù)钠骄鶗r(shí)延，實(shí)驗(yàn)數(shù)據(jù)如圖8所示。從圖8可知，相比于DBR和VAPR協(xié)議, HPSRV協(xié)議降低了傳輸時(shí)延。這要?dú)w功于HPSRV協(xié)議擇優(yōu)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，并利用邊界度量值處理路由空洞。而λ的增加提高了傳輸時(shí)延，這主要因?yàn)棣说脑黾樱黾恿藬?shù)據(jù)包碰撞概率，增加了時(shí)延。

圖8 端到端傳輸時(shí)延

圖9 冗余數(shù)據(jù)包數(shù)

最后，分析冗余數(shù)據(jù)包數(shù)，實(shí)驗(yàn)數(shù)據(jù)如圖9所示。從圖9可知，HPSRV協(xié)議的冗余數(shù)據(jù)包數(shù)趨于穩(wěn)定，在整個(gè)節(jié)點(diǎn)變化區(qū)間表現(xiàn)穩(wěn)定的時(shí)延，且遠(yuǎn)低于DBR和VAPR協(xié)議。原因在于：HPSRV協(xié)議通過(guò)定時(shí)器的設(shè)置抑制了冗余數(shù)據(jù)包數(shù)，并考慮了路由空洞問(wèn)題，提高了數(shù)據(jù)包傳輸?shù)牧鲿承浴?/p>

4 結(jié) 語(yǔ)

本文針對(duì)水下傳感網(wǎng)絡(luò)的數(shù)據(jù)傳輸問(wèn)題，提出基于水壓的抑制路由空洞的UWSNs路由算法HPSRV。HPSRV路由通過(guò)先建立轉(zhuǎn)發(fā)節(jié)點(diǎn)集，然后再利用定時(shí)器計(jì)時(shí)轉(zhuǎn)發(fā)數(shù)據(jù)包，進(jìn)而減少冗余數(shù)據(jù)包。同時(shí)，利用邊界度量值產(chǎn)生邊界轉(zhuǎn)發(fā)節(jié)點(diǎn)，實(shí)現(xiàn)抑制路由空洞的目的。實(shí)驗(yàn)數(shù)據(jù)表明，提出的HPSRV路由有效地提高了數(shù)據(jù)包傳遞率，也降低了傳輸時(shí)延。

此外，由于水域內(nèi)是以聲通信方式傳輸數(shù)據(jù)包，而水表面是以射頻通信方式傳輸數(shù)據(jù)包。而本文主要關(guān)注水域內(nèi)的數(shù)據(jù)包傳輸，也是在水域內(nèi)討論路由問(wèn)題。因此，沒(méi)有考慮水域環(huán)境對(duì)無(wú)線(xiàn)傳輸?shù)挠绊?，這也是后期研究工作方向。