Nicolas Schwind
email: nicolas-schwind@aist.go.jp

Katsumi Inoue
email: inoue@nii.ac.jp

Gauvain Bourgne
email: gauvain.bourgne@lip6.fr

Sébastien Konieczny
email: konieczny@cril.fr

Pierre Marquis
email: marquis@cril.fr

Is Promoting Beliefs Useful to Make Them Accepted in Networks of Agents?

We consider the problem of belief propagation in a network of communicating agents, modeled in the recently introduced Belief Revision Game (BRG) framework. In this setting, each agent expresses her belief through a propositional formula and revises her own belief at each step by considering the beliefs of her acquaintances, using belief change tools. In this paper, we investigate the extent to which BRGs satisfy some monotonicity properties, i.e., whether promoting some desired piece of belief to a given set of agents is actually always useful for making it accepted by all of them. We formally capture such a concept of promotion by a new family of belief change operators. We show that some basic monotonicity properties are not satisfied by BRGs in general, even when the agents merging-based revision policies are fully rational (in the AGM sense). We also identify some classes where they hold.

Introduction

We are interested in the issue of monotonicity in a multiagent system, represented as a Belief Revision Game (BRG) [START_REF] Schwind | [END_REF]. The BRG setting is a framework for modeling the belief dynamics of a group of agents V , for instance agents involved in a social network. A BRG is a dynamical system where agents have their own belief bases (representing their belief states), and communicate synchronously with their acquaintances. The acquaintance relationship is given through a binary relation A over V , i.e., (V, A) is a graph. Let us introduce a motivating example:

Example 1. Consider a group of friends Alex, Beth and Chris who are discussing on whether they should trust the quality of the food served in a given restaurant. Alex and Beth know each other, Alex and Chris as well, but Beth and Chris do not know each other. Two meals are considered by them. At the beginning, Alex believes that either the first meal or the second one is healthy, but not both of them; Beth believes that none of the two meals is healthy; whereas Chris believes that at least one of the two meals is healthy.

At each communication step, each agent revises her beliefs by considering the beliefs of her acquaintances. Several merging-based revision policies have been defined, each of them reflecting how much an agent is ready to question her current beliefs in front of the beliefs of her acquaintances. Then a piece of belief ϕ is accepted by an agent i of V when there exists a step of the game from which ϕ holds in the belief bases of i at each subsequent step; and ϕ is unanimously accepted when it is accepted by every agent of V . Now, given a piece of belief ϕ, is adding "more ϕ" in a BRG always beneficial to ϕ? More precisely, whenever a piece of belief ϕ is unanimously accepted in a BRG, is it always harmless to replace at the beginning some bases by ϕ, or more generally, by a base that is "closer" to ϕ, i.e., by a "promotion" of ϕ? This monotonicity condition is essential when one wants to investigate the potential manipulation of such sytems, in particular the control issue: consider a set of agents from a predefined subset C of V and an additional agent M who can "control" the agents from C, i.e., M can modify the initial beliefs of agents from C, then is it possible for M to make a piece of belief unanimously accepted? Such a control issue is significant for a number of multi-agent problems, including brand crisis management [Dawar and Pillutla, 2000]; in such applications, it is useful to know what information agents from C should convey to their acquaintances in order to avoid the propagation of negative perceptions.

In the next section we provide some preliminaries on BRGs. We then define and investigate in Section 3 the notion of promoting a formula ϕ in a belief base, and show that many rational change operators (including revision and contraction operators) can be used for the promotion purpose. We then formalize in Section 4 the monotonicity property based on promotion operators and show that this condition is not always satisfied by BRGs. As a consequence, replacing some agents' initial beliefs by a belief ϕ is not always the best way to make ϕ unanimously accepted. In Section 5 we show that the monotonicity property holds for BRGs based on the complete graph topology, focusing on revision policies relying on the merging operator based on a specific merging operator. We discuss some related work in Section 6 before concluding. For space reasons, proofs are omitted but can be found online at http:// www.cril.fr/ marquis/ ijcai16-long.pdf .

Belief Revision Games

Let L P be a propositional language built up from a finite set of propositional variables P and the usual connectives, including ⊕, the xor connective. ⊥ (resp. ) is the Boolean constant always false (resp. true). Formulae are interpreted in a standard way. M od(ϕ) denotes the set of models of the formula ϕ, |= denotes logical entailment and ≡ logical equivalence, i.e., ϕ |= ψ iff M od(ϕ) ⊆ M od(ψ) and ϕ ≡ ψ iff M od(ϕ) = M od(ψ). A belief base B denotes the set of beliefs of an agent, it is a finite set of propositional formulae interpreted conjunctively, so that B is identified with the conjunction of its elements. A profile C = B 1 , . . . , B n is a finite vector of belief bases. A Belief Revision Game (BRG for short) is formalized as follows [START_REF] Schwind | [END_REF]:

Definition 1 (Belief Revision Game). A Belief Revision Game (BRG) is a tuple G = (V, A, L P , B, R) where • V = {1, . . . , n} is a finite set of agents; • A ⊆ V × V is an irreflexive binary relation on V which
represents the set of acquaintances between the agents;

• L P is a finite propositional language;

• B is a mapping from V to L P where for each i ∈ V , B(i) (noted B i ) is the initial belief base of agent i;

• R = {R 1 , . . . , R n }, where each R i is the revision policy of agent i, i.e., a mapping from L P × L P in(i) to L P with in(i) = |{j | (j, i) ∈ A}| the in-degree of i, such that if in(i) = 0, then R i is the identity function.

Let G = (V, A, L P , B, R) be a BRG and let us denote C i the context of i, defined as the profile

C i = B i1 , . . . , B i in(i) where {i 1 , . . . , i in(i) } = {i j | (i j , i) ∈ A}. Then R i (B i , C i )
is the belief base of agent i once revised by taking into account her own current beliefs B i and her current context C i .

In a BRG, the beliefs of each agent evolve at each time step using her revision policy. This induces for each i ∈ V a belief sequence (B s i ) s∈N where B s i denotes the belief base of agent i after s steps, defined as B 0 i = B i and for each s ≥ 0,

B s+1 i = R i (B s i , C s i ), 1
where C s i is the context of i at step s. [START_REF] Schwind | [END_REF] showed that in any BRG, the belief sequence of each agent i is cyclic, i.e., in (B s i ) s∈N there exists a finite subsequence B b i , . . . , B e i such that for every j > e, we have B j j ≡ B b+((j-b)mod(e-b+1)) i

; the belief cycle Cyc(i) of an agent i corresponds to the series of this subsequence of belief bases

Cyc(i) = B b i , B b+1 i , . . . , B e i .
As we are interested in determining the pieces of beliefs resulting from the interaction of the agents, we focus on the outcome of each agent 1 Abusing notations, a context Ci = Bi 1 , . . . , Bi in(i) is here identified with the sequence Bi 1 , . . . , Bi in(i) .

i in G, denoted Acc G (i) and defined as:

Acc G (i) = {B s i | B s i ∈ Cyc(i)}.
We say that a formula ϕ is accepted by i in G if Acc G (i) |= ϕ, which means that ϕ is a logical consequence of every belief base in the belief cycle of i. G converges at step s if for each i ∈ V , B s+1 i = B s i . The formalization of a BRG allows each agent i to consider any revision policy R i ∈ R. However, one can take advantage of theoretical tools from Belief Change Theory (see e.g. [Alchourrón et al., 1985]), more precisely, belief revision and merging operators. A merging operator ∆ associates any formula µ (the integrity constraint) and any profile C with a new formula ∆ µ (C) (the merged base). A merging operator ∆ aims at defining the merged base as the beliefs of a group of agents represented by the profile, under some integrity constraint. Standard properties (denoted (IC0)-( IC8)) are expected for merging operators, and such operators are called IC merging operators (see [Konieczny and Pino Pérez, 2002] for details on these properties).

IC merging operators include some distance-based operators, i.e., operators that are based on the selection of some models of the integrity constraint, the "closest" ones to the given profile. These operators are characterized by a distance d between interpretations and an aggregation function f [Konieczny et al., 2004]. They associate with every formula µ and every profile C a belief base

∆ d,f µ (C) satisfying M od(∆ d,f µ (C)) = min(M od(µ), ≤ d,f C ), where ≤ d,f C is the total preorder over interpretations induced by C defined by ω ≤ d,f C ω if and only if d f (ω, C) ≤ d f (ω , C), where d f (ω, C) = f B∈C {d(ω,
(ω, B i ) | B i ∈ C .
Lastly, belief revision operators can be seen as belief merging operators applied to singleton profiles: indeed, if ∆ is an IC merging operator then the revision operator

• ∆ induced by ∆ defined for all bases B 1 , B 2 as B 1 • ∆ B 2 = ∆ B2 ( B 1 )
satisfies the standard AGM revision postulates [Alchourrón et al., 1985, Katsuno andMendelzon, 1992].

Let us go back to BRGs. Six classes of revision policies have been proposed in [START_REF] Schwind | [END_REF]

. Each of them, denoted R k ∆ (k ∈ {1, . . . , 6}
) is parameterized by an IC merging operator ∆. Each class is defined as follows,2 at each step s and for any agent i such that

C i = ∅: • R 1 ∆ (B s i , C s i ) = ∆(C s i ); steps s B s 1 B s 2 B s 3 0 p 1 ⊕ p 2 ¬p 1 ∧ ¬p 2 p 1 ∨ p 2 2k + 1 ¬p 1 ∨ ¬p 2 p 1 ⊕ p 2 p 1 ⊕ p 2 2k + 2 p 1 ⊕ p 2 ¬p 1 ∨ ¬p 2 ¬p 1 ∨ ¬p 2 Table 1: The belief sequences of Alex, Beth and Chris in G * . • R 2 ∆ (B s i , C s i ) = ∆ ∆(C s i ) ( B s i ) [= B s i • ∆ ∆(C s i )]; • R 3 ∆ (B s i , C s i ) = ∆( B s i , C s i ); • R 4 ∆ (B s i , C s i ) = ∆( B s i , ∆(C s i ) ); • R 5 ∆ (B s i , C s i ) = ∆ B s i (∆(C s i )) [= ∆(C s i ) • ∆ B s i ]; • R 6 ∆ (B s i , C s i ) = ∆ B s i (C s i ). Example 1 (continued). We consider the BRG G * = (V * , A * , L P * , B * , R * ) defined as follows. V * = {1, 2, 3}
where 1 corresponds to Alex, 2 to Beth, and 3 to Chris. A * = {(1, 2), (2, 1), (1, 3), (3, 1)} expresses that Alex knows Beth and vice-versa, and Alex knows Chris and vice-versa, but Beth and Chris are not connected. L P * is the propositional language defined from the variables P * = {p 1 , p 2 }, where p 1 stands for "the first meal is healthy" and p 2 means "the second meal is healthy." The initial beliefs of the group members are

B 1 = p 1 ⊕ p 2 , B 2 = ¬p 1 ∧ ¬p 2 and B 3 = p 1 ∨ p 2 .
Assume that all agents use the same revision policy,

R i = R 1 ∆ d H ,GMax for each i ∈ V * .
The belief sequences associated with the three agents are given in Table 1: the belief cycle of agent 1 (resp. 2, 3) is given by

(B 0 1 , B 1 1 ) (resp. (B 1 2 , B 2 2 ), (B 1 3 , B 2 3 )). We have for each i ∈ V * , Cyc(i) = p 1 ⊕ p 2 , ¬p 1 ∨ ¬p 2 and Acc G (i) = ¬p 1 ∨ ¬p 2 .
[ [START_REF] Schwind | [END_REF] studied the extent to which BRGs satisfy some basic logical properties depending on the class of revision policies used by the agents. They focused on the case where all agents use the same revision policy ranging over R k ∆ , k ∈ {1, . . . , 6}. It turned out that when the revision policy is induced from the merging operator ∆ d D ,Σ , i.e., the merging operator based on the drastic distance and the summation function, the underlying BRGs satisfy a number of expected properties [START_REF] Schwind | [END_REF]. They also developed a software available online at http:// www.cril.fr/ brg/ brg.jar, allowing one to play BRGs with various revision policies.

On the Notion of Promotion

Belief control in a multi-agent system can take various forms, depending on the meaning given to "control." Here, we are specifically interested in control strategies that consist in promoting a certain belief ϕ in the beliefs of the agents. A key issue to be addressed is then to determine what "promoting" precisely means in this context. A simple view is to consider that promoting ϕ in the belief base B of an agent consists in replacing B by a base equivalent to ϕ. While such a drastic way of promoting ϕ makes sense, it is not the only one. Thus, for instance, revising B by ϕ is another approach to do the job. Considering the whole spectrum of promotion techniques is interesting because in some scenarios it could be the case that the agent under consideration can be ready to promote ϕ by revising her own beliefs B with it, while she would be reluctant in questioning her whole base B and replacing it by ϕ. In a bribery context, she could for instance ask much more money to accept to change her base B to ϕ than to change it to the revision of B by ϕ.

We now characterize the notion of "promotion" of ϕ through a preorder ϕ over belief bases which reflects the closeness relationship to ϕ; thus, B ϕ B states that B is at least as close to ϕ as B. On this ground, promoting B consists in replacing B by any B satisfying B ϕ B: Definition 2 (ϕ-promotion). For every formula ϕ ∈ L P , the ϕ-promotion relation is the binary relation ϕ on L P × L P defined for all belief bases B, B as B ϕ B if and only if

B ∧ ϕ |= B |= B ∨ ϕ.
Obviously, one can check that for any ϕ ∈ L P , the binary relation ϕ is reflexive and transitive. More precisely: Proposition 1. For every formula ϕ ∈ L P , (L P , ϕ ) is a Boolean lattice (L P , ϕ , ϕ , ¬, ϕ, ¬ϕ), where:

• ϕ is the meet operation defined for each B, B ∈ L P as B ϕ B = (B ∧ B ) ∨ ((B ∨ B ) ∧ ϕ),
• ϕ is the join operation defined for each B, B ∈ L P as

B ϕ B = (B ∧ B ) ∨ ((B ∨ B ) ∧ ¬ϕ),
• ¬ is the complement corresponding to the standard logical negation ¬,

• ϕ is the least element, i.e., for each B ∈ L P , ϕ ϕ B,

• ¬ϕ is the top element, i.e., for each B ∈ L P , B ϕ ¬ϕ.

where formulae of L P are considered up to equivalence.

Every base B promoting ϕ in B satisfies ϕ ϕ B ϕ B. Thus B is (up to logical equivalence) the greatest formula w.r.t. ϕ promoting ϕ in B, and ϕ is (up to logical equivalence) the least formula w.r.t. ϕ promoting ϕ in B. Stated otherwise, the least demanding promotion of ϕ w.r.t. B consists in letting B unchanged, while the promotion of ϕ w.r.t. B leading to a formula as close as possible to ϕ consists in replacing B by ϕ.

The following model-theoretic characterization of the notion of promotion can be derived easily. denotes the symmetric difference between sets: Proposition 2. Given a formula ϕ, let B and B be two belief bases such that B promotes ϕ w.r.

t. B. Then ∃S ⊆ Mod (B) Mod (ϕ) such that Mod (B ) = (Mod (B) ∩ Mod (ϕ)) ∪ S.
This proposition also illustrates the fact that B and ϕ plays symmetric role in the notion of promotion. Indeed, making B closer to ϕ is precisely the same as making ϕ closer to B:

Proposition 3. B ϕ B if and only if B B ϕ.
When a promotion of ϕ in B is achieved, the set of interpretations assigning different truth values to the base B and to ϕ may only diminish. Formally: Proposition 4. Given a formula ϕ, let B and B be two belief bases such that B promotes ϕ in B. Then

Mod (B ) Mod (ϕ) ⊆ Mod (B) Mod (ϕ).
We define a promotion operator as a mapping from L P × L P to L P such that ψ ϕ ϕ ψ. Interestingly, some belief change operators of the literature are promotion operators. We recall below some of the postulates for rational revision operators •, and contraction operators - [Katsuno andMendelzon, 1992, Caridroit et al., 2015], as well as some postulates for arbitration (alias symmetric revision) operators [START_REF] Liberatore | [END_REF]]:

(R1) ϕ • µ |= µ. (R2) If ϕ ∧ µ is consistent, then ϕ • µ ≡ ϕ ∧ µ. (C1) ϕ |= ϕ -µ. (C2) If ϕ |= µ, then ϕ -µ |= ϕ. (C4) If ϕ |= µ, then (ϕ -µ) ∧ µ |= ϕ. (LS2) ϕ ∧ µ |= ϕ µ. (LS7) ϕ µ |= ϕ ∨ µ.
Proposition 5. Let ϕ be a formula and let B be a belief base. Let • be any revision operator satisfying (R1) and (R2), let be any KM contraction operator satisfying (C1), ( C2) and (C4), and let be any arbitration operator satisfying (LS2) and (LS7). We have: We can now lift the relation of formula promotion to BRGs defined on the same set of variables V , acquaintance relation A, propositional language L P and revision policies R. Given two BRGs G = (V, A, L P , B, R) and G = (V, A, L P , B , R) and a formula ϕ, we note G ϕ G if and only if for each agent i ∈ V , B i ϕ B i . Finally, we note G ϕ any BRG G such that G ϕ G. Observe that such a promotion operation of ϕ in G can be non-uniform, i.e., it is not necessarily the case that the promotion of ϕ in distinct bases of G is achieved thanks to the same promotion operator. For instance, it can be the case that B i = B i for agent i ∈ V , while B j = B j • ϕ for agent j ∈ V , and B k = ϕ for agent k ∈ V .

1. (i) B •ϕ ϕ B ∧ϕ ϕ B, (ii) B ∨ϕ ϕ B -¬ϕ ϕ B,

On Monotonicity in BRGs

In this section, we focus on the issue of monotonicity for BRGs instantiated with revision policies from the six classes defined in the previous section. Given a merging operator ∆ and E ⊆ {1, . . . , 6} R E ∆ denotes the set

{R k ∆ | k ∈ E}. We use the simpler notation R k ∆ instead of R E ∆ when E = {k}. Given a class G of BRGs and E ⊆ {1, . . . , 6}, G(R E ∆ ) is the subclass of all BRGs (V, A, L P , B, R) from G where for each R i ∈ R, R i ∈ R E ∆ .

Additionally, a set of revision policies R E

∆ is said to satisfy a given property P on a given class G of BRGs if all BRGs from G(R E ∆ ) satisfy P . Given a BRG G = (V, A, L P , B, R), a subset C of V of so-called "controllable agents" whose initial beliefs can be modified, and a formula ϕ, one is interested in determining how to modify the belief bases of agents in C in order to make

steps s B s 1 B s 2 B s 3 0 p 1 ⊕ p 2 ¬p 1 ∧ ¬p 2 p 1 ∧ p 2 s ≥ 1 p 1 ⊕ p 2 p 1 ⊕ p 2 p 1 ⊕ p 2
Table 2: An example of control strategy for G * where ϕ = p 1 ∨ p 2 is unanimously accepted.

ϕ unanimously accepted in the resulting game (when possible). The objective is thus to determine a successful "control strategy" to be implemented in order to reach the goal when it can be reached. A control strategy for G given C takes here the form of a mapping σ from C to L P , stating for each i ∈ C that B i must be replaced by σ(i); it is successful for ϕ if ϕ is unanimously accepted in the BRG obtained by applying σ to G. Typically, one wants to minimize the number of agents in C to be controlled, but the optimization problem under consideration can also be much more complex (for instance, it may take into account the cost of controlling each agent in C which is not always uniform). Among the potential control strategies is the basic strategy σ ϕ for G given C defined for any i ∈ C by σ(i) ≡ ϕ: it simply amounts to promoting ϕ as much as possible in the belief base of each agent from C. We have the following surprising result: Proposition 6. Given a BRG G = (V, A, L P , B, R), a set C ⊆ V of controllable agents, and a formula ϕ, it can be the case that the basic strategy σ ϕ for G given C is not successful for ϕ, while a control strategy for G given C which is successful for ϕ exists. Example 1 (continued). Assume that the goal of the restaurant manager is to convince all protagonists that at least one of the meals is healthy, i.e., ϕ = p 1 ∨ p 2 . Note that at the beginning, Chris' beliefs coincide with this goal (since B 3 = ϕ) and that ϕ is not unanimously accepted. So if Chris is the only controllable agent, the basic strategy σ ϕ is not successful. However, when we replace Chris' beliefs by p 1 ∧ p 2 instead, we get that Acc G * (i) = p 1 ⊕ p 2 for each i ∈ V , so p 1 ∨ p 2 is unanimously accepted (see Table 2). This shows that control is possible here given C = {3} as the only controllable agent, but not with the basic strategy.

This example illustrates the complexity of the controllability issue for BRGs in the general case. This explains why it is important to identify some conditions on BRGs for which focusing on the basic strategy would be enough to decide whether a positive answer can be given or not to the controllability question. In the following, we show that some monotonicity properties can be used as such conditions. A first property of monotonicity has been introduced in [START_REF] Schwind | [END_REF]. Given a BRG G = (V, A, L P , B, R), a formula α and an agent i ∈ V , let us denote G i→α the BRG (V , A, L P , B , R) where B maps V to {B 1 , . . . , B n }, with B i = B i ∧ α and for every j ∈ V , j = i, B j = B j . Definition 3 (Monotonicity (Mon)). A BRG G = (V, A, L P , B, R) satisfies (Mon) if whenever ϕ is unanimously accepted in G, ϕ is unanimously accepted in G i→ϕ for every i ∈ V .

(Mon) is similar to the monotonicity criterion in Social Choice Theory. In the BRG context, a formula ϕ that is unanimously accepted should still be so if some agent's initial

B s i ∧ ϕ max (B s ) |= ⊥ (case (i)) ϕ max (B s ) |= B s i (case (ii)) Otherwise (case (iii)) R 1 ∆ d D ,Σ ϕ max (B s ) ϕ max (B s ) ∨ (ϕ max -1 (B s ) ∧ ¬B s i ) ϕ max (B s ) ∧ ¬B s i R 2 ∆ d D ,Σ ϕ max (B s ) ϕ max (B s ) ϕ max (B s ) ∧ ¬B s i R 3 ∆ d D ,Σ ϕ max (B s ) ϕ max (B s ) ϕ max (B s ) R 4 ∆ d D ,Σ ϕ max (B s ) ∨ B s i ϕ max (B s ) ϕ max (B s ) ∨ B s i R 5 ∆ d D ,Σ B s i ϕ max (B s ) B s i R 6 ∆ d D ,Σ B s i ϕ max (B s ) ϕ max (B s ) ∧ B s i Table 3: B s+1 i
depending on the revision policy applied by agent i in any BRG from G com (R {1,...,6}

∆ d D ,Σ ).
beliefs were "strengthened" by ϕ. Note that the strengthening of a belief base by a formula ϕ involved here consists in just expanding the base by ϕ. However, one could consider weaker versions than expansion, i.e., the promotion operators we formalized in the previous section. So we introduce now a stronger version of the monotonicity property (cf. Definition 3) on BRGs based on the promotion relation:

Definition 4 (Strong Monotonicity (SMon)). A BRG G = (V, A, L P , B, R) satisfies (SMon) if for each i ∈ V , if ϕ is unanimously accepted in G, then ϕ is unanimously accepted in any BRG G ϕ.
It is easy to see that (SMon) implies (Mon) and that the converse does not hold in general. BRGs satisfying (SMon) are interesting in terms of strategy-proofness. Indeed, Proposition 1 tells us that ϕ is the least element of (L P , ϕ ). As a consequence, for such BRGs, determining whether it is possible to convince all the agents involved in the BRG to accept some piece of belief ϕ simply amounts to determining whether ϕ is unanimously accepted in the BRG obtained by the promotion of ϕ in every B i associated with a controllable agent so that B i ϕ = ϕ. Stated otherwise: Proposition 7. Let G = (V, A, L P , B, R) satisfying (SMon), a set C ⊆ V of controllable agents, and a formula ϕ. If the basic strategy σ ϕ for G given C is not successful for ϕ then no control strategy for G given C is successful for ϕ.

An interesting issue now is to know whether there are BRGs satisfying (SMon). We provide a positive answer to this question in the next section.

The Case of Complete Graphs

We now study the extent to which (SMon) is satisfied by BRGs whose acquaintance graph is a complete graph. This simple topology is adequate to the cases when all the agents of V know each other (for instance, this is the case in meetings where all agents are sitting around a table). We simply call the corresponding class of BRGs the complete BRGs: Definition 5 (Complete BRG). A BRG G = (V, A, L P , B, R) is complete if (V, A) is a complete graph, i.e., for all i, j ∈ V , i = j, (i, j) ∈ A. Given a class G of BRGs, G com denotes the subclass of complete BRGs from G.

In the general case, (SMon) is not satisfied by BRGs from G com (R k ∆ ) with k ∈ {1, . . . , 6}, even when ∆ is "fully" rational in the sense that it satisfies all IC postulates. Indeed:

Proposition 8. For ∆ ∈ {∆ d H , , ∆ d H ,GMax }, for any k ∈ {1, . . . , 6}, R k ∆ does not satisfy (SMon) on G com (R k ∆ ).
In the following, we investigate the monotonicity issue for complete BRGs when the merging operator used for defining the revision policies is the distance-based merging operator based on the drastic distance (and the summation function) ∆ d D ,Σ . Computing ∆ d D ,Σ µ (C) consists in selecting in the models of the integrity constraint µ those satisfying as many bases of the profile C as possible. Several works have proved this specific operator to satisfy a number of expected properties, e.g., some (language) independence conditions [START_REF] Konieczny | Belief base rationalization for propositional merging[END_REF][START_REF] Marquis | [END_REF]. In particular, ∆ d D ,Σ is robust from the point of view of strategyproofness [START_REF] Everaere | [END_REF], this is why this operator appears as a good candidate for the monotonicity issue.

The following notations are used in the rest of this section. Let C be a profile and ω be an interpretation.

C = {B i | B i ∈ C}. #E denotes the number of elements from a finite set E. # max (C) is the maximal number of belief bases from C that are consistent when interpreted conjunctively, i.e., # max

(C) = max(#{C | C ⊆ C, C |= ⊥}). {C | ω |= C} = {B i ∈ C | ω |= B i }. ϕ max (C) = ∆ d D ,Σ (C). and ϕ max -1 (C) is any formula ϕ such that M od(ϕ) = {ω | #{C | ω |= C} = # max (C) -1}.
We now present a number of characterization results concerning stability and acceptability for such BRGs, which are interesting by their own, and will be exploited to identify classes of BRGs offering (SMon). We first show that a stronger version of the agreement preservation property (AP) (see [START_REF] Schwind | [END_REF]) is satisfied by these BRGs:

Proposition 9. Let G = (V, A, L P , B, R) be a BRG from G com (R {1,...,6} ∆ d D ,Σ ). If there is a step s where {B s i | i ∈ V } is consistent, then for each i ∈ V , Acc G (B i ) = {B i | i ∈ V }. Moreover, G converges at step s+2 at most. It converges at step s + 1 at most if G ∈ G com (R {2,...,6} ∆ d D ,Σ ).
We now intend to characterize the outcome of a BRG from its initial state. Beforehand, let us introduce an intermediary result characterizing the belief base of any agent in a BRG from

G com (R k ∆ d D ,Σ )
where k ∈ {1, . . . , 6}, at some step s+1 given the belief bases of all agents at step s: Lemma 1. Let E ⊆ {1, . . . , 6} and G be a BRG from G com (R E ∆ d D ,Σ ). Then for each agent i ∈ V and each step s, her base B s+1 i can be characterized as shown in Table 3. Obviously enough, a consequence of Table 3 is that all six revision policies from R k ∆ d D ,Σ , k ∈ {1, . . . , 6}, remain distinct. Moreover, in the case when all agents have the same revision policy among R k ∆ d D ,Σ , k ∈ {1, . . . , 4}, the outcome of complete BRGs can be fully characterized:

As far as we know, the control problem for multi-agent systems has not been investigated so far in settings similar to BRGs. Though there are many works on opinion dynamics where some control or influence issues have been studied, the opinion of an agent takes typically the form of a real number, as in Hegselmann-Krause's model [START_REF] Hegselmann | [END_REF]. Let us mention among others [START_REF] Tsang | [END_REF], Bloembergen et al., 2014, Ranjbar-Sahraei et al., 2014, Blondel et al., 2009]. The very nature of the agents' opinions (real number vs. propositional formula) makes these studies and our own approach quite unrelated. Indeed, unlike real numbers that can be simply averaged, merging propositional formulae is a much more complex process (this is why many works on the topic in the knowledge representation area have been done for two decades). The quite paradoxical result presented in the paper (roughly, promoting some belief is not guaranteed to be the safest way to make it unanimously accepted) echoes paradoxes pointed out in other settings for multi-agent systems, in particular social network games [START_REF] Apt | [END_REF]. However, the resemblance is only at a shallow level since the BRG model departs a lot from social network games. Especially, social network games are "true" games, unlike BRGs (in the BRG model, agents do not have strategies and there is no payoff based on the adequacy of an agent's beliefs with the beliefs of her acquaintances).

On the other hand, some control issues (under various forms: manipulation, bribery, etc.) have received much attention recently in voting theory, especially from the point of view of computational complexity. See among many others [Amanatidis et al., 2015, Bredereck et al., 2015, Faliszewski et al., 2015, Loreggia et al., 2015, Faliszewski et al., 2014, Bouveret and Lang, 2014, Christian et al., 2007]. However, the results obtained in voting theory cannot be exploited directly for BRGs since in BRGs the beliefs of the agents may evolve after each communication step (when voting is considered, the users preferences are typically considered as fixed and the agents do not influence each other). An exception is [START_REF] Hassanzadeh | [END_REF] which shows how to reach a consensus on rankings (encoding the agents preferences) by iterative voting. Nevertheless, the corresponding model is quite different from the BRG one since it deals with preferences, and not with beliefs, and the system dynamics is ruled by distinct mechanisms (voting vs. revision). Furthermore, belief control has not been investigated in this model (the focus is on convergence issues).

Finally, though other approaches have been considered for modeling the belief dynamics of a group of agents (see dynamic epistemic logic [Harel et al., 2000, Hendricks andSymons, 2006], or more recent studies in propositional logic [Gauwin et al., 2007, Delgrande et al., 2007, Grandi et al., 2015]), the belief control issue for such settings has not been considered as well.

Conclusion

We pointed out a quite paradoxical result in belief diffusion: in a network of agents, replacing some agents' belief bases by a piece of belief ϕ may fail to make ϕ unanimously accepted, while other successful strategies exist nevertheless. However, we have identified a class of BRGs satisfying a property of strong monotonicity, and thus, avoiding this paradox, making for these BRGs the belief control issue easier to manage.

As perspectives for further research, we plan to identify additional classes of BRGs for which the strong monotonicity property holds, e.g., by considering other topologies as the line, single loop and more generally regular graph topologies. For all these BRGs, the next step will be to search for control strategies by focusing now on the "who" issue, i.e., which agents from a predefined set C should be considered. Another interesting research direction is to investigate on its own the notion of "promotion" of a piece of belief, as an attempt to provide an uniformized axiomatization of a large class of standard belief change operators.

  B)} and d(ω, B) = min ω |=B d(ω, ω ). Usual distances are d D , the drastic distance (d D (ω, ω ) = 0 if ω = ω and 1 otherwise), and d H the Hamming distance (d H (ω, ω ) = n if ω and ω differ on n variables). Using aggregation functions such as Σ and GMax lead to IC merging operators. For instance, GMax operators consider for each profile C the total preorder over interpretations ≤ d,GMax C defined by ω ≤ d,GMax C ω if and only if d GMax (ω, C) ≤ lex d GMax (ω , C) (where ≤ lex is the lexicographic ordering induced by the natural order) and d GMax (ω, C) is the vector of numbers d 1 , . . . , d n obtained by sorting in a non-increasing order the vector d

When using a merging operator without integrity constraints we just note ∆(C) instead of ∆ (C) for improving readibility.

This is even the case for • andwhen they correspond one another thanks to Levi/Harper identities.

Proposition 10. Let k ∈ {1, . . . , 4} and G = (V, A, L P , B, R) be a BRG from G com (R k ∆ d D ,Σ ). Then for each i ∈ V , Acc G (i) = ∆ d D ,Σ ( B 1 , . . . , B n ).

The cases when all agents have the same revision policy

These results allow us now to derive monotonicity results for the class of complete BRGs we are dealing with: Proposition 12. Let k ∈ {1, . . . , 6}. Then all BRGs from the class G com (R k ∆ d D ,Σ ) satisfy (SMon). A consequence of Propositions 7 and 12 is that considering the basic strategy is enough for BRGs from G com (R k ∆ d D ,Σ ), i.e., to decide whether a control strategy exists for making a formula ϕ accepted by all agents in such a BRG, it is enough to focus on the basic strategy. Let us illustrate how these monotonicity results apply to the following slightly modified version of our running example: Example 1 (continued). Consider again the BRG G * = (V * , A * , L P * , B * , R * ) from our running example, and let G * be the BRG (V * , A * , L P * , B * , R * ) where:

• A is the total relation over V * , i.e., Beth and Chris know each other as well;

and B 3 = ¬p 1 ∧ ¬p 2 , i.e., the beliefs of Alex and Beth in G * remain the same as in G * , but Chris now initially believes in G * that none of the two meals is healthy.

From Proposition 10, we get that Acc G * (i) = ∆ d D ,Σ ( B 1 , B 2 , B 3 ) ≡ ¬p 1 ∧¬p 2 for each i ∈ V * . Note that p 1 ∨ p 2 is not accepted by any agent. By applying the basic strategy σ ϕ where ϕ = p 1 ∨ p 2 and when Chris is the only controllable agent, one gets that the outcome of each agent in the resulting BRG becomes p 1 ⊕ p 2 . We have now ϕ being unanimously accepted, which means that σ ϕ is successful.


J Le Kernec
email: julien.lekernec@nottingham.edu.cn

O Romain

P Garda

J Denoulet

Empirical comparison of Chirp and Multitones on experimental UWB Software Defined Radar prototype

Keywords: Radar, Multitones, OFDM, UWB, Software Radio I

This paper proposes and tests an approach for an unbiased study of radar waveforms' performances. Using the ultrawide band software defined radar prototype, the performances of Chirp and Multitones are compared in range profile and detection range. The architecture was implemented and has performances comparable to the state of the art in software defined radar prototypes.

The experimental results are consistent with the simulations.

INTRODUCTION

In the past decade, digital architectures gradually replaced analog circuitry. As a result, purely digital waveforms have emerged (Multitones being a prominent example that has a wide array of commercial applications). These purely digital waveforms allow increased data throughput and are more robust against fading having its primary commercial application in modern telecommunication standards such as wireless LAN [START_REF] Terry | OFDM Wireless LANs: A Theoretical and Practical Guide[END_REF]. To date, Multitones have seldom been used in radar applications.

The most common radar signal used is the linear frequency modulated pulse (also known as Chirp). This signal has been commonly used in radar for several decades [2]. The adoption of Multitones in radar applications hasbeen slow to develop for a variety of reasons. Commercial applications are unlikely to be developed unless and until there is a viable need for them. Recently, the use of a swarm of drones for reconnaissance missions are required to perform Synthetic Aperture Radar (SAR) imaging and networking simultaneously to maintain formation, and send/receive data while imaging the scene. This is not possible with just Chirp. As a result, there has been an increasing interest for the use of multifunction signals such as Multitones.

Recent advances in AD/DA converters and processing capabilities, synthesizing, digitizing and processing ultrawide band (UWB) signals is now feasible on a digital platform. This allows finer resolution for imaging applications, spectrum insertion and the use of signal and frequency agility. These advances also enable software defined radar, which can dynamically reconfigure its RF frontend, middleware and processing algorithms. Software defined radar can thus be multifunction switching from one mode to the other such as surveillance, tracking, imaging and also telecommunications.

The widespread adoption of Multitones will only be possible when the capabilities of the signal match the specific tasks that are required. Then and only then can Multitones be successfully integrated into applications and subsequently put to operational use. As such, it is the confluence of factors that ultimately determine the relevance and ultimate integration of Multitones for multifunction radar applications Specifically, developing a technology without first having a commercially viable application is unlikely.

Multitones are therefore seen as a good candidate for the next generation of digital radar. Multitones are phase-coded to reduce Peak-to-Mean Envelope Power Ratio (PMEPR) and improve power amplifier efficiency. The sub-band independence [START_REF]Simulated Imaging Performance of UWB SAR Based on OFDM[END_REF] allows an independent processing of each band for multifunction operation and ensures detection even in presence of frequency selective fading [START_REF]Waveshaping of multicarrier signal for data transmission over wireless channels[END_REF]. The signal diversity is important in terms of low probability of interception to evade radar counter measures and allow frequency reuse when multiple radars operate in the same vicinity [START_REF]Train of diverse multifrequency radar pulses[END_REF]. As a result, our research question is how do Multitones signals compare to Chirp signals in multifunction radar applications?

The rest of the paper is developed as follows, section II reviews the literature on Multitones performances for radar applications and existing software defined radar platforms. Section III describes two possible radar architectures and the design considerations that lead to the chosen architecture for prototyping presented in section IV. Finally, in Section V, the radar waveforms' performances are compared in simulation and experimentally tested on the prototype.

II. LITERATURE REVIEW

There has been recent work dealing with the communication aspect of Multitones in radar without consideration of the performance of the radar [c.f. 6]. However, a few studies have examined the relative performance of Multitones in radar applications [START_REF]Improvement in target detection performance of pulse coded Doppler radar based on multicarrier modulation with fast Fourier[END_REF][8] [START_REF]Solving Doppler ambiguity by Doppler sensitive pulse compression using multi-carrier waveform[END_REF]. One such study [START_REF]Improvement in target detection performance of pulse coded Doppler radar based on multicarrier modulation with fast Fourier[END_REF] provided a simulation of single carrier and Multitones radar systems. They found that the required constant false alarm rate detection threshold is lower for Multitones than for a single carrier radar system with polyphase codes. In short, they found a higher level of precision resulting from the use of Multitones.

Two additional studies have examined the relative performance of trains of diverse Multitone pulses coded in phase and amplitude [2] [START_REF] Lellouch | OFDM waveforms for frequency agility and opportunities for Doppler processing[END_REF]. Using this technique, they both achieve near thumbtack ambiguity functions. This ambiguity function does not suffer from range-Doppler coupling as does Chirp [2]. In both cases, this ambiguity function comes at the cost of a higher pedestal level. New processing capabilities are emerging such as Doppler resolution while using agility [START_REF] Lellouch | OFDM waveforms for frequency agility and opportunities for Doppler processing[END_REF]. This particular feature cannot be performed with classic radar waveforms while using agility. In [START_REF]Solving Doppler ambiguity by Doppler sensitive pulse compression using multi-carrier waveform[END_REF], the Doppler ambiguity is resolved over one pulse train.

Multitones show potential for new radar advances, such as Doppler resolution using agility [START_REF] Lellouch | OFDM waveforms for frequency agility and opportunities for Doppler processing[END_REF]. However, it is important to note that the results for this part were mostly simulated results. It also appears that the basic performances of Multitones for radar systems are not well known and the literature lacks a viable reference to compare it to. Hence the simulations presented in section IV will be compared to experimental results described in part III. The reference in radar waveforms is the linear frequency modulated (LFM) [2] and its performances will be compared against Multitones' performances.

Concerning software radar platforms, very few papers report a full system implementation and those reported are laboratory prototypes. Four radar prototypes implementing Multitones signals were reviewed and compared: PANDORA [START_REF] Fmcw/Sfcw Radar | Pandora multifrequency[END_REF] which is the first experimental OFDM radar, an RCS measuring system [START_REF] Paichard | Microwave Camera for Multi-Dimensional Analysis of the RCS of Time-Varying targets[END_REF], a dual use SAR imaging and telecommunications system [START_REF]Radar and data communication fusion with UWB-OFDM softwaredefined system[END_REF] and a Software Defined Radio platform IDROMel [START_REF]Air Interface -IDROMel[END_REF].

A few design rules can be drawn from these architectures. First, if the AD/DA converters' instantaneous bandwidth and/or sampling frequency are not sufficient for direct synthesis or direct sampling, a super-heterodyne structure is required. The radar prototypes display submetric spatial resolution and thus digitizers sampling frequencies are at least 1 GS/s. However sampling schemes are diverse: sub-Nyquist, bandpass or direct. Finally, the frequency tuning ranges are at least 1 GHz wide. The design of the architecture should be kept simple, with as little components as possible, one or two downconversions at most. Unlike Chirp signal, stretch processing isn't applicable to Multitones thus whichever waveform is used, it should be fully digitized.

Reconfigurable radar technology is still in its early stage. The reconfiguration is limited in terms of the number of carriers, the step size, the bandwidth, or its hardware architecture has to be split into several sub-bands. These features are usually at the cost of increased hardware complexity or increased interferences in the receiver.

III. CONCEPTION OF SOFTWARE-DEFINED RADAR

This section is a description of an approach that can be used for an unbiased study of radar waveforms to the implementation of the prototype examined in this study.

A. Design approach for an unbiased experimental study

In order to unbiasedly compare different waveforms, it is essential that waveform-independent criteria are used. Further, to evaluate the performances without bias, the simulated processes and the experimental test bench should be identical. The maximum detection range and pulse compression in range profile can be used as a first step to evaluate radar waveform performances.

To compare the different waveforms, it is not sufficient to simply examine simulation results; and thus this comparison should be experimentally validated. It is therefore necessary to develop a software defined radar prototype that can test the waveforms under study without any bias. The novel approach is to compare the studied waveforms on the same platform to remove any bias. In this paper, simulations and measurements are designed to provide the basis for an unbiased study of the radar waveforms.

It should be noted that the radar prototype should be designed prior to the simulations, this way the characteristics of the prototype can then be fed to the simulator for a subsequent and direct comparison between simulated and experimental results.

B. Experimental Design 1) Design of RF system

A few constraints were established for the test bench design. The first step was to optimize the instantaneous bandwidth to maximize the radar spatial resolution. Hence, the bandwidth should be greater than 500 MHz to perform as well as state of the art radar prototypes [START_REF]Radar and data communication fusion with UWB-OFDM softwaredefined system[END_REF][10] [START_REF] Paichard | Microwave Camera for Multi-Dimensional Analysis of the RCS of Time-Varying targets[END_REF]. The radar should support any type of waveform with no changes to the RF frontend. These two requirements ensure an unbiased study of various waveforms on the same prototype. Also a reference channel is implemented to compensate for some of the circuit transfer function. This constraint is a special feature that is not normally implemented in operational radar systems but does allow refreshing the matched filter dynamically to compensate for any fluctuations in transfer function especially with power amplifiers.

Due to spatial constraints on the experimental grounds, a maximum of 50 m in slant range is achievable. Consequently, the architecture must be bi-static and emit in continuous wave to allow for pulse compression gain greater than 20 dB.

Two architectures are proposed as candidates for the implementation: frequency-interleaved, parallel.

The frequency-interleaved architecture is inspired from the prototype in [START_REF] Paichard | Microwave Camera for Multi-Dimensional Analysis of the RCS of Time-Varying targets[END_REF]. It is investigated because it reduces the number of components and the number of ADC channels. The parallel architecture is derived from the frequency interleaved architecture. Although more components are required, it has a potential for more versatile usage. The signal is directly synthesized in intermediate frequencies (IF) ranging from 1 to 2 GHz and a low pass filter removes the mirror image. The IF signal is up-converted in radio frequencies (RF) ranging from 9.9 to 10.9 GHz by F LO1 = 8.9 GHz, and a band pass filter removes the mirror image. For short range applications, the signal can be amplified by a low noise amplifier; and for longer ranges, a power amplifier can be used. At the output of the amplifier stage, a 20dB directional coupler splits the signal: the coupled output feeds the signal to the reference channel and the direct path is connected to the transmitter antenna feed. The backscattered signal is received by the second antenna which is connected to the test channel. The received signal travels through a low noise amplifier and a band pass filter removes the mirror image before downconversion by F LO1 = 8.9 GHz. The signal in the reference channel is attenuated and down-converted by F LO2 = F LO1 = 8.9 GHz. In both the reference and the test channels, the signals are band pass filtered to avoid aliasing and are then amplified prior to digitization.

b) Frequency-interleaved architecture

The radar operates in continuous wave mode; thus the spectra of any signal is discrete and the frequency step Δf (e.g. 2 MHz) is the inverse of the signal period T (e.g. 500 ns). This property is exploited to design the frequency-interleaved architecture.

Paichard [START_REF] Paichard | Microwave Camera for Multi-Dimensional Analysis of the RCS of Time-Varying targets[END_REF] provides a conceptual framework for the development of the frequency-interleaved architecture used in this study. Compared to the parallel architecture, the reference channel down-conversion-frequency is F LO2 = 9 GHz = F LO1 +Δf/2. Since the frequencies of the test channel and reference channel are not overlapping, they can be added using a power combiner, thus both signals are merged together, and the frequency step of the resulting signal is Δf/2 = 1 MHz. This architecture presents the advantage of digitizing the reference and test signals on the same ADC, thus reducing by half the number of required ADC channels as well as reducing the number of components.

2) Design of the Signal processing algorithms

The algorithms were designed to process signals impartially to allow for an unbiased comparison. Radar systems use pulse compression in order to detect targets; the optimum match filtering process in white Gaussian Noise was chosen for implementation.

Two algorithms were used :  The first algorithm employed radix-2 FFT and is suitable only for the parallel architecture.  The second algorithm used DFT due to constraints on data extraction for frequency-interleaved signals.

In both cases, the only variable in the algorithms is the input vector size, no other reconfiguration is necessary. Section 3 estimates the required processing power for each architecture; considering the Neptune VXS 2 [13] ADC will be implemented for digitization at 2GS/s. Since the test signal delay is unknown a priori, a sliding window that is three times the signal period is implemented for the test channel. This guarantees that whatever the signal returns delays are, a complete impulse response is generated without losses on the edges of the pulse compression. Hence, this algorithm is suitable for either the parallel or the timeinterleaved architectures.

Both vectors have unit sizes equal to M (e.g. 1000) which is the signal period T (e.g. 500ns) times the sampling frequency (2GS/s). For faster processing, radix-2 FFT is used, thus the digitized vector length 3M for the test channel and M for the reference channel are zero-padded ZP up to the next power of 2 greater than (4M-1). (4M-1) is the size of the crosscorrelation between 3M and M. The radar system only generates the real part of the signal. The complex values of the signal must therefore be reconstructed using a Hilbert transform Ĥ.

The signals are digitally down-converted to baseband BB, then, a window function w(n), such as Rectangle or Hamming, is applied over the pulse length M on the reference. The apodization by Hamming window limits the effect of intersymbol interference (ISI) for telecommunication signals and increases the contrast of the impulse response at the cost of a 38 % widening of the main lobe at 3 dB. A radix-2 FFT is applied on both test and reference signals to move to frequency domain. The complex conjugate ()* of the reference signal is multiplied element by element to the test signal. This operation is equivalent to a cross-correlation in time domain. Then, to obtain the impulse response in time domain, a radix-2 IFFT is applied. The complete pulse compression ranges from M/2 to (3M/2-1), giving a zero delayed response centred within that window. The reference signal on M samples is then switched back to time domain using an IDFT. This operation enables the final down-conversion BB to compensate for the slight phase modulation resulting from the frequency shift Δf/2. A window w(n) can be applied in a time domain.

The reference signal is returned to frequency domain with a DFT. Its complex conjugate ()* is multiplied element by element to the test signal. This realizes the equivalent of a time domain cross-correlation. Finally an IDFT is applied to obtain the pulse compression.

C. Initial considerations for experimental implementation

In order to quantify the required processing power, the characteristics of the Neptune VXS 2 [13] ADC that will be implemented in the radar will be used for the estimations. The ADC Neptune VXS 2 encodes the samples on 10 bits, meaning that the data is encoded on 2 bytes. Thus the data flux is 4 GB/s per channel at 2 GS/s when digitizing continuously.

(12 + 1) •

(1)

6 + 35 • 2 ( + 1) • (2)
Where n is the number of channels, M is the vector length and Y is an integer so that 4M ≤2 Y Figure IV: required processing power for the proposed radar architectures in TMACS (10 12 MACS) wrt to input vector length -considering a sampling frequency of 2GS/s, a word length of 10bits Figure IV illustrates that the processing for frequencyinterleaved architecture is intractable and therefore dismissed for implementation. The processing power for the other architecture is in the TMACS (10 12 MACS) region but within reach for the announced capabilities of the newest generation of FPGAs. The Altera Stratix V [14] performs up to 2.5 TMACS and Xilinx Virtex 7 [START_REF][END_REF] performs up to 5.314 TMACS. Although the algorithm for any vector length still has to be implemented on FPGA, real-time signal processing with two ADC channels at 2 GS/s and a resolution of 10 bits is feasible.

Even if the processing power is within reach, decimation strategies and other pre-processing schemes should be investigated to reduce the required MACS and data throughput for storage. If the radar uses pulse bursts rather than continuous wave emission, these requirements would be reduced proportionally with the pulse repetition period at a given pulse length.

IV. EXPERIMENTAL SETUP OF THE SOFTWARE DEFINED RADAR PROTOTYPE IMPLEMENTATION

As illustrated in Figure V, the implementation of the radar prototype is detailed [START_REF] Kernec | Case study analysis of linear Chirp and multi-tones radar signals through simulations and measurement with HYCAM-Research Test Bench[END_REF].

The radar has 800 MHz instantaneous bandwidth per channel, emits in X-band between 10 GHz and 11.6 GHz. It has 1.6 GHz agility and has AD/DA converter resolution of either 8 or 10 bits. This prototype supports any kind of waveforms for an unbiased analysis. The waveform agility is digitally controlled and no hardware modification is required.

Table I compares the characteristics of the proposed prototype to those of the platforms as found in [START_REF]Radar and data communication fusion with UWB-OFDM softwaredefined system[END_REF][10] [11][12]. This software defined radar prototype is comparable in performances with state of the art platforms. This prototype digitizes 800 MHz on a single ADC rather than 8 channels as proposed in [START_REF] Fmcw/Sfcw Radar | Pandora multifrequency[END_REF], 800 MHz on 2 channels in [START_REF] Paichard | Microwave Camera for Multi-Dimensional Analysis of the RCS of Time-Varying targets[END_REF] or 500 MHz on a single channel in [START_REF]Radar and data communication fusion with UWB-OFDM softwaredefined system[END_REF]. It supports any waveforms unlike [START_REF] Paichard | Microwave Camera for Multi-Dimensional Analysis of the RCS of Time-Varying targets[END_REF] that can only process OFDM in burst mode. In [START_REF]Air Interface -IDROMel[END_REF], the architecture's agility is 7 GHz with 20 MHz bandwidth where this prototype gives 800 MHz instantaneous bandwidth and 1.6GHz agility.

In Figure VI, the trihedral reflector is at the centre of the scene and distant of 27.75 m. It has a radar cross-section of 30 dBsqm thus giving a contrast of 59 dB between the reflector and the clutter. The trihedral reflector allows for reproducible experiments since it is a static target and that the signals will be measured consecutively.

Further details about the experimental setup can be found in [START_REF] Kernec | Case study analysis of linear Chirp and multi-tones radar signals through simulations and measurement with HYCAM-Research Test Bench[END_REF]. The measurements are recorded on a hard disk drive and the data is processed offline using MATLAB.

The selection of appropriate radar architecture (frontend+algorithm) and the design of reproducible experiment constitute the basis to follow the approach for an unbiased study.

In Figure VI, the trihedral reflector is at the centre of the scene and distant of 27.75 m. It has a radar cross-section of 30 dBsqm thus giving a contrast of 59 dB between the reflector and the clutter. The trihedral reflector allows for reproducible experiments since it is a static target and that the signals will be measured consecutively.

Further details about the experimental setup can be found in [START_REF] Kernec | Case study analysis of linear Chirp and multi-tones radar signals through simulations and measurement with HYCAM-Research Test Bench[END_REF]. RCS meas. syst. [START_REF] Paichard | Microwave Camera for Multi-Dimensional Analysis of the RCS of Time-Varying targets[END_REF] SAR imaging and telecom. [START_REF]Radar and data communication fusion with UWB-OFDM softwaredefined system[END_REF] Figure VI: experimental setup

The selection of appropriate radar architecture (frontend+algorithm), the design of reproducible experiment constitute the basis to follow the approach for an unbiased study.

V. EXPERIMENTAL RESULTS: COMPARISON OF RADAR WAVEFORMS

A. Studied Radar waveforms

The radar emits in continuous wave and the waveforms will cover the bandwidths (B) of 1 MHz, 10 MHz, 150 MHz and 800 MHz, and pulse repetition period (T) of 500 ns, 5 µs, 50 µs, 500 µs and 1 ms. Each bandwidth value will be tested with every values of T (the exception being BxT products lower than 75). The IF sampling frequency is 2 GS/s and the IF frequency range is centered on 1.5 GHz, the signal instantaneous bandwidth varies from 1 MHz to 800 MHz.

The studied signals are the P3 phase-coded [2] Multitones and the linear Chirp. The latter is a reference in the radar community and thus is used to evaluate the performances of Multitones.

The waveforms' continuous time equations are shown below in equations 3 and 4 (for Chirp and Multitones, respectively).

( ) = 2 + (3)
( ) = ∑ 2 ( ( + ) + ) (4)
where = ( -1) is the P3 phase code and t belongs to [0;T[, T is the pulse width and the orthogonal period for Multitones, = are the signals' bandwidth, N is an integer and the number of tones, = is the Multitones' frequency step.

= are the signals's starting frequencies. Keeping the orthogonality for Multitones will yield the best result for impulse response. The discrete time equations of both signals Chirp (3) and Multitones (4) are defined in equations ( 5) and ( 6) respectively for a sampling frequency F S and a sampling time t S . First, a condition is set = and M is an integer.

( ) = 2 + (5)
( ) = ∑ 2 ( 1 + ) + (6)
m is the sample number and belongs to [0;M[.

It should be noted that Multitones need to respect constraints at the generation and digitization to avoid intermodulation interference. So Chirp can achieve better linearity with little constraints.

B. Simulations and experimental results on pulse compression

Comparing theory and simulation, the results may differ from the expected value and at first glance, variations in the results might appear inconsistent with theory (Table II). However it should be noted that sampling the IF signal produces a regular spatial speck proportional to the IF sampling frequency. At 2 GS/s, this sampling speck is equal to 0.075 m. The 3 dB main-lobe width and the sidelobes' positions are within 10 % of the expected value for all configurations, except when the speck is large compared to the resolution as for 800 MHz where the error is within 38 %.

The simulation of pulse compression either with a rectangular or a Hamming window yielded results that are coherent with the theoretical values for main-lobe width, sidelobes' positions and amplitudes. The Chirp and Multitones offer the same performances regarding detection capabilities as shown in Table II and the sidelobe's amplitude is -13.27 dB for all cases.

C. Simulations and experimental results on detection range

The difference in detection range capabilities between both waveforms are evaluated based on the Peak-to-Mean Envelope Power Ratio (PMEPR) and the power efficiency (η). The PMEPR results range from 3.01 to 3.2 dB for Chirp and 5.44 to 5.65 dB. As for power efficiency, simulations show a relative error of 2% in favor of Multitones which is negligible. From measurements, the PMEPR results range from 3.2 to 4.22 dB for Chirp and 5 to 6.2 dB for Multitones. The discrepancies are larger in wideband than in narrowband caused by standing waves in the test bench. Concerning power efficiency, the results match simulations.

Using the monostatic radar equation, the results show that using Chirp yields an extended detection range of 13 to 17 % in simulations and 5 to 19% compared to using P3 phase-coded Multitones. The discrepancies are larger in wideband than in narrowband caused by standing waves in the test bench. This shows that Chirp on average yields an extension of 15 % in detection range compared to Multitones.

VI. CONCLUSION

This paper proposed and tested an approach for an unbiased study of radar waveforms' performances. A test-bench was designed and implemented to allow a direct unbiased comparison of simulated and experimental results. The architecture was implemented and has performances comparable to the state of the art in software defined radar prototypes [START_REF]Radar and data communication fusion with UWB-OFDM softwaredefined system[END_REF][10] [11][12].

All signal processing was performed offline using Matlab.

Based on simulations and experimental validations, it was shown that Chirp and P3 phase-coded Multitones have the same performances in range profile detection. However Chirp provides an extra 15 % in detection range compared to Multitones. The measurements (up to 150 MHz bandwidth) matched the simulation results, thereby validating the approach for the implementation of the experimental test-bench for an unbiased study of radar waveforms.

While Multitones incorporates the telecommunication function to the radar, the trade-off of at least 15% loss in detection range (for modulation with the same PMEPR reduction capability as P3 codes). Even though Multitones are not superior to other waveforms for all applications (outside of telecommunications), they outperform other waveforms in a multifunction scenario (such as telecommunications combined with radar applications). As such, Multitones can be thought of as the decathlete of waveforms -not be the best in any individual discipline but the best overall. Therefore Multitones is an optimal waveform for overall performance.

Furthermore new processing capabilities have recently emerged using Multitones (such as Doppler processing while using agility [START_REF] Lellouch | OFDM waveforms for frequency agility and opportunities for Doppler processing[END_REF] and solving Doppler ambiguity [START_REF]Solving Doppler ambiguity by Doppler sensitive pulse compression using multi-carrier waveform[END_REF] which cannot be achieved with Chirp). For long range applications, Chirp is likely to remain the waveform of choice. Multitones is likely to be the waveform of choice for short to mid-range applications -and is very likely to succeed to Chirp in the future.

The outcome of this research showed that the required processing power is greater than what can be provided by the latest FPGA chipsets using state of the art ADC. Based on the proposed equipment and architectures, the required processing power for the parallel architecture is within reach in processing power with the latest Virtex 7 [START_REF][END_REF].

The algorithm implementation on FPGA remains and it is likely that real-time processing will require several chipsets, parallel processing of the quantized signal, some pre-processing schemes and/or decimation to reach this goal. Other technological bottlenecks such as bus communication speed and writing speed for storage will hinder real-time applications. So for now UWB software defined prototypes will have to process the data offline and perform measurements in bursts and store rather than continuous operation.

VII. PERSPECTIVES FOR FUTURE RESEARCH

The architecture examined in this research can be further improved by time-interleaving the test and reference channel; thus reducing the number of components and the required processing power while keeping versatility. In the timeinterleaved architecture switches would shunt the antennas to measure a reference, hence interrupting detection. Furthermore there are added constraints on synchronization for switching operations and stability to limit the frequency of the calibration cycle. The development of new architectures (RF system + algorithms) holds the promise of continuing to reduce the processing power requirement and data throughputs, which are the primary bottlenecks towards real-time processing.

The algorithm proposed in this work is only the first step for the detection, and current trends indicate that real-time algorithms will be implemented on a single-chip. With ever growing data throughputs, the intra-chip interconnections are becoming more and more of an issue that needs to be addressed.

Using multitones for radar applications means observing moving targets, the Doppler will affect the orthogonality and thus performances may vary depending on the phase coding. Hence a trade-off between telecommunications and radar functions will need to be found. The performances of various phase codes need to be investigated. Multifunction scenarios means signal diversity and notched spectra hence performances in such configurations will need to be addressed.

  a) Parallel architecture A synoptic of the parallel architecture is shown in Figure I.

Figure

  Figure I: synoptic of parallel architecture a) Radix-2 FFT algorithm for parallel architecture Figure II describes the Radix-2 FFT algorithm. Two input signals are necessary: the reference signal and the test signal. The reference signal is used to generate the matched filter. It can either be a digital replica or a measured replica of the generated signal. The replica can either be fixed or refreshed at a given frequency.

Figure

  Figure II: Radix-2 FFT algorithm b) DFT algorithm for frequency-interleaved architecture The frequency-interleaved architecture intertwines both reference and test signals into a common signal. The reference signal is shifted in frequency by half the inverse of the pulse repetition period 1/(2T) = Δf/2 = 1 MHz compared to the test signal. The principle of the pulse compression algorithm for frequency-interleaved signals is described in Figure III. Since the frequency step of the signal is now Δf/2. The signal period is doubled. At least 2M (e.g. 2000) samples are necessary for the extraction of both signals. A Hilbert transform Ĥ is applied to the signal. The signal is then downconverted in baseband BB. A DFT is used to move to frequency domain to extract the reference and test signals before realizing the pulse compression. Odd samples go to the test channel vector and even samples go to the reference channel.

Figure

  Figure III: DFT algorithm The comparison in processing power is based on the number of real multiply accumulate operation per seconds (MACS) required to obtain pulse compression in real-time. The required processing powers for the frequency-interleaved, parallel and time-interleaved architectures are respectively given in equations (1) and (2) below. Results are shown in Figure IV.

Figure

  Figure V: prototype

Figures

  Figures VII and VIII depict the pulse compression for Chirp and Multitones on a trihedral reflector 5.2 m further in slant range than shown in Figure V. The distance can be measured at 5.121 m which is coherent with the value measured physically. The error of 0.08 m is acceptable considering the range resolution 0.1875 m and the sampling speck 0.075 m.The relative error on 3 dB mainlobe width, sidelobes' positions and difference in sidelobes' amplitudes between measurements and simulations is shown in TableIII. The large errors for 3 dB mainlobe width and sidelobes positions at 800 MHz are caused by sample speck and perturbations induced by standing wave ratios in the circuit and clutter. Otherwise, the signals from 1 MHz to 150 MHz are within 3.1 % of the expected values, for 3 dB mainlobe width and sidelobe positions, and the difference in sidelobes amplitudes are lower than 0.3 dB. Both waveforms Chirp and Multitones are equivalent on pulse compression in the range profile.

Figure

  Figure VII: measured pulse compression on trihedal reflector -distance 5.2 m -Newman Phase-Coded Multitones (MT) with 800 MHz bandwidth and 5 µs pulse repetition period

Table II :

 II simulated results at 2 GS/s for pulse compression with rectangular window for Chirp and P3 Phase-Coded Multitones

	Bandwidth	1 MHz	10 MHz	150 MHz	800 MHz
	Mainlobe 3dB-width	133 m	13.3 m	0.9 m	0.225 m
	Sidelobes'
	positions	±214.8 m	±21.4 m	±1.425 m	±0.3 m
	DSL1/DSL2

Table III :

 III relative error on 3 dB mainlobe width, sidelobes' positions and difference in sidelobes' amplitudes between measurements and simulations

	Bandwidth	1 MHz	10 MHz	150 MHz	800 MHz
	3 dB Mainlobe width	<1.9 %	<1.8 %	<2.3 %	<37 %
	Sidelobe amplitudes	<0.3 dB	<0.3 dB	<0.3 dB	[-7;3 dB]
	Sidelobe positions	<0.7 %	<1.7 %	< 3.1 %	<67 %

IDROMel [START_REF]Air Interface -IDROMel[END_REF] This work