王 鑫，田 藝，蔣 華，覃 琴

(1. 桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541004；2. 桂林電子科技大學 海洋信息工程學院，廣西 北海 536000)

0 引 言

水下無線傳感器網(wǎng)絡(luò)的定位技術(shù)在水下無線傳感器網(wǎng)絡(luò)(UWSN)中扮演著至關(guān)重要的角色[1,2]，只有當傳感器節(jié)點位置已知時，傳感器節(jié)點采集的數(shù)據(jù)才具有意義[3]。網(wǎng)絡(luò)中的節(jié)點被隨機部署在水下，部署的傳感器節(jié)點在水中形成三維體系結(jié)構(gòu)，節(jié)點在水下的隨機部署給水下無線傳感器網(wǎng)絡(luò)定位帶來了很多挑戰(zhàn)[4]。

水下無線傳感器網(wǎng)絡(luò)中節(jié)點隨機部署導致傳感器節(jié)點稀疏和錨節(jié)點分布不均勻[5]。水的流動性會造成UASN結(jié)構(gòu)的非均勻，常魯杰等[6]提出了基于迭代粒子群優(yōu)化的RQ-PSO定位算法，利用MDS-MAP算法[7]進行定位，提出的PQ-PSO算法減少了定位誤差，使得算法更具有魯棒性。針對錨節(jié)點隨機分布導致傳感器網(wǎng)絡(luò)定位率低、定位誤差大的問題，黃炎等[8]提出基于錨節(jié)點連通度的無線傳感器網(wǎng)絡(luò)定位算法，引入平均錨節(jié)點連通度的概念，根據(jù)節(jié)點實時分布來劃分網(wǎng)絡(luò)，實時控制移動錨節(jié)點分布，提高了定位算法的精度。陳友榮等[9]將網(wǎng)絡(luò)劃分成多個六邊形，提出一種輔助信標節(jié)點的路徑規(guī)劃算法，分析對比了SCAN算法、CIRCLES算法等移動路徑靜態(tài)規(guī)劃算法，降低了定位時間和平均定位誤差。汪晗等[10]提出基于幾何精度因子的靜態(tài)錨節(jié)點優(yōu)化布設(shè)方法，但定位精度受到錨節(jié)點幾何面積的大小的約束。黃冰倩等[11]提出寬度優(yōu)先搜索(BFS)算法選取虛擬錨節(jié)點，減少了虛擬錨節(jié)點數(shù)量和錨節(jié)點移動路徑長度。程向紅等[12]提出運用柵格法對已知地圖進行建模，在算法中引入向量指導路徑方向，通過多次獎勵與懲罰措施來進行路徑規(guī)劃。這些算法均在某一方面減少了錨節(jié)點數(shù)量和移動路徑長度，但缺乏對網(wǎng)絡(luò)整體定位率和定位精度的考慮。

針對已有的基于移動錨節(jié)點的定位算法，提出基于錨節(jié)點移動路徑動態(tài)規(guī)劃的水下無線傳感器網(wǎng)絡(luò)定位算法(underwater wireless sensor network localization algorithm based on dynamic planning of anchor node moving path，BMAP)。采用節(jié)點信息列表，通過錨節(jié)點與普通節(jié)點之間的雙向互動，保存采集到的網(wǎng)絡(luò)中節(jié)點的信息。利用路徑動態(tài)規(guī)劃，解決錨節(jié)點的移動路徑規(guī)劃問題。通過RSSI測距算法和三邊定位算法，實現(xiàn)了網(wǎng)絡(luò)中普通節(jié)點的定位，仿真結(jié)果表明，BMAP算法有較好的節(jié)點定位率和較低的平均定位誤差，并降低了定位能耗。

1 水下無線傳感器網(wǎng)絡(luò)模型

由于水下的特殊環(huán)境，水下無線傳感器網(wǎng)絡(luò)具有三維結(jié)構(gòu)，以水平面為XOY平面向下建立一個三維坐標系，如圖1所示。傳感器節(jié)點隨機分布在水中，水下的傳感器節(jié)點受到環(huán)境的限制，它們無法遠程充電，普通傳感器節(jié)點的能源主要因為通信和計算而耗盡。在監(jiān)控區(qū)域中布置適量數(shù)目的錨節(jié)點和普通的傳感器節(jié)點，錨節(jié)點用于輔助定位和網(wǎng)絡(luò)數(shù)據(jù)采集，傳感器節(jié)點用于采集水下相關(guān)數(shù)據(jù)。

圖1 水下無線傳感器網(wǎng)絡(luò)三維模型

如圖2所示將水下無線傳感器網(wǎng)絡(luò)三維空間定位轉(zhuǎn)換成二維平面定位。假設(shè)每個傳感器節(jié)點都可以通過自身攜帶的壓力傳感器獲得自身的深度信息，當未定位的傳感器節(jié)點接收到水下錨節(jié)點廣播的信息后，通過RSSI測距算法計算出自身與錨節(jié)點的距離L，結(jié)合自身的深度數(shù)據(jù)h，將未定位節(jié)點與錨節(jié)點投影在同一二維平面，可計算出該節(jié)點與錨節(jié)點的平面投影距離d。

圖2 三維空間轉(zhuǎn)換二維平面

第i個節(jié)點投影后與錨節(jié)點的距離為

(1)

式中：Li為第i個節(jié)點與錨節(jié)點的實際距離，hi為第i個節(jié)點的深度值。在圖2中，傳感器節(jié)點A和傳感器節(jié)點B通過已知的數(shù)據(jù)L1、L2和h1、h2利用式(1)計算出節(jié)點A的投影與錨節(jié)點投影的距離d1、節(jié)點B與錨節(jié)點投影的距離d2。

2 錨節(jié)點移動路徑動態(tài)規(guī)劃算法

路徑規(guī)劃方法應(yīng)用在眾多領(lǐng)域，可以拓撲化為點、線的問題基本都可以采用路徑規(guī)劃的方法解決?；趯π畔⒌膭討B(tài)或靜態(tài)獲取可以把路徑規(guī)劃分為靜態(tài)規(guī)劃和動態(tài)規(guī)劃。該文采用動態(tài)規(guī)劃方法，實時獲取普通節(jié)點的動態(tài)信息，生成必經(jīng)虛擬錨節(jié)點集合，通過蟻群算法求出最短路徑。

2.1 必經(jīng)虛擬錨節(jié)點的選取

2.1.1 基于廣度優(yōu)先搜索算法選取

根據(jù)虛擬錨節(jié)點到未定位節(jié)點之間的距離L判斷未定位節(jié)點的類型。先行錨節(jié)點隨機選取一個未定位的節(jié)點進行訪問，在移動的過程中廣播信息，并判斷未定位節(jié)點的類型。算法核心流程如下：

步驟1 當L

步驟4 在錨節(jié)點遍歷網(wǎng)絡(luò)的過程中，當未定位節(jié)點接收到3個或者3個以上的廣播信息，若該節(jié)點在集合Vinter中，則通過三邊定位算法定位，并將該節(jié)點加入已定位節(jié)點集合Vd。

步驟5 先行錨節(jié)點遍歷完整個網(wǎng)絡(luò)之后，從集合Vneig中刪除集合Vd中出現(xiàn)的節(jié)點ID。

步驟6 輸出最終的集合Vneig，即為必經(jīng)虛擬錨節(jié)點集合。

2.1.2 BMAP算法選取

通過兩個階段來規(guī)劃移動錨節(jié)點在網(wǎng)絡(luò)中的移動路線。第一階段為錨節(jié)點移動遍歷網(wǎng)絡(luò)發(fā)布信息、采集信息階段。如圖3所示，圓形代表虛擬錨節(jié)點，三角形代表未定位的節(jié)點，未定位節(jié)點隨機分布，將水下無線傳感器網(wǎng)絡(luò)以步長Lr為單位劃分成柵格形狀。

圖3 先行錨節(jié)點移動軌跡

水下無線傳感器網(wǎng)絡(luò)中的每一個節(jié)點都擁有一個信息列表Ginfor，先行錨節(jié)點信息列表包含發(fā)布信息時所在的虛擬錨節(jié)點ID號，標識符S(發(fā)送信息為0，接收信息為1)，深度值，接收到的未定位節(jié)點返回的信息。未定位節(jié)點信息列表包括節(jié)點自身的ID，深度值，接收到的信號強度以及發(fā)送信息的虛擬錨節(jié)點ID，標識符。

水下無線傳感器網(wǎng)絡(luò)中有兩個移動錨節(jié)點，第一個錨節(jié)點負責發(fā)布信息，第二個錨節(jié)點負責采集信息與輔助定位。

步驟1 第一個錨節(jié)點沿著圖3中虛線從下至上，從左至右移動遍歷網(wǎng)絡(luò)，當錨節(jié)點運動到虛擬錨節(jié)點的位置時廣播一次信息。第二個錨節(jié)點在t時刻之后開始沿著同一路線移動。

步驟2 未定位節(jié)點接收到信息后，將接收到的虛擬錨節(jié)點ID號和與其對應(yīng)的信號強度Sinten保存到Ginfor，ID與Sinten屬于一對一關(guān)系。

步驟3 當未定位節(jié)點不能再接收到第一個錨節(jié)點廣播的消息時，Ginfor只保留Sinten最大的3個信號對應(yīng)的ID，將自身的信息列表Ginfor發(fā)送給到達其通信范圍內(nèi)的第二個錨節(jié)點。

步驟4 第二個錨節(jié)點將接收到的信息保存到自身的信息列表Ginfor，將其中的虛擬錨節(jié)點ID保存到必經(jīng)虛擬錨節(jié)點集合Vindis。

如圖4所示，網(wǎng)絡(luò)中每一個虛線柵格的頂點即為虛擬錨節(jié)點的位置，柵格的長度為Lr，錨節(jié)點的通信半徑為R，Q1和Q2為位置未知的節(jié)點。

圖4 必經(jīng)虛擬錨節(jié)點

執(zhí)行步驟1，先行錨節(jié)點M移動到虛擬錨節(jié)點的位置時，信號范圍如圖中的圓圈所示，執(zhí)行步驟2。未知節(jié)點Qi執(zhí)行步驟3，未知節(jié)點Q1接收到先行錨節(jié)點從A、B、C、D這4個虛擬錨節(jié)點廣播的信息，保存信號強度最強的A、B、D這3點的ID，未知節(jié)點Q2接收到從C、E、F、G廣播的信息，保存C、E、F這3點的ID。執(zhí)行步驟4，完成第一階段的必經(jīng)虛擬錨節(jié)點選擇，產(chǎn)生必經(jīng)虛擬錨節(jié)點集合Vindis。

2.2 基于錨節(jié)點移動路徑動態(tài)規(guī)劃的定位算法

錨節(jié)點移動路徑規(guī)劃問題是一個旅行商問題[13](trave-lling salesman problem，TSP)，必經(jīng)虛擬錨節(jié)點集合Vindis等價于旅行家必須經(jīng)過的旅游景點集合，移動錨節(jié)點等價于旅行家，移動錨節(jié)點經(jīng)過每一個必經(jīng)虛擬錨節(jié)點等價于旅行家經(jīng)過每一個旅游景點。設(shè)計移動路線使得移動錨節(jié)點經(jīng)過所有的必經(jīng)虛擬錨節(jié)點，并且移動路徑最短。

目前，學者們提出遺傳算法、蟻群算法、禁忌搜索算法、模擬退火算法等眾多啟發(fā)式優(yōu)化搜索算法解決TSP問題。蟻群算法是模擬螞蟻覓食的方式，通過螞蟻覓食時在路徑上釋放的信息素來選擇下一條路徑。

已得必經(jīng)虛擬錨節(jié)點集合Vindis，將必經(jīng)虛擬錨節(jié)點存放在數(shù)組A和B中，其中aij=bij

A=aij(i=1,2,3,…,j=1,2)

(2)

B=bij(i=1,2,3,…,j=1,2)

(3)

必經(jīng)虛擬錨節(jié)點a到必經(jīng)虛擬錨節(jié)點b的距離

(4)

通過式(4)得到必經(jīng)虛擬錨節(jié)點的加權(quán)矩陣Di,j

(5)

設(shè)定整個蟻群中有m只螞蟻，有n個城市，各個城市之間的距離為Di,j(i,j=1,2,3…n)。

(6)

式(6)中的ηij(t)是啟發(fā)函數(shù)，β是啟發(fā)函數(shù)重要程度因子，α是信息素重要程度因子，allowk是螞蟻K可以選擇的城市集合，τij(t)是城市i和城市j之間的路徑上t時刻的信息素濃度

allowk={0,1,…,n-1-tabk

(7)

當所有螞蟻完成一次循環(huán)后按式(8)更新信息素

(8)

本文定位算法步驟如圖5所示。

圖5 BMAP算法流程

3 實驗仿真

3.1 實驗設(shè)置

實驗仿真選擇在Windows 10 PC機上通過MATLAB工具模擬海洋環(huán)境下的無線傳感器網(wǎng)絡(luò)，實現(xiàn)基于錨節(jié)點移動路徑動態(tài)規(guī)劃的水下無線傳感器網(wǎng)絡(luò)定位方法，對本文的BMAP算法與基于BFS算法的定位算法、SCAN算法和錨節(jié)點隨機的RSSI定位算法從虛擬錨節(jié)點數(shù)量、錨節(jié)點移動路徑長度、定位覆蓋率和平均定位誤差4個方面進行比較。

表1 實驗參數(shù)設(shè)置

水下無線傳感器網(wǎng)絡(luò)中節(jié)點定位率的計算方式如式(9)所示

(9)

其中，Plocation是節(jié)點定位率，Nlocnode是水下無線傳感器網(wǎng)絡(luò)中能夠被定位的節(jié)點總數(shù)，N是水下無線傳感器網(wǎng)絡(luò)中節(jié)點的總數(shù)。

3.2 實驗結(jié)果和分析

在仿真區(qū)域為90 m×90 m的正方形區(qū)域，隨機布置傳感器節(jié)點50個，傳感器節(jié)點隨機分布在監(jiān)控區(qū)域之中，傳感器節(jié)點的分布及錨節(jié)點移動路徑如圖6所示。SCAN算法中錨節(jié)點按照從下至上、從左至右沿著箭頭所示路徑移動。BFS算法根據(jù)廣度優(yōu)先搜索算法選取虛擬錨節(jié)點，錨節(jié)點沿著規(guī)劃的路徑移動。錨節(jié)點隨機算法隨機部署錨節(jié)點。BMAP算法中錨節(jié)點沿著動態(tài)規(guī)劃的路徑移動。

圖6 傳感器節(jié)點分布

圖7為SCAN算法、BFS算法和BMAP算法3個基于錨節(jié)點移動路徑規(guī)劃的定位算法的虛擬錨節(jié)點個數(shù)與網(wǎng)絡(luò)區(qū)域邊長關(guān)系對比圖。通過改變網(wǎng)絡(luò)區(qū)域邊長來改變水下傳感器節(jié)點的稀疏程度，區(qū)域邊長越大，網(wǎng)絡(luò)中節(jié)點越稀疏。在傳感器節(jié)點稀疏的水下無線傳感器網(wǎng)絡(luò)中，BMAP算法選取的虛擬錨節(jié)點數(shù)量少于SCAN算法,略大于BFS算法，BMAP算法減少了虛擬錨節(jié)點數(shù)量，從而降低了節(jié)點之間的通信能耗。

圖7 虛擬錨節(jié)點個數(shù)

圖8為SCAN算法、BFS算法和BMAP算法3個基于錨節(jié)點移動路徑規(guī)劃的定位算法的錨節(jié)點移動路徑長度與網(wǎng)絡(luò)區(qū)域邊長關(guān)系對比。在傳感器節(jié)點稀疏的水下無線傳感器網(wǎng)絡(luò)中，BMAP算法的虛擬錨節(jié)點移動路徑長度遠小于SCAN算法，略大于BFS算法的虛擬錨節(jié)點移動路徑長度。BMAP算法降低了錨節(jié)點移動能耗、減少了網(wǎng)絡(luò)定位時間。

圖8 錨節(jié)點移動路徑長度

圖9為SCAN算法、BFS算法和BMAP算法3個基于錨節(jié)點移動路徑規(guī)劃的定位算法和錨節(jié)點隨機的RSSI定位算法的節(jié)點定位率與網(wǎng)絡(luò)區(qū)域邊長關(guān)系對比圖。在傳感器節(jié)點稀疏的水下無線傳感器網(wǎng)絡(luò)中，BMAP算法的節(jié)點定位率最高，且節(jié)點定位率穩(wěn)定，優(yōu)于其它3種定位算法。BFS算法在網(wǎng)絡(luò)區(qū)域邊長為90 m和120 m時定位率優(yōu)于其它3種算法，但當網(wǎng)絡(luò)區(qū)域邊長增加時，定位率急劇下降到最低。

圖9 節(jié)點定位率

圖10為SCAN算法、BFS算法和BMAP算法3種基于錨節(jié)點移動路徑規(guī)劃的定位算法和錨節(jié)點隨機的RSSI定位算法的平均定位誤差與網(wǎng)絡(luò)區(qū)域邊長關(guān)系對比圖。BMAP算法平均定位誤差略高于SCAN算法，但遠低于BFS算法和錨節(jié)點隨機的RSSI算法。BMAP算法的平均定位誤差隨著網(wǎng)絡(luò)區(qū)域邊長的增加能夠穩(wěn)定在1 m以內(nèi)。BFS算法和錨節(jié)點隨機的RSSI算法的平均定位誤差隨著網(wǎng)絡(luò)區(qū)域邊長的增加在不斷地增大。在網(wǎng)絡(luò)區(qū)域邊長為210 m時，BFS算法和錨節(jié)點隨機的RSSI算法的平均定位誤差是BMAP算法的7倍，BMAP算法具有較高的定位精度。

圖10 定位誤差

在傳感器節(jié)點稀疏的水下無線傳感器網(wǎng)絡(luò)中，BMAP算法選取的虛擬錨節(jié)點個數(shù)和錨節(jié)點移動路徑長度小于SCAN算法，節(jié)點定位率高于BFS算法和錨節(jié)點隨機的RSSI算法，平均定位誤差遠低于BFS算法和錨節(jié)點隨機的RSSI算法。因此，BMAP算法整體具有較好的定位性能。

4 結(jié)束語

針對水下無線傳感器網(wǎng)絡(luò)節(jié)點稀疏、隨機部署錨節(jié)點導致定位誤差大、網(wǎng)絡(luò)定位率低的問題。提出一種基于錨節(jié)點移動路徑動態(tài)規(guī)劃的水下無線傳感器網(wǎng)絡(luò)定位算法。采用動態(tài)路徑規(guī)劃，通過雙移動錨節(jié)點選擇必經(jīng)虛擬錨節(jié)點，利用蟻群算法規(guī)劃錨節(jié)點移動的最短路徑，結(jié)合RSSI測距算法和三邊定位算法完成節(jié)點定位。對BMAP算法、BFS算法、SCAN算法和錨節(jié)點隨機的RSSI算法進行定位性能對比，結(jié)果表明BMAP算法整體具有較低的能耗、較高的定位率和定位精度。