Sébastien Olive
email: sebastien.olive@sciencesnaturelles.be

Per E Ahlberg
email: per.ahlberg@ebc.uu.se

Vincent N Pernègre
email: pernegre@mnhn.fr

Édouard Poty
email: e.poty@ulg.ac.be

Étienne Steurbaut
email: etienne.steurbaut@naturalsciences.be

Gaël Clément
email: gclement@mnhn.fr

New discoveries of tetrapods (ichthyostegid-like and whatcheeriid-like) in the Famennian (Late Devonian) localities of Strud and Becco (Belgium)

Keywords: Becco, Famennian, ichthyostegid-like, Strud, tetrapod, whatcheeriid-grade taxon

The origin of tetrapods is one of the key events in vertebrate history. The oldest tetrapod body fossils are Late Devonian (Frasnian-Famennian) in age, most of them consisting of rare isolated bone elements. Here we describe tetrapod remains from two Famennian localities from Belgium: Strud, in the Province of Namur, and Becco, in the Province of Liège. The newly collected material consists of an isolated complete postorbital, fragments of two maxillae and one putative partial cleithrum, all from Strud, and an almost complete maxilla from Becco. The two incomplete maxillae and cleithrum from Strud, together with the lower jaw previously recorded from this site, closely resemble the genus Ichthyostega, initially described from East Greenland. The postorbital from Strud and the maxilla from Becco do not resemble the genus Ichthyostega. They show several derived anatomical characters allowing their tentative assignment to a whatcheeriid-grade group. The new tetrapod records show that there are at least two tetrapod taxa in Belgium and almost certainly two different tetrapod taxa at Strud. This locality joins the group of Devonian tetrapod-bearing localities yielding more than one tetrapod taxon, confirming that environments favourable to early tetrapod life were often colonized by several tetrapod taxa.

THE origin of tetrapods was one of the key events in the evolution of vertebrates [START_REF] Janvier | Early Vertebrates[END_REF]Clack 2012). It gave rise to a major new group of animals that today numbers some 24,000 living species. Whereas early tetrapods from the Devonian were only known by 3 taxa at the beginning of the 1980s (Ichthyostega Säve-Söderbergh, 1932;Acanthostega Jarvik, 1952 andTulerpeton Lebedev, 1984), their number has significantly increased to reach, to date, thirteen known genera (Table 1).

The Strud quarry ("Strud northern disused quarry" sensu [START_REF] Denayer | Stratigraphy and depositional environments of the Late Famennian (Late Devonian) of Southern Belgium and characterization of the Strud locality[END_REF]) is located in the municipality of Gesves (Province of Namur, Belgium, Fig. 1). This sandstone quarry was exploited in the nineteenth century for the construction of houses in the surrounding area. During quarrying, fossils were collected and shown to the Belgian palaeontologist Maximin Lohest from Liège University. Among this material, kept in the palaeontological collections of Liège University ever since, he identified an incomplete lower jaw as belonging to the fish taxon Dendrodus traquairi (Lohest 1888, pl. VIII: 2, 5). In 2004 this lower jaw was reattributed to an Ichthyostega-like tetrapod (Clément et al. 2004) and in 2005, with the help of geologists from Liège University (L. Barchy and J.-M. Marion), the precise location of the Strud quarry was reestablished. This rediscovery gave fresh impetus to fieldwork activities, which have been continuing until now. Strud has yielded an abundant vertebrate fauna composed of actinopterygian, acanthodian, placoderm [START_REF] Olive | Devonian antiarch placoderms from Belgium revisited[END_REF]Olive et al. 2015a), and sarcopterygian fishes [START_REF] Lohest | Recherche sur les poissons des terrains paléozoïques de Belgique. Poissons des Psammites du Condroz, Famennian supérieur[END_REF][START_REF] Leriche | Les poissons famenniens de la Belgique -Les faciès du Famennien dans la région gallo-belge -Les relations entre les formations marines et les formations continentales du Dévonien supérieur sur la bordure méridionale du continent Nord-Atlantique[END_REF]Clément & Boisvert 2006). An exquisite invertebrate fauna was also recently revealed [START_REF] Garrouste | A complete insect from the Late Devonian[END_REF]Gueriau et al. 2014aGueriau et al. , b, 2016;;[START_REF] Lagebro | The oldest notostracan (Upper Devonian Strud locality, Belgium)[END_REF] as well as a diversified plant assemblage [START_REF] Prestianni | Strud: old quarry, new discoveries[END_REF]). The reader is referred to Olive et al. (2015a, table 1) and [START_REF] Denayer | Stratigraphy and depositional environments of the Late Famennian (Late Devonian) of Southern Belgium and characterization of the Strud locality[END_REF] for an exhaustive updated list of the Strud fossil content.

The Becco site is situated on a road embankment close to Becco hamlet in the municipality of Theux (Province of Liège). This Famennian vertebrate-bearing locality was recently discovered by geologists of the Liège University (J.-M. Marion and B. Mottequin) and has yielded early seed plants, antiarch, groenlandaspid and phyllolepid placoderms, diplacanthiform acanthodians, as well as actinopterygians, and dipnomorph and tetrapodomorph sarcopterygians (Olive et al. 2015b).

Here we describe new tetrapod remains from the Famennian localities of Strud and Becco

GEOLOGICAL SETTING

The Strud quarry is located in the Namur-Dinant Basin. Strata at the top of the Strud section, which provided almost all fossils, correspond to the infill sequence of a channel (lithological unit 7 or UL7) in an alluvial plain [START_REF] Garrouste | A complete insect from the Late Devonian[END_REF][START_REF] Denayer | Stratigraphy and depositional environments of the Late Famennian (Late Devonian) of Southern Belgium and characterization of the Strud locality[END_REF]. They belong to the Upper Famennian Evieux Formation and are late Famennian in age (versabiliscornuta 'Rugospora radiata' zone, VCo 'rad' zone, [START_REF] Denayer | Stratigraphy and depositional environments of the Late Famennian (Late Devonian) of Southern Belgium and characterization of the Strud locality[END_REF]Fig. 1). Tetrapod remains are extremely scarce in the Strud vertebrate assemblage. After dozens of weeks of excavation, only four isolated remains reliably attributable to tetrapods have been found in addition to the historically collected specimen. These remains have been found in beds B (IRSNB A.0006) and D (IRSNB A.0003-0005 and PALULG 6106) of lithological unit 7 (Fig. 1).

These beds correspond to the fining upward portion of the stratigraphic sequence. In the following discussion, the "Strud" designation means the uppermost channel of Strud, i.e. the top (UL7) of the Strud northern disused quarry.

The Becco locality belongs to the Theux Tectonic Window. The stratigraphic succession exposed at Becco is reduced and consists mainly of green shaly siltstone belonging to the Crupet Member (Evieux Formation, late Famennian). According to local and regional stratigraphical and sedimentological observations, this facies indicates a fluvial environment and the fossiliferous horizon most likely corresponds to a channel infill (Olive et al. 2015b).

MATERIAL AND METHODS

The Devonian tetrapod material from Strud includes the following specimens:

DESCRIPTION

Description of the tetrapod material from the Strud locality

The right postorbital IRSNB A.0006 (Fig. 2) is quite complete with only the finest distal parts of the posterior and ventral margins missing. The shape is more or less rectangular with the dorsoventral axis longer than the anteroposterior one. A well-developed anterior expansion is present on the dorsal part of the anterior margin. This anterior expansion is most probably a postfrontal process of the postorbital bone and does not seem to be the postfrontal bone fused to the postorbital. The bone is flat, except for the thickened postfrontal process. The orbital margin is relatively large with a strong elbow-like outline. The dorsal margin of the bone is sigmoid with a short overlap area for the parietal in its middle part. Thus, the parietal bone seems to slightly overlap the postorbital, at least partially. Another narrow overlap area, supposedly for the squamosal, is discernable on the posteroventral margin. The ornament consists of fine radiating pits and grooves. A long and large groove running dorsoventrally from the centre of the bone is considered as the postorbital sensory canal. In internal view the bone is quite smooth except the postfrontal process, which shows fine more or less aligned ridges.

The lower jaw (PALULG 6106, Fig. 3), described by [START_REF] Lohest | Recherche sur les poissons des terrains paléozoïques de Belgique. Poissons des Psammites du Condroz, Famennian supérieur[END_REF] as a fish fragment and reattributed by Clément et al. (2004) to an Ichthyostega-like tetrapod, includes most of the dentary except the anterior and posterior extremities, and the dorsal portions of the postsplenial and the splenial. However the suture between the two latter bones is not discernible. The splenial is strongly twisted mesially. A depressed and smooth oral groove ["sulcus oralis" of Jarvik (1996: 47)] marks the suture between the dentary and infradentaries, as seen in one of the specimens of Ichthyostega figured by Jarvik (1996: pl. 33.1). A putative mandibular canal is identified on PALULG 6106, consisting of large pores, running anteroposteriorly in the middle part of the postsplenial. The position of these aligned pores is similar to that of the partially open sensory canal in Ichthyostega (Jarvik 1996: pls. 32-33). The dentary was most probably narrow all along its length, a condition met in early tetrapods (Ahlberg & Clack 1998), but its dorsal margin does not seem to form a low crest hiding the tooth stems, as in several Devonian tetrapods. It also seems that small marginal teeth external to the main tooth row, known in Elginerpeton (Ahlberg 1995) and most of lobe-finned fishes, are here absent. The teeth are widely spaced and strongly curved posteriorly. The upper half of the dentary is ornamented with fine pits coarsening into anastomosed ridges ventrally. There is no suggestion of a radiating pattern. The internal face of the lower jaw is badly preserved. Part of the coronoid(s) is preserved but no traces of lateral coronoid teeth have been observed. This could be due to the poor preservation of the specimen but more probably to a poorly developed coronoid tooth row.

The fragments (IRSNB A.0003, Fig. 4A-E; IRSNB A.0004, Fig. 4F-G) of two right maxillae were recently collected at the Strud locality. They both suggest a narrow complete maxilla. The lateral surface is uniformly covered with coarse anastomosed ridges and pits. In internal view, there is a well developed and continuous horizontal shelf (palatal shelf), dorsally to the tooth row, which carries the sutural surfaces for the ectopterygoid and/or dermopalatine.

The teeth are almost equal in size, laterally flattened and strongly curved posteriorly, and regularly spaced if we consider the preserved teeth and tooth sockets. Marginal teeth external to the main tooth row are not observed on these maxillae fragments.

A putative cleithrum fragment (Fig. 4H) is observable in lateral view. The dorsal and ventral extremities are missing. It is elongate and proportionally thin in shape and displays a finely striate surface and a dorsoventral median furrow, as seen in Ichthyostega (Jarvik 1996: pls. 48.1, 51.1). This furrow is located between two broken weakly developed ridges tapering towards the dorsal end of the bone. The ventral part of the bone is badly preserved and the junction with the endoskeletal shoulder girdle is not observable.

Description of the Devonian tetrapod material from the Becco locality

The isolated right maxilla IRSNB A.0007 (Fig. 5) is almost complete. Due to diaclastic fragmentation of the fossiliferous layer into more or less geometric small blocks, the posterodorsal corner of the maxilla is missing. Adjacent blocks did not provide the missing piece, which must certainly be very small since the posterior end of the bone is preserved. This maxilla is a long and narrow tooth-bearing bone. Its anterior tip tapers to form an anterior process with a smooth dorsal surface. This anterior process abutted the posterior margin of the premaxilla and separated the naris (externally) and the choana (medially). The smooth surface, ventrally delimited by a deep groove, was most probably overlapped externally by the anterior tectal and/or the lacrimal. The groove itself probably housed the infraorbital sensory canal. In internal view, the smooth and concave margin of the anterior part of the bone corresponds to the posterolateral margin of the choana. Posteriorly to the anterior process, the bone rapidly deepens to its maximum depth, then gradually becomes shallower towards its posterior tip. The dorsal region of the posterior half of the bone presents externally a long and extended overlap area with thin longitudinal ridges, most probably for the jugal bone. A small, smooth and concave area on the posteroventral end of the maxilla could possibly be the overlap area for the dentary bone of the lower jaw. Internally the medial wall of the posterior end of the maxilla is smooth and slightly concave, forming the most anterior part of the lateral wall of the subtemporal fossa.

Teeth and spaces left by missing teeth indicate a total of 23 teeth. Tooth size is linked with the height of the bone. The teeth reach their maximum size on the deepest part of the bone, where two large teeth, with adjacent tooth pits, are present. The deepest point is also the widest in ventral view. The first two teeth (with one adjacent small pit), just ventrally to the naris, are small. The following two teeth (with two adjacent enlarged pits) are dramatically larger. The posterior teeth are then abruptly smaller, to regularly decrease in size until the posterior end of the maxilla. Except for the larger ones, teeth are rounded in cross section at their base, and all are more or less posteriorly curved. All teeth show longitudinal grooves running from one-third of the height from the base, marking the dentine infoldings. The medial surface of the maxilla shows, posterior to the choana, a prominent shelf ("palatal process" of Clack 1994) running parallel and dorsal to the tooth row to slowly disappear at the level of the two posteriormost teeth. This shelf was overlapped by the palatine and the ectopterygoid. Posterior to the choana a reduced medial projection could have been in firm contact with the palatine. Laterally the bone is smooth from the anterior tip to the deepest point of the bone. Its ornamentation consists in pits more or less regularly spaced, with drop-like shapes, the tips of the drops being ventrally oriented. The pits are more marked on the posterior half of the deepest part of the bone.

DISCUSSION

Comparison of the tetrapod remains from Belgium with other Devonian and Carboniferous tetrapods

Lower jaw and maxillae. The lower jaw from Strud resembles those of other Devonian tetrapods by its narrow dentary. It differs from Acanthostega by its ornament, consisting of pits in Acanthostega (Ahlberg & Clack 1998) and by the suture separating the dentary from both splenial and postsplenial, which is loose in Acanthostega. If the deep furrow marking the suture between the dentary and the (post?)splenial in Elginerpeton (Ahlberg 1995;Ahlberg & Clack 1998) is the equivalent of the "oral groove" of PALULG 6106, that could mean that both taxa share this character with Webererpeton and Obruchevichthys (Clément & Lebedev 2014). The firm attachment of the dentary to the infradentaries is also a shared character between the lower jaw from Strud, Ichthyostega and Elginerpeton. However, Elginerpeton differs by its ornament and the presence of small marginal teeth external to the main tooth row.

PALULG 6106 resembles the lower jaw of Ventastega (Ahlberg et al. 1994) by the twisted anterior part of the lateral surface but differs by the loose attachment of the dentary to the infradentaries in Ventastega and by the ornament of the dentary, which displays a smooth strip along the ventral margin, in Ventastega.

Densignathus [START_REF] Daeschler | Early tetrapod jaws from the Late Devonian of Pennsylvania, USA[END_REF] displays a loose attachment of the dentary to the infradentaries, and the lateral surface is almost devoid of ornament, two characters which were not observed on the lower jaw from Strud.

As already noticed by Clément et al. (2004), PALULG 6106 closely resembles the lower jaw of Ichthyostega by the general shape of the dentary, the dermal ornament, the dentition, and by the firm attachment of the dentary to the splenial and postsplenial (Ahlberg & Clack 1998). A well-marked oral groove is also present in some Ichthyostega specimens (e.g., Jarvik 1996: pl. 33.1), but this feature is also known in some Frasnian tetrapods (Elginerpeton, Webererpeton, Obruchevichthys). Clack et al. (2012) described Ymeria, a new Devonian tetrapod genus from East Greenland, very similar to Ichthyostega. Teeth of these two taxa differ by their shape, scarcely curved in Ymeria but clearly posteriorly curved in Ichthyostega, as seen on the lower jaw and maxillae specimens from Strud. The lower jaw of Ymeria is also almost devoid of dermal ornament.

The dentition and ornament of the fragments of maxillae from Strud correspond closely to the lower jaw, suggesting that they represent the same taxon. Like the lower jaw, they resemble the corresponding parts of Ichthyostega (Jarvik 1996: pls.6-7). They differ from Acanthostega (Clack 1994, fig. 2B;Jarvik 1996, fig. 8) by the proportionally larger teeth, and from Ventastega (Ahlberg et al. 1994, fig. 3b) by the relatively coarse ornament dominated by oblique ridges.

The maxilla from Becco differs substantially from the Strud maxillae in overall morphology, tooth shape and ornament, and evidently represents a separate taxon. Its preservation and completeness suggests that it was loosely attached, with no interdigitating sutures, to all adjacent bones (premaxilla, anterior tectal, lacrimal, jugal, quadratojugal, ectopterygoid, palatine, vomer). This feature is known in Ventastega (Ahlberg et al. 1994) and Acanthostega [START_REF] Clack | Earliest known tetrapod braincase and the evolution of the stapes and fenestra ovalis[END_REF]).

The maxilla from Becco is proportionally short compared to that of the Devonian tetrapods Acanthostega and Ventastega. The total number of teeth is also much lower, with 23 teeth or tooth pits compared to more than 40 (between 55 and 60 in Ventastega). By contrast its tooth count is close to those of Ichthyostega and Ymeria with a total number of teeth ranging between 16 and 24 [START_REF] Blom | Taxonomic revision of the Late Devonian tetrapod Ichthyostega from East Greenland[END_REF]Clack et al. 2012). Devonian tetrapods lack well-developed teeth on the maxilla, as observed anteriorly on the Becco maxilla. Enlarged teeth are present in Ventastega (Ahlberg et al. 1994), Ymeria (Clack et al. 2012) and Ichthyostega (Jarvik 1996), approximately on the same region of the bone as in the maxilla from Becco, but they are smaller and contrast less sharply with surrounding teeth. The largest teeth of Ymeria lie between positions 3 and 5. These features, together with the size proportions of the teeth, strongly recall those of the maxilla from Becco. Furthermore, the bones of Ymeria show a poorly defined ornament, although the ornament of the maxilla itself is not clearly obvious. However the dentition of the maxillae of Ymeria and from Becco differ by the gradual size reduction of the teeth from the enlarged ones to the most posterior ones. In Ichthyostega, Acanthostega, and Ventastega, the ornament of the maxilla is composed of coarse pits and anastomosed ridges, and not of small pits or by an absence of ornament as in IRSNB A.0007.

Early Carboniferous tetrapods Ossinodus from Queensland, Australia [START_REF] Thulborn | Early Carboniferous tetrapods in Australia[END_REF]Warren & Turner 2004;[START_REF] Warren | New data on Ossinodus pueri, a stem tetrapod from the Early Carboniferous of Australia[END_REF], Pederpes from Scotland (Clack & Finney 2005) and Whatcheeria from Iowa, USA [START_REF] Lombard | A new primitive tetrapod, Whatcheeria deltae, from the Lower Carboniferous of Iowa[END_REF] were all phylogenetically placed in the Whaatcheeriidae (Clack 2002a) but according to later suggestions Whatcheeriidae could be a grade rather than a clade [START_REF] Warren | New data on Ossinodus pueri, a stem tetrapod from the Early Carboniferous of Australia[END_REF]. The proportion and dentition of the maxilla from Becco are close to those of maxillae of Ossinodus [START_REF] Thulborn | Early Carboniferous tetrapods in Australia[END_REF]Warren & Turner 2004;[START_REF] Warren | New data on Ossinodus pueri, a stem tetrapod from the Early Carboniferous of Australia[END_REF]). The number of tooth loci in the Ossinodus material varies with the length of the maxilla, ranging from 33 to 42 (for a maxilla length respectively of 100 and 145 mm). Enlarged teeth are well developed, with 2 to 3 small anterior teeth. The ornament is composed of pits irregularly spaced as in IRSNB A.0007, although the ornament looks coarser in Ossinodus. The maxilla from Becco is however thinner in ventral view and the medial margin of the palatal shelf is not sinusoidal, forming well-marked embayments, as it does in Ossinodus as well as Eogyrinus and Anthracosaurus [START_REF] Panchen | The skull and skeleton of Eogyrinus attheyi Watson (Amphibia: Labyrinthodontia)[END_REF]. The maxilla from Becco is also very similar to that of Whatcheeria [START_REF] Lombard | A new primitive tetrapod, Whatcheeria deltae, from the Lower Carboniferous of Iowa[END_REF]. The latter is relatively short with approximately 33 teeth, including a large fang or fang pairs located in the anterior region of the bone. The Tournaisian (lowermost Carboniferous) taxon Pederpes from Scotland (Clack & Finney 2005) shows the left maxilla in lateral view and the anterior part of the right maxilla in ventral view. In contrast to the isolated maxilla from Becco, some large pores are present on the lateral surface of the bone in Pederpes. A total number of teeth less than 20 is suggested, with a massive tooth about position 4 to 6. Enlarged maxillary tusk at about position 5 or 6 is a feature known in the Whatcheeriidae (Clack 2002b) but some colosteid taxa also present this feature [START_REF] Smithson | The cranial morphology of Greererpeton burkemorani Romer (Amphibia: Temnospondyli)[END_REF][START_REF] Hook | Colosteus scutellatus (Newberry), a primitive temnospondyl amphibian from the Middle Pennsylvanian of Linton, Ohio[END_REF].

The proportions of the bone, a total number of teeth less than 25, enlarged maxillary fangs, abrupt size difference between the maxillary fangs and all other teeth, and ornament absent or reduced to pits are characteristics that align the maxilla IRSNB A.0007 with those of the Early Carboniferous tetrapods Ossinodus, Whatcheeria, and to a lesser extent Pederpes. Thus, the isolated maxilla IRSNB A.0007 from Becco is here provisionally referred to a whatcheeriidgrade tetrapod.

Postorbital. Few Devonian tetrapod postorbitals have been described. However, IRSNB A.0006 differs from the postorbital of Ichthyostega (Jarvik 1996), Acanthostega [START_REF] Jarvik | On the fish-like tail in the ichthyostegid stegocephalians[END_REF]Clack 2002b;[START_REF] Porro | Descriptive anatomy and threedimensional reconstruction of the skull of the early tetrapod Acanthostega gunnari Jarvik[END_REF] and an undetermined tetrapod from Russia (PIN 2921/3002, Lebedev & Clack 1993) by a long and angular orbital margin and by a well-developed ventral extension of the bone.

The postorbital from Strud strongly resembles the postorbital of Pederpes finneyae (Clack & Finney 2005) by the relative size and shape of the element, as well as the extent and squaredshape of the orbital margin. It resembles also, to a lesser extent, to the postorbital of Whatcheeria deltae [START_REF] Lombard | A new primitive tetrapod, Whatcheeria deltae, from the Lower Carboniferous of Iowa[END_REF], even if the postfrontal process and the squared-shape of the orbital margin of the latter seem less developed. Daeschler et al. (2009, fig. 5) figured postorbital bones of some early tetrapods. IRSNB A.0006 is very similar to that of an undetermined tetrapod from Red Hill (Daeschler et al. 2009, fig. 5A, ANSP 21873). The orbital margin displays a long lateral extension in both specimens and the overall elbow-like shape of the bone shows a similar squared posterodorsal corner of the orbit. The open groove of the postorbital sensory canal is located proportionally close to the orbital margin in both specimens. The posterior margin is strongly concave in ANSP 21873 (although its posterodorsal part is mainly missing) but convex in IRSNB A.0006. The dorsal margin of the latter specimen has a sigmoid line whereas it is straight on the postorbital from Red Hill. A narrow overlap area, supposedly for the squamosal, is present on the ventral margin of both specimens. The ornament is proportionally finer and covers a larger part of the surface on the postorbital from Strud, including on its postfrontal process. The postorbital from Red Hill (ANSP 21873) was assumed to indicate close relationship with a whatcheeriid-grade tetrapod. We come to the same conclusion here for the postorbital bone from Strud.

Cleithrum. IRSNB A.0005 is badly preserved but could represent an incomplete tetrapod cleithrum. If considered as such, it resembles the cleithrum of Ichthyostega (Jarvik 1996, fig. 42B) by its elongate shape, its slightly striate surface and its dorsoventral median depression.

Ichthyostega shows an important diversity in the overall shape and morphology of the cleithra, with a more or less marked dorsoventral depression. However, the ridges surrounding this depression are more clearly developed in IRSNB A.0005 than in all known complete cleithra of Ichthyostega, with the exception of one specimen (Jarvik 1996: pl. 48.1). It differs from the cleithrum of Elginerpeton (Ahlberg 1998) by a narrower cleithrum stem and from the cleithrum of Hynerpeton (Daeschler et al. 1994), Jakubsonia (Lebedev 2004) and Tulerpeton (Lebedev & Coates 1995) by a more elongate overall shape and by the presence of the dorsoventral median depression on its lateral surface. Cleithra of Ventastega (Ahlberg et al. 2008) and Acanthostega (Coates 1996, fig. 13a) are slender too but differ from IRSNB A.0005 by the absence of the dorsoventral median depression on the lateral surface.

Tetrapod diversity in Belgium

The task of recognizing a taxonomic diversity among isolated skeletal elements using morphological data always proves to be difficult (Daeschler et al. 2009). The situation of the Devonian tetrapod remains from Belgium is another example highlighting this problem. The Strud locality provided two maxilla fragments, a lower jaw, a putative cleithrum and a postorbital whereas the Becco site yielded a maxilla. The cleithrum is badly preserved, making its identification and taxonomical assignation within tetrapods rather difficult. The two maxilla fragments and the lower jaw from Strud display large and curved teeth and a well-marked ornament, and probably belong to the same taxon. They resemble the Ichthyostega material from East Greenland but are too incomplete to be formally attributable to that genus.

The isolated postorbital bone found in Strud is rather different from that of Ichthyostega and displays whatcheeriid features. We could thus consider either that there are two tetrapod taxa at the Strud locality, one with ichthyostegid and another one with whatcheeriid features, or that all these tetrapod remains from Strud are elements of a single new taxon. Such a case occurred in the past with Ossinodus pueri, a Carboniferous tetrapod of Australia (Warren & Turner 2004), the material of which was first attributed by [START_REF] Thulborn | Early Carboniferous tetrapods in Australia[END_REF] to three different taxa (an anthracosaur, a colosteid and a possible temnospondyl).

The almost complete maxilla from the Becco site is different from the maxilla fragments found at Strud. The former shows teeth proportionally smaller (except for the maxillary fangs) and much less curved, and an ornament composed of a restricted area of small pits rather of a network pits and anatomosed ridges. The maxilla IRNSB. A0007 from Becco is very similar to those known in the Early Carboniferous tetrapods of the whatcheeriid group.

The whatcheeriid-like maxilla found in Becco, very different from the Strud maxillae, argues for the presence of a whatcheeriid taxon in Belgium, which could be also represented by the postorbital from Strud. Thus, two different tetrapod taxa occurred in the Late Devonian (Famennian) of Belgium and both could be present in the Strud locality. Blieck et al. (2007[START_REF] Blieck | The biostratigraphical distribution of earliest tetrapods (Late Devonian): a revised version with comments on biodiversification[END_REF] established the biostratigraphical and palaeogeographical framework of early tetrapods. Since that study, new early tetrapod finds have been recorded. The description of Ymeria from East Greenland (Clack et al. 2012) confirmed that this area yielded the greatest number of Devonian tetrapod taxa including three species of Ichthyostega, one species of Acanthostega and one species of Ymeria. Daeschler et al. (2009) brings the total number of Devonian tetrapod genera to 13, plus at least 6 undetermined but putative new tetrapod taxa (Table 1). These recent discoveries confirm that Devonian tetrapods are mainly found in Euramerica. Only two genera have been found outside Euramerica so far, Metaxygnathus denticulus and Sinostega pani, respectively in Australia and China [START_REF] Campbell | A primitive amphibian from the Late Devonian of New South Wales[END_REF][START_REF] Zhu | First Devonian tetrapod from Asia[END_REF].

Devonian tetrapod distribution

With the occurrence of at least two Devonian tetrapod taxa in Wallonia (southeastern part of Belgium) and almost certainly two tetrapod taxa at Strud, this locality joins the group of Devonian tetrapod-bearing localities that have yielded more than one tetrapod taxon (Table 1), i.e. Red Hill in Pennsylvania with at least 3 tetrapod taxa (Daeschler et al. 2009); East Greenland with three genera and five species in Ymer Ø, and two genera and four species in Gauss Halvø; Ketleri in Latvia with two tetrapod genera (Ahlberg et al. 1994); and Andreyevka-2 in Russia with also two tetrapod genera (Lebedev & Clack 1993). It reinforces the conclusion that, already before the end of the Devonian, environments favourable to early tetrapods were in many cases supporting modestly diversified tetrapod faunas, with members distinguished by morphological characteristics that probably reflect subtly different ecological adaptations. This represents the beginning of a process of tetrapod diversification that has continued through to the present day.

  and attempt a taxonomical assignation through a comparative study with other well known Devonian and Carboniferous tetrapods. We attempt to assess the number of Devonian tetrapod taxa present in Belgium and examine the problem of evaluating animal diversity based on isolated elements. Institutional abbreviations. IRSNB, Institut royal des Sciences naturelles de Belgique, Brussels, Belgium; MNHN, Muséum national d'Histoire naturelle, Paris, France; PALULG, Palaeontological collections of the Liège University, Liège, Belgium.

  PALULG 6106: an incomplete lower jaw; IRSNB A.0003 and IRSNB A.004: fragments of right maxillae; IRSNB A.0005: a putative partial cleithrum; IRSNB A.0006: a complete right postorbital. The postorbital has been collected in bed B of lithological unit 7 whereas the other remains come from bed D in the same unit. IRSNB A.0007, an almost complete right maxilla, is the only Devonian tetrapod specimen recorded at Becco yet. PALULG 6106 and IRSNB A.0005 have been mechanically prepared, whereas IRSNB A.0003, 0004, 0006 and 0007 have been mechanically and virtually prepared in order to obtain 3D models of the entire specimens. The specimen IRSNB A.0006 has been partially mechanically prepared due to the very fine and fragile marginal regions of the postorbital bone. The virtually prepared specimens have been scanned (Computerized Tomography Scanning) at the AST-RX (Accès Scientifique à la Tomographie à Rayons X) platform of the MNHN, Paris, using the following scanning parameters: voltage = 85 kV, current = 260 µA; for IRSNB A.0003: number of slices = 1964, voxel size = 0.028 mm; for IRSNB A.0004: number of slices = 740, voxel size = 0.024 mm; for IRSNB A.0006: number of slices = 1471, voxel size = 0.023 mm; for IRSNB A.0007: number of slices = 2400, voxel size = 0.050 mm. These four specimens have been virtually reconstructed with MIMICS 16.0 (Materialise's Interactive Medical Image Control System) Software (Materialise Inc.; proprietary software at the MNHN, Paris) at the Atelier 3D, Centre de Recherche sur la Paléobiodiversité et les Paléoenvironnements, MNHN, Paris.

  demonstrated the presence of at least three early tetrapod taxa in Red Hill (Pennsylvania, USA) including the possible presence of the oldest known whatcheeriid-like tetrapod. Recently, Clément & Lebedev (2014) included a part of the material of Obruchevichthys gracilis from the Frasnian of Russia in a new taxon called Webererpeton sondalensis on the basis of different lower jaw characters. This

FIGURE CAPTIONS FIG. 1 .

 CAPTIONS1 FIGURE CAPTIONS

  Fig.2

  Fig.3

Fig. 5

 5 Fig.5

Acknowledgements. We gratefully acknowledge the Belgian Federal Science Policy Office for the research financial support (Doctoral Fellow to S. O.). We thank M. García Sanz at the X-ray Tomography Imagery Platform AST-RX of the UMS2700, MNHN, Paris, France (funded by MNHN, CNRS, Institut de France, Région Ile-de-France) for the X-ray tomography scans. Thanks are also due to F. Goussard and D. Germain (Atelier 3D, UMR 7207 MNHN/CNRS/UPMC) for their help in the 3D modelling process. Nathan Vallée-Gillette (MNHN, Paris) mechanically and virtually prepared IRSNB A.0007. W. Miseur (IRSNB, Brussels) and P. Loubry (MNHN, Paris) took the photographs. A. Folie and A. Dreze (IRSNB, Brussels) granted access to the collection of the IRSNB and provided technical support. J. Denayer (ULg, Liège) granted access to the collection of the ULg. We thank the Gesves local council staff for providing us technical support and excavation permission in Strud. We are indebted to J.-M. Marion and B. Mottequin, who discovered the Becco site and to P. Schmetz, the owner of the site, who authorized excavations. All Strud and Becco fieldworkers are also greatly acknowledged. The authors also thank the editor and reviewers for their fruitful remarks.

This paper is a contribution to the ANR TERRES 2010-BLAN-607-03 project.


Nathalie Saffon-Merceron

Marie-Claire Barthélémy

Christophe Laurent

Isabelle Fabing

Dr Pascal Hoffmann
email: pascal.hoffmann@univ-tlse3.fr

Dr Alain Vigroux
email: vigroux@chimie.ups-tlse.fr

An Unusual 3D Zinc-Organic Framework Constructed from Paddle-Wheel-Based Carboxylate Sheets Bridged by Acetate Ions

Keywords: Metal-organic frameworks, 2,6-Naphthalenedicarboxylate, Zinc, Paddle-wheel MOF, Bridging acetate ligand, Supercritical CO 2 activation

come

Introduction

Crystalline metal-organic frameworks (MOFs) have attracted considerable attention during the last decade largely because they have significantly expanded the potential capabilities of classically porous materials such as zeolites, metal oxides, or activated carbons. [1] MOFs are constructed by joining metal-containing units, referred to as secondary building units (SBUs), with organic linkers. The modular assembly of a large variety of metal SBUs and organic linkers has led to more than 20,000 different MOFs being reported and characterized within the past decade. [2] The hybrid nature of MOFs thus provides a wealth of opportunities for discovering intriguing and fascinating new structures and, more importantly, for engineering new functional materials for a wide range of potential uses including catalysis, separation, gas storage, and drug delivery. [START_REF]2012 Metal-organic frameworks issue[END_REF] One of the most common SBUs formed by metals and carboxylates is the square M 2 (O 2 CR) 4 paddle-wheel unit, in which two metal atoms are bridged by four carboxylates in syn-syn ate ions. Compound 1 exhibits large square channels (13 ϫ 13 Å), which contain DEF molecules and, alternatively, charge-balancing diethylammonium cations in situ generated by the hydrolysis of DEF under the solvothermal conditions used. The anionic host framework of 1 is unstable upon removal of guest DEF molecules suggesting that host-guest hydrogen bond interactions are crucial for maintaining the structural integrity of this compound.

mode. [4,5] These paddle-wheel units can be linked into twodimensional (2D) networks using linear dicarboxylates. In this case, the axial sites of the SBU are either unoccupied or coordinated to terminal capping ligands, typically monodentate neutral molecules. This type of arrangement, in which the paddle-wheel SBU acts as a square planar node (with four points of extension) has been observed with many different metal atoms in a vast number of 2D carboxylate MOFs, although zinc and copper are by far the most frequently encountered metals. The square M 2 (O 2 CR) 4 paddle-wheel units can also be linked into 3D frameworks by using, in addition to linear dicarboxylate linkers, bidentate neutral molecules (typically linear ditopic nitrogen donors). In this case, the paddle-wheel SBU acts as a six-connecting (octahedral) structural unit, in which the axial sites are occupied by the bidentate neutral ligands acting as pillaring agents, thus extending the 2D metaldicarboxylate layers into 3D structures. As far as it is known, 2D metal-dicarboxylate sheets have never been reported to link into a 3D framework unless neutral pillaring ligands are present in the reaction mixture. Herein, the synthesis, structural characterization, and stability of an unprecedented anionic 3D paddle-wheel-based MOF of formula unit (H 2 NEt 2 )[Zn 2 (AcO) (NDC) 2 ] (1), constructed from the linkage of zinc-2,6-naphthalenedicarboxylate (Zn-NDC) layers through axially coordinated acetate ions are reported.

Results and Discussion

The extensively studied Zn-aromatic dicarboxylic acid-DEF system (DEF = N,N-diethylformamide) are further explored for the purpose of discovering new zinc-dicarboxylate MOF structures based on commercially available linear dicarboxylate lin-kers. The synthesis of zinc-dicarboxylate MOFs is frequently performed by heating a mixture of aromatic dicarboxylic acid and zinc(II) nitrate, typically in its hexahydrate or tetrahydrate form, in a system solvent that usually contains N,N-diethylformamide (DEF) or N,N-dimethylformamide (DMF). This procedure, when carefully applied to a wide variety of rigid and linear dicarboxylic acids, reliably produces large single crystals of isoreticular MOFs (IRMOFs), which consist of Zn 4 O units connected by the dicarboxylate struts to form a common cubic topology. IRMOF-1 of formula Zn 4 O(BDC) 3 (BDC = 1,4-benzenedicarboxylate), originally named MOF-5, [6] and IRMOF-8 of formula Zn 4 O(NDC) 3 (NDC = 2,6-naphthalenedicarboxylate) are two representative structures of this series prepared under common solvothermal conditions. [7] Recently, the effect of adding small amounts of formic acid under the MOF-5 synthesis conditions was explored and the formation of new Zn-BDC MOF structures was discovered. [8] With the aim of discovering new Zn-NDC based MOFs, the phase selection effect that small amounts of added acetic acid might exert on the NDC-Zn system under solvent and reaction conditions previously described for the preparation of IRMOF-8 was similarly investigated. [7,[9][10][11]

Synthesis of (H 2 NEt 2 )[Zn 2 (AcO)(NDC) 2 ]•nDEF (1)

Initially, IRMOF-8 was synthesized using common solvothermal routes in DEF by varying metal:ligand ratios between 2 and 3.5, incubation times between 18 and 36 h, and temperature ranges between 80 and 130 °C. [7,9,12] X-ray diffraction of the single crystals so obtained indicates that the material corresponds to doubly interpenetrated phases of either IRMOF-8 or its recently described analogues. [9][10][11][12] When the latter syntheses were conducted in the presence of added acetic acid (10 equiv. relative to 2,6-naphthalenedicarboxylic acid), the corresponding IRMOF-8 crystals formed erratically during the heating period. However, within the temperature range of 80 to 130 °C, the absence of crystal formation during the first 5 h of heating was always noticed. It was therefore decided to limit the heating time to 5 h to prevent IRMOF-8 crystals from building up. By carrying out the reaction during 5 h at 130 °C, after cooling to room temperature the slow formation (5-10 d) of colorless needle-like crystals as the unique crystalline product was observed. Single-crystal and powder X-ray diffraction (PXRD) analyses (Figure 1) indicated that the framework 1 of formula (H 2 NEt 2 )[Zn 2 (AcO)(NDC) 2 ]•nDEF was obtained. However, it should be noted that small reflections in addition to those expected for phase-pure 1 are observed in Figure 1. The latter are not consistent with the PXRD data of IRMOF-8 [9] and could well result from a partial degradation of the material under the conditions used for recording the PXRD patterns, probably via the adsorption of water molecules contained in the air.

Crystal Structure

Single-crystal X-ray diffraction measurements revealed that 1 crystallizes in the tetragonal space group P4 2 /mbc. The It has been shown that anionic MOFs having diethylammonium ions as counter-cations can arise either in partially hydrated DEF [8,13] or in anhydrous DEF to which diethylammonium chloride had been added, [13] suggesting that the diethylammonium cations (either added or resulting from the hydrolysis of DEF) play a templating role in the crystallization of anionic networks. Similarly, MOFs having dimethylammonium ions as counter-cations have been described as resulting from the hydrolysis reaction of DMF. [13,14] Compound 1 is constructed from dimeric zinc clusters with a typical paddle-wheel structure, which are interconnected by NDC dianions to form a perfect 2D square-grid parallel to the ab plane. The axial sites of the Zn 2 paddle-wheel units are occupied by acetate ions, which are tightly coordinated to the zinc with a Zn1-O5 distance of 1.95(5) Å. The acetate ions unexpectedly act as bridging agents, thus giving rise to infinite anionic chains along the c axis (Figure 2). As a result, a noninterpenetrated 3D anionic architecture with large square channels of approximate dimensions 13 ϫ 13 Å is created (Figure 3). Within the infinite anionic chains, the two bridging oxygen atoms of acetates are alternatively oriented in opposite directions towards the charge-balancing diethylammonium cations. Consequently, the anionic framework of 1 exhibits channels that are alternatively occupied and unoccupied by the diethylammonium counter-cations (Figure 4).

Similarly to diethyl-or dimethylammonium cation, the formate ion derived from hydrolysis of DEF or DMF [Equation ( 1)] may also be found in the resulting framework. [8,15] However, in the present case, it is the conjugate base of added acetic acid, which has served as anionic linker. As far as it is known, compound 1 provides the first reported example of a 3D paddle-wheel-based MOF in which an anion acts as a bridging ligand to extend 2D carboxylate layers into a 3D structure.

Thermogravimetric Analysis (TGA), Flowing SC-CO 2 Activation, and N 2 Adsorption Isotherm

The thermogravimetric analysis (TGA) performed on a sample of as-synthesized 1 showed a continuous mass loss of 45 % in the temperature range 25-270 °C (Figure 5). This mass loss can be assigned to the removal of three DEF molecules and one diethylammonium acetate per formula unit (calcd. 43.8 %). The remaining residue decomposes between 320 °C and 440 °C and, according to PXRD, leads to the formation of ZnO after being heated above 450 °C. The total mass loss of the sample is about 82 %, in accordance with the calculated value of 83.6 % for (H 2 NEt 2 )[Zn 2 (AcO)(NDC) 2 ]•3DEF.

The lack of a well-defined plateau at ca. 30 % mass loss, which would have been consistent with the removal of three DEF molecules and the occurrence of a guest-free 3D framework, actually suggests that hydrogen bonded DEF molecules constitute an important element in ensuring the stability of the acetate-based 3D framework of 1. One method to assess the crystallographic aperture of 1 is to measure the BET (Brunauer-Emmett-Teller) surface area from a desolvated sample. For activating 1, it was therefore opted for the recently reported flowing supercritical CO 2 (SC-CO 2 ) procedure [16] which is often the only possibility to desolvate fragile frameworks without network transformation. [17] However, as suggested by elemental analysis (refer to Experimental Section) and TGA, activation of 1 by flowing SC-CO 2 affords a deacetylated sample, referred to as 1-SC, which exhibits a negligible BET surface area of 54 m 2 •g -1 (Figure 6), revealing a structural collapse of the framework during DEF removal.

Conclusions

A zinc-2,6-naphthalenedicarboxylate metal-organic framework (1) was solvothermally synthesized. Although 1 is based on one of the most common SBUs -the square Zn 2 (O 2 CR) 4 paddle-wheel unit -it represents the first example of a 3D paddle-wheel MOF, in which the zinc-dicarboxylate sheets are connected into a three-dimensional structure through an anionic bridging agent (i.e., the acetate ion). The resulting anionic framework of 1 exhibits large square channels containing DEF molecules and charge-balancing diethylammonium cations. Attempts to remove DEF solvent molecules without damaging the three-dimensional framework of 1 were unsuccessful, even when the relatively mild conditions of the flowing supercritical CO 2 procedure were used. It has been reported that zinc-paddle-wheel based MOFs frequently undergo partial or complete collapse due to axial ligand exchange or distortion of the dimeric zinc SBU under dry conditions. [18] Such chemical sensitivity is likely to be even more pronounced for anionic paddle-wheel frameworks like 1 as extra-framework countercations also play a crucial role in structural integrity.

Experimental Section

General: All reagents and solvents were purchased from commercial sources (Sigma Aldrich or Alfa Aesar) and were used without further purification. Synthesis of 1 was carried out in 2-5 mL glass vials. Elemental analyses were measured with a EuroVector EuroEA. Thermogravimetric analysis was performed in flowing air (heating rate 3 K•min -1 ) with a Setaram TAG-16 analyzer. The samples were held in platinum pans. Micromeritics ASAP 2020 (USA) was used to measure the surface area of the sample using nitrogen adsorption/desorption isotherms. A known amount of sample (49.1 mg) was loaded into the BET sample tube and degassed under vacuum (10 -5 Torr) at room temperature for 1 h. The BET specific surface area was calculated from the adsorption isotherm. Single-crystal X-ray diffraction were performed with a Bruker-AXS kappa APEX II Quazar diffractometer with Mo-K α radiation (λ = 0.71073 Å) at 153(2) K. The powder X-ray diffraction patterns were collected with an XPert Pro (Theta-Theta mode) Panalytical powder diffractometer with λ (Cu-K α1 , -K α1 ) = 1.54059, 1.54439 Å.

Synthesis of (H 2 NEt 2 )[Zn 2 (AcO)(NDC) 2 ]•(DEF)

n (1): 2,6-Naphthalenedicarboxylic acid (H 2 NDC, 139.7 mg, 0.64 mmol, 1.0 equiv.) and Zn(NO 3 ) 2 •6H 2 O (680.0 mg, 2.24 mmol, 3.5 equiv.) were dissolved in DEF (16 mL) containing acetic acid (366 μL, 10.0 equiv.) and sealed in a glass vial. The vial was heated to 130 °C for 5 h. After cooling to room temperature, the reaction mixture was allowed to stand 7-10 d until colorless needle-like crystals formed. The crystals were collected by filtration, washed with DEF several times and kept under fresh DEF until required for characterization. Yield: 200 mg (63 % based on H 2 BDC and n = 3). A number of attempts to obtain satisfactory elemental analysis have proved to be unsuccessful, possibly because of facile solvent loss and concomitant hydration. However, the identity of the as synthesized bulk material was confirmed by comparing the X-ray powder diffraction pattern with that simulated from the crystal structure (Figure 1).

Flowing SC-CO 2 Activation: As synthesized DEF-solvated crystals of 1 (88.7 mg) were transferred into a 2.1 mm i.d ϫ 50 mm stainless steel column. The column was connected to a supercritical CO 2 system (SFC-PICLAB Analytic apparatus equipped with HPLC K-501 Knauer pumps) with a back pressure regulator set at 100 bar. The CO 2 was pumped at a flow rate of 2 mL•min -1 and the column was heated at 35 °C through a column heater. Detection was achieved with a UV/ Vis monitor (Smartline UV 2600 Knauer detector) set at 210 nm. Under such conditions, a flowing time of 3 h was required to get zero detection. Thus, after flowing of CO 2 for 3 h, the flow was stopped and supercritical CO 2 in the column was gradually released to atmosphere. The activated sample (1-SC, 59.4 mg) in the column was transferred to a sorption cell in a N 2 glove box and the surface area was measured. Elemental analysis for 1-SC ( Structure Determination and Refinement: Intensity data for compound 1 were collected at a temperature of 153(2) K using Mo-K α radiation (wavelength = 0.71073 Å) with a Bruker-AXS APEX II Quazar diffractometer using a 30 W air-cooled microfocus source (ImS) with focusing multilayer optics. Phi-and omega scans were used. The data were integrated with SAINT, and an empirical absorption correction with SADABS was applied (SAINT; Bruker AXS Inc.: Madison, Wisconsin, 2000; SADABS, Program for data correction, Bruker-AXS). The structure was solved by direct methods, using SHELXTL Software Package, and refined using the least-squares method on F 2 . [19] All non-H atoms were treated anisotropically. The hydrogen atoms were fixed geometrically and treated as a riding model. The diethylammonium cation was found disordered over two positions. The disorder was modeled using some restraints: SAME, SADI, SIMU, DELU and ISOR. Attempts were made to model the disorder of the solvent (presumably N,N-diethylformamide) but were unsuccessful. Therefore, the SQUEEZE function of PLATON [20] was used to eliminate the contribution of the electron density in the solvent region from the intensity data, and the solvent-free model was employed for the final refinement. Crystallographic data and structure refinement results are summarized in Table 1.

Crystallographic data (excluding structure factors) for the structure in this paper have been deposited with the Cambridge Crystallographic Data Centre, CCDC, 12 Union Road, Cambridge CB21EZ, UK. Copies of the data can be obtained free of charge on quoting the depository number CCDC-1403903 for compound 1 (Fax: +44-1223-336-033; E-Mail: deposit@ccdc.cam.ac.uk, http://www.ccdc.cam.ac.uk).

Figure 1 .

 1 Figure 1. PXRD pattern simulated (1.54056 Å) from the single-crystal data of 1 (a), and measured (1.541874 Å) from a sample of 1 (b).

HCONEt 2 +

 2 H 2 O Ǟ HCO 2 H + HNEt 2 ↔ HCO 2

Figure 2 .

 2 Figure 2. View of two adjacent paddle-wheel SBUs of 1 interconnected by an acetate ion and its (disordered) diethylammonium counter-cation (color code: Zn: green; C: gray; H: white; N: blue; O: red).

Figure 3 .

 3 Figure 3. Crystal structure of 1 involving 2D paddle-wheel based Zn-NDC layers (a), interconnected by bridging acetates into a 3D framework (b) (hydrogen atoms and diethyl ammonium cations are omitted. Color code: Zn: green; N: blue; O: red; C: gray).

Figure 4 .

 4 Figure 4. (a) View of the anionic framework of 1 with channels alternatively occupied and unoccupied by the diethylammonium counter-cations. (b) Inter-layer acetate linkages involved in framework 1 with the disordered diethylammonium counter-cations. Hydrogen atoms are omitted except for the diethylammonium cations in view (a) (color code: Zn: green; C: gray; H: white; N: blue; O: red).

Figure 5 .

 5 Figure 5. TGA curve of as-synthesized 1, revealing a 45 % weight loss between 18 and 272 °C corresponding to the loss of 3DEF and one diethylammonium acetate (calcd. 43.8 %), and a total weight loss of about 82 % (calcd. 83.6 %) leading to the formation of ZnO in accordance with the molecular formula (H 2 NEt 2 )[Zn 2 (AcO)(NDC) 2 ]•3DEF.

Figure 6 .

 6 Figure 6. Nitrogen sorption isotherm of 1-SC at 77 K after activation by flowing SC-CO 2 [adsorption (ϫ) and desorption (O)].

  C 49.76, H 3.96, N 2.07 %) is in agreement with the chemical formula Zn 2 (NDC) 2 (DEF)(H 2 O) 2 (C 29 H 27 NO 11 Zn 2 : calcd. C 50.02, H 3.91, N 2.01 %).

Table 1 .

 1 Crystal data and structure refinement for 1. indices [I Ͼ 2σ(I)] R 1 = 0.0457, wR 2 = 0.1190 R indices (all data) R 1 = 0.0739, wR 2 = 0.1416 Largest diff. peak and hole /e•Å -3 0.695 and -0.537

	1


Carina Teixeira De Oliveira

Fabrice Theoleyre
email: theoleyre@unistra.fr

Andrzej Duda
email: duda@imag.fr

Broadcast Strategies with Probabilistic Delivery Guarantee in Multi-Channel Multi-Interface Wireless Mesh Networks

Multi-channel multi-interface Wireless Mesh Networks permit to spread the load across orthogonal channels to improve network capacity. Although broadcast is vital for many layer-3 protocols, proposals for taking advantage of multiple channels mostly focus on unicast transmissions. In this paper, we propose broadcast algorithms that fit any channel and interface assignment strategy. They guarantee that a broadcast packet is delivered with a minimum probability to all neighbors. Our simulations show that the proposed algorithms efficiently limit the overhead.

Introduction

Wireless Mesh Networks (WMN) have attracted increasing attention in recent years because of their low-cost and ease of deployment. These multi-hop networks are self-organized and self-configured without any centralized control. They are composed of static wireless routers and some of them act as gateways toward the Internet. In this paper, we consider WMN with routers based on the ieee 802.11 technology.

When mesh routers use a single interface (i.e. wireless network card) tuned to a single channel, the network capacity degrades with the increase of the network size due to channel contention and spatial problems such as exposed and hidden nodes [START_REF] Chaudet | Performance issues with IEEE 802.11 in ad hoc networking[END_REF]. One way of improving the performance of WMN is to use multiple non-overlapping channels (free of inter-channel interference) so that mesh routers can transmit in parallel and without collisions [START_REF] Li | How to effectively use multiple channels in wireless mesh networks[END_REF]. To take advantage of multiple channels, nodes may have multiple interfaces to simultaneously transmit/receive packets. These networks are called Multi-Channel Multi-Interface (MCMI) WMN.

It has been shown that one can significantly improve the network capacity by carefully choosing the set of channels a mesh router may use for each of its interfaces and which of them it will use to communicate with its neighbors. A pair of nodes should have sufficient channels in common with each other while minimizing interference with other active pairs.

Recently, there has been an increasing interest in developing new solutions for MCMI WMN. However, few studies considered efficient broadcast in such networks-the work done has only focused on static interface assignment in which all nodes are tuned to a common set of channels [START_REF] Qadir | Localized minimum-latency broadcasting in multi-rate wireless mesh networks[END_REF][START_REF] Yang | R-Code: Network coding based reliable broadcast in wireless mesh networks with unreliable links[END_REF]. While it is true that static approaches provide suitable stability for routing protocols without path changes, re-ordering, channel switches etc., on the other hand, these approaches do not efficiently distribute the load among all available channels. Consequently, the inability to adapt interfaces under heavy load and interference variations can drastically reduce the overall network performance. Therefore, the channel and interface assignments play a key role on MCMI WMN performance, which can not be neglected by broadcast solutions.

We propose to focus here on the broadcast problem in multi-channel multiinterface wireless mesh networks. Our contribution is threefold:

1. we introduce a classification of Channel and Interface Assignment (CIA) strategies in MCMI WMN;

2. we propose broadcast algorithms that fit any CIA strategy guaranteeing a packet is delivered with a minimum probability to all neighbors;

3. we provide simulation results to compare different strategies and choose the most suitable one for a given situation.

The rest of this paper is organized as follows. We first introduce the system model in the next section. Section 3 presents a review of relevant related work. In Section 4, we introduce the probabilistic delivery guarantee. Section 5 presents the broadcast algorithms with the probabilistic guarantee. Simulation results are presented in Section 6. Finally, we conclude the paper in Section 7.

Model and Assumptions

We model a wireless mesh network as an undirected graph G = (V, E), where V is the set of nodes (mesh routers) and E the set of edges corresponding to two nodes able to directly communicate.

We adopt the following notation: • C: the number of non-overlapping (orthogonal) channels that can be used by all nodes v ∈ V . We assume that a node can tune each of its interfaces to a set of channels c ⊆ C;

• Intf (v): the set of interfaces of node v ∈ V ;

• S(i): the schedule of interface i-a list of tuples {(channels, timeStart, timeStop)}.

The schedule may be periodical or anarchical;

• I v : the number of interfaces of node v, where

I v = I S v + I D v with I S v
denoting the number of static interfaces and I D v the number of dynamic interfaces of node v ∈ V . Two mesh routers in the transmission range of each other are able to communicate if at least one of their interfaces uses the same channel at the same instant. More formally, (u,

v) ∈ V 2 , (u, v) ∈ E if: ∃i ∈ Intf (u), ∃j ∈ Intf (v) such that S(i) ∩ S(j) = ∅ (1)

Interface Assignment

We distinguish between three types of interface assignment:

Static Interfaces

In this case, all interfaces are static and remain on a channel for a long period of time:

∀v ∈ V, I D v = 0 → I v = I S v . (2)
Figure 1(a) shows an example of static interface assignment with four channels and two interfaces. The x-axis is the time and the y-axis is the channel id. Note that each interface remains on the same channel regardless of time.

Dynamic Interfaces

In this case, all interfaces are dynamic and frequently switch from one channel to another:

∀v ∈ V, I S v = 0 → I v = I D v . (3)
Figure 1(b) presents an example of dynamic interface assignment. Note that two interfaces of a node should not use the same channel at the same instant. Otherwise, we would waste bandwidth since the pair of interfaces will interfere.

Mixed Interfaces

In this case, I S v static interfaces permanently stay on a channel and I D v dynamic interfaces frequently switch from one channel to another:

∀v ∈ V, I S v ≥ 1, I D v ≥ 1. (4)
Figure 1(c) shows an example of mixed interface assignment in which Interface 1 switches from one channel to another and Interface 2 remains tuned to channel 1.

Channel Assignment

Furthermore, we classify channel assignment according to one of the following approaches:

Common Channel Set

Static interfaces correspond to a Common Channel Set (CCS)-once a channel is assigned to an interface, it does not change.

One of the simplest set works as follows: on every node, interface 1 is assigned to channel 1, interface 2 is assigned to channel 2, and so on. CCS can also be built upon the concept of non-overlapping channels in order to reduce interference. Adya et al. simulated scenarios in which each node has two static interfaces tuned to orthogonal channels: one interface is assigned to channel 1 and the other one to channel 11 [START_REF] Adya | A multi-radio unification protocol for IEEE 802.11 wireless networks[END_REF].

Pseudo-Random

Static interfaces at different nodes may be assigned to a different set of channels. Each node locally decides which channel to allocate to static interfaces.

A simple solution consists in choosing channels at random [START_REF] Xufei | Static channel assignment for multiradio multi-channel multi-hop wireless networks[END_REF]. Another solution is to use some well-known function f of the node identifier to select the channels to assign to the static interfaces [START_REF] Kyasanur | Routing and interface assignment in multichannel multi-interface wireless networks[END_REF]. Neighbors of a node v ∈ V can use the same function f to compute the channel used by v. An alternative solution consists in explicitly exchanging hello packets that contain information about the channels used by static interfaces. Based on the received hello packets, nodes may choose to set their channels to an unused or a lightly loaded channel.

Adaptive

It uses some information or criteria to dynamically assign channels based on for instance time instants (defined or random), a pre-defined channel visiting order, the interference level, or the available bandwidth.

Finally, we distinguish between the following types of broadcast communications:

• Discovery Broadcast: a node has to discover neighbors;

• Local Broadcast: all neighbors must receive a packet;

• Flooding: a packet has to be received by all nodes in the network.

We will focus here on Local Broadcast. We considered Discovery Broadcast elsewhere [START_REF] Abdelali | Neighborhood discovery and activity monitoring in multichannel mesh networks[END_REF].

3 Related Work

Multi-channel Multi-interface Strategies

Strategies Interface Channel Ref S D M C P-R A Static/Common X X [5, 9] Static/Pseudo-Random X X [6, 10] Dynamic/Adaptive X X [11, 12] Mixed/Common & Adaptive X X X [13, 14] Mixed/Pseudo-Random & Adaptive X X X [7, 15
] Interface Assignment -S: Static, D: Dynamic, M: Mixed Channel Assignment -C: Common, P-R: Pseudo-Random, A: Adaptive A multi-channel multi-interface strategy consists of a combination of interface and channel assignments [START_REF] Si | An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks[END_REF]. We can identify the following strategies:

1. Static Interfaces/Common Channel Assignment: all interfaces are static and use the CCS approach (all nodes use channel i on the i th interface) [START_REF] Adya | A multi-radio unification protocol for IEEE 802.11 wireless networks[END_REF][START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF].

We can note that the strategy is optimal when the number of interfaces equals the number of available channels, which is seldom the case;

2. Static Interfaces/Pseudo-Random Channel Assignment: similar to the previous strategy, it assigns a channel to each interface for permanent use. However, static interfaces at different nodes may be assigned to a different set of channels [START_REF] Xufei | Static channel assignment for multiradio multi-channel multi-hop wireless networks[END_REF][START_REF] Marina | A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[END_REF].

This approach does not guarantee connectivity since two nodes may choose different channels for their interfaces. Therefore, deafness may arise;

3. Dynamic Interfaces/Adaptive Channel Assignment: all interfaces are dynamic. Thus, the topology is also dynamic: two nodes may temporarily be able to communicate until one interface switches its channel. Often, a rendezvous mechanism has to be used to avoid deafness [START_REF] Dasilva | Sequence-based rendezvous for dynamic spectrum access[END_REF][START_REF] Bahl | SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks[END_REF]. In other words, nodes can agree on the channels they will use in the next time interval. Then, channel re-assignment ensures that statistically, a node can reserve a common channel for each of its neighbors after a sufficiently long time.

4. Mixed Interfaces/Common and Adaptive Channel Assignment: static interfaces use a common channel set (CCS) while dynamic interfaces act in an on-demand manner [START_REF] So | Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[END_REF][START_REF] Tseng | A multi-channel mac protocol with power control for multi-hop mobile ad hoc networks[END_REF].

A pair of nodes may use its static interfaces to negotiate a channel for data exchange. Negotiation takes place on a dedicated control channel to isolate control RTS/CTS traffic from data.

The strategy uses all available channels with a trade-off between connectivity (static interfaces) and capacity optimization (dynamic interfaces);

5. Mixed Interfaces/Pseudo-Random and Adaptive Channel Assignment: different nodes assign their static interfaces to different channels, while the remaining interfaces switch channels in an adaptive manner. Static interfaces are used in reception while dynamic interfaces are used for transmissions. A node has just to know the list of channels used by the static interfaces of its neighbors to communicate with them: no deafness appears.

This strategy often uses one single static interface (I S v = 1) [START_REF] Kyasanur | Routing and interface assignment in multichannel multi-interface wireless networks[END_REF].

Table 1 presents an overview of all Channel and Interface Assignment (CIA) strategies.

Broadcast

Many network protocols use local broadcast for various purposes: routing, coordination, synchronization, etc. The functionality of reaching all neighbors in a local broadcast is useful in flooding and efficient flooding protocols aim at limiting the number of retransmissions. In a single channel network, one single packet is sufficient to cover all the neighbors (all neighbors receive it), because of the broadcast nature of radio transmissions.

Several papers tried to tackle the broadcast problem in multi-channel multiinterface wireless mesh networks. Qadir et al. [START_REF] Qadir | Localized minimum-latency broadcasting in multi-rate wireless mesh networks[END_REF] proposed to optimize the delay for multi-rate mesh networks. However, they focus on the global flooding problem, i.e. how each node in the network receives the flooded packets. Each node selects a subset of neighbors to forward the packet, pruning redundant transmissions. They assume a static interface assignment (Static/Common) in which all nodes are tuned to the same channels. Song et al. [START_REF] Song | Broadcasting protocols for multi-radio multi-channel and multi-rate mesh networks[END_REF] presented also independently a broadcast protocol to achieve a 100% reliability with minimum latency. They constructed a broadcasting tree using a link quality metric, but focused also on a network wide flooding. Yang et al. [START_REF] Yang | R-Code: Network coding based reliable broadcast in wireless mesh networks with unreliable links[END_REF] additionally introduced network coding to reduce the associated overhead in mesh networks.

Xing et al. [START_REF] Xing | Superimposed code based channel assignment in multi-radio multi-channel wireless mesh networks[END_REF] proposed superimposed codes to tackle both the unicast and broadcast problems in multichannel multiradio mesh networks.

In conclusion, no proposal is sufficiently generic to deal with any CIA strategy.

Probabilistic delivery guarantee

Transmission in wireless networks may suffer from errors due to various effects at PHY and MAC layers: attenuation, interference, fading, multipath propagation, synchronization errors, or collisions. Our goal is to design broadcast protocols that guarantee the reception of a broadcast packet by each neighbor with a certain probability.

Packet Error Estimation

We denote by p e bit error probability and by p p packet error probability. They are related by the following relation:

p p = 1 -(1 -p e ) size (5)
where size denotes the size in bits of a packet. p deliv is the probability of successful packet delivery p deliv = 1 -p p . Since it depends on a given radio link, we use the notation p deliv (u, v) for the transmission from u to v.

Probabilistic guarantee

We propose a probabilistic guarantee of local broadcasts. We consider that a particular neighbor is covered by a broadcast if it receives at least one copy of the corresponding packet with a probability superior or equal to p covermin , a parameter of the protocol. Higher layers may specify its value when they want to transmit a broadcast packet. A local broadcast is successful if all neighbors are covered.

Let N (v) represent the neighbors of v. We denote by p cover (u → v) the probability that node v correctly receives the broadcast of node u, i.e., v is covered. Our protocol will imply that

∀v ∈ N (u), p cover (u → v) ≥ p covermin . (6)
To provide guarantees, we limit the links to those with packet error probability of at least p pmax , i.e. a node does not maintain radio links of low quality.

Broadcast Algorithms

In this section, we introduce the broadcast algorithms based on the classification proposed in Section 3.1.

Static Interfaces with Common Channel Assignment

With the common channel assignment, the i th channel is assigned to the i th static interface, so there is no deafness. Thus, broadcast is simple: a node has just to broadcast a packet through any of its static interfaces and all its neighbors will receive it.

A node has to send as many copies of the packet as required to cover each of its neighbors with the expected probability. If we consider packet losses uncorrelated among the different copies, the probability the node v receives at least one of the k copies from u is:

p cover (u → v) = 1 -(1 -p deliv (u, v)) k (7)
Finally, a node has to send the following number of copies so that v receives the packet with a probability superior to p covermin :

K = log(1 -p covermin ) log(1 -p deliv (u, v)) (8)
The link with the smallest p deliv will determine the lower bound of the number of copies to transmit. When only one static interface is tuned to the control channel, we can use this interface to send broadcast packets. However, the whole control traffic is concentrated on the control channel thus leading to its high utilization for large broadcast load.

We can apply this approach to Strategies 1 and 4 (those that use a Common Channel Set) in Section 3.1.

Static Interfaces with Pseudo-Random Channel Assignment

With this kind of assignment, a single transmission is not sufficient for local broadcast, because not all neighbors use the same channel. A node may have to send several packets so that all its neighbors become covered through different channels. In this strategy, each node knows the list of its neighbors and their static channels (this is a feature of the unicast protocol): a node will also use this information for its broadcast transmissions.

We propose a greedy approach inspired by MultiPoint-Relays [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF]: a node chooses the minimum number of channels that cover the largest number of neighbors (cf. Algorithm 1). More precisely, a node proceeds in the following way:

• a node constructs the list of its neighbors (i.e. all the nodes with which it has a common channel uncovered (Algorithm 1, lines 1 -6).

• while at least one neighbor is covered with a probability inferior to p covermin , the node searches for the channel with the best quality:

it counts the number of newly covered neighbors for each channel (their covering probability is inferior to p covermin );

it randomly chooses one of the best channels (to balance the load among channels);

for each neighbor reachable through this channel, it updates the probability of reception. It corresponds to the delivery probability for the link (u, v) if u did not yet schedule a packet for v. Otherwise, it recursively applies Equation 9.

p cover (u, v) = 1 -(1 -p cover (u, v)) (1 -p deliv (u, v)) (9)
We can apply this approach to Strategies 2 and 5 in Section 3.1 that use static interfaces to receive packets.

Dynamic Interfaces with Adaptive Channel Assignment

When a node only uses dynamic interfaces, it needs to avoid deafness by correctly choosing both an interface and a schedule. We propose the Algorithm 2.

A node first creates the schedule of its interfaces and thus of its neighbors: a node knows the channel switching instants of all its neighbors for all their . We consider in this example a neighbor covered if it received at least one copy interfaces (otherwise transmissions are impossible due to deafness). It constructs timeslots so that itself and all its neighbors stay tuned to the same channel during one timeslot. We do not require all the nodes to switch their channels at the same time. Let us consider the example in Figure 2 in which timeslots are delimited by dashed lines: the first interface of node v 1 stays tuned to the same channel during timeslots 1 and 2 while the second interface switches between both timeslots. The schedule consists of a kind of the lowest common denominator between the different channel switching instants for all neighbors. After having constructed this schedule, the transmitter is able to compute the number of neighbors that can be covered for each interface for each timeslot (i.e. when the channels match). Thus, it will re-iterate by greedily choosing pairs <timeslot,interface> that cover the largest number of not yet covered neighbors. When a node sends a copy of a broadcast packet, it updates the probability of delivery for each neighbor, adopting the same approach as Algorithm 1 (lines 15 -20). The algorithm stops when all the neighbors are covered 0.95 with a probability superior to p covermin . Let us consider the example in Figure 2. We consider in this example a neighbor covered if it received at least one copy. As explained previously, v 1 first computes timeslots (dashed lines). Then, it chooses the neighbors reachable through each interface for each timeslot and applies the greedy algorithm. For instance, node v 1 can reach node v 3 during the first timeslot through its first interface and node v 4 through the second interface of v 4 . Finally, node v 1 may choose timeslot 1 via its first interface to cover v 3 , v 4 and timeslot 1 via its third interface to reach node v 2 .

This algorithm can apply to the strategy that only uses dynamic interfaces (Strategy 3 in Section 3.1).

Performance Evaluation

We have implemented a simulator to evaluate the broadcast performance * [20]. We assume the ideal MAC layer to focus on broadcast performance with no collision. We generate random positions of nodes and plot 95% confidence intervals. We use the standard values depicted in Table 2. The simulation measures:

1. the overhead defined as the average number of transmissions required by a node to cover all its neighbors; 2. the Jain Index of the load for all the channels to measure fairness. Let B c denotes the bandwidth consumed by the broadcast on channel c:

JainIndex = C c=1 B c 2 C • C c=1 B 2 c ( 10
)
We denote each strategy as introduced in Section 3.1 and apply the broadcast algorithms defined in the previous section. In particular, we have implemented the Dynamic/Adaptive strategy in a way that each interface equally shares its time among all the channels following a pseudo-random sequence [START_REF] Bahl | SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks[END_REF]. Two nodes are able to exchange packets if at least one pair of interfaces uses the same channel at the same instant.

Packet Error Rate

Simulation takes into account packet error probability through the Packet Error Rate (PER) model represented in Figure 3 [START_REF] Camp | Measurement driven deployment of a two-tier urban mesh access network[END_REF] that shows the relation between the PER and the distance. As explained above, the neighbors with a PER superior to p pmax have not to be covered. For the numerical results, we have chosen the value of p pmax = 0.5 although different values would lead to consistently the same results. The Dynamic/Adaptive strategy shows a limited overhead by greedily choosing the most suitable channels. The Static/Pseudo-Random strategy requires a little less broadcast packets (7 transmissions). Indeed, this strategy results in lower connectivity: two nodes may be in the radio range with each other, but may not share a common static channel. In this case, this kind of a virtual neighbor is not anymore a neighbor in the multi-channel topology and has not to be covered. This mechanically reduces the overhead. The probability of such configuration is smaller with dynamic interfaces since we increase the probability that a pair of nodes has at least one channel in common at a given instant.

Network cardinality

Finally, the Mixed/Pseudo-Random & Adaptive strategy presents the worst overhead, because it uses only one static interface, which reduces the possibilities to re-use one single transmission to cover several neighbors.

We have also evaluated fairness between different channels with the Jain Index (Figure 4 Other strategies lead to almost perfect fairness: they efficiently spread the broadcast traffic through orthogonal channels reducing the risk of congestion. In particular, the Static/Common strategy does not use a single control channel, leading to a good fairness.

Density

We have also evaluated the impact of the density on the overhead while maintaining the number of nodes constant (cf. Figure 5). Only Static/Common and Mixed/Common & Adaptive strategies have the same overhead, which is perfectly scalable, because they have a common channel set.

The overhead created by Algorithm 1 applied to the Static/Pseudo-Random slightly increases with the density: the greedy approach succeeds to better take advantage of transmissions. This growth is more important when we use dynamic interfaces as more timeslots are necessary to cover the interface schedule of new neighbors.

The Mixed/Pseudo-Random & Adaptive strategy keeps on presenting the worst overhead since only one static interface is used for reception limiting the possibilities to use one single packet to cover several neighbors.

In conclusion, our greedy strategies are particularly efficient in minimizing the overhead when the density is large.

Number of interfaces

We have also considered the influence of the number of interfaces (cf. Figure 6) on the overhead.

The Dynamic/Adaptive and the Static/Pseudo-Random strategies tend to have initially a growing overhead: the number of neighbors to be covered increases since they have more chance to have a common timeslot. Then, the overhead decreases when it exceeds a threshold since the probability of having different neighbors that use the same channel increases with the number of interfaces. The Dynamic/Adaptive begins to be more attractive when the number of interfaces is large compared to the number of channels (> 3 interfaces). Finally, for a very large number of interfaces (> 8), these strategies tend to be similar to the common channel strategies.

The strategies using a common channel for broadcast are not impacted by the number of interfaces. Besides, the Mixed/Pseudo-Random & Adaptive strategy presents also a constant overhead since the unique receiving interface keeps on being the bottleneck.

Impact of threshold p cover min

Finally, we have measured the impact of threshold p covermin on the overhead in Figure 7. When p covermin = 0.5, each neighbor is covered when the transmitter sends one single copy: we discard radio links with a larger PER, considering them unreliable. Thus, strategies with a common channel set required only one broadcast transmissions to cover all the neighbors.

When p covermin increases, the overhead becomes larger: neighbors with a large packet error probability may require the transmission of several copies. However, we can note that all the strategies follow the same trend. The overhead becomes prohibitive when we require very large p covermin (e.g. ≈ 0.99). Thus, the network protocols have to cope with broadcast unreliability. In particular, they should work in a self-stabilizing manner: even if some neighbors do not receive a particular broadcast packet, the protocol must work properly.

Conclusion and Future Work

We have proposed algorithms for local broadcast in multi-channel multiinterface wireless mesh networks. In particular, they can cope with dynamic interfaces without a common control channel. To the best of our knowledge, these algorithms are the first ones to cope with deafness in this situation. Simulations show that all the strategies have an acceptable overhead and the load is fairly distributed among channels when the Common Channel Set strategy is not used. A greedy approach is particularly efficient to take advantage of the broadcast nature of transmissions.

We plan to study how we can deal with multiple rates: different bit rates may cover a different set of neighbors with different PER. We also plan to adapt the proposed strategies to dynamic conditions adopting an opportunistic approach. Besides, we aim at optimizing the delay, e.g. consider the question of which timeslot would present the best trade-off between the delay and the overhead when we use dynamic interfaces.

Figure 1 :

 1 Figure 1: Examples of interface assignment with 4 channels and 2 interfaces.

Figure 2 :

 2 Figure 2: Local broadcast with mixed interfaces-each color of the bars represents a different channel and we report the list of neighbors reachable through each of v 1 interfaces at any instant (v 1 has 3 interfaces, v 2 and v 3 one interface, and v 4 2 interfaces). We consider in this example a neighbor covered if it received at least one copy

Figure 3 :

 3 Figure 3: Impact of the distance between the receiver and the transmitter on the Packet Error Rate (PER).

Figure 4 (

 4 Figure 4(a) presents the overhead in function of the number of nodes when maintaining constant density. The Static/Common and Mixed/Common & Adaptive strategies have the same minimal overhead: no deafness arises and all neighbors receive a broadcast transmission. Since some neighbors may present a non-null Packet Error Rate, several non acknowledged broadcasts are required before considering they are covered.The Dynamic/Adaptive strategy shows a limited overhead by greedily choosing the most suitable channels. The Static/Pseudo-Random strategy requires a little less broadcast packets (7 transmissions). Indeed, this strategy results in lower connectivity: two nodes may be in the radio range with each other, but may not share a common static channel. In this case, this kind of a virtual neighbor is not anymore a neighbor in the multi-channel topology and has

Figure 4 :

 4 Figure 4: Impact of the number of nodes, 10 avg. neighbors, 3 interfaces, 12 channels

  (b)). Mixed Interfaces with Common/Adaptive Channel assign-

Figure 5 :

 5 Figure 5: Impact of the density on the overhead, 200 nodes, 3 interfaces, 12 channels

Figure 6 :

 6 Figure 6: Impact of the number of interfaces on the overhead, 200 nodes, 10 avg. neighbors, 12 channels

Figure 7 :

 7 Figure 7: Impact of threshold p covermin on the overhead, 200 nodes, 10 avg. neighbors, 3 interfaces, 12 channels

Table 1 :

 1 Channel and Interface Assignment (CIA) Strategies

Algorithm 1 :

 1 Greedy Selection for Static Interfaces with Pseudo-Random Channel Assignment

	1 /* initialization	*/
	2 /* neighs ≡ {(neigh, channel)}	*/
	3 neighs [] ←getListNeighStaticIntf() ;
	4 /* initially, no neighbor is covered	*/
	5 for i ∈ [0..|neighs|] do
	6	Pcover [i] ←0 ;
	7 /* if at least one uncovered neighbor exists	*/
	8 while (∃n ∈ neighs such that Pcover[n] < p covermin ) do
	9	/* count the nb of neighbors covered for each channel. */
	10	for c ∈ [0..|channels|] do
	11	nbCovered [c] ←nbNeighsCovered(c) ;
	12	/* select one of the best channels	*/
	21	/* send one broadcast packet	*/
	22	sendBroadcast(bestChannel) ;

13 bestChannel ←rand(nbCovered) ; 14 /* update the Pcover proba for each newly covered neighbor */ 15 for n ∈ neighUsing(bestChannel) do 16 /* this neighbor was not yet covered at all */ 17 if Pcover [n] = 0 then 18 Pcover [n] ← Pdeliv [n] ; 19 else 20 Pcover [n] ← 1 -(1 -Pcover[n]) • (1 -Pdeliv[n]) ;

Table 2 :

 2 Default parameter values

	Parameter	Default value
	Number of nodes	200
	Density (avg. number of neighbors)	10
	Number of interfaces	3
	Number of channels	12
	p covermin (probability above which we
	consider the node is covered)

Acknowledgments

This work was supported in part by the French Government (MESR) and the Competitive Clusters Minalogic and System@tic under contracts FUI SensCity as well as the French National Research Agency (ANR) project ARESA2 ANR-09-VERS-017.

simulator is freely available at http://forge.imag.fr/projects/graphsim in the subversion repository