基于進化理論的無線網絡室內定位算法*

孫中廷， 華 鋼， 黃金城

(1.中國礦業大學 信息與電氣工程學院，江蘇 徐州 221008；2.江蘇聯合職業技術學院 徐州機電工程分院，江蘇 徐州 221011；3.鹽城工學院 信息工程學院，江蘇 鹽城 224051)

0 引 言

相對于室外環境，室內環境更加復雜，信號傳播易受到人員、墻體以及其它障礙物的阻擋，定位難度增加，因此,提高室內定位精度一直是無線定位技術研究的熱點[1]。

根據定位原理，無線室內定位算法主要分為兩類：時間測距定位和接收信號強度指示(received signal strength indication，RSSI)[2]定位。基于時間測距的定位方法主要包括：信號到達時間(time of arrival，TOA)定位、信號到達時間差(time difference of arrival，TDOA)定位等[3～5]。基于TOA定位算法存在對噪聲敏感、多路徑反射以及參考時鐘不精確等缺陷,距離估計誤差大；基于TDOA定位要求各設備間同步，但是由于室內距離有限，導致測得距離誤差較大。相對于時間測距定位算法，基于RSSI的定位算法不需要添加額外的硬件設備，很容易將定位系統的應用范圍擴大到樓群和室內，現已成為當前室內定位的主要研究方向[6]。RSSI定位通過對數路徑損耗模型來計算相對距離，然而，復雜的室內條件給模型參數帶來干擾，參數通常根據經驗獲得，這給定位精度帶來了不利影響[7]。

為了提高室內節點定位的精度，本文提出一種基于進化理論的無線網絡室內定位算法，仿真結果表明：本文算法提高了室內的定位精度，可以將定位誤差控制在實際應用的有效圍內。

1 傳統無線室內定位算法

1.1 RSSI定位路徑損耗模型

大量研究結果表明，信道的長距離衰落特性服從對數正態分布，常用對數距離路徑損耗模型可以描述實際環境，RSSI定位路徑損耗模型為

(1)

其中，n為路徑損耗指數；d為發射與接收節點間的距離；d0為參考距離；Xσ為隨機變量；PL(d0)為距離為d0時的路徑損耗[8]。

接收節點的RSSI為

RSSI=Pt-PL(d),

(2)

式中PL(d)為經過距離d后的路徑損耗；Pt為信號的發射功率。

因此，距離發射節點d0處的參考點接收信號強度A為A=Pt-PL(d0)，那么

PL(d0)=Pt-A.

(3)

把式(3)代人式(1)得到

(4)

參考距離通常d0=1，這樣可以得到

RSSI=A-10nlgd-Xσ.

(5)

(6)

那么發射節點與接收節點間的距離d為

(7)

1.2 三邊定位算法

根據式(7)計算待定位點到3個訪問接入點(access point，AP)的距離，然后以已知位置的3個AP為圓心，以其各自到待定位點的距離為半徑做圓，所得3個圓的交點，即待定位點的位置，三邊定位法示意圖如圖1所示。

圖1 三邊定位法示意圖

2 基于進化理論的室內定位算法

2.1 定位原理

在室內定位過程中，定位精度與參數A和n取值密切相關，同時A和n值與無線信號傳輸環境密切相關，如受到人員走動影響，A和n值具有時變性，然而目前A和n值的獲取方法為：在定位之前，首先進行大量的實驗測量，根據RSSI與距離的函數關系進行擬合，然后將其固定的作為該環境參數，這樣一旦環境發生改變，誤差相當大。

為了提高室內定位精度，本文利用基于進化理論的遺傳算法對參數A和n的值進行優化，以獲得更加理想的定位結果，基于進化理論的室內定位算法的原理如圖2所示。

圖2 進化理論的無線網絡室內定位原理

2.2 遺傳算法估計路徑損耗模型參數

遺傳算法是一種基于進化理論的群智能算法，通過模擬自然界“適者生存、優勝劣汰”進化過程找到問題的最優解，為此，本文將遺傳算法用于路徑損耗模型參數的估計，以提高無線網絡的室內定位精度。

2.2.1 個體編碼方式

由于待估計參數為A，n，因此,個體包括A，n兩部分，個體編碼方式具體如圖3所示。

圖3 個體的編碼方式

2.2.2 種群初始化

在一定的環境下，參數A，n的值在一定范圍內變化，設A～[m,n],[p,q]，就可以將A，n分成k等分，然后通過各種組合產生初始群體R0。

2.2.3 適應度函數設計

個體的優劣采用適應度函數進行衡量，在種群進化過程，適應度函數指導其進化方向，參數估計主要目的是減少RSSI的估計誤差，因此,適應度函數的計算公式為

(8)

2.2.4 遺傳算法估計路徑損耗模型參數的流程

基于遺傳算法估計路徑損耗模型參數的工作流程如圖4所示。

圖4 遺傳算法估計路徑損耗模型參數的流程

3 仿真實驗

3.1 仿真環境

為了測試本文算法的性能，實驗場景為10 m×40 m的室內區域，在4個頂點部署4個AP節點，中間放置2個AP節點。

3.2 結果與分析

3.2.1 模型參數估計

圖5為本文算法對一個節點RSSI值的擬合曲線，結果表明，采用基于進化理論的遺傳算法可以對參數A，n變的值進行準確估計，從而提高對數模型的擬合精度。

圖5 RSSI值的擬合結果

3.2.2 遺傳算法估計路徑損耗模型參數對定位結果影響

為了測試遺傳算法估計路徑損耗模型參數對定位結果影響，采用經驗參數確定方法進行對比實驗，待定位節點在室內進行隨機移動，并不斷測量AP節點發送來的信號強度信息，它們待定位點的位置如圖6所示。

圖6 兩種算法的節點定位軌跡

3.2.3 與當前經典室內定位算法的性能對比

為了使本文的結果更具說服務，選擇文獻[9,10]的經典無線網絡室內定位算法進行對比實驗，它們的定位結果如表1所示。從表1可知，本文算法的定位誤差遠遠小于對比算法的定位誤差。

表1 不同無線網絡室內定位算法的性能比較

4 結 論

為了提高室內節點定位的精度，本文提出一種基于進化理論的無線網絡室內定位算法。首先基于進化理論的遺傳算法找到路徑損耗模型的最優參數，然后采用三邊形定位算法對目標進行定位，最后通過仿真實驗測試其性能。仿真結果表明：本文方法是一種定位精度高、魯棒性強的室內定位方法，定位結果可靠、實際應用價值高。

參考文獻:

[1] Gu Y Y,Lo A,Niemegeers I.A survey of indoor positioning systems for wireless personal networks[J].IEEE Communications Surveys & Tutorials,2009,11(1):13-32.

[2] Kushki A,Plataniotis K N,Venetsanopoulos A N.Kernel-based positioning in wireless local area networks[J].IEEE Transactions on Mobile Computing,2007,6(6):689-695.

[3] Kushki A,Plataniotis K,Venetsanopoulos A.Intelligent dynamic radio tracking in indoor wireless local area networks[J].IEEE Transactions on Mobile Computing,2010,9(3):405-419.

[4] 陸保國,袁 杰.無線傳感器網絡的室內空間定位算法[J].計算機工程,2011,37(14):97-99.

[5] 劉 健,沈海斌.無線傳感器網絡的室內研究[J].傳感器與微系統,2013,32(9):66-68.

[6] 彭建盛,李 興,秦志強.室內立體空間定位算法的研究與實現[J].傳感器與微系統,2012,31(7):33-35.

[7] 陳 群,高星偉.一種基于RSSI的室內加權質心定位算法[J].測繪科學,2013,38(4):91-93.

[8] 倪 巍,王宗欣.基于接收信號強度測量的室內定位算法[J].復旦學報:自然科學版,2004,43(1):72-76.

[9] 劉召偉,徐鳳燕,王宗欣.基于參數擬合的室內多用戶定位算法[J].電波科學學報,2009,23(6):1090-1094.

[10] 徐鳳燕,單杭冠,王宗欣.一種帶參數估計的基于接收信號強度的室內定位算法[J].微波學報,2008,24(2):67-72.