A power control game based on outage probabilities for multicell wireless data networks

We present a game-theoretic treatment of distributed power control in CDMA wireless systems using outage probabilities. We first prove that the noncooperative power control game considered admits a unique Nash equilibrium (NE) for uniformly strictly convex pricing functions and under some technical assumptions on the SIR threshold levels. We then analyze global convergence of continuous-time as well as discrete-time synchronous and asynchronous iterative power update algorithms to the unique NE of the game. Furthermore, we show that a stochastic version of the discrete-time update scheme, which models the uncertainty due to quantization and estimation errors, converges almost surely to the unique NE point. We finally investigate and demonstrate the convergence and robustness properties of these update schemes through simulation studies.     

Optimality and Complexity of Pure Nash Equilibria in the Coverage Game

In this paper, we investigate the coverage problem in wireless sensor networks using a game theory method.We assume that nodes are randomly scattered in a sensor field and the goal is to partition these nodes into K sets. At any given time, nodes belonging to only one of these sets actively sense the field. A key challenge is to achieve this partition in a distributed manner with purely local information and yet provide near optimal coverage. We appropriately formulate this coverage problem as a coverage game and prove that the optimal solution is a pure Nash equilibrium. Then, we design synchronous and asynchronous algorithms, which converge to pure Nash equilibria. Moreover, we analyze the optimality and complexity of pure Nash equilibria in the coverage game. We prove that, the ratio between the optimal coverage and the worst case Nash equilibrium coverage, is upper bounded by 2 ? 1 m+1 (m is the maximum number of nodes, which cover any point, in the Nash equilibrium solution s*). We prove that finding pure Nash equilibria in the general coverage game is PLS-complete, i.e. ?as hard as that of finding a local optimum in any local search problem with efficient computable neighbors?. Finally, via extensive simulations, we show that, the Nash equilibria coverage performance is very close to the optimal coverage and the convergence speed is sublinear. Even under the noisy environment, our algorithms can still converge to the pure Nash equilibria.     

Asynchronous Iterative Water-Filling for Gaussian Frequency-Selective Interference Channels

This paper considers the maximization of information rates for the Gaussian frequency-selective interference channel, subject to power and spectral mask constraints on each link. To derive decentralized solutions that do not require any cooperation among the users, the optimization problem is formulated as a static noncooperative game of complete information. To achieve the so-called Nash equilibria of the game, we propose a new distributed algorithm called asynchronous iterative water-filling algorithm. In this algorithm, the users update their power spectral density (PSD) in a completely distributed and asynchronous way: some users may update their power allocation more frequently than others and they may even use outdated measurements of the received interference. The proposed algorithm represents a unified framework that encompasses and generalizes all known iterative water-filling algorithms, e.g., sequential and simultaneous versions. The main result of the paper consists of a unified set of conditions that guarantee the global converge of the proposed algorithm to the (unique) Nash equilibrium of the game.     

CDMA Uplink Power Control as a Noncooperative Game

We present a game-theoretic treatment of distributed power control in CDMA wireless systems. We make use of the conceptual framework of noncooperative game theory to obtain a distributed and market-based control mechanism. Thus, we address not only the power control problem, but also pricing and allocation of a single resource among several users. A cost function is introduced as the difference between the pricing and utility functions, and the existence of a unique Nash equilibrium is established. In addition, two update algorithms, namely, parallel update and random update, are shown to be globally stable under specific conditions. Convergence properties and robustness of each algorithm are also studied through extensive simulations.     

A Price Based Decentralized Rate Selection in IEEE 802.11 Based WLANS

We consider the problem of decentralized rate selection in IEEE 802.11 wireless local area networks (WLANs). Owing to the decentralized nature of WLANs, we formulate the current problem of rate selection as a non-cooperative game where individual users (players) of a WLAN can pick their actions from a finite set of physical layer modulation rates. The utility of each user is the difference of throughput and a cost incurred due to the price imposed by the access point. We prove the resulting non-cooperative game to be supermodular, and hence has at least one pure strategy Nash equilibrium, that is contained in a set bounded by the smallest and largest Nash equilibria. We also prove the smallest and largest Nash equilibria to be non-decreasing functions of the price and the smallest Nash equilibrium to be Pareto-dominant. We present an algorithm to compute the best response of each user asynchronously, that converges almost surely to the smallest Nash equilibrium of the game. Next we extend our price based approach to the multi-channel case and prove the resulting game to be supermodular in the special case of two channels. Our simulation results demonstrate the improvement in overall network throughput with appropriate tuning of the price.     

Joint random access and power control game in ad hoc networks with noncooperative users

We consider a distributed joint random access and power control scheme for interference management in wireless ad hoc networks. To derive decentralized solutions that do not require any cooperation among the users, we formulate this problem as noncooperative joint random access and power control game, in which each user minimizes its average transmission cost with a given rate constraint. Using supermodular game theory, the existence and uniqueness of Nash equilibrium are established. Furthermore, we present an asynchronous distributed algorithm to compute the solution of the game based on myopic best response updates, which converges to Nash equilibrium globally. Finally, a link admission algorithm is carried out to guarantee the reliability of the active users. Performance evaluations via simulations show that the game-theoretical based cross-layer design achieves high performance in terms of energy consumption and network stability.     

基于融合的无线传感器网络k-集覆盖的分布式算法

当节点采用概率感知模型且融合多个节点的数据进行联合感知的情况下,提出了一个新的无线传感器网络的覆盖优化问题:基于融合的k-集覆盖优化问题.首先,将优化问题建模为融合覆盖博弈,证明该博弈是势博弈,且势函数与优化目标函数一致,因此,最优解是一个纯策略Nash均衡解.其次,给出了节点间融合覆盖效用独立的判定条件,进而分别提出同步、异步控制的、基于局部信息的、分布式的覆盖优化算法,证明了算法收敛到纯策略Nash均衡.最后,仿真实验结果表明,当算法收敛时,网络能达到高的覆盖率且具有好的覆盖稳定性.     

The stable paths problem and interdomain routing

Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems to independently define their routing policies with little or no global coordination. It is then natural to ask if BGP can be viewed as a distributed algorithm for solving some fundamental problem. We introduce the stable paths problem and show that BGP can be viewed as a distributed algorithm for solving this problem. Unlike a shortest path tree, such a solution does not represent a global optimum, but rather an equilibrium point in which each node is assigned its local optimum. We study the stable paths problem using a derived structure called a dispute wheel, representing conflicting routing policies at various nodes. We show that if no dispute wheel can be constructed, then there exists a unique solution for the stable paths problem. We define the simple path vector protocol (SPVP), a distributed algorithm for solving the stable paths problem. SPVP is intended to capture the dynamic behavior of BGP at an abstract level. If SPVP converges, then the resulting state corresponds to a stable paths solution. If there is no solution, then SPVP always diverges. In fact, SPVP can even diverge when a solution exists. We show that SPVP will converge to the unique solution of an instance of the stable paths problem if no dispute wheel exists     

未知环境中基于图型博弈和Multi-Q学习的动态信道选择算法

研究了分布式无线网络中,没有任何信息交换、也没有环境变化先验知识情况下的动态信道接入算法。运用图型博弈模型对用户的实际拓扑进行建模分析,证明了此博弈模型存在纯策略纳什均衡并且此纳什均衡是全局最优解。同时,采用multi-Q学习求解模型的纯策略纳什均衡解。仿真实验验证了multi-Q学习能获得较高的系统容量以及在图型博弈模型中用户的效用主要由节点的度决定,而与用户数量无直接关系。     

Game-Theoretic Joint Power Allocation and Beamforming for Cognitive MIMO Systems with Finite Feedback

In the paper, we consider the imperfect channel state information (CSI) in practical cognitive MIMO systems. We first analyze the feedback of quantified CSI from the primary user (PU) and propose a joint power allocation and beamforming algorithm via game theory. Compared with the game under the condition of perfect CSI, new utility function and cost function are constructed under imperfect CSI. We analyze the error introduced from the uniformly quantified CSI and obtain new constraints. Besides, existence of the Nash equilibrium in case of both perfect CSI and imperfect CSI are proven. We propose a new iterative algorithm to reach the Nash equilibrium (NE). Simulation results show that the proposed algorithm can converge quickly.     

Bottleneck Routing Games in Communication Networks

We consider routing games where the performance of each user is dictated by the worst (bottleneck) element it employs. We are given a network, finitely many (selfish) users, each associated with a positive flow demand, and a load-dependent performance function for each network element; the social (i.e., system) objective is to optimize the performance of the worst element in the network (i.e., the network bottleneck). Although we show that such "bottleneck" routing games appear in a variety of practical scenarios, they have not been considered yet. Accordingly, we study their properties, considering two routing scenarios, namely when a user can split its traffic over more than one path (splittable bottleneck game) and when it cannot (unsplittable bottleneck game). First, we prove that, for both splittable and unsplittable bottleneck games, there is a (not necessarily unique) Nash equilibrium. Then, we consider the rate of convergence to a Nash equilibrium in each game. Finally, we investigate the efficiency of the Nash equilibria in both games with respect to the social optimum; specifically, while for both games we show that the price of anarchy is unbounded, we identify for each game conditions under which Nash equilibria are socially optimal.     

Virtual path bandwidth allocation in multiuser networks

We consider a multiuser network that is shared by noncooperative users. Each user sets up virtual paths that optimize its own selfish performance measure. This measure accounts for the guaranteed call level quality of service, as well as for the cost incurred for reserving the resource. The interaction among the user strategies is formalized as a noncooperative game. We show that the game has a unique Nash equilibrium and that it possesses a certain fairness property. We investigate the dynamics of this game and prove convergence to the Nash equilibrium of both a Gauss-Seidel scheme and a Jacobi scheme. We extend our study to various general network topologies. Finally, the formal results and some extensions thereof are tested by emulating the schemes on an experimental network     

Dense femtocell networks power self‐optimization: an exact potential game approach

Femtocell is regarded as a promising technology to enhance indoor coverage and improve network capacity. However, highly dense and self‐organized femtocells in urban environment will result in serious inter‐femtocell interference. To solve this problem, this paper proposes a distributed power self‐optimization scheme for the downlink operation of dense femtocell networks. First, a novel convex pricing mechanism is presented to price the transmit power of femtocells and construct the utility function of femtocells. Then, a noncooperative game framework for power self‐optimization of femtocells in dense femtocell networks is established on the basis of the exact potential game theory, which is demonstrated to converge to a pure and unique Nash equilibrium. Finally, combined with firefly algorithm, an effective power self‐optimization algorithm with guaranteed convergence is proposed to achieve the Nash equilibrium of the proposed game. With practical LTE parameters and a 3GPP dual‐strip femtocell model, simulation results show that the proposed game with convex pricing mechanism increases the femtocell network throughput by 7% and reduces the average transmit power of femtocells by 50% in dense femtocell networks, with respect to the compared schemes. Copyright © 2014 John Wiley & Sons, Ltd.     

BiLSTM Based Reinforcement Learning for Resource Allocation and User Association in LTE-U Networks

LTE-unlicensed (LTE-U) technology is a promising innovation to extend the capacity of cellular networks. The primary challenge for LTE-U is the fair coexistence between LTE systems and the incumbent WiFi systems. In this paper, we aim to maximize the long-term average per-user LTE throughput with long-term fairness guarantee by jointly considering resource allocation and user association on the unlicensed spectrum within a prediction window. We first formulate the problem as an NP-hard combinatorial optimization problem, then reformulate it as a non-cooperative game by applying the penalty function method. To solve the game, a novel reinforcement learning approach based on Bi-directional LSTM neural network is proposed, which enables small base stations (SBSs) to predict a sequence of future actions over the next prediction window based on the historical network information. It is shown that the proposed approach can converge to a mixed-strategy Nash equilibrium of the studied game and ensure the long-term fair coexistence between different access technologies. Finally, the effectiveness of the proposed algorithm is demonstrated by numerical simulation.

     

Non-Cooperative Multicast and Facility Location Games

We consider a multicast game with selfish non- cooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium. The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with in players, we establish an upper bound of O(radicnlog² n) on the price of anarchy, and a lower bound of Omega(log n/log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.     

On the stability of distributed sequence adaptation for cellular asynchronous DS-CDMA systems

We consider the sequence adaptation problem for cellular asynchronous code-division multiple-access (CDMA) systems. A game-theoretic approach is used to investigate the stability issues of distributed adaptation algorithms. It is shown that the Nash equilibrium may not exist for cellular CDMA systems if the traditional interference measure is used. In turn we propose a new interference measure which ensures system stability.     

Multiuser rate-based flow control

Flow and congestion control allow the users of a telecommunication network to regulate the traffic that they send into the network in accordance with the quality of service that they require. Flow control may be performed by the network, as is the case in asynchronous transfer mode (ATM) networks (the available bit rate (ABR) transfer capacity), or by the users themselves, as is the case in the Internet [transmission control protocol/Internet protocol (TCP/IP)]. We study both situations using optimal control and dynamic game techniques. The first situation leads to the formulation of a dynamic team problem, while the second one leads to a dynamic noncooperative game, for which we establish the existence and uniqueness of a linear Nash equilibrium and obtain a characterization of the corresponding equilibrium policies along with the performance costs. We further show that when the users update their policies in a greedy manner, not knowing a priori the utilities of the other players, the sequence of policies thus generated converges to the Nash equilibrium. Finally, we study an extension of the model that accommodates multiple traffic types for each user, with the switching from one type of traffic to another being governed by a Markov jump process. Presentation of some numerical results complements this study     

多用户MIMO系统中基于博弈论的鲁棒性功率分配

针对多用户多输入多输出( MU-MIMO)天线系统,提出了一种基于非合作博弈论的功率分配方案。此博弈模型中,以用户在系统中的信号泄漏噪声比值( SLNR)作为用户功率分配和公平性参数设置的依据,保证用户所期望的服务质量和公平性,并证明了纳什均衡的存在性。其次,考虑信道估计误差的影响,提出了一种基于滑动模型的迭代功率分配控制算法满足所有用户的最小通信质量要求。仿真结果显示此方案在信道误差的情况下,相比现有方案可提高系统吞吐量。     

Competitive routing in multiuser communication networks

The authors consider a communication network shared by several selfish users. Each user seeks to optimize its own performance by controlling the routing of its given flow demand, giving rise to a noncooperative game. They investigate the Nash equilibrium of such systems. For a two-node multiple links system, uniqueness of the Nash equilibrium is proven under reasonable convexity conditions. It is shown that this Nash equilibrium point possesses interesting monotonicity properties. For general networks, these convexity conditions are not sufficient for guaranteeing uniqueness, and a counterexample is presented. Nonetheless, uniqueness of the Nash equilibrium for general topologies is established under various assumptions     

Competitive Pricing for Spectrum Sharing in Cognitive Radio Networks: Dynamic Game, Inefficiency of Nash Equilibrium, and Collusion

We address the problem of spectrum pricing in a cognitive radio network where multiple primary service providers compete with each other to offer spectrum access opportunities to the secondary users. By using an equilibrium pricing scheme, each of the primary service providers aims to maximize its profit under quality of service (QoS) constraint for primary users. We formulate this situation as an oligopoly market consisting of a few firms and a consumer. The QoS degradation of the primary services is considered as the cost in offering spectrum access to the secondary users. For the secondary users, we adopt a utility function to obtain the demand function. With a Bertrand game model, we analyze the impacts of several system parameters such as spectrum substitutability and channel quality on the Nash equilibrium (i.e., equilibrium pricing adopted by the primary services). We present distributed algorithms to obtain the solution for this dynamic game. The stability of the proposed dynamic game algorithms in terms of convergence to the Nash equilibrium is studied. However, the Nash equilibrium is not efficient in the sense that the total profit of the primary service providers is not maximized. An optimal solution to gain the highest total profit can be obtained. A collusion can be established among the primary services so that they gain higher profit than that for the Nash equilibrium. However, since one or more of the primary service providers may deviate from the optimal solution, a punishment mechanism may be applied to the deviating primary service provider. A repeated game among primary service providers is formulated to show that the collusion can be maintained if all of the primary service providers are aware of this punishment mechanism, and therefore, properly weight their profits to be obtained in the future.