基于遗传聚类的无线传感器负载均衡路由算法

朱永娇，阎巍，左伟明

（1.长沙学院计算机科学与技术系，湖南长沙410003；2.湖南城市学院计算机科学系，湖南益阳413000）

无线传感器网络是一种新兴的无线网络，由部署在监测区域内的大量廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织网络系统，可用于感知、采集和处理网络覆盖区域中各种环境或感知对象的信息，并以无线方式传送到用户终端，其应用前景十分广阔[1]。但由于无线传感器节点能量有限，因此如何减少节点能量消耗，均衡使用网络能量来最大化网络生存时间成为无线传感器网络路由协议设计的重要目标[2-3]。节点聚类是一种有效的无线传感器网络路由协议设计手段，可用来增加网络的可扩展性和延长网络寿命。LEACH算法[4]是一个经典的延长网络寿命的自适应聚类协议，其执行过程是周期性的，每轮循环由节点分簇和稳定的数据通信阶段组成。基本思想是通过让各节点等概率的随机循环担任簇头，使得网络中的节点相对均衡地消耗能量，从而达到延长网络生命周期的目的。但是，从全局的角度来看，算法未能优化簇头数目，且簇头在网络中的分布是非均匀的，所有簇头直接和基站通信，对于远离基站的簇头其能量损耗很快，没能有效延长网络生存周期。刘新华等[5]提出一种分布式定向分簇算法用于无线传感器网络负载均衡，算法首先基于节点能量预评估因子将网络分割成适当的分区，然后在每个分区中根据节点在本轮的负载能力预评估因子选取簇，从而达到网络中各节点能量均衡消耗的目的，但未考虑到分簇过程中最优簇头数目的确定。为了减少传输过程中冗余数据的通信开销，均衡全网能量的消耗，文献[6]从通信协议的角度出发，提出一种链式分簇路由协议。在成簇过程中，基站利用集中式控制依据地理位置将整个网络事先划分成大小相等相邻且不重叠的方形区域，在簇内采用链式拓扑，簇头间有效构造路由树，远离基站的簇头通过多跳的方式将数据最终通过根簇头传送到基站，使簇头节点能量消耗更均衡，但该算法簇内成链时未能考虑节点能量信息，不能够适应负载动态变化的情况。E.Akhtarkavan提出一种能量自适应的簇首选择机制[7]。算法综合考虑节点分布密度与节点到能量块中心距离来优化簇首的选择，以均衡了点能量消耗，但算法在节点成簇时没有充分考虑到节点剩余能量，且假定传感网节点服从正态分布，算法性能有待进一步提高。笔者将K均值算法的局部寻优能力与遗传算法的全局寻优能力相结合，提出一种基于遗传聚类的无线传感器网络路由算法，算法能克服传统无线传感器网络分簇路由算法分簇的局部性和对初始中心的敏感性，实现了传感器网络节点自适应成簇，分簇过程中较好地考虑了各节点能量均衡消耗，从而延长无线传感器网络生命。

1 K均值聚类与遗传算法基本思想

K均值聚类是一种广泛使用的聚类算法[8]。该算法把n个对象分为K个簇，算法首先随机选择K个对象，每个对象代表了一个簇的平均值或中心，对剩余的每个对象根据其与各个簇中心的距离，将它划分到最近的簇，然后重新计算每个簇的平均值，不断重复这一过程，直到准则函数开始收敛为止。该算法以方差平方和准则为基础，其准则函数如下：

遗传算法是一种模拟生物遗传和进化过程演化而来的自适应群体搜索技术[9]。它采用随机寻优方法，通过对当前群体施加选择、交叉、变异等一系列遗传操作，产生新一代的群体，并逐步迭代使群体进化到包含最优解或近似最优解的状态。由于遗传算法的整体搜索策略和优化搜索方法的计算不依赖于梯度信息或其他辅助知识，只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，已广泛应用于组合优化、生产调度问题、自动控制、机器学习、图像处理、人工生命、遗传编码和机器学习等领域。

2 基于遗传聚类的无线传感器路由算法

笔者将遗传算法与K均值聚类相结合，应用到无线传感器网络分簇路由算法的节点分簇中，利用遗传算法的全局优化能力克服聚类算法的局部优化特性，从而避免传感器网络节点分簇的局部性，实现传感网的最分簇与节点能量均衡消耗。算法主要步骤设计如下：

1）根据节点能量确定最优簇数；

2）遗传编码与初始种群随机生成；

3）对当前种群的每个个体,用K均值方法将其优化为以该个体为初始值的K均值问题的局部最优结果；

4）对这些局部最优个体进行选择、交叉、变异操作，产生新一代种群；

5）计算新一代种群的适应度，若到达最大代次数或者满足适应度要求，执行步骤6）；否则，转去执行步骤3）；

6）输出聚类结果。

2.1 最优簇数确定

在对传感网节点进行遗传聚类前，应先确定最优分簇个数。假设N个传感器分布在面积为A的平面区域内，则有节点分布密度为：

假设整个传感网络被分成K个簇，下面考虑确定一个最优簇数K使得从每个传感节点收集到1 bit信息的总能量消耗是最小的，显然每个传感节点发送1 bit信息到汇聚节点的总能量消耗E（K）为：

其中Esh为各节点传送1 bit信息到其簇头的能量消耗，Ehsi表示簇头传送1 bit信息到汇聚节点的能量消耗。又据Heinzelman等[10]分析可导出:

其中αt，αr分别表示节点传送和接收单位比特信息的能量消耗，ε为传送放大器传送单位比特每米能量消耗，L、D分别为节点到其簇头的距离和各簇头到汇聚节点的平均距离。

于是，由式（3）、（4）有：

当传感器在监测区域内均匀分布时，可求得节点到其簇头距离期望值为：

用式（6）替换式（5）中L，并对E（K）求关于K的导数，且令其为零，解出其极值点，即得最优簇数Kμ，

2.2 遗传编码和初始种群生成

确定好节点分簇个数后，就可用遗传算法选出合适的簇头。文中首先将各种可能网络拓扑编码成染色体，于是在编码阶段至少个染色体。每个染色体用一个长度为N的二进制串S表示，每个比特位对应一个节点，如果节点i被选作簇头，则二进制串S中对应的第i位比特被设定为1；否则被设定为0。从个染色体中随机选取q个作为初始种群。

2.3 传感器网络节点分簇

以当前种群的编码值为中心，把每个节点分配到最近的类，形成新的聚类划分。然后按照新的聚类划分，计算新的聚类中心，取代原来的编码值。因为K均值较强的局部搜索能力，能较大提高遗传算法的收敛速度。本文聚类（分簇）准则是寻找Kμ个划分使得无线传感器网络中数据传输能耗最小，即：

其中Eji为节点j传送m bit信息到其簇头i的能量消耗，Eis表示簇头i传送m bit信息到汇聚节点的能量消耗。令传感节点j到其簇头i的距离为dji，则由式（4）有：

因此，为了最小化聚类准则函数J，就必须将传感器节点划分到某个簇内，以使得该节点传送数据到其簇头的能耗最小。

2.4 适应度函数的选取

适应度通常用来度量群体中各个体在优化计算中可能达到或接近于最优解的优良程度。每一次聚类划分后，每个染色体计算其适应度，最适合的染色体代表了传感器网络的最优划分。为了均衡传感器网络不同簇间的能量消耗，应使得各簇内的节点数尽可能均等，故定义个体S的适应度函数为：

其中ni表示第i个分簇内节点数，

2.5 遗传算子

1）选择操作为让遗传算法能够获得全局最优解，采用随机选择,最佳个体保留的方式。首先在每一代开始时，将群体中的最优个体记录下来。然后根据各个体的适应度计算其被选中的概率，适应度小的个体选择概率也较小并可能被淘汰，而适应度大的个体具有较大的选择概率，随机选择的过程采用了旋转轮盘方式进行选择。最后在每次遗传操作后形成新种群时用当前所记录的最优个体替换新种群中的最差个体，以防止遗传操作破坏当前种群中适应度最好的个体。

2）交叉操作随机选取两条染色体（两个二进制字符串），并随机生成一个整数c，1≤c≤N-1，将第一条染色体中的前c个基因与第二条染色体中的后N-c个基因组合在一起，形成新的染色体。检查新染色体对应的二进制串中1的个数是否为Kμ，若是，新的染色体成为新一代种群成员之一；否则丢弃该染色体，重复执行交叉操作。其中交叉率pc的选择决定了交叉操作的频率，频率越高，收敛速度越快，因此一般选取较大的交叉率，但过高的频率也可能导致过早收敛，一般的取值为0.4～0.9[11]，实验中设定交叉概率为0.6。重复交叉操作直到新一代种群中个体数达到q个。

3）变异操作变异是一种局部随机搜索，与选择、交叉重组算子相结合可以保证遗传算法的有效性，使其具有局部随机搜索能力，同时保持种群的多样性，防止非成熟收敛。设变异率为pm，以概率pm随机选取一个体，随机选取其中一部分基因（二进制比特位）进行变异操作（即按位取反），若变异后的新个体中1的个数不等于Kμ，则舍弃该个体。继续变异操作，直到新一代种群中有q′个新个体。遗传过程结束后，对新一代群体中这些个体进行比较，将最优个体作为结果输出。

2.6 数据传输阶段

首先，簇内各节点将采集的数据发送给其对应的簇头节点；然后，簇头将接收的数据经融合处理后经过单跳路由传输至汇聚节点，以完成数据传送。

3 实验仿真与分析

实验仿真程序采用matlab编写，实验中，在100 m×100 m区域内随机安放100个节点，基站的坐标为（50，50）。每个节点初始能量为0.5 J，数据包大小为16 000 bit，节点传送单位比特信息的能量消耗αt＝50 nJ/bit，节点接收单位比特信息的能量消耗αr＝50 nJ/bit，传送放大器传送单位比特每米能量消耗ε=100 pJ/（bit·m-1）。实验中假设通道无碰撞，媒体中无丢包现象，网络中所有节点是同构的，且在分簇开始时其接收电路打开，当网络划分完成后，由汇聚节点唤醒一部分节点。

为对传感器网络进行遗传分成优化划分，就要确定迭代次数（遗传代数）。图1给出了不同迭代次数时各分簇间平均节点差。从图中曲线走势可看出，遗传代数越多，则网络分簇越趋近于均衡，当迭代次数为3 000时，网络划分趋近于最优，所以仿真实验中取迭代次数为3 000次。

图1 不同遗传代数下簇间节点数平均差Fig.1Average difference of the node quantity among clusters under different numbers of generations

图2给出了3种不同算法的能耗性能比较。从图中可以看出：在相同的时间里,本文算法的网络能耗比CCR协议[6]和LEACH算法[4]都要少。而且该算法的网络能耗随时间的增长率比较稳定，说明由遗传聚类组织的网络能量消耗比较均衡，这是由于遗传聚类能确定最优簇头，找出网络优化划分，以使得各簇间负载均衡。

图2 各算法能耗比较Fig.2Comparison of energy dissipation under different algorithms

图3为节点存活数与网络生存时间的关系图，其中LEACH算法[4]在网络生存800轮后节点已全部死亡，CCR协议[6]在1 200轮时节点消耗殆尽，而本文算法则在网络生存约1 400轮后所有节点才耗尽能量。这说明本文算法节点消亡速率最慢。实际上，若将网络中出现第一个失效节点的运行时间定义为网络寿命，则LEACH算法寿命为354轮，CCR协议为549轮，本文算法为783轮。可见本文算法网络寿命比LEACH协议提高了约121%，比CCR协议提高了约43%。这是由于本文算法将遗传算法的全局寻优能力与K均值聚类的局部优化能力相结合，实现了网络优化划分，延长了网络生存时间。

图3 不同算法节点消亡速率比较Fig.3Comparison on the nodes death rate of various algorithms

4 结束语

笔者提出一种负载均衡的无线传感器网络路由算法，充分结合了K均值算法的局部搜索特性与遗传算法的全局寻优能力，利用遗传聚类思想以确定最优簇数，并对无线传感器网络进行优化分簇，使得各不同簇间负载趋于均衡。仿真实验表明，该算法可有效均衡节点能量消耗和延长网络生存时间，与其他分簇路由算法相比，其网络寿命延长了约43%。

[1]沈玉龙，徐启建，裴庆，等.基于栅格的无线传感器网络路由方法[J].通信学报，2009，30（11A）:96-100.SHEN Yu-long，XU Qi-jian，PEI Qing，et al.Wireless sensor network routing method based on grid[J].Journal on Communications，2009，30（11A）:96-100.

[2]赵彤，郭田德，杨文国.无线传感器网络能耗均衡路由模型及算法[J].软件学报，2009，20（11）:3023-3033.ZHAO Tong，GUO Tian-de，YANG Wen-guo.Energy balancing routing model and its algorithm in wireless sensor network[J].Journal of Software，2009，20（11）:3023-3033.

[3]黄琛，房鼎益，陈晓江.传感器网络中基于非均匀分簇负载均衡路由算法[J].计算机应用研究，2009，26（9）:3475-3477.HUANG Chen，FANG Ding-yi，CHEN Xiao-jiang.Novelloadbalanced routing algorithm for multi-hop sensor networks[J].Application Research of Computers，2009，26（9）:3475-3477.

[4]Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless sensor networks[C]//Proceedings of the 33rd Hawaii International Conference on System Sciences，2000:10-20.

[5]刘新华，李方敏，旷海兰，等.一种基于负载均衡的无线传感器网络分布式定向分簇算法[J].计算机研究与发展，2009，46（12）:2044-2052.LIU Xin-hua，LI Fang-min，KUANG Hai-lan，et al.A distributed and directed clustering algorithm based on load balance for wireless sensor network[J].Computer Research and Development，2009，46（12）:2044-2052.

[6]潘志芳，章勇，刘大伟.一种链式分簇的无线传感器网络路由协议[J].传感器与微系统，2009，28（6）:10-12，15.PAN Zhi-fang，ZHANG Yong，LIU Da-wei.Energy-eficient chain-cluster routing protocol for wireless sensor networks[J].Transducer and Microsystem Technologies，2009，28（6）:10-12，15.

[7]Akhtarkavan E，Shalmani M T M.Energy adaptive clusterhead selection for wireless sensor networks using center of energy Mass[C]//Proceedings of 13th International CSI Computer Conference（CSICC 2008），Kish Island，Iran，2008:130-137.

[8]苏锦旗，薛惠锋，詹海亮.基于划分的K-均值初始聚类中心优化算法[J].微电子学与计算机，2009，26（1）:8-11.SU Jin-qi，XUE Hui-feng，ZHAN Hai-liang.K-means initiall clustering center optimal algorithm based on partitioning[J].Microelectronics&Computer，2009，26（1）:8-11.

[9]朱思峰，王华东，魏荣华.一种新型免疫遗传算法[J].计算机工程与应用，2009，45（36）:29-31.ZHU Si-feng，WANG Hua-dong，WEI Rong-hua.Immune genetic algoithm based on antibody[J].Computer Engineering and Applications，2009，45（36）:29-31.

[10]Heinzelman W，Chanrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans.On Wireless Communications，2002，1（4）:660-670.

[11]陶文兵，田金文，柳健.基于遗传算法和模糊熵的前视红外图像分割[J].红外与毫米波，2003，22（6）:465-468.TAO Wen-bing，TIAN Jin-wen，LIU Jian.Segmentation of flir images by genetic algoithm and fuzzy entropy[J].Infrared Millimeter and Waves，2003，22（6）:465-468.