{'fraction_non_alphanumeric': 0.022008935958960783, 'fraction_numerical': 0.0038060565944067516, 'mean_word_length': 4.616635687732342, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient, Single Hop Time Synchronization Protocol For Randomly Connected WSNs

This paper develops a fast, accurate and energy-efficient time synchronization protocol in wireless sensor networks that operate in harsh environments. The suggested protocol concept is based on an electrical physical metaphor. The protocol treats the nodes times as the states of an unconditionally stable discrete dynamical system that uses only single hop communication. The system can terminate at a low number of message exchanges while still in the transient phase. It can yield high quality time estimates with accuracies that are fractions of the clock at which node communication takes place. The synchronizer is developed and its capabilities are demonstrated by simulation and physical experiments on the MICA-Z wireless sensor network

A promising approach that has the potential to address the requirements of operating in harsh environments uses consensus control [6] to synchronize the nodes of a WSN. In this approach, a dynamical system, which uses the local times of its nearest neighbors as input, acts as a virtual clock of a node [7,8].
However, there are serious issues that still need to be addressed before this approach becomes practical for use with WSNs deployed in harsh environments. One of the issues with this approach is that it uses too many communications. This can quickly deplete the nodes' batteries. Also, the accuracy and rate of convergence from existing methods in this approach may not be practical. Stability may depend on the type of topology the network has or on this topology remaining stationary during operation.
In this paper, we suggest a dynamical system that can operate as a virtual clock individual nodes of a WSN may use to estimate the gateway node (GWN) time after which they may use the estimate to reset their physical clocks. The system accepts, as input, the values neighboring nodes have for their local time and produces, as output, an estimate of the GWN time. It does that by averaging the input local times of the neighboring nodes. The system can terminate its local time update while in the transient phase by using a stopping criterion derived from the dynamical nature of the estimate time series. The nodes constituting the WSN are guaranteed to converge each to a local time that is close to that of the GWN provided that a path exist from the GWN that spans all the nodes of the WSN.

II. THE SYNCHRONIZATION PROCEDURE
In this section, the analogy to an electric circuit used to develop the synchronizer is explained. Also, the components of the system are presented.

A. The Resistive Network Metaphor
To have a reasonable ability to function in harsh environments, the correctness of a node behavior (micro-properties of the WSN) should not be conditioned on global properties the WSN must possess. For example, a manner in which a node function that assumes a certain network connectivity or a labeling system is highly unlikely to succeed in harsh environments where the connectivity and labeling schemes can be easily invalidated by a node getting damaged. The manner in which a node function should be indifferent to the label of a node if the node is part of the group constituting the WSN. This immediately excludes the possibility of a node using multi-hop communication. This indifference also undermines a node's ability to make use of a global connectivity scheme the network may have.
It may appear difficult to find a node-level synchronization procedure that requires only single hop communication, is not strongly reliant on a communication (connectivity) arrangement and provides guarantees on the networks ability to function. However, a quick examination of electrical networks, as shown in Figure-1, proves otherwise [9]. If the voltage of any node in an electrical network is fixed to a certain value V, all the other non-isolated nodes (i.e a path exists from a node to the fixed voltage node) will register the same voltage. The nodes of the electric network function in a manner that is indifferent to the labels of the other nodes or their connectivity scheme provided that a path from the fixed voltage node exists that spans all the nodes of the network. Moreover, deleting or inserting new nodes into the network will not affect the operation if the new nodes are part of a spanning path or the removed nodes do not render the set of spanning paths the empty set. As can be seen, a strong analogy exists between the local time of a WSN node and the voltage of a resistive electrical circuit. This analogy is exploited to build a WSN synchronizer with the desired properties.
where N is the number of nodes in the WSN, and χ i is the set of neighbors to node i and C i is the cardinality of χ i . The nodes of the WSN may be expressed as the discrete time state space sysetm with a ramp input: , B is a column vector with binary elements 0,1 ( ). If the i'th element of B is zero, it means that the i'th node is not connected to the gateway node; otherwise, there is a connection between the two. The matrix A contains nonnegative elements, ( where the L-1 norm of i a ( 1 i a ) satisfies the following: The error as a function of the discrete time can be expressed as the discrete state space system: (2) is unconditionally marginally stable regardless of the connectivity of the network. It is simple to show that if the network contains a spanning path and if B is not all zeros (i.e. the gateway node is connected to at least one of the WSN nodes), the system in (2) is stable with steady state error: C. The Stopping Criterion Equation (6) states that the system in (2) is capable of bringing the local times of the WSN nodes arbitrarily close to that of the gateway node by simply reducing ∆T. This is not practical in the case of WSN. In WSNs communication can quickly drain a node's battery. It is well-known in a WSN that the energy consumed in communicating (transmitting) one bit is equal to the energy consumed in processing one million bits within the node.
An alternative to increasing the synchronization accuracy without using excessively high communciation rates may be obtained by examining the dynamical behavior of equations (2) and (6). It is noticed that all the nodes of a network whose time upate is govered by (2) experience a strong dip in the absolute value of the error prior the steady state phase as shown in Figure-2. This is caused by the evolving local time of the node intersecting the time of the gateway node. Ideally, the error should drop to zero. However, for a finite message exachage rates, it is observed that the abosulue value of the error significantly drops for all the nodes to values well below ∆T. Formal mathematical investigation of this behavior is left for future work.  p=1). The other one has to do with maximum connectivity ambiguity (i.e. one has no ability to predict whether a channel is going to be available or not, p=0.5). As can be seen in both cases, the dip trend in the absolute value of the error persisted. Moreover, it is noticed that the times the dips occur for all the network nodes are very close. This observation provides an oppurtunity to both significantly reduce the amount of communications a node has to perform and obtain high accuracy estimates of the GWN time.
We need to have a stopping criterion (SC) to terminate the iterative process (the iterations) way before the steady state. This is carried-out by exploiting the dip behaviour which the protocol exhibit. Without this, the advantage and characteristics of the synchronization protocol will not be practical. Many SCs exist in the literature that used different stopping conditions such as maximum time, maximum number iterations, specific bound reach, mean value, standard deviation, variance, relative function, absolute function, … etc. These SCs work well in the SS region but they will not work in the transient region.
A detection filter that operates on the local time series has to be used by each node on the evolving local time estimate. This filter generates the indicator signal that will be used in localizing the instant at which the evolving local time coinside with the GWN time. A logical rule is then applied to pinpoint the local instant that will be selected as the global time. This instant is used to initialize the physical clock of the node. The rule is based on polarity change of the filter output provided that K communication cycles have elapsed. We found that K=11 works for all the cases we tested.
Although it may not be optimal, but a simple finite impulse response (FIR) difference filter to detect a change in slope can be used. This is sufficient for the scope of this work since formal design of such a filter is a mathematically involved task that requires formal investigation of the patterns the dynamics of equations (2) and (5) generate. Optimmum desing of such filter will be left for future investigation. We suggest a from of FIR difference filter with the impulse response, h(n), given by: where c f is a positive constant whose value is close to unity ( ). c f can be taken equal to 1 without affecting much the performance of the filter. This filter is found to produce good results.

III. RESULTS
The experiments are carried-out using the MicaZ sensor network from MEMSIC. Experiments were performed on a variety of networks. However, here we report results for a 16 node network with grid connectivity (Figure-5). The communication frequency is approximately 1KHz, Cf=1.002 and the Packet Size is 64bits. The soft clocks of the nodes were arbitrarily initialized. Figure-6 shows the evolution of the time error curves for all the nodes as a function of the server time before the network is considered synchronized and node communication seized. The data from the experiment is shown in Table-1. As can be seen, the minimum error at the peak of the dip region is considerably less than the 1 millisecond communication cycle. It is also worth noticing that the minimum error for all nodes occurred around the same time as if the network block-synchronize. The detection filter performs reasonably well yielding timing errors that are close to the minimum with number of communication cycles very close to the minimum needed. While in few cases (N12 and N15) the error is much higher than the minimum, it is still lower than the steady state error with significant saving in communication. From the above, it is obvious that better design of the detection filter can yield significant increase in synchronizing accuracy. Another reason for a better filter/decision design has to do with the noise physical implementation of the synchronizer introduces. Figure-7 shows the evolution of the error curves for a node in a four-node network along with the decision of when to stop the soft clock. While the decision filter performed well for simulation, the noise physical implementation introduced adversely affected its performance.  The suggested protocol is compared to the two popular protocols for WSN synchronization. The first is the

Rated Flooding Time Synchronization Protocol (RFTSP) and Energy-Efficient Gradient Time
Synchronization Protocol (EGTSP) [10]. RFTSP and EGTSP are compared to the suggested protocol using a nine-node WSN. Figure-9 shows the error profile of the node with maximum error value. As can be seen, the suggested protocol synchronizes faster than the other two. More importantly, it provides a clear indication of when the protocol has to stop. The above clearly show the practicality of the suggested synchronization procedure for use with WSNs in challenging environments.

IV. CONCLUSION
The paper suggests a synchronization procedure that addresses the needs of WSNs operating in harsh environment. The experimental results and the simulation clearly demonstrate the capabilities of the suggested synchronizer. Future work will focus on mathematical analysis of the synchronizer, better design of the detection filter and experimental investigation when connectivity is stochastic.