車 迪，牛 強

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

0 引言

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

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

1 相關(guān)工作

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

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

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

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

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

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

2 預(yù)備知識

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

2.1 3D Voronoi圖

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

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

(1)

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

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

(2)

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

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

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

2.2 序列定位算法

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

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

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

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

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

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

圖1 三維定位空間的Voronoi圖

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

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

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

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

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

3 NFSL算法

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

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

3.1 三維定位空間的劃分

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

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

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

3.2 階次序列的計算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

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

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

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

(4)

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

3.5 NFSL算法偽代碼展示

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

偽代碼如下所示。

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

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

4.1 通信開銷分析

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

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

信標(biāo)節(jié)點占總節(jié)點的比例稱為信標(biāo)節(jié)點比例，信標(biāo)節(jié)點比例的大小將直接影響本文算法的定位精度。圖6(a)～(c)分別表示信標(biāo)節(jié)點比例對本文提出算法、DV-Hop、質(zhì)心(Centroid)算法3種算法的平均定位誤差、最大定位誤差與最小定位誤差的影響。從圖中可以發(fā)現(xiàn)在信標(biāo)節(jié)點以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é)點比例增多時，本文算法的定位精度具有更為明顯的優(yōu)勢。

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

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

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

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

圖7(c)表示在網(wǎng)絡(luò)規(guī)模以50 m為間隔從300 m(長、寬、高均為300 m)擴(kuò)大至450 m的情況下本文算法與另兩種傳統(tǒng)定位算法的定位誤差對比圖。由圖可得，網(wǎng)絡(luò)規(guī)模對本文算法的定位精度有一定影響，網(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種變量對平均定位誤差的影響

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

5 結(jié)語

本文提出一種面向非完全序列的水下三維傳感網(wǎng)定位算法。利用3D Voronoi圖對定位空間進(jìn)行區(qū)域劃分，將劃分后得到的Voronoi子區(qū)域邊的中心、面的中心與體的中心作為虛擬信標(biāo)節(jié)點并得到其階次序列，比較由RSSI得到的未知節(jié)點序列與信標(biāo)節(jié)點序列的階次相關(guān)系數(shù)并構(gòu)建最鄰近序列表，最終，利用改進(jìn)后的RSD算法計算未知節(jié)點序列(非完全序列)與對應(yīng)的最鄰近序列表中各序列(全序列)的階次相關(guān)系數(shù)，將該系數(shù)作為權(quán)重并結(jié)合對應(yīng)節(jié)點坐標(biāo)實現(xiàn)對未知節(jié)點位置的加權(quán)估計。仿真結(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ǎng)絡(luò)中基于超寬帶的TOA/AOA聯(lián)合定位研究[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ǎng)絡(luò)中基于匹配濾波檢測的TOA估計[J].軟件學(xué)報,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測距的傳感器網(wǎng)絡(luò)安全定位研究[J].通信學(xué)報,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ǎng)絡(luò)中序列定位新算法的研究[J].電子學(xué)報,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ǎng)絡(luò)節(jié)點定位方法[J].自動化學(xué)報,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] 劉影,錢志鴻,孫大洋.基于參考點序列的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J].吉林大學(xué)學(xué)報(工學(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ǎng)絡(luò)節(jié)點的三維序列內(nèi)心定位算法[J].南京理工大學(xué)學(xué)報(自然科學(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)的無線傳感器定位算法[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.