基于接收信號強度指示的改進質心定位算法

谷 廣，游 峰

(華南理工大學 土木與交通學院，廣東 廣州 510641)

0 引 言

在無線傳感器網絡(wireless sensor networks,WSNs)中，位置信息對傳感器網絡的檢測活動至關重要[1]，對于定位而言，衡量定位效果優劣的指標包含精度和準確度[2]。目前，全球定位系統(global positioning system,GPS)能兼顧上述指標，但高能耗、高成本等問題，使其難以適用于WSNs。

WSNs定位算法主要分為基于距離和與距離無關兩類[3]。基于距離的定位算法通過測量相鄰節點間的距離或方位進行定位，能實現精確定位，但對硬件要求高，于是出現了距離無關定位算法。但距離無關算法定位精度不夠高，針對該問題，各種提高定位精度的方法相繼被提出。

文獻[11]改進文獻[12]的算法，提出了一種更為合理的權值選取辦法。本文基于文獻[11]，利用RSSI數據提出了一種改進的質心(improved centroid,ICentroid)定位算法算法。

1 質心定位算法

質心定位算法是一種基于網絡連通性的室外定位算法。信標節點周期性地向鄰居節點廣播信標分組，未知節點收到來自不同信標節點的信標分組數量超過某一門限或一定時間后，即確定自身位置為這些信標節點所組成的多邊形的質心

(1)

質心定位算法的精度與信標節點的分布以及密度有很大關系：

1)如圖1(a)所示，未知節點位于△ABC質心位置O，質心算法定位準確；未知節點位于△ABC內其他位置如O1，質心算法會產生比較大的誤差。

為此，從加權[13]、優選距離[14]和幾何[15]等角度，各種提高精度的方法被提出。

圖1 質心定位算法原理

2 傳播模型

無線電在空間傳播不同程度的損耗會影響基于RSSI定位算法的精度。本文選用對數—常態分布模型對整個環境進行仿真研究

(2)

式中Pt為發送功率，一般0～4 dBm；Pl(d0)為經過距離d0后的功率，一般取d0=1 m作為參考點；η為路徑損耗指數，取值范圍一般為2～4；X(σ)為均值為0方差為σ2(通常取4～10)的高斯隨機分布項。

3 改進算法

圖1(b)所示問題由信標節點分布不均勻導致，本文算法原理如圖2所示。

圖2 優選節點原理

若未知節點O落在信標節點組成的△ABC內部O1處或邊界O2處，此時存在

∠AO1B+∠BO1C+∠CO1A=360°

(3)

若未知節點落在△ABC外部(O3)，此時存在

∠AO3B+∠BO3C+∠CO3A<360°

(4)

AB,BC,CA為信標節點A,B,C之間的距離，為已知量；OA,OB,OC為未知節點O與信標節點A,B,C之間的距離，可以通過RSS值估計得到；因此,各角度值可以通過余弦定理求出

如上所述，計劃生育政策的動員模式伴隨著社會和經濟的發展具有嬗變性。 從一元的強制命令發展為交往式的動員方式，交往式的動員模式更加關注個體的動機，憑借“交往+說服”促使個體產生內生性動力，若再配以外部的選擇性激勵，計劃生育政策的實行會產生良好的社會效果和政治效果。 不過，計劃生育政策終究鎖定在“計劃”二字，因此在市場經濟體制下，以“說服”和“交往”為基石的動員式計劃生育政策永遠不會扮演決定性角色，而只能是一個不痛不癢的角色，它天然地依附于公權力強制的角色里。

(5)

由此可以得出未知節點O是否處于信標節點△ABC內部的判據：若

(6)

則未知節點O處于信標節點△ABC外部；若

(7)

則未知節點O處于信標節點△ABC內部或某一邊上；直接采用

(8)

估計未知節點的坐標會產生比較大的誤差，需要進行簡單加權處理

(9)

4 算法步驟

基于上述思想，本文算法步驟如下：

1)信標節點周期性地向周圍環境廣播自身的節點ID、位置等信息。

2)未知節點根據閾值和接收的數據包，生成鄰居節點表。

3)若未知節點的鄰居錨節點數不小于3，執行改進算法；否則,執行步驟(4)。

4)若步驟(3)未能定位該未知節點，則用普通質心算法估計未知節點坐標。

5)若未知節點沒有鄰居信標節點，則將其歸為不可定位節點。

6)計算定位誤差

(10)

式中 (xi,yi),(Xi,Yi)分別為能被定位的未知節點的估計坐標和真實坐標；n為能被定位的未知節點數目；r為節點通信半徑。

5 仿真結果

采用MATLAB進行算法仿真。在100 m×100 m的區域內隨機散布100個無線傳感器節點(包括未知節點與信標節點)，通過定位誤差和無法定位節點數目兩個指標比較算法之間的優劣。

圖3 定位誤差與信標通信半徑關系

圖3(a)～圖3(d)為信標節點數目分別為20，30，40和50時，定位誤差與節點通信半徑的關系。①表示普通質心定位算法，②表示ICentroid算法。可以發現：

1)ICentroid算法比質心定位算法定位精度高，通信半徑越大，精度提高越多。

2)普通質心定位算法定位誤差隨著節點通信半徑增加，先減小后增大。由于隨著通信半徑增大，未知節點能探測到更遠處的信標節點，使其鄰居信標節點變得很不均勻，增大定位誤差。ICentroid算法克服了此缺點。

3)隨著通信半徑的增加，ICentroid算法對定位精度的提高越來越小。因為通信半徑大到一定程度后，大部分未知節點存在鄰居信標節點，可以實現定位。

當信標節點數目為20和30時，無法定位未知節點數目隨通信半徑的變化如圖4。②，③，①線分別表示普通質心定位算法、ICentroid算法、三邊定位算法。

由圖4可知，節點通信半徑小于40 m時，基于RSSI的三邊定位算法無法定位的未知節點數目遠大于普通質心定位算法和ICentroid算法。因為三邊定位算法或極大似然估計法定位要求未知節點至少能捕捉到3個及以上的信標節點數目，否則無法定位。而ICentroid算法對這一條件沒有如此苛刻的要求。由此可見，ICentroid算法較三邊定位或極大似然估計定位精度有所欠缺，但能增加可被定位節點的數目，降低因無法定位的節點帶來的巨大誤差。

圖4 無法定位節點數目與通信半徑的關系

6 結 論

本文的ICentroid定位算法，較傳統質心定位算法定位精度有很大提高，較三邊定位算法無法被定位的節點數有很大減小。ICentroid算法對硬件的要求不高，能較好地適應WSNs低成本等要求；算法思想可被用于改進近似三角形內點測試(approximate point-in-triangulation test,APIT)等與距離無關的定位算法，或采用DV-HOP算法中“用跳數估計距離”的思想替代用“RSSI來獲得估計距離”的辦法，實現真正的“與距離無關”的改進質心定位算法。

[1] 孫利民，李建中.無線傳感器網絡[M].北京:清華大學出版社，2005: 135-155.

[2] Dargie W,Poellabauer C.Fundamentals of wireless sensor networks[M].Hoboken:John Wiley & Sons,2010:249-263.

[3] 王 瓊，候 男 ，孫 輝,等.神經計算融入多邊測量法的機器人定位方法研究[J].自動化技術與應用，2016,35(2)：1-5.

[4] Nafarieh A,Ilow J.A testbed for localizing wireless LAN devices using received signal strength[C]∥Proceedings of the Communication Networks and Services Research Conference,2008.

[5] 趙 昭，陳小惠.無線傳感器網絡中基于RSSI的改進定位算法[J].傳感技術學報,2009，22(3):391-394.

[6] 花 超，古小軍，蔡 萍，等.基于RSSI差分修正的加權質心定位算法[J].傳感器與微系統,2012,31(5):139-141.

[7] 朱忠記,何熊熊，章 曉.基于RSSI的四邊測距改進加權質心定位算法[J].杭州電子科技大學學報,2014(1):17-20.

[8] 朱明輝，張會清.基于RSSI的室內測距模型的研究[J].傳感器與微系統,2010，29(8):19-22.

[9] 呂 振，譚鵬立,一種基于RSSI校正的三角形質心定位算法[J].傳感器與微系統,2010，29(5):122-124.

[10] 丁恩杰,喬 欣，常 飛，等.基于RSSI的WSNs加權質心定位算法的改進[J]. 傳感器與微系統,2013，32(7):53-56.

[11] 劉運杰,金明錄,崔承毅.基于RSSI的無線傳感器網絡修正加權質心定位算法[J].傳感技術學報,2010，23(5):717-721.

[12] 陳維克,李文鐸，首 珩，等.基于RSSI的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報:交通科學與工程版,2006，30(2):265-268.

[13] 胡詠梅，張 歡.一種改進的無線傳感器網絡質心定位算法[J].計算機工程與科學,2012，34(2):45-49.

[14] 孫瑋琢,遲 衛,王擎宇.加權質心定位誤差的反向修正法[J].傳感技術學報,2012,25(1):114-118.

[15] 朱 劍,趙 海，孫佩剛，等.基于RSSI均值的等邊三角形定位算法[J].東北大學學報:自然科學版,2007，28(8):1094-1097.