2017年 第54卷 第2期
摘要：
科学数据是科研活动的输入、输出和资产，是科研人员对其所研究的客观对象相关现象的描述。以大规模巡天望远镜、大型粒子加速器、高通量基因测序仪等为代表的新一代观测与实验装置源源不断产生巨量科学数据，将科学研究推入一个前所未有的大数据时代。这将改变人类几个世纪以来主要研究和理解相对简单、未耦合或弱耦合系统这一局面，大大增强我们详细表征和描述复杂性能力，以及分析高度耦合复杂系统动态行为的能力。可见，科学大数据管理与分析能力及水平，成为了未来在分秒必争的重大科学发现中能否胜出的关键。来自于天文学、生命科学、高能物理等应用领域的迫切需求，也正在挑战着当今所有数据管理系统的极限，成为当下科学界和数据管理领域需携手攻坚的难题。2017年《计算机研究与发展》以科学大数据为专题，结合科学大数据的特点和典型应用需求，重点关注科学大数据管理理论与方法、关键技术与系统，以及各应用领域的最新进展等。本期专题经过公开征稿，总计收到40篇论文投稿，最终收录了5篇论文，内容涉及科学大数据管理基本理论与关键技术，天文大数据、高能物理大数据、遥感大数据等领域大数据管理需求与实践，科学数据众包服务等主题。这些文章为相关领域的研究者探讨科学大数据理论基础及应用、讨论最新的突破性进展、交流新的学术思想和新方法，以及展望未来的发展趋势，提供了很好的交流机会。
科学数据是科研活动的输入、输出和资产，是科研人员对其所研究的客观对象相关现象的描述。以大规模巡天望远镜、大型粒子加速器、高通量基因测序仪等为代表的新一代观测与实验装置源源不断产生巨量科学数据，将科学研究推入一个前所未有的大数据时代。这将改变人类几个世纪以来主要研究和理解相对简单、未耦合或弱耦合系统这一局面，大大增强我们详细表征和描述复杂性能力，以及分析高度耦合复杂系统动态行为的能力。可见，科学大数据管理与分析能力及水平，成为了未来在分秒必争的重大科学发现中能否胜出的关键。来自于天文学、生命科学、高能物理等应用领域的迫切需求，也正在挑战着当今所有数据管理系统的极限，成为当下科学界和数据管理领域需携手攻坚的难题。2017年《计算机研究与发展》以科学大数据为专题，结合科学大数据的特点和典型应用需求，重点关注科学大数据管理理论与方法、关键技术与系统，以及各应用领域的最新进展等。本期专题经过公开征稿，总计收到40篇论文投稿，最终收录了5篇论文，内容涉及科学大数据管理基本理论与关键技术，天文大数据、高能物理大数据、遥感大数据等领域大数据管理需求与实践，科学数据众包服务等主题。这些文章为相关领域的研究者探讨科学大数据理论基础及应用、讨论最新的突破性进展、交流新的学术思想和新方法，以及展望未来的发展趋势，提供了很好的交流机会。
2017, 54(2): 235-247.
DOI: 10.7544/issn1000-1239.2017.20160847
摘要：
近年来，随着越来越多的大科学装置的建设和重大科学实验的开展，科学研究进入到一个前所未有的大数据时代.大数据时代科学研究是一个大科学、大需求、大数据、大计算、大发现的过程，研发一个支持科学大数据全生命周期的数据管理系统具有重要的意义.分析了研发科学大数据管理系统的背景，阐述了科学大数据的概念和三大特征，通过对科学数据资源发展和科学数据管理系统的研究进展进行综述分析，提出了满足科学数据管理全生命周期的科学大数据管理框架，并从数据融合、数据实时分析、长期存储、云服务体系以及数据开放共享机制5个方面分析了科学大数据管理系统中的关键技术.最后，结合科学研究领域展望了科学大数据管理系统的应用前景.
近年来，随着越来越多的大科学装置的建设和重大科学实验的开展，科学研究进入到一个前所未有的大数据时代.大数据时代科学研究是一个大科学、大需求、大数据、大计算、大发现的过程，研发一个支持科学大数据全生命周期的数据管理系统具有重要的意义.分析了研发科学大数据管理系统的背景，阐述了科学大数据的概念和三大特征，通过对科学数据资源发展和科学数据管理系统的研究进展进行综述分析，提出了满足科学数据管理全生命周期的科学大数据管理框架，并从数据融合、数据实时分析、长期存储、云服务体系以及数据开放共享机制5个方面分析了科学大数据管理系统中的关键技术.最后，结合科学研究领域展望了科学大数据管理系统的应用前景.
2017, 54(2): 248-257.
DOI: 10.7544/issn1000-1239.2017.20170005
摘要：
超大型天文观测技术的出现不仅能够让研究人员观测到新的天文现象，更能用于验证已有物理模型的正确性.这些最新天文成果的发现是建立在海量天文数据的近乎实时产生、管理与分析的基础上，因此给目前的数据管理系统带来了新的挑战.以我国自主研发的地基广角相机阵(the ground-based wide-angle camera array, GWAC)天文望远镜为例，15s的采样和处理周期都处于短时标观测领域的世界前列，但却对数据管理系统提出了很多问题,包括多镜头并行输出数据管理、实时瞬变源发现、当前观测夜数据的秒级查询、数据持久化和快速离线查询等.基于上述问题，设计了分布式GWAC数据模拟生成器用于模拟真实GWAC数据产生场景，并基于产生的数据特性，提出一种两级缓存架构，使用本地内存解决多镜头并行输出、实时瞬变源发现，使用分布式共享内存实现秒级查询.为了平衡持久化和查询效率，设计一种星表簇结构将整个星表数据划分后聚集存储.根据天文需求特点，设计基于索引表的查询引擎能从缓存和星表簇以较小的代价对星表数据查询.通过实验验证，当前方案能够满足GWAC的需求.
超大型天文观测技术的出现不仅能够让研究人员观测到新的天文现象，更能用于验证已有物理模型的正确性.这些最新天文成果的发现是建立在海量天文数据的近乎实时产生、管理与分析的基础上，因此给目前的数据管理系统带来了新的挑战.以我国自主研发的地基广角相机阵(the ground-based wide-angle camera array, GWAC)天文望远镜为例，15s的采样和处理周期都处于短时标观测领域的世界前列，但却对数据管理系统提出了很多问题,包括多镜头并行输出数据管理、实时瞬变源发现、当前观测夜数据的秒级查询、数据持久化和快速离线查询等.基于上述问题，设计了分布式GWAC数据模拟生成器用于模拟真实GWAC数据产生场景，并基于产生的数据特性，提出一种两级缓存架构，使用本地内存解决多镜头并行输出、实时瞬变源发现，使用分布式共享内存实现秒级查询.为了平衡持久化和查询效率，设计一种星表簇结构将整个星表数据划分后聚集存储.根据天文需求特点，设计基于索引表的查询引擎能从缓存和星表簇以较小的代价对星表数据查询.通过实验验证，当前方案能够满足GWAC的需求.
2017, 54(2): 258-266.
DOI: 10.7544/issn1000-1239.2017.20160939
摘要：
新一代高能物理实验装置的建成与运行，产生了PB乃至EB量级的数据，这对数据采集、存储、传输与共享、分析与处理等数据管理技术提出了巨大挑战.事例是高能物理实验的基本数据单元，一次大型实验即可产生万亿级的事例.传统高能物理数据处理以ROOT文件为基本存储和处理单位，每个ROOT文件可以包含数千至数亿个事例.这种基于文件的处理方式虽然降低了高能物理数据管理系统的开发难度，但物理分析仅对极少量的稀有事例感兴趣，这导致了数据传输量大、I/O瓶颈以及数据处理效率低等问题.提出一种面向事例的高能物理数据管理方法，重点研究海量事例特征高效索引技术.在这种方法中，将物理学家感兴趣的事例的特征量抽取出来建立专门的索引，存储在NoSQL数据库中.为便于物理分析处理，事例的原始数据仍然存放在ROOT文件中.最后，通过系统验证和分析表明，基于事例特征索引进行事例筛选是可行的，优化后的HBase系统可以满足事例索引的需求.
新一代高能物理实验装置的建成与运行，产生了PB乃至EB量级的数据，这对数据采集、存储、传输与共享、分析与处理等数据管理技术提出了巨大挑战.事例是高能物理实验的基本数据单元，一次大型实验即可产生万亿级的事例.传统高能物理数据处理以ROOT文件为基本存储和处理单位，每个ROOT文件可以包含数千至数亿个事例.这种基于文件的处理方式虽然降低了高能物理数据管理系统的开发难度，但物理分析仅对极少量的稀有事例感兴趣，这导致了数据传输量大、I/O瓶颈以及数据处理效率低等问题.提出一种面向事例的高能物理数据管理方法，重点研究海量事例特征高效索引技术.在这种方法中，将物理学家感兴趣的事例的特征量抽取出来建立专门的索引，存储在NoSQL数据库中.为便于物理分析处理，事例的原始数据仍然存放在ROOT文件中.最后，通过系统验证和分析表明，基于事例特征索引进行事例筛选是可行的，优化后的HBase系统可以满足事例索引的需求.
2017, 54(2): 267-283.
DOI: 10.7544/issn1000-1239.2017.20160837
摘要：
随着遥感技术的不断进步，遥感数据的数据量越来越大，种类越来越多，分布越来越分散，遥感应用的复杂程度和个性化程度也不断提高，遥感正在走向大数据时代.而目前遥感数据基础设施在容量、可扩展性、易用性和性能等方面都难以满足遥感应用的需求，成为了遥感科学与工程从获取到最终产品这个流程中的瓶颈.为此，首先从遥感数据的本质出发，讨论了遥感数据基础设施应当具备的分布、异构、时空连续和按需数据处理等特性，并依据遥感数据基础设施的基本服务单元、分布性、时空连续性和按需处理支持能力将遥感数据基础设施分成6类.其次，针对这6类遥感数据基础设施展现出的特性，设计了实现这些基础设施可以采用的体系结构，并指出了其中实现的技术难点和解决思路.最后，就遥感数据基础设施设计和实现过程中涉及到的数据收集与整合、数据组织与管理、数据服务接口、按需数据处理等方面的技术方案进行了深入的讨论.在这些技术的支持下，遥感数据基础设施能够做到分布化、智能化和平台化，支持遥感科学的合作研究和工程上的协同应用.
随着遥感技术的不断进步，遥感数据的数据量越来越大，种类越来越多，分布越来越分散，遥感应用的复杂程度和个性化程度也不断提高，遥感正在走向大数据时代.而目前遥感数据基础设施在容量、可扩展性、易用性和性能等方面都难以满足遥感应用的需求，成为了遥感科学与工程从获取到最终产品这个流程中的瓶颈.为此，首先从遥感数据的本质出发，讨论了遥感数据基础设施应当具备的分布、异构、时空连续和按需数据处理等特性，并依据遥感数据基础设施的基本服务单元、分布性、时空连续性和按需处理支持能力将遥感数据基础设施分成6类.其次，针对这6类遥感数据基础设施展现出的特性，设计了实现这些基础设施可以采用的体系结构，并指出了其中实现的技术难点和解决思路.最后，就遥感数据基础设施设计和实现过程中涉及到的数据收集与整合、数据组织与管理、数据服务接口、按需数据处理等方面的技术方案进行了深入的讨论.在这些技术的支持下，遥感数据基础设施能够做到分布化、智能化和平台化，支持遥感科学的合作研究和工程上的协同应用.
2017, 54(2): 284-294.
DOI: 10.7544/issn1000-1239.2017.20160850
摘要：
获取科学数据的最终目的是根据具体需要从数据中提取有用的知识，并将这些知识应用到具体的领域中，帮助决策制定者制定决策.由于科学数据规模越来越大，而且呈现结构复杂的特点，如半结构化或非结构化，难以通过计算机实现自动化处理.众包通过高效调用人力资源，成为进行科学大数据众包处理的解决方案之一.针对科学大数据众包处理的特点，围绕人才筛选机制、任务处理模式和结果评估策略3方面对科学数据众包体系进行研究，并通过地理空间数据云平台开展地学领域的基于众包的遥感影像信息提取实验.研究表明，科学数据不仅能够通过众包模式来进行处理，而且通过合理的设计众包流程能够获得高质量的数据结果.
获取科学数据的最终目的是根据具体需要从数据中提取有用的知识，并将这些知识应用到具体的领域中，帮助决策制定者制定决策.由于科学数据规模越来越大，而且呈现结构复杂的特点，如半结构化或非结构化，难以通过计算机实现自动化处理.众包通过高效调用人力资源，成为进行科学大数据众包处理的解决方案之一.针对科学大数据众包处理的特点，围绕人才筛选机制、任务处理模式和结果评估策略3方面对科学数据众包体系进行研究，并通过地理空间数据云平台开展地学领域的基于众包的遥感影像信息提取实验.研究表明，科学数据不仅能够通过众包模式来进行处理，而且通过合理的设计众包流程能够获得高质量的数据结果.
2017, 54(2): 295-304.
DOI: 10.7544/issn1000-1239.2017.20150751
摘要：
现有的大部分可检索加密方案建立的安全索引面临着统计攻击的威胁.为了抵抗统计攻击，部分方案设计出关键词/文档一一对应的陷门，以检索时多次的陷门计算为代价保证安全性，但是这样又导致检索速度过于慢而无法接受.为此，研究了针对密文的安全检索方案，在克服已有方案缺点的同时保证对于统计攻击的安全性.该方案使用Bloom过滤器为文档的关键词构造索引.为了确保检索效率，对于相同的关键词构造唯一对应的陷门.通过增加伪造的文档索引，并且在索引中进行插值来确保每个关键词在文档集合中出现的次数相似，从而达到语义安全并且能够抵抗统计攻击.在实现中，对索引进行倒排进一步提高检索效率.证明了本方案的安全性，且采用实验验证了其有效性和高效性.
现有的大部分可检索加密方案建立的安全索引面临着统计攻击的威胁.为了抵抗统计攻击，部分方案设计出关键词/文档一一对应的陷门，以检索时多次的陷门计算为代价保证安全性，但是这样又导致检索速度过于慢而无法接受.为此，研究了针对密文的安全检索方案，在克服已有方案缺点的同时保证对于统计攻击的安全性.该方案使用Bloom过滤器为文档的关键词构造索引.为了确保检索效率，对于相同的关键词构造唯一对应的陷门.通过增加伪造的文档索引，并且在索引中进行插值来确保每个关键词在文档集合中出现的次数相似，从而达到语义安全并且能够抵抗统计攻击.在实现中，对索引进行倒排进一步提高检索效率.证明了本方案的安全性，且采用实验验证了其有效性和高效性.
2017, 54(2): 305-312.
DOI: 10.7544/issn1000-1239.2017.20150887
摘要：
可验证加密签名(verifiably encrypted signature, VES)能够有效地保证互联网上交易过程的公平性.VES的核心思想是：签名者利用仲裁者的公钥对自己所签发的一个普通数字签名进行加密，随后证明密文中确实包含一个普通签名，任何验证者都可以利用仲裁者的公钥来验证其真实性，但在没有签名者或仲裁者的帮助下无法从中提取出普通签名；当争议发生时，验证者可以要求仲裁者从可验证加密签名中恢复出签名者的普通签名.利用Agrawal等人在美密2010上给出的固定维数的格基委派技术、格上原像抽样算法和差错学习问题的非交互零知识证明，该文构造出一个新的格上可验证加密签名方案，并在随机预言机模型下严格证明了其安全性.与已有的可验证加密签名方案相比，该方案要求签名者根据仲裁者公钥生成签名者公私钥对，构造简单，公私钥和签名尺寸更短，效率更高，并且能够抵抗量子攻击.
可验证加密签名(verifiably encrypted signature, VES)能够有效地保证互联网上交易过程的公平性.VES的核心思想是：签名者利用仲裁者的公钥对自己所签发的一个普通数字签名进行加密，随后证明密文中确实包含一个普通签名，任何验证者都可以利用仲裁者的公钥来验证其真实性，但在没有签名者或仲裁者的帮助下无法从中提取出普通签名；当争议发生时，验证者可以要求仲裁者从可验证加密签名中恢复出签名者的普通签名.利用Agrawal等人在美密2010上给出的固定维数的格基委派技术、格上原像抽样算法和差错学习问题的非交互零知识证明，该文构造出一个新的格上可验证加密签名方案，并在随机预言机模型下严格证明了其安全性.与已有的可验证加密签名方案相比，该方案要求签名者根据仲裁者公钥生成签名者公私钥对，构造简单，公私钥和签名尺寸更短，效率更高，并且能够抵抗量子攻击.
2017, 54(2): 313-327.
DOI: 10.7544/issn1000-1239.2017.20150928
摘要：
隐私泄露是当前Android安全中最为重要的问题之一，目前检测隐私泄露的最主要方法是污点分析.Android静态污点分析技术凭借其代码覆盖率高、漏报率低的特点而被广泛应用在Android应用隐私泄露的检测上.然而，现有的静态污点分析工具却不能对Android动态加载和反射机制进行有效污点分析.鉴于当前Android动态加载和反射机制被越来越广泛地应用的现状，对如何使Android静态污点分析工具有效地处理Android应用的动态加载和反射机制的问题进行了研究.对Android源码进行了修改，使Android系统能够对Android应用实际运行中加载的dex文件和反射调用信息进行实时存储，并利用这些信息对Android静态污点分析过程进行引导.以当前领先的静态污点分析工具FlowDroid为基础，对其进行了改进，提出了使用非反射调用语句替换反射调用语句的策略，实现了一个能够对Android动态加载和反射机制进行有效污点分析的工具——DyLoadDroid，并通过实验验证了其在处理Android动态加载和反射机制的污点分析问题上的有效性.
隐私泄露是当前Android安全中最为重要的问题之一，目前检测隐私泄露的最主要方法是污点分析.Android静态污点分析技术凭借其代码覆盖率高、漏报率低的特点而被广泛应用在Android应用隐私泄露的检测上.然而，现有的静态污点分析工具却不能对Android动态加载和反射机制进行有效污点分析.鉴于当前Android动态加载和反射机制被越来越广泛地应用的现状，对如何使Android静态污点分析工具有效地处理Android应用的动态加载和反射机制的问题进行了研究.对Android源码进行了修改，使Android系统能够对Android应用实际运行中加载的dex文件和反射调用信息进行实时存储，并利用这些信息对Android静态污点分析过程进行引导.以当前领先的静态污点分析工具FlowDroid为基础，对其进行了改进，提出了使用非反射调用语句替换反射调用语句的策略，实现了一个能够对Android动态加载和反射机制进行有效污点分析的工具——DyLoadDroid，并通过实验验证了其在处理Android动态加载和反射机制的污点分析问题上的有效性.
2017, 54(2): 328-337.
DOI: 10.7544/issn1000-1239.2017.20150925
摘要：
提出一种时间约束条件下的分层访问控制方案.根据用户对感知节点资源的访问控制需求，充分考虑感知节点计算、存储能力受限且节点数海量的特点，从用户掌握密钥数、密钥获取时间和产生公共信息数3方面进行优化设计，以实现高效、安全的分层访问控制. 与现有其他方案对比，该方案的优势在于：1)用户对大量感知节点资源进行的一次访问，仅需要掌握单个密钥材料；2)通过优化设计，使用户访问节点资源密钥的获取时间与产生的公共信息数达到最佳平衡；3)提出的方案是可证明安全的.
提出一种时间约束条件下的分层访问控制方案.根据用户对感知节点资源的访问控制需求，充分考虑感知节点计算、存储能力受限且节点数海量的特点，从用户掌握密钥数、密钥获取时间和产生公共信息数3方面进行优化设计，以实现高效、安全的分层访问控制. 与现有其他方案对比，该方案的优势在于：1)用户对大量感知节点资源进行的一次访问，仅需要掌握单个密钥材料；2)通过优化设计，使用户访问节点资源密钥的获取时间与产生的公共信息数达到最佳平衡；3)提出的方案是可证明安全的.
2017, 54(2): 338-347.
DOI: 10.7544/issn1000-1239.2017.20150993
摘要：
针对Android应用程序的安全性问题，提出一种基于模糊测试方法的组件通信鲁棒性测试方案.首先构造测试集和测试用例，随后将测试用例发送给目标应用程序并收集测试数据，最后对测试数据进行分析.依据测试方案设计并实现了模糊测试工具FuzzerAPP，进而对常用应用程序进行鲁棒性测试.通过对测试数据的分析，发现发送特殊Intent可以导致应用程序的崩溃，甚至引发系统服务的级联崩溃.此外，发现测试集中多款应用程序存在测试模块暴露的问题，可能会导致隐私泄露、拒绝服务等严重安全问题.最后，通过与其他工具的对比，表明测试方法的有效性和测试工具的实用性.
针对Android应用程序的安全性问题，提出一种基于模糊测试方法的组件通信鲁棒性测试方案.首先构造测试集和测试用例，随后将测试用例发送给目标应用程序并收集测试数据，最后对测试数据进行分析.依据测试方案设计并实现了模糊测试工具FuzzerAPP，进而对常用应用程序进行鲁棒性测试.通过对测试数据的分析，发现发送特殊Intent可以导致应用程序的崩溃，甚至引发系统服务的级联崩溃.此外，发现测试集中多款应用程序存在测试模块暴露的问题，可能会导致隐私泄露、拒绝服务等严重安全问题.最后，通过与其他工具的对比，表明测试方法的有效性和测试工具的实用性.
2017, 54(2): 348-360.
DOI: 10.7544/issn1000-1239.2017.20151125
摘要：
围绕多关键字的模糊匹配和数据安全性保障问题,展开对多关键字模糊搜索方法的研究,提出一种面向多关键字的模糊密文搜索方案.该方案以布隆过滤器(Bloom filter)为基础,使用对偶编码函数和位置敏感Hash函数来对文件索引进行构建,并使用距离可恢复加密算法对该索引进行加密,实现了对多关键字的密文模糊搜索.同时方案不需要提前设置索引存储空间,从而大大降低了搜索的复杂度.除此之外,该方案与已有方案相比不需要预定义字典库,降低了存储开销.实验分析和安全分析表明,该方案不仅能够实现面向多关键字的密文模糊搜索,而且保证了方案的机密性和隐私性.
围绕多关键字的模糊匹配和数据安全性保障问题,展开对多关键字模糊搜索方法的研究,提出一种面向多关键字的模糊密文搜索方案.该方案以布隆过滤器(Bloom filter)为基础,使用对偶编码函数和位置敏感Hash函数来对文件索引进行构建,并使用距离可恢复加密算法对该索引进行加密,实现了对多关键字的密文模糊搜索.同时方案不需要提前设置索引存储空间,从而大大降低了搜索的复杂度.除此之外,该方案与已有方案相比不需要预定义字典库,降低了存储开销.实验分析和安全分析表明,该方案不仅能够实现面向多关键字的密文模糊搜索,而且保证了方案的机密性和隐私性.
2017, 54(2): 361-368.
DOI: 10.7544/issn1000-1239.2017.20150819
摘要：
在社交网络中，挖掘高影响力的信息传播者，对微博服务中内容的流行度分析和预测是非常有价值的任务.与众多相关方法相比，k-shell分解(k-core)方法因其简洁高效、平均性能好的特点吸引了越来越多的研究人员的兴趣.但是，目前k-shell方法着重考虑节点在网络中的位置因素，而忽略了话题在信息传播中的影响.因此，为了利用用户历史数据中蕴含的话题对消息的传播概率进行细粒度的建模，提出了一种话题敏感的k-shell(topic-sensitive k-shell， tsk-shell)分解算法.在真实Twitter数据集上实验表明，在发现top k高影响力传播者任务中，tsk-shell比k-shell的性能平均提高了约40%，证明了tsk-shell算法的有效性.
在社交网络中，挖掘高影响力的信息传播者，对微博服务中内容的流行度分析和预测是非常有价值的任务.与众多相关方法相比，k-shell分解(k-core)方法因其简洁高效、平均性能好的特点吸引了越来越多的研究人员的兴趣.但是，目前k-shell方法着重考虑节点在网络中的位置因素，而忽略了话题在信息传播中的影响.因此，为了利用用户历史数据中蕴含的话题对消息的传播概率进行细粒度的建模，提出了一种话题敏感的k-shell(topic-sensitive k-shell， tsk-shell)分解算法.在真实Twitter数据集上实验表明，在发现top k高影响力传播者任务中，tsk-shell比k-shell的性能平均提高了约40%，证明了tsk-shell算法的有效性.
2017, 54(2): 369-381.
DOI: 10.7544/issn1000-1239.2017.20151020
摘要：
基于延迟容忍特征，移动社会网络采用“存储—运载—转发”模式在节点之间进行消息传输.如何选定合适的中继节点进行消息的高效传输是当前研究中备受关注的热点问题.从不同的角度对网络中的多维社会特征展开分析.首先，根据节点间的交互关系，确定节点间社会关系模型；其次，依据网络拓扑给出了邻居集合和本地社区的定义，提出了一种移动社会网络的本地社区划分方法，进而建立了节点间的社区关系；然后，基于节点间的行为特征给出了节点活跃度定义，通过PageRank算法获得节点的多维属性特征PR值，并利用PR值给出节点间传输值，从而获得节点的不同传输效用值.在此基础之上，综合考虑节点社区关系和节点的不同传输效用值，设计并实现了移动社会网络的消息传输算法.实验表明，算法在传输成功率、传输冗余率、平均延时等多个方面具有优势.
基于延迟容忍特征，移动社会网络采用“存储—运载—转发”模式在节点之间进行消息传输.如何选定合适的中继节点进行消息的高效传输是当前研究中备受关注的热点问题.从不同的角度对网络中的多维社会特征展开分析.首先，根据节点间的交互关系，确定节点间社会关系模型；其次，依据网络拓扑给出了邻居集合和本地社区的定义，提出了一种移动社会网络的本地社区划分方法，进而建立了节点间的社区关系；然后，基于节点间的行为特征给出了节点活跃度定义，通过PageRank算法获得节点的多维属性特征PR值，并利用PR值给出节点间传输值，从而获得节点的不同传输效用值.在此基础之上，综合考虑节点社区关系和节点的不同传输效用值，设计并实现了移动社会网络的消息传输算法.实验表明，算法在传输成功率、传输冗余率、平均延时等多个方面具有优势.
2017, 54(2): 382-393.
DOI: 10.7544/issn1000-1239.2017.20151118
摘要：
基于时延约束的影响力最大化问题(influence maximization with time-delay constraint, IMTC)定义为在时延约束条件下，选取网络中一部分初始用户，使得影响力传播过程结束后网络中被成功影响的用户数量最多.现有研究工作主要依据网络结构优化影响力传播模型，或改进启发式算法提高初始节点的选取质量，影响力传播过程中的时间延迟特性及时延约束条件往往被忽略.针对这点不足，基于时延约束的信用分布模型(credit distribution with time-delay constraint model, CDTC)综合考虑见面概率和条件激活概率对信用分配进行优化定义，同时将相邻节点之间不断见面并激活对信用分配的阻碍作用映射到传播增量路径中，最后根据信用分布函数，使用基于时延约束的贪心算法GA-TC，递归选取边际收益最大的节点组成初始节点集合.实验结果表明：在CDTC模型上使用GA-TC算法不仅能够保证初始节点的选取质量，而且具有更高的执行效率及更好的行为执行预测能力.
基于时延约束的影响力最大化问题(influence maximization with time-delay constraint, IMTC)定义为在时延约束条件下，选取网络中一部分初始用户，使得影响力传播过程结束后网络中被成功影响的用户数量最多.现有研究工作主要依据网络结构优化影响力传播模型，或改进启发式算法提高初始节点的选取质量，影响力传播过程中的时间延迟特性及时延约束条件往往被忽略.针对这点不足，基于时延约束的信用分布模型(credit distribution with time-delay constraint model, CDTC)综合考虑见面概率和条件激活概率对信用分配进行优化定义，同时将相邻节点之间不断见面并激活对信用分配的阻碍作用映射到传播增量路径中，最后根据信用分布函数，使用基于时延约束的贪心算法GA-TC，递归选取边际收益最大的节点组成初始节点集合.实验结果表明：在CDTC模型上使用GA-TC算法不仅能够保证初始节点的选取质量，而且具有更高的执行效率及更好的行为执行预测能力.
2017, 54(2): 394-404.
DOI: 10.7544/issn1000-1239.2017.20150788
摘要：
随着带有GPS定位功能的智能手机越来越普遍，人们喜欢分享他们的地理位置或者通过评论某个地方的商品从而留下用户的足迹，这引发了以共同的兴趣点(POIs)为中心，基于地理位置信息的社交网络研究(location based social network, LBSN).社交网络中的一类典型应用是推荐系统，而推荐系统中最常见的问题是冷启动，即在用户很少点评商家或分享评论时如何为他推荐感兴趣的商家.为解决冷启动问题，提出了一种在社交网络中基于兴趣圈的社会关系挖掘推荐算法.兴趣圈是由所有访问某一类别商品的用户群及他们之间的社会关系构成的社交联系，不同的用户访问同一类别商品表明他们对此类别具有相似兴趣.该方法在传统矩阵分解模型的基础上考虑不同的兴趣圈上的社会关系，使用的社会关系包括朋友关系(显性关系)和相关专家(隐性关系)，并用它们作为规则化项来优化矩阵分解模型.实验数据集来自第5届Yelp挑战赛和自己爬取的Foursquare数据集，提出的方法与已有模型进行了充分的实验对比分析，结果表明，我们的模型特别是在解决冷启动问题方面优于多种现有的方法.
随着带有GPS定位功能的智能手机越来越普遍，人们喜欢分享他们的地理位置或者通过评论某个地方的商品从而留下用户的足迹，这引发了以共同的兴趣点(POIs)为中心，基于地理位置信息的社交网络研究(location based social network, LBSN).社交网络中的一类典型应用是推荐系统，而推荐系统中最常见的问题是冷启动，即在用户很少点评商家或分享评论时如何为他推荐感兴趣的商家.为解决冷启动问题，提出了一种在社交网络中基于兴趣圈的社会关系挖掘推荐算法.兴趣圈是由所有访问某一类别商品的用户群及他们之间的社会关系构成的社交联系，不同的用户访问同一类别商品表明他们对此类别具有相似兴趣.该方法在传统矩阵分解模型的基础上考虑不同的兴趣圈上的社会关系，使用的社会关系包括朋友关系(显性关系)和相关专家(隐性关系)，并用它们作为规则化项来优化矩阵分解模型.实验数据集来自第5届Yelp挑战赛和自己爬取的Foursquare数据集，提出的方法与已有模型进行了充分的实验对比分析，结果表明，我们的模型特别是在解决冷启动问题方面优于多种现有的方法.
2017, 54(2): 405-414.
DOI: 10.7544/issn1000-1239.2017.20150822
摘要：
虽然目前旅游者可以利用Web搜索引擎来选择旅游景点，但往往难以获得较好符合自身需要的旅游规划.而旅游推荐系统是解决上述问题的有效方式.一个好的旅游推荐模型应具有个性化并能考虑用户时间和费用的限制.调研表明，用户在选择旅游景点时，目的地与用户常居地的距离常常是一个需要考虑的问题.因为旅行距离往往可以间接地反映了时间和费用的影响.于是，在贝叶斯模型和概率矩阵分解模型的基础上，提出一个旅行距离敏感的旅游推荐模型(geographical probabilistic matrix factorization, GeoPMF).主要思想是基于每个用户的旅游历史，推算出一个最偏好的旅游距离，并作为一种权重,添加到传统的基于概率矩阵分解的推荐模型中.在携程网站的旅游数据集上的实验表明，与基准方法相比，GeoPMF 的RMSE(root mean square error)可以降低近10%；与传统概率矩阵分解模型(PMF)相比，通过考虑距离因子，RMSE平均降幅近3.5%.
虽然目前旅游者可以利用Web搜索引擎来选择旅游景点，但往往难以获得较好符合自身需要的旅游规划.而旅游推荐系统是解决上述问题的有效方式.一个好的旅游推荐模型应具有个性化并能考虑用户时间和费用的限制.调研表明，用户在选择旅游景点时，目的地与用户常居地的距离常常是一个需要考虑的问题.因为旅行距离往往可以间接地反映了时间和费用的影响.于是，在贝叶斯模型和概率矩阵分解模型的基础上，提出一个旅行距离敏感的旅游推荐模型(geographical probabilistic matrix factorization, GeoPMF).主要思想是基于每个用户的旅游历史，推算出一个最偏好的旅游距离，并作为一种权重,添加到传统的基于概率矩阵分解的推荐模型中.在携程网站的旅游数据集上的实验表明，与基准方法相比，GeoPMF 的RMSE(root mean square error)可以降低近10%；与传统概率矩阵分解模型(PMF)相比，通过考虑距离因子，RMSE平均降幅近3.5%.
2017, 54(2): 415-427.
DOI: 10.7544/issn1000-1239.2017.20160491
摘要：
视频广告作为新兴互联网广告的一个重要的分支，为广告商带来巨大的收益，目前对于视频广告的拍卖方式主要采用关键字拍卖中的广义第二价格拍卖机制.但由于视频广告的时间可分性，使得视频广告与关键字拍卖内在上成为2个不同的问题.针对这些问题，主要工作如下：1)定义在线视频广告的形式化模型.该模型是有公共预算限制和私有价格信息的异质多物品拍卖模型，且该模型不限制竞价者的收益函数分布.2)前期工作已经证明了不同时存在具有个体理性、激励相容性和帕累托最优性质的预算约束拍卖的确定性机制.所以针对视频广告拍卖问题，基于预算约束的嵌钉拍卖基础，提出不限制竞拍者Agent的边际效益形式且满足激励相容性、个体理性激励相容的随机机制.3)定性及定量分析了该机制的收益性质.通过定义分配因子和支配因子证明了该机制收益的下界，并通过针对不同分布的收益函数和预算约束的实验，在系统收益和社会效用2个指标上验证了该机制的有效性.
视频广告作为新兴互联网广告的一个重要的分支，为广告商带来巨大的收益，目前对于视频广告的拍卖方式主要采用关键字拍卖中的广义第二价格拍卖机制.但由于视频广告的时间可分性，使得视频广告与关键字拍卖内在上成为2个不同的问题.针对这些问题，主要工作如下：1)定义在线视频广告的形式化模型.该模型是有公共预算限制和私有价格信息的异质多物品拍卖模型，且该模型不限制竞价者的收益函数分布.2)前期工作已经证明了不同时存在具有个体理性、激励相容性和帕累托最优性质的预算约束拍卖的确定性机制.所以针对视频广告拍卖问题，基于预算约束的嵌钉拍卖基础，提出不限制竞拍者Agent的边际效益形式且满足激励相容性、个体理性激励相容的随机机制.3)定性及定量分析了该机制的收益性质.通过定义分配因子和支配因子证明了该机制收益的下界，并通过针对不同分布的收益函数和预算约束的实验，在系统收益和社会效用2个指标上验证了该机制的有效性.
2017, 54(2): 428-445.
DOI: 10.7544/issn1000-1239.2017.20150701
摘要：
针对现有动态死锁规避方法存在能力有限、被动盲目、开销较大和影响目标程序正确性等问题，提出一种基于未来锁集的动静结合死锁规避方案Flider.基本思想是，对于一个加锁操作，若其未来锁集中的所有锁都是空闲的，则执行该加锁操作不会导致死锁.一个加锁操作的未来锁集包括当前要加锁的锁和从该加锁操作到与之相对应的解锁操作过程中遇到的所有加锁操作所要加的锁.通过静态分析，计算锁效应信息并插桩到相应的加锁操作和函数调用操作前后.通过动态分析，劫持加锁操作，根据其锁效应信息为之计算未来锁集，只有当未来锁集中的所有锁都未被锁定才执行该加锁操作，否则等待.测评实验和对比实验表明Flider能智能主动地规避多种类型死锁，开销较小，扩展性好，不影响程序正确性.
针对现有动态死锁规避方法存在能力有限、被动盲目、开销较大和影响目标程序正确性等问题，提出一种基于未来锁集的动静结合死锁规避方案Flider.基本思想是，对于一个加锁操作，若其未来锁集中的所有锁都是空闲的，则执行该加锁操作不会导致死锁.一个加锁操作的未来锁集包括当前要加锁的锁和从该加锁操作到与之相对应的解锁操作过程中遇到的所有加锁操作所要加的锁.通过静态分析，计算锁效应信息并插桩到相应的加锁操作和函数调用操作前后.通过动态分析，劫持加锁操作，根据其锁效应信息为之计算未来锁集，只有当未来锁集中的所有锁都未被锁定才执行该加锁操作，否则等待.测评实验和对比实验表明Flider能智能主动地规避多种类型死锁，开销较小，扩展性好，不影响程序正确性.
2017, 54(2): 446-456.
DOI: 10.7544/issn1000-1239.2017.20151123
摘要：
绿色云计算已经成为一个研究焦点，动态整合虚拟机和关闭空闲主机是极具潜力的途径可降低云计算数据中心的能耗.当云平台的负载迅速增加时，系统需要启动更多的主机和创建更多的虚拟机来扩展可用资源.然而，启动主机和创建虚拟机需要一定的时间开销，使得紧急任务难以及时开始，从而延误了截止期.为了解决以上问题，首先提出具有机器启动时间感知的虚拟机扩展策略，以缓解机器启动时间冲击实时任务的时效性要求.基于该策略，设计算法STARS来调度实时任务和资源，以在保障任务时效性与节能2方面进行权横.最后，使用Google的负载数据进行模拟实验，比较算法STARS与其他2个算法的性能.实验结果表明，在保障任务时效性、节能和资源利用率方面，算法STARS优于对比算法.
绿色云计算已经成为一个研究焦点，动态整合虚拟机和关闭空闲主机是极具潜力的途径可降低云计算数据中心的能耗.当云平台的负载迅速增加时，系统需要启动更多的主机和创建更多的虚拟机来扩展可用资源.然而，启动主机和创建虚拟机需要一定的时间开销，使得紧急任务难以及时开始，从而延误了截止期.为了解决以上问题，首先提出具有机器启动时间感知的虚拟机扩展策略，以缓解机器启动时间冲击实时任务的时效性要求.基于该策略，设计算法STARS来调度实时任务和资源，以在保障任务时效性与节能2方面进行权横.最后，使用Google的负载数据进行模拟实验，比较算法STARS与其他2个算法的性能.实验结果表明，在保障任务时效性、节能和资源利用率方面，算法STARS优于对比算法.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
