Thi Thuy

Nga Nguyen

Olivier Brun
email: brun@laas.fr

Balakrishna J Prabhu
email: balakrishna.prabhu@laas.fr

T T Nga Nguyen

Using channel predictions for improved proportional-fair utility for vehicular users

come

Using channel predictions for improved proportional-fair utility for vehicular users

Introduction

A central and challenging problem in cellular networks is channel allocation, that is, to decide which mobile user the base station (BS) should serve in each time slot. To this end, the BS gathers the channel state information (CSI) from users in order to know their radio conditions, which are mainly determined by their distances to the BS and by fading effects. As maximizing the overall throughput would lead to the starvation of distant users (those with the worst potential data rates), today cellular networks allocate the channel to the user with the highest potential rate proportionally to its time-average throughput 1 . With this strategy, users with comparatively low allocated throughput are occasionally assigned a higher priority even when they are in worse channel conditions. This scheduling algorithm, which is known as the Proportional Fair (PF) scheduler, provides a fair and efficient sharing of bandwidth between users in the sense that it maximizes the aggregate logarithmic utility of obtained throughput in a fixed population of permanent users [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF].

A number of studies have been devoted to the analysis of the performance of PF scheduling in wireless networks [START_REF] Borst | User-level performance of channel-aware scheduling algorithms in wireless data networks[END_REF][START_REF] Tan | Utility maximization resource allocation in wireless networks: Methods and algorithms[END_REF][START_REF] Borst | Mobility-driven scheduling in wireless networks[END_REF][START_REF] Yi | Stochastic network utility maximisation-a tribute to kelly's paper published in this journal a decade ago[END_REF][START_REF] Zhou | Global proportional fair scheduling for networks with multiple base stations[END_REF][START_REF] Chandur | Performance evaluation of scheduling algorithms for mobile wimax networks[END_REF], assuming either a static population of permanent users, or a dynamic setting in which random finite-size data transfers come and go over time. In both cases, it was shown that PF scheduling strikes a good balance between the overall network throughput and the degree of fairness among users. In contrast to the above references, where it is assumed that the transmit powers of BSs cannot be varied over time, some authors have considered the joint optimization of channel allocation and transmit power control. This problem has been investigated for different multiplexing schemes such as CDMA [START_REF] Vijay | Joint scheduling and resource allocation in CDMA systems[END_REF] and OFDM [START_REF] Huang | Downlink scheduling and resource allocation for ofdm systems[END_REF]. The proposed algorithms base their decisions on the current channel conditions and on previous decisions.

However, most of the literature is based on the assumption that users experience stationary channel conditions. This was partly motivated by the fact that a simple index-based allocation algorithm had been shown to be optimal for stationary channels [START_REF] Kushner | Convergence of proportional-fair sharing algorithms under general conditions[END_REF]. Thus, even if they take into account the fast channel variations due to multi-path propagation, most studies ignore the variations of the channel conditions on slower time scale dues to user mobility. Taking into account such slow fading effects is particularly important for vehicular users as the mean of the Signal-to-noise ratio (SNR) improves as a vehicle comes closer to a BS and then worsens as it moves far away. Another usual assumption which is not realistic for vehicular users is the assumption of long sojourn time. Indeed, a vehicle typically stays in the scheduling area of a BS for only a few minutes.

In this article, we investigate to which extent the quality of channel allocation could be improved by exploiting information on future radio conditions in nonstationary environments. Our main motivation comes from connected vehicles which will use cellular networks to exchange information related to security and driving conditions with their environment. If the trajectory of a car is known or can be estimated from historical travel data and/or observations of the surrounding environment, then one can obtain good statistical predictions of the SNR that will be experienced by the car in the near future. In turn, these predictions could be used by the BSs to achieve a channel allocation with a higher utility than that of the PF algorithm. In this paper, we propose a channel allocation policy exploiting this extra knowledge and evaluate the improvement in utility that it yields in non-stationary environments. Note that such an improvement in utility is not possible under the assumption of a stationary channel as knowing the users' trajectory does not bring any new information on the future data rates, since users are static and hence their trajectory is just one point. We also show how to extend the proposed scheduling policy to address a joint channel allocation and transmit power control problem in which there are average and power constraints on the base-stations.

The idea of using information on future radio conditions for channel allocation was already explored in [START_REF] Bang | Channel predictive proportional fair scheduling[END_REF]. It uses future information by looking at channel state of users in a few small time-slots. Different from their approach, we do not look at the predicted channel state in few time slots which may be different between users and difficult to predict correctly due to fast fading. Instead, we base our allocation on average rate the user will experience during the time interval this user stays inside the coverage range of the BS. In the context of high-speed trains, [START_REF] Xu | Utility-based resource allocation in high-speed railway wireless networks[END_REF] solves the opportunistic utility maximization problem assuming all the future rates are perfectly known and with average power constraints.

Another closely related work is [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF] in which, using SNR maps obtained by measurements, the authors first show that PF scheduling may perform poorly in the presence of slow fading. They then propose a scheduling algorithm which is similar to PF in that the channel is allocated to the user with the highest potential rate proportionally to its total throughput. This new algorithm, which is called (PF) 2 S differs however from PF in that the total throughput includes an estimation of the future throughput whereas PF considers only the already allocated throughput. In order to estimate the future throughput, the authors proposed three methods: round-robin, blind estimation, and a local search heuristic. It was shown that even with a rough estimation of the future throughput, this new index leads to an improved utility compared to the PF algorithm in non-stationary environments. The channel allocation policy proposed in this paper is similar to the (PF) 2 S scheduling policy except that we use a different method for estimating future throughputs of vehicles. For the purposes of numerical comparisons, we shall assume in this paper that (PF) 2 S uses the round-robin policy. It was stated in [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF] that, out of the three estimation methods, round-robin is the most robust to prediction errors.

Contributions

We first consider the case when the transmit powers of BSs cannot be varied over time. We present two heuristic algorithms for non stationary channels that improve the total utility of users compared to the PF and the (PF) 2 S algorithms. Our heuristics are similar to the (PF) 2 S algorithm, except that instead of computing an estimation of future throughput from a round-robin allocation, we compute it as the solution of a utility maximization problem over a short-term horizon assuming that the means of the future data rates are known over this short horizon. The two heuristics differ in the frequency at which they recompute future allocations.

The original utility maximization problem being computationally complex, we employ three techniques to obtain lower complexity heuristics: (i) we relax the integer constraints of the original problem; (ii), we shorten the time horizon over which the problem is solved; and (iii) we compute the solution over macroscopic time slots instead of microscopic ones that helps the algorithm run in real time. The relaxation turns the problem into a convex one and allows for its efficient resolution. Shortening of the time horizon and solving over macroscopic slots reduces the number of variables in the problem and decreases the computation time.

When the transmit powers of the BSs can be varied over time, a straightforward extension of our heuristics can be used for the joint optimization of channel allocation and transmit power control under average and maximum power constraints.

We compare the performance of the proposed algorithms against those of other channel allocation algorithms using event driven simulations. The simulated scenarios include scenarios with multiple base stations and are based on realistic mobility traces generated using the open-source road traffic simulator SUMO with vehicles moving at either equal or different speeds. Simulation results show that the proposed algorithms outperform other algorithms and that exploiting the knowledge of future radio conditions allows a significantly better channel allocation. Some of the results presented in this paper appeared in ASMTA 2019 [START_REF] Nguyen | An algorithm for improved proportional-fair utility for vehicular users[END_REF] and RAWNET 2020 [START_REF] Thuy | Joint downlink power control and channel allocation based on a partial view of future channel conditions[END_REF]. These publications were limited to scheduling in a single base station setting and do not include experiments with SUMO.

Organisation

In Section 2, we state the channel allocation problem addressed in this paper. Section 3 briefly describes some existing channel allocation algorithms, which shall be used for comparison purposes. In Section 4, we present two different heuristics for improving the proportional fairness between vehicular users. Section 5 is devoted to the extension of our heuristics for the joint optimization of channel allocation and power control. Section 6 presents the numerical results for some simple scenarios with homogeneous vehicles, as well as for some more advanced scenarios generated with SUMO. Finally, Section 7 summarizes our findings and discusses some future research directions.

Problem formulation

We consider a geographical region with a network of roads that is served by a set B = {1, . . . , B} of BSs. The region is partitioned into B non-overlapping sub-regions, one for each BS. The sub-region assigned to a BS corresponds to the area in which this BS has a better average SINR that the other BSs as given by their SINR maps. We will call the sub-region of a BS as the scheduling area of this BS. This reflects the fact that users in the scheduling area of a BS are assigned to this BS which is responsible for the scheduling decisions for the users that are present there. The scheduling area is in fact a subset of the coverage area of a BS which is the area over which an acceptable signal is received from this BS. See Figure 1b illustrating the difference between the two. The SINR maps could in general vary over time and need not be symmetric. The scheduling area can be updated to reflect the temporal variations.

Users (vehicles, bicycles, pedestrians, etc) enter the network, move along different routes, and leave the network. In the following, we shall denote by U(t) the set of users in the system at time t. Figure 1a shows an area within the city of Toulouse which will be later used in the numerical experiments. In the figure, the width of the box is approximately 1 km, and the height is around 0.65 km. The data for BS location can be found on the website2 of the French Frequency Agency (ANFR), which manages all radio frequencies in France.

Every δ = 2 ms each BS has to decide which user to serve in a decentralized fashion. Here, we are assuming that there is one resource (channel, in this case) that a BS can allocate in each slot to the users in its scheduling area. In practice, there can be multiple channels and the ideas presented in this paper can be applied to this case as well. Throughout the paper, we shall also assume that a user can only be served by the closest BS. We define U b (t) as the subset of users that are attached to BS b at time t, and x i (t) as a binary decision variable which is equal to 1 if the channel of BS b is allocated to user i ∈ U b (t) at that time, and 0 otherwise.

The allocation decisions of the BSs are based on the channel conditions of the users. In time slot t, user i ∈ U b (t) has a potential data rate of r i (t) if it is allocated the channel of BS b. In the numerical experiments (see Section 6), when the user is at distance d from the BS, r i (t) will have the form

r i (t) = η i (t) • r (d) , (1)
where η i (t) is a random variable that models time-varying SNR and r (d) is the average data rate which depends on the distance d. More precisely, we assume that

r(d) = 0 if d > d max , 1 + κ e -d/σ otherwise, (2)
where κ and σ are adjustable parameters and d max is a given number standing for the scheduling area of the BS. We emphasize that the scheduling algorithms proposed in this paper do not require this assumption to work. With the above definitions, the throughput of user i at time t can then be defined as

φ i (t) = x i (t) × r i (t), (3)
which means that the throughput is 0 if the channel of the serving BS is not allocated to user i, and that it is equal to the potential data rate r i (t) otherwise. Denote by T the time horizon over which the scheduling decisions need to be determined, and let K be total number of users who pass through the considered region during that time. For simplicity, we assume that T is a multiple of δ. Our objective is to achieve the proportional-fairness between users, which is described by the following optimization problem (see, e.g., [START_REF] Borst | User-level performance of channel-aware scheduling algorithms in wireless data networks[END_REF][START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF][START_REF] Abou-Zeid | Long-term fairness in multicell networks using rate predictions[END_REF]):

                 maximize U (x) = K i=1 log 1 T T t=1 φ i (t) s.t. i∈U b (t) x i (t) = 1, b ∈ B, t = 1, . . . , T, x i (t) ∈ {0, 1}, i ∈ U b (t), b ∈ B, t = 1, . . . , T. (I)
The objective function is the sum of the logarithm of the mean throughputs of the users. Constraints i∈U b (t) x i (t) = 1 imply that each BS serves exactly one user at each time t. Finally, the last constraints x i (t) ∈ {0, 1} imply that a feasible solution is a binary vector x.

Solving the optimization problem (I) presents several practical difficulties. First and foremost, in time-slot t, the potential data rates r i (k) in the future (i.e., for k > t) are unknown. Thus, the channel allocation has to be done online with the knowledge of the past allocations and the current potential data rates only. The other difficulty is computational due to (I) being NP-hard [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF].

Apart from the algorithm in [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF], the existing algorithms for channel allocation base their decisions only on the past and current information. It was shown in [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF] that by including an estimate of future data rates, the global utility can be improved. We shall present two algorithms in Section 4 that further improve upon the gains shown in [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF].

Existing Algorithms

Before introducing our algorithms, we first present three existing channel allocation algorithms that will also be used for comparison in our numerical experiments.

Greedy allocation

The simplest channel allocation scheme is the greedy algorithm in which the BS allocates the channel to the user with maximum current potential rate, that is, in time-slot t, BS b allocates its channel to a user i * b ∈ argmax i∈U b (t) {r i (t)}. This algorithm does not use information on the past allocations and greedily maximizes the utility for the local allocation only. In scenarios where users spend similar amounts of time close to a BS (that is, have good channel conditions), greedy can perform well. On the other hand, when these times can vary a lot between users, it can lead to unbalanced allocations and possibly starvation to users who spend more time in poor channel conditions. Moreover, greedy allocation can be sporadic from a user's point of view. A user who is moving away from a BS may have to wait until it gets close to the next BS before it get a new allocation. This may lead to short-term unfairness or starvation.

Proportional Fair (PF) allocation

The PF-EXP algorithm, versions of which are implemented in cellular networks, improves the fairness by taking into account not only the current potential rate but also the previous allocations. It chooses the user with the highest ratio of the current rate to the observed throughput, that is, BS b chooses the user i ∈ U b (t) who maximizes the ratio r i (t)/A i (t -1), where

A i (t) = A i (0) + t k=1 φ i (k),
is the total allocated rate to user i up to time t (A i (0) is the initial value for each user). The algorithm takes into account the past allocation but ignoring completely the future one. A nice property that makes this algorithm attractive is that, in the long-run when T goes to ∞, it is optimal for a stationary and ergodic channels and for a fixed number of users [START_REF] Kushner | Convergence of proportional-fair sharing algorithms under general conditions[END_REF].

In [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF], it was shown using measurements that the potential data rates for vehicular traffic are not necessarily stationary. The mean potential data rate can vary along a road segment as a vehicle gets close or moves away from the BS. The non-stationarity of potential data rate means that PF-EXP may no longer be optimal which opens up the possibility to use future information for improving the global utility. The exact future rate is of course unknown but current allocation can be based on predictions made using SNR maps.

Predictive Finite-horizon PF Scheduling ((PF) 2 S)

Based on the observation of non-stationarity, in [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF], the authors proposed a modified PF algorithm that exploits estimated future rate. This algorithm works as follows:

• It predicts future data rates ri (s) of cars in every future slot s = t + 1, t + 2, . . ., T.

• It estimates future channel allocations x based on the data rate predictions. As mentioned in Section 1, the estimations can be computed using either a round-robin policy, a blind estimation, or a local-search method.

It is stated in [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF] that, out of these three, round-robin is more robust to prediction errors. Given this, we shall use Round Robin Estimation (RRE) as the estimation policy for (PF) 2 S in the numerical comparisons. As a reminder, RRE assumes that future time slots are allocated in a round-robin manner.

• For each time slot t, the BS b chooses the user i ∈ U b (t) who maximizes M i (t), where

M i (t) = r i (t) A i (t -1) + xi (t)r i (t) + T k=t+1 xi (k)r i (k) . (4)
(PF) 2 S is also an index-based algorithm like PF-EXP. The main difference between the two is that, while PF-EXP takes into account only the past rates in the denominator, (PF) 2 S also includes the estimated future allocations. It can be seen that ( 4) is related to the gradient of (I) with future rates replaced by their estimates, and choosing the user with maximal M i (t) can be seen as choosing a step in the direction of the maximal gradient. In the case of one BS, provided the future channel allocations x can be predicted correctly, an optimal solution to problem (I) can be obtained, as stated in Proposition 1.

Proposition 1. If there exists x * satisfying x * i(t) (t) = 1 and x * i (t) = 0, ∀i = i(t), where i(t) belongs to arg max i∈U b (t) r i (t) T k=1 x * i (k)r i (k) , (5)
for all t, then x * is an optimal solution of problem (I).

Proof. See B.2.

Note that condition (5) is a sufficient condition for x * to be an optimal solution of problem (I), but not a necessary condition and x * whose components are integers does not always exist. In chapter 5 of [START_REF] Thuy | Proportional-Fair Scheduling of Mobile Users based on a Partial View of Future Channel Conditions[END_REF], we discussed more detail about other properties of this optimization problem and it's solution. Moreover, in proposition of 5.5.5 of that reference, when |U b (t)| = 1, T = 2, K = 2, we solved and illustrated the solutions of the relaxed version which will be defined later in (II).

In the next section, we present our heuristics. The motivation for the heuristics comes from the observation that the formula (4) for (PF) 2 S looks like onestep of the gradient descent with starting point chosen according to the round robin policy when the RRE is used. We may expect to get a better allocation if we do more iterations instead of only one, ensuring that in every iteration the allocation is in the feasible set. To do this we employ a projected gradient algorithm, as described in the next section.

Channel allocation heuristics

We shall assume that each BS allocates the channel independently, that is, in a decentralized manner and without coordination with the other BSs. The channel allocation is done by a BS by taking into account the future data rates of the users currently attached to this BS. Since each BS decides independently, we consider an arbitrary BS, say BS b.

We propose two heuristic algorithms, Short Term Objective 1 (STO1) and Short Term Objective 2 (STO2), which are presented in the following. As explained below, the two heuristics use a different method for estimating the future throughput than the round-robin scheme used in the (PF) 2 S algorithm. This estimate is based on maximizing the total utility with the future mean channel gains as an estimate for the actual realizations. This is similar in spirit to Stochastic Model Predictive Control [START_REF] Mesbah | Stochastic model predictive control: An overview and perspectives for future research[END_REF]. The two heuristics differ in the timescale at which updated future information is used as well as in the dimension of the optimization problem solved at each decision epoch.

Projected gradient algorithm

Before describing the two heuristics, we explain the ideas common to them. The first step is to relax the integer constraints on the allocation variables in optimization problem (I), so as to obtain the following convex optimization problem

             maximize U (x) = K i=1 log 1 T T t=1 φ i (t) s. t. i∈U b (t) x i (t) = 1, t = 1, . . . , T, x i (t) ∈ [0, 1], i ∈ U b (t), t = 1, . . . , T, (II)
where K is total number of users passing BS b during T. The relaxed problem (II) is almost the same as the original problem, except the fact that now x i (t) does not need to be an integer. Let us assume for the moment that all the future arrivals are known. Under this assumption, (II) can be solved efficiently using the projected-gradient algorithm based on the formula for the projection on a simplex given in [START_REF] Condat | Fast projection onto the simplex and the l1 ball[END_REF], as described below. Let us denote by

D =    x ∈ [0, 1] K(t)×T : K(t) i=1 x i (t) = 1, t = 1, 2, ..., T    the feasible set of the relaxed problem (II) with K(t) = |U b (t)|.
Observe that although D is not a simplex, it is the Cartesian product of T simplexes since for every component t = 1, 2, . . . , T the feasible set of allocations is indeed a simplex (see details in A). We can therefore obtain a projection on D by projecting independently on the simplexes corresponding to each of the time-steps. The procedure for computing the projection Π D on the set D is formalized in A.

In the following, we present the projected gradient algorithm. Starting by initializing an arbitrary x (0) in the feasible set D, the algorithm computes at each iteration n = 1, 2, . . . a new feasible solution using the formula

x (n+1) = Π D x (n) + n ∇U (x (n) ) , (6)
where ∇U (x) is the gradient of the utility function at point x and n ∈ (0, 1) is the step size at iteration n. A new feasible solution is computed until convergence is reached. We have however limited the number of iterations to 20 in the numerical results presented in Section 6. Proposition 2 below states that if the iteration (6) converges, then the resulting allocation is optimal. In this proposition, we use the notation ∇U (x, ) := Π D (x + ∇U (x)) -x. Proposition 2. If x * ∈ D and if there exists an ∈ (0, 1) such that ∇U (x * , ) = 0, then x * is an optimal allocation of the relaxed problem (II).

Proof. See B.1.

Solving (II) using the projected gradient algorithm (6) requires the knowledge of all the future arrivals which may not be available. Further, the horizon T could be potentially large (tens of minutes giving roughly of the order of 300, 000 small-slots). This means the BS will have to solve a very high dimensional problem every 2 ms.

For the heuristics, we circumvent these two issues as follows. First, we solve (II) only for cars that are actually present in the coverage range and ignore the future arrivals. Second, we reduce the computational complexity in two ways: (i) we solve the problem over a shorter horizon; and (ii) we compute the future allocations on a larger time-scale rather than the short time-scale of channel allocation slots δ, which is usually in the order of a few milliseconds. The distance travelled in δ ms by a vehicle is typically too small to observe large changes in the mean channel conditions. Therefore, we define the notion of a big-slot over which there is noticeable change in the mean channel conditions. For example, a big-slot can be 500 × δ, giving a value of 1 second for the big-slot when δ = 2 ms. The exact value of a big-slot is an adjustable parameter that can be set by the system designer.

Next, we describe the two heuristics.

Short term objective algorithm (STO1)

Let ∆ be the size of the big-slot in absolute time units and let m = ∆/δ be the number of small-slots in a big-slot. If ri (t) is the average rate in slot t for user i, then ρi (τ ) = τ m t=(τ -1)m+1 ri (t) is the total average data rate that user i will get in big-slot τ if it is allocated in τ . Define xi (τ ) to be the allocation of user i in future big-slot τ . These allocations can be interpreted as the fraction of small-slots that user i will be allocated in the big-slot τ .

The STO1 heuristic works in two steps. At each small-slot t, it first solves the allocation for the current small-slot and the future big-slots. In the second step, it allocates the channel to the user with the largest fractional allocation for the current slot. These steps are described below:

• Step 1-In each small-slot t, solve the following optimization problem over a short-term horizon of J big-slots using the projected gradient algorithm as described above:

                       maximize i∈U b (t) log A i (t -1) + x i (t)r i (t) + τ +J-1 τ =τ xi (τ )ρ i (τ ) s.t. i∈U b (t) x i (t) = 1, x i (t) ∈ [0, 1], i ∈ U b (t), i∈U b (t) xi (τ ) = 1, τ = τ . . τ + J -1, xi (τ ) ∈ [0, 1], τ = τ . . τ + J -1, i ∈ U b (t). ( III
)
where τ is the big-slot counted from t + 1, i.e., it contains m consecutive small-slots t + 1 . . t + m. The decision variables in Problem (III) are the allocations x i (t) in the current small-slot, and the allocations xi (τ ) in the future big-slots. Since the future allocations are only computed on the time-scale of big-slots, there is reduction of factor m in the number of variables in (III).

• Step 2 -The channel of BS b is allocated to (an arbitrary) user i ∈ argmax j∈U b (t) x j (t).

The computational complexity of this heuristic is mainly in Step 1, which requires in the order of 20×(J +1)×|U b (t)|×log(|U b (t)|) operations to complete (as we limit the number of iterations of the projected gradient algorithm to 20).

Short term objective algorithm 2 (STO2)

In STO2, we further reduce the complexity by recomputing the future allocations only at the beginning of a big-slot. The future allocation computed is thus used until the end of this big-slot. If one new user arrives to the system in the middle of a big-slot, we just ignore it for this big-slot and wait until the beginning of next big-slot to update the state. Once the allocations for future big-slots are computed, then in every small-slot of this big-slot, we apply an index-based policy as in [START_REF] Borst | Mobility-driven scheduling in wireless networks[END_REF].

The steps for STO2 are:

• Step 1 -At the beginning of each big-slot τ , that is at time t = τ m + 1, solve the following problem using the projected gradient algorithm:

             maximize i∈U b (t) log A i (t -1) + τ +J-1 τ =τ xi (τ )ρ i (τ ) s.t. i∈U b (t) xi (τ ) = 1, τ = τ, . . . , τ + J -1, xi (τ ) ∈ [0, 1], i ∈ U b (t), τ = τ, . . . , τ + J -1.
(IV)

• Step 2 -Inside a big-slot, in each small-slot s, compute M i (s) as in [START_REF] Borst | Mobility-driven scheduling in wireless networks[END_REF] where the future allocation x is the solution x of (IV), and then allocate the channel to the user i maximizing M i (s).

Note that

Step 1 in STO2 is computed only once every big-slot unlike m times in every big-slot as in STO1. By doing this, we further reduce the number of computations almost by a factor m.

Extension to joint channel allocation and power control

We now show how the heuristics can be extended for joint channel allocation and power control. The throughput of user i ∈ U b (t) is now computed according to the Shannon formula

r i (t) = x i (t) log 1 + γ i (t) p i (t) x i (t) , (7)
where x i (t) is the fraction of the channel assigned to user i in slot t by base station b, and p i (t) is the power with which the BS transmits to user i. In [START_REF] Huang | Downlink scheduling and resource allocation for ofdm systems[END_REF], γ i (t) represents the channel gain of user i at time t. As before, we do not make explicit the dependence of r i (t) on the decision variables x i (t) and p i (t) in order to keep the notation light. We assume that each BS has an average transmit power constraint of P over the horizon T , and that the maximum transmit power in each time slot is P max . The objective of each BS is now to choose the power and the channel allocation so as to maximize the total utility of the K users over a horizon of T time slots:

maximize K i=1 log 1 T T t=1 r i (t) (V) s.t. ( 8
) i∈U b (t) x i (t) = 1, b ∈ B, t = 1, . ., T, (9)
1 T t i∈U b (t) p i (t) ≤ P , b ∈ B, ( 10
)
i∈U b (t) p i (t) ≤ P max , b ∈ B, t = 1, . ., T, (11)
x i (t) ∈ [0, 1], i ∈ U b (t), t = 1, . . . , T. (12)
Here ( 10) is the average power constraint, while [START_REF] Margolies | Exploiting mobility in proportional fair cellular scheduling: Measurements and algorithms[END_REF] is the maximum power constraint. Note that in (V) we have allowed for fractional channel allocations. If the system imposes a binary constraint, that is only one user on one channel in any given slot, then these constraints can be imposed as well as in the algorithms we propose. In our experiments, we observed however that allocations were mostly binary. So, we expect the qualitative conclusions to be valid whether allocations are binary or not. Remark 3 (Maximum power constraint). For conciseness, we shall not write the maximum power constraint explicitly in the optimization problems that we will define from now on. This constraint will be implicit and assumed to be applicable in all slots.

In contrast to the current literature, which is based solely on the channel gains in the current time slot, we can extend our heuristics so as to exploit also the predicted values of the mean channel gains in the future slots.

Short term objective 2 (STO2) with power control

We will only give the STO2 version of the algorithm since it is computationally less expensive and performs well. The STO1 version can also be formulated along similar lines, if needed.

As before, a big-slot is m consecutive time-slots. For a non-stationary and slowly varying model in which, for each vehicle i, the mean of the channel gains varies on a slow time-scale, the preferred value of m will be the number of time-slots during which mean channel gain remains constant. For example, for a time-slot of 2 ms, the means may vary every 200 ms, which yields m = 100 slots. In contrast, in a mobility model where cars can come and leave, the channel gains γ i (t) are non-stationary and their means change every slot. In this case, the value of m can be set by the system designer depending on how fast the mean channel gains vary. Let τ t ∈ {1, . . . , T } be the big-slot to which time-slot t belongs to. The number of slots remaining in big-slot τ t after (but not including) time t is then θ t = (τ t + 1)m -t.

We shall use the notation x for a quantity that is computed over a big-slot. For example pi (τ ) will denote the power used in all the slots inside big-slot τ . Similarly,

ri (τ ) = m • xi (τ ) log 1 + γi (τ )p i (τ ) xi (τ ) (13)
is the total rate obtained by vehicle i in big-slot τ when it is served a fraction xi (τ ) of time at a transmit power of pi (τ ). Note that here the rate is computed assuming that the channel gain is its mean value in big-slot τ . With a slight abuse of notation,

ri (τ t ) = θ t xi (τ t ) log 1 + γi (τ t )p i (τ t ) xi (τ t ) , (14)
shall denote the total rate in the remaining slots in current big-slot τ t .

Recall that STO2 recomputes the allocations and powers of the future bigslots only at the beginning of each big-slot and over a short-term horizon of J. Inside a big-slot, it computes only the solution for the current slot assuming the solution for the future big-slots to be the same as that computed at the the start of the current big-slot. The power control version of this algorithm operates in two steps.

• Step 1 -If t ≡ 1 (mod m), i.e., at the beginning of each big slot, BS b first maximizes

i∈U b (t) log t-1 s=1 r i (s) + τt+J-1 τ =τt ri (τ ) (STO2-Big) subject to [x i (τ )] ∈ S, i ∈ U b (t), τ = τ t , . . . , τ t + J -1, (15)
m i∈U b (t) pi (τ ) ≤ P , τ = τ t , . . . , τ t + J -1, ( 16
)
where S is the set of feasible solutions of problem (IV). The variables in this problem are [x i (τ )] and [p i (τ )], τ = τ t , . . . , τ t + J -1, only for the cars in the scheduling area of BS b. The constraint [START_REF] Vijay | Joint scheduling and resource allocation in CDMA systems[END_REF] ensures that the average power does not exceed P in each big-slot.

Remark 4. The average power constraint [START_REF] Vijay | Joint scheduling and resource allocation in CDMA systems[END_REF] is stricter than (10) since it is imposed in each big-slot and not over the remaining horizon. This is done because otherwise the algorithm does not necessarily use up all its power budget. Depending upon the scenario, it may leave quite some power budget for the future big-slots and not end up using it if enough cars do not arrive in the future or the channel conditions were not favorable. Therefore, to ensure that STO2 uses all the power budget, constraint [START_REF] Vijay | Joint scheduling and resource allocation in CDMA systems[END_REF] is imposed in each big-slot.

• Step 2 -Next, in each small-slot t, the optimal allocation and transmit power are computed for t as well as for the remaining small-slots in the current big-slot assuming that the allocations and transmit powers in the future big-slots are those computed from solving (STO2-Big). That is, in slot t, STO2 maximizes

i∈U b (t) log t-1 s=1 r i (s) + r i (t) + τt+J-1 τ =τt ri (τ ) (STO2-Small) subject to [x i (t)] ∈ S, [x i (τ t )] ∈ S; ( 17
)
i∈U b (t) (p i (t) + θ t pi (τ t )) ≤ P (b) t , (18)
where P (b) t

is the remaining power budget of BS b in the current big-slot. The variables in this problem are

[x i (t)], [p i (t)], [x i (τ t )] and [p i (τ t )].
In each small-slot, STO2 solves a lower dimensional problem with 4|U b (t)| variables -2|U b (t)| for the current small-slot and 2|U b (t)| for the remaining small-slots in τ t . This is twice the number that would be required when not using future information. So, the complexity induced by optimizing over future information is not excessive.

Numerical results

This section compares the utility of the proposed heuristics with PF-EXP, (PF) 2 S and a greedy algorithm. For the (PF) 2 S the future allocation was done using the round robin algorithm. Two different simulation setups will be used. In the first one in Section 6.1, vehicles move along a single road served by one BS. The simulations for this scenario are performed with Python. The second set of scenarios, presented in Section 6.2, consists of three road networks with multiple BSs. The simulations for these scenarios are done using SUMO which simulates actual vehicle driving behaviour.

Before presenting the scenarios, we first introduce the performance metric. Recall that the proportional-fair utility is defined in (I). Let

U A = K i=1 log T t=1 φ i (t) ,
be the total utility or the reward of algorithm A and by Ū A = 1 K U A its average utility (reward) over K users. A comparison of two algorithms A and B using the relative error is not appropriate because of the logarithm in the utility. Note that when a different unit of measure is used for the data rate (for example, bits instead of megabits), the ratio U A /U B changes as well. In order to have a comparison that is independent of the units of measure, it is more appropriate to use the difference U A -U B , or, for convenience, exp( Ū A -Ū B ) which gives a non-negative value with 0 meaning that the utility of B is vastly superior to A, and ∞ meaning that it is the other way round. As the performance measure, we shall use the percentage improvement of algorithm A over B given by (exp( Ū A -Ū B ) -1) • 100%.

Single road and homogeneous vehicle velocities

In the first set of simulations, there is only one base station and one straight road in the scheduling area. The road length is taken to be L = 1000 m with 0 at the leftmost edge. The closest point on the road to the BS is at z = 500 m. The data rate at position z along the road is given by:

r(z) = η • (1 + κ exp (|z -500|/σ) , (19)
where κ ≥ 0 is a real number and η is uniform random variable whose range will be in [0.7, 1.3] unless stated otherwise. A sample path of r(z) is shown in Figure 2 for two different values of κ. This function has the highest mean at the mid-point of the segment and the lowest mean at the two end points. We chose the above rate function for convenience and emphasize that the algorithm itself is independent of the rate function. The time horizon T was 4, 000, 000 small-slots which corresponds to 8000 seconds (slightly more than two hours). The big-slot length ∆ for our algorithms was taken as 1 second or equivalently 500 small-slots.

Vehicles enter the road from the left edge, move with the same velocity v = 25 m/s, and leave from the right edge. This gives N = 20, 000 spatial small-slots in the scheduling area and J = 40 big-slots. The arrival of new cars on the left edge is assumed to happen with probability p in every second.

Figure 3a shows the average utility obtained by a vehicle for each of the four algorithms as a function of the arrival probability p. When p is small it is natural for all the algorithms to give similar rewards since there is rarely more than one car at a time in the scheduling area. The difference becomes more apparent at higher values of p when there are more cars competing for the channel. Figure 3b shows the percentage improvement of the three other algorithms compared to PF-EXP. Both STO1 and STO2 do better than PF-EXP and more importantly better than (PF) 2 S. The greedy algorithm does well in this scenario mainly because all vehicles move along the same road and observe statistically identical but position-dependent radio conditions during their stay. As mentioned previously, greedy is not practically implemented because it can be very unfair to users that have heterogeneous rates. Comparison with the upper bound: before considering more complex scenarios, we compare our algorithms to the upper bound which can be obtained by solving the relaxed problem (II) assuming that all the future arrivals as well as future data rates are known exactly and given as input. Solving with such assumptions is infeasible in practice. However, purely for comparison purposes, the upper bound can show how much we lose due to lack of precise information. Since the problem size of (II) can grows quickly with the parameters, we restrict the road length to L = 100 m, and reduce the time-horizon to T = 500 s. The big-slot ∆ is shortened to 0.1 s so that J = 40 big-slots as before. The rate curve remains the same as for the previous setting.

Figures 4a and4b plot the average utility per car and percentage improvement with respect to PF-EXP for the four algorithms as well as for the upper bound. It can be observed that the proposed algorithm is quite close to the upper bound in this scenario which means that average data rates provide a good estimate of the actual data rates.

Network simulation with SUMO

Simulation of Urban MObility application (SUMO) [START_REF] Lopez | Microscopic traffic simulation using sumo[END_REF] is an open source software designed for simulating mobility of vehicles in large traffic networks. One of the features of this simulator is that we can import maps of different cities and simulate realistic mobility traces. We use this application to simulate the 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 probability of new arrival complex driving dynamics in a simple scenario and in two specific regions of Toulouse city to have an objective comparison of our heuristics against existing algorithms in realistic scenarios.

The performance evaluation of heuristics in done in two steps. In the first step SUMO is used for generating the mobility traces of vehicles. These traces are then fed to a Python script which implements the different heuristics and computes the value of the objective function.

In the following, unless otherwise specified, the parameters are chosen as follows: κ = 4, σ = 100, big-slot ∆ = 1s and the short-term horizon J is the maximal remaining sojourn time of the users that are currently inside the system. We calculate the allocation plan every one second. From now on, we do not include STO 1 in the comparison because STO 1 takes much longer time to run and may not be computationally interesting on small time-scales. Also, we also do not show the performance of the greedy algorithm here since some users may starve in a greedy allocation leading to a value of -∞.

A simple network with 1 BS

Let us consider the network presented in Figure 5a. There are two classes of users: one that arrives from A then moves along the long road to B and D (the blue one), and another one that arrives from A then moves to B and then to C (the red one). The base station is placed at location (20, 40), A is placed at (-94, 40), B is placed at (-34, 39), C is placed at (-35, -18) and D is placed at (96, 35), so the length from A to D in this simple network is 190 m. The simulation duration was 1 hour 9 minutes and 25 seconds with a total of 1598 users passing through during this time.

If we apply the greedy heuristic in this situation, then many users of the second class are never allocated the channel assuming that when the second class leaves the scheduling area it does not get close to the BS of the next cell. This is the reason why we do not evaluate the performance of the greedy algorithm for this scenario. Figure 5b shows the numerical results for this case. In this scenario, it was observed that PF-EXP always gives priority to the new arrivals no matter what the initial value is. This leads to a higher sub-optimality of PF-EXP since the other heuristics focus on users that are closer to the base station and have a higher quality channel.

Power control

We redo the above experiment for the algorithms with power control. The average power level, P is taken to be 1 and P max = 5. The horizon J = 5 big-slots and ∆ = 1 sec. The rate curve is taken such that the rate when transmitting at P gives the rate curve of the scenario without power control. Fig. 6a shows the average utility for STO2, STO2-FP which is STO2 but with a fixed power level of P in each small-slot, and PF-EXP again with a fixed power level of P in each small-slot. Gains in utility (and the throughput) can be achieved by using prediction of the future average rates. There is no discernible gain achieved by power control compared to the fixed power algorithm. The gains will of course depend upon the parameters of the scenario. One such scenario will be shown later.

Fig. 6b shows the statistics of the gain in average utility obtained by STO2 with respect to that of PF-EXP. Only alternate noise values are shown so as not to clutter the plot. The box plot shows the median and the 25 and 75 percentiles and violin plot shows how the values are distributed. The points above the horizontal line at 0 are for vehicles that improved their utility under STO2 when compared to that under PF-EXP while any point under this line indicates vehicles that see a decrease in utility under STO2. In this scenario, only two vehicles out of 1600 did not benefit by the use of STO2. Figure 8a, 8b, 8c plot the average utilities for different values of κ with the same J and ∆. The gap between STO2 and (PF) 2 S become larger when κ increases.

Figure 9a, 9b, 9c and 9d illustrate the average utilities for different values of J with the same values of κ and ∆. Remark that we assume (PF) 2 S and STO2 use the same information, so in (PF) 2 S the future information is estimated until J as well. It is seen that the more information we have, the better (PF) 2 S and STO2 perform.

Figure 10a, 10b and 10c show the influence of the size ∆ of the big-slot, assuming the same values of J and κ. The performance of STO2 is almost the same for these different values of ∆ but the running time is significantly shorter with the largest value.

Power control

As for the previous scenario, we redo the above experiment for the algorithms with power control. The average power level, P is taken to be 1 and P max = 5. The horizon J = 5 big-slots and ∆ = 1 sec. The rate curve is taken such that the rate when transmitting at P gives the rate curve of the scenario without power control. Fig. 11a shows the average utility for STO2, STO2-FP. As before, gains in utility (and the throughput) can be achieved by using prediction of the future average rates. The gains achieved by power control again are negligible compared to those by prediction.

Fig. 11b shows box plot and the violin plot for the gain in average utility of STO2 with respect to PF-EXP. The number next to the double arrowed line is the fraction of vehicles that see a decrease in their utility under STO2. Unlike in the previous scenario, this time, a non negligible proportion of vehicles see a decrease in their utility. For example, 27% of vehicles saw their utility decrease for noise level of 0.1 while this number was 8% for noise level of 0.9. However, overall STO2 improves the average utility with a median of +0.05 units of utility, that is at least half of the vehicles gained 0.05 units of utility. In the final set of simulations, we take another area of Toulouse called Jardin des Plantes with four BSs as shown in Fig. 12a. The average utilities for this scenario are plotted in Fig. 12b. It took 976 seconds, 1009 seconds, 1502 seconds and 3403 seconds to run greedy, PF-EXP, (PF) 2 S and STO2 for 1.05 hours of traffic with 740 users (including cars, buses, motorbikes, bicycles and pedestrian). Again, we do not include the greedy algorithm in the utility comparison since there are several starving users in this case.

Power control

The plots for this scenario with power control are shown in Fig. 13. Here, power control does bring improvements over the fixed-power STO2 with respect to the previous two scenarios. Compared to the Place Wilson scenario, STO2 has a smaller fraction of vehicles that are worse off than with PF-EXP. We proposed two heuristics that use future mean channel gain information to improve the utility of users in cellular networks. In order to reduce the computational complexity, they solve the problem over a shorter time horizon as well as on a larger time-scale. It was shown on numerical experiments carried out on traces generated from realistic mobility patterns that these heuristics give better utility compared to PF as well as (PF) 2 S algorithms. There are several directions in which this work can be taken. One avenue is to implement a centralized and coordinated version of these heuristics. Further, it will be interesting to design heuristics for networks in which there are a fractions of users whose future channel gain information is not known. These could be users who do not share their mobility information or users like pedestrians whose mobility can be random and hence not known exactly.

Other directions of research include designing heuristics for different utility functions and QoS requirements such are latency and jitter. On the analytical side, obtaining heuristics with guaranteed sub-optimality bounds will be worth investigating.

A Projection on feasible set D

The set D is a Cartesian product of J simplexes:

D = D 1 × D 2 • • • × D J where D t = x t = (x i,t ) i=1. .K ∈ [0, 1] K : K i=1
x i,t = 1 , for all t = 1, 2, ..., J.

Since the sets D t are simplexes, we can compute the projection on D t following [START_REF] Condat | Fast projection onto the simplex and the l1 ball[END_REF]. The projection on D can thus be computed with the simple following lemma.

Lemma 5. If y = (y i,t ) i=1. .K,t=1. .J ∈ R K×J , then

Π D (y) = Π D1 (y 1 ) × Π D2 (y 2 ) × • • • × Π D J (y J ),
where y t = (y i,t ) i=1. .K .

Proof. Denote by z = Π D1 (y 1 ) × Π D2 (y 2 ) × • • • × Π D J (y J ). It is easy to check that for any x ∈ D, we have yz, xz ≤ 0.

As described in [START_REF] Condat | Fast projection onto the simplex and the l1 ball[END_REF], the worst-case complexity of computing Π Dt is O(K 2 ), but is observed to be equal to K × log(K) in practice. Therefore the complexity of computing the projection on D = D 1 × D 2 • • • × D J is expected to be J × K × log(K) in practice.

B Proofs B.1 Proof of Proposition 2

Proposition 2. The point x * is an optimal solution if for any x ∈ D, ∇U (x * ) • (x * -x) ≤ 0.

From Lemma 5, it follows that it is sufficient to prove the above inequality on D t for an arbitrary t ∈ {1, . ., J}. Assuming U is a convex function on D t , we shall prove that if x * t = (x * i,t ) i=1,. -τ (0 -x i,t ), ≥ 0.

The last sum is greater than 0 since all its terms are greater than or equal to 0.

B.2 Proof of Proposition 1

Proposition 1. In fact the condition (5) implies that ∇U (x * ) = 0, which yields the proof according to Proposition 2.

  (a) A selected area of Toulouse which is covered by three BSs of the French mobile network operator Free Mobile. Difference between coverage area and scheduling area

Figure 2 :

 2 Figure 2: Sample path of data rate at various positions along the road. σ = 100, and η ∼ U [0.7, 1.3].

  Percentage of improvement over PF-EXP.

Figure 3 :

 3 Figure 3: Comparison of algorithms for homogeneous vehicle velocities.

  Small setting: percentage of improvement over PF-EXP.

Figure 4 :

 4 Figure 4: Comparison of algorithms against the upper bound from the solution of (II) for homogeneous vehicle velocities.

  A simple road network with two classes of users. (b) Comparison of the utilities obtained with STO2, (PF) 2 S and PF-EXP for the scenario of Fig. 5a.

Figure 5 :

 5 Figure 5: Simple netwokr scenario and its average utility.

  Gain in average utility of STO2 with respect to PFexp. Outliers have been omitted.

Figure 6 :

 6 Figure 6: Simple network with power control

  Comparison of the utilities obtained with STO2, (PF) 2 S and PF-EXP for the scenario of Fig. 7a.

Figure 7 :

 7 Figure 7: Place Wilson scenario and its average utility.

Figure 8 :

 8 Figure 8: Comparison of the utilities obtained with STO2, (PF) 2 S and PF-EXP for the scenario of Fig. 7a and for different values of κ.

  J = maximum sojourn time in term of big-slot of all users inside the system.

Figure 9 :

 9 Figure 9: Comparison of the utilities obtained with STO2, (PF) 2 S and PF-EXP for the scenario of Fig. 7a and for different time horizon J.

Figure 10 :

 10 Figure 10: Comparison of the utilities obtained with STO2, (PF) 2 S and PF-EXP for the scenario of Fig. 7a and for different values of ∆. The performance are almost the same, but the running time is much shorter when increasing the big-slot size.

  Gain in average utility of STO2 with respect to PFexp. Outliers have been omitted.

Figure 11 :

 11 Figure 11: Place Wilson scenario with power control

  Comparison of the utilities obtained with STO2, (PF) 2 S and PF-EXP for the scenario of Fig.12a.

Figure 12 :

 12 Figure 12: Jardin des Plantes scenario and its average utility.

Figure 13 :

 13 Figure 13: Jardin des Plantes with power control

  .,K ∈ D t satisifes * t -x t ) ≥ 0, for any x t ∈ D t , i.e, x *t is global optimum of U . Indeed, without loss of generality, we assume that

	∇U (x * t ) • (x x * 1,t + ∂U ∂x * 1,t ≥ x * 2,t + ∂U ∂x * 2,t	≥ . . . ≥ x * n,t +	∂U ∂x * n,t	≥ x * K,t +	∂U K,t ∂x *	,
	where n is the largest index such that
				1 n	n i=1		x * i,t +	∂U ∂x * i,t	-1 ≤ x * n,t +	∂U n,t ∂x *	.
	Define τ = 1 n	n i=1 x * i,t + ∂U i,t ∂x *	-1 . By Proposition 10 in [6] we have:
	Π Dt (x * t + •∇U (x * t )) = x * 1,t +	∂U ∂x * 1,t	-τ, x * 2,t +	∂U ∂x * 2,t	-τ, ..., x * n,t +	∂U ∂x * n,t
	Comparing term by term with (20), we get:
	1. x * n+1,t = • • • = x * K,t = 0,
	2. x * n+1,t +	∂U ∂x * n+1,t	≤ τ, • • • , x * K,t + ∂U K,t ∂x *	≤ τ . It thus follows from the first
	item that		∂U ∂x * n+1,t	≤ τ, • • • , ∂U K,t ∂x *	≤ τ ,
	3. ∂U ∂x * 1,t	= • • • = ∂U n,t ∂x *	= τ .
	It yields
	∇U (x * t ) • (x * t -x t ) =		K i=1	∂U i,t ∂x *	(x * i,t -x i,t )
						=		n i=1	∂U ∂x * i,t	(x * i,t -x i,t ) +	K i=n+1	∂U i,t ∂x *	(x * i,t -x i,t ),
						=		n i=1	τ (x * i,t -x i,t ) +	K i=n+1	∂U i,t ∂x *	(x * i,t -x i,t ),
						=		K i=1	τ x * i,t -	K i=1	τ x i,t +	K i=n+1	∂U i,t ∂x *	-τ (x * i,t -x i,t ),
	for some > 0, then		Π Dt (x * t + ∇U (x * t )) = x * t K ∂U = τ -τ + i=n+1 ∂x * i,t	(20)

-τ, 0, ..., 0 .

The throughput is different from the data rate. While the latter is the potential rate at which a user can be served, the former can be smaller since in some slots a user may not be served due to the presence of other users.

https://data.anfr.fr/anfr/portail

Acknowledgment

The authors would like to thank Continental Digital Service in France for supporting partially of this work.


M Gaudon
email: gaudon@icmcb-bordeaux.cnrs.fr

N Pailhe

A Wattiaux

A Demourgues

Structural defects in AFe 2 O 4 (A = Zn, Mg) spinels

Introduction

A 2+ (B 3+ ) 2 O 4 compounds commonly adopt a cubic symmetry with the Fd-3m space group related to the spinel-type structure. In such a structure, A 2+ and B 3+ cations occupy either the octahedral sites (16d) or the tetrahedral sites (8a) depending on their affinity for these various environments. When all the divalent cations are located in the tetrahedral sites, the spinel network is defined as a normal one or a direct one. In some cases, octahedral sites can also be occupied by a fraction or the totality of divalent cations, forcing an equivalent amount of trivalent cations to occupy tetrahedral sites. In such cases, the spinel structure is partially inverted or fully inverted, respectively. Hereafter, the inversion percentage is defined as 100y, with y the stoichiometric coefficient for the following formulae associated to spinel structure: A 2+ 1Ày B 3+ y [A 2+ y B 3+ 2Ày ]O 4 where square brackets refer to octahedral sites. With the structural convention used in the following, each oxygen atom of the network, common to three octahedral sites (16d sites) and one tetrahedral site (8a sites), is located in 32e sites with spatial coordinates (u, u, u). In Fig. 1 is presented a typical Fourier cartography for AB 2 O 4 spinel composition and for two characteristic plans: z = 0 and z = 1/8. In spinel framework, the point group symmetry of the tetrahedral sites remains perfectly isotropic, i.e., with Td configuration, whereas the octahedral sites are distorted and exhibit D 3d symmetry. Nevertheless, such description results from a global point of view for which the local atomic environments cannot be distinguished while several atoms occupy both tetrahedral and octahedral sites. X-ray data refinements with Rietveld method lead so to limited information: cell parameter, inversion rate and (u, u, u) average position of oxygen anion. All these parameters are known to be dependant from the composition, the analysis temperature either from the thermal history of the sample: temperature/duration of annealing, thermal cycle rates (quenching) and atmosphere. However some contradictions appear between the observed inversion rate and u parameter. For instance, considering specific literature data devoted to the Mg or Zn ferrite spinels, from numerous refinements, calculated bond distances are not satisfying in regard of the theoretical ones which can be evaluated from the Brown and Altermatt model [1]. Hence, for the ZnFe 2 O 4 composition which has been described in the literature as partially inverted spinel with a low rate of Fe 3+ in Td sites, the crystallographic data [2][3][4][5] proposed 8a-32e bond distances varying from 1.97 A ˚to 1.985 A ˚, i.e., longer than the Zn-O bond distances predicted for 4-coordinated Zn 2+ sites: 1.962 A ˚, a partial occupation of this site by the smallest cations (Fe 3+ ) cannot easily be considered.

In the present study, it will be shown that Zn 2+ /Mg 2+ (Fe 3+ ) 2 O 4 spinel oxides can be refined considering models including cationic and anionic vacancies and/or interstitial atoms. One can notice that even if, especially for aluminate spinels (MgAl 2 O 4 , ZnAl 2 O 4 ), ab initio calculations have evidenced the energetic stability of internal cluster formed by recombination of interstitial atoms and atomic vacancies (Frenkel pairs association) [6][7][8] and so, the possibility of their presence, no experimental refinement were performed including into consideration such phenomena.

Finally, for the ZnFe 2 O 4 sample, electronic residues in inserted position (48f and 8b sites) have been identified and may explain the distributed cationic vacancies into the (8a) tetrahedral sites.

This work proposes a new view on the cationic distribution into the spinel oxide network allowing to explain the evolution of the bond distances, the inversion rates and the oxygen atom coordinates. The aim of this paper is to compare the standard model: direct/inverted spinel to another formalism taking into account cationic/anionic vacancies with a specific distribution on the various sites.

A B S T R A C T (Zn 2+ /Mg 2+ )[Fe 3+ ] 2 O 4 spinel oxides can be refined as direct/fully inverted (respectively) spinels but considering cationic and anionic vacancies and/or interstitial atoms instead of a partial inversion rate of the A 2+ and B 3+ cations. The refinements results of the X-ray diffraction patterns and Mo ¨ssbauer spectroscopy spectra are discussed and show the veracity of the new structural formalism.

Experimental

Synthesis process

(Zn/Mg)Fe 2 O 4 pigments were synthesized by the Pechini route [9]. Aqueous solutions of citrate were prepared by dissolving citric acid (CA) in a minimal volume of water. Then, cationic salts, Fe(NO 3 ) 3 Á9H 2 O and Mg(NO 3 ) 2 Á6H 2 O, were added in stoichiometric proportion to the acid solution. A CA:cations molar ratio equal to 3:1 was used. After complete dissolution of metallic salts, ethylene glycol (EG) was added to the mixture under magnetic stirring, with a 4:1 EG:CA molar ratio. EG-CA polymerization was promoted by removing water with continued heating on a hot plate until solutions became highly viscous. Then, the obtained gelled mixtures are thermally treated in ambient atmosphere with two calcination steps: a first ''pre-calcination'' at 300 8C for 10 h with a heating/cooling rate of 1 8C min À1 , then, an annealing for 5 h at 1000 8C with 1 8C min À1 heating/cooling rate was finally performed. This chemical process is used instead of solid state route in order to obtain a higher cationic homogeneity.

X-ray diffraction studies

For structural investigations, X-ray diffraction (XRD) measurements were carried out on a PANalytical X'PERT PRO diffractometer using Co(Ka 1 /Ka 2 ) radiation in order to suppress any fluorescence problem related to the occurrence of Fe 3+ ions. The f 0 and f 00 anomalous dispersion corrections (real and imaginary parts) of each element (O, Fe, Mg, Zn) besides co-radiation, defined from the formulae f at = f 0 + f 0 + if 00 where f at is the atomic scattering factor [START_REF]International Tables of Crystallography[END_REF], were manually introduced into the program. XRD data were recorded with a 2u step = 0.0178 with a counting time over 200 s per step and 10-1208 2u range. The patterns have been treated using Rietveld refinement method using FULLPROF 1 program suite [START_REF] Rietveld | [END_REF][12]. The diffraction peaks profiles were approximated as a pseudo-Voigt using Caglioti function. The refined parameters are zero shift, scale factor, background polynomial parameters, peaks profile parameters U, V, W, and h (Lorentzian/Gaussian distribution), unit cell parameters, atomic positions, site occupancies and isotropic displacement factors.

Mo ¨ssbauer studies

In order to evaluate Fe 3+ local environments and magnetic ordering of the studied ferrite compounds, 57 Fe Mo ¨ssbauer measurements were performed at 293 K and 4 K. Both analyses are in transmission mode and were made using a conventional constant acceleration spectrometer (HALDER) using rhodium matrix source. The fitting of Mo ¨ssbauer patterns as a series of Lorentzian profile peaks allowed the calculation of position (d), amplitude and width (G) of each peak: thus, experimental hyperfine parameters were determined for the various iron sites by least square program.

Results and discussion

Focus on MgFe 2 O 4 composition

For X-ray refinements performed on MgFe 2 O 4 compound, whatever the refinement process used, cell parameter, peak profile decentring and background coefficient do not vary significantly and are not here discussed. Unit cell parameter remains equal to 8.3930(1) A ˚, a value in good agreement (but corresponding to the higher values) with the literature data [13][14][15].

As ''reference'', the structural hypothesis for refinement corresponds to fully inverted spinel without any cationic/anionic vacancy. The refinement results are reported in Table 2. This model is deficient since the isotropic displacement factors are not satisfying with negative values refined for 16d site cations. Obviously, the isotropic displacement factors of the 16d sites exhibit negative values because of their electronic density is too low with this structural hypothesis. The standard way to optimize this electronic filling in the spinel network is to consider partially inverted spinel (Mg atoms: z = 12 contain twice less electrons than Fe ones: z = 26). Results obtained from this free cationic distribution, joined in Table 2, clearly show a very important improvement of the refinement in comparison with the fully inverted model. The various correlation factors: Rp, Rwp, Rexp, RBragg indicate a ''satisfying'' refinement. The RBragg factor, characteristic of the structural refinement quality, has notably decreased from 7.5% to 3.4%. The partial inversion rate (79%) and the (u, u, u) anion's position are consistent with those proposed in current literature [13,[16][17][18]. Hence, one may conclude that the MgFe 2 O 4 is a partially inverted spinel, nevertheless, several points are unclear.

Firstly, the isotropic displacement factors (B iso ) of the cations in the tetrahedral sites are slightly larger to those in the octahedral sites. Actually, one can consider that octahedral sites should exhibit a larger B iso values than tetrahedral sites ones because of its longer bond lengths and also because the octahedral sites are occupied by a large content of Mg 2+ ions which are the lighter cations.

Secondly, the metal-ligand bond lengths have been checked and compared with the theoretical ones which can be predicted basing on the Brown and Altermatt semi-empirical law [1]. This equation is normally used in order to check if the distances established by diffractograms refinement are correct. Here, this law was used in a reverse way in order to deduce from the valences of each element, the theoretical metal-cation bond lengths in various environments. Theoretical M-O lengths are reported in Table 1. From these M-O lengths it is possible to now predict the theoretical inversion rate that one should have obtained in order to satisfy the experimental M-O distances (deduced from the refinement). Here, considering a mixing law between Mg-O and Fe-O theoretical bond lengths and with an inversion percentage of 79%, 1.883 A ˚and 2.048 A ˚lengths should be obtained, respectively for tetrahedral and octahedral sites. The calculated distances from refinements are 1.948 A ˚and 2.026 A ˚for tetrahedral and octahedral sites, respectively, i.e., too high and too low considering the bond distances estimated on the basis of the Brown model. However, it can be noticed these distances are ''standard'' in regard of the literature data.

Thus, the following hypothesis has been considered: the atomic distribution in the MgFe 2 O 4 spinel may quite remain fully inverted but in addition cationic/anionic vacancies have to be taken into account in order to explain the experimental bond distances. This hypothesis also means that the inversion rate proposed in the literature is actually an artefact issued from the inconsideration of vacancies mainly located on the tetrahedral sites of the structure.

Fe 1À3x [Mg 1Àx Fe 1+x ]O 4À4x formulae was envisaged on the basis of the chemical composition, a complete filling of the octahedral sites and the oxide electroneutrality. Note that a partial occupation of the octahedral sites by Mg 2+ has to be considered. There is the same number of adjustment parameters in this case than for the inversion rate model: x variable directly replacing the y inversion rate variable, i.e., the reliability factors issued from both model can be directly compared. The refinement was illustrated in Fig. 2a exhibiting experimental, calculated and difference signals. The results of the refinements are reported in Table 2; the experimental bond lengths found with this last refinement model were joined to Table 1. The x vacancy was determined and found equal to 0.04. This last model leads to the weakest correlation factors, particularly for the RBragg factor. Furthermore, the cationic isotropic displacement factors are now more consistent. Indeed, the B iso coefficients of the octahedral sites became slightly higher than the tetrahedral sites ones. However one should notice that B iso value of the oxygen atom remains low. Moreover, even if the two last refinement models (with or without vacancies) are very different, the electronic residues are distributed in the two cases in a very similar way. This phenomenon is illustrated by the Fourier maps (Fobs-Fcal) reported in Fig. 3. In addition the Fourier map established from the purely inverted and non-lacunar spinel model has been reported in order to illustrate the large improvement of the refinement quality from this first model up to the last one. For the as-prepared MgFe 2 O 4 oxide, the consideration of vacancies segregated on tetrahedral positions leads to the same results than those obtained with the partial inversion of Fe 3+ ions in tetrahedral sites.

Focus on ZnFe 2 O 4 composition

A comparable study to the previous one was performed on ZnFe 2 O 4 composition. In the literature data [2][3][4][5], this composition is referred as quasi-direct spinel, i.e., with a weak inversion rate ranging from 5% to 15% depending on the authors. Studies have notably show that the inversion rate depends on thermal sample history [19]. On the contrary, Mo ¨ssbauer studies show that even if nano-sized particles obtained with ball-milling or by sweet chemistry routes (sol-gel) exhibit high degree of inversion, particles with grain size over 10 nm exhibit no magnetic superexchange and can so be considered as purely normal spinel [20][21][22]. This so consist in an unclear point in the literature. Firstly, refinements have been performed considering spinel as a direct one. Secondly, the inversion rate between A and B sites cations was refined. Whatever the refinement model, the cell parameter is found equal to 8.4424 A ˚. Same observations can be made than for MgFe 2 O 4 study. There is a very significant improvement between the direct and partially inverted spinel model (Table 3 refinement results); nevertheless several points have to be discussed such as displacement factors as well as M-O bond lengths. Actually, the M Td -O distances are more important than those established from Brown and Altermatt for a pure direct spinel, i.e., Zn (IV) -O bonds lengths (1.978 A ˚instead of 1.962 A ˚). Consequently, it is less probable that a part of the Td site is occupied by a fraction of Fe 3+ ions, these last cations being largely smaller than Zn 2+ ones.

As for MgFe 2 O 4 , a model where vacancies are mainly segregated on the tetrahedral sites has to be rather considered. In comparison with the MgFe 2 O 4 compound, for ZnFe 2 O 4 composition, a vacancy rate on tetrahedral site implies in order to maintain the Fe/Zn molar ratio that a part of zinc migrates on 16d sites. Then, the refinement was performed considering the Zn 1À3x [Fe 2À2x Zn 2x ]O 4À4x formula. The refinement patterns are reported in Fig. 2b. This oxide formula was established with a part of Zn 2+ ions located in 16d sites without any compensation by the migration of Fe 3+ through 8a sites but, on the contrary, considering only compensation by oxygen vacancy creation. The corresponding refinement results are reported in Table 3 and are comparable with the partially inverted spinel model. Moreover, whatever the refinement model which is chosen, the Fourier maps show non-negligible electronic residues on two inserted positions: the 48f sites and especially on 8b sites (see Fig. 4). Thus, it seems that the occurrence of Zn 2+ ions in the octahedral sites may be the cause (consequence?) of a local structural reorganiza-tion. In a first time, it is interesting to know which elements (cations or oxygen anions) can be located into the interstitial sites. All the possible hypotheses were envisaged and discussed examining the consequence of the filling of these interstitial sites by various elements on the bonds and sites valences. The hypothesis of a settlement of 8b or 48f sites by cations (as well Fe 3+ as Zn 2+ ) could be eliminated since the occurrence of 8b cations would lead to the disappearance of the four first-neighbouring 16d sites because of the creation of too short M-M chemical bonds (face-sharing octahedral and tetrahedral cationic sites never existing). Such reorganization would so imply too expensive crystallographic network reorganization from an energetic point of view. Then, other solutions can be envisaged for the 8b/48f settlements: (i) to consider a reorganization around an isolated defect, (ii) to build small clusters constituted from recombination of several 8b/48f inserted anions (the consideration of clusters as possible defect goes in the direction of the studies drawn up from ab initio calculations [8]), or (iii) to consider that the 8b/48f anions can be located at the surface of the oxides.

For instance, we tried to illustrate possible network reorganization around an inserted 8b anion. The occurrence of extra 8b anions implies for the anion valence bond satisfaction and in order to limit network reorganization, the cationic filling of the four first 16d neighbours by Zn 2+ ions substituting for Fe 3+ ones. Moreover, the settlement of 8b site with an oxygen anion implies the disappearance of the four 32e first neighbours involving the disappearance of half of the six corners of the four 16d neighbours. Thus, the 16d neighbours become 4-coordinated (distorted tetrahedral sites) with three of their corners are 32e oxygen and one is the 8b inserted anion. A valence calculation of these ''modified'' 16d sites shows it can correspond to stabilization of Zn 2+ cations. Furthermore, this fourfold coordination is really consistent with the strong preference of the Zn 2+ cation for tetrahedral symmetry. The anion sub-network modification is compatible with the replacement of four 16d Fe 3+ cations by Zn 2+ cations which occupied preferentially the 8a sites. The 8a sites filled by Zn 2+ cations are probably the four ones affected by the elimination of the four 32e anions which are 8b sites first neighbours. Furthermore, the proposed cluster explains the source of the defect formation, i.e., the positioning and the energetic stability of the Zn 2+ cations on 16d ''tetrahedral'' sites.

The validation of this structural hypothesis (anions insertion on 8b/48f sites) comes from the significant improvement of the refinement with a model with one 8b sites for two 48f sites. The chosen code for each site occupancies corresponds to the composition feature Zn 1À3x [Zn 2x Fe 2À2x ]O (32e) 4À5.5x O (8b) 0.5x O (48f)

x ;

this code was established after a preliminary refinement performed on all occupancies. Moreover, this refinement procedure does not introduce supplementary adjustment parameters and can be directly compared with the previous ones. Notably, the RBragg factor decreases from 2.28% from the previous model until 2.03% for this last one. Furthermore, the isotropic displacement factors of the 16d and 8a positions become now correct considering the M-O bond distances and the electronic occupancies of the 8a and 16d sites (8a are the smallest sites occupied by the louder atoms). On the ZnFe 2 O 4 spinel composition, Mo ¨ssbauer analyses were also performed at 4 K and 298 K (spectra being reported in Fig. 5). At 4 K, the signal shows a sextuplet characteristic of antiferromagnetic order, and at 298 K, the signal shows a quadripolar doublet characteristic of a paramagnetic behaviour. The parameters of fitting are reported in Table 4. For both temperature, only one site is visible, the signal exhibiting only one contribution; the parameters relatives to this site (hyperfine mean filed value refined at 4 K is about 48 T) being characteristic of sixfold coordination. For the sample analysed at 4 K, even if the Mo ¨ssbauer signal is fitted with a double contribution, these two contributions converge through quite same hyperfine parameters relative to octahedral sites hence showing the absence of any tetrahedral sites contribution. Thus, Mo ¨ssbauer analyses tend to confirm the structural hypothesis of a lacunar but direct contribution for the ZnAl 2 O 4 spinel feature.

Conclusion

Herein it was proposed a new view of the ferrites networks (MgFe 2 O 4 /ZnFe 2 O 4 ) taking into account the occurrence of cationic vacancies in Td sites. In order to respect the chemical composition, the presence of these vacancies forces the framework to accept divalent cations in 16d sites which are formally octahedral environments and the occurrence of oxygen vacancies and/or oxygen in interstitial sites in order to limit energetic destabilization in clusters. These oxygen defects lead to consider that some ions in 16d site, probably Zn 2+ in the case of ZnFe 2 O 4 or even Fe 3+ ions in the case of MgFe 2 O 4 compound, are not in octahedral site but fourfold coordinated to oxygen in a strongly distorted tetrahedral site. After refinement by the Rietveld method and Mo ¨ssbauer characterisation, our proposed model seems more realistic than the classical fully or partially inverted spinel models previously described in the literature.

Fig. 1 .

 1 Fig. 1. Spinel electronic cartography of z = 0 and z = 0.125 plan.

Fig. 3 .

 3 Fig. 3. Fourier cartographies (Fobs-Fcal) of z = 0 (top) and z = 0.125 (bottom) plans of the MgFe 2 O 4 oxide. They are respectively from left to right obtained considering a fully inverted, a partially inverted or a partially lacunar model.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Fourier cartographies (Fobs-Fcal) of z = 0 (top) and z = 0.125 (bottom) plans of the ZnFe 2 O 4 oxide. They are respectively from left to right obtained considering a direct, a partially inverted or a partially lacunar model.

Table 1 M

 1 -O bonds lengths (and standard deviation) estimated from the Brown and Altermatt law.

	M-O bonds	Theoritical lengths	Experimental average lengths
			in MgFe 2 O 4 /in ZnFe 2 O 4
			Site
	16d	Mg-O: 2.099 A ˚; Zn-O: 2.110 A ˚; Fe-O: 2.015 A ˚B-O: 2.026 A ˚/2.030 A ˚Fig.

Site 8a

Mg-O: 1.949 A ˚; Zn-O: 1.962 A ˚; Fe-O: 1.865 A ˚A-O: 1.948 A ˚/1.974 A (b) oxides refined with the lacunar models.

Table 2

 2 Refined structural parameters for MgFe 2 O 4 considering the various cationic distribution models.

	Atom	Site	x	y	z	B iso (A ˚2)	SOF
	MgFe 2 O 4 refined as fully inverted spinel a
	Fe1	8a	1/8	1/8	1/8	1.6(2)	1
	Mg2	16d	1/2	1/2	1/2	À0.3(1)	0.5
	Fe2	16d	1/2	1/2	1/2	À0.3(1)	0.5
	O	32e	0.2590(4)	x	x	0.1(2)	1
	MgFe 2 O 4 refined as partially inverted spinel b
	Mg1	8a	1/8	1/8	1/8	0.54(7)	0.210(6)
	Fe1	8a	1/8	1/8	1/8	0.54(5)	0.790(6)
	Mg2	16d	1/2	1/2	1/2	0.43(6)	0.395(3)
	Fe2	16d	1/2	1/2	1/2	0.43(6)	0.605(3)
	O	32e	0.2560(2)	x	x	0.49(8)	1
	MgFe 2 O 4 refined as Fe 1À3x [Mg 1Àx Fe 1+x ]O 4À4x	c
	Fe1	8a	1/8	1/8	1/8	0.44(5)	0.87(1)
	Mg2	16d	1/2	1/2	1/2	0.52(4)	0.48(1)
	Fe2	16d	1/2	1/2	1/2	0.52(4)	0.52(1)
	O	32e	0.2560(2)	x	x	0.29(7)	0.96(1)

a Rp = 3.56%; Rexp = 3.49%; Rwp = 4.73%; RBragg = 7.5%. b Rp = 2.76%; Rexp = 3.64%; Rwp = 3.50%; RBragg = 3.55%. c Rp = 2.64%; Rexp = 3.49%; Rwp = 3.37%; RBragg = 2.86%.

Table 3

 3 Refined structural parameters for ZnFe 2 O 4 considering the various cationic distribution models.

	Atom	Site	x	y	z	B iso (A ˚2)	SOF
	ZnFe 2 O 4 refined as direct spinel a
	Zn1	8a	1/8	1/8	1/8	1.09(6)	1
	Fe2	16d	1/2	1/2	1/2	À0.36(6)	1
	O	32e	0.2612(4)	x	x	0.2(2)	1
	ZnFe 2 O 4 refined as partially inverted spinel b
	Zn1	8a	1/8	1/8	1/8	0.41(4)	0.140(6)
	Fe1	8a	1/8	1/8	1/8	0.41(4)	0.860(6)
	Zn2	16d	1/2	1/2	1/2	0.47(5)	0.930(3)
	Fe2	16d	1/2	1/2	1/2	0.47(5)	0.070(3)
	O	32e	0.2603(2)	x	x	0.82(6)	1
	ZnFe 2 O 4 refined as Zn 1À3x [Zn 2x Fe 2À2x ]O 4À4x	c
	Zn1	8a	1/8	1/8	1/8	0.48(3)	0.946(7)
	Zn2	16d	1/2	1/2	1/2	0.40(4)	0.018(4)
	Fe2	16d	1/2	1/2	1/2	0.40(4)	0.982(4)
	O	32e	0.2603(2)	x	x	0.81(6)	0.98(1)
	ZnFe2O 4 refined as ''defect'' Zn 1À3x [Zn 2x Fe 2À2x ]O 4À4x	d
	Zn1	8a	1/8	1/8	1/8	0.42(3)	0.936(7)
	Zn2	16d	1/2	1/2	1/2	0.48(4)	0.021(4)
	Fe2	16d	1/2	1/2	1/2	0.48(4)	0.979(4)
	Oi1	8b	0.625	1/8	1/8	0.78(6)	0.010(2)
	Oi2	48f	0.3436	1/8	1/8	0.78(6)	0.003(1)
	O	32e	0.2599(2)	x	x	0.78(6)	0.97(1)
	a Rp = 2.64%; Rexp = 3.03%; Rwp = 3.39%; RBragg = 5.07%.
	b Rp = 2.30%; Rexp = 3.13%; Rwp = 2.92%; RBragg = 2.26%.

c Rp = 2.30%; Rexp = 3.13%; Rwp = 2.86%; RBragg = 2.28%. d Rp = 2.23%; Rexp = 3.03%; Rwp = 2.84%; RBragg = 2.03%.