Impact of Strategy Optimization on Game-Based CR-MAC Protocol Performance

Impact of Strategy Optimization on Game-Based CR-MAC Protocol Performance

Manisha A. Dudhedia* Yerram Ravinder

Department of Electronics and Telecommunication, Sinhagad College of Engineering, S. P. Pune University, Pune 411041, India

Department of Electronics and Telecommunication, Marathwada Mitra Mandal’s College of Engineering, S. P. Pune University, Pune 411052, India

Department of Electronics and Telecommunication, Pune Institute of Computer Technology, Pune 411043, India

Corresponding Author Email: 
manisha.agnani@gmail.com
Page: 
473-478
|
DOI: 
https://doi.org/10.18280/isi.270314
Received: 
21 November 2021
|
Revised: 
25 March 2022
|
Accepted: 
10 April 2022
|
Available online: 
30 June 2022
| Citation

© 2022 IIETA. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).

OPEN ACCESS

Abstract: 

Application of Game Theory in various fields is a new approach to optimize the performance. Many researchers are applying a game theory to wireless network to optimize the network performance. Optimizing the network performance is a critical challenge, especially in wireless networks as there is always a trade-off between energy efficiency and QoS. In this paper, Game based MAC protocol is optimized. Game-based MAC where a node three strategies: small, medium, and large are proposed. However, the number of strategies and interval of strategy are not optimized. Optimizing the number of strategies and interval will help to reduce the delay of the network. The proposed solution has been tested with numerical analysis and supports intuitions. With numerical analysis, it is claimed that game-based MAC reduces the delay and thus boosts the overall performance of the network.

Keywords: 

game theory, self-configuring, wireless networks, contention window, cognitive radio based wireless network

1. Introduction

In wireless communication the networks are mainly categorised as distributed and centralised networks as shown in Figure 1. Both networks have their own merits and demerits. However, decentralised networks are gaining popularity due to its flexibility in implementation. On the other hand, centralised networks have better control over the network resources with full optimization. A cognitive radio based wireless network (CRWN) is an example of distributed network having self-configuring, multi-hop characteristics with no central authority. Therefore, all aspects of CRWN configuration and operation should be fully distributed. According to the research and study, game theory is an appropriate tool for analyzing CRWN configuration. The interaction between the nodes in CRWN is performed with the help of non-cooperative game theory which offers range of tools [1].

Dudhedia and Ravinder [2] have anticipated the use of game theory in the area of communications and networking by means of game formulations at MAC layer.

Figure 1. Centralised versus distributed network

Game Theory (GT) provides solutions in scenarios where different nodes are competing for spectrum, thus improving the network optimization. GT is a modern tool which is applied to solve many optimization problems in wireless networks. Games are categorized as incomplete and complete information.

Co-operative as well as non-cooperative games are two categories belonging to both incomplete and complete information games. Non-cooperative games do not allow players to make commitments to co - ordinate with their strategies. A non-cooperative game explores the key for choosing the best strategic plan for a player to face an opponent who seems to have his / her own tactics. Once players find something that is in their very own finest interests, co - operative games do often emerge out as non-cooperative games [1].

On the other hand, a co-operative game, is one in which groups of players (known as "Coalitions") are forced to cooperate in order to maximize one’s yields (payoffs). As a result, instead of specific performances, a co - operative game is indeed a contest among alliances of players. Besides that, a cooperative game disparity framework for coalitions to imposed coordinated behavior on members of the coalition. To form a coalition in such a specified cooperative game, GT explores both relative levels of various coalitions and the strength of the various players in each coalition.

Application of it brings about benefits such as; solutions for analysis of distributed systems, design cross layer protocol. However, there are some important assumptions, required to be kept in mind while applying the game theory to a CRWN: a practical state of affair, the selection of utility functions, the mechanism design, and the mapping variables in the game.

Nodes in CRWNs are pretty dynamic and dispensed in nature. Game concept study indicate a natural assurance to apprehend the interplay among those nodes. Asynchronous type of MAC protocol of one and more than one channels is considered [3]. This takes care of the distribution of spectrum amongst secondary users (SU) in dynamic manner. The proposed MAC evaluates the saturation throughput. Though, this method can also additionally tender optimization locally but here global optimization is missing. Htike and Hong [4] proposed a MAC protocol for CRWN which is not only energy efficient but also within a game theoretical structure. This structure was categorized as ‘non cooperative medium access game’ and ‘multiple access sub-games’. A non cooperative game has been introduced in ref. [5]. A GT framework is proposed in case of a different completely distributed ‘Carrier Sense Multiple Access (CSMA)’ algorithm where global optimization was attained. The game permits the associations for evaluating its transient throughput without message passing. This approach is completely exclusive technique to resolve the dilemma. Even so, it cannot be applied to ‘multi band radio’ or CRWN. In addition to this, the lower restriction of overall performance was discounted. Specific games are tested and their demanding situations investigated with a few upcoming research guidelines and review of games specifically CSMA is carried out. Nonetheless, it is applicable to a single channel radio [6].

Bianchi [7] offered an easy analytical representation to calculate the saturation throughput performance of the 802.11 Distributed Coordination Function. IEEE 802.11 has been executed [8], here the authors have evaluated the throughput taking into consideration non-saturated traffic conditions. The effect of transmission channel and capture effect have also been taken into account. The authors [9] have calculated the possibility of cohabitants among PUs and SUs. Their interplay is modelled with the aid of using Markov Chains. The allocation of resources for dynamic spectrum is proposed with the help of cross layer layout. With the help of this approach throughput of the SUs was improved considerably. High throughput is achieved in case of Cognitive Radio (CR) with the help of a protocol namely Distributed MAC (DMAC). This protocol selects highest quality range of support nodes in order to reduce the problem of hidden nodes for both the users (PUs and SUs) [10]. Patrick et al. with the help of concepts and applications of game theory [11] addressed single-hop ad hoc networks. An exciting study in which authors have proven that selfish nodes inside a network will be of help is presented here. Selfish nodes force the nodes in the network to perform at an efficient Nash Equilibrium (NE). Global optimum is assured if NE is achieved. Also, authors have confirmed the quasi-optimal answer for multi-adhoc set-up. The author [12] discussed about CRWN; yet selfish behaviour and fairness issues were left unexamined. Likewise, in refs. [13, 14] Cognitive Radio (CR) based performance was ruled out.

The center of attention of study is to apply game theory techniques to enhance the performance of a network at the MAC layer [2]. As shown in ref. [2], all nodes will convert MAC problem into games and play with three basic strategies: small, medium, and large. These strategies are based on different contention window size such as small (0-127), medium (0-512), large (0-1024). With these different strategy authors [2] were able to get the optimized network performance. However, this work also posed questions on the number of strategies required and the ideal interval of a strategy. Based on literature survey and known limitations of current effort, the aim of this work is to minimize the delay in Game based MAC. In this paper, optimization of strategies has been introduced to improve the performance of a network. This paper is prepared in 3 segments. Section 1 present the introduction along with the literature survey. Section 2 provides game model and the evaluation of the results. The belief is offered in segment 3 in the form of conclusion.

2. Game Theory Model

GT is a field of mathematics that assists teams in analyzing strategic thinking in crisis situations. Such circumstances occur once; two or more players with opposing goals access the system or start sharing the same assets. A game might be played by two or more people. GT offers a systematic procedure for choosing the best response / move / strategy for a player to confront an adversary who has a strategic plan.

In a game there are three components namely:

(1) Players;

(2) Strategies of each player in the game;

(3) Payoffs.

A large (n players and multi-stage) game consists of the four aspects mentioned below:

(1) Node: A node inside the game is indeed a role where one of the players must decide.

(2) Branches: It comprises the player's various approaches, and therefore correlates to possible options.

(3) Vectors: It constitutes the payoffs of each player, with the payoffs mentioned in the order of players.

(4) Information Sets: If two or more nodes are connected by a dashed line, it represents the player’s decision is somehow unaware which node he or she is at. Whenever this happens, the game is referred as an incomplete information game. But on the other hand, every other judgment has its own data set, the game is referred to as a game of adequate knowledge. Most players in this game are aware of the fact of prior actions this is referred as game with perfect information.

There is one more important concept of sub game in tree games. A game with any set of nodes and branches descending uniquely from one node is defined as a sub-game.

Figure 2. Applications of GT in Computer Science

Figure 3. Few research areas in wired and wireless networking

Game theory is applied in various disciplines. Figure 2 shows the application of GT especially in Computer Science, like Distributed computers algorithms, networking, Formulation theory to name a few. As shown in Figure 3 there are many research areas in networking like power control, adaptive Interreference avoidance, network formulation, node migration, routing, flow control, congestion control and so on. A game is formulated for conflict situations when more than one node or terminal share the same resources.

An exhaustive literature survey is carried out in order to summarize the work done by various research scholars in the field of game theory (GT). The survey reveals a variety of GT models / methodology tried out for optimization of resource sharing approaches in CR. The goal of this work is to optimize the system performance at network level using GT at the MAC layer. Based on the literature survey, and limitation of the existing work [2], motivated to propose this work on game theoretical modeling of CRWN. This network proposes various challenges however; the concentration is on MAC layer.

As shown in Figure 4, GT can be used to simulate an ad-hoc network at the physical, link, as well as network layers. There are implementations at the transport and higher layers, but this conversation is limited to the network topology. In these instances, a topic of interest is to provide the right incentives to discover global resource optimization while discouraging destructive / selfish behavior. Selflessness is usually detrimental to overall system performance; case studies indicate a node raising the power without respect for the interference provokes its own neighbors (layer 1), a node retransmitting a frame in the event of a collision without proceeding via a back off phase (layer 2), or a node refusing to forward packet data to its neighbors (layer 3) [7].

As a result, the goal of the study is to identify system performance and operational efficiency GT only at MAC layer.

'MAC' game ought to have the three dimensions as listed below:

(1) Individuality: The alternative has to be one. It is done to prevent uncertainty about which alternative every player must select.

(2) Equity: An alternative must contribute in an equal distribution with network throughput.

(3) Pareto efficient: A remedy ought to be Pareto effective in terms of assigning throughput.

Figure 4. Classification of Games as per the protocol layers

The other most essential part at this point is to get to desired outcome of a 'MAC' game.

To contribute to solving the ‘MAC' game, a one-of-a-kind effective NE, that maximizes equally locally and globally payoff is necessary. Though, achieving a distinctive effective NE involves numerous key issues [15].

A GT modeling of CRWN at MAC layer has been formulated based on a systematic review and as limitations of previous work.

MAC game is modelled as stochastic [2]. The game begins at the arrival of a data packet in the buffer of the node for transmission and this game ends once it is successfully transmitted or even if that packet is dropped. There are numerous time slots in this game, this slot is also called as a game slot. If the transmission of information packet is unsuccessful in that case it is permitted a preset restriction set because of the maximal retry restriction. Hence, the game turns into a finitely repeated game. Due to the memory less nature of BEB the same game is performed once more and as a result this game can be categorized as infinitely repeated. The game based –MAC as proven in [2] is modelled as a repeated non cooperative game. The nodes in the network can alternate their techniques through adjustment of their CW size and attempts to gain its optimum solution. Hence, estimation of the wide variety of lively nodes in well timed way is the important task for modelling the proposed MAC game.

The nodes have essentially 3 strategies namely low, medium and high [2]. The node in the network has a unique value of CW. In the network, collisions occur whilst nodes select equal strategy with equal CW value. Pi and $\bar{P}_{i}$ are described as the payoff of player 1 and 2 discretely. Correspondingly, Ps and $\bar{P}_{s}$ shows the payoff of successful in transmission. Last of all, Pf and $\bar{P}_{f}$ indicate the transmission failure. From the above-mentioned presumptions, it is obvious that, Pf<PS.

The game based can be presented as shown in Table 1.

Table 1. Players’ strategy

 

Player 2 (all other n nodes)

Player 1 (Node i)

Low

Medium

High

Low

$({{P}_{f}},{{\bar{P}}_{f}})$

$({{P}_{s}},{{\bar{P}}_{s}})$

$({{P}_{s}},{{\bar{P}}_{s}})$

Medium

$({{P}_{s}},{{\bar{P}}_{s}})$

$({{P}_{f}},{{\bar{P}}_{f}})$

$({{P}_{s}},{{\bar{P}}_{s}})$

High

$({{P}_{s}},{{\bar{P}}_{s}})$

$({{P}_{s}},{{\bar{P}}_{s}})$

$({{P}_{f}},{{\bar{P}}_{f}})$

Analysis of Delay: This is a critical metric of Quality of service (QoS). Number of varieties of components that have an important position in calculation of delay are considered. A fundamental unit considered in the delay evaluation is, time dimension. It is the difference in the time the data packet is generated and the time it is received.

Let MD represent the medium access delay. Average value of MD represented by E[MD]. As revealed in refs. [4-9], E[MD] is represented by:

$E[M D]=E\left[N_{\text {coll }}\right]\left(E\left[B_{\text {del }}\right]+T_{C}+T_{O}\right)+\left(E\left[B_{\text {del }}\right]\right.\left.+T_{S}\right)$             (1)

here, mean of number of collisions is E[Ncoll] of a frame before it is successfully received. The mean back off delay is given as E[Bdel] and TO represents the waiting time of a node before sensing the channel again. E[Bdel] is represented in Eq. (2):

$E\left[B_{\text {del }}\right]=E\left[X_{a v g}\right]+E\left[N_{F r}\right]\left(p_{s} T_{S}+\left(1-p_{s}\right) T_{c}\right)$                (2)

where, E[Xavg] represents the mean back off and E[NFr] indicates the average number of times that a node freezes its counter before it reaches state 0. In case of BEB, E[Xavg] is given by:

$E\left[N_{\text {coll }}\right]=\frac{1}{p_{s}}-1$                   (3)

In BEB, E[Xavg] and E[NFr] are given by:

$E\left[X_{a v g}\right]=\frac{C W_{0}}{2}\left[2\left(1-p_{c}\right) \times \frac{1-\left(2 p_{c}\right)^{m+1}}{1-2 p_{c}}\right]+\frac{C W_{0}}{2} \times p_{c}^{m+1}\left[2^{m+1}+\frac{2^{m}}{1-p_{c}}\right]-\frac{1}{2\left(1-p_{c}\right)}$              (4)

$E\left[N_{F r}\right]=\frac{E\left[X_{a v g}\right]}{\max (E[\alpha], 1)}-1$                  (5)

where, E[α] indicates average number of sequential idle slots.

$T_{O}=$ InterframeSpace+ ACK_timout                (6)

where, Tindicates the access method.

3. Results and Discussion

In this section, implementation of system model is carried out in MATLAB [15]. The network density from high to low has been depicted by varying the number of nodes surrounded by source node. Nodes 5 and 25 are indicating low and high density of network, respectively. Here, three strategies have been considered as defined in ref. [2], small, medium and large. Numerical results are obtained using the system model presented in section 2. All required parameters are set as per [2]. In this section impact analysis, contention window versus normalized throughput is considered with the three different strategies. Based on numerical analysis, results are depicted in Figure 2-4.

Figure 5 depicts the alteration in normalized throughput with small size of contention window. Here, small strategy means CW=[0-127]. As shown in the Figure 5 there is high throughput in the range of 20-25 slots depending on the number of nodes in the network. The value of CW is spread across wide range of CW. Before and after optimizing this value of CW the throughput reduces, reason being saturated and unsaturated traffic condition. Figure 6 depicts the variation in normalized throughput when the contention window size is medium (CW=[0-511]). In this case, high throughput is achieved within the range of (20-130) as per the network density. Similarly, Figure 7, shows the effect on normalized throughput when the contention window size is large (CW=[0-1023]). High throughput is achieved within the range of (20-130) as per the number of nodes in the network.

From Figure 5, 6 and 7 it is observed optimized value of contention window interval is with respect to network density. It is seen that the interval as well as number of strategies depends on number of nodes in a network. Therefore, at the designing stage if the approximate number of nodes in the network is known then optimized value of CW for each strategy can be defined. As it is observed from the peak of the normalized throughput comes at different values of the contention window which are summarized in Table 2. From Table 2 it is observed that delay is reduced by reducing the CW interval as per the shown values. These reduced intervals will also help designer in reducing unnecessary energy wastage as well [16, 17]. As these results are based on numerical model, few parameters are assumed as per [2] and simplified conditions (such as avoiding noise, no capturing effect, etc.) thus this approximation might give a chance of error. Hence, keeping an error margin in view range of different strategies with different densities are presented in Tables 2 and 3.

Figure 5. Variation of normalized throughput with small strategy

Figure 6. Variation of normalized throughput with medium strategy

Figure 7. Variation of normalized throughput with large strategy

Table 2. Strategy with respect to the network density

Strategy

5 Nodes

10 Nodes

(BO)

(AO)

(BO)

(AO)

Small

0-127

20-25

0-127

40-60

Medium

0-511

0-511

Large

0-1023

0-1023

Table 3. Strategy with respect to the network density

Strategy

20 Nodes

25 Nodes

(BO)

(AO)

(BO)

(AO)

Small

0-127

100-120

0-127

100-130

Medium

0-511

0-511

Large

0-1023

0-1023

Note: BO - Before Optimization, AO - After Optimization.

Table 4. % Gain in delay and energy efficiency

Nodes

5

10

20

25

5

10

20

25

Strategy

% Gain in Energy Efficiency

 % Gain in Delay

Small

80

56

6

1

80

56

6

1

Medium

95

88

77

75

95

88

77

75

Large

98

94

88

87

98

94

88

87

Similar to Tables 2 & 3, Table 4 represents the percentage gain in delay and energy efficiency. As it is observed, compared to original range of CW size, optimized window size is small. Also, at particular density of nodes, optimized range of CW size remains the same therefore the selection of CW largely relies on the size of the network. The range is presented instead of specific value the reason being there is a possibility of some error margin as well. As shown in Table 3 the percentage gain of energy efficiency and delay is achieved from 1% to 80% in implementation of small strategy. Similarly, 75% to 96% and 87% to 98% gain of energy efficiency and delay are achieved from medium and large strategy, respectively. Also, it is worth to note that increasing more strategies will not add much value to % gain in energy efficiency and delay. So having three strategies for a game is a good option. It is also a good balance between complexity and adaptability.

4. Conclusions

This paper is an extension of ref. [2], in which all nodes will convert MAC problem into games and play with three basic strategies: small, medium, and large. These strategies are based on different contention window size such as small (0-127), medium (0-512) and large (0-1024). With these different strategies it is possible to get the optimized network performance. However, this work also put-up new questions like the number of strategies required, the ideal interval of a strategy etc. So, optimized size of CW for each strategy is obtained. Using these new found interval ranges a node can go to sleep mode during the back-off counting and also reduces the waiting time to access the medium, hence saving in energy and improving delay performance of a network. Results showed that reduced strategy interval can improve the delay by a margin of 1% to 87%.

  References

[1] Felegyhazi, M., Hubaux, J.P. (2006). Game theory in wireless networks: A tutorial. Scientific Production and Competences, 1-15.

[2] Dudhedia, M.A., Ravinder, Y. (2021). Performance analysis of game based MAC protocol for cognitive radio based wireless network. Journal of King Saud University-Computer and Information Sciences. https://doi.org/10.1016/j.jksuci.2020.12.018

[3] Tan, L.T., Le, L.B. (2011). Distributed MAC protocol for cognitive radio networks: Design, analysis, and optimization. IEEE Transactions on Vehicular Technology, 60(8): 3990-4003. https://doi.org/10.1109/TVT.2011.2165325

[4] Htike, Z., Hong, C.S. (2011). Overview of 802.22 WRAN standard and research challenges. OSIA Standards & Technology Review, 24(2): 57-64

[5] Abdulghfoor, O.B., Ismail, M., Nordin, R. (2013). Application of game theory to underlay ad-hoc cognitive radio networks: An overview. In 2013 IEEE International Conference on Space Science and Communication (IconSpace), Melaka, Malaysia, pp. 296-301. https://doi.org/10.1109/IconSpace.2013.6599484

[6] Felegyhazi, M., Cagalj, M., Hubaux, J.P. (2009). Efficient MAC in cognitive radio systems: A game-theoretic approach. IEEE Transactions on Wireless Communications, 8(4): 1984-1995. https://doi.org/10.1109/TWC.2009.080284

[7] Bianchi, G. (2000). Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications, 18(3): 535-547. https://doi.org/10.1109/49.840210

[8] Daneshgaran, F., Laddomada, M., Mesiti, F., Mondin, M. (2008). Unsaturated throughput analysis of IEEE 802.11 in presence of non ideal transmission channel and capture effects. IEEE Transactions on Wireless Communications, 7(4): 1276-1286. https://doi.org/10.1109/TWC.2008.060859

[9] Kwak, B.J., Song, N.O., Miller, L.E. (2005). Performance analysis of exponential backoff. IEEE/ACM Transactions on Networking, 13(2): 343-355. https://doi.org/10.1109/TNET.2005.845533

[10] Rom, R., Sidi, M. (2012). Multiple access protocols: performance and analysis. Springer Science & Business Media.

[11] Ngallemo, H.P., Ajib, W., Elbiaze, H. (2012). Dynamic spectrum access analysis in a multi-user cognitive radio network using Markov chains. In 2012 International Conference on Computing, Networking and Communications (ICNC), Maui, HI, USA, pp. 1113-1117. https://doi.org/10.1109/ICCNC.2012.6167380

[12] Wu, C.M., Lo, C.P. (2017). Distributed MAC protocol for multichannel cognitive radio ad hoc networks based on power control. Computer Communications, 104: 145-158. http://dx.doi.org/10.1016/j.comcom.2016.12.021

[13] Chen, L., Leneutre, J. (2007). Selfishness not always a nightmare: Modeling selfish MAC behaviors in wireless mobile ad hoc networks. 27th International Conference on Distributed Computing Systems (ICDCS '07), Toronto, ON, Canada, pp. 16. https://doi.org/10.1109/ICDCS.2007.138

[14] Jang, H., Yun, S.Y., Shin, J., Yi, Y. (2017). Game theoretic perspective of optimal CSMA. IEEE Transactions on Wireless Communications, 17(1): 194-209. https://doi.org/10.1109/TWC.2017.2764081

[15] Ghazvini, M., Movahedinia, N., Jamshidi, K., Moghim, N. (2012). Game theory applications in CSMA methods. IEEE Communications Surveys & Tutorials, 15(3): 1062-1087. https://doi.org/10.1109/SURV.2012.111412.00167

[16] Math. Graphics. Programming. www.matlab.com, accessed on 14 March 2022.

[17] Doni, A.R., Sasipraba, T. (2020). LSTM-RNN based approach for prediction of dengue cases in India. Ingénierie des Systèmes d’Information, 25(3): 327-335. https://doi.org/10.18280/isi.250306