Rodrigue Imad

Charly Poulliat

Sebastien Houcke

Benjamin Gadat

BLIND FRAME SYNCHRONIZATION OF REED-SOLOMON CODES: NON-BINARY VS. BINARY APPROACH

We consider in this paper the problem of blind frame synchronization of systems using Reed-Solomon (RS) codes and other related families. We present first of all three techniques of blind frame synchronization based on the non-binary parity check matrix of RS codes. While the first two techniques involve the calculation of hard and soft values of the syndrome elements respectively, the third one perform an adaptation step of the parity check matrix before applying the soft criterion. Although RS codes are constructed from non-binary symbols, we show in this paper that it is also possible to synchronize them using the binary image expansion of their parity check matrix. Simulation results show that the synchronization algorithm based on the adaptation of the binary parity check matrix of RS codes has the best synchronization performance among all other techniques. Furthermore, the Frame Error Rate (FER) curves obtained after synchronization and decoding are very close to the perfect synchronization curves.

INTRODUCTION

Reed-Solomon (RS) codes became one of the most used codes because of their great correcting power and their utility in several applications. Many algorithms can be applied to decode RS codes. Although the Hard Decision Directed (HDD) decoder is used in most applications, its performance presents a significant degradation compared to soft decision decoding algorithms. The Adaptive Belief Propagation (ABP) algorithm was proposed in [START_REF] Jiang | Iterative soft-input-softoutput decoding of reed-solomon codes by adapting the parity check matrix[END_REF] by Jiang and Narayanan. This algorithm involves, at each iteration of the iterative procedure, the adaptation of the parity check matrix of the code to the reliability of the information bits. In [START_REF] Jego | Turbo decoding of product codes based on the modified adaptive belief propagation algorithm[END_REF], the authors proposed to achieve the adaptation procedure of the parity check matrix before applying the Belief Propagation (BP) algorithm, leading to the so-called modified-Adaptive Belief Propagation (m-ABP) algorithm. Although decoding algorithms of RS codes have shown the ability of such codes to correct heavily corrupted sequences, a This work has been supported by the French research agency under grant ANR-08-VERS-002 (CAIMAN project). great degradation in decoding performance is expected when the receiver does not know the beginning of a codeword. For this reason, frame synchronization should be applied before the decoder. Conventional frame synchronization techniques involve the transmission of a training sequence known by the receiver [START_REF] Barker | Group synchronization of binary digital systems[END_REF][START_REF] Massey | Optimum frame synchronization[END_REF][START_REF] Lui | Frame synchronization for gaussian channels[END_REF]. The major drawback of such techniques is in reducing the spectral efficiency of the transmission especially when codes of small sizes are used in the system. Other works propose to take advantage of the code structure and consider frame synchronization jointly with the decoding as in [START_REF] Robertson | A generalized frame synchronizer[END_REF][START_REF] Cassaro | Frame synchronization for coded systems over AWGN channels[END_REF]. In [START_REF] Howlader | Decoderassisted frame synchronization for packet transmission[END_REF], the authors propose to encode synchronization bits as part of the data sequence. In our work, we are interested in developing blind methods of frame synchronization wherein no additional sequence is added to the coded one. In [START_REF] Houcke | Blind frame synchronization for block code[END_REF], the authors proposed a new method of blind frame synchronization of block codes, based on the calculation of hard decisions of the syndrome elements. We refer to this technique by the Hard Syndrome (HS) based synchronization. The Soft Syndrome (SS) based synchronization algorithm was proposed in [START_REF] Imad | Blind frame synchronization for error correcting codes having a sparse parity check matrix[END_REF]. This algorithm outperforms the HS and another technique of blind frame synchronization presented in [START_REF] Sun | Optimum frame synchronization for preamble-less packet transmission of turbo codes[END_REF]. Although these synchronization methods are well adapted to codes having a sparse parity check matrix such as Low-Density Parity-Check (LDPC) codes, their performance degrades when the number of non zero elements in the parity check matrix of the code increases. Inspired by the m-ABP decoder, a modified version of the SS synchronization algorithm was proposed in [START_REF] Imad | Blind frame synchronization of product codes based on the adaptation of the parity check matrix[END_REF]. Applying this algorithm to Bose-Chaudhuri-Hocquenghem (BCH) product codes yields very good results. In this paper, we propose and compare several frame synchronization techniques adapted to RS codes. These blind techniques are based on the non-binary and binary parity check matrices. The remaining of this paper is organized as follows. In Section 2 we give the non-binary representation of RS codes and present three non-binary techniques of blind frame synchronization. We show in Section 3 that it is also possible to synchronize RS codes using the binary image expansion of their parity check matrix. Simulation results are presented in Section 4 and a conclusion to this work is drawn in Section 5.

BLIND FRAME SYNCHRONIZATION OF RS CODES BASED ON A NON-BINARY APPROACH

We consider in this study that the system is using a Binary Phase Shift Keying (BPSK) mapping and that the propagation channel is corrupted by an additive white Gaussian noise of variance σ 2 w = N 0 /2. At the reception, the k th received sample is written as:

r(k) = c(k -t 0 ) + w(k), (1)
where c(k) is the k th symbol to be transmitted, w(k) is the white Gaussian noise and t 0 is an integer representing the shift of the transmitted symbols. The goal of frame synchronization is to estimate t 0 . Synchronization techniques that we present in this paper to synchronize RS codes are inspired by the ones proposed in [START_REF] Imad | Blind frame synchronization for error correcting codes having a sparse parity check matrix[END_REF][START_REF] Imad | Blind frame synchronization of product codes based on the adaptation of the parity check matrix[END_REF]. These techniques are based on a Maximum A Posteriori (MAP) approach in the sense of maximizing the probability that a position t corresponds to the correct synchronization moment, given the received samples. In other words, it maximizes the a posteriori probability P r[t|r], where t is a possible value of the correct synchronization position and r is the received sequence of samples. Maximizing this probability is done using a sliding synchronization window on the received sequence. The size of the synchronization window can be a multiple of the size of a codeword.

In order to confirm that a position t is the correct synchronization position, we should verify that the block transmitted at this position corresponds to a valid codeword and that all other blocks in the remaining tested positions are not. The easiest way to check whether a block corresponds to a valid codeword or not is by calculating its syndrome which is obtained according to the parity check matrix of the code.

Non-binary representation of Reed-Solomon codes

A Reed-Solomon RS(N, K) code is a non-binary cyclic code of length N symbols constructed from K data symbols. Each symbol is defined in the Galois Field GF (2 m ) and can be represented by binary m-tuples, where m is an integer greater than 2. The generator polynomial of RS codes is written as:

g(x) = (x + α)(x + α 2 )...(x + α 2t ), (2)
where α is a primitive element in GF (2 m ) and t = (N -K)/2 is the symbol-error correcting capacity of the code. The non-binary parity check matrix of the RS(N, K) code has a size ((N -K) × N ) symbols and can be written as [START_REF] Jiang | Iterative soft-input-softoutput decoding of reed-solomon codes by adapting the parity check matrix[END_REF]:

H =       1 α α 2 • • • α (N -1) 1 α 2 α 4 • • • α 2(N -1) . . . . . . . . . 1 α N -K α (N -K)2 . . . α (N -K)(N -1)       (3)
We propose next three techniques of blind frame synchronization designed for non-binary codes, in particular for RS codes.

Non Binary Hard Syndrome based synchronization

We denote by h ij the element at row i and column j of the non-binary parity check matrix of the RS code. From hard decisions on received samples, we define the k th syndrome element as:

S(k) = N l=1 h kl ȳ(l), (4)
where ȳ(l) are hard decisions on symbols in GF (2 m ). In a noise free channel, if a received block is a valid codeword then the (N -K) syndrome elements are all equal to zero. When the synchronization position t 0 is unknown, a block could contain arbitrary samples that do not form a codeword and therefore, some syndrome elements are not equal to zero.

Inspired by this idea, the Non Binary Hard Syndrome (NBHS) based synchronization algorithm that we propose in this section estimates the synchronization position by: tNBHS = argmin t=0,...,mN -1

M (N -K) k=1 s t (k) , (5)
where

s t (k) = 0 if S t (k) = 0 1 if S t (k) = 0 (6)
and S t (k) is the non-binary syndrome calculated at position t of the sliding synchronization window. The variable M represents the number of blocks (of size mN samples each) contained in the sliding window. Synchronization performance is improved when M increases.

Non Binary Soft Syndrome based synchronization

Calculating hard values of syndrome elements involves a loss of information. Inspired by the algorithm of [START_REF] Imad | Blind frame synchronization for error correcting codes having a sparse parity check matrix[END_REF], we present in section the Non Binary Soft Syndrome (NBSS) based synchronization algorithm. Indeed, we can show that the synchronization criterion of [START_REF] Imad | Blind frame synchronization for error correcting codes having a sparse parity check matrix[END_REF] in its original form (before applying approximations proposed by the authors) is valid for any field order. Hence, the optimal estimate of the frame synchronization position can be derived as:

tNBSS = argmax t=0,...,mN -1 M (N -K) k=1 log P r[S t (k) = 0] . (7)
In the non-binary case, the probability that a syndrome element is equal to zero can be calculated after half iteration of the non-binary BP decoder, which can be efficiently implemented in the Fourier domain. Details on the non-binary BP algorithm are omitted due to lack of space but further information on Fast Fourier Transform (FFT) based BP and related low complexity algorithms can be found in [START_REF] Declercq | Decoding algorithms for nonbinary LDPC codes over GF(q)[END_REF].

Adaptive Non Binary Soft Syndrome based synchronization

Synchronization algorithms proposed in Sections 2.2 and 2.3 are well adapted for codes having a sparse non-binary parity check matrix. However, [START_REF] Barker | Group synchronization of binary digital systems[END_REF] shows that the parity check matrix of RS codes does not contain any element that is equal to zero. Inspired by [START_REF] Jiang | Iterative soft-input-softoutput decoding of reed-solomon codes by adapting the parity check matrix[END_REF], we propose in this section to perform, at each position of the sliding window, an adaptation of the non-binary parity check matrix of the code, to the reliability of the non-binary symbols. Many methods can be applied to compute the reliabilities of symbols defined over GF (2 m ) [START_REF] Jiang | Iterative soft-input-softoutput decoding of reed-solomon codes by adapting the parity check matrix[END_REF]. In this paper, we define the reliability of a non-binary symbol y(k) as:

Rel(y(k)) = min i=1,...,m Rel(r i (k)) = min i=1,...,m |r i (k)|, ( 8
)
where r i (k) is the i th sample constituting the non-binary symbol y(k). Once reliabilities are computed and sorted by ascending order, the first (N -K) columns of the non-binary parity check matrix, corresponding to the (N -K) least reliable symbols, are reduced to obtain a diagonal squared matrix. This can be done by applying a Gaussian elimination method on GF (2 m ) or a more computationally efficient method as described in [START_REF] Jiang | Iterative soft-input-softoutput decoding of reed-solomon codes by adapting the parity check matrix[END_REF]. The aim of this procedure is to reduce the number of nonzero elements in the part of the parity check matrix that is associated to the least reliable samples. Once adaptation operations are done, the Adaptive Non Binary Soft Syndrome (ANBSS) based synchronization performs the same steps as the ones done by the NBSS algorithm and estimates the frame synchronization position using [START_REF] Cassaro | Frame synchronization for coded systems over AWGN channels[END_REF].

BLIND FRAME SYNCHRONIZATION OF RS CODES BASED ON A BINARY APPROACH

Although RS codes are non-binary codes, we propose in this section to synchronize them using the binary image expansion of their parity check matrix. For the non-binary matrix H of (3), we can find an equivalent binary parity check matrix H b of size (m(N -K) × mN ). This matrix is obtained by replacing α in matrix H by the transpose of the binary companion matrix A of size m × m. Indeed, if

p(x) = a 0 + a 1 x + • • • + x m (9)
is a primitive polynomial having its coefficients in GF (2), then the companion matrix of p(x) is the m × m matrix defined by:

A =     0 1 0 • • • 0 0 0 1 • • • 0 0 0 0 • • • 1 a 0 a 1 a 2 • • • a m-1     (10)
Although the binary parity check matrix of RS codes contains some zeros, the number of ones in it is still large. Therefore, the synchronization technique of [START_REF] Imad | Blind frame synchronization for error correcting codes having a sparse parity check matrix[END_REF] is not adapted to RS codes. We propose in this section to apply the synchronization technique proposed in [START_REF] Imad | Blind frame synchronization of product codes based on the adaptation of the parity check matrix[END_REF] for synchronizing BCH codes, to synchronize RS codes using the binary image expansion of their parity check matrix. The main idea is to slide the synchronization window on mN consecutive positions knowing that, one of these positions corresponds to the correct frame synchronization. At each position of this window and for each block of size mN contained in the sliding window, we rearrange its samples according to their reliabilities (i.e their absolute values). Then, using a Gaussian elimination on GF (2), we rearrange the binary parity check matrix of the RS code. The first m(N -K) columns of the binary parity check matrix, corresponding to the m(N -K) least reliable samples, are thus reduced to obtain an identity squared matrix. Once the rearrangement procedure is achieved, the Adaptive Binary Soft Syndrome (ABSS) based synchronization algorithm estimates the frame synchronization position by: tABSS = argmin t=0,...,mN -1

{ψ(t)}, (11)
where

ψ(t) = M m(N -K) k=1 log 1 + exp L S t (k) . (12)
L(S t (k)) = log Pr[St(k)=1] P r[St(k)=0]
is the Log-Likelihood Ratio (LLR) of the k th syndrome element and it can be easily computed after half iteration of the binary BP decoder [START_REF] Kschischang | Factor graphs and the sum product algorithm[END_REF][START_REF] Imad | Blind frame synchronization for error correcting codes having a sparse parity check matrix[END_REF]. Note that [START_REF] Sun | Optimum frame synchronization for preamble-less packet transmission of turbo codes[END_REF] is strictly equivalent to [START_REF] Cassaro | Frame synchronization for coded systems over AWGN channels[END_REF] if the latter was applied in the binary domain.

SIMULATION RESULTS

We present in this section simulation results obtained after applying the proposed synchronization techniques to RS codes. Monte Carlo simulations were done where, for each configuration, the noise, information bits and the delay of the channel were randomly chosen. RS codes being cyclic codes and in order to keep good synchronization performance, a pseudorandom interleaver should be used to permute the transmitted symbols [START_REF] Imad | Blind frame synchronization of product codes based on the adaptation of the parity check matrix[END_REF]. Fig. 1 shows curves of the probability of false synchronization versus the signal-to-noise ratio (E b /N 0 ) once synchronization techniques were applied to RS(7, 5) code. A sliding window of size M = 5 blocks was considered. From Fig. 1, it is shown that performance of the NBHS (NBSS respectively) is better than the HS (SS respectively), especially for high E b /N 0 . On the other hand, it is clearly seen that the ABSS algorithm is the most effective among all other synchronization techniques. The ANBSS and ABSS were also applied to the RS(31, 25) code. Simulation results are shown in Fig. 2. We also plotted in this figure curves obtained by the algorithm proposed by Massey in [START_REF] Massey | Optimum frame synchronization[END_REF], which locates a synchronization word periodically embedded in the data. Even for a synchronization word having a size that corresponds to 7.1% of the total size of the RS(31, 25) code, the ABSS and ANBSS algorithms converge quicker than [START_REF] Massey | Optimum frame synchronization[END_REF]. Due to the small size of RS codes (RS(31, 25) has a size of 155 bits), it is clear that a synchronization window of size M = 1 block does not afford good synchronization performance. Increasing the size of the synchronization window yields better results. Once again, the ABSS outperforms the ANBSS. A gap of around 1 dB exists between the two curves. However, notice that the non-binary adaptation performed by the ANBSS algorithm can be parallelized and thus, it is less complex to implement than the binary adaptation procedure [START_REF] Jiang | Iterative soft-input-softoutput decoding of reed-solomon codes by adapting the parity check matrix[END_REF]. In the remaining of this paper and for complexity reasons, the criterion of [START_REF] Imad | Blind frame synchronization of product codes based on the adaptation of the parity check matrix[END_REF] in the SS and the ABSS algorithms is replaced by the approximation given in [START_REF] Imad | Blind frame synchronization for error correcting codes having a sparse parity check matrix[END_REF]. In order to verify the adequacy of the ABSS to synchronize RS codes, we plotted in Fig. 3 the Frame Error Rate (FER) curves obtained after synchronization and decoding of the RS(31, 25). The decoder used is the ABP proposed in [START_REF] Jiang | Iterative soft-input-softoutput decoding of reed-solomon codes by adapting the parity check matrix[END_REF]. For a synchronization window of size M = 5 blocks, it is clearly seen that the FER curve obtained after synchronization and decoding is very close to the perfect synchronization case. For small E b /N 0 , a gap of less than 0.4 db exists between the two curves. These curves become almost one for an E b /N 0 greater than 4 dB.

Let us now apply the ABSS synchronization technique to RS product codes. A product code C(N 1 N 2 , K 1 K 2 ) is a bidimensional code constructed from two elementary sys-tematic block codes C 1 (N 1 , K 1 ) and C 2 (N 2 , K 2 ). Hence, rows and columns of code C are codewords of C 1 and C 2 , respectively. We propose now to take advantage of the bidimensional structure of RS product codes and apply the ABSS on their elementary binary parity check matrices. Therefore, the synchronization criterion calculated in ( 12) is computed now twice: once on the rows of the RS product code, we get ψ r (t), and the other time on its columns , we get ψ c (t). The frame synchronization position is now estimated by:

t = argmin t=0,...,mN -1 {ψ r (t) + ψ c (t)}. (13)
We consider now the RS(7, 5) 2 product code. This notation means that this product code is constructed by two elementary RS(7, 5) codes. In order to verify the effectiveness of the proposed technique on synchronizing RS product codes, we plotted in Fig. 4 the FER curves obtained after synchronization and decoding. The decoder used to decode these codes is the m-ABP decoder presented in [START_REF] Jego | Turbo decoding of product codes based on the modified adaptive belief propagation algorithm[END_REF], which has a performance that is equivalent (and sometimes better) than the Chase-Pyndiah decoder. In Fig. 4 we can see that applying the SS algorithm to synchronize the RS(7, 5) 2 product code does not yield good results. For a synchronization window of size M = 1 block and at a FER equal to 10 -2 , a gap of around 1 dB is observed between the SS and the perfect synchronization case. This gap in FER disappears when we apply the ABSS algorithm. Hence, the ABSS is also well adapted to RS product codes.

CONCLUSION

We have presented in this paper original techniques for blind frame synchronization of RS codes based on their binary and non-binary parity check matrices. Simulation results have shown that the adaptive binary approach (ABSS) outperforms the non-binary one (ANBSS). Furthermore, the FER curves obtained after synchronization and decoding have proven that the ABSS technique is well adapted to RS codes. This technique was also applied to RS product codes and the results were very satisfactory. Despite the fact that the ABSS algorithm outperforms the ANBSS, the adaptation procedure used by the latter can be parallelized, which is very beneficial for hardware implementation. A perspective of this work may be to use the non-binary matrix for the adaptation (first part of the ANBSS) then compute its binary image expansion followed by half iteration of the binary BP algorithm (second part of the ABSS). Doing this may lead to reduce the complexity and calculation time of the proposed synchronization algorithm.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Probability of false synchronization of different synchronization techniques when applied to RS(7, 5) code.

Fig. 3 .

 3 Fig. 3. Frame Error Rate (FER) curves after synchronization and decoding of the RS(31, 25).

Fig. 4 .

 4 Fig. 4. Frame Error Rate (FER) curves after synchronization and decoding of the RS(7, 5) 2 product code.


Alain Petrowski
email: alain.petrowski@telecom-sudparis.eu

Farouk Aissanou
email: farouk.aissanou@telecom-sudparis.eu

Ilham Benyahia
email: ilham.benyahia@uqo.ca

Sébastien Houcke
email: sebastien.houcke@telecom-bretagne.eu

Multicriteria Reinforcement Learning Based on a Russian Doll Method for Network Routing

The routing in communication networks is typically a multicriteria decision making (MCDM) problem. However, setting the parameters of most used MCDM methods to fit the preferences of a decision maker is often a difficult task. A Russian doll method able to choose the best multicriteria solution according to a context defined beforehand is proposed. This context is given by a set of nested boxes in the criteria space, the shapes of which can be established from objective facts such as technical standards, technical specifications, etc. This kind of method is well suited for self-adaptive systems because it is designed to be able to give pertinent results without interaction with a decision maker, whatever the Pareto front.

The Russian doll multicriteria decision method is used with a reinforcement learning to optimize the routing in a mobile ad-hoc network. The results on a case study show that the routing can be finely controlled because of the possibility to include as much parameters as desired to adjust the search of the best solution on Pareto fronts a priori unknown. These results are clearly better than those obtained with the optimization of a weighted sum or the minimization of a Chebyshev distance to a reference point.

I. INTRODUCTION

A. Background on Routing Protocols for Mobile Ad-Hoc Networks

Mobile ad hoc networks (MANETs) are self adaptive telecommunication networks formed by several wireless nodes that attempt to build an efficient topology in order to communicate. The aim of the routing task is to find a path between a source node and a destination node. As the transmission range of the nodes is limited, the path often uses successive forwarding nodes called hops. The routing should optimize Quality of Service (QoS) parameters like hop count, delay or bitrates. In addition, the mobility of nodes causes frequent changes of the network topology, thus the routing mechanism must be able to modify paths in order to adapt to changes. Many works have been published on the field of routing in MANET [START_REF] Abolhasan | A review of routing protocols for mobile ad hoc networks[END_REF].

The most often, the protocols described in [START_REF] Abolhasan | A review of routing protocols for mobile ad hoc networks[END_REF] deal with a single performance parameter namely hop count. Nevertheless, many applications like video and voice require different performance parameters; therefore a new range of protocols is needed.

Recently, some protocols based on reinforcement learning methods [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] have emerged in order to deal with QoS opti-mization in MANET. These protocols are either based on Qlearning [START_REF] Watkins | [END_REF] like LQ-Routing [START_REF] Tao | LQ-Routing Protocol for Mobile Ad-Hoc Networks[END_REF], or on "Ant Colony Optimization", which is a special case of reinforcement learning [START_REF] Caro | Anthocnet: An adaptive nature-inspired algorithm for routing in mobile ad hoc networks[END_REF].

B. Routing as a Multi-criteria decision problem

The performance based routing problem is typically a multicriteria decision making problem (MCDM). It should be solved in such a way that several QoS criteria are taken into account simultaneously. However, these criteria are often contradictory. Moreover, the importance given to the different criteria depends on the requirements of the applications using the network. For example, a telephony application could accept quite high error rates, but the maximum transmission delay should be of the order of 0.1 second. On the contrary, a file transfer application will be efficient if the error rate is low, while the delay could be quite high, of the order of several seconds.

C. Related works

Especially for wireless networks, the task of selecting among many candidates the multicriteria solution fitting at best the preferences of a decision maker is discussed in many research works. Common approaches use parametric preference functions where the parameters, designated as "weights", have to be adjusted to express the relative importance given to each criterion. Often these approaches transform the MCDM problem into a single-objective optimization problem. However, it is difficult to determinate good values for the weights according to the preferences of the decision maker, especially when criteria are incommensurable. Thus, in [START_REF] Egoh | A Multi-Criteria Receiver-Side Relay Election Approach in Wireless Ad Hoc Networks[END_REF], the authors minimize a weighted sum in order to optimize the delay and the distance from a source node to a destination node, to deal with the issue of greedy-forwarding mechanism in ad hoc networks. The values of the two weights are fixed using multiple simulation scenarios. In [START_REF] Guerriero | A biobjective optimization model for routing in mobile ad hoc networks[END_REF] the authors formulate the routing task in a mobile ad hoc network as a MCDM problem that they solve by the weighted sum method. However, no idea is suggested for the setting of the weight values. The authors study the sensitivity of the optimization process results according to these weights. They claim that a good estimation of the weight values is very important to obtain a good efficiency and depend only on the application classes. In [START_REF] Setmaa-Krkkinen | Best compromise solution for a new multiobjective scheduling problem[END_REF], the authors consider the network selection problem as a MCDM problem. The aim is to optimize two contradictory objectives namely cost (price) and transmission time when a set of components (data, video, voice, etc.) is transmitted through different network connections. The problem is solved by minimizing the weighted Chebyshev distance between the solution and a reference point. Again, the authors state that the weight values have to be chosen by the user himself. However they argue that the proposed method is not very sensitive to them thanks to their choice of a specific reference point.

In [START_REF] Roy | QM2RP: a QoS-based mobile multicast routing protocol using multi-objective genetic algorithm[END_REF], the authors solve the problem of multicast routing with a multi objective genetic algorithm (MOGA) [START_REF]Multi-Objective Optimization using Evolutionary Algorithms[END_REF], which tries to approximate the set of non-dominated solutions. The aim is to construct a multicast tree that optimizes several objectives like delay and bandwidth. The choice of the best solution among the set of non-dominated solutions is performed by a decision maker according to the requirement of the application. [START_REF] Ishibuchi | Incorporation of decision maker's preference into evolutionary multiobjective optimization algorithms[END_REF] use a reference solution given by the decision maker to guide the search process of the best multicriteria solutions during the selection step of a MOGA. But, an adequate choice of the reference point is strongly dependent on the optima locations, which are a priori unknown.

D. Multicriteria routing for autonomous networks

Our work is in the line of autonomic networks [START_REF]Cognitive Networks: Towards Self-Aware Networks[END_REF], which have a self-adaptive capacity. Such networks should be able to learn from their environment, to configure themselves and they should take intelligent decisions without external help. In this context, it is unacceptable that human decision makers help the network to choose best multicriteria routing decisions.

However, the standard MCDM approaches based on parametric preference functions need an a priori knowledge of the location of optima to give pertinent results. But, this knowledge is a priori not available. When results are disappointing, interactions with a decision maker are required for choosing new parameters. For this reason, we think that standard MCDM approaches are quite adequate for human machine interactions, but not for autonomous systems. In the frame of self-adaptive machines, a more suitable way could be to consider multicriteria decision problems in terms of homeostasis. With this point of view, the importance of criteria changes according to their value in order to regulate them.

Section II presents a Russian doll method to implement multicriteria decision making. Section III shows how the Russian doll method is used by a reinforcement learning method able to optimize routing in a mobile ad-hoc network. Section IV describes a case study involving an ad-hoc network of boats. Results of experiments are then given and discussed.

II. A MULTICRITERIA DECISION MAKING METHOD FOR

AUTONOMOUS SYSTEMS

A. Pareto dominance

The criteria are represented by vectors defined in a criteria space C ⊂ R m , for which each coordinate should be mini-mized. A vector of criteria F(x) is associated with each vector x in search space Ω ⊂ R n .

The Pareto dominance is defined as follows: Let a = (a 1 , ..., a m ) and b

= (b 1 , ..., b m ) be criteria vectors, a domi- nates b if and only if ∀i ∈ [1, m], a i ≤ b i and ∃j ∈ [1, m] such that a j < b j Let F(x) = (f 1 (x), ..., f m (x))
be the objective functions of the multi-criteria optimization problem. The resolution of this problem consists in finding the Pareto optimal set of vectors X * such that each criteria vector z = F(x) with x ∈ X * is non dominated. The Pareto front F is defined as the set

F = {F(x), ∀x ∈ X * }.
Multi-criteria decision consists in choosing a Pareto optimal point that is recognized as the best choice by a decision maker.

B. Decision making by autonomous systems

We propose in this paper a MCDM approach suitable for autonomous systems where the parameters of the multicriteria decision are directly deduced from the requirements we want to reach. Typically, this kind of information could come from technical standards, technical specifications of system components or experiments.

For example, for a high quality Voice over IP (VoIP) application, the delay d should be lower than 0.1 s and the bit error rate BER should be lower than 10 -6 . The problem is finding routes maximizing the QoS. Table I gives as an example a series of thresholds associated to different levels of quality.

Unacceptable ≥ 0.5 ≥ 10 -4
Figure 1 can be used to illustrate an example of Pareto front in the criteria space generated by the BER (in abscissa) and the delay. Please note that this figure is only given to support explanations and does not come from experiments. Box 0 is defined as the whole criteria domain. According to Table I, box 2 contains high quality VoIP communications criteria vectors while vectors of box 1 that are not in box 2 are associated to degraded communications. Criteria vectors of box 0 but not in box 1 are in the "unacceptable" domain.

Figure 1 shows that box 2 does not contain any solution of Pareto front F. So there are only "degraded quality" solutions at best for this Pareto front. The best solution chosen is the closest to box 2 (high quality domain box) according to a distance to define. This example has given an idea about the working of the proposed MCDM algorithm. It is described in details in the following.

C. Russian doll decision making method

Without loss of generality, we consider the case of a minimization problem for all the criteria. A box is defined by the Cartesian product of m intervals

[l i , u i ] with i ∈ [1, m]. A set of k + 1 boxes B j = [l i0 , u ij ]
indexed from 0 to k must be defined in the criteria space in such a way that any box, except box 0, is nested in another box like Russian dolls. Box 0 is the whole criteria domain. The parameters of a box are given by bounding values or threshold values for each criterion. The lower bounds l i0 of boxes are the lower bounds of the whole criteria domain.The required number of boxes and their shapes are specification-dependent. Many nested boxes allow the system designer to accurately control the choice of a solution on the Pareto front.

In the following, we need to define a distance between vectors and boxes. We propose to use the weighted Chebyshev distance d ∞ w to ensure that any point of the Pareto front could be reached [START_REF] Bowman | On the relationship of the Tchebycheff norm and the efficient frontier of multiple-criteria objectives[END_REF] by defining appropriate shapes for boxes. Let a and b be two vectors of R m .

d ∞ w (a, b) = max i∈[1,m] w i |a i -b i | with w i ≥ 0
Now, we define the normalized Chebyshev distance between a criteria vector x ∈ B j-1 and box B j as follows:

d ∞ (x) = max i∈[1,m] δ ij , with δ ij =      0 if x i ∈ [l ij , u ij ] 0 if u ij = u ij-1 x i -u ij u ij-1 -u ij otherwise
In this way, every point on the upper borders u ij-1 of a box B j-1 is at the same distance from the nested box

B j except if u ij = u ij-1 .
Let u and v be two criteria vectors to compare. B(u) and B(v) are defined as the smallest boxes containing vectors u and v respectively. Let d ∞ (u) be the Chebyshev distance between u and the largest box contained in B(u). If u is contained by the smallest box B k , d(u) is not defined.

• Let i(B) be the index of box B. If i(B(u)) > i(B(v)),
then u is said "better than" v.

• If B(u) = B(v) and i(B(u)) = k and d ∞ (u) < d ∞ (v), then u is said "better than" v. • If B(u) = B(v) and i(B(u)) = k and d ∞ (u) = d ∞ (v)
and u dominates v, then u is said "better than" v. • In the other cases, u and v are said "indifferent". By applying these simple rules, it is easy to show that the relation "is better than or indifferent to" is reflexive and transitive. However, this relation is not antisymmetric because of the "indifferent" rule and it is not symmetric because of the "better than" rules. Moreover, this relation is total: all couples of criteria vectors can be compared.

The Russian doll decision making method is implemented by comparing couples of criteria vectors with the comparison rules described above. The best criteria vector is the one that is the closest of the largest box that does not contain any criteria vector.

III. MULTI-CRITERIA REINFORCEMENT LEARNING FOR ROUTING IN AD-HOC NETWORKS

A. Choosing the best routes according to the returns of the environment

For each class of application (VoIP, FTP, video streaming, etc.), there is a specific routing policy fitting at best the requirements for each of them. The criteria evaluation for a packet is made when it reaches its destination. Let a, s, d and n respectively stand for "application class", "source node", "destination node" and "neighbor node". A router r has to choose a neighbor n* according to a and d such that the criteria vector evaluated on the destination node d satisfies at best the QoS requirements according to a. The criteria vectors are seen as realizations of a random vector C. It is assumed that each router r, keeps in memory expected criteria vector estimations Q(a, d, r, n) = Ê(C|a, d, r, n). Note that (a, d) are given by the packet transmitted by router r. Let n * be the best neighbor according to the QoS requirements for application class a. n * is chosen by router r by comparing the expected criteria vectors Q(a, d, r, n) for every neighbor n. These multicriteria comparisons are implemented by the Russian doll method.

B. Discovering routes by reinforcement learning

Reinforcement learning (RL) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] takes place in the computation of Q(a, d, s, n) only at the source node of a packet indexed by t according to the following expression:

Q t (a, d, s, n) = Q t-1 (a, d, s, n) +α(c t -Q t-1 (a, d, s, n)), if t > 0 Q 0 (a, d, s, n) = 0
otherwise where • criteria vector c t is evaluated for packet number t at its destination. It is seen as the return of the environment of router s ; • α is a constant step-size parameter: α ∈ [0, 1). Our RL approach has been designed to work well with the Interleave Division Multiple Access (IDMA) method [START_REF] Ping | On Interleave-Division Multiple-Access[END_REF] that allows several nodes to transmit data simultaneously. However, the number of simultaneous communications must be as small as possible. For this reason we have not used a protocol of the Q-routing family.

Reinforcement learning requires finding a good equilibrium between exploitation and exploration [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] in order to be able to converge as quickly as possible towards optimal or near optimal solutions. Exploitation consists in choosing the action, i.e. the neighbor of a node, with the best-expected return. However a learning process with too much exploitation, leads to sub-optimal solutions. Exploration is required to improve the quality of the best found solution. Exploration consists in choosing an action at random, i.e. choosing the neighbor of a node at random. However, too much exploration results in a waste of resources and low returns.

It is impossible to have an a priori estimation of the packet QoS involved in the exploration process. The exploration packets should then be used only for the computation of the Q t vectors. When an exploration packet is sent by source s towards destination d, router s chooses a neighbor randomly. The other routers of a path choose their best neighbor according to their Q t vectors.

IV. EXPERIMENTS

A. The case study

An access method allows several users to share the same medium, i.e. electromagnetic waves for wireless communications. The Interleaved Division Multiple Access (IDMA) method [START_REF] Ping | On Interleave-Division Multiple-Access[END_REF] is a new access method similar to CDMA: users can send the data simultaneously and in the same band. The separation of the different users is based on the attribution of different interleavers but the code remains the same. Recent studies [START_REF] Houcke | Blind Detection for block coded interleaved Division Multiple Access[END_REF] have shown that it is even possible to use the same interleaver for all the users provided that the communications are asynchronous. This property is well suitable for MANETs. However, the greater the number of simultaneous transmitting nodes in the neighborhood, the lesser the signal to noise ratio and the greater the error rate. That involves that the quality of links between nodes is not stable and changes quickly. It is a challenge for the conception of good routing policies.

The experiments aim to estimate the efficiency of the Russian doll multicriteria decision method. The case study involves 20 boats in a rectangular region 100 × 150 km 2 that transmit data towards a terrestrial station located at coordinates (0, 75km). All the boats use the IDMA method.

During communications, boats are considered as stationary because of their low speed compared to distance between them. However, the features of communication channels change quickly because of the variability of the signal to noise ratios.

B. Simulations

The integration of the physical layer on a standard network simulator involves a high software complexity. There is no current simulator able to offer this feature. To overcome this difficulty, we have decided to work with the combination of two simulators that we have developed: one dedicated for the physical layer and IDMA access method simulation and the other for the network layer in charge of the routing tasks. The source nodes are chosen at random. Node 0, which is the terrestrial station, is the only destination of data packets.

A time period is a set of 40 successive time slots. For every time slot, a random number of simultaneous messages from 1 to 5 are sent through the network. A half of the messages is used to train the routers. The other half is used to provide performance results.

In the frame of the presented experiments, Q t (a, d, r, n) is a vector (δ t , ε t ) composed of the expected delay δ t and expected error rate ε t at time period t. These values have to be minimized by choosing adequate neighbors n* for every router r and destination 0. Four application classes are defined for these experiments. Class 1 requires minimizing ε only. Class 2 requires the minimization of δ only. Class 3 requires simultaneous minimization of δ and ε if δ ≤ 3.5. If δ > 3.5, δ is minimized only. Class 4 requires simultaneous minimization of δ and ε if δ ≤ 4.5. If δ > 4.5, δ is minimized only. Two experiments are performed.

Experiment 1 uses standard MCDM methods. However, such methods are unable to meet the exact requirements for application classes 3 and 4. So, they are simplified by dropping the thresholds 3.5 and 4.5 for classes 3 and 4 respectively. We differentiate class 3 and 4 by using two MCDM methods with the same objectives in order to compare them with the Russian doll method. The MCDM method for class 3 minimizes the weighted Chebyshev distance d ∞ w (x, ρ) between solution x = (δ, ε) and the reference point ρ = (1, 0) with weight 0.1 for δ and weight 0.9 for ε:

d ∞ (x, ρ) = max (0.1(δ -1), 0.9ε)
The weights have been chosen as normalizing coefficients since no indication was given about the importance of criteria. The MCDM method for class 4 minimizes the weighted sum of δ and ε with the same weights as for class 3.

Experiment 2 uses the Russian doll method. Now, the specification of classes 3 and 4 can be fully implemented by an appropriate choice of shapes for the nested boxes. According to section II, box 0 is defined as the whole criteria domain defined by the extreme points (0, 0) and [START_REF] Egoh | A Multi-Criteria Receiver-Side Relay Election Approach in Wireless Ad Hoc Networks[END_REF][START_REF] Abolhasan | A review of routing protocols for mobile ad hoc networks[END_REF] where the first coordinate stands for δ and the second one stands for ε.

The nested boxes for the different application classes are represented in figure 2. The box upper bounds are given in table II.

In summary, box 1 implements the threshold 3.5 or 4.5 on

C. Results

Each simulation gives 4 sets of numbers d t (a), s t (a), δ t (a) and ε t (a) for each application class a, where t is the time period number: d t (a): average of measured delays over all packets sent during time period t for application class a.

s t (a): average of success rates, s t (a) = 1e t (a), where e t (a) is the measured error rate.

δ t (a): average of Q t (a, 0, s, n * ) first coordinate (expected delay) at source nodes. For each packet, source node s is randomly chosen. Its destination is always 0.

ε t (a) : average of Q t (a, 0, s, n * ) second coordinate (expected error rate) at source nodes.

Fig. 3 and4 give the delays d t (a) and success rates s t (a) vs. time period t, for experiment 2. The figures show that d t (a) and s t (a) are clearly differentiated according to application class a. Thus, the network is able to configure itself to route simultaneously data packets according to the specifications of the different application classes.

In order to show how the learning process adapts the routing policy following a failure of some nodes, the success rates and delays for two nodes close to the destination (over 4) are suddenly and strongly degraded from the 300-th time period. Figures show that the routes are changed after some time periods to prevent the routers to choose these nodes. The network is then able to almost recover its previous performance.

Figure 5 presents the histograms of the expected delays estimations δ(a) for the Russian doll decision making. They are not displayed as bar charts as usual, but as continuous functions for the sake of readability. The width of each bin is 0.1. The frequency at abscissa x is obtained from the number of values in interval (x -0.1, x].

The effect of the boundaries of box 1 of the Russian doll method are clearly visible on fig. 5 for application classes 3 and 4. Indeed, the difference of frequencies between bins 3.4 Fig. 6. Histograms of the estimation of expected delays according to application classes for experiment 1 (bin width = 0.1) consecutive bins, while 3.5 is the δ boundary for box 1 of application class 3. Similarly, the same phenomenon occurs between bins 4.4 and 4.5 for the application 4 histogram, while 4.5 is the δ boundary for box 1 of application class 4.

The standard deviation for application class 1 is quite high as expected because the only minimized criterion is ε. For the other classes, standard deviations of δ(a) are notably lower. These values show that the δ boundaries of box 1, for a = 3 or 4, behave like an attractor. These values will be compared below with results of experiment 1.

Experiment 1 carries out standard MCDM methods only. Figure 6 presents the histograms of the expected delays estimations δ(a) for the weighted Chebyshev distance minimization (application class 3) and for the weighted sum minimization (application class 4).

Compared to experiment 2, standard deviations for application classes 3 and 4 are notably higher. The histograms of δ(a) for these classes are not very different from the one of application class 1. So, the "attraction effects" towards desired objectives are much less marked than for experiment 2.

V. CONCLUSION

Setting the parameters of most MCDM methods to fit the preferences of a decision maker is a difficult task. This paper has presented a method able to choose the best multicriteria solution according to a context defined beforehand, whatever the Pareto front. This context is given by a set of nested boxes in the criteria space, the shapes of which are defined by objective facts as technical standards, technical specifications, etc. This kind of method is well suited for self-adaptive systems because it does not need the intervention of a decision maker to adjust parameters and to assess the quality of the method results.

The Russian doll multicriteria decision method has been used with a reinforcement learning to optimize the routing in a wireless network. The results on a case study show that the routing can be finely controlled because of the possibility to include as much parameters as desired to adjust the search of the best solution on Pareto fronts a priori unknown. These results was clearly better than those obtained with the minimization of a weighted sum or a Chebyshev distance to a reference point.

More work has to be done to refine the Russian doll multicriteria decision method for self-adaptive systems. In particular, the method could be improved when the Pareto front is strongly concave by using polyhedral nested boxes instead of hyper-rectangular boxes only. Its applicability should also be evaluated in multiple contexts.

Fig. 1 .

 1 Fig. 1. Choice of a non dominated criteria vector with the help of nested boxes

4 Fig. 2 .

 42 Fig. 2. Nested boxes of the Russian doll method for the four application classes

ACKNOWLEDGMENT

This work is a part of the OPERRA project supported by the "Institut TELECOM", France.