基于網格分布的加權質心定位算法研究

， ，，

(鄭州輕工業(yè)學院，鄭州 450002)

無線傳感器網絡(Wireless Sensor Network,WSN)是由大量部署在監(jiān)測區(qū)域的傳感器節(jié)點組成的，通過無線通信形成一個多跳的自組織網絡，協(xié)作感知，采集和處理相關監(jiān)控信息[1]。無線傳感器網絡是面向事件的監(jiān)測網絡。在大多數(shù)應用中，位置信息對于感知和采集到的信息來說至關重要。如果不知道其感知對象的位置，則所感知的信息往往是毫無意義的。實時確定事件發(fā)生的位置或獲取消息的節(jié)點位置是傳感器網絡的基本功能之一，也是提供監(jiān)測位置信息的前提。因此，定位技術對傳感器網絡應用的有效性起著關鍵的作用。

無線傳感器網絡節(jié)點定位機制從定位手段上可分為基于測距定位[2]和非測距[3]定位。前者通過測量節(jié)點間的距離或者角度信息(信號到達時間、信號到達時間差、信號到達角度、信號強度等)，使用三邊測量、三角測量或最大似然估計法來計算未知節(jié)點的位置?；跍y距的算法存在需要專用硬件，使傳感器節(jié)點成本和體積加大的缺點，從而限制了其可用性。非測距定位不需要測量節(jié)點與信標節(jié)點間的距離或角度，僅僅依靠網絡的連通度即能完成定位，其在功耗、環(huán)境及成本方面的優(yōu)勢，在大規(guī)模無線傳感器網絡定位中得到了廣泛的關注。典型的非測距方法有質心算法[4]、凸規(guī)劃法[5]、APS定位算法[6]和APIT算法[7]等。

不同的信標節(jié)點布局對相同節(jié)點定位的精度可以相差很大，具體來說，當未知節(jié)點離信標節(jié)點較近時，定位精度較高；反之，定位精度則較低。信標節(jié)點分布不勻會造成空洞等問題。因此,本文采用網格結構的形式來部署網絡，以便對網絡中大部分的節(jié)點都有較高的定位精度。

本文對加權質心定位算法的定位誤差進行分析，得出環(huán)境溫濕度、反射、多徑、物體移動等因素對用RSSI測距技術計算出的權值誤差的影響導致的最終定位誤差；提出基于網格分布的自適應校正的加權質心定位算法，利用由離未知節(jié)點最近的信標節(jié)點所確定的誤差因子，修正利用RSSI測距技術求出的測距值，使未知節(jié)點適應自身所處的環(huán)境，減小因為環(huán)境造成的測距誤差，從而對權值進行修正。

1 加權質心算法模型

假設網絡中的第n個固定信標節(jié)點Bi已知位置坐標為(Xi,Yi)，其中l(wèi)≤i≤n，未知節(jié)點M的估測位置坐標為(Xe,Ye)。

則加權質心算法的計算公式為

(1)

式中:Wi表示每個固定信標節(jié)點的權值。通常該權值是未知節(jié)點到固定信標節(jié)點距離的函數(shù)。如果未知節(jié)點不能與固定信標節(jié)點Bi通信, 那么Wi為零[8]。

1.1 加權質心算法中的權值計算

對于n個固定信標節(jié)點B1(X1,Y1)，B2(X2,Y2),…，Bn(Xn,Yn)，未知節(jié)點M(Xe,Ye)到各節(jié)點的距離分別為d1,d2,d3，…,dn。

首先，只考慮兩個節(jié)點B1、B2。假設兩節(jié)點的質心在B12，位置為(X12,Y12),B12到B1和B2的距離分別為d1,d2，則存在

(X12-X1)/d1=(X2-X12)/d2

(Y12-Y1)/d1=(Y2-Y12)/d2

由此可得

X12=(X1/d1+X2/d2)/(1/d1+1/d2)

Y12=(Y1/d1+Y2/d2)/(1/d1+1/d2)

所以，可以簡單地假設1/di為權值。這樣選擇加權因子能夠體現(xiàn)各個節(jié)點對于未知節(jié)點的決定權大小,其約束力符合加權質心算法的要求[9]。

1.2 無線電傳播路徑損耗模型的分析

無線電信號在空間傳播時會有不同程度的損耗, 這些損耗在很大程度上影響了基于RSSI算法的定位精度, 因而選取合適的損耗模型尤為重要。這里采用自由空間傳播模型和對數(shù)-常態(tài)分布模型，對整個環(huán)境進行仿真模擬。

自由空間無線電傳播路徑損耗模型為

LOSS=32.44+10klgd+10klgf

(2)

式中：d為測點距信源的距離, 單位為km;f為頻率, 單位為MHz;k為路徑衰減因子。其他模型模擬現(xiàn)實環(huán)境,但與現(xiàn)實環(huán)境還有一定差距。對數(shù)-常態(tài)分布模型的路徑損耗計算公式為

PL(d)=PL(d0)+10klg(d/d0)+X0

(3)

式中：X0是平均值為0的高斯分布隨機變數(shù), 其標準差范圍為4～10;k的范圍在2～5之間。取d=1, 代入式(2)，可得LOSS的值。此時，各未知節(jié)點接收信標節(jié)點信號時的信號強度為

RSSI測量值=發(fā)射功率+天線增益-路徑損耗(PL(d))

(4)

通過式(2)、(3)、(4)可以得到距離di，從而通過加權質心算法實現(xiàn)定位[10]。

2 自適應校正的加權質心算法

加權質心定位算法采用RSSI測距來估計節(jié)點間的距離，這種方法不需要信標節(jié)點的硬件改動。但是，因為RSSI測距往往存在不精確的問題，所以算法中的RSSI測距在定位中不直接用來定位計算，而只是用來進行計算加權質心算法的權值參數(shù)，算法的本質還是基于Range-Free的定位。盡管RSSI測距沒有直接用于定位計算，但它存在的誤差對算法的定位精度依然產生著重要的影響。首先分析測距誤差給加權質心定位算法造成的影響，然后用自適應校正的算法來降低這種影響。

2.1 修正因子αij的計算

本文將離未知節(jié)點最近的信標節(jié)點作為參考節(jié)點，用參考節(jié)點的校正因子修正未知節(jié)點的測距。修正后的測距量比原始測距量能更精確地反映節(jié)點間的遠近關系，從而使權值更符合理想測距情況下加權質心算法的要求，達到了提高定位精度的目的。

圖1 自適應修正測距誤差的示意圖

αij≈βij

(5)

(6)

假設每個未知節(jié)點都有一個鄰近信標節(jié)點作為自適應校正參考節(jié)點，使得該節(jié)點的通信范圍存在同一組信標節(jié)點，并能夠對這組信標節(jié)點分別測距，那么，自適應修正后的加權質心定位算法為

(7)

2.2 自適應校正加權質心定位算法的定位

(1)信標節(jié)點周期性發(fā)送自身節(jié)點ID和自身位置信息。

(2)未知節(jié)點在收到信息后，多次記錄RSSI值，然后求均值。

(3)未知節(jié)點在收到超過閾值的n個信標信息后，建立以下4個集合：

①信標節(jié)點集合：Sn={a1,a2,a3,… ,an}；

②未知節(jié)點到錨節(jié)點的距離集合：Dn={d1,d2,d3,…，dn}；

③校正因子集合：Bn={β1,β2,β3,…，βn}；

④信標節(jié)點的位置坐標：Pn={(x1,y2),(x2,y2),(x3,y3),…，(xn,yn)}。

(4)根據(jù)式(6)計算出每個信標節(jié)點的加權值ωi。

(5)根據(jù)式(7)計算出未知節(jié)點的位置坐標(Xe,Ye)，該坐標就是經過自適應校正加權質心算法定位出的未知節(jié)點的坐標。

改進的自適應定位算法的定位流程如圖2所示。

圖2 自適應定位算法的節(jié)點定位流程圖

3 仿真實驗與分析

3.1 仿真實驗

為了對改進算法的有效性和可用性進行驗證，我們使用Matlab先后對傳統(tǒng)質心定位算法和自適應校正的加權質心算法進行仿真比較和仿真實驗，并對仿真結果進行分析。對環(huán)境模型做如下設置：假定環(huán)境是在一個自由空間環(huán)境中進行的，模擬環(huán)境為一個100 m×100 m的區(qū)域，按照網格型部署信標節(jié)點，未知節(jié)點則通過隨機的方式產生，分布如圖3所示。

圖3 錨節(jié)點分布圖

為了衡量定位算法的有效性，本文將定位誤差作為評價定位技術的首要指標。定位誤差一般用誤差值與節(jié)點通信半徑的比例表示。定義為

(8)

(9)

信標節(jié)點按100 m×100 m的結構分布，未知節(jié)點為30個，節(jié)點的通信半徑設為20 m,然后根據(jù)式(2)、(3)、(4)生成的RSSI數(shù)據(jù)，在數(shù)據(jù)中添加均值為0，方差為7的高斯噪聲來代替實際環(huán)境中的反射、多徑和物體移動、氣候等帶來的影響，衰減系數(shù)N取3，再通過自由空間傳播模型和對數(shù)-常態(tài)分布模型，按照上述步驟來仿真定位。對傳統(tǒng)質心定位算法和自適應校正的加權質心算法反復實驗，求出平均定位誤差(見圖4、圖5)。

圖4 傳統(tǒng)質心定位算法的定位仿真圖

圖5 自適應加權質心定位算法的定位仿真圖

3.2 實驗結果分析

由圖4和圖5可以看出，在錨節(jié)點分布均勻，錨節(jié)點比例較高的情況下，質心定位算法和自適應校正的加權質心定位算法都能實現(xiàn)未知節(jié)點的自定位，但是在邊界處，由于錨節(jié)點只存在于未知節(jié)點的一側，導致邊界處未知節(jié)點的定位誤差高于定位區(qū)域中間的未知節(jié)點。從圖6和圖7可以看出，大部分節(jié)點的定位精度都得到了提升。由式(8)計算出的自適應校正加權定位算法的平均定位誤差相對于傳統(tǒng)質心定位算法提高了10.9%。自適應校正的加權定位算法基本上可以準確地定位出定位節(jié)點的位置，能夠滿足傳感器網絡的一般應用要求。

圖6 傳統(tǒng)質心定位算法各未知節(jié)點的誤差圖

圖7 自適應校正的加權質心定位算法各未知節(jié)點的誤差圖

由圖8可以看出，隨著錨節(jié)點通信半徑的增大，兩種定位算法的定位精度都在減小，并且趨于穩(wěn)定。這是因為隨著通信半徑的增大，更多的錨節(jié)點會參與到未知節(jié)點的定位過程中，以錨節(jié)點為頂點的多邊形質心能夠更好地代替未知節(jié)點的位置。但是在通信半徑增大到一定值時，定位誤差對通信半徑變化的影響就不太明顯了，并且通信半徑過大會造成能耗的增大，減小錨節(jié)點的生命周期。所以，通信半徑應該根據(jù)當時的應用要求和環(huán)境來適當選取。在相同條件下，自適應加權定位算法的定位誤差明顯小于傳統(tǒng)質心定位算法和加權質心定位算法。自適應加權質心定位算法比加權質心定位算法的定位誤差降低了約31.3%。

圖8 定位算法的誤差仿真圖

4 結 語

本文提出了自適應加權質心定位算法，將測距得到的RSSI值通過離未知節(jié)點最近的錨節(jié)點進行修正，并使用Matlab軟件對該算法進行了仿真實驗分析。結果表明，此算法在不增加額外硬件的前提下，以增加較小的計算量為代價，提高了節(jié)點的定位精度，可以滿足大多數(shù)無線傳感器網絡節(jié)點定位的需求。

參考文獻：

[1] Tetsushi L. An Overview of the Sensor Networks[J].Transaction on Electronics,Information and Systems,2008,128(10):1498-1503.

[2] Zhang Yuan,Wu Wen-wu,Chen Yue-hui. A Range-based Localization Algorithm for Wireless Sensor Networks[J]. Journal of Communication and Networks,2005,7(4):429-437.

[3] He Qin-bin, Chen Fang-yue，Cai Shui-ming，et al. An Efficient Range-free Localization Algorithm for Wireless Sensor Networks[J].Science China Technological Sciences，2011，54(5):1053-1060.

[4] 何艷麗.無線傳感器網絡質心定位算法研究[J].計算機仿真，2011，28(5)：164-167,219.

[5] 張翰，劉峰.無線傳感網絡基于凸規(guī)劃的改進定位算法：Convex-PIT[J].傳感技術學報，2007,20(5)：1129-1133.

[6] 劉影，錢志鴻，劉丹，等.基于幾何學的無線傳感器網絡定位算法[J].光電子激光，2010,21(10)：1435-1438.

[7] 周四清，陳銳標.無線傳感網絡，APIT定位算法及其改進[J].計算機工程，2009,35(7)：87-89.

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

[9] 張嬋愛，馬艷艷，白鳳娥，等.基于RSSI的加權質心定位算法的實現(xiàn)[J].太原理工大學學報，2009,40(2)：146-147.

[10] 任維政，徐連明，鄧中亮.基于RSSI的測距差分修正定位算法[J].傳感器學報，2008，21(7)：1247-1250.