一種基于弱感知通信芯片的動態精度無線定位方法

趙榮陽，李小龍，梁家海

1(北部灣大學 電子與信息工程學院，廣西 欽州 535011) 2(湖南工商大學 新零售虛擬現實技術湖南省重點實驗室，長沙 410205)

1 引 言

室內定位能在室內環境下為指定對象和用戶提供有效的跟蹤[1]、定位和導航服務，停車場、商場、火車站等場所對定位和導引的需求日趨強烈.這些需求為室內定位系統[2](Indoor Positioning System，IPS)提供了巨大的機會.對比于其它的室內定位技術，如視頻分析定位[3]、基于可見光通信的定位[4]等，無線定位技術具有覆蓋區域廣、定位精度高[5]、成本低等特點[6].目前，不同的無線室內定位系統(Wireless Indoor Positioning System，WIPS)依賴于不同的無線基礎設施[7]，如ZIGBEE、藍牙[8](Bluetooth)、WIFI[9]和RFID等.為了促進無線室內定位技術的快速發展和推廣應用，關鍵的問題是在保持定位準確性的同時、盡可能地降低系統成本，以促進無線室內定位行業的快速推廣和健康發展.

對于WIPS中的無線節點來說，系統芯片的價格在其生產成本上占據著較高的比例.目前，常見的通信芯片有Nordic Semiconductor公司的nRF24系列芯片，廣泛應用于藍牙產品、兼容于IEEE 802.15的Texas Instruments公司的CC2540系列芯片，廣泛應用于WIFI產品、兼容于IEEE 802.11協議的Atmel公司的Atmel?Smart Connect WIFI系列芯片等.通過比較這些廣泛應用于無線產品的商業芯片，運行在2.4GHz的nRF24系列芯片，如nRF24L01+，在價格成本上最有優勢[10].這種芯片具有能耗低、傳輸速率快、數據幀的有效載荷比高等優點，然而這些芯片存在著如下的功能限制：沒有RSSI(Received Signal Strength Indicator)的感知能力，也就是無法測量收到的信號強度[11]，僅提供多個無線射頻輸出功率來調節信號的傳輸范圍，并且接收節點收到發送節點的最小離散輸出功率(Received Minimum Discrete Output Power，RMDOP)與其傳輸范圍之間不服從均勻分布[12].

圖1 芯片功率檔位關系示意圖Fig.1 Schematic diagram of the relationship between chip power and distance

如圖1所示，假設此類芯片的L個離散輸出功率的檔位從P1～PL逐漸增大，相應功率檔位的最大傳輸距離為r1，r2…rL(rL-1

2 問題描述

2.1 網絡模型

考慮弱信號感知能力通信芯片的功能限制，當芯片作為無線定位系統參考節點，隨機部署在二維平面的待定位區域內時，區域內的接收點無法預先確定其接收到的各參考節點的RMDOP值，故對弱感知芯片無線定位系統做如下性質假設：

1)僅考慮RMDOP與其傳輸范圍(距離)之間的關系，忽略環境對信號傳輸的干擾；

2)數量為n的弱感知芯片作為定位系統的參考節點，隨機部署之后，參考節點的物理位置已知且靜止；

3)弱感知芯片具有P1～PL+1，共L+1個離散功率輸出檔位，其中P1～PL功率檔位為接收點能夠收到的功率值，各檔位對應呈遞增關系的最大傳輸距離：r1，r2，rl…rL(rl-1rL；

4)待定位區域以網格方式劃分，每一個單元網格的物理位置由其中心點的坐標表示；

5)待定位區域內每一個單元網格的指紋向量，由其中心點的指紋向量表示；

2.2 問題建模

弱感知芯片的離散功率輸出特性，是產生本文所研究問題的主要原因之一.在提出具體問題模型之前，首先給出相關定義.

定義1.最小接收功率(RMDOP)：假設參考節點i的物理坐標為(xi，yi)，i∈(1，2，…，n)，待定位的二維平面區域，被劃分為邊長為d的G個正方形單元網格，其中網格j的中點物理坐標為(xj，yj)，j∈G，rij表示參考節點i到網格j中心點的距離，那么在此距離范圍下，網格j接收能夠接收到參考節點i的功率最小值，稱為最小接收功率(RMDOP)，記為：Pij.

定義2.單元網格指紋：單元網格中心點接收各參考節點發送的RMDOP值序列，稱為單元網格指紋，即：Fj=，i∈(1，2…n)，j∈G.

定義3.高差異度指紋：假設任意兩個單元網格j與g的中心點之間的物理距離，等于兩個單元網格邊長之和的1/2，稱它們為相鄰網格；當采用歐式距離判斷Fj與其所有的相鄰網格指紋Fg存在的差異程度時，若存在一個較大的標量δ，使得不等式：|Fj-Fg|≥δ均成立，即滿足公式(1)時，則稱Fj為高差異度指紋；其中，設Nj為單元網格j的相鄰網格數目，Fg=，i∈(1，2…n)，g∈Nj，Nj∈G.

Min(|Fj-Fg|)≥δ，j∈G，g∈Nj

(1)

考慮任意此類室內定位系統的指紋庫內，皆可能存在高差異度指紋，本文針對存在的高差異度指紋采用迭代分割的方法，即將高差異度指紋的單元網格，分割成若干個邊長更小的子網格，當子網格序列獲得定義2的單元格指紋之后，構成了定位系統的一個具有動態精度的指紋庫，以達到提高系統定位精度的目的.

假設待定位區域的總面積為S，初始指紋網格的邊長為d0；通過迭代調度、動態分割高差異度指紋的單元網格后，未被分割的非高差異度指紋的單元網格總面積記為S0，指紋網格邊長為d0，僅實現迭代一次的高差異度指紋的單元網格分割面積為S1，分割后的子網格邊長為d1；實現二次迭代的高差異度指紋的單元網格分割面積為S2，分割后的子網格邊長為d2；以此類推，實現K次迭代的高差異度指紋的單元網格分割面積為SK，分割后的子網格邊長為dK；其中，d1，d2，…，dK之間的符合如下關系：d1=α×d2…dK=α×dK-1α<1.因此，此類室內無線定位系統的動態定位精度模型，如公式(2)所示，其中A為動態定位精度值.

(2)

針對基于弱感知通信芯片的定位系統，一般情況下動態精度方法的迭代次數，取決于某次迭代后，重構的指紋庫內是否存在高差異度指紋.通常迭代次數越多，動態精度將越高，但是迭代次數的增加，將會增大指紋庫建立階段的采樣耗時及系統開銷.設有一個較小的系統定位精度標量值ε，當動態定位精度值符合條件A<ε時，停止迭代，稱ε為動態精度無線定位方法的截止精度.

定義4.動態指紋庫：設在初始指紋庫建立之后，所有單元網格的邊長均相等，為靜態指紋庫；當靜態指紋庫內存在定義3所述的高差異度指紋，并實現了高差異度指紋的K次迭代分割后，重構的含有不同單元格網格邊長、具有動態定位精度的新指紋庫，稱為動態指紋庫.

3 動態指紋庫調整策略

隨機部署的弱感知芯片作為室內無線定位系統參考節點，考慮芯片的功能限制，系統有如下特點：

1)參考節點芯片僅提供若干傳輸范圍可調節的輸出功率檔位，具有離散性；

2)接收節點收到發送節點的RMDOP值與其傳輸范圍之間不服從均勻分布；

3)芯片作為參考節點的部署情況隨機，即：在芯片部署之前，參考節點的位置坐標、參考節點之間的距離等是不確定的.

4)室內定位系統的平均定位精度，取決于待定位區域網格化的單元網格劃分情況；

因此，在網格化的待定位區域內，當任意單元網格j的指紋Fj為高差異度指紋時，可以通過迭代的方法，動態分割此高差異度指紋的單元網格，將其劃分為m×m個子網格，以提高基于弱感知芯片隨機部署的室內定位系統的定位精度.動態精度指紋庫的調整策略，包括如下步驟：

步驟1.在待定位的MM二維區域內，根據起始點的物理坐標、待定位區域面積、靜態指紋單元網格邊長、面積，計算待定位區域內的靜態指紋網格總數G、各單元網格中心點的位置坐標；

步驟2.計算待定位區域內任意單元網格j的中心點與參考節點i之間的距離，并比較參考節點傳輸功率的距離范圍序列r1，r2，rl…rL(rl-1

步驟3.依據單元網格指紋與其相鄰網格之間的指紋差異程度，判別指紋庫內的高差異度指紋，通過迭代法動態分割高差異度指紋的單元網格，并重構一個含有不同單元網格邊長的動態指紋庫G1；

步驟3.1.遍歷靜態指紋庫G，依據定義3，當單元網格的指紋Fj滿足公式1時，記錄Fj為高差異度指紋；將高差異度指紋的單元網格j，重新劃分為m×m的子網格，每一個子網格的邊長，為原高差異度指紋的單元網格邊長的α倍，并根據定義2計算子網格的指紋，其中m≥2，0<α<1；當所有高差異度指紋的單元網格均被重新劃分之后，全部指紋重新構建為一個，含有不同單元網格邊長的動態指紋庫G1；

步驟3.2.遍歷動態指紋庫G1，迭代執行步驟3.1，直到當前被遍歷的動態指紋庫G1內不存在高差異度指紋，或者定位精度小于精度標量ε，終止算法，從而獲得室內定位系統最優的動態指紋庫G1.

4 動態精度定位算法描述

4.1 靜態指紋庫的構建

靜態指紋庫是定位系統采用動態精度定位方法時的初始指紋庫，根據定義2可知，單元網格指紋是其中心點接收各參考節點發送的RMDOP值序列，即：Fj=，i∈(1，2…n)，j∈G，n為參考節點的數目，G為單元網格的總數；由問題假設與定義1可知，弱感知芯片具有P1～PL+1，共L+1個與距離相關的離散功率輸出檔位，對于待定位區域內任意單元網格的RMDOP值，可以通過中心點與參考節點之間的距離關系獲得.首先計算單元網格j的中心點與參考節點i之間的距離rij，然后在參考節點發送功率檔位的傳輸距離序列內查找，如果存在一個大于rij的最小值rl(rl-1rL時，單元網格j接收到參考節點i的RMDOP值Pij=PL+1，j∈G，i∈(1，2…n)，l∈(1，2…L)，Pij的計算如公式(3)所示.

(3)

圖2 靜態指紋庫建立流程圖Fig.2 Chart of static radio map building

重復上述操作直至獲得單元網格j與所有參考節點的RMDOP值，并以j接收到的各個參考節點的RMDOP值序列，構成單元網格j的指紋向量Fj，當待定位區域內的所有單元網格均被賦值后，獲得定位系統的靜態指紋庫.靜態指紋庫建立的算法程序流程圖，如圖2所示.

4.2 動態指紋庫的構建

動態指紋庫的構建過程中，首先遍歷靜態指紋庫G，若存在Fj，jG，滿足公式(1)，則靜態指紋庫G內存在高差異度指紋，然后記錄高差異度指紋，并迭代分割其單元網格.每一個高差異度指紋的單元網格被劃分為m×m的子網格序列，以dj表示高差異度指紋Fj的單元網格j的邊長，d表示分割后的子網格邊長，其中d=αdj，m≥2，0<α<1.本文取m=2，d=1/2dj，算法執行的過程中，將根據高差異度指紋的單元網格中心點位置坐標、子網格邊長，重新計算子網格的中心點坐標，然后利用靜態指紋庫的構建方法，生成高差異度指紋Fj的子網格指紋序列；最后，將新生成的各高差異度指紋的子指紋序列與靜態指紋庫，重構為一個含有不同單元網格邊長的新指紋庫-動態指紋庫，指紋同樣記為Fk=，i∈(1，2…n)，k∈G1，G1為動態指紋庫內的指紋總量，n為參考節點的數目.

依據動態指紋庫的構建步驟3.2，迭代遍歷、重構動態指紋庫G1.當動態指紋庫G1內不存在高差異度指紋，或者動態定位精度值符合條件A<ε，即定位精度A小于系統的截止精度標量ε時，得到的指紋庫G1被認為是系統的最優動態指紋庫，終止迭代算法.動態指紋庫的構建程序流程圖，如圖3所示.

圖3 動態指紋庫構建流程圖Fig.3 Chart of dynamic radio map building

4.3 位置估計方法描述

目標點的位置估計，是室內無線定位系統最終的目標，即當系統獲得目標點T的指紋向量FT后，在動態指紋庫G1內尋找FT的匹配指紋Fg，g∈G1.在眾多的指紋序列匹配方法中，本文選擇了歐式距離函數，來求解兩個指紋的匹配度，計算如公式(4).

(4)

公式(4)中dist表示目標指紋FT與G1內指紋Fg的匹配程度，當dist=0時，FT與Fg完全匹配；當dist0時，使得dist取最小值的Fg為FT的最優匹配值.因為指紋向量是由芯片參考節點的離散輸出功率檔構成，采用距離最鄰近(NN)方法進行位置估計時，可能存在不唯一的最優匹配值，即：目標節點T可能存在k個估計值，k≥1.因此，本文在遍歷動態指紋庫、計算所有單元網格指紋與目標指紋FT的距離時，將目標點T的匹配指紋Fg以dist值的升序，存儲于候選估計隊列Q中，并選擇k最近鄰(KNN)匹配方法，計算k個最優匹配指紋的單元網格中心點平均坐標，作為目標點的位置估計結果，計算如公式(5).其中(xT，yT)為目標點的位置估計坐標，(xg，yg)為最優匹配指紋Fg的單元網格中心點坐標，k的值由候選估計隊列Q內，最優匹配指紋Fg的數目決定.

(5)

5 實驗仿真

設參考的接收功率為1-5檔，傳輸距離分別為[3，5，7，8，9]，仿真模擬弱感知通信芯片作為參考節點，隨機部署在20×20的二維平面；選取了各接收功率傳輸距離的均方差，作為高差異度指紋判別標量δ；靜態指紋庫邊長的初始值d0=4；在參考節點數目n=7、n=10、n=20的條件下，分別完成15次獨立實驗.實驗以動態指紋庫的一次、二次迭代定位精度為考察目標，主要從參考節點數目與高差異度指紋的迭代次數、動態定位精度之間的關系；動態指紋庫、靜態指紋庫的系統精度、節點定位誤差等方面評估動態精度定位算法的性能.

5.1 定位精度分析

在動態精度定位算法的15次獨立實驗中，當參考節點數目n=7時，出現了1次不迭代(未出現高差異度指紋)、5次只進行一次迭代的情況；當n=10時，僅出現1次只進行一次迭代的情況；當n=20時，15次實驗均進行了二次迭代.算法的一次、二次迭代精度如表1、表2所示.

表1 一次迭代定位精度Table 1 Resolution for positioning in the first iteration

表2 二次迭代定位精度Table 2 Resolution for positioning in the second iteration

在參考節點數目分別為n=7、n=10、n=20時，動態指紋庫的一次、二次迭代分割后，定位精度的對比情況，如圖4(a)-(c)所示.圖4(a)是n=7時的精度對比、圖4(b)是n=10時的精度對比，可以看出當n=7與n=10的條件下，根據公式(2)的計算方法，發現二次迭代與一次迭代相比較，對于系統定位精度的提高效果并不明顯；但在圖4(c)n=20時的精度對比圖中，15次實驗中，二次迭代后的定位精度均小于2，并隨著迭代次數的增加，定位精度有較為明顯的提高.

因此可知，在動態精度算法中，高差異度指紋的出現概率，隨著參考節點數目的增加而增大；算法的迭代效果、定位精度，也隨著參考節點數目的增加而提高，圖4(d)是參考節點數目n=7、n=10、n=20條件下，算法二次迭代的定位精度效果對比圖.

5.2 位置估計誤差評估

由上述分析可知，待定位區域面積、初始的靜態指紋網格邊長固定時，高差異度指紋的出現概率、數目，將隨著參考節點數目增加而增大，在動態分割高差異度指紋后，系統的動態精度提高也更為顯著.

圖4 定位精度對比圖Fig.4 Chart of resolution comparing

文獻[12]中詳細介紹了一種基于弱感知芯片固定部署的室內定位技術—TrackCC，并在文中給出了TrackCC、LANDMARC、SAIL三種定位方法的位置評估誤差CDF函數圖，其中，基于弱感知芯片的TrackCC，定位誤差小于0.5米的概率達到68%，而SAIL小于0.5米的定位誤差的約為5%，LANDMARC則約為2.5%.

圖5 位置估計誤差對比圖Fig.5 Chart of error comparing for position estimating

本文的仿真實驗中，在參考節點數目n=10、n=20的條件下，待定位區域內隨機生成目標節點，分別通過傳統的靜態指紋庫方法、動態精度方法完成目標節點的位置估計，其定位誤差的累積概率(CDF)、單個節點定位誤差情況，如圖5所示.

圖5(a)是當參考節點n=10時的位置估計CDF分布圖，其中動態精度方法的定位誤差小于0.5的概率可達到約20%，定位誤差小于1的概率可達到約40%，并且定位誤差小于3的概率可達到85%以上.圖5(b)是當參考節點數目n=20時的位置估計CDF，動態精度方法的定位誤差小于0.5的概率可上升至約40%，定位誤差小于1的概率可達到70%以上，并且在定位誤差小于2.5時，概率逼近100%.與此同時，在圖5(a)、(b)中可以看出靜態指紋庫方法的定位誤差小于0.5米的概率可達到10%左右，定位誤差小于1米的概率可達到約20%，而且當參考節點由n=10增加到n=20之后，動態精度定位方法與靜態指紋庫方法相比較，其定位精度的提升更為顯著.

此外，仿真實驗中選取了20個隨機目標節點，觀察單個節點的定位誤差精度，如圖5(c)、(d)所示.圖5(c)為當n=10時的節點位置估計誤差對比，圖5(d)為n=20時的節點位置估計誤差對比.通過單個目標節點采用動態精度法與靜態指紋庫方法，進行位置估計的單點誤差對比，可以看出在參考節點數目n=20時，動態精度法的單個節點定位誤差精度，相較于傳統的靜態指紋庫方法，也有顯著的提高.

6 結 論

仿真實驗表明，在待定位區域面積、初始指紋單元格邊長固定的條件下，動態精度的定位效果與參考節點的數目有較為重要的關聯，增加參考節點的數目，使得指紋庫內高差異度指紋的數目增大，進而提高了動態精度方法的迭代次數和迭代效果，但同時也增加了動態精度指紋庫建立階段的采樣耗時.因此，適當的參考節點數目、適當的系統定位精度，對于本算法的應用效果較為重要.如圖5所示，本文仿真環境下，當參考節點數目n=20時，動態精度方法獲得了較好地定位效果.因此，動態精度的定位方法較靜態指紋庫方法，更適合弱感知通信芯片作為參考節點，在隨機部署的情況，能夠獲得更高的定位精度.

定位精度是評價室內無線定位系統的主要指標之一.目前，關于低成本、弱感知能力傳感器芯片，用于無線定位系統的研究，鮮有動態定位精度的相關文獻.文獻[12]中基于固定部署的弱感知芯片，提出了一種室內定位技術—TrackCC，雖然獲得了較高的定位精度，但其精度并沒有動態提高的特性，且芯片部署的人力投入較高.因此，本文提出了一種基于弱感知芯片的動態精度無線定位方法，考慮該類芯片存在的功能限制，通過接收點的最小接收功率建立指紋數據庫，利用物理相鄰指紋之間的差異程度，記錄并重新劃分高差異度指紋，構建動態精度指紋庫，旨在提高此類傳感器芯片，在隨機部署的情況下，獲得較高地系統定位精度.