一種低開銷與高準確度的水下定位算法

趙德騰

(云南師范大學 信息學院,云南 昆明 650500)

0 引言

目前,地球大約70%被海洋覆蓋,但對海洋的探索卻遠不及陸地。隨著陸地資源的枯竭、全球溫室效應加劇等問題的出現,我國越來越重視對海洋資源的探索和海洋環境的監測。2021年,我國海洋石油的增長量占據了總增長量的8成,體現了我國加快發展海洋探索的步伐。截止到2017年,我國已經建造了多個溫室監測系統,逐步完成了從南海到東海的監測,在此期間獲得了大量的監測數據,為建立全國性監測系統奠定了基礎。

當前,物聯網技術已經發展得非常迅速,它能夠把幾乎所有的物體和設備都聯系起來,使得多種應用能夠得到有效且安全的支持。作為物聯網的關鍵組成部分,無線傳感器網絡(Wireless Sensor Networks,WSNs)已經廣泛應用于多種重要行業。在地面WSNs空前發展的推動下,水下傳感器網絡(Underwater Sensor Networks,UWSNs)在近些年也開始頻繁進入大眾的視野,主要用來執行海洋各區域的監測等。與在地面上不同,水下節點無法通過GPS定位且節點隨海水移動,需要頻繁定位。

國內外對于節點的定位研究大體上可以分為兩種:一種是基于測距的,另一種是不需要測距的。前者需要先測量出未知節點與信標節點之間的距離,然后再進行節點位置的確定。后者不需要測距,利用連通性就可以實現節點位置的獲取。測距技術包括:基于到達時間、基于到達時間差、基于接收信號強度指示的測距技術等。無需測距的定位算法包括[1]:質心算法[2]、APIT算法[3]、距離矢量跳(Distance Vector-Hop,DV-Hop)算法以及這些算法的改進版本等。無需測距的定位算法雖然定位精度一般,但是對硬件要求較低,能耗也較低,因此很適合大規模部署。

DV-Hop定位算法是一種低開銷的定位算法,其定位準確度一般,主要用于地面WSNs的節點定位,針對其存在的不足,當前主要通過細分跳數[4-6]、跳距優化[5-6]以及采用智能優化算法尋找最優解等方法來改進[7-13]。細分跳數是通過改變信標節點的通信半徑,降低跳數誤差,但是會產生額外的能耗。跳距優化一般是對平均跳距進行誤差修正、對未知節點采用平均跳距的方式進行改進,但依然存在提升的空間。隨著智能優化算法的發展,其被大量應用到WSNs領域,尤其是通過與DV-Hop算法相結合,顯著提高了DV-Hop算法的定位性能。為了進一步提高定位性能并應用于UWSNs,本文提出一種改進的DV-Hop定位算法。

1 網絡模型

網絡模型示意如圖1所示,水下節點包括信標節點和普通節點(未知節點)。信標節點利用已知的自身位置信息,幫助未知節點進行定位。

圖1 網絡模型示意

2 DV-Hop算法原理

DV-Hop算法的定位過程類似于基于測距的定位算法,都是在得到未知節點與信標節點之間的距離后,再進行未知節點位置的計算,不同的是,DV-Hop算法是估算距離,代價較小。

DV-Hop算法的實現可以分為3步。

(1)獲取最小跳數。信標節點將包含自身坐標和跳數等信息的數據包廣播到網絡中,初始跳數值為0,數據包每經過一個節點,跳數值加1,最終經過對比,各節點保存到各信標節點的最小跳數。

(2)信標節點計算平均跳距和未知節點估距。

首先,信標節點計算平均跳距。信標節點利用獲得的其他信標節點的坐標和兩者之間的跳數信息進行平均跳距的計算,如公式(1)所示。

(1)

其中,HopSizei為信標節點i所計算出的平均跳距,(xi,yi)和(xj,yj)分別為信標節點i和信標節點j的坐標,hij為信標節點i到信標節點j的跳數。

其次,未知節點估算距離。未知節點收到最近信標節點計算的平均跳距后,與到各信標節點的最小跳數相乘,得到兩者之間的距離,如公式(2)所示。

dki=HopSizei×hki

(2)

其中,dki和hki分別為未知節點k到信標節點i的估算距離和跳數。

(3)未知節點定位。

利用最小二乘法進行未知節點坐標的計算。具體計算如下所示:

(3)

其中,未知節點的坐標(x,y)(x1,y1)(x2,y2)…(xn-1,yn-1)(xn,yn)為信標節點的坐標,d1、d2、···、dn-1、dn為信標節點到未知節點的距離。之后,利用方程組的前n-1個方程分別減去第n個方程得到一個新方程組,新方程組用矩陣AX=B的形式進行表示,見公式(4)。

(4)

利用最小二乘法求出的解見公式(5)。

X=(ATA)-1ATB

(5)

3 改進的DV-Hop定位算法

原始DV-Hop定位算法存在估算的節點間距離誤差較大、采用最小二乘法求解方程組可能導致無解等問題,而且復雜的水下環境會加劇定位的難度。本文通過未知節點加權估距方法和改進的粒子群優化算法提高定位性能。

3.1 未知節點加權估距

未知節點根據信標節點的平均跳距獲得自己的平均跳距,原有方法僅選取離未知節點最近的一個信標節點的平均跳距,但是網絡中的節點分布是不均勻的,需要針對不同情況,合理選擇。因此,本文同時考慮最近信標節點的平均跳距和收到的多個信標節點的平均跳距,并進行加權計算,最終獲得未知節點的平均跳距。

(6)

其中,α1、α2是權重系數,且α1+α2=1。α1、α2的計算公式分別見公式(7)和公式(8),最近信標節點和未知節點之間的跳數越多,全局平均跳距的權重越大。反之,全局平均跳距的權重越小。

(7)

α2=1-α1

(8)

其中,x是未知節點與最近信標節點之間的跳數值,C是常數。l是跳數閾值,未知節點與最近信標節點之間的跳數大于等于該閾值時,未知節點的平均跳距將只采用全局平均跳距。

3.2 改進的粒子群優化定位算法

粒子群優化(Particle Swarm Optimization)算法是一種具有高收斂速度、少參數、易實現等特點的搜索算法。粒子群優化算法的速度和位置更新公式分別見公式(9)和公式(10)。

(9)

xij(t+1)=xij(t)+vij(t+1)

(10)

其中,公式(9)的第二部分為粒子自我認知,第三部分為群體認知。t為迭代次數。c1、c2是學習因子。r1、r2為隨機數。pij為個體已知最優位置,pgj為群體已知最優位置。w為慣性因子,值大則全局搜索能力強。反之,局部搜索能力強。

原粒子群優化算法陷入局部最優的可能性較大,本文提出粒子群分離的方法降低粒子群優化算法陷入局部最優的可能性,從而實現更為準確的定位。

粒子群分離:連續多輪迭代群體最優位置沒有變化,則比較此時群體最優位置L1和群體次優位置L2之間的距離,如果距離超過某一閾值,則進行粒子群分離,即判斷所有粒子與L1和L2兩個位置之間的關系,如果當前粒子距離次優位置L2比距離最優位置L1更近,則將其從原來的粒子群中分離出來,并將分離出的粒子的群體最優位置設置為位置L2,其余粒子保持不變,分離出的粒子個數不超過Nsep。當在同一時間,分離出去的粒子的群體最優位置比主粒子群(沒有分離出去的粒子)的群體最優位置更優時,重新合并粒子群。

4 結語

本文針對DV-Hop定位算法存在的問題,提出了一種改進的DV-Hop定位算法。本文通過加權估距方法降低未知節點與信標節點之間的距離估計誤差,采用改進的粒子群優化算法進行位置的獲取,降低算法陷入局部最優的可能性,從而實現更為準確的定位。