Dominance Protocols

In wired networks sporadic messages can be scheduled efficiently using the CAN bus. It has a medium-access control (MAC) protocol which is collision-free and prioritized, and hence it is possible to schedule the bus such that if message characteristics (periods, transmission times, jitter, etc.) are known, then it is possible to compute upper bounds on message delays. This MAC protocol belongs to a family called dominance protocols or binary countdown protocols. The dominance protocol that was implemented in CAN uses open-collector/open drain circuits. Clearly, this does not easily extend to wireless channels. For this reason, researchers in the field recently designed dominance protocols for wireless channels; they are based on modulating priority bits using on-off keying.

Edit

Dominance Protocols in Wireless Networks

We adapt the dominance protocols (used in the CAN bus) to a wireless channel and perform a schedulability analysis. The main idea of our dominance protocol is that a message stream is assigned a static priority and when message streams contend for the channel, they perform a tournament such that the highest-priority message is granted access to the channel.



Edit

Protocol Basics

In the starting state, the protocol waits until the transmission queue is non-empty. Next, the protocol waits for a long idle time and then it transmits a pulse of the carrier wave. The beginning of the pulse represents a common reference point in time for all nodes. A node dequeues the highest priority message and then nodes perform a tournament. If a node wins the tournament, it transmits the message. If a node loses the tournament, it continues to listen on the channel to figure out which priority was the winner and receives the message.



Image



Edit

The Tournament

The tournament is performed bit-by-bit, starting with the most significant bit. A bit is assigned a time interval. If a node contends with a dominant bit then a carrier wave is transmitted in this time interval; if the node contends with a recessive bit, it transmits nothing but listens. This makes it possible for a node with a recessive bit to detect that another node has transmitted a dominant bit, and hence the node with the recessive bit withdraws.



Image

Edit

Implementation Aspects

Due to non-idealities in transceivers and the nature of the wireless medium, it is not obvious how these protocols should be implemented. There exist priority levels for which the protocols need to switch between transmit and receive modes for every priority bit, and this is potentially wasteful because many transceivers are not designed for frequent switching and hence every switching takes non-negligible time. It is well known that wireless channels typically have significantly higher noise levels than wired channels and that detection of pulses of short duration is difficult. For this reason, wireless communication systems often use long codes and/or spread spectrum modulation to increase the probability of a correctly received message. Unfortunately, these techniques cannot be used to transmit priority bits in the protocols: (i) long codes operate on message-level and this is too coarse; (ii) there is the need to demodulate and decode an individual bit so that a decision can be made whether the next priority bit should be transmitted. Spread spectrum modulation cannot be used on priority bits because it requires nodes that attempt to detect the priority bits are accurately synchronized with the senders: there are many senders and they can all send a priority bit at approximately the same time so a node trying to receive the priority bit cannot be synchronized with all of the senders. This makes it non-obvious whether wireless dominance protocols could work.

We implement one of the proposed dominance protocols and we call the implementation WiDOM.