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_0: Algorithms for transmission scheduling in multihop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance, scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. It is shown that tree networks can be scheduled optimally and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network thickness times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree times optimum. Since the thickness is typically several orders of magnitude less than the maximum node degree, the algorithms presented represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods. >
  @cite_20: Accurately synchronized clocks are crucial for many applications in sensor networks. Existing time synchronization algorithms provide on average good synchronization between arbitrary nodes, however, as we show in this paper, close-by nodes in a network may be synchronized poorly. We propose the Gradient Time Synchronization Protocol (GTSP) which is designed to provide accurately synchronized clocks between neighbors. GTSP works in a completely decentralized fashion: Every node periodically broadcasts its time information. Synchronization messages received from direct neighbors are used to calibrate the logical clock. The algorithm requires neither a tree topology nor a reference node, which makes it robust against link and node failures. The protocol is implemented on the Mica2 platform using TinyOS. We present an evaluation of GTSP on a 20-node testbed setup and simulations on larger network topologies.
  @cite_6: Aggregate traffic loads and topology in multihop wireless networks may vary slowly, permitting MAC protocols to "learn" how to spatially coordinate and adapt contention patterns. Such an approach could reduce contention, leading to better throughput. To that end, we propose a family of MAC scheduling algorithms and demonstrate general conditions, which, if satisfied, ensure lattice rate optimality (i.e., achieving any rate-point on a uniform discrete lattice within the throughput region). This general framework enables the design of MAC protocols that meet various objectives and conditions. In this paper, as instances of such a lattice-rate-optimal family, we propose distributed, synchronous contention-based scheduling algorithms that: 1) are lattice-rate-optimal under both the signal-to-interference-plus-noise ratio (SINR)-based and graph-based interference models; 2) do not require node location information; and 3) only require three-stage RTS CTS message exchanges for contention signaling. Thus, the protocols are amenable to simple implementation and may be robust to network dynamics such as topology and load changes. Finally, we propose a heuristic, which also belongs to the proposed lattice-rate-optimal family of protocols and achieves faster convergence, leading to a better transient throughput.
summary: Our goal is that the different stations of the network settle down in a satisfactory transmission schedule that efficiently uses the radio resources. In @cite_0 the problem is treated from a theoretical perspective in which the network topology is known and the schedule can be constructed in a centralized way. An interesting alternative is considered in @cite_6 were contention MAC protocols are proposed in which the stations learn from their neighbourhood. These two works rely on a slotted channel access, which means that neighbouring stations need to have closely synchronized clocks. The problem of gradient clock synchronization is treated in @cite_20 .