John Mullennix

Steven Stern

Gérard Bailly
email: gerard.bailly@gipsa-lab.inpg.fr

Pierre Badin

Denis Beautemps

Frédéric Elisei

Computer Synthesized Speech Technologies : Tools for Aiding Impairment -IGI Global

Keywords:

He is now the head of the

Introduction

Speech is very likely the most natural communication mean for humans. However, there are various situations in which audio speech cannot be used because of disabilities or adverse environmental conditions. Resorting to alternative methods such as augmented speech is a therefore an interesting approach. This chapter presents computer-mediated communication technologies that allow such an approach (see Figure 1). Speech of the emitter may in fact:

• not be captured by available hardware communication channels -camera, microphone • be impoverished by the quality of the hardware or the communication channel • be impoverished because of environmental conditions or because of motor impairments of the interlocutor. On the reception side, Augmented Speech Communication (ASC) may also compensate for perceptual deficits of the user by enhancing the captured signals or adding multimodal redundancy by synthesizing new perceptual channels or adding new features to existing channels. In order to improve human-human communication ASC can make use of a priori knowledge on multimodal coherence of speech signals, user/listener voice characteristics or more general linguistic and phonological structure on the spoken language or vocabulary being exchanged. The nature of this a priori knowledge, the quantitative models that implement it and their capabilities to enhance the available communication signals influence the precision and robustness of the communication. The chapter will first present:

Computerassisted mediation

Virtual human

Phonological representation

• the signals that can characterise the speech production activity i.e. from electromagnetic signals from brain activity, through articulatory movements, to their audiovisual traces • devices that can capture these signals with various impact on articulation and constraints on usage • available technologies that have been proposed for mapping these various speech representations between each other i.e. virtual human, direct statistical mapping or speech technologies using a phonetic pivot obtained by speech recognition techniques Three ASC systems developed in the MPACIF Team at GIPSA-Lab will then be described in detail: a) a system that converts non audible murmur into audiovisual speech for silent speech communication (Tran, Bailly, & Loevenbruck, submitted;[START_REF] Tran | Predicting F0 and voicing from NAM-captured whispered speech[END_REF]) b) a system that converts silent cued speech [START_REF] Cornett | Cued Speech[END_REF] into audiovisual speech and vice-versa. This system aims at computer-assisted audiovisual telephony for deaf users (Aboutabit, Beautemps, & Besacier, Accepted;[START_REF] Beautemps | Computer Synthesized Speech Technologies : Tools for Aiding Impairment -IGI Global John Mullennix and Steven[END_REF]) c) a system that computes and displays virtual tongue movements from audiovisual input for pronunciation training (Badin, Elisei, Bailly, & Tarabalka, 2008;Badin, Tarabalka, Elisei, & Bailly, 2008). Preliminary results of the evaluation of these three systems will be given and commented. A discussion on both scientific and technological challenges and limitations will conclude the chapter.

Characterizing speech production

The speech production chain sketched in Figure 2 consists of several signal transformations: the electrical activity of neural circuitry drives the contraction of several dozen of muscles that further shape the geometry of the vocal tract. The air flow generated by the pressure induced by the respiratory muscles interacts with the vocal tract walls in relation with the biomechanical properties of the speech articulators and generates various acoustic sources, such as pseudo-period signals at the glottis or noise signals at constrictions. These acoustic sources excite the vocal tract resonators and are finally radiated as speech sound through the mouth, the nose and skin. Speech production can be thus characterized by:

• Neural activity. Several brain areas are activated in motor control of speech. Nota and Honda [START_REF] Nota | Brain regions involved in motor control of speech[END_REF] found for example that the bilateral motor cortex and the inferior cerebellum hemisphere were activated after the subtraction for breathing, non speech vocalization, and hearing. They asked subjects to plan speech in four different conditions: A) normal speech (spoken aloud), B) mouthed speech (mouthing silently with normal breathing), C) unarticulated speech (voicing ''ah…'' without articulation), and D) internal speech. Activations were also found in the superior temporal gyrus and inferior parietal lobule of the left hemisphere. Activations are also found in Broca's area, the supplementary motor area (SMA), or the insula, especially in case of difficult or unusual speech production task. Note also that most areas dedicated to speech perception are also activated during speech production and vice versa [START_REF] Wilson | Listening to speech activates motor areas involved in speech production[END_REF]). • Muscular activities. Speech production involves the activation of the respiratory muscles (inhalation and exhalation), of muscles controlling the mandible, the lips, the soft palate, the pharynx and the larynx. Note also that the control of speech articulation involves the displacement of intermediate structures such as the hyoid bone. Speech production is thus accompanied by active and passive (resistive) action of both agonist and antagonist muscles.

Capturing speech

Various devices (see Figure 3) can capture dynamic representations of the current state of the speech production system. The aim of this section is to sketch the spectrum of available technology that can be used to record useful signals characterizing articulation and phonation.

The capture of sound vibration is usually performed by distant or head-mounted microphone. An alternative has been proposed to capture sound vibration • The stethoscopic microphone developed by Nakajima [START_REF] Nakajima | Non-audible murmur recognition Input Interface using stethoscopic microphone attached to the skin[END_REF] receives sound vibration through body tissue. This device is attached to the skin of the user, for instance behind the ear. The spectral bandwidth is reduced to 0-3 kHz. The observation of visible speech is typically done using two kinds of devices:

• Surface deformation. 3D range data scanners deliver very precise surface geometry together with texture information (e.g. structured light, time of flight or laser-based scanner technology). Further processing is required to compensate for head movement and to parameterize this surface with a constant number of parameters. • Movement of fleshpoints. Motion capture devices (photogrammetric methods with optical flow calculation or active/passive markers) deliver movement of fleshpoints. They directly parameterize the surface with a constant number of parameters. The observation of the internal organs does not really differ from the observation of facial movements. Three kinds of characteristics are typically monitored: density maps, positions of measurement points ("fleshpoints") and biological signals. Articulatory instrumentation includes:

• Magnetic Resonance Imaging (MRI), computerised tomography (CT), cineradiography as well as Ultra Sound Imaging [START_REF] Whalen | The Haskins optically-corrected ultrasound system (HOCUS)[END_REF] provide information on the density of particular atoms or molecules within a specific volume. Some systems exploit directly the density maps as direct input. A further processing stage often retrieves surface information: if a simple threshold is often sufficient to identify the geometry of vocal tract walls in MRI or CT scan images, the determination of the tongue surface in X-ray images or ultrasound images is far more complicated. The ideal simultaneous resolution in time and space needed to observe speech movements is not available yet: the relaxation time of free hydrogen nuclei in MRI does not allow temporal sampling frequencies of more than 10-20 images per second, while noise increases drastically when acquisition rate of X-ray or ultrasound imaging are increased. Note that a further processing stage is required to determine the individual outline of the various organs in the vocal tract. • ElectroMagnetic Articulography (EMA), ElectroPalatoGraphy (EPG) or X-ray MicroBeam (XRMB) [START_REF] Kiritani | X-ray microbeam method for measurement of articulatory dynamics: techniques and results[END_REF] incomplete information on the articulation process. The many-to-one/one-to-many mapping between these signals is underspecified and both a priori knowledge and regularization techniques should be used to recover the necessary information on the articulation. A priori knowledge can be extracted from multiple sources:

• speech maps [START_REF] Abry | Sound-to-gesture inversion in speech: the Speech Maps approach[END_REF] that are trained off-line and memorize the possible links between these signals that represent the coherence of the speech production process. Such a system builds a kind of speech homunculus that combines all kinaesthetic and sensory-motor information collected during speech production • the phonetic and phonological structure of the language being spoken • … as well as higher-level information on the linguistic content of the message. Various technological tools [START_REF] Guenther | Neural modeling and imaging of the cortical interactions underlying syllable production[END_REF][START_REF] Kröger | Modeling sensory-to-motor mappings using neural nets and a 3D articulatory speech synthesizer[END_REF][START_REF] Ouni | Modeling the articulatory space using a hypercube codebook for acoustic-toarticulatory inversion[END_REF] have been proposed to model this a priori knowledge. We present here two solutions: Gaussian Mixture modelling (GMM; see Toda et al. [START_REF] Toda | Eigenvoice conversion based on gaussian mixture model[END_REF] for its application to voice conversion) and Hidden Markov modelling (HMM; see Rabiner [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] for its application to speech recognition) that have been using in the applications of ASC presented below.

Direct statistical mapping

Speech mapping consists in building a model of the sensory-motor links based on a collection of parallel recordings of multiple characteristic signals. Though in some instances signals can actually be recorded simultaneously (see for example the combination between EMA and US in [START_REF] Aron | Multimodal fusion of electromagnetic, ultrasound and MRI data for building an articulatory model[END_REF]), the same speech items are usually recorded in different experimental setups; resulting signals must be then postaligned, often using the acoustic signal as common reference. Voice conversion techniques [START_REF] Toda | Mapping from articulatory movements to vocal tract spectrum with Gaussian mixture model for articulatory speech synthesis[END_REF][START_REF] Toda | NAM-to-Speech Conversion with Gaussian Mixture Models[END_REF] can then be used to capture statistically significant correlations between pairs of input-output signals.

Characterizing input signals. Input feature vectors X t are constructed by appending feature vectors from several frames around the current frame t. Data reduction techniques (principal component analysis in [START_REF] Toda | NAM-to-Speech Conversion with Gaussian Mixture Models[END_REF] or linear Discriminant analysis in [START_REF] Tran | Improvement to a NAM captured whisper-tospeech system[END_REF])) are often used to limit the number of model parameters to determine when the training material is too limited. Characterizing output signals. Output feature vectors Y t = [y t , Δy t ] consist of static and dynamic features at frame t. A GMM [START_REF] Toda | Spectral conversion based on maximum likelihood estimation considering global variance of converted parameter[END_REF] is then trained for representing the joint probability density p(X t , Y t |Θ), where Θ denotes a set of GMM parameters. The generation of the time sequence of the target static feature vector y from that of the source feature X = [X 1 , X 2 …X T ] is performed so that a likelihood L =p(Y/X,Θ) is maximized. Note that the likelihood is represented as a function of y: the vector Y = [Y 1 , Y 2 …Y T ] is represented as Wy, where W denotes a conversion matrix from the static feature sequence to the static and dynamic feature sequence, respectively y and Δy [START_REF] Tokuda | Speech parameter generation algorithms for HMM-based speech synthesis[END_REF]. Toda et al (Toda et al., 2005) have proposed an improved ML-based conversion method considering global variance (GV) of converted feature vectors that adds another term in the optimized likelihood. The direct statistical mapping does not require any information on the phonetic content of the training data. Alignment of input and output feature vectors -if necessary -can be performed using an iterative procedure that combines Dynamic Time Warping with conversion so that prediction error diminishes as alignment and conversion improve. The main advantage of direct statistical mapping resides in its ability to implicitly capture fine speaker-specific characteristics.

Mapping via phoneme recognition

In direct statistical mapping, the temporal structure of speech is implicitly modelled by considering (a) a sliding time window over the input frames and (b) both static and dynamic output features are combined to produce smooth and continuous parameter trajectories. Another way to account for the special temporal structure of speech is to consider that speech encodes phonological structures: in such an approach, a pivot phonetic representation that links all measurable signals is introduced.

The mapping process proceeds in two steps: a phonetic decoding using speech recognition techniques and an output trajectory formation using speech synthesis techniques. Both steps may use different mapping techniques between signals and phonemes such as classical HMM-based speech recognition combined with corpus-based synthesis. But the recent success of HMM-based synthesis [START_REF] Yamagishi | The HTS-2008 system: Yet another evaluation of the speaker-adaptive HMM-based speech synthesis system[END_REF] opens the route to more integrated statistical approaches to "phonetic-aware" mapping systems. The main advantage of phonetic-based mapping resides in its ability to explicitly introduce linguistic information as additional constraints in the underdetermined mapping problem. Both in the recognition and synthesis process, linguistic or even information structure may be exploited to enrich the constructed phonological Computer Synthesized Speech Technologies : Tools for Aiding Impairment -IGI Global John Mullennix and Steven Stern 23/06/2009 6/10 structure and restore information that could not be predicted on the sole basis of input signals e.g. melodic patterns from silent articulation as required for silent communication interfaces [START_REF] Hueber | Continuous-speech phone recognition from ultrasound and optical images of the tongue and lips[END_REF].

Applications

Applications of ASC systems are numerous. Three main areas can be found in the literature: communication enhancement, aids to communication for speech impaired people, and language training. [START_REF] Toda | NAM-to-Speech Conversion with Gaussian Mixture Models[END_REF] use direct statistical mapping for converting non audible murmur captured by a stethoscopic microphone to audible speech signal. We have recently shown that direct statistical mapping outperforms phonetic-aware HMM-based mapping and that multimodal input improves significantly the prediction [START_REF] Tran | Improvement to a NAM captured whisper-tospeech system[END_REF]. A perceptual identification task performed on a very difficult vocabulary of Japanese VCV stimuli (see Figure 4) shows that listeners can retrieve from converted speech more than 70% of the phonetic contrasts whereas amplified input NAM is unintelligible.

Communication enhancement

Aids to communication for speech impaired people

ASC systems, when addressing communication impairment, aim to compensate for motor or perceptual deficits of one or both interlocutors. BCI can for example be exploited to offer people suffering from myopathy the ability to communicate with other people. Nakamura et al [START_REF] Nakamura | Speaking aid system for total laryngectomees using voice conversion of body transmitted artificial speech[END_REF] have used voice conversion of body-transmitted artificial speech to predict the structure of speech recorded before laryngectomy from speech produced after the surgery. This computer-assisted recovery of speech [START_REF] Verma | Modeling speaking rate for voice fonts[END_REF] can also be performed by adapting voice fonts [START_REF] Verma | Modeling speaking rate for voice fonts[END_REF] to the speaker's characteristics.

Computer Synthesized Speech Technologies : Tools for Aiding Impairment -IGI Global John Mullennix and Steven Stern 23/06/2009 7/10

In our group, Beautemps et al [START_REF] Beautemps | Computer Synthesized Speech Technologies : Tools for Aiding Impairment -IGI Global John Mullennix and Steven[END_REF] are working on a system that will enable deaf people using cued speech (CS) to have visiophonic conversations with normal hearing interlocutors. CS recognition (Aboutabit, Beautemps, Clarke, & Besacier, 2007) and synthesis [START_REF] Gibert | Analysis and synthesis of the 3D movements of the head, face and hand of a speaker using cued speech[END_REF] systems have been developed to allow conversion between speech movements and hand and lips movements. The CS-to-speech system either drives the movement of a virtual hand superposed on the video of the normal hearing speaker that produces audio speech [START_REF] Bailly | Retargeting cued speech hand gestures for different talking heads and speakers[END_REF] or controls the movements of the face, head and hand of a virtual talking head. CS synthesis may restore more than 95% of the phonetic contrasts that could not be solved on the basis of lip reading alone [START_REF] Gibert | Evaluating a virtual speech cuer[END_REF].

Language training

Some ASC systems can also be used as tools for helping learners of a second language to master the articulation of foreign sounds. ASC systems thus perform acoustic-to-articulatory inversion: they compute the articulatory sequence that has most likely produced the sound sequence uttered by the learner. This articulation can be then displayed by means of a talking head in an augmented reality manner (see Figure 6), and compared to the required articulation so that proper corrective strategies are elicited. Several projects of virtual tutors have been launched [START_REF] Engwall | Pronunciation feedback from real and virtual language teachers[END_REF][START_REF] Massaro | A computer-animated tutor for language learning: Research and applications[END_REF].

We have shown that despite the fact that such displays of internal articulation appear very unusual to them, listeners / viewers possess, to a certain extent, native tongue reading capabilities without intensive training (some subjects gain up to 40% recognition rate when watching the tongue display in absence of sound) (Pierre Badin et al., 2008). Such technologies may thus help people in pronunciation training. injected in the underdetermined inversion process so as to restore the coherence of multimodal signals that deliver incomplete information on the speech articulation or that are corrupted by noise.

A number of open issues need to be dealt with before this technology can be deployed in everyday life applications:

• The problem of speaker normalization is a hot topic: Pairs of input/output training data are only available for a limited number of subjects that have accepted to be monitored with quite invasive recording devices. To be practically acceptable, ASC systems should be able to adapt to a specific user quickly using a limited quantity of input/output data; • Similar to speech recognition systems, ASC systems rely a lot on top-down information that constraints the mapping or inverse mapping problem. ASC should be able to benefit from language-specific constraints to gain robustness; • Real-time issues are also very important. Guéguin et al [START_REF] Guéguin | On the evaluation of the conversational speech quality in telecommunications[END_REF] have shown that full-duplex conversation is possible as long as one-way transmission delays are below 400ms. ASC systems should thus exploit limited contextual information to estimate output features. This imposes notably important constraints on speech recognition techniques; Such technologies that connect two human brains benefit from cortical plasticity: people can learn to cope with imperfect mappings and noisy signals. Technologies that combine multimodal input and output are likely to enable computer-mediated conversation with minimum cognitive load. Evaluation issues are critical: people can cope with very crude communication channels but at the expense of the recruitment of intensive cognitive resources that may forbid any parallel activity.

Figure 1 :

 1 Figure 1 : Computer-mediated communication consists in driving an artificial agent from signals captured on the source speaker. The embodiment of the agent may be quite diverse: from pure audio through audiovisual rendering of speech by avatars to a more videorealistic animations by means of of virtual clones of the source speaker or anthropoid robots -here the animatronic talking head Anton developed at U. of Sheffield (Hofe & Moore, 2008). The control signals of these agents can encompass not only audible and visible consequences of articulation but also control posture, gaze, facial expressions or head/hand movements. Signals captured on the source speaker provide partial information on speech activity such as brain or muscular activity, articulatory movements, speech or even scripts produced by the source speaker. Such systems exploit a priori knowledge on the mapping between captured and synthesized signals labelled here as "virtual human" and "phonological representation": these resources that know about the coherence between observed and generated signals can be either statistical or procedural.

Figure 2 :

 2 Figure 2 : The speech production chain. The intended message is decoded by the listener on the basis of audible and visible traces of speech articulation combined with a priori knowledge on the speaker, the language spoken and the message content given the history of the dialog and the situation.

•

  Figure 3. Capturing signatures of speech-production. Left-to-right: ultrasound imaging (from (Hueber, Chollet, Denby, Dreyfus, & Stone, 2007)), electromagnetoarticulography (EMA), electromyography (EMG).

  provide movement or contact information for a few measurement points attached to a speech organ. Note that EMA coils and thin wires going out of the mouth as well as the EPG artificial palate may interfere with speech movements[START_REF] Recasens | An ema study of VCV coarticulatory direction[END_REF] • Surface or needle ElectroMyoGraphy (EMG), ElectroGlottoGraphy (EGG) or photoglotography and the various invasive systems for measuring oral or nasal airflows deliver signals that can be directly exploited for characterizing speech activity. They are however very noisy and must be cleaned via both signal processing and a priori knowledge Finally neuroprosthetics and brain-to-computer interfaces (BCI) exploit devices sensitive to the electromagnetic waves created by the neurons. Invasive (brain implants), partially-invasive (Electrocorticography or ECoG) and non-invasive (electroencephalography or EEG) devices that deliver signals related to speech planning as well as loud, silent or even simulated articulation.4 Mapping signalsASC systems aim at restoring or even augmenting the signals characterizing articulation based on the signals that have been captured by some of the devices mentioned above. Most of these signals are noisy and deliver Computer Synthesized Speech Technologies : Tools for Aiding Impairment -IGI Global John Mullennix

  ASC systems, when addressing communication enhancement, aim either at fusing multimodal input in order to enhance input signals or at adding extra multimodal signals for the interlocutor so as to compensate for noisy channel or noisy perceptual conditions due to the environment. Silent speech interfaces (SSI) fall into this category: SSI should enable speech communication to take place without emitting an audible acoustic signal. By acquiring sensor data from the human speech production process, an SSI computes audible -and potentially visible -signals. Both mapping approaches have been explored: • Bu et al (Bu, Tsuji, Arita, & Ohga, 2005) generate speech signals from EMG signals recorded during silent speech articulation via an intermediate recognition of 5 vowels and the nasal sound /n/ by a hybrid ANN-HMM speech recognition system. The linguistic model has the hard job of restoring missing consonants based on phonotactic constraints of Japanese phonology. Similarly Hueber et al (Hueber et al., 2007) combine HMM-based speech recognition with corpus-based speech synthesis to generate an audible speech signal from silent articulatory gestures captured by US imaging and video. • Conversely Toda et al

Figure 4 .

 4 Figure 4. NAM-to-speech conversion (from (Tran, Bailly, Loevenbruck, & Jutten, 2008)). (a) 3D facial articulation tracked using an active appearance model; the position of the NAM device is indicated by an arrow; (b) non audible murmur as captured by the NAM microphone is characterized by a strong low frequency noise and a band-limited signal; (c) a target sample of the same utterance pronounced loudly in a head-set microphone; (d) the loud signal generated using GMM-based mapping from input signals (a) and (b).

Figure 5 .

 5 Figure 5. Cued speech processing. Left: impressive recognition scores (Aboutabit et al., 2007) are obtained by fusing lip and hand movements. Motion capture is simplified here by make-up. Right: text-to-cued speech synthesis (Gibert et al., 2005) is performed by concatenating elementary gestural units gathered by motion capture on a human speech cuer.

Figure 6 .

 6 Figure 6. Artificial tongue displays that can be used as feedback for pronunciation training (from (Pierre Badin et al., 2008)).

Acknowledgments

Some of the PhD students of the team have largely contributed to settle this research in the laboratory: Nourredine Aboutabit and Viet-Ahn Tran are warmly thanked. We also thank our colleagues Panikos Héracleous, Hélène Loevenbruck and Christian Jutten for discussion and common work. Tomoki Toda from NAIST/Japan was very helpful. This experimental work could not have been conducted without the technical support from Christophe Savariaux and Coriandre Vilain. Part of this work has been supported by the PPF "Interactions Multimodales", PHC Sakura CASSIS, ANR Telma and Artis.


Yu Chen
email: chenyu@google.com

Eric Fleury
email: eric.fleury@inria.fr

Tahiry Razafindralambo
email: tahiry.razafindralambo@inria.fr

Scalable Address Allocation Protocol for Mobile Ad Hoc Networks

In this paper, we present for mobile ad hoc networks an efficient distributed address allocation protocol which is immune to topology changes caused by node's mobility. Contrary to the common belief that mobility makes protocol design more difficult, we show that node's mobility can, in fact, be useful to provide efficient address allocation in ad hoc networks. In our protocol, each node that has been assigned an address manages a disjoint subset of free addresses independently. By taking advantage of node mobility, we can achieve roughly even distribution of free addresses amongst nodes in the system, which enables a new joining node to be configured by its neighbors via only local communication. Theoretical analysis and extensive simulation results are presented. We show that most of the address allocation requests can be processed in a timely fashion via local communication in the requester's neighborhood with time and message complexity in the order of node's degree, regardless of the network size.

I. INTRODUCTION

A wireless mobile ad hoc network is a collection of mobile nodes that communicate over wireless links in a multi-hop fashion without any fixed infrastructure or centralized servers. The focus of this work is on dynamic address allocation in wireless mobile ad hoc networks. Address allocation is a fundamental functionality required in mobile ad hoc networks. A majority of routing protocols for mobile ad hoc networks assume that nodes are configured a priori with a unique address before they communicate. However, such an assumption is not trivial, since there is no global identification which is truly unique; e.g., duplicates exist in IEEE medium access control (MAC) addresses. Hence, it is required to dynamically configure wireless nodes with a unique address upon their entry into the network.

Address allocation should be designed specifically to address the characteristics of mobile ad hoc networks. Mobility is one fundamental issue that needs to be addressed. In traditional networks, dynamic address allocation can be performed by a Dynamic Host Configuration Protocol (DHCP) [START_REF] Droms | Dynamic host configuration protocol[END_REF] server. But this solution is not well suited in wireless ad hoc networks due to the unavailability of centralized servers. Thus the goal should be to design a distributed fast efficient address allocation protocol that is immune to topology changes.

In this work, we present a solution that achieves this goal in spite of its simplicity. Our basic idea is to let each node play an independent equal role in the address allocation service in the sense that each node manages independently a disjoint subset of free addresses. In most existing works on address allocation, the assignment of an address to a new joining node is either authorized by multiple nodes, which are potentially distributed in the whole network, (e.g., [START_REF] Lu | Low-energy address allocation scheme for wireless sensor networks[END_REF]) or by a single node (e.g., [START_REF] Thoppian | A distributed protocol for dynamic address assignment in mobile ad hoc networks[END_REF]). In this work, we let each node take a full responsibility in managing a disjoint set of free addresses, A fundamental difference between our work and existing works is that our approach takes the advantage of node mobility to achieve roughly even distribution of free addresses, and thus, different from most existing works, the assignment of an address requires the authorization from only one node and there are multiple nodes that can authorize address assignments, which implies a reduction in communication cost if new joining nodes can find such a node in their neighborhood.

Contrary to the common belief that mobility makes protocol design more difficult, we show that node mobility can, in fact, be useful to provide efficient address allocation in ad hoc networks. Although, node mobility creates uncertainty on the network topology, it can also be exploited to disseminate information without incurring much communication overhead. Based on this observation, we aim to achieve even distribution of free addresses as follows: when a new node acquires a free address, it gets the free addresses held by all its neighbors and redistributes them evenly among its neighbors and itself. Since mobility increases the chance that different nodes meet each other, such a mechanism can even out the distribution of the free addresses held by nodes in the network, as verified by our analyses and simulation results.

We show by theoretical analyses and simulations that, in our approach, most nodes can be allocated addresses via local communication. As acquiring an address from a neighbor only generates a small number of messages (in the order of the new joining node's degree) and can be done a timely way regardless of the network size, our work provides fast efficient address allocation and it scales well to larger networks. Furthermore, as our approach mainly relies on local communication, it is less vulnerable to topology changes caused by node's mobility. In this work, our proposed solution is targeted at address assignment, but the idea can be easily extended to general resource management.

An overview of related work is given in Section II. Then we give the basic idea of our approach in Section III and describe our implementation in Section IV. Theoretical analyses are given in Section V and simulation results are presented in Section VI. Last we conclude our paper in Section VII.

II. RELATED WORK

A number of address auto-configuration protocols have been proposed for ad hoc networks, which aim to provide an efficient address assignment in a dynamic environment; a comprehensive survey can be found in [START_REF] Weniger | Address Autoconfiguration in Mobile Ad Hoc Networks: Current Approaches and Future Directions[END_REF].

One strategy is to employ some duplication address detection mechanism in address allocation. The basic idea is to let a new joining node pick an address by itself and checks the uniqueness of the picked address by some duplication detection mechanism, and if duplication is detected, a new address is chosen; this procedure is repeated until a unique address is found. Examples of protocols that take this strategy including [START_REF] Vaidya | Weak duplicate address detection in mobile ad hoc networks[END_REF] and [START_REF] Jeong | Autoconfiguration technologies for ipv6 multicast service in mobile ad-hoc networks[END_REF] Another strategy is based on a central or a distributed entity that assigns unique addresses to new nodes. The Dynamic Host Configuration Protocol (DHCP) [START_REF] Droms | Dynamic host configuration protocol[END_REF] is an example of this strategy. DHCP is a four phases protocol, a new joining node floods the network with a DHCP discover packet. Every DHCP server that can configure the new joining node sends (using flooding) a DHCP offer packet containing the assigned address and other configuration information to the client. The client sends back a DHCP request packet to the first server to confirm the reception of an address. In the last phase, the DHCP server sends an acknowledgment to the client. In [START_REF] Nesargi | Manetconf: Configuration of hosts in a mobile ad hoc network[END_REF], each node maintains a list of all the addresses in use in the network. When a new node joins the system, it requests an address through one of its neighbors that have joined the system. The latter chooses an address that is free according to its address list and query throughout the network for the permission to assign the chosen address; the assignment is granted only if a positive acknowledgment is received from all known nodes. In [START_REF] Lu | Low-energy address allocation scheme for wireless sensor networks[END_REF], address space is stored in a distributed way on a subset of specific nodes called ADA (ADdresses Agents). Each node is at least one hop away from an ADA. Each ADA periodically sends an HELLO message. A new joining node that receives the HELLO message is assigned an address by the ADA. If the new joining node does not receives an HELLO message, it becomes an ADR (ADdresses Root) with an address pool it also randomly generates partition identifier for merging purpose.

Works that are most similar to our work is Dynamic Configuration Distribution Protocol (DCDP) [START_REF] Misra | Autoconfiguration, registration, and mobility management for pervasive computing[END_REF], which uses a transactional model whereby nodes are either requesters of or responders to individual configuration requests. As in our approach, each node in DCDP owns an address pool; the essential difference is how the free addresses are distributed in the address pools of nodes in the network. In DCDP, when node responds a requesting node, it sub-leases part of its available address pool to the requester; while in our approach, instead of obtaining the address pool from a single node, a requester gets the information of the free addresses in the address pools of all its neighbors and redistributes them evenly in the address pools held by its neighbors and itself; since mobility increases the chance that different nodes meet each other, such a mechanism can even out the distribution of the free addresses among nodes in the network. As we will see, the performance is much improved in our approach. The work presented in [START_REF] Hu | Zero-maintenance address allocation in mobile wireless ad hoc networks[END_REF] is very close to [START_REF] Misra | Autoconfiguration, registration, and mobility management for pervasive computing[END_REF].

A fundamental characteristic of mobile ad hoc networks is nodes' mobility. In most works, mobility has a negative impact on protocols' performance and most of them do not consider node's mobility or assume that nodes are static until they are configured. However, it is also shown mobility can also help to provide better services, such as capacity [START_REF] Grossglauser | Mobility increases the capacity of ad-hoc wireless networks[END_REF], security [START_REF] Capkun | Mobility helps security in ad hoc networks[END_REF]. In this work we exploit mobility to design and efficient address allocation protocol.

III. BASIC IDEA OF OUR APPROACH

In our protocol, in order to reduce communication overhead and latency, we let each node take a full responsibility in managing a disjoint set of free addresses -when a new joining node's address allocation request is successfully processed, it is assigned an address and a set of free addresses that it is responsible to manage. We aim to evenly distribute the free addresses among nodes, thus a new joining node can be configured by its neighbors via local communication, provided that it is connected to at least one node in the system. Our basic idea is that, during the process of its address allocation request, the new joining node redistributes evenly among its neighbors and itself the free addresses that were previously held by its neighbors. In this paper, the term "broadcast" stands for message propagation in a node's neighborhood and the term "flooding" refers to network-wide message propagation. We refer address space to the set of addresses from which addresses are to be assigned to nodes in the system. The system can be initialized manually by assigning one or several nodes an address and a set of free disjoint addresses. These particular nodes are only important for initialization, since nodes play an equal role after this initialization phase.

After the system initialization, when a new joining node, called client, acquires an address, the following steps are taken. 1) The client broadcasts an address allocation request. 2) When a node in the system receives a request, it responds with its free addresses ; we refer a server to a node that has responded to an address allocation request.

3) The client listens to the responds from its neighbors for a timeout period. If it receives at least one free address, it picks one of them as its own address and divides the rest into D+1 roughly equal size portions, where D is the number of servers from which the client has received the responses. The client keeps one portion as its free addresses and send one portion to each of its servers, which will update its free addresses as the received addresses.

If the client does not get any free address during the timeout period, it resends the request; as nodes are moving around in the network, the client might meet some nodes that hold an non-empty set of free addresses when it resends the request.

Address release upon nodes departure is simple in our protocol: when a node leaves the system, it sends its address and the set of free addresses it holds to one of its neighbors which can be chosen randomly. These addresses are merged into the set of free addresses held by this neighbor and thus they can be reassigned to other nodes later.

Note in our approach, as free addresses managed by each node are disjoint, duplicate addresses will not occur in the scenarios with node crashes, network partitions or message loss; instead, address loss might happen. Our approach does not deal with network partitions or node crashes explictly. The idea behind is that, from the aspect of address allocation, the detection of network partition and node crashes is unnecessary as long as free addresses are available for new joining nodes. If a node does not get an address after a given number of requests, in most of solutions described in the literature, a request is flooded in the network and the new joining node is assigned an address in a multi-hop flooding way (since nodes are mobile). The flooding can also be used to recover lost addresses or to generate new address pools.

It is worth noting that even if a flooding can be time and resource consuming from the network point of view it can be used in our protocol. However, in the protocol implementation proposed in this paper, thanks to nodes' mobility, we remove the flooding approach and allow some nodes, not to be configured. Our analysis and simulations show that the percentage of unconfigured node is very small and that most of the address allocation requests can be processed in a timely fashion via local communication, regardless of the network size. Moreover, unlike most of the works proposed in the literature, our work is imune to topology change.

IV. PROTOCOL DESCRIPTION

In this section, we present a protocol implementation of our algorithm. We will also discuss in details the implementation of basic enhacements that can improve the performance of our protocol.

As many low-level protocols (e.g., MAC protocols), we assume that each node is equipped with a timer and each node has an identifier that is unique within its two-hop neighborhood; here we use the term "identifier" to distinguish it from the one, termed "address", assigned by our address allocation protocol. We denote the identifier of node n by id(n). A node's identifier can be a number randomly generated from a sufficiently large space. It is worth noting that the this identifier has to be unique at least in the two-hop neighborhood of the node. In our protocol, such identifiers are used only in local communication. Thus even though the length of identifiers is large, the overhead is restricted. Note once nodes are assigned addresses by our protocol, it is the assigned addresses, instead of the identifiers, that are used in high level communication.

A. Local variables and message formats

The local variables maintained by each node and the formats of messages exchanged by our protocol are given in Algorithm 1, where we denote the data type of node identifiers by Identifier and the data type of node addresses by Address.

A node n's address allocation state is represented by three variables: the address addr assigned to n, the set addr space of free addresses managed by n, and the identifier client of the node whose request is being processed by n; client is set -1 if n is not processing any request. Temparory variables are also used.

Three types of messages are defined by our protocol. The first type is ARQ (Address ReQuest) messages. This type of messages are sent by new joining nodes that require addresses. An ARQ message contains the identifier of the sender in the field src.

Upon the reception of an ARQ message, nodes that process this request responds with ARR(Address Request Response) messages. An ARR message has three fields: the identifier of the sender src, the identifier of the destination dst, that is, the identifier of the client whose address allocation request is being processed by the sender, and the set addr space of the free address space managed by the sender.

After a client receives ARR messages from servers that are processing its request, it broadcasts an ASU (Address Space Update) message to update the servers' state. An ASU message has three fields: the identifier of the sender src, a list server list of identifiers of the servers whose free address spaces will be updated by the client; the updated space of the ith node in server list is specified by addr space[i].

In the sequel, given a node n and a name x that identifies a variable, we use the denotation n.x to refer to variable x at node n, and given a message m and a name x that identifies a field, we use the denotation m.x to refer to field x in message m.

B. Algorithm sketch

The protocol version of the proposed algorithm, named MAAA (Mobility-Aided Address Allocation) protocol, is given in Algorithm 1. A new joining node follows Part I of Algorithm 1 to request an address. We use a variable try, initialized in lines 1 and updated in line 2, to trace the number of requests a node has sent.

A client sends an address allocation request via an ARQ message and it sets the timer to expire in time WaitTimeOut (lines 3-4). Before the timer expires, the client collects the free address spaces managed by the servers that process its request (lines 5-11); this information is carried in the ARR messages and the received free space and the identifiers of servers are recorded in variables recv addrs and recv servers respectively. If the client receives any free address (line 12), it picks one free address as its address (line 13) and divides the received free addresses into roughly equal size sets (line 14). The client picks one set as the free space managed by itself and it broadcasts an ASU message to update the free address space managed by servers in recv servers.

If the client fails to receive any ARR message, it resends the request (lines 17-25); the number of requests sent by a client is bounded by parameter MaxTry (line 18). The client waits for IntervalARQ (lines 19-20) before it resends the request (line 21).

Nodes that have joined the system (is already configured) follow Part II of Algorithm 1 to process address allocation requests. Each server can process more than one request at a time. When a node receives an ARQ message, even if it has no free addresses or if it is processing another request, sends an ARR message that carries the information of its free address space which can be 0 if it has no free addresses; a random backoff mechanism is used to avoid collisions (lines 3-4), where MaxMACDelay is an estimation on the maximum latency to send a message in one hop by the underlying MAC protocol. The accuracy of MaxMACDelay will not affect the correctness of the protocol. When a server receives an ASU message from a client (line 7), it updates its free space as indicated by this ASU message (lines 8-11).

4:

send ARR message m ′ with m ′ .src = id(n), m ′ .dst = client, m ′ .addr space = n.addr space;

5:

n.addr space = 0 6: end while 7: while receive an ASU message m with (m.src == client) do 8:

if (id(n) ∈ m.server list) then

9:

i = index such that m.server list[i] = id(n);

10:

n.addr space = n.addr space + m.addr spaces[i];

11:

end if 12: end while

V. PERFORMANCE ANALYSES

Theoretical analyses are presented in this section. Intuitively, with higher node density or node mobility, more nodes can be assigned addresses via local communication, as they have more chance to meet different nodes. This is verified by our analyses. Our algorithm is designed for general mobile scenarios. However, as arbitary mobility prevents most problems from being analyzed, we present our analyses for a simplified scenario modeled as follows, where for presentation simplification, we allow each node to hold a "floating-point number" of addresses (non-integer).

• Initially there are N 0 nodes, denoted by {n 1 , . . . , n N 0 }, each of which holds R addresses, including one address allocated to itself and R -1 free addresses that can be allocated to new joining nodes. We denote by S = N 0 R the size of the address space. • Only one node joins the system at a time.

• When a node n joins the system, it connects to D nodes such that each node in the system becomes n's neighbor with an equal probability. Our analyses indicate that the performance improves as node mobility or node density increases. We show in this section that the expected number of addresses at a node, including its address and the free addresses it holds, is proportional to the ratio of the total number of available addresses to the number of nodes in the system. In particular, we prove that, when 1 r of the available addresses have been assigned to N = S r nodes, the expected number of addresses at a node is at least r D D+1 . This result implies that, as long as the total number of nodes is no more than D D+1 S, the expected number of addresses at a node is at least one.

Note the case N 0 < D+1 can be modeled by a system with D + 1 initial nodes, each of which has N 0 R D+1 addresses, since when D + 1 -N 0 new nodes join the system, the system will reach a state with D + 1 nodes and each node having N 0 R D+1 addresses. So we only need to consider the case N 0 ≥ D + 1. We divide the execution into steps such that given any t > 1, the tth new node joins the system at step t; we denote by N t = N 0 + t the total number of nodes that have joined the system at the end of step t and denote by n N t the node that joins the system at step t. In particular, we refer "the state at the end of step 0" to the initial state. For any t ≥ 0 and any i ∈ [1, N t ], we denote by r (i) (t) the amount of addresses held by node n i at the end of step t.

Addresses are reallocated by our algorithm as follows. Here we focus on the steps in which address allocation can be done via the standard procedure; this represents the number of nodes that can be assigned addresses via only local communication. Since we are interested by the total amount of addresses held by a node, for each t, we present the update on the value of r (i) (t) for each node n i , instead of the specific r (i) (t) addresses allocated to n i .

• Initially, only nodes n 1 , . . . , n N 0 exist in the system, each of which holds R addresses. That is,

r (i) (0) = R, ∀i = 1, . . . , n N 0
• At step t, node n N t joins the system and the free addresses are reallocated as follows.

-A set D nodes = {i 1 , . . . , i D } of D indices are randomly chosen from {1, . . . , N t-1 }, representing the D nodes that are randomly picked as the neighbors of n N t .

-Note the address reallocation is simplified by allowing each node to hold a floating-point number of addresses. We have

r (i) (t) = k∈D nodes r (k) (t-1) D+1 if i ∈ D nodes ∪ {N t } r (i) (t -1) otherwise
Only nodes in {n i |i ∈ D nodes ∪ {N t }} update their addresses. These nodes have the same number, r N t (t), of addresses at the end of step t. The new join node n N t cannot obtain an address from its neighbors if and only if r

(N t ) (t) < 1.
Since our focus is on address allocation via local communication, we define local allocation processes as those from step 0 to step t where t satisfies r (N t ) (t) < 1. In the sequel, we present our analyses for (1) the number of addresses held by each node at the end of each step, and (2) the number of nodes in the system when a local address allocation process stops. We denote the step in which a local address allocation process stops by step T , that is, r N T -1 (T ) ≥ 1 and r N T (T ) < 1. The total number of nodes that have been allocated an address via only local communication is N T -1. In this section, given a vector v, we use v (i) to denote the ith element in v and given a matrix M , we use M (i,j) to denote the element at the ith row and jth column in M .

A. State vector and transition matrix

We describe the state of address allocation at the end of step t ≥ 0 by a vector of N elements for some large number N ≥ N 0 ; the ith element, i ∈ [1, N ], is the number of addresses held by node n i at the end of step t. Note only nodes {n 1 , . . , n N t } have joined the system, and the number of addresses held by nodes in {n N t +1 , . . . , n N } are defined to be 0.

Definition 1 (State Vector r(t)): Given any t ≥ 0, the state of address allocation at the end of step t is described by a state vector r(t) defined as:

r(t) ≡ r (1) (t), r (2) (t), . . . , r (N t ) (t), 0, . . . , 0 , where r (i) (t), i ∈ [1, N t ],
is the number of addresses held by node n i at the end of step t. As D nodes are randomly chosen at each step, r(t) is a random variable. Given t ≥ 1 we denote by R(t) the sample space of the random variable r(t). Given any t ≥ 0 and r ∈ R(t), we denote by P (r, t) the probability that the state at the end of step t is r. Formally, ∀t ≥ 0, ∀r ∈ R(t), P (r, t) ≡ the probability of (r(t) = r)

The initial state vector and sample space are given below:

• the state vector r(0) = r (1) (0), . . . , r (N 0 ) (0), 0, . . . , 0 , where r (1) (0) = . . . = r (N 0 ) (0) = R, and • the sample space of the state vector

R(0) = { r (1) (0), r (2) (0), . . . , r (N 0 ) (0), 0, . . . . . . }.
The state r(t) is decided by the state r(t -1) at the end of step t -1 and the action taken at step t. We model the action taken at step t by a matrix A(t), called a transition matrix.

Definition 2 (Transition Matrix): Given ∀t ≥ 1, we use an N × N matrix A(t), called the transition matrix, to represent the action taken at step t on the state of address allocation. That is, ∀r(t -1) ∈ R(t -1), we have

r(t) = r(t -1)A(t),
which is equivalent to

r (i) (t) = N k=1 r (k) (t -1)A (k,i) (t).
Given any t > 1, the transition matrix A(t) is a random variable. We denote by A(t) its sample space. Given A ∈ A(t), we denote by P (A, t) the probability that the transition matrix at step t is A. Formally ∀t ≥ 1, ∀A ∈ A(t), P (A, t) ≡ the probability of (A(t) = A).

The matrix A(t) that models our algorithm is computed as follows. At step t ≥ 1, given the indices {i 1 , . . . , i D } ⊆ [1, N t-1 ] of the D picked nodes, the transition matrix is

A(t) = T (i 1 , . . . , i D , t),
where T (i 1 , . . . , i D , t) is an N × N matrix such that

T (i,j) (i 1 , . . . , i D , t) ≡    1 D+1 if i, j ∈ {i 1 , . . . , i D } 1 D+1 otherwise, if i ∈ {i 1 , . . . , i D }, j = N t 1 otherwise, if i = j, i, j ≤ N t-1 0 otherwise
Given a matrix A = T (i 1 , . . . , i D , t), we denote {i 1 , . . . , i D } by D nodes(A); intuitively, these are the D nodes picked in the action modeled by A. We can verify that the A(t) so computed is consistent with our algorithm, since letting r = r(t -1)A(t), we have

r (i) = k∈D nodes(A(t)) r (k) (t-1) D+1 if i ∈ D nodes(A(t)) ∪ {N t } r (i) (t -1) otherwise .
The sample space of A(t), denoted by A(t), is the set of matrix T (i 1 , . . . , i D , t) for all the possible combinations {i 1 , . . . , i D } of D indices from {1, . . . , N t-1 }. Formally, we have

A(t) = T (i 1 , . . . , i D , t) : i k 1 = i k 2 , ∀k 1 , k 2 ∈ [1, D] ∧ (i k ∈ [1, N t-1 ], ∀k ∈ [1, D])

B. Expected state vector

Now we investigate the expected value of the state vector at step t. We define

r(t) ≡ r∈R(t) P (r, t)r and A(t) ≡ A∈A(t) P (A, t)A
Below we give a property of the expected state vector. Lemma 1:

r(t + 1) = r(0) • A(1) • A(2) . . . A(t + 1)
Proof: Due to space limitation, the proof will not be developped here. The intuition of the proof is that by defintion we have: r(t + 1) = r∈R(t+1) P (r, t + 1)r. And we can show that r(t + 1) = N k=1 r (k) (t) • A (k,i) (t + 1) . Since r(0) = r 1 (0), r 2 (0), . . . , r N 0 (0), 0, . . . , 0 is known, r(t + 1) can be computed if A(1), . . ., A(t + 1) are computed. In the next lemma, we present a computation of A(t); in particular, we compute A (i,j) (t), ∀i, j ∈ [1, N ].

We consider scenarios where nodes are randomly deployed in an 1000 meters × 1000 meters square; the radio range of each node is set to be 120 meters. The total number of nodes is denoted by N and the address space is R. We first consider R = N . The value of N is varied from 50 to 400 to achieve different levels of node density. Initially there is exactly one node in the system and new nodes are randomly joining the system as they are moving in the network area according to the a random waypoint mobility model (RWP), a random waypoint mobility model with attractors (ATT) or a Manhattan mobility model (MAN). In RWP model, nodes travel from a starting point to a randomly chosen destination at randomly chosen speed from [START_REF] Droms | Dynamic host configuration protocol[END_REF]25]m/s. When a node reaches its destination it pauses for 2 seconds before it randomly choose a new destination. ATT model is the same as the RWP model except that we define 4 attractors and the node randomly chooses a destination within a range of an attractor. In the MAN model the network area is divided into 10 × 10 grid. A node follow the edges of the grid. At a given intersection and after a pause time of 2s, the node randomly chooses an edge and leave the actual intersection at a random speed. The simulation duration is 300 seconds. We set WaitTimeOut to be 0.10 second, MaxMACDelay to be 0.05 second, IntervalARQ to be 5 seconds. We also run simulations where nodes are static to show how mobility can aid address allocation. Our simulations consist of two parts. In part I, we first evaluate the percentage of nodes that are allocated addresses via only local communication. Our simulation results show that ∼70% of nodes can be allocated via only local communication (for Speed ≥ 15m/s, R = 200 and RWP). Since address allocation via local communication can achieve efficiency and immunity to mobility, it is interesting to investigate whether it is possible to enable most nodes to be allocated addresses locally by giving extra bits in addresses as shown in our theorem. In part II, given a number of nodes N , we evaluate the percentage of nodes that are allocated addresses via local communication with up to 3 extra bits in addresses, that is, we consider address space R = rN with r = 1, 2, . . . 8. Our simulation results show that a very small number (up to 3) of extra bits in the addresses can enable most of the nodes to be allocated addresses via only local communication. The simulation results are given in Figures 1 and2. More explanations and discussions follow.

A. Impact of mobility

Impact of Speed: We observe that for all mobility models an increasing speed, roughly increases the number of node allocated via local communication (left figures of Part I of Fig. 1). Indeed, when node's speed is high, it enables a new node to meet different sets of nodes when it sends allocation requests. It is worth noting that the % of nodes are roughly similar for different speed because MaxTry is set to infinity. Results in Subsection VI-C shows clearly how different speed can affect the protocol's performances. Impact of density: The impact of node density differs depending on node mobility models. Surprisingly, we observe that for the random way point (RWP) model the % of nodes is stable when the density increases. The right figures of PartI of Fig. 1 show the % of available address at the end of the simulation. We can see that this value is decreasing for all mobility models but the sum of % of nodes and % of available address is not 100%. This tells us that the increasing density increase the address losses due to message collisions and thus reduce the % of nodes. As in our analysis we do not consider message losses the results of our theorem and the impact of density are different. Impact of node's mobility model: We observe that the shape of the curves are different depending on the mobility model. However, an increasing speed increase the % of nodes for all model compared to static network. For RWP, the % of nodes of node is stable. Indeed, when the node density increase the probability for a new joining node to meet a server increases. As stated earlier, when the node density is high, messages are more likely to be lost especially ASU and thus address pool are lost and % of nodes decreases. For ATT, the attractor are useful when node's mobility is low since new joining nodes are more likely to meet server around an attractor. However, the density around an attractor is very high and thus increases the message losses and address pool loss. For the Manhattan model (MAN), the nodes are evenly distributed on the plane which reduce the collision probability compared to the other model. Since nodes are evenly distributed, the probability for a new joining node to meet a server is also low compared to the other models.

B. Impact of protocol's parameters

Impact of R: We observe in Figure 2 (left figures) that increasing the address space increases the % of nodes. These behaviour is related to the right figures of PartI of Figure 1 since increasing the value of R reduce the effect of address pool losses. Impact of initialized nodes: We observe in Figure 2 ( the right figures) that the impact of the number of initialized node is important only for low speed. Indeed for high speed, the address pool is more likely to be distributed among nodes. It is worth noting that for MAN, increasing the number of initialized nodes has a greater impact since nodes are evenly distributed on the plane with this model.

C. Protocol's performance evaluation

In this section we show the performance evaluation results of our protocol 1 . We assume that R = 2 × N with N = 200, and that we have 4 starting nodes. With these paremeters, the number of configured node is ∼ 99% except for static networks. The Figure 3 plots the distribution of configuration time for RWP. We can see from this graphs that mobility increase the performance of address allocation because with the same density of node, the maximum time needed to configure all nodes when the nodes' speed is 25m/s is ∼ 40s, this value is ∼ 70s for a speed of 15m/s and ∼ 138s for a speed of 2m/s. These distributions also tell us that more than 80% of the nodes are configured in less than 6s which means that these nodes are configured after the first ARQ request (for RWP, 25m/s).

VII. CONCLUSION

We present in this work an efficient distributed address allocation protocol which is immune to topology changes. In our protocol, each node that has been assigned an address manages a disjoint subset of free addresses independently. By taking advantage of node mobility, we can achieve roughly even distribution of free addresses amongst nodes in the system, which enables a new joining node to be configured by its neighbors. Theoretical analyses and extensive simulation results are presented. We show that most of the address allocation requests can be processed in a timely fashion via local communication, regardless of the network size.

Algorithm 1 5 : 6 : 9 : 10 :on a server n: 1 :

 1569101 MAAA (Mobility-aided address allocation) protocol • Message formats: ARQ messages: Identifier src; ARR messages: Identifier src, dst; Address addr space[ ]; ASU messages: Identifier src, server list[ ]; Address addr spaces[ ][ ]; • Local variables: Address addr, addr space[ ]; Identifier client = -1; • Parameter: double WaitTimeOut, IntervalARQ, MaxMAXDelay; int MaxTry; PartI -Code on a client n: 1: int try = 0; 2: try + +; 3: broadcast an ARQ message m with m.src = id(n);4: set TIMER to expire in time WaitTimeOut; Address recv addrs[ ] = ∅; Identifier recv servers[ ] = ∅; 7: while (TIMER = 0) do 8: Upon reception of an ARR message m with m.dst = id(n) recv addrs = recv addrs ∪ {m.addr space}; recv servers = recv servers ∪ {m.src}; 11: end while 12: if ( recv addrs = ∅) then {{/* Successfully get an address */}} 13: addr = one address from recv addrs; 14: divide recv addrs -{addr} into k = |recv servers| + 1 subsets a 0 , . . ., a k with roughly equal size; 15: addr space = a k ; 16: broadcast an ASU message m with m.src = id(n), m.server list = recv servers and ∀i ∈ [0, |recv servers|], m.addr space[i] = a i ; 17: else {{/* Fail to get an address */}} 18: if try < MaxTry then 19: set TIMER with expiration time IntervalARQ; 20: while (TIMER = 0) do no-op; endwhile while receive an ARQ message m do 2: client = m.src; 3: backoff random time in [0, WaitTimeOut -MaxMACDelay];

Fig. 1 .

 1 Fig. 1. Simulation results (Part I)

Fig. 2 .

 2 Fig. 2. Simulation results (Part II)

Due unfair assumptions, comparison with other address allocation proto-

Lemma 2: Given t ≥ 0, letting x(t) = 1 -

otherwise.

Proof: First note at step t + 1,

• the probability for a node n i , i ∈ [1, N t ], to be picked is 1) . Here we compute

In this case, ∀A ∈ A(t), andA (i,i) = 1 otherwise. So we have

In this case, ∀A ∈ A(t), A (i,j) = 1 D+1 if i, j ∈ D node(A), and A (i,j) = 0 otherwise. So we have

In this case, ∀A ∈ A(t), A (i,N t+1 ) = 1 D+1 if i ∈ D node(A), and A (i,N t+1 ) = 0 otherwise. So we have

In this case, ∀A ∈ A(t), A (i,j) = 0. So we have A (i,j)(t) = 0. Note that the prove is shorten du to space limitation.

Given a state r(t-1) at step t-1, addresses are redistrbuted at step t according to A(t). Note for any step t, ∀k ∈ [1, N t ], the sum of entries at row k is

This means no address lost. The difference of two entries A (i,j) (t) and

N t (N t -1)(D+1) ≥ 0, each of which decreases as D increases; in particular, the minimum value, 0, is achieved when D = N t . Since a smaller difference in the A(t) means addresses are more evenly distributed in the system, this explains why a better performance can be achieved with a larger D.

Below we present a property of r(t), which will be used in our proof for the main theorem.

Lemma 3:

We can prove the lemma by showing ∀t > 0,

Note here that the proof is shorten due to space limitation. We have our main theorem below, which states that the expected number of addresses at a node, including its address and the free addresses it holds, is proportional to the ratio of the total number of available addresses to the number of nodes in the system.

Theorem 4: At step t ≥ 0, we have

.

Proof: It is easy to see ∀t ≥ 0, r (i) (t) ≥ r (N t ) (t). For any t ≥ 0, we have

In particular, when 1 r of the available addresses have been assigned to N = S r nodes, the expected number of addresses at a node is at least r D D+1 . This result implies that, as long as the total number of nodes is no more than D D+1 of the total number of addresses, the expected number of addresses at a node is at least one.

VI. SIMULATION RESULTS

We evaluate the performance of our address allocation scheme through simulations using ns-2 [START_REF] Team | The network simulator -ns-2. VINT Project Team[END_REF]. As our protocol distinguishes from others in that we aim to achieve address allocation via only local communication, our focus in the simulations is on the percentage of nodes that are assigned addresses by neighboring nodes; we denote this value by "% of nodes" in the sequel. We examine the impact of the mobility, the protocol's parameters and the time needed for a node to be configured. Due to space limitation, we do not investigate the protocols parameters such as MaxTry or IntervalARQ. In our protocol, whether a new node can get free addresses via local communication depends on the state of servers that handle its request when it sends (up to MaxTry) address allocation requests; the probability that it is allocated free addresses by neighbors is higher if it meets more servers and thus depends on node mobility and size of address space.


Tahiry Razafindralambo
email: tahiry.razafindralambo@inria.fr

Isabelle Gu

Érin Lassous

SBA: A Simple Backoff Algorithm for Wireless Ad Hoc Networks

Keywords: Ad hoc Networks, MAC protocol, Backoff Algorithm

The performance of ad hoc networks based on IEEE 802.11 DCF degrade when congestion increases. The issues concern efficiency and fairness. Many solutions can be found at the MAC layer in the literature, but very few solutions improve fairness and efficiency at the same time. In this paper, we design a new backoff solution, called SBA. SBA uses only local information and two contention window sizes. By simulations, we compare SBA with IEEE 802.11 and several alternatives to 802.11 in ad hoc networks. We show that SBA achieves a good tradeoff between fairness, simplicity and efficiency.

Introduction

An ad hoc network is a collection of nodes that communicate via wireless links in a multihop fashion without any fixed infrastructure or centralized servers. An ad hoc network has many practical applications including emergency/rescue operations, military operations and personal area networking.

One challenge in designing protocols for such a network is Medium Access Control. The IEEE 802.11 standard provides a communication mode called DCF (Distributed Coordination Function) that is fully distributed and usable in ad hoc networks [START_REF]Local and Metropolitan Area Network -Specific Requirements -Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF]. However, the MAC protocol described in DCF exhibits some performance issues in terms of efficiency (often given as the overall throughput in the network) and fairness [START_REF] Chaudet | Performance Issues with IEEE 802.11 in Ad Hoc Networking[END_REF]. If some stations cannot access to the medium or cannot send its packets successfully, these nodes can disconnect the network. Such a disconnection may affect the behaviour of the whole network or prevent some nodes from providing a given service. On the other hand, if fairness and efficiency are achieved, QoS guarantees may be expected and/or provided by/for upper layer and thus for the user application.

Many works have tackled the problem of fairness and efficiency in ad hoc networks. Some approaches modify the BEB (Binary Exponential Backoff) algorithm of IEEE 802.11 to provide better performance, whereas ohers introduce new mechanisms. Most ot the existing solutions provide either efficiency or fairness, but very few solutions consider both of them.

In this article, we propose a new approach for a backoff-based algorithm for ad hoc networks, called hereafter SBA for Simple Backoff Algorithm. Our solution relies only on local information, as successful transmissions and collisions undergone by each station without taking advantage of the carrier sensing mechanism nor the packets that can be decoded. Contrary to the BEB algorithm, SBA has only two distinct contention window sizes. SBA also uses the same contention window for all the packets it has to send in a given time interval. At the end of this interval, some computations are done to choose the contention window for the next interval. The first results show that SBA is a good candidate in terms of trade-off between fairness, simplicity and efficiency.

After a state-of-the-art given in Section 2, SBA is described in Section 3 . Then, the protocol is evaluated by simulation. The results are given in Section 4. We compare SBA with 802.11 and some other fair MAC protocols. Finally, we give a preliminary study on the complexity of these protocols in Section 5.

Related work

Due to space limitation, we only cite works that focus on the fairness issue in ad hoc networks and that design single channel and single interface MAC protocols.

There are mainly two categories of MAC protocols in the literature. The first one is based on the backoff mechanism: the protocol uses the contention window to modify the behaviour of the protocol. The use of the contention window can be a modification of the window size or of the way of increasing/decreasing it. The protocols that belong to this category are mainly based on the DCF of IEEE 802.11 for the medium access method. The second category consists of protocols that do not use the backoff algorithm to modify their behaviour. This does not mean that there is no backoff algorithm but the main changes and evolutions inside the protocol are not made via the backoff.

Backoff-based approach: The protocols in this category can be also divided into two classes. The first class, called BEB-like algorithms, contains the backoff algorithms that behave like the BEB algorithm: this means that, directly after a successful transmission, the contention window is decreased, and after a collision, the contention window is increased. The MILD (Multiplicative Increase Linear Decrease) algorithm [START_REF] Bharghavan | MACAW: a media access protocol for wireless LAN's[END_REF] and the DIDD (Double Increase Double Decrease) algorithm [START_REF] Chatzimisios | A simple and effective backoff scheme for the IEEE 802.11 MAC protocol[END_REF] belong to this category. Surprisingly, in the literature, most of these algorithms are mainly designed for single-hop networks, and very few of them are tested in ad hoc networks conditions.

The protocols of the second class modify the contention window based on some computations made by the station. These computations use some information gathered by each station from its neighbourhood. For example, in MB-FAIR [START_REF] Fang | Performance evaluation of a fair backoff algorithm for IEEE 802.11 DFWMAC[END_REF], the algorithm computes what the authors call a fair share and modifies the contention window size accordingly. The fair share is computed based on some information received from the two-hop neighborhood. The protocols described in [START_REF] Nandagopal | Achieving MAC Layer Fairness in Wireless Packet Networks[END_REF][START_REF] Luo | A new model for packet scheduling in multihop wireless networks[END_REF] also belong to this category.

Other approach or non backoff-based approach: In this category, there are also two main classes of protocols. The first class uses some information other than the one initially provided by 802.11. In the protocol EHATDMA [START_REF] He | Fairness of Medium Access Control Protocols for Multi-hop Ad Hoc Wireless Networks[END_REF], a handshake in EHATDMA can be initiated by the sender or the receiver. The protocols of this category use broad information to provide fairness for all stations.

The protocols of the second class do not use any extra information except the information gathered from the active carrier sensing mechanism. For instance, the protocols PNAV [START_REF] Chaudet | Adaptive Probabilistic NAV to Increase Fairness in Ad Hoc 802.11[END_REF] and MadMac [START_REF] Razafindralambo | Increasing Fairness and Efficiency using the MadMac Protocol in Ad Hoc Networks[END_REF] belong to this category. MadMac and PNAV insert a waiting time before sending a packet with 802.11. The waiting time is inserted depending on the activity perceived on the medium.

3 SBA: a Simple Backoff Algorithm We describe here some basic ad hoc configurations that present performance issues when 802.11 is used. These configurations are often sub-configurations of larger ad hoc topologies. We think that a good understanding of these basic scenarios is important because the rules of our algorithm SBA are based on these issues. We describe three configurations: hidden terminals, asymmetric hidden terminals and the three pairs.

a) The hidden terminals configuration is given on Figure 1(a): the two transmitters are independent and try to send packets to the same receiver. The collisions due to concurrent transmissions lead to a throughput degradation and a short term unfairness as described in [START_REF] Li | Modeling the Short-Term Unfairness of IEEE 802.11 in Presence of Hidden Terminals[END_REF]. The collisions may be reduced with the RTS/CTS mechanism of 802.11. b) The asymmetric hidden terminals configuration is given on Figure 1(b): the transmission of the upper emitter always collides and the transmission of the lower emitter always succeeds. This asymmetry leads to a long term unfairness between the two transmitters when 802.11 is used and the RTS/CTS mechanism does not solve the problem [START_REF] Bharghavan | MACAW: a media access protocol for wireless LAN's[END_REF]. c) The three pairs scenario is presented on Figure 1(c): there is no collision issue, but unfairness arises with 802.11 because the central pair cannot access the medium due to asymmetric contention [START_REF] Dhoutaut | Impact of Heavy Traffic Beyond Communication Range in Multi-Hops Ad Hoc Networks[END_REF].

Principles

In SBA, we keep the main principles of the MAC protocol of IEEE 802.11 DCF: a packet is emitted on the radio medium after a DIFS and a backoff time (during which the medium must be free) and in unicast mode, the data packet is acknowledged after a SIFS. The main differences between SBA and 802.11 are the number of backoff stages and the conditions that determine the contention window size to use. Due to space limitations, we do not describe IEEE 802.11 DCF (see [START_REF]Local and Metropolitan Area Network -Specific Requirements -Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF] for more details). Only two states. Compared to 802.11, SBA has only two different contention window sizes, one large called hereafter CW max and one small called CW min . Local information. Our protocol relies only on local information. What we mean by local information is information that a station can derive from its own experience without using any measure from the carrier sensing mechanism3 and without exploiting the content of the packets it receives nor the packets it can listen on the radio medium. Therefore the used information is collisions and successful transmissions undergone by the station, as done in the DCF mode. There are many advantages in using such local information. For example, such information is always available and reliable and if no message is exchanged the protocol overhead is reduced. Not using the carrier sensing mechanism, for computing the medium occupancy ratio for instance, can be also of some interest concerning the energy consumption. But using only local information has also some drawbacks. For example, when the number of stations is not known, it is difficult for the protocol to have an optimal behaviour. However locality is an important property for ad hoc networks protocols, especially for MAC protocols. How to use local information? The BEB algorithm of IEEE 802.11 is said to be aggressive due to the adaption of the contention window size after a successful transmission. Many BEB-like algorithms try to cope with this aggressive behaviour by a slow reduction of the contention window size. As SBA has only two distinct contention window sizes, we do not adapt the contention window size after each transmission, in order to reduce the oscillations between these two states. SBA uses the local information gathered during a given time interval to adapt the contention window for the next time interval. The length of this interval must not be too short to avoid possible oscillation and not be too long to increase the reactivity of the algorithm. The time interval used in SBA is fixed and the same for all stations. This interval is called ∆ hereafter.

Computing medium state probabilities. The medium can have different states. From the station point of view, the medium can be occupied by other stations, or occupied by its transmission resulting in a successful transmission or in a collision, or the medium can be idle. We denote the probability for the medium to be in each state by P [occ], P [suc], P [col] and P [f ree] respectively. These four probabilities cannot be accurately computed by using only local information as defined previously. However they can be approximated with this local information. The local information, known and used by a station, is the length and the time needed to transmit each packet. The value of P [suc] for a given interval is thus given by:

P [suc] = T suc ∆ (1)
where T suc is the time spent by a station in successful transmissions. In the same way, we can compute P [col] based on T col , where T col is the time spent by a station in collisions. Another local information used by a station is the number of successful transmissions and the number of collisions it undergoes during ∆, and denoted by N suc and N col (resp.). As SBA uses only one contention window size during a given time interval, it is possible to approximate, during a given ∆ and without sensing the medium, the period during which the medium is idle, denoted by P [f ree], by:

P [f ree] = (N col + N suc ) × (cw + DIF S) ∆ ( 2
)
where cw is the mean backoff time. This value is an approximation, because, we use the mean backoff time and because it only takes into account the free periods just before the transmissions. Based on previous equations, we can compute P [occ] by using the following relation:

P [occ] = 1 -(P [suc] + P [f ree] + P [col]) (3)
Note also that when the network is unsaturated, the value of P [occ] (P [f ree] resp.) is not the real occupation (idle period resp.) of the medium. This behaviour is due to the fact that the station does not use the carrier sensing mechanism to define free periods and thus occupation periods, but only local information. However, we will see that this approximation ensures good performances to SBA in unloaded networks.

SBA: the protocol

The code of SBA is presented in Algorithm 1. As we have only two states, the algorithm can be seen as the transition between these two states. Algorithm 1 shows how the statistics gathered during the ∆ period are used to switch from one state to another. Algorithm 1 consists of two main cases given in Line 1 and Line 9. If the condition of Line 1 is true, it means that the station's occupancy with successful transmissions is lower than the other stations' occupancy and then its contention window is set to CW min (Line 2), otherwise it is set to CW max (Line 10). This condition ensures that a node does not monopolize the medium as in, for instance, the three pairs or asymmetric hidden nodes scenarios. If a node thinks that it uses too much the radio medium, then it slows down its emissions by using CW max .

The condition of Line 1 does not take into account the medium load. The medium load is considered in the condition of Line 6 with two cases. If the Algorithm 1 SBA

1: if (P [suc] ≤ P [occ] + P [f ree]) then 2: CW ← CW min 3: if (P [col] > r && rand{0,1}=1) then 4: CW ← CW max 5: end if 6: if ((P [f ree] ≤ s && P [col] > 0) || (N suc + N col = 0)) then 7: CW ← CW max 8:
end if 9: else 10:

CW ← CW max 11: end if
medium is heavily loaded, then free periods are reduced and the collision probability is greater than 0 and/or the station can not access to the medium. When these two conditions are satisfied, the station uses CW max .

The condition of Line 3 uses a random variable to create asymmetry when the probability of collisions is greater than r. In this case, a random variable is drawn, and depending on its value, the contention window is set to CW max or left to CW min . When the collision probability is very high, it means that there is problem of symmetry in the network. This symmetry appears when the stations use the same contention window size, especially CW min . If these configurations lead to a high collision probability, this is probably due to the value of CW min which cannot solve the collisions. In this case, this random drawing tries to break the symmetry and divides by two the number of stations that can potentially use CW min , which may reduce the number of collisions in the next period. This condition should solve hidden nodes configurations.

Simulation results

In this section we present the simulation results of SBA. The simulations are realized on different ad hoc scenarios. We selected scenarios presented in the literature, most of them can be found in [START_REF] Chaudet | Performance Issues with IEEE 802.11 in Ad Hoc Networking[END_REF].

Simulation parameters

The simulations presented in this section were run with NS-2 [START_REF]The Network Simulator[END_REF]. We modified the simulator to reflect the DSSS modulation described in 802.11b. We also removed the overhead due to the routing protocol and the ARP protocol in order to better understand the behavior of SBA. Table 1 gives the summary of the simulation parameters we use by defaults 4 . These parameters are used in all simulations if changes are not specified.

We compare SBA to other MAC layer solutions, including the IEEE 802.11 DCF, MBFAIR [START_REF] Fang | Performance evaluation of a fair backoff algorithm for IEEE 802.11 DFWMAC[END_REF], PNAV [START_REF] Chaudet | Adaptive Probabilistic NAV to Increase Fairness in Ad Hoc 802.11[END_REF], MadMac [START_REF] Razafindralambo | Increasing Fairness and Efficiency using the MadMac Protocol in Ad Hoc Networks[END_REF] and DIDD [START_REF] Chatzimisios | A simple and effective backoff scheme for the IEEE 802.11 MAC protocol[END_REF]. These protocols belong to different categories of MAC protocols presented in Section 2. We also evaluate SBA when the ∆ periods of all the nodes are synchronized, called SBA sync hereafter. Of course, it is difficult to achieve such a synchronization in ad hoc networks, but this evaluation shows the upper bound on SBA performance. The studied results are the global throughput and the fairness of these protocols. The global throughput, i.e. the sum of the throughputs of all the stations, corresponds to the efficiency of the protocol. We measure fairness, according to the Jain fairness index defined in [START_REF] Jain | Throughput Fairness Index: An Explanation[END_REF]. When this index is close to 1, it means that the protocol is fair according to a fairness scheme. We use the Max-Min fairness scheme as a baseline comparison, as many studies on fairness in ad hoc networks do5 .

Performance results

Specific ad hoc scenarios

The 3 pairs The results of efficiency and fairness for the three pairs scenario, depicted in Figure 1(c), are given in Figure 2. In this scenario, the protocol is fair (under a Max-Min fairness scheme) when the throughputs obtained by the three pairs are roughly the same. This figure shows that the fairness index of SBA is close to 1, therefore SBA is fair, like MBFAIR, MadMac and PNAV. In this scenario, the three pairs alternate the use of CW min and CW max . This alternation allows the central pair to access the medium more often than with 802.11, which increases the throughput of the central pair and decreases the throughputs of the two external pairs. The flows throughput are roughly equal, which is not the case for 802.11 (or DIDD). On the other hand, the throughput reduction of the external pairs reduces the global throughput of the network. Therefore, SBA is less efficient than 802.11 (or DIDD).

We also see that MadMac has the better global throughput among the fair MAC protocols. This throughput is the maximum throughput that can be achieved under a Max-Min fairness restriction. This maximum throughput is achieved with MadMac by synchronizing the 3 pairs by using carrier sensing information. In SBA, we do not use such a synchronization scheme and we can see that the performance of SBA is smaller but not so far from the fair capacity. We can also notice that SBA is more efficient than MBFAIR and PNAV.

The hidden terminals Figure 3 shows the fairness index and the global throughput obtained in the hidden terminals scenario presented in Figure 1(a). As the stations have a symmetrical behaviour, the two stations have statistically the same behaviour (see [START_REF] Li | Modeling the Short-Term Unfairness of IEEE 802.11 in Presence of Hidden Terminals[END_REF] for more details). Thus, there is no long term unfairness issue with this scenario, as the different fairness indexes show. We can see from this figure that, when SBA is randomly asynchronous, the global throughput is roughly the same as with 802.11. But when the stations are fully synchronized, the global throughput of SBA is better than the throughput of 802.11 with or without the use of RTS/CTS mechanisms. The throughput of MadMac is better than the throughput of SBA, because MadMac synchronizes the hidden terminal by using the acknowledgement to identify the hidden terminals problem. Note that the performance of MadMac degrades when acknowledgements are not used. We show here that SBA can provide a good fairness-efficiency trade-off without any information. The asymmetric hidden terminals Figure 4 shows the simulation results on the asymmetric hidden terminals, given in Figure 1(b). We can see that when the stations are synchronized, the throughput of SBA is close to the throughput of 802.11 and the fairness index of SBA is close to 1, which means that the two emitters have roughly the same throughput. The figure also shows that even if the stations are not synchronized, the performances of SBA are either better or close to the performances of the other fair protocols. These good performances are due to the alternation between the use of the contention window sizes. Concerning 802.11 (or DIDD), it is more efficient than all the other tested protocols, but much less fair. Random topologies In this subsection, we present the results on random topologies. In these topologies, stations' positions are uniformly and randomly chosen in a square of 500m × 500m size. The communication range of the station is set to 150m. Sources and destinations of flows are also randomly chosen. It is worth noting that, in these simulations, the same topology and flows configuration are tested for each protocol. The results given in this section are thus topology dependent. Due to the random aspect of these scenarios, the performance metrics we use are different. For efficiency, we compute the global throughput of the network, the mean throughput of each flow and the corresponding 95% confidence interval. For fairness, we measure the min-max ratio which is the ratio between the minimum throughput achieved in the network over the maximum throughput. This metric has the advantage, compared to the usual variance, of being independent from the number of considered emitters and does not mask the situation in which a few stations are starved. If the minmax ratio is close to 1 this means that all emitters have the same throughput. If the minmax ratio is equal to 0, it means that at least one flow is starved in the networks. We also use the variation coefficient which gives the dispersion around the mean value. The variation coefficient is the ratio of the standard deviation over the mean. This metric is independent from the mean value unlike the usual variance. The higher the value of the coefficient, the higher the dispersion around the mean value. This metric gives an intuition on how the flows are distributed around the mean value. Figure 5 shows the simulations results in a random scenario with 200 stations and 150 flows. This figure shows that SBA is slightly more efficient than MadMac, PNAV and MBFAIR. We can also see that no flow is starved with SBA, unlike the other protocols for which the minmax ratio is equal to 0. The coefficient variation also shows that the dispersion around the mean throughput is smaller for SBA, which means that the flows' throughputs are close. This figure shows that in this case, SBA is the best trade-off between fairness and efficiency. To better see the difference between SBA and the other protocols, we plotted the distribution of the flows throughputs. Figure 6 shows the throughputs distribution of each protocol. The x-axis gives the throughput in kbps and the y-axis the proportion of flows that get this throughput. The size of each chart is equal to 3 kbps. We can see that with SBA, the number of flows that have a throughput close between 0 and 3 kpbs is less than 6%. Moreover, the minmax ratio tells us that no flow is starved with SBA. On the other hand, with 802.11, more than 28% of flows have a throughput between 0 and 3 kpbs. This value is more than 24% for PNAV and MBFAIR and more than 8% for MadMac. These charts also show that the difference between the aggregated throughputs of 802.11 and SBA comes from the fact that with 802.11 a little proportion of flows can get more that 1200 kbps. With SBA, there is no flow with such a throughput, the higher throughput is around 920 Kbps. One interesting point is that even if a small percentage of flows have a throughput around 1300 Kbps with MadMac, the global throughput of MadMac is lower than the SBA's one.

It is worth noting that we ran many other random simulations and the results are always the same. We mean here that SBA exhibits a good trade-off between fairness and efficiency among the tested protocols.

Complexity

The complexity of MAC protocols for ad hoc networks is hard to quantify. In this section, we define some parameters to quantify complexity and then we provide the measure of each indicator for the protocols we compare in the previous section.

Complexity parameters

(HD) History dependence: with this parameter, we try to provide the age of the information used by each protocol.

(Dist) Distance of information given in number of hops: it indicates the locality degree of the protocol. (E) Event: it indicates the event(s) from which the protocol reacts. We have identified different events: (a) successful transmission and/or collision: such an event gives, to a node, the status of the packet it has just sent; (b) carrier sensing detection; (c) reception of control packets: the protocol can use control packets to adapt its behavior; (d) reception of data packets from which the protocol can extract and use useful information like packet source, packet size, etc. (NV) Number of variables: we give here the maximum number of variables that are modified by a node after each different event given previously and used by the protocol.

Complexity results

Table 2 gives the complexity parameters for the MAC protocols we evaluate in Section 4. For the HD parameter, ǫ means that the history length is very short, i.e. the protocol adapts its behavior just after an event. For example, IEEE 802.11 DCF only needs the transmission status of the last sent packet. Stochastic process means that the history length depends on a stochastic process which can be probabilistically long even if it can only depend on the previous status of the protocol.

We give the NV parameter in respect to the format of the parameter (E): for instance (x a , x b ) for NV corresponds to at most x a modified variables after event (a) and x b modified variables after event (b) if E is denoted by (a,b). With 802.11, each node stops its backoff decrease after event (a) or changes its contention window size or not after event (b). When RTS/CTS are activated, these packets are also used to update the NAV, which corresponds to one variable modification after event (c). With SBA, T succ or T col and N succ or N col are updated after event (b). At the end of each interval, the four different probabilities, as the new contention window size, are computed, and ∆ is reset. This is denoted by 6 before each ∆ in the table. With MadMac, more variables are maintained and modified: after event (a), the backoff decrease is stopped, but some variables are updated to indicate the share of the medium as the status of a possible multiple hidden nodes configuration; after event (b), the contention window size may be updated, but MadMac also counts, via some variables, the number of collisions as the number of successive sent packets and infers, via other variables, whether the node is within a multiple hidden nodes configuration. At the end of the ∆ period, some of these variables are reset. With PNAV, a stochastic process is used to determine if the NAV is used or not. For that, different variables are updated after events (a,b). With MBFAIR, four variables are updated after event (b), (c) or (d): thanks to the sent packets or the received packtets, each node can compute its medium's occupancy of the medium, the medium's occupancy of the other stations, its fair share and the contention window size to use. With the receipt of RTS/CTS, each node can also update its NAV. It is difficult to order these algorithms in terms of complexity. It is clear the IEEE 802.11 without RTS/CTS uses very few information and very few variables. If we consider that the use of control packets introduces more complexity in the protocol than local operations, then SBA is rather simple and requires less variables than MadMac.

HD

Conclusion and future works

In this paper, we have presented a new backoff algorithm for ad hoc networks: only two contention window sizes are used and the choice of the contention window depends on computations based on local information only. Compared to existing backoff algorithms, SBA is designed for ad hoc networks. The results presented in this paper show that SBA is fairer than 802.11. Of course, the fairness induced by SBA reduces the global throughput (compared to 802.11), but this decrease is often lower than the one achieved by some other fair MAC protocols. Given the first obtained results, we think that SBA is a good candidate in terms of trade-off between fairness, simplicity and efficiency.

The next step of this work is to modify the value of each parameter of SBA such as CW min , CW max and the conditions presented in the algorithm to optimize the performances of SBA depending on the requirement of the networks.

3. 1 11 (

 111 Basic issues with 802.

Fig. 1 .

 1 Fig. 1. Basic configuration issues with IEEE 802.11 DCF

Fig. 2 .

 2 Fig. 2. Simulation results for the three pair scenario.

Fig. 3 .

 3 Fig. 3. Simulation results for the hidden terminals scenario.

Fig. 4 .

 4 Fig. 4. Simulation results for the asymmetric hidden terminals scenario.

Fig. 5 .

 5 Fig. 5. Simulation results for a random scenario with 200 stations and 150 flows.

Fig. 6 .

 6 Fig. 6. Throughputs distribution for a random scenario with 200 stations and 150 flows (throughput vs percentage of flows achieving this throughput).

Table 1 .

 1 Summary of the simulation parameters.

	SIFS	10µs	Routing protocol	static
	DIFS	50µs	∆	0.2s
	backoff slot	20µs	s	0.15
	CW min	31	r	0.5
	CW max	1023	Traffic	backlogged / CBR / UDP
	Physical header	192µs Packet size	random [600;1400] bytes
	Data rate	11 Mbps Synchronization	random
	ARP protocol	disabled Mobility	none
	Transmission range 100 m Carrier Sensing range	200 m

Table 2 .

 2 Complexity results.

			Dist	E	NV
	802.11	ǫ	∅	(a,b)	(1,1)
	802.11 (RTS/CTS)	ǫ	2	(a,b,c)	(1,1,1)
	SBA	∆	∅	(a,b)	(1,2) + 6 before each ∆
	MadMac	2 × ∆	∅	(a,b) (4,6) + 7 before each 2∆
	PNAV	stochastic process ∅	(a,b)	(2,6)
	MBFAIR	∞	2 (a,b,c,d)	(1,4,5,4)

Note that SBA uses the carrier sensing mechanism for accessing the medium to check whether the medium is free or not, but does not make any measure, as the medium occupancy ratio for instance, with this mechanism.

Due to space limitation, we do not discuss the possible values for the SBA parameters. The results are given with a single set of values.

The discussion on this choice is out of the scope of this article.