窗口滑动

窗口滑动（精选四篇）

窗口滑动 篇1

滑动窗口(slide window)协议可以解决在数据包受损、数据包丢失和过早超时等情况组合下的同步问题。滑动窗口协议有3类,它们分别为1位滑动窗口协议、退后n帧协议和选择性重传协议。这3个协议的区别在于效率、复杂性及对缓冲区的需求各有不同。因为对于“一卡通”中各种终端设备来说,后两个协议仅仅增加了复杂度而没有带来效率,所以设计中使用1位滑动窗口协议。程序清单1是wait-stop协议一个最基本的算法C语言描述。

程序清单1:大小为1,拥有8位序列号的滑动窗口协议。

图1描述了此协议。初始时,没有数据包要发送,所以发送窗口的上限和下限是相等的,而接收窗口第一个想接收的肯定是帧0,所以窗口游标为0,随着时间的推移,状态的变化如图1所示。

(a)初始时(b)发出第一帧后(c)收到第一帧后(d)收到第一个确认。

进一步,滑动窗口协议采用了捎带(piggybacking)技术,捎带技术暂时延迟待发确认,而是维持等待,直到上层向其传送下一个分组。确认被附加到即将发送的数据包上(一般使用数据包头部的ack字段),也就是说,确认是夹在下一个将发送的数据包上进行传送的,使用捎带技术的好处在于,能较好地利用有效的信道带宽。然而捎带也带来了一些问题,比如协议无法预知下一个应用数据何时到来,这样就会对系统的实时性产生严重的负面影响,所以捎带虽然可以节省带宽,但显然它不适合应用在本系统中。

2 滑动窗口的特点

由于上面的种种原因,根本不可以将滑动窗口协议原封不动地搬到本系统中来,所以必须对滑动窗口协议根据本系统的特点进行适当的变形,从而形成了现在的滑动窗口协议。

程序清单2描述了改造后的滑动窗口协议。

以下将考察协议的适应能力是否能满足日常需要。如图2说明了协议的工作序列,如图2(a)部分,可以看出在正常的情况下协议工作良好,必须考察一下协议在不正常的情况下,协议的适应能力是否可以适应应用的需要。

如图2(b)部分,假定A试着向B发送帧0,但是B未及时进行应答或A的超时时间隔设置得过短,结果会导致A也许重复地超时,发送一系列同样的帧到B,都是sequentNo=0。当第一个有效的帧到达B时,该帧被接受,packageExpected于是被置成1,这样所有重传帧都会被拒绝,这是因为B此时正在期望序列号为1,而不是为0的帧,但B会认为它所发送的应答数据丢失,所以重新发送应答数据。如图2,在对帧0数据第一次应答数据到来时,A认为B已经收到了数据,这时A向B发送第二帧,这时B发送的第二次帧0的应答数据到达A,由于从应答数据中A无法辨别应答数据是针对帧0还是帧1的,所以它默认为当前的数据,也即帧1的应答,这时它就可以继续发送帧2了,但事实上B对数据帧1根据就没有应答,也许帧1根本就没有到达B,所以在这种情况下协议就会出错,在这种情况下,由于平台收到并不是它所期望的值,且与期望值无法进行衔接,平台运用了GetBackData方法,回调A向B发送的最后的四笔数据来对B所收到的数据进行校正,从而可以找回帧1的数据,也就解决了由于回应数据无帧号消息而对数据传输的正确性所造成的影响。

摘要：以一卡通系统中滑动窗口协议的改进为依据,分析了协议在改进过程中的实时性和正确性等方面的用途。

关键词：滑动窗口,数据安全,数据实时性,数据正确性

参考文献

[1]陆永宁.IC卡应用系统.东南大学出版社,2000.

[2]王卓人,邓晋钧,刘宗祥.IC卡的技术与应用.电子工业出版社,1999.

[3]丁正铨,许祖谦.计算机网络原理与技术.四川大学出版社,1995.

[4](美)Tim parker.Mark Sportack TCP/IP技术大全.北京:北京工业出版社,2000.

窗口滑动 篇2

1 RFID漏读数据清洗方法

针对RFID漏读数据的清洗方法有多种,但基于滑动窗口的数据填补算法是目前最实用、可行的方法。文献[3]中将静态时间窗口用于填补漏读的RFID数据。然而,使用静态时间窗口存在一些问题,如图1 所示,若窗口设置过小,则有可能无法充分对漏读数据进行平滑处理,不能保证标签的完整性; 窗口设置过大,又无法较好地监测标签的动态性。因此,理想窗口大小设置应综合考虑并合理设置,使得在保证不漏读数据情况下,准确地检测标签的状态转变。

针对静态滑动窗口大小不容易确定的问题,加州大学伯克力分校的Jeffery等人提出了一种自适应改变滑动窗口大小的RFID数据清洗算法SMURF( Statisticals Moothing for Unreliabler Fid data)[4]。SMURF算法创新性地将统计理论中的随机概念引入射频数据流中。该算法基本思想: 设滑动窗口Wi由wi个时间片epoch组成。假设标签i在时间窗口内每个epoch内可能被读到的概率为pi。SMURF算法把每一个epoch对于标签的阅读看做是一次具有概率pi的伯努利实验。因此,该变量符合二项分布B( wi,pi) 。并定义piavg为Si内的平均读取率,则

利用基于伯努利实验的模型来观测标签i,如果wi个epoch中标签的平均读取率为,滑动窗口Wi由wi个时间片epoch,wi为抽样次数,假设置信度为 δ,可得,保证完整性的充分条件为窗口的大小wi满足

为保证标签的动态性,滑动窗口的大小需要满足

SMURF算法在实现过程中将初始滑动窗口的大小置为1,当窗口内发生阅读时,根据式( 2) 动态调整窗口大小以保证数据的完整性: 如果调整后的窗口大小满足式( 2) 时,SMURF则会基于式( 3) 对标签的动态性进行监测。如果窗口大小不满足式( 3) ,SMURF会将当前窗口缩小为原窗口大小的1 /2,从而对标签状态的转变做出反应; 否则,SMURF输出当前窗口,并滑动一个时间片的长度来进行下一次处理。若调整后的窗口大小不能满足式( 2) ,则SMURF会将当前窗口以2 为步长进行增大,以满足窗口设置的要求。SMURF算法实现的具体流程如图2 所示。

SMURF算法改进了定长滑动窗口大小难以确定的缺点,在静态标签下取得了较高的准确率,但当标签数目增大或者是标签频繁动态变化时,导致积极平滑或疲惫平滑现象较多,其重要原因是该算法对标签运动模式考虑欠缺[5],在标签的动态监测性方面只考虑到了标签在阅读器区域与不在区域两种情况。而实际上,这两种状态的转换也是要经历一个由量变到质变的过程,即标签的运动。本文在SMURF算法的基础上,提出一种改进的基于标签运动的RFID数据清洗算法DCATMS( Data Cleaning Algorithm of Tags in Motion Based on Sliding-window) ,DCATMS算法通过引入标签的概率运动模型来判断标签的动态跃迁性,进而动态调节滑动窗口大小,解决数据的完整性和动态性,更好地对RFID漏读数据进行填补。

2 DCATMS算法设计

DCATMS算法采用的滑动窗口模型与SMURF类似,仍将RFID数据集当作统计学中的概率事件,即大量标签的随机样本。针对SMURF算法在标签动态性检测以及窗口大小设置方面的缺陷,该算法分别引入标签概率运动模型进行标签状态发生变化的判定,同时对窗口大小的设置进行改进。

2. 1 标签概率运动模型引入

RFID技术在实际应用中,通常会有标签进、出阅读区,反应到物理世界中就是标签位置的变化,即标签的运动过程。显然,标签的运动过程必然符合牛顿运动学定律。RFID阅读器的识别半径通常为几m,最远不超过十几m。

RFID标签在阅读器识别区域内的运动速度通常较为平稳,而阅读器本身处于识别区域的中心,如图3 所示。所以在一个较小的时间段 Δt内标签的运动可被近似看作是过识别区域中心( 圆心) 的匀速直线运动或者是多个连续的匀速直线运动的组合。如果记d0为标签与阅读器的初始距离,根据匀速直线运动的性质显然可得

其中,v表示物体的运动速率。

为推断出d的值,将式( 4) 变为

其中,a =d0,b = ±v。

首先估计未知参数a和b的值,且a和b值的准确度直接会影响到数据清洗的准确度。由式( 5) 可知,d与 Δt成线性关系,所以可采用最小二乘法对参数a和b进行线性回归[6]。详细计算过程此处不再赘述,利用最小二乘法估算出参数a和b的值为

因标签处于近似匀速直线运动而且满足式( 5) ,所以可根据当前epoch对应的时间值 Δt以及的值计算出d的近似值,然后比较与阅读器的最大探测距离D的大小。RFID数据清洗时,只有在当前epoch对应的读取率pi= 0 时,才需要考虑数据填充问题,造成pi= 0 的原因主要有两种: ( 1) 标签对应的位置确实已经不在阅读器的有效探测区域,即; ( 2) 标签处于阅读器的有效探测区域,即,但由于某种原因被阅读器漏读。第一种情况属于正常现象,不必做进一步处理。而第二种情况就是所谓的漏读,在数据清洗中是应对漏读的内容进行填充。因此,要得到精确的RFID数据清洗结果,关键在于对这两种情况的准确区分。

2. 2 DCATMS算法

DCATMS算法基本思路: 在完整性方面,继续沿用SMURF算法保证完整性的条件。然而在对SMURF算法的实验中发现,将窗口大小每次线性增加2,则有可能导致窗口大小的不足而使得数据的平滑结果与实际情况相差较远。为此,本文采用一种对计算出新窗口大小与原窗口大小进行折中的方法来对窗口大小进行控制,即当计算出新窗口的大小大于原窗口大小时,将原窗口大小设置为新窗口大小与原窗口大小之和的一半。在标签动态性检测方面,通过上文标签运动模型进行准确判定。DCATMS算法基本流程如图4 所示。

3 实验结果与分析

为验证DCATMS算法的有效性,本文采用JT900R四通道射频阅读器,使用符合EPC CLASSI G2 标准的标签50 个,让标签以一定的速度通过阅读器,图5 和图6 所示为实验室环境下对算法进行测试。同时,为了验证算法的可扩展性,本文进行了大量的仿真实验,采用文献[7]中的方法生成仿真数据。如图7所示,横轴代表标签与阅读器之间的距离,纵轴表示标签被阅读器读取到的概率即阅读率。

实验中对标签进行了两种运动模式的研究: 模式1是标签以不同速度匀速运动; 模式2 是标签随机运动[8,9]。实验参数设置如表1 所示。

实验中,通过变化阅读器主识别区在整个阅读器阅读区中比例大小对数据进行实验,算法性能用每个epoch的错误阅读数来表示。错误阅读数是指当标签存在于阅读器范围内时,经算法处理过后并无阅读数据产生,或当标签在阅读器范围外时,经算法处理过后产生了阅读数据。通过大量实验数据,本文比较了固定大小的静态滑动窗口方法Static-x、SMURF算法和DCATMS的算法性能,并重点对比分析了DCATMS和SMURF算法的清洗效果。

3. 1 标签匀速运动算法清洗效果分析

实验分析了标签在匀速运动时,算法在不同速度下的平均错误数,标签匀速进出探测区域,速度在0 ~90 cm / epoch之间,实验记录了不同速度下每种方案产生的平均错误数。图8 显示了实验结果。

如图8 所示,为标签速度不同时的RAW原始数据、固定窗口Static-5、Static-10、Static-20、SMURF算法和DCATMS的性能比较。结果显示随着标签运动速度加快,对固定窗口而言,小窗口更能捕获标签的运动状态的改变,性能相对较好。SMURF和DCATMS算法则由于能够根据阅读率和约束条件进行动态调节,能更准确地应对标签运动引发的状态变化,从而准确率相对较高且较为平稳,此外DCATMS算法对标签状态改变更加敏感,准确率更好。由图7 显示的算法比较可知,DCATMS比SMURF平均错误数总体减少量约为50% ,对漏读数据的填补效果更佳。

3. 2 标签随机运动算法清洗效果分析

实验分析了标签随机运动时算法在不同主识别区百分比的平均错误数和自适应清洗结果。标签在阅读器阅读范围内及范围外以0 ~ 90 m/epoch的速度随机运动,主识别区的比率从0 ~ 1 之间以步长为0. 1 选取11 个值。较低的主识别区百分比模拟不可靠的环境,较高的主识别区百分比模拟可靠环境。图9 显示了这项实验的结果。

图9 显示了固定窗口Static-5、Static-10、Static-20、SMURF算法和DCATMS算法在不同主识别区百分比的错误数比较。结果显示主识别区百分比较低时,标签阅读率较低,大的固定窗口平滑效果相对较好且较稳定,随着阅读率的提高,所有算法的准确度都随之上升,针对固定窗口而言,小窗口的平滑效果较好。SMURF和DCATMS算法相对固定滑动窗口整体效果较好,自适应性较高,且DCATMS算法平均错误数比SMURF总体减少量约为52% 。

4 结束语

本文分析了经典的RFID漏读数据清洗算法SMURF,针对该算法存在标签动态性检测以及滑动窗口大小设置方面的缺陷,提出了一种改进的RFID漏读数据清洗算法DCATMS。DCATMS算法中引入标签概率运动模型对标签的动态性进行准确判断,防止在填补漏读数据时造成积极平滑或疲惫平滑现象较多。同时,该算法选择了一种更为合理的方法来设置窗口大小。实验结果显示,标签在两种运动模式下,DCATMS算法的清洗效果比SMURF算法有显著提高,前者产生的平均错误数量比后者降低了51% ,基本可以达到对RFID漏读数据的清洗要求。但DCATMS算法依然存在一定的缺陷。该算法中提出的标签运动模型仅考虑标签与阅读器之间的位置关系,由于RFID阅读过程的复杂性,其不仅能反映标签的位置信息,同时也能反映出标签读取的时刻。在标签动态检测机制中,若能将标签位置信息与时间相结合,可能会更加准确地判断标签的动态变化。此外,该算法有待在大量RFID标签的实际应用环境下进一步检验。

摘要：RFID标签数据漏读问题普遍存在于RFID系统的应用中,为确保RFID数据的准确性,必须对原始数据进行清洗。针对当前最有效的滑动窗口清洗算法SMURF中存在的标签动态性检测的缺陷,文中在提出的改进算法中引入了标签概率运动模型进行判定,算法能准确检测到标签动态变化,并在窗口大小设置上更为合理。实验结果表明,文中所提出的算法比SMURF算法产生的平均错误数减少51%,性能更加优越。

关键词：RFID,漏读,数据清洗,滑动窗口,标签运动

参考文献

[1]Want R.An introduction to RFID technology[J].Pervasive Computing,2006,5(1):25-33.

[2]Popovski P,Fyhn K,Jacobsen R M,et al.Robust statistical methods for detection of missing RFID tags[J].IEEE Wireless Communications,2011,18(4):74-80.

[3]Rizvi S,Jeffery S R,Krishnamurthy S,et al.Events on the edge[C].Boston:Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data,2005.

[4]Jeffery S R,Garofalakis M,Franklin M J.Adaptive cleaning for RFID data streams[C].Korea:VLDB,2006.

[5]樊华.面向物联网的RFID不确定数据清洗与存储技术研究[D].长沙:国防科学技术大学,2013.

[6]欧俊豪,王家生,徐漪萍,等.应用概率统计[M].2版.天津:天津大学出版社,2004.

[7]Jeffery S R,Garofalakis M,Franklin M J.Adaptive cleaning for RFID data streams[C].Porland:Proceedings of the 32nd International Conference on Very Large Data Bases,2006.

[8]陈翅刚.制造物联网海量RFID感知数据智能清洗处理技术研究[D].广州:广东工业大学,2014.

窗口滑动 篇3

流密码也称序列密码。序列密码一直是军队和政府使用的主要密码技术之一。其主要原理是通过伪随机序列发生器产生性能优良的伪随机序列,使用该序列与明文信息流逐比特异或得到密文序列[1]。伪随机序列发生器是指输入真随机的较短的密钥(种子)通过某种复杂的运算产生大量的伪随机位流[2]。由于流密码长度可灵活变化,且具有运算速度快、密文传输中没有差错或只有有限的错误传播等优点,目前仍是国际密码应用的主流,而基于伪随机序列的流密码是当今最通用的密码系统[3]。流密码加密流程如图1所示。

从理论上说,数据流的潜在大小是无界的,系统存储的数据相对数据流大小则是非常有限的[4]。在处理明文信息流的过程中,通常并不是对所有已经到达的数据都感兴趣,而是只对最近到达的部分数据感兴趣,这样就需要引入滑动窗口模型[5]。

1 加密程序设计及实现

加密程序应用模块设计思想,在VS2008开发平台上,对程序“窗口”模块、程序的两个线程模块即“接收方”线程和“发送方”线程采用MFC框架下的C++语言进行设计开发。

1.1“窗口”的设计

本文设计了一个大小N为7的“窗口”缓冲区,即该“窗口”缓冲区拥有7个块单元。每一个块单元由一个存储数据的数组和若干标志位组成,具体定义如下:

7个块单元首尾相接,形成一个循环队列。当7个块依次循环滚动读取文件数据时,“窗口”缓冲区则依次向后移动。

在块结构中,Data数组用于缓存文件数据。Flag标志位用于标示本块序号。NextFlag标志位用于标示本块指向的下一块的序号。HaveData标志位用于标示本块中是否有数据需要写出,初始值为false。AbleToWrite标志位用于标示本块是否可以写入,初始值为true。IsFinal标志位用于标示本块是否为最后一块,初始值为0。

1.2“发送方”与“接收方”的工作流程设计

采用多线程的技术,在程序中使用双线程来模拟收发双方。“发送方”的功能定义为文件分块读取以及进行加密,“接收方”的功能定义为从块中读取数据并写入加密后的文件。当加密开始后,双发各自完成各自的工作,互不干扰。

1.2.1“发送方”线程具体流程设计

“发送方”线程开始时,需将当前块序号初始化为0。在写入块的时候,需判断该块是否可写,即AbleToWrite标志是否为true。在当前块写完后,需修改该块的标志位,即将AbleToWrite置为false,HaveData置为true。如果是最后一块,还要修改IsFinal标志,将块内剩余数据长度赋值给该标志。具体的程序流程如图2所示:

1.2.2“接收方”线程具体流程设计

“接收方”线程与“发送方”线程同时启动,并且初始化“接收方”线程当前块序号为0。但有所不同的是,“接收方”线程启动之后一段时间一直处于等待状态,以等待“发送方”线程将窗口中第一块的读取加密操作完成。当检测到当前序号块的HaveData标志位为true时,即开始从窗口中将数据写入加密后的文件。如此依次循环,一旦检测到当前块的IsFinal标志位为true时,即开始将最后一块中的数据写入文件并完成文件写入。具体的流程如图3所示。

1.2.3 双线程协同工作具体流程设计

在“发送方”和“接收方”线程都启动之后,两个线程除了完成自己所需完成的任务之外,还要两者协同工作才能顺利的完成文件加密的工作。在滑动窗口思想下两个线程的协同工作具体流程如图4所示。

双线程启动后,窗口(即一个由块组成的循环队列缓存区)位于文件最前端。“发送方”线程开始对窗口内第一个块缓存数据进行加密,“接收方”线程则处于等待状态。当“发送方”线程完成第一块的操作之后,“接收方”检测到第一块缓存内有数据需要写出,“接收方”。

线程停止等待,开始将数据写出到加密后的文件中。同时,“发送方”线程仍然继续依次向后对块缓存中的数据进行加密。当“接收方”线程将窗口最前块缓存中的数据完全写出后,窗口向后移动一个块单位,即循环队列滚动一个块单位。在此过程中,如果“发送方”线程写完了最后一块缓存而窗口仍未移动的话,“发送方”线程将进行等待,直到窗口向后移动而出现新的块缓存。窗口移动到最后一个块缓存则停止移动,当两个线程完成对窗口缓存中的数据处理操作后,双线程终止,加密结束。

2 测试结果及分析

所述设计在实现时采用RC4流密码。测试环境:windows7操作系统;机器配置:2.4Ghz双核处理器以及2G的内存。

通过实际程序测试,得到以下的结果:1)在需加密文件大小线程方面,所设计的加密方式适合任意大小的文件,并在实际测试中得到验证;2)在文件加密速度方面,所设计加密方式的文件加密速度最低值约为16MB/s,最高值约为20MB/s;3)在系统资源占用方面,所设计的加密方式占用内存资源保持在设定值,不受文件大小影响。

3 结论与讨论

本文介绍了基于滑动窗口协议思想的流密码多线程文件加密设计。通过实际测试,证明该设计能较好的解决流密码在加密文件时存在的某些问题,如:1)当需加密文件过大并且不分割文件时,加密程序容

图4双线程协同工作流程图易占用过多的内存资源,造成电脑响应缓慢甚至无响应,如果文件大小超过内存大小的话,甚至会造成加密后的文件丢失数据的情况出现。2)如果程序针对1)中所提的问题采用加密一部分保存一部分的话,则会影响加密算法的性能。本文提出的设计实现方案较好的保证了加密的速度,在加密中不至于过多占用内存,并且使需加密的文件大小不受内存大小的限制,因此具有一定的使用价值。

滑动窗口协议思想还可以应用在更多的领域,例如数据流查询等[6,7]。在各个领域的工作流程中,如果需要使用两个功能模块对同一个对象进行操作而两个功能模块的工作又必须有一个先后顺序时,都可以使用滑动窗口协议思想进行流程设计,这主要因为它具有处理模。

块间的超强调度能力[8]。当然,在如何进一步提高加密速度等性能方面,还有待于进一步的研究。

参考文献

[1]曹天杰,张永平,毕发明.计算机系统安全[M].北京:高等教育出版社,2007:49.

[2]曹天杰,张永平,毕发明.计算机系统安全[M].北京:高等教育出版社,2007:49.

[3]罗启彬,张健.流密码的现状和发展[J].信息与电子工程,2006,4(1):75-80.

[4]陈磊松.数据流处理系统的调度策略研究[J].计算机工程与设计,2007,28(8):1845-1847.

[5]杜威,邹先霞.基于数据流的滑动窗口机制的研究[J].计算机工程与设计,2005,26(11):2922-2924.

[6]刘学军,胡平,徐宏炳,等.基于滑动窗口的在线数据流增量聚集查询[J].计算机工程,2007,33(21):45-47.

[7]王伟平,李建中,张冬冬,等.基于滑动窗口的数据流连续J-A查询的处理方法[J].软件学报,2006,17(4):740-749.

窗口滑动 篇4

目前随着通信、计算机、物联网等技术的发展，在工农业生产、国防科技等各个领域，从网络监控[1]、电子商务[2,3,4]、环境监测[5,6,7]到金融交易等[8]在数据流(即产生连续到达、动态进化的数据)应用方面发生了深刻的变化。现如今，已经有很多研究人员从数据挖掘转入数据流挖掘的队伍中，或改进原来的算法或提出新的适应数据流挖掘的算法[9,10,11]。数据流的研究主要集中在数据流综述[12]、相似性搜索[13,14,15,16]、分类[2,17]和聚类[2,3,7,18,19,20,21]。目前，聚类技术大致可以分为几类:分块法(比如k-means和k-medoids)、分层法(birch[30])和基于密度方法(DB-Scan[7,8,31]等)。针对数据流聚类算法目前比较普遍的:STREAM算法[22]和Clu Stream算法[1]。O’Callaghan等于2002年提出了Stream算法[22],STREAM算法基于分而治之的思想，并以K-means算法为基础，使用迭代过程对数据流进行聚类。Aggarwal等提出了Clu Stream算法[1],Clu Stream算法给出了一种金字塔时间框架保存实时聚类结果的设计思想，该算法更加细化了聚类的时间粒度，为解决数据流聚类演化问题提供了一种新的途径。

尽管Clu Stream算法在数据流聚类算法中应用较多，但对于滑动窗口模型下的数据流聚类，尤其是变速数据流的聚类，该算法已经无法满足聚类要求。常建龙[24]对滑动窗口做出了如下贡献:提出了Clu Win算法-基于滑动窗口的数据流聚类算法，采用拒真或纳伪两种聚类特征指数直方图作为概要结构，但同时也增加了聚类特征指数直方图的维护复杂度。

文献[25]、文献[26]在数据流聚类算法中，也采用了滑动窗口技术，并在此基础上，提出了一种增量式的数据流处理方法及数据流聚类算法。文献[32]提出了一种增量式数据流聚类方法，在不断增长的数据流的聚类过程中，采用分割和合并策略自适应地动态调整聚类的数目。文献[33]提出了新算法(HECES)，采用滑动窗口技术处理不断到来的数据流，采用收缩技术避免在寻找相关数据的协方差过程中出现的奇异点问题。文献[34]采用频谱分量相似性分析的新方法，该算法具有自回归测量数据流之间的滞后相关性，把它作为距离度量聚类的模型。该算法也采用滑动窗口模型来连续记录最新的聚类结果并动态调整聚类个数。

文献[35]针对不断变化的数据流，提出一个基于图的增量聚类算法，采用代表点对新数据不断聚类。文献[36,37]提出一种基于人工免疫系统的聚类技术，提出一种人工白红细胞网络模拟自适应观察生物免疫系统。细胞随着模拟刺激更新方法不断进化，用K-均值聚类方法周期性地改变细胞网络，从而提高了聚类的效率。文献[38]主要讨论在线聚类算法，针对不断变化的数据流，聚类算法和模糊方法相结合，利用模糊方法很好地解决了异常点和重叠簇的问题。

综上所述，很多专家学者将注意力集中到数据流的聚类，对数据流的处理也有基于滑动窗口技术，但是基于固定滑动窗口流数据聚类算法，而且过分地关注数据流聚类效率和准确度方面，而忽略了数据流是动态变化的，其变化会对数据流聚类效果产生直接的影响。针对这一问题，文献[27]将动态滑动窗口技术引入其中。其充分利用存储的概要信息对滑动窗口进行动态调整，最终生成聚类。窗口大小由两部分组成w和Δw,w代表固定部分，Δw代表可变部分，Δw由聚类开始时设定为一固定值，窗口可变部分Δw一旦设定，不管数据流流速在整个数据流聚类期间如何变化，Δw均保持不变，所以Δw并未反映出窗口大小和数据流流速之间的关系。本文的研究有别于以上研究成果，和文献[17]相似但有改进。本文的主要贡献在于:

(1)指出滑动窗口大小和数据流流速之间的定量关系，提出动态可调衰减滑动窗口模型。

(2)提出了衰减滑动窗口的聚类指数直方图。

(3)仿真结果实验表明，相对于Clu Stream算法，能够获得更优的聚类效果。

1 预备知识

1.1 衰减窗口

数据项在流中出现的越早，其权重也越小。形式化地，另流当前的元素为s1,s2，…，st，其中s1是第一个到达的元素，而st是当前的数据项。另c为一个很小的常数，比如10-6或10-9。那么，该流的指数衰减窗口定义为:。

上述的定义效果是，流中数据项的权重取决于其离当前数据项时间的远近，流中越早数据的权重也越小。与此形成鲜明对比的是，对一个大小为1/c的固定大小的窗口内的元素进行加权求和时，会对最近1/c个数据都赋予权重1，而对于所有更早的数据赋予权重0。相对于定长滑动窗口来说，对指数衰减窗口中的求和结果进行调整要容易得多。对于滑动窗口而言，在每次新数据到达时必须要考虑它是否在窗口之外。也就是说，我们必须要在求和结果之外保留数据的精确数目，或者使用某种算法。但是，在指数衰减窗口中，当新数据到达时，(1)将当前结果乘以1-c;(2)加上st+1。

这种处理方法有效的原因在于，当新数据到来时，原有数据相对于当前数据而言又远离了一个位置，因此其权重必须乘上1-c。另外，当前元素的权重为(1-c)0=1，因此，直接加上st+1可以正确体现新元素的贡献。

1.2 动态可调衰减滑动窗口模型

滑动窗口充分考虑了过期数据和近期数据对整个数据流聚类效果的影响。对于实时可变的数据流来说，往往其传输速度也在实时变化。因此，对于传输速度变化的数据流，大都采用固定的滑动窗口。这样造成了内存资源的浪费，同时流数据的采集会遗漏过多的有用的数据。本文提出了一种动态可调衰减滑动窗口，即考虑新、旧数据对数据流聚类效果的贡献大小，又体现了数据流流速与窗口大小的函数确定关系。窗口被定义为固定部分和可变部分，可变部分窗口的大小是数据流的传输速度的函数。

定义1动态可调滑动窗口大小:一个连续的时间序列构成一个时间滑动窗口，滑动窗口的大小记为TW,TW代表当前窗口内数据流中数据项的个数。

其中，W为滑动窗口大小的固定部分;Δw为滑动窗口大小的可变部分;Δw与w的关系可表示为函数f(vi,v);其中vi为数据流传输的即时速度;v为数据流最近一段时间内的平均速度，可通过统计信息计算;σ为调节因子，防止Δw过大或过小。为了防止滑动窗口的大小在很小范围内过于频繁变动，对σ的取值规定在一定范围内，对于σ的取值，讨论如下:为了防止窗口大小频繁变化，引入参数η，η的大小可以根据实际情况设定，一般情况下，0≤η≤1。

(1)数据流传输速度变慢时，即时速度vi小于匀速速度v，此时，即，具体又可分为两种情况:

(a)其中部分数据流速率变化较小，可以忽略，将在(3)中考虑;

(2)数据流传输速度变快时，即时速度vi大于匀速速度v,vi和v的关系满足:

(a)在情况(a)时，速度变化不大，可和(1)中的(a)在情况(3)中合并讨论;

(b)情况(b)时，σ取值为1,TW=W+Δw;

(c)即，Δw>w，为了防止Δw过大，此时σ取值区间为(0,1)，，相当于在一定的阈值范围内，滑动窗口的增长随数据流流速的增加线性增长，在超过阈值范围时，增幅线性衰减，TW=W+Δw。

(3)当数据流的传输速度接近于匀速速率时，即两者满足时，系统认为数据流速度变化在允许范围之内，数据流滑动窗口大小不变，TW=W。

2 变异数据流聚类的数据结构

定义2衰减滑动窗口时间聚类特征:一组具有时标Ti1…Tin的d维元组集合的时间聚类特征TCF(temporal cluster feature)为2d+4维的向量各为d维向量，其中各个参数的含义如下:

(3)n数据数目;

(4)λ各数据权值平均值，λ满足，其中:t表示当前时间。

(5)t代表刚刚到达的数据Tin;

(6)t'代表将要离开滑动窗口的数据时间下标。

本文提出的衰减滑动窗口数据结构对已提出的数据流常用数据结构进行了改进。首先，在Aggarwal等人[27]提出的数据结构的基础上，增加了时间域。常建龙等也在此基础上有所改进，提出纳伪聚类特征和拒真聚类特征时间。各个数据进入窗口的时间的计算方法有所改进，只需要知道最近到达的数据的时间并结合数据流聚类数据结构即可获得，比传统的计算方式有所简化，并不需要完全知道所有数据的时标。高自娟[28]等人也从时间域对时间聚类特征进行了扩展，提出了混合指数直方图技术。胡彧[29]也对聚类特征做了进一步的扩展，增加了被淘汰元组的到达时标均值。本文中在前人研究的基础上，将聚类特征扩展为2d+3维的，引入t和t'，分别表示最近元组时标和将被淘汰元组时标，用以及时淘汰过期元组和处理最新元组，体现了滑动窗口的思想，被淘汰元组用到达时标来代替到达时标的均值;在实际的数据流应用中，最近元组所包含的内容比历史元组要多得多且更有价值。为此，本文建立的时间衰减模型对历史元组的权重采取逐渐减少或衰减的方式。在任意时刻t，元组的权重即其衰减因子满足:st-i(1-c)i<ε，t越大，所考虑的历史数据的价值就越少。

3 动态可调滑动窗口的变速数据流聚类算法

借鉴算法Clu Stream的思想，动态可调衰减滑动窗口的变速数据流聚类算法DWSWC(Dynamic Weakened Sliding Window Clustering algorithm)，它分为两个阶段。

1)微簇在线聚类过程(Online DWSWC):调整窗口以便处理衰减滑动窗口内的数据流。存储数据流并进行更新维护其概要结构信息。

2)最终簇离线聚类过程(Offline DWSWC):根据用户聚类请求，从时间金字塔结构中获取某个时间粒度的概要数据结构，利用Clu Stream算法中的离线聚类方法得到最终的聚类结果。所以本文重点讨论在线聚类算法。

算法Oline DWSWC。

输入动态数据流DS，窗口大小W,vi为数据流传输的即时速度;v为数据流最近一段时间内的平均速度，σ为调节因子，权重阈值μ;衰减因子c;半径阈值R;误差因子ε;

输出动态滑动衰减窗口的微聚类。

执行过程如下:

(1)微簇的初始化

初始状态时，微聚类数量为0，然后在此基础上采用特定的算法构造初始簇，并初始化聚类的每一个聚类特征WSWTCF;

(2)添加数据对象

新到的数据点Xi找到最近的簇(WSWTCF)，计算Xi和每一聚类特征WSWTCF之间的距离Dis(Xi,WSWTCF)，并且找到最近的距离Dismin(Xi,WSWTCF)，并修改簇特征结构;

(3)微簇的衰减

若没有新数据对象的加入，聚类簇特征向量修改为，其中Δt为上次修改到这次修改的时间间隔;

(4)新的微簇删除及合并

微簇的数量随着数据流不断聚集迅速增加，致使系统的运行效率大大降低;另外，当历史元组从衰减时间滑动窗口中移出时，那些微簇就变成过期微簇，所以需要对那些过期微簇进行删除。对于需要合并的微簇，计算合并后的微簇的各参数的值。

这一过程的伪代码如下:

4 实验与结果分析

4.1 实验环境

对提出的算法DWSWC进行性能测试。实验环境:Intel酷睿三代四核i5处理器i5 3470，主频3.2 GHz,2G内存，Window 7操作系统。在VC++环境下编程。为了验证算法的可靠性，数据选用网上提供的真实数据和自己在本地模拟的数据。模拟数据可以根据算法的需要生成，很好地控制数据的特性，人工数据集是通过Matlab软件用随机数产生器来产生数据，生成数据量为20 000的数据集。网上提供的真实数据集KDDCUP99网络入侵检测流数据集，也都在很多学者的文献中采用[28,29]，为了对比方便，本文在此也采用该数据集作为真实数据集，是从UCI的机器学习数据集网站(http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html)下载的，共有49万余条记录，该记录的详细情况可在网上查询，在此不再赘述。为了验证本文提出的算法DWSWC的有效性，将算法在模拟的动态变速数据流环境中测试，并与Clu Stream算法进行性能比较。

4.2 聚类效果

为了适应DWSWC算法，人工模拟构造的数据流的速度是随时间变化的，为了方便，我们把数据流分割成不同的时间段，在该时间段内，存在一个平均速度v，为当前时间段内所有数据速度的平均值，数据流的即时速度vi为每一时间单元到达数据的瞬时值，由于瞬时值数量较大，在文中不一一列出，数据流的平均速度v的设置见表1所示。

采用本文提出的算法DWSWC在KDD-CUP’99网络入侵数据集上进行验证，算法考虑两个变参，数据流流速和窗口大小。为了验证算法DWSWC的聚类质量，本文将DWSWC算法和Clu Stream算法进行对比。聚类质量在有的文献中采用平方距离和SSQ[5]来衡量，但这种评价指标经分析不适合本文提出的聚类算法。本文采用文献[2]中提到的聚类纯度作为聚类质量衡量标准，算法初始参数的设置如下:窗口初始大小W=1000，窗口上限UW=10 000，衰减因子c=10-5;σ=0.5;权重阈值μ=10;半径阈值R=16;误差因子ε=0.001;η=0.5。实验结果如图1和图2。在图1分别选取处理时刻1000、2000、3000和4000时的聚类纯度分别进行对比，采用的测试数据是网络入侵数据，分别在不同的时间区间对聚类纯度进行比较，在[0,1000]时间区间内，数据流速度较慢。在[2000,3000]时间区间内，DWSWC算法的聚类纯度比Clu Stream算法的聚类纯度略高。在[2000,3000]时间区间内，数据流流速较快，DWSWC算法也能动态调整数据窗口的大小，使数据窗口适应数据流流速的变化。在[3000,4000]时间区间内，数据流流速基本不变，DWSWC算法和Clu Stream算法的聚类纯度也保持一致。所以不管数据流流速是变慢还是变快，DWSWC算法均能调整数据窗口的大小，从而保证较好的聚类质量。同样，DWSWC算法在人工数据集上也得到相同的验证结果，如图2所示。图1和图2体现了每一个时间区间聚类纯度的统计信息，为了进一步的描述数据流的瞬时速度和平均速度对聚类纯度的影响，即每一时刻数据流的聚类纯度，选取[0,1000]时间区间和[3000,4000]时间区间([1000,2000]、[2000,3000]和[0,1000]类似)作为分析的时间区间。由于时间点太多，分析时稍作处理，把100个时间点作为一个间隔，选取处理时刻为100、200、300、400、500、600、700、800、900和1000的聚类纯度做对比，两种数据集在第一时间段内的分析结果分别见图3和图4所示，同理，在第四时间段内的仿真结果分别见图5和图6所示(选取处理时刻为3000、3100、3200、3300、3400、3500、3600、3700、3800、3900和4000)。从图3-图6可以看出DWSWC算法的实时聚类效果优良。

4.3 内存开销

数据流数据量较大，内存的占用量相应地也较普通的数据聚类算法大得多，衡量一个数据流聚类算法的好坏，除了聚类质量这一标准外，还要求算法具有较小的内存空间开销。在本文提出的DWSWC算法中，内存开销的度量单位采用WSWCTCF，因为它跟Clu Stream算法采用的微簇数结构类似，内存开销相当。

在KDD-CUP’99网络入侵检测数据集中，速度逐步提高，速度从100逐步增加到1000，这样就需要不断地改动数据窗口的大小。相应的数据存储快照频率也随着变动，本文在图7中显示了不同的快照存储频率下的对比。在人工数据集中，速度从200递减到100。从图7和图8可以看出无论是数据流速度如何变化，不管速度是变快还是变慢DWSWC算法较Clu Stream算法均能占用较小的内存。

4.4 聚类处理时间

算法效率是通过聚类执行时间来衡量。本文通过DWSWC算法和Clu Stream算法的执行时间对比来测试DWSWC算法的效率。本实验选用KDD-CUP’99网络入侵检测数据集，将在数据流速度v在匀速、加速、减速三种情况下进行仿真对比。仿真结果见图9-图11所示。图9中，数据集的大小从1000变化到6000，数据流的速度为匀速v=400,DWSWC算法和Clu Stream算法的执行时间均随着数据集个数的增长而增长，两种算法的执行时间基本保持一致。在图10和图11中，数据集的大小取值不变，图10中数据流速度预处理为加速，满足v=400+10T,T为数据流的单位时间间隔，图11中数据流速度预处理为减速，满足v=400-10T，图10和图11中Clu Stream算法的聚类处理时间明显高于DWSWC算法的处理时间。通过三种情况下的时间对比可以看出DWSWC算法在数据流速度变化时比Clu S-tream更加有效。

5 结语

本文针对一种崭新的数据流聚类问题，提出了基于动态滑动衰减窗口的变速数据流聚类算法DWSWC。该算法对数据流流速和数据流窗口大小之间建立了自适应可调的函数关系。依据这一函数关系，随着数据流速度的改变，数据流窗口大小将动态发生变化。数据流的流速是时刻变化的，为了避免流速的微小变化引起滑动窗口大小过于频繁的更新，规定了流速的变化区间。采用变异数据流聚类的数据结构来支持基于此种窗口的聚类分析。实验结果表明，本文的算法是可行有效的，相对于Clu Stream算法在准确度和耗费时间上都有所改善。但是，为了防止数据流流速增长过大从而导致滑动窗口过大，算法引入了调节因子参数，调节因子的选取对算法的定量分析没有展开阐述，以后研究的一个重点是如何寻找合适的调节因子，从而进一步改善算法的性能。

摘要：在数据流聚类算法中,滑动窗口技术可以及时淘汰历史元组、只关注近期元组,从而改善数据流的聚类效果。如果同时数据流流速无规律地随时间动态变化,原来单纯的滑动窗口技术在解决这类问题时存在缺陷,所以,在充分考虑了滑动窗口大小和数据流流速之间关系的前提下,提出了基于动态可调衰减滑动窗口的变速数据流聚类算法。该算法对历史元组和近期元组分别赋予一定的权重进行处理,然后依据数据流流速的不同函数改变窗口的大小,从而实现数据流的聚类。提出了该数据流聚类算法的数据结构——变异数据流聚类的数据结构。通过真实数据和模拟数据来构造动态变速数据流从而作为验证算法的原始数据。实验结果表明,与Clu Stream聚类算法相比,该方法具有较高的聚类质量、较小的内存开销和较少的聚类处理时间。