Karen Miranda
email: kmiranda@correo.cua.uam.mx

Nathalie Mitton
email: nathalie.mitton@inria.fr

Victor Ramos Ieee

Senior Member

An autoregressive estimator for overhead reduction in Substitution Networks

Keywords: Surrogate data, autoregressive processes, overhead, substitution network

A substitution network is a temporary network that self-deploys to dynamically replace a portion of a damaged infrastructure by means of a fleet of mobile routers. Some efficient solutions deploy robots based on active measurements. A robot/node in the network may use active link monitoring to assess the link quality towards its neighbors through the use of probe packets. Such probe packets are sent periodically at a given rate, and so, the accuracy of the measurements depends on the number and the frequency of exchanged packets. However, exchanging probe packets is energy and bandwidth consuming, thus active monitoring is considered as a costly mechanism. Even so, active link monitoring is a technique widely used on many network protocols. In this paper, we focus on an adaptive positioning algorithm (APOLO) to self-deploy a network. APOLO is based on active monitoring to gather essential information from nodes. Therefore, we show how autoregressive estimation may be used to reduce the overhead caused by the active measuring technique. Moreover, it is possible to use surrogate data rather than real data to feed APOLO without impacting its performance.

I. INTRODUCTION

A substitution network is a temporary network that selfdeploys to dynamically replace a portion of a damaged infrastructure by means of a fleet of mobile routers [START_REF] Razafindralambo | Promoting Quality of Service in Substitution Networks with Controlled Mobility[END_REF]. We focus in this paper on substitution networks made of autonomous wireless robots that automatically self-deploy to surrogate the damaged networks. Their movements are based on some active measurements. Active measurement is a widely used technique that provides insights about the network performance. Nevertheless, its main disadvantage is that it introduces additional packets, causing communication overhead when collecting such measurements. Such additional packets are energy and bandwidth consuming; however, the accuracy of the measurements depends on the number and the frequency of the exchanged packets. If the probe transmission rate increases, the accuracy of the insights will increase as well; nevertheless, the corresponding overhead increases proportionally consuming network resources. Obviously, there exists a compromise between the information accuracy and the transmission rate of probe packets [START_REF] Baccour | Radio Link Quality Estimation in Wireless Sensor Networks: A Survey[END_REF]. Such trade-off is specially important when a decision making process relies on the information gathered by using the probe packets such as in the case of the adaptive positioning algorithm.

In a previous work, we have proposed an adaptive positioning algorithm called (APOLO) to self-spread mobile routers in substitution networks [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF]. Such algorithm allows the routers to self-deploy by using controlled mobility based on the link quality. The link quality is measured in terms of delay, received signal strength (RSS), or signal to noise ratio by means of active measurement. To this end, our proposed algorithm sends out probe packets to all the nodes in the one-hop communication range; each node receiving the probe packets answers with reply packets; thus, the router computes the next movement and its new placement based on the replies received.

Reducing the packet transmission rate allows to scale down the corresponding overhead. However, regarding APOLO the trade off between the consumed resources and the data accuracy is reflected on the time it takes to routers to arrive at their final location since it takes more time to acquire the necessary data to make a decision.

We may find some similar problems in the literature. For instance, the Hello protocol, also known as the neighbor discovery protocol, allows neighbor nodes to establish and maintain the neighborhood relationships in wireless ad hoc networks [START_REF] Giruka | Hello Protocols for Ad-Hoc Networks: Overhead and Accuracy Tradeoffs[END_REF]. For that purpose, each node sends Hello messages at regular intervals to claim/notify its existence. Thus, the main issue is to determine the optimal transmission rate for messages. Likewise, in wireless sensor networks (WSN) the communication task consumes most of the energy [START_REF] Raza | What does model-driven data acquisition really achieve in wireless sensor networks?[END_REF]. One method to reduce energy consumption is to reduce the number of messages exchanged between nodes. The goal of data reduction techniques is, precisely, to reduce the data exchanged between the sink and the sensor nodes. In particular, data prediction techniques reduce the amount of information sent by building a model of the data evolution. In both cases, as presented in [START_REF] Li | Mobility Prediction Based Neighborhood Discovery in Mobile Ad Hoc Networks[END_REF], it is possible to use autoregressive modeling to solve the trade-off between accuracy and resources consumed.

In this paper, we propose to use surrogate data obtained by means of an autoregressive model to avoid data starvation periods and reduce the overhead in the network. The remaining of the paper is structured as follows. Section II describes the importance of the overhead-accuracy trade off for network characterization. Then, Section III reviews the concepts of time series used in this paper. In Section IV, we describe our proposal to use surrogate data in order to reduce the exchange of probe packets. Section V describes the simulation settings and present our results. Finally, we sketch out some concluding remarks in Section VI.

II. OVERHEAD AND ACCURACY COMPROMISE

Active measurement is a well known approach to characterize the conditions and performance of a given network. To that end, active measurement techniques introduce extra packets into the network, which are known as probe packets [START_REF] Luckie | Towards improving packet probing techniques[END_REF]. Such probe packets provide insights about the network behavior like packet loss, delay, and jitter [START_REF] Hasib | Limitations of Passive & Active Measurement Methods in Packet Networks[END_REF].

Nevertheless, adding packets to the network traffic poses several challenges, particularly on wireless networks. For example, since the IEEE 802.11b [START_REF]medium access control (MAC) and physical layer (PHY) specifications, IEEE standard[END_REF] amendment may use several data rates namely 1 Mbps, 2 Mbps, 5.5 Mbps, and 11 Mbps, the amount of resources consumed by a packet relies on the rate at which the packet is transmitted; i.e., a given packet transmitted at 11 Mbps consumes less resources than an identical packet transmitted at 1 Mbps. Furthermore, it is necessary to consider the additional resources in terms of storage and analysis of the aggregated traffic as well as the cost induced by latency. Therefore, there exists a trade-off between the amount of probe packets transmitted and the accuracy of the obtained values [START_REF] Reddy | On the Accuracy of Sampling Schemes for Wireless Network Characterization[END_REF]. This is specially important when a decision-making process depends on data collected during the sampling intervals.

Apart from error as an important metric to evaluate different mechanisms, the ultimate goal is to make the same decision with less information. Particularly, our deployment algorithm needs to gather data about the link quality to decide the direction on which the router must move. Such a task depends on the transmission rate of probe packets to collect data for link quality. In other words, if the rate is too high for the decision making process, valuable resources such as energy or bandwidth would be wasted; conversely, if the rate is too low, it would cause data starvation periods where the router needs to make a decision but it does not have enough information to do so.

To illustrate the overhead and accuracy compromise in substitution networks, we consider a simple scenario composed of one source, one destination, and one router. First, we execute the adaptive positioning algorithm without modifications; then, we execute the same algorithm and we reduce the packets frequency by increasing the time between probe periods, that is, just sending one-fifth of the total of probe packets in normal conditions. Finally, we increase once again the time between probe periods, sending one-tenth of the probe packets. Figure 1 shows the corresponding behavior, where we may observe that by choosing the normal rate, the router reaches the middle point after 600 s of simulation. However, when we reduce the probe frequency, the time the router takes to reach the same point drastically increases. Thus, the overhead-accuracy tradeoff has an evident impact on the performance of APOLO.

III. SOME BACKGROUND ON TIME SERIES MODELS

Before describing our proposal to reduce overhead, we present a brief introduction to time series models for a good understanding of forecasting-based techniques. Time series forecasting methods are commonly used to predict future values of a process as a function of previous samples from a given series. In particular, the autoregressive (AR) model is widely used because of its simplicity and low complexity. This model predicts the value of X i+1 , which is denoted by Xi+1 , as a weighted sum of the previous M values of the process X i . The AR(M ) model is defined as follows:

Xi+1 = M m=1 φ m X i-m + i , (1)
where φ m represents the model coefficients, M is the model's order, and i is white noise. There are several approaches to estimate the values of φ m for m ∈ [1, . . . , M ], such as, Yule-Walker equations, ordinary least squares, maximum entropy estimates, geometric lattice method, and forward-backward method [START_REF] Proakis | Digital Signal Processing[END_REF]. In practice, the selection of the order's model M for a given data is calculated by balancing the error generated by the model against the number of parameters. It is easy to reduce the error by increasing the order, however, this requires a greater number of unknown parameters, consequently, increasing the resource requirements for computation.

The autoregressive-moving average model (ARMA) and its generalization on the autoregressive integrated moving average model (ARIMA) are a combination of the AR and the moving average (MA) models. In both, the AR branch represents the dependency between the current value and the M previous values, while the MA branch represents the influence of current and past errors due to white noise on the current and future values [START_REF] Proakis | Digital Signal Processing[END_REF].

IV. DATA REPLACEMENT

In this section, we describe how to apply autoregressive estimation to reduce the overhead produced by the use of probe packets. First, we sketch our proposal to reduce the overhead by means of autoregressive estimation and next, we evaluate the usefulness of our proposal. As we report in Section II, it is important to reduce the number of artificial packets injected into the network preserving at the same time the accuracy of the measurements.

In [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF], we have presented the adaptive positioning algorithm (APOLO) for self-deploying mobile routers in a Xprev Xnext

1 1 2 2 k k k k 2 2 1 1
Probe packet

Reply packet

Fig. 2. Example of a probe period for two neighbors.

substitution network. During the substitution network lifetime, APOLO is executed in each mobile router to determine whether it has to move by using the feedback of the link quality coming from one-hop neighbors. APOLO consists of three major stages. i) APOLO measures the link quality by means of one link parameter, e.g., RSS or SNR. ii) APOLO computes the gathered data and makes the movement decision, i.e., if the router needs to move or not to improve the link quality; and iii), APOLO determines the direction of the movement and the router moves accordingly.

Figure 2 depicts a probe period for two neighbors, X prev (previous hop) and X next (next hop), and one mobile router. The router broadcasts probe packets to all neighbors in one-hop communication range and receives reply packets in a unicast fashion from such neighbors. At every probe period, the router sends k probe packets to its neighbors, for example, if the number of neighbors is two and k = 10, the router sends 20 probe packets and receives 20 reply packets. Of course, this number is proportional to the number of nodes within the range and according to the probe period frequency. Thus, the number of exchanged packets between the router and its neighbors has a rapid growth when the number of nodes in the network increases. It is important to recall that the probe period and decision making period are independent from each other, even though the decision making process relies on data collected by the probe packets.

As we mentioned in Section II, we may reduce the number of probe packets by reducing their transmission rate. However, this causes an increment in the deployment time. Therefore, we propose to avoid the data starvation periods by substituting the missing information with estimates generated by an estimator.

A. Autoregressive Estimator

We now describe our AutoRegressive EStimator (AREs) for overhead reduction. At the beginning of the simulation, every router r executes the adaptive positioning algorithm and keeps track of the averages obtained for each link sampled. Those average samples X i , i = 0, 1, 2, 3, . . . form the time series of interest feeding our algorithm. Thus, each router builds one model per neighbor in the one-hop communication range to predict the link quality of its neighbors. We find that if autoregressive mechanisms are well tuned, important improvements may be achieved on the estimation of real data [START_REF] Miranda | Using efficiently autoregressive estimation in Wireless Sensor Networks[END_REF]. Therefore, we choose the autoregressive model as detailed in Section III by using the Yule-Walker method to calculate the model coefficients. The model's order M is the value that minimizes the mean squared error, MSE, given by

MSE = 1 n n i=1 Xi -X i 2 .
At decision period j, router r estimates the value of the link quality X fed with its own estimates until a new probe period brings new data. Then, the algorithm corrects the divergence between real and estimated data by feeding the estimator with real data at each probe period. In other words, we use the estimated values to replace the actual values when the latter are not available due to the overhead reduction. Thereby, the decision making period is not delayed by decreasing the probe transmission rate. Once the actual data arrive, our estimator uses them to update the AR model.

We describe the major steps of our overhead reduction proposal as follows. At each router r, the average values of the link quality X i , i = 0, 1, 2, 3, . . . constitute a time series. From it, each link in the routers neighborhood is associated to a time series, separately, with individual model's order and individual coefficient values. The estimator collects a set 10 samples, which is equivalent to 10 probe periods. Thus, at probe period j > 10:

• Each mobile router builds one model for each neighbor in the one-hop communication range.

• The estimator is fed with its own samples until the next probe period.

• The estimator retrieves the computed values.

• Based on the estimated values, the router moves accordingly.

V. EVALUATION

We consider a wireless network composed of mobile routers that may move on the two-dimensional Euclidean space. We use "node" as a generic term for any device into the simulation neighborhood, for instance, mobile or classic routers. For the sake of simplicity, we assume that the transmission range R of a node u is the area in which another node v can receive/send messages from/to u; i.e., d(u, v) < R(u), where d(u, v) represents the Euclidean distance between u and v, and therefore, it exists a link X between u and v. We assume that two nodes are "neighbors" when they are within the communication range of each other. We use X to refer to the links with the neighbors of a mobile router. Likewise, we assume that some of the devices are fixed, that traffic needs to be transferred between two fixed devices, and that the wireless routers dynamically move in the scenario and act as relays, regardless of the routing protocol.

We define the quality of a communication link, or just "link quality", as the probability that a message transmitted on the link is successfully received, that is, the reliability of the link [START_REF] Souryal | Rapidly-Deployable Mesh Network Testbed[END_REF]. We use the received signal strength (RSS) as a value to measure the link quality since its value retrieves insight of the performance of a wireless network [START_REF] Flushing | A mobility-assisted protocol for supervised learning of link quality estimates in wireless networks[END_REF]. Nevertheless, other link quality measures may be used [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF].

We use the term "broadcast" to refer to the message propagation in a router's neighborhood in order to obtain the link measurements. Also, we refer to the control packets of routing protocols as "Hello" messages or beacons and to the packets used in active measurements as probe packets. Finally, we define the term controlled mobility as the ability of some nodes, specially routers, to move by themselves to a specific destination or with a specific goal, i.e., the opposite of a random moving [START_REF] Natalizio | Controlled mobility in mobile sensor networks: advantages, issues and challenges[END_REF].

In this paper, we use the Dynamic Source Routing (DSR) protocol for our set of simulations [START_REF] Johnson | Ad Hoc Networking[END_REF]. DSR is a selfmaintaining routing protocol designed for multi-hop wireless networks composed of mobile nodes. DSR uses on demand routing allowing each source to determine the route used to transmit its packets to the corresponding destinations. DSR consists mainly of two mechanisms, Route Discovery and Route Maintenance. The Route Discovery cycle is used to find on demand a route between the source and the destinations. Route maintenance is used to ensure that the paths remain optimum and loop-free as network conditions change. DSR avoids additional traffic, for example, Hello packets by using source routing; i.e., by including the entire route into the packet header and by storing the routes in caches.

To evaluate our proposed estimator, we use the NS-2 network simulator [START_REF] Ns | Network Simulator v.2.29[END_REF]. We compare our proposal to the original adaptive positioning algorithm. First, APOLO is executed without any modifications. Then, we reduce the probe packets transmission rate, and replace the missing data by using estimates generated by means of AREs. We use the relative error to assess the accuracy of our estimator. The relative error is equal to:

RE = | Xi -X i | X i . ( 2
)
We use the received signal strength (RSS) as input for both algorithms, nevertheless, it is possible to consider other link metrics, such as signal-to-noise ratio (SNR) or roundtrip time (RTT). We execute 50 simulations of 1500 s for each algorithm in order to obtain average results. In all the simulations, the IEEE 802.11 DCF standard and the two-ray ground reflection model are used. We consider a scenario composed of two nodes, n1 and n2, out of the range of each other, the distance between them is 250 m. In order to communicate n1 and n2, a router r1 must be deployed. We consider that such router starts at 10 m close from n1 and it must move to allow the communication between n1 and n2 such at is shown in Figure 3. Specifically, our proposal constructs an AR model for each neighbor denoted by X prev (previous hop) and X next (next hop), respectively.

In Figure 4, we compare the performance of our proposal, replacing the data with estimates, with the original positioning algorithm that uses the actual values. We show that by using autoregressive estimation, the router achieves the optimal position after ∼600 s as the original algorithm, i.e., the router makes the same decision for its movement decision based on the estimated values with the same delay. Furthermore, we present the relative error for every sample of the model built in Figure 5. In both plots, most of the values for the relative error are smaller than 0.2; i.e., less than 20% of the error after the sample number 200. RE achieves the smallest values during the simulation, this corresponds to the instant of time when the router achieves the optimal position. Table I summarizes the gain in terms of the number of probe periods and the exchanged probe and reply packets. From such a table, we observe a considerable reduction of up to 80% on overhead during the simulation. Moreover, we modify the scenario depicted in Figure 3 by adding a mobile router (r2) and increasing the distance between n1 and n2. Then, we compare the performance of the positioning algorithm using actual data and surrogate data. The results are presented in Figure 6 where both routers achieve their final position 300 s by executing both algorithm the results above presented.

VI. CONCLUSION

In this paper, we employed autoregressive estimation in wireless substitution networks for overhead reduction. We have reduced the number of probe packets exchanged by up to 80%, while at the same time maintaining the accuracy in the movement of routers. In both, the original positioning algorithm and our proposal, the router achieves the same position by expending the same time. Clearly, replacing actual samples with accurate estimates is an effective approach to reduce the overhead caused by active measurement.

Fig. 1 .

 1 Fig. 1. Impact of the overhead-accuracy trade-off on the performance of the adaptive positioning algorithm.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Scenario 1: One source, one destination, and one mobile router.

Fig. 5 .

 5 Fig. 5. The relative error of the estimated values for Xprev (previous hop) and Xnext (next hop) by using the Yule-Walker method as a function of sample number.

Fig. 6 .

 6 Fig.6.Performance of the positioning algorithm using actual data and surrogate data as a function of time.

TABLE I

 I

	.	PACKET EXCHANGE COMPARISON
		Probe Periods	Probe Pkts.	Reply Pkts.
	change	428.7	8345.3	8344.14
	Reduction to 20%	89.2	1730.86	1729.8
	Reduction to 10%	45	863	862.3

Finally, we have chosen a gathering information cycle of 10 probe periods to calculate the estimator coefficients. Nevertheless, these values may be not optimal, thus, our future work in this direction will focus on finding the optimal values for the percentage reduction and gathering period. We will evaluate different values and will observe the impact on our mechanism.


Gregor Schiele

John Soldatos

Nathalie Mitton

Towards Interoperable IoT Deployments in Smart Cities -How

published or not. The documents may come

IoT technology enables the orchestration and coordination of a large number of physical and virtual Internet--Connected--Objects (ICO) towards human--centric services in a variety of sectors, especially in Smart Cities [START_REF] Townsend | Foreword in "The Handbook of Research on Urban Informatics: The Practice and Promise of the Real-Time City[END_REF]. Many research, pilot and commercial applications have been developed, ranging from RFID/Wireless Sensor Network applications to more sophisticated ones involving large numbers of different devices and ICOs. They are directly associated with significant business and societal impact, which makes the IoT paradigm part of relevant policies for sustainable urban development. However, this has resulted in the creation of several (parallel) IoT ecosystems, leading to IoT application silos within modern smart cities as shown in Fig 1 . Such technical silos are often the reflection of organizational silos in local government. As an example, the separation of law enforcement from the department of transportation and from the public works department results in different IoT deployments and associated technical silos.

In this paper we present the FP7 VITAL project [url1], which sets out to overcome IoT silos in Smart Cities and to enable ICO deployment and integration independently of the underlying IoT architecture. VITAL is a three year joint European project, started in September 2013 by a consortium of ten partners from Ireland, France, Greece, Italy, Spain, the UK and Turkey.

Semantic Interoperability solutions for IoT

Interoperability of IoT systems extends beyond technical/syntactic interoperability towards semantic interoperability, which mainly explores the use of a common ontology for describing resources across disjoint IoT systems [START_REF] Presser | The SENSEI project: Integrating the physical world with the digital world of the network of the future[END_REF]. Recently, several research initiatives have extended the ontology of the W3C SSN incubator group, which aims at overcoming the limitations of pre--existing XML--based formats [START_REF] Sheth | Semantic Sensor Web[END_REF] and the fragmentation of sensor ontologies into specific domains or applications [START_REF] Compton | The SSN Ontology of the Semantic Sensor Networks Incubator Group[END_REF]. This ontology describes sensors, observations, and related concepts but not domain concepts, e.g. for Smart Cities.

As an example of a system providing a common semantic layer, the OpenIoT project [url2] enables humans, devices and services to announce and annotate different (virtual) sensors/devices as W3C SSN compliant sensors. OpenIoT offers an open source Cloud-based IoT platform [url3], including components like a Sensor Middleware, a Cloud Data Storage and a Scheduler.

VITAL: Semantic Smart City Interoperability

The VITAL project builds on these approaches and extends them to ensure the semantic interoperability of evolving Smart City IoT applications and projects. It uses the SSN ontology to model data and OpenIoT as a common data management component. It extends them in two main aspects. First, it provides a much richer data model for Smart City applications, including city--wide information like demographics and Smart City stakeholders, as well as Smart City application information with city--specific Key Performance Indicators, e.g. for smart energy, smart transport, smart security etc. Second, it provides interoperable access not only to data coming from different IoT systems (like e.g. OpenIoT does) but also to services provided by these systems, e.g. discovery, monitoring and complex event processing. This allows to create higher level services that integrate these system--specific services into a single federated service view. VITAL will be validated in two smart cities that are represented in the project consortium: London (represented by the London Borough of Camden) in the UK and Istanbul (represented by the Istanbul Metropolitan Municipality) in Turkey.

Conclusion

VITAL will enable application and service providers to integrate services and data streams stemming from multiple IoT ecosystems, architectures and middleware infrastructures. This will allow to reuse and repurpose existing sensors and IoT systems, increasing the ROI (Return--on--Investment) associated with costly Smart City infrastructures. Subsequently, we hope to jumpstart the cost and time efficient development of new Smart City applications, both by city authorities and by an open developer community, leading to a new wave of such solutions in cities all over Europe.

Sensors/ICO

Fig 1 .

 1 Fig 1. Technical and organisational silo deployment in smart cities.

Figure 2 .

 2 Figure 2. VITAL platform overview.

DCS


Jean-Noël Fuchs

Pascal Lederer

Charge density wave in graphene: magnetic-field-induced Peierls instability

We suggest that a magnetic-field-induced Peierls instability accounts for the recent experiment of Zhang et al. in which unexpected quantum Hall plateaus were observed at high magnetic fields in graphene on a substrate. This Peierls instability leads to an out-of-plane lattice distortion resulting in a charge density wave (CDW) on sublattices A and B of the graphene honeycomb lattice. We also discuss alternative microscopic scenarios proposed in the literature and leading to a similar CDW ground state in graphene.

Introduction

The recent interest in graphene was triggered by the observation of an unusual "relativistic" quantum Hall (QH) effect by two groups [1,2]. This effect is a direct consequence of the peculiar density of states of graphene close to half-filling [3]. Shortly after these pioneering experiments, Zhang et al. [4] explored the regime of even larger magnetic fields, up to 45 T, and observed extra plateaus in the Hall conductivity σ xy . In contrast to the relativistic quantum Hall effect observed at lower magnetic fields, these extra plateaus cannot be explained by considering non-interacting electrons. In the present paper, we review the recent proposal of a magneticfield-induced Peierls instability for graphene on a substrate [5], which gives an explanation to the extra quantum Hall plateaus observed at high magnetic field. The Peierls instability leads to an out-of-plane lattice distortion resulting in a charge density wave (CDW) on sublattices A and B of the graphene honeycomb lattice. Other mechanisms leading to such a CDW ground state in graphene have been proposed in the literature and are discussed in the present paper [6,7,8,9]. The originality of the magnetic-field-induced Peierls instability scenario [5] is to rely on electron-phonon coupling via the substrate on which the graphene flake lies, rather than on Coulomb interactions between electrons [6,7,8,9].

Quantum Hall effect in graphene: non-interacting electrons

The graphene crystal is a honeycomb lattice of carbon atoms: a two-dimensional triangular Bravais lattice with a basis of two atoms, usually referred to as A and B. The distance between nearest neighbor atoms is a = 0.14 nm and the lattice constant is a √ 3. Experimentally, graphene sheets of area A ∼ (3-10 µm) 2 are deposited on amorphous SiO 2 /Si substrate. Applying a gate voltage V g via the substrate allows one to control the electronic filling of the graphene bands, which amounts to doping. The number of induced electronic charges is given by N c = V g C g /e where the capacitance per unit area can be estimated as C g /A ≈ ǫ/d ≈ 1.2 × 10 -4 F/m 2 , where -e < 0 is the electron charge, ǫ = ǫ 0 ǫ r (with ǫ r ≈ 4) is the silicon oxide dielectric constant and its thickness is d ∼ 300 nm [1,2]. a e-mail: fuchs@lps.u-psud.fr

The electronic properties of graphene are described by a standard nearest-neighbor tightbinding model [10] with hopping amplitude t ≈ 3 eV [11] between 2p z carbon orbitals. Each carbon atom contributes one conduction electron. There are 2N p electrons in the sample under zero gate voltage, where N p is the number of unit cells in the sample. The first Brillouin zone is hexagonal. Among its six corners, only two are inequivalent and called K and K ′ . We choose K = 4π/(3 √ 3a)u x and K ′ = -K. The resulting band structure features the merging of the conduction and valence band at precisely these two points: graphene is a two-valley (K and K ′ ) zero-gap semiconductor. Near these so-called Dirac points, the electrons behave as charged massless chiral fermions and the valence and conduction bands have the shape of a diabolo. The relativistic-like dispersion relation of electrons is ε k = ± v F |k|, with a Fermi velocity v F = 3at/2 ≈ 10 6 m/s about 300 times smaller than the velocity of light c. This results in a linear density of states close to the Dirac point. In undoped graphene (V g = 0), the valence band is filled and the conduction band is empty: the chemical potential is right at the Dirac points. Changing the gate voltage from zero allows one to fill the conduction band or empty the valence band.

In order to discuss the quantum Hall effect in graphene, we briefly review the Landau problem of a graphene electron in a perpendicular magnetic field [12]. The magnetic field is assumed weak enough to neglect any magnetic flux commensuration effect (for a study of the Hofstadter butterfly in graphene, see [13]) and we use the continuum approximation in which the tight-binding model reduces to the two-dimensional massless Dirac Hamiltonian. The Landau levels (LL) are

ε n = sgn(n) |n| ω c , (1)
where the "cyclotron" frequency is ω c = v F 2eB ⊥ / , and the LL index n is an integer. The unusual LL structure with a square root dependence in the perpendicular magnetic field is a direct consequence of the linear density of states close to the Dirac point. Each LL is 4N φ times degenerate, where the number of flux quanta across the sample N φ = eB ⊥ A/(2π ) gives the orbital degeneracy and the factor 4 accounts for twofold spin 1/2 and twofold valley degeneracy. Let ν = N c /N φ = C g V g /eN φ be the filling factor. When the gate voltage is zero, so is the filling factor and the central Landau level (CLL, n = 0) is half-filled as a result of particlehole symmetry. In addition, each LL is 4N φ times degenerate. These two facts alone show that a plateau at νe 2 /h occurs in the Hall conductivity σ xy each time the filling factor is close to sgn(n)(4|n| + 2) = ±2; ±6; ±10; . . . . In order to have extra quantum Hall plateaus, one has to provide mechanisms for lifting the spin and valley degeneracy. In the absence of interactions between electrons, the only such mechanism is the Zeeman effect, which lifts the spin degeneracy, but does not affect the twofold valley degeneracy. The Zeeman effect, which depends on the total magnetic field B tot , splits each LL and leads to a gap ∆ Z = g * µ B B tot , where µ B = e /2m is the Bohr magneton, m is the bare electron mass, and g * ≈ 2 is the effective g-factor [4]. If the Zeeman gap is larger than the LL width, one expects extra quantum Hall plateaus at ν = 4n = 0; ±4; ±8; . . . . Therefore in the absence of interactions between electrons, the only expected quantum Hall plateaus should occur at every even filling factor ν = 2n. In the experiment of Zhang et al., plateaus at ν = ±1 were observed at large magnetic field, suggesting that interactions between electrons play a role [4]. However, none of the other odd plateaus ν = ±3; ±5; . . . were observed. It is very simple to understand these facts if one assumes that the electrons have different on-site energies on the two carbon atoms in the unit cell, just as for boron nitride, which also has a honeycomb structure [14]. In that case the Dirac electrons become massive [14] and the LL are almost unchanged except for the CLL which is not valley degenerate anymore [15]: this is enough to understand the filling factors at which QH plateaus were observed. It now remains to find a microscopic mechanism leading to the generation of this mass. In the following section, we show that in the presence of a magnetic field phonon-mediated (indirect) interactions between electrons lead to a CDW ground state. The latter features different electronic charge densities on the two sublattices providing different on-site energies for A and B carbon atoms, and therefore leading to a mass for the Dirac electrons.

Magnetic-field-induced Peierls instability

Undoped graphene is a very peculiar two-dimensional metal: it has a Fermi surface consisting of only two points (K, K ′ ), which means that its density of states at the Fermi energy is vanishingly small. Such a Fermi surface features perfect nesting at wavevector Q = 0 and K, as testified by the Kohn anomalies found in the spectrum of its optical in-plane phonons [16]. This means that graphene is a quite unstable metal with respect to charge density modulations at wavevector Q and therefore, although two-dimensional, a good candidate for a Peierls instability [START_REF] Peierls | Quantum Theory of Solids[END_REF]. Electrons in free-standing graphene are strongly coupled to the in-plane optical phonons but are not coupled to the out-of-plane ZO phonon [16]. Such a coupling is also absent in graphite because each graphene layer is in a symmetric environment with respect to its neighboring layers. However for graphene on a substrate, this is not the case: as the substrate (amorphous SiO 2 ) is different from the superstrate (air), the coupling of electrons to the ZO phonons is not forbidden by symmetry. Such an electron-phonon coupling is actually provided by the interactions of the graphene sheet with the substrate, as we show below. The ZO phonons correspond to an out-of-plane vibration where the A and B atoms in the unit cell move out of phase. If this vibration is frozen-in, every second carbon atom is closer to the substrate than its partner in the unit cell: the honeycomb lattice is no longer flat but crinkled as an egg box. In that case, the A and B carbon atoms do not have the same on-site energy anymore, which means that the Dirac electrons have acquired a finite mass. In the following, we quantitatively develop this idea.

We now consider a spontaneous out-of-plane lattice distortion which -in the presence of the substrate -breaks the inversion symmetry of the honeycomb lattice and provides a mechanism for lifting the valley degeneracy in the CLL. Assume that the A (resp. B) sublattice moves away (resp. towards) the substrate by a distance η. Electrons are still described by a honeycomb nearest-neighbor tight-binding model, however the two atoms in the basis now have different on-site energies. The energy on atom A/B is called ±M . Close to the Dirac points and including the Zeeman effect, the LL read [15]

ε n,σ,α = sgn(n) M 2 + 2 v 2 F eB ⊥ |n| + g * 2 µ B B tot σ if n = 0 (2) ε 0,σ,α = αM + g * 2 µ B B tot σ if n = 0 , (3)
where α = ±1 is the valley index corresponding to the Dirac points αK, and σ = ±1 is the spin projection along the magnetic field direction. In terms of the low-energy effective theory, the distortion means that the Dirac electrons spontaneously acquire a finite mass M/v 2 F . The onsite energy difference lifts the valley degeneracy for the CLL only, with a valley gap ∆ v = 2M . Note that the effect of a nonzero on-site energy M on each n = 0 LL is very weak, of order M 2 / v 2 F eB ⊥ ≪ 1 for a typical magnetic field. The reason is that in every LL, apart from the CLL, each quantum state -independently of its valley index -has an equal weight on the two sublattices. This is, however, not the case in the CLL: electrons at the K (resp. K ′ ) point only reside on the A (resp. B) sublattice. This explains why breaking the inversion symmetry of the honeycomb lattice (by introducing different on-site energies on the two sublattices) lifts the valley degeneracy of the CLL only.

Such a lattice distortion spontaneously occurs because it lowers the total energy, just as in Peierls's mechanism [START_REF] Peierls | Quantum Theory of Solids[END_REF] except for the magnetic field playing an essential role here and for the crystal being two rather than one dimensional. Assume that the last partially filled LL is n = 0 (i.e. the gate voltage V g is such that |ν| ≤ 2). We show that in this case it is always favorable to slightly distort the lattice provided there is a perpendicular magnetic field 1 . The distortion lowers the electronic energy. This energy lowering comes both from the CLL, which gives an essential contribution, and also from all the n < 0 LL, which contribute in a less important way as we explain below. There are (2 + ν)N φ electrons in the CLL. They contribute an energy gain

E n=0 = -N φ (2 -|ν|)M (4)
because when ν < 0, all (2 + ν)N φ electrons gain each an energy M and when ν > 0, 2N φ electrons gain each an energy M but the remaining νN φ electrons loose each an energy M . This energy gain depends on the magnetic field through N φ . In addition, the energy gain is linear in the out-of-plane distortion η because the on-site energy is proportional to the distortion, as we discuss below: M = Dη, where D is a proportionality constant, akin to a deformation potential2 . The other 2(N p -N φ ) electrons that fill the n < 0 LLs, also contribute to the energy lowering. Each of them gains a small energy compared to what an n = 0 electron gains, as discussed in the preceding paragraph, but as there are many more of them, about 2(N p -N φ ) ≈ 2N p , we cannot neglect their contribution. In the tight-binding model, we find

E n<0 = -γ N p a v F M 2 , (5)
where the numerical factor γ ≈ 0.67. This energy gain is quadratic in the distortion, and therefore smaller than E n=0 at small distortion, and independent of the magnetic field. Actually, this term represents the full electronic energy gain for a lattice distortion under zero magnetic field. The distortion costs an elastic energy

E elastic = N p Gη 2 , (6)
where the out-of-plane distortion is assumed to be small η ≪ a and G is an elastic constant, which -in the adiabatic approximation -is related to the ZO phonon frequency at q = 0 by ω 2 0 ≈ 4G/m c , where m c is the mass of a carbon atom and ω 0 /2π is the phonon frequency at the Γ point. From the measured frequency ω 0 /2πc ∼ 800 cm -1 of the graphite out-of-plane optical phonon [START_REF] Dresselhaus | [END_REF], we obtain Ga 2 ≈ m c ω 2 0 a 2 /4 ∼ 14 eV. The total energy is therefore

E tot = E n=0 + E n<0 + E elastic = -N φ (2 -|ν|)Dη -γ N p a v F D 2 η 2 + N p Gη 2 . ( 7
)
The most remarkable difference in this expression with respect to the usual Peierls case is the presence of an energy gain linear in the lattice distortion η rather than proportional to η 2 ln η [START_REF] Grüner | Density Waves in Solids[END_REF]. We note that the phonon mediated (indirect) electron-electron interaction is g eff. el.-el. ∼ g 2 el.-ph. /( ω 0 ) ∼ D 2 /G. The dimensionless electron-electron coupling constant3 λ is therefore of order g eff.

el.-el. /t. Comparing the kinetic energy gain (in the absence of a magnetic field) and the elastic cost in equation (7) shows that it is λ = 2γD 2 /(3Gt).

As E n<0 and E elastic are both quadratic in the lattice distortion, we introduce a renormalized elastic constant G ′ = G -γaD 2 / v F and write an effective elastic energy:

E elastic + E n<0 = N p G ′ η 2 . ( 8
)
The effect of the n < 0 electrons is to reduce the lattice stiffness and therefore to enhance the distortion. We take it as an experimental fact that there is no spontaneous out-of-plane distortion in the absence of a perpendicular magnetic field, see also [11], which means that G ′ > 0. This means that the Peierls instability does not occur in the absence of a magnetic field. For the ZO phonon, it means that -in the adiabatic approximation -its frequency is renormalized by the coupling to the electrons as

ω 2 ≈ ω 2 0 + 4(G ′ -G)/m c = ω 2 0 (1 -λ).
Measuring the ZO phonon mode in graphene on substrate would directly give access to G ′ , and therefore provide an independent determination of the constant D through the equation

D = (G -G ′ ) v F /γa.
In order to obtain the ground state -within our mean-field approach -we minimize the total energy E tot , see equation (7), as a function of the distortion η and get

η = N φ N p 2 -|ν| 2 D G ′ , (9)
from which the valley splitting follows as

∆ v = N φ N p (2 -|ν|) D 2 G ′ ∝ B ⊥ , (10)
and the condensation energy is

E tot = -(2 -|ν|)N φ Dη/2.
Actually in the CLL, and only in that LL, the valley index is the same as the sublattice index. Therefore if at ν ≈ 0 all electrons in the CLL are in one valley, they are also only on one of the two sublattices: the ground state can therefore be described as a commensurate A-B (or site centered) CDW. The charge density oscillation is quite small however:

|N A -N B |/N p ≈ N φ /N p ∼ (a/l B ) 2 ≪ 1, where l B = /(eB ⊥ )
is the magnetic length. The usual Peierls instability, which results in a gap opening at the Fermi energy in the electronic spectrum, is accompanied by a softening of the coupled phonon mode [START_REF] Grüner | Density Waves in Solids[END_REF]. Approaching the instability from the metallic side, the phonon mode softens and goes to zero precisely at the transition -a phenomenon known as a giant Kohn anomaly [START_REF] Grüner | Density Waves in Solids[END_REF]. In order to see this effect in the case of the magnetic field induced Peierls instability where the driving parameter is the magnetic field rather than the temperature, we consider broadened LL. Broadening is due to disorder and slightly modifies the preceding calculation for lattice distortion at weak magnetic field, when the valley splitting ∆ v is smaller than the LL width ∆ imp . For example, for rectangular LL -the density of states being 4N φ /∆ imp inside a LL and zero otherwise -Eq. ( 4) is changed into

E n=0 = - 2N φ ∆ imp M 2 = - 2N φ ∆ imp D 2 η 2 , ( 11
)
while Eq. ( 5) remains unchanged since it involves totally filled LLs. The electronic energy gain is now proportional to η 2 . We therefore introduce still another effective elastic constant

G ′′ = G ′ -2 N φ N p D 2 ∆ imp ( 12
)
in order to write the total energy as E tot = N p G ′′ η 2 . The renormalized elastic constant G ′′ depends on the perpendicular magnetic field. A distortion only occurs if

G ′′ < 0, i.e. B ⊥ > B c ≡ 2π G ′ ∆ imp /3 √ 3ea 2 D 2
, which is always the case at large enough magnetic fields. This condition is precisely equivalent to requiring that the valley splitting ∆ v = 2Dη -given by Eq. ( 9) with ν ≈ 0 -be larger than the LL width ∆ imp . Therefore, as soon as B ⊥ is larger than the threshold value B c , the lattice is distorted -in other words, the ZO phonon is frozen-in -and the valley gap is larger than the LL width, which means that one can use the results obtained in the case of infinitely narrow LL. When B ⊥ < B c , the ZO phonon is strongly renormalized by a magnetic-field-dependent term and its frequency, in the adiabatic approximation, is

ω(B ⊥ ) ≈ ω(0) 1 - B ⊥ B c 1/2 , (13)
where ω(0) ≈ ω 0 √ 1 -λ is the renormalized phonon frequency at zero magnetic field. The phase transition toward the CDW ground state occurs at B ⊥ = B c , where ω(B ⊥ ) = 0.

Here we exhibit a microscopic mechanism providing the coupling of the electrons to the ZO phonon -i.e. the non-zero deformation potential D -via the interaction of the carbon atoms to the substrate. It is quite difficult to accurately predict the constant D and we will therefore only provide an order of magnitude estimate. The mechanism that we think gives the largest contribution results from the interaction of a single carbon atom from the graphene sheet with the amorphous SiO 2 substrate treated as a dielectric continuum. The non-retarded Lennard-Jones interaction energy of an atom at a distance r of a dielectric wall is given by E LJ (r) ≈ -(ǫ r -1) d 2 /(ǫ r + 1)48πǫ 0 r 3 , where d 2 is the atomic ground state expectation value of the squared electric dipole moment [START_REF] Aspect | [END_REF]. The on-site energy change resulting from the lattice distortion may be estimated as

±M ≈ E LJ (d 0 ± η) -E LJ (d 0 ) ≈ ± ǫ r -1 ǫ r + 1 d 2 16πǫ 0 d 4 0 η (14)
where the ± sign refers to sublattice A (+1) or B (-1), d 0 is the average distance between the graphene sheet and the substrate and we assumed that η ≪ d 0 . For a carbon atom d 2 ∼ 4ea 0 , where a 0 is the Bohr radius, which gives Da ∼ a(ǫ r -1)e 2 a 2 0 /(ǫ r + 1)πǫ 0 d 4 0 ∼ 1 to 14 eV depending on d 0 ∼ 0.1 to 0.2 nm. Therefore, the order of magnitude of the deformation potential Da is 5 eV. The condition G ′ > 0 that no Peierls instability occurs when B ⊥ = 0 implies that Da < Ga v F /γ ≈ 9.8 eV. Therefore, in order to match the experiment [4], we take the plausible value Da = 7.8 eV, which gives G ′ a 2 ≈ 4.2 eV. In the end, the dimensionless electron-phonon coupling constant λ = 2γD 2 /(3Gt) ≈ 0.8, which is quite a large value.

The mechanism proposed here features several differences with respect to the standard Peierls instability [START_REF] Peierls | Quantum Theory of Solids[END_REF][START_REF] Grüner | Density Waves in Solids[END_REF]: (i) the metal is two-rather than one-dimensional; (ii) the distortion does not change the Bravais lattice but only the point group symmetry -the inversion symmetry of the honeycomb crystal is broken by the instability but the triangular Bravais lattice is not affected by the distortion; (iii) the electron-phonon coupling does not exist in the isolated graphene crystal but is provided via the coupling to the substrate; (iv) the control parameter for the instability is the magnetic field rather than the temperature; (v) the metal (undoped graphene) is actually a zero gap semiconductor and has k F = 0 and the nesting condition is |Q| = 0, which indeed equals 2k F .

Charge density wave in graphene: direct electron-electron interactions

Many authors have considered the effect of direct (Coulomb) electron-electron interactions in graphene, in particular to study the quantum Hall effect. Depending on which aspect of the Coulomb interaction is thought to dominate, different scenarios have been proposed. A popular scenario is that of quantum Hall valley and spin ferromagnetism, see e.g. [9,21,22,23,24]. This is the graphene version of the well-known quantum Hall ferromagnetism: the exchange interaction between electrons favors ferromagnetism inside a partially filled LL. Indeed, it allows one to reduce the interaction energy -in other words, to gain exchange energy -at no kinetic energy cost when the LL are assumed infinitely narrow and flat. This mechanism predicts plateaus at every integer filling factor in contradiction with the existing experiments. A possible way out of this contradiction is to consider strong disorder, which naively speaking, broadens the LL and therefore, by restoring the possibility of kinetic energy changes, works against ferromagnetism [21]. This could explain the absence of certain QH plateaus at magnetic fields up to 45 T.

Apart from QH ferromagnetism, we are aware of only one other scenario: namely that of a commensurate A-B CDW ground state triggered by the magnetic field. This scenario exists in three different microscopic versions depending on which electron-electron interaction is believed to dominate. One version -the magnetic field induced Peierls instability -is the subject of the present paper and relies on electron-phonon coupling providing indirect interactions between electrons. The other two rely on Coulomb (direct) electron-electron interactions: one -the socalled magnetic catalysis -focusses on long-range Coulomb interactions, while the other relies on lattice-scale (extended Hubbard type) Coulomb interactions. All of these mechanisms lead to a similar ground state and therefore predict the same QH plateaus.

Long range Coulomb interactions

In the context of highly oriented pyrolytic graphite, Khveshchenko suggested that long range Coulomb interactions could also lead to a CDW ground state in the presence of a magnetic field [6]. This idea stemmed from the phenomenon of dynamical chiral symmetry breaking originally proposed in relativistic theories of (2+1)-dimensional interacting Dirac fermions. In this scenario, the electron-electron interaction comes from the Coulomb interaction in the continuum limit in which only the long range part of the interaction survives. Within the CLL, electrons and holes pair up to form excitons, as a result of the attractive Coulomb interaction, and these excitonic pairs Bose condense. This leads to the creation of an excitonic gap in the electronic spectrum, which is similar to what we called the valley gap ∆ v , but has a different magnetic-field dependence ∆ exciton ∼ e 2 /(ǫl B ) ∝ √ B ⊥4 . This mechanism only occurs in the presence of a magnetic field and has therefore been dubbed the "magnetic catalysis" of the excitonic instability [6,7]. The ground state can be described either as a Bose condensate of excitons inside the CLL or as an A-B CDW.

Lattice-scale Coulomb interactions

Several years ago, in the context of STM studies on graphite surfaces, Tchougreeff and Hoffmann [25,26] suggested that graphene could have a CDW ground state5 . They considered Coulomb interactions between electrons in an extended Hubbard model on the honeycomb lattice with on-site repulsion U ∼ e 2 /(ǫa) and nearest-neighbor repulsion V ∼ U , and neglected the longrange part of the Coulomb interaction. They showed that if the nearest-neighbor repulsion V was strong enough to overcome the effect of the on-site repulsion U , a CDW ground state should be favored. In the opposite case, a spin density wave (SDW) would result. Recently, several authors have shown that a magnetic field should help to trigger this CDW instability [9,8] -or the SDW depending on the precise U/V ratio [8]. In the CDW case, the corresponding valley gap is linear in the magnetic field ∆ Hubbard ∼ U (a/l B ) 2 ∝ B ⊥ just as in the magneticfield-dependent Peierls mechanism ∆ v ∼ (D 2 /G ′ )(a/l B ) 2 .

Conclusion

We have reviewed the proposal of a magnetic-field-induced Peierls instability in graphene leading to a CDW ground state [5]. The driving mechanism is the electron -ZO phonon coupling, which is provided via the interaction of carbon atoms to the substrate. The instability corresponds to the spontaneous breaking of the inversion symmetry of the graphene honeycomb lattice and results in Dirac electrons having an effective mass proportional to the magnetic field. Apart from electron-phonon interactions, there are other interactions leading to a CDW instability triggered by a perpendicular magnetic field [6,7,9,8]. As to the question of which is the dominant interaction leading to the instability in graphene, we mention two related examples of one-dimensional metals featuring a CDW instability. On the one hand, consider the well-studied case of polyacetylene, which dimerizes at low temperature and has long been described as being the prototypical example of a Peierls instability driven by electron-phonon interactions. It is now known that Coulomb interactions also play a very important role in the instability and that electron-phonon coupling alone is not enough to quantitatively explain the measured effect [28]. On the other hand, in a one-dimensional metal like KCP, the dominant mechanism leading to the Peierls distortion has been shown to be electron-phonon interactions [29]. In the case of graphene on substrate, it is therefore not clear at the moment whether a CDW does occur and if so, which is the driving mechanism leading to such a ground state in the presence of a magnetic field.

When |ν| >

2, there is no energy gained by distortion. The distortion only occurs for ν close to zero.

The corresponding electron-phonon coupling constant g el.-ph. that would appear in a Fröhlich-type Hamiltonian is g el.-ph. ∼ D /(mcω0), where mc is the mass of a carbon atom.

The quantity λ is commonly known as the dimensionless electron-phonon coupling constant, e.g. in the context of the BCS theory of superconductivity, eventhough it is actually a dimensionless (phononmediated) electron-electron coupling constant[START_REF] Grüner | Density Waves in Solids[END_REF].

This excitonic gap is of the same order of magnitude as the LL spacing ωc as the "graphene fine structure constant" e 2 /(4πǫ vF ) ≈ 0.5.

Their work was actually triggered by an early experiment on a graphene sheet on the Pt(111) surface[27]

Acknowledgments

We thank M.O. Goerbig for useful discussions, and I. Herbut and D. Khveshchenko for comments on the manuscript.