非服从性分布式系统中博弈分析法下的副本放置问题  

Replica Placement Analysis Under Game Theory in Non-Obedient Distributed System

作　　者：宋玮[1] 凌捷[1] 

机构地区：[1]广东工业大学计算机学院,广州510006

出　　处：《桂林理工大学学报》2013年第1期164-173,共10页Journal of Guilin University of Technology

基　　金：国家科技支撑计划项目(2012BAH27F05);广东省自然科学基金博士启动项目(S2012040007439);广东省教育部产学研合作项目(2011A090200068);广东省现代信息服务业发展专项基金项目(110394);广东工业大学校青年基金(082018);广东工业大学校博士启动基金(103052)

摘　　要：为解决非服从性分布式系统中多数据、多节点、有容量限制的副本放置问题,建立了副本放置模型以及向博弈模型的映射,分析了在无容量限制及有容量限制下纳什均衡的存在性问题以及纳什均衡的优化程度。考虑到纳什均衡获取的时间不可行,提出了无删除副本放置局面的定义,设计了该局面的获取算法并分析算法的相关性质。模拟实验显示了无删除副本放置局面获取算法下系统平均副本数和总代价随节点的容量及放置代价变化的过程,同时在小节点规模下与最优副本放置结果进行比较,结果显示纳什均衡带来的系统总代价不会与最优系统总代价有大的差别,说明在保证个体利益最大化时,全局的效益并不会有大的损害。To solve the replica placement with multi-data and multi-node in non-obedient distributed system,the replica placement model is established and is reflected in game model.In replica placement game model,the existence of Nash equilibrium is discussed under situations with or without capacity restriction.Then price of anarchy（PoA） is also analyzed.To avoid the time infeasibility in Nash equilibrium obtaining,replica placement without deletion is defined,obtaining algorithm is presented and analyzed.Simulations show the relations among capacity,placement cost,system average number of replicas and system total cost during the algorithm executing process.Meanwhile,in small scale,total cost caused by Nash equilibrium threr is not much difference between total cost caused by optimal solution and,indicating that when individual utility is maximized,the global utility is not damaged greatly.

关 键 词：非服从性分布式系统 博弈理论 无删除副本放置 纳什均衡 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]