Multi-Access in Packet Radio Networks

摘要

A PRN (packet radio network) is a collection of geographically distributed, possibly mobile users where each user is capable of transmitting and receiving messages over a shared broadcast medium. In a PRN, messages are divided into packets, which may be fixed or variable in length, and each packet is transmitted through the network individually. Packets are assembled at their destinations to reconstruct the original messages. The data traffic in a PRN is characterized by specifying the average message arrival rates to the network for each o-d (origin-destination) pair. A set of o-d rates is called feasible if there exist network protocols under which the number of packets in the network still not delivered to their destinations remains finite with probability one. The capacity region of a PRN is defined to be the set of all feasible sets of o-d rates. In this thesis, PRNs are studied from the viewpoint of feasibility, i.e., we take an arbitrary set of message input rates as given and try to determine if it is feasible. Our main conclusion is that, unless P = NP, there exists no practical algorithm for characterizing the capacity region of a PRN, in the sense that the decision problem regarding the feasibility of a given set of o-d rates in NP-complete. (Author)