1.   引言

迅速发展的网络技术和无处不在的传感器设备，使物联网成为学术界关注的热点领域^[1]。2003年，全球有大约63亿人口，仅有约5亿设备连接到互联网，到2010年，连接到互联网的设备增加到约125亿，而人口仅增加到约68亿^[2]。近年来，无线传感器技术和电信业发展迅速，智能手机作为一种传感器设备，产生了大量的实时数据^[3]。而未来20年，将会有1万亿台物联网感知设备出现，从而生成数十亿的异构数据^[4,5]。

随着大量的传感器接入互联网，海量数据的实时产生，互联网搜索引擎无法满足查找大量非文本传感器数据的需求，这给物联网搜索引擎带来了机遇。搜索的强时空性、海量数据的异构性与传感器节点的资源受限性，使得物联网搜索引擎的研究势在必行^[6,7]。

在传统的互联网中，已有大量的研究人员投入到对海量高维数据相似性搜索的研究中，常见的相似性搜索算法有局部敏感哈希^[8]、K邻近搜索^[9]等。而传统互联网数据大多为相对静态的文本性数据，对于高动态的、异构的与海量的物联网数据，互联网相似性搜索方法不再适用。物联网数据相似性搜索应用广泛，具有很大的研究价值，例如：大量的传感器被部署，来检测森林火灾，观察河流水位，分析道路状况等。但是，部分传感器标识工作需要部署人员来完成，制造商并没有完成，部署和标识大量的传感器，成为一项艰巨的工作。为了解决该问题，传感器自动标识服务查询具有相似输出的传感器，并获取查询到的传感器原数据，自动标识新部署的传感器，从而催生了传感器相似性查找服务。另外，传感器用于感应物理环境和物理实体，通过查找相似的传感器，可以实现对物理环境和物理实体的相似性查找。例如：基于地理位置的地点推荐服务通过相似性搜索可以帮助用户查找其可能感兴趣的地点^[10]。用户需要查找与某个著名景点 $A$ 具有相同气候的景点去旅行。通过查询传感器的温度与湿度数据值，来分析目标景点是否与 $A$ 相似，从而辅助用户出行。在智能工业中，传感器相似性查找还可用于机器故障检测，比如：某种故障发生时，设备的温度与压强呈现特定的函数变化规律，根据传感器输出的规律相似性，可以定位设备故障。在智能农业中，传感器相似性查询还可辅助病虫害的定位预防，比如：虫卵孵化需要特定的气候，当气候和土壤温湿度等情况合适时，有很大概率发生某种病虫害。更多其他场景(如：查找适宜治疗和修养的病房，查找合适的会议室)都依赖于传感器相似性搜索服务。总之，传感器相似性搜索具有很高的研究和应用价值。

目前，国内外针对传感器搜索的研究刚刚起步，主要分为预测和相似性分类查找两个方向。传感器预测方向将传感器输出数据分为定量数据和定性数据，定量数据是感应的原数据(如：温度，湿度)，定性数据是传感器的统计或分类信息(如：会议室的占用，空闲状态)^[11]。Elahi等人^[12]，基于传感器相关性创建预测模型。Dyser^[13]是一个典型的搜索引擎，提供一个可以匹配搜索请求的物理实体集预测模型。上文提到的研究，都要求传感器输出定性数据，不能应用于输出定量数据的传感器。输出定性数据的传感器，需要有计算或者汇总统计的能力。由于传感器资源或能量的局限性，很多传感器不能输出定性数据。基于传感器定量数据，文献[14]使用最小二乘多项式拟合来减少传感器的通信开销，但是拟合多项式作为先验条件获取困难。

针对传感器相似性搜索方向的研究，文献[15]将传感器的相对静态的属性(如：精度，能耗)进行分类，在分类的基础上进行搜索。根据传感器定量数据进行相似性搜索的研究有限，文献[16]提出FUZZY算法进行传感器相似性搜索，假设传感器能够计算模糊集，从而生成温度概率函数，用于计算传感器的相似性，依据相似性计算数值，获取传感器部署位置信息，对传感器要求较高。基于时间间隔的温度概率函数方法，对查询时间限制严格，比如：查询了时间段 $\left[ {{t_1},{t_2}} \right]$ 的数据，并计算了数据密度函数，但是当要查询时间段 $\left[ {{t_1},{t_3}} \right]$ 的数据时，即使 ${t_3} < {t_2}$ ，密度函数仍然需要重新计算。在封闭空间中温度是相似的，所以通过温度概率函数实现传感器相似性搜索的方法，具有较低的准确度。

为了解决上述问题，本文基于传感器动态定量数据，采用PLSS算法(Piecewise-Linear fitting Sensor Similarity search method)计算传感器间的相似值，并按照相似值进行查找结果匹配排序，完成物联网中传感器相似性搜索。首先，本文根据传感器数据集合找到数据函数变化的分段点，将数据分成不同的子集；然后对数据子集进行线性分段拟合，得到传感器数据的时间连续性拟合模型；再定义传感器相似度计算方法；最后根据匹配排序算法，将相似性计算结果进行排序，完成传感器相似性查询。

2.   物联网传感器搜索框架

本节描述传感器搜索的体系结构。在资源受限的物联网中，传感器节点的能力有限，遍历搜索模式将给传感器节点带来严重的通信和能源成本。因此，基于传感器原始数据，设计一个低成本的搜索框架，提高搜索效率非常重要。

如图1所示，传感器定期收集物理实体的状态信息，自动标识并上报底层网关。物联网中海量的传感器数据存储格式各异，使得数据处理和利用困难，异构数据格式统一越来越受到重视^[17]。本文定义传感器定量数据的时间序列模型为 $\left( {{X_{{t_i}}},{Y_{{t_i}}}} \right)$ , ${X_{{t_i}}}$ 代表时间点， ${Y_{{t_i}}}$ 代表传感器感应物理环境的值， ${t_i}$ 代表时间序列。随着时间的推移，传感器每个动态属性都生成了大量时间相关的数据。根据传感器数据，底层网关为每个传感器创建相似性计算模型，并将其存储在相似模型数据库中。传感器的相似模型在设计和构建上相互独立，可通过并行计算层来计算相似值。当用户通过客户端提交一个查询需求时，并行计算层通过用户需求获取目标查询模型，并根据目标查询模型计算相似的传感器模型序列，最后根据结果序列排序，反馈检索结果。本文给出查询模型 $q = \left( {{t_q},{a_i},F(X),\left( {{R_q}} \right)} \right)$ ，其中 ${t_q}$ 表示传感器搜索的时间区间， ${a_i}$ 代表特征属性， $F(X)$ 代表相似性计算模型， ${R_q}$ 代表查询结果。PLSS算法的搜索流程如图2所示。

图 2  PLSS搜索流程

下载: 全尺寸图片 幻灯片

图 1  物联网基于内容的传感器查询体系架构

下载: 全尺寸图片 幻灯片

3.   PLSS算法

要实现传感器相似性计算，首先假设传感器按时间间隔采集物理实体状态并自动上报本地网关，根据数据拟合函数计算传感器的相似性。因此，计算传感器的相似性，关键是找到数据拟合的方法。本文提出PLSS算法，基于传感器定量数据，解决了使用定性数据对传感器资源要求较高的问题；采用分段线性拟合方法，避免了最小二乘拟合多项式获得困难的问题；时间连续的相似性计算模型，提高了查找的灵活性，从而解决了FUZZY算法对查找时间区间的强依赖性问题。

3.1   数据子集中分段点的计算方法

要实现传感器数据的分段拟合，首先要对数据进行分段，将传感器数据集分成子数据集，针对子数据集进行线性拟合。如图3曲线依据 $\Delta t$ 分割数据区间，当 $\Delta t \to 0$ 时，总能使得时间区间 $\left[ {{t_i},{t_{i + 1}}} \right]$ 内的曲线函数近似成直线函数。因此，本文假设传感器动态属性函数在相对小的时间区间内，传感器属性值 $Y$\,\, 与时间 $X$ 为直线函数：

图 3  数据分段示意图

下载: 全尺寸图片 幻灯片

本节主要介绍数据分段的方法，数据分段关键是找到传感器属性值的分段点，使得在分段数据子集内，传感器函数可近似拟合为直线函数。本文提出如下分段点的计算方法：

第1步　设置阈域值 $\delta$ ，其中 $\delta$ 定义为

其中， $n$ 为传感器值采样个数， ${t_i}$ 为采样时间序列， $\varepsilon$ 表示拟合数值与算数平均值的偏移率， $\varepsilon$ 越大直线分段点越少，存储开销越小，查询精度越低，反之 $\varepsilon$ 越小存储开销越大，查询精度越高；

第2步　底层网关根据传感器初始数值，取 $j$ 个数据 $\left[ {{t_1},{t_j}} \right]$ ，生成直线函数，并将分段点计入数据集为

第3步　将传感器数值 $\left( {{X_{{t_{j + 1}}}},{Y_{{t_{j + 1}}}}} \right)$ 代入第2步的直线函数，计算差值

如果 ${\Delta Y}\,$ 大于阈域值 $\delta$ ，将 $\left( {{X_{{t_{j + 1}}}},{Y_{{t_{j + 1}}}}} \right)$ 计入数据集 ${I}$ ，得到

剩余的数据值重复步骤2。否则，计算下一个数值 $\left( {{X_{{t_{j + 2}}}},{Y_{{t_{j + 2}}}}} \right)$ ，重复第3步；

第4步　根据数据集 ${I}$ 内的分段点，生成数据子集。假设生成了 $m$ 段的时间子集，如式(6)：

其中，数据分段点子集 $\left\{ {\left( {{X_{{t_i}}},{Y_{{t_i}}}} \right),\left( {{X_{{t_j}}},{Y_{{t_j}}}} \right)} \right\} \in I$ , ${t_i}$ 代表第 $i$ 个时间序列， ${T_i}$ 代表第 $i$ 个时间段。

3.2   数据子集的线性拟合算法

本文主要介绍传感器数据子集的线性拟合方法。根据3.1节分段点获得传感器数据子集 $T$\,\, ，作为数据矩阵式(7)的数据行，进行线性拟合。

采集数据的方法为，在每个时间段内，采集 $k$ 个数据点，从而获得了 $m$ 行数据， $\left( {{X_{{t_i}}},{Y_{{t_i}}}} \right)$ 标识数据点，用数据矩阵表示：

用 $\Delta t$ 作为时间间隔，将 $m$ 维动态属性时间数据集 $T = \left\{ {{T_i}\left| {1 \le 1 \le m} \right.} \right\}$ 分成离散的时间点 $\left\{ {{t_i}|i = 1,2,·\!·\!· ,k} \right\}$ , ${t_i}$ 代表时间序列。时间序列满足式(8)：

对于每一行的数据，用线性拟合算法得到 $m$ 个等式如式(9)：

因此，在整个数据区间内获得了 $m$ 个分段直线函数。本文使用函数左连续处理式(9)得到

式(10)是数据的线性拟合函数。

3.3   相似性模型的构建方法

本节详细描述传感器相似性计算模型的拟合过程。

首先，对数据进行去量纲处理，其中 ${y_{{t_i}}}$ 表示原始属性值， $\bar y$ 表示属性值的算术平均值，如式(11)：

数据处理后传感器 $b$ 的特征 $a$ 数据集为

其中，定义时间区间 $T$\,\, , ${x_t}_{_i}$ 为时间数据， ${y_t}_{_i}$ 为传感器属性值， ${t_i}$ 为时间序列。定义时间等式关系为

然后，使用3.1节方法，获得式(14)所示的数据子集：

其中， $m$ 表示数据分组数量， $\left| {p_i^a} \right|$ 表示子集内数据个数，数据总量为 $n$ 。然后，根据式(9)，首先将

拟合为数据函数集：

然后，根据式(10)传感器属性计算模型拟合如式(17)：

4.   传感器查询匹配算法

本节给出依据相似性模型计算传感器相似度的计算方法，再根据相似度进行查询匹配排序，从而实现传感器的相似性查询。

4.1   相似度的计算方法

给定传感器 ${S_t}$ 为查询目标传感器，计算传感器 $\left\{ {{S_i}\left| {i \in {N^ * }} \right.} \right\}$ 分别与目标传感器的相似性。依据3.3节传感器相似性模型的构建方法，分别获得特征 $h$ 的模型函数 $\left\{ {F_i^h\left( X \right)\left| {i \in {N^ * }} \right.} \right\}$ 。

依据 ${S_t}$ 定期采集传感器特征 $h$ 的时间序列属性值 $\left\{ {\left( {{X_{{t_1}}},{Y_{{t_1}}}} \right), ·\!·\!· ,\left( {{X_{{t_n}}},{Y_{{t_n}}}} \right)} \right\}$ ，根据式(18)计算模型与目标传感器之间的绝对差：

$m$ 标识传感器的个数， $n$ 标识传感器属性值时间序列的个数， ${\rm{A}}{{\rm{d}}_i}$ 代表第 $i$ 个传感器与目标传感器的相似性。将绝对差进行降序排列，绝对差越小模型之间的相似度越高。

4.2   匹配排序算法

在4.1节中提出模型相似值 ${\rm{Ad}}$ 的计算方法，本节将给出根据相似度计算查询结果的方法。并行计算模型相似性，计算结果具有大量性和无序性，为了提高查询准确度和效率，本文结合桶排序和交换排序的原理，对查询结果进行排序。桶排序首先对结果进行分组，在组内利用交换排序排除不符合要求的结果，从而对结果集进行快速筛选。下文给出查询结果的匹配排序计算方法：

首先，对 ${\rm{Ad}}$ 进行互斥性分组，得到

其中， ${g_j}$ 表示第 $j$ 个分组， $\left| {{g_j}} \right|$ 代表 $j$ 分组内的相似值 ${\rm{Ad}}$ 的数据个数， $m$ 标识参与相似性计算的传感器模型个数。

然后，定义查询基准区间 $\left| \varepsilon \right|$ ，相似度在区间内，标识查询准确，不在区间内标识查询不准确，分别对 ${g_j}$ 依据交换排序原理进行排序，如式(20)：

其中， $R_{_l}^j$ 表示通过 ${g_j}$ 组 ${\rm{Ad}}$ 计算的结果集。

最后，依次输出传感器查询结果列表 ${R_q}$ 。

5.   仿真验证

本文使用Intel Berkeley ^[18]数据集进行评估测试，计算机仿真环境为Matlab R2015b。在仿真时，相同传感器属性统一单位。传感器1的数据集中不包含噪音点，而传感器20的数据中明显的包括噪音点。而且，传感器1和传感器20的温度数值区分度不大，有利于测试PLSS算法与FUZZY算法的差异。因此，本文采用传感器1和传感器20的温度数值进行验证测试。传感器1的数据集取1317个输出值。传感器20数据集取2059个输出值。围绕传感器1和传感器20分别取4个传感器节点作为查询验证点，如图4所示。

图 4  Intel Berkeley传感器分布图

下载: 全尺寸图片 幻灯片

5.1   查询准确度对比

空气是个连通体，地理位置相近的传感器采集的温度值应该相近。因此，本文将传感器1和传感器20作为查询的基准传感器，传感器2, 17, 19, 21, 22, 32, 33, 35分别取10组数据计算与传感器1和传感器20的相似度。如图4所示，传感器2, 32, 33, 35靠近传感器1，如果计算结果与传感器1更相似，则赋值查询结果为1标识查询准确；反之为0标识查询错误；与传感器1和传感器20的相似度相等，则赋值为0.5标识查询结果不确定。传感器17, 19, 21, 22靠近传感器20，查询结果规则同上，计算结果与传感器20更相似查询结果赋值1，否则0，相等0.5。最后，将每个传感器节点的10组查询结果求平均值，得图5中的查询准确度。

图 5  查询准确度对比

下载: 全尺寸图片 幻灯片

FUZZY算法没有介绍数据噪音点的处理流程，属性取值区间的计算是属性最大值与最小值的差，会受到噪音点的影响，从而影响相似系数的计算。在文献[16]中提到，当属性值相似时，FUZZY算法查询效果相对较差，查询准确度不高。PLSS算法的查询准确度在 $\varepsilon$ 取1%时查询准确率高于FUZZY算法，随着 $\varepsilon$ 取值的增大PLSS算法的查询准确率有所下降，对于查询准确度都不高(小于0.6)的传感器节点，即使PLSS算法的 $\varepsilon$ 取5%时，查询准确率仍然高于FUZZY算法，对于查询准确率相对较高(大于0.8)的传感器节点，PLSS算法的查询准确度略低于FUZZY算法，但是当 $\varepsilon$ 取5%时，总平均查询准确率仍然高于FUZZY算法，如图5(a)所示。

最小二乘直线拟合，数据拟合不足，查询准确度稳定性差，传感器2, 33, 35的准确率小于等于0.1，平均查询准确度明显低于PLSS算法，如图5(b)所示。文献[14]利用最小二乘多项式做传感器数据拟合，拟合多项式获取困难。为了解决上述问题，并且避免拟合不足和过拟合现象，本文取查询平均准确度大于等于60%的最低次幂多项式作为最小二乘法的拟合多项式进行相似性查询，查询准确度如图5(c)所示，当 $\varepsilon$ 取5%与1%时PLSS查询准确度均大于等于最小二乘拟合算法。

5.2   查询效率对比

查询效率是搜索引擎另一个重要的指标，本节主要分析PLSS算法的查询效率。假设计算资源和计算环境对查询时间无影响，在相同的运行环境中取相同数据进行比对，并且比对时间取查询10次的平均时间用于减小误差。

FUZZY算法查询对时间要求严格，使得每次查询必须重新计算密度函数，因此查询不能并行进行，本文进行8个传感器的80组查询，则FUZZY算法需要计算80组密度函数，而PLSS算法以时间序列作为参数，有效地解决了时间局限性的问题，对于80组传感器的查询，只需要对目标传感器1和传感器20做1组分段拟合函数，因此PLSS算法的查询可以并行进行，PLSS算法的查询效率明显高于FUZZY算法，如图6(a)所示。

图 6  查询速度比较

下载: 全尺寸图片 幻灯片

传感器的数值可以表示为时间序列的最小二乘拟合多项式^[14]，查询时间与数据量 $n$ 和多项式最高次幂 $m$ 有关。PLSS算法得到的是直线函数，查询时间只取决于查询数据量 $n$ 。本文80组数据查询的效率，PLSS算法高于最小二乘拟合算法，如图6(b)所示。

5.3   存储开销对比分析

大量的传感器连接到物联网，海量数据的存储与传递给有限的网络资源带来了挑战。通过减少传感器数据的存储开销来减少海量数据对网络的压力，成为当下研究的热点问题^[19]。

传感器原数据的存储消耗了大量的存储空间，大量数据的传递也给有限的网络资源形成了巨大的压力。将原数据拟合为曲线函数，存储和传递曲线函数，只需要存储函数的系数和变量的取值区间，比如： $y = a{x^2} + b,{\rm{ }}x \in \left[ {1,5} \right]$ ，只需存储次数2，系数 $a$ , $b$ ，变量区间1, 5。FUZZY算法、最小二乘法与PLSS算法都可以通过此方法节省存储开销。FUZZY与PLSS两种方法存储的都是直线，因此只需要存储系数和变量区间共4个维度的数据。最小二乘存储的是多项式，存储系数与多项式的幂有关，本文拟合多项式最高次幂为6，因此存储系数和变量区间共9个维度的数据。

表1为数据的存储对比。本文假设存储数据都是浮点数，占用空间一致。其中传感器数据包括时间和传感器值2个维度，因此原数据的存储占用空间为数据个数的2倍。本文每个传感器节点分别取10组数据进行对比，FUZZY算法查询时间段的局限性使得10组数据需要分别做包括数据密度和数据斜率密度的拟合，因此存储空间为10组数据密度拟合函数系数个数加上斜率密度函数系数个数的和，再乘上10。比如：对于1个传感器节点，每组数据中平均数据密度函数为16个，平均斜率密度函数为10个，那么对于1个传感器中1组数据的存储空间为(16+10)×4,10组的存储空间为(16+10)×4×10。通过计算，FUZZY算法与原数据对存储的开销数量级都是10³。最小二乘多项式拟合与PLSS算法以时间为参数，只需要拟合一次函数，可进行不同时间段的多次查询。对于PLSS算法 $\varepsilon$ 取值越小拟合直线越多，当 $\varepsilon$ 取1%时，PLSS算法存储空间与原数据和FUZZY算法相比仍然降低了2个数量级。

表 1  数据存储开销分析

	传感器1	传感器20	数据个数统计
原数据 (时间，传感器值)	1317×2	2059×2	6.752×103
FUZZY算法 (传感器平均数据密度函数)	16×4×10	20×4×10	2.400×103
FUZZY算法 (传感器平均数据斜率密度函数)	10×4×10	14×4×10
最小二乘多项式拟合算法 (传感器函数系数)	9	9	1.800×10
PLSS算法 (传感器函数系数)	16	25	4.100×10

下载: 导出CSV 

| 显示表格

6.   结束语

本文基于传感器时间序列定量属性值计算传感器的相似性，避免了传感器资源受限性问题。相比使用FUZZY算法与最小二乘法分析传感器的相似性，PLSS算法的查询准确度较高。PLSS算法以时间为拟合参数的分段拟合方法，解决了FUZZY算法中查找时间区间强依赖性的问题，使得依据时间子集查询数据的灵活性增加，解决了最小二乘法拟合多项式获取困难的问题，查询效率也得到大幅度提高。PLSS算法相对于FUZZY算法与传感器原数据，存储开销降低了两个数量级。查询计算耗时与数据模型和资源开销等都有很大关系，未来项目组将针对资源开销和数据模型复杂度与查询计算的关系，做进一步的研究。