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

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

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

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

0 引 言

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

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

1 問題描述

1.1 條件假設

為了充分討論此類芯片在室內定位系統中的應用價值以及參考錨點隨機部署的可行性，作如下假設：

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

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

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

1.2 問題建模

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

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

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

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

（1）

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

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

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

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

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

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

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

3 定位算法描述

3.1 指紋庫的構建

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

通過計算j與參考錨節點i之間的距離dij，對比錨節點功率傳輸范圍lt;d1， d2， ...， dLgt;，如果在lt;d1， d2， ...， dLgt;內有且僅有一個大于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與系統內全部參考錨節點的Pij值，建立j與全部參考錨節點的RMDOP值序列，獲得小正方形j的單元指紋Fj；系統內總數為G的小正方形均獲取指紋后，系統完成了其指紋地圖的建立。

3.2 目標點的位置匹配

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

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

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

3.3 移動目標點定位方法

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

算法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 仿真驗證

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

4.1 算法示例說明

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

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

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

4.2 誤差評估

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

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

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

5 結 語

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

參考文獻

[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數據融合定位算法[J].電子與信息學報，2019，41（9）：2209-2216.

[3] LUO J，FAN 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]趙榮陽，李小龍，梁家海.一種基于弱感知通信芯片的動態精度無線定位方法[J].小型微型計算機系統，2020，41（10）：2164-2169.

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

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

[10]秦寧寧，金磊，許健，等.鄰近信息約束下的隨機異構無線傳感器網絡節點調度算法[J].電子與信息學報，2019，41（10）：2310-2317.

[11]鄧昀，朱彥，楊逸夫，等.基于BP神經網絡的RFID室內定位算法研究[J].小型微型計算機系統，2019，40（8）：1707-1712.