In order to promote the spectral utilization, this article investigates the partially overlapping channel (POC) accessing problem in the wireless network. To reflect the heterogeneous characteristics of users, the optimization goal is set as maximizing the quality of service (QoE), instead of maximizing the throughput or minimizing the interference. The problem is formulated as a QoE maximization game and is then proved to be an ordinal potential game by utilizing the approximate relationship between interference and QoE. The proposed game is proved to have at least one pure Nash equilibrium (NE) and the best pure strategy NE point is an approximate global optimum of maximizing network QoE. A distributed algorithm is designed to reach the NE and it is proved that when the learning parameter is large enough, the algorithm asymptotically maximizes the network QoE. Simulation results verify the effectiveness of utilizing POCs and the proposed method.
1 Introduction
With the rapid development of wireless communications, spectrum becomes more and more scarce and precious. Therefore, high efficient use of spectrum turns to be necessary. Transmission on partially overlapping channels (POCs) was introduced as an effective way to enhance the spectral utilization [1, 2]. It relieves the restriction on transmitting on orthogonal channels only and takes use of every frequency in the band. However, besides co-channel interference, such overlapping using method inevitably results in the interference from adjacent channels and will severely degrade the network performance if channels are not allocated elaborately. Therefore, this article focuses on optimizing the POC accessing problem to enhance the network performance.
While existing researches have investigated some problems about POC, they mainly focused on theoretical investigations [3, 4] or algorithms design [5‐7]. Note that, most algorithms require centralized controllers and information exchange, which may not be feasible when the network scale or the user amount is large. Meanwhile, the optimization object is used to be designed as minimizing interference [8, 9] or maximizing throughput [10, 11] which can not reflect the heterogeneous characteristics of users. Quality of experience (QoE) was introduced as a metric to depict how satisfied terminal users are with the network performance [12]. It can depict different requirements and is more subjective and practical [13]. Therefore, a distributed manner is proposed in this article to maximize the QoE each user experiences on the POC. As far as we are concerned, it is the first time to optimize QoE on the POCs.
Advertisement
Game theory is a powerful distributed method in solving the channel allocation problem in wireless networks [14‐17]. In this article, we formulate the POC accessing problem as a QoE maximization game. By utilizing the approximate relationship between interference and QoE, the game is proved to be an ordinal potential game with at least one Nash Equilibrum (NE). Meanwhile, the best pure strategy NE point is proved to be the approximate global optimum of maximizing network QoE. In order to reach the optimal NE point of the proposed game, a distributed algorithm based on the Spatial Adaptive Play (SAP) [18] is proposed, where each player updates its strategy only with the information of its neighbors.
The contributions of this article can be concluded as follows:
The POC accessing problem is formulated as a QoE maximization game, where the utility function of each player is defined as the QoE it experiences. The game is proved to be an ordinal potential game and the best pure strategy NE point is the approximate global optimum of maximizing network QoE.
A Spatial Adaptive Play (SAP) based distributed algorithm is put forward to reach the optimal NE of the QoE maximization game. The algorithm is distributed which enables each player update its strategy only with the information of its neighbors. It is proved that, when the learning parameter is large enough, the algorithm asymptotically maximizes the network QoE.
Simulations are made to verify the effectiveness of utilizing POC as well as the proposed method.
The rest of the paper is organized as follows. A review of related work is given in Sect. 2. The system model and the problem formulation are given in Sect. 3. In Sect. 4, the QoE maximization game is formulated and analyzed and a distributed algorithm is proposed to reach the NE of the game. Simulation results are presented in Sect. 5 and the conclusion is made in Sect. 6.
2 Related work
The problem of channel accessing has been widely investigated in wireless networks. Most existing researches confined transmissions to non-overlapping channels (NOCs), i.e., orthogonal channels, and focused on mitigating co-channel interference [19‐25]. However, since two adjacent orthogonal channels should be separated by certain bandwidth, such orthogonal using method is a waste of spectrum as can be seen from Fig. 1.
Fig. 1
The illustration of NOCs and POCs
Fig. 2
The QoE function for the elastic service under different sensitivities
Fig. 3
The topology of the network with 35 users
×
×
×
Advertisement
To enhance the spectral utilization, the concept of POC was introduced. Authors of [1, 2] put forward the pioneer idea of using POC. After that, researchers came to make investigations about it successively. Authors of [5, 6] proposed comprehensive interference models together with different algorithms to obtain better results. Authors of [10] took both power tuning and channel assignment into consideration to enhance the performance of wireless local area networks. In [7], a set of algorithms were designed to increase the spatial reuse in wireless mesh networks. In [9], a load-aware based scheme was proposed to improve the network performance. It is notable that, the above existing methods are all centralized, which require centralized controllers and information exchange. Such methods will not be feasible in dense or large-scale networks, where the computation may be too heavy. Therefore, it is necessary to propose a distributed method, which enables users make decisions themselves, to solve the POC utilizing problem.
Game theory is a widely used distributed method in solving the channel allocation problem in wireless networks [26‐28]. While authors of [14‐17] solved the POC allocation problem by using game theory, they all aimed at minimizing interference or maximizing throughput. Such optimization problems can not reflect the heterogeneity of users. For example, in a wireless network, some users are watching videos, some are listening to the music, others are browsing the webpage. Their requirements and sensitivities to the throughput are obviously different. Which means, the same amount of throughput results in different satisfactions for different users. QoE was introduced as a metric to describe the satisfaction users experience with the network performance [12]. According to different services and requirements, different QoE functions are formulated. Such metric is more subjective and practical. Therefore, we take QoE as the optimization goal in this article.
Fig. 4
The convergence of the algorithm
Fig. 5
The influence of network density on average satisfaction
Fig. 6
The influence of users’ sensitivity on average satisfaction
Fig. 7
Comparison of QoE and throughput about different sensitive users
×
×
×
×
The differences of our work with [14‐17] can be concludes as follows. The interference model used in this paper is more accurate than that of [14, 15] which can be defined as a binary one and the network scenario is different from that of [16, 17] where a gateway exists in the network. The optimization problem of this paper is maximizing network QoE which can depict the heterogeneity of users and the proposed SAP-based algorithm can achieve better performance than those of [14‐17].
3 System model and problem formulation
Consider a wireless network with N randomly deployed users. The set of users is defined as \({\fancyscript {N}}\). Each user chooses one channel for transmission and interference may exist if more than one user select the same channel. The number and the set of the channel are denoted as A and \({\fancyscript {A}}= \left\{ {1,2, \ldots ,A} \right\} \), respectively. Denote the channel selection of user i as \(a_i\) and the QoE it experiences as \(q_i\). Note that, \(q_i\) is related to the service it receives. Generally, the better the service is, the higher the QoE is. Different services or requirements correspond to different QoE functions. Specifically, the video service, the audio service and the elastic service are the most typical ones [29]. Since the former two services mainly depend on the loss of transmission which is not the focus of our research, in this article, we assume all users are in elastic services and their sensitivity towards throughput can be different.
where \(R_i\) is the throughput user i achieves, \(c_i\) is the sensitivity parameter of user i towards the throughput, \({{R_{\max }}}\) is the maximum throughput requirement. The QoE function can be explicitly expressed in Fig. 2, where the mean opinion score (MOS) is a widely used index to depict the degree of QoE subjectively.
It can be found from Fig. 2 that the relationship between the MOS and the throughput satisfies the following properties [31]:
When the throughput exceeds the maximal requirement, the MOS will remain at five and not be improved anymore.
When the throughput is under the maximal requirement, the MOS rises monotonously with the increase of throughput and varies from zero to five continuously.
Although the sensitivity of users affect the varying rate of MOS, it has no influence on the overall varying trend of it.
After depicting the relationship between the QoE and the throughput, the influence of the interference on the throughput will be discussed. In this article, we consider the physical interference and the throughput user i achieves is expressed by the Shannon formula. Mathematically,
where B is the bandwidth of one channel, \(p_i\) is its transmission power, \(d_i\) is its transmission radius, \(\alpha \) is the path loss factor, \(N_0\) is the background noise and \(I_i\) is the total interference it suffers from all its neighbors which will be expressed later.
The interference between user i and user j is affected by two factors: the physical distance, i.e. \({d_{ij}}\), and the channel distance, i.e., \(\delta _{ij}^{} = |{a_i} - {a_j}|\) [2]. Two near users need to choose faraway channels to avoid interference while two faraway users can even use the same channel without interfering with each other.
Take the channels in the IEEE 802.11b standards for example.1 The bandwidth is 44 MHz of each channel and the channel separation is 5 MHz. If the central frequency of a specific channel is \(f_c\), the power mask of it can be expressed as [5]
When user i and user j select two channels independently, the overlapping power mask can be expressed as
$$\begin{aligned} H\left( f \right) = \int {{p_i}\left( f \right) } \cdot {p_j}\left( f \right) {\mathrm{d}}f, \end{aligned}$$
(4)
where \({p_i}\left( f \right) \) and \({p_j}\left( f \right) \) are power masks of the channels user i and user j select respectively. Note that, in the frequency domain, the overlapping power mask represents the strength of received signal of each other, which is related to the channel distance. The larger the channel distance is, the less the power masks overlaps and the weaker the strength is. The relationship between the channel distance and the overlapping power mask can be described as [3]
Since the signal strength declines with the increase of the physical distance, interference from faraway users will be weak to be ignored. That is to say, the interfering range can be regard as limited. Denote the set of users in the interfering range of user i as its neighbor. Mathematically,
where \({d_\tau }\) represents the interfering range. Note that, the interference is considered to be symmetric, user i receives the interference from its neighbors as well.
Motivated by [6], considering the effectiveness of both the physical distance and the channel distance, the interference user i suffers can be described as
When \({\delta _{ij}} = 0\), i.e., user i and user j transmit on the same channel, the interference between them only depends on the physical distance.
When \({\delta _{ij}} \ge 5\), i.e., user i and user j transmit on orthogonal channels, interference will never exists between them.
After explaining the meaning of the QoE and the interference, we reveal the relationship between them via the following theorem.
Conjecture 1
The QoE every user in the network experiences is in the approximate monotonous decreasing relationship with the interference it suffers. Meanwhile, maximizing network QoE approximately equals to minimizing network interference.
Proof
The throughput of a specific user, e.g., user i, decreases monotonously with the interference it suffers approximately [32]. Mathematically, \({R_i} \approx g\left( { - {I_i}} \right) \), where \(g\left( \cdot \right) \) is a monotonous increasing function. Meanwhile, the QoE user i experiences increases monotonously with its throughput. Mathematically, \({q_i} = h\left( {{R_i}} \right) \), where \(h\left( \cdot \right) \) is a monotonous increasing function. In this way, \({q_i} = h\left( {{R_i}} \right) \approx h\left\{ {g\left( { - {I_i}} \right) } \right\} = \gamma \left( { - {I_i}} \right) \), where \(\gamma \left( \cdot \right) \) is a monotonous increasing function. Which means, approximately, the less interference a specific user suffers, the better QoE it experiences. Then, motivated by [32], it can be declared that maximizing network QoE is equivalent to minimizing aggregate interference approximately. This ends the proof of Conjecture 1. \(\square \)
Each user aims at achieving its best QoE by accessing the most profitable channel which brings in the least interference. From the perspective of the network, the optimization problem can be formulated as maximizing the aggregate QoE each user experiences, i.e., \(q=\sum \nolimits _{i \in {{\fancyscript {N}}}} {{q_i}}\). Mathematically,
In the network with large amount of users, solving the optimization problem in a centralized method requires much calculation and great complexity. Thus, a self-organized and distributed method which does not need a centralized controller is more effective and reasonable. In this section, we formulate a game model to solve the proposed optimization problem.
where \({\fancyscript {N}}\) is the player set, \({\fancyscript {A}}_i\) is the strategy space of player i, \({\fancyscript {J}}_i\) is the neighbor set of it and \(u_i\) is the utility of it.
Since each player aims at maximizing its own QoE, define the utility function as
where \(a_{-i}\) represents the strategy profile of all players except player i and \(q_i\) is the QoE player i experiences defined in (1). Therefore, the proposed game can be formulated as
The properties of the proposed game are analyzed in this subsection.
Definition 1
(Nash equilibrium (NE) [33]) Only if no player can achieve higher utility by changing its action unilaterally, can the action profile \({a^*} = \left( {a_1^*,a_2^*, \ldots ,a_N^*} \right) \) be called a pure strategy NE. Mathematically,
(Ordinal potential game (OPG) [34]) A game is an OPG if when player i changes its action from \(a_i\) to \(\overline{{a_i}} \) unilaterally, there is a potential function \(\phi \) satisfying the following equation:
where \({\mathrm{sgn}} \left( \cdot \right) \) is a sign function defined as follows:
$$\begin{aligned} {\mathrm{sgn}} \left( x \right) = \left\{ {\begin{array}{ll} 1,& x > 0\\ 0,& x = 0\\ - 1,& x < 0 \end{array}} \right. . \end{aligned}$$
(14)
According to Definition 2, in order to prove \(\fancyscript {G}\) an OPG, we need to find the specific potential function. However, it is hard to find such a meaningful and practical one. Therefore, motivated by [32], we utilize the relationship between the interference and the QoE revealed in Conjecture 1 to find the function in an indirect way.
When playerichanges its action unilaterally, the differences between\(\phi '\)and\({u'_i}\)are the same, i.e.,\(\varDelta \phi ' = \varDelta {u'_i},\forall i \in {{\fancyscript {N}}}\).
Proof
If player i changes its action from \(a_i\) to \(\overline{{a_i}} \) unilaterally, the change of its utility is
For a specific neighbor j, the change of interference it suffers after and before player i unilaterally changes its strategy can be mathematically expressed as
where \({\delta _{ij}^{}}\) is the channel distance after player i unilaterally changes its strategy. Meanwhile, for player i, the change of interference it suffers after and before it changes its strategy can be mathematically given as
Thus, the QoE maximization game \(\fancyscript {G}\) is an ordinal potential game with at least one pure strategy NE. \(\square \)
Lemma 2
The best pure strategy NE of the QoE maximization game\(\fancyscript {G}\)is an approximate global optimum of the QoE maximizing problem\(\mathbf{P}\).
Proof
According to [35], for a finite ordinal potential game, the pure strategy NE is the strategy profile that maximizes the potential function. Since the number of players and strategies are both finite, the QoE maximization game \(\fancyscript {G}\) is a finite ordinal potential game. Denote the strategy profile maximizing the potential function \(\phi \), i.e., the pure strategy NE of \(\fancyscript {G}\), as
Note that, the QoE maximization game will be very general if we try to prove it an ordinal one directly. However, by utilizing the approximation relationship between the QoE and the interference revealed in Conjecture 1, it can be analyzed with the properties of potential games and promising results can be obtained.
4.3 An spatial adaptive play based distributed algorithm
In order to reach the NE of the game, i.e., the local or global optimal of the problem, a distributed learning algorithm is designed in this section. Although many existing algorithms, e.g., the best response (BR) [36], the learning by trial and error [37] and the stochastic learning automata (SLA) [14] can realize the purpose, they are not guaranteed to reach the optimal NE, i.e., the global optimal of the problem. Therefore, we propose a distributed algorithm to reach the optimal NE where each player makes the decision itself with the information of its neighbors.
The algorithm is on the basis of the spatial adaptive play [18] and during each iteration, only one player is selected stochastically to update its strategy while others remain unchanged. The selected player detects all channels, updates the channel selection probabilities and chooses one of the channel with probability. Note that, each player only requires information from its neighbors instead of the whole network. The formal description of the proposed algorithm is shown in Algorithm 1.
The property of Algorithm 1 is given by the following theorem.
Theorem 2
When the learning parameter\(\beta \)is large enough, Algorithm 1 asymptotically maximizes the network QoEq.
Proof
According to the methodology given in [18], when \(\beta \) is large enough, Algorithm 1 will asymptotically converge to a profile maximizing the potential function \(\phi '\). Combining with the relationship of \(\phi '\) and the aggregate interference I, together with Conjecture 1, it can be known that the profile maximizes the network QoE q approximately. This ends the proof of Theorem 2. \(\square \)
×
5 Simulation results and discussions
In this section, simulation results are given to verify the effectiveness of the proposed method. The network is a \(200\,{\mathrm{m}} \times 200\,{\mathrm{m}}\) one with the number of users varying from 20 to 40 to depict different densities of the network. Specifically, when the user amount is 20, the network is a relatively sparse one and when the user amount is 40, it is a relatively dense one. The path loss exponent is set as \({\theta =3}\). The background noise \({N_0} = - 110\,{\mathrm{dBm}}\). The transmission power of each user is \(23\,{\mathrm{dBm}}\) and the transmission range is 30 m [2]. The neighbor range is twice as large as the transmission range, i.e., 60 m, which means all users within 60 m may interfere with each other [39]. The topology of a network with 35 users is given in Fig. 3. The blue dots represents different users and the black lines between them represent the interfering relationship.
5.1 The convergence of the algorithm
The convergence of the proposed algorithm is shown in this subsection. The simulation is made in the network with 35 medium sensitive users, i.e., \(c_i=3, \forall i \in {{\fancyscript {N}}}\). It can be seen from Fig. 4 that the algorithm converges at about 300 iterations. The proposed algorithm is compared with other algorithms used in existing works, e.g., the SLA based algorithm in [14] and the Smoothed Better Response algorithm in [16]. Simulation results verify the superiority of the proposed algorithm. Besides, we make a comparison with the interference model used in [15] and it can be seen that the interference model used in this work can achieve better performance. This is because the interference model in [15] overlooked much interference which may make the channel selection strategies not effective. It is also notable that the average MOS achieved by utilizing POC is much higher than that by utilizing NOC. This is because there are more available channels for users to access when utilizing POC which can bring in less interference, higher throughput and better satisfaction.
5.2 The influence of network density on average satisfaction
Figure 5 shows the average satisfaction against the network density. The results and the reasons are given as follows:
When the number of users rises, the average MOS turns down. This is because there are more users compete for the same amount of channels and interference turns more severe which results in poorer satisfaction.
The superiority of using POC turns more evident when the network turns denser. Specifically, the enhancement of using POC against with NOC is \(4.1\%\), \(8.8\%\), \(13.2\%\), \(16.4\%\) and \(19.6\%\) when the amount of user is 20, 25, 30, 35 and 40 respectively. This is because when the network is relative sparse, it is quite possible for any user and its neighbors select different channels even there are only three available channels (NOC). With the increase of density, a user will have more neighbors and it is more likely for a user and its neighbors select the same channel when the number of available channels is three (NOC). However, POC allows users select channels from eleven ones and the possibility of choosing the same channel degrades a lot.
5.3 The influence of sensitivity on average satisfaction
Figure 6 compares the influence of sensitivity on average satisfaction. The sensitivity of users towards throughput are classified into three types, i.e., low, medium and high with \(c=2, c=3, c=4\), respectively. It can be seen that when all users are high sensitive, the average satisfaction is higher. This is because they are more easily satisfied than medium or low sensitive circumstances when given the same throughput. It can also be seen that heterogeneous sensitivity of users will not affect the performance of the proposed method.
5.4 The influence of sensitivity on individual performance
In order to depict the differences of sensitivities, five randomly selected users are analyzed in this subsection. Specifically, the sensitivity of user 1 and 2 is two, that of user 3 and 4 is three and that of user 5 is 4. That is to say, user 4 is the most sensitive one while user 1 and 2 are the least sensitive ones. It can be seen from Fig. 7 that when the sensitivity of different users is the same, the more throughput a user achieves, the better QoE it receives. For example, user 2 achieves less throughput than user 1 and thus gets poorer satisfaction. This is because the satisfaction is a monotonic increasing function of throughput given other parameters predetermined. However, when the sensitivities are different, the conclusion changes. For example, although user 4 achieves less throughput than user 1 and 3, its satisfaction is better. This is because the satisfaction of more sensitive user grows faster with the increase of throughput and the user can achieve better satisfaction when given the same amount of throughput.
6 Conclusion
In this article, the POC accessing problem in the wireless network was investigated to enhance the spectral utilization. Instead of maximizing the throughput or minimizing the interference, maximizing the network QoE was set as the optimization goal to depict the heterogeneity of users. The problem was formulated as a QoE maximization game. By utilizing the approximate relation between the interference and QoE, the proposed game was proved to be an ordinal potential game with at least one pure NE. Meanwhile, the best pure strategy NE point was an approximate global optimum of maximizing network QoE. In order to reach the NE of the game, a distributed algorithm was proposed, which can asymptotically maximize the network QoE if the learning parameter is large enough. The effectiveness of the proposed method was verified though simulations.
Acknowledgements
Funding was provided by Natural Science Foundation for Distinguished Young Scholars of Jiangsu Province (Grant No. BK20160034), National Natural Science Foundation of China (CN) (Grant Nos. 61771488, 61631020), National Science Foundation of China (Grant Nos. 61671473, 61401508), Open Research Foundation of Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
The parameters of channels but not the access method used in this article are based on the IEEE 802.11b standards. The network is universal and the method and analysis are without loss of generality which can be used on channels in other standards.
