Intelligent Automation & Soft Computing DOI:10.32604/iasc.2020.013637
Article

Research on Network Resource Optimal Allocation Algorithm Based on Game Theory

Xiaojuan Yuan1,2,*

1Harbin Institute of Technology, Harbin, Heilongjiang, 150001, China
2Guilin Tourism University, Guilin, Guangxi, 541004, China
*Corresponding Author: Xiaojuan Yuan. Email: xiaojuanyhit@yeah.net
Received: 14 August 2020; Accepted: 28 September 2020

Abstract: This paper briefly introduced the structure of heterogeneous cellular network and two algorithms which are used for optimizing the network resource allocation scheme: dynamic game algorithm based on spectrum allocation and the game allocation algorithm based on power allocation and alliance. After that, the two algorithms were simulated in MATLAB software and compared with another power iterative allocation algorithm based on non-cooperative game. The results showed that the system energy efficiency of the three algorithms decreased with the increase of the number of small base stations in the network; with the increase of the number of users in the network, the system energy efficiency of the three algorithms increased; under the same number of small base stations or users, the system energy efficiency of the allocation scheme based on the power allocation and alliance was the highest, followed by the power iterative allocation algorithm and the spectrum allocation based game algorithm; the allocation scheme based on power allocation and alliance could provide users with more satisfactory and fair services.

Keywords: Game theory; heterogeneous cellular network; power iteration; alliance

1  Introduction

The development of communication technology makes the wireless network carry more and more data, and the development of communication equipment manufacturing industry makes the function of mobile terminal more and more abundant and the cost lower and lower; the former enables wireless network to bear more function applications, and the latter is conducive to the popularization of wireless Internet and mobile terminal [1]. The popularity of wireless Internet and intelligent mobile terminals greatly facilitates people’s life. But the high penetration rate makes more and more mobile users in the wireless network access, and too many users will directly lead to the decline of the service quality of the wireless network due to the limited channel resources [2]. The methods for solving the above problems can be considered from two aspects: one is to improve the service quality by improving the resource quantity of the wireless network itself (for example, changing 3G to 4G, changing 4G to 5G, or adjusting the structure of transmission network, such as cellular heterogeneous network, etc.), and the other is to allocate the wireless network resources reasonably by optimizing the allocation algorithm [3]. The related researches are as follows. Wu et al. [4] used Stackelberg game for the first layer which was composed of macro base station (MBS) and non-cooperative game for the second layer which was composed of small base station (SBS) in heterogeneous cellular network to realize the optimization of network resource allocation, and the experimental results showed that the method could improve the signal-to-noise ratio and energy utilization ratio better than the traditional method. In the heterogeneous sensor network, Zhao et al. [5] used interference alignment technology (IA) and power allocation algorithm from game theory, which not only eliminated the interference between the primary node and secondary node, but also maximized the energy efficiency of the secondary node, and verified the effectiveness of the method through simulation. This paper briefly introduced the structure of heterogeneous cellular network and two algorithms which are used for optimizing the network resource allocation scheme: dynamic game algorithm based on spectrum allocation and game allocation algorithm based on power allocation and alliance. Then the two algorithms were simulated in MATLAB software and compared with the power iterative allocation algorithm based on non-cooperative game.

2  Heterogeneous Cellular Network

The principle of cellular network can be simply summarized as user sending information, base station receiving and forwarding information, another base station receiving and sending information, and another user receiving information, which ensures the long-distance transmission of radio waves. Each base station has a certain coverage. When the information of users exceeds the coverage, it will “relay” through another base station. These base stations together constitute the wireless signal transmission network, i.e., cellular network [6].

Although the cellular network which is composed of base stations [7] can improve the coverage of wireless signals, with the popularization of mobile terminals and the increasing demand of users for network services, the defects of the simple cellular network structure gradually become obvious, mainly including difficult guarantee of service quality at the edge of station coverage, difficult location and maintenance of base station and difficult indoor coverage. To some extent, the above problems can be solved by increasing the number of base stations, but as mentioned above, the macro base stations with a large coverage are large, which are difficult to locate, and the cost of construction and maintenance is high. Heterogeneous cellular network is proposed to solve the above problems, and its basic structure is shown in Fig. 1. Heterogeneous cellular network is obtained after hierarchically processing the original cellular network, i.e., adding SBS [8]. Fig. 1 is a simple model of double-layer heterogeneous cellular network. There are several SBS within the coverage of MBS, and there are several users in the coverage of SBS. Compared with MBS, SBS has smaller coverage, but less energy consumption, lower construction and maintenance costs, and lower requirements for site setting. When the heterogeneous cellular network work, MBS transmits information to SBS, and then SBS transmits information to users.

Figure 1: The cellular structure

3  Network Resource Allocation Method Based on Game Theory

3.1 Spectrum Resources Optimization Algorithm Based on Dynamic Game

For the convenience of research and explanation, the double-layer heterogeneous cellular network in Fig. 1 is adopted, including 1 MBS and N SBS. The total bandwidth of the network is shared between MBS and SBS by orthogonal frequency division multiplexing [9]. The game theory based spectrum resources optimization algorithm is to allocate spectrum bandwidth [10] by using the idea of game theory, so as to improve the utilization rate of spectrum and the energy efficiency of network. In the optimization algorithm, users in the heterogeneous cellular network can choose MBS and SBS freely. The problems to be solved by the algorithm can be described as follows:

where stands for the total energy efficiency of the system, is the bandwidth proportion of MBS, is the total network bandwidth, and are the spectrum unit price of MBS and SBS respectively, i.e., the energy efficiency per unit spectrum resource, and stand for the number of users accessing MBS and SBS respectively, and stand for the emission power of MBS and SBS respectively, and are average channel gains of MBS and SBS respectively [11], and is the Gaussian white noise variance [12]. In the algorithm, although the network users can choose to access MBS or SBS, they cannot control it autonomously; therefore, it is random access which can be affected by factors such as the capacity and distance of base station. The algorithm dynamically adjusts the spectrum allocation according to the user access status, which is the dynamic evolutionary game [13]. By the second derivative of Eq. (1) and based on the value range of , it is seen that there is optimal that makes the system energy efficiency the highest, and steps of the algorithm are:

① Initialization is performed, and random spectrum is allocated to MBS and SBS;

② The number of users accessing MBS and SBS is collected, and the power and average channel gain of MBS and SBS at the same moment are measured;

③ Optimal is calculated, and the calculation formula is:

④ Step ② and ③ repeat at different moments to get the real-time optimal , which can realize the dynamic game of spectrum resource allocation.

3.2 Game Algorithm Based on Power Distribution and Coalition Formation

The double-layer heterogeneous cellular network in Fig. 1 is also adopted. As the spectrum adopted by the MBS and SBS is orthogonal to each other, there is no interference. It is assumed that there are M users in the network, and there is no interference between the users accessing the same SBS. SBS in the network can be independent from each other, and they compete and game to reach the optimal balance. SBS can also cooperate with each other through time division multiplexing, the cooperated SBS form a alliance, SBS in the same alliance do not interfere each other, but compete each other to realize the optimal balance. The calculation formula of energy efficiency which is used for measuring the network performance in the algorithm is as follows:

where is the system energy efficiency of network, and are total transmission rate and total energy consumption respectively, and are the number of subchannels and no. of subchannels respectively, and are the number of subchannels and no. of SBS, stands for the weight of the -th SBS in the -th subchannel, stands for the proportion of the transmitting time of the -th SBS in its alliance, stands for the subchannel bandwidth of SBS, stands for the transmitting power of the -th SBS in the -th subchannel, stands for the channel gain of the -th subchannel between the -th SBS and user m accessing to the SBS, stands for the distribution of the alliance structure in the network or the set of alliance, stands for the alliance where the -th SBS locates, stands for any alliance except in , stands for the basic power consumption of SBS, and is the drain efficiency of the power amplifier.

The algorithm adjusts the transmission rate by adjusting the transmission power of SBS in different subchannels, so as to adjust the system energy efficiency of the network. The ultimate goal is to maximize the system energy efficiency. The basic principle of the power allocation and alliance based game algorithm is as follows. Firstly, different SBS in the network forms an alliance. Then, under the alliance structure, the optimal power allocation is solved by non-cooperative game [14], and the alliance structure of SBS is adjusted, i.e., adding a SBS into another alliance. The optimal power allocation is solved based on the non-cooperative game under the new alliance structure. The energy efficiency under the optimal power allocation before and after the change of alliance is compared. If there is any increase, the structure after the alliance change is kept; otherwise, the alliance is selected again and added, and the above steps repeat until the SBS cannot change. Finally, the alliance structure in the allocation strategy is the optimal structure obtained through constant game, and power allocation is the optimal power allocation under the alliance structure. Specific steps of the algorithm are as follows.

① The alliance structure of SBS in the network is initialized. Each SBS is regarded as an alliance.

② After selecting a SBS, n, it is randomly added to an alliance. Then of all SBS in the network is calculated using the following formula:

where is the number of all SBS in the alliance where n is located. Then, the transmission rate and energy consumption are listed according to Eq. (3).

③ Then, the optimal power allocation under the alliance structure is solved by non-cooperative game iteration. Firstly, the lower bound power satisfying the user rate is calculated, and the formula is as follows:

where is the lower bound power, is the water filling value of user m accessing SBS n [15], stands for the use of subchannel k by user m accessing SBS n, 1 for use and 0 for no use, and is the minimum rate requirement to ensure the quality of service.

④ is initialized, i.e.,

Power is iterated according to the iterative formula:

where is a new factor introduced and and are SBS transmitting power before and after iteration.

⑤ Step ④ repeats until , where is a value close to 0, or it iterates to the maximum number of times, and then (power allocation strategy) and are output.

⑥ The system energy efficiency is calculated according to obtained in step ④ and ⑤ and compared with the previous system energy efficiency. If there is an increase, SBS n will be transferred to the alliance; otherwise another alliance will be selected.

⑦ Step ②, ③, ④, ⑤ and ⑥ repeat for all SBS in the network until SBS is no longer transferred. The power allocation strategy and alliance structure are output after the alliance structure is stable.

4  Simulation Experiment

4.1 Experimental Environment

In this study, the above two wireless network resource allocation algorithms based on game theory were simulated by MATLAB software [16]. The simulation experiment was carried out in the server of a laboratory. The configuration of the server was Windows 7 operating system, Core i7 processor and 16 G memory.

4.2 Experimental Parameters

The simulated heterogeneous cellular network which was used for the two network resource allocation algorithms was similar to Fig. 1 in structure, i.e., having one MBS and N SBS. The basic parameters in the network are shown in Tab. 1.

Table 1: Basic parameters for simulation experiment

The experimental items which were used for testing the effect of network resource allocation algorithm are as follows.

(1) The number of users participating in the heterogeneous cellular network was set as 50, and the number of SBS in the heterogeneous network was set as 8 ~ 15. The system energy efficiency under different number of SBS was tested.

(2) The number of SBS in the heterogeneous network was set as 10, and the number of users participating in the network was set as 20, 30, 40, 50 and 60 respectively. The system energy efficiency under different number of users participating in the network was tested.

(3) The number of SBS in the network was set as 15, and the number of users participating in the network was set as 15, 25, 35, 45 and 55 respectively. Moreover the satisfactory throughput of each user was set, i.e., the satisfactory minimum transmission rate was 2.5 Mbps. The satisfaction of users and the fairness of the network system under different number of users was tested [17]. The calculation formula is:

where is the average satisfaction of users on the network system, is the fairness of providing service by network system, represents the total number of users and the set of users, is the no. of one of the users, and is user satisfaction (if the transmission rate of users is smaller than the set minimum transmission rate, its value is set as 0; otherwise, its value is set as 1).

The above experiments repeated for 5 times under every setting condition, and the average values were taken as the final results. Moreover, in order to further verify the optimization effect of the power allocation and alliance based game algorithm on network resource allocation, in addition to comparing the above two algorithms, they were also compared with an allocation algorithm based on non-cooperative game, i.e., the algorithm described in Section 3.2 which did carry out SBS alliance, but only carried out power iterative optimization.

4.3 Experimental Results

Different number of SBS were set in the heterogeneous cellular network, and then three algorithms were used for allocating resources. The system energy efficiency after allocation is shown in Fig. 2. It was seen from Fig. 2 that the system energy efficiency under the allocation schemes obtained by the three algorithms reduced with the increase of the number of SBS in the cellular network. Moreover, the comparison of the system energy efficiency under the allocation schemes obtained by the three algorithms under the same number of SBS showed that the system energy efficiency of the power allocation and alliance based game allocation algorithm was the highest, followed by the non-cooperative game based power allocation algorithm and the spectrum allocation based dynamic game algorithm.

Figure 2: Relationship between system energy efficiency and SBS quantity under the allocation schemes of the three algorithms

Different number of users was set in the heterogeneous cellular network, and the number of SBS was set as 10. Then network resources were allocated using the three algorithms, and the system energy efficiency under the final allocation schemes is shown in Fig. 3. It was seen from Fig. 3 that the more users participate in the heterogeneous network, the higher the system energy efficiency, but the increase amplitude of system energy efficiency reduced with the increase of the number of users. The total energy consumption of the whole network was unchanged because of the fixed number of SBS in the network even when the base station worked with the full power, but the increase of users accessing to the network meant the increase of transmission data, i.e., the increase of total network rate, which led to the increase of system energy efficiency. When the number of users increased to some value, users multiplexed subchannels, which caused interference, affected the transmission rate, and finally slowed down the increase of the energy efficiency. The comparison of the system energy efficiency under the same number of users showed that the system energy efficiency of the game allocation algorithm based on power allocation and alliance was the highest, followed by the power allocation algorithm based on non-cooperative game and the dynamic game algorithm based on spectrum allocation.

Figure 3: Relationship between system energy efficiency and number of users under the allocation schemes of the three algorithms

In the heterogeneous network, the number of SBS was set as 15, and different number of users were set. Then network resources were allocated by the three algorithms. The average satisfaction and fairness index of transmission services provided by the heterogeneous network under the final allocation scheme are shown in Fig. 4. The average satisfaction reflected the satisfaction of users with the transmission services provided by the network system, i.e., whether the transmission rate could satisfy users, and the value was between 0 and 1 (the closer it was to 1, the more satisfied the users in the network was). The fairness index reflected the fairness of users in the network receiving SBS services, and the value was also between 0 and 1 (the closer it was to 1, the more fair the services were). It was seen from Fig. 4 that no matter which algorithm was used, the satisfaction and fairness index of the allocation schemes decreased with the increase of the number of users in the network. When the number of users was 15, the satisfaction and fairness index of the three allocation schemes were all 1. The reason for the above result was that the number of users was consistent with the number of SBS and the service was one-to-one. Moreover, under the same number of users, the satisfaction and fairness of the power allocation and alliance based game allocation algorithm were the highest, followed by the non-cooperative game based power allocation algorithm and the spectrum allocation based dynamic game algorithm.

Figure 4: Satisfaction and fairness of network service delivery under the allocation schemes of the three algorithms

5  Conclusion

This paper briefly introduced the structure of heterogeneous cellular network and two algorithms which were used for optimizing the network resource allocation scheme: the spectrum allocation based dynamic game algorithm and the power allocation and alliance based game allocation algorithm. Then the two algorithms were simulated in MATLAB software and compared with a non-cooperative game based power iterative allocation algorithm. The results are as follows: (1) under the fixed number of users, the system energy efficiency of the three algorithms decreased with the increase of the number of SBS in the network; under the same number of SBS, the system energy efficiency of the power allocation and alliance based game allocation algorithm was the highest, followed by the non-cooperative game based power allocation algorithm and the spectrum allocation based dynamic game algorithm; (2) under the fixed number of SBS, the system energy efficiency of the three algorithms increased with the increase of the number of users in the network, but the increasing amplitude decreased gradually, and the satisfaction and fairness decreased with the increase of the number of users; under the same number of users, the system energy efficiency, satisfaction and fairness of the power allocation and alliance based game distribution algorithm were the highest, followed by the non-cooperative game based power allocation algorithm and the spectrum allocation based dynamic game algorithm.

Funding Statement: The author received no specific funding for this study.

Conflicts of Interest: The author declares that she has no conflicts of interest to report regarding the present study.

References

 1.  K. Khawam, S. Lahoud, M. Ibrahim, M. Yassin, S. Martin et al. (2016). , “Radio access technology selection in heterogeneous networks,” Physical Communication, vol. 18, pp. 125–139. [Google Scholar]

 2.  H. Khanmirza and N. Yazdani. (2016). “Game of energy consumption balancing in heterogeneous sensor networks,” Wireless Communications and Mobile Computing, vol. 16, no. 12, pp. 1457–1477. [Google Scholar]

 3.  T. M. Ho, N. H. Tran, L. B. Le, S. Walid, K. S. M. Ahsan et al. (2016). , “Coordinated resource partitioning and data offloading in wireless heterogeneous networks,” IEEE Communications Letters, vol. 20, no. 5, pp. 974–977. [Google Scholar]

 4.  Y. L. Wu, X. Li, H. L. Zhang and K. Wang. (2016). “Resource allocation scheme based on game theory in heterogeneous networks,” Journal of China Universities of Posts & Telecommunications, vol. 23, no. 3, pp. 57–88. [Google Scholar]

 5.  F. Zhao, W. Wang, H. Chen and Q. Zhang. (2016). “Interference alignment and game-theoretic power allocation in MIMO Heterogeneous Sensor Networks communications,” Signal Processing, vol. 126, pp. 173–179. [Google Scholar]

 6.  T. Chen, Q. Ling and G. B. Giannakis. (2017). “An online convex optimization approach to proactive network resource allocation,” IEEE Transactions on Signal Processing, vol. 65, no. 24, pp. 6350–6364. [Google Scholar]

 7.  Y. Yan, Y. Z. Li, C. Y. Xing and J. Y. Wang. , 2015. , “Spectrum allocation in two-tier heterogeneous network: A bilateral negotiation framework,” IEEE Vehicular Technology Conf., vol. 7146099. [Google Scholar]

 8.  S. L. Sun, N. Chen, T. T. Ran, J. S. Xiao and T. Tian. , 2016. , “A Stackelberg game spectrum sharing scheme in cognitive radio-based heterogeneous wireless sensor networks,” Signal Processing, vol. 126. [Google Scholar]

 9.  M. Z. Chen, W. Saad and C. C. Yin. (2017). “Echo state networks for self-organizing resource allocation in LTE-U with uplink–downlink decoupling,” IEEE Transactions on Wireless Communications, vol. 16, no. 1, pp. 3–16. [Google Scholar]

10. A. Rahmati, A. Sadeghi and V. Shahmansouri. (2016). “Price-based resource allocation for full duplex self-backhauled small cell networks,” Computer Communications, pp. 5709–5714. [Google Scholar]

11. B. N. Zhuang, D. N. Guo and M. L. Honig. (2016). “Energy-efficient cell activation, user association, and spectrum allocation in heterogeneous networks,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 4, pp. 823–831. [Google Scholar]

12. P. Yuan, Y. Xiao, G. A. Bi and L. R. Zhang. (2017). “Towards cooperation by carrier aggregation in heterogeneous networks: A hierarchical game approach,” IEEE Transactions on Vehicular Technology, vol. 66, no. 2, pp. 1670–1683. [Google Scholar]

13. C. Gao, Y. Li, Y. Zhao and S. Chen. (2017). “A two-level game theory approach for joint relay selection and resource allocation in network coding assisted D2D communications,” IEEE Transactions on Mobile Computing, vol. 16, no. 10, pp. 2697–2711. [Google Scholar]

14. A. Kermani, F. Fatemi, A. Aliahmadi and F. Barzinpour. (2017). “A novel game theoretic approach for modeling competitive information diffusion in social networks with heterogeneous nodes,” Physica A: Statistical Mechanics & its Applications, vol. 466, pp. 570–582. [Google Scholar]

15. G. Wang and T. Liu. (2018). “Resource allocation for M2M-enabled cellular network using Nash bargaining game theory,” Peer-to-Peer Networking and Applications, vol. 11, no. 1, pp. 110–123. [Google Scholar]

16. O. Semiari, W. Saad, M. Bennis and B. Maham. (2018). “Caching meets millimeter wave communications for enhanced mobility management in 5G networks,” IEEE Transactions on Wireless Communications, vol. 17, no. 2, pp. 779–793. [Google Scholar]

17. G. Wang and T. Liu. (2018). “Resource allocation for M2M-enabled cellular network using Nash bargaining game theory,” Peer-to-Peer Networking and Applications, vol. 11, no. 1, pp. 110–123. [Google Scholar]

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.