The clocks of sensor nodes are not perfect and can drift in time, so the observed time is different for the nodes in the network. However, many applications of network protocols require a ***similar time to make all or part of the nodes in the network synchronized at the instant.?
First, sensor nodes need to operate and collaborate with each other in parallel to accomplish complex sensing tasks. If the sensor nodes lack a uniform timestamp (i.e., are not synchronized) during the information gathering process, estimates will be inaccurate.?
Second, many energy-saving solutions are implemented using time synchronization. For example, sensors can be put to sleep when appropriate (by turning off the sensor and transceiver to enter an energy-saving mode) and then woken up when needed. When applying this energy-saving mode, the nodes should go to sleep and wake up at the same time, which means that the node's receiver can receive the data when it arrives, and this requires precise timing between the sensor nodes.?
2?Key performance parameters of interest for time synchronization technology?
The fundamental purpose of time synchronization technology is to provide the local clocks of the nodes in the network with the **** same timestamp. The time synchronization for Wireless?Sensor?Networks (WSNs)[1]
should should mainly consider the following aspects:?
(1) Energy efficiency. The longer the time of synchronization, the more energy is consumed and the less efficient it is. Designing time synchronization algorithms for WSNs needs to be based on the premise of considering the effective energy resources of the sensor nodes.?
(2)? Scalability and robustness. The time synchronization mechanism should support the effective expansion of the number or density of nodes in the network, and guarantee that once a node fails, the remaining network is effective and functional.?
(3) Accuracy. The need for accuracy varies for different applications and purposes.?
(4) Synchronization period. The length of time that a node needs to keep its time synchronized can be instantaneous or as long as the lifetime of the network.?
(5) Effective synchronization range. Time can be given to all nodes within the network or to nodes in a localized area.?
(6) Cost and size. Synchronization may require specific hardware, in addition, the size affects the implementation of the synchronization mechanism.? (7) Maximum error. The maximum time difference between a set of sensor nodes, or the maximum difference relative to an external standard time. ?3?A study of the main existing time synchronization methods?
Time synchronization technology is an important issue in the study of WSNs, and many specific applications require the synchronization of the local clocks of the sensor nodes, requiring various degrees of synchronization accuracy.WSNs are self-organizing, multi-hop, dynamic topology and resource-constrained, especially the nodes have limited energy resources, computational power, communication bandwidth, storage capacity, etc., which makes time synchronization schemes have their special
special needs and also make traditional time synchronization algorithms unsuitable for these networks [2]. Therefore more and more research is focused on designing
time synchronization algorithms suitable for WSNs [3]
. Many new time synchronization algorithms have been proposed for WSNs from different perspectives [4]
.?
3.1?Bidirectional synchronization mode for pair-wise (pair-wise) synchronization?
The representative algorithm is the Time Synchronization Protocol for Sensor Networks TPSN (Timing-Sync?Protocol?for?Sensor?
Networks) [5~6]
. The aim is to provide time synchronization between nodes across the entire network range of the WSN.?
The algorithm has two steps: hierarchical and synchronization. The purpose of the first step is to create a hierarchical topological network, where each node has a level. Only one node communicates with the outside world to obtain outside time, which is designated as level zero, called the root node, and serves as the time source for the entire network system. In the second step, each level i node is synchronized with the level i-1 (previous) node, and eventually all nodes are synchronized with the root node to achieve time synchronization of the whole network. The detailed time synchronization process is shown in Figure?1?
Figure 1?TPSN?synchronization process?
Let R be the upper node and S be the lower node, the propagation time is d, and the time deviation of the two nodes is θ. The synchronization process consists of the broadcasting of the start synchronization message by node R, and the preparation of the time synchronization process starts after node S receives the message. At the moment T1, node S sends a synchronization packet containing information (T1), node R receives the synchronization information at T2 and records the reception time T2, where the relation: 21TTd?
Node R sends a reply packet at the moment T3, containing information (T1,T2,T3). At the moment T4 S receives the synchronization information packet, which satisfies the relation: 43TTd?
Finally, node S can calculate the value of ?
Using the above 2 time expressions, node S can calculate the ? the value of (21)(43)2
TTTT?
TPSN reduces the uncertainty at the sending end and eliminates the time synchronization error caused by the access time due to the way of marking the synchronization packet with a timestamp at the MAC layer, making the synchronization effect more effective. Moreover, the synchronization error of the TPSN algorithm for any node depends on the number of hops it is away from the root node and has nothing to do with the total number of nodes in the network, so that the TPSN synchronization accuracy does not degrade with the increase in the number of nodes, which makes the TPSN scalable.The disadvantage of the TPSN algorithm is that once the root node is invalidated, it is necessary to re-select the root node, and to re-administer the grading and synchronization phases, which increases the computational and energy overhead, and the synchronization error grows linearly with the increase in the number of hops, which is less accurate. In addition, the TPSN algorithm does not estimate the frequency difference of the clocks, which makes it necessary to synchronize frequently and consume more energy to complete one synchronization.?
3.2?Receiver-Receiver (RR) mode?
The representative algorithm is the reference broadcast time synchronization protocol RBS (Reference?Broadcast?Synchronization) [7]
RBS is a typical receiver-receiver based synchronization algorithm, which was developed by Elson et al. with the idea of "third node" to achieve synchronization. " idea to achieve synchronization was proposed. In this algorithm, the broadcast channel characteristics of the wireless data link layer are utilized, and the basic idea is that a node (as a sender
sender) periodically sends a beacon message to its neighboring node (as a receiver) via a physical layer broadcast [10]
, and the neighboring node records the time at which the broadcast beacon is reached, and compares this time as a reference point with the clock reading. To calculate the clock offset, timestamps between peer neighbor nodes are exchanged to determine the time offset between them, and then one of them modifies its local time based on the difference in time it receives
, thus synchronizing the time [11]
.?
If the algorithm has n receiver nodes m reference broadcast packets in the network, any node receiving m reference packets will take the time of arrival of these reference packets and compare it with the time of arrival of the reference packets received by the other n-1 receiver nodes and then exchange the information. Figure 2 shows the critical path schematic of the RBS algorithm.?
Network interface card
Critical path
Receiver 1
Sender
Receiver 2
Fig. 2?Critical path schematic of the RBS algorithm?
The formula is as follows: ?
,,1
1,:[,]()m
jkikkinjnoffsetijTTm?
Where n denotes the number of receivers, m denotes the number of reference packets, and ,rbT denotes the clock at which the receiver node r receives the reference packet b.?
This algorithm does not synchronize the senders and receivers, but synchronizes the receivers with each other, effectively avoiding the effect of send access time on synchronization, removing the uncertainty of the sender's delay from the critical path, and the source of the error is mainly the uncertainty of the transmission time and the reception time, thus obtaining a higher accuracy than the method of synchronization using the bi-directional exchange of information between nodes. The biggest disadvantage of this method is that there are too many exchanges of information, and the sending nodes and receiving nodes, and the receiving nodes among themselves, have to exchange messages to achieve synchronization. The computational complexity is high, and the network traffic overhead and energy consumption are too high to be suitable for occasions with limited energy supply.?
3.3?Sender-Receiver (SR) model?
The basic principle of the time synchronization algorithm based on the sender-receiver mechanism is that the sending node sends a time synchronization message containing a local timestamp, and the receiving node records the local received time and compares it with the timestamp in the synchronization message to adjust the local clock. The following two time synchronization algorithms are proposed based on this approach.?
3.3.1?FTSP?Algorithm[8]
Flooding Time Synchronization Protocol FTSP (Flooding?Time?Synchronization?Protocol) was proposed by Branislav?Kusy et al. at Vanderbilt University, with the goal of achieving network-wide time synchronization across the network with microsecond errors. The algorithm uses a single broadcast message to synchronize the time between the sending and receiving nodes.?
It is characterized by (1) further reducing the uncertainty of the delay by analyzing the sending and receiving processes and subdividing the delay into sending interrupt processing delay, encoding delay, propagation delay, decoding delay, byte alignment delay, and receiving interrupt processing delay; (2) transmitting multiple signaling packets, which allows the receiving node to estimate the frequency difference and initial phase difference between itself and the transmitting node by using the least-square linear fitting technique; and (3) using a single broadcast message to synchronize the time between the sending node and the receiving node with a single broadcast message, with the error controlled at the microsecond level. difference and initial phase difference; (3) designing a set of root node election mechanism optimized for node failure, new node joining, topology change
, etc., which is suitable for harsh environments [12]
?
The FTSP algorithm performs a linear regression analysis of clock drift. This algorithm takes into account that the node clock crystal frequency is stable within a specific time range, so the clock offset between nodes is linearly related to time, by sending nodes periodically broadcast time synchronization messages, the receiving node obtains multiple pairs of data, constructs the best-fit straight line, and by regressing the straight line, the node can calculate the clock offset between nodes at a certain time directly through it within the time interval allowed by the error and without having to send a time synchronization message for calculation, thus reducing the number of messages sent and lowering the system energy overhead.?
FTSP combines the advantages of TPSN and RBS, which not only excludes the effect of sender's delay, but also makes an effective estimation of the receiver's uncertain delays (such as interrupt processing time, byte alignment time, hardware coding and decoding time, etc.) in the transmission of messages. The multi-hop FTSP protocol uses a hierarchical structure with the root node as the synchronization source, which can accommodate a large number of sensor nodes, and is robust to changes in network topology and root node failure with better accuracy. The algorithm compensates for the relevant error sources by using MAC layer timestamps and linear regression bias compensation, and greatly reduces the impact of interruptions and decoding time by hitting multiple timestamps for a packet, and thus averaging and filtering out jittery timestamps.FTSP?uses flooding to transmit time information from the time base node to the remote nodes, and flooding can be generated by the transit node, so error accumulation is inevitable. In addition, FTSP has a huge overhead of power consumption and bandwidth.?
3.3.2?DMTS?Algorithm [9]
Delayed Measurement Time Synchronization DMTS?(delay?measurement?time?synchronization)? algorithm is based on the sender-receiver synchronization mechanism.The implementation strategy of DMTS? algorithm is to sacrifice part of the time synchronization accuracy for lower computational complexity and energy consumption, which is a time synchronization algorithm with light energy consumption.
Delayed Measurement Time Synchronization (DMTS) is a time synchronization algorithm based on the sender-receiver synchronization mechanism.
The basic principle of DMTS algorithm is: select a node as the time master node to broadcast the synchronization time, all the receiving nodes calculate the time adjustment value by accurately measuring the delay of the one-way time broadcast message from the transmitting node to the receiving node and combining it with the transmitting node's timestamps, the receiving node sets its time to be the time of receiving the message carrying plus the transmission delay of the broadcast message, adjusting The receiving node sets its time as the time it receives the message plus the transmission delay of the broadcast message, adjusts its own logical clock value to reach synchronization with the reference point, so that all the nodes that get the broadcast message are time synchronized with the master node. The time delay dt of the sending and receiving nodes can be derived from 21()dtnttt. Where nt is the time required to send the leading code and the start character, n is the number of message bits sent, t is the time required to send one bit; 1t is the local time of the receiving node at the time of arrival of the message; 2t is the local time recorded by the receiving node at the moment before it adjusts its own clock, and 21()tt?is the reception processing delay.?
The advantage of the DMTS?algorithm is that it combines techniques such as link-layer time-stamping and delay estimation, eliminating the effects of sending delay and access delay, with a simple algorithm and low communication overhead. However, the DMTS algorithm does not estimate the frequency deviation of the clock, the clock is kept synchronized for a shorter time, it does not estimate the time delay generated by the bit offset, and it does not eliminate the influence of the clock timing accuracy on the synchronization accuracy, so its synchronization accuracy decreases slightly compared to the FTSP, and it is not suitable for the applications that require high-precision synchronization such as positioning.?
The algorithm based on the sender-receiver unidirectional synchronization mechanism requires the least number of time synchronization messages to be sent among the above three types of methods. The sender node only needs to send the synchronization message once, thus it has lower network traffic overhead and complexity and reduces the system energy consumption.?
4?Conclusion?
The article describes the types of WSN time synchronization algorithms and their respective representative algorithms, and analyzes the design principles, advantages and disadvantages of each algorithm. These protocols solve the main problems encountered in time synchronization in WSNs, but for large networks, the existing methods have more or less problems: poor scalability, low stability, slower convergence, network communication conflicts, and increased energy consumption. Future research hotspots will focus on energy saving and security of time synchronization. This will put higher requirements on the fault tolerance, effective range and scalability of the algorithms.?