## 6 Fully-Distributed Clock Synchronization Algorithms
### Fully-Distributed Clock Synchronization Algorithms under Gaussian Delays
#### 6.2.1 Belief-Based Synchronization Algorithms  
Existing fully-distributed algorithms in [22; 46; 47] are based on the belief propagation method in the Bayesian framework. Under the assumption of Gaussian random delays, [46] proposed a belief-based algorithm to estimate the clock offset in a distributed manner. Specifically, the system model is modified by adding Equation (47)-(48), and it leads to:  
\[T_{\{i,j\},n}\stackrel{{\triangle}}{{=}}c_{j}(t_{n}^{2})+c_{j}(t_ {n}^{3})-c_{i}(t_{n}^{1})-c_{i}(t_{n}^{4})=2\theta_{j}-2\theta_{i}+Z_{n} \tag{49}\]  
where \(Z_{n}\stackrel{{\triangle}}{{=}}X_{ij}-X_{ji}\). Stacking all of the observations in a vector as \(\mathbf{T}_{i,j}=\left[T_{\{i,j\},1},\cdots,T_{\{i,j\},N}\right]\) leads to the likelihood function denoted as \(p(\mathbf{T}_{i,j}|\theta_{i},\theta_{j})\). In the Bayesian scenario, the clock offset of  
Figure 4: Two-way message exchange between nodes \(i\) and \(j\). each sensor node, denoted as \(\theta_{i}\), is regarded as a random variable with prior distribution \(p(\theta_{i})\). The estimate is obtained by maximizing the posterior distribution of the clock offset. The posterior distribution of \(\theta_{i}\) for a network with only two nodes \(i\) and \(j\) is expressed as:  
\[g_{i}(\theta_{i})=\int p(\theta_{i},\theta_{j}|\mathbf{T}_{i,j})d\theta_{j} \propto\int p(\mathbf{T}_{i,j}|\theta_{i},\theta_{j})p(\theta_{i})p(\theta_{j} )d\theta_{j}\]  
Extending the above idea to a WSN with \(M\) sensor nodes, the posterior distribution of clock offset \(\theta_{i}\) is expressed as:  
\[g_{i}(\theta_{i})=\underset{\theta_{1},\cdots,\theta_{i-1},\theta_{i+1}, \cdots,\theta_{M}}{\int\cdots\int}p(\theta_{1},\cdots,\theta_{M}|\{\mathbf{T}_ {ij}\}_{i=1,\cdots,M,j\in\beta_{i}})d\theta_{1}\cdots d\theta_{i-1}d\theta_{i+ 1}d\theta_{M} \tag{50}\]  
where \(\beta_{i}\) stands for the indices of neighboring sensors of node \(i\). It can be seen that the joint distribution depends on interactions among all of the variables, and the integration is almost impossible to calculate. Therefore, belief propagation (BP) is employed to compute the posterior distribution without fully integrating Equation (50). BP takes advantage of the graphical model structure. Factor graphs represent one of the most widely used graphical models and have been adopted in [46]. An example of a factor graph for two nodes \(i\) and \(j\) is depicted in Figure 5. The two sensor nodes \(i\) and \(j\) are represented in terms of the variable nodes (circles), and they are connected to a square factor node \(\gamma_{ij}\), which stands for the likelihood function \(p(\mathbf{T}_{ij}|\theta_{i},\theta_{j})\). On the other hand, nodes \(i\) and \(j\) are also connected to factor nodes \(\gamma_{i}\) and \(\gamma_{j}\), which represent the prior distributions of \(\theta_{i}\) and \(\theta_{j}\), respectively. During each iteration, _i.e._, for the iteration \(l\), the BP algorithm in [46] is carried out via the following three steps:  
1. Each variable node \(\theta_{i}\) transmits its current belief \(b_{i}^{(l)}(\theta_{i})\) to all of its neighboring factor nodes \(\{\gamma_{ij},j\in\beta_{i}\}\). 2. Acting like an intermediate node, the message from a factor node \(\gamma_{ij}\) to a variable node \(\theta_{i}\) is calculated based on the belief received from \(\theta_{j}\): \[m_{\gamma_{i,j}\rightarrow\theta_{i}}^{(l)}(\theta_{i})=\int p(\mathbf{T}_{i, j}|\theta_{i},\theta_{j})b_{j}^{(l)}(\theta_{j})d\theta_{j}\] (51)
3. After variable node \(\theta_{i}\) receives all of the messages from its neighboring factor nodes, _i.e._, \(\{m_{\gamma_{i,j}\rightarrow\theta_{i}}^{(l)}(\theta_{i})\}_{j\in\beta_{i}}\), it updates its belief \(b_{i}^{(l+1)}(\theta_{i})\) as follows: \[b_{i}^{(l+1)}(\theta_{i})=p(\theta_{i})\prod_{j\in\beta_{i}}m_{\gamma_{i,j} \rightarrow\theta_{i}}^{(l)}(\theta_{i})\] (52)If no prior information is given about \(p(\theta_{i})\), we set \(p(\theta_{i})\) to a Gaussian PDF with zero mean and very large variance.