无线传感网中兼顾多因素的簇头选择算法

张冬旭，秦 智

(成都信息工程学院信息安全工程学院，四川成都610225)

0 引言

近年来，无线传感网络(Wireless Sensor Network，WSN)技术广泛应用于军事、环境观测及预报、医疗护理、智能家居、建筑状态检测等多个物联网领域[1]。WSN是一种由众多的低功耗、低成本的传感器节点组成的大规模动态性自组织网络，这些传感器节点体积微小且分布广泛，同时也存在着一些限制如电源能力有限、计算和存储能力有限和通信能力有限等。传感器节点的部署环境复杂，加上这些限制就导致它容易受到攻击，存在众多的安全隐患。因此，需要有效的措施来提高无线传感网络的安全性。

网络的拓扑控制具有重要的意义，基于簇结构的拓扑控制有利于分布式算法的应用，分簇结构中选举出簇头节点来担任数据融合的任务，减少了数据通信量。已经有多种算法提出，LEACH算法[2]是一种自适应分簇拓扑算法，以循环的方式选择簇头节点，使各节点都可以等概率地担任簇头节点，保证网络能量相对均衡[3];PEGASIS 算法[4]是在 LEACH 算法基础上的一种改进算法，网络中所有节点成一个簇，节点只与它最近的节点通信，从而减少能量损耗，延长网络生命周期[5];GAF算法[1]则是定期地选举出一个簇头节点，只有簇头节点保持活动，其他进入休眠状态以节省能量。以上这些算法都是基于能量因素提出的算法，同时目前大多的簇头选择算法都主要考虑能量损耗问题，而很少考虑到其他因素。文献[6]提出一种WSN中兼顾安全和剩余能量的簇头选择方法，该算法有了很大改进，综合考虑到节点信任和剩余能量因素，但是没有考虑到通信、数据等因素。在此基础上对此算法进行改进，综合考虑节点信任度、通信、能量以及数据因素，提出一种兼顾多因素的簇头选择算法，使之更全面更适应无线传感网。

1 相关算法及研究

1.1 LEACH算法

LEACH(Low Energy Adaptive Clustering Hierarchy)协议的簇头选择算法是分布式的，是一种自适应的分簇拓扑算法，周期性地执行该过程，并且没有节点可以对簇头的选择进行决定或者协调，每个节点独立自主运行簇头选举算法并决定是否成为簇头。每轮选举可以分为建立簇阶段和数据传输阶段[7]。在每一轮簇头选举成功后，簇头向周围的节点公布消息，其他节点开始加入簇，然后开始进入稳定数据传输阶段[8]。簇头收到各节点的数据后进行数据融合，并且与汇聚节点通信，簇头节点会消耗能量很大，因此隔一段时间就要进行新一轮的簇头选举来保持网络能量的均衡[9]。

簇头选举时，每个节点都会生成一个在区间[0，1]内的随机数，设定一个阀值T(n)，如果该随机数小于T(n)，就发布自己是簇头的公告。

其中，p为簇头节点在所有节点中所占的百分比，r为当前簇头选举的轮次，G为一个节点集合，其中包含所有在最近的1/p次簇头选举中都未曾当选为簇头的节点。

LEACH协议中簇头节点的算法可以在一定程度上平衡网络的负载，从而延长网络寿命。同时簇头在处理数据时使用数据融合及压缩的技术，大大减少数据传输量。但是LEACH算法仍然存在一些不足，每个节点都等概率的成为簇头节点，没有考虑到节点的剩余能量。若剩余能量不足的节点成为簇头，则其能量会很快耗尽。因为选择的随机性，容易出现簇与簇之间簇头数目分布不均匀，该选举方法无论从数量还是分布位置上都不够稳定。

1.2 簇头选择考虑因素

簇头节点对于分簇拓扑结构网络来说相当重要，负责调节簇内节点的工作，数据的融合及转发、与汇聚节点通信等工作，能量消耗较大，因此簇头的选择也要考虑多方面的因素才能保证整个无线传感网络的正常运行。簇头选举需要考虑以下几个因素。

1.2.1 节点信任度

无线传感器节点由于体积、内存、计算能力较小、通信范围有限，无法建立整个无线传感网的全局信任模型，一般只与其邻居节点交互，只需对其邻居节点信任度进行评估，建立局部信任[10]。节点信任值又分为两部分:一部分是直接信任值，即源节点根据自身与目标节点[11]直接交互的经验计算所得的信任值;另外一部分是间接信任值，即源节点通过推荐节点对目标节点的监控得到的间接信任值。某一节点的信任值需要将其所有邻居节点对它的信任值综合起来得到。信任关系如图1所示，节点i和j为邻居节点，节点j与p、q、m、n都互为邻居节点。

图1 直接信任与间接信任

1.2.2 通信因素

无线传感网中，恶意节点极有可能会丢弃或者篡改接收到的数据包，对网络安全及能量的正常使用造成威胁。而自私节点只在有自身需求时才加入网络以节省自身能量，平时不理会网络路由的需要，导致网络能量消耗量不均衡，从而影响网络寿命[12]。根据历史通信的失败与成功，可以来预测未来通信的成败，观察节点间的通信行为可以为恶意节点和自私节点的判断提供重要参考依据。

1.2.3 能量因素

传感器节点的能量很有限，而能量又决定了整个无线传感器网络的生命周期，因此能量的高效利用是簇头选择的一项重要因素。传感器节点需要进行数据的接收、传输和转发，若能量不足甚至耗尽，将会给网络正常运行带来重大影响。

为使数据传输过程中整个网络能量均衡消耗，无线传感网通常会采用能量多路径路由机制，这样就可以延长网络的生存周期。在多径传播方式中能量的消耗与节点之间的距离成指数关系，并且发送与接收数据时消耗能量的计算方法也不同[13]。

发送数据时能量消耗Ec为

其中，发送的数据大小为l，d为两节点之间的距离，Eelec为发射电路的单位能耗，εamp和famp为发射放大器的单位能耗。为距离阀值，当发送数据的距离小于该阀值时，发射放大器的消耗能量与距离的平方成正比;当距离大于等于该阀值，能耗则与距离的四次方成正比，因此在发送数据过程中，应尽量避免直接向远距离的节点发送数据来节约能耗[14]。

接收数据时能量消耗Er的计算公式为

其中，Erx为接收数据时的单位能耗，Er与接收数据的大小成正比。

1.2.4 数据因素

考虑到的数据因素包括:数据内容的大小以及数据的一致性。

无线传感器网络中需要传输大量数据，这就会消耗大量的能量。因此需要进行数据融合，即中间节点在对收到的数据进行转发前，先对其进行综合并去掉冗余数据，以节省传输能量并提高数据收集效率[1]。可设置一个数据阀值，接收数据与这个阀值相差越大则可信度的波动就会越大，以此来判断接收到数据的准确性。

同时，数据的一致性也是评估节点可信度的重要因素，通过检查数据的一致性来计算数据信任值。对数据内容的一致性进行评估，偏差越大则数据信任值越低;反之，偏差越小则数据信任值越高。

通过对数据信任值的评定，可以及时发现自私节点，以采取相关的安全措施来保障无线传感网络的数据安全。

2 算法描述

文中提出的兼顾多因素的簇头选择算法流程如图2所示。

图2 兼顾多因素的簇头选择算法流程图

2.1 节点信任度计算

(i)节点Ni和Nj是邻居节点，Ni对Nj的直接信任TDij是通过Nj对Ni的数据包转发率来衡量的 (dr为接收转发的包的数目，dt是实际转发的包数)

(ii)节点Ni对Nj的间接信任度通过Nj的邻居节点Nm的监控得到。定义P为其他推荐节点的集合，P={Nm|Ni的邻居节点，Tij≥信任推荐值Th}，P中所有节点对Nj的信任值加权平均，得到Ni对Nj的间接信任度

(iii)节点Ni对Nj的信任值为

其中，α表示TDij在信任值计算中所占权重，通过改变α的大小可以改变TDij和Mij二者的比例。

(iv)节点Nj的综合信任值Tj计算，通过计算Nj的所有邻居节点对它的信任值的均值得到，即

其中k为节点Nj的邻居节点的总个数。

2.2 通信信任值

β模型[15]利用节点过去的通信成功和失败的记录，通过计算预计未来通信成功的概率。两相邻节点Ni和Nj进行多次通信，使用β模型表示这两个节点间通信成功的概率，该模型概率密度函数为

其中，0＜x＜1，α ＞0，β ＞0。

该信任模型的期望公式为

假设节点Nj和Ni进行n次通信后，统计得到成功通信次数为Sji，失败次数为fji，由公式(6)可得节点Nj对Ni可信的期望值为

则该模型中，对下次通信的期望就是此次通信的信任值

综合Nj与其邻居节点多次通信的信任值，求和取均值，可得到该节点的通信信任值

2.3 能量信任值

节点Nj的现存能量为Ej，初始能量为E0，剩余能量比Hj为

节点在接下来一段通信过程中接收、发送及处理数据所需的能量为en，同时令Te=en/Ej，则有

则节点能量信任值Cj的计算公式为

其中p和q分别为Hj和Ij的所占权重，且p+q=1，由式(15)可以看出节点能量信任值Cj由剩余能量比Hj和Ij共同决定。

2.4 数据信任值

设置的数据信任值由两个内容决定:数据大小信任值和数据一致性信任值。

传输数据过大，则会消耗过多能量，并且容易被利用攻击，导致网络危险;而数据过小则有可能是自私节点为了节省自身能量而选择丢包[13]。为了节省能量，延长网络寿命的同时保证网络的安全，设置一个数据传输的阀值Ds，以此为数据大小的界限，综合经节点Nj发送给节点Ni的数据，其数据大小信任值DSji为

算出由节点Nj发送给它的所有邻居节点的数据的信任值，求出均值，则得到节点Nj的数据大小信任值

节点Nj采集数据一致的次数为Uj，数据采集不一致的次数为Vj，则节点Nj的数据一致性信任值DAj的计算方法为

综合以上两种信任值，在数据信任值的计算中，数据大小信任值所占权重为m，数据一致性信任值所占权重为n，且m+n=1，则有Nj的数据信任值

2.5 节点综合因子

节点Nj的综合因子需要考虑多种因素，节点信任度、通信、能量及数据因素，将以上几个方面整合起来就得到传感器节点的综合因子

其中，a、b、c和d都为权重因子，计算节点综合因子时按各个因素的重要程度来选择其大小，某因素权重因子越大则表示该因素越重要，且有(a+b+c+d)=1。设定一个因子阀值Ws，一旦节点能量耗尽或者综合因子小于该阀值，则自动被当作死亡节点处理。

2.6 簇头选择

综合因子计算出来后，根据各个节点的综合因子值进行簇头选择。设定综合因子的阀值Wn，一旦某节点综合因子低于该阀值，则默认为是恶意节点，同时也被定义为死亡节点。而综合因子越大的节点越可信，按照簇头节点在该簇内所占比例p，算出簇头节点的个数p×n，再选择综合因子Wj大的节点担任簇头。

3 仿真实验

仿真实验通过Java代码和MATLAB来实现。实验中，在200 m×200 m空间内随机选取100个节点，模拟无线传感网的通信，通过每个轮次的通信，观察节点的信任度、通信信任值、剩余能量比以及数据信任值。该实验中选取节点信任度权重a为30%，通信信任值权重b为20%，剩余能量比权重c为30%，数据信任值权重d为20%，最后通过计算算得节点的综合因子。实验中其他的参数设定如表1所示。

表1 基本参数设定

实验1:基于文中的信任模型，分别对网络中的某一个正常节点和非正常节点的综合因子的变化情况进行监控。

图3 正常节点综合因子变化图

图4 非正常节点综合因子变化图

选取该网络中某一正常节点，其综合因子变化情况如图3所示。由于能量消耗，该节点正常通信情况下，综合因子数值呈缓慢下降趋势。非正常节点的综合因子的变化如图4所示，一旦节点产生恶意行为例如传送数据过大或过小，就会导致节点综合急速下降。因此该模型可以很好的区别出正常节点和恶意节点。

实验2:比较两种算法的网络生存周期。

如图5所示，数据1代表的是仅考虑节点信任度和剩余能量比时的网络生存周期;数据2则代表使用文中兼顾多因素的算法时的网络生存周期。分别使用两种算法，进行500轮通信，观察存活节点的个数变化。通过图示的对比可以看到，文中所描述的算法使得网络生存周期延长了近20%。从而证明使用该算法可以延长网络生存周期。

图5中，在刚开始的几轮通信中数据2的图像迅速下降，说明开始几轮通信就出现了节点死亡，而死亡的节点就是恶意节点，说明本算法中恶意节点在刚进行一点恶意行为后就被检测出来，从而增强了网络的安全性。

实验证明该算法的实用性以及安全性。

图5 节点生存周期图

4 结束语

在借鉴现有的信任模型及簇头选择算法的基础上，提出一种适用于无线传感网的兼顾节点信任度、通信、剩余能量比以及数据多因素的簇头选择算法。与只考虑信任与能量的簇头选择算法相比，新的算法有效延长了网络生存周期，同时可以在开始通信不久就识别出恶意节点，大大增强了网络的安全性。考虑到多种因素的簇头选择算法，为无线传感网中的信任评价提供一种新的思路，但是该算法在安全性上仍需要进一步的考虑，同时对网络能量消耗、算法的复杂性和算法计算时消耗能量问题应有更多考虑，这就是下一步要进行的研究工作。

致谢:感谢成都市科技攻关项目(2014-HM01-00108-SF)对本文的资助

[1] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京:清华大学出版社，2005:90－100.

[2] 林楠，史苇杭.无线传感器LEACH算法的优化及仿真[J].计算机仿真，2011，28(1):178－181.

[3] Heinzelman W B，Chandra K A，Bala K H.An Application-specific Protocol Architecture for Wireless Micro-sensor Networks[J].IEEE Transactions on Wireless Communications，2002，1(4):660－670.

[4] 张震，闫连山，潘炜，等.基于 LEACH和 PEGASIS的簇头成链可靠路由协议研究[J].传感技术学报，2010，23(8):1173－1178.

[5] Lindsey S，Raghavendra C，Sivalingam K M.Data Gathering Algorithms in Sensor Networks Using Energy Metrics[J].IEEE Trans on Parallel and Distributed Systems，2002，13(9):924－935.

[6] 周立朋，卡米力·木衣丁.WSN中兼顾安全和剩余能量的簇头选择算法[J].计算机工程与应用，2012，48(3):88－90.

[7] 陈云峰，范兴刚，许博.基于LEACH的WSN簇头优化策略[J].计算机工程，2011，37(22):82－87.

[8] 王伟超，代增全，徐启建.LEACH协议簇头选择算法的改进[J].无线电工程，2010，40(3):1－3.

[9] 张浩，李腊元.基于LEACH协议的能耗均衡路由算法[J]. 计算机工程，2011，37(7):91－93，111.

[10] 孙秋景，曾平凡，曹勇.基于可信推荐节点集合的P2P信誉模型[J].计算机工程，2010，36(20):142－144.

[11] 胡光明，胡华平，龚正虎.簇结构移动自组网络中基于推荐的局部信任模型[J].计算机工程与应用，2006，29:16－22.

[12] 吴磊.无线传感器网络防范恶意节点信誉机制研究[D].重庆:重庆大学，2013.

[13] 张仕斌，陈建钧，杨骏伟.WSNs中基于簇结构的云信任模型研究[J].四川大学学报:工程科学版，2014，(8):1－6.

[14] 刘艳飞.基于分层信任管理的无线传感器网络信任模型[D].太原:太原理工大学，2015.

[15] 冯健昭，肖德琴，杨波.基于β分布的无线传感器网络信誉系统[J].计算机应用，2007，27(1):111－113.