Marceau Coupechoux
email: marceau.coupechoux@alcatel.fr

Bruno Baynat

Christian Bonnet

Vinod Kumar

CROMA: An Enhanced Slotted MAC Protocol for MANETs

Keywords: Mobile ad hoc networks, MAC, conict-free protocol, scheduling, dynamic slot allocation, TDMA

TDMA based MAC protocols can provide a very good utilization of the shared radio resources, especially at high input loads, in synchronized mobile ad hoc networks (MANETs). Global positioning systems like GPS or GALLILEO should provide a very good timing accuracy for synchronization of nodes. This paper presents a new medium access protocol for mobile ad hoc networks, called CROMA. CROMA is collision-free and receiver-oriented. It operates in a slotted environment, in a dynamic and distributed way. In this protocol, receivers act as local base stations and can manage one or several communications on a single slot. Thus, sophisticated functions are allowed at higher layers. Moreover, the hidden terminal as well as the exposed terminal problems are handled byCROMA. A theoretical analysis and extensive simulations show that CROMA can reachvery high throughputs.

Introduction

In recentyears a lot of eort has been spent in the design of protocols for mobile ad hoc networks. Such packet networks are mobile and multihop and operate without any xed infrastructure. This can be a low cost and easily deployable technology to provide high speed Internet access in a wireless environment, to organize networks of sensors, or to complement the coverage of future cellular networks.

In this paper, wepay special attention to the medium access control (MAC) sub-layer. It has a lot of impact on the system performance and its design is a very challenging issue. MAC should control access to the medium and share the channel between source-destination pairs and/or ows of data in a dynamic and distributed way. Some desirable features of the access protocol are: to be able to reuse the resources as eciently as possible, to avoid congestion and collisions, to be fair, reliable, and energy ecient.

ManyMAC protocols try to address these issues. In the literature two categories of schemes have been proposed: (i) the contention based schemes; (ii) the conict-free schemes.

In the contention based protocols, the channel has to be acquired by the nodes for each packet to be transmitted. Examples of contention based schemes are CSMA/CA, MACA [START_REF] Karn | MACA -a New Channel Access Method for Packet Radio[END_REF], MACAW [START_REF] Bharghavan | MACAW: A Media Access Protocol for Wireless LAN's[END_REF], FAMA [START_REF] Fullmer | Solutions to Hidden Terminal Problems in Wireless Networks[END_REF], IEEE 802.11 [START_REF]ANSI/IEEE Std 802.11, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specications[END_REF]. The latter seems to be very popular in most of the testbeds because the IEEE 802.11 family products are available o the shelf. Although IEEE 802.11 is exible, robust and simple, a recent paper [START_REF] Xu | Does the IEEE 802.11 MAC Protocol Work Well in Multihop Wireless Ad Hoc Networks?[END_REF] claims that it may not do very well in a multi-hop environment. According to [START_REF] Xu | Does the IEEE 802.11 MAC Protocol Work Well in Multihop Wireless Ad Hoc Networks?[END_REF], 802.11 has still the hidden terminal problem, does not handle the exposed terminal problem at all and its backo strategy leads to severe unfairness. In this family of protocols, MACA-BI [START_REF] Talucci | MACA-BI (MACA byi n vitation) -A Receiver Oriented Access Protocol for Wireless Multihop Networks[END_REF]was the rst one to be receiver oriented, i.e., the transmission of a packet is initiated by the receiver that sends a short control packet in order to reserve the channel and to invite the sender to transmit. As the receiver does not have the exact knowledge of packet queue at the sender, it must rely on a trac prediction algorithm.

On the other hand, conict-free protocols allow the reservation of the channel for a certain amount of time or data and transmissions are conict-free. TDMA deterministic scheduling may be preferred for networks with heavy load, carrying mixed trac and realizing sophisticated functions at higher layers. That is the reason whywe propose in this paper a slot allocation protocol for mobile ad hoc networks.

Unfortunately, most of the scheduling problems are NP-complete. For example, Arikan [START_REF] Arikan | Some Complexity Results about Packet Radio Networks[END_REF] has shown that constructing an optimal schedule for the point-to-pointscheduling problem to optimize throughput is NP-complete. And this is the same for the broadcast scheduling problem based on throughput optimization, as proved by Ephremides and Truong [START_REF] Ephremides | Scheduling Broadcasts in Multihop Radio Networks[END_REF]. Consequently,M A C designers have focused on suboptimal, dynamic and decentralized solutions for the slot assignment problem.

A rst class of scheduling protocols relies on the allocation of priorities to nodes. A given slot is assigned preferably to the node with the highest priority according to its oered trac. Slots can be allocated by using a control channel, e.g. in [START_REF] Cidon | Distributed Assignment Algorithms for Multihop Packet Radio Networks[END_REF]. Priorities of the neighbors are assumed to be known at each node and are allocated in a pseudorandom wayasin [START_REF] Bao | A New Approach to Channel Access Scheduling for Ad Hoc Networks[END_REF]. Then dierent strategies can be applied for the allocation of the priorities in order to have a fair and ecient share of monet.tex; 5/01/2004; 11:42; p.2 CROMA -an Enhanced Slotted MAC Protocol for MANETs 3 the channel (see e.g. [START_REF] Ramanathan | A Unied Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks[END_REF]). However, some of these protocols suer from a high overhead due to the control channel. Others do not address the problem of the distributed and dynamic assignment of priorities.

On the other hand, time-spread protocols seem to be very attractive because they are topology-independent (see e.g. [START_REF] Chlamtac | Time-Spread Multiple-Access (TSMA) Protocols for Multihop Mobile Radio Networks[END_REF] or [START_REF] Ju | An Optimal Topology-TransparentS c heduling Method in Multihop Packet Radio Networks[END_REF]). However, the frame length makes them less scalable and this class of protocols also faces the problem of distributed and dynamic code assignment.

At last, the necessity to address the problem of mobility, topology changes, and scalability, gives rise to a family of protocols where the reservation of the slots is done via a random access, most of the time a handshaking, combined with a carrier sensing mechanism. FPRP [START_REF] Zhu | A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks[END_REF] proposes a ve-phase handshaking supported by a pseudo-Bayesian algorithm to enable a faster convergence of the reservation procedure. CATA [START_REF] Tang | A Protocol for Topology-Dependent Transmission Scheduling in Wireless Networks[END_REF] uses four mini-slots in each time-slot to enable unicast and multicast transmissions. The protocol proposed in this paper comes within this family of protocols. It tries to make use of the advantages of the most popular contention based protocols to a slotted environment in order to increase their eciency. In particular, the aim of CROMA is to achieve a high slot utilization, i.e., a high capacity, at high input load thanks to an original reservation and polling scheme.

The paper is organized as follows. In section 2, we give a precise description of our proposed MAC protocol. We examine the correctness of this protocol in section 3. Section 4 gives an analytical study of the protocol in a fully connected network. At last, section 6 is the conclusion of the paper.

Protocol Description

The Collision-free Receiver-Oriented MAC (CROMA) is a medium access protocol for mobile ad hoc networks that schedules transmissions in a slotted environment. It is a dynamic and distributed protocol that operates on a single-frequency channel with omni-directional antennas. CROMA has been shortly presented in [START_REF] Coupechoux | CROMA -a New Medium Access Protocol for Mobile Ad hoc Networks[END_REF] and [START_REF] Coupechoux | Modeling of a Slotted MAC Protocol for MANETs[END_REF]. The present paper gives a full description of the protocol, integrates new advanced features, and provides an enhanced performance analysis.

In CROMA, time is divided into frames, each of them divided into a xed number L of time-slots. Each slot can be temporarily and locally attributed to the receiver of a communication link depending on topology changes and trac patterns. When a receiver is occupying a slot, it is allowed to poll several senders among its neighbors. The number of current communications for each slot is however limited by the protocol to a pre-dened value K. The polling packet sentby the receiver is used to reserve the channel and to invite a sender to send a data packet. In that sense, CROMA is a receiver-oriented protocol since a slot in the frame is associated to a single receiver.

CROMA doesn't rely on a trac prediction algorithm at the receiver. Indeed, a requesting node has to reserve resources at its intended receiver during a random access phase. This reservation is needed only at the beginning of a packet train (or message). When a receiver has no longer trac to poll, communications are released and the slot is free for another receiver.

Frame Structure

CROMA divides time into frames that are, in turn, divided into L equal time-slots. All mobile nodes are assumed to be perfectly synchronized.

Synchronization is a very critical issue for CROMA as for all distributed TDMA systems. A possible solution, nowatlow cost, consists in making use of the GPS (Global Positioning System) that provides a global synchronization for all nodes. Also the european satellite navigation system, GALILEO, will provide a very good timing accuracy [START_REF]European Commission, esa, Galileo Mission High Level Denition v3.0[END_REF]. In this case, guard intervals have to be foreseen. Another way of research is local synchronization, where nodes try to synchronize themselves by exchanging beacons with their neighborhood [START_REF] Elson | Time Synchronization for Wireless Sensor Networks[END_REF] [START_REF] Elson | Fine-Grained Time Synchronization using Reference Broadcasts[END_REF]. The algorithms proposed in the literature can be adapted in order to be used with CROMA. However, as in [START_REF] Zhu | A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks[END_REF] and [START_REF] Tang | A Protocol for Topology-Dependent Transmission Scheduling in Wireless Networks[END_REF], this paper focuses on the protocol description and considers that synchronization is a realistic assumption.

Throughout this paper, the following terminology has been chosen: a requesting node is a node that has data packets to send but has not yet succeeded in the reservation phase, its intendedr e c eiver is the destination node of these data packets. A sender is a node that succeeded in the reservation phase and that transmits data packets when it is polled by the receiver. A receiver is a node that polls senders on a given slot. At last, we will clearly distinguish the sender/receiver pair of a communication as dened earlier from the source/destination pair of a packet, that can be dierent for control packets.

Each time-slot is divided into three parts: two mini-slots, called REQ-mini-slot (request) and RTR-mini-slot (ready to receive) for the signaling, and a data transmission phase, called DATA-mini-slot (see Figure 1).

The REQ-mini-slot is used by requesting nodes during the random access phase for sending a REQ to its intended receiver. The RTR-minislot is used by their intended receivers to acknowledge requests as well as previous data transmissions, and to poll one of the senders that previously managed a successful reservation. During the DATA-mini-slot, the sender that has been polled in the RTR-mini-slot transmits a data packet. These data packets are of xed length. Indeed, it is assumed that a higher layer is responsible for fragmentation and reassembly.

CROMA from an Example

Before going into more details in the protocol description, let us illustrate the key feature of CROMA that is to allowmultiple reservations on the same slot. The receiver indeed maintains a list of senders that managed a successful reservation and will poll them in the successive frames. This feature is illustrated on Figure 2, which shows two successive reservations on the same slot i. In frame j, the REQ/RTR dialogue starts the connection between nodes A and B: A sends a REQ packet with its address. B sends backaR TR, that contains a eld to acknowledge the reservation (ackreq), and a eld to poll node A (pol). The RTR is also received by node C that is nowa w are of a communication on slot i with B as receiver. During the data phase, A, that has just been polled by B, is allowed to transmit a packet to B with its address A and a sequence number (sn) 0. Wesay that B has got the oor on slot i. In frame j +

The choice of a receiver-oriented protocol

The choice of a receiver-oriented protocol is justied by the following arguments:

(i) this is a \natural" choice since only the zone that has to be secured with respect to collisions is the zone around the receiver, and thus, the spatial reuse of the radio resources is favored;

(ii) this choice allows the multiplexing of several communications on a single slot. That implies ner ow control and QoS negociation. If a slot is associated to a sender, it cannot easily multiplex communications with dierent receivers since they may not be available because of a hidden terminal;

(iii) if a slot is associated to a receiver, a current communication on a given slot does not prevent a random access on this slot. More bandwidth for the contention for the channel implies less collisions and interference. If a slot is associated to a sender, it has to send at each frame a control packet (RTS) to give the address of its intended receiver. Moreover, the receiver has to respond with another control packet (CTS) in order to avoid the hidden terminal problem. In CROMA, once the reservation has been done, the REQ is not used any more for the duration of the communication, and the REQ-mini-slot can be used for new reservations. 2.4. Packet Formats This section describes the dierent packet formats and the MAC header of the data packets. It gives also the denition of all the MAC elds. Their signication will become clearer in the protocol description (sections 2.

Common Parts

In Figure 3, the control packet formats and the MAC header of the data packets are shown. In all packets, generic information not described in this paper, like the protocol version, are given in the eld fc that stands for frame control. The eld fcs (frame check sequence) contains a CRC (cyclic redundancy code) calculated on all the elds of the MAC header and on the frame body. The eld source.ad gives the ethernet address of the source of the packet.

Note that all packets, including data packets, have a xed size, and each mini-slot is just long enough to allow the transmission of the associated packet. For example, the time to transmit a REQ including additional bits from the physical layer, the transmit-to-receive turn around time, as well as a small time interval to takeinto account the propagation delays equal the time of the REQ-mini-slot. Note also that it is preferred that the size of the control packets are short compared to the length of the data packets (e.g. 512 bytes).

REQ Control Packet

In a REQ, the eld dest.ad gives the ethernet address of the destination of the packet (the intended receiver). The eld qs is used by a requesting node to indicate to the intended receiver the requested quality of service for the communication. This eld may be used by higher layers to negociate the QoS. It will be used in future versions of the protocol.

RTR Control Packet

ARTR has three dierent functions, as illustrated in section 2.2 and on Figure 2: respond to a REQ, poll the dierent senders on the current slot and acknowledge data packets.

In the RTR, the elds req.ad and r are used to reply to the requests sent on the same slot (during the REQ-mini-slot). If a request is correctly received and accepted, it is acknowledged by putting the address of the requesting node in the eld req.ad and the value ACK in the eld r. If a request has been correctly received, but the communication can't be established, the eld r is set to NACK. This situation is possible if the requested QoS is not allowed or if the number of current communications has reached its maximum, K. If the receiver detects a collision of REQs, r is set to COL. If the receiver didn't received any request, or if the request can't be decoded because of the channel conditions, r is set to NOTRECVD. The values NACK, COL, and NOTRECVD are useful information for the requesting nodes to reschedule their requests.

The eld polled.ad is used by a receiver to poll a sender that previously managed to establish a connection on this slot. If a sender reads its address in the eld polled.ad, it is allowed to send a data packet during the DATA-mini-slot of the same slot, just after receiving the RTR.

The acknowledgement of data packets is done thanks to the eld sn that stands for sequence number. Each node maintains a counter that is incremented for each new data packet. Receivers keep the last received sequence number. If in time-slot i of frame j, a receiver has received a data packet with sequence number m, it sets the eld sn to m in the RTR of the slot i of frame j +1 and so, acknowledges the previous data packet.

The byte n ofaR TR gives information about the slot utilization. It is decomposed into seven bits that indicate the number k of current communications, and one bit t to inform that the receiver will not accept requests on this slot anymore. More details on the use of the bit or if the bit t is set to 1, no more request can be done on this slot.

Data Packets

In data packets, the eld dest.ad gives the address of the destination of the packet.

As previously explained, each sender maintains a counter that is incremented for each new packet. This sequence number is put in the eld sn and is used by the receiver to acknowledge the reception of the packet. Let us recall that data packets have a xed size, that results of a higher layer segmentation or aggregation.

Reservation

Any communication between two nodes must be preceded by a preliminary reservation phase. In the reservation phase, requesting nodes contend to get access to a receiver. This access is done in a random way during the REQ-mini-slots and consists of ve sub-phases: listening of an entire frame, choice of a time-slot, transmission of the REQ on the chosen slot, listening of the RTR, and retry of a new reservation phase in case of failure (with or without random backo). These ve subphases are now detailed.

Frame Listening

The rst phase of the reservation consists in listening to the RTR-minislots during an entire frame, and maintaining for each slot in the frame the state of the slot. This listening process starts at the beginning of the reservation phase and lasts until the reservation has succeeded.

A slot can be in several states: FREE: no activity has been sensed during the RTR-mini-slot, i.e., no receiver has got the oor on this slot. A request will be possible on this type of slot.

OCC-NA: i.e., occupied and not available. This is the case if a RTR has a source.ad dierent from the address of the intended receiver or if the requesting node has detected a collision during the RTR-minislot, or if it didn't managed to decode the eld source.ad in the RTR, or if the requesting node is itself a receiver on this slot. This is also the case if the eld k of byte n has reached the maximum number of communications on a slot or if the bit t of byte n is equal to 1. Note that a RTR collision detected on a slot does not necessary mean that the slot is free in a multi-hop situation. A request won't be possible on this slot.

OCC-A-COL-k: i.e., occupied, available, collision, and k communications. In this case, the source.ad of the RTR is the address of the intended receiver, a collision has been detected by the receiver during the REQ-mini-slot (r = COL in the RTR), and there are currently k<Kcommunications on the slot. A request will be possible on this slot.

OCC-A-NCOL-k: i.e., occupied, available, no collision, and k communications. In this case, the source.ad of the RTR is the address of the intended receiver, no collision has been detected by the receiver during the REQ-mini-slot (r 6 = COL in the RTR), and there are currently k<Kcommunications on the slot. A request will be possible on this slot.

It is important to emphasize that the slot states are updated continuously during the whole reservation phase. In order to reduce the energy consumption, slot states updates can be however limited to a few frames before the reservation process.

Choosing a Time-Slot

The choice of the time-slot depends on the chosen scheduling policy. This policy mayhave several objectives. For example, it may maximize the slot utilization, limit the amounto fi n terference in the network, establish connections that are robust to mobility. The impact of this choice is not detailed in this paper. We present here a simple policy that favors free slots rst and therefore, aims at maximizing the slot utilization: in Section 2.4.3. Otherwise, the intended receiver doesn't reply. (Note however that the intended receiver maybeaware that the slot is occupied, which can happen in a hidden terminal conguration. In this case, the receiver doesn't answer to the request. See Section 3 for more details.) (ii) the sender has chosen a slot that is already occupied by the intended receiver. In this case, the intended receiver replies with an RTR whether it can decode or not the REQ.

Listening of the RTR and decision

A requesting node that has sent a REQ during the rst mini-slot of the chosen slot listens to the following RTR-mini-slot. Table I gives a summary of the decisions of the requesting node after the RTR-minislot.

If the eld req.ad has been set to its address and r to ACK, the requesting node enters the transmission phase. If r indicates a collision, the random backo algorithm is started. In all other cases, the requesting node is allowed to restart the reservation phase at the next frame. The random backo algorithm is thus only used when a high load is detected for the intended receiver. The backo algorithm starts when a requesting node has been informed that a collision occurred. An integer BO is randomly chosen between 1 and BACKOFFWND. This is a timer that is decremented at the beginning of each frame and each time the requesting node senses a slot in state OCC-A or FREE.AssoonasBO reaches 0, a slot is chosen on the forthcoming frame according to the scheduling policy for a new request. With this algorithm, the load on the available slots is taken into account.

The parameter BACKOFFWND is increased byamultiplicative factor (1:5) at each successive retransmission and decreased by one at each success. However, there are a lower and an upper bound for it, called BOmin and BOmax, e.g., 2 and 32.

Transmission

A sender whose request has been successful on a given slot starts its transmission phase. During a transmission phase, receivers of which resource has been reserved in the reservation phase, do a polling among their associated senders. When a sender recognizes its address in the eld polled.ad of the RTR, it sends in the same slot a data packet during the DATA-mini-slot. Each sender maintains a counter of its transmissions that is incremented at each new packet. This sequence number is copied in the eld sn of the packet header. With this method, the receiver is able to acknowledge the last correctly received data packet. For that, a receiver copies in the eld sn the sequence number of the last received packet. At the sender side, a sent data packet is stored until the receipt of the acknowledgement. If the next RTR is not received or if this RTR does not acknowledge the stored packet, a retransmission is necessary. After M retransmissions the stored packet is thrown away. This loss can be treated by an upper layer. Figure 4 shows an example of a transmission phase with a receiver and three senders. It only shows slots i of successive frames. On the upper part of the gure, the RTRs of the receiver are represented with the elds polled.ad and sn. A cyclic polling is pictured for the scheduling of the senders and data packets are shown with their eld sn.

It is clear that each receiver acts on a given slot as a local basestation with respect to its associated senders. Thus, the polling mechanism allows a high exibility for the scheduling of dierent o ws by higher layers and is a base for the implementation of QoS algorithms. Moreover, several parallel communications are possible on a given time-slot. Figure4 . Polling during the transmission phase.

monet.tex; 5/01/2004; 11:42; p.12 2.7. Release

An established communication can be interrupted in three cases: (i) the sender informs the receiver that it sends the last packet of the communication by setting the eld sn of the packet's header to the value EOT (end of transmission). If the last packet is correctly received, the receiver does not re-schedule the sender any more. However, it acknowledges the last packet with its next RTR, and this, even if it has no sender to poll;

(ii) if a receiver has polled a sender and doesn't receiveany packet from the sender, a counter set to W is decremented. When this counter reaches 0, the communication is released, and the receiver doesn't poll the sender any more. If after a poll, a packet is received, the counter is set again to W. After each polling, a sender starts a timer. If it doesn't receivea n y polling from the receiver when the timer expires, the connection is considered to be broken;

(iii) during a communication, a sender may receive several RTRs, i.e., there is a collision of RTRs. In this case, the sender considers that the current communication on this slot is released. Indeed, sending a data packet could imply a collision during the DATA-mini-slot. More precisions about this specic aspect are given in section 3.

Fairness Issue

CROMA includes a mechanism to assure a local fairness among data ows. On a given time-slot, fairness among incoming ows is assured by the receiver of the slot by means of the RTRs. By using dierent polling strategy, a receiver can easily give a fair allocation of the slot to incoming ows.

However, if the number of slots in the frame is small compared to the number of potential receivers, situations of unfairness can arise and ows can be completly starved. The bit t included in the RTRs is used in order to avoid such situations.

A receiver having the oor on a given slot counts the number of consecutive full frames. A frame is full from the point of view of a receiver, if it senses ativity at each slot of the frame. In this case, it detects a potential blocking situation for pair of nodes that cannot communicate because there are no free slots any more. If the number of monitored full frames reaches MAX FULLFRAMES, the receiver sets the bit t to 1 indicating that it will not accept new requests and that the current communications have to be released.

A sender detecting a bit t set to 1, sets the eld sn of its next packet's header to EOT and stops sending packets to the receiver. This release is done even if the sender have still packets to transmit. A requesting node detecting a bit t set to 1 in a RTR update the slot state to OCC-NA.

This strategy aims at avoiding blocking situations that can lead to unfairness. Indeed, these cases are detected by the receivers that have to free their slot if the situation lasts. In this section, we will show that CROMA is correct, i.e., that it is collision-free in both xed and mobile environment. The capture eect is not considered here, so this section shows that CROMA is collision-free in the common case provided that a sender releases its communication as soon as it detects a collision of RTRs.

Correctness

Let us rst consider a xed and multi-hop topology.W enow prove that two data packets cannot collide.

We suppose that a collision of two data packets occurs at a receiver R 1 . These packets have been sentbytwo dierent senders, namely S 1 and S 2 . During the RTR-mini-slot, R 1 specied the MAC address of the sender, say S 1 , that was allowed to send its data in the current slot.

As the MAC address is unique, a single colliding data packet is destined to R 1 . Therefore, we know that the data packet of S 2 was destined to another receiver, R 2 .

Now, as R 1 has received a data packet from S 2 and links are bidirectional, S 2 has received the RTR of R 1 . Moreover, S 2 has also received a RTR from R 2 , since it sent a data packet destined to R 2 . Thus, S 2 has detected a collision of RTRs in the current slot without interrupting its communication with R 2 . This is impossible. As a conclusion, no data collision can occur in a xed topology.

Let us now consider the case of a dynamic topology.Two concurrent communications on a slot are shown on the top of Figure 5, from node 1 to node 2 and from node 3 to node 4. These communications are sharing the same slot in frame j and they are far away enough, so that they don't interfere. In case of mobility and at the next frame j +1,node3 can either stay out of range of nodes 1 and 2, enter the communication range of 1, 2, or both 1 and 2. Same alternatives can occur for node 4. Thus, after mobility, a total of 16 relative new positions are possible. Because of the symmetry of the problem, only 10 cases are shown on Figure 5.

The left hand side of Figure 5 shows situations, where a single communication is interrupted because the sender detected a collision of RTRs on the considered slot. For example, in case b, node 4 moved in the transmission range of nodes 1 and 2. In frame j + 1, nodes 2 and 4 send simultaneously an RTR. Node 3 receives correctly the polling of 4, whereas node 1 senses a collision during the RTR-mini-slot. Node 1 decides to interrupt the communication with node 2 and does not send any data packet on this slot. If node 1 has still packet in its buer, it has to enter a new reservation phase.

The central part of Figure 5 shows exposed-terminal topologies, where both communications can still share the same slot. In case e, node 4 moved in the transmission range of node 2. In frame j +1, node 1 (resp. 3) decodes the RTR of node 2 (resp. 4) because it is out of the transmission range of node 4 (resp. 2). Both nodes 1 and 3 can send data packet during the DATA-mini-slot.

The right hand side of Figure 5 shows topologies, where communications are released because both senders detected a collision of RTRs. Case j shows a conguration where the network of nodes is fully connected after mobility. Here, RTRs of nodes 2 and 4 collide at nodes 1 and 3. On detecting the collision, they decide to interrupt their communication.

So, in the common case, in both xed and mobile environment, CROMA is collision-free. As in all protocols that rely on the exchange of short control packets, the capture eect mayh o w ever aect this conclusion.

Analytical Study

In this section we calculate the approximate throughput, i.e., the slot utilization of the protocol CROMA in a fully connected network. Following [START_REF] Tang | A Protocol for Topology-Dependent Transmission Scheduling in Wireless Networks[END_REF], we claim that this topology is the worst case in terms of interference, contention, and spatial reuse because CROMA guarantees a collision-free transmission of data after reservation in a multi-hop environment.

Model for the Slot Utilization Analysis

First of all, we describe our analytical model for the slotted MAC protocol CROMA. From this model will be derived the slot utilization of CROMA as a function of the probability p to send a REQ for a given source-destination pair. Let's enumerate the hypothesis of our model.

1. We consider a fully-connected network of N synchronized nodes; 2. all packets are of constant length and are transmitted over an assumed noiseless channel; 3. there are L slots per frame; 4. the maximum number of connections on a slot is K, i.e., when a receiver is already polling K dierent senders on a slot, no new REQ is allowed; 5. a receiver can only be associated with a single slot. This hypothesis can be in practice relaxed, but for the sake of tractability of the model, we limit the analysis to this case; 6. a node can be a sender on several slots of the frame. While being in communication on a slot, a node can send a REQ on another slot of the frame to start another connection; 7. the trac between anytwo nodes s and d is a ON/OFF trac; 8. the ON periods are modeled by bursts of packets following a geometrical distribution. The length of a message follows a geometrical law with parameter q.T hus, the average message length (AML) is 1=(1 q); 9. the OFF periods are modeled by series of slots without transmission following a geometrical distribution. This hypothesis explains that we can consider a xed probability p to start a communication. The system is described by the number of parallel connections on the slots at the end of the frame, (a 0 ;a 1 ; :::; a L 1 ), where a i is the number of current connections on slot i, 0 a i MIN(K; N 1) (see hypothesis 1 and 4), S = P L 1 i=0 1 fa i >0g MIN(N; L), (see hypothesis 3 and 5).

For the sake of simplicity, the states describe neither the receiver associated to each slot, nor the list of associated senders. The vector (a 0 ;a 1 ; :::; a L 1 ) is a discrete-time stochastic process, whose state space is also discrete. Moreover, this process is independent of its history because the geometric law is memoryless. Consequently, this process is a discrete time Markovchain (DTMC). Since the state space is aperiodic and nite, the chain is always ergodic.

From a frame to another, we can have the following transitions on slot i: a i ! a i +1(a i <K ): a reservation has been successful on slot i AND no communication has come to the end, a i ! a i : (there is a successful reservation AND this is the end of a communication) OR (there is no successful reservation AND no message is ending), a i ! a i 1(a i >0): there is no successful reservation AND this is the end of a communication. A transition probabilityb e t w een the two states (a 0 ;a 1 ; :::; a L 1 ) and (b 0 ;b 1 ; :::; b L 1 ) is assumed to be the product of the transition probabilities associated to each slot: P a 0 ;a 1 ; :::; a L 1 ! b 0 ;b 1 ; :::

; b L 1 = L 1 Y i=0 P a i ! b i : 1
Results will show that this assumption is a good approximation.

One Slot Analysis

In this section, L = 1. In this simple case, we can derive a closed-form formula for the slot utilization.

r 0,0 r 0,1 r 1,0 r 1,1 r K-1,K-1 r K-1,K r K,K-1 r K,K K-1 K ...
Figure6 . Discrete time Markovchain representing the state of the slot, for K N.

The system is described by the number of parallel connections on the considered slot at the end of the frame (the DTMC is shown on Figure 6). Let's now compute the transition probabilities r i;j of this Markovchain. Remember that the probability for a source-destination pair to enter a ON period is p.T hus, the probability that a node sends a request on a free slot is the probability that this node has a request for at least one of the destinations:

p 0 =1 (1 p) N 1 :
(2)

Thus, on a free slot, a successful reservation occurs i only one single node among N is sending a request during the REQ-mini-slot. Consequently the probabilitytoha v e a successful reservation on a free slot is

(0) = N 1 p 0 (1 p 0 ) N 1 : (3)
On an occupied slot with n connections, a receiver has got the oor on the slot and successively polls n senders that managed to reserve resources. Here, a successful reservation occurs i only a single node among the N (n + 1) nodes not currently in connection is sending a request. Therefore, the probabilitytoha v e a successful reservation on an occupied slot is

(n)= N (n+1) 1 p(1 p) N n+1 1 : (4)
In state 0 n<K, there is a transition to state n+1 i a successful request is received and this is not the end of the current communication.

The transition state r n;n+1 is thus given by: r n;n+1 = (n)q:

(5)

In state 0 <n<K , there is a transition to state n 1 i there is no successful request and this is the end of a communication, so

r n;n 1 =(1 ( n ))(1 q) : (6)
monet.tex; 5/01/2004; 11:42; p.18

From these two equations, we obtain directly r n;n for 0 <n<K: r n;n =1 r n;n+1 r n;n 1 : [START_REF] Chlamtac | Time-Spread Multiple-Access (TSMA) Protocols for Multihop Mobile Radio Networks[END_REF] In state 0, the slot is free and so r 0;1 = (0) and r 0;0 =1 r 0;1 .In state K, r K;K =1 r K;K 1 . The transition matrix is given by: P = fr i;j g 0i;jK :

(8) The stationary probabilities are obtained by solving the steady state equations = P, that enable to express all the probabilities in function of 0 :

n = 0 1 q q 1 q n 1 n 1 Y k=0 (k) 1 (k +1) ; (9)
for all n 2f1;;Kg. The system is totally described with the following equation: P K n=0 n =1.At last, the slot utilization of the protocol is given by U =1 0 :

U=1 1 1+ P K n=1 1 1 q h q 1 q i n 1 Q n 1 k=0 k 1 k+1 : ( 10
)
Figure 7 shows the slot utilization of CROMA, U, as a function of the probability p for K =3,N= 5 and dierenta v erage message length (AML = 2, 10 and 100 packets). Dotted curves have been obtained by simulations. These simulations reproduce the hypothesis of our model. We can see on the one hand that the approximations of the analysis have a small impact on the performance evaluation. On the other hand, it is clear that CROMA can achieveavery high slot utilization provided that the average message length is high.

From the DTMC, the average number of connections, N c on the slot can also be derived:

N c = K X n=0
n n : [START_REF] Elson | Time Synchronization for Wireless Sensor Networks[END_REF] Figure 8 shows the average number of connections for dierent AML values. This mean number is clearly related to the delay of transmission of a burst because the higher the number of connections on a slot is, the smaller is the resource allocated to a single connection. Thus, a trade-o has to be made between slot utilization and delay.

Multi-slot Analysis

In this section, we extend the previous result to the general case with L slots. We rst compute the transition probabilities, while distinguishing an occupied slot, a free slot and a full slot. For the sake of readability, we only consider the case K N.

Let's consider a slot i occupied by the receiver d (this is the case, where 0 <a i <K). The number of nodes that are likely to send a REQ to d are nodes that are currently not in communication with d, their number is N 1 a i . The probability for suchan od esto send a REQ on slot i is p (see hypothesis 9). Thus, the probability of a successful reservation is:

i = N 1 a i 1 p (1 p) N 1 a i 1 : (12)
Note that if a i = N 1, all nodes have a connection with the considered receiver, so that there is no REQ on this slot, and i =0 .N o w the probability that a message is ending is (see hypothesis 8): 1 q.W e can now derive the transition probabilities for slot i: P(a i ! a i +1) = i q

P(a i ! a i )= i (1 q)+q(1 i )

P(a i ! a i 1 )=( 1 i )(1 q)

Let's now consider a free slot i (a i = 0). There are S = P L 1 i=0 1 fa i >0g occupied slots in the frame, i.e., S receivers, since a receiver is associated to a single slot (see hypothesis 5).

On the considered free slot i, N senders are likely to send a REQ for N S possible receivers. Indeed, a node is allowed to send trac to several receivers in parallel on dierent slots, so all nodes are likely to start a new communication on i. Moreover, requests on i can be addressed to anyoftheN Snodes that are not receivers on another slot because i is not attributed.

Let's consider a node s. The probability that s has n REQ for the N S possible receivers is

p 1 (n)= N S n p n (1 p) N S n (16)
if s also belongs to the S receivers, and

p 2 (n)= N S 1 n p n (1 p) N S n 1 (17)
otherwise. Thus, the probability that s has n requests is:

p(n)=p 1 (n) S N +p 2 (n) N S N : (18)
Now, the probability that s sends a REQ on the free slot i is:

= N S X n=1
Pr[s sends a REQ on ijs sends n REQ]p(n) At last, there are N possible senders like s, so the transitions probabilities for i are:

P (0 ! 1) = N 1
(1 ) N 1 [START_REF] Luo | A New Model for Packet Scheduling in Multihop Wireless Networks[END_REF] P (0 ! 0) = 1 P (0 ! 1) (21) Let's at last consider a full slot (a i = K). The transition probabilities are obvious:

P (K ! K)= i (1 q)+q(1 i ) (22)
P (K ! K 1) = 1 P (K ! K) : [START_REF] Ramanathan | A Unied Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks[END_REF] The steady state equations = P are solved using anynumerical method, e.g., the iterative method of Gauss-Seidel (see [START_REF] Baynat | Th eorie des les d'attente, des cha înes de Markov aux r eseaux a forme produit[END_REF]or [START_REF] Stewart | An Introduction to the Numerical Solution of Markov Chains[END_REF]).

Figure 9 shows the slot utilization of CROMA as a function of p for dierentaverage message lengths. Analysis and simulations (dotted lines) are compared and the gure shows a good adequation of the two methods. As for L =1,we can see that CROMA can achievevery high slot utilization provided that the AML is high. Note that values of p near 1 are not realistic in a real implementation because of the backo algorithm. Simulations show that the point of operation of a highly loaded CROMA network with backo is always for p<0:5. shows the inuence of K on the system performance. There is a clear gain of channel utilization as K increases. However, this is obtained at the cost of higher delays. This is shown on Figure 11, where the average number of connections per slot is plotted. A higher number of connections per slot implies a higher delay for the burst transmissions.

Performance Analysis in a Multi-hop Environment

In this section, we provide simulation results and the performance of CROMA and of the standard IEEE 802.11 DCF mode are compared.

Methodology

Studying MAC protocols in a multi-hop environnment leads to the problem of chosing an appropriate node's topology. Literature on ad hoc networks has solved the problem by considering on the one hand typical networks, like the string network, or the grid network, and on the other hand randomly generated networks. In this paper, we adopted part of the two approaches by running CROMA over a classical and challenging network and over a random network.

We will now describe the metrics used to evaluate the performance of the MAC protocols.

End-to-end delay: this is the average time spentb y a packet from the trac generator of a source to the reception module of the destination.

End-to-end delay jitter: this is the standard deviation of the end-to-end packet delay.

Aggregate throughput: this is the average number of bits successfully received by all nodes in the network per second. The input load is the average number of bits transmitted by all nodes per second.

Fairness index: this is the widely used index, f , dened in [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems[END_REF]. If a system allocates resources to n contending entities, such that the i th entity receives an allocation x i , then:

f (x)= n X i =1 x i ! 2 n n X i=1 x 2 i
: [START_REF] Ramaswami | Distributed Scheduling of Broadcasts in a Radio Network[END_REF] If all entities get the same amount, i.e., x i 's are all equal, then the fairness index is 1 and the system is 100% fair. The choice of the metric depends upon the application. In our case, we will consider that the entities are the ows of data between source-destination pairs (i; j ) and the metric is their throughput, T i;j .

Performance in a Challenging Environment

Throughput and Delay Analysis

In order to evaluate the performance of CROMA in ad hoc networks, we considered a very simple multi-hop situation that has been used in the literature for the evaluation of MAC protocols, e.g. in [START_REF] Garcia-Luna-Aceves | Floor Acquisition Multiple Access (FAMA) in Single-Channel Wireless Networks[END_REF]. Nodes are assumed to be static, the trac is ON/OFF with exponential distributions, and the packet size is set to 512 bytes. Moreover, the channel is supposed to be perfect with a physical data rate of 2 Mbps. The transmission area of a node is a disk of radius R. Outside of the transmission area no communication is possible. Simulations have been done using the Network Simulator v2 (ns2, see [21]). The simulation parameter values are presented in Table II. Note that the mean OFF time is xed and that the mean ON time will vary in simulations. In this conguration, eight nodes form a regular topology,ows of data are shown on Figure 12. Four end-to-end communications are running in parallel: 0-1-2-3, 0-5-2-7, 7-6-5-4, and 3-6-1-4, so that several nodes have to receive and/or to relay several ows of data. A solid line without arrowb e t w een two nodes means that they are in the communication range of each other, i.e., the transmissions from one of them can be successfully decoded by the other one. A solid line with arrow means that at least one ow of data is using this link. (i) it exhibits a lot of hidden terminal situations. For example, nodes 6 and 2 are hidden from node 0, nodes 7 and 3 are hidden from node 5;

(ii) spatial reuse is possible and there are situations of exposed terminal. For exemple, nodes 1 and 2 are exposed. Several ows can share the same slot, e.g., 1-4 and 2-7, or 4-0 and 7-3;

(iii) nodes and ows experience dierent contention situations, nodes 0, 3, 4, and 7 have three neighbors, while nodes 1, 2, 5, and 6 haveve neighbors. In the case of low input load, IEEE 802.11 outperforms CROMA because the low level of contention implies a small number of collisions and small backo windows. At this level of load, the network cannot fully take advantage of the reservation scheme because trains of packets are small.

In the case of higher input load, IEEE 802.11 nodes experience more contention, and thus more collisions and wider backo windows: the access delay increases drastically. On the other side CROMA takes advantage of packet bursts to reduce the number of requests per trans-mitted packet. If a ow has made a successful reservation, long trains of packets can be transmitted without contention. Delays and jitters of CROMA L = 8 remains however always above IEEE 802.11's performance. It is clear that CROMA L = 8 is not well dimensionned for the topology. Actually, the number of slots is too high and the resource is not fully exploited, as it is shown on Figure 15. Toovercome this problem, a higher layer can split a link layer connection into two seperate CROMA connections. The slot utilization of CROMA L =8 does not exceed 0:75. This is much less than CROMA L = 6 that reaches 0:97. CROMA L = 3 and 4 fully exploit spatial reuse and exceed 1:1.

The reservation scheme, the synchronization, and the abilityofCRO-MA to handle the exposed terminal problem allow the network to achieve high throughputs. Figure 16 shows aggregate throughput as a function of the input load. IEEE 802.11 saturates at a throughput of 300 Kbps. In comparison, CROMA L =8a c hieves a maximum throughput 350 Kbps, although wehave seen that it is obviously badly dimensionned for the topology.C R OMA L = 6 reaches a maximum throughput of 425 Kbps. For less slots per frame, a problem of stability of the throughput arises. Although CROMA L =3and4achieve resp. 475 and 510 Kbps, the throughput decreases for input loads higher than 525 Kbps. Indeed, the small number of slots implies a slight instability with the considered topology.H o w ever, curves show a slow decrease leading to acceptable values even at high input load.

Fairness Analysis

Without any fairness strategy and without the use of the bit t, blocking situations can lead to severe unfairness. This is particularly the case when the input load is high and the number of slots per frame is small for the considered topology/trac pattern. For example in the topology of the Figure 12 with L = 4, if node 1 hears the RTRs of node 2 on slot 0, node 5 on slot 2, node 6 on slot 3, and sends RTRs on slot 1, 1 cannot send any REQ since the frame is full. In case of low input load, this situation is transient and has a low impact on the long term fairness. In case of high input load however, the connection 3-4 is completly starved leading to severe unfairness.

Figures 17 and18 shows the benet of use of the bit t with the aforementionned fairness strategy. The fairness index of CROMA L =3 and L = 4 are compared to the index of IEEE 802.11. For the IEEE standard and for CROMA without the use of the t, the index is close to 1 for low to moderate input load. After a threshold, the increase of input load leads to a drop of the index. This threshold is 350 Kbps for IEEE 802.11, and approximatly 700 Kbps for CROMA. With the use of the bit t, the fairness index of CROMA remains always above0:95 for both L = 3 and L =4.

Performance in a Random Network

In the previous section, we compared IEEE 802.11 and CROMA over a simple and pre-dened multi-hop topology. In this section, we consider a random connex network. [START_REF] Zhu | A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks[END_REF] to be exponential ON/OFF with the same parameters as in the previous section. Figure 20 shows the aggregate throughput of the network as Figure 21 shows the mean end-to-end delay of the data packets as a function of the input load. It is clear that the better performance of CROMA in term of throughput is obtained at the expense of higher packet delays and jitters at low input load (see Figure 22). In this case, IEEE 802.11 outperforms CROMA. However, CROMA allows to extend the area of acceptable delay and jitter by one third. For exemple, CROMA L = 6 still exhibits delays under 600 ms at an input load of monet.tex; 5/01/2004; 11:42; p. [START_REF] Zhu | A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks[END_REF] CROMA -an Enhanced Slotted MAC Protocol for MANETs 31 700 Kbps. Note also that at low input load, the frame length of CROMA has little inuence on the end-to-end delay. In term of fairness, CROMA still outperforms IEEE 802.11 in a random topology as shown on Figure 23. Note that it is very dicult to get statiscally satisfying results over random topologies because of the simulation time. However, ten dierent random connex networks (not shown here) have been simulated and provide similar results.

Conclusion

In this paper, a new MAC protocol, called CROMA has been proposed for mobile ad hoc networks. CROMA operates in a slotted environment, it is collision-free and receiver-oriented. The reservation of the resources is made through a random access phase on each slot of the frame. The transmission is done thanks to a polling by the receivers. Thus, receivers of a connection act as local base-stations and sophisticated functions at higher layers can be easily implemented.

The correctness of CROMA has been proven. Even with a dynamic topology,CROMA handles both the hidden and the exposed terminal problems.

Theoretical performance analyses and extensive simulations show that CROMA can reachv ery high throughput in a fully connected network provided that the average message length is large. Moreover, CROMA outperforms IEEE 802.11 at high input load thanks to a better channel utilization.

Figure1.

  Figure1 . Frame structure of CROMA.

  Figure5 . Interference between two communications sharing the same slot.

1Figure7.Figure8.

  Figure7 . Slot utilization vs. input load,L=1,N=5,K=3.

1Figure9.

  Figure9 . Slot utilization vs. input load,L=3 ,N=5 ,K=3 .

Figure 10 .Figure 11 .

 1011 Figure 10. Slot utilization vs. input load, inuence of K,L=3,N=5,AML=10.

Figure 12 .

 12 Figure 12. Amulithop topology, the \squares topology".

Figures 13 and 14

 14 Figures 13 and 14 show the end-to-end packet delay and jitter as function of the input load for IEEE 802.11 and CROMA. The dierent curves for CROMA assume dierentnumber of slots per frame.In the case of low input load, IEEE 802.11 outperforms CROMA because the low level of contention implies a small number of collisions and small backo windows. At this level of load, the network cannot fully take advantage of the reservation scheme because trains of packets are small.In the case of higher input load, IEEE 802.11 nodes experience more contention, and thus more collisions and wider backo windows: the access delay increases drastically. On the other side CROMA takes advantage of packet bursts to reduce the number of requests per trans-

Figure 18 .

 18 Figure 18. Fairness index vs. input load,L=4 ,squares topology.

  nodes are drawn at random in a 1000mx1000m square area, eachn o d eh a ving a transmission range of 250 m. This network is shown on Figure 19. 10 connections are established between 10 random pairs of nodes. The trac is assumed M. Coupechoux et al.

Figure 19 .

 19 Figure 19. Random topology with 30 nodes in a 1000mx1000m area.a function of the input load. While IEEE 802.11 and CROMA L =8 saturate at a load of approximatly 500 Kbps, CROMA L =6,L=4, and L = 3 reach resp. 600, 700, and 750 Kbps.

Figure 20 .

 20 Figure 20. Throughput vs. input load, random topology.

Figure 21

 21 Figure 21. End-to-end delay vs. input load, random topology.

Figure 22 .

 22 Figure 22. End-to-end delay jitter vs. input load, random topology.

Figure 23 .

 23 Figure 23. Fairness index vs. input load, random topology.

Table I .

 I Decision of a requesting node after listening to the RTR-mini-slot

	Reception	req.ad	r	Decision
	RTR decoded	my address	ACK	enter the transmission phase
		my address	NACK	retry on next frame
		not my address	-	retry on next frame
		broadcast address NOTRECVD retry on next frame
		broadcast address COL	start backo algorithm
	RTR not received or decoded -	-	retry on next frame
	2.5.5. Backo Algorithm

Table II .

 II Main Parameter Values for Simulations

	Parameter	Value
	DATAPacket size	512 bytes
	BOmin	2
	BOmax	64
	K	3
	W	3
	M	7
	MAX FULLFRAMES	30
	Inter-mini-slot time	10 s
	PHY overhead	24 bytes
	PHY Data Rate	2 Mbps
	ON distribution	Exponential
	OFF distribution	Exponential
	Peak Rate	256 Kbps
	Mean OFF time	0.5 s
	Simulation time	200 s
	Numberofsimulations per point	10
	This conguration is interesting for several reasons:
	monet.tex; 5/01/2004; 11:42; p.25

  Figure 13. End-to-end delay vs. input load, squares topology.

							Slot Utilization vs. Input Load
			1.4
					Croma L=3
					Croma L=4
					Croma L=6
			1.2		Croma L=8
			1
	Slot Utilization		0.6 0.8
			0.4
			0.2
							Packet Delay vs. Input Load
			1
			0.9 0 0	IEEE 802.11 Croma L=3 100 200 Croma L=4 Croma L=6	300	400 Input Load [kbps] 500 600	700	800	900	1000
					Croma L=8
			0.8
	0.7 Figure 15. Slot utilization vs. input load, squares topology.
	0.5 0.6 500 550 Packet delay [s] 0.4		IEEE 802.11 Croma L=3 Croma L=4 Croma L=6 Croma L=8		Throughput vs. Input Load
		450
			0.3
		400
			0.2
	Throughput [kbps]	0 0.1 250 300 350	50	100	150	200	250 Input Load [kbps] 300	350	400	450	500
		200
		150
		100
			50	0	100	200	300	400	500	600	700	800	900	1000
							Packet Delay Jitter vs. Input Load Input Load [kbps]
			1
					IEEE 802.11
					Croma L=3
	0.9 Figure 16. Throughput vs. input load, squares topology. Croma L=4 Croma L=6
					Croma L=8
			0.8
			0.7
	Packet Delay Jitter [s]	0.4 0.5 0.6
			0.3
			0.2
			0.1
			0	50	100	150	200	250		300	350	400	450	500
								Input Load [kbps]
	Figure 14. End-to-end delay jitter vs. input load, squares topology.
										monet.tex; 5/01/2004; 11:42; p.26

  Figure 17. Fairness index vs. input load,L=3 ,squares topology.

	CROMA -an Enhanced Slotted MAC Protocol for MANETs	29
							Fairness Index vs. Input Load, L = 3
		1
				IEEE 802.11
				Croma without bit t
		0.98		Croma with bit t
		0.96
		0.94
	Fairness Index	0.9 0.92
		0.88
		0.86
		0.84
		0.82	0	100	200	300	400	500	600	700	800	900	1000
							Input Load [kbps]
							Fairness Index vs. Input Load, L = 4
		1
				IEEE 802.11
				Croma without bit t
		0.95		Croma with bit t
		0.9
		0.85
	Fairness Index	0.75 0.8
		0.7
		0.65
		0.6
		0.55	0	100	200	300	400	500	600	700	800	900	1000
							Input Load [kbps]
									monet.tex; 5/01/2004; 11:42; p.28

monet.tex; 5/01/2004; 11:42; p.4

monet.tex; 5/01/2004; 11:42; p.5

monet.tex; 5/01/2004; 11:42; p.6 CROMA -an Enhanced Slotted MAC Protocol for MANETs

monet.tex; 5/01/2004; 11:42; p.7

t for fairness are given in section 2.8. If k has reached the maximum K monet.tex; 5/01/2004; 11:42; p.8

monet.tex; 5/01/2004; 11:42; p.9

If there is at least one slot in state FREE, choose one randomly and exit, otherwise go to step 2;

If there is at least one slot in state OCC-A, select the slots having the lowest value of k. Among slots in this set: a If there is at least one slot in state OCC-A-NCOL, choose one randomly and exit, otherwise go to step 2.b; b Otherwise, choose one slot in state OCC-A-COL randomly and exit; Otherwise restart the reservation phase at the next frame.2.5.3. Transmission of the request and RTR generationOn the chosen slot, the reservation is done by sending a REQ during the REQ-mini-slot. Two cases must now be considered:(i) the sender has chosen a free slot. If the intended receiver can decode the REQ, it replies to the request by sending an RTR in the same slot and by using the elds req.ad and r of this packet, as explained monet.tex; 5/01/2004; 11:42; p.10 CROMA -an Enhanced Slotted MAC Protocol for MANETs

monet.tex; 5/01/2004; 11:42; p.11

monet.tex; 5/01/2004; 11:42; p.[START_REF]European Commission, esa, Galileo Mission High Level Denition v3.0[END_REF]

monet.tex; 5/01/2004; 11:42; p.14

monet.tex; 5/01/2004; 11:42; p.15

monet.tex; 5/01/2004; 11:42; p.17

monet.tex; 5/01/2004; 11:42; p.19

monet.tex; 5/01/2004; 11:42; p.20

monet.tex; 5/01/2004; 11:42; p.21

monet.tex; 5/01/2004; 11:42; p.22

monet.tex; 5/01/2004; 11:42; p.23

monet.tex; 5/01/2004; 11:42; p.24 CROMA -an Enhanced Slotted MAC Protocol for MANETs

monet.tex; 5/01/2004; 11:42; p.27

monet.tex; 5/01/2004; 11:42; p.29

monet.tex; 5/01/2004; 11:42; p.31

monet.tex; 5/01/2004; 11:42; p.32

monet.tex; 5/01/2004; 11:42; p.33

monet.tex; 5/01/2004; 11:42; p.34


Dr Karim Bouchmella

Prof. Dr Sylvain G Dutremez
email: dutremez@univ-montp2.fr

Christian Guerin

Jean-Christophe Longato

Francoise Dahan

Christian Guérin

Jean- Christophe Longato

Françoise Dahan

J.-C Longato

Dr F Dahan

Guanidinium Alkynesulfonates

Keywords: sulfonation, alkyne, crystal engineering, hydrogen bonding, guanidinium sulfonate

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Hydrogen bonding is nature's favorite way of keeping molecules tightly bound to one another. This is presumably because most organic compounds have sites capable of hydrogen bonding ranging from weakly polarized C-H bonds to strongly polarized OH groups. Its strength depends on the nature of the atoms involved in the A-H•••B connection and, because it is a directional interaction, it is also contingent on the distance between the H and B centres and on the A-H-B angle. [START_REF] Jeffrey | An Introduction to Hydrogen Bonding[END_REF][START_REF]Glusker in Design of Organic Solids[END_REF][START_REF] Jeffrey | Hydrogen Bonding in Biological Structures[END_REF][START_REF] Desiraju | The Weak Hydrogen Bond in Structural Chemistry and Biology[END_REF][5] Due to its great versatility, hydrogen bonding has become a key interaction in Crystal Engineering. [START_REF] Desiraju | Crystal Engineering: The Design of Organic Solids[END_REF][START_REF] Desiraju | Solid-state Supramolecular Chemistry: Crystal Engineering[END_REF][START_REF] Nangia | Desiraju in Design of Organic Solids[END_REF] Numerous modules possessing hydrogen bonding capabilities have been described in the literature and used to construct supramolecular assemblies. Guanidinium organosulfonates, C(NH 2 ) 3 + RSO 3 -, in which RSO 3 -may be an alkane-or an arenesulfonate anion, belong to such category. [START_REF] Russell | [END_REF][10][11][12][13][14][15][16][17][18][19] Guanidinium sulfonates form robust hydrogen-bonded networks. It was suggested that this is due to a combination of several factors: the large number of strong hydrogen bonds, matched number of donors and acceptors (six guanidinium protons and six electron pairs on the three sulfonate oxygen atoms), 3-fold topologies for both the guanidinium and RSO 3 ions, similar sizes of the two partners, and presence of Coulombic interactions between the oppositely charged ions. [10,12,13] In the solid state, guanidinium cations and organosulfonate anions are tightly bonded through R 2 2 (8) dimer interactions. [START_REF] Etter | Graph notation was originally proposed by[END_REF] Repetition of this associative sequence along an axis results in the formation of infinite ribbons (Scheme 1). Association of these 1D ribbons through R 2 2 (8) dimer interactions and R 6 3 (12) rings in a direction perpendicular to the first one generates 2D sheets made of quasihexagonal patterns. This "honeycomb" structure appears to be general and has been observed for most guanidinium monosulfonates.

Scheme 1, here

The "honeycomb" structure is not perfectly flat but is puckered. The degree of puckering, as measured by the θ IR angle made by two adjacent ribbons (Scheme 1), is a function of the size of the R group of the sulfonate anion. For small R groups, corrugation is not severe and θ IR is close to 180°. In this case, all of the R groups within a sheet are oriented to the same side of the sheet. For bulky R groups, θ IR may be as low as 77°. [12] In this case, R groups within a sheet are not oriented to the same side of the sheet and alternate orientation from one ribbon to the next. Thus, the hydrogen-bonded sheet structure is preserved no matter what the size of the RSO 3 -anion, demonstrating the adaptability of the guanidinium sulfonate network.

The 2D sheets pile up in the third dimension according to two different motifs (Scheme 1). [START_REF] Russell | [END_REF][11][12][13] If the alkane or arene groups of the sulfonate anions are small, interdigitation of these groups is possible in the non-polar region separating the sheets, resulting in a bilayer stacking of the sheets. If the RSO 3 -anions are sterically demanding, interdigitation of the R groups is not possible, resulting in the formation of single layer motifs.

Structural studies have been carried out on guanidinium arenesulfonates bearing substituents capable of hydrogen bonding. [10,13] These substituents were found to interfere with the guanidinium sulfonate hydrogen bond network, leading to severe perturbation, and in some cases disruption of the quasihexagonal structure. The degree of perturbation decreased in the order COOH > OH > NO 2 , in agreement with the ability of these groups to form strong hydrogen bonds.

Another intriguing feature of guanidinium arenesulfonates is their ability to form inclusion compounds when crystallized from certain aromatic solvents. [14,16,19] The bilayer stacking motif observed in guest-free compounds is not encountered in host-guest complexes, presumably because interdigitation of the organosulfonate R groups in the non-polar region separating the sheets precludes the inclusion of solvent molecules. On the other hand, the single layer structure is observed in which the solvent molecules are interdigitated with the R groups of the RSO 3 -anions. Compounds that crystallize with this type of architecture have been termed "continuously layered inclusion compounds" abbreviated CLIC. In these CLIC's the number of guest molecules per guanidinium sulfonate unit is one. Another structural arrangement exists that is found in "tubular inclusion compounds" abbreviated TIC. These TIC's consist of six-sided discrete tubes, each comprising six guanidinium sulfonate ribbons.

The tubes assemble into a hexagonal array with the R groups of the RSO 3 -anions directed towards the outside of the tubes. There are two thirds of a guest per guanidinium sulfonate unit: one third guest occupies the interior of the tubes and the remaining third is located in the region between the tubes.

The thermal behavior of guanidinium alkylbenzenesulfonates and guanidinium alkylbiphenylsulfonates has been investigated by means of various techniques including polarizing optical microscopy, differential scanning calorimetry, dilatometry, infrared spectroscopy, and X-ray diffraction. [21,22] These compounds turn into persistent smectic liquid-crystal phases upon heating, and this phenomenon was ascribed to the reinforcement provided by the hydrogen-bonded network. Furthermore, rheology studies indicated the persistence of intermolecular hydrogen bonding in the liquid crystalline state. [22] Interestingly, unlike sodium alkylbenzenesulfonates, guanidinium alkylbenzenesulfonates also exhibit lyotropic behavior in aqueous and organic solvents, and this discrepancy was attributed to the fact that hydrogen bonding mediated by the guanidinium ion was required for gel formation. [23] Recently, smectic liquid crystalline phases were reported for guanidinium alkanesulfonates. [24] Ward and co-workers also prepared and characterized crystallographically a series of guanidinium α,ω-alkane-and arenedisulfonates and showed that these compounds crystallized with pillared architectures. [25][26][27][28][29][30][31][32][33][34][35] The disulfonate pillars connect opposing hydrogen-bonded sheets, resulting in the formation of cavities between the sheets. When long enough pillars are used, the cavities are sufficiently large to accommodate solvent molecules.

In this respect, guanidinium organodisulfonates have been regarded as functional organic zeolite analogues. [START_REF] Aoyama | Design of Organic Solids[END_REF] These clathrates exhibit various kinds of architectures (discrete bilayer, simple brick, crisscross bilayer, double brick, zigzag brick, V-brick) whose topologies are controlled by the size of the pillar and nature of the included guest (size of the molecule and types of functional groups present in it). An interesting application of this work has consisted in the crystallization-based separation of isomeric mixtures of aromatic molecules, [34] and attempts have been made to use these systems for chiral discrimination. [START_REF] Custelcean | [END_REF] Yet, as described previously for guanidinium organomonosulfonates, the guanidinium sulfonate sheet structure of guanidinium organodisulfonates may be disrupted when solvent molecules capable of interacting with these sheets via hydrogen bonding are included in the structure. This turned out to be the case for guanidinium 1,5-naphthalenedisulfonate crystallized in the presence of 2-methoxyethanol. [38] In another connection, the disulfonate anion may sometimes have some other function than just being a pillar between guanidinium sulfonate sheets and, for instance, electrochemical studies have been carried on guanidinium ferrocenedisulfonate adhered to a glassy carbon electrode. [39] In recent years, our research efforts have focused on the preparation, characterization, and study of the polymerisation behavior of symmetrical and unsymmetrical diacetylenes in which heteroelements are attached to the triple bonds. [40][41][42][43][44] In particular, it was found that 1,4bis(triorganosilyl)buta-1,3-diynes and their tin-containing counterparts did not show any solid-state polymerisation activity due to the bulkiness of the end-capping groups and the lack of strong interactions between molecules in the crystal lattice that could bring the C 4 rods near one another. [44] One way of improving this situation might consist of using guanidinium sulfonates comprising a diacetylenic moiety, and this possibility is currently under investigation in our laboratory. In a parallel study, we decided to investigate guanidinium monoalkynesulfonates because these molecules are simpler models than the diacetylenic ones. [START_REF] Dalrymple | Permanently porous networks sustained by charge-assisted hydrogen bonding between alkynesulfonates and Ni(tame) 2 2+ (tame = 1,1,1-tris(aminomethyl)ethane) have been described[END_REF] We report herein the synthesis and structural characterization of guanidinium sulfonates containing alkyne groups, i. interactions is present in solid 6. The 3D structure of 6 is the same as that found in Ward's compounds, i.e., it is a "typical" single layer stacking motif. Interestingly, the 3D structure of 5 is also a single layer stacking motif, but it differs from that of 6 in that the alkynyl groups all point to the same side of the sheet. This unusual arrangement originates from interlayer hydrogen bonding between sulfonate anions.

Results and Discussion

Syntheses: HC≡CSO 3 SiMe 3 (1) is a known compound that was prepared in the past by sulfonation of HC≡CSiMe 3 with ClSO 3 SiMe 3 or by sulfonation of HC≡CSiMe 3 with SO 3 ⋅dioxane; [46] we have synthesized 1 using the former method (Scheme 2).

CH 3 C≡CSO 3 SiMe 3 (2) was synthesized by sulfonation of CH 3 C≡CSiMe 3 with SO 3 ⋅dioxane (Scheme 2). ClSO 3 SiMe 3 and SO 3 ⋅dioxane were prepared as described in the literature. [46] Scheme 2, here Sulfonic acids HC≡CSO 3 H and CH 3 C≡CSO 3 H were prepared by hydrolysis of 1 and 2, respectively (Scheme 3). These acids were isolated as hydrates. [START_REF] Jeffrey | An Introduction to Hydrogen Bonding[END_REF] H NMR spectroscopy and elemental analysis showed the compositions of the two acids to be HC≡CSO stoichiometry found by Mérault. [46] The composition of 4 is similar to the

(CH 3 ) 3 SiC≡CSO 3 H•2 H 2 O
stoichiometry reported by Calas and Bourgeois. [47] [

+ C(NH 2 ) 3 ][HC≡CSO 3 -] (5) and [ + C(NH 2 ) 3 ][CH 3 C≡CSO 3 - ] (6)
were synthesized by allowing acids 3 and 4 to react with stoichiometric amounts of guanidinium carbonate (Scheme 3).

Scheme 3, here

Molecular dimensions: X-ray quality crystals of 5 and 6 were obtained by dissolving these salts in water and allowing the solutions to come slowly to dryness. It is noteworthy that water molecules are not present in the structures of 5 and 6; this situation appears to be general and has been observed for most guanidinium monosulfonates described by Ward.

This is presumably because the energy penalty for the disruption of the hydrogen bond network of guanidinium sulfonates by water molecules is too high. However, one exception has been reported which is guanidinium 2,4-dinitrobenzenesulfonate monohydrate. [13,15] Guanidinium 1-propynesulfonate ( 6 indicating a slight dissymmetry in the guanidinium cation. Although this situation is not common, it is not unusual and has been observed previously in the X-ray crystal structure of guanidinium methanesulfonate. [START_REF] Russell | [END_REF] Slight differences are also observed in the 2D structures: Unlike the situation commonly observed in guanidinium alkane-and arenesulfonates, [15] the guanidinium cations and sulfonate anions in solid 6 assemble into 1D ribbons through R 2 2 (8) and R 2 1 (6) dimer interactions (Figure 1). This is due to the fact that, in each ribbon, every third sulfonate anion has undergone a 60-degree-rotation with respect to the two preceding ones. There are six unique N-H•••O hydrogen bonds in each ribbon with geometries similar to those observed in Ward's compounds: [START_REF] Russell | [END_REF][10][11] two of them are involved in a and As seen in Figure 2, the alkynyl groups within a hydrogen-bonded sheet of 6 alternate orientation from one ribbon to the next; the stacking motif is thus single layer. This situation is unusual as it is generally observed for guanidinium organosulfonates with large R groups.

∠N(3)-H(3A)•••O(5) = 148.9°. The H•••O distances in the R 2 2 (8) rings are 2.10 (H(1B)•••O(1)), 2.15 (H(2B)•••O(3)), 2.22 (H(4A)•••O(3)), and 2.09 Å (H(5A)•••O(2)). The corresponding N•••O distances are 2.9727(19) (N(1)•••O(1)), 3.0222(10) (N(2)•••O(3)), 3.0685(10) (N(4)•••O(3)), and 2.9645(8) Å (N(5)•••O(2)). The N-H•••O angles are 169.3 (N(1)-H(1B)•••O(1)), 173.7 (N(2)-H(2B)•••O(3)), 161.1 (N(4)-H(4A)•••O(3)),
The amount of puckering of the sheets, as quantified by the dihedral angle θ IR between the least-squares plane of one ribbon and the least-squares plane of an adjacent ribbon, is 151°

(θ IR = 180° means no puckering). This low degree of puckering likely arises from the small steric demand of the alkynyl group. Guanidinium organosulfonates with similar θ IR values and known to crystallize with a single layer stacking motif include guanidinium 1butanesulfonate (157°), guanidinium ferrocenesulfonate (153°), and guanidinium 5-benzoyl-4-hydroxy-2-methoxybenzenesulfonate (165°). [START_REF] Russell | [END_REF][11][12][13] Generally, guanidinium organosulfonates with a single layer structure exhibit θ IR angles that are much smaller (51-122°). [START_REF] Russell | [END_REF]10,12,13] Figure 3, here

The alkynyl groups within a hydrogen-bonded sheet of 5 do not alternate sides from ribbon to ribbon. This stacking motif is reminiscent of a bilayer structure. However, the absence of polar regions between the sheets points to a single layer structure. The hydrogenbonded sheets of 5 lie in the ab plane (Figure 4). The amount of puckering is nil. A θ IR angle of 180° has been observed in guanidinium methanesulfonate, guanidinium triflate, guanidinium ethanesulfonate, and guanidinium 2-and 3-nitrobenzenesulfonates; these salts all crystallize with a bilayer stacking motif. [START_REF] Russell | [END_REF]12,13] Figure 4, here 3D structures: The hydrogen-bonded sheets in 6 pile up along a with no polar region between the sheets, as is normally found in guanidinium organosulfonates with a single layer structure (Figure 2). The sheets are highly interdigitated. The amount of interdigitation between the i and i-1 (or i and i+1) sheets, as estimated by adding the distance between the sulfur atom and the methyl carbon to the distance between the methyl carbon and the midpoint of the C≡C bond, amounts to 6.4 Å. The separation between two successive (i and i+1, for instance) hydrogen bonded sheets, roughly equivalent to the distance between the sulfur atom and the midpoint of the C≡C bond, is 2.3 Å. Consequently, no sizeable voids are present in the solid and a compact structure is obtained (ρ calcd = 1.474 g cm -3 ). This arrangement is also an ideal one to maximize N-H•••π interactions between guanidinium cations and acetylenic moieties. Indeed, close examination of the X-ray crystal structure indicates that there are numerous N-H•••π contacts (Figure 5). There are eighteen However, their large number suggests that their contribution to stabilization of the structure is not negligible. Literature concerning N-H•••C≡C interactions in small molecules is scarce.

H guanidinium •••C sp distances
Yet, such an interaction has been observed in 1-(2'-aminophenyl)-2-(2''nitrophenyl)ethyne. [START_REF] Desiraju | The Weak Hydrogen Bond in Structural Chemistry and Biology[END_REF]48] In this compound, one amino hydrogen interacts with the nearby the hydrogen and the midpoint of the C≡C bond is 2.49 Å; the angle between the N-H direction and an axis passing through the N-H hydrogen and the centre of the C≡C bond is 117°. [START_REF] Desiraju | The Weak Hydrogen Bond in Structural Chemistry and Biology[END_REF] Thus, the N-H Other interdigitation schemes are possible that were not observed in the solid-state structure of 6 for the following reasons: the first possibility is that the sheets be not interdigitated at all. This situation would be unfavorable because large voids would be created in the structure and steric repulsion between methyl groups in the nonpolar region between the sheets would be substantial. The second conceivable situation is that the amount of interdigitation be half the length of the 1-propynesulfonate anion, i.e. 2.2 Å. In this case, voids in the structure would be reduced and steric repulsion between methyl groups would be nil. However, this situation would not take advantage of the stabilizing N-H•••C≡C interactions mentioned earlier. A third possible scenario is that the amount of interdigitation be equal to the full length of the 1-propynesulfonate anion, i.e. 4.4 Å. In this case, the sheet structure would be disrupted because the methyl groups would be interfering with the guanidinium sulfonate hydrogen bond network.

The 3D structure of 5 is also single layer as there is no polar region between the sheets (Figure 4). The hydrogen bonded sheets all have ethynyl moieties pointing in the same direction; there is no up-down-up-down alternation. The structure may be regarded as a bilayer structure in which every other layer has been turned around. The hydrogen bonded sheets pile up along c. The amount of interdigitation between the i and i-1 sheets is quite small and is estimated to be about 1 Å, i. [49] C sp -H•••O angles cluster in the range 150-160°. [50,51] It is noteworthy that C≡C-H•••C≡C interactions as those observed in simple alkynes are not present. [52] Evidently, the structure of 5 is governed by the guanidinium sulfonate sheet motif. with strong hydrogen bonding capabilities. [10,13] Yet, it was found that these weak interactions were capable of bringing subtle changes to the basic arrangement: in the case of 6, a compact structure is obtained in which the sheets are highly interdigitated due to the presence of numerous N-H•••C≡C contacts. In the case of 5, the hydrogen bonded sheets all have ethynyl moieties pointing in the same direction because of interlayer C sp -H•••O interactions between organosulfonate anions. On the basis of Desiraju's classification, the latter hydrogen bond may be regarded as intrusive. [5] In effect, the structure of 5 is reminiscent of some work published by Janiak in which an "inverse bilayer" structure was observed for a series of 1,1'binaphthalene-2,2'-diyl phosphate salts. [53] This unusual situation was ascribed to hydrogen bonding from the cations and solvent molecules to the hydrophilic (RO) 2 PO 2 -phosphate heads which creates an interior hydrophilic region and exposes the binaphthyl groups on both exterior sides. The present study is currently being extended to guanidinium disulfonates bearing alkyne and diacetylenic groups to see how these salts compare with guanidinium α,ωalkane-and arenedisulfonates. Also, work is underway to see if other weak interactions such as arene•••perfluoroarene have structure-modifying abilities similar to those of the N-

H•••C≡C and C sp -H•••O(sulfonate) interactions reported here.

Experimental Section

General considerations: Solution 1 H and 29 Si NMR spectra were recorded on a Bruker Avance DPX 200 spectrometer. 13 C NMR spectra were obtained on either one of the following Bruker instruments: Avance DPX 200, AC 250, Avance DRX 400. [START_REF] Jeffrey | An Introduction to Hydrogen Bonding[END_REF] H chemical shifts were referenced to the protio impurity of the NMR solvent, 13 C chemical shifts to the NMR solvent, and 29 Si NMR chemical shifts to tetramethylsilane. Infrared spectra were recorded on a Thermo Nicolet Avatar 320 FT-IR spectrometer with a 4 cm -1 resolution.

Melting points were measured on a Büchi B-540 melting point apparatus and are uncorrected.

FAB mass spectra were obtained on JEOL JMS-SX102A and JEOL JMS-DX300 instruments.

HRMS measurements were performed on a Varian MAT 311 double focusing mass spectrometer at the Centre Régional de Mesures Physiques de l'Ouest (CRMPO), Université de Rennes I, Rennes, France, using electron impact (70 eV) as ionization mode. Elemental analyses were carried out at the Service Central de Microanalyse of the Centre National de la Recherche Scientifique (CNRS), Vernaison, France.

Materials: (Trimethylsilyl)acetylene (98%) was purchased from Lancaster and 1trimethylsilyl-1-propyne (97%) from Alfa Aesar. Guanidinium carbonate (99%) was obtained from Aldrich and used as supplied. 1,4-Dioxane (extra dry, with molecular sieves, water < 50 ppm, stabilized) and water (for HPLC gradient grade) were purchased from Acrōs Organics.

Dichloromethane was distilled over CaH 2 prior to use. ClSO 3 SiMe 3 and SO 3 ⋅dioxane were prepared as described in the literature. [46] Synthesis of HC≡ ≡ ≡ ≡CSO 3 SiMe 3 (1): Alkyne 1 was synthesized by sulfonation of HC≡CSiMe 3 with ClSO 3 SiMe 3 as described by Mérault. [46] Synthesis of CH 3 C≡ ≡ ≡ ≡CSO 3 SiMe 3 (2): Alkyne 2 was synthesized by sulfonation of CH 3 C≡CSiMe 3 with SO 3 ⋅dioxane following a procedure adapted from Mérault. [46] After completion of the reaction, the volatiles were removed and the crude product was purified by vacuum distillation (50 °C, 0.05 mbar). A colorless viscous liquid was obtained; yield: 80%. Si-CH 3 ), 1187 cm

Synthesis of HC≡ ≡ ≡ ≡CSO 3 H•2.33 H 2 O (3):

A 7-mL portion of deionized water was added to a diethyl ether solution (10 mL) containing 1 (12.5 g, 70 mmol). The two-phase mixture was stirred overnight. The two layers were separated and the aqueous layer was washed three times with diethyl ether to remove completely the hexamethyldisiloxane formed in the reaction. The aqueous layer was concentrated on a rotary evaporator, then heated to 79 °C on a vacuum-line. The residual liquid was left to stand at room temperature during which time a solid formed. [START_REF] Jeffrey | An Introduction to Hydrogen Bonding[END_REF] H NMR spectroscopy and elemental analysis showed the amount of water per mole of sulfonic acid to be 2.33, which is close to the HC≡CSO 3 H•2.5 H 2 O composition reported by Mérault; [46] yield: 74%. The solid is hygroscopic and turns into a liquid on exposure to air over a period of several days. K in both cases. The crystal-to-detector distance was 70 mm for both measurements. For 5, a total of 179 exposures (4 min per exposure) were taken with 0 < ϕ < 250.6° and crystal oscillations of 1.4º in ϕ. [START_REF]Stoe IPDS Manual: Version 2.93[END_REF] For 6, 139 exposures (5 min per exposure) were taken with 0 < ϕ < 250.2° and crystal oscillations of 1.8º in ϕ. No decay corrections were made to the data based on intensity checks of two hundred control reflections. The cell parameters were refined from 8000 reflections. Owing to the low values of µ, no absorption corrections were made.

Both structures were solved by direct methods (SHELXS-97). [START_REF] Sheldrick | SHELXS-97, Program for Crystal Structure Solution[END_REF] The SHELXL-97 program was used for full-matrix least-squares refinement against F o 2 using all reflections. [START_REF] Sheldrick | SHELXL-97, Program for the Refinement of Crystal Structures from Diffraction Data[END_REF] Atomic scattering factors were taken from a standard source. [START_REF]International Tables for Crystallography[END_REF] All non-hydrogen atoms were refined anisotropically. Hydrogen atoms were introduced in the calculations with the riding model, [σ 2 (F o 2 ) + (0.0283 P) 2 ] -1 [σ 2 (F o 2 ) + 0.2076 P] -1 max and mean shift/esd 0.000, 0.000 0.001, 0.000 R, [b] R w [c] (obsd reflns) 0.0200, 0.0425 0.0180, 0.0358 R, [b] R w [c] (all reflns) 0.0205, 0.0425 0.0190, 0.0360 largest diff. peak and hole [e Å -3 ] 0.127, -0.123 0.159, -0.160

Legends

θ IR R R R R R R R R 3D R R R R R R R R bilayer stacking R R R R R R R

  ) crystallizes in the centrosymmetric space group Pnma with Z = 12. One molecule in the cell occupies a general position and the other molecule lies on a mirror plane. The geometrical parameters of the crystallographically unique guanidinium cations and sulfonate groups are very much like those found in Ward's compounds: the C-N bond distances are in the range 1.3195(12)-1.3269(10) Å and the N-C-N angles lie between 119.11(11) and 120.44(6)°. The S-O bond distances span the range 1.4462(10)-1.4546(6) Å and the O-S-O angles the range 112.78(4)-113.31(4)°. The C≡C distances are those typically found in alkynes, i.e. 1.1954(13) and 1.2062(18) Å. The S-C distances are 1.7086(9) and 1.7148(13) Å. The S-C≡C angles are close to 180° and so are the C≡C-CH 3 angles, i.e., 177.22(9) and 176.07(12)° for S-C≡C and 179.67(12) and 178.90(15)° for C≡C-CH 3 .Guanidinium ethynesulfonate (5) crystallizes in the noncentrosymmetric space group P6 3 with Z = 6. There is one crystallographically unique molecule in the cell. The geometrical parameters of the guanidinium cation are slightly different from those of 6: there is one short C-N bond distance (1.3232(12) Å) and two longer ones(1.3386(11) and 1.3460(12) Å),

R 2 1 ( 6 )

 16 dimer interaction and four of them in R 2 2 (8) interactions. The H•••O distances in the R 2 1 (6) ring are 2.16 (H(1A)•••O(5)) and 2.14 Å (H(3A)•••O(5)), and the corresponding N•••O distances are 2.9437(11) (N(1)•••O(5)) and 2.9315(11) Å (N(3)•••O(5)). The N-H•••O angles are alike but differ significantly from the optimum 180° value: ∠N(1)-H(1A)•••O(5) = 148.1

Figure 2 , 3 )

 23 Figure 2, here The guanidinium cations and ethynesulfonate anions in solid 5 assemble into 1D ribbons through R 2 2 (8) dimer interactions, as is normally the case in guanidinium alkane-and arenesulfonates. The ribbons assemble into 2D sheets through R 2 2 (8) and R 6 3 (12) rings (Figure 3). There are six unique N-H•••O hydrogen bonds in each sheet. The H•••O distances are 2.10 (H(3B)•••O(2)), 2.26 (H(2A)•••O(3) and H(3A)•••O(3)), 2.34 (H(2B)•••O(1)), 2.36 (H(1B)•••O(1)), and 2.50 Å (H(1A)•••O(2)). The corresponding N•••O distances are

  ranging from 2.6766 Å to 3.1540 Å, and twelve of them are below 3 Å. The N-H•••C sp angles span the range 92.10-116.54°. Clearly, these interactions are weak.

  triple bond. It is an intramolecular N-H•••C≡C hydrogen bond bifurcated by an intramolecular N-H•••O 2 N interaction. The N-H•••C sp distances are 2.38 and 2.72 Å and the distance between

  •••C sp distances in 6 are longer than those observed in 1-(2'aminophenyl)-2-(2''-nitrophenyl)ethyne and the N-H•••C sp angles are smaller, suggestive of weaker N-H•••C≡C interactions in the former compound.

Figure 5

 5 Figure 5, here

Figure 6 , 3 -] ( 5

 635 Figure 6, here

1 H

 1 NMR (200.1 MHz, CDCl 3 ): δ = 0.49 (s, 9H; Si(CH 3 ) 3 ), 2.10 ppm (s, 3H; CH 3 C≡);13 C NMR (100.6 MHz, CDCl 3 ): δ = -0.2 (Si(CH 3 ) 3 ), 3.3 (CH 3 ), 74.5 (≡CSO 3 ), 88.3 ppm (CH 3 C≡); 29 Si NMR (39.8 MHz, CDCl 3 ): δ = 35.8 ppm (Si(CH 3 ) 3 ); IR (CCl 4 ): ν̃ = 2960 (w; C(sp 3 )-H), 2917 (w; C(sp 3 )-H), 2852 (w; C(sp 3 )-H), 2225 (s; C≡C), 1373 (s; SO 2 ), 1259 (vs;

Scheme 1 .

 1 Scheme 1.Schematic representation showing the arrangement of the guanidinium sulfonate motif as a function of increasing dimension.

Figure 1 .

 1 Figure 1. View along the a-axis showing the hydrogen bond network in 6. Ions connected through dotted lines belong to the main layer (i sheet). Rows of sulfonate anions labelled A and C belong to the i+1 sheet. Rows of sulfonate anions labelled B and D belong to the i-1 sheet.

Figure 2 .

 2 Figure 2. View along the b-axis depicting the single layer structure of 6. Three layers are shown that are labelled i, i-1, and i+1. Rows of sulfonate anions marked A, B, C, and D are the same as in Figure 1.

Figure 3 .

 3 Figure 3. View along the c-axis showing the hydrogen bond network in 5.

Figure 4 .

 4 Figure 4. View perpendicular to the c-axis showing the stacking of the layers in 5.

Figure 5 .

 5 Figure 5.View showing N-H•••π interactions (dashed lines) in crystalline 6.

Figure 6 .

 6 Figure 6. View perpendicular to the c-axis showing C sp -H•••O contacts (dashed lines) between sulfonate anions from the i and i-2 layers in crystalline 5.

  3. [b] R = Σ ||F o |-|F c || / Σ |F o |. [c] R w = [Σ (w (

  Figure 1

  e. the length of the C sp -H bond. What is causing this unusual situation is evident from Figure 6: every sulfonate anion from an i layer interacts via a C sp -H•••O hydrogen bond with another sulfonate anion located in the i-2 sheet. The C sp -

	H•••O(sulfonate) hydrogen bond length is 2.35 Å and the C sp •••O distance 3.241(2) Å. The
	C sp -H•••O angle is 156.3°. These geometrical parameters compare well with the values found
	in the literature: a CSD analysis indicates that the mean C sp -H•••O distance is 2.40(2) Å and
	the mean C sp •••O distance 3.35(1) Å.

  calcd for C 5 H 9 O 3 SSi + [M -CH 3 ] + : 177.00417; found: 177.0045; elemental analysis calcd (%) for C 6 H 12 O 3 SSi (192.3045): C 37.47, H 6.29, S 16.67; found: C 35.30, H 5.74, S 17.6.

-1

(vs; SO 2 ); HRMS (EI): m/z

Table 1 .

 1 Crystal Data and Experimental Details of Data Collection and Refinement for 5 and 6.

	Compound	5	6
	empirical formula formula weight	C 3 H 7 N 3 O 3 S 165.18	C 4 H 9 N 3 O 3 S 179.20
	crystal color	colorless	colorless
	crystal size [mm]	0.45 × 0.30 × 0.25	0.50 × 0.45 × 0.20
	crystal system	hexagonal	orthorhombic
	space group a [Å]	P6 3 (No. 173) 13.4466(11)	Pnma (No. 62) 7.9199(8)
	b [Å]	13.4466(11)	23.304(2)
	c [Å]	6.6927(5)	13.1285(14)
	α [°] β [°]	90 90	90 90
	γ [°] V [Å 3 ]	120 1047.99(14)	90 2423.0(4)
	Z	6	12
	ρ calcd [g cm -3 ] F(000)	1.570 516	1.474 1128
	µ [mm -1 ] T [K]	0.416 180	0.366 180
	graphite-monochromated Mo Kα	0.71073	0.71073
	radiation [Å]
	2θ range [°]	3.3-52.1	3.3-52.1
	index ranges	-16 ≤ h ≤ 16, -16 ≤ k ≤ 16,	-9 ≤ h ≤ 9, -28 ≤ k ≤ 28,
		-7 ≤ l ≤ 7	-16 ≤ l ≤ 16
	reflections collected	10375	21777
	independent reflections	1309	2435
	0.0258 1226 91 2 (all reflns) 1.064 no. of obsd reflns (F o > 4 σ(F o )) R int (on I) parameters refined goodness-of-fit on F o w [a]	0.0252 2240 160 1.198

  1/2 .

															Scheme 1
																		2D
	H	N H H	C N dimer N H H H O R 2 2 (8) 0D	O S R	O	H	N H H	C N	N H H R 2 2 (8) H O ribbon O S O R H N H N C H R 2 2 (8) 1D	N H H	O H	S O R	O	R 2	2 (8)	H	N H H 3 (12) C N H N H R 6 O S O O R H	H O H N O S R C N	O H H N	H N H O H	N C R S O	H N H O	R O S O H	O
																		H	H
																		sheet

Acknowledgment

We are indebted to Dr. Pierre Guenot from the Centre Régional de Mesures Physiques de l'Ouest (CRMPO), Université de Rennes I, Rennes, France, for obtaining the HRMS results reported in this work. We also thank Dr. Arie van der Lee from the Institut Européen des Membranes (UMR 5635, Université Montpellier II, Montpellier, France) for helpful discussions concerning the X-ray crystal structures of sulfonates 5 and 6.

with isotropic thermal parameters equal to 1.1 times that of the atom of attachment. Final R values and relevant crystallographic data are given in Table deposit@ccdc.cam.ac.uk).

Text for the Table of Contents

Guanidinium 1-propynesulfonate (6) crystallizes with a "standard" single layer structure in which CH 3 C≡C groups lie alternately above and below the mean plane of each sheet.

Guanidinium ethynesulfonate (5) also crystallizes with a single layer stacking motif but, unlike 6, all the sheets have HC≡C groups pointing in the same direction. C sp -H•••O hydrogen bonding between sulfonate anions is responsible for the unusual situation observed in 5.

Graphic for the