2015年 第52卷 第12期
摘要：
“互联网+”通过发挥互联网在生产要素配置中的优化和集成作用，提升实体经济的创新力和生产力。以MOOC为代表的互联网教育、以工业4.0为代表的智能制造、以互联网金融为代表的现代服务业等，都展示出“互联网+”的巨大创新空间和潜力。“互联网+”是计算机与其他学科交叉而成的新型技术，面临着一系列理论和技术的挑战，需要融合信息学科和其他传统学科的理论、方法与技术。例如，物理系统的多源动态感知、多维异构数据的融合分析、服务模式的优化改进、多目标的动态优化决策，等等，都是极富挑战性的研究内容。正是在这样的背景下，《计算机研究与发展》推出了面向“互联网+”的应用技术研究专题。本期专题论文涵盖互联网+在多个不同领域的典型应用所涉及的理论和关键技术问题，作者从互联网+的不同应用场景阐述了问题背景、研究意义、设计算法、关键技术和取得的成果，展示了“互联网+”技术的热点应用。在一定程度上反映了当前国内学者在“互联网+”技术方面的代表性研究方向。
“互联网+”通过发挥互联网在生产要素配置中的优化和集成作用，提升实体经济的创新力和生产力。以MOOC为代表的互联网教育、以工业4.0为代表的智能制造、以互联网金融为代表的现代服务业等，都展示出“互联网+”的巨大创新空间和潜力。“互联网+”是计算机与其他学科交叉而成的新型技术，面临着一系列理论和技术的挑战，需要融合信息学科和其他传统学科的理论、方法与技术。例如，物理系统的多源动态感知、多维异构数据的融合分析、服务模式的优化改进、多目标的动态优化决策，等等，都是极富挑战性的研究内容。正是在这样的背景下，《计算机研究与发展》推出了面向“互联网+”的应用技术研究专题。本期专题论文涵盖互联网+在多个不同领域的典型应用所涉及的理论和关键技术问题，作者从互联网+的不同应用场景阐述了问题背景、研究意义、设计算法、关键技术和取得的成果，展示了“互联网+”技术的热点应用。在一定程度上反映了当前国内学者在“互联网+”技术方面的代表性研究方向。
2015, 52(12): 2659-2668.
DOI: 10.7544/issn1000-1239.2015.20150749
摘要：
数字版权管理(digital rights management, DRM)是我国信息化建设的重要内容.但高昂的投资成本和欠佳的用户体验是其进一步推广的瓶颈.而已有的采用云计算解决DRM瓶颈问题的研究大都只着眼于云计算的存储服务功能，较少关注云计算的计算优势.提出了一种云计算环境下支持属性撤销的外包解密DRM方案.考虑到DRM中用户隐私保护的问题，提出用户通过匿名标签购买许可证.此外，为了充分发挥云计算在计算上的优势以及可以灵活、细粒度地撤销用户的属性，提出了一种支持属性撤销的外包解密CP-ABE(ciphertext-policy attribute-based encryption)机制.与已有的基于云计算的数字版权保护方案相比，提出的方案在保护内容和用户隐私的同时，支持灵活的访问控制机制和细粒度的用户属性撤销，并且支持CP-ABE的解密外包计算，方案具有较好的实用性.
数字版权管理(digital rights management, DRM)是我国信息化建设的重要内容.但高昂的投资成本和欠佳的用户体验是其进一步推广的瓶颈.而已有的采用云计算解决DRM瓶颈问题的研究大都只着眼于云计算的存储服务功能，较少关注云计算的计算优势.提出了一种云计算环境下支持属性撤销的外包解密DRM方案.考虑到DRM中用户隐私保护的问题，提出用户通过匿名标签购买许可证.此外，为了充分发挥云计算在计算上的优势以及可以灵活、细粒度地撤销用户的属性，提出了一种支持属性撤销的外包解密CP-ABE(ciphertext-policy attribute-based encryption)机制.与已有的基于云计算的数字版权保护方案相比，提出的方案在保护内容和用户隐私的同时，支持灵活的访问控制机制和细粒度的用户属性撤销，并且支持CP-ABE的解密外包计算，方案具有较好的实用性.
2015, 52(12): 2669-2683.
DOI: 10.7544/issn1000-1239.2015.20150721
摘要：
随着互联网+、云计算以及大数据等领域的迅速发展，异构平台成为部署科学计算、工业控制、云存储等关键应用的重要平台.由于平台内处理机性能及软硬件体系结构的异构性，异构平台表现出良好的可扩展性与高性价比.但是平台规模扩大和系统应用日趋复杂导致异构平台上实时任务的可调度性变差，系统可用性降低.针对此问题，提出了一种异构平台实时任务的可用性提升容错调度算法(availability improving fault-tolerant scheduling algorithm, AIFSAL).以处理器利用率和可用性成本为依据设计任务调度整体框架结构、处理机、任务以及调度模型；结合可用性成本设计算法并通过主副版本备份(primary/backup copy, PB)方法实现容错，任务副版本根据处理器利用率不同选择被动或重叠方式执行以减少系统冗余开销，提高可调度性，调度中无论任务主、副版本均优先选择可用性成本低的处理机以提高系统可用性；对任务分配情况和可调度性进行理论分析以证明AIFSAL的可行性.仿真实验与比较分析表明，AIFSAL较可用性约束(availability approached task scheduling algorithm, AATSAL)算法、单调速率扩展(task partition based fault-tolerant rate-monotonic, TPFTRM)算法以及最早完成时间(MinMin)算法在不降低可调度性的基础上有效地提升了系统可用性，减少了系统综合开销，综合性能提高显著.
随着互联网+、云计算以及大数据等领域的迅速发展，异构平台成为部署科学计算、工业控制、云存储等关键应用的重要平台.由于平台内处理机性能及软硬件体系结构的异构性，异构平台表现出良好的可扩展性与高性价比.但是平台规模扩大和系统应用日趋复杂导致异构平台上实时任务的可调度性变差，系统可用性降低.针对此问题，提出了一种异构平台实时任务的可用性提升容错调度算法(availability improving fault-tolerant scheduling algorithm, AIFSAL).以处理器利用率和可用性成本为依据设计任务调度整体框架结构、处理机、任务以及调度模型；结合可用性成本设计算法并通过主副版本备份(primary/backup copy, PB)方法实现容错，任务副版本根据处理器利用率不同选择被动或重叠方式执行以减少系统冗余开销，提高可调度性，调度中无论任务主、副版本均优先选择可用性成本低的处理机以提高系统可用性；对任务分配情况和可调度性进行理论分析以证明AIFSAL的可行性.仿真实验与比较分析表明，AIFSAL较可用性约束(availability approached task scheduling algorithm, AATSAL)算法、单调速率扩展(task partition based fault-tolerant rate-monotonic, TPFTRM)算法以及最早完成时间(MinMin)算法在不降低可调度性的基础上有效地提升了系统可用性，减少了系统综合开销，综合性能提高显著.
2015, 52(12): 2684-2694.
DOI: 10.7544/issn1000-1239.2015.20150726
摘要：
无线网络中的丢包，一般认为是由拥塞或无线信道衰落造成的.在4G-LTE移动网络中，其传输特征的变化使得已有丢包区分算法并不适用.对此，提出了一种针对4G-LTE移动网络的丢包区分算法LDA-LTE.首先，基于LTE基站仿真器构建了真实可控的4G-LTE移动网络仿真测试平台；然后分别采集并分析了4G-LTE移动网络在拥塞和无线信道衰落条件下的传输特征；最后根据以上传输特征，提出了LDA-LTE丢包区分算法，实现了4G-LTE移动网络在拥塞和无线信道衰落同时发生场景中的丢包区分.实验结果证明，在4G-LTE移动网络中，由于网络传输特性与丢包特征的变化，使得传统的丢包区分算法并不适用，所提方法的区分结果准确度更高.
无线网络中的丢包，一般认为是由拥塞或无线信道衰落造成的.在4G-LTE移动网络中，其传输特征的变化使得已有丢包区分算法并不适用.对此，提出了一种针对4G-LTE移动网络的丢包区分算法LDA-LTE.首先，基于LTE基站仿真器构建了真实可控的4G-LTE移动网络仿真测试平台；然后分别采集并分析了4G-LTE移动网络在拥塞和无线信道衰落条件下的传输特征；最后根据以上传输特征，提出了LDA-LTE丢包区分算法，实现了4G-LTE移动网络在拥塞和无线信道衰落同时发生场景中的丢包区分.实验结果证明，在4G-LTE移动网络中，由于网络传输特性与丢包特征的变化，使得传统的丢包区分算法并不适用，所提方法的区分结果准确度更高.
2015, 52(12): 2695-2706.
DOI: 10.7544/issn1000-1239.2015.20150745
摘要：
在能量收集信息物理融合系统(energy harvesting based cyber-physical systems, EHCPS)中,其能量管理体系结构不同于传统电池供电嵌入式系统,任务调度策略需要考虑能量收集单元的能量输出、电池的能量存储和计算任务的能量消耗.实时任务在满足能量约束的情况下,才能满足时间约束.传统抢占阈值调度的可调度性分析没有考虑任务的能量属性,其阈值分配算法也不适用于EHCPS.针对此问题,提出了一种能量相关抢占阈值调度策略(energy related preemption threshold scheduling, ERPT),在可调度性分析中融入任务能耗属性和能量补充能力,并给出了阈值分配算法,为抢占阈值调度在EHCPS中的应用提供了一种解决方法.通过与目前现有的2个经典调度策略进行比较,验证了ERPT策略能够有效减少任务抢占.
在能量收集信息物理融合系统(energy harvesting based cyber-physical systems, EHCPS)中,其能量管理体系结构不同于传统电池供电嵌入式系统,任务调度策略需要考虑能量收集单元的能量输出、电池的能量存储和计算任务的能量消耗.实时任务在满足能量约束的情况下,才能满足时间约束.传统抢占阈值调度的可调度性分析没有考虑任务的能量属性,其阈值分配算法也不适用于EHCPS.针对此问题,提出了一种能量相关抢占阈值调度策略(energy related preemption threshold scheduling, ERPT),在可调度性分析中融入任务能耗属性和能量补充能力,并给出了阈值分配算法,为抢占阈值调度在EHCPS中的应用提供了一种解决方法.通过与目前现有的2个经典调度策略进行比较,验证了ERPT策略能够有效减少任务抢占.
2015, 52(12): 2707-2724.
DOI: 10.7544/issn1000-1239.2015.20140566
摘要：
由于带宽、缓存、能量等资源有限，延迟容忍网络(delay tolerant networks, DTNs)节点会具有一定的自私性.为节省宝贵的资源，自私节点会拒绝转发其他节点的消息，从而严重影响路由性能.为激励DTNs自私节点合作转发，减小消息传递时延，提出一种基于虚拟货币的激励感知低时延路由(virtual currency-based incentive-aware low delay routing, VCILDR).该路由通过建立基于时延的货币支付和分配策略，促使自私节点快速转发其他节点消息，将直接互利消息转发给传递时延小的节点，并交换可交换互利消息.建立轮流出价讨价还价博弈模型，以确定路由中节点的可交换互利消息，并提出一种求解该模型子博弈完美均衡的贪婪算法.在真实数据集上对该激励感知低时延路由的性能进行仿真验证.实验结果表明，该路由能够有效激励DTNs自私节点进行合作转发，减小消息传递时延，同时提高消息传递成功率.
由于带宽、缓存、能量等资源有限，延迟容忍网络(delay tolerant networks, DTNs)节点会具有一定的自私性.为节省宝贵的资源，自私节点会拒绝转发其他节点的消息，从而严重影响路由性能.为激励DTNs自私节点合作转发，减小消息传递时延，提出一种基于虚拟货币的激励感知低时延路由(virtual currency-based incentive-aware low delay routing, VCILDR).该路由通过建立基于时延的货币支付和分配策略，促使自私节点快速转发其他节点消息，将直接互利消息转发给传递时延小的节点，并交换可交换互利消息.建立轮流出价讨价还价博弈模型，以确定路由中节点的可交换互利消息，并提出一种求解该模型子博弈完美均衡的贪婪算法.在真实数据集上对该激励感知低时延路由的性能进行仿真验证.实验结果表明，该路由能够有效激励DTNs自私节点进行合作转发，减小消息传递时延，同时提高消息传递成功率.
2015, 52(12): 2725-2735.
DOI: 10.7544/issn1000-1239.2015.20140560
摘要：
射频识别(radio frequency identification, RFID)是物联网需要研究的关键技术之一.基于对RFID技术的研究，提出了一种基于关联ID的防碰撞新方法.有记忆标签和无记忆标签在防碰撞算法上的主要区别在于二者实现的机理有所不同.针对有记忆的标签，该方法增加标签之间的关联关系，使标签在一定的触发条件下可以主动发送自己的ID.该方法不同于无记忆的标签.由于父子标签间存在关联关系，将该方法应用于基于多叉搜索树的确定性防碰撞情况中，其优势是单次通信可以同时识别多个标签，极大地提高了识别效率；将该方法应用于不确定性的ALOHA防碰撞情况中，读写器可以依据脉冲的位置判断出空时隙的位置，从而避免由于(在读取时隙时)读取空时隙而造成的效率下降问题.由于该方法不受ID的长度限制，通过大量的实验表明，该方法在多种应用过程中能够大幅降低碰撞的概率，能够提高系统的识别效率.
射频识别(radio frequency identification, RFID)是物联网需要研究的关键技术之一.基于对RFID技术的研究，提出了一种基于关联ID的防碰撞新方法.有记忆标签和无记忆标签在防碰撞算法上的主要区别在于二者实现的机理有所不同.针对有记忆的标签，该方法增加标签之间的关联关系，使标签在一定的触发条件下可以主动发送自己的ID.该方法不同于无记忆的标签.由于父子标签间存在关联关系，将该方法应用于基于多叉搜索树的确定性防碰撞情况中，其优势是单次通信可以同时识别多个标签，极大地提高了识别效率；将该方法应用于不确定性的ALOHA防碰撞情况中，读写器可以依据脉冲的位置判断出空时隙的位置，从而避免由于(在读取时隙时)读取空时隙而造成的效率下降问题.由于该方法不受ID的长度限制，通过大量的实验表明，该方法在多种应用过程中能够大幅降低碰撞的概率，能够提高系统的识别效率.
2015, 52(12): 2736-2749.
DOI: 10.7544/issn1000-1239.2015.20140667
摘要：
在使用WiFi接入上层服务的无线传感器网络应用中，由于WiFi链路的不稳定性，使用固定位置的网关难以适应长期稳定可靠接入的要求.提出一种基于ZigBee和WiFi双模通信节点的，适用于不稳定WiFi链路下的网络设备自适应接入及组网方法EasiARS(adaptive roles switching)，该方法包括实时低开销的WiFi覆盖环境探测和更新方法、节点自适应角色分配方法、网关和节点均为能量受限设备情况下的WiFi覆盖区内分簇和数据传输方法.EasiARS可以在外部WiFi网络环境动态变化的情况下进行传感网设备的快速部署，并根据WiFi链路的状态自适应地调整节点角色和传输策略，使数据稳定传输并均衡WiFi覆盖区内节点的能量消耗.实验验证表明，在WiFi链路状态变化下，使用EasiARS的传感网能够自适应地切换节点的工作角色，形成合适的网络拓扑结构，保证数据的稳定上传，与采用单个固定位置网关的方法比较，随着WiFi链路不同程度的变化，EasiARS的网络丢包率最多可降低90%；与采用多个备选网关的方法比较，使用EasiARS的网络生存期提高了67%，并减少了部署前期对WiFi链路质量测试和评估的工作负担.
在使用WiFi接入上层服务的无线传感器网络应用中，由于WiFi链路的不稳定性，使用固定位置的网关难以适应长期稳定可靠接入的要求.提出一种基于ZigBee和WiFi双模通信节点的，适用于不稳定WiFi链路下的网络设备自适应接入及组网方法EasiARS(adaptive roles switching)，该方法包括实时低开销的WiFi覆盖环境探测和更新方法、节点自适应角色分配方法、网关和节点均为能量受限设备情况下的WiFi覆盖区内分簇和数据传输方法.EasiARS可以在外部WiFi网络环境动态变化的情况下进行传感网设备的快速部署，并根据WiFi链路的状态自适应地调整节点角色和传输策略，使数据稳定传输并均衡WiFi覆盖区内节点的能量消耗.实验验证表明，在WiFi链路状态变化下，使用EasiARS的传感网能够自适应地切换节点的工作角色，形成合适的网络拓扑结构，保证数据的稳定上传，与采用单个固定位置网关的方法比较，随着WiFi链路不同程度的变化，EasiARS的网络丢包率最多可降低90%；与采用多个备选网关的方法比较，使用EasiARS的网络生存期提高了67%，并减少了部署前期对WiFi链路质量测试和评估的工作负担.
2015, 52(12): 2750-2763.
DOI: 10.7544/issn1000-1239.2015.20140602
摘要：
基于位置服务(location-based services, LBSs)中的不可信服务提供商不断收集用户个人数据，为用户隐私带来威胁.因此，LBSs中的位置隐私保护研究已在学术界和工业界受到广泛关注.现有道路网络中的位置隐私保护方法大多是基于深度或广度图遍历的算法，需重复扫描道路网络的全局拓扑信息，匿名效率较低.针对这一问题，利用网络Voronoi图(network Voronoi diagram, NVD)将道路网络事先划分为独立的网络Voronoi单元，将传统方法中的多次遍历全局道路网络转化为了访问网络Voronoi单元中的局部路网信息.根据网络Voronoi单元覆盖的移动用户数和路段数，将网络Voronoi单元分为了不安全单元、安全-中单元和安全-大单元3类，提出了适应不同类型网络Voronoi单元特点的高效位置匿名算法.最后，通过在真实数据集上进行大量实验，验证了提出算法在仅比传统算法多牺牲0.01%的查询代价的前提下，保证了100%的匿名成功率和0.34ms的高效匿名时间，在隐私保护强度和算法性能方面取得了较好的平衡.
基于位置服务(location-based services, LBSs)中的不可信服务提供商不断收集用户个人数据，为用户隐私带来威胁.因此，LBSs中的位置隐私保护研究已在学术界和工业界受到广泛关注.现有道路网络中的位置隐私保护方法大多是基于深度或广度图遍历的算法，需重复扫描道路网络的全局拓扑信息，匿名效率较低.针对这一问题，利用网络Voronoi图(network Voronoi diagram, NVD)将道路网络事先划分为独立的网络Voronoi单元，将传统方法中的多次遍历全局道路网络转化为了访问网络Voronoi单元中的局部路网信息.根据网络Voronoi单元覆盖的移动用户数和路段数，将网络Voronoi单元分为了不安全单元、安全-中单元和安全-大单元3类，提出了适应不同类型网络Voronoi单元特点的高效位置匿名算法.最后，通过在真实数据集上进行大量实验，验证了提出算法在仅比传统算法多牺牲0.01%的查询代价的前提下，保证了100%的匿名成功率和0.34ms的高效匿名时间，在隐私保护强度和算法性能方面取得了较好的平衡.
2015, 52(12): 2764-2775.
DOI: 10.7544/issn1000-1239.2015.20148160
摘要：
针对基于查询表的Dyna优化算法在大规模状态空间中收敛速度慢、环境模型难以表征以及对变化环境的学习滞后性等问题,提出一种新的基于近似模型表示的启发式Dyna优化算法(a heuristic Dyna optimization algorithm using approximate model representation, HDyna-AMR),其利用线性函数近似逼近Q值函数,采用梯度下降方法求解最优值函数.HDyna-AMR算法可以分为学习阶段和规划阶段.在学习阶段,利用agent与环境的交互样本近似表示环境模型并记录特征出现频率；在规划阶段,基于近似环境模型进行值函数的规划学习,并根据模型逼近过程中记录的特征出现频率设定额外奖赏.从理论的角度证明了HDyna-AMR的收敛性.将算法用于扩展的Boyan chain问题和Mountain car问题.实验结果表明,HDyna-AMR在离散状态空间和连续状态空间问题中能学习到最优策略,同时与Dyna-LAPS(Dyna-style planning with linear approximation and prioritized sweeping)和Sarsa(λ)相比,HDyna-AMR具有收敛速度快以及对变化环境的近似模型修正及时的优点.
针对基于查询表的Dyna优化算法在大规模状态空间中收敛速度慢、环境模型难以表征以及对变化环境的学习滞后性等问题,提出一种新的基于近似模型表示的启发式Dyna优化算法(a heuristic Dyna optimization algorithm using approximate model representation, HDyna-AMR),其利用线性函数近似逼近Q值函数,采用梯度下降方法求解最优值函数.HDyna-AMR算法可以分为学习阶段和规划阶段.在学习阶段,利用agent与环境的交互样本近似表示环境模型并记录特征出现频率；在规划阶段,基于近似环境模型进行值函数的规划学习,并根据模型逼近过程中记录的特征出现频率设定额外奖赏.从理论的角度证明了HDyna-AMR的收敛性.将算法用于扩展的Boyan chain问题和Mountain car问题.实验结果表明,HDyna-AMR在离散状态空间和连续状态空间问题中能学习到最优策略,同时与Dyna-LAPS(Dyna-style planning with linear approximation and prioritized sweeping)和Sarsa(λ)相比,HDyna-AMR具有收敛速度快以及对变化环境的近似模型修正及时的优点.
2015, 52(12): 2776-2788.
DOI: 10.7544/issn1000-1239.2015.20140230
摘要：
差分进化(differential evolution， DE)算法简单高效，但其控制参数和差分变异策略对待解的优化问题较为敏感，对问题的依赖性较强.为克服这一缺陷，提出了一种新的基于三角的骨架差分进化算法(bare-bones differential evolution algorithm based on trigonometry, tBBDE)，并使用随机泛函理论分析了算法的收敛性.算法采用了三角高斯变异策略以及三元交叉和交叉概率自适应策略对个体进行更新，并在收敛停滞时进行种群扰动，算法不仅继承了骨架算法无参数的优点，而且还很好地保留了DE算法基于随机个体差异进行的特性.通过对包括单峰函数、多峰函数、偏移函数和高维函数的26个基准测试函数的仿真实验和分析，验证了新算法的有效性和可靠性，经与多种同类的骨架算法以及知名的DE算法在统计学上的分析比较，证明了该算法是一种具有竞争力的新算法.
差分进化(differential evolution， DE)算法简单高效，但其控制参数和差分变异策略对待解的优化问题较为敏感，对问题的依赖性较强.为克服这一缺陷，提出了一种新的基于三角的骨架差分进化算法(bare-bones differential evolution algorithm based on trigonometry, tBBDE)，并使用随机泛函理论分析了算法的收敛性.算法采用了三角高斯变异策略以及三元交叉和交叉概率自适应策略对个体进行更新，并在收敛停滞时进行种群扰动，算法不仅继承了骨架算法无参数的优点，而且还很好地保留了DE算法基于随机个体差异进行的特性.通过对包括单峰函数、多峰函数、偏移函数和高维函数的26个基准测试函数的仿真实验和分析，验证了新算法的有效性和可靠性，经与多种同类的骨架算法以及知名的DE算法在统计学上的分析比较，证明了该算法是一种具有竞争力的新算法.
2015, 52(12): 2789-2801.
DOI: 10.7544/issn1000-1239.2015.20140516
摘要：
频繁序列模式挖掘是数据挖掘领域的1个基本问题,然而模式本身及其支持度计数都有可能泄露用户隐私信息.差分隐私(differential privacy, DP)作为一种新出现的隐私保护技术,定义了一个相当严格的攻击模型,通过添加噪音使数据失真达到隐私保护的目的.由于序列数据内在序列性和高维度的特点,给差分隐私应用于频繁序列模式挖掘带来了挑战.对此提出了一种基于交互式差分隐私保护框架的频繁序列模式挖掘算法Diff-FSPM(differential-privacy frequent sequential pattern mining).该算法利用指数机制获取最优序列长度,并采用一种维规约策略获得原始序列数据集的规约表示,有效降低序列维度的影响;应用前缀树压缩频繁序列模式,利用拉普拉斯机制产生的噪音扰动频繁模式的真实支持度计数,同时采用闭频繁序列模式和Markov假设,有效分配隐私预算,并利用一致性约束后置处理,增强输出模式的可用性.理论角度证明算法满足ε-差分隐私,实验结果验证算法具有较好的可用性.
频繁序列模式挖掘是数据挖掘领域的1个基本问题,然而模式本身及其支持度计数都有可能泄露用户隐私信息.差分隐私(differential privacy, DP)作为一种新出现的隐私保护技术,定义了一个相当严格的攻击模型,通过添加噪音使数据失真达到隐私保护的目的.由于序列数据内在序列性和高维度的特点,给差分隐私应用于频繁序列模式挖掘带来了挑战.对此提出了一种基于交互式差分隐私保护框架的频繁序列模式挖掘算法Diff-FSPM(differential-privacy frequent sequential pattern mining).该算法利用指数机制获取最优序列长度,并采用一种维规约策略获得原始序列数据集的规约表示,有效降低序列维度的影响;应用前缀树压缩频繁序列模式,利用拉普拉斯机制产生的噪音扰动频繁模式的真实支持度计数,同时采用闭频繁序列模式和Markov假设,有效分配隐私预算,并利用一致性约束后置处理,增强输出模式的可用性.理论角度证明算法满足ε-差分隐私,实验结果验证算法具有较好的可用性.
2015, 52(12): 2802-2812.
DOI: 10.7544/issn1000-1239.2015.20140553
摘要：
行为识别在语义分析领域具有很高的学术研究价值和广泛的市场应用前景.为了实现对视频行为的准确描述, 提出了2类构建稠密轨迹运动描述子的方法.1)通过光流约束和聚类，实现对运动区域的稠密采样，以获取行为的局部位置信息;2)选取目标运动角点为特征点，通过对特征点的跟踪获取运动轨迹;3)在以轨迹为中心的视频立方体内，分别构建三维梯度方向直方图(3D histograms of oriented gradients in trajectory centered cube, 3DHOGTCC)描述子和三维光流梯度方向直方图(3D histograms of oriented optical flow gradients, 3DHOOFG)描述子，用以对运动的局部信息进行准确描述.为了充分利用行为发生的场景信息，提出了一种融合动态描述子和静态描述子的行为识别新框架，使得动态特征与静态特征相互融合支撑，即使在摄像头运动等复杂场景下，亦能取得较好的识别效果.在Weizmann和UCF-Sports数据库采用留一交叉验证，在KTH和Youtube数据库采用4折交叉验证.实验证明了提出新框架的有效性.
行为识别在语义分析领域具有很高的学术研究价值和广泛的市场应用前景.为了实现对视频行为的准确描述, 提出了2类构建稠密轨迹运动描述子的方法.1)通过光流约束和聚类，实现对运动区域的稠密采样，以获取行为的局部位置信息;2)选取目标运动角点为特征点，通过对特征点的跟踪获取运动轨迹;3)在以轨迹为中心的视频立方体内，分别构建三维梯度方向直方图(3D histograms of oriented gradients in trajectory centered cube, 3DHOGTCC)描述子和三维光流梯度方向直方图(3D histograms of oriented optical flow gradients, 3DHOOFG)描述子，用以对运动的局部信息进行准确描述.为了充分利用行为发生的场景信息，提出了一种融合动态描述子和静态描述子的行为识别新框架，使得动态特征与静态特征相互融合支撑，即使在摄像头运动等复杂场景下，亦能取得较好的识别效果.在Weizmann和UCF-Sports数据库采用留一交叉验证，在KTH和Youtube数据库采用4折交叉验证.实验证明了提出新框架的有效性.
2015, 52(12): 2813-2823.
DOI: 10.7544/issn1000-1239.2015.20148025
摘要：
为提高约束多目标优化算法的分布性和收敛性，提出一种基于双种群的约束多目标优化算法.首先，改进的Harmonic距离一方面去除了Pareto等级较差个体和较远个体的影响，从而改善可行解集的分布性；另一方面有效减少了计算量，可以提高算法效率.其次，新的不可行解集更新方式与可行解集紧密联系，保留目标函数值和约束违反度同时较优的个体，将有助于产生更优可行解，同时提高了种群的多样性和搜索效率.最后，新的变异策略充分利用最优可行解和优秀不可行解的优良信息来引导种群进化，很好地兼顾了探索和开发能力，进而平衡全局搜索和局部搜索.将提出算法与其他3种优秀的约束多目标进化算法在CTP测试集上进行对比实验，结果表明提出算法相比其他算法具有一定的优势，不仅提升了算法的收敛性能，而且保证了Pareto解集良好的分布性.
为提高约束多目标优化算法的分布性和收敛性，提出一种基于双种群的约束多目标优化算法.首先，改进的Harmonic距离一方面去除了Pareto等级较差个体和较远个体的影响，从而改善可行解集的分布性；另一方面有效减少了计算量，可以提高算法效率.其次，新的不可行解集更新方式与可行解集紧密联系，保留目标函数值和约束违反度同时较优的个体，将有助于产生更优可行解，同时提高了种群的多样性和搜索效率.最后，新的变异策略充分利用最优可行解和优秀不可行解的优良信息来引导种群进化，很好地兼顾了探索和开发能力，进而平衡全局搜索和局部搜索.将提出算法与其他3种优秀的约束多目标进化算法在CTP测试集上进行对比实验，结果表明提出算法相比其他算法具有一定的优势，不仅提升了算法的收敛性能，而且保证了Pareto解集良好的分布性.
2015, 52(12): 2824-2833.
DOI: 10.7544/issn1000-1239.2015.20140801
摘要：
作为经典的NP完全问题之一，子图查询算法近年来在社交网络、生物分子网络等复杂系统分析中引起研究人员的极大关注.结点相似性计算和目标图约简是子图查询算法中提高查询准确率和降低计算复杂性的2种常用手段.针对复杂生物分子网络之间的子图查询问题，提出了一种基于半Markov随机游走的迭代加权子图查询算法.在结点相似性计算中，设计了基于半Markov游走模型的集成结点本身相似性、结构相似性及邻居结点相似性的综合度量方法；同时，在目标图约简过程中，通过迭代递减目标图中低相似性结点，以降低目标图的规模.对多个真实蛋白质网络查询的实验结果表明，算法在精度和时间复杂性方面都有明显提高.
作为经典的NP完全问题之一，子图查询算法近年来在社交网络、生物分子网络等复杂系统分析中引起研究人员的极大关注.结点相似性计算和目标图约简是子图查询算法中提高查询准确率和降低计算复杂性的2种常用手段.针对复杂生物分子网络之间的子图查询问题，提出了一种基于半Markov随机游走的迭代加权子图查询算法.在结点相似性计算中，设计了基于半Markov游走模型的集成结点本身相似性、结构相似性及邻居结点相似性的综合度量方法；同时，在目标图约简过程中，通过迭代递减目标图中低相似性结点，以降低目标图的规模.对多个真实蛋白质网络查询的实验结果表明，算法在精度和时间复杂性方面都有明显提高.
2015, 52(12): 2834-2843.
DOI: 10.7544/issn1000-1239.2015.20131883
摘要：
数据流是随着时间顺序快速变化的和连续的，其包含的知识会随着时间的改变而不同.在一些数据流应用中，通常认为最新的数据具有最大的价值.因此，会采用时间衰减模型来挖掘数据流中的频繁模式.已有的衰减因子设计方式通常具有随机性，使得到的结果集具有不稳定性；或仅考虑算法的高查全率或查准率，而忽略了算法对应的高查准率或查全率.为了平衡算法的高查全率和高查准率同时保证结果集的稳定性，设计了均值衰减因子设置方式.为了更进一步地增加最新事务的权重、减少历史事务的权重，设计了采用高斯函数设置高斯衰减因子的方式.为了比较不同衰减因子设计方式的优劣，研究并设计了4种方式的时间衰减模型，并采用这4种模型挖掘数据流闭合频繁模式.通过对高密度和低密度数据流分别进行频繁挖掘的实验结果分析可以得出，采用均值衰减因子设置方式可以平衡高查全率和高查准率；采用高斯衰减因子设置方式与其他方法相比，可以得到更优的算法性能.
数据流是随着时间顺序快速变化的和连续的，其包含的知识会随着时间的改变而不同.在一些数据流应用中，通常认为最新的数据具有最大的价值.因此，会采用时间衰减模型来挖掘数据流中的频繁模式.已有的衰减因子设计方式通常具有随机性，使得到的结果集具有不稳定性；或仅考虑算法的高查全率或查准率，而忽略了算法对应的高查准率或查全率.为了平衡算法的高查全率和高查准率同时保证结果集的稳定性，设计了均值衰减因子设置方式.为了更进一步地增加最新事务的权重、减少历史事务的权重，设计了采用高斯函数设置高斯衰减因子的方式.为了比较不同衰减因子设计方式的优劣，研究并设计了4种方式的时间衰减模型，并采用这4种模型挖掘数据流闭合频繁模式.通过对高密度和低密度数据流分别进行频繁挖掘的实验结果分析可以得出，采用均值衰减因子设置方式可以平衡高查全率和高查准率；采用高斯衰减因子设置方式与其他方法相比，可以得到更优的算法性能.
2015, 52(12): 2844-2856.
DOI: 10.7544/issn1000-1239.2015.20140598
摘要：
多核处理器已经成为现代处理器的主流体系结构,频繁图挖掘(frequent graph mining)是一个具有很多应用领域的研究热点问题,充分利用多核处理器的能力加速频繁图挖掘过程具有研究意义和实用价值.提出一种基于深度优先遍历的并行挖掘模式,使用任务池维护工作负载,提高数据的时间局部性并减少大量的内存使用;设计缓存敏感的点边数组,连续排列线程的记录数据,减少原始图的数据量,降低缓存缺失率;为了减少锁的竞争,使用灵活的任务获取方法寻找工作任务,采用内存管理队列降低频繁的内存分配释放开销.在模拟数据和真实数据上进行了详细的实验研究和性能分析,结果表明提出的技术能够有效减少内存占用并降低缓存缺失,在具有12个核心的机器上可以达到10倍的加速比.
多核处理器已经成为现代处理器的主流体系结构,频繁图挖掘(frequent graph mining)是一个具有很多应用领域的研究热点问题,充分利用多核处理器的能力加速频繁图挖掘过程具有研究意义和实用价值.提出一种基于深度优先遍历的并行挖掘模式,使用任务池维护工作负载,提高数据的时间局部性并减少大量的内存使用;设计缓存敏感的点边数组,连续排列线程的记录数据,减少原始图的数据量,降低缓存缺失率;为了减少锁的竞争,使用灵活的任务获取方法寻找工作任务,采用内存管理队列降低频繁的内存分配释放开销.在模拟数据和真实数据上进行了详细的实验研究和性能分析,结果表明提出的技术能够有效减少内存占用并降低缓存缺失,在具有12个核心的机器上可以达到10倍的加速比.
2015, 52(12): 2857-2865.
DOI: 10.7544/issn1000-1239.2015.20140685
摘要：
一个近似函数依赖(approximate functional dependency, AFD)是一个几乎成立的函数依赖,目前大部分工作仅限于从一般数据上挖掘近似函数依赖.有时数据是被组织成概率数据的形式,为了从挖掘概率数据中挖掘出可用的近似函数依赖,定义了概率近似函数依赖,它不同于任何一种以往的定义,并给出了在不确定数据中,置信概率的动态规划求解算法,由于动态规划算法复杂度较高,导出了候选依赖的概率下界来进行剪枝,随后给出了基于字典序的挖掘方法以及相应的剪枝策略,最后,在真实和合成的数据集上进行充分的实验,说明了挖掘算法的可扩展性和剪枝策略的高效性,并展示了有趣的挖掘结果.
一个近似函数依赖(approximate functional dependency, AFD)是一个几乎成立的函数依赖,目前大部分工作仅限于从一般数据上挖掘近似函数依赖.有时数据是被组织成概率数据的形式,为了从挖掘概率数据中挖掘出可用的近似函数依赖,定义了概率近似函数依赖,它不同于任何一种以往的定义,并给出了在不确定数据中,置信概率的动态规划求解算法,由于动态规划算法复杂度较高,导出了候选依赖的概率下界来进行剪枝,随后给出了基于字典序的挖掘方法以及相应的剪枝策略,最后,在真实和合成的数据集上进行充分的实验,说明了挖掘算法的可扩展性和剪枝策略的高效性,并展示了有趣的挖掘结果.
2015, 52(12): 2866-2878.
DOI: 10.7544/issn1000-1239.2015.20140634
摘要：
角色动画一直是计算机动画和虚拟现实领域的重要研究内容之一.近年来，随着3D游戏动漫以及电影特效制作产业的蓬勃发展，角色动画对物理真实性的要求日益迫切，基于物理的角色动画合成受到了研究者们越来越多的关注，催生了许多新方法与新技术.该研究问题的核心是人体运动合成方法，其旨在驱动虚拟角色运动，生成满足物理运动规律的动画.重点围绕角色动画合成方法的研究进展进行介绍.首先在对国内外研究工作全面分析与总结的基础上，根据关节力矩的计算方式不同将其分为7类:时空约束法、约束动力学优化法、低维模型法、有限状态机、数据驱动法、动力学过滤法、概率模型法，详细阐述每一类方法的原理及特点后,重点介绍每类方法中近期出现的新工作.其次,对上述各类方法的优缺点进行对照分析.最后,结合实际应用需求,针对目前工作中存在的不足,提出一些可继续深入研究的问题.
角色动画一直是计算机动画和虚拟现实领域的重要研究内容之一.近年来，随着3D游戏动漫以及电影特效制作产业的蓬勃发展，角色动画对物理真实性的要求日益迫切，基于物理的角色动画合成受到了研究者们越来越多的关注，催生了许多新方法与新技术.该研究问题的核心是人体运动合成方法，其旨在驱动虚拟角色运动，生成满足物理运动规律的动画.重点围绕角色动画合成方法的研究进展进行介绍.首先在对国内外研究工作全面分析与总结的基础上，根据关节力矩的计算方式不同将其分为7类:时空约束法、约束动力学优化法、低维模型法、有限状态机、数据驱动法、动力学过滤法、概率模型法，详细阐述每一类方法的原理及特点后,重点介绍每类方法中近期出现的新工作.其次,对上述各类方法的优缺点进行对照分析.最后,结合实际应用需求,针对目前工作中存在的不足,提出一些可继续深入研究的问题.
2015, 52(12): 2879-2887.
DOI: 10.7544/issn1000-1239.2015.20140701
摘要：
关键帧提取是视频处理的重要步骤之一，在视频内容分析中有广泛的应用.针对基于内容的视频分析，为获取高效的视频摘要提出一种视频关键帧提取方法.该方法首先以视频帧为顶点，以顶点之间的连线构造边，利用不同帧的加速鲁棒特征点的豪斯多夫(Hausdorff)距离函数计算边权重，把视频建模成一个无向权重图，然后根据图的支配集理论把视频关键帧提取等价为无向权重图的极小支配集选取问题，进而利用整数线性规划选取图支配集，得到视频关键帧.与传统算法相比，该方法提取的关键帧依赖于视频内容，不受时间和视频镜头约束.实验结果显示，该方法能够体现关键帧的代表性和区分性，具有较高的保真度和压缩率.
关键帧提取是视频处理的重要步骤之一，在视频内容分析中有广泛的应用.针对基于内容的视频分析，为获取高效的视频摘要提出一种视频关键帧提取方法.该方法首先以视频帧为顶点，以顶点之间的连线构造边，利用不同帧的加速鲁棒特征点的豪斯多夫(Hausdorff)距离函数计算边权重，把视频建模成一个无向权重图，然后根据图的支配集理论把视频关键帧提取等价为无向权重图的极小支配集选取问题，进而利用整数线性规划选取图支配集，得到视频关键帧.与传统算法相比，该方法提取的关键帧依赖于视频内容，不受时间和视频镜头约束.实验结果显示，该方法能够体现关键帧的代表性和区分性，具有较高的保真度和压缩率.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
