（信号与信息处理专业论文）一种改进的传感器网络分组密钥预分配方案.pdf

一种改进的传感器网络分组密钥预分配方案 摘要 无线传感器网络是由大量微型传感器节点构成的分布式网络系统。这种网络系统可 以广泛地应用于国防军事、国家安全、环境监测、交通管理、医疗卫生、制造业、反恐 抗灾等领域。有必要通过加密技术来保障传感器网络通信过程中传输数据的完整性和准 确性。然而，传统的相对于第三方服务器管理密钥方案和基于公钥的密钥管理方案都不 适合传感器网络，目前普遍采用的是适合传感器网络特点的密钥预分配管理方案。现有 的密钥预分配方案大多存在连通率低，抗捕获性差，不具备可扩展性等缺点，基于上述 原因，本文提出了一种改进的分组密钥预分配方案i g d k p s ( i m p r o v e dk e y p r e d i s t r i b u t i o n s c h e m eb a s e do n 矿o u pd e p l o y m e n t ) 。 首先，本文对典型随机型密钥预分配方案和基于区组设计的确定型密钥预分配方案 进行了研究和分析，并对同构分组密钥预分配方案的实现方式和性能进行了论述。 其次，基于分组密钥预分配思想，本文对t d ( k ，n ) 方案作出了适当的改进，设计出 一种可解析的t d ( k ，n ) 方案。引入b l u i l d o 二元对称多项式加密方案，并结合提出的可解 析t d ( k ，n ) 方案，进一步提出了一种改进的传感器网络分组密钥预分配方案。 最后，理论分析和仿真实验结果表明，与其他密钥预分配方案相比，本文提出的 i g d k p s 方案具有以下特点： ( 1 ) i g d k p s 方案具有较高的安全连通率。方案可以显著地提高传感器网络的整体连 通率，并使传感器网络组内节点连通率和组间节点的连通率达到一个平衡的状态。 ( 2 ) i g d k p s 方案具备良好的抗捕获性。即使在被捕获节点数量较多的情况下，i g d k p s 方案仍然能表现出比其他密钥预分配方案优秀的抗捕获性。( 3 ) i g d k p s 方案具有灵活 性。由于方案中的参数可变，因此i g d k p s 方案可以根据实际传感器节点的存储能力， 对网络的连通率和抗捕获性做出相应的调整。 关键词：传感器网络：密钥预分配；分组部署；组合设计：二元多项式 a b s t r a c t w i r e l e s ss e n s o rn e t 、v o r ki sad i s 仃i b u t e dn e t w o r ks y s t e mw 1 1 i c hi sc o m p o s e do fal a 玛e n u m b e ro ft i n vs e n s o rn o d e s t h i sn e 俩o r ks y s t e mc a l lb e 晰d e l yu s e di nn a t i o n a ld e f e n s e ， n a t i o n a ls e c u r i 饥e n v i r o i l m e n t a lm o i l i t o r i n g ，删j f i cm a i l a g e m e n t ，h e a l 廿lc a r e ，m a n u f a c t u r i n g ， a n t i t e 玎o r i s ma n do 也e rd i s a s t e ra r e a s i t sn e c e s s a 巧t oa d o p te n c r y p t i o nt e c h n o l o g y t oe n s u r e d a t ai n t e 酣t y 缸1 da c c u r a c y h o w e v e r ，m a r l y 舰d i t i o n a lk e ym a l l a g e m e n ts c h e m e sa r en o t s u i t a b l ef o rs e n s o rn e t w o r k s ，s u c ha s 吐屺t l l i r d - p a n ys e r v e rk e ym a l l a g e m e n ta i l d l ep u b l i c k e y _ b a s e dk e ym a i l a g e m e n ts c h e m e n o w a i 【a y s ，k e yp r e d i s t r i b u t i o ns c h e m e s a r ew i d e l yu s e d i i ls e n s o rn e t w o r k s m o s to ft 1 1 ee x i s 血gk e yp r e d i s 仃i b u _ t i o ns c h e m e sh a v e 廿l es h o i r t c o m i l l g s s u c ha sl o wc o m e c t i v i 吼p o o rr e s i s t a l l c ea i l ds c a l a b i l i 够f o rm ea b o v er e a s o n s ，恤sp 印e r p r o p o s e s a n i m p r o v e d铲o u p k e yp r e - d i 嘶b u t i o n s c h e m e i g d k p s ( i m p r o v e d k e y p r e d i s t r i b u t i o ns c h e m e b a s e do ng r o u pd e p l o y m e n t ) f i r s t l y ：t h em d o mk e yp r e - d i s t r i b u t i o ns c h e m e a n dt h ed e t e m i l l i s t i ck e yp r e 。d i s t r i b u t i o n s c h e m eb a s e do nt h eb l o c kd e s i g i la r er e s e a r c h e da i l da n a l y z e d r n l e nw ed i s c u s s t 1 1 e i m p l e m e n t a t i o na n dm ep e o m l a n c eo f t h eh o m o g e n e o u sg r o u pk e yp r e - d i s t r i b u t i o ns c h e m e s e c o n d l y ：b a s e do nt h et 1 1 i m d n go f 铲o u p - d 印1 0 y m e n tk e yp r e - d i s t r i b u t i o n ，w e m a k e i m p r o v e m e n t st ot 1 1 et d ( k ，n ) s c h e m e ，a n dd e s i g na r e s o l v e dt d ( k ，n ) s c h e m e t h e nw ep u ui n t 1 1 eb l u n d os c h e m e ， t 1 1 i s p 印e r 缸曲e rp r o p s e s a n i m p r o v e d s e n s o rn e t w o r kk e y p r e d i s t r i b u t i o ns c h e m eb a s e do n 伊吼l p - d e p l o y m e mb yc o m b i i l i n gm eb 1 u n d os c h e m ea n d d e s i g l l e d ) ，n ) s c h e m e a tl a s t ，m e o r e t i c a la m l y s i sa 1 1 ds i i n u l a t i o nr e s u l t ss h o w 廿1 a t ：c 印a r e dw 池。此rs c h e m e s ， m ep r o p o s e di g d k p ss c h e m el l a st 1 1 ef o l l o 、i i l gc h a m c t e r i s t i c s ： ( 1 ) t h ei g d k p ss c h e m eh a s am g h e rs e c u r ec o n n e c t i v i 够r a t e t h es c h e m ec a n s i g i l i f i c a n t l yi m p r o v et 1 1 eo v e r a uc o r m e c t i v i 够i ns e n s o rn e t w o r k s ，m a k em ei n 。g r o u pn o d e s c o i l n e c t i v 时a n dc r o s s 一掣o u pn o d e s c o i l i l e c t i v 时a c l l i e v eab a l a l l c e ds t a t er a t ei n 也es e n s o r n e t w o r k s ( 2 ) 1 ki g d k p ss c h e m eh a sag o o dr e s i s t a n c e e 沁e ni nt l l ec a s et h a tal a 培en u m b e r o fn o d e sa r ec a p t u r e d ，m ei g d k p ss c h e m ec a i ls 伽s h o w 恤o u t s 切n d i n gr e s i s 锄c e c o m p a r e dt oo m e rs h c e m e s ( 3 ) t h ei g d k p ss c h e m eh a sal l i g hn e x i b i l i t y s i n c et h es c h e m e s p a r 锄e t e ri sv 撕a b l e ，m ei g d k p ss c h e m ec a i la d j u s tt h ec o n n e c t i 、，i 够a j l dr e s i l i e n c eo ft h e n e 附o r kb a s e do nm ea c t u a ls t o m g ec a p a c i t yo fs e n s o rn o d e s k e yw o r d s ： s e n s o rn e t w o r k s ：k e y p r e d i s t r i b u t i o n ；g m u pd e p i o y 瑚e 1 1 t ；c o m b i n a t o 一翻 d e s i g n ：b i v a 靠a t ep o l y n o m i a l 第1 章绪论 第1 章绪论 1 1 研究背景 传感器节点是通过电池供电来测量某些物理量的设备，传感器节点具备数据采集、 计算、无线通信和数据融合等功能，传感器节点被部署在特定的目标区域内，协同合作， 共同来监测、收集和处理周围环境的相关信息，再通过无线通信网络把最终的信息传送 给相应的终端，使信息收集者能够时时地掌握监测区域的信息并及时做出反应i l 】。由传 感器节点组成的a dh o c ( 点对点) 网络被称为无线传感器网络( w s n ，埘r e l e s ss e n s o r n e 铆o r l ( ) 。 近年来，由于微电子技术、无线通信技术、计算技术的快速发展，传感器技术在多 功能、低功耗等技术上也得到了飞速地发展，传感器节点可以集成信息采集、相关数据 的处理以及传感器节点之间无线通信等功能。监测区域内部署的海量传感器节点组成了 无线传感器网络，传感器节点之间以无线多跳的通信方式构成了一个自组织的传感器网 络，传感器网络感知，收集，交换和处理监测目标的相关信息，然后传输给信息收集者。 传感器节点、被监测目标与信息收集者被称为传感器网络三要素。i n t e m e t 改变了人与 人之间的沟通方式，无线传感器网络则融合了物理世界与信息世界，使人类和自然的沟 通方式发生了巨大的变化。人们能够通过传感器网络来观察世界，从而使人类更加了解 世界。在预测未来技术发展的报告中，无线传感器网络技术被美国商业周刊列为2 l 世 纪最具影响力的2 1 项技术之一【2 】。未来的三大高科技产业包括传感器网络技术、仿生人 体器官和塑料电子学1 3 j 。 1 1 1 传感器网络结构 传感器网络通常是由传感器节点( s e l l s o rn o d e ) ，汇聚节点( s i i l l 【n o d e ) ，管理节点 ( m a n a g e m e n tn o d e ) 三种节点组成【4 _ 7 】，传感区域中海量的传感器节点以自组织的方式构 成传感器网络，传感器网络结构如图1 1 所示。由于传感器节点的传输能力有限，所以 传感器节点需要以多跳的方式将自身收集到的数据传输出去，通常情况下，传感器节点 可能需要通过多个中间节点才能够将监测到的数据传送给汇聚节点，汇聚节点再通过互 联网或卫星网络将数据传输给任务管理节点，任务管理节点接收到数据以后对数据进行 存储和处理，再通过汇聚节点向传感器网络发布新的监测任务。 哈尔滨工程大学硕士学位论文 图1 1 无线传感器网络体系结构图 无线传感器网络具有以下与传统网络不同的特点： ( 1 ) 有限的能量。由于传感器节点的工作需要能量的支持，当能量耗尽的时候，传感 器节点就失去了作用。因此设计无线传感器网络的时候都要以节能为前提，从而高效率 地使用有限的能量【8 1 。 ( 2 ) 自组织性。传感器网络的自组织性包含自组织通信、网络的自我调度和网络的自 我管理等功能，也就是说，传感器网络能够自动形成一个独立传输监测信息的无线网络。 ( 3 ) 多跳的路由。因为传感器节点能量有限，所以节点无法进行远距离传输，只能与 相邻节点进行直接通信。如果传感器节点要和通信范围之外的节点进行通信，则需要通 过中间节点形成多跳的路由来完成通信【9 】。 ( 4 ) 动态拓扑。传感器网络是一个动态的网络。网络中的节点可能会因为能量耗尽等 因素而失效，脱离传感器网络；同样地，传感器网络也可能增加一个新的节点；另外在 一些特殊的应用中，传感器节点的位置不是固定的。以上这些因素都会导致传感器网络 拓扑的变化，因此，为保证自身工作的连续性，无线传感器网络必须具备动态拓扑自组 织能力。 ( 5 ) 无中心。传感器网络是对等网络，传感器节点之间的关系是平等的，网络没有指 定的控制中心，可以随时向网络中添加节点或是从网络中撤销节点，添加或撤销节点对 网络造成的影响非常小甚至没有影响。 ( 6 ) 安全性。传感器节点常常被部署在恶劣的环境下或在敌对的区域中，又由于传感 第1 章绪论 器节点能量受限，以及通信信道的脆弱性，无线传感器网络非常容易遭受攻击。为保证 信息的机密性与安全性，在设计无线传感器网络的时候，要特别考虑网络的安全性问题。 1 1 2 传感器节点特征 传感器节点是一个微型的嵌入式系统，使用自身携带的微电池进行工作。传感器节 点是由传感器模块、处理器模块、无线通信模块、能量供应模块四部分组成的，如图1 2 所示。传感器模块的功能是通过感知周围环境中需要监测的物理量来采集数据，并对采 集的数据进行数据类型转换；处理器模块的功能是对自身采集的数据，或是从其他节点 接收的数据进行计算、存储、融合等操作；无线通信模块的功能是向其他节点传输自身 采集的数据或接收从其他节点发送的数据；能量供应模块的功能是为其他三个模块提供 运行所需的能量，一般使用微电池作为供电装置。从网络的角度来说，传感器节点同时 具备终端和路由两个功能，节点不但要完成对监测信息的采集和处理，还要对从其他节 点接收的数据进行存储、计算、转发等功能，与其他节点协同完成任务。 传感器模块处理器模块无线通信模块 处理器 i 传感器h a c 仍c ，i 网络卜一m c 卜叫收发器i 存储器 j ijlji 能量供应模块 图1 2 无线传感器节点结构图 传感器节点具有以下特征： ( 1 ) 电池电量有限。传感器节点体积微小，所携带的电池电量有限。由于节点数量大， 分布区域广，且经常被部署在人类无法达到的危险环境中，因此通过更换电池的方式来 为传感器节点补充能量是很难实现的。如何高效率的使用传感器节点中有限的能量以延 长传感器网络的使用寿命，是传感器网络研究中的重要课题。近年来，随着集成电路技 术的发展，节点的传感器模块和处理器模块能耗降低，因此无线通信模块消耗了节点的 大部分能量。表1 1 为节点各功能模块的能耗对比。 哈尔滨工程大学硕士学位论文 表1 1 节点各功能模块的能耗对比 网络中节点模块模块能耗( m v ) 传感器模块 3 通信模块一发送 1 3 通信模块一接收 1 2 通信模块一空闲 1 0 通信模块一睡眠 2 ( 2 ) 多种工作状态。对于传感器节点来说，节点的通信模块存在发送、接收、空闲与 休眠四种状态。发送和接收状态下的节点会消耗大量的能量，空闲状态时，节点通过监 听无线信道来确认是否有数据发送给自己，睡眠状态的节点不与外界进行通信，几乎不 消耗能量。 ( 3 ) 有限的通信能力。无线通信能量消耗e 和通信距离d 的关系为e = 材”，其中， 2 玎 4 。许多因素影响挖的取值，例如传输过程中存在障碍物，传输介质不同等。因 为能量消耗会随着通信距离的增加而呈指数形式增长，所以传感器节点的通信范围一般 不超过1 0 0 m ，否则节点会因为通信能量消耗过快而失效。 ( 4 ) 计算和存储能力有限。由于传感器节点携带的电池电量有限，而复杂的运算所 需的能量较高，因此节点无法进行复杂地运算。另外由于节点的体积很小，所以节点存 储的容量有限。 1 1 3 无线传感器网络的应用 近年来传感器网络应用范围越来越广，传感器网络正在深入更多的领域。 ( 1 ) 军事领域。传感器网络具有节点数量大、分布广、隐蔽性好、抗捕获性强的特点， 被广泛应用于军事领域。传感器网络可以对敌方的兵力、装备等作战信息进行跟踪，对 战场进行监控，对特定目标进行搜索和定位。无线传感器网络是由随机分布的大量传感 器节点组成的，即使部分节点被敌方捕获，剩余的节点依然可以通过自组织来完成任务。 ( 2 ) 环境领域。近年来，环境科学逐渐受到人们的关注。在环境研究方面，无线传感 器网络可以检测农作物的生长情况、土壤成分的变化以及牲畜与家禽的健康状况，无线 传感器网络还可用于对地表及气象的监测，水位监测等等，通过将传感器节点布置在鸟 类或昆虫的身上，研究人员可以依据收集到的相关信息进行种群复杂度的研究。 ( 3 ) 医疗领域。可以通过将传感器节点部署在病人身上来实时监测病人的体温、血压、 4 第1 罩绪论 心率等生理数据，通过节点传回的数据就可以掌握病人的身体状况，随时处理可能突发 的情况。节点收集到的数据对人体生理活动的了解和对新药的研制都有很大的帮助，传 感器节点也可以用来管理医院的各种药物。 ( 4 ) 家居领域。可以在电器或者家具周围安放传感器节点，将传感器节点收集到的数 据传输给因特网，人们通过因特网来观测家庭的状况，为生活提供便利。通过远程控制， 可以对家电进行远程遥控，也可以通过图像传感来监控家里的安全情况。 无线传感器将逐渐深入到人类生活的各个领域，人们生活的环境正在被无线传感器 网络所改变。 1 2 无线传感器网络的安全问题 在某些情况下，传感器网络中传递的重要信息是需要保密的，此时传感器网络的通 信安全就变得非常重要【1 0 】。加密计算与身份认证是保障传感器网络安全的重要方法，节 点之间建立共享密钥是传感器网络安全的基础【1 。在加密、路由安全和数据通信中，密 钥管理都起着非常重要的作用，因此有必要设计一套安全稳定的密钥管理方案【12 i 。 和现有的网络相比，传感器网络在安全方面有如下特点： ( 1 ) 传感器网络中的能量、存储和计算能力有限。 ( 2 ) 一般的传感器节点都是位置固定的，且有一定的故障率。 ( 3 ) 由于节点寿命有限和外界的干扰，传感器网络的网络拓扑结构不稳定。 ( 4 ) 传感器网络的针对性强，应用的领域具有一定的局限性。 ( 5 ) 传感器网络以数据为中心。 所以，在安全机制方面，有别于传统的有线网，传感器网络的安全机制既需要满足 其自身的特点，又由于传感器节点能量有限，计算能力较弱等缺点，使传统有线网络中 的d i m e h e l i i l a j l 密钥交换协议，r s a 公开密钥体系【1 3 】，k d c e yd i s 仃i b m i o nc e m e r ) 等密钥管理方案【1 4 】都不适用于无线传感器网络，其原因如下： 首先，传感器节点是微型的嵌入式设备，传感器网络中没有计算和数据处理能力很 强的服务器，所以无法使用k d c 来对密钥进行管理。其次，能耗是传感器网络所面临 的重要问题【】5 】，r s a 等非对称公开密钥算法要用到大量的指数运算1 6 1 ，而传感器网络 能量有限，计算能力较弱，大量的指数运算是不现实的。n a il a b 的c 锄a n 等人的相 关研究表明，非对称密钥算法无法应用于传感器网络【l 7 1 。 哈尔滨工程大学硕士学位论文 表1 2 非对称密钥算法计算能耗 c o m p u t a t i o ne n e r g yc o n s u m p t i o n ( m j ) c l o c k p r o c e s s o r p o w e r ( m j )r s ar s ad s ad s ad i 硪e ( m h z ) s i g nv e r i 母s i g i l v e r i f y h e l l m a n z 1 8 01 12 9 03 8 0 01 9 42 4 0 04 6 0 03 7 4 0 m c 6 8 3 2 81 75 08 5 04 05 2 51 0 5 08 2 5 m c f 5 2 0 43 26 1 07 7 03 74 6 09 8 07 5 5 m i p sr 4 0 0 07 52 2 01 7 70 8 59 82 01 6 9 当典型传感器节点工作时，表1 2 中总结了几类主要的非对称密钥算法计算所需的 能耗。m c 6 8 3 2 8 芯片进行一次普通的r s a 加密( 1 0 2 4 b i t 密钥) 就需要消耗8 5 0 m j 的能 量，而这个芯片只有5 2 m w 的最大输出功率。非对称加密算法中，加密计算对节点能量 损耗过大，如此巨大的计算能量损耗是节点在运行时无法承受的。因此，传统的非对称 密钥算法无法应用于传感器网络，传感器网络需考虑使用对称加密算法。同样地， c 姗a n 等人测试了几种常用的对称加密算法，这些加密算法在传感器节点计算所需的 能耗情况如表1 3 所示。 表1 3 对称密钥算法计算能耗 p r o c e s s o r a e s ( i i l j b )s h a l ( m j b )m d 5 ( m j b ) z 1 8 00 2 50 0 1 3 0 0 0 7 m c 6 8 3 2 8 0 0 1 3 10 0 0 0 6 60 0 0 8 m c f 5 2 0 4 o 0 3 5o 0 0 1 8 9 5o 0 0 0 9 5 7 m i p sr 4 0 0 00 0 0 1 1 60 0 0 0 0 5 9 o 0 0 0 0 2 8 如表1 3 所示，对称加密算法的计算能耗要远小于非对称加密算法。例如，a e s 算 法所消耗的能量在百分之一毫焦耳左右，可以应用于传感器网络，s h a 等对称加密算法 所需的计算能耗更小【1 8 】。从密钥长度的角度来说，对称加密算法要比非对称加密算法的 长度短，因此，相对于非对称加密算法，对称加密算法更适合无线传感器网络u 引。 对称密钥体制的实现需要相关的密钥管理方案，密钥管理方案一般为以下3 种【2 圳： ( 1 1 通过可信任的第三方服务器来管理协商节点双方的密钥，常用方案是k e r b e r o s 。 ( 2 ) 使用公开密钥体系，通过数字证书等方法来管理密钥，常见的公开密钥体系方案 是基于r s a 的p k i 。 ( 3 1 在传感器网络部署之前，预先将密钥分配给各个传感器节点，节点运行之后，动 第1 苹绪论 态地进行密钥广播和密钥交换，形成传感器网络的密钥连通图，密钥发现的过程是自组 织分布式的，密钥预分配方案中不需要服务器进行密钥管理。 根据前面的分析，基于可信任服务器的方法和公开密钥体系方案都无法适用于传感 器网络，只有密钥预分配方案可以应用于传感器网络。所以在实际应用中，传感器网络 一般采用能耗低的对称加密算法来进行安全通信，密钥在节点部署前预先分配给传感器 节点，在节点部署以后，节点之间动态地进行密钥协商与交换。整个密钥协商与交换的 过程是分布式的，整个方案不存在密钥管理服务器。密钥预分配方案中主要的性能指标 包括：节点之间安全连通的概率、网络的抗捕获性、可支持的网络规模以及传感器网络 的负载。安全连通率是指节点之间建立共享密钥的概率，概率越高，则传感器网络的连 通性就越好；抗捕获性表示在部分节点被捕获的前提下，传感器网络仍然保持安全的概 率，较高的抗捕获性可以使传感器网络更加安全；可支持的网络规模越大，说明方案的 适应性越强；负载包括了节点计算负载，存储负载和通信负载，由于节点资源有限，因 此要最大程度地降低网络负载【2 1 1 。 1 3 密钥预分配方案的研究现状 1 9 8 5 年，b l o m 等人提出了基于密钥矩阵的方案，通过使用对称矩阵的方法将密钥 分配给传感器节点【2 2 1 。该方案的存储和计算开销比较大，且无法实现网络的扩展。1 9 9 3 年，b l 吼d o 等人在b l o m 研究的基础之上，提出了基于对称二元f 次多项式的加密方案， 包含相同对称二元多项式的传感器节点之间都可以进行安全的通信，并且在被捕获节点 数少于f 的时候，方案都是绝对安全的【23 | 。 2 0 0 2 年，m a r y l a n d 大学的e s c h e m a u e r 和g l i g o r 提出了一种基于随机概率的密钥预 分配方案e s c h e n a u e r - g l i g o r 方案( e g 方案) ，后来的许多密钥预分配方案都是以e g 方 案为基础提出的。e g 方案中的三个重要元素分别为传感器节点的数量船，节点的密钥 环七，以及密钥池的大小p 。密钥池随机为传感器网络中的每个传感节点分配尼个密钥， 直接进行安全通信的两个节点至少需要一个公共密钥作为共享密钥，如果两个节点的公 共密钥数大于1 ，则选择其中的一个公共密钥作为共享密钥【2 4 | 。2 0 0 3 年，c h 觚等人提 出了c h a n p e 玎i g s o n g 方案( c p s 方案) ，在c p s 方案中，两个传感器节点至少需要g 个公共密钥才能够建立共享密钥。两个节点将印个公共密钥哈希函数的运算结果作为共 享密钥来进行安全通信【2 5 j 。这两种方案虽然现实可行，但是对节点被物理捕获的抗捕获 性并不理想，方案的抗捕获能力有待提高。 2 0 0 4 年，c 锄t e p e 等人首次将组合设计方法应用在密钥预分配方案的设计中【2 6 | 。虽 哈尔滨工程大学硕士学位论文 然基于区组设计的方案都有比e g 方案更高的密钥连通概率，平均密钥路径长度也更 短，但方案支持的网络规模不连续，扩展性差。2 0 0 6 年，l i u 等人基于分组思想，设计 了传感器分组密钥预分配方案。通过将传感器节点进行分组，使组内节点的安全连通概 率达到1 0 0 2 7 】，但是该方案中组间节点的连通率非常低。2 0 0 7 年，l e e 和s t i n s o n 等人 基于组合结构设计，提出一种线性的密钥预分配设计方案，通过选择不同的参数来改变 传感器网络的抗捕获性和安全连通率【弱j 。 1 4 论文的主要工作及安排 本文的思路是：首先对随机型密钥预分配方案和确定型密钥预分配方案的实现方法 及性能进行分析，然后引出分组密钥预分配方案。鉴于传统分组密钥预分配方案组间节 点连通率低，扩展性差等局限性，本文提出了一种改进的传感器网络分组密钥预分配方案。 本文首先对t d ( k ，n ) 方案进行了改进，提出一种可解析的t d ( k ，n ) 方案。然后将可解 析的t d ( k ，n ) 方案与b l u l l d o 二元对称多项式方案相结合，进一步提出一种改进的传感器 分组密钥预分配方案i g d k p s ( i i n p r o v e dg r o u pd e p l o y m e n tk e yp r e d i s 仃i b u t i o n ) 方案，并 对方案的实现过程及性能进行了详细说明和理论分析。将提出的i g d k p s 方案与l i u 方 案、e g 方案三者进行仿真分析对比，最后，对比结果表明，i g d k p s 方案在传感器网 络连通率和抗捕获性上要优于后两种方案。 本论文共分4 章，各章的主要内容如下： 第1 章介绍了传感器网络的结构和特征，并对传感器网络的安全问题进行了分析， 分析表明，基于对称加密的密钥预分配方法比较适用于传感器网络。 第2 章对经典的e s c h e n a u e r g l i g o r 和c h a j l p e r r i 哥s o n g 两种随机型密钥预分配方案 进行了描述，并对两种方案的性能进行了分析和对比，然后对近年来提出的基于区组设 计的确定型密钥预分配方案方案进行了研究和分析。 第3 章对同构分组密钥预分配方案的实现过程及性能进行了描述，鉴于现有分组密 钥预分配方案的不足，提出一种改进的分组密钥预分配方案i g d k p s ，并对i g d k p s 方 案的实现过程和性能进行了详细的分析与说明。 第4 章对i g d k p s 方案的相邻节点连通率，网络整体连通率以及抗捕获性等密钥预 分配方案中的重要性能指标进行了实验仿真，并与l i u 方案、e g 方案的仿真结果进行 了对比，对比表明，在传感器网络分组部署的环境下，i g d k p s 方案能够展现出良好的 抗捕获性、连通率和网络灵活性。 最后对本文的工作做出总结和展望，并提出可能对i g d k p s 方案有所改进的方法和 思路。 第2 章无线传感器网络密钥预分配方案 第2 章无线传感器网络密钥预分配方案 分布式无线传感器网络一般部署在无人区域或敌方领域内，传感器网络节点的数据 处理能力，存储容量和通信能力都受到了较大地限制。由于节点计算能力有限，因此基 于信任服务器的密钥管理方法无法在传感器网络中实现，由于节点能量有限，因此基于 公钥密码的密钥管理方案也无法在传感器网络中实现。目前普遍采用的是适合传感器网 络特点的密钥预分配管理方案，密钥预分配方案主要有以下三个阶段： ( 1 ) 密钥预分配阶段。网络部署之前，密钥池为每个节点分配相应的密钥或密钥信息。 ( 2 ) 直接密钥建立阶段。节点通过广播的方式向通信范围内的相邻节点确认是否有公 共的密钥或密钥信息，如果存在公共的密钥，则将其作为安全通信的密钥，如果存在相 关密钥信息，则通过一定的方法来计算两节点之间的共享密钥。直接密钥建立阶段同时 创建了网络安全拓扑结构图。 ( 3 ) 间接密钥协商阶段。如果需要进行安全通信的两个节点没有共享密钥，那么这两 个节点就要通过和这两个节点都有共享密钥的中间节点来建立安全路径进行通信。 2 1 密钥预分配方案的评价指标 无线传感器网络密钥的分配方案一般将安全连通的概率、损失的概率、支持最大网 络的规模和开销这四个方面作为评定标准。 ( 1 ) 安全连通的概率。这是指任选的两个传感器节点之间存在共享密钥的概率。一般 的传感器网络中，假如两个节点可以不借助第三方节点直接交换数据，或者通过一条安 全信道能够交换数据，那么就称这两个节点安全连通。如果一个节点同周围节点都无法 建立共享密钥，则称这个节点为孤立节点。将传感器网络中所有节点看做点的集合，安 全连通路径看做边集合，如果所有点都至少在一条边上，即所有的节点都存在安全连通 的路径，那么这个传感器网络就是安全连通的网络。 如图2 1 所示，传感器网络中一共包含5 个节点，节点的通信范围为3 0 m 。节点1 和节点2 之间存在共享密钥，因此节点1 与节点2 可以建立安全通信。同理节点2 和节 点3 、节点3 和节点4 之间也可以进行安全通信。节点4 虽然在节点i 的通信范围之中， 但是由于节点1 和节点4 之问没有共享密钥，因此节点1 和节点4 之间无法建立安全通 信，如果节点1 和节点4 要进行安全通信，则需要通过节点1 一节点2 一节点3 一节点4 这个安全路径来建立间接的通信。节点5 与其通信范围内的其他节点都没有共享密钥， 哈尔浜工程大学硕士学位论文 无法建立安全通信，节点5 是孤立节点，且整个传感器网络也不是完全连通的。安全连 通概率等于网络中能够建立安全通信的节点对数和网络中总的节点对数的比值。安全连 通概率是衡量传感器网络密钥预分配方案性能的重要指标。 ，一一一一一一、一、 ， 、 ，一一- | 、i 、 、 ，7 。 、 卜、i p 3 0 m， j 、 j 、 、 、 一一7 一一j 一一7 。 、 ， 、 ， 、 、，7， 、 77 、 、7 、一一一一一一一，一 、一一一一一一， 图2 1 一个包含5 个节点的传感器网络 ( 2 ) 损失的概率。如果传感器网络中的节点被敌对势力所捕获，那么该节点中的密钥 信息就是不安全信息。如果传感器网络中某些未被捕获的节点与被捕获的节点存在公共 密钥信息，则这些未被捕获的节点中所存储的信息也就不安全了。使用概率论的相关知 识来定义损失概率： 俐，= 鬣鬻器 陪， 根据概率论的相关知识，假如存在s 个被节点捕获，那么损失概率可写成： 知玎( s ) = 1 一( 1 一b 订( 1 ) ) 5( 2 2 ) 传感器网络的稳健性可以通过损失概率力f 砸) 来量度。 ( 3 ) 可支持网络规模。可支持网络规模是指传感器网络中可以部署的最大传感器节点 数量，可支持网络规模越大，密钥预分配方案就越好，是否支持节点的加入和撤销也是 评价密钥预分配好坏的重要标准。 ( 4 ) 开销包括存储，通信和计算三部分开销。节点存储密钥的开销为存储开销，节点 第2 章无线传感器网络密钥预分配方案 之间计算共享密钥的开销为计算开销，节点之间为了建立共享密钥进行密钥信息交换的 开销为通信开销，开销越小，密钥预分配方案越好。 2 2 随机型密钥预分配方案 在无线传感器网络中有两类密钥预分配方案：随机型密钥预分配方案和确定型密钥 预分配方案。随机型密钥预分配方案是指随机地从密钥池中提取节点所存储的密钥，然 后把它们派发到每个节点；确定型密钥预分配方案是指密钥池和节点存储的密钥是由确 定性的方法构成的，确定型密钥预分配方案可以使网络达到更好的密钥连通性。 2 2 1 特殊的随机型密钥预分配方案 有两种极端的密钥预分配方案是基于概率密钥预分配方案的特例，一种是s i n g l e m a s t e rk e v 方案，一种是n 1 方案例。两种方案的基本思想如下。 在随机型密钥预分配方案中，最简单的密钥分配算法是单密钥( s i n g l em a s t e rk e y ) 算法，也就是相同的密钥被存储在传感器网络中的每一个节点里，这样为网络提供了最 高的连通率，同时消耗比较少的存储空间。但随之而来却产生了抗捕获性差的缺点，只 要有一个节点被第三方捕获，整个网络就会变得不安全。 在n 1 方案中，任意两个匹配的节点之间都被分配了一个相同并且独立的密钥。这 样任意节点的安全通信都不会受其他节点是否被捕获的影响，使方案具备了一定程度上 的抗捕获性。但是这种方案在实现上是很困难的，例如一个由s 个节点组成的传感器网 络，则要求每个节点存储s 一1 个密钥，假如s 非常大，方案是难以实现的。 上述两种方案是基于随机概率的密钥预分配方案中的特殊情况，运用这两种方案均 可以确保邻点之间的安全连通概率最高，并且这两种方案产生的密钥图是完全连通图， 任意两个节点之间都存在共享密钥。但是上述两种密钥预分配方案都无法适用于传感器 网络。原因有如下3 点： ( 1 ) 对于单密钥方案来说，一旦传感器网络中的某个节点被捕获，则整个传感器网络 的信息都会受到威胁，可以说单密钥方案完全不具备安全性。 ( 2 ) n 1 方案中需要有一1 个密钥来分配给每个节点，这样网络就需要( 一1 ) 2 个密钥。因为节点数目巨大，则要求用能量有限的传感器来管理并维护网络是很不现实 的。 ( 3 ) n 1 方案不具备灵活性。因为网络节点具有动态的特性，常常需要添加或者撤销 一个节点。如果采用了n 1 方案，由于之前的节点无法添加新增节点的密钥，因此新加 哈尔滨工程大学硕士学位论文 入的节点很难与原来的节点建立共享密钥。密钥管理是传感器网络安全的基础，由于网 络中节点具有自组织性，所以设计的密钥管理方案必须具备灵活性来适应传感器网络的 特点，此外还要考虑设计的密钥管理方案是否能应用于大规模网络的情况。 2 2 2e s c h e n a u e r - g l i g o r 方案 1 、方案概述 e s c h e n a u e r - g 1 i g o r ( 以下简称为e - g 方案) 方案是一种经典的密钥预分配方案，该方 案是基于随机概率的一种传感器密钥管理方案，它是很多密钥预分配方案的基础，下面 是该方案具体实现过程。 e g 方案的密钥预分配过程分成以下4 个阶段：密钥预分配阶段，直接密钥建立阶 段，间接密钥建立阶段以及密钥撤销阶段。 ( 1 ) 密钥预分配阶段。在密钥预分配阶段，由服务器生成一个具有个密钥的密钥池 ( 国通常具有2 1 7 2 2 0 个密钥) ，并为密钥池中的密钥标号。从密钥池中随机选取f 个密钥 组成密钥环，将随机抽取的密钥环加载到传感器节点当中。在密钥预分配过程当中要保 证每个节点的密钥环都包含一定量的密钥，用来保证传感器网络中任意两个节点共享密 钥的概率。举例说明，如果要保证任意两个节点之间存在共享密钥的概率在0 5 以上， 则需要从密钥数量为1 0 0 0 0 的密钥池中抽取7 5 个密钥组成节点的密钥环。 ( 2 ) 直接密钥建立阶段。传感器网络中的节点部署以后，节点向其通信范围内的邻居 节点广播自身的密钥信息，邻节点接收到信息后就可以判断是否和该节点具有公共密 钥。如果两个相邻节点的公共密钥数大于1 ，则将公共密钥中的一个密钥作为两节点之 间的共享密钥。整个过程即为直接密钥建立阶段。 ( 3 ) 间接密钥建立阶段。如果相邻的两个节点口，6 没有公共密钥，则需要通过第三个 节点c 作为中间节点来间接建立共享密钥路径。中问节点c 需要在口，6 两个节点的通信范 围内，且必须和口，6 两个节点都有公共密钥。 ( 4 ) 密钥撤销阶段。该阶段是指当传感器网络中某个节点能量耗尽之时，失效的传感 器节点就会通过自身的控制器向网络中的其他节点广播自己密钥环中的密钥信息，其他 节点接收到该节点密钥环中的密钥信息后，检查自己是否和这个密钥环有公共的密钥信 息，如果有，那么公共的密钥信息就会被清除，相关密钥信息被清除以后，通过这些密 钥信息建立的安全路径也就失效了。被影响的节点重新通过直接密钥建立阶段和间接密 钥建立阶段来来建立新的安全路径。 因为f 国，所以相邻的两个传感器节点只能以一定的概率存在公共密钥，即两个 第2 苹无线传感器网络密钥预分配方案 相邻的传感器节点间的安全边是以一定程度存在的，这个概率就是安全连通概率，。 e - g 方案的主要目标就是设计合适的国与f ，使得达到一个期望值。删，由此来 保证整个网络的安全口。 e g 方案具有一定的实际应用价值，从传感器网络安全连通率的角度来说，方案可 以通过增加节点密钥环中的密钥数量来保证相邻节点之间的安全连通概率。从抗捕获性 的角度来说，即使网络中的某些传感器节点被捕获，在密钥部署密度均匀的前提下，传 感器网络仍然能保证合适的安全连通率。从灵活性的角度来说，由于传感器节点是从同 一个密钥池中获取相关的密钥信息，因此无论是添加或者删除节点，对密钥管理的影响 都不大。从对存储能力的要求来说，每个传感器节点只需存储f 个密钥组成的密钥环， 这是传感器节点可以接受的【3 2 1 。 2 、随机图论在e g 方案中的应用 e g 方案的数学模型是e r d o s 和r 6 n y i 关于随机图的理论【3 3 】。随机图是指两点间的 存在边概率为尸，p 是等概率且独立的随机变量图。当尸= 0 时，随机图没有任何边； 当p = 1 时，随机图是完全图。 e r d o s 指出：假设存在随机图中的节点数量为以，当玎非常大的时候，如果整个随机 图至少要以一定的概率只构建一个连通图，则有如下的公式( 2 3 ) 。 p = l i mp ( g ，p ) 。砌) = e 。 ( 2 - 3 ) 式中p 为任意两点之间连通的概率，c 是常数，概率p 与节点数量间的关系式如式 ( 2 4 ) 所示。 矽：型+ 三( 2 4 ) 玎玎 当给定了传感器网络节点的数量”与期望的整体连通概率只时，就可以求出传感器 网络节点间的连通概率p ，据此求出节点的平均度d 。综合公式( 2 3 ) ，(