Manar Mohaisen
email: mohaisen@cs.umn.edu

Abedelaziz Mohaisen

Merouane Debbah
email: merouane.debbah@supelec.fr

Parallel QRD-M Encoder for Multi-user MIMO Systems

Keywords: MU-MIMO precoding, vector perturbation, QRD-M encoder, sphere encoder

In the context of multi-user precoding, the idea behind vector perturbation (VP) lies in adding an integer vector to the data vector such that the overall transmit power is reduced, where the performance at the users end is consequently improved. In the literature, several techniques have been proposed to find a quasi-optimum perturbing vector, where this process was represented as an integer lattice search problem. In this paper, we propose a parallel QRD-M encoder (PQRDME) that, besides attaining a quasi-optimum diversity order, leads to tremendous reduction in the latency of the vector perturbation stage. Based on the set grouping, the proposed encoder transforms the full tree-search of the conventional QRDME into partial trees that can be pipelined to increase the encoding throughput. We evaluate the proposed algorithm under several scenarios with both perfect channel state information (PCSI) and imperfect CSI (ICSI) at the

Introduction

Compared with the single-user multiple-input multipleoutput (SU-MIMO) systems [START_REF] Pollock | Introducing Space into MIMO Capacity Calculations[END_REF], multi-user MIMO (MU-MIMO) systems can achieve tremendous capacity gains without requiring additional spatial or spectral resources [START_REF] Weingarten | The capacity region of the Gaussian multiple-input multipleoutput broadcast channel[END_REF]. To this end, downlink precoding techniques based on the information-theoretic concept of dirty paper coding (DPC), first proposed by Costa in [START_REF] Costa | Writing on dirty paper[END_REF], can be used. Considering the knowledge of the data vector and the channel state information (CSI) at the base station (BS) side, inter-user interference (IUI) can be canceled so that each user only receives its designated data.

Several MU-MIMO precoding techniques were proposed in the literature in order to achieve the nearcapacity. Among these techniques the linear precoding which consists of pre-processing the data vector using a criterion-based filtering matrix, which is constructed using either the zero-forcing (ZF) or the minimum-mean square error (MMSE) criterion [START_REF] Holakouei | Multiuser precoding techniques for a distributed broadband wireless system[END_REF] (a.k.a. channel inversion and regularized inversion, respectively.) Although the MMSE precoding alleviates the noise amplification problem appearing in the case of ZF precoding-especially when the channel matrix is ill-conditioned, it still performs much worse than the optimum brute-force encoder in terms of bit-error rate (BER) performance and diversity order.

To alleviate the noise amplification, lattice-base reduction techniques iteratively find a better-conditioned base, i.e., a channel matrix with shorter and more orthogonal columns. Therefore, linear precoding is sufficient to achieve quasi-optimum performance due to the good conditionality of the reduced basis of the channel matrix. Lenstra-Lenstra-Lovasz (LLL) algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] and Seysen's algorithm (SA) [START_REF] Seysen | Simultaneous reduction of a lattice basis and its reciprocal basis[END_REF] are extensively used to obtain better bases, where LLL algorithm is shown to require fewer computations than SA for an almost negligible degradation in the BER performance [START_REF] An | Lattice reduction aided precoding for multiuser MIMO using Seysen's algorithm[END_REF]. However, drawbacks of the lattice-reduction-based precoding techniques are in their iterative nature that slows down the encoding process, and their high worst-case computational complexity, which is exponential in the case of ill-conditioned channel matrix. Theoretically, Jalden et al. have shown in [START_REF] Jalden | Worst-and average-case complexity of LLL lattice reduction in MIMO wireless systems[END_REF] that the number of iterations of the LLL algorithm is infinite when the channel matrix has a very high condition number.

To further improve the performance of MU-MIMO precoding without requiring lattice-basis reduction, the Tomlinson-Harashima precoding (THP) reduces the required transmit power via employing a non-linear modulus operation [START_REF] Harashima | Matchedtransmission technique for channels with intersymbol interference[END_REF][START_REF] Tomlinson | New automatic equalizer employing modulo arithmetic[END_REF]. A linear version of this technique consists of two stages [START_REF] Liu | Improved Tomlinson-Harashima precoding for the downlink for multi-user MIMO systems[END_REF]: (i) a vector perturbation (VP) stage, where the data vector is perturbed by an integer-valued vector such that the required transmit power is reduced, and (ii) a precoding stage where the perturbed vector is linearly precoded using any of the aforementioned linear techniques. Despite of the apparent improvement by the THP, its vector perturbation stage is equivalent to the successive interference cancellation used in the MIMO detection literature, which is not optimum. As such, further reduction in the required transmit power can be achieved once the VP stage is optimized.

The VP problem was solved in [START_REF] Chae | Block diagonalization vector perturbation for multiuser MIMO systems[END_REF][START_REF] Hochwald | A vector-perturbation technique for near-capacity multiantenna multiuser communication -Part II: Perturbation[END_REF] using the sphere encoder (SE) which suffers from sequential search nature and high worst-case complexity. In [START_REF] Zhang | Near-capacity MIMO multiuser precodingwith QRD-M algorithm[END_REF], a QRDM encoder (QRDME) was proposed to fix the computational complexity of the SE with quasi-optimum performance. Recently, we proposed a fixed-complexity SE (FSE) that overcomes both shortcomings of the SE, while lagging the performance of the optimum encoder [START_REF] Mohaisen | Fixed-complexity sphere encoder for multi-user MIMO systems[END_REF]. Contributions: In this paper, we propose a parallel QRDME (PQRDME) that achieves a tradeoff between the attained performance and the precoding throughput. Based on the set grouping, the full vector perturbation (i.e., tree-search phase) is divided into partial vector perturbation (PVP) problems that can be processed in parallel, leading to a substantial speed-up of the precoding stage. A trade-off between precoding throughput and system performance is achieved by setting the number of PVPs; a high number of PVPs indicates higher gain in the precoding throughput but also leads to sacrificed performance, and vice-versa. In [START_REF] Mohaisen | Parallel QRD-M encoder for decentralized multi-user MIMO systems[END_REF], the proposed encoder is evaluated under the assumption of single-stream transmission where the channel state is considered to be perfectly known at the transmitter. In this paper, we further consider the case of multistream communications, where users can be equipped with more than a single receive antenna. To this end, block diagonalization (BD) [START_REF] Choi | A transmit preprocessing technique for multiuser MIMO systems using a decomposition approach[END_REF] is used as a pre-processing stage that eliminates the IUI. Furthermore, we consider imperfect knowledge of the CSI at the transmitter side [START_REF] Aruna | Variable power adaptive MIMO OFDM system under imperfect CSI for mobile ad hoc networks[END_REF]. Therefore, we employ two types of channel quantization: (i) the nonuniform Lloyd-Max quantizer which is used to independently quantize the real and imaginary parts of each channel coefficient, and (ii) the phase of the channel is quantized using a uniform quantizer, where the channel amplitude is considered to be known at the transmitter. This assumption is motivated by the fact that in future-generation communication systems, several uplink control signals, such as channel quality indicator (CQI) [START_REF] Khan | LTE for 4G broadband: Air interface technologies and performance[END_REF], indicating the amplitude or reliability of the channel are already assumed to be fed back to the BS from users. Finally, we evaluate the performance of the proposed encoder under several scenarios and compare it with the conventional MU-MIMO precoding techniques. Finally, we bring more insight into the selection of candidates set size from which the elements of the perturbing vector are drawn. Organization: This paper is organized as follows. In Section 2 we introduce the system model and statement of problem. In Section 3 we briefly describe the conventional VP techniques and outline our motivations. In Section 4, we introduce the proposed PQRDME techniques and outline its merits. In Section 5, we show simulation results and finally draw conclusions in Section 6.

System Model and Statement of Problem

In this paper, we consider a downlink system in which a single BS equipped with n T transmit antennas simultaneously communicates with n U users each equipped with n R receive antennas. In this paper, we consider the minimum number of required transmit antennas, that is, n T = (n U ×n R ). Also, let the system be transformed into the K-dimensional real Euclidean space with N = (2 × n T ), then under the assumption of narrow-band flat-fading, the downlink MU-MIMO channel is given by:

H = H T 1 H T 2 • • • H T n U T , (1)

Feedback of quantized CSI

Fig. 1 Structure of the MU-MIMO precoding system with vector perturbation and imperfect CSI at the transmitter.

where H i ∈ R (2×n R )×N is the channel coupling the n T transmit antennas to the n R receive antennas of user i, and (•) T denotes the matrix transpose.

Having both the data vector s ∈ R N and the channel matrix H at the BS, linear precoding techniques treat the data vector using a filtering matrix to obtain the following precoded vector:

x = P s √ γ = (H T H + αI N ) -1 H T s √ γ , (2)
where α, the regularization coefficient, is set to zero in the case of ZF precoding and to a value proportional to the noise variance in the case of MMSE precoding. Also, the scaling factor γ is present to fix the expected transmit power to a predefined value, which is set to 1. Therefore, the receive signal-to-noise ratio (SNR) at each receive antenna is given by E(s * s)/γσ 2 n . Since γ is inversely proportional to the conditionality of channel matrix, the receive SNR is degraded when the channel matrix is ill-conditioned.

As an alternative to the linear precoding techniques, THP reduces the required transmit power using a nonlinear modulo operation that limits the power of the precoded symbols. Conventionally, symbols are precoded successively, where each precoded symbol, e.g., s i , is rounded into a predefined range. In [START_REF] Liu | Improved Tomlinson-Harashima precoding for the downlink for multi-user MIMO systems[END_REF], a linearized version of the THP was introduced where the algorithm is split into two successive stages; namely, the VP stage and the linear precoding stage as shown in Fig. 1. The VP stage of the THP algorithm is given as:

s = s + τ t, (3)
where t is an N -dimensional vector with integer elements. In [START_REF] Hochwald | A vector-perturbation technique for near-capacity multiantenna multiuser communication -Part II: Perturbation[END_REF], τ is defined as an integer given by:

τ = 2 (|c max | + ∆/2) , (4)
where |c max | is the absolute value of the symbol with the largest magnitude, and ∆ is the spacing between any two neighbor symbols. Now, let the precoder fully equalizes for the channel effect, then the data symbols can be recovered at the receivers using a simple modulo operation that reduces the range of the received signal y to [-K, K) with K as the square root of the cardinality of the modulation set. Despite the improvement achieved by the THP compared to the linear precoders, its VP stage is equivalent to the successive interference cancellation, where only a single t candidate is retained at each VP level. This technique is not optimum, which means that further reduction in the required transmit power, i.e., smaller γ, can be achieved once the VP stage is optimized.

To this end, the VP is represented as an integer lattice-search as following:

t = arg min t∈Z N (s + τ t) T P T P(s + τ t) , = arg min t∈Z N P(s + τ t) 2 . (5)
Now, let the transpose of the matrix H be factorized into the product of a unitary matrix Q and an upper triangular matrix R, thus, the search problem in [START_REF] Costa | Writing on dirty paper[END_REF] based on the zero-forcing criterion is simplified into:

t = arg min t∈Z K L(s + τ t) 2 , = arg min t∈Z K K i=1 L i,i (s i + τ t k ) + i-1 j=1 L i,j (s j + τ tj ) 2 , (6)
where the lower-triangular matrix L = (R -1 ) T . As such, the VP problem is defined as finding the integer vector t that minimizes γ. In the sequel, t will be drawn from the integer set A of size T . In the following section, we introduce several conventional VP techniques and the motivations for the proposed PQRDME.

Conventional VP techniques and Motivations

In this section, we briefly introduce three conventional MU-MIMO precoding techniques, namely, SE, QRDME, and FSE. The main idea of the SE is to restrict the search for the optimum perturbing vector inside a hypersphere of a predefined radius. That is,

t = arg min t∈Z N P(s + τ t) 2 ≤ d 2 , ( 7
)
where d is the search radius. SE is shown to achieve a quasi-optimum performance with low average computational complexity [START_REF] Hochwald | A vector-perturbation technique for near-capacity multiantenna multiuser communication -Part II: Perturbation[END_REF]. However, SE has two drawbacks: (i) its worst-case complexity is exponential, i.e., comparable to that of the brute-force search, and (ii) it has an iterative tree-search phase that limits the efficient implementation using pipelining.

To overcome the random computational complexity of the SE, the QRDME has been proposed in [START_REF] Zhang | Near-capacity MIMO multiuser precodingwith QRD-M algorithm[END_REF]. In the QRDME, the best M candidates with the least accumulative metrics are retained at each encoding level. Fig. 2 depicts an example of the QRDME M = T = K = 4. At the first encoding level, the best 4 candidates are retained for the second encoding level. At the last encoding level, the perturbed vector with the least accumulative metric is precoded and transmitted. Although QRDME achieves a quasi-optimum performance, its tree-search phase cannot be efficiently implemented using pipelining, where consequently the encoding throughput is reduced.

In [START_REF] Mohaisen | Fixed-complexity sphere encoder for multi-user MIMO systems[END_REF], we proposed the FSE, which overcomes both drawbacks of the SE. The employed tree search strategy in the FSE achieves a full parallelization of the VP stage, leading to tremendous gains in the precoding throughput. The only drawback of the FSE is that it lags the optimum BER performance.

In this paper, we propose a PQRDME that achieves a tradeoff between the achieved performance and the precoding throughput by selecting the appropriate number of PVPs.

Proposed Parallel QRDM Encoder

The goal of the PQRDME is to achieve a tradeoff between encoding throughput, i.e., speed, and system performance. To do that, the set of candidates for the elements of t, i.e., A, is divided into non-overlapping subsets of equal cardinalities. That is,

A = G i=1 D i , (8)
where G is the number of subsets and the i-th subset is designated D i . The tree-search of the conventional QRDME is then divided into independent PVPs that are processed in parallel, where the candidates for t 1 at the j-th PVP is drawn from the subset D j . Moreover, all the candidates for t are retained at the first p levels. When p = 1, each PVP represents a smaller tree-search equivalent to that of the conventional QRDME with the difference that the candidates for t 1 are drawn from the partial subset D. However, when p = 2, all the resulting branches at the first and second encoding levels are retained. In the following, PQRDME for p = 1 and p = 2 are referred to as PQRDME-p1 and PQRDME-p2, respectively. Note that the candidates for t p+1 to t K are drawn from the full set A. , where M G is the number of candidates retained at each encoding level per PVP. Note that the number inside the circle representing each node indicates the index of the hypothesis for t. At the first encoding level, the set of candidates A is divided into two subsets of equal sizes. As a result, the full tree is divided into two parallel and independent PVP problems. In the j-th PVP, the root node is extended to all possible candidates of (s 1 + τ t), where t ∈ D j . All obtained branches are retained and their metrics are computed based on [START_REF] Costa | Writing on dirty paper[END_REF]. At the second encoding level, all the retained candidates from the first level are extended to all possible candidates of (s 2 +τ t), where t ∈ A, the accumulative metric of all the resulting branches are computed using (5) and the best two (i.e., M G ) candidates with the least accumulative metrics are retained to the following encoding levels. This process is repeated up to the last encoding level. For each PVP, the best perturbed vector, with the least accumulative metric, is retained. These best candidates per each PVP are compared and the best among them is announced as the result of the proposed PQRDME-p1 algorithm. The perturbed vector is then precoded and transmitted via the n T transmit antennas. Figure 4 depicts an example of the proposed PQRDME for p = 2, G = M G = T = 2, and K = 4. At each PVP, the root is extended to all possible candidates of (s 1 + τ t) with t ∈ D j , where all candidates are retained (two candidate per PVP in this example). The retained candidates at the first encoding level are extended to all possible candidates (s 2 + τ t), where t ∈ A. Also, all the resulting candidates are retained. In the third encoding level, the extended candidates are sorted based on their accumulative metrics and the two (i.e., M G ) with the least accumulative metrics are retained for the next encoding levels. The process is repeated as with PQRDME-p1, where at the last encoding level the best candidate that requires the least transmit power is precoded and transmitted.

Based on the above description, it stems out that the proposed PQRDME achieves a tradeoff between the parallelization capabilities, by controlling the number of PVPs (G), and the performance of the MU-MIMO system. That is, the proposed encoder is at least G times faster than the conventional QRDME for a tolerable degradation in the BER performance. Also, compared to the conventional QRDME, the proposed PQRDME requires a lower number of comparisons to select the retained hypotheses at each encoding level. The QRDME retains all candidates at the first encoding level, therefore no comparisons are required. The T = M candidates retained at the first encoding level are expanded to all possible hypotheses, leading to M T branches. To order these branches and select the best M candidates, we require ((M ×T ) 2 -1) comparisons. The same applies to all the encoding levels except the first, leading to an overall number of comparisons of ((M ×T ) 2 -1)(K -1), which is equal to 765 for the parameters given in Fig. 2. In the case of PQRDME-p1, the first encoding level does not require any comparison. In the following levels, ((M G × T ) 2 -1) comparisons are required per PVP to sort the extended branches and select the best M G candidates. This leads to a total of G((M G ×T ) 2 -1)(K -1) comparisons, which is equal to 378 for the parameters given in Fig. 3. Finally, PQRDME-p2 does not require comparisons in both the first and second encoding levels, therefore it requires G((M G × T ) 2 -1)(K -2) = 60 comparisons, for the parameters given in Fig. 4. Thus, the proposed PQRDME requires a fraction of the number of comparisons performed by the conventional QRDME. Since comparisons are done serially, which add further delay to the VP stage, the proposed encoder achieves additional gains in the encoding throughput besides reducing the computational power required to perform the comparisons. In terms of the number of visited nodes and based on the parameters of Figs. 234, the conventional QRDME visits T nodes at the first encoding level and (M × T ) nodes at each of the remaining encoding levels leading to a total of (T + (M × T )(K -1)) = 52 nodes, for the parameters given in Fig. 2. The proposed PQRDME-p1 visits T nodes at the first encoding level, and M G T nodes per level per PVP at the remaining encoding levels, leading to a total of (T + (GM G T )(K -1)) = 52 nodes, for the parameters given in Fig. 3. Finally, the proposed PQRDME-p2 visits T nodes at the first encoding level, GT nodes at the second encoding level, and M G T nodes per level per PVP at the remaining (K -2) levels, leading to a total of (T (G + 1) + (GM G T )(K -2)) nodes, which is equal to 22 for the parameters given in Fig. 4. This emphasizes on the effectiveness of the proposed PQRDME-p2 in terms of both number of comparisons and number of visited nodes, as compared to the conventional QRDME.

5 Simulation Results, Discussions, and Analyses

Simulation environment

In the following, we use the linear MMSE criterion in the precoding stage due to its superior performance, as compared to the ZF criterion. Bits are mapped to symbols using quadrature-phase shift keying (QPSK) modulation. Also, we consider that the channel is either perfectly or imperfectly known at the transmitter, where the imperfection in the channel knowledge is due to quantization error. Users are considered to be decentralized, hence they are non-cooperative. The BD of the channel matrix is achieved via the singular-value decomposition block diagonalization.

Setting the size of A

Unlike most works in the MIMO detection literature, where the candidates for the transmitted data belong to a predefined modulation set, the size of the set A is not theoretically defined, but rather depends on the system configuration and the employed VP technique. Therefore, in this paper we use intensive simulations to identify the size of the set A for the conventional and the proposed encoders. Table 1 summarizes the probability of t for t ∈ A in the perturbing vector. We remarked that prob(t = +a) = prob(t = -a) for a ∈ A, that is why we present the values as prob(t = ±a) which is equal to 2×prob(t = +a). We remark that the size of the set A for the less optimized algorithms, such as the THP and FSE-p1, is smaller compared to that of the more optimized QRDME. Also, we remarked that the probability of (|t| > 1) is very small but it has an impact on the BER performance, especially at high value of signal-to-noise ratio (see [START_REF] Mohaisen | Fixed-complexity sphere encoder for multi-user MIMO systems[END_REF], Fig. 3.) Besides, we remarked that these values are not affected by the size of the system (i.e., n U and n T ). Finally, since the proposed PQRDME-p2 algorithm achieves a quasi-optimal performance with T = 3 (see Fig. 7), where a marginal gain in the BER can be achieved by increasing T , the size of the set A is therefore restricted to 3. Fig. 5 depicts the probability of candidates for t using the proposed PQRDME for p = 2, G = M G = T = 3, and K = 8 for several SNR values. At low SNR values, prob(t = 0) is close to 1, which indicates that the VP stage is not efficient and the resulting transmitter is equivalent to the MMSE precoder. However, as the SNR increases, prob(t = ±1) increases, where the required transmit power is consequently reduced. This can be seen from the BER curves where the performance of the linear equalization and the proposed encoder coincide at low SNR values while the proposed PQRDME achieves better performance at high SNR close to the optimum encoder.

5.3 Single-stream transmission with perfect CSI at the transmitter Fig. 6 shows the BER performance of the proposed PQRDME for p = 1 and M = (G × M G ) = T = 8 and those of several conventional precoding techniques. Note that we set T = 5 and T = 7 in the case of THP and FSE-p1, respectively, since no further improvement is achieved by increasing T . For G = 2, PQRDME-p1 performs close to the QRDME algorithm, while increasing the encoding throughput by a factor of two. When G is increased to 4, the encoding throughput is increased by a factor of four, while the performance is degraded due to the increased parallelization. However, the proposed PQRDME-p1 still outperforms the FSE algorithm. Also, as shown in Figure 6, THP and LMMSE have lower performance and diversity order compared to the proposed PQRDME-p1 algorithm. Fig. 7 depicts the performance of the proposed PQRDME-p2. Note that for p = 2, the performance of the FSE Table 1 Probability of t in the perturbation vector τ t in a MU-MIMO system for K = 8, n U = 4, and SNR = 20dB, averaged over 100,000 independent trials. and that of the proposed PQRDME algorithm are improved compared to the case of p = 1. Yet, the proposed PQRDME-p2 outperforms the FSE-p2 by about 1dB at a target BER of 10 -4 . Also, the proposed PQRDME-p2, at least, triples the speed of the VP stage. This happens because the proposed encoder not only parallelizes the VP stage but also reduces the number of visited nodes and the performed comparisons to select the best candidates at each encoding level.

Multi-stream transmission with perfect CSI at the transmitter

When the number of users increases and each user is equipped with more than one antenna, the encoder becomes extremely slow due to the high dimension of the tree to be searched. To overcome this problem, the IUI can be cancelled out at the transmitter side by means of block diagonalization (BD). Therefore, the goal of the BD is to transform the MU-MIMO channel into several parallel SU-MIMO channels with zero inter-channel in- terference [START_REF] Stankovic | Combination of block diagonalization and THP transmit filtering for downlink beamforming in multi-user MIMO systems[END_REF]. That is, BD find the matrix B such that

H eff = HB =      H eff,1 0 • • • 0 0 H eff,2 • • • 0 . . . . . . . . . . . . 0 0 • • • H eff,n U      . (9)
In this scenario, B can be seen as a beamforming matrix, with H eff,i as the effective channel matrix for user i. As a result of the BD, users' data can be perturbed and encoded independently, leading to further gains in the encoding throughput.

In this paper, we consider a (n T , n U , n R ) MU-MIMO system with n T = (n U × n R ). Fig. 8 depicts a BER comparison between the proposed PQRDME-p2 and FSE-p2 in [START_REF] Holakouei | Multiuser precoding techniques for a distributed broadband wireless system[END_REF][START_REF] Choi | A transmit preprocessing technique for multiuser MIMO systems using a decomposition approach[END_REF][START_REF] Aruna | Variable power adaptive MIMO OFDM system under imperfect CSI for mobile ad hoc networks[END_REF] and [START_REF] Holakouei | Multiuser precoding techniques for a distributed broadband wireless system[END_REF][START_REF] Aruna | Variable power adaptive MIMO OFDM system under imperfect CSI for mobile ad hoc networks[END_REF][START_REF] Choi | A transmit preprocessing technique for multiuser MIMO systems using a decomposition approach[END_REF] systems. The proposed PQRDME-p2 outperform the conventional encoder by 0.8dB and 1.5dB in the [START_REF] Holakouei | Multiuser precoding techniques for a distributed broadband wireless system[END_REF][START_REF] Aruna | Variable power adaptive MIMO OFDM system under imperfect CSI for mobile ad hoc networks[END_REF][START_REF] Choi | A transmit preprocessing technique for multiuser MIMO systems using a decomposition approach[END_REF] Fig. 8 BER performance of the proposed PQRDME-p2 for M G = T = 3, and a (n T , n U , n R ) MU-MIMO system.

MU-MIMO system with imperfect CSI at the transmitter

In this section, we consider the channel coefficients to be quantized at the mobile stations. Then, the quantized version of each channel coefficient is fed back to the BS over a fast allocated control channel. In this paper, we consider the following two quantization schemes:

1. Lloyd-Max non-uniform quantizer: Uniform quantization divides the range to which the variable belongs into equal intervals. If the variable to be quantized belongs to a certain interval, then the centroid of the interval is considered as the quantized version. This quantizer is suitable for uniformly distributed variables, which is not the case of the MU-MIMO system. In this paper, we consider the real and imaginary parts of the channel to be i.i.d. centered Gaussian variables. Therefore, the non-uniform Lloyd-Max quantizer, which takes the probability density function (pdf) of the variables to be quantized into consideration, is more suitable [START_REF] Lloyd | Least squares quantization in PCM[END_REF][START_REF] Max | Quantizing for minimum distortion[END_REF]. The Lloyd-Max quantizer iteratively finds the intervals' endpoints so that the mean square error (MSE) between each channel coefficient and its quantized version is minimized. This can be achieved by allocating shorter intervals when the pdf has high values (i.e., the variable is most probable) and longer intervals when the pdf has low values. Fig. 9 depicts the performance of the proposed PQRDME-p2 for several values of B; the number of quantization bits for each part. For a low B, the BER increases, where when B = 5 the degradation due to the quantization error is tolerable.

Uniform phase quantization:

In future-generation communication systems, such as LTE/LTE-A [START_REF] Khan | LTE for 4G broadband: Air interface technologies and performance[END_REF], the channel power is quantized and fed back to the BS via a control signal to enable adaptive modulation and coding (AMC), scheduling, etc. Therefore, it is of interest to consider that the channel amplitude is known at the transmitter and only quantize the phase of each channel coefficient. Note that the amplitude of the channel coefficient follows a Rayleigh distribution which is a positive distribution with much more concentration than the Gaussian one. Therefore, a lesser number of bits is required to quantize the amplitude as compared to quantizing the real and imaginary parts which follow a double-sided distribution with higher variance. Fig. 10 shows the BER performance of the proposed PQRDME-p2 for several values of B; the number of quantization bits for each phase value. B = 6 is suitable for quantizing the phase of the channel coefficients since the degradation due to the quantization error is tolerable.

A remark on the optimality of the proposed PQRDM encoder

The proposed encoder is quasi-optimum, which means that the linear MMSE encoder might have a lower γ if the VP stage deviates from the optimum solution. Therefore, the efficiency of the vector perturbation can be measured by the amount of reduction it can achieve in the required transmit power, taking the linear pre- Fig. 11 Percentage that the MU-MIMO system with vector perturbation requires more power than the conventional linear precoding.

coder as a reference. Fig. 11 depicts the percentage of achieving an increase in the transmit power by several VP techniques. That is, the probability (given in percent) that the system employing VP requires more transmit power than the simple linear MMSE encoder. Intuitively, this percentage increases proportionally with the number of transmit antennas. This is because for higher system dimensions, the probability that the VP technique deviates from the optimum solution increases. QRDME achieves the best performance followed by the proposed algorithms, where at low system dimensions the proposed PQRDME-p2 performs close to QRDME.

Conclusions

In this paper, we proposed a parallel QRDM encoder (PQRDME) for MU-MIMO systems. Unlike the conventional QRDME scheme, which has a limited capabil-ity for parallel implementations, the proposed PQRDME has a parallel tree-search structure, leading to higher efficiency for hardware implementation via pipelining. Besides, the proposed PQRDME-p2 achieves a tremendous reduction in the computational complexity due to its improved VP stage. In this paper, we considered realistic scenarios, where users are equipped with more than a single receive antenna in a multi-stream transmission. Furthermore, we consider the channel coefficients to be quantized and fed back to the BS rather than being perfectly known at the transmitter. To demonstrate the efficiency of our proposed encoder in such scenario, two quantization schemes have been addressed. In all scenarios, simulation and analytical results show that the proposed PQRDME performs close to the optimum encoder and attains the optimum diversity order, while achieving higher encoding throughput and much lower computational complexity. Moreover, the proposed PQRDME outperforms the FSE and THP for all the simulated scenarios.

Fig. 2

 2 Fig. 2 An example of the conventional QRDM encoder for M = T = K = 4.

2 Fig. 3

 23 Fig.[START_REF] Chae | Block diagonalization vector perturbation for multiuser MIMO systems[END_REF] An example of the proposed parallel QRDM encoder for p = 1, G = M G = 2, and T = K = 4.

Figure 3

 3 Figure 3 depicts an example of the proposed PQRDME for p = 1, G = M G = 2, and T = K = 4, where M G is the number of candidates retained at each encoding level per PVP. Note that the number inside the circle representing each node indicates the index of the hypothesis for t. At the first encoding level, the set of candidates A is divided into two subsets of equal sizes. As a result, the full tree is divided into two parallel and independent PVP problems. In the j-th PVP, the root node is extended to all possible candidates of (s 1 + τ t), where t ∈ D j . All obtained branches are retained and their metrics are computed based on[START_REF] Costa | Writing on dirty paper[END_REF]. At the second encoding level, all the retained candidates from the first level are extended to all possible candidates of (s 2 +τ t), where t ∈ A, the accumulative metric of all the resulting branches are computed using (5) and the best two (i.e., M G ) candidates with the least accumulative metrics are retained to the following encoding levels. This process is repeated up to the last encoding level. For each PVP, the best perturbed vector, with the least accumulative metric, is retained. These best candidates per each PVP are compared and the best among them is announced as the result of the proposed PQRDME-p1 algorithm. The perturbed vector is then precoded and transmitted via the n T transmit antennas.

Fig. 4

 4 Fig.[START_REF] Choi | A transmit preprocessing technique for multiuser MIMO systems using a decomposition approach[END_REF] An example of the proposed parallel QRDM encoder for p = 2, G = M G = T = 2, and K = 4.

Fig. 5

 5 Fig.5Probability of the candidates for t using the proposed PQRDME for p = 2, G = M G = T = 3, and K = 8.

2 QRDME, T = 8 Fig. 6

 286 Fig.6BER performance of the proposed PQRDME for p = 1, M = T , and K = 8.

9 Fig. 7

 97 Fig. 7 BER performance of the proposed PQRDME for p = 2, M G = T , and K = 8.

Fig. 9

 9 Fig.9BER performance of the proposed PQRDME-p2 for M G = T = 3 and K = 8 with imperfect CSI at the transmitter. The real and imaginary parts are quantized using Lloyd-Max non-uniform quantizer, where each part is represented by B bits.

Fig. 10

 10 Fig.10BER performance of the proposed PQRDME-p2 for M G = T = 3 and K = 8 with imperfect CSI at the transmitter. The phase of each channel coefficient is uniformly quantized and represented by B bits.

Perturbation + P Precoding Transmitter H IUI Cancellation (Effective Channel) Channel Receivers MOD Demodulation s s % Receiver for user 1 1 ŝ x τ t Channel estimation Quanrization Vector perturbation Linear precoder Receiver for user n U

has been presented at This work is supported by research subsidy for newlyappointed professor at Korea University of Technology and Education (KoreaTech) for the period 2012-2013.


César Bernardini
email: cesar.bernardini@inria.fr

Thomas Silverston
email: thomas.silverston@inria.fr

Olivier Festor
email: olivier.festor@inria.fr

Cache Management Strategy for CCN based on Content Popularity

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The Internet is currently mostly used for accessing content. Indeed in the 2000s, P2P traffic for file-sharing counted for about 80% of the overall Internet traffic. Nowadays, video streaming services such as Youtube represent the most important part of the Internet traffic. It is expected that the sum of all forms of video (TV, VoD and P2P) will be approximately 86% of global consumer traffic by 2016 [START_REF]Cisco. Cisco visual networking index: Global mobile data traffic forecast update[END_REF].

While the Internet was designed for -and still focuses on-host-to-host communication (IP), users are only interested in actual content rather than source location. Hence, new Information-Centric Networking architectures (ICN) such as CCN [START_REF] Jacobson | Networking named content[END_REF] have been proposed. ICN architectures give high priority to efficient content distribution at large scale and have attracted considerable attention from the research community [3].

Content Centric Networking (CCN) is a network architecture based on named data where a packet address named content, not location. The notion of host as defined into IP does not exist anymore. In CCN, the content is not retrieved from a dedicated server, as it is the case for the current Internet. The premise is that content delivery can be enhanced by including per-node-caching as content traverses the network. Content is therefore replicated and located at different points of the network, increasing availability for incoming requests. An important feature for CCN is to manage the cache of nodes with caching strategies and replacement policies, which decide whether to cache and in case the cache is full, the element to be replaced respectively. It is therefore essential to design efficient cache management strategies adapted to CCN networks. Some content can be largely popular and requested by a large number of users while some other may have a more limited audience and stay confidential. Thus, we believe that the popularity of content should be take into account while designing efficient cache management strategy for CCN.

In this work, we present our new cache management strategy, Most Popular Content (MPC), designed for CCN. Instead of storing all the content at every node on the path, MPC caches only popular content. MPC caches less than CCN default strategy but still improves in-network caching performance while -at the same time-decreases resource consumption. In the paper, we first provide an overview of CCN, then we introduce MPC and present our simulation environment and performance evaluation of MPC.

Most Popular Caching Strategy

CCN Overview

CCN architecture is mostly based on two primitives: Interest and Data. A consumer requests content by sending an Interest message in the network; any node hearing the request and having the data can issue a response with a Data message. The content is therefore transmitted to the consumer and every node on the delivery path can cache the data. With no clearly defined cache management strategy, the CCN default strategy always stores content at all nodes on the delivery path (Always strategy).

As this strategy could lead to replace unpopular by popular content, we argue that caching only popular content will allow to achieve high performances and it will at the same time save resources. Therefore, we design MPC -Most Popular Content-a new cache management strategy for CCN, where nodes cache only popular content.

Most Popular Caching Strategy

In MPC, every node counts locally the number of requests for each content name, and stores the pair (Content Name; Popularity Count) into a Popularity Table .  Once a content name reaches locally a Popularity Threshold, the content name is tagged as popular and if the node holds the content it suggests its neighbor nodes to cache it through a new Suggestion primitive. These suggestion messages may be accepted or not, according to local policies such as resource availability. As the popularity of a content can decrease with time after the suggestion process, the Popularity Count is reinitialized according to a Reset Value in order to prevent flooding the same content to neighbors. MPC Strategy influences directly in CCN node requirements.

In addition to CCN cache space required, MPC needs an extra space to store the Popularity Table . For instance, to keep one million table entries means 1GB of RAM memory using 1023B per content name and 1B for the Popularity Count (we used fixed length for the name to simplify calculation).

Simulation Environment

In order to evaluate our new strategy MPC, we use ccnSim [START_REF] Rossi | Caching performance of content centric networksunder multi-path routing (and more)[END_REF], a chunk-level CCN simulator, developed in C++ over the Omnet++ framework.

For our experiments, we use a large-scale Youtube-like catalog containing 10 8 video of 10M B each: approximately a catalog of 1P B. The cache size is set to 10 GB. The popularity of files is modeled following a MZipf distribution function available in ccnSim [START_REF] Rossi | Caching performance of content centric networksunder multi-path routing (and more)[END_REF]. Then, for each experiment, we randomly set one catalog and 8 requester nodes on the topologies. In the experiments, we ramdomly place one catalog and 8 requester nodes into the ccnSim-included topologies. We then perform 10 runs of the same simulation and provide the average value.

Preliminary Results

The performance of MPC is measured according to (i) the probability to obtain a Cache Hit all along the path; (ii) the number of caching operations over the number of issued messages (Ratio of Cached Elements); the proportion of traveled hops across the network with respects to the original path from content source to its destination. (Stretch); (iv) the ratio of different chunks stored in the caches (Diversity).

In the Figure 1a, our strategy Cache Hit is greater than 85% and at the same time higher than CCN. Even when CCN reaches its highest results with Level3 or DTelecom topologies, MPC still outperforms CCN. The Ratio of Cached Elements is presented in the Figure 1b. CCN's default strategy generates one operation per every issued message which means CCN Ratio of Cached Elements is always 1. Fig. 1b shows that our MPC strategy caches up to 5 times less content than CCN for the Tree, Abilene, Geant and Tiger topologies (approximately 20%), performing less caching operations and saving memory. With DTelecom and Level3, our strategy caches more content than other topologies but still out-perform CCN (80% and 60% respectively). For this particular topology, this is due to the high connection degree of nodes.

Due to space constraints, we do not present the Figure for the Stretch metric or Diversity of content in cache. For the Stretch metric, MPC and CCN exhibit similar results: about 10% for all the topologies and both strategies are able to cache content close to requesters.

The CCN Diversity ranges from 28% to 35% for all the topologies and the MPC Diversity is much lower from 3% to 18%. Regarding Diversity, it was expected that MPC is less efficient than CCN since MPC has been designed in order to cache only popular content, limiting the diversity of the chunks in the cache of nodes.

Conclusion

In this work, we present MPC, our new cache management strategy for CCN networks. MPC strategy caches only popular content and reduces the cache load at each node.

Our simulation experiments show that MPC outperforms the CCN default caching strategy. MPC achieves a higher Cache Hit Ratio and still reduces drastically the number of replicas. By caching less data and improving the Cache Hit ratio, MPC improves network resources consumption.

Future Work

As future work, we expect to investigate the popularity concept in social environments. Nowadays, the Internet has become a social-oriented network, where users organize themselves into communities and share content among them. A group of popular users receive most of the attention and tend to act as opinion leaders. Thus based on this fact, we expect to privilege popular users by proactively spreading their content into caches. We advocate popular users generate content more likely to be requested by other users.

Fig. 1 :

 1 Fig. 1: MPC vs. CCN (LRU/Always) over different topologies


Charif Haydar
email: charif.alchiekhhaydar@loria.fr

Azim Roussanaly
email: azim.roussanaly@loria.fr

Anne Boyer
email: anne.boyer@loria.fr

Local trust versus global trust networks in subjective logic

Social web permits users to acquire information from anonymous people around the world. This leads to a serious question about the trustworthiness of information and sources. During the last decade, numerous models were proposed to model social trust in the service of social web. Trust modeling follows two main axes; local trust (trust between pair of users), and global trust (user's reputation within the community). Subjective logic, is an extension of probabilistic logic that deals with the cases of lack of evidences. An elaborated local trust model based on subjective logic already exists. The aim of this work is to apply this model to the first time on a real data set. Then, we propose another global trust model based also on subjective logic. We apply both models on a real data set of a question answering social network that aims to assist people to find solutions to their technical problems in various domains. Our proposed global trust model ensures a better performance thanks to its precise interpretation of the context of trust, and its ability to satisfy new arrived users.

I. INTRODUCTION

Web 1.0 provided a popular access to the largest data store ever existed (Internet). The major difficulty resided in extracting relevant information and resources from the huge mass of data available for most queries. Information retrieval (IR) came out to yield Internet more efficient and exploitable by ranking resources according to their relevance to queries. Then, web 2.0 arrived with more interactive tools such as forums and social networks. The numerous people who were only the spectators in web 1.0, became the actors in web 2.0. They are now able to share their own opinions and knowledge. Collaborative IR and social recommender systems (RS) [START_REF] Zuva | A Survey of Recommender Systems Techniques, Challenges and Evaluation Metrics[END_REF] are now used to rank this kind of resources.

Practically, social web permits users to acquire information from anonymous people around the world. This leads to a serious question about the trustworthiness of information and sources. To get over this problem, many computational models were proposed to model social trust and integrate it in different social online domains such as social networks, recommender systems [START_REF] Massa | Using trust in recommender systems: An experimental analysis[END_REF], [START_REF] Golbeck | Computing and Applying Trust in Web-based Social Networks[END_REF], file sharing [START_REF] Kamvar | The Eigentrust Algorithm for Reputation Management in P2P Networks[END_REF] ...etc. Social trust, for us, is the belief of an individual, so called truster, that another individual, so called trustee, has the competence and the willingness to execute or to assist in the execution of a task to the favor of the truster. The assistance can simply consist in recommending another individual to execute the task. The truster tries to acquire information and construct his own belief about the trustee before deciding to cooperate with him. We are interested in two methods to construct the belief about the trustee; the first is called local trust, it depends on the past interactions between the truster and the trustee, and on the word of mouth mechanism that allow the truster to acquire information about the trustee from his friends and theirs'. The second is called global trust, it depends on the reputation of the trustee within the community.

Subjective logic (SL) [START_REF] Audun | Subjective logic[END_REF] is an extension of probabilistic logic, based on the belief theory [START_REF] Dempster | The DempsterShafer Calculus for Statisticians[END_REF], [START_REF]Advances in the Dempster-Shafer Theory of Evidence[END_REF]. SL was already used to build a local trust model (LTSL) [START_REF] Josang | Trust Network Analysis with Subjective Logic[END_REF]. To the best of our knowledge, this model was never experimented with real data. In this paper, we propose a new global trust model based on subjective logic (GTSL), we implement the local trust model and compare the performance of both models on real data, and we compare them to a referential trust model called Moletrust [START_REF] Massa | Using trust in recommender systems: An experimental analysis[END_REF].

The object of our application is the dataset stackoverflow 1 . It is a social website based on a question answering platform to assist users to find answers to their questions in divers domains (programming, mathematics, English language, cooking ...). We assume that proposing an answer is a proof of willingness to assist the asker. Therefore, our objective is to find the user capable to provide the most relevant answer in function to his competence in the current context.

Local trust models suffer from a cold start problem, they can not deal neither with new users nor with users having no friends [START_REF] Haydar | Hybridising collaborative filtering and trust-aware recommender systems[END_REF]. Global trust models are not concerned by this problem. It is efficient even to cold start users, which improves its performance.

All three models in this paper are context aware, still their interpretations of the context are distinct. LTSL and Moletrust consider the domain of the question as the context, whereas GTSL considers a more refined context relying on the subject of the question. The precision in defining the context is another key element to GTSL to surpass the performance of the other two models.

The paper is organized as following: in section II we present the general framework, starting by presenting social trust and computational trust. In II-B we introduce subjective logic and some of it's operators. In section III, we describe the local trust SL model that we implement, and the global trust SL model that we propose. Section IV is dedicated to argue about other trust models and justify our choice of SL. In section V, we describe the used dataset, and present our evaluation method. In section VI we discuss our results. Finally in section VII we present our conclusions and future work.

II. GENERAL FRAMEWORK

The objective of trust is to find the appropriate person to cooperate with in order to achieve a given task or context. Truster's decision about to cooperate or not is influenced by many factors. In the following section we present a real life example about trust in order to explain this phenomena, and some factors that can influence the cooperation decision.

Suppose that Alice needs to repair her car. Alice knows Bob and Eric. Alice trusts Bob, but he has no experience in repairing cars. Even though Alice trusts Bob, she will not ask him to repair her car because she thinks that he lakes competence. Eric is mechanician, but the last time he changed her car's water pump he affixed a second hand one, and charged her for a new one. Alice considers Eric dishonest, so unwilling to execute the task properly. Nevertheless, Alice might accept to cooperate with Eric in certain extreme cases; for example if she is stranded nearby to his garage, or if no other mechanician is available.

Alice uses her own experience and past interactions with Bob and Eric to decide if she will cooperate with one of them or not. This example show the major role of the Alice's belief about the competence and willingness of Bob and Eric. The context here is (vehicle repairing). Hence, the belief of Alice is related to the context (basically Bob is trustee, but not in this context). In other words, Alice's decision is related to her past interactions with Bob and Eric, and the current context. Suppose now that Bob knows another mechanician called Dave. Bob was always satisfied by the work of Dave to repair his car. Bob recommends Dave to Alice. Alice accepts to cooperate with Dave although she does not know him personally, just because he is recommended by a trustee friend. Although trust is not transitive (in the mathematical meaning of transitivity), but it is still influenceable by intermediate persons [START_REF] Josang | Trust Network Analysis with Subjective Logic[END_REF], [START_REF] Golbeck | Computing with Social Trust[END_REF], [START_REF] Massa | Using trust in recommender systems: An experimental analysis[END_REF], [START_REF] Golbeck | Computing and Applying Trust in Web-based Social Networks[END_REF]. If no past direct interaction between the truster and the trustee, a trustee intermediate can assist to establish a link between them at a first time, the link then will be updated by direct interactions, so if Alice was satisfied by the work of Dave, her trust in him will increase, otherwise it will decrease. This is how the word of mouth works. Trustee friends can assist in accomplishing the task by recommending other people. Hence, trust relationships might have different types and purposes. In [START_REF] Josang | Trust Network Analysis with Subjective Logic[END_REF], authors define four properties of trust relationships:

1) Direct trust: trust is the result of interactions between exclusively the truster and trustee, such as the relations Alice Bob, Alice Eric and Bob Dave.

2) Indirect trust: the two persons do not know each others. Trust is established due to trustee intermediate persons, such as the relation Alice Dave. 3) Functional trust: the expectation of the truster is that the trustee accomplish the task himself, such as the relation Alice Eric and Alice Dave. 4) Referential trust: the expectation of the truster is that the trustee will recommend someone to accomplish the task, such as the relation Alice Bob. Note that recommendation of Bob could also be based on his referential trust in another person who knows Dave. In other words, no obligation for the trustee in referential trust to base his recommendation on a functional trust relation. Normally a series of referential trust relations must end with one functional trust relation [START_REF] Josang | Semantic Constraints for Trust Transitivity[END_REF].

Alice may receive advices from other people, such as in figure 1, where continuous lines represent trust, and dashed ones represent distrust. Alice has contradictory information about Dave. Treating these information is a complicated issue. For example, while Alice distrusts Fred, should she neglect his opinion or consider its opposite? If Alice were new in the city, and has no friends yet. The word of mouth technique would not be useful for her. Nevertheless, she can rely on the reputation of Dave using for example a specialized magazine in classifying mechanisians, or even by contacting the manufacturer of her car and asking for a certified mechanisian in her zone. Till now we considered the context as "vehicle repairing", we could be more precise by including for example the mark, the model and the fabrication year of the vehicle. Dave who used to be a good mechanic for Bob's car, might be less competent for Alice's if it is very different from Bob's car. Refining the context can lead to a more precise search [START_REF] Liu | Modeling Context Aware Dynamic Trust Using Hidden Markov Model[END_REF]. This example shows how the truster can construct his belief about the trustee using his past interactions and the word of mouth technique. It shows also the limit of this method for new users, and how a reputation based system can make more information available to them if they have no or less friends. Moreover, it demonstrate the important role of the context and the impact of its interpretation.

In the next section we discuss the formalization of social trust for the social web.

A. Computational trust

Computational trust is the formalization of social trust for computer science and its applications. It raised in the last decade to satisfy the needs of trust awareness in online applications. Computation trust has three axes [START_REF] Kwan | Trust and Online Reputation Systems[END_REF]:

• Quantitative, also called global-trust or Reputation:

where the system computes a score for each user, this score represents his global trustworthiness. This same score is considered when any other user needs to interact with this user [START_REF] Ziegler | Spreading Activation Models for Trust Propagation[END_REF].

• Qualitative, also called local-trust or relationship: it takes into account the personal bias. Represented as user to user relationship. It is the trustworthiness of a user Y from the point of view of only one user X. Some researchers call this local-trust [START_REF] Ziegler | Spreading Activation Models for Trust Propagation[END_REF].

• Process driven (system): it represents the trust of the users in the system. This kind of trust is not considered in this paper.

Many models were proposed [START_REF] Abdul-Rahman | Supporting Trust in Virtual Communities[END_REF], [START_REF] Krukow | Towards a Theory of Trust for the Global Ubiquitous Computer: A Dissertation Presented to the Faculty of Science of the University of Aarhus in Partial Fulfilment of the Requirements for the PhD Degree[END_REF], [START_REF] Mui | Computational Models of Trust and Reputation: Agents, Evolutionary Games, and Social Networks[END_REF] to model trust, they tend to formulate local trust problem within a trust network. A trust network is a directed weighted graph where vertices represent users and edges represent trust relationships. Models differentiate by their notation of edges and their strategies in traversing the network to compute trust between unconnected people, this operation is called trust propagation. As for global trust, it is usually presented by associating each user by a score that implies his reputation [START_REF] Kamvar | The Eigentrust Algorithm for Reputation Management in P2P Networks[END_REF], [START_REF] Levien | Attack resistant trust metrics[END_REF].

Subjective logic (SL) is a probabilistic model that was used to model local trust in [START_REF] Josang | Trust Network Analysis with Subjective Logic[END_REF]. It has many operators that allow it to integrate many aspects and factors of trust. In this work we use SL local trust model, and then we propose a new SL global trust model. The following section II-B is dedicated to explain the structure and some operators of subjective logic.

B. Subjective logic

Subjective logic (SL) [START_REF] Audun | Subjective logic[END_REF] is an extension of probabilistic logic, which associates each probability with a degree of uncertainty. Subjective logic allows to build models that treat with situations of incomplete evidences.

Belief theory [START_REF] Dempster | The DempsterShafer Calculus for Statisticians[END_REF], [START_REF]Advances in the Dempster-Shafer Theory of Evidence[END_REF] is a special case of probability theory dedicated to treat incomplete knowledge. The sum of probabilities of possible cases can be less than 1. Subjective logic [START_REF] Josang | A Logic for Uncertain Probabilities[END_REF] offers a belief calculus using a belief metrics called opinion. The opinion of an individual U about a statement x is denoted by: ω U x = (b, d, u, a) Where: b, d, u ∈ [0, 1] are respectively the belief, disbelief and uncertainty of U about x. The sum of the three values equals to one (i.e b + d + u = 1). Base rate a ∈ [0, 1] is the prior probability. Basically, base rate is a statistical measure applied in cases of evidences' absence. For example, when we know that the percentage of a disease x in a given population is 1%, then the base rate of x's infection is 1%. When we meet a new individual who did not make a test for the disease, priori we assume that the probability that he is infected is 1%. In social trust case, while no priori statistics are present, we consider that unknown person has a half chance to be trustworthy. So we use a base rate a = 0.5. In subjective logic, the base rate steers the contribution of the uncertainty in the computation of the probability expectation value according to the equation 1:

E(ω U x ) = b + a × u (1)
The opinion in subjective logic is based on the accumulation of successful and failed experiences. After each experience, U updates his opinion about x consistently with experience's outcome. According to this description, opinion can be represented as a binary random variable. Beta distribution is normally used to model the behavior of this kind of variables. By consequence, the opinion corresponds to the probability density function (PDF) of beta distribution. PDF is denoted by two evidence parameters α and β that can be written as functions of the number of successful and failed experiences respectively.

α = r + W × a β = s + W × (1 -a) (2)
Where r the number of successful experiences (evidences). s is the number of failed experiences. W is the noninformative prior weight which ensures that the prior (i.e. when r = s = 0) Beta PDF with default base rate a = 0.5 is a uniform PDF (normally W = 2).

The expectation value of beta PDF is:

E(Beta(p|α, β)) = α α + β = r + W a r + s + W (3)
In subjective logic, the mapping between the opinion parameters and the beta PDF parameters is given as follow: In the first line of table I we see the case of absence of evidences (experiences). The opinion is completely uncertain (u = 1). In this case, according to equation 1, the expectation value equals to the base rate value. The arrival of new experiences, will cause that the uncertainty decreases, regardless if these experiences are successful or failed. Successful experiences will augment the belief, whereas failed experiences will augment the disbelief.

b = r (r + s + W ) (4)
d = s (r + s + W ) (5)
u = W (r + s + W ) (6)
Subjective logic opinions can be illustrated in the interior of an equal-sided triangle. The three vertices of the triangle are called belief, disbelief, and uncertainty. The uncertainty axis links the uncertainty vertex with the opposite edge (the beliefdisbelief edge), the uncertainty value of the opinion is plotted on this axis considering that its contact with the edge beliefdisbelief represents the value 0, whereas the contact with the uncertainty vertex represents the value 1. In the same way we describe the belief and the disbelief axis.

The opinion is represented by the intersection point of the three projections on the three axis (belief, disbelief and certainty) is shown in the example in figure 2. The bottom of the triangle is the probability axis, the probability expectation value is the projection of the opinion point on the probability axis with respect to the line linking the uncertainty with the base rate point on the probability axis. Figure 2 illustrates an example of opinion mapping in subjective logic. The opinion is represented by a point inside the triangle. The point is the intersection of the projection of the three values b, d, and u on the axis of belief disbelief and uncertainty respectively. the probability expectation value E(x) is the projection of ω x on the probability axis directed by the axis linking a x with the uncertainty edge. algorithms propose transitivity operators. In [START_REF] Golbeck | Personalizing applications through integration of inferred trust values in semantic web-based social networks[END_REF], the inferred value is restrained by the value of trust between A and B. In [START_REF] Massa | Using trust in recommender systems: An experimental analysis[END_REF], it is inversely proportional to the distance between A and C.

Although trust transitivity has no mathematical evidences, but users generally tend to trust people who are trusted by their friends. Building a trust transitivity operator is much easier in "trust only" models. The complicated issue is when A

In this case, A can has one over two reactions: 1) A can consider that B has bad intentions towards him, so he will behave to the opposite of the opinion of B. 2) A can consider that B is just inept to argue about C, so he will neglect his opinion.

Subjective logic proposes two transitivity operators corresponding to two reactions, they are by order: Opposite belief favouring operator and uncertainty favouring operator.

Assume that the opinion of A about B and the opinion of B about C are given as follows:

ω A B = (b A B , d A B , u A B , a A B ) ω B C = (b B C , d B C , u B C , a B C )
Then the trust of A in C can be inferred by the opposite belief favouring operator as follows:

ω A B ⊗ ω B C =        b A:B C = b A B .b B C + d A B .d B C d A:B C = b A B .d B C + d A B .b B C u A:B C = u A B + (b A B + d A B ).u B C a A:B C = a B C ( 7
)
or by the uncertainty favouring operator:

ω A B ⊗ ω B C =        b A:B C = b A B .b B C d A:B C = b A B .d B C u A:B C = d A B + u A B + b A B .u B C a A:B C = a B C (8)
In this work, while the used dataset a priori does not contain attackers or malicious users, we consider that distrust relations are mostly driven by incompetence rather than bad intentions, that is why in the rest of this paper we use uncertainty favouring operator for trust transitivity.

ω C B ⊕ω C D =          b C B⋄D = b C B .u C D +b C D .u C B u C B +u C D -u C B .u C D d C B⋄D = d C B .u C D +d C D .u C B u C B +u C D -u C B .u C D u C B⋄D = u C B .u C D u C B +u C D -u C B .u C D (9)
Even if the opinions of B and D were contradictory, the operator can still cumulate their evidences to generate an unique opinion based on them.

III. PROPOSED MODELS

The aim of our models is to predict the most relevant answer to a given question within a list of answers. We employ two types of trust aware models that propose two different interpretation of context. The first (LTSL) is based on the local trust, and the second (GTSL) is based on the global trust. Both models use subjective logic.

A. Local trust subjective logic (LTSL)

This model is originally proposed in [START_REF] Josang | Trust Network Analysis with Subjective Logic[END_REF]. To the best of our knowledge it was never applied to real data. It consists in building a local trust network between users. The edges of this network are SL opinions of users about each other. Whenever a user A accepts the answer of user B to his question, the opinion of A in B is updated by adding a new successful interaction between them.

In stackoverflow, A can accept only one reply out of the list of available answers. Unaccepted answers are not necessarily bad ones. They might be simply not good enough compared to the accepted one. They even might be better but arrived too late that A has already accepted another satisfactory answer. Basically, while we do not have an explicit reaction from A towards the unaccepted answers, we suppose four hypotheses to treat them: 1) rigorous hypothesis: unaccepted answers are considered as failed interactions. 2) ignoring hypothesis: unaccepted answers are not considered at all. 3) independent subjective hypothesis: In both precedent methods, the interaction value is either +1 (successful) , or -1 (failed). In this method we introduce relatively successful/failed interactions. We use the rates of community towards the answer to estimate a subjective successful/failure of the interaction. In fact, the thumb-up represents a successful interaction with an unknown user, same thing for the thumb-down with a failed interaction. The global reaction of the community towards the answer is subjective opinion resulting from members' interactions with the answer. We consider the expectation value of the community's opinion as the value of the partially successful/failure of the interaction between the asker and the replier. 4) dependent subjective hypothesis: regarding to the fact that a user can give a thumb-up for an answers because it is better/worse than others, the attribution of thumb-up and thumb-down can be relative too. The reason why we propose another subjective method where our certainty is influenced by the global number of thumb-up and thumb-down attributed to all answers of the same question. In this case the opinion about an answer is dependent on the the other opinions about the other answers.

Certainty j = j th 2 + ann i=an0 i th
Where th is an absolute value of thumb (up or down). j is the current answer. n is the number of answers of the current question.

U+ncertainty is the complement of certainty to 1:

uncertainty j = 1 -certainty j
The default non-informative prior weight W is normally defined as W = 2 because it produces a uniform Beta PDF in case of default base rate a = 1/2. The three components of the opinion are: belief j = uncertainty j × j th up j th Where j th up is the number of thumbs up attributed to the answer. disbelief j = certainty j × j th down j th Where j th down is the number of thumbs down attributed to the answer. Finally the computes the expectation value of the resulting opinion and consider it as the value of the relative success/failure interaction.

To predict the accepted answer of a given question Q asked by the user A, we identify R the set of users who contributed answers to the current question. Then, we traverse the graph (trust network) to compute the local trust between the owner of the question and each of them. We assume that A will accept the answer of the most trustee user within R.

B. Contextual global trust model (GTSL)

Each question in stackoverflow has a set of associated keywords. We use these keywords to build a new global trust model. that considers the reputation of users towards keywords. When a user A accepts the answer of a user B to his question, a link is created or updated between B and each one of the keywords associated to the question. As for unaccepted answers we apply the same four hypothesis in III-A. The semantic signification of the links between users and keywords is the reputation of the user towards the keyword. A reputed user towards a keyword can also be called expert.

To predict the accepted answer of a given question Q asked by the user A, we identify R the set of users who contributed answers to the current question, and the set K of keywords associated to the question. We compute the average reputation score to each member of R towards the elements of K. The member with the highest average score is chosen to be the owner of the accepted answer.

IV. RELATED WORK

Computational trust is applied to many fields in artificial intelligence, recommender systems, file sharing, Spam detection, networks security ...etc. Most computational models are not completely loyal to the social trust, they are fitted to their application fields and context. Our choice of the trust model (SL) is motivated by its high faithfulness to the social trust. To the best of our knowledge, SL is usually employed in local trust networks, but its flexibility allowed us to build our contextual global trust model. In addition to its capacity to work in environment with lack of evidences like ours.

In [START_REF] Kamvar | The Eigentrust Algorithm for Reputation Management in P2P Networks[END_REF] a global trust model used to improve the confidence in a file sharing network, it considers trust as a limited quantity by person, so the more he trusts people the less he can attribute trust to each of them. Another older model in [START_REF] Levien | Attack resistant trust metrics[END_REF] used to detect malicious attacks in a developers social network, it uses a global trust metrics which can not be contextualized, and is not prepared to evidences' lack environment. Appleseed [START_REF] Ziegler | Spreading Activation Models for Trust Propagation[END_REF], tidaltrust [START_REF] Golbeck | Computing and Applying Trust in Web-based Social Networks[END_REF] and Moletrust [START_REF] Massa | Using trust in recommender systems: An experimental analysis[END_REF] are local trust models. They are applied in recommendation contexts. They deal only with positive values of trust, so they do not take the distrust into account. Moletrust and tidaltrust employ different methods to traverse the graph between a source user (truster) and a destination user (trustee). They look for the shortest path that maximizes the trust between the two users. Subjective logic proposes a different strategy, it allows all truster's friends to contribute their opinions about the destination, and then aggregates these opinions regarding the certainty of each friend towards his opinion. If a friend of the truster has no opinion towards the trustee, he will ask his friends in turn and so on. So the most important measure in SL is not the distance from the truster but the certainty of opinion.

Model in [START_REF] Richardson | Trust Management for the Semantic Web[END_REF] is used to enhance the relevance of information on the web but also using only positive trust. Other models that consider only trust exist in [START_REF] Zaihrayeu | IWTrust: Improving User Trust in Answers from the Web[END_REF], [START_REF] Falcone | A Fuzzy Approach to a Belief-based Trust Computation[END_REF], [START_REF] Almenrez | PTM: A Pervasive Trust Management Model for Dynamic Open Environments[END_REF], [START_REF] Tang | Managing Trust in Peerto-Peer Networks[END_REF].

Authors in [START_REF] Odonovan | Trust in Recommender Systems[END_REF] proposes a model based on enhancing the collaborative filtering algorithm by associating a global trust score to each user, the score is based on the success of the recommendations in which he was involved. This score represents the usability of the user for the system. Subjective logic considers trust and distrust relationships. Trust relationships in SL are based on accumulation interactions. It is able to aggregate the recommendation of many friends. It possesses numerous operators that allow it to be adaptable for different visions about trust.

Although most definitions of social trust accord the importance of the context, in most model, context is missed during the conception, or integrated as a peripheral element. In the following section we compare the performance of local trust subjective logic network to a reference network based on a shortest path method (Moletrust), then we compare them with the contextual global trust model.

V. EXPERIMENTAL WORK

We use the dataset of the website stackoverflow. The website offers a question answering forums for multiple domains, mainly but not limited to computer science. The available data contains 30 domains. Users subscribe to the website by domain, so one user can have multiple accounts, according to the number of domains in which he participates. The total number of accounts is 374,008 for about 153,000 users.

User asks a question in a given domain, and associates a set of keywords to his question, then he receives many answers. He chooses the most relevant answer to him and attributes an "accepted answer" label to it. Nevertheless, users can keep proposing new answers. Subsequent users who have the same problem as the asker can profit of answers and rate them on their usefulness by attributing thumb-up or thumb-down. In the available dataset, we have access to only the total number of thumbs-up and total number of thumbs-down an answer has, but no information about suppliers' identities. The website, offers the possibility to order answers by relevance, where the accepted answer is put in the top of the list, followed by the other answers ordered by the difference between thumbs-up count and thumbs-down count. Our work aims to use trust based models to predict the accepted answer over the set of available answers. Total number of questions in current dataset equals to 371,594, for a total number of answers 816,487. We divide the questions of each domain in five equivalent sets. Then, we apply a crossing test in five iterations, in each iteration we use four sets for learning and building the trust network and the fifth for testing the prediction quality.

A. Evaluation

While both proposed methods are based on subjective logic, we would like to compare them to a referential trust method. To the opposite to its matches, Moletrust algorithm considers the expression of trust as a binary value, and user can only expresses positive trust. This is compatible with the explicit part of the dataset, while the users can only accept answers by binary positive notation. Moletrust is a shortest path trust method, showed efficiency in another application context [START_REF] Massa | Trust-aware Collaborative Filtering for Recommender Systems. On the Move to Meaningful Internet Systems[END_REF], [START_REF] Haydar | Hybridising collaborative filtering and trust-aware recommender systems[END_REF]. We use it in our application as a base reference to evaluate the performance of SL methods.

1) Moletrust: Moletrust was presented in {massa04. It considers that each user has a domain of trust, where he adds his trustee friends to. User can either fully trust other user or not trust him at all. The model considers that trust is partially transitive, so its value decline according to the distance between the source user and the destination user. The only initializing parameter is the maximal propagation distance d.

If user A added user to his domain, and B added C, then the trust of A in C is given by the equation:

T r(A, C) = (d-n+1) d if n ≤ d 0 if n > d ( 10
)
Where n is the distance between A and C (n = 2 as there two steps between them; first step from A to B, and the second from B to C). d is the maximal propagation distance.

Consider d = 4 then: T r(A, C) = (4 -2 + 1)/4 = 0.75.

We consider that when a user A accepts an answer of another user B, that A trust B. A Moletrust link between both users is created. While the algorithm is not aware to distrust so no interpretation exists for unaccepted answers.

2) Evaluation Metrics:

We regard the problem of finding the accepted answer as a list ranking problem with one relevant item. Mean reciprocal rank (MRR) is a quality metrics used to evaluate systems that have to give out a ranked list with only one relevant item. Reciprocal rank (RR) of question is 1/r where r is the rank given by the evaluated algorithm to the accepted answer. Mean reciprocal rank is the mean value of RR's to all questions. The value of this metrics varies between 0 and 1, where 1 is the best precision score.

MRR is a good indicator to the performance of prediction algorithms for ranked lists. Nevertheless, we think that it is not perfectly adapted to our case. MRR is usually employed for systems that have to predict a list of items within the which a relevant item exists. We are trying to find the accepted answer by reranking an existing list of answers. Remark the case when the algorithm ranks the relevant item in the last position of the list, the algorithm is recompensed for at least having chosen the item within the list. In our case the list predefined, so the algorithm should not be recompensed for ranking the relevant item at the end of the list. The range of RR values is [1/r, 1], we propose a modified version where the value varies between 1 if the relevant item is in the top of the list, and 0 if it is at the end of the list. We call this metrics mean predefined lists rank(MPLR), where PLR is given by the formula:

P LR = N -r N - 1
Where: N is the size of the list.

We employ a modified competition ranking strategy, so the ranking gap is left before equal items. Example if two items on the top of the list have the same score, the are considered both second, and no item is put in the first rank.

VI. RESULTS AND DISCUSSIONS

Over the 371,594 available questions in the corpus only 118,778 have more than one answer and have an accepted answers. Only these questions are suitable to apply our test. Obviously, subjective logic models surpass Moletrust when applied in the same conditions (ignoring hypothesis). This is in the first place because the power of the probabilistic base of SL, and its capacity to accumulate interactions, whereas Moletrust considers one interaction sufficient to establish an absolute trust relation. In the second place this shows that the strategy of shortest path is not always the efficient one. Even though, the flexibility of subjective logic allowed to slightly improve the scores by using the three other hypothesis. Local trust models increases its score about 4% thanks to the probabilistic hypothises, and the global trust models increases between 7% and 14% with other hypothises.

It is also obvious that GTSL surpasses widely LTSL. LTSL suffers from a cold start problem, it is unable to predict answers to users who has no or less friends. In current dataset, about 20% of profiles (74,163 over 374,008), have asked exactly one question each. 14% of the 118,778 questions included in our test are generated by these profiles. LTSL can not predict answers to questions generated by such isolated profiles. GTSL can predict answers to these users. Basically, the truster in LTSL builds his belief by exploiting his own interactions, and those of his friends and their friends. GLSL offers a larger archive of interactions to the trusters. Truster in GLSL can has access to all the past interactions of the trustee, so construct a more elaborated belief about him.

Local trust SL model considers the domain of the question as a context. Global trust model considers a more refined interpretation of the context, based on a sub-domain defined by the tags associated to the question. The difference in both models scores shows that trust is very sensible to the context. The context in global trust model is very adaptive, this leads to a more specific person having competences in this exact context. The presence of this person in the list of people who answered the question proves his willingness to assist the asker, his competence and mastery of subject lead him to be the owner of the accepted answer. Malicious attackers who might supply answers for bad intentions will be automatically rejected or classed in the bottom of the list, because of their weak global trust score. On the other hand, context in the local trust model is more fuzzy. In real life if B was able to answer a question of A about Java programming language, this does not mean that he would be able the next time to reply to a question about C++ programming language, although it is still the same domain (context) for the local trust model. So even within the same domain, people might be experts in narrow sub-domains, while having a general or even weak knowledge about the other parts of the domain.

Our results stand up for a superiority of global trust model and its interpretation of the context, and a superiority of subjective logic models over Moletrust. We mentioned that SL models improve their scores by means of the hypothesis to interpret the implicit data, but both models are influenced differently by those hypothesis. In local trust model, the probabilistic hypothesis slightly surpass the score of the other hypothesis, because they enrich the trust network by more interactions between users. On the other hand, the global trust model achieves its best score with the rigorous hypothesis because it allows to be more strict while appointing the experts.

VII. CONCLUSION AND FUTURE WORKS

As we argued in the beginning, trust is affected by many factors including context. This work shows the efficiency and the adaptability of subjective logic, but it is also dedicated to explain the influence of the context on trust models' performance. We would like to make use of the flexibility of SL to study other factors that affect the trust such as the temporality: does a recent interaction has the same importance as an old one?. Our actual models consider only direct interactions, other incremental models update links after each successful/failed recommendation. We would like to study the impact of these recommendation interactions.

Fig. 1 .

 1 Fig. 1. Trust network

Fig. 2 .

 2 Fig. 2. Opinion

2 )

 2 Opinion fusion: Suppose in the previous example that A has another trustee friend D how also trusts C. A has two separate sources of information about C. This operator allows to aggregate the opinions of two users (B and D) about a third user C. Its idea is based on cumulating evidences about C from both B and D.

Table I

 I shows an example of the evolution of an opinion with successive interactions.

	No		state	r	s	belief disbelief	uncertainty
	0		no interaction	0 0	0	0	1
	1	successful interaction	1 0	1/3	0	2/3
	2		failed interaction	1 1	1/4	1/4	2/4
	3	successful interaction	2 1	2/5	1/5	2/5
	TABLE I.	OPINION EVOLUTION WITH SUCCESSIVE INTERACTIONS

Table

  II illustrates the MRR scores of the three models, and table III illustrates MPLR scores. MPLR scores are lower than those of MRR. Nevertheless both tables lead to the same conclusions.

http://www.stackoverflow.com