German Castignani
email: german@castignani.com.ar

Lucien Loiseau
email: lucien.loiseau@telecom-bretagne.eu

Nicolas Montavont
email: nicolas@montavont.net

An Evaluation of IEEE 802.11 Community Networks Deployments

IEEE 802.11 appears as the most popular technology for wireless access because of its low cost and high data rates capacity. In the recent years a new communication paradigm emerged, called the Community Networking, which takes advantage of existing residential 802.11 access points and is based on sharing some part of the bandwidth to members of the community. We evaluate the 802.11 environment, the quality of link, and the potential of these community networks in the city of Rennes, France. We aim at determining if these networks are offering enough coverage area to be considered as an alternative to cellular networks.

I. INTRODUCTION

Within the fourth generation (4G) wireless mobile environment, 802.11-based technologies are playing a major role because of their low-cost and high data rate capacity, allowing users to deploy their own networks and directly connect them to the Internet. This is confirmed by the extraordinary growth of WiFi products demand, estimated by market forecasts [START_REF] Snol | Wi-fi forecast to fly high this year[END_REF] to be augmented by 33% in 2010, with more than 60% of this demand being only caused by 802.11n-compliant products, due to its recent standardisation. This remarkable growth is not only related to new user devices but to APs as well, producing an increasing number of deployments. We can roughly categorize these deployments into two models: hot spot and community networks (CN). In the first case, APs are deployed in specific areas of cities, offering a geographically limited wireless access to users close to the APs. These APs are either plugged to a broadband Internet connection, or inter-connected via a wireless connection independent from the 802.11 wireless link dedicated to the users (which form a mesh architecture). The first city-wide WiFi deployments were proposed by municipalities (or a single operator) by installing APs in so-called hot spots across a city. In the second case, the CN paradigm is defined as the sharing of residential APs to a given community of people for accessing the Internet. A community is defined as clients from a single operator, or users that are collaborating together. Different residential Internet Service Providers (ISPs) provide users with 802.11 APs which have the ability to broadcast different network identifiers (ESSID). One of these ESSIDs is common to all clients and is broadcasted by all APs from the same ISP that have activated the CN service. Thus a user walking in a city can benefit from Internet access by using the CN. Even if current CN deployments are managed by ISPs, the origin of this kind of networks comes from small user communities having specific knowledge in wireless LANs, neighborhood deployments and associations. Additional information could be found in the Wireless CN forum (http://wcn.cnt.org/).

CNs thus appear as an interesting alternative to provide Internet access everywhere and for low cost. However their performance are still unknown and unpredictable; the deployment is random, as it depends on the number of clients, their willing to share, and their locations. Moreover, APs are deployed indoor, which may reduce the APs' coverage area and result in bad connection from a user on the street. In this paper, we propose an evaluation of these CNs and analyse whether they might be considered as a reliable and usable solution for an ubiquitous Internet access.

A. The 802.11 deployment problematic 802.11 operates in the free ISM band, so deployments are never totally controlled since anyone could deploy any device on that frequency band. This means that 802.11 devices can suffer from intra-system interferences (with other 802.11 devices) and inter-system interferences (with other technologies using the same frequency band). In the 2.4GHz band, 802.11 defines 13 channels (from 2.412GHz to 2.472GHz) in Europe. Each channel is 22MHz large and they are spaced 5MHz apart. This implies that adjacent channels are strongly overlapping, and that two APs operating in the same area should at least be separated by 22 MHz, which corresponds to 5 channels. For example, if an AP is using channel 1, then another AP in the same area should avoid channels 2 through 5. Due to this large overlapping, it is often recommended to only use channels 1, 6 and 11 [START_REF] Fuxjager | The myth of non-overlapping channels: interference measurements in ieee 802.11[END_REF]. Though not controlled by a central entity, channel assignment may be optimized by good practices, shared knowledge, or default equipment configurations. Nowadays, APs often come with automatic channel selection, which consists in determining the less congested channel to use. In this paper, one of our goal is to identify which channels are the most used and to determine whether the 1-6-11 deployments are a myth or match the reality. The used channels have an important impact on user mobility, since a mobile user should probe channels one after the other to find APs. By identifying which channels are the most used, we could prioritize those channels whenever a user is searching for an AP and thus minimizing the interruption time due to a handover from one AP to another.

B. The experiment

Within this work we aim to study the current 802.11 deployment in the city of Rennes, France. Rennes has a population of almost 208.000 inhabitants with an average density of 4.126hab/km2 . It is also a well-known interest area in computer sciences and telecommunications, with a vast number of research centers, universities and technological companies. The overcrowding of 802.11 deployments provides a high level of ubiquity to users, but a number of limitations may arise due to the unmanaged deployment of such networks. Some of them are related to interference, security issues and multipath loss, among others.

The experiment results we are presenting in this paper show the current and real wireless deployment in different parts of the city. We focused on the frequency usage, the level of security and the performance in terms of link quality. We also analyze the coverage of CNs to check whether a continuous connectivity could be used by a user moving in the city.

The outline of this paper is as follows. In section II we present the related work on hot-spot and community wireless networks, considering deployment issues and measurement studies. Then, in section III we present our experimentation platform, metrics and results. We also compare our results with a state of the art measurement study. We finally conclude the paper and delineate future work in section IV.

II. RELATED WORK

A. Hot spot Deployments

The first city-wide WiFi deployments were proposed by municipalities (or a unique operator) by installing APs in so-called hot spots across a city. These APs were either plugged to a broadband Internet connection, or inter-connected via a wireless connection independent from the 802.11 wireless link dedicated to the users (which form a mesh architecture). Some experimental and operational architectures can be cited: MIT Roofnet1 , Champaign -Urbana Network 2 , Oklahoma City Network [START_REF]Ock: It's all in the air[END_REF], Madison MadMesh3 and the Google WiFi Network4 , among others.

Aguayo et al. [START_REF] Aguayo | Link-level measurements from an 802.11b mesh network[END_REF] measure the performance of wireless links in a 38-node Roofnet deployment in Massachusetts. While presenting several metrics and analysis, they focus on the packet loss problem, concluding that intermediate loss rates is probably due to multi-path fading rather than attenuation or interference. Another measurement study performed by Brik et al. [START_REF] Brik | A measurement study of a commercial-grade urban wifi mesh[END_REF] during eights months focus on the Madison MadMesh Network. By using both passive and active measurements, the authors analyse the deployment's robustness in terms of link quality and mesh routing, client connectivity and network usage. They found that the bottleneck of the network is related to the client access side rather than the backbone side.

More centered on users activity, Afanasyev et al. [START_REF] Afanasyev | Usage patterns in an urban wifi network[END_REF] and Arjona et al. [START_REF] Arjona | The google muni wifi network-can it compete with cellular voice?[END_REF] studied the Google WiFi Network, a 500 APs mesh deployment in Mountain View (California). Afanasyev's study was more oriented on user activity and usage of the network (type of application and device, time of access, etc). Arjona et al. evaluated Voice over IP (VoIP) applications in mobile outdoor conditions to measure the potentials of Voice over (wireless) IP compared to cellular voice services. Testing VoIP did not give good results in term of mobility, because the network had several gaps of coverage. The authors also made a comparison with cellular networks using simple propagation models, concluding that AP density of the Google WiFi Network should increase from 12AP/km 2 to 81AP/km 2 to perform as well as cellular networks. Hot spots require a high level of investment and a dedicated infrastructure for network maintenance and operation. Because of this barrier, some Municipal WiFi (mesh) in the US failed [START_REF] Patel | Municipal wifi[END_REF], as is the case of Philadelphia city, where the city-wide deployment mutated to isolated hot spots around the city. With a totally different approach, the notion of CNs as presented in the next subsection does not suffer from this cost of deployment and maintenance.

B. Community Network Deployments

Recently, CNs emerged as a possible solution to provide Internet connectivity for a vast number of users in urban areas (see section I). CNs stand as selforganized and fully decentralized deployments, since APs are mainly connected to a residential broadband line. Due to this characteristic, APs are mainly deployed indoor without any deployment strategy, while hot spot APs are deployed outdoor. This is one of the aspect that motivated our experiment -to study if a user from a street can connect to these APs, and how long he/she can stay connected. Since these networks are based on opening the residential broadband access to the community, security and management issues arise as a challenge. These critical issues are studied by Vidales et al. [START_REF] Vidales | Metropolitan public wifi access based on broadband sharing[END_REF], where an enhanced architecture of CN deployments is proposed.

From a commercial point of view, the FON Wireless company (www.fon.com) appears as the leader of the community networks business, since they deployed one of the first shared-wireless infrastructure. They also set up an incentive model to motivate people to open their connections to the general public in a secured manner. In France, numerous communityaware ISP can be found on the market like Free (http://www.free.fr) and Neuf-SFR (http://www.sfr.fr). Moreover, users may find some APs deployed by these ISP as hot-spots in public spaces (not residential APs), that are accessible by using the same community identifiers.

C. Evaluation

One of the most interesting and complete measurement studies of metropolitan WiFi deployments (not limited only to mesh deployments) is proposed by Bychkovsky et al. [START_REF] Bychkovsky | A measurement study of vehicular internet access using in situ wi-fi networks[END_REF]. In this work, the authors focused on estimating the expected performance of 802.11b community deployments in the context of vehicular networking. This measurement study took 290 driving hours (within 232 days) by using up to nine cars implementing an embedded computer (CarTel) with a 5.5dBi omni-directional antenna. These cars performed active scanning to discover 802.11 APs. Then, when it was possible to associate, they configured an IP address and performed some data communication. Within this experience, they discovered over 32,000 APs, but they could only associate and ping in the 6.6% of the cases. Some interesting metrics have been presented in this work. The median amount of TCP data successfully uploaded by a moving car was 216Kb, with a median throughput of 30Kbytes/s. Regarding mobility, the average time of link-layer connectivity of a moving vehicle is 13s, independently from the speed of the vehicle up to 60km/h. The measured average time between two connections was quite high, around 75s. This study also identifies the main concerns the research community should focus on before these deployments become a reality. Commercial and legal issues may be studied. For instance, one hot topic in CN is related to incentives models, in order to motivate the introduction of the community paradigm. A credit based approach is proposed in [START_REF] Ai | Wi-sh: A simple, robust credit based wi-fi community network[END_REF]. Morover, Manshaie et al. [START_REF] Manshaei | Evolution and market share of wireless community networks[END_REF] proposed a gametheoretic model to study the evolution and potential market share of CNs, considering the competition with traditional licensed-band operators (3G, LTE).

Within this paper we aim to present and analyze a set of metrics defining 802.11 deployments in a medium-size European city. We focus on CNs since we observed an important relevance of these deployments on the whole 802.11 environment.

III. EXPERIENCE

A. Description

During the spring 2010, we performed an 802.11 APs deployment analysis along an 8km path in the city centre and some neighborhoods of Rennes, in France. We aim at identifying how many APs are deployed and how they are deployed, what are the coverage areas of the public hot spots and the CNs and what are the potential usages of this deployment for a mobile user. We are trying to answer the question: "Is it possible to access the Internet from everywhere in the city using an 802.11 access?". We also expect to use these results to document and further develop algorithms needed when a mobile user is roaming from one AP to another. As we have shown in [START_REF] Castignani | An evaluation of the resource discovery process in ieee 802.11 networks[END_REF], these algorithms highly depend on the channels used by the APs. In order to answer those questions, we used a laptop as a sniffer to capture the 802.11 frames along the defined itinerary. The materials and methodology of the experiment are presented in this section.

1) Materials: We captured the 802.11 frames with an Asus N10JB running Ubuntu 9. We extended the internal antenna by using an external DLink 7dBi omnidirectional antenna. The internal wireless card runs a modified version of the ath9k open source driver. In order to log the location of the captures, we used an external USB GPS receiver and osm-gps-map (http://nzjrs.github.com/osm-gps-map/) for placing the captures on a map. With regards to the results extraction, we implemented a set of scripts in Perl and C++.

2) Methodology: In order to maximise the success of AP discovery, we implemented some modifications in the MAC layer of the ath9k (mac80211 kernel module). We forced the Asus computer to perform Active Scanning every two seconds while moving around the city. This scanning procedure was performed by listening each channel for a longer duration than the one defined in the default ath9k implementation. First, the station tunes its radio on the first channel (2412M hz) and sends three Probe Requests on that channel. Then the station waits for 50ms for the reception of Probe Responses and Beacons frames, containing the information about different APs in the channel. This procedure is performed for each channel up to channel 13 (2472M hz). Therefore the time required to scan all the 13 channels is around 700ms (including the time to switch channels). At the same time, the station captures every second the geolocation information in a separate file. This file and the one with the responses from the APs are merged offline in order to obtain a complete view of the information of each AP, including the geographical data of the measure point. Regarding the mobility pattern, we mainly perform the experimentation by walking. However some captures outside the city center have been done by car, driving at a low speed, always below 45km/h.

B. Results

1) General Results: Fig. 1 summarizes the general results of the experience. Along the 8km path (Fig. 1(a)) we discovered 6220 different APs and 3305 different network identifiers (ESSID). 29% of these belong to CNs, FreeWiFi being the most frequently found ESSID (Fig. 1(b)). Considering security issues at MAC level, in Fig. 1(c) we see that WPA-based authentication is the most frequently implemented with 40%, followed by WEP (34%) and finally a significant 26% of APs without authentication. This is mainly due to the presence of CNs, since its authentication is based on a captive portal. However, data encryption is not provided at the wireless link.

Fig. 1(d) shows the channel allocation and more than 78.21% of the APs are deployed in the (recommended) non-overlapping channels 1, 6 and 11. The percentage of usage of the rest of the channels is always between 1% and 5.9%. This result perfectly matches the non-overlapping channel occupancy calculated by Gerla et al. [START_REF] Giordano | Corner: a realistic urban propagation model for vanet[END_REF] for urban wireless deployments in California (USA), in which they found 77.98%, even though additional combinations of nonoverlapping channels could be used in France since two additional channels are available (see section I-A).

With regard to the link quality, Fig. 1(e) shows the distribution of the received power (in dBm). The value of the power was obtained by extracting the RSSI field from the Beacons and Probe Responses from APs. The all-APs curve represents the distribution for all discovered APs, and we also present the power distribution for the most relevant CNs. Within the limits of the operative power range of 802.11 (-80dBm) we can find more than 75% of the APs.

Another useful metric is related to the maximum distance a user can use an AP. Depending on the speed of the user, this can approximately determine how long an AP is available. This metric is computed by finding the longest geographical distance between two Probe Responses received from the same AP. Fig. 1(f) illustrates the distribution of this metric, showing an average distance of 32.3m. Regarding this last metric, results presented by Bychkovsky et al. [START_REF] Bychkovsky | A measurement study of vehicular internet access using in situ wi-fi networks[END_REF] suggest an AP coverage of 96m in an 802.11b environment in Boston (USA). The difference between this value and our estimation (32.3m) could be related to the transmission power of the devices, which was 200mW in [START_REF] Bychkovsky | A measurement study of vehicular internet access using in situ wi-fi networks[END_REF] against 10mW (without the gain from the external antenna) in our experiment. 2) Interferences: In an European 802.11 deployment, up to 13 channels are available in the 2.4GHz band. Following the discussion given in I-A, only three channels can be simultaneously used without interferences. The most recommended channels are 1, 6 and 11 [START_REF] Fuxjager | The myth of non-overlapping channels: interference measurements in ieee 802.11[END_REF], but other combinations could be used such as 2, 7 and 12. Sources of interference can be generated by several APs sharing the same physical channel or being separated by less than 22 MHz. In order to study this issue, we propose to evaluate the distribution of the number of APs per scan (Fig. 2(a)), the distribution of the number of APs on the same channel per scan (Fig. 2(c)) and the inter-channel separation between APs per scan (Fig. 2(b)). Fig. 2(a) shows that 22 APs are discovered in average during a scan. Moreover, the most frequent value is 32 APs per scan, showing an overcrowded wireless environment. Complementing Fig. 2(a), we propose two interference metrics. A first metric named intra-channel interference represents the distribution of the number of APs that are being deployed on the same channel per scan. Fig. 2(c) shows that 7 APs are deployed in average on the same channel, and we observed up to 41 APs operating on the same channel. Secondly, we measure the minimal distance in number of channels from an AP to another operating in a different channel to observe how the APs are spread in the channels sequence. We name inter-channel interference (see Fig. 2(b)) the separation between active neighboring channels (those having at least one deployed AP). For almost 20% of the cases, APs are deployed with an inter-channel distance lower or equal to 4 (which causes interferences). For the rest of the cases, APs' deployment follows a nonoverlapping pattern, since a distance greater or equal to 5 channels (i.e. 25 MHz) is observed. The peak observed for a separation of 10 channels could be generated by deployments in which channel 6 is not used, and only channels 1 and 11 are occupied by at least one AP. Similarly, the peak observed at a separation of 5 channels stands for the cases where channels 1 and 6 are used, or 6 and 11. These results are coherent with those in Fig. 1(d) where we observed that channels 1, 6 and 11 were the most used ones. The analysis of this set of results clearly shows that the 802.11 environment is overcrowded, and while APs are generally deployed on the non-overlapping channels 1,6 and 11, there is a high number of APs deployed on the same channel.

3) Network Potential: Large 802.11 deployments come up as a key point in 4G heterogeneous environments, because 802.11 may serve as an alternative technology to 3G in some areas. A CN can easily provide Internet access to a wide number of users in urban areas at a low price. In our study, we identified that FreeWiFi, FreePhonie, Neuf WiFi and SFR WiFi Public are the most relevant CNs around the city. The similarity of the results from FreeWiFi and FreePhonie (Free) and Neuf WiFi and SFR WiFi Public (Neuf/SFR) respectively may be explained by the fact that both pairs of ESSIDs are advertised by the same physical AP. They only represent two different services, namely Internet access and voice calls. For all these identifiers, we analyzed two metrics, as shown in Table I. The Global Coverage is the percentage of locations where the network was found to be active. The Longest Path metric aims to estimate the distance a mobile user remains connected to at least one AP from the given CN while moving. Regarding the global coverage, we can appreciate that Free leads the community deployments with 67% of the path covered by at least one AP. A user having Free identifiers may find an available AP with higher probability than the second operator, Neuf/SFR. An important consideration is that the growth of such CNs is directly related to the growth of the broadband access market. This means that the efforts to deploy this kind of networks are not related to a single entity (government or operator) but to the whole population, making deployments more feasible.

Concerning user mobility, we found that the FreeWiFi network has the greatest potential. A mobile user could have uninterrupted access to at least one FreeWiFi AP along 292.12m. If we consider a user having access to both Free and Neuf/SFR platform, he could move along 451.82m (as a maximum) without interrupting the connection. However, for now mobility is not supported between APs, which means that a mobile user still has to re-connect to each AP and thus interrupting his/her session. We computed the presence of CNs along the path in Fig. 3. We can observe than Free and Neuf/SFR deployments are quite complementary. The lowest stripe from Fig. 3 illustrates the case of all CNs being considered together, showing a lower number of uncovered zones.

IV. CONCLUSIONS AND PERSPECTIVES

We presented a first set of results to evaluate the performance and the usability of 802.11 networks deployed in Rennes, France. We proposed a number of metrics to measure how many APs are reachable, what is the level of interference, how the channels are used, and how long a user remains connected to an AP. These metrics describe what are the conditions that a user faces while attempting to connect to an AP.

We found that the 802.11 environment is overcrowded (6220 APs over an 8km path), where a large number of APs (78%) are operating on the well-known non-overlapping channels (1, 6 and 11). However, the number of APs per scan is so significant (32 APs in average) that many APs are sharing the same channel leading to poor quality. These findings are important for the development of optimized channels scanning algorithms (for mobile users), by giving priority to those channels. When concerning the link quality, not all the discovered APs provide a power level that guarantees a stable communication. This could be due to regulations on transmission power limits and the fact that APs are mainly deployed indoor.

Focusing on CNs, we can state that this new paradigm is greatly present around the city, giving users the possibility to rapidly access the Internet at a low cost and to obtain reasonable performance. We observed that the two most important operators are quite complementary, giving the possibility to a user to remain connected up to 450m (assuming the user roams between APs). In terms of potential of these networks, we can consider that its growth may follow the residential broadband access market progress, and so the coverage of these networks should increase as well. As future work, we aim to develop a framework not only to perform discovery of the wireless environment, but also to evaluate the performance at the application level and study mobility using different CNs.

  Fig. 1. General Results

  Fig. 2. Channels Occupancy

Fig. 3 .

 3 Fig. 3. Presence of APs along the path

978-1-61284-663-7/11/$26.00 ©2011 IEEE ICOIN 2011

MIT Roofnet: http://pdos.csail.mit.edu/roofnet/doku.php

Urbana network: http://cuwireless.net/

(Madison MadMesh: http://madcitybroadband.com/

(Google WiFi network: http://WiFi.google.com/


German Castignani
email: german@castignani.com.ar

Andrés Arcia

Nicolas Montavont

A study of the discovery process in 802.11 networks

Today wireless communications are a synonym of mobility and resource sharing. These characteristics, proper of both infrastructure and ad-hoc networks, heavily relies on a general resource discovery process. The discovery process, being an unavoidable procedure, has to be fast and reliable to mitigate the effect of network disruptions. In this article, by means of simulations and a real testbed, our contribution is twofold. First we assess the discovery process focusing on the values of IEEE 802.11 timers: MinChannelTime and MaxChannelTime. Then, varying these timers, we propose and evaluate an adaptive discovery strategy from which we obtain notable improvements over a fixed timers strategy.

I. Introduction

Nowadays, 802.11 wireless networks appear as the most popular access network since the demand for mobile accesses continuously increases. Moreover, modern portable computing devices such as PDAs and Cell Phones, which represent an important quantity of the Internet devices, embed WiFi chipsets. In this context, users can run applications and services over the Internet by accessing different networks depending on his/her location. The access to an 802.11 network can be achieved in two different modes, depending on the nature of the point of attachment. A mobile station (MS) can form spontaneous networks (ad-hoc mode) or it can get connected to an access point (AP) which is directly connected to a backbone (infrastructure mode). In both modes, mobility appears as the key benefit of 802.11, providing the users the possibility to move inside and between cells.

When moving out of the range of its current point of attachment (i.e., between cells), an MS should quickly discover and attach to a new point of attachment to reconnect to the network. This process is known as a handover. In infrastructure mode, it consists in finding a new AP. In ad-hoc mode, an MS may additionally need to discover new services, and eventually update routing states if multi-hops protocols are used. The wide usage of 802.11 networks implies that an MS may deal with a wide variety of deployment scenarios. These scenarios consist of heterogeneous wireless devices deployments (including APs), managed by several ISP and characterized by overlapping frequencies, different traffic load and high interference. These conditions cannot be anticipated by the mov-ing MS and so the need for an appropriate scanning algorithm.

Independently of the access mode (ad-hoc or infrastructure), the scanning phase can be regarded as critical. When an MS starts up or moves around, it needs to discover its environment: radio frequencies, neighbor point of attachment (MS or AP), and available services. This process must be reliable, efficient and fast. In this article, we present experiments to assess the discovery process in 802.11 networks, and more specifically, we are interested in studying how long an MS has to wait before receiving a response from a point of attachment. We believe that these experiments and conclusions can be applied to other technologies, or extended to other discovery systems not only for 802.11 (e.g., Kozat and Tassiulas [START_REF] Kozat | Network Layer Support for Service Discovery in Mobile Ad Hoc Networks[END_REF]).

Within the 802.11 scanning phase, an MS uses management frames called Probe Request to actively scan a channel and discover point of attachments operating on it. Nevertheless, in the infrastructure mode, an MS should start a discovery process each time it switches AP -known as Layer 2 handover -to join a new Basic Service Set (BSS). In the ad-hoc mode, an MS will start a discovery process to form an Independent Basic Service Set (IBSS) with its direct neighbors. Each time an MS moves, it needs to discover again its environment and join new service sets.

I.A. The IEEE 802.11 Discovery Process

As shown in Fig. 1, an MS probes channels by broadcasting Probe Requests and waiting for Probe Responses from available points of attachment. The IEEE 802.11 standard [START_REF]IEEE Standard for Information technology -Telecommunications and information exchange between systems -Local and metropolitan area networks -Specific requirements -Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF] defines two timers, Once a Probe Request is sent, MinCT defines the maximum time to wait for the first Probe Response. If a Probe Response is not received within MinCT (i.e., MinCT expires), the MS considers that the channel is empty, and starts the process in a different channel. Otherwise, if a Probe Response is received within MinCT, then the MS waits up to MaxCT for further Probe Responses that may be sent by other point of attachment operating within the same channel.

We have chosen to characterize the discovery process by two salient metrics: the full scanning failure and the full scanning latency. A full scanning failure is defined as the impossibility to discover any of the MSs or APs within all the available scanned channels. On the other hand, the full scanning latency corresponds to the time spent during the discovery process, i.e., to scan all available channels one after the other in whatever order.

In Eq. ( 1), we represent the full scanning latency (L) as a function of MinCT and MaxCT, and the probability of finding activity on a particular channel (c), referred as P (c). Then, N ch refers to the total number of available channels 1 :

L = N ch c=1 (1-P (c))•M inCT +P (c)•(M inCT +M axCT ) (1)
Since the arrival to the cell, an MS cannot be directly attached to any BSS or IBSS (i.e., the MS can not exchange data frames during the discovery process), making the discovery process mandatory. As explained in [START_REF] Gonzalez | HAMS: Layer 2 Accurate Measurement Strategy in WLANs 802[END_REF] and [START_REF] Mishra | An Empirical Analysis of the IEEE 802.11 MAC Layer Handoff Process[END_REF], concrete measurements of the handover latency in infrastructure mode demonstrates that the discovery phase takes about 90% for 1 Recall that this number depends on regional regulations the total handover latency. Moreover, authors in [START_REF] Mishra | An Empirical Analysis of the IEEE 802.11 MAC Layer Handoff Process[END_REF] show the different approaches among manufacturers to implement different discovery techniques and settings for MinCT and MaxCT, and how variable is the AP's response time (i.e., from few milliseconds up to 40ms).

In this article, we propose a set of experiments both by simulation and a real testbed, on the discovery process and focus on evaluating the impact of MinCT and MaxCT on the full scanning latency and the full scanning failure. In particular, we propose two strategies to set the values for MinCT and MaxCT. The first one bases on using fixed timers while the second one is to dynamically adapt MinCT and MaxCT from one channel to another during the scanning process. We have observed that fixed timers strategies are implemented in existent open-source 802.11 drivers, like MadWiFi2 and ath5k 3 .

The purpose of adapting the values of MinCT and MaxCT is not to determine the best values that fit a particular deployment, since we assume an unknown and unpredictable deployment and so the topology on every discovery process is rather unknown. Thus we aim at finding a trade-off between a minimal full scanning latency and a minimal full scanning failure. Recall that when decreasing the latency we increase the failure and vice-versa. The principle is thus to lower MinCT and MaxCT values when a point of attachment has already been discovered, and on the opposite, to use higher values when no point of attachment has been found. Moreover we will see that the sequence in which the channels are scanned have an impact when MinCT and MaxCT are adaptable.

The remaining of the article is organized as follows.

In Section II we survey the related work and present a taxonomy of the different techniques to improve the discovery process. In Section III we introduce two different strategies to set the timers during a scanning process. In Section IV we evaluate the performance of both strategies by simulation and a real testbed. Finally, in Section V we conclude the article.

II. Related Work

Most of the related work done for the 802.11 discovery process concerns the optimization of the Layer 2 handover, when an MS roams from one AP to another. In this section, we present the main strategies to reduce the full scanning latency.

II.A. Selective Scanning and Caching

One simple way to reduce the full scanning latency is to only scan a subset of channels, instead of probing each of them. In [START_REF] Shin | Reducing MAC Layer Handoff Latency in IEEE 802.11 Wireless LANs[END_REF], authors suggest the utilization of a channel binary mask to decide which channels to scan. This mask is updated after each handover. During the first handover, the mask is initialized with "1" for all channels, meaning that all channels are scanned. During a handover, the MS builds a new mask for the next handover, containing a value of "1" for the non overlapping channels (1, 6 and 11) and for those where a probe response was received. The mask contains "0" for channels that may not have activity (i.e., no Probe Response was received on the previous scanning). Upon the next handover, the channel on which the MS's AP was operating is turned to "0" in the mask, since authors consider that a neighboring AP operating on the same channel is not probable. This consideration contradicts the statement presented in [START_REF] Mhatre | Using Smart Triggers for Improved User Performance in 802.11 Wireless Networks[END_REF], where a neighboring AP on the same channel is considered highly probable. Then, channels marked as "1" are scanned, if no probe responses are received on those channels, the mask values are logically inverted and the MS continues probing these new channels. If the scanning process is still unsuccessful, a standard full scanning process is executed all over again. In addition, the authors propose to use a Caching method where neighbor APs are stored during MS operation. This table will allow the MS to directly probe a neighbor AP when it returns to an AP that has already been visited. Selective Scanning reduces the full scanning latency in an average of 43%. Applying the Caching mechanism, the handover latency is reduced to reauthentication and reassociation delays, reaching a 97% of reduction. Regardless of these results, since they do not require modifications on the AP side, it has to be counted that the neighbor APs cache has to be carefully maintained. Erroneous information in the cache such as unavailable APs, leads to full scanning failure. On the other hand, as both the cache and the binary mask are incrementally built, the first handover will apply the standard technique, resulting in higher latencies.

II.B. Reducing the time spent on each channel

One of the paradigms within the handover optimization has been focusing on reducing the value of the scanning timers.

= 50μs + (31slot • 20 μs slot ) = 670μs ∼ = 1T U (2)
Authors analyse the probe response delay depending on traffic load and the number of stations on each channel. They conclude that MaxCT is not bounded as long as the number of stations can increase. They recommend to set MaxCT to avoid responses from overloaded APs. They fixed a value of 10T U based on the hypothesis that ten MS associated with the same AP is an adequate number in order to achieve good throughput. However, the fact of providing fixed timers does not guarantee a successful discovery process. Authors introduced several considerations regarding the number of stations operating on each channel and data traffic conditions. These fixed values could effectively work for some scenarios, but in other cases unnecessary delays may be introduced or even worse, the scanning may fail to find any candidate AP, resulting in a link layer disconnection.

II.C. Interleaved scanning sub-phases

The 802.11 standard active scanning algorithm implicitly defines that the handover process should be performed after detecting weak signal from the current AP. The Smooth Handover [START_REF] Liao | Practical Schemes for Smooth MAC Layer Handoff in 802.11 Wireless Networks[END_REF] and the Periodic Scanning [START_REF] Montavont | Enhanced schemes for L2 handover in IEEE 802.11 networks and their evaluations[END_REF] methods are based on splitting the discovery phase into multiple sub-phases. The objective of this division is to allow an MS to alternate between data packet exchange and the scanning process. An MS periodically performs anticipated short discovery phases so it can look for candidate APs before reaching a disconnection. During the anticipated scanning, the station builds a list of target APs maintaining some basic information (MAC address, operating channel and Service Set Identifier (SSID)). Authors of [START_REF] Liao | Practical Schemes for Smooth MAC Layer Handoff in 802.11 Wireless Networks[END_REF] propose to scan a group of channels in each sub-phase, while in [START_REF] Montavont | Enhanced schemes for L2 handover in IEEE 802.11 networks and their evaluations[END_REF] only one channel is scanned during MinCT. Each sub-phase is triggered depending on the Received Signal Strength Indicator (RSSI).

Authors of [START_REF] Liao | Practical Schemes for Smooth MAC Layer Handoff in 802.11 Wireless Networks[END_REF] evaluated the performance of the Smooth Handover in a real testbed and showed that the data packet loss is strongly reduced. In [START_REF] Montavont | Enhanced schemes for L2 handover in IEEE 802.11 networks and their evaluations[END_REF], network simulations on six different scenarios are proposed. The handover delay and the packet loss rate are reduced only in some scenarios, depending on the characteristics of the APs deployment. In other scenarios, the station continuously probes and switches between channels which contributes to a higher battery consumption, and some additional delays.

In addition, these techniques require that there must be enough overlapping area between neighboring APs, limiting the deployment scenarios where these techniques may be applied. If only small overlapping areas exist, there will not be enough time to distribute the scanning process during the MS movement. The need for overlapping area between neighboring APs strongly constrains the network deployment and requires to deploy more APs in a given area.

II.D. Synchronized passive scanning

Unlike common handover optimizations focusing on active scanning, the SyncScan [START_REF] Ramani | SyncScan: practical fast handoff for 802.11 infrastructure networks[END_REF] method is based on the standard passive scanning approach where an MS simply waits for periodic beacons on the current channel. The passive scanning latency is related to the number of channels and the BeaconPeriod timer, commonly set to 100ms. Then, passive scanning latencies usually exceed one second. SyncScan synchronizes the MS at the same time the APs beacons are received on each channel, so the MS switches to a channel when a beacon is about to arrive. Using Sync-Scan the MS has up-to-date information about APs. Since the MS does not probe the channels, the handover latency should be reduced to authentication and association delay.

This new approach may eliminate the scanning delay, but some difficulties should be analyzed. The fact that the MS must switch to a channel when a beacon is about to arrive, adds a complex time synchronization management between MSs and all deployed APs. Clock accuracy becomes critical in this approach because even a minor deviation in time synchronization becomes non-negligible preventing an MS from discovering neighbor APs. Authors propose the usage of Network Time Protocol (NTP) that maintains time within 10ms accuracy over the Internet, achieving precisions of 200μs or better in local area networks under ideal conditions. Under these considerations, we believe that SyncScan implementation is limited to very homogeneous deployments (e.g. enterprise or campus deployments), where a central administrator can manage the channel allocation and synchronization between APs for the beacon sending. Synchronizing APs in a fully heterogeneous environment (e.g. hotspots or community deployments from multiple operators around a city) for the implementation of SyncScan seems impractical. In all the cases, the SyncScan procedure is performed regularly, producing several unavailable periods for data packets transmissions, so packet loss may be observed while exploring other channels.

III. Timers Setting Strategies

Although optimization techniques have been designed for the discovery process, there is still a lack of work in the determination of the most adequate values defining the time to wait on each channel. For every fast handover approach, an MS still needs to scan channels one after the other to discover APs. In smooth handover [START_REF] Liao | Practical Schemes for Smooth MAC Layer Handoff in 802.11 Wireless Networks[END_REF] or in periodic scanning [START_REF] Montavont | Enhanced schemes for L2 handover in IEEE 802.11 networks and their evaluations[END_REF], the discovery phase is split into several independent subphases that are separated by certain time period (during which the MS may still exchange data packets). During each of these sub-phases, the MS scans the channels one by one, just as in a continuous scanning phase. In the selective scanning [START_REF] Shin | Reducing MAC Layer Handoff Latency in IEEE 802.11 Wireless LANs[END_REF], the order in which channels are scanned is determined by a binary mask built from previous scanning phases. In all cases, for each channel, APs also need to be probed and thus the time to spend on each channel needs to be defined. In any other method, such as the synchronized passive scanning [START_REF] Ramani | SyncScan: practical fast handoff for 802.11 infrastructure networks[END_REF], there is still a probability that no AP is found through the optimized method. In fact, the optimization proposed in [START_REF] Ramani | SyncScan: practical fast handoff for 802.11 infrastructure networks[END_REF] cannot be applied in an opportunistic scenario, since synchronisation between possible neighbours is not achievable. In case the optimized method fails, we need a fall-back mechanism to discover AP, i.e., we need to scan the channels one by one because all other alternatives failed.

To determine the time needed for an MS to wait for a Probe Response on each channel, we study the impact of MinCT and MaxCT on the discovery process, introduced in Section I.A. We define in this section two strategies to set the values for these timers. The first method is the most intuitive and consists in scanning channels one after the other with fixed values for both MinCT and MaxCT. The other method, referred as adaptive timers scanning, consists in varying the values of MinCT and MaxCT channel by channel, according to the AP(s) that was (were) already found. By adjusting these values, we expect to provide a better success rate for the AP discovery (i.e., low full scanning failure) than using a fixed timers strategy, while maintaining a low full scanning latency.

III.A. Fixed Timers Scanning

This first strategy consists in fixing pre-defined values for both MinCT and MaxCT, which determine the time an MS will wait on a channel for AP's responses. Low values will provide low full scanning latency, but will increase the risk of missing an AP because the MS is not waiting long enough to get a response. While theoretically an MS should expect a response before 1ms (see Section II.B), experimental results presented in Section IV.C suggest that the response from an AP varies from 1ms to 40ms. Considering the empirical analysis proposed by Mishra et al. [START_REF] Mishra | An Empirical Analysis of the IEEE 802.11 MAC Layer Handoff Process[END_REF], and our experience, we decided to evaluate the following timers: < 10ms, 20ms > and < 25ms, 50ms > for < M inCT, M axCT >. These sets of timers try to represent two limit cases for the full scanning latency and full scanning failure trade-off. The first set prioritizes the full scanning latency while the second try to avoid high levels of full scanning failure. In both sets, we fix the double of the value of MinCT for its correspondent MaxCT. This ratio was not varied during simulations and experimentations. Different values for MaxCT for the same MinCT may increase the number of discovery APs in some scenarios, but it does not affect the trade-off under study.

As stated in Section I, fixed-timers strategies are commonly implemented in open-source drivers. In the case of MadWiFi, two timers are implemented: mindwell and maxdwell. Once a Probe Request is sent on each channel, the MS waits until maxdwell (200ms) for a Probe Response or Beacon. If at least one Probe Response or Beacon is received, and if mindwell (20ms) elapsed, the station immediately switches to the next channel in the sequence. Then, the full scanning latency could vary between 260ms and 2.6s (without considering the channel switching delay), depending on the number of channels with APs deployed. In the case of ath5k, an MS first waits for 100ms on the current channel and then it sequentially scans using two timers. It first waits for the Probe Delay timer (28ms) and then it sends a Probe Request and waits for Channel Time (28ms) for the Probe Responses. In this case, the full scanning latency is close to one second. Both implementations differ from the 802.11 standard (see Section I.A). Moreover, authors of [START_REF] Mishra | An Empirical Analysis of the IEEE 802.11 MAC Layer Handoff Process[END_REF] present an analysis of the scanning phase for different 802.11 network interface cards. A very large variation of the full scanning latency is observed depending on the AP and MS technology. They found that fixed timers strategies differ from one MS to another, since they implement alternatively one or two timers, using different values. The maximum average variation found in this works was between 58.74ms and 394.27ms for the same AP configuration using different cards in the MS. As we can see, these handover latencies are too high for real time applications.

III.B. Adaptive Timers Scanning

The other possible strategy is to adapt, or dynamically change the values for MinCT and MaxCT during the scanning process based on the discovered resource. This new approach allows an MS to spend less time on channels once candidate APs have been already found whereas the fixed timers scanning would spend the same time on each channel. The main goal is to reduce the timers channel by channel while APs are discovered, because the impact of missing an AP will be less important as if no AP were found. On the contrary, timers may be increased if no AP has been found, in order to increase the chances of finding an AP on the next channel(s). In this article, we do not investigate a proper adaptation function, however we rather focus on the understanding of the discovery process using either fixed timers or variable timers. We present the adaptation function used in our experiment in Section IV, but other adaptation function could be implemented.

The selection of the sequence of channels to scan becomes important if we consider timers adaptation, because timers are adapted according to the activity on each channel. The sooner an AP is found, the faster the timers will be decreased, and thus, it is important to scan first channels on which AP(s) may be operating. In 802.11 networks, only three non-overlapping channels exist. As stated in [START_REF][END_REF] and [START_REF]Channel Overlap Calculations for 802.11b Networks[END_REF], a proper deployment typically uses only these channels. Moreover, Eriksson, et al. [START_REF] Eriksson | Cabernet: vehicular content delivery using WiFi[END_REF] and Gerla et al. [START_REF] Frank | CORNER: a realistic urban propagation model for VANET[END_REF] presented two different works in which the channel occupancy distribution is calculated in a real environment. In [START_REF] Eriksson | Cabernet: vehicular content delivery using WiFi[END_REF], the authors propose an optimal scanning strategy that gives more priority to channels 1, 6 and 11, since they found that 83% of APs are assigned to those channels. On the other hand, experimenting over a different deployment, the authors of [START_REF] Frank | CORNER: a realistic urban propagation model for VANET[END_REF] states that 77,98% of APs are deployed in the non-overlapping channels. Our own experiments on a city-wide WiFi deployment results in 78,21% of occupancy in nonoverlapped APs. Then, it could be assumed that prioritizing those channels, as stated in [START_REF] Shin | Reducing MAC Layer Handoff Latency in IEEE 802.11 Wireless LANs[END_REF] and [START_REF] Eriksson | Cabernet: vehicular content delivery using WiFi[END_REF], candidate APs may be discovered sooner. We suggest to randomize the channel switching sequence in two different subsequences. The first subsequence randomly switches between the non-overlapping channels. Then, the rest of the channels are also randomly considered. If an AP with relative good signal level is discovered in channels 1, 6 and/or 11, the adaptive system will set lower timers for the next channels to scan. In all cases, timers are adapted between pre-established bounds (defined by experimentation on Section IV.C.2). This strategy differs from that proposed in [START_REF] Eriksson | Cabernet: vehicular content delivery using WiFi[END_REF], where channels are scanned at a rate proportional to the channel occupancy, with the final goal of minimizing the time to find a channel with an AP. In our case, we consider scanning all the channels in the sequence, but giving more priority to the nonoverlapping channels, i.e., increasing the probability that a high timer will be used on those channels.

IV. Performance Evaluation

IV.A. Strategies Implementation

To evaluate both timers setting strategies, we have conducted simulations and experimentations under a real testbed. The simulation aims to evaluate the scanning process in different AP deployments, considering different time an AP employs to respond to a request. The main goal of the simulations is to roughly show the expected behavior of the different algorithms in terms of the full scanning latency vs full scanning failure trade-off, giving a global view of the problematic. Since the implementation of the simulator is mainly based on computing the expected full scanning latency and full scanning failure for different probe responses delay distribution, we decided not to implement or modify an existent network simulator, but to develop the algorithms in a simple light weight simulator in the language C. Within these algorithms, a probe response delay computation and an exponential back-off for retransmissions have been implemented.

The testbed is based on the deployment of 802.11 MSs and APs, allocated in different channels and under different traffic conditions, as detailed in Section IV.C.1. The scenarios experimented in this testbed are a subset of the simulation space in order to focus on some (limited) representative scenarios. These experiments also show that an adaptive strategy can be implemented in an open-source driver and allow measuring the handover performance with real devices.

On the one hand, the fixed timers strategy is implemented as described in the previous section with the timers < 10ms, 20ms > and < 25ms, 50ms >, which give a good overview of the performance of using fixed timers. On the other hand, for the adaptive strategy, we need to define how the timers evolve from one channel to another. We decided to increase the timers when no AP is found, and to decrease the timers when an AP is found. The decrease of the timers are proportional to the quality of the discovered AP, which is computed from the signal level and the number of APs sharing the same channel. Note that the definition of a proper metric for AP quality is out of the scope of this paper, so other algorithms might be used. In the following paragraph, we give the details of our implementation.

As illustrated in Fig. 2, the MS starts scanning using half the maximum bounds for both timers. We considered this strategy as an approximation to balance the trade-off between the full scanning latency and the full scanning failure. Observe that, if an MS started scanning using the maximum bounds of the timers, we would end up with a high full scanning latency. Otherwise, if an MS started scanning with the lower bounds of the timers, we would fall in a high full scanning failure. For a channel on which at least one AP has been discovered, the MS calculates the greatest quality of all discovered APs on that channel (Q) and the number of APs that have replied on that channel (N ). N is obtained by simply counting the number of probe responses received from different APs. Regarding Q, the Received Signal Strength Indicator (RSSI) parameter, included on each received probe response, is considered. Both Q and N are combined in order to establish the criteria that will be used to rank discovered APs, and decide whether the timers to be used on the next channel (T n+1 ) can be reduced or increased. In Fig. 2, T n+1 represents the tuple < M inCT, M axCT >, since both timers are simultaneously adapted. Then, T n+1 is calculated considering a decision making parameter (R) calculated for each channel by using Q and N .

R = Q N (3)
This simple relation allows adapting timers differently, depending on the environment that have been discovered on the previous channels. Two different APs having the same signal strength and operating in separated channels may be considered in a different way. Populated channels will not be weighted as well as those with a lower number of APs. This choice comes from the observation that in a wireless environment, we mainly consider weak signal and collisions as the issues limiting link performance. A packet transmitted on an 802.11 link may be lost because of a weak signal or a collision, but discerning the real cause is quite difficult. We focus on results obtained in [START_REF] Rayanchu | Diagnosing Wireless Packet Losses in 802.11: Separating Collision from Weak Signal[END_REF], in which a set of testbeds were implemented so as to independently analyze the effect of a weak signal (due to a low RSSI between the MS and the AP) and collision (due to several MSs and APs operating on the same channel). Authors have empirically showed that for the same packet-loss rate, the BER (Bit Error Rate) in a weak signal scenario (low RSSI, without collisions) was less than 12% against a 50% for a collision scenario (without weak signal effects). We can infer that the effect of multiple APs sharing the channel (producing collisions) is less desirable than a low RSSI scenario.

Then the MS takes into account the value of R calculated on the channel and reduces both MinCT and MaxCT using the same proportional factor (f (R)). f (R) is implemented in away that for higher values of R, timers are more strongly reduced. In contrast, as shown in Fig. 2, if no AP is discovered, no R is calculated on the correspondent channel and then timers are increased to half the difference between the last successful timers (those from whom at least one response was received from an AP) and the timers used on the previous channel (those from whom no response was received from any AP). Increasing timers using this approach avoids overshooting, since timers are smoothly augmented. Recall that the purpose of this article is not to provide the best adaptive strategy, but evaluate the impact of timers on the full scanning latency and failure. Other adaptive strategy could be proposed and additional or alternative parameters could be taken into account to estimate the quality of the discovered APs.

IV.B. Simulation results

We describe an evaluation done by simulation of both fixed and adaptive timers strategies in 25 different scenarios. For each scenario, there is either 0 or at maximum 1 AP per channel. This is to simplify the simulation, since we are interested only if the channel has activity or not. In all cases, the quality (RSSI) of each AP is randomly generated. The 25 scenarios are the following: • An ideal scenario where 13 APs are deployed one by one in the 13 available channels.

• 12 pessimistic scenarios, where APs are deployed in the last scanned channels. The first pessimistic scenario corresponds to the case where all channels are empty (no AP), except the last scanned channel where one AP is operating. Then, more APs are deployed on the last scanned channels, up to the case where only the first scanned channel in the sequence has no AP.

We identified both optimistic and pessimistic channel sequences since the adaptive strategy depends on when APs are discovered in the sequence of scanned channels. In order to evaluate the impact of different probe response delays, for each of these 25 scenarios we performed 10 different simulations. We consider P from 10% to 100% of probes responses received before 10ms, with a step of 10 points. Then, we generate uniform random probe response delays between 0 and 10ms with probability P and values greater than 10ms with probability 1 -P . We chose a uniform random law because Mishra et al. [START_REF] Mishra | An Empirical Analysis of the IEEE 802.11 MAC Layer Handoff Process[END_REF] suggests that the time of response from an AP follows a uniform law. For each simulation, a hundred thousand scanning experiences is performed in order to obtain For space reasons, we only present the results for 4, 8 and 12 deployed APs for the optimistic and pessimistic channel sequences in Fig. 3 and4. These figures show the full scanning latency on the left ordinate and the full scanning failure percentage on the right ordinate according to the probability of receiving a Probe Response before a given percentage in abscissa. Focusing first on Fig. 3 (optimistic scenarios), we can appreciate that the fixed timers strategy (using both sets of timers) tends to increase the full scanning latency (crosses and minus signs with error bars) when the number of probe responses received before 10ms increases. This is due to the effect of MaxCT, since if activity is detected on more channels the MS waits more time on each one.

On the other hand, the adaptive strategy tends to decrease the full scanning latency (stars with error bars) when the number of probe responses received before 10ms increases. This occurs because the adaptive strategy reduces the timers for the following channels to scan if activity is detected on the current scanned channel. Then if more activity is detected (due to more probe responses received on different channels) the adaptive strategy is able to reduce even more the timers. We can appreciate that there is an intersection between the full scanning latency curves for the fixed timers strategy using < 10ms, 20ms > and the adap-tive one in all the optimistic sequences scenarios. In the zone where full scanning latency of the adaptive strategy is higher than the fixed timers strategy (from the intersection point to the left), the fixed timers strategy performs worse in terms of full scanning failure, reaching very high levels in comparison to the adaptive strategy.

The full scanning failure for the fixed timers strategy using < 10ms, 20ms > is always high for a low percentage of probe responses received before 10ms (between 20% and 60% for the scenario with 4 APs). On the other hand, the adaptive strategy tends to maintain the full scanning failure as low as possible while reaching a full scanning latency comparable to the fixed timers strategy using < 10ms, 20ms >. We can also appreciate that the higher the number of deployed APs, the better full scanning latency for the adaptive strategy. For 12 APs, the adaptive strategy is always better (in terms of full scanning latency and failure than the fixed timers strategy.

As shown in Fig. 4 (pessimistic scenarios), the adaptive strategy performs worse in terms of full scanning latency than in the optimistic sequences scenarios because the timers are increased during the first scanned channels as no AP is discovered. However, it always maintains full scanning failure, under 1%. When 4 or 8 APs are deployed, the full scanning latency for the fixed timers strategy is always below the Figure 5: Testbed configuration adaptive one (for 4 APs, we even observe an important difference, where the fixed timers strategy requires 150ms in average, and the adaptive strategy requires 380ms). However, for a low percentage of Probe Response received before 10ms (less than 50%), the fixed timers strategy shows high full scanning failure (between 10% and 60%).

In summary, these simulations highlight that the discovery process is sensible to MinCT and MaxCT variations, the delay of the first response received from an AP, the APs deployments and the sequence in which the channels are scanned when MinCT and MaxCT are dynamically adapted. The literature often evaluates the efficiency of the discovery process by measuring the full scanning latency, but we can see that the discover process has also an important impact on the full scanning failure.

IV.C. Experimentation

IV.C.1. Testbed

A real testbed was implemented using up to thirteen APs from different providers and seven MSs for traffic generation (see Fig. 5). All the equipments in the testbed implemented 802,11b as physical layer. The MS uses an Atheros based D-LINK DWL-AG660. Both scanning strategies defined in Section III were implemented inside the MadWiFi driver (Version 0.9.4). Up to 64 different network scenarios were evaluated using eight different channel allocations, two different traffic conditions and four configurations for MinCT and MaxCT timers. Traffic was generated using D-ITG (Distributed Internet Traffic Generator), producing, in all configurations, a load of 8 Mbit/s between one sender and one receiver, which leads to overloaded cells. With regard to the channel allocation, the following configurations were evaluated.

• Configuration 1: Thirteen APs allocated one by one on channels 1 to 13 (one AP per channel). • Configuration 3: Three APs allocated one by one on channels 1-6 -11 (one AP per channel).

• Configuration 4: Twelve APs allocated four by four on channels 1-6-11 (4 APs per channel).

We have selected these configurations from all the possible cases since they are a valid representation of real deployments (as shown in [START_REF] Frank | CORNER: a realistic urban propagation model for VANET[END_REF] and [START_REF] Eriksson | Cabernet: vehicular content delivery using WiFi[END_REF]) and include favourable cases (for the discovery process) as well as challenging environments. In each of our experiments, we measure the discovery process over a hundred of full scanning processes, i.e., where all channels are scanned by the MS one by one.

IV.C.2. Bounds Determination for MinCT and MaxCT

In the first part of the experience, we aim at determining the bounds for MinCT and MaxCT for our adaptive strategy, i.e., the intervals in which MinCT and MaxCT will vary (defined as MinLower, Min-Upper, MaxLower and MaxUpper). For this purpose, we measure the delay of the first and further received probe responses on each channel for each particular AP deployment configuration, with and without traffic. Further probe responses are those that arrive after the first until the last probe response. We configured the MS with < 50ms, 200ms > for < M inCT, M axCT > in order to allocate enough time for the discovery of all operating APs (we were not interested in the full scanning latency, but in collecting the delay of each Probe Response). Table 1 gives the main conclusion for bounds determination. We have considered optimistic and pessimistic scenarios to define the upper and lower bounds. We also considered different percentages of received probe responses depending on the considered timer (e.g., MinUpper should represent a high value of probe response received because this bound will be used when no AP has been found). Fig. 6 shows a cumulative distribution function of the delays of the first probe response (in response to the broadcasts probe request) under a three non-overlapping channel configuration with and without traffic (configuration 3). This scenario is considered as an ideal AP configuration where interferences are minimized and thus help to determine the minimum limits for MinCT. If we observe the accumulated percentage function of first probe responses received over all the trials without traffic, we can see that 87% of the first Probe Responses were received before 6ms. Thus we decide to configure MinLower at 6ms as stated in Table 1. We can allow this relative low percentage -we could have taken 8ms where 96% of the Probe Responses were received -because we can afford to risk few unsuccessful discoveries in our adaptive strategy when this minimum value is used. Note that in the considered adaptive strategy, this minimum value is only used when APs have been discovered previously (See Section IV.A).

With the same aim and considering configuration 4, without traffic, MaxLower is set at 8ms where 50% of following Probe Responses from other APs were already received. We let MaxCT to be adapted to a low limit that covers less cases than MinCT (only a 50%), since the situation of not discovering more APs is not as risky as not discovering the first AP, in which the channel will be declared empty.

On the other hand, the upper bounds MinUpper and MaxUpper are determined using results obtained on the other scenarios (which are highly affected by interference) including traffic, like configuration 1 and 2. Cumulative functions are not illustrated due to space reasons, but we decided to pick 34ms for MinUpper (96% of further Probe Responses received in configuration 1) and 48ms for MaxUpper (87% of further Probe Responses received in configuration 2).

IV.C.3. General Results

During the second part of the experience, the adaptive strategy (ADA) was tested using bounds defined in Table 1 and the fixed timers strategy was evaluated considering three different sets of timers, < 10ms, 20ms >, < 25ms, 50ms > and finally < 50ms, 200ms > for MinCT and MaxCT respectively. Table 2 shows the results organized by scenario, where the full-discovery rate indicates in how many scanning processes all available AP were discovered. The failed scanning values describe the full scanning failure. Finally the average full scanning latency, including the standard deviation (σ) for the adaptive strategy, shows a controlled dispersion of the obtained latencies.

The main observation of these experiments confirm those of the simulations: the discovery process performance highly depends on the deployment scenarios and a high full scanning failure may be observed for the fixed timers strategy in some common network scenarios. The adaptive strategy only has 2% of full scanning failure in a single scenario (configuration 2 and loaded cells) and keeps a low full scanning latency. A detailed analysis of results of Table 2 is presented in the following paragraphs.

Impact of Traffic Load -Fig. 6 illustrates configuration 3, where probe responses are notably delayed when traffic is injected. While before 6ms the 87% of the probe responses are received in non loaded scenario, only the 43% is received when traffic is introduced. As shown in Table 2, in the case of configuration 3 with traffic, for several scannings a probe response is not received before 25ms, causing 20% of full scanning failure. Even using a MinCT equal to 50ms the full scanning failure arrives to 13%. The effect of traffic also produces a decrease in the average number of discovered APs in all evaluated scenarios. The adaptive strategy helps to reduce the effects of traffic, since no scanning process fails except in one scenario, where we observe only 2% of full scanning failure.

Theory vs Experimentation -Our experimental results do not match theoretical considerations and simulation presented in [START_REF] Velayos | Techniques to reduce the IEEE[END_REF]. In this work, a value of 1ms for MinCT is considered enough to wait for the first probe response before switching channel (see Section II.B). On the other hand, our experience shows that MinCT needs to be greater than 10ms to receive the 97% of first probe responses in an ideal three non-overlapping channel scenario without traffic. Moreover, as shown in Fig. 6 earliest first probe responses only appear after 2ms in the same configuration. Regarding MaxCT authors of [START_REF] Velayos | Techniques to reduce the IEEE[END_REF] state that it is unbounded and claims for a MaxCT equal to 10ms to be enough. We have shown during the bound determination that this value could not be sufficient for some scenarios. This gap between results proposed in [START_REF] Velayos | Techniques to reduce the IEEE[END_REF] and our experimentation (that are close to those presented in Mishra et al. [START_REF] Mishra | An Empirical Analysis of the IEEE 802.11 MAC Layer Handoff Process[END_REF]) are still under research. It may be explained by additional delays neglected in the literature, such as channel switching, congestion condition and queueing architecture for management frames.

Impact of the Number of APs -In configurations 3 and 4 where only non-overlapping channels were used, we observe less full scanning failure when there are four APs operating on the same channel (configuration 4). When there is a single AP per channel (configuration 3), a higher full scanning failure is attained in all evaluated timers for the fixed timers strategy. This may be due to the backoff timer of the MAC protocol, since there are more chances to pick a small random number when there are more active APs.

Impact of full scanning latency -Full scanning latency depends on the values of MinCT and MaxCT during the discovery process. In the adaptive strategy implemented by experimentation MinCT is initially set to MinUpper and it gradually decreases until MinLower. Fig. 7 shows full scanning latency values for all configurations with traffic including the full scanning failure (in percentage) for each case. Even if fixed timers strategy may give good results in some scenarios, the adaptive strategy provides lower or equivalent full scanning latency from 190ms to 434ms. The fixed timers strategy configured with < 10ms, 20ms > gives better latencies in AP configuration 2 around 150ms against 420ms for the adaptive strategy. But in this case full scanning failure reaches 29%, while the adaptive strategy only pro-

V. Conclusions

In this article, we have analyzed and evaluated the discovery process on 802.11 devices. This process has been extensively treated in the literature when it concerned the handover, i.e., when an MS needs to switch from one AP to another. Several optimizations were proposed in the literature that condition the full scanning latency and full scanning failure trade-off, highlighting the importance of the values of MinCT and MaxCT. In our first evaluation, we used a light weight C simulator to evaluate the influence of both timers for different probe response delays on the trade-off. We proposed two different strategies for the timers, one with fixed timers, and another one using adaptive timers. We observed that the adaptive strategy gives a better balance between the full scanning latency and the full scanning failure than the fixed timers strategy.

The full scanning latency does not overshoot and the full scanning failure is always maintained below low limits using the adaptive timers strategy (9% of full scanning failure on the optimistic 4AP scenario with only 10% of received probe responses before 10ms).

The fixed timers strategy shows high full scanning failure for long probe response delays. The second evaluation that we proposed in this article is an experimentation over a testbed with different APs and MSs. Results show that in almost all proposed scenarios, the adaptive strategy offers a better percentage of discovered APs, minimizes the number of full scanning failure (at maximum 2%), and keeps a low and controlled full scanning latency (between 190ms to 434ms). As we have shown, each particular scenario may have different optimal timer values to achieve an optimal trade-off between full scanning latency and full scanning failure. This demonstrates the importance and the efficiency of using an adaptive strategy, since the user faces heterogeneous scenarios and the discovery process must dynamically adapt to them.

As a future work we plan to further investigate different adaptive functions, scanning policies and candidate AP selection algorithms. A detailed analysis of the adaptive algorithm parameters is currently being performed in order to obtain a unique set of parameters that optimizes the algorithm. As it was proposed in several optimization techniques, a selective scanning approach not only reduces the full scanning latency, but it also conditions the success of the handover process. Thus, we could apply an optimized channel switching policy, and interrupt the scanning process before all channels have been scanned.

Figure 1 :

 1 Figure 1: Standard Active Scanning

Figure 2 :

 2 Figure 2: Adaptive Strategy Implementation

Figure 3 :Figure 4 :

 34 Figure 3: Simulation results for 4, 8 and 12 APs using the optimistic sequences

Figure 6 :

 6 Figure 6: First Probe Responses Delay

Figure 7 :

 7 Figure 7: Testbed Results

Table 1 :

 1 Bounds for MinCT and MaxCT

	Bound	Value	% of Probe	Conf. Traf.
			Resp. received
	MinLower	6 ms	87%	3	No
	MinUpper 34 ms	96%	1	Yes
	MaxLower	8 ms	50%	4	No
	MaxUpper 48 ms	87%	2	Yes

Table 2 :

 2 Comparative results

		Scenario			Full Discovery Rate			Full Scanning Failure			Full Scanning Latency
						(%)				(%)					(ms)
	AP	Channels	Number	Traffic		Fixed Timers		ADA		Fixed Timers		ADA		Fixed Timers			ADA
	conf.		of AP		10-20	25-50	50-200		10-20	25-50	50-200		10-20	25-50	50-200		σ
	1	1 to 13	13	No	65%	87%	93%	49%	0	0	0	0	275	708	2567	256	11%
	1	1 to 13	13	Yes	24%	69%	82%	40%	2%	0	0	0	317	636	2378	248	13%
	2	11	13	No	75%	92%	94%	96%	2%	2%	0	0	152	360	807	423	3%
	2	11	13	Yes	54%	88%	98%	83%	29%	3%	0	2%	159	363	814	434	5%
	3	1-6-11	3	No	92%	94%	99%	94%	0	0	0	0	117	414	1119	190	11%
	3	1-6-11	3	Yes	38%	51%	61%	81%	52%	20%	13%	0	227	403	1025	210	18%
	4	1-6-11	12	No	98%	98%	100%	95%	0	0	0	0	179	419	1121	390	3%
	4	1-6-11	12	Yes	39%	60%	87%	84%	13%	1%	0	0	239	450	1110	378	13%

http://madwifi-project.org/

http://wireless.kernel.org/

One Time Unit (TU) is equal to 1024μs


Peter Reinhardt
email: peter.reinhardt@upmc.fr

Julien Toulouse

Roland Assaraf

C J Umrigar

Philip E Hoggan

Quantum Monte Carlo facing the Hartree-Fock symmetry dilemma: The case of hydrogen rings

When using Hartree-Fock (HF) trial wave functions in quantum Monte Carlo calculations, one faces, in case of HF instabilities, the HF symmetry dilemma in choosing between the symmetryadapted solution of higher HF energy and symmetry-broken solutions of lower HF energies. In this work, we have examined the HF symmetry dilemma in hydrogen rings which present singlet instabilities for sufficiently large rings. We have found that the symmetry-adapted HF wave function gives a lower energy both in variational Monte Carlo and in fixed-node diffusion Monte Carlo. This indicates that the symmetry-adapted wave function has more accurate nodes than the symmetry-broken wave functions, and thus suggests that spatial symmetry is an important criterion for selecting good trial wave functions.

I. INTRODUCTION

It is well known that the symmetry-adapted solution of the nonlinear Hartree-Fock (HF) equations of an electronic system is sometimes unstable. An unstable solution corresponds to a saddle point of the energy as a function of the orbital parameters, and breaking of space and/or spin symmetries of the wave function then necessarily leads to one or several lower-energy HF solutions. The stability conditions of the HF equations were first formulated by Thouless [START_REF] Thouless | The Quantum Mechanics of Many Body Systems[END_REF], and the different instabilities were first categorized by Čižek and Paldus [START_REF] Čižek | [END_REF][3][4][5][6][7]. For closed-shell systems, one may encounter "singlet instabilities" when only spatial symmetry is broken, and "triplet (or nonsinglet) instabilities" when spin symmetry is also broken. There is thus a symmetry dilemma [8] in choosing between the symmetry-adapted wave function of higher HF energy and a symmetry-broken wave function of lower HF energy, in particular as a reference for a post-Hartree-Fock calculation.

A clear example is provided by closed-shell hydrogen rings H 4n+2 with equal bond lengths [9] (see, also, Ref. 10). The symmetry-adapted HF solution exhibits singlet instabilities for sufficiently large numbers of hydrogen atoms, and one can obtain symmetry-broken HF solutions with orbitals localizing on either the atoms or the bonds. However, both Møller-Plesset perturbation theory and linearized coupled cluster doubles theory (also called CEPA-0 or DMBPT-∞) give a lower total energy when starting from the symmetry-adapted solution than when starting from the symmetry-broken solutions, which casts doubts on the physical significance of the symmetry-broken solutions. Of course, the symmetry dilemma would be removed with a full configurationinteraction calculation which must give one unique so-lution, independent of the orbitals used.

Quantum Monte Carlo (QMC) approaches are alternatives to the traditional quantum chemistry methods [START_REF] Hammond | Monte Carlo Methods in Ab Initio Quantum Chemistry[END_REF][START_REF]Quantum Monte Carlo Methods in Physics and Chemistry[END_REF][13]. The two most commonly used variants are variational Monte Carlo (VMC) which simply evaluates the energy of a flexible trial wave function by stochastic sampling, and fixed-node diffusion Monte Carlo (DMC) which improves upon VMC by projecting the trial wave function onto the ground state subject to the condition that the nodes of the projected wave function are the same as those of the trial wave function. For large systems, the most common form of the trial wave function is a Jastrow factor multiplied by a fixed HF determinant (though for small systems one can do much better by replacing the HF determinant by a linear combination of optimized Slater determinants). If a system exhibits HF instabilities, then QMC also faces the symmetry dilemma in choosing between different HF wave functions. Indeed, different HF wave functions necessarily lead to different energies not only in VMC, but also in DMC since the nodes of these HF wave functions are generally different. This symmetry dilemma in DMC is only due to the fixed-node approximation, since without this approximation DMC would give one unique solution, independent of the trial wave function. Of course, for systems that are not very large, symmetry breaking could probably be avoided in the first place by optimizing the orbitals within VMC [14,15], instead of using fixed HF orbitals.

In this work, we study the impact of the HF symmetry dilemma for QMC in hydrogen rings H 4n+2 . In Sec. II, we review the HF symmetry-breaking problem in these systems, and discuss the effect of using a Slater basis versus a Gaussian basis. In Sec. III, we explain the QMC methodology and report our VMC and DMC results. Our conclusions are summarized in Sec. IV.

II. HARTREE-FOCK SYMMETRY BREAKING

In previous studies [9,16], the electronic structure of periodic rings of 4n + 2 evenly spaced hydrogen atoms (with a fixed distance of r H-H = 0.74747 Å) has been investigated. The number of hydrogen atoms is restricted to 4n + 2 in order to obtain a possible closed-shell singledeterminant solution with 2n + 1 occupied orbitals. The symmetry-adapted HF wave function has a metallic character (in the limit of an infinite ring) and can be expressed with either delocalized canonical orbitals or localized Wannier orbitals (which do not have an exponential decay). The canonical orbitals, except for the lowest one, are doubly degenerate, and in a minimal basis the orbital coefficients are fixed by the cyclic symmetry. Besides the symmetry-adapted (SA) solution, two different symmetry-broken HF solutions of lower energy can be obtained beyond critical ring sizes, when using unit cells of 2 hydrogen atoms. One solution corresponds to orbitals localized on hydrogen atoms and is referred to as the symmetry-broken atom-centered (SB-AC) solution, while the other corresponds to orbitals localized on bonds and is referred to as the symmetry-broken bondcentered (SB-BC) solution. The SB-BC solution has the lowest HF energy. The three solutions can be schematically described as

• • • H• • • H• • • , • • • H + • • • H -• • • , and • • • H-H• • • .
In each case, the symmetry breaking is accompanied by an opening of an energy gap between occupied and virtual orbitals, and orbitals decay much more rapidly than for the symmetry-adapted solution [9] , in agreement with the theoretical result of Kohn [17].

In order to distinguish the three different wave functions, one may look at the one-particle density matrix

P P αβ = 2 i∈occ. c α i c β i , (1)
containing the coefficients c αi of the occupied molecular orbitals ϕ i ( r),

ϕ i ( r) = α c α i χ α ( r), (2)
expanded in a minimal set of atom-centered basis functions, i.e. one single basis function χ α ( r) per hydrogen atom. As depicted in Figure 1, for the SA solution, we see equal elements on the diagonal and the sub-diagonals of the density matrix. For the SB-AC solution, an alternation of element values on the diagonal of the density matrix is obtained, but equal elements on the first subdiagonal, and for the SB-BC solution we have equality of the diagonal elements and alternation on the first subdiagonal. In Ref. 9, a minimal Gaussian basis set (five s Gaussian functions contracted to one single basis function for each hydrogen atom) was used. However, Gaussian basis functions are not appropriate for all-electron QMC calculations. They give large statistical fluctuations due to their incorrect vanishing gradient at the nuclear positions. It is thus much preferable to use Slater basis functions which correctly have a non-zero gradient on the nuclei and an exponential decay at large distance. In this work, we use a minimal Slater basis set (one 1s Slater function on each hydrogen atom) with an exponent of 1.17, which is smaller than the optimal exponent of 1.24 for an isolated H 2 molecule. Spin-restricted HF (and MP2) calculations were performed with an experimental code for ring systems, employed already for the previous studies [START_REF] Reinhardt | different programs to perform ab-initio calculations within highly localized orbitals[END_REF]. The necessary integrals over Slater functions have been calculated with the program SMILES [START_REF] Rico | [END_REF]. In order to obtain the symmetry-broken HF solutions, we start from a set of localized Wannier orbitals describing either an ionic situation or an explicit bond in the two-atom unit cell, and use an iterative configuration interaction procedure using singly excited determinants [20,21] instead of diagonalizing a Fock operator.

Table I reports the HF energy differences between the and H 62 for SB-BC and SB-AC, respectively. In addition, for a fixed ring size, the lowering in energy of the symmetry-broken solutions is smaller with the Slater basis set. This is an indication that the Slater basis is better than the Gaussian basis, since the amount of symmetry breaking is usually larger for poorer wave functions. The HF total energies are indeed lower with the Slater basis, for example for H 42 , the (SA) energy per two-atom cell is -0.950252 hartree with the Gaussian basis and -0.997003 hartree with the Slater basis. As an additional verification of the usefulness of Slater functions, we can look at Kato's cusp condition [22] at the nuclear positions:

1 2 | ∇ρ( r n )| av. ρ( r n ) = Z, (3)
where ρ( r n ) and | ∇ρ( r n )| av. are the density and the spherical average of density gradient at the nuclear positions, and Z is the nuclear charge. For example, for the H 86 ring, we find 1.009 for SA, 1.012 for SB-BC, and 1.034 and 0.980 for SB-AC, close to the ideal value of Z = 1. Possibly, symmetry breaking can be further reduced by using a larger Slater basis.

III. QUANTUM MONTE CARLO STUDY

QMC methods are sometimes believed to produce benchmarks in quantum chemistry, approaching the electronic correlation problem differently than common wave-function-based methods or density-functional theory. As QMC methods often rely on a HF trial wave function, it is interesting to check their sensitivity to HF symmetry breaking. We start by giving a brief overview of the VMC and DMC methods employed in this work.

A. Brief overview of VMC and DMC

We consider Jastrow-Slater trial wave function of the form

Ψ T (R) = J(R) Φ(R), (4)
where R designates the electron coordinates, Φ(R) is a HF determinant and J(R) = e f ({rij ,rIi}) is a Jastrow correlation factor depending explicitly on the electronelectron distances r ij and the nucleus-electron distances r Ii . In VMC, one calculates the energy as the expectation value of the Hamiltonian H over the wave function Ψ T by stochastic sampling

E VMC = Ψ T (R)HΨ T (R)dR = Ψ T (R) 2 E L (R)dR ≈ 1 M M i=1 E L (R i ), (5)
where E L (R) = HΨ T (R)/Ψ T (R) is the local energy, and the M points R i are sampled from Ψ T (R) 2 by a Metropolis algorithm. In DMC, one improves over the distribution Ψ T (R) 2 by generating another distribution f (R, τ ) obtained by evolving the importance-sampling Schrödinger equation in imaginary time τ = i t

- ∂ ∂τ f (R, τ ) = - 1 2 ∇ 2 f (R, τ ) + ∇ • f (R, τ ) ∇Ψ T (R) Ψ T (R) + (E L (R) -E T ) f (R, τ ), (6)
which resembles an ordinary diffusion equation with diffusion, drift and source terms on the right-hand side. This diffusion process is simulated stochastically with a population of walkers representing the distribution f (R, τ ). The trial energy E T is adjusted in the course of the calculation in order to maintain a stable population of walkers. After some iterations, the stationary distribution is obtained f (R, τ → ∞) = Ψ FN (R)Ψ T (R) where Ψ FN (R) is the fixed-node (FN) wave function, i.e. the best approximation to the ground-state wave function having the same nodes than the trial wave function. In practice, this fixed-node approximation is automatically enforced by using Ψ FN (R)Ψ T (R) as a positive probability density, meaning that Ψ FN (R) must necessarily be of the same sign as Ψ T (R). The DMC energy is then calculated as the statistical average of the local energy of the trial wave function over the mixed distribution Ψ FN (R)Ψ T (R).

The nodes of the wave function are the locations of the points R where the wave function vanishes. For a system of N electrons in 3 dimensions, they form (3N -1)dimensional hypersurfaces. A subset of these nodes is given by the antisymmetry property of the fermionic wave function with respect to the exchange of two electrons, which implies that the wave function vanishes when two same-spin electrons are at the same point in space. However, these "Pauli" (or exchange) nodes form only (3N -3)-dimensional hypersurfaces, and are therefore far from sufficient to determine the full nodal hypersurfaces (see, e.g., Ref. [START_REF] Bressanini | Recent Advances in Quantum Monte Carlo Methods[END_REF][START_REF] Bressanini | [END_REF][25] for examples of simple atomic systems). Likewise, spatial symmetry is generally far from sufficient to specify the nodes. For a given system, different HF wave functions (of different spatial symmetries) share the same Pauli nodes, but otherwise generally have very different nodal hypersurfaces, and thus lead to different fixed-node errors in DMC energies.

B. Computational details

The QMC calculations have been performed with the program CHAMP [START_REF] Champ | a quantum Monte Carlo program written[END_REF] on a massively parallel IBM Blue-Gene architecture using up to 4096 processors. The trial wave functions are constructed by multiplying the previously obtained HF wave functions by a Jastrow factor consisting of the exponential of the sum of electron-nucleus, electron-electron and possibly electronelectron-nucleus terms, written as systematic polynomial and Padé expansions [START_REF] Umrigar | [END_REF] (see also Refs. 28,29). Some Jastrow parameters are fixed by imposing the electron-electron cusp condition, and the others are optimized with the linear energy minimization method in VMC [14,15,30], using an accelerated Metropolis algorithm [31,[START_REF] Umrigar | Quantum Monte Carlo Methods in Physics and Chemistry[END_REF]. The orbital and basis exponent parameters are kept fixed in this work. Once the trial wave functions have been optimized, we perform DMC calculations within the short-time and fixed-node approximations (see, e.g., Refs. 33-37). We use an imaginary time step of ∆τ = 0.01 hartree -1 in an efficient DMC algorithm having very small time-step errors [38]. We use a target population of 100 walkers per processor, and estimate statistical uncertainties with blocks of 1000 steps, which is larger than the energy autocorrelation time of about 50 steps. The statistical uncertainty of the energy per H 2 cell is smaller than 2 × 10 -5 hartree.

The computational cost of optimizing the two-body and three-body terms in the Jastrow factor scales as the third power of the number of hydrogen atoms. When restricting the Jastrow factor to the two-body terms only, the computational cost scales quadratically with the number of hydrogen atoms, indicating that it is the evaluation of the Jastrow factor that dominates the computational cost and not the evaluation of the Slater determinant. The large reduction of computational cost achieved by removing the three-body terms comes without a big loss in the VMC energy, and in principle no loss at all in the DMC energy. For example, for the H 26 ring system, we find a VMC energy of -13.8894 ± 0.0005 hartree with the three-body term, and -13.8430 ± 0.0005 hartree without the three-body term. The computational effort is about 20 times more time consuming in the former case. We thus use a two-body Jastrow only. Another alternative, not employed in this work, is to use a shortrange three-body Jastrow.

(E(H 2n )) ∼ V (E L (H 2n )) M ∼ n V (E L (H 2 )) M , (7)
where M is the number of Monte Carlo iterations. Therefore, the statistical uncertainty of the energy per H 2 cell decreases as 1/ √ n, and thus calculations aiming at a given statistical uncertainty for this quantity requite fewer steps for increasing ring sizes.

C. Results

Figure 2 shows the VMC energies per H 2 cell of the hydrogen rings with 46 to 102 atoms for the three HF solutions. As in the case of Møller-Plesset perturbation theory and linearized coupled cluster doubles theory, the energy ordering of the three solutions is reversed in comparison to HF, the SA wave function giving now the lowest total energy and the SB-BC solution giving the highest energy. For H 86 , we show in Table II the QMC total energies and energy differences of the symmetry-adapted and symmetry-broken solutions. For comparison, we also report MP2 energies calculated with the same Slater basis set. The VMC total energy per H 2 cell lie about 50 mhartree below the MP2 energies, and the energy splittings between the different solutions are smaller than those in MP2, which shows the Jastrow factor does a good job of describing electron correlation.

Figure 3 shows the corresponding DMC results. The energy ordering is the same as in VMC and MP2, the SA wave function giving the lowest DMC total energy, and thus the smallest fixed-node error. As shown in Table II, the energy splittings between the different solutions are much smaller in DMC. This indicates that DMC is less sensitive to symmetry breaking than other correlation methods. It is an interesting feature for cases where symmetry breaking cannot be avoided. Of course, symmetry breaking would probably be avoided if the orbitals were reoptimized in the presence of the Jastrow factor within VMC, but this is computationally expensive for large systems.

IV. CONCLUSION

When HF trial wave functions are used in QMC calculations, in case of HF instabilities QMC faces the HF symmetry dilemma in choosing between the symmetryadapted solution of higher HF energy and symmetrybroken solutions of lower HF energies. In this work, we have examined the HF symmetry dilemma in hydrogen rings H 4n+2 which present HF singlet instabilities for sufficiently large ring sizes. We have shown that using a Slater basis set, instead of a Gaussian basis set, delays the onset of HF symmetry breaking until larger rings and slightly reduces the energy splittings between the symmetry-adapted and symmetry-broken wave functions. When using these different HF wave functions in VMC and DMC, we have found that the energy ordering is reversed; the symmetry-adapted wave function always giving the lowest energy. This confirms previous post-Hartree-Fock studies in showing that these symmetry-broken solutions are bad starting wave functions for correlated calculations. The fact that the symmetry-adapted wave function gives the lowest DMC energy indicates that this wave function has more accurate nodes than the symmetry-broken wave functions. The present experience thus suggests that spatial symmetry is an important criterion for selecting good trial wave functions. For systems that are not very large, the symmetry-breaking problem could probably be avoided altogether by optimizing the orbitals within the quantum Monte Carlo calculation, rather than using fixed HF orbitals.

FIG. 2 :

 2 FIG.2: VMC total energies of H4n+2 rings, per H2 cell in mhartree, for the symmetry-adapted (SA) and the two symmetry-broken (SB-AC and SB-BC) HF solutions from 46 to 102 hydrogen atoms. The statistical uncertainty is about the size of the point.

FIG. 3 :

 3 FIG.3: DMC total energies of H4n+2 rings, per H2 cell in mhartree, for the symmetry-adapted (SA) and the two symmetry-broken (SB-AC and SB-BC) HF solutions from 46 to 102 hydrogen atoms. The statistical uncertainty is about the size of the point.

TABLE I :

 I HF energy differences of H4n+2 rings, per H2 cell in mhartree, between the symmetry-broken solutions (SB-AC and SB-BC) and the symmetry-adapted (SA) one, for the Gaussian and Slater basis sets. Gaussian basis set of Ref. 9 and the Slater basis set of the present study. With the Gaussian basis set, the departure of the SB-BC and SB-AC solutions from the SA solution occurs for H 46 and H 54 rings, respectively. With the Slater basis set, the onset of symmetry breaking takes place for larger rings, i.e. for H 50

		Gaussian basis	Slater basis
	4n+2	E(SB-AC)-E(SA)	E(SB-BC)-E(SA)	E(SB-AC)-E(SA)	E(SB-BC)-E(SA)
	42	-	-	-	-
	46	-	-0.00258	-	-
	50	-	-0.03555	-	-0.00199
	54	-0.00115	-0.08933	-	-0.02739
	58	-0.01900	-0.15116	-	-0.06961
	62	-0.04980	-0.21440	-0.00080	-0.11914
	66	-0.08678	-0.27565	-0.01223	-0.17074
	symmetry-broken solutions and the symmetry-adapted
	one for the

TABLE II :

 II Total energy and energy differences, per H2 cell in mhartree, of the symmetry-adapted (SA) and the symmetrybroken (SB-AC and SB-BC) HF solutions, for the H86 ring, with the Slater basis set.As the variance of the local energy of a ring of n H 2 molecules is approximately n times the variance for one H 2 molecule, the statistical uncertainty of the energy grows with the square root of n σ

	method	E(SA)	E(SB-AC)-E(SA) E(SB-BC)-E(SA)
	HF	-996.15	-0.14	-0.39
	MP2	-1016.22	1.37	1.55
	VMC	-1063.24	0.93	1.36
	DMC	-1077.57	0.31	0.70

Acknowledgment

This work has been financed mainly through the DEISA network, project STOP-Qalm. All QMC calculations have been performed on the IBM Bluegene machines in Jülich and Munich (Germany). C.J.U. was supported in part by the NSF (Grant Nos. DMR-0908653 and CHE-1004603). The authors thank the staff of IDRIS (Orsay, France) for technical assistance to install, test and run the QMC program CHAMP on these machines. We also acknowledge using the Slater integral code SMILES (Madrid, Spain) for obtaining the HF starting wave functions. Discussions with P. Gori-Giorgi (Amsterdam, Netherlands) and J.-P. Malrieu (Toulouse, France) were very helpful for the project.