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

当期目录

2007年 第44卷 第11期    出版日期:2007-11-15
论文
数据流挖掘分类技术综述
王 涛, 李舟军, 颜跃进, 陈火旺,
2007, 44(11):  1809-1815. 
摘要 ( 615 )   HTML ( 3)   PDF (347KB) ( 1183 )  
相关文章 | 计量指标
数据流挖掘作为从连续不断的数据流中挖掘有用信息的技术,近年来正成为数据挖掘领域的研究热点,并有着广泛的应用前景.数据流具有数据持续到达、到达速度快、数据规模巨大等特点,因此需要新颖的算法来解决这些问题.而数据流挖掘的分类技术更是当前的研究热点.综述了当前国际上关于数据流挖掘分类算法的研究现状,并从数据平稳分布和带概念漂移两个方面对这些方法进行了系统的介绍与分析,最后对数据流挖掘分类技术当前所面临的问题和发展趋势进行了总结和展望.
多维概念格与多维序列模式的增量挖掘
金 阳 左万利
2007, 44(11):  1816-1824. 
摘要 ( 424 )   HTML ( 0)   PDF (545KB) ( 456 )  
相关文章 | 计量指标
多维序列模式挖掘旨在将一个或多个背景维度信息中发现的关联模式与有序事务序列中发现的序列模式有机结合,从而为用户提供信息内容更加丰富、更具有直接应用价值的多维序列模式.目前虽有一些挖掘多维序列模式的工作,但其关联模式与序列模式的发现过程是基于不同的数据结构分开进行的.提出一种新的概念格结构——多维概念格,它是对概念格的延伸与泛化,其内涵更加丰富,不仅具有多个有序的任务内涵,而且具有多个无序的背景内涵.设计实现了基于该结构的增量式多维序列模式挖掘算法,该算法使用统一的数据模型实现关联模式与序列模式的高效同步挖掘.在合成数据集上的实验结果验证了算法的有效性.同时,算法在实际的银行数据集上的应用效果也说明了算法的实用性.
二阶微粒群算法
胡建秀 曾建潮
2007, 44(11):  1825-1831. 
摘要 ( 301 )   HTML ( 0)   PDF (373KB) ( 335 )  
相关文章 | 计量指标
为了提高标准微粒群算法的全局收敛性,提出了一种新的微粒群算法——二阶微粒群算法.首先,介绍了二阶微粒群算法的引入,分析了其收敛性,并且研究了其参数的选择范围.其次,在分析二阶微粒群算法的进化方程的基础上,引出了具有随机惯性权重的标准微粒群算法.再次,在二阶微粒群算法中加入振荡因子来调整微粒的速度变化率,更好地使二阶微粒群算法收敛于全局最优.最后,利用这几种改进方法对典型测试函数进行仿真,实验结果表明,这些方法能够有效克服早熟问题,在全局收敛性和收敛速度方面均优于标准微粒群算法.
基于变异的迭代sIB算法
朱真峰, 叶阳东, Gang Li,
2007, 44(11):  1832-1838. 
摘要 ( 468 )   HTML ( 1)   PDF (426KB) ( 466 )  
相关文章 | 计量指标
IB方法使用源变量和相关变量的联合概率分布对源变量进行最大化压缩,使压缩变量最大化地保存相关变量的信息.连续IB算法(sIB)是一种较好的、应用较多的IB算法之一,但该算法存在效率低、优化不充分等问题.为了解决sIB在应用中存在的这些问题,提出了一种基于变异的迭代sIB算法(isIB). isIB算法首先从相关实验中选取合理的变异率;基于该变异率,该算法从sIB算法所产生的初始解向量中随机选取相应比例的位置,对其中的类标号进行随机变异并优化;再通过多次迭代获得了相应的优化解.实验表明在数据集相同、基本sIB算法调用次数相同的条件下,isIB算法相对于sIB算法具有运行效率高、解更优化的特点.
通信协议的实体行为描述语言CPEBSDL
范 昊, 吴哲辉,
2007, 44(11):  1839-1848. 
摘要 ( 623 )   HTML ( 1)   PDF (569KB) ( 526 )  
相关文章 | 计量指标
提出了一种通信协议的实体描述语言CPEBSDL. CPEBSDL语言是一种描述能力很强的语言,它可以对协议实体的状态、行为及协议实体对资源的控制和访问进行形式化的描述,同以往的描述语言不同,CPEBSDL语言把协议实体之间复杂的交互行为看做是实体对协议中共同使用到的资源的控制和访问,从而简化了交互行为描述的复杂性,便于对协议进行分析和测试.给出CPEBSDL语言规则对应的上下文无关文法G(CPEBSDL),并给出了G(CPEBSDL)的乔姆斯基范式,在此基础上给出了一个判定协议行为的CPEBSDL语言描述是否合法的判定算法——CYK协议行为序列的合法性验证算法.作为一个实例,用CPEBSDL语言对ISDN数据链路层协议LAPD的链接过程进行了完整的描述,并给出了一个判定协议行为序列是否合法的例子.
构造基于信任机制的自组织资源拓扑
王 伟 曾国荪
2007, 44(11):  1849-1856. 
摘要 ( 466 )   HTML ( 0)   PDF (484KB) ( 313 )  
相关文章 | 计量指标
利用P2P覆盖网络(P2P overlay networks)进行资源组织是当前研究的热点,如何保证资源获取的可靠性是研究人员面临的一个主要问题.利用节点的动态自组织属性,基于节点物理位置的拓扑构造可以提高P2P网络的性能,但没有关注P2P网络中恶意节点的问题;基于偏好的拓扑构造可以有效地提高资源共享和搜索的效率,但没有考虑节点实际提供服务的能力和节点行为的可靠性.提出了一个基于信任机制的自组织资源拓扑构造方案,利用Bayesian方法根据节点的行为来评估节点的信任度,通过节点间基于信任关系的链路更新,构造出新的自组织拓扑结构.仿真实验表明,该拓扑结构不仅有利于节点发现资源的效率,提高整个P2P网络的交互性能,还能使节点聚集在服务能力较强的可信节点周围,保证资源选取的可靠性.
P2P流媒体Cache的置换算法
陈 刚 张伟文 吴国新
2007, 44(11):  1857-1865. 
摘要 ( 390 )   HTML ( 0)   PDF (564KB) ( 307 )  
相关文章 | 计量指标
P2P流媒体cache是一种有效减少带宽开销、提高对象利用率的技术,通常采用FIFO,LRU等算法置换内容.然而,流媒体不同于Web对象,P2P网络也有别于客户/服务器模式.在分布式应用中这些算法可能影响系统的性能,为此,分析了FIFO和LRU置换算法,提出了基于供求关系的SD算法,以及基于分片副本数量的REP算法,并对其进行评估和比较.针对不同的节点到达间隔,将SD和REP同FIFO,LRU进行比较,发现在启动延迟、媒体副本数量和根节点依赖度方面SD和REP几乎均优于FIFO和LRU. 同LSB(least sent bytes)算法相比,某些场景中SD的启动延迟减少了约40%,而REP在副本数量方面远远超过LSB的结果,说明在P2P网络流媒体服务中使用SD和REP缓存置换算法有助于提高系统性能.
SEEL:无线传感器网络下自适应、低延迟的节能媒质接入控制协议
龚海刚, 余昌远, 刘 明, 易发胜, 王晓敏, 陈力军,
2007, 44(11):  1866-1872. 
摘要 ( 389 )   HTML ( 0)   PDF (405KB) ( 387 )  
相关文章 | 计量指标
无线传感器网络有着广泛的应用前景,然而由于传感器节点能量有限,因此传感器网络上运行的协议必须具备能量有效性以获得较长的生命周期.而媒质接入控制子层是节点能量消耗的主要所在,因此无线传感器网络设计的关键问题之一是媒质的接入控制.提出了一种自适应低延迟的节能MAC协议——SEEL协议,根据当前的网络负载自适应地调节竞争窗口的大小,从而减小节点数据传送的碰撞几率和由于碰撞而导致的能量消耗;采用了快速退避机制,减少了节点在退避过程中的空闲监听时间;扩展了RTS/CTS消息机制,可减少节点在每帧活动阶段的时间以及减小数据的延迟,两者都能节约能量的使用.实验结果显示,SEEL协议具有比S-MAC和TEEM协议更好的性能.
CICQ交换机中一类服务可保障的调度策略研究
李 季, 曾华NFDC8, 许登元,
2007, 44(11):  1873-1880. 
摘要 ( 395 )   HTML ( 0)   PDF (491KB) ( 356 )  
相关文章 | 计量指标
具备QoS保障能力的快速调度算法是高速交换机的首选.基于EPFTS(Ethernet-oriented physical frame timeslot switching)和CICQ(combined input-crosspoint-queued)交换技术的特点,提出了一类新的调度策略——TRWFS(timeslot reservation weighted fair scheduling).为确保各端口对上保障业务的预留带宽,TRWFS以各端口对上保障业务预留时槽数为调度权重,以优先调度保障业务和平衡各保障业务的盈余时槽(surplus timeslot,定义为现实系统和理想系统之间的服务差额)为业务调度准则.基于该调度策略进一步提出了两种实现算法——TRWFS_I和TRWFS_II,总体上使实现TRWFS的时间复杂度降至O(1).性能分析和仿真实验结果均表明两种调度算法都达到了服务保障的设计目标,仿真实验结果还表明CICQ排队方式下与其他调度算法相比,TRWFS和轮询调度综合的调度机制具有交叉缓存容量要求更低的优点.
基于DTE策略的安全域隔离Z形式模型
卿斯汉, 李丽萍, 何建波, 沈晴霓,
2007, 44(11):  1881-1888. 
摘要 ( 450 )   HTML ( 1)   PDF (441KB) ( 353 )  
相关文章 | 计量指标
基于DTE策略的安全域隔离技术是构造可信系统的基本技术之一.但现有DTE实现系统存在安全目标不明确、缺乏对系统及其安全性质的形式定义和分析的缺点,导致系统安全性难以得到保证.定义了一个基于DTE策略的安全域隔离模型,采用Z语言形式定义了系统状态、基于信息流分析的不变量和安全状态,并借助Z/EVES工具给出验证系统安全的形式分析方法.解决了DTE系统的形式化建模问题,为安全域隔离技术的实现和验证奠定了基础.
Windows环境下信任链传递及其性能分析
李晓勇, 韩 臻, 沈昌祥,
2007, 44(11):  1889-1895. 
摘要 ( 491 )   HTML ( 1)   PDF (368KB) ( 343 )  
相关文章 | 计量指标
动态多路径信任链(DMPTC)是一个基于软件类型特点的系统可信验证和保证机制. DMPTC对静态的系统软件和动态的应用软件加以区分,并采用不同的方式和策略对软件的装载运行加以控制,使得计算平台只运行那些有可信来源的可执行代码,从而确保平台的可信和安全. DMPTC可以用来防范各种已知和未知的恶意代码,并可以用来加强对生产信息系统中应用软件的管理和控制. DMPTC可以克服传统的静态单路径信任传递在系统灵活性和实用性层面的缺陷,并且在系统性能方面进行了深入的考虑和深层的优化.系统性能分析和实际测试结果都表明,在Windows系统平台上实现的DMPTC对系统运行带来的性能损失小于1%.
基于Game理论的μ-演算公理化
刘万伟 王 戟 陈火旺
2007, 44(11):  1896-1902. 
摘要 ( 404 )   HTML ( 0)   PDF (459KB) ( 274 )  
相关文章 | 计量指标
随着软硬件系统复杂性的不断提高,各种验证技术被越来越广泛的使用.模型检验技术是一种保证软硬件设计、实现正确性的有效技术.在针对软硬件的模型验证技术中,一般采用时序逻辑作为规约语言.模态μ-演算是模态和时序逻辑中应用较为广泛的一种,它具有语法成分简洁、表达能力强等特点.扩展了Lange和Stirling基于Focus Game的LTL和CTL的公理化方法.提出了一种基于Game理论的μ-演算公式的可满足性的测试方法,该种方法能够将模态μ-演算公式的可满足性问题转化为Focus Game的求解问题.进一步,基于这套Game规则,给出了一个新的关于μ-演算可靠完备的推理系统.同已有的μ-演算公理系统相比,该推理系统相对直观、简洁.
基于Game理论的μ-演算公理化
刘万伟 王 戟 陈火旺
2007, 44(11):  1896-1902. 
摘要 ( 291 )   HTML ( 0)   PDF (459KB) ( 397 )  
相关文章 | 计量指标
随着软硬件系统复杂性的不断提高,各种验证技术被越来越广泛的使用.模型检验技术是一种保证软硬件设计、实现正确性的有效技术.在针对软硬件的模型验证技术中,一般采用时序逻辑作为规约语言.模态μ-演算是模态和时序逻辑中应用较为广泛的一种,它具有语法成分简洁、表达能力强等特点.扩展了Lange和Stirling基于Focus Game的LTL和CTL的公理化方法.提出了一种基于Game理论的μ-演算公式的可满足性的测试方法,该种方法能够将模态μ-演算公式的可满足性问题转化为Focus Game的求解问题.进一步,基于这套Game规则,给出了一个新的关于μ-演算可靠完备的推理系统.同已有的μ-演算公理系统相比,该推理系统相对直观、简洁.
一种有效的贪婪模式匹配算法
张 治 施鹏飞
2007, 44(11):  1903-1911. 
摘要 ( 527 )   HTML ( 2)   PDF (563KB) ( 429 )  
相关文章 | 计量指标
模式匹配问题是意图获得两个模式中所包含个体对象之间的语义匹配和映射,其结果表示源模式的个体对象与目标模式的个体对象之间存在特定的语义关联.它在数据库应用领域起到关键性的作用,例如数据集成、电子商务、数据仓库、XML消息交换等,特别地,它已成为元数据管理的基本问题.然而,模式匹配很大程度上依赖人工的操作,是一个费时费力的过程.模式匹配问题可以归约为一个组合优化问题:多标记图匹配问题.首先,将模式表示为多标记图,将模式匹配转换为多标记图匹配问题.其次,提出多标记图的相似性度量方法,进而提出基于多标记图相似性的模式匹配目标优化函数.最后,在这个目标函数基础上设计实现了一个贪婪匹配算法,其最显著的特点是综合多种可用的标记信息,灵活准确地获得最优的匹配结果.
容错优先级混合式分配搜索算法
李 俊, 曹万华, 阳富民, 涂 刚, 卢炎生, 罗 威,
2007, 44(11):  1912-1919. 
摘要 ( 356 )   HTML ( 0)   PDF (475KB) ( 306 )  
相关文章 | 计量指标
在实时系统中,由于任务未能及时产生正确结果将导致灾难性后果,容错对于实时系统的有效性及可靠性至关重要.基于最坏响应时间计算的可调度性分析,提出了一种容错优先级混合式分配搜索算法.这种算法通过允许替代任务既能运行在高优先级别上,又可运行在低优先级别上,有效地提高了系统的容错能力.通过实验测试,与目前所知的同类算法相比,在提高系统容错能力方面更为有效.
图像中多语种文本提取的高斯混合建模方法
付 慧, 刘峡壁, 贾云得,
2007, 44(11):  1920-1926. 
摘要 ( 370 )   HTML ( 4)   PDF (467KB) ( 331 )  
相关文章 | 计量指标
建立了相邻字符区域的高斯混合模型,用于区分字符与非字符.在此基础上,提出了一种从图像中提取多语种文本的方法.首先对输入图像进行二值化,并执行形态学闭运算,使二值图像中每个字符成为一个单独的连通成分.然后根据各连通成分重心的Voronoi区域,形成连通成分之间的邻接关系;最后在贝叶斯框架下,基于相邻字符区域的高斯混合模型计算相应的伪概率,以此为判据将每个连通成分标注为字符或非字符.利用所提出的文本提取方法,进行了复杂中英文文本的提取实验,获得大于97%的准确率和大于80%的召回率,证实了方法的有效性.
基于核方法的雷达目标一维距离像识别
于雪莲, 汪学刚, 刘本永,
2007, 44(11):  1927-1931. 
摘要 ( 293 )   HTML ( 0)   PDF (304KB) ( 292 )  
相关文章 | 计量指标
由于雷达目标及其所处环境的复杂性,导致不同目标之间的关系往往是非线性的.研究基于核的非线性方法,并将其应用于雷达目标一维距离像识别.核Fisher判别分析(KFDA)是一种抽取非线性特征的最有效方法之一,但它往往会面临小样本问题.针对此问题,给出一种null-KFDA方法,对距离像进行特征提取.然后,采用一种新的核非线性分类器——KNR(kernel-based nonlinear representor),对所提取的特征进行分类.对3种飞机的实测距离像进行实验,结果验证了null-KFDA的有效性.此外,与非线性支持向量机(SVM)和径向基函数神经网络(RBFNN)相比,KNR分类器具有更优的识别性能.
保内部相似性的平面形状混合算法
张冬梅 刘利刚
2007, 44(11):  1932-1938. 
摘要 ( 379 )   HTML ( 0)   PDF (446KB) ( 383 )  
相关文章 | 计量指标
为了在计算机动画中可以得到较好的图形过渡效果,提出了一保持平面多边形内部相似性的形状混合算法,从而有效地避免了中间多边形发生局部萎缩或者膨胀的现象.此方法从源和目标多边形的同构三角剖分出发,对同构三角网格每一个夹角处表示边角关系的几何量线性插值得到相对应的中间几何量,通过这些中间几何量以及它们与顶点坐标之间的关系来建立线性方程组,给定初始条件后用现成的程序库快速求解来得到中间三角网格(其边界即为中间多边形).还通过引入特征多边形来保持混合多边形的全局视觉特征.该算法计算量小、运行效率高,对形状复杂的多边形仍然可以得到满意的结果,适合于实际应用中实时的要求.
遗传算法用于曲线的误差约束多边形近似
王 斌 舒华忠 罗立民
2007, 44(11):  1939-1945. 
摘要 ( 323 )   HTML ( 0)   PDF (391KB) ( 323 )  
相关文章 | 计量指标
提出了一种求解曲线的误差约束多边形近似问题的遗传算法.其主要思想是:1)采用变长染色体编码机制,以减少存储空间和计算时间的消耗;2)针对问题的特点,提出了一种新的杂交算子——基因消去杂交,以尽可能地消去染色体上的冗余基因,从而提高算法的寻优能力;3)采用染色体修复策略处理遗传操作产生的不可行解,该策略通过迭代地向染色体追加有价值的候选基因来实现染色体的修复,并提出一种对染色体的候选基因进行评估的机制.通过实验评估并与其他遗传算法进行比较,结果表明,提出的算法性能更优越.
二进制翻译中的X86浮点栈处理
谢海斌, 武成岗, 崔慧敏, 李 晶,
2007, 44(11):  1946-1954. 
摘要 ( 467 )   HTML ( 1)   PDF (591KB) ( 320 )  
相关文章 | 计量指标
二进制翻译系统是一种基于软件的跨平台代码迁移系统,它将一种体系结构的二进制代码翻译成另一种体系结构的二进制代码.二进制翻译可以用于解决遗产代码的迁移问题,也可以实现不同硬件平台之间软件的通用.浮点栈的处理已成为以X86为源的二进制翻译的研究中的关键性问题之一,如何处理X86浮点栈问题直接关系到以X86为源的二进制翻译系统的性能.针对X86浮点寄存器栈的特征,提出了一种扩展虚拟栈(extending virtual stack)处理方案.它采用归一的方法,保证了每个基本块中的运算所涉及到的浮点寄存器可以直接映射到目标机器中的浮点寄存器,确保了翻译的效率,并利用翻译时的分析避免了在入口处不必要的判断;同时还给出了在基本块入口处判别一个基本块是否会出现浮点栈上溢和下溢的充分必要条件,为生成更加高效的代码提供了条件.实验表明,它能够在保证正确实现其功能的前提下,获得更好的执行效率.
Web服务合成的相容性与替换性分析
史玉良, 王海洋, 张 亮, 施伯乐,
2007, 44(11):  1955-1961. 
摘要 ( 450 )   HTML ( 0)   PDF (361KB) ( 357 )  
相关文章 | 计量指标
形式化的分析有助于Web服务的合成.已有的合成分析方法,验证的重点是Web服务合成时形成的全局交互流程是否与预先定义的模型相匹配,忽略了合成时各个Web服务之间的行为是否相容.通过自动机对基于WSCI规范描述的Web服务进行形式化描述.在此基础上,提出了一个Client/Server模型,定义了Web服务合成的相容性概念,并提供相应的算法进行验证,保证了Web服务合成的正确性.在相容性分析的基础上,考虑到Web服务动态性的特点,定义了Web服务的替换性概念,并给出了保证替换服务正确性的定理.
软件中的错误传播分析
李爱国, 洪炳NFDD,, 王 司, 朴松昊,
2007, 44(11):  1962-1970. 
摘要 ( 521 )   HTML ( 0)   PDF (506KB) ( 298 )  
相关文章 | 计量指标
错误传播是分析可靠性系统不确定性中的一基本问题,可用于发现系统中最易受到错误攻击的部分及各部分之间的相互影响.分别在信号和模块级别上研究了错误在软件中的传播过程,并定义了描述此过程的参数及其计算方法,其中首次提出了模块泄漏率和活动率的概念并给出了计算方法;然后把该错误传播分析框架应用于某卫星光纤陀螺捷联航姿控制系统上.通过故障注入实验确定了其中的分析参数,验证了提出的错误传播框架的可行性与正确性.
基于时态变量对象关系模型及代数运算
叶小平
2007, 44(11):  1971-1979. 
摘要 ( 392 )   HTML ( 0)   PDF (511KB) ( 318 )  
相关文章 | 计量指标
时态数据处理多是基于关系数据库平台,时态数据库模型也以时态关系数据模型为主.关系数据模型难以处理具有复杂类型的数据对象,而面向对象数据模型还缺乏商业化应用平台.现有关系数据库平台大多增加了面向对象基本功能,形成了对象关系数据库系统,因此将对象关系数据模型进行时态扩充就显得十分必要和具有可行性.首先在现有时态关系数据模型基础上,提出了一种基于对象关系双时态数据模型,而这种数据模型适合于在现有数据库平台上实现;其次,在该模型框架内,讨论了时态对象关系模式与时态关系模式相互间的联系与转换,这也是由时态关系扩充到对象关系的基本要求;再次,分析了时态模型中时态变量复杂语义和相应绑定算法,这是时态数据库能够有效运行的基本课题之一;最后,研究了基于时态变量复杂语义的时态对象关系数据操作代数,从而为时态对象关系模式的查询进行了必要的理论探讨.
利用分区和距离实现高维空间快速KNN查询
梁俊杰, 王长磊,
2007, 44(11):  1980-1985. 
摘要 ( 748 )   HTML ( 0)   PDF (333KB) ( 498 )  
相关文章 | 计量指标
在高维空间KNN查询算法中,近似向量和一维转换表示法能有效克服维数灾难,结合这两种思想,提出一种基于区位码和距离的索引结构(BD)以实现快速KNN查询.根据高维空间向量分布特点,合理分区使得大量分布在空间表面的点尽可能地划分到不同的分区中,提高检索剪枝效率.引入区位码概念和转换函数,将高维向量近似表示并转换为一维数值形式,组织成B\++树索引.利用快速KNN查询算法,实现两层过滤,缩小搜索范围,降低树搜索代价.采用模拟数据和真实数据,大量实验验证了BD比其他同类索引具有更高的检索效率.