METHODS AND SYSTEMS FOR ACCURATE AND ACCELERATED SYNCHRONIZATION FOR COMMUNICATION NETWORKS

Abstract

The present invention contemplates a method and/or system for accurately and accelerated synchronization of communication networks. The method contemplates providing a virtual clock module in which all nodes of a network use the module in an identical manner and wherein the virtual clock module of nodes is generally a data stream whose element is the virtual time with whatever notice made is in communication with at that instant. In a preferred embodiment of the invention, the method or system is processed using a finite impulse filter. The virtual clock in each node is responsible for generating a stream of data in which one may consider as virtual time. Each sample of the discrete time stream is constructed by its nearest neighbor of the node concerned communicating the current sample of its own virtual time stream to the node.

Claims

1. A system for accurately and accelerated synchronization of communication networks, said system comprising a virtual clock module in which all nodes of a network use the material in an identical manner and wherein the virtual clock module of nodes is a data stream whose element is the virtual time with whatever notice made is in communication with at that instant; the procedure constructs a virtual clock (FIG. 1) in which all nodes used in an identical manner and generate a data stream whose element is the vertical time with whatever notice made is in communication with at that instant and wherein the method is processed using a finite impulse filter.

2. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which the procedure is simple and used by networks build from inexpensive hardware.

3. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which the procedure works for any deterministic network typology provided that the network is connected.

4. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which the synchronization procedure works when the communication network has random connectivity.

5. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which the performance of the synchronization procedure degrades with communication link availability.

6. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which the procedure is scalable for a large scale network.

7. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which the procedure treats a master node or gateway node in the same manner as the other nodes of the network.

8. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which the nodes need not be initially set to the same time in order for the procedure to function (Even if the nodes initially start with random values for time they will all converge to the same value. This enables the addition of or remove of nodes while the network is operating without endangering the networks ability to synchronize).

9. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which said procedure uses a low number of communication exchanges and leads to significant energy conservation and includes said physical clock to totally turn off communication when it is not needed.

10. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which said procedure is decentralized, self-correcting and self-maintaining.

11. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which said system uses only single hop messaging.

12. The system for accurately and accelerated synchronization of communication networks according to claim 1, in which said procedure links performance to the quality of the hardware and if the nodes carry communication at a fast rate then the error is synchronization can be reduced, also if the quality of the physical clocks used is high there is no need for frequent maintenance of the quality of synchronization.

Description

DESCRIPTION OF THE DRAWINGS

[0009] FIG. 1 is a suggested setup for a node synchronization;

[0010] FIG. 2 illustrates the structure of the suggested virtual clock;

[0011] FIG. 3 is a typical pattern of error (local time-server time) versus communication instants;

[0012] FIG. 4 is the discrete pulse response of the processing filer;

[0013] FIG. 5 is the work flow of the synchronization protocol used by the nodes;

[0014] FIG. 6 is the MICAz wireless sensor node;

[0015] FIG. 7 is a test network;

[0016] FIG. 8 is the node error profile for the network in FIG. 7 for different values of channel availability;

[0017] FIG. 9 is the four nodes ring topology, experimental data;

[0018] FIG. 10 is the error and detection signal of the nodes in FIG. 9;

[0019] FIG. 11 is a nine-node network;

[0020] FIG. 12 is the virtual clock time and error for each node of the circuit in FIG. 11;

[0021] FIG. 13 is a sixteen-node network;

[0022] FIG. 14 is the virtual clock time and error for each node of the circuit in FIG. 13;

[0023] FIG. 15 is the time at which minimum error occurred versus network size;

[0024] FIG. 16 is the error in all nine nodes averaged as a function of iteration; and

[0025] FIG. 17 is the maximum error in all nine nodes averaged as a function of iteration.

[0026] The invention will now be described in connection with the accompanying drawings wherein like reference numbers are used to identify like parts.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS OF THE INVENTION

[0027] 1.0 Summary of Invention/Detailed Description:

[0028] The nodes of a network with an impoverished infrastructure are difficult to synchronize. Since they are built from cheap hardware, their clocks are highly likely to suffer significant drift. These nodes also have a limited power supply that does not support the energy drain the frequent communication requires. The nodes of such networks, such as in sensor networks, will most probably be deployed in large numbers in harsh and RF challenged environments in which wide horizon broadcast is not possible and connectivity is unstructured and intermittent. Also, the probability of failure of such nodes is high. Therefore, making the synchronization procedure heavily dependent on a node's ID or using multi-hop communication is not desirable.

[0029] In this patent, Applicants suggest a decentralized and self-organizing procedure for synchronizing communication networks that do not have an infrastructure. The procedure is light, produces high accuracy using a small number of communication exchange with other nodes, uses only single hop communication and can function satisfactorily even when connectivity is unstructured and/or random.

[0030] The procedure constructs a virtual clock (FIG. 1) which all nodes of the network use in an identical manner. The virtual clock module of node-i generates a data stream whose element is the virtual time of the nodes. The virtual time at a certain instant is taken as the average of the virtual time with whatever nodes node-i is communicating with at that instant as shown in FIG. 2. The error formed by comparing the local sequence of average times to exact master node time is found to settle to a constant value that is relatively low. However, it is noticed that before convergence the error temporarily drops then climbs back again. A typical profile of the error is shown in FIG. 3. By interrupting the averaging process at the proper time while the computation is still in transient state, one can significantly enhance accuracy (orders of magnitude better than steady state). One can also significantly reduce the communication attempts a node makes in order to synchronize with other nodes, hence quickly synchronizing the network and significantly reduce the energy drain due to communication.

[0031] In order to detect the transient communication instant at which system's accuracy is high, the sequence is first processed using a finite impulse filter, h(n), whose pulse sequence is shown in FIG. 4. The filter is matched to the pattern in {circumflex over (t)}.sub.i which indicates that the synthetic time is close to the global time of the network (the time of the master node, t.sub.m). The stream from the filter is then examined by a decision rule to select the instant at which a sample from the average time stream ({circumflex over (t)}.sub.i) is selected as the global time, which the physical local clock should be reset to. When the condition becomes valid, Ir.sub.i is set to 1, the value of the physical clock is reset to the selected virtual time, and node-i seizes communication. Once the physical clock is reset, a counter is started in order to wake-up the virtual clock a time Tw after the physical clock is reset. This is done by setting the variable Is.sub.i=1. Tw is selected based on the quality of the physical clock and its tendency to drift. The desired accuracy and how much communication the node is allowed to devote to synchronization are also a factor in selecting Tw. An overall flow of how the synchronization procedure works is described by the flowchart in FIG. 5. The following describes in details each block of the synchronization workflow.

[0032] Get neighbors' time information:

1If I.sub.s=1, then
2Detect the transmission of the neighboring K nodes (K>0)
3For each one of the K neighbors, define the binary variable C.sub.j j=1 , . .K, such that C.sub.j=0 if the jth neighbor is to be ignored and C.sub.j=1 if the neighbor is to be used in synchronizing the node's time
4Store the time each node broadcast in {circumflex over (t)}.sub.j j=1 , . . K

[0033] Average time information:

1. Construct C=.sup.K.sub.j=1C.sub.j
2. If C=0, then keep virtual time unchanged ({circumflex over (t)}.sub.i(n)={circumflex over (t)}.sub.i(n-1)+T)
3. Else update virtual time of node-i

[00001]$\left({\hat{t}}_i\left(n\right)=\frac{1}{C}.Math.\underset{j=1}{\overset{K}{.Math.}}.Math.C_j.Math.{\hat{t}}_j\left(n\right)\right)$

[0034] Filter average time sequence:

[0035] The virtual time sequence of node-i created by the averaging process is filtered using the Finite Impulse Response (FIR) filter (h(n)):

h(n) =c.sub.f.Math.0.2.Math..sub.n+3+c.sub.f.Math.0.5.Math..sub.n+2+c.sub.f.Math.0.2.Math..sub.n+1+c.sub.f.Math.0.Math..sub.n0.2.Math..sub.n10.5.Math..sub.n20.2.Math..sub.n3

[0036] where c.sub.fis a positive constant whose value is close to unity (0.95c.sub.f1.05).

[0037] The filter is a modified difference filter with weighted coefficients. The filter is used to detect the minimum point of the time sequence and it produces the filtered sequence given by:

d(n)=h(n){circumflex over (t)}.sub.i(n)

[0038] where * is the discrete convolution operator.

[0039] Detection check & Reset Physical clock

1Ignore the first L samples of d(n) since they are fluctuating (Applicants found that L=13 is enough)
2if at ns, d(ns) changes signs (d(ns)*d(ns1) <0), then
3I.sub.r=1, I.sub.s=0,
4t.sub.j(ns) ={circumflex over (t)}.sub.i(ns)

[0040] Time maintenance counter & maintenance check

1If (t.sub.i(ns)+Tw)-{circumflex over (t)}.sub.i(n) <0, then Is=1, Go to get neighbors time stage

[0041] Symbols & Abbreviations:

t.sub.m: Time of the master node of the network. This node need not to be labeled, it can stay anonymous. Its time is generated by a physical clock and need not to be computed.
t.sub.i: Time registered by the physical clock of node i
{circumflex over (t)}: Time computed by the virtual clock of node i
Is.sub.i: A binary set variable of node i, If its value=1, its virtual clock is activated
Ir.sub.i: A binary reset variable of node i, if its value=1 the value of the physical clock is reset to the value computed by the virtual clock
h(n): The coefficients of the finite impulse response filter used to process the time average sequence,
d(n): Filtered virtual time sequence (d(n)=h(n)*{circumflex over (t)}.sub.i(n))
Tw: Estimate refresh time during which communication seizes and the virtual clock is inactive
n: Discrete time index which represents an instant at which a virtual time estimate is updated
ns: Discrete time instant at which a decision is made that the virtual time is close to the global time
K: The number of neighboring nodes whose transmission is detected by node i
C.sub.j: A binary inclusion factor (j=1, . . K). If node i decides to include node j in synchronizing its time, it sets C.sub.j to 1, else C.sub.j is set to zero.
.sub.n: it is the Kronecker delta function (.sub.n=1 for n=0, else .sub.n =0)
L: Number of discrete time steps to wait before attempting to use d(n) to identify the discrete time instant at which the virtual time is close to global time
T: Clock cycle

[0042] Each node of the network (i.e. it is a synchronization protocol) can identically use the synchronization procedure. Therefore, deploying the synchronization procedure on a network is as simple as downloading the protocol to the individual nodes.

[0043] The procedure is simple and can be used by networks built from inexpensive hardware.

[0044] The synchronization procedure does work for any deterministic network topology provided that the network is connected.

[0045] The synchronization procedure does work when the communication network has random connectivity.

[0046] The performance of the synchronization procedure gracefully degrades with communication link availability.

[0047] The procedure is scalable for large scale network.

[0048] The procedure treats the master node (gateway) in the same manner as the other nodes of the network.

[0049] The nodes need not be initially set to the same time in order for the procedure to function. Even if the nodes initially start with random values for time, they will all converge to the same value. This enables the addition or removal of nodes while the network is operating without endangering the network ability to synchronize.

[0050] The procedure uses low number of communication exchange. This leads to significant energy conservation. It also uses the physical clock to totally turn off communication when it is not needed.

[0051] The procedure is decentralized, self-correcting and self-maintaining.

[0052] It uses only single hop messaging which is more reliable than multi-hop messaging. Single hop communication or messaging, means that a node needs only the information of the nodes that are of direct communication with it. Two hop messaging means that a node needs the information of the nodes that are directly communicating with it and the nodes that are directly in communication to those nodes but do not have a communication link with the node concerned and so on for three, four , . . . hop communication. Multi-hop communication is very expensive in terms of depleting the energy of the battery, making the performance shaky and dependent on the proper functioning of all the nodes and increasing the complexity of processing in terms having to maintain routing tables and having to give the nodes unique identifiers (i.e. node labeling). Single-hop communication does not require all of the above.

[0053] The procedure links performance to the quality of the hardware. If the nodes can carry communication at a fast rate, then the error in synchronization can be reduced. Also if the quality of the physical clocks used is high, then there is no need for frequent maintenance of the quality of synchronization.

[0054] The procedure has a fast rate of convergence and can quickly synchronize a network.

[0055] The procedure, despite its simplicity, can yield accurate synchronization relative to the data exchange rate among the nodes.

[0056] The synchronization procedure does not depend on rigid network wide node labeling in order to function. Instead, it uses, short-term dynamic, node-centered labeling. This makes it suitable for large scale networks operating in harsh environments where network discovery is difficult or impossible.

[0057] The work reported in this patent has not been published previously. However, an extensive literature review was conducted and no similar procedures for synchronizing networks were found.

[0058] The idea of using virtual clocks for synchronizing communication networks without infrastructure is fairly recent. It individuated from an area called consensus control. The observation below, however, may explain why Applicants work address the practical issues needed to satisfactorily synchronize a physical communication network without infrastructure:

1The synchronization accuracy of most existing methods that use a virtual clock concept is relatively low and is not suitable for practical operation
2To the best of Applicants' knowledge, the methods keep the virtual clocks running for a long time until steady state is reached. This uses excessive communication and causes battery depletion
3Applicants did not see procedures where virtual clocks and physical clocks are combined to create a synchronized timing system. The cause of that could be the inability to determine specific points in time to stop the virtual clock and reactivate it again
4Some techniques on virtual clocks attempted to improve accuracy by augmenting averaging with other operations such as integration. The result was to jeopardize stability of the virtual clock. This also imposed severe limitations on the structure of the network and led to the loss of unconditional stability that allowed flexibility in network connectivity and operation when connectivity is time variant
5Applicants have not seen any of the virtual clock suggested up to now implemented on an actual communication network with no infrastructure (e.g. a sensor network).

[0059] 5.0 Data Analysis:

[0060] The properties of the suggested synchronization protocol is thoroughly tested using both simulation and physical experiments using the MICAz which is a 2.4 GHz, IEEE/ZigBee 802.15.4, board (FIG. 6).

[0061] To test the error profile created by the averaging procedure, in particular the transient dip in the error profile, the test network in FIG. 7 is simulated. Node-1 is selected as the master node (a stubborn node). A communication rate of 1 KHz is used. A connectivity function, f(C.sub.ij) among nodes is modeled as Bernoulli random variable with a discrete probability distribution function:

[00002]$f\left(C_{i,j}\right)=[\begin{array}{cc}p& C_{i,j}=1\\ 1-p& C_{i,j}=0\end{array}$

[0062] where p is the probability that the channel is on and the nodes are communicating. FIG. 8 shows the error profile for each node taken at three values for p: p=1 where the links are available 100% of the time, p=0.75 and p=0.5 where communication links malfunction 25% and 50% of the time, respectively. As can be seen from the case where the communication channels are fully available, the transient dip in error appeared in all nodes where the time error for each node with respect to the master nodes is orders of magnitude less than the steady state error. The communication instants at which the minimum error for each node was attained were close. The profile reasonably persisted for a relatively high channel outage rate. All experimental results corroborated the simulation results.

[0063] In FIG. 9, four MICAz sensor nodes are used to implement a ring topology network with one master node and three other nodes attempting to synchronize with it. Data exchange and estimate update is carried out at a rate of 1 KHz. The virtual time computed by the nodes is compared with that of the master node and the error signal is computed. The local times are also processed to determine the instant at which the virtual clock should stop. The graphs of the error and the detection are shown in FIG. 10. The exact data of the network is shown in Table 1. As can be seen, the minimum value the error reaches is less than 50 micro-seconds for all the nodes which takes place in the early cycles of the message exchange (at most 18 updates). Also, all nodes attained their minimum around the same time within only four update cycles. The value of the steady state error is much higher than the minimum (more than 2 milli-seconds) for all nodes and consumed close to three times the number of communication exchange. The suggested filter and decision maker selected the detection instants early in the communication exchange close to where the minimum occurs. The error of the selected virtual time is much better than that of steady state and in some cases is close to the minimum achievable error.

TABLE-US-00001 TABLE 1 detection data corresponding to FIG. 10 Exact Steady state Detected Nodes Iterations Error Iterations Error Iterations Error N1 18 0.000463281 47 0.002999968 18 0.000463281 N2 14 6.48437E05 46 0.001999968 17 0.001463281 N3 14 6.48437E05 46 0.001999968 17 0.001463281 Max 18 0.000463281 47 0.002999968 18 0.001463281 Min 14 6.48437E05 46 0.001999968 17 0.000463281

[0064] The synchronization protocol is tested on a nine-node network (FIG. 11). The evolution of the time estimate until the virtual clock is stopped for each node alone with the corresponding error relative to the master node is shown in FIG. 12. The same observations as in the previous case are recorded as shown in Table 2. All nodes exhibited a sharp, transient drop in error early in the message exchange that is significantly lower than the steady state value. The suggested protocol was able to detect this dip in error and synchronized the nodes at an accuracy that is much better than that of steady state and largely comparable to the maximum achievable accuracy.

TABLE-US-00002 TABLE 2 Time estimate characteristics for the nodes in FIG. 11 Exact Steady State Detected Nodes Iterations Error Iterations Error Iterations Error N1 67 0.000271674 195 0.007998733 67 0.000271674 N2 61 0.000210105 194 0.007498733 66 0.000228326 N3 67 0.000247653 191 0.006498654 64 0.001056578 N4 61 0.000210105 194 0.007498733 66 0.000228326 N5 67 0.000247653 191 0.006498654 64 0.001056578 N6 61 0.000265107 187 0.004499105 59 0.000960327 N7 67 0.000247653 191 0.006498654 64 0.001056578 N8 61 0.000265107 187 0.004499105 59 0.000960327 Maximum 67 0.000271674 195 0.007998733 67 0.001056578 Minimum 61 0.000210105 187 0.004499105 59 0.000228326

[0065] A larger sixteen-node network is tested (FIG. 13). The evolution of the time estimate until the virtual clock is stopped for each node alone with the corresponding error relative to the master node is shown in FIG. 14. The same observations as in the previous case are recorded as shown in Table 3. Interestingly, as the size of the network increased, accuracy also improved and more saving in the number of message exchange needed to synchronize the network, relative to steady state, is obtained.

TABLE-US-00003 TABLE 3 Time estimate characteristics for the nodes in FIG. 13 Exact Steady State Detected Nodes Iterations Error Value Iterations Error Value Iterations Error Value N1 96 0.00010285 447 0.041338725 106 0.00957014 N2 100 0.00033942 446 0.040388725 105 0.00862014 N3 96 0.000315173 444 0.038149931 103 0.002891579 N4 100 0.000188637 441 0.035842747 100 0.000188637 N5 100 0.00033942 446 0.040388725 105 0.00862014 N6 96 0.000215716 444 0.038828428 104 0.007612213 N7 100 0.000200307 441 0.035367798 100 0.000200307 N8 99 0.000459066 436 0.0316356 96 0.000669474 N9 96 0.000315173 444 0.038149931 103 0.002891579 N10 100 0.000200307 441 0.035367798 100 0.000200307 N11 99 0.000284579 433 0.029056619 92 0.002428683 N12 95 1.00546E05 420 0.020845853 80 0.014000267 N13 100 0.000188637 441 0.035842747 100 0.000188637 N14 99 0.000459066 436 0.0316356 96 0.000669474 N15 95 1.00546E05 420 0.020845853 80 0.014000268 Maximum 100 0.000459066 447 0.041338725 106 0.014000268 Minimum 95 1.00546E05 420 0.020845853 80 0.000188637

[0066] It is interesting to notice that the growth in the synchronization time versus the size of the network is almost linear as shown in FIG. 15. This is a good indicator that the protocol is scalable for large-scale networks.

[0067] In the following Applicants compare the protocol with the two popular protocols: Rated Flooding Time Synchronization Protocol (RFTSP) and Energy-Efficient Gradient Time Synchronization Protocol (EGTSP). Table 4 describes the specifications of the RFTSP, EGTSP and the proposed protocol. As can be seen from the table, from a practical point of view, the suggested protocol competes with the other two protocol.

TABLE-US-00004 TABLE 4 Specifications of three protocols Specification RFTSP EGTSP Our Protocol Type Centralized/Tree Distributed Distributed Reference/Root Reference/Root Node Broadcasting Packet Directly communicate Node to start the Flooding contain the local with the neighbours Process information about the and no reference neighbours to start node periodically the updates Failures Node/Link Failures None None Overhead High overhead, power Less overhead, power Suitable for dense Problem consumption is high efficient and high life of network, power and life of time is low time comparing with efficient and high life FTSP of time Communication Multi Hop Single Hop Single Hop Type Communication Communication Communication Compensation Compensate drift and Compensate drift and Compensate drift and offset at the same offset individually offset at the same time time Communication High Medium Low Cycles

[0068] FIGS. 16 and 17 demonstrates clearly that the suggested synchronization protocol competes with the other two protocols. First, the convergence of the suggested protocol is faster than the other two. This leads to saving in energy needed for communication. Also, unlike the other two, the time to stop the protocol and declare the circuit synchronized is well defined. As for the accuracy, it matches, even beats, the other two.

[0069] While the invention has been defined in accordance with its preferred embodiments, it should be recognized that changes and modifications may be made therein without departing from the scope of the appended claims.