树形数据网格中实现副本放置的一种优化算法  

Optimal algorithm of replica placement in tree data grid

作　　者：周飞菲[1] Zhou Feifei(School of Information Engineering,Zhengzhou Sheng Da University of Economics,Business&Management,Zhengzhou 451191,China)

机构地区：[1]郑州升达经贸管理学院信息工程学院,郑州451191

出　　处：《电子测量与仪器学报》2019年第2期195-202,共8页Journal of Electronic Measurement and Instrumentation

基　　金：2018年度河南省科技攻关重点研发与推广项目(182102210139)资助

摘　　要：针对树形数据网格这种分布式分层数据网格模型,提出了一种最佳副本放置算法,其中的副本数量k可以由用户指定。算法实现由2个阶段构成.在阶段1,对二叉树的全部节点以反向广度优先顺序被访问,且基于对象i的一个副本是否被放置在一个节点上,以自底向上的方式计算出包含读取成本和存储成本的总复制成本;在阶段2,基于一个递归过程,把由在阶段1计算得到的读取成本和存储成本作为输入,采取自上而下的过程放置副本,以使总复制成本最小化。理论分析和仿真实验结果表明,最佳副本放置算法不仅有较低的时间复杂度,而且在归一化放置成本、有效网络利用和本地访问百分比性能指标方面都优于目前几种典型的副本放置算法。Aiming at the distributed hierarchical data grid model as tree data grid,an optimal replica placement algorithm is proposed in this paper,in which the number of replicas is k,which is specified by the user.The proposed algorithm consists of two phases.In phase 1,all nodes of binary tree are visited in reverse breadth-first order,and based on whether a replica of object i is placed on a node or not,the total replication cost including both read and storage cost are calculated in a bottom up manner.In phase 2,based on a recursive process,the read cost and the storage cost calculated in phase 1 are used as input,and replicas are placed using top down procedure in order to minimize the total replication cost.Theoretical analysis and simulation results show that the optimal replica placement algorithm proposed in this paper not only has the lower time complexity,but also outperforms several typical replica placement algorithms at present in terms of the normalized placement cost,effective network usage and percentage of local access.

关 键 词：树形数据网格 副本放置 复制成本 成本最小化 有效网络利用 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]