Advanced
Intervenient Stackelberg Game based Bandwidth Allocation Scheme for Hierarchical Wireless Networks
Intervenient Stackelberg Game based Bandwidth Allocation Scheme for Hierarchical Wireless Networks
KSII Transactions on Internet and Information Systems (TIIS). 2014. Dec, 8(12): 4293-4304
Copyright © 2014, Korean Society For Internet Information
  • Received : July 01, 2014
  • Accepted : October 08, 2014
  • Published : December 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Sungwook Kim

Abstract
In order to ensure the wireless connectivity and seamless service to mobile users, the next generation network system will be an integration of multiple wireless access networks. In a heterogeneous wireless access system, bandwidth allocation becomes crucial for load balancing to avoid network congestion and improve system utilization efficiency. In this article, we propose a new dynamic bandwidth allocation scheme for hierarchical wireless network systems. First, we derive a multi-objective decision criterion for each access point. Second, a bargaining strategy selection algorithm is developed for the dynamic bandwidth re-allocation. Based on the intervenient Stackelberg game model, the proposed scheme effectively formulates the competitive interaction situation between several access points. The system performance of proposed scheme is evaluated by using extensive simulations. With a simulation study, it is confirmed that the proposed scheme can achieve better performance than other existing schemes under widely diverse network environments.
Keywords
1. Introduction
W ireless multimedia communications have been greatly increased in the number of users, diversity of applications and interface technologies. Beyond 3G, future wireless networks evolve following an IP-based infrastructure, which enables the support of applications in a cost-effective and scalable way. IP provides compatibility while being independent of the bandwidth access technology creating a heterogeneous platform that incorporates existing second/third generation (2G/3G) cellular systems with emerging 4G technologies. To scale large wireless IP networks, configuring hierarchy is an essential element. In a hierarchical wireless network environment, an effective Quality of Service (QoS) mechanism can enable different services to provide enhanced user satisfaction [1] - [2] .
Nowadays, bandwidth demand is growing exponentially due to the increased new applications. However, wireless bandwidth is a naturally limited and scarce resource. In order to satisfy the increasing demands, it is essential to develop a new bandwidth allocation algorithm; efficient bandwidth management plays a critical role in determining network performance [1] - [3] . The problem of bandwidth allocation in heterogeneous wireless access networks have been extensively studied in previous works. However, the problem of bandwidth re-allocation among multiple users under dynamic network environment scenario has not been well studied, and few works consider the joint optimization of network utility, load status and user bandwidth allocation.
In wireless network systems, there are a number of interacting intelligent agents. Each agent makes behavioral choices in the context of a dynamic environment that is formed by the collective actions. To understand the behavior of self-regarding agents, game theory has some attractive features [3] . Game theory is a field of applied mathematics that provides an effective tool in modeling the interactions among independent agents. However, classical game theory makes the assumption that game players are perfectly rational. This supposition is too strong to implement in the real world game player. For the practical game operation, players should be modeled with bounded rationality [3] - [4] .
Based on the facts presented above, we propose a new bandwidth allocation scheme based on the feedback-based game theory. By adopting the intervenient Stackelberg game model, the proposed scheme is designed as an iterative feedback process approach. Initially, Stackelberg game was developed for a hierarchical game model based on two kinds of different decision makers; a leader and followers. Decision makers have their own hierarchy level, utility function and strategies. Therefore, they are forced to act according to their hierarchy level. One higher-level decision-maker, who is referred to as a leader, makes his decisions by considering the possible reactions of followers. Many lower-level decision-makers, who are referred to as followers, react dependently based on the decision of the leader while attempting to maximize their satisfaction. In general, this approach is a proper method for the best compromise in the presence of conflicting objectives [3] , [5] .
In the proposed scheme, the network operator observes the current network environments, estimates the prospective utility and adaptively updates the bandwidth allocation strategy as a leader. For the bandwidth allocation strategies, the methodology that we adopt is the bargaining solution. Bargaining solution is a field of cooperative game theory and an effective tool to achieve a mutually desirable solution with a good balance between efficiency and fairness. Until now, a lot of different bargaining solutions have been conducted. Among different kinds of bargaining solutions, the network operator selects the most effective bargaining solution according to the multi-objective decision criterion. As followers, access providers attempt to maximize their utility function in a distributed fashion. Access providers’ decisions are applied as the input to the operator’s control procedure. This interactive feedback approach can be used to make a logical, quantitative decision.
The important features of the proposed scheme are i) ability to maintain the bandwidth efficiency as high as possible, ii) ability to respond to the current network situations based on the real time information, iii) dynamically adjustable approach to maximize the network system performance, and iv) a well-balanced network performance under widely different and diversified traffic load situations. The principle novelty of the proposed scheme is its self-adaptability for network dynamics, feasibility in providing a desirable solution and effectiveness for realistic wireless network operations.
Recently, several network resource management schemes – the Per-link Threshold based Bandwidth Allocation ( PTBA ) scheme [6] and the Energy-efficient Dynamic Load Distribution ( EDLD ) scheme [7] - have been presented for the wireless network bandwidth allocation problem. The PTBA scheme investigates optimal switching technique between coordinated access providers. In the PTBA scheme, the per-link information between an access provider and the user is assumed available at a time, and it is compared with a predetermined threshold to determine either switching or staying. The EDLD scheme is developed as a novel dynamic energy-efficient load distribution algorithm for heterogeneous wireless networks. For an effective load distribution, the EDLD scheme is designed based on the simple greedy load distribution algorithm, which is inspired by the mathematical background of the Lagrangian algorithm. Compared to these schemes [6] - [7] , the proposed scheme attains better performance for wireless networks.
This paper is organized as follows. Section II presents the proposed algorithms in detail. In Section III, performance evaluation results are presented along with comparisons with the PTBA and the EDLD schemes proposed in [6] and [7] . Through simulation, we show the ability of proposed scheme to achieve high accuracy and promptness in hierarchical wireless network system environments. Finally, concluding remarks are given in Section IV.
2. Proposed Dynamic Bandwidth Allocation Algorithms
In this paper, we propose a new bandwidth allocation scheme for the hierarchical wireless network system. Based on the intervenient Stackelberg game model, the proposed scheme can obtain an effective solution through under the constantly changing network environment. This is a suitable approach for the practical implementation.
- A. Multi-objective Decision Criterion
In a wireless network system, there are multiple Channel Providers (CPs) and Access Providers (APs). As a network operator, the CP allocates the available bandwidth to APs and each AP leases the bandwidth among End Users (EUs) who registered that AP. In this paper, we formalize the bandwidth management algorithm abstractly in terms of an intervenient Stackelberg game model. In our game model, there are a single CP as a leader, n APs ({ AP 1 ... APi ... APn }) as followers and m EUs ( n << m ). From the viewpoint of CP, the effective bandwidth allocation among APs is a very important factor in order to obtain fair-efficient network performance. To satisfy this goal, one of major concerns is to design a utility function for each AP. In this paper, we define two utility functions ( Fb and Fu ) by using call blocking probability and bandwidth utilization information. Based on the adaptive online manner, these functions can dynamically estimate the current state of APs. For the AP i , the Fb ( i ) and Fu ( i ) are defined as
PPT Slide
Lager Image
where Pri is the call blocking probability and ωi (0 < ωi < 1) is a control parameter of the sensitivity to the Pri . B ( i ) and Bc ( i ) are the total amount of allocated bandwidth and the currently used bandwidth in the AP i , respectively. To get the proper combination of the Fb and Fu functions, we use the Modified Game Theory (MGT) method. In general, the MGT method may be concluded to provide the best compromise in the presence of different control functions [8] . By practically applying the MGT, the Fb and Fu are transformed into a single objective function. To obtain this single function, the procedure is defined as follows. First, a normalized bargaining model ( NBM ( i )) for the AP i is constructed to compare the relative effectiveness.
PPT Slide
Lager Image
This bargaining model gives a normalized indication value (0 ≤ NBM ( i ) ≤ 1) as to how far a function is from its worst value. Therefore, the solution is optimized by maximizing the bargaining model [8] . Second, a weighted average ( WA ( i )) for the AP i is formulated as follows.
PPT Slide
Lager Image
The parameter γk ( k = 1 or 2) controls the relative weights given to the blocking probability ( k = 1) and bandwidth utilization ( k = 2). Under diverse network environments, the fixed values for γk cannot effectively adapt to the changing conditions. In this paper, we treat it as an on-line decision problem and adaptively modify γk value. When the blocking probability of the AP i is high, we can put more emphasis on the function ƒ 1 ( i ). In this case, a higher value of γ 1 is more suitable. Otherwise, the WA ( i ) should strongly depend on the bandwidth utilization. In this case, a higher value of γ 2 is more suitable. In this work, the value of γ 1 is dynamically adjusted based on the current call blocking probability of the corresponding AP; e.g., the γ 1 value of the AP i is Pri and the γ 2 is defined as 1 - γ 1 . Therefore, by using the real-time online monitoring, the system can be more responsive to current network conditions. According to (2) and (3), the multi-objective utility function ( Umo ( i )) of the AP i is given by
PPT Slide
Lager Image
Based on each AP’s Umo , we can estimate the outcome differentials among APs. Finally, the Outcome Differential Level ( ODL ) among APs is obtained as follows.
PPT Slide
Lager Image
- B. Adaptable Bargaining Strategy Selection Method
During wireless network operations, the role of CP is to allocate bandwidth for each AP. To get a fair-efficient bandwidth allocation, we develop a new bandwidth re-allocation algorithm based on the intervenient Stackelberg game model; it can be applicable and useful in a system with a frequently changing situation. In the proposed algorithm, the CP (i.e., an intervenient leader) monitors APs (i.e., followers) and acts explicitly, which can be programmed simply according to the bandwidth re-allocation rule (
PPT Slide
Lager Image
).
PPT Slide
Lager Image
consists of four rules
PPT Slide
Lager Image
= {ƒ 1 , ƒ 2 , ƒ 3 , ƒ 4 }, which are developed based on the different bargaining strategies.
● ƒ 1 - Nash Bargaining Solution (NBS) [4] : the main feature of NBS is to achieve a mutually desirable solution with a good balance between efficiency and fairness. NBS is obtained as follows.
PPT Slide
Lager Image
The solution set of all possible combinations of bandwidth allocation represents the game feasible set A.
● ƒ 2 - Kalai-Smorodinsky Bargaining Solution (KSBS) [4] : the main feature of KSBS is that the increasing of bargaining set size in a direction favorable to a specific player always benefits that player. Therefore, self-interested AP also can be satisfied. In KSBS, the ideal payoff ( NBM ( i ) max ) for each AP is the maximum effectiveness in the ideal situation. KSBS is obtained as a weighted max-min solution.
PPT Slide
Lager Image
● ƒ 3 - Utilitarian Bargaining Solution (UBS) [4] : This bargaining solution does not consider fairness issues among APs. In the point view of efficiency, only the sum of APs’ effectiveness is maximized. This solution can be formulated as the following:
PPT Slide
Lager Image
● ƒ 4 - Egalitarian Bargaining Solution (EBS) [4] : This bargaining solution follows the max-min effectiveness concept:
PPT Slide
Lager Image
At the initial time, the available bandwidth is equally divided for APs. After the initialization time period, the CP periodically observes the current AP situations and adaptively selects a bandwidth re-allocation rule to obtain a fair-efficient solution. In the proposed algorithm, rule mapping conditions are employed for the adaptive bargaining strategy selection;
  • i)If the averageBc(Bave) of APs is less than the predefined bandwidth utilization (Bp), ƒ3is selected to improve the system effectiveness.
  • ii)If (Bave>Bp) and (ODL<α), ƒ4is selected to equally share the benefits.
  • iii)If (Bave>Bp) and (α≤ODL<β), ƒ1is selected to fairly share the mutual benefits accruing from cooperation.
  • iv)If (Bave>Bp) and (β≤ODL≤ 1), ƒ2is selected to obtain a benefit-based fair solution.
In rule mapping conditions, α and β are used as thresholds for the bargaining strategy selection. In this work, α ∈ Г α = {0.1, 0.2, 0.3, 0.4} and β ∈ Г β = {0.6, 0.7, 0.8, 0.9} values are decided dynamically. To practically decide these values, we should be responsive to the current network information. First, based on the utility history ( A_WA ) and recent utility changes ( C_WA ), the proposed algorithm estimates the network utility of the selected α value. If the current α value is the k th element in Г α , the accumulated utility of k th α value
PPT Slide
Lager Image
at time t is modified as a weighted average of these two quantities.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the currently obtained utility of k th α value and
PPT Slide
Lager Image
is the accumulated utility for the next time interval. Therefore, A_WAα [‧] is recursively updated during the network operation rounds. The parameter η controls the relative weights given to recent and past estimation histories in our decision. Under dynamic network environments, a fixed value of η cannot effectively adapt to the changing network conditions. Therefore, we dynamically modify η to make it more responsive to the current network conditions. When the difference between
PPT Slide
Lager Image
and
PPT Slide
Lager Image
is small, the value of η makes little difference on network performance. But under dynamic network changing situation, the value of η can affect the performance significantly. In the proposed algorithm, if the traffic is uniformly distributed over the time, we can put more emphasis on the utility history, i.e., on
PPT Slide
Lager Image
. In this case, a lower value of η is more suitable. However, if traffic distribution is non-uniform, due to temporal and spatial traffic fluctuations, the utility estimation should strongly depend on the recent utility, i.e., on
PPT Slide
Lager Image
. In this case, a higher value of η is more suitable. Therefore, we must decide on the value of η by considering the current network traffic conditions and by treating it as an on-line decision problem. In the proposed algorithm, η is dynamically adjusted as follows.
PPT Slide
Lager Image
To adaptively select the α value in Г α , we define the vector V α [ k ] where 1 ≤ k ≤ |Г α |. Based on the A_WA (‧) value, V α [ k ] = 1 where
PPT Slide
Lager Image
and the remaining elements V α [ l ] 1 ≤ l ≤ |Гα|,l≠k equal to 0. For the ( t +1) th operation round, the selection probability of k th α value
PPT Slide
Lager Image
is defined as follows.
PPT Slide
Lager Image
According to the
PPT Slide
Lager Image
distribution in Equation (12), α value is stochastically given to maximize the network utility. Second, the β value is also adaptively decided in the same manner as used to decide α value. In this step-by-step feedback manner, control parameters are eventually obtained for the fair-efficient bandwidth allocation solution.
- C. The Main Steps of Proposed Bandwidth Allocation Algorithms
In this work, a new hierarchical network bandwidth allocation scheme is developed based on the intervenient Stackelberg game model. Under dynamically changing wireless network environments, the proposed scheme dynamically adapts the amount of the allocated bandwidth for each APs. The major objective is to maximize the network system performance while providing a high bandwidth utilization. As a leader, a CP can dynamically update the bandwidth allocation strategy. Among four different bargaining solutions, the most effective bargaining solution is selected to satisfy the system objective. As followers, APs attempt to maximize their utility function in an entirely distributed fashion. Therefore, control decisions are coupled with each other in a hierarchical interaction relationship. This feedback-based iterative process continues until a satisfactory solution is obtained. Traditionally, game models have only focused on investigating which decisions are made or what decisions should be made [9] . However, the proposed game model investigates how decisions are made in a distributed manner. In addition, the proposed scheme has polynomial time complexity for control decisions in the bargaining and negotiation process. It can dramatically reduce the computational complexity and overheads; it is suitable approach in real world network operations. The whole proposed algorithm is summarized as follows.
Step 1: At the initial time, the allocated bandwidth in each AP is equally divided. This starting guess guarantees that each AP enjoys the same benefit at the beginning of the system operation.
Step 2: Every time period, each AP utilizes the allocated bandwidth and estimates individually his payoff according to (1)-(3).
Step 3: Each time iteration, the CP obtains the ODL value according to (4)-(5), and dynamically selects the next bargaining solution through the bargaining strategy selection rules.
Step 4: After selecting the most adaptable bargaining strategy, the available bandwidth is allocated for each AP by using (6)-(9).
Step 5: To adaptively respond to the current network situations, the α , β and η control parameters in the bargaining strategy selection rules are dynamically adjusted according to (10) - (12).
Step 6: The CP and APs repeat computations interactively until the network system converges to a stable state.
Step 7: If the selected bargaining solution is not changed, a fair-efficient bandwidth allocation solution for the network systems is eventually obtained.
Step 8: Under widely diverse network environments, the CP and APs are self-monitoring constantly for the next iterative feedback processing; proceeds to Step 2.
3. Performance Evaluation
In this section, the effectiveness of the proposed scheme is validated through simulation. With a simulation study, the performance superiority of our proposed scheme can be confirmed. There are other performance analysis methods: theoretical or numerical analysis. However, these methods have to be limited in scope - limited modeling possibility for dynamic behavior. Therefore, for complex and complicated algorithms, such as our proposed scheme, no capability makes tractable the theoretical and numerical model without many simplifications, which cannot provide precise performance evaluation. In contrast to these methods, a simulation analysis allows more complex realistic modeling for one real-world system [10] . Therefore, in this paper, we propose a simulation model for the performance evaluation of the proposed scheme. The assumptions implemented in simulation model are as follows.
  • ● The simulated system consists of one CP and 4 APs (n= 4).
  • ● In order to implement the time-driven approach, we partition the time-axis into equal intervals of lengthunit_time.
  • ● The new service request process from the end users is Poisson with rateρ(services/unit_time/AP). The range of offered load was varied from 0 to 3.
  • ● Network system performance measures are plotted as a function of the offered load.
  • ● The total bandwidth amount is 50 Mbps and the predefined bandwidth utilization (Bp) is set to 0.5.
  • ● Theωvalue for each AP is randomly selected from [0.3, 0.6].
  • ● At the initial iteration (t= 1), the selection probabilityis equally distributed.
  • ● In order to represent various multimedia data, eight different traffic types are assumed based on connection duration, bandwidth requirement. They are generated with equal probability.
  • ● The durations of calls are exponentially distributed with different means for different multimedia traffic types.
Performance measures obtained through simulation are Service Blocking Probability (SBP), bandwidth utilization and normalized network throughput, etc. These performance measures obtained on the basis of 100 simulation runs are plotted as a function of the offered load (services/ unit_time /AP) ρ . Table 1 shows the multimedia traffic types and network system parameters used in the simulation. With multiple classes of traffic, each has different traffic characteristics.
Applications and system parameters used in the simulation experiment
PPT Slide
Lager Image
Applications and system parameters used in the simulation experiment
Recently, the PTBA and EDLD schemes [6] - [7] have been published and introduced unique challenges for the bandwidth allocation problem. Using a simulation model, we compare the performance of the proposed scheme with these existing schemes [6] - [7] to confirm the superiority of the proposed approach.
Fig. 1 shows the performance comparison for all types of traffic services in terms of SBP. As the service request rate ( ρ ) increases, the average amount of unused bandwidth decreases. Thus, new service requests are likely to be rejected and SBP increases. From low to high network traffic load intensities, the proposed scheme can provide the excellent SBP than other schemes.
PPT Slide
Lager Image
Service Blocking Probability (SBP) of network system.
Fig. 2 shows the bandwidth utilization of each scheme. To maximize the network performance, bandwidth utilization is an important performance metric. It is shown that the bandwidth utilization is virtually the same for all the schemes. However, under various the service arrival rate, the bandwidth utilization of the proposed scheme is better than the other schemes. In Fig. 3 , the comparison of the normalized network throughput is presented. It is measured as the ratio of the successfully serviced data amount. Due to the inclusion of the adaptive interactive feedback approach, we can observe that the proposed scheme gains the better throughput. It can guarantee the better network performance during network operations.
PPT Slide
Lager Image
Bandwidth utilization.
PPT Slide
Lager Image
Normalized network throughput.
From the simulation results in Figs. 1 - 3 , it can be seen that the proposed scheme, in general, performs better than the other existing schemes from low to heavy traffic load distributions. Based on the intervenient Stackelberg game model, the proposed scheme effectively formulates the competitive interaction situation for the hierarchical wireless network system. In addition, due to the adaptive feedback approach, the proposed scheme constantly monitors the current network conditions and can balance appropriate network performance while other schemes [6] - [7] cannot offer such an attractive network performance.
4. Summary and Conclusions
In order to provide the high quality of wireless connectivity and seamless service to end users, the next generation networks will be an integration of multiple wireless access networks. This will give rise to a heterogeneous wireless access system where bandwidth allocation becomes crucial for load balancing to avoid network congestion and improve system resource utilization efficiency. In this paper, a new dynamic bandwidth allocation scheme is proposed. Based on the intervenient Stackelberg game model, the proposed scheme iteratively estimates the current network situations and adaptively re-allocates the available bandwidth for APs. It features quantitative rule selection and is able to keep network load balance through dynamic system reconfiguration. In addition, our proposed feedback-based adaptive approach can significantly improve network performance. An extensive performance evaluation has been performed and the numerical results have shown that the proposed scheme can provide an effective bandwidth allocation for hierarchical wireless network systems.
BIO
Sungwook Kim received the BS, MS degrees in computer science from the Sogang University, Seoul, in 1993 and 1995, respectively. In 2003, he received the PhD degree in computer science from the Syracuse University, Syracuse, New York, supervised by Prof. Pramod K. Varshney. He has held faculty positions at the department of Computer Science of ChoongAng University, Seoul. In 2006, he returned to Sogang University, where he is currently a professor of department of Computer Science & Engineering, and is a research director of the Internet Communication Control research laboratory (ICCLab.). His research interests include resource management and game theory for network design applications.
References
Jang Ingook , Pyeon Dohoo , Kim Sunwoo , Yoon Hyunsoo 2013 “A Survey on Communication Protocols for Wireless Sensor,” Networks, Journal of Computing Science and Engineering 7 (4) 231 - 241    DOI : 10.5626/JCSE.2013.7.4.231
Kim KwangSik , Uno Shintaro , Kim MooWan 2010 “Adaptive QoS Mechanism for Wireless Mobile Network,” Journal of Computing Science and Engineering 4 (2) 153 - 172    DOI : 10.5626/JCSE.2010.4.2.153
Kim Sungwook 2011 “An Online Network Price Control Scheme by Using Stackelberg Game Model,” IEICE Transactions 94-B (1) 322 - 325    DOI : 10.1587/transcom.E94.B.322
Garroppo R.G. , Giordano S. , Iacono D. 2009 “Radio-Aware Scheduler for WiMAX Systems Based on Time-Utility Function and Game Theory,” IEEE GLOBECOM 2009 1 - 6
Wang B. , Han Z. , Ray Liu K. J. 2006 “Stackelberg game for distributed resource allocation over multiuser cooperative communication networks,” in Proc. of IEEE Global Telecommunications Conference 1 - 5
Jeong Dae-Kyo , Kim Dongwoo 2013 “Optimal access point switching with per-link threshold under nonhomogeneous bandwidth allocation,” Information and Communication Technology (ICoICT) 187 - 191
Oh Hyeontaek , Lee Joohyung , Choi JunKyun 2013 “Energy-efficient dynamic load distribution for heterogeneous access networks,” ICT Convergence (ICTC) 18 - 23
Kim Sungwook 2012 “Game theoretic Multi-objective routing scheme for wireless sensor networks,” Ad Hoc & Sensor Wireless Networks 15 (2-4) 107 - 125
Menasche D.S. , Figueiredo, E. D.R. , de Souzae Silva 2005 “An evolutionary game-theoretic approach to congestion control,” Performance Evaluation 62 (1-4) 295 - 312    DOI : 10.1016/j.peva.2005.07.028
Kim Sungwook , Varshney Pramod K. 2004 “An Integrated Adaptive Bandwidth-Management Framework for QoS-Sensitive Multimedia Cellular Networks,” IEEE Transactions on Vehicular Technology 53 (3) 835 - 846    DOI : 10.1109/TVT.2004.825704