一种基于线性规划松弛的无线位置匹配算法

马佩勋

一种基于线性规划松弛的无线位置匹配算法

马佩勋

（长沙民政职业技术学院 软件学院，长沙 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—），男，湖南长沙人，硕士，副教授，研究方向为定位算法、数据挖掘、智能信息处理。