Gateway Selection Game in Cyber-Physical Systems

Abstract

Cyber-Physical Systems (CPSs) obtain the information of the physical world and impact the environment through many different kinds of devices. Usually, devices with different wireless technologies communicate with each other and the external networks through gateways placed in the working area. Different kinds of devices in a CPS may not operate with each other for their own benefit, and the competition will be more intense between different kinds of devices. They will contend for bandwidth of gateways to increase their throughput and avoid transmission delay. In this paper, we formulate this gateway selection situation as a noncooperative game. We investigate the actions of devices when they change their gateway and the result of devices' competition. We first give a bandwidth allocation model of gateways and propose a distributed algorithm for clients of gateway selection in order to increase the total bandwidth of their own kind. Then we investigate the migration trends of clients, and three theorems about the condition when clients stop migrating are given. We propose examples of gateway selection game with and without Nash Equilibrium. At last section, we give simulation results of gateway selection game.

1. Introduction

Cyber-Physical Systems (CPSs) obtain the information of physical world and impact the environment through many different kinds of devices. They use different sensors to observe the targets and make influences on the targets through different actuator. For better understanding and changing the physical environment, data collection and analysis are of the essence [1]. Knowledge extracted from the data also guides the behaviors of actuators in CPSs. To work efficiently, all these mentioned above cannot be done without data exchanging between different devices within a certain CPS and between the devices in a CPS and the external networks.

In CPSs, data transmission usually takes advantage of wireless communication. For instance, sensors and actuators generally use wireless technology to transmit data to each other [2] and keep connection with external network in order to have quick reaction when certain event is detected [3, 4]. Different types of sensors have been arranged to obtain comprehensive information of the area, and they send data to external network for analyzing. Actuators in the area also need commands from the external network or sensors in other systems to take proper actions. Meanwhile, data exchanging between these devices is also important. When some devices need to transmit information to others, they usually send them in multicast way. In order to make multicast possible, routing tree is needed. And much effort has been spent on reducing the cost of the multicast routing [5–8]. However, when these devices are equipped with different wireless communication technologies, they cannot transmit data directly. Due to the rapid development of wireless communication technology, today, CPSs with multiwireless technology coexisting become familiar. Usually, devices with different wireless technologies communicate with each other and the external networks through gateways placed in the working area. This is because different wireless technologies may not be compatible, and considering the cost, privacy, and safety, we cannot connect each device directly to external networks. And for the expansibility of a CPS working in a certain area, gateways usually arranged to cover the whole area. In order to guarantee that no subarea is missed, gateways usually have been placed reasonably intensively, and the coverage areas of different gateways will overlap. Thus, some devices in the CPS can choose more than one gateway to connect with. It is quite rational for these devices to choose among different gateways and find the best one for them to keep connection. And how to select the most suitable gateway is a problem that has been extensively studied.

Some work focus on increasing the benefit of single user in the system. The authors in [9] consider a gateway selection problem in Unmanned Aerial Vehicles (UAVs) networks and give a distributed algorithm to guarantee the stability of an UAV. In [10] the gateway selection mechanism among all candidate gateways as essential component to interconnect MANET and Internet is considered. The authors use QoS-based metrics to select an optimum gateway. They aim is to balance traffic load among gateways in order to improve throughput performance and packet delivery ratio of integrated MANET and the Internet. In [11] a Dynamic DAP Selection Algorithm is proposed for a meter in a smart grid to randomly select Data Aggregation Points (DAPs) from its DAP list and route the packet. This algorithm aims at increasing networking's robustness and resiliency. In [12], authors propose a cooperative traffic transmission algorithm based on fuzzy logic in a joint LTE Advanced-VANET hybrid network architecture where an elected gateway will connect a source vehicle to the LTE advanced infrastructure. They design this algorithm to improve the performance of data transmission of the network. These works do not consider the mutual effect between different users and they focus on the problem of how to designate a gateway node among all the users.

Devices in CPSs may not cooperate with each other for their own benefit, and the competition will be more intense between different kinds of devices. They will contend for bandwidth of gateways to increase their throughput and avoid transmission delay. Existing works mentioned above assume that devices in CPSs are willing to cooperate with each other controlled by a central controller. This assumption is not suitable under noncooperative situation. In this paper, we focus on such a situation where devices choose their gateways only depending on their own benefit and they compete with each other for bandwidth of the gateway. Such condition inspires us to formulate this gateway selection problem as a noncooperative game. There are also some works that utilize game theory to study gateway selection problem. In [13] the authors investigate the interoperability issue in coalition networks where multiple groups of nodes are connected via wireless links. Authors of [13] use game theory to obtain the optimal selection of gateway aiming to minimize the total cost of links associated with each pair of nodes in the network. In [13] the authors also focus on how to pick a node to be the gateway. Our work focuses on which gateway should be choosed by a device in order to increase its benefit. Although a device in CPS tends to directly select a gateway which can maximize its own benefit, the cooperation among same kind of devices is necessary and advantageous. This is because same kind of devices may transmit data for others, and usually they have similar responsibility. Cooperation will increase the total profit of the same kind of devices; for instance, through cooperation, device will obtain more bandwidth of gateways compared to working alone. But the situation will change if there are different kinds of devices coexisting in the same work area. In order to increase the total benefit of their own kind, devices from different kinds will compete for limited resource of the system, such as bandwidth of gateways. There are few works investigating the behaviors of different kinds of devices of gateway selection problem in CPS; in this kind of situation, devices may change their gateways to increase total benefit of their kind. We use game theory to investigate the actions of devices when they change their gateway and the result of devices' competition.

The contributions of our work are as follows.

We model the gateway selection problem as a noncooperative game competing for bandwidth of gateway. And a practical bandwidth arrangement method is also given in this paper.

Migration trend has been investigated in this paper. We point out at which situation the clients will change their current gateway to increase total benefit of their kind and when they will keep their gateway.

We investigate the convergence of this gateway selection game. And we prove that the game will reach a Nash Equilibrium if one kind of client is fixed.

Finally, we make simulations to evaluate our method.

The paper is organized as follows. We discuss the related work in Section 2. The system models and some assumptions are given in Section 3. In Section 4 we investigate the migration of client and discuss when these client devices will keep their choice. In Section 5, we discuss the convergence. Simulation is in Section 6. And conclusions are given in Section 7.

2. Related Work

In any wireless networks, communication cost is an essential factor to consider. To transmit little and/or transmit fast can greatly improve the performance of wireless networks [14, 15]. These works solve the problem of how to extract significant information from a huge amount of sensory data. In our system model, different devices will contend for communication resource to reduce their cost, and the competition among them will greatly influence their communication cost, since each gateway has limit bandwidth. So it is of great importance to study the gateway selecting behavior of devices and the result of their competition.

Game theory has been widely used in investigating networking problems, such as [16–18]. In [16], authors introduce and analyze the properties of a class of games and the atomic congestion games on graphs and use this game theory to study the wireless network performance. In [17] the authors model the competition of SUs in a cognitive radio network with singleton congestion games with different preference constants. In [18] the authors model the scenario as a game which is equivalent to a network congestion game in the literature after proper and nontrivial transformations. And to our best knowledge, our work is the first one to analyze the gateway selection problem in CPSs using game theory.

Some studies on network selection have some similarity with our work, but we are focused on different situations. Network selection has been studied using game theory via several models including noncooperative game [19–21] and evolutionary game [22–26]. In [19] the authors propose a study to capture the dynamics among end users and network operators in the processes of network selection and resource allocation. The authors resort to noncooperative game theory to model the competition among multiple end users in accessing shared wireless networks. In [20] the authors study the dynamics of network selection in heterogeneous wireless networks. In [21] the authors analyze the convergence properties of dynamics of network selection in heterogeneous wireless networks. All the work mentioned above contribute a lot in investigating the network selection problem using game theory. However, these studies do not consider the cooperation within the same group and the competition between different groups.

Evolutionary game theory has been adopted to solve wireless communications and networking problems. Application of evolutionary coalitional game theory to solve various problems in wireless networking can be found in [22]. The paper also explains the open issues and trends in the field. In [23] a reinforcement learning-based distributed mechanism for strategy and payoff learning in wireless networks is proposed. The stability of the learning algorithm is discussed based on evolutionary game dynamics. An evolutionary game theory-based method is used in [24] to solve the problem of network selection in an environment where multiple networks are available. In [25], the service selection in small cell networks is modeled and analyzed by using evolutionary game theory. In [26], the authors present an evolutionary game theory-based distributed subcarrier and power allocation scheme for downlink transmission in orthogonal frequency division multiple access-based small cell networks under laying a macrocellular network. Evolutionary games assume a very large number of clients where a single client has minimal impact on other clients. This is not the case in our problem in which a single client can have major impacts on other users' decisions.

3. System Model

3.1. Network Model

We consider a system with three different kinds of nodes coexisting in the working area, and there is no central controller. One of them is gateway nodes represented by $G=\{g_1,g_2,\dots ,g_k\}$ . And the others are client nodes $A=\{a_1,a_2,\dots ,a_n\}$ and client nodes $B=\{b_1,b_2,\dots ,b_m\}$ . Each client node needs to connect to a gateway for data exchanging with external networks. And same kinds of clients are able to exchange data mutually. Gateways are elaborately placed to make sure the whole area has been covered, which means every client node in this area can connect to at least one gateway. Client nodes have been randomly placed in this area. And every client is able to connect to a subset of gateways. Two different kinds of client nodes are equipped with different wireless communication technologies and we assume that all gateways and clients are interference-free by means of spectrum separation between clients using different wireless communication technologies and frequency reuse and/or orthogonal channels among gateways and same kind of clients. We assume that every client can only maintain wireless connection with one gateway at a time, and clients are able to obtain nearby gateways information which contains number and type of clients connecting to this gateway through gateway's broadcast. Depending on this piece of information, clients are able to calculate bandwidth that they will get if they leave the current gateway and connect to another one. And all these clients will try to connect to other gateways, if they can benefit from changing their gateways.

3.2. Bandwidth Allocation Model

Though clients A and B use different kinds of wireless communication technologies, they share the same kind of gateway bandwidth. This can be considered as the ability of gateways of data transmission with external networks. We denote the total bandwidth of gateway $g_i$ as W and its bandwidth is arranged to clients A and B by $W_{a_i}$ and $W_{b_i}$ , and we have $W_{a_i}+W_{b_i}=W$ . Same kind of clients share the bandwidth arranged to them equally, which means $w_a=W_{a_i}/n_i$ , $w_b=W_{b_i}/m_i$ , $w_a$ and $w_b$ are the bandwidth obtained by clients a and b, $n_i$ represents number of clients A connected to gateway $g_i$ , and $m_i$ represents number of clients B connected to gateway $g_i$ . Clients A and clients B connecting to the same gateway compete for bandwidth, and the bandwidth they get depends on their numbers: the more clients connected the more bandwidth this kind of clients will get. In this paper, we assume that $W_{a_i}:W_{b_i}=n_i:m_i$ considering fairness. So the bandwidth arranged to clients a and b by gateway $g_i$ is

$$\begin{array}{cc}& w_a=\frac{n_i\left[W/\left(n_i+m_i\right)\right]}{n_i}=\frac{W}{n_i+m_i},\\ w_b=\frac{m_i\left[W/\left(n_i+m_i\right)\right]}{m_i}=\frac{W}{n_i+m_i}.\end{array}$$

(1)

From (1) we can see that clients connecting to the same gateway will obtain equal bandwidth. And the bandwidth they get only depends on the bandwidth of this gateway and the number of clients A and clients B connecting to this gateway.

3.3. Gateway Selection Game

As mentioned above, clients will change their gateways in order to increase their benefit. And different kinds of clients will compete for gateway's bandwidth. Clients can benefit from increasing bandwidth obtained by their whole kind of clients, since data can be forwarded by same kind of clients. Thus, one client will change its current gateway to another if this migration will increase the total bandwidth of its kind of clients. We model this gateway selection problem as a noncooperative game, in which clients select gateways in distributed manner to increaser their total bandwidth of their kind.

Player. Client A and client B who can connect to more than one gateway in this working area are the players in this game. And if a client can only connect to a certain gateway, it will not be considered as a player in this game.

Strategy. The strategy set in this game is the set of gateways in this area which is $G=\{g_1,g_2,\dots ,g_k\}$ . Each player's strategy set is its accessible gateways. We denote the strategy taken by player i by $s_i$ , and the strategy profile of all players is denoted by $s=(s_1,s_2,\dots ,s_N)$ , where N is the number of players.

Payoff. The bandwidth obtained by a client is the payoff of this player. What is different from common games is that player chooses its strategy not to increase its own payoff, but to increase the total payoff of its population.

Population. Players from same kind of clients form a population. In this game, there are two populations, one is players from clients A and the other is players from clients B. We denote these two populations by $P_A$ and $P_B$ .

Nash Equilibrium. We call a strategy profile at Nash Equilibrium if none of the players can increase its population's payoff by changing to another strategy when other players keep their choice.

3.4. Gateway Selection Algorithm

Because there is no central controller, each client has to find the best gateway to connect all by their own. Thus, we propose a distribute gateway selection algorithm for clients to choose their strategies among all candidate gateways. As we can see from Algorithm 1, a client will compare all its accessible gateways to find the one which makes the total payoff of its population maximum. Though the algorithm is quite simple as we expected, the result that follows the behaviors of the clients is hard to predict. Since both kinds of clients will try to maximize their population's payoff, it is meaningful to investigate the competition result.

Algorithm 1: Gateway selection algorithm.

Input: client's accessible gateways set $G_i$ , client's current gateway g, parameter

   of each gateway $g_i$ in $G_i$ : number of clients A and clients B connected to $g_i$

Output: Decision to migration, and the selected gateway

(1)  for each gateway $g_i$ in $G_i$

(2)     Calculate the increment $\Delta w_i$ of the total payoff of the population after migration

(3)    if   $\Delta w_i>\mathrm{0}$

(4)         Client change its gateway to $g_i$

(5)    else

(6)         Client keeps its current gateway

          End Algorithm

4. Migration of Client

In this section, we investigate at what condition that a client will decide to change its gateway and the tendency of clients' migration. The main notations used in this paper have been shown in Table 1.

Table 1

Main notation.

Variable	Description
W	Total bandwidth of a gateway
$$W_i$$	Total bandwidth obtained by clients of type i
$$\Delta W_i$$	Bandwidth variation of type i after migration
$$n_i$$	Number of clients A connected to gateway i
$$m_i$$	Number of clients B connected to gateway i
$$p_i$$	Total payoff of type i clients

First, we show under what condition that a client will change its current gateway to another. As mentioned above, a client migrates when its movement will increase the total payoff of its population. We will take client $a_i$ as an example. We assume $a_i$ can connect gateways $g_1$ and $g_2$ , and it keeps a connection with $g_1$ . And there are $n_1$ clients of client A and $m_1$ clients of client B connecting to $g_1$ and $n_2$ clients of client A and $m_2$ clients of client B connecting to $g_2$ . Here we assume that $n_{\mathrm{1}}+m_{\mathrm{1}}\ge \mathrm{2}$ and $n_{\mathrm{2}}+m_{\mathrm{2}}\ge \mathrm{1}$ . Thus, the total payoff of $P_A$ is

$$\begin{array}{cc}& W_A=W_{A^{\prime }}+n_{\mathrm{1}}\frac{W}{n_{\mathrm{1}}+m_{\mathrm{1}}}+n_{\mathrm{2}}\frac{W}{n_{\mathrm{2}}+m_{\mathrm{2}}}.\end{array}$$

(2)

$W_{A^{\prime }}$ is the total payoff of $P_A$ except those clients who connect to gateways $g_1$ and $g_2$ . And if $a_i$ has changed its gateway to $g_2$ , the total payoff of $P_A$ will be

$$\begin{array}{cc}& W_A^{\prime }=W_{A^{\prime }}+\left(n_{\mathrm{1}}-\mathrm{1}\right)\frac{W}{n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}}+\left(n_{\mathrm{2}}+\mathrm{1}\right)\frac{W}{n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}}.\end{array}$$

(3)

The increment of $P_A$ 's payoff is (3)-(2), which is

$$\begin{array}{cc}& \Delta W_A=\left[\left(n_{\mathrm{1}}-\mathrm{1}\right)\frac{W}{n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}}+\left(n_{\mathrm{2}}+\mathrm{1}\right)\frac{W}{n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}}\right]-\left(n_{\mathrm{1}}\frac{W}{n_{\mathrm{1}}+m_{\mathrm{1}}}+n_{\mathrm{2}}\frac{W}{n_{\mathrm{2}}+m_{\mathrm{2}}}\right).\end{array}$$

(4)

From (4) we can see that migration of client $a_i$ will only influence the payoff of those clients who connect to $g_1$ and $g_2$ . We call $g_1$ the original gateway and $g_2$ the candidate gateway. When $\Delta W_A\le \mathrm{0}$ , client $a_i$ will not change its gateway from $g_1$ to $g_2$ , because this migration makes no benefit to its population. And if $\Delta W_A>\mathrm{0}$ , which means the total payoff of $P_A$ has been increased, client $a_i$ will change its gateway from $g_1$ to $g_2$ . If $n_{\mathrm{1}}+m_{\mathrm{1}}=\mathrm{1}$ and $n_{\mathrm{2}}+m_{\mathrm{2}}=\mathrm{0}$ , which means $n_1=1$ and $n_2=m_2=0$ , the increment of $P_A$ 's payoff is

$$\begin{array}{cc}& \Delta W_A=\left[\left(n_{\mathrm{2}}+\mathrm{1}\right)\frac{W}{n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}}\right]-\left(n_{\mathrm{1}}\frac{W}{n_{\mathrm{1}}+m_{\mathrm{1}}}\right)=\mathrm{0}.\end{array}$$

(5)

So client $a_i$ will not change its gateway. If $n_{\mathrm{1}}+m_{\mathrm{1}}\ge \mathrm{2}$ and $n_{\mathrm{2}}+m_{\mathrm{2}}=\mathrm{0}$ , the increment of $P_A$ 's payoff is

$$\begin{array}{cc}& \Delta W_A=\left[\frac{\left(n_{\mathrm{1}}-\mathrm{1}\right)W}{n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}}+\frac{\left(n_{\mathrm{2}}+\mathrm{1}\right)W}{n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}}\right]-\left(n_{\mathrm{1}}\frac{W}{n_{\mathrm{1}}+m_{\mathrm{1}}}\right)=\left(n_{\mathrm{1}}-\mathrm{1}\right)\frac{W}{n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}}+W-\left(n_{\mathrm{1}}\frac{W}{n_{\mathrm{1}}+m_{\mathrm{1}}}\right)=W-\frac{m_{\mathrm{1}}}{\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)}W>\mathrm{0}.\end{array}$$

(6)

So client $a_i$ will move from $g_1$ to $g_2$ . If $n_{\mathrm{1}}+m_{\mathrm{1}}=\mathrm{1}$ and $n_{\mathrm{2}}+m_{\mathrm{2}}\ge \mathrm{1}$ , the increment of $P_A$ 's payoff is

$$\begin{array}{cc}& \Delta W_A=\frac{\left(n_{\mathrm{2}}+\mathrm{1}\right)W}{n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}}-\left(\frac{n_{\mathrm{1}}W}{n_{\mathrm{1}}+m_{\mathrm{1}}}+\frac{n_{\mathrm{2}}W}{n_{\mathrm{2}}+m_{\mathrm{2}}}\right)=\frac{\left(n_{\mathrm{2}}+\mathrm{1}\right)W}{n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}}-\left(W+\frac{n_{\mathrm{2}}W}{n_{\mathrm{2}}+m_{\mathrm{2}}}\right)=\frac{m_{\mathrm{2}}}{\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}W-W<\mathrm{0}\end{array}$$

(7)

so client $a_i$ will not move from $g_1$ to $g_2$ .

We next further simplify (4) to

$$\begin{array}{cc}& \Delta W_A=\left[\frac{\left(n_{\mathrm{1}}-\mathrm{1}\right)W}{n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}}+\frac{\left(n_{\mathrm{2}}+\mathrm{1}\right)W}{n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}}\right]-\left(\frac{n_{\mathrm{1}}W}{n_{\mathrm{1}}+m_{\mathrm{1}}}+\frac{n_{\mathrm{2}}W}{n_{\mathrm{2}}+m_{\mathrm{2}}}\right)=W\left[\frac{\left(n_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}{\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}+\frac{\left(n_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}{\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}-\frac{n_{\mathrm{1}}\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}{\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}-\frac{n_{\mathrm{2}}\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)}{\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}\right]=W\left[\frac{m_{\mathrm{2}}\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)-m_{\mathrm{1}}\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}{\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)}\right].\end{array}$$

(8)

We can see that whether (8) is greater than 0 depends on the equation below:

$$\begin{array}{cc}& {\Delta }_i=m_{\mathrm{2}}\left(n_{\mathrm{1}}+m_{\mathrm{1}}-\mathrm{1}\right)\left(n_{\mathrm{1}}+m_{\mathrm{1}}\right)-m_{\mathrm{1}}\left(n_{\mathrm{2}}+m_{\mathrm{2}}+\mathrm{1}\right)\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right).\end{array}$$

(9)

So when ${\Delta }_i>\mathrm{0}$ , client $a_i$ will change its gateway from $g_1$ to $g_2$ ; otherwise, $a_i$ will stay at its original gateway.

Theorem 1.

If the number of clients A and clients B of the original gateway equals the number of clients A and clients B of candidate gateway, respectively, none of these clients will change its strategy.

Proof.

We set the number of clients A in the original gateway and candidate gateway where both are n and we set the number of clients B in the original gateway and candidate gateway where both are m; for clients A and clients B (9) will be

$$\begin{array}{cc}& {\Delta }_{a_i}=m\left(n+m-\mathrm{1}\right)\left(n+m\right)-m\left(n+m+\mathrm{1}\right)\left(n+m\right)=-\mathrm{2}m\left(n+m\right)<\mathrm{0},\\ {\Delta }_{b_i}=n\left(n+m-\mathrm{1}\right)\left(n+m\right)-n\left(n+m+\mathrm{1}\right)\left(n+m\right)=-\mathrm{2}n\left(n+m\right)<\mathrm{0}.\end{array}$$

(10)

Both ${\Delta }_{a_i}$ and ${\Delta }_{b_i}$ are less than 0, which means changing strategy will decrease the total payoff of its population. So all these clients will keep their current strategy.

Inference 1.

When all the gateways connect same number of each kind of clients, all clients in this system will keep their strategy.

Proof.

Inference 1 is easily obtained by Theorem 1. Suppose client a wants to change its gateway from $g_i$ to $g_j$ , and the numbers of both kinds of clients connected to them are the same. From Theorem 1 we know that if client a decides to change its strategy from $g_i$ to $g_j$ , then the number of each kind of clients connecting to these two gateways must be different. And there is a contradiction.

Theorem 2.

If the number of one kind of clients in the original gateway is equal to that in the candidate gateway, the other kind of clients in original gateway will change its strategy iff there are at least two clients more in original gateway than in candidate gateway.

Proof.

Without loss of generality, we assume that the number of clients A in the original gateway is $n_1$ and the number of clients A in the candidate gateway is $n_2$ , and the number of clients B in both original gateway and candidate gateway is m; for clients A (9) will be

$$\begin{array}{cc}& {\Delta }_{a_i}=m\left(n_{\mathrm{1}}+m-\mathrm{1}\right)\left(n_{\mathrm{1}}+m\right)-m\left(n_{\mathrm{2}}+m+\mathrm{1}\right)\left(n_{\mathrm{2}}+m\right)=m\left[{\left(n_{\mathrm{1}}+m\right)}^{\mathrm{2}}-{\left(n_{\mathrm{2}}+m\right)}^{\mathrm{2}}-\left(n_{\mathrm{1}}+m\right)-\left(n_{\mathrm{2}}+m\right)\right]=m\left(n_{\mathrm{1}}+n_{\mathrm{2}}+\mathrm{2}m\right)\left(n_{\mathrm{1}}-n_{\mathrm{2}}-\mathrm{1}\right).\end{array}$$

(11)

When $n_1-n_2-1>0$ , ${\Delta }_{a_i}>0$ . For $n_1$ and $n_2$ are positive integers, $n_1-n_2-1>0$ equals $n_1\ge n_2+2$ . So when the number of clients A in $g_1$ is two more than that in $g_2$ , client $a_i$ will move from $g_1$ to $g_2$ . Now we prove the necessity. From Section 4 we know that a client will change its strategy at only one condition that this movement will increase the total payoff of its population. So when client $a_i$ moves from $g_1$ to $g_2$ , we have ${\Delta }_{a_i}>0$ . For $n_1$ , $n_2$ , and m are positive integers, $m(n_1+n_2+2m)>0$ . So $(n_1-n_2-1)$ has to be greater than zero to make ${\Delta }_{a_i}>0$ . Thus, we have $n_1\ge n_2+2$ .

Theorem 3.

Denote the number of clients A in $g_1$ and $g_2$ by $n_1$ and $n_2$ , and denote the number of clients B in $g_1$ and $g_2$ by $m_1$ and $m_2$ . When $n_1=n_2=n$ and $m_1\ne m_2$ , we have the following.

• (1)

If $m_1=m_2+1$ , none of players of clients A in $g_1$ will change its strategy to $g_2$ .

(2)

If $m_1<m_2$ and $n^2<m_1\ast m_2$ or $m_1<m_2$ and $n^2>m_1\ast m_2$ , none of players of clients A in $g_1$ will change its strategy to $g_2$ .

Proof.

Firstly, we prove the first conclusion. For clients A in $g_1$ , (9) will be

$$\begin{array}{cc}& {\Delta }_{a_i}=m_{\mathrm{2}}\left(n+m_{\mathrm{1}}-\mathrm{1}\right)\left(n+m_{\mathrm{1}}\right)-m_{\mathrm{1}}\left(n+m_{\mathrm{2}}+\mathrm{1}\right)\left(n+m_{\mathrm{2}}\right)=\left(n{m}_{\mathrm{2}}+m_{\mathrm{1}}{m}_{\mathrm{2}}\right)\left(n+m_{\mathrm{1}}-\mathrm{1}\right)-\left(n{m}_{\mathrm{1}}+m_{\mathrm{1}}{m}_{\mathrm{2}}\right)\left(n+m_{\mathrm{2}}+\mathrm{1}\right)=n^{\mathrm{2}}{m}_{\mathrm{2}}-n^{\mathrm{2}}{m}_{\mathrm{1}}+m_{\mathrm{1}}^{\mathrm{2}}{m}_{\mathrm{2}}-m_{\mathrm{1}}{m}_{\mathrm{2}}^{\mathrm{2}}-\mathrm{2}{m}_{\mathrm{1}}{m}_{\mathrm{2}}-n{m}_{\mathrm{1}}-n{m}_{\mathrm{2}}=n^{\mathrm{2}}\left(m_{\mathrm{2}}-m_{\mathrm{1}}\right)+m_{\mathrm{1}}{m}_{\mathrm{2}}\left(m_{\mathrm{1}}-m_{\mathrm{2}}-\mathrm{2}\right)-n\left(m_{\mathrm{1}}+m_{\mathrm{2}}\right).\end{array}$$

(12)

When $m_1=m_2+1$ , (12) will be

$$\begin{array}{cc}& {\Delta }_{a_i}=-n^{\mathrm{2}}-m_{\mathrm{1}}{m}_{\mathrm{2}}-n\left(\mathrm{2}{m}_{\mathrm{2}}+\mathrm{1}\right)<\mathrm{0}.\end{array}$$

(13)

Since (13) is negative, player of clients A in $g_1$ will not change its strategy to $g_2$ .

Then, we prove the second conclusion. For clients A in $g_1$ ,   (9) will be

$$\begin{array}{cc}& {\Delta }_{a_i}=m_{\mathrm{2}}\left(n+m_{\mathrm{1}}-\mathrm{1}\right)\left(n+m_{\mathrm{1}}\right)-m_{\mathrm{1}}\left(n+m_{\mathrm{2}}+\mathrm{1}\right)\left(n+m_{\mathrm{2}}\right)=\left(n{m}_{\mathrm{2}}+m_{\mathrm{1}}{m}_{\mathrm{2}}\right)\left(n+m_{\mathrm{1}}-\mathrm{1}\right)-\left(n{m}_{\mathrm{1}}+m_{\mathrm{1}}{m}_{\mathrm{2}}\right)\left(n+m_{\mathrm{2}}+\mathrm{1}\right)=n^{\mathrm{2}}\left(m_{\mathrm{2}}-m_{\mathrm{1}}\right)+m_{\mathrm{1}}{m}_{\mathrm{2}}\left(m_{\mathrm{1}}-m_{\mathrm{2}}\right)-\mathrm{2}{m}_{\mathrm{1}}{m}_{\mathrm{2}}-n\left(m_{\mathrm{1}}+m_{\mathrm{2}}\right)=\left(n^{\mathrm{2}}-m_{\mathrm{1}}{m}_{\mathrm{2}}\right)\left(m_{\mathrm{2}}-m_{\mathrm{1}}\right)-\mathrm{2}{m}_{\mathrm{1}}{m}_{\mathrm{2}}-n\left(m_{\mathrm{1}}+m_{\mathrm{2}}\right).\end{array}$$

(14)

When $m_1<m_2$ and $n^2<m_1\ast m_2$ or $m_1<m_2$ and $n^2>m_1\ast m_2$ , the first item in (14) will be negative and that will guarantee (14) is negative. So player of clients A in $g_1$ will not change its strategy to $g_2$ .

5. Migration Convergence

In this section, we investigate the convergence of gateway selection game. We first give a simple example to show how a gateway selection game converges to Nash Equilibrium.

In the example of Figure 1, there are two gateways $g_1$ and $g_2$ , and three of clients A and three of clients B. Since only $a_1$ , $a_2$ , $b_1$ , and $b_2$ can connect to both $g_1$ and $g_2$ , the player set in this game is $\{a_1,a_2,b_1,b_2\}$ , and their strategy set is $\{g_1,g_2\}$ . We assume that at beginning $a_1$ , $a_2$ , and $b_1$ connected to $g_1$ and $b_2$ connected to $g_2$ . Thus, the payoff of $P_A$ and $P_B$ is

$$\begin{array}{cc}& W_A=\mathrm{3}\times \frac{W}{\mathrm{3}+\mathrm{2}}+\mathrm{1}\times \frac{W}{\mathrm{1}+\mathrm{2}}=\frac{\mathrm{14}}{\mathrm{15}}W,\\ W_B=\mathrm{2}\times \frac{W}{\mathrm{3}+\mathrm{2}}+\mathrm{2}\times \frac{W}{\mathrm{1}+\mathrm{2}}=\frac{\mathrm{16}}{\mathrm{15}}W.\end{array}$$

(15)

Without loss of generality, let $a_1$ be the first one to decide whether it will change its strategy. If $a_1$ move to $g_2$ , the new payoff of $P_A$ will be

$$\begin{array}{cc}& W_A^{\prime }=\mathrm{2}\times \frac{W}{\mathrm{2}+\mathrm{2}}+\mathrm{2}\times \frac{W}{\mathrm{2}+\mathrm{2}}=W.\end{array}$$

(16)

Since $W_A<W_A^{\prime }$ , $a_1$ will change its gateway to $g_2$ . And now, the payoff of $P_B$ changes to

$$\begin{array}{cc}& W_B=\mathrm{2}\times \frac{W}{\mathrm{2}+\mathrm{2}}+\mathrm{2}\times \frac{W}{\mathrm{2}+\mathrm{2}}=W.\end{array}$$

(17)

Now let us consider $b_1$ 's action. If $b_1$ changes its gateway to $g_2$ , the payoff of $P_B$ will be

$$\begin{array}{cc}& W_B^{\prime }=\mathrm{1}\times \frac{W}{\mathrm{2}+\mathrm{1}}+\mathrm{3}\times \frac{W}{\mathrm{2}+\mathrm{3}}=\frac{\mathrm{14}}{\mathrm{15}}W.\end{array}$$

(18)

Since $W_B>W_B^{\prime }$ , $b_1$ will not change its strategy, so dose $b_2$ . Now it is $a_2$ 's turn to decide whether it will change the strategy. If $a_2$ changes its gateway to $g_2$ , the payoff of $P_A$ will be

$$\begin{array}{cc}& W_A^{\prime \prime }=\mathrm{1}\times \frac{W}{\mathrm{1}+\mathrm{2}}+\mathrm{3}\times \frac{W}{\mathrm{3}+\mathrm{2}}=\frac{\mathrm{14}}{\mathrm{15}}W.\end{array}$$

(19)

Since $W_A^{\prime }>W_A^{\prime \prime }$ , $a_2$ will keep its current strategy. Now, there is no player in this game that can increase its population's payoff by changing its strategy, so the game is at a Nash Equilibrium and $s^{\ast }=\{g_2,g_1,g_1,g_2\}$ . Migration of clients is shown by Figure 2.

Figure 1

An example which has Nash Equilibrium.

Figure 2

Migration of clients in example one.

But the gateway selection game will not always reach Nash Equilibrium. And we propose another example where the migration of clients will never stop.

In the example of Figure 3, there are four players: $a_1$ , $a_2$ , $a_3$ , and $b_1$ . Assuming at the beginning that $a_1$ , $a_2$ , and $a_3$ connect to $g_1$ and $b_1$ connects to $g_2$ , we use (9) to decide whether a client will change its strategy. From client $a_1$ , ${\Delta }_{a_{\mathrm{1}}}=\mathrm{2}\times \left(\mathrm{4}+\mathrm{1}-\mathrm{1}\right)\left(\mathrm{4}+\mathrm{1}\right)-\mathrm{1}\times \left(\mathrm{1}+\mathrm{2}+\mathrm{1}\right)\left(\mathrm{1}+\mathrm{2}\right)>\mathrm{0}$ , so $a_1$ will move to $g_2$ . Then from client $b_1$ , ${\Delta }_{b_{\mathrm{1}}}=-\mathrm{4}$ , so $b_1$ will not change its gateway. Next from client $a_2$ , ${\Delta }_{a_{\mathrm{2}}}=\mathrm{4}$ , so $a_2$ will move to $g_2$ . Then from $b_1$ , ${\Delta }_{b_{\mathrm{1}}}=\mathrm{4}$ , so $b_1$ will move to $g_1$ . Then $a_1$ will go back to $g_1$ , and after that, $b_1$ will go back to $g_2$ . We use Figure 4 to show these movements of clients. And the migration will never stop.

Figure 3

An example which has no Nash Equilibrium.

Figure 4

Migration of clients in example two.

And if there are three or more gateways in the system, the situation will be more complicated. For there is no guarantee that the gateway selection game can reach a Nash Equilibrium, we add a condition for this game to make sure that the migration will stop.

Theorem 4.

If only one kind of clients can change their strategies, this gateway selection game will always come to a Nash Equilibrium.

Proof.

This proof is based on contradiction. Define the system state as the set of gateways and their connected clients. Assume there is a loop in the system, as shown in Figure 5. At the beginning, the system was in state $S_1$ , and the payoff of $P_A$ is $p_1$ . Then some clients of $P_A$ leaved their gateway in order to increase the total payoff. When system state came to $S_i$ , the payoff of $P_A$ is $p_i$ , and from the migration principle of clients, we have $p_1<p_i$ . And clients of $P_A$ keep on changing their gateways, and system state changed to $S_j$ ; in order to form a loop in the system, let $S_j=S_1$ . If $S_j=S_1$ , at least the number of clients in each gateway is equal, and from (2) we have $p_j=p_1$ . Thus, $p_1<p_i<p_j=p_1$ , which is a contradiction.

Figure 5

System state evolution.

6. Simulation

In this section, we conduct several simulations to study the number of switchings of clients and the total payoff of $P_A$ and $P_B$ under different settings.

6.1. Simulation Setup

We consider an area of 100 meters by 100 meters. Clients A and clients B have been randomly placed in this region. Communication radius of clients A and B has been set to 25 meters. For most of the simulations, we place 49 gateways in the area, and set the bandwidth of gateway to 10 MBits. These gateways have been placed in grid and the interval between two gateways is about 16 meters, which makes the whole place covered by gateways. Figure 6 shows the distribution of gateways. We conduct 5 simulations with different number of clients and gateways and average the number of switchings of clients and the total payoff. We run the simulations on Windows 7 platform on DELL PC OPTILEX 790 with 3.10 GHz Intel Core i5 CPU, 8 GB memory, and hard disk of 5400 rpm and all codes were written in C/C++.

Figure 6

Gateway distribution.

6.2. Results Discussion

Figures 7, 8, and 9 show the number of clients' switchings and the total payoff of clients A and B with different numbers of clients. In Figure 7, the number of clients A equals that of clients B, and we increase the number of both clients A and B from $\mathrm{10,10}$ to $\mathrm{80,80}$ . Figure 7(a) shows the number of total switchings of clients A with fixed clients B and the number of switchings of clients A and B when both of them can change their gateway to increase the payoff of their populations. From the figure we can see that the number of switchings will increase along with the number of clients. And the average number of switchings of each client is less than one which indicates that fewer than half of the clients have changed their gateways. The migrations of clients will sometimes not stop when both clients A and B can change their gateways, and we find out that after about half number of the clients of switchings, the payoffs will be quite stable. So we stop the migrations after certain number of movements of the clients. And if these clients can reach Nash Equilibrium, each population takes fewer steps to reach Nash Equilibrium when both kinds of clients can change their gateways than what $P_A$ takes when clients B cannot change their gateways. Figure 7(b) shows the payoffs under different situations. We denote the initial payoffs of $P_A$ and $P_B$ when clients A and B are randomly placed in the area by $PA$ _0 and $PB$ _0, the final payoffs of $P_A$ and $P_B$ when only clients A can change their gateways by $PA$ _1 and $PB$ _1, and the stable payoffs of $P_A$ and $P_B$ when both clients A and B can change their gateways by $PA\_2$ and $PB\_2$ . We can see that the payoffs increase along with the number of clients, and the initial payoffs of clients A and B are quite equal. $PA\_1$ is always the biggest one among all the payoffs under any conditions; this is reasonable since clients A always change their gateways to increase the population's payoff. When the total number of clients is less than 60, the migrations of clients A also increase the payoff of $P_B$ , but when the total clients' number grows bigger, the payoff of $P_B$ decreases shapely. This is because when the number of clients is small, gateways in the area may not be fully used by all the clients, so clients A will move to some gateways which are idle at the beginning; thus, both payoffs of clients A and B can increase. But when the number of clients increases, there is no idle gateways in the area, and clients A have to squeeze the bandwidth of clients B, so $PA\_1$ becomes much larger than $PB\_1$ . This situation has changed when both kinds of clients can change their gateways. $PA\_2$ and $PB\_2$ are nearly the same in Figure 7(b).

Figure 7

Average number of switchings and payoff with number of A and B from $\mathrm{10,10}$ to $\mathrm{80,80}$ .

Figure 8

Average number of switchings and payoff with number of A and B from $\mathrm{30,10}$ to $\mathrm{30,60}$ .

Figure 9

Average number of switchings and payoff with number of A and B from $\mathrm{10,30}$ to $\mathrm{60,30}$ .

Figure 8 shows the results when the number of clients A is fixed to 30 and the number of clients B increased from 10 to 60. We can see that the number of clients B does not have much influence on the number of switchings of clients A with fixed clients B in Figure 8(a). This indicates that though the clients B may make the allocations of bandwidth of gateways different from each other, the fixed clients B cause little troubles to clients A. Figure 8(b) shows that the payoffs of one kind of clients depend much on the number of this kind of clients. And when only clients A can change their gateways, the payoffs of $P_A$ decrease slowly with the increasing number of clients B. So competition in gateway selection will increase the total payoff remarkably. And when both kinds of client can change their gateways, the competition results depend mainly on their numbers.

Figure 9 shows the results when the number of clients B is fixed to 30 and the number of clients A increased from 10 to 60. We can see from Figure 9(a) that the number of switchings increases a lot when the number of clients increases. The payoff changing tendency shown by Figure 9(b) has much similarity with Figure 8(b). With the increasing number of clients A, the payoff of $P_A$ grows larger. And $PA\_1$ is always much larger than $PA\_0$ which indicates the effectivity of the competition. Though the number of clients A is much smaller than that of clients B, clients A can narrow the gap between the payoffs of $P_A$ and $P_B$ .

Figure 10 shows the results when the numbers of clients A and B are fixed to 25 and the number of gateways increased from 25 to 81. We can see from Figure 10(a) that the number of switchings of clients increases very little compared to the great increase of the number of gateways. And the total payoffs of both kinds of clients increase a lot along with the increase of gateways.

Figure 10

Average number of switchings and payoff with number of gateways from 25 to 81.

Figure 11 shows the results of ten competitions with different initial connection gateways of clients A and B, and each number of them is 25. From Figure 9 we can see that the initial situation of clients has much influence on the competition results when only clients A can change their gateways. The number of switchings of clients A with fixed clients B changes from 7 to 17, and $PB$ _1 changes from about 120 to 200 MBits. But when both clients A and B can change their gateways, the results become much stable. $PA\_2$ and $PB\_2$ are the same in 9 of 10 competitions. They fluctuate between 215 and 225 MBits. The only one exception was not able to reach equilibrium.

Figure 11

Number of switchings and payoff with 25 clients of A and 25 clients of B.

7. Conclusion and Future Work

In this paper, we investigated the gateway selection game with two kinds of clients competing for more bandwidth of their own kind. We study the migration trends of the clients and the convergence of this game. Finally, we conduct large amounts of simulation to study the results of this gateway selection game under different conditions. Through the simulation, we show the effectivity of gateway selection game in increasing the total bandwidth of clients.