Issam Mabrouki
email: mabrouki@tcl.ite.mee.com

Xavier Lagrange
email: xavier.lagrange@enst-bretagne.fr

Gwillerm Froc
email: froc@tcl.ite.mee.com

Random Walk Based Routing Protocol for Wireless Sensor Networks

Keywords: Sensor networks, Routing, Random Walk, Data Gathering

In recent years, design of wireless sensor networks using methodologies and mechanisms from other disciplines has gained popularity for addressing many networking aspects and providing more flexible and robust algorithms. We address in this paper the problem of random walk to model routing for data gathering in wireless sensor networks. While at first glance, this approach may seem to be overly simplistic and highly inefficient, many encouraging results that prove its comparability with other approaches have been obtained over the years. In this approach, a packet generated from a given sensor node performs a random motion until reaching a sink node where it is collected. The objective of this paper is to give an analytical model to evaluate the performance of the envisioned routing scheme with special attention to two metrics: the mean system data gathering delay and the induced spatial distribution of energy consumption. The main result shows that this approach achieves acceptable performance for applications without too stringent QoS requirements provided that the ratio of sink nodes over the total number of sensor nodes is carefully tuned.

INTRODUCTION

Random walks have been studied extensively in a large number of interdisciplinary works, to which mathematicians, physicists, chemists, engineers, and others have toiled and all made significant contributions. More recently, connection with networking research area have been established providing a variety of algorithms including routing, selfstabilization, data gathering and query processing in wireless networks, peer-to-peer networks and other distributed systems [START_REF] Lima | Random walks on sensor networks[END_REF][START_REF] Alanyali | A random-walk model for distributed computation in energy-limited network[END_REF][START_REF] Dolev | Random walk for self-stabilizing group communication in ad-hoc networks[END_REF][START_REF] Avin | Efficient and robust query processing in dynamic environments using random walk techniques[END_REF][START_REF] Gkantsidis | Random walks in peer-to-peer networks[END_REF][START_REF] Servetto | Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks[END_REF]. In wireless sensor networks (WSNs) research area, this approach is gaining popularity because random walk techniques present locality, simplicity, low overhead and inherent robustness to structural changes. Such networks, formed by a large number of small, simple, battery-operated and resource-constrained nodes, are usually subject to dramatic structural changes created by sleep modes, channel fluctuations, mobility, frequent device failures, and other factors. Therefore, topology-driven algorithms are at a disadvantage for such networks as they induce high overhead to maintain up-to-date topology and routing information, and also have to provide recovery mechanisms for critical points of failure (e.g., cluster heads, nodes close to the root in a spanning tree). By contrast, stateless algorithms, such as the random walk, require no knowledge of network topology to make decisions, and thus, fit better the WSN constraints but often at the expense of QoS support.

Many earlier recent research efforts have raised this vision by focusing primarily on basic properties of random walks. For example, in [START_REF] Lima | Random walks on sensor networks[END_REF] the authors addressed the problem of data gathering in large-scale WSNs with static sensor nodes and one mobile collector node that performs a random walk on a square lattice. Whenever the collector node enters the transmission range of a sensor node, the data are collected. In this context, the authors derived analytical bounds for the expected number of distinct visited sensor nodes within a given time frame. To improve this performance metric, they proposed a practical algorithm that constrains the random walk and validated it by simulations. Constrained random walk techniques, already suggested in [START_REF] Servetto | Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks[END_REF] for multipath routing, have the advantage to achieve load balancing property in uncontrolled dynamics characterized by random ON-OFF transitions to save energy. Besides the load balancing property, which is difficult to achieve for other routing protocols, it is also proven in [START_REF] Tian | Random walk routing for wireless sensor networks[END_REF] that a random walk based routing in regular patterned WSNs consumes the same amount of energy as the shortest path routing provided that messages are of small size, which characterizes many WSN applications.

Throughout the variety of random walk based algorithms in WSN area, we realize that most of the results are derived from a qualitative view or by means of simulations and that little analytical studies use the powerful techniques of random walk theory. In addition, these results often provide lower and upper bounds on system performance and not a closed form analytical evaluation [START_REF] Lima | Random walks on sensor networks[END_REF][START_REF] Avin | Efficient and robust query processing in dynamic environments using random walk techniques[END_REF][START_REF] Servetto | Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks[END_REF]. Instead, our take in this paper is to obtain a fundamental insight into random walk performance by constructing an analytical model that owes much to the powerful analytic tools developed in the physics community [START_REF] Lindenberg | Lattice random walks for sets of random walkers. first passage times[END_REF][START_REF] Montroll | Random walks on lattices[END_REF][START_REF] Liyanage | A bibliography on applications of random-walks in theoretical chemistry and physics[END_REF]. In particular, we address here the problem of data gathering in WSNs comprised of a large number of sensor nodes and a smaller number of sink nodes to gather, process and control data. A packet generated at any sensor node performs a random walk until it reaches a sink node for the first time. At this moment, we consider that the data gathering process occurs with success. Our motivation for considering random walks in this context comes from the following observations. First, the many important papers of Scher and his collaborators [START_REF] Scher | Stochastic transport in a disordered solid. I. theory[END_REF] for modeling stochastic transport in the physics community strongly influenced us to use this approach but from a networking view. Second, to cope with the resource constraint, the multihop strategy is better, since the transmission energy consumption dominates the total power consumption induced by the circuitry of active nodes [START_REF] Chakrabarti | Multi-hop communication is order-optimal for homogeneous sensor networks[END_REF][START_REF] Chen | Energy efficient system design with optimum transmission range for wireless ad hoc networks[END_REF][START_REF] Ergen | On multi-hop routing for energy efficiency[END_REF]. Third, searching a large space of possible routes derived from having a large number of nodes may prove computationally prohibitive for low complexity devices such as sensor nodes. Thus, without any state information, sensor nodes would blindly forward data. This leads to the Unicast Random Walk based Routing (URWR).

The remainder of this paper is organized as follows. A formal network model description followed by backgrounds and theoretical elements of random walk theory are given in Section II. In section III, which forms our original contribution, we focus on the URWR performance with prior attention to two performance metrics: the mean system data gathering delay and the induced spatial distribution of energy consumption. Finally, we conclude this paper in section IV.

RANDOM WALK MODEL

Network Description

We consider a graph G(Ω, E) where Ω is a countable set of nodes wirelessly connected pairwise by a set E of undirected arcs or edges to represent communication links between nodes. At a given node r, let Z( r) = { s1, • • • , s l r } be the set of neighbors of r. Let π r = {p1, • • • , p l r } be nonnegative reals such that i pi = 1. This defines a transition probability distribution over the neighbors of r. When a packet reaches node r, the next hop is chosen by tossing a die whose i-th face occurs with probability pi, and the packet is then forwarded over the link ( r, si). The random sequence of nodes selected this way is a random walk on graph G(Ω, E).

By making different assumptions on the topology of the underlying network and on constraints imposed on π r , we are

0 N -1 N -1 0 N -1 N -1 (a) (b)
Figure 2: Equivalence between the infinite periodic square lattice (a) and the torus lattice (b). For the sake of clarity, we have deliberately missed some transitions except for the origin.

able to explore a large space of possible routing schemes. In particular, we consider in this paper a regular deployment topology where nodes are spread over an area of interest with a hexagon lattice pattern (or equivalently an equilateral triangular lattice). This pattern is of fourfold interest. First, many WSN applications are often desired to follow regular patterns for at least two reasons: (i) convenience of deployment and (ii) to achieve a higher degree of connectivity. Second, under full sensing coverage requirement, the hexagon lattice has the lowest node density [START_REF] Kershner | The number of circles covering a set[END_REF], which is important for economic reasons. Third, sensor placement can be viewed as spatial sampling from signal processing perspective. The literature there also suggests the superiority of hexagonal sampling lattice over the square lattice when the spatial spectrum of 2-D signal being measured (such as a temperature field) is bandlimited with a circular support. Finally, with a communication range rc ≥ √ 3rs, where rs stands for the sensing range, the hexagon lattice pattern provides both coverage and connectivity [START_REF] Bai | Deploying wireless sensors to achieve both coverage and connectivity[END_REF].

In this paper, we consider the case where rc = √ 3rs which corresponds to a 6-connectivity. Moreover, it is assumed that there is unbiased random motion, so that all of the 6 possible next steps away from the current position are equally likely, each having probability 1 6 . There exist two kinds of network nodes: sensor nodes and a smaller number of sink nodes distributed in a regular way, one sink node for every N 2 vertices without any specific mapping between sensor and sink nodes. A packet generated at a given sensor node performs then a random walk until it reaches a sink node for the first time. At this moment, we consider that the data gathering process occurs with success.

As illustrated in Figure 1, the induced network has a periodic structure, in which each unit cell of size N × N and in the form of a rhombus contains N 2 -1 sensor nodes and 1 sink node. Since we are interested only in which nodes are connected to which, not in the visual appearance of the unit cell, we may transform this unit cell to obtain a new cell in the form of a square lattice of size N ×N with one additional diagonal bond inserted in each fundamental square. The obtained cell has the advantage that we can assign to nodes integer coordinates while maintaining the original network topology. With a large number of unit cells and recalling the assumption that there is no specific mapping between sensor nodes and sink nodes, we can assume that the formed network is infinite and hence, it is equivalent to a torus lattice T formed by connecting the opposite ends of the square unit cell (Figure 2). Therefore, in the remainder of this paper we investigate the URWR in reference to torus lattice T . Every node s ∈ T is labeled with (s1, s2), where s1 and s2 are integers such that 0 ≤ s1, s2 ≤ N -1. The obtained results will be valid for the original network. However, before investigating the performance of the URWR, we introduce in the following backgrounds and theoretical elements of random walk theory that will be used to evaluate the URWR. Deeper discussions of random walk results can be found in [START_REF] Hughes | Random Walks and Random Environments[END_REF].

Elements of Random Theory

Node Occupation and First-Passage Probabilities

We define, for n ≥ 1, Pn( r, s) the probability of being at node s after n hops, given that the packet has been issued at node r. We also define Fn( r, s) the probability of arriving at node s for the first time on the nth hop, given that the walk started at node r. We shall refer to these probabilities as the node occupation probability and the first-passage probability respectively. By convention we have P0( r, s) = δ r s and F0( r, s) = 0.

We make use in this paper of the generating function formalism [START_REF] Lando | Lectures on Generating Functions[END_REF] to deal with a sequence {cn} n∈N by capturing all these coefficients into a formal infinite series defined as C(z) = ∞ n=0 cn z n where the complex variable z is small enough to ensure the convergence of this series. C(z) is called the generating function associated with {cn} n∈N . The interest of this formalism arises especially in probability theory to completely characterize a discrete random variable by associating a generating function to its probability distribution. Once the generating function is determined, a lot of information about the random variable, such as the expectation or the variance, can be then derived.

In the following, we denote the generating functions associated with {Pn( r, s)} n∈N and {Fn( r, s)} n∈N as P ( r, s|z) and F ( r, s|z) respectively. Hereafter we present two well-known classical relations extensively used in random walk theory, and upon which the theoretical results derived in this paper rely.

Lemma 1. At fixed r, P ( r, s | z) satisfies the normaliza- tion condition s∈T P ( r, s | z) = 1 1 -z • (1)
Proof. As long as there is no possibility that the packet is removed from T at any time n (this is so for the walks considered here), Pn( r, s) is a distribution over the nodes of T at fixed n and r, which leads to s∈T Pn( r, s) = 1, for all n ≥ 0. By taking the generating functions of both sides of this relation, (1) follows.

F ( r, s | z) = P ( r, s | z) -δ r s P ( s, s | z) , r, s ∈ T. (2)
Proof. The proof is presented in Appendix A.

Random Walk Characterization

A key issue in the problem of random walk is the resolution of the following question: how likely does the walk evolve in the future under some initial conditions? Answering this question consists in finding an explicit expression of P ( r, s | z), which completely determines the node occupation probability distribution. Globally, throughout the large number of interdisciplinary works in random walk theory, the exact closed-form solution was mostly carried out under restrictive conditions such as the periodicity of the network, the homogeneity of the system and the infiniteness of the structure on which the random walk takes place. Among these special cases, the problem of random walk on finite lattice with periodic boundary conditions (i.e., toroidal lattices) has been extensively studied. The investigation of this type of system was motivated by many situations and process encountered in statistical mechanics, solid state theory (e.g., diffusion of electrons, excitons, energy transfer, conductivity, dislocations). Montroll and Weiss [START_REF] Montroll | Random walks on lattices[END_REF] originally proposed this special problem and solved it for k-dimension. In particular, in case of square lattice with diagonal bond, they established an explicit expression of P (0, s | z), that is

P (0, s | z) = 1 N 2 m∈T e -i 2π N m• s 1 -zλ( 2π N m) (3)
where function λ( θ) is defined on R 2 as

λ( θ) = 1 3 cos(θ1) + cos(θ2) + cos(θ1 -θ2) .
Even though relation (3) does not give a simple form of P (0, s | z), it is of great importance and represents our basic relation upon which relies most of our contribution in this paper.

PERFORMANCE ANALYSIS

In the present section, we investigate the performance of the URWR. We shall focus our attention primarily on two performance metrics: (i) how long does it take for the data gathering process and (ii) how much energy does it require? These two metrics, which characterize the global system behavior, are analytically studied by using the general formalism introduced in subsection 2.2. We first focus on (i) the system data gathering delay and then (ii) the spatial distribution of the energy consumption.

System Data Gathering Delay

We define the data gathering delay of a packet at a given sensor node s as the time or the number of hops it takes to reach the sink node for the first time after it leaves sensor node s. The system data gathering delay is then obtained by averaging the packet delay over all sensor nodes contained in T . This time is a random variable denoted by DN . We consider here a uniform traffic distribution, that is, a packet has the probability 1 N 2 -1 of being generated at any sensor node in T . For studying the mean system data gathering delay, we determine first the generating function associated with the probability distribution of random variable DN .

Generating Function Analysis of DN

Suppose that at time n = 0 a packet has the probability 1 N 2 -1 of being generated at any sensor node in T . If Gn(N ) denotes the probability that the packet will reach the sink node for the first time on the nth hop, then in terms of probability notation we have

Pr DN = n = Gn(N ), n ≥ 0.
Using now the law of total probability, it is possible to decompose the event that a packet generated anywhere will reach the sink node for the first time on the nth hop, which has the probability Gn(N ), into the N 2 -1 mutually exclusive events that the packet is initially released at sensor node s with probability 1 N 2 -1 , and then arrives at the sink node for the first time after n hops, which has the probability Fn( s, 0). Thus, Gn(N ) can be expressed as

Gn(N ) = 1 N 2 -1 s =0 Fn( s, 0), n ≥ 0.
Multiplying both sides of this relation by z n and summing over all n yield

G(N | z) = 1 N 2 -1 s =0 F ( s, 0 | z),
where G(N | z) stands for the generating function associated with sequence {Gn(N )} n∈N . Then, from (2) we obtain

G(N | z) = 1 N 2 -1 s =0 P ( s, 0 | z) P (0, 0 | z) = 1 (N 2 -1)P (0, 0 | z) s∈T P ( s, 0 | z) -P (0, 0 | z) .
However, since it it assumed that there is no directional bias on any hop, the considered random walk is symmetric and therefore we have P ( s, 0 | z) = P (0, s | z). Further, using the normalization condition stated in (1), we find

G(N | z) = 1 N 2 -1 1 (1 -z) P (0, 0 | z) -1 • (4)
Various statistics of the system data gathering delay can be now extracted from this key relation using the general formalism of generating function. In particular, we propose next to derive the mean system data gathering delay, i.e., the expectation of DN denoted by E(DN ).

Mean System Data Gathering Delay

The mean system data gathering delay can be written as

E(DN ) = ∞ n=0 n Gn(N ) = lim z→1 - ∂ ∂z G(N | z)•
Although this formula does not give an explicit expression of the mean system data gathering delay, we can fortunately extract a closed-form by a Taylor 's series expansion of G(N | z) at point z = 1. Indeed, the limit of the first derivative of G(N | z) as z → 1 -is nothing but the firstorder term of its Taylor 's series. To obtain the first order Taylor 's series expansion of G(N | z) at point z = 1, we proceed as follows. We first calculate the asymptotic expansion of P (0, 0 | z) as z → 1, which is obtained by setting s = 0 in the asymptotic expansion of P (0, s | z) as z → 1 given by [START_REF] Servetto | Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks[END_REF] in Appendix B. Second, by plugging the asymptotic expansion of P (0, 0 | z) as z → 1 into (4), we obtain

G(N | z) = 1 + N 4 1 + 4ϕN (0, 1) -N 2 4(N 2 -1) (z -1) + o(z -1)
where ϕN (0, 1) is an N -dependent series obtained by setting s = 0 and z = 1 in ϕN ( s, z) defined by [START_REF] Scher | Stochastic transport in a disordered solid. I. theory[END_REF] in Appendix B.

By differentiating this Taylor 's series expansion with respect to z and then taking the limit as z → 1 -, we obtain the following closed-form expression of the mean system data gathering delay

E(DN ) = 1 4 N 2 + N 4 N 2 -1 ϕN (0, 1). ( 5
)
Some general remarks can be drawn from the previous results. First, from the first-order Taylor 's series expansion, the value of G(N | z) at point z = 1 is equal to unit, which represents the probability that the sink node is ever reached by a packet generated anywhere in the network. This means that the data gathering process ensured by the URWR is certain. Second, referring to (5), the mean system data gathering delay is finite and depends only on the size of a unit cell via parameter N . To study this dependence, one has to estimate series ϕN (0, 1). Two ways are possible. First, the mean system data gathering delay is estimated by a numerical calculation of series ϕN (0, 1). A second way consists in approximating E(DN ) by an asymptotic expansion of series ϕN (0, 1) as N → ∞, which is provided by (21) in Appendix C. Plugging (21) into ( 5), we obtain our first analytical result Result 1.

E(DN ) = √ 3 π N 2 ln(N ) + N 2 √ 3 π γ + √ 3 π ln( √ 3 π ) + ℓ + 1 4 + √ 3 π ln(N ) + √ 3 π γ + ln( √ 3 π ) + √ 3 3 πℓ + √ 3 π ln(N ) N 2 + O( 1 N 2 )• (6)
where "O" stands for the "Big-O" Landau symbol, γ is the Euler's constant (γ = 0.5772156649) and ℓ = -0.0047473394.

Discussion

As mentioned earlier, the main question we want to ask in this paper is to what extend the URWR can be efficient while being simple and light. In this section, we have focused on the mean system data gathering delay as a performance metric of the URWR. As shown by Result 1, this performance metric depends only on cell size or equivalently on the number of sensor nodes to be spread per sink node. This result is of threefold interest. First, the dependence of the achievable mean system data gathering delay on cell size alone and not on the overall network size shows that the URWR can scale up with the network size. Second, it is not necessary that N be very large for approximation formula (6) to be numerically useful. For N = 3, ( 6) gives E(D3) = 8.226 hops, which is only about 0.29 per cent different from the exact result from ( 5) that E(D3) = 8.25 hops. Third, it is always possible to guarantee an acceptable mean system data gathering delay provided that the number of sensor node per sink node is carefully tuned. Thus, approximation formula (6) can be put into practical use for WSN dimensioning with respect to crucial parameters such as the minimum ratio of sink nodes to be deployed over the total number of sensor nodes while ensuring a required threshold mean system data gathering delay.

Concretely, consider now IEEE 802.15.4 enabled network nodes with maximum and minimum supported data rates of 250 kbps and 20 kbps respectively. Since in many applications of WSNs, sensor nodes often send only beep-like small packets to the sink node to report their status, we can assume here an average packet size of about 10 bytes. Therefore, the minimum achievable mean system data gathering delay for the maximum data rate is about 938 µs while for the minimum data rate, it is about 11.7 ms. This corresponds to 2.93 hops for a unit cell of size N 2 = 4 nodes. However, as illustrated in Figure 3, to guarantee a mean system data gathering delay threshold of 1 s, the unit cell size should not exceed N 2 = 37 2 nodes for the maximum data rate, and N 2 = 12 2 for the minimum data rate. As these values approach upper bounds of practical interest, we can conclude that for applications without too stringent required delay, which often characterize a large range of WSN applications, the URWR can perform acceptable performance in terms of delay provided that the number of sensor nodes to be deployed per sink node is well managed.

Energy Consumption

Besides the mean system data gathering delay, another important performance metric of the URWR is the energy consumption: how much energy does it require for a packet to be gathered by a sink node? We do not take here into account all possible sources of energy consumption, but only the contribution of the URWR induced by successive transmissions/receptions at relay sensor nodes. A straightforward metric that measures the successive transmissions/receptions cost is the number of visits of a packet to a relay sensor node before reaching the sink node. At a given relay sensor node s, we denote by VN ( s) the number of visits during the random walk before visiting the sink node, and we assume again a uniform traffic distribution. In the following, we first put this physical picture into a mathematical form and then evaluate at relay sensor node s the mean number of visits denoted by E VN ( s) .

Sink-Avoiding Node Occupation Probability

Let us define P † n ( r, s) as the probability of being at relay sensor node s on the nth hop before reaching the sink node, given that the packet has been initially issued at sensor node r. We refer to this probability as the sink-avoiding node occupation probability. We show next how P † n ( r, s) and Pn( r, s) are related to each other. Indeed, using the law of total probability, it is possible to decompose the event that a packet generated at sensor node r will be at relay sensor node s on the nth hop, which has the probability Pn( r, s), into the two exclusive events: (i) the packet visits sensor node s on the nth hop before visiting the sink node, which has the probability P † n ( r, s), (ii) the packet first arrived at the sink node after j hops and subsequently performed a walk of n -j hops arriving at sensor node s, which has the probability Fj ( r, 0)Pn-j ( 0, s). Thus,

Pn( r, s) = P † n ( r, s) + n j=0
Fj ( r, 0)Pn-j (0, s), n ≥ 0.

Multiplying both sides by z n , summing over all n and observing that the convolution of two sequences corresponds to the multiplication of their generating functions, we obtain

P ( r, s | z) = P † ( r, s | z) + F ( r, 0 | z)P (0, s | z) (7)
where P † ( r, s | z) stands for the generating function associated with {P † n ( r, s)} n∈N . Then, substituting the expression of F ( r, 0 | z) given by ( 2) into (7) yields this key relation

P † ( r, s | z) = P ( r, s | z) -P (0, s | z) P ( r, 0 | z) P (0, 0 | z) . (8)
Next, we evaluate the mean number of visits E VN ( s) based on this relation.

Mean Number of Visits

Let us suppose that at time n = 0 a packet has the probability 1 N 2 -1 of being generated at any sensor node in T . At a given relay sensor node s, we define an indicator random variable In( s), which takes the value 1 if relay sensor node s is visited by the packet on the nth hop before reaching the sink node, and is zero otherwise. Let us also define Hn( s) and H( s | z) the probability that relay sensor node s is visited on the nth hop by the packet before reaching the sink node and its associated generating function respectively, so that, in terms of probability notation we have Pr In( s) = 1 = Hn( s).

Therefore, it can be deduced that the number of visits of the packet to relay sensor node s before reaching the sink node during the walk is simply

VN ( s) = ∞ n=0
In( s), and hence,

E VN ( s) = E ∞ n=0 In( s) = ∞ n=0 E In( s) = ∞ n=0 Hn( s) = lim z→1 - H( s | z).
Now, it remains to make explicit H( s | z). Using the law of total probability, it is possible to decompose the event that a packet generated at any sensor node will visit relay sensor node s on the nth hop before visiting the sink node, which has the probability Hn( s), into the N 2 -1 mutually exclusive events that the packet is initially generated at sensor node r with probability 1 N 2 -1 , and then visits relay sensor node s after n hops before visiting the sink node, which occurs with probability P † n ( r, s). Thus, we obtain By multiplying both sides by z n and summing over all n, we obtain

Hn( s) = 1 N 2 -1 r =0 P † n ( r, s), n ≥ 0.
H( s | z) = 1 N 2 -1 r =0 P † ( r, s | z). (9)
Finally, by plugging ( 8) into ( 9), using successively the symmetric property of P ( r, 0 | z) and the normalization condition stated in (1), we find

H( s | z) = 1 (N 2 -1)(1 -z) 1 - P (0, s | z) P (0, 0 | z) • (10)
Since the mean number of visits is defined as the limit of

H( s | z) as z → 1 -, a zero-order Taylor 's series expansion of H( s | z) at point z = 1 is sufficient to derive E VN ( s) .
Likewise the calculation of the mean system data gathering delay, we proceed first to evaluate the asymptotic expansion of P (0, s | z) P (0,0 | z) as z → 1 -, which can be derived from [START_REF] Servetto | Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks[END_REF] in Appendix B. Second, after elementary calculus, we obtain the limit of H( s | z) as z → 1 -, i.e., E VN ( s) as follows

Result 2. E VN ( s) = N 2 N 2 -1 ϕN (0, 1) -ϕN ( s, 1) + 3s2(N -s2) 2(N 2 -1) • (11)
where ϕN ( s, 1) is a series obtained by setting z = 1 in ϕN ( s, z) defined by [START_REF] Scher | Stochastic transport in a disordered solid. I. theory[END_REF] in Appendix B.

Discussion

Some general remarks can be drawn from Result 2. First, note that the mean number of visits depends on both cell size via parameter N , and the position of relay sensor node s. This is predictable since the nodes of T are not equivalent: sensor nodes in the vicinity of the sink node are not equivalent to those in the middle of the cell. Second, as shown in Figure 4, the mean number of visits achieved far away from the sink node is much closer to uniform and with higher values than the one in the vicinity of the sink node. Then we can conclude that the URWR achieves a load balancing property. Intuitively, this can be explained by the fact that a packet visiting a relay sensor node located in the vicinity of the sink node is more likely to reach it during the next fewer hops than when visiting a relay sensor node far away from the sink node, and thus, it is more likely to return once again to the latter relay sensor node. In other words, the proximity to the sink node decreases the likelihood of the return to the initial position. In this way, relay sensor nodes in the middle of the cell are expected to be more visited than the others. This is consistent with Figure 4. Interestingly enough, and at first glance surprising to us -although rather obviously with the benefit of hindsight-is the fact that the energy consumption distribution achieved along the diagonal between the upper left corner and the lower right corner is lower than the one along the opposite diagonal. This can be explained by the fact that only hops along the former diagonal are allowed and hence, accelerating random walks along this direction.

Although there is no unified definition of network lifetime, as this concept depends on the objective of an application, we adopt here a common definition which characterizes the network lifetime as the time until the first node in the network depletes its energy. In case of the URWR, the first node that depletes its energy corresponds to the most visited node during the data gathering process. As illustrated in Figure 5, the maximum mean number of visits grows logarithmically with large values of N . Therefore, the network lifetime does not degrade quickly when the number of sensor nodes per sink node increases.

Let us now consider a practical case where nodes are equipped with the MC13192, an IEEE 802.15.4 compliant radio transceiver from Freescale Semiconductor [START_REF] Mc | 4 GHz low power transceiver for the IEEE[END_REF], which offers a data rate of 250 kbps and operates in transmit/receive mode at (30 mA, 2.7 V) and (37 mA, 2.7 V) respectively. Since a visit to a sensor node counts for one reception followed by one transmission, the energy required for a 10 byte message per visit is about 57.88 µJ. Therfore, for a given energy source and a frequency for measure updates, it is possible to derive the network lifetime for a given cell size based on Figure 5.

CONCLUSION

In this paper we addressed the problem of random walk to model data gathering in large-scale WSNs with regular structure. Our motivation for this approach comes from the inherent properties of random walks such as the locality, the simplicity and the robustness to structural changes. We presented a mathematical formulation of the problem of random walk that largely owes to the powerful theoretical tools developed in the physics community. Using the generating function formalism, we established closed-form expressions for the mean system data gathering delay and the energy consumption based on the mean number of visits.

Our main results could be summarized as follows. First, the dependence of the achievable mean system data gathering delay on only the ratio of sink nodes over the total number of sensor nodes shows that the random walk can scale with the network size. Second, it is always possible to guarantee an acceptable mean system data gathering delay for delay-tolerant applications provided that this ratio is carefully tuned and that the packets are of small size. Third, as regards to energy consumption, the random walk achieves a load balancing property.

There are several interesting directions that extend the model presented in this paper. This consists for instance in deriving other significant statistics of the random walk such as the dispersion of the system data gathering delay, studying biased random walks to improve performance and considering other network topologies such as the square lattice, which will be soon published.

APPENDIX A. PROOF OF LEMMA 2

The event "the packet is at node s after n hops, given that the walk started at node r", which has the probability Pn( r, s), can be decomposed into n mutually exclusive events "the packet first arrived at node s after j hops and subsequently performed a walk of n -j hops returning to node s", with probabilities Fj ( r, s)Pn-j ( s, s). Thus

Pn( r, s) = n j=1 Fj ( r, s)Pn-j ( s, s), n ≥ 1.
If this sum is interpreted as void when n = 0, recalling the convention that P0( r, s) = δ r s and F0( r, s) = 0, we may rewrite this relation as Pn( r, s) = δ r s δ0n + n j=0 Fj( r, s)Pn-j( s, s), n ≥ 0.

Taking the generating functions of both sides yields (2).

B. ASYMPTOTIC ANALYSIS OF

P (0, S | Z) B.1 Singularity of P (0, s | z) at z = 1
We propose here to simplify the expression of P (0, s | z) given by ( 3) and to study its singularity at point z = 1. By factorizing the denominator of the summand and using the addition theorems of trigonometric functions, we obtain

P (0, s | z) = 1 N 2 N-1 m 1 =0 N-1 m 2 =0 e -i 2π N m 1 s 1 1 -z 3 cos( 2π N m1) × e -i 2π N m 2 s 2 1 -cm 1 (z) cos π N (m1 -2m2) = 1 N 2 N-1 m 1 =0 e -i 2π N m 1 s 1 1 -z 3 cos( 2π N m1) × Sm 1 (z) (12)
where functions cm 1 (z) and Sm 1 (z) are defined as

cm 1 (z) = 2z cos( π N m1) 3 -z cos( 2π N m1) (13a) Sm 1 (z) = N-1 m 2 =0 e -i 2π N m 2 s 2 1 -cm 1 (z) cos π N (m1 -2m2) • (13b)
Next, we propose to simplify Sm 1 (z). The first step is to see from (13a) that 0 < |cm 1 (z)| < 1 for 0 < z < 1 unless m1 = N 2 , which occurs only when N is even. In this case, c N 2 (z) = 0 and we find S N 2 (z) = N δ0, s 2 where the delta symbol stands for the Kronecker symbol. Let us now assume that m1 = N 2 , so that, by using the exponential representation of trigonometric functions, Sm 1 (z) can be written as follows

Sm 1 (z) = - 2 cm 1 (z) N-1 m 2 =0 e i π N (m 1 -2m 2 (1+s 2 )) e i π N (m 1 -2m 2 ) -αm 1 (z) × 1 e i π N (m 1 -2m 2 ) -α -1 m 1 (z)
where αm 1 (z) is the smaller root of the equation

X 2 - 2 cm 1 (z) X + 1 = 0
whose discriminant is nonnegative. Thus, we find

αm 1 (z) = 1 -1 -c 2 m 1 (z) cm 1 (z) • (14)
Using partial fraction decomposition, Sm 1 (z) becomes

Sm 1 (z) = 1 -c 2 m 1 (z) -1 2 N-1 m 2 =0 e -i 2π N m 2 s 2 1 -αm 1 (z) e -i π N (m 1 -2m 2 ) + αm 1 (z) e i π N (m 1 -2m 2 (1+s 2 )) 1 -αm 1 (z) e i π N (m 1 -2m 2 )
• Noting that |αm 1 (z)| < 1, it is then possible to expand each sum involved in Sm 1 (z) by using successively the expansion 1/(1 -x) = ∞ k=0 x k and the identity

N-1 m=0 e i 2π N mn = N for n = 0, ± N, ± 2N, • • • 0 otherwise.
which can be derived by remarking that the vectors e i 2π N mn form an orthogonal basis over the set of N-dimensional complex vectors. Therefore, we obtain [START_REF] Lindenberg | Lattice random walks for sets of random walkers. first passage times[END_REF] which is established for m1 = N 2 and 0 < z < 1. However, when cm 1 (z) → 0, which occurs at m1 → N 2 , αm 1 (z) goes to zero. Thus, if we extend the expression [START_REF] Lindenberg | Lattice random walks for sets of random walkers. first passage times[END_REF] to include m1 = N 2 , we obtain S N

Sm 1 (z) = N e -i π N m 1 s 2 1 -c 2 m 1 (z) 1 2 × α s 2 m 1 (z) + α N-s 2 m 1 (z) cos(πm1) 1 -α N m 1 (z) cos(πm1)

2

(z) = N δ0, s 2 , which is consistent with (13b). Therefore [START_REF] Lindenberg | Lattice random walks for sets of random walkers. first passage times[END_REF] holds for all 0 ≤ m1 ≤ N -1.

Finally, by substituting ( 15) into [START_REF] Kershner | The number of circles covering a set[END_REF], we obtain

P (0, s | z) = 1 N N-1 m 1 =0 e -i π N m 1 (2s 1 +s 2 ) 1 -z 3 cos( 2π N m1) 1 -c 2 m 1 (z) 1 2 × α s 2 m 1 (z) + α N-s 2 m 1 (z) cos(πm1) 1 -α N m 1 (z) cos(πm1) • (16)
Note that the summand involved in ( 16) is holomorphic over 0 < z < 1 for all 0 ≤ m1 ≤ N -1. However, it diverges at z = 1 when m1 = 0. Thus, the singularity of P (0, s | z) at z = 1 comes only from the first term of the sum given by [START_REF] Liyanage | A bibliography on applications of random-walks in theoretical chemistry and physics[END_REF]. It is convenient therefore to separate out the singular and non-singular parts of P (0, s | z) as follows

P (0, s | z) = √ 3 N (1 -z) 1 2 (3 + z) 1 2 × α s 2 0 (z) + α N-s 2 0 (z) 1 -α N 0 (z) + ϕN ( s, z) (17)
where

ϕN ( s, z) = 1 N N-1 m 1 =1 e -i π N m 1 (2s 1 +s 2 ) 1 -z 3 cos( 2π N m1) 1 -c 2 m 1 (z) 1 2 × α s 2 m 1 (z) + α N-s 2 m 1 (z) cos(πm1) 1 -α N m 1 (z) cos(πm1) (18)
is holomorphic at z = 1. The first term involved in [START_REF] Montroll | Random walks on lattices[END_REF] corresponds to the term m1 = 0 in [START_REF] Liyanage | A bibliography on applications of random-walks in theoretical chemistry and physics[END_REF], and the second term, ϕN ( s, z), corresponds to the sum 1 ≤ m1 ≤ N -1.

B.2 Asymptotic expansion of

P (0, s | z) as z → 1
To obtain the zero-order asymptotic expansion of P (0, s | z) as z → 1, let us successively expand the first term of P (0, s | z) involved in [START_REF] Montroll | Random walks on lattices[END_REF] and then function ϕN ( s, z) close to z = 1. After expanding function α0(z), it can be deduced that √ 3

N (1 -z) 1 2 (3 + z) 1 2 × α s 2 0 (z) + α N-s 2 0 (z) 1 -α N 0 (z) = 1 N 2 (1 -z) + N 2 -6N s2 + 6s2 2 -1 4N 2 + o (1 -z) 1 2
.

Using now the Taylor 's Theorem, ϕN ( s, z) can be represented by its zero-order Taylor series expansion at z = 1

ϕN ( s, z) = ϕN ( s, 1) + o (1 -z) 1 2 .
Finally, combining this asymptotic expansion with the one of the first term of P (0, s | z), we obtain

P (0, s | z) = 1 N 2 (1 -z) + N 2 1 + 4ϕN ( s, 1) -6N s2 + 6s2 2 -1 4N 2 + o (1 -z) 1 2 . (19)
C. ASYMPTOTIC EXPANSION OF ϕN (0, 1)

Setting s = 0 and z = 1 in (18), we obtain

ϕN (0, 1) = √ 3 2N N-1 m 1 =1 1 sin( π N m1) 1 + 1 3 sin 2 ( π N m1) 1 2 × 1 + α N m 1 (1) cos(πm1) 1 -α N m 1 (1) cos(πm1) • (20)
In this section, we show that series ϕN (0, 1) has the following asymptotic expansion as N → ∞

ϕN (0, 1) = √ 3 π ln(N ) + √ 3 π γ + ln( √ 3 π ) + √ 3π 3 ℓ + O 1 N 4 ( 21
)
where γ is the Euler 's constant and ℓ is a constant. This asymptotic expansion is obtained by writing ϕN (0, 1) as

ϕN (0, 1) = Q1(N ) + Q2(N ) + Q3(N ),
where

Q1(N ) = √ 3 2N N-1 m 1 =1 1 sin( π N m1) , Q2(N ) = √ 3 2N N-1 m 1 =1 1 + 1 3 sin 2 ( π N m1) -1 2 -1 sin( π N m1) , Q3(N ) = √ 3 N N-1 m 1 =1 1 + 1 3 sin 2 ( π N m1) -1 2 α N m 1 (1) cos(πm1) sin( π N m1) 1 -α N m 1 (1) cos(πm1)
and then by calculating separately the asymptotic expansion of each sum as N → ∞.

C.1 Asymptotic expansion of Q1(N ) as N → ∞

Let f (x) be the function defined for all real numbers x between 0 and π as follows

f (x) =      1 sin(x) - 1 x - 1 π -x , x ∈]0, π[ - 1 π , x = 0, π.
We can show that f is indefinitely differentiable, in particular

f (1) (0) = 1 6 - 1 π 2 and f (1) (π) = - 1 6 + 1 π 2 •
Remark also that Q1(N ) can be expressed as

Q1(N ) = √ 3 2N N-1 m 1 =1 f ( π N m1) + √ 3 π N-1 m 1 =1 1 m1 • (22)
Therefore, using the Euler-Maclaurin summation formula [START_REF] Graham | Concrete Mathematics: A Foundation for Computer Science[END_REF] 1

N N-1 m 1 =1 h( π N m1) = 1 π π 0 h(x) dx - 1 2N h(π) + h(0) + π 12N 2 h (1) (π) -h (1) (0) + O( 1 N 4 ) ( 23
)
where h is an indefinitely differentiable function, and since

π 0 f (x) dx = 2 ln( 2 π ), we obtain 1 N N-1 m 1 =1 f ( π N m1) = 2 π ln( 2 π )+ 1 N π - π 6N 2 1 6 - 1 π 2 +O( 1 N 4 )•
(24) It remains now to expand the second sum involved in (22), which can be recognized as the Harmonic series, that is [START_REF] Graham | Concrete Mathematics: A Foundation for Computer Science[END_REF], HN has the following asymptotic expansion

HN = N-1 m 1 =1 1 m 1 • According to
HN = ln(N ) + γ - 1 2N - 1 12N 2 + O( 1 N 4 ), ( 25
)
where γ is the Euler 's constant (γ = 0.5772156649). By plugging (24) and ( 25) into (22), we find

Q1(N ) = √ 3 π ln(N ) + √ 3 π γ + ln( 2 π ) - √ 3π 72N 2 + O( 1 N 4 )• (26)
C.2 Asymptotic expansion of Q2(N ) as N → ∞

Let g(x) be the function defined for all real numbers x between 0 and π as follows

g(x) =      1 + 1 3 sin 2 (x) - 1
2 -1 sin(x) , x ∈]0, π[ 0, x = 0, π.

We can show that g is indefinitely differentiable, in particular g (1) (0) = -1 6 and g (1) (π) = Before evaluating Q3(N ), note that the terms corresponding to the values of m1 near 1 or N -1 contributes to Q3(N ) more significantly than the ones corresponding to the values of m1 near ⌊ N 2 ⌋ when N is large. Indeed, from [START_REF] Lima | Random walks on sensor networks[END_REF] we see that when m1 ≃ 1 or N -1, sin( π N m1) is close to 0 and |αm 1 (1)| close to 1. In this range, the summand of Q3(N ) diverges as N → ∞. However, when m1 is close to ⌊ N 2 ⌋, sin( π N m1) is close to 1 and αm 1 (1) close to 0, and hence, α N m 1 (1) vanishes exponentially to zero as N → ∞. Therefore, the summand of Q3(N ) decreases to zero faster than any power of 1 N and consequently can be neglected.

We can see also that the summand of Q3(N ) is symmetric about the N 2 -axis, that is, the (N -m1)-term equals to the m1-term. Therefore, by neglecting the N 2 -term only when N is even, Q3(N ) can be rewritten as

Q3(N ) = 2 √ 3 N ⌊ N -1 2 ⌋ m 1 =1
1 + 1 3 sin 2 ( π N m1)

-1 2 α N m 1 (1) cos(πm1) sin( π N m1) 1 -α N m 1 (1) cos(πm1) • (28) In order to approximate Q3(N ) when N is very large, we use a method pioneered by Laplace and described in [START_REF] Graham | Concrete Mathematics: A Foundation for Computer Science[END_REF]. It consists in breaking the sum into two disjoint ranges DN and TN . The summation over DN should be the dominant part, in the sense that it includes enough terms to determine the significant digits of the sum when N is very large. The summation over the other range TN should be just the tail end, which contributes little to the overall total. As the big contributions to Q3(N ) occur when m1 is small, we can consider DN as the range of small values of m1, and TN the range of large values of m1. In the following we construct the asymptotic expansion of Q3(N ) by separating out the dominant and the tail ranges, and then bounding the tail range contributions.

Let am 1 (N ) denote the summand involved in (28). By separating out the dominant and the tail ranges, Q3(N ) can be then expressed as

Q3(N ) = m 1 ∈D N am 1 (N ) + m 1 ∈T N am 1 (N ). (29)
As long as m1 is held in the dominant range, πm N goes to zero as N → ∞. Therefore, am 1 (N ) can be expanded as This asymptotic expansion is valid as long as m1 ∈ DN and thus, it is allowed to take the summation of both sides of (30). Hence

Figure 1 :

 1 Figure 1: Topological equivalence between the hexagon lattice and the square lattice with additional diagonal bond inserted in each fundamental square.

Lemma 2 .

 2 F ( r, s | z) and P ( r, s | z) are related to each other according to the relation

Figure 3 :

 3 Figure 3: Mean system data gathering delay E(DN ) vs. cell size N for IEEE 802.15.4 enabled network nodes, and with an average packet size of 10 bytes.

8 EFigure 4 :

 84 Figure 4: Spatial distribution of the energy consumption based on the mean number of visits over a unit cell of size 15 × 15.

Figure 5 :

 5 Figure 5: Maximum mean number of visits vs. cell size N .

1 6 • 2 gC. 3

 623 Note that Q2(N ) can be expressed as(1) (π) -g(1) (0) + O( Asymptotic expansion of Q3(N ) as N → ∞

am 1 (

 1 N ) = bm 1 (N ) + O(cm 1 (


Suren Sargsyan
email: suren.sargsyan@irccyn.ec-nantes.fr

Vigen Arakelian
email: vigen.arakelyan@insa-rennes.fr

Sébastien Briot
email: sebastien.briot@irccyn.ec-nantes.fr

ROBOTIC REHABILITATION DEVICES OF HUMAN EXTREMITIES: DESIGN CONCEPTS AND FUNCTIONAL PARTICULARITIES

All over the world, several dozen million people suffer from the effects of post-polio, multiple sclerosis, spinal cord injury, cerebral palsy, etc. and could benefit from the advances in robotic devices for rehabilitation. Thus, for modern society, an important and vital problem of designing systems for rehabilitation of human physical working ability appears. The temporary or permanent loss of human motor functions can be compensated by means of various rehabilitation devices. They can be simple mechanical systems for orthoses, which duplicate the functions of human extremities supplying with rigidity and bearing capacity or more complex mechatronic rehabilitation devices with higher level of control. We attempt to cover all of the major developments in these areas, focusing particularly on the development of the different concepts and their functional characteristics. The robotic devices with several structures are classified, taking into account the actuation systems, the neuromuscular stimulations, and the structural schemes. It is showed that the problems concerning the design of rehabilitation devices are complex and involve many questions in the sphere of biomedicine, mechanics, robot technology, electromechanics and optimal control. This paper provides a design overview of hardware, actuation, sensory, and control systems for most of the devices that have been described in the literature, and it ends with a discussion of the major advances that have been made and should be yet overcome.

INTRODUCTION

Applications of robotics systems include several fields such as industrial production, inspection and quality control, field service, surveillance, as well as medicine and health care. The last area is particularly important due to the ability of medical robots to significantly improve surgeons' technical capability, either by making existing procedures more accurate, faster, or less invasive. Similarly, robotic systems for rehabilitation or for assistance in daily living offer real advantages. In the last decade, the interest in this field has raised mainly due the growing demand caused by increasing number of stroke patients.

In this paper, an overview of rehabilitation devices of human extremities taking into accounts their design concept and functional particularities are presented. The described rehabilitation devices of human extremities are presented by two principal groups: stationary and mobile. It has been considered that the rehabilitation system is stationary if the orthosis, i.e. the device intended to correct or improve the locomotive function, is mounted on the immobile support and mobile if the orthosis is mounted on the movable support. Let us start the overview from the analysis of stationary rehabilitation devices.

STATIONARY REHABILITATION DEVICES OF HUMAN EXTREMITIES

The stationary rehabilitation devices can be distinguished by several criteria. One of the most important distinctive characteristics of rehabilitation devices is the nature of the compensation force, which can be passive or active. The compensation force can be considered as passive if it is created by a non-motorized element.

Let us consider the working principle of such a rehabilitation device called the Ergys2 system. The Ergys2 (Therapeutic Alliances Inc, Ohio, USA) is a rehabilitation system for treating neuromuscular disorders and diseases (Fig. 1). It uses computerized functional electrical stimulation (CFES) to allow people with little or no voluntary leg movement to actively pedal [1].

Computer generated, low-level electrical pulses transmitted through surface electrodes cause coordinated contractions of the leg muscles: quadriceps, hamstring, and gluteus. Sensors located in the Ergys2 provide continuous feedback to a computer which controls the sequence of muscle contractions as well as resistance to pedaling. The result is smooth and natural pedaling with the leg muscles supplying the power.

The Ergys2 provides significant benefits for both paraplegics and quadriplegics. It prevents muscle atrophy, relaxes muscle spasms, improves circulation and increases range of motion [2]. The Lokomat (Hocoma AG, Volketswil, Switzerland) consists of a robotic gait orthosis and an advanced body weight support system (Fig. 2) [3]. This system adds the ability to measure the patient's activity by a way of force transducers fitted directly on the motors and offers the possibility to adjust the level of gait assistance for each leg between full and zero guidance force.

The LokoHelp (LokoHelp Group) is an electromechanical device developed for improving gait after brain injury [4]. The LokoHelp (Fig. 3) is placed in the middle of the treadmill surface parallel to the walking direction and fixed to the front of the treadmill with a simple clamp. It also provides a body weight support system for the patient. Clinical trials have been conducted to analyze its feasibility and efficacy [5][6]. The results show that the system improves the gait ability of the patient in the same way as the manual locomotor training. However, using the LokoHelp less therapeutic assistance is required. The aim of MotionMaker (Cyberthosis, Switzerland) (Fig. 4) is to maintain, or increase muscular volume and capacity for patients in the chronic phase, to reinstate mobility of the joints, to train cardiac capacity and prevent neurological osteoporosis. This innovative concept not only allows automation of the treatment, but also an active participation of the patient's muscles. The patient's limbs can be mobilized passively or work actively in an electro-stimulated manner and/or voluntarily against resistance loads created by the motors [START_REF] Métrailler | Cyberthosis: Rehabilitation Robotics With Controlled Electrical Muscle Stimulation[END_REF].

The MotionMaker has shown the advantages of combining robotics and controlled electrostimulation to improve voluntary control [START_REF] Métrailler | Système robotique pour la mobilization des membres infèrieurs d'une personne paraplégique[END_REF]. The activation of muscles in exercises of neurological re-education brings patients not only the recovery of muscle strength and joint mobility, but also the proprioceptive information essential for recovering the ability to activate by themselves their paralysed muscles.

Two other robotic systems have been developed with a similar working principle: (i) the Lambda [START_REF] Bouri | A new concept of parallel robot for rehabilitation and fitness: the Lambda[END_REF], a rehabilitation and fitness robot used for mobilization of lower extremities that provides the movement of the lower extremities in the sagittal plane, including an additional rotation for the ankle mobilization; and (ii) a wire-driven leg rehabilitation system [START_REF] Homma | A wire-driven leg rehabilitation system: development of a 4-dof experimental system[END_REF] developed by the National Institute of Advanced Industrial Science and Technology (AIST) of Tsukuba. The HapticWalker [START_REF] Schmidt | HapticWalker -A novel haptic device for walking simulation[END_REF] comprises two programmable foot platforms with permanent foot machine contact (Fig. 5). One of the applications of the machine is the gait rehabilitation for neurologically impaired persons such as afterstroke or spinal cord injury.

The machine is equipped with electrical direct drive motors, enabling highly dynamic footplate motions. For force feedback 6-degrees-of-freedom force/torque sensors are mounted under each foot platform.

The HapticWalker is designed as a scalable and modular system with a unit-by-unit extensibility. The basic unit enables movements in 3-degrees-of-freedom per foot in the sagittal plane. Each footplate can be extended to up to 6-degrees-offreedom, plus an additional metatarsal joint drive. The system is able to simulate not only 'smooth' trajectories like walking on plane floor, stepping staircases up/down, but also walking on rough ground or even stumbling. The machine is controlled by a full-featured robot control software and hardware.

The Lopes [START_REF] Veneman | Design and Evaluation of the LOPES Exoskeleton Robot for Interactive Gait Rehabilitation[END_REF] combines a freely translatable and 2-Dactuated pelvis segment with a leg exoskeleton containing three actuated rotational joints: two at the hip and one at the knee (Fig. 6). The joints are impedance controlled to allow bidirectional mechanical interaction between the robot and the training subject. Evaluation measurements show that the device allows both a "patient-in-charge" and "robot-in-charge" mode, in which the robot is controlled either to follow or to guide a patient, respectively. Electromyography (EMG) measurements (one subject) on eight important leg muscles show that free walking in the device strongly resembles free treadmill walking; an indication that the device can offer task-specific gait training. The Gait Trainer GT I (Reha-Stim, Berlin, Germany) [13] has been created to improve the patient's ability to walk through continuous practice. The Gait Trainer GT I assists the patient in his or her recovery of gait by relieving the body of its own weight and adapting the pace to the individual ability of the patient. The patient is being positioned using the built-in swivel device, the feet getting fixed on the base plates and the wire mounts attached in order to compensate the body's side movement. The Gait Trainer GT I is attached to the bottom of the foot and does not provide the abrupt transition in ground reaction force that normally occurs between swing and stance.

Step length and gait speed are adjustable. During therapy, the integrated servo drive automation supports the patient's own effort in order to keep the rotation speed constant. Horizontal and vertical trunk movements of the patient are also assisted according to the gait phase. The Gait Trainer GT I allows flexible deployment of its treatment for a number of diseases such as CP-children, patients with incomplete paraplegia, SHT, MS and Parkinson, also patients with joint replacements.

The AutoAmbulator (HealthSouth Cooperation) [START_REF] Galvez | Robotics for Gait Training After Spinal Cord Injury[END_REF] is a body-weight supported treadmill robot system. Robotic arms are strapped to the patient's legs at the thigh and ankle, driving them through a stepping pattern. While using the AutoAmbulator, patients can walk because the device holds their body upright while mechanized braces help guide their legs across the treadmill. A touch screen computer monitors knee torque, thigh torque, and speed, among other session data. An automatic shut down feature is triggered through severe spasms or an improper foot strike on the treadmill by the patient. It may help all sorts of patients with central nervous system disorders. AutoAmbulator is equipped with safety interlocks, redundant travel limits, variable torque limits, and a safety light array to detect improper foot drop. The AutoAmbulator is an exciting technological advance in physical therapy, but it is not a cure for walking impairments [15]. The ARTHUR (Ambulation-assisting Robotic Tool for Human Rehabilitation) [START_REF] Reinkensmeyer | A robotic tool for studying locomotor adaptation and rehabilitation[END_REF] is a 2-degrees-of-freedom robot that makes use of linear electric direct-drive motors to precisely apply forces to the leg during stepping. It was designed primarily to conduct research on human motor control of gait and has been successfully used with unimpaired participants to create novel dynamic environments that can enhance motor adaptation [START_REF] Reinkensmeyer | A robotic tool for studying locomotor adaptation and rehabilitation[END_REF]. ARTHUR cannot assist at both the knee and the lower shank as experienced therapists commonly do.

The PAM (Pelvic Assist Manipulator) [START_REF] Aoyagi | An Assistive Robotic Device That Can Synchronize To The Pelvic Motion During Human Gait Training[END_REF] is a 5-degreesof-freedom compliant robot that accommodates naturalistic motion of pelvis during walking actuated by six pneumatic cylinders, which, combined with a nonlinear force-tracking controller, provide back drivability and large force output at a relatively low cost. PAM can act as a teach-and-replay device with a PD position controller driving the pelvis onto the reference trajectory specified with or without the help of therapists.

The POGO (Pneumatically Operated Gait Orthosis) is a leg robot aimed at the goal of being used in the clinic for daily locomotor [START_REF] Reinkensmeyer | Tools for understanding and optimizing robotic gait training[END_REF]. POGO is composed of two pneumatic cylinders that are fixed to a telescoping rail system that extends from a hip belt to a molded cuff around the lower shank. One cylinder pushes and pulls between the hip belt and the rail, thus flexing and extending the hip. A second cylinder pushes and pulls between the middle of the rail and a strap wrapped just below the knee, thus providing knee flexion and extension.

The String-Man is a wire robot for manipulating the torso of the patients based on the string-puppet principle [START_REF] Surdilovic | String-man: A novel wire robot for gait rehabilitation[END_REF]. Seven wires connected to the patient's trunk achieve weight bearing and 6-dof manipulation (Fig. 7). Force sensors between the wires and the actuators allow force or impedance control: this permits adjustment of the interaction control from totally passive to completely active and allows the patients to test their balancing capabilities. The String-Man can control both the zero-moment-point location and the ground reaction force, using foot force sensors in addition to the wire force sensors.

MOBILE REHABILITATION DEVICES OF HUMAN EXTREMITIES

The most important feature of the mobile rehabilitation devices is the fact that it is easily portable and wearable. The compact and lightweight characteristics of these advanced rehabilitation devices allow them to be used in an average chair, while standing, or perhaps even during ambulatory motion.

Passive gravity balancing orthoses have been proposed for the upper arm [START_REF] Agrawal | Design and fabrication of a gravity balanced planar mechanism using auxiliary parallelograms[END_REF]- [START_REF] Herder | Development of a Statically Balanced Arm Support: ARMON[END_REF]. In the studies [START_REF] Banala | Gravity-Balancing Leg Orthosis and Its Performance Evaluation[END_REF], [START_REF] Agrawal | Theory and Design of an Orthotic Device for Full or Partial Gravity-Balancing of a Human Leg During Motion[END_REF], a design of an exoskeleton for full or partial gravity-balancing of a human leg during motion has been proposed (Fig. 8). The device is worn by the user and segments of the exoskeleton are strapped to the corresponding segments of the human leg.

In order to improve the compensation in the orthoses several balancing approaches have been developed [START_REF] Banala | A gravity balancing leg orthosis for robotic rehabilitation[END_REF]- [START_REF] Agrawal | Design of gravity balancing leg orthosis using non-zero free length springs[END_REF]. In these studies, the spring mass has been included in the balancing conditions that improves the quality of balance [START_REF] Arakelian | Improvement of balancing accuracy of robotic systems: application to leg orthosis for rehabilitation Devices[END_REF], [START_REF] Arakelian | Gravity balancing of the human leg taking into account the spring mass[END_REF].

Recently, the orthosis ALEX along with force-field controller has been developed for gait rehabilitation of stroke survivors. Its aim is to help in retraining the gait pattern by using assist-as-needed approach which allows the patient to participate more actively in the retraining process compared to other currently available robotic training devices (Fig. 9) [START_REF] Banala | Robot Assisted Gait Training With Active Leg Exoskeleton (ALEX)[END_REF]. KAFO (knee-ankle-foot orthoses) (Fig. 10) and HKAFO (hip-knee-ankle-foot orthoses) have been used for the treatment of patients with paraplegia after thoracic and/or lumbar spinal cord injuries [START_REF] Onogi | Comparison of the effects of sliding-type and hinge-type joints of knee-ankle-foot orthoses on temporal gait parameters in patients with paraplegia[END_REF]. While these orthoses provide excellent stability during steady-state standing, they are not convenient for daily home use. As a result, the rate of continuous use of orthoses is low, and they tend to be worn only for standing and exercise in the home setting. Even in the clinical setting, these orthoses are not frequently used because of problems associated with their weight, size, appearance, and comfortableness [34].

The Mobility Device (Tempe, Arizona, USA) allows patients with a wide range of impairments to walk over ground safely (Fig. 11). It is enforced with a battery operated power lift actuator that lifts patients: weighing up to 159kg (350lbs), from sit to stand. To make the effort easier, the Mobility Device is designed to assist both patient and therapist [35]. The Erigo (Hocoma AG, Volketswil, Switzerland) is an innovative tilt table with integrated robotic stepping functions (Fig. 13). It combines simultaneous dynamic leg movement and physiological loading of the lower extremities of long bed rest patients or of neurological patients in the early phase of rehabilitation. The purpose of the Erigo is to provide the opportunity of intensive movement therapy and physiological loading of the lower limbs at an early stage after onset combined with the possibility of simultaneous up-righting of the patient [3]. The WalkTrainer (Cyberthosis, Monthey, Lausanne, Switzerland) is equipped with orthoses for the legs and pelvis, body weight support, and with CLEMS (Closed Loop Electrical Muscle Stimulation) [START_REF] Métrailler | Cyberthosis: Rehabilitation Robotics With Controlled Electrical Muscle Stimulation[END_REF], this system allows near perfect mimicking of walking movements with the aim of stimulating nervous system plasticity (Fig. 14). The WalkTrainer is composed of body weight support, active winch, harness, pelvic orthesis, gait orthesis, motorized wheels, battery, electrostimulator, electrodes and control unit. The main function of the walking frame is to follow the patient while moving. It serves as a mobile support for all the other components. Training with WalkTrainer should allow one to go even further in the relearning of gait patterns by offering overground walking with controlled pelvic motion and muscle activity. The main difficulty for this system is to propose an alternative at least as good as the wheelchair in functional terms, but also in terms of ease of use and implementation.

The LiteGait (Tempe, Arizona, USA) [35] is a gait training device that simultaneously controls weight bearing, posture, and balance over a treadmill or over ground. It consists of a yoke, straps, a harness, an actuator and a base. The lift mechanism is a rechargeable, battery powered actuator which permits the incremental adjustment of weight bearing. This allows patient to be brought to an upright posture.

The handheld control allows therapists to conveniently bring patient to a standing position and adjust the amount of weight supported. LiteGait provides proper posture, reduces weight bearing, eliminates concerns for balance, and facilitates the training of coordinated lower extremity movement. It permits unilateral or bilateral support, allowing progression of the weight bearing load from non to full weight bearing and also allows the clinician to manually assist the legs and pelvis to achieve proper gait patterns. LiteGait also provides posture and balance control, creating a secure, fall free environment for the patient. The Parastep (Sigmedics, Inc, Fairborn, Ohio, USA) is a microcomputer controlled functional neuromuscular stimulation (FNS) system that enables independent, unbraced ambulation by people with a spinal cord injury. The computer is programmed to control the sequence of muscle contractions in the lower extremities that enable the functions of sit-to-stand, right and left step and stand to sit. Users are taught to initiate functions by activating commands through switch modules mounted on either side of the walker handle bars [37].

The BerkelBike (BerkelBike BV, Sint-Michielsgestel, Netherlands) [38] is a combination of a hand and a recumbent bike and is driven by arm as well as leg power (Fig. 15). It provides support to both muscle groups helping to rehabilitate and keep the muscles stronger and fitter. The benefits of cycling for impaired patients are to overcome overweighting due to lack of activities. The BerkelBike is for patients with spinal cord injury, polio, multiple sclerosis or stroke (CVA). The BerkelBike (Classic, Home or Pro) is equipped with a sensor that tells the Impuls stimulator the position of the legs. The software in the stimulator uses this information to calculate which muscles to stimulate and the strength of electric pulse required. The electric pulses generated are passed to the muscles via a pair of Impuls electrode shorts. These are like cycling shorts with a number of electrodes embedded within them. The electric pulses stimulate the muscles, causing them to contract at the appropriate time, allowing the person to cycle again [38]. The Walkabout (Polymedic Co., Goldcoast, Queensland, Australia) [START_REF] Onogi | Comparison of the effects of sliding-type and hinge-type joints of knee-ankle-foot orthoses on temporal gait parameters in patients with paraplegia[END_REF] functions as a single-axis hip joint connecting two KAFOs (Fig. 16). The unit is positioned and attached to the KAFOs between the thighs, under the perineum, but is also removable. The Walkabout system provides stability during standing and walking, is compatible with wheelchairs, have cosmetic benefits, and is easy to don/doff. However, the Walkabout system has a hypothetical axis that is lower than the position of the physiological hip joint. It was suggested that this discrepancy would create a significant impediment to ambulation by increasing resistance to the movement of the legs. The Primewalk (TIMS Co., Fukamiiwahana, Fujiko-cho, Nishikamo, Aichi, Japan) [START_REF] Onogi | Comparison of the effects of sliding-type and hinge-type joints of knee-ankle-foot orthoses on temporal gait parameters in patients with paraplegia[END_REF] is a KAFO with another medial linkage device, which has a virtual axis based on a sliding mechanism (Fig. 16). The Primewalk device is a sliding-type medial hip joint that had 12 embedded bearings in order to ensure smooth movement [START_REF] Onogi | Comparison of the effects of sliding-type and hinge-type joints of knee-ankle-foot orthoses on temporal gait parameters in patients with paraplegia[END_REF]. It is possible to wear the Primewalk system on a wheelchair. The average gait velocity is higher, cadence is faster, and stride is longer with the Primewalk system than with the Walkabout system. The value for the step length divided by the pelvic rotation angle is larger with the Primewalk system than with the Walkabout system. The Primewalk system improved the gait efficiency by the sliding mechanism that set the virtual axis of the orthoses hip joint higher than that of the hinge-type joint.

The RoboKnee (Yobotics, Inc., Cincinnati, OH, USA) is a 1-degree-of-freedom powered knee exoskeleton, for adding power at the knee to assist in stair climbing and squatting during load-carrying (Fig. 17) [39]. The RoboKnee may be used for the patients who are suffering from weakness in their lower extremities, such causes including cerebral vascular trauma (stroke), post-polio syndrome, multiple sclerosis, muscular dystrophy, and aging. The device consists of a linear series-elastic actuator connected to the upper and lower portions of a knee brace, with the help of which low impendence is achieved just below the hip and on the calf, respectively [START_REF] Pratt | The RoboKnee: An Exoskeleton for Enhancing Strength and Endurance During Walking[END_REF]. The control of the RoboKnee utilizes the ground reaction force and the center of pressure in the sagittal plane to create a positive feedback force amplification control scheme of the torque at the knee.

The Knee Exoskeleton [START_REF] Dollar | Design of a Quasi-Passive Knee Exoskeleton to Assist Running[END_REF] can be applied to the patients who suffer some form of leg weakness (Fig. 18). The concept of powered orthotic devices is to harness the passive dynamics of locomotion to reduce energetic requirements. An energetically-autonomous powered knee exoskeleton is designed to facilitate running. The device consists of a knee brace in which a motorized mechanism actively places and removes a spring in parallel with the knee joint. This mechanism is controlled such that the spring is in parallel with the knee joint from approximately heel-strike to toe-off, and is removed from this state during the swing phase of running. In this way, the spring is intended to store energy at heel-strike which is then released when the heel leaves the ground, reducing the effort required by the quadriceps to exert this energy, thereby reducing the metabolic cost of running. A motor helps lift each leg at the thigh as it moves forward and backward. This helps lengthen the user's stride, making it easier to cover longer distances at a greater speed. Its lightweight and simple design with a belt worn around the hips and thighs reduces the wearer's load and fits different body shapes. The device weights 2.8kg with batteries. It is comprised with 2 brushless DC motors, rechargeable Lithium ion battery, angle sensors, control computer and operates about 2 hours. Honda's device lightens the load on the user's legs and helps maintain a center of gravity via special mechanisms developed by the company. Walking, crouching, climbing stairs all become easier with the help of this device. There are plenty of use cases for this product, not the least of which would be helping people afflicted with mobility issues or leg problems. It can also be used for rehabilitation.

CONCLUSION

This paper presents an overview of rehabilitation devices of human extremities considering their design concepts and functional particularities. It is obvious that strict space limitations did not permit the inclusion in this review of all the devices worthy of attention. However, we have tried, wherever possible, to describe the most innovative solutions.

Analysis of rehabilitation devices showed that the stationary rehabilitation devices, which are based on the motorized orthosis provide more effective ways to reinstate mobility of the joints. They offer the possibility to adjust the level of gait assistance for each extremity according to the established program. The main advantages of these devices are the possibility of combining mechanical motion generation and controlled electrostimulations. The electric pulses stimulate the muscles, causing them to contract at the appropriate time, which accelerate the rehabilitation period. However, due to the fast development of high technologies and their applications in robotic rehabilitation, the design of mobile rehabilitation devices is also a promising field. The use of active and passive actuations allows a significant reduction of the size and weight of portative rehabilitation devices. The compact and lightweight characteristics of these advanced rehabilitation devices allow them to be used not only for medical purposes but also as walking assistive devices.

Figure 1 .

 1 Figure 1. Ergys rehabilitation system.However, the working principle of most stationary rehabilitation devices is based on the motorized orthosis, which can be with electrosimulation or without it. Let us consider some examples.

Figure 2 .

 2 Figure 2. Lokomat system.

Figure 3 .

 3 Figure 3. LokoHelp gait trainer PEDAGO.

Figure 4 .

 4 Figure 4. MotionMaker rehabilitation device.

Figure 5 .

 5 Figure 5. HapticWalker robotic walking simulator.

Figure 6 .

 6 Figure 6. Lopes gait rehabilitation device.

Figure 7 .

 7 Figure 7. String-Man rehabilitation robot.

Figure 8 .

 8 Figure 8. Prototypes developed in the University of Delaware.

FIGURE 9 .

 9 FIGURE 9. Motorized orthosis ALEX.

Figure 10 .

 10 Figure 10. Kafo.

Figure 11 .

 11 Figure 11. Mobility Device. The Walking Trainer (Ropox A/S, Naestved, Denmark) is a device to provide a normal walking pattern by controlling weight bearing, balance and posture during walking therapy (Fig. 12). It can lift patient from sitting position, with the help of attached to the device lifting actuator. Training can normally be done by one therapist [36].

Figure 12 .

 12 Figure 12. Walking Trainer.

Figure

  Figure 13. Erigo.

Figure 14 .

 14 Figure 14. WalkTrainer.

Figure 15 .

 15 Figure 15. Berkelbike classic.

Figure 16 .

 16 Figure 16. Walkabout, Primewalk.

Figure 17 .

 17 Figure 17. RoboKnee.

Figure 18 .

 18 Figure 18. Knee exoskeleton.Hybrid Assistive Limb (HAL) (CYBERDYNE Inc, Japan)[START_REF] Yoshiyuki | HAL: Hybrid Assistive Limb based on Cybernics[END_REF] consists of controller, computer, battery, bioelectrical sensors, angular sensors, acceleration sensors, floor reaction force sensors. It requires AC100V electricity and can operate continuously approximately 2 hours 40 minutes. The total weight of the device is 21kg. It supports activities like standing up from a chair, walking, climbing up and down stairs, holding and lifting heavy objects up to 70kg. HAL uses biosensors from the bio signals to interpret the wearer's intention in advance of the actual movement. This is called 'voluntary control system'. HAL has also a 'robotic autonomous control system' that provides human-like movement based on a robotic system which integrally work together with the 'autonomous control system'. HAL can be applied in various fields such as rehabilitation support and physical training support in medical field[43].

Figure 19 .

 19 Figure 19. Walking assist device with stride management assist.

Figure 20 .

 20 Figure 20. Walking assist device in use. Walking Assistive Device with Stride Management (Honda Motor) [44] is developed for patients with weakened leg muscles who are still able to walk (Figs 19 and 20).A motor helps lift each leg at the thigh as it moves forward and backward. This helps lengthen the user's stride, making it easier to cover longer distances at a greater speed. Its lightweight and simple design with a belt worn around the hips and thighs reduces the wearer's load and fits different body shapes. The device weights 2.8kg with batteries. It is comprised with 2 brushless DC motors, rechargeable Lithium ion battery, angle sensors, control computer and operates about 2 hours.

Figure 21 .

 21 Figure 21. Walking assist device bodyweight support.

Figure 22 .

 22 Figure 22. Walking assist device in use.