Some Complexity Results About Packet Radio Networks
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS
Pagination or Media Count:
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.
- Radio Communications