摘要:计算程序中循环的程序复杂度符号化上界可以验证程序的停机性.基于差分方程和最优化问题求解技术,给出了一种计算P^*-solvable 循环程序复杂度符号化上界的有效方法.分别针对含有赋值语句的循环和带条件分支的循环,提出了其程序复杂度符号化上界计算方法.与其他工作相比,该方法能够计算得到更精确的循环复杂度符号化上界,实验结果证明了该方法的有效性.

摘要:针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的自动化水平,而问题简约的思想也更有利于对算法本质特征的理解.

摘要:在分析现有改进算法的基础上,结合视知觉及认知心理学的相关理论,提出一种具备视觉反馈与行为记忆学习能力的新型蚁群算法:首先,建立视觉模型使得蚂蚁能够通过人工视觉感知周围目标城市的分布,用视知觉修正信息素噪声,提高蚂蚁探索质量;其次,建立行为记忆学习模型,使蚂蚁能够从已经走过的局部最优路径中提取经验来指导周游活动,加快算法收敛速度并强化寻优能力.经过与传统改进策略比较发现,新算法在求解质量与求解时间上均有明显改进.

摘要:首先分析研究Web 服务描述文档(WSDL 文档)的两大特征——结构特征和参引特征,然后根据各个特征对Web 服务功能语义描述的影响,提出相应的Web 服务表示模型——多向量表示模型.区别于通用文本表示模型,该模型能够显式地表示Web 服务描述文档的本质特征.其中,结构特征语义表现在多向量空间的划分上,参引特征语义映射到子向量模型中特征权重的计算上.提出了基于多向量模型的Web 服务相似度计算方法,并实现了基于该模型的Web 服务发现原型系统.最后,在真实Web 服务描述文档集合上构造了一个具有不完全相关

摘要:很多角色模型的设计和使用存在着一些限制,例如:角色对象的创建及其与源对象的绑定需要通过编码显式完成;角色对象与源对象之间的单向链接使得消息不能在它们之间互相转发等.这些限制使得角色模型的使用较为繁琐,在程序设计中往往会将系统的业务逻辑和对角色对象的控制逻辑混杂在一起.被称为DR 的动态角色模型除了相关工作的基本功能外还提供了角色对象的自动创建及其与源对象之间的双向链接,使得角色对象的使用变得透明.所有这些功能的实现都基于一种简洁、统一的前置对象机制,它不但能较好地处理复杂角色体系,还能与现有的面向对象系统

摘要:基于流和上下文敏感的SSA(static single assignment)信息流分析技术,提出了一种细粒度、可扩展的污点传播检测方法.利用控制流和数据流的相关信息,跟踪污染数据及其传播路径,可以检测缓冲区溢出、格式化串漏洞等程序脆弱性.分析过程在潜在问题点自动插装动态验证函数,在无需用户干预的情况下保证了程序的运行时安全.在GCC 编译器的基础上实现了分析系统,实验结果表明,该方法具有较高的精确度和时空效率.

摘要:基于多代理协作的IT 复杂应用管理模型,给出了用于IT 复杂应用管理的代理能力模型及管理任务分解问题的基本原则,进而提出了一种动态多角色的管理任务层级分解算法.算法考虑到多代理的能力限制,以及由管理端策略、IT 基础设施或业务逻辑改变而引起的IT 复杂应用管理任务的动态性.同时,算法兼顾了分解后子任务的平衡性,即执行子任务的多代理的负载平衡性,能够有效地提高多代理的执行效率和稳定性.仿真结果显示,由该算法所分解的子任务集呈现出了良好的执行效率及稳定的负载平衡性.

摘要:提出了一种增量式极端随机森林分类器(incremental extremely random forest,简称IERF),用于处理数据流,特别是小样本数据流的在线学习问题.IERF 算法中新到达的样本将被存储到相应的叶节点,并通过Gini 系数来确定是否对当前叶节点进行分裂扩展,在给定有限数量,甚至是少量样本的情况下,IERF 算法能够快速高效地完成分类器的增量构造.UCI 数据集的实验证明,提出的IERF 算法具有与离线批量学习的极端随机森林(extremely random forest,简称ERF

摘要:为使主题爬行能够充分利用资源的语义信息,提出基于语义的主题爬行策略.该策略利用领域本体刻画爬行主题,将本体语义映射到关键词表.通过定义断言集一致性扩展和域值关联推理任务,推演关键词间语义关系.在定义网页主题概念的基础上,结合本体推理方案提出主题概念的语义叠加效应模型.最后,利用主题概念的语义包含关系判定URLs 抓取顺序.实验结果表明,该语义主题爬行策略在抓取收获率和爬行效率上优于现有同类方法,该方案有效、可行.

摘要:研究了节点无移动能力的静态传感器网络中的栅栏覆盖问题.考虑在传感器节点具有有限移动能力时,如何构建k-栅栏覆盖的问题:首先定义了1-栅栏覆盖最小移动距离和问题(1-barrier coverage min-sum of movingdistance,简称1-BCMS).在网格划分模型情况下,将1-BCMS 问题近似为1-网格栅栏最小移动距离和问题(1-gridbarrier min-sum of moving distance,简称1-GBMS).给出了1-GBMS 问题的整数线性规划描述,

摘要:无结构P2P 网络拓扑随着规模的增大会出现一定的统计特性,充分应用该现象提出了一种多级局部覆盖网络(multi-level local overlay,简称ML²O)的无结构P2P 覆盖网,对ML²O 中节点间的连接进行恰当的数学控制后,就能使产生的拓扑具有从微观到宏观的多个粒度上的局部性.理论分析表明,ML²O 的网络直径和节点平均度都是网络规模n 的对数,为其上建立可扩展的无结构P2P 搜索奠定了基础.给出了应用ML

摘要:eMule 网络是近年来越来越流行的文件共享对等网络.一直以来,文件源的准确定位是文件共享对等网络的一个关键步骤;此外,不健康内容的肆意传播也使网络监管成为必需.这些都导致准确确定eMule 网络中节点的需求,同时促使eMule 网络最佳节点标识问题的提出.然而,eMule 网络中广泛使用的节点标识Kad ID 因可被eMule 用户任意更改,存在Kad ID 别名,即单个节点对应多个Kad ID 的情况,以及Kad ID 重复,即多个节点对应同一个Kad ID的情况,从而使用传统Kad ID 很难准确确

摘要:采用最小连通支配集的理论,研究异构无线传感器网络拓扑结构的优化问题.针对传感器节点的通信能力异构特性,综合通信链路质量、节点传输范围与剩余能量,构建起一种度量异构节点能量有效性的区域能量消耗率函数.利用该函数判断通信区域的能耗速率并确定支配节点的选择,设计了一种最小连通支配的分布式拓扑控制算法.实验结果表明,执行该算法构建起的网络拓扑具有通信链路可靠和能量利用高效的特点,能够大幅度提高异构无线传感器网络的生命周期.

摘要:无线传感器网络通常能量、带宽有限.一个关键而实用的需求是,在保证数据质量的情况下,对持续到达的采样数据进行在线式压缩.主要贡献:① 利用传感器节点内置的缓冲区,提出了单传感器节点上基于分段常量逼近的准在线式数据压缩算法(PCADC-sensor),并给出了在无穷范数误差度量下的实现;② 提出了单传感器节点上基于分段线性逼近的在线式数据压缩算法(PLADC-sensor).分别在无穷范数和2 范数误差度量的情况下给出了计算PLA 的两种简单快速算法,推导了分段线性一致逼近的充要条件;③ 簇头或基站无需接收原

摘要:在利用子网抽象技术的基础上,进一步针对带宽限制蠕虫高速扫描的特点,提出了一种基于Fluid 的大规模带宽限制蠕虫仿真模型.通过Fluid 仿真技术对蠕虫高速扫描产生的数据包进行抽象,降低其对仿真系统计算能力和存储能力的要求,进而提高仿真执行效率.仿真结果和数据包级仿真以及和实测数据的对比表明,该仿真模型可以在消耗较少资源的情况下具有较高的仿真保真度,能够满足带宽限制蠕虫传播特性分析和防御策略验证的需求.

摘要:提出一种能够在DDoS(distributed denial-of-service)攻击下保证现有正常网络流量的弹性随机公平蓝色(resilient stochastic fair blue,简称RSFB)算法.RSFB 算法根据数据流标记概率来识别良性数据流,并将识别出的良性数据流记录更新到一个良性数据流队列(benign flow queue,简称BFQ)中.算法再根据BFQ 中的良性数据流记录来保证良性数据流数据包的顺利传输.通过开展一系列实验,评估对比了RSFB 算法和几个著名主动队列管理(act

摘要:面向Web 应用,提出一种动态资源按需配置方法,能够根据不断变化的资源需求以在线方式高效地重配置集群,实时地确定集群当前节点运行数量及其上部署的虚拟机类型.该方法基于布尔二次指数平滑法预测用户请求,有效避免了配置结果落后于资源请求;基于遗传算法并行化搜索配置空间,快速发现合理配置.实验结果表明,该方法能够根据需求变化高效地在线调整系统资源配置,并可有效提高集群资源利用率,显著降低了系统能耗.

摘要:基于Lustre 文件系统,对并行文件系统的性能评估和性能建模进行了研究.通过对性能因子的调研,进行了一系列性能评估实验,并提出性能相关性模型(PRModel).在实验评估和PRModel 分析中发现,在不同的性能因子之间存在着紧密的性能相关性.为了挖掘并利用这种相关性信息,提出了一种相对性能预测模型(RPPModel)来预测不同性能因子条件下的性能.为了验证RPPModel 的有效性,设计了大量实验用例.结果表明,预测结果的平均相对误差能够控制在17%~28%的范围内,易于使用且具有较好的预测准确度.

摘要:以类OpenMP的并行程序为研究对象,在满足性能约束的条件下,结合异构系统并行循环调度和处理器动态电压调节技术优化系统功耗.首先建立了异构系统功耗感知的并行循环调度问题基本模型;然后,通过分析方法给出异构系统并行循环调度的能耗下界,该下界可用于评估功耗优化方法的实际效率;进而将异构系统并行循环调度问题归纳为整数规划问题,在此基础上,提出了处理器内循环再调度方法进一步降低功耗.最后,以CPU-GPU 异构系统为平台评测了10 个典型kernel 程序.实验结果表明,该方法可以有效降低系统功耗,提高系统效能.

摘要:基于前期工作的EOSS 算法,给出了扩展条件下的OpenMP 静态调度能量优化算法——改进的能量最优OpenMP 静态调度算法(improved energy-optimal static scheduling,简称IEOSS).该算法在原有EOSS 算法的基础上,建模了数据cache 失效造成的访存延迟对并行循环性能及能量的影响,选择最优调度块大小S^*,同时结合动态电压/频率调节,获得最小能量消耗.选择NPB3.2-OMP 的5 个程序进行模拟,以480 个处理器、6

摘要:针对事务存储系统机制下的容错问题,提出一种基于事务回退的事务存储系统的故障恢复方法.该方法利用事务存储系统自身的版本管理机制,避免了额外的检查点数据保存开销,从而实现了事务存储系统高效的故障恢复.通过对容错事务存储系统的隔离性证明了该方法的正确性.最后,使用包括4 个SPLASH-2 典型用例在内的5 个测试程序对该方法进行了性能测试.实验结果表明,与经典的Checkpointing 机制相比,该方法在避免了额外的检查点数据保存开销的同时,还具有较低的故障恢复开销.