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

当期目录

2008年 第45卷 第6期    出版日期:2008-06-15
论文
项目优化调度的多智能体社会进化算法
潘晓英 焦李成
2008, 45(6):  . 
摘要 ( 369 )   PDF (595KB) ( 593 )  
相关文章 | 计量指标
结合多智能体系统、进化算法以及关系网模型,提出了一种多智能体社会进化算法用于求解项目活动的一个最优调度顺序以使整个工程的工期最短.每个智能体生存于环境中,为了增加自身能量将与其邻域展开竞争及协同操作,同时可利用自身的知识进行自学习来增加能量.根据项目优化调度的问题特点,设计了智能体的竞争行为、协同行为以及自学习行为.通过对PSPLIB中的标准问题进行测试,同时与其他启发式算法相比较的仿真实验结果表明该算法具有良好的性能,能在较短的时间内寻找到十分接近“最优解”的调度序列.
DTN网络的延时模型分析
周晓波 周 健 卢汉成 洪佩琳
2008, 45(6):  . 
摘要 ( 385 )   PDF (896KB) ( 641 )  
相关文章 | 计量指标
DTN(delay-tolerant network)是从ad hoc, WSN(wireless sensor network)等自组织无线网络中抽象出来的一种网络模型.其典型特征是节点之间的链路间歇性中断且中断持续时间较长,以至于在任意时刻源节点和目的节点间可能不存在路径.人们对DTN的研究尤其是对路由机制的研究已经很深入,但是作为路由算法所依赖的重要信息——延时——的分析模型还没有建立起来.从DTN数据包的投递过程出发,建立起DTN的延时模型,并利用排队论的相关知识进行分析,找出系统中各特征参数之间的关系,给出一般的结论.并对某些情形进行仿真,实验的数据显示理论结果和仿真数据拟合的很好.
基于信息素模因的免疫克隆选择函数优化
戚玉涛 刘 芳 焦李成
2008, 45(6):  . 
摘要 ( 307 )   PDF (675KB) ( 519 )  
相关文章 | 计量指标
学习进化经验并用于指导进化对人工免疫算法这样的随机搜索类算法十分重要. Memetic算法在进化算子中引入局部搜索,算法的学习机制决定哪种局部搜索机制适合目标问题.然而,这类算法需要使用者事先提供问题相关的局部搜索策略.为了克服Memetic算法的这一缺点,针对函数优化问题提出了一种基于蚁群信息素的无指导的学习机制,并在此基础之上构造了基于信息素模因的克隆选择算法.算法无需提供候选的局部搜索策略(即模因),学习的内容是抗体的进化趋势,而并非要确定合适的局部搜索策略.实验结果表明,信息素模因学习机制借助信息素浓度的收敛学习到了关于目标函数的有用信息,有效提高了克隆选择算法的搜索效率.
一种基于程序段的动态电压缩放算法
彭蔓蔓 李仁发 王宇明
2008, 45(6):  . 
摘要 ( 420 )   PDF (753KB) ( 469 )  
相关文章 | 计量指标
动态电压缩放技术是一种能有效优化处理器能耗的方法,它允许处理器在运行时动态地改变其时钟频率和供电电压.针对处理器提出了一种基于程序段的动态电压缩放算法PBVSA,该算法使用建立在指令工作集签名基础上的程序段监测状态机来判断程序段是否发生变化,并作出CPU电压和频率调整决定.在程序段内,通过计算该段的频率缩放因子β (片外工作时间与片上工作时间的比例关系)来设定CPU的电压和频率.在sim-panalyzer模拟器上完成了算法的实现.通过对Mibench测试程序集的测试表明:该算法平均降低了处理器29%的能耗,而性能损失平均为5.3%.
融合多特征的最大熵汉语命名实体识别模型
张玥杰 徐智婷 薛向阳
2008, 45(6):  . 
摘要 ( 696 )   PDF (721KB) ( 857 )  
相关文章 | 计量指标
最大熵模型能有效整合多种约束信息,对于汉语命名实体识别具有很好的适用性.因此,将其作为基本框架,提出一种融合多特征的最大熵汉语命名实体识别模型.该模型集成局部与全局多种特征,同时为降低搜索空间并提高处理效率,而引入了启发式知识.基于SIGHAN 2008命名实体评测任务测试数据的实验结果表明,所建立的混合模式是一种组合统计模型与启发式知识的有效汉语命名实体识别模式.基于不同测试数据的实验说明,该方法针对不同测试数据源具有一致性.
一种新的P2P系统中基于双ratings的声誉管理机制
金 瑜 古志民 班志杰
2008, 45(6):  . 
摘要 ( 338 )   PDF (998KB) ( 464 )  
相关文章 | 计量指标
声誉系统的效率取决于回馈的质量,现有P2P系统中的声誉模型不能处理合谋、不递交ratings等攻击,并且对无过失节点还存在不公平性.针对这些问题,提出了一个新的基于双ratings的声誉管理机制.采用两个度量来评价节点:服务信任和回馈信任.服务信任反映server提供服务的可靠性;回馈信任反映consumer汇报ratings的可信度.一次交易后,要求服务双方都递交ratings,依据这两个ratings对server的服务信任和consumer的回馈信任进行更新,并且server的服务信任更新与consumer的回馈信任紧密相关.为了防止恶意节点反复实施恶意行为或不递交rating,还提出了一个惩罚机制,作为对声誉模型的补充.仿真表明,提出的声誉管理机制能够抵制上述恶意攻击,减少不公平性.
一种工作流安全策略分析方法
刘道斌 郭 莉 白 硕
2008, 45(6):  . 
摘要 ( 376 )   PDF (713KB) ( 528 )  
相关文章 | 计量指标
工作流系统中经常会发生来自系统内部人员的欺骗活动,职责分离是一种有效地防止内部欺骗的安全机制.讨论了工作流执行时的安全策略问题,给出了工作流直观的Petri网模型描述,Petri网模型清晰地刻画了工作流系统中所包含的任务以及任务与角色的对应关系.采用Prolog语言描述了工作流执行时的动态职责分离安全规则,在此基础上,运用逻辑推理的方法分析职责分离安全规则,目的是找出所有满足安全规则的有效执行链.通过分析找出所有满足安全规则的有效执行链.
基于无干扰理论的可信链模型
赵 佳, 沈昌祥, 刘吉强, 韩 臻,
2008, 45(6):  . 
摘要 ( 474 )   PDF (689KB) ( 599 )  
相关文章 | 计量指标
可信计算的相关研究已成为当前国内外信息安全方面的研究热点和趋势之一.可信计算技术也成为构建安全计算机系统行之有效的新技术.目前可信计算理论的发展滞后于技术的发展,针对可信计算中可信链传递缺乏理论模型的问题,将无干扰理论引入到可信计算领域,提出了计算机系统可信的基本理论.从动态的角度建立了基于无干扰理论的可信链模型,并对该模型进行了形式化描述和验证,而且实现了基于Linux操作系统内核的可信启动过程.其实现思路对于可信计算理论的发展和应用具有很好的参考价值.
规划图框架下用遗传算法求解时态规划问题
伍丽华, , 陈蔼祥, 姜云飞,
2008, 45(6):  . 
摘要 ( 331 )   PDF (938KB) ( 441 )  
相关文章 | 计量指标
许多现实世界中的规划问题通常希望规划目标能在尽可能短的时间内实现,并且规划动作的执行需要考虑时间因素.在规划图框架下,提出了一种能进行时态约束推理的遗传规划算法.主要工作有以下3个方面:1)介绍基于完全动作图的时序约束推理技术;2)提出能进行时序约束推理的基于规划图的遗传规划技术;3)针对基于规划图的遗传规划技术存在局部搜索能力不足的缺点,提出了在原有遗传操作算子的基础上,引入局部修复算子的混合规划技术.实验表明,这种算法能有效地处理一类时态规划问题.
一种模块化2DPCA和CSLDA相结合的人脸验证算法
袁 宁, 吴小俊, 王士同, 杨静宇, Josef Kittler,
2008, 45(6):  . 
摘要 ( 481 )   PDF (761KB) ( 502 )  
相关文章 | 计量指标
在CSLDA方法的基础上进行改进,和模块化2DPCA相结合,提出了一种模块化2DPCA+CSLDA的人脸验证方法.CSLDA将图像矩阵转化为向量进行处理,数据维数很大,计算复杂,对图像整体处理没有考虑到图像的局部特征.针对这些缺点,新方法从原始数据出发,对二维数据进行分块后采用2DPCA进行特征抽取,能有效抽取图像的局部特征,得到替代原始图像的低维的新模式.然后对新模式施行CSLDA,即基于客户相关子空间的线性判别分析方法,不仅考虑到类内、类间的差异,弥补了PCA的缺陷;而且客户相关(CS)子空间可以较好地描述不同个体人脸之间的差异性,比传统的个体特征脸具有更好的判别能力.在XM2VTS人脸库上按照Lausanne协议和ORL库上对原CSLDA和新方法进行评价和测试的结果表明, 新方法在验证效果上优于CSLDA方法.
一种基于模糊提取的虹膜鉴别方案
张 凡, 冯登国, 孙哲南,
2008, 45(6):  . 
摘要 ( 397 )   PDF (751KB) ( 545 )  
相关文章 | 计量指标
模糊提取从生物特征输入中以容错的方式可靠地提取出均匀分布的随机密钥,当输入发生变化且变化很小时,该密钥可以保持不变.研究了当汉明距离作为生物特征匹配的度量标准时,结合纠错编码学与传统密码学实现模糊提取的虹膜鉴别方法,分析了虹膜特征编码之间的差异对正确鉴别性能的影响,设计了重复码和Reed-Solomon码的两层级联纠错编码方案,并对128只虹膜的各3个样本进行了模拟实验.所给方案使用户虹膜特征模板的安全性和隐私性得到了有效保护,并能够支持用户虹膜的注册更新.此外,实验表明该方案同时具有较理想的识别性能.
基于n边形折叠的网格简化算法
陈华鸿, 罗笑南, 凌若天, 马建平,
2008, 45(6):  . 
摘要 ( 694 )   PDF (1372KB) ( 442 )  
相关文章 | 计量指标
提出在三角网格中利用多个三角形组合及检索n边形(n为正整数)的规则,并提出一种具有相似折叠规律的n边形折叠的网格简化算法,该算法以n边形折叠为基本简化操作,并以二次误差作为误差度量,每次n边形折叠操作可以减少n-1个顶点以及2(n-1)个三角形,n越大达到某一简化目标所需的折叠次数越少,因此简化速度也可能越快.通过选取适当的n值及新顶点位置,新算法可以转化成顶点删除、边折叠及三角形折叠3种已知的几何元素删除算法,因此也可以视做为基于二次误差度量的几何元素删除简化算法的总括算法.最后分别对几种n取值情况列举实验数据,说明该算法的有效性.
无内部冲突数据库模式满足P\-3及无β环判定问题研究
郝忠孝, 顾照鹏,
2008, 45(6):  . 
摘要 ( 326 )   PDF (516KB) ( 478 )  
相关文章 | 计量指标
通过分析在FD集F的最小归并依赖集D无弱左部冲突、弱右部冲突时相邻归并依赖所具有的性质和特征,提出了左部集冲突、蕴含集间冲突和主归并依赖冲突等概念,在此基础上证明了在FD集F无内部冲突且最小归并依赖集D中存在弱左、右部冲突、左部集冲突、蕴含集间冲突和主归并依赖冲突时模式分解为满足P\-3为有β环的结论,并给出了左部集冲突、蕴含集间冲突和主归并依赖冲突的判定算法及分析,为进一步研究无β环的分解奠定了基础.
基于XML索引技术的有效外延连接
姜学锋, 衡星辰, 覃 征, 邵利平,
2008, 45(6):  . 
摘要 ( 377 )   PDF (1269KB) ( 428 )  
相关文章 | 计量指标
首先给出了XML文档树、元素外延和名字路径等的形式化定义.接着,将编码方案、路径索引和名字外延的思想相结合,提出了一种改进的XML数据的索引结构(类型索引集、名字索引集和外延索引),解决了基于传统索引技术的XML数据查询方法性能上的不足.它既可以有效地支持结构连接的计算以快速地判断任意结点之间的子孙后代关系,也可以有效地支持基于名字外延的路径连接算法以快速地判断任意结点之间的父子关系,然后还可以快速地支持对包含拥有关系的小枝查询;进而给出了基于该索引结构的外延连接算法,并着重对其处理含有父子关系和拥有关系等较复杂的XPath查询路径的不同处理过程进行了对比和分析,使得对于一条长度为n的XPath绝对路径查询,最多只需要n/2-1次外延连接,且能够根据双亲结构信息等利用外延索引尽可能跳过不需要参与连接的结点.实验结果表明,提出的新的索引结构可以有效地提高查询处理的性能.
具有多时间粒度的强全序时态模式中多值依赖问题研究
万 静, 郝忠孝,
2008, 45(6):  . 
摘要 ( 396 )   PDF (660KB) ( 488 )  
相关文章 | 计量指标
在时态数据库中存在着与时态多值依赖相关的存储冗余、更新异常等问题.但由于时态多值依赖的复杂性,使得根据时态多值依赖所进行的范式分解并不能总保持无损联接,为此对强全序时态模式中时态多值依赖与无损分解的相关性进行了深入研究,给出了规则的时态多值依赖(RTMVD)和属性集的时间粒度等概念,并给出了RTMVD的一套有效的推理规则,针对强全序时态模式中时态多值依赖与无损分解的相关性给出了相关定理,解决了规则的时态多值依赖环境下时态模式在多粒度上的无损分解问题,为规则时态多值依赖环境下时态模式的进一步规范化奠定了基础.
结合信任机制的移动IPv6网络快速跨域认证方法
张 娇, 张玉军, 张瀚文, 李忠诚,
2008, 45(6):  . 
摘要 ( 467 )   PDF (1186KB) ( 529 )  
相关文章 | 计量指标
在移动IPv6(MIPv6)网络中,当移动用户从外地域接入网络时,家乡域和接入域需要协作实现对移动用户的身份认证,各管理域之间存在域间信任关系是域间协作实现用户身份认证的基础.现有MIPv6网络快速认证方法在实施域间认证的过程中忽略了域间信任关系,由于缺乏域间信任而造成的认证失败在整个认证流程结束以后才能被检测到.提出一种结合信任机制的MIPv6网络快速跨域认证方法,其中在预切换阶段考虑移动用户家乡域和接入域之间的信任关系,通过移动用户和接入网络的一次交互实现用户和接入域的有效双向认证,并设计了域间信任关系的动态维护机制.基于组合公钥(CPK)算法设计了网络实体的身份签名和验证方案,用于加速双向认证过程.理论分析和数值分析结果表明,提出的方案比现有方案在减少总认证切换延时和信令开销方面更有效.同时基于CPK算法的安全性,提出的方案在有效实现用户和网络的双向认证的同时可以保证私钥的保密性和签名的不可伪造性.
I/O负载自相似研究综述
李明强 舒继武
2008, 45(6):  . 
摘要 ( 434 )   PDF (1525KB) ( 492 )  
相关文章 | 计量指标
研究I/O负载特征,建立恰当的I/O负载模型,对存储系统的设计、优化和评估有重要的意义.通过研究发现,许多I/O到达模式和访问模式在不同尺度下都具有相似的“突发性”.而传统的泊松模型不具有这种特点,因此,研究者提出用自相似模型来描述I/O负载.此外,虽然自相似模型能够较好地描述I/O负载的长相关性,但是,它们却难以描述较小尺度上的局部奇异行为.于是,一些研究者提出用多分形模型来弥补这一缺陷.总结了目前I/O负载自相似研究的成果,分析了I/O负载自相似的研究现状,探讨了I/O负载自相似研究的发展趋势.通过分析得出,目前,自相似的评估问题还未被完全解决,I/O负载的自相似性在存储系统设计中的意义的研究还需要更深入,另外,如何建立更准确高效的I/O负载多分形模型也是一个还需要更深入研究的方面.
一款基于多处理器片上系统的动态自适应仲裁器
徐 懿, 李 丽, 杜高明, 张宇昂, 张 冰, 高明伦,
2008, 45(6):  . 
摘要 ( 381 )   PDF (1435KB) ( 593 )  
相关文章 | 计量指标
随着深亚微米工艺技术的发展,同一芯片上集成多个处理器得以实现.通信架构是多处理器片上系统的瓶颈,而高效的仲裁器可以解决多个处理器同时访问共享资源引起的冲突和竞争,从而防止系统性能的下降.提出一款算法简单的动态自适应仲裁器.它可以自动调节各个处理器占据的总线带宽,避免饥饿现象.基于多处理器仿真平台的实验结果显示它比传统的仲裁器减少了68%的任务完成时间,缩短了78%的总线等待时间,并且能更好地控制各处理器的总线带宽.
基于Contourlet的中低码率图像质量可分级编码算法
肖 羽 王相海
2008, 45(6):  . 
摘要 ( 269 )   PDF (2248KB) ( 443 )  
相关文章 | 计量指标
首先对图像Contourlet变换各子带系数的分布情况进行了统计分析,进而给出了一种基于Contourlet变换的空间方向树结构,并统计验证了该空间方向树的“零树”特性.同时针对图像Contourlet变换各子带“重要系数”的分布情况提出了一种基于图像Contourlet方向子带的多尺度量化方案.该方案对图像的边缘方向信息和纹理信息具有很好的捕捉能力.在此基础上提出了一种基于Contourlet变换的嵌入式图像质量可分级编码算法.该算法除了具有一般基于小波变换的零树编码方法的特性外,还具有方向性和各向异性的特点,其解码图像在中低码率下无论是PSNR还是纹理和边缘区域的视觉效果均优于SPIHT算法.实验结果验证了所提出算法的有效性.
移动P2P网络路由策略中模糊知识处理的研究
牛新征 佘 堃 秦 科 周明天
2008, 45(6):  . 
摘要 ( 245 )   PDF (1311KB) ( 449 )  
相关文章 | 计量指标
由于移动P2P网络的动态多变以及移动用户的频繁移动,以合作为基础的移动agent所携带的路由信息是不确定的,非实时的、模糊的.同时,这种交互得到的间接路由信息,更加具有不完整性甚至欺骗性.通过进行移动agent合作模型的设计和移动agent所携带路由信息的模糊知识处理的研究,并利用模糊知识处理方法学的支持,提出了一种从移动agent所携带的模糊知识中分析和过滤出较准确和有价值路由数据的算法, 在模糊的路由知识中找到能如实反映网络的路由信息,以此提供移动节点以及移动agent使用.通过实验仿真证明,该算法有效减小了平均端到端时延和路由开销,增加了分组投递率和建立连接的移动节点数目.同时,可以较好处理移动agent中模糊的路由信息,对路由策略性能有较大的提高.
全部到全部组播的核管理机制及其算法研究
徐 云, 鄢冰峰, 陈国良,
2008, 45(6):  . 
摘要 ( 283 )   PDF (737KB) ( 463 )  
相关文章 | 计量指标
组播是因特网上的重要应用和具有挑战性的研究问题,现在大多数已有的组播算法是基于有源树的,存在带宽利用率和传输效率问题.有核组播是在网络中选取一个核节点,并以它作为根来建立一棵连接组播组中所有成员节点的单一共享树,而不是为每个源节点建立一棵组播树,这是一种有效的方法.由于核节点选择的不同将导致组播树的不同,核节点实际上决定着有核组播的性能.因此,核选择及核迁移是有核组播里的两个重要问题.针对全部到全部的组播模型,先给出了一个以总代价最优为目标的核选择完全算法,该算法复杂度较低;然后针对实时应用设计了两个核选择近似算法,并分析了它们的近似比;最后提出了一种可扩放的核迁移算法,该算法中的树代价估算机制为核节点的迁移时机提供了一个可信的评价标准.