基于RSSI 的無線傳感器網絡質心定位算法優化①

姜文旭, 柳 迪, 趙書銳, 陳本志, 魏勝非

(東北師范大學 物理學院, 長春 130024)

無線傳感器網絡(wireless sensor network, WSN)由大量的微型傳感器節點組成, 它們通過無線電進行通信, 形成了一個具有無中心、自組織、多跳路由特點的網絡系統[1]. 1978 年, 美國的卡耐基-梅隆大學最早成立了分布式傳感器網絡工作組[2]. 2003 年, 美國《技術評論》雜志將WSN 評選為未來十大新興科技中的第一項. 2006 年, 我國在《國家中長期科學與技術發展規劃綱要》中, 提出的3 個信息領域的前沿方向, 有兩項與WSN 有關. 由此可見, WSN 的發展是必然趨勢.因其可以分布在人員無法到達的區域, 所以WSN 可廣泛應用于國防軍事、環境監測、衛生保健等領域[3].

由于節點拋灑的隨機性, 在WSN 的應用中節點采集的信息數據只有結合與之對應的位置信息才有意義,比如森林突發火災時需要確定節點監測到火源的位置信息; 軍事活動中需要確定節點監測到敵方活動信息的位置信息; 海底探測時需要確定節點監測到海底環境的位置信息. 同時, WSN 為了節約成本并且降低功耗, 只有少部分錨節點攜帶GPS, 其他大部分節點都是不知道具體位置的未知節點, 如何通過已知位置的錨節點得到未知節點的位置信息是WSN 定位技術面臨的一大難點[4]. 所以, 節點定位技術一定程度上決定了WSN 的實際應用前景, 這項技術也是眾多學者研究WSN 的重點方向之一.

在WSN 的定位算法中, 質心定位算法能耗低、實現簡單, 但是定位精度易受到錨節點密度的影響. 所以,很多學者為了減少定位誤差將其與RSSI定位算法相結合進行研究: 文獻[5]使用均值濾波、中值濾波對RSSI進行預處理, 然后對過濾后的信號進行高斯濾波并進行加權, 得到較精確的RSSI值. 該算法通過結合多種濾波方法, 減小了使用單一濾波造成的測率誤差,但是該算法在定位環節沒有考慮到由質心造成的誤差.文獻[6]提出了一種改進的加權質心定位算法, 首先使用中值濾波對RSSI進行預處理, 然后對權值進行距離的差分修正. 該算法在原始的加權質心定位算法基礎上有效地提高了定位精度, 但是能耗過高, 計算量過大.文獻[7]引入迭代的思想, 將已定位成功的未知節點升級為錨節點輔助計算. 該算法可以在錨節點占比小的情況下, 降低無法定位的節點比例, 但是該算法沒有考慮在測距過程中存在的誤差. 文獻[8]在原有錨節點的基礎之上, 利用余弦定理增加了虛擬靜態錨節點參與定位. 該算法降低了定位所需要的硬件成本, 但是沒有考慮到定位過程中將距離作為權重帶來的誤差.

針對上述研究中的缺點和不足, 本文在質心定位算法的基礎之上進行改進, 提出了一種改進的加權質心定位算法, 并通過仿真驗證算法的有效性.

1 質心定位算法

1.1 RSSI 定位算法

接收信號強度指示(received signal strength indicator,RSSI)表示發射端向接收端發送能量信號的信號強度數值[9]. 其定位過程的實現步驟, 依次是信號發射、信號采集、信號轉換以及定位計算[10]. 其中, 第3 步信號轉換最為重要, 該過程通過空間傳播模型來計算錨節點和未知節點間的距離. 本文采用對數——常態分布模型[11], 公式如下:

其中,PL(d)為距離為d(m)時的信號路徑損耗;PL(d0)為距離信號發射端d0(m)處的信號損耗, 其中d0為參考距離, 一般為1 m;η為路徑損耗指數;d為發送端到接收端的距離;Xσ為均值為零, 方差為σ的高斯隨機變量. 則接收信號強度如下:

其中,PT為發送信號強度;RSSI為接收信號強度.

由式(1)、式(2)可得, 錨節點到未知節點之間的距離為:

RSSI定位算法不需要增加多余的硬件模塊, 在實際應用中容易實現, 但是極易受到多徑效應等環境因素的影響, 導致其定位精度不高.

1.2 質心定位算法

質心定位算法[12]是一種不需要測距的定位算法,通過計算網絡連通性進行定位. 其原理是以錨節點為圓心, 以通過路徑損耗模型計算出的距離為半徑畫圓,計算出形成的公共區域的質心坐標. 可得出未知節點A(x,y)的質心算法公式為:

其中, (x,y)為未知節點坐標; (xi,yi)為未知節點通信范圍內第i個錨節點坐標;n為未知節點通信范圍內錨節點數量.

質心定位算法計算簡單、開銷小、容易實現. 但是定位誤差大, 而且定位精度極易受到錨節點數量和均勻程度的影響.

1.3 基于RSSI 的加權質心定位算法

通過文獻[13]可知, 傳統的質心定位算法不能反映出錨節點在節點定位時位置的影響, 因此, 將RSSI值作為權重因子引入質心定位算法中, 以此來反映錨節點的位置對質心坐標的影響. 如果RSSI值越大, 代表節點之間的距離越近, 則該錨節點的位置對質心坐標有更大的影響. 可得出未知節點A(x,y)的加權質心算法公式為:

其中, (x,y)為未知節點坐標; (xi,yi)為未知節點通信范圍內第i個錨節點坐標;RSSIi為第i個錨節點的信號強度值;n為未知節點通信范圍內錨節點數量.

雖然這種改進方法明顯提高了質心定位算法的定位精度, 但是在實際應用中, 外界環境比較復雜,RSSI值極易受到環境干擾, 單純使用RSSI值作為權值不易修正誤差值, 影響定位精度.

1.4 基于RSSI 測距校正的加權質心定位算法

由于實際環境中使用RSSI作為權值會影響到未知節點的定位精度, 因此, 有學者提出利用信號的空間傳輸模型計算出錨節點到未知節點間的距離, 用該距離的倒數作為影響質心的權重因子. 可得出未知節點A(x,y)的加權質心算法公式為:

其中, (x,y)為未知節點坐標; (xi,yi)為未知節點通信范圍內第i個錨節點坐標;di為未知節點A與第i個錨節點經距離校正后的距離值;n為未知節點通信范圍內錨節點數量.

式(5)和式(6)都是在RSSI算法的基礎之上對質心定位算法進行權值修正, 而式(6)考慮到了RSSI的系統環境誤差, 采用距離加權修正定位誤差, 提高了質心定位算法的定位精度. 因此本文保留其優點, 對權值能否繼續優化展開研究.

2 增強型質心定位改進算法

2.1 RSSI 值預處理

在節點定位過程中, 信號傳輸過程很容易受到多徑效應等環境因素的影響, 使得未知節點接收到的RSSI具有較大的波動性. 因此, 本文針對這個問題對接收到的RSSI值進行濾波處理, 得到優化后的RSSI值,用于測距階段的距離計算. 具體實現過程如下:

首先, 設置閾值k, 對未知節點接收到的RSSI值進行計數, 當接收到的RSSI值達到閾值時停止接收, 否則將繼續接收.

然后, 對接收到的RSSI值進行降序排序, 得到集合RSSIsort, 將該集合分別進行均值濾波和中值濾波, 公式如下:

其中,k為未知節點接收到的RSSI值個數,RSSIk為未知節點接收到的第k個RSSI值,RSSIsort為降序排列后的RSSI集合,RSSImid為中值濾波處理后的RSSI值,RSSIAVG為均值濾波處理后的RSSI值.

最后, 對RSSImid和RSSIAVG取平均值, 得到較為準確的RSSI值. 公式如下:

2.2 加權質心定位算法權值改進

在加權質心定位算法中, 權值的選取對節點定位精度影響很大, 式(6)的算法以距離的倒數作為權值來修正誤差, 進一步提高了未知節點的定位精度. 因此,本文將在此基礎上繼續對質心權值進行改進.

由式(3)的變形可得:

可以看出, 在其他參數確定的前提下, 測距值d和RSSI之間更接近于指數關系. 所以, 結合上述距離加權的質心定位算法, 將權值由距離的倒數升級為距離倒數的t次冪. 改進后的公式為:

對于t的取值, 根據文獻[14]的研究可知,t的取值主要受到錨節點密度的影響, 與環境干擾和定位區域大小無關. 因此, 接下來將通過仿真探尋t的最優取值. 仿真中t的取值范圍為[0.5, 2.5], 以0.1 為步長遍歷區間全部數值, 將算法的定位誤差作為評判標準, 分別尋找不同錨節點密度下t的最優取值, 即定位誤差最小時對應t的取值.

仿真實驗中, 實驗環境和實驗條件詳見第3 節. 在200 m×200 m 的區域中, 隨機部署300 個節點, 通信半徑為45 m, 改變錨節點密度, 實驗結果如表1. 由此可見, 其他條件不變, 當錨節點密度不同時, 隨著錨節點密度的增大,t的最優取值分布在(1.8, 2.2)區間. 因此,式(12)中的t值將會依據錨節點密度來確定, 比如錨節點密度為20%, 則t取值為2.

表1 不同錨節點密度下的t 值

2.3 迭代式加權質心定位算法

質心定位算法在定位過程中受錨節點的密度影響很大, 當錨節點密度較低時, 會產生大量無法進行定位的節點, 導致節點的覆蓋率較低. 因此本文引入迭代的思想, 實現過程如下.

當未知節點通信范圍內的錨節點數量大于或等于3 個時, 則使用原有錨節點進行定位; 當未知節點通信范圍內的錨節點數量小于3 個時, 則需要接收已定位節點所攜帶的位置信息, 將其升級為錨節點參與未定位節點的定位. 由于距離越遠節點接收到的RSSI值誤差越大, 使用升級為錨節點的節點參與后續定位運算,將會產生更大的定位誤差. 因此, 如果該節點要用到升級節點, 需要先判斷其接收到的升級節點所攜帶的RSSI值是否滿足閾值N, 如果滿足閾值N則接收, 否則丟棄該節點. 改進后的算法流程圖如圖1 所示.

王樹林在辛娜不斷完成創新高指標后的淡定和高調中，感覺到了不安和壓力。辛娜在家里開始說一不二了。辛娜開始主動干預家庭事務了。換句話說，王樹林十多年建立起來的一家之主的地位變得岌岌可危了。他開始有意無意地抗爭，開始不經思索地否決辛娜的提案，為此，兩個人之間的爭執多了起來，冷戰多了起來。

圖1 迭代式加權質心定位算法流程圖

2.4 改進算法的具體實現步驟

1)錨節點周期性的廣播自身id、位置坐標、RSSI值等信息.

2)每個未知節點分別接收并記錄下多個來自鄰居錨節點發送的信息, 如鄰居錨節點的id、坐標信息和RSSI值. 將每組RSSI值分別進行均值濾波和中值濾波處理, 取二者均值作為該錨節點的RSSI值.

3)使用對數——常態分布模型, 利用上述預處理后的RSSI值計算出每個錨節點到未知節點之間的距離d.

4)若未知節點周圍的錨節點數大于兩個, 則根據改正過的加權質心定位算法式(12), 計算出該未知節點的坐標.

5)逐一檢查未定位的節點, 重新接收鄰居錨節點以及已定位的未知節點的信息, 判斷接受到的RSSI值是否滿足閾值條件, 如果滿足, 則將已定位好的未知節點升級為錨節點, 重新對剩余的未知節點進行定位.

6)計算所有節點的平均定位誤差, 公式為:

其中, (xo,yo)為第i個未知節點的真實坐標, (xbest,ybest)為第i個未知節點的估計坐標,R為節點的通信半徑,Ei為第i個節點的定位誤差,N為未知節點的總數,EAVG為所有未知節點的平均定位誤差.

3 實驗仿真結果分析

3.1 仿真條件

將300 個節點隨機部署在200 m×200 m 的正方形區域中, 根據實驗要求設定錨節點比例和節點通信半徑. 信號傳播模型采用對數——常態分布模型, 路徑損耗指數在不同環境下取值不同, 具體可根據表2 進行參考取值, 仿真中以室內空間為定位環境, 因此將η設為4. 為了提高算法的穩定性, 采用多次重復實驗, 實驗次數為50 次, 最終的結果取50 次的平均值.

表2 各應用場景下路徑損耗系數η 的取值

根據表2 參數設置, 形成最初的節點分布圖, 如圖2所示, 圓形代表未知節點, 星形代表錨節點, 均勻分布在定位區域內.

圖2 節點分布圖

3.2 錨節點比例的影響

在總節點數為300, 通信半徑45 m, 錨節點比例分別為10%、15%、20%、25%、30%、35%、40%的情況下對質心定位算法、基于RSSI的加權質心定位算法和本文改進后的算法進行仿真, 得到的仿真結果如圖3 所示, 可以看出這3 種算法的平均定位誤差都隨著錨節點比例的增加而減小.

圖3 不同錨節點密度的平均定位誤差圖

當錨節點比例為10%時, 質心定位算法平均定位誤差最大, 這是由于未知節點周圍的錨節點過少, 導致質心定位算法暴露其弊端, 在錨節點密度小的情況下無法精準定位, 而其他兩種算法的平均定位誤差都有明顯的減小, 其中, 基于RSSI的加權質心定位算法平均定位誤差為36.53%, 本文改進算法的平均定位誤差為34.50%, 由此可見這兩種算法都可以有效改善質心定位算法的弊端, 而且本文的改進算法效果更好; 隨著錨節點比例的逐漸增大, 可以看出基于RSSI的加權質心定位算法和本文的改進算法表現出巨大的優越性,定位精度有著顯著的提升, 而本文的改進算法在同等條件下定位精度最高, 同時平均定位誤差減小的最快;當錨節點比例大于20%時, 可以看出3 種定位算法的平均定位誤差減少緩慢, 這是由于隨著錨節點的比例逐漸增大, 錨節點到達了一定數量, 足夠提供較為準確的位置輔助信息; 在其他條件相同的情況下, 錨節點比例為25%時, 本文改進的算法平均定位誤差19.24%,比質心定位算法降低了38.23%, 比基于RSSI的加權質心定位算法降低了14.49%, 由此可見本文的改進算法定位精度明顯優于前兩種算法.

3.3 節點通信半徑的影響

在總節點數為300, 錨節點密度占總節點數20%,節點通信半徑分別為30 m、35 m、40 m、45 m、50 m、55 m、60 m 的情況下對質心定位算法、基于RSSI的加權質心定位算法和本文改進后的算法進行仿真, 得到的仿真結果如圖4 所示, 可以看出這3 種算法的平均定位誤差都隨著節點通信半徑的增大而減小.

圖4 不同節點通信半徑的平均定位誤差圖

當節點通信半徑為30 m 時, 質心定位算法平均定位誤差為45.30%, 在3 種算法中定位誤差最大, 這是由于通信半徑過小, 導致未知節點無法與更多的錨節點進行通信, 從而無法精確定位, 而基于RSSI的加權質心定位算法和本文改進算法的平均定位誤差都有明顯減小, 二者平均定位誤差分別為36.05%和34.07%,由此可見, 這兩種算法都可以有效改善節點通信距離過短時質心定位算法造成的誤差, 而且本文的改進算法效果更好; 隨著通信半徑的逐漸增大, 可以看出基于RSSI的加權質心定位算法和本文的改進算法表現出巨大的優越性, 這兩種算法的定位精度比質心定位算法有著顯著的提升, 而本文的改進算法在同等條件下定位精度最高, 同時平均定位誤差減小的最快; 當通信半徑大于45 m 時, 3 種算法的平均定位誤差減少緩慢, 這是由于通信半徑越大, 節點能收獲到的定位精度越多,定位越精確; 當通信半徑為50 m 時, 本文改進的算法平均定位誤差19.24%, 比質心定位算法降低了40.70%,比基于RSSI的加權質心定位算法降低了18.27%, 由此可見本文的改進算法定位精度明顯優于前兩種算法.

4 結論

本文對質心定位算法及加權質心定位算法進行研究,在此基礎之上提出了一種改進的基于RSSI的加權質心定位算法. 首先在測距階段對RSSI值進行預處理,然后在定位階段對質心定位算法進行加權改進, 進而引入迭代的思想將已定位的未知節點升級為錨節點輔助定位, 最后將其與質心定位算法以及基于RSSI的加權質心定位算法一同進行仿真分析, 結果表明, 本文提出的改進算法相較于其他兩種算法定位精度有明顯的提高.