基于正六边形部署的WSN密钥预分配方案*

余旺科，王淑华

(绍兴文理学院数理信息学院，浙江绍兴312000)

无线传感器网络WSN(Wireless Sensor Networks)一直被认为具有广泛的应用前景，能够部署在当前典型网络所不能及的环境，为当前的众多领域，如污染监测、环境和交通流量监控等提供良好的解决方案。针对无线传感器网络能量、计算能力、存储空间及带宽等局限性问题，为了延长网络的生存时间，充分利用和优化网络资源显得尤为重要[1－4]。有效的密钥管理能为其他安全机制或服务提供最基本的技术支持[5－9]。由于无线传感器网络在各方面的局限性，传统网络的密钥管理方案不适合在无线传感器网络中的应用。

现有的基于分组的密钥管理方案还有些不足，如Kong等人提出的一种基于六边形部署的双变量多项式密钥管理方案[10]，在该方案中当q=3时，网络被俘获的链路比为0．362，而且其网络覆盖率只有0．598。在2012年严雪莉等人提出的基于六边形部署的密钥管理方案中[11]，当m=100和m=200时，其网络局部连通率最高分别为0．676和0．937，而全局连通率可能会更低一些。在代航阳等人提出的基于六边形部署方案中[12]，网络连通率为0．86。其他有些方案建立共享密钥的不一致性也很严重，虽然一个组之间的共享密钥建立概率很高，但整个无线传感器网络的共享密钥建立概率不是很理想，所以降低了整个无线传感器网络的连通性[13]。本文在随机密钥预分配方案基础上，提出一种新的利用正六边形部署信息的密钥预分配方案:HBKPS(Hexagon－Based Key Pre－distribution Scheme)。这种新的基于区域划分的无线传感器网络随机密钥预分配方案，通过将无线传感器网络分为若干个子区域，每个子区域相当于一个分组，然后对各个分组分别部署密钥。采用正六边形分别对网络进行分区，不但在覆盖全网的同时分区之间没有重叠区域，而且每个分区相邻的分区数仅为6个。

1 HBKPS区域划分

无线传感器网络节点可以随机抛撒到目标区域。这种随机抛撒传感器节点的方式在实际中合理可行，例如可通过直升机到达部署区域进行抛撒，被抛撒的节点随机分布在整个无线传感器网络区域中。本文提出的HBKPS方案将整个无线传感器网络区域分为若干个正六边形子区域，每个子区域相当于一个组，然后对各个组分别部署密钥。整个无线传感器网络被划分为若干个正六边形区域后的模型如图1所示。

图1 HBKPS方案的网络模型

选择正六边形部署无线传感器网络有一大特点:正六边形只有6个相邻组，而正方形和三角形相邻的组个数分别为8个和12个[14]。在每个组中的传感器节点都是随机分布的，每个组的传感器节点部署模型如图2所示。其中圆形部分表示每个节点直接通信的覆盖范围。

图2 每个子区域的部署模型

HBKPS方案采用基本的密钥预分配模型:一个大的密钥池在部署之前被创建，密钥池里包含了所有密钥及密钥所对应的ID，传感器节点中的所有密钥都是从这个大的密钥池中随机选取，以使该方案更具有通用性。在密钥预分配前，先把整个无线传感器网络划分为若干个正六边形区域的分组，并把这些分组划分为3个分区域，如图1所示。

分区域划分具体步骤如下:首先，在无线传感器网络中选择一个最靠近无线传感器网络中心位置的分组作为密钥分配的起始分组，如图1中所示的分组(2，1)。接着选择中心分组(2，1)的6个相邻分组中的3个，这3个分组必须满足其互不相邻，如图1 中所示的分组(1，1)、分组(3，1)和分组(2，2)。然后，分别沿着分组(2，1)的中心到分组(1，1)、分组(3，1)和分组(2，2)的中心方向继续选择相应的组，如图1中背景为非白色的分组。最终，所有这些背景为非白色的分组就把整个无线传感器网络划分为3个相同结构的分区域。

2 HBKPS方案

在密钥分配前，先在每个分组的中心位置分别放置一个临时传感器节点，称之为源传感器节点。HBKPS方案中的符号含义如表1所示。

在HBKPS方案中，假设对任意的整数m、n、h和D均能保证下列式子成立:

源节点的密钥分配步骤如下:

(1)首先，从密钥池中随机选取n个密钥分配给位于中心分组(2，1)的源节点，并将其作为初始化源节点。接着，位于分组(1，1)、分组(3，1)和分组(2，2)的源节点分别从分组(2，1)的源节点的密钥中随机选取h个密钥，其余的n－h个密钥从密钥池中随机选取。

(2)分组(2，1)的中心到分组(1，1)、分组(3，1)和分组(2，2)的中心方向上的源节点分配方案如下:未分配分组的源节点从其相邻的已分配分组的源节点的密钥中随机选取h个密钥，其余的n－h个密钥从密钥池中随机选取。

(3)3个分区域的密钥分配方案如下(以右下方那个分区域为例，其它两个分区域类似分配即可):如图1所示，分组(3，2)的相邻分组中已经有3个分组(分组(2，1)、分组(3，1)和分组(2，2))的源节点已被分配了密钥。其中分组(3，1)的源节点和分组(2，2)的源节点的密钥都是从分组(2，1)的源节点的密钥中分配而来，所以，称分组(2，1)的源节点为密钥的主要来源节点，其它两个分组的源节点为密钥的次要来源节点。

(4)如图3所示，中间的实线边框长方形分组表示分组(2，1)的源节点(密钥主要来源节点)的密钥分布，其他两个长方形分别表示分组(3，1)和分组(2，2)的源节点的密钥分布。分组(3，2)的源节点的密钥由图3中所示的C区的所有2h－n个密钥和A、B、D、E区中的各一半密钥构成，即:

图3 已分配的3个源节点的密钥分布图

(5)接着，分配该分区域中的其他分组。如:分组(3，3)由分组(2，2)、分组(2，3)和分组(3，2)共同配置;分组(4，1)由分组(3，1)、分组(3，2)和分组(4，0)共同配置等，直到所有分组分配完成。

在所有分组的源节点都分配完成后再分配每个分组中的非源节点。每个分组中的非源节点的密钥分配如下:从该分组中的源节点的密钥中随机选取m个密钥。当所有节点的密钥分配完成后，取出无线传感器网络中所有的源节点。因为这些占少数比例的源节点集中了绝大部分的分配密钥，即使被俘获较少的源节点也能对整个无线传感器网络造成较大的危害。

当有两个节点想要进行通信时，首先交换各自拥有的密钥ID来发现其互相之间共享的密钥。任何两个拥有共享密钥的节点都可以随机选择其中一个共享的密钥来进行安全通信。

3 密钥共享分析

如图1中所示的分组(3，4)与分组(3，3)、分组(3，2)和分组(2，1)的部署距离 D 分别为 1、2、3，即分组(3，4)中的所有传感器节点与分组(2，1)中的所有传感器节点的部署距离均为3。下面首先分析任意两个分组的源节点之间不同的密钥总数情况:

(1)以分组(3，1)和分组(2，1)为例:

在分组(3，1)中的h个密钥是从分组(2，1)中选取的，剩下的n－h个密钥才是从S中选取的，所以分组(3，1)和分组(2，1)中不同的密钥总数最多为:

(2)以分组(3，2)和分组(2，1)为例:

如图3中所示，分组(3，2)和分组(2，1)的共享密钥是由图3中C区的所有2h－n个密钥和B、D区中的各一半密钥构成。所以分组(3，2)和分组(2，1)中共享的密钥总数为:

即分组(3，2)和分组(2，1)中不同的密钥总数最多为:

(3)以分组(3，2)和分组(2，2)为例:

如图3中所示，分组(3，2)和分组(2，2)的共享密钥是由图3中C区的所有2h－n个密钥和D、E区中的各一半密钥构成。所以分组(3，2)和分组(2，2)中共享的密钥总数为:

即分组(3，2)和分组(2，2)中不同的密钥总数最多为:

其他分组之间不同的密钥总数类似以上分析。

由于每个分组中的非源节点从该分组中的源节点的密钥中随机选取m个密钥，所以分组(3，2)和分组(2，2)中的非源节点之间共享的密钥至少为:

其他分组的非源节点之间共享密钥类似以上分析，可得HBKPS方案中任意两个传感器节点共享密钥数至少为:

其中，当这两个传感器节点位于同一分组时D=0。

由式(4)可以得出:

所以，无线传感器网络中任意两个传感器节点都至少共享一个密钥，无论传感器节点移动到哪个区域，该节点都能和新的邻居节点直接进行安全通信。当有两个传感器节点想要进行通信时，首先交换各自拥有的密钥ID来发现其互相之间共享的密钥。任何两个拥有共享密钥的传感器节点都可以随机选择其中一个共享的密钥对来进行安全通信。在HBKPS方案中，当传感器节点部署的网络面积很大时，并不需要保证整个网络中任何节点都至少共享一个密钥，因为当传感器节点的通信范围远小于网络部署面积的最大宽度时，如果还要保证距离最远两端的传感器节点至少共享一个密钥就不切合实际。所以在本文方案中，只需要保证某个节点与其通信范围附近的节点之间至少共享一个密钥，这样，在连通概率方面就和保证整个网络的任何两个节点都至少共享一个密钥相当，因为网络连通概率可以表述为在相互通信范围内的邻居节点之间的连通概率。我们将在下节的性能分析中具体讨论部署距离和HBKPS方案中其它参数之间的关系。

4 HBKPS性能分析

本节从节点存储需求和安全性对HBKPS方案进行评估。存储需求:因为传感器节点存储空间有限，所以在保证网络到达一定连通概率时，节点应存储较少的密钥。安全性:在攻击者俘获节点时，能最大限度的保证其他未被俘获节点之间的通信安全。

4．1 存储需求

在HBKPS中，本节将分析保证整个网络连通概率为1的较理想情况下的节点最少密钥数量，这也能相应的反映其它情况下的存储需求性能。使用如下配置:

①主密钥池S大小为，|S|=100 000。

②无线传感器网络的节点总数为10 000。

③部署网络的总面积为1 000 m×1 000 m。

那么整个网络被划分的正六边形区域总数为:

如果把整个网络边长单位由米转换为正六边形区域的个数，并且根据对角线上两端的正六边形区域的部署距离最大，得出HBKPS方案中的最大部署距离Dmax为:

由式(1)～式(3)、式(9)和式(10)可得出HBKPS方案中的m与L的关系如图4所示。

图4 当D=Dmax时m与L的关系图

由图4中所示可以看出，当无线传感器网络中L=50 m时，在HBKPS方案中每个节点存储的密钥数量只有20～35，就可以保证无线传感器网络中的全局连通概率为1，也就是无线传感器网络中任何两个传感器节点都至少拥有一个共同的密钥。所以，HBKPS方案具有较好的存储需求性能。

4．2 安全性

假设攻击者俘获无线传感器网络中的节点时，都能获取这些节点中的所有密钥信息。在HBKPS方案中用被俘获的网络通信链路比例来衡量无线传感器网络的安全性。当无线传感器网络中有x个节点被俘获时，其被俘获的网络通信链路的比例由式(11)定义[15]:

在式(11)中，|S|是整个密钥池的大小，即10 000。而在HBKPS方案中，为了更好的反应被俘获网络通信链路的比例，把|S|定义为已经分配了的密钥总数，而不包括没有被分配的密钥数量，这样能更真实的反应其安全性。定义如下:

由图1部署的网络模型可以看出，在HBKPS方案中，相互通信范围内节点之间的最大部署距离D为:

由式(13)可得出，在HBKPS方案取不同r(m)和L(m)值时的部署距离D如表2所示。

从表2可以看出，在HBKPS方案中，部署距离D小于3就可以基本满足网络的连通概率需求。假设L=20，r=20，由表2可以得出在 HBKPS方案中节点不移动的情况下D=1。

表2 取不同r和L时得出的D

当n=100时，由式(1)～式(3)和式(9)可以得出在HBKPS方案中满足网络的连通概率需求时的最小h如表3所示。

表3 取不同m时得出的最小h

在HBKPS方案中，假设L=20，r=20，由表3也可以得出在节点不移动的情况下D=1，在移动距离小于2L的情况下D=3。

由HBKPS密钥预分配过程可以得出，在HBKPS方案中已经被分配的密钥总数为图1中非白色背景颜色的区域，因为其他区域的密钥都是从这些区域中进行分配的。

除了区域(2，1)中的全部n个密钥是从主密钥池中选取的，其他非白色背景颜色区域的n个密钥中只有n－h个密钥是从主密钥池中选取，剩下的h个密钥都是从已分配的区域中选取的。由图1可以得出非白色背景颜色的区域总数约为:

所以当m=100，L=20时，在HBKPS方案中已经被分配的密钥总数|S|为:

在HBKPS方案中，由于每个分组中的非源节点从该分组中的源节点的密钥中随机选取m个密钥，所以当被俘获节点部署距离为D时，式(12)中被俘获节点的平均密钥数约为:

最后，由式(12)可得，在HBKPS方案中，当有x个节点被俘获时，其被俘获的网络通信链路的比例为:

由式(14)和式(15)，n=100，L=20，D=1 得:

在HBKPS方案的安全性能仿真将采用表3中的参数，由式(16)得出被俘获的网络通信链路的比例如图5所示。

图5 HBKPS方案的安全性

从图5中所示可以看出，在HBKPS方案中，当x=20，m=0．9n 和 x=20，m=0．7n 时，网络中被俘获网络通信链路的比例仅为0．056 4和0．021 1。所以在HBKPS方案中，网络被俘获网络通信链路的比例较理想。如果网络中传感器之间的共同密钥越多，则该网络的连通概率就越高，所以该网络的安全性也将更低，因为被俘获的密钥中有更多的密钥还在未被俘获传感器之间应用。因此，通过以上HBKPS方案的性能分析可知，HBKPS方案较适合应用在安全要求不是太高，而对连通概率要求很高的网络环境中。

5 结论

本文提出的基于部署信息的无线传感器网络随机密钥预分配方案:基于正六边形区域划分的随机密钥预分配方案HBKPS。其核心思想是利用部署信息来进行区域划分，使其更适应于无线传感器网络。数据分析和仿真结果表明，HBKPS方案中无论无线传感器网络部署的传感器数量有多大，面积有多广，只要某些参数满足一定的要求，所有节点之间直接共享一个密钥的概率均为1，从而降低了在其他方案中因密钥协商带来的通信负载。即使在保证比其他方案更高连通概率的情况下，也只需更小的存储空间。综上所述，HBKPS方案具有很高的连通概率，能有效减小节点的存储空间，并具有较好的扩展性。不过针对HBKPS方案，还有些问题需要继续深入研究，如怎样优化部署信息中参数才能同时具有更好的网络连通性和安全性等。

[1]Lynch K M，Schwartz I B，Yang P，et al．Decentralized Environmental Modeling by Mobile Sensor Networks[J]．IEEE Transactions on Robotics，2008，24(3):710－724．

[2]Bertsekas D P，Tsitsiklis J N．Comments of Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules[J]．IEEE Transactions on Automatic Control，2007，52(5):968－969．

[3]祁荣宾，李思瑾，马天义，等．基于迭代的无线传感器网络三维定位算法[J]．传感技术学报，2012，25(5):645－650．

[4]Lu K，Qian Y，Guizani M，et al．A Framework for a Distributed Key Management Scheme in Heterogeneous Wireless Sensor Networks[J]．IEEE Transactions on Wireless Communications，2008，7(2):639－647．

[5]Song C，Cao J N，Liu M，et al．Maximizing Network Lifetime Based on Transmission Range Adjustment in Wireless Sensor Networks[J]．Computer Communications，2009，32(11):1316－1325．

[6]Ye Z，Abouzeid A A，Ai J．Optimal Stochastic Policies for Distributed Data Aggregation in Wireless Sensor Networks[J]．IEEE/ACM Transactions on Networking，2009，17(5):1494－1507．

[7]Lee J，Stinson D R．On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks Using Combinatorial Designs[J]．ACM Transactions on Information and System Security，2008，11(2):1－35．

[8]Ozdemir S．Functional Reputation Based Reliable Data Aggregation and Transmission for Wireless Sensor Networks[J]．Computer ＆Communications，2008，31(17):3941－3953．

[9]潘巨龙，高建桥，徐展翼，等．一种基于确定性理论的无线传感器网络信任机制 nTRUST[J]．传感技术学报，2012，25(2):240－245．

[10]Kong B B，Chen H Y，Tang X H，et al．Key Pre－Distribution Schemes for Large－Scale Wireless Sensor Networks Using Hexagon Partition[C]//IEEE Wireless Communications and Networking Conference，WCNC，2010:1－5．

[11]严雪莉，叶晓慧．一种基于六边形部署模型的面向传感器网络的随机密钥预分配方案[J]．计算机应用研究，2012，29(4):1457－1461．

[12]代航阳，徐红兵．基于六边形网格部署模型的传感器网络密钥管理[J]．电子测量与仪器学报，2008，22(5):48－52．

[13]Zhang J，Varadharajan V．Wireless Sensor Network Key Management Survey and Taxonomy[J]．Journal of Network and Computer Applications，2010，33(2):63－75．

[14]Yu Z，Guan Y．A Key Management Scheme Using Deployment Knowledge for Wireless Sensor Networks[J]．IEEE Transactions on Parallel and Distributed Systems，2008，19(10):1413－1420．

[15]Du W，Deng J，Han Y S，et al．A Key Management Scheme for Wireless Sensor Networks Using Deployment Knowledge[C]//Pro of the IEEE Infocom．Piscataway:IEEE Press，2004:586－597．