May 23, 2018

Workshop on Mathematical Modeling and Analysis of Wireless Networks,
May 8-9, 2008



Sem Borst, Alcatel-Lucent Bell Labs & Eindhoven Univ. of Techology
Some Distributed Resource Sharing and Scheduling Problems in Wireless Networks

We present preliminary results for three loosely related problems in wireless resource sharing and distributed scheduling.
First, we consider a wireless multi-hop network operating under a CSMA/CA protocol, where we explicitly track the flow of individual packets along their end-to-end path. We analyze the joint distribution of the number of packets pending for transmission at the various nodes. The results show that the end-to-end throughput may be non-monotone as function of the ingestion rate of packets. Second, we examine the problem of distributed scheduling in a system with channel variations. We discuss a scheme for determining the optimal transmission thresholds in an adaptive and distributed fashion. Thirdly, we investigate the performance of various MaxWeight type
scheduling strategies in a system with channel variations and session-level dynamics. We show that the usual queue-based algorithms no longer ensure maximum throughput, and explore the scope for alternative strategies that do achieve stability whenever possible.

Based on joint work with Dee Denteneer, Yahya Al-Harthi, Seva Shneer and Peter van de Ven.

Short Bio:
Sem Borst received the MSc degree in applied mathematics from the University of Twente, The Netherlands, in 1990, and the PhD degree from the University of Tilburg, The Netherlands, in 1994. During the fall of 1994, he was a visiting scholar at the Statistical Laboratory of the University of Cambridge, England. In 1995, he joined the Mathematics of Networks and Systems department of Bell Laboratories in Murray Hill, USA. He also holds a part-time position as a professor of Stochastic Operations Research at Eindhoven University of Technology.
Sem Borst is a member of IFIP Working Group 7.3, and serves or has served as a member of several program committees and editorial boards. His main research interests are in the area of performance evaluation and resource allocation algorithms for communication networks.

Ed Knightly, Rice University
Modeling and Experimental Validation of Congestion Control and Medium Access in Multi-Hop Wireless Networks

Multi-hop wireless networks seek to provide low-cost high-performance wireless access over large coverage areas. Unfortunately, we will show that cross-layer interactions of congestion control and carrier sense multiple access yield starvation of multi-hop flows when competing with single-hop flows, even with only two competing flows. We will use a combination of analytical modeling and experiments on a deployed urban mesh network to understand the origins of starvation, to study the reasons for failure of prior solutions, and to explore new directions in protocol design.

Short Bio:
Edward Knightly is a professor of Electrical and Computer Engineering at Rice University. He received the B.S. degree from Auburn University in 1991 and the M.S. and Ph.D. degrees from the University of California at Berkeley in 1992 and 1996 respectively. He served as associate editor of numerous journals and special issues including IEEE/ACM Transactions on Networking and IEEE Journal on Selected Areas of Communications Special Issue on Multi-Hop Wireless Mesh Networks. He served as technical co-chair of IEEE INFOCOM 2005, general chair of ACM MobiSys 2007, and served on the program committee for numerous networking conferences including ICNP, INFOCOM, MobiCom, and SIGMETRICS. He received the National Science Foundation CAREER Award in 1997 and is a Sloan Fellow since 2001. His research interests are in the areas of mobile and wireless networks and high-performance and denial-of-service resilient protocol design.

Vikram Krishnamurthy, University of British Columbia
Global Games and Correlated Equilibria for Decentralized Spectrum Access

This talk illustrates two methodologies for decentralized spectrum access in cognitive radio systems.
In the first approach, given a large number of secondary users that can access a spectrum hole, we illustrate how a global games approach
can lead to a simple characterization of the Nash equilibrium. We formulate Bayes-Nash equilibrium conditions
for which a simple threshold strategy is competitively optimal for each secondary user, and propose a scheme for
decentralized threshold computation. We show that there is a remarkable phase transition in the behavior as the variance of the estimate reduces.
In the second methodology, we illustrate how secondary users can deploy regret based stochastic approximation algorithms for learning the correlated equilibrium. For the case of agile primary users, the asymptotic analysis of the algorithm results in a switched differential inclusion.

Short Bio:
Vikram Krishnamurthy is a professor and Canada Research Chair at the Department of Electrical Engineering, University of British Columbia, Vancouver, Canada.Prior to 2002, he was a chaired professor at the Department of Electrical and Electronic Engineering, University of Melbourne, Australia. His current research interests include statistical signal processing,computational game theory, and stochastic dynamical systems. Much of his recent work focuses on applications of these methods in wireless communications, sensor networks and biomolecular simulation.

Armand Makowski, University of Maryland
Intersecting Random Graphs

Given two graphs $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ with same vertex set $V$, we define their intersection as the graph $(V,E)$ with vertex set $V$ and edge set $E = E_1 \cap E_2$. In this talk we consider the situation where each of the component graphs is itself a random graph, e.g.,a Bernoulli random graph, a geometric random graph or a random key graph. The resulting random graphs occur naturally as simple models for a number of issues in wireless networking.

We are interested in understanding how the structural properties of the component random graphs shape those of the random graph obtained by intersection. Particular attention will be given to the existence of zero-one laws for the properties of graph connectivity and the absence of isolated nodes, and to the form of the associated critical scalings.

Short Bio:
Armand M. Makowski received the Licence en Sciences Mathematiques from the Universite Libre de Bruxelles in 1975, the M.S. degree in Engineering-Systems Science from U.C.L.A. in 1976 and the Ph.D. degree in Applied Mathematics from the University of Kentucky in 1981. In August 1981, he joined the faculty of the Electrical Engineering Department at the University of Maryland College Park, where he is now Professor of Electrical and Computer Engineering. He has held a joint appointment with the Institute for Systems Research since its establishment in 1985.

Armand Makowski was a C.R.B. Fellow of the Belgian-American Educational Foundation (BAEF) for the academic year 1975-76; he is also a 1984 recipient of the NSF Presidential Young Investigator Award and became an IEEE Fellow in 2006.

His research interests lie in applying advanced methods from the theory of stochastic processes to the modeling, design and performance evaluation of engineering systems, with particular emphasis on communication systems and networks.

Laurent Massoulie, Thomson Research
Content Popularity and User Profiling for Content Placement in Peer-to-Peer VoD Systems

In this talk we consider the problem of pre-loading video content at users of a peer-to-peer system, so as to meet content demands with minimal access to infrastructure servers. We propose to leverage content popularity distribution as well as user profiling to obtain maximal benefits. We will discuss optimisation formulations, and resulting replication strategies that exploit expected demand and its volatility. We will also discuss ongoing work on user profiling, in which we advocate the use of particular spectral clustering techniques to identify profiles of users. Corresponding theoretical guarantees as well as empirical validation on the NetFlix dataset will be presented.
Based on joint work with Peter Marbach and Dan-Cristian Tomozei

Short Bio:
Laurent Massoulié graduated from Ecole Polytechnique in 1991, and received a PhD in Automatic Control from Université Paris Sud in 1995. >From 1995 to 1998 he worked in France Télécom R&D on traffic control of ATM and IP networks. From 1999 to 2006 he was with Microsoft Research Cambridge. There he worked on congestion control, overlay management, and peer-to-peer applications over the Internet. Since 2006 he is a senior researcher in Thomson Corporate Research, where he is involved in the design of peer-to-peer applications for multimedia content distribution. He is the recipient of several best paper awards (IEEE Infocom 1999, ACM Sigmetrics 2005, and ACM Conext 2007).

Mike Neely, University of Southern California
Dynamic Data Compression for Wireless Transmission over a Fading Channel

We consider a wireless node that randomly receives data from different sensor units. The arriving data must be compressed, stored, and transmitted over a wireless link, where both the compression and transmission operations consume power. Specifically, the controller must choose from one of multiple compression options every timeslot. Each option requires a different amount of power and has different compression ratio properties. Further, the wireless link has potentially timevarying channels, and transmission rates depend on current channel states and transmission power allocations. We design a dynamic algorithm for joint compression and transmission, and prove that it comes arbitrarily close to minimizing average power expenditure, with an explicit tradeoff in average delay. The algorithm is simple to implement and does not require knowledge of probability distributions for packet arrivals or channel states.

Short Bio:
Michael J. Neely received B.S. degrees in both Electrical Engineering and Mathematics from the University of Maryland, College Park, in 1997. He then received a 3 year Department of Defense NDSEG Fellowship for graduate study at the Massachusetts Institute of Technology, where he received an M.S. degree in EECS in 1999 and a Ph.D. in 2003. During the Summer of 2002, he worked as an intern in the Distributed Sensor Networks group at Draper Labs in Cambridge. He is currently an Assistant Professor in the Communication Sciences Institute (CSI), within the Electrical Engineering Department at the University of Southern California. His research interests are in the areas of stochastic network optimization and queueing theory, with applications to wireless, satellite, mobile ad-hoc networks, and switching systems. Michael is a member of Tau Beta Pi and Phi Beta Kappa.

Alexandre Proutiere, Microsoft Research
Scheduling Mobile Users in Wireless Systems

In this talk, we present new results for the design and the performance evaluation of centralized and distributed scheduling schemes in wireless networks where users / nodes may move. We first explore the case of networks without user mobility, and briefly recall existing results on their performance. We also give a new and provably accurate characterization of the throughput region of random distributed schemes, such as Aloha or CSMA. We then focus on systems where users move, and quantify the impact of this mobility on the performance of scheduling schemes. We finally explain how to design scheduling algorithms that are able to exploit mobility.

Short Bio:
Alexandre Proutiere is a researcher in the Systems and Networking group at Microsoft Research, Cambridge, Great Britain. His research interests are in the design and the performance evaluation of computer networks, with a specific interest in resource allocation and control in wireless systems. Before joining Microsoft in June 2007, he was a senior expert researcher at France Telecom R&D and an assistant professor in the computer science department of Ecole Normale Superieure (Paris). He received a PhD in mathematics from Ecole Polytechnique (Palaiseau, France) in 2003, graduated in mathematics from Ecole Normale Superieure (Paris), and qualified as an engineer at Ecole Nationale Superieure des Telecommunications (Paris). He is with Thomas Bonald the recipient of the best paper award of ACM Sigmetrics /Performance 2004.

Devavrat Shah, Massachusetts Institute of Technology
On capacity scaling in arbitrary wireless networks

Information theoretic characterization of exact capacity region for any reasonable network model remains a non-trivial question of interest
for information theorists. The notion of scaling of capacity, starting with work by Gupta and Kumar (2000), has given some traction on this question and therefore resulted in a sequence of interesting results over the past decade. The main limitation of this approach has been two folds: (a) regular network structure and (b) regular traffic requirement.

In this talk, I will try to get away from these two restrictions to get closer to the scaling of the whole capacity region for abritrary networks. Specifically, we will consider network where nodes are placed arbitrarily in an extended network (with minimum distance constraint) and traffic requirements are arbitrary. Under standard (additive i.i.d. Gaussian noise and random fading) channel model, we will separate our presentation for qualitatively two different regimes of power attenuation parameter : between (2, 3) and larger than 3. For both of these cases, we will discuss when we can characterize the exact capacity scaling and schemes achieving them. We will also discuss the questions that remain open and the technical difficulties that we are facing to complete the "scaling program".

This is based on joint works with (a) R. Madan and O. Leveque; (b) U. Niesen and P. Gupta.

Short Bio:
Devavrat Shah is currently an assistant professor with EECS, MIT since Fall 2005. He is a member of the Laboratory of Information and Decision Systems (LIDS). He is also a member of the Operations Research Center (ORC). He received his BTech degree in Computer Science & Engg. from IIT-Bombay in 1999 with the honor of the President of India Gold Medal.

He received his Ph.D. from the Computer Science department, Stanford University in October 2004. He was a post-doc in the Statistics department at Stanford in 2004-05.

He was co-awarded the IEEE INFOCOM best paper award in 2004 and ACM SIGMETRIC/Performance best paper awarded in 2006. He received 2005 George B. Dantzig best disseration award from the INFORMS. He received NSF CAREER award in 2006. His research interests include network algorithms, stochastic networks, network information theory and statistical inference.

Ness Shroff, Ohio State University
Optimizing Energy Efficiency for Sleep-Wake Enabled Sensor Networks Using "Anycasting"

In wireless sensor networks, a significant fraction of the total energy consumed is due to the wireless radio. Thus, sending nodes to sleep results in substantial energy savings. Thus a large number of papers that have been devoted to the development of efficient sleep-wake scheduling mechanisms. However, sending the radio to sleep could also result in excessive delays, which need to be carefully controlled. To that end, there has been a recent development to reduce the delay with minimal, if any, additional cost by exploiting the wireless broadcast medium. This technique is called "anycasting" and is especially useful for asynchronous wireless sensor networks. Unlike traditional sleep-wake scheduling mechanisms, in anycasting, the sending nodes transmits to the first node that awakes in its forwarding set, which results in significant reduction on the end-to-end delay. However, the critical challenges with anycasting are in selecting the forwarding set without an a priori hierarchical structure imposed in the network, and avoiding looping, without resorting to expensive global cooperation mechanisms.

The anycasting problem can be formulated as an optimization problem, e.g., maximizing the network lifetime subject to delay constraints. However, the problem is inherently non-linear and non-convex and requires the use of non-traditional tools to solve it. In this talk, I will describe how we have solved the anycasting problem which is a joint control problem of how to optimally choose the forwarding sets, the priorities assigned to the nodes in case more than one node in a forwarding set is awake, and the rates at which nodes wake up. I will also describe an optimal anycast algorithm that minimizes the end-to-end delay of all the nodes simultaneously, (or alternatively maximizes the network lifetime for a given delay), is fully distributed, and does not require complex computations.
This is joint work with Joohwan Kim, Xiaojun Lin, and Prasun Sinha

Short Bio:
Ness B. Shroff received his Ph.D. degree from Columbia University, NY in 1994. He joined Purdue University in November 1994, where he is currently Professor of Electrical and Computer Engineering and director of CWSA, a university-wide center on wireless systems and applications.

His research interests span the areas of wireless and wireline communication networks. He is especially interested in fundamental problems in the design, performance, pricing, and security of these networks. His research is funded by various companies such as Intel, Hewlett Packard, Nortel, AT&T, BAE systems, and L. G. Electronics; and government agencies such as the National Science Foundation (NSF), Defense Advanced Research Projects Agency (DARPA), Indiana Dept. of Transportation, and the Indiana 21st Century fund.

Dr. Shroff is an editor for IEEE/ACM Trans. on Networking and the Computer Networks Journal, and past editor of IEEE Communications Letters. He has served on the technical and executive committees of several major conferences and workshops. He was the technical program co-chair of IEEE INFOCOM'03, the premier conference in communication networking. He was also the conference chair of the 14th Annual IEEE Computer Communications Workshop (CCW'99), the program co-chair for the symposium on high-speed networks, Globecom 2001, and the panel co-chair for ACM Mobicom'02. Dr. Shroff was also a co-organizer of the NSF workshop on Fundamental Research in Networking, held in Arlie House Virginia, in 2003.

He received the IEEE INFOCOM 2006 best paper award, the IEEE IWQoS 2006 best student paper award, the 2005 best paper of the year award for the Journal of Commnications and Networking, the 2003 best paper of the year award for Computer Networks, and the NSF CAREER award in 1996 (his INFOCOM 2005 paper was also selected as one of two runner-up papers for the best paper award).

Patrick Thiran, EPFL Lausanne
Fairness, Spatial Reuse and Phase Transition in 802.11 Networks

IEEE 802.11 is probably the most widely used Medium Access Control protocol in current wireless networks. In the single-hop setting (wireless LAN), its performance is quite well understood. In the multi-hop setting however, there is, to date, no widely accepted model that captures rigorously all the essential features of the protocol while staying simple enough to provide insight. Consequently, when confronted with experimental results, people often find it hard to interpret them.

We use a continuous-time Markovian loss network to model protocols ``à la 802.11'' in the context of multi-hop ad hoc networks. It enables us to explore systematically the trade-off between spatial reuse and fairness, which is inherent to these decentralized CSMA/CA MAC protocols. We show in particular that the widely observed unfairness of the protocol in small network topologies does not always persist in large topologies. In large 1-dim. networks, nodes sufficiently far away from the border of the network have equal access to the channel. In 2-dim. networks, we observe a phase transition, linked to the existence of multiple Gibbs measures in the Markov Random Field model. If the access intensity of the protocol is small, border effects remain local and the protocol is long term fair as in 1-dim. networks. However, for a large enough access intensity, the border effects persist independently of the size of the network and the protocol is strongly unfair.

This is joint work with Mathilde Durvy and Olivier Dousse.

Short Bio:
Patrick Thiran is an associate professor at EPFL. He received the electrical engineering degree from the Université Catholique de Louvain, Louvain-la-Neuve, Belgium, in 1989, the M.S. degree in electrical engineering from the University of California at Berkeley, USA, in 1990, and the PhD degree from EPFL, in 1996. He became an adjunct professor in 1998, an assistant professor in 2002 and an associate professor in 2006. From 2000 to 2001, he was with Sprint Advanced Technology Labs, Burlingame, CA. His research interests include communication networks, performance analysis, dynamical systems and stochastic models. He is currently active in the analysis and design of wireless multi-hop networks and in network monitoring. He served as an associate editor for the IEEE Transactions on Circuits and Systems in 1997-99, and he is currently an associate editor for the IEEE/ACM Transactions on Networking. He was the recipient of the 1996 EPFL Ph.D. award.

Jean Walrand, University of California, Berkeley
A Distributed Algorithm for Optimal Throughput and Fairness in Wireless Networks with a General Interference Model

In multi-hop wireless networks, earlier research on joint scheduling and congestion control has suggested that MAC-layer scheduling is the bottleneck. Distributed scheduling for maximal throughput is difficult since the conflicting relationship between different links is complex. Existing works on maximal-throughput scheduling usually assumes synchronized time slots, and in each slot, a maximal-weighted ``independent set'' needs to be found or approximated. However, this is hard to implement in distributed networks. On the other hand, a distributed greedy protocol similar to IEEE 802.11 can only achieve a fraction of the throughput region. In this paper, we introduce an adaptive CSMA algorithm, which can achieve the maximal throughput distributedly under some assumptions. The intuitive idea is that each link should adjust its aggressiveness of transmission based on its backlog. Furthermore, we combine the algorithm with end-to-end flow control to achieve fairness among competing flows. The effectiveness of the algorithm is verified by simulations.

This is joint work with Libin Jiang.

Short Bio:
Jean Walrand has been a professor in the Department of Electrical Engineering and Computer Science at U.C. Berkeley since 1982. His research interests include stochastic processes, queuing theory, communication networks, control systems and applied game theory. He has published three books. He is a fellow of the IEEE.

Edmund Yeh, Yale University
Information Dissemination in Mobile Wireless Networks

In wireless networks, node mobility may be exploited to assist in information dissemination over time. We analyze the latency for
information dissemination in large-scale mobile wireless networksTo study this problem, we map a network of mobile nodes to a network
of stationary nodes with dynamic links. We then use results from percolation theory to show that under a constrained i.i.d. mobility
model, the scaling behavior of the latency falls into two regimes. When the network is not percolated (subcritical), the latency scales
linearly with the initial Euclidean distance between the sender and the receiver; when the network is percolated (supercritical), the
latency scales sub-linearly with the distance.
Joint work with Zhenning Kong, Yale University

Short Bio:
Edmund Yeh received his Bachelor of Science in Electrical Engineering with Distinction from Stanford University in 1994. In the same year, he was awarded one of ten Winston Churchill Scholarships for overseas study in science and engineering at Churchill College, University of Cambridge, in the United Kingdom. He received his Master of Philosophy in Electrical Engineering from the University of Cambridge in 1995. As a doctoral student, he studied under Professor Robert G. Gallager at the Laboratory for Information and Decision Systems at the Massachusetts Institute of Technology. He received his Ph.D. in Electrical Engineering and Computer Science from MIT in 2001. Since July 2001, he has been on the faculty at Yale University, New Haven, Connecticut, where he is currently an Associate Professor of Electrical Engineering (with joint appointments in the Departments of Computer Science and Statistics). During the summer of 2004, Dr. Yeh was an Invited Professor at the Information Theory Laboratory of the Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland. In fall 2004, Dr. Yeh was a visitor at MIT, Princeton University, and University of California at Berkeley.

Dr. Yeh is a recipient of the U.S. Army Research Office (ARO) Young Investigator Program (YIP) Award. He is a member of the Technical Program Committees for IEEE Infocom (2005-2007), IEEE Globecom (2004), and WiOpt (2006-2008). As a graduate student, he received the National Science Foundation and Office of Naval Research Fellowships for graduate study. As an undergraduate student, he received the Frederick E. Terman Award in 1994, the Barry M. Goldwater Scholarship from the United States Congress in 1993, and the Stanford President's Award for Academic Excellence in 1991. He is a member of Phi Beta Kappa, Tau Beta Pi, and IEEE. He has spent a number of summers working at industrial labs, including the Mathematical Sciences Research Center at Bell Laboratories, Lucent Technologies (1998-1999), the Signal Processing Research Department at AT&T Bell Laboratories (1993-1994), and the Space and Communications Group at Hughes Electronics Corporation (1991-1992).

Dr. Yeh's research interests are in the fields of information theory, communication theory, queueing theory, wireless systems, and data networks.