基于節(jié)點(diǎn)選取的RSSD兩輪協(xié)同定位算法

喬利娟，李　青（中國(guó)人民解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院河南鄭州450002）

基于節(jié)點(diǎn)選取的RSSD兩輪協(xié)同定位算法

喬利娟，李青
（中國(guó)人民解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院河南鄭州450002）

針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)能量有限、節(jié)點(diǎn)密集、能適應(yīng)動(dòng)態(tài)變化的特點(diǎn)，對(duì)于非配合式無(wú)源定位問(wèn)題，提出一種關(guān)于節(jié)點(diǎn)選取的接收信號(hào)強(qiáng)度差（RSSD）兩輪協(xié)同定位算法。在首輪初步定位結(jié)果的基礎(chǔ)上，提出正多邊形匹配因子，在空間域上選擇最優(yōu)節(jié)點(diǎn)參與定位，得到最終定位結(jié)果，從而提高了定位精度。仿真結(jié)果表明：此方法融合了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的特點(diǎn)，充分利用空間位置對(duì)定位的影響，通過(guò)對(duì)比仿真，證明了本文方法的有效性。

無(wú)源定位；接收信號(hào)強(qiáng)度差；空間域分布；節(jié)點(diǎn)選取

0　引言

無(wú)源定位在社會(huì)、軍事等眾多領(lǐng)域有著廣泛應(yīng)用，基于無(wú)線(xiàn)傳感器網(wǎng)實(shí)現(xiàn)無(wú)源定位，理論上可以充分發(fā)揮分布式協(xié)同定位的優(yōu)勢(shì)，利用節(jié)點(diǎn)的冗余盡可能地提高定位的精確度。然而傳感器的微型化發(fā)展只能為網(wǎng)絡(luò)提供有限的能量供應(yīng)和處理能力，因此，尋找合適的傳感器節(jié)點(diǎn)參與定位，設(shè)計(jì)定位算法，提高定位精度，已經(jīng)成為當(dāng)前無(wú)線(xiàn)傳感器網(wǎng)絡(luò)研究領(lǐng)域的熱點(diǎn)問(wèn)題。

文獻(xiàn)［1］針對(duì)當(dāng)前節(jié)點(diǎn)部署方法存在的生命周期過(guò)短、節(jié)點(diǎn)冗余等缺陷提出改進(jìn)遺傳模擬退火策略進(jìn)行節(jié)點(diǎn)部署，然而這并不適用于每種定位場(chǎng)景。為此，文獻(xiàn)［2］提出在采用最小二乘法的基礎(chǔ)上，利用累積相對(duì)距離誤差的方法進(jìn)行節(jié)點(diǎn)選取，然而其并未對(duì)距離誤差進(jìn)行區(qū)別。文獻(xiàn)［3］針對(duì)參考節(jié)點(diǎn)作為消元對(duì)象產(chǎn)生的誤差平方和不同問(wèn)題，提出一種基于最小誤差平方和的多邊定位節(jié)點(diǎn)選取方法。同樣，文獻(xiàn)［4］在考慮各個(gè)測(cè)距值誤差的基礎(chǔ)上，引入權(quán)重系數(shù)，提出一種基于最小均方誤差原則的節(jié)點(diǎn)選擇方法。文獻(xiàn)［5］從數(shù)學(xué)角度推導(dǎo)備選節(jié)點(diǎn)之間單位向量差作為節(jié)點(diǎn)價(jià)值函數(shù)，以此作為選取節(jié)點(diǎn)的標(biāo)準(zhǔn)，從而提高了計(jì)算效率。然而以上都沒(méi)有從空間角度對(duì)節(jié)點(diǎn)選取進(jìn)行論證，文獻(xiàn)［6～8］從理論上證明了最佳計(jì)算單元的空間組成并提出混沌三角形定位參考點(diǎn)選擇算法，盡管如此，對(duì)于一般場(chǎng)景的節(jié)點(diǎn)選取來(lái)講，其方法仍然缺乏普適性。

為了使空間節(jié)點(diǎn)選取更具有普適性，本文采用接收信號(hào)強(qiáng)度差（RSSD）兩輪協(xié)同定位算法，首輪對(duì)參與定位的節(jié)點(diǎn)個(gè)數(shù)進(jìn)行討論，從定位算法本身、定位精度、計(jì)算復(fù)雜度三個(gè)角度進(jìn)行合理優(yōu)化。第二輪，考慮不同空間位置對(duì)定位的影響，選取空間最優(yōu)節(jié)點(diǎn)參與定位。從而，提出每輪定位機(jī)制下的定位流程，得到最終定位結(jié)果。

1　系統(tǒng)模型與流程

本文采用經(jīng)典對(duì)數(shù)正態(tài)模型［9］，針對(duì)無(wú)源定位當(dāng)中參考節(jié)點(diǎn)信息缺失的問(wèn)題，引入RSSD定位機(jī)制［10］，從而消除參考信息的影響，最后采用最小二乘法進(jìn)行定位解算，得到定位結(jié)果。

首輪定位通過(guò)定位算法本身、定位精度、計(jì)算復(fù)雜度三個(gè)方面建立模型，歸一化求解參與定位的最優(yōu)節(jié)點(diǎn)個(gè)數(shù)，采用強(qiáng)度排序法選取參與定位的節(jié)點(diǎn)。第二輪定位從空間域出發(fā)，提出正多邊形匹配度因子，選擇最優(yōu)空間位置的節(jié)點(diǎn)參與定位?？傮w流程如圖1所示。

圖1　系統(tǒng)總體流程圖Fig 1　Flow chart of overall system

2　節(jié)點(diǎn)選取算法

2.1節(jié)點(diǎn)首輪定位機(jī)制

2.1.1首輪參與定位的節(jié)點(diǎn)討論

1）定位算法對(duì)參與定位節(jié)點(diǎn)個(gè)數(shù)的約束

由RSSD—LS解算方法可知，待定位輻射源的坐標(biāo)其實(shí)是方程組的解，對(duì)于二維空間，至少需要3個(gè)傳感器節(jié)點(diǎn)，同時(shí)為了避免可能出現(xiàn)定位模糊，參與定位傳感器節(jié)點(diǎn)個(gè)數(shù)至少為4。因此設(shè)置參與定位的傳感器節(jié)點(diǎn)個(gè)數(shù)大于4。

2）計(jì)算精度對(duì)參與定位節(jié)點(diǎn)個(gè)數(shù)的約束

參數(shù)估計(jì)方差的克拉美羅下界（CRLB）給出了無(wú)偏估計(jì)方差的下界，因此，其可以作為判斷定位精度的指標(biāo)之一。不同個(gè)數(shù)的節(jié)點(diǎn)參與定位時(shí)，CRLB是不同的，用歸一化函數(shù)表征為f（x），x=4，5，…，歸一化采用線(xiàn)性函數(shù)法。

3）計(jì)算復(fù)雜度對(duì)參與定位節(jié)點(diǎn)個(gè)數(shù)的約束

由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量的限制，因此，計(jì)算復(fù)雜度是必須要考慮的因素之一。忽略空間復(fù)雜性。分析RSSD算法可得，其計(jì)算復(fù)雜度為O（m），m為參與定位個(gè)數(shù)，對(duì)計(jì)算復(fù)雜度進(jìn)行歸一化，得到函數(shù)g（x）。

在實(shí)際工程中，以上三個(gè)方面對(duì)參與定位的傳感器節(jié)點(diǎn)都將產(chǎn)生影響，因此，需要對(duì)函數(shù)f（x），g（x）和O（m）進(jìn)行最優(yōu)化處理，從而在消耗盡可能少的資源的情況下，達(dá)到盡可能高的定位精度。

以上可以通過(guò)建立模型，歸結(jié)為求解以下問(wèn)題：

2.1.2首輪定位流程

首輪定位首先對(duì)監(jiān)測(cè)節(jié)點(diǎn)接收到的信號(hào)功率進(jìn)行預(yù)處理，其次，通過(guò)求解關(guān)于參與定位的傳感器節(jié)點(diǎn)個(gè)數(shù)約束條件，選擇合適的傳感器個(gè)數(shù)參與定位，最后采用RSSD定位算法，通過(guò)最小二乘解算算法得到輻射源的初步定位結(jié)果。以下為首輪定位流程：

1）全部傳感器節(jié)點(diǎn)（假定有N個(gè)傳感器節(jié)點(diǎn)），以周期T接收單一輻射源的信息，獲取傳感器節(jié)點(diǎn)i當(dāng)前位置的RSSI值，記為RSSIi。

4）根據(jù)2.1的節(jié)點(diǎn)選取方法，得到參與定位的節(jié)點(diǎn)個(gè)數(shù)為M1。

5）選擇RSSI平均值最大的前M1個(gè)傳感器節(jié)點(diǎn)參與RSSD定位，并且將RSSI平均值最大，即傳感器節(jié)點(diǎn)作為RSSD定位的參考節(jié)點(diǎn)。

2.2節(jié)點(diǎn)第二輪定位機(jī)制

2.2.1第二輪參與定位的節(jié)點(diǎn)討論

根據(jù)定位參考點(diǎn)優(yōu)化選擇定理［11］，二維空間中，3個(gè)定位節(jié)點(diǎn)參與定位時(shí)，由凸函數(shù)的性質(zhì)和凸優(yōu)化理論可知，將3個(gè)節(jié)點(diǎn)看成定位單元時(shí)，未知節(jié)點(diǎn)相對(duì)于定位單元的任意2個(gè)參考點(diǎn)的角度都為2π/3時(shí)，未知節(jié)點(diǎn)定位誤差值最小。當(dāng)一個(gè)滿(mǎn)足如上的定位單元參與定位時(shí)，定位誤差最小，而當(dāng)有多個(gè)這樣定位單元參與對(duì)一個(gè)未知節(jié)點(diǎn)定位計(jì)算時(shí)，隨著定位單元的個(gè)數(shù)n增多，未知節(jié)點(diǎn)的定位誤差也隨著逐漸減小，最后趨于恒定值πδ2。

計(jì)算并繪制幾何精度因子（GDOP）等高線(xiàn)圖可知，多節(jié)點(diǎn)參與定位時(shí)，當(dāng)節(jié)點(diǎn)呈正N邊形分布時(shí)，其GDOP值最小，此時(shí)定位精度最高［12］，因此，要盡可能選擇以輻射源為中心的正N邊形的傳感器節(jié)點(diǎn)參與定位。

然而在實(shí)際情況中，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，很難找到嚴(yán)格服從理論極值的定位節(jié)點(diǎn)，因此，可以根據(jù)實(shí)際情況，找到逼近于正多邊形的傳感器節(jié)點(diǎn)參與定位。正多邊形的中心到每個(gè)定點(diǎn)的距離都相等，且中心與任意兩個(gè)定點(diǎn)的夾角都相等，由此，提出正多邊形匹配度因子，選擇匹配度最高的一組傳感器節(jié)點(diǎn)參與定位，保證定位精度。過(guò)程如下：

1）設(shè)定角度閾值γ，使得滿(mǎn)足條件2π/n-γ≤αΔij≤2π/n+γ（αΔij為以輻射源為中心，兩個(gè)傳感器節(jié)點(diǎn)i，j之間的夾角）的傳感器節(jié)點(diǎn)參與定位。

2）假定輻射源到傳感器節(jié)點(diǎn)i的距離為di，為逼近正多邊形，選擇滿(mǎn)足的條件以得到面積逼近于正多邊形的傳感器節(jié)點(diǎn)。

3）得到定位結(jié)果后，再重新選擇參與定位傳感器節(jié)點(diǎn)進(jìn)行定位，減小誤差，直到達(dá)到閾值或一定次數(shù)。

綜上，正多邊形匹配因子可以歸結(jié)為求解以下問(wèn)題

2.2.2第二輪定位流程

第二輪定位從傳感器之間夾角和構(gòu)成多邊形面積角度對(duì)傳感器節(jié)點(diǎn)進(jìn)行選擇，找到逼近于正多邊形的傳感器節(jié)點(diǎn)，利用RSSD算法得到位置后以新位置重新選擇傳感器定位節(jié)點(diǎn)，多次迭代，直到達(dá)到一定次數(shù)。定位流程如下：

2）設(shè)定閾值γ，尋找正多邊形匹配因子最大的一組傳感器節(jié)點(diǎn)參與第二輪定位。

3）由步驟（2）的傳感器節(jié)點(diǎn)進(jìn)行RSSD定位，得到輻射源估計(jì)值。

3　仿真與討論

3.1首輪定位仿真性能分析

仿真環(huán)境：仿真軟件環(huán)境為Windows XP系統(tǒng)，硬件配置為2.1 GHz×2、內(nèi)存2 G的宏基筆記本。設(shè)仿真區(qū)域?yàn)?00m×200 m，隨機(jī)產(chǎn)生100個(gè)傳感器節(jié)點(diǎn)的坐標(biāo)，并隨機(jī)產(chǎn)生一個(gè)輻射源，信道模型采用對(duì)數(shù)正態(tài)模型，在Matlab2014環(huán)境下對(duì)每種情況進(jìn)行2000次蒙特卡洛仿真。

首先對(duì)首輪參與定位節(jié)點(diǎn)個(gè)數(shù)進(jìn)行仿真分析，其次，在取得最優(yōu)參與定位節(jié)點(diǎn)個(gè)數(shù)時(shí)，改變不同參數(shù)來(lái)驗(yàn)證本文強(qiáng)度排序法對(duì)提高定位精度的有效性。

圖2為不同定位復(fù)雜度與定位精度在參與定位節(jié)點(diǎn)個(gè)數(shù)（4～15）發(fā)生變化時(shí)，目標(biāo)函數(shù)的變化情況。為了避免目標(biāo)函數(shù)過(guò)分倚重某一個(gè)量值，權(quán)重設(shè)置范圍為0.4～0.6。從圖中可以看出，不管權(quán)重如何變化，目標(biāo)函數(shù)與參與定位的節(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系基本保持不變，先下降再增加，節(jié)點(diǎn)個(gè)數(shù)為7～8時(shí)，目標(biāo)函數(shù)值最小，即此時(shí)定位精度最高。

圖3為以8個(gè)節(jié)點(diǎn)參與定位為例進(jìn)行仿真，圖3（a）參數(shù)設(shè)置：環(huán)境因子np=3，測(cè)量誤差σ=［1 2 3 4 5 6 7 8 9 10］，2000次蒙特卡洛仿真。從圖中可以看出，穩(wěn)定值法選取節(jié)點(diǎn)時(shí)，定位精度隨測(cè)量誤差的增加，表現(xiàn)不穩(wěn)定；隨機(jī)法選取節(jié)點(diǎn)和排序法選取節(jié)點(diǎn)時(shí)，定位精度隨測(cè)量誤差增加基本呈增加趨勢(shì)，體現(xiàn)出正相關(guān)性。與隨機(jī)選取節(jié)點(diǎn)的方法相比，排序法的定位誤差更小，由此證明了本文方法的有效性。

圖2　節(jié)點(diǎn)個(gè)數(shù)選取仿真圖Fig 2　Simulation diagram of number of selected nodes

圖3（b）參數(shù)設(shè)置：測(cè)量誤差σ=3，環(huán)境因子np=［2 3 4 5］，2000次蒙特卡洛仿真。仍然比較以上三種選取節(jié)點(diǎn)方法的有效性。從圖中可以看出，穩(wěn)定值法選取節(jié)點(diǎn)的定位精度最差。隨著環(huán)境因子的增加，隨機(jī)選取法與排序法的定位誤差基本都呈下降趨勢(shì)，且排序法的定位誤差要小于隨機(jī)選取的定位誤差，因此驗(yàn)證了方法的有效性。

圖3　首輪定位精度對(duì)比圖Fig 3　Comparison diagram of the first round localization precision

3.2第二輪定位仿真性能分析

圖4給出的是采用不同方法選擇5個(gè)傳感器節(jié)點(diǎn)參與定位，節(jié)點(diǎn)的分布情況及定位結(jié)果。從圖中可以看出，隨機(jī)選擇方法選擇的節(jié)點(diǎn)具有隨機(jī)性，定位結(jié)果不理想。強(qiáng)度值法選擇的節(jié)點(diǎn)優(yōu)于隨機(jī)值法，定位結(jié)果也更準(zhǔn)確。而本文方法選擇參與定位的節(jié)點(diǎn)構(gòu)成的多邊形最接近于正多邊形，且定位結(jié)果最優(yōu)。

圖5給出的是隨著測(cè)量誤差的增加，采用不同方法選擇5個(gè)傳感器節(jié)點(diǎn)參與定位，得到不同的定位精度。從圖中可以看出，三種方法的定位精度基本都隨著測(cè)量誤差的增加而下降。隨機(jī)值法的定位精度跳變比較大，而本文方法與強(qiáng)度值法的定位精度呈緩慢下降趨勢(shì)，整體來(lái)看，采用本文方法選擇的傳感器節(jié)點(diǎn)最接近于正多邊形，定位精度最高。

圖6和7分別給出的是采用不同方法選擇6個(gè)傳感器節(jié)點(diǎn)參與定位，選擇的傳感器節(jié)點(diǎn)分布情況及定位精度的比較。與5個(gè)節(jié)點(diǎn)相比，得到一致的結(jié)論，且相比之下，定位精度略有提高。同樣證明了本方法的有效性。

圖4　5個(gè)節(jié)點(diǎn)的空間位置對(duì)比圖Fig 4　Spatial position comparison diagram of five nodes

圖5　5個(gè)節(jié)點(diǎn)的定位精度對(duì)比圖Fig 5　Localization precision comparison diagram of five nodes

圖6　6個(gè)節(jié)點(diǎn)的空間位置對(duì)比圖Fig 6　Spatial position comparison diagram of six nodes

圖7　6個(gè)節(jié)點(diǎn)的定位精度對(duì)比圖Fig 7　Localization precision comparison diagram of six nodes

4　結(jié)束語(yǔ)

本文研究了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中基于RSSD的節(jié)點(diǎn)選取及定位問(wèn)題，建立了兩輪定位系統(tǒng)模型，并進(jìn)行了性能分析。首輪定位從不同角度約束參與定位的傳感器個(gè)數(shù)，然后采用排序法選擇參與定位節(jié)點(diǎn)。第二輪定位提出正多邊形匹配因子，作為參與定位的節(jié)點(diǎn)選取指標(biāo)，能夠在選擇出接近最優(yōu)的節(jié)點(diǎn)組合。通過(guò)仿真與其它兩種方法進(jìn)行對(duì)比，結(jié)果表明：本文提出的方法能夠在各限制因素間取得相對(duì)較好平衡，具有較高定位精度，證明了本方法的有效性。

［1］李忠.采用遺傳模擬退火策略的WSNs節(jié)點(diǎn)部署優(yōu)化［J］.系統(tǒng)仿真學(xué)報(bào)，2014，26（2）：353-356.

［2］陳曉輝，陳錦鵬，雷邦軍.無(wú)線(xiàn)傳感器節(jié)點(diǎn)定位中基準(zhǔn)錨節(jié)點(diǎn)的選擇研究［J］.計(jì)算機(jī)工程與應(yīng)用，2012，488（3）：76-90.

［3］周海洋，余劍，張衛(wèi)濤.基于最小誤差平方和的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)多邊定位算法［J］.傳感器與微系統(tǒng)，2014，33（7）：126-132.

［4］藺莉，湯震.基于最小均方誤差選擇參考節(jié)點(diǎn)的RSS測(cè)距定位算法［J］.激光雜志，2015，36（4）：174-1778.

［5］常強(qiáng)，侯洪濤，李群，等.合作定位節(jié)點(diǎn)選擇策略［J］.國(guó)防科技大學(xué)學(xué)報(bào)，2014，36（5）：168-173.

［6］關(guān)沫，趙海，韓光，等.普適計(jì)算中定位服務(wù)的參考點(diǎn)選擇及誤差分析［J］.電子學(xué)報(bào)，2005，33（8）：1425-1431.

［7］孫佩剛，趙海，張文波，等.普適計(jì)算中定位服務(wù)的參考點(diǎn)布置及選擇算法［J］.電子學(xué)報(bào)，2006，34（8）：1456-1463.

［8］孫佩剛，趙海，韓光潔，等.混沌三角形定位參考點(diǎn)選擇算法［J］.計(jì)算機(jī)研究與發(fā)展，2007，44（12）：1987-1995.

［9］Li Xinrong.RSS-based location estimation with unknown pathloss model［J］.IEEE Transactions on Wireless Communications，2006，5（12）：3626-3633.

［10］汪子嘉，于宏毅，胡赟鵬.基于分簇傳感網(wǎng)的RSSD/TDOA協(xié)同定位方法［J］.太赫茲科學(xué)與電子信息學(xué)報(bào)，2013，11（6）：902-916.

［11］周艷.智能空間中定位參考點(diǎn)的優(yōu)化選擇及誤差分析［D］.沈陽(yáng)：東北大學(xué)，2008：11.

［12］Levanon N.Lowest GDOP in 2D scenarios［C］∥IEE Proceedings of Radar，Sonar and Navigation，IET，2000，147（3）：149-155.

DOI：10.13873/J.1000—9787（2016）06—0136—03

RSSD two-wheeled cooperative localization algorithm based on nodes selection

QIAO Li-juan，LI Qing
（College of Information System Engineering University of Information Engineering of PLA，Zhengzhou 450002，China）

Aiming at characteristics of limited energy of networks，concentrated nodes and is adapted to dynamic change of the wireless sensor networks（WSNs），a localization algorithm of two-wheeled cooperative based on nodes selection received signal strength difference（RSSD）is proposed to solve the problem of uncooperative passive localization.On the basis of the first round result，regular polygon matching factor is proposed to select the optimal nodes in the space domain to get the final localization result and improve the localization precision. Simulation results show that the proposed method combines the characteristics of WSNs and make full use of influence of space position.By comparing the simulation，the effectiveness of this method is proved.

passive localization；received signal strength difference（RSSD）；spatial domain distribution；node selection

TP393

A

1000—9787（2016）06—0132—04

10.13873/J.1000—9787（2016）06—0132—04

2016—04—12

喬利娟（1989-），女，河南洛陽(yáng)人，碩士研究生，研究方向?yàn)闊o(wú)線(xiàn)傳感網(wǎng)。