基于非均匀分簇的HWSN密钥预分配方案的研究

黄慧娟，许 勇，张 海

(安徽师范大学 数学与计算机科学学院，安徽 芜湖 241003)

基于非均匀分簇的HWSN密钥预分配方案的研究

黄慧娟，许 勇，张 海

(安徽师范大学 数学与计算机科学学院，安徽 芜湖 241003)

密钥管理问题一直是无线传感器网络中的热点研究问题之一。针对传统的密钥预分配方案具有能量不均衡以及网络生存周期短的问题，文中设计了一种新的基于分簇结构的异构传感器网络的密钥预分配方案(New Clustering In Key Pre-distribution，NCIKP)。详细给出了簇首选择过程、非均匀分簇过程以及密钥预分配过程,在选择簇首时将同时考虑节点的能量消耗率、节点到基站的距离以及节点的邻接程度。通过仿真实验与分析，相较其他的密钥预分配方案，此方案较好地满足了异构传感器网络的安全和能耗需求。

异构传感器网络;非均匀分簇;密钥预分配;能量均衡

0 引 言

随着无线传感器网络(Wireless Sensor Networks,WSN)[1]的应用发展，WSN的安全通信日益受到关注。传感器节点通常被随机置于无人监听环境之中，易遭受窃听威胁，也容易被捕获和破坏，这使得一些常用加密体系中的密钥管理方法(如公钥加密体系)不再适用于传感器网络。目前，在WSN安全通信中，较为普遍使用的是密钥预分配方案[2-9]。根据WSN构造形态，可将其分为异构传感器网络(Heterogeneous Wireless Sensor Networks，HWSN)和同构传感器网络。同构传感器网络的密钥预分配方案的研究已有很多成果[3-6]，相对而言，针对异构传感器网络的密钥预分配方案[8-9]还比较少。

文中主要关注异构传感器网络中的密钥预分配问题。因异构传感器网络中节点具有能量差异性，在进行密钥预分配过程中，若不进行节点能量的均衡与优化，则可能导致部分节点过早耗尽能量而失效。因此文中设计了一种新的基于分簇结构的异构传感器网络密钥预分配方案(New Clustering In Key Pre-distribution，NCIKP)，采用二级网络结构,综合考虑节点的能量消耗率、节点到基站的距离以及节点的邻接程度选择簇首,用以均衡节点的能量消耗；同时，簇首节点通过竞争形成不同半径的簇,以防止“热区”的出现；在此基础上分别对簇首节点以及簇内节点进行密钥预分配。

仿真实验表明，该方案具有较好的安全性能，有效提高了网络能量利用率,延长了网络生存周期。

1 相关工作

密钥预分配一直是无线传感器网络安全研究领域的一个研究热点。对于同构无线传感网络,2003年，Eschenauer和Gligor[3]提出了最经典的E-G方案,其基本思想是：每个节点从一个大的密钥池中随机分配一些密钥来构成自己的密钥环，需要通信节点之间通过发现彼此密钥环中的公共部分来确定共享密钥，然后选择一个作为其会话密钥。该方案由于不需要任何先验信息，所以安全性一般；随后Chan等[4]在E-G方案上进行改进，提出了q-composite方案，将2个节点之间共享密钥数提高到q个，增强了安全性；Du等[5]提出了一种根据节点部署信息的密钥预分配方案,有效提高了网络的连通性；2013年，王小刚等[6]提出了一种基于二次型的无线传感器网络密钥管理方案，该方案利用二次型正交对角化特性建立会话密钥，提高了安全性和可扩展性。

关于异构无线传感器网络，早在2002年，Duarte等[7]就指出了对比传统的同构无线传感器网络，异构传感器网络具有更长的生命周期和可测性。据此，马春光[8]等于2009年提出了一种基于区域的异构无线传感器网络密钥预分配方案。该方案将网络监测范围划分为多个区域，同时将密钥池也划分为多个子密钥池，在一定程度上提高了相邻节点共享密钥的概率，但是密钥池的划分较为复杂;2010年，马春光等[9]又提出了一种基于按对平衡设计的异构无线传感器网络密钥预分配方案。该方案针对网络中节点的异构性，利用按对平衡设计构造了不同的节点密钥环，增加了网络的连通性，有效降低了网络的通信负载。但上述方案仅实现了安全的密钥预分配，没有考虑不同节点的能量差异性，在实际运行中，部分节点可能因能量过早耗尽而引起失效。

针对这个问题，研究者们给出一种分簇算法，通过合理构造分簇结构，将在实现安全通信的同时，也能达到均衡网络能量消耗及延长网络寿命的目的。经典的分簇算法有LEACH[10]、HEED[11]等，但这些算法在选择簇首节点时随机性比较大，而且在能量节省方面也考虑不够；2007年，陈贵海[12]等提出一种非均匀分簇路由机制(EEUC)。该算法考虑到了节点剩余能量这一因素，实现了节点间的能量消耗平衡，但仍没有解决簇首节点选择时随机性较大的问题。2006年，卿利等[13]提出了一种异构传感器网络的分布式能量有效成簇算法(DEEC)。该算法将节点剩余能量作为选择簇首节点的主要因素，并且给出了计算最优簇头公式以及优化簇头比例公式,可是该算法没有考虑到节点在网络中所处的位置，仅以节点剩余能量为依据，存在靠近基站的节点由于承担过多的任务而过早能量耗尽的问题。2014年，刘唐等[14]提出了一种异构传感器网络的分簇算法(DUBP)。该算法首先利用能耗因子进行动态分区，再利用Floyd算法计算节点的路径因子，随后进行分簇。算法在一定程度上延长了网络寿命，但仅考虑普通节点间的能量消耗，却未考虑到簇首间的能量均衡。

总体上说，现有的分簇算法存在的问题主要有两点:一是在簇首选择时考虑的因素不够全面，具有较大的随机性，存在部分节点过早能量耗尽的问题；二是鲜有考虑到簇首节点间的能量均衡，使得靠近基站的簇首不仅要承担本簇的数据融合任务，且要为其他簇进行数据转发，即存在“热区”问题。

2 NCIKP方案设计

通过对传统的密钥预分配方案的研究，针对其在进行安全通信时未能很好地实现节点能量均衡的问题，给出了一种解决方案，即设计了一种针对异构传感器网络的基于分簇结构的密钥预分配方案。

2.1 基本假设

该方案假设共有N个传感器节点，随机分布在一个W*W的正方形区域内，所有的节点是静止或者是微移动的，从而避免网络拓扑结构频繁改变。

表1为方案中的符号及其意义。

2.2 分 簇

2.2.1 分簇准备

定义1(节点到基站的距离)：

(1)

定义2(节点的邻接程度)：与节点i之间的跳数不超过2跳的节点都是i的相邻节点。

(2)

定义3(节点的能量消耗率)：

(3)

定义4(节点权值)：

w(i)=di,BS*a+N(i)*b+v(i)*(1-a-b)

(4)

2.2.2 簇首选择

(1)阈值T(n)的推导。

表1 方案中的符号及其意义

文献[13]提出计算优化簇头的公式：

优化簇头比例为：

假设形成的簇共有L个节点，除去簇首节点，簇内还有L-1个节点，则簇内节点到基站的平均距离可表示为：

结合式(3)可推出簇内节点的平均损耗率为：

结合式(2)可推出簇内节点的平均相邻节点数目为：

综合上述分析，这里给出更适合异构传感器网络的节点成为簇首节点的概率公式：

(5)

在LEACH给出的阈值T(n)计算公式的基础上进行改进，得到新的阈值计算公式：

T(i)=

(6)

其中，G为最近1/P轮中还未当选簇首的节点的集合；r为节点连续未当选簇首节点的轮数，一旦当选，将r重置为0。

(2)簇首节点产生流程。

①通过节点与节点间、节点与基站间发送消息，每个节点分别算出自己到基站的距离、自己的邻接节点数、能量损耗速率即di,BS,N(i)以及V(i)。

③节点根据式(6)计算成为簇首节点的概率门限阈值T(i)。

⑤其余节点在本轮竞争结束前都保持睡眠状态，在本轮竞选结束后，下一轮竞选按照上述四个步骤重复进行。

2.2.3 分簇形成

(1)簇半径计算公式。

文中采用文献[12]中节点的竞争半径公式：

(7)

其中，dmax为网络中节点距离基站BS的最远距离；dmin为网络中节点距离基站BS的最近距离；C为0-1之间的一个常数；Rmax为网络中允许的最大竞争半径。

(2)每轮非均匀成簇流程。

①节点计算自己成为簇首的概率p(i)以及阈值T(i)。

③临时簇首节点广播自己的标识号ID，竞争半径Ri以及权值w(i)。

④若节点j收到i发送来的消息，便开始接下来的判断。

⑤若满足d(i,j)

⑥i检查是否本簇中所有节点的权值都小于自己的权值，若是，则广播一条消息BEHEAD_MSG(ID)给所有相邻的临时簇首节点，通知自己成为本轮簇首。

⑦若i收到本簇中节点j成为簇首的广播消息，则i必须放弃本轮簇首的机会，然后广播一条退出消息QUIT_MSG(ID)。

⑧若i收到一条来自簇中j的退出请求消息QUIT_MSG，则立刻将j从簇中删除。

⑨在每轮簇首节点竞争结束后，其余普通节点就从睡眠状态恢复过来，所有的簇首节点广播一条CH__MSG到全网，普通节点判断收到的来自不同簇首节点的消息，选择加入一个信号最强的簇中，然后给该簇首节点发送消息JOIN_CH_MSG,通知其自己成为它的簇成员。此时该轮的成簇过程完成。

2.3 密钥预分配

此阶段包括四个部分：基站为簇首分配密钥、簇首为簇内节点分配密钥、同一簇内节点的通信、不同簇内节点的通信。

2.3.1 基站为簇首分配密钥

基站产生一个密钥池S，为每一个密钥分配一个唯一的编号KID；在上面阶段通过竞争当选簇首的节点向BS发送Cki,BS(ID,di,BS)，告知基站自己成为了簇首；基站根据di,BS来给簇分配一个唯一的编号CID(di,BS越小，CID越小)；簇首节点广播消息(CID,ID)来发现自己的邻接簇，发送给基站自己邻接簇的CID，让基站知道整个网络的簇首之间的相邻关系；基站根据簇首的邻接簇数目以及邻接簇已分配密钥的情况为每个簇分配一定的密钥，构成自己的密钥池。

2.3.2 簇首为簇内节点分配密钥

簇首生成本簇内的会话密钥CHK，簇首节点从上面分配得到的密钥池中随机选择r个密钥分配给簇内节点，构成节点的密钥环，分配的密钥数不宜过多也不宜过少，过少会出现“孤立点”，从而导致通信困难；过多可能会造成单个节点被捕，整个网络瘫痪的危险。

2.3.3 同一簇内节点的通信

2.3.4 不同簇内节点的通信

为安全起见，规定不同簇内节点通信必须选择簇首节点作为中间节点。假设2个位于不同簇的节点i,j想要通信，它们分属的簇头分别为C1,C2，若2个节点间有k1,k2,…,kL个相同密钥，则利用hash函数计算，得到hash(k1‖k2‖…‖kL),来作为二者的共享密钥Ki,j，节点i用Ki,j将要发送的数据进行加密，得到EKi,j(数据)，然后用CHK1进行第二次加密，即把ECHK1{EKi,j(数据)}发送给C1，C1用CHK1解密，得到EKi,j(数据)；C1用其与C2的密钥KC1,C2加密EKi,j(数据)，随后发给C2；C2用KC1,C2解密，然后用CHK2加密得到ECHK2{EKi,j(数据)}，发给j,j随后两次解密得到原始数据，通信完成。

3 安全性分析及性能分析

3.1 安全性分析

在该方案中，簇首节点需要向基站注册自己的身份以及邻接簇情况，因此即使一个簇首被攻击者冒充，也会立即被基站检测出来；基站根据簇首邻接簇情况为其分配密钥，随后簇首再从自己的密钥池中随机取部分密钥分配给簇内节点，因此不同节点被分配到相同密钥的概率较低；在同一个簇内节点通信时，若采用以往算法中通过广播节点密钥来建立会话密钥的方法，则会增加被攻击的概率，因此该方案中同簇节点建立会话密钥时采用节点取自己的密钥来加密一个随机数和本簇标识号并与其他节点加密结果比较的方法，提高了安全性；此外该方案规定，在不同簇内节点通信时必须经过簇首节点的转发，进行二次加密，可以保证即使一个簇被攻击，也不会影响到其他簇的安全，且利用了hash函数的单向性，有效防止攻击者从单个节点的密钥来推算出节点间的通信密钥。

3.2 性能分析

利用Matlab对文中分簇算法与LEACH和EEUC协议进行性能比较分析。采用文献[10]中提出的无线通信系统能量消耗模型来进行计算。

(1)传送一个l bit的数据包到距离d的节点需耗费的能量为：

(2)接收一个lbit字节的数据包需要的能量为：

ERx(l)=lEelec

表2为仿真采用的参数表；图1为仿真场景图。

表2 仿真参数表

图1 200个节点随机布于200 m*200 m的区域

死亡节点个数和网络剩余能量随着进行的轮数变化情况比较见图2和图3。

4 结束语

文中设计了一种针对异构传感器网络的基于分簇结构的密钥预分配方案(NCIKP)。在该方案中，首先给出了一种新的分簇算法，该算法可以有效地均衡节点间的能量消耗；在密钥预分配过程中，将分别对簇首节点和簇内节点进行预分配，以降低节点被分配到相同密钥的概率；同一簇内节点在建立会话密钥时，只需随机取一个密钥加密一个随机数以及本簇标识号，并与其余节点加密结果相比较即可，避免了广播密钥带来的被攻击的风险；不同簇节点通信时，规定必须经过簇首节点的转发，进行二次加密，因此即使一个簇被攻击，也不会影响到其他簇的安全，此外还加入了Hash函数，利用其单向性来进一步提高网络的安全性。

图3 网络剩余能量随着进行的轮数变化情况比较

通过仿真实验表明，该方案具有较强的安全性，此外获得了更好的能量利用率以及更长的网络生命周期。

方案暂未考虑到异构传感器网络中节点的移动性这一问题，此外如何降低节点的计算和存储开销也将是下一步工作研究的重点。

[1] 苏金树,郭文忠,余朝龙,等.负载均衡感知的无线传感器网络容错分簇算法[J].计算机学报,2014,37(2):446-456.

[2] 孙力娟,魏 静,郭 剑,等.面向异构无线传感器网络的节点调度算法[J].电子学报,2014,42(10):1907-1912.

[3]EschenauerL,GligorVD.Akey-managementschemefordistributedsensornetwork[C]//Procof9thACMconfoncomputerandcommunicationsecurity.Washtington,DC,USA:ACM,2002:41-47.

[4]ChanH,PerrigA,SongD.Randomkeypre-distributionschemeforsensornetworks[C]//ProceedingsofIEEE2003symposiumonsecurityandprivacy.Berkeley,CA,USA:IEEE,2003:197-210.

[5]DuW,DengJ,HanY.Akeymanagementschemeforwirelesssensornetworksusingdeploymentknowledge[C]//ProceedingsofIEEEINFOCOM’04.HongKong,China:IEEE,2004:586-597.

[6] 王小刚,石为人,周 伟,等.一种基于二次型的无线传感器网络密钥管理方案[J].电子学报,2013,41(2):214-219.

[7]Duarte-MeloeJ,LiuMY.Analysisofenergyconsumptionandlifetimeofheterogeneouswirelesssensornetworks[C]//ProceedingsofIEEEGLOBEC-OM.Taipei:IEEE,2002:21-25.

[8] 马春光,尚治国,王慧强.基于区域的异构无线传感器网络密钥管理[J].通信学报,2009,30(5):74-81.

[9] 马春光,张秉政,孙 原,等.基于按对平衡设计的异构无线传感器网络密钥预分配方案[J].通信学报,2010,31(1):37-43.

[10]HeinzelmanW,ChandrakasanA,BalakrishanH.Anapplication-specificprotocolarchitectureforwirelessmicrosensornetworks[J].IEEETransactionsonWirelessCommunications,2002,1(4):660-670.

[11]YounisO,FahrnyS.Heed:ahybird,energy-efficient,distributedclusteringapproachforad-hocsensornetworks[J].IEEETransonMobileComputing,2004,3(4):660-669.

[12] 李成法,陈贵海,叶 懋,等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(1):27-36.

[13]QingLi,ZhuQingxin,WangMingwen.Adistributedenergy-efficientclusteringalgorithmforheterogeneouswirelesssensornetworks[J].JournalofSoftware,2006,17(3):1282-1291.

[14] 刘 唐,孙彦清.基于负载均衡和最短路径的异构无线传感器网络成簇算法[J].计算机科学,2014,41(10):169-172.

[15] 刘 唐，汪小芬，杨 进.基于相对距离的多级能量异构传感器网络成簇算法[J].计算机科学,2012,39(8):119-121.

Research on Key Pre-distribution Scheme for Heterogeneous Wireless Sensor Networks Based on Unequal Clustering

HUANG Hui-juan,XU Yong,ZHANG Hai

(College of Mathematics and Computer Science,Anhui Normal University,Wuhu 241003,China)

The key management is always one of hot topics in wireless sensor network.For many traditional key pre-distribution scheme with energy imbalance and network short lifetime problem,a new cluster-based key pre-distribution scheme (New Clustering in Key Pre-distribution,NCIKP) for Heterogeneous Wireless Sensor Networks (HWSN) is proposed.The cluster head selection process,unequal clustering process and key pre-distribution process are given in detail.In the selection of cluster head,also consider node energy consumption rate,node distance to the base station and node adjacency degree.According to the simulation experiment,compared with other key pre-distribution scheme,it’s better to meet the security and consumption demand for HWSN.

heterogeneous wireless sensor networks;unequal clustering;key pre-distribution;energy balance

2015-04-03

2015-07-08

时间：2016-01-04

安徽省自然科学基金资助项目(11040606M137)

黄慧娟(1990-)，女，硕士研究生，研究方向为计算机网络与信息安全；许 勇，博士，教授，硕士生导师，研究方向为计算机网络与信息安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1608.078.html

TP393

A

1673-629X(2016)02-0077-05

10.3969/j.issn.1673-629X.2016.02.018