第 ２７ 卷第 １１ 期 ２０１０ 年 １１ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏｌ．２７ Ｎｏ．１１ Ｎｏｖ．２０１０ 倡 基 于 遗 传 算 法 的 无 线 传 感 器 网 络 路 由 协 议 研 究 １， 钱焕延 １， 汪　峥 １， 王晓楠 １，２ 高德民 （１．南京理工大学 计算机学院， 南京 ２１００９４； ２．常熟理工学院， 江苏 常熟 ２１５５００） 摘　要： 针对无线传感器网络能量受限、建立高效路由困难等特点，将遗传算法应用于无线传感器网络路由协 议中，提出了一种快速构建无线传感器网络最优路径方法。 采用可变长度染色体编码，采取选择、交叉和变异操 作，充分利用基站的信息资源和强大计算功能，逼近无线传感器网络最优路径。 仿真结果表明，基于遗传算法的 无线传感器网络路由协议可以有效延长无线传感器网络的生命周期，改善网络性能。 关键词： 遗传算法； 无线传感器网络； 路由协议 中图分类号： ＴＰ３９３　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２０１０）１１唱４２２６唱０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１０．１１．０６１ Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ＧＡＯ Ｄｅ唱ｍｉｎ１， ＱＩＡＮ Ｈｕａｎ唱ｙａｎ１， ＷＡＮＧ Ｚｈｅｎｇ１， ＷＡＮＧ Ｘｉａｏ唱ｎａｎ１，２ （１．Computer School， Nanjing University of Science ＆ Technology， Nanjing ２１００９４， China； ２．Changshu Institute of Technology，Changshu Jiangsu ２１５５００， China） Abstract： Ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｅｎｅｒｇｙ ｌｉｍｉｔｅｄ， ｅｓｔａｂｌｉｓｈｅｄ ｅｆｆｅｃｔｉｖｅ ｒｏｕｔｉｎｇ ｄｉｆｆｉｃｕｌｔ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ， ａｐｐｌｉｅｄ ｓｕｃｈ ａｓ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ａ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ， ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｆａｓｔ ｃｏｎｓｔｒｕｃｔ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｏｐ唱 ｔｉｍａｌ ｐａｔｈ ｍｅｔｈｏｄ．Ｕｓｉｎｇ ｖａｒｉａｂｌｅ唱ｌｅｎｇｔｈ ｃｈｒｏｍｏｓｏｍｅｓ ｃｏｄｉｎｇ， ｓｅｌｅｃｔｉｏｎ， ｃｒｏｓｓｏｖｅｒ ａｎｄ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒｓ， ｍａｄｅ ｆｕｌｌ ｕｓｅ ｏｆ ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｓｏｕｒｃｅｓ ａｎｄ ｓｔｒｏｎｇ ｂａｓｅ ｃａｌｃｕｌａｔｉｎｇ ｆｕｎｃｔｉｏｎ， ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ａｐｐｒｏｘｉｍａｔｅ ｏｐｔｉｍａｌ ｐａｔｈ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌｓ ｃａｎ ｐｒｏｌｏｎｇ ｔｈｅ ｌｉｆｅ ｃｙｃｌｅ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ， ｉｍｐｒｏｖｅ ｔｈｅ ｎｅｔｗｏｒｋ ｐｅｒｆｏｒｍａｎｃｅ． Key words： ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ（ＧＡ）； ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ； ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ 是模拟自然选择和遗传的随机搜索算 遗传算法（ＧＡ）［１２］ 无线传感器网络是由一组传感器节点自组织而形成的一 的无线自组织网的网络路由协议不能直接应用于无线传感器 无线传感器网络最大的特点是节点能量有限且很难及时更换 机得到快速发展和广泛的应用。 其中遗传算法作为现代优化 0　引言 算法对复杂的组合最优化问题的求解具有普遍适用性。 法。 遗传算法解最优化问题计算效率高、适用范围广。 其主要 个多跳无线网络，无须固定网络支持，具有快速展开、抗毁性强 特点是直接对结构对象进行操作，不存在求导和函数连续性限 等优势，同时还具有自组织、多跳、动态拓扑和能量资源受限等 定，具有内在的隐并行性和更好的全局寻优能力。 采用概率化 特点。 它能够在人们无法接近的恶劣或特殊环境中工作，如地 的寻优方法，能自动获取和指导优化的搜索空间，自适应地调 震与气候监控、外层空间以及战场环境和信息采集系统建设 整搜索方向，无须确定的规则。 它模拟自然进化过程，具有并 等，是信息感知和采集的一场革命。 它与传统无线网络相比， 行搜索特征，利于对解的空间进行搜索，可以加快对解的搜索 速度。 电池，网络拓扑结构更加不稳定，这些特性使得以前研究很多 1　遗传算法在无线传感器网络中的研究介绍 网络中。 在将遗传算法应用于无线传感器网络方面，有很多的专家 针对无线传感器网络的特殊性，国内外学者对其路由协议 做了大量的研究。 其中很多路由协议是在 Ａｄ ｈｏｃ 网络协议的 学者做了大量的研究工作。 张玉等人 基础上，结合无线传感器特点进行了延伸。 其中有基于数据为 的无线传感器网络 ＱｏＳ 路由优化，通过改进算法来提高算法 ［２］、 ＥＭＲＳ［３，４］、ＶＬＭ２［５］、 的收敛性，速度快效率高。 但是在对路由编码时，采用了人类 ＤＰＴＢ６［６］、ＧｅｏＣａｓｔ［７］、Ｔｅａｍ Ｍｕｌｔｉｃａｓｔ［８］、Ｍｏｂｉｃａｓｔ［９］。 这些路由 遗传机制其染色体长度固定特点，对网络中的路径节点进行二 进制定长度编码，在实际模型中，一条最优路径不一定完全定 长。 周集良等人 合实现路由发现，如 Ｄｉｊｋｓｔｒａ 算法、Ａ倡 等。 这些最短 提出的基于遗传算法的 ＷＳＮＳ 多路径路由 优化，建立从源节点到目标节点的多条路由，在路径建立上选 路径算法可以称之为古典算法。 当前，现代智能算法借助计算 　　收稿日期： ２０１０唱０６唱０５； 修回日期： ２０１０唱０７唱１０　　基金项目： 江苏省自然科学基金资助项目（ＢＫ２００９１３３）；中国博士后科学基金资助项目 （２００９０４５１２１７） 　　作者简介：高德民（１９８０唱），男，江苏南京人，博士研究生，主要研究方向为无线传感器网络（ｇｄｍｎｊ＠１３９．ｃｏｍ）；钱焕延，男，江苏南京人，教授， 博导，主要研究方向为现代通信技术、网络安全；汪峥，男，江苏南京人，博士研究生，主要研究方向为无线传感器网络；王晓楠，女，江苏常熟人，副 教授，博士后研究生，主要研究方向为无线传感器网络． 协议通常采用最短路径算法与无线传感器网络实际情况相结 ［１］、谣传路由 中心的自适应路由协议 ［１０，１１］ 算法 ［１３］ 提出的基于遗传算法 ［１４］ 

高德民，等：基于遗传算法的无线传感器网络路由协议研究 ·７２２４· 　　　 第 １１ 期 择最短的和能量消耗最少的路径作为适应度函数，但是没有考 虑节点的剩余能量问题，虽然在短时间内建立的路径耗能较 少，当时间延长时，某些节点的能量迅速耗尽，建立起来的最优 路径寿命较短。 本文依靠遗传算法模型，同时根据无线传感器网络的特 点，将遗传算法融入到无线传感器网络路由协议中。 在形成无 线传感器路由时，不仅考虑通信节点间的距离，还考虑当节点 间距离增大时可能造成能量损耗的非线性增长，以及节点通信 能耗和节点剩余能量的问题，尽量减少节点能量消耗和避免监 测区域能量塌陷以及盲点的出现，使得建立起的路径根据实际 需要，在能量消耗、通信距离，节点最优性等方面找到平衡，最 终达到延长无线传感器网络寿命的目的。 通过遗传选择、交叉 和变异操作，使得种群快速收敛到最优路径。 本文也对求解无 线传感器网络最优路径提供新的思路。 2　无线传感器网络路由模型 2畅1　拓扑模型 拓扑结构优化问题的目标首先要保证网络连通性，也就是 任意两节点间存在有向路径。 网络的总耗能最小，节点的耗能 功率之和最低。 如果节点辐射半径超过一定阈值，能量会很快 耗尽，因此辐射半径超越阈值节点的数目最少也是目标之一。 根据以上内容，对无线传感器网络拓扑结构优化问题的形式化 描述如下： 将无线传感器网络抽象成一个带权的无向图 G ＝枙V，A枛。 其中：V 表示路网的节点集合 V ＝（V０，V１，…，VN －１），V１ 为源节 点，VN 为目标节点；A 表示节点间通信链路集 A ＝｛a１，a２，…， am｝。 d（vi，vj）表示节点 vi ～vj 的距离，源节点到目标节点之间 的一条链路的长度为 L。 （１） 可以用 t（vi，vj）来表示点 vi ～vj 的权值，该权值表示能量 消耗和距离因素。 遗传算法被用来寻找图 G 中节点 V１ 到目的 节点 VN 的能耗代价最小路径，同时将能耗均衡性考虑到其 中，本文中将寻路消耗和节点当前能量融入到适应度函数中。 根据无线传感器网络的硬件尺寸、价格和功耗限制，在本 文中假定：ａ） 每个传感节点有唯一的 ＩＤ 号；ｂ） 所有传感器节 点都有 ＧＰＳ 装置，具有定位功能；ｃ） 每个传感节点的发射功率 可调整；ｄ）无线传感器节点中除了源节点外剩余节点在性能 上是同等的。 由于无线硬件技术和低功率计算技术的发展和 进步，ｂ）ｃ）所作的假设是合理的。 2畅2　WSN 能量模型 少能量消耗，保持通信区域内的节点具有最大的生命周期。 在 实际应用中，从传感器节点能量的消耗过程中可以看出，节点 ［１５］。 要想延长区域生命周期，必须尽量减少通信过程中的 能耗问题。 在设计路由协议时主要考虑节点在通信时的能量 消耗情况。 节点的通信模块存在发送、接收、空闲和睡眠四种 ［１６］，不同的状态有着不同的能量消耗水平。 无线通信模 块在发送和接收状态时能量消耗最大，在空闲和睡眠时的状态 能量消耗可以忽略，因此在路由设计时最需要考虑节点在发送 和接收时的能量消耗情况。 用于通信 的 能 量 开 销 要 远 远 大 于 用 于 数 据 计 算 的 能 量 开 销 在无线传感器网络中的关键要考虑的因素是如何尽量减 L ＝ ∑ vi，vj∈V d（vi，vj） 状态 道模型 的能耗为 假设 节 点 每 接 收 一 个 单 位 的 信 息 量 需 要 的 能 量 为 i∈v，j∈ve（vi，vj） ＝ ∑ e（vi，vj） ＝E（ｒｅｃｅｉｖｅ） ＋E（ｓｅｎｄ）（i，j） 功耗） 信道模型和多经衰落（d４ E（ｒｅｃｅｉｖｅ），E（ｒｅｃｅｉｖｅ） ＝Eｅｌｅｃ；Eｅｌｅｃ 依赖于电子元器件诸如数字编码、 调制、滤波、信号扩频等因素。 节点在发送数据时，根据与相邻 节点的距离调整发射功率，所以发射能耗与距离远近有关，笔 者采用自由空间（d２ 功耗） 信 ［９］，假如距离 d 小于门限值 d０，则采用自由空间（ＦＳ）模 型；否则，采用多经（ＭＰ） 衰落模型。 在 vi，vj 两个节点相距 d 时，发送一条长度为 m 比特的信息的能耗为 E（ｓｅｎｄ）（u，t）．m ＝ mefsd２　 d ＜d０ （２） mempd４　d≥d０ 其中：efs、emp 均为常数。 在选择下一跳节点时，尽量将距离限 制在 d０ 以内，否则能耗将大大增加；另外，节点在接收到数据 后需要对数据进行整合处理，假设能耗为 ΔE，能耗主要是在数 据传输时消耗掉的，所以在本文中忽略 ΔE 的大小。 e（vi，vj） 表示节点 vi 到下一跳节点 vj 的总能耗，传输单位比特的信息 （３） 无线传感器网络路由协议的目标是路径上耗能最小，也即 希望获取一个最小的 Eａｌｌ：Eａｌｌ ＝ ∑ （E（ｒｅｃｅｉｖｅ） ＋ i∈v，j∈v E（ｓｅｎｄ）（i，j）），为了加强无线传感器网络健壮性，考虑节点的优 越性，不仅要考虑通信能耗，还要考虑节点的剩余能量。 定义１　假设节点 vj 的剩余能量为 ej，节点 vj 与 vi 通信能 量消耗具有对称性，接收和发送单位数据能耗均为 e（vi，vj）， 则定义节点 vj 的能量优越模型： （４） lij ＝eυ 其中：υ、ζ为常量。 υ、ζ的大小根据需要实际情况进行调整，分 别表示剩余能量与通信能耗的相对重要性，能量优越模型度量 标准综合考虑了节点的能量消耗以及节点的剩余能量，节点能 量消耗越小且剩余能量越大优越性越强。 在应用遗传算法得 到的路径中，笔者希望路径中拥有的优越节点个数越多越好。 3　遗传算法的应用 遗传算法包括编码、选择、交叉和变异操作。 对于选择操 作，考虑到每次进行交叉和变异都会产生一定数量的新个体， 笔者把新个体与原有个体混合在一起进行评价和选择，适应度 较高的染色体个体组成新一代个体。 图１ 为遗传算法路由模 型。 从图中可以看出，从源节点到达目标节点存在着多条通 路。 其中必有一条路径为最优路径。 遗传算法根据遗传理论 在种群延续中不断产生最优个体，依此寻找最优路径。 j ／e（vi，vj）ζ 3畅1　编码 针对网络路由问题的特殊性，考虑到路径存在变长的情况 下，本算法中，采用可变长度编码方案。 用节点 ＩＤ 号表示染色 体中的基因，源节点到目标区域的路径用相应的节点号序列表 示，即形成一个染色体。 这是一种基于路径表示的编码方法， 

·８２２４· 对于任何一个染色体，第一个基因总是信源节点，最后一个基 因总是信宿节点，同一个节点不会两次转发同一个数据包，所 以每个节点最多只能在路径中转发一次，染色体中不能有重复 的基因。 由于从源节点到基站需要中转的节点数不固定，因此 染色体的长度可变。 基站到目标节点形成多个染色体，多个染 色体组成的个体成为路径种群。 该方法很自然地体现了实际 的网络模型。 在染色体选择过程中，节点辐射半径 R 要符合信道模型。 当某一节点 R ＜R１ 时，R１ ＝d２。 该节点可以作为染色体的一部 分。 当 R１ ＜R ＜R２ 时，R２ ＝d４。 尽量减少该节点的使用，这一 点在下面适应函数中进一步进行说明。 3畅2　适应函数的确定 适应函数是用来衡量个体优劣的尺度。 遗传算法在进化 搜索中，仅以适应函数为依据，判断个体的优劣，因此函数本身 的优劣直接影响到遗传算法的可行性和收敛速度。 衡量路由 算法的性能主要以网络延时、可靠性、网络生命期等来判断，可 靠性通过多路径来保证，网络延时可以通过基站性能来调整。 所以延长网络生命期，只有通过优化路由来减少网络耗能才可 达到，耗能越少，适应值越高。 定义２　节点 １ 表示路径的初始节点，n 表示路径的终止 节点，xi，j作为指示变量满足以下条件： 最优路径问题首先满足路径长度尽可能地短，可以表示为 xi，j ＝ １　如果边（i，j） 在路径中 ０　其他 ｍｉｎ z１（x） ＝∑ i ∑ d（vi，vj）xi，j j 同时要能达到能量消耗尽可能地少，可以表示为 j i j j i j ∑ j ij ∑ 适应度函数可以表示为 ｍｉｎ z２（x） ＝∑ ｆｉｔｎｅｓｓ（x） ＝∑ ｓ．ｔ．∑ xij ＝∑ ∑ xi，j lij ｆｉｔｎｅｓｓ（x） ＝ｍｉｎ z１（x）ｍｉｎ z２（x）也即为 d（vi，vj） α xi，j lβ xij≤２，橙i∈V jn ＝１，橙i，j∈V （５） （６） （７） 适应度函数中 α和 β分别表示距离和节点的优越度的相 对重要性，当希望距离短优先时，α值设置较大，否则小于 β。 式（６） 确保除节点 １ 和节点 n 外的任何一个节点不存在或只 有两条相邻的边。 式（７）确保节点１ 和 n 是路径的端点。 3畅3　种群选取 初始种群的选取一般通过随机产生或通过其他方法构造。 为了避免早熟现象，本文在源节点到目标节点之间的一定宽度 路径上随机生成一组初始种群，采用最佳个体保存与比例选择 机制相结合的方法。 首先选出群体中 N 个适应度最高的最佳 个体作为保留染色体，将它直接遗传到子代群体中。 比例选择 算子是以正比于个体适应度值的概率来选择相应的个体。 设 群体大小为 n，个体 i 的适应度为 fi，fi ＝ｆｉｔｎｅｓｓ（ｐｏｐi（t））。 ｐｏｐi（t）为第 t 代染色体中第 i 个体，则个体 i 被选中的概 率 pi 为 pi ＝fi ／∑N j ＝１fi；i ＝１，２，…，N 以概率分布 pi 从 ＰＯＰ（t） 中随机选一些染色体构成一个 计 算 机 应 用 研 究 　 第 ２７ 卷 ｎｅｗＰＯＰ（t ＋１） ＝｛ｐｏｐi（t） ｜j ＝１，２，…，N｝ 种群 ｎｅｗＰＯＰ（t ＋１） 在本文中第一代群体中，设置有四个染色体，分别为 H１、 H２、H３、H４。 通过计算，假设 ＰＯＰ（１）中四个染色体的概率关系 为 p２ ＞p１ ＞p３ ＞p４。 如果 p４ 比 p３ 小很多，那么在新的种群中 H４ 被淘汰，新的种群 ｎｅｗＰＯＰ（２） 的染色体中的 H４ 变为 H４ ＝ H１。 3畅4　交配 交配方式在遗传算法中起着核心作用，新路径的优劣依赖 于交配操作。 遗传算法中包含有双亲双子法、变化交配法、多 交配位法和双亲单子法等方法。 考虑路由的特殊性，采用非常 规码的交配方法，具体方法为：在随机产生的两个个体串中随 机设置一个或多个交叉点，将染色体分成几个基因块，然后以 交叉概率 Pc 在交叉点处相互交换两个个体的部分染色体，从 而产生出两个新的个体。 交叉点的选择尤为重要，通常选择两个个体中出现相同的 基因处设置为交叉点，如果没有相同基因，则选择基因号码接 近处为交叉点，交叉点设置后将个体分成两个基因块，基因块 中还可以设置交叉点，将基因块再一次拆分。 考虑到路径中不 能出现重复的节点，如果在新产生的个体中出现重复的基因， 则将重复的基因删除。 3畅5　变异 变异可以保持群体的多样性，有利于产生更适应环境的个 体。 基因的变异表现为基因本身的变化和基因间顺序的变化。 通常选择粒度相对较小的基因变异作为个体变异的基本形式。 基因本身的变化会对局部路径收敛到最优，所以考虑基因间顺 序的变异和基因编号的变异。 也即变异后节点个数虽然不变， 但是当去掉重复节点时，实际长度不一样。 本文采用的变异方 法是路径中局部路径的变换，可以将局部路径看成基因块，通 模拟基因的变异。 本算法中，变异操作是为了随机获取新的链 路，因此不同于传统的取反运算。 在节点变异时，通常采用两 种方式，即节点交换次序和节点 ＩＤ 号变异。 4　仿真 在仿真环境中，随机产生１２０ 个无线传感器节点，无线传 感器节点随机分布在１５０ ×１００ ｍ２ 的平面区域，模拟场景如图 ２ 所示，所有节点的传输功率是可调节的，传感器节点根据实 际需要调节传输功率与其他节点进行通信。 数据包大小为 ５１２ Ｂｙｔｅ，元数据大小为 ２５ Ｂｙｔｅ，传输 １ｂｉｔ 消息时能量消耗为 E１ｂｉｔ ＝１nＪ／ｂｉｔ，传感器节点的初始能量 Eｓｔａｒｔ ＝１０ Ｊ，交叉概率 Pc ＝０．８，变异概率 Pm ＝０．１，υ＝１，ζ＝１。 仿真环境指定图中 一个为源节点，一个为目标节点，模拟场景如图２ 所示。 图３ 为种群收敛情况，本文随机设置２０ 个种群，每个种群 初始大小为２０ 个节点。 个体在变异后会使得个体的 ２０ 个节 点 ＩＤ 出现重复，重复节点之间不计算距离，可以满足个体为可 变长节点形成最优路径。 图３ 中以遗传１００ 和 ５００ 代进行对比。 当设置迭代次数 为１００ 时，种群还没有完全收敛，适应度值仍然出现较大波动。 当迭代次数为５００ 时，最优路径值完全收敛。 从图３ 中可以看 出在迭代次数为４８０ 时基本保持平稳，种群平均适应度为 ４２０ 过采用基因块中的基因的顺序交换和基因块中基因的变化来 

第 １１ 期 左右。 此时基站获取一条最优路径编号序列，信息从基站向目 标节点发送。 高德民，等：基于遗传算法的无线传感器网络路由协议研究 ·９２２４· 　　　 设计相应的遗传操作算子，通过优化种群选取、合理交叉、有效 变异，最终产生一条最优路径。 最优路径中对各参数因素设定 了不同的影响因子，在实际情况下，可以根据需要调整影响因 子的大小。 在计算最优路径时，虽然需要多次迭代完成收敛， 具有一定的计算量，但是模型中最优路径计算任务由计算能力 较强的基站完成，对普通节点的能耗影响较小，大大延长了普 通节点的生命周期。 仿真结果表明，该算法能够成功地建立一 条近似最优的路径。 参考文献： ［１］ ＫＵＬＩＫ Ｊ，ＨＥＩＮＺＥＬＭＡＮ Ｗ Ｒ，ＢＡＬＡＫＲＩＳＨＮＡＮ Ｈ， et al．Ｂａｓｅｄ ｐｒｏｔｏｃｏｌｓ ｆｏｒ ｄｉｓｓｅｍｉｎａｔｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［Ｊ］．Wireless Networks，２００２，223（８）：１６９２１５８． ［２］ ＢＲＡＧＩＮＳＫＹ Ｄ， ＥＳＴＲＩＮ Ｄ Ｒ．Ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ １ｓｔ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ ａｎ Ａｐｐｌｉｃｔｉｏｎｓ． Ａｔｌａｎｔａ： ＡＣＭ Ｐｒｅｓｓ，２００２：２２唱３１． ［３］ ＴＨＥＰＶＩＬＯＪＡＮＡＰＯＮＧ Ｎ， ＴＯＢＥ Ｙ， ＳＥＺＡＫＩ Ｋ．Ａｎ ｅｆｆｉｃｉｅｎｔ ｍｕｌｔｉ唱 ｃａｓｔ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］．IEIC Technical Report，２００５，104（６９０）：４１９唱４２２． ［４］ ＴＨＥＰＶＩＬＯＪＡＮＡＰＯＮＧ Ｎ， ＴＯＢＥ Ｙ， ＳＥＺＡＫＩ Ｋ．Ｔｒｅｅ唱ｂａｓｅｄ ｄａｔａ ｄｉｓｓｅｍｉｎａｔｉｏｎ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＩＣＥ Ｇｅｎｅｒａｌ Ｃｏｎｆｅｒｅｎｃｅ．２００５：４１唱４２． ［５］ ＳＨＥＴＨ Ａ， ＳＨＵＣＫＥＲ Ｂ， ＨＡＮ Ｒ．ＶＬＭ２：ａ ｖｅｒｙ ｌｉｇｈｔｗｅｉｇｈｔ ｍｏｂｉｌｅ ｍｕｌｔｉｃａｓｔ ｓｙｓｔｅｍ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ．２００３：１９３６唱 １９４１． ［６］ ＺＨＡＮＧ Ｗｅｎ唱ｓｈｅｎｇ， ＣＡＯ Ｇｕｏ唱ｈｏｎｇ， ＰＯＲＴＡ Ｔ Ｌ．Ｄｙｎａｍｉｃ ｐｒｏｘｙ ｔｒｅｅ唱ｂａｓｅｄ ｄａｔａ ｄｉｓｓｅｍｉｎａｔｉｏｎ ｓｃｈｅｍｅｓ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［Ｊ］．Wireless Networks，２００７，13（５）：５８３唱５９５． ［７］ ＫＯ Ｙ Ｂ， ＶＡＩＤＹＡ Ｎ Ｈ．Ｇｅｏｃａｓｔｉｎｇ ｉｎ ｍｏｂｉｌｅ Ａｄ ｈｏｃ ｎｅｔｗｏｒｋｓ： ｌｏｃａ唱 ｔｉｏｎ唱ｂａｓｅｄ ｍｕｌｔｉｃａｓｔ ａｌｇｏｒｉｔｈｍｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ ２ｎｄ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ．Ｗａｓｈｉｎｇｔｏｎ ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，１９９９：１０１唱１１０． ［８］ ＧＥＲＬＡ Ｍ， ＹＩ Ｙ Ｊ．Ｔｅａｍ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｍｏｎｇ ａｕｔｏｎｏｍｏｕｓ ｓｅｎｓｏｒ ｓｗａｒｍｓ［Ｊ］．ACM SIGMOD Record，２００４，33（１）：２０唱２５． ［９］ ＨＵＡＮＧ Ｑ，ＬＵ Ｃ Ｙ， ＲＯＭＡＮ Ｇ Ｃ．Ｍｏｂｉｃａｓｔ： ｊｕｓｔ唱ｉｎ唱ｔｉｍｅ ｍｕｌｔｉｃａｓｔ ｆｏｒ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｕｎｄｅｒ ｓｐａｔｉｏｔｅｍｐｏｒａｌ ｃｏｎｓｔｒａｉｎｔｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＰ唱 ＳＮ．［Ｓ．ｌ］：Ｓｐｒｉｎｇｅｒ唱Ｖｅｒｌａｇ，２００３：４４２唱４５７． ［１０］ 徐庆征，柯 熙 政．求 解 最 短 路 径 的 遗 传 算 法 中 若 干 问 题 的 讨 论 ［Ｊ］．计算机工程与设计，２００８，29（６）：１５０７唱１５０９． ［１１］ 王海梅，周献中．网络系统中的最短路径分析及其应用研究［Ｊ］． 兵工学报，２００６，27（３）：５１５唱５１８． ［１２］ ＣＨＥＶＩＬＬＡＴＰ，ＪＥＬＩＴＴＯＪ，ＢＡＲＲＥＴＯＡＮ，et al．Ａ ｄｙｎａｍｉｃ ｌｉｎｋ ａｄａｐ唱 ｔａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ＩＥＥＥ ８０２．１１，ａ ｗｉｒｅｌｅｓｓ ＬＡＮｓ［ Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ ＩＣＣ’０３．［Ｓ．ｌ．］：ＩＥＥＥ Ｐｒｅｓｓ，２００３：１１４１唱１１４５． ［１３］ 张玉，蔡红梅．基 于 遗 传 算 法 的 无 线 传 感 器 网 络 ＱｏＳ 路 由 优 化 ［Ｊ］．华北水利水电学院学报，２００９，30（４）：７５唱７７． ［１４］ 周集良，李彩霞，曹奇英．基于遗传 算 法 的 ＷＳＮＳ 多 路 径 路 由 优 化．计算机应用，２００９，29（２）：５２１唱５２４． ［１５］ ＥＴＴＵＳ Ｍ．Ｓｙｓｔｅｍ ｃａｐａｃｉｔｙ，ｌａｔｅｎｃｙ，ａｎｄ ｐｏｗｅｒ ｃｏｎｓｕｍｐｔｉｏｎ ｉｎ ｍｕｌｔｉ唱 ｈｏｐ唱ｒｏｕｔｅｄ ＳＳ唱ＣＤＭＡ ｗｉｒｅｌｅｓｓ ｎｅｔｗｏｒｋｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｒａｄｉｏ ａｎｄ Ｗｉｒｅｌｅｓｓ Ｃｏｎｆｅｒｅｎｃｅ．１９９８：５５唱５８． ［１６］ 玄光南，程润伟．遗传算法与工程优化［Ｍ］．北京：清华大学出版 社，２００４：１５７唱２３３． 图４ 为能量消耗比较，以传感器总能量消耗作为衡量指 标，用 ＧＡ 模型与泛洪模型与周集良等人提出的基于遗传算法 的 ＷＳＮＳ 多路径路由优化模型（ 简称 Ｚｈｏｕ 模型） 作比较，结果 表明，使用泛洪方式，随着时间的延长，能量消耗呈现剧烈陡峭 增长；Ｚｈｏｕ 模型中，随着时间的增加，能量消耗增长趋势比较 缓慢，这是因为在信息进行传输之前，由基站已经计算出一条 最优路径，信息只需沿着基站发出的信息包中所携带的路由标 注节点向目标节点转发即可，不会将信息发送给其他节点，所 以不会造成不必要的能量损耗。 在 ＧＡ 方式中，在开始时，能 量消耗接近 Ｚｈｏｕ 模型，但是随着时间延长，ＧＡ 模型的优势越 来越明显，这是因为在 ＧＡ 模型中，笔者考虑优越节点问题，使 得建立起来的路径中含有更多的优越节点，这样既能保证能量 消耗是逐步缓慢增长的，也可以达到延长该路径生命周期的目 的。 从总体来看，ＧＡ 模型的能量消耗速率与 Ｚｈｏｕ 模型相比， 能量的消耗得到了有效控制。 图５ 为基于遗传算法的无线传感器路径形成图，当遗传至 ５００ 代时，基站完成的最优路径发现。 5　结束语 本文引入遗传算法解决无线传感器网络路由协议问题，提 出了基于遗传算法的最优路径发现方法，根据无线传感器路由 特点，采用可变长度染色体进行路径编码。 适应度函数计算 上，综合考虑节点间通信能耗、节点剩余能量、节点通信距离等 因素，并且引入优越节点模型，同时根据无线传感器网络特点