Congestion Control in 4G Wireless Networks Using Coalition Game

Published Online June 2012 in MECS

The increasing demands and requirements for wireless communication systems have led to the design of heterogeneous wireless systems. In continuous development of mobile environments, the major service providers in the wireless market have planned to include 4th generation (4G) mobile technology. 2G and 3G are well established as the mainstream mobile technologies around the world. 4G wireless networks are achieving some confidence.

In today's Internet, real-time applications such as VoIP, videoconferencing and on-line gaming mostly use RTP over UDP or UDP alone to transport data. Because these protocols are unresponsive to congestion events, they will cause congestion in the Internet. In order to make it possible that real-time applications are widely adopted, common congestion control mechanisms are expected to be deployed. Also, a variety of wireless and wired technologies have been developed in the past years. The vision for the next generation mobile communication networks focuses on these technologies with handovers between them occurring seamlessly. New solutions are required so that the network stability is maintained even when conditions vary abruptly. Further quality perceived by interactive real-time applications is not degraded by the congestion control mechanisms.

Solving the congestion problem is not limited adding new resources or extending the capabilities of the existing resources. A large amount of theoretical and experimental work has been conducted to design stable congestion controls for high-speed heterogeneous networks. Some of the congestion control schemes are discussed below.

In the paper [1] authors have compared the feedbackbased to the reservation-based congestion control approach. The performance comparison made by evaluating some mechanisms with respect to Media Friendliness, Scalability and Dynamic Behavior. The paper [2] considers the potentially negative impacts of an increasing deployment of non-congestion-controlled besteffort traffic on the Internet. In the paper [3] author has described the main ideas behind some of the most important of router congestion feedback (RCF) approaches based on network-information sharing (NIS).

The purpose of paper [4] is to analyze and compare the different congestion control and avoidance mechanisms which have been proposed for TCP/IP protocols, namely: Tahoe, Reno, New-Reno, TCP Vegas and SACK. The paper [5] uses simulations to identify the benefits of adding selective acknowledgments (SACK) and selective repeat to TCP. Authors have compared Tahoe and Reno TCP with two modified versions of Reno TCP. Indirect TCP (or I-TCP), which is described in paper [6], is based on an indirect protocol model. In this approach, an end-to-end TCP connection between a fixed host and a mobile host is split into two separate connections: 1) a regular TCP connection between the fixed host and the mobility support router (base station) currently serving the mobile host and 2) a wireless TCP connection between the mobility support router and the mobile host. Use of the mobility support router (or indirection) at the transport layer allows special treatment of mobile hosts communicating over wireless links.

Authors proposed a new method called JetMax [7] and show that it admits a low-overhead implementation inside routers to indicate overshoot-free transient and steady state, tunable link utilization, and delay-insensitive flow dynamics. The paper [8] has introduced the concept of an effair (Metric for Congestion Control Evaluation) allocation. It is a dynamic ideal allocation that specifies optimal efficiency and fairness at every timescale. The new congestion-control and error-recovery mechanisms in TCP Santa Cruz [9] are defined. It is also shown that TCP Santa Cruz prevents the congestion using congestion window.

In paper [10] authors describe heterogeneous congestion control protocols. It reacts to different pricing signals sharing the same network. They prove the existence of equilibrium under mild assumptions. In paper [11], an ECN (explicit congestion notification) algorithm has been proposed to avoid the throughput degradation due to unnecessary packet drops. The idea of ECN was to notify sending hosts explicitly of congestion occurrence in the network instead of packet drops. A new scheme [12] is proposed for Round Trip Time (RTT) estimation, which is defined by combining Kalmanlter and a change detection algorithm (CUSUM). It is observed that on real data this algorithm provides estimates of significantly better accuracy as compared to the RTT estimator currently used in TCP.

In paper [13] author presents a novel delay-based congestion control algorithm. The main features of the proposed solution include: 1) low standing queues and delay in homogeneous environments, 2) fair coexistence of delay- and loss-based flows in heterogeneous environments, 3) delay-based flows behave as loss-based flows when loss-based flows are present in the network. The paper [14] extends the study with analyzing the optimality and stability of heterogeneous networks. They present a framework to help understand equilibrium properties of heterogeneous networks. The paper [15] describes a framework for further enhancements of the traditional IP based protocol stack to meet current and future requirements.

In paper [16] authors have explained about design of the multimedia transport protocol in heterogeneous wired-cum-wireless environment. A window based exponentially weighted moving average (EWMA) filter is introduced to achieve stability and flexibility at the same time. New implementation of TCP called TCP Santa Cruz [17] is designed to work with path asymmetries, out-oforder packet delivery, and networks with lossy links. This TCP Santa Cruz are based on estimates of delay along the forward path. The paper [18] discusses two protocols R²CP, and RCP and feasibility of RCP protocols when applied to manage power efficiently and to control congestion on heterogeneous wireless network.

In paper [19] authors present new queue length based Internet congestion control protocol. The control objective is to regulate the queue size at each link so that it tracks a reference queue size chosen by the designer. In paper [20] authors proposed Enhanced TCP congestion control scheme with Round Trip Time (RTT) inflation and the measured-RTT of the new network for the seamless soft vertical handover. In paper [21] a novel analytical framework for modeling and quantifying the performance of window controlled multimedia flows is defined. The framework captures the traffic characteristics of window-controlled flows and is applicable to various wireless links and packet transmission schemes.

In paper [22] author proposed a new protocol to improve TCP/IP suite protocols. This new protocol addresses the limitation of TCP/IP suite so that it can work on both cellular network and Wi-Fi network simultaneously. The papers [23] [24] have discussed about various congestion control algorithms. It uses network awareness as a criterion to categorize different approaches. These papers give a brief survey of major congestion control mechanisms.

A key design challenge in congestion management is to decide which network should be cooperative to provide service to vertical handoff call and in which cooperative group it will be, especially when the network nodes act in a rational and selfish manner, i.e., in a way to maximize their own performance. Thus solution to congestion control in 4G wireless networks is reduced to coalition formation. Coalition game theory can be used to analyze behavior in decentralized and self-organizing networks. Game theory models the actions and choice of strategies of self-interested players in order to capture the interaction of players in a communication networks. A game consists of A set of players N={1,2…n}.

A set of utility functions, one for each player. The utility function u assigns a numerical value to the elements of the action set A; for actions x, y e A if u(x) > u(y) then x must be at least preferred as y.

In a coalitional game (N, u) with N players, the utility of a coalition is determined by a characteristic function u: 2N ^ R, which applies to coalitions of players. For a coalition S c N, u(S) depends on the members of S. Most coalitional games have transferable utility (TU) viz. utility of a coalition can be distributed between the coalition members according to some notion of fairness. However, for many scenarios rigid restrictions are needed on the distribution of the utility. These games are known as coalitional games with nontransferable utility (NTU). In an NTU game, the payoff for each player in a coalition S depends on the actions selected by the players in S. The core of the coalitional game (N, u) is the set of coalitions that guarantees that no player has an incentive to leave N to form another coalition.

Definition: A collection of coalitions, denoted S, is defined as the set S={S 1 …S k } of mutually disjoint coalitions S i c N. If the collection spans all the players of N that is “' ^{1 S} = ^N, the collection is a partition of N.

Example: Consider a 4G congestion control game (N, u) where N ={WiFi, WiMAX, UMTS}. The players, on their own have no congestion control because vertical handoff will not be initiated. Hence u({WiFi})= u({WiMAX })= u({UMTS}) =0. Any 2-players coalition reduces two thirds of the congestion and hence, u({WiFi, WiMAX })= u({WiFi, UMTS })= u({WiMAX, UMTS})=2/3. The grand coalition reduces the whole congestion and thus u({WiFi, WiMAX ,UMTS}) =1.

In this paper, we investigate the problem of congestion management in a heterogeneous network environment by using cooperative games. Formulating the problem as a cooperative game allows individual networks to cooperate with each other by forming coalitions. Therefore the objective of each network is to maximize the overall objective of the heterogeneous network and try to reduce the congestion in the network. Every member of the coalition manages congestion according its own operation constraints.

The rest of this paper is organized as follows. In section 2, our proposed model with coalitional game formulation is designed. Section 3 presents numerical analysis of the proposed algorithm. The paper finally concludes in section 4.

• II.    System Model and Coalition Game Formation

We consider a group of wireless networks in 4G M= {1,….N} where N is the total number of wireless networks. Source and destination wireless networks needs to be identified to initiate vertical handoff to manage congestion. The solution to congestion management in 4G wireless network is provided using coalition game formation. In this paper the proposed algorithm has been formulated as coalition game with the assumption that all wireless networks in 4G form coalition for minimizing their congestion. The decision coalition formation is formally represented as: D = [ M, {Ui},{Pi}] where M is the number of players, Ui denotes the utility and Pi represents the payoff function. For this game problem, the payoff function is referred to as the Nash equilibrium, which includes each player’s best strategy, where other players can choose the equilibrium strategy.

Generally there are ‘n’ number of wireless networks in 4G with congestion factor C f j : j=1,2,3…n. These wireless networks merge together or split to form coalition sets. The merging and splitting of coalition set based on congestion factor. Based on such a parametric definition, the proposed coalition game theory can be described as follows.

• A.    Players

Players include i=1, 2, 3 …. n number of wireless networks in 4G networks. These wireless networks cooperate with each other to form coalition sets of networks. Wireless networks in coalition initiate vertical handoff among them to minimize congestion.

• B.    Strategy

The strategy of each player is to maximize their payoff. The compensation is defined in terms of minimization of congestion in all wireless networks of 4G by initiating vertical handoff. To improve their performance, the wireless networks can decide to cooperate and form a group. i.e., a coalition S in which the vertical handoff initiated from source to target wireless networks.

• C.    Payoff

Payoff reflects the overall performance of the 4G network depending on the coalition formation. The coalition will be the Nash equilibrium with core. In core none of the players, subject to the other player’s current strategy, gains any benefit by changing their membership in coalition. The Nash equilibrium with core provides the lowest congestion control by the players. The algorithm is deduced as coalition game theory.

• D.    Utility function

It is of the interest for the coalition to take into account the goals: minimization of congestion control and maximization of payoff. Further it is needed to minimize the delays experienced by user data over the multiple networks. An exponential utility function to assign congestion factor (cf) to the networks given as follows.

c f = e di / gi

Where di is the packets dropped and gi is the packets generated for transmission in network i. The congestion factor is computed using the exponential cost function for each network. Based on the congestion factor, networks decide whether to allocate resource or not. We use the congestion factor to optimize network performance. Cost of utility function varies with the congestion factor.

Some wireless networks in 4G have a free bandwidth, whereas other wireless networks experience more congestion. Packets generated from applications can be routed through free bandwidth wireless networks, so that beneficial cost of all the networks increased as well as congestion in the networks get reduced. To decide traffic from which network can be routed by initiating vertical handoff and selection of target network to transfer handoff calls are difficult to realize. We can formulate this problem as a coalitional game. Let us call each congested wireless network as source and every other wireless network in coalition as a target. Assumptions made in this coalition formulation are as follows.

Assume that no one wishes to own more congested traffic. Wireless networks in 4G have different congestion factors: denote player i’s valuation of congestion factor by c f i .

Assume that there are at least one source and one target in coalition: assume also that some target network congestion factor is less than some source network congestion factor (i.e. for some target i and source j we have c f i < c f j ), so that some vertical handoff of call is mutually desirable and no two players have the same congestion factor (c f * c f ).

• E.    Nash equilibrium solution

We define an action of grand coalition to be stable if no coalition can break away and choose an action that all its members prefer. The set of all stable actions of the grand coalition is called the core, defined as follows.

Definition 1: Core of coalitional game: The core of a coalitional game is the set of actions a N of the grand coalition N such that no coalition has an action that all its members prefer to a N .

If a coalition S has an action that all its members prefer to some action aN of the grand coalition, we say that S can improve upon aN. Thus we may alternatively define the core to be the set of all actions of the grand coalition upon which no coalition can improve. In this coalition game, at the end core is formed with merge-and-split rule. After every period of time t the coalition assessed for possibility of merge and split rule. Thus we have core when no coalition break away to form another coalition. Thus core defines set of actions like initiating vertical handoff among members of the coalitions to improve the utility of the wireless networks. This in turn reduces the congestion in wireless networks.

• F.    Coalition Formation Rules and Algorithm

The coalition formation is dynamic process. The members joining to group and leaving from the group occurs periodically. In the initial stage it starts with few numbers of players to form coalition. As time elapses, the collection of coalitions S={S 1 ,….,S k } can merge into a larger coalition if merging yields a preferred collection. Similarly, a coalition would split into smaller coalitions if splitting yields a preferred collection. Coalitions will merge only if at least one member of coalition is able to strictly improve its individual utility through this merge (or split) without decreasing the other player’s utilities. Thus it is more beneficial to include merge-and-split rules in coalition formation algorithm.

Definition 1: Merge Rule: Merge any set of coalitions {S 1 ,    S 2 ,….    S k }    therefore {S 1 , S 2 ,….    S k }

k

^ { ^U j = j }(each S j is a coalition in S).

k

We construct a coalition formation algorithm based on merge-and-split technique and have four phases: local congestion sensing, adaptive coalition formation, coalition head and coalition sensing. In the local congestion sensing, each individual wireless network computes congestion based on the number of packets dropped. In adaptive coalition formation phase, the wireless networks (or existing coalitions of wireless networks) interact in order to assess whether to share their load with nearby networks. For this purpose, an iteration of sequential merge-and-split rules occurs in the network. Each coalition decides to merge (or split) depending on the utility improvement that merging (or splitting) yields. In the final coalition-sensing phase, once the network topology converges following merge-and-split, wireless networks that belong to the same coalition report their utility function (computed using equation 2) value to their local coalition head. The coalition head subsequently uses decision rule to make a final decision. This decision is reported to all the members within their respective coalitions.

gorithm:  Coalitional Game for vertical handoff initiation in 4G

Initial State

The network is partitioned by S ={S 1 ,…S k } {At the beginning of all time T = N ={1,… n } with noncooperative wireless networks}.

Four phases in each round of the coalition formation

Phase I – Local congestion sensing

Each individual wireless networks computes its local congestion. Initially coalition consists of individual wireless networks as members in each set.

Phase II – Adaptive coalition formation:

In this phase, coalition formation occurs using merge-and-split.

Repeat

• •    S = Merge{S_1;S₂}: coalition sets S i ,S₂ decide to merge if congestion factor C f k    k=1,2 of

wireless networks are equal with slight variation. This operation executed using the merge rule

• •    S₁, S₂= Split{S}: coalition in S decides to split if congestion factor C f k k=1,2 of wireless networks varies rapidly. This operation executed using the split rule.

Until merge-and-split terminates.

Phase III – Coalition Head

Each member in coalition records the entry time when it enters into coalition. The earliest created member becomes coalition head.

Phase IV – Coalition Sensing

• a)    Each member reports its utility function (computed using equation 2) value to its local coalition head.

• b)    The coalition head of each coalition makes a final decision using function in section C.

• c)    The members in a coalition abide by the final decision made by the coalition head.

The above phases are repeated throughout the network operation. In phase II, through distributed and periodic merge-and-split decisions, the members can autonomously form the coalition.

Final Stage

Some target network congestion factor in coalition S={ S 1 ,S 2 …S k } is less than some source network congestion factor (i.e. for some target i and source j we have c f i < c f j ), so that some vertical handoff of call is initiated .

Each round of the four phases of the proposed algorithm starts from an initial network partition S = {S 1 ,…S k } of n. During the adaptive coalition formation phase any random coalition can start with merge process. The coalition S_i e S which has the highest utility in the

initial partition S starts the merge by attempting to collaborate with a nearby coalition. On one hand, if merging occurs, new coalition S i is formed, and in its turn, coalitions S i will attempt to merge with a nearby wireless network that can improve its utility. On the other hand, if S i is unable to merge with the early-discovered partner, it tries to find other coalitions that have a mutual benefit in merging. The search ends by a final merged coalition S i final composed of S i . The algorithm is repeated for the remaining S i ∈ S until all the coalitions have made their merge decisions, resulting in a final partition F. Following the merge process, the coalitions in the resulting partition F are next subject to split operations if possible. An iteration consisting of multiple successive merge-and-split operations i.e. repeated until it terminates.

For handling environmental changes, such as mobility or the joining/leaving of mobile nodes, phase II of the proposed algorithm is repeated periodically. In second phase, periodically, wireless networks autonomously manage congestion through new merge-and-split actions with each coalition taking the decision to merge (or split) subject to satisfying the merge (or split) rule. Every period of time t the wireless networks assess the possibility of splitting into smaller coalitions or merging with new partners. For example: Merging of loosely coupled wireless networks yields favorable result to reduce congestion level. Splitting of tightly coupled wireless networks increases packet flow in 4G wireless networks. Similarly after every period of time t in which the current coalition head of a coalition is turned off. The coalition members may select a new coalition head if needed. At the end of the fourth phase the coalition is stable and become core.

• III.    Performance Evaluation

In this scenario, one EVDV network, one WiMaX network and 28 WiFi network cells with 100m-coverage area serving both packet-switched voice and data calls are considered. The congestion factor represents the level of congestion in these wireless networks. Figure 1 shows the congestion factor of wireless networks in different coalition. We consider three different coalitions for wireless networks of 4G (i.e. {WiFi}, {WiFi , WiMAX}, {WiFi , WiMAX , EVDV}) in order to investigate the impact of congestion from coordination with other wireless networks. It is observed that without cooperation WiFi obtains congestion factor ranging from 0.5 to 2.9 with creation of applications between 2 to 12. Further it is observed that with cooperation with all other networks, the congestion factor ranges from 0.5 to 2.4 with creation of applications between 2 to 12.

Figure 1: Congestion factor with Coalition sets

Further we analyzed the effect of this Vertical Handoff initiation for Congestion control using Coalition Game (VHCCG) policy by considering two wireless networks WLAN and EVDV. In this system users can use voice over IP for communication. We use a discrete time simulator; the new packet-switched calls are generated with Negative exponential distributed process. It is equivalent to a Poisson process in continuous time simulation. In table 1, we list the simulation parameters of the speech traffic.

Table 1: Voice traffic parameters

Voice parameters	Distribution	Mean/value
Inter-arrival of calls (s)	Poisson	0-120
Duration of calls (s)	Geometric	120
Max.      Throughput (kbps)		13

In Figure 2, we compare the average delay for handoff call processing using schemes A-HCACH and VHCCG. With variation of offered traffic between 2 to 8 Erlangs, the average delay of handoff calls in case of VHCCG ranges from 1s to 1.48s and in case of A-HCACH it ranges from 1s to 1.75s. The average delay for handoff call processing is less in VHCCG scheme. This is due to cooperation of wireless networks in sharing network traffic.

Figure 2: Average delay for processing handoff call

Figure 3 exhibits comparison of the service time for handoff calls in A-HCAC and VHCCG. The waiting time for handoff call initiation in VHCCG is minimum compared to A-HCAC. The waiting time for handoff call initiation in VHCCG ranges from 0 to 0.4s with variation of offered traffic load from 2 to 8 Erlangs whereas in case of A-HCAC it ranges from 0 to 0.43s with variation of offered traffic load from 2 to 8 Erlangs.

Figure 3: Waiting time for handoff call initiation

• IV.    Conclusion

In this paper, we designed new mechanism to congestion control in 4G wireless networks. Compared with the traditional congestion control algorithms, this congestion control mechanism can manage congestion in 4G domains with vertical handoff initiation. The target network selection for this vertical handoff is done with coalition game. In this coalition game core is formed at equilibrium state. Simulation results showed that vertical handoff with coalition game can reduce the service time and delay for handoff call processing when compared to traditional congestion control scheme.