METHOD OF CLOCK SYNCHRONIZATION FOR A DISTRIBUTED NETWORK

A method of clock synchronization for a distributed, message-passing network includes the step of dissecting a graphical model of the distributed network into a sequence of time-varying directed sub-graphs, each sub-graph including a selection of closed loops. By comparing the sequence of sub-graphs, the influence of each closed loop is quantified. Using the loop influence information, a selection of edges in the graphical model is dynamically identified for deletion using a hierarchically semiseparable structure in order to yield an optimized graphical model. A sum-product message-passing algorithm is then applied to the optimized graphical model to calculate a clock synchronization solution. By maintaining an optimal subset of closed loops within the model, the algorithm converges to a synchronization solution, while, at the same time, limits susceptibility to faults as well as maintains a sufficient degree of algorithmic complexity that streamlines the number of steps required to achieve convergence.

FIELD OF THE INVENTION

The present invention relates generally to the field of electronic communications and, more particularly, to time synchronization protocols applied to the individual nodes of a distributed sensor or communications network.

BACKGROUND OF THE INVENTION

In a sensor or communications network, a plurality of individual compute devices is digitally interconnected to allow for the exchange of data, resources, and the like. A communication protocol is applied to the network to regulate the transmission of electronic data amongst the various compute devices, which are commonly referenced simply as nodes.

In a distributed network, the transmission of data is operationally dependent upon time synchronization amongst the individual nodes. For instance, a command which is designed to modify system code may utilize timing information to ensure that the most current version of the code is corrected. However, without proper clock synchronization, these types of code modifications may yield imperfect results.

Even when initially synchronized, the internal clock for each of the various independent nodes often counts time, or oscillates, at a slightly varying rate. As a result of this clock drift, nodes may observe certain events at different time intervals. Accordingly, individual clocks within a distributed network require periodic synchronization in order to ensure successful communications between nodes.

The communication protocol for a decentralized distributed network typically relies upon message passing amongst a selection of nodes in order to synchronize time. In other words, by routinely comparing the timing information for a selection of nodes in the network, a time inference algorithm can be implemented to in order to determine the proper time and, in turn, adjust the internal clock for each node accordingly.

Belief propagation is one type of message-passing algorithm applied to distributed networks for clock synchronization purposes. Belief propagation is a sum-product message-passing algorithm which performs probabilistic interference on a graphical model in order to calculate the marginal distribution for unobserved nodes using known values derived from observed nodes. A well-known mathematical formulation of belief propagation is represented as:

In equation [1], for an N-dimensional system, {m{i,j}} represents a set of messages, {b{i,j}} represents the associated beliefs calculated from those messages, ψ{i,j}(xi,xj) is the compatibility matrix between nodes i and j, N(i)/j represents all nodes neighboring node i except node j, and α is a normalization constant. Ideally, the algorithm converges to a fixed point of the marginal density functions (i.e., a convergence solution), thereby enabling all clocks to be effectively synchronized.

However, certain aspects of the distributed network (e.g., the degree of initial clock variance) as well as how it is represented graphically can significantly impact synchronization results. For instance, inFIG.1, a simplified example of a distributed network is shown, the network being represented generally by reference numeral 11. For ease of illustration and understanding, network11is described herein as a Global Positioning System (GPS) constellation comprised of a plurality of satellites, or nodes,13-1thru13-6.

InFIG.2, GPS constellation11is represented graphically as model31, which incorporates edges5between pairs of nodes13that are in direct communication with one another. As can be appreciated, it has been found that the application of belief propagation algorithms to graphical models of the type shown inFIG.2does not always converge to a single solution.

Specifically, within graphical model31, a cluster of nodes13may form a closed loop, or cycle,17. Because a closed loop creates multiple communication paths between a single pair of nodes, the cluster may become overweighted in probabilistic calculations and, if unmitigated, can result in its synchronization information biasing global convergence properties and/or a node essentially synchronizing against itself. As a result, implementation of the synchronization algorithm often yields constant fluctuation in values and/or convergence to a spurious solution.

For this reason, node clusters within a probabilistic graphical model are often eliminated to reduce significance and impact. In the absence of loops in a graphical model, belief propagation algorithms are guaranteed to converge to a solution. For instance, inFIG.3, GPS constellation11is represented graphically as model51. As can be seen, graphical model51adopts a spanning tree approach, with all loops removed therefrom. In other words, communication between pairs of nodes13is restricted to a single connective path, or edge,15.

Although guaranteed to converge to a solution, applying synchronization algorithms to loop-free graphical models (e.g., model51) have been found to suffer from a couple notable shortcomings.

As a first shortcoming, synchronization algorithms applied to loop-free graphical models are sub-optimal with respect to algebraic connectivity. Due to its minimal algebraic connectivity, applying synchronization algorithms to loop-free modeling techniques necessitates a significantly greater number of mathematical steps to achieve convergence, particularly for larger sized constellations as well as greater initial timing variances between clocks. This significant increase in the number of mathematical steps required to achieve convergence necessitates a corresponding increase in the time required to complete computation, which is highly undesirable.

As a second shortcoming, synchronization algorithms applied to loop-free modeling techniques are rendered susceptible to dropout faults and Byzantine faults when any message-passing failure occurs between nodes. Because node failure is common in most synchronization applications, the faults must therefore be treated to ensure adequate results.

SUMMARY OF THE INVENTION

In view thereof, it is an object of the present invention to provide a novel method of clock synchronization for a distributed network.

It is another object of the present invention to provide a method of clock synchronization of the type as described above that consistently converges to a synchronization solution.

It is yet another object of the present invention to provide a method of clock synchronization of the type as described above that is of sufficient algorithmic complexity.

It is still another object of the present invention to provide a method of clock synchronization of the type as described above that is sufficient resilient to faults caused by message-passing failures.

It is yet still another object of the present invention to provide a method of clock synchronization of the type as described above that is relatively secure and reliable.

It is another object of the present invention to provide a method of clock synchronization of the type as described above which is easy to configure and inexpensive to implement.

Accordingly, as one feature of the present invention, there is provided a method of clock synchronization for a distributed network, the method comprising the steps of (a) representing the distributed network as a graphical model, the graphical model comprising a set of nodes, wherein selected pairs of nodes in direct electronic communication with one another are shown connected by edges, (b) dissecting the graphical model into a sequence of time-varying directed sub-graphs, each sub-graph connecting the selected pairs of nodes in direct electronic communication with one another using directed edges, wherein each sub-graph includes a selection of closed loops between the plurality of nodes, (c) determining the influence of each closed loop within each sub-graph, (d) dynamically identifying a selection of edges for deletion in the graphical model based on the influence of each closed loop within each sub-graph, the deletion of edges from the graphical model yielding an optimized graphical model, and (e) applying a synchronization algorithm to the optimized graphical model to calculate a clock synchronization solution.

DETAILED DESCRIPTION OF THE INVENTION

Referring now toFIG.4, there is shown a flow chart which represents a novel method of clock synchronization for a distributed, message-passing network, the method being implemented according to the teachings of the present invention and identified generally by reference numeral111. As will be explained in detail below, clock synchronization method111applies a novel time synchronization technique which evaluates the influence of closed loops within synchronization models and, in turn, dynamically maintains an optimized selection of the closed loops within the model during implementation of the synchronization algorithm. By maintaining an optimal subset of the closed loops within the model, method111is designed to ensure convergence to a synchronization solution, while, at the same time, limit susceptibility to faults as well as maintain a sufficient degree of algorithmic complexity in order to streamline the number of steps required to achieve convergence to the synchronization solution.

For ease of understanding, method111is described in relation to GPS constellation11. However, it is to be understood that the method of present invention is not limited to inter-satellite communications. Rather, it is to be understood that method111could be similarly implemented in other forms of distributed message-passing systems (e.g., radar systems, underwater systems, and the like) without departing from the spirit of the present invention.

As can be seen, method111commences with a graph dissection step113in which the graphical model for the distributed network in need of clock synchronization is represented as a sequence of time-varying directed sub-graphs. Referring now toFIGS.5(a) and5(b), a sequence of graphical models for GPS constellation11is shown which help illustrate graph dissection step113.

Specifically, inFIG.5(a), an illustrative time-varying directed sub-graph211of GPS constellation11is shown. As can be seen, in sub-graph211, directed edges215connect nodes13in GPS constellation11. Because edges215have a specified direction, a limited number of closed loops217are formed, with each closed loop217representing the presence of multiple communication paths between a pair of nodes13. In the present example, three closed loops217-1,217-2, and217-3are identified.

InFIG.5(b), an illustrative time-varying directed sub-graph231of GPS constellation11is shown. As can be seen, sub-graph231differs from sub-graph211solely in the direction of edge215-4. However, it should be noted that the change of direction for edge215-4yields a fourth closed loop217-4within sub-graph231. As will be explained further below, the ability to quantitatively compare differences between the individual sub-graphs (e.g., sub-graph211against sub-graph231) enables the effects of each loop to be measured.

Referring back toFIG.4, in step115, the influence of each loop within each of the various sub-graphs for GPS constellation11is explicitly quantified. By quantifying the effects of each loop, an optimized selection of loops can be dynamically maintained in the representative model for the designated network. In other words, heavily biased, or overweighted, local loops can be mitigated, while benign loops can be maintained. In this manner, the quantitative effects of useful loops are exploited by method111to ensure convergence to a synchronization solution, while limiting susceptibility to faults and minimizing the number of steps required to achieve convergence.

Using the loop quantification results, an edge deletion algorithm is applied in step117to identify a selection of edges for deletion within the graphical model for the designated network. Edge deletion step117is preferably implemented using the paradigm of hierarchical semiseparable (HSS) matrices as the relaxation in the optimal edge deletion algorithm. Similar to a standard binary tree structure, the preferred edge deletion algorithm prescribes ranges of ranks for various blocks within the corresponding HSS tree. However, the prescribed ranges of ranks are determined dynamically using randomized methods rather than from pre-computations, as HSS formalism is well suited to perform these types of computations.

Based on known attributes of HSS matrix algorithms, edge deletion step117has near-linear complexity with respect to the electronic messages passed in order to achieve solution convergence. Notably, using a small constant, k, which is equal to the maximum chromatic number of the adjacency graph for a constellation, the complexity of the number of time transfers for a given node of an HSS tree can be represented as:

By combining all nodes for an HSS tree, the following expression is reached, if suitable assumptions are made on the error distributions of the messages and non-pathological local geometries:

Accordingly, it is to be understood that the number of messages required to be passed by a network using method111in order to achieve synchronization is in the order of O(n log n), where n the is the number of nodes in the graph.

Upon completion of edge deletion step117, an optimized graphical model for the intended distributed network is defined. For example, inFIG.6, an optimized graphical model251for GPS constellation11is shown. As can be seen, an optimized selection of edges15remain between nodes13that ensure convergence to a synchronization solution with near-optimal algorithmic complexity.

Referring back toFIG.4, an optional error compensation step119may be incorporated into method111in order to ensure optimal synchronization convergence. For instance, message noise can be accurately modeled with a distribution function and therefore treated as part of compensation step119.

Finally, in step121, a clock synchronization algorithm is applied to the optimized graphical model to achieve convergence to a valid synchronization solution. By optimizing the graphical model for the intended network (i.e., by including an optimal set of closed loops), a standard belief propagation algorithm can be applied to the graph to yield the synchronization solution.

Illustrative Algorithms for Implementing Synchronization Method111

It should be noted that various algorithms could be designed to implement clock synchronization method111. For illustrative purposes only, sample synchronization algorithms are provided herein. However, it is to be understood that the algorithms shown below are provided for illustrative purposes only and are not intended to limit the scope of the present invention.

For any distributed synchronization application in which the connectivity of the distributed network has a known and periodic formulation (e.g., a GPS satellite constellation), the below algorithm would be particularly well suited to yield a valid synchronization solution:Input: Message dataMessage data error distributionPeriodic connectivity information(optimal) Positional data of physical nodes(optional) Tolerance for synchronizationOutput: Vector of synchronized data(1) Precompute relaxation parameters based on periodicity properties(2) while Convergence Condition A is not satisfied(3) Select node with highest connectivity; denote Node1(4) Re-order nodes based on their distance to Node1(5) Perform nested dissoction on adjacency graph(6) Generate list of allowable deletions from (1); let n=cardinality of this list(7) for i=1:n(8) Calculate spectral metrics for candidate function(9) end(10) Select candidate which minimizes spectral function(11) and(12) Perform standard belief propagation on augmented graphHere Convergence Condition A is as follows:

In certain applications, it is often desirable or necessary to select a subset of nodes within a graph to actively broadcast messages, with the remaining nodes designated to only receive messages. Restricting electronic message transmission to a subset of nodes is often preferred for, among other things, energy constrains, security concerns, and interpretability considerations. The following algorithm is uniquely designed to resolve this particular issue:Input: Periodic connectivity information.Output: List of nodes in subset(1) Form graph G(2) for i=1:7(3) for j=1:(31−i)(4) Form graph G{i}/j and calculate the smallest Laplacian eigenvalue(5) end(6) Delete node j the maximized and form G{(i+1}=G{i}/j(7) end

For any distributed synchronization application in which the connectivity of the distributed network has either (i) a known and periodic formulation or (ii) no known periodic formulation, the two aforementioned algorithms can be used as subroutines within the algorithm provided below to yield a valid synchronization solution:Message dataMessage data error distribution(optimal) Positional data of physical nodes(optional) Tolerance for synchronizationOutput: Vector of synchronized data(1) From the Laplacian matrix A for the satellite network(2) Transform A to banded form using nested dissection(3) for nodes (separators) i=1,2, . . . root(T)−1(4) Select transmitting satellites using generalization of Algorithm 2(5) if i is a leaf(6) Compute free energy of network represented by submatrix(7) else(8) Compute rank revealing QR decomposition of submatrix(9) end(10) end(11) for nodes (separators ) i=root(T)−1, root(T)−2, . . . , 1(12) if par(i)=root(T)(13) Partition orthogonal basis into a direct sum of trees(14) Message update sub-routine(15) Message normalization sub-routine(16) else(17) Re-compress larger submatrix(18) end(19) Perform Algorithm 1 on subgraph(20) end

Actual Test Results Achieved Using Synchronization Method111

As referenced above, clock synchronization method111ensures convergence to a synchronization solution, while limiting susceptibility to node faults and maintaining a near-optimal degree of mathematical complexity. For comparative purposes, method111was tested in relation to conventional clock synchronization algorithms which use either standard loop-inclusive or spanning tree techniques. The results of the aforementioned testing are detailed below. The following results are provided for illustrative purposes only and are not intended to limit the scope of the present invention.

Specifically, inFIG.7, a graph is shown which illustrates various clock synchronization techniques applied to a set of test parameters, the comparative graph being identified generally by reference numeral311. In graph311, the results of each synchronization technique are represented along vertical axis313in terms of steps to convergence and along horizontal axis315in terms of initial variance between node clocks (i.e., time transfer error).

As can be seen, a standard spanning tree algorithm317reaches convergence to within 100 ps in a reliable fashion, but often requires a considerable number of steps (i.e., processing time). Furthermore, it can be seen that a conventional loop-inclusive, belief propagation algorithm319is unable to achieve convergence for test networks with time variance greater than 300 ps.

By comparison, an algorithm321designed to implement synchronization method111is able to achieve convergence within the same range of time transfer errors as spanning tree algorithm317but at approximately half the number of steps. In other words, method111produces the same degree of convergence reliability as synchronization protocols which adopt a spanning tree approach but at a considerably faster rate of convergence.

InFIG.8, another graph is shown which illustrates various clock synchronization techniques applied to a set of test parameters, the comparative graph being identified generally by reference numeral331. In graph311, the results of each synchronization technique are represented along vertical axis333in terms of steps to convergence and along horizontal axis335in terms of constellation size (i.e., number of nodes in the test network).

As can be seen, a standard spanning tree algorithm337reaches convergence to within 100 ps in a reliable fashion but requires a significantly greater number of convergence steps as the constellation size increases. A theoretical lower bound graph339is provided to help illustrate the relative ineffectiveness of spanning tree algorithm337with networks which are moderately large in size.

By comparison, an algorithm341designed to implement synchronization method111is able to achieve convergence at the same approximate rate as theoretical lower bound graph339across all constellation sizes. As a result, method111can be regarded as being highly scalable.

InFIG.9, a graph351is shown which illustrates the fault tolerance of method111, graph351being represented along vertical axis353in terms of steps to convergence and along horizontal axis355in terms of the number of faulty nodes in the test network. As can be seen, an algorithm357designed to implement synchronization method111is able to achieve convergence even with a limited number of faulty nodes. However, as the number of faulty nodes increases, a commensurate number of additional steps is required in order to achieve solution convergence to 100 ps.

In view thereof, method111appears to be sufficiently resilient to faults. In fact, it has been determined that as long as at least two-thirds of the network nodes continuously provide uncorrupted data, the synchronization algorithm of the present invention will converge to a valid synchronization solution.