Flooded Time Syncrhonization Protocol implementaiton on PsoC CY3209 boards

Kiran Bhagwat , Suman Kasam

CSE 237B FINAL PROJECT REPORT

Abstract:

Flooded Time Synchronization Protocol (FTSP) is a wireless time syncrhonization protocol used in wireless sensor networks (WSN) to syncrhonize the slave nodes to the global master node. We have implemented this protocol on PsoC CY3209 boards using Artaflex radios. We have done a comparative study of our implementation vs the FTSP implementatation using Berkeley Mica2 motes running TinyOS. We believe our implementation using Artaflex radios and without OS comapred to Zigbee implmentation and running TinyOS would give better performance.

Introduction:

Wireless sensor networks are becoming increasingly popular and realize vast variety of applications. The computing power combined with integration of several sensors onto tiny devices deployed as wireless sensor nodes can serve multitude of functions ranging from weather monitoring, remote study of biological eco-systems to wireless audio applications, military applications. These nodes have typically have a low power, low MIPS processor, have extremely tight resource constarints in terms of memory, power consumption and run on batteries or are solar charged and are expected to run from a few months to a few years without being physically attended to. Many distributed applications running on WSNs need precise syncrhonization of the clocks among all nodes to have a consistent view of the global time. Each node runs on its own local clock and sends (receives) packets to (from) other nodes at sampling rate of its own clock. Also, to conserve the power, the nodes can enter the sleep mode after sending/receiving the packet and wakeup just before its time for another packet. If the clocks are not syncrhonized, the nodes can miss the packets sent by other nodes. As an alternative, the slave can have a guard time added to their wakeup time to remain active longer before going into sleep mode. This however increases the power consumption. So its imperative that the nodes maintain accurate time with respect to the global clock.

The three basic methods of synchronization available in wireless sensor networks are:

  1. Relative Ordering: In this method, the synchronization is on the order of messages or events. Here, clocks are not synchronized but just the order is maintained.
  2. Relative Timing: In this method, a node keeps information about its drift and offset in correspondence to neighboring nodes. Thus, nodes have an ability to synchronize to its neighboring nodes.
  3. Global Synchronization: In this method, there is a global timescale. All the network nodes to synchronize to this global clock.

The three most popular wireless time synchronization is:

  1. Reference Broad cast synchronization (RBS)
  2. Timing sync protocol for Wireless sensor networks (TPSN)
  3. Flooded Time Synchronization. (FTSP)

Reference Broadcast Synchronization (RBS):

This is a receiver to receiver synchronization. A third party will broadcast a beacon to all the receivers. The receivers will compare their clocks to one another to calculate their relative phase offsets and transmit the recorded times to each other. The time of reference is based on when the nodes receive the beacon.Since the time synchronization protocol is receiver to receiver synchronization, the sender can be removed from the critical path. The disadvantage to this approach is the additional time syncrhonization messages needed to exchange among the nodes.

Time Sync Protocol for Sensor Networks (TPSN):

TPSN is a Time synchronization protocol that can be applied to spanning tree based network. The protocol constitutes of two levels; level discovery phase where each node determines its node level in Wireless sensor network. In the second level called synchronization level, the synchronization phase begins at root node and propagates to other levels. Here, all nodes in ‘I’ level gets synchronized to i-1 level nodes.

Flooded Time synchronization Protocol (FTSP):

In the Flooded time syncrhonization protocol (FTSP), the nodes can form a mesh network where each node sends out time sync message to every other node, or they can form a star network where only one node at a time acts as a master and all the other nodes act as slaves. The master node periodically sends out a time sync message. All the slaves in the network receive this message and syncrhonize their local clocks to the master clock. If the slaves’ clock is off only by a constant, ideally one packet would be necessary to get synchronized with the global clock. But, various issue like temperature, aging produce a drift in the slave’s clock that needs to be periodically synchronized to the master clock.

RELATED WORK:

The FTSP was designed at Vandebuilt University and implemented using Berkeley Mica2 motes [1]. TinyOS is run on these nodes and the radios follow Zigbee (IEEE 802.15.4) protocol. The time stamp is taken at the MAC level to be accurate and inserted into the message. This is done to avoid jitter due to CPU processing time, interrupts time.

The original FTSP implementation used mesh network to send and receive the messages. FTSP in star network was implemented in [2] using the same platform. In this implementation, the time stamps were taken using 32.768kHz clock due to poor stability of the Internal Oscillator. To the best of our knowledge, FTSP hasn’t been implented on PSoC boards.

IMPLEMENTATION:

The algorithm is implemented in two phases.

  1. Root node selection
  2. Update timer

We have implemented the FTSP protocol using star topology. Each node is given an unique node_id on the network. The node with the least node_id is deemed to be the master. We used the Radio Manufacturer ID (MID) as the unique node_id on the network

The Root node selection algorithm is used to set up the star network.

Root node selection Algorithm:

To obtain time synchronization in a star network there should be a single common master to all the other nodes. All the other nodes should get synchronized to this master node. Since a master node can fail or gets disconnected, the network topology can’t have a single master. The master has to be dynamically elected considering failed nodes and new nodes added to the network.

Root node selection algorithm selects the root node in the network dynamically periodically polling on the changes in network topology.

The root node selection is further divided in to 2 phases based on the nodes present status

  1. node in slave state
  2. node in Master state

When the node is in slave state the following part of the algorithm is used to determine the master or root node.

When the nodes join the network, they act as slaves initially for a fixed timeout period called SLAVE_LISTEN_TIMEOUT. If it receives a packet with the node_id less than its own, it enters the slave mode and stores the node_id from the packet as its master. If a node initially acting as a slave fails to receive a packet for a fixed timeout interval, it declares itself as a master and sends out time sync messages with a specific period.

When the node thus reaches in to master state it periodically goes in to slave mode and listens to the network to find if any new node has joined the network with a node_id less than its own. If it receives a packet with node_id less than its own, it once again transfers back to the slave mode. Thus the polling algorithm is as below.

From the algorithm above, when two nodes of node_ids less than that of the present root_id are added to the network then both behave same and couldn’t determine which one of them can act as master. Instead they both go in to the poll mode same time and comes out of the poll mode also the same time. Thus, there will be dual masters. To get rid of the problem, the SLAVE_LISTEN_TIMEOUT for each node is maintained unique depending on its wireless MID. In this case, even though dual masters are present in the network eventually every node will converge in to single master network. This also, helps more in fast network convergence, as a slave with lesser MID will listen for very less time to determine if there are any masters in the network. It does deserve it, as it is deserved master and don’t need to keep listen for long time.

Update Timer:

Timer update is a function that gets called when the node is in slave mode and receives time synchronization message. When a particular slave node receives time sync message it compares the root id of the node (its own id). If the root id of the node is less than that of its own local id it updates its clock to that of the sender (master).

In this way, care is taken that even though continuous time synchronization is not there; all the slaves synchronize to global time periodically. The period again determines the level of synchronization that can be achieved. This period in turn depends on the speed of the wireless antenna and the size of the sync message packet. The corresponding values for the experiment are discussed in the next section.

TARGET PLATFORM:

We have implemented the FTSP protocol on PsoC CY3209 Development kits. These boards are divided into four quadrants and each quadrant has its own processor, RAM, Flash and other sensors. All the four quadrants are connected using I2C bus to share the data among the quadrants. We have implemented our algorithm on Bottom Left quadrant of the board which has CY8C27643 processor with 24Mz max frequency, 256 Bytes of RAM, 16KB of flash. We have used Artaflex radios AWP24S which have CY6936 WirelessUSB LP radio in them. These radios communicate with the processor using SPI interface. These radios have a maximum data rate of 250 kbps. The Artaflex radios have their own frame format and MAC layer protocol. Typical frame has preamble bits, Start-of-frame (SOP) field, length field, 1 to 16 bytes of data and 16 bits of CRC code.

8 bits 8 bits 8 bits16 bits16 bits

Our experiment consists of different aspects of the FTSP protocol: root selection algorithm, dynamic network topology update, time sync messages with varying clock drifts and sending intervals.

We used 32 bit timers to generate the time stamp at the sender side and embed this time stamp into the frame. We used the cypress library routines to access the timer. These routines have been implemented in assembly code. Since there is no OS running on the board, there is minimal overhead in generating time stamp and sending the sync message on the netowork. The total frame size is 9 bytes in size and with a data rate of 250kbps, it would take around 330 us to send the data packet. The timers have been experimented with different clock frequencies. The network propagation delay is in the order of 1us [3]. The Wireless Radio is interfaced to the Microcontroller Unit using SPI interface running at 12Mhz. The formation of transmit packet of 9 bytes takes at 12Mhz takes around: 6us. Similarly the formation of packet after reception takes another 6us. The CPU is running at 12Mhz clock. Estimation of all other overheads (CPU processing time is in order of micro-seconds). Compared to data sending rate, this additional overhead is not comparable.

The 12Mhz clock used in the device has drift of 30ppm.i.e., the clock drifts 30 seconds every 1 million seconds. In other words, the clock drifts 30us per Second. To keep the drift in micro-second range, the algorithm has to send the time sync packet every second. But with the above implementation, considering all the worst cases, each packet could be sent even with a 500us to 700 us difference.

We have established I2C connection between Bottom left quadrant of the board where we implemented the FTSP protocol and the top right quadrant of the board which connects to the PC to record the data. Once a time sync packet arrives from the master, the slave records the the master time stamp, updates its clock according to the master time stamp and sends out the local, master time stamps as well as the error over the I2C interface to the top right quadrant of the board (CY24894). A simple I2C slave driver and USBUART driver would continuously be running on this device to grab the time stamp data send by the I2C Master and pass it on to the PC for offline processing.

EXPERIMENT:

In our first experiment, we have verified root selection algorithm when multiple masters are present in the network. It took anywhere between 30 sec to 2 minutes for the network to get converged based on the node_ids and the order in which the network was brought up

In our second experiment, we created a master slave network and sent the time stamps from the master to the slave. The slave was successful in receving the time stamp and update its local clock with the master clock. The difference in their time stamps was displayed on LCD and the data along with master, local timestamps and the error was sent over I2C-USB to PC for offline processing

In our third experiment, we stopped the slave to syncrhonize its time stamp for 50 samples before it gets syncrhonized to the master to demonstrate the accumulation of the drift at the slave side.

RESULTS:

We have implemented the FTSP protocol on PSoC CY3209 boards. We were able to form the network among multiple nodes. Slaves were able to receive the time stamp from the master and update their local clocks. We could not change the drift of the clocks by finer degree. We attempted to change the frequency of two nodes but that would throw off the frequency of the two nodes by a larger degree.

Fig 1: Error before syncrhonization until 50th sample (around -74) and after 50th sample, the error is nearly 0 (between -1 and +1)

Fig 2: Error after syncrhonization the error is nearly 0 (between -1 and +1)

REFERENCES:

[1]. M Maroti, B. Kusy, G. Simon, and A. Ledeczi, "The Flooding Time Synchronization Protocol," in Proceedings of the 2nd International Conference on Embedded Network Sensor Systems (SenSys ’04), pp. 39-49.

[2]. Dennis Cox, Emil Jovanov, Aleksandar Milenkovic, “Time Synchronization for ZigBee Networks”

[3].