基于質(zhì)心算法的室內(nèi)無線定位方法

朱 軍， 王吉平， 楊家豐， 姚 澤

(桂林電子科技大學(xué) 認(rèn)知無線電與信息處理省部共建教育部重點實驗室，廣西 桂林 541004)

目前室內(nèi)定位算法主要分成兩類：1)基于距離的算法(range-base)；2)無需測距離的算法(range-free)。基于Range-base的算法常用的測量技術(shù)有：接收信號強(qiáng)度估計(received signal strength indicator，簡稱RSSI)[1]，到達(dá)時差(time difference of arrival，簡稱TDOA)[2]，到達(dá)時間(time of arrival，簡稱TOA)[3]，到達(dá)角度(angle of arrival，簡稱AOA)[4]等，基于距離的算法精度非常高，在傳感器采集數(shù)據(jù)誤差較小情況下精度可達(dá)到厘米級。無需測距的算法通常利用無線傳感器網(wǎng)絡(luò)系統(tǒng)的連通性進(jìn)行目標(biāo)節(jié)點的位置估計，典型的算法有Dv-hop[5]、質(zhì)心算法[6]、近似三角形內(nèi)點測試法(approximate point-in-triangulation test，簡稱APIT)，基于Range-free的算法要獲得更高的精度，可通過改變參考節(jié)點分布密度或者改變盲節(jié)點通信半徑獲得。

針對影響質(zhì)心算法定位精度的問題，Huang等[8]提出通過對路徑損耗系數(shù)進(jìn)行分類，并利用歐氏距離判斷實際的RSSI值選擇相應(yīng)的路徑損耗類別。王恩良等[9]使用k-近鄰算法求解。谷廣等[10]提出一種改善參考節(jié)點分布不均勻時改進(jìn)型質(zhì)心定位算法，通過判斷檢測到的參考節(jié)點是否構(gòu)成三角形以及盲節(jié)點是否在三角形內(nèi)來決定使用何種算法來提高定位精度并且通信半徑越大誤差越小。李衛(wèi)東等[11]指出可以在3個參考節(jié)點的基礎(chǔ)上增加一個或者多個參考節(jié)點，再利用相交圓的2個交點的連線延長的交點求解盲節(jié)點坐標(biāo)。

基于文獻(xiàn)[10]，研究質(zhì)心定位算法的誤差率與通信半徑和參考節(jié)點分布密度之間的關(guān)系，找出一個三者之間的最優(yōu)點。

1 通信半徑和參考節(jié)點分布密度對定位精度的影響

1.1 信號傳輸模型

無線信號傳輸中普遍采用的理論模型為漸變模型[12]，

(1)

其中：d為盲節(jié)點到參考節(jié)點的距離；p(d)表示距離參考節(jié)點距離為d時，盲節(jié)點接收到的信號強(qiáng)度；p(d0)表示距離參考節(jié)點為d0時，盲節(jié)點接收到的信號強(qiáng)度，其中d0為參考距；n為路徑損耗系數(shù),該值隨著環(huán)境的復(fù)雜度而改變，一般障礙物越多，n取值越大，正常的范圍在2～6；X是一個服從正態(tài)分布的高斯隨機(jī)變量，單位為dBm。

實際工程應(yīng)用中一般采用簡化模型，

(2)

為了簡化計算過程，d0一般取1 m，并令p(d)為接收信號強(qiáng)度估計(received signal strength indicator,簡稱RSSI)，p(d0)=A，于是有：

IRSS=A-10nlg(d)，

(3)

A為盲節(jié)點距離參考節(jié)點1 m時，盲節(jié)點接收到信號強(qiáng)度值。

1.2 質(zhì)心算法原理

質(zhì)心算法的基本原理為：盲節(jié)點檢測到與其相互連通的參考節(jié)點，根據(jù)參考節(jié)點提供的位置信息估計自身位置。具體實現(xiàn)過程為：參考節(jié)點向四周周期性發(fā)送自身位置信息，盲節(jié)點根據(jù)接收到的不同參考節(jié)點發(fā)送的位置信息進(jìn)行自身位置估計。當(dāng)盲節(jié)點接收到的參考節(jié)點的個數(shù)或者信號強(qiáng)度達(dá)到一定閾值時，盲節(jié)點就記錄符合一定閾值參考節(jié)點位置坐標(biāo)，并利用這些參考節(jié)點所構(gòu)成的多邊形的質(zhì)心作為自身位置，如圖1所示。

圖1 質(zhì)心定位原理示意圖

假設(shè)盲節(jié)點F(x,y)接收到5個參考節(jié)點坐標(biāo)A～E，對應(yīng)的坐標(biāo)值為(xi,yi)，i=1,2,3,4,5。則盲節(jié)點F的估計坐標(biāo)為：

(4)

1.3 通信半徑對定位誤差的影響

理論猜想：當(dāng)盲節(jié)點的通信半徑增大后，同時也引入了新的參考節(jié)點，新的多邊形就會產(chǎn)生，從而得到新的質(zhì)心，那么這對定位誤差會產(chǎn)生什么樣的影響？

圖2是在100 m×100 m的區(qū)域內(nèi)隨機(jī)生成20個參考節(jié)點和一個實際節(jié)點，通過改變通信半徑為20、30 m獲得2個新的定位節(jié)點：d=20和d=30，仿真獲得的結(jié)果。

根據(jù)圖2可知，在一定的通信范圍內(nèi)，參考節(jié)點分布密度增大，絕對誤差存在減小和增大2種情況。結(jié)合圖1可知，就單個節(jié)點而言，參考節(jié)點分布密度對絕對誤差的影響不能一概而論，可能與其通信半徑和參考節(jié)點分布密度都有關(guān)系。

1.4 參考節(jié)點分布密度對定位誤差的影響

根據(jù)質(zhì)心算法的原理可知，在一定的通信范圍內(nèi)，盲節(jié)點周圍分布的參考節(jié)點密度會影響定位的結(jié)果，那么參考節(jié)點的分布密度具體是多少才可以獲得最小定位誤差?

圖3是在100 m×100 m的區(qū)域內(nèi)隨機(jī)產(chǎn)生20個參考節(jié)點和一個實際節(jié)點，通信距離為30 m，不引入新的參考節(jié)點時實際節(jié)點的定位結(jié)果為方形的節(jié)點，在實際節(jié)點通信范圍內(nèi)，引入3個菱形的參考節(jié)點后定位的結(jié)果為五角星形的節(jié)點。

根據(jù)圖3可知，在一定的通信范圍內(nèi)，參考節(jié)點分布密度增大，絕對誤差存在減小和增大2種情況。結(jié)合圖2可知，就單個節(jié)點而言，參考節(jié)點分布密度對絕對誤差的影響不能一概而論，可能與其通信半徑和參考節(jié)點分布密度都有關(guān)系。

圖2 盲節(jié)點通信半徑對絕對誤差的影響

圖3 參考節(jié)點分布密度對絕對誤差的影響

2 仿真與分析

根據(jù)第一節(jié)的分析可知，質(zhì)心算法的定位誤差與其通信半徑和參考節(jié)點分布密度均有關(guān)系，同時文獻(xiàn)[13]也指出，質(zhì)心算法的定位誤差與參考節(jié)點的分布存在一定關(guān)系，所以本次仿真不考慮參考節(jié)點的分布，減小由于隨機(jī)生成的參考節(jié)點分布位置不同而帶來的誤差影響，只考慮通信半徑和參考節(jié)點分布密度。

2.1 網(wǎng)絡(luò)部署

本次仿真在100 m×100 m的區(qū)域內(nèi)隨機(jī)生成20個盲節(jié)點，相鄰的參考節(jié)點分布成矩形分布，參考節(jié)點密度可以改變，通信距離也可以改變。參考節(jié)點密度主要通過改變Excel表格定義的橫縱坐標(biāo)實現(xiàn)，通信距離通過改變參考節(jié)點和盲節(jié)點之間的檢測距離的閾值d2實現(xiàn)，整個定位程序?qū)崿F(xiàn)流程如圖4所示。

圖4 定位程序流程圖

圖5 定位效果圖

圖5為定位效果圖。結(jié)合圖4和圖5可知，在一定的通信半徑下，當(dāng)參考節(jié)點之間的距離過大，盲節(jié)點可能出現(xiàn)無法定位的情況。

2.2 最佳通信半徑的仿真與分析

盲節(jié)點是隨機(jī)產(chǎn)生的，為了減少這一因素對算法的影響，首先在130 m×100 m區(qū)域內(nèi)隨機(jī)生成20個盲節(jié)點，固定盲節(jié)點檢測距離(距離為10 m至70 m，間隔為5 m，共13個不同的檢測距離)，在改變參考節(jié)點分布密度的情況下進(jìn)行仿真，將每組的仿真結(jié)果取平均值得到圖6。

圖6 盲節(jié)點通信半徑與誤差率的關(guān)系圖

從圖6可看出，誤差率隨通信半徑先減小后增加，仿真結(jié)果擬合的是一條二次曲線，在最低點的定位誤差率大約為0.230 8，與之對應(yīng)的通信半徑為41 m，即為最佳通信半徑。在此基礎(chǔ)上，該點對應(yīng)的就是一個較好的定位精度，且在該條件下需要的成本也相對較低。因此達(dá)到最佳通信半徑的要求后，所使用的方法能夠得到一個成本和定位誤差率的平衡點，也就是尋找最佳通信半徑所具有的實際意義。

2.3 通信半徑、參考節(jié)點分布密度與定位精度的關(guān)系

隨著盲節(jié)點的通信半徑變大，參考節(jié)點增多，平均誤差減少，但是隨著節(jié)點密度的增大，建設(shè)成本也增加，所以實際應(yīng)用中要綜合考慮成本和定位精度，需要選取一個合適的實際應(yīng)用方案。因此最后對通信半徑、參考節(jié)點分布密度和定位精度三者之間的關(guān)系進(jìn)行仿真。

使用與2.2節(jié)類似的方法，首先在130 m×100 m區(qū)域內(nèi)隨機(jī)生成20個盲節(jié)點，固定參考節(jié)點分布密度(均勻分布130、90、70、63、50、45、40、36、30、25、20、16、12個參考節(jié)點)，然后改變盲節(jié)點的通信半徑的情況下進(jìn)行仿真，最后將每組的仿真結(jié)果取平均值得到圖7。

圖7 參考節(jié)點分布密度與誤差率關(guān)系圖

從圖6和圖7可看出，參考節(jié)點的分布密度和盲節(jié)點的通信半徑之間存在一定的關(guān)系，可以用數(shù)學(xué)公式表達(dá)為

e=0.000 172 5×d2-0.014 18×d+0.522 2，

(5)

e=1.148×10-5×p2-0.002 967×p+0.389 4，

(6)

其中：e為誤差率；d為盲節(jié)點通信半徑；p為參考節(jié)點的分布密度。

利用式(5)和式(6)進(jìn)行仿真可得圖8所示，盲節(jié)點的通信半徑和參考節(jié)點分布密度與誤差率三者之間的關(guān)系。從圖8可知，盲節(jié)點的通信半徑為41 m，參考節(jié)點分布密度為41 個(分布區(qū)域130×100=13 000 m2)時，誤差率為最小0.232 4，即最小誤差距離為9.462 8 m。

圖8 盲節(jié)點通信半徑和參考節(jié)點分布密度與誤差率的關(guān)系

3 結(jié)束語

分析了盲節(jié)點的通信半徑和參考節(jié)點的分布密度對定位精度的影響，雖然提高參考節(jié)點的分布密度能夠有效提高定位精度，但在實際應(yīng)用過程中需要考慮成本問題，所以不能盲目增加參考節(jié)點密度，因此最終基于質(zhì)心算法的定位精度與成本的問題，將定位誤差率分別與盲節(jié)點的通信半徑和參考節(jié)點的分布密度之間的關(guān)系進(jìn)行仿真，再擬合出三者關(guān)系的曲線，并且找到了一個平衡三者關(guān)系的最優(yōu)點。該點的存在為室內(nèi)定位領(lǐng)域提供了非常重要的參考價值。

該研究雖然在經(jīng)典質(zhì)心算法的基礎(chǔ)上達(dá)到了預(yù)期的目的，但參考節(jié)點的分布仍會對定位誤差產(chǎn)生較大的影響，所以今后研究的重點方向是找到參考節(jié)點最合理的分布方法。