首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 156 毫秒
1.
目前重路由匿名通信系统有着广泛的应用,但也容易遭受各种攻击.基于重路由的匿名通信系统,如Onion Routing,Hordes,Tarzan以及MorphMix等,采用重路由机制在应用层转发数据,使实体之间的通信以间接的方式进行,从而有效地隐藏通信实体的身份信息,如主机的IP地址等.在基于路径的重路由匿名通信系统的基础上,提出了前驱攻击模型,并对该模型进行了理论研究和分析,其结果表明,在设计重路由匿名通信系统时,为了降低前驱攻击的成功率,要同时考虑选择发起者的概率、转发概率和所构建路径数目.  相似文献   

2.
杨智应  朱洪  宋建涛 《软件学报》2004,15(5):650-659
算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ2≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og2(n)+3log2(1/σ)+log2log2n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og2n+3log2(1/σ)+4√2+log2n+log2(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n2)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og2n+3log2(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.  相似文献   

3.
数据仓库系统中层次式Cube存储结构   总被引:11,自引:0,他引:11       下载免费PDF全文
高宏  李建中  李金宝 《软件学报》2003,14(7):1258-1266
区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(logdn),综合性能为O((logn)2d)(使用CqCu模型)或O(K(logn)d)(使用Cqnq+Cunu模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.  相似文献   

4.
Crowds系统中基于递减转发概率的路长控制策略   总被引:3,自引:3,他引:3  
Crowds匿名浏览系统中,基于固定的转发概率建立重路由路径用以在主机间转发用户请求,从而隐藏通信的发起者.在系统所采用的转发概率较大的情况下,产生的重路由路径过长,导致转发请求的延时以及系统中成员负载等性能开销过大.文中提出基于递减转发概率的路长控制策略,用以有效控制重路由路径长度,提高传输性能.首先证明在前趋攻击下,恶意成员攻破匿名保护所需的时间轮数,主要由系统中恶意成员数目所决定,受重路由路径长度的影响较小.基于该分析结果,提出了基于递减转发概率的路长控制策略.仿真结果表明,新策略能缩短重路由路径的长度,从而在保持系统匿名保护能力的前提下,有效提升系统的性能.  相似文献   

5.
谢民主  陈建二  王建新 《软件学报》2007,18(9):2070-2082
个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2kn2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k1-1)k222h+(k1+1)2h+nk2+mk1)的新算法,其中,k1为一个片断覆盖的最大SNP位点数(不大于n),k2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.  相似文献   

6.
杨奎武 《计算机科学》2016,43(Z6):255-259
提出一种基于基站大功率信号广播的延迟容忍移动传感器网络消息路由机制(High-power Broadcasting based Routing scheme,HBR)。该机制使用两个通信频率f1 和f2,基站以恒定大功率在频率f1上广播已经接收到的消息,网络中传感器节点根据基站广播信息计算自身转发概率并清理冗余消息副本,节点间利用频率f2进行通信。为进一步提升网络性能,HBR优先传输转发阈值(M)小且生存时间短的消息,并合理进行消息队列管理。仿真结果表明,与几种经典的路由机制相比,HBR在消息传输成功率、传输延迟方面有着一定的优势。  相似文献   

7.
在消息传递并行机上的高效的最小生成树算法   总被引:5,自引:0,他引:5  
王光荣  顾乃杰 《软件学报》2000,11(7):889-898
基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n2/p)和O((tsp+twn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.  相似文献   

8.
王晓峰  许道云 《软件学报》2016,27(11):2712-2724
置信传播算法求解RBk,n,α,rc,p)模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RBk,n,α,rc,p)模型中,取k=2,α>(1/k),rc>0均为常数,且满足ke-(α/(rc))≥1.证明了如果p∈(0,n-2α),则置信传播算法在RBk,n,α,rc,p)模型产生的随机实例集上高概率收敛.最后,在RBk,n,α,rc,p)模型上选取了几组不同的数据进行数值模拟,实验结果表明该结论有效.当问题规模n增大时,在RBk,n,α,rc,p)模型的可满足区域,实验收敛区间趋于一个固定范围,而理论收敛区间逐渐变窄.原因在于,RBk,n,α,rc,p)模型是一个具有增长定义域的随机CSP实例产生模型,不协调赋值的数目与参数p及问题规模n有关.  相似文献   

9.
沈一飞  陈国良  张强锋 《软件学报》2007,18(11):2683-2690
分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn).  相似文献   

10.
背包问题的最优并行算法   总被引:10,自引:2,他引:10  
利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2n/4)1-ε个并行处理机单元,0≤ε≤1,O(2n/2)个存储单元,在O(2n/4(2n/4)ε)时间内求解n维背包问题,算法的成本为O(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.  相似文献   

11.
Crowds is a recently proposed protocol for anonymous communication, which is based on the idea of “blending into a crowd”. Thus, each participant of the crowd gets the benefits of anonymity but also serves as a proxy for other participants. An important measure of the protocol is the participant payload in the system, which is measured by the amount of work a participant needs to pay on serving as a proxy for any communication requested by the participants in the system. In this paper, we derive a precise formula for the participant payload in Crowds, which improves the previous results. Moreover, our result shows the first time that the participant payload in Crowds is entirely independent of the size of the crowd. In consequence, Crowds protocol has a very nice scalability property.  相似文献   

12.
陶颋  孙乐昌 《计算机工程》2008,34(24):121-123
通过分析基于重路由的匿名通信系统模型,提出一种适合节点在环境恶劣、性能不稳定条件下工作的N路冗余重路由算法,对使用该算法的匿名通信系统的可靠性、负载特性和匿名性进行理论推导和分析,结果证明,该算法能满足用户提出的可靠性边界条件,较大地提高重路由路径的可靠性并保证系统的匿名性,但会增加节点负载,减小系统容量。  相似文献   

13.
基于下一跳重路由方式的Crowds匿名通信系统存在较多缺点。提出基于IPv6协议的Crowds系统,解决发送者与最后一跳的秘密共享问题。理论分析和实验结果表明,该系统的抗攻击能力与源路由方式相等,实现了接收者匿名,减少了通信延迟。 分类号 TP393  相似文献   

14.
基于重路由的匿名通信系统研究   总被引:5,自引:1,他引:5  
基于重路由的匿名通信系统主要采用重路由机制来提供匿名保护。论文在分析基于重路由的匿名通信模型的基础上,提出了一种转发概率等比递减的重路由算法,理论分析和计算数据表明这种重路由算法能有效保证匿名性能,使匿名通信路径长度的期望值显著降低,缩短匿名通信的延时,但随着重路由路径重组轮数增加,系统提供的匿名性仍将会降低。  相似文献   

15.
重路由匿名通信系统中基于秘密共享的重路由算法   总被引:4,自引:0,他引:4  
重路由匿名通信系统主要采用重路由机制来提供匿名保护.已有的下一跳重路由方式具有抗攻击能力弱且通信延时大等缺陷.提出基于秘密共享的重路由算法,用于在下一跳路由中实现端到端的加密,从而有效增大恶意成员的攻击难度.理论分析表明,抗攻击能力达到与源路由方式同等水平.并且,由于发送者能有效控制路由长度,因而能保证良好的通信性能.  相似文献   

16.
Crowds匿名浏览系统中可以在不影响匿名度水平的前提下,通过递减转发概率减小重路由路径长度,提高系统性能。提出利用路径长度期望值递减规律确定转发概率递减比例系数的方法,仿真实验表明,新方案可以在保持原有匿名度的基础上,有效减小重路由路径长度,提高Crowds系统的通信性能。  相似文献   

17.
SACS:一种可扩展的匿名通信系统   总被引:2,自引:0,他引:2  
匿名通信的主要目的是隐藏通信双方的身份或通信关系,从而实现网络用户的个人通信隐私及对涉密通信更好的保护.目前匿名系统的研究主要在于提高匿名性能,许多原型系统借助于多个代理的重路由技术、填充包技术和加密技术来达到匿名发送或匿名接收的目的.而当匿名系统真正要被应用于现实网络中时,系统管理方式和管理代价直接会影响到系统的可扩展性.目前的许多匿名原型系统采用集中式管理机制,不能承受大量用户的存在,因此都无法应用于大规模的网络环境中.本文基于Crowds系统,提出了一种新的匿名通信系统SACS的结构与协议描述,引入了分区域管理机制,实现了对系统内成员的分布式管理,有效地降低了匿名系统的管理开销,具有很好的可扩展性.概率分析与测试结果表明新的系统在减少系统的附加管理开销、支持良好扩展性的同时保持了与原Crowds系统相当的匿名性.  相似文献   

18.
结构化P2P覆盖网络提供一个自组织、可升级且容错性能好的合作P2P应用平台.借助于结构化覆盖网络的自组织和结构化特性,本文在结构化P2P覆盖网络基础上提出了一种不需要中心管理节点的重路由匿名通信机制.由于覆盖网络的开放性,本文分析了重路由路径长度的期望值与转发概率的关系以及重路由路径长度的期望值与覆盖网络中恶意成员数量的关系,并且分析了随着重路由路径重组轮数的增加,恶意节点将以更高的概率找到发起者.计算数据表明,采用递减转发概率将使得重路由路径长度的期望值显著降低,因而能保证良好的通信延时.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号