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

当期目录

2009年 第46卷 第2期    出版日期:2009-02-15
论文
基于FPGA的万兆流量并行实时处理系统研究
王建东, 祝 超, 谢应科, 韩承德, 赵自力,
2009, 46(2):  177-185. 
摘要 ( 650 )   HTML ( 1)   PDF (1401KB) ( 415 )  
相关文章 | 计量指标
针对万兆网络环境下入侵检测、流量审计等应用系统处理能力瓶颈,提出一个并行实时处理体系结构,并基于FPGA实现了原型系统,该系统对OC192(10Gbps)流量进行分类、过滤及统计,然后将流量分发到多个后台并行处理.系统中设计了通用包分类结构RSTCAM(range-supported split TCAM),该结构资源占用量少,可降低系统功耗,且易于实现范围查找,对基于TCAM包分类系统具有普遍意义.系统中还提出了一种负载均衡算法FDLB(feedback-based dynamic load balancing),FDLB改进了基于表的Hash方法,在保证会话完整性的前提下将流量优先分发给当前负载最小的后端处理.测试表明,原型系统完全胜任万兆流量的线速处理,平均处理延迟为4.2μs.
数据网格中请求呈现分组特性的副本管理策略研究
姜建锦, 杨广文,
2009, 46(2):  186-193. 
摘要 ( 391 )   HTML ( 0)   PDF (746KB) ( 387 )  
相关文章 | 计量指标
在数据网格中,数据使用模式将影响系统性能.根据一些实际系统的测试结果,数据请求呈现出分组特性.为研究当数据请求呈现分组特性时请求分布与副本分布的关系,首先定义了数据网格中副本复制策略的模型,然后研究在数据请求呈现分组特性时平均访问延迟最小的最优策略.采用拉格朗日乘子法以及二分法对上述模型进行求解,得到了一个在请求分组模式下的最优下载副本策略.通过模拟实验对最优策略以及均匀复制策略、比例复制策略、平方根复制策略、LRU缓存策略的性能进行了比较.结果表明,最优策略所需广域网带宽最少,平均访问延迟最小.
成本约束的网格工作流时间优化方法
苑迎春, 李小平, 王 茜, 王克俭,
2009, 46(2):  194-201. 
摘要 ( 395 )   HTML ( 2)   PDF (805KB) ( 485 )  
相关文章 | 计量指标
针对成本约束有向无环图DAG(directed acyclic graph)表示的网格工作流完工时间最小化问题,提出两个基于优先级规则的迭代启发算法.算法利用并行活动特征定义正向分层和逆向分层两个概念,将其分别引入最大收益规则MP(maximum profit),得到正分层最大收益规则MPTL(maximum profit with top level) 和逆分层最大收益规则MPBL(maximum profit with bottom level).两规则每次迭代尽量以完工时间的最小增加换取总费用的最大降低,逐步将分层初始解构造为满足成本约束的可行解.模拟结果表明,两规则在获得较少迭代次数和运行时间的同时,能显著改进MP规则的平均性能,且MPBL优于MPTL.
Web预取技术综述
班志杰, 古志民, 金 瑜,
2009, 46(2):  202-210. 
摘要 ( 578 )   HTML ( 0)   PDF (894KB) ( 592 )  
相关文章 | 计量指标
Web预取是减少用户访问延时、提高网络服务质量的关键技术之一,近年来已成为国内外的研究热点.通过利用WWW访问的空间局部性,Web预取使缓存机制从时间局部性向空间局部性扩展.归纳了Web预取技术的分类,概括和比较了不同类别的优势和局限性,给出了预取模型的基本框架及每部分的主要功能,并对各种评价标准进行了详细介绍.同时,深入分析和探讨了现有的几种典型预取算法,系统地比较了这些算法的优缺点.最后从在线性、协作预取、动态流行度、划分用户会话和基于语义与基于路径相结合等方面指出了Web预取技术的研究方向.
基于预取的流视频带宽适应性传输算法
谢建国
2009, 46(2):  211-216. 
摘要 ( 453 )   HTML ( 0)   PDF (689KB) ( 415 )  
相关文章 | 计量指标
IP网络带宽的动态特性是流视频要面临的关键问题.可伸缩编码的视频具有带宽适应性,但由于其每一层编码通常是变比特率的,那么在视频传输中,为迎合动态传输带宽,如何裁减这种分层的变比特率视频,并极大化一定的目标性能,需要传输优化.针对上述问题,提出了一个预取或缓冲优化的流视频带宽适应性传输框架,将裁减策略放到一个窗口来考虑,解决了窗口内的最小裁减量问题,其带宽适应性粒度在理论上可以细化到“比特位”,并为其他裁减算法提供综合优化的计算平台.
基于质心向量的增量式主题爬行
王 辉, 左万利, 王晖昱, 宁爱军, 孙志伟, 满春雷,
2009, 46(2):  217-224. 
摘要 ( 514 )   HTML ( 0)   PDF (1036KB) ( 453 )  
相关文章 | 计量指标
研究如何在一个网页内部进行有选择的爬行.使用TFIDF-2模型以及Max, Ave, Sum三个启发式规则分别计算文档特征权重和质心特征权重,在此基础上构建与根集文档相对应的质心向量,利用它作为前端分类器指导主题爬行.使用前后端分类器分别给Frontier中的各个锚文本打分,将它们的打分求和,从中选择打分最高的链接,下载其对应的网页.实验结果表明,在质心向量的指导下,爬行程序借助于锚文本便可以准确地预测链接所指向网页的相关性;另外,双分类器框架还使得爬行策略具有增量爬行的能力.
一种高效的SPKI/SDSI2.0策略分析算法
耿秀华, 韩 臻, 金 砺, 曹香港,
2009, 46(2):  225-234. 
摘要 ( 397 )   HTML ( 0)   PDF (967KB) ( 367 )  
相关文章 | 计量指标
信任管理方法提供了一种新的思路,弥补了传统授权机制应用于分布式系统的不足.SPKI/SDSI2.0是目前较普及的信任管理系统,系统中的每个主体都可以发放证书.在一个特定的系统状态中,系统管理员需要知道关于系统的一些“特性”,如某一主体是否有权访问被保护资源、一个本地名有哪些成员等.当证书数量庞大时,这些问题需要借助一定的工具才能回答.但以前的算法均集中于对授权问题的讨论,没有考虑与名字相关的系统策略分析,且分析效率偏低.提出了一种基于逻辑的SPKI/SDSI2.0策略分析算法EPAAS,从本质上拓宽了策略分析的领域,利用它不仅可以分析SPKI/SDSI2.0的授权问题及名字问题,还可以将这两类问题结合起来对系统策略进行综合查询;此外,EPAAS将策略分析的时间复杂度由原先算法的O(n\+3l)降至O(n),提高了分析效率.EPAAS用标准的Datalog程序表示SPKI/SDSI2.0的系统状态,以Datalog程序的最小Herbrand模型作为它的语义,证明了该语义的可靠性.
一种面向运营级以太网的自适应前向纠错方法
戴锦友, 余少华,
2009, 46(2):  239-244. 
摘要 ( 533 )   HTML ( 0)   PDF (720KB) ( 531 )  
相关文章 | 计量指标
相对于传统以太网,现有的以太网物理信道已发生巨大变化.运营级以太网则对以太网信道提出了更高的要求,在运营级以太网应用环境下,采用适当机制提高以太网信道可靠性是必要的.在IEEE802.3标准帧结构的基础上,提出了一种包含前向纠错(FEC)机制的帧结构,并阐述了基于该帧结构的FEC方法.该方法除实现纠错功能外,还具有检测信道性能并自适应调节FEC配置的机制,使得可以在保障纠错性能的基础上尽可能减少FEC带来的开销.并且使用该方法的以太网接口能够与普通以太网接口互通互联以实现后向兼容.对该方法的性能进行了透彻的分析,证明该方法可行.设计了网络设备实现该FEC方法,并搭建测试拓扑对该方法进行评测,测试结果表明,该方法可以实现预期功能.
基于关键词元的话题内事件检测
张 阔 李涓子 吴 刚 王克宏
2009, 46(2):  245-252. 
摘要 ( 729 )   HTML ( 1)   PDF (767KB) ( 448 )  
相关文章 | 计量指标
各种媒体每天有大量的新闻报道产生,需要一种自动化的分析方法将新闻以一种更加清晰的组织形式展示给用户.大多已有工作将新闻划分成平面的话题,然而一个话题并非仅仅是简单的新闻集合,而是由一系列相互关联的事件所组成的.由于话题内的事件之间往往非常相似,导致话题内的事件检测精确度较差.为了克服以上问题,提出了基于事件词元委员会的事件检测与关系发现方法.即首先挖掘每个事件的核心词元,随后利用事件的核心词元进行事件检测与关系发现.在Linguistic Data Consortium (LDC)的两个数据集上的实验结果显示,提出的事件检测与关系发现方法可以显著地改善已有方法的效果.
一种Agent的偏好系统及其建立
王蓁蓁 邢汉承 陈汉武
2009, 46(2):  253-260. 
摘要 ( 410 )   HTML ( 0)   PDF (915KB) ( 341 )  
相关文章 | 计量指标
受到Agent偏好模型的启发,提出了一个新的描述人们行为的偏好系统称为AF系统,它将Michael Freund的理性偏好推理与Adams提出的经典的归纳逻辑和概率逻辑相结合,即借助经典的逻辑系统,把人们的逻辑推理和以人们的偏好取向为基础的常识性推理以及以主观愿望为基础的意向推理结合在一起成为一个有机系统,并且在这个系统下提出Agent的理性偏好的建立方法以及推理步骤.最后给出一个实例,说明它能根据人们的部分愿望,全面估计人们的偏好走向,而且一旦人们的基本态度有所转向,偏好结构也可做相应调整,无需做根本改动,因此它具有鲁棒性和实用价值.
删除最差基学习器来层次修剪Bagging集成
谢元澄 杨静宇
2009, 46(2):  261-267. 
摘要 ( 566 )   HTML ( 0)   PDF (852KB) ( 395 )  
相关文章 | 计量指标
主要目的是寻找到一种Bagging的快速修剪方法,以缩小算法占用的存储空间、提高运算的速度和实现提高分类精度的潜力. 传统的选择性集成方法研究的重点是基学习器之间的差异化,从同质化的角度来研究这一问题,提出了一种全新的选择性集成思路. 通过选择基学习器集合中的最差者来对Bagging集成进行快速层次修剪,获得了一种学习速度接近Bagging性能在其基础上得到提高的新算法. 新算法的训练时间明显小于GASEN而性能与其相近. 该算法同时还保留了与Bagging相同的并行处理能力.
数据流上具有数据遗忘特性的小波概要
陈华辉, 施伯乐,
2009, 46(2):  268-279. 
摘要 ( 449 )   HTML ( 0)   PDF (1087KB) ( 419 )  
相关文章 | 计量指标
动态地维护数据流的概要结构是数据流查询和挖掘等处理工作的基础.在许多数据流应用场合,数据的影响随时间衰减,流中数据被逐步遗忘,称为数据流的遗忘特性.在数据流概要的构造中,应体现这种特性.离散小波变换是一种应用得较多的数据流概要构造方法.将数据流的遗忘特性引入小波概要的构造中,提出了一种能反映数据流遗忘特性的小波概要结构:基于小波的分层遗忘概要,分别讨论了误差平方和及最大绝对误差两种误差度量标准下这种概要的构造方法.所进行的实验验证了该概要的有效性.
基于结果模式的Deep Web数据抽取
马安香 张 斌 高克宁 齐 鹏 张 引
2009, 46(2):  280-288. 
摘要 ( 689 )   HTML ( 1)   PDF (1130KB) ( 471 )  
相关文章 | 计量指标
高效、准确地获取Deep Web数据是实现Deep Web数据集成系统的关键问题,然而重复语义标注、嵌套属性的存在是Deep Web数据抽取效率和准确率难以提升的瓶颈问题.因此提出基于结果模式的Deep Web数据抽取机制,将数据抽取工作分为结果模式生成和数据抽取两个阶段,属性语义标注放在结果模式生成阶段来完成,有效解决了重复语义标注问题;同时针对嵌套属性问题,提出一种有效的解决方法.与同类成果相比,基于结果模式的数据抽取方法提高了数据抽取的准确率及效率,并且为Deep Web数据集成奠定了良好的基础.
过测地线的优化曲面设计
赵宏艳 王国瑾
2009, 46(2):  289-294. 
摘要 ( 362 )   HTML ( 0)   PDF (621KB) ( 572 )  
相关文章 | 计量指标
给定一条曲线,构造以其为测地线的曲面,这是服装鞋帽类产品的设计/制造业中的一个现实课题.已有研究结果是构造出以给定曲线为公共测地线的曲面束,然后用拟合数据点的方法来确定最终曲面.这种通用方法受到曲面参数及其表示方法的影响,且没有对曲面的光顺程度加以考虑.从服装材料的特性和设计思想出发,提出一种利用能量优化来确定最终曲面的新方法.通过改变曲面表示形式和引入能量函数,方便而有效地确定了过给定测地线的一张优化曲面.给出了在插值拟合等约束条件下的相应算法.实例表明,所给算法很好地模拟了成衣的光顺设计与加工,在计算机辅助设计/制造(CAD/CAM)中富有应用价值.
用行人轮廓的分布直方图分类和识别步态
陈 实, , 马天骏, 高有行,
2009, 46(2):  295-301. 
摘要 ( 544 )   HTML ( 0)   PDF (1250KB) ( 396 )  
相关文章 | 计量指标
现有的步态识别方法对行人轮廓匹配的鲁棒性差,识别率不高.提出了一种基于轮廓直方图分布的行人步态识别方法.首先提取行人二值轮廓序列;然后通过人体局部轮廓的点分布直方图获取步态周期;继而构造表达帧间关系的周期步态平面,设计一种直方图分布的描述子获得帧姿态特征值,计算出姿态轮廓特征分布间的Jeffery距离,结合动态时间规整技术获取了测试序列和参考序列间的匹配相似度,最终完成了识别.在Soton步态数据库上进行了实验,提出算法的正确识别率可达87.59%,与相关文献的对比分析表明算法是有效的.
FPTS:一种任务间存在共享资源时的抢占阈值调度算法
贺小川 贾 焰
2009, 46(2):  302-309. 
摘要 ( 492 )   HTML ( 0)   PDF (787KB) ( 329 )  
相关文章 | 计量指标
受到广泛关注的抢占阈值调度算法能够有效减少现场切换次数,防止不必要的任务抢占,降低资源额外消耗,提高任务集合的可调度性.目前该调度算法的研究工作大多围绕独立任务集合展开,在实际实时系统中任务经常需要互斥访问共享资源,任务之间由于资源共享而导致的相关性对于任务集合的优先级分配和抢占阈值分配都有很大的影响.SRP协议是在实时系统中得到广泛应用的资源访问控制协议,具有死锁避免、提前阻塞、共享任务栈等一系列优良特性.将SRP和抢占阈值调度算法结合起来,提出FPTS调度模型,给出相应的可调度性判定公式,考虑在任务之间使用SRP协议时求解任务抢占阈值分配,最后给出计算抢占阈值分配的伪多项式时间算法.
构件式体系结构模型映射的形式化语义
侯金奎 万建成 杨 潇 王海洋
2009, 46(2):  310-320. 
摘要 ( 457 )   HTML ( 0)   PDF (1175KB) ( 397 )  
相关文章 | 计量指标
语义一致性是模型驱动开发中模型转换正确性的一个重要标准,但目前模型转换中语义特性保持的定义、描述和验证仍是一个尚未解决的难题.基于软件体系结构,利用范畴理论和代数规范形式化描述体系结构模型及其间的映射关系,使之具有精确的语义.体系结构模型的形式化语义用类型范畴图表来表示,态射合成被用来追踪构件模型之间的关联和映射,不同层次模型间的映射关系用态射和函子来形式化描述.以此为基础,进一步分析了模型转换应保持的语义特性.范畴理论支持图形化建模,可以使模型中的构件关系以及结构特征可视化,有利于对模型转换的理解和追踪.应用研究表明,该描述框架很好地把握了模型驱动开发的实质、过程和要求,为模型转换和模型驱动开发提供了新的认知、设计和语义计算的指导架构.
量子逻辑电路中控制点失效错误的定位
肖芳英 陈汉武
2009, 46(2):  321-328. 
摘要 ( 354 )   HTML ( 1)   PDF (658KB) ( 553 )  
相关文章 | 计量指标
确保可逆电路的正确性与可靠性,错误检测必不可少,错误定位难度更高.通过分析发现当可逆电路中规模为k的可逆门发生控制点失效时仅对2\+\{n-k\}个输入向量的输出产生影响,据此给出了一种把当前错误集分成若干个子集的方法生成控制点失效错误定位树.传统的错误定位方法都是通过生成真值表和错误表来产生错误定位树;该方法不需要生成和存储真值表以及错误表就能够有效定位电路中控制点失效错误.与Rfault算法相比,空间复杂度和时间复杂度更小,算法效率更高,能应用于更大规模的电路.
一种解同步电路优化设计方法的研究和实现
晋 钢 王 蕾 王志英 戴 葵
2009, 46(2):  329-337. 
摘要 ( 366 )   HTML ( 0)   PDF (995KB) ( 320 )  
相关文章 | 计量指标
解同步电路设计方法可以与现有EDA工具较好地兼容,可以极大地提高异步电路的设计效率.基于解同步电路的抽象模型——控制图,提出了一种解同步电路优化设计方法,优化过程由解同步电路的性能评价函数作为指导,在不影响电路性能的前提下有效地减小电路控制通路的面积.选取了一系列标准测试电路进行了实验,最终解同步电路控制通路所需的局部控制器数量减少了54%,C门的数量减少了76.3%.采用该设计方法,设计实现了0.35μm工艺条件下的32位解同步乘法器,实验结果表明,相对于传统的解同步电路设计方法,提出的优化设计方法可以在保持电路性能的前提下有效地减小电路的面积.
基于TDMP优化算法的QC-LDPC译码器VLSI实现
鲍 丹 向 波 申 睿 陈 赟 曾晓洋
2009, 46(2):  338-344. 
摘要 ( 857 )   HTML ( 0)   PDF (1014KB) ( 400 )  
相关文章 | 计量指标
在对TDMP算法优化的基础上,提出了一种LDPC译码器VLSI架构和实现方法.与目前已经存在的LDPC译码器相比,这种实现方法的优势主要有:1)能够实现快速收敛,将译码迭代次数降低为经典方法的50%以下,进而降低功耗;2)用于存储中间置信信息的存储器使用量比传统方法减少50%以上,大大减少芯片面积;3)校验节点置信度更新采用归一化Min-Sum算法(NMS),降低计算复杂度,选取的校正因子保证了译码器的BER性能;4)充分利用校验矩阵的准循环特点,实现规整的芯片内部互连线,减小布线难度.用这种架构实现了符合中国数字电视地面传输标准(DTMB)的LDPC译码器:融合3种码率;芯片规模为58万门;时钟频率为100MHz,数据吞吐率为107Mbps.
一种软硬件结合的控制流检测与恢复方法
龚 锐 陈 微 刘 芳 戴 葵 王志英
2009, 46(2):  345-351. 
摘要 ( 506 )   HTML ( 0)   PDF (1083KB) ( 385 )  
相关文章 | 计量指标
控制流检测可以有效地提高微处理器容错能力.针对传统软件实现的控制流检测时空开销大的缺点,提出了一种软硬件结合的控制流检测与恢复方法.该方法通过编译自动插入签名数据,由硬件在分支/跳转指令之后自动执行检测,并且提供了硬件现场保存和恢复机制,检测到控制流错误后无需复位系统即可以快速恢复正常控制流.基于8051体系结构实现了软硬件结合的控制流检测与恢复方法,实验结果表明与传统的软件控制流检测相比,该方法在保持相同的错误检测率的情况下,可以大幅减小二进制代码量和额外的性能开销,在发生控制流错误以后可以快速恢复正常控制流.