一種基于概率模型的改進Scout無線定位算法

吳小軍，趙東明，徐 進

（武漢理工大學(xué) 自動化學(xué)院 自動化系，武漢 430070）

當(dāng)前，無線定位算法已經(jīng)成為一個重要的研究方向和熱點問題.典型的定位算法可分為兩大類：基于距離的（Range－based）定位算法［1］和與距離無關(guān)的（Range－free）定位算法［2］.Range－based定位使用三邊測量法、三角測量法或最大似然估計法，即通過測量節(jié)點間的距離或角度信息來計算未知節(jié)點的位置；Range－Free定位則無需距離和角度信息，僅根據(jù)網(wǎng)絡(luò)連通性等信息即可實現(xiàn)，常用的Range－Free定位算法有DV－Hop算法、APIT算法［3］、質(zhì)心算法等.與距離無關(guān)的定位算法對節(jié)點的硬件結(jié)構(gòu)要求較低，但是其定位精度不高，很難滿足室內(nèi)定位精度的要求.常用的測距技術(shù)有RSSI、TOA、TDOA 和AOA［4］等，其中由于RSSI測距借助的硬件設(shè)備少，而且許多無線通信模塊都可以直接提供RSSI值，因此，基于RSSI的測距方法被廣泛應(yīng)用.

反射、多徑傳播、非視距、天線增益等問題都會對相同距離產(chǎn)生顯著的傳播損耗.通常將RSSI測距看作為一種粗略的測距技術(shù)，如何能夠提高基于RSSI的定位精度是一個比較有意義的問題.目前，應(yīng)用于室內(nèi)無線定位的算法有很多，比如：基于RSSI差分修正的加權(quán)質(zhì)心定位算法［5］，基于RSSI測距的差分修正定位算法［6］，基于RSSI的三角形質(zhì)心定位算法［7］，基于RSSI的無線傳感器網(wǎng)絡(luò)距離修正定位算法［8］等，文獻［9］提出了一種基于概率模型的Scout定位算法，該算法借助于參考標(biāo)簽對其相應(yīng)的讀卡器進行參數(shù)修正，利用一個概率模型來描述標(biāo)簽與讀卡器之間的距離和標(biāo)簽接收到的信號強度的關(guān)系，最后通過貝葉斯推理［10］確定目標(biāo)的定位區(qū)域，該算法定位精度較高，但是由于需要一定數(shù)量的參考標(biāo)簽，硬件成本較高，為了解決這一問題，本文在Scout定位算法的基礎(chǔ)上進行改進，提出了一種基于概率模型的改進Scout算法.

1 算法模型描述

1.1 Scout定位算法

Scout算法基于RSSI對跟蹤目標(biāo)進行定位.在算法執(zhí)行過程中，借助分布于現(xiàn)場的參考標(biāo)簽對各傳輸參數(shù)進行實時修正，利用一個概率模型來描述標(biāo)簽與讀卡器之間的距離和標(biāo)簽接收到的信號強度的關(guān)系，最后通過貝葉斯推理確定目標(biāo)的定位區(qū)域.

Scout算法定位需要n（n≥4）個信號讀取設(shè)備（讀卡器），與之對應(yīng)n（n≥4）個已知位置的參考標(biāo)簽，至少一個服務(wù)器，以及要追蹤的目標(biāo)節(jié)點標(biāo)簽若干個.讀卡器用于判斷各個標(biāo)簽的RSSI值并傳送給服務(wù)器進行處理，參考標(biāo)簽用于校正參數(shù).

該算法是通過利用已知的參考標(biāo)簽參與校正，在每次定位算法執(zhí)行的過程中，通過更新傳輸損耗和路徑損耗進行校正.在算法執(zhí)行的過程中RSSI與各個參數(shù)的關(guān)系如下.

其中，a為傳輸損耗，n為路徑損耗，每次測算之前需要進行重新計算以防止在不同測試情況下產(chǎn)生誤差.所以該算法的核心部分在于參考標(biāo)簽的參數(shù)修正部分，需要準(zhǔn)確求出每個讀卡器相應(yīng)的傳輸損耗a和路徑損耗n.

1.2 Scout定位算法的改進

本文提出的定位算法在Scout算法的基礎(chǔ)上作出了改進，該算法定位需要n（n≥4）個讀卡器，不需要在讀卡器附近設(shè)置參考標(biāo)簽，經(jīng)過算法修正后，讀卡器可以當(dāng)參考標(biāo)簽使用，這樣一來，該定位系統(tǒng)設(shè)備（n＝4時）只需要4個讀卡器就夠了，傳統(tǒng)的Scout算法需要8個節(jié)點，對于整個定位系統(tǒng)而言，本文提出的定位算法大大降低了硬件成本.改進前與改進后的定位節(jié)點布局如圖1所示.

如圖1（b）所示，在求算讀卡器1 相對應(yīng)的a和n時，根據(jù)公式（1）可知，我們只需聯(lián)立不同距離得到的信號RSSI值便可以解得a和n，如下公式（2）.由（d1，d2）求得a1、n1；由（d1，d3）求得a2、n2；由（d2，d3）求得a3、n3；然后求a1、a2、a3的平均值得a；求n1、n2、n3的平均值得n.得到信號RSSI值的時候，可以代入概率公式（3）求概率的大小.以上公式可以把信號的強弱看做一個概率事件，即無論兩點間的距離是多少，其某一次產(chǎn)生的信號可大可小，只是概率大小的區(qū)別.對于一個有限的區(qū)域，遍歷各個位置到讀卡器的距離d發(fā)出RSSI的概率，取最大的概率對應(yīng)的d.

圖1 Scout算法改進前與改進后的定位節(jié)點布局圖Fig.1 Node layout of Scout positioning algorithm and improred Scout positioning algorithm

各個點的概率歸一化后取P＞0.999 9后得到的最大概率點分布圖如圖2所示.

最后把對某一點上到各個讀卡器的概率相乘得到目標(biāo)位于該點的最終概率，從中選取最大的概率，通過計算得到目標(biāo)點的位置.

圖2 最大概率點分圖布Fig.2 Point of maximum probability distribution

2 算法的執(zhí)行步驟

圖3 算法流程圖Fig.3 Algorithm flowchart

（1）初始化可信度向量Bel（x0）

其中，x0表示跟蹤目標(biāo)的初始狀態(tài)，即目標(biāo)在探測區(qū)域中的初始位置；算法將整個探測區(qū)域劃分為N個子區(qū)域，Bel（x0）表示在初始時刻目標(biāo)位于各子區(qū)域的可能性.

（2）決定基本的探測范圍

圖4 觀測一個目標(biāo)點Fig.4 Observing a target point

（3）修正傳輸參數(shù)

（4）重新計算可信度向量Bel（xt）

（5）如果迭代次數(shù)小于預(yù)定的迭代次數(shù)，則移動到下一個網(wǎng)絡(luò)，并且返回到第2步.否則結(jié)束步驟4中的迭代過程，確定定位區(qū)域.

Bel＇（xt）稱為相對可信度向量，將向量中數(shù)值大于或等于閥值概率的元素所對應(yīng)的子區(qū)域列入最終的定位區(qū)域；C（gxk，gyk）表示整個探測區(qū)域中的第k個子區(qū)域；子區(qū)域又被稱為網(wǎng)格，一個網(wǎng)格由位于網(wǎng)格中心的一個點來表示，gxk，gyk表示第k個網(wǎng)格的中心點的橫縱坐標(biāo)，Bel（xt＝C（gxk，gyk）表示目標(biāo)在t時刻位于第k個網(wǎng)格的概率.

（6）確定定位點

每一次迭代都確定了相應(yīng)的定位區(qū)域，所有的迭代結(jié)束后，求取以上列出的各定位區(qū)域所對應(yīng)的概率的平均值，概率的平均值所對應(yīng)的點即是最終的定位點.

3 仿真結(jié)果

在Matlab平臺上分別對Scout算法和改進后的算法進行仿真，仿真條件是在一個10m×10m的正方形區(qū)域內(nèi)，傳播路徑損耗模型選擇經(jīng)典的自由空間模型和對數(shù)－常態(tài)模型.在該區(qū)域放置4個讀卡器，其坐標(biāo)自己設(shè)定，對Scout算法仿真時，在各讀卡器附近固定位置增加參考標(biāo)簽節(jié)點，對改進后的算法仿真時不需要參考標(biāo)簽.未知目標(biāo)節(jié)點的坐標(biāo)由Matlab隨機生成函數(shù)來生成，在該區(qū)域內(nèi)隨機分布，一共生成10 個未知目標(biāo)節(jié)點.然后根據(jù)RSSI與距離的關(guān)系生成RSSI數(shù)據(jù)，并在數(shù)據(jù)中添加均值為0、標(biāo)準(zhǔn)差σ為3 的高斯噪聲作為RSSI的隨機分量，以模擬實際環(huán)境中的反射、多徑、物體遮擋、氣候等帶來的影響.路徑損耗系數(shù)n取4，通過自由空間傳播模型和對數(shù)－常態(tài)分布模型，按照上述的算法步驟來對上述兩種算法進行仿真定位.對于這兩種算法，列出了迭代次數(shù)r＝10時的仿真圖.圖5和圖6是算法的Matlab仿真結(jié)果圖.

圖5 Scout算法仿真圖Fig.5 Simulation diagram of Scout algorithm

圖6 Scout算法改進后仿真圖Fig.6 Simulation diagram of improved Scout algorithm

從圖6可以看出，兩種算法定位的精度都很高，Scout算法定位需要八個定位節(jié)點，而改進后的算法只需要四個定位節(jié)點就能達到Scout算法的定位精度.

4 結(jié)論

基于概率模型的改進Scout無線定位算法，通過改進算法將定位節(jié)點減少一半，降低了定位系統(tǒng)的硬件成本，而由于改進后的算法的定位核心思想仍同于Scout定位算法，因此，基于概率模型的改進Scout無線定位算法在減少參考節(jié)點數(shù)量的情況下定位精度相比Scout定位算法并沒有降低.

5 展望

基于概率模型的改進Scout無線定位算法也存在不足，定位節(jié)點數(shù)的減少是通過改進算法來實現(xiàn)的，如果定位區(qū)域較大，需要的讀卡器數(shù)量較多時，各個讀卡器之間的關(guān)系變得復(fù)雜了，通過改進算法來減少定位節(jié)點的難度將很大，要解決這一問題還需要進一步優(yōu)化算法或者更新定位算法的思路.

［1］王 琦.基于RSSI測距的室內(nèi)定位技術(shù)［J］.電子科技，2012，25（6）：64－66.

［2］李建中，高 宏.無線傳感器網(wǎng)絡(luò)的研究進展［J］.計算機研究與發(fā)展，2008，45（1）：1－15.

［3］Sayed A，Tarighat A，Khajehnouri N.Networkbased wireless location［J］.IEEE Signal Processing Mag，2005，22（4）：24－40.

［4］Ni L M，Liu Y，Cho Y，ea al.LANDMARC：indoor loca－tion sensing using active RFID［C］／／Proceedings of the First IEEE International Conference on Pervasive Computing and Communications（PerCom 2003），2003（3）：23－26.

［5］花 超，吉小軍，蔡 萍.基于RSSI差分修正的加權(quán)質(zhì)心定位算法［J］.傳感器與微系統(tǒng)，2012，31（5）：139－144.

［6］任維政，徐連明，鄧中亮.基于RSSI測距的差分修正定位算法［J］.傳感技術(shù)學(xué)報，2008，21（7）：1247－1250.

［7］林 瑋，陳傳峰.基于RSSI的無線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法［J］.現(xiàn)代電子技術(shù)，2009，289：180－182.

［8］陳昌祥，達 維，周 潔.基于RSSI的無線傳感器網(wǎng)絡(luò)距離修正定位算法［J］.通信技術(shù)，2011，44（2）：65－69.

［9］Girod L，Estrin D.Robust range estimation using acoustic and muhimodal sensing［EB／OL］.http：／／www.rfcode.com／data＿sheets／mantis.pdf.

［10］Roos T，Myllymaki P，Tirri H，et al.A probabilistic approach to WLAN user location estimation［J］.International Journal of Wireless Information Networks，2002，9（3）：17－18.