Cristiano Ciuti

Pierre Nataf

Comment on "Superradiant Phase Transitions and the Standard Description of Circuit QED"

In a recent letter [1], Viehmann, von Delft and Marquardt claim that a superradiant phase transition [2] for a chain of Cooper pair boxes capacitively coupled to a transmission line resonator is prevented by the Thomas-Reiche-Kuhn (TRK) sum rule for the electron dipole operator. The authors consider a closed electron box model for the artificial atoms coupled to the quantized vector potential of a cavity photon mode. Since the authors are aware that the standard model of Cooper pair boxes [3] predicts such transition [4], they conclude that such standard Hamiltonian description in circuit quantum electrodynamics (QED) must have a problem in the limit of a large number N of Cooper pair boxes capacitively coupled to a resonator (the phase transition is expected to occur for N ≫ 1). We believe that the main claim in Ref. [1] is unproven as argued below.

(i) While the superradiant phase transition for Cooper pair boxes involves the superconducting degrees of freedom and dressed fields in the circuit, the authors do not consider at all any link between the TRK sum rule for the electron dipole operator matrix elements and the number of Cooper pairs or the superconducting phase difference across the Josephson junctions. By contrast, in the cavity QED case with real atoms [4], the link between the TRK electron sum rule and the superradiant phase transition is direct, because the transition affects directly the electron dipole operator associated to the atomic two-level systems. Moreover, it is unfortunate that Viehmann et al. [1] do not show at all how the TRK sum rule for the electron dipole operator modifies the standard quantization of circuit QED Hamiltonians.

(ii) In their section 'Microscopic description of Circuit QED' (page 3 of Ref. [1]), Viehmann et al. describe via the Hamiltonian H mic each artificial atom as a closed box with a fixed number n k of electrons (k = 1, 2, ..., N is the artificial atom index), hence they take the same kind of Hamiltonian for the cavity QED case as in the first part of their letter [1] and as in the first part of Ref. [4]. It is surprising that the authors [1] (iii) The generalization of the cavity QED no-go theorem to the multilevel atomic case with an arbitrary spectrum presented in Ref. [1] is based on the assumption that in the thermodynamic limit it is always possible to neglect the transitions between excited atomic levels to determine the existence of the superradiant phase transition. We show here a concrete counterexample showing that such key assumption in Ref. [1] can be violated. Let us consider a generalized Dicke model with

N 3-level sys- tem {|0 k , |1 k , |2 k } (for k = 1...N ) with the transitions |0 k → |1 k and |1 k → |2 k coupled
to the same photon mode via the coupling λ 01 and λ 12 respectively and no optical coupling between |0 k and |2 k (λ 02 = 0, this is the well-known ladder configuration). If λ 01 = 0, the system can be solved with known methods [2] since the two levels |1 k and |2 k coupled to the same photon mode form a Dicke system: for λ 12 above a critical coupling, a superradiant phase transition can occur with a ground state involving only the states |1 k and |2 k and not |0 k , while in the normal phase only the |0 k state is populated. This is a first order phase transition and so the population of excited atomic levels in the ground state jumps discontinuously to a macroscopic number. Such a jump invalidates a perturbative expansion in terms of number of excited atoms as done in Ref. [1]. At least for λ 01 ≪ λ 12 , a first-order transition can occur in a such a counterexample model, with the dominant weight in the superradiant ground states carried by the excited |1 k → |2 k transition. Note that the treatment in Ref. [1] considers only the role of the squared vector potential Â2 term for transitions from the ground level |0 ; since the TRK sum rule implies different, less stringent inequalities for the strength of the excited state transitions, the reasoning by Viehmann et al. does not cover this counterexample. Using the language of phase transitions, for the multilevel case Viehmann et al. [1] have implicitly considered only the case of second-order phase transitions (as in the standard case with two-level systems [2]), while with multilevel systems superradiant transitions of the first-order with a more abrupt change of the ground state properties need to be considered, as explicitly shown by our 3-level counterexample for the case of a single photon mode or by other closely related systems [START_REF] Hayn | A first-order superradiant transition with 3-level systems[END_REF]. The issue of multilevel superradiant phase transitions is therefore open even in atomic cavity QED and needs to be explored further in the future.

In conclusion, while we agree with the authors of Ref.

  in their microscopic model do not consider the role of the gate chemical potential, controlling the population of Cooper pairs in the superconducting box. In fact, for a proper gate voltage and for a capacitance energy E C much larger than the Josephson energy E J , the ground state |g and first excited state |e of a Cooper pair box are |g ∝ (|n + |n + 1 ), |e ∝ (|n -|n + 1 ), where n is an integer number of Cooper pairs which have Josephson tunneled into the box: hence the number of Cooper pairs is not fixed in such states.


Olivier Finkel
email: finkel@logique.jussieu.fr

The Determinacy of Context-Free Games

Keywords: Automata and formal languages, logic in computer science, Gale-Stewart games, Wadge games, determinacy, context-free games, 1-counter automaton, models of set theory, independence from the axiomatic system ZFC

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of ω-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W (L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W (L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W (L(A), L(B)).

Introduction

Two-players infinite games have been much studied in Set Theory and in Descriptive Set Theory, see [START_REF] Kechris | Classical descriptive set theory[END_REF][START_REF] Jech | Set theory[END_REF]. In particular, if X is a (countable) alphabet having at least two letters and A ⊆ X ω , then the Gale-Stewart game G(A) is an infinite game with perfect information between two players. Player 1 first writes a letter a 1 ∈ X, then Player 2 writes a letter b 1 ∈ X, then Player 1 writes a 2 ∈ X, and so on . . . After ω steps, the two players have composed an infinite word x = a 1 b 1 a 2 b 2 . . . of X ω . Player 1 wins the play iff x ∈ A, otherwise Player 2 wins the play. The game G(A) is said to be determined iff one of the two players has a winning strategy. A fundamental result of Descriptive Set Theory is Martin's Theorem which states that every Gale-Stewart game G(A), where A is a Borel set, is determined [START_REF] Kechris | Classical descriptive set theory[END_REF].

On the other hand, in Computer Science, the conditions of a Gale Stewart game may be seen as a specification of a reactive system, where the two players are respectively a non terminating reactive program and the "environment". Then the problem of the synthesis of winning strategies is of great practical interest for the problem of program synthesis in reactive systems. In particular, if A ⊆ X ω , where X is here a finite alphabet, and A is effectively presented, i.e. accepted by a given finite machine or defined by a given logical formula, the following questions naturally arise, see [START_REF] Thomas | On the synthesis of strategies in infinite games[END_REF][START_REF] Lescow | Logical specifications of infinite computations[END_REF]: (1) Is the game G(A) determined ? (2) If Player 1 has a winning strategy, is it effective, i.e. computable ? (3) What are the amounts of space and time necessary to compute such a winning strategy ? Büchi and Landweber gave a solution to the famous Church's Problem, posed in 1957, by stating that in a Gale Stewart game G(A), where A is a regular ωlanguage, one can decide who is the winner and compute a winning strategy given by a finite state transducer, see [START_REF] Thomas | Church's problem and a tour through automata theory[END_REF] for more information on this subject. In [START_REF] Thomas | On the synthesis of strategies in infinite games[END_REF][START_REF] Lescow | Logical specifications of infinite computations[END_REF] Thomas and Lescow asked for an extension of this result where A is no longer regular but deterministic contextfree, i.e. accepted by some deterministic pushdown automaton. Walukiewicz extended Büchi and Landweber's Theorem to this case by showing first in [START_REF] Walukiewicz | Pushdown processes: games and model checking[END_REF] that that one can effectively construct winning strategies in parity games played on pushdown graphs and that these strategies can be computed by pushdown transducers. Notice that later some extensions to the case of higherorder pushdown automata have been established.

In this paper, we first address the question (1) of the determinacy of Gale-Stewart games G(A), where A is a context-free ω-language accepted by a (non-deterministic) pushdown automaton, or even by a 1-counter automaton. Notice that there are some context-free ω-languages which are (effective) analytic but non-Borel and thus the determinacy of these games can not be deduced from Martin's Theorem of Borel determinacy. On the other hand, Martin's Theorem is provable in ZFC, the commonly accepted axiomatic framework for Set Theory in which all usual mathematics can be developped. But the determinacy of Gale-Stewart games G(A), where A is an (effective) analytic set, is not provable in ZFC; Martin and Harrington have proved that it is a large cardinal assumption equivalent to the existence of a particular real, called the real 0 ♯ , see [START_REF] Jech | Set theory[END_REF]page 637]. We prove here that the determinacy of Gale-Stewart games G(A), whose winning sets A are accepted by real-time 1-counter Büchi automata, is equivalent to the determinacy of (effective) analytic Gale-Stewart games and thus also equivalent to the existence of the real 0 ♯ . Next we consider Wadge games which were firstly studied by Wadge in [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF] where he determined a great refinement of the Borel hierarchy defined via the notion of reduction by continuous functions. These games are closely related to the notion of reducibility by continuous functions. For L ⊆ X ω and L ′ ⊆ Y ω , L is said to be Wadge reducible to L ′ iff there exists a continuous function f : X ω → Y ω , such that L = f -1 (L ′ ); this is then denoted by L ≤ W L ′ . On the other hand, the Wadge game W (L, L ′ ) is an infinite game with perfect information between two players, Player 1 who is in charge of L and Player 2 who is in charge of L ′ . And it turned out that Player 2 has a winning strategy in the Wadge game W (L, L ′ ) iff L ≤ W L ′ . It is easy to see that the determinacy of Borel Gale-Stewart games implies the determinacy of Borel Wadge games. On the other hand, Louveau and Saint-Raymond have proved that this latter one is weaker than the first one, since it is already provable in second-order arithmetic, while the first one is not. It is also known that the determinacy of (effective) analytic Gale-Stewart games is equivalent to the determinacy of (effective) analytic Wadge games, see [START_REF] Louveau | The strength of Borel Wadge determinacy[END_REF]. We prove in this paper that the determinacy of Wadge games between two players in charge of ω-languages accepted by 1counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy, and thus also equivalent to the existence of the real 0 ♯ .

Then, using some recent results from [START_REF] Finkel | The complexity of infinite computations in models of set theory[END_REF] and some results of Set Theory, we prove that, (assuming ZFC is consistent), one can effectively construct a 1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W (L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W (L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W (L(A), L(B)).

The paper is organized as follows. We recall some known notions in Section 2. We study context-free Gale-Stewart games in Section 3 and context-free Wadge games in Section 4. Some concluding remarks are given in Section 5.

Recall of some known notions

We assume the reader to be familiar with the theory of formal (ω-)languages [START_REF] Staiger | ω-languages[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. We recall the usual notations of formal language theory.

If Σ is a finite alphabet, a non-empty finite word over Σ is any sequence x = a 1 . . . a k , where a i ∈ Σ for i = 1, . . . , k , and k is an integer ≥ 1. The length of x is k, denoted by |x|. The empty word has no letter and is denoted by λ; its length is 0. Σ ⋆ is the set of finite words (including the empty word) over Σ. A (finitary) language V over an alphabet Σ is a subset of Σ ⋆ .

The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a 1 . . . a n . . ., where for all integers i ≥ 1, a i ∈ Σ. When σ = a 1 . . . a n . . . is an ω-word over Σ, we write σ

(n) = a n , σ[n] = σ(1)σ(2) . . . σ(n) for all n ≥ 1 and σ[0] = λ.
The usual concatenation product of two finite words u and v is denoted u.v (and sometimes just uv). This product is extended to the product of a finite word u and an ω-word v: the infinite word u.v is then the ω-word such that:

(u.v)(k) = u(k) if k ≤ |u| , and (u.v)(k) = v(k -|u|) if k > |u|.
The set of ω-words over the alphabet Σ is denoted by Σ ω . An ω-language V over an alphabet Σ is a subset of Σ ω , and its complement (in

Σ ω ) is Σ ω -V , denoted V -.
The prefix relation is denoted ⊑: a finite word u is a prefix of a finite word v (respectively, an infinite word v), denoted u ⊑ v, if and only if there exists a finite word w (respectively, an infinite word w), such that v = u.w.

If L is a finitary language (respectively, an ω-language) over the alphabet Σ then the set Pref(L) of prefixes of elements of L is defined by

Pref(L) = {u ∈ Σ ⋆ | ∃v ∈ L u ⊑ v}.
We now recall the definition of k-counter Büchi automata which will be useful in the sequel.

Let k be an integer ≥ 1. A k-counter machine has k counters, each of which containing a non-negative integer. The machine can test whether the content of a given counter is zero or not. And transitions depend on the letter read by the machine, the current state of the finite control, and the tests about the values of the counters. Notice that in this model some λ-transitions are allowed. During these transitions the reading head of the machine does not move to the right, i.e. the machine does not read any more letter.

Formally a k-counter machine is a 4-tuple M=(K, Σ, ∆, q 0 ), where K is a finite set of states, Σ is a finite input alphabet, q 0 ∈ K is the initial state, and

∆ ⊆ K × (Σ ∪ {λ}) × {0, 1} k × K × {0, 1, -1} k is the transition relation. The k-counter machine M is said to be real time iff: ∆ ⊆ K × Σ × {0, 1} k × K × {0, 1, -1} k , i.e. iff there are no λ-transitions.
If the machine M is in state q and c i ∈ N is the content of the i th counter C i then the configuration (or global state) of M is the (k + 1)-tuple (q, c 1 , . . . , c k ).

For a ∈ Σ ∪ {λ}, q, q ′ ∈ K and (c 1 , . . . , c k ) ∈ N k such that c j = 0 for j ∈ E ⊆ {1, . . . , k} and c j > 0 for j / ∈ E, if (q, a, i 1 , . . . , i k , q ′ , j 1 , . . . , j k ) ∈ ∆ where i j = 0 for j ∈ E and i j = 1 for j / ∈ E, then we write:

a : (q, c 1 , . . . , c k ) → M (q ′ , c 1 + j 1 , . . . , c k + j k ).
Thus the transition relation must obviously satisfy: if (q, a, i 1 , . . . , i k , q ′ , j 1 , . . . , j k ) ∈ ∆ and i m = 0 for some m ∈ {1, . . . , k} then j m = 0 or j m = 1 (but j m may not be equal to -1).

Let σ = a 1 a 2 . . . a n . . . be an ω-word over Σ. An ω-sequence of configurations r = (q i , c

i 1 , . . . c i k ) i≥1 is called a run of M on σ iff: (1) (q 1 , c 1 1 , . . . c 1 k ) = (q 0 , 0, . . . , 0) (2) for each i ≥ 1, there exists b i ∈ Σ∪{λ} such that b i : (q i , c i 1 , . . . c i k ) → M (q i+1 , c i+1 1 , . . . c i+1 k ) and such that a 1 a 2 . . . a n . . . = b 1 b 2 . . . b n . . .
For every such run r, In(r) is the set of all states entered infinitely often during r.

Definition 2.1 A Büchi k-counter automaton is a 5-tuple M=(K, Σ, ∆, q 0 , F ), where M ′ =(K, Σ, ∆, q 0 ) is a k-counter machine and F ⊆ K is the set of accepting states. The ω-language accepted by M is:

L(M)= {σ ∈ Σ ω | there exists a run r of M on σ such that In(r) ∩ F = ∅}
The class of ω-languages accepted by Büchi k-counter automata is denoted BCL(k) ω . The class of ω-languages accepted by real time Büchi k-counter automata will be denoted r-BCL(k) ω . The class BCL(1) ω is a strict subclass of the class CFL ω of context free ω-languages accepted by Büchi pushdown automata.

We assume the reader to be familiar with basic notions of topology which may be found in [Kec95, LT94, Sta97, PP04]. There is a natural metric on the set Σ ω of infinite words over a finite alphabet Σ containing at least two letters which is called the prefix metric and is defined as follows. v) where l pref(u,v) is the first integer n such that the (n + 1) st letter of u is different from the (n + 1) st letter of v. This metric induces on Σ ω the usual Cantor topology in which the open subsets of Σ ω are of the form

For u, v ∈ Σ ω and u = v let δ(u, v) = 2 -l pref(u,
W.Σ ω , for W ⊆ Σ ⋆ . A set L ⊆ Σ ω is a closed set iff its complement Σ ω -L is an open set. For V ⊆ Σ ⋆ we denote Lim(V ) = {x ∈ Σ ω | ∃ ∞ n ≥ 1 x[n] ∈ V }
the set of infinite words over Σ having infinitely many prefixes in V . Then the topological closure Cl(L) of a set L ⊆ Σ ω is equal to Lim(Pref(L)). Thus we have also the following characterization of closed subsets of

Σ ω : a set L ⊆ Σ ω is a closed subset of the Cantor space Σ ω iff L = Lim(Pref(L)).
We now recall the definition of the Borel Hierarchy of subsets of X ω .

Definition 2.2 For a non-null countable ordinal α, the classes Σ 0 α and Π 0 α of the Borel Hierarchy on the topological space X ω are defined as follows: Σ 0 1 is the class of open subsets of X ω , Π 0 1 is the class of closed subsets of X ω , and for any countable ordinal α ≥ 2:

Σ 0 α is the class of countable unions of subsets of X ω in γ<α Π 0 γ . Π 0 α is the class of countable intersections of subsets of X ω in γ<α Σ 0 γ . A set L ⊆ X ω is Borel iff it is in the union α<ω 1 Σ 0 α = α<ω 1 Π 0 α ,
where ω 1 is the first uncountable ordinal.

There are also some subsets of X ω which are not Borel. In particular the class of Borel subsets of X ω is strictly included into the class Σ 1 1 of analytic sets which are obtained by projection of Borel sets. The co-analytic sets are the complements of analytic sets.

Definition 2.3 A subset A of X ω is in the class Σ 1 1 of analytic sets iff there exist a finite alphabet Y and a Borel subset B of (X × Y ) ω such that x ∈ A ↔ ∃y ∈ Y ω such that (x, y) ∈ B, where (x, y) is the infinite word over the alphabet X × Y such that (x, y)(i) = (x(i), y(i)) for each integer i ≥ 1.
We now recall the notion of completeness with regard to reduction by continuous functions. For a countable ordinal α ≥ 1, a set F ⊆ X ω is said to be a Σ 0 α (respectively,

Π 0 α , Σ 1 1 )-complete set iff for any set E ⊆ Y ω (with Y a finite alphabet): E ∈ Σ 0 α (respectively, E ∈ Π 0 α , E ∈ Σ 1 1 ) iff there exists a continuous function f : Y ω → X ω such that E = f -1 (F ).
We now recall the definition of classes of the arithmetical hierarchy of ω-languages, see [START_REF] Staiger | ω-languages[END_REF]. Let X be a finite alphabet. An ω-language L ⊆ X ω belongs to the class Σ n if and only if there exists a recursive relation

R L ⊆ (N) n-1 × X ⋆ such that: L = {σ ∈ X ω | ∃a 1 . . . Q n a n (a 1 , . . . , a n-1 , σ[a n + 1]) ∈ R L },
where Q i is one of the quantifiers ∀ or ∃ (not necessarily in an alternating order). An ω-language L ⊆ X ω belongs to the class Π n if and only if its complement X ω -L belongs to the class Σ n .

The class Σ 1 1 is the class of effective analytic sets which are obtained by projection of arithmetical sets. An ω-language L ⊆ X ω belongs to the class Σ 1 1 if and only if there exists a recursive relation

R L ⊆ N × {0, 1} ⋆ × X ⋆ such that: L = {σ ∈ X ω | ∃τ (τ ∈ {0, 1} ω ∧ ∀n∃m((n, τ [m], σ[m]) ∈ R L ))}.
Then an ω-language L ⊆ X ω is in the class Σ 1 1 iff it is the projection of an ω-language over the alphabet X × {0, 1} which is in the class Π 2 . The class Π 1 1 of effective co-analytic sets is simply the class of complements of effective analytic sets.

Recall that the (lightface) class Σ 1 1 of effective analytic sets is strictly included into the (boldface) class Σ 1 1 of analytic sets. Recall that a Büchi Turing machine is just a Turing machine working on infinite inputs with a Büchi-like acceptance condition, and that the class of ω-languages accepted by Büchi Turing machines is the class Σ 1 1 of effective analytic sets [START_REF] Cohen | ω-computations on Turing machines[END_REF][START_REF] Staiger | ω-languages[END_REF]. On the other hand, one can construct, using a classical construction (see for instance [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF]), from a Büchi Turing machine T , a 2-counter Büchi automaton A accepting the same ω-language. Thus one can state the following proposition.

Proposition 2.4 An ω-language L ⊆ X ω is in the class Σ 1 1 iff it is accepted by a non deterministic Büchi Turing machine, hence iff it is in the class BCL(2) ω .

Context-free Gale-Stewart games

We first recall the definition of Gale-Stewart games.

Definition 3.1 ([Jec02]

) Let A ⊆ X ω , where X is a finite alphabet. The Gale-Stewart game G(A) is a game with perfect information between two players. Player 1 first writes a letter a 1 ∈ X, then Player 2 writes a letter b 1 ∈ X, then Player 1 writes a 2 ∈ X, and so on . . . After ω steps, the two players have composed a word x = a 1 b 1 a 2 b 2 . . . of X ω . Player 1 wins the play iff x ∈ A, otherwise Player 2 wins the play.

Let A ⊆ X ω and G(A) be the associated Gale-Stewart game. A strategy for Player 1 is a function F 1 : (X 2 ) ⋆ → X and a strategy for Player 2 is a function

F 2 : (X 2 ) ⋆ X → X. Player 1 follows the strategy F 1 in a play if for each integer n ≥ 1 a n = F 1 (a 1 b 1 a 2 b 2 • • • a n-1 b n-1 ). If
Player 1 wins every play in which she has followed the strategy F 1 , then we say that the strategy F 1 is a winning strategy (w.s.) for Player 1. The notion of winning strategy for Player 2 is defined in a similar manner.

The game G(A) is said to be determined if one of the two players has a winning strategy. We shall denote Det(C), where C is a class of ω-languages, the sentence : "Every Gale-Stewart game G(A), where A ⊆ X ω is an ω-language in the class C, is determined".

Notice that, in the whole paper, we assume that ZFC is consistent, and all results, lemmas, propositions, theorems, are stated in ZFC unless we explicitely give another axiomatic framework.

We can now state our first result.

Proposition 3.2 Det(Σ 1 1 ) ⇐⇒ Det(r-BCL(8) ω ).

Proof. The implication Det(Σ 1 1 ) =⇒ Det(r-BCL(8) ω ) is obvious since r-BCL(8) ω ⊆ Σ 1 1 . To prove the reverse implication, we assume that Det(r-BCL(8) ω ) holds and we are going to show that then every Gale-Stewart game G(A), where A ⊆ X ω is an ω-language in the class Σ 1 1 , or equivalently in the class BCL(2) ω by Proposition 2.4, is determined.

Let then L ⊆ Σ ω , where Σ is a finite alphabet, be an ω-language in the class BCL(2) ω . Let E be a new letter not in Σ, S be an integer ≥ 1, and θ S : Σ ω → (Σ ∪ {E}) ω be the function defined, for all x ∈ Σ ω , by: θ S (x) = x(1).E S .x(2).E S 2 .x(3).E S 3 .x(4) . . . x(n).E S n .x(n + 1).E S n+1 . . . We proved in [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] that if k = cardinal(Σ) + 2, S ≥ (3k) 3 is an integer, then one can effectively construct from a Büchi 2-counter automaton A 1 accepting L a real time Büchi 8counter automaton A 2 such that L(A 2 ) = θ S (L). In the sequel we assume that we have fixed an integer S ≥ (3k) 3 which is even.

Notice that the set θ S (Σ ω ) is a closed subset of the Cantor space Σ ω . An ω-word x ∈ (Σ ∪ {E}) ω is in θ S (Σ ω ) -iff it has one prefix which is not in Pref(θ S (Σ ω )). Let L ′ ⊆ (Σ ∪ {E}) ω be the set of ω-words y ∈ (Σ ∪ {E}) ω for which there is an integer n ≥ 1 such that y

[2n -1] ∈ Pref(θ S (Σ ω )) and y[2n] / ∈ Pref(θ S (Σ ω )).
It is easy to see that L ′ is accepted by a real time Büchi 2-counter automaton.

The class r-BCL(8) ω ⊇ r-BCL(2) ω is closed under finite union in an effective way, so θ S (L) ∪ L ′ is accepted by a real time Büchi 8-counter automaton A 3 which can be effectively constructed from A 2 .

As we have assumed that Det(r-BCL(8) ω ) holds, the game G(θ S (L) ∪ L ′ ) is determined, i.e. one of the two players has a w.s. in the game G(θ S (L) ∪ L ′ ). We now show that the game G(L) is itself determined.

We shall say that, during an infinite play, Player 1 "goes out" of the closed set θ S (Σ ω ) if the final play y composed by the two players has a prefix y

[2n] ∈ Pref(θ S (Σ ω )) such that y[2n + 1] / ∈ Pref(θ S (Σ ω )).
We define in a similar way the sentence "Player 2 goes out of the closed set θ S (Σ ω )".

Assume first that Player 1 has a w.s. F 1 in the game G(θ S (L)∪ L ′ ). Then Player 1 never "goes out" of the set θ S (Σ ω ) when she follows this w.s. because otherwise the final play y composed by the two players has a prefix y[2n] ∈ Pref(θ S (Σ ω )) such that y[2n + 1] / ∈ Pref(θ S (Σ ω )) and thus y / ∈ θ S (L) ∪ L ′ . Consider now a play in which Player 2 does not go out of θ S (Σ ω ). If player 1 follows her w.s. F 1 then the two players remain in the set θ S (Σ ω ). But we have fixed S to be an even integer. So the two players compose an ω-word θ S (x) = x(1).E S .x(2).E S 2 .x(3).E S 3 .x(4) . . . x(n).E S n .x(n + 1).E S n+1 . . . and the letters x(k) are written by player 1 for k an odd integer and by Player 2 for k an even integer because S is even. Moreover Player 1 wins the play iff the ω-word x(1)x(2)x(3) . . . x(n) . . . is in L. This implies that Player 1 has also a w.s. in the game G(L).

Assume now that Player 2 has a w.s. F 2 in the game G(θ S (L)∪L ′ ). Then Player 2 never "goes out" of the set θ S (Σ ω ) when he follows this w.s. because otherwise the final play y composed by the two players has a prefix y

[2n -1] ∈ Pref(θ S (Σ ω )) such that y[2n] / ∈ Pref(θ S (Σ ω ))
and thus y ∈ L ′ hence also y ∈ θ S (L) ∪ L ′ . Consider now a play in which Player 1 does not go out of θ S (Σ ω ). If player 2 follows his w.s. F 2 then the two players remain in the set θ S (Σ ω ). So the two players compose an ω-word θ S (x) = x(1).E S .x(2).E S 2 .x(3).E S 3 .x(4) . . . x(n).E S n .x(n + 1).E S n+1 . . . where the letters x(k) are written by player 1 for k an odd integer and by Player 2 for k an even integer. Moreover Player 2 wins the play iff the ω-word x(1)x(2)x(3) . . . x(n) . . . is not in L. This implies that Player 2 has also a w.s. in the game G(L). Proof. The implications Det(Σ 1 1 ) =⇒ Det(CFL ω ) =⇒ Det(BCL(1) ω ) are obvious since BCL(1) ω ⊆ CFL ω ⊆ Σ 1 1 . To prove the reverse implication Det(BCL(1) ω ) =⇒ Det(Σ 1 1 ), we assume that Det(BCL(1) ω ) holds and we are going to show that then every Gale-Stewart game G(L), where L ⊆ X ω is an ω-language in the class r-BCL(8) ω is determined. Then Proposition 3.2 will imply that Det(Σ 1 1 ) also holds. Let then L(A) ⊆ Γ ω , where Γ is a finite alphabet and A is a real time Büchi 8-counter automaton.

We now recall the following coding which was used in the paper [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF].

Let K = 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 = 9699690 be the product of the eight first prime numbers. An ω-word x ∈ Γ ω was coded by the ω-word

h K (x) = A.C K .x(1).B.C K 2 .A.C K 2 .x(2).B.C K 3 .A.C K 3 .x(3).B . . . B.C K n .A.C K n .x(n).B . . .
over the alphabet Γ 1 = Γ ∪ {A, B, C}, where A, B, C are new letters not in Γ. We are going to use here a slightly different coding which we now define. Let then

h(x) = C K .C.A.x(1).C K 2 .A.C K 2 .C.x(2).B.C K 3 .A.C K 3 .C.A.x(3) . . . . . . C K 2n .A.C K 2n .C.x(2n).B.C K 2n+1 .A.C K 2n+1 .C.A.x(2n + 1) . . .
We now explain the rules used to obtain the ω-word h(x) from the ω-word h K (x).

(1) The first letter A of the word h K (x) has been suppressed.

(2) The letters B following a letter x(2n + 1), for n ≥ 1, have been suppressed.

(3) A letter C has been added before each letter x(2n), for n ≥ 1.

(4) A block of two letters C.A has been added before each letter x(2n + 1), for n ≥ 1. The reasons behind this changes are the following ones. Assume that two players alternatively write letters from the alphabet Γ 1 = Γ ∪ {A, B, C} and that they finally produce an ω-word in the form h(x). Due to the above changes we have now the two following properties which will be useful in the sequel.

(1) The letters x(2n + 1), for n ≥ 0, have been written by Player 1, and the letters x(2n), for n ≥ 1, have been written by Player 2.

(2) After a sequence of consecutive letters C, the first letter which is not a C has always been written by Player 2. We proved in [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] that, from a real time Büchi 8-counter automaton A accepting L(A) ⊆ Γ ω , one can effectively construct a Büchi 1-counter automaton A 1 accepting the ω-language h K (L(A))∪h K (Γ ω ) -. We can easily check that the changes in h K (x) leading to the coding h(x) have no influence with regard to the proof of this result in [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] and thus one can also effectively construct a Büchi 1-counter automaton A 2 accepting the ω-language h(L(A))∪h(Γ ω ) -.

On the other hand we can remark that all ω-words in the form h(x) belong to the ω-language H ⊆ (Γ 1 ) ω of ω-words y of the following form:

y = C n 1 .C.A.x(1).C n 2 .A.C n ′ 2 .C.x(2).B.C n 3 .A.C n ′ 3 .C.A.x(3) . . . . . . C n 2n .A.C n ′ 2n .C.x(2n).B.C n 2n+1 .A.C n ′ 2n+1 .C.A.x(2n + 1) . . .
where for all integers i ≥ 1 the letters x(i) belong to Γ and the n i , n ′ i , are even non-null integers.

An important fact is the following property of H which extends the same property of the set h(Γ ω ). Assume that two players alternatively write letters from the alphabet Γ 1 = Γ ∪ {A, B, C} and that they finally produce an ω-word y in H in the above form. Then we have the two following facts:

(1) The letters x(2n + 1), for n ≥ 0, have been written by Player 1, and the letters x(2n), for n ≥ 1, have been written by Player 2.

(2) After a sequence of consecutive letters C, the first letter which is not a C has always been written by Player 2.

Let now V = Pref(H) ∩ (Γ 1 ) ⋆ .C. So a finite word over the alphabet Γ 1 is in V iff it is a prefix of some word in H and its last letter is a C. It is easy to see that the topological closure of H is

Cl(H) = H ∪ V.C ω .
Notice that an ω-word in Cl(H) is not in h(Γ ω ) iff a sequence of consecutive letters C has not the good length. Thus if two players alternatively write letters from the alphabet Γ 1 and produce an ω-word y ∈ Cl(H)h(Γ ω ) then it is Player 2 who has gone out of the set h(Γ ω ) at some step of the play. This will be important in the sequel.

It is very easy to see that the ω-language H is regular and to construct a Büchi automaton H accepting it. Moreover it is known that the class BCL(1) ω is effectively closed under intersection with regular ω-languages (this can be seen using a classical construction of a product automaton). Thus one can also construct a Büchi 1-counter automaton A 3 accepting the ω-language h(L

(A))∪[h(Γ ω ) -∩ H].
We denote also U the set of finite words u over Γ 1 such that |u| = 2n for some integer n ≥ 1 and u[2n -1] ∈ Pref(H) and u = u[2n] / ∈ Pref(H). Now we set:

L = h(L(A)) ∪ [h(Γ ω ) -∩ H] ∪ V.C ω ∪ U.(Γ 1 ) ω
We have already seen that the ω-language h(L(A))∪[h(Γ ω ) -∩ H] is accepted by a Büchi 1counter automaton A 3 . On the other hand the ω-language H is regular and it is accepted by a Büchi automaton H. Thus the finitary language Pref(H) is also regular, the languages U and V are also regular, and the ω-languages V.C ω and U.(Γ 1 ) ω are regular. This implies that one can construct a Büchi 1-counter automaton A 4 accepting the language L. By hypothesis we assume that Det(BCL(1) ω ) holds and thus the game G(L) is determined. We are going to show that this implies that the game G(L(A)) itself is determined.

Assume firstly that Player 1 has a winning strategy F 1 in the game G(L). If during an infinite play, the two players compose an infinite word z, and Player 2 "does not go out of the set h(Γ ω )" then we claim that also Player 1, following her strategy F 1 , "does not go out of the set h(Γ ω )". Indeed if Player 1 goes out of the set h(Γ ω ) then due to the above remark this would imply that Player 1 also goes out of the set Cl(H): there is an integer n ≥ 0 such that z

[2n] ∈ Pref(H) but z[2n + 1] / ∈ Pref(H). So z / ∈ h(L(A)) ∪ [h(Γ ω ) -∩ H] ∪ V.C ω .
Moreover it follows from the definition of U that z / ∈ U.(Γ 1 ) ω . Thus If Player 1 goes out of the set h(Γ ω ) then she looses the game.

Consider now an infinite play in which Player 2 "does not go out of the set h(Γ ω )". Then Player 1, following her strategy F 1 , "does not go out of the set h(Γ ω )". Thus the two players write an infinite word z = h(x) for some infinite word x ∈ Γ ω . But the letters x(2n + 1), for n ≥ 0, have been written by Player 1, and the letters x(2n), for n ≥ 1, have been written by Player 2. Player 1 wins the play iff x ∈ L(A) and Player 1 wins always the play when she uses her strategy F 1 . This implies that Player 1 has also a w.s. in the game G(L(A)).

Assume now that Player 2 has a winning strategy F 2 in the game G(L).

If during an infinite play, the two players compose an infinite word z, and Player 1 "does not go out of the set h(Γ ω )" then we claim that also Player 2, following his strategy F 2 , "does not go out of the set h(Γ ω )". Indeed if Player 2 goes out of the set h(Γ ω ) and the final play z remains in Assume now that Player 1 "does not go out of the set h(Γ ω )". Then Player 2 follows his w. s. F 2 , and then "never goes out of the set h(Γ ω )". Thus the two players write an infinite word z = h(x) for some infinite word x ∈ Γ ω . But the letters x(2n + 1), for n ≥ 0, have been written by Player 1, and the letters x(2n), for n ≥ 1, have been written by Player 2. Player 2 wins the play iff x / ∈ L(A) and Player 2 wins always the play when he uses his strategy F 2 . This implies that Player 2 has also a w.s. in the game G(L(A)).

Cl(H) then z ∈ [h(Γ ω ) -∩ H] ∪ V.C ω ⊆ L
Looking carefully at the above proof, we can obtain a stronger result:

Theorem 3.4 Det(Σ 1 1 ) ⇐⇒ Det(CFL ω ) ⇐⇒ Det(r-BCL(1) ω ).

Context-free Wadge games

We first recall the notion of Wadge games. Recall that a strategy for Player 1 is a function σ : (Y ∪ {s}) ⋆ → X. And a strategy for Player 2 is a function f : X + → Y ∪ {s}. The strategy σ is a winning strategy for Player 1 iff she always wins a play when she uses the strategy σ, i.e. when the n th letter she writes is given by a n = σ(b 1 . . . b n-1 ), where b i is the letter written by Player 2 at step i and b i = s if Player 2 skips at step i. A winning strategy for Player 2 is defined in a similar manner. The game W (L, L ′ ) is said to be determined if one of the two players has a winning strategy. In the sequel we shall denote W-Det(C), where C is a class of ω-languages, the sentence: "All Wadge games W (L, L ′ ), where L ⊆ X ω and L ′ ⊆ Y ω are ω-languages in the class C, are determined".

There is a close relationship between Wadge reducibility and games. Theorem 4.5 There exists a real-time 1-counter Büchi automaton A, which can be effectively constructed, such that the topological complexity of the ω-language L(A) is not determined by the axiomatic system ZFC. Indeed it holds that :

(1) (ZFC + V=L).

The ω-language L(A) is an analytic but non-Borel set.

(2) (ZFC + ω L 1 < ω 1 ). The ω-language L(A) is a Π 0 2 -set.

We now state the following new result. To prove it we use in particular the above Theorem 4.5, the link between Wadge games and Wadge reducibility, the Π 0 2 -completeness of the regular ωlanguage (0 ⋆ .1) ω ⊆ {0, 1} ω , the Shoenfield's Absoluteness Theorem, and the notion of extensions of a model of ZFC.

Theorem 4.61 Let B be a Büchi automaton accepting the regular ω-language (0 ⋆ .1) ω ⊆ {0, 1} ω . Then one can effectively construct a real-time 1-counter Büchi automaton A such that:

(1) (ZFC + ω L 1 < ω 1 ). Player 2 has a winning strategy F in the Wadge game W (L(A), L(B)). But F can not be recursive and not even hyperarithmetical.

(2) (ZFC + ω L 1 = ω 1 ). The Wadge game W (L(A), L(B)) is not determined.

Remark 4.7 Every model of ZFC is either a model of (ZFC + ω L 1 < ω 1 ) or a model of (ZFC + ω L 1 = ω 1 ). Thus there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W (L(A), L(B)).

Remark 4.8 In order to prove Theorem 4.6 we do not need to use any large cardinal axiom or even the consistency of such an axiom, like the axiom of analytic determinacy.

Concluding remarks

We have proved that the determinacy of Gale-Stewart games whose winning sets are accepted by (real-time) 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption.

On the other hand we have proved a similar result about the determinacy of Wadge games. We have also obtained an amazing result, proving that one can effectively construct a real-time 1-counter Büchi automaton A and a Büchi automaton B such that the sentence "the Wadge game W (L(A), L(B)) is determined" is actually independent from ZFC.

Notice that it is still unknown whether the determinacy of Wadge games W (L(A), L(B)), where A and B are Muller tree automata (reading infinite labelled trees) , is provable within ZFC or needs some large cardinal assumptions to be proved.

)

  ⇐⇒ Det(CFL ω ) ⇐⇒ Det(BCL(1) ω ).

Definition 4. 1 (

 1 Wadge[START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF]) Let L ⊆ X ω and L ′ ⊆ Y ω . The Wadge game W (L, L ′ ) is a game with perfect information between two players, Player 1 who is in charge of L and Player 2 who is in charge of L ′ . Player 1 first writes a letter a 1 ∈ X, then Player 2 writes a letter b 1 ∈ Y , then Player 1 writes a letter a 2 ∈ X, and so on. The two players alternatively write letters a n of X for Player 1 and b n of Y for Player 2. After ω steps, Player 1 has written an ω-word a ∈ X ω and Player 2 has written an ω-word b ∈ Y ω . Player 2 is allowed to skip, even infinitely often, provided he really writes an ω-word in ω steps. Player 2 wins the play iff [a ∈ L ↔ b ∈ L ′ ], i.e. iff: [(a ∈ L and b ∈ L ′ ) or (a / ∈ L and b / ∈ L ′ and b is infinite)].

  and Player 2 looses. If Player 1 does not go out of the set Cl(H) and at some step of the play, Player 2 goes out of Pref(H), i.e. there is an integer n ≥ 1 such that z[2n -1] ∈ Pref(H) and z[2n] / ∈ Pref(H), then z ∈ U.(Γ 1 ) ω ⊆ L and Player 2 looses.

This result has been recently exposed in the Workshops GASICS

2010, Paris, September 2010, and GAMES 2010, Oxford, September 2010, but it has never been published.

Definition 4.2 (Wadge [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF]) Let X, Y be two finite alphabets. For L ⊆ X ω and L ′ ⊆ Y ω , L is said to be Wadge reducible to L ′ (L ≤ W L ′ ) iff there exists a continuous function f : X ω → Y ω , such that L = f -1 (L ′ ). L and L ′ are Wadge equivalent iff L ≤ W L ′ and L ′ ≤ W L. This will be denoted by L ≡ W L ′ . And we shall say that The Wadge hierarchy W H is the class of Borel subsets of a set X ω , where X is a finite set, equipped with ≤ W and with ≡ W . Using Wadge games, Wadge proved that, up to the complement and ≡ W , it is a well ordered hierarchy which provides a great refinement of the Borel hierarchy.

We can now state the following result on determinacy of context-free Wadge games.

Recall that, assuming that ZFC is consistent, there are some models of ZFC in which Det(Σ 1 1 ) does not hold. Therefore there are some models of ZFC in which some Wadge games W (L(A), L(B)), where A and B are Büchi 1-counter automata, are not determined. We are going to prove that this may be also the case when B is a Büchi automaton (without counter). To prove this, we use a recent result of [START_REF] Finkel | The complexity of infinite computations in models of set theory[END_REF] and some results of set theory, so we now briefly recall some notions of set theory and refer the reader to [START_REF] Finkel | The complexity of infinite computations in models of set theory[END_REF] and to a textbook like [START_REF] Jech | Set theory[END_REF] for more background on set theory. The usual axiomatic system ZFC is Zermelo-Fraenkel system ZF plus the axiom of choice AC. The axioms of ZFC express some natural facts that we consider to hold in the universe of sets. A model (V, ∈) of an arbitrary set of axioms A is a collection V of sets, equipped with the membership relation ∈, where "x ∈ y" means that the set x is an element of the set y, which satisfies the axioms of A. We often say " the model V" instead of "the model (V, ∈)".

We say that two sets A and B have same cardinality iff there is a bijection from A onto B and we denote this by A ≈ B. The relation ≈ is an equivalence relation. Using the axiom of choice AC, one can prove that any set A can be well-ordered so there is an ordinal γ such that A ≈ γ. In set theory the cardinal of the set A is then formally defined as the smallest such ordinal γ. The infinite cardinals are usually denoted by ℵ 0 , ℵ 1 , ℵ 2 , . . . , ℵ α , . . . The continuum hypothesis CH says that the first uncountable cardinal ℵ 1 is equal to 2 ℵ 0 which is the cardinal of the continuum.

If V is a model of ZF and L is the class of constructible sets of V, then the class L is a model of ZFC + CH. Notice that the axiom V=L, which means "every set is constructible", is consistent with ZFC because L is a model of ZFC + V=L.

Consider now a model V of ZFC and the class of its constructible sets L ⊆ V which is another model of ZFC. It is known that the ordinals of L are also the ordinals of V, but the cardinals in V may be different from the cardinals in L. In particular, the first uncountable cardinal in L is denoted ℵ L 1 , and it is in fact an ordinal of V which is denoted ω L 1 . It is well-known that in general this ordinal satisfies the inequality ω L 1 ≤ ω 1 . In a model V of the axiomatic system ZFC + V=L the equality ω L 1 = ω 1 holds, but in some other models of ZFC the inequality may be strict and then ω L 1 < ω 1 . The following result was proved in [START_REF] Finkel | The complexity of infinite computations in models of set theory[END_REF].


Disruption-Tolerant Wireless Biomedical Monitoring for Marathon Runners: a Feasibility Study

Djamel Benferhat*, Frédéric Guidec*, and Patrice Quinton** Abstract-Off-the-shelf wireless sensing devices open a wide range of perspectives for tetherless biomedical monitoring. Yet most applications considered to date imply either indoor realtime data streaming or ambulatory data recording. Disruptiontolerant networking is a means to cope with challenging situations where continuous end-to-end connectivity between communicating devices cannot be guaranteed. In this paper we investigate the possibility of using this approach to remotely monitor the cardiac activity of runners during a marathon race, using off-the shelf sensing devices and a limited number of base stations deployed along the marathon route. Preliminary experiments show that such a scenario is indeed viable, although special attention must be paid to balancing the requirements of ECG monitoring with the constraints of episodic, low-rate transmissions.

Index Terms-Wireless disruption-tolerant networking, sensor networking, biomedical monitoring

I. INTRODUCTION

Wireless Biomedical Sensor Networks (WBSN) are a variety of wireless sensor networks (WSN) in which sensors are dedicated to the monitoring of health parameters, such as physiological [START_REF] Otto | System Architecture of WBAN for Ubiquitous Health Monitoring[END_REF], kinematics [START_REF] Martin | Ambulatory Human Motion Tracking by Fusion of Inertial and Magnetic Sensing with Adaptive Actuation[END_REF] and ambient [START_REF] Bellis | Development of Field Programmable Modular Wireless Sensor Network Nodes for Ambient Systems[END_REF] parameters. Such sensors open up new opportunities in health care, as they allow long-term, continuous monitoring of patients in clinical environment, but also that of ambulatory patients at home [START_REF] Fensli | A Wearable ECG-Recording System for Continuous Arrhythmia Monitoring in a Wireless Tele-Home-Care Situation[END_REF]. In the latter case the cost and inconvenience of regular visits to the physician can be avoided, or at least significantly reduced.

As a general rule one or several lightweight, batterypowered sensors are attached to the patient, and a wireless base station is installed in the patient's surroundings. This base station can be configured so as to store the data received from the sensors. It can also forward these data directly to a remote site, such as a physician's desktop computer or a hospital's monitoring center. In any case, since the sensors are wireless the patient can move freely around the base station, while an endless stream of data flows from the sensors he/she is carrying to the base station. This freedom of movement is however limited by the short transmission range of the wireless sensors. Most sensors implement low-power radio transmission standards (such as Bluetooth or ZigBee), with which actual transmission ranges are usually between a few meters (indoor) and up to a hundred meters (outdoor).

In the most traditional scenario involving wireless biomedical sensors and a base station, it is commonly assumed that the transmission link between a sensor and the base station is continuously available and reliable. Transient link disruptions can be tolerated thanks to protocols implementing an ARQ (Automatic Repeat reQuest) mechanism, yet the general assumption is that frequent, long-term disruptions cannot occur while a patient's health status is being monitored. Although such an assumption can be verified when a patient does not move much around the base station, there are circumstances when the connectivity between sensor and base station can be seriously disrupted by the patient's mobility.

The concept of Disruption-Tolerant Networking1 (DTN) has recently been introduced in the literature as a means to cope with challenging situations where continuous end-to-end connectivity in a network cannot be guaranteed [START_REF] Fall | Messaging in Difficult Environments[END_REF]. When considering a network where at least some of the nodes are mobile, the general idea is to apply the store, carry, and forward principle on these nodes: a node that is temporarily disconnected from the rest of the network can store messages for a while in a local cache, in order to forward these messages later when circumstances permit. If a node that stores messages is a mobile node, then mobility becomes an advantage as it allows messages to be carried physically (and potentially on long distances) before being forwarded to another node. This approach makes it possible to fill the gap between non-connected parts of the network, allowing remote nodes to communicate even though no temporaneous end-toend connectivity is ever achieved between these nodes.

Applying the store, carry and forward principle in wireless biomedical sensors is an appealing prospect. Instead of being requested to remain constantly close to the base station that is monitoring his/her health status, a patient can occasionally stray away from the base station without interrupting the process of data gathering, nor compromising the integrity of the data. When the wireless link between a sensor and its base station is disrupted, the sensor stores the data it captures in a local cache. When the link is available again, the sensor uploads the content of its cache to the base station, together with new data it keeps capturing in real-time. In variants of this model, several sensors can cooperate in order to forward data to the base station [START_REF] Nayebi | Routing, Data Gathering, and Neighbor Discovery in Delay-Tolerant Wireless Sensor Networks[END_REF], or several base stations can be deployed so that sensors simply need to upload data to the nearest base.

In this paper we consider the technical problems raised by the utilization of the store, carry, and forward principle in wireless biomedical sensor networks (WBSN). To the best of our knowledge this subject has not been investigated much so far, although disruption-tolerant solutions for non-biomedical sensor-based applications have already been proposed in the literature [START_REF] Pisztor | Opportunistic Mobile Sensor Data Collection with SCAR[END_REF], [START_REF] Jain | Exploiting Mobility for Energy Efficient Data Collection in Wireless Sensor Networks[END_REF], [START_REF] Nayebi | Routing, Data Gathering, and Neighbor Discovery in Delay-Tolerant Wireless Sensor Networks[END_REF]. With this paper our main motivation is to confront the possibilities offered by current off-the-shelf sensors with the requirements of a demanding biomedical application, in order to assess if such an application can indeed be implemented using existing devices and technologies. To achieve this goal we deliberately focus on a scenario we consider as a most challenging one: the monitoring of the cardiac activity of runners during a marathon race. The underlying idea is that if disruption-tolerant biomedical monitoring can be performed in such a scenario, then similar solutions can also be designed and implemented for less constrained scenarios.

II. OVERVIEW OF OFF-THE-SHELF WIRELESS SENSOR

DEVICES

As a general rule a typical sensor node -or mote-is composed of a micro-controller or full-featured CPU, one or several transceiver modules, internal and/or external memory, a power source, and one or more sensing elements. Many off-the-shelf models are dedicated to the monitoring of ambient parameters, so they include built-in sensing elements to capture data such as the ambient temperature, hygrometry, atmospheric pressure, seismic activity, etc.

A survey of off-the-shelf sensors is available in [START_REF] Johnson | A Comparative Review of Wireless Sensor Network Mote Technologies[END_REF]. In our project we consider using SHIMMER platforms as biomedical sensors and TELOS-B sensor platforms as the radio units of our base stations. The characteristics of both kinds of platforms are detailed below.

Crossbow's TELOS-B "mote" platform is an open-source platform designed to enable experimentation in research projects. Its architecture is quite representative of that of most other off-the-shelf sensor platforms. It features an 8 MHz TI MSP430 micro-controller with 10kB RAM, 16 kB EEPROM, 48 kB flash memory (for the firmware), and 1 MB external flash memory (for data logging). The radio module is based on an IEEE 802.15.4/ZigBee compliant CC2420 transceiver, which runs in the 2400 MHz to 2483.5 MHz ISM band and allows data rates up to 250 kbps. Data acquisition is performed on up to 8 channels through a 12-bit AD converter. Programming and data collection can be performed either via a radio link or via a built-in USB interface. Power is provided either by 2 AA batteries or by the USB interface. Note that in our project we plan to use TELOS-B platforms as radio units for base stations, because of their programmability. For a real deployment of many base stations along a marathon route, USB dongles with embedded 802.15.4 transceivers should probably be used instead of TELOS-B platforms, as this would reduce the cost of this deployment.

SHIMMER is an extensible sensor platform that shares many features with Crossbow's TELOS-B platform, although it is most especially dedicated to recording and transmitting physiological and kinematic data [START_REF] Burns | SHIMMER: A Wireless Sensor Platform for Noninvasive Biomedical Research[END_REF]. The SHIMMER platform is powered by an integrated Li-Ion battery. It features an 8 MHz MSP430 CPU and two radio transceivers: an 802.15.4/ZigBee compliant CC2420 transceiver, and a WML-C46A class 2 Bluetooth transceiver. A 2 GB micro-SD card provides storage capacity for data logging. Several kinds of expansion modules are available, incorporating physiological sensors such as ECG (electrocardiography), EMG (electromyography) or GSR (galvanic skin response) sensors, as well as kinematic sensors for 3-axis angular rate sensing and 3-axis low field magnetic sensing. Utilization of these modules for biomedical monitoring has been validated experimentally [START_REF] Burns | SHIMMER: A Wireless Sensor Platform for Noninvasive Biomedical Research[END_REF].

Like many other sensor platforms the TELOS-B and SHIM-MER platforms are driven by TinyOS, a free and opensource component-based operating system targeting wireless sensor networking [11]. TinyOS applications are built in nesC (a dialect of the C language optimized for low memory consumption) out of event-based software components, some of which present hardware abstractions and others higher-level abstractions such as packet communication, routing, sensing, actuation and storage.

III. DESCRIPTION OF THE MARATHON SCENARIO

As mentioned in Section I our objective is to investigate the feasibility of disruption-tolerant biomedical data monitoring in challenged conditions. The scenario we consider as a test case is defined as follows: we assume the cardiac activity of athletes must be monitored using off-the-shelf ECG sensors during a marathon competition. This particular scenario was selected because runners must cover a long distance during a marathon, and that distance clearly exceeds the limited radio range of the low-power radio transceivers available on current sensor platforms. Besides, since runners in a marathon all follow exactly the same route, a number of base stations can be deployed along that route (see Figure 1).

A base station (BS) is typically composed of a processing unit -for example a laptop-that features an 802.15.4 interface, and at least one wired or wireless interface for longdistance transmissions (typically an access to the Internet). The 802.15.4 interface is used to receive data from the sensors carried by marathon runners, and the long-range interface is used to forward these data to a remote site (for example the closest medical aid station, or a physician's desktop, laptop, or smartphone). Data received from the sensors can be processed locally on the BS before being forwarded to the monitoring site, although that is not a requirement.

Ensuring a full coverage of the marathon's route would require a very large number of base stations, so the idea is that a sparse coverage of the route is ensured using only a limited number of base stations, as shown in Figure 1. A disruption-tolerant solution for data gathering must therefore be implemented: as long as the ECG sensor carried by a runner is out of the radio range of any base station, the data captured by this sensor is stored locally in its internal memory. Whenever the runner passes by a BS, a transient radio contact occurs between the sensor and that BS. This contact is exploited by the sensor to upload data to the BS, which in turn can relay these data to the monitoring center. This is a typical illustration of the store, carry and forward principle, since data acquired on a mobile biomedical sensor are stored and carried for a while, before being forwarded wirelessly to another device (in that case a BS).

The implementation of such a scenario might seem to be quite straightforward. Yet the problem is that ECG monitoring In order to answer this question it is necessary to evaluate the exact requirements of ECG monitoring, as well as the possibilities offered by IEEE 802.15.4 transceivers for outdoor data transmission.

IV. REQUIREMENTS AND CONSTRAINTS

A. Requirements of ECG monitoring

The ECG expansion module of the SHIMMER platform provides (Right Arm -Left Leg) RA-LL and (Left Arm -Left Leg) LA-LL input pairs. The (Right Arm -Left Arm) RA-LA pair can then be calculated based on the first two pairs. Sampling is performed on each RA-LL and LA-LL channel by 12-bit A/D converters, and the sampling frequency can be adjusted between 200 Hz and 1 kHz. ECG sampling on two channels therefore produces a continuous stream of data, at a rate that can be adjusted between 4.8 kbps (for 200 Hz sampling) and 24 kbps (for 1 kHz sampling).

ECG monitoring is often performed "in real time" or in slightly deferred time: a physician typically examines the ECG curve as it is produced, or just after it has been produced. Alternatively, ECG data can be recorded during a long period -sometimes several days-on an ambulatory patient, using a device such as the so-called Holter monitor (named after its inventor). In that case the data recorded by that monitor are examined only once the patient comes back to the physician's office.

In our marathon scenario the objective is that ECG data get recorded continuously during the marathon race, and that bundles of data are uploaded whenever possible to the remote monitoring center, which therefore receives frequent updates about the runner's health status. Our assumption is that a reasonable update frequency should be between 5 and 10 minutes. Considering the pace of an average runner this implies that base stations should be placed about 1 to 2 km apart. The SHIMMER and TELOS-B platforms we consider in this project both operate at 250 kbps in the 2.4 GHz band. The question is therefore to determine how much data can be transferred when a marathon runner carrying an ECG-enabled SHIMMER sensor passes by a BS (based on a TELOS-B unit). The 250 kbps transfer rate mentioned in the IEEE 802.15.4 specification is of course the signaling rate -or gross bit rate-on the radio channel. The actual transfer rate available at application level shall of course be significantly lower than that signaling rate.

In order to clarify the potential of 802.15.4 transceivers for data transmissions in our marathon scenario, we conducted a series of preliminary field experiments in realistic conditions. These experiments were conducted outdoor in an open field, using a TELOS-B platform as a base station (BS) and SHIM-MER platforms -with ECG expansion modules-as mobile nodes (MN). Small nesC programs were loaded on the MN and BS, allowing the MN to detect the BS and upload as much data as possible to the BS before getting out of radio range. The detection of the BS by the MN was based on beacon frames broadcast every 2 seconds by the BS. A GPS receiver was used to measure distances and check the runner's speed.

Maximal radio range and contact duration between MN and BS: Our first objective was to measure the distance over which effective data transfers can be achieved between MN and BS in an open field. In practice we observed that connections can be established when both devices are less than 105 meters apart (with a standard deviation of 5 meters). This implies that a BS located on the side of a marathon route should be able to maintain a connection with an ECG-enabled MN during the time it takes for runners to cover at most a distance of approximately 200 meters (that is, about 35 seconds for fast runners, and between 60 and 80 seconds for average runners).

Maximal throughput of data transfers between one MN and one BS: Data transfers during a contact between MN and BS were performed by producing on the MN an endless stream of full-size data frames (with 114 random bytes in the payload field of each data frame), and counting the number of data frames received by the BS during the radio contact. Data frames were sent in unicast mode, but with acknowledgements disabled so as to avoid retransmissions in that particular experiment.

The experiment was first conducted with a static MN, the MN and BS being only a few meters apart. In such conditions we observed that no data frame was lost during the transmission (even with acknowledgements disabled), but the effective transfer rate did not exceed 55 data frames per second, which corresponds to an application-level throughput of about 50 kbps. This value is surprisingly low compared to the standard's 250 kbps signaling rate, although it is consistent with other results mentioned in the literature [START_REF] Farshchi | A TinyOS-Based Wireless Neural Sensing, Archiving, and Hosting System[END_REF] and in the TinyOS forum. Indeed it seems that the architecture of the SHIMMER and TELOS-B platforms both present a bottleneck, which lies in the connection between the microcontroller and radio transceiver. Although the CC2420 radio transceiver can send and receive frames at 250 kbps on the radio channel, these frames can only be transferred to or from the micro-controller at a very limited rate. This is an important disadvantage for our marathon scenario, which requires that a single BS be able to receive data streams from several neighbor MN units in the same timespan. Additional experiments are in progress to determine if a USB dongle embedding a 802.15.4 transceiver, used instead of the TELOS-B platform, would show the same 50 kbps limitation.

Impact of contention between multiple MN units: The transmission range and data throughput mentioned above were observed in quasi-ideal conditions, in an open environment presenting no obstacle to radio propagation, little or no radio interference, and with a single MN uploading its data to the BS. In real conditions it can be expected that data transfers between MN and BS will be performed in a noisy environment, with a high level of transmission failures. Moreover several MN may be in the radio range of the same BS at the same time, so this BS shall have to receive and process several data streams during the same timespan.

In order to measure the impact of contention between multiple MN units trying to upload their data to the same BS simultaneously, the experiment was repeated with a runner carrying successively one, two, three, and four MN units. In that case the CCA (Clear Channel Assessment) and backoff functions of the CSMA/CA method were enabled on all platforms in order to avoid collisions whenever possible. Acknowledgements were disabled, though, so we could measure the amount of frame loss. Table I shows the frame loss ratio and cumulated throughput of application-level data received on the BS depending on the number of neighbor MN units. As could be expected the frame loss ratio increases with the number of MN units trying to access the radio channel simultaneously. Conversely, the application-level throughput decreases significantly as the number of MN units increases. This is the consequence of contention between multiple MN units, which yields an inefficient use of the radio channel. This observation suggests that since our marathon scenario requires that a BS be able to deal with several MN units in the same timespan, it should play the role of a channel access coordinator, thus allowing contention-free access to the channel for each MN successively. This is discussed further in the next section.

V. TOWARD A FAIR BALANCE BETWEEN REQUIREMENTS AND TRANSMISSION CONSTRAINTS

Monitoring the cardiac activity of marathon runners is obviously a serious challenge. The preliminary results described in Section IV show that disruption-tolerant ECG monitoring of marathon runners is certainly feasible, but that special attention must be paid in order to keep the demand of ECG monitoring at a minimum while ensuring an efficient use of the wireless medium. Below is a list of options we plan to investigate while working along that line.

A. Reducing the demand of ECG monitoring

Using a low sampling frequency and/or low quantization resolution: ECG monitoring is often performed with a 500 Hz sampling frequency, and by default the SHIMMER A/D converters have a 12-bit resolution. In such conditions the bitrate of the data stream produced by SHIMMER's 2-channel ECG module is 12 kbps. This figure can be reduced significantly by using lower sampling frequency and resolution. For example a 200 Hz sampling with 8-bit samples (on each channel) would only produce a 3.2 kbps data stream. Such parameters may of course alter the quality of ECG data, but signal reconstruction techniques can be used on the receiver side in order to compensate for this low quality [START_REF] Hossein | Real-Time Compressed Sensing-Based Electrocardiogram Compression on Energy Constrained Wireless Body Sensors[END_REF].

Compressing ECG data before storage and/or transmission: An important constraint here is to implement a compression algorithm that does not exceed the computation power of a SHIMMER platform's micro-controller, such as that proposed in [START_REF] Hossein | Real-Time Compressed Sensing-Based Electrocardiogram Compression on Energy Constrained Wireless Body Sensors[END_REF]. Our expectation is that by combining low sampling frequency and resolution with efficient data compression the rate of the data stream produced by ECG monitoring on a SHIMMER platform could drop as low as 1 kbps.

Onboard analysis of ECG data: Instead of transferring the whole ECG curve to a remote monitoring site, ECG data could be analyses directly by the SHIMMER platform, which would then simply send reports or alerts to the monitoring center. A recognition module for cardiac arrhythmia is thus proposed in [START_REF] Madzarov | Heartbeat Tracking Application for Mobile Devices -Arrhythmia Recognition Module[END_REF], and delineation algorithms for the automatic detection of the major ECG characteristic waves are described in [START_REF] Boichat | Wavelet-Based ECG Delineation on a Wearable Embedded Sensor Platform[END_REF]. The algorithms proposed in both papers have a low computational complexity, so they can run on resourceconstrained platforms such as the SHIMMER.

B. Getting the most of radio contacts between MN and BS

Using an external antenna on the base station: The TELOS-B platform we used as the BS's receiver has an onboard antenna that is integrated in the printed circuit. The quality of transmissions between MN and BS could definitely be enhanced by using an external antenna on the BS.

Avoiding contention and prioritizing transmissions between neighbor MN units: When several MN units pass close to the same BS during the same timespan, contention between these MN units should be avoided. A possible approach is to implement some channel access coordination method (typically a variation on the TDMA scheme), the BS serving as a coordinator. Upon discovering a BS a MN would first request time-slots from this BS, and the number or duration of these time-slots could be adjusted based on the MN's exact needs. While passing close to the BS the MN could even implement some strategy in order to upload urgent data first, such as the most recent ECG samples, or a subset of all stored samples so the monitoring center can start displaying rough or partial ECG curves before receiving additional data.

Augmenting the capacity of a BS to handle many MN units simultaneously: If the number of MN units that can get in contact with a single BS simultaneously clearly exceeds the capacity of a single 802.15.4 transceiver, then this capacity could be increased by implementing a multichannel BS. The 2.4 GHz physical layer of the IEEE 802.15.4 standard can operate on up to 16 channels (depending on local regulations). Each base station could therefore include several IEEE 802.15.4 transceivers, each of these transceivers operating on a different channel. Some kind of FDMA multiplexing scheme would then be implemented in addition to the TDMA scheme: upon receiving a beacon of the BS on a predetermined channel (say, channel 0) a MN would contact the BS and be assigned a particular time-slot on a particular channel. Multiplying the number of 802.15.4 transceivers would of course increase the cost of a BS, but this approach would clearly make it possible for this BS to handle a large number of MN units -thus a large number of runners-in the same timespan.

VI. CONCLUSION

Off-the-shelf wireless sensing devices such as the SHIM-MER platform open a wide range of perspectives for biomedical monitoring. Yet because of its limited transmission capacity most applications considered to date imply either indoor real-time data streaming, or ambulatory data recording.

With disruption-tolerant networking an intermediate approach can be considered, whereby data are captured and stored continuously on the sensor platform, and transient connectivity with a base station is used opportunistically to upload data to a remote monitoring center.

In order to illustrate this approach we investigate a scenario we believe to be a most challenging one: the ECG monitoring of runners during a marathon race. Preliminary experiments suggest that capturing and transmitting ECG data during a marathon race is feasible using off-the shelf devices, provided the bitrate of data produced is kept at a minimum and data transfers are performed in a most efficient way. In Section V we have listed several options we plan to investigate along that line in the near future.

Figure 1 .

 1 Figure 1. Illustration of disruption-tolerant ECG monitoring of marathon runners

B

  . Possibilities of IEEE 802.15.4 transmissions IEEE 802.15.4 denotes a standard for low power, low data rate Wireless Personal Area Networks (WPAN). The original version of this standard was issued in 2003. In this version the physical layer is defined to operate on unlicensed ISM bands (868.0-868.6 MHz in Europe, 902-928 MHz in North America, and 2400-2483.5 MHz worldwide), allowing transfer rates of 20 kbps, 40 kbps, and 250 kbps depending on the band considered. Revisions of the 2003 version have been issued since then, that mostly extend the physical layer toward additional frequency bands and advanced modulation techniques.

The term Delay-Tolerant Networking is also used in the literature, although it is rather used to denote networks where very long propagation delays are the prime concern to deal with (such as interplanetary networks).


Babar Aziz
email: babar.aziz@ensea.fr

Inbar Fijalkow
email: inbar.fijalkow@ensea.fr

Myriam Ariaudo
email: myriam.ariaudo@ensea.fr

Intercarrier Interference in Uplink OFDMA Systems with Carrier Frequency Offset

Keywords: Carrier Frequency Offset, Orthogonal Frequency Division Multiple Access, Cyclic Prefix

Orthogonal Frequency Division Multiplexing (OFDM) is very sensitive to carrier frequency offsets (CFO). The CFO results in intercarrier interference (ICI). This drawback of OFDM is inherited to Orthogonal Frequency Division Multiple Access (OFDMA). In this paper, we propose a new ICI model for an uplink OFDMA system that takes into account the presence of the cyclic prefix which is usually ignored. Simulations validate the accuracy of our derivation. The subcarrier allocation is revisited in the presence of CFO.

I. INTRODUCTION

The upcoming mobile communication systems such as Wifi, WiMAX and LTE (Long Term Evolution) have to offer high data rates both in the uplink and downlink directions in order to fulfill the needs of the future innovative multimedia applications [START_REF] Molisch | Wideband Wireless Digital Communication[END_REF], [START_REF] Huang | Timing and frequency synchronization for OFDM based cooperative systems[END_REF]. OFDMA is coming forth as the favored downlink transmission scheme for these systems because it is highly adaptive and robust in frequency selective radio channels and also provides good system flexibility [START_REF] Molisch | Wideband Wireless Digital Communication[END_REF], [START_REF] Galda | OFDM:A flexible and adaptive air interface for a 4G mobile communication system[END_REF]. However, questions are still raised about the use of OFDMA in the uplink direction. A well known problem of OFDMA in the uplink is its sensitivity to carrier frequency offsets (CFO). This paper concentrates on carrier frequency synchronization error while perfect time synchronization is assumed. CFO might result from Doppler shift, or in the case where a user mixer is not perfectly synchronized to its allocated carrier frequency [START_REF] Huang | Timing and frequency synchronization for OFDM based cooperative systems[END_REF], [START_REF] Moose | A technique for orthogonal frequency division multiplexing frequency offset correction[END_REF], [START_REF] Sari | Channel equalization and carrier synchronization in OFDM systems[END_REF]. CFO besides causing attenuation and rotation of each of the subcarrier, also causes loss of orthogonality between subcarriers leading to interference among adjacent subcarriers known as ICI. The main goal of this paper is to investigate the impact of ICI resulting from CFO in an uplink OFDMA system. Several researchers have studied the ICI due to changes in frequencies [START_REF] Armstrong | Analysis of New and Existing Methods of Reducing Intercarrier Interference due to Carrier Frequency Offset in OFDM[END_REF]- [START_REF] Zhao | Intercarrier interference selfcancellation scheme for OFDM mobile communication systems[END_REF] in OFDM(A) systems. Analytical models of ICI provided in [START_REF] Kaiser | Analysis of Doppler Spread Perturbations in OFDM(A) Systems[END_REF], [START_REF] Stemick | Effect of Carrier Frequency Offset on the Channel Capacity in Multiuser OFDM-FDMA Systems[END_REF] neglect the cyclic prefix which is in practice between 1/4 and 1/8 of the number of subcarriers. The cyclic prefix is inserted in an OFDM(A) symbol to cancel intersymbol interference and ICI in frequency selective channels. Some interesting results are provided in [START_REF] Leonard | Bounds on the Interchannel Interference of OFDM in Time-Varying Impairments[END_REF] but the ICI analysis is done using the Fourier Transform rather than DFT. So the results of [START_REF] Leonard | Bounds on the Interchannel Interference of OFDM in Time-Varying Impairments[END_REF] suit the case of an infinite number of carriers which is not very realistic.

In this paper we provide an analytical model for ICI without neglecting the cyclic prefix. We will show that our analytical model is more accurate.

In section 2, the considered system model is presented along with an analytical model for the CFO depending ICI. In section 3, we present the impact of CFO introduced multiuser interference through its variance analysis and simulation results. Section 4 discusses the CFO induced self-ICI and section5 introduces the effect of subcarrier allocation.

II. UPLINK SYSTEM MODEL

In this section, we present the uplink OFDMA system under consideration. The available bandwidth B is divided into N p subcarriers. N u is the total number of users in the system. Each user is therefore allocated M = N p /N u subcarriers exclusively to fulfill its transmission demands. The radio channel model is assumed to be frequency selective. The last L modulation symbols in the OFDMA symbol are repeated after the inverse DFT to form the cyclic prefix.

A. Analytical Signal Model

We next describe the analytical signal model of the OFDMA system. The signal at the output of the transmitter of user u is given by:

x (u) (t) = Re{e j2π(fc+δf (u) c )t Np-1 k=0 a (u) k p (u) (t - kT N p )} (1)
where f c is the carrier frequency, p (u) (t) is the impulse response of the low pass filter at the transmitter and T is the symbol period of an OFDMA symbol. δf

(u) c
represents the CFO of user u with respect to f c . The CFO appears in the transmitted signal because we are considering the case where the user u is not perfectly synchronized to the carrier frequency of the base station. Note that a (u) k are the symbols at the IDFT output given by:

a (u) =     a (u) Np-1 . . . a (u) 0     = F -1 Π (u) A (u) (2)
where

A (u) = {A (u) 0 ...A (u)
M -1 } are the input symbols from user u. Π (u) is an N p × M subcarrier mapping matrix for user u. Π (u) k,p with k ∈ {0, ..., N p -1} and p ∈ {0, ..., M -1} models the multiple access scenario. It equals 1 for the carriers allocated to user u and zero elsewhere. F -1 is the DFT matrix given by

F -1 =        W -(Np-1) 2 . . . 1 . . . . . . . . . W -(Np-1) W -1 1 . . . 1        with W = e j 2π
Np . Signals from different users x (u) (t) pass through individual multipath radio channels. The received signal at the base station is the sum of the signals from all users. The overall noise free received signal r(t) is given by:

r(t) = Re{ Nu u=1 Np-1 k=0 a (u) k q (u) (t - kT N p )e j2π(fc+δf (u) c )t } (3)
where q (u) (t) is the combined impulse response of the channel from user u and of the transmitter and receiver filters. The baseband samples, at the symbol rate T /N p , input to the receiver DFT can be written as:

r Np-1 . . . r 0 . . . r -L =           h (u) o • • • h (u) L-1 0 0           a (u) Np-1 . . . a (u) 0 . . . a (u) -L h (u) o • • • h (u) L-1                                         . . . . . . . . . . . . Nu u=1 (4)
δ (Np+L-1) (u) 0 .

. .

0 δ 0 (u)                     . . .
with L as the length of the cyclic prefix. Note that δ k (u) = e j2πkδf (u) c T /Np where k = 0, ..., N p -1 are the shift coefficients. The normalized shift of user u is given by 4) are the received symbols and h k (u) is the discrete channel impulse response from user u to the base station with k = 0, ..., L. We assume that the channel impulse response length is smaller than L, so that the last terms of h k (u) can be zeros.

δf (u) = δf (u) c T r k in equation (

B. Signal at the DFT output without CFO

To analyse CFO induced ICI, we first recall the case of no CFO. When there is no CFO and each user is perfectly synchronized to the base station, the received signal is given by:

            h (u) o . . . h (u) L-1 0 . . . . . . h (u) L-1 h (u) L-1 . . . . . . . . . . . . h (u) . . . h (u) L-1 h (u) o             . . . 0 r N p -1 . . . r 0 . . . = Nu u=1 h                                                 a (u) Np-1 . . . a (u) 0 . . . ( 5
) (u) r = - - 1
The last L symbols of r in (4) corresponding to the cyclic prefix a -1 , ..., a -L have been discarded in ( 5) and the input symbols are rearranged since they are equal to a Np-1 , ..., a Np-L . Thanks to the presence of the cyclic prefix, the channel matrix in (4) has been reduced to a circulant matrix h (u) in ( 5). This circulant channel matrix is further diagonalized by the receiver DFT. The received signal after the size N p DFT block is given by

R = Nu u=1 H (u) Π (u) A (u)
where H (u) is the diagonal channel matrix of user u which is given by

H (u) = F h (u) F -1
with entries

H (u) k,k = Np-1 m=0
h m e j2πmk/Np . Knowing the allocation matrix Π (u) , the base station recovers all the input messages from Π (u)-1 R.

C. Signal at the DFT output with CFO

In the case of a CFO, δf (u) between a user u and the receiver, we show next that the channel matrix doesn't remain circulant. If the receiver performs the usual cyclic prefix symbols discarding and rearrangement as when there is no CFO, after some calculations, we get,

h (u) L-1 . . . . . . h (u) . . . h (u) L-1             0 r N p -1 . . . r 0 . . . = Nu u=1 h                                                 a (u) Np-1 . . . a (u) 0 . . . ( 6
) (u)                   +(δ - -1) x h (u)             - - Np . . . . . . δ 0 (u) δ (Np-1) (u) 0 0 -                         ∆ δ (u) - (u) 1
From equation ( 6), we find that the channel matrix can not be written in a circulant form unless we discard the additional terms xh

(u)
∆ appearing in [START_REF] Armstrong | Analysis of New and Existing Methods of Reducing Intercarrier Interference due to Carrier Frequency Offset in OFDM[END_REF]. Authors in [START_REF] Stemick | Effect of Carrier Frequency Offset on the Channel Capacity in Multiuser OFDM-FDMA Systems[END_REF], while analyzing the ICI due to CFO, have completely ignored the effect of CFO on the cyclic prefix in the received signal and the expression for the received signal is reduced to only

R = Nu u=1 H (u) δ (u) a (u)
Similarly the expressions for ICI in [START_REF] Huang | Timing and frequency synchronization for OFDM based cooperative systems[END_REF] or [START_REF] Stemick | Effect of Carrier Frequency Offset on the Channel Capacity in Multiuser OFDM-FDMA Systems[END_REF] correspond to the case where the effect of CFO is ignored on the cyclic prefix. The analytical expression we derive for ICI, ζ ici , experienced by a particular user v is given by

ζ (v) ici = Nu u=1 F (δ (u) -I)F -1 H (u) Π (u) A (u) +(δ -(u) -1)F δ (u) h (u) ∆ F -1 Π (u) A (u) (7)
Np where I is an N p ×N p identity matrix. Equation [START_REF] Kaiser | Analysis of Doppler Spread Perturbations in OFDM(A) Systems[END_REF] represents the overall interference experienced by user v. It comes from multiple users interference as well as self-ICI.

III. CFO INDUCED MULTIPLE USERS INTERFERENCE

Next, we want to quantify the impact of multiple users interference by deriving its variance. For the sake of simplicity, we assume that there are only two users in the system, N u = 2. Furthermore, it is assumed that the base station is perfectly synchronized to user 1 i.e. δf (1) = 0 so that the interference comes from user 2 only δf (2) = 0.

A. Variance of ICI

We assume in the sequel that the modulation symbols are statistically independent random variables from a predefined alphabet and independent from one user to another. Moreover, the transmit power for the modulation symbols is normalized such that E{|A (u) | 2 } = 1. Then, the interference seen by the base station on the signal from user 1 due to the CFO in user 2 is reduced to

ζ ( ) ici = F (δ ( ) -I)F -1 H ( ) Π ( ) A ( ) +(δ -( ) -1)F δ ( ) h ( ) ∆ F -1 Π ( ) A ( ) (8)
Np

1 1 2 2 2 2 2 2 2 2 2
The total variance of ( 8) is given by equation ( 9),

= σ 2 1 + σ 2 2 + cov 1,2 (9)
σ 2 ζ ici (1)
where σ 2 1 and σ 2 2 are the variances of the first and second terms of (8) respectively and cov 1,2 represents the intercovariance of these terms. Since F + = F -1 , the three terms of equation ( 9) are given by equations [START_REF] Zhao | Intercarrier interference selfcancellation scheme for OFDM mobile communication systems[END_REF][START_REF] Linnartz | Chief, Wireless Communication, The Interactive Multimedia CDROM[END_REF](12).

σ 2 2 = |δ -Np (2) -1| 2 tr{h + ∆ (2) h (2) ∆ δ (2) F -1 Π (2) Π + (2) F δ + (2) } σ 2 1 = tr{F -1 H (2) H +(2) F (δ (2) -I)F -1 Π (2) Π +(2) F (δ (2) -I) + } (10) (11) cov1,2 = 2Re (δ -Np (2) -1) tr{F h (2) ∆ δ (2) F -1 Π (2) Π + (2) F (δ (2) -I) + F -1 H + (2) } (12) ×
Note that in above equations tr(x) stands for the trace of x.

B. Blockwise Case

In this subsection, we consider that the subcarriers are allocated to the users in a block fashion as shown in Figure 1. In this case, the subcarrier allocation matrix of user 2, Π (2) , can be simplified as

Π (2) = [0 I] T
where 0 is an M ×M matrix with all entries equal to zero and I is an M × M identity matrix. Thanks to this simplification and after some calculations we find that equations (10-12) reduce to:

cov 1,2 = 2Re{(δ - -1) L-1 i=0 i+1 k=1 ( δ Np-k - ) } σ 2 2 =| -1| 2 L-1 i=0 i 1 Np δ -Np σ 2 1 = -1 k=0 sin 2 (π kT ) L-1 i=0 (11a) (10a) (12a) δf ( ) c 2 M h + i hi ( ) 2
( ) 2 h + i hi ( ) 2
( ) 2 h + i hi ( ) 2 ( ) 2
( ) 2
( ) 2
( ) 2 (
) -Equations (10a-12a) represent the total variance of the interference seen by user 1 for a blockwise carrier allocation.

C. Simulation Results

Next, we compare the derived expression of the ICI with some previous results and with a simulated OFDMA system. For the simulations the following three scenarios are considered:

• Scenario 1(Sce. Here N p = 64, length of the cyclic prefix is L = 16, N u = 2 therefore M = 32 and the carriers are allocated using the blockwise allocation shown in Figure 1. Again we assume that the base station is synchronized to user 1 so that δf (1) = 0 and δf (2) = 0. A 16-QAM modulation is used. Figure 2 shows the ICI variance versus the user 2 normalized shift values, δf (2) . The variances have been averaged over all subcarriers for each value of the normalized shift. The results are also averaged over 5000 channel realizations, with random impulse responses of length L. Results in Figure 2 show that our proposed ICI variance for user 1, σ

ζ σ 2(1)
no-cp δ f (2) Normalized by the subcarrier spacing ICI variance in [START_REF] Stemick | Effect of Carrier Frequency Offset on the Channel Capacity in Multiuser OFDM-FDMA Systems[END_REF]: Fig. 2. of the ICI variances of user 1 for the three scenarios for different values of the normalized shift in user 2 δf (2) .

[9], σ

2(1)
no-cp . At a shift of 0.08 the difference between σ

2(1)
sim and σ

2(1)

no-cp is about 12dB. This result validates our proposed ICI model of multiple user interference and associated variance and shows its superiority with respect to the models in the literature.

IV. CFO INDUCED SELF-ICI

In the previous section, we have assumed that the base station is synchronized to user 1 and we studied the multiple user interference in user 1 coming from user 2. Sticking to this assumption, we assume in this section that the base station can not be synchronized to user 2 which would have required a supplementary VCO. The interference seen by user 2 is therefore the interference from user 1 plus the interference coming from its own subcarriers, called self-ICI.

A. Blockwise Case

In the blockwise subcarrier allocation scheme of Figure 1, most subcarriers allocated to user 2, the ones in the second block, experience only self-ICI. Only the carriers on the edge experience interference from user 1. The analytical expression of the variance can't be simplified any further, so that we don't recall it here. The following simulations consider the same setting as described previously. In Figure 3, the curves for ICI variance of user 2 are plotted against the normalized shifts. Again, we can see that our results are much closer to the simulated compared to the model in [START_REF] Stemick | Effect of Carrier Frequency Offset on the Channel Capacity in Multiuser OFDM-FDMA Systems[END_REF]. Moreover, we have plotted σ

2(2) ζ

for L = 0 and it can be seen that it matches with σ 2(2) no-cp . In Figure 4, the curves for ICI variance of user 2 are plotted against its normalized shift for different lengths of the cyclic prefix, N p remains equal to 64. We can see from Figure 4 that as the length of the cyclic prefix increases from L = 16 to L = 22 (about 1 4 th and 1 3 rd of N p respectively), σ

sim and σ

ζ σ 2(2)
no-cp

Proposed ICI variance at L=0 δ f (2) Normalized by the subcarrier spacing ICI variance in [START_REF] Stemick | Effect of Carrier Frequency Offset on the Channel Capacity in Multiuser OFDM-FDMA Systems[END_REF]: Fig. 3. Comparison of the ICI variances of user 2 for the three scenarios for different values of the normalized shift in user 2 δf (2) .

in OFDMA system with CFO is more important when the cyclic prefix is long with respect to the number of subcarriers.

B. Effect of ICI on Symbol Error Rate

Next, we demonstrate the importance of the proposed model for the symbol error rate (SER) that is a better measure of performance than the variance of error. For the analytical SER calculation, we used the following formula [START_REF] Linnartz | Chief, Wireless Communication, The Interactive Multimedia CDROM[END_REF] P s = 15 16 -γ γ + 10 as γ = E s /(σ 2 ζ + N 0 ) with σ 2 ζ as defined previously and N 0 is the noise power. Simulation results shown in Figure 5 give the SER performance of user 2 for the three scenarios at δf (2) = 0.08. Again N p = 64 and L = 16. For such a high value of CFO, we can see that SERs of user 2 for Sce.1 and Sce.2 are very close to each other, around 4.10 -1 for high values of SNR while the SER for Sce.3 is much less i.e. close to 10 -1 . In Figure 6, the SER curves are plotted for different values of L. Indeed, the SER of user 2 for Sce.1 and 2 is higher at L = 22 than at L = 16. Again Sce.3 shows no change in SER with the length of cyclic prefix since it ignores the cyclic prefix. These results validate our model of the SER in OFDMA systems with CFO and their superior accuracy with respect to the literature. V. ICI AND SUBCARRIER ALLOCATION In this section, we consider the impact of the subcarriers allocation on the ICI and related performance. In systems that do not undergo CFO, channel diversity is usually induced by interleaving the subcarriers allocated to the different users. However, in systems experiencing CFO a blockwise allocation minimizes the level of interference. It reduces the interference to the edge subcarriers of the block. Channel diversity and robustness to CFO are therefore in contradiction. In the sequel, we wonder what is the best number of adjacent subcarriers in the presence of CFO. The blockwise allocation scheme presented in Figure 1 The minimum will be equal to 1, called the interleaved allocation. We simulate the same two user case presented in the previous sections with base station synchronized to user 1 while user 2 is not synchronized. The interference power is evaluated for user 1 and user 2 for blockwise allocation with different blocksizes (BS). A blockwise arrangement of the subcarriers for a blocksize of 16 is shown in Figure 7.

Figure 8 shows the ICI variance for both users versus different values of blocksize (BS). N p = 64, L = 16 and δf (2) = 0.06. At a blocksize of 32, the subcarriers of user 2 are far from , because of CFO in user 2 is only at the edge subcarriers and is small i.e. less than -23dB. While the ICI in user 2, with variance σ 2(2) ζ , is high -12dB and is caused by its own subcarriers. Figure decreases. This is because the only interference user 2 sees is from its own carriers. With a decreasing blocksize, user 2 subcarriers become far from each other and become closer and closer to user 1 subcarriers which offer no interference. In Figure 9, the ICI variance for user 1 is detailed for different values of normalized shift δf (2) for blocksizes 32, 16 and 4. We can see that with the increase in blocksize the ICI power for user 1 decreases. As expected, a larger blocksize provides more robustness against CFO. However, the gain in diversity does not seem to compensate the loss due to CFO for small values of CFO.

VI. CONCLUSION

A new analysis of the effect of carrier frequency offset (CFO) in an uplink OFDMA systems has been presented. We have demonstrated that one must take into account the cyclic prefix while analyzing Intercarrier Interference (ICI) resulting from CFO. We proposed an analytical expression of the ICI, the associated variance and SER. It allows us to study the subcarrier allocation for an OFDMA system undergoing CFO.

Fig. 1 .

 1 Fig. 1. Blockwise carrier allocation of user 1 and user 2. Each user is allocated Np/2 subcarriers that are adjacent to each other.

2( 1

 1 ) ζ , is much closer to the simulated ICI variance of user 1, σ 2(1) sim than the one derived in -0.08 -0.06 -0.04 -0

2( 2

 2 ) ζ increase accordingly. Indeed, σ2(2)no-cp remains constant. This result proves that considering our proposed model of ICI

Fig. 4 .

 4 Fig. 4. Comparison of the ICI variances of user 2 for L = 16 and L = 22 for the three scenarios.

Fig. 5 .

 5 Fig. 5. Comparison of the SERs' of user 2 for the three scenarios at Np = 64 and L = 16.

Fig. 6 .

 6 Fig. 6. Comparison of the SERs' user 2 for the three scenarios for different lengths of the cyclic prefix.

Fig. 8 .

 8 Fig. 8. ICI variances of the two users for different blocksizes at a normalized user 2 shift δf (2) = 0.06.the subcarriers of user 1 (perfectly synchronized). So the

Fig. 9 .

 9 Fig.9. ICI variance of user 1 for different values of δf(2) with blocksizes 32, 16 and 4.8 shows that with a decreasing blocksize, σ 2(1) ζ increases while σ 2(2) ζ

  corresponds to the maximum size a block can have, it is equal to N p /2.

	User 1	User 2	User 1	User 2
	. . . . . .	. . .	. . .	. . .
	0	15 16	31	63
			Subcarriers
	Fig. 7. Subcarrier allocation with blocksize equal to 16.

This work is supported by the French IdF Region DIM "Logiciels et Systmes Complexes" Project DESAP.