余旺科 马文平

西安电子科技大学计算机网络和信息安全教育部重点实验室 陕西 710071

0 引言

无线传感器网络(Wireless Sensor Networks,WSN)被部署在无人触及甚至敌方控制的环境时，节点将面临着各种各样的攻击。因此，如何保证WSN安全是WSN研究领域里的一项极其重要内容。其中，最基本的一项研究内容是密钥管理，主要目的是为传感器节点建立共享密钥，从而为网络提供安全的通信链路。有效的密钥管理能为其他安全机制或服务提供最基本的技术支持。由于无线传感器网络在计算能力、存储空间、节点能量以及网络带宽上的局限性，传统的网络密钥协商方案由于某些方面不适合WSN而不能得到真正的应用。

WSN密钥协议的研究中，存在多种关于WSN的密钥预分配方案，如信任服务器方案、公开密钥方案和密钥预分配方案。密钥预分配方案是通过预分配方案来分配密钥，密钥的分配是在节点部署之前就已完成．该方案由于在WSN建立之前就对节点分配了密钥，解决了WSN建立后分配密钥所带来的能量消耗问题，成为目前的研究热点，但在该方案中如何高效地为每个节点对分配密钥一直是个难解的问题。

1 相关研究

随机预分配密钥方法的操作方法简单描述如下：随机从密钥空间选择一个密钥池，每个传感器节点在部署之前都从该密钥池获取一些密钥，于是任意两个节点就有可能从各自所获得的密钥中找出相同的密钥来进行通信，但这种方法存在的一个问题是，任何两个节点之间存在相同的通信密钥的概率是较低且安全性也得不到保证。通过依赖部署信息把节点分成若干个组，这样在同一个组的节点之间建立共享密钥的概率相当高，这种利用部署信息的随机密钥预分配方案有效的提高了建立共享密钥的概率以及增强了网络的抗毁性。由于攻击者需要俘获很多节点才能破坏整个WSN，是目前一种比较好的WSN密钥管理方案，受到了较大的关注。另外，还有其它很多密钥管理方案可以参考有关WSN安全问题的综述。

本文提出了一种新的WSN随机密钥预分配方案，通过将目标区域分为若干个六边形子区域，然后对各个子区域分别部署密钥。节点仅需预分配数量较少的密钥信息，就能够以较高的概率建立共享密钥，即使存在大量的受损节点仍能保持较强的网络抗毁性。

2 部署模型

无线传感器网络节点可以随机抛撒到目标区域。这种随机抛撒传感器节点的方式在实际中合理可行，例如可通过直升机到达部署区域进行抛撒，被抛撒的节点随机分布在整个WSN区域中。本文提出的方案将整个WSN区域分为若干个正六边形子区域，然后对各个子区域分别部署密钥。选择正六边形部署WSN有两大优点：其一，只有少数图形(正方形、三角形和正六边形)才能很好的连续覆盖整个WSN区域，而正六边形比正方形和三角形更接近圆形；其二，正六边形只有6个相邻子区域，而正方形和三角形的相邻子区域个数分别为8个和12个。整个WSN区域被划分为若干个正六边形子区域后的模型如图1所示。在每个子区域中选择一个最接近中心点的节点作为核心节点，子区域中的其它节点为非核心节点。

图1 网络部署模型

3 密钥预分配方案

本文提出的基于部署信息的WSN随机密钥预分配方案采用基本的密钥预分配模型：一个大的密钥池在部署之前被创建，密钥池里包含了所有密钥及其所对应的ID，传感器节点中的所有密钥都是从这个大的密钥池中随机选取，以使该方案更具有通用性。

3.1 区域划分

在密钥预分配前，先把整个WSN划分为若干个正六边形子区域并把这些正六边形子区域划分为3个分区域，如图1所示。分区域划分具体步骤如下：首先，在WSN中选择一个最靠近WSN中心位置的子区域作为密钥分配的起始子区域，如图1中所示的子区域(2,1)。接着选择子区域(2,1)的 6个相邻子区域中的3个，这3个子区域必须满足其互不相邻，如图 1中所示的子区域(1,1)、子区域(3,1)和子区域(2,2)。然后，分别沿着子区域(2,1)的中心到子区域(1,1)、子区域(3,1)和子区域(2,2)的中心方向继续选择相应的子区域，如图1中背景为非纯白色的子区域。最终，所有这些背景为非纯白色的子区域就把整个WSN划分为3个相同结构的分区域。

3.2 密钥预分配方案

在本文提出的随机密钥预分配方案中，必须满足两个前提条件：其中，m为每个节点存储的密钥个数，h为每个相邻核心节点共享的密钥个数，r为两个核心节点最大的距离，d为正六边形的边长。在密钥分配前，先在每个子区域中分别选择一个最靠近中心位置的节点作为其核心点，核心节点的密钥分配步骤如下：

（1）首先，从密钥池中随机选取m个密钥分配给位于中心区域(2,1)的核心节点，并将其作为初始化节点。接着，位于区域(1,1)、区域(3,1)和区域(2,2)的核心节点分别从区域(2,1)的核心节点的密钥中选择h个密钥，其余的m-h个密钥从密钥池中随机选取。

（2）区域(2,1)的中心到区域(1,1)、区域(3,1)和区域(2,2)的中心方向上的核心节点分配方案如下：未分配区域的核心节点从其相邻的已分配区域的核心节点的密钥中随机选取 h个密钥, 其余的m-h个密钥从密钥池中随机选取。

（3）3个分区域的密钥分配方案如下(以右下方那个分区域为例，其它两个分区域类似分配即可)：如图1所示，区域(3,2)的相邻区域中已经有3个区域(区域(2,1)、区域(3,1)和区域(2,2))的核心节点已被分配了密钥。其中区域(3,1)的核心节点和区域(2,2)的核心节点的密钥都是从区域(2,1)的核心节点的密钥中分配而来，所以，称区域(2,1)的核心节点为密钥的主要来源节点，其它两个区域的核心节点为密钥的次要来源节点。区域(2,1)的核心节点为区域(3,2)核心节点密钥的主要来源节点，区域(3,1)和区域(2,2)的核心节点为区域(3,2)核心节点密钥的次要来源节点。区域(3,2)的核心节点的密钥由主要密钥来源节点中随机选取的h个密钥和两个次要密钥来源节点分别随机选取的(m-h)/2个密钥构成。接着，分配该分区域中的其它子区域。如：区域(3,3)由区域(2,2)、区域(2,3)和区域(3,2)共同配置；区域(4,1)由区域(3,1)、区域(3,2)和区域(4,0)共同配置等，直到所有子区域全部配置完成。

每个子区域中的非核心节点的密钥分配如下：先从该子区域中的核心节点的密钥中随机选取h个密钥；剩下的m-h个密钥从密钥池中随机选取。当所有节点的密钥分配完成后，每个节点都会广播其所拥有的密钥 ID来发现其互相之间共享的密钥。任何两个拥有共享密钥的节点都可以用其共享的密钥来进行安全通信。

3.3 共享密钥分析

任何两个子区域的部署距离用n表示，如图1中所示的区域(3,4)与区域(3,3)、 区域(3,2)和区域(2,1)的部署距离n分别为1、2、3。密钥预分配完成后的WSN节点的密钥共享情况如下：

（1）同一子区域中的核心节点与非核心节点之间共享密钥数为h；

（2）同一子区域中的两个非核心节点之间共享密钥数为2h-m；

（3）任何两个核心节点之间共享密钥数为n*h-(n-1)*m；

（4）不同子区域中的核心节点与非核心节点之间共享密钥数为(n+1)*h-n*m；

（5）不同子区域中的非核心节点之间共享密钥数为(n+2)*h-(n+1)*m。

4 方案分析

无线传感器网络的密钥管理方案必须具有连通性和安全性。下面就对本文提出方案中的这两个最重要的性能进行分析。

4.1 连通性

连通性就是一个网络中任何两个节点至少共享一个密钥的概率。从共享密钥分析小节可以看出，在本文提出的方案中任何两个节点至少共享一个密钥的概率为 1，明显高于其它方案。

4.2 安全性

假设攻击者俘获WSN中的节点时，都将获取这些节点中的所有密钥信息。在本文中用被俘的通信链路比例来衡量WSN的安全性。当x个节点被俘获时，网络被俘通信链路的比例可用下式定义：

设WSN中部署10000个传感器节点，在本方案中网络部署区域共划分为500个子区域(共有500个核心节点)，每个传感器节点存储的密钥数为80，则每两个节点至少共享一个密钥的概率为1。当有40个节点被俘时，本方案被俘的通信链路比例只有0.27。另外，由于在本文提出的方案中传感器是随机抛撒在WSN中的，所以每个传感器的具体位置都是随机的，这种部署位置的灵活性有效的阻止了基于具体位置信息的攻击，提高了网络的安全性。在大部分现有方案中WSN的全局连通性都只有0.6左右，而在本文方案中全局和局部连通性均为 1，所以适当减少相邻核心节点的共享密钥数，也能保证较高的网络安全连通性。这样，在被俘相同数量的节点时，被俘的通信链路比例将有所下降，有效的提高网络的抗毁性。

5 结束语

本文提出了一种新的基于部署信息的无线传感器网络随机密钥预分配方案，其核心思想是利用正六边形部署信息来分配密钥，使其更适应于WSN。数据分析表明，在本方案中无论WSN部署的传感器数量有多大，面积有多广，只要某些参数满足一定的要求，所有节点之间直接共享一个密钥的概率均为 1，从而降低了在其它方案中因密钥协商带来的通信负载。即使在保证比其它方案更高连通性的情况下，也只需更小的存储空间。综上所述，本文提出的方案具有很高的连通性，能有效减小节点的存储空间，并具有良好的扩展性和网络抗毁性。

[1] Liu D,Ning P,Du W.Group-based key predistribution for wireless sensor networks[J].ACM Trans. Sensor Netw.2008.

[2] Lee J C, Wong K H,Cao J,et al.Key management issues in wireless sensor networks： Current proposals and future developments[J].IEEE Wireless Commun.2007.

[3] Younis M F,Ghumman K, Eltoweissy M. Location-aware combinatorial key management scheme for clustered sensor networks[J].IEEE Trans. Parallel Distrib. Syst.2006.

[4] Du W,Deng J,Han Y S,et al.A pairwise key predistribution scheme for wireless sensor networks[J].ACM Transactions on information and system security.2005.

[5] Liu D,Ning P.Improving key pre-distribution with deployment knowledge in static sensor networks[J].ACM Trans.Sensor Netw.2005.

[6] Lu K,Qian Y,Guizani M,et al.A framework for a distributed key management scheme in heterogeneous wireless sensor networks[J].IEEE Trans. Wireless Commun.2008.

[7] Du X,Guizani M,Xiao Y,et al.Secure and efficient time synchronization in heterogeneous sensor networks[J].IEEE Trans.Veh.Technol.2008.