Minimizing the Number of Clusters in Mobile Packet Radio Networks

摘要

Linked-Cluster Architectures have been suggested in the literature for organizing the radios of a stationless mobile Packet Radio Network (PRN). Existing algorithms for achieving such architectures do not attempt to minimize the number of clusters and gateway nodes, aims which we claim are essential to the implementation of any Multiple Access scheme. The problem is formulated on graphs in 3 different ways, all of which are NP-complete. It is also shown that epsilon-Polynomial Time Algorithms are not likely to exist. A simple centralized heuristic, Greedy is analyzed in terms of its worst case fractional error. It is then argued that no efficient heuristic is likely to be significantly better in terms of worst-case performance. Two Distributed Linked-Cluster Algorithms are presented.