Accession Number:

ADA126696

Title:

Some Complexity Results About Packet Radio Networks

Descriptive Note:

Technical rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s):

Report Date:

1983-03-01

Pagination or Media Count:

29.0

Abstract:

It is shown that the decision problem regarding the membership of a given point in the capacity region of a packet radio network PRN is NP- complete. The capacity region is the set of all feasible sets of average origin- to-destination traffic rates, where the feasibility is defined as the existence of any set of rules deterministic or non-deterministic for moving the data through the network so that the desired rates are satisfied. The analysis includes a linear programming formulation of TDMA time-division-multi-access schemes for PRNs and NP-completeness results for some other related problems. Implicit in the analysis is the optimality of TDMA schemes in terms of achieving a given set of link traffic rates.

Subject Categories:

  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE