Jose Alfredo Guerrero
email: jguerrer@hds.utc.fr

Pedro Castillo
email: castillo@hds.utc.fr

Yacine Challal
email: ychallal@hds.utc.fr

Quadrotors Formation Control A Wireless Medium Access Aware Approach

Keywords: Formation control, medium access protocols, wireless network

In this paper, the impact of the medium access protocols on the average consensus problem over wireless networks for a group of quadrotors is established. The stabilization of each helicopter is guaranteed using a simple and bounded nonlinear control strategy. We study the case of a group of quadrotors communicating over a wireless network considering both directed and undirected graphs of information ow. It turns out that the media access control (MAC) protocols have a direct impact in both convergence time and average consensus solution, i.e. the solution of the average consensus is no longer the average of the initial conditions. It will be shown that the solution for the average consensus problem over a wireless network depends directly on the MAC algorithm. Simulations are provided to demonstrate the theoretical results. In addition, to validate the control strategy some experimental tests have been carried out to control the yaw angle of two quadrotors.

Introduction

Small Unmanned Aerial Vehicle (UAV) teams are excellent candidates for improving eciency and reducing risk in search and rescue missions in unknown or dangerous environments. The deployment of small UAV teams oers certain advantages over both individual vehicles and vehicles of larger size. Small vehicles can be more easily and cheaply deployed than larger ones, and can maneuver effectively in conned spaces. Size restrictions necessarily aect payload and range capabilities, but for applications in a nite domain that is not easily accessible, the small multi-vehicle platform can be quite advantageous for rescuers. In particular, the maneuverability and speed of small rotorcraft enable their use in wilderness areas over uneven and forested areas, as well as in and around buildings for re or natural disaster rescue in urban environments.

In the particular case of multi-agent (multiple aerial vehicle) consensus problem, most of the literature is focused on modeling the information ow network using either xed or switching topologies [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF], [START_REF] Tanner | Stable Flocking of Mobile Agents, Part I: Fixed Topology[END_REF], [START_REF] Tanner | Stable Flocking of Mobile Agents, Part II: Dynamic Topology[END_REF], [START_REF] Lee | Stable Flocking of Multiple Inertial Agents on Balanced Graphs[END_REF], [START_REF] Gazi | Stability of an Asynchronous Swarm With Time-Dependent Communication Links[END_REF], among others. This means that the communication network does not suer of time delay and packet drop problems. The main dierence between xed and switching topologies is that the switching topology case takes into account that every aerial vehicle has a limited range of interaction with its neighbors, i.e., the mobility of the aerial vehicles aects the information exchange topology.

The distributed nature of multiple robot control system over wireless networks represent an interesting research problem. Data loss, data corruption and time delay over lossy network are key factors that may lead to performance degradation and even cause instability. Recent work on networked control over noisy communication channels includes [START_REF] Sahai | The necessity and suciency of anytime capacity for control over noisy cummincation link[END_REF], [START_REF] Takikonda | Control over Noisy Channels[END_REF]. In most of the cases the packet drop phenomena is modeled as a random process without any specication of its probabilistic distribution [START_REF] Lin | Robust Consensus of Mu lti-Agent Systems with Noise[END_REF], [START_REF] Zhang | Robust Consensus for Uncertain Multi-agent Systems on Directed Communication Topologies[END_REF]. In [START_REF] Hu | Stability Robustness of Networked Control Systems with Respect to Packet Loss[END_REF], the authors consider the packet drop process as a Bernoulli process and develop stability conditions under these conditions. Another way to model the packet loss phenomena has been described in [START_REF] Ling | Soft Real-Time Scheduling of Networked Control Systems with Dropouts Governed by a Markov Chain[END_REF], where a Markov chain has been used to model the packet dropout process. This paper addresses the issue of packet loss as well as packet delay in a multiagent aerial system considering a wireless network. For this end, we use the widely adopted network simulator (NS2) which provides a rich simulation environment modeling the dierent network communication layers: the physical layer (modulation, frequencies, signal and radio propagation models, wired and wireless channels, ...), link layer (dierent medium access control algorithms: TDMA, CSMA/CD, CSMA/CA, ALOHA, ...), routing layer (routing protocols over wired and wireless networks as well as mobile ad hoc networks), transport layer (TCP, UDP, RTP, etc.), and the application layer with a rich sample of applications for typical trafc generation scenarios. It will be assumed, for simplicity, that every agent in the multi-vehicle system broadcasts its information to its neighbors considering a xed topology of information exchange, i.e. the mobility of the vehicles does not aect the information ow network. It is assumed that the neighbors of the i th -quadrotor are always in broadcasting range. Dierent network media access control protocols have been designed for wireless networks. Likewise, in this paper, we analyze the impact of the following algorithms on the multiple quadrotor average consensus problem: Carrier sense multiple access with collision avoidance (CSMA/CA) and time division multiple access (TDMA).

The outline of the paper is as follows: A brief description of the multi-quadrotor dynamics and control over perfect communication links is introduced in section 2. In Section 3, the multi-quadrotor average consensus over wireless network analysis is presented. A stability analysis to improve the convergence of the consensus is proposed in section 4. Simulation results are illustrated in section 5. And nally, conclusion and future work are discussed in section 6.

2 Multi-quadrotor consensus 2.1 Quadrotor dynamic model and control scheme Let us consider a group of N -quadrotor helicopters with the following dynamical model [START_REF] Lozano | Unmanned Aerial Vehicles Embedded Control[END_REF], [START_REF] Guerrero | Flight Formation of Multiple Rotorcrafts[END_REF]:

zi = F i cos(θ i ) cos(ϕ i ) -1; ψi = u ψ i (1a) ÿi = F i cos(θ i ) sin(ϕ i ); φi = u ϕ i (1b) ẍi = -F i sin(θ i ); θi = u θ i (1c)
where (x i , y i , z i ) and (ϕ i , θ i , ψ i ) represent the position and orientation of the i th -quadrotor, respectively. F i denotes the thrust force vector and u ψ i , u ϕ i , u θ i the generalized torques.

To stabilize the previous system, we use the following control laws,

F i = -σ b 1 i (k 1 i ż) -σ b 2 i (k 2 i (z i -z d i )) + 1 cos(ϕ i ) cos(θ i ) (2a) u ψ i = -σ b 3 i (k 3 i ψi ) -σ b 4 i (k 4 i (ψ i -ψ d i )) (2b)
u θ i = -σ b 5 i (k 5 i θi ) -σ b 6 i (k 6 i θ i ) + σ b 7 i (k 7 i ẋi ) + σ b 8 i (k 8 i x i ) ( 2c
)
u ϕ i = -σ b 9 i (k 9 i φi ) -σ b 10 i (k 10 i ϕ i ) -σ b 11 i (k 11 i ẏi ) -σ b 12 i (k 12 i y i ) (2d)
where

|σ b m i (s)| < b m i is a saturation function k m i , b m i > 0; m = 1, ..., 12
; are constant, z d i and ψ d i are the desired altitude and heading for the i th -quadrotor, respectively. It was proved in [START_REF] Sanahuja | Stabilization of n integrators in cascade with bounded input with experimental application to a VTOL laboratory system[END_REF] that the nonlinear control laws in (2) guarantee the stabilization of the i th -quadrotor in closed loop system such that

lim t→∞ z i = z d i ; lim t→∞ x i = 0 lim t→∞ ψ i = ψ d i ; lim t→∞ y i = 0
Fig. 1: Quadrotor platoon

From individual to collective behavior

In order to model the interactions among helicopters, a graph-based theoretical approach has been considered. Notice that the closed-loop system, ( 1)-( 2), for the i th -quadrotor can be expressed with the following kinematic model

ẋi = u i ∀i = 1, .., N ;
where x i is the state vector and u i represents the control input vector.

Multi-quadrotor consensus is achieved using the following algorithm

u i = - ∑ j∈N i (x i -x j ) (3)
where N i is the set of vehicles transmitting their information to the i th -quadrotor. Noticed that (3) ensures the consensus agreement in the sense of lim t→∞ |x i -x j | = 0. Hence, the position consensus among quadrotors yields

ẋ = -Lx (4)
where L is the Laplacian matrix of the information exchange graph, more details see [START_REF] Guerrero | Flight Formation of Multiple Rotorcrafts[END_REF][START_REF] Guerrero | Robust Consensus Tracking of Leader-Based Multi-Agent Systems[END_REF].

Therefore, the controllers in ( 2) can be improved to the case of multi-quadrotor consensus with the form

F i = -σ b 1 i (k 1 i ż) -σ b 2 i ( k 2 i ( ∑ j∈N i (z i -z j ) -z d i )) + 1 cos(ϕ i ) cos(θ i ) (5a)
u ψ i = -σ b 3 i (k 3 i ψi ) -σ b 4 i   k 4 i   ∑ j∈N i (ψ i -ψ j ) -ψ d i     (5b) u θ i = -σ b 5 i (k 5 i θi ) -σ b 6 i (k 6 i θ i ) + σ b 7 i (k 7 i ẋi ) + σ b 8 i   k 8 i ∑ j∈N i (x i -x j )   (5c) u ϕ i = -σ b 9 i (k 9 i φi ) -σ b 10 i (k 10 i ϕ i ) -σ b 11 i (k 11 i ẏi ) -σ b 12 i ( k 12 i ∑j∈N i (y i -y j ) ) (5d)
which implies that

lim t→∞ |(z j -z i )| = z d i ; lim t→∞ |(x j -x i )| = 0 lim t→∞ |(ψ j -ψ i )| = ψ d i lim t→∞ |(y j -y i )| = 0
In order to illustrate the performance of the previous control strategy, simulations were carried, over the x-axis, out considering a 10-quadrotor platoon over a perfect communication network (no delay, no packet loss) with cyclic topology. The initial conditions are x i (0) = i, ∀i = 0, 1, ..., 9. Since the x-and y-axis have a similar behavior, only the x-axis consensus performance graphs will be presented.

Figure 2 shows the consensus response. Observe in this gure that the convergence time is small and the solution of the average consensus over the x-axis is the average of the initial conditions, i.e., the platoon achieves consensus to 4.5m. Thus, the previous nonlinear control laws guarantees the position synchronization of the quadrotor platoon. In literature, several simulations using the previous (similar or dierent) controllers have been carried out in order to prove the stability of the consensus or of the ight formation trajectory, see [START_REF] Fax | Information Flow and Cooperative Control on Vehicle Formations[END_REF], [START_REF] Laerriere | Decentralized control of vehicle formations[END_REF], [START_REF] Dunbar | Distributed receding horizon control for multivehicle formation[END_REF], [START_REF] Chen | LNCIS 336 Group Coordination and Cooperative Control[END_REF]. Most of the assumptions in these works are considering wireless and perfect communication between the vehicles. In addition, the main results in ight formation are in general illustrated only in simulations.

As it is known, in a real multi-vehicle ight formation system, each aircraft collects information from its sensors and then exchange its information, employing wireless communication, with other autonomous vehicles in the network. Packet delay and packet loss in wireless becomes a major issue of study that must be taken into account when stabilizing multi-aerial vehicles. The goal of this work is to analyze, the impact of the wireless network communication in the real-time multi-vehicle consensus problem.

Analysis of wireless communication impact on ight formation

Let us consider the case of a N-quadrotor formation ying over a wireless communication channel. From the automatic control point of view, the key factors when using wireless channels are: end-2-end time delay, packet dropout rate, network connectivity and noise. Let us assume that the mobility of the agents does not aect the network connectivity and neglect the noise from sensors. Then, we focus our attention on the packet dropout rate and the end-2-end time delay problems. It has been shown in the communications literature [START_REF] Lian | Tilbury Performance Evaluation of Control Networks: Ethernet, ControlNet and DeviceNet[END_REF], [START_REF] Liu | Wireless medium access control in networked control systems[END_REF] that both packet dropout rate and the end-2-end time delay are determined by the Medium Access Control protocols. Our study considers two common technologies for wireless communications: CSMA/CA used in IEEE802.11 and TDMA used in GSM.

CSMA/CA

This is a distributed random access algorithm used in many standards such as Wi IEEE802.11. This scheme uses a carrier sense multiple access with collision avoidance (CSMA/CA) mechanism for resolving the problem of access to the communication medium. This implies that when a node detects a collision, it stops transmitting and waits for a random time before retransmitting. More precisely, the protocol CSMA/CA works as follows [22]:

1. a carrier sensing scheme is used 2. a data station that intends to transmit, sends a jam signal, 3. after waiting a sucient time for all stations to receive the jam signal, the data station transmits a frame 4. while transmitting, if the data station detects a jam signal from another station, it stops transmitting for a random time and then tries again.

We distinguish two variants: with and without channel reservation. In CSMA/CA with channel reservation, the transmitter rst transmits a RTS (Request to Send) for channel reservation, and waits for receiving a CTS (Clear To Send) from the destination before starting to send the data frame. CSMA/CA is not suitable for real time communications, since it does not guarantee a upper bound for the delay before sending a data frame.

TDMA

This is a time slotted scheme used in many standards such as GSM. Accordingly with [22], TDMA (Time Division Multiple Access) is a collision-free multiple access technique whereby users share a transmission medium by being assigned and using (one at a time) time slots assigned previously.

TDMA is more suitable for real time communications, since it guarantees a upper bound delay before transmitting a data frame.

Network Analysis

To evaluate the performance of CSMA/CA and TDMA protocols on the quadrotor consensus problem, extensive simulations have been run using the network simulator NS2. As it is shown in Figures 3 and4, it is clear that the packet drops for TDMA protocol are almost null. We attribute the packet drops shown in Figure 3 to the synchronization phase during the simulation initialization. Unlike TDMA, CSMA/CA shows a higher rate of packet drops due to its random broadcasting nature, see Figure 4. Now, let us analyze the average end-2-end delay which gives an insight of the expected time delay on multi-quadrotor systems. It is known that in real-time applications, after a large time delay, data may become useless. Therefore it is important to analyze the performance of MAC protocols such that the multiquadrotor system will undergo the minimal time delay. On one hand, since TDMA is a time division multiple access technique to access the transmission medium, it is almost intuitively that the time delay, should show an almost constant rate. This can be conrmed by observing Figure 5. On the other hand, taking into account the packet drop rate at each quadrotor, it is expected that CSMA/CA would show a variable time delay and the maximum time delay is much higher than TDMA. The evolution of the average end-2-end time delay over time for the CSMA/CA protocol is shown in Figure 5. It is worth to mention that the end-2-end time delay has been obtained at Agent trace level, i.e. from application to application layer.

Quadrotor Consensus over Wireless Networks

In this section, we can introduce a Network-aware average consensus control for a multi-quadrotor system over a wireless network. By taking into account the phenomena discussed above, the packet dropout process will be considered as a source of time delays in the wireless network. As shown in [START_REF] Lian | Tilbury Performance Evaluation of Control Networks: Ethernet, ControlNet and DeviceNet[END_REF], the end-2-end time delay τ is given by the dierence T dst -T src (time at destination and time at source, respectively) which in turn depends on the preprocessing time T pre , wait time T wait , transmission time T tx and the post processing time T post . Since the nearest neighbor approach assumes that each vehicle communicates only with immediate neighbors that are in its radio range, and assuming that a packet loss implies the re-transmission of the data that has been lost, we consider the packet dropout process, as part of the transmission time delay which has been dened as the frame time T f rame and the propagation time T prop , more details see [START_REF] Lian | Tilbury Performance Evaluation of Control Networks: Ethernet, ControlNet and DeviceNet[END_REF].

Then, we propose to use the following multi-quadrotor consensus control as in [START_REF] Chopra | Output Synchronization of Mechanical Systems[END_REF]

u i (t) = - ∑ j∈N i (x i -x j (t -τ ji )) (6)
Thus, (3) becomes

F i = -σ b 1 i (k 1 i ż) -σ b 2 i (k 2 i ( ∑ j∈N i (z i -z j (t -τ ji )) -z d i )) + 1 cos(ϕ i ) cos(θ i ) (7a) u ψ i = -σ b 3 i (k 3 i ψi ) -σ b 4 i   k 4 i   ∑ j∈N i (ψ i -ψ j (t -τ ji )) -ψ d i     (7b) u θ i = -σ b 5 i (k 5 i θi ) -σ b 6 i (k 6 i θ i ) + σ b 7 i (k 7 i ẋi ) + σ b 8 i   k 8 i ∑ j∈N i (x i -x j (t -τ ji ))   (7c) u ϕ i = -σ b 9 i (k 9 i φi ) -σ b 10 i (k 10 i ϕ i ) -σ b 11 i (k 11 i ẏi ) -σ b 12 i ( k 12 i ∑j∈N i (y i -y j (t -τ ji )) ) (7d)
It was proved that all the states of each agent, using (2) in closed-loop system, goes to the desired values or to zero. Then for each agent ∃ a storage function

V i (x i ) > 0 such that Vi (x i ) = -S i (x i ) with S i (x i ) ≥ 0. Therefore, considering the following Lyapunov function V = N ∑ i=1 ∑ j∈N ∫ t t-τ ji x T j (χ)x j (χ)dχ + 2 N ∑ i=1 V i (8)
this implies that,

V = -2 N ∑ i=1 S i (x i ) - N ∑ i=1 ∑ j∈N i (x j (t -τ ji ) -x i ) T (x j (t -τ ji ) -x i ) (9)
From the above it follows that

lim t→∞ |(x j (t -τ ji ) -x i )| = 0 (10)
From [START_REF] Hu | Stability Robustness of Networked Control Systems with Respect to Packet Loss[END_REF], it is clear that the solution of the average consensus to the average of the initial conditions depends on the network medium access algorithm, which in turn determines the values of the τ ji , the transmission delay from j to i, for each quadrotor.

Figure 6 shows the performance of the average consensus considering τ ji = τ kj . It can be observed that the average consensus is the same than the one for the perfect communication case. The dierence is that the convergence time for the equal time delay case is larger than for the perfect communication case.

Figure 7 shows the performance of the average consensus considering τ ji ̸ = τ kj . It can be observed that the solution of average consensus is dierent from the previous two cases: perfect communication case and equal time delays case. Based on the law of large numbers, the average of the results from a large number of simulations should be closed to the expected value. Figure 7 shows the consensus over time of the average of 1000 simulations. Now, let's take a look at the average consensus performance using a wireless network. The network scenario consisted of 10-quadrotors sharing information over a cyclic topology. A quadrotor application was developed, a UDP transport protocol was modied to exchange information with the quadrotor application and the MAC layer is shown in Figure 8. It can be concluded that the average consensus using a CSMA/CA protocol presents a larger convergence time due to both packet drops and time delay in the end-2-end transmission among quadrotors. Also, due to the fact that the access to the transmission medium is assigned randomly, it is evident that some quadrotors will transmit their positions to their neighbors before their counterparts. This implies that the dierence between any two τ ji can be large enough such that some quadrotors will evolve faster than the others. Then, the quadrotor with the smallest τ ji will update its position at a highest rate than the others. Figure 11 shows the performance of the average consensus for a small platoon of 4 quadrotors using dierent medium access control algorithms such as: CSMA/CA, TDMA, constant time delay (τ ji > 0), and perfect communication. In order to validate the control strategy, some experimental tests have been carried out using CSMA/CA. To simplify the experiments we focus mainly in the yaw dynamic of the helicopter. The experiment is developed as follows; rst the helicopters are stabilized at hover with ψ d i = 0. Then, we changed manually this desired value with the control radio only for one helicopter. We begin changing ψ d for helicopter 1, later for helicopter 2, and so on. The main result is illustrated in Figure 12. Notice from this gure, the delayed response of the second/rst helicopter when it follows the rst/second quadrotor. More details of the platesformes see [START_REF] Lozano | Unmanned Aerial Vehicles Embedded Control[END_REF]. Fig. 12: Average consensus for the yaw subsystem. An external reference was given to the system in order to show the delay over the wireless network 6 Conclusions and Future Work A nonlinear control based on saturation functions and a single integrator consensus control considering time delay for ight formation of mini rotorcraft was developed. We remark that TDMA is more suitable for real time communications than CSMA/CA, since it guarantees a upper bound delay before transmitting a data frame. CSMA/CA is less suitable for real time communications, since it does not guarantee an upper bound for the delay before sending a data frame. Extensive simulations were run in order to show the performance of the developed control scheme.

Fig. 2 :

 2 Fig. 2: Multiple quadrotor consensus using perfect communication

Fig. 3 :

 3 Fig. 3: Packet drop using TDMA. Simulation time = 60 sec.

Fig. 4 :

 4 Fig. 4: Packet drop using CSMA/CA. Simulation time = 60 sec.

Fig. 5 :

 5 Fig. 5: End-2-End delay comparison between CSMA/CA and TDMA. Simulation time = 60 sec.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Multiple quadrotor consensus with τ ji = τ kj

Fig. 8 :

 8 Fig. 8: Multiple quadrotor wireless network stack

  , it is possible to observe that the solution for the average consensus as well as its convergence time are aected by the network media access control algorithm.

Fig. 9 :Fig. 10 :

 910 Fig. 9: Multi-agent consensus using IEEE 802.11

Fig. 11 :

 11 Fig. 11: Comparison of convergence time for dierent MAC algorithms

  Quadrotor 1 Quadrotor 2

Table 1 :

 1 Performance Comparison

	MAC Algorithm	Max E-2-E Time Delay	Convergence Time
	CSMA/CA	∼ 12	∼ 1200
	TDMA	∼ 3.2	∼ 200
	Perfect Comm.	0	∼ 40

Future work in this area includes experimental tests on mini rotorcraft using real-time embedded control systems and to develop an optimized medium access control algorithm for mobile robot systems.


Vincent Drevelle

Philippe Bonnifait

Interval-based Fault Detection and Identification applied to Global Positioning

We present a real-time robust positioning system based on interval analysis and constraint propagation that computes position domains, and that is able to detect and reject erroneous measurements. GPS pseudorange measurements are represented by intervals assumed to contain the true value with a given confidence level. A 3-D map of the drivable space is also available to constrain the vehicle location. By the use of a breadth-first exploration strategy and of measurement consistency counters, the algorithm can be stopped at any time of the evaluation, and can instantly return the solution subpaving and the list of identified erroneous measurements. The method has been evaluated with real raw GPS data (i.e. pseudodistances on visible satellites) in a urban environment with a low-cost high-sensitivity GPS receiver providing faulty multipath measurements.

INTRODUCTION

In this paper, we aim at estimating a vector of parameters from a set of measurements and prior information, while detecting and identifying erroneous measurements. These erroneous measurements, also called outliers, are observations that cannot be explained by the observation model, either because they correspond to extreme noise values, or because they result of phenomenons or faults that have not been modeled.

We focus on a snapshot localization problem, where time dependency of position is not considered. Therefore, only an observation model is considered with no evolution model.

In urban environments, GPS positioning is likely to suffer from erroneous measurements. In the case of GPS, faults may arise from satellite or control segment failures. Augmentation systems (like WAAS and EGNOS) are available to protect users against such system failures. Another source of outliers is the alteration of signal propagation by the user's environment. Indeed, for time-of-flight measurement, signals are assumed to follow a direct path from the satellite to the receiver. However, especially in urban environments, when the direct path is blocked by an obstacle (like a building or a tree), the receiver may acquire a reflected ranging signal. It is called non line-ofsight propagation. This measurement is then an outlier, since the observation model is based on the hypothesis of direct propagation.

Fault detection and identification (FDI) methods are implemented in some GPS receivers, to provide receiver autonomous integrity monitoring (RAIM). They are often based on range residuals [START_REF] Walter | Weighted RAIM for precision approach[END_REF]) or parity space [START_REF] Ding | Model-based fault diagnosis techniques: design schemes, algorithms, and tools[END_REF]). RAIM is used in aeronautical navigation, to detect and identify erroneous measurements, and compute protection levels, which are bounds on the positioning error that may result from undetected faults.

Interval based methods have successfully been applied to model based diagnosis, as they enable to take model uncertainties into account and can handle nonlinear systems. [START_REF] Marx | State estimation and diagnosis of uncertain system based on an interval approach[END_REF] use interval observers to detect change of operation mode, and [START_REF] Adrot | Fault detection based on interval analysis[END_REF] propose a parity space approach where the parity matrix depends on uncertain parameters.

Set-membership methods have already been used to compute uncertainty in GPS networks with zonotopes by [START_REF] Schön | Uncertainty in gps networks due to remaining systematic errors: the interval approach[END_REF] and for interval based height-aided GPS localization (Drevelle and Bonnifait [2011b]) with fault-detection results consistent with standard RAIM methods. In this paper, we compute a position domain in which the user is located using an interval based method that is robust to the presence of erroneous GPS measurements. The method performance is increased thanks to the use of a 3D map of the drivable space. Along with the computation of the localization confidence domain, the algorithm enables to detect and identify the faulty measurements. Our contribution is to perform FDI within the set-inversion process, in a quickly interruptible algorithm thanks to the use of measurement compatibility counters.

The paper is organized as follows. Interval analysis methods for robust bounded-error estimation are first presented. Then, a way to detect and identify outliers from robust set-inversion results is shown, and an algorithm than enables quick interruption of computation with fault detection result is presented. Finally, experimental results are reported with raw GPS measurements.

ESTIMATION USING INTERVAL ANALYSIS

Interval analysis

Interval analysis [START_REF] Jaulin | Applied Interval Analysis[END_REF]) involves intervals and their multidimensional extension, interval vectors (or boxes). In opposition to arbitrary sets, intervals and boxes are easy to represent and manipulate. The set of real intervals [x] = [x, x] is denoted IR, and the set of ndimensional boxes is IR n . In this paper, a box is denoted [x] = [x, x], where vectors x and x are respectively the lower and upper bounds of [x].

Interval arithmetic allows performing computations on intervals and boxes thanks to the interval extension of classical real arithmetic operators +, -, × and ÷.

[x] + [y] = [x + y, x + y], [x] -[y] = [x -y, x -y] In the same way, elementary functions such as tan, sin and exp can be extended to intervals. This is done by returning the smallest interval covering the range of the input through the function.

The image of a box by a function f : R n → R m is generally not itself a box, but an arbitrary set. This problem is solved using the so-called inclusion functions:

The interval function [f ] from IR n to IR m is an inclusion function for f if the image of [x] by f is included in the image of [x] by [f ], i.e. ∀[x] ∈ IR n , f ([x]) ⊂ [f ]([x]
). The box hull 2S of a set S is the smallest box that includes S. Since the union of boxes is not generally a box, the box union operator returns the box hull of the union of two boxes:

[x] [y] = 2([x] ∪ [y]).

Contraction and propagation

When the components of a vector x are linked by relations or constraints, one can define a constraint satisfaction problem (CSP). It consists in finding the solution set X = {x ∈ [x]|f (x) = 0}, where [x] is the domain of the variables and f (x) = 0 represents the constraints, and can also represent inequalities by introducing slack variables [START_REF] Jaulin | Applied Interval Analysis[END_REF]).

A contractor C for a CSP is an operator that computes a smaller domain [x c ] = C([x]) without affecting the solution set, i.e. X ⊂ [x c ] ⊂ [x]. There are many ways to implement a contractor, one of them is the forward-backward contractor based on constraint propagation [START_REF] Benhamou | Revising hull and box consistency[END_REF]).

Set inversion and subpavings

The set inversion problem consists in determining the set X such as f (X) = [y], where [y] is a known interval vector of m measurements. To approximate compact sets in a guaranteed way, subpavings can be used. A subpaving of a box [x] is the union of non-empty and non-overlapping subboxes of [x].

Using interval analysis, the solution X = f -1 ([y]) can be approximated between two subpavings X and X such that X ⊆ X ⊆ X. The SIVIA algorithm allows performing such a set inversion, by recursively bisecting an initial box [START_REF] Jaulin | Applied Interval Analysis[END_REF]).

Algorithm 1 implements a SIVIA that only computes an outer approximation X of the solution set in a given domain [x 0 ], since we are seeking to characterize the positioning confidence domain. It uses a list of boxes L managed by the push and pull functions. If L is a queue, the algorithm employs a breadth-first strategy. ε controls

X 1 X 2 X 3 { 1} X i { 2} X i X i { 0} X i = Fig. 1. q-relaxed intersection of three sets the sharpness of the subpaving X. A contractor C([x]
) is used to apply the constraint from measurements on each box. It may either reduce the size of a box without losing any solution, or return an empty box if the initial box is incompatible with the measurements. Boxes larger that ε after contraction are bisected and enqueued to be processed again.

Algorithm 1 SIVIA(in: [x 0 ], C, ε) X := ∅ // empty subpaving push([x 0 ], L) while L is not empty [x] := pull(L) [x] := C([x]) // contract the box if width([x]) < ε then X := X ∪ [x] else if [x] = ∅ then ([x 1 ], [x 2 ]) := bisect([x]) push([x 1 ], L); push([x 2 ], L) endif end return X

Robust set-inversion

The presented set-inversion method is likely to return an empty solution set in the presence of erroneous measurements. Robustness to outliers can be achieved by computing the set of solutions that are compatible with at least a given number of measurements instead of the set of solutions compatible with all the measurements. By using the q-relaxed intersection of m measurement constraints (Fig. 1), a set of solutions compatible with at least m -q measurements is computed.

If a contractor C i is available for every measurement, then a q-relaxed contractor C {q} can be built. It is presented in Algorithm 2.

Figure 2 shows the results of the presented SIVIA algorithm with the q-relaxed contractor. Three constraints are provided by ranging beacons, one of which is faulty and gives an erroneous distance measurement. SIVIA is employed with the C {1} contractor to compute an outer approximation of the 1-relaxed intersection of the three constraints. The obtained solution subpaving is consistent with ground truth.

Algorithm 2 C {q} : q-relaxed contraction (m measures)

for i = 1 to m { [x i ] := C i ([x]) } [x c ] := 2   {q} i∈{1,. . . ,m} [x i ]   return [x c ] B1 B2 B3

Fig. 2. Results of a 1-relaxed set inversion in a localization

problem with 3 ranging beacons. The measurement from beacon B3 is erroneous. The solution subpaving covers the true solution-set.

FAULT DETECTION AND IDENTIFICATION

The principle of the method is to compute a solution set and then to analyze the compatibility of the measurements with this set.

In practice, it is necessary to compute a solution with robustness. Otherwise, the solution can often be empty, which prevents fault identification. The robust method that we use in this work is the q-relaxed set inversion. It enables computing a solution set robust to a specified number of outliers.

Afterward, it is possible to try to identify the faulty measurements. Indeed, uncertainty affecting the measurements makes the identification not always possible. The method that we propose is to check if the boxes of the solution subpaving are compatible with each measurement.

For each measurement, an inclusion test is done for every boxes of the subpaving. Detection and identification can be obtained using Boolean tests. The presence of an outlier is detected when the subpaving does not contain a box that can satisfy all the constraints. Outlier detection is performed when there is not any box than can satisfy the constraint of a given measurement. For instance, at the beginning of the process, all measurements are marked as outliers. As soon as a box compatible with the measurement is found, the measurement is unmarked. Once the whole subpaving has been tested, the measurements that remain marked are identified as outliers.

f -1 (y1) X q=1 f -1 (y2) f -1 (y3) b1 b2 b4 b3 Box \ Measurement [y 1 ] [y 2 ] [y 3 ] [y] b1 1 0 1 0 b2 1 1 1 1 b3 1 1 0 0 b4 0 1 1 0
Fig. 3. Detection and identification table with no erroneous measurement. The final row describes if the measurements are compatible with the computed subpaving.

In Fig. 3, the compatibility of a box with [y] (last column) is computed using a logical AND between the elements of the corresponding row. For instance, box b2 is compatible with the three measurement intervals and box b1 is compatible with the single measurements [y 1 ] and [y 3 ], but not with [y 2 ] nor all the measurements together [y]. The results for the solution subpaving are obtained by applying a logical OR between the elements of each column. Since the lower-right element equals one, no erroneous measurement is detected.

b1 b2 b3

Box \ Meas.

[y 1 ] [y 2 ] [y 3 ] [y] b1 1 0 1 0 b2 1 0 1 0 b3 1 1 0 0 Result 1 1 1 0 detection
Fig. 4. Detection and identification table with an outlier detected.

In Fig. 4, there is no box in the subpaving that can fulfill the constraints of all the measurements since the lowerright element equals zero. The presence of an outlier is thus detected. However, since there is at least a box compatible with each measurement in the solution subpaving, it is not possible to identify the faulty measurement. The detection and identification table contains also extra information.

For instance, if there is no more than one outlier at a time, one can conclude that the faulty measurement is either In Fig. 5, the presence of an erroneous measurement is detected like in Fig. 4. Moreover, the outlier can be identified in this particular case. Indeed, there is no box in the subpaving that can satisfy the constraint from measurement [y 3 ]. The latter is thus identified as the faulty measurement. The identification is guaranteed as long as the number of true outliers remains lower or equal to the degree "q" of the q-relaxation.

[y 2 ] or [y 3 ]. b2 b1 Box \ Meas. [y 1 ] [y 2 ] [y 3 ] [y] b1 1 1 0 0 b2 1 1 0 0 Result 1 1 0 0 identification detection

OPTIMIZED IMPLEMENTATION

One of the main drawbacks of the previous method is that the processing is long to interrupt, since a postprocessing has to be performed on the solution subpaving to carry out fault identification. It is unfortunate, as the set inversion process can be interrupted at any time to quickly provide an approximate solution. The ability to provide a solution with a reduced and guaranteed latency is a basic requirement for real-time systems.

We present in this section a way to prepare as much as possible the fault identification process during the exploration of the solution space. The idea is to use measurement compatibility counters. As it slows down each iteration of the set inversion algorithm, this implementation reduces the number of bisections per second. However, as the bisection loop terminates, only few quick operations are needed to get the solution subpaving and the list of identified outliers.

RSiviaExtCount (Alg. 3) computes a subpaving that covers the q-relaxed solution, and, in the meantime, keeps track of the compatibility of the subpaving with the measurements through the use of counters. Set-inversion can be interrupted at any time, and outlier detection and identification can then be done by checking the counters values. To reduce the number of inclusion tests, each box is augmented with a compatibility bit-field, which indicates which measurements are compatible with it.

When there is no solution (i.e. an empty set), there are more outliers in the measurements than q, which is the maximum number anticipated. Each counter equals zero in this case. If one wants to get a non empty result, it is possible to restart the estimation process with more relaxation (e.g. q := q + 1). This strategy is known as GOMNE (Guaranteed Outlier Minimal Number Estimator) presented in [START_REF] Jaulin | Guaranteed robust nonlinear parameter bounding[END_REF].

Otherwise, the values of the counters are examined to check the presence of outliers. If the global counter c all is equal to zero, then the presence of an outlier is detected, since there is no box in the solution that is compatible with all the measurements. One can notice that c all corresponds to the lower-right element of a detection and identification table (see Fig. 4). It is then possible to check if an outlier has been identified, simply by studying the values of individual measurement compatibility counters c i , which keep track of the number of boxes in the subpaving that are compatible with each measurement. If the counter c i is null, then the measurement y i is identified as an outlier, like in the last row of a detection and identification table (see Fig. 5). Figure 6 shows the counter values and outlier detection results after a 1-relaxed set inversion on simple examples.

This implementation of fault detection and identification inline with set-inversion not only enables reducing the latency when the computation is stopped, but also monitoring outliers during the computation. This is another advantage of this approach since it provides valuable information for online optimization of the set-inversion computation. Indeed, once a measurement has been identified as an outlier, computing a q-relaxed solution set with all the measurements is equivalent to compute a (q -1)-relaxed solution with all the measurements but the identified outlier. The robust set inversion algorithm can therefore dynamically discard measurements as they are identified as outliers and thus speed up the computation by reducing the number of constraints to satisfy.

Algorithm 3 RSiviaExtCount (in: [x], {C i , i = 1 . . . m}, [f ], [y], q, ε; out: S x )
// Initialize measurements compatibility counters

for i = 1 to m { c i := 1 c all := 1 [x].c i := 1 } L := {[x]} S x := ∅ while L = ∅ and not timeout {
// Pick a box from the list [x] := pull(L) // q-relaxed contraction with measurements

for i = 1 to m { . [x i ] := C i ([x]) } [x c ] := 2   {q} i∈{1,. . . ,m} [x i ]   // Update inclusion-test results bit-field for i = 1 to m { . if [f i ]([x c ]) ∩ [y i ] = ∅ then [x c ].c i := 1 . else [x c ].c i := 0 } // Update counters if [x c ] = ∅ then { . if w([x c ]) < ε then { . . // Box is too small . . S x := S x ∪ [x c ] .
. // Update compatibility counters .

.

for i = 1 to m { . . . c i := c i + [x c ].c i -[x].c i . . . c all := c all + i [x c ].c i - i [x].c i . . } . } .
else { .

. // Bisect and enqueue suboxes .

.

([x 1 ], [x 2 ]) = bisect([x c ]) . . push([x 1 ], L); push([x 2 ], L) .
. // Update compatibility counters (2 boxes) .

.

for i = 1 to m { . . . c i := c i + 2 • [x c ].c i -[x].c i . . . c all := c all + 2 i [x c ].c i - i [x].c i . . } . } } else { . for i = 1 to m { . . c i := c i -[x].c i . . c all := c all - i [x]c i . } } } // Compute solution set S x := S x ∪ L if c all = 0 then outlier detected for i = 1 to m { if c i = 0 then [y i ] is an outlier } (a) No outlier (b) Fault detected, unidentified outlier (c) Outlier identified: y3 c(all)=1 c(y1)=3 c(y2)=3 c(y3)=3 f -1 (y1) X q=1 f -1 (y2) f -1 (y3) 1 3 1 2 3 3 2 1 2 c(all)=0 c(y1)=3 c(y2)=1 c(y3)=2 1 3 1 3 1 2 c(all)=0 c(y1)=2 c(y2)=2 c(y3)=0 1 2 1 2
Fig. 6. Outlier detection and identification with compatibility counters

EXPERIMENTAL RESULTS

In this section, we report experimental GPS positioning results obtained with a real-time implementation of the algorithm implemented in C++. Raw time-of-flight measurements (pseudoranges) from a low-cost high-sensitivity uBlox LEA4T GPS receiver are used to constrain the user position. Measurement noise is taken into account by representing pseudoranges with intervals. A 3D map of the drivable space (provided by the french Institut Geographique National ) is also used a constraint on position. Positioning is done with the previously presented robust set-inversion algorithm. The contractors for GPS and 3D map are respectively based on interval constraint propagation and on a polygon clipping algorithm, and can be found in Drevelle and Bonnifait [2011a].

The dataset consists in three loops around the mairie of the 12 th arrondissement in Paris, covering 3 kilometers in 16 minutes (Fig. 7). It is very challenging for GPS since the narrow streets with high buildings prevent good reception of the satellites' signals, and are source of erroneous measurements due to multipath and non-line-ofsight signal propagation. A common practice to reduce the number of erroneous GPS measurements is to filter out observations whose signal-to-noise ratio (SNR) is too low. In order to test the presented algorithm in the presence of a lot of outliers, we set the SNR filtering threshold to a very low value of 20 dBHz (the standard being at 37 dBHz). Pseudorange measurements were modeled by ±3 m intervals.

The robust set-inversion algorithm used in this experiment implements the GOMNE strategy: computation starts with no constraint relaxation, and the number q of relaxed GPS measurements is increased until a non-empty solution is found. Since an empty solution-set with a q-relaxed set inversion indicates that there are at least q + 1 outliers in the measurements vector, the algorithm is able to report a lower bound of the number of outliers. This is the number of detected outliers shown in Fig. 8. Outliers identification is performed with the compatibility counters presented in the previous section. Since the use of intervals to characterize the solution as a subpaving, the results are dependent on the coordinate system. Computations are done in a "East, North, Up" local tangent frame, that enables very efficient altitude contraction with the map constraint.

Fig. 8 shows that the algorithm detects at most 3 simultaneous outliers during the trial, and is able to identify at most two outliers. This is illustrated by Fig. 9, where two outliers are successfully detected and identified at epoch #80 (t=400 s).

Due to the lack of redundancy, fault detection may fail, and even lead to wrong exclusion. This happens at epoch #89 Another source of error is the presence of too many outliers at particular epochs since the SNR threshold for measurement rejection was set very low (e.g. at t=445 s).

CONCLUSION

An interval-based position estimation method with fault detection and identification has been presented. It enables computing a localization domain from a few GPS measurements with outliers and a 3D map. An optimized implementation with measurement compatibility counters has been introduced, and tested on a sequence of real GPS data in a very difficult urban environment. The method is able to compute a position and to successfully detect and identify outliers when GPS measurement redundancy is high enough. However, it may fail to detect a fault when there are not enough GPS measurements (at least 3 satellites are required, then detection performance depends if the error moves the computed position out of the drivable space or not), or identify a good measurement as a fault when there are more erroneous measurements than good observations.

Improvements to the fault detection capability of the method could be obtained by the computation of an inner solution subpaving along with the outer subpaving, or by checking particular points like box centers. Finally, this paper has proposed a purely static approach ; A dynamic approach could improve the overall performance by taking time dependency into account.

Fig. 5 .

 5 Fig. 5. Outlier identified: [y 3 ]

Fig. 7 .Fig. 8 .Fig. 9 .

 789 Fig. 7. Path followed around the mairie of the 12 th arrondissement in Paris.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Fault detection and identification failure at epoch #89. The circle represents ground truth position.


Luca Rose
email: luca.rose@thalesgroup.com

Samir M Perlaza
email: samir.perlaza@supelec.fr

Mérouane Debbah
email: merouane.debbah@supelec.fr

Christophe J Le Martret
email: .christophe.lemartret@thalesgroup.com

Distributed Power Allocation with SINR Constraints Using Trial and Error Learning

Keywords: Learning, power control, trial and error, Nash equilibrium, spectrum sharing

In this paper, we address the problem of global transmit power minimization in a self-configuring network where radio devices are subject to operate at a minimum signal to interference plus noise ratio (SINR) level. We model the network as a parallel Gaussian interference channel and we introduce a fully decentralized algorithm (based on trial and error) able to statistically achieve a configuration where the performance demands are met. Contrary to existing solutions, our algorithm requires only local information and can learn stable and efficient working points by using only one bit feedback. We model the network under two different game theoretical frameworks: normal form and satisfaction form. We show that the converging points correspond to equilibrium points, namely Nash and satisfaction equilibrium. Similarly, we provide sufficient conditions for the algorithm to converge in both formulations. Moreover, we provide analytical results to estimate the algorithm's performance, as a function of the network parameters. Finally, numerical results are provided to validate our theoretical conclusions.

I. INTRODUCTION

In this paper, we consider a network where several transmitter-receiver pairs communicate through a common bandwidth divided into several orthogonal sub-bands, thus, subject to mutual interference. All devices must guarantee certain quality of service (QoS), expressed in terms of signal to interference plus noise ratio (SINR). The behaviour of the devices is designed for achieving a stable network operating point (equilibrium) where the maximum number of communicating pairs satisfy their QoS with the minimum global power consumption. Network operating point must be achieved by the radio devices in a fully decentralized way by selecting their power allocation policy, i.e., selecting a sub-band and a power level for each transmission. In this scenario, all communications take place in absence of a centralized controller and neither cooperation nor exchange of information between different pairs are considered. For instance, this scenario may model the case of tactical radios and ad hoc networks, where, in order to set power and channel, current solutions require a certain level of cooperation with exchange of information between the devices or a manual setting. The closest works to ours are [START_REF] Iiduka | Fixed point optimization algorithm and its application to power control in CDMA data networks[END_REF], [START_REF] Altman | S-modular games and power control in wireless networkse[END_REF] and [START_REF] Pang | Distributed power allocation with rate constraints in Gaussian parallel interference channels[END_REF]. In [START_REF] Iiduka | Fixed point optimization algorithm and its application to power control in CDMA data networks[END_REF], variational inequality theory is used to design a centralized power control algorithm for this scenario, in [START_REF] Altman | S-modular games and power control in wireless networkse[END_REF] the authors show that, if the assumption of S-modularity holds for the corresponding game, then best response dynamics [START_REF] Rose | Learning equilibria with partial information in decentralized wireless networks[END_REF] converges to a generalized Nash equilibrium (GNE); in [START_REF] Pang | Distributed power allocation with rate constraints in Gaussian parallel interference channels[END_REF], the authors provide, under the assumption of low interference, a sufficient condition for the convergence of the iterative water-filling algorithm to a GNE. It is worth noting that the works in [START_REF] Iiduka | Fixed point optimization algorithm and its application to power control in CDMA data networks[END_REF], [START_REF] Altman | S-modular games and power control in wireless networkse[END_REF] and [START_REF] Pang | Distributed power allocation with rate constraints in Gaussian parallel interference channels[END_REF] assume a compact and convex set of actions, i.e, the possible power allocation (PA) vectors may take any value in the corresponding simplex. Conversely, in our work, we consider a finite action set by quantizing the possible available powers into a certain amount of levels. Basically, this is because in practice power levels must be expressed in a finite amount of bits. Moreover, several authors have pointed out that better global performance (e.g. spectral efficiency) is achieved when the set of PA vectors is substantially reduced [START_REF] Popescu | Water filling may not good neighbors make[END_REF], [START_REF] Rose | On the Nash equilibria in decentralized parallel interference channels[END_REF], [START_REF] Altman | A Braess type paradox in power control over interference channels[END_REF], [START_REF] Perlaza | On the benefits of bandwidth limiting in decentralized vector multiple access channels[END_REF]. Indeed, this effect has been reported as a Braess kind paradox [START_REF] Braess | On a paradox of traffic planning[END_REF]. In this paper, our contribution is twofold: first, we present a fully decentralized learning algorithm able to keep the SINR level above a certain threshold a high proportion of the time, by means of only one bit feedback and relying only on local information [START_REF] Rose | Learning equilibria with partial information in decentralized wireless networks[END_REF]; second, we analytically study the convergence properties and the convergence point, which is shown to be an efficient Nash equilibrium (NE) in terms of global performance. The paper is organized as follows. In Sec. II, we describe the wireless scenario and we formalize the problem; in Sec. III, we model the system as a game in normal form and in satisfaction form; in Sec. IV we present the trial and error algorithm as introduced in [START_REF] Young | Learning by trial and error[END_REF]; in Sec. V, we present a formal analytical study of the convergence properties (i.e., expected number of iterations to reach the NE and the satisfaction equilibrium (SE)), as well as, the expected fraction of time the system is at the NE and at the SE; in Sec. VI we validate our analysis through numerical simulations; the paper is concluded in Sec. VII.

II. SYSTEM MODEL

Let us consider the system described in Fig. 1. Here, a set K = {1, ..., K} of transmitter-receiver pairs share a set C = b (1) , ..., b (C) of orthogonal sub-bands. Transmitter k is allowed to transmit over one sub-band at a time at a given power level. We denote by p k ∈ P, with P = {0, ..., P M AX }, |P| = Q, and b k ∈ C, the power level and the frequency sub-band chosen by transmitter k respectively. We denote by To communicate, pairs have to achieve a sufficient SINR level, i.e., SIN R k > Γ where we denote by Γ the minimum SINR threshold allowing transmission. Receivers treat interference as Gaussian noise, thus:

Tx Rx k = 1 k = 2 k = K
SIN R k (a) = p k g (b k ) k,k σ 2 + l∈K\k p l g (b l ) k,l 1 {b l =b k } , (1)
where g (b) k,l represents the channel power gain between transmitter l and receiver k over sub-band b, σ 2 is the power of the thermal noise assumed constant over the whole spectrum and 1 {} represents the indicator function. In our scenario, we assume block-fading channels, i.e., channel realizations are time invariant for the whole transmission. Our objective is the satisfaction of the SINR constraints for the largest possible set of pairs by using the lowest global energy consumption. Formally, we want the network configuration vector a * to be a solution of the following optimization problem

min p∈P K K k=1 p k (n) s.t. SIN R k (a) > Γ ∀k ∈ K * , (2)
where we denote by K * ⊆ K the largest subset of links able to simultaneously achieve a sufficient SINR level. Generally, to achieve this goal a central controller knowing all the network's parameters is required. In the following sections, we propose a decentralized algorithm demanding no information on the network which will steer the system to a solution of (2).

III. GAME FORMULATION In this section, we model the scenario presented in Sec 1 in two different formulations: a normal-form game and a satisfaction-form [START_REF] Perlaza | Quality-ofservice provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF] game.

A. Normal form formulation

We model the network described above by the game in normal form

G = K, A, {u k } k∈K . (3)
Here, K represents the set of players, A is the joint set of actions, that is, A = A 1 × A 2 × ... × A K where A k = C × P and we introduce the utility function u k : A → R defined by:

u k (a) = 1 1 + β P M AX -p k P M AX + β1 {SIN R k (a)>Γ} , (4)
where β is a design parameter discussed in Sec V. This function has been designed to be monotonically decreasing with the power consumption, and monotonically increasing with the number of players who achieve the minimum SINR.

In the following, we show that, with this utility function, the NE of the game G can solve the problem stated in [START_REF] Altman | S-modular games and power control in wireless networkse[END_REF]. Moreover, note that to evaluate (4) each transmitter only requires local information, since 1 {SIN R k (a)>Γ} can easily be fed back by the receiver with 1 bit.

Definition 1: (Interdependent game). G is said to be interdependent if for every non-empty subset K + ⊂ K and every action profile a = (a K + , a -K + )1 such that a K + is the action profile of all players in K + , it holds that:

∃i / ∈ K + , ∃a K + = a K + : u i (a K + , a -K + ) = u i (a K + , a -K + ) (5)
In the following, we assume that game G is interdependent. This is a reasonable assumption, since, physically, this means that no link is isolated from the others. The solution concept used under this formulation is the Nash equilibrium, which we define as follows:

Definition 2: (Nash equilibrium in pure strategies). An action profile a * ∈ A is a NE of game G if ∀ k ∈ K and ∀a k ∈ A k u k (a * k , a * -k ) ≥ u k (a k , a * -k ). (6)
To measure the efficiency of each NE, we introduce the social welfare function, defined by the sum of all individual utilities:

W (a) = K k=1 u k (a).

B. Satisfaction form

The satisfaction form is a game theoretical formulation modelling scenarios where players are exclusively interested in the satisfaction of their individual QoS constraints. Let us define the game as

G = K, A, {f k } k∈K , (7)
where K, A follow the previous definitions and the satisfaction correspondence

f k : A -k → R is defined by f k (a -k ) = (a k ∈ A k : SIN R k (a k , a -k , ) ≥ Γ) . (8)
The solution concept used under this formulation is the satisfaction equilibrium (SE) defined as:

Definition 3: (Satisfaction equilibrium). A satisfaction equilib- rium of game G is an action profile a ∈ A such that ∀k ∈ K, a k ∈ f k a -k . (9)
Moreover, we measure the effort of player k due to the use of a particular action a k by using the effort function [START_REF] Perlaza | Quality-ofservice provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF] Φ k : A k → [0, 1]. We can, then, define an efficient satisfaction equilibrium (ESE) as:

Definition 4: (Efficient satisfaction equilibrium). A satisfaction equilibrium a is said to be efficient, if ∀k ∈ K a k ∈ arg min a k ∈f k (a -k ) Φ k (a k ) (10)
In brief, an ESE is an action profile where all players are satisfied and no player may decrease its individual effort by unilateral deviation. Since our optimization problem is to minimize the overall transmit power, we identify the effort by the function:

Φ k (a k ) = p k .

IV. ALGORITHM DESCRIPTION

In this section, we briefly describe the trial and error (TE) algorithm introduced in [START_REF] Young | Learning by trial and error[END_REF], [START_REF] Pradelski | Efficiency and equilibrium in trial and error learning[END_REF]. Later, we characterize the degrees of freedom of the system to fit in our scenario. In TE learning, each player k locally implements a state machine, at each iteration n, a state is defined by the triplet:

Z k (n) = {m k (n), āk (n), ūk (n)} , (11)
where m k (n) ∈ {C, C+, C-, D} represents a "mood", i.e., a characteristic that defines the machine reaction to its experience of the environment, āk ∈ A and ūk ∈ [0, 1] represents a benchmark action and benchmark utility, respectively. There are four possible moods: content (C), watchful (C-), hopeful (C+), discontent (D). In the following, we characterize the behaviour of each player in every possible mood.

• Content

If at stage n player k is content, it uses the benchmarked action āk (n) with probability (1 -) and experiments a new action a k (n) with probability . If at stage n the player decided to experiment, at stage (n + 1) it evaluates the utility u k (n + 1) associated with a k (n) as follows:

if u k (n + 1) < ūk (n) then Z k (n + 1) = Z k (n), otherwise if u k (n + 1) > ūk (n), then, with probability G(u k (n+1)-ū k (n))
, a new action and utility benchmark are set out, i.e., ūk (n + 1) = u k (n + 1) and āk (n + 1) = a k (n), respectively. Here, G(•) must be such that:

0 < G(∆u) < 1 2 , ( 12
)
we opt for a linear formulation: G(∆u) = -0.2∆u + 0.2.

• Hopeful-Watchful

If player k achieves an increment or a decrement in its utility without having experimented at the previous stage, then the mood become hopeful or watchful, according to the following rule:

(i) if u k (n + 1) > ūk (n) then, m k (n + 1) = C+, āk (n + 1) = āk (n) and ūk (n + 1) = ūk (n); (ii) if m k (n + 1) = C-, then āk (n + 1) = āk (n) and ūk (n + 1) = ūk (n).
If player k observes an improvement also at the next stage (i.e., u k (n + 2) > ūk (n + 1)), then the mood switches to content and the benchmark utility is updated with the new one: m k (n + 2) = C and ūk (n+2) = u k (n+1). On the contrary, if a loss is observed also at the next stage (i.e., u k (n + 2) < ūk (n + 1)), then the mood switches to discontent m k (n + 2) = D.

• Discontent

If player k is discontent, it experiments a new action (a k (n)) at each step n. We refer to this behaviour as noisy search. When the corresponding utility u k (n+1) is observed, with probability p = F (u k (n+1) the mood turns to content m k (n + 1) = C, a new action and utility benchmark are set up, ūk (n + 1) = u k (n + 1) and āk (n + 1) = a k (n + 1), while, with probability

(1-p) it continues the noisy search. Note that function F must be such that

0 < F (u) < 1 2K , (13)
we opt for a linear formulation:

F (u) = -0.2 K u + 0.2 K .

A. Algorithm properties

Hereunder, we restate Theorem 1 in [START_REF] Young | Learning by trial and error[END_REF] and Theorem 1 in [START_REF] Pradelski | Efficiency and equilibrium in trial and error learning[END_REF] using our notation.

Theorem 1: Let G have at least one pure Nash equilibrium and let be small enough. Then, a pure Nash equilibrium is played at least (1 -δ) of the time.

This theorem introduces a different notion of convergence. Generally [START_REF] Rose | Learning equilibria with partial information in decentralized wireless networks[END_REF], we say that an algorithm converges when it approaches a certain solution as n → ∞ while, here, it means that this solution is played with a high probability an high proportion of the total time.

Theorem 2: Let G have at least one pure Nash equilibrium and let each player employ TE, then a Nash equilibrium that maximizes the sum utility among all equilibrium states is played a large proportion of the time.

Note that, generally, different equilibria are associated with different social welfare values. Learning algorithms available in the literature [START_REF] Rose | Learning equilibria with partial information in decentralized wireless networks[END_REF], [START_REF] Scutari | Optimal linear precoding strategies for wideband non-cooperative systems based on game theory -part II: Algorithms[END_REF], do not always take into consideration the problem of equilibrium selection, which is a central issue when aiming at global performance.

V. MAIN RESULTS

A. Working point properties

In this section, we present our results based on the previous analysis. Proofs are omitted due to space constraints. Based on the game theoretical formulation in Sec. III and the algorithm properties in Sec. IV we state the following: Theorem 3: Let N = ∅ be the set of NE of G, let β > K and let us denote by K l the number of players satisfied at the l-th NE. Then, TE converges to the NE where K l is maximized. This theorem states that, if β > K, then TE converges to a state where the largest possible number of players are satisfied and are at the NE. Here, β represents the interest a network designer has in satisfying the largest set of players over the minimization of the network power consumption. The next two theorems allow us to link this result with the original global design problem expressed in (2). Theorem 4: Let (i) A † = ∅ be the set of solutions of (2) with K * = K, (ii) N = ∅ be the set of NE of G and N ∩ A † = ∅ and let β > K. Then, TE learning converges to an action profile a * such that a * ∈ N ∩ A † and is an ESE. This theorem links together the concept of ESE of game G , the NE of game G and the solutions of (2). Indeed, when the assumptions are met, the TE algorithm will reach a network state where: (i) all players are satisfied, (ii) the network power consumption is minimized. Note that, generally, it is possible for (2) to have a solution that is not a NE of G.

Theorem 5: Let (2) have no solution for K * = K and fix β > K. Let K * be the largest number of players that can be simultaneously satisfied and let K * m be the m-th set, such that |K * m | = K * , where (2) has a solution; let also be A * m the corresponding set of solutions.

D CK-1 CK-2 C0 Eq

Fig. 2. Markov chain describing the TE algorithm in the network. The state Eq represents a state where all players are in equilibrium (i.e., SE or NE). C K-k represents a state where K -k players are using a correct action (i.e., an action that is satisfying or is optimal w.r.t. the others). D represents a state where one player is discontent.

Let us define A * = m A * m and N = ∅ the set of NE. Then, TE learning converges to an action profile a * such that a * ∈ N ∩ A * .

The previous theorem states that, when some players cannot satisfy their SINR condition, the TE algorithm selects the subset K * m among all possible K * such that: (i) the highest number of players are satisfied, (ii) the network power consumption is minimized (with the unsatisfied players employing 0 power).

Corollary 1: Let ∀k and ∀b be g

(b) k,k ≥ Γσ 2 P M AX , let C ≥ K and fix β > K.
Then, TE converges to a solution of (2).

Basically, this corollary means that, if transmitters and receivers are satisfiable on each channel (high SNR regime), then TE converges to an optimal working point.

B. Convergence analysis

TE algorithm defines a discrete time Markov chain (DTMC)

on the set of the states. Studying the behaviour of the algorithm on the complete chain is an intractable problem due to the number of states, transitions and parameters. In the following, we provide an approximated DTMC that allows us to estimate: (a) the expected converging time at the NE and at the SE, (b) the expected fraction of time the system is at the NE and at the SE. Under the light of the description made in Sec. IV, we state the following: (i) the fraction of time spent in the watchful or hopeful states is negligible compared to the one in discontent or content one; (ii) at any time, the probability of having more than one player discontent is negligible. In the following, we assume C > K and a simplified channel model, defined as

g (c) k,k = 1 ∀k, ∀c g (c) j,k = 1 2 ∀k, ∀j = k, ∀c . ( 14
)
In Sec. VI we will show that these results are good approximations also under less restrictive conditions. The resulting DTMC for studying TE behaviour is represented in Fig. 2. When interested in convergence time and occupancy frequency of the NE, state Eq represents the NE, and C K-k a state where K -k players are using an individually optimal action and D a state where one player is discontent. The transition probabilities we evaluate are listed hereunder, the detailed description is omitted due to space constraints.

P (N E, D) = K(K-1) 2 2 C 2 Q-1 Q 2 (15) P (D, N E) = (C-K+1)) CQ (16)
P (D, C K-k ) = (C-K+k) C k (K-1)! (K-k)! (17)
P (C K-k , C K-k-1 ) = (K -k) C-k CQ 1+G(∆u) . (18)
The analysis of this DTMC allows us to state the following theorems:

Theorem 6: The expected number of iterations needed before reaching the NE for the first time TNE is bounded as follows:

TNE ≤ CQ (1+G(∆u)) (C -K) 1 + log K (C -K + 1) C + 1 TNE ≥ CQ (1+G(∆u)) (C -K) γ + log K (C -K) C ;
where, γ 0.577 is the Euler-Mascheroni constant.

Note that, the time demanded to converge is directly proportional to the degree of freedom (i.e., |A k | = CQ) and inversely to the experimentation probability . Nonetheless, as we shall see, choosing a large increases the instability of the NE and, consequentially, the network performance.

Theorem 7: The expected fraction of time the system is at a NE (1 -δ) is:

(1 -δ) = 1 1 + P (N E, D)T BN E , (19)
where

T BN E ≤ K k=1 P (D, C K-k )T CN E (k) + P (D, N E) (1 -P (D, D)) 2 T CN E (k) = CQ 1+G(∆u) (C -K) γ + log K (C -k + 1) C + 1 P (D, D) = 1 -P (D, N E) - K k=1 P (D, C K-k ).
Here, (1 -δ) depends on 1 2 as in (15). This means that, the larger the the shorter the time the system is at a NE. To evaluate convergence time and occupancy frequency of the SE we, again, make use of Fig. 2. In this case, state Eq represents the SE, C K-k is a state where K -k players are satisfied and D a state where one user is discontent. The corresponding transition probabilities are listed hereunder.

P (SE, D) = K(K-1) 2 2 C 2 Q-1 Q 2 (20) P (D, SE) = (C-K+1) C (21) P (D, C K-k ) = 1 C k (K-1)! (K-k)! (C -K + k) (22)
P (C K-k , C K-k-1 ) = (K -k)Q S (C-k) 1+G(∆u) CQ . (23)
Given the model in ( 14) and C > K, the term Q S < Q represents the number of power quantization levels that a player can employ to successfully achieve SIN R k > Γ on any free channel. We can, then, state the following theorems:

Theorem 8: The expected number of iterations needed before reaching the SE for the first time TSE is bounded as follows:

TSE ≤ CQ/Q S (1+G(∆u) (C -K) 1 + log K (C -K + 1) C + 1 TSE ≥ CQ/Q S (1+G(∆u) (C -K) γ + log K (C -K) C .
Under assumption (14), being satisfied is a weaker condition than being at the NE, thus, it results that T N E ≥ T SE . Predictably, larger P M AX and lower Γ increasing Q S , are able to improve the converging speed.

Theorem 9: The expected fraction of time the system is at a SE F SE is:

F SE = 1 1 + P (SE, D)T BSE ( 24
)
where

T BSE ≤ K k=1 P (D, C K-k )T CSE (k) + P (D, SE) (1 -P (D, D)) 2 T CSE (k) = CQ (C -K) Q S γ + log K (C -k + 1) C + 1 P (D, D) = 1 -P (D, SE) - K k=1 P (D, C K-k ).

VI. SIMULATION RESULTS

The purpose of this section is threefold. First, we run simulations to numerically validate the DTMCs introduced in Sec. V, second, we validate the results on more general channel models, then, we evaluate the performance of the algorithm in terms of satisfaction and power employed. The first two experiments have been run for two different sets of parameters. The first set is composed by: K = 3, C = 4, = 0.02 and 6 ≤ Q ≤ 10. The second set is composed by K = 4, C = 5, = 0.02 and 6 ≤ Q ≤ 10. In our first experiment, we run 10 7 iterations to estimate (1 -δ) under two different channel models: the simple channels expressed in (14) and a Rayleigh channel. The results are summarized in Figure 3. As we can see, the analysis, brought on particular channel model, proves to be sufficiently precise also under more general formulations. In our second experiment, we estimated the converging time and compared with the analytical results in Figure 4. As we can see, increasing the action set dimension, i.e., increasing C or Q, brings slower convergence rate since the algorithm requires more time to explore all the possibilities. Note that, here, convergence time means the time needed by the system to work at the NE for the first time. The third experiment's parameter set is composed as follows: K = 4, C = 5, = 0.02 Q = 8 with the simplified channel model as in (14). Here, we have run 10 3 tests, each one composed by 6000 iteration of TE. The results are showed in Fig 5, where the upper curve represents the fraction of players satisfied, while the lower curve represents the ratio between the average power employed by the network and the optimal power that should be employed to satisfy all the players. In average, in accordance with Figure 3, the system reaches an optimal equilibrium (all players satisfied Lower bound K=4, C=5 Fig. 4. Expected time for the system to reach the Nash equilibrium. On the left, results for a system with K = 4 players and C = 5 channel. On the right, results for a system with K = 3 players and C = 4 channels. and minimum amount of power employed) after around 2200 iterations. Note that, even though, for some specific scenarios, this number may be too high, the configurations selected by the algorithm before the convergence are just slightly inefficient. Indeed, a configuration where all the players are able to satisfy their SINR constraints is averagely reached after 600 iterations. Moreover, before this, we observe that only a fraction of satisfiable players is satisfied, in spite of the amount of power used.

VII. CONCLUSION

In this paper, we have studied a power control problem in a self configuring decentralized network. We presented a new decentralized algorithm able to steer the network into a working point where the maximum number of transmitterreceiver pairs achieves a sufficient SINR while minimizing the network power consumption. The algorithm does not assume

Iterations

Average network power to optmimum power ratio Fig. 5. Average fraction of players satisfied versus iterations, and ratio between the average power employed and the optimal level of power that should be employed to satisfy the whole network. Available number of channel C = 5, number of players K = 4, quantization level Q = 8.

any prior knowledge of the network and can learn an efficient equilibrium with only one bit of feedback. By assuming a particular channel realization, we have analytically estimated the expected performance of the algorithm through a Markov chain description of the algorithm behaviour. Finally we have shown through Monte-Carlo simulations that the analysis is approximatively correct also for general channel models.

VIII. ACKNOWLEDGEMENT

This research work was carried out in the framework of the CORASMA EDA Project B-0781-IAP4-GC.

Fig. 1 .

 1 Fig. 1. System model

Fig. 3 .

 3 Fig. 3. Fraction of time the system is at the NE. Comparison between theoretical line and simulation results for two set of data and different channels: Rayleigh and simple one as in (14).

Here, a -K + refers to the action profile of all the players that are not in K +


James Cummings

Sebastian Rahtz

Lou Burnard

Syd Bauman

Betrand Gaiffe

Laurent Romary

Piotr Banski

Future Developments for TEI ODD

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Future Developments for TEI ODD

Cummings, James, University of Oxford, UK, James.Cummings@oucs.ox.ac.uk Rahtz, Sebastian, University of Oxford, UK, Sebastian.Rahtz@oucs.ox.ac.uk Burnard, Lou, TGE-Adonis, France, lou.burnard@tge-adonis.fr Bauman, Syd, Brown University, USA, Syd_Bauman@Brown.edu Gaiffe, Bertrand, ATILF, France, bertrand.gaiffe@atilf.fr Romary,Laurent,INRIA,France,laurent.romary@inria.fr Bański,Piotr,HUB & IDS,Poland,bansp@o2.pl The purpose of this panel is to look at the application and future development of the literate programming system known as ODD which was developed for the Text Encoding Initiative (TEI) and underlies every single use of the TEI.

Though strongly influenced by data modelling techniques characteristic of markup languages such as SGML and XML, the conceptual model of the Text Encoding Initiative is defined independently of any particular representation or implementation. The objects in this model, their properties, and their relationships are all defined using a special TEI vocabulary called ODD (for One Document Does-it-all); in this way, the TEI model is used to define itself and a TEI specification using that model is, formally, just like any other kind of resource defined using the TEI. An application selects the parts of the TEI model it wishes to use, and any modifications it wishes to make of them, by writing a TEI specification (a TEI ODD document), which can then be processed by appropriate software to generate instance documents relevant to the given application. Typically, these instance documents will consist of both user documentation, such as project manuals for human use, and system documentation, such as XML schemas or DTDs, sets of Schematron constraints etc. for machine use. In this respect ODD is a sophisticated re-implementation of the "literate programming" paradigm developed by Don Knuth in the 1970s reimagined as "literate encoding".

One of the requirements for TEI Conformance is that the TEI file "is documented by means of a TEI Conformant ODD file which refers to the TEI Guidelines". In many cases users employ pre-generated schemas from exemplar customizations, but they are usually better served if they use the TEI ODD markup language, possibly through the Roma web application, to constrain what is available to them thus customizing the TEI model to reflect more precisely their encoding needs. Some of the mechanisms supporting this extensibility are relatively new in the TEI Guidelines, and users are only now beginning to recognize their potential. We believe that there is considerable potential for take-up of the TEI system beyond its original core constituencies in language engineering, traditional philology, digital libraries, and digital humanities in general. Recent additions to the TEI provide encoding schemes for database-like information about persons and places to complement their existing detailed recommendations for names and linguistic structures; they have always provided recommendations for software-independent means of authoring scientific documentation, but the ODD framework makes it easier for TEI documents to coexist with other specialist XML vocabularies as well as expanding it to encompass the needs of new specialised kinds of text. It has been successfully used for describing other XML schemas, notably the W3C ITS (Internationalisation Tagset) and ISO TC37 SC4 standards documents; more recently its facilities have greatly simplified the task of extending the TEI model to address the needs of other research communities, such as musicologists and genetic editors.

We believe that the current ODD system could be further enhanced to provide robust support for new tools and services; an important step is to compare and contrast its features with those of other "meta-encoding" schemes and consider its relationship to ontological description languages such as OWL. The potential role of ODD in the development of the semantic web is an intriguing topic for investigation. This panel brings together some of the world"s most knowledgeable users and architects of the TEI ODD language, including several who have been responsible for its design and evolution over the years. We will debate its strengths, limitations, and future development. Each speaker will focus on one aspect, problem, or possible development relating to TEI ODD before responding to each others suggestions and answering questions from the audience. Lou Burnard will introduce the history and practical use of ODD in TEI, and describe its relevance as a means of introducing new users to the complexity of the TEI. Sebastian Rahtz will talk about the processing model for ODD, and the changes required to the language to model genuinely symmetric, and chainable, specifications. Bertrand Gaiffe will look at some of the core mechanisms within ODD, and suggest that model classes that gather elements (or other model classes) for their use into content models could be better as underspecified bags instead of sets. Syd Bauman will discuss co-occurrence constraints, pointing out that ODD"s lack of support for this feature is a significant limitation, but also that it can often be worked around by adding Schematron to an ODD. Laurent Romary and Piotr Banski will describe issues in drafting ODD documents from scratch, in particular in the context of ISO standardisation work, introducing proposals to make ODD evolve towards a generic specification environment.

We believe that the DH2012 conference offers a useful outreach opportunity for the TEI to engage more closely with the wider DH community, and to promote a greater awareness of the power and potential of the TEI ODD language. We also see this as an invaluable opportunity to obtain feedback about the best ways of developing ODD in the future, thereby contributing to the TEI Technical Council"s ongoing responsibility to maintain and enhance the language.

Organization

The 5 speakers will each give a 15-minute introduction to a problem or possible development that relates to TEI ODD. After this the organizer will moderate discussion between members of the panel on a number of questions before opening the discussion to questions from the audience.

Speakers

• Lou Burnard, lou.burnard@tge-adonis.fr, TGE-Adonis

•

  Syd Bauman, syd_bauman@brown.edu, Brown University Center for Digital Scholarship • Bertrand Gaiffe, bertrand.gaiffe@atilf.fr, ATILF • Sebastian Rahtz, sebastian.rahtz@oucs.ox.ac.uk, University of Oxford • Laurent Romary & Piotr Bański (Piotr speaking), laurent.romary@inria.fr, bansp@o2.pl, Inria, HUB & IDS Organizer James Cummings, james.cummings@oucs.ox.ac.uk, University of Oxford references Burnard, L., and R. Rahtz (2004). RelaxNG with Son of ODD. Extreme Markup Languages 2004, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.124.7139&rep=rep1&type =pdf