基于加權(quán)質(zhì)心算法的無線網(wǎng)絡(luò)節(jié)點(diǎn)定位方法*

張 維，趙 亮

(1.中國(guó)礦業(yè)大學(xué) 環(huán)境與測(cè)繪學(xué)院，江蘇 徐州 221116；2.江蘇建筑職業(yè)技術(shù)學(xué)院 a.建筑智能學(xué)院，b.信電工程學(xué)院，江蘇 徐州 221000)

無線傳感器網(wǎng)絡(luò)是集成了嵌入式計(jì)算、無線通信、微電子和傳感器等技術(shù)的綜合平臺(tái)，能夠?qū)崿F(xiàn)信息采集、數(shù)據(jù)分布式處理和傳輸、信息融合、區(qū)域檢測(cè)等多種功能，可對(duì)網(wǎng)絡(luò)分布區(qū)內(nèi)的監(jiān)測(cè)對(duì)象和環(huán)境變化信息實(shí)時(shí)感知[1-3].無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由面向任務(wù)的大量分布式傳感器構(gòu)成的無線傳感網(wǎng)絡(luò)，以其低成本、低功耗突出優(yōu)點(diǎn)獲得廣泛應(yīng)用[4-6].無線傳感器網(wǎng)絡(luò)主要包括路由協(xié)議、節(jié)點(diǎn)定位、拓?fù)淇刂频然静糠諿7-8].實(shí)現(xiàn)目標(biāo)監(jiān)測(cè)和實(shí)時(shí)跟蹤的節(jié)點(diǎn)定位技術(shù)是傳感器網(wǎng)絡(luò)的核心技術(shù)，具有關(guān)鍵和基礎(chǔ)性的作用.在生物醫(yī)療、工農(nóng)業(yè)、軍事等領(lǐng)域有廣泛的應(yīng)用.位置信息獲取的一般辦法是采用GPS定位，但其成本高、功耗大，且衛(wèi)星信號(hào)在有建筑物遮擋地方不一定被傳感器網(wǎng)絡(luò)收到，在節(jié)點(diǎn)定位中存在困難.非測(cè)距定位質(zhì)心算法只需將定位設(shè)備安裝在少數(shù)節(jié)點(diǎn)上，通過這些相互連通的節(jié)點(diǎn)實(shí)現(xiàn)定位，具有環(huán)境抗干擾，硬件成本和能耗要求低的優(yōu)點(diǎn).但多邊定位方程的常態(tài)方程中傳統(tǒng)質(zhì)心算法使用權(quán)值相等的各組數(shù)據(jù)坐標(biāo)估計(jì)，無區(qū)別處理定位誤差大小不同情況，影響定位準(zhǔn)確性.對(duì)此，本文提出了改進(jìn)加權(quán)質(zhì)心算法的節(jié)點(diǎn)定位方法，權(quán)值使用常態(tài)方程代入解得坐標(biāo)后的誤差值倒數(shù)，改進(jìn)傳統(tǒng)質(zhì)心算法，準(zhǔn)確性不同的數(shù)據(jù)通過不同權(quán)值對(duì)應(yīng)不同的影響力，提高定位精度.通過在實(shí)際環(huán)境中利用傳統(tǒng)質(zhì)心定位算法和提出的加權(quán)質(zhì)心定位算法對(duì)未知節(jié)點(diǎn)進(jìn)行定位的實(shí)驗(yàn)表明，提出的加權(quán)質(zhì)心定位算法的定位精度有顯著提高.

1 質(zhì)心算法

基于非測(cè)距的質(zhì)心定位算法對(duì)已知參考節(jié)點(diǎn)坐標(biāo)值進(jìn)行中和計(jì)算，運(yùn)算簡(jiǎn)單，易于實(shí)現(xiàn)，其定位過程取決于節(jié)點(diǎn)的分布和密度.質(zhì)心定位利用節(jié)點(diǎn)在組網(wǎng)區(qū)域中的互通性[9]，基本原理為：參考節(jié)點(diǎn)向周圍定期廣播包含自身位置和ID信息的信號(hào)，當(dāng)未知節(jié)點(diǎn)在網(wǎng)絡(luò)中收到數(shù)量達(dá)到某預(yù)設(shè)門限K的信號(hào)個(gè)數(shù)時(shí)，待定位未知節(jié)點(diǎn)的估計(jì)坐標(biāo)就用這K個(gè)參考點(diǎn)組成的多邊形質(zhì)心表示.算法示意圖如圖1所示.

圖1 質(zhì)心算法示意圖

五邊形ABCDE的五個(gè)頂點(diǎn)坐標(biāo)分別表示為(x1，y1)、(x2，y2)、(x3，y3)、(x4，y4)、(x5，y5)，若這五個(gè)參考節(jié)點(diǎn)均在定位節(jié)點(diǎn)的通信范圍內(nèi)，這時(shí)五邊形的幾何質(zhì)心就是所求節(jié)點(diǎn)的估算位置(x，y)，其表達(dá)式為

(1)

傳統(tǒng)質(zhì)心算法的優(yōu)點(diǎn)是運(yùn)算簡(jiǎn)單，不需要進(jìn)行節(jié)點(diǎn)之間協(xié)調(diào)，便于實(shí)現(xiàn).在基于測(cè)距的傳統(tǒng)質(zhì)心定位算法中，由于隨機(jī)誤差等原因，單靠某一組數(shù)據(jù)的定位結(jié)果可能有較大誤差.所以一般是在基于n組數(shù)據(jù)的傳統(tǒng)質(zhì)心算法中，最后結(jié)果取n個(gè)估計(jì)位置的平均值，考慮到計(jì)算復(fù)雜度和通信開銷的狀況，n一般宜取3.傳統(tǒng)的質(zhì)心算法計(jì)算過程為

(2)

2 改進(jìn)加權(quán)質(zhì)心算法

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

(3)

(4)

式中：(xc，yc)為利用改進(jìn)加權(quán)質(zhì)心算法對(duì)三個(gè)估算坐標(biāo)確定的坐標(biāo)值；Wi為估計(jì)坐標(biāo)值的第i組數(shù)據(jù)的權(quán)值；Ai，bi為對(duì)應(yīng)于第i組數(shù)據(jù)確定的線性方程參數(shù)；norm(X)用來衡量解得坐標(biāo)的誤差，即X的二范數(shù)，其表達(dá)式為

(5)

在改進(jìn)的加權(quán)質(zhì)心算法中，利用權(quán)值差別處理具有不同定位誤差的不同定位結(jié)果，較小誤差的倒數(shù)對(duì)應(yīng)較大的權(quán)值，較大誤差的倒數(shù)對(duì)應(yīng)較小的權(quán)值，優(yōu)化了傳統(tǒng)質(zhì)心算法，提高了定位準(zhǔn)確性.

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中，隨機(jī)布置1個(gè)定位節(jié)點(diǎn)和7個(gè)參考節(jié)點(diǎn)，其位置坐標(biāo)如表1所示.利用多邊定位的極大似然估計(jì)法[10]隨機(jī)選取三組數(shù)據(jù)的坐標(biāo)值，采用傳統(tǒng)質(zhì)心算法和加權(quán)質(zhì)心算法二次處理求出三個(gè)坐標(biāo)更精確的解.

表1 節(jié)點(diǎn)位置

方程AX=b在每組數(shù)據(jù)點(diǎn)數(shù)為3時(shí)不能使用加權(quán)質(zhì)心算法，只能采用傳統(tǒng)質(zhì)心二次求解.方程AX=b在每組選取4、5、6個(gè)點(diǎn)時(shí)，利用傳統(tǒng)質(zhì)心算法和加權(quán)質(zhì)心算法分別計(jì)算三個(gè)坐標(biāo).由均方根誤差(RMSE)來評(píng)價(jià)定位算法的準(zhǔn)確性和精度.

表2為定位過程中的選點(diǎn)分布情況.表3為多邊定位的極大似然法估算分組數(shù)據(jù)坐標(biāo)值.利用傳統(tǒng)質(zhì)心算法和改進(jìn)加權(quán)質(zhì)心算法優(yōu)化估計(jì)的未知節(jié)點(diǎn)坐標(biāo)對(duì)數(shù)據(jù)進(jìn)行處理，兩種算法的定位結(jié)果如表4所示.

表2 選點(diǎn)分布

表3 各組數(shù)據(jù)的估計(jì)坐標(biāo)值

表4 定位結(jié)果

由表4定位結(jié)果可以看出，改進(jìn)加權(quán)質(zhì)心算法定位誤差小于傳統(tǒng)質(zhì)心算法的定位誤差，定位精度有顯著提高.

圖2為誤差與參考點(diǎn)個(gè)數(shù)的關(guān)系圖.從圖2中可以看出，誤差隨參考節(jié)點(diǎn)數(shù)的增加先減小后增大.當(dāng)參考節(jié)點(diǎn)數(shù)由3逐漸增大到5的過程中，定位誤差逐漸變小，但當(dāng)參考節(jié)點(diǎn)數(shù)由5逐漸變大到6或7時(shí)，定位誤差又逐漸增大，選擇5個(gè)參考節(jié)點(diǎn)時(shí)的定位誤差最小，綜合考慮節(jié)點(diǎn)成本和計(jì)算開銷等因素，參考節(jié)點(diǎn)個(gè)數(shù)最優(yōu)為5個(gè).

圖2 參考點(diǎn)個(gè)數(shù)與誤差關(guān)系

在通信范圍內(nèi)，從表1中的7個(gè)參考節(jié)點(diǎn)坐標(biāo)中任意選取5組，每組有5個(gè)不同參考節(jié)點(diǎn)，首先分別利用多邊定位算法得出未知節(jié)點(diǎn)坐標(biāo)，再利用傳統(tǒng)的質(zhì)心算法和改進(jìn)加權(quán)的質(zhì)心算法優(yōu)化未知節(jié)點(diǎn)坐標(biāo).圖3為兩種算法定位誤差對(duì)比圖.由圖3可以看出，加權(quán)質(zhì)心算法相較傳統(tǒng)的質(zhì)心算法顯著改善了定位誤差，提高了定位精度，定位準(zhǔn)確性改善尤為明顯.

圖3 傳統(tǒng)質(zhì)心和改進(jìn)加權(quán)質(zhì)心算法誤差對(duì)比

在上述五組隨機(jī)選取的通信范圍內(nèi)待測(cè)節(jié)點(diǎn)中，對(duì)應(yīng)于2、3組的定位數(shù)據(jù)，節(jié)點(diǎn)所在位置的橫縱坐標(biāo)值分別用坐標(biāo)軸中的x、y表示，其真實(shí)坐標(biāo)值分別為(9，5)和(6，6)，得到的定位坐標(biāo)結(jié)果如圖4所示.

圖4 坐標(biāo)定位結(jié)果

通過定位結(jié)果可以看出，改進(jìn)加權(quán)質(zhì)心算法的定位精度高于傳統(tǒng)質(zhì)心算法，更接近于真實(shí)值，改進(jìn)加權(quán)質(zhì)心算法差別處理具有不同誤差的數(shù)據(jù)，可以提高定位精度，從而優(yōu)化定位結(jié)果.圖5為采用普通質(zhì)心算法和加權(quán)質(zhì)心算法分別測(cè)試6組數(shù)據(jù)，每組5個(gè)節(jié)點(diǎn)的時(shí)間對(duì)比.從圖5中可以看出，加權(quán)質(zhì)心算法用時(shí)更少，效率更高.

4 結(jié) 論

由于無線傳感網(wǎng)絡(luò)中傳統(tǒng)質(zhì)心定位算法代入各組數(shù)據(jù)后定位精度較低，提出了改進(jìn)加權(quán)質(zhì)心算法的節(jié)點(diǎn)定位方法.權(quán)值使用常態(tài)方程代入解得坐標(biāo)后誤差值的倒數(shù)，準(zhǔn)確性不同的數(shù)據(jù)通過不同權(quán)值對(duì)應(yīng)不同的影響力，提高了定位精度.分別用傳統(tǒng)質(zhì)心算法和改進(jìn)加權(quán)質(zhì)心算法進(jìn)行MATLAB仿真，最終估測(cè)出定位節(jié)點(diǎn)的位置坐標(biāo).結(jié)果表明，改進(jìn)加權(quán)質(zhì)心算法使用坐標(biāo)解代入方程后誤差值的倒數(shù)為權(quán)值，相較傳統(tǒng)質(zhì)心算法定位誤差小，定位精度高.