Laurent Ros

Hussein Hijazi

Eric Pierre Simon

Paths Complex Gain Tracking Algorithms for OFDM Receiver in Slowly-Varying Channels

Keywords: OFDM, Channel estimation, Tracking Loop, Rayleigh channel, Complex gains estimation

This paper deals with channel estimation for Orthogonal Frequency Division Multiplexing (OFDM) systems over time-varying fading channels. In conventional methods, the leastsquares (LS) estimate is obtained over the pilot subcarriers, and next interpolated over the entire frequency grid. Those methods only exploit the frequency-domain correlation of the channel. In this paper, we propose to exploit both the time-domain correlation and the specific features of the wireless radio channel. Assuming the availability of delay related information, we propose to track the variation of the paths complex amplitudes by means of online recursive algorithms. We developed two simple sub-optimal algorithms based on second-order loops which exhibit a reduced complexity compared to that of the widely popular Kalman algorithm. The error signal is based on the LS estimate of the path complex gains for the first loop, and on the steepest-descent method of the same LS cost function for the second loop. For each algorithm, we give derivations to correctly tune the loop coefficients. Simulation results over slow Rayleigh fading channel with Jakes' spectrum show that our algorithms outperform the conventional methods. Moreover, the Mean Square Error (MSE) of the first algorithm is closer to the Bayesian Cramer Rao Bound than that of a Kalman filter based on a first-order AutoRegressive approximation of the channel.

I. INTRODUCTION

Orthogonal Frequency Division Multiplexing (OFDM) is an effective technique for alleviating frequency-selective fading channels effects in wireless communication systems. In this technique, a wideband frequency-selective channel is converted to a number of parallel narrow-band flat fading subchannels which are free of Intersymbol Interference (ISI) and free (assuming negligible time variations within one OFDM symbol) of Inter-Carrier Interference (ICI). For coherent detection of the information symbols, reliable estimation of the gain of each subchannel in the OFDM system is crucial. Most of the conventional methods work in a symbol-by-symbol scheme by using only the correlation of the channel in the frequency domain (i.e the correlation between subchannels). Generally, they consist in estimating the channel at pilot frequencies and then interpolating the channel frequency response. The channel estimation at the pilot frequencies can be based on Least-Squares (LS) criterion, or for better performance on Linear-Minimum-Mean-Square-Error (LMMSE) criterion [START_REF] Hsieh | Channel estimation for OFDM systems based on comb-type pilot arrangement in frequency selective fading channels[END_REF]. Though the conventional methods can deal with time-varying L. Ros is with GIPSA-Lab, Image and Signal Department, BP 46, 38402 Saint Martin d'Hères, France (e-mail: laurent.ros@gipsa-lab.grenoble-inp.fr). H. Hijazi and E.-P. Simon are with IEMN lab, TELICE group, 59655 Villeneuve d'Ascq, France (e-mail: hijazihussein@yahoo.com, eric.simon@univ-lille1.fr). This work was supported in part by the ANR project LURGA. channels, the information of the time-domain correlation is not exploited. However, we have shown in [START_REF] Hijazi | Analytical analysis of Bayesian Cramer-Rao Bound for dynamical Rayleigh channel complex gains estimation in OFDM systems[END_REF] through online Bayesian Cramer-Rao-Bound (BCRB) analysis, that the channel estimation process of the current symbol can be largely improved by using the previous OFDM symbols. Some works have addressed the time-domain dynamics of the fading process to obtain an updated channel estimate. Chen and Zhang proposed in [START_REF] Chen | Kalman filter Channel estimator for OFDM systems in time and frequency-selective fading environment[END_REF] a structure which uses a Kalman-Filter estimator for each subchannel (exploits the time-domain correlation) and a linear combiner to refine the estimate of each subchannel (exploits the frequency-domain correlation). The complexity of the proposed structure increases with the number of subcarriers. But in practice, only few subcarriers can be used. Another interesting approach to address the problem is to use a parametric channel modeling which can effectively reduce the signal subspace dimension of the channel correlation matrix [START_REF] Yang | Channel estimation for OFDM transmission in multipath fading channels based on parametric channel modeling[END_REF]. Hence, channel estimation can be reduced to the simple estimation of certain physical propagation parameters, such as multi-path delays and multipath complex gains [START_REF] Yang | Channel estimation for OFDM transmission in multipath fading channels based on parametric channel modeling[END_REF] [5] [6] [START_REF] Hijazi | Joint Data QR-Detection and Kalman Estimation for OFDM Time-varying Rayleigh Channel Complex Gains[END_REF]. Thus, the channel frequency response can be estimated using an L-path channel model. In [START_REF] Yang | Channel estimation for OFDM transmission in multipath fading channels based on parametric channel modeling[END_REF], the ESPRIT (Estimation of Signal Parameters by Rotational Invariance Techniques) method is employed to acquire the initial multi-path time delays. With this information, a MMSE estimator is derived to estimate the channel frequency response. However, the optimal Wiener estimator remains complex and requires the knowledge of the secondorder statistical properties of the channel. In [START_REF] Simeone | Pilot-Based Channel Estimation for OFDM Systems by Tracking the Delay-Subspace[END_REF], the delaysubspace (assumed invariant over several symbols) is tracked by a subspace-tracking algorithm, and the fast variation of the path amplitudes is tracked separately by a subspace-amplitude tracking algorithm. In [START_REF] Hijazi | Polynomial estimation of time-varying multi-path gains with intercarrier interference mitigation in OFDM systems[END_REF] [7], we have addressed the problem of path complex gains estimation and ICI reduction for the case of fast-varying Rayleigh channel (normalized Doppler spread f d T ≥ 10 -2 ). Based on a polynomial modeling of the (Jakes process) channel gains variation, we use a polynomial estimation over a block of OFDM symbols in [START_REF] Hijazi | Polynomial estimation of time-varying multi-path gains with intercarrier interference mitigation in OFDM systems[END_REF], and Kalman filtering with Auto-regressive (AR) model for the tracking of the polynomial coefficients in [START_REF] Hijazi | Joint Data QR-Detection and Kalman Estimation for OFDM Time-varying Rayleigh Channel Complex Gains[END_REF]. In fact, a Kalman-based method is quite complex and do not ensure to reach the BCRB in case of mismatch between the AR model and the true channel.

In this paper, we propose simplified multi-path complex gains tracking algorithms based on recursive sub-optimal techniques which closely approach the BCRB in the case of slowly channel variations (f d T ≤ 10 -2 ). These algorithms exploit both the time-domain correlation and the specific features of the wireless channel. In wireless radio channels, the complex gains show temporal variations while the delays are quasi-constant over a large number of OFDM symbols. Assuming the availability of delay related information as in [START_REF] Hijazi | Polynomial estimation of time-varying multi-path gains with intercarrier interference mitigation in OFDM systems[END_REF] [START_REF] Hijazi | Joint Data QR-Detection and Kalman Estimation for OFDM Time-varying Rayleigh Channel Complex Gains[END_REF], we propose to track the complex gains variation by means of on-line recursive algorithms. The two proposed algorithms are based on a second-order loop. Thus, complex gains increments are also estimated in order to improve the prediction for the next iteration, exploiting the time-domain correlation. The error signal of the first loop is based on the LS estimate of the path complex gains, whereas the error signal of the second-loop is based on the steepest-descent method of the same LS cost function. For each algorithm, we give derivations to correctly tune the loop coefficients. Simulation results compared to the performance of the Kalman filter-based algorithm and to the BCRB validate the proposed algorithms.

The paper is organized as follows: Section II describes the system model. Section III derives the two suboptimal algorithms, whereas Section IV gives the Kalman algorithm. Finally, the different results are discussed in Section V.

Notations : [x] k denotes the kth entry of the vector x, and [X] k,m the [k, m]th entry of the matrix X (indices begin to 1). I N is a N × N identity matrix. diag{x} is a diagonal matrix with x on its diagonal, diag{X} is a vector whose elements are the elements of the diagonal of X. J 0 (•) is the zeroth-order Bessel function of the first kind. ∇ x represents the first partial derivatives operator i.e., ∇ x = [ ∂ ∂x1 , ..., ∂ ∂xN ] T .

II. SYSTEM MODEL

A. OFDM Transmission over multi-path channel

Consider an OFDM system with N sub-carriers, and a cyclic prefix length N g . The duration of an OFDM symbol is T = vT s , where T s is the sampling time and

v = N + N g . Let x (n) = x (n) [-N 2 ], x (n) [-N 2 + 1], ..., x (n) [ N 2 -1]
T be the nth transmitted OFDM symbol, where {x (n) [b]} are normalized 4-QAM symbols. After transmission over a multipath channel and FFT demodulation, the nth received OFDM symbol y

(n) = y (n) [-N 2 ], y (n) [-N 2 + 1], ..., y (n) [ N 2 -1] T is
given by [START_REF] Yang | Channel estimation for OFDM transmission in multipath fading channels based on parametric channel modeling[END_REF] [6]:

y (n) = H (n) x (n) + w (n) (1)
where w (n) is a N × 1 zero-mean complex Gaussian noise vector with covariance matrix σ 2 I N , and H (n) is a N × N diagonal matrix with diagonal elements given by:

[H (n) ] k,k = 1 N L l=1 α (n) l × e -j2π( k-1 N -1 2 )τ l (2)
L is the total number of propagation paths, α l is the lth complex gain of variance σ 2 α l (with L l=1 σ 2 α l = 1), and τ l ×T s is the lth delay (τ l is not necessarily an integer, but τ L < N g ). The L individual elements of {α (n) l } are uncorrelated with respect to each other. Using (2), the observation model in [START_REF] Hsieh | Channel estimation for OFDM systems based on comb-type pilot arrangement in frequency selective fading channels[END_REF] for the nth OFDM symbol can be re-written as:

y (n) = diag{x (n) }F α (n) + w (n) (3)
where

α (n) = [α (n) 1 , ..., α (n)
L ] T is a L × 1 vector and F is the N × L Fourier matrix defined by:

[F] k,l = e -j2π( k-1 N -1 2 )τ l (4)
Note: the sub-optimal algorithms proposed in this paper can work without explicit a priori random or deterministic model for the path complex gain variations. However, we recall that for the very universal "Rayleigh model", the L complex gains are wide-sense stationary narrow-band complex Gaussian processes, with the so-called Jakes' power spectrum [START_REF] Wang | On verifying the first-order Markovian assumption for a Rayleigh fading channel model[END_REF] with Doppler frequency f d . It means that α (n) l are zero-means correlated complex Gaussian variables with correlation coefficients given by R (p)

α l = E[α (n) l .α (n-p) l H ] = σ 2 α l J 0 (2πf d T p).

B. Pilot Pattern

The N p pilot subcarriers are evenly inserted into the N subcarriers at the positions P = {p s | p s = (s -1)L f + 1, s = 1, ..., N p } with L f the distance between two adjacent pilots. As we will see with equation (26), N p must fulfill the following requirement: N p ≥ L. The received pilot subcarriers can be written as the sum of two components:

y p(n) = diag{x p(n) }F p α (n) + w p(n) (5)
where x p , y p and w p are N p × 1 vectors, and F p is the N p × L Fourier transform matrix with elements given by:

[F p ] k,l = e -j2π( p k -1 N -1 2 )τ l (6)

III. SUBOPTIMAL TRACKING ALGORITHMS

A tracking algorithm can be defined by an imposed structure, and a specific criteria (or "error signal") to specify some elements of the structure [START_REF] Haykin | Adaptive Filter Theory[END_REF]. In the following, we use a second-order recursive structure, and consider two possible error signals, which will lead to 2 possible algorithms.

A. Structure of the tracking algorithm 1) Structure:

The purpose is to estimate the channel coefficients α. The estimate of α (n) , noted α(n) (or α(n|n) ), is updated at a symbol rate by the computation of a loop error signal v ǫ(n) , which is next filtered by a digital loop filter. Inspired by the Phase-Locked-Loop (PLL) design [START_REF] Mengali | Synchronization Techniques for Digital Receivers (Applications of Communications Theory)[END_REF], we use a second-order closed-loop to get the ability to track potential time linear drifts of the parameters to be estimated. The general recursive equations or our loop are : [START_REF] Gazor | Prediction in LMS-type Additive Algorithms for Smoothly Time Varying Environments[END_REF] where µ 1 , µ 2 are the (real positive) loop coefficients.

Measurement Update Equations v ǫ(n) = f unction of { y p(n) ; α(n|n-1) } (7) α(n|n) = α(n|n-1) + µ 1 .v ǫ(n) (8) Time Update equations v Lag(n) = v Lag(n-1) + v ǫ(n) (9) α(n+1|n) = α(n|n) + µ 2 .v Lag(n)
The Measurement Update Equations are responsible for the feedback, i.e., for incorporating a new measurement y p(n) into the a priori estimate α(n|n-1) to obtain an improved a posteriori estimate α(n|n) . The Time Update Equations are responsible for projecting forward (in time) the current state α(n|n) and error estimates to obtain the a priori estimates for the next time step, α(n+1|n) . As in a Kalman filter, the Time Update Equations can also be thought of a predictor equations, while the Measurement Update Equations can be thought of a corrector equations. Note that at each iteration, we get in fact in µ 2 .v Lag an estimate of the speed of the parameter α, useful to predict the parameter evolution for the next iteration.

2) General properties: The estimation error of the tracking algorithm is defined as:

ǫ (n) = α (n) -α(n|n) (11)
Combining equations ( 8) and ( 10), we have that :

α(n|n) = α(n-1|n-1) + µ 1 .v ǫ(n) + µ 2 .v Lag(n-1) (12)
The previous equation confirms that in case of linear drift of the complex amplitudes (i.e. α (n) = α (n-1) + slope), it is possible to have no steady state error at the convergence (i.e. v ǫ = 0 and v Lag = 1 µ2 .slope). By using ( 9), the Z-domain transform of ( 12) leads to :

α(z).[1 -z -1 ] = [µ 1 + µ 2 .z -1 1 -z -1 ].v ǫ (z) (13)
In the following, we note F (z) = µ 1 + µ2.z -1 1-z -1 the first-order Lead / Lag filter applied to the error signal in order to obtain α(n|n) by increment from α(n-1|n-1) , according to equation [START_REF] Mengali | Synchronization Techniques for Digital Receivers (Applications of Communications Theory)[END_REF]. The error signal for each path l = 1, ..., L should be in average, proportional to the complex amplitude error for this path in the ideal case 1 . Then we have :

v (l) ǫ(n) = β (l) d .{α (l) (n) - α(l) (n|n) } + N (l) (n) (14)
where

N (l) (n) is a zero-mean disturbance called loop noise. The real coefficient β (l)
d is called the gain of the equivalent complex gain error detector (CGED). In the case where the CGED is the same for each path, (i.e. β (l) d = β d ), the equation ( 14) leads to the vector formulation :

v ǫ(n) = β d .{α (n) -α(n|n) } + N (n) (15)
So, in the Z-transform domain, assuming linear characteristic of the CGED (15), equation ( 13) leads to

α(z) = L(z).α(z) + L(z) β d .N (z) (16)
where L(z) is the closed-loop transfer function defined by:

L(z) = β d .F (z) 1 -z -1 + β d F (z) (17)
1 else we can define an equivalent to the S-curve used in PLL design [START_REF] Mengali | Synchronization Techniques for Digital Receivers (Applications of Communications Theory)[END_REF], and (14) will stand only for small errors (linear region of the S-curve). Replacing F(z) by the lead/lag filter expression, we get:

L(z) = β d (µ 1 -µ 2 ).(1 -z -1 ) + β d µ 2 (1 -z -1 ) 2 + β d (µ 1 -µ 2 ).(1 -z -1 ) + β d µ 2 (18)
The condition of stability of the causal rational system L(z) is obtained when all the roots of the denominator polynomial are inside the unit circle. For a second-order denominator polynomial p(z) = (β d µ 1 +1).[1+c 1 z -1 +c 2 z -2 ], the stability conditions (obtained by the Schur-Cohn test [START_REF] Porat | A course in digital signal processing[END_REF]) are :

|c 2 | < 1 and -1 < c 1 1 + c 2 < 1 (19)
with in our case :

c 1 = -2 -β d (µ 1 -µ 2 ) β d µ 1 + 1 and c 2 = 1 β d µ 1 + 1
We can rewrite L(z) in the frequency-domain, by making z = e pT , with p = j2πf , and f is the frequency variable. Assuming slow reaction of the loop during one OFDM symbol T , the digital loop transfer function is close (approximation -1 ≈ 1p.T ) to an analog second-order low-pass transfer function parametrized by natural pulsation ω n (or f n = ωn 2π ) and damping factor ζ, while ω n .T << 1 :

L(e pT ) ≈ 2ζω n p + ω 2 n p 2 + 2ζω n p + ω 2 n (20) with : (ω n T ) 2 = µ 2 β d (21) 2ζω n T = (µ 1 -µ 2 )β d (22)
The error variance can be numerically computed as σ 2 ǫ = σ 2 ǫα + σ 2 ǫN . According to ( 16) and ( 11),

σ 2 ǫα = + 1 2T -1 2T Γ α (f ).|1-L(e j2πf T )| 2
df is due to the high-pass filtering 2 of α (n) , and

σ 2 ǫN = + 1 2T -1 2T Γ N (f ). 1 β 2 d
.|L(e j2πf T )| 2 df is due to the low-pass filtering of N (n) . Fig. 1 gives the modulus in frequency-domain of the exact closed-loop filter L given in (18). The couple (f n , ζ) has to be properly chosen for a good trade-off between gain tracking ability and loop noise reduction, for a given SNR and f d T scenario. Special case of first-order loop: if µ 2 = 0, equations are reduced to L(z) =

β d µ1
(1-z -1 )+β d µ1 and then approximatively to a first-order low-pass transfer function : L(e pT ) ≈ ωc p+ωc with cut-off frequency ω c such that

(ω c T ) = µ 1 β d (23)
B. First algorithm : 1) Motivation: for each OFDM symbol, the Squares Error (SE) for the received pilot subcarriers is defined by :

S( α(n) ) = ζ H (n) .ζ (n) ( 24
)
where the N p × 1 error vector is

ζ (n) = y p(n) -diag{x p(n) }F p α(n) (25)
The LS-estimator of α (n) is :

a LS(n) = G (n) y p(n) (26)
where

G (n) = F H p diag{x p(n) } H diag{x p(n) }F p -1 F H p diag{x p(n) } H (27)
And assuming normalized QPSK data, the matrix inversion should be done only once (independent of the index n):

G (n) = F H p F p -1 F H p diag{x p(n) } H (28)
Thus, after LS estimation, we obtain :

a LS(n) = α (n) + ǫ w(n) (29)
where ǫ w(n) is a zero-mean complex Gaussian noise vector with correlation matrix E{ǫ w

(n) .ǫ H w(n) } = σ 2 . F H p F p - 1
2) Error signal for the first Algorithm: We use the difference between the LS estimator a LS(n) for the nth OFDM block and the predicted vector for this block, α(n|n-1) . The error signal vector is then :

v ǫ(n) = G (n) y p(n) -α(n|n-1) (30)
3) Analysis and loop coefficients tuning: Now, for the specific case of the first error signal defined in (30), we have from equations (26),(29),(8) that:

v ǫ (z) = (α(z) + ǫ w (z)) -( α(z) -µ 1 .v ǫ (z)) (31) leading to v ǫ (z) = α(z) -α(z) 1 -µ 1 + ǫ w (z) 1 -µ 1 (32)
We can conclude than the linear model ( 15) is strictly valid for the first algorithm, with a CGED gain given by :

β d = 1 1 -µ 1 ( 33
)
and a loop noise equal to N (n) = β d .ǫ w(n) . For the first algorithm, the stability conditions (19) are then:

0 < µ 1 < 2 and 0 ≤ µ 2 < 4 -2µ 1
And from ( 21) and ( 22), one given couple (ω n , ζ) of the second-order low-pass transfer function can be obtained in tuning (µ 1 , µ 2 ) as :

µ 1 = (ω n T ) 2 + 2ζω n T 1 + (ω n T ) 2 + 2ζω n T ( 34
)
µ 2 = (ω n T ) 2 1 + (ω n T ) 2 + 2ζω n T (35)
In this way, we finally have :

0 ≤ µ 2 < µ 1 ≤ 1.
Special case of first-order loop : if gain µ 2 = 0, the online estimation algorithm is reduced to an order 1 AR low-pass filtering of the LS estimator a LS(n) :

α(n|n) = (1 -µ 1 ). α(n-1|n-1) + µ 1 .a (36)
We have from ( 23) that µ 1 = ωcT 1+ωcT .

C. Second algorithm 1) Motivation: Instead of computing explicitly the LS estimator a LS(n) for each OFDM block, we can look for an iterative steepest descent procedure. In this way, we use same error signal that for an LMS (Least Mean Squares) algorithm, but inserted in a second-order loop versus a firstorder loop. This means finally to use the prediction in order to improve LMS-type adaptive algorithm as in [START_REF] Gazor | Prediction in LMS-type Additive Algorithms for Smoothly Time Varying Environments[END_REF]. Applying the stochastic gradient descent method means to take the partial derivatives of the SE, S( α), defined in (24) with respect to the individual entries of the vector α:

∇ α(S( α)) = 2.∇ α(ζ H ).ζ (37)
where the L × N p matrix ∇ α(ζ H ) contains in one given column the partial derivatives (relative to the components of α) for the corresponding pilot subcarrier. We obtain

∇ α(S( α)) = -2.F H p diag{x p } H .{y p -diag{x p }F p α} (38)
The successive corrections to the weight vector α must then be in direction opposite to the gradient vector ∇ α(S( α)).

2) Error signal for the second Algorithm: Inserted in the global structure of the tracking procedure, the error signal for the nth OFDM symbol is chosen proportional to the negative of the gradient vector of the SE predicted for this block, from the (n-1)th observation block:

v ǫ(n) = K H (n) .{y p(n) -K (n) α(n|n-1) } ( 39
)
where we define the

N p × L matrix K (n) = diag{x p(n) }F p .
So, if µ 2 = 0, the second tracking algorithm is exactly an LMS algorithm, with µ 1 as step-size parameter (and with α(n|n-1) = α(n-1|n-1) ).

3) Analysis and loop coefficients tuning: Using the observation equation ( 5), the error signal (39) can be rewritten: 8), the error signal versus the error ǫ (n) becomes :

v ǫ(n) = K H (n) K (n) {α (n) -α(n|n-1) } + K H (n) .w p(n) (40) Using (
v ǫ(n) = [I -µ 1 .Γ] -1 Γ.{α (n) -α(n|n) } +[I -µ 1 .Γ] -1 K H (n) .w p(n) (41)
where the L × L Hermitian matrix Γ = K H (n) K (n) is independent of index n when assuming normalized data symbols, with elements defined by [Γ] ll ′ = Np k=1 e j2π(τ l -τ l ′ ) . This elements are identical on the diagonal, equal to [Γ] ll = N p . Eq. ( 41) indicates that the CGED output of one given desired path may be influenced by an interference term depending on adjacent paths. This "inter-path interference" may increase the variance of the loop noise if the Hermitian matrix Γ is not a diagonally dominant matrix. This condition depends only on the delays distribution. If non-diagonal terms can be neglected, and if µ 1 N p << 1, the detector gain is approximatively:

β d ≈ N p 1 -µ 1 N p (42)
and according to (21)(22), the tuning of the coefficient of the second-order equivalent closed loop is given by replacing (µ 1 , µ 2 ) by (N p µ 1 , N p µ 2 ) in equations (34)(35). In this way, we finally have :

0 ≤ µ 2 < µ 1 ≤ 1/N p .
IV. REFERENCE ALGORITHM : KALMAN FILTER In order to compare the performance of the previous simple sub-optimal algorithms, we recall here the Kalman Filter processing, which can give the optimal performance for a socalled Linear Gaussian Problem [START_REF] Haykin | Adaptive Filter Theory[END_REF]. The Kalman filter is a recursive algorithm composed of two stages: Time Update Equations and Measurement Update Equations. In order to use Kalman filter, we first have to give a linear state-space representation of the problem. Classically, the flat fading Rayleigh channel can be well approached [START_REF] Wang | On verifying the first-order Markovian assumption for a Rayleigh fading channel model[END_REF] by an Autoregressive (AR) model. Most often, a first-order AR (AR1) model is used to model the variation of each path, α (n) l as :

α (n) l = γ.α (n-1) l + u (n) l
where γ = J 0 (2πf d T ) according to the Jakes' model, and u (n) l is zero mean Gaussian complex circular with a variance

σ 2 u l = σ 2 α l (1 -γ 2 ).
Based on the previous AR1 model of the gains evolution, the two stages of the so called AR1-Kalman algorithm are defined as: Time Update Equations: α(n|n-1) = γ. α(n-1|n-1)

P (n|n-1) = γ 2 .P (n-1|n-1) + U (43)
Measurement Update Equations:

K (n) = P (n|n-1) K H (n) K (n) P (n|n-1) K H (n) + σ 2 I Np -1 α(n|n) = α(n|n-1) + K (n) y p(n) -K (n) α(n|n-1)
P (n|n) = P (n|n-1) -K (n) K (n) P (n|n-1) (44)
where K (n) is the Kalman gain matrix and U = diag σ 2 u1 , ..., σ 2 uL . Note that the equations are similar to those of the second (LMS-based) algorithm with µ 2 = 0 by replacing the Kalman gain K (n) by µ 1 .K H (n) , which requires an additional matrix inversion at each iteration.

V. SIMULATIONS

In this section, the performance of the recursive algorithms is evaluated and compared to that of reference algorithms (LS and Kalman algorithms). The normalized channel model is GSM Rayleigh model [START_REF] Zhao | A novel Channel estimation method for OFDM Mobile Communications Systems based on pilot signals and transform domain processing[END_REF] [6] with L = 6 paths and maximum delay τ max = 10T s . A 4QAM-OFDM system with normalized symbols, N = 128 subcarriers, N g = N 8 subcarriers, N p = 16 pilots (i.e., L f = 8) and 1 Ts = 2M Hz is used. The MSE and the BER are evaluated under a slowly time-varying channel with f d T = 10 -2 (corresponding to a vehicle speed V m ≈ 140 km/h for f c = 1GHz). 2 shows the evolution of MSE versus SNR. First of all, we observe that the performance of the AR1-Kalman algorithm, despite its complexity, does not reach the BRCB [START_REF] Hijazi | Analytical analysis of Bayesian Cramer-Rao Bound for dynamical Rayleigh channel complex gains estimation in OFDM systems[END_REF] in the case of a slowly channel variation with f d T = 10 -2 . This may be due to the difference between the real (Jakes) channel model and approached (AR1) model used in the Kalman filter (actually AR1-Kalman algorithm would reach the associated BCRB if the channel was exactly an AR1 based channel). Secondly, for the first (LS-based) proposed algorithm, it is observed that with a first-order loop (with µ 1 = 1 and µ 2 = 0) the MSE is very close to the error obtained by the AR1-Kalman filter, especially for large SNRs. On the other hand, it is interesting to observe that for a second-order loop with the best loop parameters (Table I), the MSE is closer to the BCRB than for AR1-Kalman algorithm. According to Fig. 1, the closed loop transfer function for low SNRs, with the set of values (ζ = 0.5; f n T = 2f d T ), approaches the Jakes Doppler spectrum shape. And for high SNRs, the set of values (ζ = 0.3; f n T = 15f d T ) permits to obtain a very large loop bandwidth. The corresponding loop coefficients are (µ 1 = 0.124; µ 2 = 0.0138) for SNR = 0dB, and (µ 1 = 0.647; µ 2 = 0.314) for SNR = 35 dB. It is then observed that the best performance are always obtained with a damping factor around ζ = 0.5 (and even less in high SNRs Region). This point reveals the advantage of a second-order loop versus a first-order loop (i.e. µ 2 = 0). It emphasizes then the benefit of the integration, that is inherent to the second-order loop, but not included in the AR1-Kalman algorithm. Of course, in the Kalman algorithm, larger AR model orders could be used to reduce the mismatch with the true channel (in predicting also the slope) and go toward optimal performance, but at the expense of the complexity. Finally, for the second (LMS-based) algorithm, the MSE is larger than that of the first algorithm but is lower than that of the AR1-Kalman for low and moderate SNRs. According to the theoretical analysis, this is due to a non favorable distribution of the delays for the Rayleigh channel. The non diagonal dominant property of the matrix Γ for the Rayleigh channel (ratio between the energy of the main and secondary diagonal is only around 1.3) yields "interpath interference" (IPI) which increases the loop noise variance. For high SNRs, the error variance reaches a floor, since the IPI becomes dominant with respect to the additive noise. The best choice of the natural frequency f n , according to table I, seems different than that of the first algorithm, but the computation is also much less reliable because of the bad linear approximation (42) in presence of IPI.

Fig. 3 gives the BER performance of our algorithms for f d T = 10 -2 (using a Zero-Forcing Equalizer), compared to the conventional algorithms of [START_REF] Hsieh | Channel estimation for OFDM systems based on comb-type pilot arrangement in frequency selective fading channels[END_REF] (LS criterion based only on the current symbol, with low-pass frequency interpolation (LPI)). For the sake of comparison, we also plotted the BER obtained with perfect knowledge of the channel. It is obvious that our algorithms outperform the conventional method, since we use the previous symbols in estimation process. Moreover, the BER results of our algorithms, the AR1-kalman and the reference (perfect knowledge of channel) agree with the MSE results. The BER performance of the different algorithms is very close due to the use of QPSK symbols.

VI. CONCLUSION

Sub-optimal path complex gains estimation techniques for OFDM systems over slow-fading channels have been proposed. The methods are designed for the comb pilot pattern (i.e. each OFDM symbol carries equi-spaced pilot subcarriers) but can easily be generalized to others frequenciestime grid pilot patterns. Our algorithms require path delay information, that can be accurately obtained as in [START_REF] Yang | Channel estimation for OFDM transmission in multipath fading channels based on parametric channel modeling[END_REF] [START_REF] Hijazi | Joint Data QR-Detection and Kalman Estimation for OFDM Time-varying Rayleigh Channel Complex Gains[END_REF].

The key is to capitalize on the invariance of the delays of the channel during a large number of OFDM symbols. When combined with past estimations through a simple secondorder recursive loop, this allows to improve the tracking of complex amplitudes from the delays related information. The performance has been evaluated through simulations in terms of the MSE and BER, demonstrating the considerable benefits of the proposed algorithm compared to conventional methods. Moreover, without using accurate priori information about channel statistics, the performance is comparable (and even better for the first algorithm) to the more complex Kalman estimator, when the later is based only on a first-order Autoregressive approximation of the true channel.

Fig. 1 .

 1 Fig. 1. (exact) Closed loop transfer function L(z = e j2πf T ) for normalized natural frequency fnT = 2.10 -2 (continuous line) and fnT = 2.10 -4 (dashed line), for various damping factor ζ.

8 Fig. 2 .Fig. 3 .

 823 Fig. 2. MSE vs SNR for f d T = 10 -2

  Table I gives the loop coefficients used, that yield around the best possible performance for the proposed algorithms.

	SN R	0dB	5dB	10dB	15dB	25dB	35dB
	fn (Algo 1)	2f d	2.5f d	3f d	4f d	6f d	15f d
	ζ	0.5	0.5	0.5	0.5	0.5	0.3
	fn (Algo 2)	7f d	8f d	10f d	15f d	20f d	23f d
			TABLE I
	LOOP COEFFICIENTS (FIRST / SECOND ALGORITHM)

Γα(f ) , Γ N (f ) : power spectrum density of l α (l) and l N (l) .


André De Palma

Dynamic and static congestion models: a review i

We begin by providing an overview of the conventional static equilibrium approach. In such model both the flow of trips and congestion delay are assumed to be constant. A drawback of the static model is that the time interval during which travel occurs is not specified so that the model cannot describe changes in the duration of congestion that result from changes in demand or capacity. This limitation is overcome in the Vickrey/Arnott, de Palma Lindsey bottleneck model, which combines congestion in the form of queuing behind a bottleneck with users' trip-timing preferences and departure time decisions. We derive the user equilibrium and social optimum for the basic bottleneck model, and explain how the optimum can be decentralized using a time-varying toll. They then review some extensions of the basic model that encompass elastic demand, user heterogeneity, stochastic demand and capacity and small networks. We conclude by identifying some unresolved modelling issues that apply not only to the bottleneck model but to trip-timing preferences and congestion dynamics in general

Introduction

This paper provides a brief introduction to dynamic congestion models, based on the [START_REF] Vickrey | Congestion theory and transport investment[END_REF] bottleneck model which has become the main workhorse model for economic analysis of situations involving congestion dynamics.

The word dynamic can have several possible meanings. One possibility is that it relates to the way traffic systems evolve and users learn from day to day. In the context of the bottleneck model, it relates to intra-day timing, i.e. to the interdependencies between traffic congestion at different times within a given day.

We shall discuss dynamic approaches against the background of static models. Static models assume that congestion is constant over some given time period. A congestion law provides the travel time as a function of the entering flow. The time dimension is not explicitly involved: all quantities are computed as single figures specific to a time period.

The basic static model considers a network comprising nodes and links. The nodes are centroids of zones, associating trip ends within a zone with a point that is a node in the network. Links connect the nodes. A cost function describes the cost of using each link. Congestion means that the cost increases as the number of users of the link increases. The demand is given by the origin-destination (O-D) matrix, indicating the number of trips between pairs of nodes. The solution involves the choice of route within the network for each O-D pair. Traffic volume on each link, the travel cost of using each link, the cost of making each trip, and the total travel cost for all users all depend on these route-choice decisions.

Each user for each O-D pair is assumed to choose a route in the network that minimises the sum of link costs for the trip. But users compete for the same space and the route choices of users in one O-D pair affect the costs experienced by other users through congestion. We can imagine a process where users keep revising their route choices in response to the route choices of other users. We seek an equilibrium in which no user can reduce his cost by choosing a different route. This equilibrium concept is due to [START_REF] Wardrop | Some Theoretical Aspects of Road Traffic Research[END_REF]. This problem was first given a mathematical formulation and solution for a general network by [START_REF] Beckmann | Studies in the Economics of Transportation[END_REF]. We will discuss the static model in more detail below in the context of simple networks.

The static model remains a basic tool for the mathematical description of congested networks. The static model does, however, omit important features of congestion. The static model is hence unsatisfactory for a number of purposes.

The main feature that the static model omits is that congestion varies over the day, with pronounced AM and PM peaks in most cities. Travel times can easily increase by a factor two from the beginning to the height of the peak. To design and evaluate policies for tackling congestion it is necessary to recognize these variations. There are a number of fundamental features of congested demand peaks that a model should take into account.

First, travellers choose not only a route, but also a departure time in response to how congestion varies over the course of a day. When a policy is implemented that affects peak congestion, travellers respond by changing departure time. The departure time changes are systematic on average and can be observed in the aggregate temporal shape of the peak. Think, for example, of car traffic entering the central business district (CBD) of some large city. The number of travellers reaching their workplaces per hour is fixed at the capacity rate during the morning peak. So if the number of workplaces in the CBD increases, the duration of the morning peak must increase too. Similarly, if capacity is increased the duration of the peak will shrink. The duration of the peak thus depends on both demand and capacity. Such observations suggest that trip timing is endogenous and speak in favour of dynamic models.

Second, travellers incur more than just monetary costs and travel time costs when they make a trip. Travellers have preferences regarding the timing of trips and deviations from the preferred timing are costly. Such scheduling costs are comparable in magnitude to congestion-delay costs as a fraction of total user costs. These scheduling costs are by nature ignored in static models. This means that static models cannot reveal the effect of policies that affect scheduling costs.

Third, many relevant policies can only be described within a dynamic model. A congestion toll or parking fee that varies over time as congestion increases and decreases is an obvious example.

The basic dynamic model discussed in this paper, the bottleneck model, starts directly from the above observations regarding within-day dynamics. It is therefore well suited to analyse policies that rely on these dynamics. It was introduced by William Vickrey (1969). Arnott, de Palma, and Lindsey (1993a) revisited and extended this seminal but almost forgotten model. It is a tractable model and it leads to a number of important insights. The model features one origin-destination pair (let us say residence and workplace), one route, and one bottleneck. The bottleneck represents any road segment that constitutes a binding capacity constraint. The bottleneck allows users to pass only at some fixed rate. There is a continuum of users and it takes some positive interval of time for them all to pass the bottleneck. Users are identical and they wish to arrive at the destination at the same ideal time * t . Because of the bottleneck, all but one user must arrive either before or after * t .

Deviation from * t represents a cost for users. They also incur a travel time cost, which includes free flow travel time and delays in the bottleneck. Individuals choose a departure time to minimise the sum of schedule delay and travel time costs.

To analyse this situation, we consider an equilibrium in which no traveller has incentive to change his departure time choice. This is an instance of a Nash equilibrium [START_REF] Haurie | On the relationship between Nash-Cournot and Wardrop equilibria[END_REF], which is the natural generalisation of Wardrop equilibrium. Individuals are identical and therefore they experience the same cost in equilibrium. One might wonder whether the Nash equilibrium concept has any counterpart in the real world. We see Nash equilibrium as a benchmark. Like anything else in our models, it is an idealisation, describing a situation that we hope is not too far from reality. The appeal of Nash equilibrium is that it is a rest point for any dynamic mechanism whereby informed travellers revise their (departure time) choice, if they do not achieve the maximum utility available to them.

Travellers incur the same generalised travel cost in equilibrium, but they have different trips. Some depart early, experience only a short delay at the bottleneck, but arrive early at work. Others avoid queuing delay by departing late, but arrive also late at work. Those who arrive near the preferred arrival time will experience most congestion and have the longest travel time. In this way, the bottleneck model describes a congested demand peak with a queue that first builds up and then dissolves.

The endogenous choice of the departure time was independently studied by de Palma, Ben-Akiva, Lefèvre & Litinas (1983), who proposed a dynamic model incorporating a random utility departure time choice model and a generalised queuing model. In contrast to the Vickrey bottleneck model, where the capacity constraint is either active or not, the supply model of de Palma et al. shifts smoothly from the uncongested to the congested regime.

An area of economic literature has grown out of these two initial contributions, exploring a number of issues in the context of the basic bottleneck model: e.g., equilibrium, social optimum, decentralization of the social optimum via pricing, second best pricing (including step tolls), elastic demand, heterogeneous individuals, small networks (routes in parallel and routes in series), stochastic capacity and demand, alternative treatments of congestion, and pricing on large networks. The basic model has also been extended to include mode choice, parking congestion, modelling of the evening commute and non-commuting trips. The research stream initiated with M. Ben-Akiva had more focus on numerical computation, and it has led, amongst other development, to the METROPOLIS software for large networks, discussed below.

This paper first reviews the simple static model of congestion, where time is not explicitly considered. This serves as a background for the dynamic model. We then introduce the basic bottleneck model and continue to discuss some of the extensions mentioned.

The static model of congestion ii

Static networks

We begin with a simple example. Consider a fixed number 0 N  of travellers having two routes available. The travellers split with 1 0 n  on the first route and 2 0 n  on the second route, where 1 2 n n N   . The cost associated with each route is taken to be a linear function of traffic such that the average cost on route i is  

i i i i i C n a b n  
. The cost is a so-called generalised cost, combining monetary cost and travel time in a single monetary equivalent. The Nash equilibrium occurs when no traveller wants to change route, which requires that    

1 1 2 2 C n C n 
. Solving this equation leads to the equilibrium solution iii

2 1 2 1 2 1 1 2 1 2 , e e e a a b n Nn N n b b b b        .
The Nash equilibrium has every traveller minimise his/her own cost. We can alternatively consider social optimum where the total cost for all travellers is minimised. In general the social optimum is not a Nash equilibrium. The social optimum minimises the total cost function

  1 2 , 1 2 1 1 1 2 2 2 min , ( )
( ) n n W n n n C n n C n   .
The total cost associated with use of route i is

  i i i n C n . The marginal cost of an additional user is     i i i i i i i i d n C n C n b n dn       .
In this expression,   i i

C n is the cost paid by the marginal user. The remainder i i b n is an externality:

it is the part of the increase in the total cost that is not borne by the additional user. The first-order condition for social optimum requires equal marginal costs, or

    1 1 1 1 2 2 2 2 C n b n C n b n    . (1.1)
The only difference between this and the first-order condition for the equilibrium is the terms representing the externalities of the two routes. The externalities are zero if 0

i b  , i=1,2, i.e. if
adding an additional user does not lead to increased travel cost. In this case, the social optimum would be the same as the equilibrium.

The social optimum has

0 2 1 2 1 2 1 1 2 1 2 2 , 2 2 2 2 o o a a b n Nn N n b b b b        . (1.2)
The solution is written in this way to emphasise the similarity to the Nash equilibrium. The only difference between the optimum and the equilibrium outcomes is that the marginal costs, the i b , have been replaced by 2 i b in the expression for the optimum outcome. This indicates that the optimum can be achieved as an equilibrium outcome by setting a toll equal to i i n b on each of the two routes. This has the effect of doubling the variable cost from the perspective of users and the expression in (1.2) then becomes the equilibrium outcome.

Elastic demand

The discussion so far has considered a fixed number of travellers N . We now allow demand to be elastic, limiting attention to just one route. Travellers on this route are identical, except for different willingness to pay to travel. Figure 1 shows a downward-sloping inverse demand curve   D N to reflect that demand decreases as the cost increases. The curve   C N is again an average cost curve expressing the cost that each traveller incurs. The curve

 

MC N is a marginal cost curve, expressing the marginal change in total cost following a marginal increase in the number of travellers; in other words iv

      ' MC N C N N C N    .
When the cost curve is increasing, the marginal cost curve will lie above the cost curve. The equilibrium occurs at the intersection of the demand curve with the average cost curve at the point b. The marginal traveller at this point is indifferent between travelling and not travelling, he faces a cost corresponding to the line segment a-b and a benefit of the same size. For travellers in aggregate, however, the cost of adding the marginal traveller is given by the MC curve. For the marginal traveller at point b, this cost corresponds to the line segment a-c. So the last traveller imposes a net loss corresponding to the line segment b-c on the group of all travellers. If usage was reduced to the point where the MC curve crosses the demand curve, then the corresponding loss is zero for the traveller at the point d. The total loss in market equilibrium is then represented by the shaded triangle b-c-d on the figure.

The optimal toll, labelled  in Figure 1, implements the optimum at the point d, where the private benefit is equal to the marginal cost. The toll is required because drivers ignore the costs they impose on other drivers. The toll is just the difference, evaluated at the social optimum, between the marginal cost and the average cost, i.e. the externality.

The basic bottleneck model

We now introduce the basic Vickrey bottleneck model in its simplest form. Consider a continuum of 0 N  identical travellers, who all make a trip.   . This means that the time of departure is the same as the time of arrival at the bottleneck and that the time of exit from the bottleneck is the same as the time of arrival at the destination. Travellers depart from the origin according to an aggregate schedule, described in terms of the cumulative departure rate R , where   R a is the number of travellers who have departed before time a . So R is similar to a cumulative distribution function: it is proportional to the probability that a random traveller has departed before time a . R is increasing, since travellers never return.

Moreover,   0 R   and   R N   . The departure rate     ' a R a   , wherever R is differentiable.
The bottleneck can serve at most s travellers per time unit. Travellers who have not yet been served wait before the bottleneck. The bottleneck serves travellers in the sequence in which they arrived (first-in-first-out or FIFO). The bottleneck capacity is always used if there are travellers waiting before it.

Recall that Nash equilibrium is defined as a situation in which no traveller is able to decrease his cost by choosing a different departure time. Since travellers are identical, this definition reduces to the requirement that all travellers experience the same cost and that the cost would be higher for departure times that are not chosen by any travellers.

Denote the interval of departures and arrivals as

  0 1 , I a a  .
Let us consider some properties of Nash equilibrium. First, there will be queue from the time the first traveller departs until the last traveller departs, since otherwise there would be a gap in the queue and somebody could move into the gap to decrease cost. Second, the queue will end at the time the last traveller departs, since otherwise he/she could wait until the queue was gone and reduce cost. This shows that the departure interval is just long enough for all travellers to pass the bottleneck. Third, as the cost of the first and the last travellers are equal and since they experience no queue, they must experience the same cost due to schedule delay. These insights are summarised in the following equations.

1 0 / , a a N s   (1.4)     * * 0 1 t a a t        . (1.5)
Equation (1.4) ensures that arrivals take place during an interval that is just long enough that all travellers can pass the bottleneck. Equation (1.5) ensures that no traveller will want to depart at any time outside I . Solving these two equations leads to

* 0 * 1 , N a t s N a t s            
and the equilibrium cost for every traveller is

N N s s       .
This is linear in the number of travellers and so the simple static model could be viewed as a reduced form of the dynamic model. Equations (1.4) and (1.5) are extremely useful in that they determine the equilibrium cost of travellers as a function of the number of travellers and the bottleneck capacity. The total cost is then

2 / N s  with corresponding marginal cost 2 / N s 
, of which half is internal cost to each traveller and the other half is external. The marginal change in total cost following a change in capacity s is

2 2 / N s   . Since
      0 0 max , 0 max , 0 R a R a R a N a a s s s s                        .
Differentiating this expression leads to

      0 0 , 0 , 0 R a s a s a R a s a s                     
during interval I . A few observations are immediately available. Initially the departure rate is constant and higher than s (since    ). It is high until the traveller who arrives exactly on time.

Later travellers depart at a constant rate which is lower than s .

Figure 3 shows the resulting departure schedule. The horizontal axis is time and the vertical axis is the number of departures, ranging from 0 to N . The thick kinked curve is the cumulative departure rate R . Departures begin at time 0 a and end at time 1 The traveller departing at time d exits the bottleneck exactly at time * a . Therefore the departure rate drops below capacity at this time and the queue begins to dissolve. It also follows that the queue reaches its maximum length at time d .

a with   1 R a N  .
For the top half of the figure, the horizontal time axis refers both to the departure from the origin and to the arrival time at the destination. For the bottom half of the figure, the time axis instead refers to the arrival time at the destination. The shaded areas on the bottom half of Figure 3 show the composition of the scheduling cost throughout the peak. The first traveller arrives early and is not delayed in the bottleneck so his cost is

Optimal tolling

The queue that arises in equilibrium in the bottleneck model is sheer waste. It generates no benefit at all. If travellers could be induced to depart at the capacity rate s during the equilibrium interval I , then there would be no queue. All travellers (except the very first and the very last) would gain from reduced travel time while arriving at the destination at exactly the same time as in equilibrium. A main insight of the bottleneck model is that it is possible to achieve this outcome through the application of a toll.

So consider a time varying toll   0    charged at the time of arrival at the bottleneck. We make the additional behavioural assumption that travellers choose departure time to minimise the sum of the toll and the trip cost. We restrict attention to tolls that have    

0 1 0 a a    
and are zero outside the departure interval I . This means that (1.4) and (1.5) still apply. If the toll is well- behaved, in ways to be explained below, then Nash equilibrium exists and departures still occur in the interval I . Therefore the equilibrium cost is the same as in the no-toll equilibrium discussed above.

Travellers do not lose, but somebody else may gain since revenue from the toll can be used for other purposes. The size of the toll revenue is

  1 0 a a s ds   , (1.6)
and this represents a net welfare gain.

Since the cost must be constant in equilibrium, we have

    0 , R a N a c a a s s            , (1.7)
where R is now the departure rate that results when the toll is imposed. It is (intuitively) clear that maximal efficiency is attained when the toll revenue is as large as it can be without destroying the

        , m a x , 0 m a x , 0 N N a c aa a a s s             
for a I  and zero otherwise. This toll is initially zero at time 0 a . Then it increases at the rate  until it reaches a maximum of / N s  at time 0. It then decreases at the rate  until it is again zero at time 1 . a The optimal toll corresponds to the grey shaded area in Figure 3. In a sense, it just replaces the cost of queueing by a toll. The efficiency gain is achieved because queueing is pure waste whereas the toll revenue is just a transfer.

Elastic demand

The discussion of the bottleneck model so far has assumed demand to be inelastic. A natural extension is to assume that the number of travellers deciding to participate in the peak depends on the equilibrium cost (Arnott et al., 1993a). The trip cost

      0 , p a c a a R a s     (1.8)
is the same for all travellers in equilibrium. This implies that the total toll payment is

  N p c   ,
where c is the average scheduling cost of travellers. Let    

0, ' 0 N N     be a downward sloping demand function such that   N p is the realised demand.
This is a very convenient way to extend the model: conditional on any equilibrium number of travellers, the properties of equilibrium are exactly the same as in the inelastic case. The equilibrium number of travellers is uniquely determined since demand is decreasing as a function of the equilibrium cost of travellers while the equilibrium cost of travellers is increasing as a function of the number of travellers. This simplicity comes, however, at a cost as it requires separability between trip timing on the one hand and participation on the other.

The separability of trip timing and participation implies that the optimal toll with elastic demand is the same as in the case of inelastic demand. To see this, note first that the optimal toll is able to remove queuing, so the average cost of travellers remains equal to

      ' / N p c N s c p N p      .
Using this to evaluate the first-order condition for maximum of  

W p leads to / p N s   . That is,
the optimal price should equal the equilibrium scheduling cost. Using (1.8) shows that the optimal

toll is     / , a N s c a a    
, which is the same as in the case of inelastic demand.

Optimal capacity and self-financing

Consider now a situation in which the optimal toll applies while capacity s is supplied at cost   0 K s  , with ' 0 K  . We extend the social welfare function with the cost of capacity provision

        , p W p s N r dr N p c K s        .
For any given capacity s , the optimal value of    

/ , a N s c a a     is as shown above. Note that   1 / c N s c s s      .
This can be used to show that capacity is optimal when , in which case the optimal toll cannot finance the optimal capacity.

    ' sK s N p c    .
The self-financing result is also called the cost recovery theorem. It is an instance of a general self-financing theorem by [START_REF] Mohring | Highway Benefits: An Analytical Framework[END_REF], which assumes that travel cost is homogenous of degree zero in capacity and use. A number of results on self-financing are summarised by [START_REF] Verhoef | Self-Financing Roads[END_REF].

The optimal capacity can be computed in the three regimes: no toll, coarse step toll and optimal fine toll. It can be shown that the optimal capacity is the lowest for the optimal fine toll, intermediary for the coarse toll and larger for the no toll regime (see ADL, 1993, for a proof). Note that these proofs are correct with inelastic (and elastic) demand.

Scheduling preferences

General formulation

The      formulation of scheduling cost used above is a special case of more general scheduling preferences, introduced in this section. Below we revisit the bottleneck model from the perspective of these general scheduling preferences.

In order to describe the traveller choice of trip timing in a more general way, we formulate scheduling preferences for a given trip in the form of scheduling utility   We incorporate monetary cost by considering utility to be u   . In some cases it is more convenient to talk about cost, which will then be the negative of utility, i.e. u   . In either case, it is implied that there is separability between scheduling and monetary cost. That is, a constant cost does not affect the preferences regarding trip timing.

In some situations it is necessary to specify scheduling utility further by imposing a certain functional form. For example, the      formulation specifies the scheduling cost completely up to a few parameters. Such restriction can be necessary for reasons of identification in econometric work, but in general it is preferable to specify as little as possible, since restricting the model entails the risk of introducing errors. In theoretical models it is similarly preferable to work with general formulations, since otherwise there is a risk that the results one may obtain depend on the specific formulation.

In some cases it may be considered acceptable to impose a separability condition, just as we have done in the case of monetary cost and trip timing. The timing of the trip is given by a departure time and an arrival time and we work under the assumption that these times are all that matter about trip timing. The travel time is the difference between the departure time and the arrival time. We could equivalently describe trip timing in terms of travel time and arrival time or in terms of travel time and departure time. From the perspective of general scheduling utility   1 2 , u t t , this leads to three possibilities for introducing a separability condition.

                  1 2 2 2 1 1 2 2 1 2 1 2 1 2 , , ,
u t t f t t g t u t t f t t g t u t t f t g t        
The first condition would say that scheduling utility is separable in travel time and departure time.

The second condition would say instead that scheduling utility is separable in travel time and arrival time. The      scheduling cost is a special case of this second possibility: Changing the travel time does not affect the traveller preferences regarding arrival time and vice versa. The third possible separability condition is used in the Vickrey (1973) formulation of scheduling preferences that we will consider in the next section. Here scheduling utility is separable in departure time and arrival time. That is, changing departure time, does not affect the preferences regarding arrival time and vice versa. The concept of the preferred arrival time * t was used to define the      scheduling cost. It makes sense to talk about a preferred arrival time when there is separability in travel time and arrival time, since then the preferred arrival time is not affected by the travel time. Without this separability, there is no single preferred arrival time since the preferred time to arrive depends on the travel time. If instead scheduling utility is separable in departure time and travel time, then we would want to talk about a preferred departure time. In some contexts, for example the PM commute from work to home, this might be a more natural concept. In general, neither the concept of a preferred arrival time nor a preferred departure time may be relevant. We shall now discuss Vickrey (1973) scheduling preferences, which are separable in departure time and arrival time. Vickrey (1973)

      1 2 1 2 1 2 1 2 , t T T t u t t s ds s ds       . (1.9)
The formulation is illustrated in Figure 4.

Figure 4. Vickrey (1973) scheduling preferences Note that when 1 T and 2 T are fixed, these numbers can be replaced by arbitrary numbers in (1.9) without affecting the implied preferences. Assume that 1 1 0, ' 0

    , 2 2 0, ' 0    
          2 , u t d t d d t d d d        . 1 T 2 T 1 t 2 t 1  2  * t
This is strictly increasing as a function of d . Using survey data on stated choice, [START_REF] Tseng | Value of time by time of day: A stated-preference study[END_REF] provide empirical estimates of time varying utility rates corresponding to the Vickrey (1973) model.

The cost of travel time variability

When travel time is random and travellers are risk averse, the random travel time variability leads to additional cost, the cost of travel time variability. Both Vickrey formulations of scheduling preferences are useful for deriving measures of the cost of travel time variability as well as of the scheduling impact of the headway of scheduled services. Such cost measures can be useful to incorporate elements of dynamic congestion in reduced form in static models. Consider a traveller who is about to undertake a given trip. The travel time for the trip is random from the perspective of the traveller. While he/she does not know the travel time outcome before making the trip, the traveller knows the travel time distribution. The travel time distribution is independent of the departure time of the traveller. The latter is a strong assumption but necessary for the results

The traveller is assumed to choose his departure time optimally, so as to maximise his/her expected scheduling utility. That makes the expected scheduling utility a function just of the travel time distribution. Therefore it is possible in principle to evaluate how the expected scheduling utility depends on the travel time distribution. Simple expressions are available for the two Vickrey specifications of scheduling preferences.

In the case of      preferences, [START_REF] Fosgerau | The value of reliability[END_REF] show that the expected trip cost with optimal departure time is

      1 1 s ds                 ,
which is linear in the mean and in the standard deviation of travel time. This is a practical advantage in applications. The expression depends on the shape of the travel time distribution through the presence of  in the integral and so  must be taken into account if the marginal value of standard deviation of travel time is to be transferred from one setting to another. In the same vein, Fosgerau (2009) uses      scheduling cost to derive simple expressions for the value of headway for scheduled services. In the case of Vickrey (1973) scheduling preferences with linear utility rates, [START_REF] Fosgerau | The value of travel time variance[END_REF] carry out a parallel exercise. They show that with random travel time and unconstrained choice of departure time, the expected scheduling cost with the optimal choice of departure time is linear in travel time, travel time squared and the variance of travel time. Parallel results are also provided for the value of headway for scheduled services. In contrast to the case of      scheduling cost, it is possible also to derive a simple expression for the expected scheduling cost for the case of a scheduled service with random travel time.

The bottleneck model revisited

The results discussed above for the basic bottleneck model survive in some form with more general scheduling preferences. The setup of the model is as before, the only change is that now travellers are only assumed to have scheduling preferences of the general form discussed above.

Without loss of generality we may again consider 1 2 0 d d   , since the exact form of scheduling preferences is not specified.

It is easy to argue, using the same argument as in the simple case, that Nash equilibrium requires departures in an interval

  0 1 , I a a  satisfying 1 0 / , a a N s   (1.10)     0 1 . v a v a  (1.11)
This is illustrated in Figure 5. Moreover, the queue has length zero at time 0 a and 1 a but it is strictly positive at any time in the interior of this interval. The second condition (1.11) has a unique solution since v is quasiconcave and it ensures that no traveller will want to depart at any time outside I .

Figure 5. The function v and the equilibrium departure interval Equations (1.10) and (1.11) determine the equilibrium utility of travellers as a function of the number of travellers and the bottleneck capacity. It is then straightforward to derive the marginal external congestion cost and the marginal benefit of capacity expansion.

As in the basic model, there is always a queue during the interval I and a traveller arriving at the bottleneck at time a exits at time

  0 / a R a s  .
Travellers are identical so they achieve the same scheduling utility in equilibrium is the same as in the no-toll equilibrium. As in the basic model, the optimal toll maintains the departure rate at capacity. The optimal toll is then given by      

    0 0 , R a v a u a a s         .
0 a v a v a   
for a I  and zero otherwise.

The conclusions regarding elastic demand extend to the case of general scheduling preferences. That is, the optimal toll is still p u    , which is the same as in the case of inelastic demand. The conclusions regarding optimal capacity and self-financing also carry over to the general case. That is, if capacity is supplied at constant cost and optimally chosen, then the optimal toll exactly finances the capacity cost.

Extensions of the bottleneck model

The bottleneck model is useful in many ways. It generates a number of insights concerning dynamic congestion, while being still relatively simple and tractable. The model is useful if the mechanisms it describes are representative of the real world. It is, however, a highly stylised description of actual congested networks. It is therefore of interest to extend the model by introducing more relevant features. Such an exercise has two main purposes. One is to gauge the robustness of the conclusions of the basic model. We can have greater confidence in conclusions that survive in more general versions of the model. The other main purpose is to generate new insights that were not available with the basic model. This section proceeds with a presentation of some of the extensions of the bottleneck model available in the literature.

Second best pricing

The optimal toll described above varies continuously over time. A real toll could do the same to any relevant degree of precision, but there remains the problem that travellers may not be able to understand such a complex pricing structure. Moreover, there may be technological reasons for varying tolls less frequently. Acceptability of road pricing is also a fundamental issue (see, e.g. de Palma, Lindsey & Proost, 2007, on this issue).

Such considerations have led researchers to consider tolls that vary in steps. In the context of the bottleneck, ADL (1990) consider the simplest step toll, namely a toll that is positive and constant during some interval and zero otherwise. Such a toll has also been called a coarse toll.

The discrete jumps of such a toll generate some new properties of the resulting equilibrium. Three groups of travellers can be identified according to whether they travel before, during or after the tolling period. Figure 6 compares the cumulative departure curve in the step-toll equilibrium and compares it with the no-toll equilibrium. Consider first the time before the toll is turned on. The cost of the last traveller not to pay the toll should be the same as the cost of the first traveller to pay the toll. To achieve this equality, there must be a period with no departures between these two travellers. Early in the morning travellers depart at a high rate, they pay no toll and consequently depart at the same rate as they would in no-toll equilibrium. Just before the departure time at which travellers would begin to pay the toll, departures cease for a while and the queue dissipates gradually as travellers are served by the bottleneck.

Departures start again when the queue has diminished just enough for the toll payment to be compensated by lower queueing time. The optimal single step toll is timed such that the queue has just disappeared at the time the toll kicks in. Departures for the group of travellers paying the toll then continue following the pattern analysed above. The toll is constant for these travellers and hence does not affect the departure rates. The departure rate is consequently high until the time at which a traveller arrives at the destination exactly on time, and then it drops to a lower level. The optimal single step toll is timed such that the queue has just disappeared at the time the toll lifts.

A new phenomenon emerges relating to the third and final group of travellers who do not pay the toll. As shown in Figure 6, there is no queue at the moment before they depart. But the first traveller to depart must have the same cost in equilibrium as the other travellers. This can only happen if there is a mass departure at this time. In a mass departure, travellers depart so closely together that their sequence in the queue is random. In this case, travellers are assumed to account for their expected trip cost.

It turns out that all the remaining travellers depart at once under the optimal coarse toll if   as has been found in most empirical studies. On average they are better off than a traveller who waits until the queue has gone before departing. But all travellers must achieve the same expected cost in equilibrium. Therefore the first traveller departs later under the coarse toll than under no toll.

Coarse toll equilibrium

Charging period ADL (1990) carried out their analysis for the case of a single step coarse toll. [START_REF] Laih | Queueing at a bottleneck with single-and multi-step tolls[END_REF]2004) extended this analysis to the case of multistep tolls using a slightly modified queueing technology in which some travellers can wait in a separate queue for the toll to lift, while those paying the toll pass the bottleneck. ix Laih then showed that at most n/(n + 1) of the total queueing time can be eliminated with the optimal n-step toll. [START_REF] Daganzo | A Pareto Improving Strategy for the Time-Dependent Morning Commute Problem[END_REF] also consider a step toll with the modified queueing technology. They divide travellers into two groups. Travellers from the first group are not liable to pay any toll. Travellers from the second group are liable to pay a constant step toll if they pass the bottleneck during the tolling period, otherwise they do not have to pay any toll. If the toll is high enough then travellers from the tolled group will avoid the tolling period. The tolling period is timed such that it fits exactly with the equilibrium departure interval of the untolled group. As a consequence, travellers from the untolled group can find an equilibrium during the tolling period and be strictly better off than without the scheme. Travellers from the tolled group are not worse off, since they travel during the same interval as without the scheme and avoid paying any toll by travelling outside the toll period. The essential insight is that the equilibrium cost is determined by the first and last travellers (as in (1.5) or (1.11)) as long as capacity is fully utilised during the departure interval.

The function of the toll in this example is to reserve the bottleneck capacity for a specific group of travellers during a specific interval of time. [START_REF] Shen | Pareto-improving ramp metering strategies for reducing congestion in the morning commute[END_REF] describe a mechanism that uses ramp metering to achieve a similar effect.

Random capacity and demand

ADL (1999) consider bottleneck congestion in a situation where capacity varies randomly from day to day. The ratio is fixed within a day and given the ratio the evolution of the queue is then deterministic. Travellers choose departure time without knowing the random ratio of the day. They are assumed to find equilibrium in expected utility given the information they have. ADL identify circumstances in which the static model is not consistent with a reduced form of the dynamic model. A perhaps surprising result is that providing more information can decrease welfare when demand is elastic and congestion is not efficiently tolled. [START_REF] Lindsey | Cost recovery from congestion tolls with random capacity and demand[END_REF] considers self-financing in the bottleneck model with random capacity and demand. He finds that the Mohring-Harwitz self-financing theorem survives randomness as long as the information used to set the optimal toll is the same as the information that is available to travellers.

de [START_REF] De Palma | Random queues and risk averse users[END_REF] include random travel time variability in a different way. They consider the bottleneck model with fixed capacity but where the FIFO property of the bottleneck model is replaced by random queue sorting, where all travellers in the queue at any given time have the same probability of exiting the queue at that moment. A range of intermediate regimes is also considered. Equations (1.10) and (1.11) still apply and the results that follow from these hence also apply.

Queues take time to dissipate. This physical property of queues has implications for how queues evolve over the course of a day. An empirical regularity of congested demand peaks is that the mean travel time peaks later than the variance of travel time. [START_REF] Fosgerau | On the relation between the mean and variance of delay in dynamic queues with random capacity and demand[END_REF] shows how this phenomenon arises in a dynamic model of congestion with the ratio of demand to capacity being random.

Heterogeneity

An extension to the basic bottleneck model which is clearly very important is to allow for heterogeneity. The basic model describes travellers as having identical scheduling preferences and identical preferred arrival time. This is very far from reality. For example, using survey data, [START_REF] Fosgerau | Investigating the distribution of the value of travel time savings[END_REF] estimates the distribution of the value of travel time,  . After conditioning on a number of controls, he finds that the remaining variation in the value of travel time has more than a factor of 50 between the 20th and 80th percentiles of the value of travel time distribution. There is every reason to think that preferences regarding earliness and lateness are similarly heterogeneous.

One of the first questions to ask when such heterogeneity is allowed in the bottleneck models is whether equilibrium still exists and whether it is unique. Analysis of the model would be severely complicated if this failed. This is the subject of [START_REF] Lindsey | Existence, Uniqueness, and Trip Cost Function Properties of User Equilibrium in the Bottleneck Model with Multiple User Classes[END_REF], who presents general conditions under which equilibrium exists in the basic bottleneck model extended with heterogeneity in the form of a finite number of homogenous groups of travellers. Lindsey provides a review of previous literature regarding preference heterogeneity in the dynamic model.

Parking

Parking is costly in that it competes for urban space with other uses. Cruising for parking is a significant contributor to urban congestion. Arnott and co-authors have published a series of papers on this and related issues, a recent reference is [START_REF] Arnott | Downtown parking in auto city[END_REF].

There are a few papers on downtown parking in a dynamic framework in which parking occupies space and the attractiveness of a parking space decreases with the distance to the CBD. ADL (1991) use the bottleneck model to assess the relative efficiency of road tolls and parking fees. Without pricing, drivers occupy parking in order of increasing distance from the CBD. A timevarying toll can prevent queueing, but does not affect the order in which parking spots are taken. Optimal location-dependent parking fees may be superior; they do not eliminate queueing, but induce drivers to park in order of decreasing distance from the CBD, thereby concentrating arrival times closer to work start times. Zhang, Huang and Zhang (2008) integrate AM and PM commutes with parking in this framework.

Small networks with dynamic congestion

This section considers some simple extensions from one link to small networks. Consider first two routes in parallel connecting an origin with a destination. There are 0 N  travellers with

n n T T s s        .
This is equivalent to (1.1) for the static model. It is straightforward to verify that the equilibrium number of travellers on route 1 is

  1 12 1 21 1 2 1 2 s ss n N T T s s s s        ,
and the equilibrium cost is

1 1 2 2 1 2 1 2 s T s T N C s s s s        .
This shows that two bottlenecks in parallel act just like a single bottleneck. The equivalent single bottleneck would have a fixed travel time that is a weighted average of the fixed travel times on the two routes and it would have a bottleneck capacity that is the sum of the capacities of the two routes. This result can be generalised to any number of parallel routes. A toll may be set at each bottleneck just as if it was a single bottleneck with elastic demand. As we have seen (page 6), the optimal toll does not affect the cost of using each route. Hence the split of travellers between routes is not affected by optimal tolling: The optimal toll does not reallocate between routes, but only across departure times. This is a very different conclusion than was reached in the static model, where the social optimum had a different allocation of travellers on routes than the equilibrium.

There is another situation in which several bottlenecks acts like a single bottleneck. This happens when bottlenecks are connected in a serial manner. In this case, the effective capacity is just the minimum of the bottleneck capacities. That is, the binding capacity constraint is that of the smallest bottleneck.

The property that parallel or serial bottlenecks can be reduced to a single equivalent bottleneck seems likely to survive if      preferences are replaced by general preferences. The description of the equivalent bottleneck does become more complicated. The property that equilibrium usage of the parallel routes is optimal also survives. ADL (1993b) analyse a Y-shaped network of bottlenecks to show that a Braess type paradox can arise: an increase in capacity can lead to increased cost. Analysis of more complicated networks is complicated and no general results on networks of bottlenecks seem to be available.

Large networks

The extension of the dynamic model to large networks remains a difficult problem. So far, existence and uniqueness of equilibrium have not been established (in spite of many attempts). The dynamic traffic assignment problem [START_REF] Merchant | A Model and an Algorithm for the Dynamic Traffic Assignment Problems[END_REF] is the subject of a large literature spanning several disciplines. [START_REF] Heydecker | Analysis of Dynamic Traffic Equilibrium with Departure Time Choice[END_REF] and Zhang & Zhang (2010) derive some analytical results.

Otherwise, the literature mostly uses numerical methods. Dynamic traffic assignment models are also difficult to work with numerically due to the dimensionality of the problem, which quickly becomes extreme. Consider a simulation model in which travellers choose the least-cost path through a network. Conditional on the actions of all other travellers, the problem of finding the least-cost path is feasible to solve using well-established algorithms [START_REF] Dijkstra | A note on two problems in connection with graphs[END_REF]. These algorithms are quite efficient but nevertheless require nontrivial time to execute. The dynamic version of such a model is formulated in continuous time; we may want to approximate it using discrete time steps of one second. In, say, a four hour peak period there are 14,400 possible departure time choices. In order to simulate the choice of departure time, we have to find the least-cost path for each possible departure time. Consider a city which can be adequately represented by a zone system of 500 zones. Then the OD-matrix, indicating the size of origin-destination flows is a 500 by 500 matrix with 25,000 entries. So the model will have to solve 3.6 billion shortest path problems through the network connecting the 500 zones. This will have to be done many times in order for such a simulation to identify an equilibrium in which no traveller will want to change his choice of departure time and route. The result is a huge computational problem and it is practically impossible to handle using a naive approach.

This section describes one approach taken to this problem, used in the model METROPOLIS [START_REF] De Palma | METROPOLIS -Modular System for Dynamic Traffic Simulation[END_REF]. The basic idea for reducing the amount of computation is to drop the assumption that travellers can choose the shortest path considering the whole network at once. At each intersection, travellers are able to observe the travel cost on each downstream link. But they do not observe the travel cost on links further downstream. Instead they are able to form an expectation regarding the travel cost from the next downstream nodes until the destination. Travellers then choose the next link with the smallest expected total cost to reach the destination, i.e. the smallest sum of the cost of the next link and the downstream expected cost. This portrays travellers as making dynamic discrete choices and these are readily formulated as a dynamic programming model using the Bellman principle. x,xi The simulation model looks for equilibrium using a process which can be interpreted as a dayto-day learning process. At the end of each day, the past outcomes for all travellers are pooled and this pool of information is common knowledge. During the next day, travellers have this information available when forming expectations. The idiosyncratic error terms are the same day after day (for departure time choice model). The choice of route can be either deterministic or stochastic (in such case, error terms are i.i.d. over space and time).

Other congestion functions

Henderson (1974) formulated a dynamic model of congestion using a similar setup to [START_REF] Vickrey | Congestion theory and transport investment[END_REF], but in which the travel time is determined by the flow at the time of departure and where flows departing at different times do not interact. [START_REF] Chu | Alternative congestion pricing schedules[END_REF] showed that the original Henderson formulation had problems due to nonexistence of equilibrium and proposed a reformulation in which travel time for a traveller is instead determined by the flow at the time of arrival at the destination. The Chu formulation has the Vickrey bottleneck as a limiting case.

Conclusions

This paper has presented an overview of dynamic models of congestion, focusing on results derived from the Vickrey bottleneck model. This model combines in a compact way the essential features of congestion dynamics. We have also argued that some fundamental features of congestion are inherently dynamic, which makes dynamic models indispensable for many purposes. In particular, dynamic models can be used to study a variety of policies that cannot be studied with static models. These include road pricing with a time-varying component, flexible work hours, staggered work hours, dynamic access control, and ramp metering used to differentiate capacity allocation. Pricing policies are much more effective when tolls depend on the time of the day, for stylised as well as for real networks (see [START_REF] Santos | [END_REF].

Research into congestion dynamics remains a very active area with many unresolved issues of high importance. We will mention a few here. Economic analyses using dynamic models of congestion are usually undertaken on the assumption that users are in Nash equilibrium. It would therefore be of interest to give general conditions under which Nash equilibrium exists (for general networks). It would further be of interest to specify learning mechanisms that would lead to Nash equilibrium. A learning mechanism is a rule that travellers use to update their choice of departure time and route in the presence of information concerning past outcomes. The existence of learning mechanisms leading to Nash equilibrium would support the presumption that the notion of Nash equilibrium is useful as a benchmark for actual congestion phenomena. Knowledge about learning mechanisms leading to Nash equilibrium may also be useful for the design of algorithms to find Nash equilibrium in simulation models.

Progress would also be desirable concerning the nature of scheduling preferences. The discussion in this paper has taken for granted that travellers are equipped with scheduling preferences and that these can be regarded as exogenous from the point of view of our analysis. Our transportation perspective has led us to be concerned with the timing of trips and we view travellers simply as having preferences regarding timing such that they can respond to circumstances by changing their trip timing in sensible ways. These times are hardly the fundamental objects of preference and, strictly speaking, it only makes sense to formulate preferences in these terms when circumstances such as the activities before and after the trip can be regarded as exogenous. This is, however, not a very appealing position. If I know that my trip will take more time, then I will adjust my schedule for the day to take this into account. I care, e.g., about not being late for appointments. But I make the appointments myself and so my scheduling preferences are a consequence of choice.

It is natural to ask why commuters mostly prefer to arrive at work at the same time. Various contributions have answered this question by pointing to agglomeration forces at the workplace, whereby productivity and wages are affected by the degree of overlap in work times, see [START_REF] Henderson | The economics of staggered work hours[END_REF], [START_REF] Wilson | Wage variation resulting from staggered work hours[END_REF], [START_REF] Hall | Temporal agglomeration[END_REF]. If this view is correct, then changes to the transport system will affect agglomeration, which in turn will affect commuter scheduling preferences. It remains to be seen how such mechanisms matter for our understanding of the effect of transport policies.

Endogeneity of scheduling preferences may also matter for the value of information. Consider a trip exposed to random travel time variability. At some point in time I will learn the size of delay. If scheduling preferences are exogenous, then it only matters whether I learn about the size of the delay soon enough to adjust my departure time. If scheduling preferences are endogenous, then it also matters whether I learn about the size of the delay soon enough to adjust my schedule [START_REF] Kreps | Temporal Resolution of Uncertainty and Dynamic Choice Theory[END_REF] consider dynamic choice behaviour under conditions of uncertainty, with emphasis on the timing of the resolution of uncertainty.

As discussed in this paper, the current state of the topic of dynamic congestion modelling provides a range of general insights from small stylised models. Numerical simulation models exist to deal with the complexities of real size networks. In between, there is a large gap. Numerical simulation has the drawback that it must rely on particular assumptions, which may or may not provide good approximations to the object of interest. So a main motivation for continued theoretical research into dynamic models of congestion is the desire for increased generality. The fewer assumptions required for a conclusion, the more certain we can be that it applies. As this paper has discussed, there are a number of directions in which we would like to extend our models so that they become better able to account for the facts that travellers are very heterogeneous, they make route and scheduling decisions based on limited information, they interact heavily in ways related to scheduling and they move about in complex networks that are subject to random shocks. The other main motivation for research into the area is the potential for providing a better empirical foundation for our models. One possibility that naturally comes to mind is to seek to utilise data sources such as GPS data to obtain a better understanding of actual trip scheduling behaviour.

In conclusion, many exciting things have been done, giving us many important insights into congestion dynamics, and there are still many exciting things waiting to be done. vii We use subscripts to denote partial derivatives. viii Provided that the toll does not decrease too quickly. A quickly decreasing toll may induce travelers to avoid certain departure times, which leads to unused capacity.

ix [START_REF] Laih | Queueing at a bottleneck with single-and multi-step tolls[END_REF] did not recognize that it was necessary to reformulate the queueing technology in order to obtain his results. This was rectified in [START_REF] Laih | Effects of the optimal step toll scheme on equilibrium commuter behaviour[END_REF].

x The exact optimization procedure used in METROPOLIS was never published since it is commercial proprietary software.

xi Dynamic discrete choice models are surveyed in [START_REF] Aguirregabiria | Dynamic discrete choice structural models: A survey[END_REF].

  Figure 1. A static model

  The line segment connecting point 0 a to point e represents the number of travellers served by the bottleneck, it has slope s . The first departures take place at a rate larger than capacity and queue builds up. For example, at time a , the number of travellers who have departed corresponds to the length of the segment a c  , while the number of travellers who have been served by the bottleneck corresponds to the length of the segment a b  . Thus the queue at that time has length corresponding to the segment b c  . The travellers in the queue at time a will all have been served by time d , which is then the time at which the traveller departing at time a is served by the bottleneck. The time spent in the bottleneck equals the length of the queue at the time of departure divided by the capacity.

  . Later travellers do not arrive as early, but are delayed more in the queue and incur the same trip cost. The traveller who arrives at the preferred arrival time is the most delayed and his trip cost comprises solely travel time cost. Later arrivals are less delayed in the queue, but arrive later at the destination. The last traveller is not delayed in the bottleneck at all, but arrives last at the destination and incurs a cost of  

Figure 3 .

 3 Figure 3. Equilibrium departure schedule under      preferences

  . the sum of consumer surplus and the total toll revenue. To find the welfare optimising toll, note that

  time varying toll   0    charged at the time of arrival at the bottleneck. We restrict attention to tolls that have     zero outside the departure interval I . This means that equations (1.10) and (1.11) still apply. If the toll is not too large, then Nash equilibrium exists with departures still in the interval I . viii Therefore the equilibrium utility   0 v a

Figure 6 .

 6 Figure 6. The optimal coarse toll

  preferences. They each have to choose a route and a departure time. Each route has a certain fixed travel time and a bottleneck with fixed capacity. Denote the fixed travel times by i T and the capacities by , 1since all travellers choose one and only one route. Moreover, let i  denote the arrival rate at the bottleneck for each of the routes. Consider first the choice of departure time conditional on the number of travellers on each route. From the previous analysis we know that in equilibrium they incur a trip cost of /

  iv 'C denotes the derivative of C . v[START_REF] Small | The scheduling of Consumer Activities: Work Trips[END_REF] tested a range of formulations of scheduling preferences, including the  . This follows since    . We use subscripts to denote partial derivatives.

  there is no toll, price equal travel cost: / , The function is this a reduced-form supply function, which is very usefull, especially in analytical work, together with a trip demand function.There is always a queue during the interval I . This means that the bottleneck capacity is fully utilised and hence that sd travellers pass the bottleneck during an interval of length d . At time a , a total of   R a travellers have entered the bottleneck, taking a total time of  /

	p	e			N s	that is price is a function of N
	and s.

R a s to pass. The first traveller enters and exits the bottleneck at time 0 a . Hence a traveller arriving at bottleneck at time a exits at time   0 / a R a s  . Travellers are identical so they incur the same scheduling cost in equilibrium. Normalising * 0 t  , it emerges that

  That is, the revenue from the optimal toll is equal to This finding leads directly to the self-financing theorem for the bottleneck model. If capacity is produced at constant returns to scale, i.e. if    

	  sK s . '
	' K s sK s 	with	  K s constant, then the optimal '
	toll exactly finances the optimal capacity   K s N p c     . If there are increasing returns to 
	scale, then   K s sK s   ' 

i We would like to thank Robin Lindsey for many useful comments, suggestions and references. The first author would like to thank the Institut Universitaire de France.ii For a more detailed analysis of congestion in the static model see the G. Santos and E. Verhoef contributions.iii We assume the parameters are such that this equation leads to positive flows on each route.