Fingerprint positioning method based on measurement report signal clustering

doi:10.11772/j.issn.1001-9081.2023010005

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (12): 3947-3954.DOI: 10.11772/j.issn.1001-9081.2023010005

• Frontier and comprehensive applications • Previous Articles Next Articles

Fingerprint positioning method based on measurement report signal clustering

Haiyong ZHANG¹^,², Xianjin FANG¹(), Enwan ZHANG³, Baoyu LI², Chao PENG⁴, Jianxiang MU²

^1.School of Computer Science and Engineering，Anhui University of Science and Technology，Huainan Anhui 232001，China
^2.GuoChuang Cloud Technology Company Limited，Hefei Anhui 230088，China
^3.China Mobile Group Anhui Company Limited，Hefei Anhui 230088，China
^4.College of Electronic Countermeasure，National University of Defense Technology，Hefei Anhui 230037，China

Received:2023-01-04 Revised:2023-04-23 Accepted:2023-04-24 Online:2023-06-06 Published:2023-12-10
Contact: Xianjin FANG
About author:ZHANG Haiyong， born in 1992， M. S. candidate. His research interests include operator big data， machine learning.
ZHANG Enwan， born in 1982， M. S. His research interests include artificial intelligence， operator big data.
LI Baoyu， born in 1982， M. S. His research interests include artificial intelligence， operator big data.
PENG Chao， born in 1994， M. S. His research interests include complex network， artificial intelligence.
MU Jianxiang， born in 1993. His research interests include operator big data.
Supported by:
Anhui University of Science and Technology Innovation Fund(2022CX2129);Research and Development Special Fund of Institute of Environment-friendly Materials and Occupational Health （Wuhu） of Anhui University of Science and Technology(ALW2021YF08)

基于测量报告信号聚类的指纹定位方法

张海永¹^,², 方贤进¹(), 张恩皖³, 李宝玉², 彭超⁴, 穆健翔²

^1.安徽理工大学计算机科学与工程学院, 安徽淮南 232001
^2.科大国创云网科技有限公司, 合肥 230088
^3.中国移动通信集团安徽有限公司, 合肥 230088
^4.国防科技大学电子对抗学院, 合肥 230037

通讯作者: 方贤进
作者简介:张海永（1992—），男，安徽合肥人，硕士研究生，主要研究方向：运营商大数据、机器学习
张恩皖（1982—），男，安徽合肥人，硕士，主要研究方向：人工智能、运营商大数据
李宝玉（1982—），男，安徽安庆人，硕士，主要研究方向：人工智能、运营商大数据
彭超（1994—），男，安徽合肥人，硕士，主要研究方向：复杂网络、人工智能
穆健翔（1993—），男，安徽阜阳人，主要研究方向：运营商大数据。
基金资助:
安徽理工大学创新基金资助项目(2022CX2129);安徽理工大学环境友好材料与职业健康研究院（芜湖）研发专项基金资助项目(ALW2021YF08)

Abstract

Abstract:

Aiming at the problems of low positioning precision and efficiency of fingerprint positioning methods based on Weighted K-Nearest Neighbor （WKNN） and machine learning algorithms， a fingerprint positioning method based on Measurement Report （MR） signal clustering was proposed. Firstly， MR signals were divided into three attributes： indoor， road and outdoor. Then， by using the Geographic Information System （GIS） information， the grids were divided into building， road and outdoor sub-regions， and MR data with different attributes were placed in the sub-regions with corresponding attributes. Finally， with the help of K-Means clustering algorithm， MR signals in the grid were clustered and analyzed to create virtual sub-regions under the sub-region， and WKNN algorithm was used to match MR test samples. Besides， the average positioning accuracy was calculated by using the Euclidean distance， and the positioning performance of the proposed method was tested by some MR data in the production environment. Experimental results show that the proportion of 50 m positioning error of the proposed method is 71.21%， which is 2.64 percentage points higher than that of WKNN algorithm， and the average positioning error of the proposed method is 44.73 m， which is 7.60 m lower than that of WKNN algorithm. It can be seen that the proposed method has good positioning precision and efficiency， and can meet the positioning requirements of MR data in the production environment.

Key words: Measurement Report (MR), positioning, signal clustering, Weighted K-Nearest Neighbor (WKNN) algorithm, Euclidean distance

摘要：

针对基于加权K最近邻（WKNN）和机器学习算法的指纹库定位方法存在精度和定位效率较低的问题，提出一种基于测量报告（MR）信号聚类的指纹定位方法。首先，把MR信号分为室内、道路和室外这3种属性；其次，利用地理信息系统（GIS）信息将栅格分为建筑物、道路和室外子区域，并将不同属性的MR数据落入对应的属性子区域；最后，借助K均值（K-Means）聚类算法对栅格内的MR信号进行聚类分析，以创建子区域下的虚拟子区域，并采用WKNN算法对MR测试样本进行匹配。此外，利用欧氏距离计算平均定位精度，并通过生产环境的一些MR数据测试了所提方法的定位性能。实验结果表明，所提方法的50 m定位误差占比为71.21%，相较于WKNN算法提升了2.64个百分点；平均定位定位误差为44.73 m，相较于WKNN算法降低了7.60 m。所提方法具备良好的定位精度和效率，可满足生产环境中MR数据的定位需求。

关键词: 测量报告, 定位, 信号聚类, 加权K最近邻算法, 欧氏距离

CLC Number:

TP391.9

Haiyong ZHANG, Xianjin FANG, Enwan ZHANG, Baoyu LI, Chao PENG, Jianxiang MU. Fingerprint positioning method based on measurement report signal clustering[J]. Journal of Computer Applications, 2023, 43(12): 3947-3954.

张海永, 方贤进, 张恩皖, 李宝玉, 彭超, 穆健翔. 基于测量报告信号聚类的指纹定位方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3947-3954.

Figures/Tables 14

Fig.1 Overall framework of MR signal clustering

Tab. 1 Explanation of symbols used in this paper

符号	说明
MR	测量报告
CGI	主、邻基站标识，全球小区识别码
TA	时间提前量
RSRP	主、邻基站信号强度（参考信号接收功率）
LON	经度
LAT	纬度
H	基站的高度
S	基站与手机终端的水平距离
d	基站与手机终端的欧氏距离
$D m i n$ 、 $D m a x$	基站与手机终端距离的理论最小值和最大值
Min_Ts、Max_Ts	TA值对应的最小和最大采样时间，可以计算TA值对应的最小和最大距离
r	采样点合理率，用来评判样本数据准确性
p	子栅格内MR样本缺失基站CGI占该区域内样本的比例
AVG_RSRP	子栅格内基站信号强度的平均值
w	填补MR样本点内无基站信号强度的权重
$z 1$ ~ $z n$	预设值，表示p的范围
$A 1$ ~ $A n$	预设值，p不同范围对应的信号强度权重值
ADD_RSRP	填补MR样本点内无对应基站电平值
GRID_ID	划分栅格ID
GRID_SUB_ID	划分子栅格ID
GRID_SUB_TYPE	子栅格类型（室内、道路和室外）
GRID_SUB_ORDER	封闭子栅格经纬度序列
$p a v g$	平均定位精度
$L i$	指纹库定位与实际位置的距离偏差
$N 25$ 、 $N 50$ 、 $N 75$ 、 $N 100$	分别代表定位误差在25 m、50 m、75 m、100 m 范围内的点数
$p 25$ 、 $p 50$ 、 $p 75$ 、 $p 100$	分别代表定位误差在25 m、50 m、75 m、100 m 范围内的占比
GROUP_ID	虚拟子区域ID（子区域聚类中心ID）

Tab. 1 Explanation of symbols used in this paper

符号	说明
MR	测量报告
CGI	主、邻基站标识，全球小区识别码
TA	时间提前量
RSRP	主、邻基站信号强度（参考信号接收功率）
LON	经度
LAT	纬度
H	基站的高度
S	基站与手机终端的水平距离
d	基站与手机终端的欧氏距离
$D m i n$ 、 $D m a x$	基站与手机终端距离的理论最小值和最大值
Min_Ts、Max_Ts	TA值对应的最小和最大采样时间，可以计算TA值对应的最小和最大距离
r	采样点合理率，用来评判样本数据准确性
p	子栅格内MR样本缺失基站CGI占该区域内样本的比例
AVG_RSRP	子栅格内基站信号强度的平均值
w	填补MR样本点内无基站信号强度的权重
$z 1$ ~ $z n$	预设值，表示p的范围
$A 1$ ~ $A n$	预设值，p不同范围对应的信号强度权重值
ADD_RSRP	填补MR样本点内无对应基站电平值
GRID_ID	划分栅格ID
GRID_SUB_ID	划分子栅格ID
GRID_SUB_TYPE	子栅格类型（室内、道路和室外）
GRID_SUB_ORDER	封闭子栅格经纬度序列
$p a v g$	平均定位精度
$L i$	指纹库定位与实际位置的距离偏差
$N 25$ 、 $N 50$ 、 $N 75$ 、 $N 100$	分别代表定位误差在25 m、50 m、75 m、100 m 范围内的点数
$p 25$ 、 $p 50$ 、 $p 75$ 、 $p 100$	分别代表定位误差在25 m、50 m、75 m、100 m 范围内的占比
GROUP_ID	虚拟子区域ID（子区域聚类中心ID）

Fig.2 Signal propagation distance model

Tab. 2 TA relations

TA值	Min_Ts / Ts	Max_Ts / Ts
0	0	16
1	16	32
︙	︙	︙
11	176	192
12	192	224
︙	︙	︙
37	992	1 024
38	1 024	1 280
︙	︙	︙
41	1 792	2 048
42	2 048	3 072
43	3 072	4 096
44	4 096	︙

Fig.3 Grid division results

Tab. 3 Relations between w and p

条件	w
$p > z 1$	$A 1$
$z 2 < p ≤ z 3$	$A 2$
︙	︙
$p ≤ z n$	$A n$

Tab. 3 Relations between w and p

条件	w
$p > z 1$	$A 1$
$z 2 < p ≤ z 3$	$A 2$
︙	︙
$p ≤ z n$	$A n$

Fig. 4 MR original data

Fig.5 Test area

Tab.4 Statistics of APE

实验序号	方案A	方案B	方案C	方案D
均值	52.33	53.32	48.44	44.73
1	52.66	53.62	48.50	43.79
2	52.33	52.59	48.68	44.42
3	52.64	53.89	47.95	45.77
4	51.69	52.85	49.01	45.38
5	51.73	53.38	48.31	44.35
6	52.93	53.59	48.19	44.67

Tab.5 Analysis of error results of different schemes

方案	总点数	$N 25$	$N 50$	$N 75$	$N 100$	$p 25$ /%	$p 50$ /%	$p 75$ /%	$p 100$ /%
A	62 401	22 000	42 789	51 356	55 466	35.26	68.57	82.30	88.89
B	62 401	27 356	40 756	48 784	53 252	43.84	65.31	78.18	85.34
C	62 401	32 346	42 823	50 291	54 056	51.84	68.63	80.59	86.63
D	62 401	32 849	44 436	51 645	55 017	52.64	71.21	82.76	88.17

Tab.5 Analysis of error results of different schemes

方案	总点数	$N 25$	$N 50$	$N 75$	$N 100$	$p 25$ /%	$p 50$ /%	$p 75$ /%	$p 100$ /%
A	62 401	22 000	42 789	51 356	55 466	35.26	68.57	82.30	88.89
B	62 401	27 356	40 756	48 784	53 252	43.84	65.31	78.18	85.34
C	62 401	32 346	42 823	50 291	54 056	51.84	68.63	80.59	86.63
D	62 401	32 849	44 436	51 645	55 017	52.64	71.21	82.76	88.17

Fig.6 Comparison of clustering positioning results ofdifferent schemes

Tab.6 MR positioning results of different schemes

方案	平均误差	中值误差	90%误差
A	52.33	32.16	106.85
B	53.32	31.39	134.95
C	48.44	23.19	124.66
D	44.73	22.00	113.92

Tab. 7 Analysis of MR positioning efficiency

日期	时间/min	日期	时间/min
2023-03-01	35	2023-03-05	49
2023-03-02	51	2023-03-06	40
2023-03-03	52	2023-03-07	46
2023-03-04	57

Fig. 7 MR positioning application examples

References 25

1	DEL PERAL-ROSADO J D， RAULEFS R， LÓPEZ-SALCEDO J A， et al. Survey of cellular mobile radio localization methods： from 1G to 5G［J］. IEEE Communications Surveys and Tutorials， 2018， 20（2）：1124-1148. 10.1109/comst.2017.2785181
2	武青. 基于指纹库和无线测量报告的用户定位系统［D］. 北京：北京邮电大学， 2021：1-2.
	WU Q. User localization system based on fingerprint database and measurement report［D］. Beijing： Beijing University of Posts and Telecommunications， 2021：1-2.
3	康军，黄山，段宗涛，等.时空轨迹序列模式挖掘方法综述［J］. 计算机应用， 2021， 41（8）： 2379-2385. 10.11772/j.issn.1001-9081.2020101571
	KANG J， HUANG S， DUAN Z T， et al. Review of spatio-temporal trajectory sequence pattern mining methods［J］. Journal of Computer Applications， 2021， 41（8）： 2379-2385. 10.11772/j.issn.1001-9081.2020101571
4	元广杰，李小东，江照意，等.路测数据驱动的移动终端定位方法［J］. 计算机应用， 2016， 36（12）： 3515-3520. 10.11772/j.issn.1001-9081.2016.12.3515
	YUAN G J， LI X D， JIANG Z Y， et al. Mobile terminal positioning method driven by road test data［J］. Journal of Computer Applications， 2016， 36（12）： 3515-3520. 10.11772/j.issn.1001-9081.2016.12.3515
5	张齐林，李方伟，王明月.基于时间反演的到达时间定位［J］. 计算机应用， 2021， 41（3）： 820-824. 10.16798/j.issn.1003-0530.2021.05.020
	ZHANG Q L， LI F W， WANG M Y. Time of arrival positioning based on time reversal［J］. Journal of Computer Applications， 2021， 41（3）： 820-824. 10.16798/j.issn.1003-0530.2021.05.020
6	LIU Y， GUO F. Performance analysis of TDOA and FDOA estimation for pulse signals［J］. International Journal of Antennas and Propagation， 2022， 2022： No.7672417. 10.1155/2022/7672417
7	DÍEZ-GONZÁLEZ J， ÁVAREZ R， VERDE P， et al. Analysis of reliable deployment of TDOA local positioning architectures［J］. Neurocomputing， 2022， 484： 149-160. 10.1016/j.neucom.2021.12.074
8	CHANG A C， CHANG J C. Robust mobile location estimation using hybrid TOA/AOA measurements in cellular systems［J］. Wireless Personal Communications， 2012， 65（1）： 1-13. 10.1007/s11277-011-0224-8
9	LI Y Y， QI G Q， SHENG A D. Performance metric on the best achievable accuracy for hybrid TOA/AOA target localization［J］. IEEE Communications Letters， 2018， 22（7）： 1474-1477. 10.1109/lcomm.2018.2833544
10	ZHOU M， LI Y， TAHIR M J， et al. Integrated statistical test of signal distributions and access point contributions for Wi-Fi indoor localization［J］. IEEE Transactions on Vehicular Technology， 2021， 70（5）： 5057-5070. 10.1109/tvt.2021.3076269
11	WANG B， GAN X， LIU X， et al. A novel weighted KNN algorithm based on RSS similarity and position distance for Wi-Fi fingerprint positioning ［J］. IEEE Access， 2020， 8： 30591-30602. 10.1109/access.2020.2973212
12	VO Q D， DE P. A survey of fingerprint-based outdoor localization［J］. IEEE Communications Surveys and Tutorials， 2016， 18（1）： 491-506. 10.1109/comst.2015.2448632
13	ZHANG L， CHU X， ZHAI M. Machine learning-based integrated wireless sensing and positioning for cellular network［J］. IEEE Transactions on Instrumentation and Measurement， 2023， 72： No.5501011. 10.1109/tim.2022.3224513
14	ZHANG Y， RAO W， YUAN M， et al. Context-aware telco outdoor localization ［J］. IEEE Transactions on Mobile Computing， 2022， 21（4）： 1211-1225. 10.1109/tmc.2020.3025127
15	ZHANG Y， DING A Y， OTT J， et al. Transfer learning-based outdoor position recovery with cellular data ［J］. IEEE Transactions on Mobile Computing， 2021， 20（5）： 2094-2110. 10.1109/tmc.2020.2968899
16	王宁，刘旭峰，贾元启，等. 基于机器学习的LTE-MR定位算法研究与应用范例［J］. 北京交通大学学报， 2021， 45（2）： 87-94， 110. 10.11860/j.issn.1673-0291.20200088
	WANG N， LIU X F， JIA Y Q， et al. Algorithm design and application example of machine learning-based LTE-MR positioning technique ［J］. Journal of Beijing Jiaotong University， 2021， 45（2）： 87-94， 110. 10.11860/j.issn.1673-0291.20200088
17	周志超，冯毅，夏小涵，等.基于移动蜂窝网的机器学习室外指纹定位方案［J］. 电信科学， 2021， 37（8）： 85-95. 10.11959/j.issn.1000-0801.2021201
	ZHOU Z C， FENG Y， XIA X H， et al. Outdoor location scheme with fingerprinting based on machine learning of mobile cellular network［J］. Telecommunications Science， 2021， 37（8）： 85-95. 10.11959/j.issn.1000-0801.2021201
18	TORIL M， WILLE V， LUNA-RAMÍREZ S， et al. Characterization of radio signal strength fluctuations in road scenarios for cellular vehicular network planning in LTE ［J］. IEEE Access， 2021， 9： 33120-33131. 10.1109/access.2021.3060995
19	MICHELI D， MURATORE G， VANNELLI A， et al. Rain effect on 4G LTE in-car electromagnetic propagation analyzed through MDT radio data measurement reported by mobile phones［J］. IEEE Transactions on Antennas and Propagation， 2021， 69（12）： 8641-8651. 10.1109/tap.2021.3090505
20	中国通信标准化协会. 数字蜂窝移动通信网无线操作维护中心（OMC-R）测量报告技术要求： YD/T 2824—2015 ［S］. 北京：中国标准出版社， 2015：7-8.
	China Communications Standards Association. digital cell mobile communications network OMC-R measurement report technical specification： YD/T 2824—2015 ［S］. Beijing： Standards Press of China， 2015：7-8.
21	科大国创软件股份有限公司. 一种基于GIS数据进行栅格子区域划分的方法及装置： 201811625700.4［P］. 2019-05-17.
	GuoChuang Cloud Technology Company Limited. A method and equipment for dividing grid areas based on GIS data set： 201811625700.4 ［P］. 2019-05-17.
22	刘大有，陈慧灵，齐红，等.时空数据挖掘研究进展［J］. 计算机研究与发展， 2013， 50（2）： 225-239. 10.7544/issn1000-1239.2013.20110235
	LIU D Y， CHEN H L， QI H， et al. Advances in spatiotemporal data mining［J］. Journal of Computer Research and Development， 2013， 50（2）： 225-239. 10.7544/issn1000-1239.2013.20110235
23	张平，陈昊.面向5G的定位技术研究综述［J］. 北京邮电大学学报， 2018， 41（5）： 1-12.
	ZHANG P， CHEN H. A survey of positioning technology for 5G ［J］. Journal of Beijing University of Posts and Telecommunications， 2018， 41（5）： 1-12.
24	DWIVEDI S， SHREEVASTAV R， MUNIER F， et al. Positioning in 5G networks［J］. IEEE Communications Magazine， 2021， 59（11）： 38-44. 10.1109/mcom.011.2100091
25	KANHERE O， RAPPAPORT T S. Position location for futuristic cellular communications： 5G and beyond［J］. IEEE Communications Magazine， 2021， 59（1）： 70-75. 10.1109/mcom.001.2000150

[1]	Xiaohui CHENG, Yuntian HUANG, Ruifang ZHANG. Lightweight infrared road scene detection model based on multiscale and weighted coordinate attention [J]. Journal of Computer Applications, 2024, 44(6): 1927-1934.
[2]	Lin SUN, Menghan LIU. K-means clustering based on adaptive cuckoo optimization feature selection [J]. Journal of Computer Applications, 2024, 44(3): 831-841.
[3]	Meiyu CAI, Runzhe ZHU, Fei WU, Kaiyu ZHANG, Jiale LI. Cross-view matching model based on attention mechanism and multi-granularity feature fusion [J]. Journal of Computer Applications, 2024, 44(3): 901-908.
[4]	Yi WANG, Shenglei PEI, Yu WANG. Indoor positioning method of multi-fingerprint database based on channel state information and K-means-SVR [J]. Journal of Computer Applications, 2023, 43(5): 1636-1640.
[5]	Yijian ZHAO, Li LIN, Qianqian WANG, Peng WEN, Dong YANG. Trajectory prediction of sea targets based on geodetic distance similarity calculation [J]. Journal of Computer Applications, 2023, 43(11): 3594-3598.
[6]	Xueqin CHEN, Tao TAO, Zhongwang ZHANG, Yilei WANG. Long short-term session-based recommendation algorithm combining paired coding scheme and two-dimensional conventional neural network [J]. Journal of Computer Applications, 2022, 42(5): 1347-1354.
[7]	Ne LI, Guangzhu XU, Bangjun LEI, Guoliang MA, Yongtao SHI. Logo recognition algorithm for vehicles on traffic road [J]. Journal of Computer Applications, 2022, 42(3): 810-817.
[8]	Bingqi SHEN, Zhiming ZHANG, Shaolong SHU. UWB-VIO integrated indoor positioning algorithm for mobile robots [J]. Journal of Computer Applications, 2022, 42(12): 3924-3930.
[9]	ZHANG Qilin, LI Fangwei, WANG Mingyue. Time of arrival positioning based on time reversal [J]. Journal of Computer Applications, 2021, 41(3): 820-824.
[10]	HUI Fei, XING Meihua, GUO Jing, TANG Shuyu. Forward collision warning strategy based on vehicle-to-vehicle communication [J]. Journal of Computer Applications, 2021, 41(2): 498-503.
[11]	ZHANG Chi, LI Zhuhong, LIU Zhou, SHEN Weiming. Unmanned aerial vehicle image positioning algorithm based on scene graph division [J]. Journal of Computer Applications, 2021, 41(10): 3004-3009.
[12]	ZHANG Jianming, SHI Yuanhao, XU Zhengyi, WEI Jianming. Adaptive UWB/PDR fusion positioning algorithm based on error prediction [J]. Journal of Computer Applications, 2020, 40(6): 1755-1762.
[13]	WANG Yajie, ZHANG Yunbo, WU Yanyan, DING Aodong, QI Bingzhi. General chess piece positioning method under uneven illumination [J]. Journal of Computer Applications, 2020, 40(12): 3490-3498.
[14]	ZHANG Bang, ZHU Jinxin, XU Zhengyi, LIU Pan, WEI Jianming. Bayesian network-based floor localization algorithm [J]. Journal of Computer Applications, 2019, 39(8): 2468-2474.
[15]	LUO Yuan, YUN Mingjing, WANG Yi, ZHAO Liming. Human fatigue detection based on eye information characteristics [J]. Journal of Computer Applications, 2019, 39(7): 2098-2102.

Fingerprint positioning method based on measurement report signal clustering

基于测量报告信号聚类的指纹定位方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 25

Related Articles 15

Recommended Articles

Metrics