成簇阶段恶意节点识别与剔除模型研究及实现

李小庆，袁一方，何冰

（1.武汉大学电气工程学院，湖北武汉430072；2.武汉大学经济与管理学院，湖北武汉430072；3.武汉大学测绘学院，湖北武汉430072）

随着传感器技术、嵌入式技术以及低功耗无线通信技术的发展，生产具备感应、无线通信以及信息处理能力的微型无线传感器已成为可能。这些廉价的、低功耗的传感器节点共同组织成无线传感器网络（WSN，wireless sensor network），通过节点间的相互协作，将其监测和感应的多种环境信息（如温度、湿度等）传回到远程基站进行处理[1]。由于受到成本、体积等因素的限制，传感器节点的处理能力、无线带宽，以及电池容量等资源非常有限。并且在很多应用中，传感器节点都被部署在环境恶劣的地区，节点的能量无法得到补充，于是如何延长传感器网络的生存时间和实现安全的数据通信成为设计上需要考虑的一个难题。

将传感器节点安全分簇是目前解决这一问题的重要方法。分簇的基本思想是通过簇首对簇内节点间的相关信息融合及转发机制减少数据的传输量和距离，进而降低通信能量，达到网络节能的目的。传感器网络的主要任务是将网络中传感器节点收集的数据传送给基站。实现该任务的一种最简单方法是使用直接传送[2]，即网络中的每个节点把收集到的数据直接传送给基站。然而，对于远离基站的传感器节点，节点直接传送数据消耗的能量代价太高将使节点很快死亡。为解决这个问题，目前已经提出了许多以节约能量为目的的分布式成簇算法，如LEACH[3]，PEGASIS等。

LEACH（low energy adaptive clustering hierarchy）协议是MIT学者Heinzelman等人为无线传感器网络设计的低功耗自适应聚类路由算法，其出发点主要是考虑一簇节点内的能量消耗问题，目的是为了延长节点的工作时间，并且实现节点的能耗平衡[4]。它以轮换的簇首选择方式，将簇首的繁重转发任务交由各个节点均衡分担，从而达到节点能量消耗均衡的效果，延长网络的整体存活寿命。然而此算法的分簇原理虽然可行但是每个簇中仍存在恶意节点的问题，因此从节点到基站传输数据的安全问题和能量高效问题依旧是安全敏感的无线传感器网络应用面临的主要问题。

本文在网络分簇阶段应用SECA（Secure Encryption Clustering Algorithm）安全密钥成簇算法[5]，实现在成簇阶段及时对恶意节点进行识别和剔除，尽可能减小恶意节点对网络的破坏。它借鉴了LEACH算法的簇首轮转思想，在分簇阶段就引入密钥预分布方案，从而保证网络节点之间的通信安全性，同时优化每一轮生成的簇内结构，使得每一轮的能耗尽可能小，以达到延长网络寿命的目的。

1 模型假设

假设n个传感器节点随机均匀地分布在一个L×L的正方形区域内，并且该传感器网络具有如下的性质：

1）在传感器节点区域较远的地方固定有一个基站sink；

2）区域内的所有传感器节点都是同构（传输半径和传输角相同）的，节点能量有限为Eo，具有相似的处理和通信的能力，并对网络具有相同的重要性；

3）节点分布之前是安全的，未受到任何入侵行为引起的篡改和破坏；

4）数据的采样周期长，采集到的数据通过数据融合技术进行综合处理；

5）每个节点都可以通过单跳方式与基站进行直接通信；

6）节点通信是对称的，即从节点x传送消息m到y消耗的能量和从y传送消息m到x所消耗的能量是相同的；

7）节点ID在出厂后是不可以更改的；

8）每个传感器节点都携带有一个相同的主密钥，节点间的任何通信都须用主密钥基于AES对称密码算法进行加密和解密处理来识别网络中的恶意节点所阻挠数据通信。

9）假设节点进行通信工作时，按照LEACH算法的层次模型进行，即是簇内普通节点只能与本簇内其他节点以及簇首通信，簇间信息交换由簇首来完成，簇首可以直接将数据包融合后发给基站。

10）恶意节点通过密钥不匹配被识别，并告之其他网络内节点，在下一轮成簇的过程中将被识别的恶意节点剔除，不允许其加入任何一个簇，排除在有效网络之外。

2 关键变量说明

表1 部分变量说明Tab.1Part of the variable declaration

3 数学模型建立

模型设定初始的成为簇首的概率为p=0.05，然后模型按照T（n）的概率计算方案计算各个节点的被选择为簇首的概率。

由于LEACH算法是以t为周期进行新一轮分簇，而每一轮分簇都会识别并剔除恶意节点和已经消耗完能量死去的节点，故每一轮网络中剩余的有用节点数目会不断递减。引入布尔变量bool（i）来记录是否网络可以正常工作。判断标准定义为：现存活的有用节点数目不少于原始总节点数n的一半。Liv为bool的累加和。由于重新分簇具有周期性，故统计网络有效工作期间已进行的重新分簇轮数即可以等效描述网络的存活时间。数学表达公式如下：

等效存活时间Liv=Σbool（i）

4 MATLAB仿真模型的建立

算法流程描述如下：

1）假定初始状态各个节点都是正常的、安全。由基站根据初始概率p和公式T（n）的计算结果初始确定第一轮簇首。

2）各个簇首向整个网络广播自己被选为簇首的信息，其他节点接收到广播信息以后，分别计算自己与各个簇首的距离，选择最近的簇首就近加入其所在簇。第一轮分簇完成。

3）分配给同簇节点共享密钥，不同簇之间密钥不同。分配给簇首以簇首通信密钥。

4）进行t时间的加密数据通信。任何一次数据通信或者消息交换都需要进行密钥认证。同簇之间可以自由通信，但是簇间通信只能由簇首来完成，簇首均有能力直接向基站发送数据包。

5）随机在网络中选中1个或者2个（随机）的节点，赋予它们恶意节点的行为特征：节点向异簇节点发出通信请求。正常节点运行时候，若不是簇首不会向异簇节点发起会话请求，即便是簇首节点也只能向其他簇首节点发送请求。而恶意节点的特征是无论自己或者对方是否同簇或者是否为簇首，均向其发起数据请求。这种行为在模型中被认为是非法的。

6）节点加密通信的过程中，若某节点A检测到密钥不对的非法通信请求，即将该请求节点ID记录加入黑名单devil中。

7）该节点A立即向簇首（若A是普通节点）或者基站（若A是簇首）发布黑名单中的恶意节点ID，告示其它节点对这个ID的消息实施封锁。

8）周期t时间到。开始新的一轮簇首选取。如步骤1）。

9）各节点计算自己与各簇首之间的距离，请求加入较近的簇首所在簇。这时簇首节点对请求节点发起安全认证。如果在黑名单devil中有记录，则拒绝其加入本簇。并广告给其它簇首节点，拒绝将其加入新簇。基站将这类孤立的恶意节点剔除出网络。将剩余能量为0或者小于0的节点清理出网络。于是，新簇形成。

10）重复步骤3）、4）、5）、6）、7）、8）、9）。

11）所有节点均被剔除（恶意的节点，死亡的节点），网络停止，结束。

在MATLAB[6]平台上编写仿真程序，并运行，运行结果如图所示。

图1 基站和节点分布图Fig.1Distribution of the base station and nodes

图2 恶意节点Fig.2Malicious nodes

其中图1为初始状态随机产生的节点位置以及基站位置分布。图3为剩余节点数与循环轮数、概论簇头数与循环轮数的关系。由图3可以观察到：使用密钥预分配方案后，系统的寿命（以Liv为标准）大约为320轮左右。恶意节点的分布图如图2所示。图4为没有将恶意节点识别并剔除的网络剩余可用节点与循环轮数的关系。由图3和图4可以明显看出，恶意节点的识别和剔除对于网络的生存性能非常重要。并且基于LEACH算法的密钥分配方案对于恶意节点的识别和剔除效果较好。

图3 剩余节点数与循环轮数、该轮簇头数与循环轮数的关系Fig.3Relationship of the remaining nodes and recycling rounds、The number of cluster heads and recycling rounds

图4 没有剔除恶意节点的网络剩余节点数与循环轮数、该轮簇头数与循环轮数的关系Fig.4Relationship of the remaining nodes and recycling rounds、The number of cluster heads and recycling rounds without moving malicious nodes out

5 模型分析

在无线传感器网络中，安全的成簇算法是减少能量消耗的一种关键技术，它能够增强网络的扩展性，延长网络的生存时间。与已有探索性研究成果相比，本模型将安全技术前移至成簇阶段进行，并基于密钥预分配方案来识别恶意节点，从开始就阻截攻击行为，有助于从根本上保障所采集信息的真实性和可靠性。借鉴LEACH成簇算法，将能效目标、成簇效率结合起来，有助于最大限度提高网络的存活性和鲁棒性。

模型基于层次通信网络模型，建模简单，思路清晰，重点在于成簇阶段恶意节点的识别和剔除。模型采用密钥预分配的方案实行安全成簇算法，较之“虚假数据”、“错误数据”等普通判断方法，提高了恶意节点的识别率，有助于整个网络的网络寿命的提高和网络性能的维护。此外，模型采用等效存活时间的判断标准，合理简洁。可以很好地反映网络的存活指标。方法通俗，可推广性能高。

当然，无线传感器网络的实际通信过程是一个很复杂的过程，远不止模型中假设的层次通信那么简单。所以模型具有一定的实际局限性，与实际现实情况有一定差距。此外，恶意节点的特征描述稍显简单，可以适当加入多个判断标准同时加以判断。从而确保不漏判不错判，进一步提高系统的性能和效率。

6 模型改进

由于本次仿真的主要是基于恶意节点的识别与剔除，所以在建立模型的时候弱化了自组织网络的通信特性。目前，无线传感器网络存在的攻击模型主要有：虫洞攻击（Wormhole攻击）、黑洞攻击（Sinkhole攻击）、女巫攻击（Sybil攻击）、虚假路由信息攻击、选择性转发攻击、HELLO泛洪攻击以及欺骗性确认攻击。其中Wormhole攻击、黑洞攻击、女巫攻击是3种比较典型的攻击方式，也是基本的攻击手段，其他的攻击方式常结合这3种攻击方式进行。

基于以上实际无线传感器网络的特性，模型改进方向可以设置为：自组织邻居通信，针对典型攻击明确恶意节点的行为和其他特征。从而更加真实地仿真网络系统的通信过程，在多特征识别的优势下，更加准确的识别和剔除对网络性能破坏的恶意节点。进一步，更加准确、实用地在成簇阶段处理恶意节点来提高网络的整体性能和网络工作寿命。

[1]孙利民.无线传感器网络[M].北京:清华大学出版社，2005.

[2]YU YY，CHONG PHJ．A Survey of Clustering Schemes for Mobile Ad Hoc Networks[J]．IEEE Communications Surveys and Tutorials，First Quarter，2005，7（1）：32－48．

[3]Heinzelman WR，Chandraka SAN A，Balakrishnan H．Energyefficient communication protocol for wireless microsensor networks[C]//Proceeding33rdAnnualHawaiiInternationalConference on System Sciences（HICSS00），2000:3005－3014．

[4]佘静涛，胡同森，钟明霞.无线传感器网络路由协议LEACH的研究与改进[J].计算机系统应用，2009（2）：30－34.SHE Jing-tao，HU Tong-sen，ZHONG Ming-xia.LEACH routing protocol for wireless sensor networks Research and Improvement[J].Applied Computer Systems，2009（2）:30－34

[5]胡向东，蔡东强.无线传感器网络安全加密成簇算法的设计及研究[J].重庆邮电大学学报：自然科学版，2009，21（3）：421－424.HU Xiang-dong，CAI Dong-qiang.Wireless sensor network security encryption algorithm design and research clusters[J].Chongqing University of Posts and Telecommunications：Natural Science，2009，21（3）：421－424.

[6]张志涌，杨祖樱.MATLAB教程[M].北京:北京航空航天大学出版社，2010.