Benoît Perthame

Min Tang

Nicolas Vauchelet

Derivation of the bacterial run-and-tumble kinetic equation from a model with biochemical pathway

Keywords: kinetic-transport equations, chemotaxis, asymptotic analysis, run and tumble, biochemical pathway, Mathematics Subject Classification (2010): 35B25, 82C40, 92C17

Kinetic-transport equations are, by now, standard models to describe the dynamics of populations of bacteria moving by run-and-tumble. Experimental observations show that bacteria increase their run duration when encountering an increasing gradient of chemotactic molecules. This led to a first class of models which heuristically include tumbling frequencies depending on the path-wise gradient of chemotactic signal.

More recently, the biochemical pathways regulating the flagellar motors were uncovered. This knowledge gave rise to a second class of kinetic-transport equations, that takes into account an intra-cellular molecular content and which relates the tumbling frequency to this information. It turns out that the tumbling frequency depends on the chemotactic signal, and not on its gradient.

For these two classes of models, macroscopic equations of Keller-Segel type, have been derived using diffusion or hyperbolic rescaling. We complete this program by showing how the first class of equations can be derived from the second class with molecular content after appropriate rescaling. The main difficulty is to explain why the path-wise gradient of chemotactic signal can arise in this asymptotic process.

Randomness of receptor methylation events can be included, and our approach can be used to compute the tumbling frequency in presence of such a noise.

Introduction

Two classes of kinetic-transport equations have been proposed to describe, at the cell scale, the movement of bacteria by 'run and tumble' in a given external effective signal M (x, t), usually related to the extra-cellular chemo-attractant concentration S by a relation of the type M = m 0 + ln(S).

The simplest class is for the probability p(x, v, t) to find a bacteria at location x ∈ R d and with velocity v ∈ V (a smooth bounded subset of R d , one can choose the unit ball to fix idea ). The evolution of this probability is given by a Boltzmann type equation

∂ t p + v • ∇ x p = T [D t M ](p), x ∈ R d , v ∈ V, t ≥ 0, (1)
with the path-wise gradient of M defined as

D t M = ∂ t M + v • ∇ x M (2)
and T a tumbling kernel which typically takes the form

T [D t M ](p) = V T D t M (x, v , t), v, v p(x, v , t) -T D t M (x, v, t), v , v p(x, v, t) dv . (3)
Such equations, with T depending on M or D t M , were used intensively to model bacterial chemotaxis, possibly with M connected to the cell density, as a result of chemoattractant release by bacteria. They were first introduced in [START_REF] Othmer | Models of dispersal in biological systems[END_REF] and the Keller-Segel drift-diffusion system was subsequently derived [START_REF] Othmer | The diffusion limit of transport equations II: Chemotaxis equations[END_REF] in the diffusion limit; surprisingly, with a kernel T depending on M and not on its gradient, and in opposition to the Keller-Segel system which solutions blow-up for large mass, it was proved that the solutions exist globally [START_REF] Chalub | Kinetic models for chemotaxis and their drift-diffusion limits[END_REF][START_REF] Hwang | Global Solutions of Nonlinear Transport Equations for Chemosensitive Movement[END_REF]. However, experiments show that bacteria as E.coli extend their runs when feeling an increasing concentration of chemoattractant and this led to study tumbling kernels T that depend on D t M , see [START_REF] Erban | From individual to collective behaviour in bacterial chemotaxis[END_REF][START_REF] Dolak | Kinetic models for chemotaxis: Hydrodynamic limits and spatio-temporal mechanisms[END_REF]. The nonlinear theory is then more difficult (see [START_REF] Bournaveas | Global existence for a kinetic model of chemotaxis via dispersion and Strichartz estimates[END_REF] and the references therein) and blow-up can occur in finite time [START_REF] Bournaveas | Critical mass phenomenon for a chemotaxis kinetic model with spherically symmetric initial data[END_REF]. These models with T depending on D t M are able to explain the experimental observation of traveling pulses of bacteria, which cannot be done when T only depends on M itself, see [START_REF] Saragosti | Mathematical description of bacterial traveling pulses[END_REF][START_REF] Saragosti | Directional persistence of chemotactic bacteria in a traveling concentration wave[END_REF]. Also, departing from this kinetic-transport equation, it is possible to rescale it and study the diffusion and hyperbolic limit as in [START_REF] Erban | From individual to collective behaviour in bacterial chemotaxis[END_REF][START_REF] Dolak | Kinetic models for chemotaxis: Hydrodynamic limits and spatio-temporal mechanisms[END_REF][START_REF] Saragosti | Mathematical description of bacterial traveling pulses[END_REF][START_REF] Saragosti | Directional persistence of chemotactic bacteria in a traveling concentration wave[END_REF][START_REF] Hwang | Global Solutions of Nonlinear Transport Equations for Chemosensitive Movement[END_REF][START_REF] Hillen | Transport and anisotropic diffusion models for movement in oriented habitats, Dispersal, Individual Movement and Spatial Ecology: A mathematical perspective[END_REF]. When T undergoes stiff dependency on D t M , the hyperbolic limit is singular and the analysis is particularly delicate [START_REF] James | Chemotaxis : from kinetic equations to aggregate dynamics[END_REF].

More elaborated kinetic models have been proposed recently that incorporate intracellular chemosensory system. In the simplest description of the biochemical pathways, they use a single additional variable m ≥ 0, which represents the intracellular methylation level. Then, the kinetic-transport equation is written for the probability density function p(x, v, m, t) of bacteria at time t, position x ∈ R d , moving at velocity v ∈ V and methylation level m > 0

   ∂ t p + v • ∇ x p + ∂ m [f (m, M )p] = Q[m, M ](p), p(x, v, m = 0, t) = 0. (4)
The intracellular adaptation dynamics is described by the reaction rate f (•) for which we assume f (m = 0, M ) > 0, which allows us to pose the boundary condition at m = 0. The tumbling term

Q[m, M ](p) is Q[m, M ](p) = V λ(m, M, v, v )p(t, x, v , m) -λ(m, M, v , v)p(t, x, v, m) dv , (5)
where λ(m, M, v, v ) denotes the methylation dependent tumbling frequency from v to v, in other words the response of the cell depending on its environment and internal state. We borrow this formalism from [START_REF] Jiang | Quantitative modeling of Escherichia coli chemotactic motion in environments varying in space and time[END_REF][START_REF] Si | A pathway-based mean-field model for E. coli chemo-taxis: mathematical derivation and keller-segel limit[END_REF] even though this type of models, involving more general signal transduction, can be traced back to [START_REF] Dolak | Kinetic models for chemotaxis: Hydrodynamic limits and spatio-temporal mechanisms[END_REF][START_REF] Erban | From individual to collective behaviour in bacterial chemotaxis[END_REF][START_REF] Erban | Taxis equations for amoeboid cells[END_REF][START_REF] Xue | Multiscale models of taxis-driven patterning in bacterial populations[END_REF]. The authors in [START_REF] Dolak | Kinetic models for chemotaxis: Hydrodynamic limits and spatio-temporal mechanisms[END_REF][START_REF] Erban | From individual to collective behaviour in bacterial chemotaxis[END_REF][START_REF] Erban | Taxis equations for amoeboid cells[END_REF][START_REF] Si | A pathway-based mean-field model for E. coli chemo-taxis: mathematical derivation and keller-segel limit[END_REF][START_REF] Xue | Multiscale models of taxis-driven patterning in bacterial populations[END_REF][START_REF] Xue | Macroscopic equations for bacterial chemotaxis: integration of detailed biochemistry of cell signaling[END_REF] developed the asymptotic theory which allows to recover, in the diffusion and in the hyperbolic limits, macroscopic equations where the variables are only (x, t) as the Keller-Segel system, or (x, m, t) for structured Keller-Segel models.

In the program of establishing the relations between these pieces of the model hierarchy for bacterial population motion, a derivation is missing: how are related these two classes of kinetic models (1)-( 3) and ( 4)-( 5)?

Our goal is to show how, assuming fast adaptation and stiff response, the methylation level is at equilibrium with the external signal represented by M , and the equation ( 1) can be derived from (4). In particular we aim at computing the bulk tumbling kernel T (D t M, v, v ) from the methylation dependent kernel λ(m, M, v, v ), a statement we give in the next section. Two difficulties arise here: one is to infer the proper rescaling in the kinetic equations, the second is to carry-out the mathematical analysis for singular limits. Our approach allows us to also include noise resulting from random receptor-methylation and demethylation events. The proof of the formula for T is given in sections 3 and 4; we show that a direct use of the variable m is not enough to produce the formula and that a new variable is needed, which zooms on the intra-and extra-cellular methylation equilibrium. We conclude by relating our notations to a more physically based description of the same model where the cell receptors activity is used in the model parameters, see section 5.

To keep simplicity, we assume that the external signal function M (x, t) is given and smooth. Therefore questions of existence and blow-up are not considered here.

Fast adaptation, stiff response

Assumptions. For our mathematical derivation, we introduce a small parameter which acts both as a fast time scale for external signal transduction and as a stiffness parameter for the response in terms of tumbling rate. We assume moreover that the reaction rate f only depends on the difference m -M , in accordance with the physical models that we recall in Section 5. Therefore, we rescale equation ( 4)- [START_REF] Dolak | Kinetic models for chemotaxis: Hydrodynamic limits and spatio-temporal mechanisms[END_REF] as

   ∂ t p + v • ∇ x p + 1 ∂ m f m -M p = Q [m, M ](p ), p (x, v, m = 0, t) = 0, (6)
with the tumbling kernel

Q [m, M ](p ) = V Λ m -M , v, v p (x, v , m, t) -Λ m -M , v , v p (x, v, m, t) dv . (7)
We complete this equation with an initial data p ini ≥ 0 which satisfies

R d ×V ×R (1 + m 2 )p ini (x, v, m) dx dv dm < ∞, (8) pini
:= R p ini dm ∈ L ∞ (R d × V ). (9)
Also, we are going to use several assumptions for the functions M , f and Λ. We assume they are as smooth as necessary and that for some constants m ± , g ± , λ ± ,

0 < m -≤ M (x, t) ≤ m + , M ∈ C 1 b R d × [0, ∞) , (10)
f (y) = -yG(y), with G ∈ C 1 b (R), 0 < g -≤ G(y) ≤ g + , (11)
∂ y Λ y, v, v < 0, 0 < λ -≤ Λ y, v, v ≤ λ + . (12)
Various scalings have been proposed for kinetic equation and the closest, but still different seems to be the high field limit [START_REF] Berthelin | high-field limit from a kinetic equation to multidimensional scalar conservation laws[END_REF]. In [START_REF] Liao | Global solution for a kinetic chemotaxis model with internal dynamics and its fast adaptation limit[END_REF], still other scalings or limits are studied.

The main result. With these assumptions, we are going to show that as vanishes, we recover the simpler model ( 1)-( 3) as a limit of (6).

Theorem 2.1 (Derivation of the kinetic equation) We make the assumptions (8)-( 9) on the initial data, and (10)-( 12) on the coefficients. Let p be the solution to [START_REF] Endres | Physical principles in sensing and signaling, with an introduction to modeling in biology[END_REF]. Then, for all

T > 0, p is bounded in L ∞ [0, T ] × R d × V and p := R p dm →0 p0 in L ∞ [0, T ] × R d × V -weak- and p0 satisfies equation (1)-(3) with T u, v, v = Λ - u G(0) , v, v .
Furthermore, we have p0 := R p 0 dm with p 0 the weak limit (in measures, see [START_REF] Othmer | The diffusion limit of transport equations II: Chemotaxis equations[END_REF]) of p which is given by

p 0 (x, v, m, t) = p0 (x, v, t)δ m = M (x, t) .
Before we prove this theorem in the next sections, we present a variant of this result.

Internal noise. Due to random receptor-methylation and demethylation events, some internal noise can be observed in E. coli chemotaxis and we can model it by adding a diffusion term in m [START_REF] Endres | Physical principles in sensing and signaling, with an introduction to modeling in biology[END_REF]. The model is as follows:

∂ t p + v • ∇ x p + 1 ∂ m f m -M p = ∂ 2 mm p + Q [m, M ](p ), (13)
with the no-flux boundary condition that now reads

f (-M )p (x, v, m, t) -2 ∂ m p (x, v, m, t) = 0, at m = 0. ( 14
)
Theorem 2.2 (Limit with noise) With the assumptions and notations of Theorem 2.1, the same conclusions hold for the solution p of (13), with the same expression for p 0 and

T u, v, v = G(0) 2π R Λ y, v, v e - G(0) 2 y+ u G(0) 2 dy.
A priori bounds and principle of the proof. Before we explain the derivation of the formula stated in these theorems, let us make some observations which explain the difficulty. Because we assume that M (x, t) is given, we handle a linear equation for which existence and uniqueness of weak solutions is well established. The nonlinear case, when the chemoattractant concentration giving rise to M is coupled to p , can also be treated, see [START_REF] Liao | Global solution for a kinetic chemotaxis model with internal dynamics and its fast adaptation limit[END_REF]. In particular we will make use of the uniform estimates (see Section 4)

R d ×V ×R p (x, v, m, t) dx dv dm = R d ×V ×R p ini (x, v, m) dx dv dm, ∀t ≥ 0, ( 15
) p (x, v, t) ≤ pini (x, v) ∞ e Ct , ∀t ≥ 0, ( 16
)
where C is a nonnegative constant. From these bounds, we conclude that we can extract subsequences (but to simplify the notations we ignore this subsequence) which converge as mentioned in the theorems.

Passing to the limit in the equation on p (with or without noise) gives us

∂ m f m -M p 0 = 0.
This tells us that f m-M p 0 = 0 (it is constant and p 0 is integrable). Because, with assumption [START_REF] James | Chemotaxis : from kinetic equations to aggregate dynamics[END_REF], f m -M vanishes only for m -M = 0, we conclude that p 0 is a Dirac mass at m = M , hence the expression of p 0 in Theorems 2.1 and 2.2. However this information is not enough to pass to limit in the equation on p obtained integrating in m equation ( 6) or [START_REF] Liao | Global solution for a kinetic chemotaxis model with internal dynamics and its fast adaptation limit[END_REF], that is

∂ t p + v • ∇ x p = R + Q [m, M ](p ) dm.
Indeed, in the right hand side, the product Λ m-M , v, v p (x, v , m, t) is, in the limit, a discontinuity multiplied by a Dirac mass. For this reason, we have to rescale in m in order to evaluate this limit, which we do in the next section.

The change of variable

To get a more accurate view of the convergence of p to a Dirac mass in m, and following [START_REF] Erban | From individual to collective behaviour in bacterial chemotaxis[END_REF], we introduce a blow-up variable around m = M . We set

y = m -M , q (x, v, y, t) = p (x, v, m, t) (17)
so that q (x, v, t)

:= R q (x, v, y, t) dy = R p (x, v, m, t) dm = p (x, v, t). (18)
Because of these identities, our statements will equivalently be on q and will go through the analysis of q rather than p itself. Also notice that the bounds in ( 15), ( 16) also hold true for q and q and allow us to take weak limits.

(i) Without noise. The equation for q (t, x, v, y) is written, using the definition in (2),

∂ t q + v • ∇ x q - 1 D t M ∂ y q + 1 2 ∂ y f ( y)q = V Λ y, v, v q (x, v , y, t) -Λ y, v , v q (x, v, y, t) dv .
From [START_REF] James | Chemotaxis : from kinetic equations to aggregate dynamics[END_REF], we can write f ( y) = yG( y) and the above equation becomes

∂ t q + v • ∇ x q - 1 D t M ∂ y q - 1 ∂ y yG( y)q = V Λ y, v, v q (x, v , y, t) -Λ y, v , v q (x, v, y, t) dv . ( 19
)
Because q is a bounded measure on R d × V × R + × (0, T ), for all T > 0, as → 0, q has a weak limit q 0 in the sense of measure (again after extraction) and the above equation gives, in the distributional sense,

∂ y yG(0)q 0 + D t M (S)q 0 = 0. (20)
From this, we infer that

q 0 (t, x, v, y) = q0 (t, x, v)δ y = - D t M (S) G(0) . ( 21
)
This information is useful provided we can establish that q0 (x, v, t) = R q 0 (x, v, y, t) dy = weak-lim

→0 q (x, v, t). ( 22
)
This step is postponed to Section 4 and involves a control of the tail for large values of m.

We may also integrate equation [START_REF] Si | A pathway-based mean-field model for Escherichia coli chemotaxis[END_REF] with respect to y and find in the limit

∂ t q0 + v • ∇ x q0 = V Λ - D t M G(0) , v, v q 0 dv -Λ - D t M G(0) , v , v q0 , (23)
where D t M (S) is the total derivative, as in ( 2), but in the direction v and where q 0 represents q0 (x, v , t). Finally, for any smooth test function φ, we have from the change of variable

m → y = (m -M )/ , R p (x, v, m, t)φ(m) dm = R q (x, v, y, t)φ(M + y) dy → q0 (x, v, t)φ(M ),
where we use [START_REF] Xue | Multiscale models of taxis-driven patterning in bacterial populations[END_REF]. This gives the limiting expression of p 0 in Theorem 2.1. These are the results stated in Theorem 2.1, if we can establish the relation q0 = p0 as stated in ( 22), which we do later.

(ii) With internal noise. Similarly, after introducing the new variables as in [START_REF] Saragosti | Directional persistence of chemotactic bacteria in a traveling concentration wave[END_REF], the equation ( 13) for q (t, x, v, y) writes

∂ t q + v • ∇ x q - 1 D t M ∂ y q + 1 2 ∂ y f ( y)q = 1 ∂ 2 yy q + V Λ y, v, v q (x, v , y, t) -Λ y, v , v q (x, v, y, t) dv .
From [START_REF] James | Chemotaxis : from kinetic equations to aggregate dynamics[END_REF], this equation becomes

∂ t q + v • ∇ x q - 1 D t M ∂ y q - 1 ∂ y yG( y)q = 1 ∂ 2 yy q + V Λ y, v, v q (x, v , y, t) -Λ y, v , v q (x, v, y, t) dv . (24)
In the limit → 0, the above equation converges to, in the sense of distributions, ∂ y yG(0)q 0 + D t M q 0 = -∂ 2 yy q 0 , which shows that

q 0 (x, v, y, t) = q0 (x, v, t) G(0) 2π e - G(0) 2 y+ D t M G(0) 2 , (25)
a useful information, still assuming we have proved the relation ( 22) for q0 . We conclude as before. After integration of (24) with respect to y, passing to the limit → 0, we find

         ∂ t q0 + v • ∇ x q0 = V T D t M, v , v q 0 -T D t M, v, v q0 udv , T D t M, v, v = G(0) 2π R Λ(y, v, v )e - G(0) 2 y+ D t M G (0) 2 dy.
(

The Theorem 2.2 is also proved.

A priori bounds

We now establish the various estimates which justify that we can pass to the limit as indicated in Section 3 and thus we prove the Lemma 4.1 We make the assumptions of Theorem 2.1, then the condition (22) holds and for some constant which depends on y 2 q ini dy dx dv and M W 1,∞ (R d ×R + ) , we have y 2 q (t) dy dx dv ≤ C(q ini , M ).

Consequently, q converges weakly in the sense of measure towards q 0 and (i) for q a solution to [START_REF] Si | A pathway-based mean-field model for Escherichia coli chemotaxis[END_REF], q 0 is given by (21) with q0 weak solution of (23), (ii) for q a solution to (24), then, q 0 is given by (25) with q0 weak solution of (26).

Proof. We only consider the case (i) without noise, the case (ii) is obtained by the same token. We first prove some estimates which imply weak convergence. Then, we pass to the limit in the equation satisfied by q .

L 1 bound. For completness, we recall that equation ( 19) is positivity preserving and conservative. It follows the uniform, in , bound for q in L 1 , see [START_REF] Othmer | The diffusion limit of transport equations II: Chemotaxis equations[END_REF].

L ∞ bound on q . We use the notation [START_REF] Si | A pathway-based mean-field model for E. coli chemo-taxis: mathematical derivation and keller-segel limit[END_REF] for q . Arguing in the spirit of [START_REF] Hwang | Global Solutions of Nonlinear Transport Equations for Chemosensitive Movement[END_REF][START_REF] Bournaveas | Global existence for a kinetic model of chemotaxis via dispersion and Strichartz estimates[END_REF][START_REF] Vauchelet | Numerical simulation of a kinetic model for chemotaxis[END_REF]), we first prove the uniform L ∞ bound on q .

Integrating ( 19) with respect to y, from the bound [START_REF] Jiang | Quantitative modeling of Escherichia coli chemotactic motion in environments varying in space and time[END_REF] and the nonnegativity of q , we get

∂ t q + v • ∇ x q ≤ λ + q dv .
Then, using the method of characteristics, we have ∂ t q (t, x + vt) ≤ λ + q (x + vt, v , t) dv , which implies after integration q (t, x, v) -qini (x -vt) ≤ λ + t 0 q (x -vs, v , t -s) dv ds.

Taking the supremum in x, v, we find

q (t) ∞ ≤ qini ∞ + λ + |V | t 0 q (s) ∞ ds,
and using Gronwall's inequality, we find the estimate in [START_REF] Saragosti | Mathematical description of bacterial traveling pulses[END_REF].

Control on the tail in m. In order to prove the condition [START_REF] Xue | Macroscopic equations for bacterial chemotaxis: integration of detailed biochemistry of cell signaling[END_REF], we need to ensure that there is no mass loss at infinity in m. To do so, we multiply both sides of ( 19) by y 2 and integrate by parts with respect to x, v, and y. This yields d dt y 2 q dy dx dv + 2 y 2 G( y)q dy dx dv + 2 yD t M q dy dx dv = 0.

Using the Cauchy-Schwarz inequality, we deduce d dt y 2 q dy dx dv + 2 y 2 G( y)q dy dx dv ≤ 1 y 2 G( y)q dy dx dv + 1 (D t M ) 2 q G( y) dy dx dv.

By assumption [START_REF] Hwang | Global Solutions of Nonlinear Transport Equations for Chemosensitive Movement[END_REF],

D t M is bounded in L ∞ ([0, T ] × R d × V ).
From assumption [START_REF] James | Chemotaxis : from kinetic equations to aggregate dynamics[END_REF] and the mass conservation, the last integral of the right hand side is uniformly bounded by a constant denoted by C > 0. Then from assumption [START_REF] James | Chemotaxis : from kinetic equations to aggregate dynamics[END_REF], we have, d dt y 2 q dy dx dv + g - y 2 q dy dx dv ≤ C .

From the Gronwall Lemma, we deduce the bound for all t > 0, y 2 q (t) dy dx dv ≤ e -tg -/ y 2 q ini dy dx dv + C g - , which implies a uniform bound on y 2 q (t) dy dx dv.

Passing to the limit. From the bound above, we deduce that, we can extract a subsequence which converges weakly in measure q q 0 and such that q q0 in L ∞ -weak . Then we can pass to the limit in the sense of distribution in equation [START_REF] Si | A pathway-based mean-field model for Escherichia coli chemotaxis[END_REF] and deduce that the limit q 0 satisfies equation [START_REF] Vauchelet | Numerical simulation of a kinetic model for chemotaxis[END_REF] in the sense of distribution. In fact, we notice that from the Lipschitz character of G, we have y(G( y) -G(0))q dx dy ≤ C y 2 q dx dy → 0, as → 0, thanks to the estimate on the tail above. Finally, [START_REF] Vauchelet | Numerical simulation of a kinetic model for chemotaxis[END_REF] implies that yG(0)q 0 + D t M q 0 is constant a.e., and this constant should be 0 since from the estimate on the tail above, we have that yq 0 ∈ L 1 . We conclude that q 0 vanishes except when yG(0) + D t M (S) = 0. By conservation of the mass, we deduce the expression (21) for p 0 .

Comments on physical background

The form of the equation ( 6) corresponds, for E. coli chemotaxis, to the formalism in the physical literature. We have simplified the notations for mathematical clarity and we explain now how to relate our notations to known biophysical quantities. Here we have used the same biological parameters as in [START_REF] Jiang | Quantitative modeling of Escherichia coli chemotactic motion in environments varying in space and time[END_REF][START_REF] Si | A pathway-based mean-field model for Escherichia coli chemotaxis[END_REF].

• The methylation level M (x, t) at equilibrium is related to the extra-cellular attractant profile S, by a logarithmic dependency

M = M (S) = m 0 + f 0 (S) α , with f 0 (S) = ln 1 + S/K I 1 + S/K A .
The constants m 0 , K I , K A represent the basic methylation level, and the dissociation constants for inactive, respectively active, receptors. Numerical values are given by α = 1.7, m 0 = 1, K I = 18.2µM , K A = 3mM .

• The receptor activity a(m, S) depends on the intracellular methylation level m and the extracellular chemoattractant concentration S such that

a = 1 + exp(N E) -1 , with E = -α(m -m 0 ) + f 0 (S) = -α(m -M (S)). (27)
The coefficient N = 6 represents the number of tightly coupled receptors.

• The intracellular dynamics and tumbling frequency are given by

f m -M (S) = F (a) = k R (1 -a/a 0 ), λ m -M (S) = Z(a) = z 0 + τ -1 a a 0 H ,
where a(m, S) is the receptor activity defined in (27). The parameter k R is the methylation rate, a 0 is the receptor preferred activity which is such that f (a 0 ) = 0 and f (a 0 ) < 0. For the tumbling frequency, z 0 , H, τ represent the rotational diffusion, the Hill coefficient of flagellar motors response curve and the average run time respectively. All these parameters can be measured biologically, their values are given by k R = 0.01s -1 ∼ 0.0005s -1 , a 0 = 0.5, z 0 = 0.14s -1 , τ = 0.8s, H = 10.

• Two kinds of noise can be observed in the signaling pathway for E. coli, one is from the external fluctuation of the ligand concentration and the other is the internal noise from the random receptor-methylation and demethylation event [START_REF] Endres | Physical principles in sensing and signaling, with an introduction to modeling in biology[END_REF]. For small complexes, the effect on the activity from the external noise is negligible compared to the internal noise.

We refer the readers to [START_REF] Si | A pathway-based mean-field model for Escherichia coli chemotaxis[END_REF][START_REF] Endres | Physical principles in sensing and signaling, with an introduction to modeling in biology[END_REF][START_REF] Jiang | Quantitative modeling of Escherichia coli chemotactic motion in environments varying in space and time[END_REF][START_REF] Si | A pathway-based mean-field model for E. coli chemo-taxis: mathematical derivation and keller-segel limit[END_REF] and the references therein for the detailed physical meanings of these parameters. In E. coli chemotaxis, the adaptation time is faster than the system time, i.e. the rescaled constant k R is large. Let k R = 1 , where is the ratio between the system time and the adaptation time. For example, when the system time is 1000s and the adaptation time is 100s, = 0.1.

Moreover, the Hill coefficient H is large which indicates that λ(m -M (S)) varies fast with respect to m -M (S). Therefore, the scaling introduced in ( 6) is satisfied by E. coli chemotaxis. We can use

f (r) = 1 - 1 a 0 1 + exp(-N αr) -1 .
Therefore, the function G(•) used in [START_REF] James | Chemotaxis : from kinetic equations to aggregate dynamics[END_REF] is given by

G(r) = - f (r) r = - 1 r 1 - 1 a 0 1 + exp(-N αr) -1 , with G(0) = -f (0) = N α 4a 0 .
Besides, from Theorem 2.1 for the case without noise, using y = r yields

T (D t M, v, v ) = Λ(y, v, v ) = z 0 + τ -1 1 + exp(-N α y) -H a H 0 = z 0 + τ -1 1 + exp N α D t M (S)/G(0) -H a H 0 .
And from Theorem 2.1, when the noise in the methylation level is considered,

T D t M, v, v = G(0) 2π R Λ y, v, v e - G(0) 2 y+ D t M G(0) 2 dy.
Since the run duration last longer when bacteria encounter an increasing gradient of chemotactic molecules, this lead to higher bacteria density at the place where the ligand concentration S is higher. This phenomena is well explained by the classical Keller-Segel model which can be considered as the parabolic limit of the kinetic-transport models. However, recent experimental observation shows that higher ligand concentration leading to higher bacteria density is only valid in a spatial-temporal slowvarying environment. When the ligand concentration varies fast, there exists a phase shift between the mass center of ligand concentration and of the bacterias [START_REF] Zhu | Frequencydependent Escherichia coli chemotaxis behavior[END_REF]. This is due to the memory effect in the slow methylation adaptation rate. In the limiting kinetic model, D t M (S) takes into account the memory effect along the trajectory of the moving cell [START_REF] Vauchelet | Numerical simulation of a kinetic model for chemotaxis[END_REF]. Then, two interesting questions come: are these two kinds of memory effect the same? Can we see the phase shift between the mass center of ligand concentration and of the bacteria in the limiting kinetic model?

Numerical illustrations

We performed numerical simulations using the method SPECS [START_REF] Jiang | Quantitative modeling of Escherichia coli chemotactic motion in environments varying in space and time[END_REF]. It is a cell based model that takes into account the evolution of each cell intracellular methylation level, which determines the tumbling frequency of each bacteria. As explained in [START_REF] Si | A pathway-based mean-field model for E. coli chemo-taxis: mathematical derivation and keller-segel limit[END_REF][START_REF] Si | A pathway-based mean-field model for Escherichia coli chemotaxis[END_REF], SPECS and the kinetic model that incorporates intracellular chemo-sensory system (4) show a quantitative match. As in [START_REF] Si | A pathway-based mean-field model for E. coli chemo-taxis: mathematical derivation and keller-segel limit[END_REF][START_REF] Si | A pathway-based mean-field model for Escherichia coli chemotaxis[END_REF], we choose the two velocity kinetic model and a periodic 1D traveling wave concentration

S(x, t) = S 0 + S A sin[ 2π (x -ut)],
which is spatial-temporal varying and where the wavelength is equal to the length of the domain. We compare the numerical results of SPECS and the limiting kinetic model in Figure 1. Upwind scheme is used for the transport terms and periodic boundary conditions are considered. The density is scaled at the order of 10 -3 , it is the ratio between the actual cell number and the total number. In the Figure 1, the x axis represents the remainder of x -ut mod , i.e. we keep tracking the wave front of the periodic traveling wave. Two different wave velocities u = 0.4µm/s and u = 8µm/s are considered. We compare the density profiles ρ = V p dv and the cell flux J = V vp dv. When the concentrated wave moves slowly, the limiting kinetic model gives good consistency, however in the fast-varying environment, the density and cell flux profiles are different for SPECS and the limiting kinetic model. We refer the readers to [START_REF] Jiang | Quantitative modeling of Escherichia coli chemotactic motion in environments varying in space and time[END_REF][START_REF] Si | A pathway-based mean-field model for Escherichia coli chemotaxis[END_REF] for more detailed discussions and physical explanations. This numerical experiment shows that the memory effect using the model based on D t M (S) is different from the memory effect for the complete model (4) when fast external chemoattractant waves are considered. This phenomena can be explained by the slow adaptation rate in the methylation level and the memory along the trajectory compared to the phase shift. In this fast wave regime, our mathematical results do not apply because the scaling assumptions are not satisfied.

Figure 1 :

 1 Figure 1: Numerical comparison between the limiting kinetic model and SPECS. The steady state profiles of density ρ (top) and current J (bottom) are presented. Left: u = 0.4µm/s; Right: u = 8µm/s. In the subfigures, histograms and solid lines are from SPECS, while the dash star and dash dotted lines are calculated using the limiting kinetic equation. Parameters used here are [L] 0 = 500µM , [L] A = 100µM , = 800µm. We have used 20, 000 cells for simulation with SPECS.

This author is partially supported by NSF of Shanghai under grant 12ZR1445400, NSFC 11301336 and 91330203, and Shanghai Pujiang Program 13PJ140700.


An Auction-Based Mechanism for Cooperative Sensing in Cognitive Networks

Qiong Shi, Cristina Comaniciu and Katia Jaffrès-Runser Abstract-In this paper, we propose an auction-based cooperative sensing protocol for secondary users in cognitive networks. The proposed auction mechanism is based on a novel modified Vickrey auction with a three dimensional bid, that accounts for detection gains as well as for virtual currency gains. We present a formal proof to show that the proposed three dimensional bidding mechanism preserves the truthfulness property of the classic Vickrey auction. The cooperative auction is combined with a prioritized access scheme to increase the efficiency and to reduce the response time for the coalition formation procedure. Our auction-based cooperative sensing mechanism can be easily applied to different network scenarios, by defining specific utility functions. The proposed cooperative sensing auctioning mechanism is illustrated for both downlink and uplink. Our simulation results show that users' cooperation is incentivized by the proposed algorithm, which leads to significant detection gains for the downlink and the uplink scenarios, with a more efficient energy expenditure. Index Terms-Cooperative spectrum sensing, Vickrey auction, prioritized access, cognitive networks.

I. INTRODUCTION

T HE problem of coexistence between primary and sec- ondary users in a cognitive radio (CR) network has been extensively studied in the literature. Secondary users (SUs) are allowed to utilize unused spectrum holes but have very stringent requirements on the level of interferences that they could create to primary users (PUs). To this extent, they are required to sense the spectrum with high accuracy to determine if there is no ongoing primary communication that they would potentially disturb.

Providing Quality of Service (QoS) guarantees for the primary network and efficient communications for the secondary network is very often addressed in the literature by proposing intelligent spectrum management algorithms. In particular we distinguish several research topics that address various aspects of efficient spectrum management for the secondary-primary users' coexistence ( [START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF], [START_REF] De Domenico | A survey on MAC strategies for cognitive radio networks[END_REF]):

1) Spectrum sensing allows CR networks to determine the availability of spectrum resources ( [START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF], [START_REF] Lu | A novel robust detection algorithm for spectrum sensing[END_REF], [START_REF] Saad | Coalition formation games for collaborative spectrum sensing[END_REF]); 2) Spectrum selection implements mechanisms for CR users to select the best channels among all the available Q. Shi and C. Comaniciu are with the Electrical and Computer Engineering, Stevens Institute of Technology, Hoboken, NJ, 07030 USA (e-mail: shiqiong@gmail.com).

K. Jaffrès-Runser is with Université de Toulouse, France.

spectrum bands, based on their QoS requirements as well as on the characteristics of the spectrum ( [START_REF] Nie | Adaptive channel allocation spectrum etiquette for cognitive radio networks[END_REF], [START_REF] Malanchini | On spectrum selection games in cognitive radio networks[END_REF]); 3) Spectrum sharing coordinates the primary network and the CR network, or several CR networks to share the spectrum in an efficient way ( [START_REF] Yang | Channel-aware access for cognitive radio networks[END_REF], [START_REF] Niyato | Competitive pricing for spectrum sharing in cognitive radio networks: dynamic game, inefficiency of Nash equilibrium, and collusion[END_REF]); 4) Spectrum mobility allocates spectrum for dynamic variations in spectrum availability ( [START_REF] Lee | Spectrum-aware mobility management in cognitive radio cellular networks[END_REF]).

In this paper, we study the problem of spectrum sensing for detecting the presence of a PU for both the uplink and the downlink case, in the context of incentivizing SUs' cooperation for efficient energy management. From a practical perspective, there are several challenges for this spectrum sensing problem, including hardware constraints, the hidden PU problem, the receiver uncertainty problem, difficulties in detecting spread spectrum signals, difficulties in setting optimal sensing parameters and various security issues ( [START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF]).

In this paper we address some of these challenges by proposing a cooperative sensing scheme. Cooperative sensing has been shown to be successful in alleviating the hidden PU problem by exploiting multi-user diversity gains ( [START_REF] Unnikrishnan | Cooperative sensing for primary detection in cognitive radio[END_REF], [START_REF] Mishra | Cooperative sensing among cognitive radios[END_REF]). Moreover, cooperative sensing has been shown to improve significantly the detection of a weak signal with a low SNR ( [START_REF] Unnikrishnan | Cooperative sensing for primary detection in cognitive radio[END_REF]).

We note that the hidden PU problem in CR networks is different from the classic hidden terminal problem in the carrier sense multiple access (CSMA). In CSMA, a hidden terminal problem occurs when two nodes that cannot hear each other transmit simultaneously and they are received at a given receiver who is in the transmission range of both nodes ( [START_REF] Tobagi | Packet switching in radio channels-part II: the hidden terminal problem in carrier sense multiple-access and the busy-tone solution[END_REF]). As opposed to this situation, a hidden PU problem for spectrum sensing occurs when the PU's signal is shadowed or in a severe multipath fading at a SU and so this SU cannot sense the presence of the PU ( [START_REF] Unnikrishnan | Cooperative sensing for primary detection in cognitive radio[END_REF], [START_REF] Letaief | Cooperative communications for cognitive radio networks[END_REF]). If then the primary receiver is in the transmission range of the SU, this SU will cause interference to the primary communication. In CR networks, the receiver's uncertainty problem is similar to the hidden terminal problem in CSMA ( [START_REF] Akyildiz | NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey[END_REF]) and the cooperative sensing is very effective in addressing this problem ( [START_REF] Lee | Optimal spectrum sensing framework for cognitive radio networks[END_REF]). Fig. 1 illustrates the hidden PU problem and the receiver uncertainty problem for spectrum sensing. It can be seen that the cooperation between SU 1 and SU 2 enables the detection of a PU, which would not be detected by SU 1 independently. The cooperative detection comes of course at a price, and several aspects have been mentioned in the literature, such as detection delay, requirements of a multi-user coordination algorithm as well as control channel support, problems related to asynchronous sensing, cooperation overhead, additional power consumption for spectrum sharing, and increased complexity ( [START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF], [START_REF] Hussain | Spectrum sensing in cognitive radio networks: up-to-date techniques and future challenges[END_REF]).

In this paper, we focus on designing a good cooperation strategy that aims to increase SUs' detection capabilities, while addressing some challenges mentioned above. Our solution is to propose a cooperation formation mechanism based on an auctioning strategy and prioritized bidding response, which minimizes the energy consumption, the detection delay, and the complexity and overhead associated with cooperative schemes. Some initial analysis and results for our proposed auctioning strategy were presented in our previous work in [START_REF] Shi | An auction-based mechanism for cooperative sensing in cognitive networks[END_REF] for the downlink transmission scenario. In this paper, we extend our previous analysis in [START_REF] Shi | An auction-based mechanism for cooperative sensing in cognitive networks[END_REF] by adding a formal proof for the truthfulness property of our proposed auctioning mechanism for the downlink, and by addressing the uplink transmission scenario.

In the literature, many papers have addressed various aspects related to the cooperative sensing for CR networks, for example, maximizing CR network throughput ( [START_REF] Shen | Maximum channel throughput via cooperative spectrum sensing in cognitive radio networks[END_REF], [START_REF] Fan | Joint optimal cooperative sensing and resource allocation in multichannel cognitive radio networks[END_REF]), proposing novel fusion and combining rules ( [START_REF] Unnikrishnan | Cooperative sensing for primary detection in cognitive radio[END_REF], [START_REF] Ma | Soft combination and detection for cooperative spectrum sensing in cognitive radio networks[END_REF]), and proposing algorithms for wideband sensing ( [START_REF] Fan | Joint optimal cooperative sensing and resource allocation in multichannel cognitive radio networks[END_REF], [START_REF] Tian | Compressed wideband sensing in cooperative cognitive radio networks[END_REF]). In addition, there are a few papers discussing coalition formation mechanisms ( [START_REF] Saad | Coalition formation games for collaborative spectrum sensing[END_REF], [START_REF] Saad | Coalitional games in partition form for joint spectrum sensing and access in cognitive radio networks[END_REF], [START_REF] Gharehshiran | Dynamic coalition formation for resource allocation in cognitive radio networks[END_REF], [START_REF] Hao | A coalition formation game for energy-efficient cooperative spectrum sensing in cognitive radio networks with multiple channels[END_REF]), which are also our focus in this paper. For example, [START_REF] Saad | Coalition formation games for collaborative spectrum sensing[END_REF] analyzes coalition benefits and proposes a merge-split algorithm for a more efficient coalition performance, i.e., better cooperative detection probabilities with reasonable cooperative false alarm probabilities. This work is extended in [START_REF] Saad | Coalitional games in partition form for joint spectrum sensing and access in cognitive radio networks[END_REF], which further takes into account some other key factors in spectrum sharing and access control (e.g., interference coordination, capacity optimization and sensing time). The authors in [START_REF] Gharehshiran | Dynamic coalition formation for resource allocation in cognitive radio networks[END_REF] address the CR admission, resource allocation and load balancing under IEEE 802.22 framework, by building an optimal coalition structure to obtain the maximal sum of utilities for all the cells and then negotiating to reach an optimal payoff distribution with an objective of maximizing the average payoff for each CR. In [START_REF] Hao | A coalition formation game for energy-efficient cooperative spectrum sensing in cognitive radio networks with multiple channels[END_REF], SUs form M coalitions to sense M channels to obtain optimal sensing accuracy and energy efficiency.

None of these works explicitly consider SUs' incentives to cooperate given that participation in a cooperative sensing will consume SUs' energy. For example, the paper [START_REF] Saad | Coalition formation games for collaborative spectrum sensing[END_REF] assumes that all the users have a mutual interest in sensing the spectrum, which may not always be the case, especially for a lightlyloaded network scenario. Users who do not have data waiting for transmission in their buffers may not be interested in sensing spectrum in order to save their energy. The assumption in our work is that SUs are currently passive users, which need to be incentivized to participate in cooperative sensing coalitions. To incentivize these SUs' cooperation we propose a virtual currency exchange for coalition formation. Our work differs from all previous works in the literature, in that we do not implicitly assume that SUs are willing to cooperate for spectrum sensing if they do not have packets to send, but rather we incentivize their cooperation by proposing an auction-based coalition formation mechanism.

This paper is organized as follows. The system model and assumptions are given in Section II, and our proposed auctionbased cooperative sensing protocol is presented in Section III. Section IV provides detailed description for the proposed prioritized bid access control. Simulation results together with discussions are given in Section V, and conclusions are presented in Section VI.

II. SYSTEM MODEL

In this paper, we consider a CR network sharing a known spectrum with a primary network. The primary network has a base station (e.g., cellular systems [START_REF] Attar | Cognitive radio game for secondary spectrum access problem[END_REF], TV broadcast networks [START_REF] Demir | Draft Standard for Wireless Regional Area Networks Part 22: Cognitive Wireless RAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Policies and Procedures for Operation in the TV Bands[END_REF]), whose location is known by the CR network, and multiple users, which are uniformly distributed across the network. In addition, this primary network has a requirement on the detection probability of the CR network in order to guarantee that its QoS will not be degraded due to allowing opportunistic access for SUs. The access paradigm of SUs is the interweave mode, defined in [START_REF] Goldsmith | Breaking spectrum gridlock with cognitive radios: an information theoretic perspective[END_REF] as a mode in which SUs are only allowed to access spectrum holes where PUs are absent. The CR network consists of several transmitter (Tx)-receiver (Rx) pairs, which are also uniformly distributed across the network. We assume that Tx SUs have transmission buffers to store data from the upper layer. Once the spectrum is available to these Tx SUs, they will retrieve their data from these buffers to transmit it over the air. Moreover, we assume that SUs know their own locations by means of employing some localization algorithms or based on GPS information. Our study focuses on stationary SUs and thus no SU mobility is assumed.

We consider the downlink case first, for which the base station transmits signals to communicate with its receivers.

We then extend our work to the uplink case. We show that the auction mechanism can be applied to incentivize cooperation for the uplink case as well, even though the utility functions need to be redefined appropriately in order to capture some new characteristics, which are specific to the uplink scenario. For the uplink case, there may be one or more PUs transmitting signals to the base station and their locations cannot be known by the CR network in advance. As a consequence, we need to formulate this sensing problem from the PU receiver's perspective. The goal is to minimize the possible interference created by SUs to the PU receiver, i.e., the base station.

In our system model, we use SUs' local detection probabilities and the error probabilities for the reporting links to formulate utility functions. These metrics depend on the signal-to-noise ratios (SNRs) for the links, which is a fundamental measure for link quality, readily available without incurring any additional cost to the system. We consider a densely deployed CR network with a light traffic load. A dedicated control channel is assumed to be available for SUs communications for coordination ( [START_REF] Lee | Optimal spectrum sensing framework for cognitive radio networks[END_REF], [START_REF] Fan | Joint optimal cooperative sensing and resource allocation in multichannel cognitive radio networks[END_REF], [START_REF] Xie | A parallel cooperative spectrum sensing in cognitive radio networks[END_REF]), which can be implemented as a dedicated frequency band, an unlicensed band such as ISM, or an underlay UWB system [START_REF] Cabric | A cognitive radio approach for usage of virtual unlicensed spectrum[END_REF]. For analysis simplicity, we assume that this dedicated channel is error free.

A. Detection model

Consider the same detection model as in [START_REF] Saad | Coalition formation games for collaborative spectrum sensing[END_REF], i.e., energy detectors for SUs and several SUs forming a cooperative group/coalition with a SU in this group acting as the head node. All the SUs in a cooperative group, including the head SU, perform energy detection and then the member SUs report their local hard decisions to the head SU via transmission links employing BPSK modulation. The head SU determines whether there is a PU present in its neighborhood by using the OR rule. For readers' convenience, we give here the detection probability (p d,i ) and the false alarm probability (p f,i ) for SU i using an energy detector in a Rayleigh fading environment (cf. [START_REF] Ghasemi | Collaborative spectrum sensing for opportunistic access in fading environments[END_REF]).

p d,i =e -λ 2 θ-2 s=0 1 s! λ 2 s + 1 + γi,P U γi,P U θ-1 × e - λ 2(1+γ i,P U ) -e -λ 2 θ-2 s=0 1 s! λγ i,P U 2(1 + γi,P U ) s , (1)
p f,i = Γ(θ, λ/2) Γ(θ) , ( 2
)
where θ is the time bandwidth product, λ is the energy detection threshold and γi,P U =

PP U hi,P U σ 2
is the average SNR of the received signal over the link from the PU to the ith SU i given that P P U is the PU's transmission power, σ 2 is the Gaussian noise variance and h i,P U = ϕ d ν i,P U is the path loss between the PU and the ith SU, where ϕ is the path loss constant, ν is the path loss exponent and d i,P U is the distance between the PU and the ith SU. Γ(•, •) is the incomplete gamma function and Γ(•) is the gamma function. The missed detection probability of the ith SU is p md,i = 1 -p d,i . The energy detection threshold λ is determined based on an imposed false alarm probability p f .

The cooperative detection probability and the cooperative false alarm probability for a cooperative group (G) using the OR rule are given as follows. In this cooperative group, we consider that the kth SU is the head node and all the other SUs report to it, and we compute the detection probability (P d,G ) and the false alarm probability (P f,G ) for the group to be:

P d,G = 1 - i∈G [p d,i • p e,i,k + (1 -p d,i ) (1 -p e,i,k )] , (3)
P f,G = 1 - i∈G [p f • p e,i,k + (1 -p f ) (1 -p e,i,k )] , (4) p e,i,k = 1 2 1 - γi,k 1 + γi,k , (5)
where p e,i,k is the probability of errors due to fading over the reporting channel between the ith SU and the kth SU, and γi,k is the average SNR of the reporting channel between the ith SU and the kth SU. The cooperative missed detection probability for this group is given as P md,G = 1 -P d,G . The head SU is the reporting sink, so its reporting error probability is set to be zero in ( 3) and (4), i.e., p e,i,k = 0. We note that using cooperation, the detection probability is improved, but the false alarm probability is also increased. Therefore, we need to guarantee that the false alarm probability is kept within a desirable range by appropriately selecting the cooperative group members.

B. Frame structure

The energy detector is widely used for cooperative spectrum sensing due to its simple implementation and no prior information requirement on the PU's signals. The energy detector has the disadvantage of not being able to distinguish between the SUs' and PUs' signals, and thus SUs using energy detectors cannot sense the spectrum and transmit data at the same time. In this paper, SUs are assumed to be perfectly synchronized at the initial setup of the network.

In our proposed auction-based cooperative sensing, a frame consists of a cooperative sensing sub-frame and a data transmission sub-frame. In this paper, we assume constant preset sizes for the sub frames. In the cooperative sensing subframe, all the nodes participating in the cooperative group sense the channel and report their measurements to the head node. The head node determines the possible presence of PU transmissions, by exploiting the OR rule, and if no PU transmissions are detected, the head node transmits its data in the data transmission sub-frame.

III. AUCTION-BASED COOPERATIVE SENSING

A cooperative sensing mechanism relies on users participating in sensing and reporting for improved detection accuracy. However, sensing will deplete the batteries for the cooperating users. The work in [START_REF] Saad | Coalition formation games for collaborative spectrum sensing[END_REF] considers that all the SUs have packets to transmit and thus form a coalition to help sense the spectrum and coordinate their transmissions, which is not always a practical assumption. Our assumption is that SUs do not always have packets to transmit and must be provided with incentives to enable cooperation.

A. Virtual currency in an auction-based game

In our model, the CR network is lightly loaded, and consequently there are many SUs in the neighborhood that are not interested in transmitting packets at the moment. We designate such SUs in the rest of the paper as idle SUs in contrast to active SUs which have data to transmit. To incentivize idle SUs to cooperate, we introduce a virtual currency that can be used to reward spectrum sensing cooperation. Each SU is assigned an initial level of currency. Idle SUs can accumulate currency by participating in cooperative sensing. Once these SUs become active (i.e., have packets to send), they can spend their currency on initiating a sensing coalition which would improve their spectrum sensing detection performance.

Based on this virtual currency, SUs can initiate coalition requests, and form sensing coalitions based on a bid algorithm reminiscent of auctions. We propose a three dimensional modified Vickrey auction mechanism for spectrum sensing coalition formation, and we show that this auction mechanism preserves the desirable truthfulness property of the classic Vickrey auction [START_REF] Vickrey | Counterspeculation, auctions and competitive sealed tenders[END_REF]. A Vickrey auction is a type of sealed-bid auction, where bidders do not know the bid of other bidders and the highest bidder wins, but the winner pays the price of the second-highest bid.

For our problem, an active head SU seeks to find a set of idle SUs that maximizes its cooperative detection probability while keeping its cooperative false alarm probability below some desirable threshold. In this auction-based game, the head SU rewards the idle SUs for their sensing capabilities in increasing its own detection probability. However, the head SU is interested in paying as little currency as possible for the sensing service provided by other idle SUs. An idle SU aims at gaining currency but without spending too much energy in sensing. As a consequence, it will decide to participate if the currency benefits can compensate its loss in sensing energy. These benefits and costs for cooperation are captured in utility function definitions for both the active head SUs and the idle SUs. These utility functions are used to characterize the users' payoffs.

B. Utility functions

A utility function is a mathematical way of describing the payoff associated with an action, reflecting the tradeoff between the action's profit and cost. The players in an auction game (potential cooperative SUs and SUs initiating the cooperation requests) will choose actions that will maximize their individual utilities. Based on their utilities, the potential cooperative SUs decide whether to respond to cooperation requests and the head SU that initializes the cooperation request chooses a group of responding SUs.

1) Downlink case: For downlink transmission scenario, we define the utility for a head SU (u DW h ) as a tradeoff among the detection probability, the false alarm probability [START_REF] Saad | Coalition formation games for collaborative spectrum sensing[END_REF], as well as the virtual currency cost for setting up the coalition:

u DW h = P d,G -B(P f,G ) - nm i=1 b i , (6)
where P d,G and P f,G are the cooperative detection probability and the cooperative false alarm probability, respectively, b i is the price asked by responding/member SU i, (the minimum payment that responding SUs would accept), and n m is the number of member nodes in the considered group G. The B(P f,G ) function is a logarithmic barrier penalty function given as:

B(P f,G ) = -α 2 • ln 1 -( P f,G α ) 2 , if P f,G < α +∞, if P f,G ≥ α , (7)
where α = P f,th is the false alarm constraint for the cooperative group. The formation of coalitions that incur an undesirably high false alarm probability (i.e., P f,G > P f,th ) is prevented by imposing an infinite cost for such coalitions.

We simplify the expression in ( 6) to reduce the overhead on payment information exchange and reduce implementation complexity [START_REF] Demir | An auction based AODV protocol for mobile ad hoc networks with selfish nodes[END_REF] by proposing a more generous payment policy in which all the member SUs are equally paid with r m , which is defined as the maximum of all the prices asked by member SUs in the current cooperative group (G), i.e., r m = max i∈G b i . Hence, the utility for the head SU is simplified as,

u DW h = P d,G -B(P f,G ) -n m r m . ( 8
)
Given the utility function in [START_REF] Yang | Channel-aware access for cognitive radio networks[END_REF], the head SU will select a winning cooperative group among all possible groups of SUs. The winning group will have the best detection performance (in terms of the tradeoff between detection probability and false alarm probability) obtained with the lowest payment. The utility u m,i of an arbitrary member SU i, is defined as the amount of currency it gets after cooperating in the spectrum sensing, i.e. the difference between the bid and the energy cost for cooperation. Formally:

u m,i = b i -C e,m , if b i -C e,m > 0 -∞, if b i -C e,m ≤ 0 , (9)
where C e,m = ǫ • c e,m is the energy cost for cooperation assuming a price ǫ per unit energy and an energy expenditure c e,m . We assume a uniform energy expenditure for cooperation across all the member nodes and thus C e,m is the same for all the members. This utility definition represents a member SU's effective gain when it chooses to cooperate, namely the difference between its received payment and its energy cost.

If its received payment is less than its energy cost, the SU will get a negative infinite utility, which will discourage its cooperation. The definition of the utility function ensures that only the SUs that can get enough payment to compensate their loss in energy due to cooperation will respond to cooperation requests.

2) Uplink case: Compared to the downlink case, it is much more difficult to derive detection probabilities for SUs' energy detectors for the uplink transmission scenario. This is due to the fact that more than one PU may be transmitting data to the base station at the same time. These PUs are randomly distributed over the field, and if there is no prior knowledge about the primary network deployment and the PUs' locations, an exact derivation of a cooperative detection probability is intractable. As a consequence, the utility function associated with a head node (i.e., the node requesting the coalition formation) needs to be redefined to capture the relevant measures of performance for the uplink case. In our work, we assume that the base station is located at the field's center and the PUs' locations have a uniform distribution. In our design, we exploit the knowledge on the location of the base station, and the uniform distribution of SUs, by seeking coalition partners with more advantageous positions to detect PUs, i.e., closer to PUs' receiver. In addition, we also consider the link quality for the reporting nodes when computing the utility function for a head node.

Taking into account a similar simplified payment strategy as for the downlink case, a head SU's utility for the uplink case (u UP h,k ) can be defined as what a head SU can obtain after subtracting all the payments from the group's detection gain.

u UP h,k = min i∈G ( d i,BS 1 -p e,i,k ) • 1 + n m i∈G di,BS 1-p e,i,k -B(P f,G ) -n m r m , (10)
where d i,BS is the distance between SU i and the base station, p e,i,k is the error probability of the link between SU i and the head SU k and 1 + n m is the total number of SUs in the cooperative group G including the head SU. The gain is considered to be invert proportional to an average loss

i∈G d i,BS 1-p e,i,k 1+nm
, where larger distances to the base station and a bigger error rate of reporting links are more disadvantageous for PU detection. The term min i∈G ( di,BS 1-p e,i,k ) is introduced for normalization purposes. From this definition, we can see that a smaller average distance from the group to the base station and a more reliable reporting link are preferred. The member SUs' utility function for the uplink case remains the same as the one proposed for the downlink case, i.e., [START_REF] Niyato | Competitive pricing for spectrum sharing in cognitive radio networks: dynamic game, inefficiency of Nash equilibrium, and collusion[END_REF].

C. Modified Vickrey auction mechanism

In a traditional Vickrey auction, the bidder with the highest bid wins and pays the second highest bid. For our cooperative sensing scenario, the head SU selects its coalition members such that such coalition membership maximizes its utility function. The coalition members form a winning group denoted as G w . Since the head SU's utility is a combination of performance and price (as defined in (8)), the bid price alone cannot be used to determine the winner. Furthermore, multiple winners for this auction game are possible. It becomes clear that the classic Vickrey auction mechanism needs to be modified in order to accommodate these new constraints [START_REF] Comaniciu | An auctioning mechanism for green radio[END_REF], but the requirement is to preserve its desirable truthfulness characteristic. In what follows, we take the downlink transmission scenario as an example to illustrate and analyze our proposed auction mechanism. We note that discussions and proof hold for the uplink case as well, with the only modification that the head SU's utility function definition is different for the uplink transmission case.

In our proposed auction mechanism, the head SU selects auction winners based on its utility, and determines a payment strategy that will preserve the truthfulness characteristic of the Vickrey auction. We propose a new payment scheme (ρ m ), which represents the highest price in the winning group, plus the difference between the utility (u max = P d,Gw -B(P f,Gw ) -n m r m ) for the best coalition G w and the utility (u

′ max = P ′ d,G ′ -B(P ′ f,G ′ ) -n ′ m r ′ m )
for the second best coalition G ′ , divided by the number of members in the winning group G w , i.e.,

ρ m = max i∈Gw b i + u max -u ′ max n m ≡ max i∈Gw b i + x, (11)
with x = umax-u ′ max nm > 0.
In the expressions of u max and u ′ max , n m and n ′ m are the number of members of coalitions G w and G ′ , respectively, and r m and r ′ m are the payment (max i∈Gw b i ) for the coalition G w and the payment (max i∈G ′ b i ) for the coalition G ′ , respectively. Note that r m = max i∈Gw b i , so the payment expression is simplified as

ρ m = [P d,G -B(P f,G )] -u ′ max n m . ( 12
)
1) Truthfulness property: The following theorem illustrates that the proposed auction mechanism has the desirable truthfulness property.

Theorem 1. Truthfulness property The above proposed payment mechanism for our modified Vickrey auction ensures that all users have a dominant strategy of bidding their true valuation of resources.

The motivation behind our proposed payment mechanism is that the actual payment should be unrelated to an SU's own bid, but should benefit this SU in G w . In [START_REF] Shi | An auction-based mechanism for cooperative sensing in cognitive networks[END_REF], a higher payment than the winning SU's own bid benefits this SU because x > 0, and the benefit is equally distributed among all the SU members. From [START_REF] Unnikrishnan | Cooperative sensing for primary detection in cognitive radio[END_REF], we can see that the actual payment does not depend on the SUs' individual bids. This property holds for all the cases except when the highest bidder is also the highest bidder for the second highest utility group. To avoid having a key node (i.e, a node that is advantageously placed and thus most likely to be part of multiple candidate coalition groups) drive the bid price for multiple coalitions, and thus have incentives to overbid, the head node will modify the auction as follows. In the case that the highest bidder in the winning coalition is also the highest bidder in the runner up coalition, the second highest utility will be computed based on a price computed using the second highest bid in the coalition, thus effectively discounting the highest bidder. This change ensures that coalitions with the highest and second highest utility will not have a common bid price in this particular situation, and thus the proof of truthful bid will hold for all cases. The detailed proof steps for the theorem are given as follows for a general case, when we assume that the highest bidder in the winning coalition is not the same as the highest bidder in the runner up coalition.

Proof: We note that a SU cannot change the winning decision unless it has the highest bid in the winning group.

Suppose that SU j who has the highest bid in its group decides to bid higher than its true valuation: b j + y, y > 0. In this case, the user will remain the highest bidder in its group. Given this scenario, there are two possible cases:

(a) The group that SU j is involved in loses this auction, which results in u m,j = 0. If the group would have won this auction by SU j bidding b j , then this SU's utility would have been u m,j = b j + x -C e,m > 0.

So overbidding decreases its utility. If bidding the true valuation would not have won this auction, then still u m,j = 0, which implies that there is no incentive for the user to overbid. (b) The group that SU j is involved in wins this auction, which implies that SU j would also have won with a bid b j , because a lower bid yields to a higher utility for the requesting SU. The SU j gets paid b j + y

+ x ′ with x ′ = [P d,G -B(P f,G )-nm(bj +y)]-u ′ max nm =
x-y given other SUs are bidding their true valuation. Therefore, the actual payment is b j + x, which is the same as what is paid when this SU bids truthfully.

Suppose that SU j decides to bid lower than its true valuation: b j -y. No matter whether this SU is still the highest bidding in a group or not, it both means the highest bid decreases and the same discussion applies. Without loss of generality, for illustration purposes, we consider the case in which this SU still has the highest bid. Similar to the overbidding case, there are also two cases:

(a) The group that SU j is involved in loses this auction, which implies that SU j would also lose with a truthful bid b j . Therefore, the lower bid does not change the outcome of this auction. In other words, this SU does not have an incentive to underbid its true valuation. (b) The group that SU j is involved in wins this auction. If this SU's action has changed the outcome of this auction by underbidding, then this SU gets paid b j -y + x ′ , where x ′ can be determined as

x ′ = [P d,G -B(P f,G )-nm(bj -y)]-u ′ max nm = y -x.
Then the actual payment for this SU is b j -x < b j , where b j is the minimal price this SU would accept to be paid for its energy expenditure. If this SU would also have won without lowering its bid, the payment that this SU gets when underbidding is decreased to b j -x from b j + x when bidding truthfully, because this SU has the highest bid in this group. Therefore, this SU does not have an incentive to underbid its true valuation.

By defining the actual payment ρ m (which is greater than the initial payment r m ) when selecting coalition members, the head node's final utility decreases. However, we show that the effective utility of a head node is positive, which ensures that the head node will have an incentive to initiate the cooperation. The head node's effective utility is defined as

u h = P d,G -B (P f,G ) -n m [P d,G -B(P f,G )] -u ′ max n m = u ′ max > 0. ( 13
)
2) Bidding: We propose a three-dimensional bid structure, B i = (p d,i , p e,i,k , b i ) for the downlink case and B i = (d i,BS , p e,i,k , b i ) for the uplink case, where p d,i is the local detection probability of node i, d i,BS is the distance between node i and the base station, node k is the requesting node, p e,i,k is the error probability over the link between node i and node k, and b i is the price asked by node i. This three-dimensional bid mechanism will allow the auctioneer to evaluate its gains in terms of the detection probability that a new cooperating user may bring to the coalition, as well as costs associated with both false alarm probabilities and virtual payments.

The detection probability and the error probability can be calculated using ( 1) and ( 5), respectively, given the known/estimated power and distance information. The bid price asked by SU i is defined as a function of its residual energy and its current virtual currency balance. In our simulations, we consider that the SUs have a given energy reserve and then this energy is gradually depleted without replenishment. Since SUs value energy, their cooperative price should increase when they have a small residual energy reserve and sufficient currency. The SUs' utility function captures the fact that their energy valuation is modulated by their current residual battery energy levels and their virtual currency balance (a "rich SU" would be less interested in accumulating more currency). Based on these observations, we propose a virtual currency bid (b i ) defined as follows:

b i = β c i ξ r,i , (14)
where β is a scale parameter, c i is the currency balance of SU i and ξ r,i is its residual energy.

IV. PRIORITIZED ACCESS FOR BIDDING

As a consequence of a node initiating a cooperation request, multiple response bids may collide on the common shared dedicated channel in our densely populated CR network. Based on our assumption of a lightly loaded network, we anticipate very few collisions in initiating requests for cooperation and substantial collisions for bid responses.

As such, for requesting SUs, a simple binary exponential backoff scheme for collision resolution is employed. In an exponential backoff scheme, the retransmission after collisions is delayed by an amount of time derived from the slot time and the number of attempts to retransmit. In a binary exponential backoff scheme, a random number of slot times between 0 and 2 z -1 is chosen after z collisions.

For the responding SUs, we propose a prioritized backoff access scheme in order to reduce the probability of collisions, to improve the delay in establishing coalitions, and to better prioritize the order of responses for various SUs. In what follows, we discuss the implementation aspects of our proposed cooperative sensing scheme. Firstly, we describe the proposed frame structure. Secondly, we define a priority level for the backoff response access for bidders, and finally, the detailed coordination procedure is described.

A. Modified frame structure

We have introduced the regular frame structure for cooperative sensing in Section II-B. This frame holds when all SUs have data to transmit and thus have a clear incentive in participating in cooperative sensing. In the context of lightly loaded networks, only SUs being selected by our auction game are participating in the cooperative sensing stage. Thus, our modified frame structure starts with a coordination sub-frame as depicted in Figure 2.

A coordination sub-frame is comprised of several Request-Respond-Acknowledge (RRA) phases, which are further divided into a request sub-phase, a response sub-phase and an acknowledgement sub-phase. The sub-phases consist of several slots. The number of RRA phases and numbers of slots in these sub-phases are implementation-dependent parameters which can be designed in order to optimize the performance of CR networks taking into account the SUs' distribution and network traffic characteristics.

In the request sub-phase, SUs who need to, and are able to ask for cooperation send their cooperation requests. In the following response sub-phase, SUs that hear a request and are interested to cooperate respond to the request with their bids. The requesting/head SU then selects SUs to form its cooperative sensing group/coalition in order to maximize its utility. In the acknowledgement sub-phase, the requesting SU pays the selected responding SUs and thus confirms the formation of a cooperative group.

During one coordination sub-frame, there is at most one successful request in the neighborhood, but in the entire network, there could be multiple successful requests as long as they are separated in space, such as not to interfere with each other. Winners in the coordination sub-frame will send their data in the data transmission sub-frame and we are assuming that a frame cannot be multiplexed by multiple users, so only one SU can win in the neighborhood, while in the large network, geographically distant SUs may transmit their signals at the same time. After the coordination subframe, a cooperative sensing sub-frame follows, in which the formed cooperative sensing group will collaboratively sense the spectrum to determine its availability. Finally, the data transmission sub-frame follows, in which the successful head SU will transmit its data if the sensing result from the cooperative sensing sub-frame is the absence of PUs.

B. Priority level

For the prioritized access, we define a priority level for responding SUs according to their bids, i.e., their local detection probabilities for the downlink case and the distances between them and the base station for the uplink case, the error probabilities for their reporting links and their bid prices. Assume without loss of generality that SU k is a requesting SU (head node). Then, the priority level for a bidding SU i in the downlink case (l DW i,k ) is defined as

l DW i,k = w 1 p d,i p e,i,k + w 2 (-b i ) , where w 1 + w 2 = 1, ( 15
)
where p d,i is the local detection probability of SU i, p e,i,k is the error probability of the reporting link between SU i and SU k, b i is the asked price by SU i, w 1 and w 2 are weights associated with the ratio of p d,i to p e,i,k , and b i respectively. We note that a high local detection probability, a good quality of the reporting link and a low price are preferred in terms of the requesting SU's utility. The priority level for a bidding SU i in the uplink case (l UP i,k ) is defined as

l UP i,k = w 1 d k,BS d i,BS • p e,i,k + w 2 (-b i ) , where w 1 + w 2 = 1, (16)
where d k,BS is the distance between the head SU k and the base station and d i,BS is the distance between the responding SU i and the base station. It is noted that the responding SUs that have smaller distances to the base station are given a higher priority.

The responding SUs' backoff windows are set according to their priority levels. More specifically, a responding SU i with a priority level l DW i,k or l UP i,k (denoted as l i in the following) will set its backoff window between t and t+2 L/ log(li) , where t is the starting time of the response sub-phase and L is used to scale the priority level and to guarantee the randomness. The impact of the parameter L selection on the performance of the proposed prioritized access algorithm will be discussed in Section V.

We note that the prioritized response statistically ensures that good bids are received first and thus allows the requesting SU to collect only the first N responses rather than to collect all the responses, without significantly degrading the performance. Further, the complexity of the winners' selection algorithm also decreases with the decrease in the number of received bids, as the head SU needs to consider all the possible combinations when determining the winning group that achieves a maximum utility.

C. Coordination procedure

In Fig. 3, we illustrate a flow chart for the prioritized access control for downlink coalition formation. At the beginning, SUs calculate their local detection probabilities when they have data to send. If their local detection probabilities are greater than a threshold p d,r (i.e., they have a good channel condition), they will perform individual sensing, otherwise, they will request cooperative sensing. The threshold p d,r can be determined according to the network QoS requirement. The difference between the downlink case and the uplink case is that, in the uplink scenario, SUs compare their distances to the base station with a threshold d up,r in order to decide whether to initiate a cooperation process or not, rather than compare their local detection probabilities with the threshold p d,r . For illustration purposes we present here the flow chart for the downlink case (Fig. 3).

At the beginning of a request sub-phase, if a SU has a nonempty queue, it will send a request packet if it has not heard any successful request in the previous request sub-phases in the current frame. If the SU has heard that a successful request has taken place in a previous RRA phase, it will defer its request to the next frame since only one SU can send its data in the current frame. If requests of several SUs collide in the same request sub-phase, the requesting SUs will not receive any response in the following response sub-phase and then they will reschedule their requests in another request sub-phase possibly in the same frame using again the binary exponential backoff scheme.

In the response sub-phase, the SUs who hear a request and are interested in participating in the sensing coalition will respond to the requesting SU with their bids by using a random backoff access with a backoff window modulated by their priority levels as described in Section IV-B. More specifically, a responding SU first calculates its backoff window according to its priority level, then it uniformly selects one slot within this window to respond with its bid. Colliding SUs abandon competition for the current RRA phase. The winners are selected by the head node, among all the successful received bids in this phase. In the acknowledge sub-phase, the head SU acknowledges the winners by broadcasting their payment.

V. SIMULATION RESULTS

The simulations in this paper are implemented in Matlab. We consider 32 nodes deployed in a square region of 3kmby-3km with a fixed base station at the center. The path loss exponent is chosen to be 3. For both downlink and uplink, PUs' transmission power is set to be 100mW and SUs' transmission power is 10mW. For the downlink case, the target false alarm probability is set to be 0.01 for the local energy detector, based on which a threshold for detection is determined. A threshold for the detection probability, set to be p d,r = 0.9, is used by SUs to determine whether or not to ask for cooperation. For the uplink case, a threshold for the distance from SUs to the base station is set to be 500 meters and SUs located farther will seek their neighbors' cooperation. All the SUs are assigned one unit initial energy and one unit initial currency. In our simulation, for illustration purposes, we exploit a simple model for SUs' energy depletion: every member SU consumes the same amount of energy (c e,m ), while the head SU consumes twice as much energy as member SUs (c e,h ). In this section, we use the convention that a group with x members has actually x + 1 total nodes, including the head SU. All the parameters are summarized in Table I, and all the presented simulation results were obtained by averaging over 100 runs.

A. PU and SU activity models

We use the same PU and SU activity models for both downlink and uplink. To model the PU activity, we use a two-state birth-death process with a death rate δ and a birth rate µ as in [START_REF] Lee | Optimal spectrum sensing framework for cognitive radio networks[END_REF], [START_REF] Xie | A parallel cooperative spectrum sensing in cognitive radio networks[END_REF]. We also assume that the duration of the ON state and the OFF state are exponentially distributed ( [START_REF] Lee | Optimal spectrum sensing framework for cognitive radio networks[END_REF]) with the parameters δ and µ, respectively. We chose the death rate δ = 4 and the birth rate µ = 1.5 for the numerical results. For the SU activity, we model SUs' data arrival as a Poisson process with an expected number of arrivals per frame, η = 0.5.

B. Coordination analysis based on one snapshot simulation

From the perspective of cooperative group formation, there is no difference between the downlink case and the uplink case, because the algorithm that facilitates group is independent of the utility function definition. We use the downlink transmission scenario to illustrate our simulation results.

Fig. 4 represents a snapshot of the cooperative group formation in our CR network at the end of an arbitrary coordination sub-frame. In Fig. 4, we represent the PU base station as a blue star, a successful requesting SU as a solid black triangle with its member SUs represented by a solid green square, and an idle SU who does not join in the cooperative sensing is represented as a circle. The red dashed circle explicitly illustrates a cooperative group. We note that there are only 18 SUs totally shown in the figure, rather than the entire group of 32 SUs deployed in the network, because the other 14 SUs are located near the base station and as such, will perform individual sensing due to their good channel quality and they are thus out of our scope for our task of illustrating the cooperative mechanism.

At the beginning of the request sub-phase in the first RRA sub-phase of an arbitrary chosen frame, SU 4 , SU 9 , SU 10 , SU 11 , SU 14 , SU 18 nodes have initiated requests for cooperation, but SU 9 and SU 10 collided because they are in the transmission range of each other. So according to the exponential backoff scheme, SU 9 rescheduled its request to the fourth request sub-phase in the current frame, and SU 10 would request again in the second request sub-phase of the current frame. The successful nodes, SU 4 and SU 11 cannot form cooperative groups because they do not have neighbors. SU 14 would like to select its only neighbor SU 5 to form its cooperative group, but SU 14 cannot afford the payment to SU 5 at this time, so no coalition is formed. SU 18 selected SU 15 and SU 17 as its members from all the successful responding SUs (SU 3 , SU 6 , SU 7 , SU 15 , SU 17 ) in order to obtain maximal utility. The responses from SU 8 and SU 12 collided, so they lost the opportunity of being selected as members. In the second RRA phase, SU 10 requested successfully this time and

C. Performance analysis of prioritized response

In order to understand tradeoffs among different performance measures achieved by introducing the prioritized response access, we consider the following three cases. In the description, we denote the qualified neighbors as the neighboring nodes with positive utilities, not members of another cooperative group and not currently waiting to initiate cooperation requests.

• Case I: Perfect response access.

This scenario represents an ideal case that involves no collisions, and can be implemented by perfectly scheduling all the responses to a cooperation request. • Case II: Complete prioritized response access.

For this scenario, all the qualified neighbors perform prioritized backoff first. Some responding neighbors may collide, but all the good responses are collected. In this case, some responses may not reach the requesting SU due to collisions and the time that the requesting SU needs to wait in order to collect all the responses may be long.

• Case III: Truncated prioritized response access.

The requesting SU only collects the first N responses, or only waits for a fixed period of time in the response subphase. This case is proposed to overcome the possibly undesirable long response sub-phase, at the cost of possibly degraded detection performance. For the numerical results illustration, the head SU collects the first two responses. In our simulation, we illustrate in Table II the average cooperative missed detection probability (P md,G ), the average cooperative false alarm probability (P f,G ), an estimate of the average computational complexity and the average window length of the response sub-phase for the downlink case over different SU layouts. In Table II, the computational complexity of the algorithm is estimated as the average number of successful responses, which is related to the number of combinations that need to be computed and compared by the head SU to maximize its utility (the head SU computes the power set of all the successful responding members, which is the set of all the possible subsets of these successful members).

We can see that the detection performance deteriorates in Case II and Case III compared to Case I, while the false alarm probabilities are kept within the same range. Furthermore, we see that the processing complexity for the head SU decreases significantly especially for Case III. When we calculate the number of combinations that the head SU needs to compare based on the number of received responses, the improvement becomes even more significant. For example, if the head SU receives 5 responses, it needs to compare 31 combinations; if the head SU receives 2 responses, it only needs to compare 3 combinations, which is a strong decrease in complexity compared to 31 combinations. In Case I, the number of successful response is equal to the number of qualified neighbors, while in Case II some neighbors' responses are not received by the head SU due to collisions. So the head SU receives fewer responses in Case II than in Case I. As expected, Case II has the longest response window. Again, in Case I, the neighbors' responses are coordinated perfectly and the length of the responding window is equal to the number of neighbors. In practice, Case III is more attractive, due to its simple implementation, short response window length and acceptable detection performance. The performance degradation is not significant because the prioritized access response will ensure that, statistically, the best bids will be received first.

From the energy consumption and coordination delay perspective, our proposed prioritized bidding response in conjunction with a proper truncation scheme can help achieve the minimal energy cost and detection time. A smaller number of responses means that SUs will spend less energy in signal transmission and processing and the system will have shorter frames, which corresponds to a smaller detection delay. Considering Case III in Table II as an example, when there are two successful responses, other SUs will quit from transmission and a large reduction of the number of combinations a head SU needs to consider also saves its additional energy. Moreover, the response sub-phase length in Case III is only around 13% of that for Case II. Considering that a coordination sub-frame may consist of several RRA phases, we can expect more improvement on the detection time.

D. Cooperative detection performance

As we have previously discussed in Section III-B2, for the uplink case we assume that the responding/member SUs that are closer to the base station are more beneficial for a head SU to get a higher utility. In Fig. 5, we show the cooperative groups' missed detection probabilities with respect to their average distances to the base station. We note the increasing trend of the curve which shows a tendency for the missed detection probability to increase with distances of reporting nodes to the base station, although the fading characteristic of the channel will affect this increasing trend, thus resulting in some fluctuations of the missed detection probability.

In our simulations we illustrate that the missed detection probability can be decreased if coalitions of nodes are formed based on our proposed auction-based mechanism, while keeping the false alarm probability within a desirable range and maximizing the system lifetime. In this subsection we focus on illustrating the missed detection and false alarm probability performance. In Fig. 6 and7, we show how the missed detection probability can be reduced compared to the individual sensing for different head nodes, which form small coalitions (two members), for the downlink and uplink cases, respectively. For the uplink case, only one PU is considered, which corresponds to the worst case for the energy detectors (i.e., no accumulated signal strength from multiple PUs received by SUs).

From both Fig. 6 and Fig. 7, we see that the detection performance is improved significantly when cooperation is incentivized between the head SU and its two member SUs. Without cooperation, the individual detection performance is below the acceptable level. We also note that the cooperative false alarm probability is kept within a desirable range. We can see that the detection performance for the uplink case is worse than that for the downlink case, and this is an expected result, as the uplink case is more difficult to analyze due to the lack of information on the nodes' exact locations, and thus relies on some model approximations.

In Fig. 8, we show the cooperative sensing performance in terms of the average missed detection probability and the average false alarm probability when the coalition has one, two and three members. The individual/non-cooperative sensing performance is represented by a zero-member coalition. We can see that the detection performance is improved when the SUs cooperate, increasing as the number of members increases. The improvement in the detection performance comes at the price of a higher false alarm probability. We can see that, by including the false alarm probability in the utility function definition, the proposed auction scheme limits the increase in the obtained false alarm probability for the coalition within desirable levels.

E. Residual energy distribution

A balanced energy expenditure is beneficial for achieving a longer network lifetime. If some SUs drain their energy much faster than others, their short lifetime would affect the network connectivity and topology, thus disabling the CR network. In Fig. 9, we show the variance of the residual energy across all the SUs in the network as it evolves in time, starting from the initial first frame to the last frame for which all the SUs are functional, i.e., they are not energy depleted. We noticed that the residual energy variance increases very slowly , with a measured maximum variance of about 0.04 for the downlink case and about 0.035 for the uplink case, which means that our proposed mechanism yields an even battery life distribution and thus maximizes the network lifetime.

F. Discussion on parameter selection

In our proposed prioritized response access, we introduce the weights w 1 and w 2 in the definition of the priority level (see [START_REF] Letaief | Cooperative communications for cognitive radio networks[END_REF]), and the scale factor L to determine idle SUs' backoff window in Section IV-B. Selecting the ratio of w 1 to w 2 will determine whether the detection performance or the currency is more important and how much one metric is preferred over the other one. The factor L controls the backoff window length and implicitly influences the collision probability of the bidding responses. A larger L yields a longer response sub-phase, while a smaller L results in more collisions. Note that all of these parameters jointly affect the backoff window. Therefore, the network designer should determine w 1 and w 2 first according to his preference, and then L should be selected considering the tradeoff between the length of the response sub-phase and the collision probability. Table III gives the cooperative missed detection probability and the backoff window length for various values for the parameters mentioned above. We see that the detection performance is degraded due to collisions of responses in Case B (smaller L), compared with that in Case A, although a smaller backoff window is achieved in Case B. In Case C, the change of weights has a similar effect on the missed detection probability and the response window length to a smaller L. These parameters could be optimized with respect to various performance metrics, and this will be addressed in future work.

There are two other parameters defined for our proposed cooperative sensing, ǫ (price of unit energy) and β (scale factor in SUs' bidding), which are not set to adjust the system performance. The price of unit energy ǫ should be set according to the energy evaluation in the network and the scale factor β is used to balance the energy consumption, the currency and the detection performance (see [START_REF] Tobagi | Packet switching in radio channels-part II: the hidden terminal problem in carrier sense multiple-access and the busy-tone solution[END_REF] and ( 15)).

The virtual currency plays a critical role in our auctionbased mechanism. In a practical scenario, SUs are given an initial level of currency, which allows them to initiate cooperation and to interact with their neighbors in the auction game with the purpose of not depleting their currency. This initial level of currency can be experimentally determined based on the characteristics of the secondary network. As the network is functioning, some SUs may not be able to afford their members' payments in a frame, and then they need several frames to become able to form coalitions again, either by earning currency after they respond to their neighbors' requests, or by selecting different sets of member nodes, who bid with lower prices.

VI. CONCLUSION

In this paper, we have proposed a novel cooperative sensing framework for cognitive radio networks, which incentivizes selfish SUs to cooperate by introducing a virtual currency reward in an auction game. In this game, the SUs are guaranteed to bid their true valuation. A prioritized access control framework for the bid responses is also proposed to reduce the amount of collisions incurred, the sensing coalition set-up time, and the complexity of the bid selection algorithm. Our numerical results show that our cooperative sensing scheme improves the detection performance, while keeping the false alarm probability below an acceptable threshold. Future work will address some other aspects of parameter optimization for our design. In addition, an interesting extension to our current mechanism would be to integrate some schemes to mitigate the negative impact of malicious users.

Fig. 1 .

 1 Fig. 1. Illustration of hidden PU problem and receiver uncertainty problem.

Fig. 2 .

 2 Fig. 2. Illustration of the modified frame structure for coordination.

Fig. 3 .

 3 Fig. 3. Flow chart of the coordination procedure.

Fig. 4 .

 4 Fig. 4. A snapshot of the cooperative group formation. Illustration for the downlink case.

Fig. 5 .

 5 Fig.5. Detection performance with respect to the average distance from nodes in a cooperative coalition to the base station for the uplink case.

  Missed detection/False alarm probability Cooperative miss detection probability Cooperative false alarm probability Individual miss detection probability

Fig. 6 .

 6 Fig. 6. Downlink cooperative detection performance.

Fig. 7 .

 7 Fig. 7. Uplink cooperative detection performance.

Fig. 8 .

 8 Fig. 8. Downlink/Uplink cooperative detection performance with respect to the size of coalitions.

Fig. 9 .

 9 Fig. 9. Downlink/Uplink residual energy variance over all the SUs.

TABLE I PARAMETERS

 I FOR THE COOPERATIVE SENSING PROTOCOL

	Notation	Value	Description
	P tx,P U	100mW Transmission power of the base station;
	P tx,SU	10mW	Transmission power of SUs;
	ν	3	Path loss exponent;
	p f	0.01	SUs' local false alarm probability used
			to determine the local detection thresh-
			old;
	P f,th	0.1	Constraint on false alarm probability
			for the cooperative group;
	p d,r	0.9	Detection probability threshold for the
			downlink case;
	dup,r	500	Distance threshold for the uplink case;
	ǫ	0.1	Price of a unit energy;
	ce,m	0.01	Member SUs' energy expenditure per
			cooperative sensing;
	c e,h	0.02	Head SUs' energy expenditure per co-
			operative sensing;
	β	0.01	Scaling parameter for SUs' bids;
	w 1	0.1	Weight of the ratio of p d,i to p e,i,k in
			the priority level;
	w 2	0.9	Weight of bid b i in the priority level;
	L	10,5	Scaling parameter for SUs' backoff
			window;
	δ	4	Death rate of PU's birth-death process;
	µ	1.5	Birth rate of PU's birth-death process;
	η	0.5	SUs' packet arrival rate;

TABLE II PERFORMANCE

 II WITH DIFFERENT RESPONSE SCHEMES. SU 13 to form its cooperative group. When it came to the fourth RRA phase, SU 9 defers its request because SU 10 has succeeded in the previous RRA phase.

		Case I Case II Case III
	P md,G	0.0071	0.0084	0.0119
	P f,G	0.0369	0.0395	0.0345
	Complexity	6.4	4.7	2.0
	Window Length	6.4	67.8	8.8

selected

She's interested in performance evaluation of wireless networks (cognitive networks, DTN, ad hoc networks, wireless embedded networks) using game theory, multiobjective optimization and metaheuristics. She's been working as well on fountain and network coding for wireless sensor networks.