基于分层的传感器网络密钥预分配方案*

周波清， 李素君， 羊四清

(1.中南大学 信息科学与工程学院，湖南 长沙 410083；2.湖南人文科技学院 信息科学与工程系，湖南 娄底 417000)

0 引 言

在军事和商业的应用中，传感器网络的安全问题是必须解决的核心问题之一[1]。近年来，相关学者提出了许多密钥管理方案[2～12]。

Du W等人第一次将部署知识模型化[8]，基于这个部署模型提出了一个密钥预分配方案。Zhou B等人将部署知识和密钥链结合起来[9]，提高了文献[8]所提方案的性能。Yu Z等人提出了一个新密钥预分配方案[10],此方案将部署区域划分成六边形的单元格，与基于二维单元格的方案[8]相比，其性能有所提高。Fanian A等人将六边形的部署知识进行一步划分，并使用主从密钥机制为节点建立共享密钥[11]，此方案具有完美地对抗节点俘获的弹性性能，但是存储开销随着六边形区域的增大而增加，新部署的节点很难与已部署在网络中的节点建立共享密钥。

与不利用部署知识的密钥管理方案[2～7]相比，利用部署知识的密钥管理方案[8～11]具有如下优点：1)存储开销减少；2)局部连通率和抗节点俘获的弹性性能显著提高。但是这些方案没有考虑部署误差，随着节点的实际位置与其期望位置之间误差的增加，其局部连通率将显著下降，最终导致全局部连通率的下降。

为了减轻因部署误差而引起的方案性能的显著下降，本文提出了一种基于分层的密钥预分配方案(KPS-L)，并在此基础上提出了一种密钥预分配方案，此方案将整个部署区域划分成六边形的单元格，每个单元格都是基本单元，每个基本单元都有联系单元，联系单元根据离基本单元的远近分层。基本单元使用独立的基本密钥池，然后基于分层和基本密钥池创建基本单元的联系密钥池。部署点位于基本单元格的节点不仅要从本单元格的基本密钥池中选取密钥，还需从本单元的联系密钥池中选取一些密钥，与文献[10]相比，其局部连通率和全局连通率都有显著提高。

1 对密钥建立方案KPS-L

1.1 部署模型

与文献[10]一样，KPS-L方案使用基于群的部署模型，具体描述如下：

1)整个网络被划分成正六边形的网格，如图1所示；

2)每个网格有一个部署点，在图1中，部署点位于单元格的中心；

3)部署点相同的节点组织成群，群内节点在网络中的实际位置服从以部署点为中心的二维正态分布。

图1 区域划分图(其中“●”代表部署点)

1.2 密钥管理模型

每个网格都是基本单元，基本单元的邻居单元根据离基本单元的远近分层。

图1例举了以(3,2)为基本单元的2层联系单元。其中深色的6个单元为(3,2)的第1层联系单元；浅色的12个单元为(3,2)的第2层联系单元。

定义2 基本密钥池:系统为基本单元格(r,c)产生大小为m的密钥池BK(r,c)，网络中的基本密钥池都相互独立。

1.3 密钥预分配

部署点位于单元(r,c)的群中的节点预分配如下密钥信息：

1)从BK(r,c)中选取t0个密钥,这部分密钥称为基本密钥。

1.4 共享密钥建立阶段

节点部署好后，进入共享密钥建立阶段。下面以节点a,b为例来讲解对密钥的建立过程。

如果节点a和b的部署点相同，且它们之间存在如下y(y≤t0)个共同密钥k1,…,ky，则它们之间的共享密钥为kab=H(k1⨁…⨁ky,IDa⨁IDb)，其中,⨁为异或操作。

共享密钥建立成功之后，来自基本密钥池的密钥经过Hash变换后的才存储到节点中，即对于任何基本密钥k，共享密钥建立成功之后，节点a存储如下密钥：k′=H(k,IDa)。

1.5 路径密钥建立阶段

本方案路径密钥可以使用文献[8～11]中的方法建立，在此就不再详细地介绍。

2 性能分析与模拟

定义4 相邻节点：如果节点a和b都在对方的通信范围内，则称a和b为相邻节点。

定义5 局部连通率(local connectivity)：网络中任意两相邻节点能够建立共享密钥的概率。

定义6 全局连通率(global connectivity)：密钥连通分量中的节点数与物理连通分量中的节点数之比。密钥连通子图是指图中的节点通过相邻节点建立的共享密钥相互连通；物理连通分量是指图中的节点通过相邻节点相互连通。

定义7 抗毁性(resilience)：没有被俘获的相邻节点之间建立的对密钥被破译的概率(在本文的模拟过程中，没有考虑路径密钥被破译的概率)。

2.1 节点能够建立对密钥的概率

节点a和b能够建立对密钥的概率与它们的部署位置有关。

如果a和b的部署点相同，则它们之间能够建立共享密钥的概率为

(1)

如果a和b的部署点不同，但两节点的部署点都位于对方的第i(1≤i≤L)层联系单元内，则它们之间能够建立共享密钥的概率为

(2)

如果a和b的部署点不同，且两节点的部署点都超出了对方的联系单元，则它们之间能够建立共享密钥的概率为0。

2.2 性能模拟

在本文的模拟中，KPS-L方案主要参数设置如下：

1)部署区域为700 m×700 m；

2)部署区域被划分成正六边形的网格，正六形的边长为50 m，部署点位于正六边形的中心；

3)节点被划分成群，每群有40个节点，节点在网络中的实际位置服从以部署点为中心，以σ为方差的二维正态分布；

4)最大的联系层数L为2；

5)每个独立密钥池的大小m为600；

6)t0,t1和t2的值分别为40,60和60。

KPS-L方案的网络模型、密钥池的大小、每个节点预分配的密钥数都与YG方案[10]相同。为了确保比较的公平性，在共享密钥建立成功后，YG方案也对预分配的密钥进行了Hash处理。

从图2中可以得出：两方案的局部连通率随着二维正态分布标准方差σ的增加而下降。但是YG方案下降得过快,如当σ=110时，YG方案的局部连通率仅为52%，下降了31 %;而KPS-L方案的局部连通率为62%，仅下降了20 %,与YG方案相比，其局部连通率提高了18 %。

图2 局部连通率对比示意图

在YG方案中，部署点位于基本单元中的节点只能与部署点位于它的邻居单元格中的节点建立共享密钥。随着部署误差的增加，不仅导致局部连通率的显著下降，而且也导致全局连通率的下降。如图3所示，当σ=110时，YG方案的全局连通率为97.3%，也就是说，部署到网络的1000个节点中，有23个节点由于不能与它周围的邻居节点建立共享密钥而被浪费。但是，在相同的情况下，KPS-L方案仅浪费了4个节点。

图3 全局连通率对比示意图

图4中的参数cc表示敌手在共享密钥建立阶段俘获的节点数。从图4可以得出，KPS-L方案和YG方案都具有很好的弹性性能。如，当cc=20时，KPS-L方案和YG方案两方案中节点间建立的共享密钥被破译的概率分别约为0.7%和0.3%。Gu W等人在文献[12]中提出了一个新的性能参数：抗毁局部连通率PRC=(1-PR)×PC，其中PR,PC分别表示抗毁性、局部连通率,此参数更具实际意义。一个方案如果能够达到很高的局部连通率，但是节点间建立的安全链路基本被破译，则这个方案也就失效了。当σ=110，cc=20时，KPS-L方案和YG方案的抗毁局部连通率分别为61.8%和52.6%。

3 结束语

针对利用部署知识的方案因部署误差而引起的方案性能的显著下降的问题，提出了一种基于分层的密钥管理方案。与基本单元只与相邻单元相联系的方案(YG方案)相比，其局部连通率和全局部连通率都显著提高。

图4 抗毁性对比示意图

参考文献:

[1] Perrig A,Szewczyk R,Tygar J D,et al.SPINS:Security protocols for sensor networks[J].Wireless Networks,2002,8:521-534.

[2] Eschenauer L,Gligor V D.A key-management scheme for distri-buted sensor networks[C]∥Proc ACM CCS,Washington,DC,USA,2002:41-47.

[3] Chan H,Perrig A,Song D.Random key predistribution schemes for sensor networks[C]∥Proc IEEE S & P,Berkeley,USA,2003.

[4] Das A K.An efficient random key distribution scheme for large-scale distributed sensor networks[J].Security and Comm Networks,2011,4(2):162-180.

[5] 袁 珽,马建庆,钟亦平,等.基于时间部署的无线传感器网络密钥管理方案[J].软件学报,2010,21(3):516-527.

[6] Bechkit W.New key management schemes for resource constrain-ed wireless sensor networks[C]∥Proc IEEE WoWMoM,Lucca,Italy,2011.

[7] 李素君,周波清,羊四清.传感器网络高效密钥建立方案[J].计算机工程与应用,2013,49(2):134-136.

[8] Du W,Deng J,Han Y S,et al.A key management scheme for wireless sensor networks using deployment knowledge[J].IEEE Trans on Dependable and Secure Computing,2006,3(1):62-77.

[9] Zhou B,Li S,Li Q,et al.An efficient and scalable pairwise key pre-distribution scheme for sensor networks using deployment knowledge[J].Computer Communications,2009,32(1):124-133.

[10] Yu Z,Guan Y.A key management scheme using deployment knowledge for wireless sensor networks[J].IEEE Trans on Para-llel and Distributed Systems,2008,19(10):1411-1425.

[11] Fanian A,Berenjkoub M,Saidi H,et al.A high performance and intrinsically secure key establishment protocol for wireless sensor networks[J].Computer Networks,2011,55:1849-1863.

[12] Gu W,Chellappan S,Bai X,et al.Scaling laws of key predistribution protocols in wireless sensor networks[J].IEEE Trans on Information Forensics and Security,2011,6(4):1370-1382.