WSN中基于邻居发现的动态密钥管理方案

尚凤军，周永奎

（重庆邮电大学 计算机科学与技术学院，重庆400065）

0 引 言

无线传感器网络 （WSN）是集微电子技术，传感器技术，通信技术于一体而组建的网络，可广泛应用于军事和商业等领域［1］。无线传感器网络往往部署在无人监管或容易受损被俘获的环境中，保证无线传感器网络的安全是应用中首先考虑的问题［2］，其中密钥管理机制是保证无线传感器网络安全的核心机制［3，4］。但是由于节点资源有限，无固定基础设施支持，节点易受损等问题，传统网络中的密钥管理机制往往不能直接应用于无线传感器网络中，安全问题一直是学术界研究的重点［5］。

近年来，研究人员提出了大量应用于无线传感器网络的动态密钥管理方案，Moharrum和Eltoweissy提出了基于EBS的动态密钥管理方案，但该方案属于集中式密钥管理方案［6］，不能适用于节点数目较多的大规模网络；Elwoweissy等人提出了基于EBS动态密钥管理方案LOCK （localized combinatorial keying）［7］，在分簇的基础上为簇内普通传感节点动态分配管理密钥，具有节点删除，密钥更新等功能，但存在共谋攻击的问题；Younis在层次式 WSN里提出基于位置信息的EBS动态密钥管理方案SHELL（scalable，hierarchical，efficient，socation－aware and lightweight）［8］，该方案能够有效抵御节点共谋攻击，但是该方案需要节点具有定位能力获得节点的具体位置，且网络拓扑结构发生变化后，该方案抵抗共谋攻击的能力下降。

针对以上方案的缺点，为提高网络的安全性能，减少节点开销，本文提出一种基于邻居发现的动态密钥管理方案 （NDDK）具有以下优点：

（1）该方案通过邻居发现过程在簇首中形成整个簇的拓扑结构模型，进一步生成密钥分配方案，不需要通过GPS等定位技术获取节点的位置信息；

（2）该方案采用节点分层算法用于生成EBS矩阵进行密钥分配，与SHELL中启发式搜索算法相比减少了簇首节点的计算开销，增强了网络抵抗共谋攻击的性能；

（3）该方案引入同化二元同化多项式［9］代替普通密钥，提高了节点抵抗俘获攻击性能；

（4）该方案在网络拓扑结构发生变化之后仍能保证节点分配密钥组合最佳，总体上提高了网络抵抗共谋攻击的性能。

1 系统介绍

EBS是由Eltoweissy等于2004年提出的一种分层式的基于组合优化原理的应用于无线传感器网络中的组通信密钥管理方案［10］。EBS系统通常表示为集合 （n，k，m），其中n为每一组传感器节点的数量，k＋m表示每一组传感节点所拥有的管理密钥的总量，k表示每个节点分配的管理密钥的数量，m为密钥更新的信息数。EBS系统是由包含部分节点的子集 （A1，A2，A3……）构成的集合Г。每个子集A是由一系列含有同一管理密钥的节点构成的集合。

定理1 当Ckk＋m≥n时k＋m中的任意k＋m个组合均可以构成EBS（n，k，m），从而形成一个EBS动态密钥分配方案。

定理2 通过广播最多m个数据包动态取消或更新任意节点所有的k个密钥，从而实现节点的删除。

假设传感节点N1被捕获，则需要通过密钥k4和k5取消并更新节点N1拥有的密钥k1，k2，k3删除节点N1：

（1）Ek4（S′，Ek1（k1′），Ek2（k2′），Ek3（k3′））

（2）Ek5（S′，Ek1（k1′），Ek2（k2′），Ek3（k3′））

其中Eki（x）表示数据x用密钥ki进行加密，密钥ki更新为ki′，si′ 为更新后的 会话密钥。

2 NDDK方案

本文提出的是基于邻居发现的EBS动态密钥管理方法，首先利用节点的一跳邻居节点发现过程在簇首中建立整个簇的拓扑结构模型，簇首根据整个簇的拓扑模型进行动态密钥管理。主要研究内容包括：网络初始化，EBS矩阵的生成，管理密钥的分配，节点添加和密钥更新等方面的内容。

2.1 网络初始化阶段

在网络部署前，每个节点预载入仅与基站共享的节点密钥KI，一个全网唯一的ID和一个统一的单向密钥生成函数F。节点部署后，开始进行网络初始化。本文假设网络在初始化阶段是安全，攻击者不能俘获并破解任何传感节点。具体步骤如下：

步骤1 网络部署之后，节点进行一跳邻居发现过程，节点u在一跳范围内广播邻居节点发现信息：

其中ADV－discovery为节点邻居发现消息标志。接收到NMu的节点v将节点u及其ID保存在自己的邻居列表ID－listv中。

步骤2 本文在分簇的基础上进行动态密钥的管理，以簇为单位进行动态密钥管理。分簇不是本文研究的重点，本文采用已有的分簇方式进行分簇［11］。

步骤3 分簇完成后，普通传感节点u将ID－listu发送至u所在簇的簇首CHi：

在簇首中形成整个簇的拓扑结构模型。

2.2 EBS矩阵的生成

网络初始化完成之后，为保证邻居节点分配的密钥组合汉明距离最小，本文采用节点分层算法决定普通传感节点SN的密钥组合即在簇首CH中形成EBS矩阵。我们采用无向图G（V，E）说明算法，如图1所示。V表示所有顶点的集合V＝ ｛A，B，C…，G｝。E表示所有边的集合，边的存在代表两个节点在彼此的通信范围内互为邻居节点。

图1 簇拓扑结构模型

（1）首先计算所有节点度数，选取度数最大的节点作为根节点，根节点的邻居节点处在第二层，依次类推。

（2）根据层数优先，同层节点中度数较大的节点优先分配密钥的准则，划分节点分配密钥的优先次序。如图1所示B，F处在同一层中，B的度数为4，E的度数为3，优先对B进行分配。

（3）根据簇内节点数量n选取合适的k和m的值，在k＋m值最小的前提下，保证k的值最小。

（4）根据节点分配次序，依次指定节点密钥组合，并保证邻居节点中分配的密钥组合汉明距离最小，在对节点分配密钥时只挑选未使用的密钥组合。本文选择EBS参数k＝2，m＝3对图1中节点进行密钥分配，生成EBS矩阵如表1所示。

表1 EBS（8，2，3）的密钥子集

2.3 管理密钥分配

EBS矩阵生成之后，簇首节点CH从邻居节点中选择密钥生成节点KGN，KGN的数量为t且t＞ （k＋m）／k，这样保证部分KGN的俘获不会导致全部管理密钥泄漏。首先，CH向基站申请用于分配管理密钥的种子seed，SEED是用于申请种子的标志，簇首利用seed生成分配密钥ks＝F（seed）［12］；然后，CH在簇内广播seed和利用ks加密的EBS矩阵，簇内节点SN收到消息后根据seed生成密钥ks同时解密得到EBS矩阵；其次，KGN生成同化多项式［10］密钥ka，并利用ks加密后发送给簇首，簇首在簇内逐个广播ka；最后，SN利用ks和EBS矩阵接收仅属于自己的k个密钥多项式。密钥多项式的分配过程描述见表2。

表2 密钥多项式分配过程

KGN生成的同化二元多项式［10］如式 （1）所示

其中l∈ ［1，2，…，k＋m］，对于分配了同一个同化多项式的一组节点可以形成相同的共享密钥。密钥分配完成之后，CH销毁其存储的全部管理密钥，SN销毁其存储的EBS矩阵。

2.4 节点添加

在网络的运行过程中，由于节点能量耗尽或者节点俘获被删除等原因，需要向网络中添加新的节点。新添加节点部署前预载入节点发现密钥ksg，同时基站BS向网络中所有的簇首发送新添加节点的ID和节点发现密钥ksg。以图2为例子说明节点u的添加过程：

（1）节点u部署后向其邻居节点广播邻居发现消息：

（2）收到邻居发现消息的传感节点v，将新加入的节点u及其ID添加在自己的邻居列表中，同时v向u发送回复消息，回复消息包括该节点的ID和其所在的簇的簇首ID：

（3）收到回复消息的后u形成节点邻居列表，向合适簇首CHi发送节点加入请求消息：

其中join为新节点加入请求标志。

（4）簇首CHi收到节点加入请求消息后，通过ksg和节点ID验证u身份。验证成功后为u分配与邻居节点汉明距离最小的管理密钥组合。节点添加成功后删除ksg：

图2 节点添加

2.5 密钥更新

为提高网络的安全性能，动态密钥管理系统需要周期性的进行密钥更新。本文假设网络为静态网络即节点在部署之后位置不发生变化。由于网络在运行过程中由于节点的删除和添加等原因，网络的拓扑结构可能会发生变化。本文以簇为单位进行的密钥管理，所以根据簇的拓扑结构是否发生变化将密钥更新分为两个不同的方案：

（1）簇的拓扑结构不发生变化：簇首向KGN发送密钥更新请求，KGN生成新的管理密钥多项式ka’并将ka’用ka加密得到E （ka’，ka），并进一步用ks加密得到E （E（ka’，ka），kS）发送给簇首，簇首使用ks解密，得到E（ka’，ka），同时在簇内广播 E （ka’，ka），普通传感节点收到后用ka解密的到新的管理密钥ka’，删除更新前的管理密钥ka。

（2）簇的拓扑结构发生变化：有于节点能量耗尽或节点被俘获等原因，网络中需要进行节点的删除和添加，此时簇的拓扑结构发生变化。簇首根据更新后的拓扑结构按照2.3所示方法重新进行管理密钥分配。

3 性能分析与比较

下面从网络安全性和节点开销等方面对本方案进行分析，并与SHELL方案进行对比，两种方案均为基于EBS的动态密钥管理方法。SHELL［8］方案中节点分为普通传感节点SN和网关节点Gateway，对Gateway需要更大的存储空间和计算能力，同时要求节点具有定位能力。本文提出的方案，所有的节点均为普通传感节点，且不需要节点具有定位能力，对节点要求更低，适用性更强。

3.1 节点抗俘获性能

本文与SHELL均以簇为单位进行动态密钥管理，我们以簇为单位分析节点的抗俘获攻击的性能。假设网络中存在n个节点，每个节点分配k个同化二元多项式，更新密钥的数量为m，被捕获节点的数量为Nc，同化多项式Fi被捕获的概率为pFi，如式 （2）所示

由式 （2）可知t＋1阶同化二元多项式是t－安全的。当俘获不超过t个拥有同一个多项式的节点时，该多项式是不可破解的。本文使用同化多项式密钥作为节点的管理密钥，节点的抗俘获性能优于SHELL。

3.2 节点抵抗共谋攻击的性能

在密钥分配的过程中，本文提出的方案利用节点数量信息和簇拓扑结构信息对簇内传感节点进行管理密钥的分配。在节点添加和密钥更新的过程，簇首节点根据簇拓扑结构的变化，为节点动态分配管理密钥，保证网络抵抗共谋攻击的性能。为了验证本文提出方案对共谋攻击的抵抗性能，我们针对不同的网络规模进行仿真实验，并将本文方法与SHELL［8］进行比较。如图3所示。

图3 共谋链长度比较

图3描述了不同网络规模下整个网络被捕获时SHELL和NKKD最短共谋链的长度的比较。由于本文采用节点分层算法进行密钥分配，由图3可知在不同网络规模下，NKKD的最短共谋链的长度较SHELL更长，NKKD对抵抗共谋攻击的性能更好。随着网络规模的增大，最短共谋链的长度总体上不断增大。

3.3 节点开销

（1）生成EBS矩阵的计算开销

在SHELL和本文的方案中，簇首首先根据网络的拓扑结构，决定簇内节点的密钥组合即形成EBS矩阵。在SHELL采用启发式算法［8］进行密钥分配，节点在分配密钥过程中需要不断的同上层节点交换密钥组合，以保证与相邻节点的密钥组合的汉明距离最小。本文采用节点分层算法，首先划分节点分配密钥的顺序，不需要密钥分配节点与上层节点反复交换密钥，密钥分配算法的时间复杂度大大降低。若网络中存在n个节点，本文算法时间复杂度为O （n），SHELL采用启发式算法时间复杂度为O（n2），如表3所示。

（2）SN存储开销

本文使用的管理密钥为多项式密钥，节点存储k个t阶多项式密钥需要的密钥存储空间为k（t＋1），SHELL中节点使用普通密钥需要存储空间为k。虽然多项式密钥的使用增加了节点的存储空间，但是节点抵抗俘获攻击的能力大大增强，提高了网络的安全性能。

（3）密钥分配通信开销

SHELL在密钥分配过程中簇首为簇内节点逐个分配K个管理密钥，每个密钥分配消息中包含k个管理密钥，则需要的总的通信开销为nk，n为簇内SN节点的数量。本方案中CH逐个广播管理密钥，每个管理密钥仅需广播一次，需要的总的通信开销仅为k＋m，远远小于nk。本方案中通信开销显著降低。

表3 节点开销

4 结束语

本文针对传感器网络容易受到节点俘获攻击和共谋攻击的问题，提出了基于邻居发现的动态密钥管理方案。该方案中的节点均为普通传感节点，节点通过邻居发现过程而不需要通过节点定位，形成网络的拓扑结构，降低了对节点的要求和功耗；通过节点分层生成EBS矩阵进行管理密钥分配，降低簇首节点的计算开销和分配开销，同时增强了网络抵抗共谋攻击的性能；在节点添加和密钥更新的过程，簇首根据节点的邻居列表动态更新网络的拓扑结构，从而使节点获得最优的密钥组合，提高网络抵抗共谋攻击的性能。分析结果表明，与相关文献比较，该方案增强了网络安全性能，整体上降低了网络开销。

［1］Aronti P，Pillai P，Chook V.WIRELESS sensor networks：A survey on the state of the art and the 802.15.4and ZigBee standards［D］.Pisa：Department of Computer Science，University of Pisa，2006.

［2］CHEN X，Makki K，Yen K，et al.Sensor network security：A survey［J］.IEEE Communications Survey ＆ Tutorials，2009，11 （2）：52－73.

［3］PEI Qingqi，SHEN Yulong，MA Jianfeng.Survey of wireless sensor networks security techniques［J］.Journal on Communications，2007，28 （8）：113－122（in Chinese）.［裴庆祺，沈玉龙，马建峰.无线传感器安全技术综述 ［J］.通信学报，2007，28 （8）：113－122.］

［4］SU Zhong，LIN Chuang，REN Fujun，et al.Key management schemes and protocols for wireless sensor networks［J］.Journal of Software，2007，18 （5）：1218－1231（in Chinese）.［苏忠，林闯，任富君，等.无线传感器网络密钥管理的方案和协议 ［J］.软件学报，2007，18 （5）：1218－1231.］

［5］WEN Tao，ZHANG Yong，GUO Quan，et al.Dynamic group key management scheme for homogeneous wireless sensor networks［J］.Journal on Communications，2012，33 （6）：164－173（in Chinese）.［温涛，张永，郭权，等.WSN中同构模型下动态组密钥管理方案 ［J］.通信学报，2012，33 （6）：164－173.］

［6］Mohamum M，Eltoweissy M.A study of static versus dynamic keying schemes in sensor networks ［C］／／Montreal：Proc of 2nd ACM International Workshop on Performance Evaluation of Wireless Ad Hoc，Sensor Networks，and Ubiquitous Networks，2005：122－129.

［7］Mohanum M，Elwoweissy M，Mukkamala R.Dynamic key management in sensor networks ［J］.IEEE Communications Magazine，2006，44 （4）：122－130.

［8］Younis M，Ghummank，Elwoeissy M.Location－aware combinatorial key management scheme for clustered sensor networks［J］.IEEE Transaction on Parallel and Distributed System，2006，17 （8）：865－882.

［9］KONG Fanrui，LI chunwen，DING Qingqing.Dynamic key management scheme for wireless sensor networks based on polynomial keys ［J］.Journal of Tsinghua University，2009，49（10）：21－24（in Chinese）.［孔繁瑞，李春文，丁青青.基于多项式的传感器网络动态密钥管理方法 ［J］.清华大学学报，2009，49 （10）：21－24.］

［10］Eltowieissy M，Heydari H，Morales L，et al.Combinatorial optimization of key management in group communications［J］.Journal of Network and Systems Management，2004，12 （1）：33－50.

［11］YU Lei，LI Jianzhong，LUO Jizhou.Distributed secure clustering protocol in wireless sensor networks［J］.Journal of Software，2009，20 （10）：2705－2720（in Chinese）.［余磊，李建中，骆吉洲.一种无线传感器网络分布式安全成簇协议 ［J］.软件学报，2009，20 （10）：2705－2720.］

［12］ZHONG Jin，LUO Jun，JIANG Rong，et al.Routing based two－level key management scheme in wireless sensor networks［J］.Application Research of Computers，2011，28 （2）：738－741（in Chinese）.［钟进，罗军，江荣，等.无线传感器网络基于路由的两级密钥管理方案 ［J］.计算机应用研究，2011，28（2）：738－741.］