传感器网络中对偶密钥的动态密钥路径建立机制及算法.doc

第2期胡宇舟等：传感器网络中对偶密钥的动态密钥路径建立机制及算法59传感器网络中对偶密钥的动态密钥路径建立机制及算法胡宇舟1，王雷2,3，陈治平2,3，顾学道3（1. 天津大学 管理学院，天津 300072；2. 清华大学 计算机科学与技术博士后流动站，北京 100084；3. 深圳现代计算机公司博士后科研工作站，广东 深圳 518057）摘 要：对偶密钥技术的采用使无线传感器网络通信的安全性得到保障。对偶密钥中的动态密钥路径的应用又进一步提高无线传感器网络通信的可靠性。利用层次超立方体模型中节点编码的特性及其高容错性，提出了基于局部弱连通性概念的簇内动态密钥路径和基于位置信息的簇间动态密钥路径的两类算法。理论与计算机仿真数据分析表明，该算法具有良好的可靠性和高效性，是一种适合无线传感器网络安全可靠的具有实用价值的算法。关键词：传感器网络；安全；对偶密钥；动态密钥路径；超立方体中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)02-0052-07Establishing scheme and algorithm for dynamic key-path of pair wise key for sensor networksHU Yu-zhou1, WANG Lei2,3, CHEN Zhi-ping2,3, GU Xue-dao3(1. Department of Management, Tianjian University, Tianjian 300072, China；2. Postdoctoral Program of Computer Science & Technology, Tsinghua University, Beijing 100804, China; 3. Postdoctoral Program of Shenzhen Modern Computer Manufacture (MCM), Shenzhen 518057, China)Abstract: Security schemes of pair wise key establishment ensure communication security in wireless sensor networks. Dynamic key-path in pair wise key establishment farther increases communication security in the networks. Establishing scheme and algorithm for dynamic key-path in pair wise key for wireless sensor networks were presented based on the encoding peculiarity and high fault-tolerant ability of named H(k,u,m,v,n) (hierarchical hypercube) of cluster distributed sensor networks. Theoretic studies and figures of computer simulation show that the algorithm has good reliability performance and high efficiency, which is suitable for cluster distributed sensor networks.Key words: sensor networks; security; pair wise key; dynamic key path; hypercube1 引言收稿日期：2006-11-10；修回日期：2007-11-22对偶密钥作为一种基础安全机制，广泛应用于安全通信。但基于传感器节点的资源限制原因13，显然公共密钥加密等传统的对偶密钥建立技术并不适合传感器网络节点之间的对偶密钥建立。目前，针对传感器节点的资源限制特性，2002年Eeschnaure和Gligor4基于密钥预置（key predistribution）机制，提出了一种基于概率密钥预置（probabilistic key predistribution）模型。2003年，Chan等5对上述思想进行了扩展，提出了2种新的密钥预置模型，即q-composite密钥预置模型和随机对偶密钥模型。2004年，Liu等6又对上述方法进行了改进，并基于多项式密钥预置模型7，给出了一种基于多项式池的密钥预置（polynomial pool-based key predistribution）模型，并提出了两种新的密钥预置算法，即随机子集指派（random subset assignment）和基于超立方体指派（hypercube-based assignment）的密钥预置算法。Wang等结合传感器网络部署时飞机撒落在山区而容易形成层次超立方体（hierarchical hypercube）H(k,u,m,v,n)的实际，提出了一种在预置密钥路径下基于簇部署的H(k,u,m,v,n)分布模型的对偶密钥预置机制和建立算法8。上述对偶密钥预置模型，虽然有效地提高了传感器网络节点之间的通信安全性，但仍存在着一个预置密钥路径的共同缺陷：当小部分的节点妥协（受到被敌人攻击遭到破坏或故障）时，将会对很大部分的对偶密钥造成影响。本文利用H(k,u,m,v,n)模型中节点编码的特性及其高容错性911建立动态密钥路径，提出了一种对偶密钥下的动态密钥路径的建立机制和建立算法。理论与计算机仿真数据分析表明，该算法具有良好的可靠性能和低的通信开销。另外，算法不要求任意传感器节点之间能直接通信。因此，该算法使传感器网络对偶密钥建立算法成为更具安全可靠性的一种具有实际应用价值的算法。本文的结构如下：在第2节中给出了传感器网络中基于簇部署的层次超立方体H(k,u,m,v,n) 分布模型存在妥协节点时的可靠性分析，在第3节中给出了动态密钥路径建立机制与算法的详细描述；在第4节中对该算法可行性和开销的分析；第5节是结束语。2 对偶密钥预置算法2.1 预备知识定义1 （对偶密钥）：当任意2个节点具有某个共同的密钥E时，则称这2个节点之间具有一个对偶密钥E。定义2 （密钥路径）：当2个节点A0, Ak之间不具备对偶密钥时，若存在路径A0,A1, A2,Ak-1,Ak使得任意节点对Ai, Aj之间至少存在一个对偶密钥，其中0ik-1, 1jk。定义3 （n维超立方体互联网络）：n维超立方体网络Hn（或简称为n-cube）是具有下述性质的一种网络拓扑结构：1）它由2n个节点和n2n-1条边构成；2）每一个节点可由一个不相同的n位二进制串b1b2bn进行编号；3）节点编号的规则为,当且仅当Hn中2个节点的二进制串恰有一位不同时，2个节点是相邻的，即这2个节点之间有一条边相连。2.2 基于簇部署的分布层次超立方体H(k,u,m,v,n)模型传感器节点通过飞机进行分批投放时投放的批次为k，任意传感器节点的通信半径为r。针对每批投放的传感器节点，我们称之为一“簇”，假定每个“簇”已分配一个惟一簇号l，1lk，且传感器节点通过飞机分批投放后，每个簇中的传感器节点构成一个连通图，且整个传感器网络构成一个连通图。依据上述假定，图1给出了一个具体的基于簇部署的传感器网络分布模型。对于投放k批总共N 节点构成k层超立方体（hierarchical hypercube）H(k,u,m,v,n)模型方法如下。1) 每N/k个节点连接成一个n维超立方体：在每个n维超立方体中，各节点按i1i2in进行编号（称为簇内超立方体节点编号）,其中0i1,i2,inv-1，v=，为向上取整符号；于是共得到k个这样的n维超立方体。将这k个n维超立方体按j1j2jm进行编号（称为簇间超立方体节点编号），其中0j1,j2,jmu-1，u=。将得到的这k个n维超立方体内的节点按如下方法连接成m维超立方体：在得到的这k个n维超立方体中，将具有相同簇内超立方体节点编号的节点连接成一个m维超立方体。H(k,u,m,v,n)模型中的节点编码：H(k,u,m,v,n)模型中的每个节点编码包含2部分（i, j），其中i为簇内超立方体节点编号, i=i1i2in，其中0i1,i2,inv-1；j为簇间超立方体节点编号, j=j1j2jm，其中0j1,j2,jmu-1。传感器网络中的k个簇可映射成H(k,u,m,v,n) 模型中的k层超立方体，每个簇中的传感器节点可按H(k,u,m,v,n) 模型每层中的超立方体节点编号，然后k个簇中的所有节点再按照簇间超立方体节点编号。这样，整个传感器网络将映射成一个H(k,u,m, v,n) 模型。图1 基于簇部署的传感器网络分布模型2.3 基于H(k,u,m,v,n)模型的对偶密钥预置算法基于H(k,u,m,v,n)模型的对偶密钥预置算法主要包括以下3个过程：1) 多项式密钥池的生成与密钥预置；2) 直接对偶密钥发现；3) 路径对偶密钥发现。在多项式密钥池的生成与密钥预置时，从密钥设置机随机生成度数为t的二元多项式f(x,y)= ，使得f(x,y)= f(y,x)，其中x，y是H(k,u,m,v,n)的如前所述的节点编号。直接对偶密钥的发现是通过判断节点A(i1i2in，j1j2jm)和节点B (i1i2in，j1j2jm)之间的距离d= d1+ d2，其中d1=dh(i1i2in, i1i2in)，和d2=dh(j1j2jm, j1j2jm)，如果d=1（d1=0，d2=1或d1=1,d2=0），则节点A，B之间一定存在直接对偶密钥8。若d1，则节点A，B之间一定存在密钥路径8。3 算法性能分析比较3.1 攻击2个特定传感器节点之间的对偶密钥1) 假定入侵者想攻击2个特定传感器节点u,v，且u,v均不妥协，而入侵者想破解它们之间的对偶密钥。a) 若u,v之间可以建立直接对偶密钥，则入侵者惟一的办法就是设法破解u,v之间的对偶密钥，即破解u,v之间的共同的二元多项式f(x,y)。由于二元多项式f(x,y)的度数为t，因此，入侵者需要至少妥协t+1个具有f(x,y)分量的传感器节点。b) 若u,v之间通过中间节点建立间接对偶密钥，则入侵者需要至少妥协一个中间节点，或者破解一个u,v之间的共同的二元多项式f(x,y)。但即便入侵者获得成功，u,v还可以通过选择替代路径重建它们之间对偶密钥。2) 假定入侵者想攻击两个特定传感器节点u,v，且u,v均不妥协，而入侵者想阻止它们之间建立对偶密钥，则入侵者需要破解u或者v的所有m+n个二元多项式。由于任意二元多项式的度数均为t，因此，入侵者需要至少妥协t+1个具有某个二元多项式分量的传感器节点才能破解该二元多项式。因此入侵者需要至少妥协(m+n)(t+1)个具有传感器节点才能阻止u,v之间建立对偶密钥。3.2 攻击整个网络假定攻击者已经知道了传感器节点中的二元多项式分布情况，则其可以利用逐个妥协二元多项式池中的二元多项式来系统地攻击整个网络。假定攻击者已经妥协的二元多项式的比率为pc，则可能有N=pc(m+n)个传感器节点包含至少一个妥协二元多项式的分量；而在剩余的N- N个传感器节点均不包含妥协二元多项式的分量，因此，剩余的N-N个传感器节点之间可以利用任何二元多项式的分量来建立直接对偶密钥，只是在其建立间接对偶密钥时需要进行对偶密钥重建，以避开在密钥路径的中间节点之间使用妥协二元多项式的分量作为两个中间节点之间的直接对偶密钥。假定传感器网络的规模为N=10 000，图2给出了基于不同H(k,u,m,v,n) 模型分布的传感器网络中包含至少一个妥协二元多项式的分量的传感器节点数量与pc的对比数据。图2 基于不同H(k,u,m,v,n) 模型分布的网络中受影响的节点数与pc的对比由图2可知，当传感器网络规模一定时，传感器网络中受影响的节点数量随着妥协节点数量的增加而增大。定理1 假设传感器网络的总节点数为N，攻击者已经妥协的二元多项式的比率为pc，则当uv时，基于超立方体模型H(v,p)的密钥预置机制11的受影响的传感器节点数量，大于基于H(k,u,m,v,n)模型的新型密钥预置机制的受影响的传感器节点数量。证明 基于篇幅原因，证明过程略。假定传感器网络的规模为N=10 000，图3给出了基于H(9,3,2,2,n) 模型、基于超立方体模型H(2,p)分布的传感器网络中包含至少一个妥协二元多项式的分量的传感器节点数量与pc的对比数据。由图3可知，定理1的结论成立，且当传感器网络规模一定时，传感器网络中受影响的节点数量随着妥协节点数量的增加而增大。图3 基于H(9,3,2,2,n)，H(2,p)分布的网络中受影响的节点数与pc的对比在实际应用中，由于传感器节点通过飞机投放，在基于H(k,u,m,v,n)模型进行密钥预置阶段预先设置好的H(k,u,m,v,n)模型将被破坏，在逻辑空间H(k,u,m,v,n)上相邻的节点，在实际部署的传感器网络中可能不相邻，即无法直接进行通信。因此，在实际的传感器网络分布中，距离为t的任意节点A和节点B之间往往需要通过多于t-1个中间节点来建立对偶密钥路径。4 对偶密钥动态路径建立机制与算法在基于H(k,u,m,v,n)模型进行密钥预置阶段预先设置好的H(k,u,m,v,n)模型将受到破坏时，在逻辑空间H(k,u,m,v,n)上相邻的节点，在实际部署的传感器网络中可能不相邻。因此，完全基于逻辑空间H(k,u,m,v,n)的构造特点来建立路由将可能导致路由的开销增加过大。考虑到传感器节点具有资源限制的特点，从而导致节点易因能耗、妥协、通信半径等原因而失效、不可信或不在通信区域，因此，有必要考虑新的适合传感器网络实际部署中的上述特点的动态路径对偶密钥建立算法。为此，在本节中，我们将提出一种基于局部弱连通性概念与传感器节点的位置信息相节合的新的动态路径对偶密钥建立算法。依据传感器网络的实际部署特点，在同一个簇中，由于节点稠密分布，大部分节点将处于有效通信半径之内，因此在同一簇中的传感器节点将能基本保持在基于H(k,u,m,v,n)模型进行密钥预置阶段预先设置好的H(k,u,m,v,n)模型结构，因此，在同一簇中的传感器节点之间的路径对偶密钥建立过程中，算法可依据逻辑空间H(k,u,m,v,n)的特性进行实际物理空间中路由的部署。考虑到传感器节点具有的易失效、不可信或不在通信区域等情形，针对在同一簇中的传感器节点之间的路径对偶密钥建立过程，算法将主要基于局部弱连通性概念进行实际路径对偶密钥的建立路由。而在簇间，则情形正好相反，只要少部分节点能进行直接通信，而且，传感器网络实际部署后，对于逻辑上相邻的2个簇或2个节点，也将无法保证其能在实际物理空间中也能相邻或直接进行通信，因此，在基于H(k,u,m,v,n)模型进行密钥预置阶段预先设置好的H(k,u,m,v,n)模型将基本被破坏，此时，若仍然依据逻辑空间H(k,u,m,v,n)的特性进行部署实际物理空间中的路由时，将大大增加路径对偶密钥的建立开销。为此，针对在不同簇间的传感器节点之间的路径对偶密钥建立过程，算法将主要基于传感器节点的位置信息进行实际路径对偶密钥的建立路由。在给出具体算法之前，本节首先对H(k,u,m,v,n)模型的高容错性进行分析，给出局部弱连通性概念的相关定义与性质分析。4.1 局部弱连通性定义4 n-维超立方体H(v,n)中2个节点A、B是相邻的，当且仅当两个节点A、B的编码对应的字符串恰好有一位互异。定义5 n-维超/子立方体H(v,n)的任意节点A为可达的，当且仅当该节点A是非故障的，且A为非n-孤立的；n-维超立方体H(v,n)的任意节点A称为n-孤立的，当且仅当该节点A的所有与H(v,n)中非故障节点之间的链路均为故障的。n-维超/子立方体H(v,n)的任意节点A为q-可达的，当且仅当该节点A的第q(1qn)个维度上的所有u个邻节点及其之间的链路均为非故障的。定义6 （k-维局部弱连通性）：如果n-维超立方体H(v,n)中每个k-维子立方体H(v,k)（k1）中所有可达节点构成一个连通图且存在H(v,k)中的某个节点A，使得节点A为q-可达的，则称H(v,n)为k-维局部弱连通的。定义7 （任意局部弱连通性）：如果n-维超立方体H(v,n)对任意一个k-维子立方体H(v,k)（k1），存在一个包含H(v,k)的h-维子立方体H(v,h)（hk），且H(v,h)是h-维局部弱连通的，则称H(v,n)为任意局部弱连通的。定义8 对任意给定的长度为n-k的字符串，其对应H(v,n)中一个具有uk个节点的k-维子立方体H(v,k)，H(v,k)中的节点的字符串具有b1 b2bn-k*的形式，其中符号*可任意取值0,u-1。满足上述定义的两类局部弱连通性条件的H(v,n)模型具有以下良好性质。定理2 满足k-维局部弱连通条件的n-维超立方体H(v,n)中所有可达节点构成一个连通图。证明 基于篇幅原因，证明过程略。定理3 满足任意局部弱连通性条件的n-维超立方体H(v,n)中所有可达节点构成一个连通图。证明 基于篇幅原因，证明过程略。由定理2与定理3可知，满足定义的2个局部弱连通性条件的超立方体的所有可达节点之间一定是全局连通的。4.2 基于两类局部弱连通性条件的簇内密钥路径动态建立算法结合传感器网络在同一个簇中节点稠密分布，且在同一簇中的传感器节点将能基本保持在基于H(k,u,m,v,n)模型进行密钥预置阶段预先设置好的H(k,u,m,v,n)模型结构的特点，易知在同一簇中的传感器节点构成的传感器子网模型H(v,n)同样具有超乎寻常的健壮性，即当有大量传感器节点失效或妥协时，整个子网模型H(v,n)仍可保持全局连通。因此，当将传感器子网中的失效或妥协节点映射成H(v,n)模型中的故障节点，而将传感器子网中的安全正常的节点映射成H(v,n)模型中的可达节点时，则显然可以假定同一簇中的传感器节点所构成的H(v,n)模型能满足上述定义的两类局部弱连通性条件。基于上述假定，我们已将实际部署的整个传感器网络映射成了H(k,u,m,v,n)模型，而将其中的每个簇内的传感器子网映射成了H(v,n)模型，因此，我们可将传感器网络等同于逻辑H(k,u,m,v,n)模型，而将每个簇内的传感器子网等同于逻辑H(v,n)模型。在接下来的章节中，将整个传感器网络简称为H(k,u,m,v,n)，而将每个簇内的传感器子网简称为H(v,n)。首先，基于满足k-维局部弱连通性条件的n-维超立方体H(v,n)模型，给出传感器网络中的第一类路径对偶密钥建立算法（算法1），然后基于满足任意局部弱连通性条件的n-维超立方体H(v,n)模型，给出传感器网络中的第二类路径对偶密钥建立算法（算法2）。基于满足k-维局部弱连通性条件的n-维超立方体H(v,n)模型的传感器网络中的第一类路径对偶密钥建立算法如下。算法1 基于满足k-维局部弱连通性条件的n-维超立方体H(v,n)模型的传感器子网中的第一类路径对偶密钥建立算法。输入：具有妥协或失效节点与失效链路的传感器子网H(v,n)及其两个可达节点A(a1an，a1am)、B(b1bn，b1bm)。输出：传感器网络H(v,n)中由A到B的一条正确密钥路径。1) 得到节点A、B的字符串的前半部分：Aa1an，B b1bn，其中aj、bj0,v-1；/*由定义5中同构性质，不妨设B所在的k-维子立方体具有b1bn-k *形式。*/2) 初始化路径P：P A；初始化临时字符串C：C= c1cn A；3) FOR(j=1；jn；j+)IF（ajbj） 依据定理1，通过相邻k-维子立方体寻找一对连通的可达节点：C= c1cj-1 cj cj+1cn-kcn、b1bj-1 bj xj+1xn-kxn，其中ct= bt（t1,j）； 扩展路径P：将节点b1bj-1 aj aj+1an-k an-k+1an到节点b1bj-1 bj xj+1xn-kxn的路径加入P中； C b1bj-1 bj xj+1xn-kxn；/*经过上述步骤则构造了一条从A= a1an到可达节点b1bj-1 bj xj+1xn-kxn的一条正确密钥路径。*/4) 扩展路径P：在k-维子立方体b1bn-k *中将从节点b1bn-k xn-k+1xn到目的节点B= b1bn的密钥路径加入到P中。算法终止，于是找到了一条由A到B的正确密钥路径P。接下来基于定义7和定理2，给出基于满足任意局部弱连通性条件的n-维超立方体H(v,n)模型的传感器网络中的第二类路径对偶密钥建立算法如下。算法2 基于满足任意局部弱连通性条件的n-维超立方体H(v,n)模型的传感器子网中的第二类路径对偶密钥建立算法。输入：具有妥协或失效节点与失效链路的传感器子网H(v, n)及其两个可达节点A、B。输出：传感器网络H(v,n)中由A到B的一条正确密钥路径。1) 得到节点A、B的编码字符串的前半部分：Aa1an，B b1bn，其中aj、bj0,v-1；2) 初始化路径P：P A；初始化临时字符串C：C= c1cn A；3) FOR(i=1；In；i+) IF（ajbj） FOR（k=1；kn-i；k+） IF（依据定理2，通过相邻k-维子立方体可以找到一对连通的可达节点：C= c1cj-1 cj cj+1cn-kcn、b1bj-1 bj xj+1xn-kxn，其中ct= bt（t1,j）扩展路径P：将节点b1bj-1 aj aj+1an-k an-k+1到节点b1bj-1 bj xj+1xn-kxn的路径加入P中；C b1bj-1 bj xj+1xn-kxn； 3）BREAK；IF（k n-i）WHILE（kn）IF（在k-维子立方体c1 c2cn-k *中不存在一条从C到B的正确密钥路径）k+；IF（ k n）算法终止，H(u,n)不是任意局部弱连通的，未能找到一条从A到B的正确密钥路径；ELSE 在k-维子立方体c1 c2cn-k *中扩展路径P从C到B； 4) 算法终止，找到了一条从A到B的正确密钥路径P。基于前叙描述可知，以上算法1和算法2主要用于同一簇中的传感器节点之间的路径密钥建立。由于传感器节点在同一簇中稠密分布，因此，可以假定同一簇中的传感器节点所构成的逻辑超立方体模型满足2、3或4-维局部弱连通性条件，以有效降低算法1和算法2的时间复杂度。下面分析上述假定的合理性。假定某个簇中的传感器节点共有2 000个，其构成的逻辑超立方体模型H(v,n)中，取v=3，则n=7。若假定其满足3-维局部弱连通性条件（即任意33=27个节点构成的包含若干个失效或妥协节点的逻辑子立方体中的所有可达节点构成一个连通图，这个假定显然也是合理的），则算法1和算法2的时间复杂度将分别为135、216。对规模为2 000个节点的传感器网络，在最坏的情形下，只需要135或216个hops即可找到一条从源节点到目的节点之间的正确密钥路径。4.3 基于H(k,u,m,v,n)模型的簇间密钥路径动态建立算法基于前一节的算法1和算法2，结合传感器网络中节点的位置信息，可以给出基于H(k,u,m,v,n)模型的密钥路径动态建立算法如下。算法3：基于H(k,u,m,v,n)模型的密钥路径动态建立算法。输入：传感器网络H(k,u,m,v,n)及其两个可达节点A(a1an，a1am)、B(b1bn，b1bm)。假定atbt, t1,s；at=bt, ts。输出：传感器网络H(k,m,n)中由A到B的一条正确密钥路径。1) 得到节点A、B的编码字符串：A(a1an，a1am)，B (b1bn，b1bm)，其中aj、bj0,u-1, aj、bj0,v-1；2) 若a1am = b1bm, 则按4.2节中的算法1或算法2进行密钥路径的寻径；3) 否则，首先利用按4.2节中的算法1或算法2进行密钥路径的寻径，找到节点A(a1an，a1am)到节点C(b1bn，a1am)之间的密钥路径；然后，令I0=C(b1bn，a1am)，I1=(b1bn，b1 a2am)，Is=B(b1bn，b1 b2bs as+1am)基于传感器节点位置信息11的路由算法，分别找到从节点It到It+1之间的一条正确路由。4) 算法结束。若存在这样的一条正确密钥路由，则节点A与节点B之间可用建立的路由来建立密钥路径；否则节点A与节点B之间的密钥路径建立失败，节点A将在以后再次尝试建立与节点B之间的密钥路径。5 算法分析为了验证算法性能，本节进行了仿真实验，实验环境为：在一个800800的区域内，随机分布1 0005 000个传感器节点，假定每个节点的传感半径为50，针对每种不同的网络分布，进行连续100次实验，每次实验随机设定一些节点和一些链路为故障，随机选择源和目标节点，得到不同的网络进行实验，实验结果中的相关数据取定为100次实验结果的均值。图4给出了基于H(5,u,2,v,4)模型的密钥路径动态建立算法，与文献11中基于H(v,p)模型的密钥路径建立算法的密钥成功建立概率对比数据。图4 基于H(5,u,2,v,4)，H(v,p) 模型的密钥成功建立概率对比由图4可知，基于H(5,u,2,v,4)模型的密钥路径动态建立算法，其密钥成功建立概率要远高于文献11中基于H(v,p)模型的密钥路径建立算法，其原因在文献11中的算法要求任意节点之间能直接通信，而当实验环境不满足要求时，文献11中算法的性能将无法保障。另外，在基于H(5,u,2,v,4)模型的密钥路径动态建立算法中，采用算法2的动态建立算法，其密钥成功建立概率要稍高于算法1。图5进一步给出基于H(5,u,2,v,4)模型的密钥路径动态建立算法的时间复杂度实验数据。图5 基于H(5,u,2,v,4)，H(v,p) 模型的密钥路径动态建立法时间复杂度的对比由图5可知，在基于H(5,u,2,v,4)模型的密钥路径动态建立算法中，采用算法2的动态建立算法，其密钥成功建立时间要稍高于算法1。总体上，基于H(5,u,2,v,4)模型的密钥路径动态建立算法具有较小的时间复杂度。6 结束语根据传感器在簇间和簇内的不同分布特性，导出了基于局部弱连通性概念的簇内动态密钥路径和基于位置信息的簇间动态密钥路径的两类算法。理论分析与计算机仿真数据表明，新的动态密钥路径算法的可靠性和开销均有良好的性能，是一种适合传感器网络分簇分布特点的高效动态密钥路径的建立算法。参考文献：1POTTIE G, KAISER W. Wireless sensor networks J. Communications of the ACM, 2000, 43(5): 5158.2ESTRIN D, GOVINDAN R, HEIDEMAN J, et al. Next century challenges: scalable coordination in sensor networksA. Proc of the 5th annual ACM/IEEE international conference on Mobile computing and networkingC. New York, 1999. 263-270.3AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networksJ. IEEE Communications Magazine, 2002, 40(11): 102-114.4EESCHNAURE L, GLIGOR V D. A key-management scheme for distributed sensor networksA. Proc of the 9th ACM conference on computer and communication securityC. New York, 2002.41-47.5CHAN H, OERRIG A, SONG D. Random key predistribution schemes for sensor networksA. Proc of the IEEE Symposium on Research in