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

当期目录

2008年 第45卷 第10期    出版日期:2008-10-15
论文
基于Petri网的混惑检测
赵明峰, 宋 文, 杨义先,
2008, 45(10):  1631-1637. 
摘要 ( 567 )   HTML ( 0)   PDF (700KB) ( 441 )  
相关文章 | 计量指标
在Petri网中,并发和冲突是两个重要的概念,并发和冲突现象混淆的系统特征称之为混惑,当系统存在混惑时获取一个正确的执行以及分析系统性质较为困难,因而存在混惑的系统不是一个好的模型.网论认为并不是并发和冲突相结合带来了麻烦,而是它们相结合导致的混惑带来了麻烦.所以,对一般Petri网模型混惑的检测及可能影响混惑的子网结构研究显得非常必要.在基本网系统下,以混惑的定义为基础,提出了结构混惑的定义,在此基础上定义了3类基本结构混惑,证明了这3类可构成结构混惑的最小完全集,给出检测结构混惑的算法和混惑的检测方法,并将该算法和方法应用到工作流网中,以实例定性分析了结构混惑与混惑的区别和联系以及对合理性的影响.
模型检测基于概率时间自动机的反例产生研究
张君华 黄志球 曹子宁
2008, 45(10):  1638-1645. 
摘要 ( 550 )   HTML ( 2)   PDF (756KB) ( 585 )  
相关文章 | 计量指标
模型检测基于概率系统的反例产生问题,在最近引起人们的关注.已有的工作主要围绕模型检测Markov链的反例产生而开展.基于概率时间自动机(PTA)是Markov链的不确定性和系统时钟的扩展.关注的是模型检测PTA的反例产生问题.首先通过在PTA上寻找概率之和恰好大于λ的k条最大概率的路径,并根据这些路径和原PTA构造原PTA的一个子图,从而快速找到违背性质的具有较少证据的反例.然后精化此结果——通过逐条加入上述各条最大概率的路径来精确地计算已加入路径所构成的PTA子图的最大概率.由于考虑到符号状态交集对概率系统的影响,可以得到证据更少的反例.
一种共游程码的测试数据压缩方案
詹文法, 梁华国, 时 峰, 黄正峰, 欧阳一鸣,
2008, 45(10):  1646-1653. 
摘要 ( 546 )   HTML ( 0)   PDF (880KB) ( 470 )  
相关文章 | 计量指标
提出了一种新的基于游程编码的测试数据压缩/解压缩的算法:共游程码(SRLCS)编码,它在使用较短的代码字来代替较长的游程的传统游程编码基础上,进一步充分利用了相邻游程之间的相关性,使用一位来代替与前一游程相同的整个后一游程,这样整个后一游程可以用一位来表示,达到从多位到一位的转换,进一步压缩了测试数据.由于测试数据中存在大量的无关位,对无关位适当的赋值,可以增加连续游程长度相同的概率,提出了一种针对共游程码的无关位填充算法.理论分析和实验结果证明该方案具有高数据压缩率、硬件实现简单等特点.
基于缓冲Cell的用户迁移方法研究
周 忠 王少峰 吴 威
2008, 45(10):  1654-1661. 
摘要 ( 431 )   HTML ( 0)   PDF (1776KB) ( 555 )  
相关文章 | 计量指标
分布式虚拟环境中现有的用户迁移方法主要基于固定缓冲区,而近年研究热点的多服务器结构采用动态缓冲区,服务器区域调整中受影响的用户不能进行迁移,影响了交互性和效率.提出一种基于缓冲Cell的用户迁移方法,将缓冲区用一组Cell来表示,将用户替身运动和区域调整引起的迁移抽象为4项状态迁移条件.根据用户和所属Cell的状态变化,触发用户状态迁移,多个用户可并发高效地完成迁移.实验表明,这种用户迁移方法可有效支持用户的并发迁移,并具有较低的通信附加负载.
面向低概率事件场景的传感器网络分簇控制算法
刘林峰, 金 杉,
2008, 45(10):  1662-1668. 
摘要 ( 458 )   HTML ( 0)   PDF (853KB) ( 530 )  
相关文章 | 计量指标
为了延长网络生命期,无线传感器网络必须高效地消耗电池能量,而网络拓扑作为上层协议的重要平台,是实现这一目标的支撑基础.WSN的一个显著特征即具有应用多样性,为了研究符合低概率事件场景的传感器网络拓扑控制方案,建立并分析了传感器网络模型.由于在低概率事件场景下节点侦听能耗占据主导地位,经研究发现此时生命期目标与k中心问题本质上具有密切联系,可视为k中心问题的对偶问题,因此针对分簇机制分别设计了3个阶段执行:邻居信息获取阶段、簇头确定阶段和节点归属阶段,从而引入了一种基于k中心问题的周期性分簇控制算法PCA,PCA算法体现了负载均衡的思想,同时尽可能减少了簇头数目.模型理论分析和仿真实验结果都表明,PCA算法能得到快速部署,并且PCA算法能获得较优的拓扑结构,有效地延长了WSN的生命期.
网格局部性及其优化研究
艾丽华 罗四维
2008, 45(10):  1669-1675. 
摘要 ( 422 )   HTML ( 0)   PDF (1077KB) ( 424 )  
相关文章 | 计量指标
数据网格已逐步在科学研究领域得到应用.提高数据网格的性能以适应分布式数据管理已经成为研究数据网格的一个热点.提出了网格局部性的概念,分析了网格局部性对数据网格性能的影响,并从增强网格局部性的角度对数据网格的性能进行优化,提出了综合跳-扩散副本替换策略(jump-DRP)和参考生物外激素的任务调度策略(JARIP).实验结果表明,考虑了网格局部性因素的jump-DRP与JARIP的策略组合提高了网格平台的任务处理性能,并对各类应用背景及任务的复杂程度具有鲁棒性.
基于可信平台的一种访问控制策略框架——TXACML
聂晓伟, 冯登国,
2008, 45(10):  1676-1686. 
摘要 ( 433 )   HTML ( 0)   PDF (887KB) ( 718 )  
相关文章 | 计量指标
根据可信平台访问控制需求,提出一个可信平台属性分类规则,定义属性评估函数,可以实现可信平台数据安全分发和访问.同时针对XACML现有的策略合成算法不能有效满足可信平台自动方策略复合需求,设计了一个基于平台可信度的策略合成算法,该算法可以使策略的优先级和可信度保持一致,实现自动方策略复合.在此基础上,进一步对XACML实施扩展,形成可信平台策略语言框架TXACML(XACML based on trusted platform).采取TXACML对一个实例给出了策略描述和策略合成过程,验证了TXACML的有效性.
非双线性映射下一种实用的和可证明安全的IBE方案
徐 鹏 崔国华 雷凤宇
2008, 45(10):  1687-1695. 
摘要 ( 550 )   HTML ( 0)   PDF (857KB) ( 597 )  
相关文章 | 计量指标
根据MOV归约理论,采用双线性映射构造的基于身份加密方案使得该方案不具有椭圆曲线高效的优点.针对这一点,参考组合公钥体制提出了一种非双线性映射下可证明安全的基于身份加密方案,并且通过采用Katz-Wang的双公钥思想,使得该方案在随机预言机模型下的安全性证明中具有“紧”的归约.为了说明提出方案具有较好的实用性,分析了该方案的归约程度和执行效率.为了使提出方案在具有大量用户的系统中同样具有实用性,提出了多域基本模型.
针对同义词替换信息隐藏的检测方法研究
罗 纲 孙星明 向凌云 刘玉玲 甘 灿
2008, 45(10):  1696-1703. 
摘要 ( 729 )   HTML ( 1)   PDF (1030KB) ( 820 )  
相关文章 | 计量指标
基于同义词替换的文本信息隐藏方法,可以通过对载体中的同义词进行有选择的替换来嵌入隐藏信息.通过分析,发现这种方法嵌入隐藏信息后会导致载体文本中同义词结对概率的明显增加.基于此,提出了一种通过分析文本中同义词结对值来进行隐藏信息检测的算法.实验表明,该检测算法漏警率约为4%,虚警率约为9.8%,证明该检测算法可以有效地检测基于同义词替换的文本信息隐藏方法隐藏的信息.
基于博弈的MANETs信任模型研究
罗俊海 范明钰
2008, 45(10):  1704-1710. 
摘要 ( 583 )   HTML ( 0)   PDF (1358KB) ( 524 )  
相关文章 | 计量指标
移动Ad-Hoc网络(MANET)是由一组带有无线收发装置的移动节点组成的无须固定设置支持的临时性的通信网络.MANETs具有开放的媒质、动态的拓扑结构、分布式的合作和受限的网络能力等基本特点.在MANETs中,节点之间相互信赖路由和转发数据包,节点间的合作是非常重要的.但是由于自私节点为了储存能量和其他资源,而不参与转发数据.由于MANETs通信没有第3方的中心认证,所以集中于强制合作是不适应的.基于博弈研究MANETs中的节点行为,根据节点的信誉度来获得资源,刺激节点共享资源和转发数据.提出了基于博弈理论的信任模型,鼓励包转发,约束自私节点.仿真结果表明该信任模型能够识别自私节点并且能在信任节点之间建立信任,提高了整个网络效率.
一种对多级安全模型安全性的分析方法
司天歌 谭智勇 戴一奇
2008, 45(10):  1711-1717. 
摘要 ( 517 )   HTML ( 0)   PDF (659KB) ( 454 )  
相关文章 | 计量指标
由于BLP模型的基本安全公理不能完全证明模型的安全性,因此,在分析BLP改进模型的安全性时,如果模型的安全策略十分复杂而不能直接判断其安全性,或者模型由于改变了安全属性定义等而动摇了基本安全公理的推理基础时,应从其他角度证明改进模型的安全性.利用基于系统动作的不干扰模型,从信息流的角度给出一种对多级安全模型的形式化分析方法,为多级安全模型的安全性验证提供了一种新的途径.该不干扰模型把不干扰关系扩展到系统动作之间,提出了新的单步展开定理,可描述多级安全模型中的动态策略.通过以ABLP与DBLP模型为实例进行分析,说明了该分析方法的实用性.
战略互联网风险检测与故障分析方法
李千目 刘凤玉
2008, 45(10):  1718-1723. 
摘要 ( 523 )   HTML ( 0)   PDF (822KB) ( 576 )  
相关文章 | 计量指标
随着新一代战略互联网规模的不断扩大,网络应用不断增加,传统的网络故障诊断系统功能单一、操作复杂、效率低下,已不能满足军网管理的发展需要.基于粗糙集的神经网络理论,提出网络性能检测与故障分析的RSNN算法,实现不一致情况下的故障规则获取和学习样本的净化处理.该算法具有简化样本、适应性强、容错性高等特点,能有效处理网络故障诊断中噪声和不相容的信息.由于诊断问题的实质是一种映射,该算法用一种前馈型网络来逼近这种映射关系,实现对故障的有效分类.实验表明,利用该方法实现的系统与同类的其他方法相比,大幅提高了诊断准确率和诊断速度.
多特征组合和图切割支持的物体/背景分割方法
邓 宇 李 华
2008, 45(10):  1724-1730. 
摘要 ( 568 )   HTML ( 0)   PDF (1458KB) ( 560 )  
相关文章 | 计量指标
运动物体分割是计算机视觉应用领域中的一个基本问题,阴影和亮度变化均易造成分割结果错误.通过组合多种图像特征,实现了一种新的检测运动物体方法.一方面,组合图像的颜色、梯度和纹理特征,利用梯度和纹理信息对亮度变化不敏感的特性,提高运动物体分割的准确性;另一方面,使用图切割算法对物体/背景进行分割,在不影响整体分割结果前提下修正局部判别错误的像素点,分割结果噪声少且稳定性强.对不同场景的分割结果表明,该方法是高效的和实用的.
一种基于采样点的大规模群体实时三维可视化方法
束 搏, 毛天露, 徐文彬, 王兆其,
2008, 45(10):  1731-1738. 
摘要 ( 457 )   HTML ( 0)   PDF (2203KB) ( 567 )  
相关文章 | 计量指标
大规模群体的三维可视化是虚拟现实领域的研究热点之一.目前,由于驱动方法与渲染效率的问题,在虚拟空间中创建的大规模虚拟群体很难同时满足驱动与渲染过程的逼真与实时.该问题对于群体规模庞大,个体外形、动作具有一定程度个性化,需要进行独立运动控制的场景尤为明显.针对这一问题,提出了一个高效的大规模虚拟群体三维可视化方法:首先,通过使用模板派生技术从少量模板模型派生出大量外观各异的个体模型;其次,使用运动数据个性化变形技术实现了运动数据的重用;最后,使用基于采样点的渲染技术实现了大规模数据的实时显示.在上述工作基础上,研究并开发了一套大规模虚拟群体的三维可视化系统,能够方便的在普通PC机上实时、逼真的展示大规模的运动虚拟群体,并实现了60000群众紧急疏散过程的实时三维可视化.
基于局部复杂度和初级视觉特征的自底向上注意信息提取算法
田 媚 罗四维 黄雅平 赵嘉莉
2008, 45(10):  1739-1746. 
摘要 ( 440 )   HTML ( 0)   PDF (2157KB) ( 1310 )  
相关文章 | 计量指标
借鉴心理学中有关视觉注意的研究成果,提出了一种新的自底向上的注意信息提取算法.自底向上的注意信息由图像中每个点对应区域的显著性构成,区域的尺度自适应于局部特征的复杂度.新的显著性度量标准综合考虑了局部复杂度、统计不相似和初级视觉特征这3个方面的特性.显著区域在特征空间和尺度空间中同时显著.获取的自底向上的注意信息具有旋转、平移、比例缩放不变性和一定的抗噪能力.以该算法为核心,构建了一个注意模型,将其应用于多幅自然图像的实验证明了算法的有效性.
关于AdaBoost有效性的分析
付忠良
2008, 45(10):  1747-1755. 
摘要 ( 667 )   HTML ( 1)   PDF (1010KB) ( 586 )  
相关文章 | 计量指标
在机器学习领域,弱学习定理指明只要能够寻找到比随机猜测略好的弱学习算法,则可以通过一定方式,构造出任意误差精度的强学习算法.基于该理论下最常用的方法有AdaBoost和Bagging.AdaBoost和Bagging 的误差分析还不统一;AdaBoost使用的训练误差并不是真正的训练误差,而是基于样本权值的一种误差,是否合理需要解释;确保AdaBoost有效的条件也需要有直观的解释以便使用.在调整Bagging错误率并采取加权投票法后,对AdaBoost和Bagging的算法流程和误差分析进行了统一,在基于大数定理对弱学习定理进行解释与证明基础之上,对AdaBoost的有效性进行了分析.指出AdaBoost采取的样本权值调整策略其目的是确保正确分类样本分布的均匀性,其使用的训练误差与真正的训练误差概率是相等的,并指出了为确保AdaBoost的有效性在训练弱学习算法时需要遵循的原则,不仅对AdaBoost的有效性进行了解释,还为构造新集成学习算法提供了方法.还仿照AdaBoost对Bagging的训练集选取策略提出了一些建议.
基于势结构的任一时间联盟结构生成算法
苏射雄 胡山立 郑盛福 林超峰 骆剑彬
2008, 45(10):  1756. 
摘要 ( 349 )   HTML ( 0)   PDF (680KB) ( 492 )  
相关文章 | 计量指标
联盟形成是多Agent系统中的一个关键问题. 人们寻求能极大化联盟值总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解. Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的.Dang等人给出的算法是所见到的第1个不以层为单位的搜索算法,对于较小的限界明显地优于Sandholm等人给出的算法. 深刻分析了联盟结构间的关系,采用更小的搜索粒度(势结构),提出基于势结构的任一时间算法,在搜索最底两层及顶层后,进一步搜索势结构集合CCS(n, b)对应的未搜索过的联盟结构,渐进地给出越来越低的限界,大大改进了Sandholm等人(快10\+\{35\}倍,当n=100,K=2)和Dang等人(快10\+\{18\}倍,当n=100,K=3)的工作.
基于策略迭代和值迭代的POMDP算法
孙 湧 仵 博 冯延蓬
2008, 45(10):  1763-1768. 
摘要 ( 1030 )   HTML ( 7)   PDF (551KB) ( 545 )  
相关文章 | 计量指标
部分可观察Markov决策过程是通过引入信念状态空间将非Markov链问题转化为Markov链问题来求解,其描述真实世界的特性使它成为研究随机决策过程的重要分支.介绍了部分可观察Markov决策过程的基本原理和决策过程,提出一种基于策略迭代和值迭代的部分可观察Markov决策算法,该算法利用线性规划和动态规划的思想,解决当信念状态空间较大时出现的“维数灾”问题,得到Markov决策的逼近最优解.实验数据表明该算法是可行的和有效的.
一种基于动态平衡树的在线索引快速构建方法
郭瑞杰, 程学旗, 许洪波, 王 斌, 丁国栋,
2008, 45(10):  1769-1775. 
摘要 ( 480 )   HTML ( 0)   PDF (1335KB) ( 698 )  
相关文章 | 计量指标
倒排索引的构建可以通过离线方式高效地完成,但是仅当整个数据集索引完毕后方可提供检索服务.在线索引可以在构建倒排索引的同时提供检索服务,新加入的文档即刻可供检索.提出了一种基于动态平衡树的在线索引更新策略,利用动态平衡树控制索引合并过程,使索引合并总是在大小相近的子索引之间进行,以减少索引合并代价,同时可以调节索引和检索之间的性能平衡.该方法提供了一个基于合并的在线索引更新框架, 与已有方法相比具有更好的通用性、更高的性能和更好的规模可扩展性.在由4000万张网页构成的270 GB Web数据集上运行的实验表明,该方法在实际系统中是高效的,将索引更新的性能提高了92.28%,而检索性能仅下降4.79%,大幅度降低了在线索引构建的代价.
基于多重索引模型的大规模词典近似匹配算法
龚才春, 黄玉兰, 许洪波, 白 硕,
2008, 45(10):  1776-1781. 
摘要 ( 506 )   HTML ( 0)   PDF (746KB) ( 654 )  
相关文章 | 计量指标
编辑器的拼写校正、搜索引擎的查询纠正、光学字符识别的结果检查等领域都用到词典近似匹配算法.传统单索引模式很难在高性能的前提下保证高召回率.词典越大问题越严重.提出了大规模词典近似匹配的多重索引模型,首先将背景词典根据单词长度划分为若干子词典,对各子词典按照一定策略建立unigram,bigram,trigram,quadgram中的一种或若干种索引,当查找用户模式P的近似匹配时,根据模式P检索特定N-gram索引链,从而得到候选近似匹配集合C,对C中每一个单词W,计算P与W的编辑距离即可输出P的所有最终匹配结果R.实验表明,基于多重索引模型的词典近似匹配算法能够大幅度减少候选近似匹配结果的数量,从而提高词典近似匹配的速度.
精确覆盖问题的O(1.414\+n)链数DNA计算机算法
李肯立, 刘 杰, 杨 磊, 刘文斌,
2008, 45(10):  1782-1788. 
摘要 ( 436 )   HTML ( 0)   PDF (741KB) ( 592 )  
相关文章 | 计量指标
DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2\+n)减少至O(1.414\+n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果.
二进制翻译中解析多目标分支语句的图匹配方法
陈 龙, 武成岗, 谢海斌, 崔慧敏, 张兆庆,
2008, 45(10):  1789-1798. 
摘要 ( 471 )   HTML ( 0)   PDF (1089KB) ( 528 )  
相关文章 | 计量指标
二进制翻译技术现已成为实现软件移植的重要手段.在二进制翻译系统中,如何有效地挖掘程序的代码并对其进行高效翻译是影响系统性能的关键,而二进制代码中间接跳转语句的存在,使得静态时难以得到它的跳转目标,影响了代码的发掘率和最终的翻译效果.在通常的应用程序中,间接跳转指令经常用来实现多目标分支语义,分支目标存放在跳转表中.提出了一种解析多目标分支语句及其跳转表的方法,能够挖掘出间接跳转的目标,进而对其进行有效翻译并提高二进制翻译系统的性能.该方法提出使用语义图来对预期语义进行刻画和表达.语义图能够对考察的指令序列进行语义提取,识别出与预期语义相匹配的指令流,还可以应对编译器在不同优化选项下生成的指令,并能有效滤除不相关指令带来的干扰.实验结果表明,对于SPEC CINT2000中的部分测试用例,代码翻译的覆盖率可以提高9.85%~22.13%,相应带来的性能提升可达到8.30%~17.71%,而使用的算法时间复杂度仅为O(1).
一种面向服务的事件驱动架构信息集成平台构造方法
杨志义, 杨 刚, 张海辉,
2008, 45(10):  1799-1806. 
摘要 ( 413 )   HTML ( 2)   PDF (1118KB) ( 721 )  
相关文章 | 计量指标
信息集成方法研究对企业异构复杂应用集成具有重要的学术和应用价值.提出一种面向服务的事件驱动架构SOEDA,可构建灵活的分布式信息集成平台.采用以服务单元形式封装的适配器连接各种异构系统,通过分布式标准消息路由器作为底层平台实现服务单元的注册、发现和通信.层次化体系和模块化设计有助于提高应用系统的敏捷性、互操作和集成能力.服务单元中采用事件驱动和动态线程池技术保障了系统的高效性.引入系统外部负载、线程开销和资源冲突,采用排队论模型对其性能进行评价.实例表明采用该方法构建的SynchroESB平台能够灵活集成企业遗留系统,提供高效可靠服务.