Some Complexity Results About Packet Radio Networks

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1983
Accession Number
ADA126696

Entities

People

  • Erdal Arikan

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies
  • Space

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Evolutionary Algorithms
  • Flow Rate
  • Geometry
  • Information Systems
  • Line Of Sight
  • Linear Programming
  • Mathematical Programming
  • Network Protocols
  • Network Topology
  • Networks
  • Polynomials
  • Satellite Networks
  • Security
  • Topology
  • Transmitting

Fields of Study

  • Computer science

Readers

  • Operations Research
  • Statistical inference.
  • Tactical Satellite Communications Systems Engineering.