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 multiobjective decision criterion for each access point. Second, a bargaining strategy selection algorithm is developed for the dynamic bandwidth reallocation. 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.
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 IPbased infrastructure, which enables the support of applications in a costeffective 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 reallocation 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 selfregarding 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 feedbackbased 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 higherlevel decisionmaker, who is referred to as a leader, makes his decisions by considering the possible reactions of followers. Many lowerlevel decisionmakers, 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 multiobjective 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 wellbalanced network performance under widely different and diversified traffic load situations. The principle novelty of the proposed scheme is its selfadaptability for network dynamics, feasibility in providing a desirable solution and effectiveness for realistic wireless network operations.
Recently, several network resource management schemes – the
Perlink Threshold based Bandwidth Allocation
(
PTBA
) scheme
[6]
and the
Energyefficient 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 perlink 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 energyefficient 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. Multiobjective 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}
...
AP_{i}
...
AP_{n}
}) 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 fairefficient 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 (
F_{b}
and
F_{u}
) 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
F_{b}
(
i
) and
F_{u}
(
i
) are defined as
where
Pr_{i}
is the call blocking probability and
ω_{i}
(0 <
ω_{i}
< 1) is a control parameter of the sensitivity to the
Pr_{i}
.
B
(
i
) and
B_{c}
(
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
F_{b}
and
F_{u}
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
F_{b}
and
F_{u}
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.
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.
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 online 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
Pr_{i}
and the
γ
_{2}
is defined as 1 
γ
_{1}
. Therefore, by using the realtime online monitoring, the system can be more responsive to current network conditions. According to (2) and (3), the multiobjective utility function (
U_{mo}
(
i
)) of the AP
i
is given by
Based on each AP’s
U_{mo}
, we can estimate the outcome differentials among APs. Finally, the
Outcome Differential Level
(
ODL
) among APs is obtained as follows.
 B. Adaptable Bargaining Strategy Selection Method
During wireless network operations, the role of CP is to allocate bandwidth for each AP. To get a fairefficient bandwidth allocation, we develop a new bandwidth reallocation 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 reallocation rule (
).
consists of four rules
= {ƒ
_{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.
The solution set of all possible combinations of bandwidth allocation represents the game feasible set A.
● ƒ
_{2}
 KalaiSmorodinsky 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, selfinterested 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 maxmin solution.
● ƒ
_{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:
● ƒ
_{4}
 Egalitarian Bargaining Solution (EBS)
[4]
: This bargaining solution follows the maxmin effectiveness concept:
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 reallocation rule to obtain a fairefficient 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 benefitbased 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
at time
t
is modified as a weighted average of these two quantities.
where
is the currently obtained utility of
k
^{th}
α
value and
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
and
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
. In this case, a lower value of
η
is more suitable. However, if traffic distribution is nonuniform, due to temporal and spatial traffic fluctuations, the utility estimation should strongly depend on the recent utility, i.e., on
. 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 online decision problem. In the proposed algorithm,
η
is dynamically adjusted as follows.
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
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
is defined as follows.
According to the
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 stepbystep feedback manner, control parameters are eventually obtained for the fairefficient 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 feedbackbased 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 fairefficient bandwidth allocation solution for the network systems is eventually obtained.
Step 8:
Under widely diverse network environments, the CP and APs are selfmonitoring 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 realworld 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 timedriven approach, we partition the timeaxis 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
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.
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.
Bandwidth utilization.
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 reallocates 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 feedbackbased 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.
View Fulltext
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
94B
(1)
322 
325
DOI : 10.1587/transcom.E94.B.322
Garroppo R.G.
,
Giordano S.
,
Iacono D.
2009
“RadioAware Scheduler for WiMAX Systems Based on TimeUtility 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 DaeKyo
,
Kim Dongwoo
2013
“Optimal access point switching with perlink threshold under nonhomogeneous bandwidth allocation,”
Information and Communication Technology (ICoICT)
187 
191
Oh Hyeontaek
,
Lee Joohyung
,
Choi JunKyun
2013
“Energyefficient dynamic load distribution for heterogeneous access networks,”
ICT Convergence (ICTC)
18 
23
Kim Sungwook
2012
“Game theoretic Multiobjective routing scheme for wireless sensor networks,”
Ad Hoc & Sensor Wireless Networks
15
(24)
107 
125
Menasche D.S.
,
Figueiredo, E. D.R.
,
de Souzae Silva
2005
“An evolutionary gametheoretic approach to congestion control,”
Performance Evaluation
62
(14)
295 
312
DOI : 10.1016/j.peva.2005.07.028
Kim Sungwook
,
Varshney Pramod K.
2004
“An Integrated Adaptive BandwidthManagement Framework for QoSSensitive Multimedia Cellular Networks,”
IEEE Transactions on Vehicular Technology
53
(3)
835 
846
DOI : 10.1109/TVT.2004.825704