李 伟，张凤梅

(西安邮电大学 自动化学院, 陕西 西安 710121)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)如何有效地降低网络能量消耗一直是受到国内外研究者重视[1]。当前无线传感网络路由算法可分为两类：分簇路由和平面路由算法。高效的路由算法能有效降低网络能量消耗，延长网络寿命。LEACH算法通过随机选举簇首来均衡网络中的能耗，但仍存在成簇不均匀，簇首选取不合理的问题。为解决该问题，文献[2]中的GEC算法提出引入K-Means(KM)聚类算法进行分簇，以欧氏距离[1]作为相似度测度，求对应某一初始聚类中心向量V的最优分类，使得评价指标J最小从而形成K个均匀分簇，但该算法对初始聚类中心敏感，算法需要指定参数K的值、输入不同K值随目标准则函数进行不同次数的迭代、聚类结果波动大易出现局部最优问题[3]。

本文对LEACH算法及GEC算法进行分析研究，提出KM-LEACH算法。首先通过引入KM算法对LEACH算法成簇过程中存在的问题进行优化，并结合遗传算法对KM算法中易陷入局部最优的问题进行改进。其次在簇首选取过程中，通过引入剩余能量和位置影响因子合理选取簇首。经仿真表明，KM-LEACH算法有效降低了网络中的能耗，延长了网络生命周期。

1 基于KM的分簇路由算法

1.1 LEACH算法

在LEACH算法引入“轮”的概念，周期性随机选举簇首，每轮分为簇首建立阶段和数据传输阶段。簇首建立阶段，网络中的各个节点会随机生成一个0～1的数。若随机数小于阈值T(n)[4]，则该节点成为簇首。阈值计算公式T(n)为

(1)

式中p为簇首百分比，r为当前轮数，mod为余数运算，G为最后1/p轮中未被选为簇首的节点集合。……