无线传感器网络的信息分级多路径路由算法.pdf

2 0 1 1年 第 3 O 卷 第 6期 传感器与微系统 T r a n s d u ce r a n d Mi cr o s y s t e m T e ch n o l o g ie s 1 0 9 计算与测试 0 p P 无线传感器网络的信息分级多路径路 由算法 何佩 卢先领 秦宁宁 徐保 国 江南大学 物联 网工程学 院 江苏 无锡 2 1 4 1 2 2 摘要 经过分析多路径路由协议的实时胜能 提出了一种信息分级的多路径路由 MP I C 算法 该算 法采用最小跳数法创建路由表 建立了可以中转节点选择概率模型 系统根据信息等级调整相关权值 以 满足不同等级信息的时延和可靠性能要求 仿真实验表明 与 E E A R E A MMS P E E D协议相比 该算法可 以有效降低信息时延 具有较高的数据传输可靠性 在多业务流应用方面能够表现出良好的性能 关键词 分级 多路径 路由协议 无线传感器网络 中图分类号 T P 2 1 2 文献标识 码 A 文章编号 1 0 0 0 9 7 8 7 2 0 1 1 0 6 0 1 0 9 0 3 I n f o r m a t io n cla s s ifi ca t io n b a s e d mu lt i p a t h r o ut ing a lg o r it hm f o r wir e le s s s e n s o r ne t wo r ks H E P e i L U X ia n l in g Q I N N i n g n in g X U B a o g u o S ch o o l o f ln t e r n e t o f T h in g s E n g in e e r in g J ia n g n a n U n i v e r s i t y Wu x i 2 1 4 1 2 2 C h i n a Ab s t r a ct Re a l t ime p e rf o r ma n ce o f mu lt i p a t h r o u t in g p r o t o co ls is a n a ly z e d An in f o r ma t io n cla s s if ica t io n b a s e d mu lt i p a t h r o u t in g a lg o r it h m is p r o p o s e d T h is n e w a lg o r it h m cr e a t e s r o u t in g t a b le u s in g min imu m h o p n u mb e r s m e t h o d s e t u p a p r o b a b i lit y m o d e l w h e r e r e le v a n t w e i g h t co u l d b e a d j u s t e d b a s e d o n t h e le v e l o f in f o r ma t i o n i n o r d e r t o me e t s u ch p e rf o r ma n ce r e q u ir e me n t s a s d e ma n d o f t ime d e la y a n d r e lia b ilit y o f d if f e r e n t le v e ls o f in f o rm a t io n S imu la t io n r e s u lt s in d ica t e t h a t co mp a r e d w it h E E AR a n d EAMMS P E ED t h e n e w r o u t in g al g o r it h m p r o v id e s s h o r t e r t ime d e la y a n d h ig h e r r e lia b ilit y o f d a t a t r a n s mis s io n I t h a s g o o d p e r f o r ma n ce o n b u s in e s s p r o ce s s co n t e x t a p plica t io n Ke y wo r ds cla s s ifi ca t ion mu lt i p a t h r o ut in g pr o t o co l wir e le s s s e n s o r n e t wo r k s 0引 言 无线传感器网络是由部署在监测区域内大量的廉价微 型传感器节点组成 通过无线通信机制形成的一个 自组织 网络系统 能够实时感知和收集网络分布区域内的各种有 效信息 并对这些信息进行处理 传送到用户 无线传感器 网络是继因特网之后 对2 1世纪人类生活方式产生重大影 响的 I T热点技术 在战场跟踪 空间探索等应用中 系统对数据实时性要 求较高 感知数据仅在一定时间内有效 所以 数据在有效期 之前发送至基站 对成功执行任务至关重要 除实日 寸 生要求 之外 信息可靠性同样重要 在森林火灾监测应用中 正常温 度的感知数据可以容忍一定的丢包率 然而异常温度的感知 数据则需要可靠地发送到基站 因为它可能是火灾的征兆 因此 需要设计可提供多种业务流需求的路由协议 1 相关研究 在无线传感器网络应用 中 单路径路由协议容易造成 收稿 日期 2 0 1 0 0 9 1 3 基金项目 国家 8 6 3 计划资助项 目 2 0 0 7 A A 1 0 Z 2 4 1 网络能量消耗不均衡 传输路径上节点能量 肖 耗过快会形 成路 由空洞 在源节点和汇聚节点之间建立多条路径 则 可降低路 由请求的频率和数据等待延时 从而提高数据传 输的可靠性 能够为不同的服务质量要求提供不同的路径 目前主要的多路径路由协议有 S P I N E A R MMS P E E D等 S P I N s e n s o r p r o t o co l f o r i n f o rma t io n v i a n e g o t ia t i o n 协议 是以数据为中心的多路径路由协议 基本思想是通过三次 握手的协商过程和 元数据 来解决信息爆炸 信息重复和 资源浪费等问题 缺点是当产生或收到数据的节点的所有 邻居节点均不需要数据时 无法保证数据的可靠传递 E E A R e n e r g y a w a r e r o u t in g 协议是一种能量相关的路 由协议 该协议根据与邻居节点的距离和节点的剩余能量 情况 使数据传输均衡消耗整个网络的能量 但其网络扩展 性一般 MMS P E E D m u lt i p a t h a n d m u l t i s p e e d r o u t in g p r o t o co 1 1 l0 传 感 器 与 微 系 统 第3 O卷 协议是一种可靠式路由协议 通过多个全局的分组传输速 率来保证实现实时需求 E A MM S P E E D则在 MMS P E E D协 议基础上 在选择前向路径时考虑了4个因素 地理位置 可靠性 延迟 剩余能量 缺点是算法相对复杂 能量消耗较 大 针对多种业务流对实时性 可靠性等指标有不同需求 的特点 本文根据信息重要性进行信息分级 提出了一种信 息分级路由 MP I C 算法 经仿真实验证明 该协议在保证 信息可靠率的同时 降低信息延迟 延长网络生命周期 2 算法分析 M P I C算法由3个部分组成 1 路由创建 通过最小跳 数法创建节点路 由表 最小跳数法实现简单 节点只需了解 局部拓扑信息 2 路径选择 通过建立中转节点的选择概率 模型 均衡网络能量分布 3 路由维护 通过广播剩余能量 和传输差错率信息 提供路径选择中所需参数值 2 1 路 由创建 用 h表示传感器节点到达汇聚节点的跳数 初始时设 定 S i n k节点的跳数为 h 0 其他节点到达 S in k节点的跳 数为 h o S in k节点向网络广播路由创建消息 当节点 收到节点 的路由创建消息后 按以下规则进行处理 1 如果 h v h u 1 清空现有的路 由表内容 再将节点 添 I n N 1 级路由表中 更新 h v h u 1 广播带有 砌的路 由创建信息 J 当2个和2个以上节点同时向同一邻居节点发送广播 信息时 将导致数据冲突的发生 为了减少数据冲突 所有 的节点第一次接收到路 由创建消息后 需要等待一段时间 包括固定时间和随机时间 后再转发路由创建消息 如同 以太网中采用的退避算法 固定时间的长短 由路由创建消 息的跳数值决定 跳数越多 固定时间越长 虽然固定时间 的设置会延长路由创建时间 但可以增加广播的可达性 为了减少全网的路由创建信息量 每个节点仅转发一次路 由创建信息 J 2 2 路径选择 贪婪路由中频繁使用能量消耗最小的路径进行信息传 输 虽然可以取得较低的传输时延 但造成该路径上的节点 因耗能速度过快而提前失效 为了均衡网络能量分布 设节 点 U选择邻居节点 作为下一跳节点的概率为 r fv p a ll o w 其中 a l lo w 代表节点 I的路由表中所有节点 e 代表 节点 与节点 间的通信延时 是节点 的剩余能量 参 数 O t 和 分别表示通信延时和节点剩余能量的可调权值 可以根据需求调节 O l和 j 节点监I t i f l的信息等级越高 则通信延时的权值 设 置越高 剩余能量的权值 设置越低 若信息需要一定的 可靠率保障时 则将同一份数据备份 沿着不同路径传递 从效率和开销角度来看 选取 3条路径从效率和开销的折 中来看是相对最佳的 当信息等级最高时 通信延时的权 值 O 设置为 1 剩余能量的权值 设为 0 中转节点通过检 查信息等级值 做 出同样的参数设置 直到将信息传送到 S i n k节点 这种以不同路径发送相同数据的方式可以提高 数据可靠性 当节点 t 向 S i n k节点发送消息 按下述的伪随机 比例 规则在 1 级路由表中选择节点 V 作为下一跳节点 a r g m a x e g g o 其他 式中q 0 1 为随机变量 q 0 1 是常数 是根据 式 1 的选择概率模型产生的一个随机变量 若节点 I t 的 1级路由表中的节点全部无效 则在 2级路由表中按照伪随 机比例规则选择下一跳节点 2级路 由表的设立增强 了网 络的鲁棒性 避免了网络因部分节点失效而造成的局部瘫 痪 数据丢失和传输速率较低的传送均视为传输差错 为 了节点间的数据传输满足一定的传输速率要求 低于传输 差错率阈值的节点禁止作为中转节点 2 3 路 由维护 当节点的剩余能量发生改变时 向网络广播能量信息 邻居节点接收到能量信息包后更新相应路由表项 MA C层 收集差错消息 并将传输差错率通告给所有邻居节点 以便 能正确地选择下一跳节点 当节点的剩余能量小于阈值 时 仅接收和发送等级较高的信息 3 仿真实验与结果分析 分别 对 MP I C E E A R以及 E A MM S P E E D协议进行 了仿 真 对比这 3种算法在相同环境下的信息时延和生命周期 节点随机产生3个等级的信息 对信息时延有不同的需求 仿真参数为 监测区域5 0 0 m 5 0 0 m 节点数量2 5 0个 初始 能量 1 J 最大传播半径 5 0 m 信息时延是指信息从源节点传输到汇聚节点所用的时 间 其中包括了发送时延 传播时延 处理时延等 图 l 所 示 MP I C算法的信息时延小于 E E A R和 E A MMS P E E D协 议 这是由于 M P I C算法根据信息等级调节发送延迟权值 和使用路径数量 以满足不同业务流的实时性要求 在遇 到路由 空洞 现象时 E A M MS P E E D协议采用了反向压力 路由变更机制 虽可以对网络 空洞 现象做出有效反应 但 第 6期 何佩 等 无线传感器网络的信息分级多路径路由算法 它是以信息时延为代价的 而 MP I C算法采取了设定能量 阈值的方法 当剩余能量小于能量阈值时 节点仅可以发送 和接收高等级消息 降低了高等级信息的延迟 6 5 6 0 5 5 5 0 4 5 4 0 3 5 一 M P I C E E AR E AMM S P E E D a o 0 5 0 lO U l5 0 2 0 0 2 5 0 3 0 0 时间 rain 图 1 信息 时延 F ig 1 Time d e la y o f in f o r ma t io n 图2所示为生存节点数量随网络运行时间而变化的情 况 E E MMS P E E D协议因为算法比较复杂 所消耗的能量较 大 部分节点因能量耗尽较早退 出网络 E E A R算法虽然 可以均衡能量分布 但是 以信息时延作为代价 无法满足 不同业务流的时延要求 且采取链路重传机制这类被动地 提高传输成功率的方法 耗费大量的能量 而 M P I C算法 在路径选择中主动过滤了低于传输差错率阈值的节点 减 少了因数据丢包而进行重传所消耗的能量 当在发送对实 时性要求不高的数据时 可以通过调节剩余能量 的权值均 衡整个网络的能量分布 删 删 虹 士 H 时l 司 mi 图 2生存节点数量 Fig 2 Nu mbe r o f s u r v iv in g no de s 4 结束语 本文针对多业务流应用的性能要求提出了 MP I C算 法 该算法根据监测指标进行信息分级 对不同等级的信息 采取针对性的路径选择 高效率地应对异常情况 在保障 传输成功率的同时 降低信息的传输时延 延长网络生命周 期 上接第 1 0 8页 参考文献 1 孑 L 凡琴 微焦点 x射线 检测技 术 的现状 与应用 J 无 损检 测 2 0 0 8 3 0 1 2 9 3 1 9 3 3 2 何伟 李薇 张玲 基于计算机图像处理 的电路印刷板 缺陷监测 J 计算机测量 与控制 2 0 0 7 1 5 1 0 1 2 9 5 1 2 9 7 3 胡永芳 徐玮 禹胜林 等 B G A封装器件焊点缺陷 x射线 检测法 J 电子工业技术 2 0 0 5 2 6 6 3 4 0 3 4 4 4 蒋刚毅 郁梅 陈晓明 等 基于图像处理的 B G A封装器件 缺陷检测算法 J 计算机应用研究 2 0 0 2 7 1 0 0 1 0 1 参考文献 1 孙利民 李建中 陈渝 等 无线传感器网络 M 北京 清 华大学出版社 2 0 0 5 2 A l w a n H A g a r w a l A A s u r v e y o n f a u l t t o l e r a n t rou t i n g t e ch n iq u e s i n w i r e le s s s e n s o r n e t w o r k s c P r o c o f t h e T h i r d I n t e r n a t i o n a l Co n f e r e n ce o n S e n s o r Te ch n o lo g ie s a n d Ap p lica t io n s Gr e e ce 2 0 0 9 3 6 6 37 1 3 T a n g L i a n g L i Qi a o li a n g S S P I N A p r o v a b ly s e cu r e rou t i n g p r o t o co l f o r w i r e l e s s s e n s o r n e t w o r k s C P ro c o f t h e 2 0 0 9 I n t e r n a t io n a l C o n f e r e n ce o n Co mmu n i ca t io n S o ft wa r e a n d Ne t wo r k Ma ca u 2 0 0 9 6 2 0 6 2 4 4 Y o u n u s M Mi n h a s A J a v e d M Y e t a 1 E E A R E ffi ci e n t e n e r g y a w a r e ro u t i n g i n w i r e l e s s s e n s o r n e t w o r k s C P r o c o f 2 0 0 9 I n t e ro a t io n a l Co n f e r e n ce o n Ult r a Mo d e r n Te le co mmu n ica t io n s Wo r k s h o ps Ru s s ia 2 0 0 9 5 7 6 2 5 S a n a t i s Y a g h m a e e M o h a m m a d H o s s e i n B e h e s h t i A s g h ar E n e r gy a ware mu lt i p a t h a n d mu lt i S PEE D r o u t in g p r o t o co l in wir e le s s s e n s o r n e t w o r k s C P r o c o f t h e 1 4 t h I n t e r n a t i o n a l C S I C o m p u t e r C o n f e r e n ce I r a n 2 0 0 9 6 4 0 6 4 5 6 H u ang S C J an R H E n e r gy a w a r e lo a d b a l a n ce d ro u t i n g s ch e m e s fo r s e n s o r n e t w o r k s p a r a l l e l a n d d is t rib u t e d s y s t e m s C P r o c o f t h e 1 0t h I n t e r n a t io n a l C o n f e r e n ce o n Para lle l an d Dis t r ib u t e d S y s t e ms US A I EE E 2 0 0 4 41 9 4 2 5 7 K i m J L in X S h r o ff N B e t a1 O n m a x im i z i n g t h e li f e t i m e o f d e la y s e n s i t i v e w i r e le s s s e n s o r n e tw o r k s w i t h a n y e a s t C P r o c o f I EEE I NF OCOM Ph e o n ix AZ US A 2 0 0 8 8 0 7 8 1 5 8 F e l e m b a n E L e e C G E k i ci E e t a1 M M S P E E D M u h i p a t h m u l t i s p e e d p r o t o co l for Q o S o f r e l iabi l i t y a n d t i m e l i n e s s i n w i r e l e s s s e n s o r n e t w o r k s J Mo b i le C o m p u t i n g 2 0 0 6 5 6 7 3 8 7 5 4