WMSNs中目标覆盖算法与通信策略研究.pdf

3 2 传感器与微系统( T r a n s d u c e r a n d Mi c r o s y s t e m T e c h n o l o g i e s ) 2 0 1 3年 第3 2卷 第 8期 WMS Ns 中目标覆盖算法与通信策略研究 王晓晨，冯秀芳，辛英 ( 太原理工大学 计算机科学与技术学院， 山西 太原 0 3 0 0 2 4 ) 摘要：在无线多媒体传感器网络 ( WM S N s ) 中， 覆盖控制是一个基本 问题， 反映了无线传感器 网络 ( WS N s ) 对外部世界的感知能力。基于 WMS N s 的有向感知模型， 对基于优先级的目标覆盖算法研究。针 对贪婪算法和改进的贪婪算法具有局部最优性且没有考虑网络中目标的覆盖度的问题进行改进 ， 尽量照 顾覆盖边缘的关键节点 ， 提出了基于优先级的方向优化算法。针对 WMS N s 通信的高宽带需求 ， 模拟生物 的动态平衡特性， 为 WMS N s 提出了动态平衡 自主通信算法 ， 使传感器节点能自主合作 、 有效地进行的事 件信号通信。一系列仿真实验证明了算法在应用中的有效性。 关键词：无线多媒体传感器网络；覆盖增强； 方向优化；自主通信； 动态平衡 中图分类号 ：T P 3 9 3 文献标识码 ：A 文章编号 ：1 0 0 0 - 9 7 8 7 ( 2 0 1 3 ) 0 8 - 0 0 3 2 -03 S t u d y o f t a r g e t c o v e r a g e a l g o r i t h m a n d c o mmun i c a t i o n s t r a t e g y i n W M S Ns W ANG Xi a o c h e n，F ENG Xi u- f a ng，XI N Yi n g ( S c h o o l o f C o mp u t e r S c i e n c e a n d T e c h n o l o g y ， T y u a n Un i v e r s i t y o f T e c h n o l o gy ， T y u a n 0 3 0 0 2 4 ， C h i n a ) A b s t r a c t ：I n w i r e l e s s mu l t i m e d i a s e n s o r n e t w o r k s ( WM S N s ) ， c o v e r a g e c o n t r o l i s a b a s i c p r o b l e m， w h i c h r e fl e c t s s e n s i n g a b i l i t y o f W MS N s o n o u t s i d e wo r l d Di r e c t i o n s o p t i mi z a t i o n a l g o ri t h m b a s e d o n p ri o ri t y i n v i e w o f d i r e c t i o n a l s e n s i n g m o d e l o f WMS N s i s s t u d i e d A i m i n g a t p r o b l e m t h a t g r e e d y al g o r i t h m s ( G A) a n d e n h a n c e gre e d y a l g o ri t h ms ( E G A ) h a v e l o c al o p t i mi z a t i o n a n d w i t h o u t c o n s i d e ri n g t a r g e t c o v e r a g e ， i m p r o v e t h e al g o r i t h m， t r y t o c o n s i d e r k e y n o d e s t h a t c o v e r e d g e s ， p u t f o r wa r d d i r e c t i o n s o p t i mi z a t i o n alg o ri t h m b a s e d o n p ri o ri t y Ai mi n g a t h i g h ba nd wi d t h r e q ui r e me n t s for c o mmu ni c a t i o n i n W MS Ns，s i mu l a t e bi o l o g i c ho me o s t a s i s p r o p e r t y，p r o p o s e h o me o s t a s i s a u t o n o mo us c o mmu ni c a t i o n a l g o r i t hm f o r W MSNs， s e ns o r n o d e s ca n a u t o c o o pe r a t i o n， t a k e e v e nt s i g na l c o mmun i ca t i o n e f f e c t i v e l y A s e r i e s o f s i mu l a t i o n e x pe rime n t s p r o v e t h e e f f e c t i v e n e s s o f a l g o rit h ms i n a p p l i c a t i o n Ke y w o r d s ：w i r e l e s s m u l t i me d i a s e n s o r n e t w o r k s ( WMS N s ) ；c o v e r a g e e n h a n c e m e n t ；d i r e c t i o n s o p t i m i z a t i o n ； a u t o n o mo u s c o mmun i c a t i o n；h o me o s t a s i s 0 引 言 传统的无线传感器网络( WS N s ) 主要是对外部环境中 的单一的物理量进行采集和处理。随着人们要求获取的监 测环境数据更加全面、 丰富， 这就要求传感器能够感知更加 多样的信息， 如声音、 图像、 视频等。因此， 无线多媒体传感 器网络( w i r e l e s s m u l t i me d i a s e n s o r n e t w o r k s ， WM S N s ) 应运而 生 。WMS N s的应用前景非常广阔 ， 如 ， 环境监 测 、 智能家 居、 医疗卫生、 交通监控等 ， 在近年来受到了研究者的广 泛关注。在众多研究中， 覆盖和能量分配是研究 WMS N s 的核心 问题 。 在文献 4 中， 温俊等提出了改进的贪婪算法和公平 的方向优化算法。贪婪算法( g r e e d y a l g o ri t h m， G A) 应用在 WMS N s 的覆盖中， 具有复杂度低效果 良好的特点。在 G A 中， 节点每次选择覆盖最多目标节点的方向作为工作方向， 但邻居节点间不交换信息， 这可能造成对某些的目标的遗 漏。在改进的贪婪算法( e n h a n c e gre e d y al g o r i t h m， E G A) 中， 节点接收邻居节点的感知信息从而找出未被覆盖的 目标最 多的方向作为工作方向。 本文基于 WMS N s 的特点为目标覆盖提出基于优先级 的方向调整算法。该算法考虑 目标节点的覆盖度 ， 若 目标 节点覆盖度较小， 则优先级较高； 反之， 则优先级较低。节 点根据覆盖 目标总的优先级高低来选择工作方向。同时， 基于WMS N s的大数据量通信 的特点， 提出了动态平衡 自主通信算法， 减少冗余通信 ， 降低能耗。此算法以较低能 收稿 日期 ： 2 0 1 3 -01 - 2 7 基金项 目： 山西省 回国留学人员科研资助项 目 ( 2 0 1 1 - 0 2 9 ) ；山西省科技基础条件平台建设项 目 ( 2 0 1 1 0 9 1 0 0 0 3 -01 0 3 ) 第 8期 王晓晨， 等： WMS N s中目标覆盖算法与通信策略研究 3 3 源开支， 从事件信号取得足够数量的数据样本 ， 精确重建宽 带事件信号， 大大减少网络中的信息通信量。 1 有 向感知模型 本文采 用的有 向感知模 型如 图 1所示 ， 该模 型 由 四元 组 ( P， R， ， ) 表示 ， 其 中， P为节 点 的位 置 ， R为感 知半 径 ， 2 为视角范围， 为单位向量 ， 即主感知方向 j 。 图 1 有 向感知模型 Fi g 1 Di r e c t i o n a l pe r c e pt u a l m o d e l 若监测区域中目标点 P 被覆盖， 需要满足公式( 1 ) r f I ( 1 ) 【 I P P l I C O S P P 1 其中， I P P ： I 为传感器节点P到目标P 的欧氏距离。 在本文中假设 WMS N s中所有节点都是同构的， 即节点 参数规格相同。在初始部署后， 节点本身位置不动， 但方向 可调。各个节点都明确 自身位置与感知方向， 各节点对 自 身传感方向可控。 2 基 于优先 级的方向优化算法 由于 G A和 E G A都没有 考虑 目标 覆盖 度 的问题 ， 所 以 得到的结果一般 是局部 最优 的。针对 以上不 足 ， 本文 基 于 E G A的思想， 提出了基于优先级的方向优化( d i r e c t i o n s o p t i m i z a t i o n a l g o r i t h m b a s e d o n p r i o r i t y ， D O B P ) 算法 ， D O B P在节 点考虑 目标节点的覆盖度， 给覆盖度较小的 目标节点设定 相对较高的优先级 ， 而覆盖度较高的节点则优先级较低。 节点最终选择 目标节 点优 先级 最高的方向为工作方 向。 2 1 D O B P算法符号描述 优先级函数依赖于应用环境和要求。在本文 中， 优先 级函数P ( a ) 取决于目标节点的覆盖度， 覆盖度越低的节点 拥有越高的优先级 ， 期望得到更多节点的覆盖 ， P ( a ) 为 P ( U )= 一 ( 2 ) 其中， k和 为已决策节点和未决策节点为目标 a提供 的覆盖度。式( 3 ) 为节点在感知方向d 上总的优先级 h ( si ,d id ) ： j p a 4 A ；。 ( 3 ) 【 0 ， o t h e r w i s e 2 2问题建模 关键 目标是网络中覆盖度最小的目标， 对网络的生命 周期起决定性作用 ， 所以， 应具有高优先级。覆盖子集是 指在同一个活动期内能够覆盖所有 目标的节点集合。而 目 标覆盖的最终 目标就是覆盖网络 中的每个 目标， 同时使 网 络的生命周期最长。给定 目标节点总数A和传感器节点总 数 s ， 找出集合 S - ， S S ， 以及对应的 t 一， t ， 使得生 命 周 期 f 最 大。 覆 盖问 题 就 可以 被 形 式 化 的 描 述 为 日 m ax ， ( 4 ) P S i ,p ,h ， t ， V s S， ( 5 ) l p l H P S i,p ,h 1 ， V s S， ( 6 ) h= 1 P=1 S i ,p ,h 1 1 d ， s ， 。 E d S i,p ,h E o ， 1 ( 7 ) 公式( 5 ) 约束各个节点的工作总时间在其生命周期内， 公式( 6 ) 规定每个节点在同一时刻只能工作在一个方向上， 公式 ( 7 ) 确保 每个 目标 至少 被 一个 节点 覆 盖。通 过 以上 4个公式的约束， 能够找出网络中的多个覆盖子集。 图2给出D O B P算法的基本流程图。节点在循环过程 中找到各自的优化方 向， 从而形成覆盖所有 目标的网络多 覆盖子集。网络多覆盖子集的查找已经被证明是一个 N P 完全问题， D O B P只能近似的进行查找。 检测各个方 向目标信息。 计算各个方向优先级 确定最高优先级 的方 向 确定感知节点优先级 高级优先级节点决策 。 图 2 D OB P算 法流程 图 Fi g 2 Fl o w c ha r t o f DOBP a l g or i t hm 3动态平衡 自主通信机制 生物体能维持在一个相对稳定的平衡状态， 称为动态 平衡 。同样 ， WM S N s 也要保持在一个相 对稳定 的状态才 能 正常工作。为使 WMS N s 具有自我维护功能， 提出动态平衡 自主通信 ( h o me o s t a s i s i n s p i r e d a u t o n o m o u s c o m m u n i c a t i o n ， HA C ) 。HA C从事件信号中采用不规则抽样提取数据样 本 ， 使用最低能源开支来重建事件信号。同时提供实时带 宽事件信号通信 ， 根据其光谱特征调整通信参数 ， 这样就不 需要来 自汇聚节点的反馈消息。WMS N s 传感器与生物体 细胞功能对应如图3所示。 在 WMS N s中采用 H A C， 节点能够根据生物动态平衡 的原则进行协作交流事件信息。在作为传感器节点所使用 的采样和通信参数测定时， H A C将事件信号的频谱特征也 传 感 器 与 微 系 统 第 3 2 卷 神经 细胞( N。 C e l 1 ) ： 感知外界 刺激并激发 细胞分泌激素 腺细胞( G C e l 1 ) ： 分泌激素 并将外部刺激通知给组织 免役细胞( T C e l 1 ) ： 检测并排 除侵入组织的故障 N传感器 ： 对带宽频谱进行 评估 ， 行成集群 G传感器： N传感器集群的 簇头， 给汇聚节点传输数据 T传感器 ： 检测并将入侵通 知给N传感器和G传感器 图 3 生 物 体 和 无 线 多媒 体 传 感 器 网 络 映射 Fi g 3 M a p pi n g b e t we e n h o me o s tati c s y s t e m a n d W M S Ns 考虑进来。通过 N传感器对基于事件信号的频谱带宽估 计， 使用 G传感器来确定必须传递的取样数量， 以便在汇聚 节点能准确的重建。另外， 不规则采样是一个重要的节约 能耗的方式 J 。在不规则采样中， 当采样频率为l厂时 ， N传 感器按抽样概率从事件信号取样。这样 ， 能够有效减少传 感器节点传输 的样本数量 ， 减轻网络负荷 ， 在节约能量 的条 件下， 不规则采样能够提供更加准确的重建信息 。 HA C由5个不同的阶段组成 ： 光谱估计阶段 、 N传感器 聚类阶段、 抽样概率确定阶段、 频道频率选择阶段和信号重 建阶段。假设通过 N传感器 i 产生和传输的指标集和 ， 来 告知汇聚节点取 自 ( t )的样品 。J 是一个 向量 ， 用 1表示 抽取的样 本 ， 0表示错过 的样本 。这样 ， 就可 以通 过 ， 得知 哪些样本来 自 N传感器 i ， 在采样 间隔 T ( s ) 内包括这 些样 本的数据包和指标集合是否被接收。如果带有数据包的， 没有被接收， 则把指示集合设置为0 。I 作为 长度的比 特流进行传输 ， 在传输过程中开销很低。样本集由 N传 感器 i 产生和传播， 表示为 1 K = ， ( 1 ) ( 0 ) ， ( 2 ) ( ) ， ， ) ( T ) ( 8 ) 4 仿 真实验 本文实验采用 Ma t l a b 7 0实现， 将 5 0个有向传感器节 点随机部署在 4 0 0 m x 4 0 0 m的检测区域， 传感器节点的感 知半径 为 1 0 0 m。对 比采用 E G A和 D O B P调 整网络部 署的 覆盖效果。图4、 图5分别为使用 E G A和使用 D O B P调整 感知方向后的覆盖效果。图6显示在网络初始部署和应用 E G A， D O B P后， 关键 目标覆盖度与感知节点数 目的关系， 从 图中可以看 出： 1 ) 当节点随机初始部署后， 采用 E G A和 D O B P可以显著减少未被覆盖 目标的数量。2 ) 采用 D O B P 算法后对关键目标的覆盖度明显增加， 随着节点数 目的增 加， 关键 目标的覆盖度增大。 本文进一步比较分析了 E G A和 D O B P的性能， 并对结 合 H A C后的网络性能进行 了比较。图 7显示关键 目标覆 盖度和网络生存周期受节点数目的影响。通过计算的关键 目标覆盖度和网络生存期结果显示， D O B P+H A C在对关键 目标覆盖度和网络生存期延长上都具有更好的效果。 35 0 g 2 5 0 R 1 5 0 5 0 50 1 5 0 2 50 35 0 x m 图 4 EG A算法优化 Fi g 4 Op timi z a tio n o f EGA a l g o r i t hm 5 O 1 5O 2 50 3 50 x m 图5 D OB P算法优化 Fi g 5 Op t i mi z a t i o n o f DOBP a l g o rit hm 图 6 初始部署与 E GA及 DOB P的关键 目标覆盖度 Fi g 6 Orig i n a l d e p l o y me nt ， a n d EGA c o v e r a g e r a t e o f k e y ta r g e t s o fDOBP 皿 艘 舞 匿 烛 刊 酶 匿 感知节点数 目 图 7节点数 目对关键 目标 覆盖度和生命周期影响 F i g 7 Effe c t o f n umb e r o f n o d e s o n c o v e r ag e r a t e a n dl i f e c y d eof k e y o b j e c t 5 结论 本文通过采用基于优先级的 目标覆 盖算 法来调整节点 的工作方向， 从而优化无线多媒体传感器网络的目标覆盖。 D B O P针对 E G A没有考虑节点覆盖度， 结果是局部最优的 缺陷， 通过给节点赋予优先级对算法进行优化。仿真实验 结果表明： D O B P明显提高了对关键 目标的覆盖。同时， 模 拟生物的动态平衡特性 ， 提出了动态平衡 自主通信算法， 从 而减少网络中的信息通信量 ， 以降低网络的能耗， 延长网络 寿命。实验结果可以看出： 相比于 E G A， D O B P结合动态平 衡 自主通信算法达到了延长 WMS N s 生命周期的目的。 ( 下转第 3 8页 ) 2 2 l 1 O 蠖 皿 3 8 传 感 器 与 微 系 统 第3 2卷 0 5 7 0 0 5 2 0 0 4 7 0 0 4 20 U 1 U U 1 ， U 2 U U 2 U 30 U 3 0 40 睡眠概率 图5不同睡眠概率下的网络编码收益 Fi g 5 Ga i n s o f ne t wo r k c o d i n g whe n s l e e p p r o b a b i l i ti e s a r e d i ffe r e n t 从图中可看出： 用网络编码方法传输相比普通重传方 法， 传输效率提升了将近5 0 ， 且随着睡眠概率的增大， 所 获得的收益更大， 传输效率可以得到改善更明显。 实验 3如图 6为节点个数 为 1 O ， M=1 0 0 ， f 】 由 0 1 0 4， Z 2 =f 3 =f 1 +0 O 2 ， f 4 =Z 5 =Z 1 +0 O 4 ， Z 6 =Z 7 =f 1 +O 0 6 ， f 8 =Z l + 0 O 8 ， Z 9 = Z 1 0 =Z 1 +0 1 ， 卢 =0 2 ( 1 i 5 ) ， =0 3 ( 6 i 1 0 ) 时， 用网络编码进行重传的收益情况。从图中可 看出： 丢包概率越大， 用网络编码进行重传获得的收益越大。 O 6O 0 55 0 50 0 4 5 0 40 0 1 0 U 1 5 O 2 0 0 2 5 U 3U U 35 0 40 丢包率 图 6 不同丢包率下的网络编码收益 Fi g 6 Ga i n s o f n e t wo r k c o din g whe n p a c k e t - l o s s r a t e a r e d i f f e r e n t 6 结论 本文结合睡眠调度机制和网络编码， 提出了一种适合 于睡眠调度机制下的网络编码方法。该方法首先通过查询 当前发送时刻醒着的节点信息集合， 将醒着的节点丢失的 数据包通过网络编码组合发送， 使得编码包的效用最大， 通 过实验仿真验证可以看出： 这种方法相比原有的逐个重传 的方法能够有效地减少数据包的平均传输次数， 提高传输效 ； ； ( 上接第 3 4页 ) 参考文献： 1 马华东 ， 陶丹 多媒体传感器 网络及其进展 J 软件学 报 ， 2 0 0 6 ， 1 7 ( 9 ) ： 2 0 1 3-2 0 2 8 2 王汝传 ， 孙力娟 无线多媒体 传感器 网络技 术 M 北京 ： 人 民邮电出版社 ， 2 0 1 1 ： 9-1 2 3 A k y i l d i z I F ， Me l o d i a T ， C h o w d h u ry K R A s u r v e y o n w i r e l e s s mu l t i m e d i a s e n s o r n e t w o r k s J C o mp u t e r N e t w o r k s ， 2 0 0 7 ， 5 1 ( 4 ) ： 9 2 1 -9 6 0 4 温俊 ， 蒋杰 ， 窦文华 公平 的有 向传感器网络方向优化和 节点调度算法 J J o u r n a l o f S o f t w a r e ， 2 0 0 9， 2 0 ( 1 )： 6 4 4- 6 5 9 5 A t a k a n B a r i s ， A k a n O z g u r B D i s t r i b u t e d a u d i o s e n s i n g wit h h o m e o s t a s i s ， i n s p i r e d a u t o n o mo u s c o m mu n i c a t i o n J A d Ho c N e t - 率， 明显地降低节点的能耗， 进而延长 WS N s 的使用寿命。 参考文献 ： 1 P a r k J ， L u n D s ， S o l d o F ， e t a 1 P e r f o r m a n c e o f n e tw o r k c o d in g i n A d H o c n e t w o r k s C ffP r o e e e d i n g s o f Mil C O M 2 0 0 6 ， Wa s h i n g t o n DC， US A ， 2 0 0 6： 1-6 2 D o u g h e y R， F r e i l i n g C ， Z e g e r K L i n e a ri t y a n d s o l v a b i l i t y i n mu l t i c a s t n e t w o r k s J I E E E T r a n s a c t i o n s o n I n f o r m a t i o n T h e o r y 2 0 0 4， 5 0 ( 1 0 ) ； 2 2 4 3-2 2 5 6 3 K o e t t e r R， M e d a r d M B e y o n d r o u t i n g ： A n al g e b r a i c a p p r o a c h t o n e t w o r k c o d i n g J I E E E A C M T r a n s a c t i o n s o n N e t w o r k ， 2 0 0 3， 4 9 ( 2 ) ： 3 7 1 -3 8 1 4 L u n D S ， R a t n a k a r N， M e d a r d M， e t a1 Mi n i m u m c o s t mu h i c a s t o v e r c o d e d p a c k e t n e t w o r k s J I E E E T r a n s a c t i o n s o n I n f o rma t i o n T h e o ry， 2 0 0 6 ， 5 2 ( 6 ) ： 2 6 0 8-2 6 2 3 5 G a n e s a n D， G o v i n d a n R， S h e n k e r S ， e t a 1 H i g h l y r e s i l i e n t ， e n e r - g Y e f f i c i e n t m u h i p a t h r o 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 J AC M S I GMOBI L E Mo b i l e C o mp u t i n g a n d C o mmun i c a t i o n s Re - v i e w， 2 0 0 1 ， 5 ( 4 ) ： 1 1- 2 5 6 L i S Y， Y e u n g R W， C a i N L i n e a r n e t w o r k c o d i n g J I E E E T r a n s a c t i o n s o n I n f o r ma t i o n T h e o ry， 2 0 0 3， 4 9 ( 2 ) ： 3 7 1 -3 8 1 7 Ho n g Y， X u J ， J i a n g C L i f e t i m e m a x i mi z a t i o n i n w i r e l e s s s e n s o r n e t w o r k s w i t h n e t w o r k c o d i n g C P r o c e e d i n g s o f Wi C O M 2 0 0 7 ， S h a n g h a i ， Ch i n a ， 2 0 07： 2 5 2 7-2 5 3 0 8 Wu Y， C h o u P A， K u n g S Y Mi n i m u m- e n e r g y mu l t i c a s t i n m o b i l e A d H o c n e t w o r k s u s