基于分簇的有效无线传感器网络密钥管理方案

李明，熊盛武，郑晓亮

（武汉理工大学湖北武汉430070）

近年来，随着微机电系统、无线通信、信息网络与集成电路等技术的迅速发展，新兴的无线传感器网络应运而生。无线传感器网络是由大量分布式传感节点组成的面向任务型自组织网络。由于拥有广泛的应用前景，无线传感器网络得到了迅速发展，广泛应用于国防军事、工业控制、环境监测、交通管理等领域。虽然无线传感器网络有许多优点，但由于很多传感器网络有可能被部署在敌方区域，而且由于它的无线通信特性，很容易遭到攻击，如何加强它的抗攻击能力，提高安全性就显得极为重要[1]。一般来说，无线传感器节点拥有有限的资源，比如计算能力、存储空间和能量等，这导致了非对称密码算法难以在其上被使用，所以无线传感器网络普遍使用基于对称密码的密钥管理算法来保证其安全。通过无线传感器网络的特性以及可能面临的攻击，综合已有的多种算法，在分簇结构无线传感器网络基础上提出一种新的密钥管理方案，并给出了这种方案的性能分析与仿真结果，结果显示提高了算法的安全性能。

1 分簇无线传感器网络拓扑结构

分簇无线传感器网络[2]是现在使用比较广泛的网络结构，分簇无线传感器网络拓扑结构如图1所示。

图1 分簇结构的无线传感器网络拓扑结构Fig.1Clustering structure of wireless sensor network topology

将基于该结构进行密钥管理。该网络结构是由基站、簇头与簇内节点3种类型的节点构成。其中基站的主要功能是数据汇总，对网络中的传感器节点发送命令，基站具有无限能量、高计算能力以及充足的存储空间。簇头节点主要是将本簇内成员收集到的信息进行简单的数据融合并发送到基站，同时下达基站对本簇成员的命令，簇头节点是具有特殊功能的传感器节点，其能量、计算能力和存储空间都很有限。簇内节点负责感知周围环境，将采集到的数据传送到簇头节点。

2 基于随机概率的密钥预分配方案相关算法

2.1 KPD算法

KPD概率密钥共享算法[3]首先创建一个密钥池，密钥池里包含了密钥及其所对应的ID，然后为每个节点随机从密钥池里分配一定数目的密钥，当节点被投放后，每个节点会广播它所拥有的密钥ID来发现互相之间共享的密钥，任意两个共享密钥的节点都可以建立安全信道，任意节点通过安全信道来通信。由不同的密钥池大小P和每个节点所存储的密钥数k，这个算法能获得不同的连通性和抗攻击性。假设任意两个通信节点能建立安全链接的概率用p1表示，则p1=了提高算法的抗攻击性，可在此基础上约定共享q个密钥才能建立链接，即q-composite方案[4]。

2.2 基于分簇的算法

分簇算法是将传感器节点分成很多簇，簇内节点和簇间节点拥有不同的密钥共享概率。每个簇都拥有一个单独的密钥池，而且同一簇内的节点有很多概率被投放到同一片区域，这样每个节点有很大概率同相邻节点共享密钥。如果两个簇在投放点上是邻居的话，其相应的密钥池也被看成是相邻的，而且这些密钥池有如下性质[5]：

1）两个垂直或者平行的相邻密钥池共享α|Sc|个密钥，0≤α≤0.25。

2）两个斜相邻密钥池共享β|Sc|个密钥，0≤β≤0.25，4α+4β=1。3）两个不相邻的密钥池不共享密钥。

其中|Sc|为密钥池的大小，根据上述性质，在节点被投放后，每个节点有一定概率与同簇及相邻簇的节点共享密钥。

2.3 基于节点身份的密钥预分配方案

该方案[6]采用将节点身份与节点密钥、密钥标识3者相结合的思想完成密钥的预分配阶段和共享密钥发现阶段来提高抵抗被俘获攻击的能力。

假设网络中放置n个传感器节点，符号表示如下：id：每个传感器节点的唯一标识，其中id=1，2，…n；Sid：标识为id的传感器节点；

P：密钥分配中心产生的密钥池；

m：每个传感器节点的密钥个数，m个密钥构成节点的密钥环；

IDid：节点Sid所有m个密钥组成的标识集合；

1）密钥预分配阶段

①给每个传感器节点分配唯一的id，基站密钥中心生成大量的密钥组成一个密钥池P，每个接入网络的节点选出m个不同的密钥构成该节点的密钥环，并给出每个密钥的标识ID，i=1，2，…m；

②利用Hash函数建立节点身份与密钥标识之间的关系。对于节点Sid来说，输入节点id以及第i个密钥的标识IDiid，将Hash函数的输出作为第i个密钥新的标识，重复执行m次得到该节点一个新的密钥标识集合，通过这一步使得密钥中心产生的密钥标识与所配置的节点身份联系了起来，将重新得到的密钥和密钥标识集载入节点的内存中。

③按照与②中相同的规则，将基站的身份id与每个节点的密钥建立联系，得出基站与每个节点的共享密钥。到此，节点密钥的预分配已经完成，每个节点都分配了各自的密钥环，并且完成了节点与基站的密钥协商。

2）共享密钥发现阶段

每个传感器节点广播自己的身份标识id，对于节点i的其中一个邻居节点j，将j的身份作为输入求出该节点所对应的密钥标识集合IDj。然后将IDj与自己的密钥标识集合比较，如果存在相同的密钥标识，那么就以该密钥标识对应的密钥作为这两个节点之间的共享密钥。

3）路径密钥建立阶段

如果两个节点没有发现共享密钥，那么需要第3个节点作为中间节点，分别与第3个节点建立安全的链接协商路径密钥，这个过程与上述两个阶段相同。

3 基于分簇的有效密钥管理方案

在上述算法中，每个节点都存储一定数目的密钥，不同的节点可能会共享密钥，当节点被攻破时，它所存储的密钥将被泄露，所有其它使用这些密钥进行的通信都将不再安全。我们可以把一部分存储的密钥替换为包含某种中间信息的特殊信息，这些特殊信息也可以建立安全链接，而且泄露后不会对其它链接产生任何不利后果，这样可以有效地提高安全性，同时对连通度没有太大影响。

3.1 初始化阶段

首先为每个簇创建一个容量为P的密钥池，簇内每个节点从密钥池里随机选择m个密钥，并从这串密钥中随机选u个密钥，将它们替换成特殊信息。特殊信息EK可计算如下，EKk=k（H（K′⊕IDk））其中IDk为密钥k所对应的ID，⊕为二进制异或，H0为哈希操作，k0为使用密钥k进行的加密操作，节点会存储一个各自不同的密钥K′。由于K′对每个节点都不同，一旦某个节点被俘获，它所拥有的K′不能被用于解密其它节点间的加密通信。当节点把某个密钥k替换成对应的EK后，只需存储EK而不再存储对应的k以节省存储空间，因为算法中它不需要靠k来对EK进行解密操作，每个节点通过K′，ID和H求出EK解密后的值，即H（K′⊕IDk），这个值被作为建立通信的密钥，而另外一个节点只需拥有k，就可以通过解密EK来获取这个通信密钥，从而建立安全链接。

3.2 链接建立过程

在通信密钥建立过程中，每个节点都需要发现周围能和其密钥相匹配的节点。如果两个节点拥有相同的密钥，或者一个节点拥有密钥，另一个节点拥有由该密钥运算得到的EK，都可以认为两个节点拥有相匹配的密钥。在密钥发现过程中，每个节点将自己的密钥ID列表进行广播，这些ID对应自己拥有的密钥以及EK。当广播完成后，拥有匹配密钥的节点就可以建立安全链接了。这可以由2种方式达成，第1种，如果双方都拥有密钥k，他们可以使用k作为通信密钥来建立安全链接。第2种，如果一方拥有密钥k，另一方拥有对应的EK，那么它们也能建立安全链接，所使用的密钥双方可以按如下步骤计算，对于拥有EK的一方，它计算如下kreal=H（K′⊕IDk）。对于拥有k的一方，它首先接受另一方传输过来的EK，然后计算kreal=Dk（EKk），其中Dk（）为使用k来进行的解密操作。当双方都拥有了相同的密钥K′后，可以用它来加密通信。由于每个节点的K′都不一样，每个密钥的ID也不相同，所以每个K′只在两个节点之间共享，即使它被泄露了也不会影响其它节点间的通信。哈希函数H用于保护密钥信息，如果攻击者已经获取了密钥k，以及某个节点对应密钥k的EK，攻击者也无法解密EK来获取这个节点的K′信息，这样也就无法计算出这个节点跟另外节点通信所使用的kreal。

4 安全性能分析及仿真结果

4.1 安全性能判断标准[7]

1）连通性连通性代表网络安全连通的能力。即节点在可通讯的范围内，建立安全链接的概率。

2）抗攻击性抗攻击性指网络在某些节点被攻破的情况下仍能保持通信安全的能力。

4.2 安全性能分析

4.2.1 抗攻击性

当传感器网络节点选择替换特殊信息的u个密钥占节点密钥m的比例r不同时，将会产生不同的安全性。在算法中给定一个t，它能在网络部署之前计算出来，r的取值在t的两边可以采取两种不同的密钥串选择方法，来使安全性能得到最优化。如果P代表密钥的容量大小，m代表传感器节点能容纳的密钥数目，n代表无线传感器网络所有节点的数目，则m（1-r）n＜=p表示整个无线传感器网络中被直接存储的密钥数目小于密钥池大小。如果让每个节点都存储不一样的密钥，一旦这些节点被攻破，它们所泄露的密钥对其它节点的链接不会造成任何威胁，这样整个网络的抗攻击性一直会保持最大值1。当r等于t时上述不等式取等在算法中，一个节点会存储直接密钥以及另一些密钥的间接信息，数目分别是m（1-r）以及mr。如果它被攻破了，m（1-r）个密钥将被泄露，而以及密钥间接信息对攻击者而言没有任何价值。当S个节点被攻破时仍能保持安全的概率可计算如由上述分析可知，当0≤r＜t时被攻破的节点数目越多那已建立的安全链接越不安全，当t≤r≤1时被攻破的节点不会对其它的链接产生影响，此时安全性能达到最大值。

4.2.2 连通性

如果P表示密钥池的大小，两个节点分别存储K1和K2个密钥，不存储特殊信息，那么这两个节点能建立安全链接点存储m（1-r）个密钥以及mr个间接密钥信息。首先，让A从容量为P的密钥池中随机选择m（1-r）个密钥，然后让B从剩下的密钥池中随机选择m（1-r）个密钥，最后让A，B分别从剩下密钥池中选择mr个密钥，并将他们替换成EK。当0≤r＜t时，A存储的m（1-r）个密钥与B的密钥及特殊信息没有匹配的概率为：p1=1-p（P，m，m（1-r）），A存储的特殊信息与B也无匹配的概率为：p2=1-p（P-m（1-r），mr，m（1-r）），这样A与B能建立安全链接的概率为pn=1-（1-p1）（1-p2）。当t≤r＜1时，任意两个节点都不会共享密钥，它们依靠间接密钥信息来建立链接，连通性为pn=1-（1-p（P，mr，m（1-r）））2。

4.2.3 r对性能的影响

r为可变参数，不同的值会导致不同的安全性。一般来说，给定P和m，增加r会导致更好的抗攻击性，但会降低连通性。由于连通性和抗攻击性在我们改变r后都会发生改变，因此可以通过固定某一个性能指标值来观察另一个性能指标的变化来判断综合性能的变化情况。此处固定m，通过调节P来使连通性保持同一个值。当0≤r＜t时，r与安全性能的关系如图2所示。其中连通性取值0.4，每个节点存储能力为200。从图2中我们知道与KPD算法相比，算法改善了安全性能。

图2 抗攻击性（0≤r＜t）Fig.2Performance of anti-attack（0≤r＜t）

当t≤r＜1时节点被攻破并不会泄露任何密钥，网络的抗攻击性能为最好。图3为与KPD算法的性能比较结果，其中网络规模分簇规模为500个节点，m为100，P为500，r为0.99，连通性为0.4。

图3 抗攻击性（t≤r＜1）Fig.3Performance of anti-attack（t≤r＜1）

由上述性能分析知，算法较其它算法在安全性上有所提高。不同的网络规模，密钥存储数，密钥池大小，r等参数均会导致不同的安全性能，可以根据实际情况选择适当的参数。

5 结束语

本文提出了一个基于分簇的有效无线传感器网络密钥管理方案。在不降低连通性的同时提高了安全性。在未来，可以探索采用怎样的分簇算法以及分簇的大小来提高性能，同时也可以研究11这个算法与其它算法一起使用的适用性，从而开发出一个基于这个算法的分组框架算法。

[1]王睿，韩芳溪，张晓丽．无线传感器网络密钥预分配与动态分配策略[J]．计算机工程与应用，2006，43（3）：120-122．WANG Rui，Han FANG-xi，ZHANG Xiao-li.Wireless sensor networkskeypre-distributionanddynamicallocation strategy[J].Computer Engineering and Application，2006，43（3）:120-122.

[2]章静，许力，黄榕宁.自组网中可信的分簇策略[C]//第二届可信计算与信息安全学术会议论文文集，2006：1-5．

[3]Echenauer L，Gligor V D.A key management scheme for distributed sensor network[C]//Proc of the 9th ACM Conf on Computer and Communications Security，New York：ACM Press，2002：41-47．

[4]Chan H，Perrig A，Song D．Random key pre-distribution schemesforsensornetworks[C]//IEEESymposiumon Research in Security and Privacy，2003:197-213.

[5]Du W，Deng J，Han Y S，et al．A key management scheme for wireless sensor networks using deployment knowledge[C]//Proceedings of IEEE INFOCOM，Piscataway：IEEE Press，2004：586-597．

[6]杨庚，王江涛，程宏兵，等．基于身份加密的无线传感器网络密钥分配方法[J]．电子学报，2007，35（1）：180-184．YANG Geng，WANG Jiang-tao，CHENG Hong-bing，et al．A key establish scheme for WSN based on IBE and Diffle-Hellman algorithms[J]．Acta Eleclronics Sinica，2007，35（1）:180-184．

[7]Xiao Y，Rayi V K，Sun B，et al．A survey of key management schemesinwirelesssensornetworks[J]．Computer Communications，2007，30（11-12）:2314-2341．