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

当期目录

2009年 第46卷 第10期    出版日期:2009-10-15
论文
片上二维网络互连性能分析
王 炜 乔 林 杨广文 汤志忠
2009, 46(10):  1601-1611. 
摘要 ( 334 )   HTML ( 1)   PDF (3793KB) ( 402 )  
相关文章 | 计量指标
片上互连网络已日益成为影响片上多处理器性能的重要因素之一.几乎所有的互连结构均是在二维网络的基础上演变发展而来的.首先分析了几种常见的内部结点度均为4的二维网络的静态特性,提出了一种新的二维片上网络互连路由结构和通信协议,基于全局均匀随机通信模型,通过改变网络规模和变换通信强度,分析了不同结构网络的动态特性,然后用链接数表示通信成本,提出了一种新的网络互连综合性能评估指标网络单位成本延迟负载能力,最后对二维网络片上互连的综合性能进行了对比分析,指出了其各自适用的场合.
基于遗传算法的全芯片级覆盖率驱动随机验证技术
沈海华, 王朋宇, 卫文丽, 郭 崎,
2009, 46(10):  1612-1625. 
摘要 ( 490 )   HTML ( 1)   PDF (1573KB) ( 563 )  
相关文章 | 计量指标
随机测试生成技术是当今大规模集成电路仿真验证流程中的重要支撑技术.覆盖率驱动的随机测试生成方法是目前该领域研究的热点.遗传算法具有部分优化问题的黑盒特性,不需要了解问题的太多先验知识,适合处理黑盒优化问题.因此,将遗传算法应用在覆盖率反馈驱动随机测试生成时,不需要复杂的领域先验知识,节约了大量的专家时间,提高了验证的自动化程度.分析了各种基于遗传算法的覆盖率驱动的随机测试生成方法,并在此基础上设计和实现了基于遗传算法的全芯片级覆盖率驱动随机验证平台.该平台被实际应用在龙芯处理器的验证中,实验结果表明,平台有效提高了验证效率.
一种面向异构实时集群系统的使用率反馈控制方法
王 洁, 王宏安, 傅 勇, 李 新,
2009, 46(10):  1626-1633. 
摘要 ( 374 )   HTML ( 0)   PDF (1524KB) ( 464 )  
相关文章 | 计量指标
软实时系统有着广泛的应用,如在线游戏、股票交易、传感器网络数据处理等.在这类应用中,通常有多个服务节点来响应外界大量的软实时请求.为了保证服务质量及防止系统超载,这些节点的CPU需要满足一定的使用率限制.为此,首先提出了异构集群系统中基于负载平衡的CPU使用率动态模型,其次在算法设计上将反馈控制理论引入其中并提出了针对异构实时集群系统的基于反馈的使用率控制算法.实验结果证明,该算法在引入负载平衡机制的异构实时集群系统中运行良好,系统节点间负载均衡并且各节点的CPU使用率能稳定地运行在限定状态.
面向实时流处理的多核多线程处理器访存队列
田杭沛 高德远 樊晓桠 朱怡安
2009, 46(10):  1634-1641. 
摘要 ( 474 )   HTML ( 0)   PDF (1937KB) ( 432 )  
相关文章 | 计量指标
针对多核多线程处理器中乱序访存影响计算实时性的问题,在对典型访存队列进行研究的基础上提出了一种新的访存队列构建模型及其硬件结构.该模型采用窗口优化算法控制最差情况下的访存延迟,保证访存的实时性,同时又利用优化的乱序调度策略减少访存延迟.实验证明,该访存队列可控制最大访存延迟,与顺序访存相比,存储器具备更高的带宽,与传统的乱序访存相比较,可以充分满足计算的实时性需求,而存储器有效带宽基本不受影响,解决了多核多线程处理器承担实时流计算的基础难题.
动态组簇的协同定位算法
周 全, 朱红松, 徐勇军, 罗海勇, 李晓维,
2009, 46(10):  1642-1650. 
摘要 ( 543 )   HTML ( 0)   PDF (1484KB) ( 409 )  
相关文章 | 计量指标
提出一种动态组簇的协同定位方法,用于基于传感器网络的目标定位和跟踪.该方法包括数据融合算法和虚拟簇漂移(virtual cluster shift,VCS)机制两部分.数据融合算法部分采用均值漂移(mean shift)算法.虚拟簇漂移机制分布式地在组织目标周围的锚节点建立临时簇.簇首管理簇成员,收集感知数据,执行融合算法.当虚拟簇无法锁定目标时,簇首指定离目标最近的簇成员担任新簇首,簇的成员也进行更替,由此将虚拟簇移动(shift)到合适的位置.分析和仿真结果显示,采用动态组簇的协同定位方法跟踪目标可以大幅度降低通信开销,产生的通信量仅为以往集中式定位算法开销的13.
基于802.11的多信道MAC协议性能分析
毛建兵 毛玉明 冷甦鹏 白 翔
2009, 46(10):  1651-1659. 
摘要 ( 512 )   HTML ( 1)   PDF (1245KB) ( 584 )  
相关文章 | 计量指标
为了改善无线网络中信道带宽的利用率,提高网络的吞吐量性能,已有研究提出了采用多信道MAC协议的方法,将单个信道分割成控制子信道和数据子信道进行联合使用.针对基于802.11 DCF的该类型MAC协议,采用离散Markov链对DCF的退避机制进行建模分析,研究了多信道下两种MAC机制的饱和吞吐量性能与信道带宽分配比例的关系,分析了网络节点数、数据分组大小和DCF竞争窗口等对优化多信道带宽分配的影响,并将多信道MAC机制下的网络性能与单信道MAC机制进行了对比.分析和仿真结果表明,采用优化的信道带宽分配,多信道的MAC机制可以一定程度上提高网络的吞吐量性能.但是,当允许控制帧以最大信道速率传输时,多信道MAC机制吞吐量性能并不比单信道MAC机制好.
一个网络归档存储中实用的数据持有性检查方案
肖 达, 舒继武, 陈 康, 郑纬民,
2009, 46(10):  1660-1668. 
摘要 ( 489 )   HTML ( 0)   PDF (1145KB) ( 469 )  
相关文章 | 计量指标
在网络归档存储中,数据持有性检查(DPC)用来在实际文件访问发生之前实时地检测远端服务器是否仍然完好地持有文件.提出一个实用的DPC方案.在一个挑战-应答协议中,检查者要求服务器计算文件中若干随机指定的数据块的一个Hash值,并和对应的校验块一起返回,以此判断文件的持有性.通过这种随机抽样校验的方法,在保证足够的置信度的同时降低了持有性检查的计算和通信开销.同时提出一个基于校验块循环队列的挑战更新机制,从而允许动态增加检查者可发起的有效挑战的次数.分析表明检查者端的存储开销和检查者和服务器间的通信开销均为常数量级.测试结果表明一次置信度为99.4%的持有性检查的计算开销为1.8ms,和磁盘I/O开销相比可以忽略不计;通过避免使用公钥密码系统,将文件预处理的计算开销降低了3个数量级.
互联网域间路由系统安全态势评估
刘 欣, 王小强, 朱培栋, 彭宇行,
2009, 46(10):  1669-1677. 
摘要 ( 505 )   HTML ( 0)   PDF (1172KB) ( 395 )  
相关文章 | 计量指标
基于边界网关协议BGP的互联网域间路由系统缺乏必要的安全机制,面临严重的安全威胁.尽管人们对BGP路由系统的安全问题进行了详尽研究,但是很少量化该系统的安全态势,并且网络管理员也确实需要有用的安全态势信息来感知自治系统(AS)的路由安全状况.为了解决这个问题,分析了互联网域间路由系统的层次特性,提出了一个基于BGP异常路由的安全评估模型.该方法的基本思想是基于BGP路由系统的层次特性构造路由状态树,准确地刻画BGP路由系统中各路由实体之间的层次关系、存储和表达每个实体的路由安全状态;并根据所检测的异常路由计算每个实体的路由安全状态.实验测试表明,该模型能同时评估BGP路由器、自治系统和互联网域间路由系统的安全威胁态势,可为网络管理员提供直观的安全态势曲线.
基于再生技术的无线传感器网络容侵拓扑控制方法
王良民, 马建峰,
2009, 46(10):  1678-1685. 
摘要 ( 402 )   HTML ( 0)   PDF (1942KB) ( 367 )  
相关文章 | 计量指标
面对入侵时如何生成一个具有较高容侵能力的拓扑,在节点能源都会耗尽时如何维持一个可用的网络拓扑是布置在不可照料环境下的无线传感器网络拓扑面临着的两个关键问题.针对这两个问题,提出了一种基于再生技术的容侵拓扑控制方法,该方法被证明为可生成具有较强容侵能力的拓扑结构,同时将不断播撒进入部署区域的新增节点视为网络的可更新资源,以一代代再生网络的方式补充网络的可用能量以延长网络的生存期.仿真实验分析了拓扑控制方法中的一些参数特征及其在延长网络的生存期方面的性能,并与相关工作进行了比较.
基于安全策略模型的安全功能测试用例生成方法
张 敏 冯登国 陈 驰
2009, 46(10):  1686-1692. 
摘要 ( 544 )   HTML ( 7)   PDF (907KB) ( 600 )  
相关文章 | 计量指标
实施第三方安全功能独立测试是信息安全产品测评中的一个重要环节,对于以安全数据库管理系统为代表的信息安全产品,其系统规约的测试并不能完全真实反映系统行为,还需要满足系统安全策略.提出了基于安全策略模型的安全功能测试用例自动生成方法,该方法包括基于语法的划分、基于规则的划分、基于类型的划分等步骤,依据形式化安全模型生成正确描述系统行为的操作测试用例集.该方法有助于提高测试质量,发现手工测试中难以发现的缺陷,并有助于减少测试过程中的重复劳动,实现测试自动化并提高测试效率.
一种基于特征重要度的文本分类特征加权方法
刘 赫, 刘大有, 裴志利, 高 滢,
2009, 46(10):  1693-1703. 
摘要 ( 578 )   HTML ( 6)   PDF (2160KB) ( 572 )  
相关文章 | 计量指标
针对文本分类中的特征加权问题,提出了一种基于特征重要度的特征加权方法.该方法基于实数粗糙集理论,通过定义特征重要度,将特征对分类的决策信息引入到特征权重中.然后,在标准文本数据集Reuters-21578 Top10和WebKB上进行了实验.结果表明,该方法能改善样本空间的分布状态,使同类样本更加紧凑,异类样本更加松散,从而简化从样本到类别的映射关系.最后,使用Nave Bayes,kNN和SVM分类器在上述数据集上对该方法进行了实验.结果表明,该方法能提高分类的准确率、召回率和$F$\-1值.
面向大规模语料的语言模型研究新进展
骆卫华, 刘 群, 白 硕,
2009, 46(10):  1704-1712. 
摘要 ( 530 )   HTML ( 1)   PDF (1107KB) ( 827 )  
相关文章 | 计量指标
N元语言模型是统计机器翻译、信息检索、语音识别等很多自然语言处理研究领域的重要工具.由于扩大训练语料规模和增加元数对于提高系统性能很有帮助,随着可用语料迅速增加,面向大规模训练语料的高元语言模型(如N≥5)的训练和使用成为新的研究热点.介绍了当前这个问题的最新研究进展,包括了集成数据分治、压缩和内存映射的一体化方法,基于随机存取模型的表示方法,以及基于分布式并行体系的语言模型训练与查询方法等几种代表性的方法,展示了它们在统计机器翻译中的性能,并比较了这些方法的优缺点.
一种新的情感词汇语义倾向计算方法
杜伟夫, 谭松波, 云晓春, 程学旗,
2009, 46(10):  1713-1720. 
摘要 ( 501 )   HTML ( 1)   PDF (1380KB) ( 515 )  
相关文章 | 计量指标
当前,人们越来越倾向于通过互联网(论坛、讨论组、博客)表达自己对事物的观点、意见.如何利用计算机自动、有效地挖掘这些信息是一个具有挑战性的问题,并且在企业智能分析、政府舆情分析等领域具有广阔的应用空间和发展前景.文本倾向分析就是以挖掘、分析文本中所包含的情感信息为目的的一种技术,它是传统的话题发现与跟踪研究的拓展和深化,并为其提供了新的思路和方法.文本倾向分析的基础是词语语义倾向计算.提出一个可扩展的词汇语义倾向计算框架,将词语语义倾向计算问题归结为优化问题.在算法实现上,首先利用多种词语相似度计算方法构建词语无向图;然后利用以“最小切分”为目标的目标函数对该图进行划分,并利用模拟退火算法进行求解.实验证明了该框架的合理性以及求解方法的有效性.
XML流管理研究综述
杨卫东 施伯乐
2009, 46(10):  1721-1728. 
摘要 ( 548 )   HTML ( 0)   PDF (1362KB) ( 491 )  
相关文章 | 计量指标
近年来,XML流管理是数据流研究领域中的一个热点研究问题.不同于传统数据库管理系统,XML数据流管理系统需要在使用少量内存的情况下随时处理在线到达的数据流;由于XML流具有递归的、层次的结构,并且用户兴趣通常用XML查询语言来表示,因此,XML流管理技术与关系型数据流(基于元组的数据)管理技术有很大不同.综述XML流管理技术及各项研究成果;指出XML流管理系统的特点;比较了当前典型的XML数据流管理系统;系统地阐述和分析当前国内外已有的XML流数据处理方法(包括基于自动机的方法、基于索引的方法,基于序列的方法)和流处理的相关优化技术;指出尚需进一步研究的问题.
扩频鲁棒图像水印中的亮度越界处理方法
赵启阳 尹宝林
2009, 46(10):  1729-1736. 
摘要 ( 380 )   HTML ( 2)   PDF (1781KB) ( 477 )  
相关文章 | 计量指标
在扩频鲁棒图像水印中,在水印嵌入过程中的“频域-空域”变换会引起像素亮度值的越界,而现有的解决方案有可能导致水印检测值的大幅降低,并严重削弱了水印的鲁棒性.因此以典型的扩频水印机制为例,通过在空间域给出水印检测值的近似计算方法,研究了像素亮度越界现象对水印检测值的影响,发现对纹理较少的高亮度图像,像素的亮度越界将严重地降低水印检测值.最后提出了一种自适应的分块式亮度调整策略,分析和实验表明,新的调整策略能够有效地改进含水印图像的保真性和水印的鲁棒性.
基于线元几何的旋转面点云数据旋转轴提取算法
张 量, 姜晓峰,
2009, 46(10):  1737-1742. 
摘要 ( 441 )   HTML ( 0)   PDF (1448KB) ( 427 )  
相关文章 | 计量指标
当前逆向工程CAD建模技术中,由于基于特征的曲面重构技术在精确表达原始模型、还原设计意图以及快速建模中所具备的优势,使其逐渐成为逆向工程领域新的研究热点.为实现海量数据快速特征提取,提出了一种基于线元几何、线性丛的旋转面点云数据旋转轴提取算法.算法首先将三维空间中的点投影到线元空间中,构建线性丛,而后在线性丛上拟合运动方程,通过特征参数计算旋转轴位置.此方法无须精确估算曲面法矢,有效地提高了特征提取速度.在算法中设计并使用了K-Local-RANSAC算法进行快速离散区域扩张并排除外点,保证了算法的健壮性.实验证明,本算法对于包括圆环面在内的旋转面都能得到较好的效果,而且能较好地适用于碎片数据及含有噪声的情况.
Ambient演算的一种分层语义
吕江花 马世龙
2009, 46(10):  1743-1749. 
摘要 ( 460 )   HTML ( 0)   PDF (678KB) ( 388 )  
相关文章 | 计量指标
网络计算系统中涉及的操作复杂,很难直接给出一种的语义描述框架.作为一种网络计算模型,Ambient演算主要刻画了计算的分布性和移动性.目前关于Ambient的语义研究很多,但均是基于规约规则的语义形式.这种描述方式尽管简洁,一方面却具有不确定性,不利于实际的网络计算系统的设计和直接实现;另一方面,这种语义描述方式均在一个层次上描述Ambient演算系统中的各种行为语义,使得Ambient演算中各种计算行为纠缠在一起,复杂而难以理解.根据Ambient演算的结构特点,给出了Ambient演算的一种分层语义描述形式,系统以ambient为单元,分成3层进行描述,分别给出不同层上行为的语法定义、语义定义、语义方程以及不同层间的转换函数的定义,从而给出Ambient演算系统的指称语义描述形式.这种描述方式从层次化的角度分析了Ambient演算的计算行为,有助于对Ambient演算中行为的理解和实际应用系统的实现.
移动界程模型检测
江 华, 李 祥,
2009, 46(10):  1750-1757. 
摘要 ( 392 )   HTML ( 0)   PDF (772KB) ( 400 )  
相关文章 | 计量指标
首次将嵌套谓词等式系应用到带递归的谓词界程逻辑模型检测中,提出了第1个时间复杂性与逻辑公式的交错嵌套深度呈指数关系的局部模型检测算法,这也是目前已知的第2个带递归的谓词界程逻辑模型检测算法.所做的工作有:①讨论了谓词界程逻辑公式与嵌套谓词等式系间语义的等价性,给出了谓词界程逻辑公式转换成嵌套谓词等式系的方法;②讨论了谓词界程逻辑模型检测问题,给出了具体算法,并分析了算法的复杂性.
一种基于页面级流缓存结构的流检测和预取算法
刘 立, 陈明宇, 包云岗, 许建卫, 樊建平,
2009, 46(10):  1758-1767. 
摘要 ( 434 )   HTML ( 0)   PDF (3110KB) ( 341 )  
相关文章 | 计量指标
为了提高网络内存的访存性能,基于一种页面级流缓存和预取结构提出了可变步长的带状流检测算法VSS(variable stride stream)和基于时钟步长的流预取优化算法来优化网络访存性能.带状流检测算法解决了固定步长流检测下循环访问中虚拟页地址的跳跃问题,消除了断流,可以有效提高流检测的覆盖率.基于时钟步长的流预取优化动态调整预取长度,可以解决有些预取不能及时取回的问题,进一步提高预取性能.通过和顺序预取算法的比较可以看出,VSS算法可以实现高准确率、低通信开销的预取.通过模拟分析了这种流缓存和预取机制在网络访存系统中的应用,验证了以少量性能下降换取灵活的远程内存扩展方法的可行性.
基于存储优化的多模式串匹配算法
刘燕兵, 刘 萍, 谭建龙, 郭 莉,
2009, 46(10):  1768-1776. 
摘要 ( 556 )   HTML ( 0)   PDF (1237KB) ( 596 )  
相关文章 | 计量指标
多模式串匹配算法是网络内容过滤系统的核心技术之一.自动机的存储空间大小和Cache性能是影响多模式串匹配算法速度的关键因素.随着模式串规模的扩大,自动机的巨大存储开销导致现有的串匹配算法性能大幅度下降.从压缩存储空间以提高Cache命中率的思想出发,提出了一种对经典SBOM算法的优化策略,它用Suffix Tree代替SBOM算法中的Factor Oracle结构,同时用剪枝的方法将Suffix Tree降低为近似线性的空间复杂度,然后用双数组Trie表示之,以压缩存储空间.与SBOM算法相比,改进算法不仅能够有效地节省存储空间,而且显著地提高了串匹配的速度,非常适合于在线高速匹配的应用环境.