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

当期目录

2009年 第46卷 第6期    出版日期:2009-06-15
论文
基于贝叶斯网络的无结构化P2P资源搜索方法
钱 宁 吴国新 赵生慧
2009, 46(6):  889-897. 
摘要 ( 325 )   HTML ( 1)   PDF (1505KB) ( 509 )  
相关文章 | 计量指标
资源搜索是P2P网络基本功能及核心问题,关系到P2P网络可用性及扩展能力.尽管已提出许多无结构化P2P搜索方法,但复杂组织方式、较高搜索代价及过多维护影响其可用性.提出一个全分布无结构化P2P网络搜索方法BNS.该方法从节点自身兴趣特性出发,利用节点上资源之间语义相关,应用贝叶斯网络建立推理模型,根据相关资源历史信息进行推理,采用概率方法,将搜索导向与目标相关的节点,提高搜索性能.实验表明,该方法能够有效地提高搜索性能,消耗较少带宽且维护简单,对P2P动态变化特性具有良好适应能力.
WPathload:一种改进的可用带宽测量方法
曾 彬, 张大方, 黎文伟, 谢高岗,
2009, 46(6):  898-904. 
摘要 ( 469 )   HTML ( 2)   PDF (793KB) ( 442 )  
相关文章 | 计量指标
可用带宽是网络的重要资源,对其准确的估计与测量是流量工程和网络监测等必须解决的问题, 但对它的实际测量存在许多困难.针对Pathload可用带宽测量方法存在收敛慢、开销大的问题,提出了一种Pathload可用带宽测量的改进方法(WPathload).该方法基于时延变化的统计规律,改进发送速率调整算法,并采用周期流组到达目的端的速率代替周期流的发送速率,更新可用带宽上界,从而加快收敛速度,降低测量开销.实验结果表明,改进后的方法能快速反映可用带宽的变化,增强了跟踪带宽变化的能力.
一种扩展的多操作系统远程启动协议ENCBP
韦 理, 徐广斌, 张尧学, 夏 楠, 匡文渊,
2009, 46(6):  905-912. 
摘要 ( 463 )   HTML ( 0)   PDF (802KB) ( 429 )  
相关文章 | 计量指标
提出一种在局域网环境下对网络计算设备进行远程多操作系统引导的协议——ENCBP(extended network-based client boot protocol)协议,对现有的NCBP(network-based client boot protocol)协议进行改进,通过区分引导的操作系统内核结构的类型改进了协议交互的过程,提高了单内核操作系统远程启动的效率,提出更安全的传输方法,增强了协议的安全性,引入在BIOS芯片中的固件启动代理,节省了对附加芯片的需求.最后以基于龙芯Ⅱ号平台的透明计算系统作为应用实例进行测试,并对测试结果做了分析和评价,验证了该方法的有效性.
一种互操作测试的建模及测试选择方法
李 华 叶新铭 吴承勇 王 龙 王玲玲
2009, 46(6):  913-919. 
摘要 ( 377 )   HTML ( 0)   PDF (872KB) ( 412 )  
相关文章 | 计量指标
互操作性测试可以对设备互连互通互操作提供根本保证,一致性测试与互操作性测试既有相交的部分又各有不同.互操作性测试包括两个被测实现,其中一方有时称为QE(qualified equipment).根据被测的规范说明的不确定有限状态机模型和当前已有的互操作性测试经验构建概率不确定有限状态机,有效地刻画当前的互操作性测试状况.基于该模型采用宽度优先算法以及一定的策略生成包含所有状态的二叉树,然后基于得到的二叉树给出了包含不确定状态的互操作性测试序列的选择算法,通过示例展示了提出的算法的有效性,并以RIP协议的计数到无穷为例展示了提出的建模方法的应用.最后给出了结论以及下一步的研究工作.
分布式多点并发测试系统的设计与实现
骆 昊 曾华燊
2009, 46(6):  920-926. 
摘要 ( 608 )   HTML ( 1)   PDF (877KB) ( 541 )  
相关文章 | 计量指标
随着Internet的迅速发展,IP路由器在网络中的地位越来越重要,因此在路由器产品进入网络之前必须对其进行全面的测试以检测其功能和性能是否满足应用的需求.针对现有的基于单机架构的路由器测试系统存在的不足,从多个角度分析了构建分布式架构测试系统的必要性.设计并实现了分布式多点并发测试系统,该系统由一个分布式测试管理器和多个测试代理组成,具有良好的可伸缩性和可扩展性,能够模拟路由器在真实网络中的工作环境并实现对路由器的一致性测试、性能测试和互操作性测试.对系统的实现细节进行了详细的阐述,重点讨论了分布式测试系统中的同步问题并提出了相应的解决方案.在上述工作的基础上进行了路由器测试实验,证实了该系统的可行性和实用性.
Internet路由关联分析与监测系统设计
梁 伟, 毕经平,
2009, 46(6):  927-933. 
摘要 ( 437 )   HTML ( 2)   PDF (1126KB) ( 601 )  
相关文章 | 计量指标
Internet已经从一个学术性网络演化成为具有商业意义的公共信息基础设施的重要组成部分,路由系统是其基础和关键部分,对Internet路由层面的监测与分析有着重要的理论和现实意义.Internet路由结构被划分成为域内路由和域间路由,两者紧密联系并相互作用,但是目前路由监测和分析的工作主要基于单一协议进行,无法给出包含多种路由协议的全面监测视图,也不能很好地解决由于协议交互带来的问题.针对这个不足,探索了域内和域间路由的关联分析技术,并在此基础上成功设计实现了Internet路由监测系统IRMS(Internet routing monitoring system).IRMS在对主流路由协议OSPF,BGP的监测基础上,可以提供包括全局路由拓扑构造、协议交互分析在内的路由关联分析能力.实际网络路由监测实验表明,IRMS使网络管理人员可以更加深入和全面地进行路由监测分析.
无线传感器网络中一种避免节点拥塞的算法
孙国栋, 廖明宏, 邱 硕,
2009, 46(6):  934-939. 
摘要 ( 457 )   HTML ( 0)   PDF (900KB) ( 476 )  
相关文章 | 计量指标
无线传感器网络节点拥塞导致节点丢弃大量的数据包,这不仅影响了网络服务质量, 还浪费了节点宝贵的能量,进而缩短了网络生命周期.提出了一种避免传感器网络节点拥塞的算法.该算法包含了基于发送窗口分配的拥塞避免和基于优先级的数据包调度策略.网络节点首先根据一定策略为上一跳节点分配发送窗口来预防本地发生拥塞,获得发送窗口的上一跳节点每次选择优先级最高的数据包发送以改善网络服务质量.模拟实验表明,提出的算法具有良好的能量有效性,有效地避免了由节点缓冲区溢出造成的网络丢包,同时改善了网络传输的公平性并降低了网络的平均延迟.
不同设计层次下密码运算部件抗功耗攻击能力量化评估技术
童元满 王志英 戴 葵 陆洪毅
2009, 46(6):  940-947. 
摘要 ( 370 )   HTML ( 0)   PDF (842KB) ( 432 )  
相关文章 | 计量指标
为设计有效抗功耗攻击且具有高性价比的安全芯片,需要在其设计实现过程中量化分析密码运算部件抗功耗攻击的防护能力,其关键在于评估防护能力以及模拟密码运算部件的瞬态功耗.以成功实施功耗攻击所需的样本数来量化密码运算部件抗功耗攻击能力,提出了成功实施功耗攻击所需样本数的估算方法;在RTL(register transfer level)级、综合后以及布局布线后等不同设计层次进行瞬态功耗模拟的技术;以及以空间换时间和多线程并行模拟技术,以提高瞬态功耗的模拟速度,也可以用于大规模电路的瞬态功耗模拟.
一种基于风险的多域互操作动态访问控制模型
唐 卓, 赵 林, 李肯立, 李瑞轩,
2009, 46(6):  948-955. 
摘要 ( 477 )   HTML ( 5)   PDF (788KB) ( 461 )  
相关文章 | 计量指标
随着Internet及其相关技术的快速发展,在开放的、异构的多自治域环境下,出现了大量的分布式应用之间的互操作. 多自治域环境的复杂性与信息安全共享不断演变进化的特点,使得传统访问控制模型难以保证数据资源在交互过程中的安全.通过将风险概念引入访问控制中,提出一种基于风险的多域动态访问控制模型.在本模型中,主体所具有的某项安全策略的风险等级由自治域间的互操作历史记录、客体的安全等级以及访问事件的安全系数得出,通过对高风险等级的安全策略进行调整以达到对系统风险的实时控制.理论分析表明这种方法可有效保证访问控制的灵活性和多自治域环境的安全性.
二元推导与自相关随机性检测算法的相关性分析
范丽敏, 冯登国, 陈 华,
2009, 46(6):  956-961. 
摘要 ( 459 )   HTML ( 0)   PDF (534KB) ( 564 )  
相关文章 | 计量指标
随机性检测在密码学中发挥着重要的作用,目前,已有多种不同的随机性检测算法.但是,实际应用中选择所有的检测算法进行检测不现实,选择哪些算法能够使检测充分且无冗余,这需要研究检测算法之间可能存在的关系.对两种重要的随机性检测算法二元推导和自相关进行了研究.从二者的基本原理出发,对其检测的推导过程进行了分析,结合杨辉三角的性质证明了在参数k选择为2\+t时,二元推导与自相关是等价的.若同时进行参数为2\+t的二元推导检测和自相关检测则存在冗余.同时对这个结论进行了实验验证.另外,研究还发现,在参数k选择为2\+t-1时,二元推导检测中推导序列的每一个比特包含初始序列的所有相关比特信息.所研究工作为实际应用中随机性检测项目和检测参数的选择提供了理论的指导.
可重构分组密码处理结构模型研究与设计
杨晓辉 戴紫彬 张永福
2009, 46(6):  962-967. 
摘要 ( 539 )   HTML ( 0)   PDF (613KB) ( 620 )  
相关文章 | 计量指标
随着信息技术的发展和网络规模不断扩大,网络通信等应用对数据加解密处理提出了更高的要求.可重构计算是将可重构硬件处理单元和软件可编程处理器结合的计算系统.因此采用可重构计算技术来设计密码处理系统,使同一硬件能够高效灵活地支持密码应用领域内的多种算法.同时满足了密码处理对性能和灵活性的要求,提高了密码系统的安全性.论文在分析分组密码算法处理结构的基础上,结合了可重构结构的设计思想和方法,提出了一种可重构密码处理结构模型RCPA,并基于该模型实现了一款验证原型.原型在FPGA上成功进行了验证测试并在0.18μm CMOS工艺标准单元库下进行逻辑综合以及布局布线.实验结果表明,在RCPA验证原型上执行的分组密码算法都可达到较高的性能,其密码处理性能与通用高性能微处理器处理性能相比提高了10~20倍;与其他一些专用可重构密码处理结构处理性能相比提高了1.1~5.1倍.结果说明研究的RCPA模型既能保证分组密码算法应用的灵活性又能够达到较高的性能.
一种快速求解旅行商问题的蚁群算法
冀俊忠 黄 振 刘椿年
2009, 46(6):  968-978. 
摘要 ( 664 )   HTML ( 3)   PDF (1682KB) ( 582 )  
相关文章 | 计量指标
蚁群优化是一种元启发式的随机搜索技术,是目前解决组合优化问题最有效的工具之一.将信息素更新和随机搜索机制的改进相结合,提出一种快速求解旅行商问题的蚁群算法.首先给出了一种新的信息素增量模型,以体现蚂蚁在不同路径上行走时所产生的信息素差异;然后以蚂蚁经过的路径(直线段)作为信息素扩散浓度场的信源,改进了信息素扩散模型,强化了蚂蚁间的协作和交流;最后采用较低复杂度的变异策略对迭代的结果进行优化.在大量通用数据集上的实验表明,该算法不仅能获得更好的最优解,而且收敛速度有显著的提高.
带传递关系和存在量词的描述逻辑MSC推理
蒋运承, 唐素勤, 王 驹, 周生明,
2009, 46(6):  979-987. 
摘要 ( 454 )   HTML ( 0)   PDF (679KB) ( 432 )  
相关文章 | 计量指标
分析了描述逻辑非标准推理的重要性,特别分析了描述逻辑MSC推理的研究现状和存在的问题.针对目前描述逻辑MSC推理不能同时处理传递关系和存在量词的不足,研究了带传递关系和存在量词的描述逻辑εL\++的MSC推理问题. 提出了一种新的εL\++-描述图,利用描述树和描述图给出了描述逻辑εL\++的MSC近似推理算法,并利用εL\++-描述树同态和εL\++-描述树描述图同态证明了MSC近似推理算法的正确性. 作为一个附带的结果,利用εL\++-描述树描述图同态给出了εL\++的实例推理算法,也证明了实例推理算法的正确性.
最大方差展开的快速松弛算法
王庆刚, 李见为,
2009, 46(6):  988-994. 
摘要 ( 1315 )   HTML ( 0)   PDF (1370KB) ( 499 )  
相关文章 | 计量指标
最大方差展开(maximum variance unfolding,MVU)是在流形局部等距概念基础上提出的一种新的非线性维数约减算法,能有效学习出隐含在高维数据集中的低维流形结构.但MVU的优化需要解决一个半定规划(semidefinite programming,SDP)问题,巨大的计算和存储复杂度限制了它在大规模数据集上的可行性.提出了MVU的一种快速算法——松弛最大方差展开(relaxed maximum variance unfolding,RMVU),算法基于Laplacian特征映射(Laplacian eigenmap)近似保留数据集局部结构的思想,对MVU中严格的局部距离保留约束进行松弛;算法求解转变为一个广义特征分解问题,大大降低了运算强度和存储需求.为了适应更大规模数据集的处理需求,同时提出了RMVU的一种改进算法——基于基准点的松弛最大方差展开(landmark-based relaxed MVU,LRMVU).在模拟数据集和COLT-20数据库上的实验验证了算法的有效性.
一种基于主存Δ-tree的高维数据自相似连接处理
刘 艳, 郝忠孝,
2009, 46(6):  995-1002. 
摘要 ( 459 )   HTML ( 0)   PDF (672KB) ( 389 )  
相关文章 | 计量指标
相似连接作为数据挖掘的基元,可被用来大幅度提高相似搜索、数据分析和数据挖掘的速度.大多数研究主要集中在大量基于磁盘数据的高维连接.目前计算机可得到的主存容量越来越大以及对空间连接的有效处理的需求表明,一大类问题的空间连接能够在主存中处理.Δ-tree是一个新提出的多层索引,已被证实优于其他主存索引.因此,以Δ-tree为基础,提出了一种空间连接算法Δ-tree-join,研究了它的性能,和目前最先进的算法EGO-join和EGO\+*-join进行了比较.结果显示Δ-tree-join的效率比它们有大幅度提高,是一种有效的连接方法.
基于版本空间解析中心的多类分类器的泛化性能分析
曾凡仔 肖德贵 李仁发 罗娟
2009, 46(6):  1003-1008. 
摘要 ( 537 )   HTML ( 0)   PDF (596KB) ( 405 )  
相关文章 | 计量指标
多类分类是机器学习领域中的重要问题.目前普遍采用的多类分类方法:“one versus all”(OvA)直接利用“标准”的两类分类器重复构造两类分类器,导致计算复杂度较高、分类效率降低.基于支持向量机的多类分类器尽管无需重复构造两类分类器,但由于它对应于版本空间(version space)内最大超球的中心,所以当版本空间为非对称或比较狭长时,它的泛化能力显著降低.而基于版本空间解析中心的多类分类算法M-ACM克服了上述问题.从理论上分析了该分类器的泛化性能,给出了它的泛化误差上界,并进行了实验验证.
BJUT-3D三维人脸数据库及其处理技术
尹宝才 孙艳丰 王成章 盖 赟
2009, 46(6):  1009-1018. 
摘要 ( 4500 )   HTML ( 26)   PDF (1875KB) ( 1318 )  
相关文章 | 计量指标
BJUT-3D是目前国际上最大的中国人的三维人脸数据库,其中包括经过预处理的1200名中国人的三维人脸数据,这一数据资源对于三维人脸识别与建模方面的研究有重要意义.首先介绍了BJUT-3D数据库的数据获取条件、数据形式,并针对数据库建立过程中数据预处理技术进行了讨论.最后作为数据库的直接应用,进行了多姿态人脸识别和人脸姿态估计算法的研究.实验结果证实,该算法具有良好的性能.
基于SPN的信息系统生存性分析建模研究
张乐君, 国 林, 张 冰, 杨 武, 王 巍, 杨永田,
2009, 46(6):  1019-1027. 
摘要 ( 589 )   HTML ( 0)   PDF (1175KB) ( 519 )  
相关文章 | 计量指标
研究基于随机Petri网(SPN)的信息系统生存性分析建模方法.首先,将信息系统抽象为请求组件、通信组件、处理组件和存储组件4个部分;其次,将信息系统工作流程形式化描述和生存性分析建模相结合,并分别描述了通用信息系统、系统组件失效修复、串联并接、冗余以及具有可生存属性组件的随机Petri网建模方法.从而对系统形式化描述的同时对系统生存性能做了定性和定量分析;最后,仿真实验证明基于SPN建模方法分析信息系统生存性的有效性和准确性,并为可生存的信息系统设计提供理论基础和指导.
强全序时态模式中混合依赖集成员籍问题的研究
万 静, 王晓宇, 郝忠孝,
2009, 46(6):  1028-1035. 
摘要 ( 351 )   HTML ( 0)   PDF (610KB) ( 439 )  
相关文章 | 计量指标
对于TFD和RTMVD混合依赖集约束的强全序时态模式来说, 成员籍问题的解决对设计有效的模式分解算法必不可少.由于强全序时态模式中多时间粒度的使用,使其成员籍问题的解决变得更加复杂.为此定义了强全序时态模式下的属性集在给定时态类型上的混合闭包、属性集的混合闭包、属性集在给定时态类型上的混合依赖基、属性集的混合依赖基等概念,给出了求强全序时态模式下属性集的混合闭包、属性集的混合依赖基以及TFD和RTMVD混合依赖集成员籍问题的算法,并对算法的可终止性、正确性进行了证明,对时间复杂性进行了分析.
局部范围受限的多类型最近邻查询
孙冬璞, 郝忠孝,
2009, 46(6):  1036-1042. 
摘要 ( 385 )   HTML ( 0)   PDF (1155KB) ( 477 )  
相关文章 | 计量指标
多类型最近邻查询在现实中的应用范围比传统的最近邻查询广泛.基于多类型最近邻查询,提出局部范围受限的多类型最近邻查询(PCMTNN)概念,针对范围约束是任意简单多边形区域的数据集给出PCMTNN算法,利用椭圆最小外切矩形的易求性和与椭圆本身覆盖区域的最近似性特点缩小了搜索范围,并用一个链表结构实现了在一次R树的遍历过程中找到包含在所有搜索区域内的数据集中点的过程,从而大幅度减少了无用点的访问数量.实验结果分析表明算法具有较好的性能.
弱可逆线性有限自动机的一种分解
姚兴华, 邓培民, 易 忠, 蒋运承,
2009, 46(6):  1043-1051. 
摘要 ( 355 )   HTML ( 2)   PDF (703KB) ( 432 )  
相关文章 | 计量指标
讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解, 从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上, 即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机M\-D, 并得到了分解存在的充要条件;最后, 用输出序列的代数性质来刻画其中的充分条件, 并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于n元弱可逆有限自动机, 而且分解条件也比较简单, 仅与输出序列的性质有关.
有向无环图最小度生成树问题的一种近似算法
姚国辉 朱大铭 马绍汉
2009, 46(6):  1052-1057. 
摘要 ( 1189 )   HTML ( 0)   PDF (563KB) ( 688 )  
相关文章 | 计量指标
计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过Δ\+*+1,其中Δ\+*为某一最优树的度.算法的时间复杂度为O(n\+2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.
一种面向多核处理器并行系统的启发式任务分配算法
刘 轶, 张 昕, 李 鹤, 钱德沛,
2009, 46(6):  1058-1064. 
摘要 ( 633 )   HTML ( 0)   PDF (661KB) ( 534 )  
相关文章 | 计量指标
多核处理器使得并行系统的结构更加复杂并且其中任务个数大大增加,为了在这类系统中高效地进行任务分配,建立了任务分配模型,并提出了一种包含两轮操作的启发式任务分配算法,分别完成进程到处理节点和进程内线程到处理器核的分配.每轮操作经过带回溯的多次迭代处理,最终得到任务到处理器核的分配方案.与穷举查找法和遗传算法的对比测试表明该算法能在较短时间内求得近优解,并且当线程个数增大时,算法的求解时间远小于遗传算法.