软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2011年第07期杂志 文档列表

软件学报杂志系统软件与软件工程

基于消息日志的Web服务接口业务协议挖掘1413-1425

摘要：Web服务接口的业务协议描述了Web服务的外部行为，对于Web服务的复用具有重要意义，可以作为服务发现、组合、验证和运行期可信保障等方面的重要基础．目前，已有一些工作研究了Web服务的协议发现问题，即从Web服务的调用消息日志中挖掘Web服务接口的业务协议．但已有方法主要关注服务的控制流约束，忽略了数据流约束以及数据流和控制流的相互约束．针对这一问题，研究了如何从Web服务的调用日志中自动挖掘Web服务接口，并侧重综合考虑Web服务的数据流和控制流．首先扩展了传统Petri网，提出了一种增加了数据流描述的Web服务接口模型－－BPN（business protocol net）模型．在此基础上，进一步提出了一种自动化的挖掘框架，可以从web服务调用消息记录中合成Web服务的BPN表示．最后，通过仿真实验验证了该方法的有效性．其结果表明，所提出的挖掘算法是正确而有效的．

基于全局QoS约束分解的Web服务动态选择1426-1439

摘要：随着执行时绑定的Web服务的提出及其被大量地应用到开放式服务中，用户对支持快速和动态的Web服务组合提出了新的要求．即在组合过程中，用尽可能短的时间花费选择满足用户端到端的QoS要求的服务．针对上述要求，提出了一种基于全局QoS约束分解的动态服务选择方法（Web service dynamic selection approach，简称WSDSA）．该方法的主要思想是，通过基于模糊逻辑的自适应调整方法（adaptive adjustment method，简称AAM）和自适应粒子群优化算法（adaptive particle swarm optimization，简称APSO）将全局QoS约束自适应地分解为满足用户偏好的局部约束，然后利用局部最优获得最合适的组合服务．性能评价表明，WSDSA方法具有较好的有效性，仅用较低的时间花费就能达到或接近全局最优解，能够满足服务选择的实时性和动态性．

异构集群系统中具有QoS需求的实时任务容错调度1440-1456

摘要：容错调度是调度问题中一个重要的研究内容，是提高系统可靠性的有效手段．目前已有很多集群系统中实时任务的容错调度算法，但是这些算法都没有考虑到任务的QoS需求问题．提出了一种异构集群系统中具有QoS需求的实时任务容错调度算法FTQ（fault-tolerant QoS-based scheduling）．该算法采用主版本／副版本（primary／backup，简称PB）技术，综合考虑了任务的时间限制、任务的QoS需求、系统的可靠性和系统资源的利用率，能够自适应地根据系统负载情况动态地调整任务的QoS级别和副版本的执行模式，从而提高了系统的灵活性、可靠性、可调度性和资源的利用率．对系统的可靠性进行了定量分析，并将其引入到容错调度算法中，提高了系统的可靠性．同时，在调度过程中尽量提前主版本的开始时间，推迟副版本的开始时间，以使任务的副版本采用被动执行模式或者使任务主版本和副版本的重叠部分尽量少，提高了资源的利用率．此外，采用了副版本重叠技术，并分析了副版本的最晚开始时间及其约束条件，提高了任务的调度成功率．通过大量的模拟实验，对FTQ，NOFTQ和DYFARS算法进行了比较．实验结果表明，FTQ算法的性能优于其他方法，具有更好的调度质量．

确定性有限状态机的最小测试成本迁移覆盖准则1457-1474

摘要：软件测试中的一个重要问题是测试成本和测试效率的平衡问题．依据程序中错误分布的2-8定律，将测试分为两个阶段，以解决该问题．第1阶段采用最小代价发现软件中的错误，第2阶段针对第l阶段中发现的错误补充设计测试用例，探测软件中潜在的错误．重点是第1阶段的实现，依据确定性有限状态机和集合划分的理论，提出了确定性有限状态机的最小测试成本迁移覆盖准则，给出了最小测试成本迁移覆盖存在的充分和必要条件，设计了优化迁移覆盖和最小测试成本迁移覆盖的实现算法，并讨论了测试序列集合的有效性问题．在实验中，依据该方法不仅能够获得最小测试成本的测试用例集合，而且同样能够探测出确定性有限状态机中迁移上的错误．

异构多处理器SoC的应用算法性能优化方法1475-1487

摘要：在嵌入式多媒体处理领域中，多处理器片上系统（multi-proces sorsystem-on-chip，简称MPSoC）的应用越来越广泛．多媒体处理MPSoC通常采用“主处理器核＋多个异构协处理器核”的主流体系结构．该结构兼顾了、MPSoC系统的通用性与灵活性、性能与功耗，但也向MPSoC的性能优化方法提出了更高的要求．针对异构MPSoC上的多媒体应用算法，提出了一种MPSoC多媒体处理性能优化方法．该方法经过应用特征分析、循环仿射划分、应用向MPSoC各处理器核的映射，实现了优化的数据局部性与多级并行性，从而提高了异构MPSoC上多媒体应用算法的性能．实验结果表明，该方法对于多媒体应用算法在异构MPSoC上的处理性能优化方面取得了明显效果．

基于事件的社会网络演化分析框架1488-1502

摘要：提出了一个全新的复杂网络分析框架来跟踪动态网络的演化规律，发现其在演化过程中的时间特性．不同于传统静态时间片的分析方法，整个框架首先利用有效而快速的方法发现网络的timeline，然后利用图近似算法刻画timeline中的平稳演化段落，这样可以有效地降低个体行为的不确定性所带来的网络演化噪声．此外，综合考虑到网络中个体的多维属性，还提出一种高效的社团发现算法，用以发现动态网络中的社团结构．为了对社团进行演化分析，提出了社团演化的评价方法，以发现社团演化过程的动态特征．最后，为了示例该框架的有效性和实用性，整个框架被应用于多个实际的网络数据集，并且揭示了这些网络在演化过程中的时间特性及社团演化模式．

软件学报杂志模式识别与人工智能

基于视听信息的自动年龄估计方法1503-1523

摘要：年龄是人的重要属性．近年来，自动估计用户年龄逐渐成为一个涉及模式识别、计算机视觉、语音识别、人机交互、机器学习等领域的活跃课题．其在现实世界中也有很多的实际应用，如法医学、电子商务、安全控制等等．日常生活中，人们往往可以很容易地根据视听信息（这里主要指人脸和语音）来判断一个人的年龄，原因在于人脸和语音是人的年龄信息的重要载体．同样的，人机交互系统可以根据人脸图像以及语音来自动进行年龄估计．主要介绍了基于视听信息进行年龄估计的应用领域所遇到的挑战以及现有的解决方案．详细介绍了基于视听信息的年龄估计所用到的主要模型、算法及其性能与特点，并且分析了自动年龄估计未来可能的发展趋势．

可判定的时序动态描述逻辑1524-1537

摘要：动态描述逻辑DDL（dynamic description logic）提供了一种基于描述逻辑的动作理论，适用于语义Web环境下对动态领域知识的刻画和推理．为了将分支时序逻辑的刻画能力引入到动态描述逻辑中，将时间的进展体现为原子动作的执行，从而将时序维与动态维统一起来．在此基础上，从描述逻辑ALCQIO出发构建了一个时序动态描述逻辑TDALCQIO,给出了TDALCQIO的Tableau判定算法，并证明了算法的可终止性和正确性．TDALCQIO不仅兼容了构建在描述逻辑ALCQIO基础上的动态描述逻辑的刻画和推理能力，而且还可从可达性、安全性等角度对整个动态领域的时序特征进行刻画和推理，从而为语义Web环境下对动态领域知识的刻画和推理提供了进一步的逻辑支持．

求解QBF问题的启发式调查传播算法1538-1550

摘要：提出了一种启发式调查传播算法，并基于该算法设计了一种QBF（quantified Boolean formulae）求解器－－HSPQBF（heuristic survey propagation algorithm for solvingQBF）系统．它将Survey Propagation信息传递方法应用到QBF求解问题中，利用Survey Propagation作为启发式引导DPLL（Davis，Putnam，Logemann and Loveland）算法，选择合适的变量进行分支，从而可以减小搜索空间，并减少算法回退的次数．在分支处理过程中，HSPQBF系统结合了单元传播、冲突学习和满足蕴涵学习等一些优秀的QBF求解技术，从而能够提高QBF问题的求解效率．实验结果表明，HSPQBF无论在随机问题上还是在QBF标准测试问题上都有很好的表现，验证了调查传播技术在QBF问题求解中的实际价值．

支撑向量数据域描述优化问题最优解理论分析1551-1560

摘要：支撑向量数据域描述（support vector data description，简称SVDD）作为一种已经得到广泛应用的核方法，目前研究主要集中在其性能和效率的提高上，然而该算法优化问题最优解性质的理论性质却没有得到足够的关注．为此，首先把SVDD定义的原始优化问题等价转化为一个凸约束二次优化问题，然后从理论上证明了其构建的超球圆心具有唯一性，然而超球半径在一定条件下却存在不唯一性，并且给出了半径存在不唯一性的充分必要条件．还从对偶优化问题的角度分析了超球的圆心和半径性质，并且给出了SVDD算法中在根据优化问题最优解构建超球半径不唯一情况下计算超球半径的方法．完善了该算法的理论和方法体系，从而为其更深入的研究和应用奠定了理论基础．

基于核化图嵌入的最佳鉴别分析与人脸识别1561-1570

摘要：将压缩映射和同构映射引入核化图嵌入框架（kernel extension of graph embedding，简称KGE），从理论上证明了KGE框架内的各种核算法其实质是KPCA（kernel principal component analysis）＋LGE（1inear extension of graphembedding，简称LGE）框架内的线性降维算法，并且基于所给出的理论框架提出了一种综合利用零空间和非零空间鉴别信息的组合方法．任何一种可以用核化图嵌入框架描述的核算法，都可以有相应的组合方法．在ORL，Yale，FERET和PIE人脸数据库上验证了所提出的理论和方法的有效性．

基于重构权的离群点检测方法1571-1579

摘要：近几年来，流形学习在模式识别、机器学习和数据挖掘等许多领域都受到了广泛的关注．但是，通常的流形学习方法对离群点缺乏鲁棒性对此，提出了一种基于重构权的流形离群点检测方法．该方法在每个样本点构造局部“强”邻域，再利用局部重构权来计算每个样本点的可靠值，最后利用可靠值检测出离群点．该算法具有计算快、参数少、参数敏感性小等优点．基于此离群点检测方法，提出了鲁棒的Isomap算法．实验结果表明，该方法能够有效检测离群点，从而提高流形学习方法对离群点的鲁棒性．国家自然科学基金（10901062）；福建省自然科学科学基金（2010J01336）；华侨大学基本科研业务专项基金

软件学报杂志计算机网络与信息安全

移动分布感知的车载自组网络数据分发1580-1596

摘要：提出了一种面向／订阅系统基于车辆移动分布感知的事件分发策略MDA（mobile distribution．awaredata dissemination）．基于车流的自组织性及自稳性的特点，建立VANET（vehicular ad hoc network）下的／订阅模型，通过计算车辆与移动订阅者的相遇概率，预测订阅者的移动分布，并以此为依据实时部署和调度广播令牌在网络中的转发，从而有效地控制事件的分布，保证了数据传递的有效性，与已有相关研究相比，MDA采用的启发式算法，能够使事件的分布更好地适应网络环境的动态变化．此外，MDA采用了一种基于概率预测密度的令牌控制算法，通过实时地调整令牌的数量，进而控制事件的数量，降低了整个网络的负载．模拟实验结果表明，与现有的几种消息分发算法相比，MDA能以较低的网络负载和传榆延迟获得较高的数据传输成功率．

移动传感器网络中定位算法的性能评测1597-1611

摘要：主要有3个方面的贡献：首先，发现在已有的移动传感器网络定位算法中所使用的仿真过程不能产生稳定的性能统计数据．讨论了这种现象的原因，并且提出一种定量的方法来设置仿真过程，以使得所设置的仿真过程能够产生稳定的性能统计数据．然后，测定和比较了几种典型的移动传感器网络定位算法在无障碍物部署和有障碍物部署的环境中的性能．发现在有障碍物部署的环境中，很多已有算法中提出的用以提高定位精度的技术是无效的；相反地，它们反而会降低算法的定位精度．最后，提出了几种节点可以借以评价自身位置估计的精度的度量．发现以前工作中提出的“最大可能定位误差”度量在指示单个节点的位置估计的精度时，其表现好于其他几种所提出的度量．

无线传感器网络中的定位模型1612-1625

摘要：位置信息在无线传感器网络应用中日益重要，针对该网络中的定位问题，提出一种新颖的基于模糊识别的定位模型．在该模型中，定位空间被一些样本点划分为若干个小区域，每个样本点唯一地对应一个信号向量，通过计算未知点信号向量与各个样本点对应向量的贴近度，可以最终确定未知点的坐标．该定位模型直接采用了射频信号对未知点进行定位，不但避免了一些range-based定位模型中出现的误差叠加等问题，而且还降低了计算复杂度．最后，借助NS-2仿真手段对该定位模型进行了验证．结果表明，该定位模型具有较高的性能，适合无线传感器网络应用．

时延受限且能量高效的无线传感网络跨层路由1626-1640

摘要：如何通过网络的多跳中继把传感器节点收集的信息快速、高效地传输至基站，是无线传感器网络的基本问题．研究发现，MAC（media access control）层的睡眠调度和无线信道的不规则性均会对路由协议的效率产生较大影响．虽然传统分层设计的网络协议有着模块化的优点，但各层之间的相互独立却导致网络的整体性能不能达到最优．此外，已有协议通常采用牺牲时延以提高能量效率的方法，会给时延敏感系统带来不能容忍的端到端时延．提出一种时延受限且能量高效的跨层路由协议（delay-constrained and energy-efficient cross-layer routing简称DECR），该协议在做出路由决定时考虑MAC层以及链路层的相关信息，其目标是在将端到端时延控制到低于预定上界的前提下最优化节点的能量效率．理论分析和实验结果表明，所提出的跨层路由协议具有较好的性能．

基于串空间的Ad Hoc安全路由协议攻击分析模型1641-1651

摘要：根据ad hoc安全路由协议的特点，分析串空间理论的优势和不足，并在串空间分析协议的基础上，设计出一种返回不存在路由的协议攻击分析模型,以扩展SRP协议为例，验证了模型的正确性．

模2＾n加和模2加混合运算的异或分支数1652-1660

摘要：研究了扩散结构为二元域上非线性变换的异或分支数．给出了扩散结构为二元域上非线性变换的异或分支数的定义及其与分组密码抗差分攻击和线性分析能力的关系，证明了以模2^n加和模2加的混合运算为扩散结构的异或分支数等于将模2^n加换成模2加且将各变元系数模2后所得的二元域上线性变换的异或分支数，从而简化了此类非线性扩散结构异或分支数的计算问题．