Tutorial

• Network Coding and its Impact on Wireless System Design
  Instructors: Suman Banerjee, University of Wisconsin, Madison, WI, USA; and Sudipta Sengupta, Microsoft Research, Redmond, WA, USA

  +++ more details +++
  Abstract

  Network coding is a relatively new area of information theory, originating from the seminal work of Ahlswede et al. (2000) which showed that the maximum capacity of multicast can be achieved by mixing packets (through linear combinations over finite fields) in transit network nodes (this cannot be achieved, in general, by routing). Much of the existing literature on network coding has focused on multicast scenarios in wired networks.

  Over the last couple of years, network coding has found new applications in wireless networks as a technique for improving throughput or increasing resiliency in high packet loss environments, for both unicast and multicast traffic. These schemes exploit the broadcast nature of the wireless medium and employ different packet mixing techniques. Network coding has also been applied to the wireless physical layer by mixing and reconstruction of analog signals in the face of wireless interference. It has also been used, quite interestingly, to improve throughput in large-scale wireless sensor networks comprising of low-cost off-the-shelf radios. Recently, a number of commercial vendors of software and hardware have taken note of the new opportunities provided by network coding and are keen to utilize them in their systems.

  Given that network coding is a new, somewhat radical, primitive available as a building block for wireless systems, it has natural interactions with all layers of the protocol stack of any system. The key question this tutorial tries to raise is --- How should network coding as a primitive be considered by all layers of a wireless protocol stack in the design of single-hop and multi-hop communication systems? For instance, what is the impact of using “analog network coding” at the PHY layer, on the MAC layer; what is the impact of using local network coding at the MAC layer on routing decisions; and how should a transport protocol react to the availability of network coding primitives at the MAC and routing layers.

  The goal of this tutorial is to provide a quick introduction on the impact of network coding in the design of single-hop and multi-hop wireless networking systems.

  The tutorial will be structured as follows. In the first part of the tutorial, we will introduce network coding and survey some theoretical basic results. In the second part, we will examine the feasibility of some of these techniques in practical design of single-hop and multi-hop wireless communication systems. More specifically, we will examine the design choices and interactions of network coding with each layer of the protocol stack, ranging from the physical layer to the application layer. At the physical layer, we will study possible designs of analog network coding techniques. At the MAC layer, we will study practical design constraints and the implications of “local” network coding techniques. At the network layer, we will study how routing decisions should be affected if network coding primitives were to be applied. We will compare and contrast local and global network coding strategies. At the transport layer, we will study the impact of network coding related losses on performance of end-to-end protocols, such as TCP. Finally, at the application layer, we will study the impact of building applications, such as P2P file sharing in a multi-hop wireless network, that are cognizant of network coding primitives, both at the lower layers and at this layer. We will conclude with a range of open questions in this domain of work.

  Our discussion of wireless networks will draw upon experiences by us and others in the design of WLANs, wireless mesh networks, as well as sensor networks. We will aim to balance theory and system perspectives in this tutorial, and discuss which of these techniques can be readily implemented in today’s off-the-shelf hardware, and which would require specific changes in future design of such systems.

  Intended Audience

  The tutorial will assume basic understanding of networking principles and familiarity with the layered architecture of networking protocol stacks. No background in network coding will be assumed. In particular, we believe that the tutorial will be quite beneficial to:

  1. Graduate students and researchers in the area of networking and communications (especially wireless), who want to explore further research opportunities in this topic.
  2. Practicing networking professionals in the telecommunications and networking industry, especially those who would be interested in utilizing this new primitive in the design of future wireless networking products.
• Randomized Scheduling in Wireless Multihop Networks
  Instructors: Peter Marbach, University of Toronto; and Devavrat Shah, Massachusetts Institute of Technology

  +++ more details +++
  Abstract

  A fundamental problem in wireless multihop networks is how to schedule packet transmissions at the individual nodes. What makes this problem more challenging compared with wireline networks is the interference of packet transmissions at different nodes. The design of a simple and distributed aka message-passing packet scheduling mechanism in wireless multihop networks is one of the important open issues in wireless networks. There has been notable progress over the last couple of years in understanding distributed packet scheduling mechanism for wireless networks. The goal of this tutorial is to provide an overview of the current state-of-art in distributed scheduling by presenting the main models and key results in this area. The tutorial is aimed both at researchers who are interested in an overview of currently proposed mechanisms and possible research directions in this area, as well as practitioners who are interested in overview of the potential and limitations of proposed distributed scheduling mechanisms.

  The tutorial will focus on two approaches to distributed scheduling in wireless networks: (a) mechanisms based on random access protocols and (b) mechanisms based on maximum weight matching scheduler. The first approach aims at extending the well-known CSMA/CD mechanism to multihop wireless networks. While several such approaches have been proposed in the literature, only recently a formal framework for studying and characterizing the performance of such schemes for multi-hop networks has emerged. The tutorial will discuss mathematical models that have been proposed, as well as approaches on how to implement such schemes in a practical setting. The second main approach that we present focuses on distributed mechanisms that can implement the maximum-weight policies that has been proposed in the seminal work of Tassiulas and Ephremides. The tutorial will provide message-passing implementation of the maximum-weight policies building on ideas from statistical physics and artificial intelligence (aka Belief propagation). The performance of algorithm and detailed implementation cost will be discussed as well. Overall, the tutorial will provide the spectrum of algorithm, starting with simplest random access algorithm at one end and the more involved (queue-based) message-passing algorithm at the other.

  The proposed tutorial is a full-day tutorial. It will contain 6 segments where each segment will take about 60 mins. The broad division of the tutorial is as follows. (detailed outline is skipped here, but we are happy to provide it if required; please feel free to contact us).

  Biographies

  Peter Marbach was born in Lucerne, Switzerland. He received the Eidg. Dipl. El.-Ing. (1993) from the ETH Zurich, Switzerland, the M.S. (1994) in electrical engineering from the Columbia University, NY, U.S.A, and the Ph.D. (1998) in electrical engineering from the Massachusetts Institute of Technology (MIT), Cambridge, Massachusetts, U.S.A. He was appointed as assistant professor in 2000, and associate professor in 2005, at the Department of Computer Science of the University of Toronto. He has also been post-doctoral fellow at Cambridge University, UK, and a visiting professor at Microsoft Research, Cambrigde, UK, at the Ecole Polytechnique Federal at Lausanne (EPFL), Switzerland, and at the Ecole Normale Superieure, Paris, France.

  Peter Marbach has received the IEEE INFOCOM 2002 Best Paper Award for his paper "Priority Service and Max-Min Fairness". He is on the editorial board of the ACM/IEEE Transactions of Networking. His research interests are in the fields of communication networks, in particulare in the area of wireless networks, Peer-to-Peer Networks, and Social Networking applications.

  Devavrat Shah is currently an assistant professor with the department of electrical engineering and computer science, MIT. 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 also spent time at MSRI, Berkeley while he was a post-doc.

  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 are in the network algorithms, stochastic analysis of networks and large scale statistical inference.
• Smart Computing Environments: Challenges, Solutions and Future Directions
  Instructor: Prof. Sajal K. Das, The University of Texas at Arlington

  +++ more details +++
  Abstract

  This tutorial is about smart and pervasive erwironrnents that link computers to everyday settings and commonplace tasks in a self-organized, self-managing and self-healing manner. The desire to create smart environments has existed for decades. However, recent advances in such areas as mobile and pervasive computing, wireless and sensor networks, data mining and learning, autonomic networking, and middleware technologies are making this dream a reality.

  A definion of "smart" or "inteIIigent" is "the ability to acquire and apply knowledge," while the environment refers to our surroundings. We therefore define a smart orwironmont as one that is able to autonomously acquire and apply knowIedge about an environment and its inhabitants in order to improve their experience in that environment without explicit awareness. Moreover, such networlced environment must be able to support autonomic (i.e., self-*) services with minimal human intervention.

  The type of experience that individuals wish from smart and pervasave environrnents varies with the individual and the type of environment. These include safety and security, of its inhabitants, reduction in the operational and management cost of the environment intelligent task automation, performance optimization, context-aware resource provisioning, and automatic fault recovery.

  The objectn of this inter-disciplinary tutorial is to present state-of-the-art topics in the design, development, modeling and applications of smart environments. The topics include cutting-edge enabling technologies in smart devices, wireless and sensor networks, mobile and pervasive computing, middleware and software agents that are essential in building smart and autonomic spaces. We will describe novel architectures, algorithms, and protocols for agent based smart home design, learning and prediction of context patrns (location, activity, etc.), data mining and episode discovery, intelligent decision making, automation and control, and context-aware resource management. Successful projects on smart erwiroriments realized ri a vanoty of settings along with innovative applications (e.g. smart health care and security) will also be described.

  Abstract

  This tutorial is intencd for students, educators, researchers, engineers, and professionals interested in the fields of computer science and engineering, integrated systems design, pervasive and smart environments. The tutorial material will be based on the book Smart Environments: Technology, Protocols and Applications, coauthored by D. J. Cook and S. K. Das (John Wiley, 2006), and augmented by recent research and development in this emerging field.
• Data Communication and Coordination in Wireless Sensor and Sensor-actuator Networks
  
  Instructor: Ivan Stojmenovic, University of Birmingham, UK
  Abstract

  Wireless sensor and sensor-actuator networks are expected to operate autonomously in unattended environments. They can be remotely connected to the user via one or more base stations (sinks) with direct access to a fixed infrastructure (such as the Internet). Stationary actuators may control sensors by deciding about their activity status (for example, wake up more sensors in areas with anticipated movement or higher reported temperatures) and act upon the environment (for example, by activating its own light/sound alarming or by activating their own water sprinklers). Mobile actuators (which might be co-exist with stationary ones) are robot like devices that can perform additional actions such as (re)placing sensors at needed locations.

  While wireless sensor networks attracted enormous research interest, the research of sensor actuator networks is in the initial phases and fundamental network coordination and data communication protocols need to be designed to provide basic functionality to these networks. Examples of problems to be solved are sensor placement by actuators to improve sensing area coverage, minimum energy broadcasting and routing involving actuators, controlled actuator mobility for realization of fault tolerant network, sensor actuator and actuator-actuator coordination, anycasting (reporting from sensor to the nearest actuator), and actuator movement and coordination to provide accurate localization to sensors.

  A tentative outline for the tutorial content is as follows:

  • Existing models for sensor and actuator networks, including existing interpretation of what actuators are, whether or not sensors and actuators are mobile, whether or not communication is multihop.
  • Algorithms for deploying sensors by robots, coordinated movement and task execution of swarm of miniature robots, robot dispersion, load balancing and task assignment, and actuator and sensor network generation.
  • Data communication and coordination algorithms for routing, anycasting, multicasting, data gathering, actuator-actuator coordination, backbone, sensor area coverage, relocation, broadcasting.

  The main paradigm shift is to apply localized (or greedy) schemes as opposed to existing protocols requiring global information. Localized algorithms are distributed algorithms where simple local node behavior achieves a desired global objective.

  Localized protocols provide scalable solutions, that is, solutions for wireless networks with an arbitrary number of nodes. It is recognized that scalability and functionality for sensor networks operations is only possible with the position information, which becomes available with increasing number of affordable software and hardware solutions. For some other tasks, e.g. broadcasting, position information helps but scalable solutions without it are also possible.

  The main objective of the tutorial is to present state of the art research results on data communication and coordination in wireless sensor and sensor-actuator networks, with emphasizes on localized and position based techniques. Physical layer impact on the design of network layer protocols is also discussed. Most of presented techniques are based on localized geometric and graph structures.
• Modeling and Mitigating Interference in Multi-Hop Wireless Networks
  
  Instructors: Douglas M. Blough, Georgia Institute of Technology; Samir R. Das, Stony Brook University; and Paolo Santi, IIT-CNR

  +++ more details +++
  Abstract

  Given the vast literature on this important research topic, we envision a full-day tutorial organization. Broadly speaking, the tutorial will be composed of four parts: 1) Interference models, 2) Measuring Interference, 3) Dealing with Interference, and 4) Interference-Aware Algorithms. Furthermore, we envision short initial and ending sections, where the introductory section will provide motivations and review challenges related to interference modeling/measuring in wireless networks, and the final section will wrap up and outline several avenues for further research in the field. A more detailed view of the tutorial's topic is given in the next section.

  This tutorial has three major goals:

  • To give the attendees an organic view of the considerable body of literature devoted to interference modeling/measuring and interference-aware protocol design in multi-hop wireless networks,
  • To provide the attendees with an “interference-awareness toolkit”, i.e., with the expertise needed to effectively deal with the complex radio interference phenomenon; to this purpose, we will describe in detail the theoretical tools that compose this toolkit, which are derived from the theories of applied probability, information theory, computational complexity, integer/linear programming, and approximation algorithms, and
  • To outline the limitations of current approaches, and the challenges related to effectively dealing with radio interference in a realistic scenario; in this way, we will disclose several directions for further research in the field.

  The tutorial will be organized as follows.

  1. Motivation. First, we will motivate the need for adequately dealing with radio interference in a wireless network design. As a motivating example, we will refer to wireless mesh networks, where several types of interference has to be taken into account (intra-backbone interference, interference between client and backbone nodes, and external interference { i.e., interference with close-by wireless networks). We will also survey the challenges related to interference modeling/measuring and interference-aware protocol design in wireless networks.
  2. Part I: Modeling interference. In this part of the tutorial, we will extensively describe the several interference models introduced in the literature. First, we will outline the distinction between primary interference (which can occur also in traditional, wired networks), and secondary interference (which is particular to wireless networks). We will then survey existing secondary interference models, namely:
     1. Graph-based models, in which interference is modeled in terms of hop distance between links in the communication graph;
     2. Protocol and geometric models, in which a geometric notion of interference is used;
     3. SINR-based models, in which correct message reception at a receiver is driven by the experienced SINR value.
     We will end this part of the tutorial with a comparison of the various models, e.g., in terms of the network capacity nominally achievable under the various models.
  3. Part II: Measuring Interference. In this part of the tutorial, we will survey techniques and methodologies aimed at measuring interference relationships between network links. We will consider three different classes of such approaches:
     1. Pair-wise approaches, whose purpose is to estimate pair-wise interference, typically targeting 802.11 networks.
     2. Multi-way approaches, in which mutual interactions between larger subsets of links are investigated, again typically targeting 802.11 networks.
     3. STDMA approaches, whose purpose is to investigate multi-way interference in presence of STDMA-based MAC layer.
     This part of presentation will include enough details so that the attendees will be able to perform similar measurement experiments and derive interference relationships using commodity radio platforms, such as 802.11 or 802.15.4.
  4. Part III: Dealing with Interference. In this part, we will describe in detail the major techniques that have been studied to mitigate and/or eliminate interference. These include the use of multiple channels (both overlapping and non-overlapping), directional antennas, transmit power control, and MIMO antennas. The characteristics of these approaches including important technology parameters associated with them will be presented. A short survey of the literature on use of these techniques and impacts on interference will be given. We will conclude this part with a comparative analysis of the relative benefits of the different approaches.
  5. Part IV: Interference-Aware Algorithms. In this part of the tutorial, we will present a broad cross-sections of interference-aware algorithms for wireless networks. As a reference network architecture, we will consider wireless mesh networks. Examples of the following classes of algorithms will be given:
     1. STDMA scheduling. Transmission scheduling is the most fundamental problem in which interference play a significant role. As such, it has been widely studied in the literature. We will first show how the computational complexity of optimally solving this problem heavily depends on the underlying interference model. We will then present optimal algorithms under the primary interference model, and approximation algorithms under different secondary interference models.
     2. Channel Assignment. Channel assignment is another problem in which interference plays a fundamental role. We will survey channel assignment algorithms based on different interference models, and considering both the use of orthogonal and overlapped channels.
     3. Transmit Power Control. Work that uses power control for reducing interference, not simply for energy savings, will be presented and discussed.
     4. Routing. We will discuss interference-aware routing algorithms and present evaluations of their performances.
     5. Joint Approaches. We will present approaches where some combination of scheduling, channel assignment, transmit power control, and routing are considered as a joint optimization problem.
     6. Dealing with external interference. We will review recent approaches that account not only for internal, network-generated interference, but also for possible interference caused by external, close-by networks operating on the same frequency band.
  6. Final remarks. In the last part of the tutorial, we will wrap-up, discuss the limitations of current approaches for dealing with radio interference in wireless networks, and state challenges related to effectively tackling interference in a realistic scenario. This discussion will disclose several avenues for further research in the field.