# Randomized and Efficient Time Synchronization in Dynamic Wireless Sensor Networks: A Gossip-Consensus-Based Approach

Authors: Nan Xiong; Minrui Fei; Taicheng Yang; Yu-Chu Tian
Journal: Complexity
 (2018)

---

## Abstract

This paper proposes novel randomized gossip-consensus-based sync (RGCS) algorithms to realize efficient time calibration in dynamic wireless sensor networks (WSNs). First, the unreliable links are described by stochastic connections, reflecting the characteristic of changing connectivity gleaned from dynamic WSNs. Secondly, based on the mutual drift estimation, each pair of activated nodes fully adjusts clock rate and offset to achieve network-wide time synchronization by drawing upon the gossip consensus approach. The converge-to-max criterion is introduced to achieve a much faster convergence speed. The theoretical results on the probabilistic synchronization performance of the RGCS are presented. Thirdly, a Revised-RGCS is developed to counteract the negative impact of bounded delays, because the uncertain delays are always present in practice and would lead to a large deterioration of algorithm performances. Finally, extensive simulations are performed on the MATLAB and OMNeT++ platform for performance evaluation. Simulation results demonstrate that the proposed algorithms are not only efficient for synchronization issues required for dynamic topology changes but also give a better performance in terms of converging speed, collision rate, and the robustness of resisting delay, and outperform other existing protocols.


---

## Body

## 1. Introduction

Ad hoc wireless sensor networks (WSNs) without preexisting infrastructures are composed of autonomous sensors [1], and the sensors are a variety of low cost, low power, sensing devices, which work cooperatively through ad hoc wireless communications. In WSNs, many kinds of missions [2, 3], such as transmission scheduling, event sequencing, information fusion, and distributed filtering, rely heavily on a consistent notion of time to keep running orderly. For instance, Internet of Things’ perception layer provides a ubiquitous access to the network, in which the multiple terminals collaborate closely with each other, and accurate synchronized clocks determine whether a multiterminal cooperation is accomplished or not. Therefore, timing protocols, which should concern with topologies, time delays, low power consumption, and so on, is the premise of dealing with services of ad hoc WSNs.Two configurations of timing protocols are available: hierarchical and distributed. Cluster-based and tree-based protocols would both fall into the hierarchical configuration, because they perform a special operation; that is, some designated nodes are elected to be the reference (such as cluster head, root, and master). The typical hierarchical timing protocols include the one-way message dissemination schemes [4], two-way message exchange schemes [5], flooding schemes [6], pairwise broadcast synchronization (PBS) [7], and reference broadcast synchronization (RBS) [8]. Based on the message passing and filter methods, most of the works have built an estimation and tracking framework for the time synchronization problem, but these prototypes are not purely decentralized in nature. The hierarchy structure of a network consists in the logical master–slave relationship which is maintained by an actual infrastructure. The timing messages in this structure are delivered from top to bottom, while each node is labeled an equal identity tag in a distributed configuration. In the absence of a preexisting infrastructure, the distributed configuration is obviously more suitable to WSNs.Recently, based on distributed consensus algorithms [9, 10] of multiagent networks, consensus-based approaches for designing distributed timing protocols [11–21] have received a lot of attention in WSNs. These protocols utilize local information to achieve global synchronization and easily adopt to WSNs’ distributed sensor property with computational lightness. However, the common drawbacks of existing consensus-based timing protocols are as follows:
(1)
The changing connectivity is rarely considered [17]. In dynamic WSNs, it is not possible to deterministically forecast the activating timeslot of sensors due to the uncertainties of nodes, such as uncontrollable mobility, sleep scheduling, heterogeneous nodes with various coverage levels, and so on. Radio signal fading caused by environmental turbulence can also severely corrupt the performance of wireless links. The nodes in the design of the consensus-based timing protocols sequentially update their own clocks whenever they receive a timing message from a geographical neighbor [11]. Because the logical rate represents the slope of the linear logical clock model, each node i is required to build a fixed link with the same neighboring node in order to collect timing messages and estimate the relative drift. In the MTS [12], the authors assume that a larger B is used to keep link i,j constant during a time interval kB,k+1B. Although it enables the MTS to behave robustly to work against topology changes, in highly dynamic topology this assumption will be unrealistic. This is because at a timeslot t1, node i can exchange timing messages with a neighbor only once to obtain clock reading. At the next timeslot t2, the link i,j will lose the connection. More generally, any pair of nodes “gossip” only once in one timeslot. Thus, the randomly changing connectivity between adjacent nodes renders efficient relative drift estimation challenging. This problem will directly affect the implementation of the logical clock rate and offset compensation, and become more paramount as the change of connected relation of WSNs gets faster. On this issue, the existing consensus-based timing protocols can be classified into two categories: (1) deterministic synchronization, which relies on a fixed link, such as [11–18]; and (2) randomized synchronization, such as [19–21]. Brown et al. [19] investigated the transient consensus behavior of the random pairwise consensus synchronization (RPCS) algorithm. It is a pity that the reciprocal delay model is supposed to be symmetric. Sun et al. [20] proposed a randomized method to deal with the random access problem. The method proposed therein combines a partial-update rule with a complete-update rule. However, the partial-update rule is capable of compensating the offset in nondeterministic instants which results in incompletely compensating the clock rate. Bolognani et al. [21] proposed a randomized linear algorithm for the second-order consensus timing protocol. This algorithm is based on the average-value-based criterion, which have a slow speed of convergence.
(2)
The speed of convergence may be relatively slow. A major concern is the lower convergence speed which increases the message complexity and consumes the limited power of the sensor nodes. However, many protocols [11, 13–16, 19–21] are proposed based on the average-value-based criterion, which need more iterations to achieve acceptable synchronization error.
(3)
The delay model is unrealistic. Several protocols suppose the uplink delay and the downlink delay among two nodes are symmetric [13, 19] or obey a statistical delay model [12, 14], such as normal distribution and Gaussian distribution. Worse still, the uncertainty regarding the delay is associated with the influence of the exterior environment.
(4)
The common broadcast period would give rise to the timing message collision as pointed out in publications [11, 18, 20], but without being handled. The existing consensus-based timing protocols employ a deterministic communication protocol, in which each node is allowed to communicate with its neighboring nodes that are within its range in each deterministic timeslot. Due to the hidden node problem [22], the collisions become too serious to be further ignored since a exposed node receives multiple timing messages from hidden nodes with a common broadcast period during the same timeslot.The critical fact that the real-world delays would change irregularly, and the more iterations and collisions would waste energy, has a negative effect on synchronization performances. Inspired by the rumor spreading of human groups and the way how epidemics spread, gossip algorithm [23, 24] has been widely investigated in the information theory community for information dissemination. In the context of the multiagent networks, randomized gossip algorithm is attractive for solving the distributed and stochastic consensus problems [25–27] due to its randomized behavior and asynchronous processing. Faced with the dynamic topology issue, the gossip consensus provides less conservatism and higher efficiency than the existing consensus approach. So they are perceived as uniquely suited for the inherent dynamics of ad hoc WSNs whose topology is randomly connected. The gossip consensus approach contains two dimensions: gossip interaction and gossip update. The gossip interaction mode is particularly well suited for applications into wireless peer-to-peer and ad hoc sensor networks, where a random pair of nodes is active at each iteration and that it out-syncs itself is a prior fact. In addition, randomized gossiping may allow communication asynchronously at random times to lower the probability of message collisions. The gossip update policy is that each node has to share its output with one of the neighboring nodes. That being said, privacy issues could easily apply to a node which participates in such updating. On the contrary, the existing consensus approach allows a node to share its output with multiple nodes, so privacy issues could discourage some nodes from participating in such updating. Therefore, under a more practical delay model, it is of great interest to study randomized gossip algorithm for achieving the generalized consensus timing protocol that has faster convergence speed and lower collision rate in dynamic WSNs.Motivated by these, this paper presents an innovative randomized and efficient timing protocol for dynamic WSNs, including the mutual drift estimation, clock rate and offset compensation. The key novelty of the contribution lies in a randomized algorithm for the extension of the generalized consensus-based timing protocol which implements probabilistic synchronization using randomized gossip-type interactions and updates. To achieve this goal, for the first time, we design the idea of the randomized activation of the synchronization links based on the preprogrammed Poisson process to activate a pair of nodes, and use the gossip-consensus-based approach with the converge-to-max criterion to fully adjust the clock rate and offset of random pairwise nodes. Moreover, by exploiting a least square-based low-pass filter, a revised version is improved to cope with the bounded delays.The major contributions of this paper are summarized below:(i)
We first ignore the time delays and propose a novel randomized gossip-consensus-based time synchronization (RGCS) protocol by incorporating the idea of randomized gossip algorithm into the consensus-based timing protocol. Compared to traditional mechanisms, the gossip consensus is achievable in a fully decentralized, randomized, and asynchronous fashion, even in highly dynamic WSNs. The converge-to-max criterion is introduced to achieve finite-time convergence, since the gossip consensus is a not fast convergence algorithm. Then, we prove that the expected logical clocks are synchronized with probability one (w.p.1), and provide a lower bound of fast finite-time convergence. In addition, we develop a Multi-RGCS protocol based on the principle of the edge-coloring (EC) technique to save finite-convergence time.
(ii)
We consider the case where the delay obeys a realistic bounded model compared to the particular distribution communication delay model, and further propose a Revised-RGCS protocol to work against the uncertain bounded time delays. The filter proposed therein is competent to deal with practical delays which could be a basic constraint in the drift estimation issue over real-world WSNs.
(iii)
We conduct performance evaluations of the proposed protocols through extensive simulation experiments using the MATLAB and OMNeT++. Simulation results demonstrate that RGCS fully adjusts logical rate and offset to achieve network-wide synchronization for randomly connected WSNs, and Revised-RGCS gives a better performance in terms of collision rate, converging speed, and the robustness of resisting delays compared to other existing protocols.The rest of this paper is organized as follows. In Section2, we review the related literatures and state the novelty with respect to the previous works. Section 3 formulates the time synchronization problem. Section 4 elaborates the proposed RGCS, Multi-RGCS, and Revised-RGCS. The simulation results are given in Section 5. Section 6 concludes the paper.


## 2. Related Work

In the absence of preexisting infrastructures, distributed configuration is a promising paradigm for distributed WSNs. Within this context, tremendous research efforts have already been devoted to distributed timing protocols. Based on belief propagation, a fully distributed timing protocol [28] developing from the two-way sender–receiver synchronization scheme was used for the joint estimation of rate and offset. Distributed asynchronous Clock Synchronization (DCS) [29] protocol was proposed for delay-tolerant networks. DCS can achieve global time synchronization among mobile nodes over intermittent connections with long delays, but the rate and offset are adjusted separately. Ahmed et al. [30] considered unreliable links to build an asynchronous framework, but it is the same as an RFA without rate compensation. An On-demand Time Synchronization Protocol (AOTSP) [31] was proposed with the advantages of weak spatial accumulative effect, low communication cost, and high scalability. However, AOTSP suffers from a temporal accumulative effect on account of exchanging timestamps.In recent years, distributed consensus concept [9, 10] has become a hot topic in the distributed time calibration research. Distributed timing protocol based on the idea of the consensus algorithm was originally achieved with the Average TimeSynch (ATS) [11] protocol which fully compensates clock rate and offset. To accelerate convergence speed, the Maximum Time Synchronization (MTS) [12] protocol was developed by which the system trajectories of rate and offset are updated to achieve the maximum-value under a normal distribution delay model, and Saiah et al. [14] proposed the Consensus-based Multi-hop Time Synchronization (CMTS) protocol under the Gaussian delay model. Panigrahi and Khilar [13] proposed a multiobjective evolutionary strategy-based topological optimization for the consensus timing protocol to deal with a trade-off between the minimizing of delays and the selection of sync initiating nodes, but the delays are assumed to be symmetric. The other improved protocols include the Robust-ATS (RoATS) [15] and Least Square estimation-based Time Synchronization (LSTS) [16] aiming at the delays. Recent works contributed by Tian et al. [17] presented a very generalized model of the Consensus-based Time Synchronization (CBTS) algorithm without topological conditions. However, the RoATS, LSTS, and CBTS designed for distributed WSNs with delays are static scenarios and ignore the changing connectivity of dynamic WSNs. Brown et al. [19] investigated the transient consensus behavior of clock parameters in the Random Pairwise Consensus Synchronization (RPCS). Similar to DCS, RPCS adjusts rate and offset separately. He and Dong et al. investigated consensus timing protocol under message manipulation attacks [32] and sybil attacks [33], respectively. In order to address the topology change issue, the MTS protocol supposes that link i,j should be kept constant within a time width B; however, in a highly dynamic topology, this assumption is unrealistic. Sun et al. proposed the Random Broadcast-based Distributed time Synchronization (RBDS) [20] protocol based on the random access mechanism, which combines the partial-update rule with the complete-update rule. However, the partial-update rule is capable of compensating the offset in a nondeterministic timeslot which results in incompletely adjusting the drift. Based on the gossip consensus, we relax the basic condition of the MTS (that is, compared with the MTS, we do not need link i,j kept constant during a time interval kB,k+1B to collect the clock states more than once) and also enable complete-rate and complete-offset compensation.There has been a surge of activity in ad hoc WSNs using the idea of gossip protocols. Specific to time synchronization, Marechal et al. [34] proposed a distributed gossip protocol for only adjusting natural clock drifts. Bolognani et al. proposed a Proportional Integral (PI) synchronization controller [35] with gossip communication mode for time synchronization. The PI controller proposed therein takes advantage of the asynchronism of pairwise-exchange communication. Coupling-based internal Clock Synchronization (CCS) [36] which combines the gossip paradigm with a nature-inspired approach was proposed to cope with disturbance. The logical clock in the CCS is equal to the hardware clock plus an adjustment. This is a special case of our logical clock model which has both multiplicative and additive compensation. Joerg et al. [37] proposed a hybrid protocol for distributed microphones over a wireless network, which integrated the two-way message exchange mechanism with the gossiping technique. The idea of gossiping used therein mainly seeks a virtual master clock. Based on broadcast gossiping, Stankovic et al. [38] proposed two instrumental variable-type distributed recursions for estimating parameters of calibration functions with a general noise assumption. A concern regarding distributed recursion is their excessive use of communication, while the nodes of randomly connected networks can only communicate with its immediate neighbor in an opportunistic manner.In summary, some of the above algorithms only compensate offset or rate [27, 30, 34], and other algorithms compensate offset and rate separately [4, 19, 29, 37]. Several algorithms reconstruct clock parameters and perform reverse reconstruction to align absolute time, so they usually introduce more computational complexity [4, 30, 37]. The distributed nature of the consensus-based timing protocols is superior to other timing protocols, but the message collision rate is relatively high. In particular, node i announces a timing message when the hardware clock τi or logical clock Ti is such that there exists an integer Ψ satisfying τit=nΨ or Tit=nΨ+ϕi, n=1,2,3,…,N. There is a high probability of a timing message collision event in algorithmic mechanisms when the hardware parameters or bias ϕ are converging closely for at least two unidentified and hidden nodes [11, 12, 18, 20, 33]. In addition, many algorithms [11, 13–16, 18–21, 34] are still average-value-based algorithms, which have a slow speed of convergence. Worse still, under significant clock drifting, the average information will remove after a few iterations with a slow speed of convergence. Hence, taking the above reasons into consideration, energy-efficient time synchronization for dynamic WSNs may not be achieved by these consensus-based timing protocols. The major advantage of the gossip idea is that the iterative dynamics appear as a randomized and asynchronous evolution, so that it is quite convenient for asynchronous network and topological changes. Nevertheless, the main drawbacks of the aforesaid gossip-based protocols have been analyzed from the compensation quantity, the excessive use of communication, and so on.So, taking a hybrid approach, we first proposed the RGCS algorithm without considering the delays, which combines the advantage of the randomized gossip algorithm and consensus-based TimeSync. The algorithm fully adjusts rate and offset, and also fits into the dynamic topology of randomly connected WSNs with lower collision. The converge-to-max criterion was introduced to choose the coefficients properly in order to enable fast convergence. A Revised-RGCS algorithm was developed by adopting the least square-based low-pass filter to counteract the impact of bounded delays. Summing up the works for comparison in this section, the features of representative distributed timing protocols are summarized in Table1. Our time synchronization properties include:
(i)
Rate and offset synchronization. Each clock rate and offset should be fully adjusted to achieve a common virtual clock.
(ii)
Compatible with dynamic topology changes. A time synchronization protocol has to explore the changing connectivity to design compensation rules.
(iii)
Energy-efficient. The number of message collisions should be small. Synchronization should be finished within a limited time, since the gossip consensus is a not fast converging algorithm.
(iv)
Robustness against bounded time delays. The bounded convergence should be guaranteed even when bounded uncertain delays are present.Table 1
The comparison of representative distributed timing protocols.
Dynamic topology
Delay
Iterative way
Interference
Rate
Offset
MTS [12]
Yes
Yes
Max
High
Yes
Yes
RoATS [15]
No
Yes
Average
High
Yes
Yes
RPCS [19]
Yes
Yes
Average
High
Separate
Separate
RBDS [20]
Yes
No
Average
High
Incomplete
Yes
RFA [27]
No
No
—
Low
No
Yes
DCS [29]
Yes
Yes
Average
High
Separate
Separate
AOTSP [31]
No
Yes
—
Low
Yes
Yes
CCS [36]
No
Yes
Average
Low
No
Yes
Ours
Yes
Yes
Max
Low
Yes
Yes


## 3. Problem Formulation

SupposeN sensor nodes of a WSN indexed by i=1,2,…,N. Owing to the node dormancy or death and random failure of links, a successful contact between a pair of nodes i and j depends on the probability distribution of the setup of stochastic links. Thus, the topology of dynamic ad hoc WSNs is modeled as a time-varying graph Gt=V,ℰt. V is the set of vertices, and the existence of stochastic links ℰt=eijt∣i,j∈V is determined independently. The set of node i’s neighbors is denoted by Ni=j∈V,eij∈ℰt. We use a notation ij to indicate eij which means node i and j happen to link together, and the undirected random graph is bidirectional.Definition 1.
A synchronization linkij or eij means that an arbitrary random node i is coupled with its geographical neighbor j∈Ni once to perform a synchronous operation. Specifically, triggering node i sends a beacon to choose the triggered neighbor j and confirm the ID of the synchronization link eij; then, they swap timing messages with each other. Due to the randomized activation of nodes, we need a neighbor discovery protocol for nodes to discover each other when they are neighbors.
Fortunately, a simple and useful neighbor discovery protocol can be used as in [39].Assumption 1.
When nodeii∈V is activated at time t, the cardinality Nit≥1.Assumption 2.
The delays of thelth uplink and downlink communication between node i and j is denoted by dij and dji. They are unequal and bounded by upper bound D; that is, 0<dij<D, dij≠dji.The oscillator generates the standard unit of frequencyΩ. The clock provides its reading τt of the elapsed absolute time t by accumulating the number of impulsive signals τt=κ∫totΩεdε+τt0, where κ is an oscillator frequency correction. The oscillation frequency is nearly invariable in a short time horizon, so the clock reading of the ith node possesses a linear dynamic behavior such as
(1)τit=ait+bi,where ai and bi are the hardware clock rate and offset, respectively. ai determines the timing rate of the clock and bi represents the difference of the nodes’ clock reading. The logical clock is a linear affine function of τit. αit is a multiplicative compensation and βit is an additive compensation, as follows:
(2)Tit=αitτit+βit=α~itt+β~it,where α~it=aiαitandβ~it=αitbi+βit are called the logical rate and offset, respectively. So, we have available quantity τit, and two variables αit, βit to be designed.The objective is to design a randomized communication protocol and a gossip-consensus-based approach for coupled nodesi, j∈V announcing its timing messages and adjusting the logical rate and offset, such that the logical clocks Tii∈V is synchronized in the probability sense, as follows:
(3)∀i,j∈V,∃Prlimt→∞Tit−Tjt=0=1.Finally, notationPr, o, O denote probability, infinitesimal of higher order, and infinitesimal of the same order, respectively.


## 4. RGCS, Multi-RGCS, and Revised-RGCS Algorithms

### 4.1. RGCS Algorithm

#### 4.1.1. Randomized Communication Protocol

A randomly connected ad hoc WSN is specifically characterized in that the nodes are randomly activating and sleeping, and the RGCS algorithm is supposed to run independently in each individual node. Firstly, the Poisson process is configured to each node in order to generate the synchronization link (Sync-L) beacon which is sent to a node of its neighborhood by exploiting the broadcast nature of wireless communications. Thus, the randomized activation ofeiji,j∈V satisfies the Poisson process with the constant intensity λij such that Prtijl+σ−tijσ=n=λijln/n!eλijl, n=0,1…, for ∀l, σ≥0. Some special circumstances are as follows: if λij=0, it means link eij is not activated forever, and if λij=∞, it means link eij is activated infinitely in a given time interval. The Sync-L beacon between node i and j is confirmed, which is referred to the stochastic link activation event. Once the randomized activation of link eij takes place, by using the Media Access Control (MAC) layer time stamps, triggering node i pushes a multivariable message αitlij,βitlij,τitlij to node j. After that, the triggered node j pulls a multivariable message αjtlij,βjtlij,τjtlij to node i. The overall procedure is illustrated in Figure 1.Figure 1
The Sync-L beacon and timing message exchanges in a dynamic wireless sensor network.Thus, accordingly, the set of activated synchronization links∪i=1,j=1Neijt are an identically and independently distributed (i.i.d.) Poisson distribution. Suppose that function ℱN represents the amount of synchronization links of an underlying graph. When it is a complete graph, we can maximize ℱN as NN−1/2. Clearly, the set ∪l=0∞∪i=1,j=1Ntlij∣eij∈Et satisfies global Poisson distribution with the intensity ℱNλ, because all intensities have the same value. Each global gossip instantly corresponds to an updating event. We denote ∆l,ij as the intertime between consecutive gossip instants for the global Poisson process, and Δl,ijl∈N,ij∈Et is an i.i.d. process with moments
(4)EΔl,ij=1ℱNλ,EΔ2l,ij=2ℱNλ2.The intensityλ increased, whereas ∆l,ij continuously decreased. The physical significance of λij represents the intermittent of activation events of link eij, and the mathematical meaning of λij represents the mean value of the occurrence of the activation events per unit time. In many scenarios, environmental-temperature variations will be slow to change around nodes. Hence, we can do that by increasing intensity λij to enlarge the frequency of a link activation event in order to work against slowly changing drifts.As shown in Figure2, we illustrate how the proposed mechanism works under the hidden node problem. Node A is visible from node B, and node C is visible from node B too. However, node A and node B cannot sense with each other, because they are out of the communication zone of each other. In the deterministic communication protocol (such as ATS, MTS, RoATS, etc.), each node transmits its timing messages periodically with a common period based on its own clock on chip. If nodes A and B have a small difference in terms of the hardware rate and offset, they will announce timing messages to node C simultaneously. Thus, the collisions will occur endlessly. In our proposed mechanism, each node announces a timing message asynchronously based on its preprogrammed Poisson process, and random pairwise node delivery timing messages in the uplink and downlink successively. So node A randomly gossips, then a sync timeslot is established between nodes A and C with probability PrtlAC. The sync timeslot between nodes B and C is established with probability PrtlBC. The Poisson intervals δAC and δBC are independent of each other. If the transmission delay is negligible, the width of the sync timeslot can be narrow such that the probability of collisions will further down. Hence, with an appropriate λ, the probability of collisions is lower than that in the deterministic communication.Figure 2
Illustration of the proposed randomized communication under the hidden node scene.To defend against message manipulation attacks, secure consensus timing protocols should contain a detecting and excluding outlier mechanism for the logical clock checking and hardware clock checking. From the analysis of logical clock checking mechanism in the literature [32], we know that the bounded communication cycle which was determined by Ψ∣τit=NΨ,N=1,2,…,Ψ>0 is a pivotal parameter of the secure protocols. However, the authors suppose Ψ is invariable under malicious modification with the purpose of preventing the attack nodes using outdated receiving information to cheat, that is, it makes nodes to collect messages from neighboring nodes within a constant duration. The proposed gossip interaction mode which has less conservatism to topology changes can remove this limitation properly. Also, Ψ is the key parameter which contributes to represent the conforming relationship of Definition 1 in the literature [33] to defend against a sybil attack, and RGCS is robust to the distortion of the bounded communication cycle.


#### 4.1.2. Gossip Consensus Approach for Clock Rate and Offset Compensation

LetΔSiij be the difference of hardware clock readings τi of triggering node i in gossip instant tlij and tl−1ij, namely, ΔSiij=τitlij−τitl−1ij. The main idea of the updating rule is to utilize the gossip consensus approach based on the interchange of the gossiping neighbors’ messages. Triggered node j updates its logical rate α~jt and offset β~jt by averaging them with the estimates of its gossiping neighbors, namely, a~jtl+1ij=1−ρ1a~jt~kj+ρ1a~itlij. Each node consists of estimating the logical rate with respect to the virtual consensus rate, and local node j stores a new compensation αj. Then, by dividing αj at both sides of above equation, we have
(5)ajtl+1ij=1=ρ1ajt~kj+ρ1aiajaitlij,where ρ1∈0,1. The constant ρ1 defines the degree of change of compensation α in gossip instant tl+1ij. If ρ1 is set to a small value, the average information will be removed in a few updates. Additionally, due to the discrete observations of the relative drift, we can increase ρ1 to guarantee the stationarity of the estimated α. Based on the above analysis, the converge-to-max criterion is applied to t~kj. The time, t~kj, indicates the previous gossip instant of arbitrary edges which contain node j just before activated edge eij’s lth gossip instant. Equation (5) counts the absolute time on two scales, that is, updating the usage round and communication round, to avoid confusion between the updating iteration and the gossiping communication. Scrupulously, t~kj is given as follows:
(6)t~kj=maxtsjp,trqjtsjp<tlij,trqj<tlij;p,q=1,…,n;s,r=1,2,….When the Sync-Leij is activated in the next gossip instant tlij, node i uses τitl−1ij which would be stored in the flash memory of sensors to compute the number of drift, namely, the relative drift ajitlij for node j is computed by
(7)aiaj=ajitlij=ΔSiijΔSjij.During all iterations, each nodei’s storage is ONi for all possible synchronization links. It implies that, even though the size of the network node increases, the storage complexities of the RGCS per node per iteration will not grow. This property ensures the scalability of the algorithm.Substituting (7) into (5) yields the update equation of compensating αj. Again, based on the converge-to-max criterion, we design the rate compensation iteration rule of random pairwise nodes. In this rule, the rate compensations of triggering node i, triggered node j, and silent nodes evolve as follows
(8)ajtl+1ij=maxajt~kl,ajitlijaitlij,aitl+1ij=maxait~ki,aijtlijajtlij,asilenttl+1ij=asilentt~ksilent,which means that random pairwise nodes i and j reach the maximum logical clock together at a random gossip instant tl+1ij, and other nodes are silent. In (8), node i and j sequentially iterate its own estimated logical clock only once per gossiping interaction. Observing that whether t~ki and t~kj will be different or the same depends on the contiguous activation of the Sync-L of global Poisson process. After the rate compensation is applied, the random pairwise nodes compute the instantaneous estimated logical clock difference Titlij−Tjtlij and try to adjust its offset β in order to reduce the difference. Once again, the gossip consensus approach and the converge-to-max criterion are applied to local node i, j, and silent nodes for attaining offset compensations, as follows
(9)βjtl+1ij=βjt~kj+ρ2Titlij−Tjtlij,βitl+1ij=βit~ki+ρ2Tjtlij−Titlij,βsilenttl+1ij=βsilentt~ksilent,where ρ2=1 and Titlij=αitlijτitlij+βitlij. The flowchart of the RGCS algorithm is shown in Figure 3(a), and the basic procedures are described as follows: Step 1. Randomly initialize each local clock τi. Step 2. Judge whether arbitrary node i activates its neighbor or not, or whether it is activated by its neighbor or not. Step 3. Perform update equations (6), (7), (8), and (9). Step 4. Judge whether to meet the sync accuracy or not. Otherwise, return to Step 2.Figure 3
Flowchart of the proposed algorithms. (a) Randomized Gossip-Consensus-based time Synchronization (RGCS). (b) Multi-RGCS.
(a)
(b)


#### 4.1.3. Convergence of RGCS

Substituting (2) into (3) yields an intuitive translation of the time synchronization issue:
(10)Prlimt→∞a~t=av=1,∀i∈V,Prlimt→∞β~it=bv=1,∀i∈V,Pra~it−a~jt=o1t,∀i∈V,where av and bv are the parameters of a consistent virtual clock. Equation (10) shows that whether the clocks achieve synchronization or not depends not only on the convergence of the logical rate and offset, but also on the convergence speed of the logical rate errors Prα~it−α~jt, because errors will tend to diverge if the convergence speed to zero of Prα~it−α~jt is slower than 1/t.Theorem 1.
Consider the rate and offset update equations given by (6), (7), (8), and (9), and there exist two variables ∆>0 and l>0 such that the union graph Gtlij,Δl,ij=∪ij∪lGtlij for ∀eij∈ℰt is connected with probability one. Then, (10) holds true.Proof 1.
Firstly, two functionsVvt and Vvt are introduced, where Vvt is the set of nodes whose logical rate and offset are equal to av and bv in instant t, and Vvt is the cardinality of set Vvt. Define amax=maxai,∀i∈V, let node v be the node whose clock rate is equal to amax. According to the initial sets, there is at least one node in the network whose logic clock rate and offset are equal to av and bv in the initial instant; that is, Vvt≠⊘,Vvt≥1. With the loss of generality, assume node j has a larger logical rate. If the link eij is activated at gossip time tlij, node i will update its logical clock such that aiαi=ajαj and αibi+βi=αjbj+βj. Thus, the logical rate of each node is less than or equal to amax during the iteration of RGCS. For a pair of nodes i and j, i, j∈Vv, there is aiαi=amax, αibi+βi=βv, and ajαj=amax, αjbj+βi=βv. Thus, we can infer that aiαi or ajαj≥akαk holds for ∀k∈V. Therefore, a pair of nodes i and j in Vv will no longer update its logical clock and maintain its logical rate and offset during the latter iterations, which means that Vvt is nondecreasing.The complement of a setVv is defined as V−Vv, which means that the set of nodes are not in Vv. If node k is not in the set Vv, then node k is in V−Vv. Since all nodes’ logical rate is less than or equal to amax during the iteration of RGCS, so we have akαk<av for ∀k∈V−Vv. Thus, if node i∈Vv is coupled with node k by Sync-L, then it follows from (8) and (9) that node k will update its logical clock such that akαk=av,αkbk+βk=βv. Then, one obtains that Vvt+=Vvt+1 and V−Vvt+=V−Vvt−1, where t+ is the finish time of the iteration. Hence, Vvt will strictly increase when node i∈Vv is coupled with node j∈V−Vv.IfVvt=N in instant t, it implies that Prlimt→∞α~it=ac=1,Prlimt→∞β~it=bc=1, for ∀i∈V. Otherwise, we have Vvt<N. Since graph Gtlij,Δl,ij is jointly connected with probability one, there is at least one link eik for i∈Vv and k∈V−Vv, which means that there has λik>0. The probability of the event that link eik is activated satisfies 1−e−λikt′−t. Therefore, we have the probability of Vvt≥Vvt+1 being equal to 1−e−λikt′−t. Thus, Vvt will strictly increase with probability one when t→∞. Hence, we have Prlimt−∞Vvt=n=1, which yields Prlimt→∞a~it=ac=1, Prlimt→∞β~it=bc=1, for ∀i∈V. Then, Praiαit−ajαjt can approximate to zero when t→∞. Clearly, limt→∞Praiαit−ajαjt/1/t=0,Prα~it−α~jt=o1/t thus satisfied. The Theorem 1 is thus proved.In practice, considering the thrift energy to a bigger extent, the finite-time convergence of algorithms is very important in WSNs. Next, we will give the lower bound of the probability for the finite-time convergence of RGCS. For nodei, j, let us assume Wij represents the time cost for a link activation event.Then,uij,Uij∫0tuijsds is the probability density function and probability distribution function of Wij, respectively.Theorem 2.
Suppose the union graphGtlij,Δl,ij=∪ij∪lGtlij for ∀eij∈ℰt is connected with probability one. Then, we have PrTit=τvt,i∈V≥∏i∈VUvit.Proof 2.
From the proof of Theorem1, we can conclude that node i in V−Vv will become a node in Vv after the link evi is activated. When Tit=τvt, there is PrTit=τvt=Uvit, i∈V. ∏i∈VPrTit=τvt≤PrTit=τvt,i∈V which yields PrTit=τvt,i∈V≥∏i∈VUvit. Theorem 2 is thus proved.


### 4.2. Multi-RGCS Algorithm

Obviously, RGCS is obtained by the single-gossiping rule. Under this scenario, other silent nodes are situated in the wait state, while only one synchronization link is activated in a timeslot. We expect that more coupling nodes are able to exchange and update states in a timeslot, or more than a neighboring node can overhear a triggering node’s messages (i.e., broadcast gossip manner). Based on their positive effect on the performance of the convergence rate, the multigossiping version of RGCS (Multi-RGCS) is a topic which is worth exploring. In fact, we can assume that more than two nodesi,j,… wake up in tl simultaneously with probability Ptl>0. So the single-gossiping version corresponds to specific implementation of the above assumption in which if and only if two nodes i and j wake up.Different from the foregoing single-gossiping, Multi-RGCS requires an additional precondition that the synchronization links cannot have a public vertex in the same slot. In other words, we need to seek a multigossip sequenceMn,tc=mtcn, where n is the color number, tc is the switching time. So, the synchronization links are dyed different colors, and those links that have the same color are categorized as the group mtcn. This problem could be investigated by the idea of the edge-coloring (EC) [40]. The EC aims at an assignment of one color to each synchronization link such that no two synchronization links on the same node are assigned the same color. Here, we give a straightforward EC algorithm to realize Multi-RGCS as in Figure 3(b). Thereunto, the key procedures of obtaining the multigossip sequence are summarized as follows. For tc, do the following: Step 1. Generate a spanning tree ℋ of graph Gtc; Step 2. Randomly pick a single edge in ℋ, find a nonadjacent edge to the former, and then find a nonstaining edge for coloring the third color until it cannot find any nonstaining edge. Step 3. The edges of different colors constitute the multigossip sequence Mn,tc=mtc1,mtc2,…,mtcn. The probability characteristics of the set tl,l=1,2,… is similar to the set ∪l=0∞∪i=1,j=1Ntlij, and the physical meaning of ti− refers to the previous gossip instant of any synchronization link involving node i. In Multi-RGCS, several nodes are involved in multisynchronization links mtcn to increase the synchronization traffic and enhance the convergence speed.


### 4.3. Revised-RGCS Algorithm

In RGCS, we suppose that the delays are negligible. However, by considering various disturbances, which act as an additive noise model (such as the delay), the actual timestamp is truly noisy, and the delay distribution is unknown. To deal with this issue, we proposed a least square estimation-based low-pass filter against bounded delays (Assumption2). As shown in Figure 4, the time delay of the lth communication between node i and j is denoted by dij (i→j, namely, dij influences ΔSjij). dij is bounded by upper bound D; that is, 0<dij<D. dji (j→i, namely, dji influences ΔSiij) is the same definition as dij, but may be unequal.Figure 4
Illustration of gossip-consensus-based time synchronization with bounded delays.Due to the symmetry, the following process takes the case ofdij. Based on the definition of the relative drift and dij, we have a longspan estimator α^ijl for αijl as follows
(11)a^ijl=τjtlij+dijl−τjt0ij+dij0τitlij−τit0ij=aj∑lδijl+dijl−dij0aiΣlδij=aij1+ξ^l,where ξ^l=dijl−dij0/∑lδij and δij is the intertime between consecutive gossip instants for link eij. Since dij is bounded by D, we have ξˆl≤D/Σlδij. Hence, we know that ξ^l decays in a rate of O1/δ.Letα^ij∗l be the optimal estimator for α^ijl, and denote el=a^ijlτitlij−a^ij∗lτitlij. A least square principle as J=∑l=1lel2 is employed. For calculating the recursion of α^ij∗l, we apply a partial derivative for α^ij∗l, namely
(12)∂J∂a^ij∗=0,which yields an optimal estimator as follows:
(13)a^ij∗l=1−γ∗la^ij∗l−1+γ∗lτjtlij−τjt0ijτitlij−τit0ij,where the weighting parameter
(14)γ∗l=δ21+δ22+⋯+δ2lδ21+δ21+δ22+⋯+δ21+δ22+⋯+δ2l,and α^ij∗0=1. Substituting (11) into (13) yields
(15)a^ij∗l=aij1+ξ^∗l,where
(16)ξ∗l=δ1+δ1+δ2+⋯+δ1+δ2+⋯+δ1dijl−dij0δ1+δ1+δ22+⋯+δ1+δ2+⋯+δl2.Then, bounded bydij, we notice that the denominator of ξ^∗l is δ’s quadratic term after accumulating, and the numerator of ξ^∗l is δ’s first degree term. It implies that the decay rate of ξ^∗l is also O1/δ. This decay rate ensures that the proposed least square estimation-based low-pass filter avoids the divergence condition of Prα~it−α~jt. Hence, we can utilize α^ij∗l/δ1+δ1+δ2+⋯+δl1/2 to replace αijtl and modify the rate-updating rule of the triggering node i of (6); thus, there is
(17)aitl+1ij=1−ρ1δ1+δ1+δ2+⋯+δl1/2ait~ki+ρ1a^ij∗lajtlijδ1+δ1+δ2+⋯+δ11/2.The criterion for selecting the appropriate weighting parameterδ1+δ1+δ2+⋯+δl−1/2 is based on a piece-wise constant function, and it is chosen to be a decreasing factor, which contributes to restraining the negative effect of additive noise in stochastic approximation. Actually, the weighting parameter in this paper is a special case of the standard conditions in stochastic approximation methods: ∑l∞δ1+δ1+δ2+⋯+δl−1/2=∞ and ∑l∞δ1+δ1+δ2+⋯+δl−1<∞.Sinceaijtlij is an estimation of inverse relative drift aijtlij, the rate updating rule of triggered node j is
(18)ajtl=1ij=1−1−ρ1δ1+δ1+δ1+⋯+δl1/2ajt~kj+1−ρ1aitlija^ij∗lδ1+δ1+δ2+⋯+δl1/2.Then, the clock offset compensations of local nodei, j is updated as follows:
(19)βitl+1ij=βit~ki+ρ2Tjtlij−Titlij+djil,(20)βjtl+1ij=βjt~kj+ρ2Titlij−Tjtlij+dijl.The delays also have an impact ont~ki. The issue is caused by the fact that node j would not instantly receive its gossiping neighbor’s states due to uncertain delay, and if delay dij satisfies the following two conditions: (i) delay dij greater than intertime ∆; (ii) node j joins next gossip averaging; then t~ik will change and needs to be modified. When dij≠dji, we call this asymmetric gossip, and this is a common case. To clearly explain how delay influences the local updating equations, we might as well suppose link eij is activating. After ∆, there are three possibilities of adjacent Sync-L: eik, ejh, and ekh, ∀k,h∈V, if:Case 1.
dij≥∆l,ik+n∆l,kh,n=0,1,…, then (18) and (20) utilize a^ik∗l and t~ki=maxtsik,trik∣sr=12….Case 2.
dji≥∆l,jh+n∆l,kh,n=0,1,…, then (17) and (19) utilize a^jh∗l and t~hj=maxtsjh,trhj∣sr=12….The discriminant of Case 1 and Case 2 is easy to implement, because the comparison between the length of delay and the interval time of node activation depends on the local nodes themselves. The delays make Revised-RGCS slightly complex, but it will not damage the convergence. However, we should point out that the update of the logical rate is based on the long-span neighboring statesτjtlij−τjt0ij, so the nodes should set up a cached memory for forming a buffer queue of the timing messages. To summarize the above process, a flow diagram of the Revised-RGCS algorithm is described in Figure 5.Figure 5
Flowchart of Revised-RGCS algorithm.


## 4.1. RGCS Algorithm

### 4.1.1. Randomized Communication Protocol

A randomly connected ad hoc WSN is specifically characterized in that the nodes are randomly activating and sleeping, and the RGCS algorithm is supposed to run independently in each individual node. Firstly, the Poisson process is configured to each node in order to generate the synchronization link (Sync-L) beacon which is sent to a node of its neighborhood by exploiting the broadcast nature of wireless communications. Thus, the randomized activation ofeiji,j∈V satisfies the Poisson process with the constant intensity λij such that Prtijl+σ−tijσ=n=λijln/n!eλijl, n=0,1…, for ∀l, σ≥0. Some special circumstances are as follows: if λij=0, it means link eij is not activated forever, and if λij=∞, it means link eij is activated infinitely in a given time interval. The Sync-L beacon between node i and j is confirmed, which is referred to the stochastic link activation event. Once the randomized activation of link eij takes place, by using the Media Access Control (MAC) layer time stamps, triggering node i pushes a multivariable message αitlij,βitlij,τitlij to node j. After that, the triggered node j pulls a multivariable message αjtlij,βjtlij,τjtlij to node i. The overall procedure is illustrated in Figure 1.Figure 1
The Sync-L beacon and timing message exchanges in a dynamic wireless sensor network.Thus, accordingly, the set of activated synchronization links∪i=1,j=1Neijt are an identically and independently distributed (i.i.d.) Poisson distribution. Suppose that function ℱN represents the amount of synchronization links of an underlying graph. When it is a complete graph, we can maximize ℱN as NN−1/2. Clearly, the set ∪l=0∞∪i=1,j=1Ntlij∣eij∈Et satisfies global Poisson distribution with the intensity ℱNλ, because all intensities have the same value. Each global gossip instantly corresponds to an updating event. We denote ∆l,ij as the intertime between consecutive gossip instants for the global Poisson process, and Δl,ijl∈N,ij∈Et is an i.i.d. process with moments
(4)EΔl,ij=1ℱNλ,EΔ2l,ij=2ℱNλ2.The intensityλ increased, whereas ∆l,ij continuously decreased. The physical significance of λij represents the intermittent of activation events of link eij, and the mathematical meaning of λij represents the mean value of the occurrence of the activation events per unit time. In many scenarios, environmental-temperature variations will be slow to change around nodes. Hence, we can do that by increasing intensity λij to enlarge the frequency of a link activation event in order to work against slowly changing drifts.As shown in Figure2, we illustrate how the proposed mechanism works under the hidden node problem. Node A is visible from node B, and node C is visible from node B too. However, node A and node B cannot sense with each other, because they are out of the communication zone of each other. In the deterministic communication protocol (such as ATS, MTS, RoATS, etc.), each node transmits its timing messages periodically with a common period based on its own clock on chip. If nodes A and B have a small difference in terms of the hardware rate and offset, they will announce timing messages to node C simultaneously. Thus, the collisions will occur endlessly. In our proposed mechanism, each node announces a timing message asynchronously based on its preprogrammed Poisson process, and random pairwise node delivery timing messages in the uplink and downlink successively. So node A randomly gossips, then a sync timeslot is established between nodes A and C with probability PrtlAC. The sync timeslot between nodes B and C is established with probability PrtlBC. The Poisson intervals δAC and δBC are independent of each other. If the transmission delay is negligible, the width of the sync timeslot can be narrow such that the probability of collisions will further down. Hence, with an appropriate λ, the probability of collisions is lower than that in the deterministic communication.Figure 2
Illustration of the proposed randomized communication under the hidden node scene.To defend against message manipulation attacks, secure consensus timing protocols should contain a detecting and excluding outlier mechanism for the logical clock checking and hardware clock checking. From the analysis of logical clock checking mechanism in the literature [32], we know that the bounded communication cycle which was determined by Ψ∣τit=NΨ,N=1,2,…,Ψ>0 is a pivotal parameter of the secure protocols. However, the authors suppose Ψ is invariable under malicious modification with the purpose of preventing the attack nodes using outdated receiving information to cheat, that is, it makes nodes to collect messages from neighboring nodes within a constant duration. The proposed gossip interaction mode which has less conservatism to topology changes can remove this limitation properly. Also, Ψ is the key parameter which contributes to represent the conforming relationship of Definition 1 in the literature [33] to defend against a sybil attack, and RGCS is robust to the distortion of the bounded communication cycle.


### 4.1.2. Gossip Consensus Approach for Clock Rate and Offset Compensation

LetΔSiij be the difference of hardware clock readings τi of triggering node i in gossip instant tlij and tl−1ij, namely, ΔSiij=τitlij−τitl−1ij. The main idea of the updating rule is to utilize the gossip consensus approach based on the interchange of the gossiping neighbors’ messages. Triggered node j updates its logical rate α~jt and offset β~jt by averaging them with the estimates of its gossiping neighbors, namely, a~jtl+1ij=1−ρ1a~jt~kj+ρ1a~itlij. Each node consists of estimating the logical rate with respect to the virtual consensus rate, and local node j stores a new compensation αj. Then, by dividing αj at both sides of above equation, we have
(5)ajtl+1ij=1=ρ1ajt~kj+ρ1aiajaitlij,where ρ1∈0,1. The constant ρ1 defines the degree of change of compensation α in gossip instant tl+1ij. If ρ1 is set to a small value, the average information will be removed in a few updates. Additionally, due to the discrete observations of the relative drift, we can increase ρ1 to guarantee the stationarity of the estimated α. Based on the above analysis, the converge-to-max criterion is applied to t~kj. The time, t~kj, indicates the previous gossip instant of arbitrary edges which contain node j just before activated edge eij’s lth gossip instant. Equation (5) counts the absolute time on two scales, that is, updating the usage round and communication round, to avoid confusion between the updating iteration and the gossiping communication. Scrupulously, t~kj is given as follows:
(6)t~kj=maxtsjp,trqjtsjp<tlij,trqj<tlij;p,q=1,…,n;s,r=1,2,….When the Sync-Leij is activated in the next gossip instant tlij, node i uses τitl−1ij which would be stored in the flash memory of sensors to compute the number of drift, namely, the relative drift ajitlij for node j is computed by
(7)aiaj=ajitlij=ΔSiijΔSjij.During all iterations, each nodei’s storage is ONi for all possible synchronization links. It implies that, even though the size of the network node increases, the storage complexities of the RGCS per node per iteration will not grow. This property ensures the scalability of the algorithm.Substituting (7) into (5) yields the update equation of compensating αj. Again, based on the converge-to-max criterion, we design the rate compensation iteration rule of random pairwise nodes. In this rule, the rate compensations of triggering node i, triggered node j, and silent nodes evolve as follows
(8)ajtl+1ij=maxajt~kl,ajitlijaitlij,aitl+1ij=maxait~ki,aijtlijajtlij,asilenttl+1ij=asilentt~ksilent,which means that random pairwise nodes i and j reach the maximum logical clock together at a random gossip instant tl+1ij, and other nodes are silent. In (8), node i and j sequentially iterate its own estimated logical clock only once per gossiping interaction. Observing that whether t~ki and t~kj will be different or the same depends on the contiguous activation of the Sync-L of global Poisson process. After the rate compensation is applied, the random pairwise nodes compute the instantaneous estimated logical clock difference Titlij−Tjtlij and try to adjust its offset β in order to reduce the difference. Once again, the gossip consensus approach and the converge-to-max criterion are applied to local node i, j, and silent nodes for attaining offset compensations, as follows
(9)βjtl+1ij=βjt~kj+ρ2Titlij−Tjtlij,βitl+1ij=βit~ki+ρ2Tjtlij−Titlij,βsilenttl+1ij=βsilentt~ksilent,where ρ2=1 and Titlij=αitlijτitlij+βitlij. The flowchart of the RGCS algorithm is shown in Figure 3(a), and the basic procedures are described as follows: Step 1. Randomly initialize each local clock τi. Step 2. Judge whether arbitrary node i activates its neighbor or not, or whether it is activated by its neighbor or not. Step 3. Perform update equations (6), (7), (8), and (9). Step 4. Judge whether to meet the sync accuracy or not. Otherwise, return to Step 2.Figure 3
Flowchart of the proposed algorithms. (a) Randomized Gossip-Consensus-based time Synchronization (RGCS). (b) Multi-RGCS.
(a)
(b)


### 4.1.3. Convergence of RGCS

Substituting (2) into (3) yields an intuitive translation of the time synchronization issue:
(10)Prlimt→∞a~t=av=1,∀i∈V,Prlimt→∞β~it=bv=1,∀i∈V,Pra~it−a~jt=o1t,∀i∈V,where av and bv are the parameters of a consistent virtual clock. Equation (10) shows that whether the clocks achieve synchronization or not depends not only on the convergence of the logical rate and offset, but also on the convergence speed of the logical rate errors Prα~it−α~jt, because errors will tend to diverge if the convergence speed to zero of Prα~it−α~jt is slower than 1/t.Theorem 1.
Consider the rate and offset update equations given by (6), (7), (8), and (9), and there exist two variables ∆>0 and l>0 such that the union graph Gtlij,Δl,ij=∪ij∪lGtlij for ∀eij∈ℰt is connected with probability one. Then, (10) holds true.Proof 1.
Firstly, two functionsVvt and Vvt are introduced, where Vvt is the set of nodes whose logical rate and offset are equal to av and bv in instant t, and Vvt is the cardinality of set Vvt. Define amax=maxai,∀i∈V, let node v be the node whose clock rate is equal to amax. According to the initial sets, there is at least one node in the network whose logic clock rate and offset are equal to av and bv in the initial instant; that is, Vvt≠⊘,Vvt≥1. With the loss of generality, assume node j has a larger logical rate. If the link eij is activated at gossip time tlij, node i will update its logical clock such that aiαi=ajαj and αibi+βi=αjbj+βj. Thus, the logical rate of each node is less than or equal to amax during the iteration of RGCS. For a pair of nodes i and j, i, j∈Vv, there is aiαi=amax, αibi+βi=βv, and ajαj=amax, αjbj+βi=βv. Thus, we can infer that aiαi or ajαj≥akαk holds for ∀k∈V. Therefore, a pair of nodes i and j in Vv will no longer update its logical clock and maintain its logical rate and offset during the latter iterations, which means that Vvt is nondecreasing.The complement of a setVv is defined as V−Vv, which means that the set of nodes are not in Vv. If node k is not in the set Vv, then node k is in V−Vv. Since all nodes’ logical rate is less than or equal to amax during the iteration of RGCS, so we have akαk<av for ∀k∈V−Vv. Thus, if node i∈Vv is coupled with node k by Sync-L, then it follows from (8) and (9) that node k will update its logical clock such that akαk=av,αkbk+βk=βv. Then, one obtains that Vvt+=Vvt+1 and V−Vvt+=V−Vvt−1, where t+ is the finish time of the iteration. Hence, Vvt will strictly increase when node i∈Vv is coupled with node j∈V−Vv.IfVvt=N in instant t, it implies that Prlimt→∞α~it=ac=1,Prlimt→∞β~it=bc=1, for ∀i∈V. Otherwise, we have Vvt<N. Since graph Gtlij,Δl,ij is jointly connected with probability one, there is at least one link eik for i∈Vv and k∈V−Vv, which means that there has λik>0. The probability of the event that link eik is activated satisfies 1−e−λikt′−t. Therefore, we have the probability of Vvt≥Vvt+1 being equal to 1−e−λikt′−t. Thus, Vvt will strictly increase with probability one when t→∞. Hence, we have Prlimt−∞Vvt=n=1, which yields Prlimt→∞a~it=ac=1, Prlimt→∞β~it=bc=1, for ∀i∈V. Then, Praiαit−ajαjt can approximate to zero when t→∞. Clearly, limt→∞Praiαit−ajαjt/1/t=0,Prα~it−α~jt=o1/t thus satisfied. The Theorem 1 is thus proved.In practice, considering the thrift energy to a bigger extent, the finite-time convergence of algorithms is very important in WSNs. Next, we will give the lower bound of the probability for the finite-time convergence of RGCS. For nodei, j, let us assume Wij represents the time cost for a link activation event.Then,uij,Uij∫0tuijsds is the probability density function and probability distribution function of Wij, respectively.Theorem 2.
Suppose the union graphGtlij,Δl,ij=∪ij∪lGtlij for ∀eij∈ℰt is connected with probability one. Then, we have PrTit=τvt,i∈V≥∏i∈VUvit.Proof 2.
From the proof of Theorem1, we can conclude that node i in V−Vv will become a node in Vv after the link evi is activated. When Tit=τvt, there is PrTit=τvt=Uvit, i∈V. ∏i∈VPrTit=τvt≤PrTit=τvt,i∈V which yields PrTit=τvt,i∈V≥∏i∈VUvit. Theorem 2 is thus proved.


## 4.1.1. Randomized Communication Protocol

A randomly connected ad hoc WSN is specifically characterized in that the nodes are randomly activating and sleeping, and the RGCS algorithm is supposed to run independently in each individual node. Firstly, the Poisson process is configured to each node in order to generate the synchronization link (Sync-L) beacon which is sent to a node of its neighborhood by exploiting the broadcast nature of wireless communications. Thus, the randomized activation ofeiji,j∈V satisfies the Poisson process with the constant intensity λij such that Prtijl+σ−tijσ=n=λijln/n!eλijl, n=0,1…, for ∀l, σ≥0. Some special circumstances are as follows: if λij=0, it means link eij is not activated forever, and if λij=∞, it means link eij is activated infinitely in a given time interval. The Sync-L beacon between node i and j is confirmed, which is referred to the stochastic link activation event. Once the randomized activation of link eij takes place, by using the Media Access Control (MAC) layer time stamps, triggering node i pushes a multivariable message αitlij,βitlij,τitlij to node j. After that, the triggered node j pulls a multivariable message αjtlij,βjtlij,τjtlij to node i. The overall procedure is illustrated in Figure 1.Figure 1
The Sync-L beacon and timing message exchanges in a dynamic wireless sensor network.Thus, accordingly, the set of activated synchronization links∪i=1,j=1Neijt are an identically and independently distributed (i.i.d.) Poisson distribution. Suppose that function ℱN represents the amount of synchronization links of an underlying graph. When it is a complete graph, we can maximize ℱN as NN−1/2. Clearly, the set ∪l=0∞∪i=1,j=1Ntlij∣eij∈Et satisfies global Poisson distribution with the intensity ℱNλ, because all intensities have the same value. Each global gossip instantly corresponds to an updating event. We denote ∆l,ij as the intertime between consecutive gossip instants for the global Poisson process, and Δl,ijl∈N,ij∈Et is an i.i.d. process with moments
(4)EΔl,ij=1ℱNλ,EΔ2l,ij=2ℱNλ2.The intensityλ increased, whereas ∆l,ij continuously decreased. The physical significance of λij represents the intermittent of activation events of link eij, and the mathematical meaning of λij represents the mean value of the occurrence of the activation events per unit time. In many scenarios, environmental-temperature variations will be slow to change around nodes. Hence, we can do that by increasing intensity λij to enlarge the frequency of a link activation event in order to work against slowly changing drifts.As shown in Figure2, we illustrate how the proposed mechanism works under the hidden node problem. Node A is visible from node B, and node C is visible from node B too. However, node A and node B cannot sense with each other, because they are out of the communication zone of each other. In the deterministic communication protocol (such as ATS, MTS, RoATS, etc.), each node transmits its timing messages periodically with a common period based on its own clock on chip. If nodes A and B have a small difference in terms of the hardware rate and offset, they will announce timing messages to node C simultaneously. Thus, the collisions will occur endlessly. In our proposed mechanism, each node announces a timing message asynchronously based on its preprogrammed Poisson process, and random pairwise node delivery timing messages in the uplink and downlink successively. So node A randomly gossips, then a sync timeslot is established between nodes A and C with probability PrtlAC. The sync timeslot between nodes B and C is established with probability PrtlBC. The Poisson intervals δAC and δBC are independent of each other. If the transmission delay is negligible, the width of the sync timeslot can be narrow such that the probability of collisions will further down. Hence, with an appropriate λ, the probability of collisions is lower than that in the deterministic communication.Figure 2
Illustration of the proposed randomized communication under the hidden node scene.To defend against message manipulation attacks, secure consensus timing protocols should contain a detecting and excluding outlier mechanism for the logical clock checking and hardware clock checking. From the analysis of logical clock checking mechanism in the literature [32], we know that the bounded communication cycle which was determined by Ψ∣τit=NΨ,N=1,2,…,Ψ>0 is a pivotal parameter of the secure protocols. However, the authors suppose Ψ is invariable under malicious modification with the purpose of preventing the attack nodes using outdated receiving information to cheat, that is, it makes nodes to collect messages from neighboring nodes within a constant duration. The proposed gossip interaction mode which has less conservatism to topology changes can remove this limitation properly. Also, Ψ is the key parameter which contributes to represent the conforming relationship of Definition 1 in the literature [33] to defend against a sybil attack, and RGCS is robust to the distortion of the bounded communication cycle.


## 4.1.2. Gossip Consensus Approach for Clock Rate and Offset Compensation

LetΔSiij be the difference of hardware clock readings τi of triggering node i in gossip instant tlij and tl−1ij, namely, ΔSiij=τitlij−τitl−1ij. The main idea of the updating rule is to utilize the gossip consensus approach based on the interchange of the gossiping neighbors’ messages. Triggered node j updates its logical rate α~jt and offset β~jt by averaging them with the estimates of its gossiping neighbors, namely, a~jtl+1ij=1−ρ1a~jt~kj+ρ1a~itlij. Each node consists of estimating the logical rate with respect to the virtual consensus rate, and local node j stores a new compensation αj. Then, by dividing αj at both sides of above equation, we have
(5)ajtl+1ij=1=ρ1ajt~kj+ρ1aiajaitlij,where ρ1∈0,1. The constant ρ1 defines the degree of change of compensation α in gossip instant tl+1ij. If ρ1 is set to a small value, the average information will be removed in a few updates. Additionally, due to the discrete observations of the relative drift, we can increase ρ1 to guarantee the stationarity of the estimated α. Based on the above analysis, the converge-to-max criterion is applied to t~kj. The time, t~kj, indicates the previous gossip instant of arbitrary edges which contain node j just before activated edge eij’s lth gossip instant. Equation (5) counts the absolute time on two scales, that is, updating the usage round and communication round, to avoid confusion between the updating iteration and the gossiping communication. Scrupulously, t~kj is given as follows:
(6)t~kj=maxtsjp,trqjtsjp<tlij,trqj<tlij;p,q=1,…,n;s,r=1,2,….When the Sync-Leij is activated in the next gossip instant tlij, node i uses τitl−1ij which would be stored in the flash memory of sensors to compute the number of drift, namely, the relative drift ajitlij for node j is computed by
(7)aiaj=ajitlij=ΔSiijΔSjij.During all iterations, each nodei’s storage is ONi for all possible synchronization links. It implies that, even though the size of the network node increases, the storage complexities of the RGCS per node per iteration will not grow. This property ensures the scalability of the algorithm.Substituting (7) into (5) yields the update equation of compensating αj. Again, based on the converge-to-max criterion, we design the rate compensation iteration rule of random pairwise nodes. In this rule, the rate compensations of triggering node i, triggered node j, and silent nodes evolve as follows
(8)ajtl+1ij=maxajt~kl,ajitlijaitlij,aitl+1ij=maxait~ki,aijtlijajtlij,asilenttl+1ij=asilentt~ksilent,which means that random pairwise nodes i and j reach the maximum logical clock together at a random gossip instant tl+1ij, and other nodes are silent. In (8), node i and j sequentially iterate its own estimated logical clock only once per gossiping interaction. Observing that whether t~ki and t~kj will be different or the same depends on the contiguous activation of the Sync-L of global Poisson process. After the rate compensation is applied, the random pairwise nodes compute the instantaneous estimated logical clock difference Titlij−Tjtlij and try to adjust its offset β in order to reduce the difference. Once again, the gossip consensus approach and the converge-to-max criterion are applied to local node i, j, and silent nodes for attaining offset compensations, as follows
(9)βjtl+1ij=βjt~kj+ρ2Titlij−Tjtlij,βitl+1ij=βit~ki+ρ2Tjtlij−Titlij,βsilenttl+1ij=βsilentt~ksilent,where ρ2=1 and Titlij=αitlijτitlij+βitlij. The flowchart of the RGCS algorithm is shown in Figure 3(a), and the basic procedures are described as follows: Step 1. Randomly initialize each local clock τi. Step 2. Judge whether arbitrary node i activates its neighbor or not, or whether it is activated by its neighbor or not. Step 3. Perform update equations (6), (7), (8), and (9). Step 4. Judge whether to meet the sync accuracy or not. Otherwise, return to Step 2.Figure 3
Flowchart of the proposed algorithms. (a) Randomized Gossip-Consensus-based time Synchronization (RGCS). (b) Multi-RGCS.
(a)
(b)


## 4.1.3. Convergence of RGCS

Substituting (2) into (3) yields an intuitive translation of the time synchronization issue:
(10)Prlimt→∞a~t=av=1,∀i∈V,Prlimt→∞β~it=bv=1,∀i∈V,Pra~it−a~jt=o1t,∀i∈V,where av and bv are the parameters of a consistent virtual clock. Equation (10) shows that whether the clocks achieve synchronization or not depends not only on the convergence of the logical rate and offset, but also on the convergence speed of the logical rate errors Prα~it−α~jt, because errors will tend to diverge if the convergence speed to zero of Prα~it−α~jt is slower than 1/t.Theorem 1.
Consider the rate and offset update equations given by (6), (7), (8), and (9), and there exist two variables ∆>0 and l>0 such that the union graph Gtlij,Δl,ij=∪ij∪lGtlij for ∀eij∈ℰt is connected with probability one. Then, (10) holds true.Proof 1.
Firstly, two functionsVvt and Vvt are introduced, where Vvt is the set of nodes whose logical rate and offset are equal to av and bv in instant t, and Vvt is the cardinality of set Vvt. Define amax=maxai,∀i∈V, let node v be the node whose clock rate is equal to amax. According to the initial sets, there is at least one node in the network whose logic clock rate and offset are equal to av and bv in the initial instant; that is, Vvt≠⊘,Vvt≥1. With the loss of generality, assume node j has a larger logical rate. If the link eij is activated at gossip time tlij, node i will update its logical clock such that aiαi=ajαj and αibi+βi=αjbj+βj. Thus, the logical rate of each node is less than or equal to amax during the iteration of RGCS. For a pair of nodes i and j, i, j∈Vv, there is aiαi=amax, αibi+βi=βv, and ajαj=amax, αjbj+βi=βv. Thus, we can infer that aiαi or ajαj≥akαk holds for ∀k∈V. Therefore, a pair of nodes i and j in Vv will no longer update its logical clock and maintain its logical rate and offset during the latter iterations, which means that Vvt is nondecreasing.The complement of a setVv is defined as V−Vv, which means that the set of nodes are not in Vv. If node k is not in the set Vv, then node k is in V−Vv. Since all nodes’ logical rate is less than or equal to amax during the iteration of RGCS, so we have akαk<av for ∀k∈V−Vv. Thus, if node i∈Vv is coupled with node k by Sync-L, then it follows from (8) and (9) that node k will update its logical clock such that akαk=av,αkbk+βk=βv. Then, one obtains that Vvt+=Vvt+1 and V−Vvt+=V−Vvt−1, where t+ is the finish time of the iteration. Hence, Vvt will strictly increase when node i∈Vv is coupled with node j∈V−Vv.IfVvt=N in instant t, it implies that Prlimt→∞α~it=ac=1,Prlimt→∞β~it=bc=1, for ∀i∈V. Otherwise, we have Vvt<N. Since graph Gtlij,Δl,ij is jointly connected with probability one, there is at least one link eik for i∈Vv and k∈V−Vv, which means that there has λik>0. The probability of the event that link eik is activated satisfies 1−e−λikt′−t. Therefore, we have the probability of Vvt≥Vvt+1 being equal to 1−e−λikt′−t. Thus, Vvt will strictly increase with probability one when t→∞. Hence, we have Prlimt−∞Vvt=n=1, which yields Prlimt→∞a~it=ac=1, Prlimt→∞β~it=bc=1, for ∀i∈V. Then, Praiαit−ajαjt can approximate to zero when t→∞. Clearly, limt→∞Praiαit−ajαjt/1/t=0,Prα~it−α~jt=o1/t thus satisfied. The Theorem 1 is thus proved.In practice, considering the thrift energy to a bigger extent, the finite-time convergence of algorithms is very important in WSNs. Next, we will give the lower bound of the probability for the finite-time convergence of RGCS. For nodei, j, let us assume Wij represents the time cost for a link activation event.Then,uij,Uij∫0tuijsds is the probability density function and probability distribution function of Wij, respectively.Theorem 2.
Suppose the union graphGtlij,Δl,ij=∪ij∪lGtlij for ∀eij∈ℰt is connected with probability one. Then, we have PrTit=τvt,i∈V≥∏i∈VUvit.Proof 2.
From the proof of Theorem1, we can conclude that node i in V−Vv will become a node in Vv after the link evi is activated. When Tit=τvt, there is PrTit=τvt=Uvit, i∈V. ∏i∈VPrTit=τvt≤PrTit=τvt,i∈V which yields PrTit=τvt,i∈V≥∏i∈VUvit. Theorem 2 is thus proved.


## 4.2. Multi-RGCS Algorithm

Obviously, RGCS is obtained by the single-gossiping rule. Under this scenario, other silent nodes are situated in the wait state, while only one synchronization link is activated in a timeslot. We expect that more coupling nodes are able to exchange and update states in a timeslot, or more than a neighboring node can overhear a triggering node’s messages (i.e., broadcast gossip manner). Based on their positive effect on the performance of the convergence rate, the multigossiping version of RGCS (Multi-RGCS) is a topic which is worth exploring. In fact, we can assume that more than two nodesi,j,… wake up in tl simultaneously with probability Ptl>0. So the single-gossiping version corresponds to specific implementation of the above assumption in which if and only if two nodes i and j wake up.Different from the foregoing single-gossiping, Multi-RGCS requires an additional precondition that the synchronization links cannot have a public vertex in the same slot. In other words, we need to seek a multigossip sequenceMn,tc=mtcn, where n is the color number, tc is the switching time. So, the synchronization links are dyed different colors, and those links that have the same color are categorized as the group mtcn. This problem could be investigated by the idea of the edge-coloring (EC) [40]. The EC aims at an assignment of one color to each synchronization link such that no two synchronization links on the same node are assigned the same color. Here, we give a straightforward EC algorithm to realize Multi-RGCS as in Figure 3(b). Thereunto, the key procedures of obtaining the multigossip sequence are summarized as follows. For tc, do the following: Step 1. Generate a spanning tree ℋ of graph Gtc; Step 2. Randomly pick a single edge in ℋ, find a nonadjacent edge to the former, and then find a nonstaining edge for coloring the third color until it cannot find any nonstaining edge. Step 3. The edges of different colors constitute the multigossip sequence Mn,tc=mtc1,mtc2,…,mtcn. The probability characteristics of the set tl,l=1,2,… is similar to the set ∪l=0∞∪i=1,j=1Ntlij, and the physical meaning of ti− refers to the previous gossip instant of any synchronization link involving node i. In Multi-RGCS, several nodes are involved in multisynchronization links mtcn to increase the synchronization traffic and enhance the convergence speed.


## 4.3. Revised-RGCS Algorithm

In RGCS, we suppose that the delays are negligible. However, by considering various disturbances, which act as an additive noise model (such as the delay), the actual timestamp is truly noisy, and the delay distribution is unknown. To deal with this issue, we proposed a least square estimation-based low-pass filter against bounded delays (Assumption2). As shown in Figure 4, the time delay of the lth communication between node i and j is denoted by dij (i→j, namely, dij influences ΔSjij). dij is bounded by upper bound D; that is, 0<dij<D. dji (j→i, namely, dji influences ΔSiij) is the same definition as dij, but may be unequal.Figure 4
Illustration of gossip-consensus-based time synchronization with bounded delays.Due to the symmetry, the following process takes the case ofdij. Based on the definition of the relative drift and dij, we have a longspan estimator α^ijl for αijl as follows
(11)a^ijl=τjtlij+dijl−τjt0ij+dij0τitlij−τit0ij=aj∑lδijl+dijl−dij0aiΣlδij=aij1+ξ^l,where ξ^l=dijl−dij0/∑lδij and δij is the intertime between consecutive gossip instants for link eij. Since dij is bounded by D, we have ξˆl≤D/Σlδij. Hence, we know that ξ^l decays in a rate of O1/δ.Letα^ij∗l be the optimal estimator for α^ijl, and denote el=a^ijlτitlij−a^ij∗lτitlij. A least square principle as J=∑l=1lel2 is employed. For calculating the recursion of α^ij∗l, we apply a partial derivative for α^ij∗l, namely
(12)∂J∂a^ij∗=0,which yields an optimal estimator as follows:
(13)a^ij∗l=1−γ∗la^ij∗l−1+γ∗lτjtlij−τjt0ijτitlij−τit0ij,where the weighting parameter
(14)γ∗l=δ21+δ22+⋯+δ2lδ21+δ21+δ22+⋯+δ21+δ22+⋯+δ2l,and α^ij∗0=1. Substituting (11) into (13) yields
(15)a^ij∗l=aij1+ξ^∗l,where
(16)ξ∗l=δ1+δ1+δ2+⋯+δ1+δ2+⋯+δ1dijl−dij0δ1+δ1+δ22+⋯+δ1+δ2+⋯+δl2.Then, bounded bydij, we notice that the denominator of ξ^∗l is δ’s quadratic term after accumulating, and the numerator of ξ^∗l is δ’s first degree term. It implies that the decay rate of ξ^∗l is also O1/δ. This decay rate ensures that the proposed least square estimation-based low-pass filter avoids the divergence condition of Prα~it−α~jt. Hence, we can utilize α^ij∗l/δ1+δ1+δ2+⋯+δl1/2 to replace αijtl and modify the rate-updating rule of the triggering node i of (6); thus, there is
(17)aitl+1ij=1−ρ1δ1+δ1+δ2+⋯+δl1/2ait~ki+ρ1a^ij∗lajtlijδ1+δ1+δ2+⋯+δ11/2.The criterion for selecting the appropriate weighting parameterδ1+δ1+δ2+⋯+δl−1/2 is based on a piece-wise constant function, and it is chosen to be a decreasing factor, which contributes to restraining the negative effect of additive noise in stochastic approximation. Actually, the weighting parameter in this paper is a special case of the standard conditions in stochastic approximation methods: ∑l∞δ1+δ1+δ2+⋯+δl−1/2=∞ and ∑l∞δ1+δ1+δ2+⋯+δl−1<∞.Sinceaijtlij is an estimation of inverse relative drift aijtlij, the rate updating rule of triggered node j is
(18)ajtl=1ij=1−1−ρ1δ1+δ1+δ1+⋯+δl1/2ajt~kj+1−ρ1aitlija^ij∗lδ1+δ1+δ2+⋯+δl1/2.Then, the clock offset compensations of local nodei, j is updated as follows:
(19)βitl+1ij=βit~ki+ρ2Tjtlij−Titlij+djil,(20)βjtl+1ij=βjt~kj+ρ2Titlij−Tjtlij+dijl.The delays also have an impact ont~ki. The issue is caused by the fact that node j would not instantly receive its gossiping neighbor’s states due to uncertain delay, and if delay dij satisfies the following two conditions: (i) delay dij greater than intertime ∆; (ii) node j joins next gossip averaging; then t~ik will change and needs to be modified. When dij≠dji, we call this asymmetric gossip, and this is a common case. To clearly explain how delay influences the local updating equations, we might as well suppose link eij is activating. After ∆, there are three possibilities of adjacent Sync-L: eik, ejh, and ekh, ∀k,h∈V, if:Case 1.
dij≥∆l,ik+n∆l,kh,n=0,1,…, then (18) and (20) utilize a^ik∗l and t~ki=maxtsik,trik∣sr=12….Case 2.
dji≥∆l,jh+n∆l,kh,n=0,1,…, then (17) and (19) utilize a^jh∗l and t~hj=maxtsjh,trhj∣sr=12….The discriminant of Case 1 and Case 2 is easy to implement, because the comparison between the length of delay and the interval time of node activation depends on the local nodes themselves. The delays make Revised-RGCS slightly complex, but it will not damage the convergence. However, we should point out that the update of the logical rate is based on the long-span neighboring statesτjtlij−τjt0ij, so the nodes should set up a cached memory for forming a buffer queue of the timing messages. To summarize the above process, a flow diagram of the Revised-RGCS algorithm is described in Figure 5.Figure 5
Flowchart of Revised-RGCS algorithm.


## 5. Simulation Studies

To verify the superiority of novel proposed algorithms, we carried out comparative simulations for RGCS and Multi-RGCS with a delay-free case in the Matlab R2010b. Then, using the OMNeT++ 5.1471 simulator, a more realistic simulator for WSNs, we verified the Revised-RGCS algorithm with delays.


### 5.1. Delay-Free Case

As shown in Table1, DCS and RPCS are two appropriate reference algorithms, so we compared the performances of RGCS with them. All of them have been investigated numerically for emulating a randomly connected ad hoc WSN. The important parameter setting is described as follows. The local hardware rate is chosen from 0.999,1.0001, and the local offset is chosen from 0,0.002. αi0=1 and βi0=0. The number of nodes is 9, and the number of local nodes that can be accessed by the other nodes is 3. The initial synchronization period is 10 s. The threshold of successful Sync-L is characterized by a Poisson process with intensity λ, and the intensity reflects the connection strength between individual nodes. The average number of Sync-L per time interval is 10. It is feasible that the joint topologies of the simulation model of dynamic WSN are connected with probability one. The time unit is one second. The required accuracy is ±1 millisecond. Because there are no reference nodes and random initial parameters, we employed a metric to evaluate the synchronization error of the algorithms: the maximum difference of the parameters between any two nodes in overall WSN [18–20], that is, η95%t≥95%, where
(21)ηt=maxi,jXi0−Xj0−maxi,jXit−Xjtmaxi,jXi0−Xj0⋅100%,for∀i,j∈V.Figure6 shows the maximum error of logical rate α~it and offset β~it under RGCS and DCS. In our algorithm, the logical rate and offset synchronization can be achieved simultaneously. So, RGCS designed for randomly connected WSNs is an asynchronous and distributed configuration, and can make a complete compensation for the rate and offset. Due to the dense node density, DCS cannot achieve rate compensation and offset compensation simultaneously. Because DCS was devised for sparse node density to tolerate long delays, this leads to the synchronous mode for the update of the rate and offset. At the beginning of the compensation in RPCS, the rate of compensation is faster than that in RGCS, because RPCS employs a standard frequency estimation technique to obtain an estimate of the pairwise drift. However, the descending rate of the offset compensation is relative slow, and the logical clock Tit could not be synchronized without the backward jumps phenomenon.Figure 6
Comparison of maximum error of rateα~it and offset β~it between RGCS algorithm and the reference algorithms.Figure7 shows the maximum error of Tit of RGCS under λ=1, 5, and 10, from which it can be observed that it takes less time with λ=10 to reach synchronization. This is because a larger intensity of the Poisson process can decrease intertime ∆l,ij between consecutive gossip instants for any links. The results in Figure 6 validate the theoretical features of (3). So the descent velocity of the maximum error of logical clocks with λ=10 becomes more remarkable.Figure 7
Comparison of maximum errors of logical clocksTit of RGCS under different λ (the same initialization values of clocks for comparing intuitively).Figure8 shows the comparative simulation results with regard to single RGCS and Multi-RGCS. The green line represents the convergence of logical clocks in Multi-RGCS. The falling speed of the green line is faster than that of the blue line (single RGCS), because more clocks exchange their states and come close to the maximum-value at each gossip instant. Then, Figure 9 shows the relationship between different coloring edge’s numbers ranging from n=5 to n=12 and 95th percentile of synchronization errors. The performance degrades as more coloring numbers increase; however, it exhibits an approximate linear dependence; thus, it refers to the amount of gossip as a function of the coloring number n. We can involve this feature to suppress drift for different synchronization accuracies.Figure 8
Comparison of maximum errors ofTit between single RGCS and Multi-RGCS.Figure 9
The relationship between the number of gossip and coloring number (simulate it for 10).Based on the above simulation results and discussions, it can be seen that the paper has proposed an RGCS algorithm with superior performances compared to existing methods in terms of dynamic adaptability and faster convergence speed. A edge-coloring algorithm can be applied to constitute a spanning tree so that Multi-RGCS has a faster convergence speed than that in RGCS.


### 5.2. Bounded Delay Case

OMNeT++ is an extensible, modular, component-based C++ simulation library and framework, primarily for building network simulators. Based on the MiXiM framework and Network Description (NED) files, we implement an ad hoc WSN on the OMNeT++ 5.1.1, and then run the Revised-RGCS algorithm on it. It has been simulated for WSNs ofN=9 clocks placed on a field with a size of 100 m × 100 m. Moving sensors are indexed by bidimensional coordinates X and Y, namely, node 11, node 12, node 13, node 21, node 22, node 23, node 31, node 32, and node 33. For those mobile nodes, we used the Random Walk module to locate the coordinate position of the node. In this module, each node was made to move to the next coordinate position at random. Note that the radios in a node could collect incident message sets with higher layer module operation decoupled by buffers, so a deferred message will be valid. Table 2 summarizes the key parameters.Table 2
Simulation parameters.
Module
Parameter and data value
Application
250 kbps data rate
Wireless channel
Bandwidth: 20 MHz, data rate: 250 kbps, modulation type: BPSK
Radio
Sensitivity: −95 dBm, noise floor: −100 dBm, transmit power: 0 dBm, mode: ideal
Tunable MAC
Timestamp and default parameters
Communication radius
10 m, 20 m, and 30 m for every three nodes
Mobility model
Random walk (mobility update interval = 100 ms, speed = 5 m/sec)
Initial energy
28,080 J
Field size
100 m × 100 m
Simulation time
600 secsThe probability density distributions of time delaysdij and dji are shown in Figure 10. We carried on the statistics from 10 times simulations and obtained their distribution. It can be seen that the maximum delay is bounded which confirms the realistic bounded model. In reality, dij is often different from dji because the uplink and downlink between the head and tail are independent from one another. Obviously, the Revised-RGCS is an asymmetric gossip. In RPCS, the authors assume reciprocal propagation delays dij=dji in each synchronization round. The delay assumption in this paper is more practical than that in the RPCS.Figure 10
The difference ofdij and dji.With the bounded delays, we compared the relative drift estimation method, which is based on a low-pass filter, used in the Revised-RGCS and that in RGCS. Figure11 shows the results of the relative drift estimation error ξ^∗l of random pairwise nodes. It is observed that using (15), the relative drift αij can be estimated accurately as α^ij∗l (the blue line) will converge to the ideal value. Oppositely, the average estimate error is diverging in RGCS (the green line) without the low-pass filter. We see that the relative rate estimation under the bound delay can be obtained with the Revised-RGCS, on which an effective timing protocol depends.Figure 11
Comparison of relative drift estimation error between Revised-RGCS and RGCS.The simulation results of the Revised-RGCS, DCS, and RPCS implementations are presented in Figure12. It is observed from Figure 12 that the Revised-RGCS takes about 20 synchronization rounds to reach within 10 ticks while RPCS does not achieve the expected error before 20 rounds. It is clear that the Revised-RGCS can ensure that the sync error is bounded. In contrast, due to symmetric delay, the maximum synchronization error of the RPCS is ceaselessly growing. The results demonstrate that the Revised-RGCS converges asymptotically while RPCS is diverging. Although the DCS algorithm can reach time synchronization, its convergence rate is relatively slow under the randomly connected scene. This is because in DCS, the offset and rate compensation are initiated by the updated table information which is a weighted average of the neighborhoods. Most of the existing timing protocols employ a deterministic periodic synchronization scheme which results in message collisions, and they concentrate on those which merely exploit a packet in a collision timeslot or directly discard redundant packets. These techniques are passive to a certain extent. The reason for this is that WSNs require a nontrivial collision detection scheme and invalid packets waste energy. In RGCS, we assume that every gossiping of a pair of nodes costs the same amount of energy Eeg and let Eg be the total energy cost for gossiping to the expected accuracy, then, Es=Eg=∑l=1;eijNδl,ij×Eeg for ∀eij∈Et. As discussed in Section 2, we know that in most of the distributed configuration protocols, similar hardware clock states are the main reason behind the message collisions of hidden nodes. Hence, the number of clocks is considered to be an evaluation indicator. Figure 13 shows the timing message collision rate versus the number of clocks. The timing collision rate of RPCS and DCS protocols achieve 23.4% and 19.2% when the network scale is 100. In simulations, due to an asynchronous pairwise policy and an appropriate λ, the collision rate of RGCS is null. In the Revised-RGCS, the collision rate is 2.1%, because the timing messages are delivered to the MAC layer of the nodes with long delays which collides with the Sync-L event at few instants.Figure 12
Comparison of maximum synchronization error (ticks) between the Revised-RGCS algorithm and the current algorithms.Figure 13
Comparison of the Revised-RGCS, RGCS, DCS, and RPCS on the collision rate as the number of clocks increase.Based on the above simulation results and discussions, the Revised-RGCS can guarantee time synchronization under the realistic bounded delay model with a low collision rate compared to the current algorithms in practice.


## 5.1. Delay-Free Case

As shown in Table1, DCS and RPCS are two appropriate reference algorithms, so we compared the performances of RGCS with them. All of them have been investigated numerically for emulating a randomly connected ad hoc WSN. The important parameter setting is described as follows. The local hardware rate is chosen from 0.999,1.0001, and the local offset is chosen from 0,0.002. αi0=1 and βi0=0. The number of nodes is 9, and the number of local nodes that can be accessed by the other nodes is 3. The initial synchronization period is 10 s. The threshold of successful Sync-L is characterized by a Poisson process with intensity λ, and the intensity reflects the connection strength between individual nodes. The average number of Sync-L per time interval is 10. It is feasible that the joint topologies of the simulation model of dynamic WSN are connected with probability one. The time unit is one second. The required accuracy is ±1 millisecond. Because there are no reference nodes and random initial parameters, we employed a metric to evaluate the synchronization error of the algorithms: the maximum difference of the parameters between any two nodes in overall WSN [18–20], that is, η95%t≥95%, where
(21)ηt=maxi,jXi0−Xj0−maxi,jXit−Xjtmaxi,jXi0−Xj0⋅100%,for∀i,j∈V.Figure6 shows the maximum error of logical rate α~it and offset β~it under RGCS and DCS. In our algorithm, the logical rate and offset synchronization can be achieved simultaneously. So, RGCS designed for randomly connected WSNs is an asynchronous and distributed configuration, and can make a complete compensation for the rate and offset. Due to the dense node density, DCS cannot achieve rate compensation and offset compensation simultaneously. Because DCS was devised for sparse node density to tolerate long delays, this leads to the synchronous mode for the update of the rate and offset. At the beginning of the compensation in RPCS, the rate of compensation is faster than that in RGCS, because RPCS employs a standard frequency estimation technique to obtain an estimate of the pairwise drift. However, the descending rate of the offset compensation is relative slow, and the logical clock Tit could not be synchronized without the backward jumps phenomenon.Figure 6
Comparison of maximum error of rateα~it and offset β~it between RGCS algorithm and the reference algorithms.Figure7 shows the maximum error of Tit of RGCS under λ=1, 5, and 10, from which it can be observed that it takes less time with λ=10 to reach synchronization. This is because a larger intensity of the Poisson process can decrease intertime ∆l,ij between consecutive gossip instants for any links. The results in Figure 6 validate the theoretical features of (3). So the descent velocity of the maximum error of logical clocks with λ=10 becomes more remarkable.Figure 7
Comparison of maximum errors of logical clocksTit of RGCS under different λ (the same initialization values of clocks for comparing intuitively).Figure8 shows the comparative simulation results with regard to single RGCS and Multi-RGCS. The green line represents the convergence of logical clocks in Multi-RGCS. The falling speed of the green line is faster than that of the blue line (single RGCS), because more clocks exchange their states and come close to the maximum-value at each gossip instant. Then, Figure 9 shows the relationship between different coloring edge’s numbers ranging from n=5 to n=12 and 95th percentile of synchronization errors. The performance degrades as more coloring numbers increase; however, it exhibits an approximate linear dependence; thus, it refers to the amount of gossip as a function of the coloring number n. We can involve this feature to suppress drift for different synchronization accuracies.Figure 8
Comparison of maximum errors ofTit between single RGCS and Multi-RGCS.Figure 9
The relationship between the number of gossip and coloring number (simulate it for 10).Based on the above simulation results and discussions, it can be seen that the paper has proposed an RGCS algorithm with superior performances compared to existing methods in terms of dynamic adaptability and faster convergence speed. A edge-coloring algorithm can be applied to constitute a spanning tree so that Multi-RGCS has a faster convergence speed than that in RGCS.


## 5.2. Bounded Delay Case

OMNeT++ is an extensible, modular, component-based C++ simulation library and framework, primarily for building network simulators. Based on the MiXiM framework and Network Description (NED) files, we implement an ad hoc WSN on the OMNeT++ 5.1.1, and then run the Revised-RGCS algorithm on it. It has been simulated for WSNs ofN=9 clocks placed on a field with a size of 100 m × 100 m. Moving sensors are indexed by bidimensional coordinates X and Y, namely, node 11, node 12, node 13, node 21, node 22, node 23, node 31, node 32, and node 33. For those mobile nodes, we used the Random Walk module to locate the coordinate position of the node. In this module, each node was made to move to the next coordinate position at random. Note that the radios in a node could collect incident message sets with higher layer module operation decoupled by buffers, so a deferred message will be valid. Table 2 summarizes the key parameters.Table 2
Simulation parameters.
Module
Parameter and data value
Application
250 kbps data rate
Wireless channel
Bandwidth: 20 MHz, data rate: 250 kbps, modulation type: BPSK
Radio
Sensitivity: −95 dBm, noise floor: −100 dBm, transmit power: 0 dBm, mode: ideal
Tunable MAC
Timestamp and default parameters
Communication radius
10 m, 20 m, and 30 m for every three nodes
Mobility model
Random walk (mobility update interval = 100 ms, speed = 5 m/sec)
Initial energy
28,080 J
Field size
100 m × 100 m
Simulation time
600 secsThe probability density distributions of time delaysdij and dji are shown in Figure 10. We carried on the statistics from 10 times simulations and obtained their distribution. It can be seen that the maximum delay is bounded which confirms the realistic bounded model. In reality, dij is often different from dji because the uplink and downlink between the head and tail are independent from one another. Obviously, the Revised-RGCS is an asymmetric gossip. In RPCS, the authors assume reciprocal propagation delays dij=dji in each synchronization round. The delay assumption in this paper is more practical than that in the RPCS.Figure 10
The difference ofdij and dji.With the bounded delays, we compared the relative drift estimation method, which is based on a low-pass filter, used in the Revised-RGCS and that in RGCS. Figure11 shows the results of the relative drift estimation error ξ^∗l of random pairwise nodes. It is observed that using (15), the relative drift αij can be estimated accurately as α^ij∗l (the blue line) will converge to the ideal value. Oppositely, the average estimate error is diverging in RGCS (the green line) without the low-pass filter. We see that the relative rate estimation under the bound delay can be obtained with the Revised-RGCS, on which an effective timing protocol depends.Figure 11
Comparison of relative drift estimation error between Revised-RGCS and RGCS.The simulation results of the Revised-RGCS, DCS, and RPCS implementations are presented in Figure12. It is observed from Figure 12 that the Revised-RGCS takes about 20 synchronization rounds to reach within 10 ticks while RPCS does not achieve the expected error before 20 rounds. It is clear that the Revised-RGCS can ensure that the sync error is bounded. In contrast, due to symmetric delay, the maximum synchronization error of the RPCS is ceaselessly growing. The results demonstrate that the Revised-RGCS converges asymptotically while RPCS is diverging. Although the DCS algorithm can reach time synchronization, its convergence rate is relatively slow under the randomly connected scene. This is because in DCS, the offset and rate compensation are initiated by the updated table information which is a weighted average of the neighborhoods. Most of the existing timing protocols employ a deterministic periodic synchronization scheme which results in message collisions, and they concentrate on those which merely exploit a packet in a collision timeslot or directly discard redundant packets. These techniques are passive to a certain extent. The reason for this is that WSNs require a nontrivial collision detection scheme and invalid packets waste energy. In RGCS, we assume that every gossiping of a pair of nodes costs the same amount of energy Eeg and let Eg be the total energy cost for gossiping to the expected accuracy, then, Es=Eg=∑l=1;eijNδl,ij×Eeg for ∀eij∈Et. As discussed in Section 2, we know that in most of the distributed configuration protocols, similar hardware clock states are the main reason behind the message collisions of hidden nodes. Hence, the number of clocks is considered to be an evaluation indicator. Figure 13 shows the timing message collision rate versus the number of clocks. The timing collision rate of RPCS and DCS protocols achieve 23.4% and 19.2% when the network scale is 100. In simulations, due to an asynchronous pairwise policy and an appropriate λ, the collision rate of RGCS is null. In the Revised-RGCS, the collision rate is 2.1%, because the timing messages are delivered to the MAC layer of the nodes with long delays which collides with the Sync-L event at few instants.Figure 12
Comparison of maximum synchronization error (ticks) between the Revised-RGCS algorithm and the current algorithms.Figure 13
Comparison of the Revised-RGCS, RGCS, DCS, and RPCS on the collision rate as the number of clocks increase.Based on the above simulation results and discussions, the Revised-RGCS can guarantee time synchronization under the realistic bounded delay model with a low collision rate compared to the current algorithms in practice.


## 6. Conclusions

This paper presents a new randomized and energy-efficient time synchronization protocol called RGCS for dynamic WSNs with randomly changing connectivity. The protocol is based on distributed consensus TimeSync but incorporating the gossip algorithm. Therefore, it is superior to existing protocols in a generalized randomization framework, and can be well adapted to the link variation of ad hoc WSNs dynamically. The new idea of randomized scheduling of the synchronization links is to lower the rate of collision, so the RGCS dramatically relieves the collision phenomenon. Based on the converge-to-max criterion, the method has been deduced to accelerate the convergence speed. By combining the idea of the EC, the Multi-RGCS has been proposed. Moreover, the Revised-RGCS has been developed to specially restrain the impact of uncertain bounded delays. Extensive simulations have demonstrated the better performances of the proposed protocols.The proposed EC method is rough, since the dynamic ad hoc WSNs need a global coordinator in order to produce a spanning tree at each changing moment of topology. It is worth investigating how to design a pure distributed EC algorithm for Multi-RGCS. This will enhance the adaptability for fast changing networks. However, pure distributed edge-coloring is to be NP-Complete. In future work, we will focus on developing a solution to find the maximum clique of the sync edges.



---

*Source: 4283087-2018-11-08.xml*