Minimizing the Number of Clusters in Mobile Packet Radio Networks
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1985
- Accession Number
- ADA160127
Entities
People
- Abhay K. Parekh
Organizations
- Massachusetts Institute of Technology