================================= Packet-level time synchronization ================================= :TEP: TBA :Group: Core Working Group :Type: Documentary :Status: Draft :TinyOS-Version: > 2.1 :Author: Miklos Maroti, Janos Sallai :Draft-Created: 15-May-2008 :Draft-Version: $Revision$ :Draft-Modified: $Date$ :Draft-Discuss: TinyOS Developer List .. Note:: This memo documents a part of TinyOS for the TinyOS Community, and requests discussion and suggestions for improvements. Distribution of this memo is unlimited. This memo is in full compliance with TEP 1. Abstract ============================================================================ This TEP describes a packet-level time synchronization mechanism that allows for sending a time value along with the packet which is automatically converted from the sender's local time to the receiver's local time by the communications stack. 1. Introduction ============================================================================ Time of occurrence of events is often of interest in a sensor network. Maintaining a synchronized UTC or a virtual global time in a sensor network may, however, lead to significant communication overhead and may not always be required by the application. This TEP describes a packet-level time synchronization mechanism that allows for sending a time value along with the packet which is automatically converted from the sender's local time to the receiver's local time by the communications stack. Packet-level time synchronization is limited to single-hop communication and does not provide synchronized network time. It provides a simple yet powerful abstraction, on top of which it is possible to implement higher-level time synchronization services (e.g. FTSP [6]_)in a platform-independent way. Packet-level time synchronization is semantically equivalent to the ETA primitives [1]_. The rest of this TEP specifies: - Platform-independent packet-level time synchronization interfaces - How these interfaces are provided in the HIL - A guideline how each transceiver's HAL may implement the above interfaces 2. Interface ============================================================================ Packet-level time synchronization is implemented by the communication stack and is exposed through two interfaces, ``TimeSyncAMSend`` and ``TimeSyncPacket``. The ``TimeSyncAMSend`` interface allows for sending a time value (e.g. an event timestamp) along with a message. It is parameterized by the precision and width of the time value:: interface TimeSyncAMSend { command error_t send(am_addr_t addr, message_t* msg, uint8_t len, size_type event_time); command error_t cancel(message_t* msg); event void sendDone(message_t* msg, error_t error); command uint8_t maxPayloadLength(); command void* getPayload(message_t* msg, uint8_t len); } The ``send`` command sends a regular message just like ``AMSend.send`` [2]_, but it also performs sender-receiver time synchronization. The ``event_time`` parameter holds the time of some event as expressed in the local clock of the sender. The receiver can obtain the time of this event (expressed in its own local time) via the ``TimeSyncPacket`` interface. The rest of the functionality is identical to that of the ``AMSend`` interface, therefore its description is omitted here. Please refer to [2]_ for details. The ``TimeSyncPacket`` interface, parameterized by a precision tag and width, allows for retrieving a time value that was sent along the received packet:: interface TimeSyncPacket { command bool isValid(message_t* msg); command size_type eventTime(message_t* msg); } The ``isValid`` command returns ``TRUE`` if the value returned by ``eventTime`` can be trusted. Under certain circumstances the received packet cannot be properly time stamped, so the sender-receiver synchronization cannot be finished on the receiver side. In such case, this command returns ``FALSE``. This command MUST be called only on the receiver side and only for messages transmitted via the TimeSyncAMSend interface. The communications stack MUST guarantee that if the ``isValid`` command called from within the ``receive`` event handler returns ``TRUE``, then the value returned by the ``eventTime`` command can be trusted. However, it might be possible that the local clock overflowed more than once or that is was stopped or reset since the packet was received, which causes the ``event_time`` to be invalid. The ``isValid`` command MAY return ``TRUE`` in such situations, and it is the responsibility of the user of the interface to ensure that the clock runs freely from the time of message reception to the time when ``eventTime`` is called. To avoid this issue, it is recommended that ``isValid`` and ``eventTime`` are called from the ``receive`` event handler. The ``eventTime`` command should be called by the receiver of a packet. The time of the synchronization event is returned as expressed in the local clock of the caller. This command MUST BE called only on the receiver side and only for messages transmitted via the ``TimeSyncAMSend`` interface. 3. HIL requirements ============================================================================ The signature of the platform's ActiveMessageC [5]_ MUST include:: provides interface TimeSyncAMSend; provides interface TimeSyncPacket; where event times are given in the node's local time, which is available through ``HILTimerMilliC.LocalTime``. The communications stack MAY support timestamp precisions and widths other than ``TMilli`` and uint32_t, respectively. Also, alternative ``TimeSyncAMSend`` and ``TimeSyncPacket`` implementations MAY use clock sources other than ``HILTimerMilliC.LocalTime``. 4. Implementation guidelines ============================================================================ Packet-level time synchronization employs the ETA primitives. In this TEP, only the basics of the time synchronization mechanism are described, for details please see [1]_. This section presents two possible implementation approaches. The first approach assumes that the payload of the packet is still mutable when the transmission time of the packet (e.g. the timestamp of the SFD interrupt) becomes available. The second approach avoids this assumption and uses the packet timestamping functionality described in TEP [4]_ to implement packet- level time synchronization. 4.1 Approach #1 ---------------------------------------------------------------------------- Several transceivers allow for modifying the contents of a packet after packet transmission is started. Packet-level time synchronization can be implemented very efficiently on such platforms. Transmitter's story - When the communications stack services a ``TimeSyncAMSend.send`` command called with event timestamp ``t_e``, it stores ``t_e`` (e.g. in a map with the pointer of the message_t as key) and sets the designated timestamp field in the packet payload to ``0x80000000``. - When the packet starts being transmitted over the communication medium, a corresponding hardware event is timestamped (e.g. an SFD interrupt). Let us denote this transmission timestamp with ``t_tx``. The difference of event timestamp ``t_e`` and transmit timestamp ``t_tx`` is written into the designated timestamp field in the payload of the packet (typically into the footer, since the first few bytes might have been transmitted by this time). That is, the information the packet contains at the instance when being sent over the communications medium is the age of the event (i.e. how much time ago the event had occurred). - If an error occurs with timestamping the transmission or with writing the package payload after transmission has started, then the designated timestamp field in the packet payload will contain ``0x80000000``, indicating the error to the receiver. Receiver's story - The packet is timestamped with the receiver node's local clock at reception (e.g. with the timestamp of the SFD interrupt). Let us denote the time of reception with ``t_rx``. The reception timestamp is stored in the metadata structure of the ``message_t`` [5]_. - When the event time is queried via the ``TimeSyncPacket`` interface, the ``eventTime`` command returns the sum of the value stored in the designated timestamp field in packet payload and the reception timestamp, i.e. ``e_t- e_tx+e_rx``. This value corresponds to the time of the event in the receiver's local clock. - The ``TimeSyncPacket.isValid`` command returns ``FALSE`` if the time value stored in the payload equals ``0x80000000`` or if the communications stack failed to timestamp the reception of the packet. Otherwise ``TRUE`` is returned, which indicates that the value returned by ``TimeSyncPacket.eventTime`` can be trusted. 4.1 Approach #2 ---------------------------------------------------------------------------- If a particular platform does not support changing the packet contents after the synchronization event (start of transmission, SFD interrupt, etc.) had occured, it is still possible to provide packet-level time synchronization functionality at the cost of some communication overhead. Such an approach can rely on packet timestamping TEP [4]_ to implement packet-level time synchronization. Transmitter's story - When the communications stack services a ``TimeSyncAMSend.send`` command called with event timestamp ``t_e``, it stores ``t_e`` (e.g. in a map with the pointer of the message_t as key) and sends the packet. - Transmission of the packet is timestamped using the packet timestamping TEP [4]_ mechanism. Let us denote this transmission timestamp with ``t_tx``. The difference of event timestamp ``t_e`` and transmit timestamp ``t_tx`` is sent in an auxilliary packet. That is, the information the auxulary packet contains is the age of the event at the time when the initial packet was transmitted. Receiver's story - The packet is timestamped with the receiver node's local clock at reception (e.g. with the timestamp of the SFD interrupt). Let us denote the time of reception with ``t_rx``. The reception timestamp is stored in the metadata structure of the ``message_t`` [5]_. - When the auxilliary packet arrives, the time value it carries (``t_e-t_tx``, the age of the event) is stored in a metadata field of the main packet. The auxilliary packet is discarded, and the receive event is signalled with the pointer to the main packet. - When the event time is queried via the ``TimeSyncPacket`` interface, the ``eventTime`` command returns the sum of the value stored in the metadata (age of the event) and the reception timestamp, i.e. ``e_t- e_tx+e_rx``. This value corresponds to the time of the event in the receiver's local clock. - The ``TimeSyncPacket.isValid`` command returns ``FALSE`` if the communications stack failed to timestamp the reception of the packet. Otherwise ``TRUE`` is returned, which indicates that the value returned by ``TimeSyncPacket.eventTime`` can be trusted. 5. Reference implementation ---------------------------------------------------------------------------- A reference implementation of the packet-level time synchronization mechanism described in this TEP can be found in ``tinyos-2.x/tos/chips/rf230``. 6. Author's Address ============================================================================ | Miklos Maroti | Janos Sallai | Institute for Software Integrated Systems | Vanderbilt University | 2015 Terrace Place | Nashville, TN 37203 | phone: +1 (615) 343-7555 7. Citations ============================================================================ .. [1] Kusy, B., Dutta, P., Levis, P., Maroti, M., Ledeczi, A., Culler, D., Elapsed Time on Arrival: A simple and versatile primitive for canonical time synchronization services. International Journal of Ad hoc and Ubiquitous Computing, Vol, 2, No. 1, 2006. .. [2] TEP 116: Packet protocols .. [3] TEP 102: Timers .. [4] TEP TBA: Packet timestamping .. [5] TEP 111: message_t .. [6] Maroti, M., Kusy, B., Simon, G., and Ledeczi, A. 2004. The flooding time synchronization protocol. In Proceedings of the 2nd international Conference on Embedded Networked Sensor Systems (Baltimore, MD, USA, November 03 - 05, 2004). ACM SenSys '04.