Supervisor: Kaisa Sere
The Shared Medium Problem
Download 298.62 Kb.
|
- Navigate this page:
- 2.2 MAC Protocols for Ad Hoc Networks
- 2.2.1CSMA / CA
- 2.2.4MACA-BI
- 2.2.9IEEE 802.11b
- 2.2.10Bluetooth
2.1 The Shared Medium ProblemProblems in wireless computer networks with a shared medium (frequency band) have been identified. For instance, a problem called “hidden terminal” appears when at least three nodes (A, B and C) are operating close to each other, so that A and B, and B and C are within radio range. If A and C sends to B at the same time, the data received at node B will be corrupt. This can happen because A and C are “hidden” from (cannot sense) each other, this is shown in figure 2-2. 
Fig. 2 2: Hidden Terminal. A  related problem called “exposed terminal” could arise in a scenario depicted in figure 2-3. Because many MAC protocols inhibit transmission when transmission of another terminal is detected, node A will not be able to transmit to any node when B is transmitting to C. This is not correct since A could transmit to any terminal other than B and C that is within its range without spoiling the reception at terminal C.
Fig. 2 3: Exposed terminal. 2.2 MAC Protocols for Ad Hoc NetworksA number of schemes for accessing a shared medium have been proposed so far. An overwhelming portion of MAC protocols use at least two short control messages for reservation of the medium in order to combat hidden/exposed terminal problems. The transmission reservation is done by transmitting a “Ready To Send” (RTS) and a terminal accepting this request answers with a “Clear To Send” (CTS). Every terminal that overhears the RTS or the CTS will defer from transmitting during a specified time in order to avoid collisions. If a collision does occur, this is detected when certain amount of time has elapsed without receiving an acknowledgement for a packet. After a collision, protocols generally retransmit the packet that collided. This cannot be done instantly because then the packets sent by two or more terminals would collide again. This can be helped by backing off a random amount of time between 0 and the number of collisions for the same packet experienced so far times a backoff slot time (depending on the physical characteristics of the network). This method is called binary exponential backoff (BEB). We will now examine a number of propositions that are more or less based on this type of communication. These are CSMA/CA, MACA, MACAW, MACA-BI, PAMAS, DBTMA and MARCH. After that, a new protocol called HAMA is examined. Sections 2.2.9 and 2.2.10 contain specifications of MAC protocols that have been implemented in two wireless networks, called IEEE 802.11b and Bluetooth. All of these protocols solve the shared medium problem in different ways and as the last thing in this chapter, a classification of the protocols will be given based on how these solve the problem. 2.2.1CSMA / CAIn Carrier Sense Multiple Access (CSMA) terminals sense the medium before transmitting and then take appropriate action according to how the medium was found. There are three variations of CSMA that behave in the following way:
The hidden terminal problem plagues CSMA, so Collision Avoidance (CA) is needed. CA can be added to CSMA by letting terminals transmit only after the initiator has gotten permission from the receiver. Requests for permission are sent by addressing the receiver with a “Ready To Send” control packet. If permission is granted by the receiver, it will transmit a “Clear To Send” (CTS) back to the initiator. If CTS is not received by the initiator within a certain interval it will timeout and try again. When a collision is detected, the BEB (explained above) method is invoked. Any other terminal overhearing either the RTS or CTS will avoid collisions by deferring from transmission during a specified interval. 2.2.2MACAMACA [Karn90] stands for Multiple Access Collision Avoidance and allows for many terminals to share a medium for data communication with help of appropriate control messages. Interestingly, MACA abolishes the carrier sensing as this cannot be relied on in all situations (like exposed terminal). MACA is designed to solve the hidden/exposed terminal problems by regulating the transmitter power, among other things. A terminal running MACA requests the medium by sending a RTS to the receiver. Since the radio signal propagates omnidirectionally, every terminal within the sender’s radio range will hear this and will know not to transmit. If the receiver is able to receive data at the moment, it will answer with a CTS. This, in turn, inhibits the receiver’s neighbors from transmitting during a specified time. The inhibition delay time for the sender’s neighbors is equal to the longest possible time for the sender to receive a CTS plus a random delay. The neighbors of the receiver should “keep quiet” for a time specified in the CTS (the length of the data that the sender specified in its RTS is copied to the CTS) plus a random delay to avoid collisions. MACA solves the problem of exposed terminal since a terminal A receiving only a RTS addressed to a certain terminal B, can deduce that it will not disturb the transmission to B since it has not received a CTS from B (A is not a neighbor of B). Although MACA is data packet collision free, RTS packet collisions can still happen in MACA and are detected through lack of CTS answer. If this happens, a BEB delay is waited. MACA also has a power-regulating feature, which works as follows: Communicating neighbors include readings of the currently received signal strength in messages. This will help the other party to lower the output signal it is using. When a suitable level, which is strong enough to reach from terminal B to terminal A is known, B can use a power level below this value in order to be able to keep on communicating with other terminals although a CTS is heard. This improves overall throughput of the network. If the size of a data packet to be sent is not much greater than the control packets then these can be omitted. That is, a terminal can send the data immediately without the RTS-CTS procedure. A very important point is made in [Karn90] is that the data message must not be of critical nature since the risk of data packet collision then exist. A suitable application of this would be the cumulative acknowledgements of TCP since it does not matter if one is lost as long as the next one is received before the sliding window is filled up. 2.2.3MACAWMACAW (MACA with Acknowledgement) [Bharghavan+94] is a modification of MACA. MACAW addresses a problem found in MACA in which some terminals that have experienced more collisions will be less likely to allocate the channel before terminals that have experienced fewer collisions. This ratchet effect occurs because every time a terminal experiences a collision, its backoff value is doubled (and reduced to minimal after successful exchange of RTS-CTS) and is thus increasingly likely to be dealt longer random values to wait before accessing the channel after collision. In order for the ratchet effect to take place the channel has to be heavily utilized and the backoff value of one terminal is significantly higher than the competing terminal’s. This problem is corrected in MACAW by inserting the backoff value in packets and letting other terminals copy the value from the packet to its actual value and therefore spreading the backoff values, keeping them on a similar level at every terminal. An important point made in [Bharghavan+94] is that MACA relies on the transport layer to provide the final recovery of transmission errors. As errors in TCP are often detected after a timeout period this will inflict substantial delays. Because MACAW uses hop-by-hop acknowledgements (ACK), the timeout values can be made significantly smaller than TCP timeouts, thus providing faster error detection. The receiver returns the ACK to the sender as soon as a successful transmission of a data packet has occurred. If the ACK is not received, the data will be retransmitted. If retransmission is also unsuccessful, an error message is sent to the initiator. Although MACA has the useful feature of informing the sender’s neighbors of the duration of the transmission in the RTS, the neighbors still do not know if the receiver received the RTS successfully or if the sender is actually transmitting. A Data-Sending (DS) packet is therefore added which is transmitted by the sender, when it receives a CTS, with the intent that every neighbor of it is informed that a data transmission is underway. Thus, every neighbor defers transmission during the delay indicated by the DS. Another problem that MACAW solves can occur when terminals are aligned in the way shown in figure 2-4: The scenario begins when one terminal wins the initial access to the medium, in this case D (C responds to D’s RTS) and after that relatively large data packets (compared to the control packets) are sent form D to C. The problem arises when A wants to transmit to B, but does not get any responsive CTS because B is deferring due to the fact that is has heard an CTS from C. Over time, it will be very unlikely that A will get access to the medium since its RTS should be received exactly when one data transmission between D and C has just ended. 
Fig. 2 4: B cannot respond to A because B is deferring. The lack of synchronization between A and D (A is actually contending with D), and the fact that the data packets are larger in size, makes it unlikely that A’s RTS will arrive at B during a short contention period. This is why yet another packet is added to MACAW, called “Request for Request To Send” (RRTS). This packet can be sent by B to A after it has received a RTS from A to which it cannot send an CTS, thus letting B contend for access in place of A since B has heard the CTS from C and will know when to request a RTS. So, the RRTS is sent to the sender of the initial RTS (A) at the next won contention period, which enables A to retransmit a RTS if it still has data to send. Other terminals hearing the RRTS defer for a delay long enough to let a RTS-CTS sequence to take place between A and B. Simulation results in [Bharghavan+94] show that, in networks with high error rates the benefit from the ACK messages substantially. The DS and RRTS make the allocation of the channel fair. The message exchanges in the MACAW protocol amounts to a five-way handshake scheme, which will have more control overhead than other protocols. 2.2.4MACA-BIThe basic model of channel allocation was rethought in the protocol called MACA-By Invitation [Talucci+97]. As the name suggests, it is the receiver that “invites” the sender to send. MACA-BI uses a two-way handshake and utilizes a Ready To Receive (RTR) message, which is the message that has to be received by a terminal before it can transmit data. Neighbors overhearing the RTR are inhibited from transmitting during the length of the transmission. This can be seen as a form of neighbor polling protocol. To increase the chance that a neighbor being polled actually has data to send, the queue length and packet arrival rate at the neighbor can be included in packet exchanges so that the receiver can poll the terminal in greatest need of channel access. When terminals are mobile, the MACA-BI receiver initiated method is inadequate and RTS messages can be used if a terminal’s queue length or packet delay exceeds a threshold value. The two-way handshake of MACA-BI drastically reduces the amount of control messages that has to be sent in order to allocate the channel compared to other protocols. The achieved advantage over MACA evaporates when connectionless, bursty transmissions occur because a receiver does not know which node to poll and the RTS message has to be used by the sender. The hidden terminal problem still exist for control messages, but as with other MACA based protocols, two data packets can never collide in MACA-BI. The chance of control packet collision will be half of that of MACA since half as many control packets are used. And finally, as mentioned in [Talucci+97] collision avoidance does not suffer from the reduced handshake procedure. 2.2.5PAMASPower Aware Multi-Access with Signaling for Ad Hoc Networks (PAMAS) [Singh+98] is also based on MACA. What makes this protocol special is that is has a separate signaling channel with which RTS-CTS dialogue is maintained and a normal data channel for data messages. When a terminal wants to transmit, a RTS is sent over the signaling channel. If, however, another terminal is receiving data at the moment, it will respond with the busy tone, which will collide with any subsequent control messages, making it impossible for other terminals to engage in dialogue. But, if the control channel was idle, and no other terminal is receiving data (no busy tone is put on the control channel), the RTS will get through to the receiver and the sender then starts waiting for a CTS (if a CTS is never received, the sender enters a binary exponential backoff state). If the sender receives a RTS while waiting for a CTS, it will itself transmit a CTS packet and start waiting for data to arrive. This can take place only after the receiver has replied with the CTS, which can be done if there is no busy tone on the control channel nor is any neighbor transmitting data (data channel is idle). When data begins to arrive at the receiver, it asserts a “busy tone” on the signaling channel. In PAMAS, if a terminal has no packets to send and at least one neighbor is transmitting and another is receiving, the other terminals can power down in order to save energy. The difficulty is then to know when to power-up the again. Probing intermittently could solve this. In simulations power savings between 10-70% are registered (with various network layer routing protocols). In [Singh+98] it is pointed out that overhearing packets consume power as well (approx. 2-15 watt while receiving). 2.2.6DBTMAIn [Deng+98] it is shown that in protocols based solely on RTS-CTS sequences (no separate signaling channel), the probability of collisions is about 60%. To reduce this percentage, an ad hoc version of the last hop medium access protocol Busy Tone Access (BTMA) was developed, and was named Dual Busy Tone Multiple Access (DBTMA). Like PAMAS, DBTMA has one data- and one control channel (for RTS-CTS) and two busy tones for alerting others of ongoing transmission. One tone is used to signify receive-busy (BTr) and the other transmit-busy (BTt). As usual when a terminal wants to transmit it sends a RTS over the control channel if no BTr signal is sensed (no neighbor is receiving). The terminal to which the RTS is addressed answers with a CTS if no BTt (no neighbor is transmitting) signal is sensed and places a BTr tone on the signalling channel. When the CTS reach the originator of the RTS, it can begin transmitting data, but also sets the BTt tone on the signaling channel. Neighbors that can hear either busy tone are prohibited from transmitting. 2.2.7MARCHMARCH (Media Access with Reduced Handshake) described in [Toh02] is a medium access protocol that takes advantage of the fact that neighbors can overhear each other, in order to reduce the amount of messages needed for a successful handshake. MARCH is also a receiver-initiated protocol, in which the polling is done in an intelligent way. The polling can be made intelligent by allowing MARCH to access the routing table of the network layer. When a neighbor overhears a CTS, it will know that data is about to be sent to the sender of the CTS. Since the neighbor has access to the network layer routing table it can check if it belongs to the route that the overheard packet is traversing. The overheard CTS must, therefore contain the MAC address of the CTS-sender and a route ID (RTID), which identifies the route that the packet is traversing. The neighbor then sets a timer long enough to let the sender of the CTS receive the data and waits for the time to elapse. When that happens, the neighbor will know exactly which node to request data from, that is, if the terminal that sent the CTS is on the same route as the neighbor. The neighbor requests the data with a subsequent CTS2 message. This kind of “CTS only” communication can be done at every hop (an RTS has to be used by the source initially) along the route from a source to a destination, thus providing a very efficient receiver initiated medium access protocol. Figure 2-5 displays a simple scenario using MARCH. This MAC protocol requires that the network protocol caches complete routes like DSR does see (section 3.5). 
Fig. 2 5: C requests data from B with a CTS2. 2.2.8HAMAHybrid Activation Multiple Access (HAMA) [Bao+02] is a medium access protocol for ad hoc networks that uses techniques previously mainly found in one-hop base station networks (i.e. mobile phone networks) called Code Division Multiple Access (CDMA) and Time Division Multiple Access (TDMA). CDMA is basically direct sequence spread spectrum (explained in the first section of this chapter) in which each terminal is given its own spreading code to avoid interference. Protocols using this kind of medium access methods are called “conflict-free” because every node can transmit without worrying about collisions (the opposite of conflict-free is contention based, i.e. protocols derived from CSMA/CD). In HAMA the neighborhood is expanded to contain not only one-hop (direct) neighbors, but also two-hop (indirect) neighbors. A terminal needs to have information about the whole of its neighborhood. We will soon see how this information is gathered, but let us now concentrate on what kind of information is needed and its purpose. The knowledge of the neighborhood is used to derive topology dependant transmission schedules as a basis for a priority scheme. To enable conflict free data communication, HAMA utilizes a pool of carefully chosen orthogonal (non-overlapping) spreading codes (DSSS), which are assigned to terminals. This protocol relies on the fact that CDMA codes and TDMA time slots only have to be unique in the neighborhood, in other words the protocol has to see to it that no two nodes use the same code at the same time as another within two hops. HAMA supports both unicast and broadcast transmission in a time slot with the senders spreading code, during which no other neighbor (one- nor two-hop) can transmit. Multiple unicast transmissions during one timeslot can take place (because of different spreading codes). One time slot is long enough to accommodate the transmission of one packet. The priority scheme we talked about earlier works in the following way: Each terminal will be in a state corresponding to its own priority compared to the terminals around it. Only terminals with a higher priority are allowed to transmit to terminals with lower priority. The following states are defined in HAMA:
When a terminal compares the priorities of the neighborhood with its own and determines that is can transmit (i.e. states BT, UT or DT) it must select a set of one-hop neighbors that can receive its packets. On the other hand if a terminal determines that it is a receiver (R or D states), it has to choose a one-hop neighbor with the highest priority whose spreading code it must listen to. There is still the open issue of how the priority information is spread in the neighborhood. This information cannot be spread with the collision-free channel because we need that information in order for the channel to work in the first place. For this purpose, another channel for distributing information among one- and two-hop neighbors is used. It is a common channel based on a best-effort model, with a known spreading code. Over this channel the so-called neighbor protocol is run. For instance when two terminals become neighbors they exchange complete one-hop neighbor information and both inform their one-hop neighbors about the new link. Also, hello messages are sent over this channel in order to maintain connectivity. In case of link breakage a neighbor delete message is sent out. In order to avoid the control messages of the neighbor protocol to become synchronized and cause collisions, a random amount of time is waited before transmitting them. Lastly, we give an example (fig. 2-6) of operation in an ad hoc network based on HAMA, also found in [Bao+02]. Here A becomes the BT because it has the highest priority. The terminals F, G and H are Drain receivers due to the fact that they have the lowest priorities. Nodes B and D are receivers because of their high priority neighbors. 
Fig. 2 6: Nodes in a HAMA network with assigned priorities. 2.2.9IEEE 802.11bA set of techniques for wireless networking (without routing) is given in a standard called 802.11b [IEEE99], by the Institute of Electrical and Electronics Engineering (IEEE). 802.11b networks uses the ISM band with either frequency hopping7 spread spectrum (SS) or direct sequence SS at the physical layer. For ad hoc networks distributed medium access algorithms make sense. The 802.11b also supports centralized access with help of a base station, but will not be discussed further here. For distributed medium access 802.11b defines an algorithm called Distributed Foundation Wireless MAC (DFWMAC). This MAC algorithm features a Distributed Coordination Function (DCF), which is also the foundation for the optional centralized medium access method, called Point Coordination Function (PCF). DCF uses a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) protocol. When a terminal is getting ready to transmit, it will first sense the medium to ensure that no other terminal is transmitting at the moment. If this is true, it will wait for a period corresponding to the priority of the packet and then if the medium is still idle, transmit. If the medium was found busy at either sensing points, it will start monitoring the current transmission, waiting for an acknowledgement (ACK) for the transmitted data to be overheard. During this time the terminal defers from transmitting. This also happens when a terminal overhears a RTS or CTS and asserts a “network allocated signal” for itself until an ACK is overheard. When the medium is sensed idle for the second time or an ACK is overheard, the terminals aspiring to transmit will still wait for a period determined by the binary exponential backoff method. This is done to reduce the risk of multiple terminals sending at the same time when the medium becomes idle. The priority scheme defines three different periods of delay, called Inter Frame Space (IFS, this is not a frame in the normal sense, but an interval). The shortest delay is called Short IFS (SIFS) and it is after this period time critical control packets are allowed to be sent. This includes RTS-CTS-ACK transmission. The following delay is called PCF IFS (PIFS), and is a medium length period only waited by a base station when it is used. DCF IFS (DIFS) is the longest period waited and is used for asynchronous traffic by any terminal when no traffic of higher priority exists. So, in effect the priority scheme lets ongoing RTS-CTS conversation pass before other traffic. After this the base station is allowed to take control in order to issue polls. The polls are themselves of SIFS priority. When no traffic mentioned above is present, ordinary terminals are allowed to seize the medium for asynchronous traffic. This means that if an ad hoc network is operating while a base station is present in some neighborhood of the ad hoc network, nodes within the range of the base station will gain access to the medium more frequently than those communicating directly. To prevent ad hoc terminals from starvation, a super frame (see fig.2-7) is defined. This frame contains two parts one for synchronous, contention free traffic and an asynchronous access method for contention based traffic. During the first part the base station may seize the medium and issue polls to stations. After that, the ad hoc terminals may contend for medium access during the latter part of the super frame. At the end of the super frame the base station starts to contend for access with PIFS priority. If this takes so long that the super frame interval is overrun, the contention free period will be shortened in the following super frame. 
Fig. 2 7: A super frame. To achieve higher transmission reliability, frames can be fragmented and sent one by one. This works because smaller frames are more likely to be received without errors. Every fragment has its own sequence number, checksum and every fragment has to be acknowledged before the next is sent. Larger fragment bursts can also be sent when medium access is acquired. 2.2.10BluetoothBluetooth8 does not follow the OSI layered model, but the layer that comes closest to the MAC sub layer [Tanenbaum03] is the Bluetooth layer called the “baseband”. Bluetooth uses a centralized TDM (Time Division Multiplexing) protocol for channel access, which means that terminals are synchronized in time with a central authority called a “master” in order to know when time boundaries for transmission are. The slots are 625sec long and half is allocated to the master and the other half to slaves. Frames can be of length 1, 3 or 5 slots (625b, 1875b and 3125b). It is more efficient to transmit longer frames not only because less hopping is done, but also only one header is needed instead of many. A negative effect of long frames is that the likelihood if transmission error in a packet will increase. No direct communication between slaves is possible therefore data has to be relayed by the master. We will now describe how two devices find each other with Bluetooth. Before data can be transferred with Bluetooth, identification9 and negotiation of roles (i.e. master and slave) must take place. This is done by sending inquiry packets on a common hopping sequence to surrounding devices if there is any. In order to have time to transmit queries and listen for answers, the inquirer has to hop twice as fast as terminals in the listening mode, which will reply. If there is more than one listener, the replies could collide and they therefore wait a random period in order to avoid collisions. A device in the vicinity replies with a Frequency Hop Synchronization (FHS) packet, which contains the listener’s address, class and clock offset. The device class identifies the type of device in question and can be used to query only certain classes of devices. The sender of the query is now able to transmit a unicast page message using the listener’s clock. If the receiver of the page message accepts the incoming connection (i.e. it has been specified to work with the other type of device), it will send an acknowledgement (ACK) to the pager. Upon receiving the ACK, the pager will become the master and the paged terminal slave. At this time the slave switches to a hopping sequence dictated by the master and the devices can begin transmitting data. Data is transmitted in slots where one hop frequency is used for every slot, in other words the hopping is only done between full packets. The slots can be reserved by the slaves and are granted by the master by polling, but no specific polling scheme is specified and this can be implemented as manufacturer sees fit. When new terminals are to be accepted into the piconet, the master can invite them after being discovered at page time. During the invitation-join sequence, operation in the piconet must be suspended. Additionally, to the seven active slaves on star-shaped piconet, it can contain inactive, parked devices in low-power mode, waking up periodically. If a slave joins the piconets of two masters, it can combine the two piconets into a so-called “scatternet”. Download 298.62 Kb. Share with your friends:
|