Kyung Shik Lim

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 7, No. 2, pp. 426-436, Feb. 2000
10.3745/KIPSTE.2000.7.2.426,   PDF Download:

Abstract

Given a linear arrangement of n base stations which generate multiple types of traffic among themselves, we consider the problem of finding a set of disjoint clusters to cover n base stations so that a cluster is assigned a location server. Our goal is to minimize the total communication cost for the entire network where the cost of intra-cluster communication is usually lower than that of inter-cluster communication for each type of traffic. The optimization problem is transformed into an equivalent problem using the concept of relative cost, which generates the difference of communication costs between intra-cluster and inter-cluster communications. Using the relative cost matrix, an efficient algorithm of , where m is the number of clusters in a partition, is designed by dynamic programming. The algorithm also finds all the valid partitions in the same polynomial time, given the size constraint on a cluster and the total allowable communication cost for the entire network.

Statistics
Cite this article