International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(2): 145-151
Published online June 25, 2021
https://doi.org/10.5391/IJFIS.2021.21.2.145
© The Korean Institute of Intelligent Systems
Jaesung Park1 and Changyong Yoon2
1School of Information Convergence, Kwangwoon University, Seoul, Korea
2Department of AI Software Convergence, Suwon Science College, Hwaseong, Korea
Correspondence to :
Changyong Yoon (cyyoon@ssc.ac.kr)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Wireless local area network (WLAN) uses a medium access control method based on the carrier sense multiple access with collision avoidance (CSMA/CA). In CSMA/CA, each station maintains a contention window by adjusting its size according to the perceived contention level. By making a station autonomously choose a waiting time randomly, using its current contention window size, CSMA/CA resolves the channel contention problem among a set of stations in a distributed manner. However, because the contention window size is limited, the packet collision probability increases sharply as the number of stations, with data to send, increases. To resolve this problem, we propose a novel medium access control method using a minority game. In the proposed method, each station learns the current contention level in a distributed manner and decides whether to send a packet using the acquired knowledge to decrease its packet collision probability. Through simulation studies, we show that compared with CSMA/CA and random selection methods, the proposed method decreases both the packet collision probability and the time interval between successful packet transmissions.
Keywords: Medium access control, CSMA/CA, Minority game, Inductive reasoning
The transmission rate of a wireless local area network (WLAN) is increased by improving the physical layer [1,2]. However, the medium access control layer is still based on carrier sense multiple access with collision avoidance (CSMA/CA) [1,3]. CSMA/CA is a random access control method that operates in a distributed manner. In CSMA/CA, if a station has a packet to send, it first checks if there is an ongoing transmission in the communication channel. If the station senses that the channel is idle, it suspends the packet transmission for a random amount of time to avoid packet collisions. A station sets the waiting time by randomly choosing a value from the interval between the minimum the maximum contention window (CW) size that it maintains.
Every time a station experiences a packet collision, it doubles the maximum CW size to reduce the probability of packet collision. However, the maximum CW size is limited by a predefined threshold value. Therefore, as the number of stations with data to send increases, the packet collision probability increases sharply, even in an environment where each station has a sufficient number of transmission opportunities [4]. Packet collisions can be avoided by using a very large CW. However, the average packet transfer delay increases with CW size [5].
Various optimization methods have been proposed to resolve this problem [6–8]. These methods are based on adjusting the CW size according to the network environment. However, they assume a saturation case in which all stations always have packets to send. They also assume that the number of stations competing for packet transmission is known a priori, when in reality it is difficult for a station to know in advance. In addition, they make a station exchange information with other stations or access points (APs) to estimate the system parameters needed for CW optimization, which compromises the distributed nature of the random access control method.
To address this issue, we propose a novel medium access control method through inductive reasoning (MACIR). We adopt the minority game (MG) theory in [9] to devise the MACIR. Using MACIR, a station learns the network contention level through its packet transmission experiences. Using the intelligence obtained from past packet transmission, a station controls its packet transmission autonomously to maximize successful packet transmission probability, without any information exchanges with other entities. Because MACIR is based on the MG, the number of stations sending packets is maintained at a desired level, in a distributed manner, even though stations make decisions on their packet transmissions selfishly to maximize their benefits. Through simulation studies that compare the performance of MACIR and that of CSMA/CA, we show that MACIR decreases both the packet collision probability and the time interval between successful packet transmissions.
The remainder of this paper is organized as follows. In Section 2, we summarize related work. In Section 3, we present the MACIR algorithm. After showing the validity of the proposed method, by showing the simulation results in Section 4, we conclude the paper in Section 5.
Game theory has been widely used to resolve the problems involved in designing communication networks [10–12]. The algorithms based on game theory are designed based on the assumption that the game players are fully rational. In addition, all the information needed for a game player is assumed to be available when the player makes a decision. Based on these assumptions, each game player makes a decision through deductive reasoning to maximize its profit selfishly.
However, it is not guaranteed that all players in a game are rational. Furthermore, in communication networks, it is common for a player to not have all the information when it needs to make a decision. For example, a player can observe the result of a game that is caused by a combination of decisions made by individual players. However, each player cannot know the decisions made by each player.
The MG notes that some players in the game are partially rational and make decisions through inductive reasoning. In the MG, a player adjusts its game strategy using only the past
Various studies have been conducted on IEEE 802.11 MAC protocols. The performance of the distributed coordination function in the IEEE 802.11 specification was analyzed mathematically and through computer simulations [14,15]. The authors in [16] proposed a collision-rate-based backoff algorithm. They found a collision rate range giving superior transmission performance through simulation studies and adjusted the CW size, according to the collision rate, to improve efficiency. In [17], the authors proposed a multichannel MAC for a cognitive WLAN. They proposed two Markov chain models and derived the throughput and delay of cognitive radios. The authors in [18] analyzed the distributed coordination function with in-band full-duplex capabilities. They also proposed two frame aggregation methods to enhance the data transmission efficiency of an in-band full-duplex WLAN. In [4], the authors found two parameter settings that resulted in two different throughput stable regions. They also proposed a method that can identify the two regions quickly and accurately. A dynamic adaptive success-collision (DASC) backoff algorithm proposed in [8] uses two threshold values to distinguish low traffic loads and high traffic loads. The backoff algorithm adopted in DASC takes proactive measures to optimize the delay and throughput for a contention-based vehicular network. However, these conventional methods were optimized for a specific operating environment. In addition, they make assumptions on the underlying dynamics, involved in packet transmission, to simplify the analysis.
In this study, we propose a medium access control method, using a MG. Unlike conventional methods, the proposed method does not require any information, except for the game result, for a station to make a packet transmission decision. Nevertheless, the proposed method maintains the number of sending stations at the level that a system operator specifies, in a distributed manner.
In this section, we present an algorithm for a station to control medium access in a distributed manner, through inductive reasoning. Before proceeding, we summarize the notations used in this study in Table 1. When a station has a packet to send and senses that a channel is idle, MACIR is used to decide whether to send a packet or suspend the packet transmission until the next transmission opportunity.
A set of stations using the same AP is regarded as the player in the packet transmission game. An AP keeps track of the average packet collision rate during a given time interval. If the average packet collision rate is larger than a predefined threshold value
Station
Each strategy of a station is associated with a score that quantifies the suitability of the strategy. If we denote the score of the
where
When a station has a packet to send and senses an idle channel, it selects the strategy table to determine an action by choosing the strategy table that has the highest score value.
Let us denote the entry in the strategy table
We carried out simulation studies to validateMACIR by comparing its performance with that of the conventional methods under the same environment. We deployed 5,000 stations and one AP in an area where each station is within the transmission range of the other stations and the AP so that they interfere with each other’s transmissions. According to the IEEE 802.11 standard, we set the minimum CW size to 32 and the maximum CW size to 1,024. To simulate a severe congestion environment, we assume that each station always has a packet to send. In addition, to focus on the error that occurs at aMAC layer, which is caused by the packet transmission collision, we assume that a packet is not corrupted by a wireless channel. We considered two conventional methods for the performance comparison. In the first method, each station probabilistically decides whether to send a packet according to a uniform distribution. Specifically, a station chooses a random number
Figure 1 shows the packet collision probability over time. We can observe, in Figure 1, that the packet collision probability is the smallest when MACIR is used. In addition, the packet collision probability obtained by MACIR is close to the threshold value for the packet collision probability. Because the congestion level is high, almost all packets sent by following the CSMA/CA collide with each other. In MACIR, each station learns the collision status of the network and autonomously controls its packet transmission. Therefore, the packet collision probability obtained by MACIR was lower than that obtained by the uniformly random approach.
To compare each method with respect to the number of packets that are sent successfully, we scrutinize Figure 2, which shows the cumulative probability distribution of the number of packets sent successfully. In Figure 2, the x-axis represents the number of packets sent successfully, and the y-axis represents the cumulative probability of the corresponding values on the x-axis. For a fair comparison, the total number of packets sent by each method was set to the same value when we obtained Figure 2. We can observe that the number of packets sent successfully is the highest when MACIR is used. For example, let us denote the number of packets sent successfully when the y-axis is 0.9
Figure 3 compares the three methods in terms of inter-packet successful transmission time. The inter-packet successful transmission time is defined as the time difference between the time that a station sends a packet for the first time and the time that the packet is finally transmitted without collision. We can observe that CSMA/CA results in the longest inter-packet successful transmission time. MACIR provides a smaller inter-packet successful transmission time than the uniformly random approach. Specifically, 75% of the inter-packet successful transmission times, obtained by MACIR, are less than those when uniformly random is applied. We also observe that MACIR has a longer tail distribution than the uniformly random approach, which means that 25% of the inter-packet successful transmission times obtained by MACIR are larger than those obtained by uniform random.
In Figure 4, we show the cumulative probability distribution of the successful packet transmission rate when the number of stations is reduced to 4,000. The successful packet transmission rate is defined as the number of packets sent successfully over the number of packets sent. We observe that MACIR provides the highest successful packet transmission rate. In the case of CSMA/CA, the successful packet transmission rate was less than 5%. In the case of uniform random, the successful packet transmission rate is less than 17, while the successful packet transmission rate increases to 21 when MACIR is used.
In this paper, we proposed a novel medium-access control method, using MG theory. Each station participating in the packet transmission game determines whether to send a packet based on the intelligence acquired from past game results. Unlike conventional methods, the proposed method does not require the exchange of information with other stations. Through simulation studies, we show that MACIR drives the packet collision probability to a pre-defined threshold value in a distributed manner, even though each station selfishly decides its packet transmission decision to maximize its successful packet transmission probability. We also show that, compared with CSMA/CA and uniform random methods, MACIR increases the number of packets that are sent successfully and decreases the inter-packet successful transmission time. In addition, the successful packet transmission rate, obtained by MACIR, was higher than those obtained by CSMA/CA and uniform random methods. In future work, we will extend MACIR so that it can support a set of traffic classes that require different types of quality of services.
No potential conflict of interest relevant to this article was reported.
Symbols used in this paper.
Symbol | Meaning |
---|---|
Length of the packet transmission history that a station uses to determine an action. | |
The most recent | |
Action specified in the | |
Score of the | |
A threshold value for the packet collision probability that an AP attempt to maintain. |
E-mail: jaesungpark@kw.ac.kr
E-mail: cyyoon@ssc.ac.kr
International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(2): 145-151
Published online June 25, 2021 https://doi.org/10.5391/IJFIS.2021.21.2.145
Copyright © The Korean Institute of Intelligent Systems.
Jaesung Park1 and Changyong Yoon2
1School of Information Convergence, Kwangwoon University, Seoul, Korea
2Department of AI Software Convergence, Suwon Science College, Hwaseong, Korea
Correspondence to:Changyong Yoon (cyyoon@ssc.ac.kr)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Wireless local area network (WLAN) uses a medium access control method based on the carrier sense multiple access with collision avoidance (CSMA/CA). In CSMA/CA, each station maintains a contention window by adjusting its size according to the perceived contention level. By making a station autonomously choose a waiting time randomly, using its current contention window size, CSMA/CA resolves the channel contention problem among a set of stations in a distributed manner. However, because the contention window size is limited, the packet collision probability increases sharply as the number of stations, with data to send, increases. To resolve this problem, we propose a novel medium access control method using a minority game. In the proposed method, each station learns the current contention level in a distributed manner and decides whether to send a packet using the acquired knowledge to decrease its packet collision probability. Through simulation studies, we show that compared with CSMA/CA and random selection methods, the proposed method decreases both the packet collision probability and the time interval between successful packet transmissions.
Keywords: Medium access control, CSMA/CA, Minority game, Inductive reasoning
The transmission rate of a wireless local area network (WLAN) is increased by improving the physical layer [1,2]. However, the medium access control layer is still based on carrier sense multiple access with collision avoidance (CSMA/CA) [1,3]. CSMA/CA is a random access control method that operates in a distributed manner. In CSMA/CA, if a station has a packet to send, it first checks if there is an ongoing transmission in the communication channel. If the station senses that the channel is idle, it suspends the packet transmission for a random amount of time to avoid packet collisions. A station sets the waiting time by randomly choosing a value from the interval between the minimum the maximum contention window (CW) size that it maintains.
Every time a station experiences a packet collision, it doubles the maximum CW size to reduce the probability of packet collision. However, the maximum CW size is limited by a predefined threshold value. Therefore, as the number of stations with data to send increases, the packet collision probability increases sharply, even in an environment where each station has a sufficient number of transmission opportunities [4]. Packet collisions can be avoided by using a very large CW. However, the average packet transfer delay increases with CW size [5].
Various optimization methods have been proposed to resolve this problem [6–8]. These methods are based on adjusting the CW size according to the network environment. However, they assume a saturation case in which all stations always have packets to send. They also assume that the number of stations competing for packet transmission is known a priori, when in reality it is difficult for a station to know in advance. In addition, they make a station exchange information with other stations or access points (APs) to estimate the system parameters needed for CW optimization, which compromises the distributed nature of the random access control method.
To address this issue, we propose a novel medium access control method through inductive reasoning (MACIR). We adopt the minority game (MG) theory in [9] to devise the MACIR. Using MACIR, a station learns the network contention level through its packet transmission experiences. Using the intelligence obtained from past packet transmission, a station controls its packet transmission autonomously to maximize successful packet transmission probability, without any information exchanges with other entities. Because MACIR is based on the MG, the number of stations sending packets is maintained at a desired level, in a distributed manner, even though stations make decisions on their packet transmissions selfishly to maximize their benefits. Through simulation studies that compare the performance of MACIR and that of CSMA/CA, we show that MACIR decreases both the packet collision probability and the time interval between successful packet transmissions.
The remainder of this paper is organized as follows. In Section 2, we summarize related work. In Section 3, we present the MACIR algorithm. After showing the validity of the proposed method, by showing the simulation results in Section 4, we conclude the paper in Section 5.
Game theory has been widely used to resolve the problems involved in designing communication networks [10–12]. The algorithms based on game theory are designed based on the assumption that the game players are fully rational. In addition, all the information needed for a game player is assumed to be available when the player makes a decision. Based on these assumptions, each game player makes a decision through deductive reasoning to maximize its profit selfishly.
However, it is not guaranteed that all players in a game are rational. Furthermore, in communication networks, it is common for a player to not have all the information when it needs to make a decision. For example, a player can observe the result of a game that is caused by a combination of decisions made by individual players. However, each player cannot know the decisions made by each player.
The MG notes that some players in the game are partially rational and make decisions through inductive reasoning. In the MG, a player adjusts its game strategy using only the past
Various studies have been conducted on IEEE 802.11 MAC protocols. The performance of the distributed coordination function in the IEEE 802.11 specification was analyzed mathematically and through computer simulations [14,15]. The authors in [16] proposed a collision-rate-based backoff algorithm. They found a collision rate range giving superior transmission performance through simulation studies and adjusted the CW size, according to the collision rate, to improve efficiency. In [17], the authors proposed a multichannel MAC for a cognitive WLAN. They proposed two Markov chain models and derived the throughput and delay of cognitive radios. The authors in [18] analyzed the distributed coordination function with in-band full-duplex capabilities. They also proposed two frame aggregation methods to enhance the data transmission efficiency of an in-band full-duplex WLAN. In [4], the authors found two parameter settings that resulted in two different throughput stable regions. They also proposed a method that can identify the two regions quickly and accurately. A dynamic adaptive success-collision (DASC) backoff algorithm proposed in [8] uses two threshold values to distinguish low traffic loads and high traffic loads. The backoff algorithm adopted in DASC takes proactive measures to optimize the delay and throughput for a contention-based vehicular network. However, these conventional methods were optimized for a specific operating environment. In addition, they make assumptions on the underlying dynamics, involved in packet transmission, to simplify the analysis.
In this study, we propose a medium access control method, using a MG. Unlike conventional methods, the proposed method does not require any information, except for the game result, for a station to make a packet transmission decision. Nevertheless, the proposed method maintains the number of sending stations at the level that a system operator specifies, in a distributed manner.
In this section, we present an algorithm for a station to control medium access in a distributed manner, through inductive reasoning. Before proceeding, we summarize the notations used in this study in Table 1. When a station has a packet to send and senses that a channel is idle, MACIR is used to decide whether to send a packet or suspend the packet transmission until the next transmission opportunity.
A set of stations using the same AP is regarded as the player in the packet transmission game. An AP keeps track of the average packet collision rate during a given time interval. If the average packet collision rate is larger than a predefined threshold value
Station
Each strategy of a station is associated with a score that quantifies the suitability of the strategy. If we denote the score of the
where
When a station has a packet to send and senses an idle channel, it selects the strategy table to determine an action by choosing the strategy table that has the highest score value.
Let us denote the entry in the strategy table
We carried out simulation studies to validateMACIR by comparing its performance with that of the conventional methods under the same environment. We deployed 5,000 stations and one AP in an area where each station is within the transmission range of the other stations and the AP so that they interfere with each other’s transmissions. According to the IEEE 802.11 standard, we set the minimum CW size to 32 and the maximum CW size to 1,024. To simulate a severe congestion environment, we assume that each station always has a packet to send. In addition, to focus on the error that occurs at aMAC layer, which is caused by the packet transmission collision, we assume that a packet is not corrupted by a wireless channel. We considered two conventional methods for the performance comparison. In the first method, each station probabilistically decides whether to send a packet according to a uniform distribution. Specifically, a station chooses a random number
Figure 1 shows the packet collision probability over time. We can observe, in Figure 1, that the packet collision probability is the smallest when MACIR is used. In addition, the packet collision probability obtained by MACIR is close to the threshold value for the packet collision probability. Because the congestion level is high, almost all packets sent by following the CSMA/CA collide with each other. In MACIR, each station learns the collision status of the network and autonomously controls its packet transmission. Therefore, the packet collision probability obtained by MACIR was lower than that obtained by the uniformly random approach.
To compare each method with respect to the number of packets that are sent successfully, we scrutinize Figure 2, which shows the cumulative probability distribution of the number of packets sent successfully. In Figure 2, the x-axis represents the number of packets sent successfully, and the y-axis represents the cumulative probability of the corresponding values on the x-axis. For a fair comparison, the total number of packets sent by each method was set to the same value when we obtained Figure 2. We can observe that the number of packets sent successfully is the highest when MACIR is used. For example, let us denote the number of packets sent successfully when the y-axis is 0.9
Figure 3 compares the three methods in terms of inter-packet successful transmission time. The inter-packet successful transmission time is defined as the time difference between the time that a station sends a packet for the first time and the time that the packet is finally transmitted without collision. We can observe that CSMA/CA results in the longest inter-packet successful transmission time. MACIR provides a smaller inter-packet successful transmission time than the uniformly random approach. Specifically, 75% of the inter-packet successful transmission times, obtained by MACIR, are less than those when uniformly random is applied. We also observe that MACIR has a longer tail distribution than the uniformly random approach, which means that 25% of the inter-packet successful transmission times obtained by MACIR are larger than those obtained by uniform random.
In Figure 4, we show the cumulative probability distribution of the successful packet transmission rate when the number of stations is reduced to 4,000. The successful packet transmission rate is defined as the number of packets sent successfully over the number of packets sent. We observe that MACIR provides the highest successful packet transmission rate. In the case of CSMA/CA, the successful packet transmission rate was less than 5%. In the case of uniform random, the successful packet transmission rate is less than 17, while the successful packet transmission rate increases to 21 when MACIR is used.
In this paper, we proposed a novel medium-access control method, using MG theory. Each station participating in the packet transmission game determines whether to send a packet based on the intelligence acquired from past game results. Unlike conventional methods, the proposed method does not require the exchange of information with other stations. Through simulation studies, we show that MACIR drives the packet collision probability to a pre-defined threshold value in a distributed manner, even though each station selfishly decides its packet transmission decision to maximize its successful packet transmission probability. We also show that, compared with CSMA/CA and uniform random methods, MACIR increases the number of packets that are sent successfully and decreases the inter-packet successful transmission time. In addition, the successful packet transmission rate, obtained by MACIR, was higher than those obtained by CSMA/CA and uniform random methods. In future work, we will extend MACIR so that it can support a set of traffic classes that require different types of quality of services.
Comparison of data collision rate.
Comparison of the number of packets sent successfully.
Comparison of the inter packet successful transmission time.
Comparison of the successful packet transmission rate.
Symbols used in this paper.
Symbol | Meaning |
---|---|
Length of the packet transmission history that a station uses to determine an action. | |
The most recent | |
Action specified in the | |
Score of the | |
A threshold value for the packet collision probability that an AP attempt to maintain. |
Comparison of data collision rate.
|@|~(^,^)~|@|Comparison of the number of packets sent successfully.
|@|~(^,^)~|@|Comparison of the inter packet successful transmission time.
|@|~(^,^)~|@|Comparison of the successful packet transmission rate.