计算机科学技术

师雪霖，徐恪

计算机科学技术

云虚拟机资源分配的效用最大化模型

师雪霖，徐恪

随着云计算和虚拟化技术的发展，为云资源管理提供了一种更高层次的调度选择：一个作业不再只能分配到一台物理机上，而是可将一台或多台物理机的计算资源虚拟化成一台虚拟机来运行该作业。根据作业需要，高效分配定量的物理资源放置虚拟机，是决定云系统性能的关键因素，即云资源调度问题实质就是一个虚拟机和物理机之间的映射问题。文中借鉴网络效用最大化模型，提出了一种云资源调度模型——云效用最大化（Cloud Utility Maximization，XUM）模型，与传统调度模型相比，目标函数不再是最小化最大完工时间，而是以达到效用最大为调度目标，可以充分提高用户的满意程度。通过求解CUM优化问题得到最优的虚拟机和物理机映射关系。设计了针对该模型的分解优化算法——简化次梯度算法求解拉格朗日对偶问题，证明了该算法可以获得原始模型问题的最优解。仿真实验表明算法可行且具有良好的收敛特性，并给出了CUM模型在真实云环境下的应用场景。在云环境中，不仅资源的地理位置分布广泛，甚至属于不同的自治系统，而且资源往往具有异构性、动态性，如何有效分配计算资源是决定整个云性能、效率的关键问题。因此，随着云计算技术的日益普及，有效的云资源调度模型和算法将成为高效利用这些资源的关键。由于云计算模式从提出伊始即考虑到其商业实现，所以从经济效用度量的调度模型更具意义。本文提出的云资源CUM调度模型，和以往0-1整数规划的调度方法不同，利用计算机网络中NUM模型思路，实现了对物理机计算资源的更高层次分配：以效用最大为调度目标，一台或多台物理机资源如同网络链路的带宽一样，通过虚拟化技术分配给一个或多个作业。此外给出了该模型的优化算法，通过简化的次梯度算法求解该模型的拉格朗日对偶问题。通过模拟实验表明，算法具有可行性和260计算机学报2013年较好的收敛性。

来源出版物：计算机学报, 2013, 36(2): 252-262

入选年份：2014

基于云模型的信任评估方法研究

张仕斌，许春香

摘要：复杂的网络环境下存在的随机性、模糊性和不可预测性等不确定性因素给网络交易带来了诸多安全问题，而在网络交易中，信任是交易能够顺利进行的前提和关键。文中以复杂的网络环境为研究背景，通过对复杂的网络环境中信任、信任影响因素及信任机制等问题的研究，引入云模型理论，研究并提出了基于云模型的信任评估方法，实现了信任的定性与定量的转换，客观地反映了信任的随机性、模糊性和不可预测性；为了有效地防止不法分子的信用炒作和欺骗行为，文中提出了特殊属性评价方法和信任惩罚方法。通过仿真实验，验证了文中研究的信任评估方法能够对复杂的网络环境中实体的信任做出合理的评价；通过防信用炒作实验和防周期行骗实验，进一步验证了基于云模型的信任评估方法的可行性和合理性，为复杂的网络环境中信任评估的研究提供了有价值的新思路。在复杂的网络环境中有许多不确定因素（随机性、模糊性和不可预测性等）都会对用户的信任产生一定影响，而在网络交易（例如电子商务交易）中，只有在交易双方相互信任的情况下，交易才有可能顺利地进行下去，所以信任是进行交易活动的前提和关键。本文以复杂的网络环境为研究背景，引入云模型理论和借鉴已有工作，研究并提出了针对复杂的网络环境下的基于云模型的信任评估方法；通过模拟实际场景进行仿真实验，进一步验证了基于云模型的信任评估方法的可行性和合理性。目前，尽管我们在信任评估方面进行了一些研究，取得了一些阶段性的成果，但是有很多技术还停留在实验室中，距离推广还有很多实际问题需要进一步研究解决；除此之外，研究如何防范具有信任诋毁的信任评估模型也是下一步主要研究的工作。使用本文所研究的基于云模型的信任评估方法，可以使具有欺骗行为的卖家的信任值陡降，这也证明了基于云模型的信任评估方法能有效地防止具有欺骗行为的买家，同时也进一步说明本文研究的基于云模型的信任评估方法的可行性和合理性。

来源出版物：计算机学报, 2013, 36(2): 422-431

入选年份：2014

社交网络的结构支撑理论

韩毅，许进，方滨兴，等

摘要：社交网络分析是近年来的研究热点之一，常见的分析方法包括度分布分析、个体排名、社区发现、模式发现等。本文中，我们认为一个人的社会地位与其所在的网络结构具有紧密的联系，而这种网络结构对成员社会地位的影响程度是可以被表示和量化的。通过分析社交网络的链接结构，将社交网络中个体与个体间的依赖关系从一般社会关系中抽取出来，提出了一种基于依赖模型的支持力衡量方法，并基于此给出了一种高效的计算最具支持力的节点计算方法。此外，基于上述模型，设计了一种基于依赖关系的支撑结构模型及其计算方法，用于刻画社交网络中特定节点的影响力来源。我们在大规模的真实数据环境下对模型和算法的正确性、效率和伸缩性进行了验证。在社交网络全面进入人们生活的同时，也可以发现微博等社交网络上虚假谣言信息盛行、网络推手和欺诈活动猖獗、甚至针对社交网络的蓄意的煽动破坏等现象也给正常的互联网社会活动带来了有害的影响。本文在分析了社交网络中节点影响力度量函数及其相互影响的基础上，给出了社交网络上依赖模型、支持力和支撑社区的定义、性质和计算方法，实验结果证明了本文的模型和方法是正确且高效的。社交网络上的结构支撑理论分析具有广泛的应用前景，例如，例如，在在线社交网站上，通过分析节点在结构中的支持力，可以综合分析其承载的舆情信息的传播能力，从而可以进行商业推广，或进行舆论导向等研究。在Web结构上，对于一个给定节点，必定会有一组节点共同组成其支持社团，通过分析支持社团的互联结构，可以有效地识别人为构造的网络链接垃圾结构等。在线社交网络是一个异质复杂网络，在社交网络的结构支撑理论方面，下一步可以将本文的工作进一步深化，研究社交网络中内容和结构的互依赖和支持关系，必将具有良好的研究前景。此外，如何利用网络大数据管理系统对本文提出的算法进行优化，也是一个下一步值得研究的问题。

来源出版物：计算机学报, 2014, 37(4): 905-914

入选年份：2014