摘要:上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.

摘要:为了缓解概率计算树逻辑模型检测中的状态空间爆炸问题,提出了概率计算树逻辑的限界模型检测技术.该技术首先定义概率计算树逻辑的限界语义,并证明其正确性;之后,通过实例说明在传统限界模型检测中,以路径长度作为判断检测过程终止的标准已经失效,基于数值计算中牛顿迭代法的终止准则,设计了新的终止判断标准;然后提出基于线性方程组求解的限界模型检测算法;最后,通过3 个测试用例说明,概率计算树逻辑限界模型检测方法在反例较短的情况下能够快速完成检测过程,而且比概率计算树逻辑的无界模型检测算法所需求得的状态空间要少.

摘要:部署是软件生命周期中的一个重要环节,是软件生产的后期活动,通过配置、安装和激活等活动来保障软件制品的后续运行.为了系统地了解软件部署的现状和最新进展,建立了一个多侧面、细粒度的分析框架——W⁴H,以对该领域的主要研究工作和系统工具进行概括分析.该框架从软件部署的概念和面对的问题空间出发,由5 个侧面、12 个维度构成,覆盖了软件部署方法中主体、客体、适用范围、方式策略和过程支持能力等多个方面.基于W⁴H 分析框架,对当前具有代表性的软件部署方法与技术进行分析和总结.案例研究结果表明,该分析框架能够对软件部署方法与技术进行较为全面的分析,对软件系统部署方法和技术的选择及开发具有重要的指导意义.

摘要:随机测试是实践中广泛采用的一种黑盒测试方法.近年来提出的适应性随机测试方法改进了随机测试的不足,仿真实验结果表明,改进效果取决于软件失效域的特征.提出以测试约束刻画软件失效域在输入域上的分布,探讨了基于现有的程序分析技术构造测试约束的过程,讨论了基于测试约束的软件失效域的特征分析方法.以一个实例软件验证所提出的测试约束构造过程及其软件失效域特征分析方法.测试约束揭示了软件故障的触发与传播的内在机制,基于测试约束的软件失效域的特征分析方法有助于改进测试用例的设计质量以及评价适应性随机测试方法的适用性.

摘要:在工作流管理系统中,个人工作列表的优化调度具有重要意义.已有的相关研究主要关注工作流实例的调度,而关于个人工作列表调度的研究还较少.首先描述了工作流实例动态执行环境下个人工作列表调度问题,并提出了一个基于遗传算法的个人工作列表资源调度算法.该算法要为每一个执行人推荐一个可行工作列表,并在保证工作项联合执行成功率的同时最小化总体延误代价.最后,通过一个仿真实验将该遗传算法与其他7 种基于分配规则的典型调度算法进行了比较.结果表明,所提出的基于遗传算法的个人工作列表资源调度算法比已有的其他典型调度算法具有更好的调度效果.

摘要:如今,越来越多的处理器集成了SIMD(single instruction multiple data)扩展,现有的编译器大多也实现了自动向量化的功能,但是一般都只针对最内层循环进行向量化,对于多重循环缺少一种通用、易行的向量化方法.为此,提出了一种面向SLP(superword level parallelism)的多重循环向量化方法,从外至内依次对各个循环层次进行分析,收集各层循环对应的一些影响向量化效果的属性值,主要包括能否对该循环进行直接循环展开和压紧、有多少数组引用相对于该循环索引连续以及该循环所包含的区域等,然后根据这些属性值决定在哪些循环层次进行直接循环展开和压紧,最后通过SLP 对循环中的语句进行向量化.实验结果表明,该算法相对于内层循环向量化和简单的外层循环向量化平均加速比提升了2.13 和1.41,对于一些常用的核心循环可以得到高达5.3 的加速比.

摘要:随着语义Web 的快速发展,语义Web 数据大幅增长.在语义Web 中,单个对象很可能由多个不同的标识符(例如URI)指称.语义Web 中,对象共指的消解是识别语义Web 中指称相同对象的不同标识符,并消除描述这些标识符的RDF(resource description framework)数据之间不一致性的过程,它对于语义Web 数据的融合、搜索、浏览等具有重要作用.首先,形式化定义了语义Web 中对象共指的消解问题;然后,从对象共指识别使用的特征、数据冲突的消解方式、对象共指消解方法的适用范围、现有原型系统和基准测试集这5 个方面调研了最新的研究进展;最后,讨论了尚存的挑战,并展望未来可能的研究发展方向.

摘要:粗糙集是1982 年由Pawlak 教授提出的解决集合边界不确定的重要方法,它通过两个精确的上、下近似集作为边界线来刻画目标集合(概念)X 的不确定性,但它没有给出如何用已知的知识基(知识粒)来精确或近似地描述边界不确定的目标集合(概念)X 的方法.首先给出了集合之间的相似度概念,然后分析了分别用上近似集R(X)和下近似集R(X)作为目标集合(概念)X 近似描述的不足,提出了在已有知识基(粒)空间下寻找目标集合(概念)X 的近似集的方法,并分析了用R_0.5(X)作为X(概念)的近似集的优越性.最后讨论了不同知识粒度空间下R_0.5(X)与X 的相似度随知识粒度的变化关系.从新的角度提出了目标集合(概念)X 近似集的构造方法,促进了粗糙集模型的发展.

摘要:提出了一种种群规模自适应动态控制策略,实现了种群规模根据进化过程自适应的动态变化.该策略的实现不依赖于算法进化操作的具体步骤,因而适用于各种基于种群优化的自然计算方法.首先给出了动态控制策略的框架;然后,在此框架下,充分利用动态种群规模反馈的有用信息,提出了基于Logistic 模型的增加/删除数目自适应变化的方法,设计了自适应地兼顾有效性和多样性的增加算子和基于多样性的删除算子.将该策略应用到两种不同的自然计算方法中,采用经典测试函数和新型CEC05 测试函数验证其性能.实验结果均表明,结合了所提出的种群规模自适应动态控制策略的新算法,比原算法在求解精度和收敛速度上均有明显的提升.

摘要:针对约束多目标优化问题,提出修正免疫克隆约束多目标优化算法.该算法通过引进一个约束处理策略,用一个修正算法对个体的目标函数值进行修正,并对修正后的目标函数值采用免疫克隆算法进行优化,用一个精英种群对可行非支配解进行存储.该算法在优化过程中,既保留了非支配可行解,也充分利用了约束偏离值小的非可行解,同时引进整体克隆策略来提高解分布的多样性.通过对约束多目标问题的各项性能指标的测试以及和对比算法的比较可以看出:该算法在处理约束多目标优化测试问题时,所得解的多样性得到了一定的提高.同时,解的收敛性和均匀性也得到了一定的改进.

摘要:基于视觉词的统计建模和判别学习,提出一种视觉词软直方图的图像表示方法.假设属于同一视觉词的图像局部特征服从高斯混合分布,利用最大-最小后验伪概率判别学习方法从样本中估计该分布,计算局部特征与视觉词的相似度.累加图像中每个视觉词与对应局部特征的相似度,在全部视觉词集合上进行结果的归一化,得到图像的视觉词软直方图.讨论了两种具体实现方法:一种是基于分类的软直方图方法,该方法根据相似度最大原则建立局部特征与视觉词的对应关系;另一种是完全软直方图方法,该方法将每个局部特征匹配到所有视觉词.在数据库Caltech-4和PASCAL VOC 2006上的实验结果表明,该方法是有效的.

摘要:联盟规范系统(coalitional normative system,简称CNS)通过选择性地限制联盟的联合行动来对规范系统(normative system,简称NS)进行扩展.扩展了ATL 的语义,提出了Coordinate-ATL(Co-ATL),用于对CNS 进行形式化.为了刻画其规范能力的极限,确定了Co-ATL 的两个语言片段,分别对应于两类不可改变的系统属性.对NS 和CNS之间的关系进行了讨论,表明所得到的结果可以更好地界定NS 的能力极限.此外,引入了对执行历史进行编码的有限状态机,进一步对CNS 进行了扩展,提出了CNS-M.可以证明,关于CNS 能力极限的界定在该扩展下保持稳定.

摘要:为了改善粒子群算法易早熟收敛、精度低等缺点,提出一种多尺度协同变异的粒子群优化算法,并证明了该算法以概率1 收敛到全局最优解.算法采用多尺度高斯变异机制实现局部解逃逸.在算法初期阶段,利用大尺度变异及均匀变异算子实现全局最优解空间的快速定位;随着适应值的提升,变异尺度随之降低;最终在算法后期阶段,利用小尺度变异算子完成局部精确解空间的搜索.将算法应用6 个典型复杂函数优化问题,并同其他带变异操作的PSO 算法比较,结果表明,该算法在收敛速度及稳定性上有显著提高.

摘要:约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR 改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.

摘要:由于认知无线网络(cognitive radio network,简称CRN)固有“二次利用”的特性,使其日益得到重视.而作为CRN 核心构成的MAC(medium access control)协议,业已成为当前各研究机构的一个热点.主要对频谱感测技术、信道接入技术等MAC 层核心设计问题进行了探讨,并针对认知无线网络MAC 的特性及需求进行了分析,然后对设计MAC 频谱感知技术、信道接入技术、频谱共享技术等相关研究进展进行了归类总结.最后指出了当前面临的主要研究难点及挑战,并提出了一些方向性建议.

摘要:提出了一种无线mesh 网络中基于主动路由的区域移动管理(active routing based intra-domain mobilitymanagement,简称ARMM)方法,将移动终端(mobile station,简称MS)的位置更新和mesh 路由器(mesh route,简称MR)之间的动态路由相结合,让MR 代替附着在它上面的MS 进行位置管理,从而实现MR 对MS 的定位.给出了ARMM方法中的二层路由模型、路由算法及位置更新机制.性能分析结果表明,相对于现有的区域移动管理方法, ARMM方法具有较小的切换延时、位置更新开销和数据传输开销.

摘要:在很多P2P 应用中,节点可以根据其兴趣或资源划分为不同的类型,而以特定类型节点为目标的基于覆盖网的路由也就成为实现数据分发及查询的关键.非结构化覆盖网具有维护开销低、鲁棒性高的优点,却也因此难以保证路由效率.提出了一种基于gossip 的类型采样方法——TypeSampler,它以等概率采样不同类型的节点(称为类型采样),以此保证在任意节点发现特定类型邻居节点的概率下界,进而保证非结构化覆盖网中的路由效率.为了实现类型采样,TypeSampler 首先通过基于gossip 的节点采样及反熵聚集估计各类型节点的比例,然后,TypeSampler 再根据这些比例估计值周期性地维护每个节点的类型采样表.理论分析与实验结果表明,TypeSampler 能够实现精确的类型比例估计以及近似均匀随机的类型采样,并能适应动态的网络环境.而且相对于已有的方法,TypeSampler 能够支持更高效的路由,且具有更好的可扩展性.

摘要:为了解决现有JPEG 隐写分析方法特征冗余度高和未能充分利用特征间互补关系的问题,提出了一种基于主成分分析(principal component analysis,简称PCA)进行特征融合的JPEG 隐写分析方法,并分析所选特征之间的互补性.通过融合将互补特征结合在一起,更全面地反映载体和隐写信号间的统计差异,并用PCA 分离出冗余成分,最终达到进一步提升准确率的目的.实验结果表明,在不同数据集和嵌入率情况下,该方法分析高隐蔽性隐写(如F5,MME 和PQ)的准确率高于主要JPEG 分析方法,在耗时上较现有特征层融合降维方法大为缩短.

摘要:评估信息系统安全措施效用是改进系统信息安全绩效的一条重要途径.传统方法在评估安全措施效用时并没有考虑业务数据流、攻击流和安全措施要素之间的相互作用和影响,无法保证评估过程和结果的有效性.提出了一种给定脆弱性环境下的信息系统安全措施效用评估方法,应用颜色Petri 网为系统业务数据流、攻击流和安全措施要素进行统一建模.通过设计节点间脆弱性利用图生成算法和改进的Dijkstra 算法识别所有可能破坏信息系统安全属性的最短攻击路径,使用层次评价模型评估系统安全措施的效用.给出了一种基于多属性决策的系统最优信息安全效用提升方案选择算法.改善评估过程对人员主观经验的依赖问题,有助于保证评估结果的一致性和可追溯性.以一个具体的Web 业务系统为例进行实验,验证了所提出的模型和方法的正确性和有效性.

摘要:BOMM(byte-oriented memorial mixer)算法是一种基于字节操作的混合型带记忆的序列扰乱算法,因具备良好的密码学性质,一个新的流密码算法Loiss 使用了它作为主要组件.建立了BOMM 算法的5 次代数方程系统,在此基础上讨论了针对Loiss 算法的代数攻击的复杂度.此外还发现了BOMM算法的一个统计弱点,并分析了Loiss算法在一类弱密钥下的安全性.

摘要:提出了一种基于线索平衡二叉排序哈希树认证委分字典的安全高效的源认证(origin authentication,简称OA)方案,用于防范BGP 地址前缀劫持攻击.基于Aiello 和McDaniel 等人提出的OA 服务,通过数值区间对AS 号和IP 地址前缀这两种BGP 前缀宣告资源进行了统一的形式化定义,采用一种方案同时解决了两种前缀宣告资源的源可信问题.该方案不仅解决了原OA 服务中存在的“无效分配关系的证据量是有效分配关系证据量的两倍”的问题,而且与原OA 服务相比,该方案建树所需要的总节点数降低约一半.同时,委分证据集合的平均长度更小.因此,该源认证方案效率更高.

摘要:利用多路径传输协议,多宿主主机可以通过多条路径并行传输数据,从而有效提高系统的吞吐率和鲁棒性.但是由于不同路径在带宽、延迟和丢包率等方面存在差异,接收端必须缓存大量乱序到达的分组.数学分析表明,减少接收端的缓存开销有两条途径:一是最小化每条路径的发送队列中积压分组的数量,二是降低分组发送速率.由前者,提出依据每条路径的空闲发送窗口大小进行分组调度的算法SOD(Scheduling On Demand);由后者,提出利用窗口通告机制限制分组发送速率的流控方法.模拟实验结果表明:与现有算法相比,SOD 的缓存开销最小;在接收端进行流控限制的情况下,SOD 的吞吐率最大,并且在不同实验场景中性能表现稳定.