基于遗传算法的WSN谣传路由的改进

朱钱祥，孙志毅

(太原科技大学电子信息工程学院，太原030024)

无线传感器网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，现已广泛的应用于工业、农业和军事等方面。它布置大量而廉价的传感器节点到要监测的区域[1]，通过多跳的方式将监测到的信息传送到汇聚节点。由于传感器节点的工作环境的限制，它本身带有的电源是不可替换，因此节点的能量是有限的，如何高效的使用能量延长网络的寿命就成了无线传感器网络路由设计主要面对的问题[2]。

谣传路由[3]是Braginsky等人提出的适用于数据传输量较少的传感器网络的一种路由协议，它通过事件消息和查询消息随机产生的路径交叉生成源节点到汇聚节点的路径。该算法虽然克服了洪泛方式[4]建立转发路径所带来的“内暴”等问题，但却存在路径非最优化的问题，本文从能量消耗最优的角度出发，提出了一种基于遗传优化[5]的路由算法GARR(Rumor Routing based on Genetic Algorithm)。

1 相关定义

定义1 事件agent:从事件区域中心的节点(源节点)出发在网络中随机传播并产生一个事件路径，它包含有:发生事件的信息，距离源节点的跳数event_hop，生命周期event_ttl，所处节点的编号event_id，已产生的路径能量消耗量event_elec，以及产生一个禁忌表event_tabu(用来包含已经过的节点的编号)。

定义2 节点:无线传感器网络构成的基本元素，在本文中，各个节点都知道其坐标以及通信范围，并能根据节点之间的距离自发的调整其发射功率。它包含节点本身的初始能量node_elec，节点的编号node_id.各节点的邻居节点表node_neighbor(节点的通信范围内的所有节点编号)以及该节点到各个邻居节点的所需能量消耗值。

定义3 查询agent:从汇聚节点出发在网络中随机传播产生一个查询路径。它包含查询事件的信息，距离汇聚节点的跳数queer_hop，生命周期queer_ttl，所处节点的编号queer_id，已产生的路径能量消耗量queer_elec，以及产生一个禁忌表queer_tabu(用来包含已经过的节点的编号)。

定义4 完整的路径:当事件路径和查询路径产生交点时，通过这个交点连结两条路径行成一个从源节点到汇聚节点的完整的路由。

定义5 节点间的能量消耗:节点i和节点j间的能量消耗[6]:

Et(i，j)是节点i向节点j转发大小为kbit的数据包所消耗的能量，Er(j)是节点j接收大小为kbit数据包所消耗的能量，d为节点i和节点j之间的距离。

2 算法的设计

2.1 算法思想

如图1所示:当事件区域有事件发生时，其中心的节点产生事件agent，并在网络中心随机传播，同时汇聚节点产生查询agent，也随机产生一条路径，并和事件路径交叉行成一条新的路由。由于这两个agent是随机传播的，因此该路径可能产生回路并且非最优的，浪费了大量不必要的开销。由于遗传算法[7]不依赖于事件的连续性、可导性，只依赖于其评价函数的性质，对初始种群进行一代代的优化直至找到最优值，因此，利于遗传算法对多条从源节点到汇聚节点的路径组成的种群进行优化，通过交叉、变异操作[8]，产生最优的个体，也即最优的路由路径。

2.2 算法的步骤

初始的种群的产生

(1)当事件区域有事件发生，节点A产生50个事件agent，event(k)_hop为0，event_tabu包含有源节点A，每个agent移向下一跳节点，这个过程满足:

a.下一节点必须在事件agent所处节点i的邻居节点表node(i)_neighbor内。

b.下一节点必须不包含于该agent的禁忌表中(防止出现回路)。

图1 谣传路由Fig.1 Rumor routing

c.若是下一跳节点为孤立节点(也即该节点的通信范围内只有上一跳节点没有其它节点)，则执行回退策略，即返回到上一跳节点重新选择节点进行转移。

(2)当事件agent从节点i转移到节点j时，event(k)_hop 加 1，event(k)_ttl减 1，将节点i的编号添加到event(k)_tabu中，将所需的能耗cost(i，j)加到event(k)_elec中。

(3)事件agent按上述步骤进行移动直至event(k)_ttl变为0.

(4)同理，汇聚节点发送的查询agent在网络中转移的步骤如事件agent转移策略一样。

(5)事件agent和查询agent所产生的两条链路几个交点中，随机选择一个交点进行两条路径的连结，形成一个新的链路，对此链路进行回路的消除，产生一个新的从源节点到汇聚节点的路径though(k)。

(6)按照上述步骤产生50条路径作为初始的种群P，然后利用遗传算法对该种群进行优化。

遗传算法对路径的优化:

(7)对种群P中第k条路径进行适应值的计算，采用的适应值函数为:

(8)在种群P中选择最优的10条路径保存下来(取适应值最大的10条)，然后按轮盘法选择38条路径进行交叉操作产生38个新的个体，最后随机选择2条路径进行变异操作，这样就构成新的下一代的种群P.

交叉操作分为单点交叉和双点交叉两种，本文采用单点交叉，具体做法是:判断两条路径是否有相同的节点，若有一个或超过一个的相同点，随机选择一个相同点进行单点交叉，若没有相同点，则保持不变，交叉操作如图2所示。

图2 交叉操作Fig.2 Intersect operation

a是路径though(i)所经过所有节点的编号，b是路径though(j)所经过所有节点的编号，a和b中相同的节点有3和5(除掉源节点1和汇聚节点100)，随机选择一个节点作为交叉节点，在此，选择节点5作为交叉节点，产生了新的路径a1和b11.在路径a1中，存在着回路 3、5、6、8，消除该回路便产生了新了路径a11，将b11和a11作为新的个体保存到下一代种群中去。

变异操作:在路径i中随机选择一个节点作为变异节点，重新建立该节点到汇聚节点的路径代替原路径节点i后的节点编号。

(9)通过上述操作，由上一代的最优10个路径，交叉生成的38条路径，变异生成的2条路径组合成新一代的种群P，然后对此种群再进行选择、交叉、变异操作，直至适应值趋向于稳定时，此时适应值最大的路径为最优路径。

3 仿真设计与结果分析

使用MATLAB进行仿真，在200 m×200 m范围内放置100个节点，各个节点都是随机布置的，所有的节点一旦放置好了便不能移动，假设源节点坐标为(0，0)，汇聚节点的坐标为(200，200)，每个节点的初始能量都一样，εelec=5.0×10-9J/bit·m2，Eelec=5.0 ×10-9J/bit，数据包大小为4 000 bit.

图3是谣传路由算法和GARR算法所形成的两条路径。由仿真结果可知，谣传路由算法产生的路径传送一个数据包消耗的能量为10.383 5 J，而由GARR算法产生的路径传送一个数据包则消耗2.111 7 J，节约了近 78.7%的能量。

图4是种群代数和各代种群中最优个体(也即最优路径)传送一个数据包所消耗的能量之间的关系，由图可知，当运算到第34代时，得出的最优路径的就接近于最终的结果，由此可以看出，GRAA算法运算较少次便可计算出结果，运算所消耗的能量相比于通信消耗的能量可以忽略不记。

图3 GARR和RR产生的路径Fig.3 Paths generated by GARR and RR

图4 不同优路径消耗能量值Fig.4 The energy consumption of different paths

4 结束语

谣传路由是典型的基于数据查询的无线传感器路由，它克服了洪泛方式建立转发路径带来的开销过大的问题，但是由于其事件消息和查询消息的随机扩散，便产生了路径非最优的问题。本文提出的GARR算法采用了在事件消息和查询消息中加入了禁忌表的方式、采用遗传优化的思想计算出最优路径，减少了节点能量的使用，极大的延长的网络的使用寿命。

[1]ALYILDIV I F，SU W，SANKARASUBRAMANIAM Y，CAYIRCI E.A survey on sensor networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[2]戴世瑾，张翼德，李乐民.无线传感器网络的路由协议研究与分析[J].计算机应用研究，2006，23(12):294-297.

[3]BRAGINSKY D，ESTRIN D.Rumor routing algorithm for sensor networks[C]∥Proceeding of the 1st Workshop on Sensor Networks and Application.Atlanta:ACM Press，2002:22-31.

[4]INTANAGONWIWAT C，GOVINDAN R，ESTRIN D，et al.Directed Diffusion for Wireless Sensor Networking[J].IEEE/ACM Transactions on Networking，2003，11(1):2-16.

[5]郭绍永，谈 冉.遗传算法在无线传感器网络中的应用[J].微计算机信息，2009(10):125-127.

[6]吉云，徐玉斌.基于地理位置划分的无线传感器网络分簇算法[J].太原科技大学学报，2010，31(1):6-9.

[7]GOLDBERG D E.Genetic algorithms in search，optimization，and machine learning[M].New York:Addison Wesley，1989.

[8]周集良，李彩霞，曹奇英.基于遗传算法的WSNs多路径路由优化[J].计算机应用，2009.29(2):521-524.