A genetic algorithm for reliability-oriented task assignment with k/spl tilde/ duplications in distributed systems
A genetic algorithm for reliability-oriented task assignment with k/spl tilde/ duplications in distributed systems
复制标题
DOI：
10.1109/tr.2005.863797
复制
发表时间：
2006-03
影响因子：
5.9
通讯作者：
C. Chiu;Chung-Hsien Hsu;Y. Yeh
中科院分区：
文献类型：
--
作者：
C. Chiu;Chung-Hsien Hsu;Y. Yeh
分布式系统是由通信链路连接的处理器-存储器对的集合。分布式系统的可靠性可以用分布式程序可靠性和分布式系统可靠性分析来表示。分布式系统的可靠性计算是一个NP难问题。程序和数据文件的分发会影响系统的可靠性。面向可靠性的任务分配问题是一个NP难问题，即寻找一个使程序可靠性或系统可靠性最大的任务分配。例如，就成功支持的呼叫数量而言，将信道有效地分配给不同的小区可以大大提高整个网络的吞吐量。本文提出了一种基于遗传算法的面向可靠性的任务分配方法（GAROTA），用于计算k/spl tilde/-DTA可靠性问题。该算法使用遗传算法来选择一个程序和文件分配集是最大的，或接近最大的，相对于系统的可靠性。数值结果表明，该算法在大多数情况下都能得到精确解，且计算时间明显短于穷举法.当所提出的方法不能给出精确解时，与精确解的偏差很小。本文提出的技术将有助于读者理解任务分配可靠性与分布式系统拓扑结构之间的关系。
A distributed system is a collection of processor-memory pairs connected by communication links. The reliability of a distributed system can be expressed using the distributed program reliability, and distributed system reliability analysis. The computing reliability of a distributed system is an NP-hard problem. The distribution of programs & data-files can affect the system reliability. The reliability-oriented task assignment problem, which is NP-hard, is to find a task distribution such that the program reliability or system reliability is maximized. For example, efficient allocation of channels to the different cells can greatly improve the overall network throughput, in terms of the number of calls successfully supported. This paper presents a genetic algorithm-based reliability-oriented task assignment methodology (GAROTA) for computing the k/spl tilde/-DTA reliability problem. The proposed algorithm uses a genetic algorithm to select a program & file assignment set that is maximal, or nearly maximal, with respect to system reliability. Our numerical results show that the proposed algorithm may obtain the exact solution in most cases, and the computation time seems to be significantly shorter than that needed for the exhaustive method. When the proposed method fails to give an exact solution, the deviation from the exact solution is very small. The technique presented in this paper would be helpful for readers to understand the correlation between task assignment reliability, and distributed system topology.