Amar Prakash Azad

Eitan Altman
email: eitan.altman@sophia.inria.fr

Rachid El-Azouzi
email: rachid.elazouzi@univ-avignon.fr.

Routing Games : From Egoism to Altruism

Keywords: Routing game, altruism, Nash equilibrium, performance analysis, Cooperation Routage de jeu, l'altruisme, l'équilibre de Nash, analyse de performance, de la Coopération

The paper studies the routing in the network shared by several users. Each user seeks to optimize either its own performance or some combination between its own performance and that of other users, by controlling the routing of its given flow demand. We parameterize the degree of cooperation which allows to cover the fully non-cooperative behavior, the fully cooperative behavior, and even more, the fully altruistic behavior, all these as special cases of the parameter's choice. A large part of the work consists in exploring the impact of the degree of cooperation on the equilibrium. Our first finding is to identify multiple Nash equilibria with cooperative behavior that do not occur in the non-cooperative case under the same conditions (cost, demand and topology). We then identify Braess like paradox (in which adding capacity or adding a link to a network results in worse performance to all users) in presence of user's cooperation. We identify another type of paradox in cooperation scenario: when a given user increases its degree of cooperation while other users keep unchanged their degree of cooperation, this may lead to an improvement in performance of that given user. We then pursue the exploration and carry it on to the setting of Mixed equilibrium (i.e. some users are non atomic-they have infinitesimally small demand, and other have finite fixed demand). We finally obtain some theoretical results that show that for low degree of cooperation the equilibrium is unique, confirming the results of our numerical study.

Introduction

Non-cooperative routing has long been studied both in the framework of road-traffic as well as in the framework of telecommunication networks. Such frameworks allow to model the flow configuration that results in networks in which routing decisions are made in a non-cooperative and distributed manner between the users. In the case of a finite (not very large) number of agents, the resulting flow configuration corresponds to the so called Nash equilibrium [START_REF] Basar | Dynamic Noncooperative Game Theory[END_REF] defined as a situation in which no agent has an incentive to deviate unilaterally. The Nash equilibrium has been extensively used in telecommunications, see e.g. [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF][START_REF] Kameda | but does equilibriuma situation of load balancing in distributed computer systems[END_REF]. The authors in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] studied a routing games in which each user has a given amount of flow to ship and has several paths through which he may split that flow. Such a routing game may be handled by models similar to [START_REF] Park | Quality of service provision in noncooperative networks with diverse user requirements[END_REF] in the special case of a topology of parallel links. This type of topology is studied in detail in the first part of [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] as well as in [START_REF] Altman | Equilibria for multiclass routing problems in multiagent networks[END_REF]. However, the model of [START_REF] Park | Quality of service provision in noncooperative networks with diverse user requirements[END_REF] does not extend directly to other topologies. Indeed, in more general topologies, the delay over a path depends on how much traffic is sent by other users on any other path that shares common links. Routing games with general topologies have been studied, for example, in the second part of [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF], as well as in [START_REF] Altman | Equilibria for multiclass routing problems in multiagent networks[END_REF]. A related model was studied thirty years ago by Rosenthal in [START_REF] Rosenthal | A class of games possessing pure strategy nash equilibria[END_REF], yet in a discrete setting. It is shown that in such a model there always exists a pure strategy Nash equilibrium. He introduces a kind of discrete potential function for computing the equilibrium. Nevertheless if a player has more than 1 unit to ship such an equilibrium doesn't always exist.

In this work, we embark on experimental investigation of the impact of cooperation in the context of routing games. In particular we consider parallel links and load balancing network topology for investigation, originally presented in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] and [START_REF] Kameda | Braess-like Paradoxes in Distributed Computer Systems[END_REF] in the context of selfish users. The experimentation is mainly aimed at exploring some strange behaviors which appears in presence of user's partial cooperation (Cooperation in Degree), which is further strengthened with some theoretical results.

Firstly, we identify loss of uniqueness of Nash equilibria. We show by a simple example of parallel links and load balancing network that there may exist several such equilibria. Moreover, even the uniqueness of link utilization at equilibria may fail even in the case of simple topology. A similar example of parallel links, in absence of the cooperation between users there would be a single equilibrium [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF]. Beyond Nash equilibrium we investigate further in the setting of Mixed users i.e. where there are two types of users, Group user and Individual users. Group users seek Nash equilibrium while the Individual users seek equilibrium with Wardrop conditions. Strengthening our earlier finding, we observe loss of uniqueness with partial cooperation against the unique solutions shown in [START_REF] Boulogne | Mixed Equilibrium for Multiclass Routing Games[END_REF] for selfish users. However in the latter section (Sec. 5), we show theoretically that there exist uniqueness of Nash equilibrium under some conditions in the presence of cooperation between users.

Secondly, we identify paradoxical behavior in presence of such cooperation. One of the observed paradox here is a kind of Braess paradox, a well studied paradox in routing context. Braess paradox has attracted attention of many researchers in context of routing games especially related to upgrading the system, see [START_REF] Bean | Braess' paradox in a loss network[END_REF]- [START_REF] Kameda | Braess-like Paradoxes in Distributed Computer Systems[END_REF]. The famous Braess paradox tell us that increasing resources to the system leads to degraded performance in some cases. Such paradox is originally shown to exist in many scenarios, e.g. Braess network in [START_REF] Kameda | How harmful the paradox can be in Braess/Cohen-Kelly-Jeffries networks[END_REF], Load balancing network in [START_REF] Kameda | Braess-like Paradoxes in Distributed Computer Systems[END_REF]. Although such paradoxes are found even in the case of selfish users earlier, their existence even in case of such partial cooperation is highlighted here. We show that as the link capacity increases the overall cost of a user increases i.e. addition of resources in the system can tentatively lead to degraded performance. Even more, we also identify another kind of paradox related to degree of Cooperation: When a user increases its degree of cooperation while other users keep their degree of cooperation unchanged, leads to performance improvement of that user. We also observe similar behavior even when other user also increase their degree of cooperation. Altruism is talked in the context of economics in [START_REF]Handbook of the Economics of Giving, Altruism and Reciprocity[END_REF] as follows: "Motivationally, altruism is the desire to enhance the welfare of others at a net welfare loss to oneself". One may pose the question of whether there is any sense in analyzing altruism in networking context. is there any reason to expect an ISP to take routing decision so as to maximize the utility of other users? We believe that altruistic behaviour can be rewarding for the ISP as it can attract demand. Already in [START_REF] Korilis | Architecting Non cooperative Networks[END_REF] it was shown that if some small amount of flow is controlled by network manager and the latter routes it in some altruistic way then this can enable the manager to impose an efficient equilibrium (One that coincides with the global optimum).

The paper is structured as follows: in section 2, we present the system model, define our framework of cooperative user and, formulate the problem. Further in section 3 we detail the numerical investigation and summarize the findings. Based on one of the findings, we depict more examples identifying Braess paradox in the setting of Nash game in subsection 3.3. In section 4, mixed equilibrium is illustrated. In section 5, we develop theoretical results to show the conditions where uniqueness can be established in presence of users cooperation. In section 6 we summarize the study of impact of cooperation.

System model

We consider a network (V, L), where V is a finite set of nodes and L ⊆ V × V is a set of directed links. For simplicity of notation and without loss of generality, we assume that at most one link exists between each pair of nodes (in each direction). For any link l = (u, v) ∈ L ,define S(l) = u and D(l) = v. Considering a node v ∈ V, let In(v) = {l : D(l) = v} denote the set of its in-going links, and Out(v) = {l : S(l) = v} the set of its out-going links.

A set I = {1, 2, ..., I} of users share the network (V, L), where each source node acts as a user in our frame work. We shall assume that all users ship flow from source node s to a common destination d. Each user i has a throughput demand that is some process with average rate r i . User i splits its demand r i among the paths connecting the source to the destination, so as to optimize some individual performance objective. Let f i l denote the expected flow that user i sends on link l. The user flow configuration f i = (f i l ) l∈L is called a routing strategy of user i. The set of strategies of user i that satisfy the user's demand and preserve its flow at all nodes is called the strategy space of user i and is denoted by F i , that is:

F i = {f i ∈ R |L| ; l∈Out(v) f i l = l∈In(v) f i l + r i v , v ∈ V},
where r i s = r i , r i d = -r i and r i v = 0 for v = s, d. The system flow configuration f = (f 1 , ..., f I ) is called a routing strategy profile and takes values in the product strategy space F = ⊗ i∈I F i . The objective of each user i is to find an admissible routing strategy f i ∈ F i so as to minimize some performance objective, or cost function, J i , that depends upon f i but also upon the routing strategies of other users. Hence J i (f ) is the cost of user i under routing strategy profile f .

Nash equilibrium

Each user in this frame work minimizes his own cost functions which leads to the concept of Nash equilibrium. The minimization problem here depends on the routing decision of other users, i.e., their routing strategy

f -i = (f 1 , ..., f i-1 , f i+1 , ...f I ), Definition 2.1 A vector f i , i = 1, 2, .
.., I is called a Nash equilibrium if for each user i, f i minimizes the cost function given that other users' routing decisions are f j , j = i. In other words,

J i ( f 1 , f 2 , ..., f I ) = min f i ∈F i J i ( f 1 , f 2 , ..., f i , ..., f I ), i = 1, 2, ..., I, (1)
where F i is the routing strategy space of user i.

Nash equilibrium has been discussed in the context of non-cooperative game with selfish users quite often in recent studies.

In this paper we study a new aspect of cooperative routing games where some users cooperate with the system taking into account the performance of other users. We define this degree of Cooperation as follows :

Definition 2.2 Let - → α i = (α i 1 , .., α i |I| )
be the degree of Cooperation for user i. The new operating cost function Ĵi of user i with Degree of Cooperation, is a convex combination of the cost of user from set I,

Ĵi (f ) = k∈I α i k J k (f ); k α i k = 1, i = 1, ...|I|
where Ĵi (f) is a function of system flow configuration f with cooperation.

Based on the degree of Cooperation vector, we can view the following properties for user i,

• Non cooperative user : if α i k = 0, for all k = i.

• Altruistic user : User i is fully cooperative with all users and does not care for his benefits, i.e., α i i = 0.

• Equally cooperative -if α i j = 1 |P| , user i is equally cooperative with each user j, where j ∈ P, P ⊆ I.

Note that Ĵi (f ) is the new effective cost function with degree of Cooperation, where it takes into account the cost of other users. Although a user cooperating with the system, it attempts to minimize its own operating cost function in the game setting. Hence such frame work can be classified under non-cooperative games and the thus we can benefit to apply the methods of non-cooperative games to obtain various quantities e.g. Nash equilibria.

Numerical Investigation of the role of cooperation

In this section we detail some numerical examples to study the routing game in the presence of cooperation between some users. In these examples, we use two types of cost functions : linear function which is often used in the transportation network and M/M/1 function which is used in the queuing networks. We consider two network topologies : parallel links [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] and load balancing networks [START_REF] Kameda | but does equilibriuma situation of load balancing in distributed computer systems[END_REF] which are defined below Load Balancing Network: A simple load balancing topology of network G consists of 3 nodes is depicted in Fig. 1(a). This topology has been widely studied in context of queuing networks. The nodes are numbered 1, 2, 3 and communication links among them are numbered as l 1 , l 2 , l 3 , l 4 . Node 1, 2 acts as source node and node 3 acts as destination node. Link l 1 , l 2 are directed links for nodes 1, 3 and nodes 2, 3 where as, link l 3 , l 4 are directed link for nodes 1, 2 and nodes 2, 1. Cost function of user i is the sum of cost of each link

J i = l∈{1,...4} f i l T l (f l )
, where T l (f l ) is the link cost function. The cost of each user i with cooperation can be defined as below, Parallel Links Network: A simple parallel links topology of network G consists of 2 nodes is depicted in Fig. 1(b) which is originally discuses in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF]. The nodes are numbered 1, 2 and communication links between them are numbered as l 1 , l 2 . Node 1 acts as source node and node 2 acts as destination node. Cost function of user i is the sum of cost of each link

Ĵi = l∈{1,...4} k∈{1,2} α i k f k l T l (f l ) (2) 1 2 3 r 1 r 2 l 3 l 4 l 1 l 2 (a) Load balancing 2 1 l 1 l 2 r 1 r 2 (b) Parallel links
J i = l∈{1,2} f i l T l (f l )
, where T l (f l ) is the link cost function. The cost of each user i with cooperation can be defined as below,

Ĵi = l∈{1,2} k∈{1,2} α i k f k l T l (f l ) (3)
For each network topology, we consider both the cost functions for investigation. Linear Cost Function: Linear link cost function is defined as, T l (f li ) = a i f li + g i for link i = 1, 2, where as, T l (f lj ) = cf lj + d for link j = 3, 4.

M/M/1 Delay Cost Function: The link cost function can be defined as,

T l (f li ) = 1 C l i -f l i
, where C li and f li denote the total capacity and total flow of the link l i . Note that this cost represents the average expected delay in a M/M/1 queue with exponentially distributed inter arrival times and service times under various regimes such as INRIA the FIFO (First In First Out) regime in which customers are served in the order of arrivals, the PS (Processor sharing) regime and the LIFO (Last In First Out) regime. This same cost describes in fact the expected average delays in other settings as well such as the M/G/1 queue (exponentially distributed inter arrival times and general independent service times) under the PS or the LIFO regime.

Numerical Examples

We consider two users share a network. We distinguish two cases. An asymmetric case in which the user 1 is cooperative with α 1 1 > 0 and user 2 is noncooperative, i.e., α 2 2 = 0. The second case is symmetric case in which both users are cooperative with the same degree of cooperation α, i.e. α = α 1 1 = α 2 2 . We compute the Nash equilibrium at sufficiently many points of degree of Cooperation α in the interval [0,1] and plot the corresponding user cost and user flow. Here user flow signifies the fraction of demand flowing in the corresponding user destination link. Since we consider only two links, the fraction of demand flow in one route complements that of the other route. Hence we plot the fraction of demand corresponding to the user i.e. f 1 l1 for user 1 and f 2 l2 for user 2. In sequel we describe five experiments as follows:

Experiment 1) Load balancing network with linear link cost: In Fig. 2(a)-2(b), we plot the cost and the flow obtained at Nash equilibrium versus α in the range [0, 1]. We use the following parameters,

a 1 = a 2 = 1, g 1 = g 2 = 0, c 1 = c 2 = 0.1, d 1 = d 2 = 0.2.
Note that the plot of user 1 and 2 overlap in the figure in symmetrical case. This is due to the same degree of Cooperation.

a 1 = a 2 = 1, g 1 = g 2 = 0, c 1 = c 2 = 0.1, d 1 = d 2 = 0.2., Cooperation : { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.
Experiment 2) Parallel links with linear link cost: In Fig. 3(a),3(b), we plot te cost function and the flow for both users obtained at Nash equilibrium for α in the range of [0, 1]. We use the following parameters,

a 1 = 4, a 2 = 2, g 1 = 1, g 2 = 1, r 1 = 1.2, r 2 = 1.
Experiment 3) Load balancing network with M/M/1 link cost: Consider the parameters for the link cost functions as,

C l1 = 4.1, C l2 = 4.1, C l3 = 5, C l4 = 5, r 1 = 1, r 2 = 1.
In Fig. 4(a),4(b), we plot cost and flow obtained at Nash equilibrium for 0 ≤ α ≤ 1.

Experiment 4) Parallel links with M/M/1 link cost: In Fig. 5(a),5(b), we plot the cost function and the flow for both users obtained at Nash equilibrium versus α. We use the following parameter, C l1 = 0.001, C l2 = 0.001, r 1 = 1, r 2 = 1.

a 1 = 4, a 2 = 2, g 1 = 1, g 2 = 1, r 1 = 1.2, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asym- metrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.
C l1 = 4.1, C l2 = 4.1, C l3 = 5, C l4 = 5, r 1 = 1, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.
C l1 = 0.001, C l2 = 0.001, r 1 = 1, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.
Experiment 5) Load balancing network with linear link cost: We vary the link cost for l 3 and l 4 by varying the parameter c. More precisely, we increase c from 0 to 1000 in the steps of 20 and compute Nash equilibrium at each point. In Fig. 6, we plot the We analyze the results obtained from the experimentation done above. We will be using α = α 1 here for simplicity as we have fixed α 2 = 1 for asymmetrical case and α = α 1 = α 2 for symmetrical case. The important behavior can be summarized under following two headings.

Non uniqueness of Nash equilibrium

In Fig. 2 we observe that there exist multiple Nash equilibria for both symmetrical case and asymmetrical case. Note that multiple Nash equilibria is constrained to some range of cooperation(α). However there also exist some range of cooperation where unique solution exist. We observe that there exist three Nash equilibrium for some range of cooperation, two Nash equilibrium at one point and, unique Nash equilibrium for some range of cooperation. In Fig. 345, we obtain multiple Nash equilibria as above for some range of cooperation. In Fig. 3(a),3(b), 5(a),5(b) although α 1 = α 2 , due to other parameter being non-symmetrical, we do not observe a symmetrical plot for "J 1 , J 2 -Symmetrical". Uniqueness of Nash equilibrium is shown in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF], for a similar situation as in Fig. 2(a),2(b) for selfish user, but we observe loss of uniqueness when users have some cooperation.

Braess like paradox

We also observe a Braess kind of paradox which is related to performance when additional resource is added to the system. To understand this, consider the topology of experiment 1, i.e., the load balancing network topology. Consider a configuration where initially link l 3 and l 4 has very high cost (i.e. effectively doesn't exist) and latter the link cost is reduced to a low value e.g. c = 0 and d = 0.5. This can be interpreted as an additional resources added to the system. Observe than for the initial configuration the cost of user 1 is J 1 = 1 and cost of user 2 is J 2 = 1 in experiment 1. However in the latter configuration which is depicted in Fig. 2(a), we observe the cost of user 1 and 2 is greater that 1 at Nash equilibria. This explains degradation of performance when resources are increased. A very clearer observation can be made in Fig. 6 where the link cost for link l 3 and l 4 is parameterized. Due to multiple Nash equilibria we see two curves. The lower curve corresponds to Nash solutions where flow for each user choose direct link to destination while the upper curve correspond to mixed strategy solution where a fraction of flow for each user choose direct link path. Notice that user cost is improving as the link cost is increasing for the upper curve. Such paradox is widely studied as Braess paradox in many literature. Above we identified the existence of Braess paradox in load balancing network. Now we identify the Braess paradox in parallel links topology. Consider the parameters as follows, C l1 = 4.1 C l2 = 4.1 r 1 = 2 r 2 = 1. Consider the scenario when initially the link l 3 , l 4 does not exist, while latter they are added in the system. In other words, the initially the capacity C 3 = 0, C 4 = 0, and latter it is C 3 = 10, C 4 = 10. Note that when C 3 = 0, C 4 = 0, flow at Nash equilibrium is trivially f l1 = 1, f l2 = 1. In the following, we consider two scenarios of degree of cooperation :

• Only one user is Cooperative : The degree of Cooperation taken in this case is α 1 = 0.93, α 2 = 0. On increasing the capacity C 3 , C 4 from 0 → 10, the cost functions at Nash equilibrium are obtained as J 1 = 0.952 → 2.06, J 2 = 0.3225 → 0.909 and the flows are

f l1 = 2 → 0, f l2 = 1 → 0.0951.
We also obtain another Nash equilibrium where the cost functions and the flow doesn't change from initial state. Note that increasing the capacity in the network degrades the performance at the first Nash equilibrium.

• Both users are Cooperative : We repeat the above experiment with the degree of Cooperation α 1 = 0.9, α 2 = 0.9. The cost functions at Nash equilibrium are obtained as J 1 = 0.952 → 1.247, J 2 = 0.3225 → 0.430. We again obtain another Nash equilibrium where the cost functions and the flow doesn't change from initial state. Note that again increasing the capacity in the network degrades the performance at the first Nash equilibrium.

Paradox in cooperation

In Fig. 2(a), we observe that J 1 has higher cost than J 2 . This is intuitive because user 2 is selfish user while user 1 has a varying degree of Cooperation. In particular remark that α 1 ↓ 0, J 1 ↑ J 2 . But this is not true for the whole range of Cooperation. Observe in Fig. (3.a) a non intuitive behavior for some small range of α 1 (approximately α 1 ∈ (0.87, 1). Notice that when the degree of cooperation α 1 increases (i.e. increase in its altruism) while other user be pure selfish (α 2 = 0), leads to improved cost of user 1. This is a paradoxical behavior, we call it paradox in cooperation. This paradox also exist in case of symmetrical cooperation (see J 1 -Symmetrical, J 2 -Symmetrical ) in the range of α approximately (0, 0.4). Notice that such paradox is still observed in Fig. 34. Remark that such paradox exist only when there are multiple equilibria.

Mixed Equilibrium

The concept of mixed-equilibrium (M.E.) has been introduced by Harker [START_REF] Harker | Multiple equilibrium behaviors on networks[END_REF] (and further applied in [START_REF] Wie | A differential game approach to the dynamic mixed behavior traffic network equilibrium problem[END_REF] to a dynamic equilibrium and in [START_REF] Boulogne | Mixed Equilibrium for Multiclass Routing Games[END_REF] to a specific load balancing problem). Harker has established the existence of the M.E., characterized it through variational inequalities, and gave conditions for its uniqueness. We discuss here the behavior of mixed equilibrium in presence of partial cooperation. Consider the network (V, L) shared by two types of users: (i) group users (denoted by N ) : these users have to route a large amount of jobs; (ii) individual users; these users have a single job to route through the network form a given source to a given destination. There are infinitely many individual users. For simplicity, we assume that all individual users INRIA have a common source s and common destination d. Let P be the set of possible paths which go from s to d.

Cost function

-J i : F → [0, ∞) is the cost function for each user i ∈ N -F p : F → [0, ∞),
is the cost function of path p for each individual user. The aim of each user is to minimize its cost, i.e., for i ∈ N , min f i J i (f ) and for individual user, min p∈P F i p (f ). Let f p be the amount of individual users that choose path p.

Definition 4.1 f ∈ F is a Mixed Equilibrium (M.E.) if ∀i ∈ N , ∀g i s.t.(f -i , g i ) ∈ F, Ĵi (f) ≤ Ĵi (f -i , g i ) ∀p ∈ P, F (p) (f) -A ≥ 0; (F (p) (f) -A)f i (p) = 0
where A = min p∈P F p (f )

Mixed equilibrium in parallel links

In the following proposition, we provide some closed form of Mixed equilibrium in parallel links.

Proposition 1 Consider parallel links network topology (Fig. 1(b)) and M/M/1 delay link cost function. Consider that a Group type user and Individual type users are operating in this network. The mixed equilibrium strategy

(f 1 * l1 , f 2 * l2
) can be given exactly as follows, 1. When Both link is used at Wardrop equilibrium:

       (M 1 , N 1 ) if a 1 < M 1 < b 1 ; otherwise, (0, -cc) if r 1 < min r2+C2-C1, α(C 2 -C 1 )+2αr 2 2α-1 , (r 1 , r 1 -cc) if r 1 < min α(C 2 -C 1 ) 1-2α ,r2-(C2-C1)
, where

M 1 = -α(C 2 -C 1 )+r 1 (2α-1) 2(2α-1) , N 1 = (C 1 -C 2 )(1-α)+(2α-1)r 2 2(2α-1) , a 1 = max(-C 2 -C 1 2 - r 2 -r 1 2 ,0), b 1 = min(-C 2 -C 1 2 + r 1 +r 2 2 ,r1), cc = -C 2 -C 1 2 - r 2 -r 1 2 , dd = -C 2 -C 1 2 + r 2 +r 1 2 ,
2. When only one link ( 1) is used at Wardrop equilibrium:

       (M 2 , 0) if c 1 < M 2 < r 1 ; otherwise, (c 1 , 0) if h(r 1 ) > 0, (r 1 , 0) if h(r 1 ) < 0, where c 1 = max(-C2-C1 2 -r2-r1
2 , 0) and M 2 is the unique (if there exists) root of the quadratic equation

h(x) = ax 2 + bx + c = 0 in [c 1 , r 1 ]. The coefficients of the quadratic equation are a=((C1-C2+r2)(1-α)-αr2); b=(C1(1-α)(2(C2-r2-r1) +2(C2-r2))+2αr2C1); c=C1(1-α)[(C2-r1-r2) 2 -C1(C2-r2)]-αr2C 2 1 .

RR n°7059

When only one link (2) is used by Wardrop user:

       (M 3 , r 2 ) if 0 < M 3 < d 1 ; otherwise, (0, r 2 ) if h(0) > 0, (d 1 , r 2 ) if h(0) < 0, where d 1 = min(-C2-C1 2 + r2+r1
2 , r 1 ) and M 3 is the unique root(if there exist) of the quadratic equation

g(x) = ax 2 + bx + c = 0 in [0, d 1 ]. The coefficients of the quadratic equation are a=((C1-C2+r2)(1-α)-αr2); b=(C1(1-α) (2(C2-r2-r1)+2(C2-r2))+2αr2C1); c=C1(1-α) [(C2-r1-r2) 2 -C1(C2-r2)]-αr2C 2 1 .

Proof:

We first state the general condition for the mixed equilibrium to exist. Based on link uses, there are 3 scenarios when Wardrop conditions can be met for equilibrium to exist. We individually state each of them and then we establish the conditions for equilibria.

For link cost to be finite the link flow must satisfy the flow constraint f l1 < C 1 , f l2 < C 2 . From this we obtain the general condition r 1 +r 2 < C 1 +C 2 . Equilibria can be attained in the following conditions:

1. When both link is used by Wardrop users: Wardrop users utilize both the links, i.e., f 2 l1 > 0, f 2 l2 > 0, implies cost of both links are same, i.e., T l1

(f l1 ) = T l2 (f l2 ) (we use T l1 (f l1 ) instead of F l1 (f l1 ) from def. 4.1). From T l1 (f l1 ) = T l2 (f l2 ) ⇒ f 2 l2 = -cc + f 1 l1 , 0 < f 1 l1 < r 1 , and 0 < f 2 l2 < r 2 imply that a 1 ≤ f 1 * l1 ≤ b 1 , where a 1 = max(cc, 0), b 1 = min(dd, r 1 ), cc = -C2-C1 2 -r2-r1 2 and dd = -C2-C1 2 + r2+r1 2 .
Thus the necessary conditions for equilibrium to exist reduces to r 1 + r 2 > |C 1 -C 2 | by noting cc < r 1 and dd > 0. Thus the equilibrium strategy (f

1 * l1 , f 2 * l2 ) is given by    (M 1 , N 1 ) if a 1 < M 1 < b 1 ; otherwise, (0, -cc) if r 1 < min r2+C2-C1, α(C 2 -C 1 )+2αr 2 2α-1 , (r 1 , r 1 -cc) if r 1 < min α(C 2 -C 1 ) 1-2α ,r2-(C2-C1) ,
where

M 1 = -α(C 2 -C 1 )+r 1 (2α-1) 2(2α-1) , N 1 = (C 1 -C 2 )(1-α)+(2α-1)r 2 2(2α-1) . Note that J 1 (f 1 l1 , f 2 l2 ) is strict convex in the range 0 < f 1 l1 < r 1 , 0 < f 2 * l2 < r 2 ( by definition of M/M/1 cost function). It can be directly inferred that if the equilibrium point (M 1 , N 1 ) satisfies the condition a 1 < M 1 < b 1 , (it
is an interior point) there exist atmost one equilibrium.

Otherwise when there is no interior equilibrium point, there may exist equilibrium at f l 1 1 = 0 or f l 1 1 = r 1 , i.e at point (0, -cc) or at point (r

1 , r 1 -cc) (since T l 1 (f l1 ) = T l 2 (f l2 ) implies f 2 l2 = -cc + f l 1 1
). The point (0, -cc) can be an equilibrium point only when a 1 = max(0, cc) = 0 and J ′1 (0, cc) > 0. This directly implies r 1 < r 2 + (C 2 -C 1 ), and r 1 < α(C2-C1)+2αr2 2α-1 respectively.

Combining these, we get r

1 < min r 2 + (C 2 -C 1 ), α(C2-C1)+2αr2 2α-1
. Following the similar steps we can directly obtain that point (r 1 , r 1cc) can be an

INRIA equilibrium point when r 1 < min α(C2-C1) 1-2α , r 2 -(C 2 -C 1 ) .

When only one link (link 1) is used by Wardrop user:

In this case, Wardrop users utilize only link 1, i.e., f 2 l2 = 0. This directly implies T l1 (f l1 ) ≤ T l2 (f l2 ) ⇒ f 1 l1 ≤ cc (from wardrop condition). Combining the above with positive flow condition 0 ≤ f 1 * l1 ≤ r 1 , we obtain 0 ≤ f 1 * l1 ≤ c 1 , where c 1 = min {cc, r 1 }. Since c 1 must be greater than 0, the necessary condition for equilibrium to exist reduces to

r 1 -r 2 ≥ C 1 -C 2 . Further the equilibrium strategy (f 1 * l1 , f 2 * l2 ) is given by        (M 2 , 0) if 0 < M 2 < c 1 ; otherwise, (0, 0) if h(0) > 0, (c 1 , 0) if h(0) < 0, where M 2 is the unique root of quadratic equation h(x) = ax 2 + bx + c. Let x 1 = -b+ √ D 2a , x 2 = -b- √ D 2a
are the roots of the Quadratic equation h

(x) = 0, where a = (C 1 -C 2 -r 2 )(1 -α) + αr 2 ; b = 2(1 -α)[(C 1 -r 2 )(2(C 2 -r 2 ) + r 1 )] + 2αr 2 (C 2 -r 1 ); c = (1 -α)(C 1 -r 2 )[(C 2 -r 1 ) 2 -(C 2 -r 1 )(C 1 - r 2 ) -r 1 (C 1 -r 2 )] + αr 2 (C 2 -r 1 ) 2 ; D = b 2 -4ac. The quadratic equation h(x) = 0 will have unique solution in the range 0 < f 1 l1 < r 1 because J ′1 (f 1 1 , 0) is strict convex in the range 0 < f 1 l1 < r 1
( by definition of M/M/1 cost function). Hence there can be atmost one equilibrium point satisfying 0 < M 2 < c 1 (i.e single interior point).

Otherwise when there is no interior equilibrium point, there may exist equilibrium at f l 1 1 = 0 or f l 1 1 = r 1 , i.e., at point (0, 0) or at point (r 1 , 0). The point (0, 0) can be an equilibrium point only when J ′1 (0, 0) > 0, i.e., h(0) > 0.

Similarly point (c 1 , 0) can be equilibrium point only when J ′1 (0, 0) < 0, i.e., h(0) < 0.

When only one link (2) is used by Wardrop user:

In this case Wardrop users utilize only link 2, i.e., f 2 l2 = r 2 . Following the similar steps as before, we obtain d 1 ≤ f 1 * l1 ≤ r 1 , where d 1 = max {dd, 0}. Since d 1 must be less than r 1 , the necessary condition for equilibrium to exist reduces to

r 1 -r 2 ≤ C 2 -C 1 .
Further the equilibrium strategy (f 1 * l1 , f 2 * l2 ) is given by

       (M 3 , r 2 ) if d 1 < M 3 < r 1 ; otherwise (0, r 2 ) if h(r 2 ) > 0, (d 1 , r 2 )
if h(r 2 ) < 0, where M 3 is the unique root(if there exist) of the quadratic equation g

(x) = ax 2 + bx + c in d 1 < f 1 l1 < r 1 . Let x 1 = -b+ √ D 2a , x 2 = -b- √ D 2a
are the roots of the Quadratic equation g(x) = 0, where a = ((

C 1 -C 2 +r 2 )(1-α)-αr 2 ); b = (1 -α)[4C 1 (C 2 -r 1 -r 2 ) + 2r 1 C 1 ] -2αr 2 C 1 ); c = (1 -α)[(C 2 -r 1 -r 2 + C 1 )C 1 (C 2 -r 2 -r 1 ) -r 1 C 2 1 ] + αr 2 C 2 1 ; D = b 2 -4ac.
The quadratic equation g(x) = 0 will have unique solution in the range 0 < f 1 l1 < r 1 because J ′1 (f 1 1 , r 2 ) is strict convex in the range 0 < f 1 l1 < r 1 ( by definition of M/M/1 cost function). Hence there can be atmost one equilibrium point satisfying d 1 < M 3 < r 1 (i.e single interior point).

Otherwise when there is no interior equilibrium point, there may exist equilibrium at f l 1 1 = 0 or f l 1 1 = r 1 , i.e., at point (0, r 2 ) or at point (r 1 , r 2 ). The point (0, r 2 ) can be an equilibrium point only when J ′1 (0, r 2 ) > 0, i.e., g(r 2 ) > 0. Similarly point (r 1 , r 2 ) can be equilibrium point only when J ′1 (0, r 2 ) < 0, i.e., g(r 2 ) < 0.

Corollary 1 Consider the symmetric parallel links, i.e., (C 1 = C 2 = C, r 1 = r 2 = r) network with M/M/1 delay link cost function. In a mixed user setting the mixed equilibrium strategy ((f 1 * l1 , f 2 * l2 )) can be given by

   ( r 2 , r 2 ) when r 1 > f 1 l1 > 0, r 2 > f 2 l2 > 0 (0, 0) when 0 ≤ f 1 l1 ≤ r 1 , f 2 l2 = 0, if α ≥ 0.5 (r, r) when 0 ≤ f 1 l1 ≤ r 1 , f 2 l1 = 0, if α ≥ 0.5

Proof:

Consider the symmetric case when

C 1 = C 2 = C, r 1 = r 2 = r.
The general condition thus reduces to r < C from prop. 1. Equilibrium can be attained under the following scenario based on link uses.

When both link is used by Wardrop users:

Wardrop users utilizes both the links, i.e., f 2 l1 > 0, f 2 l2 > 0, implies cost function of both the links are same, i.e., T l1

(f l1 ) = T l2 (f l2 ). From T l1 (f l1 ) = T l2 (f l2 ) ⇒ f 2 l2 = f 1 l1 , 0 < f 1 l1
< r, and 0 < f 2 l2 < r, implies that necessary condition for equilibrium to exist are always satisfied. Further the equilibrium strategy (f 1 * l1 , f 2 * l2 ) is given by ( r 2 , r 2 ) which can be directly obtained from prop. (1.1).

When only one link (link 1) is used by Wardrop user:

In this case, Wardrop users utilize only link 1, i.e., f 2 l2 = 0. This directly implies T l1 (f l1 ) ≤ T l2 (f l2 ) ⇒ f 1 l1 ≤ 0 (from wardrop condition). Combining the above with positive flow condition 0 ≤ f 1 * l1 ≤ r 1 , we obtain f 1 * l1 = 0. This suggests that equilibrium point can be given by (f 1 * l1 , f 2 * l2 ) = (0, 0) if there exist. Note that (0, 0) is the boundary point solution. If J ′1 (0, 0) ≥ 0 (Nash solution of user 1) then the equilibrium point is given by (0, 0). J 1 ′ (f 1 l1 , 0) can be expressed as P (x) Q(x) , where

P (x) = ax 2 + bx + c, a = r(2α-1); b = 2(C-r)(2(C-r)(1-α)+r); c = (2α-1)r(C-r) 2 ; D = 16(C -r) 2 (1 -α)C[(C -r)(1 -α) + αr] and Q(x) > 0 for all x, thence J ′1 (0, 0) ≥ 0 ⇒ c ≥ 0 ⇔ α ≥ 0.5.

When only one link (2) is used by Wardrop user:

In this case, Wardrop users utilize only link 2, i.e., f 2 l2 = r. This directly implies T l1 (f l1 ) ≥ T l2 (f l2 ) ⇒ f 1 l1 ≥ r (from Wardrop condition). Combining the above with positive flow condition 0 ≤ f 1 * l1 ≤ r 1 , we obtain f 1 * l1 = r. This suggests that equilibrium point can be given by (f 1 * l1 , f 2 * l2 ) = (r, r) if there exist. Remark that this case is symmetrical to case when only link 1 is used. Hence we can directly infer the condition for equilibrium point to exist. The equilibrium point point (r, r) exist, when α ≥ 0.5. In Fig. [START_REF] Kameda | How harmful the paradox can be in Braess/Cohen-Kelly-Jeffries networks[END_REF], we depict the mixed equilibrium strategy(flow) for the varying degree of cooperation(α). Observe the loss of uniqueness of mixed equilibrium in presence of partial cooperation. It is known to have unique equilibrium in the network setting with finitely many selfish users [START_REF] Boulogne | Mixed Equilibrium for Multiclass Routing Games[END_REF]. Remark that we have already shown in the previous section that there exist multiple Nash equilibria in presence of partial cooperation. Due to space limitation we illustrate this behavior with only parallel links topology and M/M/1 cost function. However we identify a similar remark from other configuration also.

Existence and uniqueness of Equilibrium

Having noted the existence of multiple Nash equilibrium in sec.3.1 using various examples, we here establish the conditions under which unique nash equilibrium exist. Uniqueness of Nash equilibrium is shown in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] in case of non-cooperative games for parallel links topology. Under some condition, uniqueness is shown for general topology also. In this section we follow the similar structure to establish the uniqueness for parallel links topology in case of our setting of user cooperation.

We follow some assumptions on the cost function J i same as in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF].

Assumption 5.1 : G1: J i (f ) = l∈L Ĵi l (f l )). Each Ĵi l satisfies: G2: J i l :[0, ∞) → (0, ∞] is continuous function. G3: J i l : is convex in f j l for j = 1, ...|I|. G4: Wherever finite, J i l is continuously differentiable in f i l , denote K i l = δ Ĵi l δf i l .
Note the inclusion of +∞ in the range of Ĵi l , which is useful to incorporate implicitly and compactly and additional constraints such as link capacities. Also note that the assumption G3 is stronger than in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF].

Function that comply NEP is with the function which comply with the type G function.

We shall mainly consider cost functions that comply with the following assumptions:

Assumption 5.2 : B1: J i (f ) = l∈L f i l T l (f l )) B2: T l : [0, ∞) → (0, ∞]. B3: T l (f l ) is positive, strictly increasing and convex. B4: T l (f l ) is continuously differentiable.
Functions that comply with these assumptions are referred to as type-B functions.

Remark 5.1 In Assumption B1, T l (f l ) is the cost per unit of flow (for example mean delay) on the link l, for the total utilization, f l = i∈I f i l , of that link. Note that if T l (f l ) is the average delay on link l, it depends only on the total flow on that link. The average delay should be interpreted as a general congestion cost per unit of flow, which encapsulates the dependence of the quality of service provided by a finite capacity resource on the total load f l offered to it.

A special kind of type-B cost function is that which corresponds to an M/M/1 link model. In other words, suppose that C1: Ĵi (f i l , f l ) = f i l Ṫl (f l ) is a type-B cost function. C2:

T l = 1 C l -f l f l < C l ∞ f l > C l .
Where C l is the capacity of the link l. Function that comply with these requirements are referred to as type-C functions. Such delay functions are broadly used in modeling the behavior of the links in computer communication networks [START_REF] Bertsekas | Data Networks[END_REF], [START_REF] Kleinrock | Queueing Systems[END_REF].

Parallel links network topology

In this section we study the special case where the users from set I shares a set of parallel communication links L = {1, 2....L} interconnecting a common source node to a common destination node. In [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF], uniqueness of Nash equilibrium is shown for the selfish users (when user do not cooperate in managing the communication link) in parallel links, where the cost functions (J i (f )) of users are assumed to hold assumption 5.2. However this is not true when the users have cooperation in degree as defined in sec.(2.2). We observe that assumption 5.2 is not sufficient to guarantee unique Nash equilibrium in our setting. It is a harder problem to characterize system behavior for general degree of cooperation. Hence we consider a special case of cooperation where a user cooperative with similar cooperation with all other users i.e.

Ĵi (f) = (1 -α i )J i (f) + α i k J k (f)
Consider the cost function of type 5.2. The cost function of each user on link l is given by

Ĵi l (f ) = ((1 -α i )f i l + α i f -i l )T l (f l ) = ((1 -α i )f l + (1 -2α i )f -i l )T l (f l )
INRIA is aimed users take only their performance but also other's performance. We have parameterized the degree of Cooperation to capture the user behavior from altruistic to ego-centric regime. We notice some strange behaviors. Firstly we show the existence of multiple Nash equilibria by a simple example of parallel links and load balancing networks in contrast to the unique Nash equilibrium in case of selfish users. Moreover, we then explored the mixed user scenario, which is composed of a finite number of Group type user seeking Nash equilibrium and infinitely many Individual type users satisfying Wardrop condition. We illustrate loss of uniqueness of equilibrium even in mixed users scenario in presence of partial cooperation by an example for parallel links network. However it is known to have unique equilibrium in presence of only finitely many selfish users in similar settings.

Secondly we identify two kinds of paradoxical behavior. We identify situation where well known Braess paradox occurs in our setting of cooperation. We show using an example of parallel links network with M/M/1 link cost that addition of system resources indeed degrades the performance of all users in presence of some cooperation, while it is well known that this is not true for this setting with only selfish users.

We also identify another type of paradox, paradox in cooperation: i.e. when a given user increases its degree of cooperation while other users keep unchanged their degree of cooperation, this may lead to an improvement in performance of that given user. In extreme sense a user can benefit itself by adopting altruistic nature instead of selfishness.

INRIA

Figure 1 :

 1 Figure 1: Network Topology

Figure 2 :

 2 Figure 2: Topology : Load balancing, Cost function : Linear, Parameters :a 1 = a 2 = 1, g 1 = g 2 = 0, c 1 = c 2 = 0.1, d 1 = d 2 = 0.2., Cooperation : { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.

  Flow values at Nash equilibrium

Figure 3 :

 3 Figure 3: Topology : Parallel links, Cost function : Linear, Parameters :a 1 = 4, a 2 = 2, g 1 = 1, g 2 = 1, r 1 = 1.2, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.

  Flow values at Nash equilibrium

Figure 4 :

 4 Figure 4: Topology : Load balancing, Cost function : M/M/1 Delay, Parameters : C l1 = 4.1, C l2 = 4.1, C l3 = 5, C l4 = 5, r 1 = 1, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.

Figure 5 :

 5 Figure 5: Topology : Parallel links, Cost function : M/M/1 Delay, Parameters :C l1 = 0.001, C l2 = 0.001, r 1 = 1, r 2 = 1, Cooperation: { Symmetrical: α 1 = α 2 , Asymmetrical: 0 ≤ α 1 ≤ 1, α 2 = 0}.

Figure 6 :

 6 Figure 6: Topology : Load balancing, Cost function : Linear, Parameters : a 1 = 4.1, a 2 = 4.1, d = 0.5, Cooperation:α 1 = α 2 = 0.93 .

Figure 7 :

 7 Figure 7: Parallel links, M/M/1 delay cost at C l1 = 4, C l2 = 3, r 1 = 1.2, r 2 = 1.

RR n°7059

l and f l . Uniqueness of Nash equilibrium can be also observed in case of All-positive flow in each link. By All-positive flow we mean that each user have strictly positive flow on each link of the network.

The following result establishes the uniqueness of Nash Equilibrium in case of positive flow.

Theorem 5.1 Consider the cost function of type 5.2. Let f and f be two Nash equilibria such that there exists a set of links L 1 such that {f i l > 0 and f i l > 0, i ∈ I} for l ∈ L 1 , and

Proof: Let f ∈ F and f ∈ F be two NEP's. As observed f and f satisfy the Kuhn-Tucker condition. We rewrite the Kuhn-Tucker condition in terms of f -i l , f l as below,

The above relation and the fact that K i l (.; .) is increasing in both of is argument will be used below to establish that f = f i.e. f i l = f i l for every l, i. The first step is to establish that f l = fl for each link l. To this end, we prove that for each l and i, the following relation holds:

We shall prove (4), since (5) is symmetric. Assume that λi ≤ λ and fl ≥ f l for some l and i. For f i l > 0 together with our assumptions imply that:

where the last inequality follows from the monotonicity of K i l in its second argument. Now , since K i l is nondecreasing in its first argument, this implies that f -i l ≤ f i l , and (4) is established.

Let

From (4), we know that , f -i l ≤ f -i l for l ∈ L 1 and i / ∈ I a , it follows that :

This inequality obviously By symmetry, that the set {l : fl < f l } is also empty. Thus, it has been established that:

We now show that λi = λ i for each user i. To this end, note that (4) may be strengthen as follows:

> 0 for at least one link l and from (8) implies that, l∈L f i l > l∈L f i l = r i , which contradicts the demand constraint for user i. We, therefore, conclude that λi < λ i does not hold for any user i. A symmetric argument may be used to show that λi = λ i for every user i ∈ I. Combined with [START_REF] Kameda | How harmful the paradox can be in Braess/Cohen-Kelly-Jeffries networks[END_REF], this implies by ( 4) and ( 5) that

Uniqueness of NEP in general topology

It is a hard to characterize system behavior for general network with user's partial cooperation. For selfish users, it is shown that there exist uniqueness for Nash equilibrium point(NEP) under Diagonal Strict Convexity in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF]. We consider a special case of cooperation where a user cooperates equally with all other users i.e.

Consider the cost function of type 5.2. The cost function of each user on link l can be thus given by

Theorem 5.2 Consider the cost function of type 5.2. Let f and f be two Nash equilibria such that there exists a set of links L 1 such that {f i l > 0 and f i l , i ∈ I} for l ∈ L 1 , and {f i l = f i l = 0, i ∈ I} for l ∈ L 1 . Then f = f . Under all positive flows assumption, the Kuhn-Tuker conditions for all l = (u, v) ∈ L ∞ becomes

Summing each of these equations over i, we obtain H uv (f l ) := (αI + 1 -2α)T ′ l (f l ) + I(1α)T l (f l ) = λ uλ v H uv ( fl ) := (αI + 1 -2α) fl T ′ l ( fl ) + (1α)IT l ( fl ) = λuλ v Since the function H is strictly increasing, we follow the same proof of Theorem 3.3 in [START_REF] Orda | Competitive Routing in Multiuser Communication Networks[END_REF] to conclude that f = f . INRIA


Cédric Berbra

Sylviane Gentil

Suzanne Lesecq
email: suzanne.lesecq@cea.fr

Identification of Multiple faults in an Inertial Measurement Unit

Keywords: Fault diagnosis, fault detection, fault isolation, fault identification, multiple faults, optimization, Inertial Measurement Unit

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

Identification of Multiple faults in an

Inertial Measurement Unit C. Berbra * S. Gentil * S.Lesecq * *

INTRODUCTION

This paper deals with the diagnostic design of an Inertial Measurement Unit (IMU). An IMU is an electronic device that measures and reports on a vehicle velocity, orientation, and gravitational forces, using a combination of accelerometers, magnetometers and rate-gyros. An IMU senses the current rate of acceleration using one or more accelerometers, and detects changes in rotational attributes such as pitch, roll and yaw angles using one or more rate-gyros and magnetometers. The data collected from the IMU sensors allows a computer to track a rigid body position and attitude (orientation). IMUs are typically used to maneuver aircrafts, including Unmanned Aerial Vehicles (UAVs), among many others, and spacecrafts, including shuttles, satellites and landers. Besides navigational purposes, low-cost IMUs are also used nowadays as orientation sensors in the field of human motion. They are for instance frequently used for sports technology, patient or senior monitoring, capture technology and animation. Nevertheless, they are not very robust and can present many kinds of faults. It is thus interesting to develop Fault Detection and Isolation (FDI) for IMUs together with Fault Tolerant Control (FTC) for systems that embed IMUs.

GIPSA-lab has developed a quadrotor as a test-bench for advanced control and diagnostic techniques. A quadrotor is an UAV with four rotors, each motor driving a blade. This quadrotor is equipped with an IMU. From its measurements, the attitude of the quadrotor is computed and then used in a state observer and a control loop [START_REF] Guerrero-Castellanos | Bounded attitude stabilization: Real-Time application on four-rotor helicopter[END_REF], [START_REF] Guerrero-Castellanos | A low-cost air data attitude heading reference system for the tourism airplane applications[END_REF]). UAV diagnosis has also been intensely stud-ied during the last few years. For instance, FDI techniques have been applied to autonomous aircrafts [START_REF] Simani | Application of Fault Diagnosis methodologies to a general aviation aircraft[END_REF]) [START_REF] Bonfe | Active Fault Tolerant Control Scheme for a General Aviation Aircraft Model[END_REF]), or to small autonomous helicopters [START_REF] Heredia | Sensor and actuator fault detection in small autonomous helicopter[END_REF]). In [START_REF] Henry | From fault diagnosis to recovery actions for aeronautic and aerospace missions: a model-based point of view[END_REF], [START_REF] Issury | Multiple and simultaneous fault isolation with minimal fault indicating signals: a case study[END_REF], [START_REF] Patton | A Monte Carlo analysis and design for FDI of a satellite control system[END_REF]), FDI techniques are applied in aeronautics and aerospace areas. Our team has also proposed some solutions to the diagnostic problem of UAV [START_REF] Tanwani | Experimental networked embedded minidrone-part II. Distributed FDI[END_REF], Berbra et al. (2008a)), being aware that the most important quadrotor component likely to fail is the IMU. FTC solutions have also been proposed [START_REF] Berbra | A Multi-Observer Switching Strategy for Fault-Tolerant Control of a Quadrotor Helicopter[END_REF]).

Diagnosis includes fault detection and isolation (FDI) but another important point is fault identification. Fault identification consists in estimating the fault amplitude and its temporal behavior, which is helpfull for the FTC of a system. In our previous works [START_REF] Tanwani | Experimental networked embedded minidrone-part II. Distributed FDI[END_REF], Berbra et al. (2008a)), a bank of observers has been used to design structured residuals based on the quadrotor state estimation. The major difficulty in the solutions proposed in the latter papers is that the diagnostic algorithm is sensitive to the quadrotor model uncertainty or to disturbances on the quadrotor. Moreover, fault identification and multiple fault detection is not possible. These drawbacks constituted the motivation of the work presented in the present paper.

The simulation results have been obtained with Matlab/Simulink to simulate the quadrotor model, its control, observation and diagnosis. In order to postpone real experiments until everything has been carefully checked, an effcient way to simulate a system whose safety is critical is a hardware-in-the-loop approach. Such an experiment has been conducted for the quadrotor [START_REF] Berbra | Hardware in the loop networked control and diagnosis of a quadrotor drone[END_REF]).

This paper is organized as follow: section 2 briefly presents the Inertial Measurement Unit model. Section 3 describes the diagnostic algorithm that has been developed for the IMU and that is completely independent of the experiment. The residual generation is fully described and some simulation results are discussed. Section 4 concludes this paper.

DESCRIPTION OF THE INERTIAL MEASUREMENT UNIT

2.1 Description of a rigid body orientation

Fig. 1. Definition of the coordinate frames

To depict the orientation of a rigid body subject to movements, two frames are considered (see Fig. 1): the inertial frame R(e x , e y , e z ) and the body frame B(e 1 , e 2 , e 3 ). The inertial frame is attached to the earth and a classical choice is the NED frame (North, East, Down). The body frame is attached to the structure with its origin at the centre of mass of the body.

In the following paragraphs, the focus is done on orientation, also named attitude. Orientation can be expressed by three angles yaw-pitch-roll (φ, θ, ψ) or by a unitary quaternion q ∈ 4 (Chou (1992))

q = [q 0 - → q T ] T , q 2 = 1 (1)
The advantage of using q for the attitude representation is to avoid singularities that appear with classical angular representations (Euler angles or Cardan angles). Moreover, q is an elegant and efficient attitude representation from a computational point of view, which is of great importance for embedded systems. The quaternion representation is chosen in the present paper to perform computations. However, the simulation results will be presented in the roll-pitch-yaw formulation because it is more intuitive and thus easier to interpret the curves.

A coordinate change from -→ r in the reference frame to -→ c in the body frame is expressed with

c = q -1 ⊗ r ⊗ q = q ⊗ r ⊗ q (2) where r = [0 - → r T ] T , c = [0 - → c T ] T . q = [q 0 -- → q T ]
is the conjugate of q and ⊗ is the quaternion multiplication.

Moreover, the coordinate change can be represented with matrix C(q) that is expressed as

C(q) = (q 2 0 -- → q T - → q )I + 2( - → q - → q T -q 0 [q × ]) (3) - → c = C(q) - → r (4) with [q × ] = 0 -q 3 q 2 q 3 0 -q 1 -q 2 q 1 0 (5)

Inertial Measurement Unit (IMU) modeling

The estimation of attitude (or orientation) and of rotational speed of a rigid body (the quadrotor for example) is a pre-requisite for its attitude control. An IMU can be embedded in the system in order to provide measurements that will be fused to estimate the attitude. The IMU consists of a tri-axis accelerometer (a 1 , a 2 , a 3 ), a tri-axis magnetometer (m 1 , m 2 , m 3 ) and three rate gyros (g 1 , g 2 , g 3 ) mounted at right angles.

Rate Gyro modeling

The angular velocity ω is measured in the body frame B with the three rate gyros. The measurements delivered by these sensors are affected by noise. Theoretically, the integral of ω could give the relative orientation but the presence of noise generates errors that are accumulated over time. As a consequence, state observers are prefered. The sensor measurements are modeled as

ω g = ω + η gyro (6)
where ω g ∈ 3 are the sensor readings, ω ∈ 3 represents the system angular velocity and η gyro is assumed to be a zero-mean white noise of appropriate dimension. Note that η gyro = 0.01 rad/s.

Accelerometer modeling The 3-axis accelerometer senses the inertial forces and gravity in B. The transformation of accelerometer measurements from inertial frame R to body frame B is computed as follows

b acc = C(q)( v -g) + η acc (7)
where b acc ∈ 3 corresponds to the measurements in B, and η acc is a zero-mean white noise of appropriate dimension. The motion is supposed quasi-static so that linear accelerations v are neglected (i.e. v g ). In this way, accelerometers are only sensitive to the gravitational field g. Note that measurements are normalized. Therefore g = [0 0 1] T . Note that η acc = 0.002 m/s 2 .

Magnetometer modeling

The information provided by the tri-axis magnetometer is added to the inertial measurements. The magnetic field is sensed in

B. It is defined by b mag = C(q)h m + η mag (8)
where h m = [h mx 0 h mz ] T and b mag ∈ 3 are the magnetic field in R and B, respectively. For the experimentation,

h m = [ 1 2 0 √ 3 2 ] T .
Note that η mag = 0.0007 mgauss. Remark Note that the accelerometer and magnetometer measurements are modeled by static non linear equations ( 7)-( 8) that depend on constant vectors g and h m and on matrix C(q) which is a non-linear function of q.

Quadrotor control-loop

The diagnostic technique proposed in this paper is exemplified on a quadrotor that is under development at GIPSA-Lab. For this system, a non linear attitude observer has been designed [START_REF] Guerrero-Castellanos | A low-cost air data attitude heading reference system for the tourism airplane applications[END_REF]). The quaternion estimation q est is used in a feedback loop. The attitude reference is given by a quaternion reference (see Fig. 2). The controller implemented for the troduced in a x . This sensor fault is equivalent to 50%. Fig.

shows the real attitude of the quadrotor when the sensor ult is not detected. As can be seen, the quadrotor crashed. erefore, it is obvious that FDI must be implemented. It is a fety issue. In sections III and IV, two different FDI methods r the IMU are presented. implemented here. The attitude is represen quaternion for computation convenience, th bian being linear in the unknown q. Moreo optimization can be performed with "clas constraints) tools when the quaternion is Generalized Rodrigues Parameters. The magnetometer measurements satisfy the n ( 9)-( 10). The detection procedure is perfor Firstly, the attitude ( q) i , i = 1 : 6, is estim measurements (measurement i discarded, s solution of a non linear optimization probl q = 1. Then, qi , together with the model (10) provides the measurement estimates th troduced in a x . This sensor fault is equivalent to 50%. Fig.

I FAULT SIGNATURE TABLE f a x f a y f a z f m x R 1 [100000] [111111] [111111] [111111] R 2 [111111] [010000] [111111] [111111] R 3 [111111] [111111] [001000] [111111] R 4 [111111] [111111] [111111] [000100] R 5 [111111] [111111] [111111] [111111]
shows the real attitude of the quadrotor when the sensor ult is not detected. As can be seen, the quadrotor crashed. herefore, it is obvious that FDI must be implemented. It is a fety issue. In sections III and IV, two different FDI methods r the IMU are presented. . Inertial Measurement Unit (IMU) model The attitude and the quadrotor rotational speed are a prequisite for attitude control. An IMU is embedded in the uadrotor in order to provide measurements that will be sed to estimate the attitude. The IMU consists of a triaxis ccelerometer (a x , a y , a z ), a triaxis magnetometer (m x , m y , m z ) nd three rate gyros (g x , g y , g z ) mounted at right angle. Their implemented here. The attitude is represen quaternion for computation convenience, th bian being linear in the unknown q. Moreo optimization can be performed with "class constraints) tools when the quaternion is p Generalized Rodrigues Parameters. The magnetometer measurements satisfy the no ( 9)-( 10). The detection procedure is perform Firstly, the attitude ( q) i , i = 1 : 6, is estima measurements (measurement i discarded, s solution of a non linear optimization probl q = 1. Then, qi , together with the model Fig. 4. Real attitude with a failure in a 1 at time t = 5 s Fig. 4 shows the real attitude of the quadrotor when a bias of 0.5 is introduced in a 1 at time t = 5 s (additive fault). When the sensor fault is not detected, quadrotor crashes. Therefore, it is obvious that FDI must be implemented for safety issue.

f a x f a y f a z f m x R 1 [100000] [111111] [111111] [111111] R 2 [111111] [010000] [111111] [111111] R 3 [111111] [111111] [001000] [111111] R 4 [111111] [111111] [111111] [000100]

DIAGNOSIS

To perform the diagnosis of the IMU, a bank of estimators/observators is implemented [START_REF] Isermann | Fault-Diagnosis Systems: An Introduction from Fault Detection to Fault Tolerance[END_REF]), [START_REF] Chen | Robust Model-Based Fault Diagnosis for Dynamic Systems[END_REF]). Note that the technique proposed here is totally independent of the system in which the IMU is embedded. The residual generator is decomposed into two parts:

• Procedure 1: generation of the residuals that detect the accelerometer and magnetometer sensor faults. In this case, the rate gyro measurements are not used; • Procedure 2: generation of the residuals that detect the rate-gyro sensor faults. In this case, the result obtained by the previous FDI algorithm for accelerometer and magnetometer faults is used to perform this diagnosis.

3.1 Procedure 1: accelerometers and magnetometers Fig. 5 shows the structure of the procedure implemented here. The accelerometer and magnetometer measurements satisfy the set of six non-linear equations ( 7)-( 8). The residuals are generated as follow:

(1) the attitude qi , i = 1 : 6, is estimated from 5 over 6 measurements, where i corresponds to the measurement discarded (see Fig. 5). Therefore, qi is the solution of a non linear optimization problem with constraint q = 1 (Berbra et al. ( 2008a)) or [START_REF] Tanwani | Experimental networked embedded minidrone-part II. Distributed FDI[END_REF]); (2) with qi , the measurements are estimated with the measurement model ( 7)-( 8); (3) the residual vector R i ∈ 6 is computed in a classical way (difference between measurements and their estimates).

troduced in a x . This sensor fault is equivalent to 50%. Fig.

shows the real attitude of the quadrotor when the sensor ult is not detected. As can be seen, the quadrotor crashed. erefore, it is obvious that FDI must be implemented. It is a fety issue. In sections III and IV, two different FDI methods r the IMU are presented.

Inertial Measurement Unit (IMU) model

The attitude and the quadrotor rotational speed are a prequisite for attitude control. An IMU is embedded in the adrotor in order to provide measurements that will be sed to estimate the attitude. The IMU consists of a triaxis celerometer (a x , a y , a z ), a triaxis magnetometer (m x , m y , m z ) d three rate gyros (g x , g y , g z ) mounted at right angle. Their odels are given by

ω g = ω + η 1 (8) b acc = C(q)( v -g) + η acc (9) b mag = C(q)h m + η mag ( 10
)
η i , i = {1, acc, mag} are assumed to be Gaussian zeroean independent white noises. The motion is supposed quasi- implemented here. The attitude is represented with a unitary quaternion for computation convenience, the underlying Jacobian being linear in the unknown q. Moreover, the non-linear optimization can be performed with "classical" (i.e. without constraints) tools when the quaternion is parameterized with Generalized Rodrigues Parameters. The accelerometer and magnetometer measurements satisfy the non-linear equations ( 9)-( 10). The detection procedure is performed in three steps. Firstly, the attitude ( q) i , i = 1 : 6, is estimated from 5 over 6 measurements (measurement i discarded, see Fig. 5). qi is the solution of a non linear optimization problem with constraint q = 1. Then, qi , together with the model measurements ( 9)-( 10) provides the measurement estimates that are insensitive to the discarded measurement. Lastly, the residual vector R i ∈ ℜ 6 is computed in a classical way. Note that this residual is sensitive to faults in all the sensors but the discarded one. The fault signature table is given in Table I.

R i , i = 1 : 6, is the set of residuals obtained without a x , a y , a z , m x , m y , m z respectively. In column, faults in the var- Note that R i is sensitive to faults in all the sensors used to compute qi . Thus R i is insensitive to faults in sensor i.

The fault signature table is given in Table 1. R i , i = 1 : 6, is the set of vectorial residuals obtained when qi is estimated without a 1 , a 2 , a 3 , m 1 , m 2 , m 3 respectively. The columns of Table 1 represent the faults in the six sensors.

[111111] means that the residual elements are computed with a faulty sensor (i.e. the faulty sensor is in the set of sensors used to estimate qi ).

[100000] corresponds to residual elements computed without the faulty sensor. Therefore, the faulty sensor can be isolated.

Consider a fault in a 1 identical to the one in section (2.3).

For the sake of place, only two over six residual vectors are presented. Fig. 6 shows R 1 computed without sensor a 1 . As expected, only the first element in R 1 is sensitive to the fault (see the first column in Table 1). Note that the magnitude of the first component in R 1 is equal to the magnitude of the fault introduced. Therefore, the sensor fault is detected, isolated and identified. Fig. 7 depicts R 6 computed without m 3 . All the components of R 6 are sensitive to the fault because a 1 is taken into account for the estimation of q6 . The rate-gyro measurements satisfy the dynamic nonlinear equation

q = q0 - → q = 1 2 -- → q T I 3 q 0 + [ - → q × ] ω (9)
Eq. ( 9) is approximated to provide the diagnosis of rate gyros. The diagnostic procedure implemented is depicted in Fig. 8. It is summarized hereafter:

(1) the FDI algorithm proposed in section (3.1) to obtain an unfaulty estimate of the attitude (i.e. the quaternion qi computed without faulty sensor) is first used. Denote q(k) this attitude computed at time kT e ; (2) q(k) is filtered to reduce the noise. The filter is designed as follows:

H(z) = (1 -α)z -1 1 -αz -1 (10)
with α = e -Te τ , and T e = 10 ms the sampling period;

(3) the filtered attitude is derived to obtain q. This derivative is obtained with the following approximation:

dq dt ≈ qfilter (k) -qfilter (k -1) T e (11)
(4) With q and q, solve (9) in a least squares sense to compute ωi ; (5) the residual vector r ωi , i = 1 : 3, is the difference between the measurements and their estimates. As an example, consider a bias failure of 0.1 rad/s = 5.7 o /s on the rate gyro g 3 that appears at t = 5 s. Fig. 9 shows the real attitude of the quadrotor if this sensor fault is not detected. It is clear that for safety reason, the rate gyro sensor faults must be diagnosed. 11 shows the real attitude of the quadrotor in the fault-free case. The first reference attitude is reached after 2.5 s and the new attitude is attained after 1.5 s. Now consider that at the time the reference changes, two rate gyro sensor faults appear simultaneously: a bias failure of 0.5 rad/s is added on g 3 and a drift failure of 0.5 rad/s appears on g 1 . Fig. 12 shows the real attitude if these faults are not detected. The φ angle is very different from its nominal value and the system will crash. Fig. 13 shows the residual vector r ω . As can be seen, r ω1 is sensitive only to the drift failure in g 1 and its magnitude is equal to the magnitude of the fault. In the same way, r ω3 is sensitive only to the bias failure in g 3 and its magnitude is equal to the magnitude of the failure. r ω2 is insensitive to both failures. Moreover, all residuals are insensitive to a reference change.

FDI results in the presence of a disturbance

A complex problem tackled by the diagnostic community is developing residual generators insensitive to model uncertainty and real disturbances acting on the system to diagnose while remaining sensitive to faults. A step disturbance of 2 o in applied on each angle. The objective is to evaluate the robustness of the residual generator proposed in the present paper against disturbances. Theses disturbances could represent a gust of wind.

Fig. 14 shows the residual vector R 1 in the presence of the disturbances. Remind that R 1 is computed without a 1 . Fig. 15 shows the residual vector r ω . As can be seen, the proposed FDI algorithm is totally insensitive to these disturbances because it does not rely on the dynamic model of the rigid body on which the IMU is fixed.

CONCLUSION AND PERSPECTIVES

A new method to perform FDI of an Inertial Measurement Unit is proposed in this paper. A bank of estimators has been implemented that take advantage of information redundancy. Actually there is no sensor redundancy, but the various sensors sense complementary and redundant information. From the attitude estimate and the measurement models, the residuals can be computed as the difference between the measurements and their estimates. A strongly isolating table is obtained. Contrary to (Berbra et al. (2008a)) or [START_REF] Tanwani | Experimental networked embedded minidrone-part II. Distributed FDI[END_REF]), the method proposed in the present paper is insensitive to a disturbance applied on the rigid body in which the IMU is embedded. Moreover, it is insensitive to an uncertainty in the dynamic model of the rigid body, for instance an uncertainty in the inertia matrix of the rigid body. This nice property exists because the model of the rigid body is no more used for diagnosis. Additionally, with the method proposed, the fault identification can be performed and simultaneous sensors faults can be considered. It is important to note that the FDI procedures proposed here are general ones and can be applied to any system that makes use an Inertial Measurement Unit to estimate attitude. This new algorithm must now be tested for the quadrotor application. Note that a first step will be to use an "hardware in the loop" experiment (Berbra et al. ( 2009)) because the system embeds a network on which the data from the IMU as transmitted to the processor unit.

For the quadrotor application, a Fault Tolerant Control could be implemented to take into account the sensor faults. As the magnitude of the residuals are the same as the magnitude of the faults, the FTC can be expected to be easier. Moreover, when faulty sensors are isolated, only the unfaulty measurements could be used by the state observer. Due to redundancy in the information sensed by the sensors, this observer can be exploited with partial measurement loss [START_REF] Lesecq | Quadrotor attitude estimation with data losses[END_REF]. Thus the control law would not need to be modified.

Fig. 2 .

 2 Quadrotor

Fig. 3 .

 3 Fig. 3. Real attitude of the quadrotor in fault-free case

  ALGORITHM BASED ON OP TECHNIQUE A bank of estimators/observers is use diagnosis of the quadrotor [9]. Therefore, are obtained. Only accelerometer or ma faults are considered in the present paper. I algorithms for rate-gyro or actuator faults been presented. Fig.5 shows the principle

Fig. 5 .

 5 Fig. 5. Residuals generation for sens

Fig. 3 .

 3 Fig. 3. Real attitude in the fault-free case

Fig. 3 .

 3 Fig. 3. Real attitude of the quadrotor in fault-free case

  estimators/observers is use diagnosis of the quadrotor [9]. Therefore, s are obtained. Only accelerometer or ma faults are considered in the present paper. In algorithms for rate-gyro or actuator faults been presented. Fig.5 shows the principle

Fig. 5 .

 5 Fig. 5. Residuals generation for sens

Fig. 3 .

 3 Fig. 3. Real attitude of the quadrotor in fault-free case

  Fig. 5. Residuals generation for sensor faults

Fig. 5 .

 5 Fig. 5. Residuals generation for accelerometer and magnetometer sensors

Fig. 6 .Fig. 7 .

 67 Fig. 6. Residual vector R 1 in presence of a fault in a 1 at time t = 5 s

  Fig.

  Fig. 9. Real attitude of the quadrotor with a fault in g 3 at time t = 5 s Fig.10shows the residual vector r ω expressed in rad/s . As expected, only the residual r ω3 is sensitive to this sensor fault.

Fig. 10 .

 10 Fig. 10. Residual vector to detect rate-gyro sensor faults Consider the following scenario: the reference attitude is first equal to [φ θ ψ] = [0 0 0] o . At time t = 5 s, the reference attitude becomes [φ θ ψ] = [10 -20 5] o . Fig.11shows the real attitude of the quadrotor in the fault-free case. The first reference attitude is reached after 2.5 s and the new attitude is attained after 1.5 s. Now consider that at the time the reference changes, two rate gyro sensor faults appear simultaneously: a bias failure of 0.5 rad/s is added on g 3 and a drift failure of 0.5 rad/s appears on g 1 .

Fig. 12 .

 12 Fig. 11. Real attitude in the fault-free case

Fig. 13 .

 13 Fig. 13. Residual vector to detect simultaneous rate-gyro sensors faults

Fig. 15 .

 15 Fig. 14. R 1 in the presence of a disturbance

TABLE

TABLE I FAULT SIGNATURE TABLE

 ISIGNATURE

Table 1 .

 1 Fault signature table to isolate accelerometer and magnetometer sensor faults

	fa 1	fa 2	fa 3	fm 1	fm 2	fm 3

ACKNOWLEDGEMENTS

This work is partially supported by the Safe-NeCS project funded by the Agence Nationale de la Recherche (France) under grant ANR-05-SSIA-0015-03


R Coleman

On the image of Euler's totient function

Euler's totient function φ is the function defined on the positive natural numbers N * in the following way:

where (x, n) is the pgcd of x and n. Thus φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, and so on. The principle aim of this article is to study certain aspects of the image of the function φ.

Elementary properties

Clearly φ(p) = p -1, for any prime number p and, more generally, if α ∈ N * , then φ(p α ) = p αp α-1 . This follows from the fact that the only numbers which are not coprime with p α are multiples of p and there are p α-1 such multiples x with 1 ≤ x ≤ p α .

It is well-known that φ is multiplicative, i.e., if m and n are coprime, then φ(mn) = φ(m)φ(n). If n ≥ 3 and the prime decomposition of n is

n = p α1 1 . . . p αs s ,
then from what we have seen

φ(n) = s i=1 (p αi i -p αi-1 ) = n s i=1 (1 - 1 p i ).
Notice that p αp α-1 = p α-1 (p -1).

This implies that, if p is odd or p = 2 and α > 1, then p αp α-1 is even. Hence, for n ≥ 3, φ(n) is even. Thus the image of φ is composed of the number 1 and even numbers.

The following property is simple but very useful. proof If m is odd, then (2, m) = 1 and so

φ(2m) = (2 -1)φ(m) = φ(m). If m is even, then (2, m) = 1, hence φ(2m) = 2φ(m) = φ(m)
. This ends the proof. 2

2 Bounds on φ -1 (m)

Let m ∈ N * and consider the inverse image φ -1 (m) of m, i.e.

φ -1 (m) = {n ∈ N * : φ(n) = m}.
There are several questions we might ask. First, is the set φ -1 (m) empty and, if not is it finite. It is easy to see that φ -1 (1) = {1, 2} and as we have already seen, φ -1 (m) is empty if m is odd. It remains to consider the case where m is an even number. The following result, due to H. Gupta [START_REF] Gupta | Euler's totient function and its inverse[END_REF], helps us to answer these questions.

Proposition 2.1 Suppose that m is an even number and let us set

A(m) = m p-1|m p p -1 , where p is prime. If n ∈ φ -1 (m), then m < n ≤ A(m).
proof Clearly, if φ(n) = m, then m < n. On the other hand, if φ(n) = m and n = p α1 1 . . . p αs s , then

m = n s i=1 p i -1 p i =⇒ n = m s i=1 p i p i -1 .
However, if p|n, then from the first section we know that p -1|φ(n) and it follows that, for each p i , p i -1|m. Hence n ≤ A(m). 2

The proposition shows that the inverse image of an element m ∈ N * is always finite. It also enables us to determine whether a given number m is in the image of φ: we only need to determine A(m), and then calculate φ(n) for all integers n in the interval (m, A(m)].

Examples 1. The divisors of 4 are 1,2 and 4. Adding 1 to each of these numbers we obtain 2, 3 and 5, all of which are prime numbers. Thus A(4

) = 4 • 2 1 • 3 2 • 5 4 = 15.
To find the inverse image of 4, it is sufficient to consider numbers between 5 and 15. In fact, φ -1 (4) = {5, 8, 10, 12}. 2. The divisors of 14 are 1, 2, 7 and 14. However, if we add 1 to each of these numbers we only find a prime number in the first two cases. Thus A(14) = 14 • 2 1 • 3 2 = 42. If we consider the numbers n between 15 and 42, we find φ(n) = 14 and so φ -1 (14) = ∅.

Remark The example m = 14 shows that there are even numbers which are not in the image of φ.

A is a function defined on {1} ∪ 2N * . Let us look at the first values of A with the corresponding values of φ (when defined): From the table we see that A(m) may be odd, even or a fraction and that A is not increasing (A(12) > A( 14)). Also, we may have φ(A(m)) = m or φ(A(m)) > m.

m A(m) φ(A(m)) 1 2
It is interesting to consider the special case m = 2 k . The only divisors of 2 k are 1, 2, 2 2 . . . , 2 k . If we add 1 to each of these numbers, we obtain numbers of the form 2 i + 1, where 0 ≤ i ≤ k. For i ≥ 1, such numbers are prime only if i is a power of 2. A number of the form

F n = 2 2 n + 1 is said to be a Fermat number. Therefore A(2 k ) = 2 k • 2 • F n F n -1 = 2 k+1 • F n F n -1 ,
where the product is taken over Fermat numbers F n which are prime and such that F n -1|2 k . For example, if m = 2 5 = 32, then F 0 , F 1 and F 2 are the only Fermat numbers F n such that F n -1|m. In addition these Fermat numbers are all prime. Therefore A(m) = 64

• 3 2 5 4 • 17 16 = 255 2 .
The Fermat numbers F 0 , . . . , F 4 are all prime; however F 5 , . . . , F 12 are composite numbers and it has been shown that for many other numbers n, F n is composite. In fact, up till now no Fermat number F n with n ≥ 5 has been found to be prime. If there are no prime Fermat numbers with n ≥ 5, then for 2 k ≥ 2 16 we have

A(2 k ) = 2 k+1 • F 0 2 • F 1 2 2 • F 2 2 4 • F 3 2 8 • F 4 2 16 = 2 k-30 F 0 F 1 F 2 F 3 F 4 ,
which is an integer for k ≥ 30.

Before closing this section, let us consider the upper bound on odd elements of φ -1 (m). From Corollary 1.1, we know that if n is odd and n ∈ φ -1 (m), then 2n ∈ φ -1 (m), therefore an upper bound on odd elements of φ

-1 (m) is A(m)
2 . We should also notice that at least half of the elements in φ -1 (m) are even. In fact, φ -1 (m) may be non-empty and contain very few odd numbers, or even none. For example, the only odd number in φ -1 (8) is 15 and φ -1 (2 32 ) contains only even numbers (see Theorem 5.2 further on).

The case m = 2p

We now consider in some detail the case where p is prime and m = 2p. Theorem 3.1 If p is a prime number, then 2p lies in the image of φ if and only if 2p + 1 is prime.

proof If 2p + 1 is prime, then φ(2p + 1) = 2p and so 2p ∈ Im φ.

Suppose now that 2p ∈ Im φ. If p = 2, then 2p = 4 ∈ Im φ, car φ(5) = 4 and 2p + 1 = 5, which is prime. Now suppose that p is an odd prime. As 2p ∈ Im φ, there exists n such that φ

(n) = 2p. If n = 2 k , then 2 k-1 = φ(2 k ) = 2p
, which is clearly impossible, because p is an odd number greater than 1. Hence there is an odd prime q such that n = qs. There are two cases to consider: 1. q |s, 2. q|s. We will handle each of these cases in turn, using Proposition 1.1.

Case 1. We have 2p = (q -1)φ(s) which implies that q -1|2p. The only divisors of 2p are 1, 2, p and 2p. As q = 2, the possible values for q -1 are 2, p or 2p and hence for q are 3, p + 1 or 2p + 1. However, p + 1 is not possible, because p + 1 is even and hence not prime. If q = 3, then φ(s) = p. As p is an odd number greater than 1, this is not possible. It follows that q = 2p + 1 and so 2p + 1 is prime. Case 2. Here we have 2p = qφ(s) and so q|2p. The possible values of q are 1, 2 , p or 2p. However, as q is an odd prime, we must have q = p. This implies that φ(s) = 2. Also, q|s and so q -1|φ(s). It follows that p = q = 3 and hence 2p + 1 = 7, a prime number.

As in both cases 2p + 1 is prime, we have proved the result.

2

Definition A prime number of the form 2p + 1, with p prime, is said to be a safe prime. In this case, the prime number p is said to be a Sophie Germain prime.

Remarks 1. The theorem does not generalize to odd numbers. Certainly, if s is odd and 2s + 1 is prime, then 2s ∈ Im φ. However, it may be so that 2s + 1 is not prime and 2s ∈ Im φ. For example, 54 = φ(81) and so 54 ∈ Im φ. However, 54 = 2 • 27 and 2 • 27 + 1 = 55, which is not prime.

2.

Let us now consider φ -1 (2p). From Theorem 3.1, the set φ -1 (2p) is empty if 2p + 1 is not prime. If 2p + 1 is prime, then we have

A(2p) = 2p • 2 1 • 3 2 • 2p + 1 2p = 6p + 3. Hence, if n ∈ φ -1 (2p), then 2p < n ≤ 6p + 3. It is worth noticing that φ(6p + 3) = φ(3)φ(2p + 1) = 2 • 2p = 4p. Corollary 3.1 If 2p ∈ Im φ, then 2 k p ∈ Im φ, for k ≥ 1.
proof For k = 1 the result is already proved, so suppose that k ≥ 2. As 2p + 1 is an odd prime, 2 k and 2p + 1 are coprime. Therefore

φ(2 k (2p + 1)) = φ(2 k )φ(2p + 1) = 2 k-1 2p = 2 k p.
This ends the proof. 2

Remarks 1. From the corollary we deduce that, for every prime p such that 2p + 1 is prime, there is an infinity of numbers a such that a ≡ 0(mod p) and a ∈ Im φ.

2. If 2p / ∈ Im φ, then we cannot say that 2 k p / ∈ Im φ for any k ≥ 2. For example, 14 / ∈ Im φ, but 28 ∈ Im φ.

Sets of elements of the form 2p

In this section we will need an important theorem due to Dirichlet: Theorem 4.1 If n ∈ N * and (a, n) = 1, then there is an infinite number of prime numbers p such that p ≡ a(mod n).

Chapman [START_REF] Chapman | Dirichlet's theorem: a real variable approach[END_REF] has recently given a relatively elementary proof of this result.

Let us consider the prime numbers p in the interval [ It is natural to ask whether there is an infinite number of distinct primes p such that 2p ∈ Im φ (resp. 2p / ∈ Im φ). Our question amounts to asking whether there is an infinite number of safe primes, or equivalently an infinite number of Sophie Germain primes. Up till now this question has not been answered. The largest known safe prime, found by David Undebakke in January, 2007, is 48047305725.2 172404 -1. We can say a lot more concerning numbers of the form 2p which are not in the image of φ.

Theorem 4.2 For any odd prime number p, there is an infinite set S(p) of prime numbers q such that 2q / ∈ Im φ and p|2q + 1.

proof If p is an odd prime, then p-1 2 is a positive integer and ( p-1 2 , p) = 1. From Dirichlet's theorem, we know that there is an infinite number of prime numbers of the form q = p-1 2 + kp, with k ∈ Z. Then

2q + 1 = 2 p -1 2 + kp + 1 = p + 2kp = p(1 + 2k).
From Theorem 3.1, we know that 2q / ∈ Im φ and clearly p|2q + 1. 2

Remark The sets S(p) may have common elements, but in general are distinct. For example, 14 is in S(3) and S(5), but not in S(7), 26 is in S(3), but not in S(5) and S(7) and 34 is in S(5) and S(7), but not in S(3).

The following result follows directly from the theorem.

Corollary 4.1 For every odd prime number p, there exists an infinite subset S(p) of N * such that a ≡ -1(mod p).

and a / ∈ Im φ, when a ∈ S(p).

Remark At least for the moment, we cannot say that there is an infinity of odd prime numbers p such 2p ∈ Im φ. However, we can say that that there is an infinity of odd numbers s such that 2s ∈ Im φ. Here is a proof. From Dirichlet's theorem, there is an infinity of prime numbers p such that p ≡ 3(mod 4). Thus, for each of these primes, there exists k ∈ Z such that

p = 3 + 4k = 1 + 2(1 + 2k). As 1 + 2(1 + 2k) is prime 2(1 + 2k) ∈ Im φ and of course 1 + 2k is odd. 5 Structure of φ -1 (m)
If n is an odd solution of the equation φ(n) = m, then 2n is also a solution (Corollary 1.1). It follows that the equation can have at most half its solutions odd. It is natural to look for cases where there are exactly the same number of odd and even numbers of solutions.

First let us consider the case where m = 2p and p is an odd prime. If p = 3, then 6 < n ≤ 21. A simple check shows that φ -1 (6) = {7, 9, 14, 18}. There are two odd and two even solutions of the equation φ(n) = 6. Proposition 5.1 If p is a prime number such that p ≥ 5 and 2p + 1 is prime, then φ -1 (2p) contains exactly one odd and one even element, namely 2p + 1 and 4p + 2.

proof If φ(n) = 2p, then, from Remark 2. following Theorem 3.1, 2p < n ≤ 6p + 3. The divisors of 2p are 1, 2, p and 2p and so the only possible prime divisors of n are 2, 3 and 2p + 1. If n = 2p + 1 or 4p + 4, then φ(n) = 2p and there can be no other multiple n of 2p + 1 such that φ(n) = 2p. If n is not a multiple of 2p + 1 and φ(n) = 2p, then n must be of the form n = 2 α • 3 β . If α ≥ 3, then 4|2p, which is impossible. Also, if β ≥ 2, then 3|2p. However, this is not possible, because p ≥ 5. Therefore α ≤ 2 and β ≤ 1. As n > 2p ≥ 10, the only possibility is n = 12. As φ(12) = 4, this is also impossible. The result now follows.2

We can generalize this result to odd numbers in general. We will write O(m) (resp. E(m)) for the set of odd (resp. even) solutions of the equation φ(n) = m. proof If the equation φ(n) = 2s has no solution, then there is nothing to prove, so suppose that this is not the case. If n is an odd solution of the equation, then 2n is also a solution. Hence O(2s) ≤ E(2s).

If n is an even solution, then we may write n = 2 α t, with α ≥ 1 and t odd. If t = 1, then φ(n) is a power of 2, which is not possible. It follows that t ≥ 3. If we now suppose that α > 1, then φ(n) = 2 α-1 φ(t) and, as φ(t) is even, 4 divides φ(n) = 2s, which is not possible. Therefore α = 1 and so n = 2t. As φ(t) = φ(2t) = φ(n), we must have O(2s) ≥ E(2s) and the result now follows.

2

Corollary 5.1 There is an infinity of numbers m such that φ -1 (m) is non-empty and composed of an equal number of odd and even numbers.

proof It is sufficient to recall that there is an infinity of primes p such that p = 1 + 2s, with s odd (remark after Corollary 4.1). 2

At the other extreme is the case where φ -1 (m) is non-empty and composed entirely of even numbers. In considering this question, the following result due to Gupta [START_REF] Gupta | Euler's totient function and its inverse[END_REF], is useful. We will give a modified proof of it.

Theorem 5.2 O(2 k ) = 0 or O(2 k ) = 1.
proof If k = 0, then we have φ -1 (2) = {3, 4, 6} and the result follows. Suppose now that k > 0 and that φ(n) = 2 k , with n odd. If p is an odd prime such that p -1 divides 2 k , then p must be of the form 2 i + 1. The only primes of this form are Fermat numbers, hence if n = p α1 0 . . . p αr r is the decomposition of n as a product of primes, then each p i must be a Fermat number. If we allow α i = 0, then we may suppose that p i = F i . Thus

2 k = φ(F α0 0 ) . . . φ(F αr r ) = αi≥1 F αi-1 i (F i -1).
If α i > 1 for some i, then the product is not a power of 2, hence we must have α i = 0 or α i = 1, for all i, and so 2 k = α 0 2 2 0 . . . α r 2 2 r .

Clearly α 0 . . . α r is k written in binary form. Therefore there can be at most one odd number n such that φ(n) = 2 k . If α i = 1 only when F i is prime, then there exists n odd such that φ(n) = 2 k and s(k) = 1.

On the other hand, if there is an α i such that F i is not prime, then there does not exist an odd number n such that φ(n) = 2 k . 2

If k < 32, then k can be written in binary form as α 0 . . . α 4 . As F 0 , . . . F 4 are all primes, there exists an odd number n such that φ(n) = 2 k . However, for 2 32 , this is not the case, because F 5 is not prime. Up till now no Fermat number F n , with n ≥ 5, has found to be prime, so it would seem that, for k ≥ 5, there is no odd number in the set φ -1 (2 k ). This suggests that there is an infinity of numbers m for which φ -1 (m) is non-empty and only composed of even numbers.

Conclusion

We have seen that the inverse image φ -1 (m) is an empty set for any odd positive integer m > 1 and also for an infinite number of even positive integers. We have also seen that, when φ -1 (m) is non-empty, its cardinal can be odd or even and that it can have at most half of its members odd; it is also possible that all its members are even. Up till now no number m has been found such that φ -1 (m) contains only one element. Carmichael conjectured that such a case does not exist, but this is yet to be proved (or disproved). However, for k ≥ 2, Ford [START_REF] Ford | The number of solutions of φ(x) = m[END_REF] has shown that there is a number m such φ -1 (m) contains precisely k elements.

To close I would like to thank Dominique Duval and Mohamed El Methni for reading the text and offering helpful suggestions.

Proposition 1 . 1 2 Corollary 1 .

 1121 If p, m ∈ N * , with p prime, and n = pm, then φ(n) = (p -1)φ(m), if (p, m) = 1, and φ(n) = pφ(m), if (p, m) = 1. proof If (p, m) = 1, then we have φ(n) = φ(p)φ(m) = (p -1)φ(m).Now suppose that (p, m) = 1. We may write m = p α m ′ , with α ≥ 1 and (p, m ′ ) = 1. Thusφ(n) = φ(p α+1 )φ(m ′ ) = p α (p -1)φ(m ′ ). However φ(m) = p α-1 (p -1)φ(m ′ )and so φ(n) = pφ(m). 1 φ(2m) = φ(m), if and only if m is odd.

Theorem 5. 1

 1 If s is odd and s ≥ 3, then O(2s) = E(2s).