In this paper, we deal with the problem of M2M gateways' network selection for different types of M2M traffic in heterogeneous wireless networks. Based on the difference in traffic's quality of service (QoS) requirements, the M2M traffic produced by various applications is mainly classified as two categories: flexible traffic and rigid traffic. Then, game theory is adopted to solve the problem of network-channel selection with the coexistence of flexible and rigid traffic, named as flexible network access (FNA). We prove the formulated discrete game is a potential game. The existence and feasibility of the Nash equilibrium (NE) of the proposed game are also analyzed. Then, an iterative algorithm based on optimal reaction criterion and a distributed algorithm with limited feedback based on learning automata are presented to obtain the NE of the proposed game. In simulations, the proposed iterative algorithm can achieve a near optimal sum utility of whole network with low complexity compared to the exhaustive search. In addition, the simulation results show that our proposed algorithms outperform existing methods in terms of sum utility and load balance.
Machine-to-Machine (M2M) communications technology is a key technique of the Internet of things (IoT) to realize efficient, real-time transmission [1]. Consequently, many standard organizations are active in developing standards to support M2M communications, e.g. standard organizations, 3GPP, ETSI, GSMA, IEEE etc. [2]. In M2M communications, machines communicate with each others without human intervention. The goal of M2M communications is to provide ubiquitous connectivity among all machine nodes.In next-generation wireless network, different wireless access technologies (such as LTE cellular network, WiMAX and IEEE 802.11-based wireless local area network (WLAN) will be integrated into heterogeneous wireless networks to achieve more energy-efficient and spectrum-efficient communications. In wireless heterogeneous networks, due to the existence of diverse standards and uncooperative operators, it is difficult to deal with the challenges brought by massive machine nodes' demands on communications, for example, random access congestion, inefficient transmission caused by a great number of small data and the contradiction between limited network resources and massive data transmission requirements etc. [3],[4].
- 1.1 Motivations
To achieve better performance of M2M communications, three important problems must be solved in the future M2M networks: the high performance of end-user devices, quality of service (QoS) guarantees, and interference [5]. Thereinto, QoS guarantees in M2M communications will be the focus of this paper. However, for M2M nodes, different applications have different requirements on communication, for example, some applications (e.g., navigation, smart grids, telehealth) require hard delay constraints [6], and other applications (e.g., payment) have less demand on delay constraints [2]. In addition, different types of M2M traffic require different degrees of QoS. Due to the fixed and limited resources of heterogeneous networks, the resources should be allocated to M2M nodes appropriately in order to satisfy different types of traffic's QoS requirements. How to provide efficient and reliable M2M communications in heterogeneous wireless networks has become an urgent problem. In recent years, many literatures have investigated this problem [2-10]. Among these methods, a hierarchical heterogeneous architecture is very suitable to achieve heterogeneous scalable connectivity and high capacity [2], [11], while satisfying QoS of different traffic.Significantly, in heterogeneous wireless networks environment, network selection is an efficient solution to guarantee users' QoS by using various network resources [12-21]. During the network selection process, the users select the radio access networks (RAN) that differ in technology, bandwidth, latency, etc. according to their different QoS requirements, such as, to maximize the throughput, to decrease the transmission delay, and so on. Recently, many studies have proposed various network selection schemes, e.g., potential game based network selection scheme [12], online network selection scheme [13], probabilistic based network selection scheme [14], etc. However, the experimental results in [22] showed that, compared to traditional human-to-human (H2H) traffic, M2M traffic exhibited different patterns in multiple aspects. Therefore, without considering the characteristics of M2M traffic during network selection procedure, these schemes mentioned in [12-21] can't be applied to M2M communications directly. In addition, a cost-effective and scalable M2M solution can be offered by hierarchical network architectures, in which various M2M applications will be supported.
- 1.2 Contributions
In this paper, considering the QoS requirements of different M2M traffic, a wireless access scheme in the M2M gateways is investigated for hierarchical heterogeneous wireless network. Firstly, based on the results in [22], different types of M2M traffic's QoS requirements on wireless resources are analyzed. The M2M traffic produced by various applications (e.g., asset tracking, building security, fleet, miscellaneous, metering and telehealth [22]) is mainly classified as two categories, i.e., flexible traffic and rigid traffic, according to the QoS requirements of M2M traffic. Secondly, two metric functions are designed to describe the satisfaction degrees for two categories of M2M traffic. Game theory is adopted to solve the problem of the M2M gateways' network-channel selection with the coexistence of flexible and rigid traffic, named as flexible network access (FNA) in this paper. Different from network selection scheme in [12], the proposed FNA scheme considers the load balance and different types of M2M traffic's QoS requirements simultaneously. Then, we design a gateway's utility function that takes into account satisfaction degree and network load. The game with our proposed utility function is proved to be a potential game where a feasible pure strategy Nash equilibrium (NE) must exit [23]. Moreover, the sufficient condition for the feasibility of pure strategy NE is also analyzed. In addition, an iterative algorithm based on optimal reaction criterion [24] and a distributed algorithm with limited feedback based on the concept of learning automata [25] are presented to obtain the NE of the proposed game. Finally, simulation results show that the proposed scheme not only meets the QoS requirements of different types of M2M traffic but also improves the efficiency of network resources, i.e., achieving better load balance.
- 1.3 Related Works
In this subsection, some related works are discussed. The following two aspects would be covered: QoS assurance in M2M communications and network selection.In M2M communications, the problem of QoS assurance focus on how to design an efficient scheme to guarantee different M2M nodes’ requirements. For example, [7] proposed a random access scheme that minimized resources requirements to meet the QoS constraints (outage probability) of different M2M groups. [8] designed a scalable hybrid MAC protocol for heterogeneous M2M networks where the M2M nodes have different QoS requirements. In [9], an opportunistic user association was proposed to provide fair resource allocation for M2M traffic while considering the QoS of human-to-human (H2H) traffic in the multi-service heterogeneous networks. In [10], a statistical QoS guarantees uplink wireless allocation scheme was developed for LTE networks where H2H and M2M coexist. However, the methods proposed in existing works aren’t suitable for our scenario where network selection is used to guarantee the M2M traffic’s QoS requirements in heterogeneous networks.Network selection problem is usually modeled using either a centralized or a decentralized approach. In most centralized approach, there is a concentrated controller to decides the users’ distribution among the networks. Such as, [15] proposed a user association scheme among mutiple base stations to balance load in heterogeneous networks, and an energy efficient cell selection scheme is proposed in [16]. While for the decentralized approach, the decision is made by users to choose the most suitable available RAN. For example, a signal strength based and a pricing based network selection schemes were proposed in [17] and [18], respectively. In addition, there are many different mathematical theories which have been used for modeling the problem of network selection, such as, utility theory, multiple attribute decision making, fuzzy logic, game theory, combinatorial optimization, and Markov chain [19], in which game theory is widely adopted in the problem of network selection [20]. Authors in [12] proposed an ordinal potential game based network selection scheme to maximize the system throughput in heterogeneous networks with time-varying channel. [21] proposed a market-based approach to the problem of network selection in heterogeneous wireless networks where the selection mechanism is based on auction game. However, the above mentioned literatures don’t consider the characteristics of M2M traffic, such as, current works focus on the downlink network selection scheme, while for M2M communications, uplink transmission from M2M nodes to serve is more common for major applications.The rest of the paper is organized as follows. In Section 2, we give a detailed description of the system model, the problem of FNA is also formulated. The proposed game-theoretic formulation is given in Section 3. A centralized iterative algorithm and a distributed learning algorithm are presented in Section 4. The performance evaluation is given in Section 5. Finally, the conclusions are drawn in Section 6.
2. System Model
- 2.1 Wireless Access Networks
We consider a particular service area in the coverage of the heterogeneous wireless network environment consisting of N heterogeneous access networks (e.g., GSM/WCDMA/CDMA-2000/LTE, etc.), M M2M gateways and many M2M nodes as shown in Fig. 1. In this paper, we focus on the uplink communication of M2M nodes, i.e., the transmission from M2M nodes to M2M servers.
Illusion of hierarchical M2M system architecture in heterogeneous wireless networks.
Fig. 1 captures a hierarchical M2M system architecture over heterogeneous wireless networks, wherein multiple M2M nodes and an M2M gateway forms a group. In a group, M2M nodes can't send data to the M2M server directly in uplink channel, they connect to M2M gateway firstly. Then, according to the QoS requirements of the received traffic and network load, the M2M gateway chooses wireless access channel to send these traffic. Consequently, the M2M gateway is a smart M2M device which is responsible for managing M2M nodes, collecting M2M nodes' data and connecting to the M2M server in its group. Specifically, the M2M gateway communicates with the M2M server through a wide access network (WAN) connection. M2M nodes communicate with the M2M gateway by adopting the transport protocols, such as ZigBee, WiFi and Bluetooth. Note that an M2M gateway can serve multiple traffic by multi-transceiver or MAC protocols.We assume that the set of access networks is N={1,2,…,N} and the set of M2M gateways is M={1,2,…,M}. Network j∈N can provide K_{j}={1,2,…,K_{j}} channels with different bandwidth. The k th (k∈K_{j}) channel of Network j (j∈N)
PPT Slide
Lager Image
M2M gateways simultaneously. In this paper, we consider both large-scale path loss attenuation and small-scale fading in the channel model. The path loss factor is ϒ. The channel gain between the i th M2M gateway and the base station of the network j is h_{ij}, ∀i∈M and ∀j∈N. We model h_{ij} as zero-mean mutually independent, circularly symmetric complex Gaussian random variables with unit variance, and noise is modeled as independent, zero-mean additive white Gaussian noise with variance σ^{2}.We assume that R_{i} is the selected network-channel strategy of the i th gateway. The network-channel selection set of the i th M2M gateway is
PPT Slide
Lager Image
indicates that the i th M2M gateway selects the channel
PPT Slide
Lager Image
denotes that i th gateway selects none of the network to access.
- 2.2 FNA Problem
In the hierarchical heterogeneous network, an M2M gateway may receive massive and various M2M traffic from its group members. Due to the diverse and limited heterogeneous network recourses, an effective network selection strategy should be adopted by all gateways to satisfy M2M traffic's QoS requirements. In this paper, we propose a gateways' network access scheme to mitigate the contradiction between limited resources and massive transmission requirements, named as FNA scheme. The objective of FNA scheme is not only to satisfy the QoS requirements of different types of traffic but also to improve the efficiency of network resources. After analyzing different types of M2M traffic's requirements on wireless resources1 and based on the result in [22], we mainly classify these types of M2M traffic as two categories: flexible traffic and rigid traffic. In flexible traffic category, traffic's satisfaction degree raises with allocated bandwidth increasing, such as building security in [22]. In rigid traffic category, traffic's satisfaction degree keeps fixed if allocated bandwidth is larger than the required threshold, such as asset tracking and telehealth etc. It can be seen that the satisfaction degree is the parameter that describes the deviation between allocated resources and traffic’s QoS requirements. Note that the value of traffic's satisfaction degree ranges from 0 to 1. If traffic's satisfaction degree is equal to 0, then no resources are allocated. Traffic's satisfaction degree is equivalent to 1, when the allocated resources can satisfy the traffic's QoS requirements perfectly.Fig. 2 (a) and (b) present the satisfaction degree as a function of allocated bandwidth for rigid traffic and flexible traffic, respectively. In Fig. 2 (a), for rigid traffic, once allocated bandwidth is larger than required threshold resources, satisfaction degree approaches to 1. It can be perceived from Fig. 2 (b) that satisfaction degree raises with allocated bandwidth increasing when traffic is flexible.
The relationship between allocated bandwidth and M2M traffic's satisfaction degree.
Note that although there are various requirements on wireless resources for M2M traffic, bandwidth is one of the most important requirements. Therefore, we only consider requirements on bandwidth for different M2M traffic in this paper.
3. Game-Theoretic Formulation and Performance Analysis
In this section, we will resort to game theory to model the problem of FNA in M2M communi- cations and analyze the existence and feasibility of NE.
- 3.1 Problem Formulation and Game Model
In this paper, we emphasize on how M2M gateways select wireless channel to meet different traffic's QoS requirements and maximize the utility of the whole network simultaneously. First, the utility of the whole network is presented. Then, we analyze how to model the FNA problem the utility by game theory.First of all, for convenience of mathematical modeling, we describe the relationship between the allocated bandwidth and M2M traffic's satisfaction degree through specific mathematical expressions. Then, two satisfaction functions are given to describe the satisfaction degree of rigid traffic and that of flexible traffic, respectively.For rigid traffic, satisfaction function can be computed as
PPT Slide
Lager Image
where b is the allocated bandwidth, b_{req} is the required bandwidth of the rigid traffic, i.e., threshold value. κ is a selected constant. The larger κ is, the steeper the curve will be.For flexible traffic, satisfaction function can be obtained as
PPT Slide
Lager Image
where b_{max} is the maximum channel bandwidth among all channels in the heterogeneous networks.Without loss of generality, we assume that the i th M2M gateway selects the channel
PPT Slide
Lager Image
. Let r_{i,j,k} denotes the utility reward of the i th M2M gateway when the channel
PPT Slide
Lager Image
. Let r_{i,j,k} denotes the utility reward of the i is selected, and r_{i,j,k} can be expressed as
PPT Slide
Lager Image
where Sa_{i,j,k} denotes the sum of different types of traffic's satisfaction degree in the i th gateway,
PPT Slide
Lager Image
is the number of M2M gateways who select the channel
PPT Slide
Lager Image
, P_{i} is the transmit power of the i th gateway, b_{i,j,k} describes the allocated bandwidth for the i th M2M gateway in the channel
PPT Slide
Lager Image
. Supposing that there are
PPT Slide
Lager Image
types of rigid traffic and
PPT Slide
Lager Image
types of flexible traffic in the i th M2M gateway, Sa_{i,j,k} can be calculated by
PPT Slide
Lager Image
where b_{s,req} denotes the required bandwidth of the s th type of M2M traffic. According to (1) and (2), the satisfaction degree of traffic presents the maximum capability of the M2M gateway satisfying the traffic’s requirements (we don’t consider access control protocol among different traffic in this paper). In addition, since larger satisfaction degree will lead to more utility based on (3), the satisfaction degree of i th M2M gateway Sa_{i,j,k} is the sum of the satisfaction degree of all its traffic, which is in accordance with the design principle of the utility function in (3) although Sa_{i,j,k} may be large than 1. Consequently, the sum of satisfaction degree of the rigid traffic in the i th M2M gateway can be expressed by the first term of (4). Moreover, the satisfaction degree of different flexible traffic in an M2M gateway is the same based on (2). The sum of satisfaction degree of the flexible traffic in i th M2M gateway is computed by the second term of (4). The parameter
PPT Slide
Lager Image
in (3) indicates the price of the selected channel
PPT Slide
Lager Image
and can be obtained as
PPT Slide
Lager Image
where
PPT Slide
Lager Image
denotes the achievable rate of the channel
PPT Slide
Lager Image
, β is a constant.The price of channels increases as the number of M2M gateways that get access to the channel (denoted as
PPT Slide
Lager Image
) raising. Hence, in order to balance the network load, M2M gateways prefer to select the quite free channel. According to the price mechanism, we define load-balance-index of the whole network as L to reflect the utilization of heterogeneous wireless resources, and L can be computed by
PPT Slide
Lager Image
where
PPT Slide
Lager Image
denotes the average number of M2M gateways in each channel. From (6), we know that the greater L is, the better the load balance of network will be. It can be observed from (3)-(5) that M2M gateways desire to select channel which has capability to support their M2M traffic. However, due to the price mechanism, M2M gateways tend to obtain a better tradeoff between satisfaction degree and cost during channel selection process.The utility of whole network is defined as
PPT Slide
Lager Image
Note that
PPT Slide
Lager Image
if the i th M2M gateway selects the channel
PPT Slide
Lager Image
. In order to improve the performance of whole network, this paper is aimed at maximizing the sum utility reward u_{sum} with the network resources constraints. Formally, the FNA problem can be expressed as
PPT Slide
Lager Image
where R_{-i}. denotes the network-channel selection strategies of all M2M gateways excluding the i th M2M gateway.
PPT Slide
Lager Image
(∀j∈N and ∀k∈K_{j}) represents the constraint on the number of M2M gateways which select the channel
PPT Slide
Lager Image
is the maximum number of M2M gateways which the channel
PPT Slide
Lager Image
can serve simultaneously. Thus,
PPT Slide
Lager Image
denotes the capability of network and is determined by both the total bandwidth of the channel
PPT Slide
Lager Image
and the bandwidth required by M2M traffic.
PPT Slide
Lager Image
. Next, we will establish a game-theoretic formulation for FNA problem.Each M2M gateway selects a channel to maximize the sum utility reward u_{sum}. Furthermore, network-channel selection strategy profiles which go against constraints {
PPT Slide
Lager Image
|∀j,k,j∈N,k∈K_{j}} can not be selected. However, it is difficult to know which network-channel selection strategy profiles are infeasible in advance. Thus, u_{sum} can not be used as gateways' utility function. Inspired by the game model given in [24], we define the utility function of the i th M2M gateway as
PPT Slide
Lager Image
where
PPT Slide
Lager Image
, ξ is a non-negative constant, and it is chosen to be large enough to ensure that U_{i} < 0, ∀_{j} ∈ N, when
PPT Slide
Lager Image
. The second term in (9) represents the constraints in (8).Then we define the M2M gateways' FNA game as
PPT Slide
Lager Image
where the rational M2M gateways are regarded as the players. R_{i} is the pure strategy space, and G is a game with common utility as U_{i}=U_{s}, ∀i,s∈M.We assume R_{i}=
PPT Slide
Lager Image
, and define function V(R_{i},R_{-i}) as
PPT Slide
Lager Image
Theorem 1: G is a potential game with the potential function V.Proof: Assume that
PPT Slide
Lager Image
is an arbitrary strategy of the i th M2M gateway, and
PPT Slide
Lager Image
is an alternate strategy of the i th M2M gateway, the strategies of the other M2M gateways remain unchanged. Then, we have
PPT Slide
Lager Image
where
PPT Slide
Lager Image
indicate the number of M2M gateways in channel
PPT Slide
Lager Image
respectively when the network-channel selection strategy profile is (R_{i},R_{−i}).
PPT Slide
Lager Image
, denote the number of M2M gateways in channel
PPT Slide
Lager Image
respectively when the network-channel selection strategy profile is (R'_{i},R_{−i}). It can be found that
PPT Slide
Lager Image
Thus, (12) can be further expressed as.
PPT Slide
Lager Image
Hence, according to the definition of potential game in [23], G is a potential game whose potential function is V.
- 3.2 Analysis of NE
In this subsection, the existence and feasibility of the NE of the proposed game are investigated. First of all, the existence of the NE of G is analyzed.Lemma 1: The maximizer for U_{i} is a Pareto optimal pure strategy NE of G, if
PPT Slide
Lager Image
Proof: Supposing that {R_{i}}_{i∈M}⊂{R_{i}}_{i∈M} is a maximizer for U_{i}. Obviously, there exists no other network-channel selection strategy{R_{i}}_{i∈M} satisfying
PPT Slide
Lager Image
if, for some s,
PPT Slide
Lager Image
Hence, no M2M gateway can increase its utility without decreasing the other M2M gateway's utility. According to the definition of Pareto optimality in [26], [27],
PPT Slide
Lager Image
is a Pareto optimal solution to G.Additionally, ∀i∈M, if
PPT Slide
Lager Image
is an alternate strategy of the i th M2M gateway, we have
PPT Slide
Lager Image
That is, an arbitrary M2M gateway can never get a utility which is larger than the utility obtained by
PPT Slide
Lager Image
if it changes its own strategy unilaterally. From the definition of NE in [27], the network-channel selection strategy profile
must be a feasible channel selection strategy profile. Thus the lemma is proved. □If there are no constrains, every NE of our formulated game can be used as a solution. However, it is known from Lemma 1 that there may exist one feasible pure strategy NE when the constrains {
PPT Slide
Lager Image
|∀j,k,j∈N,k∈K_{j}} are considered. Nevertheless, it is still unclear whether an arbitrary NE can satisfy the constrains or not. In following, we will analyze the feasible of the NE of G.Lemma 2: The network-channel selection strategy profile that violates the number of M2M gateways constraints (i.e., {
PPT Slide
Lager Image
|∀j,k,j∈N,k∈K_{j}}) is not the pure strategy NE of G, if
PPT Slide
Lager Image
where ξ_{th} is defined as
PPT Slide
Lager Image
Proof: Assuming that {R_{i}}_{i∈M} violates constraint {
PPT Slide
Lager Image
|j∈N,k∈K_{j}}, but is a pure strategy NE of G. Then,
PPT Slide
Lager Image
and U_{i}(R_{i},R_{−i})<0, ∀i∈M.For a discrete strategy
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
From (19) and (20), we have
PPT Slide
Lager Image
Firstly, base on the precondition
PPT Slide
Lager Image
, then
PPT Slide
Lager Image
Hence, when u_{sum}(R_{i},R_{-i})-u_{sum}(0,R_{−i}) < ξ,
PPT Slide
Lager Image
Secondly, if
PPT Slide
Lager Image
, then
PPT Slide
Lager Image
Similarly, if u_{sum}(R_{i},R_{−i})-u_{sum}(0,R_{−i}) < ξ,
PPT Slide
Lager Image
According to the definition of NE in [23] and [27] and arbitrariness of {R_{i}}_{i∈M}, we can find that (23) and (25) contradict the presupposition that {R_{i}}_{i∈M} is a NE of G if
PPT Slide
Lager Image
. Thus, {R_{i}}_{i∈M} is not a pure strategy NE of G.When the network-channel selection strategy violates other constraints, we can prove the lemma in the same way. Therefore, the lemma is proved. □From Lemma 2, it can be seen that the pure strategy NE of the game will satisfy the constraints {
PPT Slide
Lager Image
|∀j, k, j ∈ N,k∈K_{j}} when ξ_{j}>ξ_{th}. It means that if ξ>ξ_{th}, the pure strategy NE of G must be feasible. ξ_{th} can be regarded as “threshold” of parameter ξ for achieving the feasible solutions.
4. Algorithm
- 4.1 Iteration Algorithm of Network-channel Selection Based on Satisfaction Degree
In this subsection, an iterative algorithm of network-channel selection based on satisfaction degree (IANCSS) is designed, as shown in Algorithm 1. The NE of the proposed game can be obtained by updating the strategies of M2M gateways based on the best response rule. Firstly, the convergence of IANCSS is proved as follows.
Iteration Algorithm of Network-channel Selection Based on Satisfaction Degree
PPT Slide
Lager Image
Iteration Algorithm of Network-channel Selection Based on Satisfaction Degree
Lemma 3:IANCSS converges to a feasible pure strategy NE of G in finite steps from any initial starting strategy profiles, if ξ>ξ_{th}.Proof: The maximum value of U_{i} is denoted as
PPT Slide
Lager Image
. Because the number of M2M gateways is finite,
PPT Slide
Lager Image
< ∞. For any initial starting strategy profile, since
PPT Slide
Lager Image
then IANCSS is a non-decreasing procedure. Therefore, the procedure must converge in finite steps.When IANCSS converges to a strategy profile
PPT Slide
Lager Image
, for an arbitrary M2M gateway i ,i ∈ M , and an alternative pure strategy
PPT Slide
Lager Image
,we have
PPT Slide
Lager Image
therefore, the strategy profile
PPT Slide
Lager Image
is a pure strategy NE of G according to the definition of NE in [27]. Moreover, according to the results in Lemma 2, the i th M2M gateway will never select strategy profile which violates the constraints {
PPT Slide
Lager Image
|∀j,k,j∈N,k∈K_{j}} if ξ>ξ_{th}.Hence, the Lemma is proved.
- 4.2 Distributed Network-channel Selection Algorithm Based on Learning Automata
IANCSS needs global information and a centralized controller, which is difficult to realize in practical. In this subsection, we design a distributed network-channel selection algorithm based on learning automata ( DNCSALA ) [25] to obtain the NE with limited feedback information.Assuming that the knowledge of {h_{ij}}_{∀i∈M,∀j∈N} is perfectly available at base stations but unknown at each M2M gateway. We extend the game G to a mixed strategy in order to apply the learning algorithm. Let
PPT Slide
Lager Image
be the mixed strategy of R_{i} of the ith M2M gateway, where
PPT Slide
Lager Image
denotes the probability that the ith M2M gateway selects the k th channel in the network j.If the mixed strategy network-channel selection game is played successively, it could be modeled as a stochastic game of learning automata. Each M2M gateway (i.e. player) is represented by a learning automaton and the actions of the automaton are the network-channel selection strategies of M2M gateways.
PPT Slide
Lager Image
is the action probability distribution of the ith automaton at instant t.The normalized utility of the i th M2M gateway is the reaction to the i th automaton, which can be expressed as γ_{i}(t). Let γ_{i}(t)=αU_{i}(t) be the normalized U_{i}(t), where U_{i}(t) is the utility of the i th M2M gateway. α, 0 < α < 1, is a parameter to guarantee the value of γ_{i}(t) lying in the interval [0,1). In this paper, we use an adaptive normalize parameter mechanism, as M2M gateways usually have no prior knowledge of their utilities. The details of the learning algorithm is given in Algorithm 2.
Distributed Network-channel Selection Algorithm Based on Learning Automata.
PPT Slide
Lager Image
Distributed Network-channel Selection Algorithm Based on Learning Automata.
At each instant, the required information of each M2M gateway is the normalized utility after each play and its current action. It does not need to know any prior information of the network. M2M gateways only compute the probabilities (real numbers) of their actions and the base stations just compute the normalized common utilities. So the complexity of proposed DNCSALA is significantly reduced.Since G is a game with common utility, according to the theorem 4.1 in [25], DNCSALA algorithm converges to a pure strategy NE of G if ζ^{s} is sufficiently small. When multiple pure strategy NEs exist, we can run DNCSALA several times and choose the strategy profile with the highest utility.In conventional learning automata, the step size ζ^{s} is a predetermined constant and has great impact on the convergence speed. Normally, the larger ζ^{s} is, the faster DNCSALA will converge. In this paper, we design an adaptive step size mechanism to increase the speed of convergence.Specifically, we define the time-varying step size as
PPT Slide
Lager Image
where T_{1}<T_{2}<…<T_{m}_{-1} are ordered positive integers, T_{m} is defined as positive infinity, ζ^{s}_{1}<ζ^{s}_{2}<…<ζ^{s}_{m}<1 denote the ordered step size values, m is a finite positive integer.We note that this adaptive step size mechanism does not affect our theoretical results, and adaptive step size mechanism is very useful in practice as it can adaptively control the speed of convergence of DNCSALA under a desired level.
Each M2M gateway generates a random number between 0 and 1, and selects an action if the random number locates within the selected range of the action which is determined by its action probability vector.
5. Simulation Results and Performance Analy
In this section, the performance of both IANCSS and DNCSALA is evaluated. Group control is one of the M2M features and the group division is based on location and function. Hence, it is reasonable to assume that an M2M gateway sends a single type of traffic. In simulations, we assume that there are two kinds of gateways: flexible gateway and rigid gateway. The flexible gateway and the rigid gateway only support flexible traffic and rigid traffic, respectively. The parameters of the system are set as follows.Assuming that gateways are randomly set in a rectangular area with the coordinates of four vertexes (-100m,100m), (100m,100m), (-100m,-100m) and (100m,-100m). The number of heterogeneous access networks N is set to 3, and the base stations of these networks are located at coordinates (-90m,0m), (0m,0m) and (90m,0m), respectively. The number of channels provided by each network K_{j} is set to 2, ∀j∈{1,2,3}. The normalized bandwidth of each channel is set as {0.5,0.9,0.5,0.8,1,0.6}. Let
PPT Slide
Lager Image
=3, ∀j∈{1,2,3} and k∈{1,2}, the pass loss factor ϒ=4, and β=10. We assume that all M2M gateways have the same transmitted power P, and the average signal-to-noise SNR=P/σ^{2}. According to the definition of gateways' strategy space, we know that the network-channel selection strategy space of the i th M2M gateway R_{i} is equal to
PPT Slide
Lager Image
. Throughout this section, the performance evaluation is carried out by using MATLAB simulator, and the simulation results in all figures are averaged, via up to 10, 000 independent runs (Monte-Carlo simulation).Firstly, the convergence of our proposed IANCSS algorithm is evaluated. The convergence speed of IANCSS under different numbers of gateways is plotted in Fig. 3, where SNR=5dB. Since the convergence speed of IANCSS is mainly related to initial state and utility function, we assume that all gateways are flexible ones for simplicity. The conclusions can be easily extent to other situations. It can be known from Fig. 3 that the convergence speed is very fast ( no more than 3 iterations when the number of M2M gateways is small ). Furthermore, we find that the number of M2M gateways has little effect on the convergence speed.
Convergence speed of IANCSS under different numbers of gateways when SNR=5dB.
Fig. 4 shows the evolution of the choice probabilities of the M2M gateway's actions (i.e.mixed strategy for DNCSALA ) with the step size ζ^{s}=0.1, ζ^{s}=0.2, ζ^{s}=0.3 and adaptive step size, where SNR=5dB, the number of flexible gateways M_{f} is set to 4, and the number of rigid gateways M_{r} is set to 4. The normalized required bandwidth of 4 rigid gateways b_{req} is {0.5,0.6,0.7,0.7}. We let
PPT Slide
Lager Image
, T_{1}=40, T_{2}=90 for adaptive step size mechanism. It can be seen from Fig. 4 that DNCSALA has a good convergence. When ζ^{s}=0.1, the 4th M2M gateway's strategy converges to the
PPT Slide
Lager Image
after about 300 iterations. When ζ^{s}=0.2, the 4th M2M gateway's strategy converges to the
PPT Slide
Lager Image
after about 100 iterations. When ζ^{s}=0.3, the 4th gateway's strategy converges to the
PPT Slide
Lager Image
after about 80 iterations because of the existence of multiple NEs. When the adaptive step size mechanism is adopted, the 4th gateway's strategy converges to the
PPT Slide
Lager Image
after about 90 iterations. From these results we know that the convergence speed is fast when ζ^{s} is lager and the number of the M2M gateways' strategies is small. Furthermore, DNCSALA may converge to different NEs with the different step sizes ζ^{s} even for the same channel realization.
Evolution of the choice probabilities of the actions (i.e. mixed strategy) of the 4th rigid gateway when SNR=5dB.
Fig. 5 presents the comparison of the sum utility for different algorithms, where M_{f}=4, M_{r}=4 and b_{req}={0.5,0.6,0.7,0.7}. “scheme in [12]” denotes the scheme proposed in [12], in which each gateway selects channel to maximize its throughput and to balance the load of network. “Random selection” scheme means that each M2M gateway selects a channel to access randomly. From Fig. 5, due to using globe information, the performance of IANCSS is most close to that of exhaustive search, and is better than that of DNCSALA. Compared to “scheme in [12]”, our proposed two algorithms have better performance of the sum utility due to the gain obtained by selecting channels according to the characteristics of M2M traffic. While the “scheme in [12]” only considers to maximize network throughput. Also, we can find that the performance gap between the proposed two algorithms and “scheme in [12]” increases as the SNR increasing. Furthermore, without using any information, the performance of “random selection” is worst.
Comparison of performance with the different algorithms when M=8.
We can also see from Fig. 5 that the performance of DNCSALA algorithm decreases as ζ^{s} increasing, since multiple NEs exist in most situations and it is very likely for DNCSALA to miss the optimal (or near-optimal) NE when ζ^{s} is large. For DNCSALA, we can expect that the larger the value of ζ^{s} is, the worse the system performance will become. If the value of ζ^{s} is adequately small, the performance can be improved further, but operation complexity grows. Meanwhile, it can been found that the proposed adaptive step size mechanism can strike a good balance between performance and convergence speed.Fig. 6 shows the effect of the number of gateways on the sum utility among different algorithms, where, for a given number of gateways, half of these gateways is flexible gateway, and the rest is the rigid gateway. The normalized required bandwidth of flexible gateways is randomly set between 0 and 1. It can be seen from Fig. 6 that raising the number of gateways has positive effect on the sum utility when the number of gateway is small. The sum utility decreases if the number of gateways is larger than the saturation point (the saturation point is 8). Due to punishment for the unfeasible solution, the sum utility decreases to zero when the number of gateways exceeds 18 which is the maximum serve capability of the networks. In addition, our proposed two algorithms outperform the “scheme in [12]” and “Random selection” for all number of gateways and different SNR.
The sum utility against the number of gateways with different algorithms .
In Fig. 7, we illustrate the impact of M2M gateway proportions on the sum utility of different algorithms, where SNR=5dB, F-GW and R-GW denote flexible gateway and rigid gateway, respectively. When there are 4 rigid gateways, the normalized required bandwidth of 4 flexible gateways is set to {0.5,0.6,0.7,0.7}. When there are 8 rigid gateways, the normalized required bandwidth of all flexible gateways is set to {0.5,0.6,0.7,0.7,0.5,0.6, 0.7,0.7}. According to (1) and (2), the satisfaction degree of the rigid gateway reduces quickly when the allocated bandwidth is less than the required bandwidth. For flexible gateway, satisfaction degree increases with allocated bandwidth raising. Therefore, the larger the proportion of flexible gateway will lead to higher utility. Furthermore, it can be obtained from Fig. 7 that the sum utility of the “scheme in [12]” keeps fixed for different M2M gateway proportions due to the lack of considering the characteristics of different M2M traffic during the process of network-channel selection.
Comparison of performance with different M2M gateway proportions when SNR=5dB.
Fig. 8 plots the utility of heterogeneous wireless resources for different algorithms, where M_{f}=4, M_{r}=4 and the normalized required bandwidth of 4 flexible gateways b_{req}={0.5,0.6,0.7,0.7}. Load-balance-index L is the reciprocal of the variance of the number of M2M gateways in each channel and can be calculated by (6). When the number of M2M gateways in each channel is more close to the mean value
PPT Slide
Lager Image
, the load-balance degree L is great. Therefore, L can be used to describe the performance of load balance, i.e., utilization of resources. Due to adopt our designed price mechanism of channels, IANCSS, DNCSALA and exhaustive search can achieve the almost same load balance, and are better than “scheme in [12]”, the performance of random select algorithm is worst, which proves that the price mechanism of channel is an efficient way to make gateways selecting different channels and to achieve better load balance. Furthermore, It can be found from Fig. 8 that the SNR has little impact on L.
Comparison of load-balance-index with different algorithm when M=8.
From Fig. 3 to Fig. 8, it can be known that the performance of IANCSS is most close to that of exhaustive search, and the convergence speed of IANCSS is very fast. However, IANCSS needs global information of network and is difficult to realize. By comparison with IANCSS, DNCSALA is a distributed algorithm with limited feedback, and doesn't need the global information. In addition, we can adjust the value of the step size parameter or use adaptive step size mechanism to obtain a tradeoff between the performance and the convergence speed. In summary, DNCSALA is more flexible and practical in contrast with IANCSS.
6. Conclusion
In this paper, a game-theoretic method is adopted to solve the problem of M2M gateways' FNA in heterogeneous wireless networks. We prove that the FNA game is a potential game which exists at least one pure strategy NE, and the sufficient condition for the feasibility of the pure strategy NE is also provided. A iteration algorithm (IANCSS) and a distributed learning algorithm (DNCSALA) are proposed to obtain the pure strategy NE of the proposed game. Simulation results show that although IANCSS has a good performance and the convergence speed of it is very fast, DNCSALA is more practical related to the IANCSS. Compared to the exhaustive search, the proposed two algorithms can achieve a near optimal sum utility of whole network. These two algorithms can also substantially improve the utility of whole network and achieve better load balance under the constraints on network resources compared to the “scheme in [12]” and the “random selection” scheme.
BIO
Hui Tian graduated from Tianjin University in 2009, received his M.S. degree in Communication and Information Systems from PLA University of Science and Technology (PLAUST) in 2012. Now he is a PhD candidate in Nanjing Institute of Communication Engineering, PLAUST, Nanjing China. His research interests are focus on wireless communication, cognitive radio networks, heterogeneous network etc.
Wei Xie is a lecture in the PLAUST, Nanjing China. He received his M.S. degree in Communication and Information Systems from PLAUST in 2002. His research interests include wireless communication systems and networks, cooperative communications and cognitive radio.
Youyun Xu received the Ph.D. degree in information and communication engineering in 1999 from Shanghai Jiao Tong University (SJTU), China. He is currently a professor with Nanjing Institute of Communication Engineering, PLAUST, China. His research interests are focus on new generation wireless mobile communication system (LTE, IMT-Advanced, and Related), advanced channel coding and modulation techniques, multiuser information theory and radio resource management, and cognitive radio networks.
Kui Xu received the B.S. degree in wireless communications from the PLAUST, Nanjing, China in 2004, and the Ph.D. degree in software defined radio from the PLAUST, Nanjing, China, in 2009. He is currently a lecturer in the College of Communications Engineering, PLAUST. From Dec. 2013, he was a Postdoctoral Fellow with PLAUST. His research interests include broadband wireless communications, signal processing for communications, network coding, wireless communication networks.
Peng Han was born in Changchun, Jilin province, China. He graduated from Dalian Maritime University in 2010, and received his M.S. degree in Communication and Information Systems from PLAUST in 2013, Nanjing China. His research interests are focus on wireless communication, cognitive radio networks, etc.
Wu Geng
,
Talwar Shilpa
,
Johnsson Kerstin
,
Himayat Nageen
,
Johnson Kevin D.
2011
“M2M: From Mobile to Embedded Internet,”
IEEE Communications Magazine
49
(4)
36 -
43
DOI : 10.1109/MCOM.2011.5741144
Wang Kun
,
Alonso-Zarate Jesus
,
Dohler Mischa
“Energy-Efficiency of LTE for Small Data Machine-to-Machine Communications,”
in Proc. of IEEE ICC
2013
4020 -
4024
Jo Minho
,
Maksymyuk Taras
,
Bastista Rodrigo L.
,
Maciel Tarcisio F.
,
De Almeida Ndre L.F.
,
Klymash Mykhailo
2014
“A Survey of Converging Solutions for Heterogeneous Mobile Networks,”
IEEE Wireless Communications
21
(8)
54 -
62
Liu Yi
,
Yuen Chau
,
Cao Xianghui
,
Hassan Naveed Ul
,
Chen Jiming
2014
“Design of a Scalable Hybrid MAC Protocol for Heterogeneous M2M Networks,”
IEEE Internet of Things Journal
1
(1)
99 -
111
DOI : 10.1109/JIOT.2014.2310425
Jo Minho
,
Maksymyuk Taras
,
Strykhalyuk Bohdan
,
Cho Choong-Ho
2015
“Device-to-Device (D2D) Based Heterogeneous Radio Access Network Architecture for Mobile Cloud Computing,”
IEEE Wireless Communications
12
(3)
Kumar Abhinav
,
Mallik Ranjan K.
,
Schober Robert
2014
“A Probabilistic Approach to Modeling Users’ Network Selection in the Presence of Heterogeneous Wireless Networks,”
IEEE Transactions on Vehicular Technology
63
(7)
3331 -
3341
DOI : 10.1109/TVT.2013.2297437
Ye Qiaoyang
,
Rong Beiyu
,
Chen Yudong
,
Al-Shalash Mazin
,
Caramanis Constantine
,
Andrews Jeffrey G.
2013
“User Association for Load Balancing in Heterogeneous Cellular Networks,”
IEEE Transactions on Wireless Communications
12
(6)
2706 -
2716
DOI : 10.1109/TWC.2013.040413.120676
Mesodiakaki Agapi
,
Adelantado Ferran
,
Alonso Luis
,
Verikoukis Christos
“Energy-efficient Context-aware User Association for Outdoor Small Cell Heterogeneous Networks,”
in Proc. of IEEE ICC
2014
1614 -
1619
Chang B.
,
Chen J.
2008
“Cross-layer-based adaptive vertical handoff with predictive RSS in heterogeneous wireless networks,”
IEEE Transactions on Vehicular Technology
57
(6)
3679 -
3692
DOI : 10.1109/TVT.2008.921619
Elias Jocelyne
,
Martignon Fabio
,
Chen Lin
,
Altman Eitan
2013
“Joint Operator Pricing and Network Selection Game in Cognitive Radio Networks: Equilibrium, System Dynamics and Price of Anarchy,”
IEEE Transactions on Vehicular Technology
62
(9)
4576 -
4589
DOI : 10.1109/TVT.2013.2264294
Wang Lusheng
,
Kuo Geng-Sheng
2013
“Mathematical Modeling for Network Selection in Heterogeneous Wireless Networks – A Tutorial,”
IEEE Communications Surveys and Tutorials
15
(1)
271 -
292
DOI : 10.1109/SURV.2012.010912.00044
Konka Jakub
,
Andonovic Ivan
,
Michie Craig
,
Atkinson Robert
2014
“Auction-Based Network Selection in a Market-Based Framework for Trading Wireless Communication Services,”
IEEE Transactions on Vehicular Technology
63
(3)
1365 -
1377
DOI : 10.1109/TVT.2013.2280344
Shafiq M. Zubair
,
Liu Lusheng Ji
,
Alex X.
,
Pang Jeffrey
,
Wang Jia
2013
“Large-Scale Measurement and Characterization of Cellular Machine-to-Machine Traffic,”
IEEE/ACM Transactions on Networking
21
(6)
1960 -
1973
DOI : 10.1109/TNET.2013.2256431
Sastry P.S
1994
“Decentralized learning of Nash Equilibria in Multi-Person Stochastic Games with Incomplete Information,”
IEEE Transactions on Systems Man and Cybernetics
24
769 -
777
DOI : 10.1109/21.293490
@article{ E1KOBZ_2015_v9n10_3789}
,title={A Flexible Network Access Scheme for M2M Communications in Heterogeneous Wireless Networks}
,volume={10}
, url={http://dx.doi.org/10.3837/tiis.2015.10.002}, DOI={10.3837/tiis.2015.10.002}
, number= {10}
, journal={KSII Transactions on Internet and Information Systems (TIIS)}
, publisher={Korean Society for Internet Information}
, author={Tian, Hui
and
Xie, Wei
and
Xu, Youyun
and
Xu, Kui
and
Han, Peng}
, year={2015}
, month={Oct}
TY - JOUR
T2 - KSII Transactions on Internet and Information Systems (TIIS)
AU - Tian, Hui
AU - Xie, Wei
AU - Xu, Youyun
AU - Xu, Kui
AU - Han, Peng
SN - 1976-7277
TI - A Flexible Network Access Scheme for M2M Communications in Heterogeneous Wireless Networks
VL - 9
PB - Korean Society for Internet Information
DO - 10.3837/tiis.2015.10.002
PY - 2015
UR - http://dx.doi.org/10.3837/tiis.2015.10.002
ER -
Tian, H.
,
Xie, W.
,
Xu, Y.
,
Xu, K.
,
&
Han, P.
( 2015).
A Flexible Network Access Scheme for M2M Communications in Heterogeneous Wireless Networks.
KSII Transactions on Internet and Information Systems (TIIS),
9
(10)
Korean Society for Internet Information.
doi:10.3837/tiis.2015.10.002
Tian, H
et al.
2015,
A Flexible Network Access Scheme for M2M Communications in Heterogeneous Wireless Networks,
KSII Transactions on Internet and Information Systems (TIIS),
vol. 10,
no. 10,
Retrieved from http://dx.doi.org/10.3837/tiis.2015.10.002
[1]
H Tian
,
W Xie
,
Y Xu
,
K Xu
,
and
P Han
,
“A Flexible Network Access Scheme for M2M Communications in Heterogeneous Wireless Networks”,
KSII Transactions on Internet and Information Systems (TIIS),
vol. 10,
no. 10,
Oct
2015.
Tian, Hui
Xie, Wei
Xu, Youyun
et al.
“A Flexible Network Access Scheme for M2M Communications in Heterogeneous Wireless Networks”
KSII Transactions on Internet and Information Systems (TIIS),
10.
10
2015:
Tian, H
,
Xie, W
,
Xu, Y
,
Xu, K
,
Han, P
A Flexible Network Access Scheme for M2M Communications in Heterogeneous Wireless Networks.
KSII Transactions on Internet and Information Systems (TIIS)
[Internet].
2015.
Oct ;
10
(10)
Available from http://dx.doi.org/10.3837/tiis.2015.10.002
Tian, Hui
,
Xie, Wei
,
Xu, Youyun
,
Xu, Kui
,
and
Han, Peng
,
“A Flexible Network Access Scheme for M2M Communications in Heterogeneous Wireless Networks.”
KSII Transactions on Internet and Information Systems (TIIS)
10
no.10
()
Oct,
2015):
http://dx.doi.org/10.3837/tiis.2015.10.002