Keywords: optimization, benchmarking, black-box, software

user documentation for the Black-Box Optimization Benchmarking (BBOB) tools provided for the GECCO 2009 workshop of the same name.

Purpose

This document provides the user documentation for the Black-Box Optimization Benchmarking (BBOB) tools provided for the GECCO 2009 workshop of the same name.

Description of the Software

The software can be downloaded at: http://coco.gforge.inria.fr/doku.php?id=bbob-2009

It provides:

1. benchmark functions, coded in MATLAB/Octave and C, 2. a single generic function interface to the benchmark functions, coded in MATLAB/Octave and C, 3. the Python post-processing tool, 4. L A T E X files templates, and 5. the corresponding documentations.

The first two items are used to run black-box optimization experiments and generate data. The second two are used to obtain a workshop paper collecting the results from the experiments.

Running Experiments

A general description of the goals of the workshop, how to perform the experiments using MATLAB/Octave and the output data format can be found in [START_REF] Hansen | Real-parameter black-box optimization benchmarking[END_REF].

To run an experiment, an interface function, fgeneric, is provided which takes care of writing the output data and which can be used to gather further information on the current experiment (e.g., the current number of function evaluations).

Running Experiments in C

The interface to fgeneric differs from the MATLAB example given in [START_REF] Hansen | Real-parameter black-box optimization benchmarking[END_REF], we provide in Figure 1 the equivalent example script in C. A specific folder structure, described in Annex in [START_REF] Hansen | Real-parameter black-box optimization benchmarking[END_REF], is needed for running an experiment. This folder structure can be obtained by untarring the archive createfolders.tar.gz and renaming the output folder or alternatively by executing the Python1 module createfolders before executing any experiment program. Make sure createfolders.py is in your experiment working directory and from the command-line simply do: python createfolders.py PUT_MY_BBOB_DATA_PATH

; } printf("----dimension %d-D done ----\n", dim[idx_dim]); } return 0; } RT n°0372
To list other differences between the MATLAB and C code, calls to fgeneric specified by a string first argument in MATLAB, are replaced by fgeneric string in C, e.g. fgeneric('ftarget') is replaced with fgeneric ftarget. Also, the generic call to fgeneric(X) to evaluate candidate vectors is replaced by fgeneric evaluate(double * X) for a single vector and fgeneric evaluate vector(double * XX, unsigned int n, double * result) for an array of vectors where XX is the concatenation of the n candidate vectors and result is an array of size n which contains the resulting function values.

Collected Data

If run correctly, the data for an experiment will be located in a folder that we will call DATAPATH in the following. The post-processing tool described in Section 4 takes DATAPATH as input argument and will recursively look for '.info' files which contain the necessary information about the experiments, see Appendix E in [START_REF] Hansen | Real-parameter black-box optimization benchmarking[END_REF].

Generate the Workshop Paper

The post-processing tool bbob pproc generates image files and L A T E X tables from the raw experimental data obtained as described previously in 3. These files and tables will be a part of your workshop paper. The workshop paper itself is composed of the description of your algorithm, any additional information you feel necessary to describe your experiments, and the aforementioned results from the post-processing procedure. To ease the procedure of writing the paper we include a L A T E X template for each testbed within the provided software.

The entire post-processing tool is written in Python and requires Python to be installed on your machine. The minimal software requirements for using the post-processing tool are Python (2.5.2), Matplotlib (0.91.2) and Numpy (1.0.4). In the following, we explain how to obtain and install the required software for different systems (Linux, Windows, Mac OS) and which steps you have to perform to run the post-processing on your data.

Installing the Software

While the bbob pproc source files are provided, you need to install Python and its libraries Matplotlib and Numpy. We recommend using Python 2.5 and not a higher version (2.6 or 3.0) since the necessary libraries are not (yet) available and the code is not verified. For all operating systems the packages can be found at the following locations: Python: http://www.python.org/download/releases/2.5.4/, Numpy: http://sourceforge.net/projects/numpy/, Matplotlib: http://sourceforge.net/projects/matplotlib/.

We recommend the use of the latest versions of Matplotlib (0.98.5.2) and Numpy (1.2.1).

INRIA

Linux

In most common Linux distributions Python (but not Numpy or Matplotlib) is already part of the installation. If not, use your favorite package manager to install Python (python), Numpy (package name: python-numpy) and Matplotlib (package name: python-matplotlib) and their dependencies. If your distribution and repositories are up-to-date, you should have Python 2.5.2, Matplotlib 0.91.2 and Numpy 1.0.4. Though those are not the most recent versions of each package, they meet the minimal software requirements to make the BBOB software work. If needed, you can alternatively download sources and compile binaries. Python and the latest versions of Matplotlib and Numpy can be downloaded from the links in Sect 4.1. A dependency for the Linux version of Matplotlib is libpng, which can be obtained at http://www.libpng.org/. You will then need to properly install the downloaded packages before you can use them. Please refer to the corresponding package installation pages.

Windows

For installing Python under Windows, please go to the Python link in Sect 4.1 and download python-2.5.4.msi . This file requires the Microsoft Installer, which is a part of Windows XP and later releases. If you don't have the Microsoft Installer, there is a link for the download provided at the same page. After installing Python, it is recommended to first install Numpy and then Matplotlib. Both can be installed with the standard .exe files (respectively numpy-1.2.1-win32-superpack-python2.5.exe and matplotlib-0.98.5.2.win32-py2.5.exe). These files can be obtained from the provided SourceForge links in Sect 4.1.

Mac OS

Mac OS X comes with Python pre-installed, the version might be older than 2.5 though. It is recommended to upgrade Python by downloading and installing a newer version. To do this, if you have Mac OS X 10.3 and later you can download the disk image file python-2.5.4-macosx.dmg containing universal binaries from the Python download page, see Sect 4.1. More information on the update of Python on Mac OS can be found at this location: http://www.python.org/ download/mac/6 . Open the disk image and use the installer7 You will then need to download and install Numpy and Matplotlib from the SourceForge links listed in Sect 4.1.

Using the bbob pproc Package

When you have obtained experimental data and want to perform the postprocessing you will need to download and un-archive the bbob pproc package on your system. The package can be obtained from http://coco.gforge.inria.fr/doku.php?id=bbob-2009. Then, to post-process the data, make sure the data folder DATAPATH generated by your experiments is in the current working directory and execute: python path_to_postproc_code/bbob_pproc/run.py DATAPATH from a shell or the command window (Windows). Note that in Windows the path separator '\' must be used instead of '/'. The folder path to postproc code is the one where the provided post-processing software was un-archived. The above command will create the folder ppdata in the current working directory, which will contain the post-processed data in the form of figures and L A T E Xfiles for the tables. This process might take a few minutes. If the verbosity is off (default), you will only get the following message to indicate that the postprocessing is finished:

Output data written to folder ppdata.

If you are familiar with Python and want to run the post-processing directly from a Python shell you have to execute:

>>> import bbob_pproc >>> bbob_pproc.main('DATAPATH')

This first command requires that the path to bbob pproc is in the Python search path. The resulting ppdata folder now contains a number of T E X, eps, png files.

Help for the bbob pproc Package

Additional help for the bbob pproc package can be obtained by executing the following command in a shell: python path_to_postproc_code/bbob_pproc/run.py -h This will give a short summary of the package and additional options for executing the post-processing. The code documentation can be found in the folder path to postproc code/pydoc within the provided software package. It gives a detailed explanation of the Python code.

Using the L A T E X Templates

The files templateBBOBarticle.tex and templateBBOBnoisyarticle.tex are provided. If compiled correctly using L A T E X, they will generate documents collecting and organizing the output from the BBOB post-processing tool. Each of the templates has a given page organization optimized for the presentation of the results for a each testbed. In the case that you have results on both testbeds, we recommend that you generate and submit two separate documents.

To compile a document, you need to make sure that:

1. you have a working L A T E X distribution on your computer 8 , 2. you are in the working directory (containing the folder ppdata containing all the output from the BBOB post-processing tool), 3. templateBBOBarticle.tex 9 , bbob.bib and sig-alternate.cls are in the working directory (all files are provided with the software),

Then, simply execute: latex templateBBOBarticle bibtex templateBBOBarticle latex templateBBOBarticle latex templateBBOBarticle in a shell or open the chosen template file in your favorite L A T E X editor and compile it with the L A T E X option. The document templateBBOBarticle.dvi will be generated in the format required for a GECCO workshop paper. Now you need to complete this document by filling and adding in the template file all the meta-information that is needed, your own information as author, a complete description of your algorithm and a description of how you chose your algorithm parameters (see also [START_REF] Hansen | Real-parameter black-box optimization benchmarking[END_REF]). As for your bibliographical references you can either add your references to bbob.bib or include your bib-file in the bibliography-statement at the end of the template file. Please refer to http://www.sheridanprinting.com/typedept/gecco3.htm and http://www.acm.org/sigs/publications/sigguide-v2.2sp for more details on the formatting of your L A T E X document.

Figure 1 :

 1 Figure 1: exampleexperiment.c: example for benchmarking MY OPTIMIZER on the noise-free function testbed in C.

RT n°0372

To install Python, please refer to 4.1.INRIA

The discussion over IDLE for Leopard user (http://wiki.python.org/moin/MacPython/ Leopard) is not relevant for the use of bbob pproc package.

Following this step will leave the pre-installed Python on the system and install the MacPython 2.5.4 distribution. MacPython contains a Python installation as well as some Mac-specific extras.RT n°0372

http://www.latex-project.org/ INRIA

http://www.inria.fr ISSN 0249-0803

Acknowledgments

Steffen Finck was supported by the Austrian Science Fund (FWF) under grant P19069-N18. The BBOBies would like to acknowledge Miguel Nicolau for his insights and the help he has provided on the implementation of the C-code.


Georges Daufin

Jean-François Radenac

Geneviève Gésan-Guiziou

François-Louis Kerhervé

Olivier Le Berre

Françoise Michel

Uzi Merin

A Novel Rig Design for Ultra-and Microfiltration Experiments

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Shandipsing Robee
email: shandipsing.robee@thalesgroup.com

Anne-Charlotte Amiaud
email: anne-charlotte.amiaud@thalesgroup.com

J P Coupez
email: jp.coupez@imt-atlantique.fr

Thomas Merlet
email: thomas.merlet@thalesgroup.com

Mutual coupling reduction through choke structures in a Slotted Waveguide Antenna Array

Keywords: Direct Metal Laser Sintering (DMLS), Mutual coupling reduction, Slotted Waveguide Antenna Array (SWAA), Choke, 3D printing

This article presents a comprehensive study on reducing mutual coupling in a slotted waveguide antenna array (SWAA), operating in the X band. The objective is to limit such parasitic coupling effects on radiation pattern performances. Optimised choke structures are inserted between adjacent slots sub-arrays in order to control surface currents distribution. Simulation results exhibit a remarkable reduction on isolation between adjacent waveguides. This induces an overall performance improvement in terms of main beam and side lobes control. Furthermore, using field calculator on HFSS™, the efield levels of each slot are extracted. The plus points and drawbacks of the choke structure on the radiation pattern are then explained.

I. INTRODUCTION

In modern adaptive radar applications, mechanical beam steering antenna arrays have been replaced by Active Electronically Scan Array (AESA), offering improved performances (compactness, beam-scanning...) [START_REF] Skolnik | Radar Handbook, Third Edition, ser. Electronics electrical engineering[END_REF]. In AESA structures, slotted waveguide antenna [START_REF] Elliott | The design of small slot arrays[END_REF] arrays have been widely used instead of planar arrays as they offer low-loss structures and can handle high power levels [START_REF] Da Costa | A dual-band slotted waveguide antenna array for radars applications[END_REF].

SWAA were initially fabricated through conventional metal machining process, with drawbacks (cost, limited geometrical complexity...) [START_REF]Waveguide slot array antenna with a hybrid-phase feed for grating lobe reduction[END_REF]. Additive manufacturing techniques like 3D printing and Direct Metal Laser Sintering (DMLS) have made accessible low-cost prototyping with enhanced complexity [START_REF] Guennou-Martin | Design and manufacturing of a 3-d conformal slotted waveguide antenna array in ku-band based on direct metal laser sintering[END_REF].

Beamforming capabilities in AESA generate compactness constraints, regarding the number of radiating elements to be used to create beam diversity. This inevitably increases interferences between adjacent slotted waveguides structures due to proximity effects and mutual coupling affecting performances in terms of radiation characteristics [START_REF]A 3D-Printed Coaxial-fed Waveguide 2-Slot Array for an AESA Radar Application in the Ku-band[END_REF].

This work proposes an optimised choke structure in order to reduce mutual coupling and to increase isolation levels between adjacent slotted waveguides. The objective of this paper is to underline the success of the proposed choke structure on mutual coupling reduction while also highlighting its impact on radiation pattern properties. This is done by displaying the electric field on each slot while simulating the structure on HFSS™. An analysis of the radiation pattern and electric field level is then done, with and without the choke structure.

II. THEORICAL BACKGROUND

A quarter wavelength groove called choke, as shown in figure 1, is often used as a decoupling option [START_REF] Kimura | Alternating-phase fed single-layer slotted waveguide arrays with chokes dispensing with narrow wall contacts[END_REF], [START_REF] Ogiwara | 2-D MoM Analysis of the Choke Structure for Isolation Improvement between Two Waveguide Slot Array Antennas[END_REF], providing a practical and efficient solution to mitigate mutual coupling effects.

Figure 1: Choke between two adjacent slotted waveguides

The choke structure is equivalent to a short-circuited quarter wavelength stub, between a load and a source, used in transmission lines theory in order to reduce an impedance mismatch [START_REF]Book : Impedance matching using single stubs[END_REF].

It means that, when a groove of length λ0/4 is applied between two adjacent slotted waveguides, its upper region will be an open circuit with an infinite impedance. In reality, the impedance will be very high but not infinite. Having a very high impedance on the choke upper part will prevents the flow of surface currents, hence reducing mutual coupling between adjacent waveguides.

III. VERTICAL SLOTTED WAVEGUIDE DESIGN AS A GROOVE

Usually, the quarter wavelength groove is carved directly in a piece of metal using traditional metal machining process. Those process have some limits. For example, when using a drill to carve the choke, its bottom is not a perfect rectangle but rounded. This can modify the short-circuit property of the choke structure and make it less efficient. Moreover, in our w ≈λ0/4 case, the choke has reduced dimensions, typically a width (w) of 1 mm large and a depth ( ) of 7.5 mm. Drilling such a small groove with precision can be quite complex and costly. The groove can also present some manufacturing irregularities along its length.

To overcome those hurdles, we have investigated an alternative approach to integrate such choke structures exploiting DMLS printing technology. The overall structure, including the choke and the adjacent waveguides can be printed at once. By this means, a high-quality complex structure of the slotted antenna array can be designed under low cost processing considerations. The design of the slotted waveguide array antenna is composed of 3 waveguides, each containing 4 radiating slots as shown in the figure 2. The slotted waveguide antenna array and the choke structure are optimised for an X-band antenna array. With the use of the choke structure, the isolation between adjacent waveguides is improved, leading to an enhancement in the overall performance of the antenna array.

To evaluate the efficiency of the proposed choke configuration and its influence on the radiation pattern, simulations using HFSS™ software were conducted. The effect of the choke structure on the mutual coupling are often monitored by observing the Scattering parameters [START_REF] Daggula | Flange Effect Minimization and Antenna Isolation Improvement Using RF Choke in Slotted Waveguide Array Antenna[END_REF].

In the following section, the central waveguide of the three parallel sub-linear-array (each containing 4 radiating slots) is fed and the mutual coupling on the other two waveguides is observed in figure 3.

Figure 3: S parameters of a 3*4 SWAA centre fed

Without the choke, the reflection coefficient (S22) has a value of -22.2 dB (@ 9.82 GHz) and the isolation coefficients are at -17.3 dB (@ 9.82 GHz).

Adding the choke cause the reflection coefficient to decrease to -24.0 dB (@ 9.78 GHz) and the isolation coefficients to reach a value of -25.9 dB (@ 9.78 GHz). It means that only a small part of the mutual coupling occurs after adding the quarter wavelength groove. The low frequency shift of 40 MHz (from 9.82 GHz to 9.78 GHz) can be easily overcome by adjusting the antenna dimensions.

The antenna bandwidths are defined as the frequency ranges in which the reflection coefficients are lower or equal to -10 dB. It can also be noted that the introduction of the choke induces an increase of the bandwidth, from 120 MHz to 160 MHz (@ S22 value -10dB). This can be explained by the fact that the central fed waveguide is disturbed by the mutual coupling from the two unfed waveguides. One of the consequences is that its input impedance is altered, which in results diminishes its bandwidth. When the chokes are added, they reduce the surface current between adjacent waveguides. Thus, the input impedance of central waveguide is less affected leading to an increase in bandwidth and an increase in the isolation.

The mutual coupling can be observed qualitatively by observing the surface current distribution on the antenna array (Figure 4). On figure 4-a In zone "a", the E plane is more directive along the axis with the choke. The choke makes the radiation more effective in the desired radiation plane, that is, perpendicular to the SWAA plane.

Similarly, in zone "d", the E plane back lobe decreases from -8 dBi to -16 dBi. The choke prevents most the surface current overflow towards the back of the SWAA. This is mainly due to a reduction of undesired currents in the external parts of the slots reference ground plane (i.e. the upper face or the metallized aligned waveguide), with therefore a reduced contribution of the different discontinuities (corners of the waveguides) in the backward radiation.

The positive influences of the choke on the H plane are: a. In zone "a", the gain increases from 13 dBi to 14 dBi b. In zone "b", first side lobes are decreased by 5 dB on the left and by 3 dB on the right c. In zone "c", second side lobes are decreased by 2 dB on the left and by 1 dB on the right d. In zone "d", the back lobe is decreased by 8 dB.

At a quick glance, we can rapidly conclude that the overall radiation pattern has been improved by the addition of the choke. But, if we look closely at the curves some issues can be identified, mainly in the H plane (red curves).

The negative consequences of the choke on the H plane (red full line curves) are: a. In zone "a", the H plane becomes less directive. That is the main lob is larger with the choke than without. b. In zone "b", we can observe some dissymmetry.

The left and right side of the first side lobe are not equal. It can be explained that the weightings on each slot in the fed waveguide are no more equal. c. A dissymmetry is also noticed in zone "c" after the choke was added.

Normally, it was not expected that the choke will have such a significant influence on the H plane. We can suppose that the weights and the phases of the field distribution on each slot of the central waveguide are change in the presence of the choke. This alteration does not allow correct summation required to have a symmetric radiation pattern.

The above phenomenon can also qualitatively be observed when looking at the surface currents on the top of SWAA while varying the phase of the field distribution of the slots in the central fed waveguide from 0° to 360° (figure 6). Without the choke, when the phase of the slots field distribution on the central fed waveguide is varied from 0° to 360°, all 4 slots (slot1a, slot2a, slot3a and slot 4a) lights up and turn off at the same time. It means they are in phase and the weights for the 4 antennas are equal.

With the choke, when the phase of the E-field is varied from 0° to 360°, we can observe that Slot 1b and Slot 4b, resonate together but not at the same time as Slot 2b and Slot 3b. Slot 2b and 3b, light and turn off at the same time. To summarise, Slots 1b/4b and Slot 2b/3b are out of phase in the presence of the choke. This phenomenon was not expected. Normally, no changes were expected on the fed waveguide as with and without the choke the feeding, position of the slots and general configurations stayed the same. Till now, the observation was made only qualitatively. In order to better understand the phenomenon, we need to know the impact of the choke on amplitudes and phases distributions in each slot.

VI. ON SLOT LOCAL DISPLAY OF THE ELECTRIC FIELD

The local E-field display is done by adding a "polyline" together with the use of field calculator. The polyline acts as a probe during simulations on HFSS™ when placed on each slot antenna centre phase as shown value is then calculated using the field calculator with the appropriate equations on HFSS™.

Figure 7: Probes on the centre phase of each slot antenna

The n° 8 picture depicts the SWAA without the choke.

Figure 8: E-field phase and amplitude on each slot without choke

The graphs show the variation of the electric field with the phase of the slots on the SWAA without the choke.

Figure 8-A shows the centre fed waveguide (waveguide 2). It can be observed that all four slots present on this waveguide are in phase and have equal field amplitude of 15,000 V/m. It means that the weighting on those slots are equal. To obtain a radiation pattern, the weights of the four central waveguides are added. The result is the red dotted H plane radiation pattern present in figure 5. As all weights are equal and have the same phase, the resultant radiation pattern is symmetric.

Figures 8-B (waveguide 1) and 8-C (waveguide 3) show the unpowered couple waveguides. The maximum field amplitude on each slot of those two waveguides is around 5000 V/m. Here we have the evidence of mutual coupling between adjacent waveguides in SWAA as only the centre waveguide is fed here.

In figure 8-B, slot 2 and slot 4 have the highest E-field levels as they are closer to the central fed waveguide. Slot 2 level is higher than slot 4 as it is surrounded by slot 1 and 3. While slot 4 is at the end of waveguide 1. It only one slot close to it.

A similar observation is made in figure 8-C. Slot 1 and Slot 3, have the highest levels as they are closer to the central fed waveguide. Slot 3 E-field level is higher than slot 1. This is because slot 1 is at the start of waveguide 1 and has only one slot close to it. The graphs show the variation of the electric field with the phase of the field distribution in each slot.

Figure 9-A show the centre fed waveguide. We can already observe that the electric field amplitudes on the powered waveguide have been altered by the presence of the quarter wavelength groove. Going from 15000 V/m to 12500 V/m on the top and from -15000 V/m to -6000 V/m. This means that the weight attribution to each of the individual antenna is no more perfect. Additionally, we can observe an offset on the graphs. Investigation is still going on to know why the addition of the choke causes this offset.

Furthermore, we can remark that Slots 1b/4b and Slot 2b/3b are out of phase by 10° in the presence of the choke. The fact that all the slots are no more in phase was qualitatively observed in Part 5. This leads to an inefficient recombination of the individual slot weightings causing a dissymmetry in the radiation pattern. We suppose that this snag can be overcome by slightly readjusting the positions of slot 2b and slot 3b in terms of alignment and distance between phase centres. Research is still going on to confirm this supposition. divided by 5. We can now say that the presence of the choke reduces the mutual coupling by 5.

Now considering Figures 9-B

Here the same curves offsets are observed. An inquiry is still going in order to better understand those observations.

VII. OUTLOOK AND CONCLUSION

This paper makes a complete investigation on the effects of adding a choke structure on a SWAA. It also explains how the choke is used to reduce unwanted parasitic coupling in a SWAA design. Then with the help of a new methodology of e-field calculation with the help of probes on HFSS™ show the plus points and drawback of the choke structure.

The knowledge of the in detailed functioning of choke structure helped us to readjust and optimise our design further. Once the chokes added, the slots position can be modified to put the right weighting on each of them. Our final structure will be composed of a double choke structure decreasing the mutual coupling by 1 or 2 more dB.

Figure 2 :

 2 Figure 2: Slotted waveguide antenna array, with and without choke

  , (no choke), high current leakage can be spotted on the unfed waveguides. Adding the optimised choke structure decreases drastically those leakages (fig 4-b).

Figure 4 :Figure 5 :

 45 Figure 4: Centre fed SWAA: Surface current leak on the upper metallic plane V. CHOKE EFFECT ON THE RADIATION PATTERN Most publications in the literature shows only the positive mutual coupling reduction impact of the choke. The decoupling ability of the choke is only shown globally in terms of S parameters. With such information, it is almost impossible to analyse properly the effects of the choke. The only way possible to have a good visualisation is to displaywhat is happening locally on each slot, before and after adding the choke. In this section, the positive influence of the choke will be underline, as well as its drawbacks, on the radiation pattern and the waveguide slots antenna's weightings.In order to facilitate the explications, the radiation pattern is divided into 4 zones: a, b, c and d on figure5. The E planes curves are blue and the H plane curves are red. The dotted lines represent the SWAA without choke and the full lines with choke.

Figure 6 :

 6 Figure 6: Centre fed SWAA: Surface current leak on the upper metallic plane at a particular phase (0°).

Figure 7 .

 7 The electric field

Figure 9

 9 Figure 9 illustrate the SWAA in the presence of chokes.

Figure 9 :

 9 Figure 9: E-field phase and amplitude on each slot with choke

  and 9-C, we can notice that the electric field coupled on the unpowered waveguide has drastically decrease. The level falling from a 5000 V/m in the upper part to 1500 V/m and from 5000 V/m in the lower part to 500 V/m. The average coupled electric field have been Probes


Keywords: wireless network, transmission scheduling, interference, distributed algorithm, stability. INRIA réseau sans-fil, ordonnancement des transmissions, interférences, algorithme distribué, stabilité

stability under Markovian assumptions. Finally the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes.

Introduction

Transmission scheduling is a main problem in telecommunication networks. It has received a lot of attention both for wired and for wireless networks (radio, ad hoc, sensor network). In a wireless network a difficulty comes from interference problems. During a step or time slot, only transmissions which do not interfere can be scheduled. In this paper we consider any binary interference model. However for computations, examples, and simulations, we will use the so called d-interference model, where two transmissions which are within some interference distance d from each other interfere. In the particular case d = 0 (see [START_REF] Mazumar | Maximum weighted matching with interference constraints[END_REF]), we have the primary node interference model, where two transmissions interfere if their links intersect (one node can communicate with at most one another node); therefore, a set of transmissions can be activated together in the same time slot only if they form a matching in the corresponding undirected graph. The case d = 1 is known as the 802.11 interference model or distance-2 matching problem (see [START_REF] Balakrishnan | The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks[END_REF][START_REF] Bonifaci | Graphs and Algorithms in Communication Networks, chapter Data Gathering in Wireless Networks[END_REF][START_REF] Kumar | End-to-end packetscheduling in wireless ad-hoc networks[END_REF][START_REF] Wan | Multiflows in multihop wireless networks[END_REF]): here two links interfere if the first one contains a vertex adjacent to one of the second link. In that case a set of non interfering transmissions form an induced matching (see examples for d = 0 in Figure 3(a) and for d = 1 in Figure 3(b)).

The traffic is single-hop and the arrival process to each link of the network is assumed to be stochastic, with characteristics not necessarily known by the network designers. The goal is to schedule active links at each step in order to insure the stability of the system and, in particular, to activate links which are the most loaded. In the primary node interference model this corresponds to finding a maximum matching or a large matching. Centralized algorithms have been proposed to solve this problem both for random arrivals in [START_REF] Tassiulas | Scheduling and performance limits of networks with constantly changing topology[END_REF][START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[END_REF] and deterministic arrivals in [START_REF] Klasing | On the complexity of bandwidth allocation in radio networks[END_REF]. As example, if the network is a square grid of 4 nodes (Figure 1) with the primary node interference model (d = 0), we can activate at one step either vertical links (Figure 1(a)) or horizontal links (Figure 1(b)). It is also possible to have a single active link in the network but we consider only the two previous sets of active links (maximal sets). A good scheduling algorithm has to insure the stability of the system (stability of the four queues associating to the four links in Figure 1). For example if the capacity of each link is 1 (if a link is active during a step, it sends 1 message), and if the average number of arrival messages per step is A v = 2 7 for the two vertical links and A h = 4 7 for the two horizontal links, we get a simple scheduling algorithm for the system. Indeed if we choose to activate vertical links 5 steps over 14 and activate horizontal links 9 steps over 14, we get trivially the stability of the queueing system because A h < 9 14 and A v < 5 14 . Since arrival processes are not necessarily known a priori by network designers, thus in practice algorithms have to compute the set of active links as a function of current and past arrivals. However only distributed algorithms with limited local knowledge can be used. Indeed, centralized algorithms are based on a total knowledge of the network (i.e. link backlogs) at each step, an information which is very difficult to acquire because of the interference. Actually, acquiring this information is at least as much complicated than solving the scheduling problem. In addition, for the sake of energy saving, decisions have to be made locally, without exchanging messages with a central station. In [START_REF] Brzezinski | Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach[END_REF][START_REF] Eryilmaz | Polynomial complexity algorithms for full utilization of multi-hop wireless networks[END_REF][START_REF] Modiano | Maximizing throughput in wireless networks via gossiping[END_REF] distributed algorithms are described but they all lead to communication overheads which increase with the size of the network. In particular [START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF] presents a distributed algorithm valid for any binary interference model but at the expense of a non-constant overhead (increasing with the size of the network). The need for distributed algorithms with a small constant overhead has been emphasized in [START_REF] Sanghavi | Distributed link scheduling with constant overhead[END_REF][START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], where a distributed algorithm with a constant overhead depending on the quality of the desired approximation is described; however it is only valid for the primary node interference model (d = 0). Recently, in [START_REF] Rajagopalan | Network adiabatic theorem: an efficient randomized protocol for contention resolution[END_REF] a randomized (aloha-like) contention resolution protocol was proposed that is conjectured to be throughput optimal.

It is worth noting that in the general case (i.e. interference model different from the primary node interference model) the problem of finding a set of links fulfilling the interference constraints and maximizing the sum of the weights (i.e. the total backlog on the links) is NP-Complete. For instance the problem of finding a maximum induced matching in a graph (case d = 1 in the d-interference model) is NP-Complete [START_REF] Stockmeyer | Np-completeness of some generalizations of the maximum matching problem[END_REF][START_REF] Cameron | Induced matchings[END_REF] and it remains NP-Complete even for very special graphs (for 3-regular planar graphs for instance). Furthermore it is proved in [START_REF] Orlovich | Approximability results for the maximum and minimum maximal induced matching problems[END_REF] that the problem of finding a maximum induced matching in a graph cannot be approximated in polynomial time within a factor of n 1 2 -c for any constant c > 0 (unless P = N P ), where n is the number of vertices in the graph (associating to the network).

Under these considerations, we make the following contributions to the general problem:

• We design the first, to our knowledge, distributed transmission algorithm which holds for any binary interference model while simultaneously having a communication overhead independent of the network size (Section 4). • We formally prove properties of our algorithm and compute design tradeoffs. In particular, our overhead grows logarithmically with the maximum degree 1 of a node in the network and requires no explicit knowledge of queue size information between nodes (Section 5).

• We characterize the stability region of our algorithm under standard Markovian assumptions (Section 6) and validate our design via simulations (Section 7).

• Finally, we propose extensions to our algorithm in the multi-hop case (Section 8).

We begin by describing our model and some related work in the next two sections.

Modeling

We model the network by an undirected transmission graph G = (V, E), where there is an edge (link) e = uv ∈ E between two nodes u ∈ V and v ∈ V if they can communicate. We suppose that the relation is symmetric that is if u can transmit a packet to v, then v can transmit a packet to u and also that during a transmission both links are used as there are acknowledgment messages; so we have a symmetric directed graph; but for simplicity we use the undirected associated graph.

Interference can be modeled in different ways. We can use SINR (Signal-to-Interference-Noise Ratio) models [START_REF] Chen | A queue-aware scheduling algorithm for multihop relay wireless cellular networks[END_REF] but that makes both the algorithms and the analysis hard. We choose to use a binary symmetric interference model like in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF][START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF][START_REF] Wan | Multiflows in multihop wireless networks[END_REF]. We define the interference set of a link e ∈ E, denoted by ε(e), as the set of edges interfering with e. Our algorithm is valid for any set ε(e), but in the computations, examples, and simulations, we use a model based on an interference distance d ≥ 0 as follows. Two edges interfere if one vertex of the first edge is 1 From a practical standpoint, this presents a more attractive design tradeoff since node degree is bounded by physical layer characteristics whereas the network size can be unbounded.

INRIA

= (u 1 , u 2 ) ∈ E is ε(e) = {(v 1 , v 2 ) ∈ E, ∃i, j ∈ {1, 2}, d(u i , v j ) ≤ d}, where d(u, v)
is the distance between u and v in G, that is the length of a shortest path between these two nodes in G. Two examples of interference sets are represented in Figure 2 for the two interference models defined by d = 0 and by d = 1. We suppose that time is slotted and synchronized in the network. Our algorithm consists, like in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF][START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF], of a sequence of steps or time slots, all of the same size. One step contains two different phases: a control phase itself divided into mini-slots which consists of finding a valid set of active links for the sending (second) phase. We will say that a set of active links at step t ≥ 1 is valid if the edges activated during this step do not interfere. The interference model defined by d = 0 is a particular case, commonly used, and it is known as the primary node (or node exclusive) interference model. In that case two edges interfere if they are incident and a valid set of active links, at some step, is a matching of the transmission graph G. The case d = 1, more realistic, is known as the 802.11 interference model. In that case two nodes can exchange data only if their neighbors are not involved in a communication. Said otherwise a valid set of active links is what is called an induced matching of G. Two examples of sets of active links are represented in Figure 3 for a square grid graph (network) of 16 nodes for interference models defined by d = 0 (Figure 3(a)) and defined by d = 1 (Figure 3(b)).

We introduce for each edge e ∈ E of the transmission graph G = (V, E) and for each step t ≥ 1, the variable a t (e) such that a t (e) = 1 if edge e is an active link, allowed to send data during step t (a t (e) = 0 otherwise). The interference constraints imply that ∀e, e ∈ E, if a t (e) = a t (e ) = 1, then e / ∈ ε(e) (and e / ∈ ε(e )). Otherwise there are interference problems and so messages are not received correctly.

Traffic is dynamic and is assumed in this article to be single-hop, like in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], that is to say one packet sent through a communication link leaves the network just after. However we can deal with multi-hop traffic with few changes in our algorithm (see Section 8). To each edge (link) e ∈ E is associated a queue. We denote by q t (e) the number of messages in the queue of link e ∈ E at the beginning of step t ≥ 1. We will say that the weight of e at step t ≥ 1 is q t (e). At each step, new packets arrive in the links of the network (edges of the transmission graph) according to some arrival processes. These ones are specific to each link e ∈ E and not necessarily known by the designers of the network. Let A t (e) be the number of packets arriving in edge e ∈ E during step t ≥ 1. The capacity of an edge e ∈ E, denoted by c(e), is the number of packets that e can serve during one time slot t ≥ 1 if the link is active (that is if a t (e) = 1). Thus we have q t+1 (e) = (q t (e) -a t (e)c(e)) + + A t (e) with (y) + = max(y, 0).

Previous Works

We briefly describe in this section two algorithms respectively proposed in [START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF] and [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF] because we use the same modeling. They are both distributed but the algorithm in [START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF] does not admit a constant overhead, whereas the one described in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF] is valid only for the primary node interference model (d = 0).

In the algorithm described in [START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF], for each step t ≥ 1 there are a control phase and a data phase, like in our modeling (Section 2). Before each control phase, composed of T mini-slots, each edge e ∈ E is undetermined, and chooses a backoff value t(e), 1 ≤ t(e) ≤ T . In this context undetermined means that the edge does not know if it will be active or inactive during the data phase of the current step. If edge e receives a message (from an edge in ε(e)) during a mini-slot t, 1 ≤ t ≤ t(e) -1, then e is inactive. Otherwise e sends a control message during mini-slot t(e) and if it does not receive a message, then e is active (e is inactive otherwise). At the end, a valid set of active links is computed, allowed to send messages during the data phase. This simple algorithm is valid for any interference set, but the choice of the backoff value t(e), for any edge e ∈ E, is a function of the weights of edges located in its interference set ε(e) and function of the weights of edges located in interference set of each e ∈ ε(e). More precisely t(e) depends on the weights of edges belonging to the following set S = {e , e ∈ ε(e)} ∪ {e , e ∈ ε(e ), e ∈ ε(e)}. Thus at each time slot t ≥ 1, each edge has to update the weights of edges located in its 2d -neighborhood (edges at distance ≤ 2d from e), if we have an interference model based on distance d. Therefore the overhead is not constant and furthermore one has to obtain this information, which, due to interference, is a problem as difficult as the transmission scheduling problem.

The algorithm described in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], Augmenting Paths Algorithm, has a constant overhead but it is specific to the primary node interference model (d = 0). It uses the "augmenting path tool" developed for matching theory [START_REF] Lovász | Matching Theory[END_REF] and which is used to find polynomial centralized algorithms to determine maximum matchings. In that case, at each time slot t ≥ 1, INRIA a valid set of active links is a matching of the transmission graph G = (V, E). The main idea of Augmenting Paths Algorithm, is to compute, at a step t + 1 > 1, a matching of G from the matching of G found at step t. In [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], it is proved that, if 2k + 1 is the maximum length of the augmenting paths, the algorithm needs a constant overhead of order 4k + 2 and achieves k k+2 of the capacity region (we can improve via a careful analysis this value to k k+1 ). Moreover at the beginning of each time slot t ≥ 1, each node v ∈ V becomes seed with a constant probability p. A seed is a node allowed to start an alternating path. In [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], it is not described how to compute p analytically.

Finally it is necessary to precise that Augmenting Paths Algorithm is specific to the primary node interference model (d = 0), not the more realistic one. Indeed the augmenting paths technical is a property of the notion of matching in graphs. Recall that the problem of determining a maximum matching (if the interference model is defined by d = 0) can be done in polynomial time with a centralized algorithm, but for interference models defined by d ≥ 1, determining a maximum valid set of active edges is an NP-complete problem. In Section 7.2.2 we compare via simulations the performance of Augmenting Paths Algorithm to the performance of our distributed algorithm, proposed in Section 4, for a square grid composed of 121 nodes.

Our Distributed Algorithm

We propose in this section a distributed link scheduling algorithm, valid with a constant communication overhead, whereas the algorithm proposed in [START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF] has an overhead increasing with the size of the network, and valid for any binary interference set, whereas Augmenting Paths Algorithm, proposed in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], is valid only for the primary node interference model (d = 0). Furthermore algorithms proposed in the literature like those in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF][START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF] require exchange of weights between some edges (the acquisition of this information is, due to interference, a difficult and costly problem and needs itself a control phase). Here, in contrary, during each mini-slot of the control phase, any edge either sends a control message composed of 1 bit or nothing. The main idea of Algorithm Log is to use interference as information. More precisely during each mini-slot the only important thing for an edge e ∈ E is to determine if an edge e ∈ ε(e) has sent a control message through this mini-slot. Based on that and on its own bit the edge will decide to be active or inactive or postpone the decision to another mini-slot. As two edges e ∈ E and e ∈ ε(e) do not exchange their respective weights during the control phase, the number and size of mini-slots, and therefore the overhead, are minimized.

As previously described in Section 2, the network is modeled by an undirected transmission graph G = (V, E) and time is slotted into steps of same size. At any step t ≥ 1, a set of active links is chosen through a control phase and during the data phase, these links send their messages. We precisely describe in this section, the control phase for any time slot t ≥ 1. We propose a distributed algorithm, Algorithm Log, which will compute a valid set of active links at step t, with a sum of weights of edges belonging to this set as large as possible. Recall that the weight q t (e) of an edge e ∈ E is the number of messages in the queue associated to this link (Section 2). Finally only edges with weight greater than their capacity will participate to Algorithm Log, that is if qt (e) c(e) ≥ 1. We call this set of edges E 1 . Another idea consists in associating to each edge a virtual weight (see Section 4.1) in such a way that two edges interfering have different virtual weights (Lemma 1). Then each edge computes the binary control vector associated to the virtual weight; the bits 1 will indicate the mini-slots when the edge will send a control message if it is not yet inactive (Section 4.2). In Section 4.3 we describe precisely Algorithm Log, before giving two examples in Section 4.4. We then analyze Algorithm Log in Section 5.

Virtual Weights

The idea consists in splitting the values of the queues into a small number K of disjoint intervals (classes) I 0 , . . . , I K-1 with the constraint that the largest class I K-1 contains all the values greater than some value L: I K-1 =]L, ∞[. As K will be small, many edges interfering might belong to same interval. To differentiate them we also give to each edge a color (integer) γ(e) in such a way that two edges interfering have different colors. Let C be the number of colors. For example if G is a path, in the d-interference model, we can use only d + 2 colors by giving to the edges values 1, 2, . . . , d + 2, 1, 2, . . . , d + 2, . . . Figure 4(b) shows a coloring for a cycle of length 9 with C = 3 within the primary node interference model (d = 0). We will see in Section 5.3 how to determine C. This coloring will give a ranking between the edges in a same interval. In order to get different rankings in consecutive slots, we will permute the colors. For that we associate in the slot t the value γ t (e) = (γ(e) + t -2) modC + 1. From definition of γ(e), γ t (e) = γ t (e ) for each e ∈ E, e ∈ ε(e), t ≥ 1. For example, with C = 3 an edge with color 1 will get a value 1 at slot 1, 2 at slot 2, 3 at slot 3, 1 at slot 4, 2 at slot 5 and so on. Now we can assign to each edge e ∈ E a virtual weight q t (e) as follows. Let f be the mapping

f : [1, ∞[→ {0, . . . , K -1} defined by f (x) = i if x ∈ I i for i = 0, 1, . . . , K -1. Then q t (e) = Cf q t (e) c(e) + γ t (e) (1)
See Figure 4 and Figure 5 for examples of computations. Note that

0 < q t (e) ≤ CK ∀e ∈ E 1 , t ≥ 1. ( 2
)
The discussion of the choice of constants C, K and L is deferred to Section 5.3 and Section 5.4.

The motivation for introducing these virtual weights is threefold. First, and most importantly, virtual weights have the property that two interfering links have different virtual INRIA weights (see Lemma 1 below). This property will be a key ingredient for ensuring that our scheduling algorithm determines a maximal set of active links in each time slot (see Section 5.1). Second, the scaling in (1) (i.e. the fact that q t (e) is divided by c(e)) will ensure that our algorithm will work with absolute delays in terms of time and not favor links with high capacities. Finally our algorithm will use the ranking induced by the virtual weights to determine the active edges; an edge with a high virtual weight and in particular with a high queue will have more chances to be chosen.

Lemma 1.

Let e, e ∈ E be two edges in E 1 such that e ∈ ε(e) (and e ∈ ε(e )). Then, q t (e) = q t (e ).

Proof. If qt (e) c(e) and qt(e ) c(e ) belong to two different intervals, that is f

( qt(e) c(e) ) = f ( qt(e ) c(e ) ), then |C(f ( qt(e)
c(e) ) -f ( qt(e ) c(e ) ))| ≥ C and as 1 ≤ γ t (e), γ t (e ) ≤ C, q t (e) = q t (e ). Otherwise, if f ( qt (e) c(e) ) = f ( qt(e ) c(e ) ), then by the choice of γ(e) and γ(e ), γ t (e) = γ t (e ) and so q t (e) = q t (e ).

Control Vector

We assign to each edge e ∈ E 1 , a control vector v t,e = (v t,e (1), . . . , v t,e (T )) where v t,e (i), 1 ≤ i ≤ T , corresponds to the ith bit of q t (e). Recall that q t (e) ≤ CK for each e ∈ E, and so T = log 2 (CK) + 1 . Remark that an edge e / ∈ E 1 (that is not participating to the control phase) can be considered as having a virtual weight q t (e) = 0 and so having a control vector v t,e only composed of 0, and we do not consider anymore this kind of edges in our algorithm (we could have included them with this control vector but they will never become active). In Table 1, all possible virtual weights and corresponding control vectors of an edge e ∈ E 1 are represented for each possible pair (q t (e), γ t (e)) according to the following parameters: d = 0 (primary node interference model), C = 3, K = 5, and for example L = 4. It corresponds to a cycle graph with an odd number of nodes. An example of such a graph G = (V, E) is depicted in Figure 4(b), where values located on edges correspond to a valid assignment of γ(e) for each e ∈ E. Indeed, any such assignment requires at least 3 different integers, and so C ≥ 3 (see Section 5.3). Remark that for a cycle with an even number of nodes, 2 integers are sufficient to assign γ(e) for each edge e ∈ E. We could have chosen another value for L for example L = 100 and take as intervals I 4 =]100, ∞[ and for example I 0 = [START_REF] Balakrishnan | The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks[END_REF][START_REF] Eryilmaz | Polynomial complexity algorithms for full utilization of multi-hop wireless networks[END_REF]; I 1 =]10, 30]; I 2 =]30, 60]; I 3 =]60, 100] or any other splitting of the values of the queues. The control vector is the same as that given.

Algorithm Log

Given the following inputs : the binary interference model, K, L, and a valid integer C respecting previous constraints, Algorithm Log will compute a maximal set of active edges.

Table 1: (q t (e), v t,e ) for every possible pair (q t (e), γ t (e)) for Algorithm Log (C = 3, K = 5, L = 4). (e) c(e) ) γ t (e) q t (e) v( 1) v( 2) v( 3) v( 4)

Control Vector: v = v t,e f ( qt
1 1 1 0 0 0 1 1 2 2 0 0 1 0 1 3 3 0 0 1 1 2 1 4 0 1 0 0 2 2 5 0 1 0 1 2 3 6 0 1 1 0 3 1 7 0 1 1 1 3 2 8 1 0 0 0 3 3 9 1 0 0 1 4 1 10 1 0 1 0 4 2 11 1 0 1 1 4 3 12 1 1 0 0 ≥ 5 1 13 1 1 0 1 ≥ 5 2 14 1 1 1 0 ≥ 5 3 15 1 1 1 1
At each mini-slot of Algorithm Log, an edge can be active, inactive, or still undetermined.

All the edges e ∈ E 1 active at the end of Algorithm Log will send data after. The control phase is itself divided into α subphases. We first explain subphase 1 before motivating and describing subphases 2, . . . , α. We will see in Section 5.1 how to determine α.

Subphase 1

Let us describe subphase 1 composed of T mini-slots. Before mini-slot 1, each edge is undetermined. During a mini-slot i,

1 ≤ i ≤ T , e ∈ E

INRIA

At the end of subphase 1 (after T mini-slots), we get a valid set of active links (edges), respecting interference constraints. For example if the interference model is defined by d = 0 (primary node interference model), we get a matching of G. If the interference model is defined by d = 1, we get an induced matching of G. Furthermore at the end of subphase 1, an edge e ∈ E is either active or inactive (see Lemma 2). Lemma 2. At the end of subphase 1 of Algorithm Log, there is no undetermined edge.

Proof. From Lemma 1, q t (e) = q t (e ) for any e, e ∈ E such that e ∈ ε(e). Suppose e is undetermined at the end of subphase 1 of Algorithm Log. During the last mini-slot where e sends a control message (mini-slot T if q t (e) is odd, mini-slot T -1 if q t (e) is even), it stayed undetermined if another edge e ∈ ε(e) sends a message during this mini-slot. But as q t (e) = q t (e ) there is a preceding mini-slot where the edge with the biggest weight was sending a control message and the other not; but the edge with the smallest weight would have become inactive at this time slot, a contradiction.

Definition 3.

An edge e ∈ E 1 is a local maximum edge at step t ≥ 1 if ∀e ∈ ε(e), q t (e ) ≤ q t (e). Remark that if an edge is maximum then we have the strict inequality from Lemma 1.

From Lemma 2, it follows that a maximum local edge e is necessarily active at the end of subphase 1.

Corollary 4. A local maximum edge e ∈ E is always active at the end of subphase 1 of Algorithm Log.

Thus edges with large weights (in a local point of view) are chosen as active and belong to the set of active links. Recall that one of the main objectives of transmission scheduling algorithms is to insure stability of queues associated to links, and so if the set of active links contains edges with large weights, queues with many messages decrease.

After subphase 1, it might happen that the set of active links was not maximal (edges can be added to this set without removing current edges in this one). For instance Figure 4 describes subphase 1 of Algorithm Log for a cycle composed of 9 edges with d = 0. For such a network it is the worst case in terms of cardinality of the set of active links (matching of G). Indeed after subphase 1, only the central link is active. One possibility is to add extra mini-slots to get more active links with a random process. Another solution is to repeat this subphase α -1 times, and so get α subphases in Algorithm Log. We describe it in Section 4.3.2.

Other Subphases

As described in Section 4.3.1, it might happen that the set of active edges was not maximal after subphase 1. To deal with this problem, we apply α -1 times the protocol described for RR n°6763 subphase 1, but only with edges which can be added that is inactive edges without active links in their interference sets. After each subphase each edge is either active or inactive (Lemma 2). So, we add a re-initialization mini-slot after each subphase j, 1 ≤ j ≤ α -1, where each active edge sends a control message and inactive edges become undetermined if they do not receive any message (lines 15-20 of Algorithm 1). The next subphase will involve only those undetermined edges. In Theorem 5 of Section 5.1, we will see that, if we fix the value of the parameter α to be T , we insure that at the end of each control phase, Algorithm Log always computes a maximal set of active edges in E 1 .

Finally we define Algorithm Log composed of α subphases as described above. A formal algorithm for each edge e ∈ E is described in Algorithm 1, where s(e) = 1 if e is active, s(e) = 0 if e is undetermined, and s(e) = -1 if e is inactive.

INRIA Algorithm 1 Distributed Algorithm of an edge e ∈ E Require: q t (e), γ t (e). Ensure: return active or inactive

1: e computes q t (e) and v t,e 2: s(e) = 0 3: for j = 1, . . . , α do 4:

for i = 1, . . . , T do 5:
if s(e) = 0, and v t,e (i) = 1 then

6:

e sends a message (to edges in ε(e))

7:

if e does not receive a message then 8:

s(e) = 1 if s = 0, v t,e (i) = 0, and e receives a message then 12:

s(e) = -1

Examples

We present here two examples of applications of Algorithm Log. In Section 4.4.1 Algorithm Log is applied to a square grid graph with the interference model defined by d = 0 and in Section 4.4.2 Algorithm Log is applied to a graph (generated randomly as in Section 7.2.3) with the interference model defined by d = 1.

Square Grid with d = 0

Let G = (V, E) be a square grid graph composed of |V | = 16 nodes and |E| = 24 edges (Figure 5). The interference model is defined by d = 0, and so a valid set of active links is a matching of G. In our example the smallest C respecting constraints described in Section 4.1 is 4 (See Figure 5(b) for an example of such optimal assignment of γ(e) for each e ∈ E and see Section 5.3 for details). In this example K = 15 and L = 140. Given a time slot t ≥ 1, the weight q t (e), the value γ t (e), and the virtual weight q t (e) are respectively represented in Figure 5(a), in Figure 5(b), and in Figure 5(c) for each edge e ∈ E. For example for the top-left edge e ∈ E with weight q t (e) = 94 and γ t (e) = 1, q t (e) = 37 using Equation 1. Thus the associated control vector v t,e (e) = (1, 0, 0, 1, 0, 1). Let us describe subphase 1 of Algorithm Log composed of 6 mini-slots. At the beginning (before mini-slot 1), each link is undetermined. During mini-slot 1, each edge e such that v t,e (1) = 1 sends a control message and:

(a) if e sends a control message and e does not receive one from an edge in ε(e), then e becomes active; (b) if e receives a control message (therefore coming from an edge in ε(e)) and does not send a control message, then e becomes inactive; (c) otherwise e remains undetermined. Figure 5(d) shows the state of the edges after mini-slot 1. For example the horizontal edge on the bottom-left (with q t (e) = 53) becomes active. Furthermore there are three connected components of undetermined edges, respectively composed of 5, 3, and 2 edges. Repeating the same protocol during mini-slot 2, there are three connected components of undetermined edges, respectively composed of 2, 3, and 2 edges (Figure 5(e)). After mini-slot 3, a second edge becomes active and there are three connected components of undetermined edges, respectively composed of 2, 1, and 2 edges (Figure 5(f)). After mini-slot 4, there are two additional active links, and there is one connected component of undetermined edges composed of 2 edges. After mini-slot 5, one more edge becomes active and there is no undetermined edge (Figure 5(g)). Thus after T = 6 mini-slots (after subphase 1 of Algorithm Log), a set of active links is found. But it is easy to show that this matching is not maximal. Thus at the beginning of subphase 2, inactive edges without active link in their interference sets become again undetermined (it is possible with one re-initialization mini-slot at the end of the previous subphase). We repeat the same protocol than before, and in this example we get a maximal set of active links (maximal matching) after the subphase 2. From Theorem 5 of Section 5.1, α = T subphases is sufficient to insure a maximal set of active links (∀d ≥ 0).

Random Graph with d = 1

Let G = (V, E) be a random graph composed of |V | = 33 nodes and |E| = 56 edges (Figure 6). G has been generated using method described in Section 7.2.3. The interference model is defined by d = 1, and so a valid set of active links is an induced matching of G. Figure 6 shows the four first mini-slots of subphase 1 of Algorithm Log. We get after mini-slot 4 a maximal induced matching and so the set of active links for this time slot.

Analysis

We analyze in this section Algorithm Log, fixing the value α to ensure that for any time slot t ≥ 1, the set of active links is maximal in Section 5.1, computing the overhead (number of mini-slots of the control phase) in Section 5.2, and finally describing how to choose the different parameters C, K, L of Algorithm Log in Section 5.3 and in Section 5.4.

Maximality

After the control phase of Algorithm Log for any step t ≥ 1, we prove that the set of active links is always maximal,if we choose α = T = log 2 (CK) + 1 .

Theorem 5. If we choose α = T = log 2 (CK) + 1 in Algorithm Log, then for all e ∈ E 1 (set of edges with positive virtual weight), there exists one edge e ∈ ε(e) ∪ {e} such that e is active at the end of Algorithm Log.

INRIA

Proof. Let T = log 2 (CK) + 1 . Let e 1 be any edge of E 1 . Either e 1 is active at the end of subphase 1 of Algorithm Log, and the theorem is proved. Or e 1 is inactive due to an edge e 2 ∈ ε(e 1 ) (with q t (e 2 ) > q t (e 1 )) which has sent a control message at some mini-slot t 1 . Either e 2 is active and the theorem is proved or e 2 is inactive due to an edge e 3 ∈ ε(e 2 ) which has sent a control message at some mini-slot t 2 > t 1 , and so on. Let k be the largest index of a sequence of inactive edges e 1 , e 2 , . . . , e k such that edge e i (1 ≤ i ≤ k) is inactive due to e i+1 ∈ ε(e i ) which has sent a control message at mini-slot t i and edge e k+1 is active.

As

T ≥ t k > . . . > t i > t i-1 > . . . > t 1 ≥ 1, we have k ≤ T .
We will now prove by induction that, at the end of the subphase j of Algorithm Log, the longest sequence of edges e 1 , e 2 , . . . , e kj such that edge e i (1 ≤ i ≤ k j ) became inactive due to e i+1 ∈ ε(e i ) and edge e kj +1 is active, satisfies k j ≤ T -j + 1. As we have seen, that is true for j = 1. Suppose it is true till j -1. Note that e kj +1 was not active at the end of subphase j -1, otherwise e kj would have been definitively inactive at the end of the subphase j -1 and would not participate to the subphase j . As the edges e 1 , e 2 , . . . , e kj are also inactive at the end of subphase j -1, we have a sequence of inactive edges of length k j + 1 and by induction hypothesis the length of this sequence satisfies k j + 1 ≤ T -(j -1) + 1 and so k j ≤ T -j + 1. Therefore, for some j 0 ≤ T , k j0 ≤ 1 implying that at the end of the subphase j 0 any edge e is either active or is inactive due to an active edge e ∈ ε(e) ∪ {e}.

Overhead (Complexity)

We compute here the number of mini-slots required for the control phase of Algorithm Log according to K and C.

Theorem 6. The number of mini-slots of the control phase of Algorithm Log is

T log = log 2 (CK) + 1 2 + log 2 (CK) + 1 -1.
Proof. Subphase 1 of Algorithm Log is composed of T mini-slots where T = log 2 (CK)+1 . From Theorem 5, α = T subphases are sufficient to insure maximality. Furthermore at the end of subphase i, 1 ≤ i ≤ T -1, one re-initialization mini-slot is needed. Indeed each active edge sends a control message and some inactive edges become undetermined if they do not receive any message. Thus T -1 extra mini-slots are added. Finally T log = T 2 + T -1.

How to Compute the Constant C?

In order to minimize the overhead of Algorithm Log (number of mini-slots of the control phase), we have to minimize the constant C, insuring that γ(e) = γ(e ) and 1 ≤ γ(e), γ(e ) ≤ C for all e, e ∈ E such that e ∈ ε(e) (and so e ∈ ε(e )). Recall that if γ(e) = γ(e ), then ∀t ≥ 1, γ t (e) = γ t (e ) (Section 4.1). Given a graph G = (V, E), our problem consists in assigning an integer (a color) γ(e) to each edge e ∈ E such that the integers assigned to two edges e, e ∈ E with e ∈ ε(e ) are different, minimizing the total number of integers (colors) used to do it. For our problem, the integer (color) assigned to an edge e corresponds to γ(e) and the minimum total number of colors needed corresponds to the minimum C respecting previous constraints. There exists a simple greedy algorithm to do it in linear time using 2∆(G) d+1 different integers (colors) [START_REF] Diestel | Graph Theory[END_REF] where ∆(G) is the maximum degree in G with the interference model defined by d.

A particular case is when the binary interference model is defined by d = 0. In that case, the problem of minimizing C remains to compute the Edge Chromatic Number, denoted by χ (G), of G (see [START_REF] Fiorini | Edge-colourings of graphs[END_REF]). Theorem 7 proves a better bound to the optimal number of colors needed. A proof of this theorem can be found in [START_REF] Fiorini | Edge-colourings of graphs[END_REF] and a constructive proof in [START_REF] Misra | A constructive proof of vizing's theorem[END_REF]. Finally there exists a polynomial time algorithm to get a (+1)-approximation for this particular problem. More precisely this algorithm computes a valid coloring of the edges using at most ∆(G) + 1 colors and in the worst case, the optimal value is ∆(G) colors.

Theorem 7 (Vizing's Theorem). Given a graph

G = (V, E), ∆(G) ≤ χ (G) ≤ ∆(G) + 1 where ∆(G) is the maximum degree in G.
Furthermore, if G is bipartite, χ (G) = ∆(G), and in particular for the grid χ (G) = 4.

How to Choose K and L?

If the number T log of mini-slots allowed is constant and fixed, it is possible to compute the maximum value of K respecting this constraint. More precisely we choose the largest K such that log 2 (CK) + 1 2 + log 2 (CK) + 1 -1 ≤ T log (C is a constant previously computed by algorithms described in Section 5.3). Furthermore we choose L large enough. Recall that the number of mini-slots T log of Algorithm Log is constant when L increases.

Stability

We analyze the stability of Algorithm Log in this section. Note that since Algorithm Log produces a maximal match in every timestep, it is guaranteed to achieve a fraction of the maximum throughput capacity in an arbitrary wireless network [START_REF] Chaporkar | Throughput and fairness guarantees through maximal scheduling in wireless networks[END_REF]. However, the capacity region for Algorithm Log is larger than this minimum bound, and we now proceed to calculate it.

Let A t (e) ∈ {0, 1, . . .} be the number of arrivals on link e in slot t.

Recall that q t (e) is the number of packets waiting to be transmitted on link e (called queue e) at the beginning of slot t.

For the sake of simplicity we assume that arrivals on link e ∈ E during slots sC + 1, sC + 2, . . . , (s + 1)C (s = 0, 1, . . .) join queue e at the end of slot (s + 1)C.

INRIA

Let B s (e) := (s+1)C t=sC+1 A t (e) be the cumulated number of arrivals on link e ∈ E during slots sC + 1, sC + 2, . . . , (s + 1)C. We have q (s+1)C (e) = q sC+1 (e) -x sC+1 (e) + B s (e), e ∈ E, where x sC (e) ∈ [c(e), q sC+1 (e)] is the number of packets transmitted on link e during slots sC + 1, sC + 2, . . . , (s + 1)C. The requirement that x sC (e) ≥ c(e) is a consequence of the property that Algorithm Log activates a link only if its backlog is at least equal to the link capacity (see Section 4.1).

Assumption 1.

For each e ∈ E, {B s (e), s ≥ 0} is an independent and identically distributed (iid) sequence of random variables. Furthermore {B s (e), s ≥ 0}, e ∈ E, are mutually independent sequences. Assumption 1 and the definition of the virtual weights in Section 4.1 imply that X := {((q sC (e), γ sC (e)), e ∈ E), s ≥ 0} is a Markov process with state-space IN |E| × {1, . . . , C}, where C is the number of colors needed so that two interfering edges have different colors.

We will assume that this Markov chain is irreducible. Under Algorithm Log this property will hold, in particular, if P (A t (e) = k) > 0 for all k.

The stability of Algorithm Log is defined as the stability of the Markov chain X. In words, when Algorithm Log is stable then queues "will not build up".

Let {I j } j be the set of all admissible schedules. A schedule I j = (I j (e), e ∈ E) is a binary vector where I j (e) = 1 if link e is active and I j (e) = 0 otherwise. A schedule is admissible if it will not produce any interference among active links.

Define the so-called capacity region C [START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[END_REF] (with λ j > 0 for all j)

C =    v =   j λ j I j   M with j λ j < 1    .
with M = diag(c(e), e ∈ E).

Let c = (c(e), e ∈ E) be the link capacity vector. Let H(e) be the maximum number of links that can be scheduled if link e is not scheduled and let H = max(1, max e∈E H(e)).

We define the load vector as the vector b = (E[B s (e), e ∈ E).

The following result holds: The proof is an adaptation of the proof of Theorem 1 in [START_REF] Bhandari | A result on hybrid scheduling in wireless networks[END_REF] (Hint: replace the definition of the set L (s) in [START_REF] Bhandari | A result on hybrid scheduling in wireless networks[END_REF] by L (s) = {e ∈ E : q sC+1 (e) ≥ LCc(e)}) since Algorithm Log behaves as a hybrid scheduling whenever L (s) = E for all s ≥ 0.

for all e ∈ E then Algorithm Log is stable.

If this conjecture holds a natural question is to know what stability region among that defined by Theorem 8 and by conditions (3) is the largest. We provide a partial answer to that question in the setting of Example 9 when c(e) = 1 for all e ∈ E.

Assume that (2(d + 2)/3)((d + 2)a + ) ∈ C for some > 0 so that from Example 9 Algorithm Log stabilizes the load vector a = (a(1), . . . , a(|E|)) with a(e) := A(e).

From the definition of the region C this means that there exist constants λ i > 0 with This shows that the stability region given in ( 3) is larger than that given in Theorem 8.

We conclude this section by observing that conditions

A(e) < c(e)/C, e ∈ E. [START_REF] Cameron | Induced matchings[END_REF] ensure the stability of Algorithm Log when K = 1. This is so because when K = 1 the virtual weights do not depend on the backlogs, which in turn implies that Algorithm Log becomes a deterministic algorithm that guarantees each link e to transmit at least c(e) packets every C consecutive slots.

Simulations

We investigate in this section performance of our distributed scheduling algorithm, Algorithm Log, via simulations. More precisely, we compute the total sum of active links at a given step (Section 7.1), and we study the evolution of the largest queue of the network for thousands time slots (Section 7.2). For instance in Section 7.2.2 we compare the largest and average value computed by Algorithm Log to the one found by Augmenting Paths Algorithm, proposed in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF].

Weight of the Set of Active Links

We study in this section the ratio between weights of the optimal matching and the matching computed by Algorithm Log for a path. Figure 7(a) shows this ratio for a path G = (V, E) composed of |E| = 50 edges for 1000 tests. At each test, we assign a weight for each e ∈ E as follows: P (q t (e) = i) = 1/101, 0 ≤ i ≤ 100. We observe that, for each test, Algorithm Log finds a matching of weight at least 4/5 than the optimal.

Evolution of the Largest/Average Queue

We investigate in this section the evolution of the length of the queues for a certain number of time slots applying Algorithm Log. (a) Ratio optimal / Algorithm Log. Algorithm Log to Augmenting Paths Algorithm for the grid topology (largest and average values), using parameters chosen in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF].

Paths

We show here some simulations for path networks. From Section 5.3, it is sufficient to assign the sequence of integers (colors) 1, 2, 1, 2, . . . on the edges of the path, considering the interference model defined by d = 0. Thus C = 2. We first investigate Algorithm Log for a path G = (V, E) composed of |E| = 100 edges during 100000 time slots. We choose K = 1000. Furthermore for any edge e ∈ E, the capacity is c(e) = 18, and the arrival process is defined as follows: n 1 messages arrive in average on e at a step t ≥ 1 for an edge e ∈ E with color 1 (γ(e) = 1) and n 2 message arrives in average for the others (each edge e ∈ E such that γ(e) = 2). Figure 8(a), Figure 8(b), and Figure 8(c) represent the largest weight of edges at each time slot respectively for pairs (n 1 , n 2 ) = (16, 1), = [START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF][START_REF] Brzezinski | Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach[END_REF], and = [START_REF] Chen | A queue-aware scheduling algorithm for multihop relay wireless cellular networks[END_REF][START_REF] Chen | A queue-aware scheduling algorithm for multihop relay wireless cellular networks[END_REF]. We observe that the largest queue is always lower than respectively 400, 180, and 140.

Then we investigate the impact of the value of K on the largest and average queue of a path G = (V, E) composed of 100 edges with d = 0. For each e ∈ E, an average of 0.75 (respectively 0.2) messages arrive at each step t ≥ 1 if γ(e) = 1 (respectively γ(e) = 2). Figure 7(b) represents largest and average weight after 50000 time slots for different values of K: K = 1, 2, 4, 8, . . . , 128. The plot illustrates the performance-overhead tradeoff of Ka higher K leads to lower average queue sizes, but most of the gains come with relatively small values of K.

Square Grids

We compare in this section our distributed algorithm, Algorithm Log, to the one proposed in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], Augmenting Paths Algorithm, choosing the same parameters. More precisely, the simulations have been done for a square grid G = (V, E) of |V | = 121 nodes and with |E| = 220 edges (Figure 9). For each edge e ∈ E, the capacity is c(e) = 1. Furthermore values mentioned in Figure 9 represent average arrivals divided by a parameter λ ≤ 1.

As described in Section 3, Augmenting Paths Algorithm requires parameters in inputs: k and p. In [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], simulations have been done for the following parameters: {k = 2, p = 0.2}, {k = 3, p = 0.2}, and {k = 3, p = 0.1}. In [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF], the number of time slots is 48000.

Recall that Augmenting Paths Algorithm is only valid for the primary node interference model, and so d = 0 for our comparisons. Let us describe the parameters chosen for Algorithm Log. From Section 5.3, the minimum value of C respecting constraints described in Section 4 is χ (G) = 4. See Figure 5(b) for an example of valid assignment of γ(e). Furthermore we choose K = 1000 = L + 1. We compare in Figure 10 Algorithm, for the parameter {k = 2, p = 0.2} described in [START_REF] Bui | Distributed link scheduling with constant overhead[END_REF]. Simulation results for the two other parameters are analogous. We note that the flexibility of Algorithm Log comes at a price for highly loaded networks, as Augmenting Paths Algorithm performs better on average (though both are stable). However, Augmenting Paths Algorithm is specialized for d = 0 where Algorithm Log is stable for any value of d. Figure 7.2.3 shows a simulation for the same grid network with the arrival rate in the capacity region established in Section 6. As can be seen, Algorithm Log stabilizes the system.

Random Graphs

Finally in this section we apply Algorithm Log to a random network. First let us describe how we have built our random graphs before analyzing the evolution of the largest queue. Given a grid graph G = (V, E ), we delete an edge e ∈ E with a certain constant probability p, before adding others edges with another constant probability q between two nodes not so far than a certain Euclidean distance. We get a random transmission graph G = (V, E). Figure 6 shows an example of such a random graph with |V | = 33 nodes and |E| = 56 edges.

In our simulations, we investigate the stability criteria defined in Equation 3 of Section 6 with c(e) = 20, ∀e ∈ E.

The arrival processes for edges of the network are defined as follows: we first assign to each edge e ∈ E an average arrival of 20 messages per step t ≥ 1 (uniform between 0 and 40). To respect previous conditions, we decrease the average number of arrivals per step by 1 for an edge e if it is necessary, until having the desired condition. In Figure 7

Multi-Hop Traffic

We show in this section how to extend Algorithm Log to take into consideration multi-hop traffic when routing is fixed. The main idea is to change the vector q t of previous weights (Section 2) and the vector q t of previous virtual weights (Section 4.1) into multi-hop vector of weights q m t and virtual multi-hop vector of weights q m t . Let G = (V, E) be the transmission graph. More precisely ∀e ∈ E, q m t (e) = p i t (e)h i t (e) where p i t (e) is the packet numbered i in the queue of link e at step t and h i t (e) is the number of remaining hops of the previous packet. From q m t (e), we compute q m t (e) for e in the same manner than in Algorithm Log (Section 4.1). We assume here that the routing is pre-computed. Note that the policy of services can changed with application requirements.

Conclusion

We proposed in this the first, to our knowledge, a distributed algorithm for the transmission scheduling problem in wireless networks with constant overhead and arbitrary binary interference. We proved that the set of active links at each time slot is maximal. We proposed sufficient stability conditions and investigated performance of our distributed algorithm via simulations. We also proposed extensions to our algorithm in the multi-hop case.

Since our algorithm works with arbitrary interference constraints, and uses observed interference for its functioning, we believe it translates into a practical implementation well and that is planned as future work. It will be interesting now to prove a better stability condition and characterize the stability region of our algorithm. Although simulation results strongly suggest that the algorithm is capacity achieving, it remains to be proven analytically.

2 Figure 1 :

 21 Figure 1: scheduling algorithm for grid for d = 0.

Figure 2 :

 2 Figure 2: interference sets of e for d = 0 and d = 1.

Figure 3 :

 3 Figure 3: two sets of active (blue straight) links.

Figure 4 :

 4 Figure 4: subphase 1 of Algorithm Log for a cycle of 9 edges (d = 0, C = 3, K = 5, L = 4).

INRIA

2 Figure 5 :

 25 Figure 5: Algorithm Log for a grid (d = 0, C = 4, K = 15, L = 140).

Figure 6 :

 6 Figure 6: four first mini-slots of subphase 1 of Algorithm Log for a random graph with d = 1.

Theorem 8 .

 8 Under Assumption 1 and if E[B s (e)B s (e )] is bounded for all e, e ∈ E then Algorithm Log stabilizes the load vector b if (CH/(C + H -1))(b + c) ∈ C for some > 0.

i λ i < 1 4 )From ( 4 ) 5 )

 1445 such that (2(d + 2)/3) ((d + 2)a(e) + ) = i λ i I i (e), e = 1, . . . , |E|. (and the positiveness of we deduce that a(e) < 3 2(d + 2) 2 i λ i I i (e), e = 1, . . . , |E|. (Let us show that the vector a strictly lies within the region defined by conditions in (3). This amounts to showing that D(e) < 1 for e = 1, . . . , |E| with D(e) := a(e -1 + d) + • • • + a(e -1) + a(e) +a(e + 1) + • • • + a(e + 1 + d) where a(e) = 0 if e ∈ {1, . . . , |E|} by convention. From (5) we find D(e) < 3 2(d + 2) 2 i λ i (I i (e -1 + d) + • • • +I i (e -1) + I i (e) + I i (e + 1) + • • • + I i (e + 1 + d)) INRIA for e = 1, . . . , |E|. By definition of the interference distance d we observe that I i (e -1 + d) + • • • + I i (e -1) + I i (e) +I i (e + 1) + • • • + I i (e + 1 + d) ≤ 2 for e = 1, . . . , |E| since at most 2 links can be simultaneously active among 2(d + 1) + 1 consecutive links. Hence, D(e) < 3/(d + 2) 2 ≤ 3/4 for e = 1, . . . , |E| and for any d ≥ 0.

Figure 7 :

 7 Figure 7: Performance of Algorithm Log

Figure 8 :

 8 Figure 8: evolution of the largest queue for a path network composed of 100 edges for Algorithm Log (d = 0, K = 1000, L = 99, C = 4).

Figure 9 :Figure 10 :

 910 Figure 9: grid network.

  Figure 10(a), Figure 10(b), and Figure 10(c) represent respectively largest and average value for λ = 0.90, 0.95, 0.97 (red straight lines represent Augmenting Paths Algorithm and blue dotted lines represent Algorithm Log).

Figure 11 :

 11 Figure 11: Largest and average queue size for a grid network with d = 1 interference constraint

Example 9 .

 9 Consider a graph G = (V, E) composed of |E| links in series with an arbitrary interference distance d. In this case, H = 2(d + 1) since a link is in conflict with at most 2(d + 1) other links and C = d + 2 since d + 2 colors are needed to color a path when the interference distance is d.Assume that for each e, {A t (e), t ≥ 0} is an idd sequence with A(e) = E[A t (e)] and that E[A t (e)A t (e )] is bounded for e, e ∈ E. In particular, E[B s (e)] = 2A(e).

	Theorem 8 says that if the vector a = (A(e), ∈ E) is such that there exists > 0 with
	(2(d + 2)/3)((d + 2)a + c) ∈ C then a stabilizes Algorithm Log.
	We conjecture that if
	A(e ) <	min	c(e )
	e ∈ε(e)∪{e}	e ∈ε(e)∪{e}

RR n°6763


G Cochet

A.-C Amiaud

J.-P Coupez

A Manchec

T Merlet

C Person

C Quendo

Transition PCB/guide d'onde ridgé par cavité SIW

Cet article présente une transition entre un guide d'onde et un circuit imprimé sans connecteur intermédiaire. Elle permet une transition orthogonale dans le plan du champ électrique vers un guide d'onde ridgé. La transition est composée d'une cavité SIW alimentée par une ligne microruban et disposant d'une fente au centre de la cavité qui permet la transmission du signal vers le guide d'onde. La transition, conçue sur un substrat Ro4350, permet une bande passante de 130 MHz et résonne à 10 GHz. Elle se révèle particulièrement intéressante pour alimenter un réseau d'antennes à balayage électronique grâce à sa largeur inférieure à 0,5λ0. Une variante topologique ayant une bande passante deux fois plus large est également présentée.

Introduction

Depuis plusieurs années, les besoins en termes de performances des systèmes de télécommunication hyperfréquences vont grandissant et ce aussi bien pour les performances électriques que pour la mise en oeuvre matérielle de ces dispositifs. Les domaines de la défense, du spatial, de l'aéronautique et de l'automobile sont particulièrement demandeurs de systèmes intégrant non seulement de nouvelles fonctions telles que le balayage électronique, mais aussi de dispositifs moins encombrants, d'un poids toujours réduit et avec une contrainte de coût forte.

Pour répondre à certaines de ces contraintes, des options s'offrent aux concepteurs. L'utilisation de guide d'onde de section réduite, par exemple ridgé, permet non seulement de réduire l'encombrement de certains dispositifs, mais permet aussi un balayage électronique de forte amplitude angulaire grâce à l'utilisation de réseau Afin de palier à ces problèmes, une nouvelle transition PCB/guide d'onde sera présentée dans cet article [START_REF] Cochet | Dispositif de transmission d'un signal à un guide d'ondes[END_REF]. Cette nouvelle transition permet une interconnexion directe entre PCB et guide d'onde, i.e. sans élément complémentaire. Pour une application industrielle, cette transition a l'avantage d'être très simple à monter. Elle peut être adaptée à n'importe quel type de guide quelle que soit la géométrie de sa section transverse, autorisant ainsi une périodicité des guides de 0,5λ0.

Conception et simulation de la transition

Le but de cette nouvelle transition est de pouvoir assurer une transmission du signal efficace entre un circuit imprimé et un guide d'onde ridgé tout en assurant un encombrement limité et une bonne efficacité électrique. Le PCB est ainsi directement en contact avec le guide d'onde placé de façon orthogonale sur le circuit imprimé, Figue 1 (a). La transition proposée est alimentée par (1) une ligne d'accès microruban connectée au plan de masse Les résultats de simulation montrent une faible sensibilité des paramètres S au positionnement du guide vis-à-vis de la fente, Figure 3. Cela, couplé à l'absence d'éléments intermédiaires tels qu'un capot, permet une mise en oeuvre très simple de la transition.

La transition PCB / guide d'onde présente des pertes comprises entre 1.5 et 2 dB sur sa bande de fonctionnement. La plus grande partie de ces pertes (~1 dB) est attribué aux pertes diélectriques du substrat, ce qui est confirmé par une simulation électromagnétique en utilisant un substrat sans pertes. Une plus faible partie peut être attribué à la proximité de la résonance et de la

Variante topologique

La topologie présentée en Figure 2 montre une bande passante relative adaptée à -10 dB de 1.3%. Une variante topologique de cette transition PCB/guide d'onde ridgé est présenté ici. Cette variante utilise des perturbations circulaires au sein de la cavité SIW afin d'augmenter la bande passant de la transition [START_REF] Heidarzadeh | Bandwidth enhancement of the SIW cavity backed slot antennas using symmetric circular perturbation[END_REF].

La topologie de cette version de la transition est très proche de la version précédente et sa mise en oeuvre est identique à celle présentée en Figure 1. La cavité SIW est toujours d'une longueur et largeur d'environ une longueur d'onde et est percée d'une fente orthogonale à la ligne d'alimentation placé au centre de la cavité. La différence topologique vient des vias disposés en quart de cercle dans deux coins opposés de la cavité, Figure 4. Les dimensions obtenues après optimisation par simulation électromagnétique sont présentées en Tableau 2.

Les deux quarts de cercle de vias permettent de séparer les résonances des modes TE120 et TE210, ce qui augmente la largeur de la bande passante sans augmenter ni l'empreinte ni la complexité de fabrication de la transition.

Les coefficients de réflexion et de transmission de la transition sont donnés en Figure 6. La transition présente une réflexion inférieure à -10 dB de 9.85 à 10.12 GHz, soit une bande passante de 270 MHz. Cela représente une augmentation de 108 % de la bande passante de la transition sans les perturbations circulaires.

La majeure partie des pertes observées sur la transmission dans la bande passante sont attribuées aux pertes dans le substrat, ~1 dB. Une plus faible partie des pertes est attribué à la proximité de la fréquence de fonctionnement de la transition et de la fréquence de coupure.

Conclusion

La compacité est un critère important pour les systèmes de communication embarqués. De plus, lorsque ces systèmes reposent sur des antennes à balayage électronique, le pas entre éléments rayonnants doit être compatible des valeurs de dépointage visées. La transition présentée dans ce papier permet d'alimenter directement un guide d'onde via un circuit imprimé sans utilisation de connecteurs intermédiaires. Compacte, simple à fabriquer et à mettre en oeuvre, elle peut être utilisée pour alimenter des guides de faible section transverse. Elle se révèle donc particulièrement intéressante dans les cas d'application nécessitant une grande compacité comme les antennes à balayage électronique. En effet la transition proposé, associé a un guide d'onde ridgé, permet un pas entre voies de 0.45λ0. Deux versions de cette transition sont proposées, la première permet d'obtenir une bande passante relative de 1.3% à 10 GHz et la deuxième topologie proposée permet une bande passante de 2.7% à 10 GHz grâce a l'utilisation de perturbation au sein de la cavité SIW.

Références

  d'antennes guide à fentes [1]. En effet, la réduction de la section du guide permet une périodicité des guides dans leur largeur pouvant être de l'ordre d'une demi longueur d'onde, distance qui permet théoriquement un dépointage électronique illimité du faisceau. Afin de réduire l'encombrement et les pertes du système complet dues à la transition entre le circuit d'alimentation et de réception et l'antenne guide à fentes, une interconnexion directe par le circuit imprimé, ou PCB (Printed Circuit Board) est possible pour éviter l'utilisation de connecteurs coaxiaux. Cependant, ce type d'interconnexion est souvent limité aux guides d'onde à section rectangulaire [2][3] et/ou nécessite des éléments supplémentaires tels que des capots [2][4] augmentant l'encombrement, le poids et le coût du système.

Figure 1 .

 1 Figure 1. (a) vue de la transition PCB/guide d'onde, (b) vue éclatée de la transition et (c) vue de la transition coté guide d'onde.

  d'une cavité SIW à fente d'obtenir une transition ayant une très petite empreinte grâce à la permittivité du milieu. En effet, la largeur de la cavité de 13.5mm permet une périodicité de la transition selon cet axe de 0.45λ0 à la fréquence de résonance. Cette faible périodicité permet à la transition d'être utilisée pour alimenter des réseaux de guides à fentes pour un balayage électronique 1D nécessitant un fort angle de dépointage. En effet, le balayage électronique est limité par l'espacement entre éléments rayonnants, un espacement de 0.5λ0 étant nécessaire afin assurer un dépointage maximal sans apparition de lobes de réseau. De plus, cette transition à l'avantage d'être basée sur une technologie de SIW, relativement simple et maitrisée à l'échelle industrielle. Cette technologie étant éprouvée, son coût de fabrication est modéré et n'augmentera pas le coût de fabrication de la carte électronique nécessaire au fonctionnement d'un réseau d'antennes.

Figure 2 .

 2 Figure 2. Schéma de la transition.

Figure 3 .

 3 Figure 3. Section du guide d'onde.

Figure 4 .

 4 Figure 4. Paramètres S simulés de la transition en fonction de la distance entre le haut du ridge et la fente

Figure 6 .

 6 Figure 6. Paramètres S simulés de la topologie large bande de la transition.

Figure 5 .

 5 Figure 5. Schéma de la transition large bande.

Dimensions en millimètres de la transition large bande à 10GHz sur substrat Ro4350.

  [1] Wei Wang, Shun-Shi Zhong, Yu-Mei Zhang and Xian-Ling Liang, "A broadband slotted ridge waveguide antenna array," in IEEE Transactions on Antennas and Propagation, vol. 54, no. 8, pp. 2416-2420, Aug. 2006, doi: 10.1109/TAP.2006.879216. [2] K. Seo, "Planar Microstrip-To-Waveguide Transition in Millimeter-Wave Band", in Advancement in Microstrip Antennas with Recent Applications. London, United Kingdom, IntechOpen, 2013 [Online].

	Lcav	13.62	Wgap	0.7
	Wcav	13.62	L	4.86
	Lslot	11.5	W	1.09
	Wslot	0.3	Dvia	0.4
	Lgap	2.4	Pvia	0.8
			R	5.43
	Tableau 2.