第4卷第1期 智能系统学报 Vol 4 Na 1 2009年2月 CAA I Transactions on Intelligent Systems Feb 2009 基于免疫算法的无线传感器网络路由算法 毕晓君，张艳双 (哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001) 摘要：针对移动代理MA)以能量有效的方式收集相关性数据的特点，提出一种基于免疫算法的数据融合路由算 法.利用免疫算法的寻优能力对MA路由进行全局优化，并根据节点数据传输和融合能量开销及节能增益，对移动代 理迁移到每个节点是否进行数据融合进行选择，以提高信息收集过程中网络能量效率.实验结果表明，该算法具有 更好的能量利用效率和较低延时. 关键词：无线传感器网络：数据融合，免疫算法：移动代理 中图分类号：N914文献标识码：A文章编号：1673-4785(2009)01-006705 A routng a lgor ithm for wireless sensor networks ba sed on an immune a lgorithm BI Xiao-jun,ZHANG Yan-shuang (College of Infomation and Communication Engineering,Harbin Engineering University,Harbin 150001,China) Abstract:Mobile agents (MA)collect correlated data in an energy efficientway:we proposed an adaptive data fu- sion routing algorithm based on such an imune algorithm.W ith thismethod,a global route opti ization was per fomed using the search ability ofourMA imune algorithm.Then,according to data trans ission cost and energy gain,the algorithm adaptively detem ined whether fusion wasmade for every node the moving agent transn itted,so that energy efficiency in the netork was mp roved in the course of data collection Smulation results showed that this algorithm has better energy efficiency and low tme delay Keywords:wireless sensor network,data fusion;mmune algorithm;MA 无线传感器网络(wireless sensor netorks,算法决策全局最优的MA路由，并且根据能量开销 WSN)由于其灵活性，可以广泛应用在军事侦察、环 和节能增益自适应决定MA迁移到每个节点是否进 境检测和工业生产等领域：然而WN中节点的能 行数据融合，取得了比较好的能量利用效率，是目前 量、通信和计算能力较为有限，网络设计需考虑容错 效果最好的方法.但是为了保证数据的完整收集，要 性、可扩展性、可靠性和节能等需求.目前，如何节省 求访问网络内所有节点，而采用遗传算法计算MA 网络能耗、延长网络生命周期成为WSN中研究的重 路由时.由于遗传算法自身寻优能力的限制，计算迭 点 代时间比较长，并且遗传算法容易陷入局部最优，最 数据融合技术可有效消除冗余信息，减少数据 佳路径的选择得不到保证，所以该算法的路由消耗 传输量，提高数据收集的准确性和效率.针对数据融 与系统延时相对还比较大 合的特点，Qi等学者提出了移动代理1，(mobile a- 免疫算法是在遗传算法基础之上发展起来的一 gent,MA)的概念，可按需移动并靠近数据源进行处 种全局优化算法，大多遗传算法能够解决的问题，免 理，特别适合近距感知和“以数量换质量”的无 疫算法都能够有效解决且效率要比遗传算法好.作 线传感器网络，在网络协议设计和信息处理等领域 者提出了一种基于免疫算法的数据融合路由算法， 也引起了人们的重视.目前己提出许多有效的移动 利用免疫算法良好的寻优能力求解MA访问所有节 代理数据融合路由算法581，其中文献[9]利用遗传 点完成数据收集而总能耗最小的路径，最终实现了 减少无线传感器网络的能量消耗、减少网络系统时 收稿日期：200809-26 延的目的 通信作者：毕晓君.Emai止bixiao jun@hrbeu edu cn 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
第 4卷第 1期 智 能 系 统 学 报 Vol. 4 №. 1 2009年 2月 CAA I Transactions on Intelligent System s Feb. 2009 基于免疫算法的无线传感器网络路由算法 毕晓君 ,张艳双 (哈尔滨工程大学 信息与通信工程学院 ,黑龙江 哈尔滨 150001) 摘 要 :针对移动代理 (MA)以能量有效的方式收集相关性数据的特点 ,提出一种基于免疫算法的数据融合路由算 法. 利用免疫算法的寻优能力对 MA路由进行全局优化 ,并根据节点数据传输和融合能量开销及节能增益 ,对移动代 理迁移到每个节点是否进行数据融合进行选择 ,以提高信息收集过程中网络能量效率. 实验结果表明 ,该算法具有 更好的能量利用效率和较低延时. 关键词 :无线传感器网络 ;数据融合 ;免疫算法 ;移动代理 中图分类号 : TN914 文献标识码 : A 文章编号 : 167324785 (2009) 0120067205 A routing algor ithm for wireless sensor networks based on an immune algor ithm B I Xiao2jun, ZHANG Yan2shuang (College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China) Abstract: Mobile agents (MA) collect correlated data in an energy efficientway: we p roposed an adap tive data fu2 sion routing algorithm based on such an immune algorithm. W ith thismethod, a global route op tim ization was per2 formed using the search ability of ourMA immune algorithm. Then, according to data transm ission cost and energy gain, the algorithm adap tively determ ined whether fusion wasmade for every node the moving agent transm itted, so that energy efficiency in the network was imp roved in the course of data collection. Simulation results showed that this algorithm has better energy efficiency and low time delay. Keywords:wireless sensor network; data fusion; immune algorithm; MA 收稿日期 : 2008209226. 通信作者 :毕晓君. E2mail: bixiaojun@hrbeu. edu. cn. 无 线 传 感 器 网 络 (wireless sensor networks, WSN)由于其灵活性 ,可以广泛应用在军事侦察、环 境检测和工业生产等领域 ;然而 WSN 中节点的能 量、通信和计算能力较为有限 ,网络设计需考虑容错 性、可扩展性、可靠性和节能等需求. 目前 ,如何节省 网络能耗、延长网络生命周期成为 WSN中研究的重 点 [ 123 ] . 数据融合技术可有效消除冗余信息 ,减少数据 传输量 ,提高数据收集的准确性和效率. 针对数据融 合的特点 , Q i等学者提出了移动代理 [ 4 ] (mobile a2 gent, MA)的概念 ,可按需移动并靠近数据源进行处 理 ,特别适合“近距感知 ”和“以数量换质量 ”的无 线传感器网络 ,在网络协议设计和信息处理等领域 也引起了人们的重视. 目前已提出许多有效的移动 代理数据融合路由算法 [ 528 ] ,其中文献 [ 9 ]利用遗传 算法决策全局最优的 MA路由 ,并且根据能量开销 和节能增益自适应决定 MA迁移到每个节点是否进 行数据融合 ,取得了比较好的能量利用效率 ,是目前 效果最好的方法. 但是为了保证数据的完整收集 ,要 求访问网络内所有节点 ,而采用遗传算法计算 MA 路由时. 由于遗传算法自身寻优能力的限制 ,计算迭 代时间比较长 ,并且遗传算法容易陷入局部最优 ,最 佳路径的选择得不到保证 ,所以该算法的路由消耗 与系统延时相对还比较大. 免疫算法是在遗传算法基础之上发展起来的一 种全局优化算法 ,大多遗传算法能够解决的问题 ,免 疫算法都能够有效解决且效率要比遗传算法好. 作 者提出了一种基于免疫算法的数据融合路由算法 , 利用免疫算法良好的寻优能力求解 MA访问所有节 点完成数据收集而总能耗最小的路径 ,最终实现了 减少无线传感器网络的能量消耗、减少网络系统时 延的目的. © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
68- 智能系统学报 第4卷 1基于移动代理的无线传感器网络数 一，由此点数据融合后的权重为 据融合模型 w(y=6w(+p(y)1-om人. 3) 基于移动代理的无线传感器网络由3个主要部 综合式1)、式(2)得节点的融合方程为 分组成：汇聚节点(simk)、传感器节点(node)和通信 w(=(p(l+w(y）(1-0m)· 网络.传感器节点散布在观察区域内采集与观察对 (1 -0 ) 4) 象相关的数据，并将协同处理后的数据传送到sik 计算移动代理路由的目的就是找到一条MA访 其中sik有相对较强的处理、存储和通信能力，并 问所有节点完成数据融合和收集且消耗总能量最小 能进行全局优化.simk可以通过Intemet或通信卫星 的路径，即在以传感器节点为顶点的无向全连通图 实现传感器网络与任务管理节点之间的通信，网络 G中找到一个可行的最优子图G=W.E)SG. 的具体结构如图1所示」 最优子图G应该满足： G =argmin∑(ftel+t(e)+ ∑te (5) sink 其中 E=fele∈E`,x.=ly node Em=fele∈E,x=0以 免疫算法基本原理 初始化种群T 图1基于移动代理的无线传感器网络 根据当前最佳 Fig 1 W ireless sensor netorks based on MA 个体提取疫苗 移动代理MA)本质上是一个程序实体，拥有 一定的智能和判断能力.它可以在自己的控制下，按 计算适应度函数 照一定的规程在网络节点间迁移，完成特定的任务， MA由simk节点产生并根据当前的网络状态，决策 判断条件 是 停止运行 MA的最优路由.MA从sink出发，沿着事先设计的 并输出结果 路由访问每一个节点，收集、融合感兴趣的数据，并 T 将之带回simk用一个无向全连通图G=(W,E)来 交叉、变异B 代表无线传感器网络，顶点v∈V代表网络中的一个 传感器节点，边e=(u,以∈E代表顶点和所对 接种疫苗C, 应的传感器节点能够直接通信.根据文献[69做出 以下定义： 免疫选择D 定义1设任意节点v∈V的权重为传输数据 量w()以，边e=(u,的权重为w(e=w(,其中： 否 体更新 u为起点，v为终点 T 定义2设c(e为单位传输能量，边e的数据 是 传输能量为 最佳种群 t(e)=c(e)w (e). 1) 定义3设g(为单位融合能量，p(·)为数 据融合前的权重，w(·)为数据融合后的权重，边e 最佳个体 (判决输出结果) 不进行数据融合的能量为 f(e)=g(e)(w(u)+w(v))o (2) 图2免疫算法流程图 数据融合率·是数据融合路由协议的关键因素之 Fig 2 Fbwchart of mmune algprithm 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
1 基于移动代理的无线传感器网络数 据融合模型 基于移动代理的无线传感器网络由 3个主要部 分组成 :汇聚节点 ( sink)、传感器节点 ( node)和通信 网络. 传感器节点散布在观察区域内采集与观察对 象相关的数据 ,并将协同处理后的数据传送到 sink. 其中 sink有相对较强的处理、存储和通信能力 ,并 能进行全局优化. sink可以通过 Internet或通信卫星 实现传感器网络与任务管理节点之间的通信 ,网络 的具体结构如图 1所示. 图 1 基于移动代理的无线传感器网络 Fig. 1 W ireless sensor networks based on MA 移动代理 (MA )本质上是一个程序实体 ,拥有 一定的智能和判断能力. 它可以在自己的控制下 ,按 照一定的规程在网络节点间迁移 ,完成特定的任务. MA由 sink节点产生并根据当前的网络状态 ,决策 MA的最优路由. MA从 sink出发 ,沿着事先设计的 路由访问每一个节点 ,收集、融合感兴趣的数据 ,并 将之带回 sink. 用一个无向全连通图 G = (V, E) 来 代表无线传感器网络 ,顶点 v∈V代表网络中的一个 传感器节点 ,边 e = ( u, v) ∈ E代表顶点 u和 v所对 应的传感器节点能够直接通信. 根据文献 [629 ]做出 以下定义 : 定义 1 设任意节点 v∈V 的权重为传输数据 量 w ( v) ,边 e = ( u, v)的权重为 w ( e) =w ( u) ,其中 : u为起点 , v为终点. 定义 2 设 c ( e)为单位传输能量 ,边 e的数据 传输能量为 t( e) = c ( e) w ( e). (1) 定义 3 设 q ( e)为单位融合能量 , w ( ·)为数 据融合前的权重 , w ( ·)为数据融合后的权重 ,边 e 不进行数据融合的能量为 f ( e) = q ( e) (w ( u) +w( v) )σuv . (2) 数据融合率 σuv是数据融合路由协议的关键因素之 一 ,由此点 v数据融合后的权重为 w ( v) = (w ( u) +w( v) ) (1 - σuv ). (3) 综合式 (1) 、式 (2)得节点 v的融合方程为 w ( v) = (w ( u) +w( v) ) (1 - σuv ) · (1 - σuv xuv ). (4) 计算移动代理路由的目的就是找到一条 MA访 问所有节点完成数据融合和收集且消耗总能量最小 的路径 ,即在以传感器节点为顶点的无向全连通图 G中找到一个可行的最优子图 G 3 = (V, E 3 ) Α G. 最优子图 G 3 应该满足 : G 3 =a rgm in G 3 e∈∑E 3 f ( f ( e) + t( e) ) + e∈∑E 3 n t( e). (5) 其中 : E 3 f = { e | e ∈ E 3 , xe = 1}, E 3 n = { e | e ∈ E 3 , xe = 0}. 2 免疫算法基本原理 图 2 免疫算法流程图 Fig. 2 Flowchart of immune algorithm ·68· 智 能 系 统 学 报 第 4卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第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
·70· 智能系统学报 第4卷 rihm,AFGA)进行性能比较.实验在Pentium CPU 实验，这也是判定一个算法优劣的重要指标.为了对 260GHz内存1024MB的计算机上运行的，程序采 比本文算法与AFGA算法在延时方面的性能，实验 用MA TLAB7.0语言编写」 中将两种算法的实验仿真时间进行了比较，节点数 实验中，将传感器节点随机抛洒在一个 n分别选取50、100、150、200、250、300，进行多次实 50m50m的区域中，sink点坐标为(25,30)，每个 验并取平均值，结果如图4所示。 节点产生1500byte数据包，发送单位比特数据耗能 35 为c(e=Bd+e,其中：d为节点之间的欧式距离： 30 —AFGA 无线通信的可调参数为B=100p/(bit·m;r= 回 ·一本文算法 2:接收单位比特数据能量为e=100nJ/bit相关节 20 点的数据相关性可由相关系数P来表示.当d≤5 15 时，p=1·d/,反之p=Q因此当在节点v进行数 10 据融合时，节点v处数据量为 w(以=maxw(u),w(以)+ 50100150200250300 minw(u,w(y）(1-Pw人.(8) 传感器节点数 采用的免疫算法初始种群规模设定为20.交换 概率为Q85,变异概率为001AFGA算法中遗传 图4不同节点数两种算法仿真时间 算法的种群规模为20，交叉概率为Q85两种优化 Fig 4 Smulations tme of to algorithms in different nodes 算法的初始进化代数均为200，进化代数随节点数 由图4可以看到，提出的算法的仿真时间比 的不同而不同.节点数n分别选取50、100、150、 AFGA要小一些，节点数比较少时，二种算法的时间 200、250、300,进行多次实验并取平均值.图3为不 相差不大；但是随着节点数的增加，本文算法的优势 同节点规模情况下，本文算法和AFGA的能量消耗 就显现出来.这是因为遗传算法和免疫算法的运行 对比情况，其中o=80n/bit相关距离5=35m, 时间都与进化代数有关，而节点数目的增加会造成 经过多次实验，计算MA收集网络中所有节点的信 解空间复杂度的增加，AFGA中遗传算法须持续增 息并返回simk的平均能量消耗 加进化代数以保证能够寻到全局比较精确的最优 250 解，而免疫算法具有良好的寻优能力，可以设置相对 -AFGA 较少的进化代数：所以随着节点规模的增加，提出的 200 ·。本文算法 算法比AFGA算法具有更少的计算时间，实现了降 150 低延时的目的，适合无线传感器网络中一些对于延 盟100 时要求较高的应用 50 5结束语 基于移动代理的数据融合技术，能够消除冗余 50 100150200250300 信息，减少数据传输量，从而有效地节省能量，延长 传感器节点数 网络生命，有着很大的实际研究价值.利用免疫算法 图3不同节点规模下两种算法能耗 的寻优能力进行全局路由优化，并通过比较融合能 Fig 3 Energy consumption of wo algorithms in different 量与节省的传输能量，自适应调整MA在节点是否 nodes 进行数据融合.实验结果表明，提出的算法能够减少 由图3可见在不同节点规模情况下，本文算法 能量消耗，提高了网络能量效率，并能减少延时，适 在能量消耗方面要优于AFGA算法，并且随着节点 应无线传感器网络多节点应用的要求，具有重要的 数的增加能量消耗小的优势更加明显这是因为，免 实际应用价值 疫算法相对于遗传算法，收敛到全局最优解的能力 比较高，在计算MA路由时，遗传算法容易得出局部 参考文献： 最优而计算出能量消耗较小的路径，而免疫算法却 [1 ]AC DLY IF,SUW,SANKARASUBRAMAN AM Y,etal 能计算出能耗更小的全局最佳路径，所以最终实现 W ireless sensor networks A survey [J ]Computer Net- 了节约能量消耗的目的。 w0ks2002,38(4):393-422 另外还进行了算法执行时间实验，即延时情况 [2]CHONG C Y,KUMAR S Sensor neworks Evolution,op- 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
rithm,AFGA) [ 9 ]进行性能比较. 实验在 Pentium CPU 2. 60GHz、内存 1024MB的计算机上运行的 ,程序采 用 MATLAB7. 0语言编写. 实验 中 , 将 传 感 器 节 点 随 机 抛 洒 在 一 个 50 m ×50 m的区域中 , sink点坐标为 ( 25, 30) ,每个 节点产生 1 500 byte数据包 ,发送单位比特数据耗能 为 c ( e) =βd r +ε,其中 : d为节点之间的欧式距离; 无线通信的可调参数为 β= 100 pJ / ( bit·m 2 ) ; r = 2;接收单位比特数据能量为 ε= 100 nJ /bit. 相关节 点的数据相关性可由相关系数 ρ来表示. 当 d≤rs 时 ,ρ= 1 - d / rs ,反之 ρ= 0. 因此当在节点 v进行数 据融合时 ,节点 v处数据量为 w ( v) =max(w ( u) , w( v) ) + m in (w ( u) , w( v) ) (1 - ρuv ). (8) 采用的免疫算法初始种群规模设定为 20,交换 概率为 0. 85,变异概率为 0. 01. AFGA算法中遗传 算法的种群规模为 20,交叉概率为 0. 85. 两种优化 算法的初始进化代数均为 200,进化代数随节点数 的不同而不同. 节点数 n 分别选取 50、100、150、 200、250、300,进行多次实验并取平均值. 图 3为不 同节点规模情况下 ,本文算法和 AFGA的能量消耗 对比情况 ,其中 ω = 80 nJ /bit,相关距离 rs = 35 m , 经过多次实验 ,计算 MA收集网络中所有节点的信 息并返回 sink的平均能量消耗. 图 3 不同节点规模下两种算法能耗 Fig. 3 Energy consump tion of two algorithm s in different nodes 由图 3可见在不同节点规模情况下 ,本文算法 在能量消耗方面要优于 AFGA算法 ,并且随着节点 数的增加能量消耗小的优势更加明显. 这是因为 ,免 疫算法相对于遗传算法 ,收敛到全局最优解的能力 比较高 ,在计算 MA路由时 ,遗传算法容易得出局部 最优而计算出能量消耗较小的路径 ,而免疫算法却 能计算出能耗更小的全局最佳路径 ,所以最终实现 了节约能量消耗的目的. 另外还进行了算法执行时间实验 ,即延时情况 实验 ,这也是判定一个算法优劣的重要指标. 为了对 比本文算法与 AFGA算法在延时方面的性能 ,实验 中将两种算法的实验仿真时间进行了比较 ,节点数 n分别选取 50、100、150、200、250、300,进行多次实 验并取平均值 ,结果如图 4所示. 图 4 不同节点数两种算法仿真时间 Fig. 4 Simulations time of two algorithms in different nodes 由图 4可以看到 ,提出的算法的仿真时间比 AFGA要小一些 ,节点数比较少时 ,二种算法的时间 相差不大 ;但是随着节点数的增加 ,本文算法的优势 就显现出来. 这是因为遗传算法和免疫算法的运行 时间都与进化代数有关 ,而节点数目的增加会造成 解空间复杂度的增加 , AFGA中遗传算法须持续增 加进化代数以保证能够寻到全局比较精确的最优 解 ,而免疫算法具有良好的寻优能力 ,可以设置相对 较少的进化代数 ;所以随着节点规模的增加 ,提出的 算法比 AFGA算法具有更少的计算时间 ,实现了降 低延时的目的 ,适合无线传感器网络中一些对于延 时要求较高的应用. 5 结束语 基于移动代理的数据融合技术 ,能够消除冗余 信息 ,减少数据传输量 ,从而有效地节省能量 ,延长 网络生命 ,有着很大的实际研究价值. 利用免疫算法 的寻优能力进行全局路由优化 ,并通过比较融合能 量与节省的传输能量 ,自适应调整 MA在节点是否 进行数据融合. 实验结果表明 ,提出的算法能够减少 能量消耗 ,提高了网络能量效率 ,并能减少延时 ,适 应无线传感器网络多节点应用的要求 ,具有重要的 实际应用价值. 参考文献 : [ 1 ]ACIDLY I F, SU W , SANKARASUBRAMAN IAM Y, et al. W ireless sensor networks: A survey [ J ]. Computer Net2 works, 2002, 38 (4) : 3932422. [ 2 ]CHONG C Y, KUMAR S. Sensor networks: Evolution, op2 ·70· 智 能 系 统 学 报 第 4卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第1期 毕晓君，等：基于免疫算法的无线传感器网络路由算法 ·71 portunities,and challenge [J].Proceedings of the EEE, of Posts and Telecommunications,2007,27(1):64-68 2003,91(8):1247-1256 [9湖海峰，杨震.无线传感器网络中基于移动代理的自 [3 ]WANG Feng,TAN Qichuan,GAO Quanxue,et al A 适应数据融合路由算法[J]电子与信息学报，2008,30 study of sensormanagement base on sensor netorks [C]// (9):2254-2258 Proceedings of 2003 IEEE Itemational Conference on Ro- HU Haifeng,YANG Zhen Mobile-agent-based adaptive da- botics,Intelligent Systems and Signal Processing.Chang- ta fusin routing algorithm in wireless sensor netorks[J. sha,China,2003,2:8-13. Joumal of Electronics Infomation Technology,2008,30 [4 JQIHairong.IYENGAR S S,CHA KRABARTY K Multires- (9):2254-2258 lutions data integration using mobile agents in distributed [10]HENZELMAN W,CHANDRAKASAN A,BALLADRY- sensor neworks [J].IEEE Transition Systems,Man and SHNAN H.Energy-efficient conununication procol or Cybemetics-Part C:Applications and Rev,2001,31(3): wireless sensor netorks [C]//Proceedings of the 33rd 383-391 Hawaii Intemational Conference on System Sciences Ha- [5 ]RAJAGOPALAN R,MOHAN C K,VARSHNEY P,et al wai,USA,2000:10 Multi-objective mobile agent routing in wireless sensor net- 作者简介： works[J].IEEE Transition Congress on Evolutionary Com- 毕晓君，女，1964年生，教授博士生 putation,2005,5(5):1730-1737. 导师，博士，中国图像图形学会会员，黑 [6]HYDER A K SHANBAZAN E.WALTZ E Multisensor 龙江省生物医学工程学会常务副理事 fusion [M Dordrecht Kluwer Academ ic Publishers, 长，黑龙江省人工智能学会常务理事.主 2002 要研究方向为图像处理、语音识别合成 [7WU Qishi,RAO N S V,BARHEN J,et al On computing 技术、信息智能处理技术.先后承担省部 mobile agent routes for data fusion distributed sensor net- 级科研项目7项，获得省部级科学技术进步二等奖2项、三等 works[J ]IEEE Transition Knowledge and Data Engineer 奖3项.发表学术论文31篇，其中9篇被E收录. ing,2004,16(6):740-753 张艳双，男，1984年生，硕士研究 [8王2，曹涌涛，糜正琨.无线传感器网络Mobile Agent 生，主要研究方向为通信与信息系统、 路由问题的模拟退火解法[J小南京邮电大学学报， 无线传感器网络、人工智能， 2007,27(1):64-68 WANG Jun,CAO Yongtao,MI Zhengkun Smulation an- nealing soluton for the routing problem of mobile agents in wireless sensor networks[J.Joumal of Nanjing University 第2届智能机器人与应用国际会议 The 2nd hterna tional Conference on htelligent Robotics and Applica tions The 2nd Intemational Conference on Intelligent Robotics and Applications (CRA2009)will be held at Orchard Hotel,Singapore in 16-18,December 2009 C RA2009 conference welcomes contributions of quality papers pres- enting new research,new app lications,and new technolgical develpments at the hardware and/or sofware levels for intelligent and autonomous robots m portantDates: Subm ission of Full Papers 15 June 2009 Paper Accep tance:15 August 2009 Subm ission of Final Papers 15 September 2009 Early Bird Registration:30 Sep tember 2009 Technical Program:30 September 2009 Conference:16-18 December 2009 Ema il:james lee@robotics sg W ebsite:http://icira2009 robotics sg/index php 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
portunities, and challenge [ J ]. Proceedings of the IEEE, 2003, 91 (8) : 124721256. [ 3 ]WANG Feng, TIAN Q ichuan, GAO Quanxue, et al. A study of sensormanagement base on sensor networks [C ] / / Proceedings of 2003 IEEE International Conference on Ro2 botics, Intelligent System s and Signal Processing . Chang2 sha, China, 2003, 2: 8213. [ 4 ]Q IHairong, IYENGAR S S, CHAKRABARTY K. Multireso2 lutions data integration using mobile agents in distributed sensor networks [ J ]. IEEE Transition System s, Man and Cybernetics2Part C: App lications and Rev, 2001, 31 ( 3) : 3832391. [ 5 ] RAJAGOPALAN R, MOHAN C K, VARSHNEY P, et al. Multi2objective mobile agent routing in wireless sensor net2 works[J ]. IEEE Transition Congress on Evolutionary Com2 putation, 2005, 5 (5) : 173021737. [ 6 ]HYDER A K. SHANBAZIAN E, WALTZ E. Multisensor fusion [ M ]. Dordrecht: Kluwer Academic Publishers, 2002. [ 7 ]WU Q ishi, RAO N S V, BARHEN J, et al. On computing mobile agent routes for data fusion distributed sensor net2 works[J ]. IEEE Transition Knowledge and Data Engineer2 ing, 2004, 16 (6) : 7402753. [ 8 ]王 − ,曹涌涛 ,糜正琨. 无线传感器网络 Mobile Agent 路由问题的模拟退火解法 [ J ]. 南京邮电大学学报 , 2007, 27 (1) : 64268. WANG Jun, CAO Yongtao, M I Zhengkun. Simulation an2 nealing solution for the routing p roblem of mobile agents in wireless sensor networks[J ]. Journal of Nanjing University of Posts and Telecommunications, 2007, 27 (1) : 64268. [ 9 ]胡海峰 ,杨 震. 无线传感器网络中基于移动代理的自 适应数据融合路由算法 [J ]. 电子与信息学报 , 2008, 30 (9) : 225422258. HU Haifeng, YANG Zhen. Mobile2agent2based adap tive da2 ta fusion routing algorithm in wireless sensor networks[J ]. Journal of Electronics & Information Technology, 2008, 30 (9) : 225422258. [ 10 ] HEINZELMAN W , CHANDRAKASAN A, BALLADRY2 SHNAN H. Energy2efficient conununication p rotocol for wireless sensor networks [ C ] / /Proceedings of the 33 rd Hawaii International Conference on System Sciences. Ha2 waii,USA, 2000: l210. 作者简介 : 毕晓君 ,女 , 1964年生 ,教授 ,博士生 导师 ,博士 ,中国图像图形学会会员 ,黑 龙江省生物医学工程学会常务副理事 长 ,黑龙江省人工智能学会常务理事. 主 要研究方向为图像处理、语音识别合成 技术、信息智能处理技术. 先后承担省部 级科研项目 7项 ,获得省部级科学技术进步二等奖 2项、三等 奖 3项. 发表学术论文 31篇 ,其中 9篇被 EI收录. 张艳双 ,男 , 1984 年生 ,硕士研究 生 ,主要研究方向为通信与信息系统、 无线传感器网络、人工智能. 第 2届智能机器人与应用国际会议 The 2nd International Conference on Intelligent Robotics and Applications The 2nd International Conference on Intelligent Robotics and App lications ( IC IRA2009) will be held at O rchard Hotel, Singapore in 16218, December 2009. ICIRA2009 conference welcomes contributions of quality papers p res2 enting new research, new app lications, and new technological developments at the hardware and /or software levels for intelligent and autonomous robots. Im portant Da tes: Subm ission of Full Papers: 15 June 2009 Paper Accep tance: 15 August 2009 Subm ission of Final Papers: 15 Sep tember 2009 Early Bird Registration: 30 Sep tember 2009 Technical Program: 30 Sep tember 2009 Conference: 16 - 18 December 2009 E2ma il: james. lee@ robotics. sg W ebsite: http: / /icira2009. robotics. sg/index. php 第 1期 毕晓君 ,等 :基于免疫算法的无线传感器网络路由算法 ·71· © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
