设为首页加入收藏
全站搜索
新闻详情
 
新闻搜索
 
 
栏目导航
 
 
当前位置
无线传感器网络中基于模式序列分类的分布式数据流过滤技术
作者:管理员    发布于:2016-02-16 16:52:39    文字:【】【】【

  计算机研究与发展无线传感器网络中基于模式序列分类的分布式数据流过滤技术石冰杨晓春王斌康宁周春华于戈(东北大学信息科学与工程学院沈阳110004)是无限、连续、实时、快速的数据。然而,在一些实际的应用中,由于传感器能量的有限性,传感器传送所有感知数据是不实际的。针对这一问题,提出一种基于模式序列分类的数据过滤技术,来减少数据的传输量,从而达到节省资源的目的。基于模式序列分类的数据过滤技术不考虑内网聚集,在传感器的缓存中存有一些模式序列,给定一个相似度衡量阈值,对传感器在某一段时间里感知到的数据做出处理,在已有的模式序列中寻找与当前传感器采集感知到的这段数据的相似序列,传感器只用传送部分数据通过,-i,定义为滑动窗口的大小,记为2模式管理本文把所有模式序列和滑动窗口中的数据都当做是时间序列,当滑动窗口满时(即元组个数等于窗口尺寸),在模式序列集中寻找当前窗口序列的相似序列。

  2.1基于相似序列的过滤本文的相似度量采用一般时间序列的相似度量方法――欧几里德距离公式。

  =y,3<,…,y,X,Y的欧几里德距离记为:本文定义满足,则;为相似序列。

  定义4.模式子序列。假设挖掘出《个模式序列为其中任意一个模式序列y,是由一序列有时间顺序的元组组成的,B卩,y,其中+我们称Y,为第个模的一个子序列,简称为模式子序列。

  定义5.模式长度一个模式序列 =3<,:y,…,:y,则该模式长度记为是。

  的小长度。因此在寻找当前窗口的相似序列时分为两种情况:①整体匹配,当前窗口中的序列与相似模式序列具有相同的长度;②子序列匹配,当前窗口中的序列长度比相似模式序列长度小。

  数据过滤图如所示,本文对集中处理器和分布式处理器中的模式分别进行相应的编号,当前窗口满时,在分布式处理器端寻找当前窗口序列的相似序列。找到相似序列,如果是整体匹配,分布式处理器只需向中心处理器传送该模式的W号,集中处理器就默认接收到的数据为该模式序列的值。如果是子序列匹配,分布式处理器只需向中央处理器传送该序列所在模式的W号及在模的起始和结束位置。

  2.2模式序列分类在分布式处理器端,要找与当前窗口相似的模式序列,简单的方法就是从第1个模式序列开始近似匹配,窗口每次滑动的长度为1,直到找到相似模式序列。在第f个模没有找到当前窗口序列的相似序列时,窗口滑动L -W+1次,坏的情况是比较完《个模式,没有找到当前窗口的相似序列。

  那么窗口总共滑动的次数为+,效率很低。因此,本文对所有的序列模式进行分类来提篼系统的效率。

  为了知道序列的大致形状,先找出序列中的关键点,本文提出一个关键点算法如算法1.根据关键点,可以将模式转换,然后在转换后的模式上进行索引。

  输出:所有关键点在序列中所在的位置。

  第1步。首先,构建S的关键点序列P,在P中记下S的两端点对应的位置和取值信息,成为初始的关键点。

  第2步。遍历从P中依次取出相邻两关键点作为端点关键点,找到端点关键点在S中对应的位置/和7作为两个端点,对于任意出S中离两端点是和j所确定的直线距离远的点S,S就是新关键点,并将S的位置和取值信息加人到P中的端点关键点之间,生成新的关键点序列P.第3步。重复执行步骤2,直到任意两关键点间的新关键点到两端点的斜率与端点关键点之间的夹角的斜率小于e时,认为两端点间为直线,循环结束。

  第4步。根据P得出S的大致形状以及S各点值的取值范围。

  本文通过分析根据关键点得出的模式的形状,把模式分为上凸模式、下凸模式和混合模式三大类。

  上凸模式包括两种情况:①模式序列中的大值在模式两端点所在直线的上方,且模式序列中的小值在模式的端点处;②模式的大值在模式的结束点处,模式的小值在模式的开始点处。

  下凸模式包括两种情况:①模式序列中的小值在模式两端点所在直线的下方,且模式的序列中的大值在模式的端点处;②模式的大值在模式的开始点处,模式的小值在模式的结束点处。

  混合模式:模式序列两端点的值的大小介于模式的大值与小值之间。

  如果根据关键点算法,得出的窗口中的大致趋势为直线型时,传任意一个数据值即可。通过上述方法对模式序列分类后,再根据模式序列的取值范围,建立模式树。模式树的人口处有3个节点,分别对应模式序列的3种类别。对于每一个模式类别,可知该类模式序列的取值范围,该取值范围对应的节点有《个孩子节点,《的取值根据具体情况来设定,本文中不做详细讨论。每个叶子节点的取值范围都包含于其对应的父亲节点的取值范围。

  本文首先用关键点算法得出当前窗口中序列的大致形状,根据一级索引确定所属模式类别,再根据当前窗口序列的取值范围进行索引。本文可能出现当前窗口序列的取值包含于同一父亲节点的相邻两个叶子节点的取值范围中的情况,针对这一情况,本文给出了一个定理。

  定理1.当前窗口序列的取值范围包含于同一父亲节点的两个相邻叶子节点取值范围中时,当前窗口序列的相似序列一定不在当前窗口取值范围与叶子节点取值范围的左端点的差值大于5的叶子节点对应的序列模。

  证明。设当前窗口序列为X二x,r,…,x,当前窗口序列的取值范围为6,并且当前窗口序列属于上凸模式类。设上凸模式的取值范围为,其中有两个叶子节点的取值范围分别为。不失一般性,设当前窗口序列与=:y,y,…,y,是+1任意Vl62-aI2>5,则该叶子节点所对应的模式序列的子序列都不与当前窗口序列相似。证毕。

  为了使滑动窗口每次滑动的距离更长一些,本文提出了当前窗口的相似序列匹配如算法2.算法2.当前窗口序列的相似序列匹配算法。

  输人:当前窗口序列索引到的模式序列输出:当前窗口的相似匹配序列所在模式的W号和起始、结束位置。

  + +认为序列X与Y的子序列Y,不匹配,窗口滑动第2步。设滑动窗口在每个模式序列中第;次滑动的长度为窗口在滑动前的第2个关键点对应于模式序列的位置模式序列中离;+近的关键点的位置为P,则d=第3步。如果没有找到相似序列,循环执行步骤2,当窗口的末端对应于序列模的位置到序列模式结束点的长度小于窗口尺寸w时,窗口在该模式上停止滑动。

  第5步。若找到相似序列,返回相似序列所在模式序列的W号及在序列模的位置,没找到相似序列,返回为空。

  如果找到多个相似序列,取D值小对应的模式序列,因为两序列间的距离越小表明越相似。

  3实验分析本文采用的数据集是中的真实天气数据集,本文只用温度、湿度、风速3个属性的数据。

  实验用服务器配置为CPU:IntelPIV2.8GHz,系统主存512MB,操作系统为WindowsXP,数据库使用SQLServer2000.和文通过实验对文中提出方法的有效性进行了检Model两种预测方法进行了比较本文给出两个衡量标准来进行对比分析需要发送数据量的百分比和平均误差值。需要发送数据量的百分比是要发送的数据量占整个数据量的百分比。平均误差值是近似值在精度范围内发送数据的平均误差,在时刻¢,设传感器监测到的实际值为V,在集中处理器端存的对应近似值为V,-,£,-VVI.假设集中处理器端有《个数据存储的是近似值,那么AverageError S1 ~V1.首先,本文应该通过实验找出e,n的好设置,因为e的取值将影响关键点算法和模式的形状。由于精度值5太大没有意义,本文在实验中设置精度值的范围为。在评估e变化对系统的影响时,本文取精度值在精度范围中的一个中间值U =4),测出需要发送的数据量。

  从的实验结果可以得出,e在0.1左右时,传输的数据量百分比小。因此在本文后面的实验中,e的取值为0.1.和给出了和中两种方法进行对比的实验结果,图中横坐标为PrecisionWidth),纵坐标为要发送的数据量占整个数据量的百分比和平均误差。

  从中可以看出,当5从0~10逐渐变大时,平均误差值增大显示,当5从0~10逐渐变大时,分布式处理器向集中处理器发送的数据量逐渐减少。从实验结果图可以明显地看出,本文提出的方法要优于中的方法。

  5变化时产生的平均误差(e 4结论和未来工作本文提出了一种新的过滤方法来减少基于分布式数据流环境下的通信代价。本文的方法通过时间序列的相似性比较,过滤掉很多数据,从而减少了通信量。实验结果表明,本文提出的方法能较大地减少数据的传输量,降低传感器网络中的通信代价。

  在未来的工作中,将对模式树叶子节点的取值范围进行具体研究,并对模式序列进行动态存储管理。

访问统计
51客服