范文一：滑动窗口算法
今天在看USSD相关的资料，对网络传输部分的信息进行了回顾，忍不住又看了一遍通信中用的非常多的滑动窗口算法。滑动窗口算法主要是用来解决系统间通信的时候的流量拥塞及控制问题，一个好的实现既可以提高网络通信的数据流量，同时又能提高通信质量和解决拥塞控制问题。
简要描述一下该算法：
1、将需要传递的信息编码为一个有序的帧序列；
2、发送方设置一个滑动窗口（缓冲区），该窗口大小为最大发送帧数（N）。该缓冲区采用先进先出队列机制，首先发送N帧信息，每帧都有一个定时器，当超时还没有收到接收方的应答帧时，则重发该帧；
3、接收方设置一接收队列，对接收到的每帧入队列。如果该帧是编号最小的帧，则发送该帧收到的应答帧给发送方；
4、发送方如果收到接收方的某帧的应答消息，则判断，如果是队列的第一个帧，则该帧出列。队列空出一位，再发送一帧，否则记录其为可出列标记。
利用滑动窗口算法原理，可以保证一堆数据在有序发送的情况下，顺利的达到接收方。
通过对滑动窗口算法原理的分析，可以将该算法应用在如下场景：
A系统需要给B系统发送大量的资料，这些资料需要拆分为M次才能发送完成，考虑到网络流量问题，不能一次性的就全部把M个数据块发送给B系统。较好的处理方式是设置符合网络流量大小的值N，做为A系统一次发送的数据块个数。N作为滑动窗口的长度。采用滑动窗口算法来完成A、B系统的数
范文二：滑动窗口算法原理
1. 滑动窗口算法
--------------------------------------------------------------------------------
滑动窗口算法工作过程如下。首先,发送方为每 1帧赋一个序号(sequence number) ,记作 S e q N u m 。现在,让我们忽略 S e q N u m是由有限大小的头部字段实现的事实,而假设 它能无限增大。发送方维护 3个变量:发送窗口大小(send window size) ,记作 S W S ,给 出发送方能够发
送但未确认的帧数的上界; L A R 表示最近收到的确认帧 (last acknowledgement re c e i v e d ) 的序号; L F S 表示最近发送的帧 (last frame sent) 的序号, 发送方还维持如下的不变式: LAR-LFR ≤ RWS
当一个确认到达时,发送方向右移动 L A R,从而允许发送方发送另一帧。同时,发送方为 所发的每个帧设置一个定时器,如果定时器在 A C K 到达之前超时,则重发此帧。注意:发送方必须存储最多 S W S个帧,因为在它们得到确认之前必须准备重发。
接收方维护下面 3个变量:接收窗口大小(receive window size) ,记为 RW S,给出接收方 所能接收的无序帧数目的上界; L A F表示可接收帧(l a rgest acceptable frame)的序号; L F R表示最近收到的帧(last frame re c e i v e d)的序号。接收方也维持如下不变式: LFS-LAR ≤ SWS
当一个具有顺序号 S e q N u m的帧到达时,接收方采取如下行动:如果 S e q N u m≤ L F R或 S e q N u m > L A F,那么帧不在接收窗口内,于是被丢弃;如果 L F R
关于这个方案的另一个变种是使用选择确认 (selective acknowledgements) 。 即,接收方能够 准确地确认那些已收到的帧,而不只是确认按顺序收到最高序号的帧。 因此,在上例中,接 收方能够确认帧 7、 8的接收。 如果给发送方更多的信息, 就能使其较容易地保持管道满载, 但增加了实现的复杂性。
发送窗口大小是根据一段给定时间内链路上有多少待确认的帧来选择的; 对于一个给定的延 迟与带宽的乘积, S W S是容易计算的。另一方面,接收方可以将 RW S设置为任何想要的 值。通常的两种设置是:RW S= 1,表示接收方不存储任何错序到达的帧; RW S=S W S, 表示接收方能够缓存发送方传输的任何帧。由于错序到达的帧的数目不可能超过 S W S个, 所以设置 RWS >S W S没有意义。
2. 有限顺序号和滑动窗口
--------------------------------------------------------------------------------
现在我们再来讨论算法中做过的一个简化, 即假设序号是可以无限增大的。 当然, 实际上是 在一个有限的头部字段中说明一个帧的序号。 例如, 一个 3比特字段意味着有 8个可用序号 0 ~ 7。 因此序号必须可重用, 或者说序号能回绕。 这就带来了一个问题:要能够区别同一序 号的不同次发送实例,这意味着可用序号的数目必须大于所允许的待确认帧的数目。例如, 停止等待算法允许一次有 1个待确认帧,并有 2个不同的序号。
假设序号空间中的序号数比待确认的帧数大 1,即 S W S ≤ M A a x S e q N u m -1 ,其中 M a x Seq N u m 是可用序号数。这就够了吗?答案取决于 RW S 。如果 RW S = 1,那么 MaxSeqNum ≥ SWS+1是足够了。如果 RW S等于 S W S,那么有一个只比发送窗口尺寸大 1的 M a x S e q N u m是不够的。 为看清这一点,考虑有 8个序号 0 ~ 7的情况,并且 S W S = RW S = 7。假设发送方传输帧 0 ~ 6,并且接收方成功接收,但 A C K丢失。接收方现在 希望接收帧 7, 0 ~ 5,但发送方超时,然后发送帧 0 ~ 6。不幸的是,接收方期待的是第二 次的帧 0 ~ 5,得到的却是第一次的帧 0 ~ 5。这正是我们想避免的情况。
结果是, 当 RW S = S W S时, 发送窗口的大小不能大于可用序号数的一半, 或更准确地说, SWS<(maxseqnum+1) 直观地,这说明滑动窗口协议是在序号空间的两半之间变换,就像="" 停止等待协议的序号是在="" 0和="" 1之间变换一样。="" 唯一的区别是,="" 它在序号空间的两半之间连="">
注意,这条规则是特别针对 RW S = S W S的。我们把确定适用于 RW S和 S W S的任意值 的更一般的规则留做一个练习。 还要注意, 窗口的大小和序号空间之间的关系依赖于一个很 明显以至于容易被忽略的假设, 即帧在传输中不重新排序。 这在直连的点到点链路上不能发 生, 因为在传输过程中一个帧不可能赶上另一个帧。 然而, 我们将在第 5章看到用在一个不 同环境中的滑动窗口算法,并且需要设计另一条规则。
3. 滑动窗口的实现
--------------------------------------------------------------------------------
下面的例程说明我们如何实现滑动窗口算法的发送和接收的两个方面。 该例程取自一个正在 使用的协议,称为滑动窗口协议 S W P(Sliding Window Pro t o c o l) 。为了不涉及协议图中 的邻近协议,我们用 H L P(高层协议)表示 S W P上层的协议,用 L I N K(链路层协议) 表示 S W P下层的协议。 我们先定义一对数据结构。首先, 帧头部非常简单:它包含一个序 号(S e q N u m)和一个确认号(A c k N u m) 。它还包含一个标志(F l a g s)字段,表 明帧是一个 A C K帧还是携带数据的帧。
其次,滑动窗口算法的状态有如下结构。对于协议发送方,该状态包括如上所述的变量 L A R 和 L F S,以及一个存放已发出但尚未确认的帧的队列 (s e n d Q) 。 发送方状态还包含一 个计数信号量(counting semaphore) ,称为 s e n d Wi n d o w N o t F u l l。下面我们将会看 到如何使用它, 但一般来说, 信号量是一个支持 s e m Wa i t和 s e m S i g n a l操作的同步原 语。每次调用 S e m S i g n a l,信号量加 1,每次调用 S e m Wa i t,信号量减 1。如果信号 量减小,导致它的值小于 0,那么调用进程阻塞(挂起) 。一旦执行了足够的 s e m S i g n a l操作而使信号量的值增大到大于 0,在调用 s e m Wa i t的过程中阻塞的进程就允许被恢复。 对于协议的接收方, 如前所述, 该状态包含变量 L F R , 加上一个存放已收到的错序帧的队 列(r e c v Q ) 。最后,虽然未显示,发送方和接收方的滑动窗口的大小分别由常量 S W S 和 RW S表示。
S W P的发送方是由 s e n d S W P过程实现的。这个例程很简单。首先, s e m Wa i t使这 个进程在一个信号量上阻塞,直到它可以发另一帧。一旦允许继续, s e n d S W P设置帧 头部中的顺序号,将此帧的拷贝存储在发送队列(s e n d Q )中,调度一个超时事件以便 处理帧未被确认的情况,并将帧发给低层协议。
值得注意的一个细节是刚好在调用 m s g A d d H d r之前调用 s t o r e _ s w p _ h d r。该例程 将存有 S W P头部的 C 语言结构 (s t a t e - > h d r) 转化为能够安全放在消息前面的字节串 (h b u f) 。该例程(未给出)必须将头部中的每一个整数字段转化为网络字节顺序,并且 去掉编译程序加入 C 语言结构中的任意填充。 7 . 1节将详细讨论字节顺序的问题,但现在, 假设该例程将多字整数中最高有效位放在最高地址字节就足够了。
这个例程的另一个复杂性是使用 s e m Wa i t 和 s e n dW i n d o w N o t F u l l 信号量。 S e n dWi n d o w N o t F u l l被初始化为发送方滑动窗口的大小 S W S(未给出这一初始化) 。发 送方每传输一帧, s e m Wa i t操作将这个数减 1,如果减小到 0,则阻塞发送方进程。每收 到一个 A C K,在 d e l i v e r S W P中调用 s e m S i g n a l操作(见下面)将此数加 1,从而 激活正在等待的发送方进程。
在继续介绍 S W P的接收方之前,需要调整一个看上去不一致的地方。一方面,我们说过, 高层协议通过调用 s e n d操作来请求低层协议的服务,所以我们就希望通过 S W P发送消 息的协议能够调用 s e n d(S W P, p a c k e t) 。另一方面,用来实现 S W P的发送操作的过 程叫做 s e n d S W P, 并且它的第一个参数是一个状态变量 (S w p S t a t e) 。 结果怎样呢? 答案是, 操作系统提供了粘结代码将对 s e n d的一般调用转化为对 s e n d S W P的特定协议 调用的粘结代码。这个粘结代码将 s e n d的第一个参数(协议变量 S W P)映射为一个指向 s e n d S W P的函数指针和一个指向 S W P工作时所需的协议状态的指针。我们之所以通过 一般函数调用使高层协议间接调用特定协议函数, 是因为我们想限制高层协议中对低层协议 编码的信息量。 这使得将来能够比较容易地改变协议图的配置。现在来看 d e l i v e r操作的 S W P的特定协议实现,它在过程 d e l i v e r S W P中实现。这个例程实际上处理两种不同 类型的输入消息:本结点已发出帧的 A C K 和到达这个结点的数据帧。在某种意义上,这 个例程的 ACK 部分是与 send SWP中所给算法的发送方相对应的。 通过检验头部的 F l a g s字段可以确定输入的消息是 ACK 还是一个数据帧。注意,这种特殊的实现不支持数据帧中 捎带 A C K。当输入帧是一个 ACK 时, delive rSWP仅仅在发送队列(send Q)中找到与此 ACK 相应的位置(slot ) ,取消超时事件,并且释放保存在那一位置的帧。由于 A C K可能 是累积的, 所以这项工作实际上是在一个循环中进行的。 对于这种情况值得注意的另一个问 题是子例程 swp In Wind o w的调用。这个子例程在下面给出,它确保被确认帧的序号是在 发送方当前希望收到的 A C K的范围之内。
当输入帧包含数据时, d e l i v e r S W P首先调用 m s g S t r i p H d r和 l o a d _ s w p _ h d r以便从帧中提取头部。例程 l o a d _ s w p _ h d r对应着前面讨论的 s t o r e _ s w p _ h d r, 它将一个字节串转化为容纳 S W P头部的 C 语言数据结构。 然后 d e l i v e r S W P调用 s w p
I n Wi n d o w以确保帧序号在期望的序号范围内。 如果是这样, 例程在已收到的连续的帧的 集合上循环,并通过调用 d e l i v e r H L P例程将它们传给上层协议。它也要向发送方发送 累积的 A C K, 但却是通过在接收队列上循环来实现的 (它没有使用本节前面给出的 s e q N u m To A c k变量) 。
最后, s w p I n Window 是一个简单的子例程,它检查一个给定的序号是否落在某个最大和 最小顺序号之间。
4. 帧顺序和流量控制
--------------------------------------------------------------------------------
滑动窗口协议可能是计算机网络中最著名的算法。 然而, 关于该算法易产生混淆的是, 它可 以有三个不同的功能,第一个功能是本节的重点,即在不可靠链路上可靠地传输帧。 (一般 来说,该算法被用于在一个不可靠的网络上可靠地传输消息。 )这是该算法的核心功能。 滑动窗口算法的第二个功能是用于保持帧的传输顺序。 这在接收方比较容易实现, 因为每个 帧有一个序号, 接收方要保证已经向上层协议传递了所有序号比当前帧小的帧, 才向上传送 该当前帧。即,接收方缓存了(即没有传送)错序的帧。本节描述的滑动窗口算法确实保持 了帧的顺序, 尽管我们可以想象一个变异, 即接收方没有等待更早传送的帧都到达就将帧传 给下一个协议。 我们可以提出的一个问题是:我们是否确实需要滑动窗口协议来保持帧的顺 序,或者, 这样的功能在链路层是否是不必要的。 不幸的是, 我们还没有看到足够多的网络 体系结构来回答这个问题我们首先需要理解的是, 点到点链路序列如何由交换机连接而形成 一条端到端的路径。
滑动窗口算法的第三个功能是,它有时支持流量控制(f l o w c o n t ro l) ,它是一种接收方 能够控制发送方使其降低速度的反馈机制。 这种机制用于抑制发送方发送速度过快, 即抑制 传输比接收方所能处理的更多的数据。 这通常通过扩展滑动窗口协议完成, 使接收方不仅确 认收到的帧, 而且通知发送方它还可接收多少帧。 可接收的帧数对应着接收方空闲的缓冲区 数。 在按序传递的情况下, 在将流量控制并入滑动窗口协议之前, 我们应该确信流量控制在 链路层是必要的。
尚未讨论的一个重要概念是系统设计原理, 我们称其为相关性分离 (separation of concerns) 。 即, 你必须小心区别有时交织在一种机制中的不同功能, 并且你必须确定每一个功能是必要 的,而且是被最有效的方式支持的。 在这种特定的情况下,可靠传输、 按序传输和流量控制 有时组合在一个滑动窗口协议里, 我们应该问问自己, 在链路层这样做是否正确。 带着这样 的疑问,我们将在第 3章(说明 X. 2 5网如何用它实现跳到跳的流量控制)和第 5章(描述 T C P如何用它实现可靠的字节流信道)重新考虑滑动窗口算法。
范文三：滑动窗口算法
滑动窗口算法
1. 滑动窗口算法
滑动窗口算法工作过程如下。 首先, 发送方为每 1帧赋一个序号 (sequence number) , 记作 S e q N u m。 现在, 让我们忽略 S e q N u m是由有限大小的头部字段实现的事实,而假设它能无限增大。 发送方维护 3个变量 :发送窗口大小 (send window size),记作 S W S, 给出发送方已经发
送但未确认的帧数的上界; L A R表示最近收到的确认帧 (last acknowledgement re c e i v e d) 的序号; L F S表示最近发送的帧 (last frame sent)的序号,发送方还维持如下的不变式:
LAR-LFR≤RWS
当一个确认到达时,发送方向右移动 L A R,从而允许发送方发送另一帧。同时,发送方为所发的每个帧设置一个定时器,如果定时 器在 A C K到达之前超时,则重发此帧。注意:发送方必须存储 最多 S W S个帧,因为在它们得到确认之前必须准备重发。
接收方维护下面 3个变量:接收窗口大小 (receive window size),记为 RW S/* 对应允许接受的数据包 */,给出 接收方所能接收的无 序帧数目的上界 ; L A F表示可接收帧(largest acceptable frame)的序号; L F R表示最近收到的帧(last frame re c e i v e d)的序号。 接收方也维持如下不变式:
LFS-LAR≤SWS
(NFE为等待下一帧的序号 )
当一个具有顺序号 S e q N u m的帧到达时,接收方采取如下行动:如果 S e q N u m≤L F R或 S e q N u m > L A F,那么帧不在接收窗 口内,于是被丢弃;如果 L F R
注意,在这个例子中,接收方可以在帧 7刚一到达时就为帧 6发送一个认帧 N A K(negative acknowl edgment)。然而,由于发送方 的超时机制足以发现这种情况,发送 N A K反而为发送方增加了复杂性,因此不必这样做。正如我们已提到的,当帧 7和 8到达时为 帧 5发送一个额外的 A C K是合理的;在某些情况下,发送方可以使用重复的 A C K作为一个帧丢失的线索。这两种方法都允许早期 的分组丢失检测,有助于改进性能。
关于这个方案的另一个变种是使用选择确认(selective acknowledgements)。即,接收方能够准确地确认那些已收到的帧,而不只是确 认按顺序收到最高序号的帧。因此,在上例中,接收方能够确认帧 7、 8的接收。如果给发送方更多的信息,就能使其较容易地保持 管道满载,但增加了实现的复杂性。
发送窗口大小是根据一段给定时间内链路上有多少待确认的帧来选择的;对于一个给定的延迟与带宽的乘积, S W S是容易计算的。 另一方面, 接收方可以将 RW S设置为任何想要的值。 通常的两种设置是:RW S= 1, 表示接收方不存储任何错序到达的帧; RW S=S W S,表示接收方能够缓存发送方传输的任何帧。由于错序到达的帧的数目不可能超过 S W S个,所以设置 RWS >S W S没有意义。
2. 有限顺序号和滑动窗口
现在我们再来讨论算法中做过的一个简化,即假设序号是可以无限增大的。当然,实际上是在一个有限的头部字段中说明一个帧的序 号。例如,一个 3比特字段意味着有 8个可用序号 0 ~ 7。因此序号必须可重用,或者说序号能回绕。这就带来了一个问题:要能够区 别同一序号的不同次发送实例,这意味着可用序号的数目必须大于所允许的待确认帧的数目。例如,停止等待算法允许一次有 1个待 确认帧,并有 2个不同的序号。
假设序号空间中的序号数比待确认的帧数大 1, 即 S W S ≤ M A a x S e q N u m -1 , 其中 M a x Seq N u m 是可用序号数。 这就够了吗? 答案取决于 RW S 。如果 RW S = 1,那么 MaxSeqNum≥SWS+1是足够了。如果 RW S等于 S W S,那么有一个只比发送窗口尺寸大 1的 M a x S e q N u m是不够的。为看清这一点,考虑有 8个序号 0 ~ 7的情况,并且 S W S = RW S = 7。假设发送方传输帧 0 ~ 6,并 且接收方成功接收,但 A C K丢失。接收方现在希望接收帧 7, 0 ~ 5,但发送方超时,然后发送帧 0 ~ 6。不幸的是,接收方期待的是 第二次的帧 0 ~ 5,得到的却是第一次的帧 0 ~ 5。这正是我们想避免的情况。
结果是,当 RW S = S W S时,发送窗口的大小不能大于可用序号数的一半,或更准确地说, SWS<(maxseqnum+1) 直观地,这说明="" 滑动窗口协议是在序号空间的两半之间变换,就像停止等待协议的序号是在="" 0和="" 1之间变换一样。唯一的区别是,它在序号空间的两="">
注意,这条规则是特别针对 RW S = S W S的。我们把确定适用于 RW S和 S W S的任意值的更一般的规则留做一个练习。还要注意, 窗口的大小和序号空间之间的关系依赖于一个很明显以至于容易被忽略的假设,即帧在传输中不重新排序。这在直连的点到点链路上 不能发生,因为在传输过程中一个帧不可能赶上另一个帧。然而,我们将在第 5章看到用在一个不同环境中的滑动窗口算法,并且需 要设计另一条规则。
3. 滑动窗口的实现
下面的例程说明我们如何实现滑动窗口算法的发送和接收的两个方面。该例程取自一个正在使用的协议,称为滑动窗口协议 S W P (Sliding Window Pro t o c o l)。为了不涉及协议图中的邻近协议,我们用 H L P(高层协议)表示 S W P上层的协议,用 L I N K(链 路层协议)表示 S W P下层的协议。我们先定义一对数据结构。首先,帧头部非常简单:它包含一个序号(S e q N u m)和一个确认 号(A c k N u m)。它还包含一个标志(F l a g s)字段,表明帧是一个 A C K帧还是携带数据的帧。
其次,滑动窗口算法的状态有如下结构。对于协议发送方,该状态包括如上所述的变量 L A R 和 L F S ,以及一个存放已发出但尚未 确认的帧的队列(s e n d Q)。发送方状态还包含一个计数信号量(counting semaphore),称为 s e n d Wi n d o w N o t F u l l。下面 我们将会看到如何使用它,但一般来说,信号量是一个支持 s e m Wa i t和 s e m S i g n a l操作的同步原语。每次调用 S e m S i g n a l, 信号量加 1,每次调用 S e m Wa i t,信号量减 1。如果信号量减小,导致它的值小于 0,那么调用进程阻塞(挂起)。一旦执行了足 够的 s e m S i g n a l操作而使信号量的值增大到大于 0,在调用 s e m Wa i t的过程中阻塞的进程就允许被恢复。
对于协议的接收方,如前所述,该状态包含变量 L F R ,加上一个存放已收到的错序帧的队列(r e c v Q)。最后,虽然未显示,发 送方和接收方的滑动窗口的大小分别由常量 S W S和 RW S表示。
S W P的发送方是由 s e n d S W P过程实现的。这个例程很简单。首先, s e m Wa i t使这个进程在一个信号量上阻塞,直到它可以发 另一帧。一旦允许继续, s e n d S W P设置帧头部中的顺序号,将此帧的拷贝存储在发送队列(s e n d Q)中,调度一个超时事件以 便处理帧未被确认的情况,并将帧发给低层协议。
值得注意的一个细节是刚好在调用 m s g A d d H d r之前调用 s t o r e _ s w p _ h d r。该例程将存有 S W P头部的 C 语言结构(s t a t e - > h d r) 转化为能够安全放在消息前面的字节串 (h b u f) 。 该例程 (未给出) 必须将头部中的每一个整数字段转化为网络字节顺序, 并且去掉编译程序加入 C 语言结构中的任意填充。 7 . 1节将详细讨论字节顺序的问题,但现在,假设该例程将多字整数中最高有效位 放在最高地址字节就足够了。
这个例程的另一个复杂性是使用 s e m Wa i t 和 s e n dW i n d o w N o t F u l l 信号量。 S e n dWi n d o w N o t F u l l被初始化为发送方 滑动窗口的大小 S W S(未给出这一初始化)。发送方每传输一帧, s e m Wa i t操作将这个数减 1,如果减小到 0,则阻塞发送方进 程。每收到一个 A C K,在 d e l i v e r S W P中调用 s e m S i g n a l操作(见下面)将此数加 1,从而激活正在等待的发送方进程。
在继续介绍 S W P的接收方之前,需要调整一个看上去不一致的地方。一方面,我们说过,高层协议通过调用 s e n d操作来请求低层 协议的服务,所以我们就希望通过 S W P发送消息的协议能够调用 s e n d(S W P, p a c k e t)。另一方面,用来实现 S W P的发送操 作的过程叫做 s e n d S W P,并且它的第一个参数是一个状态变量(S w p S t a t e)。结果怎样呢?答案是,操作系统提供了粘结代 码将对 s e n d的一般调用转化为对 s e n d S W P的特定协议调用的粘结代码。 这个粘结代码将 s e n d的第一个参数 (协议变量 S W P) 映射为一个指向 s e n d S W P的函数指针和一个指向 S W P工作时所需的协议状态的指针。我们之所以通过一般函数调用使高层协议 间接调用特定协议函数,是因为我们想限制高层协议中对低层协议编码的信息量。这使得将来能够比较容易地改变协议图的配置。现 在来看 d e l i v e r操作的 S W P的特定协议实现,它在过程 d e l i v e r S W P中实现。这个例程实际上处理两种不同类型的输入消息:本结点已发出帧的 A C K和到达这个结点的数据帧。 在某种意义上, 这个例程的 ACK 部分是与 send SWP中所给算法的发送方相对应 的。通过检验头部的 F l a g s字段可以确定输入的消息是 ACK 还是一个数据帧。注意,这种特殊的实现不支持数据帧中捎带 A C K。 当输入帧是一个 ACK 时, delive rSWP仅仅在发送队列(send Q)中找到与此 ACK 相应的位置(slot ),取消超时事件,并且释放保 存在那一位置的帧。由于 A C K可能是累积的,所以这项工作实际上是在一个循环中进行的。对于这种情况值得注意的另一个问题是 子例程 swp In Wind o w的调用。这个子例程在下面给出,它确保被确认帧的序号是在发送方当前希望收到的 A C K的范围之内。 当输入帧包含数据时, d e l i v e r S W P首先调用 m s g S t r i p H d r和 l o a d _ s w p _ h d r以便从帧中提取头部。 例程 l o a d _ s w p _ h d r对应着前面讨论的 s t o r e _ s w p _ h d r,它将一个字节串转化为容纳 S W P头部的 C 语言数据结构。然后 d e l i v e r S W P调用 s w p I n Wi n d o w以确保帧序号在期望的序号范围内。 如果是这样, 例程在已收到的连续的帧的集合上循环, 并通过调用 d e l i v e r H L P 例程将它们传给上层协议。它也要向发送方发送累积的 A C K ,但却是通过在接收队列上循环来实现的(它没有使用本节前面给 出的 s e q N u m To A c k变量)。
最后, s w p I n Window 是一个简单的子例程,它检查一个给定的序号是否落在某个最大和最小顺序号之间。
4. 帧顺序和流量控制
滑动窗口协议可能是计算机网络中最著名的算法。然而,关于该算法易产生混淆的是,它可以有三个不同的功能, 第一个功能是本节 的重点,即在不可靠链路上可靠地传输帧。 (一般来说,该算法被用于在一个不可靠的网络上可靠地传输消息。) 这是该算法的核心 功能 。
滑动窗口算法的第二个功能是用于保持帧的传输顺序 。这在接收方比较容易实现,因为每个帧有一个序号,接收方要保证已经向上层 协议传递了所有序号比当前帧小的帧,才向上传送该当前帧。即,接收方缓存了(即没有传送)错序的帧。本节描述的滑动窗口算法 确实保持了帧的顺序,尽管我们可以想象一个变异,即接收方没有等待更早传送的帧都到达就将帧传给下一个协议。我们可以提出的 一个问题是:我们是否确实需要滑动窗口协议来保持帧的顺序,或者,这样的功能在链路层是否是不必要的。不幸的是,我们还没有 看到足够多的网络体系结构来回答这个问题我们首先需要理解的是,点到点链路序列如何由交换机连接而形成一条端到端的路径。
滑动窗口算法的第三个功能是, 它有时支持流量控制 (f l o w c o n t ro l), 它是一种接收方能够控制发送方使其降低速度的反馈机制。 这种机制用于抑制发送方发送速度过快, 即抑制传输比接收方所能处理的更多的数据。这通常通过扩展滑动窗口协议完成,使接收方 不仅确认收到的帧,而且通知发送方它还可接收多少帧。可接收的帧数对应着接收方空闲的缓冲区数。在按序传递的情况下,在将流 量控制并入滑动窗口协议之前,我们应该确信流量控制在链路层是必要的。
尚未讨论的一个重要概念是系统设计原理,我们称其为相关性分离(separation of concerns)。即, 你必须小心区别有时交织在一种机 制中的不同功能 ,并且你必须确定每一个功能是必要的,而且是被最有效的方式支持的。在这种特定的情况下, 可靠传输、按序传输 和流量控制有时组合在一个滑动窗口协议里 ,我们应该问问自己,在链路层这样做是否正确。带着这样的疑问,我们将在第 3章(说 明 X. 2 5网如何用它实现跳到跳的流量控制)和第 5章(描述 T C P如何用它实现可靠的字节流信道)重新考虑滑动窗口算法。
范文四：时间滑动窗口内基于密度的数据流聚类算法
: 1001 , 9081( 2011) 05 , 01363 , 04doi: 10, 3724 / SP, J, 1087, 2011, 01363文章编号
时间滑动窗口内基于密度的数据流聚类算法
，娜邢长征李
( )，125105辽宁工程技术大学 电子与信息工程学院辽宁 葫芦岛
( linna_86@ 163, com)
: ，，摘 要为了提高数据流的聚类质量和效率采用等时间跨度滑动窗口技术然后利用改进的微簇结构保存数据
，，、。: 流的概要信息最后利用微簇删除策略定期删除过期孤立微簇基于真实数据集与人工数据集的实验表明与传统
，、。基于界标模型的聚类算法相比该算法可获得较好的效率较小的内存开销和快速的数据处理能力
: ; ; ; ; 关键词数据流聚类滑动窗口微簇界标模型
TP311, 13:: A中图分类号文献标志码
Density-based data stream clustering algorithm over
timebased sliding windows -
LI Na, XNG Chang-zheng I
( Coege of Eectroncs and nformaton Engneerng,Laonng Technca Unversty, Huudao Laonng 125105, Chna) llliIiiiiiiliiliiiAbstact: Stream data custerng agorthm was mproved in termso f custer quaty and effcency, Ths paper adopted a rliliilliiii
new method toi mprove cluster quality and efficiency, Firstly, the technology of the time-based sliding window was
apped,S econdy, the structureo f mproved mcro-custer was created tosav e the summary, Fnay, a new strategy was liliilill
designed to regularly delete expired micro-clusters and outlier micro-clusters, Compared with traditional clustering algorithms of
landmark- based model, the proposed method is of better efficiency, less memory overhead and fast data processing
capabilities,
Key words: data stream; clustering; sliding window; micro cluster; landmark model based Data Stream Clustering Algorithm over Time-based Sliding 0 引言Window) 。: TSWDCluStream 主要工作有算法提出新的微簇 ，，删除策略及时地删除过期微簇或孤立微簇提高聚类质量和 、，随着计算机技术通信技术以及网络技术的飞速发展许
，;速度在很大程度上降低了算法的 时间和空间复杂 性 、、多应用领域时刻都在产生连续达到持续增长动态进化化的 ,1 , 3,，———、数据数据流常见的应用有网络监控日志银行交易 TSWDCluStream ，算法采用一种等时间跨度滑动窗口的思想。信息等从数据流中获取知识的数据挖掘研究得到了广泛的 ,9 , 11, ，这种思想有别于传统的计数的滑动窗口由于金字塔结，关注数据流中获取知识发现的重要手段也得到了深入的研 ，，构的限制存储快照模型存在误差而时间滑动窗口能够很好 ,4,。: STREAM CluStream 究典型的数据流聚类算法有算法和 ，地满足那些只关心近期特定周期内数据的应用需求能很好 ,5,。STREAM ，算法算 法 采 用分而治之的聚类技 术并 以 ; TSWDCluStream 地弥补金字塔结构的不足算法提出了适合 K-means; 算法为基础能够确保簇和簇内元组之间的误差平方 ，。时间滑动窗口内的聚类微簇特征该结构能够被增量维护，, CluStream 和最小但没有考虑数据流的进化算法设计了一
，通过一系列真实和人工数据集上的实验验证了本文算法的，种金字塔时间框架保存实时聚类结果具有良好的可扩展性
。可行性和有效性 ; ，， 和高聚类质量包括在线和离线两部分前者进行实时聚类
，后者则在前者基础上进行宏聚类和聚类进化分析但是没有 1 ,6,预备知识 ，HPStream D- 。、体现 出近期数据的重要 性之 后算 法 ,7,相关概念 Stream CluStrcam 1, 1 ，算法等都借鉴了 算法的两阶段聚类模
1 。R 定义 核对象如果一个对象的 域至少包含最小数 。，式由于大部分聚类算法采用了距离度量不能很好地处理 ,8,。Cao 任意形状的数据流为此 等人提出了基于密度的数据 ，。 目 μ 个对象则称该对象为核心对象DenStream，。 流聚类算法 着眼于处理任意形状的数据流问题2 。t，mc 定义 核心微簇时刻 假设微簇 中维护了一组带
CuStream ，。，l它强调了孤立点检测问题同时与 算法相比它 T，T，…，Tx，x，…，x。，有时间标签 的元组 此时可用 1 2 n 1 2 n iiiiii，只能提供对当前数据流的一种描述不能反映用户指定时间 CMC( w，c，r) :三元组特征结构 对其进行定义
n 。窗内的流数据的变化情况
，针对这些不足本文在已有算法基础上提出了时间滑动 w ? μ w = f( t ,T ) ;ij ? j = 1TSWDCluStream ( Density-窗口内基于密度的数据流聚类算法 n
f( t ,T ) xij ij? j 1 = c = w
: 2010 , 10 , 20; : 2011 , 01 , 14。收稿日期修回日期
: ( 1986 ,) ，，，，: 、; ( 1967 ,) ，，，，作者简介李娜数据挖掘数据流聚类邢长征女山东聊城人硕士研究生主要研究方向男辽宁阜新人教授
: ，、、。博士主要研究方向数据库数据挖掘数据流聚类
n TSWDCluStream 。法 分为两个阶段f( t ,T ) dist( x，c)ij ij ? 1) ( OnlineTSWDCS) : 微簇在线维护过程针对时间滑动窗 j = 1 r =; r ? ε，，口内的数据流进行处理存储数据流的汇总信息并进行增量 w
。更新维护数据的概要信息结构 : w ， ; w ，c ，r 。 其中满足 μ为权重为中心为半径2) ( OffneTSWDCS) : li最终簇离线生成过程根据用户聚类 3 t，mc 。定义 微簇时刻 假设微簇 中维护了一组带有时 ，，请求从金字塔框架中获取某个时 间 粒 度 的 快 照利 用 T，T，…，Tx，x，…，x。，间标签 的元组 此时可用五元 i1 i2 in i1 i2 in DBSCAN 。算法获取最终的聚类结果本文重点讨论在线维护 : 组特征结构对其进行定义 。过程 X X FCS( C，t) = ( FCS2( C，t) ，FCS1( C，t) ，w，t，) τ 2, 2 数据结构 X X : FCS2( C，t) ，FCS1( C，t) 其中为加权平方和为加权线性TSDCuStream Wl算法 使用了时间滑动窗口模型对数据流 ，w ，t 。和为权重和为最后到达该簇的点时间 ，，进行分析处理只存储最近的数据窗口不需要保存基本窗口 n，。内的所有数据后再进行处理从而减少了内存的需求具体 X j 2( FCS2( C，t) = f( t ,T ) ( x) ? ik ik? :步骤如下 k = 1 n 1) ( ntTSdngWndow) Iiliii。时间滑动窗口的初始化 X j ( FCS1( C，t) = f( t ,T ) ( x)? ik ki? B。每个基本窗口 里有不同数量的数据流将每个基本 i k = 1 TA,i,，TA n窗口的摘要信息都存入到阈值数组 在数组 里有 w( t) = f( t ,T )W + 1 ( W ) 。个元组是基本窗口个数 ik ? k = 12) ( UpdateTSlidingWindow) 。时间滑动窗口的更新 :有了上面的数据可以得出微簇的中心为 每一次滑动窗口的更新包括一个新基本窗口概要信息的 X c = FCS1( C，t) / w( t)
:微簇的半径为
X 2X r = FCS2( C，t) / w( t),( FCS1( C，t) / w( t) 槡。B ，添加和一个过期基本窗口概要信息的删除当 到达时 i DenStream ( t，3 ，算法的维簇结构引入特征 定义 扩展了 TA,j,Bj W + 1，,j ，0 ，1 i 。保持着 的值其中 ? ? 并且 处 i , j ) ， w 。τ有助于更全面的描述任意形状的簇当权重 βμ ? B，TA,W + 1,，，理完 之后最后一个 被忽略其他的向下移动 i ( 0 ， ，1 ) ，= 1，; = 0， β 则 τ 即该微簇为候选核心簇否则 τ : TA,j,TA,j + 1,，BTA,1,。 即最后的 的值放入到 ? i。即该微簇为孤立核心簇 , 32算法描述1, 2 时间滑动窗口 OnneTSWDCSli。算法，在许多应用领域新数据往往比旧数据更重要时间窗口 DS; T; 输入 动态数据流 时间滑动窗口周期 权重阈值 模型能够很好地满足那些只关心近期特定周期内数据的应用 d
; ; ; 。 。:μ半径阈值 ε衰减因子 λ 误差因子 β需求具体定义如下
,12,。 输出 存储在金字塔模型中的微簇4 t p，。定义 基本窗口给定一时刻 和时间跨度 在
:执行步骤如下 ( t ,p ，p ,时间段内到达的数据流数据组成一个时间相关基
1) 微簇的初始化。B，bi ，本窗口 记 为数据流的第 个时间基本窗口基本窗口大 t DBSCAN N { P} ，{ P} ， 应用 算法初始化 个对象通过扫描b,s i ze = | b| ，b,s p an = p。小 时间跨度 t t t ，p，r ，R ，w ， 找出候选核心簇如果对于对象 在 的条件下 βμ? 5 。定义 时间滑动窗口一个连续的时间相关基本窗口p ，{ P} p。则 归为候选核心微簇并且从中删除对象
2) 。添加数据对象 SB，SB= b，b，…，b记 序列构成一个时间滑动窗口 i , w +1 , w +2 iiiW B，B在时间滑动窗口 内的基本窗口 对于 到达的新 i i i ，W 为第 个基本窗口到达后的时间滑动窗口其中 表示一个p，rR ，，的对象 如果满足 ? 则对象归入到孤立核心簇其中 p ，sb,s p an = W ×p 。滑动窗口容纳基本的数目时间跨度 i : 2 2 1 等时间跨度滑动窗口的思想每两个相邻的滑动窗口的 ( CF+ p，CF+ p，w + 1，t，) ; τ否则归入簇特征结构修改为 p，时间跨度为 保证在对两个连续的滑动窗口中的数据采样 ，到孤立核心簇并修改簇特征结构
3) 。，，建立新核心簇 时有重叠的数据存在分析两个连续滑动窗口的数据流变化
，w ，在孤立核心簇中满足 βμ 则将孤立核心簇从缓冲 ? 。情况 ，。区中删除建立一个新的孤立核心簇 , 31时间衰减模型4) 。微簇的衰减 ，实际数据流应用中最近元组所蕴含的知识往往要比历 ，若没有 新 数 据 对 象 的 加 入聚类簇特征向量修改为 。，史元组有价值为此本文采用时间衰减模型逐步衰减历史 。t，元组密度的权重在时刻 每个元组的衰减因子的大小满 2 , λΔt 1 , λΔt , λΔt ( CF×2 ，CF× 2 ，w × 2 ，t ，) ，t τ其中 Δ为特征向量 l, tλ : 2 ， ( ，0 ) ，，。 足ελ λ 值越大历史数据的重要性就越低 。上次修改到当前修改的时间间隔
5) 。新的微簇删除策略 :数据流总的权重t = t c，，数据流不断运行孤立核心簇的数量迅速增加严重降低 v , λt = W( t) = v2 ; ，了系统的运行效率另外当历史元组从时间滑动窗口中移出 ?, λ 1 ,2 t = 0，，时一些微簇也能变成过期微簇所以有必要对那些过期或孤 : t。，v 其中表示当前时间表示数据流的流速 c ( T) t，。立簇进行定期删除删除周期设 令当前时刻为 基本 d c
2 TSWDCluStream 的算法 T ，2 T: T，T 。窗口的时间周期 且 ? 下面分情况进行讨论 d
, 1c，| mc, t, t| T，mc 2m算法的思想如果 那么 为过期微 ? 对微簇 ? l c d CluStream ，借鉴算法 的思想把基于密度的数据流聚类算 ，。簇应当加以删除删除过期微簇仅仅消除了历史元组对当前
。, 1，3聚类结果的影响不会引人误差执行时间mc，| mc, t, t| ， T ，w? 对微簇 如果 但是权重 l c d e。 算法效率通过聚类执行时间来衡量本文通过统计算法 ，, ( t, t T) ,1+λc o dOnlineTSWDCS DenStream 与 的执行时间比来衡量本文算法 2 ( t，t) ，( t，t) = ，tt，ξ其中 ξ 是当前时间代表 c o c o c o , Tλd 2 ,1 。1 KDDCUP99 B400C20D40 效率的高低图 为处理 和 数据集
。c ，，，m孤立核心簇建立时间此时虽然有效但为孤立微簇所，，95% :10 0% ，的实验结果可以看出执行时间比为 说明两 。以也应当加以删除 ，OnlineTSWDCS 。者效率比较近但是 算法更高效些 6) 。将微簇的特征向量写入磁盘
: 按一定的时间跨度将在线过程的内存结果时间滑动窗
，，Clustream 口与微簇的特征向量写入磁盘并按 算法提出的 ,5,pyramid time frame。的策略组织这些结果这一过程的伪代 :码如下
if ( DS! = NULL) {
/ /，p数据流没有结束读取数据流中的每个数据点
InitTSlidingWindow( ) ; / 初始化时间滑动窗口/UpdateTSdngWndow( ) ;liii/ /更新时间滑动窗口 if ( r ) {? ε p
/ /p c，数据 添加到最近的候选核心簇 后其半径小于等于 ε p 图 1 执行时间比 把数据点 p 归入到 c; p }2 ，图 为执行时间随着数据流长度和维数变化比较从不 else if( r) {ε ? o ( a) 。2 同长度和不同维数上分别考查算法的效率从图 可看 / 数/据 p 添加到相邻的孤立维簇 c，其半径小于等于 ε o ，出执行时间随元组数量基本呈线性增长趋势说明算法效率 数据 p 归入到 c; o ; 2( b) 基本稳定从图 可看出执行时间随着维数呈线性增长的 f ( w βμ ) { I? o 。趋势 / / c 的权重大于 βμ o
c归入到候选核心簇; o }}
else{
p ;为 新建一个孤立维簇
}
}if ( t T= = 0) { %p
for( 每一个候选核心维簇 c) { p
f( w， ) iβμ p/ / 如果候选核心维簇权重小于 βμ
c; } 删除 p
For( 每一个孤立维簇 c) { o
if( w? ξ( t，t) )o c o
/ /如果孤立维簇的权重小于给定阈值
c; } 删除 o }
。保存当前时间滑动窗口内的维簇结构
实验验证 3
Intel T5870:，2 实验 环 境处 理 器主 频酷 睿 双 核
2, 00 GHz，2 GB 。Windows XP。内存操作系统为 算法是用
VC + + 。。实现的实验数据采用真实数据和人工数据集真实
KDDCUP99 ，数据集是 网络入侵检测流数据集这个数据集是 UCI ( http: / /kdd, ics, uci, edu / 从 的机器学习数 据 集 网 站 databases / kddcup99 / kddcup99, html) ，494 020 下载的共有条记 图 2 执行时间随着数据流长度和维数变化 Matab 。l录人工数据集是通过 软件生成的并满足一系列高 3, 2 内存的使用情况，: B、C、DT“”“”“”“”斯分布的数据采用如下标记命名和分
B T首先考虑时间滑动窗口中基本窗口 在不同的周期 、、别表示数据集中元组的个数自然簇的个数元组的维数和基 i: 。，本窗口的周期数实验中参数缺省设置如下初始化对象 ，3 中对数据流长度的影响如图 显示在取值不同的基本窗口 ntN = 1 000，v = 1 000，= 0, 25; R Ii=数据流速 衰减因子 λ 。KB，，350 下内存的使用情况结果显示内存的使用不超过
，，在数据流环境下数据曲线接近平滑也说明了不管数据流有 , 001，T = 5; Ts;16，= 10，= 0= 9 微簇删除周期 μ 误差度 β d，。多长此算法都能自我调节 。W = 5滑动窗口的长度
nternatona Conference on Data ngneerng, ashngton,IEEE IilEiiWi 4结语DC: IEEE, 2002: 685 , 694, AGGARWAL C, HART J,W ANG J, et a, A framework for custe- ll ,5,本文研究了时间滑动窗口内基于密度的数据流聚类问
ring evolving data streams , C , / / Pr oceedings of the 29th Interna- ，TSWDCluStream 。题提出了 算法该算法采用等时间跨度滑
tona Conference on Very arge Data Bases, Washngton, DC: illi，动窗口的思想较好地满足了考察特定时间周期内数据的应
。，，IEEE, 2003: 81 , 92, 用需求实验结果表明本文的算法是可行有效的能够满足
、。数据流环境对聚类算法的处理速度内存空间的要求 AGGARWAL C, HART J,W ANG J, eta l, A framework for projec- ,6,
ted clustering of high dimensional data streams, C, / / P roceedings of
the Thrteth nternatona Conference on Very arge Data iiIill
Bases,Ne w York: ACM Press,200 4: 852 , 863,
,7,CHERT Y, TU L, Density-based clustering for real-time stream data
,C, / / P roceedngs of the 13th ACM SGDD nternatona Confer- iIKIil
ence on Knowledge Discovery and Data Mining, New York: ACM
Press,200 7: 133 , 142,
,8,CAO F, ESTER M, QIALL W, et al, Density-based clustering over
an evolving data stream with noise ,C, / / Pr oceedings of the Sixth 3 ( T = 3，5，7)图 内存的使用情况 SIAM International Conference on Data Mining, Bethesda,M D,
:参考文献USA: ,s, n, ,, 2006,
,1,HAN J,KA MBER M, Data mining: Concepts and techniques,M,, ,9, ,, ,J,, , 2007, 34孙玉芬卢炎生流数据挖掘综述 计算机科学2nd ed, Morgan Kaufmann: Elsevier Inc, 2006: 467 , 589, ( 1) : 1 , 5, YANG Q, WU X, 10 Chaengng probems in data mnng research llilii ,2,,10,,,, ,J,, 常建龙曹锋周傲英基于滑动窗口的进化数据流聚类 软 ,J ,, nternatona Journa of nformaton Technoogy , D ecson IillIilii,2007,18( 4) : 905 , 918,件学报
Making, 2006,5( 4) : 597 , 604, , ZASLAVSKY A, SNS S, data,11, GABER M MKRIHAWAMYMining GAROFALAKS M, GEHRKE J,R ASTOG R, Queryng and mn- IIiistreams: a review ,J,, ACM SIGMOD Record, 2005, 34( 2) : 19 , ,3,
ng data streams You ony get one oo ,C, / / P roceedngs of 2002 i:llki21,
,12, LIN C H,CHIU D Y,WU Y H, et al, Mining frequent itemsets from ACM SGOD nternatona Conference on anagement of IMIilM
data streams with a time-sensitive sliding window ,EB / OL,, ,2010 Data,Ne w York: ACM Press,2002: 635 , 635,
O'CALLAGLMA L, MISHRA N, MEYCRSON A, eta l, Streaming- , 07 ,10 ,, http: / c/iteseerx, ist, psu, edu / viewdoc / summary, doi ,4,
= 10, 1, 1, 104, 7216, data agorthms for hgh quaty custerng ,C, / / Pr oceedngs of liililii
( )1350 上接第 页
，Gass ，l别数据集的类别个数较大如 数据集则需要小支持度 A, COWLING P I, A greedy classification algorithmTHABTAH F ,4,
。，阈值才能获得高的分类精度对置信度阈值来说提高置信 based on assocaton rue , J ,, pped Soft Computng, 2007, 7 iilAlii
，度阈值并不能提高分类器的精度反而过大的支持度会降低 ( 3) : 1102 , 1111,
，分类精度所以在下一步工作中需要研究支持度和置信度的 ZHU X Y, SONG Q B, JIA Z H, A weighted voting-based associa- ,5,。选取方法以取得更好的分类效果 tive classification algorithm ,J,, Computer Journal, 2010, 53 ( 6 ) :
786 , 801,
,6,CERF L, GAY D, SELMAOU N, eta , A parameter-free ssaoca- Ili 4结语 tive classification method ,C, / / P roceedings of the 10th Internation- SVM ，本文给出一种结合分类关联规则和 的分类框架提 Conference on Data Warehousing and Knowledge Discovery, Ber- al 。FCM 高了分类的效率和精度该算法采用 聚类算法离散化 lin: Sprnger, 2008: 293 , 304, i，byte-vector 连续属性数据基于 结构高效地提取模糊分类关 ,7,PEDRYEZ W, Fuzzy sets technology in knowledge discovery ，，联规则并定义了合理的评分策略对规则进行加权构造基于 ,J,,F uzzy Sets and Systems,19989,8 ( 3) : 279 , 290, SVM ，兼容性的特征向量作为 的输入得到的分类器模型经过 ,8,CONG GAO, TAN K L, TUNG A K H,et al, Mining top-k covering 。，实验验证表明该算法是有效的进一步要研究的问题是面 rule groups for gene expression data , C , / / Pr oceedings of 2005 ，SVM ，对大型数据集需要对 算法进行改进以及对核函数的 ACM SIGMOD International Conference on Management of 。选取进一步研究 Data,Ne w York: ACM Press,200 5: 670 , 681, :参考文献 ,9,CHANG C C, C J, LBS A brary for support vectorm aLIN IVM:li-
chne ( 2001) ,EB / OL,, ,2010 , 05 , 10,, http / /i: ,1,BARALIS, GARZA P,A lazy approach to pruning classificationwww, cse, ntu,e du, tw / :cj n / papers / bsvm, pdf, ilili rules ,C, / / P roceedings of IEEE 2002 International Conference on LIU BING, HSU W, MA YIMING, Integrating classification and as-,10, Data Mining, Washington, DC: IEEE Press,200 2: 35 , 42, socaton rue mnng ,C, / / P roceedngs of the Fourth nternatonaiiliiiIil X, HAN J, CPAR: Cassfcaton based on predctve assoca- YIN liiiiii ,2,Conference on Knowledge Discovery and Data Mining, Washington, tion rules , EB / OL ,, ,2010 ,05 ,10 ,, http: / /www, siam, org / DC: IEEE, 1998: 80 , 86,
proceedngs / datamnng /2003 / dm0340nX, pdf, iii_Yi,11, LI WENMIN, HAN JIAWEI, PEI JIAN, CMAR: Accurate and effi- WANG J, KARPS G, HARMONY: Effcenty mnng the best YIiilii cient classification based on multiple class association rule , C , / / ,3 ,
rules for classification ,EB / OL,, ,2010 , 05 ,10 ,, http: / /Proceedings of 2001 IEEE International Conference on Data www,si am, org / proceedings / datamining /2005 / dm05_19wangj, pdf, Mnng, ashngton, DC: EEE, 2001: 369 , 376, iiWiI
范文五：基于时间滑动窗口的自适应加权抽样算法 精灵论文
基于时间滑动窗口的自适应加权抽样算法
刘畅，唐达
(大连理工大学计算机科学与技术学院，辽宁 大连 116023) 摘要:为了构
建传感器网络流数据的概要数据，总结和分析构建概要数据的几种抽样方法， 给出一种基于
时间滑动窗口的自适应加权随机抽样算法:AWRS/BTSW 算法。该算法根据流数 据变化的快慢
程度，动态的对流数据加权，将权值和数据到达时间做为数据项的键值，根据 键值大小对流
数据进行抽样，解决了现有的抽样算法生成的概要数据与原始数据偏离大小不 确定以及数据
过期问题。并将该算法应用到深海平台监测系统中，与其他抽样算法相比，该 算法在数据变
化稳定的情况下，能快速的生成概要数据，当监测到数据变化剧烈时，动态改 变抽样方式，
抽取的概要数据精确性高。
关键词:流数据;概要数据;自适应;AWRS/BTSW 算法;时间滑动窗口
中图分类号:TP302.1
Adaptive weighted sampling algorithm based on time sliding
window
Liu Chang, Tang Da
(Computer Science and Technology School, Dalian University of Technology,
LiaoNing DaLian 116023)
Abstract: To obtain the synopsis data of the data stream from the sensor networks, this paper summarizes and analyzes several sampling methods of building synopsis data, and provides an adaptive weighted random sampling algorithm based on time sliding window: AWRS/BTSW algorithm. A weight is assigned to data item dynamically acording to the change of data stream, and a key is assigned for each data item by compromising its weight and arrival time, then sample with the key. This algorithm solves the problems of uncertain deviation between the original data and the sample data and the expiration of data. Finally, this algorithm is applied to Deep Sea Platform Monitoring System. Compared with other sampling algorithms, this method can produce synopsis data quickly when the data is stable,and change the sampling method dynamically when the data changes rapidly to decrease relative errors.
Keywords:data stream; synopsis data; adaptive; AWRS/BTSW algorithm; time sliding window
0 引言
深海平台监测系统主要由数据采集、数据分析、数据处理及评价体系四部分组成，从传
感器网络上进行数据采集是系统最重要的部分。传感器网络上的应用对数据的管理与分析提
[1] 出了新的要求，例如可以处理连续查询，快速响应用户查询等要求，其本质是对流数据
进行管理和分析。流数据是连续的、无界和随时间变化的。数据流上的查询通常是连续运行
的，当新数据到达时增量式地返回结果，即长时间运行的、连续的、持久的查询。流数据的
特点决定了其分析技术通常只能是一次处理,其算法应是单遍扫描(one-pass)。由于存储容量
的有限性,不可能完整地保存全部流数据元素。在深海平台监测系统中,用户并不需要获得精
确的查询值,仅仅需要一个近似结果即可。考虑设计一个远小于原数据流规模的结构,保存已
流过数据的概要特征,方便数据流的查询及分析。因此,概要数据结构(synopsis data
[2] structure)的设计成为数据流技术的热点研究问题之一。
基金项目:国家科技重大专项课题子课题(No. 2008ZX05026)
作者简介:刘畅(1986-)，男，硕士研究生，主要研究方向:数据流管理系统. E-mail: tigerdlut@163.com
1 概要数据构建技术
[3,4][5]常用的概要数据构建技术包括抽样技术(sampling)、直方图技术(histogram)和小波技
[6]术(wavelet)。直方图技术只能反应数据的分布特征，有些需要多次扫描数据集,不适合于数 据流的查询，小波技术相对复杂，抽样方法是从数据集中抽取小部分数据代表整个数据集， 并根据该样本集合获得查询结果。深海平台监测系统实时性高，且需要对历史数据进行查询， 因此，抽样技术适合该系统。目前主要存在三种不同的抽样算法及其研究现状:
均匀抽样(uniform sampling):数据集中各元素以相同的概率被选取到样本集合中。
[3]Vitter提出水库抽样方法，令样本集合的容量为S ，在任一时刻n, 数据流中的元素都以S/n 的概率被选取到样本集合中去。如果样本集合大小超出 S，则从中随机去除一个样本。可以
[4]ons 等人提出精确抽样方法，对于仅出现一次的元素， 证明，各元素的入选几率相同。Gibb
类似于水库抽样，仍然用元素代码表示;而对于多次出现的元素，则利用结构〈value, count〉 表示，精确抽样方法比水库抽样方法更节约空间。
[4]偏倚抽样(biased sampling):不同元素的入选几率可能不同。Gibbons 等人提出计数抽 样方法，该算法是精确抽样方法的一个变种，区别在于样本集合溢出时处理方式不同，能有 效地获得数据集中的热门元素列表。
[7]综合抽样:将均匀抽样和偏倚抽样结合起来。Efraimidis等人认为均匀抽样以相同的概 率对数据流中到达的数据元组进行随机抽样，没有考虑数据元组可能有不同重要性的情况。 该文献改进了水库抽样算法，给出了加权抽样(Weighted Random Sampling)算法。ZHANG
[8]Longbo等人通过改进加权抽样算法,结合基本窗口技术，提出优先数随机抽样算法(PRS), 根据数据的权值和到达时间，计算其优先数，并根据优先数的大小决定其是否进入样本集以
[9]及样本集中被替换的数据元组，算法能够有效地处理过期数据元组问题。HOU Wei等人在 周期抽样的基础上提出一种针对多个相关数据流的概要数据生成算法，该算法在某种程度上 能够防止多个数据流之间的多次连接操作，提高了抽样的效率。
上述算法没有考虑流数据的变化特点，其中加权抽样算法能根据数据重要性进行抽样， 但需要用户赋予数据一定的权值。在深海平台监测系统中，用户并不知道什么时候到来的数 据重要，也就无法给这些数据赋予准确的权值，因此，抽取的概要数据与原始数据偏离大小 不确定。本文给出一种基于时间滑动窗口的自适应加权随机抽样算法:AWRS/BTSW
(Adaptive Weighted Random Sampling Based on Time Sliding Window)算法，该算法根据时间序列数据流在不同时刻变化快慢程度，动态对流数据进行抽样，解决了现有抽样算法抽样 的概要数据与原始数据偏离不确定以及数据过期问题。从流数据变化特点出发，定义了平均 数据变化率，skipping 因子等相关概念，根据流数据的平均变化率赋予数据项相应的权值， 结合基本窗口技术，综合考虑权值和时间因素并将其做为数据项的键值，在抽样时，根据 skipping 因子的值决定是否跳跃若干数据项，根据键值大小决定是否将对应的数据项选入样 本集或从样本集中替换掉。
2 AWRS/BTSW 算法
由于时间序列数据流在不同时刻取值的变化剧烈程度不一致，定义数据变化率来描述数 据的变化。在时刻 i 的数据定义为t.x 。数据变化率+i 定义为 ，t.x t.x)/ t.x，。则在+t i i i 1i 1
+t
。) /+t 的时间跨度周期里的数据的平均变化率为+i , ( + i i , 1
引入 skipping 因子记录数据流中数据值变化的特征，skipping 因子是基于平均数据变化 率的函数，其基本思想是，数据流值变化越慢，跳跃的元组个数越多。 skipping (+t) 定义如 下:
, true if (+i , ,) , skipping (+t ) ,
false if (+i , ,) ,, ;
其中 , 取经验值。
以数据流 S 上基于时间的连续更新滑动窗口为例描述 AWRS/BTSW 算法，假设当前滑 动窗口的时间跨度为 T，后面叙述用到的其他一些符号如表 1 所示。
表1 符号表
Tab. 1 notation table
符号 定义
S[0], S[1],...S[k 1] 基本滑动窗口
当前滑动窗口数据项的数目 w, n 当前滑动窗口需要处理的数据项
数据流的数据项 该函数从(x,y)v i生成均匀随机变量 数据项 生成的random( x, y) 随机数 i u iv 数据项 的键值v i x i 数据项 的权值v i w, 0 i 数据项 到达的时间v i t i
MIN 当前滑动窗口最小的键值y f (x, y) 对于变量 x,y， 是一个单调递增函数，例如 . x f (x, y)
g ( x) 单调递增函数
w( x) 单调递增函数
当时间跨度的数据到达时，通过计算它的平均数据变化率来衡量数据流的变化剧 +t +i
烈程度，根据 skipping 因子的值决定是否跳跃+t 时间跨度的数据项。其基本思想是，若数
据平均变化率不超过给定值，则滑过这些元组。若数据平均变化率超过给定值，则给这段数据项赋予相应的权值，数据变化越快，赋予的权值就越大。权值计算公式如下:
1 ，(1) (， , 0) w , w( +i ),+i +t
为解决时间滑动窗口的数据过期问题，将数据的到达时间和权值作为数据项的键值。键 值计算公式如下:
(2)x , ，g (t ) ， ,f (w , , )i i i i
其中 ， 和 , 是权衡数据到达时间和权值的两个参数， , , random(0,1) 。当时间窗口 i
向前滑动时，当前滑动窗口的数据项的键值周期性的计算，可以将滑动窗口分为 K 个基本 窗口( s[0], s[1], ..., s[k 1] )。假设 v在基本窗口 s[m] ，则当前滑动窗口的数据项的键值 x可 i i
以计算如下:
(3) x , ，g(k m) ，,f (w , , )i i i
假定l 是一个正整数，则公式可以转化如下:
1 1 w2l +t (4)x , ，，k m ， ,，， ,, i i
代入公式(1)可得:
1
1 1 ， +il 2 x , ，， k m ， ,，， ,, (5)i i
新到来的+t 时间段的数据，将 m = k 代入公式(5)计算可得: 1
1
，
+i x , ， ， ,, (6)i i
AWRS/BTSW 算法具体如下:
输入:数据流 S，T
输出:基于时间的滑动窗口 W 的概要数据集 R
1.将时间戳 0 到 T 的 个数据项加入到滑动窗口中;w
2.将当前滑动窗口分为 K 个基本窗口(s[0],s[1],…s[k-1])， ;K , T /+t
3.计算每个基本窗口的平均数据变化率及权值;+i w i
4.计算每个基本窗口的键值 x; i
5.Fori , w ， 1, w ， 2, ...n ,重复步骤 5-12;
6.计算下一个时间跨度数据平均变化率;+t +i
7.IF skipping (+t ) ,, true ，跳跃+t 个时间跨度段，goto 第 5 步;
8.将+t 时间跨度的数据项读取到 s[k];
9.查找当前滑动窗口中键值最小的基本窗口，假设最小键值为 MIN;
10.计算+t 时间跨度的键值 x; i
11. IF x, MIN , i
将+t 时间跨度数据项增加到滑动窗口中;
删除最小键值的基本窗口;
12.窗口向前滑动， s[i] s[i 1] ;(i=1,2,…,k)
3 相关算法比较
[8] 目前面向带权值数据流上的随机抽样算法中，ZHANG Longbo 等人提出了 PRS 算法， 它在 WRS 算法的基础上进行了改进，该算法相对 WRS 算法提高了效率和精确度。但该算 法随机生成权值，并根据权值大小进行抽样，因此，生成的概要数据与原始数据偏离大小不 确定。本文给出的 AWRS/BTSW 算法能自动监测流数据变化的快慢程度，动态改变抽样的 方式，在实际的应用中，生成的概要数据精确度比 PRS 算法高，效率也得到提升。
一个数据集中，稳定数据所占的比重定义为数据的稳定度。在仿真实验中对 PRS 算法, AWRS/BTSW 算法所用时间，准确性进行了比较。测试环境为:操作系统 Windows XP,
Dual-Core CPU:2.6GHz Pentium 4 PC,内存 1G。分别使用五种数据集 D1,D2,D3,D4,D5,其中 D1 的稳定度为 0，D2 的稳定度为 25%，D3 的稳定度为 50%，D4 的稳定度为 75%，D5 的 稳定度为 100%。在 PRS 算法中用 random(0,10)分别为每个数据元组生成一个随机数作为其 权值,然后分别在每个数据集上运行两种算法,最后求其算术平均值。在每次实验过程中数据 总量为 3 万，抽取的样本的数量为 5000，并使用固定的数据流速， , 取 0.0001。最后实验 结果如图 1 和图 2 所示。
900 800PRS 700AWRS/BTSW 600 500 400 300 200 100 00 25 50 75 100
stability/%
图 1 算法所用时间的比较
Fig. 1 Comparison of efficiency
8PRS
6 AWRS/BTSW
4
error/%2
0
0 25 50 75 100
stability/%
图 2 算法相对误差的比较
Fig. 2 Comparison of accuracy
数据变化稳定时，与 PRS 算法相比，AWRS/BTSW 算法能较快的生成概要数据，当监 测到数据变化剧烈的时候，该算法能动态改变抽样的方式，生成概要数据的准确性比 PRS 算法高。而在深海平台监测系统等实际应用中，剧烈变化的数据的准确性对数据分析很重要。 因此，该算法能很好的用在深海平台监测系统等实际应用中。
4 结论
本文总结和分析构建概要数据的几种抽样方法，给出一种基于时间滑动窗口的自适应加 权随机抽样算法:AWRS/BTSW 算法。该算法解决了现有抽样算法生成的概要数据与原始 数据偏离大小不确定以及数据过期问题，提高了准确性。在深海平台监测系统等实际的应用 中，流数据变化时而缓慢，时而剧烈，该算法能根据这种变化特点动态的对数据进行抽样， 与其他抽样算法相比，该算法效率高，相对误差小。在实验过程中，若数据一直处于剧烈变 化状态时，该算法优势不太明显，今后将进一步对这类数据的概要数据的构建进行研究。
5 致谢
感谢在写论文过程中导师的耐心辅导，我在整个写作过程中收获很多，也感谢实验室的
同学们，在我写论文的过程中给过我很多帮助，同时也感谢已经毕业的师兄，在论文格式的
修改过程中和投稿过程中给我很大的帮助。
[参考文献]
[1] BABCOCK B, BABU S, DATAR M, et al. Models and issues in data streams [A].Proceedings of the twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems [C].New York: ACM, 2002.1~16.
[2] GIBBONS P B, MATIAS Y. Synopsis data structures for massive data sets [J].Dimacs Series in Discrete Mathematics and Theoretical Computer Science, 1999:39~70.
[3] VITTER J S. Random sampling with a reservoir [J].ACM Trans on Mathematical Software, 1985, 11(1): 37~57.
[4] GIBBONS P B, MATIAS Y. New sampling-based summary statistics for improving approximate query answers [A].Proceedings of the 1998 ACM SIGMOD international conference on Management of data[C]. New York: ACM, 1998.331~342.
[5] GIBBONS P B, MATIAS Y, POOSALA V. Fast incremental maintenance of approximate histograms [J]. ACM Transactions on Database Systems, 2002, 27(3): 261~298.
[6] MATIAS Y, VITTER J S, WANG M. Wavelet-based histograms for selectivity estimation [J].ACM SIGMOD Record, 1998, 27(2):448~459.
[7] EFRAIMIDIS P S , SPIRAKIS P G. Weighted random sampling with a reservoir [J].Information Processing Letters, 2006, 97(5):181~185.
[8]ZHANG L B, LI Z H, ZHAO Y Q, et al. A priority random sampling algorithm for time-based sliding windows over weighted streaming data[A].Proceedings of the 2007 ACM symposium on Applied computing[C]. New York: ACM, 2007.453 ~456.
[9]HOU W, YANG B, WU C S, et al. RedTrees: A relational decision tree algorithm in streams [J].Expert Systems with Applications, 2010, 37(9):6265~6269.
