Sara Berri
email: sara.berri@l2s.centralesupelec.fr

Vineeth Varma

Samson Lasaulce
email: samson.lasaulce@l2s.centralesupelec.fr

Mohammed Said Radjef
email: radjefms@gmail.com

Jamal Daafouz
email: jamal.daafouz@univ-lorraine.fr

Studying Node Cooperation in Reputation Based Packet Forwarding within Mobile Ad hoc Networks

Keywords: Mobile ad hoc networks, Packet forwarding, Cooperation, Evolutionary game theory, ESS, Replicator dynamics

In the paradigm of mobile Ad hoc networks (MANET), forwarding packets originating from other nodes requires cooperation among nodes. However, as each node may not want to waste its energy, cooperative behavior can not be guaranteed. Therefore, it is necessary to implement some mechanism to avoid selfish behavior and to promote cooperation. In this paper, we propose a simple quid pro quo based reputation system, i.e., nodes that forward gain reputation, but lose more reputation if they do not forward packets from cooperative users (determined based on reputation), and lose less reputation when they chose to not forward packets from non-cooperative users. Under this framework, we model the behavior of users as an evolutionary game and provide conditions that result in cooperative behavior by studying the evolutionary stable states of the proposed game. Numerical analysis is provided to study the resulting equilibria and to illustrate how the proposed model performs compared to traditional models.

Introduction

A mobile ad hoc network (MANET) is a wireless multi-hop network formed by a set of mobile independent nodes. A key feature about MANETs is that they are self organizing and are without any established infrastructure. The absence of infrastructure implies that all networking functions, such as packet forwarding, must be performed by the nodes themselves [START_REF] Basagni | Mobile ad hoc networking[END_REF]. Thus, multi-hop communications rely on mutual cooperation among network's nodes. As the nodes of an ad hoc network have limited energy, the nodes may not want to waste their energy by forwarding packets from other nodes. If all the nodes are controlled by a central entity, this will not be a major issue as cooperation can be a part of the design, but in applications where each node corresponds to an individual user, it is crucial to develop mechanisms that promote cooperation among the nodes.

Several works in the literature provide solutions based on incentive mechanisms, such as those based on a credit concept [START_REF] Buttyán | Enforcing Service Availability in Mobile Ad-Hoc WANs[END_REF], [START_REF] Buttyán | Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks[END_REF], [START_REF] Krzesinski | Promoting Cooperation in Mobile Ad Hoc Networks[END_REF] etc., whose idea being that nodes pay for using some service and they are remunerated when they provide some service (like packet forwarding). Others like [START_REF] Jianl | HEAD: A Hybrid Mechanism to Enforce Node Cooperation in Mobile Ad Hoc Networks[END_REF], [START_REF] Li | Game-Theoretic Analysis of Cooperation Incentive Strategies in Mobile Ad Hoc Networks[END_REF] use reputationbased mechanisms to promote cooperation. Game theory has been a vital tool in literature to study the behavior of self-serving individuals in serval domains including MANETs. In [START_REF] Félegyházi | Game Theory in Wireless Networks: A Tutorial[END_REF], [START_REF] Félegyházi | Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks[END_REF], [START_REF] Jaramillo | A Game Theory Based Incentivize Cooperation in Wireless Ad hoc Networks[END_REF], etc. the interaction among nodes in packet forwarding is modeled as a one shot game based on prison's dilemma model, extended then to repeated game. Furthermore, evolutionary game theory is introduced in [START_REF] Seredynski | Evolutionary Game Theoretical Analysis of Reputation-based Packet Forwarding in Civilian Mobile Ad Hoc Networks[END_REF], [START_REF] Seredynski | Analysing the Development of Cooperation in MANETs using Evolutionary Game Theory[END_REF], [START_REF] Tang | When Reputation Enforces Evolutionary Cooperation in unreliable MANETs[END_REF], to study the dynamic evolution of system composed of nodes and to analyze how cooperation can be ensured in a natural manner. In [START_REF] Seredynski | Evolutionary Game Theoretical Analysis of Reputation-based Packet Forwarding in Civilian Mobile Ad Hoc Networks[END_REF] the evolutionary game theory is applied to study cooperation in packet forwarding in mobile ad hoc networks. Here, the authors used the prison's dilemmabased model [START_REF] Félegyházi | Game Theory in Wireless Networks: A Tutorial[END_REF] and the aim was to implement several strategies in the game and to evaluate performance, by observing their evolution over time.

The aforementioned works rely on incentive mechanisms, which has been proved to improve nodes cooperation. However, implementing such solutions often result in a large computational complexity during the game. We would like to find an answer to the following question, "Is it possible to achieve global cooperation in packet forwarding by a simple and natural way?". In this paper, we model the nodes interaction in a MANET as an evolutionary game by proposing a new formulation of the packet forwarding and reputation model. We introduce a simple reputation system with a quid pro quo basis, wherein, reputation is gained by forwarding packets and is lost when refusing to forward. However, a key feature is that the reputation loss depends on the packet source. If the packet is from a node with low reputation, less reputation is lost by not forwarding that packet. This simply means that selfish users will naturally have low reputation, while users are encouraged to help other cooperative users, resulting in a significantly different model from the likes of [START_REF] Seredynski | Evolutionary Game Theoretical Analysis of Reputation-based Packet Forwarding in Civilian Mobile Ad Hoc Networks[END_REF], [START_REF] Tang | When Reputation Enforces Evolutionary Cooperation in unreliable MANETs[END_REF] etc. With this model, we study two node classes, one which try to maintain a certain high reputation, and another class which disregard their reputation. We show that nodes are likely to cooperating by means of evolutionary game theory concepts and provide numerical results showing how the proposed model improves network performance. The novel reputation model we propose will naturally result in the cooperative users cooperating among each other and refusing to forward packets from selfish users, thereby eliminating the need for a third party to punish selfish behavior.

The remainder of the paper is structured as follows. In Sec. 2 we formulate the reputation and game models. We propose to analyze the evolutionary game in Sec. 3, by providing the associated equilibrium, and studying strategies evolution. This allows us to determine condition ensuring global cooperative behavior.

The numerical results are presented in Sec. [START_REF] Krzesinski | Promoting Cooperation in Mobile Ad Hoc Networks[END_REF]; it has to be noted that the results are the same for any game settings satisfying the provided conditions and not only for the given examples. Finally, Sec. 5 presents the conclusion.

Problem formulation and proposed game model

In this section, we provide a game model to study the packet forwarding interaction. We consider a packet forwarding game, where the players are the nodes, each of them can be cooperative, by forwarding other nodes' packets, or noncooperative, by dropping other nodes' packets. Thus, the players have to choose a strategy s i from the strategy set S={C, NC}. The actions C and NC mean cooperative and non-cooperative, respectively. The two player packet forwarding game can be defined in its strategic-form as following.

G (2) =< {1, 2}, {S i } i∈I , {u i } i∈I >, (1)
where:

• I = {1, 2} is the set of players (two players), that are the network nodes;

• S i is the set of pure strategies of player i ∈ I, which is the same for all the players, corresponding to S={C, NC}; • u i is the utility of player i ∈ I, that depends on its behavior and that of its opponent. To demonstrate the utility formulation, we consider the case of a pair of nodes from the network, within which a node may act as a sender and a relay (and vice versa). Thus, the players' utility can be represented by a payoff matrix as given by [START_REF] Buttyán | Enforcing Service Availability in Mobile Ad-Hoc WANs[END_REF].

A = C NC C λ -1 -1 NC λ 0 , (2)
where: λ > 0 is a coefficient representing the benefit associated to successfully sending a packet while spending a unit of energy. The first player actions are along the rows and the second players along the columns. Naturally, when λ < 1 no nodes are motivated to cooperate as the energy cost relative to the gain from having packets relayed is too high. In the interesting case (the case where a MANET framework is feasible) of λ > 1, the outcome of the proposed game can be characterized by the well-known Nash Equilibrium (NE), which is the strategy profile from which no player has interest in changing unilaterally its strategy.

The resulting strategy profile is beneficial for players when they act individually. However, the NE of the packet forwarding game is inefficient, corresponding to drop all the time, and provides for players 0 as utility. Thus, to overcome this problem we propose to add to the game (1) a reputation model, that defines the reward and the cost in terms of reputation according to the node decision, cooperative or non-cooperative. On the other hand, it would be better to model the interactions among all the N nodes and not just the two-player case. To deal with this, we propose to introduce evolutionary game theory, where the dynamical evolution of game strategies is studied through pairwise interactions.

In the following section, we provide the reputation model we propose, and construct the new packet forwarding game including the reputation mechanism as an integrated system. That means the game is played taking into account the reputation, which we show can be interpreted as a constraint on the strategy space, while the nodes aim to maximize their utility function.

Reputation model

We assume that there is a reputation system introduced in order to discourage selfish behavior and reward cooperative behavior by separating these two classes of nodes. The reputation system is represented as a function depending on the own action and the opponent's action. The reputation increases by a certain margin δ r whenever a node relays the packet from another node, chooses C as action. Reputation is lost whenever a node refuses to relay a packet, by choosing NC as action. However, the loss of reputation from refusing to relay the packet from a node with low reputation δ b is smaller than the loss incurred by refusing to relay the packet from a well reputed node δ g . For ease of notation the reputation of a user i ∈ I is given by R i (t), and if R i (t) > 0 the node has a good reputation and otherwise bad reputation. The change in reputation is given by:

R i (t + 1) = R i (t) + d i (t)δ r -(1 -d i (t))(δ g 1(R j > 0) + δ b 1(R j ≤ 0)), (3)
where: d i (t) ∈ {0, 1} is the decision to relay or not at time t. 0 corresponds to the action NC, and 1 to C. j is a random variable indicating the sender requesting i to relay. 1 is the indicator function, it is one when the condition inside the brackets is satisfied and 0 otherwise. We consider two primary classes of nodes based on their reputation value. The set H of "Hawks" who are selfish (non-cooperative) and don't care about reputation. As a result these nodes never relay packets, i.e., s i =NC ∀i ∈ H, but use the network and try to make the other nodes relay their packets, and so we have R i (t) < 0 ∀i ∈ H. These nodes will always have d i (t) = 0 for all t and therefore will also have a low reputation.

The other class of nodes are the set D of "Doves", who try to maintain a positive reputation. These nodes will have a strategy s such that on average their reputation gain is positive. Let us denote the dove population share (fraction of users who are in the dove class) by p. The population share of hawks will simply be given by 1 -p.

Utility maximization

In this subsection, we present how reputation system is integrated in the packet forwarding game in order to improve game outcomes and avoiding the noncooperative situation. As even the doves do not want to waste energy, they will not attempt to transmit ever single packet, but only such that their average reputation gain is at least 0 (reputation must be an increasing function). We assume that even a cooperative node, i.e., the Dove class, does not relay packets all the time. The doves have a mixed strategy to relay messages, and it relays messages from other doves with probability s d , and from hawks with a probability s h , i.e., the action C is chosen with different probabilities depending on the opponent's class.

As a result, the net utility is given by the number of times their packets get forward subtracted by the energy cost paid is given by them. The expected payoff of doves is given by the formula (4).

U (D, p) = (λ -1)ps d -s h (1 -p). (4)
This must be maximized over s d , s h while maintaining a positive reputation, i.e.,

E[R i (t + 1) -R i (t)] ≥ 0 or p(s d δ r -(1 -s d )δ g ) + (1 -p)(s h δ r -(1 -s h )δ b ) ≥ 0. ( 5
)
Therefore for a given population share of doves p, we can find the strategy of doves by solving the following optimization problem. max

s d ,s h U (D, p) p(s d δ r -(1 -s d )δ g ) + (1 -p)(s h δ r -(1 -s h )δ b ) ≥ 0 0 ≤ s d ≤ 1, 0 ≤ s h ≤ 1. (6)
Hawks have the same utility function, but don't have a reputation constraint, therefore, the corresponding expected payoff is given by the formula [START_REF] Félegyházi | Game Theory in Wireless Networks: A Tutorial[END_REF].

U (H, p) = λps h . (7)
Thus, the expected payoff of any individual is given by (8):

U (p, p) = pU (D, p) + (1 -p)U (H, p), (8)
where p is the population profile. If λ > 1, U (D, p) is maximized trivially by choosing s d = 1. Therefore, s h will be the smallest such that constraint (5) holds.

p(s d δ r -(1 -s d )δ g ) + (1 -p)(s h δ r -(1 -s h )δ b ) ≥ 0 ⇒ pδ r + (1 -p)(s h δ r -(1 -s h )δ b ) ≥ 0 ⇒ pδ r + (1 -p)(s h (δ r + δ b ) -δ b ) ≥ 0 ⇒ s h ≥ (1-p)δ b -pδr (δ b +δr)(1-p)
. Thus, we have:

s h = max (1 -p)δ b -pδ r (δ b + δ r )(1 -p) , 0 . (9)
Note that the introduction of s h < 1 is one of the main novelties of this paper, which can be different from s h = 1 as defined in the traditional forwarding game payoff [START_REF] Félegyházi | Game Theory in Wireless Networks: A Tutorial[END_REF], [START_REF] Félegyházi | Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks[END_REF], [START_REF] Jaramillo | A Game Theory Based Incentivize Cooperation in Wireless Ad hoc Networks[END_REF], [START_REF] Seredynski | Evolutionary Game Theoretical Analysis of Reputation-based Packet Forwarding in Civilian Mobile Ad Hoc Networks[END_REF], [START_REF] Tang | When Reputation Enforces Evolutionary Cooperation in unreliable MANETs[END_REF], etc. where the cooperative nodes forward packet all the time without making distinction among the opponent nodes that can be cooperative, belonging to D, or non-cooperative, belonging to H. Furthermore, the proposed reputation system is simpler and can be defined as a constraint when nodes take decision purely based on the reputation class of the packet source node.

Evolutionary game formulation

We can formally define the resulting evolutionary game with the strategic form

G =< {D, H}, {(s d , s h )} × {0}, p ∈ [0, 1], {u c } c∈{D,H} >, (10)
where:

• {D, H} are the reputation classes (or population types); • {(s d , s h )} is the set of strategies playable by D, with always playing 0 or NC strategy; • p is the population share of class D; • u c is the utility of class D or H as defined in ( 4) and [START_REF] Félegyházi | Game Theory in Wireless Networks: A Tutorial[END_REF].

Our objective in the following section is to study the evolution of strategies in this game, and analyze possible equilibrium points.

Evolutionary game analysis

Evolutionary game theory study the dynamic evolution of a given population based on two main concepts: evolutionary stable strategy (ESS) and replicator dynamics. Let p the initial population profile. We assume that a proportion ε of this population plays according to another profile q (population of mutants), while the other individuals keep their initial behavior p. Thus, the new population profile is (1 -ε)p + εq. The expected payoff of a player that plays according to p is U (p, (1 -ε)p + εq), and it is equal to U (q, (1 -ε)p + εq) for the one playing according to q.

Definition 1 [START_REF] Smith | The Logic of Animal Conflict[END_REF] A strategy p ∈ ∆ is an evolutionary stable strategy (ESS), if : ∀q ∈ ∆, ∃ ε = ε(q) ∈ (0, 1), ∀ε ∈ (0, ε)

U (p, (1 -ε)p + εq) > U (q, (1 -ε)p + εq), (11)
ε is called invasion barrier of the strategy p, which may depend on q.

The replicator dynamics is the process that specifies how a population is distributed over the pure strategies set in a game evolving in time.

Definition 2 (Replicator dynamics). The replicator dynamics is given by ( 12) [START_REF] Jonker | Evolutionary Stable Strategies and Game Dynamics[END_REF]:

ṗi = p i [U (i, p) - |S| j=1 p j U (j, p)], i ∈ {1, . . . , |S|}. (12)
The system [START_REF] Tang | When Reputation Enforces Evolutionary Cooperation in unreliable MANETs[END_REF] describes the replication process in continuous time. It gives the percentage of individuals newly playing strategy s i in the next period, it depends on the initial value p i (t 0 ). Using the relation [START_REF] Tang | When Reputation Enforces Evolutionary Cooperation in unreliable MANETs[END_REF], the replicator dynamics of the proposed game is:

ṗ = p(1 -p)(p(λ -1)(1 -s h ) -s h ). ( 13
)
For the evolutionary game G, we have the following results.

Theorem 1. When λ > 1, the evolutionary game G admits exactly two ESS at p = 0 with an invasion barrier ε = min

δ b δrq(λ-1)
, 1 , and p = 1 with an invasion barrier ε = 1. When the initial configuration is such that p < p T , the replicator dynamics takes the system to p = 0 and when p > p T , the replicator dynamics takes the system to p = 1 with

p T = δ b δ b + λδ r corresponding to the mixed NE.
Proof. First, we can easily verify that p T corresponds to a mixed NE by noticing that the utilities of H and D classes are identical at this point. Next, we use the definition 1, to prove the results stated in Theorem 1 corresponding to the invasion barrier. Let x = (1 -ε)p + εq, and Ū = U (p, x) -U (q, x). U (p, x) and U (q, x) are defined using the relation [START_REF] Félegyházi | Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks[END_REF].

Ū = p(x(λ -1) -s h (1 -x)) + (1 -p)(λxs h ) -q(x(λ -1) -s h (1 -x)) -(1 -q)(λxs h ) = (p -q)(x(λ -1) -s h (1 -x)) -(p -q)(λxs h ) = (p -q)(x(λ -1)(1 -s h ) -s h ). ( 14
)
1. In the first case, p = 0, this gives s h = δ b δ b +δr . We can solve for the condition when

Ū > 0 ⇒ -q(εq(λ -1)(1 -s h ) -s h ) > 0 ⇒ (-εq(λ -1)(1 -s h ) + s h ) > 0 ⇒ (-εq(λ -1)δ r + δ b ) > 0 ⇒ ε < δ b δ r q(λ -1) . (15)
Thus, from the definition 1 we conclude that p = 0 is an ESS with ε = min δ b δrq(λ-1) , 1 as an invasion barrier. Note that p = 0 is an ESS only if the population share of D decreases, and that of H increases, i.e., the replicator dynamics is negative or ṗi < 0. If s h = s h , ṗ < 0 gives the following result:

ṗ < 0 ⇒ p(1 -p)(p(λ -1) - (1 -p)δ b -pδ r (δ b + δ r )(1 -p) (p(λ -1) + 1)) < 0 ⇒ p((δ b + δ r λ)p -δ b ) δ b + δ r < 0 ⇒ p < p T (16)
2. Now we prove that p = 1 is an ESS. In this case s h = 0. Thus, the following result:

Ū = (1 -ε(1 -q))(λ -1),
we have λ > 1 ⇒ Ū > 0. This implies, according to definition 1, that p = 1 is an ESS ε = 1 as an invasion barrier. This occurs if ṗ > 0, i.e., when:

p((δ b + δ r λ)p -δ b ) δ b + δ r > 0 ⇒ > δ b δ b + δ r = p T (17)
4 Numerical analysis

In this section, we present numerical application of the proposed evolutionary game including a reputation system. All the results are based on the replicator dynamics which describes how the population evolves, and allows one to determine others performance metrics such as expected utility of players and the number of forwarded packets.

We study the effect of the proposed reputation model on the evolutionary stable strategy of the game. Fig. 1 presents the results, we consider two scenarios: 1) The curve in solid line corresponds to results provided by the proposed game model including a reputation system, and assuming that the cooperative nodes forward packets of non-cooperative nodes with some probability s h . 2) The curve in dashed line corresponds to results provided by putting s h = 1, meaning that cooperative nodes forward all the time, which corresponds to the previous packet forwarding game introduced in [START_REF] Félegyházi | Game Theory in Wireless Networks: A Tutorial[END_REF], [START_REF] Félegyházi | Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks[END_REF], [START_REF] Jaramillo | A Game Theory Based Incentivize Cooperation in Wireless Ad hoc Networks[END_REF], [START_REF] Seredynski | Evolutionary Game Theoretical Analysis of Reputation-based Packet Forwarding in Civilian Mobile Ad Hoc Networks[END_REF], etc. It is seen that using our new formulation, which integrates a reputation mechanism as a constraint, the system could converge towards a cooperative state, by carefully choosing the game settings. Thus, global cooperation could be guaranteed after a given time. Whereas, when the game does not include the reputation constraint, the population converges to the strategy non-cooperation, which is the unique evolutionary stable strategy of the game, regardless of the initial condition and game settings.

The results given by the Figure 1 can be used to characterize the expected utility of players. Fig. 2 presents the results of both cases s h = s h and s h = 1. From these figures, we observe that the utilities evolve over time in the same way that the proportion of the considered population, corresponding to D in that case. Thus, the proposed model provides better results, it promotes cooperation among nodes. Indeed, in order to show the influence level of these results on network performance, we consider a network composed of 50 nodes, randomly placed in surface of 1000m × 1000m, with a transmission range equals to 150m, and plot normalized number of forwarded packets within a network, using the proposed game model with constraint, and that introduced in previous works [START_REF] Félegyházi | Game Theory in Wireless Networks: A Tutorial[END_REF], [START_REF] Félegyházi | Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks[END_REF], [START_REF] Jaramillo | A Game Theory Based Incentivize Cooperation in Wireless Ad hoc Networks[END_REF], [START_REF] Seredynski | Evolutionary Game Theoretical Analysis of Reputation-based Packet Forwarding in Civilian Mobile Ad Hoc Networks[END_REF], etc. defined without any constraint and assuming that the cooperative nodes forward all the time, i.e., s h = 1. We assume that all the nodes need to send 10 packets to a given destination. Fig. 3 represents the results for the following game settings: λ = 3, δ r = 3 and δ b = 1. It clearly shows a direct influence, because the number of forwarded packets is strongly linked to the cooperative nodes proportion in packet forwarding.

Remark: While setting δ b = 0 can indeed make p = 1 the only ESS, this may not be a suitable reputation model for the MANET framework due to several reasons. Firstly, setting δ b = 0 will completely discourage D from forwarding packets from H class, which may also include new users to the MANET, thereby discouraging new users as they might be unable to send their packets without increasing their reputation. Secondly, note that D may not always forward packets from D as in practice the channel conditions between the nodes also play a big role in determining the resource cost and therefore the utility gained by forwarding (which we have not accounted for in this work). Accounting for channel fading due to path loss or small-scale fading will therefore, be a relevant extension of this work. These considerations show that reputation model parameters must be carefully designed in practice.

The contribution of this paper is to propose a the packet forwarding game [START_REF] Félegyházi | Game Theory in Wireless Networks: A Tutorial[END_REF], introducing a reputation system, which modifies reputation based on the reputation class of the packet source, i.e., cooperative or noncooperative. The aim is to motivate node cooperation using a simple and efficient mechanism. As a smaller reputation is lost by not forwarding packets from selfish users (classified by the reputation system), cooperative users will effectively forward the packets from other cooperative users and may avoid forwarding packets from selfish users. Effectively, we have demonstrated using evolutionary game theory concepts that, global cooperation in the network can be achieved under some conditions we stated related to the game settings with a low computational complexity. Finally, through simulations, we have shown that in terms of the number of forwarded packets in the MANET, the proposed game model provides significant gains over the game model where the cooperative nodes forward packet regardless of the opponent's behavior. As an extension of the present work, we propose to study the multi-hop case, where the interaction involves more than two players. Another relevant extension would be to account for channel fluctuations and the resulting utility function which might result in the cooperative class users forwarding packets from selfish users and not another cooperative user despite the reputation losses, due the channel conditions being favorable.

1 Fig. 1 .

 11 Fig. 1. Evolutionary dynamics of the Doves, nodes that play the strategy 'Cooperation' with a proability s * h in the proposed game model, and previous packet forwarding game model where s h = 1. We plot for several initial frequency values.

1 Fig. 2 .

 12 Fig. 2. The expected utility of D in the proposed game previous packet game model, where s h = 1. We plot for several initial frequency values 0.7 and 0.3.

1 Fig. 3 .

 13 Fig. 3. Normalized number of forwarded packets for an Ad hoc network of 50 nodes, in the proposed game model and previous packet forwarding game model, where s h = 1. We plot for two initial frequency values 0.7 and 0.3.

The present work is supported by the LIA project between CRAN, Lorea and the International University of Rabat.


Daniel Bonilla Licea
email: dbonillalicea85@gmail.com

Vineeth S Varma

Samson Lasaulce
email: samson.lasaulce@l2s.centralesupelec.fr

Jamal Daafouz
email: daafouz6@univ-lorraine.fr

Mounir Ghogho
email: mounir.ghogho@uir.ac.ma

Des Mclernon
email: d.c.mclernon@leeds.ac.uk

Robust trajectory planning for robotic communications under fading channels

come

Introduction

Traditionally in wireless literature, the trajectory of the mobile node is assumed to be an exogenous variable and the communication resources are optimized based only on the wireless parameters. However, we have seen an emergence of new technology like unmanned aerial or ground vehicles, drones and mobile robots which have communication objectives in addition to their destination or motion based objectives [START_REF] Licea | Trajectory planning for energy-efficient vehicles with communications constraints[END_REF]. Several works [START_REF] Ooi | Minimal energy path planning for wireless robots[END_REF] have studied trajectory optimization problems when the communication constraint is that of having a target SNR. However, we are interested in the case where the communication requirement is downloading a certain number of bits within a given time.

Previously, we have studied the problem where a mobile robot (MR) must download (or upload) a given amount of data from an access point and also reach a certain destination within a given time period in [START_REF] Licea | Trajectory planning for energy-efficient vehicles with communications constraints[END_REF]. However, in [START_REF] Licea | Trajectory planning for energy-efficient vehicles with communications constraints[END_REF], we did not account for wireless channel fading and in fact assumed that the wireless signal strength is determined purely based on the path loss. In this work, we want to relax this strong assumption and account for small-scale fading and shadowing effects. In this article we will show how to design offline a robust reference trajectory under limited amount of information and high uncertainty about the wireless channel. This trajectory will allow the MR to reach the goal point and completely transmit the content of its buffer to the access point (AP) with a sufficiently high probability.

In practice, this reference trajectory will be preloaded on the MR prior to the execution on the task and it will serve the MR as guide which may need to be slightly modified according to the wireless channel measurements collected by the MR while executing its task. This adaptation mechanism is outside the scope of this article and we will only focus on the design of the reference trajectory. Future works will address the online adaptation mechanism. The main contributions of this paper are as follows.

-Trajectory planning of a MR starting from an arbitrary point, which must reach a certain target point and download a certain number of bits from a nearby access point. -Optimization of the trajectory to minimize a cost function which depends on the amount of data left in the buffer to be downloaded and the energy consumed. -Considering a robust cost function which accounts for the random fluctuations of the wireless channel due to small-scale fading and shadowing effects.

Note that the first two contributions were also provided in [START_REF] Licea | Trajectory planning for energy-efficient vehicles with communications constraints[END_REF] for the much more simpler case in which only path-loss is assumed to determine the wireless signal. The rest of the paper is structured in the following manner. We provide the model for the wireless communication system and the robot motion in Section 2. We then provide the problem statement in Section 3 and provide a solution concept in Section 4. Finally, we provide numerical simulations in Section 5.

System Model

The position of the MR is given by p(t) ∈ R 2 , at any time t ∈ R ≥0 . We assume that the robot starts at position s, i.e. p(0) = s. The MR and the AP communicate with a frame duration T during which the channel fading is assumed to be a constant, i.e we assume a block fading model. The robot has a buffer with state b(k) ∈ Z ≥0 denoting the number of bits it must transmit at the discretized time k = t T . The initial buffer size is the total file size and is assume to be given by N , i.e., b(0) = N . The robot is equipped with a wireless system to communicate with an access point at p AP satisfying the following properties.

Communications system

The MR will move among dynamic scatterers and the bandwidth used for the communication will be lower than the coherence bandwidth. As a consequence the wireless channel between the MR and the access point (AP) will experience time-varying and flat multipath (small scale) fading as well as shadowing (large-scale fading). With loss of generality, we assume, from now on, that the communication problem consists in uploading data from the MR to the AP. The signal received by the AP at time t can be written as

y AP (t, p(t)) = h(p(t), t)s(p(t)) p(t) -p AP α/2 2 x(t) + n AP (t), (1)
where p AP is the location of the AP, h(p(t), t) represents the time-varying smallscale fading which we assume to be Nakagami distributed and s(p(t)) represents the shadowing term which we assume to be lognormal distributed [START_REF] Cai | A Two-Dimensional Channel Simulation Model for Shadowing Processes[END_REF]. Nakagami fading is well suited to model the behavior of the multipath fading in many practical scenarios [START_REF] Simon | Digital Communications over Fading Channels[END_REF]. Without loss of generality we assume E[|h(p(t))| 2 ] = 1 and so the p.d.f. of |h(p(t))| becomes

f h (z, m) = 2m m Γ (m) z 2m-1 exp -mz 2 , ( 2
)
where m is the shape factor of the Nakagami distribution. As mentioned before, the shadowing term s(p(t)) is lognormal distributed and so we have log (s(p(t))) ∼ N 0, σ 2 s with σ 2 s being the its variance. Also, the normalized spatial correlation of the shadowing is

r(p, q) = exp - p -q 2 β , (3)
where β is the decorrelation distance which will be unknown to the MR prior to the execution of the trajectory. Now, the coefficient α in (1) is the power path loss coefficient which usually takes values between 2 and 6 depending on the environment; x(t) is the signal transmitted by the robot with average power E[|x(t)| 2 ] = P and n AP (t) ∼ CN (0, σ 2 n ) is the zero mean additive white Gaussian (AWGN) noise at the AP's receiver. From [START_REF] Licea | Trajectory planning for energy-efficient vehicles with communications constraints[END_REF] we have that the signal-to-noise ratio (SNR) at the AP (in dB) is:

Γ dB (p(t)) = 10 log 10 P σ 2 n + 20 log 10 (s(p(t))) + 20 log 10 (|h(p(t), t)|) -10α log 10 ( p(t) -p AP 2 ) . (4)
As a result, the number of bits in the MR's buffer is given by:

b(k) =     N - k j=0 R Γ (p(jT ))     + (5)
where and a + = a for a > 0 and a + = 0 for a ≤ 0; Γ (p(jT )) is the estimate of Γ (p(jT )) which is Γ dB (p(jT )) in linear scale, N is the initial number of bits in the buffer and R Γ (p(kT )) is the number of bits in the payload of the packet transmitted during the duplexing period k. As mentioned above, the number R Γ (p(kT )) of bits transmitted in the payload is computed by the MR according to its most recent SNR estimate. So we have (for b(k) = 0):

R Γ = R j , ∀ Γ ∈ [η j , η j+1 ), j = 0, 1, • • • , J (6)
with R j < R j+1 , η j < η j+1 , R 0 = 0, η 0 = 0 and η 1 must be above the sensitivity of the AP's receiver.

Mobile robot

We assume the MR to be omnidirectional and its velocity is assumed to be controlled directly. This results in its motion described by

ṗ(t) = u(t), (7)
where p(t) is the MR position at time t and u(t) is the control input which is bounded by:

u(t) 2 ≤ u max , (8)
Finally, the mechanical energy spent by the MR between t 0 and t 1 while using the control signal u(t) is:

E mechanical (t 0 , t 1 , u) = m t1 t0 u(t) 2 dt. ( 9
)
where m is the mass of the MR.

Problem statement

The objective of the robot is to depart from a starting point s to a goal point g within a time t f and transmit the all the content from its buffer to the AP. The desired trajectory is such that it consumes little mechanical energy from the robot and also allows the robot the transmit all the content of the buffer quickly. In addition we want that when the MR follows this trajectory it succeeds in emptying its buffer with a high probability.

We assume that the only knowledge available to the MR (and the designer) about the environment (prior to the execution of the trajectory) is the position of the starting and goal points (i.e., s and g); an estimate of the path loss coefficient α, but we assume no knowledge about the severity of the small-scale fading (i.e., about the shaping factor m in (2)). Solving the general problem with no approximation is very hard due to the large amount of stochastic perturbations, the shadowing correlation and the large number of terms in the sum of [START_REF] Malmirchegini | On the Spatial Predictability of Communication Channels[END_REF]. This results in a very complicated expression for the probability of the buffer to be empty at t f . Therefore, we look at the most likely buffer state given by b

(k) =     N - k j=0 R (Γ (p(jT )))     + (10) where R (Γ (p(jT ))) is the statistical mode of R (Γ (p(jT ))), i.e., R (Γ (p(kT ))) = max argmax R∈{Rj } J j=0 Pr (R (Γ (p(kT ))) = R) . ( 11
)
This results in the following optimization problem

minimize u θ 1 tf 0 u(t) 2 2 u 2 max dt + θ 2 t f T k=0 T b(k) N s.t. ṗ(t) = u(t) u(t) 2 ≤ u max , p(0) = s, p(t f ) = g, t f T k=0 R (Γ (p(kT ))) ≥ r R N. (12)
The optimization target is a convex combination of the energy spent in motion by the robot (9) and of a second term which estimates how quickly the buffer is emptied. This second term is a sum over the most likely number of bits left in the buffer at time instant t = kT (i.e., E [b(k)]). The coefficients {θ k } 2 k=1 of the convex combination determine the relative importance of each optimization criterion.

Note that due to the stochastic nature of the channel we can not ensure that when the MR follows the reference trajectory it will always be able to empty its buffer but we can ensure that this happens with a certain probability. As calculating the actual probability of failing to meet the communication requirement constitutes a very hard task as explained above, we introduce r R ≥ 1 which is an overestimation parameter selected by the designer. The final constraint in (12) ensures that the sum of the statistical mode of the bits transmitted in the payload over all the trajectory is equal to an overestimation of the initial number of bits in the buffer, i.e., r R N . So when the trajectory is actually executed, the probability that the buffer will be emptied will be high and by increasing the overestimation parameter r R we can reduce the probability of the MR failing to empty its buffer when it reaches the goal point g. The term b(t) is a discreet and deterministic function of the MR's position. This difference makes the problem much more feasible to solve. Now, to solve the optimization problem (12) we first define the region A j as:

A j = {p | R (Γ (p)) = R j }. ( 13
)
Due to the wireless channel model the region A J is circular while the shape of region A j , for j = 1, 2, • • • , J -1, is a ring with inner and outer radii of r j+1 and r j respectively. And r j is given by:

r j = min r | R (Γ (r[cos(θ) sin(θ)] -p AP )) = R j (14)
The radii r j are computed from the channel statistics which can be estimated using the techniques presented in [START_REF] Malmirchegini | On the Spatial Predictability of Communication Channels[END_REF]. Nevertheless, for lack of space we do not provide here the details on how to compute it. We also define u j (t) as any control law that takes the vehicle through the regions {A k } j k=0 . The set of all control laws u j (t) will be denoted as U j and U = ∪ J j=0 U j is the set of all control laws. One simple way to solve (12) is to first solve it with the additional constraint u ∈ U j , once for each different value of j = 1, 2, • • • , J. We will denote as u * j (t) the optimum control law that solves (12) under the additional constraint u ∈ U j and u * (t) as control law that solves (12) under the constraint u ∈ {u * j (t)} J j=1 . Therefore to solve (12) we will calculate all the optimum control signals u * j . In order to minimize the mechanical energy term in the optimization target of (12) the optimum control law u * j (t) must make the robot enter and exit the convex hull of each region {A n } j n=0 at most once. These input and output points to the convex hull of the area A j are denoted by i j and o j respectively. We regroup these points in the following set

C j = {s, i 1 , i 2 , • • • , i j , o j , o j-1 , • • • , o 1 ,
g} and index them as follows:

c j 0 = s, c j n = i n , for n = 1, 2, • • • , j, c j n = o 2j+1-n , for n = j + 1, j + 2, • • • , 2j, c j 2j+1 = g. (15)
where s and g are the starting and goal points for the robot. In addition, t n is the time instant in which the robot is at p j n and:

τ n t f = (t n+1 -t n ), n = 0, 1, • • • , 2j (16)
where:

2j n=0 τ n = 1, τ n > 0, (17)
Note that the coefficients {τ n } 2j n=0 determine the portion of time t f that the robot takes to go from c j n-1 to c j n . Let us also write the points belonging to C j in polar coordinates as:

c j n = r j n [cos(φ j n ) sin(φ j n )] T . ( 18
)
From the definition of i n and o n we know that they lie in a circle of radius r n which can be computed from the p.m.f. of R (Γ (p(kT ))). Therefore we know {r j n } 2j n=1 and as a consequence the only unknowns to uniquely determine C j are the angles 5 {φ j n } 2j n=1 , where the φ j n is the angle of c j n respect to the AP. Now, the optimum control law u * j (t) takes the robot from c j 0 up to c j 2j+1 in ascending order through each point in C j . We can also see that the second term in the optimization target of (12) depends only the time spent in each region A j (i.e., on the durations τ k t f ) and not on the shape of the particular path followed by the robot nor by its velocity profile. So, the velocity profile and the path must be selected to minimize the mechanical energy (i.e., the first term in the optimization target ( 12)). To do so the vehicle must go from c j n-1 to c j n in a time τ n t f (to be determined) using minimum energy. Using calculus of variations [START_REF] Kirk | Optimal control theory: An introduction[END_REF] we can show that this is achieved by:

u j (t) = c j n -c j n-1 τ n-1 t f ∀ t ∈ [t n-1 , t n ). ( 19
)
Therefore if we add the constraint u ∈ U j and then we optimize {τ n } 2j n=0 and the angles {φ j n } 2j n=1 we obtain u * j (t). Now, if we use the constraint u ∈ U j and select u j (t) to take the form (19) then the optimization target of problem (12) becomes:

J {τ n } 2j n=0 , {φ j n } 2j n=1 = θ 1 2j+1 n=1 c j n -c j n-1 2 u 2 max τ n-1 t f + θ 2 t f T k=0 T b(k) N . (20)
And using (13), ( 19) and the constraint in (12) we have the following approximation:

τ j t f T R j + j-1 n=0 (τ 2j-n + τ n )t f T R n ≥ r R N (21)
So, taking into account ( 19)-( 21) the optimization problem (12) becomes:

minimize {τn} 2j n=0 ,{φ j n } 2j n=1 J {τ n } 2j n=0 , {φ j n } 2j n=1 s.t. 2j+1 n=1 τ n = 1, τ n > 0, r 2 n +r 2 n-1 -2rnrn-1 cos(φ j n -φ j n-1 ) τ 2 n t 2 f ≤ u 2 max , n = 0, 1, • • • , 2j c j n = r j n [cos(φ j n ) sin(φ j n )] T , c j 0 = s c j 2j+1 = g, τj t f T R j + j-1 n=0 (τ 2j-n + τ n )t f T R n ≥ r R N (22)
where the first line of constraints ensures that the coefficients {τ k } 2j k=0 determine the portion of the total time t f taken to go from one point in C j to the next one. The next line of constraints establishes the maximum velocity of the robot. The final constraint is the robust constraint which will allow the designer to obtain a high probability of the MR emptying completely its buffer.

To solve the optimization problem (22) we first express the angles {φ j n } 2j n=1 as function of the durations {τ n } 2j n=0 . This is achieved by deriving the optimization target of ( 22), see more details in [START_REF] Licea | Trajectory planning for energy-efficient vehicles with communications constraints[END_REF]. Then we use simulated annealing algorithm (SAA) [START_REF] Russell | Artificial Intellingence: A Modern Approach[END_REF] to optimize the durations {τ n } 2j n=0 . This concludes the discussion about the optimization of the trajectory and in the next section we present some simulations to better understand its behaviour and observe its performance.

Simulations

In this section we present some simulations to gain some insight about the trajectories obtained by the method presented in this paper. We select 10 log 10 P σ 2 n = 33dB. Now, the initial number of bits in the buffer b(0) = 600N s while the possible amount of bits transmitted in one packet can be

R 0 = 0, R 1 = 4N s , R 2 = 16N s , R 3 = 64N s
where N s is the number of symbols transmitted in one packet. Note that such values for the number of bits transmitted in the payload can be obtained using a rectangular M-QAM modulation. Now, regarding the thresholds {η j } J j=0 we fix them so that the bit error rate is at least 10 -3 . Now regarding the channel we select the path loss coefficient as α = 2, shadowing variance σ 2 s = 2.5 and then for the decorrelation distance we select β = 10λ, where λ is the wavelength of the RF carrier used for communications.

We select the starting and the goal points to be s = [8λ 0] and g = [9 -6]λ while we locate the access point at the origin. Then the time to reach the goal point is t f = 20s, the period between packets T = 100ms and the maximum velocity of the MR is 10λ per second.

First of all we consider for references a trajectory that goes from s to g using minimum energy. This is achieved by a linear path between both points and a constant velocity profile. We will denote such trajectory as T 0 . Then we consider a trajectory T 1 optimized according to (22) with θ 1 = 1, θ 2 = 0 and r R = 1. This trajectory is optimized to use minimum energy while satisfying constraint (21). Then we also consider another trajectory T 1 optimized according to (22) with θ 1 = 0, θ 2 = 1 and r R = 1. This trajectory is optimized to empty the buffer as quick as possible.

In Fig. 1 we can observe the paths corresponding to the trajectories T 0 , T 1 and T 2 . We first note that the path corresponding to T 1 is shorter than the path corresponding to T 2 which agrees with the fact that the trajectory T 1 is optimized to minimize the energy consumed (while satisfying constraint (21)). Then regarding the shape of the paths we see that the path of T 2 reaches A 2 through the shortest path, this is done in order improve as quick as possible the transmission rate in order to empty the buffer as soon as possible. Now, regarding the path for T 1 the robot reaches A 2 by moving in an orthogonal direction with respect to the vector gs, by doing so the robot minimizes the amount of deviation from g which reduces then the distance total distance travelled and consequently the energy spent. When we observe the velocity profiles of both trajectories in Fig. 2 we first note that the period with highest velocity takes place from t = 0 until t = τ 1 this is because the robot is rushing to get out from A 0 to start transmitting as many bits as possible. Then we also observe that the minimum velocity occurs when the robot reaches the inner most area of the trajectory (in this case A 2 ). This is in order to spend as much time as possible in that area with the best channel conditions in the trajectory.

Then, in table 1 we observe the average time in which the buffer is emptied E[t empt ], the probability of success P S (i.e., the probability of emptying the buffer when reaching g) and the amount of mechanical energy used normalized by mλ 2 . As it is expected the trajectory T 0 uses minimum energy but its probability of success is very low (0.0868). On the other hand the probability of success for the optimized trajectories T 1 and T 2 is much higher, 0.7206 and 0.9347 respectively, but due to the larger paths and velocities their energy consumption is higher. Now, we observe the effect of the robustness parameter r R , see (21). To do so we consider two more trajectories. The first one, denoted T 3 , is optimized according to (22) with θ 1 = 0.3, θ 2 = 0.7 and r R = 1. While the second trajectory, denoted T 4 , is optimized according to (22) with θ 1 = 0.3, θ 2 = 0.7 and r R = 1.5. We observe in Fig. 3 that their path is really similar (the path corresponding to T 4 is slightly larger) but their velocity profiles are clearly different as we can observe in Fig. 4. The trajectory T 4 spends a larger time in the area A 2 in order to increase the average data rate and therefore increase the probability of success. But by doing so the robot has to move quicker when it gets out from A 2 in order to reach g in time. By comparing the probabilities of success of T 4 with T 3 in table 1 we observe that increasing the robustness parameter r R indeed increases the probability of success although it also increases the energy consumption.

Note that all the optimized predefined trajectories were able to produce a relatively large probability of success in a fading channel without the use of any kind of diversity. This large probability of success was achieved by optimizing the trajectories using only first order statistics of the wireless channel. In the future we will take into account channel measurements to develop an online mechanism which further improves the success probability while reducing the amount of mechanical energy.

Conclusions

We have formulated the problem of robust trajectory optimization for an MR with a target point to reach and a certain number of bits to transmit within a given time. Due to small scale fading and shadowing effects, obtaining a suitable reference trajectory offline is non-trivial. Therefore, we consider the most likely buffer state at each time determined based on the statistical mode and optimize the desired metric by introducing an overestimation parameter for robustness. This approach results in an optimization problem with a feasible solution.

Fig. 1 . 2 Fig. 2 .

 122 Fig.1. Paths corresponding to trajectories T0 (green), T1 (blue) and T2 (magenta). Starting point s represented by a circle, goal point s represented by a triangle and AP location at the origin. We observe as well the delimitation of the areas {Aj} 3 j=0 .

Fig. 3 .

 3 Fig. 3. Paths corresponding to trajectories T3 (green) and T4 (dashed red).

4 Fig. 4 .

 44 Fig. 4. Velocity profiles of trajectory T3 (top) and T4 (bottom).

Table 1 .

 1 Performance of different trajectories

	trajectory E[tempt] (s) PS Energy/(mλ 2 ) (J)
	T0	14.46	0.0868	0.1859
	T1	10.41	0.7206	0.8139
	T2	7.72	0.9347	4.8924
	T3	7.68	0.8652	3.8928
	T4	7.59	0.9262	4.7909

The present work is supported by the LIA project between CRAN, Lorea and the International University of Rabat.