# A Stackelberg-Game-Based Power Control Algorithm for Wireless Mesh Networks

Authors: Yanbing Liu; Tao Wu; Jun Huang; Shousheng Jia
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Wireless mesh networks (WMNs) are a promising networking paradigm for next generation wireless networking system. Power control plays a vital role in WMNs and is realized to be a crucial step toward large-scale WMNs deployment. In this paper, we address the problem of how to allocate the power for both optimizing quality of service (QoS) and saving the power consumption in WMNs based on the game theory. We first formulate the problem as a noncooperative game, in which the QoS attributes and the power of each node are defined as a utility function, and all the nodes attempt to maximize their own utility. In such game, we correlate all the interfering nodes to be an interfering object and the receiving node to be the interfering object's virtual destination node. We then present an equilibrium solution for the noncooperative game using Stackelberg model, and we propose an iterative, distributed power control algorithm for WMNs. Also, we conduct numeric experiments to evaluate the system performance, our results show that the proposed algorithm can balance nodes to share the limited network resources and maximize total utility, and thus it is efficient and effective for solving the power control problem in WMNs.


---

## Body

## 1. Introduction

Wireless mesh networks (WMNs) are a key networking paradigm for next generation wireless networking system. The openness feature of WMNs makes the transmission power level affect the performance of wireless network significantly. In wireless networks, higher signal-to-interference plus noise ratio (SINR) value yields lower BER and higher data rate, and every node desires to have the lowest possible transmission power coupled with the highest SINR. Power control technology that deals with the selection of proper transmission power is closely related to quality of service (QoS) optimization and power saving. Therefore, power control plays a vital role in WMNs and is expected to be a crucial technique for large-scale WMNs deployment.Power control scheme, which determines transmission range or interference range, is critical to the performance of the WMNs. However, the existing power control schemes that largely rely on the local information of sending node, which cannot accurately reflect the link quality of transmission path, and the transmissions with the power control schemes cannot share network resources reasonably. On the other hand, game theory, due to its mathematical capability in analyzing the interaction among independent decision-makers [1], has drawn much attention in the design of self-organizing and adaptive wireless networks. Game theory is a computing model by means of psychology, and it assumes that people are selfish, which is different from machine learning that try to discover the laws through the sample data. Game theory provides a powerful tool to study power allocation problems in competitive wireless networks. As far as we know, game theory has been actively applied for distributed resource allocation of different goals in adhoc and WMNs. Our research work is to devise a distributed, efficient power control scheme with low complexity for WMNs. In this paper, we propose a noncooperative power control algorithm for WMNs’ QoS optimization and power saving using the Stackelberg game model. Specifically, the contributions made in this work are threefold.(i)
We design a multiobjective utility function to represent users’ preference between QoS achieving and power saving, and we prove the existence and uniqueness of the theoretical optimal solution.(ii)
Based on the Stackelberg game model, we formulate this power-allocation problem as a noncooperative game, and we solve the power control game to get subgame perfect Nash equilibrium (SPNE) in detail.(iii)
According to SPNE, we propose a distributed power control algorithm for WMNs. The algorithm can advantageously improve the network performance by balancing all nodes in the interference range to share the limited network resource.Through numeric experiments, the proposed algorithm is shown to be efficient and effective in balancing nodes to share the limited network resources and maximizing total utility. We thus believe that it is applicable to various wireless networking systems.The remainder of this paper is organized as follows. In Section2, we present related works and the contributions of the work. Section 3 explicates the selfish character of WMNs nodes and designs a utility function for power control. Section 4 gives the system model and problem definition. Section 5 formulates the power control problem as the Stackelberg game model and conducts Nash equilibrium (NE) point. Section 6 presents the proposed power control algorithm. The numeric experiment is included in Section 7. Finally, we conclude the paper in Section 8.


## 2. Related Work

Recently a large amount of researches progress has been made in power allocation for wireless networks. Authors in [2] designed a power-controlled MAC protocol that enables nodes to adjust their transmission powers while allowing for some interference margin at the receiver. Simulation results demonstrated that significant throughput and energy gains are obtainable with MAC protocol. Nonetheless, it is difficult to implement synchronization between nodes. The MAC protocol fails to handle the interference problem as well. Literature [3] presented several distributed power control algorithms. These algorithms take the node sensitivities to current interference levels into account. In [4], the authors considered the problem of topology control in hybrid WMNs. An algorithm was developed to calculate the optimal transmission power so that network connectivity is maintained, node transmission power is reduced to cover only the nearest neighbors, and network lifetime is extended. However, the above referred research studies share the same features, that is, assuming the devices cooperate with the purpose of system performance optimization. While for the wireless nodes, they do not basically belong to a single authority and may not want to achieve consensus and pursue a common goal. Therefore, the nodes are usually too selfish like the players who attempt to maximize their own performance without considering the other players’ objective. Therefore, the assumption might not hold.Currently applying game theory in power allocation for competitive wireless networks has also become an active research topic. As far as we know, game theory has been actively applied for distributed resource allocation of different goals in ad hoc and WMNs. Tan and coauthors in [5] modeled the channel assignment and power control problem as a noncooperative game, in which all wireless users jointly pick an optimal channel and power level to minimize a joint cost function. However, the proposed algorithm is theoretic, and it cannot be implemented in practice conveniently. In [6], the authors proposed a payment-based power control scheme using game theory where each user announces a set of price coefficients that reflect different compensations paid by other users for the interference they produce. The proposed approach converges to Nash equilibrium where at this point it is able to provide a fairer throughput share among users. In [7], the authors focused on how to control the transmission power of the access points’ pilot signals using game theory to manage interference. They considered a noncooperative power control game and computed the transmission power level of each access point as Nash equilibrium of the game. On the other hand, they considered a cooperative power control game and presented a punishment strategy enforced by the game regulator to punish selfish access points. However, the assumption of the game regulator is not feasible for WMNs. Since most of the terminals in a wireless network are battery powered, such WMNs clients and sensor nodes, energy efficiency is crucial to prolonging the life of the terminals. In addition to the PC game, studies pertinent to the energy efficiency game can be found in [8–10].Through the aforementioned studies concentrated on QoS optimization (throughput optimization) and energy efficiency, little research has been reported to balance both the QoS optimization (throughput optimization) and energy efficiency under the game theoretic framework. In this paper, we address the problem of power allocation for both QoS optimization and power saving in wireless mesh networks. Our work differs from above researches in the following three ways. First, we address the problem in multihop WMNs instead of single-hop WMNs. Second, we present a joint objective function to balance the QoS optimization (throughput optimization) and energy efficiency. Third, we combine the QoS optimization and power saving into a single game termed noncooperative game (NQPG), and the detailed description is given in Section5.


## 3. Utility Function for Power Control

In WMNs, each autonomous node attempts to maximize its own interest and tends to be “selfish”; therefore, there exists a game between these nodes. While in the power control scenario, a user tends to adjust its transmission power in response to other users’ actions, which leads to a sequence of power vectors that converge to a point where no user has incentive to increase its individual power, and this point is called NE. Unfortunately, such an NE point does not necessarily exist. In general, we have the following sufficient conditions.Definition 1.
An NE exists in a noncooperative power control gameG=[N,{Pi},{Ui(·)}] if, for all i=1,…,n:(i)
the strategy profilePi is a nonempty, convex, and compact subset of some Euclidean space ℜ,(ii)
Ui(·) is continuous and quasi concave in Pi,
whereN={1,2,…,n} is the index set of the currently active nodes, Pi represents the strategy set, and Ui(·) is the utility function for user i. Each node selects a power level pi from the convex set Pi such that pi∈Pi. Let the power vector p=(p1,p2,…,pn) denote the outcome of the game in terms of the selected power levels of all the users. The resulting utility level for the ith user is U(pi,P-i). The strategy space of all the users excluding the ith user is denoted by P-i.In WMNs with shared transmission medium, the signal of one node may interfere with that of other nodes. Typically, a selfish user without any energy constraint would tend to achieve a high SINR at the receiving node irrespective of the fact that it may cause excessive interference to other users [5]. Eventually all nodes will transmit at their maximum power level because power is strictly increasing with the SINR. Considering the overall performance of the network, the desired utility function should take the SINR and power into account, so we specify a utility function for each node to adjust transmission power, which consists of three terms, and we will introduce them individually. To address the power control problem, we adopt a function to measure the throughput [11]:
(1)A1(pi,P-i)=W·log2(1+γiΩ),
where pi denotes the strategy chosen by source node i, P-i denotes the strategies of all other nodes in interference range, W is the link bandwidth, Ω is the channel gap, Ω≥1, and γi represents the SINR of node i [5], and
(2)γi=pi·Gi,j/di,jα∑k∈S-i,k=1,k≠ipk·Gk,j/dk,jα+N0,
where di,j is the distance from sending node i to receiving node j, pi is the transmission power of node i, α is the attenuation index, α∈[2,4] [12], Gi,j is the link gain from node i to node j, N0 is AWGN power at the receiving node, S is the active nodes set in the interference range, and S-i denotes all the active nodes except node i. In the deterministic formulation of the power control problem for WMNs, the AWGN power N0 is a constant.What a concerns selfish user is that it can utilize the channel to transmit at an optimal power level, disregarding of its impact on other transmissions. In order to optimize the QoS of WMNs, the design of utility function should consider the effect of node’s transmission power on the overall performance of the network and the energy consumption, so we define the available wireless medium as(3)A2(pi,P-i)=Φ-∑k∈Sξk·pk-N0,
where Φ is a system constant and ξi is a variable related to the source node i.From a social welfare point of view, it is reasonable to charge the node some price for the consumption of energy, so we define the energy price as(4)A3(pi,P-i)=μi·pi,
where μi represents the price coefficient.We now note that the following expression is the utility function for this game:(5)U(pi,P-i)=A1(pi,P-i)·A2(pi,P-i)-A3(pi,P-i)=W·log2(1+γiΩ)·(Φ-∑k∈Sξk·pk-N0)-μi·pi.Proposition 2.
An NE exits and is unique in the power control gameG=[N,{Pi},{Ui(·)}].Proof.
The first condition of the existence of NE is satisfied obviously. We take the second-order partial derivative of utility function with respect topi:
(6)∂2U(pi,P-i)∂pi2=-2ξi<0.
So U(pi,P-i) is a continuous and quasi-concave function in pi. The proof of the uniqueness of NE of the game is straightforward according Debreu’s theorem [13].


## 4. System Model and Problem Formulation

We select appropriate transmission power for network nodes using game theory and consider the communication situation in an interference range, and as long as the nodes share some common resources in WMNs, competition among them cannot be avoided, and thus a game is born accordingly. In order to enhance SINR to optimize QoS and save energy, we use Stackelberg model to model the power control problem.Definition 3.
Wireless signal strength attenuates with the propagation distance increases and the path loss can be defined as follows [12]:
(7)Pr(d)=Pt·Gt,rdt,rα,
where dt,r is the distance from receiving node to source node, α is the attenuation index, and α∈[2,4]. Pt is transmission power and Gt,r is the link gain.To the receiving noder of link l(s,r), its total received signal strength is
(8)TEr=∑i∈S-tPi·Gi,rdi,rα+Pt·Gt,rdt,rα+N0,
where Pt·Gt,r/dt,rα is the signal strength at receiving node r and ∑i∈S-t(Pi·Gi,r/di,rα)+N0 is the cumulative interference of the receiving node r, which is caused by the transmissions which are simultaneous with the transmission in link l(s,r) and AWGN power at the receiving node r.As for the receiving nodes in WMNs, it is difficult to obtain their interfering neighbors’ detail information, including the transmission power and the distance to the receiving node. As the noder1 shown in Figure 1, it may be interfered by node s2, s3, and s4. If the system adopts some control mechanism such as RTS/CTS, the transmission s4 in the node r1’s communication range will be deferred, but the transmissions of node s2 and s3 in the node r1’s interference range will impact node r1’s transmission all the same, and r1 does not know them. Then, the power control problem is the power allocation between the interfering neighbors s2, s3 and the sending node s1 of the receiving node r1. Therefore, our goal is to design a power control scheme which can allocate transmission power properly to optimize the network throughput and save energy.Figure 1
A WMNs’ transmission scene.


## 5. Stackelberg Power Control Game (SPCG)

### 5.1. Problem Formulation

Stackelberg games are also called leader-follower games. In a Stackelberg game, the players of this game are a leader and a follower. The problem assumes that the follower reacts in such a rational way that they optimize its objective function based on the leader’s action. The Stackelberg model can be solved by finding the subgame perfect Nash equilibrium (SPNE).In our power control game mode, we assume that the system adopts RTS/CTS mechanism and protocol interference model. We assume that all nodes have the same frequency and they are immobile. We assume that the selected transmission power by the proposed power control algorithm can ensure the required minimum SINR in all transmissions.According to the RTS/CTS mechanism, if the receiving noder1 receives data, all other transmissions in the communication range of the receiving node r1 are deferred. Thus, the interference only comes from the nodes in the region that is out of the communication range, such as s2, s3, and s4, as shown in Figure 2, where dT and dI are the radius of the communication range and the interference range, respectively.Figure 2
Wireless interference model.Because of the wireless signal attenuation characteristics, if the transmission power of the interfering nodess2, s3, and s4 become larger, the interference of the receiving node r1 that is caused by these interfering nodes will get larger, so the trend of the interference strength at the receiving node r1 is consistent with the received signal strength at the receiving node r2, r3, and r4. Then we define all the nodes that affect the link quality of the receiving node r1 as an interfering object, and we define the receiving node r1 as the interfering object’s virtual destination node. Since we cannot get the interfering nodes’ transmission power, we estimate the sum of the transmission power of all interfering nodes through measuring the strength of the cumulative interference at receiving node r1. According to (2), the sum of the transmission power of all interfering nodes can be expressed by pinf=dinfα·pinf′, where pinf′ is the cumulative interference of the receiving node r1, and dinf is the average distance from the interfering nodes to r1 and we define dinf=(dI+dT)/2. We regard the sum of the transmission power pinf of all interfering nodes as the interfering object’s game strategy, which can be computed by the receiving node r1’s cumulative interference level pinf′. On the other hand, we define the source node as sending object, and the transmission power level is the sending object’s game strategy. So this power control process is modeled as a game between the sending object and the interfering object of the receiving node.As the complexity restriction of power control algorithm,A1(pi,P-i) and A2(pi,P-i) are all monotone function on pk, and pk is considered in A2(pi,P-i), k∈S-i. On the other hand, log2(1+γi/Ω) is a monotone function on γi, so the utility function (5) can be rewritten as
(9)U(pi,P-i)=(Φ-∑k∈Sξk·pk-N0)·W·(1+pi·Gi,j/di,jαΩ·(∑k∈S-i,k=1,k≠iGk,j+N0))-μi·pi.Definition 4.
The power control problem can be formulated as the Stackelberg power control game(10)G=〈O,{Pi},{Ui(·)}〉,
where(1)
O={O1,O2} is the set of players. O1 is the interfering object that represents all the interfering nodes of the receiver in a transmission process; it is the leader in this game. O2 is the sending object that represents the source node; it is the follower in this game, and it reacts based on the leader’s action;(2)
action set{Pi}; each player select power level pi such that pi∈Pi. Player O1’s transmission power level is p1, player O2’s transmission power level is p2;(3)
utility function{Ui(·)}; The resulting utility level for player Oi. According the utility function in (9), considering the need of reducing the complexity of power control algorithm, we set ξk=1, and the utility functions of the interfering object and the sending object can be defined as follows:
(11)U(p1,P-1)=(Φ-p1-p2-N0)·W·(1+p1·GO1,r/d1αΩ·(GO2,r+N0))-μ1·p1,U(p2,P-2)=(Φ-p1-p2-N0)·W·(1+p2·GO2,r/d2αΩ·(GO1,r+N0))-μ2·p2,wherep1 is the transmission power of the interfering object, p2 is the transmission power of the sending object, d1 is the average distance from the interfering nodes to their destinations where we define d1= dT/2,d2 is the distance from the sending node to the receiving node, GO1,r is the link gain from the interfering object O1 to the receiving node r, and GO2,r is the link gain from the sending object O2 to the receiving node r.


### 5.2. Problem Solving

Substitutingp1, p2 with p1′, p2′, the Stackelberg power control game in (11) can be rewritten as follows:
(12)U(p1,P-1)=(Φ-p1′·dinfα-p2′·d2α-N0)·W·(1+p1′·dinfα·GO1,r/d1αΩ·(GO2,r+N0))-μ1·p1′·dinfα,U(p2,P-2)=(Φ-p1′·dinfα-p2′·d2α-N0)·W·(1+p2′·GO2,rΩ·(GO1,r+N0))-μ2·p2′·d2α,
where p1′=p1/dinfα is the cumulative interference level of the receiving node, p2′=p2/d2α is the received signal strength at the receiving node, dinf is the average interference distance from all the interfering nodes to the receiving node, and d2 is the distance from the sending node to the receiving node.The SPNE can be found by solving the Stackelberg power control game model. As the power strategy ofO2 depends on the power level of O1, we define that p2′=R(p1′) denotes the follower’s best action function, where the subscript 1 represents the leader and 2 represents the follower. As players tend to be “selfish” and maximize their own utility, we take the first-order derivative of the follower O2’s utility function U(p2,P-2) with respect to its strategy p2′, we arrive at:
(13)∂U(p2,P-2)∂p2′=W·GO2,rΩ·(GO1,r+N0)·(Φ-p1′·dinfα-2p2′·d2α-N0)-W·d2α-μ2·d2α.
Define ∂U(s2,s-2)/∂p2′ = 0; then we get the best action function as
(14)p2′=R(p1′)=12d2α(Φ-p1′·dinfα-N0)-Ω·(GO1,r+N0)·(W+μ2)2W·GO2,r.
Substitute p2′ in U(p1,P-1) with the R(p1′) in the above formula; we get
(15)U(p1,P-1)=W2[Ω·(GO1,r+N0)·(W+μ2)·d2αW·GO2,rΦ-p1′·dinfα-N0aaaaaa+Ω·(GO1,r+N0)·(W+μ2)·d2αW·GO2,r]·(1+p1′·dinfα·GO1,r/d1αΩ·(GO2,r+N0))-μ1·p1′·dinfα.
We take the first-order derivative of the follower O1’s utility function U(p1,P-1) with respect to p1′; we arrive at
(16)∂U(p1,P-1)∂p1′=W·GO1,r·dinfα/d1α2Ω·(GO2,r+N0)×[Φ-2p1′·dinfα-N0+Ω·(GO1,r+N0)·(W+μ2)W·GO2,r]-W2·dinfα-μ1·dinfα.
Define ∂U(p1,P-1)/∂p1′=0; then
(17)p1=12[Φ-N0-Ω·(GO2,r+N0)·(W+2μ1)·d1αW·GO1,raaaaa+Ω·(GO1,r+N0)·(W+μ2)W·GO2,r].
According to the best action function, we get
(18)p2=14[Φ-N0+Ω·(GO2,r+N0)·(W+2μ1)·d1αW·GO1,raaaaa-3Ω·(GO1,r+N0)·(W+μ2)W·GO2,r].
So the Stackelberg equilibrium (theoretical optimal solution) of SPCG is (p1,p2).According to Stackelberg power control game, we know the relationship of the receiving node’s cumulative interferencep1′ and the sending node’s transmission power p2 is as follows:
(19)p2=d2α·p2′=d2α·R(p1′)=12(Φ-p1′·dinfα-N0)-Ω·d2α·(GO1,r+N0)·(W+μ2)2W·GO2,r.


## 5.1. Problem Formulation

Stackelberg games are also called leader-follower games. In a Stackelberg game, the players of this game are a leader and a follower. The problem assumes that the follower reacts in such a rational way that they optimize its objective function based on the leader’s action. The Stackelberg model can be solved by finding the subgame perfect Nash equilibrium (SPNE).In our power control game mode, we assume that the system adopts RTS/CTS mechanism and protocol interference model. We assume that all nodes have the same frequency and they are immobile. We assume that the selected transmission power by the proposed power control algorithm can ensure the required minimum SINR in all transmissions.According to the RTS/CTS mechanism, if the receiving noder1 receives data, all other transmissions in the communication range of the receiving node r1 are deferred. Thus, the interference only comes from the nodes in the region that is out of the communication range, such as s2, s3, and s4, as shown in Figure 2, where dT and dI are the radius of the communication range and the interference range, respectively.Figure 2
Wireless interference model.Because of the wireless signal attenuation characteristics, if the transmission power of the interfering nodess2, s3, and s4 become larger, the interference of the receiving node r1 that is caused by these interfering nodes will get larger, so the trend of the interference strength at the receiving node r1 is consistent with the received signal strength at the receiving node r2, r3, and r4. Then we define all the nodes that affect the link quality of the receiving node r1 as an interfering object, and we define the receiving node r1 as the interfering object’s virtual destination node. Since we cannot get the interfering nodes’ transmission power, we estimate the sum of the transmission power of all interfering nodes through measuring the strength of the cumulative interference at receiving node r1. According to (2), the sum of the transmission power of all interfering nodes can be expressed by pinf=dinfα·pinf′, where pinf′ is the cumulative interference of the receiving node r1, and dinf is the average distance from the interfering nodes to r1 and we define dinf=(dI+dT)/2. We regard the sum of the transmission power pinf of all interfering nodes as the interfering object’s game strategy, which can be computed by the receiving node r1’s cumulative interference level pinf′. On the other hand, we define the source node as sending object, and the transmission power level is the sending object’s game strategy. So this power control process is modeled as a game between the sending object and the interfering object of the receiving node.As the complexity restriction of power control algorithm,A1(pi,P-i) and A2(pi,P-i) are all monotone function on pk, and pk is considered in A2(pi,P-i), k∈S-i. On the other hand, log2(1+γi/Ω) is a monotone function on γi, so the utility function (5) can be rewritten as
(9)U(pi,P-i)=(Φ-∑k∈Sξk·pk-N0)·W·(1+pi·Gi,j/di,jαΩ·(∑k∈S-i,k=1,k≠iGk,j+N0))-μi·pi.Definition 4.
The power control problem can be formulated as the Stackelberg power control game(10)G=〈O,{Pi},{Ui(·)}〉,
where(1)
O={O1,O2} is the set of players. O1 is the interfering object that represents all the interfering nodes of the receiver in a transmission process; it is the leader in this game. O2 is the sending object that represents the source node; it is the follower in this game, and it reacts based on the leader’s action;(2)
action set{Pi}; each player select power level pi such that pi∈Pi. Player O1’s transmission power level is p1, player O2’s transmission power level is p2;(3)
utility function{Ui(·)}; The resulting utility level for player Oi. According the utility function in (9), considering the need of reducing the complexity of power control algorithm, we set ξk=1, and the utility functions of the interfering object and the sending object can be defined as follows:
(11)U(p1,P-1)=(Φ-p1-p2-N0)·W·(1+p1·GO1,r/d1αΩ·(GO2,r+N0))-μ1·p1,U(p2,P-2)=(Φ-p1-p2-N0)·W·(1+p2·GO2,r/d2αΩ·(GO1,r+N0))-μ2·p2,wherep1 is the transmission power of the interfering object, p2 is the transmission power of the sending object, d1 is the average distance from the interfering nodes to their destinations where we define d1= dT/2,d2 is the distance from the sending node to the receiving node, GO1,r is the link gain from the interfering object O1 to the receiving node r, and GO2,r is the link gain from the sending object O2 to the receiving node r.


## 5.2. Problem Solving

Substitutingp1, p2 with p1′, p2′, the Stackelberg power control game in (11) can be rewritten as follows:
(12)U(p1,P-1)=(Φ-p1′·dinfα-p2′·d2α-N0)·W·(1+p1′·dinfα·GO1,r/d1αΩ·(GO2,r+N0))-μ1·p1′·dinfα,U(p2,P-2)=(Φ-p1′·dinfα-p2′·d2α-N0)·W·(1+p2′·GO2,rΩ·(GO1,r+N0))-μ2·p2′·d2α,
where p1′=p1/dinfα is the cumulative interference level of the receiving node, p2′=p2/d2α is the received signal strength at the receiving node, dinf is the average interference distance from all the interfering nodes to the receiving node, and d2 is the distance from the sending node to the receiving node.The SPNE can be found by solving the Stackelberg power control game model. As the power strategy ofO2 depends on the power level of O1, we define that p2′=R(p1′) denotes the follower’s best action function, where the subscript 1 represents the leader and 2 represents the follower. As players tend to be “selfish” and maximize their own utility, we take the first-order derivative of the follower O2’s utility function U(p2,P-2) with respect to its strategy p2′, we arrive at:
(13)∂U(p2,P-2)∂p2′=W·GO2,rΩ·(GO1,r+N0)·(Φ-p1′·dinfα-2p2′·d2α-N0)-W·d2α-μ2·d2α.
Define ∂U(s2,s-2)/∂p2′ = 0; then we get the best action function as
(14)p2′=R(p1′)=12d2α(Φ-p1′·dinfα-N0)-Ω·(GO1,r+N0)·(W+μ2)2W·GO2,r.
Substitute p2′ in U(p1,P-1) with the R(p1′) in the above formula; we get
(15)U(p1,P-1)=W2[Ω·(GO1,r+N0)·(W+μ2)·d2αW·GO2,rΦ-p1′·dinfα-N0aaaaaa+Ω·(GO1,r+N0)·(W+μ2)·d2αW·GO2,r]·(1+p1′·dinfα·GO1,r/d1αΩ·(GO2,r+N0))-μ1·p1′·dinfα.
We take the first-order derivative of the follower O1’s utility function U(p1,P-1) with respect to p1′; we arrive at
(16)∂U(p1,P-1)∂p1′=W·GO1,r·dinfα/d1α2Ω·(GO2,r+N0)×[Φ-2p1′·dinfα-N0+Ω·(GO1,r+N0)·(W+μ2)W·GO2,r]-W2·dinfα-μ1·dinfα.
Define ∂U(p1,P-1)/∂p1′=0; then
(17)p1=12[Φ-N0-Ω·(GO2,r+N0)·(W+2μ1)·d1αW·GO1,raaaaa+Ω·(GO1,r+N0)·(W+μ2)W·GO2,r].
According to the best action function, we get
(18)p2=14[Φ-N0+Ω·(GO2,r+N0)·(W+2μ1)·d1αW·GO1,raaaaa-3Ω·(GO1,r+N0)·(W+μ2)W·GO2,r].
So the Stackelberg equilibrium (theoretical optimal solution) of SPCG is (p1,p2).According to Stackelberg power control game, we know the relationship of the receiving node’s cumulative interferencep1′ and the sending node’s transmission power p2 is as follows:
(19)p2=d2α·p2′=d2α·R(p1′)=12(Φ-p1′·dinfα-N0)-Ω·d2α·(GO1,r+N0)·(W+μ2)2W·GO2,r.


## 6. Stackelberg-Game-Based Power Control Algorithm

### 6.1. Power Control Algorithm

One shortcoming of power control mechanisms previously based on pricing is that they do not have a convenient algorithm for implementing it in practice, and we present an efficient and straightforward power control algorithm based on game theory.According to (19), the cumulative interference p1′ of the receiving node is determined in a certain network condition, and we can measure it in MAC layer, and the transmission power level can be adjusted as follows:
(20)pt=dtraα·pt′=dtraα·R(pinf′)=12(Φ-pinf′·dinfα-N0)-Ω·dtraα·(GO1,r+N0)·(W+μt)2W·GO2,r,
where dtra is the distance from the sending node to the receiving node, pt′ is the received signal strength at the receiving node, pinf′ is the cumulative interference of the receiving node, dinf is the average distance from the interfering nodes to the receiving node, and μt represents the price coefficient. According to (2), we can optimize network performance through selecting the sending nodes’ transmission power level pt. We can see from (20) that the transmission power pt is a negative monotone function on cumulative interference pinf′, but due to the restriction of the available of wireless medium in (3), pinf′ will not unlimitedly increase, and pt will not unlimitedly decrease; they will be adjusted to achieve equilibrium and optimize their utility function.The interfering nodes of the current receiving node may be the sending nodes in their own transmission links, and the current sending node may also cause interference to these interfering nodes, so we select the transmission power according to the cumulative interference that comes from the interfering nodes; we must also consider the impact of the current sending node’s transmission power on the other sending nodes in the interference range. According to the Stackelberg game, the proposed power control algorithm can balance all transmission nodes in the interference range to share the limited network resources and improve network performance consequently. In our algorithm, the system allocates transmission power through transmitting power emendation instruction to the interfering nodes and the sending node by the receiving node. The proposed power control algorithm is as in Algorithms1 and 2.Algorithm 1:Collect interference information algorithm (CIIA).
Begin
Input: Routing protocol;
Output: Interference information table;
(
1
) If a node needs to send data, it should broadcasts active notice message in two-hop
range to inform other nodes, and the receiving node record the source nodes of
these control messages as the active neighbor list;
(
2
) Each node calculates its own average cumulative interference pinf′  in communication
process and broadcasts interference notice message including average cumulative
interferencepinf′, the active neighbor list and the transmission power level in
one-hop range through routing protocol periodically;
(
3
) After receiving a control message from a neighbor node,  each node establishes
an interference information table to record the adjacent node’s average
cumulative interferencepinf′, the adjacent node’s active neighbor nodes and the distance
d
tra to this adjacent node which is computed through the transmission power
and the received signal strength of the control message.
EndAlgorithm 2:Stackelberg-game-based power control algorithm (SGPCA).
Begin
Input: The strategy set Pi, utility function Ui(·);
Output: Optimal transmission power set;
(
1
) When node needs to send data to adjacent node, it queries the cumulative interference pinf′
of the destination node from the interference information table firstly, and selects a proper
transmission power levelpt using (20) based on the cumulative interference of the destination and
the distance to the destination. The node transmits data with the selected
transmission  power levelpt;
(
2
) Based on the received signal strength pt and the average cumulative interference pinf′, according
to the Stackelberg Subgame Perfect Nash Equilibrium, the receiving node transmits power
emendation instruction to the interfering nodes and the sending node;
(
3
) The interfering node and the sending node adjusts its transmission power to optimize its
utility function based on the received power adjust instruction.
(
4
) Circulation steps (2) and (3), until the two game objects’ transmit power achieve steady state.
End


### 6.2. Time Complexity Analysis

We assumed thatn is the number of the active nodes in the interference range, and m stands for iterative times of SGPCA.Firstly, for the initialization that establishes interference information tables in the CIIA, in which every node broadcasts active notice message and interference notice message, and the process can be seen as setting up directed complete graph; it takesO(2n·(n-1)). Each node needs to register its adjacent nodes interference information; it takes O(n·(n-1)). Each node needs to compute the distance to its adjacent nodes which takes O(n·(n-1)). Each node calculates its own average cumulative interference which takes O(n). So the time complexity of the CIIA is O(4n·(n-1)+n).Secondly, we assume all nodes are interferential, except the sending node and the receiving node, and the algorithm SGPCA needs the receiving node to transmit power emendation instruction to the interfering nodes and the sending node which takesO(n-1), and all these nodes need to adjust their transmission which also takes O(n-1). If the iterative times of SGPCA is m, the time complexity of the SGPCA is O(2m·(n-1)).So, the time complexity of Stackelberg-game-based power control algorithm is(21)O(2m·(n-1)+4n·(n-1)+n)=O((2m+4n)·(n-1)+n)=O(n2).Asn is the number of the active nodes in interference range, and it is not large, so the power control algorithm’s time complexity O(n2) is not high and it is feasible.


## 6.1. Power Control Algorithm

One shortcoming of power control mechanisms previously based on pricing is that they do not have a convenient algorithm for implementing it in practice, and we present an efficient and straightforward power control algorithm based on game theory.According to (19), the cumulative interference p1′ of the receiving node is determined in a certain network condition, and we can measure it in MAC layer, and the transmission power level can be adjusted as follows:
(20)pt=dtraα·pt′=dtraα·R(pinf′)=12(Φ-pinf′·dinfα-N0)-Ω·dtraα·(GO1,r+N0)·(W+μt)2W·GO2,r,
where dtra is the distance from the sending node to the receiving node, pt′ is the received signal strength at the receiving node, pinf′ is the cumulative interference of the receiving node, dinf is the average distance from the interfering nodes to the receiving node, and μt represents the price coefficient. According to (2), we can optimize network performance through selecting the sending nodes’ transmission power level pt. We can see from (20) that the transmission power pt is a negative monotone function on cumulative interference pinf′, but due to the restriction of the available of wireless medium in (3), pinf′ will not unlimitedly increase, and pt will not unlimitedly decrease; they will be adjusted to achieve equilibrium and optimize their utility function.The interfering nodes of the current receiving node may be the sending nodes in their own transmission links, and the current sending node may also cause interference to these interfering nodes, so we select the transmission power according to the cumulative interference that comes from the interfering nodes; we must also consider the impact of the current sending node’s transmission power on the other sending nodes in the interference range. According to the Stackelberg game, the proposed power control algorithm can balance all transmission nodes in the interference range to share the limited network resources and improve network performance consequently. In our algorithm, the system allocates transmission power through transmitting power emendation instruction to the interfering nodes and the sending node by the receiving node. The proposed power control algorithm is as in Algorithms1 and 2.Algorithm 1:Collect interference information algorithm (CIIA).
Begin
Input: Routing protocol;
Output: Interference information table;
(
1
) If a node needs to send data, it should broadcasts active notice message in two-hop
range to inform other nodes, and the receiving node record the source nodes of
these control messages as the active neighbor list;
(
2
) Each node calculates its own average cumulative interference pinf′  in communication
process and broadcasts interference notice message including average cumulative
interferencepinf′, the active neighbor list and the transmission power level in
one-hop range through routing protocol periodically;
(
3
) After receiving a control message from a neighbor node,  each node establishes
an interference information table to record the adjacent node’s average
cumulative interferencepinf′, the adjacent node’s active neighbor nodes and the distance
d
tra to this adjacent node which is computed through the transmission power
and the received signal strength of the control message.
EndAlgorithm 2:Stackelberg-game-based power control algorithm (SGPCA).
Begin
Input: The strategy set Pi, utility function Ui(·);
Output: Optimal transmission power set;
(
1
) When node needs to send data to adjacent node, it queries the cumulative interference pinf′
of the destination node from the interference information table firstly, and selects a proper
transmission power levelpt using (20) based on the cumulative interference of the destination and
the distance to the destination. The node transmits data with the selected
transmission  power levelpt;
(
2
) Based on the received signal strength pt and the average cumulative interference pinf′, according
to the Stackelberg Subgame Perfect Nash Equilibrium, the receiving node transmits power
emendation instruction to the interfering nodes and the sending node;
(
3
) The interfering node and the sending node adjusts its transmission power to optimize its
utility function based on the received power adjust instruction.
(
4
) Circulation steps (2) and (3), until the two game objects’ transmit power achieve steady state.
End


## 6.2. Time Complexity Analysis

We assumed thatn is the number of the active nodes in the interference range, and m stands for iterative times of SGPCA.Firstly, for the initialization that establishes interference information tables in the CIIA, in which every node broadcasts active notice message and interference notice message, and the process can be seen as setting up directed complete graph; it takesO(2n·(n-1)). Each node needs to register its adjacent nodes interference information; it takes O(n·(n-1)). Each node needs to compute the distance to its adjacent nodes which takes O(n·(n-1)). Each node calculates its own average cumulative interference which takes O(n). So the time complexity of the CIIA is O(4n·(n-1)+n).Secondly, we assume all nodes are interferential, except the sending node and the receiving node, and the algorithm SGPCA needs the receiving node to transmit power emendation instruction to the interfering nodes and the sending node which takesO(n-1), and all these nodes need to adjust their transmission which also takes O(n-1). If the iterative times of SGPCA is m, the time complexity of the SGPCA is O(2m·(n-1)).So, the time complexity of Stackelberg-game-based power control algorithm is(21)O(2m·(n-1)+4n·(n-1)+n)=O((2m+4n)·(n-1)+n)=O(n2).Asn is the number of the active nodes in interference range, and it is not large, so the power control algorithm’s time complexity O(n2) is not high and it is feasible.


## 7. Numeric Result and Performance Evaluation

In this section, we present numerical results for the algorithm presented in the previous sections. We set a typical value for each variable to validate the efficiency of the proposed power control scheme. We set system gainGO1,r=40, GO2,r=60, bandwidth W=10.0, Gaussian white noise N0=5.0, price coefficient μ1=μ2=10.0, traffic constant Φ=15000.0, channel gap Ω=1.0, the attenuation index α=2, transmission distance dtra=10.0, the average interference distance as dinf=(dI+dT)/2=20, and the average distance from the interfering nodes to their own destination ditod=dT/2=6.65. In our experiment, the transmission model is simple: we assume that there is a transmission from the sending node to its receiving node and some interfering transmission in the interference range to impact the link quality of the transmission. Convergence of the proposed power control algorithm is defined as reaching within 0.01% of the steady-state values in power update [14].Different from machine learning research methods, we investigate the performance of the proposed power control algorithm by using analysis and comparison. In the Stackelberg game, all players are selfish and do their best to maximize their utility, and the follower reacts in such a rational way that they optimize its utility function based on the leader’s action. If the leader’s action does not maximize his utility, he adjusts his action to increase his utility, and the follower adjusts his action accordingly. In the proposed power control algorithm, the receiving node gets the subgame perfect Nash equilibrium point based on the system parameters. Based on the cumulative interference that comes from the interfering nodes and the received signal strength, the receiving node sends power emendation introductions to the interfering nodes and the sending node, and the nodes adjust their transmission power. At the next iteration, the receiving node senses the updated cumulative interference and the updated received signal strength, compares it to the Subgame Perfect Nash Equilibrium point, and sends power emendation introductions again. This iteration process stops only if the system achieves steady state. We first analyzed the proposed algorithm in a feasible system to verify the iteration process’s convergence. Then, we used the just enough transmission power schemes [15] and the IEEE 802.11 standard as a baseline to evaluate the performance of the proposed power control algorithm. We compared the proposed power control algorithm, the just enough transmission power scheme, and the IEEE 802.11 maximum transmission power scheme in three aspects, including the receiving node’s SINR, energy efficient, and total utility. The just enough transmission power scheme simply modifies the IEEE 802.11 RTS/CTS mechanism, and maximum transmit power is used for request-power-to-send (RPTS)/acceptable-power-to-send (APTS) handshake between the data sender and receiver, which is used to determine the minimum transmission power that will result in a successful packet reception at the receiver for DATA-ACK transmission, that is, the minimum transmission power is selected based on the required minimum SINR (RMSINR) of the receiver. In our experiment, we set the RMSINR as 1.5. In the IEEE 802.11 maximal transmission power scheme, all nodes transmit data with the maximum transmit power. Also, we define the maximal transmission power ss 8000.


### 7.1. Performance Evaluation of the Proposed Power Control Algorithm

According to the Stackelberg power control game, to ensure the application’s QoS, the interfering node can adjust its transmission power to get the best utility, and the sending node can select transmission power based on the receiving node’s cumulative interference decided by the interfering node’s transmission power. The trend of the interfering node and the sending node’s transmission power is shown in Figure3. The system can converge and achieve steady state after carrying through thirteen times iteration. According to the parameter value in the aforementioned paragraph, we get the Subgame Perfect Nash Equilibrium of the power control game as (6522, 4161). We can see from Figure 3 that, when the system achieves steady state, the interfering nodes and the sending node’s transmission power consist with the Subgame Perfect Nash Equilibrium point.Figure 3
The transmission power comparison.By using the same experiment model considered previously, we investigate the receiving node’s SINR in iteration process, and the corresponding results are shown in Figure4. In the third generation, the SINR is maximal, but the iteration process continues. Because at this point, the receiving node’s link quality is the best, but the transmission power of the interfering node is too small. The proposed algorithm must enable all transmission nodes to share network resources evenly.Figure 4
SINR of the sending node.The system’s utility is shown in Figure5. We can see that the utility of the interfering node and the sending node vary with their transmission power adjustment in the iteration process. Through thirteen times iteration, each node adjusts its transmission power leading to a sequence of power vectors that converges to an equilibrium point, and there is no player that has the incentive to change its individual power. As the interfering node acts firstly and the sending node ensues, the interfering node’s utility is always greater than the sending node’s utility, which is called “pioneer predominance” in Stackelberg game theory.Figure 5
System’s utility.


### 7.2. Performance Comparison

We investigate the performance of the proposed power control algorithm in terms of SINR, energy efficiency, and users’ utility. We compare the proposed algorithm with the just enough transmission power schemes and the IEEE 802.11 maximum transmission power scheme.The comparison of the receiving node’s SINR is shown in Figure6. In the just enough transmission power schemes, the receiving node computes the transmission power to achieve the required SINR based on its interference and informs the sending node through APTS message. The sending node transmits data with the minimum transmission power for successful transmission. The minimum required SINR is decided by the network equipment and it achieves steady, as shown in Figure 6(b). In the IEEE 802.11 maximal transmission power scheme, the transmission power is kept in the same level no matter how the wireless environment changes. The IEEE 802.11 maximum transmission power scheme desires that all nodes transmit any data with the maximum transmission power.SINR comparison.
(a)
The proposed power control algorithm
(b)
The just enough transmission power scheme
(c)
IEEE 802.11 standard power control schemeThe SINR depraves with the increasing interference, as shown in Figure6(c). In the proposed power control algorithm, different from the above power control schemes, the network nodes adopting the algorithm can adjust interference level through sending emendation introduction to the interfering nodes, and the power control algorithm is acclimated to new environment. The system can achieve steady state after limited number of iteration. Compared with the just enough transmission power schemes and the IEEE 802.11 standard transmission power scheme, the proposed algorithm can enable nodes to get sufficient SINR in complicated network conditions.We define the energy efficiency as the ratio of the total utility to the sum of the transmission power of the interfering nodes and the sending node. Figure7 shows the comparison of the three power control schemes’ energy efficiency. We can see that the proposed power control algorithm’s energy efficiency is stable, whereas the energy efficiency of the just enough transmission power scheme and the IEEE 802.11 maximum transmission power scheme decline rapidly with the receiving node’s cumulative interference increases.Figure 7
Energy efficiency comparison.The utility comparison of the three power control schemes is demonstrated in Figure8. In the mass, the total utilities of the nodes adopting the IEEE 802.11 standard control scheme are less than those of the nodes adopting the proposed power control algorithm and the just enough transmission power scheme, and the total utilities decrease with the receiving nodes’ cumulative interference increases. If the receiving nodes’ interference level is low, the total utilities of the nodes adopting the just enough transmission power schemes are higher than the proposed power control algorithm. But if the interference level becomes greater, the total utilities will become very small, and the just enough transmission power schemes cannot offer adequate performance to ensure QoS.Figure 8
Utility comparison.


## 7.1. Performance Evaluation of the Proposed Power Control Algorithm

According to the Stackelberg power control game, to ensure the application’s QoS, the interfering node can adjust its transmission power to get the best utility, and the sending node can select transmission power based on the receiving node’s cumulative interference decided by the interfering node’s transmission power. The trend of the interfering node and the sending node’s transmission power is shown in Figure3. The system can converge and achieve steady state after carrying through thirteen times iteration. According to the parameter value in the aforementioned paragraph, we get the Subgame Perfect Nash Equilibrium of the power control game as (6522, 4161). We can see from Figure 3 that, when the system achieves steady state, the interfering nodes and the sending node’s transmission power consist with the Subgame Perfect Nash Equilibrium point.Figure 3
The transmission power comparison.By using the same experiment model considered previously, we investigate the receiving node’s SINR in iteration process, and the corresponding results are shown in Figure4. In the third generation, the SINR is maximal, but the iteration process continues. Because at this point, the receiving node’s link quality is the best, but the transmission power of the interfering node is too small. The proposed algorithm must enable all transmission nodes to share network resources evenly.Figure 4
SINR of the sending node.The system’s utility is shown in Figure5. We can see that the utility of the interfering node and the sending node vary with their transmission power adjustment in the iteration process. Through thirteen times iteration, each node adjusts its transmission power leading to a sequence of power vectors that converges to an equilibrium point, and there is no player that has the incentive to change its individual power. As the interfering node acts firstly and the sending node ensues, the interfering node’s utility is always greater than the sending node’s utility, which is called “pioneer predominance” in Stackelberg game theory.Figure 5
System’s utility.


## 7.2. Performance Comparison

We investigate the performance of the proposed power control algorithm in terms of SINR, energy efficiency, and users’ utility. We compare the proposed algorithm with the just enough transmission power schemes and the IEEE 802.11 maximum transmission power scheme.The comparison of the receiving node’s SINR is shown in Figure6. In the just enough transmission power schemes, the receiving node computes the transmission power to achieve the required SINR based on its interference and informs the sending node through APTS message. The sending node transmits data with the minimum transmission power for successful transmission. The minimum required SINR is decided by the network equipment and it achieves steady, as shown in Figure 6(b). In the IEEE 802.11 maximal transmission power scheme, the transmission power is kept in the same level no matter how the wireless environment changes. The IEEE 802.11 maximum transmission power scheme desires that all nodes transmit any data with the maximum transmission power.SINR comparison.
(a)
The proposed power control algorithm
(b)
The just enough transmission power scheme
(c)
IEEE 802.11 standard power control schemeThe SINR depraves with the increasing interference, as shown in Figure6(c). In the proposed power control algorithm, different from the above power control schemes, the network nodes adopting the algorithm can adjust interference level through sending emendation introduction to the interfering nodes, and the power control algorithm is acclimated to new environment. The system can achieve steady state after limited number of iteration. Compared with the just enough transmission power schemes and the IEEE 802.11 standard transmission power scheme, the proposed algorithm can enable nodes to get sufficient SINR in complicated network conditions.We define the energy efficiency as the ratio of the total utility to the sum of the transmission power of the interfering nodes and the sending node. Figure7 shows the comparison of the three power control schemes’ energy efficiency. We can see that the proposed power control algorithm’s energy efficiency is stable, whereas the energy efficiency of the just enough transmission power scheme and the IEEE 802.11 maximum transmission power scheme decline rapidly with the receiving node’s cumulative interference increases.Figure 7
Energy efficiency comparison.The utility comparison of the three power control schemes is demonstrated in Figure8. In the mass, the total utilities of the nodes adopting the IEEE 802.11 standard control scheme are less than those of the nodes adopting the proposed power control algorithm and the just enough transmission power scheme, and the total utilities decrease with the receiving nodes’ cumulative interference increases. If the receiving nodes’ interference level is low, the total utilities of the nodes adopting the just enough transmission power schemes are higher than the proposed power control algorithm. But if the interference level becomes greater, the total utilities will become very small, and the just enough transmission power schemes cannot offer adequate performance to ensure QoS.Figure 8
Utility comparison.


## 8. Conclusion

In this paper, we investigated the problem of power control and proposed an efficient power control algorithm for WMNs based on game theory. We modeled the power control problem to be a noncooperative Stackelberg game by observing the distinctive features of WMNs that each user makes its own decision selfishly and devised a utility function which comprehensively considers both of throughput and energy efficiency. Through the technique of SPNE in such Stackelberg game, we deduced the relationship between the sending node’s transmission power and the receiving node’s cumulative interference. The deduced equilibrium point indicates that the receiving node transmits power emendation instruction to the interfering nodes and the sending node to adjust their transmission power. We also presented the numerical experiment; the results show that all of the users obtain the sufficient SINR and achieve energy efficiency, and the proposed algorithm can balance nodes to share the limited network resources and maximize total utility; thus it is efficient and effective in solving the power control problem.



---

*Source: 832309-2013-03-13.xml*