2013, 24(6):1165-1176. DOI: 10.3724/SP.J.1001.2013.04288
摘要:研究了在制造商占优并优先调度的分销供应链中,多个分销商同时与制造商进行协商以改善自身调度的问题,建立了基于补偿的多目标协商调度模型,提出了同时实施分销商局部演化计算与制造商全局演化计算的新型多目标合作协同演化算法GLCCEC.提出了制造商全局精英解的跳跃渐变解组合策略及全局非支配解集实时更新策略,设计了保持局部作业顺序约束下的分销商局部解全局化动态规划算法.实验结果表明,GLCCEC算法能够在不损害制造商调度的条件下有效改善每个分销商的调度,所获得的非支配解集不仅目标值优于现有的3 种主要合作协同演化算法MOCCGA,NSCCGA,GBCCGA,而且具有良好的解分散度.
2013, 24(6):1177-1195. DOI: 10.3724/SP.J.1001.2013.04323
摘要:针对多模态优化问题,提出了基于广义凸下界估计模型的改进差分进化算法.首先,基于模型变换方法将原优化问题转变为单位单纯形约束条件下的严格递增射线凸优化问题;其次,基于广义凸理论,利用差分进化算法中更新个体的适应度知识,建立原优化问题广义凸下界估计模型,设计实现了基于N-叉树的估计模型快速计算方法;进而,综合考虑原问题目标值与其估计值之间的差异,提出一种基于有偏采样的小生境指标,并设计区域进化树更新策略来保证算法的局部搜索能力.数值实验结果表明,提出的算法能够有效地发现并维持一定数量的满意解模态,动态地实现全局模态搜索到模态内局部增强的自适应平滑过渡.对于给出的测试问题,能够发现所有的全局最优解以及一些较好的局部极值解.
2013, 24(6):1196-1206. DOI: 10.3724/SP.J.1001.2013.04281
摘要:设计了一种混合并行XML 解析方法.该方法由轻量级事件划分、事件级并行解析和后处理三阶段组成.使用SIMD 指令来加速事件划分.阶段级处理使用软件流水线并行技术.同时使用了事件级数据并行技术和流水线并行技术,所以该方法是一种混合并行方法.与其他方法相比,该方法具有高效并行解析和低通信开销的优势.在基于8 核Intel Xeon X7560 CPU、Linux 操作系统机器上的测试结果表明,与现有其他方法相比,该方法能够达到更高的加速以及更好的可扩展性.
2013, 24(6):1207-1221. DOI: 10.3724/SP.J.1001.2013.04259
摘要:针对效用网格下截止期约束的工作流费用优化问题,提出了路径平衡(path balance,简称PB)算法,对工作流中各路径长度进行调整,并提出基于路径平衡的费用优化(path balance based cost optimization,简称PBCO)算法.PBCO 基于PB 的计算结果设置初始约束时间,充分利用了工作流的费用优化空间.同时,采用逆向分层策略对任务进行分层,并根据各层任务数按比例分配冗余时间,有效地增大了多数任务的费用优化空间,进一步改善了工作流的费用优化效果.实验结果表明,PBCO 比另外几种著名算法(如DET,DBL 等)改进了约35%.
2013, 24(6):1222-1242. DOI: 10.3724/SP.J.1001.2013.04387
摘要:随着语义网以及信息抽取技术等研究的发展,Web 上涌现出越来越多的RDF 数据,海量RDF 数据的管理,已经成为学术界和工业界研究的热点之一.从RDF 数据集形态及RDF 数据组织存储两个维度以及查询表述、查询处理、查询优化等方面,深入地分析和比较了RDF 数据查询处理方法,并在此基础上提出了未来研究的方向和挑战.
2013, 24(6):1243-1262. DOI: 10.3724/SP.J.1001.2013.04320
摘要:随着移动定位技术和物联网技术的不断发展,时空查询技术受到了广泛关注.在实际的应用中,对象的移动方向和轨迹常受到空间网络限制并且位置信息往往带有不确定性.在以一般性的概率分布函数形式表示位置的不确定性的基础上,提出一种基于分割区间的概率查询增量处理模型和查询优化方法.考虑采用概率分布近似中心作为目标对象的估计位置,近似地解决普遍位置不确定性的问题,以较小的精度损失换取效率上的极大提高.最后,采用真实的路网数据集和模拟的对象分布,验证了模型和算法在效率和准确性方面均表现突出.
2013, 24(6):1263-1273. DOI: 10.3724/SP.J.1001.2013.04274
摘要:由于攻击者采用各种技术手段隐藏攻击行为,DDoS 攻击变得越发难以发现,应用层DDoS 成为Web 服务器所面临的最主要威胁之一.从通信群体的层面分析Web 通信的外联行为特征的稳定性,并提出了一种应用层DDoS 检测方法.该方法用CUSUM 算法检测Web 群体外联行为参数的偏移,据此来判断DDoS 攻击行为的发生.由于外联行为模型刻画的是Web 通信群体与外界的交互,并非用户个体行为,所以攻击者难以通过模仿正常访问行为规避检测.该方法不仅能够发现用户群体访问行为的异常,而且能够有效区分突发访问和应用层DDoS 攻击.模拟实验结果表明,该方法能够有效检测针对Web 服务器的不同类型的DDoS 攻击.
2013, 24(6):1274-1294. DOI: 10.3724/SP.J.1001.2013.04284
摘要:为了解决前缀劫持、路由伪造和源地址欺骗问题,设计了一种路由体系——基于责任域的安全路由体系(accountability realm based secure routing architecture,简称Arbra).首先,提出了自治系统到责任域的映射方法和基于责任域的两级路由结构,责任域是具有独立管理主体的网络,也是Arbra 网络拓扑的基本元素,因为它为内部用户的网络行为负责,所以称做责任域;其次,建立了基于责任域的路由体系设计框架,主要包括混合寻址方案、核心路由协议、标签映射协议、分组转发流程和公钥管理机制等研究内容;最后,比较了Arbra 和其他著名路由结构(IPv4/v6,LISP,AIP)的异同,分析了Arbra 的安全性、可扩展性、通信性能和部署代价.研究结果表明:(1) Arbra 具有的分布式信任模型,不仅有利于抵御前缀劫持、路由伪造和源地址欺骗攻击,而且还给许多其他网络安全问题的解决奠定了基础;(2) Arbra 具有优良的可扩展性,路由表的规模较小;(3) Arbra 具有合理的通信性能和部署代价.该研究成果可以看做是以网络安全为视角对未来信息网络体系结构的有益探索.
肖春静 , 刘明 , 龚海刚 , 陈贵海 , 周帆 , 吴跃
2013, 24(6):1295-1309. DOI: 10.3724/SP.J.1001.2013.04291
摘要:不同于无线传感器网络和移动Ad Hoc 网络,无线Mesh 网络中的组播主要侧重于提高吞吐量,而干扰是影响吞吐量的重要因素.在构建组播拓扑时,传统的方法主要考虑最小价值或最短路径,而通过减少干扰来提高组播性能的研究较少,且它们的干扰计算方法都采用单播的思想,并不适合于组播.例如,当n 个接收节点同时从一个节点接收数据时,在组播中这n 个接收节点之间不存在干扰,而在单播中认为存在干扰.因此,提出了组播冲突图来计算组播干扰,给出组播树干扰的定义.可以发现,求最小干扰组播扰树是NP 完全问题,然后提出基于万有引力的启发式算法构建具有较小干扰的组播树.为了适用于多信道的情况,提出了满足不同干扰范围的多跳信道分配算法.最后,仿真结果显示,与MCM 相比,所提出的算法无论是在单天线单信道还是多天线多信道下,都能取得较高的吞吐量和较低的延迟.
2013, 24(6):1310-1323. DOI: 10.3724/SP.J.1001.2013.04313
摘要:具有认知性、自主性和适变性等特点的认知Wi-Fi 2.0 无线网络技术,作为提高无线网络容量的重要技术不断引起学术界、标准组织和工业界的关注.针对现有功率控制技术不能刻画多个认知节点存在分层决策的现象,提出一种认知Wi-Fi 2.0 无线网络中多用户动态分层功率控制算法.基于提出的斯坦科尔伯格(Stackelberg)容量最大化博弈模型,为认知Wi-Fi 2.0 无线网络中感知信息不对称的多用户分别设计了分布式功率控制方法,实现领导者用户和跟随者用户的多阶段动态交互在保证个体效用的同时实现网络整体性能.该算法根据当前认知Wi-Fi 2.0 无线网络中多个认知节点接入频谱顺序的不同,确定领导者用户和跟随者用户;然后,对于领导者和跟随者分别采用不同的功率控制策略,并多次交互实现多用户分层算法的动态交互收敛.蒙特卡洛仿真验证了算法的有效性.
2013, 24(6):1324-1333. DOI: 10.3724/SP.J.1001.2013.04287
摘要:SNOW3G 流密码算法是3G Partnership Project(3GPP)中实现数据保密性和数据完整性的标准算法UEA2&UIA2 的核心,ZUC 是3GPP 中加密算法128-EEA3 和完整性保护算法128-EIA3 的核心.至今还没有针对SNOW3G 进行猜测决定攻击的研究结果出现.对SNOW3G 进行了猜测决定攻击,其计算复杂度为2320,所需数据量为9 个32 比特密钥字.通过对ZUC 算法设计的分析,将ZUC 算法中基于32 比特字的非线性函数转化为基于16 比特半字的非线性函数,提出了基于16 比特半字的猜测决定攻击,其计算复杂度为2392,所需数据量为9 个32 比特密钥字,该结果优于已有的针对ZUC 的猜测决定攻击.分析结果表明,尽管ZUC 算法的内部状态规模小于SNOW3G,在抵抗猜测决定攻击方面,ZUC 明显优于SNOW3G.
2013, 24(6):1334-1345. DOI: 10.3724/SP.J.1001.2013.04279
摘要:针对加密流量的在线普适识别问题,提出一种基于加权累积和检验的时延自适应加密流量盲识别算法.利用加密数据的随机性特点,对网络报文逐一实施累积和检验,根据报文长度将结果进行加权综合.无需解密操作,也无需匹配特定内容,实现了对加密流量的普适识别.可动态调整报文的检测数量,以达到时延和准确率的统一,实现在线识别.仿真结果显示,对公开和未公开的加密协议流量,识别率均可达到90%以上.
2013, 24(6):1346-1360. DOI: 10.3724/SP.J.1001.2013.04395
摘要:随着分布式系统规模的增大,设计复杂度也不断提升,系统可靠性所面临的问题也越来越严峻.由于拜占庭协议能够容忍包括人为失误、软件bug 和安全漏洞等各种形式的错误,其系统技术和实现方法越来越受到研究者们的重视.介绍和总结了目前拜占庭系统技术的研究成果,分析了目前拜占庭系统的研究现状,并探讨了拜占庭系统的发展趋势.通过分析得出:1) 拜占庭系统性能上仍然与已经实用的非拜占庭系统相距较大,占用资源数量仍然较多,需要进一步研究其性能和资源优化技术;2) 通过检测错误或者定期修复来降低系统中的错误,是延长系统可持续运行时间的方法,需要研究新的、高效的全面检测拜占庭服务器、合理定期修复等保障系统可持续运行的方法;3)实际应用背景和需求及其特定错误类型的处理方法对拜占庭协议和功能等提出了不一样的要求,需要研究拜占庭系统在实际中的应用和可用性.
2013, 24(6):1361-1375. DOI: 10.3724/SP.J.1001.2013.04325
摘要:应用级checkpointing 是一种在大规模科学计算领域中备受关注的容错技术,该技术由用户程序员选择在适当的地方保存关键数据,从而降低了容错开销.选择合适的checkpointing 位置、减小全局checkpoint 保存数据量是优化应用级checkpointing 技术的关键问题.对于近年来推出的带有通用GPU 的异构系统上的应用级checkpointing 技术,也同样面临上述问题.针对异构系统体系结构和程序特征,对面向异构系统的应用级checkpointing 技术的检查点设置进行了静态分析,提出两套不同机制的检查点设置方法:同步及异步检查点设置方法,并分别就checkpointing 优化设置问题对其进行数学建模和求解.最后,通过实验验证并评估了所提出的两种方法的性能.
2013, 24(6):1376-1389. DOI: 10.3724/SP.J.1001.2013.04280
摘要:处理器发展已进入多核时代.现有并行仿真内核常常以多进程方式使用多核资源,存在较大的同步和通信开销,无法深入发掘多核处理器潜能.基于层次化并行仿真内核(HPSK)模型,重点对时间管理服务和事件管理服务进行优化,支持多线程架构下进行高效能仿真:(1) 基于混合时间推进模式,提出最小发送时戳(EETS)计算协议,可根据仿真应用特点灵活配置为异步EETS 算法以支持高效的全局同步,并证明了计算协议的正确性;(2) 基于并行仿真事件交互的特点,提出无锁创建、异步提交和指针通信的事件管理算法,最小化线程之间的锁开销并减少了内存的消耗.实验结果表明,采用上述优化服务的HPSK 能够在各种条件下获得很好的加速效果.
2013, 24(6):1390-1402. DOI: 10.3724/SP.J.1001.2013.04392
摘要:多核处理器并行程序的确定性重放是实现并行程序调试的有效手段,对并行编程有重要意义.但由于多核架构下存在共享访存不同步问题,并行程序确定性重放的研究依然面临多方面的挑战,给并行程序的调试带来很大困难,严重影响了多核架构下并行程序的普及和发展.分析了多核处理器造成并行程序确定性重放难以实现的关键因素,总结了确定性重放的评价指标,综述了近年来学术界对并行程序确定性重放的研究.根据总结的评价指标,从纯软件方式和硬件支持方式对目前的确定性重放方法进行了分析与对比,并在此基础上对多核架构下并行程序的确定性重放未来的研究趋势和应用前景进行了展望.
秦秀磊 , 张文博 , 王伟 , 魏峻 , 赵鑫 , 钟华 , 黄涛
2013, 24(6):1403-1417. DOI: 10.3724/SP.J.1001.2013.04352
摘要:Key/Value存储系统在大规模、高性能云应用支撑方面扮演了重要的角色,对云端Key/Value存储系统而言,数据迁移是实现节点动态扩展与弹性负载均衡的关键技术.如何降低迁移开销,是云服务提供商需着力解决的问题.已有研究工作大多针对非虚拟化环境下的数据迁移问题,这些方法对于云端Key/Value存储系统而言往往并不适用.为应对上述挑战,将数据迁移问题纳入负载均衡场景解决.提出一种基于面积的迁移开销模型,该模型可以有效感知底层VM性能干扰状况,权衡迁移时间与性能衰减值.进一步提出一种开销敏感的数据迁移算法,该算法基于开销模型与均衡度制订数据迁移计划,选取最优的迁移操作.基于雅虎的云服务基准测试工具YCSB验证了该方法的有效性.