[BACK]
Intelligent Automation & Soft Computing
DOI:10.32604/iasc.2020.013637		 images
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.

images

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:

images

where images stands for the total energy efficiency of the system, images is the bandwidth proportion of MBS, images is the total network bandwidth, images and images are the spectrum unit price of MBS and SBS respectively, i.e., the energy efficiency per unit spectrum resource, images and images stand for the number of users accessing MBS and SBS respectively, images and images stand for the emission power of MBS and SBS respectively, images and images are average channel gains of MBS and SBS respectively [11], and images 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 images, it is seen that there is optimal images 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 images is calculated, and the calculation formula is:

images

④ Step ② and ③ repeat at different moments to get the real-time optimal images, 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:

images

where images is the system energy efficiency of network, images and images are total transmission rate and total energy consumption respectively, images and images are the number of subchannels and no. of subchannels respectively, images and images are the number of subchannels and no. of SBS, images stands for the weight of the images-th SBS in the images-th subchannel, images stands for the proportion of the transmitting time of the images-th SBS in its alliance, images stands for the subchannel bandwidth of SBS, images stands for the transmitting power of the images-th SBS in the images-th subchannel, images stands for the channel gain of the images-th subchannel between the images-th SBS and user m accessing to the SBS, images stands for the distribution of the alliance structure in the network or the set of alliance, images stands for the alliance where the images-th SBS locates, images stands for any alliance except images in images, images stands for the basic power consumption of SBS, and images 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 images of all SBS in the network is calculated using the following formula:

images

where images 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:

images

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

④ images is initialized, i.e.,

images

Power is iterated according to the iterative formula:

images

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

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

⑥ The system energy efficiency is calculated according to images 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

images

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:

images

where images is the average satisfaction of users on the network system, images is the fairness of providing service by network system, images represents the total number of users and the set of users, images is the no. of one of the users, and images 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.

images

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.

images

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.

images

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