search for


Distributed Medium Access Control Method through Inductive Reasoning
International Journal of Fuzzy Logic and Intelligent Systems 2021;21(2):145-151
Published online June 25, 2021
© 2021 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 (
Received April 26, 2021; Revised April 26, 2021; Accepted June 9, 2021.
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License ( which permits unrestricted non-commercial 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
1. Introduction

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 [68]. 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.

2. RelatedWork

2.1 Minority Game

Game theory has been widely used to resolve the problems involved in designing communication networks [1012]. 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 n game results. Then, a player makes a binary decision according to the best game strategy available at its decision time. The MG mechanism enables a fair share of resources among the players even though they act selfishly to maximize their own profits [13].


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.

3. Medium Access Control through Inductive Reasoning

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 θ, the AP broadcasts δ = 1 to indicating that the current congestion level is high. Otherwise, an AP broadcasts δ = 0 which indicates that the packet collision rate is not severe. The information δ is used as the result of the packet transmission game.

Station i maintains the most recent η game history before the t-th transmission opportunity, which is denoted by ϕi(t). A station makes a binary decision using the past packet transmission results. As the length of the packet transmission history that a station maintains to determine an action is η, there can be 22η strategy tables. Among the possible strategy tables, a station randomly selects n strategy tables to configure its set of strategy tables Ωi = {Si,1, . . ., Si,j, . . ., Si,n} to use the packet transmission game, where Si,j is the j-th strategy table that station i maintains. Each strategy table Si,j is composed of 2η elements and each element in Si,j is composed of an instance of a η game result si,j,k and a binary decision variable ai,j,k. When the η game results are k and ai,j,k = 1, it indicates that a station should send a packet at the first packet transmission opportunity. In contrast, ai,j,k = 0 indicates that a station must suspend packet transmission.

Each strategy of a station is associated with a score that quantifies the suitability of the strategy. If we denote the score of the j-th strategy table of station i, when station i receives the τ-th game results as ψi,j(τ), it is updated whenever the station receives the game result δ from an AP as follows:


where αi,j,ϕi(t) is an action, specified in the j-th strategy table of station i, when the most recent η game history is ϕi(t). We note that the score ψi,j(t) is updated irrespective of whether Si,j is used to determine a packet transmission action at the t-th transmission opportunity.

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 Si,j* that matches the most recent game history ϕi(t) as si,j*i(t). Then, the action that station i takes becomes the binary decision variable ai,j*i(t) which is associated with si,j*i(t).

4. Performance Evaluation

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 p from [0, 1] in a uniformly random manner. If p is greater than 0.5, the station decides to send a packet. Otherwise, the station chooses to suspend packet transmission. Henceforth, we refer to this method as uniformly random. The second method is the standard CSMA/CA method. In the case of the proposed method, we set the length of the game history to 10 so that each station had 1,024 strategy table entries. We also set the number of strategy tables that a station has, to two and the collision threshold value to 0.5. We repeated the same simulations 20,000 times by varying the seed number and obtained the results by averaging each simulation result.

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α. When CSMA/CA is used, α=50 and α increases to 220 when a uniformly random approach is used. When MACIR is used, α is approximately 450. From Figure 2, we see that MACIR decreases the packet collision probability more than the other methods.

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.

5. Conclusion

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.


This research was supported by the Ministry of Science and ICT (MIST) under the National Program for Excellence in SW (No. 2017-0-00096), supervised by the Institute for Information & Communications Technology Planning & Evaluation (IITP).

Conflict of Interest

No potential conflict of interest relevant to this article was reported.

Fig. 1.

Comparison of data collision rate.

Fig. 2.

Comparison of the number of packets sent successfully.

Fig. 3.

Comparison of the inter packet successful transmission time.

Fig. 4.

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.
ϕi(t) The most recent η game history before t-th transmission opportunity.
Si,j j-th strategy table that a station i maintains.
si,j,k k-th element in the j-th strategy table of a station i.
ai,j,ϕi(t) Action specified in the j-th strategy table of a station i when the most recent game. history is ϕi(t).
ψi,j(τ) Score of the j-th strategy table of a station i when the station receives the τ-th packet transmission game result.
θ A threshold value for the packet collision probability that an AP attempt to maintain.

  1. IEEE Standard for Information Technology (2021). Telecommunications and Information Exchange between Systems - Local and Metropolitan Area Networks—Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications
  2. Deng, C, Fang, X, Han, X, Wang, X, Yan, L, He, R, Long, Y, and Guo, Y (2020). IEEE 802.11 be Wi-Fi 7: new challenges and opportunities. IEEE Communications Surveys & Tutorials. 22, 2136-2166.
  3. Karmakar, R, Chattopadhyay, S, and Chakraborty, S (2017). Impact of IEEE 802.11 n/ac PHY/MAC high throughput enhancements on transport and application protocols: a survey. IEEE Communications Surveys & Tutorials. 19, 2050-2091.
  4. Zhao, Q, Feng, L, Zhao, L, Li, Z, and Liang, Y (2020). SatOpt partition: dividing throughput-stability region for IEEE 802.11 DCF networks. IEEE Transactions on Vehicular Technology. 69, 10278-10290.
  5. Karabulut, MA, Shah, AS, and Ilhan, H . The effect of contention window size of the IEEE 802.11 DCF for VANETs., Proceedings of 2018 26th Signal Processing and Communications Applications Conference (SIU), 2018, Izmir, Turkey, Array, pp.1-4.
  6. Zerguine, N, Aliouat, Z, Mostefai, M, and Harous, S . M-BEB: enhanced and fair binary exponential back-off., Proceedings of 2020 14th International Conference on Innovations in Information Technology (IIT), 2020, Al Ain, UAE, Array, pp.142-147.
  7. Chao, IF, Lai, CW, and Chung, YH . A reservation-based distributed MAC scheme for infrastructure wireless networks., Proceedings of 2018 3rd International Conference on Intelligent Green Building and Smart Grid (IGBSG), 2018, Yilan, Taiwan, Array, pp.1-4.
  8. Wu, G, and Xu, P (2017). Improving performance by a dynamic adaptive success-collision backoff algorithm for contention-based vehicular network. IEEE Access. 6, 2496-2505.
  9. Coolen, ACC (2005). The Mathematical Theory of Minority Games: Statistical Mechanics of Interacting Agents. Oxford, UK: Oxford University Press
  10. Trestian, R, Ormond, O, and Muntean, GM (2012). Game theory-based network selection: solutions and challenges. IEEE Communications Surveys & Tutorials. 14, 1212-1231.
  11. Mkiramweni, ME, Yang, C, Li, J, and Zhang, W (2019). A survey of game theory in unmanned aerial vehicles communications. IEEE Communications Surveys & Tutorials. 21, 3386-3416.
  12. Moura, J, and Hutchison, D (2018). Game theory for multi-access edge computing: survey, use cases, and future trends. IEEE Communications Surveys & Tutorials. 21, 260-288.
  13. Galstyan, A, Kolar, S, and Lerman, K . Resource allocation games with changing resource capacities., Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems, 2003, Melbourne, Australia, Array, pp.145-152.
  14. Dai, L, and Sun, X (2012). A unified analysis of IEEE 802.11 DCF networks: stability, throughput, and delay. IEEE Transactions on Mobile Computing. 12, 1558-1572.
  15. Manzoor, S, Yin, Y, Gao, Y, Hei, X, and Cheng, W (2020). A systematic study of IEEE 802.11 DCF network optimization from theory to testbed. IEEE Access. 8, 154114-154132.
  16. Lin, CH, Tsai, YC, Hwang, WS, and Cheng, MH. A collision rate-based backoff algorithm for wireless home area networks.
  17. Dappuri, B, and Venkatesh, TG (2018). Design and performance analysis of multichannel MAC protocol for cognitive WLAN. IEEE Transactions on Vehicular Technology. 67, 5317-5330.
  18. Murad, M, and Eltawil, AM (2020). Performance analysis and enhancements for in-band full-duplex wireless local area networks. IEEE Access. 8, 111636-111652.

Jaesung Park received his B.S. and M.S. degrees in electronic engineering, and his Ph.D. in Electrical and Electronic Engineering from Yonsei University, Seoul, Korea in 1995, 1997, and 2001, respectively. From 2001 to 2002, he worked at a research faculty at the Department of Computer Science and Engineering of the University of Minnesota at Twin Cities, under a scholarship provided by LG Electronics Korea, where he worked as a senior research engineer from 2002 to 2005. He was an associate professor at the University of Suwon from 2005 to 2019. Currently, he is a professor at the School of Information Convergence in the Kwangwoon University. His current research interests include the design, analysis, and evaluation of communication networks.


Changyong Yoon received his B.S., M.S., and Ph.D. in Electrical and Electronic Engineering from Yonsei University, Seoul, Korea, in 1997, 1999, and 2010, respectively. He was a senior research engineer at LG Electronics Inc. and LG-Nortel, and he developed system software for the DVR and WCDMA from 1999 to 2006. From 2010 to 2012, he was a chief research engineer at LG Display and developed circuit and algorithms for touch systems. Since 2012, he has been a professor with the Department of AI Software Convergence, Suwon Science College, Hwaseong, Korea. His main research interests include intelligent transportation systems, pattern recognition, robot vision, and fuzzy application systems.


June 2021, 21 (2)
Full Text(PDF) Free


Funding Information
  • CrossMark
  • Science Central