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

馬佩勛

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

馬佩勛

（長沙民政職業(yè)技術(shù)學院 軟件學院，長沙 410004）

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

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

0 引言

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

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

1 問題描述及傳播模型

1.1 無線位置匹配問題

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

圖1 WLMP系統(tǒng)

1.2 傳播模型

1.2.1 LoS傳播模型

目前，對數(shù)-距離傳播模型廣泛應(yīng)用于不同環(huán)境[11]。用弗里斯（Friss）等式表述與距離關(guān)系為

1.2.2 非視距NLoS傳播模型

當無線信號穿過墻時，與距離關(guān)系[12]為

1.2.3 噪聲變量

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

2 MLLM算法

2.1 似然函數(shù)的計算

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

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

傳播模型服從對數(shù)-正態(tài)模型，變量服從高斯分布，*可簡化為

2.2 MLLM算法

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

2.2.1 目標函數(shù)

整數(shù)線性規(guī)劃（integer linear programming, ILP）目標函數(shù)為

2.2.2 基于LPR求解

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

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

3 性能仿真

3.1 仿真場景

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

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

表1 兩個場景的仿真參數(shù)

3.2 場景一環(huán)境下的匹配準確率和運算時間

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

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

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

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

圖3 場景一的運算時間

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

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

3.3 場景二環(huán)境下的匹配準確率和運算時間

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

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

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

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

圖5 場景二的運算時間

4 結(jié)束語

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

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

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

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

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

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

[6] 王芳. 射頻RSS聚類與多傳感器融合的室內(nèi)定位算法[J]. 計算機工程與設(shè)計, 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數(shù)據(jù)恢復方法[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] 姚錦一, 卞維剛, 任雯婷, 等. 室內(nèi)定位信號強度-距離關(guān)系模型構(gòu)建與分析[J]. 現(xiàn)代測繪, 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] 游康勇, 楊立山, 郭文彬. 無線傳感器網(wǎng)絡(luò)下基于壓縮感知的多目標分層貪婪匹配定位[J]. 自動化學報, 2019, 45(3): 38-47.

[14] 徐建軍, 譚鮮明, 張潤楚. 一種懲罰最大似然方法估計混合回歸模型[J]. 中國科學: 數(shù)學, 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

馬佩勛. 一種基于線性規(guī)劃松弛的無線位置匹配算法[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

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

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