Background: Pulse Coupled Oscillators

Reins-MAC builds on the literature of Pulse Coupled Oscillators (PCOs), which is inspired by firefly behavior. Each beetle periodically emits a light. Other fireflies observe these flashes and alter the timing of their own flashes, eventually yielding a unison blinking of the whole swarm. Formally, the periodic behavior can be described as a cyclic oscillator manifest as a phase variable that (i) assumes a value in a given range, e.g., [0,1), (ii) increases linearly over time and (iii) resets to the first limit when the second is reached. To mimic the flash of a firefly, resetting the phase variable can be combined with a pulse that is essentially a notification of the reset.

In fireflies, periodic pulsing and observing others is not sufficient to produce synchrony. This coupling is achieved by either actively anticipating or delaying the individual pulse. Mathematically, this means that the phase variable of a firefly is no longer a constant, linear function over time, but it exhibits spontaneous changes in response to observations. The rules driving these changes are captured in a coupling function that establishes the phase variable at which the flash will occur in the next oscillation round.

A distributed problem that can be reduced to the PCO scheme is pulse scattering, whose goal is to obtain pulsing schedules where all the nodes that can hear each others beating are evenly spread throughout the oscillation period. A simple but effective solution is to distance the local pulse as much as possible from the surrounding ones; this is achieved by placing the beating almost exactly in the middle between two adjacent perceived pulses.

Reins-MAC TDMA Scheduling

Slot Allocation. We approach slot size selection and slot allocation by noting the similarity between this communication problem and that of pulse scattering. Consider the simple case when all nodes are within communication range. Nodes spread their pulses evenly throughout the frame, and if a transmission slot for a specific node is defined to begin at the moment at which it pulses and end when the next node pulses, a TDMA schedule emerges. Consider directly applying such an algorithm in a multi-hop network. While node C in Figure 1 will scatter with respect to both A and D, because A and D are not within range, they do not scatter with respect to one another and their slots may overlap. Simultaneous transmissions from A and D will overlap, causing collisions at C, as shown in Figure 2. This issue is solved by applying pulse scattering with a horizon of 2 hops as shown in Figure 3. When the node's own pulse fires, it can transmit; when a 1-hop distant pulse is received, the node listens for incoming transmissions; when a 2-hop distant pulse is expected the node sleeps to save energy, as no communication involving it is possible.

Politely Join the Schedule. We first recall that no synchronization is required in the solution presented above. In fact, a node wanting to join the system can trivially learn the current communication schedule by listening to the pulsing of its neighbors, and independently decide the best placement of its own pulse. However, this solution does not avoid collisions with ongoing communication. Therefore, we adopt the approach employed in classic TDMA solutions, allocating a coordination slot, common to all schedules. Augmenting our MAC-solution with such a synchronized slot is trivial: we simply require nodes to pulse twice. One pulse is controlled by the scattering equation as defined previously, while the other is updated according to a synchronization coupling function, e.g., align the local pulse to the average of the heard pulses. Notification of both pulses is combined and transmitted at the beginning of the assigned transmission slot. The synchronized pulse identifies a small, fixed size slot, shown as a shaded region in Figure 4, during which all nodes must listen, and any node can transmit using a simple contention-based access approach. For a node to join the schedule, it transmits in the control slot a deferred pulse indicating its preferred location in the schedule. All nodes incorporate the pulses indicated in the control messages into their schedules, and after a stabilization period, the new node can begin to transmit without disrupting ongoing communications.

QoS Provisioning in Reins-MAC

Latency Control. In the scheduling solution described thus far, the sequence of node pulses is fixed. This sequence affects latency, therefore enabling changes in the sequence of node pulses is the key to support latency constraints. Our solution is simply for a node to remove itself from the schedule, then re-enter the schedule at its desired location, using the control slot described previously. This is shown in Figure 5 as node C removes itself from its original location between A and B, and uses the control slot to announce its new, desired position between nodes D and B.

Bandwidth Reservation. The bandwidth available to each node is constrained to its own slot size. Therefore, Reins-MAC allows each node to increase the single, assigned slot to the size requested at run-time. To accomplish this, we give the pulse a duration in time, delimiting the beginning and end of the pulse with guarding phases, spread equal distance from the center of the pulse. This guarding phases act as actual pulses for the other nodes in the schedule, which scatter accordingly, as described for slot allocation. As depicted in Figure 6, by extending the pulse duration of C to begin at the first guard and end at the second, the slots of A and B shift, leaving a slot that provides the requested bandwidth guarantee to C. In the example, the total reserved duration must be less than the distance between A and B, as placing the guards beyond these limits results in incorrect pulse scattering.


Fig 1: Network topology


Fig 2: 1-hop scattering at A


Fig 3: 2-hop scattering at A


Fig 4: Polite joining of N


Fig 5: Reordering


Fig 6: Guarding bandwidth