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.

2.1 Minority Game

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

2.2 WLAN MAC

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 θ, 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 2^2η strategy tables. Among the possible strategy tables, a station randomly selects n strategy tables to configure its set of strategy tables Ω_i = {S_i,1, . . ., S_i,j, . . ., S_i,n} to use the packet transmission game, where S_i,j is the j-th strategy table that station i maintains. Each strategy table S_i,j is composed of 2^η elements and each element in S_i,j is composed of an instance of a η game result s_i,j,k and a binary decision variable a_i,j,k. When the η game results are k and a_i,j,k = 1, it indicates that a station should send a packet at the first packet transmission opportunity. In contrast, a_i,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 S_i,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 S_i,j^* that matches the most recent game history ϕ_i(t) as s_i,j^*,ϕi(t). Then, the action that station i takes becomes the binary decision variable a_i,j^*,ϕi(t) which is associated with s_i,j^*,ϕi(t).

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.

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.

Symbols used in this paper.