A Game-Theoretic Analysis of Multiple Protocol Data Flows in Hierarchical M2M Communication Networks

Abstract

A hierarchical machine-to-machine (M2M) communication network, where multiple heterogeneous devices compete for transmission on congested links, is considered. In such a network, the cluster headers gather the network coding and routing messages from multiple M2M devices and forward them to the cellular network. We propose a novel discriminatory user-based utility mechanism for network coding users and routing users. The price of anarchy (PoA), which is used to characterize the worst-case efficiency bounds, is analyzed. The simulation results show that network coding could promote the efficiency to a certain extent.

1. Introduction

With the increasing development of the mobile communications and the expansion of the internet applications, the machine-to-machine (M2M) technologies are driving demands. The M2M communication networks are carried out as an integration of different techniques including transducer technologies, computer software, and data communications. In particular, the M2M communications provide diverse application scenarios compared to those of traditional communications among humans, where numerous sensor nodes and massive data are in need. The features, that are infrequent data transmissions and functions of group-based operations, are inherent from human-to-human communications [1].

Since a great number of self-organized nodes offer the information sources or the command execution without human intervention, these nodes can also be considered to carry the selfish or self-benefited features to take actions [2]. Thus, the M2M network is more likely to get congested especially when massive selfish nodes act to maximize each individual benefit. In order to overcome such a problem, the idea of game theory over the strategic behaviors of selfish users can be further studied [3–5].

With the advent of network coding [6], nodes are allowed to process the incoming independent information flows before forwarding them to communication networks. Network coding has been acknowledged to offer benefits along various dimensions of communication networks such as wireless resources, throughput, and security [7]. Particularly, in [8], it has been confirmed that as an effective means of efficient reliable data dissemination, network coding plays a key role in developing the M2M communication networks. In addition, combined with traditional routing schemes, alternative strategies can also be carried out in M2M communications [9].

Using the well-known game theory together with the network coding, in this paper, we propose a game model with the existence of Nash equilibrium (NE) [10] in M2M communication networks. In particular, we analyze the price of anarchy (PoA) in a cognitive M2M communication system with a hierarchical structure and cluster headers, where the tremendous information which contains the data packets and signaling messages is issued by a significant number of mobile devices. Assuming that the number of source devices in machine type communication (MTC) is the same as the number of nodes in the network, the nodes can be regarded as the network users who can also be classified as network coding users or routing users depending on different transmission patterns. The main idea is that different behaviors of different sorts of users, which are considered to maximize each individual surplus, can influence the efficiency of the whole system.

Consider a cloud-based M2M network in Figure 1, where a number of machine nodes transmit message to the same amount of receivers through one simple link. Each M2M device selects a nearby cluster header as its desired access point. Cluster header gathers the total amount of members that belong to it and then broadcasts the information to each member and the enhanced Node Bs (eNBs). After that, the eNBs constructs the connections between the two clusters, and each device selects its own strategies. With the inferences of the PoA which is adopted to measure the efficiency of the system, the network coding and routing can be regenerated to improve the PoA, whether the link is congested or not. The formulations of PoA under the conditions of the link being congested or unrestricted can be obtained. It can be observed that the clues are concluded to induct the resources allocation to achieve a better efficiency according to the consistence of different sorts of users.

Figure 1

Hierarchical system in cognitive M2M communication.

The rest of the paper is organized as follows. In Section 2, the related works with respect to the resource allocation methods in M2M communication, network coding, and pricing mechanisms are summarized. Section 3 proposes the network model including the game model, calculating functions, and some definitions. Section 4 illustrates the transmission game and the corresponding conclusions. Simulations in Section 5 show the envisioned curves of the PoA under different conditions. The paper is finally concluded in Section 6 with future works.

2. Related Work

A cognitive M2M communication system has been proposed in [11], in which the cluster headers gather the traffic information from multiple M2M devices using cognitive radio technologies in cellular bands and forward it to the cellular networks. In this case, the number of M2M devices that directly access the cellular network is decreased and the cellular network only needs to manage the transmission among the header nodes and the reduced M2M devices. It has been confirmed in [11] that the congestion or overload of the control signal can be avoided or resolved using the corresponding structure, while an effective way has been considered in [12] to promote energy efficiency. In [13], the 3GPP concept and the network operation have been presented where different solutions have been provided to release the congestion in the radio as well as the core network, by allocating different priorities for different users to access the network. Based on the 3GPP standard, the overview of the M2M and LTE network architectures has been presented in [14]. However, the detailed operations and the corresponding results or influences have not been well demonstrated. In order to develop efficient mechanisms to handle congestion settlements due to signaling messages which are issued by massive numbers of mobile devices, [15] has proposed the mechanisms for signaling congestion settlements to minimize the frequency of attempts or disallow the connection from the devices to the network. In addition, it has been demonstrated in [16] that different protocols can be carried out to improve controlling congestion and overload problems over MTC devices.

As to the network coding, it has been confirmed in [17] that resource allocation games with routing can be utilized to improve the throughput in a single line bottleneck link of wireless networks. This work has been extended in [18], where joint intersession network coding has been first considered and the discriminatory pricing functions of routing and network coding which is based on the affine marginal cost (AMC) pricing mechanism in [17] have been developed. Note that since the link capacity has not been considered in the above literature, the efficiency and optimization of resource allocations may not be achieved for the network coding in M2M networks.

Similar to the market regulation of price in economics, the pricing mechanism is an effective means to allocate resources. The widely known pricing mechanism is the AMC mentioned above. However, as the AMC does not consider the number of users sharing the resources, the average cost-sharing (ACS) pricing mechanism has been developed in [19]. Note that ACS takes not only the total rates through the sharing link but also the number of sharing users into consideration. Thus, the ACS pricing mechanism is more appropriate for the issues as we will discuss.

3. Network Model

Let us simplify the M2M communication architecture in Figure 1 to a congestion control model which is shown in Figure 2.

Figure 2

A link shared by K users, containing one network coding flow and R routing flows.

We assume that there are $R\hspace{0.17em}\hspace{0.17em}(R\ge 1)$ routing users together with $N\hspace{0.17em}\hspace{0.17em}(N\ge 2)$ network coding users, while the total number of users is $K=N+R$ . The set of coding users is denoted by $N=\{\mathrm{1,2},\dots ,N\}$ . For each user, $i\in N$ , $r_{\text{NC}}$ is the coding rate of each network coding user. For all routing users, $q={\sum }_{i=1}^R{r}_i$ represents the sum of routing rates, while $r_i$ is the transmission rate of routing user $i\in R=\{\mathrm{1,2},\dots ,R\}$ .

Nodes W and Z represent two cluster headers. Each user is offered with the system information that contains the utility functions and the price or cost formulations. A congestion communication link between two intermediate nodes, W and Z, is given by $(W;Z)$ . The intermediate node W performs the linear network coding on packets of N NC users. The node W delivers network coding packets together with routing packets to node Z, and then node Z forwards these packets to the corresponding destinations. Thus, the sum rate over link $(W;Z)$ becomes $q+r_{\text{NC}}$ . Notice that the link will be overloaded if it exceeds the fixed link capacity C, that is, $q+r_{\text{NC}}=r_{\text{NC}}+{\sum }_{i=1}^R{r}_i\le C$ .

In the following, we will introduce the game model and its related computing methods or functions.

3.1. Game Model

• (i)

Players: users in set K.

(ii)

Strategies: transmission rates ${\sum }_i{r}_i$ and data transmission options.

(iii)

Payoffs: surplus of one user $S_i(r_i)$ and the whole system ${\sum }_{i=1}^K{S}_i(r_i)$ .

Although each user prefers to make a decision to choose a transmission mode between routing and network coding to acquire its own payoffs, maximizing the payoffs of the whole system is the main target.

3.2. Utility, Cost, and Price Functions

The utility function $U(r_i)$ quantifies the user i's payoff in terms of its desired transmission rate $r_i$ ; here $i\in K$ . In this paper, we propose a novel discriminatory user-based utility mechanism, which is defined as follows.

Definition 1.

For each network coding user, its transmission rate is $r_{\text{NC}}$ , and then the utility function is $U(r_{\text{NC}})={\gamma }_{\text{NC}}·r_{\text{NC}}$ . For each routing user $i\in R$ , the utility function is $U(r_i)={\gamma }_R·r_i$ . Here, both ${\gamma }_{\text{NC}}$ and ${\gamma }_R$ are utility parameters, which are in the interval (0,1].

Obviously, the utility parameters depend on the transmission mode. Without the loss of generality, the utility function is assumed to be nonnegative, concave, increasing, and differentiable, which is the same as the one defined in [17].

The function $C(r_i)$ is a monetary cost for utilizing the link resource, which is defined as follows.

Definition 2.

For each user $i\in K$ , if its transmission rate is $r_i$ , the cost function $C(r_i)=r_i·p(·)$ . Here, $p(·)$ denotes the price function depending on the transmission mode.

In the following, we formulate the resource allocation problem in the hierarchical M2M communication networks under the proposed discriminatory user-based utility mechanism. An efficient rate allocation can be characterized as an optimal solution of the following aggregate surplus maximization with network coding and routing (SMNCR) problem [18]:

SMNCR Problem

$$\begin{array}{l}S\left(\sum _i{r}_i\right)=\sum _{i}U\left(r_i\right)-\sum _{i}C\left(r_i\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\sum _{i=\mathrm{1}}^N\left({\gamma }_{\text{NC}}·r_{\text{NC}}-C\left(r_i\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\sum _{i=\mathrm{1}}^R\left({\gamma }_R·r_i-C\left(r_i\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\text{s}.\text{t}.\hspace{1em}{r}_i\ge \mathrm{0},\hspace{1em}i=\mathrm{1},\dots ,K.\end{array}$$

(1)

The ACS pricing mechanism takes both the numbers of sharing users and the total rates through the sharing link into consideration. Reference [19] defines it as follows.

Definition 3.

Assume there are n users. To each user i, $i=\mathrm{1,2},\dots ,n$ , its transmission rate is given by $r_i$ . Then, the ACS pricing function is defined as $p({\sum }_i{r}_i/n)$ .

Notice that the linear price functions are the only price functions that can satisfy the four axioms of additivity, rescaling, consistency, and positivity for cost-sharing systems at the same time [20, 21]. Suppose that $p(x)=a·x$ , where the parameter a is a constant real number and $a>0$ . To all network coding users, the transmission rate is $r_{\text{NC}}$ , while they share the same link resource. Hence, the cost function becomes

$$\begin{array}{cc}& C\left(r_{\text{NC}}\right)=r_{\text{NC}}·p\left(\frac{r_{\text{NC}}}{N}\right)=\frac{a·r_{\text{NC}}^{\mathrm{2}}}{N}.\end{array}$$

(2)

Then, to routing user $i\in R$ , the cost function is given by

$$\begin{array}{cc}& C\left(r_i\right)=r_i·p\left(\frac{{\sum }_i{r}_i}{R}\right)=\frac{a·r_i·q}{R}.\end{array}$$

(3)

In the next section, we will analyze the existence of NE [8] and formulate the corresponding efficiency in terms of the PoA.

3.3. NE and PoA

The selfish nature of players leads to undesirable and inefficient network performances. The selfish behavior is mainly presented by choosing the strategies to maximize its own payoffs without the consideration of the utility of the whole system. An NE is an action profile with the property that no single player can obtain a higher payoff by deviating unilaterally from the profile.

The NE of a game can be defined as a rate vector ${\mathit{r}}^{*}$ such that for any user $i\in K$ , we have $S(r_i^{*},{\mathit{r}}_{-i}^{*})\ge S(r_i,{\mathit{r}}_{-i}^{*})$ , for all $r_i\ge 0$ . Here, ${\mathit{r}}_{-i}^{*}$ denotes the vector of all rates chosen by users other than ith. The existence of NE in the proposed game model is analyzed as follows.

Suppose that for user $i\in K$ , its transmission rate is $r_i$ . At first, we analyze the existence of $r_i^{*}$ . According to (1) and Definitions 1 and 2, the utility function is $U(r_i)={\gamma }_i·r_i$ and the cost function is $C(r_i)=r_i·p(r_i)$ ; then we can obtain

$$\begin{array}{l}F\left(r_i\right)=\frac{\partial S_i\left(r_i,{\mathit{r}}_{-i}\right)}{\partial r_i}=\frac{\partial U\left(r_i\right)}{\partial r_i}-\frac{\partial C\left(r_i\right)}{\partial r_i}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}={\gamma }_i-p\left(r_i\right)-r_i\frac{\partial p\left(r_i\right)}{\partial r_i}.\end{array}$$

(4)

The condition to maximize the individual surplus $S(r_i)$ is given by $F(r_i)=\partial S(r_i,{\mathit{r}}_{-i})/\partial r_i=0$ .

Furthermore, since $\partial F(r_i)/\partial r_i=-2\partial p(r)/\partial r_i<0$ , $F(r_i)$ is a monotone decreasing function. Then, we can infer that the transmission rate $r_i^{*}$ exists and becomes the only solution when the price function $p(r_i)$ is given.

Based on the above analysis, we can conclude that an NE solution exists. Here, we only consider the two blocks of resources allocated to two sets of NC and routing users, respectively, instead of performing an individual resource allocation to each user. As a result, given the block of resource allocated to the routing users, each individual routing user's transmission rate depends on other routing users. Thus, NE is nonunique for this game model under the ACS pricing mechanism. After that, we can assess the efficiency of the network resource allocation by the PoA. The PoA is the worst-case efficiency of the NE among all possible choices of parameters, that is, the number of users, the utility, cost, and price functions.

Let $S^O(\mathit{r})$ be an optimal solution of SMNCR Problem and let $S^{*}(\mathit{r})$ be the NE of the game under the same system parameters. We can define the PoA as follows:

$$\begin{array}{cc}& \text{PoA}=\frac{{\min }_r{S}^{*}\left(\mathit{r}\right)}{{\max }_r{S}^O\left(\mathit{r}\right)}.\end{array}$$

(5)

The main purpose in this paper is to find the appropriate transmission strategies by analyzing the PoA under the discriminatory user-based utility mechanism. A detailed discussion is offered in the next section.

4. The PoA Analysis

In this section, we aim to find the effectiveness of the discriminatory user-based utility mechanism in the proposed game model. The PoA analysis is divided into three parts, i.e., the NC users' NE solutions, the routing users' NE solutions, and the optimal solutions of SMNCR Problem. Assume that the NC users have the priority to determine their coding rate. After that, each routing user select their own rate either under the conditions of the congestion or not. The optimal solutions may also adapt to the condition. Finally, the formulation of PoA is acquired.

Proposition 4.

For each network coding user $i\in N$ , its transmission rate is denoted by $r_i=r_{NC}$ , the NE solution is given by $r_{NC}^{*}=N·r_{NC}/\mathrm{2}a$ , and the corresponding surplus of network coding group becomes $S_{NC}^{*}=N^{\mathrm{2}}·{\gamma }_{NC}^2/\mathrm{4}a$ .

Proof.

According to Definitions 1 and 2, (1), and (2), we have

$$\begin{array}{cc}& S_i\left(r_{\text{NC}}\right)=U\left(r_{\text{NC}}\right)-C\left(r_{\text{NC}}\right)={\gamma }_{\text{NC}}·r_{\text{NC}}-{a·r}_{\text{NC}}·\frac{r_{\text{NC}}}{N}.\end{array}$$

(6)

Taking the derivative of (6) with respect to $r_{\text{NC}}$ and we can show that

$$\begin{array}{cc}& S_i^{\prime }\left(r_{\text{NC}}\right)={\gamma }_{\text{NC}}-\mathrm{2}·a·\frac{r_{\text{NC}}}{N}.\end{array}$$

(7)

Let the above equation be zero and we can obtain $r_{\text{NC}}^{*}=N·{\gamma }_{\text{NC}}/2a$ . Then, the surplus of the user becomes $S_i^{*}=N·{\gamma }_{\text{NC}}^2/4a$ , and the accumulation surplus of the network coding group is given by

$$\begin{array}{cc}& S_{\text{NC}}^{*}=N·S_i^{*}=\frac{N^{\mathrm{2}}·{\gamma }_{\text{NC}}^{\mathrm{2}}}{\mathrm{4}a}.\end{array}$$

(8)

Proposition 5.

Without congestion, one has

$$\begin{array}{cc}& \text{PoA}\mathbf{\ge }\frac{N^{\mathrm{2}}·{\gamma }_{NC}^{\mathrm{2}}·{\left(R+\mathrm{1}\right)}^{\mathrm{2}}+\mathrm{4}{R}^{\mathrm{2}}·{\gamma }_R^{\mathrm{2}}}{N^{\mathrm{2}}·{\gamma }_{NC}^{\mathrm{2}}·{\left(R+\mathrm{1}\right)}^{\mathrm{2}}+R·{\gamma }_R^{\mathrm{2}}·{\left(R+\mathrm{1}\right)}^{\mathrm{2}}}.\end{array}$$

(9)

Proof.

According to Definitions 1 and 2, (1), and (3), for routing user $i\in R$ , we can show that

$$\begin{array}{l}{S}_i\left(r_i\right)=U\left(r_i\right)-C\left(r_i\right)\\ \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}={\gamma }_R·r_i-a·r_i·\frac{{\sum }_i^R{r}_i}{R}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}={\gamma }_R·r_i-a·r_i·\frac{q}{R}.\end{array}$$

(10)

Taking the derivative of (10) with respect to $r_i$ , we have

$$\begin{array}{cc}& \frac{\partial S_i\left(r_i\right)}{\partial r_i}={\gamma }_R-a·\frac{q}{R}-a·r_i·\frac{\mathrm{1}}{R}.\end{array}$$

(11)

Since without any congestion, each routing user just selects its own rate to maximize (10). Due to the symmetry in [22], it is given that ${q^{*}=R·r}_i^{*}$ . Let (11) be zero and $r_i^{*}=R·{\gamma }_R/a(R+1)$ . Then, the surplus $S_i^{*}=R·{\gamma }_R^2/a{(R+1)}^2$ and the accumulation surplus of the routing group is given by

$$\begin{array}{cc}& S_R^{*}=R·S_i^{*}=\frac{R^{\mathrm{2}}·{\gamma }_R^{\mathrm{2}}}{a{\left(R+\mathrm{1}\right)}^{\mathrm{2}}}.\end{array}$$

(12)

According to (1), the total surplus of the system becomes

$$\begin{array}{l}S\left(\sum _i{r}_i\right)=\sum _{i=\mathrm{1}}^N\left({\gamma }_{\text{NC}}·r_{\text{NC}}-C\left(r_i\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}+\sum _{i=\mathrm{1}}^R\left({\gamma }_R·r_i-C\left(r_i\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=N·{\gamma }_{\text{NC}}·r_{\text{NC}}-N·{a·r}_{\text{NC}}·\frac{r_{\text{NC}}}{N}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}+{\gamma }_R·{\sum }_i^R{r}_i-a·{\sum }_i^R{r}_i·\frac{{\sum }_i^R{r}_i}{R}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=N·{\gamma }_{\text{NC}}·r_{\text{NC}}-a·r_{\text{NC}}^2\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}+{\gamma }_R·q-a·\frac{q^2}{R}.\end{array}$$

(13)

While the network is not yet congested, the q and $r_{\text{NC}}$ are independent of each other. Thus, taking the derivative of q or $r_{\text{NC}}$ , respectively, the optimal solution can be obtained as follows:

$$\begin{array}{cc}& \frac{\partial \left(N·{\gamma }_{\text{NC}}·r_{\text{NC}}-a·r_{\text{NC}}^{\mathrm{2}}\right)}{\partial r_{\text{NC}}}=\mathrm{0},\\ \frac{\partial ({\gamma }_R·q-a·q^{\mathrm{2}}/R)}{\partial q}=\mathrm{0},\\ \Downarrow \\ r_{\text{NC}}^O=\frac{N·r_{\text{NC}}}{\mathrm{2}a},\\ q^O=\frac{R·r_R}{\mathrm{2}a}.\end{array}$$

(14)

Then, the surplus maximums of two groups are, respectively, calculated as

$$\begin{array}{l}{S}_{\text{NC}}^O=N·{\gamma }_{\text{NC}}·r_{\text{NC}}^O-a·{\left(r_{\text{NC}}^O\right)}^{\mathrm{2}}=\frac{N^{\mathrm{2}}·{\gamma }_{\text{NC}}^{\mathrm{2}}}{\mathrm{4}a},\\ \hspace{1em}{S}_R^O={\sum }_{i=1}^{R}U\left(r_i\right)-{\sum }_{i=1}^{R}C\left(r_i\right)\\ \hspace{1em}\hspace{1em}\hspace{0.17em}={\gamma }_R·q^O-a·\frac{{\left(q^O\right)}^2}{R}=\frac{R·r_R^2}{4a}.\end{array}$$

(15)

According to (8), (12), (15), and the definition of PoA, we have

$$\begin{array}{l}\text{PoA}=\frac{{\min }_r{S}^{*}\left(\mathit{r}\right)}{{\max }_r{S}^O\left(\mathit{r}\right)}\\ \hspace{1em}\hspace{1em}\ge \frac{{\sum }_{i=\mathrm{1}}^{K}U\left(r_i^{*}\right)-{\sum }_{i=\mathrm{1}}^{K}C\left(r_i^{*}\right)}{{\sum }_{i=\mathrm{1}}^{K}U\left(r_i^O\right)-{\sum }_{i=\mathrm{1}}^{K}C\left(r_i^O\right)}\\ \hspace{1em}\hspace{1em}\ge \frac{N^{\mathrm{2}}·{\gamma }_{\text{NC}}^{\mathrm{2}}/\mathrm{4}a+R^{\mathrm{2}}·{\gamma }_R^{\mathrm{2}}/a{\left(R+\mathrm{1}\right)}^{\mathrm{2}}}{N^{\mathrm{2}}·{\gamma }_{\text{NC}}^{\mathrm{2}}/\mathrm{4}a+R·r_R^{\mathrm{2}}/\mathrm{4}a}.\end{array}$$

(16)

Proposition 6.

In congestion, one has

$$\begin{array}{cc}& PoA\mathbf{\ge }\frac{\left(N^{\mathrm{2}}·{\gamma }_{NC}^{\mathrm{2}}/\mathrm{4}a\right)+\left(\left(\mathrm{2}a-N·{\gamma }_{NC}\right)\left(\mathrm{2}{\gamma }_R-\mathrm{2}aC+N·{\gamma }_{NC}\right)/\mathrm{4}a\right)}{\left(a\left(R\text{+1}\right)/R\right)·{\left[\left(NR·{\gamma }_{NC}-R·{\gamma }_R+\mathrm{2}aC\right)/\mathrm{2}a\left(R+\mathrm{1}\right)\right]}^{\mathrm{2}}+C·{\gamma }_R-\left(a{C}^{\mathrm{2}}/R\right)}.\end{array}$$

(17)

Proof.

Once the congestion occurs, the worst NE solution is considered as the total resource for all the routing users is allocated to only one user [14], that is, $r_i^{*}=q^{*}=C-r_{\text{NC}}^{*}=C-N·{\gamma }_{\text{NC}}/2a$ ,   $r_1^{*}=\cdots =r_{i-1}^{*}=r_{i+1}^{*}=r_R^{*}=0$ . Therefore, in this case, the pricing function becomes ${p(r}_i^{*})$ . According to (10), the surplus of the routing group is given by

$$\begin{array}{l}{S}_R^{*}={\gamma }_R·r_i^{*}-a·r_i^{*}·\frac{q^{*}}{\mathrm{1}}\\ \hspace{1em}=\frac{\left(\mathrm{2}a-N·{\gamma }_{\text{NC}}\right)\left(\mathrm{2}{\gamma }_R-\mathrm{2}aC+N·{\gamma }_{\text{NC}}\right)}{\mathrm{4}a}.\end{array}$$

(18)

Then, the global optimal surplus is obtained as follows:

$$\begin{array}{l}S\left(\sum _{i\in K}{r}_i\right)=N·{\gamma }_{\text{NC}}·r_{\text{NC}}-a·r_{\text{NC}}^{\mathrm{2}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\gamma }_R·q-a·\frac{q^{\mathrm{2}}}{R}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=N·{\gamma }_{\text{NC}}·r_{\text{NC}}-a·r_{\text{NC}}^{\mathrm{2}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\gamma }_R·\left(C-r_{\text{NC}}\right)-a·\frac{{\left(C-r_{\text{NC}}\right)}^{\mathrm{2}}}{R}.\end{array}$$

(19)

Taking the derivative of (19) with respect to $r_{\text{NC}}$ , we can have

$$\begin{array}{cc}& r_{\text{NC}}^O=\frac{NR·{\gamma }_{\text{NC}}-R·{\gamma }_R+\mathrm{2}aC}{\mathrm{2}a\left(R+\mathrm{1}\right)},\end{array}$$

(20)

while the optimal surplus is given by

$$\begin{array}{l}{S}^O\left(\sum _i{r}_i\right)=N·{\gamma }_{\text{NC}}·r_{\text{NC}}^O-a·{\left(r_{\text{NC}}^O\right)}^{\mathrm{2}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\gamma }_R·\left(C-r_{\text{NC}}^O\right)-a·\frac{{\left(C-r_{\text{NC}}^O\right)}^2}{R}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\frac{a\left(R+1\right)}{R}·{\left[\frac{NR·{\gamma }_{\text{NC}}-R·{\gamma }_R+\mathrm{2}aC}{\mathrm{2}a\left(R+\mathrm{1}\right)}\right]}^{\mathrm{2}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+C·{\gamma }_R-\frac{a{C}^{\mathrm{2}}}{R}.\end{array}$$

(21)

In addition, according to the definition of PoA, (8), (18), and (21), we have

$$\begin{array}{l}\text{PoA}=\frac{{\min }_r{S}^{*}\left(\mathit{r}\right)}{{\max }_r{S}^O\left(\mathit{r}\right)}\\ \hspace{1em}\hspace{1em}\ge \frac{{\sum }_{i=\mathrm{1}}^{K}U\left(r_i^{*}\right)-{\sum }_{i=\mathrm{1}}^{K}C\left(r_i^{*}\right)}{{\sum }_{i=\mathrm{1}}^{K}U\left(r_i^O\right)-{\sum }_{i=\mathrm{1}}^{K}C\left(r_i^O\right)}\\ \hspace{1em}\hspace{1em}\ge (\frac{N^{\mathrm{2}}·{\gamma }_{\text{NC}}^{\mathrm{2}}}{\mathrm{4}a}\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\left(\mathrm{2}a-N·{\gamma }_{\text{NC}}\right)\left(\mathrm{2}{\gamma }_R-\mathrm{2}aC+N·{\gamma }_{\text{NC}}\right)}{\mathrm{4}a})\\ \hspace{1em}\hspace{1em}\hspace{1em}\times (\phantom{\frac{a{C}^{\mathrm{2}}}{R}}\frac{a\left(R+1\right)}{R}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·{\left[\frac{NR·{\gamma }_{\text{NC}}-R·{\gamma }_R+\mathrm{2}aC}{\mathrm{2}a\left(R+\mathrm{1}\right)}\right]}^{\mathrm{2}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{+C·{\gamma }_R-\frac{a{C}^{\mathrm{2}}}{R})}^{-1}.\end{array}$$

(22)

5. Simulation and Numerical Results

In this section, we evaluate the performances of ACS pricing mechanism with choices of different parameters including N, R, ${\gamma }_{\text{NC}}$ , and ${\gamma }_R$ . It is assumed that the link capacity $C=1$ and the pricing parameter $a=1$ . The utility ratio $\eta ={\gamma }_{\text{NC}}/{\gamma }_R$ is defined to formulate the PoA.

Firstly, let us suppose that the number of the NC users equals that of routing users, that is, $N=R$ . Here, we consider that the PoA when $N=R$ varies from 2 to 100 with $\eta =\mathrm{4,2},\mathrm{1,0.5}$ , respectively. The corresponding results are shown in Figure 3.

Figure 3

When $N=R$ , the PoA varies with the N or R and η.

As illustrated in Figure 3, when the utility parameter becomes $\eta =\mathrm{1}$ and $\eta =\mathrm{2}$ , respectively, the corresponding PoA approaches to 1, which means that the efficiency of the system is maximized. When $\eta =\mathrm{2}$ , with the increased number of users, the PoA is approximately 77%. On the other hand, when $\eta =\mathrm{4}$ (i.e., ${\gamma }_{\text{NC}}=4{\gamma }_R$ ), the PoA is decreased to approximately 51%, which is surprisingly lower than those of the other three cases. The result shows that the utility gap between network coding and routing cannot be too large.

Let $N=2$ , where η is the counterpart of the β in [15]. In Figure 4, it is shown that when $N=2$ , the PoA is reduced to almost 5%, which indicates that as the proportion of NC users is lower than that of routing users, the ACS pricing mechanism could not provide better performance compared to the AMC pricing mechanism [13].

Figure 4

Efficiency (PoA) at an NE of 100 randomly generated resource allocation game scenarios when $N=2$ .

Under the same conditions, it is worthy to compare our proposed schemes to those in [14], where only two coding users are considered. With the number of the routing users varying from 0 to 100, as R is not very large, for example, $R<10$ , the uniform utility parameter mechanism functions well as shown in Figure 5. However, the increasing of routing users leads to a sharp decline of PoA if $\eta =\mathrm{1}$ or 1/2 as shown in Figure 5. Specifically, it also shows that as $\eta =\mathrm{2}$ or 4, the PoA becomes much more stable. In addition, when $R>10$ , which is always the case, the discriminatory utility mechanism is in advantage obviously.

Figure 5

The PoA varies when $N=2$ and R is from 0 to 100.

Moreover, we make a research into the question whether the proportions of coding users or routing users in the whole users have an influence on PoA. The results are illustrated, respectively, in Figure 6, where the higher proportion of the network coding user leads to the larger PoA, that is, enlarging the performance of networks. It demonstrates that the proportion of users choosing network coding transmission mode has a direct effect on the efficiency of utilizing network resource.

Figure 6

The PoA varies with the proportion of coding users or routing user.

6. Conclusion and Future Work

In this paper, we developed a novel discriminatory utility game model based on ACS pricing mechanism by assigning network coding users and routing users with the different utility parameters. The detailed analysis was provided to study the influences on the PoA due to different transmission strategies of the users. The simulation results demonstrated that the newly proposed utility mechanism contributes to the promotion of PoA. Furthermore, we found that the proportion of users choosing network coding acts as a key parameter to the PoA results, while the network coding could promote the efficiency of utilizing network resource to a certain extent. In reference to these conclusions, some useful methods or clues can be taken in the management of M2M network resources. Although only one transmission is considered among M2M devices in this paper, the results can be extended to repeated games in future works.