面向非完全序列的水下三維傳感網(wǎng)定位算法

車(chē) 迪，牛 強(qiáng)

(中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)(*通信作者電子郵箱chedi@cumt.edu.cn)

0 引言

隨著無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)[1]應(yīng)用的日益廣泛，近年來(lái)，對(duì)于無(wú)線傳感器網(wǎng)絡(luò)在水下應(yīng)用的研究成為了熱點(diǎn)。水下傳感器網(wǎng)絡(luò)[2]是一種包括聲、磁場(chǎng)、靜電場(chǎng)等的物理網(wǎng)絡(luò)，其在污染預(yù)測(cè)、海洋監(jiān)測(cè)、遠(yuǎn)洋開(kāi)采以及海洋數(shù)據(jù)采集等方面取得了廣泛的應(yīng)用，更將在未來(lái)的海軍作戰(zhàn)中發(fā)揮重要的作用與優(yōu)勢(shì)。在基于無(wú)線傳感器網(wǎng)絡(luò)的監(jiān)測(cè)應(yīng)用中缺乏位置信息的數(shù)據(jù)往往沒(méi)有意義，因此獲取傳感器節(jié)點(diǎn)的位置信息至關(guān)重要，對(duì)于水下傳感器網(wǎng)絡(luò)也是一樣的，得到傳感器節(jié)點(diǎn)的位置信息是其研究工作的重中之重。作為水下傳感器網(wǎng)絡(luò)的關(guān)鍵基礎(chǔ)支撐技術(shù)之一，節(jié)點(diǎn)定位技術(shù)的研究具有極其重要的理論與實(shí)際意義[3]。

現(xiàn)有的無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位方法大多以二維空間為背景，但由于水下傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位為三維空間模型，因此，本文以水下三維傳感網(wǎng)的目標(biāo)定位為著眼點(diǎn)。另外，絕大多數(shù)基于序列的定位算法皆以信標(biāo)節(jié)點(diǎn)通信范圍全網(wǎng)覆蓋為研究前提，則未知節(jié)點(diǎn)可接收全網(wǎng)信標(biāo)節(jié)點(diǎn)的通信信息，因此該種算法皆利用全序列(序列長(zhǎng)度為信標(biāo)節(jié)點(diǎn)數(shù))進(jìn)行節(jié)點(diǎn)定位，但水下傳感網(wǎng)中，存在環(huán)境惡劣、信號(hào)傳播困難以及定位空間較廣等因素，所以信標(biāo)節(jié)點(diǎn)通信范圍無(wú)法達(dá)到全網(wǎng)覆蓋，導(dǎo)致未知節(jié)點(diǎn)接收信標(biāo)節(jié)點(diǎn)通信信息部分缺失。為解決上述問(wèn)題，本文提出一種基于非完全序列(序列長(zhǎng)度小于信標(biāo)節(jié)點(diǎn)數(shù))的水下三維傳感網(wǎng)定位算法。該算法利用Voronoi圖的三維空間劃分方法和階次序列定位的思想，通過(guò)虛擬信標(biāo)節(jié)點(diǎn)、非完全序列的引入以及最鄰近序列表的加權(quán)平均估算，在保證定位精度較高的前提下有效降低了算法的計(jì)算復(fù)雜度，且未帶來(lái)額外的節(jié)點(diǎn)能量消耗以及網(wǎng)絡(luò)成本。

1 相關(guān)工作

與其他環(huán)境下的傳感器網(wǎng)絡(luò)相同，根據(jù)定位過(guò)程中是否實(shí)際測(cè)量節(jié)點(diǎn)的物理距離或方位角度，水下傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法主要分為兩大類：

1)基于測(cè)距的定位算法。基于測(cè)距的定位機(jī)制通過(guò)測(cè)量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位角度來(lái)估算未知節(jié)點(diǎn)的位置。一般情況下，未知節(jié)點(diǎn)需與信標(biāo)節(jié)點(diǎn)進(jìn)行直接通信，并利用其接收到的信號(hào)強(qiáng)度、到達(dá)角度或到達(dá)時(shí)間差進(jìn)行測(cè)距，然后再根據(jù)其與信標(biāo)節(jié)點(diǎn)的幾何關(guān)系來(lái)測(cè)算未知節(jié)點(diǎn)的坐標(biāo)。在基于測(cè)距的定位算法中，最典型的幾種測(cè)距方法為：基于接收的信號(hào)強(qiáng)度指示(Received Signal Strength Indication， RSSI)[4]、到達(dá)角度(Angle Of Arrival， AOA)[5]、到達(dá)時(shí)間(Time Of Arrival， TOA)[6]和到達(dá)時(shí)間差(Time Difference Of Arrival， TDOA)[7]等。

2)距離無(wú)關(guān)的定位算法。距離無(wú)關(guān)的定位算法不需要節(jié)點(diǎn)間的絕對(duì)測(cè)距或是角度信息，僅利用節(jié)點(diǎn)之間的相鄰關(guān)系，依據(jù)網(wǎng)絡(luò)的連通度以及信標(biāo)節(jié)點(diǎn)信息進(jìn)行未知節(jié)點(diǎn)的位置測(cè)算。目前已提出的距離無(wú)關(guān)定位算法有：質(zhì)心算法[8]、近似三角形內(nèi)點(diǎn)測(cè)試法(Approximate Point-In-triangulation Test， APIT)[9]和DV-Hop算法[10]等。

基于序列的定位算法是近幾年提出的一種綜合基于測(cè)距和距離無(wú)關(guān)的定位算法，其核心思想是將一個(gè)二維定位平面用已排好的信標(biāo)節(jié)點(diǎn)通過(guò)某種方式進(jìn)行空間劃分，構(gòu)建虛擬信標(biāo)節(jié)點(diǎn)，并根據(jù)其與信標(biāo)節(jié)點(diǎn)的距離次序來(lái)確定虛擬信標(biāo)節(jié)點(diǎn)的階次序列，即定位序列。文獻(xiàn)[11]首次提出了WSN中基于序列的節(jié)點(diǎn)定位方法，利用每?jī)蓚€(gè)參考點(diǎn)之間的垂直平分線將具有n個(gè)參考點(diǎn)的二維空間劃分為O(nn)個(gè)區(qū)域，并分別用序列獨(dú)一無(wú)二地表示各個(gè)區(qū)域(由于幾何約束，得到的序列實(shí)際數(shù)為O(n4))，該算法對(duì)由于無(wú)線信道的多徑干擾和遮蔽效應(yīng)產(chǎn)生的隨機(jī)誤差具有魯棒性。文獻(xiàn)[12]提出了一種三點(diǎn)垂心法和序列定位相結(jié)合的無(wú)線傳感網(wǎng)中節(jié)點(diǎn)定位的改進(jìn)算法，即通過(guò)得到序列相關(guān)系數(shù)的前三位最大值，求出與未知節(jié)點(diǎn)距離“最近”的三個(gè)區(qū)域的重心所構(gòu)成的三角形的垂心，且過(guò)濾掉未知節(jié)點(diǎn)不可能處在的區(qū)域，降低了節(jié)點(diǎn)平均定位誤差，該算法增加了估算未知節(jié)點(diǎn)精確位置的計(jì)算量，但無(wú)需增加算法的計(jì)算復(fù)雜度與傳感器節(jié)點(diǎn)的硬件設(shè)備，與傳統(tǒng)的三點(diǎn)垂心法與序列定位算法相比，該算法對(duì)于節(jié)點(diǎn)的定位精度有明顯的提高。文獻(xiàn)[13]提出了一種基于N-最優(yōu)階次序列的無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位方法，通過(guò)無(wú)線信號(hào)的衰減模型來(lái)產(chǎn)生虛擬測(cè)試點(diǎn)，再以參考點(diǎn)為樣本，利用隨機(jī)采樣的方法確定最優(yōu)N值，最后選擇階次為前N位的序列代表的區(qū)域，對(duì)未知節(jié)點(diǎn)的位置進(jìn)行加權(quán)估算，該方法有效減少了節(jié)點(diǎn)的定位誤差，并且能在一定程度上提高邊界節(jié)點(diǎn)的定位精度。文獻(xiàn)[14]提出了一種基于參考點(diǎn)序列的無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位算法，該算法將Voronoi圖的頂點(diǎn)作為參考點(diǎn)，從而使信標(biāo)節(jié)點(diǎn)的數(shù)目增加，然后利用基于參考點(diǎn)與信標(biāo)節(jié)點(diǎn)到傳感器節(jié)點(diǎn)建立的序列等級(jí)對(duì)傳感器節(jié)點(diǎn)的位置進(jìn)行估算，該算法比質(zhì)心算法和DV-Hop算法具有更高的定位精度。其中，文獻(xiàn)[12-13]在文獻(xiàn)[11]的基礎(chǔ)上對(duì)定位算法進(jìn)行了改進(jìn)，但也令其算法的復(fù)雜度有所增加，文獻(xiàn)[14]雖首次將Voronoi圖引入到基于信標(biāo)節(jié)點(diǎn)的定位空間區(qū)域劃分中，但并未考慮未知節(jié)點(diǎn)所處區(qū)域信標(biāo)節(jié)點(diǎn)對(duì)定位估算的影響。

文獻(xiàn)[15]提出了SLC3V(Sequence Localization Correction algorithm based on 3D Voronoi diagram)，一種基于Voronoi圖原理與階次序列的三維無(wú)線傳感器網(wǎng)絡(luò)定位算法，該算法利用Voronoi圖對(duì)三維定位空間進(jìn)行區(qū)域劃分，構(gòu)建虛擬信標(biāo)節(jié)點(diǎn)的階次序列表，并通過(guò)RSSI方法得到未知節(jié)點(diǎn)的定位序列，然后選擇N個(gè)最優(yōu)參數(shù)并對(duì)其進(jìn)行等級(jí)相關(guān)系數(shù)的歸一化處理，最后實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)位置的加權(quán)估計(jì)，但該算法以假設(shè)信標(biāo)節(jié)點(diǎn)的通信半徑能覆蓋整個(gè)無(wú)線傳感網(wǎng)為研究背景，這就限制了該算法只能應(yīng)用于定位空間較小的網(wǎng)絡(luò)環(huán)境，而不適用于覆蓋范圍較大的網(wǎng)絡(luò)以及通信環(huán)境惡劣的水下傳感網(wǎng)。

本文關(guān)注水下三維傳感網(wǎng)的節(jié)點(diǎn)定位問(wèn)題，對(duì)上述問(wèn)題加以考慮，針對(duì)信標(biāo)節(jié)點(diǎn)通信半徑非全網(wǎng)的大規(guī)模網(wǎng)絡(luò)，并結(jié)合Voronoi圖劃分原理、序列定位算法和RSD(Regulated Signature Distance)[16]算法，設(shè)計(jì)一種面向非完全序列的水下三維傳感網(wǎng)定位(Non-Full Sequence-based Localization, NFSL)算法，實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)位置的加權(quán)估算。

2 預(yù)備知識(shí)

本章簡(jiǎn)單介紹3D Voronoi圖[17]在三維定位空間中進(jìn)行區(qū)域劃分的原理以及基于序列的定位算法。

2.1 3D Voronoi圖

Voronoi圖是眾多空間劃分方法之一，它將空間劃分成一定數(shù)量的子區(qū)域。目前，Voronoi圖已被廣泛應(yīng)用于各個(gè)領(lǐng)域，比如地理信息系統(tǒng)、氣象學(xué)以及資訊系統(tǒng)等。許多科研人員利用Voronoi圖來(lái)研究無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋問(wèn)題。

現(xiàn)給定一個(gè)二維平面上傳感器離散點(diǎn)集合P={p1,p2,…,pn}，2≤n<∞，A(x,y)為平面上任意一點(diǎn)，則散點(diǎn)pk(xk,yk)，k∈K={1,2,…,n}與點(diǎn)A的歐氏距離d(pk,A)表示為：

(1)

Voronoi圖基于每個(gè)散點(diǎn)將該平面劃分為n個(gè)區(qū)域，使得每個(gè)區(qū)域有且僅有一個(gè)散點(diǎn)pk，且在散點(diǎn)pk所在Voronoi區(qū)域R(pk)中的任意點(diǎn)A滿足下述條件：

R(pk)={A|d(pk,A)≤d(pj,A),?k≠j∧k,j∈K}

(2)

則散點(diǎn)集P的Voronoi圖R(P)由該平面上所有散點(diǎn)的Voronoi區(qū)域構(gòu)成。

由上述可得，2D Voronoi圖是由一組連接每?jī)蓚€(gè)鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形組成，且該連續(xù)多邊形無(wú)重疊、無(wú)接縫[18-19]，但隨著維數(shù)的增長(zhǎng)，構(gòu)成Voronoi圖的單元也由多邊形變成了高維的多面體，因此，構(gòu)成3D Voronoi圖的單元即為一組三維多面體的集合。如圖1所示，其中，實(shí)心圓點(diǎn)表示在三維定位空間內(nèi)隨機(jī)部署的10個(gè)信標(biāo)節(jié)點(diǎn)，圖示即為基于10個(gè)信標(biāo)節(jié)點(diǎn)的3D Voronoi圖。

最近鄰近性為Voronoi圖的特性之一[20]，即Voronoi子區(qū)域內(nèi)的任意節(jié)點(diǎn)到該區(qū)域信標(biāo)節(jié)點(diǎn)的歐氏距離小于到其他Voronoi子區(qū)域信標(biāo)節(jié)點(diǎn)的歐氏距離，本文正是利用這一特性對(duì)三維定位空間進(jìn)行區(qū)域劃分。

2.2 序列定位算法

近年來(lái)，許多研究提出基于序列的定位方法，其高效性得益于結(jié)合了基于測(cè)距與距離無(wú)關(guān)兩類算法，但目前對(duì)序列定位算法的研究大多都以二維空間作為背景[21]。由于序列定位算法在三維空間的應(yīng)用原理與二維空間相同，且三維空間的圖示較二維空間更為復(fù)雜，所以在這里以序列定位算法在二維空間中的應(yīng)用過(guò)程為例作簡(jiǎn)單說(shuō)明：

步驟1 構(gòu)建二維空間的邊界。

步驟2 利用每?jī)蓚€(gè)相鄰信標(biāo)節(jié)點(diǎn)連線的垂直平分線將邊界內(nèi)的區(qū)域劃分為三類子區(qū)域：點(diǎn)、線、面。

步驟3 計(jì)算每個(gè)子區(qū)域的重心(本文將其稱作虛擬信標(biāo)節(jié)點(diǎn))以及其與各個(gè)信標(biāo)節(jié)點(diǎn)之間的距離。

步驟4 確定定位空間中所有虛擬信標(biāo)節(jié)點(diǎn)的定位序列并將其歸入階次序列表中。

步驟5 計(jì)算未知節(jié)點(diǎn)的定位序列與階次序列表中虛擬信標(biāo)節(jié)點(diǎn)定位序列的等級(jí)相關(guān)系數(shù)，并選擇系數(shù)值最大的虛擬信標(biāo)節(jié)點(diǎn)序列作為距離未知節(jié)點(diǎn)定位序列“最近”的序列。而該“最近序列”所對(duì)應(yīng)的區(qū)域重心即作為未知節(jié)點(diǎn)的估測(cè)位置。

圖1 三維定位空間的Voronoi圖

其中，虛擬信標(biāo)節(jié)點(diǎn)的定位序列與未知節(jié)點(diǎn)的定位序列在后面的3.2節(jié)中會(huì)給出詳細(xì)介紹，階次序列表即包含所有虛擬信標(biāo)節(jié)點(diǎn)的定位序列。

圖2為基于4個(gè)信標(biāo)節(jié)點(diǎn)的3種區(qū)域階次序列確定方法的示例，其中區(qū)域1為點(diǎn)，區(qū)域2為邊，區(qū)域3為面。如上述步驟所示，區(qū)域劃分完成后，根據(jù)各個(gè)子區(qū)域的重心到4個(gè)信標(biāo)節(jié)點(diǎn)的距離即可得到相應(yīng)的階次序列(如區(qū)域1的階次序列為3113，區(qū)域2的階次序列為3211，區(qū)域3的階次序列為1243)。

相比其他基于RSSI的定位算法，基于序列的定位算法無(wú)需利用RSSI來(lái)得到具體的距離參數(shù)，它只用來(lái)確定未知節(jié)點(diǎn)的定位序列，故RSSI方法的固有誤差對(duì)本文基于序列的定位算法影響相對(duì)較小。

序列定位算法在三維定位空間中的應(yīng)用是在二維空間中應(yīng)用的一種拓展與延伸，三維空間被每?jī)蓚€(gè)信標(biāo)節(jié)點(diǎn)連線的垂直平分面劃分出來(lái)的3種類型子區(qū)域分別為：邊、面、體。

圖2 基于4個(gè)信標(biāo)節(jié)點(diǎn)的階次序列示例

3 NFSL算法

水下傳感器網(wǎng)絡(luò)的應(yīng)用場(chǎng)景為三維空間，且Voronoi圖具有高階模型，所以本文考慮將3D Voronoi圖引入到水下傳感網(wǎng)的應(yīng)用場(chǎng)景中。文獻(xiàn)[22]中提出一種基于序列加權(quán)的無(wú)線傳感器網(wǎng)絡(luò)定位算法，雖然該算法降低了邊緣節(jié)點(diǎn)的誤差以及改善了定位精度，但其應(yīng)用背景為二維定位空間，不適應(yīng)于水下傳感網(wǎng)的目標(biāo)定位；文獻(xiàn)[23]提出的一種基于3D Voronoi圖的序列定位算法SL3V (Sequence Localization algorithm based on 3D Voronoi diagram)和文獻(xiàn)[15]提出的一種基于Voronoi圖和階次序列的三維無(wú)線傳感器網(wǎng)絡(luò)定位算法皆以三維傳感網(wǎng)為背景且信標(biāo)節(jié)點(diǎn)的通信范圍都假設(shè)為全網(wǎng)覆蓋，這就導(dǎo)致其無(wú)法應(yīng)用于大規(guī)模三維網(wǎng)絡(luò)或需昂貴的通信范圍極大的傳感器設(shè)備。

針對(duì)上述問(wèn)題，本文提出一種面向非完全序列的水下三維傳感器網(wǎng)絡(luò)定位(NFSL)算法。其基本思想為：首先，利用3D Voronoi圖基于三維定位空間中給定的信標(biāo)節(jié)點(diǎn)對(duì)該區(qū)域進(jìn)行劃分，并將劃分成的Voronoi多面體中3種區(qū)域的幾何中心作為虛擬信標(biāo)節(jié)點(diǎn)；然后，計(jì)算每個(gè)虛擬信標(biāo)節(jié)點(diǎn)到各個(gè)信標(biāo)節(jié)點(diǎn)的距離并得出虛擬信標(biāo)節(jié)點(diǎn)的階次序列以及計(jì)算每個(gè)信標(biāo)節(jié)點(diǎn)到各個(gè)信標(biāo)節(jié)點(diǎn)的距離并得出信標(biāo)節(jié)點(diǎn)的階次序列；接著，通過(guò)RSSI方法得到未知節(jié)點(diǎn)的非完全階次序列，并利用該序列與所有信標(biāo)節(jié)點(diǎn)的階次序列作相似度比較，選擇與其相似度最大的信標(biāo)節(jié)點(diǎn)作為“最鄰近”信標(biāo)節(jié)點(diǎn)，并將該信標(biāo)節(jié)點(diǎn)的階次序列與其所屬區(qū)域所有虛擬信標(biāo)節(jié)點(diǎn)的階次序列列入表中從而構(gòu)建出與該未知節(jié)點(diǎn)相對(duì)應(yīng)的最鄰近序列表；最后，利用修改后的RSD算法計(jì)算未知節(jié)點(diǎn)序列與其對(duì)應(yīng)的最鄰近序列表中所有序列的相關(guān)系數(shù)，通過(guò)對(duì)該系數(shù)作歸一化處理并將所得結(jié)果作為權(quán)重實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)位置的加權(quán)估計(jì)。

3.1 三維定位空間的劃分

根據(jù)實(shí)際的定位環(huán)境在三維空間中構(gòu)造立方體邊界，且信標(biāo)節(jié)點(diǎn)被隨機(jī)分布于定位空間中。本文使用3D Voronoi圖劃分三維定位空間，Voronoi多面體產(chǎn)生后，每一個(gè)信標(biāo)節(jié)點(diǎn)都在相應(yīng)的Voronoi多面體內(nèi)部。為了降低空間劃分的復(fù)雜度，本文利用文獻(xiàn)[18]中提出的快速生成3D Voronoi圖方法。

區(qū)域劃分完成后，三維定位空間就被每?jī)蓚€(gè)信標(biāo)節(jié)點(diǎn)之間的垂直平分面分隔成了3種類型的區(qū)域，即邊、面、體。如圖3所示，其中，實(shí)心圓點(diǎn)表示三個(gè)信標(biāo)節(jié)點(diǎn)A、B、C。

圖3 虛擬信標(biāo)節(jié)點(diǎn)階次序列示例

3.2 階次序列的計(jì)算

本文算法涉及到對(duì)3種序列的處理，分別為：信標(biāo)節(jié)點(diǎn)的階次序列(與信標(biāo)節(jié)點(diǎn)的定位序列等同，后可類比之)、虛擬信標(biāo)節(jié)點(diǎn)的階次序列和未知節(jié)點(diǎn)的階次序列。

3.2.1 信標(biāo)節(jié)點(diǎn)階次序列

作為信標(biāo)節(jié)點(diǎn)，其位置信息皆為已知條件，那么就可以利用兩點(diǎn)距離公式計(jì)算一個(gè)信標(biāo)節(jié)點(diǎn)與其他信標(biāo)節(jié)點(diǎn)的距離，根據(jù)距離的由近到遠(yuǎn)將對(duì)應(yīng)的信標(biāo)節(jié)點(diǎn)編號(hào)表達(dá)成為一個(gè)階次序列，則由此方法可得到每個(gè)信標(biāo)節(jié)點(diǎn)的階次序列，記為Seq_anch。舉例說(shuō)明，如表1所示，已編號(hào)的5個(gè)信標(biāo)節(jié)點(diǎn)A、B、C、D、E，信標(biāo)節(jié)點(diǎn)A距離自己以及其他4個(gè)信標(biāo)節(jié)點(diǎn)的距離分別為0，419.469 9，573.551 2，462.814 2，548.015 5，由于與節(jié)點(diǎn)A距離從近到遠(yuǎn)的信標(biāo)節(jié)點(diǎn)編號(hào)分別為：1、2、4、5、3，所以信標(biāo)節(jié)點(diǎn)A的階次序列為12453。

表1 信標(biāo)節(jié)點(diǎn)階次序列的確定

3.2.2 虛擬信標(biāo)節(jié)點(diǎn)階次序列

首先，給出虛擬信標(biāo)節(jié)點(diǎn)的定義：本文將利用3D Voronoi圖劃分出的3種區(qū)域(邊、面、體)的幾何中心作為虛擬信標(biāo)節(jié)點(diǎn)。為了簡(jiǎn)化運(yùn)算，每個(gè)區(qū)域的中心被定義如下：任何邊的中心為其中點(diǎn)，任何面的中心根據(jù)文獻(xiàn)[11]中的方法計(jì)算，任何體的中心為相應(yīng)多面體中最遠(yuǎn)的兩個(gè)點(diǎn)連線的中點(diǎn)。

在給定的三維定位空間中，信標(biāo)節(jié)點(diǎn)的位置信息為已知，則所有虛擬信標(biāo)節(jié)點(diǎn)的位置在區(qū)域劃分完成后都已確定并可被推算出來(lái)，那么根據(jù)虛擬信標(biāo)節(jié)點(diǎn)到各個(gè)信標(biāo)節(jié)點(diǎn)距離的遠(yuǎn)近就可得到虛擬信標(biāo)節(jié)點(diǎn)的階次序列，記為Seq_vir。虛擬信標(biāo)節(jié)點(diǎn)序列確定的具體過(guò)程與3.2.1節(jié)中信標(biāo)節(jié)點(diǎn)階次序列的步驟相似。

圖3為虛擬信標(biāo)節(jié)點(diǎn)序列的一個(gè)示例，圖中實(shí)心圓點(diǎn)A、B、C表示信標(biāo)節(jié)點(diǎn)，空心圓點(diǎn)D、E、F表示虛擬信標(biāo)節(jié)點(diǎn)，且每個(gè)虛擬信標(biāo)節(jié)點(diǎn)旁邊都有一個(gè)基于距離階次的定位序列。其中，點(diǎn)D為一個(gè)邊的中心，由于A點(diǎn)到D點(diǎn)的距離排名為第一位(即A點(diǎn)距離D點(diǎn)最近)，且B點(diǎn)距離D點(diǎn)的距離排名為第三位(即B點(diǎn)距離D點(diǎn)最遠(yuǎn))，所以節(jié)點(diǎn)D的階次序列為132。同理，點(diǎn)E是一個(gè)體的中心，其階次序列為231，點(diǎn)F為一個(gè)面的中心，其階次序列為312。

3.2.3 未知節(jié)點(diǎn)階次序列

不同于之前提到過(guò)的眾文獻(xiàn)假設(shè)所有的未知節(jié)點(diǎn)全部位于信標(biāo)節(jié)點(diǎn)的通信范圍內(nèi)，本文提出的定位算法基于水下大規(guī)模三維傳感器網(wǎng)絡(luò)且信標(biāo)節(jié)點(diǎn)的通信范圍非全網(wǎng)覆蓋。首先，全網(wǎng)信標(biāo)節(jié)點(diǎn)向周?chē)膫鞲衅鞴?jié)點(diǎn)發(fā)送數(shù)據(jù)包，未知節(jié)點(diǎn)根據(jù)接收到的RSSI值得到其到各信標(biāo)節(jié)點(diǎn)的距離次序從而劃分出該點(diǎn)到各信標(biāo)節(jié)點(diǎn)的位置序列等級(jí)，最終確定未知節(jié)點(diǎn)的階次序列，記為Seq_unk。

在這里著重說(shuō)明，由于上文提到的信標(biāo)節(jié)點(diǎn)與虛擬信標(biāo)節(jié)點(diǎn)的階次序列都是基于已知的位置信息而得，所以為全序列，即序列長(zhǎng)度為信標(biāo)節(jié)點(diǎn)的總數(shù)；而本節(jié)提出的未知節(jié)點(diǎn)的階次序列是基于RSSI方法而得，由于RSSI會(huì)受到通信范圍的影響，且在大規(guī)模且通信環(huán)境惡劣的水下傳感網(wǎng)中，信標(biāo)節(jié)點(diǎn)通信范圍很難達(dá)到全網(wǎng)覆蓋，所以，未知節(jié)點(diǎn)的階次序列多為非完全序列(即序列長(zhǎng)度小于信標(biāo)節(jié)點(diǎn)的總個(gè)數(shù))。

如圖4所示，N1與N2代表兩個(gè)未知節(jié)點(diǎn)，右邊的序列為其從全網(wǎng)6個(gè)信標(biāo)節(jié)點(diǎn)接收到的RSSI值，其中，Inf表示未知節(jié)點(diǎn)不在該信標(biāo)節(jié)點(diǎn)的通信范圍內(nèi)。以圖中的N1為例，其RSSI序列為-147.01，-157.58，-137.25，-154.34，Inf，-156.60，由于RSSI值的大小可以粗略反映未知節(jié)點(diǎn)到各信標(biāo)節(jié)點(diǎn)距離的遠(yuǎn)近，則該未知節(jié)點(diǎn)的階次序列可根據(jù)RSSI值的由大到小確定，所以N1的階次序列為3-1-4-6-2(序列不包括與該未知節(jié)點(diǎn)無(wú)法通信的信標(biāo)節(jié)點(diǎn)的編號(hào))。N2階次序列的確定與N1同理。

圖4 未知節(jié)點(diǎn)階次序列示例

3.3 最鄰近序列表的構(gòu)建

常用的度量2個(gè)階次序列相似度的準(zhǔn)則為Kendall的Tau指標(biāo)與Spearman的階次相關(guān)系數(shù)，但二者的處理對(duì)象皆為等長(zhǎng)的階次序列，不適用于本文中的非等長(zhǎng)序列(信標(biāo)節(jié)點(diǎn)序列與虛擬信標(biāo)節(jié)點(diǎn)序列均為全序列，未知節(jié)點(diǎn)序列為非完全序列)，因此，本文借鑒RSD算法對(duì)2個(gè)非等長(zhǎng)階次序列進(jìn)行相似度度量并得到其階次相關(guān)系數(shù)，由于該階次相關(guān)系數(shù)被用作權(quán)重，所以本文對(duì)該算法稍加修改使其適應(yīng)于NFSL，修改后的RSD算法可用下式表達(dá)：

(3)

其中，K為序列Sm與Sn并集的長(zhǎng)度，SD(Sm,Sn)為顯性、隱性、可能性3種翻轉(zhuǎn)對(duì)數(shù)量之和[16]，則據(jù)式(3)得到的結(jié)果RSD′(Sm,Sn)即為序列Sm與Sn的階次相關(guān)系數(shù)(即二者的相似度)，其范圍為[0,1]，在3.4節(jié)中將其作為權(quán)重對(duì)未知節(jié)點(diǎn)的位置作加權(quán)估計(jì)。

針對(duì)給定未知節(jié)點(diǎn)X(x,y,z)的階次序列S，利用式(3)計(jì)算序列S與所有信標(biāo)節(jié)點(diǎn)序列的階次相關(guān)系數(shù)，選擇系數(shù)最大的信標(biāo)節(jié)點(diǎn)作為未知節(jié)點(diǎn)X的“最鄰近”信標(biāo)節(jié)點(diǎn)Nb，并將其置于最鄰近序列表T中，另外，將Nb所處Voronoi子區(qū)域中所有虛擬信標(biāo)節(jié)點(diǎn)的階次序列也置于T中。由此，未知節(jié)點(diǎn)X的最鄰近序列表T={T1,T2,…,Tn}即可被確定，其中T1為信標(biāo)節(jié)點(diǎn)Nb的階次序列，T2到Tn為Nb所屬子區(qū)域中所有虛擬信標(biāo)節(jié)點(diǎn)的階次序列。

3.4 未知節(jié)點(diǎn)位置的加權(quán)估計(jì)

給定未知節(jié)點(diǎn)X(x,y,z)的定位序列W，本文算法根據(jù)3.3節(jié)中介紹的方法構(gòu)建X的最鄰近序列表T={T1,T2,…,TN},計(jì)算出W與T中每個(gè)序列的階次相關(guān)系數(shù)(該系數(shù)已歸一化)并將其作為權(quán)重，最后結(jié)合最鄰近序列表T中各個(gè)序列相對(duì)應(yīng)的節(jié)點(diǎn)坐標(biāo)進(jìn)行未知節(jié)點(diǎn)位置的加權(quán)估計(jì)，則未知節(jié)點(diǎn)X(x,y,z)的坐標(biāo)可表示為：

(4)

其中：r(Ti)表示未知節(jié)點(diǎn)序列W與最鄰近序列表T中序列Ti的階次相關(guān)系數(shù)，Ci表示T中第i個(gè)序列Ti對(duì)應(yīng)的坐標(biāo)。

3.5 NFSL算法偽代碼展示

本節(jié)綜合3.1～3.4節(jié)內(nèi)容，給出NFSL的算法流程。首先，根據(jù)已知的信標(biāo)節(jié)點(diǎn)坐標(biāo)矩陣N，計(jì)算信標(biāo)節(jié)點(diǎn)階次序列Seq_anchi以及空間劃分后所得虛擬信標(biāo)節(jié)點(diǎn)的坐標(biāo)矩陣V，根據(jù)N與V計(jì)算出所有虛擬信標(biāo)節(jié)點(diǎn)階次序列Seq_virj；其次，根據(jù)給定未知節(jié)點(diǎn)X的RSSI矩陣S，計(jì)算未知節(jié)點(diǎn)階次序列Seq_unkk；然后，利用式(3)計(jì)算未知節(jié)點(diǎn)序列與所有信標(biāo)節(jié)點(diǎn)序列的階次相關(guān)系數(shù)，并取值最大的信標(biāo)節(jié)點(diǎn)作為該未知節(jié)點(diǎn)的“最鄰近”信標(biāo)節(jié)點(diǎn)Nb，Nb的階次序列記為S_anch，將Nb與其所處Voronoi子區(qū)域中所有虛擬信標(biāo)節(jié)點(diǎn)的階次序列置于最鄰近序列表T中，其對(duì)應(yīng)坐標(biāo)置于坐標(biāo)集C中；最后，利用式(3)計(jì)算出未知節(jié)點(diǎn)序列與T中每條序列的階次相關(guān)系數(shù)r(Ti)，并將其作為權(quán)重，利用式(4)實(shí)現(xiàn)未知節(jié)點(diǎn)X位置的加權(quán)估計(jì)。

偽代碼如下所示。

算法1 NFSL算法。

Input: Coordinates matrix of anchorsN, RSSI matrixS

for each anchornido

Compute theSeq_anchiof all anchors

end for

Compute coordinates matrix of vir_anchorsV

for each vir_anchorvjdo

ComputeSeq_virjof all vir_anchors

end for

Compute theSeq_unkkof all unknown nodes

for unknown nodeXdo

ComputeRSD′(Seq_unkk,Seq_anchi)

according to Eqn. (3)

ConstructCandT

Computer(Ti) =RSD′(Seq_unkk,Ti)

according to Eqn. (3)

Compute coordinate ofXaccording to Eqn. (4)

end for

Output: Coordinates matrix of unknown nodes

4 仿真結(jié)果與性能分析

本文利用Matlab仿真軟件對(duì)提出的定位算法進(jìn)行仿真，評(píng)估其性能，并與DV-Hop、質(zhì)心算法等經(jīng)典定位算法進(jìn)行比較。本章采用的仿真環(huán)境為：500個(gè)節(jié)點(diǎn)隨機(jī)分布于500 m×500 m×500 m的正方體區(qū)域內(nèi)，其中，信標(biāo)節(jié)點(diǎn)比例為0.3，節(jié)點(diǎn)通信半徑均為200 m。以上參數(shù)均為默認(rèn)值，下文仿真中除個(gè)別對(duì)比參數(shù)(如信標(biāo)節(jié)點(diǎn)比例、通信半徑、節(jié)點(diǎn)總數(shù)和網(wǎng)絡(luò)規(guī)模)作為變量以外，其余變量均為默認(rèn)值。另外，本文仿真結(jié)果中的定位誤差是指節(jié)點(diǎn)的實(shí)際定位誤差(m)與節(jié)點(diǎn)通信半徑(m)的比值。如圖5所示，圖中所有參數(shù)皆為默認(rèn)值。

圖5 仿真節(jié)點(diǎn)分布

4.1 通信開(kāi)銷分析

在DV-Hop中，信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置，接收節(jié)點(diǎn)記錄到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)并轉(zhuǎn)發(fā)給下一跳鄰居節(jié)點(diǎn)，最終每一個(gè)未知節(jié)點(diǎn)可以得到與每一個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)；但在NFSL與質(zhì)心算法中，每個(gè)未知節(jié)點(diǎn)僅接收通信范圍內(nèi)所有信標(biāo)節(jié)點(diǎn)的通信信息而不再向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，由此就可獲得NFSL中未知節(jié)點(diǎn)距離信標(biāo)節(jié)點(diǎn)的階次序列和質(zhì)心算法中所有與該未知節(jié)點(diǎn)連通的信標(biāo)節(jié)點(diǎn)位置信息。綜上可得，本文算法與質(zhì)心算法的通信開(kāi)銷大致相同，且小于DV-Hop的通信開(kāi)銷。

4.2 信標(biāo)節(jié)點(diǎn)數(shù)的影響

信標(biāo)節(jié)點(diǎn)占總節(jié)點(diǎn)的比例稱為信標(biāo)節(jié)點(diǎn)比例，信標(biāo)節(jié)點(diǎn)比例的大小將直接影響本文算法的定位精度。圖6(a)～(c)分別表示信標(biāo)節(jié)點(diǎn)比例對(duì)本文提出算法、DV-Hop、質(zhì)心(Centroid)算法3種算法的平均定位誤差、最大定位誤差與最小定位誤差的影響。從圖中可以發(fā)現(xiàn)在信標(biāo)節(jié)點(diǎn)以0.15，0.2，0.25，0.3，0.35，0.4的比例逐漸遞增的情況下，本文算法的平均定位誤差由約0.32下降至約0.23，DV-Hop由約0.33微降至約0.3，質(zhì)心算法則由約0.34降至約0.29，雖然3種算法的定位誤差都在逐漸遞減，但本文算法的定位效果提高最快。表明在信標(biāo)節(jié)點(diǎn)比例增多時(shí)，本文算法的定位精度具有更為明顯的優(yōu)勢(shì)。

4.3 節(jié)點(diǎn)通信半徑、節(jié)點(diǎn)總數(shù)與網(wǎng)絡(luò)規(guī)模的影響

本文算法的定位精度受多種因素影響，因此本節(jié)進(jìn)一步在不同通信半徑、節(jié)點(diǎn)總數(shù)與網(wǎng)絡(luò)規(guī)模的情況下對(duì)算法進(jìn)行了評(píng)估。圖7(a)為通信半徑對(duì)本文算法與經(jīng)典定位算法的平均定位誤差影響對(duì)比圖，從圖中可以看出，通信半徑對(duì)3種算法的影響不盡相同，其中，隨著通信半徑以25 m為間隔從150 m擴(kuò)大至300 m的情況下，本文算法的平均定位誤差從約0.35下降至約0.17，然DV-Hop的定位精度無(wú)明顯波動(dòng)，質(zhì)心算法的定位精度與之降低，定位誤差增至約0.38左右。

圖6 信標(biāo)節(jié)點(diǎn)比例對(duì)定位誤差的影響

圖7(b)為本文算法、DV-Hop算法和質(zhì)心算法平均定位誤差在節(jié)點(diǎn)總數(shù)增加影響下的變化趨勢(shì)?？梢钥闯觯谛艠?biāo)節(jié)點(diǎn)比例不變而節(jié)點(diǎn)總數(shù)以50為間隔從300增至600的情況下，本文算法的定位誤差從約0.31降至約0.24，而質(zhì)心算法的定位誤差則由約0.33降至約0.3，對(duì)比之下，本文算法定位精度的提高速度遠(yuǎn)超于質(zhì)心算法，這是由于信標(biāo)節(jié)點(diǎn)數(shù)隨節(jié)點(diǎn)總數(shù)的增加而增加的原因，說(shuō)明未知節(jié)點(diǎn)的數(shù)量對(duì)本文算法的影響微乎其微。圖中DV-Hop算法的定位誤差曲線無(wú)太大波動(dòng)，說(shuō)明在信標(biāo)節(jié)點(diǎn)比例一定時(shí)，DV-Hop算法的定位精度受節(jié)點(diǎn)總數(shù)變化的影響不明顯，這與該算法的性質(zhì)有關(guān)。

圖7(c)表示在網(wǎng)絡(luò)規(guī)模以50 m為間隔從300 m(長(zhǎng)、寬、高均為300 m)擴(kuò)大至450 m的情況下本文算法與另兩種傳統(tǒng)定位算法的定位誤差對(duì)比圖。由圖可得，網(wǎng)絡(luò)規(guī)模對(duì)本文算法的定位精度有一定影響，網(wǎng)絡(luò)規(guī)模越小定位精度就越高。即使在網(wǎng)絡(luò)規(guī)模較大(網(wǎng)絡(luò)規(guī)模為450 m×450 m×450 m)的情況下，相較于另兩種算法的誤差值(DV-Hop:約0.3，Centroid:約0.33)，本文算法仍具有較低的定位誤差值，約為0.23。

圖7 3種變量對(duì)平均定位誤差的影響

仿真結(jié)果表明，本文算法在通信開(kāi)銷小于或大致相同于另兩種定位算法的情況下，在多種影響因素下均具有較高的定位精度，與傳統(tǒng)定位算法相比其定位精度最大可提高約23%。

5 結(jié)語(yǔ)

本文提出一種面向非完全序列的水下三維傳感網(wǎng)定位算法。利用3D Voronoi圖對(duì)定位空間進(jìn)行區(qū)域劃分，將劃分后得到的Voronoi子區(qū)域邊的中心、面的中心與體的中心作為虛擬信標(biāo)節(jié)點(diǎn)并得到其階次序列，比較由RSSI得到的未知節(jié)點(diǎn)序列與信標(biāo)節(jié)點(diǎn)序列的階次相關(guān)系數(shù)并構(gòu)建最鄰近序列表，最終，利用改進(jìn)后的RSD算法計(jì)算未知節(jié)點(diǎn)序列(非完全序列)與對(duì)應(yīng)的最鄰近序列表中各序列(全序列)的階次相關(guān)系數(shù)，將該系數(shù)作為權(quán)重并結(jié)合對(duì)應(yīng)節(jié)點(diǎn)坐標(biāo)實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)位置的加權(quán)估計(jì)。仿真結(jié)果表明，在不增加任何硬件的情況下，本文算法有效提高了定位精度，與傳統(tǒng)定位算法相比定位精度最大可提高約23%。

References)

[1] DU X D, JI J T, YAN D P. Application research of wireless sensor network in intelligent transportation system [J]. Advanced Materials Research, 2010, 108/109/110/111: 1170-1175.

[2] LIU L, WU X, ZHU Z, et al. A localization algorithm based on beacon error problem in underwater wireless sensor network [C]// Proceedings of the 15th IEEE International Conference on Communication Technology. Piscataway, NJ: IEEE, 2013: 478-482.

[3] WALDMEVER M, TAN H P, SEAH W K G. Multi-stage AUV-aided localization for underwater wireless sensor networks [C]// Proceedings of the 25th IEEE International Conference on Advanced Information Networking and Applications Workshops. Washington, DC: IEEE Computer Society, 2011: 908-913.

[4] BAHL P, PADMANABHAN V N. RADAR: an in-building RF-based user location and tracking system [C]// Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE, 2000: 775-784.

[5] 肖竹,譚光華,李仁發(fā),等.無(wú)線傳感器網(wǎng)絡(luò)中基于超寬帶的TOA/AOA聯(lián)合定位研究[J].計(jì)算機(jī)研究與發(fā)展,2013,50(3):453-460.(XIAO Z, TAN G H, LI R F, et al. Joint TOA/AOA localization based on UWB for wireless sensor networks [J]. Journal of Computer Research and Development, 2013, 50(3): 453-460.)

[6] 吳紹華，張欽宇，張乃通.UWB無(wú)線傳感器網(wǎng)絡(luò)中基于匹配濾波檢測(cè)的TOA估計(jì)[J].軟件學(xué)報(bào),2009,20(11):3010-3022.(WU S H, ZHANG Q Y, ZHANG N T. TOA estimation based on match-filtering detection for UWB wireless sensor networks [J]. Journal of Software, 2009, 20(11): 3010-3022.)

[7] 陳鴻龍，李鴻斌，王智.基于TDoA測(cè)距的傳感器網(wǎng)絡(luò)安全定位研究[J].通信學(xué)報(bào),2008,29(8):11-21.(CHEN H L, LI H B, WANG Z. Research on TDOA-based secure localization for wireless sensor networks [J]. Journal on Communications, 2008, 29(8): 11-21.)

[8] ADEMUWAGUN A, FABIO V. Reach centroid localization algorithm [J]. Wireless Sensor Network, 2017, 9: 87-101.

[9] HOSSEINIRAD S M, POURDEILAMI J, NIAZI M, et al. On improving APIT algorithm for better localization in WSN [J]. Journal of AI & Data Mining, 2013, 2(2): 97-104.

[10] ZHANG A, YE X, HU H, et al. Improved DV-HOP positioning algorithm based on one-hop subdivision and average hopping distance modification [J]. Chinese Journal of Scientific Instrument, 2012, 33(11): 2552-2559.

[11] YEDAVALLI K, KRISHNAMACHARI B. Sequence-based localization in wireless sensor networks [J]. IEEE Transactions on Mobile Computing, 2007, 7(1): 81-94.

[12] 劉志華,陳嘉興,陳霄凱.無(wú)線傳感器網(wǎng)絡(luò)中序列定位新算法的研究[J].電子學(xué)報(bào),2010,38(7):1552-1556.(LIU Z H, CHEN J X, CHEN X K. A new algorithm research of sequence-based localization technology in wireless sensor networks [J]. Acta Electronica Sinica, 2010, 38(7): 1552-1556.)

[13] 裴忠民,鄧志東,徐碩,等.一種基于N-最優(yōu)階次序列的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法[J].自動(dòng)化學(xué)報(bào),2010,36(2):199-207.(PEI Z M, DENG Z D, XU S, et al. A new localization method for wireless sensor network nodes based onN-best rank sequence [J]. Acta Automatica Sinica, 2010, 36(2): 199-207.)

[14] 劉影,錢(qián)志鴻,孫大洋.基于參考點(diǎn)序列的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),2012,42(2):489-493.(LIU Y, QIAN Z H, SUN D Y. Node localization scheme for wireless sensor networks based on reference node sequence [J]. Journal of Jilin University (Engineering and Technology Edition), 2012, 42(2): 489-493.)

[15] LIU J, YAN F, YANG X. 3D localization algorithm based on Voronoi diagram and rank sequence in wireless sensor network [J]. Scientific Programming, 2017, 2017(4): Article No. 4.

[16] ZHONG Z, HE T. RSD: a metric for achieving range-free localization beyond connectivity [J]. IEEE Transactions on Parallel & Distributed Systems, 2011, 22(11): 1943-1951.

[17] ALMASHOR M, KHALIL I. Reducing network load in large-scale, peer-to-peer virtual environments with 3D Voronoi diagrams [C]// Proceedings of the 17th International Conference on High Performance Computing. Washington, DC: IEEE Computer Society, 2010: 1-10.

[18] HWANG G J, ARUL J M, LIN E, et al. Design and multithreading implementation of the wave-front algorithm for constructing Voronoi diagrams [C]// ICA3PP: Proceedings of the 6th International Conference on Algorithms and Architectures for Parallel Processing. Berlin: Springer, 2005: 257-266.

[19] LIU J Y, LIU S. A survey on applications of Voronoi diagrams [J]. Journal of Engineering Graphics, 2004, 25(2): 125-132.

[20] DU Q, GUNZBURGER M, JU L L. Advances in studies and applications of centroidal Voronoi tessellations [J]. Numerical Mathematics: Theory, Methods and Applications, 2010, 3(2): 119-142.

[21] 陳嘉興,劉志華.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的三維序列內(nèi)心定位算法[J].南京理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2011, 35(3): 371-375.(CHEN J X, LIU Z H. 3D Sequences and incenters localization algorithm for nodes in WSN [J]. Journal of Nanjing University of Science & Technology, 2011, 35(3): 371-375.)

[22] 胡敏.基于階次序列加權(quán)的無(wú)線傳感器定位算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(10):116-119.(HU M. Node localization algorithm of wireless sensor networks based on optimal weighted rank sequences [J]. Computer Engineering and Applications, 2014, 50(10): 116-119.)

[23] YANG X, LIU J. Sequence localization algorithm based on 3D Voronoi diagram in wireless sensor network [J]. Applied Mechanics & Materials, 2014, 644-650: 4422-4426.

This work is partially supported by the National Key Research and Development Program of China (2016YFC060908), the National Natural Science Foundation of China (51674255), the Production-Study-Research Joint Prospective Research Project of Jiangsu Province (BY2014028- 09).

CHEDi, born in 1994, M. S. candidate. Her research interests include sensor network, ocean observing network.

NIUQiang, born in 1974, Ph. D., professor. His research interests include machine learning, data mining.