摘 要： 在LEACH协议的基础上提出了一种LEACH_P算法，该算法使用基于划分的聚类算法PAM对初始拓扑进行分簇。首轮选择距离簇质心最近的节点作为簇头，后面各轮选择簇头邻域内剩余能量最大的节点作为簇头。每当死亡节点增量达到节点总数的5%时，重新进行分簇，同时簇头领域半径增大25%后再进行簇头选择。仿真结果表明，LEACH_P算法分簇更加合理，节点能耗更加均衡，整个网络生存周期（第一个节点死亡时间）延长了30%左右，有效地提升了网络性能。
关键词： WSN路由协议；LEACH；PAM算法；MATLAB仿真
传感器技术、微机电系统、现代网络和无线通信等技术的进步，推动了具有现代意义的无线传感器网络的产生和发展[1]。现在无线传感器网络已经非常广泛，军事、环境监测和预报、健康护理、建筑物状态控制等领域都可以看到无线传感器网络的影子。无线传感器网络的自身特点决定了其特殊性，由于能量无法得到补充，能量有限，因此必须尽可能地节约能耗以延长节点的存活时间，节能降耗便成为了无线传感器网络研究中一个热点。本文在经典的LEACH协议的基础上提出了LEACH_P(LEACH based on PAM)协议，通过MATLAB仿真验证了其在均衡节点能耗上的有效性。
1 LEACH协议
LEACH[2]是最早提出的基于分簇的层次路由协议。普通节点的数据经由各自簇头节点传给sink节点，有效减少了整个网络的能量消耗。同时，簇头的选举使得各个节点都能在数轮之中当选一次簇头，均衡了簇头的能量损耗，有效地提高了网络性能。据计算，相比于一般的平面路由协议，LEACH可以延长网络周期约15%[3]。
尽管如此，LEACH协议仍然有以下不足：
(1)簇的形成为先选举簇头再形成簇，簇头的选举具有很大的随机性，仅仅依靠生成的随机数来决定是否成为簇头。
(2)簇头的选举具有很大的随机性，任何节点只要其生成的随机数小于阈值T(n)即可当选为簇头，未考虑到节点的剩余能量。
(3)簇的形成过程实质是先选出簇头再根据簇头形成簇，由于之前的簇头选举没有考虑到节点的物理位置，使得可能出现各个簇内成员节点数目差距很大。成员节点较多的簇内簇头能耗会非常大，显然不利于延长网络的生存时间。
2 PAM算法
PAM算法是由KAUFMAN L和ROUSSENUW P J等人提出的一种中心点划分聚类算法[4]。算法策略如下。
在数据集中随机选择k个对象作为中心点，其余节点皆为非中心点。算法反复使用非中心点来试图替换中心点，基于各种可能的组合，估算聚类结果的质量。一个中心点Oi如果可以被一个非中心点对象Oh所代替，那么这次迭代过程中的Oh将被作为新的中心点出现在下一轮迭代中，算法运算直至最终收敛。
非中心节点Oh试图替换中心节点Oi时， PAM算法为每一个非中心点Oj计算代价Cjih，Cjih的值存在以下4种情况，如图1所示。
(1)Oj属于中心点Oi。如果Oi被Oh替换后，Oj离另外一个中心点Om更近，那么Oj加入Om，此时，Cjih=Distance（j，m）-Distance（j，i）。
(2)Oj属于中心点Oi。如果Oi被Oh替换后，Oj离Oh更近，那么Oj加入Oh。此时，Cjih=Distance（j，h）-Distance（j，i）。
(3)Oj属于中心点Om。如果Oi被Oh替换后，Oj还是离Om更近，那么对象的隶属关系保持不变。此时，Cjih=0。
(4)Oj属于中心点Om。如果Oi被Oh替换后，Oj还是离Oh更近，那么Oj加入Oh的簇。此时，Cjih=Distance(j，h)-Distance(j，m)。
其中，Distance（i，j）表示点i到点j的距离，此处使用欧几里得距离。
计算替换产生的总代价函数TC=Cjih，其中j为除节点h和i之外的其余所有节点。如果TC<0，说明替换后的中心点更接近簇的中心，分簇更加合理，执行中心节点的替换过程；否则，不进行中心节点的替换。
LEACH_P协议是基于LEACH进行的改进，所以协议运行流程大致相同，同样是以轮（round）为单位。不同于LEACH协议的是，LEACH_P改变了原来LEACH协议的先选举簇头再形成簇的构造顺序，改为先使用PAM算法对初始簇进行均匀分簇，而后再进行簇头的选举。之后分簇的结果将在一段较长的时间内保持不变，直到死亡节点的增加数目达到一定量再重新进行分簇。簇头的选举在每一轮结束后都会进行。在每一轮的簇头选举过后，接着进行数据传输，数据传输阶段与LEACH协议完全一样，这里不再赘述。总的来说，LEACH_P协议包含簇的形成、簇头选举和数据传输三个部分。下面着重介绍簇的形成和簇头选举两个部分。
2.1 簇的形成
簇的形成即对拓扑中的节点进行分簇，分簇后使得各个簇内的节点分布更加紧凑，有利于缩短数据传输距离，节省数据传输时消耗的能量。分簇并不是每一轮都进行，在协议运行开始时进行初始分簇，之后只有当死亡节点数的增量达到一定量时，才会在下一轮开始时先重新分簇，以此规避由于节点死亡带来的簇头节点负载不均衡。使用PAM算法对原始拓扑进行分簇时，需要确定分簇的数目k。k的值不能过大，否则就不能最大化分簇路由带来的能量节省。k的值也不能过小，这样会使单个簇头需要负担的簇内节点过多，簇头节点能量消耗过快，也不利于整个网络性能的提升。根据参考文献[5]，假设传感器节点均为相似二维空间λ泊松分布，则可以得到最优的簇头节点百分比为：
其中，c为区域边长的一半，由节点总数即可求得分簇的数目。
分簇算法包括以下几个步骤：
(1)从初始数据集中随机选择k=p×N（节点总数）个节点作为临时中心点Oi。
(2)将剩余节点依照距离最短原则选择距离最近的临时中心点加入其簇。
(3)选择一个异于中心点Oi的非中心点Oh，试图用Oh替换Oi作为新的中心点。
(4)计算替换产生的总代价TC，如果TC<0，则进行替换操作，此后Oh作为新的中心点存在。
(5)跳到步骤(3)，直达所有可能的“替换对”都进行替换试探完毕后停止，最终形成新的k个临时中心点Oi，一轮迭代过程完成。
(6)跳转到步骤(2)，进行下一轮的迭代，直到达到迭代次数，跳转到步骤(7)。
(7)迭代过程完成，中心点Oi选择完毕。
(8)其余非中心点Oj根据到各个中心点Oi的距离选择距离最近的中心点加入其簇。
(9)分簇完毕，形成k个簇。
2.2 簇头选举
经过分簇后，分出的各个簇节点数较为平均，各个簇内节点间间距较小。簇头选择应该兼顾簇头节点的剩余能量和簇头节点的位置。
2.2.1 首轮簇头选举
首轮由于所有节点的剩余能量大体相同，簇头的选择基于节点剩余能量的考虑可以忽略，主要从节点的位置考虑选举簇头。根据参考文献[6]，当第i个簇内的非簇头节点向j传输数据时，系统消耗的总能量取决于?撞dij2（簇内距离较近，使用多路径衰减模型），尽量减小撞dij2即可实现节省能耗。令第j个簇的簇头节点的坐标为（Xj，Yj），簇内的非簇头节点坐标为（Xn，Yn），节点总数为M，所以分簇数的个数为M×p；簇j内节点数目为Nj（包括簇头）。计算得到第j个簇内非簇头节点到簇头节点之间距离平方的数学期望：
2.2.2 首轮之后轮次的簇头选举
首轮之后轮次的簇头选举应该综合考虑到节点的剩余能量和节点的物理位置。首轮之后的簇头选择策略是：以簇的中心（几何中心）为中心点，以半径r作圆。在此圆中，选择剩余能量最多的节点作为簇头。首轮中，簇头节点位置较为居中，簇内其余非簇头节点到簇头节点的距离不同，而非簇头节点的发送数据能耗与传输距离有直接关系。一轮过后，靠近簇边缘的节点剩余能量相对较小，所以应该选择离簇头近的节点作为簇头。数轮过后，离簇头较近的节点可能都已经当选过簇头，由于作为簇头的能量耗损较大，此时整个簇头的剩余能量区域分布情况是簇边缘的节点剩余能量多，簇中间的节点剩余能量较小。此后应该尽量选择这些边缘节点作为簇头。LEACH_P协议的策略是每隔数轮N将半径r增大20%，每次增大的半径幅度都为0.2r，当半径增大到2.5r后，再过一段时间，半径重新调整到r，之后重复前面的步骤继续进行。总之，首轮之后的簇头选择是：在以各个簇中心为原点，以r为半径的圆内选择剩余能量最大的节点作为簇头，间隔N轮后，r增大20%，当半径增大到2.5r后，半径重新回归到r，从头再进行递增。
3 仿真分析
本文使用MATLAB作为实验工具进行仿真。实验中，100个节点随机分布在100×100的区域内，节点总数为100个。汇聚节点sink位于拓扑的中心位置，坐标为(50，50)。节点当选为簇头的概率p取0.05。实验中用到的其他主要参数如表1所示，所采用的拓扑图如图2所示。
图2是使用LEACH_P协议进行首轮分簇的结果。可以看出，使用PAM算法对初始拓扑图进行聚类能够取得比较好的聚类结果。各个聚簇内的节点数目比较平均，簇的大小相似，这样有利于簇头节点均衡能耗，各个簇头的轮平均能耗更为接近。
本实验主要从节点能量总耗费和死亡节点数对实验进行分析。各轮总能量消耗图如图3所示。LEACH_P协议和LEACH协议在各轮中的总能量耗损非常接近，并且会在很长的一段时间内保持这种趋势。其中的原因是：使用PAM算法能够带来比较好的分簇结果。但是，即便如此，各轮中总的数据传输距离（包括簇内节点到簇头节点的距离和簇头节点到簇内节点的距离）大体相同，所以总的能量耗损曲线基本上重合在一起。在之后的340轮左右，LEACH_P(NEW)协议的曲线开始凸显出来，同时在之后的50轮中，LEACH_P协议的总能耗会与LEACH协议的能耗进一步拉大，这是由于LEACH协议中各节点的剩余能量分布不均匀造成的。LEACH分簇没有考虑到节点的剩余能量和节点的地理位置，进行分簇的结果又不尽理想，使得最终节点间的剩余能量差距较大。仿真结束后，会余下一些不能再次成簇的节点。下面通过分析剩余节点图来补充说明图3中最后50轮曲线变化的原因。
剩余节点对比图如图4所示。LEACH协议第一个节点死亡的时间是在245轮左右，而LEACH_P协议则是在350轮左右。LEACH_P协议使得整个网络的生命周期延长了30%左右。LEACH协议中节点死亡20%是在330轮左右，而LEACH_P协议则是在350轮；LEACH协议中节点死亡率为80%经历的轮数为145轮，而LEACH_P协议只有用30轮。LEACH_P协议在如此短的时间内节点大量死亡，是因为整个网络的能量均衡效果比较好，节点的剩余能量值接近，单一节点的死亡预示其他节点的能量也快耗尽。网络生命周期的延长原因也正是如此，能量消耗能够分担到每个节点，同时分担的份额也较为平均。而在LEACH中，非均衡的能量损耗使得节点的剩余能量差异较大。均衡整个网络的能量损耗到各个节点，使得整个网络的性能大幅提高。图4中，仿真结束后，LEACH协议中剩余存活的节点达到13个，LEACH_P中为5个，这也正是图3中仿真结束后LEACH比LEACH_P协议剩余的能量多的原因。
本文在LEACH协议基础上提出了LEACH_P算法，通过PAM算法对拓扑进行分簇，之后再选举簇头。仿真实验证明了其在均衡节点能耗上取得了比较好的结果，LEACH_P协议能够利用整个网络中的节点来均衡网络能量损耗，使得整个网络的生存周期提高了30%，增强了网络性能。接下来的研究方向是如何在均衡能耗的前提下减少单轮网络总能耗。
参考文献
[1] 孙利民.无线传感器网络[M].北京：清华大学出版社，2005.
[2] HEINZELMAN W，CHANDRAKASAN A，BALAKBISHNAN H.Energy efficient communication protocol for wireless micro-sensor network[C].Proceedings Of The 33rd Hawaii Interna-tional Conference on System Sciences，Washington，DC，IEEE Transactions on Computer Society，2000：3005-3014.
[3] HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNANH.Energy-efficient communication protocol for wireless micro-sensor networks[C].Proceedings of HICSS’00，Los Alamitos，CA，USA，IEEE Press，2000.
[4] KAUFMAN L，ROUSSEEUW P J.Finding grouping in data：an introduction to cluster analysis[M].New York：John Wiley & Sons，1990.
[5] BANDYOPADHYAY S，COYLE E J.An energy efficient hi-erarchical clustering algorithm for wireless sensor networks[C].IEEE INFOCOM 2003，Twenty-Second Annual Joint Conference of the IEEE Computer and Communications，IEEE Societies，2003，3：1713-1723.
[6] 胡兴华，骆坚，谭珊珊，等.固定簇的LEACH半径自适应簇头改进算法[J].传感技术学报，2011，24（1）：79-82.