Eitan Altman
email: altman@sophia.inria.fr

Konstantin Avrachenkov

Laura Cottatellucci

Merouane Debbah
email: merouane.debbah@supelec.fr

Gaoning He

Alberto Suarez

Operating Point Selection in Multiple Access Rate Regions

We study the selection of the rate allocation in multiple access channels (MAC). We consider MACs with different rate regions. Namely, we investigate the polytope rate regions, convex non-polytope rate regions, and non-convex rate regions. Different operating points of the rate region possess different properties in terms of efficiency, fairness, stability, etc. Our goal is to provide guidelines for the choice of an operating point using the above-mentioned criteria. We use two methodological approaches: fairness function approach leading to an optimal system operation point and game theoretic approach leading to an equilibrium point. In particular, we use games with correlated constraints. All fairness concepts and normalized Nash equilibrium produce the same rate allocation in the case of a MAC with polytope rate region. In the case of MACs with convex non-polytope and non-convex rate regions this property does not hold and behavior becomes much more various. In the case of some non convex rate regions the max-min fair allocation may even not exist.

I. INTRODUCTION

In this paper we consider capacity regions for different kind of multiple access channels (MAC). A capacity region consists of all n-tuples of achievable rates for a MAC with n users transmitting to a common destination. Typically, one has a very broad choice of achievable rates over the capacity region, however different operating points possess different properties in terms of efficiency, fairness, stability, etc. Our goal is to provide guidelines for the choice of an operating point using above-mentioned criteria. We classify MACs by geometrical characteristics of their capacity regions. Namely, we investigate the polytope capacity regions, convex nonpolytope capacity region and non-convex capacity regions. An example of MAC with a polytope capacity region is the General Time-Invariant Gaussian MAC [START_REF] Cover | Elements of Information Theory[END_REF]. Examples of MACs with a convex non-polytope capacity region are TDMA and FDMA MACs [START_REF] Cover | Elements of Information Theory[END_REF]. An example of MAC with a non-convex capacity region is the Collision channel without feedback [START_REF] Massey | The Collision Channel without Feedback[END_REF]. For the selection of the operating point we use two methodological approaches: game theoretic approach leading to an equilibrium point and fairness function approach leading to an optimal system operation point.

The fairness function approach can be applied to any kind of capacity region. It turns out that in the case of the polytope capacity region some specific optimal fair points coincide with the equilibrium points attained in some games. The latter allows one to use distributed algorithms to achieve those operating points.

In particular in the game theoretic framework we consider games with correlated constraints arising in MACs with polytope capacity regions. In constrained games, each player is faced with a constrained optimization problem rather than a simple non-constrained optimization; the constraints may be independent of actions of other players, in which case they are called "orthogonal constraints" [START_REF] Rosen | Existence and Uniqueuness of Equilibrium Points for Concave N -person games[END_REF]. A more complex situation arises when the actions available to one player depend on those used by the others. Such games are called games with correlated constraints [START_REF] Rosen | Existence and Uniqueuness of Equilibrium Points for Concave N -person games[END_REF]. These games exhibit various characteristics that are very different than those without constraints or with orthogonal constraints. A central feature in these games is that they often possess a large number of equilibria. Natural questions that arise concern selection of an equilibrium. Can we identify ones that are more fair or more stable than others? We study this type of selection criteria as well as other criteria related to decentralized implementations.

It turns out that in MAC with polytope capacity region the rate assignment corresponding to the α-fairness function optimization is the same for all values of the parameter α. It also coincides with the max-min fair allocation, which for this type of MAC, is the same as α-fair allocation when the parameter α goes to infinity. We prove that the α-fair allocation for the MAC with polytope capacity region also coincides with a unique normalized Nash equilibrium. We also show that in this case the maximization of the Jain's fairness index corresponds to maxmin fairness. The above properties are related to the particular polytope structure of the achievable rate region.

In the rest of the paper we investigate multiaccess channels whose achievable regions are not a polymatroid; we study cases in which they are convex but not polytopes, and cases in which they are not convex. We show how the geometric properties of the rate capacity alter the properties of rate assignments corresponding to various fairness concepts. In particular, we show that in the case of some non convex achievable rate regions the maxmin fair allocation may not exist.

II. POLYMATROID ACHIEVABLE RATE REGION

Consider n non-cooperative mobiles transmitting up-link to a base station. The square amplitude of the channel gain between mobile i and the base station is h i . The variance of the additive white Gaussian noise is denoted by σ 2 0 . We consider the setting in which the achievable rate region is given by the convex polytope C defined by the set of constraints:

i∈S R i ≤ ρ(S) ∀S ⊂ {1, ..., n} (1)
where

ρ(S) = log 1 + i∈S P i h i σ 2 0 .
We assume that no mobile (player) can tolerate the losses that would occur if transmission rates were chosen outside the achievable region. This assumption places these games in the category of games with common constraints [START_REF] Rosen | Existence and Uniqueuness of Equilibrium Points for Concave N -person games[END_REF]. Each player wishes to maximize its own transmission rate, or more generally some strictly concave increasing function U i of its rate. This game has coupled constraints: the choice of strategies of a player depends on the strategies chosen by other players.

The equilibrium notion here, is that of finding a rate allocation vector R within C such that no mobile i can gain by deviating from R i to another S i for which (S i , R -i ) ∈ C (here R -i is the vector of strategies R j for j = i, where R j is the entry of R corresponding to player j). This equilibrium concept is a special case of the so-called "generalized equilibrium" or "social equilibrium". They have been introduced already in [START_REF] Arrow | Existence of an equilibrium for a competitive economy[END_REF], [START_REF] Debreu | A social equilibrium existence theorem[END_REF] (for more recent papers see [START_REF] Debreu | Existence of competitive equilibrium[END_REF], [START_REF] Facchinei | On generalized Nash games and variational inequalities[END_REF]).

As shown recently in [START_REF] Altman | Games with constraints with networking applications[END_REF], to define games with constraints it is not sufficient to know the utility and constraints of each given player. One should also specify how does a player value the fact that constraints of another player are satisfied or violated. Some extreme cases are (i) a player is indifferent to satisfaction of constraints of other players, (ii) common constraints: if a constraint is violated for one player then it is violated for all players. The equilibrium point selections at hand are modelled as games with common constraints. In particular, we shall study the properties of a subset of the equilibria of such games known as normalized equilibria introduced by Rosen [START_REF] Rosen | Existence and Uniqueuness of Equilibrium Points for Concave N -person games[END_REF]. They have properties that are quite appealing in terms of decentralized implementation, pricing and billing.

Games with coupled constraints along with the generalized equilibrium has been applied to many networking problems, see e.g. [START_REF] Altman | S-modular games and power control in wireless networks[END_REF], [START_REF] Altman | Constrained Markov Games: Nash Equilibria[END_REF], [START_REF] Altman | Games with constraints with networking applications[END_REF], [START_REF] Azouzi | Constrained traffic equilibrium in routing[END_REF].

It is straightforward to see that we have:

Lemma II.1. All rates satisfying

n i=1 R i = ρ(S)
, where S = {1, ..., n}, subject to [START_REF] Altman | S-modular games and power control in wireless networks[END_REF] are Nash equilibria and are Pareto-efficient. Any other point is not an equilibrium.

Remark II.1. The strategy of player i in our game consists of choosing the ith entry of a rate vector. A deviation of the ith player from a point in the achievable rate region to another one in that region affects only the rate of that player and not that of other ones.

In view of the large number of Nash equilibria we address next the problem of selecting one which has desirable properties: the normalized Nash equilibrium. The motivation for proposing that one is related to pricing and billing issues. Pricing We are interested in pricing mechanisms that induce equilibria strategies and that can be implemented in a scalable and decentralized way. Let λ i be the per packet price for mobile i and let λ be the vector whose ith entry is λ i . Then the payoff of mobile i with the additional pricing becomes

L λ i (R) := U i (R i ) + λ i ( n i=1 R i -ρ(S)). Define C := i∈S R i ≤ ρ(S), ∀S ⊂ {1, ..., n} \ S.
Consider now the following relaxed game. Find R * ∈ C such that for each i and R ∈ C,

L λ i (R * ) ≥ L λ i (R i , (R * ) (-i) ).
If it has a solution then L λ i (R * ) can be viewed as the Lagrangian that corresponds to the constrained optimization problem faced by mobile i when the other mobiles play (R * ) (-i) obtained by relaxing the single constraint i∈S R i ≤ ρ(S). From Karush-Kuhn-Tucker (KKT) Theorem we know that there exists a vector λ (whose entries are not necessarily equal) such that a rate vector R * is an equilibrium in the original game only if for each i, R * i maximises

L λ i (R i , (R * ) (-i) ) obtained by relaxing the single constraint i∈S R i ≤ ρ(S).
Thus, λ can be used to define a non-scalable pricing. It is non-scalable since the price per packet will depend on i.

Let x * be the vector whose ith component is given by the solution to

dU i (x) dx + λ i = 0. (2)
If x * ∈ C then it is the unique equilibrium of the relaxed game.

Denote the solution by R * (λ).

Problem P1: Consider a constant λ and let λ be a vector of dimension n with all its entries λ. Then, we wish to find λ such that R * (λ) is an equilibrium of the original game.

If we find such a λ then it defines indeed a scalable distributed pricing since the billing can be performed per packet and can be implemented without any knowledge to which mobile the packet belongs to.

An equilibrium associated with some constant λ that solves Problem P1 is a special case of the normalized equilibrium concept introduced in [START_REF] Rosen | Existence and Uniqueuness of Equilibrium Points for Concave N -person games[END_REF].

Theorem II.1. There exists a unique normalizied equilibrium to the original problem associated with some λ as defined in Problem P1.

Proof: Define G to be the n dimensional square matrix whose ijth entry is ∂Li(R) 2 ∂Ri∂Rj . Then obviously, G + G T is strictly negative definite. The Theorem then follows from [START_REF] Rosen | Existence and Uniqueuness of Equilibrium Points for Concave N -person games[END_REF]Thm 4].

A. Equal utility functions and maxmin fair assignment

Fix λ as given in Theorem II.1. Assume that U i is the same for all i. Then the Lagrangians corresponding to each player i have all the same dependence on their argument:

L λ i (R) := U (R i ) + λ( n j=1 R j -ρ(S)).
Thus x * defined in equation ( 2) has the form (x, ..., x). Note that x does not depend on P i and h i , i = 1, ..., n.

Thus for any P i and h i such that x * ∈ C, the scalable pricing λ from Theorem II.1 yields a Pareto equilibrium which is fair in the sense that all users receive the same rates. This is a special case of the maxmin fairness which we define next.

Definition II.1. A rate allocation is called maxmin fair if we cannot increase the rate R i of user i without decreasing the rate R j for some user j with R j ≤ R i , while maintaining feasibility.

Next we show that (i) when maximizing the sum of utilities over C, the unique solution corresponds to the maxmin throughput assignment; and (ii) the normalized equilibrium is always maxmin fair, even if x * / ∈ C. In the latter case, the equilibrium will of course not be symmetric.

Figures 1 and2 are examples of achievable rate regions for the case of two users. Figure 1 exhibits a case where the maxmin fair rates are equal. In Figure 2 the point on the boundary (the segment S 1 parallel to the x-axis) for which the rates are equal is not Pareto optimal and therefore is not maxmin fair. The maxmin fair rate assignment is in that case the intersection between the segment S 1 and the diagonal segment.

Remark II.2. There are achievable rate regions of other access networks that have the following property Π Pareto : all the points on the boundaries other than those on the axis, are Pareto optimal. An example is given in Section III. Let x be the intersection of the diagonal segment with the Pareto frontier. By construction, all coordinates of x are equal. Since x is Pareto optimal, then for any direction i, the only way to increase x i is by decreasing x j for some j such that x j = x i . Hence, x is a max-min fair assignment. Thus when Π Pareto holds, the maxmin assignment always symmetric even if the data are not.

To establish the above mentioned results we shall use the majorization order and Schur concavity which we define next.

Definition II.2. (Majorization and Schur-Concave Function [10])

d [i] (1) ≤ k i=1 d [i] (2), k = 1, ..., n -1,
and n i=1 d [i] (1) = n i=1 d [i] (2),
where The following result from [START_REF] Shum | Fair Rate Allocation in Some Gaussian Multiaccess Channels[END_REF] characterizes the maxmin fair rate assignement in terms of majorization.

d [i] (m) is a permutation of d i (m) satisfying d [1] (m) ≥ d [2] (m) ≥ ... ≥ d [n] (m), m = 1, 2. A function f : R n → R is Schur concave if d(1) ≺ d(2) implies f (d(1)) ≥ f (d(2)).
Theorem II.2. The maxmin fair rate assignment belongs to the dominant face S and is majorized by any other point on the dominant face.

We would like to note that there is an algorithm with O(n 2 ) complexity for determination of the maxmin fair rate assignment [START_REF] Shum | Fair Rate Allocation in Some Gaussian Multiaccess Channels[END_REF].

B. Other fairness concepts and their relation to the Normalized equilibrium

1) Global optimization: Consider the global optimization problem of maximizing the sum of the utilities n i=1 U (R i ) over the achievable rate region C. We relax the constraint i R i ≤ ρ(S) and write the Lagrangian

L λ (R) := i U (R i ) + λ( n j=1 R j -ρ(S)).
We can rewrite it as

L λ (R) := i ψ(R i ) where ψ(x) := U (x)+λx- ρ(S) n . (3)
Using Lemma II.2 we conclude that L λ (R) is Schur concave. We conclude from Lemma II.2 the following:

Theorem II.3. The sum of utilities over the achievable rate region is maximized at the maxmin rate assignment.

Proof: According to Theorem II.2, the maxmin fair rate assignment is majorized by any other point on the dominant face. It therefore maximizes any Schur concave function on the dominant face. In particular, it maximizes L λ (R) for any λ since by Lemma II.2 we conclude that L λ (R) is Schur concave. This implies the Theorem since by Karush-Kuhn-Tucker (KKT) Theorem, there exists λ such that the sum of utilities is maximized by the rate assignment that maximizes the Lagrangian L λ (R). ⋄ 2) α-fairness: We next recall the concept of α-fairness and of general α-fairness. Mo and Walrand [START_REF] Mo | Fair End-to-End Window-based Congestion Control[END_REF] introduced the family of utility functions indexed by a real non-negative parameter α:

V α (x) = x 1-α 1 -α for α = 1.
Consider the problem of maximizing n i=1 V α (x i ) where (x 1 , ..., x n ) lies in a closed convex set X. It is shown in [START_REF] Mo | Fair End-to-End Window-based Congestion Control[END_REF] that the solution of the maximization problem converges to the maxmin fair assignment over X as α → ∞, it provides the harmonic fairness for α = 2, it converges to the proportional fair assignment as α → 1 and it provides the globally optimal assignment over X for α = 0. Now, instead of assigning fairly x ∈ X we can assign fairly some utility of x. We thus define

W α (x) = U (x) 1-α 1 -α and maximize n i=1 W α (x i ) over X.
The solution is called the generalized α-fairness [START_REF] Touati | Generalized Nash Bargaining Solution for bandwidth allocation[END_REF].

Corollary II.1. (i) For all α ≥ 0, the alpha-fair rate assignment coincides with the unique rate assignment. (ii) Consider some strictly concave increasing utility function U . For all α ≥ 0, the generalized alpha-fair rate assignment coincides with the unique maxmin rate assignment.

Proof: Both the α-utility V α as well as the generalized αutility W α are concave. It follows from Lemma II.2 that n i=1 V α (R i ) and n i=1 W α (R i ) are Schur concave. Since these are concave functions defined on a convex compact set, they have a solution (which is unique for all α > 0). The solution is thus the same for all α > 0 and is majorized by any other point on the dominant face of the rate region. In particular since this solution does not depend on α, it is the limit of the α-fair solutions as α → ∞ and therefore it follows from [START_REF] Mo | Fair End-to-End Window-based Congestion Control[END_REF] that the solution is maxmin fair. ⋄

Remark II.3. The proof of the Corollary provides an alternative proof to Theorem II.2.

Remark II.4. It may seem astonishing that all fairness concepts provide the same rate allocation. In fact, this is not the case in general fair assignment (see examples in [START_REF] Touati | Generalized Nash Bargaining Solution for bandwidth allocation[END_REF]) although the utilities V α and W α are always Schur concave. To understand this, note that both α-fair and generalized α-fair assignments are Pareto optimal. Whenever the Pareto optimal set has the property that the sum rates are constant then indeed any Schur concave function will have the same maximizer and thus all the fairness concepts would coincide. In the ensuing Sections III and IV we give examples of multiuser access channels where different fairness concepts result in different rate allocations.

3) Jain's fairness: We shall call a rate allocation Jain's fair if it maximizes the Jain's fairness index [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems[END_REF]:

J = ( n i=1 R i ) 2 n n i=1 R 2 i .
The Jain's fairness index ranges from 1/n (worst case) to 1 (best case).

Since the maxmin fair rate allocation minimizes

n i=1 R 2 i
[14], we conclude that the maxmin fair rate allocation is also the Jain's fair rate allocation.

4) The normalized equilibrium: We know from Theorem II.1 that there exists a unique normalized equilibrium R * to the original problem associated with some λ as defined in Problem P1. R * is thus such that for each i, its ith component maximizes

L λ i (R) := U (R i ) + λ( n j=1 R j -ρ(S)
). This implies that R * is the unique vector that maximizes

j U (R j ) + λ( n j=1 R j -ρ(S))
over C. This is the Lagrangian that corresponds to the global optimization problem. We conclude that R * is the globally optimal solution. Applying Theorem II.3 we conclude:

Theorem II.4. The unique normalized equilibrium is the maxmin fair assignment.

C. Differential services and weighted α-fairness

We next raise the question of providing differentiation between the mobiles. We do that by defining K priority classes. Let k(i) be the priority class corresponding to mobile i. We associate to class k priority some positive constant w k . Introduce the following problem.

Problem P2. Let λ be some constant and define the price per traffic of mobile i as λ i (w k ) = λ/w k if mobile i belongs to priority class k. We wish to find the constant λ such that λ i (w k(i) ) defines an equilibrium in our problem.

If such pricing exists then it is indeed scalable since billing is done not according to the exact identity of the source of each packet but according to the priority class of the transmitted packets.

An equilibrium obtained as in problem P2 indeed exists and is unique [START_REF] Rosen | Existence and Uniqueuness of Equilibrium Points for Concave N -person games[END_REF]. This is the general form of a normalized equilibrium. The choice of w k now allows to determine the rate that each priority class would get.

Furthermore, according to [START_REF] Rosen | Existence and Uniqueuness of Equilibrium Points for Concave N -person games[END_REF], finding normalized equilibrium is equivalent to the solution of the following optimization problem:

U (R) = n i=1 w k(i) U (R i ), (4)
subject to constraints (1). In the important particular case when the optimal solution to (4) lies on the dominant face and the choice of utility function corresponds to α-fairness, we have explicit expressions for λ and for the optimal rates.

Theorem II.5. Let U (x) be α-fairness utility function. If the optimal rate allocation lies on the dominant face, the Lagrange multiplier and the optimal rates are given by

λ = n j=1 (w k(j) ) 1/α ρ( S) α , and
R i = ρ( S) n j=1 (w k(j) ) 1/α (w k(i) ) 1/α . Proof:
The formulae of the theorem's statement are derived with the help of the Lagrangian

L = n i=1 w k(i) R 1-α i 1 -α + λ(ρ( S) - n i=1 R i ).
We note that if we take α = 1 the prices become proportional to the rates. In the case of α = 1 the utility function is logarithmic, which corresponds to the standard utility function for elastic traffic. This provides justification to price elastic traffic proportionally to required rates.

We also note that for any choice of weights we have that R i → ρ( S)/n as α → ∞ whenever the point (ρ( S)/n, ..., ρ( S)/n) belongs to the dominant face. In fact, since the case α → ∞ corresponds to the lexicographic optimization for any choice of weights, the following more general statement holds.

Theorem II.6. As α → ∞, the weighted α-fair rate allocation converges to maxmin fairness.

We would like to note that the lexicographic optimization and maxmin fairness concepts coincide for polymatroid capacity regions but can differ in the case of non-convex regions. We shall discuss this issue in more detail in the special section on non-convex capacity regions.

There are several kinds of multiple access systems whose capacity region is characterized by a polytope. Some examples are listed below:

• Multiple access systems with single transmit antennas at both sides and time invariant channel [START_REF] Cover | Elements of Information Theory[END_REF]. • Multiple access systems with single transmit and receive antennas and flat fading, when the channel state information is known only at the receiver but not at the transmitter [START_REF] Shamai | Information theoretic considerations for symmetric, cellular, multiple-access channels-Part I[END_REF].

• Multiple access systems with multiple transmit and receive antennas and unbiased flat fading, when the channel state information is known only at the receiver but not at the transmitter [START_REF] Rhee | On the capacity of multiuser wireless channels with multiple antennas[END_REF].

III. CONVEX NON-POLYTOPE ACHIEVABLE RATE REGION

Let us consider the Gaussian multiple access orthogonal channel. Classical example of orthogonal channels are TDMA and FDMA. In this case, the achievable rate region is given by

R i ≤ θ i ln 1 + P i h i θ i σ 2 ∀S ⊂ {1, ..., n} (5)
where 0 ≤ K ı=1 θ i ≤ 1. Given P i and h i , i = 1...K the achievable rate region (5) is convex but it is not a polytope and it is strictly contained in [START_REF] Altman | S-modular games and power control in wireless networks[END_REF]. All points on the capacity region border are Pareto efficient and Nash equilibria. Therefore, here again we need to choose among many Pareto efficient points and Nash equilibria. We suggest to use α-fairness utility function to select a particular equilibrium point. In the following theorem we characterize the α-fair equilibrium selection.

Theorem III.1. The α-fair rate allocation in the Gaussian multiple access orthogonal channel, which maximizes the utility function

U (R) = n i=1 R 1-α i 1 -α ,
is unique for any value of the parameter α and is given by θ's which solve the following system of equations

θ i ln(1 + P i h i θ i σ 2 ) -α ln(1 + P i h i θ i σ 2 ) - P i h i θ i σ 2 + P i h i = λ 0 , (6) n i=1
θ i = 1.

The above system has a solution in explicit form in the case of total rate maximization (α = 0):

θ * i = P i h i n k=1 P k h k . ( 7
)
When α → ∞, the α-fair rate allocation provides maxmin fair rate allocation (R * 1 = R * 2 = ... = R * n ). Proof. The uniqueness of the α-fair rate allocation follows from the fact that we deal with the convex optimization problem. The equations [START_REF] Debreu | Existence of competitive equilibrium[END_REF] follow from the KKT conditions for the Lagrangian

L = n i=1 R 1-α i 1 -α +λ i θ i ln(1 + P i h i θ i σ 2 ) -R i +λ 0 1 - n i=1 θ i .
For the particular case α = 0, it follows from system (6) that

ln(1 + P i h i θ i σ 2 ) - P i h i θ i σ 2 + P i h i = ln(1 + P j h j θ j σ 2 ) - P j h j θ j σ 2 + P j h j , or ln(1 + P i h i θ i σ 2 ) -ln(1 + P j h j θ j σ 2 ) = P i h i θ i σ 2 + P i h i - P j h j θ j σ 2 + P j h j .
Now it is easy to see that the values of θ's provided by [START_REF] Azouzi | Constrained traffic equilibrium in routing[END_REF] make zero both sides of the above equation. Also, it is clear that the values of θ's provided by [START_REF] Azouzi | Constrained traffic equilibrium in routing[END_REF] satisfy the normalization condition. ⋄ Let us calculate the Jain's fairness index for the rate allocation corresponding to the total rate maximization

J = ( n i=1 R i ) 2 n n i=1 R 2 i = ( n i=1 P i h i ) 2 n n i=1 P 2 i h 2 i ≥ 1 n .
We note that the lower bound 1/n can be achieved and hence the allocation corresponding to the total rate maximization can be extremely unfair judging by the Jain's fairness index. Thus, the α-fairness concept provides a continuous spectrum of rate allocations from the possibly very unfair total rate maximization to the completely fair maxmin rate allocation.

It is easy to calculate the maximal total rate corresponding to the total rate maximization problem

n i=1 R * i = ln 1 + n i=1 P i h i σ 2 .
Multiple access systems which enable time-sharing of the coding schemes are in general characterized by a convex capacity region. Examples of multiple access channels having a convex non-polytope capacity region with non linear boundary surfaces are:

• Time invariant multiple access systems with multiple antennas and without intersymbol interference (ISI) [START_REF] Yu | Iterative Water-filling for Gaussian Vector Multiple Access Channels[END_REF]. • Time invariant multiple access channel with single [START_REF] Cheng | Gaussian Multiaccess Channels with ISI: Capacity Region and Multiuser Water-Filling[END_REF] or multiple antennas [START_REF] Yu | Iterative Water-filling for Gaussian Vector Multiple Access Channels[END_REF] and ISI. • Flat fading channel with channel state information known at the transmitter and the receiver and single [START_REF] Tse | Multiaccess Fading Channel-Part I: Polymadroid Structure, Optimal Resource Allocation and Throughput Capacity[END_REF] or multiple transmitting and receiving antennas. • In all previous cases with fading channels we considered the ergodic capacity regions, i.e. we assumed that the codewords have a duration such that the channel is ergodic in such time interval. However, it is possible to consider a second situation when codewords have a duration independent of the scale of the channel variation.

In general, the channel is not stationary and ergodic in the timeframe of a codeword. In such a case, it is possible to have reliable communications only if the channel is known at both ends. These kind of capacity region for multiple access channel with single transmit and receive antennas are investigated in [START_REF] Tse | Multiaccess Fading Channel-Part II: Delay Limited Capacity[END_REF] and the maximum achievable rates are referred to as delay limited capacities. The approach of Theorem III.1 equally applies to the above multiple access channels. In particular, in the case of any strictly convex capacity region, there is a unique α-fair rate allocation. We also note that in the present case, similarly to the polymatroid capacity region case, the Jain's fair allocation coincides with the maxmin fair allocation.

IV. NON-CONVEX ACHIEVABLE RATE REGION

Shannon pointed out in [START_REF] Shannon | Two Way Communication Channels[END_REF] that all capacity and zerocapacity regions are convex if it is possible to time-share the coding schemes applied to attain individual points of the region. However, time sharing is not applicable to all systems. When some system characteristic prevents the use of time sharing the capacity region is not necessarily convex. As an example, time sharing is not applicable if the system nodes do not share a common time reference.

We present below some examples of systems with nonconvex rate regions.

A. Collision Channel Without Feedback

The collision channel without feedback has been studied first in [START_REF] Massey | The Collision Channel without Feedback[END_REF]. The absence of a feedback channel does not enable synchronization for applying time sharing of the codebooks. The interested reader is referred to [START_REF] Massey | The Collision Channel without Feedback[END_REF] for a detailed description of the system. Shortly, we recall here that the two cases of slot-synchronized and asynchronous collision channel are investigated in [START_REF] Massey | The Collision Channel without Feedback[END_REF]. The source for each user is Q-ary symmetric, independent of the others and generating information at a rate of C i packet/slot. The duty factor p i of user i is the fraction of time during which user i is actually transmitting packets. Thus, the transmitting rate of the user when she is actually using the channel is Ci pi . The signals at the receiver is impaired, eventually, only by colliding signals but not by additive noise. The capacity region is the set of all source rates that are approachable in the sense that there exist coding schemes with rate Ci pi with enable reliable communications 1 .

Let C u,0 , C u , C s,0 , and C s be the zero and non zero capacity regions of asynchronous collision channels, and the zero and non zero capacity regions of the slot-synchronous collision channels, respectively. All these regions coincide and the boundary of the common capacity region C is the set of all points [START_REF] Massey | The Collision Channel without Feedback[END_REF] C = (C 1 , C 2 , . . . , C n ) such that

C i = p i n j=1 j =i (1 -p j ) (8)
being p = (p 1 , . . . p n ) a probability vector whose elements are nonnegative and satisfying the constraint n i=1 p i = 1. Interestingly, C is not convex but its complement in the nonnegative orthant is convex [START_REF] Post | Convexity of the Non-achievable Rate Region for the Collision Channel without Feedback[END_REF]. Figure 3 shows the capacity region for the two users case.

In the next theorem we characterize the α-fair rate allocations for the non-convex capacity region described by [START_REF] Facchinei | On generalized Nash games and variational inequalities[END_REF].

Theorem IV.1. The α-fair rate allocation for the capacity region described by [START_REF] Facchinei | On generalized Nash games and variational inequalities[END_REF] has three distinct cases with respect to the value of α:

• Case α > α * : The α-fair rate allocation corresponds to the maxmin rate allocation. • Case α = α * : There are several α * -fair rate allocations.

Among α * -fair rate allocations one corresponds to the maxmin fair rate allocation. Moreover, if n = 2, any rate allocation on the capacity boundary is α * -fair. If n > 2, one α * -fair rate allocation corresponds to the maxmin fair allocation and the other α * -fair rate allocations correspond to total rate optimization and are given by the points R i = 1 and R j = 0 for j = i. • Case α < α * : The α-fair rate allocations correspond to total rate optimization and are given by the points R i = 1 and R j = 0 for j = i.

Fig. 1 .

 1 Fig. 1. Rate region: equal rates are maxmin fair

Lemma II. 2 .

 2 [10, Proposition C.1 on p. 64] Assume that a function g : R n → R can be written as the sum g(d) = n i=1 ψ(d i ) where ψ is a concave function from R to R. Then g is Schur concave.

The communications systems analyzed in the previous sections were characterized by the same source rate and transmission rate, while in this case the two quantity differs. To keep clear this feature, we adopt a different notation for the source rate in the collision channel and in the following recovery channel.

The threshold value α * is given by α * = (n -1) ln(n/(n -1)) ln(n) + (n -1) ln(n/(n -1))

.

Proof. To determine the threshold value α * , we equate the values of the α-fairness utility function evaluated at the maxmin fair point (1/n, ..., 1/n) and the corner point (1, 0, ..., 0). Namely, we need to solve the following equation with respect to α:

If n = 2, the boundary of the capacity region has an explicit form R

= 1 and the statement of the theorem for n = 2 follows immediately. If n > 2, we consider small perturbations around the maxmin fair point

and around the corner points

in order to conclude that we deal with isolated maxima. ⋄ Since the point p = (1/n, ..., 1/n) provides the maximal value to the Jain's fairness index, in the case of the nonconvex capacity region described by [START_REF] Facchinei | On generalized Nash games and variational inequalities[END_REF] the maxmin fairness coincides with the Jain's fairness in this example of multiple access channel with non convex capacity region.

The capacity of the slot-synchronized collision channel has been extended in [START_REF] Tinguely | The Collision Channel with Recovery[END_REF] to the case when a multiuser decoder is utilized at the receiver and the colliding messages can be recovered with probability q. This channel is referred to as recovery channel. The capacity of the n-user recovery channel with recovery probability q is the closure of all rate points (R 1 , R 2 , . . . , R n ) satisfying the following for all i = 1, . . . n :

where 0 ≤ p i ≤ 1.

In contrast to the previously investigated rate regions, the region (10) is neither convex, as the cases investigated in Section II and III, nor concave as for the collision channel without feedback. Examples of this capacity region are provided in [START_REF] Tinguely | The Collision Channel with Recovery[END_REF]. In the next theorem we characterize the α-fair rate allocations for the capacity region [START_REF] Marshall | Inequalities: Theory of Majorization and its Applications[END_REF].

Theorem IV.2. The α-fair rate allocation for the capacity region described by [START_REF] Marshall | Inequalities: Theory of Majorization and its Applications[END_REF] has three distinct cases with respect to the value of α:

• Case α > α * : The set S α + of the α-fair rate allocations contains the single point R 1 = . . . R n = q corresponding to the maxmin fair rate allocation. • Case: α < α * : The set S α -of the α-fair rate allocations contains n points corresponding to total rate optimization points, namely

The set S α * of the α-fair rate allocations contains contains n + 1 points. More specifically, S α * = S α + S α -. The threshold value α * is given by

Proof. We focus on the case q > 0 since for q = 0 the recovery channel reduces to the collision channel. All the extreme points for the optimization problem max

belonging to the rate region [START_REF] Marshall | Inequalities: Theory of Majorization and its Applications[END_REF] are obtained as solution of the KKT conditions for the Lagrangian

The points satisfying the KKT conditions belong to the union set S α -n i=0,i =1 K i where K i is the set of all distinct permutations of (q, . . . q i times , 0, . . . 0 n-i

). Potential maximum values for the utility function are reached in S α -where

1-α (the other sets correspond to obvious local maxima and minima). To determine the threshold value α * , we equate the values of the α-fairness utility function evaluated at S α -and S α + . Namely, α * is the solution of the following equation with respect to α:

⋄ With the allocation rate (q, q, . . . q) all users transmit continuously ignoring the presence of the interfering users and relying only on the multiuser decoding capabilities of the receiver. It could be surprising that there exists a single threshold for the parameter α which determines a transition from the set of the allocation rates S α-to the set S α+ while the points in K i are not α-fair allocations for any value of α. This phenomenon is due to system model adopted to describe the recovery channel. In fact, the recovery probability is assumed constant and independent of the number of colliding users. In practical systems the recovery probability q is a decreasing function of the system load, i.e. the number of active users in the system. Taking into account this aspect could induce a smoother transition from S α-to S α+ through the sets K i when the parameter α increases.

B. Implication on max-min fairness

Consider the utility region given in Figure 4. It has two points, A and B, which are both lexicographically maxima: the value of the smallest coordinate of any point in the region is maximized there; moreover among all points that maximize the smallest coordinate, points A and B also maximize the value of the largest coordinate. For the case where the achievable region is convex, lexicographic maxima are also maxmin fair. The region of Figure 4 however has no maxmin assignment! For example, at point A, any way to increase the assignment in the vertical axis direction results in a decrease in the assignment in the horizontal direction. We note that in this case the Jain's fair allocation is well defined (it is the intersection point of the central line pointed by (1/n, ..., 1/n) and the boundary of the capacity region) and is different from the lexicographic fair allocations.

The Figure 4 is taken from a rate region in interference channel with random access [START_REF] Simeone | A game-theoretic view on the interference channel with random access[END_REF]. To our knowledge, this is the first time that this phenomenon is identified in our context. A similar phenomenon has been discovered in the context of assignment of discrete objects, see [START_REF] Sarkar | Fair Bandwidth Allocation for Multicasting in Networks with Discrete Feasible Set[END_REF].

V. CONCLUSION

We have studied multiuser access channels in the context of non-cooperative games with correlated constraints. In the non-cooperative games with correlated constraints the actions available to one player depend on those used by the others. A typical feature in these games is that they often possess infinitely many equilibria. To select among the equilibria we have proposed to use the Normalized Nash equilibrium and different fairness concepts such as maxmin fairness, lexicographic fairness, α-fairness and Jain's fairness. We have considered three main types of multiuser access channels: polymatroid regions, convex non polytope regions, and non convex capacity regions. In the case of Gaussian multiple access channel (an example of a channel with polymatroid achievable rate region), the normalized Nash equilibrium and all fairness concepts select the same equilibrium. In the case of Gaussian multiple access orthogonal channel (an example of a channel with convex non-polytope achievable rate region) different fairness concepts can select different equilibria. We have characterized these equilibria. Finally, we have identified very interesting facts about channels with non-convex achievable rate regions. It turns out that in some channels with non-convex achievable rate regions the maxmin fair allocation might not even exist. An interesting future research direction is to study equilibria selection in the case of several base stations.


Walid Saad
email: saad@unik.no.

Zhu Han

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

Are Hjørungnes

Physical Layer Security: Coalitional Games for Distributed Cooperation

Cooperation between wireless network nodes is a promising technique for improving the physical layer security of wireless transmission, in terms of secrecy capacity, in the presence of multiple eavesdroppers. While existing physical layer security literature answered the question "what are the link-level secrecy capacity gains from cooperation?", this paper attempts to answer the question of "how to achieve those gains in a practical decentralized wireless network and in the presence of a secrecy capacity cost for information exchange?". For this purpose, we model the physical layer security cooperation problem as a coalitional game with non-transferable utility and propose a distributed algorithm for coalition formation. Through the proposed algorithm, the wireless users can autonomously cooperate and self-organize into disjoint independent coalitions, while maximizing their secrecy capacity taking into account the security costs during information exchange. We analyze the resulting coalitional structures, discuss their properties, and study how the users can self-adapt the network topology to environmental changes such as mobility. Simulation results show that the proposed algorithm allows the users to cooperate and self-organize while improving the average secrecy capacity per user up to 25.32% relative to the non-cooperative case.

I. INTRODUCTION

During the past decade, security in wireless networks has been mainly considered at higher layers using various techniques such as cryptography. However, with the emergence of ad hoc and decentralized networks [START_REF] Debbah | Mobile flexible networks: The challenges ahead[END_REF], [START_REF] Kauffmann | Measurement-based self organization of interfering 802.11 wireless access networks[END_REF], higher-layer techniques such as encryption are complex and hard to implement. Therefore, there has been a recent attention on studying the fundamental ability of the physical layer (PHY) to provide secure wireless communication. The main idea is to exploit the wireless channel PHY characteristics such as fading or noise for improving the reliability of wireless transmission. While these characteristics have always been seen as impairments, PHY layer security studies can utilize these characteristics for improving the security and reliability of wireless communication systems. This reliability is quantified by the secrecy capacity, which is defined as the maximum rate of secret information sent from a wireless node to its destination in the presence of eavesdroppers. The study of this security aspect began with the pioneering work of Wyner over the wire-tap channel [START_REF] Wyner | The wire-tap channel[END_REF] which showed that communicating data can be done in a secure manner without relying on any form of encryption such as secret keys. This work was followed up in [START_REF] Leung-Yan-Cheong | The Gaussian wiretap channel[END_REF], [START_REF] Csiszar | Broadcast channels with confidential messages[END_REF] for the scalar Gaussian wire-tap channel and the broadcast channel, respectively.

In recent years, there has been a growing interest in carrying out these studies unto the wireless and the multi-user channels [START_REF] Liang | Secure communication over fading channels[END_REF][START_REF] Gopala | On the secrecy capacity of fading channels[END_REF][START_REF] Liang | Multiple-access channels with confidential messages[END_REF][START_REF] Prada | Secrecy capacity of SIMO and slow fading channels[END_REF][START_REF] Dong | Secure wireless communications via cooperation[END_REF][START_REF] Li | Secret communication via multi-antenna transmission[END_REF]. For instance, in [START_REF] Liang | Secure communication over fading channels[END_REF] and [START_REF] Gopala | On the secrecy capacity of fading channels[END_REF], the authors study the secrecy capacity region for both the Gaussian and the fading broadcast channels and propose optimal power allocation strategies. In [START_REF] Liang | Multiple-access channels with confidential messages[END_REF], the secrecy level in multiple access channels from a linklevel perspective is studied. Further, multiple antenna systems have been proposed in [START_REF] Prada | Secrecy capacity of SIMO and slow fading channels[END_REF], [START_REF] Li | Secret communication via multi-antenna transmission[END_REF] for ensuring a non-zero secrecy capacity, notably when the channel between the source and the destination is worse than the channel between the source and the eavesdroppers. Due to the size limitations of mobile devices, cooperation has been recently investigated as a practical way to achieve the multiple antenna gains [START_REF] Jindal | Capacity of ad-hoc networks with node cooperation[END_REF]. In this context, the work in [START_REF] Dong | Secure wireless communications via cooperation[END_REF] investigates, through a two stage algorithm, the secrecy capacity gains (with no cost) resulting from the cooperation between a single cluster consisting of one source node and a number of relays. In this work, they investigate how a group of single antenna users can collaborate, by using beamforming (with no cost for cooperation), for improving their secrecy capacity. Briefly, the majority of the existing literature is devoted to the information theoretic analysis of link-level performance gains of secure communications with no information exchange cost, notably when a source node cooperate with some relays such as in [START_REF] Dong | Secure wireless communications via cooperation[END_REF]. No work seems to have investigated how a number of users, each with its own data, can interact and cooperate at network-wide level to improve their secrecy capacity and provide PHY security for their wireless transmission.

The main contribution of this work is to propose distributed cooperation strategies, through coalitional game theory, which allow to study the interactions between a network of users that seek to secure their communication through cooperation in the presence of multiple eavesdroppers. Another major contribution is to study the impact on the network topology and dynamics of the inherent trade off that exists between the PHY security cooperation gains in terms of secrecy capacity and the information exchange costs. In other words, while the earlier work answered the question "what are the secrecy capacity gains from cooperation?", here, we seek to answer the question of "how to achieve those gains in a practical decentralized wireless network and in the presence of a cost for information exchange?". We model the problem as a non-transferable coalitional game and propose a distributed algorithm for autonomous coalition formation based on well suited concepts from cooperative games. Through the proposed algorithm, each user autonomously decides to form or break a coalition for maximizing its utility in terms of secrecy capacity while accounting for the loss of secrecy capacity during information exchange. We show that independent disjoint coalitions form in the network, due to the cooperation cost, and we study their properties. Through simulations, we assess the performance of the proposed algorithm, investigate the network topology, and show how the users can self-organize and adapt the topology to mobility. Simulation results show that the proposed algorithm allows the users to cooperate and self-organize while improving the average secrecy capacity per user up to 25.32% relative to the non-cooperative case.

The rest of this paper is organized as follows: Section II presents the system model. Section III presents the game formulation and properties. In Section IV we devise the coalition formation algorithm. Simulation results are presented and analyzed in Section V. Finally, conclusions are drawn in Section VI.

II. SYSTEM MODEL

Consider a network having N transmitters (e.g. mobile users) sending data to M receivers (destinations) in the presence of K eavesdroppers that seek to tap into the transmission of the users. Users, receivers and eavesdroppers are unidirectional-singleantenna nodes. We define N = {1, . . . , N }, M = {1, . . . , M } and K = {1, . . . , K} as the sets of users, destinations, and eavesdroppers, respectively. In this work, we consider only the case of multiple eavesdroppers, hence, we have K > 1. Furthermore, let h i,mi denote the complex baseband channel gain between user i ∈ N and its destination m i ∈ M and g i,k denote the channel gain between user i ∈ N and eavesdropper k ∈ K. We consider a line of sight channel model with

h i,mi = d -µ 2 i
,mi e jφi,m i with d i,mi the distance between user i and its destination m i , µ the pathloss exponent, and φ i,mi the phase offset. A similar model is used for the user-eavesdropper channel.

For multiple access, we consider a TDMA transmission, whereby, in a non-cooperative manner, each user occupies a single time slot. Within a single slot, the maximum amount of reliable information transmitted from the user i occupying the slot to its destination m i is quantified through the secrecy capacity C i,mi defined as follows [START_REF] Liang | Secure communication over fading channels[END_REF]:

C i,mi = C d i,mi -max 1≤k≤K C e i,k + , (1)
where C d i,mi is the Shannon capacity for the transmission between user i and its destination m i ∈ M, C e i,k is the Shannon capacity of user i at the eavesdropper k ∈ K, and a + max (a, 0).

In a non-cooperative approach, due to the broadcast nature of the wireless channel, the transmission of the users can be overheard by the eavesdroppers which reduces their secrecy capacity as clearly expressed in [START_REF] Debbah | Mobile flexible networks: The challenges ahead[END_REF]. For improving their performance and increasing their secrecy capacity, the users can collaborate by forming cooperative groups known as coalitions. Within every coalition, the users can utilize collaborative beamforming techniques for improving their secrecy capacities. In this context, every user i belonging to a coalition S will use the cooperation protocol of [START_REF] Dong | Secure wireless communications via cooperation[END_REF] by dividing its slot into two durations:

1) In the first duration, user i broadcasts its information to the other members of coalition S. 2) In the second duration, coalitions S performs collaborative beamforming. In other words, all the members of coalition S relay a weighted version of user i's signal to its destination.

The objective of this cooperation is to null the signal at the eavesdroppers, i.e., impose C e i,k = 0, ∀k ∈ K, hence, improving the secrecy capacity in (1) [START_REF] Dong | Secure wireless communications via cooperation[END_REF]. Each coalition S ⊆ N that forms in the network is able to transmit within all the time slots previously held by its users. Thus, in the presence of cooperating coalitions, the TDMA system schedules one coalition per time slot. During a given slot, the coalition acts as a single entity for transmitting the data of the user that owns the slot. An illustration of this model is shown in Figure 1 for N = 9 users, M = 2 destinations, and K = 2 eavesdroppers.

Furthermore, we define a fixed transmit power per time slot P which constrains all the users that are transmitting within a given slot. In a non-cooperative manner, this power constraint applies to the single user occupying the slot, while in a cooperative manner this same power constraint applies to the entire coalition occupying the slot. Such a power assumption is typical in TDMA systems comprising mobile users and is a direct result of ergodicity and the time varying user locations [START_REF] Jindal | Capacity of ad-hoc networks with node cooperation[END_REF][START_REF] Vishwanathan | Downlink capacity evaluation of cellular networks with known interference cancellation[END_REF][START_REF] Saad | A distributed merge and split algorithm for fair cooperation in wireless networks[END_REF]. For every coalition S, during the time slot owned by user i ∈ S, user i utilizes a portion of the available power P for information exchange (first stage) while the remaining portion P S i is used by the coalition S to transmit the actual data to the destination m i of user i (second stage). For information exchange, user i ∈ S can broadcast its information to the farthest user î ∈ S, by doing so all the other members of S can also obtain the information due to the broadcast nature of the wireless channel. This information exchange incurs a power cost Pi, î given by

Pi, î = ν 0 • σ 2 q i, î , (2)
where ν 0 is a target average signal-to-noise ratio (SNR) for information exchange, σ 2 is the noise variance and q i, î = 1/d µ i, î

is the path loss between users i and î with d i, î the distance between them. The remaining power that coalition S utilizes for the transmission of the data of user i during the remaining time of this user's slot is

P S i = ( P -Pi, î) + (3)
For every coalition S, during the transmission of the data of user i to its destination, the coalition members can weigh their signals in a way to completely null the signal at the eavesdroppers. We define, for a coalition S, the |S| × 1 vectors

h S = [h i1,m1 , . . . , h i |S| ,m |S| ] H , g k S = [g i1,k , . . . , g i |S| ,k ] H
, and w S = [w i1 , . . . , w i |S| ] H which represent, respectively, the "userdestination" channels, "user-eavesdropper k" channels, and the signal weights. By nulling the signals at the eavesdropper through cooperation within coalition S, the secrecy capacity (1) achieved by user i ∈ S at its destination m i during user i's time slot becomes [10, Eq. ( 14)]

C S i,mi = 1 2 log 2 (1 + (w opt S ) H R S w opt S σ 2 ), (4)
where R S = h S h H S , σ 2 is the noise variance, and w opt S is the weight vector that maximizes the secrecy capacity while nulling the signal at the eavesdropper and is given in [START_REF] Dong | Secure wireless communications via cooperation[END_REF]Eq.(20)] by

w opt S = β S i G H S (G S G H S ) -1 e with G S = [h S , g 1 S , . . . , g K S ] H a (K + 1) × |S| matrix, β S i = P S i e H (GS G H S )
-1 e a scalar and e = [1, 0 1×K ] H a (K + 1) × 1 vector. In (4), the factor 1 2 accounts for the fact that half of the slot of user i is reserved for information exchange.

Having adequately presented the model for physical layer security, the remainder of this paper is devoted to investigate how a network of users can cooperate, through the protocol described in this section, and improve the security of their wireless transmission, i.e., their secrecy capacity.

III. PHYSICAL LAYER SECURITY AS A COALITIONAL GAME

In this section, we formulate the physical layer security model of the previous section as a coalitional game and we investigate its properties. For instance, the proposed PHY security problem is modeled as a coalitional game with a non-transferable utility defined as [START_REF] Myerson | Game Theory, Analysis of Conflict[END_REF]: Definition 1: A coalitional game with non-transferable utility is defined by a pair (N , V ) where N is the set of players and V is a mapping such that for every coalition S ⊆ N , V (S) is a closed convex subset of R |S| that contains the payoff vectors that players in S can achieve.

For the proposed physical layer security problem, given a coalition S and denoting by φ i (S) the payoff of user i ∈ S during its time slot, we define the coalitional value set, i.e., the mapping V as follows

V (S) = {φ(S) ∈ R |S| | ∀i ∈ S φ i (S) = (v i (S) -c i (S)) + if P S i > 0, and φ i (S) = -∞ otherwise.}, (5)
where v i (S) = C S i,mi is the gain in terms of secrecy capacity for user i ∈ S given by ( 4) while taking into account the available power P S i in (3) and c i (S) is a secrecy cost function that captures the loss for user i ∈ S, in terms of secrecy capacity, that occurs during information exchange. Note that, when all the power is spent for information exchange, the payoff φ i (S) of user i is set to -∞ since, in this case, the user has clearly no interest in cooperating.

With regard to the secrecy cost function c i (S), when a user i ∈ S sends its information to the farthest user î ∈ S using a power level Pi, î, the eavesdroppers can overhear the transmission. This security loss is quantified by the capacity at the eavesdroppers resulting from the information exchange and which, for a particular eavedropper k ∈ K, is given by

Ĉe i,k = 1 2 log (1 + Pi, î • |g i,k | 2 σ 2 ), (6)
Given this security loss, the cost function c(S) can be defined as

c i (S) = max ( Ĉe i,1 , . . . , Ĉe i,K ). (7)
In a nutshell, the proposed coalitional value defined in (5) considers the benefit from cooperation, in terms of improved secrecy capacity, while taking into account the costs in terms of reduced power for transmission due to the power fraction used for information exchange as well as the secrecy capacity loss due to the eavesdroppers overhearing the transmission of the users during the information exchange phase.

Subsequently, the proposed physical layer security cooperation problem can be easily formulated as a coalitional game with non-transferable utility as per the following property:

Property 1: Given the mapping V in (5), whenever the users transmit at their maximum rate (i.e. capacity), the proposed PHY security cooperation problem is a (N , V ) non-transferable utility coalitional game.

Proof: Immediate result from the fact that when the users transmit at their maximum rate, the mapping V (S) defined in ( 5) is a singleton set, and hence, closed and convex. Consequently, the proposed coalitional game model has a non-transferable utility V (S) expressed by [START_REF] Csiszar | Broadcast channels with confidential messages[END_REF] In general, coalitional game based problems seek to characterize the properties and stability of the grand coalition of all players since it is generally assumed that the grand coalition maximizes the utilities of the players [START_REF] Myerson | Game Theory, Analysis of Conflict[END_REF]. In our case, although cooperation improves the secrecy capacity for the users in the TDMA network; the costs in terms of:

1) The fraction of power spent for information exchange as per (3) and, 2) the secrecy loss during information exchange as per [START_REF] Gopala | On the secrecy capacity of fading channels[END_REF] strongly limit the cooperation gains. Therefore, for the proposed (N , v) coalitional game we have:

Property 2: For the proposed (N , V ) coalitional game, the grand coalition of all the users seldom forms due to the various costs for information exchange. Instead, disjoint independent coalitions will form in the network.

Proof: Given a number of users positioned at different location within the wireless network, cooperation for improving the secrecy capacity entails costs, as previously mentioned, in terms of secrecy loss and power loss during information exchange as per ( 2) and [START_REF] Gopala | On the secrecy capacity of fading channels[END_REF]. Hence, in a practical wireless network where the users are located at different positions, it is highly likely that, when they attempt to cooperate for forming the grand coalition N of all users, either: (i)-there exists a pair of users i, j ∈ N that are distant enough to require an information power cost of P hence they have no incentive to join the grand coalition, or (ii)-there exists a user i ∈ N with the payoff of i in the grand coalition φ i (N ) = 0 due to the secrecy loss as captured by [START_REF] Gopala | On the secrecy capacity of fading channels[END_REF], hence this user i has incentive to deviate from the grand coalitions. Clearly, by accounting for the various cooperation costs, the grand coalition of all users will seldom form (it only forms if all users are very close, which is unrealistic in a large scale wireless network) and hence, the network structure consists of disjoint independent coalitions.

Due to this property, traditional solution concepts for coalitional games, such as the core [START_REF] Myerson | Game Theory, Analysis of Conflict[END_REF], may not be applicable. In fact, in order for the core to exist, as a solution concept, a coalitional game must ensure the grand coalition, i.e., the coalition of all players will form. However, as seen in Figure 1 and corroborated by Property 2, in general, due to the cost for coalition formation, the grand coalition will not form. Instead, independent and disjoint coalitions appear in the network as a result of the collaborative beamforming process. In this regard, the proposed game is classified as a coalition formation game, and the objective is to find the coalitional structure that will form in the network, instead of finding only a solution concept, such as the core, which aims mainly at stabilizing the grand coalition.

Furthermore, for the proposed (N , V ) coalition formation game, a constraint on the coalition size, imposed by the nature of the cooperation protocol exists as follows:

Remark 1: For the proposed (N , V ) coalition formation game, the size of any coalition S ⊆ N that will form in the network must satisfy |S| > K.

This is a direct result of the fact that, for nulling K eavesdroppers, at least K + 1 users must cooperate, otherwise, no weight vector can be found to maximize (1) while nulling the signal at the eavesdroppers.

IV. DISTRIBUTED COALITION FORMATION ALGORITHM

A. Coalition Formation Algorithm

Coalition formation has been a topic of high interest in game theory [START_REF] Ray | A Game-Theoretic Perspective on Coalition Formation[END_REF][START_REF] Apt | Stable partitions in coalitional games[END_REF][START_REF] Apt | A generic approach to coalition formation[END_REF][START_REF]A generic approach to coalition formation (extended version)[END_REF]. The goal is to find algorithms for characterizing the coalitional structures that form in a network where the grand coalition is not optimal. For instance, using game theoretical techniques from coalition formation games, we devise an algorithm for distributed coalition formation algorithm in the proposed (N , V ) PHY security cooperative game. For constructing a coalition formation process suitable to the proposed game, we require the following definitions [START_REF] Apt | A generic approach to coalition formation[END_REF] Definition 2: A collection of coalitions, denoted by S, is defined as the set S = {S 1 , . . . , S l } of mutually disjoint coalitions S i ⊂ N . In other words, a collection is any arbitrary group of disjoint coalitions S i of N not necessarily spanning all players of N . If the collection spans all the players of N ; that is l j=1 S j = N , the collection is a partition of N . Definition 3: A preference operator or comparison relation is an order defined for comparing two collections R = {R 1 , . . . , R l } and S = {S 1 , . . . , S p } that are partitions of the same subset A ⊆ N (i.e. same players in R and S). Therefore, R S implies that the way R partitions A is preferred to the way S partitions A.

Various well known orders can be used as comparison relations in different scenarios [START_REF] Apt | A generic approach to coalition formation[END_REF], [START_REF]A generic approach to coalition formation (extended version)[END_REF]. These orders can be divided into two main categories: coalition value orders and individual value orders. Coalition value orders compare two collections (or partitions) using the value function of the coalitions inside these collections (suitable for games with transferable utilities) while individual value orders perform the comparison using the individual payoffs of every user. For the individual orders, two collections R and S are seen as two vectors of individual payoffs of the same length (corresponding to the total number of players) where each element of these payoff vectors corresponds to the utility received by the players in each coalition R i ∈ R and S i ∈ S. In this context, individual value orders are quite suitable for non-transferable utility games such as the proposed game. Hence, for the PHY security coalition formation game, we define the following individual order that will be used in the coalition formation algorithm Definition 4: Consider two collections R = {R 1 , . . . , R l } and S = {S 1 , . . . , S m } that are partitions of the same subset A ⊆ N (same players in R and S). For a collection R = {R 1 , . . . , R l }, let the utility of a player j in a coalition R j ∈ R be denoted by Φ j (R) = φ j (R j ) ∈ V (R j ). R is preferred over S by Pareto order, written as R S, iff R S ⇐⇒ {Φ j (R) ≥ Φ j (S) ∀ j ∈ R, S}, with at least one strict inequality (>) for a player k. In other words, a collection is preferred by the players over another collection, if at least one player is able to improve its payoff without hurting the other players. Subsequently, for performing autonomous coalition formation between the users in the proposed PHY security game, we construct a distributed algorithm based on two simple rules denoted as "merge" and "split" [START_REF] Apt | A generic approach to coalition formation[END_REF] defined as follows.

Definition 5: Merge Rule -Merge any set of coalitions {S 1 , . . . , S l } whenever the merged form is preferred by the players, i.e., where

{ l j=1 S j } {S 1 , . . . , S l },

Initial State

The network is partitioned by T = {T 1 , . . . , T k } (At the beginning of all time T = N = {1, . . . , N } with non-cooperative users).

Three phases in each round of the coalition formation algorithm

Phase 1 -Neighbor Discovery: a) Each coalition surveys its neighborhood for candidate partners. b) For every coalition T i , the candidate partners lie in the area represented by the intersection of |T i | circles with centers j ∈ T i and radii determined by the distance where the power for information exchange does not exceed P for any user (easily computed through (2)). Phase 2 -Adaptive Coalition Formation:

In this phase, coalition formation using merge-and-split occurs. Using the above rules, multiple coalitions can merge into a larger coalition if merging yields a preferred collection based on the Pareto order. This implies that a group of users can agree to form a larger coalition, if at least one of the users improves its payoff without decreasing the utilities of any of the other users. Similarly, an existing coalition can decide to split into smaller coalitions if splitting yields a preferred collection by Pareto order. The rationale behind these rules is that, once the users agree to sign a merge agreement, this agreement can only be broken if all the users approve. This is a family of coalition formation games known as coalition formation games with partially reversible agreements [START_REF] Ray | A Game-Theoretic Perspective on Coalition Formation[END_REF]. Using the rules of merge and split is highly suitable for the proposed PHY security game due to many reasons. For instance, each merge or split decision can be taken in a distributed manner by each individual user or by each already formed coalition. Further, it is shown in [START_REF] Apt | A generic approach to coalition formation[END_REF] that any arbitrary iteration of merge and split rules terminates, hence these rules can be used as building blocks in a coalition formation process for the PHY security game.

Accordingly, for the proposed PHY security game, we construct a coalition formation algorithm based on merge-and-split and divided into three phases: neighbor discovery, adaptive coalition formation, and transmission. In the neighbor discovery phase (Phase 1), each coalition (or user) surveys its environment in order to find possible cooperation candidates. For a coalition S k the area that is surveyed for discovery is the intersection of |S k | circles, centered at the coalition members with each circle's radius given by the maximum distance ri (for the circle centered at i ∈ S k ) within which the power cost for user i as given by ( 2) does not exceed the total available power P . This area is determined by the fact that, if a number of coalitions {S 1 , . . . , S m } attempt to merge into a new coalition G = ∪ m i=1 S i which contains a member i ∈ G such that the power for information exchange needed by i exceeds P , then the payoff of i goes to -∞ as per ( 5) and the Pareto order can never be verified. Clearly, as the number of users in a coalition increases, the number of circles increases, reducing the area where possible cooperation partners can be found. This implies that, as the size of a coalition grows, the possibility of adding new users decreases, and hence, the complexity of performing merge also decreases.

Following Phase 1, the adaptive coalition formation phase (Phase 2) begins, whereby the users interact for assessing whether to form new coalitions with their neighbors or whether to break their current coalition. For this purpose, an iteration of sequential merge-and-split rules occurs in the network, whereby each coalition decides to merge (or split) depending on the utility improvement that merging (or splitting) yields. Starting from an initial network partition T = {T 1 , . . . , T l } of N , any random coalition (individual user) can start with the merge process. The coalition T i ∈ T which debuts the merge process starts by enumerating, sequentially, the possible coalitions, of size greater than K (Remark 1), that it can form with the neighbors that were discovered in Phase 1. On one hand, if a new coalition Ti which is preferred by the users through Pareto order is identified, this coalition will form by a merge agreement of all its members. Hence, the merge ends by a final merged coalition T final i composed of T i and one or several of coalitions in its vicinity. On the other hand, if T i is unable to merge with any of the discovered partners, it ends its search and T final i = T i . The algorithm is repeated for the remaining T i ∈ T until all the coalitions have made their merge decisions, resulting in a final partition F. Following the merge process, the coalitions in the resulting partition F are next subject to split operations, if any is possible. In the proposed PHY security problem, the coalitions are only interested in splitting into structures that include either singleton users or coalitions of size larger than K or both (Remark 1). Similar to merge, the split is a local decision to each coalition. An iteration consisting of multiple successive merge-and-split operations is repeated until it terminates. The termination of an iteration of merge and split rules is guaranteed as shown in [START_REF] Apt | A generic approach to coalition formation[END_REF]. It must be stressed that the merge or split decisions can be taken in a distributed way by the users/coalitions without relying on any centralized entity.

In the final transmission phase (Phase 3), the coalitions exchange their information and begin their secure transmission towards their corresponding destinations, in a TDMA manner, one coalition per slot. Every slot is owned by a user who transmits its data with the help of its coalition partners, if that user belongs to a coalition. Hence, in this phase, the user perform the actual beamforming, while transmitting the data of every user within its corresponding slot. Each run of the proposed algorithm consists of these three phases, and is summarized in Table I. As time evolves and the users, eavesdroppers and destinations move (or new users or eavesdroppers enter/leave the network), the users can autonomously self-organize and adapt the network's topology through appropriate merge-and-split decisions during Phase 2. This adaptation to environmental changes is ensured by enabling the users to run the adaptive coalition formation phase periodically in the network.

The proposed algorithm in Table I can be implemented in a distributed manner. As the user can detect the strength of other users' uplink signals (through techniques similar to those used in the ad hoc routing discovery), nearby coalitions can be discovered in Phase 1. In fact, during Phase 1, each coalition in the network can easily work out the area within which candidates for merge can be found, as previously explained in this section. Once the neighbors are discovered, the coalitions can perform merge operations based on the Pareto order in Phase 2. Moreover, each formed coalition can also internally decides to split if its members find a split form by Pareto order. By using a control channel, the distributed users can exchange some channel information and then and then cooperate using our model (exchange data information if needed, form coalition then transmit). Note that, in this paper, we assume that the users have perfect knowledge of the channels to the eavesdroppers which is an assumption used in most PHY security related literature, and as explained in [START_REF] Dong | Secure wireless communications via cooperation[END_REF] this channel information can be obtained by the users through a constant monitoring of the behavior of the eavesdroppers.

B. Partition Stability

The result of the proposed algorithm in Table I is a network partition composed of disjoint independent coalitions. The stability of this network partition can be investigated using the concept of a defection function [START_REF] Apt | A generic approach to coalition formation[END_REF].

Definition 7: A defection function D is a function which associates with each partition T of N a group of collections in N . A partition T = {T 1 , . . . , T l } of N is D-stable if no group of players is interested in leaving T when the players who leave can only form the collections allowed by D.

We are interested in two defection functions [START_REF] Apt | Stable partitions in coalitional games[END_REF][START_REF] Apt | A generic approach to coalition formation[END_REF][START_REF]A generic approach to coalition formation (extended version)[END_REF]. First, the D hp function which associates with each partition T of N the group of all partitions of N that can form through merge or split and the D c function which associates with each partition T of N the group of all collections in N . This function allows any group of players to leave the partition T of N through any operation and create an arbitrary collection in N . Two forms of stability stem from these definitions: D hp stability and a stronger D c stability. A partition T is D hp -stable, if no player in T is interested in leaving T through merge-and-split to form other partitions in N ; while a partition T is D c -stable, if no player in T is interested in leaving T through any operation (not necessarily merge or split) to form other collections in N .

Hence, a partition is D hp -stable if no coalition has an incentive to split or merge. For instance, a partition T = {T 1 , . . . , T l } is D hp -stable, if the following two necessary and sufficient conditions are met [START_REF] Apt | A generic approach to coalition formation[END_REF], [START_REF] Apt | Stable partitions in coalitional games[END_REF] ( is the non-preference operator, opposite of ):

1) For each i ∈ {1, . . . , m} and for each partition {R 1 , . . . , R m } of T i ∈ T we have

{R 1 , . . . , R m } T i ; (8)
2) For each S ⊆ {1, . . . , l} we have

i∈S T i {T i |i ∈ S}, (9)
The above conditions are the generalized form (through the framework of [START_REF] Apt | A generic approach to coalition formation[END_REF]) of the D hp stability conditions presented in [START_REF] Apt | Stable partitions in coalitional games[END_REF]. Using this definition of D hp stability, we have Theorem 1: Every partition resulting from our proposed coalition formation algorithm is D hp -stable.

Proof: Consider a partition T resulting from the convergence of an iteration of merge-and-split operations such as in the algorithm of Table I, then no coalition in T can leave this partition through merge or split. For instance, assume T = {T 1 , . . . , T l } is the partition resulting from the proposed merge-and-split algorithm. If for any i ∈ {1, . . . , l} and for any partition {S 1 , . . . , S m } of T i we assume that {S 1 , . . . , S m } T i then the partition T can still be modified through the application of the split rule on T i contradicting with the fact that T resulted from a termination of the merge-and-split iteration; therefore {S 1 , . . . , S m } T i (first D hp stability condition verified). A similar reasoning is applicable in order to prove that T verifies the second condition; since otherwise a merge rule would still be applicable.

Furthermore, a D c -stable partition T is characterized by being a strongly stable partition, which satisfies the following properties:

1) A D c -stable partition is D hp -stable.

2) A D c -stable partition is a unique outcome of any iteration of merge-and-split. 3) A D c -stable partition T is a unique -maximal partition, that is for all partitions T = T of N , T T . In the case where represents the Pareto order, this implies that the D c -stable partition T is the partition that presents a Pareto optimal utility distribution for all the players. Clearly, it is desirable that the network self-organizes unto a D c -stable partition. However, the existence of a D c -stable partition is not always guaranteed [START_REF] Apt | A generic approach to coalition formation[END_REF]. The D c -stable partition T = {T 1 , . . . , T l } of the whole space N exists if a partition of N that verifies the following two necessary and sufficient conditions exists [START_REF] Apt | A generic approach to coalition formation[END_REF]:

1) For each i ∈ {1, . . . , l} and each pair of disjoint coalitions S 1 and S 2 such that {S 1 ∪ S 2 } ⊆ T i we have {S 1 ∪ S 2 } {S 1 , S 2 }. I converges to the optimal D c -stable partition, if such a partition exists. Otherwise, the final network partition is D hp -stable.

Proof: The proof is a consequence of Theorem 1 and the fact that the D c -stable partition is a unique outcome of any merge-and-split iteration [START_REF] Apt | A generic approach to coalition formation[END_REF] which is the case with any partition resulting from our algorithm.

Moreover, for the proposed game, the existence of the D cstable partition cannot be always guaranteed. For instance, for verifying the first condition for existence of the D c -stable partition, the users that are members of each coalitions must verify the Pareto order through their utility given by [START_REF] Csiszar | Broadcast channels with confidential messages[END_REF]. Similarly, for verifying the second condition of D c stability, users belonging to all T -incompatible coalitions in the network must verify the Pareto order. Consequently, the existence of such a D cstable partition is strongly dependent on the location of the users and eavesdroppers through the individual utilities (secrecy capacities). Hence, the existence of the D c -stable partition is closely tied to the location of the users and the eavesdroppers, which, in a practical ad hoc wireless network are generally random. However, the proposed algorithm will always guarantee convergence to this optimal D c -stable partition when it exists as stated in Lemma 1. Whenever a D c -stable partition does not exist, the coalition structure resulting from the proposed algorithm will be D hp -stable (no coalition or individual user is able to merge or split any further).

V. SIMULATION RESULTS AND ANALYSIS

For simulations, a square network of 2.5 km × 2.5 km is set up with the users, eavesdroppers, and destinations randomly deployed within this area 1 . In this network, the users are always assigned to the closest destination, although other user-destination assignments can be used without any loss of generality in the proposed coalition formation algorithm. The simulation parameters used are as follows. First, the power constraint per slot is P = 10 mW, the noise level is -90 dBm, and the SNR for information exchange is ν 0 = 10 dB which implies a neighbor discovery circle radius of 1 km per user. For the channel model, the propagation loss is set to α = 3.

In Figure 2, we show a snapshot of the network structure resulting from the proposed coalition formation algorithm for a randomly deployed network with N = 15 users, M = 2 destinations, and K = 2 eavesdroppers. This figure shows how the users self-organize into 6 coalitions with the size of each coalition larger than K or equal to 1. For example, Users 4 and 15, having no suitable partners for forming a coalition of size larger than 2, do not cooperate. The coalition formation process is a result of Pareto order agreements for merge (or split) between the users. For example, coalition {5, 8, 10, 13} formed since all the users agree on its formation due to the fact that V ({5, 8, 10, 13}) = {φ({5, 8, 10, 13}) = [0.356 0.8952 1.7235 0.6213]} which is a clear improvement on the non-cooperative utility which was 0 for all four users (due to proximity to eavesdropper 2). In a nutshell, this figure shows how the users can self-organize into disjoint independent coalition for improving the PHY security of their wireless transmission.

In Figure 3 we show how the algorithm handles mobility through appropriate coalition formation decisions. For this purpose, the network setup of Figure 2 is considered while User 12 is moving horizontally for 1.1 km in the direction of the negative x-axis. First of all, User 12 starts getting closer to its receiver (destination 2), and hence, it improves its utility. In the meantime, the utilities of User 12's partners (Users 3 and 11) drop due to the increasing cost. As long as the distance covered by User 12 is less than 0.2 km, the coalition of Users 1 and 6 can still bring mutual benefits to all three users. After that, splitting occurs by a mutual agreement and all three users transmit independently. When User 12 moves about 0.8 km, it begins to distance itself from its receiver and its utility begins to decrease. When the distance covered by User 12 reaches about 1 km, it will be beneficial to Users 12, 4, and 15 to form a 3-user coalition through the merge rule since they improve their utilities from φ 4 ({4}) = 0.2577, φ 12 ({12}) = 0.7638, and φ 15 ({15}) = 0 in a non-cooperative manner to V ({4, 12, 15}) = {φ({4, 12, 15}) = [1.7618 1.0169 0.6227]}.

In Figure 4 we show the performance, in terms of average utility (secrecy capacity) per user, as a function of the network size N . The results are averaged over the random positions of the users, eavesdroppers and destinations. For cooperation with coalitions, the average individual utility increases with the number of users. This is interpreted by the fact that as the number of users N increases, the probability of finding candidate partners to form coalitions with increases for every user. In contrast, for the non-cooperative approach an almost constant performance is noted. Finally, as easily seen in Figure 4 cooperation presents a clear performance advantage at all network sizes reaching up to 25.32% improvement of the average user utility (secrecy capacity) at N = 45.

VI. CONCLUSIONS

In this paper, we study the user behavior, topology, and dynamics of a network of users that interact in order to improve their secrecy capacity through cooperation. We formulate the problem as a non-transferable coalitional game, and propose a distributed and adaptive coalition formation algorithm. Through the proposed algorithm, the mobile users can autonomously take the decision to form or break cooperative coalitions through well suited rules from cooperative games while maximizing their secrecy capacity taking into account various costs for information exchange. We characterize the network structure resulting from the proposed algorithm, study its stability, and analyze the selfadaptation of the topology to environmental changes such as mobility. Simulation results show that the proposed algorithm allows the users to self-organize while improving the average secrecy capacity per user up to 25.32% relative to the noncooperative case.

Fig. 1 .

 1 Fig. 1. System Model for Physical Layer Security Coalitional Game.

  repeat a) F = Merge(T ); coalitions in T decide to merge based on the algorithm of Section IV-A. b) T = Split(F ); coalitions in F decide to split based on the Pareto order. until merge-and-split terminates. Phase 3 -Secure Transmission: Each coalition's users exchange their information and transmit their data within their allotted slots. The above three phases are repeated periodically during the network operation, allowing a topology that is adaptive to environmental changes such as mobility. therefore, {S 1 , . . . , S l } → { l j=1 S j }. Definition 6: Split Rule -Split any coalition l j=1 S j whenever a split form is preferred by the players, i.e., where {S 1 , . . . , S l } { l j=1 S j }, thus, { l j=1 S j } → {S 1 , . . . , S l }.

Fig. 2 . 1 :

 21 Fig.2. A snapshot of a coalitional structure resulting from our proposed coalition formation algorithm for a network with N = 15 users, M = 2 destinations and K = 2 eavedroppers.2) For the partitionT = {T 1 , . . . , T l } a coalition G ⊂ N formed of players belonging to different T i ∈ T is Tincompatible if for no i ∈ {1, . . . , l} we have G ⊂ T i .In summary, D c -stability requires that for all T -incompatible coalitions {G}[T ] {G} where {G}[T ] = {G ∩ T i ∀ i ∈ {1, . . . , l}} is the projection of coalition G on T . If no partition of N can satisfy these conditions, then no D c -stable partition of N exists. Nevertheless, we have Lemma 1: For the proposed (N , v) PHY security coalitional game, the proposed algorithm of TableIconverges to the optimal D c -stable partition, if such a partition exists. Otherwise, the final network partition is D hp -stable.Proof: The proof is a consequence of Theorem 1 and the fact that the D c -stable partition is a unique outcome of any merge-and-split iteration[START_REF] Apt | A generic approach to coalition formation[END_REF] which is the case with any partition resulting from our algorithm.Moreover, for the proposed game, the existence of the D cstable partition cannot be always guaranteed. For instance, for verifying the first condition for existence of the D c -stable partition, the users that are members of each coalitions must verify the Pareto order through their utility given by[START_REF] Csiszar | Broadcast channels with confidential messages[END_REF]. Similarly, for verifying the second condition of D c stability, users belonging to all T -incompatible coalitions in the network must verify the Pareto order. Consequently, the existence of such a D cstable partition is strongly dependent on the location of the users and eavesdroppers through the individual utilities (secrecy capacities). Hence, the existence of the D c -stable partition is closely tied to the location of the users and the eavesdroppers, which, in a practical ad hoc wireless network are generally random. However, the proposed algorithm will always guarantee convergence to this optimal D c -stable partition when it exists as stated in Lemma 1. Whenever a D c -stable partition does not exist, the coalition structure resulting from the proposed algorithm will be D hp -stable (no coalition or individual user is able to merge or split any further).

Fig. 3 .

 3 Fig.3. Self-adaptation of the network's topology to mobility as User 12 in Figure2moves horizontally on the negative x-axis.

Fig. 4 .

 4 Fig. 4. Performance in terms of the average individual user utility (secrecy capacity) as a function of the network size N for M = 2 destinations and K = 2 eavesdroppers.

This work was done during the stay of Walid Saad at the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign and was supported by the Research Council of Norway through projects 183311/S10, 176773/S10, and 18778/V11.

This general network setting simulates a broad range of network types ranging from ad hoc networks, to sensor networks, WLAN networks as well as broadband or cellular networks.