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

当期目录

2007年 第44卷 第2期    出版日期:2007-02-15
论文
基于合作博弈的移动代理网管任务协作模型
卞正皑 刘 波 罗军舟
2007, 44(2):  193-200. 
摘要 ( 402 )   HTML ( 0)   PDF (490KB) ( 414 )  
相关文章 | 计量指标
为提高网络管理任务性能,需要研究在复杂网管任务下多移动代理协作问题.由于传统代理协作模型(如合同网协议)并不适合大规模网络中复杂任务的代理协作,不能保证协作模型中个体代理性能的稳定.为此合作博弈理论成为移动代理的网管任务协作问题的重要途径,在该协作模型中,单个功能代理被视为具有自主意识的主体,它具有自身的效用函数评估个体的性能.将代理协作问题转化成为凸联盟博弈模型并利用Shapley值作为协作模型中任务分配合理性的评判标准,并基于上述理论模型,提出3阶段的任务协作算法.
自适应的PIP主动队列管理机制
刘 明 窦文华 张鹤颖
2007, 44(2):  201-207. 
摘要 ( 461 )   HTML ( 1)   PDF (500KB) ( 386 )  
相关文章 | 计量指标
近年来AQM的研究者提出了多种主动队列管理机制,包括RED,PI,REM,AVQ,PD,SMVS,PIP等,它们之间的主要区别在于丢弃概率的计算方法不同,其中基于反馈校正的PIP是综合性能更为突出的一种算法,但是遗憾的是其参数不能实现自动配置.结合单神经元自适应PID控制器,为PIP算法建立了自适应的模型,提出一种参数自适应的PIP算法.通过NS2仿真实验,验证了该算法能提高链路利用率和降低报文丢失率,有效缓解了根据特定网络条件配置算法参数的问题.结合PI,REM,AVQ,PD等AQM算法,讨论了该自适应模型在其他AQM机制中的推广.
交换式以太网物理拓扑结构的自动发现
孙延涛, 石志强, 吴志美,
2007, 44(2):  208-215. 
摘要 ( 459 )   HTML ( 0)   PDF (467KB) ( 566 )  
相关文章 | 计量指标
准确及时的拓扑结构信息是网络性能监测与评估、故障发现与定位、资源分配与管理等一系列维护工作的基础.交换式以太网是目前局域网的主要组网方式,其拓扑结构被看做为一棵拓扑树,并把网络节点之间的连接关系分为直系关系和旁系关系,给出一组判定定理用以确定网络节点之间的连接关系.基于上述定理,提出了一个新的拓扑发现算法,该算法能够利用不完整的地址转发表构造出整个网络拓扑结构.该算法已成功地应用于社区宽带综合业务网络管理系统(CBISNMS)中.
传感器网络中一种基于链路稳定性和多路径的拓扑控制算法
吴震东 李善平
2007, 44(2):  216-222. 
摘要 ( 399 )   HTML ( 0)   PDF (385KB) ( 417 )  
相关文章 | 计量指标
通过压缩邻居节点集合的势,进而调整网络拓扑结构的拓扑控制方法,可以提高传感器网络的能量效率.然而现有的拓扑控制方法尚没有充分地考虑链路不稳定性因素,以及如何在提高能量效率的同时改善负载均衡.在对链路损失模型进行分析的基础上,考察了能量效率、负载均衡和邻居节点集的势之间的关系.发现在同时改善能量效率和负载均衡之间有一对矛盾.提出了一个分层的拓扑控制算法LELB(layered energy-efficient and load balance algorithm),可以在链路不稳定的情况下进一步改善能量效率,同时获得更好的负载均衡.仿真结果表明,LELB算法对网络性能有很好的改善.
基于机器学习的动态信誉评估模型研究
陈菲菲 桂小林
2007, 44(2):  223-229. 
摘要 ( 393 )   HTML ( 0)   PDF (432KB) ( 871 )  
相关文章 | 计量指标
为在开放网络环境中建立资源消费者(用户)和资源提供者(主机)之间的信任关系,提出基于机器学习的动态信誉评估模型.模型中用户的信誉级别可以根据其行为和一些其他监测数据动态变化,而资源的信誉级别也可以根据用户对资源所提供服务的评价动态变化.给出了用于生成评估规则和信誉级别的模糊信誉级别评估算法(FTEA),算法采用基于规则的机器学习方法,具有从大量输入数据中自学习以获取评估规则的能力.实验结果表明,1000组输入数据能够生成理想的规则库,并且算法执行时间随输入判定因素数目成指数形式增长,因此需要选择5~6个因素和1000个左右的样本数据以进行系统实现.
一种针对弹性CA的分布式密钥产生方案
庄 湧冯登国
2007, 44(2):  230-235. 
摘要 ( 440 )   HTML ( 0)   PDF (339KB) ( 489 )  
相关文章 | 计量指标
弹性CA是一种使用入侵容忍技术保护CA密钥的CA系统,它采用了新的私钥分割方法加强了系统的安全性,但其使用的密钥分发中心却不利于CA私钥安全.分布式密钥产生方案就是在传统的弹性CA方案的基础上取消了密钥分发中心,使用分布式的密钥产生和分割机制,从而保证了在CA初始化和整个运行过程中,任意t-1(t为门限值)台服务器都不可能窃得CA私钥,大大加强了CA系统安全.
电子邮件UA与MTA间抗抵赖协议的研究与实现
夏春和, 刘 璀, 李肖坚, 陶 然,
2007, 44(2):  236-241. 
摘要 ( 480 )   HTML ( 0)   PDF (389KB) ( 409 )  
相关文章 | 计量指标
抗抵赖服务旨在生成、收集、维护已声明的事件或动作的证据,并以此证据解决关于某事件发生或未发生而引起的争议.抗抵赖协议借助密码学算法以实现抗抵赖服务.提出了一种用户代理与传输代理间的双方不可否认协议NRPUM,并将其封装到邮件传输协议SMTP与POP3中,以实现用户代理与传输代理间的邮件抗抵赖.经过分析以及实验验证,该抗抵赖方法能够完成用户代理与传输代理间的不可否认性.
基于PLSA模型的文本分割
石 晶 戴国忠
2007, 44(2):  242-248. 
摘要 ( 617 )   HTML ( 2)   PDF (438KB) ( 779 )  
相关文章 | 计量指标
文本分割在信息提取、文摘自动生成、语言建模、首语消解等诸多领域都有极为重要的应用.基于PLSA模型的文本分割试图使隐藏于片段内的不同主题与文本表面的词、句对建立联系.实验以汉语的整句作为基本块,尝试了多种相似性度量手段及边界估计策略,同时考虑相邻句重复的未登录词对相似值的影响,其最佳结果表明,片段边界的识别错误率为6.06%,远远低于其他同类算法.
基于桥接盟员的异类RTI和多联盟互连技术研究
蔡 楠 周 忠 吴 威
2007, 44(2):  249-257. 
摘要 ( 323 )   HTML ( 1)   PDF (575KB) ( 446 )  
相关文章 | 计量指标
高层体系结构(high level architecture,HLA)的互操作模式基于单一的联盟执行上下文,并未涉及不同RTI(run-time infrastructure)和联盟间的互操作及联盟级的互操作和重用.提出一种基于桥接盟员的异类RTI和多联盟的互连体系结构,据此设计实现了RTIBridge桥接软件,详细介绍其软件结构以及其中的关键技术问题,分析了桥接盟员执行RTI服务的典型流程,提出一种异类RTI和多联盟互连开发和执行过程模型,最后进行了实验与结果分析.
一种基于边缘特征的纸币污损检测方法
金 野 刘松波 刘家锋 宋 玲 唐降龙
2007, 44(2):  258-264. 
摘要 ( 445 )   HTML ( 0)   PDF (483KB) ( 833 )  
相关文章 | 计量指标
污损检测是纸币清分中的一个重要环节.针对纸币上常见的笔迹及撕裂污损,提出了一种基于图像边缘特征的检测方法.首先将待检测图像与参考图像进行图像配准,然后采用Kirsch算子提取两图像的边缘信息,并提出了一种符合人的主观感受的边缘强度差的计算方法,在此基础上提取的污损特征,对于图像中新增加的边缘信息十分敏感,而对各像素的灰度值、边缘强度值的相对变化则具有很强的抗干扰性.将纸币划分为若干个相互重叠的子区域,通过对子区域内污损特征统计,来判定该子区域内是否存在污损.实验证明,该方法识别率高且稳定、可靠,满足实际要求.该方法已应用到实际的纸币清分系统中.
汉语中方位参考点恢复研究
李晗静 李 生 赵铁军
2007, 44(2):  265-268. 
摘要 ( 300 )   HTML ( 0)   PDF (224KB) ( 369 )  
相关文章 | 计量指标
方位参考点恢复是自然语言空间语义理解中十分重要问题.方位参考点恢复是在篇章中找方位词的参考点并补充上,得到完整的空间表达式.目前,自然语言处理技术大多面向句子级,导致省略参考点空间表达式独立出现,使空间语义理解困难.方位参考点恢复无疑可以解决类似问题.在此提出基于有限知识的方位参考点恢复方法.在句法分析基础上,以知网为常识库,结合有限知识识别空间表达式以及恢复方位参考点.实验结果表明该方法比较令人满意.
上下文感知计算及系统框架综述
李 蕊 李仁发
2007, 44(2):  269-276. 
摘要 ( 850 )   HTML ( 1)   PDF (348KB) ( 1271 )  
相关文章 | 计量指标
当人们在与其他人或周围的环境交互时,常常会无意识地利用到诸如手势、眼神、情境、环境状况等上下文信息.与之相反,计算机系统却很少能有效地利用这些信息.但自Mark Weiser提出普适计算以来,如何有效利用上下文信息开始得到充分重视并发展成为一种新的计算模式——上下文感知计算.通过对近10年来上下文感知计算尤其是系统框架的发展进行综述和分析,提出了一个新的上下文感知计算系统框架概念模型,同时对该概念模型所涉及的关键技术问题进行了深入探讨,这可为感知计算的进一步研究提供指导.
论文
基于局部最优的联盟结构生成算法
苏射雄, 胡山立, 林超峰, 郑盛福,
2007, 44(2):  277-281. 
摘要 ( 379 )   HTML ( 0)   PDF (306KB) ( 375 )  
相关文章 | 计量指标
联盟形成是多Agent系统中的一个关键问题.针对多Agent联盟数量是Agent个数指数倍的问题,给出了基于局部最优Agent联盟结构生成算法——OCS算法.基于局部最优,将Agent联盟结构图化简,并利用划分所对应的一类联盟结构的上界对Agent联盟结构图进行剪枝,极大降低了搜索空间.接着证明了OCS算法的时间复杂性为O(3\+n),但在实验上已经接近O(23n/2).最后通过对比数据分析,表明了OCS算法的效率. OCS算法是对Rothkopf和刘惊雷等人相关工作的改进.
一种改进的频繁闭项集挖掘算法
宋 威, 杨炳儒, 徐章艳, 高 静,
2007, 44(2):  278-286. 
摘要 ( 334 )   HTML ( 0)   PDF (578KB) ( 445 )  
相关文章 | 计量指标
频繁闭项集惟一确定频繁项集且规模小得多,但挖掘频繁闭项集仍是很费时的.为提高挖掘效率,提出了一种改进的频繁闭项集挖掘算法DCI-Closed-Index. 该算法用“索引数组”来组织数据,通过为每个项目增加包含索引,找到频繁共同出现的项集.利用二进制位图技术,给出了一个求包含索引的快速算法.然后根据项目在包含索引中出现的频率由高到低进行排序,并利用包含索引作为启发信息,合并同时出现且支持度相等的频繁项,得到初始生成子,从而大大缩小了搜索空间.同时利用索引数组对每一个生成子的前序集和后序集进行约简,得到新的、较小的约简前序集和约简后序集.并证明了约简前序集和后序集与原来的前序集和后序集的功能是一样的.从而减少了候选生成子的集合包含判断的操作.实验结果表明,该算法的性能优于其他主流算法.
蚁群算法在移动Agent迁移中的应用研究
杜荣华, 姚 刚, 吴泉源,
2007, 44(2):  282-287. 
摘要 ( 279 )   HTML ( 0)   PDF (307KB) ( 391 )  
相关文章 | 计量指标
移动Agent提供了一种全新的分布计算范型.移动Agent技术给分布式系统的设计、实现和维护都带来了新的活力.旅行Agent问题是一类复杂的组合优化问题,目的在于解决移动Agent在不同主机间移动时如何根据移动Agent的任务和其他约束条件来规划最优的迁移路线.蚁群算法作为一种新的生物进化算法,具有并行、正反馈和启发式搜索等特点,是一种解决旅行Agent问题的有效手段,受到了广泛的关注,但它与其他进化算法一样存在易陷入局部最小的缺点.在蚁群算法的基础上,通过修改它的信息素轨迹更新规则,引入自适应的信息素挥发系数来提高收敛速度和算法的全局最优解搜索能力,从而使得移动Agent在移动时以最优的效率和最短的时间来完成迁移.仿真结果表明,改进的算法在解的性能和收敛速度上均优于相关算法.
基于主题语言模型的句子检索算法
吴友政 赵 军 徐 波
2007, 44(2):  288-295. 
摘要 ( 741 )   HTML ( 0)   PDF (443KB) ( 610 )  
相关文章 | 计量指标
提出了基于主题语言模型的汉语问答系统句子检索算法,该算法利用问答系统中特有的提问分类信息(即提问的答案语义信息)对句子初检结果进行主题聚类,通过Aspect Model将句子所属的主题信息引入到语言模型中,从而获得对句子语言模型更精确的描述.对于初检结果的聚类,提出了“一个句子多个主题”和“一个句子一个主题”两种算法.相对于PLSI算法的主题空间维度,提出的主题空间具有更加明确的物理意义;由于不需要迭代运算,运行速度更具优势.对比实验的结果表明,与标准语言模型方法相比,基于主题语言模型的方法可以明显地提高汉语问答系统句子检索模块的性能.
适应用户兴趣变化的协同过滤推荐算法
邢春晓, 高凤荣, 战思南, 周立柱,
2007, 44(2):  296-301. 
摘要 ( 892 )   HTML ( 24)   PDF (325KB) ( 1494 )  
相关文章 | 计量指标
协同过滤算法是至今为止最成功的个性化推荐技术之一,被应用到很多领域中.但传统协同过滤算法不能及时反映用户的兴趣变化.针对这个问题,提出两种改进度量:基于时间的数据权重和基于资源相似度的数据权重,在此基础上将它们有机结合,并将这两种权重引入基于资源的协同过滤算法的生成推荐过程中.实验表明,改进后的算法比传统协同过滤算法在推荐准确度上有明显提高.
模糊环境中工作流任务分配的多级模型
肖郑进 何钦铭 陈 奇
2007, 44(2):  302-309. 
摘要 ( 397 )   HTML ( 0)   PDF (442KB) ( 580 )  
相关文章 | 计量指标
对工作流实例中各用户型任务进行自动优化分配是提高工作流管理系统运行效率的关键技术之一.在详细分析了影响用户型任务分配的多种因素及其语意模糊性后,提出了一个可组合的任务分配多级模型以及相应的任务分配方法,详细讨论了具有自适应能力的影响因素权重设计方法.最后,通过与其他任务分配方法对比,分析了该任务分配方法的性能.
一种面向移动导航设备的电子地图空间索引结构
方 钰 蒋昌俊 陈 林
2007, 44(2):  310-316. 
摘要 ( 311 )   HTML ( 1)   PDF (441KB) ( 444 )  
相关文章 | 计量指标
传统的R-tree系列和四叉树系列对数据对象的多级显示没有给予足够的支持,在小比例尺地图的显示过程中,影响了检索效率.即使是支持多级显示的R-tree的各种变形,也由于对资源的要求而不能满足嵌入式设备的应用需求.针对嵌入式设备数据I/O的特点,从地图数据的分级显示、顺序与批量访问、索引数据的优化等多方面入手,提出了一种基于多级Hilbert网格的线性索引结构.实验证明该索引结构在空间利用率和查询性能等方面与传统的空间索引技术相比有明显的改善,并在上海市交通信息网格移动交通信息服务终端上获得了良好的实施效果.
IOMan:一种支持多操作系统远程启动和运行的I/O管理方法
夏 楠, 张尧学, 杨善林, 王晓辉,
2007, 44(2):  317-325. 
摘要 ( 449 )   HTML ( 0)   PDF (472KB) ( 354 )  
相关文章 | 计量指标
为了降低用户使用和维护计算机系统的成本,基于透明计算模式提出了一种工作在局域网环境下的I/O管理方法:IOMan. IOMan只是用软件方法在客户端设置磁盘I/O重定向机制,按需动态下载数据,而不需要修改当前常用的操作系统如Windows的启动机制,也不影响其他I/O操作,能够支持多种操作系统的远程启动和应用程序的运行. IOMan基于客户机/服务器模型,包括I/O Client和I/O Server两个部分,其中I/O Client工作在客户端,I/O Server工作在服务器端. I/O Client通过重新定义访问磁盘的BIOS中断处理程序以及创建虚拟本地磁盘,将I/O请求发送给服务器;I/O Server响应客户端请求,读写服务器上存储的虚拟硬盘文件,然后以扇区形式将数据发送给I/O Client.
实时协同工作系统中操作转换算法综述
廖 斌 何发智 荆树旭
2007, 44(2):  326-333. 
摘要 ( 611 )   HTML ( 6)   PDF (467KB) ( 515 )  
相关文章 | 计量指标
首先分析了实时协同工作系统中的事件关系,讨论了一致性模型及其收敛问题,然后以典型实时协同工作系统中操作转换算法的研究进展为线索,将算法中最核心的调度函数剥离出来,进行了详细的分析.对意图维护问题进行了解析,将其归结为在立即模式下对并发问题的处理,得出了意图维护问题在算法层面的准则.最后对基本转换函数和典型转换算法进行了归纳和总结,并对进一步研究方向进行了探讨.
SMP集群系统上矩阵特征问题并行求解器的有效算法
赵永华, 迟学斌, 程 强,
2007, 44(2):  334-340. 
摘要 ( 417 )   HTML ( 0)   PDF (422KB) ( 423 )  
相关文章 | 计量指标
对称矩阵三对角化和三对角对称矩阵的特征值求解是稠密对称矩阵特征问题并行求解器的关键步.针对SMP集群系统的多级体系结构,基于Householder变换的矩阵三对角化和三对角矩阵特征值问题的分而治之算法,给出了它们的MPI+OpenMP混合并行算法.算法研究集中在SMP集群系统环境下的负载平衡、通信开销和性能评价.混合并行算法的设计结合了粗粒度线程并行模式和任务共享的动态调用方法,改善了MPI算法中的负载平衡问题、降低了通信开销.在深腾6800上的实验表明,基于混合并行算法的求解器比纯MPI版本的求解器具有更好的性能和可扩展性.
纹理合成的自相关性判别法及其应用
莫灿林 陈 敏 郭绍义
2007, 44(2):  337-341. 
摘要 ( 298 )   HTML ( 0)   PDF (362KB) ( 398 )  
相关文章 | 计量指标
从加快纹理相似性的判别速度出发,提出了一种纹理合成的自相关性判别法.传统的纹理合成算法随着邻域和样本的增大,计算量将成倍增加,纹理合成速度减慢的劣势逐渐体现出来.因此,算法对样本纹理建立简单的自相关性距离查找表,利用L邻域内像素的自相关性距离作为像素匹配的判别依据,以查找取代传统匹配过程中的繁琐计算,极大地加快了合成速度,可实现动态的、多精度的合成效果调控,以及避免块匹配中易出现纹理接缝的问题.经验证,该算法可在纹理合成、图像修补及纹理检索中应用,并可很好地达到实时的应用要求.
基于数组的桶排序算法
杨 磊 宋 涛
2007, 44(2):  341-347. 
摘要 ( 616 )   HTML ( 3)   PDF (396KB) ( 776 )  
相关文章 | 计量指标
经典桶排序算法以链表形式实现“桶”,处理均匀数据效率很高,是O(N)算法.但对极不均匀数据则退化成低效的O(N\+2)插入排序.讨论了记录携带附加数据的计数排序算法,将“桶”实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(N log N)算法处理桶内数据.对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(N log N)的原算法.对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法.均匀数据实验表明,桶排序算法明显优于Linux下标准qsort系统调用,且数组桶排序算法效率更高.而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用.
Cache自适应写分配策略
郇丹丹, 李祖松, 胡伟武, 刘志勇,
2007, 44(2):  348-354. 
摘要 ( 585 )   HTML ( 0)   PDF (394KB) ( 365 )  
相关文章 | 计量指标
处理器所能提供的有效带宽是目前制约处理器性能提高的关键因素.通过对Cache写失效行为的分析,提出了一种新的提高处理器带宽利用率的Cache写失效处理策略——Cache自适应写分配策略.该策略在访存失效队列中收集全修改Cache块,对全修改Cache块采用非写分配策略,并能够自适应地切换为写分配策略.与传统的Cache写失效处理策略相比,Cache自适应写分配策略硬件代价小,避免了不必要的数据传输,降低Cache污染,减少存储管理队列阻塞的频率.结果表明,采用Cache自适应写分配策略,STREAM基准测试程序带宽平均提高62.6%,SPEC CPU2000程序的IPC值平均提高5.9%.
非线性规律访存操作的数据预取技术
吴佳骏, 冯晓兵, 张兆庆,
2007, 44(2):  355-360. 
摘要 ( 335 )   HTML ( 0)   PDF (369KB) ( 408 )  
相关文章 | 计量指标
编译器在静态分析方式下很难对程序的非线性规律访存操作进行正确的数据预取.但采用profiling技术可以得到程序运行时候的访存规律,利用这些信息可以精确地插入数据预取指令.基于stride profiling技术,提出了新的信息收集类型stride iterative,更精确地反映程序执行时访存指令的实际行为,并结合别名分析的结果调整对同一cache行的数据预取,得到比普通数据预取更好的预取性能.安腾2上运行CPU2000的12个整型测试例子平均有8.54%的性能提升,其中mcf性能提升达到了77.87%.
动态存储管理安全验证的Coq实现
项 森 陈意云 林春晓 李 隆
2007, 44(2):  361-367. 
摘要 ( 440 )   HTML ( 2)   PDF (433KB) ( 339 )  
相关文章 | 计量指标
随着软件规模和复杂度的日益提升,软件安全的问题变得越来越严峻,同时有越来越多的研究工作集中在高可信软件的开发上.由于类型系统表达能力的不足,现有的研究不触及底层软件的验证.由于Hoare逻辑更好的表达能力,采用Hoare逻辑风格的推理,在汇编语言级别,使用Coq形式化与定理证明工具可以实现一个经过安全验证的动态存储管理函数库,这是程序验证技术一次有意义的实践.实践表明,程序验证技术可以应用到高可信软件的开发上.