CN104039006A - Clock synchronization method for wireless sensor network - Google Patents

Abstract

The invention discloses a clock synchronization method for a wireless sensor network. The method is improved aiming at the existing clock synchronization method. In the wireless sensor network, nodes achieve a synchronous state by exchanging information packages containing timestamps, the transfer process of the information packages is not instantaneously finished, some time is needed during all information sending, receiving and processing processes, and message transfer time delays with non-determinacy are generated in these time. According to the method, Bayesian estimation is carried out on receiving time according to the characteristic that errors due to the message transfer time delays obey normal distribution with an expected value of 0, so as to obtain a more accurate receiving time, thus improving the accuracy of clock synchronization.

Description

A Clock Synchronization Method for Wireless Sensor Networks

technical field

The invention relates to a clock synchronization method of a wireless sensor network, which belongs to the technical field of computer communication.

Background technique

The research on clock synchronization technology in wireless sensor networks has become a hot spot in the industry. In a wireless sensor network, it depends on the cooperation of all sensor nodes to complete system functions, such as node positioning, data fusion, TDMA scheduling, cooperative sleep, etc., all of which are based on accurate clock synchronization of nodes. For traditional networks, clock synchronization technologies are widely used, such as time synchronization protocols NTP and GPS. However, wireless sensor networks are different from traditional networks. Due to the influence of complexity, power consumption, cost, size and other factors, the time synchronization protocols NTP and GPS cannot be used in wireless sensor networks. A clock synchronization protocol for wireless sensor networks.

The existing clock synchronization methods in wireless sensor networks can be mainly divided into three categories: 1. The receiver-receiver-based synchronization method, the representative method of which is the RBS (Reference Broadcast Synchronization) method; 2. The sender-based synchronization method —The two-way synchronization method of the receiver, its representative method is the TPSN (Timing-Sync Protocol for Sensor Networks) method proposed by Ganeriwal et al. and the TINY-SYNC/MINI-SYNC method proposed by M.L.Sichitiu et al.; 3. Based on A sender-receiver one-way synchronization method is typically FTSP (Flooding Time Synchronization Protocol). Most of the current synchronization methods are improvements to the above methods, and the main indicators to measure the advantages and disadvantages of the improved clock synchronization methods are the clock synchronization accuracy and the energy consumption of the network. However, in wireless sensor networks, the two main sources of error in time synchronization are information transmission delay and instability of crystal oscillator frequency. And the present invention can well solve the above problems.

Contents of the invention

The purpose of the present invention is to propose a clock synchronization method for wireless sensor networks aiming at the problem of uncertain information transmission delay in traditional time synchronization algorithms, which can improve the accuracy of clock synchronization.

The technical scheme that the present invention solves its technical problem is: the present invention provides a kind of clock synchronization method (abbreviation, TPSN-B) of wireless sensor network, and this method is divided into hierarchical discovery process and synchronous process, comprises the following steps:

Step 1: Hierarchy discovery process;

The hierarchical network structure is regarded as a spanning tree, assuming that the root node of the tree is the clock source node, and its hierarchical number is set to 0. The root node broadcasts an information packet, which contains the ID of the root node and the layer number. Once the nodes within the communication range receive the information packet, they set their own layer level to the layer number in the information packet plus 1. Then, these nodes broadcast new information packets containing their own IDs and hierarchy numbers, and the received nodes set their own hierarchy numbers in the same way, and so on, until the nodes in the entire network have established their own hierarchy levels. When a node that already has a layer number receives the broadcast information packet again, it ignores it.

Step 2: Synchronization process;

Starting from the root node, two nodes at adjacent levels exchange information packets containing time stamps, and Bayesian estimation is performed on the receiving time at the receiving node to obtain a more accurate receiving time and complete the two nodes at adjacent levels. synchronization between nodes.

Step 3: Repeat the above step 2 until all nodes in the network complete the clock synchronization process.

The synchronous process of method step 2 of the present invention comprises the following steps:

1) Assuming that the layer numbers of nodes R and S are respectively kth layer and k+1 layer, when synchronizing, the upper layer node R broadcasts a time synchronization request packet to notify S node to prepare for time synchronization.

2) Node S sends a synchronization packet containing time T ₁ to node R at time T ₁ after waiting for a random period of time.

3) After node R receives the information packet, it uses the local clock to record the receiving time T ₂ , and performs Bayesian estimation on the receiving time T ₂ to obtain a more accurate receiving time T ₂ ':

4) Then node R sends a confirmation message to node S at time T ₃ in the same way, the message contains (T ₁ , T ₂ , T ₃ ).

5) Node S records the time T ₄ of receiving the message with local time at T ₄ , and performs Bayesian estimation on T ₄ to obtain a more accurate receiving time T ₄ ',

6) Calculate the new time offset Δ':

The node in the present invention adjusts its own local clock according to Δ.

Beneficial effect:

1. The present invention well solves the problem of uncertainty in transmission delay of information packets exchanged during the synchronization process.

2. The present invention can better improve the precision of clock synchronization.

Description of drawings

FIG. 1 is a schematic diagram of the process of forming a node hierarchy in the present invention.

Fig. 2 is a schematic diagram of the synchronization process of adjacent layer nodes in the present invention.

Fig. 3 is a flow chart of the method of the present invention.

Detailed ways

The invention will be described in further detail below in conjunction with the accompanying drawings.

As shown in Fig. 1, Fig. 2 and Fig. 3, the present invention provides a kind of clock synchronization method of wireless sensor network, and this method comprises the following steps:

1) According to the above-mentioned layer discovery process of the present invention, form the layer relation between nodes, set root node as layer 0, have K layers altogether, all nodes in the sensor network are all synchronized with the clock of root node (layer 0).

2) Assuming that the layer numbers of nodes R and S are respectively kth layer and k+1 layer, when synchronizing, the upper layer node R broadcasts a time synchronization request packet to notify S node to prepare for time synchronization.

3) Node S sends a synchronization request message to node R at time T ₁ after waiting for a random period of time, and the message includes sending time T ₁ and standard deviation σ ₁ of T ₁ .

4) The node R uses local time to record the time of receiving the information packet sent by S as T ₂ , and the time value obtained through Bayesian estimation is T ₂ '. Because the error of the node clock value obtained by TPSN through message passing is a normal distribution, that is The value of _σ2 can be calculated from the received time values. According to sending time T ₁ , receiving time T ₂ , variance and A more accurate estimate of the received time T ₂ ' and its variance can be obtained

$\begin{array}{c}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\\ {\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{<span\; class="notranslate">\; \&prime;</span>\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}\end{array}$

5) Then node R sends a confirmation message to node S at time T ₃ in the same way, the message contains (T ₁ , T ₂ ′, T ₃ , σ ₃ ).

6) Node S receives the acknowledgment packet from node R at time _T4 , and uses the same method to obtain the new receiving time _T4 ' and its variance according to Bayesian estimation

$\begin{array}{c}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}\\ {\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}^{<span\; class="notranslate">\; \&prime;</span>\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}\end{array}$

At this point, node S obtains a set of time stamps (T ₁ , T ₂ ′, T ₃ , T ₄ ′). Calculate the corresponding new time offset Δ' and adjust the local clock according to Δ':

${\mathrm{<span\; class="notranslate">\; \&Delta;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span>\frac{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; 2</span>}}$

7) Repeat the above steps until all nodes on the Kth layer have also completed the synchronization process.

Claims (4)

1. a clock synchronizing method for wireless sensor network, described method comprises the steps:

Step 1: level discovery procedure;

The stratified network configuration of tool is regarded as to spanning tree, and the root node of hypothesis tree is served as clock source node, and establishing its level number is 0; A packets of information of root node broadcast, the ID that comprises root node and level number, once the node in communication range is received packets of information, the stratum level of oneself is set to packets of information and adds 1 middle-level number; Then, the packets of information of the ID that comprises oneself that these node broadcasts are new and level number, the node receiving arranges the level number of oneself in the same way, goes down by that analogy, until the node in whole network is all set up the hierarchy levels of oneself; When the node of the number of having levels receives the packets of information of broadcast again, do and ignore processing;

Step 2: synchronizing process;

From root node, between two nodes of adjacent level, exchange packets, containing the packets of information of timestamp, and is carried out Bayesian Estimation at receiving node place to time of reception, obtains time of reception more accurately, completes synchronous between two nodes of adjacent level;

Step 3: repeat above-mentioned steps 2, until all nodes complete clock synchronous process in network.

2. the clock synchronizing method of a kind of wireless sensor network according to claim 1, is characterized in that, the step 2 of described method comprises:

1) level number of supposing node R and S is respectively k floor and k+1 floor, and when synchronous, upper layer node R broadcast a time synchronized request packet, notifies S node to carry out the preparation of time synchronized;

2) node S is after the wait of one section of random time, at T ₁constantly to node R, send and contain T constantly ₁synchronizing information bag;

3) node R receives after packets of information, with local clock, records time of reception T ₂, and to time of reception T ₂row Bayesian Estimation, obtains time of reception T more accurately ₂':

4) then node R in the same way at moment T ₃to node S, send an acknowledge message, in this message, comprise (T ₁, T ₂, T ₃);

5) node S is at T ₄constantly with local zone time, record the time T of receipt message ₄, and to T ₄carry out Bayesian Estimation, obtain time of reception T more accurately ₄',

The time migration Δ that 6) calculating makes new advances ': node is adjusted the local clock of oneself according to Δ.

3. the clock synchronizing method of a kind of wireless sensor network according to claim 2, is characterized in that, the step 3 of described method couple time of reception T ₂the method of carrying out Bayesian Estimation comprises:

It is a normal distribution that described method is utilized the error of the nodal clock value that message transmission obtains, from the time value receiving, calculate σ ₂value, according to transmitting time T ₁, time of reception T ₂, variance with obtaining time of reception is more accurately:

$T_2^{\&prime;}=\frac{{\mathrm{\&sigma;}}_2^2}{{\mathrm{\&sigma;}}_1^2+{\mathrm{\&sigma;}}_2^2}{T}_1+\frac{{\mathrm{\&sigma;}}_1^2}{{\mathrm{\&sigma;}}_1^2+{\mathrm{\&sigma;}}_2^2}{T}_2$

。

4. the clock synchronizing method of a kind of wireless sensor network according to claim 2, is characterized in that, in the step 5 of described method to time of reception T ₄the concrete grammar that carries out Bayesian Estimation is:

$T_4^{\&prime;}=\frac{{\mathrm{\&sigma;}}_4^2}{{\mathrm{\&sigma;}}_3^2+{\mathrm{\&sigma;}}_4^2}{T}_3+\frac{{\mathrm{\&sigma;}}_3^2}{{\mathrm{\&sigma;}}_3^2+{\mathrm{\&sigma;}}_4^2}{T}_4$

。