Accession Number:

ADA160127

Title:

Minimizing the Number of Clusters in Mobile Packet Radio Networks

Descriptive Note:

Master's thesis

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s):

Report Date:

1985-10-01

Pagination or Media Count:

87.0

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.

Subject Categories:

  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE