一種基于弱感知通信芯片的移動目標定位追蹤方法

摘 要：以通信能力較弱的低成本芯片為定位系統(tǒng)參考錨點，采用隨機部署方式，利用目標點接收系統(tǒng)內(nèi)參考錨點的輸出功率序列，構(gòu)建基于芯片輸出功率與傳輸距離關(guān)系的弱感知指紋地圖；針對此類系統(tǒng)內(nèi)存在位置匹配候選節(jié)點可能不唯一的問題，依據(jù)目標點運動一般具有方向性與連通性的特點，提出了一種基于弱感知通信芯片的移動目標定位追蹤方法。此方法根據(jù)移動目標的歷史路徑信息，計算當(dāng)前位置與前一相鄰位置候選節(jié)點之間的相交概率，維護一棵包含目標點路徑信息、位置節(jié)點累計概率的概率樹，通過在概率樹內(nèi)尋找最大累計概率的葉子節(jié)點，從而獲得移動目標的定位結(jié)果。仿真實驗表明：本方法能夠較好地解決位置匹配候選節(jié)點不唯一的問題，且其定位效果與傳統(tǒng)方法中固定部署參考節(jié)點的定位系統(tǒng)較為接近，亦能夠滿足室內(nèi)定位、目標追蹤等方面的要求。

關(guān)鍵詞：隨機部署；弱感知；輸出功率；相交概率；累計概率；概率樹

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2024）07-000-04

0 引 言

近年來，在基于位置服務(wù)的需求推動下，室內(nèi)定位系統(tǒng)的應(yīng)用迎來了重大機遇[1]。紅外、超聲波（US）、射頻（RF）、地磁場、超寬帶[2]、WiFi等無線通信技術(shù)[3-4]，被大量地應(yīng)用到室內(nèi)定位系統(tǒng)中。但是，無論基于何種技術(shù)實施的室內(nèi)無線定位系統(tǒng)，都需要在保證定位精度的同時，盡可能地降低系統(tǒng)成本，以提高系統(tǒng)商用價值，促進其大面積推廣。低成本、低功耗、弱感知能力的商用通信芯片的出現(xiàn)，例如Nordic Semiconductor公司的nRF24LE1芯片，為解決室內(nèi)無線定位系統(tǒng)的成本問題提供了新的途徑[5]。但是，此類芯片不具備發(fā)送、接收連續(xù)信號的能力，其輸出功率是與傳輸距離關(guān)聯(lián)的離散值[6]。

假設(shè)此類弱感知芯片對應(yīng)于距離d1， d2， ...， dL（dL-1lt;dL）的輸出功率為P1， P2， ...， PL，本文利用接收點與此類芯片的距離關(guān)系，通過目標點接收參考錨點發(fā)送的最小輸出功率值（Received Minimum Discrete Output Power， RMDOP）[7]，構(gòu)建室內(nèi)無線定位系統(tǒng)的位置指紋地圖，并結(jié)合目標點的運動特性，實現(xiàn)基于弱感知芯片的移動目標定位追蹤工作。

1 問題描述

1.1 條件假設(shè)

為了充分討論此類芯片在室內(nèi)定位系統(tǒng)中的應(yīng)用價值以及參考錨點隨機部署的可行性，作如下假設(shè)：

（1）弱感知芯片作為參考錨節(jié)點隨機部署后，位置坐標已知。

（2）目標點的接收功率為：P1， P2， ...， PL+1，其中P1， P2， ...， PL與距離d1， d2， dl， ...， dL（dl-1lt;dl）相關(guān)且目標點能夠接收到芯片發(fā)送的輸出功率，PL+1是目標點無法接收芯片錨點輸出功率時的值，即dgt;dL。

（3）將待定位的二維區(qū)域網(wǎng)格化，每個小正方形網(wǎng)格的位置為其中心坐標，位置指紋為中心坐標點接收參考錨點輸出功率的序列。

1.2 問題建模

由于參考錨點隨機部署后的位置不固定以及弱感知芯片輸出的離散性，在無線定位系統(tǒng)內(nèi)的不同位置有可能出現(xiàn)相同的RMDOP序列，如圖1所示，其中P1為目標點接收到參考節(jié)點1的功率時的檔位，P2為目標點接收到參考節(jié)點2的功率時的檔位。當(dāng)通過目標點與待定位區(qū)域內(nèi)位置指紋的RMDOP序列進行位置匹配時，具有最小差值的匹配節(jié)點可能出現(xiàn)不唯一的情況。即目標點可能存在多個定位匹配的候選節(jié)點，這種現(xiàn)象將增大無線定位系統(tǒng)的誤判概率、影響系統(tǒng)的平均定位誤差。本文內(nèi)容涉及定義如下：

定義1：最小接收功率（RMDOP）。設(shè)弱感知芯片錨點i的位置坐標為（xi， yi）， i∈（1， 2， ...， n），以邊長為e的小正方形網(wǎng)格化待定位平面；任意小正方形j的位置坐標為（xj， yj）， j∈G，G為區(qū)域內(nèi)網(wǎng)格的總數(shù)；在i與j之間的距離dij的范圍內(nèi)，j接收到參考錨點i輸出的最小值，Pij即為j相對于i的RMDOP值。

定義2：單元指紋。待定位平面范圍內(nèi)的任意小正方形j，收到系統(tǒng)內(nèi)全部參考錨節(jié)點的RMDOP值，構(gòu)成的RMDOP序列，即Fj=lt;P1j， ...， Pij， ...， Pnjgt;，" i∈（1， 2， ...， n）， j∈G，稱為單元指紋。

定義3：相交概率。假設(shè)任意目標點T以速度v勻速運動，在時間t內(nèi)目標點的移動距離s=vt；若目標點T的當(dāng)前位置為A，那么以A為圓心、s為半徑的圓被稱為目標點在A的位置圓，記為TA；當(dāng)位置A的前一相鄰位置B有I個位置匹配候選節(jié)點（I≥1），則目標點在位置B任意候選節(jié)點的位置圓記為TiB，i∈（1， 2， …， I）；將目標點在當(dāng)前位置A的位置圓TA與前一相鄰位置B的任意候選節(jié)點位置圓的相交面積記為NiAB，i∈（1， 2， …， I），若NiAB=0表示兩個位置圓不相交；將TA與前一相鄰位置B各候選節(jié)點位置圓的相交面積總和記為NAB，，則NAiB與NAB的比值稱為位置圓TA與位置B候選節(jié)點i的位置圓TBi的相交概率PAi。例如：位置B的候選節(jié)點數(shù)目I=2時，位置B與位置A處位置圓的相交示意圖如圖2所示。其相交概率的計算公式為：

（1）

依據(jù)目標點在室內(nèi)運動通常保持固定方向移動，且軌跡可連通的特性，本文針對系統(tǒng)內(nèi)目標點位置匹配時可能存在多候選節(jié)點的問題，利用目標點運動軌跡上相鄰位置候選節(jié)點間的相交圓面積，計算目標點從起點到終點各相鄰位置候選節(jié)點的相交概率值，探討基于弱感知芯片隨機部署的移動目標點定位追蹤方法。

本方法的核心工作是計算目標點運動路徑上，相鄰位置圓的相交概率，維護一棵從起點到終點的累計概率樹，并在概率樹的所有路徑分支中，尋找移動目標點位置匹配候選節(jié)點的最大累計概率，將其視為移動目標點的定位結(jié)果。當(dāng)前后相鄰的兩個位置圓的相交概率大于某一常數(shù)η1時，乘以一個增強因子ε1；當(dāng)相交概率小于某一常數(shù)η2時，乘以一個減弱因子ε1，且1≥η1≥η2，ε1≥ε2。此外，為了抑制累計概率樹的復(fù)雜度，提高算法的實用性，設(shè)存在某一足夠小的常數(shù)ε，若目標點某條運動路徑的累計概率小于ε，則視該條路徑為無效路徑，進而將其從概率樹中進行剪枝。

2 移動目標點的位置匹配策略

針對定位區(qū)域內(nèi)的移動目標點，根據(jù)定義3計算目標點運動路徑上相鄰位置的相交概率；利用相交概率，構(gòu)建一棵包含目標點當(dāng)前位置與前一相鄰位置關(guān)系的累計概率樹；通過更新、裁剪移動目標點從起點至終點的累計概率樹，并在概率樹的各路徑分支中尋找目標點運動路徑上最大累計概率的葉子候選節(jié)點，即為當(dāng)前的定位結(jié)果。移動目標點的位置匹配過程如下：

（1）在待定位范圍內(nèi)確定原點，依據(jù)待定位平面的總面積、小正方形邊長及面積，獲取各小正方形的物理位置[8]、計算得到定位系統(tǒng)的指紋總量G；

（2）依據(jù)定義1、定義2，計算系統(tǒng)內(nèi)任意小正方形j的單元指紋，迭代獲取系統(tǒng)的全部指紋，建立指紋地圖G；

（3）利用RMDOP之差反映的距離大小關(guān)系，通過歐氏距離實現(xiàn)移動目標點的位置匹配時，維持一個用以存儲包括當(dāng)前位置路徑信息、累計概率、候選節(jié)點的列表curL，一個用以存儲歷史位置信息的列表preL，以及一個保存目標點運動路徑上各位置匹配候選節(jié)點的列表canL。利用定義3構(gòu)建一棵從起點到終點，包含移動目標點路徑信息、累計概率的概率樹。若概率樹中的某條路徑的累計概率小于某一足夠小的常數(shù)ε，則該路徑被視為不可到達，進而將其從概率樹中剪枝，最后在概率樹內(nèi)尋找累計概率最大的葉子節(jié)點（終點），將其路徑信息視為移動目標點的定位追蹤結(jié)果。

3 定位算法描述

3.1 指紋庫的構(gòu)建

由條件假設(shè)、定義1、定義2，可以得到系統(tǒng)內(nèi)任意小正方形j的單元指紋Fj=lt;P1j， ...， Pij， ...， Pnjgt;，" i∈（1， 2， ...， n）， j∈G。

通過計算j與參考錨節(jié)點i之間的距離dij，對比錨節(jié)點功率傳輸范圍lt;d1， d2， ...， dLgt;，如果在lt;d1， d2， ...， dLgt;內(nèi)有且僅有一個大于dij的最小值dl（dl-1lt;dij， dijlt;dl， ...， dL），則將芯片傳輸距離為dl時的最小輸出功率Pl記為小正方形j接收到參考錨點i的功率值Pij；如果dijgt;dL，則Pij=PL+1，j∈G， i∈（1， 2， ...， n），

l∈（1， 2， ...， L），Pij的計算公式為：

（2）

迭代獲取小正方形j與系統(tǒng)內(nèi)全部參考錨節(jié)點的Pij值，建立j與全部參考錨節(jié)點的RMDOP值序列，獲得小正方形j的單元指紋Fj；系統(tǒng)內(nèi)總數(shù)為G的小正方形均獲取指紋后，系統(tǒng)完成了其指紋地圖的建立。

3.2 目標點的位置匹配

在獲得目標點T的運動路徑上某一位置的指紋向量FT后，利用歐氏距離函數(shù)在指紋庫G內(nèi)，尋找FT的最優(yōu)匹配指紋Fg，g∈G，從而完成移動目標點T的位置匹配工作，其歐氏距離函數(shù)為：

，i∈（1， 2， ...， n），g∈G" " " "（3）

式中：E表示目標指紋FT與指紋庫內(nèi)某指紋Fg的相似程度，即使得E取最小值的Fg為FT的最優(yōu)匹配結(jié)果。因為系統(tǒng)弱感知芯片參考錨節(jié)點的離散輸出功率特性，且隨機部署在定位系統(tǒng)內(nèi)，所以可能存在多個Fg使得E取最小值的情況。也就是說，目標點在運動路徑上某一位置可能有多個匹配候選節(jié)點。因此，本文對移動目標點進行位置匹配時，將當(dāng)前位置信息存儲于curL列表，還將目標點運動路徑上各位置可能存在的多個最優(yōu)匹配候選節(jié)點依次（從起點至終點）存儲于位置匹配候選節(jié)點列表canL中；利用移動目標點定位追蹤方法，最終獲得目標點在運動路徑上的位置信息。

3.3 移動目標點定位方法

依據(jù)目標點在室內(nèi)運動通常保持固定方向移動，且行動軌跡可連通的特性，通過歐氏距離函數(shù)實現(xiàn)移動目標點的位置匹配時，維持一個用以存儲當(dāng)前位置候選節(jié)點、路徑信息、累計概率的列表curL，一個用以存儲歷史位置信息的列表preL，以及一個保存目標點運動路徑上各位置匹配候選節(jié)點的列表canL。設(shè)當(dāng)前位置j的某一候選節(jié)點A（A∈canL[j]），前一相鄰位置的匹配節(jié)點S（S∈canL[j-1]， canL[j-1]∈preL），利用定義3計算當(dāng)前匹配位置與相鄰前一位置的相交概率值PAS。若PASgt;η1，則當(dāng)前位置匹配節(jié)點的累計概率CP乘以一個增強因子ε1；若PASlt;η2，則當(dāng)前位置匹配節(jié)點的累計概率CP乘以一個減弱因子ε2，且1≥η1≥η2，ε1≥ε2。本算法的主要工作是維護一棵從起點到終點，包含目標點運動路徑信息、位置節(jié)點累計概率的概率樹，在概率樹內(nèi)尋找累計概率最大的葉子節(jié)點（終點），將其路徑信息視為移動目標點的定位結(jié)果。由于目標點位置匹配候選節(jié)點數(shù)目的不確定性，算法的復(fù)雜度會隨著候選節(jié)點數(shù)目的增多與目標點移動距離的增加而增大。為了抑制累計概率樹的復(fù)雜度，提高算法的實用性，可以設(shè)置某一足夠小的常數(shù)ε，當(dāng)目標點的某條運動路徑累計概率小于ε，則視該條路徑為無效路徑，進而將其從概率樹中剪枝，以達到在保證算法正確性的同時，有效降低算法復(fù)雜度的目的。移動目標點定位算法如下：

算法1：移動目標點定位算法

1： 輸入：目標點路徑起點：StartPos；

2： 輸出：目標點定位路徑：Path；

3： path=[]，curL=[]，preL=[]，canL[]；

4： preL=preL+StartPos；

5： for j=1 to length[canL] do

6： MaxCP=0； /*最大累計概率

7： for All S ∈preL do

8： for All A∈canL[j] do

9： Calculate probability PAS；

10： if PAS≥η1 then CP=preL[loc]×PAS×ε1；

11： else if PAS≤η2 then CP = preL[loc]×PAS×ε2；

12： else CP = preL[loc]×PAS；

13： end if

14： curL=curL+（canL[j][loc]，preL[loc]+canL[j][loc]，CP）；

15： if CP≥MaxCP then" MaxCP=CP；

16： path=preL[loc]+canL[j][loc]；

17： end if

18： preL = curL；

19： end for

20： end for

21： end for

22： return path

4 仿真驗證

本文在驗證過程中，將弱感知芯片的離散輸出功率檔位設(shè)為5檔，分別為[4.5，5，5.5，6，9]，其中9表示接收點無法接收到離散功率；模擬在20×20的待定位范圍內(nèi)，隨機部署20個基于此類芯片的參考錨節(jié)點，在網(wǎng)格化小正方形邊長e=2的條件下，利用蒙特卡洛方法，實現(xiàn)當(dāng)前位置候選節(jié)點與前一相鄰位置的相交圓面積估算；進而計算得出目標點運動路徑上各位置的相交概率；建立了目標點運動路徑的累計概率樹；應(yīng)用實驗示例對移動目標點定位算法進行詳細說明，并通過多次獨立實驗對系統(tǒng)的平均定位誤差及效果進行了分析。

4.1 算法示例說明

假設(shè)目標點從起點開始，路徑上相鄰位置的橫坐標x增加1.2，縱坐標y增加1.7，某次實驗驗證中位置1的定位匹配共有3個候選節(jié)點，與前一個相鄰位置（起點）的相交概率分別為66.7% 、33.3%、0%（相交概率為0%時，表示當(dāng)前候選節(jié)點與前一相鄰位置的距離過遠，兩個位置圓不相交）；位置2的定位匹配中，共有2個候選節(jié)點，與前一個相鄰位置的3個候選節(jié)點的相交概率分別為46.2%、36.4%、19.2%和29.2%、29.2%、41.6%；位置3的候選節(jié)點與前一個相鄰位置的2個候選節(jié)點的相交概率分別為0%、100%。目標點運動路徑上各位置相交概率關(guān)系如圖3所示。

由于起點位置作為已知條件，所以位置1的相交概率為前一位置（起點）與位置1的3個候選節(jié)點的相交概率，其他位置的相交概率均為當(dāng)前位置候選節(jié)點與前一相鄰位置的相交概率。將位置1的候選節(jié)點分別記為1_1、1_2、1_3，位置i的第j個候選節(jié)點記為i_j。將圖3中各個路徑轉(zhuǎn)換為累計概率樹，如圖4所示。

本方法以目標點當(dāng)前位置候選節(jié)點為圓心，運動速度與時間的乘積（s=vt）為半徑，計算當(dāng)前位置與前一相鄰位置之間的位置概率關(guān)系，并依據(jù)相交概率的大小，分別乘以增強因子與減弱因子，從而達到連續(xù)更新移動目標點位置信息、裁剪路徑復(fù)雜度的目的。因此，當(dāng)相交概率為0時，表示當(dāng)前位置候選節(jié)點與前一相鄰位置的距離較大，位置圓無法相交，如圖4中位置1_3與起點的位置關(guān)系；另一方面，當(dāng)路徑上某一位置匹配存在多個候選節(jié)點時，隨著目標點的延續(xù)性移動，誤判的候選節(jié)點將逐步被糾正，如圖4中位置3_1對位置2_1的匹配結(jié)果進行了糾正；最后在獲得的概率樹內(nèi)，尋找目標點累計概率最大的運動路徑，得到其路徑為：起點、位置1_1、位置2_2、位置3_1、位置4_1。

4.2 誤差評估

本方法依據(jù)移動目標點前后相鄰位置之間的相交概率關(guān)系，確定其在運動路徑上各位置的匹配結(jié)果，所以本方法難以在脫離目標點運動路徑的情況下，獲得單一位置的定位精度。因此，本文借鑒文獻[9]中的分析方法：以一條路徑上所有位置節(jié)點的平均定位誤差來評判系統(tǒng)的定位結(jié)果。在上述仿真條件下，應(yīng)用本方法獨立完成10次仿真實驗[10]，其中7次出現(xiàn)了移動目標點位置匹配時候選節(jié)點不唯一的情況，各次實驗獲得的平均定位誤差最大值為1.085，最小值為0.585，平均值約為0.852，目標點運動路徑上各位置匹配候選節(jié)點數(shù)目及平均定位誤差見表1所列。

對比文獻[11]提出的基于弱感知通信芯片固定部署的室內(nèi)定位算法，表1中本方法的平均定位誤差最大值1.085與文獻[11]的方法中區(qū)域劃分的2類均方根誤差1.086 3非常接近；且本方法多次實驗的定位誤差平均值為0.852，最小值為0.585，明顯優(yōu)于文獻[11]的方法中區(qū)域劃分的3類均方根誤差0.926 5

及4類均方根誤差0.956 7。由此可見，本方法在以弱感知芯片作為定位系統(tǒng)參考節(jié)點并隨機部署的條件下，其定位效果略優(yōu)于傳統(tǒng)方法中以弱感知芯片為主動RFID標簽，且固定部署參考節(jié)點的定位系統(tǒng)，完全能夠滿足室內(nèi)定位的要求。

5 結(jié) 語

目前，以弱感知芯片為參考錨點并隨機部署的室內(nèi)定位研究成果相對較少。因此，本文提出了一種基于弱感知芯片的移動目標定位、追蹤方法，利用目標點的運動特性，計算目標點運動路徑上當(dāng)前位置與前一相鄰位置的相交概率，通過尋找移動目標點的最大累計概率路徑，確定目標點的最終位置匹配結(jié)果。仿真實驗表明，本方法在弱感知芯片作為參考錨節(jié)點并隨機部署的條件下，能夠較好地解決移動目標點某一位置匹配時候選節(jié)點不唯一的問題，有效降低了系統(tǒng)的定位誤差，減少了誤判現(xiàn)象，對促進弱感知芯片在無線定位系統(tǒng)中的應(yīng)用具有較重要的理論意義和研究價值。

參考文獻

[1] HE S，CHAN S H G. Wi-Fi fingerprint-based indoor positioning：recent advances and comparisons [J]. IEEE communications surveys amp; tutorials，2016，18（1）：466-490.

[2]王守華，陸明熾，孫希延，等.基于無跡卡爾曼濾波的iBeacon/INS數(shù)據(jù)融合定位算法[J].電子與信息學(xué)報，2019，41（9）：2209-2216.

[3] LUO J，F(xiàn)AN L，LI H. Indoor positioning systems based on visible light communication：state of the art [J]. IEEE communications surveys amp; tutorials，2017，19（4）：2871-2893.

[4] SHU Y，HUANG Y，ZHANG J，et al. Gradient-based fingerprinting for indoor localization and tracking [J]. IEEE transactions on industrial electronics，2016，63（4）：2424-2433.

[5] LI X，YANG Y，CAI J，et al. Plils：a practical indoor localization system through less expensive wireless chips via subregion clustering [J]. Sensors，2018，18（1）：205.

[6] LI X，ZHENG Y，CAI J，et al. TrackCC：a practical wireless indoor localization system based on less-expensive chips [J]. Sensors，2017，17（6）：1391.

[7]趙榮陽，李小龍，梁家海.一種基于弱感知通信芯片的動態(tài)精度無線定位方法[J].小型微型計算機系統(tǒng)，2020，41（10）：2164-2169.

[8]田子建，賀方圓.一種基于分布式壓縮感知的礦井目標指紋數(shù)據(jù)庫建立方法[J].電子與信息學(xué)報，2019，41（10）：2450-2456.

[9]王曉亮，徐恪，楊錚，等. TinyLoc：一種面向能耗受限的可穿戴設(shè)備的室內(nèi)定位算法[J].計算機學(xué)報，2017，40（8）：1813-1828.

[10]秦寧寧，金磊，許健，等.鄰近信息約束下的隨機異構(gòu)無線傳感器網(wǎng)絡(luò)節(jié)點調(diào)度算法[J].電子與信息學(xué)報，2019，41（10）：2310-2317.

[11]鄧昀，朱彥，楊逸夫，等.基于BP神經(jīng)網(wǎng)絡(luò)的RFID室內(nèi)定位算法研究[J].小型微型計算機系統(tǒng)，2019，40（8）：1707-1712.