一種基于線性規劃松弛的無線位置匹配算法

馬佩勛

一種基于線性規劃松弛的無線位置匹配算法

馬佩勛

（長沙民政職業技術學院 軟件學院，長沙 410004）

針對物聯網中設備的定位問題，提出基于最大似然估計的位置匹配（MLLM）算法。MLLM算法先測量每對設備間的接收信號強度值（RSSI），再利用這些RSSI值構建位置與節點身份標識號（ID）間的最佳匹配似然函數。最后，利用線性規劃松弛（LPR）求解，進而實現節點的位置匹配。仿真結果表明，相比于窮舉搜索，MLLM算法有效地降低了運算時間，并保持較高的位置匹配準確度。

無線定位；位置匹配；似然估計；接收信號強度；線性規劃

0 引言

無線傳感網絡（wireless sensor networks, WSNs）由低功耗、微型傳感節點構成。節點一般由微控制器、存儲單元、電源和無線射頻（radio frequency, RF）收發器組成。部署WSNs的根本目的在于收集數據。節點通過感測環境數據，再將數據向控制中心傳輸。因此，WSNs成為物聯網（internet of things, IoT）的重要組成部分[1]。

位置服務是物聯網的一項基本需求[2-3]。利用全球定位系統（global positioning system, GPS）模塊節點能夠獲取位置信息。但安裝GPS模塊增加了節點成本，并且運行GPS也增加了節點的能量消耗。此外，在室內環境中，無法利用GPS模塊進行定位。因此，研究人員把精力投放于基于RF定位算法。例如，文獻[4]提出基于RF梯級分域的室內定位算法，該定位算法由離線和實時定位兩個階段構成，先將定位區域劃分成若干個子域，再對各子域內的參考節點進行梯級分類。文獻[5]提出基于RF信號強度的室內定位算法，先利用信號強度測距，再通過三邊定位算法估計節點位置；但是信號在室內環境的衰減大，測距誤差較大。文獻[6]提出基于射頻信號接收強度（received signal strength indicator, RSSI）聚類與多傳感器融合的定位算法。文獻[7-8]采用加權聚類均值策略，降低定位誤差。但是執行加權聚類算法，增加了算法的復雜性。為此，研究人員提出了數據匹配定位算法。所謂數據匹配定位算法就是將信號特征與預定數據庫的信息進行比對，進而識別目標設備最可能出現的位置[9]，如RF指紋定位算法。盡管匹配定位算法的實施方式靈活，但是它們存在因背景噪聲、無線多徑衰落、損耗等因素引起的較大定位誤差的不足。并且在不同的背景環境下的傳播模型并不相同。若在所有背景環境下采用相同的傳播模型測距，必然會引起較大的測距誤差。因此，需針對特定環境，采用與此環境相匹配的傳播模型，即需對傳播模型進行調整。據此，提出最大似然估計的位置匹配算法（maximum likelihood- based localization matching, MLLM）算法。MLLM算法先測量每對傳感節點間的RSSI值，再通過RSSI值獲取位置與節點間最佳匹配似然函數，并利用線性規劃松弛（linear programming relaxation, LPR）求解，進行位置匹配，最終實現節點位置的估計。

1 問題描述及傳播模型

1.1 無線位置匹配問題

每個傳感節點配備了無線收發器，且能與其他節點交互消息。因此，節點能夠捕獲交互信號的RSSI值。獲取了RSSI值后，再傳輸至服務器。

圖1 WLMP系統

1.2 傳播模型

1.2.1 LoS傳播模型

目前，對數-距離傳播模型廣泛應用于不同環境[11]。用弗里斯（Friss）等式表述與距離關系為

1.2.2 非視距NLoS傳播模型

當無線信號穿過墻時，與距離關系[12]為

1.2.3 噪聲變量

假定傳播模型服從對數-距離模型，隨機變量就服從零均值、標準方差的高斯分布。因此可得

2 MLLM算法

2.1 似然函數的計算

一旦從獲取了所有節點的RSSIs值，服務器就將其存儲于矩陣。對于RSSI矩陣，通過尋找滿足在假設集能滿足最大化似然函數[14]值*，即

將式（8）代入式（7）可得

傳播模型服從對數-正態模型，變量服從高斯分布，*可簡化為

2.2 MLLM算法

式（10）為個變量的組合優化問題。為了降低算法的運算時間，MLLM算法利用LPR求解式（10）的近似解。

2.2.1 目標函數

整數線性規劃（integer linear programming, ILP）目標函數為

2.2.2 基于LPR求解

利用LPR求解式（11）時，解可能不是整數，則需先利用式（18）獲取近似解，即

然后將節點與位置進行匹配，進而最大化所有節點的和為

3 性能仿真

3.1 仿真場景

利用LPR求式（10）的近似解。在仿真過程，選用混合整數線性規劃（mixed integer linear programming, MILP）、遺傳算法（genetic algorithm, GA）和窮舉搜索（brute force search, BFS）求解，并與LPR進行性能比較，分析它們的匹配準確率和運算時間。

同時考慮兩個仿真場景，仿真場景參數如表1所示。

表1 兩個場景的仿真參數

3.2 場景一環境下的匹配準確率和運算時間

圖2顯示了LPR、MILP和BF的3個求解算法的匹配準確度。

圖2 場景一的位置匹配準確度

從圖2可知，位置匹配準確度隨噪聲標準方差的增加而下降，LPR、MILP和BF算法的位置匹配準確度隨變化具有類似走勢。然而，當大于6 dB·m后，LPR算法求解的位置匹配準確度低于MILP和BF。但當小于6 dB·m時，LPR算法求解的位置匹配準確度與MILP和BF一致。這也說明，通過LPR算法獲取的近似解適應噪聲環境波動小的環境。

圖3顯示了LPR、MILP和BF算法求解位置匹配所需的時間。

圖3 場景一的運算時間

從圖3可知：LPR算法平均運算時間約4 s；BF算法的平均運算時間約133 s；LPR和BF算法的運算時間隨變化波動小；MILP算法的運算時間隨的波動較大。當大于10 dB·m時，MILP算法的運算時間甚至大于BF算法。

結合圖2和圖3不難發現，盡管LPR算法在噪聲嚴重環境下的匹配準確度低于MILP和BF算法，但是它的運算時間遠低于MILP和BF算法。這也說明，LPR算法能夠以低復雜度換取較高的匹配準確度。

3.3 場景二環境下的匹配準確率和運算時間

圖4顯示LPR和GA算法所求解的位置匹配準確度。

圖4 場景二的位置匹配準確度

從圖4可知，GA算法與LRP算法的位置匹配準確度相近，并隨節點數變化趨勢相近。節點數越大，匹配準確度越高，當為20時，匹配準確度達到0.9。節點數越多，獲取節點間測距數據也越多，也越有利于位置匹配準確度的提高。

圖5顯示了GA和LPR算法匹配位置消耗的時間。從圖5可知，它們所消耗的時間隨節點數的增加而上升，當節點數達到15后，運算時間隨快速地增加。LPR算法的運算時間的增加速度高于GA。但是，它的匹配準確度也高于GA。

圖5 場景二的運算時間

4 結束語

針對WLMP系統的位置匹配問題，提出基于最大似然估計的位置匹配算法MLLM。MLLM先通過RSSI值獲取節點間的距離，并利用距離信息構建似然函數。然后，通過LPR求解，并減少運算時間。與同類的GA、BF算法求解相比，MLLM算法引用LPR算法求解，減少了運算時間。

[1] 郝占軍, 曲南江, 黨小超. 復雜環境下一種多移動節點的WSN三維覆蓋算法[J]. 計算機工程, 2019, 45(2): 114-121.

[2] 逯志宇, 王建輝, 巴斌. 修正容積卡爾曼濾波數據域直接定位方法[J]. 航空學報, 2018, 38(25): 34-45.

[3] 江禹生, 馮硯毫, 管芳, 等. 無線傳感網非測距三維節點定位算法[J]. 西安電子科技大學學報(自然科學版), 2016, 39(5): 140-148.

[4] 吳霽桂, 陳向前. 基于RF梯級分域的室內定位算法[J]. 計算機仿真, 2017, 34(2): 384-389.

[5] 王肖玥峰, 魯照權, 周永燕, 等. 基于射頻信號強度的室內定位方法[J]. 傳感器與微系統, 2019, 38(3): 47-50.

[6] 王芳. 射頻RSS聚類與多傳感器融合的室內定位算法[J]. 計算機工程與設計, 2018, 39(6): 1553-1560.

[7] XIAO J, ZHOU Z, YI Y, et al. A survey on wireless indoor localization from the device perspective[J]. ACM Computing Surveys, 2016, 49(2): 25-30.

[8] KOTARU M, JOSHI K, BHARADIA D, et al. SpotFi: decimeter level localization using WiFi[J]. ACM SIGCOMM Computing Communication Review, 2015, 45(4): 269-282.

[9] 吳昊, 陳立全, 沙晶, 等. 一種基于特征匹配定位的SQLite數據恢復方法[J]. 南京郵電大學學報(自然科學版), 2018, 38(1): 106-112.

[10] NGUYEN C L, GEORGIOU O, YONEZAWA Y, et al. The wireless localization matching problem[J]. IEEE Internet of Things Journal, 2017, 4(5): 1312-1326.

[11] 姚錦一, 卞維剛, 任雯婷, 等. 室內定位信號強度-距離關系模型構建與分析[J]. 現代測繪, 2018, 41(1): 23-25.

[12] PENA D, FEICK R, HRISTOV H D, et al. Measurement and modeling of propagation losses in brick and concrete walls for the 900-MHz band[J]. IEEE Transaction Antennas Propagation, 2016, 51(1): 31-39.

[13] 游康勇, 楊立山, 郭文彬. 無線傳感器網絡下基于壓縮感知的多目標分層貪婪匹配定位[J]. 自動化學報, 2019, 45(3): 38-47.

[14] 徐建軍, 譚鮮明, 張潤楚. 一種懲罰最大似然方法估計混合回歸模型[J]. 中國科學: 數學, 2019, 49(8): 1159-1182.

A wireless localization matching algorithm based on linear programming relaxation

MA Peixun

（Changsha Social Work College Software Institute, Changsha 410004, China）

For positioning of devices in the Internet of Things (IOT), Maximum Likelihood- based Localization Matching (MLLM) algorithm is proposed in this paper. MLLM algorithm first measures the

Signal Strength Indicator (RSSI), and constructs the optimal matching likelihood function between position and node IDentity (ID). Then, Linear Programming Relaxation (LPR) is used to solve the problem, and then the position matching of nodes is realized. Simulation results show that, compared with brute force search, MLLM algorithm can effectively reduce the operation time and maintain a high position matching accuracy.

wireless localization; localization matching; maximum likelihood;received signal strength; linear programming

P228

A

2095-4999(2022)01-0085-05

馬佩勛. 一種基于線性規劃松弛的無線位置匹配算法[J]. 導航定位學報, 2022, 10(1): 85-89.（MA Peixun.A wireless localization matching algorithm based on linear programming relaxation[J]. Journal of Navigation and Positioning, 2022, 10(1): 85-89.）

10.16547/ j.cnki.10-1096.20220112.

2020-07-13

中國殘聯課題殘疾人輔助器具專項（2021CDPFAT-06）。

馬佩勛（1978—），男，湖南長沙人，碩士，副教授，研究方向為定位算法、數據挖掘、智能信息處理。