基于遗传策略的无线传感器网络分簇路由优化

周 强

(滁州学院计算机科学与技术系,安徽滁州239012)

基于遗传策略的无线传感器网络分簇路由优化

周 强

(滁州学院计算机科学与技术系,安徽滁州239012)

分析了无线传感器网络的特点及各种路由协议的优缺点,将改进的遗传算法方案应用到无线传感器网络分簇路由优化问题中,在满足传感器网络约束条件的基础上智能地计算出最佳路由,使通信距离最小化。模拟实验的结果表明,本文提出的算法方案在解决无线传感器网络路由优化问题中具有良好的综合求解能力。

无线传感器网络;遗传算法;分簇

0 引言

无线传感器网络(w ireless sensor netwo rks,WSN)是由部署在监测区域内大量廉价的微型传感器节点组成,通过无线通信的方式形成的一个多跳的自组织的网络系统,其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息,并发送给观察者[1]。WSN实现了互联网与物理世界的连通,极大扩展了人类的认识能力,填补了互联网和物理世界不能互联的缺憾,在用户、互联网和物理世界之间架起了一座桥梁。然而在WSN中,节点能量有限并且一般没有后备能源补充,因此,在以多跳为基本特点的传感器网络中,如何以能量消耗问题为考虑的重点,探讨寻找源节点和目的节点间的优化路径,将数据分组沿着优化路径正确转发是这类网络最重要的问题之一。由于传感器网络的应用环境千差万别,具有很强的应用相关性,不同应用中的路由协议可能差别很大,因此并没有通用的路由协议。

传感器网络由基站和大量的节点组成,节点任意部署在被监测区域内,这一过程往往是通过飞行器撒播、人工埋置和火箭弹射等方式完成的,节点以自组织的形式构成网络。根据结点数目的多少和最终形成的拓扑结构,可以划分为平面路由协议和分簇路由协议。平面结构的网络比较简单,所有节点的地位平等,不存在等级和层次差异,是对等式结构。源节点和目的节点之间一般存在多条路径,网络负荷由这些路径共同承担,一般情况下不存在瓶颈,网络比较健壮。但其最大的缺点是网络中没有管理节点,缺少对通信资源的优化管理,自组织协同工作算法复杂,对网络动态变化的反应速度较慢等[2]。

在分簇路由协议中,传感器网络被划分为多个簇(cluster)。每个簇由一个簇头(cluster head)节点和多个簇成员(cluster member)节点组成。簇头主要负责簇间的数据的转发,簇成员只负责数据的采集,这大大减少了网络中路由控制信息的数量,因此具有很好的可扩充性。其主要缺点是簇头的能量消耗问题,簇头发送和接收报文的频率要高出普通结点的几倍至几十倍,会消耗更多的能量,并且很难进入休眠状态,一般可以通过在簇内更换簇头的方式克服此问题。目前主要的分簇路由协议有麻省理工学院的Heinzelman等人为WSN设计的低功耗自适应聚类路由协议LEACH,这是WSN中最早提出的分簇路由协议;阈值敏感的高能效传感器网络协议,这是WSN中第一个响应型通信协议;传感器信息系统中的高能效采集协议PEGASIS,这是在LEACH的基础上发展起来的基于“链”的路由协议。

使用分簇路由机制具有以下优点[3]:第一,簇头构成一个上层连通网络负责数据的长距离路由转发,而成员节点则可在空闲时关闭通信模块;第二,成员节点的功能比较简单,无须维护复杂的路由信息,而簇头融合成员节点的数据后再进行转发,减少了数据通信量,从而达到节省网络能量的目的;第三,分簇的拓扑结构有利于管理和分布式算法的应用,并可对系统变化作出快速反应,具有良好的可扩展性,适合大规模网络。

在实际应用中,由于传感器中的节点数目较多,对分簇结构网络路由进行优化的计算复杂度与节点数量的级数成正比,因此是一个典型的NP难题,无法用穷举法等精确方法求解。遗传算法(Genetic A lgo rithm,GA)是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化、并具有广泛适用性的概率搜索方法,虽然不一定会求得最优解,但可以在短期内获得近优解或最优解,具有实际应用价值。GA模拟了达尔文自然选择生物进化过程的计算模型,它由美国密歇根大学的John Holland教授首先提出,算法模拟物种从低级到高级的演化过程,从初始种群开始,采用优胜劣汰的自然法则,通过对种群施加遗传操作实现个体结构的重组的迭代过程,最终达到某种形式上的收敛,适用于求解NP难题。Turgut等在文献[4]中提出在Ad hoc网中引入GA来提高聚类算法的性能,Jin等人在文献[5]中提出利用GA来实现无线传感器网络中的能量优化问题,Ferentionos等人在文献[6]中通过对遗传算子的改进对Jin的算法进行了扩展,但以上算法仍存在收敛速度慢或容易陷入局部解等问题。本文主要将改进的GA应用到传感器网络分簇路由优化问题中,在满足传感器网络约束条件的基础上智能地选择出最佳路由方案,使通信距离最小化,从而达到高效地使用传感器节点的能量和最大限度地延长网络生命周期的目的。

1 问题描述

在如图1所示的分簇路由拓扑结构机制中,网络中的节点分为簇头节点和成员节点。在每个簇中首先根据一定的算法选出某个节点作为簇头,它的主要作用是管理或控制簇内成员节点,协调成员节点之间的工作,负责簇内信息的收集和数据的融合处理以及簇间信息的转发等。

图1 传感器网络的分簇结构图

假设网络中有1个基站,已被选出有N个簇头节点H1,H2,…Hn,同时存在M个成员节点M1,M2…Mm,所有节点位置已经固定,每个成员节点与一个簇头建立通信联系,每个簇头直接与基站连接。研究和实践表明传感器网络在传输环节消耗了大部分的能量,因此问题的目的是确定每个成员节点与哪个簇头节点连接使得网络通信总距离最小。由于簇头的能量有限,因此约束条件为每个簇头最多只能与K个成员节点通信。

数学模型如下:

其中(x,y)是问题的一个可行解,即满足约束条件的所有节点位置{(x1,y1),(x2,y2),…(xn,yn)},F是适应度函数,即解的优劣程度或适应度的一种度量。

2 基于遗传策略的分簇路由优化方法

2.1 染色体编码

为便于描述问题,算法采用自然数编码,假设网络中有8个成员节点和4个簇头节点,某个体的1～8个成员节点分别连接到编号为3、2、2、1、2、3、4、1的簇头节点,则该个体的基因序列为32212341。为保证产生的解满足约束条件,因此需要建立基因控制表控制染色体中基因出现的次数,此处控制表的值是2321。

2.2 适应度函数

为简化问题,本算法采用通信距离作为权值。假设第t代群体中第x个个体的第i个成员节点到第j个簇头节点的距离为dij,第j个簇头节点到基站的距离为sj,若第i个成员节点通过第j个簇头节点连接到基站则设置Lij= 1,否则设置Lij=0,能量消耗值可表示为:

为保证适应值大的个体被选择,适应度函数设为:

2.3 跳跃基因算子

本文使用了文献[7]提出的跳跃基因遗传算法(JGGA)的一种操作算子,主要目的是当基本的遗传算子在群体中进行全局搜索时,让跳跃基因(JG)算子围绕染色体进行局域搜索,使其能在进化过程中对计算结果进行微调。

JGGA模拟了由研究玉米遗传学的诺贝尔奖获得者麦克林托克提出的跳跃基因现象。研究发现9号染色体在遗传时经常会在相同的位置断裂,并且发现有一种非自治的可移动基因Ds,在一种自治的可移动基因A s的作用下,可以在相同或不同染色体中从一个位置移动到另一个位置。JG的行为与其它算子一样都是基于概率而发生,并且在相同或不同染色体中进行转移也是随机的,染色体的选择没有限制。为了将JG与GA框架相融合,本算法将跳跃基因算子在选择操作之后引入,即在交叉操作发生之前实施。JGGA的执行方法是每个染色体中都有一段连续的基因被选为“转座子”,其数量可以大于1。“转座子”的位置是随机分配的,并可以在群体中相同或不同的染色体间转移,执行方法如图2所示。本文算法中转座子仅在相同染色体中移动。

图2 跳跃基因的执行方法

2.4 交叉算子

研究和实验表明,在群体进化后期,在染色体中出现了很多相同的基因块,即优良基因块,经过交叉操作后,这些基因块又被分开了很多次,从而出现了更差的个体,因此本文采用了文献[8]提出的改良交叉算子,首先把优良基因块直接复制到子代个体的对应位置中,然后两个父代再进行单点或多点交叉产生新的子代,保证了进化后期个体中的优良基因块不会被破坏。

2.5 其它遗传操作

本文算法随机生成初始群体,使用排序选择和最优保留策略,在进化后期采用改进的单点交叉操作,对每个个体采用随机位变异操作,本文的跳跃基因算子应用于选择操作与交叉操作之间进行,改进的交叉算子在第200代后开始执行。

3 实验结果及分析

用Visual C++编程实现上述算法,实验中首先确定基站的位置坐标为(50,50),然后随机确定10个簇头节点和20个成员节点的位置坐标,如表1所示。

实验中设定的约束条件为每个簇头最多只能与4个成员节点通信。遗传操作的种群规模S为50,交叉概率Pc为0.65,变异概率Pm为0.05,运行代数G为500代,为验证改进的遗传算法的效果,分别用标准遗传算法(SGA)与本文改进的遗传算法(HGA)在相同参数的条件下进行对比实验,两种算法各10组实验结果各不相同,但总体趋势一致。利用本文提出的HGA算法计算所得最优解为894.3,拓扑结构图如图3所示,远于标准遗传算法SGA计算的最优解926.2。图4显示两种算法计算的最优解随代数变化的情况,可见本文算法求解结果明显优于标准遗传算法。

表1 随机产生的传感器网络中各节点的位置坐标

4 结论

本文针对传感器网络分簇路由优化问题提出了一种改进的遗传算法。所提算法利用了跳跃基因算子围绕染色体进行局域搜索,使其能在进化过程中对计算结果进行微调,并改进了交叉算子,避免了进化后期个体中的优良基因块被破坏的情况,使得算法具有综合求解性能强的特点。通过对假设的传感器分簇路由优化问题进行仿真实验,计算结果显示本文算法的收敛速度和得到的最优解明显优于标准遗传算法,验证了本文算法的优良求解能力和在传感器网络优化问题中的实际应用价值。

[1] 孙利民,李建中,陈 渝,等.无线传感器网络[M].北京:清华大学出版社,2005.

[2] Yu HB,Zeng P,Wang ZF,et al.Study of communication p rotocol of distributed Sensor network[J].Journal of China Institute of Communication,2004,25(10):102-110.

[3] Akkaya K.Younis M.Asurvey of routing p rotocols in wireless sensor networks[J].Ad Hoc Networks,2005,3(3):325-349.

[4] D.Turgut,S.K.Das,R.Elmasri,and B.Turgut.Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic app roach[C].In Proceedingsof the Global Telecommunications Conference(GLOBECOM),November 2002.

[5] S.Jin,M.Zhou,and A.S.Wu.Sensor network optimization using a genetic algo rithm[C].In Proceedings of the 7th World M ulticonference on Systemics,Cybernetics and Informatics,2003.

[6] K.P.Ferentinos,T.A.Tsiligiridis,and K.G.A rvanitis.Energy op timization of w ireless sensor netwo rks for environmentalmeasurements[C].In Proceedings of the International Conference on Computational Intelligence for Measurement Systems and Applications(CIMSA),July 2005.

[7] Ripon K.S.N.,Tsang C.,et al.An Evolutionary Approach for Solving the Multi-Objective Job-Shop Scheduling Problem[J]. Studies in Computational Intelligence,2007,49:165-195.

[8] 周 强,崔逊学.一种不确定条件下的多目标流水车间调度优化算法[J].模式识别与人工智能,2009,22(1):101-107.

Clustering Routing Optimization of Wireless Sensor Networks based on Genetic Strategy

Zhou Qiang
(Department of Computer Science and Technology,Chuzhou College,Chuzhou 239012,China)

This paper analyzes the characteristics of w ireless senso r netwo rks and the strengths and weaknesses of various routing p rotocols.A hybrid genetic algo rithm is p roposed to solve the clustering routing op timization p roblem s of w ireless sensor networks,so it can intelligently calculate the op timal route on the basisof the constraint satisfaction of w ireless sensor networks,and minimize the communication distance.The results of simulation experiments have show n that this algorithm and scheme p roposed in the paper can p rovide a good perfo rmance fo r the p roblem s.

w ireless senso r netwo rk;genetic algo rithm;clustering

book=0,ebook=5

TN92

A

1673-1794(2010)02-0023-03

周 强(1978-),男,硕士,讲师,研究方向:智能计算、传感器网络优化。

安徽高校省级自然科学研究项目(KJ2009B140)、滁州学院自然科学研究项目(2008kj004B)

2009-12-11