基于K-M eans的WSN动态信任度双簇头选取算法

张 顶，张 琳

(南京邮电大学 计算机学院，江苏 南京 210023)

无线传感器网络是由大量的空间分布的微电子设备组成的网络系统。广泛运用于环境检测、数据采集等相关工作，各个节点能够感知环境，进行信息数据的处理，基于分簇协议，将数据发送到WSN内选取的簇头节点（CH），最终传输至称为基站（BS）的中心点［1］。

无线传感器网络中的数据传输、网络的生存时间一直是研究热点。许多无线传感器网络往往部署在恶劣，甚至敌对的环境中，如军事领域等不安全环境［2］，因此，研究可信数据的安全高效传输，较长的网络生存时间，稳定的拓扑结构是非常必要的。

而现有的WSN研究［3］，主要侧重于路由技术、节点能量、信任度等单一方面，会造成簇的偏斜分布，CH可能位于簇的边缘处。簇头节点的选取不当，会直接导致数据丢失。

针对以上问题，本文基于K-Means聚类算法［4-5］，先通过计算欧式距离进行分簇并选取初始簇头，接着设计了3种计算动态信任度的参数，分别是节点剩余能量、距离簇头的欧式距离、最大一跳邻居数，再提出DTK-Means算法，选取出双簇头。通过信任双簇头轮换机制，提高数据采集、传输的安全性，节省簇头频繁选取所需耗费的能量，提高网络的生存时长。

1 相关工作

目前对无线传感器网络的聚类机制与簇头选取研究是基于几大主流路由协议的。这些协议［6-17］从网络结构、节点能量、节点信任度等方面入手。

通过考虑网络结构［18］，将路由技术分为两类，分层路由技术与平面路由技术。分层路由技术的例子是HEED［19］，该协议使用时分多址（TDMA）。平面路由技术的例子是直接扩散和顺序分配路由，研究高效安全的多传输路径。在分层路由中，每个传感器节点被划入某一簇［20］，基于信任原则进行簇头的选取，每个节点的信任可以通过考虑传感器节点的恶意、邻居关系等不同参数来计算［21］，信任聚合过程需要簇头节点完成。

基于能量感知的经典算法是LEACH［22］，该算法最大限度地减少能量耗散，选择具有高能量的节点作为CH。但该算法可能导致节点的能量损失不均匀并形成盲点，进而影响网络的整体性能，针对LEACH的弊端提出了许多扩展，例如LEACH-C的组合度量聚类算法以提高能效［23］。该算法采用集中式聚类构造和分布式CH选择方法，但与节点能量关联度较高。

在节点信任度研究方面［24-25］，一种基于信任感知的机制TSSRM［24］，从节点行为维度与能量维度构建节点的直接信任度与间接信任度，并进行节点综合信任度计算，从而建立节点间安全传输路径。

2 DTK-M eans模型设计

2.1 节点分簇

综上所述，在讨论算法的细节之前，检查系统模型的假设至关重要。我们假设各节点都是同质的，并具有相同的初始能量值，所有节点是随机且均匀分布，分簇以及簇头选取后，所有节点和基站保持静止。每个节点可以感知自身位置，同时也知道其他节点和基站的位置。欧式距离可以确定所有距离。数据由普通节点传输至簇头，再经由簇头传输至基站。

本文分簇基于K-Means算法。该算法使用欧氏距离均值将数据集划分为k个簇，它遵循以下步骤：（1）初始时任意选择k个点（形心），k为分簇所需的数量。这k个点作为这k个簇Ci的形心CHi，i∈｛1，2，…，k｝；（2）分别计算其他节点Nj与k个CHi的欧式距离，j∈｛1，2，…，N｝。Nj与哪个CHi的欧式距离最小，则将Nj划入对应簇Ci中；（3）重新计算k个簇的形心，更新选出新的CHi；（4）用新的CHi，重复步骤（2）；如果数据点的聚类分配发生变化，则重复步骤（3）；（5）整个分簇稳定，并将最终选定的k个形心设置为CHori。

考虑处理计算得到的欧式距离数据，使用误差平方和（Sum of the Squared Error，SSE）作为聚类的目标函数，多次运行K-Means产生的不同的簇集，取SSE最小的数值

其中，k表示k个聚类中心，Ci表示第几个中心，dist表示的是欧式距离。

求第k个形心Ck，即对SSE求导，令导数等于0，并求解Ck；m代表第k个簇内的节点个数。公式如下

最后求得的最小化SSE的最佳形心值为簇中各点的均值，所得最佳形心设为CHori。分簇算法如算法1所示。

算法1 分簇过程

2.2 簇头节点的选择

簇头节点的选择在DTK-Means算法中尤为重要。因为其余非CH节点将数据传输至CH节点，CH节点对接收到的数据进行聚合、分析，并传输至基站（BS）。本文提出了一个改进的K-Means算法，在一个簇中有两个CH节点来管理该集群。而CH的选取原则基于动态信任度，如图1所示，从节点剩余能量、节点距CH的欧式距离和周期内最大一跳可达邻居数，这三大维度考量节点的动态信任度。

动态信任度计算公式如下

其中，X代表考虑的维度，X1，X2，X3分别代表三个信任维度节点剩余能量、节点距CH的欧式距离和周期内最大一跳可达邻居数。W代表最佳系数，即该影响因素对动态信任度的权重。动态信任度DT满足［0，1］，DT数值越高，表明节点可信度越高。

本文采用AHP的1～9标度法如表1所示，求解最佳系数数值。

表1 AHP的1～9标度法

求得W1=0.698 6，W2=0.237 0，W3=0.064 4。

定义1 节点的剩余能量，表示每个节点当前所具有的能量。

节点的剩余能量作为动态信任度的衡量维度之一。此处，我们采用如下的能量模型：节点传输数据时的单位比特能耗Eelec，节点的初始能量Eori，节点的剩余能量Elast，节点的消耗能量Ecost。传输1 bit数据所需的能量消耗由三部分组成：节点发送数据Etra消耗的能量，节点接收数据Erec和节点之间建立邻居时ACK分组交换Eack，此外还有能量阈值Etru与有效节点判别值Euse。

节点的消耗能量公式

Ecost（l，d）=Etra（l，d）+Erec（l，d）+Eack（6）其中，l表示数据长度，即比特位数，d表示两节点之间的欧式距离。

节点发送1 bit数据所消耗的能量如下

节点接收1 bit数据所消耗的能量如下

节点之间建立邻居时ACK分组交换Eack所消耗的能量如下其中表示ACK分组数据包的长度与数据包的长度之比。

最终节点的剩余能量计算公式

设置节点能量信任阈值Etru为总能量的50%，当高于此值，节点将有资格参与簇头节点的选取。因为簇头需要保证一定的能量储备，以供维持簇头节点的职责。

因此，节点是否可参与簇头节点选取的判别公式如下

定义2 节点距CH的欧式距离

表示簇内普通节点距CH的距离。距离度量最常用的就是闵可夫斯基距离（亦即p范数），即

当p=2的时候，闵可夫斯基距离即为欧氏距离（2范数），公式简化为

无线传感器往往布置在环境较为复杂的环境中，本文计算节点间的距离度量所采用的欧式距离，以三维空间为基准。最终距离计算公式如下

其中，x，y，z分别代表三维空间的三条坐标轴。

节点之间的距离度量，可有效地反映出节点之间的联系紧密性。首先在聚类后，原始簇头往往处于簇内的中心，此时根据动态信任度选取新的簇头节点，需要簇头节点也尽量处于整个簇的中心位置，可以极大降低其余节点传输数据所消耗的能量。

定义3 周期内最大一跳可达邻居数

表示在一个簇头选取周期内，节点的链路状态表中显示的最大一跳可达邻居节点数量。节点参数如图2所示。链路状态表是一个记录节点信息以及节点之间交互信息的数据表，存储了节点的ID、节点数据转发的出口、接口地址、COST值、邻居ID、节点自身动态信任度。每一个节点都有自己的ID，通过ID来标识每一个节点。COST值量化节点之间的跳数，节点i在将数据传输至CH过程中，每经过一个普通节点，COST值加1。节点在建立邻居时，将ACK报文与链路状态表广播给其他所有节点，最终计算出当前周期内，节点将数据传输至CH节点过程中所建立的一跳可达的邻居数量。

最终基于动态信任度的簇头选取算法如算法2所示。

算法2 簇头节点的选取

3 DTK-M eans机制

3.1 网络初始分簇阶段

该算法从无线传感器网络初始阶段开始，所有节点将其位置信息发送给BS（基站）。基站收集到所有节点的位置信息后，根据K-Means无监督聚类算法任意选取k个形心。节点之间相互通信，根据欧式距离加入距离最近的形心，形成k个簇，再求解簇内的平均值，以确定新的形心。经过几次迭代后，分簇稳定，最终选定的形心作为初始簇头节点CHori。每个节点的动态信任度初始化为0。

3.2 网络双簇头选取阶段

经过K-Means算法，所有节点划分成k个稳定簇，并选出初始簇头节点CHori后，进行双簇头节点CHfirst与CHsecond的选取。首先，每个节点建立两个预先定义的阈值。第一个是能量信任阈值，为总能量的50%，簇头节点需要有一定能量的储备，低于此阈值的节点无法参与簇头节点的选取。第二是动态信任度阈值，分为两个阈值，其一是针对双簇头节点的阈值，其二是针对整个簇内的节点。每个节点进行ACK报文与链路状态表的传输，先建立稳定的邻居状态，然后根据动态信任度计算公式计算出每个节点自身的动态信任度，并更新链路状态表中的数据信息，周期性地将新的链路状态表发送给其他节点。

根据动态信任度，选取出主簇头节点CHfirst与备份簇头节点CHsecond。选定双簇头节点后，CHfirst向所有传感器节点广播一个TDMA帧，节点在此帧的基础上与CH进行通信，并根据每个节点传输至簇头节点的COST值，建立负载均衡机制，从而消除数据冲突与多通道访问问题。CHfisrt节点将收到每个数据包转发给BS与CHsecond。CHsecond作为备份簇头节点，将接收到的数据保存，防止CHfirst节点遭受攻击，导致数据丢失。当CHfirst动态信任度低于CHsecond时，由CHsecond节点作为主簇头节点并承担相应职责。实现双簇头轮换，避免簇头节点的频繁选取而导致的能量耗散。

3.3 网络后运行阶段

随着无线传感器网络的运行，节点的能量不断耗散，动态信任度逐渐降低，逐步进入网络后运行阶段，此阶段需要考虑簇头节点的重新选取，以及动态信任度过低的节点，以及整个网络的可信度。

当CHfirst与CHsecond的动态信任度均低于预先设定的阈值时，网络中断操作，由当前的主簇头节点将数据发送至BS后，重新进行无线传感器网络的双簇头节点的选取。

当节点的动态信任度低于某一阈值时，节点能量过低，位置异常，邻居数波动，都可能导致动态信任度较低。将此节点置为不可信节点或死亡节点，可以实现对无线传感器网络的安全性保护，以及对该节点的隔离。

当超过70%的节点的动态信任度均低于某一阈值时，无线传感器网路进入最后运行阶段，此时大部分节点都为不可信节点或死亡节点。在此阶段，整个网络中剩余的可信节点将数据直接传送至BS，一直持续到90%的节点死亡。最终，整个网络变为不可信网络，需要对所有节点重新布置规划。

4 仿真结果与性能评估

4.1 实验仿真

本研究采用NS2仿真器分析DTK-Means的性能，并与同类型经典算法K-Means［4-5］，HEED［19］，LEACH-C［23］进行比较。

仿真的硬件环境为Intel（R）Core（TM）i7-6700HQ CPU2.50GHz。每个节点可以通过其邻居节点在网络中扩散消息，允许节点周期性地通过邻居节点以及中继节点的转发，发送的消息的TTL设置为5。仿真参数如表2所示。

表2 仿真参数设置

4.2 性能指标与分析

为了恰当地比较DTK-Means算法和其他同类算法的性能，采用计量学方法，从下文中三个方面进行评估。在实验前，设定模拟中的两个重要参数，一个是能量阈值，另一个是中断参数。能量阈值在每个节点定义。如果节点的能量低于阈值，则不再具备参选CH的资格。该参数固定为初始电池能量的50%。CHfirst节点动态信任度低于阈值，则不再具备担任主簇头节点的资格，该参数设定为0.6。当主、备份节点动态信任度均低于阈值时，则进行簇头的重新选取。中断参数定义为导致网络从网络初始分簇阶段到后运行阶段的死亡节点数。通过实证观察，该参数被定为70%的节点。

4.2.1 无线传感器网络生命周期

将网络运行时长作为评价无线传感器网络生命周期的指标。它的公认标准度量是检测活动节点的数量。此度量标准的一个重要参数是FND，它检测节点之间通信轮次过程中网络中第一个死亡的节点。如图3所示，第一个节点在DTK-Means中死亡的平均通信轮次数是1 010次。其他同类算法在较低轮次数时便产生第一死亡节点。LEACH-C，HEED在数据传输过程中，总是选择能量较少的节点，这会导致节点过早死亡。K-Means频繁选取簇头加速节点死亡。通过双簇头的选取，大大延长了DTK-Means中的FND标准，更凸显DTK-Means的稳定性。

4.2.2 数据包传输比率

PDR，数据包传输数量也是衡量算法性能的重要指标之一。数据包分组传送比率被定义为在特定时间段内无误地传送到目的地的数据包数量。DTK-Means算法引入了COST值实现了负载均衡机制，减少了路径冲突，同时由备份簇头节点CHsecond备份数据，极大提升了数据的接收性与稳定性，即使在节点数目越来越多的情况下，也能保证一个较高的数据包传递率。图4显示DTK-Means算法的PDR指数较高。

4.2.3 节点能量耗散

通过双簇头节点轮换机制，大大降低了簇头的选取次数，节省了因为簇头选取所需耗费的能量，使得网络中能量耗散最小化。网络的剩余能量以及能耗如图5所示。从仿真结果可以看出，DTK-Means在节能方面比LEACH-C与K-Means更有效，且能量耗散速度平稳。K-Means和LEACH-C增加了10%到30%的能耗。DTK-Means算法具备更高的节能性。

5 结束语

无线传感器网络的聚类机制与簇头选取十分重要。簇头节点的适当选取可极大提升无线传感器网络的性能，本文提出了一种基于K-Means的改进优化算法DTK-Means，侧重于簇头节点的选取阶段。引入三个维度计算出每个节点的动态信任度，选取从出主备份双簇头节点，极大地提升了网络生命周期与数据包传输成功率，提高了整个网络拓扑的安全性。

本文仍然存在不足。在处理动态信任度较低的节点时，没有考虑是否为恶意节点、异常节点等多种因素，处理方式较为单一。以及在网络运行一段时间后进行簇头的重新选取，可能会出现局部间动态信任度梯度差较大。在未来的研究工作中，可以考虑对动态信任度异常节点的处理机制，检测恶意节点并实施多种预防攻击机制，以及二次选取簇头时的局部优化机制，为后续研究无线传感器网络的安全性提供新的思路。