Multiple Access with Collision Avoidance for Wireless

Last updated

Multiple Access with Collision Avoidance for Wireless (MACAW) [1] is a slotted medium access control (MAC) protocol widely used in ad hoc networks. [2] Furthermore, it is the foundation of many other MAC protocols used in wireless sensor networks (WSN). [2] The IEEE 802.11 RTS/CTS mechanism is adopted from this protocol. [3] [4] It uses RTS-CTS-DS-DATA-ACK frame sequence for transferring data, sometimes preceded by an RTS-RRTS frame sequence, in view to provide solution to the hidden node problem. [1] Although protocols based on MACAW, such as S-MAC, use carrier sense in addition to the RTS/CTS mechanism, MACAW does not make use of carrier sense. [1]

Contents

Principles of operation

An example to illustrate the principle of MACAW. It is assumed that only adjacent nodes are in transmission range of each other. MACAW protocol.jpg
An example to illustrate the principle of MACAW. It is assumed that only adjacent nodes are in transmission range of each other.

Assume that node A has data to transfer to node B. Node A initiates the process by sending a Request to Send frame (RTS) to node B. The destination node (node B) replies with a Clear To Send frame (CTS). After receiving CTS, node A sends data. After successful reception, node B replies with an acknowledgement frame (ACK). If node A has to send more than one data fragment, it has to wait a random time after each successful data transfer and compete with adjacent nodes for the medium using the RTS/CTS mechanism. [1]

Any node overhearing an RTS frame (for example node F or node E in the illustration) refrains from sending anything until a CTS is received, or after waiting a certain time. If the captured RTS is not followed by a CTS, the maximum waiting time is the RTS propagation time and the destination node turnaround time. [1]

Any node (node C and node E) overhearing a CTS frame refrains from sending anything for the time until the data frame and ACK should have been received (solving the hidden terminal problem), plus a random time. Both the RTS and CTS frames contain information about the length of the DATA frame. Hence a node uses that information to estimate the time for the data transmission completion. [1]

Before sending a long DATA frame, node A sends a short Data-Sending frame (DS), which provides information about the length of the DATA frame. Every station that overhears this frame knows that the RTS/CTS exchange was successful. An overhearing station (node F), which might have received RTS and DS but not CTS, defers its transmissions until after the ACK frame should have been received plus a random time. [1]

To sum up, a successful data transfer (A to B) consists of the following sequence of frames:

  1. “Request To Send” frame (RTS) from A to B
  2. “Clear To Send” frame (CTS) from B to A
  3. “Data Sending” frame (DS) from A to B
  4. DATA fragment frame from A to B, and
  5. Acknowledgement frame (ACK) from B to A.

MACAW is a non-persistent slotted protocol, meaning that after the medium has been busy, for example after a CTS message, the station waits a random time after the start of a time slot before sending an RTS. This results in fair access to the medium. If for example nodes A, B and C have data fragments to send after a busy period, they will have the same chance to access the medium since they are in transmission range of each other.

RRTS [1]

Node D is unaware of the ongoing data transfer between node A and node B. Node D has data to send to node C, which is in the transmission range of node B. D initiates the process by sending an RTS frame to node C. Node C has already deferred its transmission until the completion of the current data transfer between node A and node B (to avoid co-channel interference at node B). Hence, even though it receives RTS from node D, it does not reply back with CTS. Node D assumes that its RTS was not successful because of collision and hence proceeds to back off (using an exponential backoff algorithm).

If A has multiple data fragments to send, the only instant when node D successfully can initiate a data transfer is during small gaps in between that node A has completed data transfer and completion of node B next CTS (for node A next data transfer request). However, due to the node D backoff time period the probability to capture the medium during this small time interval is not high. To increase the per-node fairness, MACAW introduces a new control message called "Request for Request to Send" (RRTS).

Now, when node C, which cannot reply earlier due to ongoing transmission between node A and node B, sends an RRTS message to node D during next contention period, the recipient of the RRTS (node D) immediately responds with an RTS and the normal message exchange is commenced. Other nodes overhearing an RRTS defer for two time slots, long enough to hear if a successful RTS–CTS exchange occurs.

To summarize, a transfer may in this case consist of the following sequence of frames between node D and C:

  1. “Request To Send” frame (RTS) from D to C
  2. “Request for Request to send” frame (RRTS) from C to D (after a short delay)
  3. “Request To Send” frame (RTS) from D to C
  4. “Clear To Send” frame (CTS) from C to D
  5. “Data Sending” frame (DS) from D to C
  6. DATA fragment frame from D to C,
  7. Acknowledgement frame (ACK) from C to D

Ongoing research

Additional back-off algorithms have been developed and researched to improve performance. [5] [6] [7] [8] [9] The basic principle is based on the use of sequencing techniques where each node in the wireless network maintains a counter which limits the number attempts to less than or equal to the sequence number or use wireless channel states to control the access probabilities so that a node with a good channel state has a higher probability of contention success. [5] This reduces the number of collisions.

Unsolved problems

MACAW does not generally solve the exposed terminal problem. Assume that node G has data to send to node F in our example. Node G has no information about the ongoing data transfer from A to B. It initiates the process by sending an RTS signal to node F. Node F is in the transmission range of node A and cannot hear the RTS from node G, since it is exposed to co-channel interference. Node G assumes that its RTS was not successful because of collision and hence backs off before it tries again. In this case, the solution provided by the RRTS mechanism will not improve the situation much since the DATA frames sent from B are rather long compared to the other frames. The probability that F is exposed to transmission from A is rather high. Node F has no idea about any node interested in initiating data transfer to it, until G happens to transmit an RTS in between transmissions from A.

Furthermore, MACAW might not behave normally in multicasting.

See also

Related Research Articles

<span class="mw-page-title-main">IEEE 802.11</span> Wireless network standard

IEEE 802.11 is part of the IEEE 802 set of local area network (LAN) technical standards, and specifies the set of medium access control (MAC) and physical layer (PHY) protocols for implementing wireless local area network (WLAN) computer communication. The standard and amendments provide the basis for wireless network products using the Wi-Fi brand and are the world's most widely used wireless computer networking standards. IEEE 802.11 is used in most home and office networks to allow laptops, printers, smartphones, and other devices to communicate with each other and access the Internet without connecting wires. IEEE 802.11 is also a basis for vehicle-based communication networks with IEEE 802.11p.

<span class="mw-page-title-main">Carrier-sense multiple access with collision avoidance</span> Computer network multiple access method

Carrier-sense multiple access with collision avoidance (CSMA/CA) in computer networking, is a network multiple access method in which carrier sensing is used, but nodes attempt to avoid collisions by beginning transmission only after the channel is sensed to be "idle". When they do transmit, nodes transmit their packet data in its entirety.

Carrier-sense multiple access with collision detection (CSMA/CD) is a medium access control (MAC) method used most notably in early Ethernet technology for local area networking. It uses carrier-sensing to defer transmissions until no other stations are transmitting. This is used in combination with collision detection in which a transmitting station detects collisions by sensing transmissions from other stations while it is transmitting a frame. When this collision condition is detected, the station stops transmitting that frame, transmits a jam signal, and then waits for a random time interval before trying to resend the frame.

<span class="mw-page-title-main">Medium access control</span> Service layer in IEEE 802 network standards

In IEEE 802 LAN/MAN standards, the medium access control (MAC), also called media access control, is the layer that controls the hardware responsible for interaction with the wired or wireless transmission medium. The MAC sublayer and the logical link control (LLC) sublayer together make up the data link layer. The LLC provides flow control and multiplexing for the logical link, while the MAC provides flow control and multiplexing for the transmission medium.

A controller area network is a vehicle bus standard designed to allow microcontrollers and devices to communicate with each other. It is a message-based protocol, designed originally for multiplex electrical wiring within automobiles to save on copper, but it can also be used in many other contexts. For each device, the data in a frame is transmitted serially but in such a way that if more than one device transmits at the same time, the highest priority device can continue while the others back off. Frames are received by all devices, including by the transmitting device.

IEEE 802.11e-2005 or 802.11e is an approved amendment to the IEEE 802.11 standard that defines a set of quality of service (QoS) enhancements for wireless LAN applications through modifications to the media access control (MAC) layer. The standard is considered of critical importance for delay-sensitive applications, such as voice over wireless LAN and streaming multimedia. The amendment has been incorporated into the published IEEE 802.11-2007 standard.

Distributed coordination function (DCF) is the fundamental medium access control (MAC) technique of the IEEE 802.11-based WLAN standard. DCF employs a carrier-sense multiple access with collision avoidance (CSMA/CA) with the binary exponential backoff algorithm.

<span class="mw-page-title-main">Hidden node problem</span> Problem in wireless networking

In wireless networking, the hidden node problem or hidden terminal problem occurs when a node can communicate with a wireless access point (AP), but cannot directly communicate with other nodes that are communicating with that AP. This leads to difficulties in medium access control sublayer since multiple nodes can send data packets to the AP simultaneously, which creates interference at the AP resulting in no packet getting through.

IEEE 802.15.4 is a technical standard which defines the operation of a low-rate wireless personal area network (LR-WPAN). It specifies the physical layer and media access control for LR-WPANs, and is maintained by the IEEE 802.15 working group, which defined the standard in 2003. It is the basis for the Zigbee, ISA100.11a, WirelessHART, MiWi, 6LoWPAN, Thread, Matter and SNAP specifications, each of which further extends the standard by developing the upper layers which are not defined in IEEE 802.15.4. In particular, 6LoWPAN defines a binding for the IPv6 version of the Internet Protocol (IP) over WPANs, and is itself used by upper layers like Thread.

RTS/CTS is the optional mechanism used by the 802.11 wireless networking protocol to reduce frame collisions introduced by the hidden node problem. Originally the protocol fixed the exposed node problem as well, but modern RTS/CTS includes ACKs and does not solve the exposed node problem.

Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. These algorithms find usage in a wide range of systems and processes, with radio networks and computer networks being particularly notable.

<span class="mw-page-title-main">Exposed node problem</span>

In wireless networks, the exposed node problem occurs when a node is prevented from sending packets to other nodes because of co-channel interference with a neighboring transmitter. Consider an example of four nodes labeled R1, S1, S2, and R2, where the two receivers are out of range of each other, yet the two transmitters in the middle are in range of each other. Here, if a transmission between S1 and R1 is taking place, node S2 is prevented from transmitting to R2 as it concludes after carrier sense that it will interfere with the transmission by its neighbor S1. However note that R2 could still receive the transmission of S2 without interference because it is out of range of S1.

In data communications, flow control is the process of managing the rate of data transmission between two nodes to prevent a fast sender from overwhelming a slow receiver. Flow control should be distinguished from congestion control, which is used for controlling the flow of data when congestion has actually occurred. Flow control mechanisms can be classified by whether or not the receiving node sends feedback to the sending node.

Selective Repeat ARQ or Selective Reject ARQ is a specific instance of the automatic repeat request (ARQ) protocol used to manage sequence numbers and retransmissions in reliable communications.

Ethernet Powerlink is a real-time protocol for standard Ethernet. It is an open protocol managed by the Ethernet POWERLINK Standardization Group (EPSG). It was introduced by Austrian automation company B&R in 2001.

Multiple access with collision avoidance (MACA) is a slotted media access control protocol used in wireless LAN data transmission to avoid collisions caused by the hidden station problem and to simplify exposed station problem.

Vehicular Reactive Routing protocol (VRR) is a reactive routing protocol with geographical features which is specifically designed for Wireless Access for the Vehicular Environment (WAVE) standard in vehicular ad hoc networks (VANETs). The protocol takes advantages of the multichannel scheme defined in WAVE and uses the Control Channel (CCH) for signalling, and relies on one of the multiple Service Channels (SCHs) for payload data dissemination.

The link layer is the lowest layer in the TCP/IP model. It is also referred to as the network interface layer and mostly equivalent to the data link layer plus physical layer in OSI. This particular layer has several unique security vulnerabilities that can be exploited by a determined adversary.

NACK-Oriented Reliable Multicast (NORM) is a transport layer Internet protocol designed to provide reliable transport in multicast groups in data networks. It is formally defined by the Internet Engineering Task Force (IETF) in Request for Comments (RFC) 5740, which was published in November 2009.

Sensor Media Access Control(S-MAC) is a network protocol for sensor networks. Sensor networks consist of tiny, wirelessly communicating computers, which are deployed in large numbers in an area to network independently and as long as monitor their surroundings in group work with sensors, to their energy reserves are depleted. A special form of ad hoc network, they make entirely different demands on a network protocol and therefore require network protocols specially build for them (SMAC). Sensor Media Access Control specifies in detail how the nodes of a sensor network exchange data, controls the Media Access Control (MAC) to access the shared communication medium of the network, regulates the structure of the network topology, and provides a method for synchronizing.

References

  1. 1 2 3 4 5 6 7 8 Vaduvur Bharghavan; et al. (1994-08-01). "MACAW: A Medium Access Protocol for Wireless LAN's" (PDF). In the Proc. ACM SIGCOMM Conference (SIGCOMM '94), August 1994, pages 212-225. Retrieved 2007-01-18.{{cite journal}}: Cite journal requires |journal= (help)
  2. 1 2 Wei Ye; et al. (2002-06-01). "An Energy-Efficient MAC Protocol for Wireless Sensor Networks" (PDF). INFOCOM 2002. Archived from the original (PDF) on 2006-11-04. Retrieved 2006-11-26.{{cite journal}}: Cite journal requires |journal= (help)
  3. ↑ Wei Ye; et al. (2004-06-01). "Medium Access Control With Coordinated Adaptive Sleeping for Wireless Sensor Networks" (PDF). IEEE/ACM Transactions on Networking, Vol. 12, No. 3, pp. 493-506, June 2004. Archived from the original (PDF) on 2006-12-09. Retrieved 2006-12-27.{{cite journal}}: Cite journal requires |journal= (help)
  4. ↑ Karl, Holger (2005). Protocols and Architectures for Wireless Sensor Networks . Wiley. p.  117. ISBN   0-470-09510-5.
  5. 1 2 Guowang Miao; Guocong Song (2014). Energy and spectrum efficient wireless network design. Cambridge University Press. ISBN   978-1107039889.
  6. ↑ P. Venkata Krishna, Sudip Misra, Mohhamed S. Obaidat and V. Saritha, “Virtual Backoff Algorithm: An Enhancement to 802.11 Medium Access Control to Improve the Performance of Wireless Networks” in IEEE Trans. on Vehicular Technology (VTS), 2010
  7. ↑ Sudip Misra, P. Venkata Krishna and Kiran Issac Abraham, “Learning Automata Solution for Medium Access with Channel Reservation in Wireless Networks” accepted in Wireless Personal Communications (WPS), Springer
  8. ↑ P. Venkata Krishna & N.Ch.S.N. Iyengar “Design of Sequencing Medium Access Control to improve the performance of Wireless Networks” Journal of Computing and Information Technology (CIT Journal), Vol. 16, No. 2, pp. 81-89, June 2008.
  9. ↑ P.Venkata Krishna & N.Ch.S.N.Iyengar, 'Sequencing Technique – An Enhancement to 802.11 Medium Access Control to improve the performance of Wireless Networks', Int. J. Communication Networks and Distributed Systems, Vol.1, No.1, pp 52-70, 2008
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.