8th International Workshop on Resource Allocation and Cooperation in Wireless Networks 2012 - Program

Time Session

Friday, May 18

09:00-09:15 Opening and welcome
09:15-10:15 Keynote session
10:15-10:40 Break
10:40-12:20 Games and Optimization
12:20-13:30 Lunch
13:30-15:10 Information and Cooperation
15:10-15:30 Break
15:30-17:10 Scheduling and Resource Management

Friday, May 18

09:00 - 09:15

Opening and welcome

09:15 - 10:15

Keynote session

Tamer Basar: Incentivizing Agents Toward Efficient Resource Utilization in Networks
Game theory provides a rich set of tools, of both conceptual and algorithmic nature, in settings where competition and/or cooperation among different entities are commonplace, and there is also the need for strategic decision-making. One such setting is that of wireless networks, where typical resources to be allocated or shared are bandwidths, spectra, and routes, and typical agents that can be viewed as players are users (primary and secondary), and providers. Within this setting, this talk will provide an overview of the relevant methodologies from game theory, stressing an economics-centric framework, and concentrating on two main topics, namely, pricing of services, and incentivizing players through mechanism designs (or reverse engineering). Both these topics involve multi-agent decentralized decision-making in an uncertain environment with distributed computation. The talk will cover some specific existence, uniqueness and computational issues that arise in these contexts, as well as some asymptotics for large-population regimes.

10:15 - 10:40

Break

10:40 - 12:20

Games and Optimization

Fair Scheduling in Common-Pool Games by Aspiration Learning
Georgios Chasparis (Lund University, Sweden); Ari Arapostathis (University of Texas at Austin, USA); Jeff Shamma (Georgia Institute of Technology, USA)
We propose a distributed learning algorithm for fair scheduling in common-pool games. Common-pool games are strategic-form games where multiple agents compete over utilizing a limited common resource. A characteristic example is the medium access control problem in wireless communications, where multiple users need to decide how to share a single communication channel so that there are no collisions (situations where two or more users use the medium at the same time-slot). We introduce a (payoff-based) learning algorithm, namely aspiration learning, according to which agents learn how to play the game based only on their own prior experience, i.e., their previous actions and received rewards. Decisions are also subject to a small probability of mistakes (or mutations). We show that when all agents apply aspiration learning, then as time increases and the probability of mutations goes to zero, the expected percentage of time that agents utilize the common resource is equally divided among agents, i.e., fairness is established. When the step size of the aspiration learning recursion is also approaching zero, then the expected frequency of collisions approaches zero with time.
Optimal Power Policy and Throughput Analysis in Cognitive Broadcast Networks Under Primary's Outage Constraint
Athipat Limmanee (University of Melbourne, Australia); Subhrakanti Dey (University of Melbourne, Australia)
This paper focuses on a spectrum-sharing based cognitive radio fading broadcast channel (BC) with a secondary base station (SBS) and $M$ secondary receivers (SRs) concurrently utilizing the same spectrum band with one delay-sensitive primary user (PU). The quality-of-service requirement in the primary network is given by the primary user's outage probability constraint (POC). We address the optimal power allocation problem for the ergodic sum capacity (ESC) maximization in the secondary BC network subject to a POC and an average transmit power constraint at SBS. Optimality conditions reveal that in each fading block SBS will choose only one SR with the highest channel power gain and allocate the block to that user. Furthermore, if PU's power strategy is assumed to be ON-OFF with constant power when ON, the secondary network throughput scaling for large $M$ in Rayleigh fading is also investigated. It is shown that the secondary sum throughput in Rayleigh fading BC scales as O(log(log M)). Numerical results support the theoretical results derived in the paper.
Power Control Under Best Response Dynamics for Interference Mitigation in a Two-Tier Femtocell Network
Vaggelis G. Douros (Athens University of Economics and Business, Greece); Stavros Toumpis (Athens University of Economics and Business, Greece); George C. Polyzos (Athens University of Economics and Business, Greece)
Femtocell networks are about to be extensively deployed with the aim of providing substantial improvements to cellular coverage and capacity. However, their deployment is nontrivial because of the extra interference that the femtocell nodes cause to the macrocell nodes with which they share the same portion of the spectrum. This paper proposes a non-cooperative power control approach for interference mitigation in a two-tier femtocell network where the first tier is a conventional cellular network and the second tier is a set of (short-range) femtocells. We define objective functions that are different for Femtocell Mobile Nodes (FMNs) and macrocell Mobile Nodes (MNs). We then define a power control game, we prove the existence of a Nash Equilibrium (NE) for that game and we analyze the necessary and sufficient conditions so that the NE is unique. Based on the best response dynamics method, we propose a distributed iterative power control scheme that, starting from any initial power vector, converges to that NE. We simulate various scenarios that are based on realistic assumptions and topologies. Results show that, in many cases, in the NE, smooth coexistence of all entities of the topology is feasible.
Satisfying Demands in Heterogeneous Networks
Veeraruna Kavitha (SRM University & SRM Research Institute, India); Sreenath Ramanath (Lekha Wireless, India); Mérouane Debbah (Supelec, France)
In this paper, we consider a heterogeneous network (eg. Macrocells overlaid with Small cells), where users associated with their respective base stations (BS) demand certain rates. These users interfere with each other and one needs an algorithm that satisfies the demands irrespective of the number of interferers and the amount of interference (whenever the demands are within the achievable limits). In our previous paper, we proposed one such iterative power allocation algorithm called UPAMCN (Universal power allocation algorithm for multicell networks), when all the agents update their power profiles at the same rate. Using two time scale stochastic approximation analysis, we analyze the same (UPAMCN) algorithm, when the heterogeneous agents update their power profiles at different rates. We obtain partial analysis of the algorithm using an ODE framework and demonstrate the convergence of the proposed algorithm via numerical examples and simulations.

12:20 - 13:30

Lunch

13:30 - 15:10

Information and Cooperation

Invited talk: Emilio Leonardi - Exploiting Channel Memory for Wireless Scheduling with limited Channel Measurements: An asymptotic study We consider a wireless downlink scenario with a large number of available channels under the following two assumptions: (i) channels states can be explicitly sensed at a limited rate; (ii) channels are modeled as i.i.d. ON/OFF Markov chains. Our goal is to characterize the fundamental trade-off between system throughput and channel sensing rate in the challenging scenario in which jointly the number of channels tends to infinity and the probability of finding an individual channel in the ON state tends to zero. To this end, we propose a simple scheduling algorithm that effectively exploits channel memory to maximize the successful transmission probability. We obtain the sufficient and necessary conditions to achieve the maximum (in order sense) system throughput.
Exploiting Channel Memory for Wireless Scheduling with Limited Channel Probing: An Asymptotic Study
Paolo Giaccone (Politecnico di Torino, Italy); Emilio Leonardi (Politecnico di Torino, Italy)
We consider a wireless downlink communication system with N parallel channels under the following two assumptions: (1) the channels states can be explicitly sensed at a limited rate λ_s, (2) channels are modeled as i.i.d., ON/OFF Markov chains with stationary distribution [π_OFF , π_ON]. The goal of this paper is to characterize the fundamental trade-off between system throughput and channel sensing rate λ_s in the challenging scenario in which N → ∞ and jointly π_ON → 0. To this end, we propose a simple scheduling algorithm that effectively exploits channel memory to maximize the successful transmission probability. We obtain sufficient and necessary conditions to achieve maximum (in order sense) system throughput. Finally, we show the performance of our policy under a non-asymptotic scenario.
XOR-based Coding for the 3-user Broadcast Erasure Channel with Feedback
Sophia A. Athanasiadou (Aristotle University of Thessaloniki, Greece); Marios Gatzianas (Center for Research and Technology Hellas, Telematics and Informatics Institute, Greece); Leonidas Georgiadis (Aristotle University of Thessaloniki, Greece); Leandros Tassiulas (University of Thessaly, Greece)
We study the case of the three-user broadcast erasure channel, with multiple unicast traffic, where feedback from the users is fed back to the transmitter in the form of ACK/NACK messages. We propose two coding algorithms, named XOR1 and XOR2, which operate on a specially constructed network of virtual queues. XOR2 is more sophisticated than XOR1 but achieves a known capacity outer bound in the following settings 1) spatially i.i.d. erasures for all values of erasure probability and 2) spatially independent erasures where the maximum erasure probability does not exceed 8/9. The algorithms rely only on simple XOR operations between packets, allow instantaneous decoding and require no knowledge of channel statistics.
Energy Efficient Routing with Mutual Information Accumulation
Tolga Girici (TOBB Economics and Technology University, Turkey); Ahmet Kazez (TOBB Economics and Technology University, Turkey)
We consider minimum-energy routing in a wireless network. We assume the use of ideal rateless codes, so that a node can accumulate transmission rates from the transmission of previous nodes on the routing path. Mutual information accumulation has significant advantages when compared with classical0 cooperative schemes that use energy accumulation. However, the resource allocation problem becomes more complex, as it involves the determination of 1) Routing path, 2) Transmission duration of each node, and 3) Transmission power of each node. We formulated the problem as an optimization problem, where the objective function is the total energy expenditure and the constraints are minimum mutual information for each node and the maximum total transmission time. The joint power/time optimization problem has a biconvex nature, which admits coordinate-descent type of solutions. The optimal routing path is found using a branch-and-bound technique. The energy gains are measured by comparison with a simple routing and resource allocation scheme.
Network Cooperation for Client-AP Association Optimization
Akash Baid (WINLAB, Rutgers University, USA); Michael Schapira (Hebrew University of Jerusalem, USA); Ivan Seskar (Rutgers University, USA); Jennifer Rexford (Princeton University, USA); Dipankar Raychaudhuri (Rutgers University, USA)
Optimization of client-AP association pattern has been shown to improve load balancing and user throughput in multi-AP enterprise/hot-spot WiFi deployments. In this paper, we propose and evaluate a cooperation scheme between two or more such overlapping hot-spot networks that incorporates inter-network interference in the client-AP association optimization problem. We model the effects of multiple overlapping WiFi deployments, determine the information that networks need to share and formulate a non-linear program that each network can solve for proportional fair optimal client-AP association. Assuming a sum of log rates utility function, we reuse a known 2 + ϵ approximation algorithm for solving the NP-hard problem in polynomial time. We evaluate the performance gain through large scale simulations with 2-4 overlapping networks, each consisting of 15-35 access points(APs) and 50-250 users in a 0.5x0.5 sq.km. urban setting. Results show an average of 150% improvement in the 10 percentile client throughputs with modest reductions in the mean throughputs

15:10 - 15:30

Break

15:30 - 17:10

Scheduling and Resource Management

Invited Talk: Jianwei Huang - Partial Cooperation for Spectrum Sharing in Cognitive Radio Network Today's wireless spectrum is both scarce (for emerging applications) and heavily under utilized (by existing licensees), mainly due to the static licensing policy. Cognitive radio technology has the potential to significantly improve the spectrum utilization and provide new spectrum resources for new devices and applications. A major obstacle of large-scale industry adoptions of cognitive radio, however, is the lack of proper business models that integrate the unique features of cognitive radio technology. We propose the concept of Cognitive Virtual Network Operator (CVNO), which is an operator who provides services to the secondary unlicensed wireless devices without actually owning the wireless spectrum. Compared with a traditional virtual network operator who often leases spectrum via long-term contracts, a CVNO can acquire spectrum dynamically in short-term by both sensing the "spectrum holes" of licensed bands and leasing from the spectrum owner. As a result, a CVNO can make flexible investment and pricing decisions to match the current demands of the secondary unlicensed users. We discuss two scenarios in this talk. In the first case, a monopoly CVNO makes the optimal investment and pricing decisions with supply uncertainty. The system can be modeled as a four-stage Stackelberg game. In the second case, two CVNOs compete with each other to attract the demands from the same pool of end-users. We model this system as a three-stage multi-leader dynamic game. In both cases, we characterize the existence and uniqueness of the subgame perfect equilibrium, and show various interesting engineering insights in terms of operators' investment/pricing decisions and the end-users' QoS. The equilibrium decisions of the CVNO enjoy simple threshold based properties and have low implementation complexities.
Partial Cooperation for Spectrum Sharing in Cognitive Radio Network
Lok Man Law (The Chinese University of Hong Kong, Hong Kong); Fen Hou (Macao Polytechnic Institute, Macao); Jianwei Huang (The Chinese University of Hong Kong, Hong Kong)
In this paper, we consider a cognitive radio network where secondary users may have different sets of available channels. We propose a partial cooperation scheme that captures the feature of incomplete channel availability information under spatial heterogeneity. It encourages cooperation among users in a group with the same priority channel, while allows contentions among users from different groups. We show that our proposed scheme achieves a good balance between the channel utiliza- tion and additional signaling overhead by comparing with no cooperation and full cooperation schemes. We further derive the lower bound of channel utilization of the proposed scheme by comparing it with a full cooperation scheme. Numerical results show that the average performance of the scheme can be more than two times better than the lower bound derived. In our simulations, the scheme is up to 15% better in channel utilization than the no cooperation scheme.
Flow Optimization in Delay Tolerant Networks Using Dual Decomposition
Savvas Gitzenis (Certh, Greece); George Konidaris (Athens University of Economics and Business, Greece); Stavros Toumpis (Athens University of Economics and Business, Greece)
We study flow optimization in Delay Tolerant Networks (DTNs), which we model using structures called Capacity Region Evolving Graphs (CREGs). CREGs comprise different instances (called replicas) of the actual network graph in cascade; each replica is associated with a distinct time period (called epoch) and its own Capacity Region. Although CREGs can model any DTN, they are particularly well suited for the study of wireless ones. We define a single-commodity utility maximization problem in a CREG of T replicas that contains as special cases various interesting flow maximization problems. Using dual decomposition, we cast the maximization as a dual problem that can be solved iteratively and where in each iteration a set of T problems, T times smaller than the original, are solved, potentially (if multiple processors are available) in parallel. In addition, we propose two suboptimal utility maximization heuristics that operate on an epoch-by-epoch basis.
Optimal Capacity Relay Node Placement in a Multi-hop Network on a Line
Arpan Chattopadhyay (Indian Institute of Science, India); Abhishek Sinha (Indian Institute of Science, India); Marceau Coupechoux (TELECOM ParisTech, France); Anurag Kumar (Indian Institute of Science, India)
We use information theoretic capacity formulas for the relay channel to study the problem of optimal placement of relay nodes along the straight line joining a source node and a destination node. The capacity formulas that we utilize are for full-duplex radios at the relays and decode-and-forward relaying. For the single relay case, and individual power constraints at the source node and the relay node, we derive the optimal relay placement and the optimal power allocation to the source-relay channel, for the exponential and the power-law path-loss channel models. We find that at low attenuation cooperation between source and relay is important and hence the relay should be placed close to the source, whereas at high attenuation the relay merely works as a repeater and should be placed at the center of the line segment joining the source and the destination. For the multiple relay case, we consider exponential path-loss and a total power constraint over the source and the relays, and derive an optimization problem, the solution of which provides the optimal relay locations. Numerical results from solving the problem suggest that at low attenuation the relays are mostly clustered close to the source in order to be able to cooperate among themselves and with the source, while needing minimum power for the source to transmit the message to them; on the other hand, at high attenuation they are uniformly placed and work as repeaters.
Low Complexity Grouping for Massive Scheduling in 4G Networks
Qianrui Li (EURECOM, France); Lusheng Wang (EURECOM, France); Laura Cottatellucci (EURECOM, France); Navid Nikaein (Eurecom, France)
In this paper, we investigate user grouping for cooperative scheduling in a two-cell network. When the number of transmitters grows large, the complexity of user grouping algorithms becomes quickly exorbitant and unaffordable in real-time systems. We consider user grouping algorithms maximizing the network sum rate in cell with a massive number of users. We provide a suboptimal user grouping algorithm based on the statistics of scheduling pattern which substantially reduces complexity compared to the optimum Hungarian algorithm with negligible capacity degradation. Surprisingly, it outperforms the greedy algorithm with a considerable lower complexity.