無線傳感器網(wǎng)絡精度優(yōu)選RSSI協(xié)作定位算法

汪 明，許 亮，何小敏

(廣東工業(yè)大學 自動化學院，廣州 510006)(*通信作者電子郵箱celiangxu@gdut.edu.cn)

0 引言

目標定位與追蹤是物聯(lián)網(wǎng)系統(tǒng)的重要需求。傳統(tǒng)定位技術(shù)有全球定位系統(tǒng)(Global Positioning System, GPS)、無線網(wǎng)絡通信技術(shù)WiFi(Wireless Fidelity)、藍牙等，這些技術(shù)都需要附屬設備實現(xiàn)目標定位且成本較高、不易部署，而無線傳感器網(wǎng)絡具有隨機部署、成本低等優(yōu)點。利用無線傳感器網(wǎng)絡節(jié)點自定位技術(shù)實現(xiàn)目標定位與追蹤是當前無線傳感器網(wǎng)絡一個重要應用方向，而高精度和快速定位是節(jié)點自定位追求的目標，因此研究精度高和速度快的無線傳感器網(wǎng)絡定位算法是關(guān)鍵[1-3]。

現(xiàn)存的無線傳感器網(wǎng)絡定位算法主要有兩類：基于距離的定位算法和距離無關(guān)的定位算法。距離無關(guān)定位算法主要有：質(zhì)心算法、距離向量-跳段(Distance Vector-Hop, DV-Hop)算法、無定形(Amorphous)定位算法、近似三角形內(nèi)點測試法(Approximate Point-In-Triangulation Test, APIT)算法[4]，這類算法實現(xiàn)簡單，但定位精度低，無法滿足高精度定位應用需求[5]?；诰嚯x的定位算法能夠?qū)崿F(xiàn)精確定位，但是對節(jié)點硬件要求較高，這類算法主要有到達時間(Time Of Arrival, TOA)、到達時間差(Time Difference Of Arrival, TDOA)、到達角度(Angle Of Arrival, AOA)、接收信號強度指示(Received Signal Strength Indicator, RSSI)，前三者都要求增加額外硬件設備，對傳感器節(jié)點成本要求較高[6]。由于節(jié)點本身具有無線發(fā)射模塊，無需增加額外硬件，因此基于RSSI測距的定位算法得到廣泛研究[7]；但RSSI測距受環(huán)境障礙物和多徑效應影響較大，從而影響定位精度。如何減小環(huán)境因素對RSSI測距的影響，成為現(xiàn)代學者研究的重點[8]。文獻[9]提出一種混合預處理模型處理得到的RSSI值，提高了RSSI測距精度和抗干擾能力，但受環(huán)境影響較大，無法實現(xiàn)精確定位。文獻[10-11]認為較大的RSSI值估算出的距離精度越高，因而提出一種加權(quán)質(zhì)心定位算法，一定程度上提高了節(jié)點定位精度；但節(jié)點一致性不是很好，無法實現(xiàn)精確定位。文獻[12-13]根據(jù)節(jié)點測量功率和平面幾何約束關(guān)系，提出一種動態(tài)獲取區(qū)域路徑損耗指數(shù)的方法，可有效提高信號強度轉(zhuǎn)換成距離的精度；但該方法要求功率測量時無噪聲，實際環(huán)境中很難實現(xiàn)。文獻[14]提出一種將接收信號強度與行人航位推算系統(tǒng)(Pedestrian Dead Reckoning, PDR)相結(jié)合的室內(nèi)定位算法，該算法可有效減小非視距情況下障礙物對定位精度的影響；但引進慣性裝置，使得節(jié)點硬件成本較高，不適合大規(guī)模部署。文獻[15]提出一種針對定位各階段實施定位誤差抑制的基于接收信號強度的協(xié)作定位算法，該算法在一定程度上提高了節(jié)點定位精度；但忽略了未知節(jié)點間的信息，造成了大量冗余信息的浪費。文獻[16]提出一種基于RSSI概率估計函數(shù)的網(wǎng)格定位算法，該算法提高了節(jié)點定位精度，適合局部定位；但穩(wěn)定性較差，具有較大的偶然性。文獻[17]根據(jù)節(jié)點隸屬度建立骨干網(wǎng)，采用兩跳距離估計，結(jié)合協(xié)作技術(shù)，充分利用未知節(jié)點間的冗余信息，該算法定位精度高；但算法復雜，難以實現(xiàn)快速定位要求。文獻[18-19]在不知道節(jié)點發(fā)射功率的情況下，采用一種改進半定規(guī)劃的基于RSSI的協(xié)作定位算法，有效提高了節(jié)點定位精度；但算法計算復雜，對節(jié)點硬件要求高，不適合大規(guī)模部署。上述文獻基于RSSI測距定位算法，主要有以下不足：一是只利用未知節(jié)點與錨節(jié)點間的接收信號強度進行定位，而忽略未知節(jié)點與未知節(jié)點間接收信號強度信息，對未知節(jié)點間冗余信息利用不足，造成信息浪費；二是不加篩選利用未知節(jié)點間接收信號強度RSSI，增加了算法時間復雜度。

針對目前定位算法對未知節(jié)點間接收信號強度RSSI利用不足及盲目利用的問題，本文提出了一種精度優(yōu)選協(xié)作策略的RSSI協(xié)作定位算法，利用未知節(jié)點間接收信號強度RSSI參與節(jié)點位置修正，根據(jù)定位精度篩選參與協(xié)作的未知節(jié)點，有效提高了節(jié)點定位精度和算法效率。與已有定位算法相比，主要有以下改進；

1)根據(jù)RSSI閾值，從大量未知節(jié)點中粗篩選出定位精度相對較高節(jié)點；利用subset子集判斷方法和錨節(jié)點置換準則，進一步挑選出兩級精度協(xié)作骨干節(jié)點，為下一步協(xié)作求精準備條件。

2)以鄰居骨干節(jié)點作為協(xié)作對象，利用未知節(jié)點間的接收信號強度對未知節(jié)點進行協(xié)作求精，避免因參與協(xié)作的未知節(jié)點因自身精度低而無法達到對定位精度修正的效果，提高了節(jié)點定位精度，減小了算法復雜度。

1 動態(tài)信號傳播模型和測距誤差修正函數(shù)

研究分析RSSI信號傳播模型可以知道，路徑損耗指數(shù)λ是信號強度RSSI轉(zhuǎn)換為距離的重要參數(shù)。利用定位區(qū)域內(nèi)錨節(jié)點已知的位置信息和相互間的通信，結(jié)合信號傳播模型，可以實時動態(tài)獲取路徑損耗指數(shù)，建立動態(tài)信號傳播模型，減小環(huán)境對測距的影響。根據(jù)定位區(qū)域內(nèi)錨節(jié)點間已知的實際距離和由信號傳播模型得到的測量距離，建立測距誤差修正函數(shù)，可以進一步提高測距精度。根據(jù)動態(tài)信號傳播模型和測距誤差修正函數(shù)，在測距階段對測量距離進行預處理，可以有效提高定位階段的定位精度。

1.1 對數(shù)信號傳播模型

基于信號強度指示RSSI的定位中，根據(jù)節(jié)點接收到的射頻信號強度，采用適當?shù)臒o線信號傳輸模型，將其轉(zhuǎn)換為距離，最后再利用三邊測量法計算出節(jié)點的位置。實踐表明，射頻信號在傳播時隨著距離逐漸衰減的，其衰減特性服從對數(shù)正態(tài)分布，常用對數(shù)常態(tài)分布模型，作為信號強度和傳播距離的轉(zhuǎn)換關(guān)系，其表達式如下：

P(d)=P(d0)-10λlg (d/d0)+Xσ

(1)

其中：P(d)表示距離發(fā)射節(jié)點距離為d處的接收信號功率，單位為dBm;P(d0)表示距離發(fā)射節(jié)點d0處的接收信號功率，單位為dBm；d0為參考距離，一般取為1 m；λ為路徑損耗指數(shù)，其值受環(huán)境的影響，一般在2～4；Xσ代表環(huán)境噪聲，信號傳輸過程中易受環(huán)境噪聲影響，如信號串擾，式中取Xσ為零均值的高斯噪聲模擬環(huán)境噪聲。接收節(jié)點可根據(jù)接收到的信號強度，利用式(1)計算出與發(fā)射節(jié)點間的距離。

1.2 建立動態(tài)信號傳播模型

路徑損耗指數(shù)λ表示信號強度RSSI隨距離增加衰減的速率，是測距估計的一個重要參數(shù)，其值取決于特定的傳播環(huán)境。準確獲取路徑損耗指數(shù)的值，可以有效減小測距誤差。傳統(tǒng)方法都是根據(jù)經(jīng)驗取λ值，無法得到適應相應環(huán)境的λ值，導致計算距離與實際距離存在較大誤差，而且一旦應用環(huán)境發(fā)生改變，就要重新調(diào)整λ值，使應用不夠靈活。本文結(jié)合位置信息已知的錨節(jié)點，動態(tài)獲取路徑損耗指數(shù)。未知節(jié)點周期性地探測其鄰居錨節(jié)點，選擇其中接收信號強度最大的3個鄰居錨節(jié)點，根據(jù)錨節(jié)點相互間的接收信號強度，結(jié)合信號傳播模型即可實時獲取未知節(jié)點所在定位區(qū)域的路徑損耗指數(shù)。

假設A、B、C為未知節(jié)點N的3個鄰居錨節(jié)點，A與B、C兩個錨節(jié)點間的接收信號強度RSSI分別為P(dB)、P(dC)，代入式(1)可得：

(2)

P(dB)-P(dC)=10λlg (dAB/dAC)

(3)

錨節(jié)點A、B、C位置已知，dAB、dAC的實際距離可以計算出來，根據(jù)式(3)即可求出路徑損耗指數(shù)λ的值。將此時所求得的路徑損耗指數(shù)λ代入信號傳播模型，根據(jù)未知節(jié)點N與錨節(jié)點A、B、C間的接收信號強度，計算出未知節(jié)點與錨節(jié)點間的距離，可以有效減小環(huán)境對測距誤差的影響。

1.3 測距誤差預修正函數(shù)

為進一步減小環(huán)境對測距誤差的影響，減小測距誤差，由定位區(qū)域內(nèi)錨節(jié)點間的實際距離和錨節(jié)點間利用信號傳播模型得到的測量距離，根據(jù)誤差變化的整體趨勢，利用最小二乘法擬合出一條誤差隨距離變化的測距誤差曲線，最后利用測距誤差曲線對未知節(jié)點得到的測量距離進行修正。設實際距離與測量距離之間滿足誤差函數(shù)，其表達式如下：

s′=β1si+β0

(4)

其中si表示測量距離。

平方損失函數(shù)：

(5)

其中：si表示兩個錨節(jié)點間測量距離；Δsi表示錨節(jié)點間實際距離與測量距離之差；n表示定位區(qū)域內(nèi)通信錨節(jié)點的數(shù)量。使用最小二乘法，求得使平方損失函數(shù)最小時的系數(shù)β0、β1，得到測距誤差修正函數(shù)，根據(jù)式(6)修正未知節(jié)點與信標節(jié)點間測量距離：

(6)

根據(jù)定位區(qū)域內(nèi)錨節(jié)點的信息，建立具體環(huán)境下的RSSI信號傳播模型和測距誤差函數(shù)，對測量距離進行預處理，可以有效提高后續(xù)節(jié)點定位精度。

2 精度優(yōu)選策略的RSSI協(xié)作定位算法

傳統(tǒng)定位算法主要關(guān)注未知節(jié)點與錨節(jié)點間的信息，并將其轉(zhuǎn)換成距離進行定位。無線傳感器網(wǎng)絡中，未知節(jié)點不僅可以與錨節(jié)點通信，未知節(jié)點之間也可以相互通信，這樣就會存在大量冗余信息。在協(xié)作定位中，未知節(jié)點間信息被用來對定位節(jié)點進行誤差矯正。對于一個已定位未知節(jié)點，可根據(jù)與其鄰居未知節(jié)點間的信息對自身位置進行矯正，提高節(jié)點定位精度。由協(xié)作定位原理可知，因為需要未知節(jié)點參與協(xié)作求精，在迭代求精的過程中可能會產(chǎn)生累計誤差，因此必須保證協(xié)作節(jié)點的精度足夠高，這樣就可以將協(xié)作過程中的累計誤差降低到最低，同時參與協(xié)作的未知節(jié)點精度越高，對鄰居未知節(jié)點誤差修正效果越好?；诖耍疚奶岢鲆环N基于精度優(yōu)選的協(xié)作策略。對粗定位節(jié)點，利用RSSI閾值、subset子集和錨節(jié)點置換準則篩選出符合精度要求的節(jié)點，并以篩選出的節(jié)點作為協(xié)作對象，對未知節(jié)點進行位置優(yōu)化求精。以篩選出鄰居協(xié)作骨干節(jié)點作為協(xié)作對象，對未知節(jié)點位置進行協(xié)作求精，提高節(jié)點定位精度，同時也避免因參與協(xié)作未知節(jié)點因為自身精度低而無法達到對定位精度修正的效果，提高了協(xié)作效率。

算法流程如圖1所示。1)RSSI粗定位。根據(jù)接收信號強度RSSI計算待定位節(jié)點與錨節(jié)點距離，最后使用極大似然法對未知節(jié)點進行粗定位。2)篩選協(xié)作骨干節(jié)點。根據(jù)信號強度與測距誤差關(guān)系，設置RSSI閾值，快速從大量未知節(jié)點中挑選出定位精度較高的節(jié)點；對挑選出的節(jié)點使用subset子集判定，剔除受環(huán)境影響而不穩(wěn)定的節(jié)點，得到次選協(xié)作骨干節(jié)點；最后利用錨節(jié)點置換原則，篩選出符合精度要求的節(jié)點作為優(yōu)選骨干節(jié)點。3)協(xié)作求精。以鄰居優(yōu)選協(xié)作骨干節(jié)點作為優(yōu)選協(xié)作對象，在鄰居優(yōu)選協(xié)作骨干節(jié)點不足的情況下，再選擇鄰居次選協(xié)作骨干節(jié)點作為協(xié)作對象，對未知節(jié)點進行位置誤差修正。

圖1 精度優(yōu)選協(xié)作定位算法流程

2.1 RSSI粗定位

在定位區(qū)域內(nèi)，當未知節(jié)點鄰居錨節(jié)點數(shù)大于或等于3個時，根據(jù)未知節(jié)點和錨節(jié)點間的接收信號強度RSSI，利用信號傳播模型和測距誤差修正函數(shù)計算出未知節(jié)點與相應錨節(jié)點間距離，最后使用極大似然法對未知節(jié)點進行定位。對鄰居錨節(jié)點數(shù)小于3個的未知節(jié)點，先以一級鄰居骨干節(jié)點作為補充錨節(jié)點進行定位；若錨節(jié)點數(shù)仍低于3個，則再以二級鄰居骨干節(jié)點作為進一步的補充錨節(jié)點進行定位，可有效擴大節(jié)點定位范圍。具體算法如下。

算法1 RSSI粗定位算法。

Input：錨節(jié)點坐標(xanchor,yanchor)，未知節(jié)點i∈1,2,…,n。

Output：未知節(jié)點估計坐標(xN,yN)。

Method:

for alli← 1:ndo

j→ 鄰居錨節(jié)點

ifj≥3 then

(xN,yN) ← ML(Max Likehood Estimation)

else

b1 ← 鄰居優(yōu)選協(xié)作骨干節(jié)點

j←j+b1

ifj≥3 then

(xN,yN) ← ML

else then

b2 → 鄰居次選協(xié)作骨干節(jié)點

j←j+b2

(xN,yN) ← ML

end if

end if

end for

2.2 篩選協(xié)作骨干節(jié)點

參與協(xié)作的節(jié)點精度直接影響著誤差修正效率，本文根據(jù)RSSI閾值、subset子集判斷方法以及錨節(jié)點置換原則，有效篩選出RSSI粗定位精度較高的節(jié)點。首先，使用RSSI閾值，可快速從大量的未知節(jié)點中的篩選出精度相對較高的節(jié)點，減少計算時間。subset子集判斷方法和錨節(jié)點置換原則由于要再次進行定位運算，計算復雜，因此，在使用RSSI閾值篩選出的節(jié)點中，使用subset子集判斷方法和錨節(jié)點置換原則，不僅可以剔除受環(huán)境影響的節(jié)點，篩選出精度高的節(jié)點，同時也能極大減少計算時間，節(jié)省能量。最后以篩選出的節(jié)點作為協(xié)作節(jié)點參與位置誤差修正。

2.2.1 確定RSSI閾值

RSSI值受多徑效應影響較大，同一條件下，RSSI值越大，測距誤差越小，節(jié)點定位精度越高。通過實驗確定不同環(huán)境下的RSSI閾值，再根據(jù)RSSI閾值可以快速從大量未知節(jié)點中篩選出粗定位精度較高的未知節(jié)點。實驗中，信號傳播模型各變量取值如下：參考距離d0為1 m；在參考距離處節(jié)點接收信號強度P(d0)為-40 dBm；Xσ為零均值、方差為2的正態(tài)分布。在仿真環(huán)境下，得到的測距誤差與接收信號強度之間的關(guān)系如表1所示。

表1 測距誤差與信號強度的關(guān)系

由表1的實驗結(jié)果可知，外部條件一定情況下，在路徑損耗指數(shù)相同時，不同節(jié)點間距對應的測距誤差相差很大；在相同節(jié)點間距時，不同路徑損耗指數(shù)對應的測距誤差也存在較大差別。為提高節(jié)點定位精度，應盡量減小測距誤差。根據(jù)表1，取測距誤差參考值為1.5 m，初步篩選出定位精度較高的節(jié)點。由測距誤差得到RSSI閾值如下：當路徑損耗指數(shù)λ在[2,2.5)時，取RSSI閾值為RSSIthres=-65 dBm；當路徑損耗指數(shù)λ在[2.5,3)時，取RSSI閾值為RSSIthres=-80 dBm；當路徑損耗指數(shù)λ在[3,3.5)時，取RSSI閾值為RSSIthres=-90 dBm；當路徑損耗指數(shù)λ在[3.5,4)時，取RSSI閾值為RSSIthres=-100 dBm。

2.2.2 RSSI閾值篩選節(jié)點

由信號傳播模型可知，接收信號強度RSSI隨著節(jié)點間收發(fā)距離的增大而減小。接收信號強度RSSI值越大，根據(jù)信號傳播模型計算得到的測量值與真實值越接近；RSSI值越小，測量值與真實值誤差越大。根據(jù)表1得到的RSSI閾值當來自錨節(jié)點信號強度平均值RSSIav>RSSIthres時，表明此時節(jié)點的測距較精確，定位精度較高。

未知節(jié)點N在同一位置接收來自n1個錨節(jié)點的RSSI值，使用高斯模型對RSSI值進行處理，減少小概率、大干擾事件的影響。最后，對來自不同錨節(jié)點的接收信號強度RSSI求均值：

(7)

其中，n1為鄰居錨節(jié)點數(shù)；RSSIi為與第i個錨節(jié)點間的接收信號強度。結(jié)合路徑損耗指數(shù)判斷其與RSSI閾值的關(guān)系，如果

RSSIav≥RSSIthres

(8)

表示此節(jié)點粗定位精度相對較高。可見，利用RSSI閾值，可以快速從大量未知節(jié)點中初步篩選出定位精度相對較高的節(jié)點。

2.2.3 用subset子集提取次選協(xié)作骨干節(jié)點

RSSI閾值受環(huán)境影響較大，具有不穩(wěn)定性。為進一步消除環(huán)境的影響，本文提出一種subset子集判定的方法。由表1可知，在相同條件下，RSSI值越大，節(jié)點測距誤差越小，定位精度也相應更高。使用極大似然法對未知節(jié)點定位，其實是一個迭代使用三邊測量法縮小定位區(qū)域的過程，未知節(jié)點最終位置實際上是由測距誤差最小的幾個錨節(jié)點決定的。在未知節(jié)點鄰居參考節(jié)點中取4個具有最大RSSI值的錨節(jié)點，取4個錨節(jié)點中的任3個錨節(jié)點為一組，使用三邊測量法定位，可以得到未知節(jié)點的4個估計位置。相應地，這4個估計位置相互間的誤差應該是未知節(jié)點所有鄰居錨節(jié)點的組合中使用三邊測量法時最小的。正常情況下，未知節(jié)點在同一位置的這4個估計位置應該是很接近的，如果4個估計位置相互間的誤差較大，超過某一閾值k,則表示該節(jié)點受環(huán)境影響較大，位置估計不穩(wěn)定?；诖耍x取未知節(jié)點4個具有最大RSSI值的鄰居錨節(jié)點建立一個subset(4,3)子集，subset(4,3)表示在接收信號強度最大4個錨節(jié)點中任意3個錨節(jié)點為一組的一個集合。對每組subset(4,3)中來自3個錨節(jié)點的RSSI值使用三邊測量法進行定位，最終可以得到未知節(jié)點的4個位置估計值，取4個位置相互間誤差最小值：

E=min{dis(ck1,ck2),?k1∈1,2,3,4,

k2∈1,2,3,4 andk1≠k2}

(9)

其中：k1，k2為subset子集序號；ck1為第k1個subset子集得到的位置估計；dis(ck1,ck2)為第k1個subset子集位置估計和第k2個subset子集位置估計之間的誤差距離。當位置誤差滿足：

E≤θ

(10)

則表明節(jié)點估計位置穩(wěn)定，受環(huán)境干擾小，精度較高。實驗中，θ取0.5，將滿足條件式(10)的節(jié)點作為次選協(xié)作骨干節(jié)點。

RSSI閾值篩選節(jié)點計算簡單，但是易受環(huán)境影響，使得RSSI閾值具有不穩(wěn)定性。使用subset(4,3)子集判定條件，可以從RSSI閾值篩選出的節(jié)點中進一步剔除受環(huán)境影響較大的節(jié)點，確保篩選出節(jié)點的高精度和穩(wěn)定性。

2.2.4 用錨節(jié)點置換原則篩選優(yōu)選協(xié)作骨干節(jié)點

因為參與協(xié)作的節(jié)點精度越高，對未知節(jié)點誤差修正效果越明顯，可有效提高協(xié)作效率。為了滿足協(xié)作節(jié)點的高精度要求，還需采取一定的措施對節(jié)點進行再提取，使篩選出的節(jié)點精度盡可能高。這里提出一種錨節(jié)點置換原則，對上面篩選的優(yōu)選協(xié)作骨干節(jié)點進行再處理：設未知節(jié)點N的估計坐標為(xN,yN)，參與定位的3個信標節(jié)點分別為A(xA,yA)、B(xB,yB)、C(xC,yC)?，F(xiàn)在將未知節(jié)點N看成位置已知的信標節(jié)點，坐標為(xN,yN)，稱為轉(zhuǎn)化信標節(jié)點。在信標節(jié)點A、B、C中任選一個節(jié)點，這里選擇信標節(jié)點B，將其看成未知節(jié)點。最后利用信標節(jié)點A、C和未知節(jié)點N對B采用三邊測量法進行定位，估計坐標為B′(xB′,yB′)，最后與B的實際位置進行比較，計算估計誤差：

(11)

最終的誤差由確定δ。δ越小，表明節(jié)點定位誤差越小,實驗中取δ=0.2 m。如果信標節(jié)點B的估計誤差滿足式(11)，可以認為未知節(jié)點N的精度滿足要求，因此將未知節(jié)點N作為協(xié)作節(jié)點。根據(jù)錨節(jié)點置換原則，將篩選出的所有符合條件的未知節(jié)點作為優(yōu)選協(xié)作骨干節(jié)點。

2.3 協(xié)作求精

2.3.1 協(xié)作縮小定位區(qū)域

未知節(jié)點在RSSI定位階段，由于信號強度的測量存在誤差，轉(zhuǎn)化為距離使用三邊測量法進行定位時，得到的只是一個區(qū)域，最后將這個區(qū)域的質(zhì)心作為未知節(jié)點估計位置，使未知節(jié)點的定位精度較低。利用未知節(jié)點間相互通信的協(xié)作信息，可以進一步縮小使用三邊測量法得到的定位區(qū)域，有效提高未知節(jié)點定位精度。

圖2所示為協(xié)作縮小定位區(qū)域圖。O1未知節(jié)點B使用三邊測量法的定位區(qū)域，根據(jù)節(jié)點A與節(jié)點B間的接收信號強度RSSI，利用信號傳播模型可以得到節(jié)點A與節(jié)點B間的測量距離為d12，以節(jié)點A為圓心，d12為半徑作圓與節(jié)點B定位區(qū)域O1相交得到區(qū)域O1′，可將節(jié)點B的位置區(qū)域縮小到O1′里，這樣對節(jié)點B的位置估計就會更加精確。

圖2 協(xié)作縮小定位區(qū)域原理

2.3.2 精度優(yōu)選協(xié)作節(jié)點的協(xié)作策略

根據(jù)協(xié)作縮小定位區(qū)域原理可知，協(xié)作時要根據(jù)協(xié)作節(jié)點的位置對未知節(jié)點進行誤差修正，協(xié)作節(jié)點本身存在誤差，但在協(xié)作時可能會產(chǎn)生累計誤差。正是因為協(xié)作求精時可能會產(chǎn)生累計誤差，所以前面才會采用subset子集判斷方法和錨節(jié)點置換準則以確保篩選出的協(xié)作節(jié)點精度足夠高，這樣協(xié)作節(jié)點參與協(xié)作時，就可以將協(xié)作求精時的累計誤差降到最低，同時也能提高協(xié)作效率?；诖?，本文提出一種基于精度優(yōu)選協(xié)作節(jié)點的協(xié)作策略，在每次協(xié)作中，分為骨干節(jié)點和普通未知節(jié)點的協(xié)作求精。骨干節(jié)點協(xié)作求精：對每個骨干節(jié)點，以鄰居優(yōu)選協(xié)作骨干節(jié)點作為優(yōu)選協(xié)作對象，如果沒有鄰居優(yōu)選協(xié)作骨干節(jié)點，則以鄰居次選協(xié)作骨干節(jié)點作為次選協(xié)作對象，使用協(xié)作算法對節(jié)點位置進行協(xié)作求精。普通未知節(jié)點協(xié)作求精：未知節(jié)點同樣以鄰居優(yōu)選協(xié)作骨干節(jié)點作為優(yōu)選協(xié)作對象，以鄰居次選協(xié)作骨干節(jié)點作為次選協(xié)作對象，使用協(xié)作算法對節(jié)點位置進行協(xié)作求精。最后，直到協(xié)作前后節(jié)點位置無變化則停止。這樣，既可以提高節(jié)點定位精度，同時也減少了計算時間。協(xié)作策略的具體步驟如算法2所示。

算法2 精度優(yōu)選協(xié)作節(jié)點的協(xié)作算法。

Input:低精度未知節(jié)點i粗定位坐標(xN,yN)，骨干節(jié)點j粗定位坐標(xbackbone,ybackbone)。

m→ 骨干節(jié)點數(shù)

for allj← 1:mdo

p→ 鄰居優(yōu)選骨干節(jié)點

ifp>0 then

以p為協(xié)作對象

(xbackbone′,ybackbone′) ← 協(xié)作求精

else

p′ → 鄰居次選協(xié)作骨干節(jié)點

以p′為協(xié)作對象

(xbackbone′,ybackbone′) ← 協(xié)作求精

end if

X←xbackbone-xbackbone′

Y←ybackbone-ybackbone′

end for

m1← 低精度未知節(jié)點數(shù)

for alli← 1:m1do

l← 鄰居優(yōu)選協(xié)作骨干節(jié)點

ifl>0 then

以l為協(xié)作對象

(xN,yN) ← 協(xié)作求精

else

l′ ← 鄰居次選協(xié)作骨干節(jié)點

以l′為協(xié)作對象

(xN,yN) ← 協(xié)作求精

end if

X′ ←xN-xN′

Y′ ←yN-yN′

end for

ifX′=0 andY′=0 andX=0 andY=0 then

stop

Output:未知節(jié)點協(xié)作求精坐標(xN′,yN′)、(xbackbone′,ybackbone′)。

整個協(xié)作過程中，都是盡量選擇精度高節(jié)點作為協(xié)作對象，以協(xié)作節(jié)點精度決定協(xié)作次序，提高協(xié)作效率，避免因參與協(xié)作未知節(jié)點因為自身精度低而無法達到對定位精度修正效果，減少計算時間。

2.4 精度優(yōu)選RSSI協(xié)作定位算法時間復雜度分析

正文內(nèi)容這里采用大O記法O()來體現(xiàn)本文算法中各部分的時間復雜度，O1～O3分別表示RSSI粗定位、篩選協(xié)作骨干節(jié)點和協(xié)作算法的時間復雜度。

1)RSSI粗定位算法。

設初始未知節(jié)點總數(shù)為P，對每個節(jié)點進行三邊定位判斷，時間復雜度為：

T1=O1(P)

(12)

2)篩選協(xié)作骨干節(jié)點。

最壞的情況是每個未知節(jié)點都滿足RSSI閾值判斷和錨節(jié)點置換原則，因此要進行P次運算，則時間復雜度為：

T2=O2(P)

(13)

3)協(xié)作定位。

設優(yōu)選協(xié)作骨干節(jié)點數(shù)為M，次選協(xié)作骨干節(jié)點數(shù)為N，迭代次數(shù)為Q，則骨干節(jié)點協(xié)作求精的時間復雜度為：

T3′=O3′((M+N)×Q)

(14)

未知節(jié)點協(xié)作求精時間復雜度為：

T3″=O3″((P-M-N)×Q)

(15)

總的時間復雜度為：

T3=O3(P×Q)

(16)

RSSI粗定位和篩選協(xié)作骨干節(jié)點計算簡單，為后期協(xié)作求精作準備，算法代價不高。最后的協(xié)作求精階段，基于一種精度優(yōu)選協(xié)作策略，前面的節(jié)點篩選減少了該階段的計算時間，整體算法時間復雜度相對較低。

3 實驗結(jié)果與分析

為驗證所提出定位算法效果，本文在CPU Intel Core i5- 4590@ 3.30 GHz、內(nèi)存4 GB、Matlab R2015a仿真平臺下，對所提算法定位效果進行模擬仿真。

實驗中，設置定位區(qū)域為100 m×100 m正方形區(qū)域，節(jié)點隨機部署在該區(qū)域內(nèi)，節(jié)點總數(shù)目、參考節(jié)點數(shù)和通信半徑等參數(shù)根據(jù)具體實驗要求來設置。設第i個未知節(jié)點實際位置坐標為(xi,yi)，估計位置坐標為(xei,yei)，節(jié)點定位誤差Ei定義如下：

(17)

其中：i=1，2，…，N，代表未知節(jié)點序號；R代表通信半徑。節(jié)點平均定位誤差定義如下：

(18)

節(jié)點平均定位誤差越小，表明算法定位精度越高。

實驗中，將本文算法分別與文獻[15]、文獻[16]和傳統(tǒng)協(xié)作定位算法定位效果進行對比分析。其中，文獻[15]是一種改進的針對各階段實施定位誤差抑制的基于RSSI定位算法；文獻[16]是一種改進的基于RSSI概率估計函數(shù)的網(wǎng)格定位算法。文獻[15-16]相較于傳統(tǒng)的RSSI協(xié)作定位算法，定位精度都有較大的提升。傳統(tǒng)協(xié)作定位算法，即對鄰居未知節(jié)點信息不加篩選盲目利用的協(xié)作定位算法。本文通過分析錨節(jié)點數(shù)、未知節(jié)點數(shù)以及節(jié)點通信半徑對定位精度影響，分別將本文算法與文獻[15-16]兩種改進的RSSI定位算法進行對比。在時間效率上將本文算法和傳統(tǒng)協(xié)作定位算法進行了對比。

3.1 協(xié)作節(jié)點篩選

圖3為在100 m×100 m的網(wǎng)絡區(qū)域內(nèi)，節(jié)點最大通信半徑為20 m時，優(yōu)選協(xié)作骨干節(jié)點分布。圖3(a)為未知節(jié)點數(shù)為50，錨節(jié)點數(shù)為25時，得到優(yōu)選協(xié)作骨干節(jié)點分布圖；圖3(b)為未知節(jié)點數(shù)為100，錨節(jié)點數(shù)為25時，得到的優(yōu)選協(xié)作骨干節(jié)點分布。

由圖3可知，在其他條件相同的情況下，優(yōu)選協(xié)作骨干節(jié)點數(shù)隨著未知節(jié)點數(shù)的增加而增加。

3.2 錨節(jié)點數(shù)對定位精度的影響

圖4為在100 m×100 m的網(wǎng)絡區(qū)域內(nèi)，節(jié)點最大通信半徑為20，未知節(jié)點數(shù)為100，錨節(jié)點數(shù)為10，15，20，25，30，35，40時本文算法和文獻[15-16]改進RSSI定位算法對比曲線。

由圖4可知，在外部條件相同的情況下，本文算法明顯優(yōu)于文獻[15-16]算法。在錨節(jié)點數(shù)較小時，節(jié)點平均定位精度較文獻[15-16]算法也有所提高，但定位精度仍較低；隨著錨節(jié)點數(shù)增加，節(jié)點平均定位精度也不斷提高；當錨節(jié)點數(shù)增加到35以后，節(jié)點平均定位精度變化緩慢趨于穩(wěn)定。實驗表明，本文算法具有很好的魯棒性和穩(wěn)定性。

圖3 優(yōu)選協(xié)作骨干節(jié)點分布

圖4 錨節(jié)點數(shù)對定位精度影響

3.3 未知節(jié)點數(shù)對定位精度影響

圖5為在100 m×100 m的網(wǎng)絡區(qū)域內(nèi)，節(jié)點最大通信半徑為20，未知節(jié)點數(shù)分別為20，50，100時，使用本文算法得到的節(jié)點平均定位誤差對比曲線。

圖5 未知節(jié)點數(shù)對定位精度影響

從圖5可知，未知節(jié)點數(shù)越多，節(jié)點定位精度越高。未知節(jié)點的密度影響著協(xié)作骨干節(jié)點的數(shù)量，因為未知節(jié)點數(shù)越多，協(xié)作骨干節(jié)點也越多，協(xié)作后節(jié)點定位精度相應越高。由此可見，本文算法在節(jié)點密集部署環(huán)境下能取得較好的效果。

3.4 通信半徑對定位精度影響

圖6為100 m×100 m網(wǎng)絡區(qū)域內(nèi)，未知節(jié)點總數(shù)為100個，錨節(jié)點數(shù)為20，節(jié)點通信半徑分別設置為10，15，20，25，30，35，40時，本文算法與文獻[15]、文獻[16]兩種改進RSSI算法平均定位誤差隨節(jié)點通信半徑變化對比。

圖6 通信半徑對定位精度影響

由圖6可知，隨著通信半徑的增大，本文算法節(jié)點平均定位精度逐漸提高。在外部條件相同的情況下，本文算法明顯由于文獻[15]算法、文獻[16]算法。在通信半徑較小的情況下，本文算法節(jié)點平均定位精度相較于文獻[15]算法、文獻[16]算法有所提高，但效果不明顯；當節(jié)點通信半徑大于20 m時，本文算法能夠取得較好的效果，節(jié)點平均定位精度較文獻[15]算法、文獻[16]算法有較大提升?？梢?，本文算法在大范圍網(wǎng)絡能取得較好的效果。

3.5 協(xié)作次數(shù)對定位精度的影響

在100 m×100 m的網(wǎng)絡區(qū)域里，設置節(jié)點最大通信半徑為20，錨節(jié)點的數(shù)量為20，未知節(jié)點數(shù)為100，圖7是本文算法、傳統(tǒng)協(xié)作定位算法和文獻[15]改進RSSI定位算法平均定位誤差與協(xié)作次數(shù)的關(guān)系。

圖7 協(xié)作次數(shù)對定位精度影響

從圖7中節(jié)點平均定位誤差與協(xié)作次數(shù)關(guān)系曲線可知：本文算法和傳統(tǒng)協(xié)作定位算法，節(jié)點定位精度隨著協(xié)作次數(shù)的增加而不斷提高；在相同的協(xié)作次數(shù)下，本文協(xié)作定位算法節(jié)點定位精度明顯高于傳統(tǒng)協(xié)作定位算法。因為本位算法實行的精度優(yōu)選協(xié)作節(jié)點的策略，避免了因參與協(xié)作的未知節(jié)點因為自身精度低而無法對定位精度修正，提高了協(xié)作效率，因此在相同時間內(nèi)，本文算法要比傳統(tǒng)協(xié)作算法取得更高的定位精度。

3.6 節(jié)點定位時間

圖8是在100 m×100 m網(wǎng)絡區(qū)域內(nèi)，節(jié)點最大通信半徑為20 m時，錨節(jié)點數(shù)為20時，本文算法和傳統(tǒng)協(xié)作算法定位時間隨未知節(jié)點數(shù)變化對比。

圖8 節(jié)點定位時間對比

由圖8可知，節(jié)點定位消耗的平均時間隨著未知節(jié)點數(shù)的增加而增大。在外部條件相同，未知節(jié)點一定的情況下，本文算法節(jié)點平均定位時間比傳統(tǒng)協(xié)作定位算法下降了20%，在定位效率上取得極大提升。

4 結(jié)語

無線傳感器網(wǎng)絡定位是無線傳感器網(wǎng)絡應用的一個重要前提，考慮到傳統(tǒng)算法定位精度不足、時間復雜度高等不足，本文提出了無線傳感器網(wǎng)絡RSSI協(xié)作定位算法。仿真實驗結(jié)果表明，在外部條件相同的情況下，相較于傳統(tǒng)算法，本文算法在定位精度上提高了15%，在時間效率提高了20%，在定位精度和時間效率上都有大幅提升，適合節(jié)點在大規(guī)模密集環(huán)境下實現(xiàn)快速精確定位。本文算法主要適用于大規(guī)模密集部署的網(wǎng)絡，下一步將考慮如何實現(xiàn)在稀疏網(wǎng)絡中的高精度快速定位，已進一步減小其在實際應用中的成本。