位置感知的移动节点聚集检测方法研究

郭晓雷，秘建宁，张宇，张欣海

(中国电子科学研究院，北京　100041)



工程与应用

位置感知的移动节点聚集检测方法研究

郭晓雷，秘建宁，张宇，张欣海

(中国电子科学研究院，北京100041)

移动节点聚集检测是无线网络应用的一项新内容。为提高大规模目标区域内节点聚集检测的效率和准确度，提出一种基于位置感知和密度聚类的移动节点聚集检测方法。首先，通过无线定位技术来获取移动节点的位置坐标，此过程中，有偏最小二乘法可用于降低距离估计误差对定位的影响；其次，在将目标区域进行网格划分的基础上，采用密度聚类方法搜索节点聚集簇，并对相邻网格的节点相邻聚集簇进行合并；最后，输出节点聚集簇的区域及其包含的节点信息。仿真试验验证了方法在实际应用中的可行性和有效性。

节点聚集检测；无线定位；聚类分析

0　引　言

随着无线通信、微机电系统、数字电子等技术的发展，各种移动无线网络的研究和应用呈现出高速增长的态势，目前最广泛应用的有移动通信网、无线局域网(WLAN)和各类自组织(Ad hoc)网络。这些网络除了提供最基本的无线通信和网络接入功能外，还衍生出多种典型应用，例如定位跟踪、实时监控、智能家居、交通管理、物流调配等[1,2]。

移动节点聚集检测技术作为无线网络研究的一项新内容，对于无线网络应用的丰富和扩展有着重要意义。例如，在公共安全领域[3]，基于手机与使用者之间普遍存在的“人机一体”现象，利用手机聚集检测技术，可实现对重要场所人群的实时监测和有效管理，自动判断人群聚集情况并及早发现人群行为异常的预兆，从而及时采取解决措施，避免灾祸的发生；在城市交通管理领域，结合车联网技术[4]，道路上行驶的每辆车可以看作是一个移动节点，这样车联网移动节点聚集检测技术可用于对道路交通流量的实时监测，及时发现拥堵路段，协助管理部门进行交通疏导，并可为驾驶员提供合理行车路线；在动物习性研究中，研究人员将特定的传感器节点安装在研究对象上，通过节点间的相互协作组成移动传感网[5](一种特殊的Ad hoc网络)，这样通过判断传感网节点的聚集状态可以迅速确定生物种群的栖息地点，并实时监测种群的运动状态和各种生理信息。上述应用中，行人、车辆和动物本质上都是无线节点的移动载体，它们聚集状态监测可通过移动节点聚集检测技术来实现。

目前，关于移动节点聚集状态监测的传统方法主要有人工统计、机械统计、电子计数、射频识别等[6]，但这些方法普遍存在应用范围受限、实时性较差、系统建设成本高等问题，不适用于节点数目较多或目标区域开放的情况。近年来，基于图像识别的群体密度识别方法[7]逐渐兴起，理想情况下这种方法可以实现群体密度全天时和全覆盖统计，但实际中其受环境条件的影响较大(例如晚间判定效果较差)，且存在选点布控复杂、设施投资较大、实时性差、计算复杂度高等问题，此方法的工程化应用前景有待进一步探讨。

为解决现有方法存在的问题，提高移动节点聚集检测的效率和准确度，本文提出一种基于位置感知的移动节点聚集检测方法，在利用无线定位技术获得节点位置的基础上，通过网格划分和密度聚类的方式对节点的聚集状态进行检测，当存在节点数目较多的聚集簇时，可快速输出节点聚集区域的位置信息。本方法计算复杂度低、准确度高且实时较好，可满足多种应用领域对移动节点聚集状态监测的需求。

1　无线定位技术

在进行节点聚集状态或范围检测之前，首先需要收集目标区域内节点的位置信息，而移动节点位置的感知可借助无线定位技术来实现。无线定位技术主要利用无线信号的某些参数特征来判断节点的绝对/相对位置，根据定位结果类型的不同，可分为物理定位和符号定位两种[8]，前者需要得到被定位目标具体的物理位置，如(39°55′45.79″N, 116°26′27.56″E)，后者仅需得到定位目标的符号位置或相对位置，如“某个节点在工人体育场中”或者“某个节点在场馆正门前方10米处”。在实际应用中，两种定位结果可以相互转化，例如在人群聚集监测(交通监测)中，可根据高密度人群(车辆)所处的物理位置，迅速确定人群聚集(交通拥堵)发生的建筑物(街区)，从而协助相关人员进行快速响应。

根据定位过程中所使用的无线信号参数特征的不同，定位技术也可分为基于接收信号强度(Received Signal Strength Indication, RSSI)的定位、基于到达时间(Time of Arrival, TOA)的定位、基于到达时间差(Time Difference of Arrival, TDOA)的定位、基于到达角度(Angle of Arrival, AOA)的定位等。前面三种定位技术首先需要通过RSSI、TOA或TDOA方法估计出节点间的距离，当然待定位节点可以获得自身到3个(二维定位)或4个(三维定位)参考节点(自身位置已知的节点)的距离后，就可以采用一定的数学方法计算出自身的位置坐标。在某些场合下，当待定位节点测距范围内的参考节点数量不足时，可采用节点间的最小多跳距离来代替欧式距离[9]。以图1为例，待定位节点O可直接测量出自身到参考节点A、B、C的距离分别为do1、do2和do3，由于参考节点D不在节点O的测距范围内，两者之间的距离do4可通过OE和ED的距离和(多跳距离)来近似，即do4≈doe+ded。

图1　节点定位示意图

记参考节点A、B、C、D的位置坐标分别为X1, X2, X3, X4，这样可建立求解待定位节点坐标Xo的欧式方程组(其中n= 4)：

(1)

求解上述方程组采用最广泛的方法是最小二乘(Least Square, LS)算法，LS算法在节点间的距离估计误差服从均值为0的高斯分布时，所得到的估计值是的极大似然最优估计。当距离估计误差分布的均值不为0(有偏差)时[10]，可采用有偏最小二乘法来计算待定位节点的坐标估计值：

(2)

其中，n为参考节点的数目，b为距离估计误差分布的均值。

2　节点聚集检测方法

当获得目标区域内移动节点的位置信息后，可借鉴基于网格和密度的聚类方法[11, 12]来检测节点的聚集状态；如果存在密度较高的节点聚集簇时，则输出节点聚集的区域范围。具体方法包括三个主要步骤：

步骤一、对目标区域进行网格划分。首先，确定长方形子网格长度和宽度取值，基于此将目标区域均匀划分为J子网格Gk(j=1, 2, …,J)；当目标区域不规则时，可根据其边界坐标将其扩展为一个规则的长方形区域，然后再对其进行网格划分；在此过程中，将不足一个网格面积的子区域当作一个子网格；最后，统计并记录每个子网格中的移动节点ID和位置信息。

步骤二、通过密度聚类方式搜索每个子网格中的节点聚集簇。首先，统计出每个子网格中节点的密度信息(每个节点邻域内包含的其他节点数目)，找出核心节点(自身密度不低于阈值T的节点)和次核心节点(处于核心节点邻域内但自身密度小于阈值T的节点)；然后，从任意核心节点开始，通过密度聚类的方式找出一个完整的节点聚集簇；当核心节点遍历完全后，输出子网格中所有节点聚集簇的信息。具体步骤如下：

① 设定节点邻域半径ε和密度阈值T；

② 计算目标区域内所有节点Na的密度ma；当Na处于子网格边界附近时，需要同时统计其所处子网格和相邻子网格中的所有相邻节点来计算密度ma；如果ma≥T，则Na为核心节点，并将Na标记为未处理的核心节点；设定迭代次数j= 1；

③ 对于子网格Gj，取Gj中节点聚集簇数目Fj=0；

④ 判断子网格Gj中是否存在未处理的核心节点；如果Gj中存在未处理的核心节点，取Fj=Fj+ 1，转到下一步；如果不存在未处理的核心节点，转到步骤⑨；

⑤ 取子网格Gj中的任意未处理的核心节点Na，将Na和其邻域内的所有节点归于同一个簇CFj，并将Na标记为已处理的核心节点；

⑥ 搜索簇CFj中未处理的核心节点，将其邻域内的所有节点添加到簇CFj中；

⑦ 重复步骤⑥，直到簇CFj中的所有核心节点都被标记为已处理的核心节点；

⑧ 完成簇CFj的扩展，转到步骤④；

⑨ 完成子网格Gj的搜索；如果Fj>0，输出Gj的所有节点聚集簇及聚集簇数目Fj；

⑩ 取j=j+1，如果j≤J，转到步骤③；否则，结束子网格中节点聚集簇的搜索。

步骤三、对节点相邻聚集簇进行合并。统计出每个子网格中的节点聚集簇之后，根据簇中核心节点间的连通度关系确定相邻子网格中的节点相邻聚集簇，并对其进行合并。其中，节点相邻聚集簇是指存在连通核心节点的一对节点聚集簇，而连通核心节点是指自身邻域包含对方且自身又处于对方邻域内的一对核心节点。

最后，输出目标区域内节点数目大于一定阈值的节点聚集簇Ck的区域信息[XCk,lCk,wCk] (k= 1, 2, …,K)及Ck所包含节点的ID。其中，XCk表示聚集簇Ck所在的长方形区域的中心坐标，lCk和wCk分别表示此区域的长度和宽度。

3　仿真验证

本部分通过仿真试验来验证论文方法的有效性。如图2所示，在1000×1000的目标区域内部署200个移动节点(节点ID分别为1-200)，所有节点在某一时刻的位置坐标可通过无线定位技术来获得，本试验主要在位置已知的情况下对节点的聚集状态进行检测。试验中，目标区域被划分的子网格数目J=4，即子网格{Ga, Gb, Gc, Gd}的边长都为500；密度聚类时，取节点邻域半径ε=50和密度阈值T=4。

图2　节点分布示意图

在图2所示的节点分布情况下，各子网格共检测到6个节点聚集簇(长方形子区域)，记作{C1, C2, C3, C4, C5, C6}，如图3所示。在子网格Ga中，检测到1个节点聚集簇C1，其区域信息为[(477.9, 521.6) ,40.8, 39.7]，包含8个节点；在子网格Gb中，检测到2个节点聚集簇C2和C3，区域信息分别为[(535.2, 542.2), 83.4, 59.4]和[(592.7, 744.3), 61.9, 61.8]，分别包含9个和5个节点；在子网格Gc中，检测到的2个节点聚集簇C4和C5的区域信息分别为[(26.2, 408.7), 70.3, 38.5]和[(458.6, 471.8), 55.4, 77.0]，分别包含5个和20个节点；在子网格Gd中，仅检测到1个节点聚集簇C6，区域信息为[(524.9, 446.4) ,105.3, 46.9]，包含19个节点。

图3　各子网格检测到的节点聚集簇示意图

当检测出每个子网格中的节点聚集簇后，可对相邻子网格中的节点相邻聚集簇进行合并。在图3中，节点聚集簇C1, C2, C5和C6的地理位置相邻，且之间存在连通核心节点，因此，可将这四个簇合并成一个大簇Cfinal(如图4所示)，其他两个簇C3和C4保持不变。Cfinal所在区域的中心为(492.5, 488.8)，接近目标区域的中心，区域的长度和宽度分别约为190.1和144.8。图5为Cfinal所在区域的放大图，这个簇共包括56个节点，其ID分别为{1, 3, 14, 18, 22, 27, 29, 32, 34, 38, 44, 46, 47, 49, 52, 55, 58, 61, 65, 67, 68, 70, 75, 78, 79, 91, 95, 96, 101, 104, 111, 112, 113, 114, 117, 119, 126, 127, 131, 132, 136, 140, 141, 142, 144, 147, 148, 160, 165, 169, 170, 171, 175, 184, 185, 194}。

图4　节点相邻聚集簇合并结果图

图5　节点聚集区域示意图

4　结　语

移动节点聚集检测技术在公共安全、交通管理、生物监测等领域具有广阔的应用前景。随着无线网络技术的发展，无线定位技术逐渐成熟。利用无线定位技术所提供的位置估计信息，提出一种基于网格划分和密度聚类的一种移动节点聚集感知方法。节点位置能否准确感知对本方法有效性的影响较大，为提升无线定位的精度，可采用有偏最小二乘法来计算节点坐标的估计值。本方法计算复杂度低、速度快且准确度较高，在目标区域较大或移动节点数目较多的应用场景下具有更显著的优势。如何降低无线定位误差对于本方法的影响是下一阶段研究要考虑的问题之一。

[1]汪涛. 无线网络技术导论[M]. 北京: 清华大学出版社, 2008.

[2]胡杰, 张兴, 王文博. 无线网络中的业务行为及业务容量—概念、模型及发展[J]. 中国电子科学研究院学报, 2012, 7(2): 168-173.

[3]张仕学, 李石君, 余伟, 等. 突发事件人群异常聚集热点区域预测[J]. 中国安全科学学报, 2015, 25(9): 159-164.

[4]汪成亮, 张晨. 面向车联网的交通流参数检测[J]. 2012, 48(23): 212-218.

[5]孙利民, 李建中, 陈渝等. 无线传感器网络[M]. 北京: 清华大学出版社, 2005.

[6]胡成, 李伟, 姚晓晖. 为了这样的灾难不再发生—城市人群聚集风险的监测与预警[J]. 科技智囊, 2011, 1: 74-79.

[7]常庆龙, 夏洪山. 利用归一化前景和二维联合熵的人群聚集检测方法[J]. 武汉大学学报(信息科学版), 2013, 9(38): 1126-1130.

[8]Hightower J, Boriello G. Location Systems for Ubiquitous Computing. Computer, 2001, 34(8): 57-66.

[9]Niculescu D, Nath B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication Systems, 2003, 22(1/4): 267-280.

[10]Picard J S, Weiss A J. Localization of Networks Using Various Ranging Bias Models[J]. Wireless Communications and Mobile Computing, 2008, 8(5): 553-562.

[11]贺玲, 吴玲达, 蔡益朝. 数据挖掘中的聚类算法综述[J]. 计算机应用研究, 2007, 1: 10-13.

[12]Han J, Kamber M, Pei J. Data Mining: Concepts and Techniques, Third Edition[M]. Burlington: Morgan Kaufmann, 2011.

郭晓雷(1983—)，男，河北人，博士，主要研究方向为网络与信息系统等；E-mail：guoxiaolei247@hotmail.com

秘建宁(1979—)，男，河北人，博士，主要研究方向为信息系统总体设计技术等；

张宇(1987—)，男，吉林人，主要研究方向为通信网络仿真等；

张欣海(1975—)，男，辽宁人，高级工程师，主要研究方向为数据挖掘技术等。

Study on the Location-aware Based Mobile Node Aggregation Detection Method

GUO Xiao-lei, BI Jian-ning, ZHANG Yu, ZHANG Xin-hai

(China Academy of Electronics and Information Technology, Beijing 100041, China)

Mobile node aggregation detection is a new application of wireless networks. To improve the efficiency and accuracy of node aggregation detection in large area, a location-aware and density clustering based detection method is proposed. Firstly, the location coordinates of mobile nodes are obtained by wireless localization technology, in which, the biased least square method can be used to reduce the effect of distance estimation errors on localization. Secondly, the target area is divided into several sub-grids. On the basis, density clustering approach is utilized to search node aggregation clusters. Then, the aggregation clusters with neighboring core nodes in adjacent grids are merged into a bigger one. Finally, the regional information and relevant nodes of aggregation clusters are outputted as detection results. Simulation experiments demonstrate the effectiveness and application feasibility of the proposed method.

Node Aggregation Detection；Wireless Localization；Cluster Analysis

10.3969/j.issn.1673-5692.2016.04.016

2016-06-09

2016-07-20

TP393

A

1673-5692(2016)04-425-05