无线传感器网络中三边定位的聚类分析改进算法

朱齐媛,马兴灶



无线传感器网络中三边定位的聚类分析改进算法

朱齐媛1,马兴灶2*

1. 岭南师范学院 信息工程学院, 广东 湛江 524048 2. 岭南师范学院 机电工程学院, 广东 湛江 524048

为提高无线传感器网络(WSN)节点定位精度，本文提出一种基于RSSI三边定位聚类改进算法。该算法基于RSSI向量在三边测量定位的结果中引入聚类优化算法，最后得到未知节点的定位结果。数据表明，该算法在无线传感器网络未知节点的定位中定位精度和定位误差都有改进。

无线传感器网路; RSSI; 聚类分析

无线传感器网络（Wireless Sensor Network, WSN）[1]中使用一定数量的无线传感器，用特定的网络形态，传达网络覆盖区域内的被感知对象的指定信息并传输到指定目的地。通常情况下，那些低成本的、低功耗的无线传感器节点被随机抛洒到预设地监控区域，通过无线传感器网络，人们即可实时获取事件位置或信息节点位置，完成对该区域的监控。在无线传感器网络中如果不知道位置信息，那么即使是获取到了准确的传感数据，对于系统而言，分析这些数据也是无意义的[2]。由此可见，节点定位就成为无线传感器网络中对所感知的数据或者事件进行跟踪或分析的重要要求之一。

在诸多的无线传感器网络中节点定位算法中，大致分为两类，以TOA、TDOA、AOA以及RSSI为代表的与距离相关的；另一类是与距离无关，以物联网的连通性为必要条件，算法包括有质心算法、DV-Hop等[3]。目前，大部分无线传感器模块自带RSSI值，无须额外硬件，精度高、简单可靠。在实际应用的环境中却会因为系统内部（硬件物理噪声、测量参数设置）和系统外部（自然环境中的对无线电信号的散射与干涉）等因素，致使实际的测量结果与理论结果存在一定程度的误差，文献[4]就针对传输模型提出了对RSSI数据通过求其平均值和粒子滤波，获取到相对准确的RSSI值减小定位误差。

三边定位算法是目前应用最为广泛的算法之一[5]，在已知的三个信标节点位置信息，通过几何关系得到未知节点的位置。关于定位误差，很多学者提出了自己的观点，例如文献[6]提出基于聚类的多边定位算法，[7]提出基于聚类密度点的质心加权算法等。

聚类是一种源于分类学的数据分析方法，因其自由伸缩性以及高效性被广泛地应用在多个领域。在无线传感器网络中，信标节点不断接收着大量的未知节点发送过来的数据，这些数据大量并且极大可能是多元性的，如此构成的数据集恰好符合聚类算法应用的场景。本文将三边定位算法与聚类算法联合应用到无线传感器网络的节点定位，提出了基于RSSI三边的聚类改进分析定位算法，提高节点定位精度，降低节点定位误差。

1 系统模型

1.1 无线电信道模型

对数ㄧ常态分布模型是无线信号传播模型中最常用的一种。传播距离以RSSI表示接收到的以dBm为单位的无线电信号的强度。通过对数距离路径损耗模型获取节点的RSSI，式(1)为转化模型。

RSSI(d)=RSSI(0）-10log10d/0+(1)

式中发射点处接收到的信号强度值为RSSI(d)，表示信号在0的信号强度值用RSSI(0)；表示无线电信号传输路径的衰减因子，见表1；表示正态随机变量，该变量平均值为0同时标准差为。一般情况下，对测量结果影响很小。

表1说明在不同场景下值的选择范围，同时也说明即使在同一场景下，由于节点所处的具体位置可能也会有所不同，因此测距结果里就会存在一定比例的异常数据。

表 1 不同区域下路径损耗的典型值x

1.2 三边定位算法

未知节点U通过诸如RSSI测量方法获得信标节点1、2和3到未知节点U的对应距离1、2和3。以1、2和3为圆心，距离1、2和3为半径画圆，得到三个圆之间的交点，联立方程组即可获得未知节点U的定位。定位原理简图如图1所示。

图 1 三边定位原理图

图1中信标节分别为1(1,1)，2(2,2)和3(3,3)，到未知节点的RSSI距离分别为1、2和3，根据比达格斯定理，列出方程组：

未知节点U的估计坐标值为：=[AA]-1Ab (4)

定义误差以表示，设未知节点估计坐标值为则

2 KMC+_TLA算法的过程

三边定位算法是这个算法的基础，首先在二维平面上，任选三个距离信息使三边定位算法得到接近真实位置的定位结果。图2表示的是信标节点和未知节点的分布部署，在实验场景设置为100 m×100 m的正方形区域中，如果未知节点设置在该区域的中心位置（50,50），设置参数=3，信标节点和未知节点之间的距离都满足正态分布，取=0.05。

图 2 信标节点与未知节点部署

2.1 基于RSSI源数据预处理

在距离数据集{1,2,…,d}中任取3个数据通过三边定位可得到定位结果。这些结果用数据集合U表示，记作U={(x,y)|=1.2,…,}。

2.2 改进的聚类算法KMC+以及在三边定位算法中的应用过程

聚类算法-Means(MacQueen:1967)是解决众所周知的关于聚类问题的非监督学习算法。它针对指定的数据集，按照要求将其分类为预定义的数据集，适用于大数据集；缺点是值的确定，一般情况下值是随机的，然而却可能致使最后是不同的聚类结果，甚至没有解。

KMC+[9]是-Means算法一种改进，在延续经典算法优势的同时，优化对异常数据敏感问题。无线传感器网络中大量信标节点数据集中，其中由于外界环境或硬件等因素会存在一些异常数据，定位结果因此就会出现误差[8]。

具体的算法过程为：

（1）数据集U中的数据作为待聚类的样本U={(x,y)|=1.2,…,}，首先选定样本空间中任意一个样本作为第一个聚类的中心点1；

（2）计算除该点之外数据点相对这个中心点的Euclidean距离1j|=1,2,…,；

（4）计算所有其他数据点到这个两个中心的距离1j，2j|=1,2,…,，再次选出距离最远的那个点作为下一个聚类的中心点C+2；

（5）重复过程（3）和过程（4）直到第个聚类被选择出来，，确定各个聚类中心，应用经典聚类算法得到聚类结果{1,2,…,W}。

（6）对每个聚类内对聚类中心求取平均值，结果即为定位结果。

3 仿 真

本文的实验的仿真平台采用Matlab2016b，系统配置win10，64位系统，i7处理器，内存为16 G。设置100 m×100 m的检测区域，设置参数=5。避免偶然性的误差，数据测量取50次以上的平均值。随机部署节点200个（信标节点从5到50个逐步递增，递增单位5个/次），通信半径45 m，仿真结果如图3、图4所示。

图 3 平均定位误差

图 4 最大定位误差

4 讨 论

定位仿真的指标考核的目标即为定位误差。参与算法对比的数据为文献[10]提出的聚类定位法在和文献[11]提出的基于坐标修正的改进型三边定位算法。

图3、图4分别是文献[10]、文献[11]算法与本文算法的平均定位误差比较图和最大误差对比图。从图3中可以看出随着信标节点的个数的不断增加，平均定位误差在快速降低，从8.9 m~0.6 m，图4表明最大定位误差从9 m~0.9 m，比较文献[10]和[11]无论是平均定位误差还是最大定位误差均有减小20%以上。

随着信标节点的增加，显然无论从平均定位误差角度还是最大定位误差角度来看，误差变化也都基本趋向于稳定。这点说明聚类算法中值的优化选择在无线传感器网络定位中表现良好，值得借鉴。

5 结 论

针对-Means聚类算法在无线传感的定位算法的应用过程中，中心点的选择对于异常数据的敏感性问题，本文提出了一种将改进的聚类算法引入到基于RSSI的三边定位算法中。通过仿真数据表明，新的三边定位算法中改进的聚类算法里聚类中心值得选择的优秀特性有效地提高了未知节点地定位精度，降低定位误差。

[1] Bista R, Kim YK, Chang JW. A new approach for energy-balanced data aggregation in wireless sensor networks[C]//Ninth International Conference on Computer and Information Technology, South Korea: IEEE, 2009:9-15

[2] 谷洪亮,史元春.一种用于智能空间的多目标跟踪室内定位系统[J].计算机学报,2007,30(9):1603-1611

[3] 王振朝,张琦,张峰.基于RSSI测距的改进加权质心定位算法[J].电测与仪表,2014,51(21):63-67

[4] 赵珊,付敬奇.基于粒子滤波模型的RSSI测距优化研究[J].电子测量技术,2016,39(3):122-126

[5] Shuo S, Sun H, Song Y. Design of an experimental indoor position system based on RSSI[C]//2010 2nd International Conference on Information Science and Engineering Hangzhou, China:IEEE, 2010:1989-1992

[6] 孙大洋,钱志鸿,韩梦飞,等.无线传感器网络中多边定位的聚类分析改进算法[J].电子学报,2014,42(8):1601-1608

[7] 张乙竹,周礼争,唐瑞,等.基于K-means聚类点密度的WSNs加权质心定位算法[J].传感器与微系统,2015,34(7):125-127,131

[8] Akanksha K, Abhishek S. A comparative study of K-Means, K-Means++ and Fuzzy C-Means clustering algorithms" in Computational[J]. Intelligence and Communication Technology, IEEE, 2017:1-6

[9] Arthur D, Vassilvitskii S. k-Means++: the advantages of careful seeding[C]//Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orlean: Society for Industrial and Applied Mathematics, 2007:1027-1035

[10] 冯欣,张鹏,徐亚明,等.一种利用K均值聚类的无线传感器网络节点定位算法[J].武汉大学学报:信息科学 版,2013,38(10):1257-1260

[11] 郭世俊,雷虎,何淋,等.基于坐标修正的改进型三边定位算法[J].上海海事大学学报,2013,38(10):1257-1260

Improved Algorithm of Trilateral Clustering Analysis in Wireless Sensor Network

ZHU Qi-yuan1, MA Xing-zao2*

1.524048,2.524048,

In order to improve the positioning accuracy of wireless sensor network (WSN) nodes, an improved algorithm of tripartite location clustering based on RSSI（ Received Signal Strength Indicator）was proposed. This algorithm was based on the data set of the spatial RSSI vector. It introduced the clustering improvement algorithm into the results of the trilateral localization method and obtained the positioning results of the unknown nodes. The data showed that the algorithm could improve the positioning accuracy and error of the unknown nodes in WSN.

Wireless Sensor Network (WSN); Received Signal Strength Indicator; clustering analysis

TP393

A

1000-2324(2019)03-0473-04

10.3969/j.issn.1000-2324.2019.03.025

2018-04-12

2018-05-23

超声波辅助热风干燥龙眼能效评价与品质控制系统研究(2017KQNCX123);紧凑型多模带通滤波器的设计(2014B01131)

朱齐媛(1979-),女,硕士,讲师,主要从事物联网技术工作. E-mail:zhuqy1979@lingnan.edu.cn

Author for correspondence. E-mail:maxz@lingnan.edu.cn