Recursive time synchronization protocol method for wireless sensor networks

• US 9,226,252 B2
• Filed: 06/03/2013
• Issued: 12/29/2015
• Est. Priority Date: 06/03/2013
• Status: Expired due to Fees

• Current Assignee: King Fahd University of Petroleum & Minerals (Government of Saudi Arabia), King Abdul AZIZ City For Science and Technology
• Original Assignee: King Fahd University of Petroleum & Minerals (Government of Saudi Arabia), King Abdul AZIZ City For Science and Technology
• Inventors: Akhlaq, Muhammad, Sheltami, Tarek R.
• Primary Examiner(s): Oveissi, David
• Application Number:
  US13/909,031
• Publication Number:
  US 20140355628A1
• Time in Patent Office: 939 Days
• Field of Search: 370/3, 370/509
• US Class Current: 1/1
• CPC Class Codes: H04W 56/001 Synchronization between nodes

Abstract

The recursive time synchronization protocol method for wireless sensor networks provides a modified and extended RTSP method to make it work with clustered networks. In case of non-clustered or flat network, each node is assumed to be a clusterhead in order to run the RTSP method correctly. The RTSP method involves the election of a reference node, and compensation for offset and drift. Simulation results show that the extended RTSP method further improves the accuracy and energy consumption, i.e., it can provide an average accuracy of 0.23 μs in a large multi-hop clustered network while using only 1/7th of the energy consumed by FTSP in the long run.

Claims

1. A computer-implemented recursive time synchronization protocol method for a clustered wireless sensor network (WSN), comprising the steps of:

electing a single reference node i for offset and drift compensation, the electing being limited to nodes that are clusterheads;

calculating a time read by a logical clock of the i^th node of the clustered WSN, the calculation utilizing the relation;

C_i(t)=α

_i+β

_it,

where α

_i is the clock offset deviation from ideal time at the reference time t=0 and β

_i is the frequency of the clock;

re-synchronizing the clock within a time T≦

δ

/2ρ

, where δ

is an offset and ρ

is a skew rate;

estimating the offset and a drift of the clock, thereby re-synchronizing the clock;

initiating a time synchronization request, the time synchronization request being initiated by any initiating node in the clustered WSN, wherein the step of initiating the time synchronization request comprises the steps of;

initiating the time synchronization request from the initiating node at the initiating node'"'"'s local time T1 and transmitting the time synchronization request to a first intermediate node;

receiving the time synchronization request at the first intermediate node at the first intermediate node'"'"'s local time T2;

storing identification data and local times T1 and T2 in computer readable memory, the local times T1 and T2 being respectively stored as variables T1 old and T2old; and

forwarding the time synchronization request from the first intermediate node to a second intermediate node at the first intermediate nodes local time T1;

recursively forwarding the time synchronization request from the second intermediate node to the reference node, thereby establishing a request-path, the reference node receiving the forwarded time synchronization request at the reference node'"'"'s local time T2;

using a REP (reply to time synchronization) message to forward the time T back to the initiating node via the request-path; and

compensating the time T with a propagation delay time at each hop in the request-path, thereby time synchronizing all clustered WSN nodes in the request-path, wherein the step of compensating the time T comprises the steps of;

transmitting the REP message from the reference node to the second intermediate node at the reference node'"'"'s local time T3;

receiving the REP message at the second intermediate node at the second intermediate node'"'"'s local time T4;

calculating a first propagation delay, d1, as

2. The computer-implemented recursive time synchronization protocol method for clustered wireless sensor networks according to claim 1, wherein said reference node election further comprises the step of sending an ERN (enquiry/reference node election) message directed at the clusterheads.

3. The computer-implemented recursive time synchronization protocol method for clustered wireless sensor networks according to claim 2, wherein said request for time synchronization (REQ) comprises the step of sending a REQ message directed at the reference node.

4. The computer-implemented recursive time synchronization protocol method for clustered wireless sensor networks according to claim 3, wherein said ERN, REP and REQ messages each comprise a message ID field, an origin ID field, an immediate source node ID field, an immediate destination node ID field, a reference node ID field, a local time when the message was sent/forwarded field, a local time when the message was received field, a local time when a reply was sent/forwarded field, and a reference time when the reply was sent/forwarded field.

5. The computer-implemented recursive time synchronization protocol method for clustered wireless sensor networks according to claim 3, wherein said step of time T forwarding is performed by any fully time synchronized node in said request-path.

6. The computer-implemented recursive time synchronization protocol method for clustered wireless sensor networks according to claim 5, wherein nodes within a predefined range to the reference node perform the following steps before nodes outside the predefined range:

receive announcements about a newly elected reference node;

initiate a time synchronization request on knowing the ID of the newly elected reference node; and

synchronize with the newly elected reference node.

7. The computer-implemented recursive time synchronization protocol method for clustered wireless sensor networks according to claim 6, further comprising the step of said newly elected reference node to retreat on receiving an ERN message from another reference node having a smaller identification (ID), thereby avoiding a reference node conflict.

8. The computer-implemented recursive time synchronization protocol method for clustered wireless sensor networks according to claim 7, further comprising the steps of:

using said ERN message to determine if a node is losing accuracy of time synchronization; and

recursively performing said step of forwarding the time synchronization request when the node is determined to be losing time synchronization accuracy.

9. The computer-implemented recursive time synchronization protocol method for clustered wireless sensor networks according to claim 7, wherein said step of estimating the offset and the drift of the clock is performed using a least square linear regression on two data points (2LR), governed by the relations: