François Despaux

Adrien Van Den Bossche

Katia Jaffrès-Runser

Thierry Val

N-TWR: An accurate time-of-flight-based N-ary ranging protocol for Ultra-Wide band

Keywords:

In the last decade, wireless positioning systems have drawn a strong interest from a research point of view, especially for indoor environments where Global Positioning Systems (GPS) is not available. As an alternative, emerging applications relying on Ultra-Wide Band (UWB) communication technology have been proposed to offer a ranging accuracy in the order of some dozens of centimeters. Indeed, UWB radios' increased accuracy originates in the high time resolution of UWB signals that can be leveraged to measure precisely travel times of signals (e.g. Time of Flight, ToF). ToF can be easily translated to inter-node distance. In this work we propose N-TWR, a ToF-based N-ary ranging protocol created for localization using UWB. The proposed N-TWR protocol is based on the estimation of the ToF between a target node to be localized (which may be mobile or static) and a set of N anchors. It has been designed to minimize the number of messages exchanged between all nodes compared to a naive solution that exploits the state-of-the-art UWB ranging method. Validation has been made using experiments carried out in our Open Source Framework, DecaDuino, which enables fast prototyping of protocols sitting on top of UWB Physical layer. The N-ary ranging provided by N-TWR achieves the same level of accuracy as the naive protocol exploiting SDS-TWR but using four times less messages. We exhibit as well that N-TWR can be efficiently leveraged to design a simple and elegant trilateration localization algorithm.

Introduction

In the context of Wireless Sensor Networks (WSNs), and especially in the context of mobile ad hoc networks (MANET), node localization has become utterly important as more and more applications rely on node positioning services, but as well for improved context-aware network management and maintenance. As such, increasing attention has been drawn lately to wireless positioning systems in indoor environments where Global Positioning Systems (GPS) usually fails. Several dedicated wireless technologies have been proposed. A large body of works rely on the socalled RF fingerprinting technique that measures the power level received from radio frequency (RF) signals emitted by wireless access points. The accuracy achieved by these techniques is in the order of several meters using WiFi [START_REF] Jekabsons | An analysis of wi-fi based indoor positioning accuracy[END_REF] , ZigBee [START_REF] Alhmiedat | A Zigbee-based mobile tracking system through wireless sensor networks[END_REF] or even tens of meters for mobile networks [START_REF] Chen | Cellular network location estimation via RSSbased data clean enhanced scheme[END_REF] . Moreover, an extensive site survey has to be conducted to create a radio map to be exploited for localization. We refer the reader to Section 2 to get the main solutions of the literature. Such a precision is unacceptable for applications that require a precision in the order of a few tens of centimeters. We will refer to such a localization accuracy as a dozen centimeter-level accuracy. Ultra-Wide Band (UWB) communication technology combines medium to high data rate communications with positioning capabilities offering a ranging precision in the order of few centimeters in a low-power and low-cost context [START_REF] Alarifi | Ultra wideband indoor positioning technologies: analysis and recent advances[END_REF][START_REF] Djaja-Josko | A new transmission scheme for wireless synchronization and clock errors reduction in UWB positioning system[END_REF][START_REF] Mcelroy | Comparison of wireless clock synchronization algorithms for indoor location systems[END_REF] . For positioning systems employing UWB radios, time-based schemes provide very good accuracy due to the high time resolution of UWB signals. These timebased positioning systems rely on measurements of travel times of signal between nodes. The IEEE 802.15.4a-2007 amendment [7] defines a physical layer for low data rate communications combined with positioning capabilities. One of the communication signal format defined by this standard is the Impulse Radio Ultra-Wide Band (IR-UWB). Two different time-based ranging protocols are defined by the standard: Two-Way Ranging (TWR) and Symmetric Double Sided (SDS)-TWR. Both TWR and SDS-TWR share the objective to estimate the Time of Flight (ToF) between two wireless nodes. The drawback of TWR is that the non time synchronization of the internal clocks of the nodes is not compensated for, leading to inaccurate ToF estimations. SDS-TWR achieves ToF measurements by accounting the clock skews in the ToF calculation, pushing the ranging accuracy to a couple of centimeters. However, this is achieved by performing two times the TWR procedure in a symmetric manner, doubling the number of exchanged messages.

The contributions of this paper are based on our previous work [START_REF] Despaux | Accurate and platform-agnostic time-of-flight estimation in ultra-wide band[END_REF] where we have defined a novel skew-aware TWR ranging protocol that only necessitates 2 message exchanges instead of the 4 ones needed by SDS-TWR.

From this improved point-to-point ranging procedure, we develop an N-ary protocol called N-TWR that efficiently and simultaneously ranges a static or mobile target node from a set of N anchor nodes located in the environment. Anchor nodes are fixed and of course communicate with the same UWB physical layer. In other words, N-TWR measures the distances between the target and a set of N anchor nodes. Compared to a naive implementation triggering N successive pairwise SDS-TWR ranging steps, we show that N-TWR achieves the same level of accuracy with only N + 1 messages instead of 4 × N . This leads to an improved energy performance, as we will see in this paper.

Our N-ary ranging is particularly useful for applications where moving items have to be tracked precisely indoors. An example being the tracking of food items during their elaboration process in an automated factory. Another example would be the design of an underground smart parking facility.

The central contribution of this work is the definition of N-TWR, an on-demand localization protocol for sensor nodes. With this solution, a target node can initiate a localization operation by communicating with N static anchor nodes deployed in the environment. The target node locates itself knowing the distances that separates her from each anchor nodes. Distances are measured by leveraging our Skew-Aware TWR protocol [START_REF] Despaux | Accurate and platform-agnostic time-of-flight estimation in ultra-wide band[END_REF] .

The definition of N-TWR has lead us to develop the following contributions:

• The definition of the Skew-Aware TWR protocol that estimates the time of flight between two nodes with a precision of a few centimeters. This estimate is obtained by compensating for the clock skews using a reduced number of exchanged messages. Two alternative implementations are investigated for the skew estimation: ( i ) using a linear regression approach and ( ii ) using the hardware functionality of a specific UWB transceiver [START_REF] Decawave | Module[END_REF] , the DecaWave DW10 0 0.

• The design of the N-ary concurrent ranging operations required to produce the N-TWR localization result. These operations are realized using a specific TDMA protocol which facilitates the use of Skew-Aware TWR. We show that these operations lead to an accurate measurement of the distance between the N anchors and the target node. This protocol is optimal in terms of the number of exchanged messages as only N + 1 messages are needed.

• The design of the trilateration algorithm. The N ranging results are here exploited by a specific trilateration algorithm that localizes the target with an accuracy of a dozen of centimeters.

This paper is organized as follows: Section 2 presents the related works on localization using ranging protocols. The skew-aware TWR and the N-TWR protocols are presented in Section 3 , together with our specific trilateration algorithm. Section 4 presents our experimental results for the skew-aware T WR and N-T WR protocols and finally, conclusions and future works are given in Section 5 .

Related works

This section introduces first the main types of localization protocols capable of tracking a target node from a network of static anchor nodes deployed indoors. Next, the discussion focuses more specifically on solutions relying on time of flight measurement and UWB ranging.

Position estimation

Received Signal Strength (RSS)

The strength of a received signal is decreased by path loss (PL) which is proportional to the distance between emitter and receiver. As such, measuring RSS can be leveraged to estimate the distance from a target node to an anchor node. Using a basic free-space pathloss attenuation model, the RSS matches P (d) as follows:

P (d) = P 0 -10 n log 10 d d 0 ( 1
)
where n is the PL exponent, P (d) is the received power at distance d and P 0 is the received power at reference distance d 0 . By modeling both multi-path and shadowing phenomena [START_REF] Goldsmith | Wireless Communications[END_REF] , the Cramer-Rao lower bound (CRLB) [START_REF] Scharf | Geometry of the Cramer-Rao bound[END_REF] gives an estimate of the distance between the target and the anchor node. It is then possible to derive the uncertainty of the target position given by a circular shape of centre C (anchor position) and radius d . A finer position can be calculated if the RSS of several anchor nodes is measured, creating several circles on the plane whose intersection help in reducing location uncertainty. Many papers deal with RSS localization [START_REF] Ruiz | Performance comparison between simulated and real case scenario of RSSI-Based localization algorithms on a WSAN[END_REF][START_REF] Xue | Improved Wi-Fi RSSI measurement for indoor localization[END_REF] ...

Time of Arrival (TOA)

The Time of Arrival [START_REF] Gezici | A survey on wireless position estimation[END_REF] method estimates the distance between a target and anchor node for which the position is known. The distance between both nodes can be derived from the time of arrival τ and the propagation speed of the signal c . Since the distance es- timation is based on the time of arrival, a nanosecond synchronisation between target and anchor clock is mandatory as a small time measurement error triggers large distance deviations. As for RSS, the location of the target node can be determined with increased accuracy if the time of flight of several anchor nodes is computed, materialized by the intersection of circles of different centers and radii.

Time Difference of Arrival (TDOA)

Previously introduced TOA approach imposes a fine synchronisation between target and anchor node. A different approach that does not require a separate clock synchronisation between target and anchor node is known as Time Difference of Arrival (TDOA) [START_REF] Gezici | A survey on wireless position estimation[END_REF] . The TDOA technique measures the time of arrival of an RF signal from the target at several points in space given by the location of the anchors. The method compares the dates each anchor node has received the signal of the target. The traditional approach to estimating TDOA is to compute the cross-correlation of a signal arriving at two nodes. By knowing the location of each receiver (anchor), an estimate of the location of the source of the emissions can then be deduced by intersecting a set of hyperbolas. Even though there is no need for synchronisation between target and anchors, this method imposes receiver nodes to be synchronized.

Angle of Arrival (AOA)

The Angle of Arrival (AoA) [START_REF] Gezici | A survey on wireless position estimation[END_REF][START_REF] Zhou | The UWB imaging system with rotating antenna array for concealed metallic object[END_REF] technique, sometimes referred to as Direction of Arrival (DoA), locates the mobile node by determining the angle of incidence at which signals from the target arrive at the receiving node. Geometric relationships can then be used to estimate location from the intersection of two lines of bearing (LoBs) formed by a radial line to each receiving node. In a two-dimensional plane, at least two receiving nodes are required for location estimation with improved accuracy coming from at least three or more receiving nodes (triangulation).

Ranging protocols

Ranging gives an estimate of the distance between two nodes, the radius. This information can be deduced from the received power of signals emitted by anchors or by measuring the time of flight. The first option offers at best a meter-level ranging accuracy while the other one can range a node with an error of only a few centimeters. Main solutions for both strategies are presented next, with an emphasis given to time of flight-based solutions.

Ranging with Received Signal Strength Indicator (RSSI).

The first ranging systems were based on RSSI measurements as RSSI is offered by most radio platforms to the upper layers of the protocol stack. In the context of WSNs, several localization systems based on BlueTooth Low Energy (BLE) [START_REF] Gomez | Overview and evaluation of bluetooth low energy: an emerging low-power wireless technology[END_REF] have been proposed: BlueCats, BlueSense, Estimote, Gelo, GlimWorm, Kontakt, Sensorberg, among others. They all build on the initial solution proposed by Apple and known as iBeacons [START_REF]iBeacon for developers[END_REF] . They hardly provide a meter-level accuracy for ranging as BLE beacons reception power is strongly influenced by obstacles (walls, human body, etc.). A recent study [START_REF] Paek | A measurement study of BLE ibeacon and geometric adjustment scheme for indoor location-Based mobile applications[END_REF] highlights that iBeacon RSSI values vary significantly across iBeacon vendors, mobile device platforms, deployment height of the device, indoor/outdoor environmental factors, and obstacles. Another recent field study achieves a meter-level localization accuracy by combining BLE with WiFi fingerprints [START_REF] Kriz | Improving indoor localization using bluetooth low energy beacons[END_REF] .

Ranging with Time of Flight (ToF).

ToF-based protocols compute the distance by multiplying the ToF by the propagation speed. As explained before, in Time of Arrival (ToA), a node (target) sends a message to an anchor. The target node marks the emission time of this message. Once received, the anchor records the reception time and sends this information back to the target node who can estimate the ToF by subtracting both timestamps. Fig. 1 (a) pictures the ToA protocol. This simple approach requires, however, a common notion of time between nodes. In other words, a synchronisation between node's clocks is mandatory. Some researches in this direction were proposed in [START_REF] Zhu | Joint synchronization and localization using TOAs: a linearization based WLS solution[END_REF] and [START_REF] Zheng | Joint time synchronization and localization of an unknown node in wireless sensor networks[END_REF] .

The conventional two-way ranging protocol (TWR) [7] , estimates the range without a common timing reference. In this protocol ( Fig. 1 (b)), target node sends a START message recording the departure time t 1 . Once this message is received by an anchor, the anchor records the arrival time t 2 and sends the corresponding acknowledgement (ACK) back to the target, recording also its departure time t 3 . After receiving the ACK message, the target node will also record the arrival time t 4 . Due to the inability for predicting the ACK departure time (and thus the inability to embed this information in the ACK response), a second message REPLY is sent back to the target node carrying the information specifying t 2 and t 3 . With this information at the target node side, the ToF can be computed as follows:

T oF = t 4 -t 1 -(t 3 -t 2 ) 2 (2)
An improvement of TWR, named 2M-T WR (2-Messages T WR), was proposed in [START_REF] Van Den Bossche | Decaduino: an open framework for wireless time-of-flight ranging systems[END_REF] . In this protocol, depicted in Fig. 2 (a), authors make use of a functionality of the DecaWave DW10 0 0 [START_REF] Decawave | Module[END_REF] transceiver that allows to schedule the emission of a frame at a precise time with a precision of 15 picoseconds. The frame sending instant is aligned on a 8 ns timeslot, which is a limitation of the hardware. Thanks to this feature, the MAC-layer has the ability to generate a frame which includes its future departure time. Then, both t 2 and t 3 can be embedded in the ACK response, reducing then the number of messages sent since the REPLY frame is no longer needed. This solution keeps a similar and an acceptable ranging error.

One of the main sources of error in TWR protocol stems from the clock skew. Crystal oscillators used in sensor nodes do not work exactly with the same nominal frequency. As such, a small positive or negative relative offset accumulates over time. Since propagation speed is almost the speed of light, even a small offset may cause a significant error in ranging. The Symmetric Double-Sided Two Way Ranging (SDS-TWR) shown in Fig. 2 (b) was proposed in the UWB standard [7] to mitigate the impact of clock skew. By means of two subsequent TWR steps, it reduces the impact of clock skew on the ranging results. The ToF can then be computed as:

T oF = (t 4 -t 1 ) -(t 3 -t 2 ) + (t 8 -t 5 ) -(t 7 -t 6 ) 4 (3)
Unlike the T WR algorithm, SDS-T WR algorithm needs at least 4 messages to get ranging information. Besides, and in order to eliminate the effects of clock skews, it assumes that the turn-around time of sender A is the same as the turn-around time of receiver B (i.e. A = B in Fig. 2 (b)).

Subsequently, different variants of the SDS-TWR have been proposed in the literature. In [START_REF] Kim | Performance Analysis of the SDS-TWR-MA Algorithm[END_REF] , authors propose the SDS-TWR-Multiple Acknowledgement (SDS-TWR-MA) in which the anchor sends multiple ACK frames for a single START message from the target node (cf. Fig. 3 ). The basic idea behind the proposed algorithm is to use multiple acknowledgement messages (ACK+REQ) for a single ranging operation instead of iterating the whole ranging process several time to get a stabler ranging result. According to their results, their ranging algorithm reduces the number of ranging messages of 33% compared to the SDS-TWR protocol.

In [START_REF] Kwak | A new double two-way ranging algorithm for ranging system[END_REF] , authors propose Double Two-Way Ranging (D-TWR) protocol for estimating the ToF, reducing the effects of clock skews without the assumption of identical reply time between node A and B ( Fig. 4 ). Node A starts the ranging by sending a START message and, after a fixed delay τ A , a second message is sent to node B. By using a fixed time delay, the reply time of each device is no longer needed. Results show that D-TWR can reduce the number of ranging messages when compared to SDS-TWR. As far as we know, the D-TWR protocol is not implementable on today's UWB transceivers, where the emisssion time cannot be scheduled exactly at picosecond-level.

Authors in [START_REF] Lee | Symmetric double side two way ranging with unequal reply time[END_REF] , propose an SDS-TWR version which is able to reduce the ranging error when the variation of the reply time or the values of timing drift increases. Their idea is to introduce a compensation factor for a pair of two sensor nodes based on broadcasted information. During SDS-TWR operation, the reply time is sent to its next sequentially transmitting node and based on the ratio of the two different reply times, individual node will then calculate a compensation factor and use it to compensate ranging error due to the variation of the reply time.

Even though SDS-TWR clearly reduces the negative impact of clock skews, it necessitates an important number of exchanged messages, an issue that may be prohibitive for energy-constrained applications. The goal of all previously presented works is to present a ranging protocol that provides the most accurate instantaneous ranging measurement. Hence, protocols that perform better are usually exchanging more information. In this work, and contrarily to this, we leverage a ranging protocol that minimises the number of exchanged messages but that is still accounts for clock skews to preserve ranging accuracy.

In Section 3.1 , we offer a detailed description of Skew-Aware TWR, a ranging solution we have defined in our previous works [START_REF] Despaux | Accurate and platform-agnostic time-of-flight estimation in ultra-wide band[END_REF] . We show in this paper that this protocol offers an accurate ToF estimation as it compensates for the clock skews with a reduced number of message exchanges compared to regular SDS-TWR protocols. Next, we introduce the novel N-TWR localization protocol based on Skew-Aware TWR to operate concurrently N ranging operations between a target node and N anchor nodes.

N-TWR is compared by extensive measurements to solutions relying on SDS-TWR in Section 4 . Next, we present an overview of the IEEE 802.15.4a standard as it is central to our design and is the one used in our experiments.

Background: Standard 802.15.4a

The IEEE 802. 15.4a [7] is the first international standard that provides a specific physical layer capable of wireless ranging for Wireless Sensor Networks. Two formats of communication signal are proposed: Impulse Radio Ultra-Wide Band (IR-UWB) signal and the chirp spread spectrum (CSS) signal, both of them suitable for data communication as well as ranging purposes. In this work, we consider the IR signal format. The packet format proposed by the standard is shown on Fig. 5 . The packet preamble is used to synchronise entities with informing arrival of a packet. The preamble length is of 16, 64, 1024 or 4096 symbols and is adjusted to channel quality for an increased reliability. For example, a larger preamble size will help low quality receivers to gain higher SNRs while a smaller preamble size reduces the channel occupancy, leading to a more efficient energy consumption. The SFD is a short sequence with 8 or 64 symbols indicating the end of the preamble and the start of the physical layer header. It is used to establish frame timing and its detection is important for accurate time estimation.

According to the standard, a device may implement the optional ranging support by specifying a RFRAME frame as presented in Fig. 6 . The RFRAME is indicated by setting a ranging bit in the PHY header of the packet. The range between two nodes (devices) is determined typically via Time of Arrival (ToA) (see Section 2.2 ) of a RFRAME by tracking its arrival time. However, as seen in Section 2.2 , ToA requires a common timebase between both nodes. As such we exploit here TWR which is less sensitive to relative clock offsets ( Fig. 1 (b)).

Two counter values are necessary to report: the ranging counter start value, which represents the time of arrival (ToA) ( t 2 ) of the first pulse of the first symbol of the PHR, also known as RMARKER , and the ranging counter stop value representing the time when the RMARKER of the ACK packet leaves the antenna ( t 3 ). Then, the timestamp report should contain both ( t 2 ) and ( t 3 ). This timestamping requires a very high precision timer, typically more precise than 100 ps, which is available on today's UWB transceivers such as the DecaWave DW10 0 0 [START_REF] Decawave | Module[END_REF] . On this transceiver, the resolution of the high precision timer is 15.625 ps (64 GHz), which theoretically enables a precision of 4.69 mm on ranging operations.

A note on UWB transceiver selection.

To evaluate the performance of our solution, we will conduct an extensive experiment campaign. This experimental validation ensures that (i ) the operations are feasible on a lightweight sensor, (ii ) the obtained accuracy accounts for a realistic setting.

The range of UWB hardware currently available is very limited as only a few different types of transceivers are sold on the market. We have conducted our experiments with the DecaWave DW10 0 0 [START_REF] Decawave | Module[END_REF] transceiver. Since this sensor platform is not available in open WSN testbeds, we've conducted our measurements with our own platform as described in Section 4.1 . This transceiver offers advanced functionalities that may be leveraged to increase the accuracy of ranging operations. However, the protocols defined in this paper don't require these advanced features and thus, are portable to other types of platforms. The only characteristic required for selecting another transceiver is to be able to record message emission and reception dates with a precision in the order of tens of nanoseconds.

Advanced hardware functionalities are for instance (i ) the ability to learn the clock skew between two nodes engaged in a ranging operation as leveraged in [START_REF] Fofana | An original correction method for indoor ultra wide band ranging-based localisation system[END_REF] , or ii ) the ability to schedule the emission of a frame at a specific future date as leveraged in [START_REF] Despaux | Accurate and platform-agnostic time-of-flight estimation in ultra-wide band[END_REF] . If such features are available, it is possible to improve the precision of the protocols proposed herein or reduce the number of messages required.

N-TWR: A novel time-of-flight localization protocol

As said, time-based positioning systems rely on the measured travel times of signals between nodes. Our objective in this work is to provide an accurate Time-of-Flight based localization protocol (N-TWR) where a target node can accurately estimate its position using a reduced number of messages exchanged with N anchor nodes. Localization of the target necessitates the estimation of the range separating the target node from each anchor node. This ranging operation can be performed naively by realizing N basic SDS-TWR operations. Instead, our N-TWR solution elegantly leverages our Skew-Aware TWR [START_REF] Despaux | Accurate and platform-agnostic time-of-flight estimation in ultra-wide band[END_REF] protocol to perform the N ranging operations and calculate the location of the anchor accordingly.

This section describes the N-TWR protocol by first describing the features of Skew-Aware TWR. Next, it defines how N-TWR operates and calculates the target location from the N target-anchor ranges. Note that all operations performed in N-TWR can be implemented on today's UWB transceivers.

Skew-Aware TWR ranging

The proposed approach is based on the TWR protocol. As shown in Fig. 1 (b), once the message reply reaches the destination, node A will be able to estimate the ToF as in Eq. (2) . However, t 4 -t 1 and t 3 -t 2 are values that are computed by different nodes having different clock rates. Hence, the time difference t 3 -t 2 measured with the clock rate of A and t 4 -t 1 with the clock rate of B are really different, even though they represent almost the same time interval. Authors in [START_REF] Fofana | An original correction method for indoor ultra wide band ranging-based localisation system[END_REF] propose a skew compensation based on a DecaWave DW10 0 0 functionality that allows obtaining the frequency relationship between nodes:

k = f B f A
. Then, the estimation of the ToF by taking into account the clock skew can be computed as follows:

T oF ′ = t 4 -t 1 -k (t 3 -t 2 ) 2 (4)
However, this approach is platform-dependent in the sense that it relies on the DecaWave DW10 0 0 functionality for compensating the skew. In order to be able to estimate the skew for any type of platform, we have proposed in [START_REF] Despaux | Accurate and platform-agnostic time-of-flight estimation in ultra-wide band[END_REF] another approach which doesn't depend on a specific hardware functionality. It proposes a method based on linear regression that allows us to estimate the skew value K . Linear regression solution is obtained using the least squares methodology [START_REF] Yan | Linear Regression Analysis: Theory and Computing[END_REF] provided by the SciPy scientific library [START_REF] Jones | SciPy: open source scientific tools for Python[END_REF] for Python.

From the message exchange shown in Fig. 1 (b), node A receives t 2 and t 3 representing the dates the first pulse of the first symbol of the PHR of the START message (RMARKER) arrives at node B and the moment when the SFD marker of the ACK packet leaves the antenna, respectively. This information is very useful for node A to estimate the skew of node B with respect to node A . This can be done as shown in Fig. 7 where the line's slope represents the skew between node A and B . This first TWR iteration will allow node A to obtain a first rough estimate of the skew between itself and node B , based on the line passing through points ( t 2 , t 1 ) and ( t 3 , t 4 ). Successive message exchanges will allow node A to estimate a more accurate skew by means of a linear regression approach which will consider, not only, the current points ( t 2 , t 1 ) and ( t 3 , t 4 ), but also those previously computed. By successively computing the slope of the regression line, the estimation of the ToF can be improved in the same way as done in [START_REF] Fofana | An original correction method for indoor ultra wide band ranging-based localisation system[END_REF] but using the slope learned with the linear regression method:

T oF ′′ = t 4 -t 1 -slope (t 3 -t 2 ) 2 (5)
An important point to emphasize is the fact that our linear regression approach approximates the skew by considering two points ( t 2 , t 1 ) and ( t 3 , t 4 ) and it assumes the global instants t 1 and t 3 to be equal to t 2 and t 4 , respectively. In other words, the propagation time is neglected. This assumption is not unreasonable given that the propagation time is around 9 nanoseconds (for a distance of 2 m) while (t 4 -t 1 ) and (t 3 -t 2 ) are around 300 µs. Clearly, the impact of these few nanoseconds over the skew can be considered as negligible.

It is important to stress as well that the number of messages sent with Skew-Aware TWR is of at most three and at least two if ACK and REPLY are merged using the scheduling functionality of [START_REF] Van Den Bossche | Decaduino: an open framework for wireless time-of-flight ranging systems[END_REF] , which is a two-fold decrease compared to SDS-TWR.

Another important point is the channel access mechanism of Skew-Aware TWR. Every time a node has a message to send (START, ACK, REPLY), it sends it as done in Aloha method. In other words, there is no advanced access control for sending these UWB frames. Since in this case, only two nodes emit messages one after the other, there is no risk for collisions among these frames. By means of this scheme, we avoid delaying the reception of timestamps (which may have a non-negligible impact in the ToF and thus, in the ranging estimation).

In Section 4 , experiments show how the accuracy on the estimated ToF is improved for Skew-Aware compared to the basic TWR protocol. An experimental comparison of Skew-Aware TWR with SDS-TWR is presented as well, showing that both protocols offer the same level of ranging accuracy. Skew-Aware TWR being particularly energy-efficient and precise, we have leveraged it to derive our N-TWR N-ary ranging protocol presented next.

N-TWR ranging protocol and localization algorithm

In this section, we present the proposed N-TWR N-ary ranging protocol that builds on our improved Skew-Aware TWR scheme. The aim of N-TWR is to compute with a limited number of message exchanges the distance between the target node and a set of N anchor nodes distributed in the building, concurrently. Based on the ranging measurements, we introduce a novel localization algorithm that, knowing the anchor locations, derives the target position.

N-TWR

Fig. 8 shows the sequence diagram of the proposed protocol. The target node starts by broadcasting a START packet (violet segment) recording its departure time t 1 . Once the broadcast message arrives at anchor A i , it records its arrival time t i 2 and sends back an ACK message (grey line) at t i 3 . If the transceiver is able to schedule the emission of message (cf. Fig. 2 (a)), the ACK message can hold both t i 2 and t i 3 timestamps. For the DecaWave DW10 0 0 platform, the transmission time resolution is of 15.625 ps; The emission can be scheduled at the beginning of an 8ns timeslot. Thanks to this feature, the MAC-layer has the ability to generate a frame which includes its future emission date.

Once the target node receives the ACK message from anchor A i , it records its arrival time t i 4 . From t 1 , t i 2 , t i 3 and t i 4 , the target node computes the ToF from itself to anchor A i using the linear regression skew compensation of Skew-Aware TWR presented in Section 3.1 . The same calculation is applied to obtain the range separating the target from the other anchors. Fig. 9 illustrates the proposed N-ary protocol.

In our experiments, and in order to avoid collisions, a deterministic delay d between A i and A j ACK messages is enforced, ∀ i, j, i = j . The idea behind this schema is to implement a static TDMA which is determined based on the anchor's addresses. The anchor having the lower address value, and after a fixed delay, sends the response back to the tag in the first place. The second lower address anchor will then wait for the first message and will send its response at its assigned slot. The procedure is then executed for all anchors. These delays are represented in the sequence diagram ( Fig. 8 , green rectangle). Once the target node has computed the ToF from itself to each of the anchors, it will be able to find its position using the known locations of the anchors with a given localization algorithm.

Thanks to the broadcast of the START message, N-TWR reduces the number of messages needed to poll n anchors. By using N-TWR, the whole ranging process is completed in a shorter time than classical ranging protocols, typically few milliseconds, depending on the number of anchors. This duration is consistent with usual duty cycles values considered in WSNs: for a ranging period of one second, the duty cycle is lower than 1%. The message number reduction, combined with the limited range of UWB transmission, has another benefit: it offers good scalability properties to N-TWR. Only a limited number of anchors will receive the initial START message and participate to the localization operation. This localization operation only lasts a couple of milliseconds. As such, it is reasonable to think that several target nodes could request for localization with N-TWR. However, how to orchestrate several localization requests concurrently is not investigated in this paper and is kept for future works.

Next we present the specific trilateration algorithm used in this work to localise the target node.

Localization algorithm

In order to validate the N-TWR N-ary ranging protocol presented in the previous section, we have designed a specific trilateration algorithm. This algorithm localizes the target node knowing the anchor node locations and the ranges measured with N-TWR. From N-TWR ranging, the target nodes computes the distances to each anchor following:

dist <t,i> = v × T oF <t,i> (6)
being ToF < t, i > the time of flight from the target node t to anchor i , and v the propagation speed. With this information, a set of N circles C = { C 1 , C 2 , . . . , C N } of center ( x i , y i ) and radius r i are constructed, where ( x i , y i ) represents the position of anchor i and r i the range dist < t, i > between the target and anchor i . In our experiments, we consider three anchors and the size of the set C is thus equal to 3 ( N = 3 ). The position of the target belongs to the surface intersecting all circles in C.

Main localization steps.

Our trilateration algorithms works in the following manner. First, from the set of circles C defined with center and radius, we compute the set of intersection points P where the circles intercept. An intersection point is added to this set if it belongs to at least two circles. From this set P, the location of the target node S is derived as the centre of mass of all points in P. This last calculation of S is developed later for the case where N = 3 .

Extension of the circle set.

ToF measurements are prone to errors, leading to sometimes too large or too small circles. In such cases, the intersection points of the circles of C may be an empty set. To account for potential errors in the localization algorithm, the set of circles C is extended to capture potential imprecisions in the ranging. The procedure for creating this extended set is given as follows:

For each C i ∈ C , we consider the set of k + 1 concentric circles C = { C r i } where r represents the radius taken from the set of R = { r i ,

r i + k, r i + 2 k • • • r i + k 2 } .
In other words, we consider the original circle of radius r i and those formed by incrementing its length from r i to r i + k 2 with an increment of k units. Fig. 10 shows the concentric circles created from a given circle C i .

The extended set of circles is composed of the set of all concentric circles derived from the original circles in C. Besides, three particular cases can also be identified as shown in Fig. 12 . Here, Fig. 12 (a) and (b) are particular cases of Fig. 11 (b), while Fig. 12 (c) is a particular case of Fig. 11 (d).

Target location derivation for

Considering the fact that the target node has all the information regarding the anchor positions as well as the distance to each of them, the previously presented procedure for intersecting the set of circles can be easily computed by the target node.

Moreover, we have illustrated the computation of S for the case where N = 3 . We show that this case performs very well in our experiments in next section. We can develop a localization step for larger N , but the fact that N-TWR works well for 3 anchors is really interesting as it offers interesting scaling properties. Indeed, if T targets want to localize themselves concurrently and there are N > > T anchors available for servicing these requests, ⌊ N / T ⌋ requests could be performed in parallel at most. Of course, proper scheduling and anchor to target assignements have to be arranged by a higher layer protocol. This feature is out of the scope of this paper and left for future works but previous research has demonstrated its viability for other localization technologies [START_REF] Gui | Improving localization accuracy using selective 3-anchor dv-hop algorithm[END_REF][START_REF] Dalce | Indoor self-localization in a WSN, based on time of flight: propositions and demonstrator[END_REF].

Experiments & results

In this section, experimental results are given to validate the performance of the previously presented protocols and algorithms. First, a description of our testbed is given. Second, we introduce a set of experimental scenarios for which we can test the performance of the Skew-Aware TWR protocol of Section 3.1 . In order to accurately carry out this experimental evaluation, a preliminary experiment had been done whose objective is to determine the impact of the antenna's orientations on the estimated ToF. Based on these preliminary results, experiments were carried out to compare Skew-Aware TWR to both T WR and SDS-T WR. Finally, the N-TWR protocol has been experimented together with the results of our trilateration localization algorithm.

Testbed description

The testbed is based on DecaDuino [START_REF] Van Den Bossche | Decaduino: an open framework for wireless time-of-flight ranging systems[END_REF] , an open framework for the fast-prototyping and performance evaluation of UWBbased protocols. It provides a driver for the DecaWave DW10 0 0 UWB transceiver and modules based on this transceiver, such as DecaWave DWM10 0 0. In addition to wireless communication, DecaDuino supports ToF ranging. As a classical Physicallayer Service Access Point (PHY-SAP), DecaDuino provides the two conventional Physical-Data (PD) and Physical Layer Management Entity (PLME) SAPs which enable MAC-level protocols to send/receive data and configure the transceiver (channel, transmission rate, preamble parameters...). Since this framework was designed to aid in the implementation of ToF based protocols, DecaDuino also provides access to the Physical-level 64 GHz high precision timer which offers precise message timestamping at both transmission ( t TX ) and reception ( t RX ) with a resolution of 15.625 ps. Finally, DecaDuino implements advanced synchronization/timestamping functionalities such as delayed transmission and receiver skew evaluation. A compliant hardware called DecaWiNo is also described in [START_REF] Van Den Bossche | Decaduino: an open framework for wireless time-of-flight ranging systems[END_REF] and shown in Fig. 13 . On this design, the transceiver is a DWM10 0 0 [START_REF] Decawave | Module[END_REF] and the Arduino board is a Teensy 3.2 which embeds an ARM Cortex M4 32-bit MCU rated at 72 MHz, with 64 kB RAM and 256 kB program memory. DecaWiNo follows an open hardware design; various ressources on this node can be found at [START_REF]DecaWiNo and DecaDuino ressources[END_REF] . There is no specific operating system deployed on the micro-controller, all protocol operations being implemented in C.

Measurements have been done in two different types of environments: an anechoic chamber and a non-isolated room depicted in Fig. 14 (a) and (c), respectively. As seen on the map, reflexions on walls and furniture may trigger multipath fading in the non-isolated room. During the measurements, there was no other wireless system functioning in the 5 GHz ISM frequency band. As we'll see in our experiments, and as expected, results for the nonisolated room setting are really close to the ones obtained in the anechoic chamber. This is a consequence of the robustness of UWB to multipath fading.

Preliminary experiment

The idea behind these series of experiments was to be able to determine the impact of the antenna's orientation over the ToF. Indeed, the antenna present on the module is not perfect: its orientation impacts the ToF measurement. As usual when using a testbed, the nodes and environment has to be carefully controlled to offer a clean setting where results can be properly understood.

Experiments have been carried out in the anechoic chamber of Fig. 14 (a) for two nodes separated by a distance of 2 m. One of the nodes is located on a rotating table ( Fig. 14 (b)). Fig. 15 shows the configuration of the first preliminary experiment. A total of four preliminary experiments are listed in Table 1 .

During the tests, node B is fixed while node A is rotated of 5 °per second, starting at 0 °. Experiments stop when the angle of 180 °is reached. For each angle value, one basic TWR ranging operation is performed 1 As such, the result of each experiment is a set of ToF measurement for different angles of incidence of node A 's antenna. We recall that no skew compensation is performed in TWR, inducing larger ranging errors. The point is here not to get the most accurate ToF measurement, but to find the orientation of A relatively to B that offers the best conditions (and thus reduces the ranging error).

Fig. 16 shows for each scenario the results in terms of the distance error for different angles of incidence. Results clearly show the impact of the antenna's alignment on the quality of ToF measurements and therefore, on the ranging error. In fact, for each of the scenarios we can see that, as node A 's antenna gets closer to 90 °, the distance error reduces, independently of node B 's configuration. Table 2 summarizes the experiments made. For each of the scenarios we show the average distance error and the standard deviation, together with the orientations where best and worst values are achieved. From this we can see that both scenarios 2 and 3 seem to be better than the others. Minimum error is achieved when the antenna's angle for node A is around 75 °with both nodes in vertical position (or vertical and horizontal position for node A and B , respectively). These results were useful for us to find the optimal configuration for estimating and comparing the ToF in the following experiments validating our Skew-Aware TWR protocol. Our results confirm and clarify several existing works such as [START_REF] Zhou | The UWB imaging system with rotating antenna array for concealed metallic object[END_REF] .

TWR and Skew-Aware TWR comparison

In this experiment, our objective is to measure the accuracy improvement of our Skew-Aware TWR approach compared to legacy TWR. In order to carry out this, we have set up four different scenarios by changing the distance between nodes. The comparison is done in terms of the distance error computed from the estimated ToF for: traditional TWR (without skew compensation), Skew-Aware TWR (skew estimated from a linear regression approach) and also Skew-Aware TWR where the skew is estimated from the DecaWave's functionality. Non-isolated room 3

Scenarios

Scenarios were set up in two different environments: an anechoic chamber as well as in a non-isolated room. Table 3 shows the scenarios' configuration. Here, Scenario 5 and 6 have the same configuration parameters as Scenarios's 8 and 9, respectively. We also included a fifth scenario in which we compare the distance error for a distance of one metre. Based on the preliminary results presented in Section 4.2 , antennas were aligned in an optimal way (angle of 75 °for node A and 90 °for node B). For practical reasons, we consider the second scenario's configuration where both nodes are in vertical position.

The idea then is to compute the ToF estimated from the original TWR and the Skew-Aware TWR (by means of both skew approaches). Then, based on the computed ToF, the distance error (in percentage of the real distance) is derived. We consider two methods for estimating the skew: the linear regression approach of Section 3.1 and the DecaWave's functionality. We also present a comparison between both of them.

Results

Figs. 17 and 18 present the results in terms of the distance error computed from the ToF estimation for each of the predefined scenarios. These figures show the percentage of the real distance that the error represents. The first conclusion we can draw from these results is that the estimation of the ToF is significantly improved when compensating it with the skew estimation. This result was also confirmed in [START_REF] Fofana | An original correction method for indoor ultra wide band ranging-based localisation system[END_REF] for a skew estimated by means of the DecaWave's functionality. Secondly, we can see that there is no significant difference between the estimation done by both skew compensation approaches. This is due to the fact that both skew estimations are not so far from each other. Fig. 19 shows the skew's evolution in parts per million (ppm) for both approaches. Green line represents the evolution of the computed slope while red points represent the estimated skew from DecaWave DW10 0 0 transceiver. As we can see, skew between nodes seems to sta-bilise as the time goes by. This may be due to the fact that skew is affected by sensor's temperature. In order to confirm this, we have run an experiment for 20 min in which we measure both skew and temperature for a set of two nodes exchanging messages. Fig. 20 shows that, after 600 seconds, both temperature and skew stabilises showing the close relationship between both parameters. In this experiment, node A sends one message per second. After sending the message, it turns the radio off in order to save energy. On the other side, node B remains awake in order to receive the message from A . This can explain the difference in terms of the temperature between two nodes.

Table 4 presents the average distance error for scenarios 5-9. The last two columns show that the distance error is almost the same for both skew estimation approaches. However, a slight improvement in the ToF estimation can be achieved when compensating the skew by linear regression (see LR column).

SDS-TWR and Skew-Aware TWR comparison

Since SDS-TWR is conceived to minimise the impact of the clock skew, our objective in this experiment set-up was to compare SDS-TWR with the Skew-Aware TWR in terms of the distance error. Based on results presented in previous section ( Fig. 19 ), we only consider the skew compensation based on linear regression since it is slightly more accurate than the DecaWave's functionality.

Scenarios

Two scenarios were considered for this experiment, both of them were run in a non-isolated room for two distances: 2 and 3 m. Details are shown in Table 5 .

Results

Fig. 21 shows distance error in percentage of the real distance for both SDS-TWR and Skew-Aware TWR. SDS-TWR and Skew-Aware offer very close performance. However, as already highlighted, SDS-TWR necessitates a nearly two-fold increase in the number of messages exchanged.

This increase, as shown later in Section 4.6 , has a negative impact on energy consumption compared to Skew-Aware TWR.

Table 6 shows the average distance error for both protocols. While SDS-TWR needs at least five messages to achieve this precision, our approach makes only use of three messages. Note that this number can be reduced even further to two messages if t 2 and Fig. 18. Distance error comparison: non-isolated room t 3 are embedded in the ACK message, as done in [START_REF] Van Den Bossche | Decaduino: an open framework for wireless time-of-flight ranging systems[END_REF] , by using the scheduling functionnality of DW10 0 0 transceiver.

Finally, we have also carried out a t -test over the samples in order to compare the means of distance errors for both approaches. From Table 7 we can see that for both scenarios, the p -value is below the standard thresholds of 0.05 or 0.01, so we reject the null hypothesis and we can say that there is a statistically significant difference between both means ( Table 6 ).

Localization with N-TWR

Previous experiments validate the quality of the Skew-Aware TWR approach defined in Section 3.1 . We have shown, for isolated and non-isolated environments, that the ranging precision achieved with Skew-Aware TWR is in the same order than the one achived by SDS-TWR, but for a reduced number of messages. In the following experiments, the performance of N-TWR is evaluated for the localization of a target node by N = 3 anchor nodes.

Scenarios

Two experiments are considered here for 2 different locations of the target node as depicted on Fig. 22 . In Section 4.2 , we have shown the importance of aligning antennas in order to minimise the ToF estimation error. Since we are considering both scenarios in 2D, it is impossible to perfectly align anchors' antennas with the target node antenna. In the future, we expect to run our experiments by considering omnidirectional antennas (isotropic 3D). The antennas configuration is done as follows: Anchors 2 and 3 are positioned at an angle of 45 °with respect to the target antenna position. On the other hand, Anchor 1 is positioned at an angle of 180 °with respect to the target antenna position. The target node broadcasts a START message every 500 ms and, as shown in Fig. 8 (green rectangles), anchors send the ACK messages following a schedule in order to avoid collisions: Anchor 1 waits 400 µs before sending its ACK, Anchor 2 waits 800 µs and Anchor 3 waits 1200 µs after the arrival of the broadcast message com- ing from the target node. A total of 536 measurements were done. Regarding the concentric circles, the set R of considered radii is defined as R = { r, r + k, r + 2 k, r + 3 k } with k = 10 centimeters. For each measurement (t 1 , t i the ToF from itself to each of the anchors following N-TWR protocol. Once the ToFs are estimated, the localization algorithm of Section 3.2.2 is applied to estimate the location of the target node.

Results

In this section we present the results concerning the protocol N-TWR and the quality of the localization of the target. The evaluation of the N-TWR is done in two steps:

• First, we compare the ToF estimation of the N ranging operation with N-TWR to a solution where N consecutive SDS-TWR operations are performed.

• Second, we assess the quality of the localization of the target node with the localization algorithm of Section 3.2.2 . Table 8 lists the real and the estimated distance, as well as the ranging error. SDS-TWR performs better for ranging with anchors 1 and 3, while N-TWR performs better for the ranging with anchor 2. Ranging operations are in the order of tens of centimeters for both protocols.

Localization error of the target.

Once the target node has estimated the distance between itself and the set of anchor, it will be able to localise itself by means of the trilateration algorithm presented in Section 3.2.2 . In these experiments, the localization algorithm has been executed offline, on a regular computer. Fig. 23 shows the estimated target position after the execution of the N-TWR protocol and the localization algorithm. Details are shown in Table 9 in which we show the average error distance in meters, the standard deviation as well as the best and worst distance error. We recall that a total of 536 measurements were done. Results are really good as the average localization error of the target is in the range of ten to twenty centimeters.

Energy evaluation

This section concentrates on the energy performance evaluation of the ranging protocols discussed in this paper. This model mostly offers a sim ple way of com paring the ener gy consum ption of the The protocol sequences rely on several MCUs2 (e.g. CPU, RAM, flash) and transceiver states. They all consume a different power lever as indicated in Tables 10 and11 . The values listed in both tables have been verified on our testbed. The aim of this section is to calculate the energy consumed by the target node for each protocol (T WR, SDS-T WR, 2M-T WR, D-T WR, SDS-T WR-MA and our contribution N-TWR) and this when several anchors are considered. The proposed derivation is based on a classical model where energy is obtained for each state by multiplying the power consumed by a state by the time this state is active in the protocol sequence.

For the MCU, we consider two states: active (with f CPU = 48 MHz) and hibernate . For the transceiver, we consider all the available states. To compare the protocols, we consider a simple energy profile for the target with states: • The action "sending message" has a duration D tx where the MCU is in active mode and the transceiver in transmit mode. In this first simple model, we do not consider frame length variation: all messages have the same length. This action implies an energetical cost C tx ,

• The action "wait-for-ack-frame" has a duration D rx -ack where the MCU is in active mode and the transceiver in receive mode. This action implies an energetical cost C rx -ack ,

• The action "wait-for-data-frame" has a duration D rx -data where the MCU is in active mode and the transceiver in receive mode. This action implies an energetical cost C rx -data ,

• Between these actions, the remote node MCU is in active mode and the transceiver in idle mode, during the corresponding duration; this implies energetical costs C idle -ack and C id le -d ata .

The sequence diagrams of the investigated protocols are represented in Fig. 24 . In this study, we compare all protocols using the same following timing values: D tx = 200 µs; D rx -ack = 400 µs; D rx -data = 800 µs. In reality of course, these timing values vary across protocols. But this simplifying assumption has been made to compare the protocol on a unified basis. From the sequence diagrams, the timing values of the four states and power values of Tables 10 and11 , the energy consumed by the target node when performing an N-ary ranging operation to the anchors is computed for each protocol. is the most energy-efficient protocol since the anchors are solicited with a single broadcast message.

Results discussion

Skew-Aware TWR ranging

In Section 4.3 , we have evaluated Skew-Aware TWR and compared with the traditional TWR protocol. From the results we can conclude that our approach for compensating the clock's skew improves the performance of the ToF estimation without asking for any additional message exchange between nodes. This is an important improvement to the TWR protocol to accurately estimate the ToF, and consequently, the ranging between nodes. In order to estimate the skew, two approaches were proposed: the first one based on a linear regression estimation and the second one considering the functionality of DecaWave. Both approaches improve the performance of the ToF's estimation, as shown in Figs. 17 and 18 . However, results stemming from the linear regression method are slightly better than the ones using the DecaWave's functionality. Besides, the linear regression approach can be applied independently of the underlying hardware.

We have also compared our Skew-Aware TWR approach with SDS-TWR in terms of the distance error. Results in Section 4.4 show that our approach is slightly better than the estimation provided by SDS-TWR. Furthermore SDS-TWR requires at least five message exchanges for getting ranging information while Skew-Aware TWR needs at most three messages. It can be reduced to two messages to follow the emission scheduling capability of the hardware as proposed in the 2M-TWR protocol.

N-TWR Protocol

In order to evaluate N-TWR, we have carried out an experiment considering two scenarios by varying the distances between the target node and one of the anchors. We have first evaluated the individual ranging errors between the target and the anchor nodes by comparing both N-TWR and SDS-TWR protocols. Since positions of both target and anchors are fixed and known, the theoretic distances between them ( d th i ) is known. This theoretic distance is then compared with the empirical ones ( d est(NT W R ) i and d est(SDS) i ).

From Table 8 we can see that, for the first scenario, the average distance error (considering the tree anchors) is about 13 cm for the N-TWR while for the SDS-TWR, 9 cm. For the second scenario, about 18.8 cm for N-TWR and 13.5 for SDS-TWR. For both protocols, Table 8 suggests that this difference between both scenarios may be due to the impact of the distance between the target and Anchor 1, which is doubled from one scenario to another. This can be clearly seen when comparing d est(NT W R ) 2 and d est(NT W R ) 3 (average), which remain almost the same for both scenarios. The same can be seen for the SDS-TWR protocol.

However, the average distance error from the target node to Anchor 1 increases from 6.21 to 20.49 cm for the case of N-TWR and from 1.93 to 15.97 for SDS-TWR. Regarding the performance in terms of the distance error for the N-TWR protocol with respect to SDS-TWR, we can see that SDS-TWR is more accurate for estimating the distance between the target node to each of the anchors. However, SDS-TWR achieves an accurate estimation to the detriment of the number of messages exchanges. In fact, SDS-TWR needs four messages between the target and a given anchor for estimating the ToF and thus, twelve messages were needed in our experiments. In general, considering N anchors, the total number of message exchanges between target and anchors would be 4 × N . On the other hand, our N-TWR protocol needs only N + 1 messages for achieving good results which are not so far from those obtained by SDS-TWR. The message number reduction has an impact on energy consumption, as seen on Fig. 25 : N-TWR is better than SDS-TWR since the anchors are sollicited with a single broadcast message.

As underlined previously, SDS-TWR offers a better ranging error compared to N-TWR. Looking closer at the ranging errors to anchor nodes in Table 8 , we see that the theoretic distance between the target and anchors 2 and 3 is the same (141cm). Distances estimated with SDS-TWR are similar in both cases (around 128 cm), which is reasonable. However, with N-TWR, the distance estimated between target and anchor 2 is of around 133 cm and the one between target and anchor 3 of around 114 cm. This difference can be explained by the fact that the time that has ellapsed between the START message emission and the emission of the ACK messages of anchors 2 and 3 is different. Typically, the ACK message of anchor 3 is sent 400 µs after the one of anchor 2. At the time the tar- get receives the last ACK of anchor 3, the timestamps measured for the START message emission as relevant anymore as the internal clock drift of the anchor has probably changed. The best behavior of SDS-TWR is explained by the fact that the time ellapsed between START and ACK messages is short. This result call for an implementation of N-TWR where the number of anchors stays limited to 3 or 4 nodes maximum.

Even though the ranging error of N-TWR is a little larger the one of SDS-TWR, our localization algorithm ensures a ten to twenty localization accuracy of the target. Results presented in Fig. 23 and in Table 9 clearly underline the complementarity of the N-ary ranging with the localization trilateration algorithm we have proposed herein.

Overall, we can conclude N-TWR is a good solution for tracking a target node with an dozen centimeter-level accuracy in an indoor environment. It offers a greatly reduced energetic footprint compared to the other solutions while achieving pretty accurate distance estimations. Reducing the number of messages per localization operation is beneficial for the overall network throughput. Plus it offers a better ground for scaling the system to localize numerous targets concurrently.

Conclusions and future work

In this work we have presented N-TWR, a ToF-based N-ary ranging protocol for WSN in UWB. The aim of this protocol is to be able to accurately estimate the distance between a target node and a set of anchors. Therefore, we have first introduced an approach for estimating the ToF between two nodes, taking into account the skew between nodes while minimizing the number of exchanged messages. Two techniques for estimating the skew were presented, the first one based on a DecaWave functionality and the second one based on a linear regression approach, both of them efficiently improving the ToF precision. These preliminary results, together with those concerning the antenna alignment, were useful for conceiving a protocol (N-TWR) which is able to estimate the ranging between nodes while minimizing the impact of the skew as well as the number of exchanged messages. We have then evaluated the N-TWR protocol in LOS conditions, by comparing it to SDS-TWR, in terms of the distance error.

Results in Section 4.5 show that the protocol achieves a good performance in terms of the distance error between nodes even though results from SDS-TWR are slightly more accurate. Nevertheless, SDS-TWR achieves a better performance to the detriment of the number of exchanged messages which in considerably higher compared to N-TWR. In fact, SDS-TWR needs 4 × N messages to estimate the distance between the target and the set of N anchors, while N-TWR only N + 1 . Therefore, we can conclude that our Nary ranging protocol is suitable for applications requiring a limited number of messages exchanged. N-TWR offers thus a reduced energetic footprint while achieving a dozen centimeter-level accuracy for ranging operations.

Finally, we have proposed an improved localization algorithm that locates a target node by intersecting concentric circles. Starting from the information regarding the distance between nodes (radius), a set of concentric circles are accounted for by varying the radius. The target position is then computed by intersecting a set of circles and by studying different cases. Results show that the estimated target position is in the order as well of 10 to 20 cm, which is really encouraging.

As a future work, we will tackle the problem of scaling the proposed solution. Therefore, we will work on a defining a higher layer protocol that will orchestrate the localization requests of multiple nodes. To validate this work, we plan to extend our experiment setting: use more anchors (a deployment of 20 nodes is planned), longer distances (20 m), multiple targets. We aim as well at performing extensive measurements with realistic indoor scenarios, including NLOS conditions, WiFi/Bluetooth networks coexistence and mobile nodes. To carry out this set of experiments, we plan to use omnidirectional antennas to increase the precision in the ToF estimation. Three rails, with three mobile nodes with a millimeter positioning precision, will also be available on our testbed in the future; they will enable the execution of automatic positioning scenarios. We plan as well to work on a finer-grained energy consumption model by using more realistic state models that includes message lengths and MCU/transceiver sleep modes.

Fig. 1 .

 1 Fig. 1. TOA and TWR protocols.

Fig. 2 .

 2 Fig. 2. 2M-TWR and SDS-TWR protocols.

Fig. 3 .

 3 Fig. 3. SDS-TWR-MA protocol [23] .

Fig. 4 .

 4 Fig. 4. D-TWR protocol[START_REF] Kwak | A new double two-way ranging algorithm for ranging system[END_REF] .

Fig. 5 .Fig. 6 .

 56 Fig. 5. IEEE 802.15.4a packet.

Fig. 7 .

 7 Fig. 7. Skew estimation.

Fig. 8 .

 8 Fig. 8. The N-TWR sequence diagram.

Fig. 9 .

 9 Fig. 9. The N-TWR protocol.

Fig. 10 .

 10 Fig. 10. Concentric Circles { C r i } for a given anchor i .

N = 3 .

 3 The following algorithm is defined for |A| = 3 (i.e. we have three circles to intercept) to extract the location of the target node from the set of intersection points P. It is illustrated in Fig.11. The intersection procedure calculates the coordinates of the intersection points. Depending on the location and size of the circles, a different number of intersection points can be obtained. For the case of |A| = 3 , four cases are depicted that are solved as follows:• No intersection points Fig.11(a) No solution exists -S = ∅ . • Two-point intersection set ( Fig. 11 (b)): In this case, P = { A, B } and there is one circle, C out which doesn't intercept any other circle. The point S is obtained as follows. First, the midpoint p m of [ A, B ] segment is calculated. Then, the segment s = [ p m , c ] , with c the center of C out , is constructed. The solution S is obtained by finding the center of mass of A, B and C where C is the intersection of segment s and C out .• Four-point intersection set ( Fig.11 (c)): In this case, the intersection set holds 4 points. The solution is then obtained by selecting first the closest pair of points ( A and B ). The location S is

Fig. 11 .

 11 Fig. 11. Circle intersections scenarios.

Fig. 12 .

 12 Fig. 12. Circle intersections scenarios (particular cases).

Fig. 13 .

 13 Fig. 13. DecaWiNo: Deca-Wireless Node.

Fig. 14 .

 14 Fig. 14. Anechoic chamber, non-isolated room map and rotating table.

Fig. 15 .

 15 Fig. 15. Scenario 1.

Fig. 16 .

 16 Fig. 16. Distance error versus angle of incidence (antenna).

Fig. 17 .

 17 Fig. 17. Distance error: anechoic chamber

Fig. 19 .

 19 Fig. 19. DecaWave (DW) and Linear Regression (LR) skew evolution in parts per millon (ppm).

Fig. 20 .

 20 Fig. 20. Relationship between Temperature and Skew.

Fig. 21 . 22 .

 2122 Fig. 21. SDS-TWR versus TWR with skew comparison.

4. 5 . 2 . 1 .

 521 ToF with N-TWR and SDS-TWR. The range obtained with a single N-TWR operation and with N SDS-TWR subsequent operations is illustrated next. Lets call d est(NT W R ) i and d est(SDS) i the estimated distances between the target and anchor i for both N-TWR and SDS-TWR, respectively. Since both target and anchor positions are fixed and known, the theoretic distances are also known. Lets call d th i the theoretic distance between the target and anchor i . The ranging error in centimeters is calculated with | d est(NT W R ) i -d th i | .

Fig. 23 .

 23 Fig. 23. Position estimation for each scenario.

Fig. 25 Fig. 24 .Fig. 25 .

 252425 Fig. 24. Ranging Protocols Sequence Diagrams. Blue rectangles represent reception states while red ones represente active transmission states. (For interpretation of the references to colour in this figure legend, the reader is referred to the web version of this article.)

Table 1

 1 Scenario's configuration. Distance error versus angle of incidence (antenna).

		Node A			Node B
	Scenario	Position	Angle's rotation	Position	Fixed angle
	Scenario 1	Vertical		0 °-180 °Vertical	0 °Scenario
	2	Vertical		0 °-180 °Vertical	90 °Scenario
	3	Vertical		0 °-180 °Horizontal	90 °Scenario
	4	Horizontal	0 °-180 °Horizontal	90 °Table
	2
	Scenario	Max		Min
			Angle °Error(cm)	Angle °Error(cm)
	Scenario 1	0	92	75	68
	Scenario 2	0	61	75	27
	Scenario 3	0	56	70	28
	Scenario 4	0	68	55	47

Table 3

 3 Scenario's configuration for ToF measurements.

	Scenario	Room	Distance (meters)
	Scenario 5	Anechoic chamber	2
	Scenario 6	Anechoic chamber	3
	Scenario 7	Non-isolated room	1
	Scenario 8	Non-isolated room	2
	Scenario 9

Table 4

 4 Average error comparison between TWR (without skew), TWR (skew Linear Regression (LR)) and TWR (skew DecaWave (DW)).

		Average error (meters)
	Scenario	Without skew	Skew (LR)	Skew (DW)
	Scenario 5 (ACH)	0.519	0.120	0.146
	Scenario 6 (ACH)	0.7	0.357	0.372
	Scenario 7 (NIR)	0.36	0.012	0.009
	Scenario 8 (NIR)	0.534	0.145	0.158
	Scenario 9 (NIR)	0.70	0.306	0.316

Table 5

 5 Scenario's configuration for SDS-TWR and TWR comparison.

	Scenario	Room	Distance (meters)
	Scenario 10	Non-isolated room	2
	Scenario 11	Non-isolated room	3
	Table 6
	Distance error between SDS-TWR and TWR (with skew compensa-
	tion).
		Average error (meters)
	Scenario	SDS-TWR	TWR (LR skew)
	Scenario 10	0.164	0.150
	Scenario 11	0.343	0.328
	Table 7
	SDS-TWR and TWR (with skew compensation): t -test results.
		t -test over samples
	Scenario	t -statistic	p -value
	Scenario 10	7.335	1.319e-11
	Scenario 11	10.194	1.288e-19

Table 10

 10

	DecaWiNo	energy	consumption:	MCU	Freescale
	MK20DX256VLH7.
	MCU state	Details		Power (Vcc = 3.3 V)
	Active	f CPU = 96 MHz	129 mW
		f CPU = 72 MHz	103 mW
		f CPU = 48 MHz	89 mW
		f CPU = 24 MHz	55 mW
		f CPU = 16 MHz	33 mW
		f CPU = 8 MHz	22 mW
		f CPU = 4 MHz	15 mW
		f CPU = 2 MHz	5,1 mW
	Sleep	Sleep, LPTMR wake	2 mW
		Deepsleep, LPTMR wake	650 µW
		Hibernate, LPTMR wake	< 30 µW
	Table 11
	DecaWiNo energy consumption: Transceiver DecaWave
	DWM10 0 0 module.
	State	Details	Power (Vcc = 3.3 V)
	Active	Transmit	145.8 mW
		Receive	4 4 4 mW
		Idle		39.7 mW
	Sleep	Sleep		0.029 mW
	message exchange at the transceiver. Energy dissipation for pro-
	cessing messages by CPU and calculating ranging data is not mod-
	eled herein. Moreover, to be consistent with our implementation
	of the protocols on our MCU, we're having the CPU functioning in
	busy-waiting mode. In other words, it can't go into a reduced en-
	ergy consumption state during emission or reception of a frame.

We could have measured more samples for each angle value, but since measurements are performed in an anechoic chamber, variability is really low.

, t i

, t i

Micro Controller Unit.

Acknowledgments

This work was supported in part by the FEDER/French Occitanie Region within the GUINNESS project.