（通信与信息系统专业论文）基于lu矩阵的无线传感器网络密钥预分配算法研究.pdf

摘要 摘要 无线传感器网络( w s n ) ，是由大量资源受限的传感器节点以。a dh o c 方式构成的自组织多跳无 线通信网络，综合了传感器、嵌入式计算、分布式处理和通信等技术，通过节点的协同操作，进行 实时监测、感知和采集各种监测对象的信息并处理和传送到目的节点。 通信安全是无线传感器网络最基本的一项服务，特别是节点被部署在无人触及、容易受损或被 俘获的环境时，保证其安全性更是应优先考虑的问题。无线传感器网络除了具有一般无线网络所面 临的信息泄露、信息篡改、重放攻击、拒绝服务等多种威胁外，还面临传感器节点容易被攻击者物 理操纵，并获取存储在传感器节点中的所有信息，从而控制部分网络的威胁。无线传感器网络的安 全方案中，加密技术是基础，核心则是密钥管理。在低成本、低功耗、资源受限的传感器节点上现 实可行的密钥分配方案是基于对称密码体制的密钥预分配方案，主要分为随机型和确定型两种方案。 随机预分配方案中，节点保存密钥环，节点间通过直接连通和间接连通这两种形式达到一定概率的 连通性。其优点是分配方法简便，缺点是节点间不能保证安全连通，连通概率与节点密钥存储量、 抗毁能力成反比。确定预分配方案中，节点保存密钥构造信息，动态计算出节点间的共享密钥。其 优点是任意节点间可建立直接安全通信，缺点是密钥协商的通信和计算开销较大。 矩阵方案和多项式方案是两种常见的确定预分配方案。本文专注于确定预分配方案的算法研究， 分析了结合l u 矩阵分解和多项式的方案，针对其不足之处，利用u j 矩阵的特性并考虑在多维空间 中加以扩展，提出了四种改进方案。 对称矩阵的分解计算中，除了通常的l u 乘积形式( 其中l 为下三角矩阵，u 为上三角矩阵) 以外。还包括一种变化形式l d l t 乘积形式( 其中d 为对角线矩阵，d l t 相当于上三角矩阵u ) 。在 参照范德蒙德矩阵形式构造了l 矩阵的基础上，本文首先在一维密钥空间中提出了基于l u 矩阵 ( u = - d l t ) 和基于a b 矩阵( a b = b ) a t ，b t = l ，a t = l d l - t l t ) 的两种改进方案。随后将这两种方 案扩展到多维空间，提出了多维l u 矩阵以及多维a b 矩阵的两种相应方案。计算结果表明，多维 密钥空间的改进方案可以用较低的存储、通信、计算开销满足更大的网络容量需求。在保持安全连 通基础上，提高了节点抗毁能力，改进了动态扩展能力，是两种高性能的无线传感器网络密钥预分 配方案。 【关键词】 无线传感器网络，安全，密钥预分配l u 矩阵，多维，分簇 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k ( w s n ) ，i sas e l fo r g a n i z e dm u l t ih o pw i r e l e s sc o m m u n i c a t i o nn e t w o r kt h a t b a s e do nab i ga m o u n to fa dh o c - s t r u c t u r e da n dr e s o u r c e - c o n s t r a i n e ds e n s o r s w s nc o l l e c t si n f o r m a t i o n f r o mt a r g e t si nr e a lt i m eu s i n gs e n s o r , e m b e d d e dc o m p u t i n g ，d i s t r i b u t e dp r o g r e s s i n ga n dc o m m u n i c a t i o n t e c h n o l o g y i n f o r m a t i o ni sc o l l e c t e db yc o o p e r a t i o nb e t w e e nn o d e s c o m m u n i c a t i o ns e c u r i t yi sab a s i cc o n c e r no fw s n ，e s p e c i a l l yw h e nt h en o d e sa 咒b e y o n dh u m a n r e a c ho ri nar i s k ys i t u a t i o n w s ni sn o to n l yt h r e a t e n e db yn o r m a lw i r e l e s sn e t w o r kp r o b l e m ss u c h 雒 i n f o r m a t i o nl e a k a g e ，i n f o r m a t i o nt a m p e r i n g r e p l a y i n ga t t a c h , d d o s ，b u ta l s oi t ss p e c i a lp r o b l e m s w h e n t h en o d e sa r ea a p p e db yi n t r u d e r , a l li n f o r m a t i o ns t o r e dc o u l db ee a s i l yo b t a i n e da n dp a r to ft h ew h o l e n e t w o r km i g h tb ee a s i l yc o n t r o l l e d e n c r y p t i o nt e c h n o l o g yi st h eb a s i sa n dk e ym a n a g e m e n ti st h ek e y e l e m e n to fs e c u r i t ym a n a g e m e n tf o rw i r e l e s ss e n s o rn e t w o r k s r e a l i s t i ck e yp r e - d i s t r i b u t i o ns c h e m e sf o r l o w - c o s t , l o wp o w e rc o n s u m p t i o n , r e s o u r c e - c o n s t r a i n e ds e n s o rn o d e sa r eb a s e do ns y m m e t r i ce n c r y p t i o n a l g o r i t h m n o d e st h a tu s er a n d o mk e yp r e - d i s t r i b u t i o ns c h e m ec o m m u n i c a t ed i r e c t l yo ri n d i r e c t l yw i t hk e y r i n gs t o r e d r a n d o mk e yp r e 新加入节点从基站取得最新的安全信息，根据广播反馈情报选择最近的簇加入，向簇头节 点申请发现节点间共享密钥。如果验证通过，则从簇头节点获得簇密钥，加入安全网络。如果验证 东南大学硕士学位论文 失败，簇头节点会标记该节点i d 为恶意节点，并向基站和其它簇头通报该信息。 模式2 ：扩展密钥空间维数。 ( 1 ) 基站生成新的g ，、4 、昂矩阵( ，：尉1 ) ，由现有安全网络随机选择信息组( 序号、行向 量的种子踟与列向量彳，0 分发至个簇头节点。再由簇头节点随机选择分发至各簇节点。 ( 2 ) 新加入节点类似于模式1 ，通过验证后加入安全网络。 网络规模的缩减形式与扩展类似。有节点退出网络时，基站得到反馈消息后记录矩阵池彳7 的利 用情况：一旦基站发现有某个矩阵彳，不再被利用且报告，如果收到需要缩减规模的命令，将通过广 播向全网通告节点i d 的分量和对应的彳，r 矩阵对应的密钥空间无效，可以删除以节省存储空间。 3 5 基于多维l u 矩阵的改进方案 本方案基于多维密钥空间下的l u 矩阵乘法以及2 元t 度多项式，以下分为三个阶段说明：密钥 预分配阶段，分簇组网阶段，正常运行阶段。 3 5 1 密钥预分配阶段 步骤l ：部署服务器在有限域g f ( q ) ( g 为足够大的素数) 上参照范德蒙德矩阵形式随机生成尺 组上三角矩阵g ，和对角线矩阵d r ( 其中，t r t 为矩阵维数，r 为密钥空间维数) 。 g ，= lll l g r 2g r 3 g r i n g r l 3 赢 g 蒜 赡1 其中，g n o ( 产l ，2 ，墨，乒幺3 ，o n ) ，翻间互不相等； o r = 其中，磊0 ( 严l ，2 ，皿，i = l ，2 ，m ) ，磊间互不相等； 步骤2 ：生成r 组m m 实对称矩阵蜀。 d 啉 ( 3 3 3 ) ( 3 3 4 ) 砟 2砟 砟 第3 章确定密钥预分配的改进方案 矩阵群的生成过程类似于一维密钥空间下的l u 矩阵方式，可参照3 2 1 步骤2 的对应算法。 步骤3 ：密钥预分配。各节点保存节点d 、行向量的种子踟、列向量。 ( 1 ) 各节点从每组密钥空间中随机选择序号，即of i r - i ； ( 2 ) 合并每组抽即令节点i d 为舻i 玩i ，如果节点i d 重复，重新随机选择序号j ：r ； ( 3 ) 按照节点m 组成顺序，节点中保存尺组行向量的种子踟与列向量。 3 5 2 分簇组网阶段 步骤1 ：基站启动分簇组网过程 本过程与多维密钥空间中a b 矩阵的实现过程相同可参照3 4 2 步骤l 的过程。 步骤2 ；节点间通过预分配密钥发现各对应密钥空间的基础共享密钥 任选两个节点a 、矗，针对第，组( i d a ，g a , 啪和嵋，跏c 劲，有如下发现过程。 ( 1 ) 节点a 向节点b 发送( i d a ，鲥( 其中，钿= 田叫) ( 2 ) 节点b 计算硒 ：f ( i r a ，山) ：戚芝脚屯t 川r a 嚣- = 曲篁川( 既i 叫i r b ) 口d ( 唬) ( 3 3 5 ) a = la = l ( 3 ) 节点b 向节点彳发送a 。筋嘲( 其中，j , b = i d , a ) ( 4 ) 节点a 计算杨 ：厂，锄) = 施窆厶嚣t 管1 。1 1 1 1 n 塞厶( i , b i r a ) 纠d - 口。- t ) ( 3 3 6 ) a = la - - - i 如果局庐钿，则第，组共享密钥值对发现成功( 此时岛是数值，不是向量) 如果确认了全部共享密钥值对，则向节点b 发送认证成功消息，否则发送认证失败消息。 ( 5 ) 节点b 如果接收到反馈的认缸成功消息，节点彳和节点b 问可以建立安全链路。 步骤3 ：构造节点间共享密钥，建立的安全链路，簇头向簇内分发簇密钥。 ( 1 ) 由于节点a 、b 所得到的k o p k r # ( 闰，1 ，r - 1 ) 都相同，故可构造相同的向量。 ( 2 ) 对比前述2 元t 度多项式( 2 2 ) ，该向量可构成2 元尺一1 度多项式在，维密钥空间中令 f嘞= 0 ，o ，) 1 巧：m 羔”g j 加t 叱妒d “：d q 3 乃 东南大学硕士学位论文 用节点i d 的分量序号合计值代替节点i d 本身，参照多项式算法，有类似于( 3 3 1 ) 和( 3 3 2 ) 的两式成立。如果乃户，该值即为节点间共享密钥。 ( 3 ) 参照3 4 2 步骤3 的( 3 ) ，两者过程基本相同。 3 5 3 正常运行阶段 本方案中网络节点规模的动态更新与多维密钥空间的a b 类似，同样有两种模式；调整密钥空 间维数，调整密钥空间内向量维数。 以下详细说明扩展的实现方式。 模式1 ：扩展密钥空间内向量维数。 ( 1 ) 由于各维密钥空间的扩展过程完全相同，以下以第，维为例说明。令矩阵g 和矩阵d 都 扩展到m + l 维。 则有下式成立 l ：g r ： d = u = d g = l 1 9 2 1 9 3g g 、 1 g 州磊+ l 西 如 呜 而西4 9 2 吐9 3 如 爵如 d m + l 而 g l + d 2 g 三+ l 如 ( 3 3 8 ) ( 3 3 9 ) ( 3 4 0 ) 如上所示，l u 矩阵都扩展m + l 维，依然满足前述的标准l u 矩阵形式。 ( 2 ) ( 3 ) ( 4 ) 与多维空间的a b 矩阵方式基本相同，可参照3 4 3 扩展模式1 的对应内容。 其中，列向量由a ，0 改为u n 。 模式2 ：扩展密钥空间维数。 ( 1 ) 基站生成新的g ，、d ，矩阵( 闽+ 1 ) ，由现有安全网络随机选择信息组( 序号“行向量的 2 6 第3 章确定密钥预分配的改进方案 种子劭与列向量分发至个簇头节点，再由簇头节点随机选择分发至各簇节点。 ( 2 ) 新加入节点类似于模式l ，通过验证后加入安全网络。 网络规模的缩减形式与扩展类似。有节点退出网络时，基站得到反馈消息后记录矩阵池u 的利 用情况：一旦基站发现有某个矩阵坼不再被利用且报告，如果收到需要缩减规模的命令，将通过广 播向全网通告节点i d 的分量和对应的珥矩阵对应的密钥空间无效，可以删除以节省存储空间。 3 6 追加随机参数的改进方案 该方案是对前述改进方案的补充，主要差别在于共享密钥砀应用随机参数后再传输。 ( 1 ) 计算共享密钥时( 多维空间场合，针对各组基础共享密钥) ，算出的岛值是直接发送的。 如果在传输局前，生成一个随机参数，同时发送k y x o r p 与户，对方节点验证时，如果满足下式， 则使用k _ 岱p 作为共享密钥。 k j i = k j i x o r p = k 畦x o r | b = k 珏 q a u ( 2 ) 计算共享密钥时，如果某个节点被俘获。复制了一个节点，两者都企图加入安全网络的情 况下，入侵节点可以获取被复制节点与其它所有节点间的共享密钥。引入随机参数后，复制节点与 原节点针对相同节点计算所得的共享密钥将各不相同。这实际上是提高计算通信开销来提高节点抗 毁能力，只有对安全性有极高要求时才适合采用。第4 章的性能分析未考虑该优化方式。 3 7 本章小结 本章首先简述了结合l u 矩阵分解和二元多项式密钥预分配的方案【1 3 l 的不足，依次基于l u 矩 阵、a b 矩阵、多维a b 矩阵、多维叫矩阵及随机参数等方面提出了改进方案，并就密钥预分配、 分簇组网和正常运行三个阶段加以详细说明。 2 7 东南大学硕士学位论文 4 1 引言 第4 章改进方案的性能分析与比较 本章首先回顾用于对比的基准方案的不足之处，然后针对第3 章提出的基于l u 矩阵、a b 矩阵、 多维a b 矩阵、多维l u 矩阵的改进方案，就网络连通度、存储开销、通信开销，计算开销、动态 扩展能力以及抗毁能力等指标进行归纳分析，并以图表的形式与基准方案进行性能对比 4 2 基准方案的缺点回顾 4 2 1 基于2 元多项式的密钥预分配方案 ( 1 ) 该方案中，每个节点都要保存基于共享多项式计算的什l 项系数，节点存储开销较大。 ( 2 ) 网络规模动态扩大时，新节点仍可保持全连通，但安全门限t 与节点容量的比例逐渐减低， 全网安全性下降。而提高安全门限t 必须替换系数更多的多项式，并更新所有节点，所需开销巨大 ( 3 ) 网络规模较大时，安全门限t 较高，节点问连通所需计算开销较大。 4 2 2 结合l u 矩阵分解和多项式的密钥预分配方案 ( i ) l u 矩阵整数分解困难。任意生成的对称矩阵墨l u 分解的结果几乎都是两个包含小数的 三角矩阵，而同样的算法下，小数运算远比整数运算复杂 ( 2 ) 节点存储量较高。节点需要保存节点d ，行向量及u 列向量，其平均存储量与基于多 项式的方案相当 ( 3 ) 通信复杂度较高节点间计算共拿密钥时需要交换节点d ，l 行向量信息、指示l u 向量 的非零系数个数f 以及确认用的通信密钥足，平均通信复杂度约为 l 0 9 2 + 掣l 0 9 2 q + l 0 9 2 m + 吾1 0 9 2 足 ) 二 二 ( 4 ) 计算复杂度较高计算岛或晦：f 次乘法；计算共享密钥：( - 1 ) 2 次乘泌( f 1 ) 次加法 因为卢l ，2 ，妒，所以可以产生埘2 种乘法，约m 2 2 种计算结果。三向量的非零项有女项时，多项式 硒的结果可能项数为l ，2 ，厶，m 所以构造多项式时的平均计算复杂度为伽+ l x 2 m + 1 ) 6 m 次乘 法，平均项数也为讲= 伽十l x 2 m + 1 ) 6 m 。由于通过多项式计算密钥时，包含2 ( m ，- 1 ) 次乘法+ 伽，1 ) 次 乘法，所以总的平均计算复杂度约为细1 3 柳次乘法- + ( m 4 ) 3 次加法，对比基于多项式的方案：( 2 t - 1 ) 次乘法唧次加法，由于向打1 ，其计算复杂度有了较大降低 ( 5 ) 动态扩展性不足。对称矩阵k 经过l u 矩阵分解得到l u 三角矩阵，当矩阵足中追加l 行 2 客 第4 章改进方案的性能分析与比较 1 列时，重新执行l u 分解的结果和原来的分解结果相比，几乎全部向量都变更了。 4 3 性能分析与比较 针对基于多项式的方案、结合l u 矩阵分解与多项式的方案以及e - g 方案就网络连通度、存储 开销、通信开销，计算开销、动态扩展能力以及抗俘获能力等指标与本文提出的改进方案进行对比 分析 4 3 1 网络连通度 对比的所有方案都是基于确定密钥预分配的方案，任意节点问都可以计算出共享密钥。因此采 用这些方案的无线传感器网络，其网络连通度均为1 4 3 2 存储开销( 网络容量) l 节点用于安全通信的存储开销主要包含节点i d 和通信密钥构造信息。 ( 1 ) 多项式方案： 是网络容量由于l 0 9 2 n 相当于节点i d ，闩胛- 1 ，所以本方案的存储开销有下式成立 l 0 9 2 + ( t + 1 ) l 0 9 2 叮= l 0 9 2 + m l 0 9 2 口 ( 4 2 ) ( 2 ) 结合l u 矩阵分解与多项式的方案：( 以下简记为l u 矩阵分解方案) l u 矩阵中节点保存交长向量，l 0 9 2 m 对应向量序号，所以本方案的存储开销有下式成立 l 0 9 2 n + ( m + 1 ) x 0 9 2 q + l 0 9 2 嬲 ( 4 3 ) ( 3 ) l u 矩阵方案：( 以下四种为改进方案) l 0 9 2 q 对应g i ，伽+ 1 ) 2 x l o g 奢l 对应列向量m ，所以本方案的存储开销有下式成立 1 0 9 2 + 1 0 9 2 9 + 竿1 0 醴+ 1 0 9 2 m _ l 0 9 2 n + m z + 3 l 。9 2 9 + 1 0 9 2 历) ( 4 ) a b 矩阵方案： l 0 9 2 q 对应白，m l 0 9 2 q 对应列向量彳1 所以本方案的存储开销有下式成立 l 0 9 2 窖+ m l 0 9 2 叮+ l 0 9 2 朋= ( m + 1 ) l 0 9 2 口+ l 0 9 2 历 ( 4 5 ) ( 5 ) 多维a b 矩阵方案： 因为针对r 个独立矩阵彳，r ，m 与m 同近似有下列公式成立 i 譬 ( 4 6 ) n ：瓶 ( 4 7 ) 銮堕奎兰堡主兰垡堡茎 r l 0 9 2 = 去l 0 9 2 ( 4 8 ) 因为针对r 个矩阵月，r ，m = m r ，所以本方案的存储开销有下式成立 ( 1 。9 2 叮+ 所l 0 9 2 q + l 。9 2 m ) r = ( 聊t + 1 ) r l 。9 2 q + r l 。9 2 胁= 吾l 。9 2 + ( 册+ r ) l 。9 2 9 ( 4 9 ) ( 6 ) 多维l u 矩阵方案： 类似于方案5 ，本方案同样满足公式( 4 8 ) ，所以本方案的存储开销有下式成立 ( 丁m + 3 峭2 q 与2 m 卜学l 0 9 2 q + r l 0 9 2 m = l l 0 9 2 n m + 3 r 怕酽 由于t = m 1 、m - - m r 以及通常r 远小于m 。对比以上公式，方案6 的存储开销最低。 计算网络容量时，当向量维数m 相当的情况下，方案1 和方案4 只包含1 个多项式，方案2 和 方案3 可生成约m 2 2 个不同的多项式，而方案5 和方案6 则可以生成( 研，沈广个不同的多项式。所 以在同样存储开销条件下，方案5 和方案6 的网络容量远高于其它对比的方案。 4 3 3 通信开销 通信开销主要包含节点i d 、密钥构造信息以及确认用的通信密钥。( 以下计算每节点平均通信 开销，因为确认成功失败消息各方案相同，没有考虑在内) ( 1 ) 多项式方案： 由于只需要交换节点i d ，尺为生成的通信密钥，所以本方案的通信开销有下式成立 l 0 9 2 + 去l 0 9 2 k ( 4 1 1 ) ( 2 ) l u 矩阵分解方案： 由于还需要交换三行向量信息及指示l u 向量的非零系数个数i ，所以本方案的平均通信 开销有下式成立 l 。9 2 + 孚l 0 9 2 0 9 2 脚+ 扣2 k ( 3 ) l u 矩阵方案： 类似于方案2 ，但是用l 行向量的生成参数白代替了三行向量信息，所以本方案的通信 开销有下式成立 l 0 9 2 + l 0 9 2 9 + l 0 9 2 册+ 妻l 0 9 2 鬈( 4 1 3 ) ( 4 ) a b 矩阵方案： 近似于方案3 ，因为直接用f 代替了节点i d ，所以本方案的通信开销有下式成立 l 0 9 2 叮+ l 0 9 2 m + 去1 0 9 2 k ( 4 1 4 ) 第4 章改迸方案的性能分析与比较 ( 5 ) 多维a b 矩阵方案： 相当于足组独立的a b 矩阵方案的通信开销，所以本方案的通信开销有下式成立 ( - 。9 2 9 + 。9 2 加。+ 互1 - 。9 2 k 。) r = 三1l 0 9 2 n + r l 0 9 2 q + i r - 。9 2 足 ( 4 5 ) ( 6 ) 多维l u 矩阵方案： 相当于r 组独立的l u 矩阵方案的通信开销，所以本方案的通信开销有下式成立 ( - 0 9 2 9 + - 。9 2 历+ 三- 。9 2 k 。) 尺= j 1i 0 9 2 n + r l 0 9 2 q = - 詈。9 2 k c 4 6 ， 对比以上公式，通常情况下还是方案l 的通信开销最少；改进方案相对于方案2 ，通信开销都 有显著减少，其中方案4 的通信开销最小，方案5 和方案6 的通信开销相同。 4 3 4 计算开销 计算开销主要来自公共多项式和共享密钥的计算，其它计算部分未考虑。 ( 1 ) 多项式方案： 由于t = m 1 ，本方案的计算开销为 ( 2 t - 1 ) 次乘法+ ，次加法气2 坍- 3 ) 次乘法+ 伽1 ) 次加法 ( 2 ) l u 矩阵分解方案： 参照前述4 2 2 中( 2 ) 的分析，本方案的计算开销约为 伽一1 3 6 ) 次乘法坳- 4 归次加法 ( 3 ) l u 矩阵方案： 与方案2 对比，本方案只是在l u 矩阵的构造方式及乘法计算时点有差异，平均的加法 运算量是相同的，首先做2 次乘法把g j d a i d s 形成整体参加后续计算，所以本方案的计算开销约为 2 + ( m 4 y 3 2 - 1 次乘法- t - ( m - 4 ) 3 次加法= ( 2 胁i i ) 3 次乘法+ 伽- 4 ) 3 次加法 ( 4 ) a b 矩阵方案： 由于向量序号( - - 2 ，o n ) ，所以平均计算项数为+ 1 ) 2 1 m ，所以本方案的计算开销约为 ( 肌+ 1 ) 2 - 1 m - 1 次乘法+ 仰+ 1 ) 2 1 m 次加法，即约为沏1 ) ：2 次乘法+ ( 朋+ 1 ) 2 次加法 ( 5 ) 多维a b 矩阵方案： 本方案各维密钥空间的计算同方案4 ，还要加上最终共享密钥的计算，其中，1 1 1 - - - - 7 1 7r ， 2 ( 小1 ) 次加法是用节点i d 的分量序号合计值代替节点d 本身，所以本方案的计算开销约为 r ( m 1 ) 2 次乘法+ 饿m ，+ 1 ) 2 次加法+ 2 ( r - 1 ) 次加法+ 2 僻- 1 ) 次乘法+ ( 小1 ) 次加法 即为：( , n + 3 r - 4 心次乘洳( m + 7 r 6 ) 1 2 次加法 东南大学硕士学位论文 ( 6 ) 多维l u 矩阵方案： 本方案各维密钥空间的计算同方案3 ，最终共享密钥的计算同方案5 ，所以本方案的计算 开销约为 娥2 m 1 1 ) 3 次乘法+ 铽所 - 4 ) 3 次加法+ 2 ( r - 1 ) 次加法+ 2 ( r - 1 ) 次乘法+ ( | r i ) 次加法 即：( 2 m 一5 r - 6 ) 3 次乘法- t - ( m + 5 r - 9 ) 1 3 次加法 注：由于乘法耗时远大于加法，因此计算开销的对比，主要关注乘法的计算次数。 由于通常情况下历远大于尺，对比以上公式，方案1 至方案4 ，乘法的主要计算开销由2 m 、m 、 2 m 1 3 、m 1 2 逐渐减小，方案5 和方案6 扩展到多密钥空间后，计算量与对应的一维密钥空间相比稍 有增加，主要计算开销依然保持m 2 、2 m 1 3 。综合来说，方案4 的计算开销最小。除此以外，方案2 由于难于进行整数l u 分解，如果被迫使用浮点数计算的话，计算开销将大量增加。 4 3 5 动态扩展能力 ( 1 ) 多项式方案： 扩展项数时，节点中原有的项都要和节点i d 相乘后更新，扩展能力较差。 ( 2 ) l u 矩阵分解方案： ，扩展矩阵分解得到的l u 矩阵变了，导致所有节点的安全信息都要更新，扩展能力很差。 ( 3 ) l u 矩阵方案： 前述3 2 3 节中说明了新节点动态加入和失效节点的动态撤销的步骤，安全网络内原有的 节点不用更新，扩展能力较好。 ( 4 ) a b 矩阵方案： 前述3 3 3 节中说明了新节点动态加入和失效节点的动态撤销的步骤，扩展时安全网络内 原有的节点需要补足a r 的对应向量中扩展的部分，扩展能力稍差 ( 5 ) 多维a b 矩阵方案： 前述3 4 3 节中说明了新节点动态加入和失效节点的动态撤销的步骤，类似于一维密钥空 间中的a b 矩阵方案，密钥空间内向量维数扩展时能力稍差密钥空间维数扩展时能力较好。 ( 6 ) 多维l u 矩阵方案： 前述3 5 3 节中说明了新节点动态加入和失效节点的动态撤销的步骤，有两种动态更新网 络规模的方式，更新需要的通信开销较小、而规模变化的幅度很大，节点动态扩展能力最好 4 3 6 抗俘获能力( 抗毁能力) 无线传感器节点部署后，节点抗俘获能力是保持网络架构安全的要素。以下通过计算正常节点 问被俘获连接的比例来评估多维矩阵及多维l u 矩阵方案节点面对捕获攻击的抗毁能力，并和e - g 方 3 2 案、结合l u 矩阵分解与多项式的方案( 以下简称l u 矩阵方案) 进行性能比较。 e g 方案中，在任何两个正常节点间共享密钥被捕获的可能性有以下公式成立： 足删蒯= 1 一( 1 一告) 名 ( 4 1 7 ) 其中，七是每节点的密钥数( 相当于l u 矩阵的维数所) ，s 是密钥池的大小。 假设在任何两个正常节点间共享密钥是k ，多项式池中的多项式是局，p 2 ，p ，令g 为x 节点被俘 获的事件，a ，是共享密钥臌己暴露的尸j 算出的事件。在外节点被俘获的情况下，共享密钥廊皮算出 的可能性，在l u 矩阵方案1 1 训i l8 1 中推导出以下公式成立： p c 删毗一驴i - - 杰t + 础珊一矿 其中，节点多项式数硇节点密钥容量七和安全门限，所决定，z = k - t + 1 。为了获得一个大的安全门 限砬远小于多项式池容量缈。 多维l u 矩阵方案( 多维a b 矩阵方案与其相同，以下不再说明) 的每个密钥空间都与l u 矩阵方案 类似，因为l u 矩阵为m ，小的，所以节点密钥容量k = - m ，安全门限t = m 1 ，节点多项式数f = 2 ，多项 式池容量0 3 - = m 忱。因此，对照公式( 4 1 8 ) ，多维矩阵方案的一个密钥空间中有以下公式成立： p ，( 删吲j f i c 一驴i 主= m ij k 三m x m 卅志) h 其中，是密钥空间序号。r - - - i ，2 ，皿，r 是密钥空间维数。 又因为多维矩阵方案的各个密钥空间的计算是独立的，所以有以下公式成立： 婀一北) - ( e r ( e l c o m p r o m i s e d ) ) r 饵习( 斋卅志) 州卜。， 以下通过( 表3 参数列表及图4 1 、图4 2 节点抗俘获能力( a b ) ) 来说明三种方案的对比结果。 表3 节点抗俘获能力对比参数列表 e g 方案【4 il u 矩阵方案1 9 】多维l u 矩阵方案 七s彩 七( 册) ，_ r，纷fr 1 0 01 0 0 0 0 01 0 0 01 0 09 923 224 2 0 01 0 0 0 0 05 0 02 0 01 9 921 6 28 3 3 东南大学硕士学位论文 1s t x l 0 0 1 l 正冀1 0 ，4 1 l x1 0 4 1 1 0 x 1 0 n l ，冀1 0 l l 。t l 口材 t x 1 0 犍 4 。髯i 0 们 2 x 1 0 材 o 簟俘蕊蕾威簟 图4 - 1 节点抗俘获能力( a ) 铷 l o t 磐菝葛赢蠡 图4 2 节点抗俘获能力( b ) 注：多维矩阵方案肌= 3 2 ，r = 4 的轨迹为2 0 0 0 附近的点，图4 - 1 中难以看出 第4 章改进方案的性能分析与比较 4 4 本章小结 本章首先回顾了基准方案的不足之处，然后对2 种基准方案，4 种改进方案以公式推导的方式 加以分析，依据通常的可能取值范围对比