（计算机应用技术专业论文）ad+hoc网络mac层自私行为检测机制研究.pdf

中文摘要 在a dh o c 网络中，随着网络设备可编程能力的提高，自私用户为了获得更 高的吞吐量、更低的延迟或更少的能耗，他们可能蓄意篡改网络协议。相对于网 络层次模型中的其它各层而言，m a c ( m e d i u m a c c e s sc o n t r 0 1 ) 层协议的篡改将使 得自私用户更容易获得更高的“收益”。因此，研究a dh o c 网络m a c 层自私行 为检测机制是很有必要的。 s w n c u s u m ( s l i d i n gw i n d o wn o n - p a r a m e t e rc u m u l a t i v es u m ) 算法是一种 基于统计的m a c 层自私行为检测算法，它能够快速地判断a dh o c 网络中是否 存在自私节点，但是它无法明确指出哪个节点是自私节点。针对s w n c u s u m 算法存在的这一问题，本文提出了一个改进方法。改进后的s w n c u s u m 算法 具有广泛的适用性，它可以实时地检测出多种引起m a c 层接入延迟发生变化的 m a c 层自私行为。仿真结果表明，改进后的s w n c u s u m 算法具有较低的检 测延迟和较高的检测准确性。 本文还提出了一种基于免疫原理的m a c 层自私行为检测系统s d s i ( t h e s e l f i s hb e h a v i o rd e t e c t i o ns y s t e mb a s e do ni m m u n et h e o r y ) 。s d s i 是一种基于规则 的检测系统，它由四个模块组成：预处理模块、先天性检测模块、获得性检测模 块和处理模块。预处理模块负责对m a c 层接入延迟进行预处理，先天性检测模 块和获得性检测模块负责网络异常的检测，处理模块对异常情况进行综合处理。 根据抗体匹配抗原的思想，s d s i 利用检测规则来匹配m a c 层自私行为。其中， s d s i 通过连续r 位匹配算法来判断m a c 层自私行为是否与检测规则匹配。为 了保持检测规则的多样性和优越性，s d s i 定期对检测规则进行变异操作。仿真 结果表明，不管是单跳还是多跳、单节点自私还是多节点自私，s d s i 都能够准 确、及时地检测出m a c 层自私行为。 关键词：a dh o c 网络，i e e e8 0 2 1 1d c f ，自私行为，检测，c u s u m ，免疫原 理 a b s t r a c t t h ed e v e l o p m e n to fp r o g r a m m a b l en e t w o r ke q u i p m e n t sp r o v i d e sc o n v e n i e n tf o r s e l f i s hu s e r si na dh o cn e t w o r k st ot a k ea d v a n t a g e s ( e g h i g h e rt h r o u g h p u t ，l e s s d e l a yo rl o w e re n e r g yc o n s u m p t i o n ) o fo t h e ru s e r sb yd e l i b e r a t e l yt a m p e rn e t w o r k p r o t o c o l s e s p e c i a l l yi nm e d i u ma c c e s sc o n t r o l ( m a c ) l a y e r , s e l f i s hu s e r sc a no b t a i n m o r ep r o f i t s t h e r e f o r e ，i ti sn e c e s s a r yt os t u d ym a cl a y e rs e l f i s hb e h a v i o rd e t e c t i o n m e c h a n i s m s s l i d i n gw i n d o wn o n - p a r a m e t e rc u m u l a t i v es u m ( s w n - c u s u m ) i sas t a t i s t i c a l d e t e c t i o na l g o r i t h mo fm a cl a y e rs e l f i s hb e h a v i o r , w h i c hm a yq u i c k l yd i s c o v e rt h e s e l f i s hb e h a v i o r si na dh o cn e t w o r k s h o w e v e r , i tc a nn o tl o c a t et h es e l f i s hn o d e s i n t h i st h e s i s ，w ep r o p o s e das e l f i s hn o d ed e t e c t i o nm e t h o dt oo v e r c o m et h ew e a k n e s so f s w n - c u s u m t h ei m p r o v e ds w n - c u s u mc a ne f f e c t i v e l ya n dr a p i d l yl o c a t et h e s e l f i s hn o d e s ，a n dc a nb ei m p l e m e n t e di nan u m b e ro fs c e n a r i o s t h es i m u l a t i o n r e s u l t ss h o wt h a tt h ei m p r o v e ds w n c u s u mh a sl o wd e t e c t i o nd e l a ya n dh i g h d e t e c t i o na c c u r a c y m o r e o v e r , w ep r o p o s ear u l e - b a s e ds e l f i s hb e h a v i o rd e t e c t i o ns y s t e m ，n a m e dt h e s e l f i s hb e h a v i o rd e t e c t i o ns y s t e mb a s e do ni m m u n et h e o r y ( s d s i ) s d s ic o n s i s t so f f o u ri n d e p e n d e n tm o d u l e s p r e - p r o c e s s i n gm o d u l e ，i n n a t ed e t e c t i o nm o d u l e ，a c q u i r e d d e t e c t i o nm o d u l ea n dp r o c e s s i n gm o d u l e i ns d s i ，t h em a cl a y e ra c c e s sd e l a yi s c a l c u l a t e da n dc o d e db yp r e - p r o c e s s i n gm o d u l e ，a n dt h e nt h ed e l a yi sa n a l y z e da n d c o m p a r e db yi n n a t ed e t e c t i o nm o d u l ea n da c q u i r e dd e t e c t i o nm o d u l ef o ra b n o r m a l b e h a v i o r s a l lu n u s u a lc i r c u m s t a n c e sa r ep r o c e s s e db yt h ep r o c e s s i n gm o d u l e s i m i l a r t ot h ea n t i b o d y a n t i g e nt h e o r y , s d s ie m p l o y sc o n t i n u o u sr - b i t m a t c h i n ga l g o r i t h mt o m a t c hm a cl a y e rs e l f i s hb e h a v i o r sw i t hd e t e c t i o nr u l e s f u r t h e r m o r e ，t h ed e t e c t i o n r u l e sm u t a t ep e r i o d i c a l l yt om a i n t a i nt h ed i v e r s i t ya n ds u p e r i o r i t y t h es i m u l a t i o n r e s u l t ss h o wt h a ts d s ic a na c c u r a t e l ya n dq u i c k l yd e t e c tt h em a cl a y e rs e l f i s h b e h a v i o r s k e yw o r d s ：a dh o cn e t w o r k s ，i e e e8 0 2 11d c f , s e l f i s hb e h a v i o r , d e t e c t i o n ， c u s u m ，i m m u n et h e o r y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丕鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：对移黻签字同期：佣罗 年夕月同 学位论文版权使用授权书 本学位论文作者完全了解墨壅盘堂有关保斟、使用学位论文的规定。 特授权叁鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：苹器斌 签字曰期：矽年多月伺 导师签名：锯关忝 签字同期：伊歹年多月沙日 第一章绪论 1 1a dh o c 网络概述 第一章绪论 a dh o c 网络【】是一种多跳的无线网络，它不需要现有基础设施和基站的支 持，可以随时随地快速地组建，因此a dh o c 网络被广泛地应用于战场、灾难恢 复等领域。随着无线移动通信和移动终端技术的快速发展，a dh o c 网络在民用 领域的应用也越来越多。 与传统网络相比，a dh o c 网络具有很多不同之处，主要体现在： 1 在a dh o c 网络中，所有节点1 地位平等，节点之间以对等的方式进行通信， 没有集中的控制中心。 2 在a dh o c 网络中，主机能量有限，且受地形等环境因素的影响，使得单个 节点的通信覆盖范围有限，所以如果某个节点想要和自己通信范围以外的节 点进行通信，就需要通过网络中其它节点的转发来完成，因此又将a dh o c 网络称为多跳网络。 3 在a dh o c 网络中，节点可以任意移动，网络拓扑结构动态变化。 4 a dh o c 网络采用无线信道进行通信，而无线信道具有天然的广播特性，因 此在a dh o c 网络中，某一节点的数据传输将影响其传输范围内的其它节点。 1 2i e e e8 0 2 1 1d c f 机制 i e e e8 0 2 1 1 规科5 ，6 】是一个无线局域网标准，它定义了主机( c l i e n t ) 和基站 ( b a s es t a t i o n ) 或a p 之间以及主机与主机之间的无线通信规范。i e e e8 0 2 1 1 标准 中定义了p c f ( p o i n tc o o r d i n a t i o nf u n c t i o n ) 和d c f ( d i s t r i b u t e dc o o r d i n a t i o n f u n c t i o n ) 两种网络架构模式。p c f 是一个集中控制模式，顾名思义，p c f 网络一 般存在一个集中控制中心，它主要用于控制整个网络的通信。而d c f 是一种分 布式协调模式，它支持无线主机之间的直接通信，无需控制协调中心的介入。虽 然i e e e8 0 2 1 1d c f 最初是为无线局域网( w i r e l e s sl a n ，w e a n ) 设计的，然而目 本文对节点、站点和主机不加以区别。 第一章绪论 前绝大多数a dh o c 网络都把i e e e8 0 2 1 1d c f 作为底层的通信协议。 通过使用载波侦听多路访问冲突避免( c a r r i e rs e n s em u l t i p l ea c c e s sw i t h c o l l i s i o na v o i d a n c e ，c s m a c a ) 和随机退避( r a n d o mb a c k o f t ) 机制，i e e e8 0 2 1 1 d c f 允许节点之间自动协调媒介的共享。除此之外，所有数据传输都使用a c k 确认( m a c l e v e la c k n o w l e d g m e n t s ) 机制，如果发送节点没有收到a c k ，发送节 点将进行重传直到数据成功传输或重传次数达到阈值限制。 1 2 1 载波侦听 d c f 提供了两种载波侦听方式：物理载波侦听和虚拟载波侦听。这两种载 波侦听方式都是用来估计信道忙闲状态的。无论哪种方式指示信道忙，d c f 就 认为信道处于忙状态；否则d c f 认为信道处于空闲状态。 物理载波侦听方式由物理层提供。它根据接收信号的强弱或质量来估计信道 的忙闲状态。 虚拟载波侦听方式由m a c ( m e d i u ma c c e s sc o n t r 0 1 ) 层提供。该机制通过网 络分配矢量( n e t w o r k a l l o c a t i o nv e c t o r , n a v ) 实现。n a v 基于m a c 帧中的持续时 间标识码( d u r a t i o n i d ) 字段来实现对信道使用情况的预测。如果某个站点检测到 正在传输的m a c 帧的持续时间标识码字段大于自己的n a v ，该站点就用这个 持续时间标识码字段的值更新自己的n a v ；否则n a v 不变。 n a v 可以被认为是一个计数器，n a v 以一个统一的速率递减，直到递减为 0 。当n a v 为0 时，虚拟载波侦听方式指示信道空闲：否则指示信道忙。无论站 点是否正在传送数据，只要n a v 为非零，虚拟载波侦听就认为信道忙。 1 2 2 随机退避机制 节点在发送数据之前必须先监听信道，如果信道空闲且空闲时间达到d i f s ， 节点才可以使用信道；否则延迟接入信道，直到再次检测到信道空闲时间达到 d i f s ，然后随机选择一个退避时间进入退避阶段，退避阶段结束后如果信道仍 然空闲，节点才可以使用信道。 随机退避时间是通过下式 5 1 产生的： b a c k o f f t i m e = r a n d o m ( 、木a s l o t t i m e 其中r a n d o m ( ) 是- - 个随机函数，它返回一个 0 ，c w 之间的随机整数。c w ( c o n t e n t i o nw i n d o w , 竞争窗口) 是 c w m i n ，c w m a x 之间的一个整数，c w m i n 和 c w m a x 与物理层相关。a s l o t t i m e 也是一个与物理层特性相关的值。 第一章绪论 c w 初始值为c w m i n 。如果节点传输数据失败，c w 将选择序列( 图1 - i 给 出了一个c w 序列) 中的下一个值直到c w 增加为c w m a x 。一旦节点成功传输 数据，c w 将重置为c w m i n 。 wm a x 1 2 7 6 3 3 1 m i n z 产一 1 2 3d c f 数据传输方式 il lt h 州r e t r a n s m l s s i o n l ls e c o n dr e t r a n s m i s s l o n l l f i r s tr e t r a n s m i s s i o n li n i t i a ia t t e m p t 图1 1 p 】c w 序列示例 d c f 提供了两种数据传输方式： 1 基本数据传输方式( 见图1 2 ) 。 s o u r c e d a t a + s 礤s + d s + d e s t i m a t i o n a c k g m e r 脚锄i o n 嗍 r d e f e r a c c e s s b a c k o f f a f t e rd e f e r 图1 - 2d c f 基本数据传输方式 第一章绪论 2 r t s c t s 数据传输方式( 见图1 - 3 ) 。 圆k 刊 e j 降i冈 j h l s i f s _ i a t i o n s i f s c t - - 石 n i f 宜 ? i ， n a v ( r t s )| c j o n t e n t i o nw i n d o w j n a v ( c t s ) r d e f j i b ra c o e s sb a c k o f fa 船rd e f e r 图1 3 t 5 1d c fr t s c t s 数据传输方式 这两种数据传输方式的区别在于，r t s c t s ( r e q u e s tt os e n d c l e a r t os e n d ) 数据传输方式在发送实际的数据帧之前要发送r t s c t s 短帧进行信道预留。 r t s c t s 短帧的使用可以有效地避免实际数据帧碰撞的发生，能够有效的提高 信道利用率。并且由于r t s c t s 帧非常短，所以r t s c t s 的传输开销很小。虽 然r t s c t s 的使用有很明显的优势，但是在实际应用中r t s c t s 帧的传输终归 会引起一部分延迟，所以r t s c t s 在实际中的应用并不多见。 1 3m a c 层自私行为 自私行为( s e l f i s hb e h a v i o r ) 是指一个节点蓄意地更改或误用网络协议，以牺 牲其它节点来增加自己的利益，具体体现在最大化自己的带宽，最小化自身的延 迟等等。本文将采取自私行为的节点称为自私节点( s e l f i s hn o d e ) 或自私用户 ( s e l f i s h u s e r ) 。在本文以后的论述中，在不会引起歧义的情况下，对自私行为、 自私节点、自私用户将不加以区别。 1 3 1m a c 层自私行为产生的原因 随着网络设备可编程能力的提高，用户为了获得更高吞吐量、更低延迟或更 少能耗，他们不惜蓄意篡改网络协议。相对于网络层次模型中的其它各层而言， m a c 层协议的篡改将使自私用户获得更高的“收益”。这主要体现在以下几个方 面： 1 效果比在上层自私显著，因为m a c 层直接和媒介打交道，m a c 层协议的篡 第一章绪论 改能够直接影响节点的信道接入，从而能够更加快速地改变节点的吞吐量和延 迟。 2 因为上层的机制检测不到m a c 层的改变，所以自私节点可以结合其它上层 的自私行为来强化自私的效果。 3 相对于上层协议而言，a dh o c 网络m a c 层协议数量少、种类单一，基本上 只要修改i e e e8 0 2 1 1d c f 协议，就能在很多情况下发挥作用。 1 3 2m a c 层自私行为策略 文献 7 】对m a c 层自私行为策略进行了一个总结，文中提到目前主要的m a c 层自私行为策略有： 1 选择性地干扰其它节点发送的m a c 帧，以达到增加其它节点m a c 层竞争窗 口大小的效果，即间接地减小了自己的m a c 层接入延迟1 。干扰的帧类型可 以是： a ) c t s 帧。在这种情况下，自私节点侦听到不是发送给自己的r t s 帧时， 故意发送无用m a c 帧来干扰c t s 帧的传输，这样，接下来的d a t a 帧 将不会发送，信道变为空闲，发送r t s 帧的节点竞争窗口将加倍，自私 节点的信道接入概率得以提高。 b ) a c k 或d a t a 帧。虽然对a c k 帧和d a t a 帧的干扰并没有减少d a t a 帧的传输时间，但是它导致了发送节点竞争窗口的加倍，也即间接提高 了自私节点访问信道的概率。 2 修改协议参数以降低m a c 层接入延迟： a ) 信道空闲时，自私节点在d i f s ( d c fi n t e r f r a m es p a c e ) 之前，s i f s ( s h o r t i n t e r f r a m es p a c e ) 之后传输数据包。正常情况下，节点应该在信道空闲时 间达到d i f s 时才能传输数据包，但自私节点为了降低延迟，在信道空 闲时间还不到d i f s 就发送数据包。 b ) 夸大n a v 。当发送r t s 和数据帧时，自私节点故意增大n a v 的值，防 止其它用户竞争信道。 c ) 更改退避时间( b a c k o f ft i m e ) 。自私节点为了减小延迟故意在较小的竞争 窗口中选择退避时间，甚至固定竞争窗口( 即不进行二进制指数退避) 。 在上面介绍的几种自私行为策略中，更改退避时间是最难被检测的，因为在 1 在本文中，m a c 层接入延迟定义为两次成功发送r t s ( 使用r t s c t s ) 或实际数据包( 不使用r t s c t s ) 之间的信道空闲时间。 第章绪论 i e e e8 0 2 1 1d c f 中，退避刚问是一个伪随机数，所以即使能够获得别的节点的 退避时间，也根难判断该退避时问是否被篡改过。田此本文的研究主要针对这 自私行为策略，但是文中得出的结论同样适用于其它自私行为策略只要该自私 行为策略会引起节点m a c 层接入延迟的变化。 1 33m a c 层自私行为对整个网络的影响 文献 8 】对c s m a c a 网络中自私节点的数量、竞争窗口的大小以及节点吞 吐量之间的关系进行了研究。研究结果表明当阿络中存在单个自私节点时，自私 节点的吞吐量随着竞争窗口的增大mf 降，面正常节点的备n l 量随着自私节点竞 争窗口的增大而升高。但是j l 要存在单个自私节点，正常节点的吞吐量就比小存 在自私节点时的吞吐量要低，而自私节点的吞u t 量比止常情况要高( r 图直观地 说明了这一结粜) 。 0二 1c 1 二觚2 5 3 ( _ ( 一。1 f d 、f wn7 】0 * f v iot _ 1 自a l 图1 8 1 单节点自私的情况下竞争窗口与吞吐量的关系 气网络中存在多个自私节点时，自私节点的春吐量随着竞争窗口的增大先升 高后降低。而正常节点的吞吐量随着自私节点竞争窗口的增大而升高。自私节点 的吞吐量这样变化的原闻是自私节点选择的竞争葡口较小时，多个自私节点之间 的碰撞概率较大，这时碰撞概率成为影响吞吐量的 要嘲素所以尽管竞争窗口 小，但是吞吐量并没有提高而随着竞争窗口的增大，碰撞逐渐减少，吞叶量逐 渐升高，碰撞概牢对吞吐量的影响逐渐降低，当碰撞概率对吞吐量的影响降低到 某一值时，竞争窗u 大小对吞吐景的影响占主导地位，园此随着竞争商u 的进一 步增大自私肯点的吞吐量将随之下降， 第章绪论 0 4 c h e a er ss i m u l 0 2 c h e a t er s a n a 4 y ， w e l l _ b s h a v o ds l m u l 。型业主业型型竺坚 01 0 2 03 0 4 05 d6 07 0 8 09 01 0 ( c 0 m o n l l o nw i n d o wf w lo fc h e a t e r s 图1 5 ”多节点自私的情况下，竞争窗口与吞吐量的关系 1 4 国内外研究现状 随着a d h o c 网络在民用领域的拓展，越来越多的大学和研究机构加入到了 a d h o c 州络的研究当中。a d h o c i 旬9 络m a c 层自私行为检测是当前研究的一个 热点。 1 41 启发式检测方法 在i e e e8 0 2 1 1 d c f 协议中，退避时间是发送节点在区间0 ，c w l 中随机选择 的一个值，因此发送节点两次连续传输之间的时间可以是上述区间的任何值，因 此即使接收节点或其它邻居节点能够获得发送节点两次连续传输之间的时间间 隔，也很难区别该时间间隔是被篡改过的还是正常的。pk y a s 册l l r 等人在文献r 9 ， l o 中提出通过让接收节点指定发送节点的退避时间来打破退避时间的“神秘 性”从而达到检测的目的。通过文献9 ，1 0 1 中给出的仿真结果可以看出，该方 法可以快速有效地榆测篡改退避时间这一自私行为，但是这一方法对现有协议的 修改过大，而且该方法的两个前提假设接收节点可信、发送节点与接收节点 不存在串谋明显不适片j 于a dh o c 网络。虽然作者试图对该方法进行扩展以解决 这两个前提假设所存在的问题，但扩展还不是根完善，有待进一步改进。l e i g u a u g 和c h 删t ia s s i 【l ”等人通过改进二进制指数退避算法( b i n a , 呵e x p o n e m i a i b a c k o 或b e b ) ，使得退避时间具有一定的可预测性，进而达到检测自私行为的目 的。但是改进后的退避算法将明显增加节点之间的碰撞概率。 通过l3 2 小节的介绍叮咀知道除了修改退避时间这种自私行为之外，m a c 层还存在其它的自私行为，文献【7 】针对目前已知的m a c 层自私行为设计了 第一章绪论 d o m i n o ( s y s t o nf o rd e t e c t i o no fg r e e d yb e h a v i o ri n 也em a cl a y e ro fi e e e 8 0 2 1 1p u b l i c n e t w o r k s ) 系统，该系统可以用来快速地检测目前己知的m a c 层自 私行为，而且还可以随时增加新的模块用来检测新的自私行为。d o m i n o 系统 只需要在a p 处安装d o m i n o ，而不需要修改移动主机处的m a c 层协议，因此 其兼容性也很强。但是这也必然导致了其不适用于a dh o c 网络。而且随着模块 的增加，d o m i n o 系统可能做得非常大，以至于严重影响a p 的性能。 1 4 2 基于统计的检测方法 由于退避时间的随机性，单独的退避时间无法区别节点是否自私，因此统计 的方法在这类问题上能发挥很好的作用。文献 1 2 针对修改m a c 层退避时间的 自私行为，提出了一种基于k s 检验的检测方法。仿真结果表明在不需要事先 知道节点自私行为策略的情况下，该检测方法具有很好的性能。文献 1 3 】在 m i n i m a x ( 极小极大分析) 框架下，使用s p r t ( 序贯概率比检验) 来检测自私行 为。相对于其它检测方法而言，基于统计的检测方法基本上不需要对现有协议进 行修改，因此具有比较强的兼容性和可用性。 1 5 论文工作 本文工作主要包括以下4 个方面： 1 改进s w n c u s u m ( s l i d i n gw i l l d o wn o n p a r a m e t e rc u m u l a t i v es u m ) t 1 4 算法。 s w n c u s u m 算法是一种基于统计的m a c 层自私行为检测算法，它能够快 速地判断a dh o c 网络中是否存在自私节点，但是无法判断哪个节点为自私 节点。针对s w n c u s u m 算法存在的这一问题，本文对其进行了改进。改 进后的s w n c u s u m 算法一共包括两个模块，模块一调用原s w n c u s u m 算法判断网络中是否存在自私行为，模块二找出网络中的自私节点。 2 在q u a l n e t 仿真平台上实现改进后的s w n c u s u m 算法。仿真结果表明， 改进后的s w n c u s u m 算法能够实时地对m a c 层自私行为进行快速、准 确地检测。 3 提出基于免疫原理的m a c 层自私行为检测系统一一s d s i ( t h es e l f i s h b e h a v i o rd e t e c t i o ns y s t e mb a s e do ni m m u n et h e o r y ) 。s d s l 分为预处理模块、 先天性检测模块、获得性检测模块和处理模块。s d s i 是一个基于规则的检 测系统，它通过连续r 位匹配算法来判断邻居节点m a c 层接入延迟编码是 否与检测规则匹配，从而达到检测自私行为的目的。对于一个基于规则的检 测系统而言，检测规则的质量直接影响着检测的效果，因此为了保持检测规 第一章绪论 则的多样性和优越性，s d s i 定期对检测规则进行变异操作。 4 基于免疫原理的m a c 层自私行为检测系统的q u a l n e t 仿真实现。仿真结果 表明，s d s i 能够快速、准确地检测出m a c 层自私行为，而且适用于多跳和 多节点自私场景。 1 6 论文结构 下面简单介绍一下本文的结构。第二章对s w n c u s u m 算法进行改进，使 其不但能够发现网络是否存在异常，而且可以检测出哪个节点是自私节点；第三 章在q u a l n e t 仿真平台上实现改进后的s w n c u s u m 算法；第四章提出一种基 于免疫原理的m a c 层自私行为检测系统；第五章通过q u a l n e t 仿真验证s d s i 的检测性能；第六章对全文进行总结，并指出了存在的不足和以后需要进一步改 进的地方。 第二章基于c u s u m 的检测方法 2 1 引言 第二章基于c u s u m 的检测方法 从1 4 节的介绍可以看出，启发式m a c 层自私行为检测方法对现有协议的 修改过大，而基于统计的检测方法在不需要对现有协议修改的基础上，仍然能够 快速、准确地检测出自私行为。但是现有的基于统计的检测方法也有一定的局限， 比如事先需要知道统计模型。s w n c u s u m 算法是一种基于统计的无参检测算 法，它不需要事先知道统计模型，而且同时具有快速、准确检测自私行为的优点。 2 2 特征序列的选取与测量 2 2 1 特征序列的选取 在基于统计的自私行为检测方法中，节点为了检测自私行为必须收集足够多 的统计数据。在a dh o c 网络中，节点在m a c 层可以收集的统计数据有节点吞 吐量和m a c 层接入延迟，下面将对比分析这两种统计数据，然后给出适合自私 行为检测的特征序列。 1 节点吞吐量的大小表面上看是区分节点自私与否的重要特征，但是节点吞吐 量的大小除了与自私相关以外，它更大程度上取决于于节点运行的上层应用 程序，例如一个节点的上层应用为流媒体应用，而另一个节点的上层应用为 h t t p 应用，一般而言，第一个节点的吞吐量会大于第二个节点的吞吐量。 2 在a dh o c 网络中，m a c 层一般使用i e e e8 0 2 1 1d c f 协议，该协议从本质 上保证了节点的m a c 层接入延迟统计公平，所以如果某个节点存在自私行 为，那么其m a c 层接入延迟会比别的节点低，换句话说m a c 层接入延迟 可以作为区别节点自私与否的特征数据。 结合上面的分析，本文将特征序列选取为m a c 层接入延迟序列。 2 2 2 特征序列的测量 a dh o c 网络使用无线信道作为通信媒介，无线信道是一个广播信道，因此 第二章基于c u s u m 的检测方法 节点可以很容易侦听到邻居节点发送的任何m a c 帧。通过1 2 节的介绍可以知 道a dh o c 网络m a c 层一般使用i e e e8 0 2 1 1d c f 协议，该协议有两种数据传输方 式基本数据传输方式和r t s c t s 数据传输方式。如果使用基本数据传输方 式，节点通过公式( 2 1 ) 计算邻居节点的m a c 层接入延迟。 n m a d i ，= ( 1 ，一t “一l 一7 赫一7 b ) 仃 ( 2 - 1 ) 其中 n m a d , ，：邻居节点i 的第j 个m a c 层接入延迟估计值 t i ，：侦听到邻居节点i 发送第j 个实际数据帧的时刻 t u 一，：侦听到邻居节点i 发送第j 1 个实际数据帧的时刻 ：d i f s 时间间隔 k ：7 e t 。一，t i , j 】这段时间内信道忙的时间 盯：s l o t 时间间隔 t i - l j o 墨 壹 n c 大 卜一 ， 图2 1 基本数据传输方式下邻居节点m a c 层接入延迟计算方法 如果使用r t s c t s 数据传输方式，节点通过下面的公式来计算邻居节点的 m a c 层接入延迟。 n m a d f = ( f 吖一t “一l 一7 赢一互唧) 盯 ( 2 - 2 ) 1 本文提到的邻居节点均为一跳邻居节点，即在节点传输范围之内的邻居节点。 第二章基于c u s u m 的检测方泫 其中 n m a d , ，：邻居节点i 的第j 个m a c 层接入延迟估计值 f f ，：侦听到邻居节点i 发送第j 个r t s 帧的时刻 一。：侦听到邻居节点i 发送第j 1 个r t s 帧的时刻 瓦詹：d i f s 时间间隔 k ：在h 山，t i , j 】这段时间内信道忙的时间 盯：s l o t 时间间隔 r 日 h = n m a d i 。， k 图2 2r t s c t s 模式下邻居节点m a c 层接入延迟计算方法 2 3c u s u m 算法 c u s u m ( c u m u l a t i v es u m ) 算法【1 5 】是统计过程控制中的一种基本算法，它可 以发现统计过程中均值的微小变化。c u s u m 算法的理论依据是随机序列一旦发 生某种变化，那么其概率分布也会发生相应的变化【l6 】，c u s u m 算法能够非常迅 速地检测到随机序列概率分布的这种变化，因此它被广泛地应用于统计过程控制 中。c u s u m 算法是一类序列变化点检测算法，它的目标是判断随机序列是否发 生了某种变化，如果检测发生了某种变化，相应地给出变化发生的时间。c u s u m 算法的数学描述如下。 令陇i = 0 ，l ，田表示一个随机序列，相互独立，且概率密度函数为 p 。o ) 。在随机序列发生变化前，参数护的值为吼，发生变化后秒的值变为q o o 。 c u s u m 算法就是要检测出这种改变，并且给出变化发生的时问。 c u s u m 算法中一个关键概念是对数似然比( 1 0 9 1 i k e l i h o o dr a t i o ) ，其定义如 ； 第章基于c u s u m 的检测方法 下： ( 2 - 3 ) 对数似然比的一个重要统计特性是在参数目发生变化前其均值为负，而在参数0 发生变化后其均值为正。 令 七 s 。- - z s ， 滓i 聊t2 蹬l g i = s 女- m 女h ( 2 4 ) ( 2 - 5 ) ( 2 - 6 ) 其中h 是根据实际情况给定的一个阈值。如果式( 2 6 ) 为真，就说明统计过程发生 了某种变化，而发生变化的时间点由式( 2 7 ) 给出。 2 4s w n c u s u m 算法 t 。= m i n k ：g 女h ) ( 2 7 ) 通过2 3 节的介绍可以知道，c u s u m 需要预先知道随机序列的概率密度函 数n ( 工) ，但是对于动态变化的a dh o c 网络而言，m a c 层接入延迟的概率密度 函数基本上是不可能获得的，因此文献 1 4 】提出了一种基于c u s u m 的滑动窗口 无参检测算法( s w n c u s u m ) 。s w n c u s u m 主要思想描述如下： 令 x i = x ：一a 胪y i _ l 强嚣。黑“ ( 2 8 ) ( 2 - 9 ) 器 nl = s 第二章基于c u s u m 的检测方法 其中a 为随机序列 咒i = o ，1 ，秘均值的一个上界，y o - - 0 ，1 1 为滑动窗口大小。 对应的决策函数为 d 。c y ，= ? 妻三： 如果d 。( y ，) = 1 ，说明统计过程发生变化，发生变化的时间为 2 5s w n c u s u m 算法改进 ( 2 一1 0 ) 乞= m i n i ：d 以) = 1 ( 2 1 1 ) 2 4 节介绍的s w n c u s u m 算法只能发现网络中是否存在自私行为，但是 不能确定具体哪个节点是自私节点。本文对s w n c u s u m 算法进行改进，使其 不但能够发现网络异常而且能够确定自私节点。改进后的s w n c u s u m 检测算 法一共包括两个模块，第一个模块判断网络是否出现异常，第二个模块找出异常 网络中的自私节点。 第一个模块按照文献 1 4 】中提出的s w n c u s u m 算法来判断网络是否出现 异常。 在第二个模块中，定义 x ? i = b x 1( 2 - 1 2 ) 其中b 为随机序列 凰i = 0 ，l ，厨( 该随机序列就是2 2 节统计的m a c 层接入 延迟序列) 均值的一个下界，在正常情况下x ，的均值为负。如果某个节点的x ， 的均值变为正时，第二个模块就断定这一节点为自私节点。 由于a dh o c 网络随着时间动态变化，因此距离当前时间越久的x ，对当前 的影响越小，因此改进后的算法仍然将使用滑动窗口模型。 令 第二章基于c u s u m 的检测方法 y f = ( e ) + i u k = t - u + l 与s w n c u s u m 类似，为了提高计算效率，给出y ，的递归定义表达式 ( 2 1 3 ) 一屯砸y i - i x 暑- x 霄i “ ( 2 - 1 4 ) 。1 【y ，一l + (i ) + 一(，) + ， “ 、 其中，“为滑动窗口大小， 对应的判定函数为 姒一，= ? 搿 ( 2 一1 5 ) ( 2 - 1 6 ) 即当以( y ，) = l 时，断定该m a c 层接入延迟序列所对应节点为自私节点。自私 发生的时间由下面的公式给出。、 2 6 本章小结 t 。= m i n i ：d ( y f ) = 1 ) ( 2 - 1 7 ) 本章首先讨论了特征序列的选取和测量，接着分别介绍了c u s u m 和s w n c u s u m 算法，最后针对s w n c u s u m 算法无法确定哪个节点是自私节点的问 题，文章提出了一个改进的方法。改进后的s w n c u s u m 算法具有广泛的适用 性，它可以实时地检测出任何引起m a c 层接入延迟发生变化的m a c 层自私行 为。 o p 区 叫 x x o； 乩$ = x 第三章改进后的s w n c u s u m 算法性能评价 第三章改进后的s w n c u s u m 算法性能评价 3 1q u a l n e t 仿真实现 3 1 1q u a l n e t 仿真介绍 q u a l n e t t t s 由s c a l a b l en e t w o r kt e c h n o l o g i e s ( s n t ) 公司开发，是一种应用于 无线、有线以及混合动态网络的快速、精确的开发、仿真系统，是美国加州大学 洛杉矶分校( u c l a ) 开发的开放源代码的g l o m o s i m 的商业版本。 q u a l n e t 使用的是一种分层体系结构，这种分层结构与t c p i p 网络的协议栈 类似。由于q u a l n e t 使用分层结构，所以q u a l n e t 中数据只在相邻层之间移动。 q u a l n e t 的协议栈从上到下依次为应用层( a p p l i c a t i o nl a y e r ) 、传输层( t r a n s p o r t l a y e r ) 、网络层( n e 押o r kl a y 盱) 、链路层( l i n kl a y e r ) 和物理层( p h y s i c a ll a y e r ) 。 q u a h a e t 链路层提供了点到点的数据传输。在发送端链路层从网络层接收数据并 且依赖于物理层通过通信信道将数据发送出去，而在接收端链路层从物理层接收 数据然后将数据上传至网络层。q u a l n e t 中已经实现的链路层协议有p o i n t