基于加權質心算法的無線網絡節點定位方法*

張 維，趙 亮

(1.中國礦業大學 環境與測繪學院，江蘇 徐州 221116；2.江蘇建筑職業技術學院 a.建筑智能學院，b.信電工程學院，江蘇 徐州 221000)

無線傳感器網絡是集成了嵌入式計算、無線通信、微電子和傳感器等技術的綜合平臺，能夠實現信息采集、數據分布式處理和傳輸、信息融合、區域檢測等多種功能，可對網絡分布區內的監測對象和環境變化信息實時感知[1-3].無線傳感器網絡(wireless sensor network，WSN)是由面向任務的大量分布式傳感器構成的無線傳感網絡，以其低成本、低功耗突出優點獲得廣泛應用[4-6].無線傳感器網絡主要包括路由協議、節點定位、拓撲控制等基本部分[7-8].實現目標監測和實時跟蹤的節點定位技術是傳感器網絡的核心技術，具有關鍵和基礎性的作用.在生物醫療、工農業、軍事等領域有廣泛的應用.位置信息獲取的一般辦法是采用GPS定位，但其成本高、功耗大，且衛星信號在有建筑物遮擋地方不一定被傳感器網絡收到，在節點定位中存在困難.非測距定位質心算法只需將定位設備安裝在少數節點上，通過這些相互連通的節點實現定位，具有環境抗干擾，硬件成本和能耗要求低的優點.但多邊定位方程的常態方程中傳統質心算法使用權值相等的各組數據坐標估計，無區別處理定位誤差大小不同情況，影響定位準確性.對此，本文提出了改進加權質心算法的節點定位方法，權值使用常態方程代入解得坐標后的誤差值倒數，改進傳統質心算法，準確性不同的數據通過不同權值對應不同的影響力，提高定位精度.通過在實際環境中利用傳統質心定位算法和提出的加權質心定位算法對未知節點進行定位的實驗表明，提出的加權質心定位算法的定位精度有顯著提高.

1 質心算法

基于非測距的質心定位算法對已知參考節點坐標值進行中和計算，運算簡單，易于實現，其定位過程取決于節點的分布和密度.質心定位利用節點在組網區域中的互通性[9]，基本原理為：參考節點向周圍定期廣播包含自身位置和ID信息的信號，當未知節點在網絡中收到數量達到某預設門限K的信號個數時，待定位未知節點的估計坐標就用這K個參考點組成的多邊形質心表示.算法示意圖如圖1所示.

圖1 質心算法示意圖

五邊形ABCDE的五個頂點坐標分別表示為(x1，y1)、(x2，y2)、(x3，y3)、(x4，y4)、(x5，y5)，若這五個參考節點均在定位節點的通信范圍內，這時五邊形的幾何質心就是所求節點的估算位置(x，y)，其表達式為

(1)

傳統質心算法的優點是運算簡單，不需要進行節點之間協調，便于實現.在基于測距的傳統質心定位算法中，由于隨機誤差等原因，單靠某一組數據的定位結果可能有較大誤差.所以一般是在基于n組數據的傳統質心算法中，最后結果取n個估計位置的平均值，考慮到計算復雜度和通信開銷的狀況，n一般宜取3.傳統的質心算法計算過程為

(2)

2 改進加權質心算法

傳統質心算法在坐標定位估計中默認了各組數據估計坐標的權值相等，對誤差不同的各組數據沒有差別處理.多邊定位算法在理想情況下，b為準確值，解方程得到使AX=b兩邊相等的正確無誤的估計坐標值X.但b在實際情況下是包含誤差的，且最小二乘法解方程時b的誤差越大，得到的估計坐標值X誤差越大，降低了定位精度.基于此，本文提出了改進的加權質心算法，引入權值的概念差別處理具有不同誤差的數據，提高定位精度.改進的加權質心算法在解得坐標后代入方程得到相應誤差值，權值使用該誤差值的倒數，即

(3)

(4)

式中：(xc，yc)為利用改進加權質心算法對三個估算坐標確定的坐標值；Wi為估計坐標值的第i組數據的權值；Ai，bi為對應于第i組數據確定的線性方程參數；norm(X)用來衡量解得坐標的誤差，即X的二范數，其表達式為

(5)

在改進的加權質心算法中，利用權值差別處理具有不同定位誤差的不同定位結果，較小誤差的倒數對應較大的權值，較大誤差的倒數對應較小的權值，優化了傳統質心算法，提高了定位準確性.

3 實驗結果及分析

實驗中，隨機布置1個定位節點和7個參考節點，其位置坐標如表1所示.利用多邊定位的極大似然估計法[10]隨機選取三組數據的坐標值，采用傳統質心算法和加權質心算法二次處理求出三個坐標更精確的解.

表1 節點位置

方程AX=b在每組數據點數為3時不能使用加權質心算法，只能采用傳統質心二次求解.方程AX=b在每組選取4、5、6個點時，利用傳統質心算法和加權質心算法分別計算三個坐標.由均方根誤差(RMSE)來評價定位算法的準確性和精度.

表2為定位過程中的選點分布情況.表3為多邊定位的極大似然法估算分組數據坐標值.利用傳統質心算法和改進加權質心算法優化估計的未知節點坐標對數據進行處理，兩種算法的定位結果如表4所示.

表2 選點分布

表3 各組數據的估計坐標值

表4 定位結果

由表4定位結果可以看出，改進加權質心算法定位誤差小于傳統質心算法的定位誤差，定位精度有顯著提高.

圖2為誤差與參考點個數的關系圖.從圖2中可以看出，誤差隨參考節點數的增加先減小后增大.當參考節點數由3逐漸增大到5的過程中，定位誤差逐漸變小，但當參考節點數由5逐漸變大到6或7時，定位誤差又逐漸增大，選擇5個參考節點時的定位誤差最小，綜合考慮節點成本和計算開銷等因素，參考節點個數最優為5個.

圖2 參考點個數與誤差關系

在通信范圍內，從表1中的7個參考節點坐標中任意選取5組，每組有5個不同參考節點，首先分別利用多邊定位算法得出未知節點坐標，再利用傳統的質心算法和改進加權的質心算法優化未知節點坐標.圖3為兩種算法定位誤差對比圖.由圖3可以看出，加權質心算法相較傳統的質心算法顯著改善了定位誤差，提高了定位精度，定位準確性改善尤為明顯.

圖3 傳統質心和改進加權質心算法誤差對比

在上述五組隨機選取的通信范圍內待測節點中，對應于2、3組的定位數據，節點所在位置的橫縱坐標值分別用坐標軸中的x、y表示，其真實坐標值分別為(9，5)和(6，6)，得到的定位坐標結果如圖4所示.

圖4 坐標定位結果

通過定位結果可以看出，改進加權質心算法的定位精度高于傳統質心算法，更接近于真實值，改進加權質心算法差別處理具有不同誤差的數據，可以提高定位精度，從而優化定位結果.圖5為采用普通質心算法和加權質心算法分別測試6組數據，每組5個節點的時間對比.從圖5中可以看出，加權質心算法用時更少，效率更高.

4 結 論

由于無線傳感網絡中傳統質心定位算法代入各組數據后定位精度較低，提出了改進加權質心算法的節點定位方法.權值使用常態方程代入解得坐標后誤差值的倒數，準確性不同的數據通過不同權值對應不同的影響力，提高了定位精度.分別用傳統質心算法和改進加權質心算法進行MATLAB仿真，最終估測出定位節點的位置坐標.結果表明，改進加權質心算法使用坐標解代入方程后誤差值的倒數為權值，相較傳統質心算法定位誤差小，定位精度高.