協(xié)作室內(nèi)定位優(yōu)化算法

石 瑩, 趙梗明

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院, 上海 200234)

無(wú)線網(wǎng)絡(luò)技術(shù)的發(fā)展和覆蓋率的增加,使得人們?cè)陔S時(shí)隨地使用無(wú)線網(wǎng)絡(luò)資源時(shí),對(duì)自身位置信息的需求量不斷提高.尤其在室內(nèi)環(huán)境下,能夠快速準(zhǔn)確地獲得移動(dòng)終端的位置信息變得日益迫切.與此同時(shí),協(xié)作移動(dòng)定位已經(jīng)開始逐漸步入新型無(wú)線定位方式的行列,隨著無(wú)線通信技術(shù)的發(fā)展和處理數(shù)據(jù)能力的不斷增強(qiáng),對(duì)于精確位置信息方面的科學(xué)技術(shù)領(lǐng)域也成為十分具有潛力的實(shí)驗(yàn)課題和研究方向.

針對(duì)于無(wú)線室內(nèi)定位誤差過(guò)大的問(wèn)題,本文作者利用協(xié)作的思想,進(jìn)行優(yōu)化算法設(shè)計(jì).通過(guò)仿真實(shí)驗(yàn)驗(yàn)證,所設(shè)計(jì)的優(yōu)化算法相對(duì)于傳統(tǒng)的三角質(zhì)心定位,可以減小它的定位誤差,從而達(dá)到提高位置估算精確度的目的.

1 傳統(tǒng)三角質(zhì)心定位法

三角質(zhì)心法是在定位算法中利用率較高的一類定位算法.由于在實(shí)際情況中環(huán)境內(nèi)的各種干擾,使得到達(dá)待測(cè)節(jié)點(diǎn)的RSSI值小于理論上的RSSI值,這也就使得理論模型中的3個(gè)圓的半徑過(guò)大,從而出現(xiàn)3個(gè)圓的交集域[1-3],如圖1所示.

在這個(gè)交集域中,分別設(shè)3個(gè)頂點(diǎn)為E、F、G,則三角質(zhì)心算法的思想是,以△EFG的質(zhì)心定義為待測(cè)節(jié)點(diǎn)的位置.由此建立方程組,如式(1),分別聯(lián)立方程組1和方程組2,可以求得以A為圓心和以B為圓心的2個(gè)圓的2個(gè)交點(diǎn)坐標(biāo),這時(shí)需要判斷哪個(gè)交點(diǎn)距離點(diǎn)C更近,則定義為G點(diǎn)(選擇保留),另外一個(gè)舍棄.同理,計(jì)算出E、F點(diǎn)的坐標(biāo)值.

(1)

另外一點(diǎn)值得注意的是,當(dāng)以A、B、C三點(diǎn)為圓心,以三點(diǎn)到待測(cè)節(jié)點(diǎn)的距離為半徑的3個(gè)圓(如圖2)沒(méi)有交點(diǎn)時(shí),則表示這組數(shù)據(jù)無(wú)法通過(guò)三角質(zhì)心算法計(jì)算待測(cè)節(jié)點(diǎn)坐標(biāo),應(yīng)給予舍棄處理[4-5].

圖1 三角質(zhì)心法

圖2 3個(gè)圓不相交的情況

2 協(xié)作通信

在協(xié)作無(wú)線通信中,主要考慮節(jié)點(diǎn)之間通過(guò)協(xié)作的方式增加定位精度.在一個(gè)協(xié)作通信系統(tǒng)中,需要每一個(gè)節(jié)點(diǎn)都可以傳輸數(shù)據(jù)并可以作為其他節(jié)點(diǎn)的協(xié)作代理.

協(xié)作通信可以使代碼率增加而傳輸功率降低.對(duì)于傳輸功率的降低,有兩方面原因.一方面是因?yàn)閰f(xié)作通信不僅僅是2個(gè)節(jié)點(diǎn)時(shí)間的傳遞信息,而是所有節(jié)點(diǎn)同時(shí)傳輸數(shù)據(jù);另一方面是因?yàn)榉旨挠欣蛩?使得所有節(jié)點(diǎn)的底層傳輸功率降低.若假設(shè)系統(tǒng)中所有的參數(shù)恒定不變,那么降低傳輸功率是有利的.

同樣,從系統(tǒng)運(yùn)行速率上看,協(xié)作通信會(huì)使系統(tǒng)率降低,而信道代碼率升高.這是由于在一個(gè)協(xié)作通信系統(tǒng)中,每一個(gè)節(jié)點(diǎn)為其他節(jié)點(diǎn)發(fā)射自身相關(guān)信息,這樣就會(huì)到導(dǎo)致系統(tǒng)率降低.同時(shí),協(xié)作分集的有利影響使得每個(gè)節(jié)點(diǎn)的頻譜效率增加,這也導(dǎo)致了信道代碼的提高[6].

待測(cè)節(jié)點(diǎn)-已知節(jié)點(diǎn)鏈路和待測(cè)節(jié)點(diǎn)-待測(cè)節(jié)點(diǎn)鏈路中的RSS數(shù)據(jù)都可以運(yùn)用在協(xié)作定位過(guò)程當(dāng)中.假設(shè)待測(cè)節(jié)點(diǎn)M的坐標(biāo)為{X(i)=[x(i),y(i)]T,i=1,…,nm},而已知節(jié)點(diǎn)S的坐標(biāo)為{X(j)=[x(j),y(j)]T,j=1,…,ns}.Soork等人提出的最小二乘目標(biāo)函數(shù)[7],如式(2)所示:

(2)

式(2)中,p(i)[j],α(i)[j],d(i)[j]是Mi～Sj之間的接收功率,α參數(shù)和距離;p(i)(m),α(i)(m),d(i)(m)是Mi～Mm之間的接收功率,α參數(shù)和距離.通過(guò)公式(2)計(jì)算出J(X)的最適應(yīng)點(diǎn),并給出了所有待測(cè)節(jié)點(diǎn)的位置估計(jì).

3 基于協(xié)作的室內(nèi)定位優(yōu)化算法設(shè)計(jì)

本設(shè)計(jì)的主要思想為:利用協(xié)作定位的方法,不僅對(duì)已知節(jié)點(diǎn)與待測(cè)節(jié)點(diǎn)之間傳遞信號(hào)進(jìn)行測(cè)量,而且對(duì)待測(cè)節(jié)點(diǎn)之間傳遞的無(wú)線信號(hào)也進(jìn)行測(cè)量,從而獲得更好的定位精度及魯棒性.當(dāng)所有關(guān)于已知節(jié)點(diǎn)和待測(cè)節(jié)點(diǎn)的自身信息與相對(duì)信息均傳遞到PC機(jī)后,PC機(jī)立刻估算出待測(cè)節(jié)點(diǎn)的“絕對(duì)”位置.

根據(jù)傳統(tǒng)三角質(zhì)心算法獲得M1,M2坐標(biāo)分別為(X1,Y1),(X2,Y2),計(jì)算M1,M2間的距離d1.通過(guò)M1,M2之間的RSSI值,根據(jù)自由空間路徑損耗模型計(jì)算得出距離d.

RSSI=Pr(d0)-10n×lg(d/d0)+Xσ,

(3)

(4)

則可求得Δd:

Δd=|d-d1| .

(5)

此時(shí),設(shè)計(jì)兩種基于協(xié)作思想的,針對(duì)于未知節(jié)點(diǎn)為兩種的定位優(yōu)化算法.此兩種優(yōu)化算法均是在d(利用通過(guò)傳統(tǒng)質(zhì)心定位算法求得的兩點(diǎn)距離)的基礎(chǔ)上,根據(jù)d1(兩點(diǎn)之間RSSI值求得的兩點(diǎn)距離)進(jìn)行坐標(biāo)優(yōu)化定位.

圖3 圓域型優(yōu)化算法的圖示(兩個(gè)待測(cè)點(diǎn))

(6)

(7)

M={(x1,y1),(x2,y2)|min|(x1-x2)2+(y1-y2)2-d|},

(8)

(9)

4 仿真實(shí)驗(yàn)

4.1 圖象分析

為了簡(jiǎn)單直觀地看出定位優(yōu)化的結(jié)果,現(xiàn)將通過(guò)傳統(tǒng)三角質(zhì)心法、直線型優(yōu)化算法、圓域型優(yōu)化算法3種方法分別定位5次的仿真誤差進(jìn)行比較,如圖4所示.

圖4 定位誤差比較

從圖4中可以看出:

(1) 經(jīng)過(guò)與圓域型優(yōu)化算法相結(jié)合后,在大部分情況下,優(yōu)化后的定位均可達(dá)到定位誤差減小的目的;

(2) 在優(yōu)化結(jié)果上看,與圓域型優(yōu)化算法相結(jié)合后,定位誤差被優(yōu)化程度不定.

4.2 數(shù)據(jù)分析

分別列舉出利用傳統(tǒng)三角質(zhì)心法和三角質(zhì)心算法與圓域型優(yōu)化算法相結(jié)合的優(yōu)化定位算法定位20次的誤差進(jìn)行比較,如表1所示.

表1 誤差對(duì)比

從誤差數(shù)據(jù)中,可以計(jì)算出以下對(duì)比數(shù)據(jù)(以下數(shù)據(jù)均由此20組數(shù)據(jù)得出),如表2所示.分析可得：

表2 誤差分析數(shù)據(jù)對(duì)比

(1) 圓域型定位優(yōu)化算法在實(shí)際定位優(yōu)化中,確實(shí)可以減少定位誤差.可以得出:經(jīng)過(guò)圓域型優(yōu)化算法優(yōu)化后的三角質(zhì)心定位算法相對(duì)于傳統(tǒng)三角質(zhì)心算法的定位精度約提高11.62%.

(2) 經(jīng)過(guò)優(yōu)化后的定位算法在優(yōu)化最大值與優(yōu)化最小值方面的誤差數(shù)據(jù),經(jīng)計(jì)算,獲得一些數(shù)據(jù)結(jié)論.

在優(yōu)化誤差最大值方面:圓域型優(yōu)化算法相對(duì)于傳統(tǒng)三角質(zhì)心算法,誤差約減小7.74%.

在優(yōu)化誤差最小值方面:圓域型優(yōu)化算法相對(duì)于傳統(tǒng)三角質(zhì)心算法,誤差約減小22.66%.

從此數(shù)據(jù)中看出經(jīng)過(guò)優(yōu)化后的定位算法相對(duì)于傳統(tǒng)定位算法在定位誤差范圍上也有一定的優(yōu)化效果,特別在誤差最小值方面效果更為突出,優(yōu)化誤差程度可在原來(lái)誤差基礎(chǔ)的1/5以上.

(3) 為了進(jìn)一步說(shuō)明優(yōu)化后的定位算法在定位優(yōu)化上的作用,分別列出這20組實(shí)驗(yàn)數(shù)據(jù)與傳統(tǒng)三角質(zhì)心定位算法相比較的優(yōu)化程度(即提高精確度),如圖5所示.

圖5 優(yōu)化程度折線圖(20次實(shí)驗(yàn))

其中優(yōu)化程度最大的一組為第3組,優(yōu)化程度為28.63%.優(yōu)化程度最小的一組為第10組,優(yōu)化程度為0.05%.在這20組實(shí)驗(yàn)中,與圓域型優(yōu)化算法相結(jié)合后定位算法在定位方面表現(xiàn)出良好的優(yōu)化定位效果,而且值得注意的是這種優(yōu)化算法使得每次的定位誤差都會(huì)產(chǎn)生不同程度上的優(yōu)化效果.

5 結(jié)束語(yǔ)

本文作者對(duì)原有的三角質(zhì)心室內(nèi)定位算法進(jìn)行改進(jìn),利用協(xié)作定位的思想,通過(guò)未知節(jié)點(diǎn)與未知節(jié)點(diǎn)的通信再次對(duì)定位的坐標(biāo)進(jìn)行優(yōu)化.考慮到定位誤差的優(yōu)化方式問(wèn)題,將優(yōu)化方式與定位信息相結(jié)合進(jìn)行優(yōu)化.通過(guò)仿真實(shí)驗(yàn)證明,定位優(yōu)化算法可以在平均誤差方面、誤差范圍方面、優(yōu)化程度方面都有顯著的效果.在未來(lái)的優(yōu)化算法研究中,可以考慮將遺傳算法應(yīng)用到圓域定位優(yōu)化算法中,使定位達(dá)到更加精確的效果.

參考文獻(xiàn):

[1] 林瑋,陳傳峰.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法[J].現(xiàn)代電子技術(shù),2009(2):180-182.

[2] 朱劍.基于RSSI均值的等邊三角形定位算法[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2007,28(8):1094-1097.

[3] 張興會(huì),張志輝,鄧志東.基于RSSI測(cè)距技術(shù)的三角形面積和定位算法[J].電子測(cè)量技術(shù),2008,31(11):92-98.

[4] 鄧宏彬.一種基于無(wú)線傳感器網(wǎng)絡(luò)的星球漫游機(jī)器人定位算法[J].機(jī)器人,2007,29(4):384-388.

[5] 張興會(huì),鄧志東.基于無(wú)線傳感器網(wǎng)絡(luò)的地下礦工定位算法[J].計(jì)算機(jī)測(cè)量與控制,2008,16(12):2003-2005

[6] NOSRATINIA A,HUNTER T E, HEDAYAT A.Cooperative communication in wireless networks[J].IEEE Communications Magazine,2004,42(10):74-80.

[7] SOORK A S,SAADAT R, TADAION A A.Cooperative mobile positioning based on received signal strength[C]∥International Symposium on Telecommunications 2008(IST 2008).Tehran:IEEE,2008.