Oana Hotescu
email: oana.hotescu@enseeiht.fr

Katia Jaffrès-Runser

Adrien Van

Den Bossche

Thierry Val
email: thierry.val@irit.fr

Synchronizing Tiny Sensors with SISP: A Convergence Study

Keywords: Networks → Protocol testing and verification, Sensor networks, Network performance analysis, Wireless Sensor Network, Synchronization, Convergence analysis

The SImple Synchronization Protocol (SISP) has been designed for tiny sensors to offer a wireless synchronization service to the network. SISP is completely distributed with a flat architecture. Nodes broadcast a SYNC message periodically that contains the value of their view of a shared clock counter. Every time a SYNC message is received, nodes update their shared clock by averaging it with the clock value embedded in the message. This protocol converges in practice very well, and requires a small amount of energy as SYNC messages can be sent every second only. Moreover, computations are basic, perfectly fitting the tiny sensor platforms needed for the Internet of Things. Its distributed operations enable the network to adjust seamlessly to the appearance or disappearance of other nodes. This paper concentrates on the convergence analysis of this promising protocol. Convergence time and synchronization accuracy are determined analytically, by simulations and by experimenting a real sensor platform. All results show that this protocol offers an accuracy in the order of a few tens of microseconds. Moreover, our analytical derivations capture very well an upper bound on the synchronization accuracy.

INTRODUCTION

The Internet of Things (IoT) is foreseen to be central to future communication technologies. In the next decade, not only humans will exchange information, but machines and objects of different sorts as well. Objects of all kinds, connected wirelessly using various technologies (WiFi, 5G, Ultra Wide Band, LoRa, etc. ) will carry data over short or long distances. Different services are envisioned where this data plays a very important role, which may strongly impact the performance of a much larger cyber-physical system. https://doi.org/10.1145/3127540.3127564

For instance, industry will evolve to a new generation of factories where all processes and humans are monitored to measure the production efficiency, but as well to extract information and metrics that can be leveraged to further improve operations in real-time. Such data can as well warrant the quality of the products by completely tracing the history of all goods and processes.

In such a context, objects (sensors, actuators, robots, smartphones, ...) will coexist in the factory and mostly communicate wirelessly. The density of these systems calls for advanced communication techniques that seamlessly scale. Objects enter or leave the system in an autonomous fashion in this case. As such, network operations have to be designed in a completely distributed manner.

For these objects to efficiently communicate in such a dense context, wireless channel has to be divided among communicating nodes using time or frequency division medium access (or both). Current industry-oriented wireless solutions such as WirelessHart [START_REF]WirelessHART Specification 75, TDMA Data-Link Layer[END_REF] or the TSCH mode of IEEE803.15.4e [START_REF][END_REF] define an FTDMA medium access layer. This layer offers 10 millisecond time slots to emit a 127 byte frame at 250 kbits/s and receive its acknowledgement. It has been highlighted in [START_REF] Wang | Fraboul TDMA versus CSMA/CA for wireless multi-hop communications: a stochastic worst-case delay analysis[END_REF] that this slot duration is too large and detrimental to overall communication performance. Reducing this duration is only possible if a scalable synchronization protocol can be leveraged to finely synchronize these resource-limited objects.

Synchronizing nodes over a network is not a new problem and lots of solutions exist in the literature. The closest works to this study are related to the synchronization of wireless sensor networks. Representative protocols are RBS [START_REF] Elson | Fine-grained Network Time Synchronization Using Reference Broadcasts[END_REF], TPSN [START_REF] Ganeriwal | Timing-sync Protocol for Sensor Networks SenSys'03[END_REF], FTSP [START_REF] Maróti | The Flooding Time Synchronization Protocol SenSys '04[END_REF], PulseSync [START_REF] Lenzen | PulseSync: an efficient and scalable clock synchronization protocol[END_REF], SHARP [START_REF] Gonzalez | The Sticking Heartbeat Aperture Resynchronization Protocol[END_REF] and SISP [START_REF] Van Den Bossche | SISP: a lightweight Synchronization Protocol for Wireless Sensor Networks[END_REF]. Our aim is to leverage a protocol that provides a seamless synchronization over tiny lowcomplexity platforms. RBS and TPSN have been created to synchronize a relatively small set of nodes and thus they don't scale well. FTSP and PulseSync, on the contrary, have been designed to flood beacons to rapidly transfer time information to remote sensors. Both algorithms achieve a synchronization accuracy of a few tens of microseconds. FTSP offers a maximum accuracy of 80µs, and PulseSync a maximum accuracy of 38µs for a line topology of 20 nodes. Both approaches synchronize the network to the time of a selected root node. If this root node dies, another node has to be elected and its time spread in the network, creating a possible cut of synchronization service.

This paper focuses on a different solution that floods beacons as well in the network. These beacons are not forwarded in a multihop fashion, but are beamed and exploited by the nodes to agree on a common notion of time called the shared clock. Since this shared clock results from the common decision of all nodes, the departure of one node has little impact on the shared clock value. There is no central entity. This solution is called SISP which stands for SImple Synchronization Protocol [START_REF] Van Den Bossche | SISP: a lightweight Synchronization Protocol for Wireless Sensor Networks[END_REF].

SISP is completely distributed with a flat architecture. Nodes broadcast a SYNC message periodically that contains the value of their view of a shared clock counter. Every time a SYNC message is received, nodes update their shared clock by averaging it with the clock value embedded in the message. This protocol converges in practice very well, and requires a small amount of energy as SYNC messages can be sent every second only. Moreover, computations are basic, perfectly fitting the tiny sensor platforms needed for the Internet of Things. Its distributed agreement on a common clock enables the network to adjust seamlessly to the appearance or disappearance of other nodes.

SISP has been evaluated experimentally in the past [START_REF] Van Den Bossche | SISP: a lightweight Synchronization Protocol for Wireless Sensor Networks[END_REF], [START_REF] Gonzalez | The Sticking Heartbeat Aperture Resynchronization Protocol[END_REF]. It has been shown in [START_REF] Gonzalez | The Sticking Heartbeat Aperture Resynchronization Protocol[END_REF] that it clearly outperforms RBS on an Arduino Fio embedded platform running a 8MHz micro-controller. RBS reaches only an accuracy of 1509 µs in average while SISP offers a 112µs accuracy for a 2-node topology (beacons are emitted every 500ms in both protocols). So far, there is no thorough quantification of the SISP convergence properties. The goal of this paper is to fill this gap and exhibit the short convergence of this promising protocol to a stable synchronization with low error. Convergence time and synchronization accuracy are determined analytically, by simulations and though experimentations. All results show that this protocol offers a maximum accuracy in the order of a few tens of microseconds on the investigated hardware. Moreover, our analytical derivations capture very well an upper bound on the synchronization accuracy.

The paper is organized as follows. Section 2 introduces SISP and the model we will leverage for its analysis. The following three sections analyze its convergence properties using three different means: simulations in Section 3, theoretic analysis in Section 4 and experiments in Section 5. Finally, Section 6 concludes this work and draws the main lines of future works.

PROTOCOL AND MODEL 2.1 SISP protocol

SISP is a SImple Synchronization Protocol designed for lightweight wireless sensors [START_REF] Van Den Bossche | SISP: a lightweight Synchronization Protocol for Wireless Sensor Networks[END_REF]. SISP is completely distributed, and there is no hierarchy among nodes. Through the exchange of periodic SYNC messages, all nodes adopt a global time reference with a precision of a few tens of microseconds. This global time reference is not the absolute universal time but a time that all nodes agree to follow together. Algorithm 1 presents the actions performed by the sisp() function that is called periodically by each node of the network.

SISP defines two integer counters per node: the local clock LCLK and the shared clock SCLK. At onset, both counters are set to zero. Both clocks are incremented by one unit every time the sisp() procedure is called. Every P procedure call, a node broadcasts a SYNC message that conveys the SCKL value the sender node measures at emission time. For all other calls, she listens to SYNC messages sent by neighbours. If a SYNC message is received, she reads the embedded clock value, RCLK, and updates her shared clock following:

SCLK = ⌊ RCLK + SCLK 2 ⌋ (1)
This operation averages both clock values and rounds up the result to the closest inferior integer with ⌊ ⌋ operators. SISP is a perfect fit for tiny microprocessors as it requires only one addition plus one division by 2 (i.e. 1 bit right shift). SYNC frames are not acknowledged, only nodes receiving the frame update their SCLK counter. SISP can be implemented over any type of medium access protocol that offers broadcast communication service. However, its accuracy and convergence duration will be impacted by the number of SYNC messages that collide. Future works will study the impact of SYNC message losses on SISP accuracy and convergence duration. In the following, all derivations, simulations and experiments are made for the ideal case where no SYNC frame collision occurs.

SISP is illustrated in Figure 2 with a sample execution carried out over a 2-node topology. Node N 0 begins her emissions before node N 1 by sending SYNC frames every 100 sisp() procedure calls. The first three SYNC emissions have no effect on the network since there is no active node. Once N 1 is turned on, she initialises her SCLK counter to 0. After 20 calls, N 1 receives the SYNC frame of N 0 and offsets its SCLK according to Eq. ( 1). When the LCLK counter of N 1 reaches 100, N 1 sends a new SYNC message that causes a change in the SCLK value of N 0. The execution continues this way, which leads to the gradual convergence of the shared clocks of both nodes after a couple of SYNC broadcasts. The remainder of this paper concentrates on the convergence study of this protocol for simple topologies.

SISP model

In this paper, we adopt the following model to capture the core elements of SISP for a network composed of N nodes. Each node Ni, i ∈ {0, .., N }, has a local hardware clock denoted LCLK N i and a view of the shared clock denoted SCLK N i . Throughout this study we adopt the notations of Table 1.

The reference clock for all derivations is chosen as the one of node N 0, naming LCLK N 0 . The local clocks of all other nodes are modeled as linear functions of this reference clock:

LCLK N i = α N i * LCLK N 0 + β N i (2)
where α N i and β N i are respectively the drift and offset of the local clock of Ni with respect to the one of N 0. Offset and drift can take

α N i Node N i clock drift LCLK N i Node N i local clock SCLK N i Node N i shared clock t k
A discrete clock that moves one step forward every time a SYNC message is emitted by a node of the network. Integer k counts the number of SYNC messages emitted since the beginning of the synchronization.

D N i k Duration in seconds that separates t k and t k-1 on node N i d N i N j (t k )
Difference between the shared clocks of node N i and node N j at t k P SYNC message period in clock tops a Synchronization accuracy t a Convergence duration positive or negative values. A positive (resp. negative) drift implies that Ni runs faster (resp. slower) than N 0. If α N i equals one, both clocks run at the same speed. In this case, synchronization is simpler as only offset has to be compensated for by the protocol. Of course, this model is a simplification of reality: drift can change over time because of the variations of the oscillators frequencies of N 0 and N 1 with heat, load, etc. The impact of real variations on SISP synchronization will be observed in our experimental study.

The linear model will be leveraged in the simulation and analytic studies.

SISP convergence

This paper aims at measuring and calculating a bound on the convergence time and synchronization accuracy of SISP.

Convergence time. In this protocol, the first SYNC messages mostly compensate for the clock offsets of all nodes. The shared clocks of all nodes converge to a value close to the average of their offsets

β avд = 1/N ∑ i=N -1 i=0 β N i .
The time needed for the shared clocks to reach this average offset β avд is defined here as the convergence time of SISP. It is denoted by t a and expressed in seconds.

Synchronization accuracy.

Once the shared clocks of all nodes have reached this average offset, all subsequent SYNC emissions permit to combat the drifts by resetting the shared clock periodically. The difference between the shared clocks of two nodes depends on their relative drift and the synchronization period P. For a given P value, the larger the drift between two nodes, the faster their shared clocks diverge before a new SYNC resets their values. The accuracy a of SISP for a set of N nodes is defined as the maximum shared clock deviation existing in the network once convergence has occurred. Each pair of node may experience a different shared clock difference. As such, the accuracy a can be formulated as the maximum shared clock difference over all pairs of nodes:

a = max (i, j ) d N i N j (3)
Convergence time and accuracy will be investigated using (i) simulations, (ii) analysis and (iii) measurements. For the analysis, we will look for an upper bound on accuracy.

Investigated topologies

Three elementary topologies are investigated in this work that are representative of small deployments:

• the 2-node topology, where two nodes are in direct view.

• the 3-node ring topology, where each sensor can communicate with the two other ones. They create a clique. • the 3-node in line topology, where nodes are aligned but only the central node can communicate with the two other nodes. Border nodes can not communicate with each other.

All studies have been made by accounting for the technical features of a real sensor platform: the DecaWino sensor [START_REF] Van Den Bossche | DecaWiNo ressources[END_REF]. It is an open-source hardware design equipped with the transceiver DWM1000 and an Arduino board, the Teensy 3.2 with ARM Cortex M4 32-bit MCU rated at 64GHz, 64kB RAM and 256kB program memory. The hardware clock of this microprocessor drifts of around 20 ppm (parts per millions). It means that after one million seconds, the oscillator exhibits a deviation of +/-20 seconds. Our measurements have been made with this sensor platform.

Next and unless specified otherwise, a SYNC message is emitted by a node every second. The sisp() procedure is called every microsecond. This setting, for a clock drift of 20 ppm, should limit the time deviation to +/-20 microseconds.

SIMULATION STUDY

Convergence and synchronization accuracy have been investigated first by simulation. An in-house simulator has been designed in Java for this purpose following the SISP and network model introduced earlier. Results for the three topologies of interest are given next. For each of them, convergence and accuracy are given when the drift of all nodes equals 0 ppm or 20 ppm. For 0 ppm, we set all nodes to α N i = 1 and for 20 ppm, we set them to α N i = 0, 100020.

2-node topology

Figure 3 plots the difference of the SCLK counters of both nodes over time. If this difference is zero, both nodes have adopted the same shared clock and are thus perfectly synchronized. The x-axis represents the local clock of N 0, which represents our reference clock.

Figure 3-(top) gives the shared clock difference when there is no clock drift. Before 10 seconds, the difference of shared clocks is decreasing to compensate for the offset difference of both nodes. After 10 seconds, since no drift exists, clocks stay in tune. For the 20ppm case, represented on Figure 3-(bottom), a similar decay of the SCKL difference is observed, but after 9 seconds, the difference oscillates around a value of 10µs. The accuracy is here of 11µs, given by the maximum shared clock difference. This observation is in line with a SYNC period of 1s. and a 20ppm oscillator.

On Figure 4, we investigate the influence of P on the shared clock difference observed at convergence for different values of clock drift. This figure has been obtained for an oscillator frequency of 1MHz. The x-axis represents the clock drift varying from 0 to 50 ppm while the y-axis represents the period P of SYNC messages in seconds. For instance, for a drift of 20 ppm, the lowest shared clock difference that can be seen here is between 10 and 20µs. This is possible for a SYNC period of 1s. A SYNC period of 3s. offers an accuracy between 30 and 40µs. The general message is that to obtain a better accuracy, shorter SYNC periods have to be chosen.

3-node topologies

When the drift equals 0ppm for all three nodes, all pairs converge to a difference of shared clocks equal to zero. This result isn't plotted as it will be demonstrated analytically in Section 4. Simulation results for the case where the drifts are non-null are given next.

Figure 5 represents the shared clock difference for a 3-node ring topology, where the local clock of node N 0 is given as the reference clock. The drift of N 1 is set to 10ppm and the one of N 2 to 20ppm. On Figure 5, the three curves represent the shared clock difference observed for the three pairs of nodes. At convergence, the largest difference is observed between nodes N 0 and N 2. The shared clock difference is the same between the other 2 pair of nodes, which is correct as they have both a relative drift of 10ppm. As such, the overall synchronization accuracy is given by the pair of nodes experiencing the largest relative drift.

In Figure 6, the pairwise shared clock differences for the 3-node line topology is given. As for the 3-node ring topology, the local clock of N 0 is the reference clock and the drifts are equal to 10ppm for N 1 and 20ppm for N 2. The three differences are periodic as observed for the ring topology, but the convergence duration is twice as long as for the ring topology. This can be easily understood as direct communications between border nodes are impossible: clock updates need two beacons to be accounted for by all nodes. Again, the pair of nodes that experiences the largest relative drift (naming N 2 and N 0) is the one showing the largest shared clock difference.

Simulation results summary

Table 2 shows for each topology the synchronization accuracy and the convergence time observed by simulations. Not surprisingly, it is the 3-node ring topology that offers the shortest convergence time, as 2 nodes can update their shared clock at each SYNC message emission. The longest convergence is observed for the 3-node line topology, as updates have to be 'relayed' by the central node. For the no-drift cases, perfect synchronization is achieved and accuracy is 0. For the 20 ppm drift, an oscillatory behavior is observed after convergence whose maximum value, given by the accuracy, is bounded. Bounds are in the order of a few tens of microseconds, which is in-line with the setting of a one second SYNC emission. In the following, convergence time and synchronization accuracy are investigated analytically.

ANALYTIC STUDY

In this section, we conduct an analysis of the convergence of SISP synchronization protocol and we provide a bound on the synchronization accuracy and the minimal number of messages needed to achieve the synchronization state. We begin by describing the methods used to prove the protocol convergence, then we summarize the main results obtained for the considered topologies. A detailed proof for the 2-node topology is given, together with the main proof elements of the 3-node topologies.

Methodology

Expressions for the convergence time and an upper bound on the synchronization accuracy are derived here for each topology. We study the case where clocks don't drift away (i.e. α N i = 1) and the one where a known drift of α N i 1 is experienced by the nodes. Derivations are made in the latter case for non-homogeneous offsets and drifts as given in the model of Eq.( 2). Moreover, offsets and drifts are not a function of time, and thus are assumed to be constant. Propagation delays are neglegted. Synchronization accuracy is proved by deriving the difference of shared clock values, denoted d N i N j (t k ) and by expressing it as a sequence of real values indexed by t k . We prove that this difference is a decreasing sequence and that its limit is its infimum using the following Lemma: Lemma 4.1. If a sequence of real numbers is decreasing and bounded below, then its infimum is the limit.

Results summary

Bounds obtained analytically are summarized in Table 3. We define D = P 1+α N 1 as the average value of D and σ =

√ 1 N * ∑ N k =1 (D N 0 k -D)
2 its standard deviation. Function LCM (x, y) extracts the least common multiple of x and y, with x > 0 and y > 0.

Synchronization accuracy is proved to be 0 if α i = 0, ∀i ∈ {0, .., N -1}. For the 2-node α N i 1 scenario, we provide an upper bound on the accuracy that is tight. For the 3-node ring and line topologies, we haven't succeeded in deriving analytic bounds for the α N i 1 case so far. However, for the 3-node topologies SISP converges to a perfect synchronization if α i = 0 for all nodes. Thus, we argue that if it is possible to learn and compensate for these drifts over time with an improved version of SISP, we can prove the convergence of this new protocol as it becomes equivalent to the no-drift case. Future works will concentrate on the design of this drift-aware

log 2 |β N 1 | -1 α N i = 1 2-node (1 -α N 1 ) * ( D + σ ) + 4 3 max(T N 0N 1 , log 2 |β N 1 | -1) with T N 0N 1 = LCM (P, P * α N 1 )/α N 1 α N i 1 3-node ring 0 log 2 (max i |β N i |) -1 α N i = 1 3-node ring - max [ LCM (T N 0N 1 ,T N 0N 2 ), log 2 (max i |β N i |) -1 ] α N i 1 3-node line 0 log 2 (max i |β N i |) -1 α N i = 1 3-node line - max [ LCM (T N 0N 1 ,T N 0N 2 ), log 2 (max i |β N i |) -1 ] α N i 1
SISP protocol. Next, a detailed proof for the 2-node topology convergence time and accuracy is given.

2-node topology

We illustrate this proof with the sequence of SISP protocol messages given in Figure 7. Assuming the nodes begin sending messages at time t 0 , the shared clock values at t 0 for the two nodes can be calculated for the reference clock LCLK N 0 . By recurrence, the shared clock expression at time t k can be deducted from the shared clock expression at t k -1 . Following, the SCLK difference is extracted and interpreted as a sequence. We prove by recurrence that this SCLK difference is a decreasing sequence and deduce its limit. Lemma 4.1 is then leveraged to prove protocol convergence. Local clocks of the two nodes run at the same speed. Thus, the duration D N 1 k elapsed between the two shared clock updates on node N 1 is the same as D N 0 k on node N 0.

Synchronization accuracy. The shared clocks values of both nodes are given in Eq. ( 4) if the first SYNC message is sent by N 0 and in Eq. ( 5) if it is sent by N 1:

SCLK N 0 (t k ) = SCLK N 0 (t k -1 ) + D N 0 k SCLK N 1 (t k ) = 1 2 * [ SCLK N 0 (t k-1 ) + SCLK N 1 (t k -1 ) + 2 * D N 0 k ] ( 4
)
SCLK N 1 (t k ) = SCLK N 1 (t k -1 ) + D N 1 k SCLK N 0 (t k ) = 1 2 * [ SCLK N 0 (t k-1 ) + SCLK N 1 (t k -1 ) + 2 * D N 0 k ] (5)
We are interested in identifying the time t k where the shared clock values of the two nodes are equal; in this case, the difference between the two shared clocks is 0. We denote this difference

d N 0N 1 (t k ) = SCLK N 0 (t k )-SCLK N 1 (t k ).
Since only two nodes are considered in this topology, we will drop the index N 0N 1 to simplify notations in all derivations related to the 2-nodes scenario. We substitute in this formulae the equations of shared clocks given in Eq. ( 4) or in Eq. ( 5). For both cases, we obtain after substitution:

d (t k ) = 1 2 * (SCLK N 0 (t k -1 ) -SCLK N 1 (t k -1 )) = 1 2 * d (t k -1 )
As such, the difference d (t k ) can be expressed according to the difference at t 0 :

d (t k ) = 1 2 k * d (t 0 )
The limit of this sequence is 0. It is straightforward to prove by induction that this sequence is decreasing for increasing k. From Lemma 4.1, we can state that the shared clock difference converges to 0. Thus, shared clock values converge to the same value and perfect synchronization is thus achieved.

Convergence time. Convergence time t a is deduced from the minimum number of messages needed to achieve convergence. It is deduced from setting 1 2 k * d (t 0 ) to 1 and solving it for k:

t a = k = log 2 d (t 0 ) = log 2 |β N 1 | -1 (6)
as

d (t 0 ) = β N 1 /2.

Drift case (α N 1 1).

Clock LCLK N 0 is still the reference clock, and the local clock of N 1 drifts away from LCLK N 0 with rate α N 1 1. As such,

D N 1 k = α N 1 * D N 0 k . Convergence time.
The simulation results of Section 3 show that the shared clock difference repeats itself periodically after all offsets have been compensated for. The period of the shared clock difference d is given by the least common multiple (LCM) of the SYNC message periods of both nodes: LCM (P, P * α N 1 ) (its the hyper-period of the two periodic flows emitted by N 0 and N 1). This value has to be converted to the time reference of node N 0. The period of d is denoted T N 0N 1 and given by:

T N 0N 1 = 1 α N 1 * LCM (P, P * α N 1 ) (7)
Convergence occurs if all offsets have been compensated for and one hyper-period T N 0N 1 has at least elapsed:

t a = max(T N 0N 1 , log 2 |β N 1 | -1) (8)
Synchronization accuracy. As before, we aim at calculating the shared clock difference d (t k ) to prove its convergence and calculate its accuracy. The shared clocks values of both nodes are given in Eq. ( 9) if the first SYNC message is sent by N 0 and in Eq. ( 10) if it is sent by N 1:

SCLK N 0 (t k ) = SCLK N 0 (t k-1 ) + D N 0 k SCLK N 1 (t k ) = ⌊ 1 2 * [SCLK N 0 (t k -1 ) + SCLK N 1 (t k -1 ) +(α N 1 + 1) * D N 0 k ] ⌋ (9) SCLK N 1 (t k ) = SCLK N 1 (t k -1 ) + α N 1 * D N 0 k SCLK N 0 (t k ) = ⌊ 1 2 * [SCLK N 0 (t k -1 ) + SCLK N 1 (t k-1 ) +(α N 1 + 1) * D N 0 k ] ⌋ (10)
The difference d (t k ) = SCLK N 0 (t k ) -SCLK N 1 (t k ) can be obtained by substituting SCLK N 0 (t k ) and SCLK N 1 (t k ) using ( 9) and (10), respectively. Expressions for the shared clock difference are given in (11) if the first SYNC message is sent by N 0 and (12) otherwise.

d (t k ) = D N 0 k - ⌊ 1 2 * [ -d (t k-1 ) + (α N 1 + 1) * D N 0 k ] ⌋ (11) d (t k ) = ⌊ 1 2 * [ d (t k -1 ) + (α N 1 + 1) * D N 0 k ] ⌋ -α N 1 * D N 0 k (12)
Using the properties of the integer part it is possible to bound the shared clock difference as shown in inequalities (13) and ( 14).

1 2 * [ d (t k-1 ) + (1 -α N 1 ) * D N 0 k ] < d (t k ) < 1 2 * [ d (t k -1 ) + (1 -α N 1 ) * D N 0 k ] + 1 (13) 1 2 * [ d (t k -1 ) + (1 -α N 1 ) * D N 0 k ] -1 < d (t k ) < 1 2 * [ d (t k-1 ) + (1 -α N 1 ) * D N 0 k ] (14)
By recurrence, the difference at t k can be expressed according to the difference at t 0 as in the inequalities (15) and (16).

A - 2 3 < d (t k ) < A + 4 3 (15) A - 4 3 < d (t k ) < A + 2 3 (16)
where :

A = 1 2 k * [ d (t 0 ) + (1 -α N 1 ) * (D N 0 1 + 2 * D N 0 2 + ... + 2 k -1 * D N 0 k ) ] .
Accuracy upper bound. We recall that D N 0 k represents the difference between emission and reception dates of a SYNC message at N 0. We can assume that in average, it is close to P/2, with P the SYNC emission period of SISP. To obtain an estimate of A, and thus an estimate of the bounds on d (t k ), we assume D N 0 k is normally distributed: 50% of its values are less than P/2 and 50% of the values are greater than P/2. The mean of this distribution is equal to D = P/(1 + α N 1 ) and the standard deviation to σ = √ 2 . With this assumption, we can substitute the durations D N 0 k by the mean duration D and the standard deviation σ in A. As such, we obtain an approximated value of A :

1 k * ∑ k i=1 (D N 0 i -D)
à = 1 2 k * [ d (t 0 ) + (1 -α N 1 )(2 k -1)( D + σ ) ]
Calculating the limit of à as k grows to infinity, we get:

Ã∞ = lim k →∞ à = (1 -α N 1 )( D + σ )
Since we may not know which node has started to emit SYNC messages first, we extract from Eq. ( 15) and ( 16) an upper bound on d (t k ) which is given by

d (t k ) < ̰ + 4/3 (17)
The average value of d (t k ) can as well be computed by setting σ to zero in Ã∞ . This average value derivation only depends from system parameters and can be computed without any precise information on the protocol execution. To get a more precise estimation of the accuracy, a few values of D N 0 k are required to calculate the standard deviation σ . These values can be either obtained by the first steps of a simulation or by measurements of the SYNC message emission and reception dates.

Figure 8 illustrates, on top of the simulated shared clock difference of Figure 3, our average and upper bound on d (t k ). The average calculation already provides a meaningful order of magnitude of the accuracy. A more precise estimation, using the upper bound of Eq.( 17), is plotted as well. In this example the upper bound on the synchronization accuracy is less than 10µs. This section concentrates on the 3-node topology for the case where no drift exists between the nodes. Derivations are similar to the ones presented earlier for the 2-node topology. Thus, only basic explanations are provided in the following.

3-node topology

Synchronization accuracy. As for the 2-node topology, the difference of SCLK values is computed for each couple of nodes. The protocol is convergent if the three differences converge. By induction we can prove that the sequences of shared clock differences for each pairs are decreasing and that we can calculate their limit which is 0. This derivation holds whether nodes are in a ring setting or in a line setting.

Convergence time. The convergence time is calculated for each pair of nodes as done for the 2-node topology by counting the minimum number of messages to achieve a difference of 1. Convergence time for the whole network is given by the maximum convergence time for the all pairs of nodes. Formally, we have:

t a = log 2 max i (d N 0N i (t 0 )) = log 2 (max i |β N i |) -1

Drift case (α N i 1).

Convergence time. As for the 2-node case, the simulation results of Section 3 show that the shared clock difference repeats itself periodically after all offsets have been compensated for. The period of the shared clock difference for the two pairs (N 0, N 1) and (N 0, N 2) are given by the least common multiple (LCM) of the SYNC message periods of both nodes:

T N 0N i = 1 α N i * LCM (P, P * α N i ), i = 1, 2 (18)
A global period can be computed from T N 0N 1 and T N 0N 2 by computing T = LCM (T N 0N 1 ,T N 0N 2 ). Convergence occurs if all offsets have been compensated for and one global hyper-period T has at least elapsed:

t a = max(T , log 2 (max i |β N i |) -1) (19)
Synchronization accuracy. As defined previously, it is given by the maximum shared clock difference observed after convergence over the three pairs of nodes. As observed in the simulations, the maximum shared clock difference is observed for the pair of nodes having the largest difference in drifts. Accounting for all drifts in an analytic derivation of the shared clock difference of all pairs is challenging for both ring and line topologies and have not been derived for this study. However, it is interesting to note that if it is possible to learn and compensate the drifts from the SYNC messages in SISP, calculating the accuracy resumes to the case where no drift exists. In this case, it is possible to prove the convergence and offer a theoretical accuracy of 0. Future works will concentrate on deriving a novel version of SISP that mitigates clock drifts by prediction as proposed in [START_REF] Lenzen | PulseSync: an efficient and scalable clock synchronization protocol[END_REF].

EMPIRICAL STUDY

In order to complete the theoretical and simulation study of the SISP protocol convergence, we have deployed SISP on the DecaW-iNo nodes introduced earlier. The implemented protocol uses the same configuration as the one deployed in simulation. The SYNC message period is equal to 1s.

Figure 9 shows the shared clock difference d (t k ) measured for a 2-node topology. The x-axis shows the reference clock LCLK N 0 and the y-axis the shared clock difference. From this curve, it can be seen that convergence occurs at 13 seconds and that the synchronization accuracy is then around 10 microseconds. The analytic upper bound on the accuracy is plotted in red as well. This bound accounts for the standard deviation derived from the D N 0 k values obtained by simulation. Our bound clearly fits very well the measured values.

On Figure 10, the shared clock difference for each couple of nodes has been represented for the 3-node ring topology. The three differences have a similar evolution. They are decreasing until 15s on the reference local clock and then they present regular variations. The synchronization accuracy is of about 8 µs. Similarly, Figure 11 shows the three shared clock differences for the 3-node line topology. Convergence time is clearly longer for the line topology than for the ring topology (26s. versus 15s.). The synchronization accuracy is larger as well (32µs. versus 8µs.). Measurements are close to the values observed by simulations for 2-node and 3node ring scenarios. For the line scenario, the convergence time calculation should be improved to account for the propagation of messages. Table 4 summarized the synchronization accuracy and the convergence time observed by measurement. Theoretical values are included as well, if available. These results are similar to the simulation results of Table 2. Overall, SISP only needs a few seconds to achieve a stable state. This convergence time depends on the number of nodes and on the network topology. The synchronization accuracy is the order of a few tens of microseconds, which is in line with the protocol design goal.

CONCLUSIONS

In this paper we studied the convergence properties of SISP, a lightweight, totally distributed synchronization protocol for wireless sensor networks. Three different approaches have been presented to investigate the protocol behavior. First, simulations have helped us to establish that there is a convergence time before nodes agree on a shared clock. If the clock of nodes drifts apart, the protocol produces periodic variations of the shared clock after initial convergence. Second, we have derived analytic expressions to quantify both convergence time and synchronization accuracy. For the 2-node scenario, we even have been able to calculate a tight upper bound on the accuracy. Last, we present measurements on a real wireless sensor network which are totally in line with simulation and theoretical results.

Future works will now concentrate on extending these results to a larger number of nodes and to the case where SYNC messages collide. Another promising research is the definition of a new version of SISP that compensates for the drift of nodes by learning it over time. This will ensure proper convergence as in this case, the problem reduces to the case where no drifts exist (they are mitigated by the learning step). In other words, we will be able to easily calculate the accuracy and convergence time as the α N i values will be equal to one.

Figure 1 :

 1 Figure 1: SISP procedure: LCLK, SCLK and P are global integer variables.

Figure 2 :

 2 Figure 2: SISP sequence diagram

Figure 3 :Figure 4 :

 34 Figure 3: Difference of the shared clocks (in log scale) over time for the 2-node topology, with a 0ppm drift (top) and 20ppm (bottom)

Figure 5 :

 5 Figure 5: Difference of the shared clocks (in log scale) for a 3-node ring topology. The drift of node N 1 is 10ppm and the drift of N 2 is 20ppm.

Figure 6 :

 6 Figure 6: Difference of the shared clocks (in log scale) for a 3-node line topology. The drift of node N 1 is 10ppm and the drift of N 2 is 20ppm.

Figure 7 :

 7 Figure 7: SISP protocol execution for 2-node scenario

Figure 8 :

 8 Figure 8: Mean and upper bound estimation of the shared clock difference for the 2-node topology for a 20ppm drift.

4. 4 . 1

 41 No drift case (α N i = 1).

Figure 9 :

 9 Figure 9: Measured difference of the shared clocks (in log scale) for a 2-node topology.

Figure 10 :

 10 Figure 10: Measured difference of the shared clocks (in log scale) for a 3-node ring topology.

Figure 11 :

 11 Figure 11: Measured difference of the shared clocks (in log scale) for a 3-node line topology.

Table 1 : Table of notations Notation Definition

 1

Table 2 : Simulation study: synchronization accuracy and convergence time for all topologies.

 2

	Topology	Synchronization Convergence
		accuracy (in µs.)	time (in s.)
	2-node ; 0 ppm	0	10
	2-node ; 20 ppm	11	9
	3-node ring ; 0 ppm	0	8
	3-node ring ; 10/20 ppm	7	7.5
	3-node line ; 0 ppm	0	21
	3-node line ; 10/20 ppm	32	19.5

Table 3 : Synchronization accuracy and convergence time expressions. Synchronization accuracy for the 2-node α N i 1 case is an upper bound.

 3

	Topology	Synchronization accuracy a	Convergence time t a
	2-node	0

Table 4 : Measured synchronization accuracy and conver- gence time. Theoretical values are given in parenthesis if available.

 4

	Topology	Synchronization Convergence
		accuracy (µs)	time (s)
	2-node	10 (10)	13 (16)
	3-node ring	8	15 (19)
	3-node line	32	26 (19)

ACKNOWLEDGEMENTS

This work has been supported by Region Occitanie and European FEDER program under the MHTag GUINESS project.


Frederic Symesak

SUB HILBERT SPACES IN THE UNIT BALL OF C n

come

Sub Hilbert spaces In the unit Ball of n

Introduction

The aim of this note is to give a characterization of some reproducing kernels of spaces of holomorphic functions on the unit ball of C n . These kernels are obtained with the weighted Bergman kernel B α (z, w) and bounded holomorphic functions ϕ 1 (z), • • • , ϕ l (z).

We denote by B the unit ball of C n and by r(z) = n i=1 |z i | 2 -1 a defining function. Let α > -1 and let dV α (z) = (-r(z)) α dV (z). We denote by A 2 α the weighted Bergman space of B with respect the measure dV α (z) [START_REF] Krantz | Function theory of several complex variables[END_REF]. It is a Hilbert space and its reproducing kernel is given by B α (z, w) = c α (1 -zw) n+1+α . When α = 0, we denote by B(z, w) the usual Bergman kernel and by A 2 the Bergman space. we have Theorem 1.1. Let α > -1 and Φ(z) = (ϕ 1 (z), • • • , ϕ l (z)) be holomorphic. The kernel K α (z, w) = 1 -Φ(z)Φ(w) B α (z, w) is a reproducing kernel if and only if sup B |Φ(w)| ≤ 1.

The reproducing properties of kernels of type (1 -ϕ(z)ϕ(w))B(z, w) was studied by F. Beatrous and J. Burbea [START_REF] Beatrous | Interpolation problems for holomorphic functions[END_REF], for spaces of holomorphic functions on domains of C n and by S. Saitoh for abstract kernels of Hilbert spaces of functions [START_REF] Saitoh | Theory of reproducing kernel and its applications[END_REF]. In the case of he unit disc of C, when ϕ is finite Blaschke product, the characterization of the related Hilbert space was obtained by K. Zhu [START_REF] Zhu | Sub-Bergman Hilbert Spaces on the Unit Disk[END_REF] and [START_REF] Zhu | Sub-Bergman Hilbert Spaces on the Unit Disk II[END_REF] for Bergman space and by S. Sultanic for weighted Bergman spaces [START_REF] Sultanic | Sub-Bergman Hilbert spaces[END_REF]. The same questions was introduced by L. De Branges ang J. Rovnyak in the context of Hardy spaces [START_REF] Sarason | Sub-Hardy Hilbert spaces in the Unit Disk[END_REF]. The following theorem gives the Hilbert space associated to the kernel K α (z, w). We have

Theorem 1.2. Let α ≥ 1 and let Φ(z) = (ϕ 1 (z), • • • , ϕ l (z)) be holomorphic. The Kernel K α (z, w) is a reproducing kernel of A 2 α-1 if and only if there exists C > 0 such that 1-|Φ(z)| 2 ≤ C(-r(z)), z in B.
For -1 ≤ α < 0, we denote by B 2 α the diagonal Besov space. A holomorphic function f belongs to B 2 α if and only if (I + N )f is in A 2 α+1 , where N = n k=1 z k ∂ z k is the normal complex field [START_REF] Krantz | Function theory of several complex variables[END_REF]. We have

Theorem 1.3. Let Φ(z) = (ϕ 1 (z), • • • , ϕ l (z)) be holomorphic. If there exists C > 0 such that sup B |N ϕ i (w)| ≤ C i, 1 ≤ i ≤ l, then (1) If 0 < α < 1, K α (z, w) is a reproducing kernel of A 2 α-1 . (2) K 0 (z, w) is a reproducing kernel of the Hardy space H 2 . (3) If -1 < α < 0, K α (z, w) is a reproducing kernel of B 2 α .

Sub-Bergman spaces

Recall that the Bergman projection B α is the orthogonal projection from L 2 (dV α ) onto A 2 α . Given a bounded function ϕ the Toëplitz operator of symbol ϕ is defined by

T ϕ f = B α (ϕf ).
We consider the self-adjoint operator H given by

Definition 2.1. Let Φ(z) = (ϕ 1 (z), • • • , ϕ l (z)) be holomorphic. We set Hf = l i=1 ϕ i T ϕ i f f ∈ A 2 α .
We first estimate the norm of H. We have

Proposition 2.2. Let H as above. Then H = sup B |Φ(w)| 2 . Proof : Let f in A 2 α . Then Hf A 2 α ≤ l i=1 ϕ i B α (ϕ i f ) A 2 α ≤ sup B |Φ(w)| l i=1 B α (ϕ i f ) A 2 α . Since B α is a projection, B α (ϕ i f ) A 2 α ≤ ϕ i f A 2 α , then l i=1 B α (ϕ i f ) A 2 α ≤ sup B |Φ(w)| f A 2 α . Let f w (z) = B α (z, w) B α (w, w) , u in B. Then Hf w (z) = l i=1 ϕ i (z)ϕ i (w)f w (z) and Hf w , f w α = |Φ(w)| 2 , where •, • α is the inner product of A 2 α . The relation Hf w , f w α ≤ H f 2 A 2
α and the fact that f w A 2 α = 1 finish the proof. Proof of the theorem 1.1: Assume that sup B |Φ(w)| 2 ≤ 1. Then H is a contraction and the operator (I -H) 1/2 is well defined. It is a self-adjoint operator and it is well known that (I -H) 1/2 A 2 α is a sub-Hilbert space whose reproducing kernel is given by (I -H)B α (z, w) = K α (z, w) see [START_REF] Sarason | Sub-Hardy Hilbert spaces in the Unit Disk[END_REF], [START_REF] Zhu | Sub-Bergman Hilbert Spaces on the Unit Disk[END_REF] for details.

Assume now that K α (z, w) is a reproducing kernel, then for any finite sequences (w j ) K α (w j , w k ) is a definite positive matrix. Let w be a point in the ball, then

K α (w, w) = (1 -|Φ(w)| 2 ) B α (w, w) ≥ 0, then |Φ(w)| 2 ≤ 1.
Proof of the theorem 1.2: The proof involves the Douglas criterion [START_REF] Douglas | On majorization, factorization, and range inclusion of operators on Hilbert space[END_REF] we mention here the statement. In the definition, the relation AA * λBB * means that λBB * -AA * is a positive operator. We consider the coordinate functions Φ 0 (z) = (z 1 , • • • , z n ) and we denote by H 0 its associated operator. The kernel of the Hilbert space (I

-H 0 ) 1/2 A 2 α is given by (1 -zw) B α (z, w) = c α B α-1 (z, w). Then (I -H 0 ) 1/2 A 2 α = A 2
α-1 by the uniqueness of the reproducing kernel. If we suppose that K α (z, w) is a reproducing kernel of A 2 α-1 , from the Douglas criterion, there exists λ > 0 such that I -H

λ(I -H 0 ). Let f in A 2 α . Then (I -H)f, f α ≤ λ (I -H 0 )f, f α . Let w in B. The function f (z) = B α (z, w) gives 1 -|Φ(w)| 2 ≤ λ(-r(w)).
The sufficient conditions follows from the result :

Proposition 2.3. Let Φ(z) = (ϕ 1 (z), • • • , ϕ l (z)) be holomorphic. If 1 -|Φ(z)| 2 ≤ C(-r(z)), there exists λ > 0 such that 1 λ (I -H 0 ) I -H λ(I -H 0 ).
Proof of the proposition 2.3 : Let α ≥ 1. The right part of the "inequality" follows from two technical lemmas :

Lemma 2.4. There exists C > 0 such that for f in A 2 α , (I -H)f, f α ≤ C f 2 A 2 α+1 . Proof : Let f in A 2 α . Then (1) (I -H)f, f α = B B K α (z, w)f (w)f (z)(-r(w)) α (-r(z)) α dV (w)dV (z).
Let K(z, w) = K α (z, w)(-r(w)) 1/2+α/2 (-r(z)) 1/2+α/2 and notice by K the integral operator given by ( 2)

Kg(z) = B K(z, w)g(w)dV (w), g ∈ L 2 (B)
Assume for the moment that K is bounded in L 2 (B), the Chauchy-Schwarz inequality gives

(I -H)f, f α ≤ K(f (-r(•)) 1/2+α/2 ) L 2 (B) f A 2 α+1 ≤ C f 2 A 2 α+1
.

It remains to study the boundedness of K. This follows from the Schur criterion [START_REF] Zhu | Operator Theory in Function Spaces[END_REF]. We have only to prove that there exists

C > 0 such that K(z, w) = C |1 -zw| n+1 . Recall that, [4] prop 8.1.4., (3) |1 -Φ(z)Φ(w)| 2 (1 -|Φ(z)| 2 )(1 -|Φ(w)| 2 ) ≤ |1 -zw| 2 (-r(z))(-r(w))
.

Therefore there exists C > 0 such that 1 -Φ(z)Φ(w) ≤ C|1 -zw| then |K(z, w)| has the desired pointwise estimate. We finish the proof of the proposition with the following result :

Lemma 2.5. Let α > -1. There exists C > 0 such that 1 C f 2 A 2 α+1 ≤ (I -H 0 )f, f α ≤ C f 2 A 2 α+1 , f ∈ A 2 α . Proof : The proof is direct. Let f (z) = m a m z m . Recall that z m 2 A 2 α = c α Γ(m 1 + 1) • • • Γ(m n + 1) Γ(|m| + n + 1 + α)
,

where |m| = m 1 + • • • + m n [4]. Let us remark that (1 -zw)B α (z, w) = cB α-1 (z, w). Then (I -H 0 )f (z) = c B B α-1 (z, w)f (w)(-r(w)) α dV (w) = c m a m z m |m| + n + α . and (I -H 0 )f, f α = c m |a m | 2 Γ(m 1 + 1) • • • Γ(m n + 1) (|m| + n + α)Γ(|m| + n + 1 + α) .
Notice that

f 2 A 2 α+1 = c m |a m | 2 z m 2 A 2 α+1 = c m |a m | 2 Γ(m 1 + 1) • • • Γ(m n + 1) Γ(|m| + n + 2 + α) .
The equivalence follows from the relation Γ(z + 1) = zΓ(z).

For the left part of the "inequality" (of the proposition 2.3), we consider the auxiliary operator

H given by Hf = B α (|Φ| 2 f ), α > -1. Let us remark that H ≤ sup B |Φ(w)| 2 and Hf, f α = l i=1 ϕ i f, B α (ϕ i f ) α ≤ l i=1 ϕ i f, ϕ i f α = Hf, f α , then (4)
I -H I -H

We have the following result :

Lemma 2.6. Let H as above. There exists λ > 0 such that I -H 0 λ(I -H).

Proof :

Let us remark that 1 -|Φ(0)| 2 ≤ 2|1 -Φ(z)Φ(0)|, the relation (3) gives 1 1 -|Φ(z)| 2 ≤ 4 1 -|Φ(0)| 2 |1 -Φ(z)Φ(0)| 2 (1 -|Φ(z)| 2 )(1 -|Φ(0)| 2 ) ≤ C (-r(z))
.

Then -r(z) ≤ C(1 -|Φ(z)| 2 ) and f 2 A 2 α+1 ≤ C (I -H)f, f α .
It remains to apply the lemma 2.5 to achieve the proof.

Proof of the theorem 1.3 : The proof is similar for 0 ≤ α ≤ 1 but require a minor modification to use the Schur criterion. We recall that for u an v holomorphic functions [START_REF] Rudin | Function theory in the Unit Ball of C n[END_REF],

B u(w)v(w)(-r(w)) α dV (w) = B (N + (n + 1 + α)I)u(w)v(w)(-r(w)) α+1 dV (w) = B u(w)(N + (n + 1 + α)I)v(w)(-r(w)) α+1 dV (w), (5)
In this case the kernel of (I -H 0 ) 1/2 A 2 α is given by (1 -zw) B α (z, w) = cB α-1 (z, w) thus (I -H 0 ) 1/2 A 2 α is the weighted Bergman space A 2 α-1 when 0 < α < 1, the Hardy space H 2 for α = 0 and the Besov space B α for -1 < α < 0.

For f in A 2 α , (I -H)f (z) = B (N + (n + 1 + α)I)K α (z, w)f (w)(-r(w)) α+1 dV (w)
and the relation ( 1) becomes

(I -H)f, f α = B (N + (n + 1 + α)I)(I -H)f (z)f (z)(-r(z)) α+1 dV (z) Let K(z, w) = (-r(z)) α/2+1/2 (-r(w)) α/2+1/2 × (N + (n + 1 + α)I)(N + (n + 1 + α)I)K α (z, w)
and K be the integral operator given by (2). Then

(I -H)f, f α = B K(f (•)(-r(•)) 1/2 )(z)f (z)(-r(z)) 1/2 dV (z). K(z, w) = 1 s,t=0 (I + (n + 1)N ) s (I + (n + 1)N ) t (1 -Φ(z)Φ(w)) ×(I + (n + 1)N ) 1-s (I + (n + 1)N ) 1-t B α (z, w).
Then there exists C > 0 such that

|K(z, w)| ≤ C(-r(z)) α/2+1/2 (-r(w)) α/2+1/2 ( |1 -Φ(z)Φ(w)| |1 -zw| n+1+α+2 + i |N ϕ i (w)| + i |N ϕ i (z)| |1 -zw| n+1+α+1 + ( i |N ϕ i (z)|) ( i |N ϕ i (w)|) |1 -zw| n+1+α
) .

Recall

2 A 2 α+1.

 22 that |1 -Φ(z)Φ(w)| ≤ C|1 -zw| and sup B |N ϕ i (w)| ≤ C, then |K(z, w)| ≤ C(-r(z)) 1/2 (-r(w)) 1/2 |1 -zw| n+2 .Let us remark that (-r(z)) and (-r(w)) are bounded by a constant times |1 -zw|. Then|K(z, w)| ≤ C |1 -zw| n+1 . The operator K is bounded in L 2 (B) and the relation (1) gives (I -H)f, f α ≤ C f The lemma 2.5 gives I -H ≤ λ(I -H 0 ).The theorem 1.2 and 1.3 characterize the sub-Hilbert space (I -H) 1/2 (A α ), this space is the analogue for the unit ball of C n of the complementary space. The space (I -H) 1/2 (A α ) is also a complementary space. It is a consequence of the relation (4) and the lemma 2.6 that there exists C > 0 such that 1C (I -H 0 ) I -H I -HUnder the condition on Φ given in the theorem 1.2 and theorem 1.3, we have (I -H) 1/2 (A α ) = (I -H) 1/2 (A α ).