Christophe Guyeux

An update on the topological properties of asynchronous iterations

Keywords: distributed computing, asynchronous iterations, theoretical modelling, chaos theory

come

Introduction

Given f : (Z/2Z) N → (Z/2Z) N , the asynchronous iterations are defined as follow:

x 0 ∈ (Z/2Z) N , and

∀n ∈ N, ∀i ∈ 1, N , x n+1 i f (x n ) i if i ∈ s n x n i else.
(

) 1
where (s n ) n∈N ∈ P ( 1, N ) is a sequence of subsets of {1, 2, ..., N}: P(X) here refers to all the parts of a set X, when a, b is the set of integers ranging from a to b; finally, the n-th term of a sequence u is written in exponent notation u n , as this is a vector with N coordinates: u n 1 , . . . , u n N . Asynchronous iterations have provided, for decades, a mathematical framework for finding advanced algorithm schemas in distributed computing: roughly speaking, the coordinates of the vector x n correspond to the calculation units, the function f is the equivalent of the calculation to be distributed, and the sequence s is the way to distribute these calculations: the sequence {1, 2, . . . , N}, {1, 2, . . . , N}, {1, 2, . . . , N}, . . . corresponding to a parallel calculation, when {1}, {2}, . . . {N}, {1}, {2}, . . . is a serial calculation, for example.

This mathematical formulation of asynchronous distributed algorithms has made it possible to establish various theoretical frameworks, in which proof of convergence and convergence rate calculations could be established. As an illustrative example, three special cases of the Definition 1 will be recalled in this article, who have a significant theoretical and practical interest. These are Chazan and Miranker's historical approach, asynchronous memory iterations, and Bertsekas' model. Situations for which we can be sure of the convergence of these models will be presented, before discussing the problem of the termination of algorithms. Taking a direction diametrically opposed to these convergence efforts, we will then discuss that the study of chaos of such asynchronous iterations, described as discrete dynamic systems, has been initiated this last decade, and studied in more depth in various publications that followed the founding article of [START_REF] Guyeux | Le désordre des itérations chaotiques -Applications aux réseaux de capteurs, à la dissimulation d'information, et aux fonctions de hachage[END_REF].

This topological behaviour, which had never been examined before, has led to interesting applications of such complex dynamics in various domains of computer security like hash functions [START_REF] Bahi | Quality analysis of a chaotic proven keyed hash function[END_REF] and digital watermarking [START_REF] Guyeux | A new chaos-based watermarking algorithm[END_REF]. The dynamics studied in this framework can also derive from computers (sensor networks, neural networks, pseudo-random number generators, etc.) or biology (protein folding, genome evolution, etc.). Taking into account these many possibilities, an original approach of asynchronous iterations was to track, model and theoretically study these complex dynamics inherited from computer science or biology. The objective of this article is precisely to take stock of recent advances made in the study of the disorder of asynchronous iterations, and to put them in historical perspective with the results relating to the order and convergence of such iterations.

This article is structured as follows. In the next section, various historical approaches, among the most significant in the theoretical study of the convergence of asynchronous iterations, will be recalled. These theoretical frameworks and convergence results will be put into perspective in Section 3, in which the opposite (disorder and divergence of such iterations) will be followed. This article will conclude with a discussion, in which the applications of such an approach to disorder will be discussed, and avenues for theoretical exploration will be proposed.

2 An historical perspective of the convergence study

Three historical models

The iterations considered in this manuscript have been studied for more than fifty years, both in terms of their convergence and their applications. In this section, rather than being exhaustive, we have chosen to arbitrarily present three models that have had a significant historical impact.

The Chazan and Miranker model

The first theoretical work on asynchronous algorithms dates back to 1969, it focused on linear system resolutions.

The interest of asynchronism when resolving such systems, using several computers that can communicate with each other, is as follows. In an asynchronous iterative algorithm, the components of the iterated vector are updated in parallel, without any a priori order or synchronization between the machines. The asynchronous implementation allows a better recovery of communications by calculations (no downtime due to synchronizations) and allows failures (temporary or permanent). Asynchronism also has the advantage of better adaptability to changes in the computing infrastructure, such as changes in topology: changes in the number of computers, or in the possible communications between them.

This model, based on the work of Chazan and Miranker [START_REF] Chazan | Chaotic relaxation[END_REF], Miellou [START_REF] Miellou | Algorithmes de relaxation chaotique à retards[END_REF], and Baudet [START_REF] Baudet | Asynchronous Iterative Methods for Multiprocessors[END_REF], has been formalized on the following manner: Definition 1 (Chazan and Miranker model) Let X = R n 1 × . . . × R nα . The asynchronous iterations associated to F : X → X , with initial condition x 0 ∈ X , corre-spond to the sequence x ∈ X N defined by:

x t i =      F i x I t 1 1 , . . . , x I t α α si i ∈ S t x t-1 i si i / ∈ S t
where x i is the sub-vector of x on R n i , F i is the i-th block-component of F , and ∀t ∈ N * , S t ⊂ 1; α and

I t ∈ N α .
In other words, at iteration t, the value of the i-th block-component x i is either the value of x i at iteration t -1, or the mapping F i x

I t 1 1 , . . . , x I t α α
, in which the current component blocks x t i are not taken into account, but one of their previous values x

I t i i , i.e.
, the component block that the system had at the time I t i . This approach allows for very general transmission delays to be taken into account. Finally, the S t sequence indicates which cell blocks should be updated at time t. It can be seen that this model of delay iterations is a special case of the Definition 1.

In addition, it is assumed in this model that the S and I sequences test the following assumptions:

H1. The values of the iterated vector used in the calculations at the iteration t come at best from the iteration t -1 (notion of delay in transmission): ∀t ∈ N * , I t i t -1, H2. I t i → +∞, when t → +∞: the too old values of the components of the iterated vector must be definitively discarded as the calculations progress.

H3.

No subvector stops to be updated (so-called pseudo-periodic strategies). In other words, t appears an infinite number of times in S.

This a specific framework of iterations, but the purpose remains relatively general: blocks are considered rather than components; real numbers are manipulated; and delays are taken into account, which depend on the blocks from which the information comes. The only constraints are that no component of the iterated vector should cease to be permanently updated, and that the values of the components associated with too old iterations should cease to be used as the calculations progress. It should be noted, to finish with the introduction of this model, that the above hypotheses H2 and H3 find their natural justification in the fact that the initiators of this theory were exclusively seeking the convergence of asynchronous iterations.

Asynchrones iterations with memory

Asynchronous iterations with memory use at each iteration several values of each component of the iterated vector, which may be related to different iteration numbers. This gives the following definition: Definition 2 (Asynchrones iterations with memory) Let n ∈ N, α ∈ 0; n , and the following decomposition of R n : X = R n 1 × . . . × R nα , where

α i=1 n i = n.
Let F : X m → X , where m ∈ N * . One asynchronous iteration with m -1 memories associated to the application F and to the subset Y of the m first vectors {x 0 , x 1 , . . . , x m-1 }, is a sequence (x j ) j∈N of vectors of X such that, for i ∈ 1; α and j m, we have:

   x j i = F i (z 1 , . . . , z m ) if i ∈ S j x j i = x j-1 i if i / ∈ S j
where ∀r ∈ 1; m , z r is the vector constituted by the subvectors z r l = x I r l (j) l , (S j ) j m is a sequence of non-empty subsets of 1; α , and

I = I 1 1 (j), . . . I 1 α (j), I 2 1 (j), . . . I 2 α (j), I m 1 (j), . . . I m α (j) j m is a sequence of [N α ] m .
In addition, S and I satisfy the following conditions:

• max r∈ 1;m I r i (j) r ∈ 1; m j -1, for all j m;

• min r∈ 1;m I r i (j) r ∈ 1; m tends to infinity when j tends to infinity; and

• i appears an infinite number of times in S.

These iterations, which are also a special case of the Definition 1, have been studied by Miellou [START_REF] Miellou | Itérations chaotiques à retards, étude de la convergence dans le cas d'espaces partiellement ordonnés[END_REF], El Tarazi [START_REF] Tarazi | Contraction et ordre partiel pour l'étude d'algorithmes synchrones et asynchrones en analyse numérique[END_REF] and Baudet [START_REF] Baudet | Asynchronous Iterative Methods for Multiprocessors[END_REF]. Asynchronous iterations with memory have been proposed to deal with the case where an application, whose fixed point is searched by a classical method, is not explicitly defined. They allow to assign some processors to intermediate function calculations, while the others are in charge of updating the components of the iterated vector [START_REF] Baz | Contribution à l'algorithmique parallèle. Le concept d'asynchronisme : étude théorique, mise en oeuvre, et application[END_REF].

Bertsekas model

The Bertsekas model of fully asynchronous iterations differs significantly from the two models presented above. By introducing another formulation of these objects, it makes it possible to better understand their nature, in particular by allowing them to be categorized by classes. Let:

• X 1 , . . . , X n some sets, and X = X 1 × . . . × X n .

• F i : X → X i some functions, and

F (x) = (F 1 (x), . . . , F n (x)) defined from X to X .
The Bertsekas model of totally asynchronous algorithms, another special case of the Definition 1, is the following [START_REF] Baz | Contribution à l'algorithmique parallèle. Le concept d'asynchronisme : étude théorique, mise en oeuvre, et application[END_REF].

Definition 3 (Bertsekas model) We assume that there is a sequence of events T = {0, 1, 2, . . .} for which one or more components x i of the iterative vector x are updated by one of the processors of the parallel or distributed architecture. Let be T i the sub-series of events for which x i is updated. We assume too that the processor updating x i may not have access to the most recent values of the x components, and for any t / ∈ T i , x i remains unchanged. An asynchronous iteration of the Bertsekas model is a x t sequence of vectors of R n such that for any i ∈ 1; n :

   x t+1 i = F i (x 1 (τ i 1 (t)) , . . . , x n (τ i n (t))) if t ∈ T i x t+1 i = x t i if t / ∈ T i where τ i l (t) ∈ 0; t , ∀l ∈ 1; n , ∀t ∈ T .
The T elements are the indices of the sequence of moments at which the updates are delivered. The difference t-τ i l (t), on the other hand, represents the delay in accessing the i-th component of the iterated vector, when updating the i-th component at the moment t [START_REF] Baz | Contribution à l'algorithmique parallèle. Le concept d'asynchronisme : étude théorique, mise en oeuvre, et application[END_REF].

For the model to be complete, one of the following two assumptions regarding calculations and communications must be added to the above definition:

Hypothesis of total asynchronism. The T i sets are infinite. Moreover, if t k is a subseries of elements of T i that tends to infinity, then lim k→+∞ τ i l (t k ) = +∞, for all l ∈ 1; n .

Partial asynchronism hypothesis.

There is a positive integer B, called asynchronism character, such as:

1. For any i ∈ 1; n , and for any t, at least one element of the set t; t+B-1 belongs to T i : each component is refreshed at least once during an interval containing B refreshes.

2. t -B < τ i l (t)
t, ∀i, l ∈ 1; n , and t ∈ T i : the information used to update a component has a maximum delay of B.

τ

i i (t) = t, ∀i ∈ 1; n , ∀t ∈ T i :
when updating the component assigned to it, each processor uses the last value of the same component.

Partially asynchronous iterations were introduced by Bertsekas and Tsitsiklis in [START_REF] Bertsekas | Parallel and distributed iterative algorithms: a selective survey[END_REF]. They are less general than totally asynchronous iterations: markers are placed on the delays and the duration of the interval between two consecutive updates of the same component. However, they may be of great interest when excessive asynchronism leads to divergence, or does not guarantee convergence.

The use of asynchronous iterative algorithms raises two types of problems: establishing their convergence, and ensuring the termination of algorithms. These problems are reviewed in the next two sections.

On the usefulness of convergence situations

Convergence in the asynchronous model is more difficult to achieve than in the synchronous model due to the lack of synchronization, and therefore the less regular behaviour of iterative patterns. However, a number of general results could be established. They are for various contexts: (non-linear) systems, fixed point problems, etc.

Case of equation systems

The first convergence result, published by Chazan and Miranker in 1969 [START_REF] Chazan | Chaotic relaxation[END_REF], is a necessary and sufficient condition for the convergence of the asynchronous iterations, as part of the resolution of linear systems. It requires the definition of H-matrices: Definition 4 (H-matrices) A matrix N is a H-matrix if the Ñ matrix consisting of diagonal elements of N minus the absolute value of non-diagonal elements, is a matrix such that its diagonal coefficients are strictly positive, its non-diagonal elements are negative or null, and the opposite of Ñ exists, and has its positive coefficients.

The necessary and sufficient condition for convergence for linear systems can then be stated [START_REF] Chazan | Chaotic relaxation[END_REF]:

Proposition 1 Let's say the system of equations Ax * = z, where x * and z are two vectors of R n . Then any asynchronous algorithm defined by the Chazan and Miranker model, where F then corresponds to a Jacobi type matrix per point, converges towards the solution of the problem if and only if A is a H-matrix.

Various sufficient conditions have since been set out in specific frameworks of equation systems, both linear and non-linear [START_REF] Spitéri | Contribution à l'étude de la stabilite au sens de liapounov de certains systemes differentiels non lineaires[END_REF], for the various asynchronous iteration models mentioned above. Such results can be found in [START_REF] Bahi | Algorithmes asynchrones pour des systèmes différentiels-algébriques. Simulation numérique sur des exemples de circuits électriques[END_REF], [START_REF] Bahi | Méthodes itératives dans des espaces produits[END_REF], or [START_REF] Baz | Contribution à l'algorithmique parallèle. Le concept d'asynchronisme : étude théorique, mise en oeuvre, et application[END_REF].

Fixed point problems

In the same vein, various convergence results for asynchronous iterations applied to fixed point problem solving have been obtained [START_REF] Miellou | Un critère de convergence pour des méthodes générales de point fixe[END_REF]. One of the most remarkable results is related to the contraction of the function, and is stated as follows [START_REF] Miellou | Algorithmes de relaxation chaotique à retards[END_REF]: Proposition 2 Let be E a reflexive Banach space finished product of a family of Banach spaces

(E i , ||.|| i ), i ∈ 1; α . Let us denote by ϕ(x) = (||x 1 || 1 , . . . , ||x α || α ) the canonical vectorial norm of E. Let F : D(F ) → D(F ) a function, where D(F ) ⊂ E is non-empty. If • F has a fixed point in x * ∈ D(F ),
• and F is contracting in x * for the vectorial norm ϕ, then the asynchronous iterative algorithm defined by the Chazan and Miranker model belongs to D(F ), and converges to x * . This result has been extended to fixed point applications with relaxation parameter [START_REF] Tarazi | Contraction et ordre partiel pour l'étude d'algorithmes synchrones et asynchrones en analyse numérique[END_REF], [START_REF] Tarazi | Some convergence results for asynchronous algorithms[END_REF], asynchronous iterative algorithms with memory in a context of classical contraction [START_REF] Tarazi | Some convergence results for asynchronous algorithms[END_REF], and partial order [START_REF] Tarazi | Algorithmes mixtes asynchrones. Etude de convergence monotone[END_REF]. Other classic results can be found in [START_REF] Miellou | Itérations chaotiques à retards, étude de la convergence dans le cas d'espaces partiellement ordonnés[END_REF] and [START_REF] Jacquemard | Contribution à l'étude d'algorithmes à convergence monotone[END_REF].

Bertsekas' asynchronous convergence theorem

Bertsekas' theorem provides a set of sufficient conditions for the convergence of asynchronous algorithms for fixed point problems. This result, which is based on Lyapunov's theory of stability, is based on the study of a series of sets to which the elements of the iterated vector suite belong. Its advantage is that it provides a more abstract framework for the analysis of the convergence of asynchronous iterations, which includes in particular the contraction and partial order aspects.

Proposition 3 (Asynchronous convergence of Bertsekas [START_REF] Bertsekas | Parallel and distributed computation: numerical methods[END_REF]) Let X = X 1 × . . . × X n a cartesian product of sets. Suppose there is a series of non-empty subsets X j of X , increasing for inclusion, such as ∀j, there are sets

X j i ⊂ X i checking X j = X j 1 × . . . × X j n .
Let us assume too that:

• F (x) ⊂ X j+1 , ∀j, ∀x ∈ X j ,
• if x is a sequence of vectors such as x j ∈ X j for all j, then x tends to a fixed point of F .

Under these conditions, and if x 0 ∈ X 0 , then any fully asynchronous iteration defined according to the Bertsekas model converges to a fixed point of F .

Bertsekas and his team used this theorem to obtain convergence results for various asynchronous algorithms applied to solving a wide variety of problems: dynamic programming, search for minimum paths, optimization problems, network flow, optimal routing... Other convergence results can be found in the literature. Thus, Lubachewski and Mitra have established a sufficient convergence result for asynchronous iterations with bounded delays applied to the resolution of singular Markovian systems [START_REF] Lubachevsky | A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radius[END_REF]. Finally, Frommer and Szyld studied the so-called multisplitting and asynchronous decomposition methods [START_REF] Frommer | Asynchronous Two-Stage Iterative Methods[END_REF], [START_REF] Frommer | Asynchronous Weighted Additive Schwarz Methods[END_REF].

The problem of algorithm termination

The final termination of the iterative algorithm must occur when the iterated vector is sufficiently close to a solution of the problem, and a special procedure must be designed to detect this termination. Since the number of iterations of the algorithm can be infinite, the calculation processes can never be inactive. There are relatively few effective termination methods for asynchronous algorithms. Indeed, termination presents many difficulties, especially in cases where processors do not share a global clock, or where communication delays can be arbitrarily long.

The most frequently used termination methods are designed empirically. For example, a particular processor can be assigned the task of observing the local termination conditions in each processor: the algorithm terminates when all local conditions are met. This approach is functional in the unique case where the degree of asynchronism is very low. Other empirical methods are possible. For example, Bertsekas and Tsitsiklis proposed in [START_REF] Bertsekas | Parallel and distributed computation: numerical methods[END_REF] that each processor send termination and restart messages to a central processor in charge of these problems. The Chajakis and Zenios [START_REF] Chajakis | Synchronous and asynchronous implementations of relaxation algorithms for nonlinear network optimization[END_REF] method does not require a central processor: a processor completes its calculations if its local termination condition is satisfied, and if it has received termination messages from other processors, and acknowledgements of all its termination messages. No termination method has been formally validated in the most general case, or almost in the most general case: the Bertsekas and Tsitsiklis solution is one of the few with formal validity. However, this method has a number of disadvantages: complex protocol, many communications, restrictive convergence conditions, etc.

As we can see, the problems of convergence of asynchronous iterations and their applications have been widely studied over the past fifty years. The inverse problem of the divergence of these iterations has been studied more recently, over the past decades, and has also proved to be rich in applications. The formal framework and these applications are the subject of the remainder of this article.

3 Theoretical foundations of the divergence

Asynchronous iterations as a dynamical system

In the absence of "delay", asynchronous iterations can be rewritten as a recurring sequence on the product space X = (Z/2Z) N × P( 1, N ) N , consisting of the calculated vectors on the one hand, and the series of components to be updated on the other hand. If you enter the functions i : P ( 1, N ) N → P ( 1, N ), (s n ) n∈N -→ s 0 , producing the first subset of the sequence s and σ : P ( 1, N ) N → P ( 1, N ) N , (s n ) n∈N -→ (s n+1 ) n∈N , performing a shift to head the list, then the asynchronous iterations of the Equation ( 1) are rewritten as a discrete dynamical system G f on X :

X 0 ∈ X , et ∀n ∈ N, X n+1 = (F f (X n 1 , i(X n 2 )); σ(X n 2 )) = G f (X n ) (2)
where

F f : (Z/2Z) N × P ( 1, N ) -→ (Z/2Z) N , (x, e) -→ (x i X e (i) + f (x) i X e (i)) i∈ 1,N ,
with X X as the characteristic function of the set X and x = x + 1 (mod 2).

Finally, a relevant distance can be introduced on X , as follows [START_REF] Guyeux | A Topological Study of Chaotic Iterations. Application to Hash Functions[END_REF]:

d((S, E); ( Š; Ě)) = d e (E, Ě) + d s (S, Š)
where

d e (E, Ě) = N k=1
δ(E k , Ěk ), δ being the Hamming distance, and

d s (S, Š) = 9 N ∞ k=1 |S k -Šk | 10 k .
With such a distance, we can state that [START_REF] Guyeux | Le désordre des itérations chaotiques -Applications aux réseaux de capteurs, à la dissimulation d'information, et aux fonctions de hachage[END_REF]:

Proposition 4 G f : (X , d) → (X , d) is a continuous map.
Asynchronous iterations had until now been studied with discrete mathematics. Such a rewrite therefore makes it possible to study them with the tools of mathematical analysis. This is all the more relevant since the results of distributed computation algorithms are usually fixed points, and mathematical analysis contains various frameworks for studying fixed points of dynamical systems. Note that we iterate on a topological space composed only of integers, when the associated algorithms manipulate machine numbers: the theoretical framework of study is exactly that of practical applications. We can also, through a topological semi-conjugation, reduce these asynchronous iterations to a simple dynamic system over an interval of R, but the inherited topology is not that of the order [START_REF] Guyeux | Le désordre des itérations chaotiques -Applications aux réseaux de capteurs, à la dissimulation d'information, et aux fonctions de hachage[END_REF]. This rewriting of asynchronous iterations in the form of discrete dynamic systems has allowed us to study their dynamics using mathematical analysis tools: mathematical topology, and more recently measurement theory for ergodicity concepts.

In what follows, we will first recall the key concepts of the study of the disorder and randomness of discrete dynamic systems, and then we will see to what extent asynchronous iterations can exhibit such dynamics.

The mathematical Theory of Chaos

Notations and terminologies

Let's start by introducing the usual notations in discrete mathematics, which may differ from those found in the study of discrete dynamic systems. The n-th term of the sequence s is denoted by s n , the i-th component of vector v is v i , and the k-th composition of function f is denoted by

f k . Thus f k = f • f • . . . • f , k times.
The derivative of f is f , while P(X) is the set of subsets of X. B stands for the set {0; 1} with its usual algebraic structure (Boolean addition, multiplication, and negation), while N and R are the notations of the natural numbers and real ones. X Y is the set of applications from Y to X , and so X N means the set of sequences belonging in X . x stands for the integral part of a real x (the greatest integer lower than x). Finally, a; b = {a, a + 1, . . . , b} is the set of integers ranging from a to b.

With these notations in place, we are now able to introduce various classical notions of disorder or randomness for discrete dynamic systems.

Devaney-based approaches

In these approaches, three ingredients are necessary for unpredictability [START_REF] Formenti | Automates cellulaires et chaos : de la vision topologique à la vision algorithmique[END_REF]. First, the system must be inherently complicated, indecomposable: it cannot be simplified into two systems. Subsystems that do not interact, allowing a divide and conquer strategy to be adopted applied to the system is ineffective. In particular, many orbits must visit the entire space. Second, an element of regularity is added, to offset the effects of inflation. The effects of the first ingredient, leading to the fact that closed points can behave in a completely different way, and this behavior can not be predicted. Finally, system sensitivity is required as a third ingredient, so that close points can eventually become distant during system iterations. This last requirement is often implied by the first two ingredients. Having this understanding of an unpredictable dynamic system, Devaney formalized in the following definition of chaos.

Definition 5 A discrete dynamical system x 0 ∈ X , x n+1 = f (x n ) on a metric space (X , d) is chaotic according to Devaney if: 1. Transitivity: For each couple of open sets A, B ⊂ X , ∃k ∈ N s.t. f k (A) ∩ B = ∅.
2. Regularity: Periodic points are dense in X .

3. Sensibility to the initial conditions: ∃ε > 0 s.t.

∀x ∈ X , ∀δ > 0, ∃y ∈ X , ∃n ∈ N, d(x, y) < δ and d(f n (x), f n (y)) ε.

With regard to the sensitivity ingredient, it can be reformulated as follows.

• (X , f ) is unstable if all its points are unstable: ∀x ∈ X , ∃ε > 0, ∀δ > 0, ∃y ∈ X , ∃n ∈ N, d(x, y) < δ and d(f n (x), f n (y)) ε.

• (X , f ) is expansive if ∃ε > 0, ∀x = y, ∃n ∈ N, d(f n (x), f n (y)) ε
The system can be intrinsically complicated too for various other understandings of this desire, which are not equivalent to each other, such as:

• Topological mixing: for all pairs of open disjointed sets that are not empty U, V ,

∃n 0 ∈ N s.t. ∀n n 0 , f n (U ) ∩ V = ∅.
• Strong transitivity: ∀x, y ∈ X , ∀r > 0, ∃z ∈ B(x, r), ∃n ∈ N, f n (z) = y.

• Total transitivity: ∀n 1, the composition f n is transitive.

• Undecomposable: it is not the union of two closed, non-empty subsets that are positively invariant (f (A) ⊂ A).

These various definitions lead to various notions of chaos. For example, a dynamic system is chaotic according to Wiggins if it is transitive and sensitive to initial conditions. It is said to be chaotic according to Knudsen if it has a dense orbit while being sensitive. Finally, we speak of expansive chaos when the properties of transitivity, regularity and expansiveness are satisfied.

Approach from Li and Yorke

The approach to chaos presented in the previous section, considering that a chaotic system is an inherently complicated (non-decomposable) system, with possibly an element of regularity and/or sensitivity, has been supplemented by another understanding of chaos. Indeed, as "randomness" or "infiniteness", it is impossible to find a single universal definition of chaos. The types of behaviours we are trying to describe are too complicated to fit into a single definition. Instead, a wide range of mathematical descriptions have been proposed over the past decades, all of which are theoretically justified. Each of these definitions illustrates specific aspects of chaotic behaviour.

The first of these parallel approaches can be found in the pioneering work of Li and Yorke [START_REF] Li | Period three implies chaos[END_REF]. In their famous article entitled "The Third Period Involves Chaos", they rediscovered a weaker formulation of Sarkovskii's theorem, which means that when a discrete dynamic system (f, [0.1]), with continuous f , has a cycle 3, then it also has a cycle n, ∀n 2. The community has not adopted this definition of chaos, as several degenerate systems satisfy this property. However, on their article [START_REF] Li | Period three implies chaos[END_REF], Li and Yorke also studied another interesting property, which led to a notion of chaos "according to Li and Yorke" recalled below.

Definition 6 Let (X , d) a metric space and f : X -→ X a continuous map on this space. (x, y) ∈ X 2 is a scrambled couple of points if lim inf n→∞ d(f n (x), f n (y)) = 0 and lim sup n→∞ d(f n (x), f n (y)) > 0 (in other words, the two orbits oscillate eachother).

A scrambled set is a set in which any couple of points are a scrambled couple, whereas a Li-Yorke chaotic system is a system possessing an uncountable scrambled set.

Lyapunov exponent

The next measure of chaos that will be considered in this document is the Lyapunov exponent. This quantity characterizes the rate of separation of the trajectories infinitely close. Indeed, two trajectories in the phase space with initial separation δ diverge at a rate approximately equal to δe λt , where λ is the exponent Lyapunov, which is defined by: Definition 7 Let x 0 ∈ R and f : R -→ R be a differentiable function. The Lyapunov exponent is defined by λ(x 0 ) = lim

n→+∞ 1 n n i=1 ln f x i-1 .
Obviously, this exponent must be positive to have a multiplication of initial errors by an exponentially increasing factor, and therefore be in a situation of chaos according to this formulation.

Topological entropy

Let (X , d) a compact metric space and f : X -→ X a continuous map for this space. ∀n ∈ N, a new distance d n is defined on X by

d n (x, y) = max{d(f i (x), f i (y)) : 0 ≤ i < n}.
With ε > 0 and n 1, two points of X are ε closed compared to this measure if their first n iterates are ε closed. This measurement makes it possible to distinguish in the vicinity of an orbit the points that move away from each other during the iteration of the points that travel together. A subset E of X is said to be (n, ε)-separated if each pair of distinct points of E is at least ε separated in the metric d n . Indicates by N (n, ε) the maximum cardinality of a separate set (n, ε). N (n, ε) represents the number of distinct orbit segments of length n, assuming that we cannot distinguish the points in ε from each other.

Definition 8

The topological entropy of the map f is equal to

h(f ) = lim →0 lim sup n→∞ 1 n
log N (n, ) .

The limit defining h(f ) can be interpreted as a measure of the average exponential growth of the number of distinct orbit segments. In this sense, it measures the complexity of the dynamical system (X , f ).

The disorder of asynchronous iterations

The topological space over which asynchronous iterations are defined was first studied, leading to the following result [START_REF] Guyeux | A Topological Study of Chaotic Iterations. Application to Hash Functions[END_REF]: Proposition 5 X is an infinitely countable metric space, being both compact, complete, and perfect (each point is an accumulation point).

These properties are required in a specific topological formalisation of a chaotic dynamic system, justifying their proof. Concerning G f 0 , it was stated that [START_REF] Guyeux | A Topological Study of Chaotic Iterations. Application to Hash Functions[END_REF].

Proposition 6 G f 0 is surjective, but not injective, and so the dynamical system (X , G f 0 ) is not reversible.

It is now possible to recall the topological behaviour of asynchronous iterations.

We have firstly stated that [START_REF] Guyeux | A Topological Study of Chaotic Iterations. Application to Hash Functions[END_REF]:

Theorem 1 G f 0 is regular and transitive on (X , d), so it is chaotic as defined by Devaney. In addition, its sensitivity constant is greater than N -1.

Thus the set C of functions f : B N -→ B N making asynchronous iterations of Definition 2 a case of chaos according to Devaney, is a not empty set. To characterize the functions of C, we first stated that transitivity implies regularity for these particular iterated systems [START_REF] Bahi | On the Link Between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems[END_REF].

To achieve characterization, the function F f allows to define a graph Γ f , where the vertices are the vectors of Z/2Z, and there is a ridge labeled s ∈ P ( 1, N ) from i to j if, and only if F f (i, s) = j. We have shown that the properties of the dynamic system G f are strongly related to those of the graph G f . Thus, for example, if the latter is strongly related, then the asynchronous iterations are highly transitive and regular, and therefore chaos in Devaney's mathematical sense. Other properties, such as topological entropy, expansiveness, or sensitivity to initial conditions, defined in topological terms, could also be studied. On the other hand, the subsets of 1, N can be drawn according to a certain probability distribution, which allows to study the associated Markov chain (ergodicity, mixing time, etc.) These various disorder results are presented below [START_REF] Bahi | On the Link Between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems[END_REF].

Theorem 2 G f is transitive, and thus chaotic according to Devaney, if and only if Γ(f ) is strongly connected.

This characterization allows to quantify the number of functions in

C: it is equal to 2 N 2 N
. Then, the study of the topological properties of the disorder of these iterative systems was the subject of a more detailed study which led to the following results.

Theorem 3 ∀f ∈ C, P er (G f ) is infinitely countable, G f is strongly transitive and is chaotic according to Knudsen. It is thus undecomposable, unstable, and chaotic as defined by Wiggins.

Theorem 4 (X , G f 0 ) is topologically mixing, expansive (with a constant equal to 1), chaotic as defined by Li and Yorke, and has a topological entropy and an exponent of Lyapunov both equal to ln(N).

At this stage, a new type of iterative systems that only handle integers has been discovered, leading to the questioning of their computing for security applications. The applications of these chaotic machines and avenues for theoretical exploration will be proposed in the discussion section.

Discussion

The theoretical developments around the disorder of asynchronous iterations, presented above, have led to interesting and original advances in applications. In [START_REF] Guyeux | Le désordre des itérations chaotiques -Applications aux réseaux de capteurs, à la dissimulation d'information, et aux fonctions de hachage[END_REF], for instance, it is explained how to design finite state machines with truly chaotic behaviour. The idea is to decompartmentalize the machine, and to use at each iteration the values provided to it at the input to calculate the value to be produced at the output. By this process, even if the machine is finite state, it does not always enter a loop, since the input is not necessarily periodic. Since then, we have continued to study these chaotic machines, proposing in particular applications concerning steganography [START_REF] Couchot | STABYLO: steganography with adaptive, bbs, and binary embedding at low cost[END_REF][START_REF] Bahi | Steganography: a class of algorithms having secure properties[END_REF] and digital watermarking [START_REF] Guyeux | A new chaos-based watermarking algorithm[END_REF][START_REF] Guyeux | An improved watermarking scheme for Internet applications[END_REF][START_REF] Bahi | Lyapunov exponent evaluation of a digital watermarking scheme proven to be secure[END_REF], hash functions [START_REF] Bahi | Quality analysis of a chaotic proven keyed hash function[END_REF][START_REF] Lin | On the use of chaotic iterations to design keyed hash function[END_REF], and the generation of pseudo-random numbers [START_REF] Couchot | Pseudorandom number generators with balanced gray codes[END_REF][START_REF] Contassot-Vivier | Random walk in a n-cube without hamiltonian cycle to chaotic pseudorandom number generation: Theoretical and practical considerations[END_REF].

A second field of investigation seemed very interesting based on the modeling, study and simulation of complex systems from disciplines other than computing, that is, processes whose complex dynamics can take the following form: an operation taken from a possible set of functions, and applied only to a variable subset of system coordinates. Such complex dynamics occur naturally in molecular biology, and more particularly in the spatial folding of proteins. This is why the model commonly used in protein conformation prediction tools, known as the 2D/3D HP square lattice model, has been rewritten using a discrete dynamic system in asynchronous iterations, and we proved that this system had several chaos properties [START_REF] Bahi | Chaos of protein folding[END_REF].

Until now, the rewriting of asynchronous iterations as discrete dynamical systems has only been used to study the disorder, the maximum divergence that can be obtained by such iterations, the application framework targeted being computer security: the generation of pseudo-random numbers, hash functions, and symmetric encryption operation modes. With these elements in mind, we plan to pursue this research in various directions, building on the work carried out over many years on the convergence criteria for asynchronous iterative methods. This will make it possible to deepen the knowledge of cases of divergence (and convergence, studied in particular with tools of measurement theory) of such iterations, taking into account the delay.

Indeed, if the asynchronous iterations were initially studied for their convergence, in particular within the framework of distributed digital algorithmics, their reformulation in the form of a dynamic system, then a graph, was only studied for divergence purposes. We would therefore like to study what these reforms can bring to the study of the convergence of such asynchronous iterations. We also intend to bring convergence results from the world of dynamic systems to that of discrete mathematics. Finally, until now, the delay has not been taken into consideration: we consider that the vector at time t is deduced from the vector at time t -1, and depends on a continuous function and a sequence of coordinates to be updated. In other words, we assume that the stochastic process associated with asynchronous iterations satisfies Markov's property, and we wish in further work to consider the case where this is no longer true. This applies to both convergence and divergence. These results will be applied to a better understanding of the spatial and temporal evolution dynamics of biological sequences (genomes and proteins), and in particular will make it possible to increase knowledge about the generation of pseudo-random numbers.

This study was financed in part by the EIPHI Graduate School (contract "ANR-17-EURE-0002") and by the Interreg RESponSE project.


Nesrine Khernane
email: nesrine.khernane@univ-fcomte.fr

Jean-Franc ¸ois Couchot
email: jean-francois.couchot@univ-fcomte.fr

Ahmed Mostefaoui
email: ahmed.mostefaoui@univ-fcomte.fr

Joint Routing/Encoding-Power for Network Lifetime Maximization in WVSN

One of the most important issues, in Wireless video sensor networks (WVSNs), is to achieve an optimal video data encoding through an efficient resource allocation, while maximizing the overall network lifetime. However, the multimedia data is usually voluminous and delivering the compressed video data to the forwarding node poses an emergent demand, to simultaneously optimizing the video encoding and data routing performance in order to maximize the network lifetime. Based on unknown routing matrix, in this paper, we focus on the integration of routing into the analytic model proposed in our previous work. The simulation results show that our proposed solution consumes less than 0.03% of the total battery and ensures a prolongation of the network lifetime compared to the literature approaches.

I. INTRODUCTION

Multimedia sensor networks have been widely regarded as a promising emerging application [START_REF] Kim | Low power routing and channel allocation method of wireless video sensor networks for internet of things (iot)[END_REF]. Thus, it can take advantages in many applications, such us the smart parking advice systems. According to the research firm Navigant Research, such systems are expected to grow rapidly (i.e., up to one million on-street spaces by 2024) [START_REF] Chodosh | Can we park smarter? a project of nyu's science, health and environmental reporting program[END_REF].

a) Motivations: WMSN should ensure the transmission of multimedia content, implying a high data rates and thus a high bandwidth requirement. To cope with this problem, a multimedia content can be compressed. However, more is the compression level of the multimedia data, less is the number of bits to transmit, and hence large is the distortion. On the other side, if we decrease the level of the compression, the data rate increases.

Thus, two main challenges should be considered: a) the encoding of the multimedia content with respect to the desired video quality at the sink and b) the reliable routing of the latter, since the choosing routing protocol can highly influence the network lifetime as shown in [START_REF] Khernane | Routing impact on network lifetime maximization using power/rate trade-off in wvsn[END_REF].

In fine, processing and delivery of multimedia content are not independent each other, and their interaction has a major impact on network lifetime.

b) Contributions: Several approaches have been proposed to ensure a power/rate tradeoff for network lifetime maximization. However, the routing issue has been left as a separate field (i.e., the routing matrix was pre-defined and considered as an input), and none of the research works have actually considered an unknown routing matrix.

In this paper, we confine our interest to the integration of the routing issue, based on an unknown routing matrix, in the analytic model proposed in our previous work [START_REF] Khernane | Maximizing network lifetime in wireless video sensor networks under quality constraints[END_REF], that ensures a trade-off between the desirable visual quality and the available network's resources. Thus, the main contributions of this paper are:

• we prove that the problem of choosing a single routing protocol among N routing protocols is NP-complete, • we propose a solution that optimally selects the forwarding nodes, • we integrate the proposed solution into the analytic model proposed in [START_REF] Khernane | Maximizing network lifetime in wireless video sensor networks under quality constraints[END_REF],

• the resolution of the novel optimization problem is distributed and can handle the topology change, in contrast to the approaches proposed in the literature. In the same context, we have proposed two other solutions that ensure a multipath routing with disjoint paths. The objective of the latter is to cope with both: the huge volume of data rates and link failure, and thus minimize the energy consumption of the intermediate nodes.

Furthermore, we conducted an in-depth simulation analysis of the proposed approaches over two main parameters: battery consumption, and network lifetime. The simulation results show that our proposed solution ensures the convergence of the system, consumes less than 0.03% of the total battery and ensures a prolongation of the network lifetime compared to the literature approaches.

II. RELATED WORK In this section we outline some of the proposed solution in the literature, which we broadly classify into two categories.

A. Power-Rate-Distortion approaches

Based on the Power-rate-Distortion (P-R-D) model [START_REF] He | Resource allocation and performance analysis of wireless video sensors[END_REF], authors in [START_REF] He | Distributed algorithms for network lifetime maximization in wireless visual sensor networks[END_REF] and [START_REF] Arar | Optimal resource allocation for green and clustered video sensor networks[END_REF] have proposed a decentralized solution. A mathematical model that considers the encoding powers, and the data distortion was developed. However, authors in [START_REF] He | Distributed algorithms for network lifetime maximization in wireless visual sensor networks[END_REF] did not ensure the convergence for any initial configuration which may lead to no feasible solution.

Through another P-R-D model [START_REF] Lin | Optimal joint power-rate adaptation for error resilient video coding[END_REF], authors in [START_REF] Gürses | Distributed quality-lifetime maximization in wireless video sensor networks[END_REF] have proposed a solution, in which the distortion model was considered in the objective function instead of considering it as a constraint. The formulated problem was solved using the Proximal Point Algorithm. However, the inverse lifetime was computed in a centralized manner by the sink.

In a similar work, an appropriate trade-off between the minimum data distortion and maximum network lifetime was studied in [START_REF] Zou | Lifetime and distortion optimization with joint source/channel rate adaptation and network coding-based error control in wireless video sensor networks[END_REF], the formulated problem was solved in a distributed manner by primal decomposition. In [START_REF] Zou | Modeling and optimization of network lifetime in wireless video sensor networks[END_REF], the authors have proposed a fully distributed solution that jointly optimizes the network coding based multi-path routing. However, both of the aforementioned solutions used the network coding during problem formulation, which requires the decoding and the encoding of the transmitted data at the intermediate nodes resulting in an additional power consumption.

Furthermore, all of the aforementioned approaches consider a pre-defined routing matrix.

B. Routing approaches

Authors in [START_REF] Park | Maximum lifetime routing in wireless sensor networks[END_REF] have shown that the problem of routing messages, in a wireless sensor network to maximize network lifetime, is NP-hard. Starting from this point they propose a heuristic solution. While in [START_REF] Madan | Distributed algorithms for maximum lifetime routing in wireless sensor networks[END_REF] authors have focused on the problem of computing a flow that maximizes the lifetime of the network. However, in these papers the transmission rate on each link is fixed.

In order to meet: delay, packet-loss, energy and memory, authors in [START_REF] Cobo | Ant-based routing for wireless multimedia sensor networks using multiple qos metrics[END_REF] have only addressed the routing scheme between the cluster heads and the sink. However, the control packets used in this solution can cause a high overhead. By exploiting the geographic locations and QoS performance of the neighbor nodes, authors in [START_REF] Razzaque | Data-centric multiobjective qos-aware routing protocol for body sensor networks[END_REF] have implemented a localized hop-byhop routing. The problem was formulated using the multiobjective Lexicographic Optimization (LO) approach.

Nonetheless, the aforementioned routing protocols did not consider at all the encoding power at each node.

To the best of our knowledge, the only work that considered both: a) power-rate-distortion optimization, b) and routing discovery in WMSNs, was described in [START_REF] Kim | Low power routing and channel allocation of wireless video sensor networks using wireless link utilization[END_REF]. However, the optimization problem does not consider the reception power consumption. Additionally, the routing information are monitored by the sink (i.e., in a centralized manner).

III. NP-COMPLETENESS PROOF Including routing issue leads to the following problem: how to select the optimal routing path among all available ones?. The "brute-force" approach is to test all the existing routing paths and then selecting the optimal one with regard to the metric of prolonging the network lifetime. However, including all the existing routing protocols within the same optimization problem can induce a long activity duration implying more energy consumption and hence low network lifetime. To deal with this problem, it is necessary to find a routing protocols execution scheduling in such a way that execution time does not exceed a certain threshold.

Let P 1 be the problem of executing N routing protocols on a single instance of network. Each routing protocol has an execution time denoted t i . The main objective here is to find a scheduling that minimizes the positive number L = N i=1 t i . This function tends to minimize the execution time of the routing protocols.

Theorem 1: The decision problem corresponding to the aforementioned problem is NP-complete.

Proof 1: Let N be the number of the routing protocols, with t i the execution time of the routing protocol i, and a positive number T . Is there a scheduling such as L ≤ T ?

• Given a solution, it is clear that the time taken to verify whether it is valid or not is O(N ).

• The problem, denoted by P 2 , that we will reduce to P 1 is Knapsack problem, which is defined as the following:

A set S = {x 1 , x 2 , x 3 , ..., x n } of n numbers and a positive number y such that:

n i=1 x i = y, is there A ⊂ S such that: n i=1 x i ≤ y?
Let us now construct the polynomial reduction f of the Knapsack problem to our P 1 problem, in such a way that an instance I of Knapsack problem, have a "yes" answer, if and only if f (I), an instance of our problem, has a "yes" answer. Let I be an instance of Knapsack problem. An instance f (I) of our problem can be formulated as the following:

• N = n + 1;

• t i = x i ; N i=1 t i = n i=1 x i + 1; • t n+1 = 1; n+1 i=1 t i = y + 1.
1) We will prove now that L ≤ T if and only if there is a set A such that n i=1 x i ≤ y. Suppose that the subset A such that n i=1 x i ≤ y exists. Then, consider a scheduling that executes first the subset A in an arbitrary order, then the n+1 routing protocol, afterward the S-A subset. The routing protocols in a subset A ends at y in the worst cases, since n i=1 x i ≤ y. The y routing protocol ends at n + 1, and the rest of routing protocols ends at n i=1 x i + 1. Thus all routing protocols were executed and thus L ≤ T . We can conclude that if the Knapsack problem has a solution then P 1 has also.

2) Suppose now that our problem P 1 has a solution, thus we have to prove that the Knapsack problem has also a solution. In order to prove this implication, it is simpler to show its contraposition. In other words, suppose that the Knapsack problem does not have a solution which implies that there is no solution A ⊂ S such that n i=1 x i ≤ y. Let A be the subset of the routing protocols executed before the n + 1 routing protocol, which implies that the execution of A ends at:

E A = n i=1
x i > y , by hypothesis. The n + 1 routing protocol will be executed after and ends at E A + 1, and thus L > T . Therefore, if the Knapsack problem has a negative response, then P 1 also. The Knapsack problem is equivalent to our problem, and thus, we can conclude that P 1 is NP-complete. The NP-completeness of the studied problem led us to develop an heuristic, that takes into account especially the energy consumption since the main objective is to maximize the network lifetime.

IV. NETWORK MODEL We consider a multimedia sensor network consisting of N multimedia sensors. These tiny devices have to find the optimal path consuming the minimum energy toward the sink. Thus, our network can be defined as follows:

• An oriented graph G(V, L), where V = {h 1 , . . . , h n } is a set of video sensor nodes and L = {l ij | h i , h j ∈ V} is a set of oriented links. • Two routing matrices a + il and a - il of size N * L denote the matrices of outgoing links and incoming links, respectively. Their elements are defined as: a + il (resp. a - il matrix) equals to 1, if a given link l is an outgoing link from i (resp. an incoming link to) and 0 otherwise. • Then, a general routing matrix a il of size N * L can be formulated as the following: a il = a + il -a - il . Note that, each node h generates a multimedia traffic of rate R h . The generated traffic can be forwarded to the sink using intermediate nodes. Therefore, the flow conservation [START_REF] He | Distributed algorithms for network lifetime maximization in wireless visual sensor networks[END_REF], denoted η hi , at each node must be formulated as follows:

η hi = l∈L a il x hl =    R h if i is the source of the traffic -R h if i is the sink 0 otherwise.
(1) where x hl represents the data rate, originated from node h, at link l. Figure 1 shows an example of a directed WMSNs deployed in a region of 50mx50m.

V. THEORETICAL BACKGROUND

A. Node Power Consumption Model

In this subsection, we formalize the different powers consumed by each node for video coding and data routing.

1) Video coding power consumption: the main objective here is to minimize the video distortion, while considering the encoding power level. Authors in [START_REF] He | Resource allocation and performance analysis of wireless video sensors[END_REF] have proposed the following power-rate-distortion (P-R-D) model:

D h = σ 2 e -γ.R h .P 2/3 sh , (2)
where σ 2 is the average input variance, D h is the encoding distortion, and γ is the encoding efficiency coefficient, R h is the source rate and P sh is the encoding power.

2) Transmission and reception power consumption: using the power Consumption model presented in [START_REF] Heinzelman | An application-specific protocol architecture for wireless microsensor networks[END_REF], the data transmission and reception is formulated, respectively, as:

P ti = l∈L a + il * (α+βd np l ) * h∈V x hl , P ri = c r * l∈L a - il * h∈V x hl , (3)
where α and β are transmit electronics parameters, d l is the distance between the transmitter and the receiver, n p is the path-loss exponent, h∈V x hl corresponds to the aggregate rate transmitted through link l, and c r is the radio receiver energy consumption cost.

Then, the total power dissipation at node i can be formulated as:

P i = P sh + P ti + P ri (4)
where P sh = 0, if i is the sink node (i.e., i = N ).

B. Network Power Consumption Model

In this paper, we consider critical applications where the exhaustion of energy of the first node will cause the failure of the whole network. Therefore, and by assuming that each node i has initial energy denoted B i , the network lifetime T net is defined as:

T net = min i∈N B i /P i . (5)

C. Distributed Bellman Ford formulation

Based on the literature, the shortest path represents the minimum-energy routing topology if data is not aggregated [START_REF] Cheng | Joint routing and link rate allocation under bandwidth and energy constraints in sensor networks[END_REF]. For this reason, we have chosen to implement the distributed Bellman Ford algorithm, that has the following formulation [2]:

D i = min j [d ij + D j ], (6)
where D i is the shortest distance from node i to the destination and d ij is the distance from node i to j (j is a one-hop neighbor of i, denoted by N brs i ). The include of the minimum in ( 6) means that the closest neighbor is selected.

D. Disjoint Paths

The benefits of disjoint path routing are significant for high data multimedia applications [START_REF] Seo | Disjoint-path routing: Efficient communication for streaming applications[END_REF], it can be used to split the high data over the existing paths or to cope with the links' failure. However, the disjoint paths problem is known to be NP-complete in directed graphs, and can be defined as follows [START_REF] Iqbal | Disjoint paths in networks[END_REF]: Given a directed network G = (N , L) of N nodes and L weighted links. Find k paths P 1 , P 2 , ..., P k from i ∈ N to the sink node, such that the paths share minimal common links.

VI. PROBLEM FORMULATION As previously mentioned, we aim to integrate the routing problem into the analytic model proposed in [START_REF] Khernane | Maximizing network lifetime in wireless video sensor networks under quality constraints[END_REF] that ensures a trade-off between the desirable visual quality at the sink and the available network's resources.

Before going further let us briefly recall the analytical model proposed in our previous work [START_REF] Khernane | Maximizing network lifetime in wireless video sensor networks under quality constraints[END_REF].

a) Literature review: The maximization of the network lifetime can be expressed by minimizing the inverse lifetime given in [START_REF] Chodosh | Can we park smarter? a project of nyu's science, health and environmental reporting program[END_REF]. Let q = 1/T net be the inverse lifetime of the network. However, using q in the problem formulation can not lead to solve this latter in a fully distributed manner.

To cope with this problem, an auxiliary variable, q i (∀i ∈ N ), has been introduced and maintained at each individual node i that should be followed by the following constraint: i∈N a il .q i = 0 (∀l ∈ L). Firstly, to ensure convexity of the objective function, minimizing q is equivalent to minimize |N |q 2 , which is equivalent to: i∈N q 2 i , using the auxiliary variable q i . On the other side, we have introduced the following exponents to the corresponding functions (i.e., R h , x hl and P sh ): 2, 2, and 8/3 respectively, with some regular factors (namely δ r , δ x and δ p ), to ensure a strict convexity of the problem, more details can be found in [START_REF] Khernane | Maximizing network lifetime in wireless video sensor networks under quality constraints[END_REF]. Then, the problem can be formulated as follows: minimize (q,r,x,Ps) i∈N

q 2 i + δ x h,l x 2 hl + δ r h R 2 h + δ p h P 8/3 sh subject to l∈L a il x hl = η hi ∀h ∈ V ∀i ∈ N , σ 2 e -γR h P 2/3 sh ≤ D h ∀h ∈ V, P sh + P ti + P ri ≤ q i B i ∀i ∈ N , i∈N a il q i = 0 ∀l ∈ L,
x hl ≥ 0, R h ≥ 0, P sh > 0.

(7) Let us now introduce the routing constraints to (7): minimize (q,r,x,Ps) i∈N

q 2 i + δ x h,l x 2 hl + δ r h R 2 h + δ p h P 8/3 sh subject to 1) l∈L a il x hl = η hi ∀h ∈ V ∀i ∈ N , 2) σ 2 e -γR h P 2/3 sh ≤ D h ∀h ∈ V, 3) P sh + P ti + P ri ≤ q i B i ∀i ∈ N , 4) i∈N a il q i = 0 ∀l ∈ L, 5) D i = min j [d ij + D j ] ∀i ∈ N ∀j ∈ N brs i 6) a + il = {0, 1} ∀i ∈ N ∀l ∈ L, 7) a - il = {0, 1} ∀i ∈ N ∀l ∈ L, 8) x hl ≥ 0, R h ≥ 0, P sh > 0.
(8) The first constraint reflects the flow conservation maintained at each node. The second constraint ensures the respect of the desired video quality. The third constraint presents the network lifetime with respect to the minimum node lifetime. The fourth constraint ensures the convergence of the system. The fifth constraint presents the shortest path from i to the destination going through the best neighbor. The sixth and seventh constraints present the indicators of the sender and the receiver, respectively. The rest of constraints ensures that all the variables remain positive.

VII. DISTRIBUTED RESOLUTION

In this section we present the resolution of Problem [START_REF] He | Distributed algorithms for network lifetime maximization in wireless visual sensor networks[END_REF]. Due to the rich structure of this problem, a decomposition approach can be applied. Firstly, a primal decomposition with respect to the coupling variables (a + il , a - il ) is required. Then, the dual problem can be formulated with respect to the coupling constraints (1), ( 2), ( 3) and (4). Finally, the original optimization problem (8) can be decomposed into two subproblems as follows:

P1:min (q,r,x,Ps) i∈N

q 2 i + δ x h,l x αx hl + δ r h R αr h + δ p h P αp sh
subject to (1), ( 2), ( 3), ( 4), [START_REF] He | Distributed algorithms for network lifetime maximization in wireless visual sensor networks[END_REF]. P2:min

(a + il ,a - il ) U * (a + il , a - il )
subject to (5), ( 6), [START_REF] Gürses | Distributed quality-lifetime maximization in wireless video sensor networks[END_REF].

Note that, the resolution of the P1 problem is achieved if and only if the coupling variables (a + il , a - il ) are fixed, since these two matrix are needed in the first, third and fourth constraints that are attached to the P1 problem. However, a + il and a - il are updated through P2, thus, U * (a + il , a - il ) aims to minimize the number of paths and can be viewed as the optimal value for the resolution of P1.

A. P2 resolution

Next, we discuss how to update the coupling variable (a + il , a - il ), based on the distributed Bellman Ford method. The path discovery steps are executed according to the following:

1) Neighboring discover: In this phase each video sensor node i ∈ V broadcasts a HELLO message in order to have the geometric coordination of its neighbors, and updates its neighboring table. At the end of this phase, each node i will construct its routing matrices (i.e., a + il and a - il ), as well as the the routing matrices of the outgoing and incoming links of its one-hop neighbors j ∈ Nbrs i (i.e., a + jl and a - jl , respectively). 2) Path establishment: After the neighboring discover phase, each sensor node i initiates the Bellman Ford algorithm by sending d ij + D i , where D i = 0 if i is the source and D i = ∞ otherwise. At the reception of a such message each node j ∈ Nbrs i checks if D j > d ij + D i . If "yes" j proceeds as follows:

• Set D j = d ij + D i ,
• send the estimate d jk +D j to each sensor node k ∈ Nbrs j ,

• the operation continues until the sink node.

3) Path confirmation: At the end of the Path establishment phase, the sink node should maintain the shortest distance from each node to the latter as well as the latest node through which it has received this distance. Then, in the path confirmation phase the sink node sends a pathConf message through the inverse path.

4) Disjoint Path: In order to construct multi-paths, the sink node instead of maintaining only the shortest distance from each node to the latter, it maintains the two or three shortest distances paths. On the other hand, to ensure a disjoint paths and avoid to have paths with shared node, we limit each node to accept only one message from an intermediate node with a given sequence number. Thus, nodes that receives more than one message, maintains the one with the minimum cost and ignores the rest.

B. P1 resolution

Lagrangian Dual based methods [START_REF] Palomar | A tutorial on decomposition methods for network utility maximization. Selected Areas in Communications[END_REF] can be used to solve a P1 problem. Thus, it can be written as below: For any h ∈ V, i ∈ N , and l ∈ L, and where u i , v h , λ h,i , w l are the Lagrange multipliers.

L(R, x, P s , q, u, v, λ, w) = i∈N q 2 i + δ x h,l x αx hl + δ r h R αr h + δ p h P αp sh + h∈V i∈N u hi l∈L a il .x hl -η hi + h∈V v h ln(σ 2 /D h ) γP 2/3 sh -R h + i∈N λ i (P i -q i B i ) + l∈L w l i∈N a il q i (10)
Following the subgradient method [START_REF] Bertsekas | Convex analysis and optimization[END_REF], the different Lagrange multipliers can be iteratively calculated, as follows:

u k+1 hi = u k hi -θ k η k hi -l∈L a il .x k hl v k+1 h = max 0, v k h -θ k R k h - ln(σ 2 /D h ) γ(P k sh ) 2/3 λ k+1 i = max 0, λ k i -θ k q k i B i -P k ti -P k ri w k+1 l = w k l + θ k i∈N a il q k i ( 11
)
Where θ k represents the step size and given by: θ k = ρ/k 1/2 , where ρ > 0 and k > 0.

All the functions to be minimized are differentiable, and thus, can be computed in one step as follows:

q k i = max , -( l∈L a il w l -λ i B i ) 2 P k sh = max      ,   -3λ k h + (3λ k h ) 2 + 64δ p .v k h /γ. ln(σ 2 /D h ) 16δ p   3 5      R k h = max 0, v h k 2δ r
x k h,l = max 0, -i∈N λ k i (P ti + P ri ) + u k hi a il 2δ x for any h ∈ V, i ∈ N , and l ∈ L.

VIII. SIMULATION RESULTS

In this section, we evaluate our routing/power-rate tradeoff approach,using the topology given in Figure 1, through simulation. The model was implemented using OMNET++ simulator [START_REF] Varga | Discrete event simulation system[END_REF], through MiXiM framework [START_REF] Köpke | Simulating wireless and mobile networks in omnet++ the mixim vision[END_REF]. The values of the simulation parameters are presented in Table I.

A. Convergence of the proposed solution

The convergence of the auxiliary variable q i to a common q, can be observed in figure 2, where we can see that after a 10 -2 convergence threshold, the system is almost stable. Thus, in the following, we consider the system as completely stable when the maximum variation between the q i is T = 10 -2 .

B. Optimization cost

In this subsection we analyze the cost of the optimization steps on both energy and duration at each node. , node 2 and node 2 for one path, two paths and three paths, respectively. Thus, it concerns the total energy requirement for the optimization steps of both P1 and P2. We can observe that the two paths routing protocol is the least energy applicant routing protocol, even less than the one path routing protocol. This observation can be explained by the fact the one path routing protocol requires much more iterations to converge and thus, it can get to the point of consuming more energy. Even though, we can conclude that the optimization steps including both P1 and P2 consume a negligible energy. Fig. 3: battery consumption of optimization steps 2) Optimization steps duration: In this stage of evaluation, we present the need in term of duration (in minute) of the optimization steps to converge to the common variable q. Figure 4 presents the optimization steps duration including both: P1 plus P2, for each threshold T ≤ 10 -3 of the last converging nodes (namely, node 7, node 2 and node 2 for one path, two paths and three, respectively). It can be observed that more is the need to gain precision, more is the optimization duration.

C. Node lifetime improvement

The node lifetime can be calculated using the following formula: T i = B i /P i .

Figure 5 shows the lowest improvement of nodes lifetime. We can see that with our optimization steps, and by including the routing constraints in the analytical model while imposing a trade-off between P sh and R h , we have increased the network lifetime by at least 7.72, 12.53 and 11.95 times considering the minimum nodes lifetime (i.e., node 7, node 2 Fig. 4: Optimization duration and node 2 for one path, two paths and three, respectively). We can also observe that the two and three paths routing protocols ensure the hightest network lifetime, since the multimedia content is distributed over the existing outgoing links. And thus, it demonstrates that the proposed design effectively increases the nodes lifetime and thus the network lifetime. In wireless video sensor networks, the video coding and multimedia content transport are the most energy consuming tasks, and hence impact the overall network lifetime. Thus, both of the processing and delivery of multimedia content should be considered, since their interaction has a major impact on network lifetime. In this paper, based on our previous study on power/rate tradeoff for network lifetime maximization, we have proposed a novel analytical model for video coding and multimedia content delivery. The optimization problem was solved over a two level optimization. Simulation results approve the effectiveness of the proposed solution, given its minimal requirements in terms of computational power and energy consumption.

Fig. 1 :

 1 Fig. 1: Example of a WMSN.

Fig. 2 :

 2 Fig. 2: Auxiliary variables

Fig. 5 :

 5 Fig. 5: Remaining lifetime after each convergence threshold

TABLE I :

 I Configuration of model parameters in a WVSN[START_REF] He | Distributed algorithms for network lifetime maximization in wireless visual sensor networks[END_REF]


Stéphane Chrétien
email: stephane.chretien@npl.co.uk

Christophe Guyeux
email: christophe.guyeux@femto.fr

Online shortest paths with confidence intervals for routing in a time varying random network

The increase in the world's population and rising standards of living is leading to an ever-increasing number of vehicles on the roads, and with it ever-increasing difficulties in traffic management. This traffic management in transport networks can be clearly optimized by using information and communication technologies referred as Intelligent Transport Systems (ITS). This management problem is usually reformulated as finding the shortest path in a time varying random graph. In this article, an online shortest path computation using stochastic gradient descent is proposed. This routing algorithm for ITS traffic management is based on the online Frank-Wolfe approach. Our improvement enables to find a confidence interval for the shortest path, by using the stochastic gradient algorithm for approximate Bayesian inference. The theory required to understand our approach is provided, as well as the implementation details.

I. INTRODUCTION

A. Motivation

Information and communication technologies have a great potential impact in the field of traffic and mobility management with a goal to achieve a safer and better optimized use of the transport network [START_REF] Elizondo | An intelligent traffic network optimisation by use of bayesian inference methods to combat air pollution in local urban areas[END_REF]. Optimal routing is one of the key tasks involved in intelligent planning and an extensive body of work has been devoted to this topic since the 60's. The optimal routing problem is well known in the combinatorial optimisation community under the name of the shortest path problem. Since the advent of Linear Programming in the 50's, a great number of optimisation problems related to logistics and planning have be shown to be special instances of convex optimisation. The shortest path problem, in particular, is one of these problems for which a solution can be found in polynomial time using linear programming, and even faster algorithms are available such as the celebrated Dijkstra algorithm (or its generalisation, namely the A* algorithm).

In real world situations, however, there is never such a thing as a static network and the data available on the edge properties are evolving drastically in time. The cause of these variations are most often multiple: in e.g. transportation networks, a periodic behavior is definitely present in the traversal time of every route segment of the graph, because of the signal repeats from one day to the other. There might also be other periodicities such as depending on the day in the week, on the season, etc. There must also be various types of trends: linear or piecewise linear trends, jumps, exponential growth, etc. Jumps may be due to various kinds of disruptions.

Piecewise linear signals can also occur in the presence of certain saturation phenomena. Exponential growth may be due to the increase of the population. On the top of this list of possible variations of the network properties come the fully random fluctuations, due to real time behavior on the roads.

B. Previous work on the stochastic shortest path problem

In the case where the network is corrupted by random perturbations only, a very important work appeared in [START_REF] Dimitri | An analysis of stochastic shortest path problems[END_REF] where the problem is discussed in great mathematical details using a Markovian decision process approach. This model was also explored in [START_REF] Harilaos | Dynamic shortest paths in acyclic networks with markovian arc costs[END_REF]. The dynamic programming approach was later refined in the subsequent paper [START_REF] Harry Polychronopoulos | Stochastic shortest path problems with recourse[END_REF] where the computational complexity is significantly improved. The paper [START_REF] Waller | On the online shortest path problem with limited arc cost dependencies[END_REF] described a model with possible spatial and temporal correlations between the edges of the network. Starting from the results in [START_REF] Waller | On the online shortest path problem with limited arc cost dependencies[END_REF], the interesting work [START_REF] Yy Fan | Shortest paths in stochastic networks with correlated link costs[END_REF] described a efficient algorithm for solving the stochastic shortest path problem with correlations. A non-stationary version of this kind of model was proposed in [START_REF] Gao | Optimal routing policy problems in stochastic time-dependent networks[END_REF] where the problem is addressed using an adaptation of dynamic programming ideas.

Our approach to the shortest path problem was inspired by the recent breakthrough of [START_REF] Jacob D Abernethy | Competing in the dark: An efficient algorithm for bandit linear optimization[END_REF] where the problem was recast as an online convex optimisation problem and the rate m

√

T was proved for a practically easy to implement algorithm. The online approach to the stochastic shortest path problem had long been interesting to the machine learning commmunity. The pioneering work by [START_REF] Takimoto | Path kernels and multiplicative updates[END_REF] and then [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF] set on the trend and proposed interesting and efficient algorithm. The partial information setting was studied in [START_REF] Awerbuch | Adaptive routing with endto-end feedback: Distributed learning and geometric approaches[END_REF] and superseeded by [START_REF] Jacob D Abernethy | Competing in the dark: An efficient algorithm for bandit linear optimization[END_REF] using online convex optimisation techniques based on the linear programming representation of the shortest path problem based on the handy convex hull representation of P u,v .

C. Our contribution

The previous works on the stochastic shortest path culminated in the discovery of the adaptive approach of [START_REF] Jacob D Abernethy | Competing in the dark: An efficient algorithm for bandit linear optimization[END_REF] for the bandit setting with a controlled regret. A recent and elementary presentation of the online Frank-Wolfe approach to the problem is proposed in [START_REF] Hazan | Introduction to online convex optimization[END_REF]Section 7]. Our interest in the online approach was sparked by the difficulty to model the intricate compound of random and deterministic behavior which enter into the type of phenomena observable on real networks.

The main ingredient we contribute to the online approach is a way to produce a confidence interval together with a shortest path. Our procedure is motivated by recent discoveries [START_REF] Mandt | Stochastic gradient descent as approximate bayesian inference[END_REF] which prove that an appropriate rescaling of the Iterate Averaging Stochastic Gradient produces a sequence which is nearly Gaussian and has a distribution governed by the Bayesian posterior associated with the estimation problem, i.e. the shortest path in our setting.

The main algorithm proposed in this paper combines the results of [START_REF] Hazan | Introduction to online convex optimization[END_REF] with those of [START_REF] Mandt | Stochastic gradient descent as approximate bayesian inference[END_REF] in order to propose an efficient way to simulate the distribution at time T of the shortest path in a stochastic and potentially non-stationary (but smoothly evolving) environment.

We demonstrate through numerical experiments the efficiency of our approach.

D. Plan of the paper

The remainder of this article is organized as follows. The proposed algorithm is described in Section II together with its practical implementation. Numerical simulations are then proposed in Section III, for the sake of illustration. This research work ends by a conclusion section, in which the contribution is summarized and intended future work is outlined.

II. ONLINE ROUTING

In this section, we describe our algorithm and its practical implementation.

A. Online shortest path computation using stochastic gradient descent

The shortest path problem in a time varying random graph is more complex to address than the standard shortest path problem in a deterministic graph.

1) Formulation: We are given a graph G = (V, E) and a source-sink pair (u, v) ∈ V 2 . Let P u,v denote the set of all paths from u to v. At each iteration t, the optimisation algorithm observes a set of weights w t ∈ R |E| + and selects a path p t ∈ P u,v . When the next iteration t + 1 starts, a new set of observed weights w t+1 ∈ R |E| + is available and the decision maker observes a loss

l t = e∈pt w t (e) (1)
associated with p t . Our goal is to design a stochastic algorithm in order to perform iterative routing optimisation based on online sequentially updated information w t about the network state.

One possible way to address this stochastic optimisation problem is to consider each path in P u,v as an expert and compare the loss of all experts in the pool in order to select the best among them. Unfortunately, the cardinality of P u,v might be exponential and the resulting optimisation problem might end up being computationally intractable.

Another, much more efficient option is to take the online convex optimisation approach of [START_REF] Hazan | Introduction to online convex optimization[END_REF].

2) The online Frank-Wolfe algorithm: As is well known in combinatorial optimisation, the standard shortest path problem with edge weights w e , e ∈ E, can be recast as a linear programming problem consisting in solving

min x∈E |E| w * x (2)
subject to 1 x ∈ P u,v . The main idea is based on the fact that the P u,v has the following convex hull:

c∈E x u,c = 1 (3) c∈E x c,v = 1 (4) ∀c ∈ V \ {u, v}, c :(c ,c)∈E x c ,c = c :(c,c )∈E x c,c (5)
∀e ∈ E, x e ∈ [0, 1]. (6)
In our time varying random setting, we receive at each time t a new value w t ∈ R |E| of the vector of weights and our goal is to achieve the minimal regret over a given time horizon {1, . . . , T }, for a given T ∈ N * . The Online Conditional Gradient, aka Online Frank-Wolfe algorithm is a very efficient approach for doing this. The method is described in Algorithm 1 below.

Result: The path encoded in x T x 1 is a shortest path from u to v, computed e.g. from averaged historical data; for t = 1 to T do y t+1 ← shortest path with edge cost vector

η t τ =1 w τ + 2(x t -x 1 ) (7)
set x t+1 = γ t x t + (1 -γ t ) y t+1 ; end Algorithm 1: The Online Frank-Wolfe Algorithm [START_REF] Hazan | Introduction to online convex optimization[END_REF]Section 7.5] The following result characterises the performance and adaptivity of this online method.

Theorem 1 [11, Theorem 7.2] Let D be the diameter of conv(P u,v ) and assume that w t 2 ≤ G for all t ∈ {1, . . . , T }. The Online Frank-Wolfe Algorithm 1 with parameters η = G/(DT 3/4 ) and

γ t = min{1, 2/t 1/2 } satisfies * t=1 w * t x t - min x∈conv(Pu,v) T t=1 w * t x ≤ 8DG T 3/4 . (8)
In other words, after dividing (8) by T , this theorem says that the average loss suffered by the sequence of shortest paths is of the same order as the best average loss, i.e. the one suffered by one optimal path.

B. Joint posterior distribution and confidence intervals

The next question to be addressed is the one of providing a confidence interval for the shortest path. One idea is to apply the approach proposed in [START_REF] Mandt | Stochastic gradient descent as approximate bayesian inference[END_REF] which consists in using the stochastic gradient algorithm for approximate Bayesian Inference.

In the case where, instead of the Online Frank-Wolfe algorithm, one uses the Iterate Averaging Stochastic Gradient method defined in Algorithm 2. For this algorithm to be Result: The last iterate x T x 1 is an arbitrary initial point;

for t = 1 to T do y t+1 = y t -η∇f t (x t ) set x t+1 = γ t x t + (1 -γ t ) y t+1 ; end Algorithm 2: The Iterate Averaging Stochastic Gradient Algorithm [13, Section6.1]
relevant, however, we need the function f to be strongly convex. Moreover, the vector ∇f t (x t ) will denote a centered stochastic perturbation of ∇f (x t ).

For the Iterate Averaging Stochastic Gradient Algorithm, one obtains the following guarantees.

Claim 1 [13, Based on Appendix G] Assume that L T (x) = 1 T T t=1 f t (x) (9)
is strongly convex. Take

γ t = t t + 1 . ( 10
)
Then, we have

E [x T x * T ] ≈ 1 ηT Σ(A -1 ) * + A -1 Σ ( 11
)
where A is the Hessian of L T at its minimiser.

The accuracy of ≈ in the latter claim depends on how well L T is approximated by 1 2 x t Ax on the domain where the trajectory (x t ) t=1,...,T will be wandering.

C. Our new approach

In our Online Frank-Wolfe setting, the problem is radically different from the Iterate Averaging Stochastic Gradient method, since the average cost L T = 1 T T t=1 w t , • is linear, and therefore not strongly convex. However, we can use the same type of result for the output x T generated by the Online Frank-Wolfe Algorithm with γ t = t/(t + 1) as in [START_REF] Aric | Exploring network structure, dynamics, and function using NetworkX[END_REF], and η = 1/T . Indeed, a similar diffusion-type approximation can be performed for the Online Frank Wolfe Algorithm as the one given in [START_REF] Mandt | Stochastic gradient descent as approximate bayesian inference[END_REF] for the Iterate Averaging Stochastic Gradient if we replace the Ornstein-Uhlenbeck process by one similar to [START_REF] Bubeck | Sampling from a log-concave distribution with projected langevin monte carlo[END_REF]. The theoretical details will be given in an extended version of the present work.

Result: The last iterate x T for l = 1 to L do Run Algorithm 1 with γ t = t/(t + 1) and η = 1/T and return x (l) T end Compute the variance

σ = 1 L L l=1 w (l) * T x (l) T 2 - 1 L L l=1 w (l) * T x (l) T 2 . (12)
Output the confidence interval

I α = 1 L L l=1 w (l) * T x (l) T -u 1-α/2 ; 1 L L l=1 w (l) * T x (l) T + u 1-α/2 (13)
Algorithm 3: The new sampling scheme

III. NUMERICAL SIMULATION

A. Simulation protocol

We have designed an ad hoc transport network using the Python language [START_REF] Rossum | Python reference manual[END_REF]. In this simulator, the number of crossroads has been set at various values, and each of them is linked to 2 to 5 other crossroads, according to a random draw. This design leads to a undirected graph, where nodes represent the crossroads, and edges are weighted according to the time needed between two nodes. Such weights are randomly picked in the real interval [0; 1] and updated at each time iterate, leading to a time varying random network. Such a dynamic graph has been implemented using the Networkx library [START_REF] Aric | Exploring network structure, dynamics, and function using NetworkX[END_REF].

Algorithm 1 has then been computed, with the following parameters. η has been set to:

η = G DT 3 2
, where G is equal to the square root of the number of edges, while D is the largest distance between two shortest paths. T , for its part, is the number of steps of the algorithm, which has been set at 100. Finally, we have considered that:

γ t = t t + 1 .
At initialization stage, w 0 , which is the vector of travel times (from size the number of edges) at the beginning of the simulation, which should in practice be equal to the averaged historical data, has been picked randomly. y 1 is the associated shortest path calculated, like all the other shortest paths, using the Dijkstra algorithm: the i-th component of y 1 is 1 if the i-th edge is in this shortest path, else it is equal to 0. Finally, x 1 has been set at y 1 .

B. Obtained results

We have applied the proposed algorithm to various random networks, with a number of nodes respectively equal to N = 12, 100, 200, and 500. The evolution of the shortest Finally, we have verified that the global computation cost of our approach is similar to the Djikstra algorithm (complexity of O(nlog(n)), as can be seen in Figure 3. This result is encouraging, as we take place in a more difficult context of the shortest path problem, namely when the transport network evolves dynamically.

IV. CONCLUSION

In this article, we proposed an online approach for the stochastic shortest path problem, which computes a confidence interval together with a shortest path. The approach is based on an appropriate rescalling of the Iterate Averaging Stochastic Gradient. Our main algorithm is a combination of the results of [START_REF] Hazan | Introduction to online convex optimization[END_REF] and of [START_REF] Mandt | Stochastic gradient descent as approximate bayesian inference[END_REF], leading to an efficient way to simulate the distribution at time T of the shortest path in a stochastic and potentially non-stationary (but smoothly evolving) environment. This algorithm has been implemented using the Networkx library of the Python language, and obtained results have been discussed.

In future work, the authors intention is to apply this online Other directions of research encompass the use of new probability laws for edges, the introduction of correlations between two edges (or between two successive iterations in one given edge), and the variability in the number of nodes.

Fig. 1 :

 1 Fig. 1: The algorithm working on a small dynamic network (reaching 11 from 0)

Fig. 2 :Fig. 3 :

 23 Fig. 2: Convergence aspects of the proposal

here we make a slight abuse of notation by interpreting Pu,v as a set of binary vectors which are indicators of a path from u to v, i.e. setting every component of x to 1 when index by an edge on the path

ACKNOWLEDGMENT C.G. acknowledges the financial support of the EU (Feder) and the Swiss Confederation within the framework of the Interreg France-Switzerland programme. S.C. benefited from funding from the INNOVATE UK CAPITALS project http://gtr.rcuk.ac.uk/projects?ref=102618.


Jérôme Salvi

Kien Phan Huy

Jean-Charles Beugnot

Plasmonic nanofibers for the enhanced of Brillouin scattering

Introduction

The rich and complex dynamics of light and sound interactions in tiny optical waveguides such as photonic nanofibers and microstructured optical fibers has recently gained high interest. For instance, photonic nanofibers are hair-like glass wire, manufactured by tapering optical fibers down to submicron diameters [1]. In addition to providing strong light confinement and, hence, enhanced nonlinear optical effects, photonic nanowires also exhibit a large evanescent field. They thus have a number of optical and mechanical properties that make them very attractive for both fundamental physics and technological applications not currently possible with comparatively bulky optical fibers [2]. To date, Brillouin scattering in these tiny waveguides has yet to be explored. Brillouin scattering between sound and light waves has been extensively investigated in optical fibers. It is well-known that tapered optical fiber support many transverse, longitudinal and surface acoustic waves over a broad frequency range from 50 MHz to 11 GHz. We propose to functionalized surface of nanofiber with a gold or silver coating for infrared applications and enhanced nonlinear phenomena as represented in figure 1. Circulating cylindrical coating with metallic layer is perfectly adapted to generate surface plasmon at telecom wavelengths and is suitable for filters, polarizers, and sensors applications [3][4][5][6]. In particular, reference [7] showed that the Brillouin signals could be enhanced by orders of magnitude when surface plasmon fields are involved. The main idea of our paper is to enhance Brillouin light scattering from surface acoustic waves in a subwavelength-diameter optical fibre [8] coated with a thin metal film in order to take advantage of the surface plasmon modes existing in these kind of cylindrical structures [9]. In this context, we design tellurite nanofiber coated with 10 to 40 nm thick gold layers. We numerically demonstrated that the nanofibers with 2.5 µm diameter support two surface modes of azimuthal order 0 and 1 at a wavelength of 1550nm. The optical power distribution of optical mode with an effective index of 2.134+i5.26e-3 is represented in Fig. 2 (d). For calculation, the refractive index of tellurite glasses and gold layer are 2.119 and 0.4649+i.10.56, respectively. For comparison, the optical power distribution of optical mode in tellurite fibre (without coating) is represented in Fig 2(a). These surface plasmonic modes in a cylindrical geometry confine the energy at the surface of the nanofiber and the main idea is then to allow Brillouin scattering enhancement from surface acoustic waves. In tiny optical waveguides, several families of acoustic modes can be exalted by Brillouin scattering. We have experimentally demonstrated the generation of surface acoustic waves propagating at the surface of the nanofibers [8]. We performed numerical calculations of Brillouin interaction by solving the elastodynamic equation subject to an electrostrictive force [8]. As a first approximation, the photoelastic coefficient in gold is neglected [10][11].

As we can see on figure 2(b,e), the amplitude of longitudinal displacement is 5 times larger in plasmonic configuration.

Conclusions

In tellurite rod coating with a gold thin film, surface acoustic wave involved in Brillouin scattering can be enhanced by plasmonic effect at telecommunications wavelength.

Figure 1 :

 1 Figure 1: Schematic of the Brillouin backscattering interaction within a tellurite tapered optical fiber coated with gold thin film.

Figure 2 :

 2 Figure 2: Numerical calculation of Brillouin backscattering interaction in 2.5µm diameter tellurite nanofibers with a gold layer of 40nm (d-f) and without metal coating (a-c). The incident optical wavelength is 1550nm. The deformation and sound density are calculated for an incident optical power of 1 W.