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.
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 .
@cite_0 @cite_20 @cite_6
2103182676 2171436899 2127380142
We present an improved algorithm to wake up a multi-hop ad-hoc radio network. The goal is to have all the nodes activated, when some of them may wake up spontaneously at arbitrary times and the remaining nodes need to be awoken by the already active ones. The best previously known wake-up algorithm was given by Chrobak, Gasieniec and Kowalski [11], and operated in time O(n5 3 log n), where n is the number of nodes. We give an algorithm with the running time O(n3 2 log n). This also yields better algorithms for other synchronization-type primitives, like leader election and local-clocks synchronization, each with a time performance that differs from that of wake-up by an extra factor of O(log n) only, and improves the best previously known method for the problem by a factor of n1 6. A wake-up algorithm is a schedule of transmissions for each node. It can be represented as a collection of binary sequences. Useful properties of such collections have been abstracted to define a (radio) synchronizer. It has been known that good radio synchronizers exist and previous algorithms [17,11] relied on this. We show how to construct such synchronizers in polynomial time, from suitable constructible expanders. As an application, we obtain a wake-up protocol for a multiple-access channel that activates the network in time O(k2 polylog n), where k is the number of stations that wake up spontaneously, and which can be found in time polynomial in n. We extend the notion of synchronizers to universal synchronizers. We show that there exist universal synchronizers with parameters that guarantee time O(n3 2 log n) of wake-up. In multi-hop ad hoc networks, the efficiency of a medium access control protocol under heavy traffic load depends mainly on its ability to schedule a large number of simultaneous non-interfering transmissions. However, as each node has only a local view of the network, it is difficult to globally synchronize transmission times over the whole network. How does the lack of global coordination affect spatial reuse in multi-hop wireless networks? We show that in a de-centralized network the spatial reuse does not benefit from global clock synchronization. On the contrary, we demonstrate that non-slotted protocols using collision avoidance mechanisms can achieve a higher spatial reuse than the corresponding slotted protocols. By means of a simple backoff mechanism, one can thus favor the spontaneous emergence of spatially dense transmission schedules. Since wireless ad-hoc networks use shared communication medium, accesses to the medium must be coordinated to avoid packet collisions. Transmission scheduling algorithms allocate time slots to the nodes of a network such that if the nodes transmit only during the allocated time slots, no collision occurs. For real-time applications, by ensuring deterministic channel access, transmission scheduling algorithms have the added significance of making guarantees on transmission latency possible. In this paper we present a distributed transmission scheduling algorithm for hexagonal wireless ad-hoc networks with a particular focus on Wireless Sensor Networks. Afforded by the techniques of ad-hoc networks topology control, hexagonal meshes enable trivial addressing and routing protocols. Our transmission scheduling algorithm constructs network-wide conflict-free packet transmission schedule for hexagonal networks, where the overhead of schedule construction in terms of message exchanges is zero above and beyond that for topology control and other network control related functions. Furthermore, the schedule is optimal in the sense that the bottleneck node does not idle. We also present an implicit clock synchronization algorithm to facilitate scheduling. We derive the real time capacity of our scheduling algorithm. We present evaluations of our scheduling algorithm in the presence of topological irregularities using simulation.