无线传感器网络中一种密钥预分发算法设计

邵明杰

【摘要】 在无线传感器网络（WSNs）中，密钥预分发算法十分重要。现有的密钥预分发算法通常是在连通性、抵抗节点捕获的安全弹性和存储、通信和计算过载之间进行交换，很难使各项指标都很理想。本文在对WSNs典型密钥预分发算法的特点进行分析的基础上，利用部署知识和密钥空间的极限安全特性于组合模型中的方法，提出了一种新的适合于WSNs密钥预分发算法。分析该算法在占用较小的内存、局部高概率连通的情况下，能使网络得到完美的安全弹性。

【关键词】 无线传感器网络 密钥预分发 组合设计 部署知识

一、引言

典型的无线传感器网络由成千上万个非常小的传感器节点组成，这些节点由电池供能、装载完整的传感器系统、有一定的数据处理能力和很小的内存空间、并且能进行短距离无线通信。将这样一些节点随机部署在一个特定目标区域，它们就形成了一个无人照顾的无线网络。

二、无线传感器网络密钥预分发算法的主要评价指标

（1）局部连通性：指部署后位置相互邻近节点间的连通性能。（2）抵抗节点捕获的安全弹性：即当网络中一部分节点被对手破坏后，剩余安全节点间能建立安全链路的概率。当任意多个节点被破坏后，网络中安全节点间任意通信链路仍然安全，则称安全弹性是完美的。（3）计算和通信过载：即节点间为了建立密钥链路所需的计算和通信所用能量。（4）内存过载：即密钥预分发算法所占用的节点内存。（5）全局连通性：即根据算法形成的密钥共享图中，孤立节点占整个网络的比率。（6）可验证性：通常传感器节点无人照顾且缺乏保护，节点完全不可信任，这要求节点间通信应该具有验证性能。

三、部署知识模型

假设传感器节点被部署后将是静止或在很有限的区域内运动。同时设节点被部署在一个 2维区域内，这里称为目标区域。仅在相互信号半径内，传感器节点间能通信。定义传感器节点的信号半径为dr且为分析方便令dr=。定义节点在目标区域内期望的位置为期望位置且用坐标（Lx，Ly）表示，节点在目标区域内最终的实际位置为居住位置且用（x，y）表示，部署传感器节点的位置为部署位置。部署模型描述如下：

（1）设一个目标区域被分为m个尺寸相等的六边形（也可以选用三角形等其它形状的图形来覆盖这个区域）。相对于三角形和正方形六边形能更有效的覆盖目标区域，同时，相对于12边形等分析起来更简便。（2）N个传感器节点被分到ω个群中，每个群有n=个节点且被部署到同一个细胞（cell）中，即群i是被部署到第i个cell中，其中i∈[1，m]、θ为与某个cell相邻的cell数量。（3）一个cell中心是一个部署点。由于是随机部署，每个节点的居住位置与期望位置通常会有一定误差，并且当这个误差在一定范围内时，利用部署知识能非常有效地改善密钥预分发性能。设这个部署误差最大值为e，某节点u的期望位置为（Lx，Ly）。节点u概率密度函数能表示为：

（1）

在这里‖·‖表示期望位置与居住位置间的距离。

四、算法实现及性能分析

基于上一部分的部署模型，提出一种新的密钥预分发算法，它有效地获得了组合方法在密钥预分发设计中能提高连通性的优势、利用部署知识能有效提高密钥预分发性能的优势及Blom设计具有的极限安全特性这一非常好的性质。因此，称这一方法为利用部署知识的多密钥空间组合设计。在这个设计中，服务器根据每个cell的位置信息为cell内的节点分发密钥且这些密钥来自于服务器产生的密钥空间池中。根据上面的部署模型，给每个cell分一个对应的主密钥空间及其ID。例如，对于第i个cell内的节点，我们用其对应的主密钥空间为它及与这个cell相邻的（θ-1）个cell内的节点分发密钥。为使密钥预分发设计具有完美的安全弹性，我们要求主cell及与之相邻（θ-1）个cell内总节点数小于等于（t+1）。基于这种部署模型，利用组合理论对其进行分析，有下列结论。

通过融合多密钥空间设计与部署知识于确定性密钥预分发设计中，可以建立一个v=ω、b=、r=t+1且k=θ的（v，b，r，k）-BIBD构造。

在这个部署模型中，共有N=b传感器节点即每个节点作为一个区组。为了相邻节点间能够安全通信，需要建立成对密钥。在部署前，每个节点存储它所在cell对应的主密钥空间及相邻cell对应的主密钥空间中的密钥到它ROM中。根据第2节部署模型，节点需要存储θ个密钥空间中的密钥。因此，有k=θ；由于若两个区组中有来自同一个密钥空间的密钥，则它们就可以利用这个公共的密钥空间建立直接密钥。在部署模型中，一个密钥空间被用于（t+1）个节点，因此，从区组图的角度考虑，可以认为每个密钥空间被使用了（t+1）次，即有r=t+1；同时，由于每个cell中有n=个节点，且整个网络中共有ω个cell。因此，区组总数为b=且v=ω。

4.1 抵抗节点捕获的安全弹性

由于当每个密钥空间最多被t+1个节点使用时，无论整个网络中有多少个节点被扑获，都不会影响网络中其它剩余安全节点间的通信。因此，被提出的设计将具有完美的安全弹性。然而，这又产生了新的问题：网络密度很大程度上被降低。为了解决这个问题，这里提出了进行部署时，要根据密度要求来确定cell的尺寸。以 节点为例（这里设dr=300m）：当每个cell的面积为400m2时，每个cell内有α个传感器节点。则有每个密钥空间被θα个节点使用；当每个cell的面积为40m2时，每个cell内有β个节点。则有每个密钥空间被θβ个节点使用。由于网络密度D=在这里（m+1）为某个节点通信范围内邻节点的数量，因此，两种情况下的网络密度分别为：D1= D2=。因此，网络密度与每个cell内节点的数量成正比的关系。这样，我们就可以根据网络密度、每个cell内节点的数量和每个密钥空间被最多t+1个节点使用的关系来确定适合的cell尺寸。从而使整个网络就具有了完美的安全弹性。

4.2 计算连通性

在无线传感器网络中对于连通性，通常由局部连通性和全局连通性两个方面进行分析。在这个被提出的设计中，局部连通性是指：在目标区域内居住位置相邻的节点间能够建立直接密钥的概率。全局连通性是指：整个网络中任意节点间能建立直接密钥的概率。由于，在无线传感器网络中，更重要的是局部连通性。因此，对全局连通性进行分析时，为了简化这一过程，常假设此时节点的信号半径为无限大。

4.2.1 局部连通性

首先，假设节点Na的居住位置和期望位置分别用a和表示a。考虑被分别部署在目标区域的两个节点Na和Nb，设它们的期望位置已知，则它们居住位置相邻的概率为：

（2）

下面定义两个事件E和F：（1）E：能与第i个cell中的某节点Na直接通信的节点数μ。（2）F：在与Na居住位置相邻节点中，能与节点Na建立直接密钥的节点数μ'。这样，网络的局部连通性可以表示为：p=。为了计算F和E，需要设第i个cell用Ci表示，并且节点在期望位置的主cell内是随机部署的，则在cell内任意节点期望位置的概率密度函数为或0（在这里R为正六边形的边长）。用Si表示与主cell是i的节点共享至少一个公共密钥的一组节点所在的主cell。根据上一部分的部署模型，可知每个Si中有19个cell。这样，可计算得：

（3）

（4）

（5）

（6）

从而，可以得到局部连通性的概率表达式。

4.2.2 全局直接连通性

为了减少传感器节点通信过载，设计仅考虑网络中任意节点间直接连通的情况，称全局直接连通性。在（v，b，r，k）-BIBD构造的密钥预分发模型中，网络的全局直接连通概率可以用pglobal=来表示。则根据定理1，可得在这个设计中网络的全局连通概率为：

pglobal= （7）

在这里，由于部署模型采用的是六边形的蜂窝结构，因此，为了简化分析，令θ=7。同时，设t=39，则根据定理1存在的充要条件，可知需满足ω≥241，将其代入上式有pglobal≈20%。由此可知，所形成的区组图中任意两区组连通的概率约为20%。因此若选择更适合的部署策略，仅需用6-8个cell就可以代替算法中要求的至少241个cell。但这时密钥空间的极限安全性能又无法保证网络完美的安全弹性。因此，根据实际工作要求的主要性能，对不同的部署策略需要更深入研究。

五、结语

在这篇文章中，为了有效地改善无线传感器网络中密钥预分发设计的性能，我们利用部署知识、组合理论和密钥空间极限特性的优势，提出了一种新的算法。分析表明，当网络中的传感器节点能以一个确定的概率被部署到期望位置或部署后能够发现这个节点的位置时，这个设计在占用很少的内存和通信、计算过载的情况下，为网络提供了一个完美的抵抗节点捕获安全弹性，并且同时具有较好的连通性能。

参 考 文 献

[1] J.Zheng， P.Lorenz， P.Dini. Wireless Sensor Networking[J].IEEE Network， 2006（3）：2-3

[2] Fredric Newberg.wireless sensor networks design and implementation[D].Los Angeles： University of California， Los Angeles， 2002

[3] Fei Hu，Jason Tillet，Jim Ziobro，N.K.Sharma. Secure Wireless Sensor Networks：Problems and Solutions[J].Journal on Systemics， Cybernetics and Informatics.2004，11（9）：419-439.

[4] 孙永进，孙雨耕，陈宝江，房朝晖. 无线传感器网络1点和2点连通可靠性研究[J]. 传感技术学报. 2004，（3）：3792385.