Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2008年 第45卷 第2期    出版日期:2008-02-15
论文
Contagion蠕虫传播仿真分析
王跃武 荆继武 向 继 刘 琦
2008, 45(2):  207-216. 
摘要 ( 285 )   HTML ( 0)   PDF (602KB) ( 365 )  
相关文章 | 计量指标
Contagion蠕虫利用正常业务流量进行传播,不会引起网络流量异常,具有较高的隐蔽性,逐渐成为网络安全的一个重要潜在威胁.为了能够了解Contagion蠕虫传播特性,需要构建一个合适的仿真模型.已有的仿真模型主要面向主动蠕虫,无法对Contagion蠕虫传播所依赖的业务流量进行动态模拟.因此,提出了一个适用于Contagion蠕虫仿真的Web和P2P业务流量动态仿真模型,并通过选择性抽象,克服了数据包级蠕虫仿真的规模限制瓶颈,在通用网络仿真平台上,实现了一个完整的Contagion蠕虫仿真系统.利用该系统,对Contagion蠕虫传播特性进行了仿真分析.结果显示:该仿真系统能够有效地用于Contagion蠕虫传播分析.
基于可连Cell的无线传感器网络拓扑控制算法
金 鑫 熊 焰 李  岳丽华
2008, 45(2):  217-226. 
摘要 ( 240 )   HTML ( 0)   PDF (541KB) ( 319 )  
相关文章 | 计量指标
在无线传感器网络的拓扑控制(TC)中,基于Cell的TC算法被认为是一类可以节省传感器节点能量并延长网络生命周期的方法,但是其需要较多的骨干网节点并且无法保证连通性.通过分析现今算法的内在局限性,提出了一种1-Con思想:当一个Cell的头节点被加入当前骨干网时,所有其可以连接的Cell使用该节点连入拓扑结构,然后此新骨干网递归地继续扩大.基于此思想,设计了一种基于可连Cell的拓扑控制算法(CCTC),并从理论上证明: 1) CCTC可以保证其所形成的拓扑结构维持网络连通;2)每一轮用于形成骨干网的工作节点非常少. CCTC的计算复杂度是线性的,空间复杂度和信息交换量都是常数量级.仿真实验同样显示,CCTC可以在提供良好鲁棒性和较少的消息交换的情况下,更有效地节省节点能耗并延长网络生命周期.
应用于高速网络的基于报文采样和应用签名的BitTorrent流量识别算法
郭振滨 裘正定
2008, 45(2):  227-236. 
摘要 ( 311 )   HTML ( 0)   PDF (514KB) ( 445 )  
相关文章 | 计量指标
在高速网络上进行P2P流量识别具有极大的困难,因为基于端口号的方法已经不再准确,而基于应用签名的方法没有足够高的处理效率.提出了应用于高速网络的基于报文采样和应用签名的BitTorrent流量识别算法.建立了误检率和漏检率模型来分析报文采样率和签名率对识别准确度的作用,并指导应用签名和采样率的选择.通过开发流状态判别预处理器,在Snort平台上实现了该流量识别算法.实验结果表明该流量识别算法处理效率和准确度都是令人满意的,能应用于高速网络环境.在普通个人计算机上,对采样报文的处理效率在800Mbps以上.将该方法应用于报文处理,当采样率为0.5时漏检率为0.6%,当采样率为0.1时漏检率为5.9%,当采样率为0.05时漏检率为10.5%. 将该方法应用于流数据分析,当采样率为0.5时漏检率为0.06%,当采样率为0.1时漏检率为0.33%,当采样率为0.05时漏检率为1.1%. 该方法展现了优秀的误检性能,没有任何报文被误检.实验结果也表明误检率和漏检率模型是非常准确的.
一种基于位向量交集运算的规则冲突检测算法
李 林 卢显良
2008, 45(2):  237-245. 
摘要 ( 461 )   HTML ( 1)   PDF (448KB) ( 492 )  
相关文章 | 计量指标
无论从报文分类算法自身还是从安全角度,规则冲突检测都是一个重要的研究课题.而目前常用的冲突检测算法效率较低.针对这一情况,在ASBV算法基础之上,提出了一种高效的冲突检测算法DBBV. 同ASBV算法类似,DBBV算法也采用了分治思想和位向量技术.但与ASBV算法不同,在每一维规则分量处理过程中,DBBV算法只需要进行一次位向量交集运算,而ASBV算法需要进行多次位向量并集运算;DBBV算法支持以范围形式表示的规则集,而ASBV算法只支持以前缀形式表示的规则集.对DBBV算法的正确性进行了证明,测试表明其检测速度快于ASBV算法.
基于串归约的网格工作流费用优化方法
苑迎春, 李小平, 王 茜,
2008, 45(2):  246-253. 
摘要 ( 322 )   HTML ( 0)   PDF (470KB) ( 432 )  
相关文章 | 计量指标
针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明: BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.
无线传感器网络中一种新型的混合型数据收集协议
徐建波, 李仁发,
2008, 45(2):  254-260. 
摘要 ( 277 )   HTML ( 0)   PDF (405KB) ( 454 )  
相关文章 | 计量指标
无线传感器网络节点数量庞大,单个节点资源极其有限,其数据收集协议设计的首要目标是有效节约能源、延长网络生命周期.分析和比较了现有几种典型的数据收集协议,立足于实际应用需求,设计出一种基于分簇结构的混合型数据收集协议(MDGP). MDGP是一种具备区分服务机制和网内数据融合的数据收集协议,适合于矿井安全监测等大规模检测应用.提出了一个能平衡负载、减少簇头节点的簇头产生算法.采用反向汇聚树结构传输处理数据流,同时对一些紧急数据的处理也进行了详细的讨论.仿真实验表明,MDGP比传统的数据收集协议能获得更长的生命期,达到了较好的预期效果.
仿真网格中一种基于知识的动态任务调度算法
吴 磊 都志辉
2008, 45(2):  261-268. 
摘要 ( 278 )   HTML ( 0)   PDF (413KB) ( 374 )  
相关文章 | 计量指标
仿真网格是以通用网格技术为基础、面向仿真领域的专用网格,目前国际上对仿真网格的研究尚处于起步阶段.现有的分布式仿真HLA(high level architecture)体系结构中的仿真资源和联邦成员是静态绑定的,网格技术的引入使得仿真资源的动态分配成为可能.根据仿真网格任务调度的特点,在仿真网格中建立了一种任务调度模型,并针对该模型,提出了一种新的基于知识的动态任务调度算法KMO,该算法适用于将N个相互独立的计算需求不同的仿真任务调度到M个随时间动态变化的仿真资源上,它能对若干次调度后的结果进行统计并提炼成“知识”反馈给算法预处理部分,使得该算法在动态多变的环境中能获得比较稳定的性能.实验结果表明,在仿真网格环境中,该算法的性能优于网格中传统的任务调度算法.
DPVoD:基于P2P的视频点播体系结构
吴 艾 刘心松 符青云 刘克剑
2008, 45(2):  269-277. 
摘要 ( 539 )   HTML ( 3)   PDF (452KB) ( 337 )  
相关文章 | 计量指标
可扩展性和可靠性是视频点播系统大规模应用的关键,提出了一种P2P点播系统结构DPVoD. 系统基于应用层组播,用户以订制的缓存为其他节点提供服务,并形成相对独立的共享并发流组播树,组播树之间根据拥有的视频数据的重合程度而建立不同的组邻居关系,以此为基础,采用多种机制来提高系统性能:组协同工作、父亲点选择策略、状态控制协议和失效恢复等.定义并分析了可能对系统性能有严重影响的结尾雪崩问题并提出解决方案.对系统基本性能进行了理论分析.仿真结果表明,在静态和动态环境中,DPVoD系统的并发流占用数和利用率、可靠性等性能均优于类似系统.
数据流上的分位数近似算法研究
杨 蓓, 黄厚宽,
2008, 45(2):  287-292. 
摘要 ( 601 )   HTML ( 0)   PDF (347KB) ( 1385 )  
相关文章 | 计量指标
数据流是一种新型数据模型,广泛应用于交通流量监控、通信管理、传感器网络、股票分析、Web点击流等众多领域.近年来越来越多的学者关注于数据流上的分位数计算研究.由于流数据的连续、无界、易失等特性,存储完整的流数据信息并得到精确的查询结果几乎是不可能的.在实施查询计算时追求内存用量与查询精度之间的最佳均衡.设计了规范数直方图的概要数据结构以存储流数据的摘要信息,并在此基础上提出了单遍扫描的、联机的分位数近似算法,其时间和空间复杂度均线性于概要结构中桶的个数,而与数据流的长度无关,因而具有很好的可规模性.该方法在均匀分布的数据上取得了优良性能.分析了算法精度与内存需求的关系.实验结果表明该算法具有较精确的查询结果,具备良好的实用性和有效性.
利用模式及语言学特征提高阅读理解性能
杜永萍, 黄萱菁, 吴立德,
2008, 45(2):  293-299. 
摘要 ( 334 )   HTML ( 2)   PDF (397KB) ( 381 )  
相关文章 | 计量指标
阅读理解(reading comprehension,RC)任务的目的在于理解一篇文档并对提出的问题返回答案句.提出了一种充分利用外部资源来提高RC系统性能的方法,使得RC系统性能在Remedia和ChungHwa两种语料上均得到提高.特别地,在对基于Remedia语料RC系统的性能分析表明,24.1%的性能提高归因于基于Web的答案模式匹配的运用,11.1%的性能提高归因于语言学特征匹配策略运用.同时也进行了t-test,结果表明答案模式匹配、语言学特征匹配和词汇语义关联推理的运用所得到的性能提高是显著的.
关系数据库模式和本体间映射的研究综述
瞿裕忠 胡 伟 郑东栋 仲新宇
2008, 45(2):  300-309. 
摘要 ( 485 )   HTML ( 0)   PDF (488KB) ( 554 )  
相关文章 | 计量指标
关系数据库模式和本体间映射是语义网研究中的一个重要问题.首先,给出关系数据库模式和本体间映射的形式化定义,并从建模思想和应用场景两个方面分析问题的难点.根据3个不同角度,即模型转换的途径、映射策略的适用范围以及映射结果的表达形式,调研当前存在的多种解决途径.在此基础上,进一步介绍并比较6个具有代表性的关系数据库模式和本体间映射的工具.最后,讨论存在的挑战,并指出未来可能的研究方向.
一种基于Z曲线近似k-最近对查询算法
徐红波, 郝忠孝,
2008, 45(2):  310-317. 
摘要 ( 440 )   HTML ( 0)   PDF (540KB) ( 401 )  
相关文章 | 计量指标
k-最近对查询是空间数据库中重要操作之一.在低维空间中基于R*树分枝限界最近对查询算法(k-self-CPQ)和Brute-Force算法的查询效率较高,而在高维空间中其性能急剧恶化,降低空间维度成为解决问题的关键.依据Z曲线构造过程,将高维空间分割成大小相等的网格,以此将网格中的点映射到线性空间中.提出了基于网格划分的降维方法及最小网格概念,给出了基于Z曲线近似k-最近对查询算法.利用最小网格的边长,算法优化线性扫描过程.实验结果表明在高维空间中算法性能优于Brute-Fore和k-self-CPQ,且近似k-最近对质量较好.
属性序列图:形式语法和语义
张鹏程 周 宇 李必信 徐宝文
2008, 45(2):  318-328. 
摘要 ( 408 )   HTML ( 1)   PDF (649KB) ( 403 )  
相关文章 | 计量指标
在基于场景的软件工程中,时态逻辑被广泛地用来推理并发系统的正确性.模型检验技术允许自动检验系统模型和给定的属性之间的一致性,这些属性常用线性时态逻辑公式来表示.不幸的是,由于这些公式具有复杂的结构使得模型检验技术很难应用在工业实践中.属性序列图可以用来解决这种问题,它是一种基于场景的可视化的语言,容易理解并且具有较强的表达能力,能够克服当前工业中常用的符号中存在的诸多表达缺陷.为了能够完全清晰地描述和理解属性序列图,使其能够广泛地应用,给出其形式语法和基于Büchi自动机的形式语义,并进行了实例研究,讨论了其应用前景.
支持HLA仿真和并行绘制的统一对象模型研究
王总辉 熊 华 姜晓红 石教英
2008, 45(2):  329-336. 
摘要 ( 303 )   HTML ( 0)   PDF (476KB) ( 383 )  
相关文章 | 计量指标
随着计算机硬件、软件、网络以及社会需求的发展,分布式交互仿真应用对大规模复杂场景和大量仿真实体对象的管理能力和绘制能力提出了较高的要求.针对现有HLA仿真应用中大规模复杂场景的视景仿真实时性较差、仿真实体对象管理与绘制对象管理是分离的等问题,提出了统一对象模型,包含异质实体对象树、操作记录列表和统一访问接口,实现了仿真实体对象和绘制对象的高效组织和统一管理.该统一对象模型在HLA仿真平台和并行绘制平台之间建立了高效的数据交换桥梁,减轻了两者集成的开发工作量,并有效地支持了大规模复杂场景和大量仿真实体对象的实时绘制,有助于提高仿真的实时性.该统一对象模型对于HLA仿真平台和并行绘制平台具有通用性.最后给出了实验结果和分析.
FPGA实时实现PGA算法的研究
郝智泉, 王贞松, 刘 波,
2008, 45(2):  342-347. 
摘要 ( 525 )   HTML ( 0)   PDF (364KB) ( 488 )  
相关文章 | 计量指标
合成孔径雷达(SAR)成像具有数据量巨大、算法比较复杂等特点.如何实时实现SAR成像的相关算法是嵌入式高性能计算领域一个值得研究的问题. FPGA以其高性能、可重构等优势,被越来越多地应用到嵌入式高性能计算领域中作为一种高效低成本的解决方案.针对SAR成像中多普勒调频率估计的经典算法——PGA算法,以FPGA作为实现平台,通过对算法的本质的挖掘,提出了适于FPGA实时实现的对于经典算法的改进算法.同时也阐述了将改进算法映射到FPGA实现的设计过程.实验结果表明,改进的算法较经典的PGA算法明显地减少了迭代次数,在SOC中通过硬件的运算精度能够满足系统的要求.
一种基于移动计算环境的因果日志卷回恢复算法
张 展 左德承 慈轶为 杨孝宗
2008, 45(2):  348-357. 
摘要 ( 378 )   HTML ( 0)   PDF (553KB) ( 446 )  
相关文章 | 计量指标
由于移动节点的不可靠和无线网络连接的脆弱性,研究移动计算系统容错机制具有重要意义.对可以跨区移动、随时可以与网络断开的自治性很强的移动节点来说,异步的卷回恢复是一种重要的容错手段.现有的移动计算环境下的卷回恢复算法都无法完全实现一致的异步卷回恢复.基于因果消息日志,提出一种新的移动计算环境的卷回恢复算法:通过先行图来记录节点间的消息依赖关系,将异步检查点、基于发送方的暂存消息日志和先行图全部在移动支持站上存储和处理,为移动节点提供一种透明的容错服务,完全消除依赖关系在移动节点之间造成的影响.用形式化的方法证明了系统的一致性.仿真结果表明,在卷回开销达到最低的同时,也显著降低了无错运行时的通信和存储开销.
高性能处理器的差错校正技术
王 真 江建慧 员春欣
2008, 45(2):  358-366. 
摘要 ( 275 )   HTML ( 0)   PDF (444KB) ( 453 )  
相关文章 | 计量指标
随着芯片密度的不断增加和对可靠性要求的不断提高,高性能处理器的容错设计越来越受到关注.对近年来高性能处理器的差错校正技术进行了分析和比较,它们被分为时钟级差错恢复、指令级差错恢复、线程级差错恢复以及重构等4类,研究对象包括研究方案、原型和产品.研究结果表明,以片上多处理器和/或同时多线程为特征的高性能处理器除了沿用传统的容错技术之外,多以固有的、旨在为改善性能而重复设置的硬件资源为基础来设计容错机制和调度方案.
基于统计信息的Cache漏流功耗估算方法
周宏伟 张承义 张民选
2008, 45(2):  367-374. 
摘要 ( 243 )   HTML ( 0)   PDF (445KB) ( 346 )  
相关文章 | 计量指标
随着工艺尺寸的缩小,漏流功耗逐渐成为制约微处理器设计的主要因素之一. Sleep Cache与Drowsy Cache是两种降低Cache漏流功耗的重要技术.基于统计信息的Cache漏流功耗估算方法(SB_CLPE)用于对Sleep Cache或Drowsy Cache进行Cache漏流功耗估算,根据该方法设计的Cache体系结构能够在程序执行过程中实时估算Cache漏流功耗.通过对所有Cache块的访问间隔时间进行统计,SB_CLPE可以估算出使用不同衰退间隔时Cache的漏流功耗,从而得到使Cache漏流功耗最低的最佳衰退间隔.实验表明,SB_CLPE对Sleep Cache的漏流功耗的估算结果与HotLeakage漏流功耗模拟器通过模拟获得的结果相比,平均偏差仅为3.16%,得到的最佳衰退间隔也可以较好吻合.使用SB_CLPE的Cache体系结构可以用于在程序执行过程中对最佳衰退间隔进行实时估算,通过动态调整衰退间隔以达到最优的功耗降低效果.
可重构资源管理及硬件任务布局的算法研究
李 涛 杨愚鲁
2008, 45(2):  375-382. 
摘要 ( 256 )   HTML ( 0)   PDF (497KB) ( 509 )  
相关文章 | 计量指标
可重构系统具有微处理器的灵活性和接近于ASIC的计算速度,可重构硬件的动态部分重构能力能够实现计算和重构操作的重叠,使系统能够动态地改变运行任务,可重构资源管理和硬件任务布局方法是提高可重构系统性能的关键.提出了基于任务上边界计算最大空闲矩形的算法(TT-KAMER),能够有效地管理系统的空闲可重构资源;在此基础上使用FF和启发式BF算法进行硬件任务的布局.实验表明,算法能够有效地实现在线资源分配与任务布局,获得较高的资源利用率.