（信号与信息处理专业论文）基于免疫算法的有向传感器网络目标覆盖研究.pdf

哈尔滨t 稃大学硕十学位论文 摘要 随着传感器技术 计算机技术 信号处理技术的发展 无线传感器网络成为人们 研究的热点 由于硬件的限制 无线传感器网络由许多带有有限能量的节点组成 并 被随机部署在监测区域内 其中的传感器节点具有监测 数据采集 无线通信的能力 以往的传感器网络中的传感器节点的感知模型都是全向型的 即感知范围为一个圆域 但甥琰中存在一种有向型的传感器 它们在不同的方向上具有不同的感知能力 其感 知范围是一个扇形 且其感知方向可以变化 因此 以往对于全向型传感器网络的研 究成果完全不适用于有向传感器网络 需要人们找到新的解决办法 覆盖问题是传感器网络研究的基本问题 主要有区域覆盖 目标覆盖等 目前人 们的关注焦点都是区域覆盖 对于目标覆盖的研究还很少 本文旨在针对有向传感器 网络的目标覆盖问题进行研究 即在一个区域中随机分布大量的传感器与目标点 在 对有向传感器构建数学模型后 采用免疫算法进行组合优化选择 选择最少数量的传 感器覆盖全部的目标点 从而节省硬件成本 延长网络生存时间 本文首先介绍了有向传感器网络的概念与基本理论 并给出了传感器的0 1 感知 模型和概率感知模型 基于o 1 感知模型 本文采用免疫算法 n 包括免疫规划算 法 i p f l 克隆选择算法 c s a 在相同的网络参数条件下进行仿真实验 并将得到的结 果与目前解决效果最好的遗传算法进行比较 在概率感知模型下 考虑到搜索时间和 算法的稳定性 本文采用免疫规划算法进行仿真实验并分析得到的结果 最终通过仿 真实验证明 免疫规划算法和克隆选择算法能有效的解决有向传感器全目标覆盖的问 题 并且要优于目前效果最好的遗传算法 同时 免疫规划算法对于概率感知模型下 的目标覆盖也是有效的 关键词 有向传感器网络 目标覆盖 免疫算法 概率感知模型 哈尔滨t 程大学硕十学位论文 a bs t r a c t w i t ht h ed e v e l o p m e n to ft h es e n s o rt e c h n o l o g y c o m p u t e rt e c h n o l o g y s i g n a lp r o c e s s i n g t e c h n o l o g y w i r e l e s ss e n s o rn e t w o r k s w s n b e c o m e sam a j o rc o n c e r ni nr e s e a r c hf i e l d f o r t h el i m i t a t i o no ft h es e n s o rh a r d w a r e s w s nc o n s i s t so fal a r g en u m b e ro fs e n s o r sw i t h l i m i t e dp o w e rw h i c ha r er a n d o m l yd e p l o y e di nac e r t a i na r e a t h es e n s o rn o d e sa r ec a p a b l e o fm o n i t o r i n g d a t ag a t h e r i n g w i r e l e s sc o m m u n i c a t i o n s f o r m e rs e n s i n gm o d e lo fs e n s o rn o d e si nw s ni so m n i d i r e c t i o n a l w h o s es e n s i n ga r e a i sar o u n d b u ti nr e a l i s t i cc o n d i t i o nw eh a v ea n o t h e rk i n do fs e n s o rn o d e sw h i c hh a v e d i f f e r e n ts e n s i n gc a p a b i l i t i e si nd i f f e r e n ts e n s i n gd i r e c t i o n s a n di t ss e n s i n gr a n g ei sas e c t o r w h o s ed i r e c t i o nc a l lb et u r n e d s of o r m e rr e s o l v e n t si no m n i d i r e c t i o n a lw i r e l e s ss e n s o r n e t w o r k sd o n ta d a p tt ot h ed i r e c t i o n a lw i r e l e s ss e n s o rn e t w o r k s f o rw h i c hw en e e dt o p r e s e n t n e wr e s o l v e n t s c o v e r a g ei s s u ew h i c hc o n s i s t so fa r e ac o v e r a g e t a r g e t sc o v e r a g ea n d s oo ni s f u n d a m e n t a la n d c r u c i a li nt h er e s e a r c ho fw s n n o wp e o p l ep a ya t t e n t i o nm o s t l yt ot h e a r e ac o v e r a g e a n dt h er e s e a r c h si nt a r g e t sc o v e r a g ea r es c a r c e t h et h e s i sf o c u s e so nt h e t a r g e t sc o v e r a g ei nd i r e c t i o n a ls e n s o rn e t w o r k s w i t ht h ev a s ts e n s o r s a n dt a r g e t sw h i c ha r e r a n d o m l yd e p l o y e di na na r e a w ec r e a t em a t h e m a t i cm o d e l i n go fd i r e c t i o n a l s e n s o r sa n d c h o o s es e n s o r sa sf e wa sp o s s i b l et h a tc a nm o n i t o ra l lt h et a r g e t s s ow ec a ne c o n o m i z et h e c o s to fh a r d w a r e sa n da l s op r o l o n gt h el i f eo fd i r e c t i o n a ls e n s o rn e t w o r k s w ei n t r o d u c et h ec o n c e p t i o na n dt h ee s s e n t i a lt h e o r i e so fd i r e c t i o n a ls e n s o rn e t w o r k s f i r s ti nt h et h e s i s a n da l s od i s c u s st h e0 1s e n s i n gm o d e la n dt h ep r o b a b i l i t ys e n s i n g m o d e l b a s e do nt h e0 1s e n s i n gm o d e l w eh a v es i m u l a t i o ne x p e r i m e n t sa t t h es a l t l e p a r a m e t e r so fd i r e c t i o n a ls e n s o rn e t w o r k sw i t hi m m u n ea l g o r i t h m i a w h i c hc o n s i s t so f i m m u n ep r o g r a m m i n ga l g o r i t h m i p a n dc l o n es e l e c t i o na l g o r i t h m c s a a n dt h es i m u l a t i o n r e s u l t sa r ec o m p a r e dw i t hg e n e t i ca l g o r i t h m i n t h e p r o b a b i l i t ys e n s i n g m o d e la n d c o n s i d e r i n gt h es e a r c h i n gt i m ea n ds t a b i l i t yo fa l g o r i t h m s w ea d o p ti l t l n l u n ep r o g r a m m i n g a l g o r i t h m a n dt h e na n a l y s et h es i m u l a t i o nr e s u l t s s i m u l a t i o ne x p e r i m e n t ss h o w t h a ti pa n d c s aa r ev a l i df o rt a r g e t sc o v e r a g ei nd i r e c t i o n a ls e n s o rn e t w o r k sa n db e t t e rt h a ng e n e t i c a l g o r i t h m a l s oi pi sv a l i df o rt a r g e t sc o v e r a g ei np r o b a b i l i t ys e n s i n gm o d e l k e yw o r d s d i r e c t i o n a ls e n s o rn e t w o r k s t a r g e t sc o v e r a g e i m m u n ea l g o r i t h m p r o b a b i l i t y s e n s i n gm o d e l 第1 章绪论 第1 章绪论 1 1 课题研究的目的及意义 无线传感器网络的覆盖能力是网络性能的一个重要衡量指标 目标覆盖是覆盖问题 的一个主要方面 但相比于区域覆盖人们对此研究的还很不够 随着网络技术的发展 以有向感知模型的传感器组成的网络越来越引起人们的关注 并在实际应用中逐渐发挥 作用 所谓的 有向感知模型 d i r e c t i o n a ls e n s i n gm o d e l 就是其传感器节点的感知范围 是一个以节点为圆心 半径为其感知距离的扇形区域 它们在任意时刻只能工作在一个 方向上 在其他方向上不具有感知能力 工作方向是一个有限角度的扇形 因此 有向 传感器的覆盖区域是由其位置与工作方向共同决定的 全向型仅由位置决定 不同的 方向互相重叠 需要调整传感器的工作状态 工作或休眠 和调整传感器的工作方向 从而用最少数量的传感器实现覆盖要求 如覆盖区域最大 覆盖全部目标点 延长网络 生存时间等 与常用的全向感知模型相比 有向感知模型不仅能满足某些因硬件限制使 感知模型为扇形的传感器的感知特性 而且还具有节省能耗 延长网络生存时间 节约 成本等优点 但是感知模型的差异造成了现有基于全向感知模型的覆盖问题的研究成果 不能直接应用于有向传感器网络 迫切需要设计出一系列新方法 解决有向传感器网络的 目标覆盖问题 有向传感器网络的目标覆盖已被证明是一个n p 完全问题 以全部目标 被覆盖为前提 目前已有人用遗传算法进行了初步探索f l 并取得了较好的效果 但在 实时性上还有很大的不足 并且易陷入局部最优 算法性能不够稳定 目前 由于传感器网络通常工作在复杂的环境下 而且网络中传感器节点众多 因 此大都采用随机部署方式 但是随即部署方式不可能一次性将传感器合理的部署于网 络区域中 会形成大量的冗余传感器和感知区域的重叠 因此需要我们研究如何能最大 限度的有效利用传感器 即用最少数量的传感器实现覆盖要求 目f j 由于有向传感器网络是从无线传感器网络发展出来的新的研究领域 人们对 此研究的还很不够 并且 就研究方向而言绝大多数文章集中于覆盖问题中的区域覆盖 网络的连通性和网络生存时间上 对于覆盖问题中的目标覆盖关注的很少 在目标覆盖 中 有的文章用到分布式算法 这样可以减少算法的计算量 提高实时性 其覆盖率与 算法的复杂度成正比 可是 造成的直接后果是有些目标点没有被覆盖到 在大部分现 实情况中都可以满足覆盖要求 但在某些特殊的情况下 比如战场对敌人的监控或自然 哈尔滨t 程大学硕十学何论文 灾害监测等 如果有覆盖遗漏 那么后果是灾难性的 目前 国内外已有学者开始了对 于全目标覆盖的研究 但成果较少 发表的相关文献不超过1 0 篇 且优化效果较差 网络覆盖规模也很小 因此对该问题的研究具有前沿性和必要性 本文旨在针对大量传感器和目标点随机部署后的有向传感器网络目标覆盖问题进 行深入研究 目的是寻找最少数量的传感器来覆盖全部的目标点 为此本文在构建有向 传感器的数学模型基础上 采用人工免疫算法中的免疫规划算法和克隆选择算法 解决 在0 1 感知模型和概率感知模型条件下的全目标覆盖问题 这样不仅能节省硬件成本 还可以合理分配网络的空间资源 更好地完成环境感知 信息获取任务以及提高网络生 存能力 1 2 国内外研究现状 无线传感器网络是随着无线通信技术 嵌入式计算技术 传感器技术 分布式信息 处理技术的进步而发展起来的一种新兴的信息获取技术 是涉及多学科高度交叉 知识 高度集中的前沿热点研究领域 对于它的研究兴起于2 0 世纪9 0 年代 进入2 1 世纪后 更加引起人们的广泛兴趣 美国最早开始了无线传感器网络的研究工作 并首先应用于 军事领域 目前 美国很多的大学和研究所都在从事传感器网络的研究 著名的有加州 大学伯克利分校 u c b u n i v e r s i t yo f c a l i f o m i a b e r k e l e y 的b w r c 研究中心和w e b s 研究项目 哈佛大学 h a r v a r du n i v e r s i t y 的c o d eb l u e 项目 斯坦福大学 s t a n f o r d u n i v e r s i t y 的w s n l 实验室等 在国内 也已经有许多机构着眼于传感器网络的研究 较早进行相关研究的有中科 院研究所 软件所 哈尔滨工业大学 清华大学 北京大学 上海交大 北京交通大学 等 国家自然基金会从2 0 0 3 年期也设立了传感器网络研究的相关课题 并在随后将其 列为重点项目 对于无线传感器网络的研究方向主要有网络覆盖 网络连通性 网络生存时间等 通常情况下 传感器被大量的高密度的随机部署于待监测区域 为了保证覆盖质量 网 络连通性 以及网络生存时间等要求 必须要有很高的冗余度 网络生存时间问题是人 们重点关注的一个方面 对于生存时间的解决方法主要的思想是 将网络中的所有传感 器划分为若干集合 子集 每个集合都能完成覆盖要求 在任意时刻只有一个子集处 于工作状态 其他子集都处于休眠状态 各个子集轮流工作 可以有效的延长网络生存 时间 可以将无交点子集问题归结为n p 完全的s e t c o v e r 覆盖集 问题 2 1 文献 3 不要求节点只能隶属于一个集合 可以出现在多个子集之中 同时为每个子集分配工作 2 第1 章绪论 时间 总和不大于单个节点的生存时间 目的是使各节点集合的工作时间之和 即网络 生存时间 最大 同时提出了一个在不用知道位置信息的基于最小子集的图论方法 它 利用大量传感器的冗余性 找出许多满足覆盖条件的传感器子集 因此每一个子集都能 具有很高的区域覆盖度 从而最大限度的扩展网络生存时间 与之相似的有文献 4 中的 e s s c 利用了s p o n s o r e ds e c t o rc o v e r a g e 概念 也有效的延长了网络生存时间 并且具 有高度的区域覆盖率 l d a s t s j 分析了相邻传感器覆盖区域中的冗余性 可以在没有位置 信息和方向信息的情况下对其进行计算 通过交替的关闭冗余节点延长网络的生存时 间 对于覆盖问题 文献 6 在网络中的传感器于初期部署后 应用模糊理论系统调整传 感器的位置对网络进行优化 进而增强传感器网络的工作效率 当每一个传感器都被固 定在一个工作方向时 文献 7 分析了其区域的覆盖率 传感器有有向的天线时 文献 8 同时分析了其区域覆盖和网络的连通性 它推导出区域覆盖和连通性是一个传感器活跃 概率的函数 此函数仅仅取决于网络本身的拓扑结构 也有使用网格节点的调度算法 使用网格点近似划分覆盖区域 在从传感器中选择尽量少的节点覆盖全部的网格点 一 般使用近似算法或线性规划算法等 s 4 0 l 利用无向图的概念 文献 1 1 1 4 从支配集的角度 研究了覆盖问题 构建一个连通区域支配集 减少了传感器工作节点数 节省了网络能 量从而延长网络生存时间 在网络生存时间上面 文献 1 5 i 正n 了构造无交集的传感器 子集是一个n p 完全问题 并提出了基于混合整数规划的启发式算法 文献 1 6 1 7 对此 进行了扩展 不限制子集之问不可交叉 即可以有传感器节点隶属于不同的子集 提出 了基于线性规划的启发式和贪婪算法 在区域覆盖中 文献 1 8 在事件的漏报概率和误报概率的前提下 定义节点的感知 区域 再使得节点互相协调 保证低于误报率和漏报率阈值的情况下扩大感知区域 文 献 1 9 提出了一种分层 非对称下的一致化感知覆盖构架 u s e n s e 此构架中普通节点 的状态可以切换 用集中式算法实施全局的覆盖调度 同时可以支持其他多种覆盖控制 算法 文献 2 0 首次提出了传感器网络的栅栏覆盖模型 主要考虑的是当移动目标穿越 传感器网络覆盖的区域中时 网络对此移动目标检测到的概率大小 针对某些需要多重 覆盖的情况 文献 2 u 考虑了k 覆盖问题 即在传感器网络覆盖范围中 待检测区域或 待检测目标点被至少k 个传感器同时覆盖 当对覆盖率要求不是很高时 文献 2 2 设计 出了启发式算法 选择具有最小 势 的工作点集合完成覆盖要求 但以上的研究仅仅 针对网络的覆盖效果 没有同时兼顾到覆盖后网络中传感器的连通性 为此 文献 2 3 讨论了在满足覆盖要求的前提下 如何保证连通性 证明了通讯半径与感知半径相等时 哈尔滨丁程犬学硕十学位论文 网络覆盖的同时也能具有连通保证 在此证明的基础上 提出分布式位置信息节点几何 密度控制算法o g d c 对于目标覆盖中的k 覆盖问题 文献 2 4 将k 覆盖前提条件应用到栅栏覆盖上 当 一个目标通过网络的覆盖区域时 保证至少有k 个传感器能检测到它 并且持续监控直 到此目标离开网络监控区域 文章给出了如何找出最少数量传感器节点满足k 覆盖要求 的算法 在对有向传感器网络的研究中 关于有向传感器网络的覆盖问题 文献 2 5 首次提 出了有向传感器网络的概念 并且同时研究了此类型传感器网络的部署策略和连通性问 题 文献 2 6 在传感器工作方向可旋转的模式下 提出了在给定覆盖度下的节点数量估 计方法 使用感知连通子图 s c s g 将网络划分为若干部分 这样可以有效降低算法 的时间复杂度 但网络成本较高 文献 2 7 提出离散目标的最少节点最大覆盖 m c m s 问题 即寻找最少的节点覆盖最多的目标 用到了整数线性规划法 集中式贪婪算法和 分布式贪婪算法 文献 2 8 1 研究了有向传感器网络模式下的栅栏覆盖问题 利用 f o v v o r o n o i 图给出了一种集中式算法 监测质量较高 但计算方法复杂 传输量较高 文献 2 9 提出了有向多覆盖集问题 m d c s 并证明其是n p 完全问题 利用混合整数 规划方法提出了几种集中式的启发式算法 总之 目前对于有向传感器各种覆盖问题的研究尚处于起步阶段 尤其对于全目标 覆盖问题的研究成果较少 且还不够理想 为此有必要对此进行深入的研究 本文将以 此为研究对象 通过引入人工免疫算法 解决有向传感器的覆盖问题 目前基于人工免 疫算法的解决方案尚没有文献发表 1 3 本文主要研究内容和章节安排 本课题属于基础应用研究 重点研究有向传感器网络中的目标覆盖问题 在网络区 域中随机部署大量传感器节点和若干目标点 利用人工免疫算法中的免疫规划算法和克 隆选择算法这两种集中式优化算法寻找最少数量的传感器覆盖全部的目标点 再将这两 种算法的仿真结果和遗传算法进行对比 针对仿真结果分析理论原因 对于更符合实际 情况的概率覆盖模型 免疫规划算法也是适用的 我们利用免疫规划算法进行仿真实验 并分析其性能 为此本论文的具体内容安排如下 第1 章为绪论 首先介绍了课题研究的目的和意义 说明了本课题的实际应用价值 然后介绍了课题的国内外研究现状 综述了无线传感器网络不同研究领域已有的研究成 4 第1 章绪论 果 并分析其优点或不足 然后探讨了有向传感器网络的目标覆盖问题 指出了本课题 研究的方向 第2 章 简要概述了无线传感器网络的基本概念 并详细介绍了无线传感器网络的 相关理论知识 如网络结构 网络特性 节点部署和节点感知模型 网络覆盖要求等 然后介绍有向传感器网络的结构 特点等基本概念 并针对课题的研究性质 确定了有 向传感器的覆盖模型和重要的参数 第3 章 介绍了人工免疫算法相应的基本理论 由于本课题采用的算法是人工免疫 算法中的免疫规划算法和克隆选择算法 因此本章对它们分别进行了深入的探讨和分 析 给出它们的理论框架和算法流程 第4 章 针对有向传感器网络覆盖问题的特点 构造有向传感器的数学模型 提出 了新的概念 方向覆盖矩阵 解矩阵 并在此基础上 与免疫规划算法和克 隆选择算法相结合 针对两种不同的算法给出其优化原理和操作方式 实现过程 引 入概率感知模型增加了课题的难度 根据其特点 决定采用免疫规划算法 并给出了算 法的优化方式 第5 章 首先在0 1 感知模型下 利用免疫规划算法和克隆选择算法在相同的网络 参数条件下 对有向传感器网络目标覆盖问题进行仿真实验 然后将其结果与目前应用 效果最好的遗传算法进行比较分析 同时 在概率感知模型的条件下 利用免疫规划算 法进行仿真实验 观察其结果 并分析其性能 最后本文将总结归纳本人对于有向传感器网络目标覆盖问题所做的工作与得到的 成果 并对其不足和今后的发展进行展望 哈尔滨t 稗大学硕十学位论文 i i i i i i i 置i i i i i i i i i i 葺i i i i i i i i i i i i i 一 i h i i i i i i i i i i i i i i i i i i i 宣i i i i i i i i i i 第2 章无线传感器网络的相关理论知识 2 1 无线传感器网络 无线传感器网络是随着无线通信技术 嵌入式计算技术 传感技术 分布式及集中 式信息处理技术等发展而发展出来的一种信息获取和处理技术 是近几年 直高速发展 中的继i t 技术发展高潮后的的又一技术发展高潮 其主要特点是多学科交叉融合 知 识高度集成 且均为前沿学科热点研究领域l 3 0 3 5 1 无线传感器网络中的传感器具有体积 小 价格便宜 能耗低 支持短距离无线通信等特点 由这些传感器所组成的系统具有 数据采集 数据处理 数据传输等功能 无线传感器网络是由大量的传感器组成的覆盖 区域 能对此区域中的不同地区 目标进行感知和对感知到的数据进行简单的处理及传 输通信 目前其应用范围越来越广泛 如军事侦察 目标监控 环境监测 空间探测 城市交通 智能家居等 在可以预测的未来 其应用范围还会继续扩大 随着其应用的 逐渐深入 必将惠及人类生活的各个方面 7 无线传感器网络覆盖问题 就是通过网络中分布的传感器节点对已知区域中的地区 或 目标点实现物理信息的感知及处理 并将其转换成数字信息 通过无线通信技术传送 到基站或汇聚节点 是通过传感器网络实现对物理世界的感知 也是人们对其研究的根 本目的 2 1 1 无线传感器网络的结构 无线传感器网络通常包括传感器节点 汇聚节点 工作站 基站 文献 3 8 给出 了传感器网络的基本结构图 图2 1 为同构无线传感器网络 图2 2 为异构无线传感器 网络 同构型传感器网络中大量传感器节点随机部署在某个区域中 构成无线网络 各 个传感器节点所采集到的数据通过无线通信汇聚到汇聚节点 其中传感器既要采集数据 又要传输数据 汇聚节点再将数据传输到基站 人们可以通过基站对区域内的传感器进 行操控 异构型传感器网络中有不定数目的汇聚节点 以一个或多个汇聚节点为核心 在其周边的传感器节点同此汇聚节点共同构成子网 并且事先规定好通信协议 汇聚节 点之间也有通信协议 但不同于传感器节点 其中离基站最近的汇聚节点为主汇聚节点 负责与基站进行通信 6 第2 章无线传感器网络的相关理论知识 图2 1 同构犁传感器网络结构图 甏线转感器謦焱 管瑷工作姑 图2 2 异构型传感器网络结构幽 2 1 2 无线传感器网络的特点 无线传感器网络通常都是针对具体情况进行针对性设计的 不同于常见的通信网 络 无线局域网络 从而有其自身的特点 通常其节点数目极为庞大 分布更为密集 在某些人类不易或情况不允许进入的区域采用抛洒等随机分布方式部署大量的传感器 节点对此区域进行数据采集和监控等 并且由于很难对传感器进行更换还要考虑其网络 生存时间的问题 因此就要合理的对传感器进行操控 分清工作传感器和休眠传感器 在满足覆盖要求的情况下 尽可能利用少量的传感器满足覆盖要求从而延长网络生存时 哈尔滨t 稃犬学硕 学位论文 间 无线传感器网络的主要特点如下 1 超大规模 在一个区域内 无论是区域覆盖还是目标覆盖 为了不出现盲区或遗漏目标点 必 须极为密集的分布大量的传感器节点 从而满足要求 并且由于可能在某个区域中无法 更换传感器 就需要把传感器分成许多的不同子集 满足覆盖要求 当一个子集中的 传感器能源耗尽无法继续工作时 就启动下一个子集接替 从而最大的延长整个网络的 生存时间 因此需要有大量的冗余传感器节点 构造多个子集 2 能量受限 无线传感器一般体积很小 其能源由自身的电池提供 因此本身的能量有限 在很 多情况下 传感器部署在情况极为恶劣的环境下 无法人为的更换电源 所以只能有一 次性的使用机会 这样就需要人们在对传感器进行硬件选择和软件设计上就要考虑低功 耗或电源效率问题0 9 4 0 i 3 网络自组性 有的时候无线传感器网络并不是用的中心控制模式 即没有严格意义上的控制中 心 各个节点地位平等 并且节点可以随时加入或退出网络 单个节点的故障不会影响 网络的总体运行 因此节点必须具备自组织能力 在部署完毕后 通过集中或分布式算 法调整节点的工作状态 进而独立构成完整网络 此时整个网络也就具有自适应性 可 以适应一些任务变化的要求 4 网络动态性 无线传感器网络是一个动态的网络 节点可以自由进入或离开 或者人为的操纵节 点使之处于工作或休眠状态 这都可以使网络的拓扑结构发生变化 此时网络具有很强 的动态变化性 因此 网络必须具有可重构 可调整性 即动态拓扑组织功能 5 多跳路由 有时候传感器节点的通信半径受限 这样就不可能与基站直接进行通信 如果需要 数据传递 那么就要与邻居节点通信 通过多跳路由的方式 通常没有专用的路由设备 多跳路由传输由传感器节点独自完成 因此网络中每个节点要有既能采集信息也能传输 信息的能力 2 1 3 无线传感器网络覆盖要求 无线传感器网络的覆盖是指 在区域内分布大量的传感器节点 通过这些节点对此 区域内的某些地区或目标点进行检测 并且采集相关的数据信息 进而传输到基站进行 8 第2 苹无线传感器网络的相关理论知识 处理 对地区或目标的覆盖是无线传感器网络的重要功能之一 反映了此网络对物理世 界的感知能力 4 网络中单一节点的感知能力有限 因此需要多个节点的合作才能实现 对网络区域的有效感知 其中涉及到节点的感知模型和空间分布方式等前提条件 直接 影响到网络的覆盖质量f 4 2 考虑覆盖要求的不同 无线传感器网络的覆盖模式可大致分为三类 1 区域覆盖 区域覆盖的含义是指某个待监测区域需要被至少一个传感器监控到 即整个待监测 区域都能被若干传感器节点感知 删 2 目标覆盖 也可被称为点覆盖 即区域内分布有许多离散的目标点 每一个目标点能被网络中 的至少一个传感器感知至u 4 6 4 7 3 栅栏覆盖 栅栏覆盖主要关注的是传感器网络对进入或离开网络区域中的目标点进行感知的 能力 对移动中的目标点也要能进行实时感知 并且侦测概率要满足一定条件h 8 4 9 图2 3 为三种覆盖的示意图 监测区域 目标 监游区域 目标移动路径监铡区域 二麓 a 区域覆盏 b 目标覆盖t c 嚣栏覆盖 图2 3 三种覆盖情况 针对覆盖问题的解决算法可以大致分成两类 1 分布式算法 分布式算法的主要思想是 每一个传感器根据自身位置信息及其周围的局部信息 包括邻居节点 决定其工作状态 通常网络中的传感器都要不断的获得周围局部的信 息 再根据自身的状态 如是否有目标 所剩能量 是否冗余等 不仅要决定当前的工 9 哈尔滨1 稃大学硕十学能论文 一 一 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 作状态 还要当网络出现突发情况时能实时反应 保持网络的覆盖质量 分布式算法相 对来讲计算复杂度较小 算法实时性较好 但分布式算法也有很大的缺点 传感器之间 要不断的交换信息 信息的处理都在每个传感器内部进行 这样需要消耗很多的能量 不利于传感器的持续工作 对网络的生存时间造成不良影响 并且每一个传感器只能获 取局部信息 不能根据全局的情况判断问题 这样就造成了某种程度上的信息缺失 进 而可能会出现过度冗余或目标覆盖率偏低的情况 2 集中式算法 集中式算法的特点是 所有节点的位置信息都被汇总集中处理 通常由基站获取全 部的信息 在此基础上基于全局进行统筹规划 基站对所有节点统一进行管理 按照覆 盖要求操控不同节点的工作状态 其主要优点是从全局的角度分析问题 计算结果比分 布式算法更为精确 其缺点是对传感器的通信能力要求很高 这样才能把数据传输给基 站 因为所有传感器都要把自身的信息传递给基站 这样造成网络通讯流量的很大负担 需要网络基站具有很高的数据实时处理能力 2 1 4 无线传感器网络节点部署 无线传感器网络的节点部署方式能影响甚至决定网络的拓扑结构 连通性 覆盖质 量以及网络生存时间等特性 其部署方式主要有三种 确定性部署 随机部署 移动部 署 1 确定性部署 确定性部署也叫可控部署 人们可将传感器节点放到网络区域中的指定位置 从而 用最优的部署方式满足人们对网络覆盖的需要 确定性部署的前提条件是整个网络应用 环境固定 并且网络状态和涉及到的参数已知 这样人们可以按照网络的覆盖要求 部 署传感器节点检测目标区域或目标点 但是这种节点部署方式只能适用于某些确定的场 合 对于人们认识不清或无法探知的区域无法应用 2 随机部署 在许多实际的自然环境中 网络环境无法预知 甚至不适于人类进入 无法应用确 定性部署 并且网络自身的拓扑结构可能随着时间而变化 网络中的节点覆盖情况也要 随之变化 所以也不使用确定性部署 此时 通过随机抛洒的方式 将传感器节点分布 于网络区域中 虽然不知道网络的环境 但是由于有大量冗余的节点 仍可以满足覆盖 要求 当前 在传感器覆盖问题研究中 随机部署方式下的覆盖是研究热点 通常有两种 1 0 第2 章无线传感器网络的相关理论知识 情况 一种是传感器节点随机部署后无法移动 另一种是传感器节点部署后可以移动 也称动态网络覆盖 3 移动部署 出于需要 在传感器网络中引入移动节点 当这些节点部署在网络环境中后 部分 或全部节点可以自由移动 但要受到能量和算法控制的限制 这样可以减少传感器节点 部署的随机性引起的覆盖质量偏低 弥补静止节点覆盖能力的不足 还可以对网络进行 后期调整 带来很大的灵活性 只是对算法的要求较高 因此造成算法非常复杂 会过 多的消耗传感器自身的能源 2 1 5 无线传感器网络节点的感知模型 传感器网络的特性不仅与覆盖要求和节点部署方式有关 还取决于节点的感知模 型 节点的感知模型决定于节点的硬件特性 反映了传感器硬件的物理感知能力 常见 的感知模型有两种 一种是二元感知模型 一种是概率感知模型 1 二元感知模型 二元感知模型又叫做o 1 感知模型 即当目标区域或目标点在传感器的感知范围内 时 被感知到的概率恒为1 不在感知范围内时 被感知到的概率为0 湖 在前人的研 究中 最常用到的o 1 感知模型是圆盘模型 球感器的感知范围是以节点为圆心 半 径为 的圆盘 假设节点j 的坐标为 j 节点感知半径为 目标点p 的坐标为 n p 则节点与目标点的距离公式为 d s p s 一p 2 s 一p y 2 若距离d s p 小于 或等于节点s 的感知半径 则目标点p 被覆盖 记为c s p 1 否则不被覆盖 c s p 0 如公式 2 一1 所示 fl d s p 2 1 1 c s p 21 0o t h e r w i s c 2 概率感知模型 o 1 感知模式是对传感器节点感知能力的抽象化与理想化 只能提供理论研究的依 据 在实际情况中 由于传感器自身特性或者外界环境的影响 如是否有噪音 通信信 号强度 使得节点对目标感知的能力与其与目标的距离有很大关系 通常来讲 目标 越靠近节点信息采集越完整 节点感知概率越大 目标离节点越远感知的效果越差 节 点感知概率越小 并且随着距离的变化 感知概率是一个渐变的过程 不存在突变现象 1 5 1 1 最常见的概率感知模型是指数概率模型 如公式 2 2 所示 c c j p c t 口dc s p 卢三 囊 三毒 c 2 2 口 为反映感知强度随目标与节点距离衰减程度的参数 2 2 有向传感器网络 传感器网络的覆盖问题一直是传感器研究的热点之一 国内外学者相继对其进行了 深入的研究并使其得到了广泛的应用 以往的研究主要是基于全向感知模型 即节点的 覆盖范围是以节点为圆心 感知半径为 的圆形 但现实中有一类传感器 其感知范围 并不是圆盘型 而是以传感器节点为圆心 感知半径为 的扇形区域 称为有向传感器 如视频传感器 超声波传感器 红外传感器等 s 2 5 4 1 由这些有向传感器组成的网络系统 就称为有向传感器网络 有向传感器的感知范围受限 只有在其工作方向上才能有效感知 而在其他方向上 无感知能力 当网络中分布了大量的有向传感器时 周围有需要被感知的目标区域或目 标点 人们不仅要通过算法判定此传感器应该处于何种工作状态 如工作 休眠 还 要在此传感器工作的前提下决定工作在哪个方向上 因此 有向感知型传感器网络的覆 盖算法计算更为复杂 并且以往的基于全向感知型传感器网络的覆盖算法不能直接应用 在上面 一 一 有向型传感器不同于以往的全向型传感器的主要方面是当其工作时 传感器的覆盖 区域不是一个圆域而是一个有限角度的扇形域 因此 一个有向型传感器可选择的工作 方向数取决于其感知角度的大小 从理论上说 一个有向传感器可以在3 6 0 度范围内自 由旋转 也就是有无限多个工作方向 但联系实际硬件情况和便于理论研究 本文设定 一个有向型传感器的工作方向是固定的 即一个传感器的感知角度为口时 那么它就有 2 个工作方向 每个工作方向一旦固定就不能旋转 本文中感知角度口为9 0 度 因 此一个传感器有4 个可选的工作方向 分别对应坐标系的4 个象限 且方向固定不可转 动 一个有向传感器只的四个方向 可以看做坐标系的四个象限 如图2 4 所示 分别 为4 d 2 以 以 当传感器工作时 只能在这四个方向上选取一个工作方向 此时 在其他的方向上没有感知能力 也就是说 只有当目标点存在于工作方向中时才能被感 知 否则即使在其他可选方向中也不能被感知到 在算法仿真中 有向传感器的感知半 径可变 感知模型有二元感知模型和概率感知模型两种 第2 章无线传感器网络的相关理论知识 图2 4 为感知角度为9 0 度的有向传感器的典型模型 厂 弋 弋一 夕 图2 4 有向传感器的典型模型 有向传感器的硬件模型已经给出 在此基础之上 本文要用这些有向型的传感器实 现目标覆盖的目的 即a t c a l lt a r g e t sc o v e r a g e 全目标覆盖问题 也就是在一个区 域中随机且密集大量的分布传感器和目标点 选择最少数量的传感器覆盖此区域中全部 的目标点 用到的基本参数有 第m 个目标点 整个区域中有m 个目标点 第i 个传感器 整个区域中分布n 个传感器 a 目标点的集合 a 函1 a 2 a 3 a m s 传感器的集合 s h 是 邑 4 传感器s 的第j 个方向 1 f n l 4 口 感知角度 本文统一为9 0 度 感知半径 传感器感知半径与硬件特性相关 2 3 本章小结 本章首先介绍了无线传感器网络的基本概念和网络特性 主要从网络结构 节点部 署 感知模型等方面介绍了无线传感器网络的知识 然后 本文再介绍了有向传感器网 络的概念与知识 有向传感器网络的广泛应用是一种必然趋势 它的出现将会给人类社 会带来极大的变革 因此 对其进行深入的研究和探讨具有很高的理论和实际价值 哈尔滨t 程入学硕十学位论文 第3 章人工免疫算法弟3 草人上兕7 殳异法 3 1 人工免疫算法概述 人工免疫系统 a r t i f i c i a li m m u n es y s t e m 简称a i s 是继人工神经网络 遗传算 法和蚁群算法之后 又一从生物中获得灵感 用于解决优化问题的生物启发式算法 是 生命科学和计算机科学相结合而形成的智能算法 免疫算法是基于免疫学理论和生物免 疫系统机制而提出的 是对生物免疫机理的一种模拟 并受到遗传算法的启发 因此免 疫算法与遗传算法有相似之处 1 9 7 4 年 美国诺贝尔奖获得者j e m e 率先提出了免疫网 络理论而引起人们的关注 之后f a r m e r p e r e l s o n b e r s i n i v a r e l a 等免疫理论学者分别 在1 9 8 6 年 1 9 8 9 年和1 9 9 0 年发表了有关论文 在免疫系统启发实际工程应用方面做出 了突出贡献 为建立有效的基于免疫原理的计算系统和发展智能系统开辟了道路 日本 学者i s h i d a 在1 9 9 0 年利用免疫系统解决了传感器网络故障诊断问题 是目前可查的最 早的免疫系统在工程领域的研究成果 美国学者f o r r e s t 在1 9 9 4 年将免疫系统理论用于 计算机安全和病毒检测 取得了成功 随后越来越多的人注意到p e r e l s o n b e r s i n i v a r e l a 等免疫理论学者所做早期研究工作的重要性 人工免疫系统的应用领域由此不断得到扩 大 时至今日 尽管免疫算法还存在许多缺陷 但经过研究人员不断地改进 应用 目 前己成功应用于机器学习 异常和故障诊断 机器人行为仿真 机器人控制 网络入侵 检测 神经网络设计 参数优化 工业设计和工业生产等领域 并表现出较好的性能和 效率 生物免疫系统是抵抗细菌 病毒和其它致病因子入侵机体的基本防御系统 作为生 物的重要系统之一 免疫系统具有免疫防御 免疫自稳 免疫监视功能 它不需要神经 系统和大脑的参与 可独立完成对各种抗原的识别和抵抗 同时自觉地保持自身的稳定 性 通过免疫应答 免疫调节 免疫记忆等过程 高效地完成其复杂而重要的任务 使 机体在充满各种各样有害细菌和病毒的环境中得以生存 因此生物免疫系统是一个复杂的自适应系统 它不依靠任何中心控制 具有分布式 任务处理能力 具有在局部采取行动的智能 它通过具有交流作用的化学信息构成网络 进而形成全局概念 由于生物免疫系统的复杂性和多功能性 使得人工免疫系统的生物 学基础是多样的 比如免疫网络 克隆选择理论 阴性选择等 目前基于这些生物免疫 学理论或机制己开发出多种形式的算法模型 因此免疫算法不同于以往的生物启发式算 法 它没有统一的启发源模式 利用生物免疫系统的某一方面机制或原理就可以设计新 1 4 第3 章人 丁免疫锝法 算法 因此从广义角度而言 人工免疫系统就是基于生物免疫系统理论而提出的多个算 法的统称 目前免疫算法主要包括人工免疫网络模型和人工免疫算法两大方面 人工免疫网络模型主要是指在模拟细胞交互 免疫网络动态行为的基础上建立起来 的各种网络模型 如独特型网络模型 抗体网络模型 多值免疫网络模型 免疫联想记 忆模型和互联耦合网络模型等 免疫网络模型强调网络结构中各节点之间的信息通讯和 相互作用 以及其所形成的动态平衡性 人工免疫算法模拟生物免疫系统的识别 学习 进化等免疫原理和机制 针对不同 应用领域设计出各种算法模型 人工免疫算法强调免疫系统的智能学习机制 目前已成 为人工免疫系统研究的主要组成部分 因此人们常提的免疫算法通常与人工免疫系统含 义等同 在人工免疫算法中 已得到成功应用的算法主要有否定免疫算法 克隆选择算法 免疫遗传算法和免疫规划算法等 此外 还有b 细胞算法 疫苗免疫算法等 多数免疫 算法都是针对优化问题展开研究 本文即利用人工免疫算法中的免疫规划算法和克隆选 择算法解决有向传感器网络中的目标覆盖问题 3 1 1 人工免疫算法基本框架 人工免疫算法是一种确定性选择和随机性选择相结合并具有勘测与开采能力的启 发式随机搜索算法 通常情况下 当使用人工免疫算法求解具体的问题时 首先应将问 题中的有关元素 概念和处理过程与生物免疫系统的相关免疫物质和原理机制建立映射 关系 然后建立这些免疫元素相应的数学表达模型 最后根据相关免疫原理和机制设计 出相应的人工免疫算法 人工免疫算法将优化问题中待优化的问题对应免疫应答中的抗原 可行解对应抗体 b 细胞 可行解质量对应抗体与抗原的亲和度 如此则可以将优化问题的寻优过程 与生物免疫系统识别抗原并实现抗体进化的过程对应起来 将生物免疫应答中的进化链 抗体群 免疫选