基于K-means++的无线传感网能量高效分簇协议

余 扬，李艳彩，陈君华

(云南民族大学 云南省高校物联网应用技术重点实验室，云南 昆明 650500)

无线传感网络[1]是由随机部署在监测区域的大量廉价低功耗微型传感器节点以无线通信方式形成一个多跳自组织网络，其用来感知、采集、传输和处理网络所覆盖区域中对象的相关信息.由于节点所携带电池的能量十分有限，因此如何降低能耗最大化传感网络生命周期是目前国内外众多学者研究的热点问题之一[2-3].文献[4]提出了LEACH层次路由自适应分簇算法，节点周期性轮流担任簇首，该算法缺点是随机选择簇首，导致簇首分布不均且数量不固定，导致部分节点能量消耗过快，进而影响网络生命周期.文献[5]的Improved-LEACH协议虽然对簇首选择过程进行了优化，但是只适合处理规模较小的无线传感网，文献[6]的LEACH-C算法根据节点全局位置和剩余能量用模拟退火算法集中选择簇首.随着节点数量增加，计算量较大，不适合大规模无线传感器网络.文献[7]的 HEED算法基于节点的能量及节点到簇首间距离采用分布式方式选择簇首，但是在选择簇首时，需要不断竞争迭代，同时与邻居节点进行信息交互，增加通信的能耗.文献[8]的PEGASI算法通过贪心算法将网络中节点串成基于地理位置的一条链，在链状结构上进行数据融合和传输到达汇聚节点(Sink)，该算法缺点是传输延迟较大，也没有考虑到簇首与Sink的距离，以及节点剩余能量，导致靠近Sink的分簇节点能量消耗较快，使得网络负载不均衡[9].

常见无线传感网络的聚类算法有K-means[10]，该算法能够高效处理大型数据集，时间复杂度接近于线性，但是聚类结果受初始节点的选取影响较大，对于偏离较大的数据很敏感.K-mediods算法[11]是对K-means的一种改进，相对于噪声不敏感，个别数据不会对总体划分造成太大影响，其方法是根据样本与簇心节点距离分配给最近一个簇，然后反复利用非簇心节点来代替簇心节点，该算法优点对于较小的数据集有效，但不能扩展到大型的数据集，聚类结果仍然受初始节点的选取影响较大.K-means++算法[12]的基本思想对初始节点中距离中心越远的点会有更高的概率被选为聚类中心，克服了起始种子节点带来的聚类偏差，因此簇首与簇首分布相对更加均匀，同时簇首的数量也是确定的，可以较好的扩展到大规模无线传感网络中.

考虑上述算法的不足，结合层次路由和K-means++算法的基本思想、从簇的形成、簇首的选择、簇间通信3个关键因素考量对传统路由协议进行改进，提出了基于K-means++无线传感网能量高效分簇协议.

1 无线传感网络能耗模型

1.1 网络模型

假定无线传感网络中的传感器节点在监测区域内随机部署，具有以下特点：

1) 传感器节点可以感知自己的地理位置.

2) 传感网中所有节点都是同构的，即有相同的接收、发送和数据处理能力，每个节点具有唯一的ID.

3) 传感网节点部署后位置固定，初始能量相同而且能量有限.

4) 传感器能根据接受者距离远近，自适应调整其发射功率以节省能量.

5) 汇聚节点在远离传感器节点且位置固定，能量充足可以保证正常的能量消耗.

6) 所有节点都能够和汇聚节点直接通信.

1.2 能耗模型

无线传感器的能耗主要集中在无线网络数据传输上，能量模型采用一阶无线电模型[10]，该模型的结构如图1所示.

ETx(l,d)=l·Eelec+l·ε·dr

.

(1)

ERx(l)=l·Eelec

.

(2)

2 簇首数量的确定和簇的划分

传感网的节点在目标监测区域进行部署通常是随机的，往往很难达到理想的均匀分布.某些节点所在区域可能过于集中，也可能过于分散，从整体分布上看可能是矩形也可能形成其他各种形状，以往设想为所有节点都理想分布的情况下，难以符合实际最佳簇首数量的选取，只有对传感器节点进行更好的分簇，才能更好的均衡网络负载，延长网络生命周期.

分簇设计时需综合考虑网络的分布大小、节点分布密度、网络能耗以及运行过程的可靠性，才能增强网络运行的稳定性.

2.1 传统簇首数量的确定方法

传统最佳簇首数量的确定根据文献[4]，首先假定有N个节点均匀分布在M×M的区域，将其分为k个簇，那么每个簇中有N/k个节点，其中包含一个簇首和N/k-1个非簇首节点，簇首完成数据的接收、融合，然后直接转发至汇聚节点.假定汇聚节点距离监测区域位置较远，所有簇首到汇聚节点的平均距离dtoBS来近似为每个簇首到汇聚节点距离，节点通信方式可采用多径衰减模型，簇首能耗近似表示为式(3)，其中EDA为融合1 bit数据的能耗.

(3)

簇内普通节点的能耗为式(4)：

(4)

每个簇的全部能量消耗可以表示为式(5)：

Ecluster=ECH+EnonCH

.

(5)

整个无线传感网总的能耗表示为式(6)：

Etotal=k·Ecluster

.

(6)

(7)

上式(7)确定的簇首数量kopt适合作为一个理想条件下的参考值，但实际使用时需要根据所有节点分布情况和汇聚节点位置对kopt进行优化，本文中采用聚类评估指标S_Dbw优化簇首数量.

2.2 K-means++分簇算法设计

在簇的建立初期，汇聚节点对成簇进行集中计算处理，若指定p个簇首，目标监测区域随之被划分为p个簇，初始节点的选择以(7)式中的kopt为参考数量，算法具体步骤为：

Step 1 随机选择一个传感器节点作为第一个聚类中心c1=(x1,y1)，计算每个节点与当前最近聚类中心的欧氏距离D(x)，x∈X，x表示一个传感器节点，X表示所有传感器节点构成的样本集合.

Step 3 重复2过程直到选择最后一个聚类中心cp=(xp,yp)，于是形成p个聚类中心.

Step 4 对每个节点x，分别计算它到p个聚类中心的距离，并将其划分到距离最小的聚类中心所对应的簇中.

Step 6 执行步骤4，直到簇内的质心位置不再发生变化为止.

2.3 引入聚类评估指标S_Dbw确定簇首数量

K-means++算法需要人为给定簇的总数量c，考虑到实际节点部署的监测区域分布位置多变的情况.为了确定最优簇首数量，使用文献[13]中S_Dbw算法作为聚类评估指标，因其不需要引入外部数据，同时对噪声、密度、单调性、组和偏态分布这5个方面评价具有非常好的可靠性[14].当S_Dbw评估指标取得最小值时，其所对应簇的数量c可以保证所有簇的结构相对平衡，分布更加均匀，同时簇中成员密度和簇与簇的分离度更加合理，有效的避免了簇首过于分散或者过于集中.

聚类评价S_Dbw的计算公式如下：

S_Dbw(c)=Scat(c)+Dens_bw(c)

.

(8)

无线传感网由N个节点构成区域S，对其整体划分成c个小区域，每个小区域代表一个簇，所有簇的中心点集合表示为D={vi|i=1,…,c}，簇内的密度评价为式(9)：

(9)

式(9)中表示第i个簇ci的中心点，vj表示第j个簇cj的中心点，uij表示vi和vj的中点.簇间的分离度评价为式(10)：

(10)

式(10)中σ(vi)表示簇ci中的所有节点到其中心点的方差，σ(S)表示整个区域S中N个传感器节点到其中心点的方差.

2.4 簇首选择

网络中簇首的选择需要充分考虑节点能量，能量较高的节点更容易成为簇首.若将整个无线传感网划分成c个区域之后，簇首的数量也随之固定，簇首选取仅在每一个簇中分别进行，可有效避免传统随机选取方式下中簇首数量变化太大，簇首之间距离过远或者过近，造成能量负载不均衡，节点能量过早耗尽的情况.簇首选取完毕之后，汇聚节点以广播形式向全网广播消息，每个普通节点加入距离自己最近的簇首，簇内的簇首选举方式如式(11)所示

(11)

式(11)中，CHi表示第i簇内的簇首，Eresidual为节点当前的剩余能量，Einit为节点的初始能量，Tmin是最小的阈值，避免剩余能量过低的节点仍能被选为簇首.

2.5 簇间通信

当簇首与汇聚节点距离较远时，适合采用多跳接力通信，原因是直接与汇聚节点通信能量消耗过大.为寻找每个簇首到汇聚节点(Sink)的最优多跳路径，可采用改进的Dijkstra算法.

为了满足簇首之间的能量消耗更加平衡，文中综合考虑簇首间的距离和下一跳簇首的能耗，首先定义簇与簇及簇与汇聚节点间的通信代价为:

(12)

min(Sink,v)=minCi(v)

.

(13)

无线传感网中簇间通信主要实现步骤如下：

(14)

再计算min{D(v)}，找到其对应的D(vj)的值，也就获得了其中最小值点对应的簇首节点ID.

Step 3 当i=k-1时，意味所有节点都访问过，结束此步骤.否则，用新的节点替换旧的节点作为新的中间节点，令i=i+1,并回到步骤2中.

表1 仿真参数

Step 4 最优路径生成完毕之后，Sink节点携带各簇首节点的ID及其双亲节点的编号以广播消息的形式发送，簇首在稳定阶段将把数据沿着指定的双亲节点向汇聚节点的方向传输，那么处于根节点的簇首，其双亲节点就是Sink节点，按照以上的方法，簇首与簇首及汇聚节点之间生成一颗以汇聚点为根的树形结构，则每个簇首节点到汇聚节点通信代价都是最优路径.

3 仿真分析

3.1 仿真环境及参数设置

实验使用Matlab 2014b对无线传感网网络进行仿真，网络中有200个无线节点，随机部署在200×200 m2的区域，汇聚节点位于(100,275)，参数如表1所示.

基于K-means++算法(KEECS)对区域内所有节点进行聚类，聚类完成之后使用S_Dbw指标进行评估，S_Dbw的值越小对应成簇的质量就越高，每次改变簇的数量k，实验中簇的数量k和S_Dbw的对应关系如图 2所示.

从图2中可以看出，随着成簇数量的增加，聚类评价指标值将获得最小值.当成簇数量k=10，聚类评价指标值取得最小值，即无线传感网获得最佳的成簇数量.此时，无线传感网总共被划分成10个簇，如图 3表示，其中，实心点代表每个簇的质心位置.

3.2 LEACH，LEACH-C与KEECS分簇比较

依据表1的参数，分别对LEACH、LEACH-C与KEECS的算法进行仿真，LEACH，LEACH-C的簇首概率为0.05[15]，得到的的实验结果分别如图4、图5、图6所示.

图4、图5表明LEACH协议由于簇首选举函数随机性的特点，导致成簇的数量和位置有很大的不确定性，某些位置过于分散或者过于集中，同时通信方式都采用单跳的形式传输，比较单一.而图6中可以看出通过优化KEECS算法聚类得到的簇，簇与汇聚节点之间可以进行多跳方式进行通信，与LEACH的2种协议所形成簇对比，在地理位置上和簇内节点数量上，K-means++算法整体分布更加均匀，可有效平衡网络负载和降低簇首能量消耗.

3.3 网络生存时间对比

如图7所示，传感节点初始200个，随着轮数的增加，部分传感器节点能量耗尽，存活节点总数量越来越少.

从图7中可以看出KEECS协议在第1 406轮时第1个节点死亡，第1 903轮时最后1个节点能量耗尽，LEACH协议中第170轮时第1个节点死亡，在第1 527轮时最后1个节点的能量耗尽，LEACH-C协议在191轮时第1个节点能量耗尽，在第1 661轮时最后1个节点能量耗尽.因此改进后的协议的生命周期比传统的LEACH和LEACH-C协议都要长，且第1个节点的死亡时间比传统的LEACH算法大幅增加，最后1个节点的死亡时间提升了25%，因此本算法可以有效的延长了网络的生存时间.从图7中还可以发现第1个节点能量耗尽轮数和最后1个节点能量耗尽的时间隔时间很短，说明第1次出现节点能量耗尽之后，其他节点在短时间之内也迅速死亡，于是可以保证监测区域较长时间的完整覆盖，网络结构更加稳定，避免部分区域因为节点过早死亡而影响获取监测区域完整的信息.

3.4 网络消耗能量对比

节点总的剩余能量是衡量整体网络能量利用效率的一个重要标准，相同的运行轮数下，剩余的能量越多，则每一轮节点消耗的能量就越少.图8表示网络的总能量随着运行轮数变化的曲线图，全网共200个节点，初始总能量都是100J，随着运行的轮数增加时，网络的总能量逐渐减少.

当能量减少到0J时，KEECS算法运行的轮数最多，这是由于KEECS算法在数据传输过程中簇首的合理分布，并采用了数据融合和基于Dijkstra多跳通信的方式，此方法可以保证每个簇首到Sink节点的通信代价是最优的.

3.5 汇聚节点接收数据包的数量对比

如图9所示，对LEACH、LEACH-C与KEECS的算法进行仿真，分别得到汇聚节点接受的数据包数量和运行轮数之间的关系.

采用模拟退火算法的LEACH-C向Sink节点发送数据包的传输量最大，传统的LEACH算法次之，KEECS算法的Sink节点收到的数据包数量最少，说明整个数据传输过程能够很好的减少了节点与Sink节点的数据传输量，合理的减轻了网络的负载[16]，从而有效的节省了传感网中节点的能量，延长了网络的生存周期.

4 结语

对于传统的无线传感网中分簇路由协议在簇的形成、簇首选取、数据传输这些方面的不足，通过结合K-means++算法进行改进，使其计算速度快，适合处理大规模数据.分簇阶段，引入S_Dbw聚类评价指标来确定最佳簇首数量，能够较好的适应各种方式部署的无线传感器节点，传感器节点的部署也不必局限于特定规则的形状，在簇首的选举过程中不仅考虑簇首的地理位置，也综合考虑了节点的剩余能量.在节点向汇聚节点传输数据的过程中，采用多跳通信的方式进行传输，有效节省了通信资源的消耗.通过仿真对比发现：新的算法延长了网络节点的生存时间，也减少了网络节点的能量消耗，利于整个网络负载的均衡，非常有利于获取监测区域的完整信息.