基于分簇结构的非对称随机密钥预分配方案

王 瑾, 王 斌, 丁 杰, 高 锐

(扬州大学信息工程学院, 江苏 扬州 225127)

0 引言

随着无线通信和传感器技术的飞速发展,无线传感器网络(wireless sensor networks, WSN)广泛应用于军事、环境和医疗等领域[1]．无线传感器网络主要由大量体积小且具有无线通信和监测能力的传感器节点组成, 这些节点被稠密地部署在监测区域[2]．WSN的部署环境通常较为复杂,面对各种安全威胁时传感器节点容易受到攻击,故安全问题的解决至关重要[3]．由于传感器节点的资源有限, 通常只能采取基于对称密钥的管理方案, 因此为传感器网络分发密钥的方案设计备受关注．Eschenauer和Gligor[4]最早提出了随机密钥预分配的EG方案, 该方案中每个传感器节点从大的密钥池中随机选取等长的密钥环,通过共享密钥建立节点间的安全连接．当给定密钥池大小时,EG方案欲使节点间能以一定的概率建立安全连接, 节点所持有的密钥环必须足够大, 从而导致额外的内存开销增大．随后,众多学者围绕EG方案展开了大量研究．Zhao[5]讨论了节点捕获条件下的随机密钥预分配方案的安全性质．Yagan等[6-7]讨论了信道不可靠条件下随机密钥预分配方案的渐近连通性,并提出一种节点随机配对密钥分配方案, 即若干个随机节点共享密钥,保持簇头的存储开销为一常量,仍维持渐近的连通性．Omar[8],Yagan[9-10]等讨论了无线传感器网络中密钥分配技术的各种应用及相关的安全性质．EG方案及上述随机密钥预分配方案本质上是面向平面结构的网络设计的,而实际的WSN网络多采用层次结构进行管理,如LEACH协议[11],将网络分为多个簇,每个簇由簇头节点和簇内节点组成．本文拟设计一种基于分簇的非对称随机密钥预分配方案(cluster based asymmetric random key distribution,CARKD),采取非对称模式为分簇的网络结构分配对称密钥．

1 本文方案及其安全连通度

假设有n个传感器节点随机分布在感知区域内, 现采用分簇的方式进行管理, 其中簇的规模为k, 则簇的数量为L=[n/k]．该L个簇头之间采用完全密钥共享的模式, 即每个簇头保存L-1个密钥分别用于执行与其他簇头的安全通信．

设置簇内主密钥池S=∪1≤i≤LSi,Si∩Sj=∅,i≠j, 不同子密钥池互不相交．第i个簇Ci的每个子密钥池Si的大小均为X=|S|/L, 簇Ci采用非对称的随机密钥预分配方案, 即簇Ci的每个成员从Si中随机抽取q个密钥, 其簇头节点从Si中随机抽取cq(c≥2)个密钥, 参数c代表簇头节点密钥池相对成员节点密钥池大小的放大系数．

1.1 簇间安全连通度

簇Ci内的普通节点xi和簇Cj内的普通节点xj之间可以通过各自簇头节点间的安全转发建立一条长度为3的安全路径．xi和xj能够建立该安全路径的概率为

(1)

普通节点与簇头建立安全链路的概率则为pij1/2．

1.2 簇内安全连通度

簇Ci内的普通节点xi和xj之间可以建立如下安全路径:

1) 当簇Ci内部两个节点至少共享一个密钥时可以建立一个安全链接, 其概率为

(2)

2) 允许xi和xj通过簇头建立长度为2的安全路径, 该事件的概率为

(3)

则xi和xj能够建立安全路径的概率为

pij=pij1+(1-pij1)pij2．

(4)

由此可见, 非对称密钥分配方式与分簇结构的结合使得簇头可以帮助普通节点提高建立安全连接的概率．

1.3 密钥捕获攻击

(5)

2 方案性能分析

2.1 安全连通度比较

设置实际参数: WSN中传感器节点个数n=100, 簇的规模k=10, 簇的数量L=10．

在EG方案中2个节点建立安全连接的概率为

p=1-((|S|-q)!)2/(|S|!(|S|-2q)!).

(6)

该方案中当节点存储的密钥数相同时,密钥池越小,节点之间的安全连通度越高．

图1给出了当|S|=2 000时EG方案和本文方案在c=2,3时的节点间安全连通度结果．由图1可知: 当c=2,3时,在节点存储密钥数相同的情况下, CARKD方案与基本密钥预分配方案相比具有更好的节点安全连通度, 且c值越大, 即簇Ci的簇头从密钥池Si中随机抽取的密钥数越多, 节点的连通度越高．

图2给出了当|S|=2 000时EG方案和本文方案中簇内一对节点安全连通度比较结果．由图2可知,在普通节点存储密钥数相同的情况下, 本文方案中簇内一对节点具有更高的节点安全连通度．

图1 CARKD方案与EG方案的安全连通度比较Fig.1 The security connectivity comparison between CARKD and EG solutions

图2 CARKD方案与EG方案簇内一对节点的安全连通度Fig.2 Security connectivity comparison for a pair of nodes within a cluster between EG scheme and a single cluster of CARKD scheme

2.2 密钥存储开销比较

在EG方案中, 单个传感器节点的存储开销为q, 网络中总的密钥存储开销为nq．取总密钥池|S|=5 000, 传感器节点选取的密钥环大小为100时, 该方案的安全连通度约为87.01%, 此时总的密钥存储开销为10 000．

本文方案中, 簇内普通节点的存储开销为q, 簇头节点的存储开销为cq+L-1, 网络中总的密钥存储开销为L(cq+L-1)+(n-L)q．令簇的大小k=10, 则簇的数量L=n/k=10．当c=2时, 为了达到相同的连通度, 簇内普通节点选取的密钥数仅为25, 簇头节点选取的密钥数为50, 此时位于不同簇的节点间的安全连通度达87.05%, CARKD方案总的密钥存储开销为2 750; 当c=3时, 为了达到相同的连通度, 簇内普通节点选取的密钥数仅为21,簇头节点选取的密钥数为63,此时密钥连通度达89.20%, CARKD方案总的密钥存储开销为2 520．

经对比可知, 在达到相同连通度的情况下,本文方案中的节点可以选取更小的密钥环,并且能够进一步减少节点的存储开销．

当各个簇的大小不一致时, 本文方案中的分析方法仍适用,但需要在公式中换入实际的簇的大小．

3 结语

本文基于分簇结构提出了一种非对称模式的随机密钥预分配方案, 本方案在簇头之间采用完全密钥共享技术,在簇内普通节点和簇头之间采用非对称的随机密钥预分配技术．本文方案在达到与EG方案相同的安全连通度时,可以节省节点的密钥存储开销．但是当网络节点规模增大时,簇的规模固定,簇头数量会上升,在簇头之间采用完全密钥共享技术会增大簇头的存储开销,故下一步将考虑在簇头之间采用节点随机配对密钥分配方案设计以及节点的移动对网络连通度的影响．