• 2012年第23卷第3期文章目次
    全 选
    显示方式: |
    • 利用派生谓词和偏好处理OSP 问题的目标效益依赖

      2012, 23(3):439-450. DOI: 10.3724/SP.J.1001.2012.03985

      摘要 (4207) HTML (0) PDF 638.05 K (4010) 评论 (0) 收藏

      摘要:在过度规划问题(over-subscribed planning,简称OSP)研究中,如果目标之间不是相互独立的,那么目标间的效益依赖比单个目标效益更能提高规划解的质量.但是已有的描述模型不符合标准规划描述语言(planning domain description language,简称PDDL)的语法规范,不能在一般的OSP 规划系统上进行推广.提出了用派生谓词规则和目标偏好描述效益依赖的方法,这二者均为PDDL 语言的基本要素.实质上,将已有的GAI 模型转换为派生谓词规则和目标偏好,其中派生谓词规则显式描述目标子集的存在条件,偏好机制用来表示目标子集的效益,二者缺一不可.该转换算法既可以保持在描述依赖关系时GAI 模型的易用性和直观性上,又可以扩展一般的OSP 规划系统处理目标效益依赖的能力.从理论上可以证明该算法在转换过程中的语义不变性,在基准领域的实验结果表明其可行性和对规划解质量的改善能力.提出符合PDDL 语言规范的目标效益依赖关系的描述形式,克服了已有模型不通用的缺点.

    • 复杂网络簇结构探测——基于随机游走的蚁群算法

      2012, 23(3):451-464. DOI: 10.3724/SP.J.1001.2012.03996

      摘要 (5049) HTML (0) PDF 823.79 K (9428) 评论 (0) 收藏

      摘要:网络簇结构是复杂网络最普遍和最重要的拓扑属性之一,网络聚类问题就是要找出给定网络中的所有类簇.有很多实际应用问题可被建模成网络聚类问题.尽管目前已有许多网络聚类方法被提出,但如何进一步提高聚类精度,特别是在没有先验知识(如网络簇个数)的情况下如何发现合理的网络簇结构,仍是一个未能很好解决的难题. 针对该问题,在马尔可夫随机游走思想的启发下,从仿生角度出发提出一种全新的网络聚类算法——基于随机游走的蚁群算法RWACO.该算法将蚁群算法的框架作为RWACO 的基本框架,对于每一代,以马尔可夫随机游走模型作为启发式规则;基于集成学习思想,将蚂蚁的局部解融合为全局解,并用其更新信息素矩阵.通过“强化簇内连接,弱化簇间连接”这一进化策略,使网络簇结构逐渐地呈现出来.实验结果表明,对一些典型的计算机生成网络和真实网络, 该算法能够较准确地探测出网络的真实类簇数,与一些有代表性的算法相比,具有较高的聚类精度.

    • 不完备模型下的离散事件系统诊断方法

      2012, 23(3):465-475. DOI: 10.3724/SP.J.1001.2012.04028

      摘要 (3919) HTML (0) PDF 630.63 K (3618) 评论 (0) 收藏

      摘要:提出不完备模型的两种不完备性:模型定义不完备和因果关系不完备.在模型定义不完备条件下,用在线观测与模型共同约束的方法处理观测乱序及未定义事件,得到可行的诊断轨迹.相对于基于完备模型假设下不能诊断的结论,该方法扩展了诊断方法的适用范围,放松了对模型的约束要求.在因果不完备条件下,提出用因果图联系部件,解决分布式诊断中由于部件独立建模而导致的不彻底诊断,提高了诊断的精确性.通过实验验证,两种条件下的诊断方法均能在相应的不完备模型中得到预期诊断结果,并对模型进行局部修订,提高模型的完备性.

    • 融合关系与内容分析的社会标签推荐

      2012, 23(3):476-488. DOI: 10.3724/SP.J.1001.2012.04001

      摘要 (4871) HTML (0) PDF 680.75 K (6123) 评论 (0) 收藏

      摘要:标签是Web 2.0 时代信息分类与索引的重要方式.为解决标签系统所面临的不一致性、冗余性以及完备性等问题,标签推荐通过提供备选标签的方法来提高标签的质量.为了进一步提升标签推荐的质量,提出了一种基于标签系统中对象间关系与资源内容融合分析的标签推荐方法,给出了基于LDA(latent Dirichlet allocation)的融合表示对象间关系与资源内容的标签系统生成模型TSM/Forc,提出了一种基于概率的标签推荐方法,并给出了基于吉布斯(Gibbs)抽样的参数估计方法.实验结果表明,该方法可以提供比当前主流与最新方法更加准确的推荐结果.

    • 一个基于流程相似性的自动服务发现框架

      2012, 23(3):489-503. DOI: 10.3724/SP.J.1001.2012.04010

      摘要 (4330) HTML (0) PDF 849.99 K (4622) 评论 (0) 收藏

      摘要:服务发现是面向服务的网络软件开发过程的关键阶段,同时也是影响服务组合效率的关键因素.针对当前服务发现自动化程度低下、准确性不高的现状,从两个方面提高服务组合效率:首先,提出一种自动组合服务发现模式,支持流程粒度的组合服务发现及复用;其次,在发现过程中设计了一种量化的相似性评估算法,综合考虑组合流程的静态结构与动态行为特征,以提高服务发现的准确率;最后,结合以上两方面形成一个基于流程相似性的自动服务发现框架(automatic service discovery framework based on business process similarity,简称AutoDisc).利用真实数据完成的评估实验结果表明,AutoDisc的准确性优于单纯考虑结构或行为的发现方法,在所给出的应用案例中,使服务组合效率提高75.5%,具有较好的可扩展性.

    • 死路径语义下BPEL 路径敏感性缺陷分析

      2012, 23(3):504-516. DOI: 10.3724/SP.J.1001.2012.04065

      摘要 (4053) HTML (0) PDF 711.44 K (4031) 评论 (0) 收藏

      摘要:软件缺陷是衡量软件测试充分性的一项重要指标,为了提高基于BPEL 的组合Web 服务流程的可靠性和健壮性,提出了一种死路径语义下路径敏感的缺陷检测方法.死路径是BPEL 提供的特殊语义,不具有任何执行信息, 但是可以连接两个可执行路径片段.为了避免死路径对检测精度的影响,将死路径和路径条件有机地结合起来,采用了变量的抽象取值范围来表示流程的执行状态,即属性状态条件.通过状态条件中变量抽象取值范围为空来识别不可达路径及死路径,并在汇合节点进行了属性状态条件的合并.采用一个既与死路径相关又与执行路径相关的未初始化变量的缺陷检测贯穿整个分析与验证过程,进而说明了该方法的有效性.

    • 跨组织多业务事务建模与验证方法

      2012, 23(3):517-538. DOI: 10.3724/SP.J.1001.2012.04103

      摘要 (4107) HTML (0) PDF 606.92 K (4315) 评论 (0) 收藏

      摘要:面向服务的事务处理是保障业务交互和协作正确性的关键技术.针对跨组织多业务流程,提供了一种支持多业务事务建模与验证的方法.在建模方法上,对Pi-演算扩展了事务语义,将进程间的动作交互与跨组织膜活动相关联来刻画多业务事务协调行为.在验证过程中,基于等价自动机转换思路集成现有模型检验技术,验证多业务事务是否满足人们需要的各种性质.实验结果表明,该建模与验证方法能够有效地保障多业务流程在设计与实现过程中的正确性.

    • 一种非清洁数据库的数据模型

      2012, 23(3):539-549. DOI: 10.3724/SP.J.1001.2012.04042

      摘要 (4107) HTML (0) PDF 583.12 K (5876) 评论 (0) 收藏

      摘要:非清洁数据为数据管理带来了新的挑战,当前,处理非清洁的数据清洗方法在实际应用中存在一定的局限性,因此需要在一定程度上容忍非清洁数据的存在.这样,研究管理包含非清洁数据的数据库管理技术就成为了重要的问题,其核心在于如何从包含非清洁数据的数据库中得到满足应用所要求的清洁度的查询结果.从非清洁数据处理角度出发,提出了一种非清洁数据库的数据模型.该模型提出了非清洁数据的表示方法,支持非清洁数据的数据操作,并且支持数据操作清洁度的计算.同时还讨论了查询表达式的等价转换规则和模型的初步实现.

    • n-of-N 数据流模型上高效概率Skyline 计算

      2012, 23(3):550-564. DOI: 10.3724/SP.J.1001.2012.04050

      摘要 (3713) HTML (0) PDF 816.09 K (3972) 评论 (0) 收藏

      摘要:研究概率数据流上的q-skyline 计算问题.与只支持滑动窗口数据流模型的已有方法相比,所提出的方法能够支持更为通用的n-of-N 数据流模型.采用将q-skyline 查询转换为区间树上刺入查询的方法支持n-of-N 数据流模型.提出PnNM 算法维护支持n-of-N 数据流模型所需的相关数据结构,高效处理了不确定对象候选集合更新和区间更新等维护工作;提出PnNCont 算法实现连续查询处理.理论分析和实验结果表明,算法能够有效地支持概率数据流n-of-N 模型上的q-skyline 查询处理.

    • 半限制空间内的RFID 可能性k-近邻查询技术

      2012, 23(3):565-581. DOI: 10.3724/SP.J.1001.2012.04060

      摘要 (3990) HTML (0) PDF 1.01 M (4197) 评论 (0) 收藏

      摘要:作为一种监控与跟踪车流和人类活动等的潜在技术,RFID(radio frequency identification)已经在数据库领域得到了很大关注.RFID 监控对象上的k-近邻查询是一种最重要的时空查询,能够用来支持有价值的高层信息分析.但是,不同于没有限制的空间和基于限制的空间,RFID 监控场景通常被设置在一种半限制的空间内,需要新的存储和距离计算策略.此外,监控对象位置的不确定性对查询语义和处理方法提出了挑战.提出了半限制空间的概念, 并且分析了基于RFID 的半限制空间的模型.基于半限制空间,在给定一个动态查询点的基础上,提出了3 种模型和算法以有效地估计可能性k-近邻的查询结果,并采用一些特殊的索引技术加快查询的速度.实验对提出算法的效率和准确性进行了评估,表明了相关方法的有效性.

    • XML 动态区间编码方法

      2012, 23(3):582-593. DOI: 10.3724/SP.J.1001.2012.04003

      摘要 (4688) HTML (0) PDF 632.31 K (4388) 评论 (0) 收藏

      摘要:提出了适用于XML 文档更新环境下的区间编码方法— —DCLS(dynamic containment labeling scheme).DCLS 将基于整数的编码泛化到基于向量的编码,扩展了传统静态区间编码方法,有效避免了XML 文档更新时的重新编码.不论文档更新与否,DCLS 都显示了良好的性能:DCLS 利用基于整数的静态区间编码方法进行初始编码,在文档不更新的环境下,具有较高的存储效率和查询性能;同时,DCLS 将整数视为特殊向量,不仅能够支持文档更新,而且更新效率高;特别是倾斜插入时,DCLS 可以避免编码位长的快速增加.实验结果表明,与已有的动态区间编码方法相比,DCLS 具有更好的性能.

    • 模糊面向对象数据模型的描述逻辑表示与推理

      2012, 23(3):594-612. DOI: 10.3724/SP.J.1001.2012.04037

      摘要 (4785) HTML (0) PDF 931.19 K (4369) 评论 (0) 收藏

      摘要:通过分析描述逻辑与面向对象数据模型之间的关系,研究了基于描述逻辑的模糊面向对象数据(fuzzy object-oriented data,简称FOOD)模型的表示与推理.首先,进一步研究了FOOD 模型,提出了FOOD 模型的形式化定义和语义定义,以便更好地在FOOD模型与模糊描述逻辑之间建立对应关系;然后,针对FOOD模型的特点和推理需求,介绍了模糊描述逻辑f-ALCIQ.在此基础上,研究了基于f-ALCIQ 的FOOD 模型的表示与推理,包括:实现了从 FOOD 模型到f-ALCIQ 知识库在结构层和实例层上的转化,即实现了从FOOD 模型到f-ALCIQ TBox 的转化,以及从FOOD 模型相应的数据库实例到f-ALCIQ ABox 的转化;进而,基于转化得到的f-ALCIQ 知识库,研究了如何利用 f-ALCIQ 的推理机制对FOOD 模型的推理问题(一致性、包含性和冗余性等)进行推理;最后,设计并实现了基于f-ALCIQ 的模糊描述逻辑推理机(FRsQ 推理机),实现了对FOOD 模型和f-ALCIQ 模糊概念知识的自动推理.

    • 异步多信道无线传感器网络MAC 协议

      2012, 23(3):613-628. DOI: 10.3724/SP.J.1001.2012.03984

      摘要 (3936) HTML (0) PDF 1.04 M (4578) 评论 (0) 收藏

      摘要:针对无线传感器网络中控制信道饱和问题以及三重隐终端问题,提出了一种异步多信道MAC 协议—— RIM(receiver-initiated MAC).RIM 利用接收端开始的传输机制有效地解决了控制信道饱和问题,同时采用了基于概率的随机信道选择机制避免了三重隐终端问题.而且,RIM 支持一种简单且可靠的异步广播机制.通过基于马尔可夫链的理论分析,得到了RIM 中节点的最优占空比.为验证RIM 的实际性能,进行了模拟和真实实验.实验结果表明, 与其他多信道MAC 协议相比,随着信道数及网络负载的增加,RIM 增加了网络吞吐量,降低了传输所消耗的能量,同时也提高了广播的可靠性,达到了能量有效的目的.

    • 延迟容忍传感器网络中基于群组运动的事件传输

      2012, 23(3):629-647. DOI: 10.3724/SP.J.1001.2012.03971

      摘要 (3742) HTML (0) PDF 1.51 M (4212) 评论 (0) 收藏

      摘要:提出了一种基于分布式群组移动的事件分类传输策略GMED(distributed group mobility adaptive event delivery).通过有效地发现和利用传感器节点在运动过程中形成的群组,建立基于群组的事件分类传输模型,改善数据传输性能.其中,群组的转发是依据各自与汇聚点的机会概率按照多副本方式进行的;而群内的事件传输则是基于各成员的稳定邻居集建立传输路径,并以单副本方式进行.队列管理则根据事件的优先级决定递交的顺序和丢弃原则.此外,引入冗余副本控制机制,优化副本管理,降低网络负载.模拟实验结果表明,与现有的几种DTMSN(delay tolerant mobile sensor networks)数据传输算法相比,GMED 能以较低的数据传输能耗和传输延迟获得较高的数据传输成功率,且网络寿命相对较长.

    • 基于网络编码的对等网流媒体传输模型和算法

      2012, 23(3):648-661. DOI: 10.3724/SP.J.1001.2012.03991

      摘要 (4344) HTML (0) PDF 842.68 K (4477) 评论 (0) 收藏

      摘要:在对等网(peer-to-peer,简称P2P)流媒体系统中,节点(用户)的输出带宽(上行带宽)容量利用率的提高能够降低服务器的带宽开销.网络编码可以实现组播的最大吞吐率,因而具有提高系统中节点输出带宽容量利用率的潜力.将随机线性网络编码应用到P2P 流媒体系统中,建立了基于随机线性网络编码的P2P 流媒体传输过程模型,并据此建立传输算法的优化模型,比较研究了贪婪式算法、最少者优先算法和随机算法等.优化结果表明,随机算法可以平等均匀地获取数据包,能够最充分地利用节点的输出带宽容量,降低服务提供商的运营成本.通过对优化模型解的分析,对实际系统中的传输算法给出了设计指导原则.

    • 一种基于语义吸引的节点规模估计方法

      2012, 23(3):662-676. DOI: 10.3724/SP.J.1001.2012.03990

      摘要 (3910) HTML (0) PDF 764.54 K (3636) 评论 (0) 收藏

      摘要:节点规模是各种分布式应用的基础信息,节点波动的大规模网络环境要求节点规模估计方法具有较高的估计精度和较强的鲁棒性,已有的节点规模估计方法多侧重于某个方面的优化而未能充分权衡计算精度和鲁棒性. 提出一种基于语义吸引的节点规模估计方法——SEBSA(a network size estimation method based semantic attraction).SEBSA 将每个节点标识所对应的实数区间上的哈希值作为语义信息,节点通过与哈希值临近的节点周期性地交换哈希空间上的邻居信息,以快速吸引与自己哈希值最近的一组节点,测量该组节点哈希值的平均间距以估计节点规模.理论分析和实验结果表明,相对于已有方法,SEBSA 在节点频繁波动的网络环境中仍然能够快速地提供准确的节点规模信息.

    • 一种实现数据主动泄漏防护的扩展中国墙模型

      2012, 23(3):677-687. DOI: 10.3724/SP.J.1001.2012.03974

      摘要 (3984) HTML (0) PDF 595.03 K (4236) 评论 (0) 收藏

      摘要:中国墙模型具有能够同时提供自主控制和强制控制的特性,因而被广泛应用于商业领域中,以防止有竞争关系的企业之间的信息流动而导致利益冲突.但是由于对读写约束过于严格,因而应用范围有限,特别是在数据泄漏防护的应用中未能发挥其优越性.针对数据泄漏防护对信息流动的控制需求,从数据客体的角度出发,考虑中国墙模型中的利益冲突问题,提出了主动冲突关系的概念,将原来对信息双向流动的约束转换为对单向流动的约束.在此基础上,提出了一种可以实现数据主动泄漏防护的扩展中国墙模型ACWM(aggressive Chinese wall model),并给出了模型的形式化描述和相关定理的证明.分析表明,ACWM 模型可以实现传统中国墙模型的安全目标,而约束条件更加灵活,可以实现数据泄漏防护的需求.

    • 严格线性散播网络编码

      2012, 23(3):688-699. DOI: 10.3724/SP.J.1001.2012.03963

      摘要 (3540) HTML (0) PDF 677.98 K (3347) 评论 (0) 收藏

      摘要:针对线性广播和线性散播网络编码在保证节点或节点集解码空间维数方面的不足,提出了一类新的线性网络编码——严格线性散播网络编码.给出了严格线性散播的定义,并设计了相应的构造算法.此种网络编码增强了对网络中任意非源节点集的输入链路上的全局编码核的限制,但其构造所需的有限域的阶并不大于普通的线性散播.此外,还提出了多种转换矩阵的概念,并证明了普通线性散播到严格线性散播的转换矩阵的存在性.结合特殊的数据打包策略,论证了严格线性散播在异构网络中的应用优势:一方面,它能够利用单一网络编码会话实现异构网络中的多速率信息传输;另一方面,它能够为异构网络拓扑结构的扩展提供便利.

    • 代码混淆算法有效性评估

      2012, 23(3):700-711. DOI: 10.3724/SP.J.1001.2012.03994

      摘要 (4950) HTML (0) PDF 621.95 K (6115) 评论 (0) 收藏

      摘要:代码混淆是一种能够有效增加攻击者逆向分析和攻击代价的软件保护技术.然而,混淆算法的有效性评价和验证是代码混淆研究中亟待解决的重要问题.目前,对代码混淆有效性的研究大都是基于软件复杂性度量的,然而代码混淆作为一种保护软件安全的技术,更需要从逆向攻击的角度进行评估.将面向逆向工程的思想引入到代码混淆算法评估中,通过理论证明和具体实验验证了其可行性.该评估方法能够为混淆算法提供有效证明,并对判别和选择代码混淆算法具有指导意义,同时也有助于寻求更有效的代码混淆方法.

    • 基于静态贝叶斯博弈的蠕虫攻防策略绩效评估

      2012, 23(3):712-723. DOI: 10.3724/SP.J.1001.2012.03997

      摘要 (3836) HTML (0) PDF 692.67 K (4662) 评论 (0) 收藏

      摘要:现有蠕虫攻击策略(防护策略)评估方法没有考虑防护策略(攻击策略)变化对攻击策略(防护策略)绩效评估的影响,且防护策略评估忽视了策略实施成本.针对这种情况,构建了基于静态贝叶斯博弈的绩效评估模型 (performance evaluation model based on static Bayesian game,简称PEM-SBG)以及对抗情形下的蠕虫攻防策略绩效评估方法.在模型PEM-SBG 基础上提出的基于灰色多属性理论的防护策略绩效评估方法,综合考虑了成本类和收益类的多个评估属性,有助于提高评估过程的全面性.针对典型的蠕虫攻防场景.利用仿真工具SSFNet 进行了模拟实验,验证了所提出的模型和方法的有效性.

    • 自适应门限的EPON 动态带宽分配实现

      2012, 23(3):724-734. DOI: 10.3724/SP.J.1001.2012.04038

      摘要 (3316) HTML (0) PDF 630.01 K (4082) 评论 (0) 收藏

      摘要:EPON(Ethernet passive optical network)是解决宽带接入中瓶颈问题的关键技术.为了实现EPON 中共享上行带宽的公平和有效分配,以及不同分类业务的QoS 保证,提出了基于门限的动态带宽分配算法.该算法根据 ONU(optical network unit)的带宽请求和门限值授权分配带宽,实现了3 种基于反馈控制理论的自适应调整门限方法并分析了其优缺点.模拟实验结果表明,与其他算法相比,该算法能够减少平均包时延,提高网络吞吐量.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:https://www.jos.org.cn
  • 刊号:ISSN 1000-9825
  •           CN 11-2560/TP
  • 国内定价:70元
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号