水下無線傳感器網絡節點混合定位與優化算法

侯森林,杜秀娟,李梅菊,黃科軍

(1.青海師范大學 計算機學院,西寧 810008; 2.青海省物聯網重點實驗室,西寧 810008)

0 概述

隨著海上絲綢之路的興起,國家對大海探索和關注日趨增多,水下無線傳感器網絡(Underwater Wireless Sensor Network,UWSN)得到了越來越多的關注。作為無線傳感器網絡(Wireless Sensor Networks,WSN)在水下的延伸,UWSN在海洋農業、海礦產勘探、可燃冰能源開發等方面具有廣泛的應用前景,已經成為該領域研究熱點[1,2]。但水下環境復雜多變,與WSN有著較大差異。陸地WSN采用電磁波通信,而由于海水的吸收作用,電磁波在水下傳輸能量衰減嚴重,且頻率越高,衰減越多[3]。實驗表明:使用IEEE 802.15.4(868 MHz、915 MHz、2.4 GHz)或IEEE 802.11b/g(2.4 GHz)協議的節點發送的電磁波在水下的傳播距離為0.5 m～1.0 m。因此,電磁波無法作為信息傳輸媒介在水下使用,取而代之的是聲波。聲波傳播1 000 m需要670 ms,其傳輸速度遠小于電磁波傳播速度,比電磁波的時延高了5個數量級。同時,水的壓力、溫度和礦物質導致了水環境的高時空變特性,UWSN的時鐘同步和測距技術比陸地上的更為復雜,定位更為困難[4]。傳感器節點受到水流動的影響,位置變化不定,需要周期性地更新節點位置,一般由船舶飛機等隨機部署在水域,其部署密度有疏有密。因此,陸地傳感器成熟的定位方法不能直接應用到UWSN中。在對深海不同深度環境的監測中,網絡節點是部署在三維的海水中。與二維的定位技術相比,水下三維傳感網絡定位面臨巨大挑戰,針對三維環境定位算法的研究至關重要[5]。水的流動以及水下復雜地理和生物環境導致傳感器節點位置變幻不定,數據傳輸的難度較大。同時,水下傳感器節點通常使用蓄電池,更換和充電不方便。因此,在研究UWSN時,還應優先考慮節能和均衡節點的能量消耗。

監測數據消息若無位置信息,則沒有意義,因此需要對隨機布放的傳感器節點的位置信息進行定位。水聲通信具有長時延、高時空變等特性,導致UWSN的時鐘同步存在較大困難。因此,本文提出一種采用無需時間同步且對時延不敏感非對稱往返測距(Round-trip Time of Flight,RTOF)算法獲得節點之間的距離[6],進而采用水下傳感器定位(Underwater Sensor Positioning,USP)算法將之映射到Sink節點的平面[7],由Sink節點使用三邊定位算法計算得出節點的位置集合,隨后用加權迭代最小二乘法對位置集合進行擬合。

1 相關研究

本文對節點定位中常見的專業術語進行定義。

定位覆蓋率:能夠定位的節點數量與節點總數之比。尚沒有一種定位算法能確保所有未知節點都能實現精確的定位,定位覆蓋率受具體算法和信標數的影響,在某種程度上決定了節點的定位效果[8]。

定位精度:表示節點定位的準確程度,與定位誤差有關,誤差越大,精度越小。定位精度是衡量節點定位效果的主要指標。在軍事行動中,如果定位不準確,誤差過大,后果不堪設想。通常用絕對精度和相對精度2種定位精度表現形式[8]。在第4節的仿真實驗中,本文采用絕對值衡量定位精度。

能耗誤差積(EEP):能耗與平均誤差值的積[7],用來評價算法在能耗和定位精度兩方面的綜合性能,計算公式如下:

EEP=E·averageLocationError

(1)

在計算二維節點的坐標時,通常采用三角測量法、三邊測量法、模式識別等方法。根據是否要求距離本文將定位算法分為兩大類:距離相關定位和距離無關定位算法[9]。由于通過距離無關獲得的定位得出的位置信息不準確,因此本文使用與距離有關的定位算法。測距常用算法有到達時間(TOA)算法、到達時間差(TDOA)算法、到達角度(AOA)算法、接收信號強度指示(RSSI)算法、RTOF算法等[10,11]。TOA算法是根據介質的傳播速度,利用介質到達時間來計算距離,計算公式如下:

dr=(T1-T0)V

(2)

其中,T1為信號接收時間,T0為信號發送時間,V為信號傳播速度。TOA算法要求節點之間保持精確的時間同步,這在UWSN中存在較大困難。TDOA算法利用信號到達的時間差來測距,會受到海水對聲波的吸收、多路徑等不確定性因素干擾。AOA算法利用信號到達角度或相對方位測距,需要裝配天線陣列或多個超聲波接收機,這使水聲調制解調器(modem)設計更復雜而增加成本,且水下環境復雜,易受外界干擾。RSSI算法使用水聲信號強度來測量節點間的間距[12],該算法所需能量少、成本低,但水環境里噪聲較多,導致測距誤差較大。RTOF算法利用往返時間差計算節點間的距離,不需要水下節點進行時鐘同步,降低了因時鐘同步帶來的能量消耗,并且往返時間差越大,計算結果越精確。本文采用RTOF算法。

在基于測距的水下定位算法方面,移動預測的大規模水下定位(Scalable Localization with Mobility Prediction,SLMP)[13]算法是在近海條件下、基于水下物體移動模型的預測位置的方案。SLMP 算法包含水面浮標、水下錨節點、未知位置節點的定位。在定位過程中,未知節點首先估計自身運動規律,其次預測自己位置。水下錨節點使用水上節點計算自己的位置,并結合原坐標和移動模型計算自己位置。如果位置之差小于既定閾值,則判定水下錨節點的移動規律有效,否則水下錨節點執行移動預測算法程序更新自身的移動模型。未知節點偵聽到水下錨節點位置廣播后,啟動移動預測程序來更新自身的移動和位置信息。因為水的流動具有相關性,SLMP 算法在定位中僅需對移動模型進行部分更新,所以水下通信次數較少,耗費能量少[14]。但SLMP算法的性能依賴水下節點移動模型是否精準,而且極大似然估計法在計算節點坐標時存在一定誤差,導致定位精度和覆蓋率降低。ARTFL是一種基于USP的定位方案[8],使用基站、信標節點和未知節點3種節點。水下節點在進行定位時,使用類TOA 的方式保證測距精度,提出了不需要時鐘同步的RTOF。在測量距離時,用本地時間與分組的處理時間差,以此計算水下節點和信標節點間的距離。深度信息可通過壓力傳感器獲取,在水下節點位置計算中,ARTFL通過映射投影的方法,將水下的定位問題轉化到二維定位問題,最后使用最小二乘法計算出節點的三維坐標。該方案降低了通信消耗,但沒有考慮節點移動和信標位置的不確定對定位精度的影響,具有較大局限性,未知節點映射水下錨節點坐標帶來較多的能耗,減小了網絡生存周期,降低了定位成功率和覆蓋率。SWN算法采用對稱往返策略,利用水下聲波的廣播特點,每個信標節點發送測距請求給所有的水下未知節點[15],收到請求的水下節點發送若干分組來響應所有的信標節點,信標節點通過圓的交點計算出位置。SWN 定位方案的平均定位誤差較小,但能耗高,網絡壽命較短。因此,基于測距的UWSN定位算法通常在提高定位精度、降低計算成本時,會導致能耗和復雜度增高。

2 RTOF算法與 USP算法

RTOF算法:如果2個節點屬于不同時鐘域或無法進行準確的時鐘同步,可以用計算往返時間、扣除處理延時的策略來計算設備之間的距離。對于節點A、B,若節點A欲測距,則A發起測距請求包PA,并將PA的發送時刻T0記下;B收到PA,并記下接收PA的時刻T1,節點B在T2時刻發送反饋包PB(PB包含T1,T2);A接收到PB的時刻為T3。距離計算公式如下:

(3)

由于T3、T0和T2、T1分別屬于A、B的時鐘域,并由A和B分別測量時間差,因此A、B之間不需要時鐘同步。同時,該方法只需要一次信號交互即可實現,無需時鐘的同步要求。文獻[6]證明在釆用高斯過程信號模擬中,TOA與RTOF算法所帶來誤差的差異不大,且RTOF相對表現更好。

USP算法:利用投影原理,通過壓力傳感器獲取的節點深度,節點將已知節點的坐標投影到自己所在的平面上,從而用二維的解決方案解決三維空間定位問題。這種算法簡化了定位的復雜性,使三維問題可以用二維定位算法解決,人們可以使用在WSN中較為成熟的二維定位算法,從而簡化定位問題。USP算法過程分為2個步驟:預分配和分布式定位。在預分配步驟中,節點載入必要信息,分配唯一標志ID,配置相關參數:USP迭代次數上限M,接收/發送信號耗費時間ΔB,迭代更新坐標耗費時間ΔC以及2次USP定位間的休眠時間ΔS[7,16]。每次的定位周期ΔT,計算公式如下:

ΔT=ΔB+ΔC+ΔS

(4)

第二階段執行分布式的定位算法。節點需要維護鄰居節點和自身節點的相關信息,包括坐標集合和位置信息。Sink節點浮在水面上,通過GPS獲得坐標,發送自身位置信息廣播;未知節點偵聽到Sink廣播信息,在偵聽到足夠的錨節點位置信息后,啟動投影模塊進行錨節點位置映射,獲得錨節點映射到自己平面的坐標后,采用三邊定位迭代計算位置。定位的迭代次數不超過上限M。

圖1顯示了待定位節點X將錨節點A、B和C映射到同一平面上,映射后的節點為A′、B′和C′,映射后的位置用來定位X。

圖1 節點映射

在ΔB時間片內,未知節點發起定位請求,并監聽來自水下錨節點的位置廣播信息。在ΔC時間片內,未知節點根據三邊定位法計算節點位置。在ΔS時間片內,節點處于休眠狀態,等待下一個周期開始。

文獻[17]指出USP算法的缺陷是:未知節點映射錨節點坐標,導致能耗增加,網絡生存周期減小,定位成功率低和需要時間同步,另外測距方法也不確定。文獻[8]提出使用最小二乘法對位置集合進行簡單地擬合,但并未對每個位置元素賦予相應的權重。考慮到實際定位過程中錨節點對未知節點的定位影響不相同,簡單地擬合會導致較大的定位誤差[18]。因此,本文提出一種基于加權迭代最小二乘法的定位擬合算法(MYALGO)。

3 混合定位與優化算法

3.1 加權迭代最小二乘法

簡單最小二乘法的算術表達式如下:

(5)

其中,m代表等式的個數,n代表未知數β的個數,m>n,將式(5)進行矩陣化后得到:

Xβ=Y

(6)

為了求解β,引入殘差平方和函數

S(β)=‖Xβ-Y‖2

(7)

當β=β∧時,S(β) 取最小值,記作:

β2=argmin(S(β))

(8)

通過對S(β)進行微分,求極值可得:

XTXβ∧=XTY

(9)

若式(9)中矩陣XTX非奇異[19],則β有唯一值:

β∧=(XTX)-1XTY

(10)

本文算法根據RTOF算法測得節點間距離。RTOF測距具有傳播時延越長,測距越精確的特點。每個未知節點周圍有多個錨節點,為了使USP定位更加精確,對每個錨節點賦予相應權重,距離越遠的錨節點權重越大。即在對節點位置進行擬合的過程中,對式(7)賦予相應的權重因子,得到:

S(β)=‖Xβ-δY‖2

(11)

其中,X為錨節點的位置,β表示未知節點的位置,Y為錨節點與未知節點間的距離,δ為權重因子。

3.2 網絡結構

Sink節點分布在水面,每個Sink節點配備GPS模塊用以獲取自身位置信息,配備太陽能板供電,配備RF模塊用于Sink節點間通信,配備水聲通信modem用于和水下節點間通信。在水下定位算法中,Sink節點作為首批水下錨節點,其數量至少為3個。

未知節點配備水聲通信modem,通過modem可以和錨節點通信,也可以在節點間相互通信。由于節點整體成本低廉,適合大量部署。

此外,為了減少能耗,根據未知節點到Sink節點的距離將未知節點分為3類:若未知節點可以收到多于等于3個Sink節點的定位廣播信息,稱之為A類未知節點;若未知節點收到定位廣播的個數小于3且多于等于1個,則稱之為B類未知節點,A、B類節點定位由Sink節點集中定位;若未收到任何定位廣播信息,即稱之為C類未知節點,C類節點采取分布式定位,如圖2所示。

圖2 無線通信網絡結構

3.3 改進的定位算法

為了使定位的效果盡可能精確,引入加權迭代最小二乘法對結果集進行優化。同時,為了節約能量和減少通信,優化方案通過對水下節點進行分類區分,使得A、B類節點只用modem發送一次數據即可定位,C類節點在未收到任何定位信息的情況下,就知曉自身所處環境的惡劣,采取推遲發送定位請求時間,并減小發送頻率,盡可能減少了未知節點發送數據次數,降低通信,達到節約能量的目的。文中的改進算法可概述如下:

水下錨節點每隔間隔T時間周期性地發送定位廣播包,廣播包的格式為{Type;NodeId;NodeRank;Seqno; SendTime;Location}。

Type:包的類別,取值為BROADCAST_TYPE、BROADCAST_REP、HELP_REQ、HELP_REP、USP_REP、USP_REQ。

NodeId:節點的唯一標識,布放前預先設置。

NodeRank:節點的級別。Sink節點的NodeRank為0,由Sink節點計算位置未知節點的NodeRank為1,除Sink節點外還需要其他錨節點幫助定位的未知節點的NodeRank為2,進而依次遞推。

Seqno:包序列號,與NodeId一起用于唯一標識包。

SendTime:包發送時間。

Location:節點的位置。Sink節點的位置信息通過GPS獲得。

定義:

α=T/10

(12)

3類節點的定位如下:

1)A類節點的定位:若未知節點在定位周期開始后的3α內收到Sink節點定位廣播的個數多于等于3個,則節點為A類節點,其NodeRank為1。則該節點向Sink節點回復一次響應包,響應包格式為{Type;NodeId; Seqno; SendTime; Argu; Depth; Data}。

Argu:收到定位廣播包的個數。

Depth:未知節點的水深。

Data:一個數組。數組元素有兩個屬性:Sink節點號和該Sink定位廣播報文的接收時間。

接收到響應包Sink節點向周圍Sink節點請求該未知節點響應包到各個Sink節點到達時間。Sink節點采用太陽能供電,不需要考慮能耗,且采用RF通信,時延小。周圍Sink節點收到該請求后,檢查緩存信息并給該Sink節點回復,收到回復的Sink節點采用RTOF計算未知節點到各個Sink節點的距離,進而在采用USP映射后,計算獲得未知節點在該水平面上距離各Sink節點的距離,并使用式(11)進行迭代計算,迭代次數最多不超過M次(M通過信標節點的個數確定)。Sink節點將計算得到的未知節點的位置信息、未知節點到各個Sink節點的距離、時間戳等信息發送給該未知節點,回復包為{Type;NodeId; Seqno; SendTime; Location; Distance}。

Distance:未知節點在水平面上距離各Sink節點的距離。

未知節點獲得位置信息后,若首次被定位,則采用該位置。否則,最終坐標由新舊坐標按照相應權重擬合。進而通過2次比較RTOF算法得到的距離,若距離相差較大,則判定水聲信道變化劇烈,該節點即向同層及下一層的節點發送警告信息,以避免因受環境影響而造成不必要的能量損耗,并在此之后采取暫停通信的策略。

2)B類節點的定位:若未知節點ζ在5α內收到來自Sink的定位廣播個數少于3個且多于1個,則該節點為B類節點。B類節點需要向鄰居錨節點廣播發送一次helpReq報文,helpReq報文格式為{Type;NodeId; Seqno; SendTime; Argu; Depth; Data}。

收到helpReq報文的錨節點根據Argu來生成一個隨機數,通常Argu越大,隨機數值越大。水下錨節點根據隨機數的大小決定是否回復helpRep。在回復的helpRep報文中,包含對應helpReq的接收時間戳和helpRep的發送時間。

當未知節點ζ收到足夠的helpRep后,向直連的Sink節點發送定位所需的相應信息,其中包含接收到的水下錨節點ID、水下錨節點消息的接收時間、與水下錨節點的距離等。之后該Sink節點采用RTOF算法計算未知節點ζ到各水下錨節點的距離,進一步根據USP算法映射,獲得未知節點到各水下錨節點的距離,使用式(11)加權迭代最小二乘法進行迭代運算,并將計算結果等信息發送給該未知節點。

3)C類節點的定位:若未知節點ζ在8α收到的來自Sink節點的定位廣播包數為0,則該節點為C類節點。ζ向鄰居水下錨節點發送USPReq定位請求報文,收到該請求的鄰居錨節點向ζ發送USPRep定位響應報文,報文格式為{Type; NodeId; Seqno; SendTime; Location; NodeRank; Depth}。節點ζ在收到足夠的定位響應報文后,采用RTOF算法計算到各錨節點的距離,選取最遠的3個錨節點的距離,用三邊定位算法進行自定位。

4 仿真與結果分析

本文以NS2作為仿真平臺,對算法的定位覆蓋率、定位精度、EEP進行分析。仿真環境設置如下:在一個范圍可調的3D區域內隨機部署100個傳感器節點,通過控制3D區域的大小來調節節點密度。通過增減Sink節點個數來調節首批水下錨節點個數,水流速度為1 m/s。從定位覆蓋率、定位精度、EEP 3個方面對MYALGO與SLMP、ARTSFL、SWN進行性能對比分析。

如圖3所示,由于SLMP算法沒有考慮節點隨水流移動的情況,在節點密度相當時,SLMP算法的定位覆蓋率比MYALGO算法小。

圖3 不同的節點密度對應的覆蓋率

圖4是在節點平均距離與通信范圍為150 m的實驗數據。結合圖4可以看出在MYALGO的定位誤差比ARTSFL小的情況下,EEP值降低了些。

圖4 不同的信標數對應的EEP值

圖5是在節點間平均間隔與通信范圍為500 m時的實驗數據。由圖5可知,隨著信標節點數增加,位置的迭代計算次數會相應增加,定位精度會隨之提高。并且在信標數為6時,MYALGO算法優于ARTSFL和SWN算法。

圖5 不同的信標數對應的平均定位誤差

圖6顯示了文中算法在Sink節點個數為3、4、5的條件下,平均節點間隔以50 m為刻度逐漸增大時,平均節點間隔與各個定位精度的關系圖。由圖6可知,隨著平均節點間隔的增加和信標節點的數目增多,節點間通信時延和節點獲得信標節點的定位廣播越多,計算位置時迭代次數會上升,平均定位誤差逐漸降低。這表明MYALGO算法在增加節點間隔或信標數目時都可以取得較好的定位效果,驗證了算法在長距離水下定位中的適用性。

圖6 MYALGO不同節點間隔下的平均定位誤差

圖7為在青海湖搭建的水下網絡實驗床平臺。文中已經在NS2上對算法的性能進行了初步的實驗,下一步將著手算法在真實的水下環境中的測試。

圖7 實驗床安裝調試平臺

5 結束語

本文提出一種MYALGO算法,該算法通過Sink節點發起定位廣播,收到3個或3個以上定位廣播的未知節點進行回復,接收到回復的Sink節點通過與其他Sink節點通信獲得該未知節點到各個Sink節點的時間差,進而使用RTOF計算Sink節點到該未知節點的距離。Sink節點通過加權迭代最小乘法對位置集合進行擬合。仿真結果表明,該算法能在較低通信量、計算量以及能量消耗的同時,提高定位覆蓋率和定位精度。依托在青海湖搭建水下網絡實驗床平臺,將對該算法的定位精度、節點能耗以及Sink節點個數的最優關系在真實環境中進行檢測分析,并開展進一步的研究。