杨友良，李艳辉

（河北联合大学，河北 唐山063009）

无线传感器网络通过大量布置在检测区域内的传感器节点采集网络覆盖区域内感知对象的信息，通过多跳的无线通信方式，将收集、处理后的信息提供给终端用户。由于传感器节点本身资源的限制，特别是WSN节点能量更为有限，因此研究分簇算法是必要的，LEACH算法［1］是最早提出的单跳分簇算法，其在无线传感器网络中占有举足轻重的作用。然而，为了能够更加有效的延长网络生命周期，我们必须研究新的分簇路由算法。

1 LEACH算法原理

无线传感器网络中的层次路由协议最大的特点便是采用分簇技术。利用此技术可以很明显的将整个网络内的所有节点分成簇首、簇内节点、汇聚节点三个层次［2］。其结构可表示为如图1所示。LEACH协议是由Heinzelman提出的层次型路由协议算法，其在无线传感器网络中占有举足轻重的作用。针对簇首过重的负担导致其很快失效这一问题，LEACH协议通过轮次的方法周期性的选择簇首。一旦节点成为簇首节点，它将会向整个网络广播其成为簇首的信息，传感器网络中的其它节点接收到整个网络中所有簇首的信息后，依据接收信息的信号强度，挑选出最强的簇首所在簇群加入。在进行数据信息通讯时，簇首、簇内节点、数据汇聚点三者之间的通讯采用单一的直接通讯方式，即簇首与簇内节点直接传送信息，簇首与数据汇聚点之间也是采用单跳的方式进行通讯。

图1 分簇结构示意图

LEACH算法中采用以下策略选择簇首［3］：

数据汇集点首先设定一个阈值T（n），此阈值决定哪个传感器节点成为簇首，并且，此阈值分配给每一个传感器节点，随着LEACH算法的运行，每个传感器节点的阈值也将随着改变。阈值T（n）表示如下：

其中，分子P表示在本轮中当选簇首在整个网络中所有节点的比例，r表示为当前进行的轮数，rmod（1／p）表示为本轮中被选为簇首的个数，G表示为本轮中没有被选择成为簇首的其它传感器节点的集合。当本轮建簇开始时，网络中所有的传感器节点均需要产生一个随机数M（〈0〈M〈1），M的意义可以表示如下：

在LEACH算法中，每一轮开始时都将进行簇首的选择。为了更好地延长网络的生存周期，在选择簇首时应该尽量选择剩余能量充足的传感器节点。但此算法还是有很多不足，所以提出新的算法是有必要的。

3 基于FCM的分簇多跳路由算法

传统的分簇协议在确定簇首后，依据传感器节点与簇首的距离进行分簇。本文提出的分簇路由协议首先确立簇群的方位，依据此方位信息确立簇首及候选族首，保证了整个网络中簇群的均勾分布。

文献［4］中提到，在实践运用中，为达到网络无缝覆盖率η，在监测区域A中随机选取的簇首数K应该为：

其中r为节点传输半径。

当节点由于能量消耗殆尽导致失效时，簇群的有效节点数目会慢慢降低。新的网络无缝覆盖率ηnew与有效节点数S的关系：

本文提出的分簇路由协议采用模糊C均值聚类（FCM）算法［5］实现无线传感器网络中簇的形成。首次完成分簇后，当其中某一个簇群中的所有簇首的能量降低至阈值时，才开始下一轮分簇。

数据汇聚点将WSN中N个传感器节点的坐标组成一个集合X｛Xj，j＝1，2……N｝，该集合中的N个样本对应于N个传感器节点。设Vi（i＝1，2……K）为每个聚类的中心，U（i，j）是第j个节点对第i个簇群的隶属度函数。J.C.Bezdek提出的模糊C均值聚类算法（FCM）是一种模糊目标函数法，其目标函数J（U，V）定义为：

其中，U＝［uik］（i＝1，2……C；k＝1，2……N）为隶属度矩阵，且满足下式：

其中m的最佳范围是［1.5，2.5］，dik是第k个样本到第i类的距离，定义为：

因此，可以采用新的目标函数使式（5）达到最小值的必要条件：

这里λj（j＝1，……，n）是式（5）的n个约束式的拉格朗日乘子。对上式所有的输入参数进行求导运算，使式（5）达到最小的必要条件为：

和

为了防止簇首节点能量消耗过快导致节点失效，设定当簇首能量降低至阈值β时，族首向队列中下一个节点发送信息，通知该节点成为簇首，此簇首则自动转换为普通节点。

在完成分簇后，采用簇首转发的原理。远距离的簇首并不直接同基站进行数据传送，而是选择同其最近的簇首进行传输，每一个簇首在接收到其它簇首传输到的数据后，进行相应的数据融合处理，然后转发下一个簇首，直至数据汇集点，此举极大的缩短了信息的传送距离，降低了簇首节点能量消耗。并且本策略中每一个簇群有多个节点轮流当选簇首，在仿真实验中也证实，此举保证了簇群稳定，在初次确立传输路线后，在很长周期内可以稳定数据传输路线。

本文提出的路由算法的流程图如图2所示。

3 仿真与分析

为了说明算法的效果，我们使用MATLAB对算法进行了仿真测试，选择的仿真场景参数如表1所示。

比较了最传统的LEACH算法和本文提出的新算法。图3为两种算法的生命周期比较，通过死亡节点数随时间的变化来判定生命周期的长短，从图中可以看出新的算法比LEACH算法的生命周期长。

表1 仿真场景参数

图2 算法流程图

图3 死亡节点与时间的关系

4 结论

对现有的LEACH路由算法进行研究时发现，当普通节点当选为簇头节点后，需要完成数据融合、与汇聚节点通信等任务，能量消耗较大。但是簇首数量不固定分簇不均匀，再者，对于反应式的无线传感器网络，由于簇首不周期性的发送监测数据，从而使得各节点能量消耗不均匀，LEACH决定节点的“角色”并没有考虑节点的剩余电池能量，存在着负载均衡策略不完备的缺点［7］。而本文提出的基于FCM的分簇多跳路由算法弥补了LEACH算法的不足，有效地延长了网络生存周期。

［1］宋文.无线传感器网络技术与应用［M］.北京：电子工业出版社，2006.

［2］马永波.无线传感器网络精确动态定位及其安全性问题研究［D］.吉林大学2010.

［3］Heinzelman W.B.，Chandrakasan A.P.，Balakrishnan H，An application－specific protocol architecture for wireless microsensor networks，（2009）IEEE Transactions on Mireless Communications，1（4），pp.660－670.

［4］Heinzelman，W.R.；Chandrakasan，A.；Balakrishnan，H."Energy－Efficient Communication Protocol for Wireless Microsensor Networks".In Proceedings of HICSS，00：the 33rd Hawaii International Conference on System Sciences，Wailea Maui，HI，USA，4－7January 2000；Volume 8.

［5］Manjeshwar，A.；Agrawal，D.P."A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks".In Proceedings of the 15th International Parallel and Distributed Processing Symposium IPDPS 2001，San Francisco，CA，USA，23－27April 2001.

［6］纪金水.基于Zigbee无线传感器网络技术的系统设计［J］.计算机工程与设计，2007.