趙德騰

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

0 引言

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

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

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

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

1 網絡模型

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

圖1 網絡模型示意

2 DV-Hop算法原理

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

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

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

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

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

(1)

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

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

dki=HopSizei×hki

(2)

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

(3)未知節(jié)點定位。

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

(3)

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

(4)

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

X=(ATA)-1ATB

(5)

3 改進的DV-Hop定位算法

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

3.1 未知節(jié)點加權估距

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

(6)

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

(7)

α2=1-α1

(8)

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

3.2 改進的粒子群優(yōu)化定位算法

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

(9)

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

(10)

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

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

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

4 結語

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