V Kerzérho
email: v.a.kerzerho@ewi.utwente.nlcomte

M Comte

F Azais

P Cauvet

S Bernard

M Renovell
email: renovell@lirmm.fr

Digital Test Method for Embedded Converters with Unknown-Phase Harmonics

Keywords: converter testing, harmonic characterization, unknown-phase harmonics, Design-for-Test

This paper presents an extension of the ANC ("Analogue Network of Converters")-based method, which is an original Design-for-Test (DfT) technique associated to a dedicated test algorithm to characterize the harmonic components of a set of embedded converters using only digital test resources. The ANC-based method was primarily developed under the assumption that the harmonics' phase is proportional to the input phase. This assumption is not valid for all converter architectures, where filtering effects may affect the harmonics' phase. The improved ANC-based method is able to calculate the magnitude of the harmonic components with unknown phase. The fundamental principle of this improved version of the ANC-based method is the same, but further mathematical developments have been established using a model independent from the harmonics' phase. The simulation results and the experiments show an excellent agreement between the values measured using the method and the values measured with a usual test setup, for the THD and SFDR parameters. Simulations were carried out considering both random phases and realistic phase delays such as the ones induced by a low pass filter.

INTRODUCTION

The popularity of portable data and communication applications like smart phones, laptops, or MP3/MP4 players is currently the wellspring for integration of many different functions into a single package. Systems-in-Package (SiPs) or Systems-On-Chip (SOCs) that integrate very different analogue or mixed-signal blocks have been developed toward this aim. Although they offer clear benefits such as extreme miniaturization or connection length reduction, they imply in compensation very significant test challenges. Indeed in many mixed-signal circuits, the test of the analogue blocks may represent up to 90% of the whole test effort while these blocks represent only 10% of the whole chip area. The reason of such a challenge is twofold. Firstly, analogue testing is made of a long sequence of parametric measurements that are performed using highly precise, but very expensive, instruments. Secondly, the access, the control and the observation of deeply embedded analogue blocks -and consequently, the test access, the test control and the test observation-are increasingly limited, as far as the number of pads is greatly reduced. Consequently the internal accessibility of the whole system is drastically decreasing. Also, as signals become faster and systems are operated at higher speeds, external testing become more susceptible to noise, crosstalk and probing problems.

To overcome these problems, several authors have proposed different Built-In-Self-Test (BIST) techniques where signals are internally generated and/or analyzed [START_REF] Toner | A BIST scheme for an SNR test of a sigma-delta ADC[END_REF][START_REF] Toner | A BIST Technique for a Frequency Response and Intermodulation Distortion Test of a Sigma-Delta ADC[END_REF][START_REF] Ohletz | Hybrid Built In Self Test (HBIST) for Mixed Analog/Digital Integrated Circuits[END_REF][START_REF] Sunter | A simplified polynomial-fitting algorithm for DAC and ADC BIST[END_REF][START_REF] Azais | Towards an ADC BIST scheme using the histogram test technique[END_REF][START_REF] Azais | Implementation of a linear histogram BIST for ADCs[END_REF][START_REF] Arabi | A New Built-In Self Test Approach For Digital-to-Analog and Analog-to-Digital Converters[END_REF]. Another possible and less expensive solution consists in introducing Design-for-Test (DfT) features to internally transform the analogue signals into digital signals that are made controllable and observable from the chip I/Os [START_REF] Nagi | A Signature Analyzer for Analog and Mixed-Signal Circuits[END_REF][START_REF] Mahoney | DSP-Based Testing of Analog and Mixed-Signal Circuits[END_REF][START_REF] Burns | An Introduction to mixed-signal IC test and measurement[END_REF][START_REF] Huertas | Test and design-for-testability in mixed-signal integrated circuits[END_REF]. As a result, only digital signals are externally handled by non-expensive digital test equipment (Low Cost Tester).

In an example prototype for Set-Top-Box applications, like in most current mixed-signal systems, the converters are among the main components: 2 Analogue-to-Digital Converters (ADC) and 6 Digital-to-Analogue Converters (DAC) are embedded in the same SiP. The present specifications for these converters require a 10-bit resolution, but the next generations will make use of 12-bit converters. Testing this whole set of converters is a very complex task requiring a long test time because of the above mentioned problems of accessibility, signal integrity, accuracy of converter parameter measurements.

In this context, an original DfT technique called "Analogue Network of Converters" (ANC) was developed that permits to test the whole set of embedded ADCs and DACs [START_REF] Kerzérho | Analogue Network of Converters": a DFT Technique to Test a Complete Set of ADCs and DACs Embedded in a Complex SiP or SOC[END_REF]. An extremely minimal circuitry is added to the original chip allowing the application of a fully digital low-cost test to the System-in-Package/System-On-Chip. The basic principle relies on setting a test path with DACs and ADCs. The fault masking is avoided by using a post-processing algorithm that discriminates harmonics from the different converters inserted in the test path. The ANC-based method can also be exploited to test standalone ADCs using low resolution arbitrary waveform generators as it breaks the rule stating that the test equipment resolution should be at least 2 bits higher than the ADC under test [START_REF] Kerzérho | ADC Production Test Technique Using Low-Resolution Arbitrary Waveform Generator[END_REF].

The ANC-based method was developed with the assumption that the phase of the harmonic components is strictly proportional to the input signal nominal phase. However our experiments did not confirm this theoretical assumption. Indeed, we could observe that some harmonics may have a non-null phase, despite the input signal phase being set to zero. In this paper, we present an extension of the primarily developed method to the estimation of the harmonics of the output samples with a phase which is not correlated to the phase of the input signal.

The paper is organized as follows. Section 2 gives the fundamental knowledge on data converter testing based on spectral analysis and pinpoints the issues related to the phase of harmonics. Section 3 summarizes the principle of the ANC-based method. The mathematical developments of the improved ANC-based method are then presented in section 4, followed by the validation results in section 5. Finally, section 6 concludes the paper.

CONVERTERS, HARMONICS AND PHASES

A very popular test for data converters relies on spectral analysis. It is usually implemented in a DSP-based test architecture [START_REF] Mahoney | DSP-Based Testing of Analog and Mixed-Signal Circuits[END_REF][START_REF]IEEE standard for terminology and test methods for analog-to-digital converters[END_REF]. Basically, a single tone sine-wave stimulus is sourced to the converter input, and then an FFT analysis is performed on the output sample set. The resulting spectrum is subsequently processed to compute the dynamic parameters such as the Total Harmonic Distortion (THD) or the Spurious Free Dynamic Range (SFDR). The spectrum also permits to estimate an essential static parameter, i.e. the Integral Non Linearity (INL), using the method proposed in [START_REF] Janik | A Spectral approach to estimate the INL of A/D converter[END_REF].

A typical spectrum considering an ADC driven by an ideal sine-wave at frequency f 0 is illustrated in figure 1. This spectrum exhibits a fundamental bin at f 0 , the harmonic components being located at multiple values of the fundamental frequency, and noise at other frequencies. The fundamental component corresponds to the input sine-wave while other components are induced by the converter non-idealities.

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ * = ) max( log 20 ) ( 10 k H F dB SFDR ( 2
)
where F is the amplitude of the fundamental and H k the amplitude of the k th harmonic.

To introduce the theoretical fundamentals, let us consider an ideal sine-wave applied to an ADC. Using a Fourier series expansion, the output signal can be expressed by equation (3. This equation distinguishes the sampled sine-wave x(n) that would be delivered by an ideal ADC from the sum of all harmonic contributions introduced by the converter non-idealities. Hence H 0 corresponds to the offset contribution of the converter and H 1 corresponds to the contribution of the gain error and non linearity of the converter. The total amplitude of the fundamental component, previously defined as F, is the sum of H 1 and the contribution of the ideal ADC, which is included in x(n) in equation ( 3):

( ) ( ) ( ) (
) ( )

∑ ≥ + + + + = 0 cos k k i n k n k H n x n s ε θ θ θ (3)
where n is the sample index, θ i the input phase, θ k the phase of the k th harmonic, ε( ) the noise that affect the converted signal, and θ n the nominal sampling phase given by:

n N M n π θ 2 = (4)
where N is the number of samples and M the number of cycles (i.e. signal periods) in the sample set.

The theoretical developments that mathematically link the harmonic components to the converter INL are given in [START_REF] Janik | A Spectral approach to estimate the INL of A/D converter[END_REF]. The expression of the output signal can be easily linked to the spectrum presented in figure 1 by developing equation (3):

( ) ( ) ( ) ( ) ( ) ( ) ∑ ≥ + + - + + = 0 ) sin( sin ) cos( cos k n k i k n k i k n k k H k k H n x (π θ θ i k k = (6)
and by setting the input phase θ i to zero, equation (5) becomes:

( ) ( ) ( ) ( ) ∑ ≥ + + = 0 cos k n k n k H n x n s ε θ (7)
In this case, the imaginary part of the spectrum is cancelled and only the real part of the spectrum directly corresponds to the amplitude of the spectrum.

However if we consider the case of a converter with harmonics' phase not correlated to the input phase, setting the input phase θ i to zero leads to:

( ) ( ) ( ) ( ) ( ) ( ) ∑ ≥ + - + = 0 sin ) sin( cos ) cos( k n k k n k k n k H k H n x n s ε θ θ θ θ (8)
In this case, it clearly appears that both the real and the imaginary parts of the spectrum have to be considered and used in the computation of the dynamic parameters.

ANC FUNDAMENTAL PRINCIPLE

The Analogue Network of Converters, presented in [START_REF] Kerzérho | Analogue Network of Converters": a DFT Technique to Test a Complete Set of ADCs and DACs Embedded in a Complex SiP or SOC[END_REF], is a DfT concept developed to enable the fully digital test of a set of DACs and ADCs embedded in a complex system. It can also be used to relax the requirements on the test equipment in case of stand-alone converter testing [START_REF] Kerzérho | ADC Production Test Technique Using Low-Resolution Arbitrary Waveform Generator[END_REF].

In the ANC-based method, the analogue outputs of the DACs are basically connected to the analogue inputs of the ADCs so that only digital test resources are required to apply the test stimuli and capture the test responses. Similarly to a classical DSPbased test, single-tone sine-waves are used as test stimuli and the test response analysis is based on the FFT computation of the captured output samples. The method addresses networks embedding several ADCs and DACs, and is even more efficient as the number of tested converters increases. As illustrated in figure 2, the method requires at least two DACs and one ADC. The idea is then to exploit different configurations and different test conditions in order to separate the harmonic contribution of each converter. Switches enable to connect any DAC output (I i ) or combination of DAC outputs to any ADC input (O i ). The mathematical developments were established considering only static non-idealities of the converters, meaning that the harmonics' phase of each converter was not taken into account. In this case, the model presented in equation ( 3) simplifies and becomes:

( ) ( ) ( ) ( ) ( ) ∑ ≥ + + + = 0 cos k i n k n k H n x n s ε θ θ (9)
We are therefore in the situation where setting the initial phase θ i to zero results in the cancellation of the imaginary part of the spectrum, and the real part directly leads to the amplitude of the spectrum.

To illustrate the method, let us first consider a test configuration where the DAC1 output is directly connected to the ADC1 input (Fig. 3). The spectrum of the resulting output signal is computed and the values of the harmonic components H k m,1 are extracted. Obviously, the output signal is affected by errors of both converters. In other words, the resulting spectrum includes the harmonic contribution of DAC1 as well as the harmonic contribution of ADC1. According to equation ( 9), setting a zero initial phase shift, we can write the following equation:

FS k FS k m k Hadc1 Hdac1 H + = 1 , (10)
where Hdac1 k FS and Hadc1 k FS correspond to the amplitude of the k th harmonic of DAC1 and ADC1 respectively, for a full-scale input signal (FS).

Equation [START_REF] Burns | An Introduction to mixed-signal IC test and measurement[END_REF] establishes a relation between the harmonic contributions of the two converters involved in the test configuration. In this equation, the left member is known and corresponds to the amplitude of the k th spectral bin measured on the spectrum, while the right member corresponds to the unknowns under calculation.

This short example demonstrates the relationship between one configuration and its resulting equation, which leads to the fundamental idea of the ANC-based method. By using different configurations, we can establish different equations. The objective is then to determine the adequate set of configurations that results in a system of independent equations, which can be solved to discriminate the harmonic contribution of each converter. We have identified 3 different configurations (DAC1/ADC1, DAC2/ADC1 and DAC1+DAC2/ADC1) associated with 4 different test conditions (related to amplitude and phase of test stimuli) that permit to obtain a system of five independent equations:

2 / 5 , 2 / 2 / 4 , 2 / 2 / 3 , 2 , 1 , π ϕ π ϕ ϕ ϕ π k Hadc1 k Hdac2 Hdac1 H Hadc1 k Hdac2 Hdac1 H Hadc1 Hdac2 H Hadc1 Hdac2 H Hadc1 Hdac1 H FS k FS k FS k m k FS k FS k FS k m k FS k FS k m k FS k FS k m k FS k FS k m k
The different configurations and conditions will be presented in the next section. Solving this system permits to compute the amplitude of the harmonic components, for each individual converter.

EXTENSION OF THE ANC-BASED METHOD

A limitation of the ANC-based method described in the previous section is that the phase of the harmonics is not taken into account in the mathematical developments. However, the method was proven efficient in practical experimentations with real-life converters [START_REF] Kerzérho | A novel DFT technique to test a complete set of ADC's and DAC's embedded in a complex SiP[END_REF]. This can be explained by the fact that in all experiments, the converters under study exhibited a phase of harmonics linearly proportional to the input signal nominal phase. In such a situation, when setting the input signal nominal phase to zero, the imaginary part of the spectrum is cancelled and the real part directly gives the amplitude in the spectrum. The system of equations established from the model given by equation ( 9) is therefore valid and leads to a correct estimation of the harmonic contribution of each individual converter. However the assumption that the harmonics' phase is linearly proportional to the input signal nominal phase is not always verified and highly depends on the converter architecture. We have seen that this assumption is often verified for types of architecture that use a sample and hold stage, but it cannot be assessed for other architectures where filtering and noise may affect the harmonics' phase. Our objective is consequently to improve the ANC-based method to cover all the real-life cases.

The fundamental principle of this improved version of the ANC-based method is the same, but the mathematical developments have now to be established using the complete model of the general case, i.e. the model described by equation (3).

4.1.

First configuration: 1 DAC connected to 1 ADC Let us consider again the configuration in which the DAC1 output is directly connected to the ADC1 input (Fig. 3). The signal applied on the DAC input covers the full scale of the converters. This configuration constitutes the first step of the ANC method. Obviously, the output signal is still affected by errors of both converters. The spectrum of the resulting output signal is computed and the values of the harmonic components H k m,1 are extracted. Now, considering the general case described in equation

(3) and setting the input signal nominal phase θ i to zero, we can write the following equations:

( ) ( ) ( ) ( ) ⎪ ⎩ ⎪ ⎨ ⎧ - - = + = FS k adc1 FS k FS k dac1 FS k m k FS k adc1 FS k FS k dac1 FS k m k Hadc1 Hdac1 H Hadc1 Hdac1 H , , 1 , , , 1 , sin sin
) Im( cos cos ) Re( θ θ θ θ (11)
In the second step, the test path goes through DAC2 and ADC1 (Fig. 4). The amplitude of the test signal still reaches the full scale of the converters. Therefore, we obtain a second couple of equations given by [START_REF] Kerzérho | Analogue Network of Converters": a DFT Technique to Test a Complete Set of ADCs and DACs Embedded in a Complex SiP or SOC[END_REF], where H k m,2 is the amplitude of the k th harmonic measured on the ADC output. We can now play with the amplitude and phase of the input signal to establish new equations. The input signal phase has no influence on the converter harmonic contribution but the input signal amplitude A in modifies the converter harmonic contribution (Hdac1 k Ain ≠ Hdac1 k FS if A in ≠ FS). No trivial relationship exists between these different harmonic contributions. Consequently, the use of different amplitudes induces additional unknown parameters. Nevertheless, it also introduces new test setup possibilities that can be exploited to get additional independent useful information.

) ( ) ( ) ( ) ⎪ ⎩ ⎪ ⎨ ⎧ - - = + = FS k adc1 FS k FS k dac FS k m k FS k adc1 FS k FS k dac FS k m k Hadc1 Hdac H Hadc1 Hdac H , , 2 2 ,
Practically, we have looked for a system of equations that allows the discrimination of the three converter harmonic contributions using test stimuli with amplitude at full-scale and amplitude at half-scale.

The new third equation is the result of a test at half-scale through DAC2 and ADC1 (Fig. 5). The measured harmonics are the sum of DAC2 and ADC1 harmonic contributions for an input signal at half-scale. At this point, we therefore have ten unknown parameters and only six equations (11-13) from three acquisitions. It would obviously be vain to apply new test conditions with different input signal amplitudes in the same test configuration. To avoid this problem, the two DAC's outputs are added to establish a new configuration. This new configuration is described in the next section.

( ) ( ) ( ) ( ) ⎪ ⎩ ⎪ ⎨ ⎧ - - = + = 2 / , 2 / 2 / ,

4.2.

Second configuration: 2 DACs connected to 1 ADC The second hardware configuration is made up of two DACs and one ADC. The input of the ADC is the sum of the two DAC outputs. Note that a similar test configuration has already been described in [START_REF] Jiang | Dither Incorporated Deterministic Dynamic Element Matching for High Resolution ADC Test Using Extremely Low Resolution DACs[END_REF]. But in this case, the objective was to test only the ADC, the DACs having a higher resolution than the one of the ADC under test. This is not the case in our method, which permits to test an ADC using DACs of similar or even lower resolution as demonstrated in [START_REF] Kerzérho | ADC Production Test Technique Using Low-Resolution Arbitrary Waveform Generator[END_REF].

For the sake of simplicity, let us consider three converters with same resolution and dynamic range. Obviously, we cannot use the sum of two full-scale and in-phase signals from DAC1 and DAC2, because it would result in a signal with an amplitude of twice the converters' full-scale and would saturate the ADC. The solution to overcome this problem is to play with amplitude and phase shift of the input signals to result in a sum signal that remains within the full scale of the ADC.

Practically, the 4 th test setup involves a full-scale input signal on DAC1 and a half-scale input signal on DAC2 with a π phase shift (Fig. 6). The resulting signal at the ADC input is a sine-wave at half-scale: The resulting couple of equations is the sum of the harmonic contribution at full scale of DAC1, the harmonic contribution at half-scale of DAC2 balanced by the phase shift and the harmonic contribution at ½ full-scale of ADC1.

( ) ( ) 2 ) cos( 2 ) cos( cos 2 ) cos( cos x x x x x = - = + + π (14)
( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) ( ) [ ] 2
FS k adc1 FS k FS k dac2 FS k FS k dac1 FS k m k FS k adc1 FS k FS k dac2 FS k FS k dac1 FS k m k Hadc1 k Hdac2 Hdac1 H Hadc1 k Hdac2 Hdac1 H θ θ π θ θ θ π θ + + - = + + = (15)
The 5 th required test setup is very similar to the previous one. The input amplitudes are the same as before but they are relatively phase shifted of 1 ϕ . The resulting signal at the ADC input is now a sine-wave at full-scale with a phase shift of 2 ϕ . The 5 th couple of equations then corresponds to the sum of the harmonic contributions balanced by their phase shifts:

( ) ( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) [ ] [ ] ( ) ( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) [ ] [ ] FS k adc1 FS k adc1 FS k FS k dac2 FS k dac2 FS k FS k dac1 FS k m k FS k adc1 FS k adc1 FS k FS k dac2 FS k dac2 FS k FS k dac1 FS k m k k k Hadc1 k k Hdac2 Hdac1 H k k Hadc1 k k Hdac2 Hdac1 H , 2 , 2 2 / ,
+ + + + - = - + - + = (18)
In summary, the proposed test strategy is composed of five successive tests. Each test consists in an acquisition and a spectral analysis (with Fast Fourier Transform) to evaluate harmonic bins. We obtain a system of 10 independent equations for each harmonic bin given hereafter. This system can be solved to determine the real and imaginary parts of harmonic contribution related to the different converters. From this, the dynamic parameters such as THD and SFDR can be computed for each converter. Solving this system of equations therefore makes the independent characterization of each converter possible.

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) [ ] [ ] ( ) ( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) [ ] [ ]
FS k adc1 FS k adc1 FS k FS k dac2 FS k dac2 FS k FS k dac1 FS k m k FS k adc1 FS k adc1 FS k FS k dac2 FS k dac2 FS k FS k dac1 FS k m k FS k adc1 FS k FS k dac2 FS k FS k dac1 FS k m k FS k adc1 FS k FS k dac2 FS k FS k dac1 FS k m k FS k adc1 FS k FS k dac2 FS k m k FS k adc1 FS k FS k dac2 FS k m k FS k adc1 FS k FS k dac2 FS k m k FS k adc1 FS k FS k dac2 FS k m k FS k adc1 FS k FS k dac1 FS k m k FS k adc1 FS k FS k dac1 FS k m k k k Hadc1 k k Hdac2 Hdac1 H k k Hadc1 k k Hdac2

4.3.

Further configurations to test additional converters Thanks to the converter characterization obtained from the second configuration, testing every additional converter embedded in the same complex chip is straightforward. For that, we can use one of the three previously characterized converters as a measurement instrument with non-ideal, but known, specifications.

The test time directly depends on the number of required captures. The first step of the test procedure needs five captures to test three devices. Then the new test configuration is achieved by connecting one converter to an previously characterized converter. Doing that, and considering [START_REF] Huertas | Test and design-for-testability in mixed-signal integrated circuits[END_REF], only one couple of variables is unknown: the harmonic contribution of the uncharacterized converter (amplitude and phase). As a consequence we need only one additional acquisition to test this converter. So, the number of acquisitions for a complex chip with n DACs and m ADCs is only of n+m+2 acquisitions without any external analogue equipment requirement.

Moreover, because the test stimulus application and the test response capture are performed using only digital ATE resources, it is possible to concurrently test several converters. Consequently, after the first step, each new step could use simultaneously all available characterized converters as measurement instruments. In this configuration, the test time could be drastically shortened.

VALIDATION

The theoretical extension of the ANC-based test method has been validated through simulation, using the converter model described in [START_REF] Kerzérho | Analogue Network of Converters": a DFT Technique to Test a Complete Set of ADCs and DACs Embedded in a Complex SiP or SOC[END_REF]. Converter non-idealities are included in the model based on real-life INL values extracted from measurements on several data converters. Sampling jitter and thermal noise are also considered. In addition, we also include a possible injection of an arbitrary phase shift on the converter harmonics.

5.1.

Data converter model To simulate the test strategy, we need to establish a model that takes into account the effects of the converter nonidealities. Three main sources of errors will be considered, i.e. the sampling jitter of the converter, the non-linearities of its transfer function and the thermal noise.

Let us consider an input sine-wave sourced to an ideal converter. This sampled signal can be expressed (in LSB unit) by: ( ) ( )

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = FS DC N n FS N V V V V n x 2 cos 2 0 0 θ θ (19)
where N and V FS respectively represent the number of bits and the full-scale voltage of the converter, V 0 and V DC respectively correspond to the amplitude and the DC component of the input sine-wave, and θ 0 and θ n are respectively the initial and nominal sampling phase of the signal. The nominal sampling phase is given by:

n M P n ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = π θ 2 (20)
where M is the number of samples and P the number of periods in the record.

Let us now introduce the sampling jitter of the converter. Essentially, it is a phase noise that changes the ideal sampling time. The resulting deteriorated signal is given by: ( ) ( )

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + + + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = FS DC N t n FS N V V J V V n r 2 cos 2 0 0 θ θ (21) where t t f J δ π 0 2 =
, with f 0 the frequency of the input signal and t δ a centred Gaussian noise. According to [4] and thanks to a Taylor series development, the jitter contribution can be separated from the input signal expression in (21). Finally, considering an additional thermal noise we obtain the following expression:

( ) ( ) ( ) n n x n r ε + = (22)
where ε(n) is the sum of the noise induced by the sampling jitter and the thermal noise (N Th ). The thermal noise is usually modelled by a centred Gaussian noise.

( ) ( ) Th n t FS N N J V V n + + = 0 0 sin 2 θ θ ε (23)
The second significant source of errors that has to be considered is the non-linearity of the converter transfer function. A common approach to analytically model the converter INL is based on polynomial approximation [START_REF] Sunter | A simplified polynomial-fitting algorithm for DAC and ADC BIST[END_REF][START_REF] Janik | Estimation of A/D Converter Nonlinearities from complex Spectrum[END_REF][START_REF] Adamo | FFT Test of A/D Converters to Determine the Integral Nonlinearity[END_REF]. However, such modelling does not permit to describe the sharp transitions usually encountered for actual INL. In order to alleviate this drawback, we choose a different approach which consists in using "true" INL curves extracted from measurements on real data converters.

Consequently, let us consider s(n) the signal deteriorated by the two types of errors:

( ) [ ] )]) ( ([ ) ( n r INL n r n s + = (24)
where INL(x) is a non-linearity curve measured through histogram testing of a real converter. This non-linearity curve is indexed by the rounded signal [r(n)], including the sampling jitter effect. The complete equation is rounded to model the quantization effect.

Equation ( 24) is the equation that models the deterioration of a sine-wave signal passing through a converter affected by sampling jitter, transfer function non-linearities and thermal noise. In addition, an individual phase shift can be introduced on each harmonic individually. This equation has been used for the simulations described in the following sections.

5.2.

Validation of the extended method improvement with random phase harmonics In order to validate the improved ANC-based method, we have considered a set of three converters, i.e. two DACs and one ADC. First, we have simulated each data converter in a stand-alone configuration applying a single-tone sine-wave stimulus to the converter input and performing an FFT analysis on the converter output. This corresponds to the usual DSPbased test and is used to get reference values for the THD and SFDR parameters. Then, we have simulated the set of converters in the different configurations and test conditions defined in the ANC-based method. Here again single-tone sinewaves are used as test stimuli and an FFT is performed on the captured output samples. From these five acquisitions, we have established the system of independent equations that links the measured harmonic contribution to the individual harmonic contribution of each converter (considering only the real part of the spectrum for the original ANC-based method and both the real and imaginary parts of the spectrum for the improved ANC-based method) and we have solved the system. Finally, we have computed the THD and SFDR parameters using the estimated amplitude of the harmonic components.

Results are summarized in Tables I to IV, which compare the values of the THD and SFDR parameters computed using the stand-alone configuration to the values of the THD and SFDR parameters computed using either the original or the improved ANC-based method, with and without phase shift injected on the converters' harmonics. Analyzing these results, it can be seen that when the converters' harmonics are not affected by a random phase shift, both the original and the improved versions of the ANC-based method produce an accurate measurement of the THD and SFDR parameters, with an estimation error that remains below 0.7dB. However when the converters' harmonics are affected by a random phase shift, the performances of the original ANC-based method degrades with an estimation error that increases up to 4.3dB for the THD parameter of DAC1. In contrast, the improved ANC-based method gives very accurate measurements, with an estimation error lower than 0.2dB. These results clearly validate the efficiency of the improved ANC-based method.

5.3.

Validation in a realistic case The purpose of this validation is to get as close as possible to a realistic case. Let us consider a circuit made of a DAC and a low-pass filter. In case of the impossibility to bypass the filter in the test path, the DAC/filter chain should be tested as one single component. An obvious solution to estimate the harmonic distortions induced by the DAC is to choose the frequency of the test signal in the bandwidth of the filter. Although the presence of the filter has no influence on the amplitude of the inband signals, it introduces a group delay that can induce some significant phase delays to the resulting signals. This situation is similar to the one addressed by the algorithm previously described. We have a test stimulus, i.e. a sine-wave, affected by harmonics induced by a DAC. The phases of these harmonics are not proportional anymore to the stimulus phase because of the filter.

This case has been simulated considering a 12bit DAC, a 2 nd order Bessel filter with a cut-off frequency at 30MHz (Fig. 7), and a test frequency of 4.43MHz. The test configuration is made of two DACs with different non-linearities, followed by a filter. The filter outputs are summed and the result is sent to an ADC (Fig. 8), with no phase delays added. Simulation results are provided in Tables V and VI. Although the low pass filters introduce phase shifts on the test path, it can be seen that the improved ANC method permits good characterization of DACs with an estimation error below 0.8dB, whereas the original ANC method presents an estimation error ranging from 1.5dB to 2.4dB. Concerning the ADC, we observed similar results with both the original and improved versions of the method.

Wide range validation

The purpose of this second simulation set is to validate the approach not only for DACs but also for ADCs and for a wide range of phase variations.

Considering the basic test configuration described in 5.2, made of two DACs and one ADC, we modified the converter models to introduce random phase delays on the harmonics generated by the converters' non linearities. We ran 400 simulations using different phases for each harmonic of each converter. The phases were randomly chosen following a normal distribution. Figure 9 presents the histogram of the phases chosen for the harmonic 2 of DAC2 as an illustration. The standard deviation is π/6. For each simulation, the THD and SFDR were estimated using both the original and improved ANC algorithms.

Figure 1 .

 1 Figure 1. Output spectrum of an ADC under an ideal sine-wave stimulus

Figure 2 .

 2 Figure 2. Analog Network of Converters (ANC) concept

Figure 3 .

 3 Figure 3. First test configuration, first test setup

Figure 4 .

 4 Figure 4. First test configuration, second test setup

(

Figure 5 .

 5 Figure 5. First test configuration, third test setup

Figure 6 .

 6 Figure 6. Second test configuration, fourth test setup

Figure 7 .

 7 Figure 7. Bode plot of Bessel low-pass filter

Figure 8 .

 8 Figure 8. Simulated test configuration

Figure 9 .

 9 Figure 9. Histogram of phase variations applied to harmonic 2 of DAC2

Figure 1 :FSFigure 3 :

 13 Figure 1: Output spectrum of an ADC under an ideal sine-wave stimulus

Figure 5 :

 5 Figure 5: First test configuration, third test setup

Figure 6 :

 6 Figure 6: Second test configuration, fourth test setup

Figure 7 :Figure 9 :Figure 11 :

 7911 Figure 7: Bessel low-pass filter Bode plot

TABLE I .

 I THD VALUES AND ESTIMATION ERRORS WITHOUT PHASE SHIFT ON CONVERTERS' HARMONICS

TABLE II .

 II SFDR VALUES AND ESTIMATION ERRORS WITHOUT PHASE SHIFT ON CONVERTERS' HARMONICS

TABLE III .

 III THD VALUES AND ESTIMATION ERRORS WITH A RANDOM PHASE SHIFT INJECTED ON CONVERTERS' HARMONICS

TABLE IV .

 IV SFDR VALUES AND ESTIMATION ERRORS WITH A RANDOM PHASE SHIFT INJECTED ON CONVERTERS' HARMONICS

TABLE V .

 V THD VALUES AND ESTIMATION ERRORS WITH PHASE SHIFT FROM LOW-PASS FILTER

TABLE VI .

 VI SFDR VALUES AND ESTIMATION ERRORS WITH PHASE SHIFT FROM LOW-PASS FILTER

TABLE I :

 I THD values and estimation errors without phase shift on converters' harmonics THD (dB)Estimation Error (dB)

		Reference	Original ANC	Improved ANC	Original ANC	Improved ANC
	DAC1	-77.9	-77.2	-77.3	0.7	0.6
	DAC2	-74.4	-74.1	-74.2	0.3	0.2
	ADC	-66.1	-65.8	-65.7	0.3	0.4
	TABLE II: SFDR values and estimation errors without phase shift on converters' harmonics
			SFDR (dB)		Estimation Error (dB)
		Reference	Original ANC	Improved ANC	Original ANC	Improved ANC
	DAC1	78.9	79.3	79.3	0.4	0.4
	DAC2	76.1	75.6	75.6	0.5	0.5
	ADC	70.5	69.8	69.8	0.7	0.7

TABLE III :

 III THD values and estimation errors with a random phase shift injected on converters' harmonics THD (dB)Estimation Error (dB)

		Reference	Original ANC	Improved ANC	Original ANC	Improved ANC
	DAC1	-77.9	-73.6	-77.7	4.3	0.2
	DAC2	-74.4	-73.2	-74.4	1.2	0.0
	ADC	-66.1	-67.0	-66.2	0.9	0.1

TABLE IV :

 IV SFDR values and estimation errors with a random phase shift injected on converters' harmonics

			SFDR (dB)		Estimation Error (dB)
		Reference	Original ANC	Improved ANC	Original ANC	Improved ANC
	DAC1	78.9	76.8	78.8	2.1	0.1
	DAC2	76.1	76.6	76.1	0.5	0.0
	ADC	70.5	68.5	70.4	2.0	0.1
	TABLE V: THD values and estimation errors with phase shift from low-pass filter
			THD (dB)		Estimation Error (dB)
		Reference	Original ANC	Improved ANC	Original ANC	Improved ANC
	DAC1	-82.4	-84.8	-81.6	2.4	0.8
	DAC2	-74.4	-76.4	-74.6	2.0	0.2
	ADC	-66.1	-65.9	-65.6	0.2	0.5
	TABLE VI: SFDR values and estimation errors with phase shift from low-pass filter
			SFDR (dB)		Estimation Error (dB)
		Reference	Original ANC	Improved ANC	Original ANC	Improved ANC
	DAC1	78.4	79.9	78.1	1.5	0.3
	DAC2	76.0	78.2	76.0	2.2	0.0
	ADC	70.4	69.9	69.7	0.5	0.7

from 5 to 10. However, it is worth noting that this computation is performed off-chip using the tester digital signal processing resources and has no impact on the cost of the test procedure. These developments therefore offer an efficient generic method to perform the harmonic characterization of a set of data converters using only digital external test equipment, without any assumption on the converter architecture and potential phase shift of the converter harmonics.

The improvement of the extension of the ANC-based method was validated through a number a simulations involving random phase shifts as well as realistic filter phase delays on the harmonic contributions.

Figure 10 presents the histogram of the 400 THD estimations for DAC2:

• using the original ANC method (light grey bars),

• using the improved version of ANC method (dark grey bars). The value of the THD, obtained with a usual test method in a stand-alone configuration, is referenced on the histogram (74.4dB).

Figure 10. Histogram of THD estimations with original and improved ANC methods for DAC2 Figure 11 presents the histogram of the 400 SFDR estimations for DAC2:

• using the original ANC method (light grey bars),

• using the improved version of ANC method (dark grey bars). The value of the SFDR, obtained with a usual test method in a stand-alone configuration, is referenced on the histogram (76.1dB). These histograms enable to give visual conclusions. The estimation of dynamic parameters follows a normal distribution as much as the phase delays distribution. The dynamic parameter estimations are far much spread and consequently the estimation errors are bigger with the original method than with the new version of the method. Following tables summarize the numerical results. Tables VII and VIII give respectively THD and SFDR estimations for the three converters. In order to have a clear overview of the measurement accuracy against random phase delays, the average, dispersion and maximum error are presented in the tables. The update of the method decreases the dispersion from the range [7.6, 13.1dB] to the range [1.0, 1.8dB] and the maximum error from [5.9, 9.0dB] to [0.6, 1.1dB]. In other words, in case of random phase delays of harmonic induced by tested converters, the updated ANC method ensures low estimation error. A maximum estimation error of 1dB is fully acceptable considering that industrial test repeatability is usually around 2dB.

We repeated the simulations with a higher standard deviation of π, to confirm the accuracy of the new method against phase delays. The simulation results are provided in Tables IX andX. Despite the increase of phase delays, we still have a significant decrease of dispersions and maximum errors: from range [8.4dB, 20.2dB] to range [0.8dB, 2.6dB] regarding dispersion and from range [6.2dB, 14.4dB] to range [0.5dB, 1.5dB] regarding maximum error. Considering a maximum error lower than 1.5dB, we can conclude that the method is still accurate with high amplitudes of random phase delays.

CONCLUSION

In this paper, we have presented an extension of the ANC-based method capable of handling converters with randomphase harmonics. Indeed, the ANC-based method was originally developed under the assumption that the harmonics' phase is proportional to the input phase. Although this assumption is often verified, it is not valid for all converter types of architecture. New mathematical developments based on a general model that includes the harmonics' phase of converters were therefore established. The efficiency of the improved ANC-based test was evaluated through simulations, demonstrating an excellent agreement between the THD and SFDR values measured with a usual test setup and the THD and SFDR values computed with the method.

Compared to the initial ANC-based test method, no additional resources are required, and the number of test configurations and test acquisitions remains the same. Only the size of the independent equations system is different, growing


Xu Li

Nathalie Mitton

Isabelle Simplot-Ryl

David Simplot-Ryl

Mobile-Beacon Assisted Sensor Localization with Dynamic Beacon Mobility Scheduling

Keywords: Mobility management, Mobile beacon, Sensor localization, Wireless sensor networks

In mobile-beacon assisted sensor localization, beacon mobility scheduling aims to determine the best beacon trajectory so that each sensor receives sufficient beacon signals with minimum delay. We propose a novel DeteRministic bEAcon Mobility Scheduling (DREAMS) algorithm, without requiring any prior knowledge of the sensory field. In this algorithm, beacon trajectory is defined as the track of depth-first traversal (DFT) of the network graph, thus deterministic. The mobile beacon performs DFT under the instruction of nearby sensors on the fly. It moves from sensor to sensor in an intelligent heuristic manner according to RSS (Received Signal Strength)-based distance measurements. We prove that DREAMS guarantees full localization (every sensor is localized) when the measurements are noise-free. Then we suggest to apply node elimination and topology control (Local Minimum Spanning Tree) to shorten beacon tour and reduce delay. Through simulation we show that DREAMS guarantees full localization even with noisy distance measurements. We evaluate its performance on localization delay and communication overhead in comparison with a previously proposed static path based scheduling method.

I. INTRODUCTION

A wireless sensor network (WSN) is a collection of lowcost sensing devices, i.e., sensors, connected by wireless communication links in an ad-hoc fashion. Usually, it is densely deployed in a region of interest for object monitoring and target tracking. In many high-level WSN applications, a reported event, e.g., a fire in a woody area, an enemy tank in a battle field and a survivor in a natural disaster, just to mention a few, is meaningful and can be responded to only if the event position is known. Location awareness also plays an important role in some low-level network functionalities such as geographic routing and data centric storage. Indeed, sensors are expected to know their positions for effective and efficient use of WSNs.

Localization is a fundamental problem dealing with how a sensor determines its spatial coordinates (i.e., position). A straightforward solution is to equip each sensor with a GPS receiver that can provide the sensor with its exact location. But this is not a cost-effective solution because WSN normally contains a massive number of sensors (thus requires a large amount of extra monetary investment). It has limited applicability because GPS works only in open areas with no obstruction to satellite signal (for example, they do not function in underwater or indoor environment), and in some hostile scenario such as battlefield surveillance, GPS signals may be jammed by adversaries and become unavailable to individual sensors unless the sensors are equipped with expensive GPS anti-jam protection techniques [START_REF]GPS Anti-Jam Protection[END_REF].

Existing non-GPS-based sensor localization algorithms can be classified as range-based or range-free [START_REF] Wang | A survey on sensor localization[END_REF]. Range-based localization relies on signal features such as Angle of Arrival (AoA), Time of Arrival (ToA), Time Difference of Arrival (TDoA), or Received Signal Strength (RSS) for ranging (i.e., finding nodal relative distance or angle). Unlocalized nodes use reference locations and the range information to estimate their own position by triangulation, trilateration or multilateration, depending on the signal feature used. The reference locations are called beacons. They are implemented by location-aware nodes emitting location signals. Rangefree localization uses topological information (e.g., hop count) rather than range information. It may or may not use beacons.

Localization that relies on AoA, ToA, or TDoA requires additional complex hardware and/or synchronized transmitters for the signal feature measurement and dramatically increases deployment cost. On the other hand, measuring RSS is free of cost because RSS Indicator (RSSI) is available with regular radio module. In range-free localization without use of beacons (thus any signal feature), nodes are localized in a virtual coordinate system that does not necessarily have direct relation with the ground truth. While virtual coordinates may be an acceptable replacement of physical coordinates for networking, they are less helpful to real life applications where true physical position is required for event response and decision making (e.g., emergency rescue and environment control).

Hence, considerable research attention has been attracted to beacon-assisted localization (whether range-based or rangefree) using RSS, for accuracy, efficiency and applicability concerns. Generally speaking, sensors infer their position from their spatial relations with the beacons in range, which are in turn estimated using RSS. To limit positioning possibilities in a minimal region (i.e., to increase localization accuracy), they should have direct contact with a sufficient number of beacons. The number of beacons and their distribution thus has direct impact on the localization performance. A large number of uniformly distributed beacons will lead to better performance than a few crawdedly or linearly deployed ones (which may result in symmetry in localization).

On the other hand, manual beacon placement may not be possible due to operational factors, and meanwhile the number of beacons should be significantly smaller than the number of sensors because, otherwise, beacon deployment cost will offset the savings on sensor side. Localized sensors can become new beacons and help other sensors self-localize. This iterative method reduces the initial number of beacons required but results in aggregated localization error. Under these circumstances, mobile beacons (wireless communicable devices such as mobile robots and unmanned vehicles) are introduced as alternative cost-saving technique in delay-tolerant scenarios. As we will see in this paper, if one or a few mobile beacons are used properly, full sensor localization guarantee can be achieved.

A. Objective and motivation

In this paper, we address mobile-beacon assisted sensor localization: a location-aware beacon travels in the sensory field, transmitting signals conveying their latest location on a periodic basis; on individual sensors, a localization algorithm is engaged during beacon visit. Some experimental work [START_REF] Caballero | A Particle Filtering method for Wireless Sensor Network Localization with an Aerial Robot Beacon[END_REF] has already demonstrated the feasibility and applicability of this approach in practice. In this approach, beacon transmission locations correspond to traditional fixed beacons. It is advantageous in terms of deployment cost (only a few beacon nodes are required) and communication overhead (only local communication is involved). These advantages however do not come for free, but in exchange for increased localization delay. It is because sensors can be localized only when they are in direct contact with the mobile beacon and receive sufficient signals from it. Beacon trajectory thus have to be properly planned so as to be shortest in length and meanwhile well cover every sensor for quick, full and accurate localization.

Our focus here is not on individual sensor localization but on beacon mobility scheduling, i.e., finding optimal beacon trajectory, which is a variant of the NP-complete Traveling Salesman Problem (TSP). A poor trajectory may result in not only large localization delay but also low localization ratio and high localization error. Due to random node dropping, sensors placement pattern is not known a priori. In a dynamic environment, even if the initial pattern was known, the final node distribution may be different (e.g., moved by wind or animals). Beacon trajectory thus should be planned on the fly rather than beforehand. In the literature, this problem is often purposefully overlooked, or oversimplified by unrealistic assumptions, due to its difficulty stemming from the fact that the position of unknown nodes is not known a priori [START_REF] Kushwaha | Sensor Node Localization Using Mobile Acoustic Beacons[END_REF]. To advance state of the art, we study dynamic beacon mobility scheduling in realistic settings. At individual sensor level may any existing localization procedure be adopted as long as it utilizes beacon signals for localization. Below is detailed problem statement.

B. Problem statement

We consider a connected static WSN randomly deployed in the Euclidean plane. The sensory field boundary is not known a priori. Sensors are initially unlocalized. A mobile beacons is stochastically placed in the network to localize sensors. It knows about its own coordinates in a coordination system (not necessarily geographic location) as it moves.

Nodes, whether sensors or beacon, are equipped with an omni-directional antenna. Sensors have the same transmission range; the beacon node has a transmission range not smaller than sensors'. Each node is associated with a unique identifier (ID), e.g., manufacturer serial number, by which it can be distinguished from others. Each sensor node (and beacon) periodically transmits 'hello' (resp., beacon) message carrying its ID (resp., current local position coordinates) and other information necessary for localization. 'Hello' frequency and beacon frequency may be different. Each sensor is equipped with a localization procedure, which can be any algorithm that relies on beacon signals.

The goal is to develop a beacon mobility scheduling algorithm, by which the mobile beacon is able to dynamically determine its trajectory and coordinate with one another such that every sensor receives sufficient beacon signals and becomes localized. The overall beacon mobility scheduling should yield minimum localization delay and minimum communication overhead. Note that here we consider only single-beacon scenario; multi-beacon scenario is part of our future work.

C. Our contributions

We propose a novel localized solution to the above stated problem, named DeteRministic bEAcon Mobility Scheduling (DREAMS). To our knowledge, DREAMS is the first algorithm of its kind. In the following we introduce its working principle and summarize our simulation study.

In DREAMS, the beacon node first visits a sensor by random movement, and then performs a depth-first traversal (DFT) on the network graph under currently visited sensor's instruction (a visited sensor, after being localized, recommends an unvisited neighbor for the beacon to visit next). It stops moving when it finds that it returns to the first sensor and the sensor has no unvisited neighbors. During DFT, the beacon node performs intelligent distance-based heuristic movement from sensor to sensor following RSS, and sensors run the built-in localization procedure to self-localize using received beacon signals. To shorten the beacon trajectory, DFT may be performed on a local minimum spanning tree (LMST) subgraph, where edges are weighted by RSS, and in addition, unvisited, but localized, sensors may be excluded from DFT if the exclusion does not affect discovery of unlocalized sensors.

We prove that DREAMS guarantees full localization with noise-free pair-wise distance measurement (which is used by beacons for heuristic inter-sensor movement). For the practical scenarios with measurement noise, we conducted extensive simulation study, in comparison with the fixed S-shape beacon trajectory proposal (referred to as StaticPath) [START_REF] Huang | Static Path Planning for Mobile Beacons to Localize Sensor Networks[END_REF]. Because both DREAMS and StaticPath are independent of the localization procedure on individual sensors, in simulation we chose to use trilateration for simplicity. We comparatively evaluate their performances on localization quality and localization delay with various configuration parameters. Our simulation results indicate that DREAMS is alway able to offer 100% localization ratio (full localization), while StaticPath has failure rate at 1.6%. For localized sensors, DREAMS has more than 4 times better localization accuracy than StaticPath. As expected, DREAMS however has larger localization delay, increasing as the network size goes up.

The remainder of the paper is organized as follows. We review previous work on mobile-beacon assisted sensor localization in Sec. II. We present our new algorithm DREAMS in Sec. III and evaluate its performance in Sec. IV. We concludes the paper and discuss our future work in Sec. V.

II. RELATED WORK

There exists a rich body of research on sensor localization. Due to space limit, we only review the previous works on mobile-beacon assisted approaches. A comprehensive survey covering other localization methods can be found in [START_REF] Wang | A survey on sensor localization[END_REF].

In [START_REF] Sichitiu | Localization of Wireless Sensor Networks with a Mobile Beacon[END_REF], a mobile beacon periodically transmits a beacon message containing its latest location. Any sensor receiving the message concludes that it must be somewhere around the beacon node with certain probability. For each received beacon message, the sensor obtains the RSSI and uses it together with the beacon location (embedded in the message) to construct a constraint on its own position estimate. Then it applies Bayesian inference to compute its new position estimate from its old position estimate and the new constraint. Its initial position estimate is set to an arbitrary point in the sensory field. Having received all beacon messages, the sensor is localized to a weighted average of these position estimates. In [START_REF] Kushwaha | Sensor Node Localization Using Mobile Acoustic Beacons[END_REF], the sensor localization problem is modeled as a non-linear optimization problem, where node locations are to be optimized. The nonlinear objective functions are the differences between pair-wise distances computed from sensor location estimates and range measurements (ToA based). This functionfitting problem is solved using the least square method, which requires an initial guess for the sensor positions. The quality of the initial guess has direct impact on the (convergence) performance of the algorithm. To mitigate this dependence, an iterative incremental approach is suggested. Node location estimates are improved in each iteration. Mobile beacons are used to transform relative positions to absolute locations.

Filtering is a signal processing technique that removes from a signal unwanted component (noise). It has been widely applied in different domains such as image processing and robotics, and is recently adopted for mobile-beacon assisted sensor localization. The idea is to model localization as an online estimation in a non-linear dynamic system and estimate the system state (i.e., sensor location) using range information obtained from filtered wireless signal features. In [START_REF] Pathirana | Node Localization Using Mobile Robots in Delay-Tolerant Sensor Networks[END_REF], [START_REF] Zhang | A Novel Distributed Sensor Positioning System Using the Dual of Target Tracking[END_REF], robust Extended Kalman Filter and unscented Kalman filter are respectively used with RSS as system measurements. In [START_REF] Pathirana | Node Localization Using Mobile Robots in Delay-Tolerant Sensor Networks[END_REF], the filter is installed on the beacon node that receives periodical signal from sensors, and localization results are passed to sensors by local communication. In [START_REF] Zhang | A Novel Distributed Sensor Positioning System Using the Dual of Target Tracking[END_REF], the mobile beacon periodically transmits signal to sensors, and the latter run the filter to localize themselves. In [START_REF] Huang | Monte Carlo localization of wireless sensor networks with a single mobile beacon[END_REF], Monte Carlo sampling-based Bayesian filtering is employed with various types of observations such as ranging, AoA, connectivity and their combinations. The filter is run on the beacon node. In [START_REF] Caballero | A Particle Filtering method for Wireless Sensor Network Localization with an Aerial Robot Beacon[END_REF], [START_REF] Teng | Adapting Mobile Beacon-Assisted Localization in Wireless Sensor Networks[END_REF], a particle filter solution is presented. In [START_REF] Teng | Adapting Mobile Beacon-Assisted Localization in Wireless Sensor Networks[END_REF], the authors proposed to increase filtering efficiency and accuracy by varying the size of sample sets and the parameter of the dynamic model in the estimation process.

In all above mentioned algorithms, beacon mobility scheduling was not studied. Few existing works [START_REF] Kim | MBAL: A Mobile Beacon-Assisted Localization Scheme for Wireless Sensor Networks[END_REF], [START_REF] Xiao | A Walking Beacon-Assisted Localization in Wireless Sensor Networks[END_REF] addressed this problem under strong assumptions. In [START_REF] Kim | MBAL: A Mobile Beacon-Assisted Localization Scheme for Wireless Sensor Networks[END_REF], accurate (noisefree) pair-wise distance measurements are assumed, and localization is by trilateration (requiring three non-collinear reference locations). The idea of mobility scheduling is to provide sensors with reference locations in preferred regions upon their request. It is not clear how the beacon will move when no request is received, while some remote area remains unlocalized. Localization is thus not guaranteed. In [START_REF] Xiao | A Walking Beacon-Assisted Localization in Wireless Sensor Networks[END_REF], the sensory field is known a priori, and unrealistic binary communication model is implicitly used. Two algorithms were presented, respectively using beacon departure/arrival and variance of RSS. Pre-defined 'S' shape trajectory spanning the entire sensory field is suggested to support the two algorithms. In [START_REF] Huang | Static Path Planning for Mobile Beacons to Localize Sensor Networks[END_REF], [START_REF] Koutsonikolas | Path Planning of Mobile Landmarks for Localization in Wireless Sensor Networks[END_REF], other types of fixed trajectories are suggested under the assumption of known sensory field boundary. In [START_REF] Kanchi | Robot assisted localization of sensor networks guided by rigidity[END_REF], [START_REF] Priyantha | Mobile-Assisted Localization in Wireless Sensor Networks[END_REF], the beacon node first collects the topology information of the network, then with this global view, it identifies the areas where additional distance measures are needed so that in the end the whole network becomes a globally rigid region and is thus localizable by a range-free algorithm. The authors did not address how to physically identify a target area and move the beacon node to that area without position information.

Summarizing, mobile-beacon assisted sensor localization is not well studied. In particular, there is no real solution to the integral beacon mobility scheduling problem, which is our focus here. We propose a novel localized mobility scheduling algorithm, called DREAMS, advancing the literature one step forward. DREAMS dynamically determines beacon trajectory and guarantees full localization, without any prior knowledge of the sensory field boundary. It is a generic framework that can be incorporated with any existing localization algorithm that relies on beacon signals to solve the mobile-beacon assisted sensor localization problem in a complete sense.

III. BEACON MOBILITY SCHEDULING

In this section, we propose a novel DeteRministic bEAcon Mobility Scheduling (DREAMS) algorithm, by which a mobile beacon R is able to visit every sensor and provide it with sufficient beacon signals and as a result a fully localized network is guaranteed. This algorithm is deterministic in the sense that sensors' visiting order is fixed provided R starts from the same sensor.

A. The framework (depth-first traversal)

The framework of DREAMS is a process of depth-first traversal (DFT) of the network graph, where R follows instructions (embedded in 'hello' message) from neighboring sensors and corresponding RSS. Throughout the DFT, R periodically transmits beacon message, while sensors self-localize using received beacon signals.

At initiation, R moves randomly and tries to find an adjacent sensor by listening to 'hello' message. The first sensor discovered is called root. It is the sensor that R starts the DFT from, and will be the root of the resultant traversal tree. When multiple sensors are discovered together, sensor ID or RSS can be used as tie breaker. A target sensor is a sensor that R is currently moving to. A sensor is visited if it has been taken by R as target, and unvisited otherwise. The first target of R is the root sensor. R notifies its current target sensor by beacon message so that the latter is able to identify its own status (whether serving as target or not).

When a sensor S is serving as the target of R, it selects as child an unvisited neighboring node S with strongest RSS. A random selection can be alternatively made, or preference can be given to a neighbor with high priority, which can be evaluated, for example, by the importance/intensity of its detected event (embedded in 'hello' message). By 'hello' message, S recommends S to R as next target; by the same message, it informs S about their parent-child relationship. If S has no unvisited neighbors, it will recommend its parent (which has already been localized) to R. In the case that S has no parent either (i.e., it is the root node), it informs R about this situation. R finishes the DFT, in other words, DREAMS terminates, when it realizes that its target sensor is localized and neighboring no unlocalized sensors and has no parent.

During the DFT, R proceeds toward each target sensor S by heuristic movement (see Sec. III-B for detail) if S is not yet localized. While R is performing this movement, S estimates its own location by the sensor localization procedure and informs R of the result. Once R is informed that S becomes localized, it stops the heuristic movement, moves straight toward S and becomes ready to change target. It changes target to the recommended S immediately if S is localized already (in this case, S is the parent of S), and otherwise as soon as it receives 'hello' message from S . Then it notifies S about the change via beacon message.

In the case that R has not received signal from S after arriving at the estimated location of S, it knows that the location estimate of S is not accurate enough and informs S about the inaccuracy. After that, it resumes the heuristic movement toward S, which will lead it either infinitely closer to the true location of S or moving around S (as discussed in Sec. III-B), and eventually discover S . In this recovery heuristic movement process, R notifies S to update location estimate directly with the reported beacon location if it reaches a position closer to S.

B. Distance-based heuristic movement

Central to the above DFT framework is the heuristic movement of R toward its target sensor S. The heuristic movement relies on the measurement of relative distance of R and S. It is implemented by a sequence of effective movement procedures (EMP), each in turn consists of a few movement steps and moves R to a position closer to S, without resorting to the position information (whether exact or approximate) of S. In the following, we present EMP first with noise-free distance measurement and then with noisy measurement.

1) Noise-free distance measurement: Before we elaborate on EMP, we introduce the following theorem that serves as the foundation of EMP.

(∠cba) > 1 4 , then |ac| < |ab|. 2) If cos(∠cba) < -1 4 , then |ad| < |ab|. 3) If -1 4 ≤ cos(∠cba) ≤ 1 4 , then |ae|, |af | < |ab|. Proof: For ease of presentation, let x = |ab|, α 1 = ∠cba, β 1 = ∠acb, ϑ 1 = ∠eca (∠ace in Fig. 1(a)), y 1 = |ac|, z 1 = |ae|, α 2 = ∠abd, β 2 = ∠bda, ϑ 2 = ∠adf (∠f da in Fig. 1(b)), y 2 = |ad|, z 2 = |af |. Then α 1 + α 2 = π, β 1 + ϑ 1 = 1 2 π and β 2 + ϑ 2 = 1 2 π. Further, define t 1 = 5 4 -cos α 1 and t 2 = 5 4 -cos α 2 .
In ∆abc and ∆abd, by the law of cosines we respectively have

y 2 1 = x 2 + ( x 2 ) 2 -2x( x 2 ) cos α 1 = x 2 t 1 (1)
y 2 2 = x 2 + ( x 2 ) 2 -2x( x 2 ) cos α 2 = x 2 t 2 (2)
Apparently, if cos α 1 > 1 4 , then 0 ≤ t 1 < 1 and y 1 < x; if cos α 1 < - 1 4 , then cos α 2 > 1 4 and 0 ≤ t 2 < 1 and thus y 2 < x. We remain to show y 1 < x and y 2 < x for -1 4 ≤ cos α 1 ≤ 1 4 . Notice that under this condition we have

1 ≤ t 1 , t 2 ≤ 3 2 .
In ∆abc we have

x 2 = y 2 1 + ( x 2 ) 2 -2y 1 ( x 2 ) cos β 1 = y 2 1 + x 2
4 -xy 1 cos β 1 by the law of cosines. Then through simple transformation, cos β 1 is expressed as

cos β 1 = y 1 x - 3x 4y 1 . (3)
Take square root at both sides of Eqn. ( 1) and plug it in Eqn.

(3). We obtain

cos β 1 = √ t 1 - 3 4 √ t 1 . (4)
We know cos ϑ 1 = 1 -(sin ϑ 1 ) 2 and sin ϑ 1 = sin( π 2β 1 ) = cos β 1 . Using Eqn. (4), we have

cos ϑ 1 = 1 -( √ t 1 - 3 4 √ t 1 ) 2 (5)
In ∆abe, according to the law of cosines and by Eqn. ( 1) and ( 5) we have

z 2 1 = x 2 t 1 ( 5 4 -1 -( √ t 1 - 3 4 √ t 1 ) 2 ). ( 6
)
Our goal is to prove z 1 < x. It is equivalent to prove z 2 1 -

x 2 = x 2 ( 5 4 t 1 -1 -t 1 1 -( √ t 1 -3 4 √ t1 )
2 ) < 0, which holds if and only if

5 4 t 1 -1 < t 1 1 -( √ t 1 - 3 4 √ t 1 ) 2 . (7)
Because 5 4 t 1 -1 > 0, the above inequality can be safely converted to the following inequality by taking square at both sides and then through trivial manipulation.

t 3 1 - 15 16 t 2 1 - 31 16 t 1 + 1 < 0. (8)
Let λ be the left side of this inequality. We have 15 16 x - 15 16 opens up and intersects the X axis at 15± √ 960 32 which contains the closed range [1, 3 2 ], we conclude t 2 1 - 15 16 t 1 -15 16 < 0, and consequently, λ < 0 and λ < 0. This finally proves that y 1 < x for -1 4 ≤ cos α 1 ≤ 1 4 . By the same technique, we can easily prove that y 2 < x for -1 4 ≤ cos α 1 ≤ 1 4 . This completes the proof. Now we are ready to present the effective movement procedure (EMP). Suppose that S is located at a and R is initially located at b in Fig. 1. The idea of EMP is to move R to position c in a random direction, and if c is not closer to a than b, further move R to either e or f (depending on ∠abc).

λ = λ -1 + t 1 = t 1 (t 2 1 -15 16 t 1 -15 16 ) > λ. Because the parabola f (x) = x 2 -
From Eqn. ( 1 As we see, EMP takes target sensor S and an arbitrary direction as input. It involves at most three movement steps. The first step is performed toward the inputed direction. It returns the direction of the last step. EMP guarantees progress (toward S) according to Theorem 1. In the course of heuristic movement to S, R runs EMP iteratively, each time with S and an arbitrary direction (or the output direction of previous EMP iteration or a direction perpendicular to it) as input. As the procedure iterates, R moves infinitely closer to S. It can be considered having reach S if its distance to S is sufficiently small (e.g., with respect to a given threshold).

THEOREM 2: With accurate pair-wise distance measurement, DREAMS guarantee full localization.

Proof: The heuristic movement enables the mobile beacon to reach a target sensor by Theorem 1, which is localized in the worst case when the beacon arrives at its position. The DFT ensures every sensor to be taken as localization target and therefore localized by the mobile beacon.

2) Noisy distance measurement: The above introduced EMP relies on accurate distance measurement. It can not be applied directly in reality, as the measurement is always inaccurate/nosily. Measurement noise may lead R to a wrong direction, away from S, or contradictionary situations that are impossible in theory. In the following, we are going to modify EMP to accommodate measurement noise. We begin with how to measure pair-wise distance.

R estimates its distance to S simply using the RSS of 'hello' message from S and the log-distance signal propagation model [START_REF] Xia | A simplified analytical model for predicting path loss in urban and suburban environments[END_REF] reversely. According to this propagation model, the average power at distance d from a wireless transmitter is

µ(d) = β -10α log d, ( 9
)
where α is a slope describing signal strength change rate, We shall now modify EMP to mitigate its dependence on the accuracy of distance measurement and reduce the impact of measurement noise on the performance. The modification includes removal of precise distance thresholds and addition of exception handling (by moving R back to its initial position). The new EMP takes the same input parameters and returns the same output as the old one. But unlike the old EMP, it may return NULL, implying that no progress is made and R stays at the original position. As the old EMP, this new procedure is run in iterations by R to approach S. If one iteration returns NULL, the next iteration will take a random direction as input. In each EMP, sojourn time is needed between steps for distance estimation. Below are the revised pseudo codes. The new exception handling subroutine has three input parameters, i.e., target sensor S, beacon initial position p and RSS of S at p. With this subroutine, after a number of trial EMP, if not at the first EMP, R will pass through the high-RSS (relative to rss) area and get out of the dead end. Because of the opportunistic nature of this dead end recovery method, large delay may occur. However, recall that in DREAMS the ultimate goal of the heuristic movement (iterative EMP) is not to move R to the position of S but provide S with sufficient beacon signals or discover the recommended next target sensor around S. Once the goal is achieved, R will move away from S for a new target even if it has not yet recovered from the dead end. Later, in Sec. IV we show through simulation that DREAMS guarantees full localization despite the presence of measurement noise and evaluate its delay performance.

C. Optimization techniques

In the rest of this section, we will present two optimization techniques, node elimination and topology control for truncating beacon trajectory and reducing localization delay. They can be used in combination for the performance.

1) Node elimination: While the beacon node R is localizing its target sensor (by iterative EMP), nearby sensors may overhear its signals and become localized as a side effect. This is very likely to happen since sensors are usually densely deployed. Those by-accident localized sensors remain unvisited. Intuitively, unvisited, but localized, sensors should not be included in the beacon trajectory. Thus we propose to improve the algorithm performance by node elimination. Eliminated nodes are not recommended to R as target and thus not visited. Notice that the network graph (or subgraph) that R is traversing is a navigation graph, and its connectivity is critical to full localization. Node elimination needs to be done with caution; otherwise, it may disconnect the navigation graph and causes localization failure.

A localized, but unvisited, sensor eliminates itself from the navigation graph if it has degree 1 (eliminated neighbors do not count) or all its neighbors are either visited or eliminated. The rationality is that, visiting such a node does not contribute to localization, and removing it does not affect the connectivity of the unvisited part of the graph. To perform self-elimination, a sensor changes its status to eliminated. Node elimination can cause chain effect: a sensor that does not satisfy the elimination conditions becomes qualified after (some of) its neighbors are eliminated and then performs self-elimination. As such, the size of the navigation graph is dynamically reduced, and beacon trajectory is consequently shortened.

It is often beneficial to have a spanning tree structure (e.g., for efficient communication) over the network. Eliminated nodes will apparently not be included in the DFT tree. But they can be easily linked to the tree through local operations Fig. 3. Node elimination as follows. When a node performs self-elimination, it attaches itself to one of its neighbors that are not yet eliminated by taking that neighbor as parent. It informs the selected parent node about their parent-child relation by 'hello' message. This parent node is later either eliminated (and attached to another node) or visited (thus attached to the DFT tree). Cascaded attachment ensures all eliminated nodes to be linked to the traversal tree without loop.

Figure 3 illustrates node elimination in a network of 4 nodes, with trilatertion as individual sensor localization procedure for simplify and beacon transmission only at step destinations. Their communication ranges are indicated by dashed circles. The beacon node R starts from p and visits p 1 , • • • , p 8 in order in 8 steps. After R reaches p 4 , a becomes localized because there exist 3 non-collinear reference points p, p 2 , and p 4 in its communication range. R keeps moving toward the position estimate of a (shown as a small hollow dot beside a) by the algorithm. At p 5 , it receives 'hello' message from b, which is the node suggested by a to visit next.

Then R changes its target to b and decides to move to p 6 (a random decision). At the same time, a becomes localized due to the three non-collinear reference locations p 2 , p 3 andp 5 and then performs self-elimination since it has only one neighbor c. When R arrives at p 8 , both b and c become localized because of p 5 , p 6 , and p 8 . c has three neighbors, a, b and c. Because c is eliminated and a and b are both visited, b eliminates itself. After c is eliminated, b has no unvisited neighbor and thus recommends to R its parent a, which is the root node, as next target. Because a now has no unvisited neighbors either, R stops moving and stays at p 8 . The final tree structure is a -b -c -d with a being the root. The edge ab is defined by DFT, while the rest are defined by node elimination.

2) Topology control: To minimize localization delay, R should travel a shortest tour that covers all the sensors in the network. This is in general the Euclidean Traveling Salesman Problem (TSP), which is known to be NP-complete. An informal definition of the TSP problem is the following: given a number of cities (i.e., sensors), find the shortest tour that visits each city exactly once and returns to the starting city. It is well known that DFT on Euclidean minimum spanning tree (MST) (with repeated visit being removed from the sequence) defines a 2-approximate solution to Euclidean TSP [START_REF] Cormen | Introduction to Algorithms[END_REF]. Motivated by this result, we naturally consider to run DREAMS on Euclidean MST instead of the original network graph. In our context, the repeated visits skipped for TSP approximation have to be allowed because they may be necessary for R to receive signal from unvisited sensors and continue DFT.

An MST is a subgraph connecting all the network nodes with weighted edges that lead to minimum total weight. In Euclidean MST, each edge is weighted by Euclidean distance between the two end nodes. Sensors may distributedly (e.g., by [START_REF] Awerbuch | Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems[END_REF], [START_REF] Gallager | A distributed algorithm for minimum-weight spanning trees[END_REF]) construct an MST according to the mutual agreement on RSS with each of its neighbors (which reflects their relative distance, here no RSS-to-distance conversion is needed). The resultant MST is thus called RSS MST. It is an approximation of the Euclidean MST. MST construction is an expensive global computation process. To preserve the localized nature of DREAMS, we consider using a localized graph that is similar to MST. A natural option is local MST (LMST) [START_REF] Li | Design and analysis of an MST-based topology control algorithm[END_REF], which contains MST as subgraph. To compute LMST, each node computes the MST of its own neighborhood. An edge between two nodes belongs to the LMST if and only if the two nodes are in each other's local MST.

In Figure 4, a network of 15 nodes (numbered 0-14) are randomly deployed in a 100 × 100 area. Their transmission radii are 25. The two sub-figures show the complete beacon trajectory respectively over the original network graph and LMST subgraph. The mobile beacon starts from the lowerleft corner and performs heuristic movement (all movement steps are shown). The mobile beacon starts from the lowerleft corner; the first sensor discovered by it is shown as a dark node. The destination of beacon movement steps is shown indicated by a small dot. The number beside it is the ID of the corresponding target sensor. If we count the number of the small dots, we will find that LMST-based trajectory involves 55 beacon steps while the non-LMST-based has 63 steps. From the figure, it is no clear what is the saving in the length of beacon trajectory. A detailed performance evaluation will presented in Sec. IV.

IV. PERFORMANCE EVALUATION

In this section, we evaluate the performance of DREAMS through simulation. Beacon mobility scheduling is not well studied in the literature. DREAMS is the first localized dynamic deterministic solution designed for realistic settings (without prior knowledge of sensory field and with RSS measurement noise). It is independent of individual sensor localization procedure; the static path method is the only existing work that has this property. Hence we decide to use fixed beacon trajectory for comparison. In particular, we chose S-shape StaticPath as it is reported to have most stable performance [START_REF] Huang | Static Path Planning for Mobile Beacons to Localize Sensor Networks[END_REF].

'Hello' message is regarded as built-in technique. Beacon message is a common tool of all beacon-assisted localization algorithm. Both are constant in size and propagate only one hop. Given fixed transmission frequency, their resultant communication cost is countable and thus out of our interest. Our simulation study focuses on the following two aspects.

Localization performance: It is measured by failure rate and localization error. The former is the average ratio of the number of unlocalized sensors (due to insufficient beacon signals) to the total number of sensors after the scheme terminates; the latter is the average distance between the estimated and the real positions of sensors.

Delay performance: It is measured by moving distance and number of movement steps. The former is the total distance that the beacon travels during the course of localization. Movement steps are the steps in EMP. It is a metric only for DREAMS, where there is waiting time between two successive steps and thus additional delay.

A. Simulation setup

We implemented StaticPath [START_REF] Huang | Static Path Planning for Mobile Beacons to Localize Sensor Networks[END_REF] and DREAMS in a custom C simulator. We implemented the following four DREAMS variants, which differ in the way that a visited sensor chooses a neighbor to recommend to the beacon node as next target:

• DREAMS-Random: choose a unvisited neighbor randomly; In heuristic movement, an EMP iteration takes a perpendicular direction of the output direction of previous iteration as input if the out direction is not NULL, and an random direction otherwise. Because StaticPath and DREAMS are independent of the individual sensor localization algorithm, we choose to use trilateration (which requires three non-collinear beacon locations and pair-wise distance) for simplify in both algorithms.

Study with other localization algorithms is for future work.

For both StaticPath and DREAMS, a sliding-window technique is used in trilateration-based sensor localization for error removal. Each sensor applies a sliding window of size 3 on the received sequence of beacon signals. Using the signals in the window, it computes its own location (if computable), and compare the result with the average of previous results. If the difference is less than a threshold, set to 0.5 in our simulation, it localizes itself to the new average position. A sensor is localized until its position estimate is satisfactorily (with respect to the above threshold). In StaticPath, it is localized to the latest average regardless.

In our simulation, we deployed a connected WSN of size n randomly in a 1000 × 1000 square region. We varied n in such a way that the average node degree ranges from 7 to 35. A mobile beacon is randomly placed in the network. It has constant speed 0.08 per simulated time unit. The beacon and sensors have same communication range 100. RSS reading is the summation of the true value and a zero-mean Gaussian noise of variance equal to 20% of the true value. We use the same 'hello' frequency and beacon frequency: one message per 1 + δ simulated time units, where δ is a random value in range [-0.2, +0.2]. For each setting, we conducted 1000 simulation runs, each with a randomly generated sensor and beacon distribution.

B. Simulation results

Fig. 5(a) plots the proportion of nodes that can not be localized, i.e., that know less than 3 non-collinear beacon locations, or that could not compute a reasonable result due to RSS noise. As expected, all DREAMS variants present a 0% failure rate (i.e., full localization) since the beacon visits every node. This is not the case for StaticPath for which 1.6% of nodes do not receive enough beacons and remain unlocalized. Fig. 5(b) plots the mean localization error noticed. One could observe that for every DREAMS variant, the error is independent of the network density (node degree) and remains very low (bellow 1, close to 0.5). This is due to the fact that a beacon will move around a target node as long as it is necessary to achieve this accuracy. This is not the case for the StaticPath scheme for which the error is much higher and increases with the number of nodes. This can be explained by the fact that in this latter scheme, the beacon trajectory depends neither of the node status (localized or not) nor of the number of nodes, and thus nodes are more likely to receive insufficient beacon messages for localization. Fig. 5(c) shows the average moving distance. By StaticPath, the beacon always travels the same distance whatever the network size is. In DREAMS, the more sensors, the longer the distance to travel. For DREAMS-Random, the distance is the longest. This can be explained by the fact that a sensor may recommend for the beacon to visit a neighbor far from the current target. Since in LMST, edges are generally shorter than in the original graph, the mean travel distance of DREAMS-LMST-Random is smaller than DREAMS-Random. In DREAMS-Closest and DREAMS-LMST-Closest, it is yet smaller since a node always recommends its closest neighbor. All DREAMS curves tend to be flat as node degree increases because the higher the node density the more probably nodes are localized without being targeted by the beacon. Fig. 5(d) plots the total number of movement steps by the beacon, which has the same trend as moving distance for the same reasons. This is worth noting that delay performance greatly depends on the localization accuracy required. The more accurate the computed position, the more movement steps and the larger moving distance involved. We chose to present only results for a accuracy below 1 due to space limit.

V. CONCLUSIONS

While beacon mobility scheduling is long considered a great difficulty in mobile-beacon assisted sensor localization, we have shown in this paper that it can be surprisingly accomplished by using the sensor network as a navigation graph. We proved that our solution, named DREAMS, guarantees full localization when each beacon is able to measure pair-wise distance accurately and showed through simulation that this property preserves even when measurement noise is present.

DREAMS was presented without considering sensor failures, which may disconnect the navigation graph and lead to localization failure. A simple fault-tolerant technique is random walk. That is, when the beacon node fails to receive instructions from sensors for its next movement step, it starts to move randomly to find a unlocalized sensor. Once it finds one, it will re-run DREAMS from there again. DREAMS is currently designed for scenarios that there is a single mobile beacon. In the future, we will extend it to multi-beacon scenarios, where the main challenge is localized beacon coordination.

4 Fig. 1 .

 41 Fig. 1. Theorem 1

THEOREM 1 :

 1 Given six different points a, b, c, d, e, f in the Euclidean plane such that b ∈ cd, a, e, f are located on the same side of cd, |bc| = |bd| = 1 2 |ab|, ce⊥cd, |ce| = 1 2 |ac|, df ⊥cd and |df | = 1 2 |ad|, as illustrated in Fig. 1. 1) If cos

Fig. 2 .

 2 Fig. 2. Noisy distance measurments

Fig. 4 .

 4 Fig. 4. Beacon trajectory

Fig. 5 .

 5 Fig. 5. Simulation results.

  ), |ac| is a monotonically decreasing function of cos(∠abc). Plug the threshold values ± 1 4 of cos(∠abc) in the equation, we obtain the corresponding threshold values (in terms of |ab|) of |ac|, i.e., |ab| and √ 6 2 |ab|, which is used in EMP by R to make movement decision as it is not able to measure angle. The pseudo codes of EMP are given below.

	Procedure: Effective_Movement_Procedure
	Input	: S, target sensor; dir, direction of 1st step
	Output	: direction of the last movement step
	/ ***** all distances used are error-free measurement ***** /
	p = current position of R; move a distance of 1 2 |pS| to q1 in dir; if |q1S| < |pS| then
	return dir; else if |q1S| > opp_dir = the opposite of dir; √ 6 2 |pS| then
	move a distance of |pS| to q2 in opp_dir;
	return opp_dir;
	else
	per_dir = a direction perpendicular to dir; move a distance of 1 2 |q1S| to q2 in per_dir; if |q2S| < |qS| then
	return per_dir;
	else
	opp_per_dir = the opposite of per_dir;
	move a distance of |q2S| in opp_per_dir;
	return opp_per_dir;
	endif
	endif

ACKNOWLEDGMENT

This work was partially supported by a grant from CPER Nord-Pas-de-Calais/FEDER Campus Intelligence Ambiante and the ANR SensLAB project.

In Fig. 2(a), the RSS gradient lines of S are shown by dashed curves. R starts heuristic movement toward S from position p. In the first iteration of EMP, it visits q 1 , • • • , q 4 in order, as indicated by the arrowed lines, and finally returns to p (no progress is made). In the second iteration, it visits q 5 and then q 6 , which finally appears closer to S than p. From q 6 , taking a direction perpendicular to the output direction of the second EMP iteration, R advances to q 7 through an third iteration of EMP. From there R continues EMP iteratively, which are now shown in the figure. Due to distance measurement noise it is possible that R is stuck at a dead end and never able to reach S, as discussed below.

Figure 2(b) illustrates a dead-end situation. The dashed curve enclosing S closely stands for the RSS gradient line through R's current position p. The dashed circle centered at S is the corresponding RSS gradient line in the deal case. R estimate its distance to S to be d, while the true distance is less than 1 2 d. In any EMP iteration started at p, R always moves to a position on the solid circle of radius 1 2 d and centered at p at the first step, and at the last step it always return to p. Notice the fact that R is actually attempting to move from p to an area of high-RSS, which is however enclosed in the solid circle. Because its step destinations are never inside the circle, EMP fails always. But nevertheless, R may pass through the high-RSS area in the course of EMP, depending on the input direction. Thus we modify the exception-handling subroutine as follows to recover from dead end.