(Translated by https://www.hiragana.jp/)
Multiple Access with Collision Avoidance for Wireless: Difference between revisions - Wikipedia Jump to content

Multiple Access with Collision Avoidance for Wireless: Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
m Replacing File:MACAW.JPG with Commons version File:MACAW protocol.jpg (report errors here)
 
(21 intermediate revisions by 16 users not shown)
Line 1: Line 1:
{{Short description|Slotted medium access control protocol widely used in ad hoc networks}}
'''Multiple Access with Collision Avoidance for Wireless''' ('''MACAW''')<ref name="MACAW">{{cite journal|author=Vaduvur Bharghavan et al. |title=MACAW: A Medium Access Protocol for Wireless LAN's|url=http://pdos.csail.mit.edu/decouto/papers/bharghavan94.pdf|version=In the Proc. ACM SIGCOMM Conference (SIGCOMM '94), August 1994, pages 212-225|date=1994-08-01|accessdate=2007-01-18}}</ref> is a slotted [[Medium Access Control]] (MAC) protocol widely used in [[ad hoc network]]s.<ref name="SMAC_1">{{cite journal |author=Wei Ye et al. |title=An Energy-Efficient MAC Protocol for Wireless Sensor Networks |url=http://www.isi.edu/~weiye/pub/smac_infocom.pdf|version=INFOCOM 2002|date=2002-06-01|accessdate=2006-11-26 |archiveurl = http://web.archive.org/web/20061104045110/http://www.isi.edu/~weiye/pub/smac_infocom.pdf |archivedate = 2006-11-04}}</ref> Furthermore, it is the foundation of many other [[Medium Access Control|MAC]] protocols used in [[Wireless Sensor Networks]] (WSN).<ref name="SMAC_1"/> The [[IEEE 802.11 RTS/CTS]] mechanism is adopted from this protocol.<ref name="SMAC_2">{{cite journal |author=Wei Ye et al. |title=Medium Access Control With Coordinated Adaptive Sleeping for Wireless Sensor Networks |url=http://www.isi.edu/~weiye/pub/smac_ton.pdf|version=IEEE/ACM Transactions on Networking, Vol. 12, No. 3, pp. 493-506, June 2004|date=2004-06-01|accessdate=2006-12-27 |archiveurl = http://web.archive.org/web/20061209195620/http://www.isi.edu/~weiye/pub/smac_ton.pdf |archivedate = 2006-12-09}}</ref><ref name=holger>{{cite book | last = Karl| first = Holger | authorlink = Holger Karl | year = 2005| title =Protocols and Architectures for Wireless Sensor Networks | publisher = Wiley | isbn = 0-470-09510-5 | page = 117}}</ref> 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 terminal problem]].<ref name="MACAW"/> 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.<ref name="MACAW"/>
'''Multiple Access with Collision Avoidance for Wireless''' ('''MACAW''')<ref name="MACAW">{{cite journal|author=Vaduvur Bharghavan|title=MACAW: A Medium Access Protocol for Wireless LAN's|url=http://pdos.csail.mit.edu/decouto/papers/bharghavan94.pdf|version=In the Proc. ACM SIGCOMM Conference (SIGCOMM '94), August 1994, pages 212-225|date=1994-08-01|accessdate=2007-01-18|display-authors=etal}}</ref> is a slotted [[medium access control]] (MAC) protocol widely used in [[ad hoc network]]s.<ref name="SMAC_1">{{cite journal |author=Wei Ye|title=An Energy-Efficient MAC Protocol for Wireless Sensor Networks |url=http://www.isi.edu/~weiye/pub/smac_infocom.pdf|version=INFOCOM 2002|date=2002-06-01|accessdate=2006-11-26 |archiveurl = https://web.archive.org/web/20061104045110/http://www.isi.edu/~weiye/pub/smac_infocom.pdf |archivedate = 2006-11-04|display-authors=etal}}</ref> Furthermore, it is the foundation of many other MAC protocols used in [[wireless sensor networks]] (WSN).<ref name="SMAC_1"/> The [[IEEE 802.11 RTS/CTS]] mechanism is adopted from this protocol.<ref name="SMAC_2">{{cite journal |author=Wei Ye|title=Medium Access Control With Coordinated Adaptive Sleeping for Wireless Sensor Networks |url=http://www.isi.edu/~weiye/pub/smac_ton.pdf|version=IEEE/ACM Transactions on Networking, Vol. 12, No. 3, pp. 493-506, June 2004|date=2004-06-01|accessdate=2006-12-27 |archiveurl = https://web.archive.org/web/20061209195620/http://www.isi.edu/~weiye/pub/smac_ton.pdf |archivedate = 2006-12-09|display-authors=etal}}</ref><ref name=holger>{{cite book | last = Karl| first = Holger | author-link = Holger Karl | year = 2005| title =Protocols and Architectures for Wireless Sensor Networks | url = https://archive.org/details/protocolsarchite00karl| url-access = limited| publisher = Wiley | isbn = 0-470-09510-5 | page = [https://archive.org/details/protocolsarchite00karl/page/n144 117]}}</ref> 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]].<ref name="MACAW"/> 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.<ref name="MACAW"/>


== Principles of operation ==
== Principles of operation ==
[[Image:MACAW.JPG|thumb|450px|An example to illustrate the principle of MACAW. It is assumed that only adjacent nodes are in transmission range of each other.]]
[[File:MACAW protocol.jpg|thumb|450px|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.<ref name="MACAW"/>
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.<ref name="MACAW"/>


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.<ref name="MACAW"/>
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.<ref name="MACAW"/>
Line 24: Line 23:


=== RRTS <ref name="MACAW"/>===
=== RRTS <ref name="MACAW"/>===
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 D. 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).
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).
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).
Line 37: Line 36:
# “Data Sending” frame (DS) from D to C
# “Data Sending” frame (DS) from D to C
# DATA fragment frame from D to C,
# DATA fragment frame from D to C,
# Acknowledgement frame (ACK) from C to D.
# Acknowledgement frame (ACK) from C to D


==Ongoing research==
==Ongoing research==
Additional back-off algorithms have been developed and researched to improve performance.<ref>P. Venkata Krishna, Sudip Misra, [[Mohammad S. Obaidat|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</ref><ref>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</ref><ref>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.</ref><ref>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</ref> 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. This reduces the number of collisions.
Additional back-off algorithms have been developed and researched to improve performance.<ref name=Miao>{{cite book|author1=Guowang Miao|author-link=Guowang Miao|author2=Guocong Song|title=Energy and spectrum efficient wireless network design|publisher=[[Cambridge University Press]]|isbn=978-1107039889|year=2014}}</ref><ref>P. Venkata Krishna, Sudip Misra, [[Mohammad S. Obaidat|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</ref><ref>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</ref><ref>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.</ref><ref>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</ref> 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.<ref name="Miao"/> This reduces the number of collisions.


=== Unsolved problems ===
=== 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 not 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.
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]].
Furthermore, MACAW might not behave normally in [[multicast]]ing.


== See also ==
== See also ==
Line 51: Line 50:


== References ==
== References ==
{{Reflist}}
<references/>


{{Channel access methods}}
{{Channel access methods}}
Line 57: Line 56:
[[Category:Wireless sensor network]]
[[Category:Wireless sensor network]]
[[Category:Media access control]]
[[Category:Media access control]]

[[de:Carrier Sense Multiple Access/Collision Avoidance]]

Latest revision as of 23:27, 11 April 2024

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]

Principles of operation[edit]

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][edit]

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[edit]

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[edit]

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[edit]

References[edit]

  1. ^ a b c d e f g h 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. ^ a b 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. ^ a b 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Multiple_Access_with_Collision_Avoidance_for_Wireless&oldid=1218481482"