遮擋環境下室內定位系統的信標節點布局優化*

焦 侃， 馮劉濤， 張 磊， 胡志新

(1.長安大學 工程機械學院，陜西 西安 710064； 2.成都國光電氣股份有限公司，四川 成都 610051)

0 引 言

隨著各類型智能移動終端的發展，如何在復雜室內獲取實時、高精度的位置信息是智能移動終端在室內場景為人們提供各類服務的關鍵，具有廣闊的市場應用前景[1,2]。根據微軟國際室內定位大賽的評估結果，基于測距的室內定位系統在室內復雜環境中具有較好的性能[3]。其主要定位架構包括基于到達時間(time of arrival，TOA)法、到達時間差(time difference of arrival，TDOA)法，以及基于信號接收強度指示(received signal strength indication,RSSI)的測距法。與其他技術相比，基于測距的定位系統具有低計算復雜度和低能耗的特點，因而具有較好的應用前景。但在實際應用和推廣中，室內遮擋非視距(non-line-of-sight，NLOS)環境成為該類技術所面臨的最主要挑戰[4]。

在室內復雜環境中，遮擋往往會給測距引入一個較大的正偏差，極大地削弱了系統的定位精度和穩定性。目前，改善室內NLOS環境下定位系統性能的解決途徑包括：研究更好的NLOS定位算法[5]；增加信標的部署密度[6]。前者會提高計算復雜度，后者則會增加定位系統整體的成本。通過優化系統信標的布局方式，可以在不改變計算復雜度和部署成本的前提下，提高系統的定位性能。

目前，針對室內定位系統信標節點最優化布局的研究尚處在起步階段，且絕大多數研究成果均是針對理想的非遮擋(即視距(line-of-sight，LOS))環境。文獻[7]給出了尋找節點最優布局的一種迭代搜索算法，但這種方法對于簡單規則環境下的錨節點最優布局搜索有較好的收斂性，對于復雜的室內定位環境還有改進的空間。文獻[8]提出了定位誤差的簡化算法與近似函數，利用改進的隨機搜索算法在可接受的時間成本內找到信標節點的次優分布。文獻[9]給出了TDOA和頻差到達(frequency difference of arrival,FDOA)定位算法下的最優參考節點的配置策略，未考慮遮擋物問題。文獻[10]利用混合整數線性規劃 (mixed-integer linear programming,MILP)法基于信標節點布局幾何精度因子(geometric dilution of precision，GDOP)最小化三維無遮擋環境下的定位信標節點數并找到其對應的最優分布。但所給出的信標節點只能分布于定位空間的表面且不考慮空間內的NLOS問題。

因此，本文針對遮擋環境中基于測距的定位系統，提出了一種基于粒子群優化(particle swarm optimization，PSO)算法的信標節點布局優化，并提出了針對遮擋環境的最優化適應度函數,分別通過數值仿真和實驗進行性能評估，來提高室內復雜環境中基于測距的定位系統的精度和穩定性。

1 問題描述

1.1 GDOP

GDOP是衡量由信標節點布局所引起的系統定位誤差的一個重要參數， GDOP值越小表示定位系統的定位精度越高。在高斯環境下的m個信標節點特定布局，GDOP的值G可以表示為

(1)

(2)

相對應地，TDOA架構的Q和H分別表示為[11]

(3)

(4)

1.2 遮擋環境下的GDOP

在理想無遮擋環境下的GDOP計算中，距離量測被看作服從獨立同分布的高斯分布。但在NLOS環境下，當待測節點與信標節點之間存在遮擋物時，距離測量信息服從高斯分布的假設不成立。基于式(1)對GDOP進行計算會存在較大誤差。

為了對NLOS環境中的GDOP進行計算，一種切實可用的方法是剔除掉遮擋的距離量測信息后，僅使用LOS量測來對GDOP值進行近似計算。因此,遮擋環境下GDOP值的計算，只需考慮LOS信標節點布局的影響。

2 遮擋環境下的適應度函數

信標節點布局優化問題，即為在定位空間中找到一種最優的布局方式，使得定位區域中的GDOP均值最小。本文研究的是遮擋環境中信標節點布局優化問題，由于遮擋的影響，單個待測節點需獲取足夠的LOS量測才能成功定位。TOA架構需要2個以上，而TDOA架構則需要3個。

因此,布局優化的目標可描述為：在定位目標區域找到一組信標節點的布局，使得區域內能夠成功定位的待測節點GDOP均值最小。選取目標區域內均勻分布的N個測量點作為待測節點，信標節點布局P能夠成功定位的節點個數為N′，優化問題的適應度函數可定義為

(5)

該適應度函數僅考慮到能夠成功定位的待測節點。對于LOS量測數量小于最小需求的未知節點則不予考慮。因此，針對遮擋環境，對上述適應度函數進行改進

(6)

式中i為待測節點所能獲得的LOS量測信息的數量，N′i為獲取LOS信息數量為i的未知節點的總數，fi為權重系數，不同權重系數下所期望的每類未知節點占比例有所不同。對于TOA架構，i′=2;對于TDOA架構，i′=3。

3 優化方法

3.1 PSO算法

節點布局優化問題大多采用隨機搜索法來尋找其最優解。本文采用PSO算法來尋找遮擋環境下信標節點的最優布局。PSO算法是一種基于簡化生物社會模型的群智能優化算法,可描述為：n個粒子組成的群體在D維空間中運動，結合粒子自身以及群體所經歷的最好位置來更新粒子的運動狀態。粒子的運動速度與位置更新由式(7)和式(8)決定[12]

(7)

(8)

w=wmin+(wmax-wmin)×(1-k/kmax)

(9)

式中wmax和wmin分別為最大慣性權重與最小慣性權重，kmax為最大迭代步數。

3.2 算法流程

在定位空間中對m個信標節點進行布局優化。定位區域離散化后待測節點數量為N。粒子規模取S，每個粒子表示一種信標布局方式，則單個粒子的維度為m×3，每個維度的最大搜索速度為vmax。綜合考慮算法的初期的全局搜索能力以及后期的局部搜索能力，選取最大慣性權重wmax為0.9，最小慣性權重wmin為0.4，最大迭代次數為kmax步。

步驟1 在定位區域內隨機初始化粒子群的初始位置與初始速度，即隨機確定S種初始信標節點布局方式與初始速度,并要保證每種布局的信標節點位置都在非遮擋區域內。

步驟4 若滿足終止條件，則輸出最優布局方式與其適應度值，否則返回步驟2。終止條件包括：1)迭代次數超出最大值；2)適應度函數的值小于設定閾值；3)迭代步間差值小于設定閾值。

4 數值仿真與結果分析

以基于TOA定位系統在二維平面內的4個信標節點布局優化問題進行數值仿真。定位區域為40 m×40 m，對定位區域進行長寬均為0.5 m的網格劃分，其頂點為待測節點。PSO算法的最大慣性權重與最小慣性權重分別取0.9與0.4，最大搜索速度為5 m/s，粒子群規模為20，迭代次數為500次。

當定位區域為LOS時，信標節點的最優布局如圖1(a)所示，該結果與文獻[13]中的結果相似。當定位區域存在遮擋物時，定位區間為非凸。以式(6)為優化適應度函數，權重系數f2,f3,f4取0.1,0.1,0.8，優化布局結果如圖1(b)所示。分析兩種環境下的信標節點優化布局結果可發現，當定位空間為遮擋環境時，信標節點的最優布局會優先提高能同時接收到更多LOS信號的未知節點的數量，其結果與實際的認知情況相符合。

圖1 LOS與遮擋場景的布局優化結果對比

適應度函數式(6)中，不同權重系數fi用于控制所期望的不同數量LOS量測定位區域的占比。取f2,f3,f4的值為

(10)

計算在該權重下的信標節點最優布局，并統計不同權重系數下N′2，N′3，N′4占比如圖2所示。

圖2 不同權重配比下的區域占比

5 實驗與結果分析

通過在實際場景中的實驗對本文所提出的定位方法性能進行評估。室內實驗環境選在長安大學本部北院主教學樓三樓大廳進行，如圖3所示，長約11 m，寬約9 m。該場景是一個半敞開的大廳，利用場景中的柱子來模擬室內遮擋現象。具體實驗步驟為：在同一室內遮擋環境下依次布設兩種信標布局，在每種布局方式下選取三個位置相同的節點作為待定位的未知節點進行定位實驗,如圖4所示。根據最大似然估計算法得出每個未知節點的位置估計信息。依據經驗的布局方式和最優化布局如圖5(a)所示。兩類布局方式下的定位結果如圖5(b)和圖5(c)所示。

圖3 實驗場景照片

圖4 實驗硬件設備

圖5 不同布局方式下的定位結果

可以看出，最優布局整體定位結果相較于經驗布局有所提高。在定位點1處，經驗布局和最優化布局的結果相似。但布局在經過優化后，其定位精度和穩定性均得到了提升。

在定位點2，經驗布局由于信標B被遮擋，僅依靠A和C來進行位置估計。并且三者處在一條直線上，使得其定位誤差較大，穩定性較差。經過布局優化后，該點定位性能得到極大提升。

定位點3，經驗布局對該點較為友好，不存在NLOS問題，其獲得了較高的定位精度和穩定性。而最優布局僅依賴信標B′和C′進行定位，其定位精度和穩定性有所下降。如圖6所示為定位結果的CDF對比，可以看出，經過布局優化后，其定位性能和穩定性均得到了提升。

圖6 兩類布局下的CDF對比

6 結 論

本文針對室內NLOS環境，面向基于LOS的室內定位，在不改變室內定位算法與增加信標部署數量的前提下，通過優化信標節點的布局方式以提高定位精度與穩定性。通過分析NLOS環境中的GDOP問題，提出了信標節點布局優化的適應度函數，并基于PSO算法對其進行求解。進一步地，對其算法的詳細計算過程進行了闡述。隨后，通過數值仿真，在遮擋環境中對本文所提出方法的性能進行評估。并對適應度函數的權重對優化結果的影響進行了仿真和分析。結果表明:所提出的適應度函數能夠有效解決遮擋環境中的信標節點布局優化問題，并能夠通過適應度函數的權重對信標節點布局優化的結果進行控制。通過在實際場景中，對比TOA定位系統在信標節點經驗布局和最優化布局下的定位性能，可以看出,經過布局優化后，其定位性能和穩定性均得到了提升。