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

当期目录

2007年 第44卷 第9期    出版日期:2007-09-15
论文
一种高性能的全序组播算法
李 磊 王怀民 史殿习
2007, 44(9):  1449-1455. 
摘要 ( 455 )   HTML ( 0)   PDF (364KB) ( 721 )  
相关文章 | 计量指标
全序组播是构建分布式应用程序的一种重要组通信原语,它能够保证一个通信组中的所有成员都按照同样的顺序接收消息.目前的全序组播算法不能同时获取低延迟和高吞吐量,并且缺乏对应用程序通信模式的适应性,因此不适用于高性能计算环境.在分析已有算法排序机制基础上,指出影响全序组播算法性能的关键因素,并提出一种基于leader/followers模式和阻塞检测机制的新算法.算法工作原理如下:每一个组成员都可以在任意时刻发送消息,但只能提交来自当前leader成员的消息;一旦leader成员进入不活跃状态,则通过特殊的命令来指定某个活跃的follower成员为新的leader成员.模拟实验结果表明,该算法在延迟时间和吞吐量等性能指标方面都优于已有算法,同时在突发消息模式下能够大幅度提升性能.
求解HP模型蛋白质折叠问题的改进PERM算法
陈 矛, 黄文奇, 吕志鹏,
2007, 44(9):  1456-1461. 
摘要 ( 469 )   HTML ( 1)   PDF (331KB) ( 559 )  
相关文章 | 计量指标
PERM是一种用来求解基于HP模型的蛋白质折叠问题的高效算法.在介绍PERM算法核心思想的基础上,对影响算法效率的因素做了改进:重新定义了权重和权重预测公式,并对选择动作时不同情况下的权重计算公式进行了统一,得到了改进的PERM算法.对当前文献中的多个典型算例进行了测试,并与Monte Carlo算法和PERM进行了比较.结果表明, 改进后的PERM算法在计算速度上比PERM有明显提高,在速度和优度上远高于Monte Carlo算法.特别是对链长为46的算例,找到了比文献中报道的结果能量更低的构形.
动态增殖流形学习算法
曾宪华, 罗四维,
2007, 44(9):  1462-1468. 
摘要 ( 494 )   HTML ( 1)   PDF (428KB) ( 471 )  
相关文章 | 计量指标
流形学习的主要目标是发现高维观测数据空间中的低维光滑流形.目前,流形学习已经成为机器学习和数据挖掘领域的研究热点.为了从高维数据流和大规模海量数据集中探索有价值的信息,迫切需要增殖地发现内在低维流形结构.但是,现有流形学习算法不具有增殖能力,并且不能有效处理海量数据集.针对这些问题,系统定义了增殖流形学习的概念,这有利于解释人脑中稳态感知流形的动态形成过程,且可以指导符合人脑增殖学习机理的流形学习算法的研究.以此为指导原则,提出了动态增殖流形学习算法,并在实验中验证了算法的有效性.
基于语言建模的文本情感分类研究
胡 熠, 陆汝占, 李学宁, 段建勇, 陈玉泉,
2007, 44(9):  1469-1475. 
摘要 ( 585 )   HTML ( 0)   PDF (394KB) ( 644 )  
相关文章 | 计量指标
提出了一种基于语言建模的文本情感分类的方法.将文本的情感倾向标记为“赞扬”或“批评”,可以为文本提供主题之外的语义信息.为此提出了从训练数据中分别估计出代表“赞扬”和“批评”两种情感倾向的语言模型,然后通过比较测试文本自身的语言模型和这两种训练好的情感模型之间的Kullback-Leibler距离,分类测试文本的思路.各个模型的参数分别选用词形特征的unigram和bigram,而相应的参数估计也分别尝试了最大似然和平滑两种策略.当在电影评论语料上和代表不同分类模型的支持向量机及朴素贝叶斯分类器进行比较时,语言建模的方法表现出了较好的分类性能和鲁棒性.
一种具有混合编码的二进制差分演化算法
贺毅朝, 王熙照, 寇应展,
2007, 44(9):  1476-1484. 
摘要 ( 760 )   HTML ( 4)   PDF (535KB) ( 766 )  
相关文章 | 计量指标
差分演化(DE)是Storn和Price于1997年提出的一种基于个体差异重组思想的演化算法,非常适用于求解连续域上的最优化问题.首先引入“差异算子”等概念,给出DE的一种简洁算法描述,并分析了它所具有的特性.然后,为了使DE能够求解离散域上的最优化问题,基于数学变换思想引入“辅助搜索空间”和“个体混合编码”等概念,通过定义一个特殊的满射变换,在辅助搜索空间的作用下将连续域上的高效差分演化搜索变换为离散域上的同步演化搜索,由此提出了第1个二进制差分演化算法:具有混合编码的二进制差分演化算法(HBDE).接着,给出了HBDE的依概率收敛和完全收敛的定义,并利用离散Markov随机理论证明了HBDE是完全收敛的. HBDE不仅完全具有DE的各种特性和所有优点,而且非常适用于求解离散域上的最优化问题,对随机生成的大规模3-SAT问题实例和典型0/1背包问题实例的数值计算表明:该算法具有很好的全局收敛性和稳定性,其性能远远超过二进制粒子群优化算法和遗传算法.
双重软件体系结构描述框架XYZ/ADL
朱雪阳
2007, 44(9):  1485-1494. 
摘要 ( 617 )   HTML ( 1)   PDF (523KB) ( 490 )  
相关文章 | 计量指标
体系结构设计在软件开发过程中扮演着重要角色.工程中常用图形语言为软件体系结构建模,它们有直观、半形式化的优点;但是语义不够精确,难以对它们表示的模型进行分析,在这方面,形式化方法可与之互补.但在工程使用中仅用形式化语言建模又不太现实,所以如何结合二者之长以提高软件的可靠性已成为工业界和学术界共同关心的问题.提出了双重软件体系结构描述框架XYZ/ADL:支持工程中软件体系结构的基本概念,前端用一般的体系结构框图作为结构描述,用UML活动图、状态图作为抽象行为表示;后端用既可表示系统动态语义又可表示系统静态语义的时序逻辑语言XYZ/E作为一致的语义基础.前端的图形语言便于软件工程师的交流和使用,后端的形式语言是进一步的形式化分析验证的基础.
软件容错模型中的容错实时调度算法
刘 东 张春元 李 瑞 黄 影 李 毅
2007, 44(9):  1495-1500. 
摘要 ( 535 )   HTML ( 0)   PDF (371KB) ( 528 )  
相关文章 | 计量指标
在软件容错模型的容错实时调度算法中,主部分可执行性的预测精度是影响调度算法性能的关键.针对此问题提出了DPA(deep-prediction based algorithm)和EDPA(EDF-based DPA)算法.算法考虑当前时间至替代部分通知时间之间的任务执行情况,通过构建预测表对待执行主部分的可执行性进行精确预测.当主部分不发生错误时算法根据预测表调度任务. DPA依照预测表中通知时间的先后顺序调度主部分,而EDPA则按照EDF算法调度预测表中的主部分.模拟结果表明,DPA和EDPA较目前同类算法可获得更多的主部分执行时间,降低CPU的消耗.当软件错误率较低、任务周期较短时,算法能够以较小的调度开销获得较高的调度性能.
一种高性能北桥芯片的设计及性能分析
曾洪博, 胡明昌, 李 文, 蔡 飞, 唐志敏,
2007, 44(9):  1501-1509. 
摘要 ( 490 )   HTML ( 0)   PDF (513KB) ( 512 )  
相关文章 | 计量指标
计算机系统整体性能的提高不仅仅依赖于处理器计算能力的提升也需要高性能芯片组的有力支持.芯片组承担着CPU和外围设备通信的重任,而且目前大多数系统中采用把内存控制器集成在北桥中的方法,这更加突出了北桥在访存性能以至于在整个系统中的关键作用.以高性能为目标,龙芯2C处理器配套北桥芯片NB2005的设计和优化采用了很多新的方法和技术,其中包括根据程序行为进行动态Page管理的内存控制电路,一种与内存控制电路状态相结合的预取策略和具备高吞吐量低延迟的PCI通道设计等.性能测试和分析表明,搭配NB2005的龙芯2C系统访存带宽要比搭配Marvell GT64240北桥的系统提高40%以上,运行SPEC CPU2000浮点和定点程序的性能分别提高了12.2%和2.5%,磁盘I/O的性能也提高了30%.
环网中的维度气泡流控与自适应路由算法
肖灿文, 张民选, 过 锋,
2007, 44(9):  1510-1517. 
摘要 ( 367 )   HTML ( 1)   PDF (432KB) ( 439 )  
相关文章 | 计量指标
介绍了一个称为环网维度气泡流控(TDBFC)的新型流控策略和称为环网维度气泡路由(TADBR)算法的新型自适应路由算法.在Bubble流控和DBFC流控的基础上设计了适合于环网的维度气泡流控.在环网中,如果采用TDBFC流控策略,设计的TADBR自适应路由算法可实现无死锁的最短距离的路由.对于以上结论,提供了详细的证明.最后,介绍了自行设计的模拟工具RingNetSim,该模拟器实现了TDBFC流控策略和TADBR算法.在RingNetSim上分析了TADBR算法的性能,结果显示环网维度气泡路由算法拥有较好的性能.
基于Horn逻辑扩展模型的安全协议反例的自动构造
周 倜, 李梦君, 李舟军, 陈火旺,
2007, 44(9):  1518-1531. 
摘要 ( 347 )   HTML ( 0)   PDF (821KB) ( 549 )  
相关文章 | 计量指标
根据安全协议的Horn逻辑扩展模型和相应的安全协议验证方法,提出了自动构造不满足安全性质的安全协议反例的求解策略,并给出了重要定理的证明,设计了一系列自动构造协议攻击的构造算法,并在基于函数式编程语言Objective Caml开发的安全协议验证工具SPVT中实现了这些算法,给出了主要算法的优化方法,详细分析了主要算法的时间复杂度,从理论上证明了算法是线性时间算法.最后,用SPVT对一些典型的安全协议进行了验证,得到了不安全协议的反例,并对反例进行了分析.得到的反例非常方便于阅读,与Alice-Bob标记非常接近,从而使任何领域的专家都可以用这种形式化的方法检查安全协议是否存在真实的反例.
基于双线性群的同态承诺方案
宋 焰
2007, 44(9):  1532-1537. 
摘要 ( 867 )   HTML ( 1)   PDF (352KB) ( 706 )  
相关文章 | 计量指标
承诺方案是一种基本而用途广泛的密码学原语,其在数学签名方案、电子支付协议、零知识协议以及安全多方计算协议等方面有着重要应用,因而成为密码学领域重要的研究课题之一.从设计思想来看,大多数有效承诺方案的构造都可纳入q单向群同态这一框架.但q单向性是一种极强的要求,使得其在实例化时可供选择的群结构受到限制.如何突破限制寻求新途径就成为承诺方案构造方面的重要课题.首次基于合数阶双线性群分别构造了无条件隐藏的陷门承诺方案以及无条件绑定的承诺方案,同时证明了在子群判定假设下这两个承诺方案分别是计算上绑定和计算上隐藏的.由于双线性群支持双线性映射,这些承诺方案除具备通常的线性同态性质外还具备特有的乘性同态性质.
基于系统调用和齐次Markov链模型的程序行为异常检测
田新广, 高立志, 孙春来, 张尔扬,
2007, 44(9):  1538-1544. 
摘要 ( 506 )   HTML ( 0)   PDF (395KB) ( 573 )  
相关文章 | 计量指标
异常检测是目前入侵检测领域研究的热点内容.提出一种新的基于系统调用和Markov链模型的程序行为异常检测方法,该方法利用一阶齐次Markov链对主机系统中特权程序的正常行为进行建模,将Markov链的状态同特权程序运行时所产生的系统调用联系在一起,并引入一个附加状态;Markov链参数的计算中采用了各态历经性假设;在检测阶段,基于状态序列的出现概率对特权程序当前行为的异常程度进行分析,并根据Markov链状态的实际含义和程序行为的特点,提供了两种可选的判决方案.同现有的基于隐Markov模型和基于人工免疫原理的检测方法相比,提出的方法兼顾了计算成本和检测准确度,特别适用于在线检测.该方法已应用于实际入侵检测系统,并表现出良好的检测性能.
一个安全的动态门限签名体制
李慧贤, 蔡皖东, 庞辽军,
2007, 44(9):  1545-1549. 
摘要 ( 405 )   HTML ( 0)   PDF (285KB) ( 449 )  
相关文章 | 计量指标
现有大多数门限签名体制存在一个共同的问题:门限值是固定的,这限制了它们的应用范围.基于离散对数计算问题的困难性提出了一个动态门限签名体制,有效地解决了上述问题.该体制允许在群体中共享多个组密钥,每个组密钥对应一个不同的门限值;可以根据文件的重要性而灵活地选取不同的门限值进行门限签名;每个签名者仅需保护一个签名密钥和一个秘密值;且不需要任何公共信息.分析表明,与已有体制相比,提出的体制能够抵御内部或外部攻击者的各种攻击,并可防止联合欺诈行为的发生,具有更好的安全性和实用性.
一种基于正反馈的对等网络拓扑获取方法
王 勇 云晓春 李奕飞 王晓锋
2007, 44(9):  1550-1556. 
摘要 ( 328 )   HTML ( 0)   PDF (415KB) ( 374 )  
相关文章 | 计量指标
精确有效的对等网络测量方法是解决其建模和网络设计优化难题的重要基础.对等网络是Internet上的一层覆盖网络,网络协议多样,节点及节点间的关系变化迅速,获得精确完整的对等网络拓扑数据面临很大困难.研究对等网络协议特点、分析特定的对等网络结构实体成为认识对等网络拓扑特性的一种可选研究方案.以Gnutella网络为测量对象,构造了正反馈结构的分布式Gnutella拓扑测量系统D-crawler;分析了系统实现中的主要算法;定义了拓扑数据准确性和完整性评价指标;实验验证了测量系统的性能.实验结果表明,D-crawler系统具有较好的节点信息获取速度,能够得到反映Gnutella网络特征的拓扑数据,数据准确.
基于DHT的拓扑感知节点聚集算法
段翰聪, 卢显良, 唐 晖, 周 旭, 赵志军,
2007, 44(9):  1557-1565. 
摘要 ( 508 )   HTML ( 0)   PDF (552KB) ( 529 )  
相关文章 | 计量指标
在文件共享、流媒体和协作计算等P2P应用模型中,节点间采用单播通信并构建出对应的覆盖网络.由于覆盖网络通常建立在已有的底层网络之上,节点随机加入系统将导致上下层网络拓扑不匹配,不仅增加了节点间通信延时而且给底层网络带来较大的带宽压力.当前的拓扑匹配算法尚存在可扩展性低、节点聚集时延长等问题.在网络坐标算法和DHT算法基础之上,提出一种分布式的拓扑感知节点聚集算法TANRA,利用等距同心圆簇对节点二维网络坐标平面进行等面积划分,并根据节点所处区域进行多层命名空间中区间的一一映射.由于保留了节点之间的邻近关系,从而可使用DHT基本的“发布”和“搜索”原语进行相邻节点聚集.仿真结果表明,TANRA算法在大规模节点数时能有效保证网络拓扑匹配,并且具有较低的加入延时.
基于幂律分布和小世界特性的无结构P2P网络中搜索方法研究
汤大权 贺明科 孟庆崧
2007, 44(9):  1566-1571. 
摘要 ( 363 )   HTML ( 0)   PDF (373KB) ( 544 )  
相关文章 | 计量指标
目前无结构P2P系统得到了大量的应用,但其常用的基于简单flooding机制的信息资源搜索方法造成了严重的通信消耗.基于P2P网络的幂律分布和小世界特性,通过对复杂网络幂律特性产生机制的分析并借鉴人际传播中谣言传播机制,提出了一种结合择优连接机制和谣言传播中兴趣衰减机制的信息资源搜索方法.其中择优连接是导致复杂网络幂律特性产生的机制之一,而谣言传播中的兴趣衰减机制适合于聚合网络中的信息传播.分析和仿真结果表明,提出的搜索方法可以有效地减少无结构P2P网络中信息搜索的通信开销.
网格环境下一种可调目标的启发式调度策略
丁 丁 罗四维 高 瞻
2007, 44(9):  1572-1578. 
摘要 ( 341 )   HTML ( 1)   PDF (448KB) ( 422 )  
相关文章 | 计量指标
针对网格环境下不同类型的任务执行时间相差较大的问题,提出了基于任务平均执行时间的忍耐度的概念,重新构造了启发式规则,体现了任务QoS的要求;并将这种服务质量的需求与任务完成时间相结合,给出了一个可调节的局部目标函数,实现了一种基于任务完成时间和任务服务质量的启发式调度算法OA-Sufferage;最后,给出了服务率(service ratio)的概念和定义,定量地衡量任务得到的服务质量.实验结果表明,该策略优先调度那些等待时间相对于执行时间较大的任务,提高了任务的服务率;而且可以通过调节局部目标函数中的偏好因子(preference factor),追求任务完成时间和QoS的不同目标,更加适合开放复杂的网格环境.
大规模复杂场景交互绘制技术综述
吴玲达 高 宇 魏迎梅
2007, 44(9):  1579-1587. 
摘要 ( 359 )   HTML ( 1)   PDF (389KB) ( 618 )  
相关文章 | 计量指标
大规模复杂场景的快速绘制是虚拟现实、实时仿真和三维交互设计等许多重要应用的底层支撑技术,也是诸多研究领域面临的一个基本问题.随着近几年三维扫描和建模技术的飞速发展,三维场景的规模和复杂度不断增大,大规模复杂场景的交互绘制受到了国内外研究者越来越多的重视并取得了一系列研究成果.首先简要回顾了大规模复杂场景交互绘制的研究进展情况;然后通过对其中涉及的主要关键技术进行总结分析,并对国内外典型的绘制系统进行比较和分类,阐述了大规模复杂场景交互绘制的主要研究内容,给出了大规模复杂场景交互绘制系统所应包含的基本组成部分和一般框架;最后对今后的发展方向做出了展望.
一种流体艺术风格的自适应LIC绘制方法
钱小燕, 肖 亮, 吴慧中,
2007, 44(9):  1588-1594. 
摘要 ( 352 )   HTML ( 0)   PDF (555KB) ( 481 )  
相关文章 | 计量指标
把LIC算法应用到非真实感绘制中,提出一种自适应流体艺术图的LIC绘制方法.对源图像亮度分量计算切矢量场,然后对其进行增强、平滑处理获得结构矢量场;通过随机扰动源图像获得纹理参考图像;根据结构矢量场和纹理参考图像的局部特征产生可变的LIC积分步长和步数,自适应地处理纹理参考图像;最后对绘制效果进行颜色渲染,生成具有丰富颜色特征的流体艺术图.实验表明,该方法能够较好地模拟诸如梵高画的流体艺术风格,呈现生动、灵活的波动感.
基于高斯混合模型的活动轮廓模型脑MRI分割
陈允杰, 张建伟, 韦志辉, 夏德深, 王平安,
2007, 44(9):  1595-1603. 
摘要 ( 453 )   HTML ( 0)   PDF (529KB) ( 501 )  
相关文章 | 计量指标
传统的活动轮廓模型用于图像分割往往基于目标的边界信息,在图像含有强噪音或目标具有弱边界时很难得到真实解.引入高斯混合模型构造新的约束项,在新的约束项作用下模型可以减少噪音的影响,并防止从弱边界泄漏.高斯混合模型求解通常使用Expectation-maximization(EM)算法,该算法是局部优化算法,且对初值敏感.因此引入粒子群算法,并提出一种改进的算法,利用该算法的全局优化性求解高斯混合模型的参数,以提高参数精度.对脑核磁共振图像(MRI)分割实验表明该模型具有较好的分割效果.
基于柱坐标B样条活动曲面模型的3D分割方法
汤 敏, 汤 杨, 徐立中, 王平安, 夏德深,
2007, 44(9):  1604-1611. 
摘要 ( 412 )   HTML ( 0)   PDF (605KB) ( 512 )  
相关文章 | 计量指标
基于长轴和短轴系列核磁共振图像重建3D左心室内外表面是提取左心室基本形态参数以及左心室运动分析的基础.提出了柱坐标B样条主动表面(CBAS)模型,将其用于3D分割左心室内外膜表面. CBAS模型的等参曲线网格由B-snake模型组成,根据短轴、长轴成像平面在3D空间中的位置关系,网格中的节点在两幅短轴及长轴图像上寻找对应的边缘点,节点间的采样点则在单一的短轴或长轴图像上获得图像能量.首先利用改进的模糊Hough变换确定短轴图像中左心室心肌内外轮廓的大致位置,其次用其构建柱坐标B样条主动曲面模型的初始表面.对左心室表面的分割过程在柱坐标下进行,使得模型在SA图像及LA图像上形状的改变能够统一为一个参数的变化,减小了模型的复杂度.最后通过与手工分割结果的线性回归分析证明了方法的准确性.
一种基于数据垂直划分的分布式密度聚类算法
倪巍伟, 陈 耿, 孙志挥,
2007, 44(9):  1612-1617. 
摘要 ( 395 )   HTML ( 0)   PDF (362KB) ( 489 )  
相关文章 | 计量指标
聚类分析是数据挖掘领域的一项重要研究课题,对大数据集的聚类更以其数据量大、噪声数据多等而成为一个难点.针对数据垂直划分的情况,提出连通点集及局部噪声点集等概念.在分析局部噪声点集与全局噪声点集以及局部连通点集与全局连通点集关系的基础上,对全局噪声点进行有效过滤,进一步设计闭三角链表结构存储各个结点的聚类中间结果,提出了基于密度的分布式聚类算法DDBSCAN.理论分析和实验结果表明,算法可以有效解决垂直划分的大数据集聚类问题,算法是有效可行的.
基于单元区域的高维数据聚类算法
谢坤武 毕晓玲 叶 斌
2007, 44(9):  1618-1623. 
摘要 ( 431 )   HTML ( 2)   PDF (357KB) ( 449 )  
相关文章 | 计量指标
高维数据空间维数较高,数据点分布稀疏、密度平均,从中发现数据聚类比较困难,而用基于距离的方法进行高维数据聚类,维数的增多会使得计算对象间距离的时间开销增大. CAHD(clustering algorithm of high-dimensional data)算法首先采用双向搜索策略在指定的n维空间或其子空间上发现数据点密集的单元区域,然后采用逐位与的方法为这些密集单元区域进行聚类分析.双向搜索策略能够有效地减少搜索空间,从而提高算法效率,同时,聚类密集单元区域只用到逐位与和位移两种机器指令,使得算法效率得到进一步提高.算法CAHD可以有效地处理高维数据的聚类问题.基于数据集的实验表明,算法具有很好的有效性.
小规模情感数据和大规模中性数据相结合的情感韵律建模研究
邵艳秋, 穗志方, 韩纪庆, 王志伟,
2007, 44(9):  1624-1631. 
摘要 ( 359 )   HTML ( 0)   PDF (414KB) ( 508 )  
相关文章 | 计量指标
建立好的情感韵律模型是合成情感语音的重要环节,而在情感语音的研究过程中,一个必须面对的现实问题就是通常情感数据量相比于中性数据量要少得多.将一个含有高兴、生气、悲伤3种情感语音的小规模数据库和一个较大规模的中性语音数据库相结合,进行情感韵律建模研究.对影响情感的韵律参数进行了分析,建立了基于人工神经网络的情感韵律模型.针对情感数据量相对于中性数据量的不足而导致的过拟合现象,提出了3种解决办法,即混合语料法、最小二乘融合法和级联网络法.这些方法都在不同程度上扩大了情感语料的作用,使得情感预测效果都有所提高.尤其是级联网络法,将中性模型的结果作为级联网络的一个输入,相当于扩大了情感模型的特征空间,更加强化了情感模型各输入特征的作用,在3种情感的各韵律参数生成中效果是最好的.