N Mitton

E Fleury

I Guérin Lassous

B Sericola

⋆ S Tixeuil

Fast Convergence in Self-Stabilizing Wireless Networks *

Keywords: coloring, scheduling, stabilization time, multi-hop wireless networks

The advent of large scale multi-hop wireless networks highlights problems of fault tolerance and scale in distributed system, motivating designs that autonomously recover from transient faults and spontaneous reconfiguration. Self-stabilization provides an elegant solution for recovering from such faults. We present complexity analysis for a family of self-stabilizing vertex coloring algorithms in the context of multi-hop wireless networks.

Such "coloring" processes are used in several protocols for solving many different issues (clustering, synchronizing...). Overall, our results show that the actual stabilization time is much smaller than the upper bound provided by previous studies. Similarly, the height of the induced DAG is much lower than the linear dependency on the size of the color domain (that was previously announced). Finally, it appears that symmetry breaking tricks traditionally used to expedite stabilization are in fact harmful when used in networks that are not tightly synchronized.

Introduction

Wireless multi-hop networks (such as ad hoc or sensor networks) consist of sets of independent mobile wireless nodes that operate without the support of a pre-existing fixed infrastructure.

They offer unique benefits for certain environments and applications as they can be quickly deployed. Nodes are self-contained, battery-powered computers with radio links that enable the entities to self-organize into a network, communicate with each other and exchange data.

The advent of large-scale multi-hop wireless networks highlights problems of fault tolerance and scale in distributed system, motivating designs that autonomously recover from transient faults and spontaneous reconfiguration. Resuming correct behavior after a fault occurs can be very costly [START_REF] Perlman | Interconnections: Bridges, Routers, Switches, and Internetworking Protocols[END_REF]: the whole network may have to be shut down and globally reset in a good initial state. While this approach is feasible for small networks, it is far from practical in large networks such as forecast sensor networks. Self-stabilization [START_REF] Dijkstra | Self stabilizing systems in spite of distributed control[END_REF][START_REF] Dolev | Self-Stabilization[END_REF] is an attractive approach for such problems. It provides a way to recover from faults without the cost and inconvenience of a generalized human intervention: after a fault is diagnosed, one simply has to remove, repair, or reinitialize the faulty components, and the system, by itself, will return to a good global state within a relatively short amount of time.

Distributed self-stabilizing algorithms may thus be used for organizing and/or managing multi-hop wireless networks. For example, the self-stabilizing distributed vertex coloring algorithm can be used for resource allocation [START_REF] Lynch | Distributed algorithms[END_REF] or distributed local organization [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF][START_REF] Mitton | Self-stabilization in self-organized wireless multihop networks[END_REF] in such networks. The vertex coloring problem, issued from classical graph theory, consists in choosing different colors for any two neighboring nodes in a graph. This problem can easily be generalized to distance k, requiring that any two nodes that are up to k hops away must have different colors. Intuitively, the vertex coloring algorithm runs as follows: every node repetitively collects colors chosen by its neighbors, and if it detects a conflict with its own color, randomly chooses a fresh color (not taken by its distance-k neighborhood). Such algorithms in multi-hop wireless networks do not try to minimize the number of used colors, but when the graph degree is bounded by a small constant (as it is the case in sensor networks), the expected local stabilization time (i.e. the stabilization time in any neighborhood) of the algorithm is also constant. This makes the algorithm independent on n, the number of the nodes in the network, and thus scalable to large networks. Moreover, the directed acyclic graph that is induced by the colors is of constant height, so that self-stabilizing algorithms that are composed with the coloring can stabilize also in constant time. This property was used, in the context of multi-hop wireless networks, in [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF] to compute a minimal distance-2 coloring, and in [START_REF] Mitton | Self-stabilization in self-organized wireless multihop networks[END_REF] to self-organize the network into clusters, both locally stabilizing in expected constant time. While this distance-k coloring algorithm has provenly fast local stabilization time, the influence of system parameters remains unknown.

In this paper, we study the stabilization time of distance-k coloring algorithms in various settings that are relevant to wireless multi-hop networks. We first provide a theoretical study in synchronous and anonymous networks: we extend the analysis carried out in [START_REF] Chelius | On the NAP Protocol[END_REF] to the context of anonymous networks. Using simulations, we consider various topologies (grids and random graphs), different kinds of scheduling hypothesis (synchronous and probabilistically asynchronous), and variants of the algorithm that uses network wide identifiers so that priorities can be derived for neighboring nodes. We study the impact of these parameters on the stabilization time of distance-k coloring algorithms.

The remaining of the paper is organized as follows: Section 2 formally presents the system model and the coloring algorithm. In Section 3, we analytically study the stabilizing time considering a synchronous setting, while in Section 4 we provide extensive simulations and comments on various parameters. Section 5 gives concluding remarks.

Preliminaries

System model. The system is composed of a set V of nodes in a multi-hop wireless network and each node has a unique identifier. Communication between nodes uses a low-power radio. Each node p ∈ V can communicate with a subset N p ⊆ V of nodes determined by the range of the radio signal R; N p is called the neighborhood of node p. p does not belong to N p (p / ∈ N p ). In the wireless model, transmission is omni-directional: each message sent by p is effectively broadcast to all nodes in N p . We also assume that communication capability is bidirectional: q ∈ N p iff p ∈ N q . Define N 1 p = N p and for i > 1,

N i p = N i-1 p ∪ { r | (∃q : q ∈ N i-1 p : r ∈ N q ) } (let's call N i p the distance-i neighborhood of p).
We assume that the distribution of nodes is sparse: there is some known constant δ such that for any node p, |N p | ≤ δ. Note that sensor networks can control density by adjusting their radius R and/or powering off nodes in areas that are too dense, which is one aim of topology control algorithms.

Notation. We describe algorithms using the notation of guarded assignment statements:

G → S represents a guarded assignment, where G is a predicate of the local variables of a node, and S is an assignment to local variables of the node. If predicate G (called the guard) holds, then assignment S is executed, otherwise S is skipped. We assume that all such guarded assignments execute atomically when a message is received. At any system state, where a given guard G holds, we say that G is enabled at that state.

Execution and scheduling. The life of computing at every node consists of the infinite repetition of evaluating its guarded actions. The scheduler is responsible for choosing enabled processors for executing their guarded rules. In this paper, we consider three possible schedulers: the synchronous scheduler, the probabilistic central scheduler, and the probabilistic distributed scheduler. With the synchronous scheduler, nodes operate in lock steps, and at every step, every node is activated by the scheduler. At every step, the probabilistic central scheduler randomly activates exactly one node. With the probabilistic distributed scheduler, at each step, each node is activated with probability 1/n. The two last schedulers model the fact that although nodes execute their actions at the same speed on average, there is a chance that their clocks or speeds are not uniform, so that the system is slightly asynchronous. The distributed scheduler is more realistic than the central one, but the latter is often used for proving self-stabilizing algorithms.

Shared Variable Propagation. Nodes communicate with their neighbors using shared variables. To keep the analysis simple, we assume that there exists an underlying shared variable propagation scheme that allows nodes to collect shared variables in their neighborhood at distance k, for a fixed k. A possible implementation can be found in [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF]. For our purpose, we simply assume that a node is able, in one "macro" step, to read all shared variables in its neighborhood at distance k. This assumption is justified in Appendix.

Coloring Algorithm and DAG construction. The coloring algorithm that we consider uses a single shared variable for each node. Let C p be a shared variable that belongs to the domain ∆; variable C p is the color of node p. The S Cp predicate refers to the set of colors that have been used in the neighborhood at distance k of p:

S Cp = {C q | q ∈ N k p }. Let random(S)
choose with uniform probability some element of set S. Node p uses the following function to compute C p :

newC(C p ) =        C p if C p ∈ S Cp random(∆ \ S Cp ) otherwise
The algorithm for vertex coloring is the following: N1:true → C p := newC(C p )

As colors are ordered and unique in a node neighborhood, such a coloring algorithm can lead to the construction of a Directed Acyclic Graph (DAG) when (virtually) drawing a directed edge from each node to its only neighbor with the lowest color (if such a node exists).

Local Stabilization. With respect to any given node v, a solution for the coloring problem at distance k is locally stabilizing for v with convergence time t if, for any initial system state, after at most t time units, every subsequent system state satisfies the property that any node w at distance less than k from v is such that C w = C v . For randomized algorithms, this definition is modified to specify expected convergence times (all stabilizing randomized algorithms we consider are probabilistically convergent in the Las Vegas sense). In [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF], the authors show that Algorithm N1 self-stabilizes with probability 1 and has constant expected local stabilization time.

Uniform vs. Non Uniform Networks. In theory, the coloring algorithm N1 could work in uniform and anonymous networks (where nodes do not have unique identifiers and execute the same code). Collecting the neighborhood at distance k generally requires identifiers. Then, it is possible to tweak the algorithm to use these identifiers to break symmetry and expedite convergence: when at least two neighbors have a conflicting color, the node with the lowest identifier never changes its color. Thus, we have the guarantee that at any step, at least one of the conflicting nodes gets a stable color. In the remaining of the paper, we distinguish two operating modes for the algorithm: the all mode refers to the mode where all conflicting nodes draw a new color (anonymous networks), while the all but one mode refers to the version where the previous algorithm applies (uniform networks where one conflicting node does not change its color).

Analysis

In this section, we theoretically compute the expected stabilization time of the coloring protocol N1, i.e. the expected number of steps before a node has a color that is not already used in its distance-k neighborhood. From [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF], we already know that when the degree is upper bounded by a constant(δ), the expected local stabilization time is also upper bounded by a constant. However, the actual constant is not given in [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF], and the one that can be derived from the algorithm is high (about δ 6 for a distance-3 coloring).

The other metric of interest for our purpose is the height of the DAG that is induced by the colors. Indeed, when the coloring algorithm is used as a building block for subsequent algorithms, the stabilization time of those algorithms is generally in the order of the color DAG height, a lower DAG height inducing a smaller stabilization time. In [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF], the authors show that the height of the DAG is bounded by |∆| + 1, where ∆ denotes the color domain.

For the theoretical study, we consider only the synchronous scheduler, and we model the coloring protocol by a successive set of random draws. The main goal is to assign a color to each node. A way to model this problem is to consider that the color domain is represented by a set of M urns in which one must randomly distribute L balls which are going to represent the nodes. In each neighborhood, the goal is then to have only one ball (one node) associated to a given urn (one color).

This model has already been used in [START_REF] Chelius | On the NAP Protocol[END_REF] (for the NAP protocol), in which the authors analyze the stabilization time of a self-addressing network where two links must receive a unique prefix in the network. In this model, the urns symbolize the prefix and the balls the links. Each link chooses a random prefix in a prefix domain. If two links have chosen the same prefix, the one with the lowest ID keeps it while the other one(s) choose(s) a new prefix among the ones not already assigned. The analysis and the calculus carried out in [START_REF] Chelius | On the NAP Protocol[END_REF] thus roughly correspond to our all but one mode. In this section, we extend the analysis in the all mode.

Note that this theoretical study only matches for complete networks, i.e. where each node can communicate with all the other nodes. In multi-hop networks, it is possible that two neighboring nodes (A and B) with no conflicting colors simultaneously draw a new identical color, because they each have another conflicting neighbor (not visible to A or to B). But, it is important to note that this theoretical study gives a lower bound on the actual stabilization time (this is further refined in Section 4).

The algorithm can be modeled in terms of urns/balls as follows.

Algorithm 1 Coloring Process(L, M )

⊲ Input: M urns and L balls ⊲ Pre-condition: M ≥ L if (L = 0) then
Randomly throw the L balls in the M urns; if (case = 'all') then Keep aside all urns that contain exactly one ball with their ball inside ; end if (case = 'all but one') then Keep aside all urns containing at least one ball and one of their balls; end Let note c ≤ M the number of "correct" urns that we keep aside; Call Color Process(L -c, M -c); end By repeating the process, eventually every ball will be stored in a correct urn and every urn will contain at most one ball. Let N denote the number of iterations needed to reach such a configuration, i.e. the number of calls to the recursive procedure of coloring. We are interested in computing the distribution and the expectation of the random variable N . We consider the homogeneous discrete-time Markov chain X = {X n , n ∈ AE}, on the finite state space I = {0, 1, . . . , L} where the event {X n = i} represents the fact that, after n transitions (or calls to the coloring procedure), the procedure Color Process(M -i, L-i) is currently executed. In other words, {X n = i} represents the fact that, after n transitions, exactly i urns and balls have been kept aside, i.e. exactly i urns contain exactly one ball. The Markov chain starts in state 0 with probability 1, which means that at the beginning, none of the urns and balls have been kept aside. The random variable N can be defined more formally, for L ≥ 1, as N = n≥0 L-1 i=0 1 {Xn=i} . N is the number of transient states of X visited before absorption.

We denote by P(L, M ) = (p i,j (L, M )) (i,j)∈I 2 the transition probability matrix of the Markov chain X, where p i,j (L, M ) represents the probability to have exactly j urns and balls kept aside at the time n + 1 given that i urns and balls have been kept aside at time n. p i,j (L, M ) is thus the probability to obtain exactly j -i urns each with one ball when throwing L -i balls into M -i urns. For all i ≤ j, we thus have p i,j (L, M ) = p i,j = p 0,j-i (L -i, M -i).

(1)

The Markov chain X is clearly acyclic and the state L is the absorbing state of X.

This means that for every i ∈ I -{L} and j ∈ I, we have p i,j (L, M ) = 0 for i > j and

p L,L (L, M ) = 1.
The transition probability matrix P(L, M ) has thus the following form:

P(L, M ) =                 p 0,0 p 0,1 p 0,2 • • • • • • p 0,L 0 p 1,1 p 1,2 p 1,3 • • • p 1,L . . . . . . . . . . . . . . . . . . 0 0 • • • 0 p L-1,L-1 p L-1,L 0 0 • • • • • • 0 1                
.

The computation of the matrix P(L, M ) depends on the drawing hypothesis (all but one or all mode). But, once the transition probability matrix is computed, the way of evaluating the stabilization time of the coloring algorithm is the same whatever the drawing hypothesis. The all but one mode is a little bit simpler because it implies p i,i (L, M ) = 0 for every 0 ≤ i ≤ L -1, which means that the stabilization time N of the coloring algorithm is bounded: N ≤ L. We give in the following subsection the transition probability matrix of each mode before giving the distribution and the expectation of the stabilization time N of the coloring algorithm.

p 0,j (L, M ) can thus be expressed as

p 0,j (L, M ) = P[K 1 (L, M ) = j] = M k=0 a L,M (k, j).
In order to compute all the probabilities a L,M (k, j) we can proceed by recursion on integer L by conditioning on the result of the throw of the last ball. More precisely, in order to obtain k empty urns and j urns with only one ball inside when throwing L balls in M urns we need:

1. Either obtaining k + 1 empty urns and j -1 urns with exactly one ball inside at the end of the L -1 first throws of L -1 balls in M urns and throwing the last ball in one of the k + 1 empty urns. Thus, from that decomposition and for L ≥ 2, we have:

a L,M (k, j) = k + 1 M a L-1,M (k+1, j-1)1 {j≥1} + j + 1 M a L-1,M (k, j+1)+ M -(j + k) M a L-1,M (k, j)
where 1 {c} is the indicator function equal to 1 if condition c is true and 0 otherwise. For L = 1 we trivially have as initial value for the recursion:

a 1,M (k, j) = 1 {k=M -1, j=1} . (3)
It is also easy to check that a L,M (k, j) = 0 if either j > L either k = M or j + k > M . Note that for j = L, we have a L,M (k, L) = 0 for k = M -L and a L,M (M -L, L) = p 0,L (L, M ) which is given by relation [START_REF] Dijkstra | Self stabilizing systems in spite of distributed control[END_REF] and that clearly satisfies the recurrence relations.

Matrix for the all but one mode: This case is the one given in [START_REF] Chelius | On the NAP Protocol[END_REF]. We only give here the results. In the all but one mode, at each step, we keep aside at least one urn together with one of the balls contained inside. This means that the transition probability p i,i (L, M ) = 0 for every 0 ≤ i ≤ L -1. The Markov chain X is thus strictly acyclic and the stabilization time N of the coloring algorithm is bounded by L.

Based on a well-known result about the number of ways of throwing r different balls in n different urns such that exactly m urns are non-empty [START_REF] Eisen | Introduction to Mathematical Probability Theory[END_REF], the transition probability matrix is given according to (1), for i < j, by

p i,j (L, M ) = M -i j -i j-i k=0 j -i k (-1) k j -i -k M -i L-i
.

Distribution and expectation of N . Now, given the transition probability matrix of the Markov chain X, we are able to determine the distribution (P [N = n] for n = 0, . . . , ∞) and the expected value E [N ] of the random variable N for both modes. The mean value E [N ] is also actually the mean number of steps needed before stabilization of our coloring algorithm and so its stabilization time.

These calculus are detailed in [START_REF] Chelius | On the NAP Protocol[END_REF]. We directly use them here. They are easily derived from the classical results on Markov chains. Let Q denote the sub-matrix obtained from P(L, M ) by removing the last line and the last column which correspond to the absorbing state L.

We denote by α the row vector containing the initial probability distribution of the transient states of X, i.e. α = (P [X 0 = i]) i=0,...,L-1 . As already seen, the Markov chain starts in state 0 with probability 1 and, thus we have α = (1, 0, . . . , 0). With these notations, we have

P [N = n] = αQ n-1 (I -Q)½, for n ≥ 1, P [N > n] = ∞ k=n+1 αQ k-1 (I -Q)½ = αQ n ½, for n ≥ 0,
and

E [N ] = ∞ n=0 P [N > n] = α (I -Q) -1 ½,
where I is the identity matrix and ½ is the column vector with all entries equal to 1, both of dimension L. If V = (V i ) 0≤i≤L-1 is the column vector defined by

V i = E [N |X 0 = i],
we have

E [N ] = V 0 .
The vector V of conditional expectations is given by V = (I -Q) -1 ½, which means that it is solution to the linear system (I -Q)V = ½, which can also be written as V = ½ + QV or equivalently, since the matrix P(L, M ) is acyclic, as

V i = 1 1 -p i,i   1 + L-1 j=i+1 p i,j V j   for i = L -2, . . . , 0, with V L-1,L-1 = 1/(1 -p L-1,L-1 ).
We are now able to compute E [N ] = V 0 by recurrence from V i . We use these theoretical results in the next sections to compare with the simulation outcomes.

Simulations

We performed simulations to evaluate the stabilization time of the coloring algorithms over different assumptions, to analyze the directed acyclic graph deriving from it in each case, and to compare those values to the theoretical ones in order to validate our analytical model. As mentioned in the previous sections, we are mainly interested in the stabilization time under several scheduling and coloring hypothesis but also on the height of the derived DAG.

Simulation model. We use a simulator we developed and that assumes an ideal MAC layer. In each case, each statistic is the average over 1000 simulations. All coloring algorithms studied below are analyzed over a same node distribution.

We say that a node executes an action (or acts, for short) when it checks its neighbors' color and if needed, chooses another color among the available ones. For a distance-k coloring, a color c ∈ ∆ is said available for a node u if ∀v ∈ N k u , C v = c. As mentioned in Section 2, we studied the coloring algorithm for different kinds of scheduling hypothesis: Synchronous (every node acts at every step), Probabilistic Central (exactly one random node acts at every step) and Probabilistic Distributed (at each step, each node acts with probability 1 n ). Each scheduling hypothesis is studied for both modes of coloring: all but one mode (for each pair of conflicting nodes, every node but one chooses another color) and all mode (every conflicting node chooses another color).

We have run Algorithm N1 for distance-1 and distance-2 colorings with these scheduling hypothesis and modes over a random geometric topology and a grid with a varying number . In these settings, we collect the stabilization time of the coloring algorithm as well as the height of the induced DAG. In the synchronous mode, every node acts with probability 1 (so the expected time before acting is 1 step) whereas in both probabilistic modes, every node acts within expected n steps.

As schedulers are meant to model scheduling properties rather than implemented scheduling mechanisms, in a "real" system a particular node would act within a constant expected time.

So, in order to be able to compare the three schedulers and to be fair when considering the stabilization time of different schedulings, the number of steps before stabilization in probabilistic modes is divided by n.

In the geometric approach, nodes are randomly deployed using a Poisson Process in a 1×1 square with various levels of intensity λ (from 500 to 1000). In such processes, λ represents the mean number of nodes per surface unit. The communication range R is set to 0.1 in all tests. We thus have a mean number of neighbors per node ranging from 15 to 32. In the grid, we consider topologies where each central node has 4 and 8 neighbors.

Theory vs. Simulation. As mentioned in Section 3, we expect that our theoretical results

give an accurate lower bound on the stabilization time of the coloring algorithm. Indeed, when considering a complete graph, once a node u has chosen an available color, every other node in the network knows that color (as a neighboring node of u) and thus will not choose it anymore. However, in a non-complete graph, a situation such as illustrated in Figure 1 (for distance-1 coloring) may occur and thus, the average stabilization time would be higher than the one in a complete graph, therefore our theoretical analysis only leads to a lower bound. For example, let's run the algorithm over the graph plotted on Figure 1, under the synchronous scheduling and the all mode. Every node has to choose a color from 0 to 4 until getting a locally unique color. Node B has two neighbors, A and C. The example shows the colors drawn at each step by each node. As there still exist conflicts at the end of the three steps, the algorithm would not stop yet. But, from the theoretical analysis, if we consider that A, B and C are in a complete graph, then at step 2, C has its color (3) and at step 3,

A and B have their color (1 and 2). So at the end of the three steps, with the theoretical analysis, every urn has been kept aside and the system should have stabilized.

A,0 B,0 C,0 D,0 Step 1 System execution A,1 B, 1 C,3 D,3 A,1 B,2 C,2 D,4
Step 2

Step 3

Available colors to B In order to evaluate the difference between the analytical lower bound and the simulated stabilization time, we compute by simulation the number of times that two neighboring nodes not originally in mutual conflict have to both choose another color and both get the same In all cases, whatever the coloring distance k and the color domain ∆, we can note that the behavior of both probabilistic schedulers is similar. With the probabilistic scheduling hypothesis, in order to stabilize, the scheduler has to choose a node in conflict. In the all but one mode, only one node per pair of conflicting nodes actually chooses another color.

The probabilistic schedulers thus have less chance to elect a conflicting node in the all but one mode than in the all mode (almost half chances less). Therefore, with the all mode, these probabilistic schedulings achieve better stabilization time (almost half time) than with the all but one mode. In the synchronous mode, at each step, every node acts. As in the all but one mode, in any pair of conflicting nodes, already one of those nodes has a stable color, so the stabilization time is lower than in the all mode. Note that for sensor networks, nodes are rarely tightly synchronized, so that the most realistic model is the distributed probabilistic scheduler, so the all mode is to be preferred in this context. This mode also is the easiest to implement in sensor networks as it does not require that every node knows the identity of the nodes in its k-neighborhood.

Influence of the size of the color domain. Since the most realistic model for sensor networks is the distributed probabilistic one with all mode, Figures 4(a Results clearly show that a higher domain size |∆| induces a lower stabilization time and a higher DAG. There thus is a trade-off to do between these two characteristics depending of the application that will use the coloring. However, and although theoretical results show that the DAG height can be up to |∆| -1, simulation results show that the actual height is in fact much lower, and most certainly sub-linear in |∆|. Influence of the coloring distance. Figure 5 plots the stabilization time for distance k-coloring with all mode, assuming the distributed probabilistic scheduler in 4-neighbor and 8-neighbor grids, respectively. The used color domain size is (max p∈V |N p |) 2×k . In order to evaluate the time to collect all colors from the neighborhood at distance k in a wireless sensor network, we reason as follows. Consider the subgraph that is centered in node p and contains all nodes up to k hops away from p. Now assume that the expected time for nodes in a 1-hop neighborhood to communicate with all their neighbors is upper bounded by a constant C (See Appendix). In the worst case, this subgraph is a tree where each node has degree It turns out that when k increases, the stabilization time eventually increases as fast as k 2 , independently of the topology. This means that the number of colors used is sufficiently large so that the coloring itself is almost performed in constant time, but the communication time becomes the main bottleneck of the algorithm.

Concluding remarks

Distance-k coloring is a useful mechanism for multi-hop wireless networks. In [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF], distance-3 coloring was used to construct a TDMA schedule and in [START_REF] Mitton | Self-stabilization in self-organized wireless multihop networks[END_REF], distance-2 coloring permitted to expedite density-based cluster construction. Further applications could be derived, e.g.

distance-k maximal independent set construction, by having nodes that have locally minimal color in their k-neighborhood be part of the independent set, and remaining nodes that do not see distance-k neighbors with lower colors in the independent set join the independent set.

In this paper, we have first extended the theoretical analysis of [START_REF] Chelius | On the NAP Protocol[END_REF] to anonymous networks (all but one mode). Then, by simulations, we have evaluated the impact of two considered modes (all but one and all modes), of different scheduling policies and of the color domain on the stabilization time and the induced DAG height. We have shown analytically and by simulation that the stabilization time and the DAG height of such coloring protocols in multi-hop wireless networks are low.

Further studies are needed to get a more realistic bound that takes into account the probabilistic nature of the MAC layer used in such networks. Indeed, as k grows, the size of the messages gets longer (in the order of δ k-1 , since a node needs to communicate information about its neighborhood at distance k -1 to each of its neighbors), so the probability that collisions occur between neighbors grows, and the delay increases.

(n-1) stations have successfully emitted and that the n th station succeeds to transmit during slot k. We thus have:

P [X = k, k > n] = k-1 k-n+1 n n-1 (1 -P suc ) (k-n+1) P n suc
We can deduce the mean number of slots E [X] needed before every n stations are able to transmit an information to their neighbors.

E [X] = ∞ k=0 kP [X = k] = nP [X = n] + ∞ k=n+1 kP [X = k] = P n suc × n + ∞ k=n+1 k k -1 k -n + 1 n n -1 (1 -P suc ) (k-n+1)
This can be derived into: As P suc only depends on n and that we assume that n is upper bounded by a constant, E [X] also is a constant. Therefore, in average, a node is able to read all shared variables in its neighborhood within constant time.

2 . 3 .

 23 Either obtaining k empty urns and j + 1 urns with exactly one ball inside at the end of the L -1 first throws of L -1 balls in M urns and throwing the last ball in one of the j + 1 urns containing exactly one ball. Or obtaining k empty urns and j urns with exactly one ball inside at the end of the L -1 first throws of L -1 balls in M urns and throwing the last ball in one of the M -(j + k) urns that contain at least 2 balls.

  of neighbors per node and different sizes of color domain ∆ . The initial stabilizing algorithm has been designed using |∆| = (max p∈V |N p |) 2×k , k being the coloring distance, but as we are interested in the impact of this domain size over the stabilization time and the DAG height, we have also run Algorithm N1 for |∆| = 2 × max p∈V |N k p | . Moreover, as in sensor networks, nodes do not have a general view of the network and thus have no way a priori to know the maximum degree in the graph, we have also run simulations where each node has its own color domain size such that ∀p ∈ V, |∆ p | = (|N p |) 2×k

Figure 1 :

 1 Figure 1: A possible execution for distance-1 coloring in a synchronous network.

  ) and 4(b) plot the stabilization time with these hypothesis for the distance-1 coloring algorithm as well as the height of the induced DAG, using different sizes of color domain. Nevertheless, results for the DAG height are similar whatever the coloring hypothesis.

|∆| = |Np| 2 +

 2 but one mode Synchronous -All mode Distributed Probabilistic -All but one mode Distributed Probabilistic -All Mode Central Probabilistic -All but one Mode Central Probabilistic -All Mode (b) |∆| = maxp∈V |Np| 2 Synchronous -All but one mode × Synchronous -All mode * Distributed probabilistic -All but one mode Distributed probabilistic -All mode Central probabilistic -All but one mode o Central probabilistic -All mode (d) Legend

Figure 3 :

 3 Figure 3: Stabilization time of the distance-1 coloring process for different modes and scheduling hypothesis over a geometric node distribution with different sizes of color domain.

Figure 4 :

 4 Figure 4: Influence of the color domain size on the stabilization time and the DAG height.

Figure 5 :

 5 Figure 5: Stabilization time with respect of time for message transmission as a function of the coloring distance.

E-

  [X] = P n suc × n + n(n + 1(n + 1) + nP suc )

Table 1 :

 1 Theory and simulations results for the stabilization time for synchronous distance-1 coloring with |∆| = (max p∈V |N p |) 2 ) and |∆| = 2 × (max p∈V |N p |) in grids.

						4 neighbors
		all but one					all
	2 * M ax				M ax 2		2 * M ax	M ax 2
	Theory	Simulation	Theory	Simulation	Theory	Simulation	Theory	Simulation
	1.88	1.89		1.51	1.64		2.14	2.14	1.56	1.61
						8 neighbors
		all but one					all
	2 * M ax				M ax 2		2 * M ax	M ax 2
	Theory	Simulation	Theory	Simulation	Theory	Simulation	Theory	Simulation
	1.51	1.56		1.14	1.22		1.56	1.67	1.15	1.21
		500 nodes	600 nodes	700 nodes	800 nodes	900 nodes	1000 nodes
	Mean degree	15.7			18.8	22.0	25.1	28.3	31.4
						all but one
	Theory		2.35			2.40	2.44	2.50	2.53	2.56
	Simulation	2.78			2.91	2.87	2.94	2.99	2.97
							all
	Theory		2.83			2.91	2.94	2.95	3.05	3.08
	Simulation	3.25			3.31	3.29	3.28	3.42	3.41

Table 2 :

 2 Theory and simulations results for the stabilization time for synchronous distance-1 coloring with |∆| = 2 × (max p∈V |N p |) in random geometry topologies. time is much lower than expected. From the results of [6], the stabilization time is at least linear in |∆| (being upper bounded by a constant when δ also is a constant). In contrast, our simulation results show a sub-linear (in |∆|) stabilization time, since considering |∆| = 2 × max p∈V |N p | vs. |∆| = max p∈V |N p | 2 merely divides by two the stabilization time. Also, doubling the degree of the nodes (when the network grows from 500 nodes to 1100 nodes) does not double the stabilization time. Especially, with the synchronous and distributed probabilistic schedulers, the stabilization time remains upper bounded by a constant.

* This work is supported by the FNS of the French Ministry of Research through the FRAGILE project [5] of the ACI Sécurité et Informatique.

Computation of the transition matrix P(L, M ). We now explicit the transition probability p i,j (L, M ) of the Markov chain X for all i ≤ j for both modes.

Matrix for the all mode: In the all mode, all nodes in conflict choose a new color among the free ones. At each step, we keep aside the urns and their balls if they contain exactly one ball. Unlike the all but one mode, we may keep none urn and ball at a step and thus the diagonal values of P(L, M ) are not null.

From relation [START_REF] Chelius | On the NAP Protocol[END_REF], we only have to compute the transition probability p 0,j-i (L -i, M -i)

for i ≤ j. The computation of the transition probabilities p i,j (L, M ) yields to the computation of the transition probabilities p 0,j (L, M ).

By definition of the transition matrix as stated above, the transition probability p 0,j (L, M ) is the probability to obtain exactly j urns containing only one ball when throwing randomly L balls into M urns. The case j = L yields to the generalized birthday problem and thus we have:

For j < L, we proceed as follows. We throw L balls into M urns. We denote by K 0 (L, M ) the number of empty urns and by K 1 (L, M ) the number of urns with exactly one ball inside. Let a L,M (k, j) denote the joint distribution of both random variables K 0 (L, M ) and

The transition probability color. Results for a distance-1 synchronous scheduling coloring are given in Figure 2. As we can see, the greater the color domain size, the more unlikely this case is to appear (almost 0% of the cases when the color domain size is quadratic in the maximum degree of the nodes).

We also note that, even for a small color domain size (such as twice the maximum degree), this case does not occur very often (less than 18% in the worst case). Thus, we can expect that in practice, our analytical result gives a very accurate lower bound on the stabilization time of the coloring protocol. As expected, theoretical results give tight lower bounds of the simulation outcome. Note that the size of the grid has no influence on the results, the number of neighbors being the only key parameter.

Stabilization time. Figure 3 presents the stabilization time for each scheduling hypothesis and both modes when using different sizes of color domain, for a random spatial distribution of the nodes. The most striking result compared to those of [START_REF] Herman | A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks[END_REF] is that the stabilization

A Appendix

In this section, we justify the following assumption "a node is able, in one step, to read all shared variables of its neighbors". In more details, we show that the expected time before receiving information from every neighbor is upper bounded by a constant.

In [START_REF] Zhai | Performance analysis of IEEE 802.11 MAC Protocols in wireless LANs[END_REF], the authors provide a performance analysis of IEEE 802.11 MAC protocols in wireless LANs. By considering a graph with n stations that are all within the transmission range of one another (i.e. the communication graph is a complete graph), the authors model the backoff timer nodes trigger in 802.11 before transmitting, which depends on the collisions that have occurred before. They deduce in particular the probability P suc that there is one successful transmission among the n stations in a considered time slot. A transmission is considered as successful if there is exactly one station that emits in this slot. If p c is the probability that there is at least one packet transmission in the medium among n stations (p c is also given in [START_REF] Zhai | Performance analysis of IEEE 802.11 MAC Protocols in wireless LANs[END_REF]), we have:

We now show that the time before all neighbors of a node successfully communicate is upper bounded by a constant, on average. Let the random variable X be the number of slots needed before the n stations be able to transmit information to their neighbors. In the best case, each station chooses a time slot to transmit different from every other. We thus have: P [X < n] = 0 and P [X = n] = P n suc .

Then, P [X = k, k > n] is the probability that at the end of the (k -1) first time slots,


Trinh Van Chien

Thanh Lam

Tu

Dinh-Hieu Tran

Hieu Van Nguyen

Symeon Chatzinotas

Marco Di Renzo

Björn Ottersten

CONTROLLING SMART PROPAGATION ENVIRONMENTS: LONG-TERM VERSUS SHORT-TERM PHASE SHIFT OPTIMIZATION

Keywords: Reconfigurable intelligent surface, coverage probability, ergodic channel rate 1. INTRODUCTION

Reconfigurable intelligent surfaces (RISs) have recently gained significant interest as an emerging technology for future wireless networks. This paper studies an RIS-assisted propagation environment, where a single-antenna source transmits data to a single-antenna destination in the presence of a weak direct link. We analyze and compare RIS designs based on long-term and short-term channel statistics in terms of coverage probability and ergodic rate. For the considered optimization designs, closed-form expressions for the coverage probability and ergodic rate are derived. We use numerical simulations to analyze and compare against analytic results in finite samples. Also, we show that the considered optimal phase shift designs outperform several heuristic benchmarks.

Index Terms-

criterion may, however, not be applicable in some application scenarios that are characterized by a short coherent time, since the optimal phase shifts of the RIS elements need be updated frequently in order to adapt to the rapid changes that characterize the small-scale fading [START_REF] Jung | Performance analysis of large intelligent surfaces (LISs): Asymptotic data rate and channel hardening effects[END_REF]. Another option for optimizing the phase shifts of the RIS elements is based on leveraging only statistical channel state information (CSI), i.e., the large-scale characteristics of the wireless channel [START_REF] Abrardo | Intelligent reflecting surfaces: Sum-rate optimization based on statistical position information[END_REF][START_REF] Di Renzo | Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and the road ahead[END_REF]. Optimization criteria based on long-term CSI need to be updated less frequently, and this reduces the channel estimation overhead. However, some performance degradation is expected as compared with the optimal phase shift design based on instantaneous CSI. Even though some research works have recently proposed the design of RISs based on long-term CSI, to the best of our knowledge, no previous work has comprehensively and analytically analyzed as well as compared the achievable performance of RIS-assisted wireless networks based on short-term and long-term CSI.

Based on these considerations, the aim of this paper is to study the performance of RIS-assisted systems by considering optimization criteria based on long-term channel statistics and short-term channel statistics, i.e., based on prefect CSI. We analyze the coverage probability and the ergodic channel capacity under long-term and short-term phase shift design criteria. Specifically, we derive closed-form expressions of the coverage probability and the ergodic channel rate for both optimization criteria, highlighting findings that have not been investigated before. Several insights are also observed, such as that the long-term phase shift design offers similar performance as the short-term optimal phase shift design as the number of RIS elements increases.

Notation: Upper-bold and lower-bold letters are used to denote matrices and vectors, respectively. The identity matrix of size M × M is denoted by I M . The Hermitian and regular transpose are denoted (•) H and (•) T , respectively. CN (•, •) denotes a circularly symmetric Gaussian distribution. The expectation of a random variable is denoted by E{•}. The upper incomplete Gamma function is denoted by Γ(m, n) = ∞ n t m-1 exp(-t)dt and Γ(x) = ∞ 0 t x-1 exp(-t)dt denotes the Gamma function.

SYSTEM MODEL

We consider an RIS-assisted communication system where a single-antenna source communicates with a single-antenna destination. A frequency-flat block-fading channel model is assumed in each coherence interval. The RIS comprises M reflecting elements. The RIS phase shift matrix Φ Φ Φ ∈ C M ×M is defined as Φ Φ Φ = diag [e jθ1 , . . . , e jθ M ] T , where θ m ∈ [-π, π] is the phase shift of the m-th reflecting element.

Channel Model

The channel of the direct link between the source and the destination is h sd ∈ C. The indirect link from the source to the destination comprises the channel between the source and the RIS, which is denoted by h sr ∈ C M , and the channel between the RIS and the destination, which is denoted by h rd ∈ C M . Specifically, the channels are defined as h sd = √ β sd g sd , h sr = hsr + g sr , and h rd = hrd + g rd , where g sd ∼ CN (0, 1), g sr ∼ CN (0, I M β sr /(K sr + 1)), and g rd ∼ CN (0, I M β rd /(K rd + 1)) are the small-scale fading contributions; β sd , β sr , and β rd are the large-scale fading coefficients; and K sr ≥ 0 and K rd ≥ 0 are the Rician factors. Based on [START_REF] Björnson | Massive MIMO networks: Spectral, energy, and hardware efficiency[END_REF], the line-of-sight (LoS) channel vectors hα ∈ C M , α ∈ {sr, rd}, are given as follows

hα = K α β α K α + 1 e jk(ψα,φα) T u1 , . . . , e jk(ψα,φα) T u M T , (1)
where ψ α and φ α are the azimuth and elevation angles of departure (AoD) under which the RIS views the source and the destination for α = sr and α = rd, respectively. By assuming that the RIS is a planar surface, the wave vectors in (1), k(ψ α , φ α ), are

k(ψ α , φ α ) = 2π λ [z 1 , z 2 , sin(ψ α )] T , (2)
with z 1 = cos(ψ α ) cos(φ α ) and z 2 = sin(ψ α ) cos(φ α ), and λ is the signal wavelength. Also, the vector u m in (1) is defined as

u m = [0, mod(m-1, M H )d r , (m-1)/M H d r ] T ,
where mod is the modulus operation and • is the floor function. d r is the element spacing at the RIS.

To facilitate the analysis in the next section, Theorem 1 gives the moments of the RIS-assisted (cascaded) channel for an arbitrary phase shift matrix Φ Φ Φ.

Theorem 1. The indirect link from the source to the destination through the RIS has the following statistical moments

E{|h H sr Φ Φ Φh rd | 2 } = δ, E{|h H sr Φ Φ Φh rd | 4 } = δ 2 + a, ( 3
)
where δ = |ᾱ| 2 + M µ K, ᾱ = hH sr Φ Φ Φ hrd , µ = β sr β rd /ω, ω = (K sr +1)(K rd +1), K = K sr +K rd +1, K = 1+2K sr +2K rd , and a = 2M |ᾱ| 2 µ K + M 2 µ 2 K 2 + 2M µ 2 K + 8|ᾱ| 2 µ.
Proof. The proof follows by using known results on the moments of Rician random variables. It is omitted due to space limitations.

The second and fourth moments demonstrate that the array gain due to the presence of an RIS is proportional to M and M 2 , respectively.

Phase Shift Designs and Channel Rate

If the source transmits a data symbol s with E{|s| 2 } = 1, the received signal y ∈ C at the destination is

y = √ ρ h sd + h H sr Φ Φ Φh rd s + n, (4)
where ρ is the transmit power and n ∼ CN (0, σ 2 ) is the additive noise. The phase shift matrix Φ Φ Φ is usually optimized based on the CSI. In this paper, we focus our attention on two design criteria.

i) Short-term phase shift design: The phase shifts of the RIS elements are optimized based on perfect CSI, which encompasses large-scale and small-scale fading statistics.

ii) Long-term phase shift design: The phase shifts of the RIS elements are optimized based on statistical CSI. In particular, the optimal phase shift matrix is obtained by maximizing the average SNR at the destination.

The short-term phase shift design corresponds to the best achievable performance. Let us assume that we are interested in maximizing the received signal strength, i.e.,

ρ|h sd + h H sr Φ Φ Φh rd | 2 .
Then, the short-term optimal phase shift of the m-th RIS element, which is denoted by θ opt,st m , is [START_REF] Wu | Intelligent reflecting surface enhanced wireless network via joint active and passive beamforming[END_REF][START_REF] Van Chien | Outage probability analysis of IRS-assisted systems under spatially correlated channels[END_REF]

θ opt,st m = arg(h sd ) -arg([h * sr ] m ) -arg([h rd ] m ), ∀m, (5)
where [h sr ] m and [h rd ] m are the m-th element of h sr and h rd , respectively. The optimal phase shift of each RIS element in [START_REF] Chien | Reconfigurable intelligent surfaceassisted Cell-Free Massive MIMO systems over spatially-correlated channels[END_REF] needs to be updated every channel coherent interval. By contrast, the long-term phase shift matrix can be applied for a longer period of time, which spans many coherence intervals. Conditioned on the phase shift matrix and the CSI, the channel rate is formulated as

R = log 2 (1 + γ) , [b/s/Hz], (6)
where the signal-to-noise ratio (SNR) value γ is

γ =        ν|h sd + h H sr Φ Φ Φ opt,lt h rd | 2 , Long-term, (7a)
ν |h sd | + M m=1 ω m 2 , Short-term, (7b)
where

ω m = |[h sr ] m ||[h rd ] m |, ∀m.
The SNR value γ that corresponds to the short-term phase shift design is obtained by using the optimal phase shift design in [START_REF] Chien | Reconfigurable intelligent surfaceassisted Cell-Free Massive MIMO systems over spatially-correlated channels[END_REF]. As far as the long-term phase shift design is concerned, the optimal phase shift matrix Φ Φ Φ opt,lt = diag [e jθ opt,lt 1 , . . . , e jθ opt,lt M ] T is obtained in Lemma 1.

Lemma 1. If the m-th phase shift of the RIS is set as follows

θ opt,lt m = -arg([ h * sr ] m ) -arg([ hrd ] m ), (8)
then the average received SNR, E{γ} with γ given in (7a) is maximized.

Proof. The proof follows by maximizing the cost function E{γ} subject to the phase shift constraints θ m ∈ [-π, π], ∀m.

The detailed proof is omitted due to space limitations.

The phase shift design in (8) depends only on the LoS components of the channels. The short-term and long-term phase shift designs are both aimed at boosting the strength of the received signal. The short-term phase shift design is, in general, an upper-bound for the long-term phase shift design. In analytical terms, in fact, we have the following

log 2 (1 + ν|h sd + h H sr Φ Φ Φ opt,lt h rd | 2 ) (a) ≤ max {θm} log 2 (1 + γ) (b) = log 2 (1 + ν|h sd + h H sr Φ Φ Φ opt,st h rd | 2 , (9)
where Φ Φ Φ opt,st = diag [e jθ opt,st 1 , . . . , e jθ opt,st M ] T is the shortterm phase shift matrix with θ opt,st m , ∀m, defined in [START_REF] Chien | Reconfigurable intelligent surfaceassisted Cell-Free Massive MIMO systems over spatially-correlated channels[END_REF]. In particular, (a) is obtained because the phase shift solution that maximizes the average received SNR is a feasible point of the capacity maximization problem as a function of the instantaneous CSI, and (b) is obtained because the short-term phase shift design in ( 5) is the optimal solution.

COVERAGE PROBABILITY AND ERGODIC

CHANNEL RATE In this section, we introduce analytical frameworks for the coverage probability and the ergodic rate for the short-term and long-term phase shift designs.

Coverage Probability

From the channel rate in (6), we define the coverage probability for a given target rate ξ [b/s/Hz] as P cov = 1 -Pr(R < ξ), where Pr(•) denotes the probability of an event. By denoting z = 2 ξ -1, the coverage probability can be rewritten as

P cov (z) = 1 -Pr(γ < z), (10)
We utilize the moment-matching method to compute the coverage probability in [START_REF] Di Renzo | Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and the road ahead[END_REF].

Theorem 2. The coverage probability in (10) can be formulated, in a closed-form expression, as

P cov (z) ≈ Γ (k, z/w) /Γ(k), (11)
where the shape parameter k and the scale parameter w depend on the criterion for optimizing the phase shifts of the RIS elements. If the long-term phase shift design is utilized, we have

k = (β sd + o 1 β sr β rd ) 2 β 2 sd + o 2 β 2 sr β 2 rd + 2β sd o 1 β sr β rd , (12)
w = νβ 2 sd + ν 2 o 2 β 2 sr β 2 rd + 2νβ sd o 1 β sr β rd β sd + o 1 β sr β rd , (13)
where ν = ρ/σ 2 is the ratio between the transmit power and noise power, and the scalars o 1 and o 2 are defined as

o 1 = ω -1 (K sr K rd η + KM ), (14)
o 2 = ω -2 (2ηK sr K rd (M K + 4) + M 2 K 2 + 2M (2 K -1)), (15)
with η = | hH sr Φ hrd | 2 . If, on the other hand, the short-term phase shift design is considered, the shape and scale parameters are

k = k c (k c + 1) 2(2k c + 3) , w = 2νw 2 c (2k c + 3) , ( 16
)
where

k c = (c1+c2 √ βsrβ rd ) 2 c3+c4βsrβ rd and w c = c3+c4βsrβ rd c1+c2 √ βsrβ rd with c 1 = 0.5 πβ sd , c 2 = 0.25M πt sr t rd ω -0.5 , (17)
c 3 = 4 -π 4 β sd , c 4 = M - M π 2 16 t 2 sr t 2 rd ω -1 , ( 18
)
and

t sr = 1 F 1 (-0.5, 1, -K sr ), t rd = 1 F 1 (-0.5, 1, -K rd ) with 1 F 1 (•, •, •) being the confluent hypergeometric function of the first kind.
Proof. The proof is based on computing the mean and the variance of the SNR expressions in (7a) and (7b). To this end, the closed-form expressions in Theorem 1 is used. Then, the obtained mean and variance are matched to those of a Gamma distribution. The details of the proof are omitted due to space limitations.

The coverage probability in [START_REF] Björnson | Massive MIMO networks: Spectral, energy, and hardware efficiency[END_REF] offers a simple closedform expression for evaluating the performance of RISassistusually ed communications without the need of resorting to Monte Carlo simulations. As the number of RIS elements is usually sufficiently large, the obtained analytical expressions can be further simplified. If, for example, we ignore the nondominant terms, the shape parameter tends to k → (K sr K rd η + KM ) 2 /(2ηK sr K rd M K + M 2 K 2 ) for the long-term phase shift design and to k → c 1 + c 2 √ β sr β rd 2 /(4c 3 + 4c 4 β sr β rd ) for the short-term phase shift design. If M → ∞, in addition, we obtain k → 1 and k → ∞ for the long-term and short-term phase shift designs, respectively. Furthermore, the scale parameter tends to w → ν 2 o 2 β sr β rd /o 1 and to w → 4ν(c 3 + c 4 β sr β rd ) for the long-term and short-term phase shift designs, respectively. If M → ∞, we obtain w → ∞. By rewriting the Gamma function in [START_REF] Björnson | Massive MIMO networks: Spectral, energy, and hardware efficiency[END_REF] in a series expression and ignoring the highorder terms, the coverage probability in ( 11) is simplified to [START_REF] Van Chien | Coverage probability and ergodic capacity of intelligent reflecting surface-enhanced communication systems[END_REF]. Based on the obtained values of k and w, this implies that the coverage probability tends to 1 as M → ∞ for both the short-term and the long-term phase shift designs. This implies that, if the number of reconfigurable RIS elements is large enough, an RIS is capable of offering a good coverage. It is worth mentioning that the coverage probability in [START_REF] Björnson | Massive MIMO networks: Spectral, energy, and hardware efficiency[END_REF] can applied to arbitrary phase shift designs, including the random and equal phase shifts as reported in [START_REF] Van Chien | Outage probability analysis of IRS-assisted systems under spatially correlated channels[END_REF].

P cov → 1 -(z/w) k k 2 Γ(k)

Ergodic Channel Rate

The channel rate in [START_REF] Zhi | Two-timescale design for reconfigurable intelligent surface-aided Massive MIMO systems with imperfect CSI[END_REF] depends on the small-scale and largescale fading coefficients. In this section, we study the ergodic

A closed-form expression of ( 19) is given in Lemma 2 that still relies on a moment-marching approach, according to which the received SNR is matched to a Gamma distribution.

Lemma 2. The ergodic channel capacity in (19) can be formulated in the closed-form expression as follows:

R = 1 Γ (k) ln (2) G 3,1 2,3 1 w 0, 1 0, 0, k , (20)
where G m,n p,q z a 1 , . . . , a q b 1 , . . . , b p is the Meijer-G function, and, similar to Theorem 2, k and w are the shape parameter and the scale parameter of the approximating Gamma distribution, respectively.

Proof. The proof follows along the same lines as the proof in [START_REF] Van Chien | Coverage probability and ergodic capacity of intelligent reflecting surface-enhanced communication systems[END_REF], with the exception that the channel model considered in this paper is different.

Differently from [START_REF] Van Chien | Coverage probability and ergodic capacity of intelligent reflecting surface-enhanced communication systems[END_REF], Lemma 2 can be applied to all phase shift designs, which include the short-term and the long-term phase shifts designs of interest in this paper. The analytical expressions for k and w that correspond to the latter two phase designs are the same as for Theorem 2.

NUMERICAL RESULTS

In this section, we validate the obtained analytical frameworks with the aid of Monte Carlo simulations. We consider an RIS-assisted wireless network where the source is located at the origin and the center-point of the RIS is located at (27, 25, 25) m. For the direct link, the channel gain β sd [dB] is β sd = -33.1 -3.50 log 10 (d sd /1m), where d sd is the distance between the source and the destination. For the indirect link, the channel gains β α [dB] are β α = -25.5 -2.4 log 10 (d α /1m), where d α is the distance between the transmitter and the receiver. The Rician factors are equal to K α = 10 1.3-0.003dα . The transmit power is 20 mW and the system bandwidth is 10 MHz. The carrier frequency is 1.8 GHz and the noise power is -94 dBm. The following phase shift designs are considered for comparison: i) the short-term phase shift design in [START_REF] Chien | Reconfigurable intelligent surfaceassisted Cell-Free Massive MIMO systems over spatially-correlated channels[END_REF]; ii) the long-term phase shift design in (8); iii) the equal phase shift design where the phase shifts are all set equal to π/4; and iv) the random phase shift design where arbitrary values in the range [-π, π] are considered.

In Fig. 1(a), we compared the closed-form expression of the coverage probability against Monte Carlo simulations. The good overlap between the analytical results and the numerical simulations confirms the accuracy of [START_REF] Björnson | Massive MIMO networks: Spectral, energy, and hardware efficiency[END_REF]. In Fig. 1(b), we utilize the analytical framework in [START_REF] Björnson | Massive MIMO networks: Spectral, energy, and hardware efficiency[END_REF] to evaluate the coverage probability as a function of the number of RIS elements and for different designs of the phase shifts. The phase shift designs based on short-term and long-term CSI offer significant gains compared to the equal and random phase shift designs. In addition, the gap between the short-term and long-term phase shifts design reduces as the number of RIS elements increases. Finally, Fig. 1(c) displays the ergodic rate [b/s/Hz] in (20). We evince that the deployment of an RIS results in a substantial increase of the ergodic rate, as opposed to surfaces that operate as random scatterers and are not smart and reconfigurable. Notably, the long-term phase shift design provides an ergodic rate that is close to the short-term phase shift design, and approaches it if the number of RIS elements is sufficiently large.

CONCLUSION

This paper has investigated the coverage probability and the ergodic rate of an RIS-assisted link for different phase shift designs depending on the amount of channel information that is exploited for optimizing the RIS. It is shown that a longterm phase shift design that depend on long-term CSI offers a suboptimal solution with a performance loss compared with the optimal phase shift design based on perfect CSI that decreases as the number of RIS elements increases. Generalization of this research work includes the analysis of sources and destinations equipped with multiple antennas.

Fig. 1 .

 1 The system performance: (a) Coverage probability v.s. the target rate [b/s/Hz] with M = 100 and the destination is located at (180, 15, 15) m; (b) Average coverage probability (defined as E{Pr(R > ξ)}, which is averaged over different realizations of the destination's location) v.s. the number of RIS elements; and (c) Ergodic rate v.s. the number of RIS elements. channel rate over a long time period by averaging out the small-scale fading as follows R = E{log 2 (1 + γ)}, [b/s/Hz].

This work was partially supported by RISOTTI-Reconfigurable Intelligent Surface for Smart Cities under ProjectFNR/C20/IS/14773976/RISOTTI.