METHOD OF SYNCHRONIZING NODES IN A DETERMINIST MESH NETWORK

Abstract

The present invention relates to a method for synchronising a node in a deterministic mesh network, in particular a network of sensors using a channel hopping (TSCH) transmission medium access mode. Each node measures the successive synchronisation offsets of its local clock in relation to those of neighbour nodes with which it enters into communication, the measurement being carried out by detecting a reception event of a packet transmitted by the neighbour node or an acknowledgement of a packet transmitted by said node to the neighbour node. The node estimates from these synchronisation offsets, a synchronisation offset for the timeslot and corrects its local clock by a fraction of the synchronisation offset thus estimated. Said fraction may be determined by means of multi-agent reinforcement learning (MARL), each agent being associated with a node of the network.

Claims

1. Method for synchronising a node in a deterministic mesh network, the access of the nodes of the network to the transmission medium being programmed according to a slotframe split into timeslots, said node being able to communicate with its neighbour nodes during timeslots of the slotframe by using transmission resources, said node being provided with a local clock and measuring the synchronisation offsets of this clock in relation to the local clock of at least one neighbour node by detecting a reception event of a packet transmitted by the neighbour node or an acknowledgement of a packet transmitted by said node to the neighbour node, characterised in that said node estimates, from at least one synchronisation offset thus measured, a future synchronisation offset of the local clock for a timeslot following the one for which the last measurement was carried out and corrects its local clock by a correction value equal to a fraction of the synchronisation offset thus estimated.

2. Method for synchronising a node according to claim 1, characterised in that the synchronisation offset measured is not taken into account for the correction if it is greater than a first predetermined threshold value.

3. Method for synchronising a node according to claim 1, characterised in that the fraction is less than half of the estimated synchronisation offset.

4. Method for synchronising a node according to claim 1, characterised in that when said correction value is greater in absolute value than a second predetermined threshold value, a synchronisation fault is signalled.

5. Method for synchronising a node according to claim 1, characterised in that the node estimates a future synchronisation offset of its local clock from a plurality N of synchronisation offsets, measured during past timeslots and the current timeslot, the node being in communication with one of its neighbour nodes during the past timeslots and the current timeslot.

6. Method for synchronising a node according to claim 5, characterised in that the node estimates the future synchronisation offset by carrying out a linear regression on the N synchronisation offsets, measured during past timeslots and the current timeslot.

7. Method for synchronising a node according to claim 5, characterised in that the node records in a FIFO stack the (N−1) synchronisation offsets measured during past timeslots, independently of the neighbour node with which said communication was established.

8. Method for synchronising a node according to claim 5, characterised in that the node records in a plurality of FIFO stacks the synchronisation offsets measured during past timeslots, each stack being associated with a neighbour node and only storing the synchronisation offsets in relation to the neighbour node with which it is associated.

9. Method for synchronising a node according to claim 1, characterised in that the fraction of the estimated synchronisation offset is obtained by means of multi-agent reinforcement learning, each agent being associated with a node of the network.

10. Method for synchronising a node according to claim 1, characterised in that the network of nodes possesses a physical layer in accordance with the standard IEEE 802.15.4, a data link layer in accordance with the standard IEEE 802.15.4e, the access control of the nodes to the transmission medium being performed in TSCH mode.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0040] Other features and advantages of the invention will become apparent upon reading a preferable embodiment of the invention, described with reference to the appended figures, wherein:

[0041] FIG. 1 schematically shows an example of transmission scheduling between nodes of a WSN network using the TSCH protocol;

[0042] FIG. 2 shows an example of timing chart for transmitting and receiving a packet for two nodes of a WSN network using the TSCH protocol;

[0043] FIG. 3 shows an example of timeslot template attack in a WSN network using the TSCH protocol;

[0044] FIG. 4 schematically shows time offsets measured by a node in order to synchronise according to the synchronisation method of the invention;

[0045] FIG. 5 schematically shows a flowchart of the method for synchronising a node in a deterministic mesh network, according to one embodiment of the invention.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

[0046] It will subsequently be considered a deterministic mesh network within the meaning of the foregoing, of fixed or dynamic topology. The network is meshed and each node may enter into communication with its neighbours, in transmission or in reception. Furthermore, it is assumed that the medium access of the various nodes is programmed according to slotframes, each slotframe itself being split into timeslots, the access of the nodes during a timeslot using distinct transmission channels so as to prevent the collisions of packets between various communications. The transmission resources used by the various channels during a timeslot may in particular be frequencies, multiplex subcarrier chunks OFDM, orthogonal codes, or even a combination of the preceding resources. The access control of the various nodes is programmed during each slotframe by a scheduling matrix whereof one of the dimensions (hereafter the columns) corresponds to the timeslots and the other dimension (hereafter the rows) corresponds to the transmission resources in question.

[0047] A typical case of application of the present invention is that of a network of sensors (WSN network) whereof the physical layers (PHY) and data link layers (MAC) are respectively in accordance with the standards IEEE 802.15.4 and IEEE 802.15.4e and whereof the medium access control is carried out by channel hopping according to the TSCH mode as described in the introductory part. The TSCH mode may be used within the scope of a plurality of protocol stacks, for example in 6tiSCH (IPv6 on TSCH mode), 6LoWPAN, WirelessHART (Highway Addressable Remote Transducer), Wi-SUN (Smart Ubiquitous Networks) networks, etc.

[0048] We will subsequently consider a pair of nodes of the network in question, namely a transmitter node and a receiver node in communication with one another during a given timeslot A.sup.i=[T.sub.0.sup.i, T.sub.0.sup.i+1], corresponding to the i.sup.th column of the scheduling matrix. The transmitter node and the receiver node use the transmission resource specified in the scheduling matrix during the timeslot, A.sup.i.

[0049] As illustrated in the timing chart of FIG. 4, the transmitter node 410 transmits a packet on this resource at the time T.sub.1.sup.i=T.sub.0.sup.i+TsTxOffset, measured by its local clock H1. More specifically, the start frame delimiter (SFD) leaves the transmitter node at this time, such as measured by H1. The packet (that is to say its delimiter SFD) is received by the receiver node at the time R.sub.1.sup.i, such as measured by its local clock, H2. The receiver node deduces therefrom a first synchronisation offset δ.sub.1.sup.i=R.sub.1.sup.i(T.sub.0.sup.i+TsTxOffset), it being understood that the values T.sub.0.sup.i,TsTxQffset are known of all of the nodes of the network and that (T.sub.0.sup.i+TsTxOffset) is measured by means of the local clock of the receiver node.

[0050] At the end of the receipt of the packet (that is to say on receipt of the end frame delimiter), the receiver node waits for a time TsTxAckDelay and sends an acknowledgement back to the transmitter node, during a time T.sub.2.sup.1, such as measured by its local clock, H2. The acknowledgement is received by the transmitter node at the time R.sub.2.sup.i, such as measured by its local clock, H1. The transmitter node deduces therefrom a second synchronisation offset δ.sub.2.sup.i=R.sub.2.sup.i−T.sub.2.sup.i=R.sub.2.sup.i−(T.sub.0.sup.i+TsTxOffset+Tpacket+TsTxAckDelay), it being understood that the value TsTxAckDelay is known by all of the nodes of the network and that, by definition, the duration of the packet, Tpacket, is known by the transmitter node. The time T.sub.2.sup.i=(T.sub.0.sup.i+TsTxOffset+Tpacket+TsTxAckDelay) is measured by means of the local clock of the transmitter node, H1.

[0051] At the end of this exchange, the receiver node disposes a first synchronisation offset, δ.sub.1.sup.i, and the transmitter node disposes a second synchronisation offset, δ.sub.2.sup.i.

[0052] Subsequently, we will note in a generic manner, δ.sup.i, in order to indifferently designate the first (or the second) synchronisation offset, δ.sub.1.sup.i (δ.sub.2.sup.i), measured by a node during the timeslot A.sup.i.

[0053] This synchronisation offset calculation is repeated for all of the access slots during which a node is in communication (in transmission or in reception).

[0054] In the aim of simplifying the presentation and without loss of generality, we will assume that the timeslots during which the node is in communication are consecutive and will note i−N+1, . . . , i−2, i−1, i, the indexes of these slots, with N≥1. The synchronisation offsets successively measured by the node are respectively noted δ.sup.i−N+1, . . . , δ.sup.i−2, δ.sup.i−1, δ.sup.i. From these synchronisation offsets thus measured, the node estimates its next synchronisation offset, i.e. {circumflex over (δ)}.sup.i+1, and carries out a synchronisation correction of a time η{circumflex over (δ)}.sup.i+1, with a catch-up factor η, 0<η≤1/2, before the start of the following access slot.

[0055] Thus, it is understood that if the local clock of the node delays in relation to the local clock of the node with which it is in communication, this clock must be advanced by η|{circumflex over (δ)}.sup.i+1|. Inversely, if the local clock of the node advances in relation to the local clock of the node with which it is in communication, this clock must be delayed by η|{circumflex over (δ)}.sup.i+1|.

[0056] If it is now designated by N.sub.1 and N.sub.2 the two nodes in communication during the timeslot A.sup.i, and that it is noted respectively {circumflex over (δ)}.sub.N.sub.1.sup.i+1 and {circumflex over (δ)}.sub.N.sub.2.sup.i+1 the next synchronisation offsets estimated by these nodes, the node N.sub.1 will apply a synchronisation correction η{circumflex over (δ)}.sub.N.sub.1.sup.i+1 and the node N.sub.2 will apply a synchronisation correction η{circumflex over (δ)}.sub.N.sub.2.sup.i+1, such that the relative synchronisation deviation will be reduced by η|{circumflex over (δ)}.sub.N.sub.2.sup.i+1−{circumflex over (δ)}.sub.N.sub.1.sup.i+1|=ηΔ.sub.N.sub.1.sub., N.sub.2.sup.i where Δ.sub.N.sub.1.sub., N.sub.2.sup.i is the offset (in absolute value) between the local clocks of the nodes N.sub.1 and N.sub.2, measured during the timeslot A.sup.i.

[0057] Thus, the correction will be carried out equally between the transmission node and the reception node. The selection of η=1/2 corresponds to the case where an attempt is made to cancel in one go the offset between the two local clocks for the following timeslot. However, it may be preferred to carry out this compensation progressively, by taking a lower value of η, for example η=1/p with p>2 or also η=2.sup.−M with M≥1.

[0058] It is important to note that the synchronisation corrections are performed in a distributed manner without reference nodes. The local clocks of the various nodes synchronise progressively little by little as communications between the nodes are established. The catch-up factor η makes it possible to control the convergence speed of the synchronisation of the network, a low value of this factor in particular making it possible to prevent an unstable or oscillatory state.

[0059] In practice, each node records in a FIFO stack of size N−1 the synchronisation offsets that it has successively measured during N−1 previous communications.

[0060] Thus, still in the hypothesis where these communications took place during consecutive timeslots, the δ.sup.i−N+1, . . . , δ.sup.i−2, δ.sup.i−1 are stored in the stack. These values as well as the value measured during the current chunk, A.sup.i serve to estimate the synchronisation offset during the following chunk A.sup.i+1 and, as already described, to carry out a synchronisation correction of η{circumflex over (δ)}.sup.i+1 the local clock. The current value measured, η.sup.i, is then stored in the stack and the oldest value δ.sup.i−N+1 is unstacked.

[0061] Generally, when the communications of the node took place during the access slots, where A.sup.i−k.sup.N−1, . . . , A.sup.i−k.sup.2, A.sup.i−k.sup.1 where i−k.sub.N, . . . , i−k.sub.2, i−k.sub.1 are the indexes of N−1, last access slots during which the node in question has transmitted or received a packet from a third-party node, the offset values δ.sup.i−k.sup.N−1, . . . , δ.sup.i−k.sup.2, δ.sup.i−k.sup.1 are stored in the stack. An estimation of the synchronisation offset during the timeslot A.sup.i+1, that is to say {circumflex over (δ)}.sup.i+1, is obtained from offset values stored in the stack and the one measured during the current timeslot. The offset correction is performed before the start of the chunk A.sup.i+1. Alternatively, the correction may be performed later, but however before the next communication of the node.

[0062] Advantageously, in addition to the synchronisation offset values, the node may also store the indexes of the timeslots during which they were measured. Indeed, in the forecast {circumflex over (δ)}.sup.i+1, it is understood that an offset measurement is all the less taken into account if it is older.

[0063] Generally, various forecasting methods may be used to forecast δ.sup.i+1. In particular, an autoregressive forecasting model, a Bayesian filtering in a manner known by the person skilled in the art may be used. Other forecasting models may be considered without departing from the scope of the present invention.

[0064] According to an important alternative embodiment, the synchronisation correction is only applied insofar as this correction is lower in absolute value than a predetermined threshold, i.e. η|{circumflex over (δ)}.sup.i+1|<δ.sub.max. Failing this, it will be concluded a default case. Such a default case may in particular occur when a node of the network is subjected to a timeslot template attack or that its clock is deficient. In the case of a WSN network using an access control according to the TDSCH mode, it will advantageously be selected δ1/2min(|PGT|, |AGT|).sub.max where |PGT|, |AGT| are the respective durations of the guard times PGT and AGT. Thus, it is ensured that the guard times during a possible communication between the same nodes during the timeslot A.sup.i+1 are in fact respected.

[0065] According to another variant, the synchronisation offset δ.sup.i, measured during a timeslot, A.sup.i, is compared with the forecast value {circumflex over (δ)}.sup.i. If the difference between the measured value and the forecast value exceeds a certain threshold, i.e. |δ.sup.i−{circumflex over (δ)}.sup.i|>ε, the parameters of the forecasting model may be updated (in other words the model may be adaptive).

[0066] In the embodiments previously described, we have assumed that all of the synchronisation offsets measured by a node in communication were stored in the same stack, independently of the node with which it is in communication. According to one variant, the offset values measured may be labelled by the identifiers of the nodes with which the communication was established. More specifically, if the node N.sub.1 is considered and its neighbour nodes are noted N.sub.i.sup.j, j=1, . . . , J, the node N.sub.1 may manage up to J distinct stacks, each stack j=1, . . . , J being dedicated to the storage of synchronisation offsets, δ.sup.i−k.sup.j.sup.N−1, . . . , δ.sup.i−k.sup.j.sup.2, δ.sup.i−k.sup.j.sup.1 of the local clock of the node N.sub.1 in relation to the clock of the node N.sub.1.sup.j. It is understood that the correction applied to the local clock, will then depend on the node with which the communication will be established.

[0067] Regardless of the variant considered, the catch-up factor may be determined by means of a multi-agent reinforcement learning (MARL) method. It is reminded that a reinforcement learning method is an automatic learning method wherein an autonomous agent, immersed in an environment, learns actions to carry out from experiences, so as to optimise a reward accumulated over time. The agent makes decisions depending on its current state and the environment provides it with rewards depending on the actions that it carries out. When the learning method is furthermore of the multi-agent type, each node plays the role of an agent and learns from its environment, in this case the network, the various agents operating in a cooperative manner.

[0068] More specifically, during a timeslot, A.sup.i, each node in communication is in a state S.sub.i (offset of its local clock in relation to a reference time). It carries out an estimation of the synchronisation offset and estimates the correction, η.sub.k{circumflex over (δ)}.sup.i+1, to be applied during the following access slot where η.sub.k belongs to a predetermined set of catch-up factor values. Following an action, in this case following the application of the correction of the local clock by the node, its environment (the network), returns to it a new state (corresponding to a new offset of the local clock) as well as a reward (positive or negative) that is shared by all of the nodes of the network. Thus, each node independently learns the catch-up factor that it must apply to maximise the mathematical expectation of the sum of future rewards, weighted by their respective discount factors. A description of reinforcement learning methods may be found in the work of Richard S. Sutton and Andrew G. Barto entitled “Reinforcement learning”, 2.sup.nd edition, 2018, pp. 129-132.

[0069] FIG. 5 shows a flowchart of the method for synchronising a node in a deterministic mesh network, according to one embodiment of the invention.

[0070] The synchronisation method is based on a periodic process, repeating at each timeslot.

[0071] Consequently, we will consider the access slot, A.sup.i.

[0072] In step 510, the node determines if it is programmed to transmit a packet to a neighbour node or to receive a packet from a neighbour node during the timeslot, A.sup.i, from the scheduling matrix.

[0073] If this is not the case, the node waits for the next timeslot, A.sup.i+1.

[0074] On the other hand, if a communication is established in transmission or in reception with a neighbour node during the timeslot, A.sup.i, the node measures in 520 the synchronisation offset, δ.sup.i, of the local clock with the neighbour node from the detection of an event. When the node is receiver, the measurement of the offset, δ.sub.1.sup.i, is obtained by detection of the time at which it receives the packet from the neighbour node and more specifically its start frame delimiter, SFD. On the other hand, when the node is transmitter, the measurement of the offset δ.sub.2.sup.i is obtained by detection of the reception time of the acknowledgement of the packet in question.

[0075] When the receipt of the packet (respectively of the acknowledgement) occurs outside of an authorised guard time (PGT for the packet, AGT for the acknowledgement in the case of a TSCH access mode), the synchronisation offset is not taken into account for the correction (step not shown). In an equivalent manner, when the synchronisation offset is greater than a (first) predetermined threshold value, it is not taken into account for the synchronisation correction.

[0076] In step 530, the node estimates, from at least one synchronisation offset measurement the, future synchronisation offset, δ.sup.i+1, of its local clock for the following timeslot, A.sup.i+1.

[0077] Preferably, this estimation, {circumflex over (δ)}.sup.i+1, is performed from a plurality of previous synchronisation offset measurements, δ.sup.i−k.sup.N−1, . . . , δ.sup.i−k.sup.2, δ.sup.i−k.sup.1, obtained during timeslots A.sup.i−k.sup.N−1, . . . , A.sup.i−k.sup.2, A.sup.i−k.sup.1, as well as of the synchronisation offset measurement, δ.sup.i relating to the current timeslot, A.sup.i.

[0078] The estimation, {circumflex over (δ)}.sup.i+1, may be obtained for example by means of a linear regression.

[0079] In step 540, the node calculates a correction of its local clock, that is to say advances or delays (according to the sign of {circumflex over (δ)}.sup.i+1) its local clock by a time η|{circumflex over (δ)}.sup.i+1|, with 0<η≤1/2.

[0080] In optional step 550, it is determined if the correction is below a second threshold value, i.e. η|{circumflex over (δ)}.sup.i+1|≤δ.sub.max. If this is the case, we can continue to step 560.

[0081] Otherwise, the node notes a case of synchronisation fault in 555 and may for example adapt the parameters of its autoregressive model.

[0082] In step 560, the node corrects its local clock by the amount of the correction. More specifically, if {circumflex over (δ)}.sup.i+1 is positive, that is to say if the reception time measured with the local clock arrived later than expected, the clock is advanced and vice versa if {circumflex over (δ)}.sup.i+1is negative, that is to say if the reception time measured with the local clock arrived earlier than expected, the local clock is delayed by η|{circumflex over (δ)}.sup.i+1|.

[0083] This correction occurs before the start of the following access slot, A.sup.i+1, and, in any case, before any new communication of the node programmed in the scheduling matrix.

[0084] The process continues with the new access slot, A.sup.i+1.