2011, 22(7):1413-1425. DOI: 10.3724/SP.J.1001.2011.03820
摘要:Web 服务接口的业务协议描述了Web 服务的外部行为,对于Web 服务的复用具有重要意义,可以作为发现、组合、验证和运行期可信保障等方面的重要基础.目前,已有一些工作研究了Web 服务的协议发现问题,即从Web 服务的调用消息日志中挖掘Web 服务接口的业务协议.但已有方法主要关注服务的控制流约束,忽略了流约束以及数据流和控制流的相互约束.针对这一问题,研究了如何从Web 服务的调用日志中自动挖掘Web 服口,并侧重综合考虑Web 服务的数据流和控制流.首先扩展了传统Petri 网,提出了一种增加了数据流描述的Web 服务接口模型——BPN(business protocol net)模型.在此基础上,进一步提出了一种自动化的挖掘框架,可以从Web 服务调用消息记录中合成Web 服务的BPN 表示.最后,通过仿真实验验证了该方法的有效性.其结果表明,所提出掘算法是正确而有效的.
2011, 22(7):1426-1439. DOI: 10.3724/SP.J.1001.2011.03842
摘要:随着执行时绑定的Web 服务的提出及其被大量地应用到开放式服务中,用户对支持快速和动态的Web 服务组合提出了新的要求.即在组合过程中,用尽可能短的时间花费选择满足用户端到端的QoS 要求的服务.针对要求,提出了一种基于全局QoS 约束分解的动态服务选择方法(Web service dynamic selection approach,简称WSDSA).该方法的主要思想是,通过基于模糊逻辑的自适应调整方法(adaptive adjustment method,简称AAM)和应粒子群优化算法(adaptive particle swarm optimization,简称APSO)将全局QoS 约束自适应地分解为满足用户的局部约束,然后利用局部最优获得最合适的组合服务.性能评价表明,WSDSA 方法具有较好的有效性,仅用较时间花费就能达到或接近全局最优解,能够满足服务选择的实时性和动态性.
2011, 22(7):1440-1456. DOI: 10.3724/SP.J.1001.2011.03833
摘要:容错调度是调度问题中一个重要的研究内容,是提高系统可靠性的有效手段.目前已有很多集群系统时任务的容错调度算法,但是这些算法都没有考虑到任务的QoS 需求问题.提出了一种异构集群系统中具有QoS 需求的实时任务容错调度算法FTQ(fault-tolerant QoS-based scheduling).该算法采用主版本/副版本(primary/backup, 简称PB)技术,综合考虑了任务的时间限制、任务的QoS 需求、系统的可靠性和系统资源的利用率,能够自适应地根据系统负载情况动态地调整任务的QoS 级别和副版本的执行模式,从而提高了系统的灵活性、可靠性、可调和资源的利用率.对系统的可靠性进行了定量分析,并将其引入到容错调度算法中,提高了系统的可靠性.同时,度过程中尽量提前主版本的开始时间,推迟副版本的开始时间,以使任务的副版本采用被动执行模式或者使任版本和副版本的重叠部分尽量少,提高了资源的利用率.此外,采用了副版本重叠技术,并分析了副版本的最晚时间及其约束条件,提高了任务的调度成功率.通过大量的模拟实验,对FTQ,NOFTQ 和DYFARS 算法进行了.实验结果表明,FTQ 算法的性能优于其他方法,具有更好的调度质量.
2011, 22(7):1457-1474. DOI: 10.3724/SP.J.1001.2011.03872
摘要:软件测试中的一个重要问题是测试成本和测试效率的平衡问题.依据程序中错误分布的2-8 定律,将测为两个阶段,以解决该问题.第1 阶段采用最小代价发现软件中的错误,第2 阶段针对第1 阶段中发现的错误补计测试用例,探测软件中潜在的错误.重点是第1 阶段的实现.依据确定性有限状态机和集合划分的理论,提出了性有限状态机的最小测试成本迁移覆盖准则,给出了最小测试成本迁移覆盖存在的充分和必要条件,设计了优移覆盖和最小测试成本迁移覆盖的实现算法,并讨论了测试序列集合的有效性问题.在实验中,依据该方法不仅获得最小测试成本的测试用例集合,而且同样能够探测出确定性有限状态机中迁移上的错误.
2011, 22(7):1475-1487. DOI: 10.3724/SP.J.1001.2011.03847
摘要:在嵌入式多媒体处理领域中,多处理器片上系统(multi-processor system-on-chip,简称MPSoC)的应用越广泛.多媒体处理MPSoC 通常采用“主处理器核+多个异构协处理器核”的主流体系结构.该结构兼顾了MPSoC 系统的通用性与灵活性、性能与功耗,但也向MPSoC 的性能优化方法提出了更高的要求.针对异构MPSoC 上的体应用算法,提出了一种MPSoC 多媒体处理性能优化方法.该方法经过应用特征分析、循环仿射划分、应用向MPSoC 各处理器核的映射,实现了优化的数据局部性与多级并行性,从而提高了异构MPSoC 上多媒体应用算法能.实验结果表明,该方法对于多媒体应用算法在异构MPSoC 上的处理性能优化方面取得了明显效果.
2011, 22(7):1488-1502. DOI: 10.3724/SP.J.1001.2011.03841
摘要:提出了一个全新的复杂网络分析框架来跟踪动态网络的演化规律,发现其在演化过程中的时间特性.于传统静态时间片的分析方法,整个框架首先利用有效而快速的方法发现网络的timeline,然后利用图近似算画timeline 中的平稳演化段落,这样可以有效地降低个体行为的不确定性所带来的网络演化噪声.此外,综合考网络中个体的多维属性,还提出一种高效的社团发现算法,用以发现动态网络中的社团结构.为了对社团进行演析,提出了社团演化的评价方法,以发现社团演化过程的动态特征.最后,为了示例该框架的有效性和实用性,整架被应用于多个实际的网络数据集,并且揭示了这些网络在演化过程中的时间特性及社团演化模式.
2011, 22(7):1503-1523. DOI: 10.3724/SP.J.1001.2011.04012
摘要:年龄是人的重要属性.近年来,自动估计用户年龄逐渐成为一个涉及模式识别、计算机视觉、语音识别、人机交互、机器学习等领域的活跃课题.其在现实世界中也有很多的实际应用,如法医学、电子商务、安全控制.日常生活中,人们往往可以很容易地根据视听信息(这里主要指人脸和语音)来判断一个人的年龄,原因在于人语音是人的年龄信息的重要载体.同样的,人机交互系统可以根据人脸图像以及语音来自动进行年龄估计.主要了基于视听信息进行年龄估计的应用领域所遇到的挑战以及现有的解决方案.详细介绍了基于视听信息的年计所用到的主要模型、算法及其性能与特点,并且分析了自动年龄估计未来可能的发展趋势.
2011, 22(7):1524-1537. DOI: 10.3724/SP.J.1001.2011.03869
摘要:动态描述逻辑DDL(dynamic description logic)提供了一种基于描述逻辑的动作理论,适用于语义Web 下对动态领域知识的刻画和推理.为了将分支时序逻辑的刻画能力引入到动态描述逻辑中,将时间的进展体现子动作的执行,从而将时序维与动态维统一起来.在此基础上,从描述逻辑ALCQIO出发构建了一个时序动态描辑TDALCQIO,给出了TDALCQIO 的Tableau 判定算法,并证明了算法的可终止性和正确性.TDALCQIO 不仅兼容了构描述逻辑ALCQIO 基础上的动态描述逻辑的刻画和推理能力,而且还可从可达性、安全性等角度对整个动态的时序特征进行刻画和推理,从而为语义Web 环境下对动态领域知识的刻画和推理提供了进一步的逻辑支持.
2011, 22(7):1538-1550. DOI: 10.3724/SP.J.1001.2011.03859
摘要:提出了一种启发式调查传播算法,并基于该算法设计了一种QBF(quantified Boolean formulae)求解器——HSPQBF(heuristic survey propagation algorithm for solving QBF)系统.它将Survey Propagation 信息传递方法应QBF 求解问题中.利用Survey Propagation 作为启发式引导DPLL(Davis,Putnam,Logemann and Loveland)算法,合适的变量进行分支,从而可以减小搜索空间,并减少算法回退的次数.在分支处理过程中,HSPQBF 系统结合元传播、冲突学习和满足蕴涵学习等一些优秀的QBF 求解技术,从而能够提高QBF 问题的求解效率.实验结明,HSPQBF 无论在随机问题上还是在QBF 标准测试问题上都有很好的表现,验证了调查传播技术在QBF 问解中的实际价值.
2011, 22(7):1551-1560. DOI: 10.3724/SP.J.1001.2011.03856
摘要:支撑向量数据域描述(support vector data description,简称SVDD)作为一种已经得到广泛应用的核方法,研究主要集中在其性能和效率的提高上,然而该算法优化问题最优解性质的理论性质却没有得到足够的关注.,首先把SVDD 定义的原始优化问题等价转化为一个凸约束二次优化问题,然后从理论上证明了其构建的超球具有唯一性,然而超球半径在一定条件下却存在不唯一性,并且给出了半径存在不唯一性的充分必要条件.还从优化问题的角度分析了超球的圆心和半径性质,并且给出了SVDD 算法中在根据优化问题最优解构建超球半唯一情况下计算超球半径的方法.完善了该算法的理论和方法体系,从而为其更深入的研究和应用奠定了理础.
2011, 22(7):1561-1570. DOI: 10.3724/SP.J.1001.2011.03843
摘要:将压缩映射和同构映射引入核化图嵌入框架(kernel extension of graph embedding,简称KGE),从理论上了KGE 框架内的各种核算法其实质是KPCA(kernel principal component analysis)+LGE(linear extension of graph embedding,简称LGE)框架内的线性降维算法,并且基于所给出的理论框架提出了一种综合利用零空间和非零空别信息的组合方法.任何一种可以用核化图嵌入框架描述的核算法,都可以有相应的组合方法.在ORL,Yale,FERET 和PIE 人脸数据库上验证了所提出的理论和方法的有效性.
2011, 22(7):1571-1579. DOI: 10.3724/SP.J.1001.2011.03839
摘要:近几年来,流形学习在模式识别、机器学习和数据挖掘等许多领域都受到了广泛的关注.但是,通常的流习方法对离群点缺乏鲁棒性.对此,提出了一种基于重构权的流形离群点检测方法.该方法在每个样本点构造局部“强”邻域,再利用局部重构权来计算每个样本点的可靠值,最后利用可靠值检测出离群点.该算法具有计算快、参、参数敏感性小等优点.基于此离群点检测方法,提出了鲁棒的Isomap 算法.实验结果表明,该方法能够有效检群点,从而提高流形学习方法对离群点的鲁棒性.
2011, 22(7):1580-1596. DOI: 10.3724/SP.J.1001.2011.03871
摘要:提出了一种面向发布/订阅系统基于车辆移动分布感知的事件分发策略MDA(mobile distribution-aware data dissemination).基于车流的自组织性及自稳性的特点,建立VANET(vehicular ad hoc network)下的发布/订阅,通过计算车辆与移动订阅者的相遇概率,预测订阅者的移动分布,并以此为依据实时部署和调度广播令牌在网的转发,从而有效地控制事件代理的分布,保证了数据传递的有效性.与已有相关研究相比,MDA 采用的启发式,能够使事件代理的分布更好地适应网络环境的动态变化.此外,MDA 采用了一种基于概率预测密度的令牌控法,通过实时地调整令牌的数量,进而控制事件代理的数量,降低了整个网络的负载.模拟实验结果表明,与现有种消息分发算法相比,MDA 能以较低的网络负载和传输延迟获得较高的数据传输成功率.
2011, 22(7):1597-1611. DOI: 10.3724/SP.J.1001.2011.03864
摘要:主要有3 个方面的贡献:首先,发现在已有的移动传感器网络定位算法中所使用的仿真过程不能产生稳性能统计数据.讨论了这种现象的原因,并且提出一种定量的方法来设置仿真过程,以使得所设置的仿真过程能生稳定的性能统计数据.然后,测定和比较了几种典型的移动传感器网络定位算法在无障碍物部署和有障碍物的环境中的性能.发现在有障碍物部署的环境中,很多已有算法中提出的用以提高定位精度的技术是无效的;相,它们反而会降低算法的定位精度.最后,提出了几种节点可以借以评价自身位置估计的精度的度量.发现以前中提出的“最大可能定位误差”度量在指示单个节点的位置估计的精度时,其表现好于其他几种所提出的度量.
2011, 22(7):1612-1625. DOI: 10.3724/SP.J.1001.2011.03836
摘要:位置信息在无线传感器网络应用中日益重要,针对该网络中的定位问题,提出一种新颖的基于模糊识定位模型.在该模型中,定位空间被一些样本点划分为若干个小区域,每个样本点唯一地对应一个信号向量,通算未知点信号向量与各个样本点对应向量的贴近度,可以最终确定未知点的坐标.该定位模型直接采用了射频对未知点进行定位,不但避免了一些range-based 定位模型中出现的误差叠加等问题,而且还降低了计算复杂度. 最后,借助NS-2 仿真手段对该定位模型进行了验证.结果表明,该定位模型具有较高的性能,适合无线传感器网用.
2011, 22(7):1626-1640. DOI: 10.3724/SP.J.1001.2011.03838
摘要:如何通过网络的多跳中继把传感器节点收集的信息快速、高效地传输至基站,是无线传感器网络的基题.研究发现,MAC(media access control)层的睡眠调度和无线信道的不规则性均会对路由协议的效率产生较大.虽然传统分层设计的网络协议有着模块化的优点,但各层之间的相互独立却导致网络的整体性能不能达到最优.此外,已有协议通常采用牺牲时延以提高能量效率的方法,会给时延敏感系统带来不能容忍的端到端时延.提出一延受限且能量高效的跨层路由协议(delay-constrained and energy-efficient cross-layer routing,简称DECR),该协做出路由决定时考虑MAC层以及链路层的相关信息,其目标是在将端到端时延控制到低于预定上界的前提下化节点的能量效率.理论分析和实验结果表明,所提出的跨层路由协议具有较好的性能.
2011, 22(7):1641-1651. DOI: 10.3724/SP.J.1001.2011.03866
摘要:根据ad hoc 安全路由协议的特点,分析串空间理论的优势和不足,并在串空间分析协议的基础上,设计种返回不存在路由的协议攻击分析模型.以扩展SRP 协议为例,验证了模型的正确性.
2011, 22(7):1652-1660. DOI: 10.3724/SP.J.1001.2011.03837
摘要:研究了扩散结构为二元域上非线性变换的异或分支数.给出了扩散结构为二元域上非线性变换的异或数的定义及其与分组密码抗差分攻击和线性分析能力的关系,证明了以模2n 加和模2 加的混合运算为扩散结异或分支数等于将模2n 加换成模2 加且将各变元系数模2后所得的二元域上线性变换的异或分支数,从而简此类非线性扩散结构异或分支数的计算问题.
2011, 22(7):1661-1675. DOI: 10.3724/SP.J.1001.2011.03870
摘要:传统的基于实体标识的授权模型会导致由于授权路径的不一致而引起权限传播的不一致,并可能导致法的实体进入授权路径获得不应有的权限.针对以上两方面的问题,提出一个基于属性的授权委托模型ABADM (attribute-based authorization delegation model),将授权模型中权限的传递与权力的委托均建立在实体所具有的属合的基础之上,以属性集合作为实体自身的代表进行授权,从而确保拥有相同属性凭证链的实体其权限是一致的.模型将属性与访问权限进行明确区分,提出了域内属性权限分配策略和域间属性计算模型,通过两者的结合给出ABADM 模型中计算实体所拥有的跨域属性集合和访问权限的方法,并结合具体实例对模型的使用进行了说明.
2011, 22(7):1676-1689. DOI: 10.3724/SP.J.1001.2011.03858
摘要:网络协议逆向分析是恶意软件分析的一项重要内容.现有的网络协议逆向分析方法主要考虑获取消息和协议语法,缺少数据的行为语义,导致分析者难以在网络数据和恶意软件行为之间建立起对应关系.提出一种协议的语法规范和字段行为语义分析方法,该方法利用基于虚拟执行环境的动态程序分析技术,通过分析恶意对网络数据的解析过程提取协议语法信息,并根据恶意软件对协议字段的使用方式获取字段的程序行为语义.结合API 拦截和指令执行监控,该方法降低了分析复杂度,提高了分析效率.在所设计和实现的原型系统Prama(protocol reverse analyzer for malware analysis)上的实验结果表明,该方法能够较为准确地识别字段,提取协法规范,并能在命令字段与其引起的程序行为之间建立起有效的对应关系.
2011, 22(7):1690-1698. DOI: 10.3724/SP.J.1001.2011.03825
摘要:无证书混合签密能够处理无证书体制下任意长度的消息,而普通的无证书签密则不能处理.指出Selvi 提出的攻击是不成立的,并构造了一个新的无证书混合签密方案.与现有方案相比,该方案具有密文长度短、计度快的优点,因此更适用于带宽窄、计算资源少的通信环境,如ad hoc 网络.在随机预言模型和双线性Diffie-Hellman 困难性假设条件下,该方案可证明是安全的.