第1期 毕晓君，等：基于免疫算法的无线传感器网络路由算法 ·69。 免疫算法将生命科学中免疫的概念和理论应用 序进行编码.算法实现过程如下： 到遗传算法中，在原有标准遗传算法的框架基础上 1)初始化.设定算法终止条件，交叉概率A,变 引入了免疫算子(mmune operator).免疫算子由接 异概率，记忆库规模T,随机产生初始种群= 种疫苗和免疫选择两部分构成，其中疫苗指的是依 {,,…,+1},种群为所有节点访问顺序的随机 据人们对待解问题所具备的或多或少的先验知识， 排序，种群进化代数为H,其中个体h∈1,2，…H} 从中提取出的一种基本的特征信息.疫苗的正确选 的路由为S号，S,S…S,,根据每个路径 择对算法的运行效率具有十分重要的意义，是免疫 排序，计算此路径下的能量消耗，目标函数是： 操作得以有效地发挥作用的基础与保障.但是疫苗 的优劣，生成抗体的好坏并不涉及到算法的收敛性， Es (=Ea (s.S)+clw (Ss ) ∈E 因为免疫算法的收敛性归根结底是由免疫选择来保 ∑c传w(3}+q4)m,+ 证的.在计算移动代理路由问题的中止条件是由设 定的进化代数决定的，所以其过程一定是收敛的.为 F到)1 (6 了加快算法的收敛速度并有效地解决进化过程中可 能出现的退化现象，文中在免疫选择的过程中采用 式6)中第1部分是sink节点发送移动代理到第1 个节点消耗的能量，第2部分则是移动代理访问网 了保优操作.该算法的运行流程如图2所示 络内所有节点后回到sik所消耗的能量，其中： 3 基于免疫算法的MA改进路由算法 E阳={4| 、=0,4∈1，…m}, 实现 时=（分|=1，u∈L…m升 MA路由问题可转化为NP(non-detem inistic polynom ial)完全问题o,通常采用启发式算法计算 2计算亲和度.当前种群T中的每一个抗体 近似最优解.进化计算是一种全局最优的启发式方 T,根据适应度函数 法，需要获得网络全局拓扑信息和各节点的访问代 F(T)=1/Eos (T). (70 价，解空间的复杂度对算法收敛速度和解的质量非 计算得出抗体亲和度F(1),求出当前中群中的最 常关键.它在此处对应的是MA需要访问节点个数， 佳个体，截取其中某一段作为疫苗 它随着节点数增多而增大.一般情况下，无线传感器 3)算法终止条件判断.判断是否满足迭代终止 网络内的节点少则几十个，多则上百甚至上千，这导 条件.若满足，确定当前种群中的最佳个体作为算法 致路由问题的解空间复杂度比较高.求解移动代理 最终寻找的解，否则，按照以下步骤进行 路由问题，需要访问网络中的每一个节点以保证信 4)对于当前的第k代父本种群T进行交叉和 息的有效收集.采用遗传算法时，由于算法本身的寻 变异操作，得到种群B 优能力的限制，迭代时间比较长从而增加了系统的 5)对B接种疫苗.即按一定的比例在当前种 延时，并且遗传算法易于陷入局部最优，最佳路径的 群中抽取一定数量的个体，并按先前提取的疫苗对 选择得不到保证.所以选用寻优能力良好的免疫算 这些个体的某些基因位上的基因进行修改，使所得 法求解MA全局最佳路径，来节约能量消耗和减少 个体以较大的概率具有更高的适应性 系统延时 6)免疫选择.即对接种了疫苗的个体进行适应 在将免疫算法应用到求解sik节点和网络中 度检测，若其适应度不如父代，则取消疫苗接种，否 传感器节点之间的总体能耗达到最小的最佳路径问 则保留该个体进入下一代.令k=k+1,返回2)，直 题时，将最低能耗问题对应为抗原，相应的路径对应 到设定的进化代数 于抗体.在对抗体编码时，采用遍历所有簇首节点的 7)在得到的最佳种群中选择适应度函数值最 次序排列进行编码，每一抗体码串形式如下：V1,2, 大的个体作为最佳个体了，该个体就是全局最优 ',其中，V,表示遍历所有节点的序号.程序中 MA路由的个体 抗体定义为一维数组TN),N为网络中的节点个 数与sik个数之和，数组中的各个元素T(i动(i∈ 4实验仿真与结果分析 1,2,N})的取值为1~N的一个整数，分别表 为了验证提出算法的性能，这里进行了仿真实 示节点的序号.根据问题的约束条件，每一数组内的 现，并与目前解决MA路由问题效果最好的自适应 各元素值互不相同.抗体以遍历所有节点的排列顺 数据融合遗传算法(adaptive fusion genetic algo 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net免疫算法将生命科学中免疫的概念和理论应用 到遗传算法中 ,在原有标准遗传算法的框架基础上 引入了免疫算子 ( immune operator). 免疫算子由接 种疫苗和免疫选择两部分构成 ,其中疫苗指的是依 据人们对待解问题所具备的或多或少的先验知识 , 从中提取出的一种基本的特征信息. 疫苗的正确选 择对算法的运行效率具有十分重要的意义 ,是免疫 操作得以有效地发挥作用的基础与保障. 但是疫苗 的优劣 ,生成抗体的好坏并不涉及到算法的收敛性 , 因为免疫算法的收敛性归根结底是由免疫选择来保 证的. 在计算移动代理路由问题的中止条件是由设 定的进化代数决定的 ,所以其过程一定是收敛的. 为 了加快算法的收敛速度并有效地解决进化过程中可 能出现的退化现象 ,文中在免疫选择的过程中采用 了保优操作. 该算法的运行流程如图 2所示. 3 基于免疫算法的 MA改进路由算法 实现 MA路由问题可转化为 NP ( non2determ inistic polynom ial)完全问题 [ 10 ] ,通常采用启发式算法计算 近似最优解. 进化计算是一种全局最优的启发式方 法 ,需要获得网络全局拓扑信息和各节点的访问代 价 ,解空间的复杂度对算法收敛速度和解的质量非 常关键. 它在此处对应的是 MA需要访问节点个数 , 它随着节点数增多而增大. 一般情况下 ,无线传感器 网络内的节点少则几十个 ,多则上百甚至上千 ,这导 致路由问题的解空间复杂度比较高. 求解移动代理 路由问题 ,需要访问网络中的每一个节点以保证信 息的有效收集. 采用遗传算法时 ,由于算法本身的寻 优能力的限制 ,迭代时间比较长从而增加了系统的 延时 ,并且遗传算法易于陷入局部最优 ,最佳路径的 选择得不到保证. 所以选用寻优能力良好的免疫算 法求解 MA全局最佳路径 ,来节约能量消耗和减少 系统延时. 在将免疫算法应用到求解 sink节点和网络中 传感器节点之间的总体能耗达到最小的最佳路径问 题时 ,将最低能耗问题对应为抗原 ,相应的路径对应 于抗体. 在对抗体编码时 ,采用遍历所有簇首节点的 次序排列进行编码 ,每一抗体码串形式如下 : V1 , V2 , …, Vn ,其中 , Vi 表示遍历所有节点的序号. 程序中 抗体定义为一维数组 T (N ) , N 为网络中的节点个 数与 sink个数之和 ,数组中的各个元素 T ( i) ( i∈ { 1, 2, …, N } )的取值为 1～N 的一个整数 ,分别表 示节点的序号. 根据问题的约束条件 ,每一数组内的 各元素值互不相同. 抗体以遍历所有节点的排列顺 序进行编码. 算法实现过程如下 : 1)初始化. 设定算法终止条件 ,交叉概率 pc ,变 异概率 pm ,记忆库规模 Tc ,随机产生初始种群 T 0 = { T 0 1 , T 0 2 , …, T 0 N + 1 },种群为所有节点访问顺序的随机 排序 ,种群进化代数为 H,其中个体 h∈{ 1, 2, …, H} 的路由为 { S 0 T h i , S 1 T h i , S 2 T h i , …, S m T h i , S 0 T h i },根据每个路径 排序 ,计算此路径下的能量消耗 ,目标函数是 : Ecost ( T h i ) = Ecost (S 0 T h i , S 1 T h i ) + e r∑T h i ∈E′n c ( e r T h i w (S r S r T h i ) + e p∑T h i ∈E′f c ( e p T h i ) w (S p S r T h i ) + q ( e p T h i ) [w (S p S r T h i ) + w‰(w (S p+1 S r T h i ) ) ]. (6) 式 (6)中第 1部分是 sink节点发送移动代理到第 1 个节点消耗的能量 ,第 2部分则是移动代理访问网 络内所有节点后回到 sink所消耗的能量 ,其中 : En′= { e u T h i | xe u T h i = 0, u ∈ { 1, …, m } }, Ef′= { e u T h i | xe u T h i = 1, u ∈ { 1, …, m } }. 2)计算亲和度. 当前种群 Tm 中的每一个抗体 Ti 根据适应度函数 F ( T h i ) = 1 /Ecost ( T h i ) , (7) 计算得出抗体亲和度 F ( T h i ) ,求出当前中群中的最 佳个体 ,截取其中某一段作为疫苗. 3)算法终止条件判断. 判断是否满足迭代终止 条件. 若满足 ,确定当前种群中的最佳个体作为算法 最终寻找的解 ,否则 ,按照以下步骤进行. 4)对于当前的第 k代父本种群 Tk 进行交叉和 变异操作 ,得到种群 Bk . 5)对 Bk 接种疫苗. 即按一定的比例在当前种 群中抽取一定数量的个体 ,并按先前提取的疫苗对 这些个体的某些基因位上的基因进行修改 ,使所得 个体以较大的概率具有更高的适应性. 6)免疫选择. 即对接种了疫苗的个体进行适应 度检测 ,若其适应度不如父代 ,则取消疫苗接种 ,否 则保留该个体进入下一代. 令 k = k + 1,返回 2) ,直 到设定的进化代数. 7)在得到的最佳种群中选择适应度函数值最 大的个体作为最佳个体 Tbest ,该个体就是全局最优 MA路由的个体. 4 实验仿真与结果分析 为了验证提出算法的性能 ,这里进行了仿真实 现 ,并与目前解决 MA路由问题效果最好的自适应 数据融合遗传算法 ( adap tive fusion genetic algo2 第 1期 毕晓君 ,等 :基于免疫算法的无线传感器网络路由算法 ·69· © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net