text: This paper introduces a protocol that distributively constructs a collision-free schedule for multi-hop packet radio networks in the presence of hidden terminals. As a preliminary step, each wireless station computes the schedule length after gathering information about the number of flows in its neighbourhood. Then, a combination of deterministic and random backoffs are used to reach a collision-free schedule. A deterministic backoff is used after successful transmissions and a random backoff is used otherwise. It is explained that the short acknowledgement control packets can easily result in channel time fragmentation and, to avoid this, the use of link layer delayed acknowledgements is advocated and implemented. The performance results show that a collision-free protocol easily outperforms a collision-prone protocol such as Aloha. The time that is required for the network to converge to a collision-free schedule is assessed by means of simulation.
  @cite_28: It is shown that the decision problem regarding the membership of a point in the capacity region of a packet radio network is nondeterministic polynomial time hard (NP hard). The capacity region is the set of all feasible origin-to-destination message rates where feasibility is defined as the existence of any set of rules for moving the data through the network so that the desired rates are satisfied.
summary: To further complicate the issue, wireless propagation introduces an additional degree of randomness and unpredictability to the network. In order to advance in the analysis of multi-hop packet radio networks, some simplifications are in order. One of the most common modeling assumptions is the use of a graph representation of the network, where an edge exists between two stations if they are in the transmission range of each other. As an example, @cite_28 uses a graph representation to show that determining whether a traffic matrix belongs to the capacity region of a packet radio network is NP hard. We will use the graph topology representation and several other assumptions in the present paper.