Fantastic Data

SAS Medium Access Protocol

Up until now, network protocols have been optimized for either high performance or low power consumption precluding the deployment of large networks of autonomous, battery powered nodes. Fantastic Data's Synchronous/Asynchronous (sas) medium access protocol achieves both goals. The sas protocol rapidly switches from asynchronous, contention service to synchronous, collision free service depending upon data load and criticality. The hybrid approach optimizes for performance when that is critical and for low power consumption when performance is not as important. It is a completely distributed protocol with no special nodes, control points, boundary conditions, or limit on the size of the network. The sas protocol provides the following benefits:

Low power
When there is little or no application data, the sas protocol quickly reconfigures the network neighborhood to a quiescent state. Overhead transmissions such as beacons, are almost non-existent and even receiver usage is less than 0.2% while still providing low latency (< 1s) communication between neighbors.

High efficiency
Intelligent scheduling of the fundamental TDMA architecture provides much higher efficiency than a typical CSMA scheme. Synchronous, fan out slots provide efficient delivery of data to multiple neighbors simultaneously. Within the TDMA structure, individual asynchronous, fan in slots are managed with an adaptive comb algorithm to reduce collisions.  

High reliability
Efficient link level acknowledgements coupled with forward error correction coding ensures message delivery with minimum overhead even in challenging environments. The sophisticated architecture supports multicast message acknowledgement. Inefficient high level retry mechanisms are not required.

Distributed and local control
The sas protocol operates with purely local and completely distributed control. Configuration changes occur quickly because there is no need for messages to travel across the network to or from a controller. There is no limit to the number of nodes in the full mesh network.

Time synchronization
As for any TDMA protocol, time synchronization is required. The sas protocol derives time synchronization from the delivery of data messages. No explicit time beacons are used, saving considerable energy.

Spectrum reuse
The sas protocol makes efficient use of the available spectrum, by employing a number of techniques. These include coordinated time division multiple access (TDMA), dynamic frequency selection (DFS), transmit power control (TPC), and spatial diversity through directional antennas and local reuse. Keyed time slot and frequency hopping provide interference mitigation.

Slot scheduling
The sas protocol implements a time division multiple access (TDMA) scheme with dynamic frequency selection (DFS), transmit power control (TPC), and spatial diversity through the use of directional antennas. The protocol operates by scheduling the use of time slots for a specific purpose. Slot scheduling is fully distributed—any node can schedule a slot at any time based upon its knowledge of the state of the neighboring network, its load, interference statistics, data criticality, and other factors.

Slots may be scheduled for communication to or from a specific node, subset of nodes, or all nodes. Before scheduling a slot, the node checks its knowledge of slot schedules for conflicts. After scheduling a slot, the node informs its neighbors, which then pass the information on to their own neighbors. Slots may be scheduled for transmit or receive and may be scheduled for point-to-point, fan-in (1 receiver from multiple potential transmitters) or fan-out (1 transmitter to multiple receivers) operation. Collision detection and a special comb backoff algorithm manage multiple access on fan-in slots.

Schedule conflicts are rare since the number of slots is far greater than the number required at a particular time. Conflicts are resolved by having one of the conflicted nodes change its schedule. Conflicts occur when 2 nodes in a neighborhood simultaneously schedule the use of the same slot, or more often during network formation when 2 nodes have scheduled the use of the same slot before they become connected. Slots are scheduled with an effective first and last use time and are only used within that time period. Slots scheduled by the transmitter are not used until acknowledged by the intended receiver. Time slots and frequency channels are scrambled on every frame based on a shared key and time of day.

Mode Switching
An asynchronous, fan in, receive slot uses the least energy—only a single receiver is on when there is no data to transmit. A synchronous, fan out, transmit slot to all neighbors uses the most energy since many receivers are on even if no data is transmitted. Conversely, such a receive slot is capable of moving very little data while such a transmit slot is capable of moving a lot of data efficiently and with low latency to many neighboring nodes. The sas protocol switches operation between the types of slots to best meet the current communications needs of the nodes.

The sas protocol may be configured to alter the slot schedule upon a number of types of events. Some events (such as excess load or a high collision rate) are measured within the communication stack, while other events may be generated by application specific code.

By far the most interesting event type for a sensor network is a cue from an external process. The sas protocol reacts to a cue from the surveillance system that sensor data may be forthcoming to produce a broadcast slot. With approximately 1–2 seconds of leadtime, the sas protocol can reconfigure the network neighborhood from a laid-back, barely active state to a state supporting the rapid movement of sensor data.

Network Formation
Operation of a node begins by scheduling some (configuration dependent) fan in, receive slots. Every so often (also configuration dependent), sas formats a message containing its receive slot schedule, and announces this in an unscheduled use of a randomly selected, unused slot. If any neighboring node hears this transmission, it knows how to talk back to the originating node. On subsequent frames it attempts to contact the originating node with a message containing its own slot schedule.

Once two-way communication is established, the nodes exchange other information about themselves and their neighbors, so that both nodes may build knowledge of activities in a neighborhood about themselves. Upon learning of a neighbor of a neighbor, the node attempts to contact that neighbor of a neighbor. This procedure establishes additional links more quickly and more efficiently than the unscheduled search that discovered the first link.

The operation of the SAS protocol is tested and visualized in an emulation environment. The animations illustrate the operation of a network running the SAS protocol in various states.

Hammel, T., Rich, M., Graff, C. Design of a Sensor Protocol Suite for VLSI Implementation. In Military Communications Conference, 2005 (MILCOM 2005) (Atlantic City, NJ, October 20, 2005). IEEE Press, 2005, Vol. 4, 2421-2426. paper presentation

Hammel, T., Rich, M. A higher capability sensor node platform suitable for demanding applications. In Information Processing in Sensor Networks Conference, 2007 (IPSN 2007) (Cambridge, Massachusetts, April 25, 2007). ACM Press, 2007. paper presentation

Sensor Node User's Guide. May 25, 2006. manual


Field Experiment

Network Formation

Busy Network

Quiet Network


Copyright © 2006, 2007 by Fantastic Data. All rights reserved.