Page History: Overview
Compare Page Revisions
Page Revision: 2007/05/25 17:40
A prioritized Medium Access Control (MAC) grants the right to access to
the computer node with the highest priority.
Such a protocol was originally created for wireline networks; Controller
Area Networks (CAN) is the most known one
and it is currently deployed in 700 million units.
We are tranferring this idea to the wireless domain and exploring this
idea to solve problems in real-time communication
and collaborative distributed computing (wireless/line sensor networks
and cyber-physical systems).
The study prioritized MAC protocols has triggered a number of research activities, namely:
- A prioritized MAC protocol for single broadcast domains (SBD), named WiDOM-SBD;
- A prioritized MAC protocol for multiple broadcast domains (SBD), named WiDOM-MBD;
- A prioritized MAC protocol for wireless networks that that offers several channels;
- Efficient computation of aggregated quantities (such as MIN, MAX) of sensor readings;
- Dissemination of data when the topology is unknown;
- Exploiting the multi-channel capability together with a prioritized MAC protocol.
These are briefly overviewed below.
§§§EditSectionPlaceHolder§§§WiDOM-SBD
WiDom is a prioritized MAC protocol for wireless networks. It is an adaptation of 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.
Protocol Overview
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
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.
§§§EditSectionPlaceHolder§§§WiDOM-MBD
We propose a wireless medium access control (MAC) protocol that provides static-priority scheduling of messages in a guaranteed collision-free manner. Our protocol supports multiple broadcast domains, resolves the wireless hidden terminal problem and allows for parallel transmissions across a mesh network. Arbitration of messages is achieved without the notion of a master coordinating node, global clock synchronization or out-of-band signalling. The protocol relies on bit-dominance similar to what is used in the CAN bus except that in order to operate on a wireless physical layer, nodes are not required to receive incoming bits while transmitting. The use of bit-dominance efficiently allows for a much larger number of priorities than would be possible using existing wireless solutions. A MAC protocol with these properties enables schedulability analysis of sporadic message streams in wireless multihop networks.
§§§EditSectionPlaceHolder§§§WiDOM-MC
We are exploring the development of a simple globally prioritized multi-channel medium access control (MAC) protocol for wireless networks. Such protocol should provide “hard” pre-run-time real-time guarantees to sporadic message streams, exploit a very large fraction of the capacity of all channels for “hard” real-time traffic and also fully utilize the channels with non real-time traffic when hard real-time messages do not request to be transmitted.
§§§EditSectionPlaceHolder§§§Data Aggregation
We consider a network where nodes take sensor readings, but individual sensor
readings are not the most important pieces of data
in the system. Instead, we are interested in aggregated
quantities of the sensor readings such as minimum
and maximum values, the number of nodes and
the median among a set of sensor readings on different
nodes. We exploit a prioritized medium
access control (MAC) protocol to efficiently compute aggregated quantities
of sensor readings. We aim at developing distributed algorithms that have a very low time-and
message-complexity for computing certain aggregated
quantities.
If every sensor
node knows its geographical location, then sensor
data can be interpolated with our novel distributed algorithm,
and the message-complexity of the algorithm
is independent of the number of nodes. Such an interpolation
of sensor data can be used to compute any
desired function; for example the temperature gradient
in a room (e.g., industrial plant) densely populated
with sensor nodes, or the gas concentration gradient
within a pipeline or traffic tunnel.
§§§EditSectionPlaceHolder§§§Data Dissemination
A prioritized MAC protocol can be used to efficiently disseminate data when the topology is unknown.
We study the problem of disseminating data from an arbitrary source node to all other nodes in a distributed computer system. We assume that nodes do not know the topology and that wireless broadcast is used. We propose new protocols which propagate data faster and uses fewer broadcasts.
§§§EditSectionPlaceHolder§§§WISHES
We are exploring how to use multi-channel capability
together with a prioritized MAC protocol to deal with the well-known hidden node problem.