# 10th International Symposium of Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks - Program

Time Session

## Tuesday, May 15

08:45 Opening and welcome
09:00 Keynote: On Location Privacy
10:15 Break,
Medium access
11:45 Lunch
12:45 Games and Learning
14:15 Break
14:30 Cellular Networks
16:00 Break
16:15 Delay Minimization

## Wednesday, May 16

09:00 Keynote: Effective information delivery through opportunistic replication in wireless networks
10:00 Break
10:15 Network Optimisation
11:45 Lunch
14:15 Break
14:30 Game Theory
16:00 Social event

## Thursday, May 17

09:00 Keynote: User Cooperation and Conferencing Encoders for Different Classes of Multiple-Access Channels
10:00 Break
10:15 Relay Networks
11:45 Lunch
12:45 Routing
14:15 Break
14:30 Scheduling

## Tuesday, May 15

### 09:00 - 10:00

#### Keynote: On Location Privacy

Jean-Pierre Hubaux
The more pervasive wireless networks become, the more our private location data get exposed. In this talk, we will describe some solutions to this problem, including mix zones and their application to vehicular networks. We will also address non-cooperative behavior in privacy protection. Then we will show how location privacy can be quantified. We will also discuss why so much public research funding is devoted to the further improvement of (wireless) networks (in spite of the fact that manufacturers will take care of that anyhow) and so little to privacy protection (which is usually not a vendors' priority).

### 10:15 - 11:45

#### Medium access

Interference-safe CSMA Networks by Local Aggregate Interference Power Measurement
Chi-Kin Chau (Masdar Institute & MIT, UAE); Jialiang Zhang (The Chinese University of Hong Kong, P.R. China); Minghua Chen (The Chinese University of Hong Kong, P.R. China); Soung Chang Liew (The Chinese University of Hong Kong, Hong Kong)
Most current wireless IEEE 802.11 networks rely on a power-threshold based carrier-sensing multi-access (CSMA) mechanism to prevent packet collisions, where a transmitter permits its transmission only if the locally measured "aggregate interference power" from all the existing transmissions is below a pre-specified power-sensing threshold. But improper configuration of power-sensing threshold cannot ensure interference-safe transmissions, resulting in degradation of throughput and fairness performance. This paper presents the first viable solution for fully interference-safe transmissions that (1) is based on a realistic signal-to-interference-and-noise ratio (SINR) model, and (2) is compatible with the carrier-sensing mechanism in existing CSMA networks. These two features uniquely distinguish our work from the previous studies. Specifically, we determine a proper interference-safe power-sensing threshold by considering both the effects of (i) arbitrary ordering of local interference power measurements, and (ii) ACK frames. We compare our interference-safe solution with other solutions, and provide extensive evaluation on its throughput and fairness performance.
Flow-Level Stability of Multihop Wireless Networks Using Only MAC-Layer Information
Javad Ghaderi (University of Illinois at Urbana-Champaign, USA); R. Srikant (University of Illinois at Urbana-Champaign, USA)
It is by now well-known that wireless networks with file arrivals and departures are stable if one uses alpha-fair congestion control and back-pressure based scheduling and routing. In this paper, we examine whether alpha-fair congestion control is necessary for flow-level stability. We show that stability can be ensured even with very simple congestion control mechanisms, such as a fixed window size scheme which limits the maximum number of packets that are allowed into the ingress queue of a flow. A key ingredient of our result is the use of the difference between the logarithms of queue lengths as the link weights. This result is reminiscent of results in the context of CSMA algorithms, but for entirely different reasons.
Stability and Instability of Backlog-Based Random Access in Wireless Networks
Sem Borst (Alcatel-Lucent, Bell Labs & Eindhoven University of Technology, USA); Javad Ghaderi (University of Illinois at Urbana-Champaign, USA); Phil Whiting (Bell Labs, Lucent Technologies, USA)
While simple and inherently distributed, backlog-based access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. The type of activation rules for which throughput optimality has been established, may however yield excessive backlogs and delays. More aggressive/persistent access schemes have the potential to improve the delay performance, but do not offer any universal maximum-stability guarantees. Motivated by the above issues, we use fluid limits to explore the (in)stability properties of wireless networks with backlog-based random-access algorithms. Such fluid limits have varying qualitative properties, dependent on the specific scenario, ranging from ones with smooth deterministic features, to others which exhibit random oscillatory characteristics. It turns out that more aggressive access schemes continue to provide maximum stability in some networks, e.g. complete interference graphs. As we show however, in other topologies such schemes can drive the system into inefficient states and thus cause instability. Simulation experiments are conducted to illustrate and validate the analytical results.
Delay-Constrained Multi-hop CSMA Networks
Yaniv George (Bar-Ilan University, Israel); Itsik Bergel (Bar Ilan University, Israel); Ephraim Zehavi (Bar-Ilan University, Israel)
The mean packet delay (MPD) of multi-hop wireless ad-hoc networks (WANET) has a major impact on the networks performance and quality of service. In this paper we analyze the performance of slotted carrier sense multiple access (CSMA) WANET under a MPD constraint. The MPD is determined by the mean number of hops between sources and destination pairs, the back-off probability and the outage probability. Using stochastic geometry analysis we perform a cross-layer optimization and present a simple expression for the area spectral efficiency (ASE) of the network as function of the MPD and the fading channel properties. Our main result is that the ASE grows linearly with the allowed MPD, D. The linear scaling coefficient can also be evaluated from the ASE expression: For example, with mean source-destination distance of L, a network that operates over Rayleigh fading channels with a path loss factor of 4 can achieve a maximum of 0.04D/L source-bits per second per hertz per square-meter. The accuracy of the presented results is demonstrated by numerical simulations.

### 12:45 - 14:15

#### Games and Learning

Online Learning to Optimize Transmission Over Unknown Gilbert-Elliot Channel
Yanting Wu (University of Southern California, USA); Bhaskar Krishnamachari (University of Southern California, USA)
This paper studies the optimal transmission policy for a Gilbert-Elliot Channel. The transmitter has two actions: sending aggressively or sending conservatively, with rewards depending on the action chosen and the underlying channel state. The aim is to compute the scheduling policy to determine which actions to choose at each time slot in order to maximize the expected total discounted reward. We first establish the threshold structure of the optimal policy when the underlying channel statistics are known. We then consider the more challenging case when the statistics are unknown. For this problem, we map different threshold policies to arms of a suitably defined multi-armed bandit problem. To tractably handle the complexity introduced by countably infinite arms and the infinite time horizon, we weaken our objective a little: finding a $(1-(\epsilon+\delta))$-approximate policy instead. We present the UCB-P algorithm, which can achieve this objective with logarithmic-time regret.
Collusion of Operators in Wireless Spectrum Markets
Omer Korcak (Marmara University, Turkey); Tansu Alpcan (The University of Melbourne, Australia); George Iosifidis (University of Thessaly, CERTH & CERTH, HELLAS, Greece)
Collusion of operators in wireless spectrum markets are investigated using a coalitional (cooperative) game approach. Although illegal and detrimental to users, such collusions are often observed in real life, e.g. in the form of price fixing. Building on an evolutionary game model of the market, the conditions for and dynamics of coalition formation among operators are rigorously studied. The results obtained provide a foundation for effective measures against operator collusion by altering the underlying motivations rather than fighting against the symptoms.
A Bayesian Jamming Game in an OFDM Wireless Network
Andrey Garnaev (St.-Petersburg State University, Russia); Yezekael Hayel (LIA, University of Avignon, France); Eitan Altman (INRIA, France)
The goal of this paper is to investigate how incomplete information on the fading channel gains impacts transmission parameters. We consider in an OFDM network with transmitters and jammers. To deal with this situation we employ a Bayesian approach by introducing different type of user and jammer corresponding to their knowledge of the network environment. To get an insight of the problem, the signal to interference and noise ratio (SINR) is considered as the main metric to optimize. First, equilibrium are found in closed form expressions. Second, we show interesting results saying that incomplete information on the jammer channel gains leads to equilibrium strategies which correspond to utilization of the same channels by the different types of the jammer. Meanwhile incomplete information about the transmitter channel gains leads to channels sharing transmission equilibrium strategies employed by different types of users.
Joint Pricing and Cognitive Radio Network Selection: a Game Theoretical Approach
Jocelyne Elias (Université Paris Descartes - Sorbonne Paris Cité, France); Fabio Martignon (Université Paris-Sud, France); Eitan Altman (INRIA, France)
This paper addresses the joint pricing and network selection problem in cognitive radio networks, considering both the point of view of network users and the Primary Operator. The problem is formulated as a Stackelberg (leader-follower) game where first the PO sets the network subscription price to maximize its revenue. Then, users perform the network selection process, deciding whether to pay for having a guaranteed service, or use a cheaper, best-effort secondary network, where congestion and low throughput may be experienced. Such process is modeled as a population game to study the strategic interactions among a large number of agents. For our pricing and network selection game, we provide equilibrium and convergence properties, and derive optimal stable price and network selection settings. Numerical results illustrate that our game model captures the main factors behind cognitive network pricing and channel selection, thus representing a promising framework for the design and understanding of cognitive radio systems.

### 14:30 - 16:00

#### Cellular Networks

Linear-Regression Estimation of the Propagation-Loss Parameters Using Mobiles' Measurements in Wireless Cellular Networks
Bartlomiej Blaszczyszyn (Inria-Ens, France); Mohamed Kadhem Karray (France Telecom R&D, France)
We propose a new linear-regression model for the estimation of the path-loss exponent and the parameters of the shadowing from the propagation-loss data collected by the mobiles with respect to their serving base stations. The difficulty consists in deriving the parameters of the distribution of the propagation loss with respect to an arbitrary base station from these regarding the strongest one. The proposed solution is based on a simple, explicit relation between the two distributions in the case of infinite Poisson network and on the convergence of an arbitrary regular (in particular hexagonal) network to the Poisson one with increasing variance of the shadowing. The new approach complements existing methods, in particular the one based on COST Walfisch-Ikegami model, which does not allow for the shadowing estimation and is not suited for indoor scenario.
Analysis of Small Cell Networks with Randomly Wandering Users
Veeraruna Kavitha (SRM University & SRM Research Institute, India); Sreenath Ramanath (Lekha Wireless, India); Eitan Altman (INRIA, France)
We develop a framework to model and study cellular networks with randomly wandering users. Our model captures user displacement resulting from random mobility patterns and arrival positions, which in turn influences the transmission rates. We model the user movements by a random walk with exponential wandering times. Each cell is composed of disjoint (allocated transmission) rate regions and we model each rate region as an equivalent step in the random walk model. We further use spatial queuing theoretic tools to obtain explicit expressions for the expected service time (total time during which user derives service from the cell), call busy and drop probabilities. We obtain approximate closed form expressions for optimal cell size (for some asymptotic speed cases and small cell radii) and validate them via numerical simulations. % We study the influence of system parameters like the path loss factor, speed of user movement, power budget etc, on these optimizers. We show that the optimal cell size increases with the increase in the speed of the users or in the power budget and decreases with increase in path loss factor.
Characterizing the Throughput Gain of Single Cell MIMO Wireless Systems with Full Duplex Radios
Sanaz Barghi (University of California, Irvine, USA); Mohammad Khojastepour (NEC Laboratories America, USA); Karthikeyan Sundaresan (NEC Labs America, USA); Sampath Rangarajan (NEC Labs America, USA)
Using additional antennas and signal processing techniques to build a full-duplex radio is becoming a popular topic in the networking research community. Traditionally, additional antennas are used for MIMO (multiple input multiple output) transmissions and it is well-known that increasing the number of antennas on either transmitter or receiver side increases the link capacity. In this work, we look at the comparison between using multiple-antennas to form a MIMO link with that of utilizing them for full-duplex systems. Our results indicate that under certain conditions, full-duplex radio can provide performance boost when additional antennas are used for full-duplex instead of MIMO.
Enabling Relaying Over Heterogeneous Backhauls in the Uplink of Femtocell Networks
Sumudu Samarakoon (Centre for Wireless Communications, University of Oulu, Finland); Mehdi Bennis (Centre of Wireless Communications, University of Oulu, Finland); Walid Saad (University of Miami, USA); Matti Latva-aho (UoOulu, Finland)
In this paper, we develop novel two-tier interference management strategies that enable macrocell users(MUEs) to improve their performance, with the help of open-access femtocells. To this end, we propose a rate-splitting technique using which the MUEs optimize their uplink transmissions by dividing their signals into two types: a coarse message that is intended for direct transmission to the macrocell base station and a fine message that is decoded by a neighboring femtocell, and subsequently relayed over a heterogeneous (wireless/wired) backhaul. For deploying the proposed technique, we formulate a non-cooperative game among the MUEs in which each MUE can decide on its relaying femtocell while maximizing a utility function that captures both the achieved throughput and the expected backhaul delay. Simulation results show that the proposed approach yields up to 50% rate improvement and up to 10 times delay reduction, relative to classical interference management approaches, with no cross-tier cooperation.

### 16:15 - 17:45

#### Delay Minimization

Optimal Sampling Strategies for Minimum Latency Routing with Imperfect Link State
Saikat Guha (BBN Technologies, USA); Don Towsley (University of Massachusetts at Amherst, USA); Prithwish Basu (BBN Technologies, USA); Howard Tripp (Roke Manor Research Ltd, United Kingdom); Timothy Freeman (Roke Manor Research Ltd, United Kingdom); Dmitriy Katz (IBM T.J. Watson Research Center, USA); Robert E Hancock (Roke Manor Research, United Kingdom); Jim Kurose (University of Massachusetts at Amherst, USA)
Since dynamic wireless networks evolve over time, optimal routing computations need to be performed frequently on time-varying network topologies. However, it is often infeasible or expensive to gather the current state of links for the entire network all the time. We provide a thorough analytical characterization of the effect of various link-state sampling strategies operating under a limited sampling budget on the performance of the minimum latency routing policy in a special class of dynamic networks. We show that for a two-state Markov link-dynamics model parameterized by probabilities p, q, if links are more likely to turn on than off at each time instant (p>q), a "depth-first" sampling strategy is optimal, whereas a "breadth-first" sampling strategy is optimal if links are more likely to turn off than on (p<q). We precisely characterize the optimal-latency spatial-sampling schedules for one-shot interrogation. Furthermore, we present numerical simulation results on comparing various spatio-temporal sampling schedules under an overall sampling rate constraint, and a few other probing cost models.
Delay Estimation and Fast Iterative Scheduling Policies for LTE Uplink
Akash Baid (WINLAB, Rutgers University, USA); Ritesh Madan (Qualcomm, USA); Ashwin Sampath (Qualcomm, USA)
We present the design and detailed evaluation of a fast iterative LTE uplink spectral resource scheduler. We model all constraints due to contiguous bandwidth allocation, peak transmit power and fractional power control. We design a novel mechanism for inferring the packet delays approximately from the buffer status reports (BSR) and construct a new non-differentiable objective function for delay based scheduling - this generalizes recent results on iterative schedulers for small delay. For frequency flat fading, we construct an O(N log L) (per iteration) optimal resource allocation algorithm for N users and L points of non-differentiability in the objective function. For a frequency diversity scheduler with M sub-bands, the corresponding complexity is essentially O(N(M^2 + L^2)) per iteration. Through detailed system simulations based on NGMN and 3GPP evaluation methodology, we demonstrate the effectiveness of our schemes for LTE. A detailed version of the paper is made available at [1] for reference.
Delay Minimization in Multihop Wireless Networks: Static Scheduling Does It
Sharad Birmiwal (University of Waterloo, Canada); Jayakrishnan Unnikrishnan Nair (California Institute of Technology, USA); D. Manjunath (IIT Bombay, India); Ravi Mazumdar (University of Waterloo, Canada)
In this paper, we seek to address the issues of poor end-to-end delay performance and high per-slot computational overhead of the classical max-weight algorithm. We propose a variant of the max-weight algorithm that promotes the use of shorter parts, which leads to significantly lower delays. Next, we study a static routing and scheduling scheme obtained by adapting the optimal routing problem in wireline networks to wireless networks. The static scheme slows the timescale of routing and scheduling computations from per-slot to the timescale of change in the network traffic pattern, and still achieves a delay performance that is comparable to our proposed dynamic scheme.
Inter-session Network Coding in Delay-Tolerant Networks Under Spray-and-Wait Routing
Lucile Sassatelli (I3S - CNRS Universite de Nice UMR, France); Muriel Médard (MIT, USA)
The goal of this paper is to derive the performance analysis for a unicast session, under Spray-and-Wait routing and inter-session network coding, in the presence of background traffic in DTN with homogeneous mobility. General settings are considered for the distribution of the data rate between nodes, the buffer size, the number of sessions contending for network resources. Thanks to mean-field approximations, fluid models are derived to predict the dissemination of the packets pertaining to different flows, thereby presenting the first, to the best of the authors knowledge, study of performance in DTN with Spray-and-Wait under the presence of contention between several sessions. The accuracy of the model is assessed through simulations based on synthetic mobility traces.

## Wednesday, May 16

### 09:00 - 10:00

#### Keynote: Effective information delivery through opportunistic replication in wireless networks

Leandros Tassiulas
Increased replication of information is observed in modern wireless networks either in pre-planned content replication schemes or through opportunistic caching in intermediate relay nodes as the information flows to the final destination or through overhearing of broadcast information in the wireless channel. In all cases the available other node information might be used to effectively increase the efficiency of the information delivery process. We will consider first an information theoretic perspective and present a scheme that exploits the opportunistically available overheard information to achieve the Shannon capacity of the broadcast erasure channel. Then we will consider information transport in a multi-hop flat wireless network and present schemes for spatial information replication based on popularity, in association with any-casting routing schemes, that achieve asymptotically optimal performance.

### 10:15 - 11:45

#### Network Optimisation

Leader Selection for Minimizing Convergence Error in Leader-Follower Systems: A Supermodular Optimization Approach
Andrew Clark (University of Washington, USA); Linda Bushnell (University of Washington, USA); Radha Poovendran (University of Washington, USA)
In leader-follower systems, follower nodes receive inputs from a set of leader nodes, exchange information, and update their states according to an iterative algorithm. In such algorithms, the node states may deviate from their desired values before the algorithm converges, leading to disruptions in network performance. In this paper, we study the problem of choosing leader nodes in order to minimize convergence errors. We first develop a connection between a class of weighted averaging algorithms and random walks on graphs, and then show that the convergence error is a supermodular function of the set of leader nodes. Based on the supermodularity of the convergence error, we derive efficient algorithms for selecting leader nodes that are within a provable bound of the optimum. Our approach is demonstrated through a simulation study.
Maximizing a Submodular Utility for Deadline Constrained Data Collection in Sensor Networks
Zizhan Zheng (The Ohio State University, USA); Ness B. Shroff (The Ohio State University, USA)
We study the utility maximization problem for data collection in sensor networks subject to a deadline constraint, where the data on a selected subset of nodes are collected through a routing tree rooted at a sink subject to the 1-hop interference model. Our problem can be viewed as a Network Utility Maximization (NUM) problem with binary decisions. However, instead of a separable concave form of system utility commonly seen in NUM, we consider the class of monotone submodular utility functions defined on subsets of nodes, which is more appropriate for the applications we consider. While submodular maximization subject to a cardinality constraint has been well understood, our problem is more challenging due to the multi-hop data forwarding nature even under a simple interference model. We have derived efficient approximation solutions to this problem both for raw data collection and when in-network data aggregation is applied.
Joint Mission and Communication Aware Mobility Control in Mobile Ad-Hoc Networks
Hee-Tae Roh (Yonsei University, Korea); Jang-Won Lee (Yonsei University, Korea)
In this paper, we study a mobility control problem in mobile ad-hoc networks with controllable mobility. Especially, we consider mission-critical networks in which nodes have their own specific mission whose degree of satisfaction depends on the their location as well as want to maintain a good communication quality with their neighbor nodes that also depends on their location. Hence, in this paper, we study a joint mission and communication aware mobility control problem. We formulate the problem as a potential game and develop a distributed algorithm that converges to the Nash equilibrium. In addition, we also show that if some minor conditions are satisfied, our algorithm provides a global optimal solution that minimizes the weighted sum of costs for mission and communication.
Nomographic Gossiping for f-Consensus
Mario Goldenbaum (Technische Universität Berlin, Germany); Holger Boche (Technical University Munich, Germany); Slawomir Stańczak (Fraunhofer Heinrich Hertz Institute, Germany)
In this paper, we present a novel class of iterative gossip algorithms called nomographic gossiping that allow to efficiently achieve a rapid global consensus among nodes/agents in clustered wireless networks with respect to an arbitrary function of the initial states. The algorithms are based on the surprising fact that every real-valued multivariate function has a nomographic representation, which is simply a function of a superposition of a finite number of univariate functions. Since superpositions can be effectively generated via the wireless channel by letting nodes in a cluster transmit simultaneously their pre-processed states to a cluster head, the convergence speed can be significantly increased provided that some connectivity condition between clusters is fulfilled. The proposed class of algorithms consists of an uncoordinated randomized approach that converges almost surely, as well as of deterministic protocols that converge in a finite number of iterations under the drawback of some required coordination.

### 12:45 - 14:15

Aylin Turhan (Boston University, USA); Murat Alanyali (Boston University, USA); David Starobinski (Boston University, USA)
We study optimal admission control of secondary users (SUs) in cognitive radio (CR) networks in presence of preemption. In this model, when a primary user (PU) arrives to the system and finds all the channels busy, it preempts an SU unless all the customers in the system are PUs. We apply admission control on the SUs only. Using dynamic programming (DP), we find the optimal admission control policy that maximizes the long-run average revenue. As our main contribution, we show that the optimal admission control of the SUs depends only on the total number of customers in the system (i.e. it does not depend on the number of PUs and SUs in the system individually) and is of threshold type. Therefore, although the system is modeled as a two-dimensional Markov chain, our findings allow simple and efficient computation of the optimal control policy.
Imitative Spectrum Access
Xu Chen (The Chinese University of Hong Kong, Hong Kong); Jianwei Huang (The Chinese University of Hong Kong, Hong Kong)
Cognitive radio is a promising technology for improving the spectrum utilization. In this paper, we study how secondary users can share the spectrum in a distributed fashion based on imitations. In the proposed imitative spectrum access mechanism, each secondary user estimates its expected throughput based on local observations, and imitates the channel selection of another user who achieves a higher throughput. We show that the imitative spectrum access mechanism converges to an imitation equilibrium wherein no imitation can be further carried out on the time average. Numerical results show that when the number of users is large, the imitative spectrum access mechanism can converge to a Nash equilibrium, which is a special case of the imitation equilibrium.
A Soft Sensing-Based Cognitive Access Scheme Exploiting Primary Feedback
Ahmed M. Arafa (Nile University, Egypt); Karim G Seddik (American University in Cairo & Alexandria University, Egypt); Ahmed Sultan (Alexandria University, Egypt); Tamer ElBatt (Nile University, Egypt); Amr El-Sherif (Alexandria University, Egypt)
In this paper, we examine a cognitive spectrum access scheme in which secondary user (SUs) exploit the primary feedback information. We consider an overlay secondary network (SN) employing a random access scheme in which SUs access the channel by certain access probabilities that are function of the spectrum sensing metric. In setting our problem, we assume that SUs can eavesdrop on the primary link's feedback. We study the cognitive radio network from a queuing theory point of view. Access probabilities are determined by solving a secondary throughput maximization problem subject to a constraint on the primary queues' stability. First, we formulate our problem which is found to be non-convex. Yet, we solve it efficiently by exploiting the structure of the secondary throughput equation. Our scheme yields improved results in, both, the SU throughput and the primary user (PU) packet delay. In addition, it comes very close to the optimal genie-aided scheme in which SUs act upon the presumed perfect knowledge of the PU's activity.
(CORN)^2: Correlation-Based Cooperative Spectrum Sensing in Cognitive Radio Networks
Dongyue Xue (Ohio State University, USA); Eylem Ekici (The Ohio State University, USA); Mehmet Can Vuran (University of Nebraska-Lincoln, USA)
In this paper, (CORN)^2, a correlation-based, optimal sensing scheduling algorithm is developed for cognitive radio networks to minimize energy consumption. A sensing quality metric is defined as a measure of the correctness of spectral availability information. The optimal scheduling algorithm is shown to minimize the cost of sensing (e.g., energy consumption, sensing duration) while meeting the sensing quality requirements. To this end, (CORN)^2 utilizes a novel sensing deficiency virtual queue concept and exploits the correlation between spectrum measurements of a particular secondary user and its collaborating neighbors. The proposed algorithm is further proved to achieve a distributed and optimal solution under certain, easily satisfied assumptions. In addition to the theoretically proved performance guarantees, the proposed algorithm is also evaluated through simulations.

### 14:30 - 16:00

#### Game Theory

Invited papers session
Designing Incentives for Wireless Relay Networks Using Tokens
Jie Xu (University of California, Los Angeles, USA); Mihaela van der Schaar (University of California, Los Angeles (UCLA), USA)
This paper proposes a novel system design for wireless relay networks formed of self-interested users that relies on token exchanges. Our emphasis in this paper is on developing optimal designs for token systems to be deployed in relay networks. The optimal designs aim to maximize the probability that the relay transmission will be executed by transceivers whenever they are requested to provide such services. We prove that the efficiency of the relay network heavily depends on issuing the optimal amount of tokens rather than an arbitrary amount. We formulate the design problem of the token system as a bi-level optimization problem. In the inner level optimization problem, we determine the transceivers' incentive-compatible strategies (i.e. the strategies that maximize the transceivers' own utilities). We prove that these strategies exhibit a simple threshold structure. The outer level problem determines the optimal token amount, which maximizes the overall relay network efficiency. This amount of tokens needs to be neither too small nor too large and depends on the threshold that the self-interested transceivers adopt in the inner level problem.
A Game Theoretic Analysis on Incentive Mechanisms for Wireless Ad Hoc VoD Systems
Weijie Wu (Chinese University of Hong Kong, Hong Kong); John Chi Shing Lui (Chinese University of Hong Kong, Hong Kong); Richard T. B. Ma (National University of Singapore, Singapore)
Wireless ad hoc networks enable the wireless devices to directly communicate with each other. An emerging application in such systems is video-on-demand service that can greatly reduce the content server's workload by utilizing the nodes' resources. Such an application relies on the cooperation of all participating nodes. However, the nodes are selfish in nature. Therefore, a key design issue is to appropriately incentivize the cooperation among each other. In this paper, we design a simple yet effective reward based incentive mechanism so as to stimulate the nodes to upload and/or forward data to one another. By using a Stackelberg game model, we analyze the interactions between the content provider's rewarding strategy and the nodes' contributing behaviors. We derive a unique Stackelberg equilibrium and show its efficiency. By using a repeated game, we study the long term intelligent interaction between nodes and the content provider. We also design a cheating prevention mechanism and analyze its effectiveness under the repeated game setting.
Non-Cooperative Association of Mobiles to Access Points Revisited
Cengis Hasan (INRIA & INSA Lyon CITI Laboratory, France); Eitan Altman (INRIA, France); Jean-Marie Gorce (INSA-Lyon, France); Majed Haddad (Orange-Labs & France Télécom, France)
We consider in this paper games related to the association problem of mobiles to an access point. It consists of deciding to which access point to connect. We consider the choice between two access points or more, where the access decisions may depend on the number of mobiles connected to each one of the access points. We obtain new results using elementary tools in congestion and crowding games.

## Thursday, May 17

### 09:00 - 10:00

#### Keynote: User Cooperation and Conferencing Encoders for Different Classes of Multiple-Access Channels

Holger Boche
In the first part of the talk we prove two coding theorems for the compound multiple-access channel (MAC) with an arbitrary number of channel states. The channel state information at the transmitters is such that each transmitter has a finite partition of the set of states and knows which element of the partition the actual state belongs to. The receiver may have arbitrary channel state information. The first coding theorem is for the case that both transmitters have a common message and that each has an additional private message. The second coding theorem is for the case where rate-constrained, but noiseless transmitter cooperation is possible. This cooperation may be used to exchange information about channel state information as well as the messages to be transmitted. The cooperation protocol used here is Willems conferencing. We show how this models base station cooperation in modern wireless cellular networks used for interference coordination and capacity enhancement. In particular, the coding theorem for the cooperative case shows how much cooperation is necessary in order to achieve maximal capacity in the network considered. In the second part of the talk we derive the capacity region of arbitrarily varying multiple-access channels with conferencing encoders for both deterministic and random coding. We obtain a dichotomy: either the channels deterministic capacity region is zero or it equals the two-dimensional random coding region. We determine exactly when either case holds. We also discuss the benefits of conferencing. For both the compound and the arbitrarily varying cases, we give the example of a channel which does not achieve any non-zero rate pair without encoder cooperation, but the two-dimensional random coding capacity region if conferencing is possible. Unlike compound multiple-access channels, arbitrarily varying multipleaccess channels may exhibit a discontinuous increase of the capacity region when conferencing is enabled. We use the arbitrarily varying multiple-access channel with conferencing encoders for an information-theoretic analysis of the performance of wireless networks with cooperating base stations disturbed by exterior interference.

### 10:15 - 11:45

#### Relay Networks

Optimal Resource Allocation and Relay Selection in Bandwidth Exchange Based Cooperative Forwarding
Muhammad Nazmul Islam (WINLAB, Rutgers University, USA); Narayan Mandayam (WINLAB, Rutgers University, USA); Sastry Kompella (Naval Research Laboratory, USA)
In this paper, we investigate joint optimal relay selection and resource allocation under bandwidth exchange (BE) enabled incentivized cooperative forwarding in wireless networks. We consider an autonomous network where N nodes transmit data in the uplink to an access point (AP) / base station (BS). We consider the scenario where each node gets an initial amount (equal, optimal based on direct path or arbitrary) of bandwidth, and uses this bandwidth as a flexible incentive for two hop relaying. Our contribution is two-fold. First, we propose an incentivized forwarding based resource allocation algorithm which maximizes the global utility while preserving the initial utility of each cooperative node. Second, defining the link weights of each relay pair as the utility gain due to cooperation (over noncooperation), we show that the optimal relay selection in alpha -fair NUM, often a combinatorially cumbersome problem, reduces to the maximum weighted matching (MWM) in a non-bipartite graph. Numerical results show that the proposed algorithms provide 20-25% gain in spectral efficiency and 90-98% reduction in outage probability.
Energy Minimization in Cooperative Relay Networks with Sleep Mode
Yiqun Wu (Tsinghua University, P.R. China); Ness B. Shroff (The Ohio State University, USA); Zhisheng Niu (Tsinghua University, P.R. China)
In this paper, we consider the energy minimization problem in cooperative relay networks with sleep modes. The relay nodes are assumes to be able to work in either active mode or sleep mode. We formulate two different problems based on the time scales of mode transition. In the case of fast transition, the problem is shown to be a supermodular minimization problem. We develop two algorithms: a local greedy search algorithm as well as an efficient relaxation based algorithm, which provides a provable performance bound. In the case of slow transition, the problem is shown to be NP-hard even for the single relay selection case. Approximation algorithms are proposed based on the supermodular structure of the problem. Simulation results show that the proposed algorithms perform close to optimal, and significant energy savings can be achieved. The comparison between fast transition and slow transition is also presented.
Half-Duplex Decode-Partial-Forward
Mohammad Shaqfeh (Texas A&M University at Qatar, Qatar); Hussein Alnuweiri (Texas A&M University, Qatar)
We propose a new transmission scheme, which we call Decode-Partial-Forward (DPF), for orthogonal half-duplex relay channels. We demonstrate that the DPF scheme achieves significantly higher rates than the conventional DF scheme that is based on repetition coding and it performs close to the capacity bounds of DF relaying. In DPF, the source superimposes two separate codewords and the relay decodes both codewords but it regenerates (forwards) "the more difficult to decode" codeword only. The destination node applies successive interference cancellation in order to decode the two codewords based on the received signals in both time slots. We provide a closed-form solution to find the optimal power and rate allocation for the two superimposed codewords in order to maximize the sum achievable rate. The DPF scheme provides a simple and practical alternative to the advanced cooperative coding techniques.
Performance Modelling of Opportunistic Forwarding with Imprecise Knowledge
Chiara Boldrini (IIT-CNR, Italy); Marco Conti (IIT-CNR, Italy); Andrea Passarella (IIT-CNR, Italy)
In this work we present a framework for modeling the performance of single-copy forwarding protocols for opportunistic networks. The framework has the following characteristics: (i) it provides a closed form solution for a large class of probability distributions representing inter-meeting times, (ii) it is able to model both randomized and utility-based forwarding protocols, and (iii) it accounts for errors in the estimations of the utility values used by utility-based schemes for making forwarding decisions. Using this framework, we show how it is possible to identify the most effective forwarding policies depending on the amount of estimation errors in the utility value.

### 12:45 - 14:15

#### Routing

Minimum-energy Packet Forwarding Over Lossy Networks Under Deadline and Reliability Constraints
Zhenhua Zou (KTH-Royal Institute of Technology, Sweden); Mikael Johansson (Royal Institute of Technology, Sweden)
This paper studies the minimum-energy packet forwarding under deadline and reliability constraints over multi-hop and lossy wireless networks. We assume a routing topology in the form of a directed graph with a finite-state Markov chain link loss model, and formulate the minimum energy problem as a finite-horizon constrained Markov decision process. We show that the minimum energy problem can be solved by maximizing a weighted sum of reliability and energy, and that the optimal forwarding policy is a randomized policy over two history-independent and deterministic policies. Numerical examples show that the transmission energy cost of achieving reliabilities close to the maximum can be significant when links are bursty. In addition, transmission power adjustments can further reduce energy cost. Lastly, we develop simple heuristic policies with a good balance between energy and reliability.
Keqin Liu (University of California, Davis, USA); Qing Zhao (University of California at Davis, USA)
We consider the adaptive shortest-path routing problem in wireless networks under unknown and stochastically varying link states. In this problem, we aim to optimize the quality of communication between a source and a destination through adaptive path selection. Due to the randomness and uncertainties in the network dynamics, the quality of each link varies over time according to a stochastic process with unknown distributions. After a path is selected for communication, the aggregated quality of all links on this path (e.g., total path delay) is observed. The quality of each individual link is not observable. We formulate this problem as a multi-armed bandit with dependent arms. We show that by exploiting arm dependencies, a regret polynomial with network size can be achieved while maintaining the optimal logarithmic order with time. This is in sharp contrast with the exponential regret order with network size offered by a direct application of the classic MAB policies that ignore arm dependencies. Furthermore, our results are obtained under a general model of link-quality distributions (including heavy-tailed distributions) and find applications in cognitive radio and ad hoc networks with unknown and dynamic communication environments.
Dynamic Shortest Path Algorithms for Hypergraphs
Jianhang Gao (University of California, Davis, USA); Qing Zhao (University of California at Davis, USA); Wei Ren (Microsoft Corporation, USA); Ananthram Swami (Army Research Lab., USA); Ram Ramanathan (BBN Technologies, USA); Amotz Bar-Noy (Brooklyn College & Graduate Center, CUNY, New York, USA)
hypergraph is a set V of vertices and a set of non-empty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph.
Relay Selection with Channel Probing for Geographical Forwarding in WSNs
Kolar Purushothama Naveen (Indian Institute of Science, India); Anurag Kumar (Indian Institute of Science, India)
In a large wireless sensor network (WSN) with sleep-wake cycling nodes, we are interested in the local decision problem faced by a node that has "custody" of a packet and has to choose one among a set of next-hop relay nodes. Each of the relays is associated with a "reward" that summarizes the cost/benefit of forwarding the packet through that relay. We seek a locally optimal solution to this problem, the idea being that such a solution, if adopted by every node, could provide a reasonable local heuristic for the end-to-end forwarding problem. Towards this end, we propose a local forwarding problem where the relays wake-up at random times, at which instants they reveal the probability distributions of their rewards. To determine a relay's exact reward, the source has to further probe the relay, incurring a probing cost. Thus, at each relay wake-up instant, the source, given a set of relay reward distributions, has to decide whether to stop (and forward the packet to an already probed relay), continue waiting for further relays to wake-up, or probe an unprobed relay. We formulate this local forwarding problem as a Markov decision process (MDP) and obtain some interesting structural results on the optimal policy. Our problem can be considered as a new variant of the optimal stopping problem.

### 14:30 - 16:00

#### Scheduling

On the Need for Coordination Among Base Stations in a Heterogeneous Network