论文研究-梯度算子对反向合成梯度算法的影响.pdf

所需积分/C币:5 2019-09-08 01:32:33 1.97MB .PDF

信任凭证的存储策略是信任管理领域中广受关注的一个研究内容,它直接影响到凭证的收集、撤销和凭证链的构造等问题。针对RT0信任管理模型,提出了一种基于2D-CAN网络(2-dimensions Content Addressable Network)的信任凭证存储策略,通过<发行者,主体>的二维信息,将信任凭证映射存储到二维CAN协议的对应节点上,从而实现凭证的分布式存储,并提供灵活地查询。同时,研究提出了一个基于凭证图双向生长的信任链发现算法。实验表明,基于2D-CAN协议的凭证存储算法,能达到较高的鲁棒性和查询效率。
502007,43(29) Computer Engineering and Applications计算机工程与应用 (x,ya)和(xn,y)分别表示该节点所包含的CAN子空间的左下的空间,以逆向查找为例) 角坐标和右上角坐标。 输入:Key:基于一维信息的查询关键字(k,*) 前向查找中,主体D需要收集的所有凭证,分布地存储于 n:算法阶数,树的最大分叉数 节点集汎中: 输出:符合查询条件的凭证集合 况={n1(<x,y>,<xm,ym)yh≤H(D)<y} 队列q1,用于存储待查询线形区间,初始化只有一个元素[0,M 逆向查找中,发行者需要收集的所有凭证,分布地存储 队列q2,用于存储新产生线形区间,初始化为空 于节点集汎中: While((q1不为空) 况={n(<x,y>,<xm,y>)x≤H(D)<xa} 对q1中的每一个线形区间L={a,b 因此,基于单维信息的凭证的查找问题,实质上是对上述 发送n个定位请求,分别为key=(k,e), 节点集进行遍历的问题,显然在CAN网络中,该节点集可以按 照查询维的坐标进行排序,序号上相邻的节点,也是CAN空间 其中e=/x(b-+1m)-1j=0,1,,n b 中的邻居节点。设满足条件的节点数为M(M<<N) (k,en)请求最终定位到节点m,n在查询维上的管理范围 (1)行查找:实体D通过CAN路由机制定位(0,H(D)为(a,b); 坐标于节点n1,n1返回所有存储于本地的凭证和该节点涵盖空 if(b≥em) 间的查询维坐标上限U;然后继续定位(U+1,H(D))坐标,循环 返回n节点中所有符合(k,*)条件的凭证; 执行,直到U=N中止。串行算法只需要发送M个查询请求即 中止该分支的查找;} 可得到所有满足(*,主体)形式的信任凭证,网络通信开销比较 低,但是因为采取串行操作,每次查询都依赖于前一次查询的 返回n节点中所有符合(h,*)条件的凭证; 结果,查询的总时间过长。 产生子空间[b+1,e-1],保存到队列q2; 2)并行查找:实体D同时并行发出N个查询请求,分别 定位(n,H(D),其中n=0,1,…,N-1,对应的CAN节点并行做 清空q1; g1=g2 出响应:返回该凭证或者回应无此凭证。并行查找充分利用了 清空q2; 对等网络节点的并行计算能力,总体查询时间短,实时性较高 但是并行的N个查洵请求,也带了较高的网络通信开销。尤其4.2信任凭证链的发现 在实际的CAN系统中,为了保证哈希映射的唯一性和均匀性, 釆用分布式哈希表的方法,实现信任凭证的分布存储和定 N一般取值很大,由此会带来的极为高昂的通信代价 位,能为凭证链的发现提供灵活的凭证查询手段,有利于设计 (3)优化查找:在二维CAN网络中,基于单维信息(如(* 高效率的凭证链查找算法。文献[l指岀,在采用深度优先的策 H(D))或者(H(A),*)的查询,表现为对一维有序空间上的所 略时候,在某些情况下,单向查找算法的效率远低于双向查找 有子空间的遍历,而所有子空间都对应着一个参与节点。提出 算法,这主要表现在前者形成的凭证图尺寸远大于后者。因此, 了一种基于n叉树的优化算法,算法执行过程类似于一颗n叉凭证的存储策略必须能够支持灵活的双向的凭证链查找。在双 树的生成树的高度为总的查询步数。在每一步查询中,对剩余 向查询中,根据用户所发出的对某一角色的申请,从两个方向 的所有连续空间分别进行n等分,对每一个等分区间发送一个 用户、角色)同时进行凭证链的查找,分别构成前向和后项凭 查询请求。然后根据响应节点在查询维上的包含范围,决定分 证图。当两个方向的凭证图连通即表示凭证链发现成功,而前、 裂该等分区域,或者终止该次查询。n叉树的前序遍历就可以 后凭证图的并集就是凭证链发现所需要的最终凭证图。在查找 得到该一维空间上的节点序列(按分段地址排序)。在例1中 过程中,为了最终能够构造较小的凭证图,根据贪婪算法思想, 查找所有由 project发行的信任凭证,即在CAN网络中查找所 每一步都从前、后凭证图中选择广度较小一个作为查找方向。 有索引形式为(H( project),*)=(824,*)的凭证,CAN空间为1基于以上思想,同时考虑凭证链非线性结构和存在凭证回路的 024×1024,设n=2,首先并发执行两个定位操作Deph=1:Q11特点,本文提出了一个面向最小凭证图的,基于凭证图双向生 (key=(824,0)和Q12(key=(824,512),Q1定位到节点E,Q12 定位到节点A,A节点的上边界不大于Q12的上界,不需要进长的凭证链发现算法。 定义1,对于角色表达式e,定义: 一步查找;节点E产生新的查寻范围[256,511,.并发执行两个 LAJ,e=A 定位操作 Depth=2:Q21和Q22,都定位到节点C,不需要进 步查找(图2)。 asele 4},e=A.r1,r2 算法1基于n叉树的凭证查找算法(设二维CAN为NN base(∪bse()U…Ubse(G),ein/n…∩/ [0,1023 定义2逆向凭证图G(e,C)是一个有向图G(Vr,E,),e0是 Ql(key=(824,0) Q12(kcy=(824,512) 初始角色,C为当前已经获得的凭证集合,V,是节点集合,E,是 V,上满足三条闭包属性最小有向边集。 [0,255] V=Vo∪va∪Va, Q21(key=(824,256 [512,1023 Ve=(∪a.r,e}J{eol是Vc的基本子集 返回先证c3(O Q22(key=(824,383)) 256,511 ∪.n是v的连接扩展子集 图2基于2叉树的优化查询 姜志宏,王晖,孙晓,等:基于2D-CAN协议的信任凭证存储和查找算法 ∪G,…,f,是V的交集扩展子集 利用算法1得到凭证集C=∪(∪{k的主体为D); n∈S2(G) De base(n) 定义3前向凭证图G(D,C)是一个有向图G(V,E),D for(S(G)中的所有节点e) 是初始实体,C为当前已经获得的凭证集合,V是图的节点集 if(e=A r)( 合,E是v上满足三条闭包属性的最小有向边集。 V=V∪{A}标示为已处理接点 设置连接监控器,对后续处理进行监控:{ V=vUv If(A∈G,A到节点B.r存在路径 VG=(∪Mr,e∪D是v的基本子集 V=V∪{B.r,r,E=E∪{A.r→B.r.r; For(C中具有e←A形式的每一个凭证) =∪}是v的连接扩展子集 V=vU{e},E=E∪{4→e};} eVo∩e=A.r For(C中具有e'←e形式的每一个凭证) 定义4逆向查找算法中,凭证图G;(eo,C)的逆向待处理 V=v∪e,E=EJ{ee 节点集S(G)=ele没有经过查找算法处理,e∈V},逆向连通 If(e为非交集角色) 节点集S(G)={e存在从e到eo的路径,e∈V}。 For(C中具有e← enfnf2n…m形式的每一个凭证 定义5前向查找算法中,凭证图G(Do,C)的前向待处理 V=VU|enf∩f∩…∩f,标示为已处理节点 节点集S(G)=cle没有经过查找算法处理,e∈V},前向连通 V=V∪e},标示为已处理节点; E=EU(enf∩fn…∩f)→e 节点集S(G)=(l存在从D到e的路径,e∈V 设置连接监控器,对后续处理进行监控: 其中,连通节点集主要用于判断凭证图的发现,待处理节 If(n∈G,n到e和f,(i=1,2,…,k)都存在路径 点集用于减少每次搜索的广度,以及检测凭证回路。 E=EU{n(cnf∩f0…∩f); 算法2基于凭证图双向生长的凭证链发现算法 标示e的所有直接后继节点为未处理节点;} 输入:实体D和需要求证的从属角色名R / lend for(for(G中具有…) 输出:从实体D到角色R0的凭证链,或者凭证链不存在 /if ∥/ lend for(for(S(G)中的所有…)) 构造逆向证据图G,初始仅包含R0; lend for(else) 构造前向证据图G,初始仅包含 Vend for( while( true ) While(true ) ifS(G)或S(C)为空)返回结果,凭正链不存在 43信任凭证存储的鲁棒性考虑 if(S(G)nS(G))∪(S(G)∩S(G)非空)返回结果,凭证 信任凭证是信任关系构造和推理的关键,而P2P网络的动 链存在}; 态性在很大程度上降低了凭证查询的鲁棒性,例如PP节点的 If(S(G)>=S(G)V选择逆向查找 突然失效会导致信任网络丢失部分凭证,从而影响对应的信任 标记S(G)中所有节点为已处理节点; 关系的建立。为了提高凭证存取的鲁棒性,采用CAN协议的多 利用算法1得到凭证集G=∪∪ck的发行者为l}; 坐标体系来解决这个问题。每一个计算机节点都独立地映射为 h个坐标点,分别加入到CAN网络的k个坐标体系中,同样, for(S(G)中的所有节点e if (e=A r)( 每一个凭证也独立映射为k个坐标点,分别存储在h个坐标系 For(G,中具有Are形式的每一个凭证) 中。因为映射是随机均匀的,同一个凭证就概率均匀地存储在 V=V∪{e},E=E,∪{eAr}; 网络中的k个节点上。实际运行中大部分网络失效都具有随机 if(e=A r r2)( 性和局部关联性,采用基于多坐标系的P2P存储和查找策略, V=V∪{A4,r},标示A.r为已处理节点; 能将信任链构造的容错性和鲁棒性大大提高。 设置连接监控器,对后续处理进行监控:{ If(发现有实体D到Ar路径) 5实验和分析 V=V∪{D.r2},E=E,∪{D2+A.r,r2};} 论文采用C语言实现了一个模拟器,模拟实现了一个采用 for(C中具有Ane形式的每一个凭证 二维CAN网络管理的信任凭证分发与查询系统。实验运行平 V=VU{e},E=E,∪{e→+A.r};} 台:CPU, Intel p42.0G,内存512M,操作系统是 Windows Xp。 if(ef∩f∩…∩f) 通过模拟器,分别模拟了凭证<发行者,主体>到CAN空间的映 V=V∪V、,…月,都标记为已处理结点; 射和分布算法,基于多叉树的凭证查找算法,基于凭证图双向 设置交集监控器,对后续处理进行监控:{ 生长的凭证链发现算法,还对P2P动态性对凭证链发现算法鲁 If(n∈V,n到f/,…都存在路径) 棒性的影响进行了分析。 E=E,∪{nY∩f2∩…∩f};} for(C中具有←e形式的每一个凭证,=1,2,…,k){ 5.1凭证存储的负载分析 V=V∪{e},E,=E∪{e/},;} 实验生成一个包含2000个节点的二维CAN网络,然后 J/for 随机选择节点作为发行者,向网络中插入信任凭证。考虑到信 任网络的出度具有 power--aw特性,在插入凭证过程中,本文 Else{选择前向查询 使用 power-law网络的生成算法PLOD( Power law out-De 标记S(G)中所有节点为已处理节点 gree),用于生成符合 power-law规则的10000到150000个 522007,43(29) Computer Engineering and Applications计算机工程与应用 信任凭证。图3是对信任凭证存储的三种方法的负载比较。其 30 中可以看出,就负载的绝对均衡性而言,将所有凭证都存储于 发行者节点的方法效果最差,将所有凭证都存储于主体节点的 20 方法效果最好,这可以归结于信任凭证网络的 power-law特 5 forward 性。基于二维信息的存储策略效果居于二者之间,略次于存储 algorithm 二10 于主体节点的方法,但是本文提出的这种存储策略能提供更大 backward algorithm 灵活性,便于根据需要选择不同的查找方向。 bidirect I亡「 1400 020406080100120140160 Distribute by Issuer number of credentials(thousand 图5凭证图的尺寸大小vs.凭证数量 Distribute 800 by subject (I, 5.4发现算法的鲁棒性验证 CAN网络的动态性对凭证链发现的成功率也产生影响。 400 考察了CAN网络中节点失效率和凭证图构造成功率之间的关 系,并且通过实现多坐标系的改进CAN来降低节点失效的影 1000 5002000 响。考虑节点失效为完全独立事件,对网络中已存在的1000 equence number of node 个凭证链,分别模拟了在失效率为0.01,0.02,0.05,0.1,0.2,0.3, 图3凭证存储的负载比较 0.4,0.5时,坐标系数目为1,2,3的h坐标系,比较其发现成功 5.,2基于n叉树的信任凭证查找算法效率分析 率,结果如图6。实验表明,使用多坐标系CAN网络,能增强凭 如前所述,基于单维信息(如发行者或者主体),串行查找链发现的鲁棒性和容错性。但是多坐标系CAN网络也增加 算法需要的查找步数seps≈lnN(N为CAN网络节点总数,并了存储冗余和附加的通信流量,在要求不是很严格的环境下 采用2-3个坐标系,在节点失效率达到50%的情况下,凭证链 行查找算法则需要发送N个查询请求,二者在实际环境中显 然都是没有现实意义的。实现了基于n叉树的信任凭证优化查发现成功率仍然能达到095以上。 1.0冷 找算法,以査找树的分叉数n作为参数,比较了不同n取值下 二 a0.9- 算法成功查找到所有凭证所需要的查找步数和总的查找次数。 比较结果见图4,显然当n取值为2-4的时候,算法同时具有 E0.8 比较低的运行时间(查找步数)和网络流量(查找次数)。为了便 0.7 于实现,在后面的实验中取值n=2 s0.6 40+ query depth 1000 60.5 Coordinates=2- Coordinates= l uery 0.4 -800 三25 600 Failure possibility of nodes 20 图6节点失效率vs.凭证图构造成功率 15 200 6结论和将来的工作 信任管理技术是实现分布环境下的存取控制的一个研究 0 2468101214161820 热点,其主要思想是通过特定的凭证集合,推理出应用所需要 (n)parameter of algorithm 的信任关系。其中,信任凭证的存储策略是广受关注的一个研 图4基于n叉树的凭证查找算法分析 究内容,并且直接影响到凭证的收集、撤销和凭证链发现等问 53信任凭证链的发现算法分析 题。本文针对RT0信任管理模型,提出了一种基于2D-CAN网 络的信任凭证存储策略,通过<发行者,主体>的二维信息,将信 考察三种凭证链的发现算法:对全部凭证存储于发行者节 任凭证映射存储到2D-CAN网络中,从而实现了凭证的分布 点采用的逆向算法,对全部凭证存储于主体节点采用的前向算式存储和灵活地查询。并在此基础上,研究了基于凭证图双向 法,提出的基于凭证图双向生长的发现算法。实验比较比较了生长的信任链发现算法。实验表明本文提出的凭证存储算法 在节点总数不变时,网络中凭证总数和凭证图的尺寸大小之间能达到较高的鲁棒性和查询效率。进一步的工作包括在此存储 的关系,比较结果如图5。随着网络中凭证数增加前向算法和策略上的信任凭证吊销研究,异构的P2P环境中的负载均衡问 后向算法的凭证图大小急剧增长,而双向算法构造的凭证图尺题,以及对包含非单调性凭证的信任关系构造和推理。 寸仅仅略微增长,远远小于前二者。可见分布式环境中双向算(收稿日期:2007年5月) 法带来的网络流量和运算效率,明显优于单向查找。当网络中 凭证数增加时,给凭证图大小带来了两种因素的影响:一个是参考文献: 单个节点所存储的凭证数增加进而使得凭证图尺寸增加,另 [1 Li N H, Winsborough W H, Mitchell J C Distributed credential 个是网络直径减小,查找所需步数减少,从而使得凭证图尺寸 chain discovery in trust management[J]Journal of Computer Secu- 减小。两个因素的综合影响,使得图中的凭证图尺寸曲线产生 rity,2003,11(1):35-86 了起伏,而不是单调的递增。 下转89页)

...展开详情
试读 5P 论文研究-梯度算子对反向合成梯度算法的影响.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-梯度算子对反向合成梯度算法的影响.pdf 5积分/C币 立即下载
    1/5
    论文研究-梯度算子对反向合成梯度算法的影响.pdf第1页
    论文研究-梯度算子对反向合成梯度算法的影响.pdf第2页

    试读已结束,剩余3页未读...

    5积分/C币 立即下载 >