当前位置:首页 >> 信息与通信 >>

遗传算法在WSN路由协议设计中的研究与应用_图文

维普资讯 http://www.cqvip.com

计算机与数字工程 

第3 5卷 

遗 传 算 法 在 WS N路 由协 议设 计 中 的研 究 与应 用 
朱鹏 飞 - 蒋 廷耀 - ’’     ’’    
( 三峡 大学软件工程技术研究 中心 ” 宜 昌 43 0 ) 三峡 大学 电气信息学 院  宜 昌 4 3 0 )   402 ( ’   402  摘 要 和传统无线 网络 的节点相 比, 线传感 器网络的节点 有其 特殊 的地 方 : 无 电源能量有 限 , 信能力 有限 以及 计  通

算能力有限 , 网络拓扑结构更加不稳定 , 这些特性使 得以前研究很多 的无线 自组织 网的网络路 由协议不 能直接应用 于无 线 

传感器网络。提出基于遗传 算法思想来设 计和优化无 线传感器 网络的路 由协议 , 使得 源节点 和 目的节 点之 间以及 中间节  点之间存 在多 条最佳路 径 , 节点在进行路 由选择 的同时 , 最大限度来保 证 网络各节 点的总体 能量 消耗最少 , 最终保 证整个 

网络 的残存性能有进一 步的提高 。  
关键词 无线传感器 网络
T 12 P 8 

遗传算法

路 由算法 

中 图分 类 号

1 引 言   
无线传感器网络就是 由部署在监测 区域内大  量的廉价微型传感器节点组成 , 通过无线通信方式  形成的一个多跳 自组织 网络系统 , 目的是协作地  其 感 知 、 集 和 处 理 网络 覆 盖 区 域 中感 知 对 象 的 信  采
息, 并发 送 给 观察 者 … 。 由 于 无 线 传 感 器 网络 可 

以及 节 点 的剩 余 能量情 况 , 给每条 路径 赋予 一定 的  选择 概率 , 得 数 据 传 输 均 衡 消耗 整 个 网络 的能  使 量 , 长 网络 的生存 期 。这种路 由机 制 的提 出的确  延 可 以很好地 解决 WS N能 量 的 比较 均衡 消耗 问题 ,   但 是 它也存 在着 某 些 不 足 , : 如 对某 些 重 负荷 节 点  保 护不 够得 力 , 局部 路径 的优 化方 面考虑 也不是  在

以有效及时地获取物理信息 , 所以在军事战场情报 
的获 取 , 环境 观测 与 预报 系统 、 医疗 护 理 等方 面它  有着 重要 的应用 。  

很充分等 , 因此我们在此提出基于 G A算法来设计  优化 这 多条路 径 以及这 些节 点之 间局部 路径 。  

2 G 算 法简 介 J   A  
遗传算法是 基 于达尔 文 的物种 起 源所提 出   的” 物竟天择, 适者生存 ” 这一思想 , 在计算机 中模  拟生物在 自然环境 中的遗传和进化过程而形成的  种自 适应全局优化概率搜索算法 , 它和基于导数  的解析方法和其他启发式搜索方法一样 , 都是一种  迭代 方 法 : 选定 的初 始解 出发 , 过 不 断 迭代 逐  从 通


但是 , 和传统无线 网络 的节点相 比, 无线传感  器网络的节点有其特殊的地方 : 电源能量有限 , 通  信能力有限以及计算能力有限 , 网络拓扑结构更加  不 稳定 , 这些 特性 使得 以前研 究很 多 的无线 自组 织 
网的 网络路 由协议 不 能 直 接 应用 于无 线 传 感 器 网  络; 此外 当前 WS 中讨 论 较 多 的基 于查 询 的路 由  N 机 制 D 2在 通 信 过 程 中仅 仅 利 用 一 条 路 径 进 行  D【   数据 的传输 , 种机 制在 面对 网络攻 击或 者其他 灾  这 害 时往往不 能够 及 时 地 进 行反 馈 ; 再者 , 无 线 传  在 感器 网络 中 , 由协议 的设 计不 仅关 心单个 节点 的  路
能量 消耗 , 同时更 关 心 整 个 网络 能量 的均 衡 消 耗 ,  

步 改进 当前解 , 直至 最后搜 索 到最优 解 或者是 满意 

解。遗传算法在步骤上主要 可以分为下面几个步 
骤 : 将 问题 可行解 的空 间映射 成染 色体 集合 的搜  ① 索 空 间。② 确定 适 应 值 函数 、 交 率 和变 异 率 等 。 杂   ③ 进行 选择 、 交叉 和 变异等操 作 。④在 新 旧个体 中  选 择优 胜者 形成新 的种群 , 然后判 断这 些染 色体 是  否 满足要 求 , 若没有 则 利用 刚产生 的染 色体进 行新 


这样才 能够 延长 整个 网络 的生存 周期 ; 而一 味地 依 

靠某一条路径进行数 据传输往往造成某些节点的  早衰 , 最终导致 网络 的分割 或者 是该 网络快速 崩  溃 。为此 , au  .Sa 等 人 提 出 了 一 种 能 量 多  R hlC hl 路径 路 由机 制 』该 机 制 在 源 节 点 和 目的 节 点 之  , 间建立多条路径 , 根据路径上节点的通信能量消耗 

轮 的选 择 、 叉 和变异 等操 作 ……在 这些操 作进  交

行完 之后 将种 群 中 的最 优 染 色体 还 原 成 为一 个 可  行解 作为 问题 的最优 解 。   由于无 线传 感 器 网 络 的特 点 之一 就 是 网络 拓 

收 到本 文时间 :06年 9月 2   20 7日

作者 简 介 : 鹏 飞, , 士研 究 生 , 究 方 向: 线 传 感 器 网 络 路 由及 无 线 网 络 安 全 。蒋 廷 耀 , , 教 授 , 朱 男 硕 研 无 男 副  
硕士生导师 。  

维普资讯 http://www.cqvip.com

第3 5卷( 07 第 8期  20 )

计算 机与数字工程 
1 +3   —   _ _ 1 _ — +8 +l  

2  1

扑结构 极 不 稳 定 ] 利 用 遗 传 算 法 在 某 时 刻 求 解  , 出到 目的节 点 的 K条 路 径 , 样 将 实 际上 极 不 稳  这 定 的网络拓 扑结 构 变 成 逻 辑 上相 对 稳 定 的拓 扑 结  构, 由于在 节点存 取 了 k条 最 优 路 径 , 以在 某 一  所
时刻 当一条路 径 失 效后 其 它路 径 仍 然 可 以进 行 数 

可 以分 别编 码 为 :  

染 色体 P : 3791 记 为 :1 2 3 4 5 11    1   口          a aaa 染 色体 P : 34681 21     1记 为 :1 2 3 4 5 6   b b            bb bb 在 染色 体选 择 的过程 中 , 节点 要先 与 阀值 进行  比较 : 当某一 节 点 的 R<r , 节点 只 有 在作 为  l时 该

据 的传 输 , 同时采 用该 路 由算法 对 失效 的路 径进行  局 部修 复 和优 化 , 后将 修 复 的结 果 返 回给 源 节  然 点 。这样 源节 点就 无 需 在 路 径 出现 故 障 后 再 次 发  出路 由请求 , 而 在 一 定 程 度 上 可 以 减 少 路 由开  从
销 , 到节 能的 目的。 达  

源节点或 目的节点才将其作为染色体的一部分; 当  r l<R<r , 2时 我们 尽 量减 少该 节 点 的使 用 , 一  这
点 在下 面适 应值 函数 中进 一 步进行 说 明 。  
3 2 适应 函数 的选 取  .

3 算 法 实 现   
在设计 之前 , 我们 首先 进行 如 下定义 和 声 明 :   设 无 向离 散 图 G=( V,E) V 表 示 节 点 的集  ,

由于在 无线 传感 器 网络 中能量 的消耗很 重要 ,   因此 在 算法 的设 计过 程 中 , 们采 用如 下 函数作 为  我
适 应 函数 :  
O×_— L l  —
1  

+ 卢×( 一口 1 )×m n R ) R>r i(    3  

合, E表示 边 的集合 , 边 赋予 权 值 cs() 各 ot i 以示 这  两点之 间进 行 通 信 所 要 付 出 的 代 价 , 表 示 源 节    点 , 表 示 目的节 点 , 于 中间节点  剩余 能量 的    对
度 量按 照许 力  提 出 的 A   o d H c网络 能 量 感 知 协  议 中所 定义 的做 如下声 明 :  

∑c s( ) ot i  

O×—— L l  —
1  

+( O) i(    r R>r 1一 1 ×m n R ) 3> l  

∑c s( ) oti  

O×—— l— 一10 l   —— 一 0 0×( 一O _ 1 1 )×mn R ) R<r i(     l   ∑cs() ot    

R=电池 剩余 能 量/ 电池初 始能 量 
此外 , 义 了 r, 定 。r  两级 阀值 , 中 r 2 当  其 l<r。 某个 节 点 的 R值 小 于 r 2时 , 过 它 的 路 径 的 概率  经

其 中: 表 示 从 目的 源 节 点 ( 为 v ) 目 的节 点  S 记 0到
( 为  ) 间所 经 过 的节 点 数 目,ot 示从 节点  记 之 cs表

( 一1 到节点 i i ) 的代 价 , 就是 两 点 间进 行 单位 数  也 据传 输 时 的能 量 消 耗 , 同等 条件 下 , 量 消耗 越  在 能 少, 适应 值就 越 大 ; 为该 条 路 径 能量 消耗 和该 路   

降低 , 对该 节 点 将 对 它 所 在 的 路 径 进 行 局 部 的优  化, 并允 许该 路径 被 其 他 的路 由取代 , 它 的邻 居  在 节点 查 找符合 条件 的替 代 节点 , 并通 知 它的上 下游  节点 实 现本地 路径 的更 新 和替代 ; 当某个 节点 的电 
池能 量小 于 r 1时 , 节 点 只为 自己作 为 源 节 点 或  该 目的节点 的路 径服务 。  

径上剩余能量最 小值的一个均衡值 。6以及上 面  的 10 00都 是 一个 奖惩 系数 , 6为 大 于 1的 一个 奖  励 系数 , 以 由用 户 自己来 进 行 设定 , 表示 对 哪  可 它
些能 量值 较高 的路 径 赋予 更 高 的适应 值 。10 0 0作 

为一 个惩 罚系 数 , 这里用 它是 用来 表 明在一 个 节点  的能 量值 很低 的 时候 , 只有 在极其 特殊 的情 况下 才  用它 们作 为路 径上 的一 部分 。适 应 函数值 越大 , 表 
2  

明该 条路径 的生存 能力 越强 。  
3 3 交 叉  . 

交 叉在 遗 传算 法 中起 着核 心 作用 , 路 径 的产  新 生 往往 靠 的就 是交 叉 操 作 , 叉 分 为 单 点 交叉 、 交 两  点 交叉 、 均匀 交 叉 和 多 点交 叉 , 计 中我 们 采 用单  设
图 1 染 色 体 编 码 

点交 叉 , 即根 据 长度 挑 选 出来 的染 色 体 , 即产 生  随


3 1 染 色体 编码  .

个 交叉 位置 , 比如 在上 面 的两 条染 色体 中我们 假 
染色体  : 34681 1     1记为 :l 2 3 4  b     a a      6   bb b  

在设 计 中 , 我们 采 用源节 点 到 目的节 点或 者是  中间节 点之 间 的路 径作 为染 色 体进 行编 码 , 由于在  源 节点 和 目的节点 之 间可能 存 在多条 路 径 , 些路  这 径 的所经 过 的节点 数 目极有 可能 不等 , 以我们 采  所 用 可变 长度 的染色 体 编码 , 如在 上 图 1中源 节点 1  
到 目的节 点 1 1之 问 的两条路 径 :  
1 3 7_ 9 _ _ _+1    1

设 随 即产生 的交 叉位 置 为 2则 交叉 后 的结 果 为 :  

染 色体 P : 3791 为 :1 2 3 4 s ; 1    1记   b b          aaa 在交 叉 的过程 有 可能 出现 随 即产生 的交叉 位置 后 ,   染色 体 P 不 能 够与 染色 体 P 进行连 接 ( 。 : 如我们 假  设上 面 a 和 b 无 法进 行连 接 ) 这种 情 况 出现后 , : , ,  

则依次向后查找 , 若是在这样一系列过程完成后没 

维普资讯 http://www.cqvip.com

2  2

朱鹏 飞等 : 遗传算 法在 WS N路 由协议设计 中的研究 与应 用 

第3 5卷 

有形 成 一条新 的染 色体 , 则染 色体 P 与 P 色体     染 交叉 失败 , 再选 择两 条染 色体进 行交 叉 。   此外在 交叉 过程 中可能会形 成环 路 , 如交叉后  的一 条新 的染 色 体为 :  
14 3 7 6 4 5 1   1               0 l 

命, 同时用 遗传 算法 对源 节点 和 目的节点 之 间的路 

径 以及局部路径的优化, 使得在不影响数据传输 的   同时 , 也保证 了网络 整 体 能 量 的均 衡 和 最 小 消耗 。  
对 于遗 传 算 法 在 求 k条 最 优 路 径 的 收 敛 性 , 马  炫  在他 的论 文 中 用 做 实 验 的方 式 进 行 说 明 , 实  验结 果证 明这 种算 法 的收敛性 很好 。  

此 时消 除重复 基 因 即可 , 如上 面消 除重复 基 因 
块后 的结 果为 :  
14 5 1   1      0 1 

5 结 束 语   
在无线 传感 器 网络 中 , 当前 的路 由机 制大 多都 

3 4 变 异  .

生 物 的基 因产 生 变 异后 产 生 的适 应 环境 的基 

因是促进生物更好适应环境 的重要因素 , 对于路径 
表示 的染色 体 , 异操 作把连 接 点组成 的路 径作 为  变 基 因块 , 实现 染 色体 的基 因块 变 异 , 就 是 用 两个  也 节点之 间 的其 他路 径来 代替 当前路 径 , 如有下 面 一  段 经过交 叉后 的染 色体 : 37681 , 1     1不妨 设 (        376
8 这 段基 因块 发 生 了 变 异 , 异 后 的结 果 形 式 如  ) 变

采取利用单条路径来进行数据的传输 , 采用此路 由   机 制很 容易 使得 某些 节 点 能 量 过度 消耗 而提 前 衰 
亡, 一方 面会 造成 无 线 传 感 器 网络 的分 割 , 一 方  另 面 也使得 网络 在 面对 攻 击 或 其他 一些 灾 害 时残 存  性较 差 , 我们采 用基 因算 法来 求得 源节 点到 目的节  点之 间 的多条最 优 路 径 可 以有 效 解 决 上 面提 到 的 
问题 。  
参 考 文 献 

(   ) 其 中 (    ) 3468 就 是 此形 式 中 的  3x8 , 3768 (    ) 两种 。在 此过程 中若 产 生 环路 才 用 前 面 同样 的方  法进行 消 除 。   35 新一 代种群 的选 择  . 最 后进 行新 的种 群筛 选 : 源 染 色体 、 叉后  在 交 产 生 的染 色体 以及 变 异后 的染 色体 中选 择那 些具  有 优 良品性 的染 色体 ( 即适 应 值 Ftes 大 的那  i s最 n 些 染色 体 ) 为新 一 代 的 种 群 。在 种 群 世 代 更 新  作 过 程 中有 可 能产生 同样 的染 色体 , 此时要 消 除同样  的染 色体 , 这样 经 过 若 干代 的进 化后 , 即可 以得 到  我们 所要 求 的前 K条 最佳 路径 。  
[ ] 利 民等. 线 传感 器 网络 [ . 1孙 无 M] 清华 大 学 出版 社 ,  
2 05,   0 2

『 ] t a o w w t .D r t   iu i :A sa b ea d r_ 2 I a g n i a C i ce d s n   cl l n  o  n n   e d f o a  
b s c mmu i ai n   aa im  o   e s r n t o k .P o   ut o   n c t s p r d g f r s n o   e w r s rc o 6 h An u   t SC n  n Mo i   o u i g a d Ne o k   t   n a I ’   o fo   b l C mp t     t r s ln e n n w

[ ] au  .h hadJ   R be  nryA aeR uig 3 R h l S a   a M. aayE e   w r ot   C n n g   n o Lw E eg A   o  esrN tok [ .n r f  o   nr   d H cSno  ew rs C] I:Po  r y c
I EE E  Wiee s o rl s C mmu ia in  a d n c t s n  New r ig Co f r  o t o k n   ne -

ec WC C’2 , E E,0 2 1 1 2  ne( N 0 ) I E 20 , :7~ 1

[ ] 敏强. 传算 法 的基 本理 论 与应 用 [ . 学 出版  4李 遗 M] 科

4 对算法 的分析 
在传统 的路 由机制中, 往往采用的是用一条路  径来进行数据韵传输 , 而这条路径 的产生往往采用  的是 Djsa 法或 者是 这 种算 法 的改 进所 得 到 , i t 算 kr   虽然此 路径 在 以某 一权 值来 进行衡 量 时是最 优 的 ,  

社 ,0 2 20 

[] 5 李建 中 , 李金宝 , 石胜飞.传感 器网络及 其数据 管理 的 
概念 、 问题和进展 [ ] 软件学报 , 0 , (0   J. 2 31 1) 0 4 [] 6 许力等 .自组网环境下 具有能 量和移 动感 知 的 自适应  路 由协议 [ ] 计算机应用 2 0 ( 0  J. 04,1 )

[] 7 邢传鼎等. 工智 能原理及应用 [ ] 东华 大学 出版社 , 人 J.  
20 05,  3

但是由于种种因素的制约 , 往往使得单条路径在数 
据传输的过程 中显得力不从心。而在该算法 中, 阀  门值的引入使得 WS N中的节点最大程度地延长寿 

[] 8 马炫.求 K条最优路径问题 的遗传算法 [ ] 计算机 工  J.
程与应用 ,0 6 (2   20 , 1 )