孔德川,王建平,2,牛立元
(1.河南科技學院,河南新鄉(xiāng) 453003;2.武漢理工大學,湖北武漢 430070)
水下無線傳感器網(wǎng)絡通常由大量的傳感器組成,傳感器隨機分布在水下感測區(qū)域內(nèi),用來偵測環(huán)境的變化或者感應其目標物,并將收集的數(shù)據(jù)做處理,以聲波傳輸?shù)姆绞剑瑐魉偷絽R聚節(jié)點或海上基站。水下無線傳感器網(wǎng)絡是由具有聲學通信與計算能力的傳感器節(jié)點構成的水下監(jiān)測網(wǎng)絡系統(tǒng)[1]。
隨著無線傳感器技術的發(fā)展,當前水下無線傳感器網(wǎng)絡的研究已經(jīng)引起了學術界的高度重視。針對水下無線傳感器網(wǎng)絡的系統(tǒng)結構、水下定位、水聲通信等研究領域已經(jīng)開展了大量基礎研究,并取得了一定的成果,相關小規(guī)模的海洋傳感器網(wǎng)絡已經(jīng)投入試驗運行[2]。水下無線傳感器網(wǎng)絡部署在海洋等水下環(huán)境,在實現(xiàn)水下環(huán)境的污染監(jiān)控、水下生物樣本采集、自然災害預防、輔助導航等方面具備廣闊的應用前景[3]。
相對于在陸地上部署的無線傳感器網(wǎng)絡,水下無線傳感器網(wǎng)絡在技術與應用上難度相對較大,一方面,受到水下環(huán)境的影響,水下無線傳感器網(wǎng)絡通常使用聲波作為傳輸媒介[4],而傳統(tǒng)的陸地無線傳感器網(wǎng)絡采用無線電波通信。另一方面,水下無線傳感器網(wǎng)絡的部署、供電等較陸地無線傳感器網(wǎng)絡難度會更大一些。聲波在水中通信容易受到洋流、溫度、多路徑衰減、噪聲等因素影響,更容易發(fā)生數(shù)據(jù)丟失[5],由于聲波在水中會有傳播延遲的問題,數(shù)據(jù)包從源端傳感器可能必須花較多的時間才能送達匯聚節(jié)點。
當前基于陸地使用的無線傳感器網(wǎng)絡路由算法層出不窮,通??煞譃橹鲃邮铰酚?、反應式路由與地理位置路由3類[6]。但由于聲波與無線電波的特性不同,因此傳統(tǒng)的陸地無線傳感器網(wǎng)絡路由算法并不適合于水下傳感器網(wǎng)絡使用。王錦程等在基于最小代價算法和目的節(jié)點序列距離矢量路由算法的基礎上,提出了一種均衡節(jié)點能耗的路由算法ECBP[7]。該算法按照最小能量代價建立多跳路由表,任何傳感器節(jié)點在向sink節(jié)點發(fā)送數(shù)據(jù)包時,總是沿著最小能量代價的路徑多跳傳遞,從而避免了某些關鍵節(jié)點能量過早耗盡的情況,延長了網(wǎng)絡的生命周期。
YAN Hai等提出了一種基于深度的水下無線傳感器網(wǎng)絡路由算法DBR[8]。該算法采用貪婪轉發(fā)算法,基于多Sink節(jié)點網(wǎng)絡結構,DBR采用洪泛傳播機制,產(chǎn)生了大量的冗余數(shù)據(jù),導致過多的能量消耗,且降低了網(wǎng)絡帶寬利用率,其設計的深度算法存在局部路由空洞。另外,網(wǎng)絡中每個節(jié)點必須配置深度傳感器,增加網(wǎng)絡成本,同時深度傳感器也要消耗一部分能量,會降低網(wǎng)絡壽命。
Hydrocast是Uichin Lee[9]等提出的水下傳感器網(wǎng)絡路由算法。Hydrocast 算法利用局部拓撲信息,采用簡單的貪婪算法選擇最優(yōu)候選節(jié)點集,且不存在隱藏終端問題。但是 Hydrocast算法同樣會出現(xiàn)多個轉發(fā)節(jié)點傳遞同一個數(shù)據(jù)包的現(xiàn)象,造成信息的冗余發(fā)送和節(jié)點能量的浪費。
在進行三維海洋網(wǎng)絡環(huán)境監(jiān)控時,通常需要將傳感器部署到不同深度的海下空間中。為此,必須要通過無窮多個節(jié)點的協(xié)同工作來實現(xiàn)信息的傳輸。在這種信息傳輸過程中,設計一種路由算法極其關鍵。一方面要保證所有傳感器節(jié)點所感測到的環(huán)境信息能基于路由算法忠誠地傳到sink節(jié)點[10],另一方面,如何實現(xiàn)數(shù)據(jù)的聚合,保證數(shù)據(jù)傳輸?shù)娜哂喽茸钚。瑫r能實現(xiàn)整個傳感器網(wǎng)絡的節(jié)能等都是當前研究的熱點。
2.1系統(tǒng)模型
文中提出基于深度部署水下無線傳感器網(wǎng)絡的路由算法。在整個過程中,將海平面劃分n個區(qū)塊,即對二維坐標做定義。如圖1所示,假設劃分9個區(qū)域并作編號,每個區(qū)域內(nèi)都有傳感器分布,假設每個傳感器在部署中均能將自己當前所處區(qū)域坐標和所處水下的深度信息基于設計的路由算法回傳給sink節(jié)點,基于此來構建傳感器的三維空間坐標系。水下傳感器之間采用超聲波實現(xiàn)通信,采用設計的路由算法來實現(xiàn)整個部署水下無線傳感器的區(qū)域全覆蓋過程。
圖1 三維空間部署模型
假設每個傳感器都能偵測目前所在的深度與數(shù)據(jù),深度為傳感器垂直到海平面的距離。每個傳感器都有自己的ID與坐標編號,sink節(jié)點也有自己的坐標編號,傳感器之間通過超聲波實現(xiàn)通信,sink節(jié)點采用一條可通信的錨鏈和水下的某個傳感器節(jié)點基于有線進行通信。假設每個傳感器都有相同的最大信號傳輸半徑,如果數(shù)據(jù)傳送距離超過最大傳送半徑則無法送達。每個傳感器以自己當前位置為中心,采用最大傳送半徑構建的球型區(qū)域來選擇在該空間中的鄰居傳感器節(jié)點。以此來獲知鄰居節(jié)點的數(shù)目、距離、傳感器ID與坐標編號,并能互相交換信息,傳感器也能從鄰居中辨識海面上的sink節(jié)點。傳感器隨機分布在固定海面下,傳感器分布完后,就不再移動。傳感器節(jié)點將感測數(shù)據(jù)通過路由算法傳送給鄰居節(jié)點,整個數(shù)據(jù)基于路由算法基于多跳的方式傳遞到sink節(jié)點。
2.2n層二叉樹的基本概念
n層二叉樹以樹的概念構建路由鏈路,在進行路由過程中,下層的傳感器只從鄰居節(jié)點中找兩個比自己深度小的傳感器節(jié)點。下層的傳感器是n層二叉樹的第一層,兩個比自己深度小的鄰居傳感器是n層二叉樹的第二層,以此類推就可以找到第三層。當傳感器到某層后不在查找葉子節(jié)點時,n層二叉樹的N就用那層命名。
如圖2所示的3層二叉樹中,第3層是最后的葉子節(jié)點,該層有4個傳感器,所以就有4條路徑來查找sink節(jié)點。為了防止路徑過長而造成太多傳送次數(shù),所以在每條路徑會分別限制多跳次數(shù),例如圖2中的路徑1限制的最大多跳次數(shù)為6,也就是數(shù)據(jù)包在路徑1只能傳送6次,如果6次后仍然傳輸不成功,則必須停止傳送,以此來保證傳輸無限循環(huán)的問題。
圖2 3層二叉樹示意圖
每個傳感器節(jié)點除了自己的深度與數(shù)據(jù)的信息外,啟用一個鄰居信息表來決定數(shù)據(jù)包發(fā)送的對象,由鄰居的信號強弱可以知道彼此間的距離,一開始傳感器與鄰居溝通,將鄰居的傳感器ID、坐標編號、深度與距離放入鄰居信息表中。每個傳感器產(chǎn)生的數(shù)據(jù)包都會編號,數(shù)據(jù)包序號是唯一的,sink節(jié)點可以知道數(shù)據(jù)包是從哪個傳感器發(fā)出的,假設水下有100個傳感器可以傳送數(shù)據(jù)到匯聚節(jié)點,某個傳感器會產(chǎn)生數(shù)據(jù)包序號為IDi={1+100×i,i=0,1,2,3,…,n}。因此數(shù)據(jù)包的ID是{1,101,201,301,…}這樣的序列。為了防止相同數(shù)據(jù)包在同一個傳感器傳送兩次以上,因此傳感器有一個歷史數(shù)據(jù)包隊列,當某個數(shù)據(jù)包第一次到達某個傳感器,歷史數(shù)據(jù)包隊列會記錄數(shù)據(jù)包序號,歷史數(shù)據(jù)包隊列可以確保相同數(shù)據(jù)包不會在相同傳感器傳送第二次,這樣可以防止數(shù)據(jù)包再次走相同或類似路徑。
2.3n層二叉樹的構建
提出n層二叉樹的主要目的是希望數(shù)據(jù)包能往海面移動且數(shù)據(jù)包也能向左右擴散,使得數(shù)據(jù)包到達sink節(jié)點的機率增加。因此選擇找兩個鄰居來傳送,如果只有一個鄰居,只能選擇唯一傳感器來傳送,沒有鄰居的情況下,數(shù)據(jù)包將會終止傳送。
n層二叉樹有兩種鄰居選擇策略:一種鄰居選擇策略希望選擇的鄰居越接近海面越好,所以會找深度最小的傳感器來當中繼傳感器;另一種選擇策略希望數(shù)據(jù)包能擴散,所以會找比自己深度小、最接近水平軸且能離自己較遠的節(jié)點。
文中采用第二種策略來構建n層二叉樹。前面提到,在部署水下傳感器網(wǎng)絡時,文中基于三維空間坐標來對水下的傳感器進行定位,即每個傳感器均通過一個坐標系來定位。采用最接近水平軸的策略,可以避免數(shù)據(jù)包都在相同坐標區(qū)域傳送,接近水平的鄰居是距離當前節(jié)點最遠的鄰居,這樣有更高的機率讓數(shù)據(jù)包傳輸?shù)狡渌麉^(qū)域。雖然所有傳感器知道匯聚節(jié)點的坐標編號,但傳感器仍然無法得知二維平面前后左右的關系,只能知道與鄰居高度的關系,因此數(shù)據(jù)包能跨其他坐標區(qū)域?qū)⒏菀讉鬏數(shù)絽R聚節(jié)點。為此采用計算兩個傳感器之間的深度差的方法可以很方便地實現(xiàn)該選擇策略。
為完成三維環(huán)境下相鄰兩個傳感器之間的傳輸距離的計算。采用極坐標來簡化計算過程。極坐標是二維坐標系統(tǒng),用兩點間的夾角和距離來表示,極坐標可被擴展到三維空間中,形成球形坐標。如圖3所示,原點O和S表示兩個傳感器,設原點的坐標為〈0,0,0〉,S的坐標為〈a,b,c〉。球坐標可以采用坐標〈d,φ,θ〉擴展為三維空間,其中d是到S原點O的距離,φ表示d與z軸的角度(0≤φ≤180),θ是d的投影與x軸的角度(0≤θ≤90),假設φ的余角為δ,則δ=90°-φ,δ也就是距離水平面的角度,球坐標可用下式表示:
a=dsinφcosθ
(1)
b=dsinφcosθ
(2)
c=dcosθ
(3)
圖3 三維球坐標
圖3中S坐標的c,d是兩個傳感器的水平距離和傳播距離,由上面的公式可以計算出φ的角度,dsinφ可表示投影距離,鄰居傳感器的dsinφ越大也就有更高的優(yōu)先權被選擇當中繼節(jié)點。在建立n層二叉樹選擇鄰居時,n層二叉樹會考慮φ的角度,φ選擇的范圍是0≤φ≤90°,φ越接近90°的鄰居為優(yōu)先選擇,當有多個鄰居傳感器有相同的φ,會比較鄰居傳感器的dsinφ,dsinφ大的鄰居傳感器有較高的優(yōu)先權被選擇來當中繼節(jié)點。
2.4最大跳數(shù)的定義
當n層二叉樹建立完成后,最高層的傳感器分別有自己的路徑要走,由于基站是在海面上,所以越深的傳感器必須走更長的路徑,最大的跳數(shù)就必須較大,越淺的傳感器就走較短的路徑,最大的跳數(shù)就相對較小,因此采用傳感器的深度當作標準,用Nmax-hop表示最大的跳數(shù),Ldeep(i)表示第i層傳感器的深度,r表示傳感器的信號傳送距離,K表示倍率參數(shù),其值可根據(jù)實際情況取正整數(shù),本文設定的K值為2,最大跳數(shù)的定義如式(4)所示:
(4)
如圖4所示,3層二叉樹最頂層有4個傳感器A、B、C、D深度分別為H1=600 m、H2=900 m、H3=400 m、H4=100 m,假設傳感器的最大傳輸距離為300 m,k=2,因此按照式(4)計算的最大跳數(shù)為6。
圖4 最大跳數(shù)
為保證算法不出現(xiàn)路由環(huán)路,定義一個最大傳輸次數(shù),如式(5)所示:
(5)
式中:m表示即將傳送的傳感器數(shù)量;n表示n層二叉樹的層數(shù);K為倍率參數(shù);j表示n層二叉樹最頂層傳感器;Ldeep(j)表示由最頂層傳感器j所在的深度;r表示最大傳送距離。
面對上述的城市公共空間不足和公共性衰退的問題,盡管目前很多城市在發(fā)展建設中設法保留或新增一些公園、綠道等綠色公共空間,但是因為資本對城市空間生產(chǎn)的偏向性,這些為城市大眾服務的、少有經(jīng)濟回報的空間在城市空間里往往比例不足[8]。綠色公共空間在城市里的缺失,分布不均,不成系統(tǒng),以及城市周邊的自然環(huán)境被日益吞并、侵占、污染等狀況造成了一些典型的城市問題,包括環(huán)境問題和市民心理問題。
2.5鄰居節(jié)點的選擇
當n層二叉樹建立完成后會產(chǎn)生2n-1條路徑,為了避免數(shù)據(jù)包可能只在小區(qū)域傳送,所以可以在數(shù)據(jù)包上升的過程選擇是否有更好路徑,每個傳感器都知道匯聚節(jié)點的坐標編號,所以數(shù)據(jù)包只要送到傳感器的坐標編號與匯聚節(jié)點的坐標編號相同,再往深度低的方向送,就可以送達匯聚節(jié)點,如果數(shù)據(jù)包走到傳感器的坐標編號與匯聚節(jié)點的坐標編號不同時,利用建立n層二叉樹的擴散方法,傳感器依照dsinφ來選擇鄰居來傳送。
最后,數(shù)據(jù)包到海面附近的傳感器時,無法再往上傳送數(shù)據(jù)包,也就是無法找到比自己更高的鄰居,所以傳感器依照dsinφ來決定傳送對象,φ為90°左右的鄰居為優(yōu)先選擇,當有多個鄰居傳感器有相同的φ,會比較鄰居傳感器的dsinφ,dsinφ越大的鄰居是優(yōu)先考慮來傳送,因此數(shù)據(jù)包可以在接近海平面的傳感器傳送而不會再往深的方向傳送。建立完成n層二叉樹后鄰居的選擇優(yōu)先權如下:
(1)傳感器本身的坐標位置與匯聚節(jié)點坐標位置相同,數(shù)據(jù)包往深度小的方向傳送;
(2)鄰居傳感器的坐標位置與匯聚節(jié)點坐標位置相同;
(3)依照dsinφ來決定傳送對象。
3.1仿真條件設置
基于MATLAB實現(xiàn)了所設計路由算法的仿真過程。在實驗中,傳感器節(jié)點隨機分布在固定大小的三維地圖,傳感器節(jié)點分布完后,就不再移動,匯聚節(jié)點固定在三維地圖最上方,對地圖的二維平面(X、Y平面)劃分9個區(qū)塊,每個區(qū)塊都有坐標編號,因此每個節(jié)點都有自己的坐標編號。每個節(jié)點都有固定的最大傳送范圍,即在傳送范圍以內(nèi)的傳感器節(jié)點才能接收數(shù)據(jù)。
表1 仿真實驗參數(shù)
3.2不同層數(shù)、不同傳輸半徑下分組投遞率的對比
為討論n層二叉樹算法的層數(shù)和傳感器傳輸半徑的影響,探討了在2層、3層、4層二叉樹環(huán)境下,傳輸半徑為100 m、150 m時的分組投遞比對率。圖5是傳輸半徑為100 m時,2層、3層、4層二叉樹的仿真結果??梢钥吹蕉鏄涞膶訑?shù)越高,其數(shù)據(jù)包傳遞率相對就會越大,隨著水下網(wǎng)絡中傳感器數(shù)量的增加,數(shù)據(jù)包傳遞率也在逐步增加。
圖5 傳輸半徑為100 m時的數(shù)據(jù)包傳遞率對比
圖6列出的是當傳感器的數(shù)據(jù)傳輸半徑為150 m,傳感器數(shù)量從200個遞增到700個時,2層、3層、4層二叉樹的數(shù)據(jù)包傳遞率情況,同樣可以看到,層數(shù)越高,數(shù)據(jù)包傳遞率越大,隨著傳感器數(shù)量的增加,數(shù)據(jù)包傳遞不斷增加,對比圖5可以看到,當傳輸半徑增加時,在對應相同的傳感器數(shù)量下,數(shù)據(jù)報傳遞率明顯提高。
圖6 傳輸半徑為150 m時的數(shù)據(jù)包傳遞率對比
3.3與其他算法的數(shù)據(jù)包傳遞率、能耗對比
從圖5和圖6的實驗結果對比看來,當節(jié)點數(shù)接近700個,3層二叉樹算法和4層二叉樹算法在數(shù)據(jù)傳輸半徑為100 m和150 m時,其數(shù)據(jù)包傳遞率基本上都接近0.995??紤]到節(jié)能,在對比DBR、ECBP和Hydrocast等3種路由算法時,設定采用3層二叉樹路由算法進行對比,采用的傳感器數(shù)量為200~700個,實際水下三維環(huán)境同樣為900 m×900 m×900 m環(huán)境,傳輸半徑為100 m,倍率參數(shù)為2。整個實驗執(zhí)行50次,每次執(zhí)行360 s,每60 s執(zhí)行1次采樣。實驗中,主要對比了DBR、ECBP和Hydrocast 3種算法的數(shù)據(jù)包傳遞率、整個網(wǎng)絡的能耗情況。
圖7是4種算法的數(shù)據(jù)包傳遞率對比,可以看到Hydrocast算法的數(shù)據(jù)包傳遞率最高,由于Hydrocast算法利用局部拓撲信息,采用簡單的貪婪算法選擇最優(yōu)候選節(jié)點集,不存在隱藏終端問題,為此其數(shù)據(jù)包傳遞率最高。3層二叉樹算法基于當前傳感器深度,采用多跳傳播且限制轉發(fā)次數(shù),能較大程度上實現(xiàn)網(wǎng)絡中數(shù)據(jù)傳播的負載均衡。DBR存在局部路由空洞,為此,其數(shù)據(jù)包傳遞率也較低。ECBP算法總是沿著最小能量代價的路徑多跳傳遞,整個路由拓撲穩(wěn)定性差,導致數(shù)據(jù)包傳遞率最低。隨著傳感器數(shù)量的增加,4種算法的數(shù)據(jù)包傳遞率均呈現(xiàn)增加的趨勢。
圖7 與DBR、ECBP和Hydrocast算法數(shù)據(jù)包傳遞率對比
圖8是4種算法的能耗對比情況,能耗關系到水下傳感器網(wǎng)絡的生命周期,路由算法的能耗越小,則構建的拓撲穩(wěn)定性越好。路由算法的能耗主要發(fā)生在數(shù)據(jù)傳輸過程中,為此在仿真過程中采用整個參與通信節(jié)點的平均剩余電量的期望值來進行計算。在4種算法中,DBR算法采用多Sink節(jié)點結構,采用貪婪轉發(fā)算法,基于洪泛機制傳播,其存在局部路由空洞現(xiàn)象,所以,該算法的能耗最高。Hydrocast 算法同樣基于貪婪轉發(fā)算法,但其采用局部更低深度節(jié)點優(yōu)先恢復機制抑制節(jié)點的洪泛,為此,其能耗低于DBR算法。3層二叉樹算法采用多路徑(multi-path)來傳送感測數(shù)據(jù),通過傳輸次數(shù)限制了路由環(huán)路,為此,其能耗也相對較低。ECBP基于最小代價算法和DSDV算法,數(shù)據(jù)總是沿著最小能量代價的路徑多跳傳遞,從而避免了某些關鍵節(jié)點能量過早耗盡的情況,所以該算法的能耗最小。
圖8 與DBR、ECBP和Hydrocast算法能耗對比
文中提出了基于n層二叉樹的水下無線傳感器網(wǎng)絡路由算法,在整個過程中,將海平面劃分n個區(qū)塊,通過三維空間坐標來對水下傳感器節(jié)點進行定位。采用最接近水平軸的策略來選擇最遠鄰居,利用傳感器彼此間的深度差來決定路由方向,使用簡單的區(qū)塊定位,通過多跳方式,基于多路徑傳送,將感測數(shù)據(jù)送達海面sink節(jié)點。通過限制傳送次數(shù),防止了路由環(huán)路,同時提高了數(shù)據(jù)包傳遞率。
通過MATLAB實現(xiàn)了該路由算法的性能仿真分析,分別探討了2層、3層、4層二叉樹環(huán)境下,傳輸半徑為100 m、150 m和300 m時的分組投遞比對率。實驗結果顯示,n層二叉樹的層數(shù)越高,傳輸半徑越大,其數(shù)據(jù)包傳遞率相對越大,隨著水下網(wǎng)絡中傳感器數(shù)量的增加,數(shù)據(jù)包傳遞率逐步增加。通過傳輸半徑為100 m的3層二叉樹對比了DBR、ECBP和Hydrocast 3種常見水下傳感器網(wǎng)絡路由算法的數(shù)據(jù)包傳遞率和能耗情況。實驗結果顯示,3層二叉樹算法的數(shù)據(jù)包傳遞率趨于和Hydrocast路由算法一致,接近0.948,而能耗卻明顯低于BDR和Hydrocast路由算法。如果采用3層以上,傳輸半徑更高的二叉樹算法,必將能提高數(shù)據(jù)包傳輸率,但是,隨著層數(shù)和傳輸半徑的增加,卻會導致傳感器網(wǎng)絡能耗的增加,在實際水下無線傳感器網(wǎng)絡使用中,選擇合適的層數(shù)和傳輸半徑,實現(xiàn)傳感器網(wǎng)絡能耗和書包傳遞率的平衡是未來研究的重要課題。
參考文獻:
[1]夏娜,鄭語晨,杜華爭,等.剛性驅(qū)動水下傳感器節(jié)點自組織布置.計算機學報,2013,36(3):494-505.
[2]郭忠文,羅漢江.水下無線傳感器網(wǎng)絡的研究進展.計算機研究與發(fā)展,2010,47(3)377-389.
[3]AKYITDIZ F,POMPITI D,MELODIA T.Underwater acoustic sensor networks.Research Challenges.2005,3(3):257-279.
[4]單志龍,胡燕.基于相交環(huán)的水下無線傳感器網(wǎng)絡節(jié)點自定位研究.傳感技術學報,2012(4):536-540.
[5]陳榮,單志龍.大規(guī)模水下無線傳感器網(wǎng)絡定位誤差抑制研究.計算機與現(xiàn)代化,2011(5):87-91.
[6]陳衡,錢德沛,伍衛(wèi)國.無線傳感器網(wǎng)絡地理位置路由度量方法.西安交通大學學報,2009(12):55-59.
[7]王錦程.一種基于水聲信道的無線傳感器網(wǎng)絡路由算法.傳感技術學報,2009,22(1):108-111.
[8]YAN H,SHI ZHIJIE,CUI J H.DBR:depth based routing for underwater sensor networks.Proceedings of networking,2008:16-1221.
[9]LEE U,WANG P,NOH Y,et al.Pressure routing for underwater sensor networks.Proceedings of IEEE INFOCOM 2010:1-9.
[10]李琳,雷康,李小三.網(wǎng)絡多向多sink節(jié)點WSN路由算法.西北大學學報(自然科學版),2013(2):214-218.