Advanced
Priority-based Differentiated Service in Spectrum Mobility Game
Priority-based Differentiated Service in Spectrum Mobility Game
KSII Transactions on Internet and Information Systems (TIIS). 2014. Apr, 8(4): 1324-1343
Copyright © 2014, Korean Society For Internet Information
  • Received : November 26, 2013
  • Accepted : March 20, 2014
  • Published : April 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Bingxian Lu
School of Software, Dalian University of Technology Dalian, Liaoning 116000 - CN
Zhenquan Qin
School of Software, Dalian University of Technology Dalian, Liaoning 116000 - CN
Lei Wang
School of Software, Dalian University of Technology Dalian, Liaoning 116000 - CN
Liang Sun
School of Software, Dalian University of Technology Dalian, Liaoning 116000 - CN
Ming Zhu
School of Software, Dalian University of Technology Dalian, Liaoning 116000 - CN
Lei Shu
Guangdong Petrochemical Equipment Fault Diagnosis Key Laboratory, Guangdong University of Petrochemical Technology, Maoming, Guangdong 525000 - CN

Abstract
In recent years, the problem of spectrum mobility in Cognitive Radio (CR) Networks has been widely investigated. In order to utilize spectrum resources completely, many spectrum handoff techniques based on game theory have been proposed, but most studies only concern that users how to achieve better payoffs, without much attention to the diverse needs of users. In this paper, we propose a new channel-switching model based on game theory, using a prioritized approach to meet the diverse needs of users in two different modes (CQ and PS). At the same time, this paper proposes some acceleration techniques to reach the Nash equilibrium more efficiently. We evaluate the performance of the proposed schemes depending on priority using real channel availability measurements, and conclude that the channel quality function (CQ) mode provide better service for priority user but the plan-sorting (PS) mode can be more suitable in multiple priority users exist scene.
Keywords
1. Introduction
W ith the development and popularization of wireless technology, wireless technology has been applied in many scenarios, like mobile phone, TV, radio, satellite, and WiFi. Especially, in recent years, with the rapidly growing popularity of WiFi, WiFi Access Point (AP) exists in every corner of our life, like Starbucks, McDonald’s, airports, railway stations, and even in telephone booths.
Wireless technology greatly facilitates our life, but the limited spectrum resources are too short to meet our demand for frequency bands. Available channel bands become more and more crowded, especially with the appearance of 4G and other new technologies, and the current available bands are not enough for new technology to use. Therefore, we need a method to take full use of existing spectrum resources.
In recent years, cognitive radio network has been widely investigated. Cognitive radio is an intelligent wireless communication system that is aware of its surrounding environment, and uses the methodology of understanding-by-building to learn from the environment and adapt its internal states to statistical variations in the incoming RF stimuli by making corresponding changes to certain operating parameters in real-time, with two primary objectives in mind: highly reliable communication whenever and wherever needed; efficient utilization of the radio spectrum [1] .
In order to utilize spectrum resources completely, people need to find those bands that can be used. In recent years, Microsoft, Google, and other enterprises have begun to establish their own spectrum database, and have already made a number of significant achievements, such as Microsoft’s WhiteSpaceFinder (see Fig. 1 ). The FCC’s rule said that users must be given access to a predictive database which details the time when the license holders will be active/inactive over the next 24 hours [2] , which make cognitive radio network users have the capacity to use these data to make their own spectrum switching plans.
PPT Slide
Lager Image
Microsoft Research WhiteSpaceFinder [5].
Since the inception of the game theory, a growing number of areas began to utilize the theory to study, analyze, model, and solve problems. For wireless networks, especially cognitive radio network, game theory is an important research tool.
There have been many scholars used game theory to study cognitive radio network [3] . For example, Southwell et al. [2] has solved the problem that when cognitive network users meet the situation that existing channel is not available, they will choose to use it continually or to switch to other channels for better payoffs, and Malanchini et al. [4] introduced the gambling problems in selecting channels.
These studies in modeling mostly focus on the system’s overall payoffs, in fact, some users may need high speed, and the others need low speed. The existing models and the methods cannot well adapt to the demand.
A common assumption in previous congestion game based spectrum sharing literature is that a user’s utility strictly increases with its received data rate (and hence strictly decreases with the congestion level). This is true, for example, when users are running elastic applications such as file downloading. However, there are many other types of applications with more specific QoS requirements, such as VoIP and video streaming. These inelastic applications cannot work properly when their QoS requirements are violated, but do not obtain additional benefits when given more resources than needed. This kind of traffic is becoming increasingly popular over the wireless networks. This motivates us to study the spectrum mobility game model with priority in this paper. Rather than assuming that users wish to increase their data rates whenever possible, we assume that each user has a fixed QoS requirement. If the requirement is satisfied, then the user has no inclination to change his choice of resource. It was inspired that the concept of focusing upon satisfaction rather than data rate maximization [6] .
Therefore, this article proposes a game model of cognitive network that meets the different requirements. This model achieves to meet the needs of high speed and low speed for different users at the same time, based on the approach that different needs of users use different priority.
The follows is the main innovation of this paper:
(1) Propose a game model with priority, which can satisfy different performance requirements of users: We propose a kind of spectrum-mobility-game-model with priority. The model provides different quality of service based on setting different priorities to different users. Our model can take both primary user (PU) and secondary user (SU) into consideration.
(2) Propose new acceleration technology to accelerate the convergence to the optimal solution: We propose the acceleration technology based on the partition method, at the same time we use the algorithm of approximate Nash equilibria to speed up.
The organization of the rest of this paper is as follows. In Section II, we survey related work. In Section III, we present our spectrum mobility games with priority model. In Section IV, we present novel techniques to accelerate convergence. We present specifics of simulation experiments, which validate the correctness of the proposed algorithm in Section V. Finally, Section VI concludes the paper.
2. Related Work
The problem of spectrum mobility in cognitive radio networks has been widely investigated in the literature recently [7] - [11] .
- 2.1 Game Theory for Cognitive Radio Networks
Game theory is an important tool in studying, modeling, and analyzing the cognitive radio networks [7 , 12] .
Southwell et al. [2] presented a general game theoretic model of cognitive radio-channel- selection-problem with switching cost (see Fig. 2 ). The authors used a symmetric network- congestion-game-model to solve the spectrum mobility problem with prior information of heterogeneous channels. The authors also provided a decentralized algorithm for achieving Nash equilibria without communicating.
PPT Slide
Lager Image
A general game theoretic model of cognitive radio channel selection problem.
Malanchini et al. [4] proposed a game theoretic framework to evaluate spectrum management problem in cognitive radio network. CR users can adopt the framework in order to share available bands with other users. At the same time, the authors analyzed the properties of spectrum selection game.
Chen et al. [13] adopted a game theoretic approach for the database-assisted TV white space access point (AP) network design. The authors provided a distributed algorithm, which allows multiple players to organize themselves into Nash equilibria.
However, those general game theoretic models are simple and easy to use, but none of them concerned about the issue of differentiated service.
- 2.2 QoS in Cognitive Radio Networks
Dasilva et al. [14] stated that a complete solution to the problem of providing adequate quality of service (QoS) to heterogeneous users must take into account the issue of pricing. By adopting an appropriate pricing policy and by setting prices carefully, a service provider will be able to offer the necessary incentives for each user to choose the best service that matches his/her needs, thereby discouraging over-allocation of resources and maximizing revenue and/or social welfare.
Roberts [6] presented the main points of an analysis of the statistical nature of Internet traffic and the way that affects the performance of voice, video, text, and data services. The author proposed an alternative flow-aware networking architecture based on a novel router design called cross-protect. In this architecture, performance requirements are satisfied without explicit service differentiation, creating a particularly simple platform for the converged network.
Wang et al. [15] analyzed a cognitive radio network where SUs contend for spectrum usage, using random access method, over available PU channels. The authors focused on SUs’ queuing delay performance, and they studied the steady-state delay performance of SUs by applying a fluid-queue-approximation-approach.
There are many other researches about QoS in cognitive radio networks, such as [16] - [20] . In this paper, we focus on the different needs of SUs, and use a priority-based method to provide differentiated service.
- 2.3 Convergence to Approximate Nash Equilibria
Fabrikant et al. [21] stated that in the symmetric network [22] , a pure Nash equilibrium can be computed in polynomial time. They proposed a polynomial algorithm for finding a pure Nash equilibrium in symmetric network congestion games.
Chien et al. [23] studied the ability of decentralized, local dynamics in non-cooperative games to reach an approximate Nash equilibrium rapidly. They stated that symmetric congestion games [24] can converge to an ε -Nash equilibrium within a number of steps that is polynomial in the number of players and ε −1 . Feldmann et al. [25] analyzed which approximation guarantees can be achieved by the method of randomized rounding for network congestion games with delay functions such as polynomials, exponential functions, and functions from queuing theory.
In this paper, we use an approximation algorithm to reach Nash equilibria for our game model.
- 2.4 Symmetric Network Congestion Games
Congestion games [26] have been used to study many network resource allocation scenarios. The basic idea behind congestion games is that a player needs to pay a cost de ( x ) when he uses a resource e with a congestion x . In a network congestion game, the resources are edges within a graph. Each player selects a route from their source vertex to their destination vertex, in an attempt to minimize the cost they pay from traversing congested edges. For example, network congestion games can model how drivers select routes through cities. A network congestion game is symmetric [22] when every player selects a route from the same source vertex to the same destination vertex.
Since symmetric network congestion games are congestion games, they have the finite improvement property. This means that when players keep improving their strategy choices asynchronously where no more than one player changes its strategy at any given time, the system will eventually reach a Nash equilibrium.
The correspondence between spectrum mobility games and symmetric network congestion games allows us to design a spectrum mobility planning protocol. The purpose of this protocol is to allow the users to select their routes through frequency-time in a mutually acceptable and efficient way, i.e., reaching a Nash equilibrium.
- 2.5 Priority-based Differentiated Service
Kim et al. [27] proposed a priority-based scheme, comprising Frame Tailoring and Priority Toning, in order to relax such a problematic delay and guarantee time-bounded delivery of high priority packets in event-monitoring networks.
Yaghmaee et al. [28] observed that the information provided might have different levels of importance and argue that sensor networks should be willing to spend more resources in disseminating packets carrying information that is more important. Some applications of WMSNs may need to send real time traffic toward the sink node. This real time traffic requires low latency and high reliability so that immediate remedial and defensive actions can be taken when needed. Therefore, similar to wired networks, service differentiation in wireless sensor networks is also an important issue. The authors present a priority-based rate control mechanism for congestion control and service differentiation in WMSNs. They distinguish high priority real time traffic from low priority non-real time traffic, and service the input traffic based on its priority. Simulation results confirm the superior performance of the proposed model with respect to delays, delay variation, and loss probability.
Wang et al. [29] stated that in wireless sensor networks (WSNs), congestion occurs, for example, when nodes are densely distributed, and/or the application produces high flow rate near the sink due to the convergent nature of upstream traffic. Congestion may cause packet loss, which in turn lowers throughput and wastes energy. Therefore congestion in WSNs needs to be controlled for high energy-efficiency, to prolong system lifetime, improve fairness, and improve quality of service (QoS) in terms of throughput (or link utilization) and packet loss ratio along with the packet delay. The authors propose a node priority-based congestion control protocol (PCCP) for wireless sensor networks. In PCCP, node priority index is introduced to reflect the importance of each node. PCCP uses packet interarrival time along with packet service time to measure a parameter defined as congestion degree and furthermore imposes hop-by-hop control based on the measured congestion degree as well as the node priority index. PCCP controls congestion faster and more energy-efficiency than other known techniques.
In this paper, we use the priority-based differentiated service to get better performance in cognitive radio network.
3. The Spectrum Mobility Games with Priority Model
- 3.1 Assumptions and Notations
We consider a scenario that cognitive radio network SUs use a spectrum database provided by a spectrum allocation server (see Fig. 3 ). We denote the set of heterogeneous channels by B , the set of SUs by N . We divide time into independently time slots. We can choose the length of a time slot to be any value that is suitable for various kinds of scenarios. The server has prior information of the channel availabilities, so the users can access the spectrum database, which is on the server, which describes the available channels over the coming T time slots. We involve set T ={1,2,⋯, T }, representing the set of the next T time slots. By requesting the server, users plan how to act over these time slots.
PPT Slide
Lager Image
Spectrum sharing with spectrum database.
For every time-frequency point ( b , t ) with time t T and channel b B , the spectrum database has channel quality functions f (b, t) ( x ). The function (1) shows a user’s payoff for using channel b at time t , while x represents a total number of users on channel b at time t , and V represents the initial value of the channel quality. It is non-increasing and non-negative with x , reflecting that a user’s benefit by using a channel will decrease with the congestion level.
PPT Slide
Lager Image
To apply to many practical scenarios, the model allows every time-frequency point ( b , t ) to have a different channel quality function. The model can allow one channel to have a lower bandwidth than another, i.e., f (b, t) ( x )< f (b′,t) ( x ). The model can also allow the payoff of using a channel to change over time in a way, which represents license holder dynamics. For example, in a spectrum underlay network scenario, we have f (b, t) ( x )=0 for all x > J , representing the scenario where the license holder of channel b will not tolerate more than J users transmitting concurrently on the channel. In a spectrum overlay network scenario, we set f (b, t) ( x )=0 for all x , which represents that the license holder is active on channel b at time t , and the cognitive radio users can’ t access that channel.
The model assume that a user must pay a cost of k ( k ≥0) every time for switching channels. This allows us to model several possible negative effects of switching. At the same time, it takes a fixed number of s ( s ≥0) time slots every time for a user switches channels. For example, if a user begins switching at the end of time slot t, then it will land on the destination channel at the beginning of time slot t + s +1. We assume that users cannot gain any payoff when they are in the middle of switching.
- 3.2 Spectrum Mobility Games with Priority
The spectrum mobility game with priority is specified by a 7-tuple Γ=( N , P , B , T ,( f (b, t) ) (b, t) B × T , s , k ) where N ={1,2,⋯, N } is the set of players, P ={ P 1 , P 2 ,⋯, PN } is the set of players’ priorities, B ={1,2,⋯, B } is the set of heterogenous channels, T ={1,2,⋯, T } is the set of time slots, f (b, t) is the (non-increasing) channel quality function of channel b at time t , s ( s ≥0) is the number of time slots it takes for a user to switch, and k ( k ≥0) is the switching cost.
For the spectrum mobility game with priority, we redefine the channel quality function f (b, t) with priority. We will detail this in next section.
We show how users can switch channels with a directed graph G =( V , E ) (see Fig. 4 ). Routes through the graph G represent routes through time-frequency. When a user travels along a route, the user gains payoffs at the vertices, and pays costs at the edges. The graph G =( V , E ) is defined as follows:
PPT Slide
Lager Image
Spectrum Mobility Games with priority in a directed graph.
  • The vertex is set asV=B×T. Vertex (b,t)∈Vrepresents channelbin time slott.
  • The edge is setE=Estick⋃Eswitch. The setEstickrepresents the actions where users do not switch channels, i.e.,Estickis the set of all edges of the form ((b,t),(b,t+1)) such thatb∈Bandt∈{1,2,⋯,T−1}. The setEswitchrepresents the actions where users switch channels, i.e., the set of all edges of the form ((b,t),(b′,t+s+1)) such thatb,b′∈B:b≠b′ andt∈{1,2,⋯,T−1−s}.
We denote the set of all routes from a vertex of the form ( b ,1)∈ V to a vertex of the form ( b ′, T )∈ V in G by ℛ=⋃ c,c′∈B RG (( b ,1),( b ', T )). Moreover, define cost as E ↦ℕ 0 such that ∀ e ;∈ E we have
PPT Slide
Lager Image
In this context, we map the player’s route as its chosen strategy, and the strategy of the player n N is its route X n =ℛ. The game profile X =( X n ) n′∈N ∈( R ) N consists of each player’s choice of route. Note that a game profile includes one strategy for each player. Similarly, X n is defined as the strategy set chosen by all other players except player n.
Since the game is executed in a distributed manner, the utility function Un ( X ) of each player n N only depends on the strategy of its own and neighbors, and is defined as,
PPT Slide
Lager Image
where ψX ( v )=| n ′∈ N : v V ( X ) n | is the total number of users whose chosen routes visit the vertex v . The first sum in (3) represents the payoff that user n gains from transmitting on channels. The second sum in (3) represents the cost it pays due to switching. In order to achieve an optimal value for Un ( X ), the players will negotiate and change their interdependent strategies in X .
Definition (Nash Equilibrium, NE) , A strategy X * X is a NE if it satisfies
PPT Slide
Lager Image
According to this definition, no player can benefit by deviating from its strategy if other players do not change theirs. In other words, this result guarantees an agreement for negotiations among all the players. However, it can’t be intrinsically guaranteed of optimal outcome or fairness.
- 3.3 Priority-based Differentiated Service
For each user Ni , we define a demand Qi . Users can generate the priority Pi according to their requirements Qi , and server will make spectrum mobility plans and charge based on the priorities of users. For example, the demand Q of the user who is utilizing the short message service (SMS) is low, correspondingly the priority P is low, the quality of the spectrum mobility plan which was assigned is poor, available time is short, delay is high, and the price is low; On the contrary, the demand Q of the user who is watching video is high, correspondingly the priority P is high, the quality of the spectrum mobility plan which was assigned is good, available time is long, delay is low, and the price is high.
Here, our model has two working modes:
(1) To achieve the mechanism that high priority users get better quality of the channel by adjusting the channel quality function. First, we change the channel quality function to
PPT Slide
Lager Image
By default, all users priority P = 1, there are a total of x users on channel b at time t . The channel quality function f (b, t) ( x )= V /( I 1 + I 2 +⋯+ IN )= V / x , that is, the user benefits associated with channel congestion degree. When the priority of user Ni rises, the quality value of the channel used by the user will decrease (quality does not necessarily reduce the actual channel), so that other users will avoid Ni of the channel, allowing users Ni can be exclusive or share the channel with less users, and the channel quality that user Ni gains will improve. As shown in Fig. 5 , when the red user’s priority P =1, it has no difference with general users; When the priority of user was advanced, with P =2, the user began to use exclusively part of time slots; When the priority of user continues to ascend, with P ≥3, the time slots used by the user are all exclusive. For PUs, we can set its priority to infinity, that is, the quality function of the channel containing PU is f (b, t) =1/∞≈0, so we can regard the PUs as special users who have infinitely large priority.
PPT Slide
Lager Image
Differentiated Service.
(2) When the server allocates the channels according to the information of available channel in spectrum database, it generates a spectrum mobility plans set X which includes N plans, while the N is the number of active users. The server will analyze the qualities of plans in X , for example, speed, delay, etc. Sorting according to the qualities of plans, and finally allocates the spectrum mobility plans according to the priority level. The high priority user gets the high quality plan; on the contrary, the low priority user gets the low quality plan.
The first working mode changes the channel quality function to provide differentiated service, denoted as channel quality function (CQ) mode; and the second working mode sorts the plans to provide differentiated service, denoted as plan-sorting (PS) mode.
4. Techniques to Accelerate Convergence
In this section, we present novel techniques for spectrum mobility game with priority to improve convergence speed.
- 4.1 Divide and Conquer
After we bring PU into the model, we found that in the model of spectrum mobility game with priority, PU has no essential difference from SU without concerning priority, and PU do not need to participate in the game with SU, from which we get inspired: high priority users can take precedence to choose their own plan, and the low priority users’ plan does not have much influence on the former.
With the conclusion above, we can use "Divide and Conquer" method to divide users into smaller groups by priority and play games within each group, so as to reduce the computation scale.
Shown in Fig. 6 , specific steps are as follows:
PPT Slide
Lager Image
The Accelerate Convergence Algorithm.
  • Divide users into several groups by priority, and users of the same priority belong to the same group.
  • Sort the groups according to the priority of the groups from big to small in order.
  • Play the game inside the highest priority group to achieve Nash equilibria.
  • Play the game inside the priority groups to achieve Nash equilibria, until it reaches the Nash equilibria within the lowest priority group.
Shown in Fig. 7 , as the first step, PUs, which the priority is ∞, make their plans, then high priority SUs play and make plans, finally low priority SUs play and make plans.
PPT Slide
Lager Image
Divide and conquer method.
- 4.2 Algorithm to Approximate Nash Equilibria
Only when the channel quality functions and switching costs of the spectrum mobility game are integer valued, does it correspond to a symmetric network congestion game with integer valued cost functions. There is a polynomial time algorithm which can be used to find a Nash equilibrium of such symmetric network congestion games. Thus, one limitation of our model is that it is not guaranteed to converge within polynomial time when the channel quality functions and switching costs are not integer valued.
Chien et al. [23] studied the ability of decentralized, local dynamics in non-cooperative games to rapidly reach an approximate Nash equilibrium. Feldmann et al. [25] analyzed that approximation guarantees can be achieved for congestion games by the method of randomised rounding. Their results show that the success of this method depends on different criteria depending on the class of functions considered. Inspired by their work, we use an approximation algorithm to reach Nash equilibria for our game model.
For symmetric congestion games in which the edge delays satisfy a "bounded jump" condition, the game can convergence to an ε -Nash equilibrium within a number of steps that is polynomial in the number of players and ε −1 . We prove that rapid convergence holds even under only the apparently minimal assumption that no player is excluded from moving for arbitrarily many steps. We also prove that, in a generalized setting where players have different tolerances εi that specify their thresholds in the approximate Nash equilibrium, the number of moves made by a player before equilibrium is reached depends only on his associated εi , and not on those of the other players. Finally, we show that polynomial time convergence still holds even when a bounded number of edges are allowed to have arbitrary delay functions.
A network symmetric congestion game is described by a directed graph G =( V , E ) with m edges, a set N of n players, a pair ( si , ti )∈ V × V of source and target node for each player i N , and a non-decreasing delay function de for each edge e E . For i N we denote by Pi the set of all paths from node si to node ti . Every player i has to choose one path Pi from the set Pi and to allocate all edges on this path. For a state S =( P 1 , P 2 ,⋯, Pn )∈ P 1 × P 2 ×⋯× P n and an edge e E , we denote by ne ( S ) the number of players allocating edge e in state S , i.e. ne ( S )=|{ i N | e Pi }|. The delay δi ( S ) to a player i N in state S is defined as equal to the delay dpi ( S ):=Σ ePi de ( ne ( S ) of the chosen path Pi in S . Every player wants to allocate a path with minimum delay. We say that a state S is a Nash equilibrium if no player can decrease her delay by changing her strategy. That is, if state S ′ is obtained from S by letting one player i N change her strategy, then the delay δi ( S )′) is at least as large as the delay δi ( S ). A state S is said to be an ε -approximate Nash equilibrium if δi ( S )≤(1+ ε )⋅ δi ( S )′) for every state S ′ that is obtained from S by letting one player i N change her strategy.
PPT Slide
Lager Image
Compute approximate Nash equilibria.
In order to compute approximate Nash equilibria, we use the method of randomized rounding. First, we relax the network congestion game by replacing each player by an infinite set of agents, each of which controls an infinitesimal amount of flow. To be more precise, we can transform the network congestion game into a multi-commodity flow problem [30] and we introduce a flow demand of 1 that is to be routed from node si to node ti for every player i N . The delay of edge e E is de ( f )= de ( fe ), and the delay on a path P is the sum of the delays of its edges, i.e. dP ( f )=Σ e∈P de ( fe ). A flow vector f is called a Wardrop equilibrium [25] if for all commodities i N and all paths P 1 , Pi Pi with fP 1 >0 it holds that dP 1 ( f ) dP 2 ( f ). It is well known that Wardrop equilibria can be computed in polynomial time using convex programming.
By using the approximation algorithm, our game model ensures to reach an approximate Nash equilibrium within polynomial time whether the channel quality functions and switching costs are integer valued or not.
5. Simulations
- 5.1 Experiment Setup
We applied our proposed model to study spectrum mobility of channel availability using real data. The data we used was a record of the availability of B =3 channels in total length for 1 minute in Maryland. Time is divided into T =600 time slots, each 0.1 seconds long. The data can be represented by a 3 × 600 matrix D * like that
PPT Slide
Lager Image
We use the database D * of a spectrum mobility game with priority in each frequency time piece ( b , t ) has a channel quality function f (b, t) ( x )= D * b, t / x .
We studied the behavior of N = 10 users at the Nash equilibria. We consider a switching costs k = 0 , and investigate the effect of the priority P (see Figs. 9 and Figs. 10 ). Out of the 3 × 600 time-frequency blocks, only 1173 are available. In each Nash equilibrium computed, at least one player accesses each available time-frequency block; because of the form of the channel quality functions f (b, t) , the average payoff of the users is thus equal to 117.3 in average cases.
PPT Slide
Lager Image
Payoff of priority user and average.
PPT Slide
Lager Image
Average congestion level of channels which are used by priority user.
- 5.2 Payoff
First, we compare payoff of selected user in CQ and PS mode. Fig. 9 shows the comparison between the payoffs of the selected user. Set the number of users N to 10 in this simulation, which includes a priority user. Set the of the ordinary users’ priority to 1, and the priority level of priority user ranges from 1 to 10. In the figure, set the priority level of priority users as the horizontal ordinate, and the payoff as the vertical ordinate. In Fig. 9 , we can clearly see that with the growth of the priority, the selected user’s payoff increases gradually in both CQ and PS mode. This is because when P is larger, the users can get better channels, and thus cause decreasing of payoffs to users who do not have a high priority. At the same time, we can see that whit the growth of the priority, the payoff of the selected user in CQ mode increases much quicker than it in PS mode. In CQ mode, when the priority is 9, it reaches the maximum payoff, that is, the number of total users minus 1 ( N −1). And in PS mode, when the priority is 10, it reaches the maximum payoff, that is, the number of total users ( N ). On the other hand, with the change of the priority, the average payoff of all users fluctuates at around 110 in both CQ and PS mode. It reflects that the change of priority has little effect to all users in only one-priority users exist scene, which being consistent with the forecast analysis.
- 5.3 Congestion Level
Then, we compare average congestion level of channels, which are used by the selected user in CQ and PS mode. Fig. 10 shows how the average congestion level of the selected user changes with the change of the priority level. In Fig. 8 We can see that with the increasing of priority, the channel’s average channel congestion degree decreases significantly in CQ mode, and its service quality is becoming better. And in CQ mode, when the priority grows up to N −1, the average channel congestion degree no longer reduces, and stays steady at around 2.4. At this point, the quality of service the user obtains is optimal, that is, with the increasing of priority, the quality of service does not enhance any more. In PS mode, the average congestion level of channels, which are used by the selected user, has not shifted noticeably.
- 5.4 Mutil-user
Shown in Fig. 11 and Fig. 12 , we studied the behavior of users at the Nash equilibria in CQ and PS mode, in each mode there are two selected users: A and B. We conduct three comparisons, and set the priority level respectively as following:
PPT Slide
Lager Image
Payoffs of 2 priority users exist scene in CQ mode.
PPT Slide
Lager Image
Payoffs of 2 priority users exist scene in PS mode.
  • PA=4,PB=7;
  • PA=5,PB=5;
  • PA=7,PB=4
From these comparisons, we can find that users who have higher priority can have more payoffs than lower priority users in both CQ and PS mode. Moreover, the average payoff of all users in CQ mode is lower than the payoff in PS mode.
In the experiments described above, we use the generic algorithm and accelerate convergence technology at the same time. Results show that in both CQ and PS mode scenario, the general algorithm has similar results with our algorithm using accelerate convergence technology, while the cost of time of the latter is much less than the former.
- 5.5 Performance comparison
We implement another simulation with the number of users N = 40, 50, and 60 with half of the users having a high QoS demand. Upon comparison, we also implement the decentralized spectrum access solution by Q-learning mechanism proposed in [31] . We observe that our algorithm can achieve up-to 32% performance gain over the Q learning mechanism. Compared with the PS mode, the performance loss of the CQ mode is at most 10%. This demonstrates the efficiency of the proposed algorithm.
PPT Slide
Lager Image
Performance comparison of the PS mode, CQ mode, and Q-learning mechanism.
6. Conclusion
Our main contribution is that we proposed a model of spectrum mobility game with priority, which can provide differentiated service and is suitable for users in scenarios with different requirements. Without affecting the overall payoff, our model is able to provide users who have different needs (i.e., has different priorities) with different services. In the meantime, due to the priority, we can view the PUs as special users with the highest priority, so that our model is not only suitable for competition with SU, but also put the PU and the SU into consideration together.
In CQ mode, when only a high priority user exists, and other users’ priorities are the default values, the selected user advances the default user priority 1 to N −1, and in the process of which, the user’s payoff increases significantly. Then if improve the user’s priority again, income does not improve, the average for all users in the process has no obvious change. It proves that our model is effective to meet the high demand for the user to provide better services, meanwhile, we get the conclusion that the highest priority can be set to N −1. In PS mode, the high priority user’s payoff increases but not significantly. And because it’s a sorting method, the highest priority can be set to N .
In the case of multiple priority users exist, our experiments proved that higher priority users’ payoff is always higher than the lower one, and the same priority users get similar amount of payoff, which proves that our model in the presence of multiple high priority users can still provide different services for different needs of users. However, in CQ mode, the average payoff of all users wills decreases when more than one priority users exist. On the contrary, the number of priority user does not affect the average payoff of all users.
We can conclude that the priority user will get better service in CQ mode than it in PS mode, and the PS mode can used in multiple priority users exist scene without affect the average payoff of all users.
In order to accelerate the convergence speed, we propose two different acceleration technologies: First, we use divide and conquer method, and only let the same priority user compete, which effectively reduces the size of the game, and speeds up the convergence speed. Then, we use an algorithm of approximation Nash equilibria, which can significantly improve the convergence speed to ensure the convergence of a better result at the same time.
In our experiment, there was no significant difference between the general algorithm and the acceleration technology, while time spent in the latter is apparently less than the former, which proves that the acceleration of our technology can be achieved to very close to the optimal solution in a short period of time.
In the future work, we will optimize the acceleration algorithm to achieve better results. We also plan to broaden our model’s uncertainty and random circumstance of channels. Random games seem to be the appropriate model for these scenarios. This promotion is very challenging, and will be popular in the future cognitive radio scenarios.
Acknowledgements
This work is supported by Natural Science Foundation of China under Grants No. 61070181, No. 61272524 and No.61202442. Lei Shu’s research work in this paper is supported by the Guangdong University of Petrochemical Technology’s Internal Project No. 2012RC0106, and Open Fund of Guangdong Provincial Key Laboratory of Petrochemical Equipment Fault Diagnosis No.GDUPTKLAB201323.
BIO
Bingxian Lu was born in 1991. He received a Bachelor degree in software engineering in 2012, and an M.E. in 2014 both from Dalian University of Technology, Dalian, China, where he is going for a Ph.D. degree. He is a student member of ACM and China Computer Federation (CCF). His research interests include wireless network, cognitive radio networks, and game theory.
Zhenquan Qin received the bachelor degree in security engineering and the Ph.D. degree in communication and informatin system both from University of Science and Technology of China (USTC) in 2002 and 2007, respectively. Now he is an associate professor in the School of Software of Dalian University of Technology (DUT). He is a member of IEEE and China Computer Federation (CCF). His research interests include wireless network, network analysis and network security.
Lei Wang is currently a full professor, and the Director of Graduate Education of the School of Software, Dalian University of Technology, China. He received his B.S., M.S. and Ph.D. from Tianjin University, China, in 1995, 1998, and 2001, respectively. He was a Member of Technical Staff with Bell Labs Research China (2001-2004), a senior researcher with Samsung, South Korea (2004-2006), a research scientist with Seoul National University (2006-2007), and a research associate with Washington State University, Vancouver, WA, USA (2007-2008). His research interests involve wireless ad hoc network, sensor network, social network and network security. He has published 60+ papers and the papers have 600+ citations.
Lei Shu (M’07) received Ph.D. degree from National University of Ireland, Galway, Ireland, in 2010. Until March 2012, he was a Specially Assigned Researcher in Department of Multimedia Engineering, Graduate School of Information Science and Technology, Osaka University, Japan. Since October 2012, he joined Guangdong University of Petrochemical Technology, China as a full professor. His research interests include: Wireless Sensor Networks, Multimedia Communication, Middleware, Security, and Fault Diagnosis. He has published over 200 papers in related conferences, journals, and books. His current H-index is 17. He had been awarded theGlobecom 2010 and ICC 2013 Best Paper Award. He is serving as Editor in Chief for EAI Endorsed Transactions on Industrial Networks and Intelligent Systems, and associate editors for a number of famous international journals.
References
Haykin S. 2005 “Cognitive radio: brain-empowered wireless communications” Selected Areas in Communications, IEEE Journal on Article (CrossRef Link) 23 (2) 201 - 220    DOI : 10.1109/JSAC.2004.839380
Southwell R. , Huang J. , Liu X. 2012 “Spectrum mobility games” IEEE in Proc. of INFOCOM, 2012 Proceedings IEEE Article (CrossRef Link) 37 - 45
Niyato D. , Hossain E. , Han Z. 2009 “Dynamics of multiple-seller and multiple-buyer spectrum trading in cognitive radio networks: A game theoretic modeling approach” Mobile Computing, IEEE Transactions on Article (CrossRef Link) 8 (8) 1009 - 1022    DOI : 10.1109/TMC.2008.157
Malanchini I. , Cesana M. , Gatti N. 2009 “On spectrum selection games in cognitive radio networks” IEEE in Proc. of Global Telecommunications Conference 2009, GLOBECOM 2009 Article (CrossRef Link) 1 - 7
“Microsoft research whitespacefinder.” Available: Website
Roberts J. W. 2004 “Internet traffic, qos, and pricing” Proceedings of the IEEE Article (CrossRef Link) 92 (9) 1389 - 1399    DOI : 10.1109/JPROC.2004.832959
Akyildiz I. F. , Lee W.-Y. , Vuran M. C. , Mohanty S. 2008 “A survey on spectrum management in cognitive radio networks” Communications Magazine IEEE Article (CrossRef Link) 46 (4) 40 - 48    DOI : 10.1109/MCOM.2008.4481339
Liang Y.-C. , Chen K.-C. , Li G. Y. , Mahonen P. 2011 “Cognitive radio networking and communications: An overview” Vehicular Technology, IEEE Transactions on Article (CrossRef Link) 60 (7) 3386 - 3407    DOI : 10.1109/TVT.2011.2158673
Akyildiz I. F. , Lee W.-Y. , Vuran M. C. , Mohanty S. 2006 “Next generation/dynamic spectrum access/cognitive radio wireless networks: a survey” Computer Networks Article (CrossRef Link) 50 (13) 2127 - 2159    DOI : 10.1016/j.comnet.2006.05.001
Wang L.-C. , Wang C.-W. 2008 “Spectrum handoff for cognitive radio networks: Reactive-sensing or proactive-sensins?” IEEE International, IEEE in Proc. of Performance, Computing and Communications Conference 2008, IPCCC 2008 Article (CrossRef Link) 343 - 348
Gao L. , Wang X. , Xu Y. , Zhang Q. 2011 “Spectrum trading in cognitive radio networks: A contract-theoretic modeling approach” Selected Areas in Communications, IEEE Journal on Article (CrossRef Link) 29 (4) 843 - 855    DOI : 10.1109/JSAC.2011.110415
Wang B. , Wu Y. , Liu K. 2010 “Game theory for cognitive radio networks: An overview” Computer Networks Article (CrossRef Link) 54 (14) 2537 - 2561    DOI : 10.1016/j.comnet.2010.04.004
Chen X. , Huang J. 2012 “Game theoretic analysis of distributed spectrum sharing with database” IEEE in Proc. of Distributed Computing Systems (ICDCS) 2012 IEEE 32nd International Conference on Article (CrossRef Link) 255 - 264
DaSilva L. A. 2000 “Pricing for qos-enabled networks: A survey” Communications Surveys & Tutorials IEEE Article (CrossRef Link) 3 (2) 2 - 8    DOI : 10.1109/COMST.2000.5340797
Wang S. , Zhang J. , Tong L. 2010 “Delay analysis for cognitive radio networks with random access: A fluid queue view” IEEE in Proc. of INFOCOM 2010 Proceedings IEEE Article (CrossRef Link) 1 - 9
Niyato D. , Hossain E. 2008 “Competitive pricing for spectrum sharing in cognitive radio networks: Dynamic game, inefficiency of nash equilibrium, and collusion” Selected Areas in Communications, IEEE Journal on Article (CrossRef Link) 26 (1) 192 - 202    DOI : 10.1109/JSAC.2008.080117
Zhang C. , Wang X. , Li J. 2009 “Cooperative cognitive radio with priority queueing analysis” IEEE in Proc. of Communications 2009(ICC’09) IEEE International Conference on Article (CrossRef Link) 1 - 5
Key P. B. , McAuley D. R. 1999 “Differential qos and pricing in networks: Where flow control meets game theory” in Software IEE Proceedings IET Article (CrossRef Link) 146 (1) 39 - 43    DOI : 10.1049/ip-sen:19990154
Swami S. , Ghosh C. , Dhekne R. P. , Agrawal D. P. , Berman K. A. 2008 “Graph theoretic approach to qos-guaranteed spectrum allocation in cognitive radio networks” IEEE International. IEEE in Proc. of Performance Computing and Communications Conference 2008(IPCCC 2008) Article (CrossRef Link) 354 - 359
Wang F. , Krunz M. , Cui S. 2008 “Price-based spectrum management in cognitive radio networks” Selected Topics in Signal Processing, IEEE Journal of Article (CrossRef Link) 2 (1) 74 - 87    DOI : 10.1109/JSTSP.2007.914877
Fabrikant A. , Papadimitriou C. , Talwar K. 2004 “The complexity of pure nash equilibria” ACM in Proc. of Proceedings of the thirty-sixth annual ACM symposium on Theory of computing Article (CrossRef Link) 604 - 612
Daskalakis C. , Goldberg P. W. , Papadimitriou C. H. 2006 “The complexity of computing a nash equilibrium” ACM in Proc. of Proceedings of the thirty-eighth annual ACM symposium on Theory of computing Article (CrossRef Link) 71 - 78
Chien S. , Sinclair A. 2011 “Convergence to approximate nash equilibria in congestion games” Games and Economic Behavior Article (CrossRef Link) 71 (2) 315 - 327    DOI : 10.1016/j.geb.2009.05.004
Vöcking B. , Aachen R. 2006 “Congestion games: Optimization in competition” Kings College Publications in Proc. of Proceedings of the 2nd Algorithms and Complexity in Durham Workshop London Article (CrossRef Link) 9 - 20
Feldmann A. E. , R#168;oglin H. , V#168;ocking B. 2008 “Computing approximate nash equilibria in network congestion games” Structural Information and Communication Complexity. Springer Article (CrossRef Link) 209 - 220
Southwell R. , Huang J. 2012 “Convergence dynamics of resource-homogeneous congestion games” Game Theory for Networks Springer Article (CrossRef Link) 281 - 293
Kim T. H. , Choi S. 2006 “Priority-based delay mitigation for event-monitoring ieee 802.15. 4 lr-wpans” Communications Letters IEEE Article (CrossRef Link) 10 (3) 213 - 215    DOI : 10.1109/LCOMM.2006.1603388
Yaghmaee M. H. , Adjeroh D.A. 2009 “Priority-based rate control for service differentiation and congestion control in wireless multimedia sensor networks” Computer Networks Article (CrossRef Link) 53 (11) 1798 - 1811    DOI : 10.1016/j.comnet.2009.02.011
Wang C. , Sohraby K. , Lawrence V. , Li B. , Hu Y. 2006 “Priority-based congestion control in wireless sensor networks” IEEE in Proc. of Sensor Networks, Ubiquitous, and Trustworthy Computing 2006 IEEE International Conference on vol. 1, Article (CrossRef Link) 8 -
Karakostas G. 2002 “Faster approximation schemes for fractional multi-commodity flow problems” in Proc. of Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics Article (CrossRef Link) 166 - 173
Li H. 2010 “Multi-agent q-learning for competitive spectrum access in cognitive radio systems” IEEE in Proc. of Fifth IEEE Workshop on Networking Technologies for Software Defined Radio (SDR) Networks Article (CrossRef Link) 1 - 6