Tutorials 

 

The MobiCom 2008 program will include two half-day tutorials on Sunday, September 14 on timely areas related to the scope of the conference. Full details on the scheduling of these two tutorials will be posted here shortly. The following two tutorials are planned for MobiCom 2008:

   Tutorial 1 (half-day, morning)  

Modeling and Mitigating Interference in Multi-Hop Wireless Networks

Douglas M. Blough (Georgia Institute of Technology, USA)
Samir R. Das (Stony Brook University, USA)
Paolo Santi (IIT - CNR, Italy)

One of the major factors limiting traffic carrying capacity in wireless networks is radio interference. Dealing with radio interference will become increasingly important when next generation wireless networks become widespread, as scenarios in which several closely located wireless networks sharing the same frequency bands for communication in an unregulated environment will become very common. In these situations, not only internal interference (i.e., interference generated by nodes belonging to the same network), but also external interference (i.e., interference generated by close-by wireless networks) has to be taken into account. If both internal and external wireless interference are not carefully addressed in a wireless network design, performance delivered to the end user will be highly unpredictable and, in general, poor. Hence, mechanisms for adequately dealing with interference are a key ingredient for the success of next generation wireless networks.

The above discussion motivates the considerable interest of the research community in understanding and analyzing the impact of interference on multi-hop wireless network performance. A seminal work in this area by Gupta and Kumar analyzed traffic carrying capacity of a wireless network in an interference-limited environment. Following that work, several authors have characterized network performance in several interference-limited environments, and designed "interference-aware" network protocols.

A major challenge in dealing with wireless interference is how to model such a complex physical phenomenon. In fact, wireless interference is closely related to radio signal propagation, whose accurate modeling has challenged (and still challenges) the communication engineering community for many years. Hence, the definition of radio interference models that are at the same time accurate and manageable from an analytical/algorithmic point of view is very difficult, and has been a matter of considerable research effort. In early works on multi-hop wireless networks, very simple interference models (e.g., distance-based or graph-based models) were adopted in the analysis and/or design of wireless network protocols. More recently, increasingly complex (e.g., SINR-based) interference models have been considered in the literature.

Another fundamental aspect in the design of "interference-aware" network protocols is how to measure interference. In fact, many of the interference-aware approaches presented in the literature are based on the assumption that the interference relationships between the various network links are known. Indeed, instantiating these relationships via measurements in a real-world scenario is a very challenging research problem by itself, which has been addressed only very recently.

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.

Tutorial Outline

  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. 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:
    • Graph-based models, in which interference is modeled in terms of hop distance between links in the communication graph;
    • Protocol and geometric models, in which a geometric notion of interference is used;
    • 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. Measuring Interference. In this part of the tutorial, we will survey techniques and method- ologies aimed at measuring interference relationships between network links. We will consider three different classes of such approaches:
    • Pair-wise approaches, whose purpose is to estimate pair-wise interference, typically targeting 802.11 networks.
    • Multi-way approaches, in which mutual interactions between larger subsets of links are investigated, again typically targeting 802.11 networks.
    • 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. 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. 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:
    • 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.
    • 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.
    • Transmit Power Control. Work that uses power control for reducing interference, not simply for energy savings, will be presented and discussed.
    • Routing. We will discuss interference-aware routing algorithms and present evaluations of their performances.
    • 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.
    • 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.

Biographical Sketches

Douglas M. Blough received the B.S. degree in electrical engineering and the M.S. and Ph.D. degrees in computer science from The Johns Hopkins University, Baltimore, MD, in 1984, 1986, and 1988, respectively. Since Fall 1999, he has been Professor of Electrical and Computer Engineering at the Georgia Institute of Technology, where he also holds a joint appointment in the College of Computing and is Co-Director of the NSF Industry-University Cooperative Research Center on Experimental Research in Computer Systems (CERCS). From 1988 to 1999, he was on the faculty of Electrical and Computer Engineering at the University of California, Irvine. Dr. Blough's research interests include wireless multihop networks, dependability and security, and distributed systems. In these areas, he has published over 100 articles in refereed journals and conferences. Dr. Blough was Program Chair for the 2000 International Conference on Dependable Systems and Networks (DSN) and the 1995 Pacific Rim International Symposium on Fault-Tolerant Systems, and General Chair for the Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS) in 2004 and 2006. He has been on the Program Committees of numerous other conferences, including MobiHoc 2006 and MobiCom 2008, was Associate Editor for IEEE Transactions on Computers from 1995 through 2000, and was Associate Editor for IEEE Transactions on Parallel and Distributed Systems from 2001 through 2005. He was also Tutorials Chair for MobiHoc 2006.

Samir R. Das is currently an associate professor in the Computer Science Department in the State University of New York at Stony Brook. He received his Ph.D. in Computer Science from Georgia Institute of Technology, Atlanta, in 1994. His research interests are in wireless networking and mobile computing, focusing on protocols, systems and performance evaluation. He received the U.S. National Science Foundation's CAREER award in 1998 and the best paper award in ACM MobiSys conference in 2007. He has been a speaker in the Distinguished Visitor program of the IEEE Computer Society during 2001-03. He co-chaired the technical program committee for several prominent conferences and workshops on wireless networking, such as the ACM MobiHoc (2001), ACM MobiCom (2004) and IEEE WiMesh (2006). He also served on the program committees of many conferences including Mobicom, MobiHoc, INFOCOM, ICDCS, SECON, etc. He currently serves or has served on the editorial board of the IEEE/ACM Transactions on Networking, IEEE Transactions on Mobile Computing, ACM/Kluwer Wireless Networks Journal and Ad Hoc Networks journal. Dr. Das has given several tutorial talks on wireless mesh networking in ICNP (2005), INFOCOM (2006), MobiHoc (2006) and Globecom (2006) conferences.

Paolo Santi received the Laura Degree and Ph.D. degree in computer science from the University of Pisa in 1994 and 2000, respectively. He has been researcher at the Istituto di Informatica e Telematica del CNR in Pisa, Italy, since 2001. During his career, he visited Georgia Institute of Technology in 2001, and Carnegie Mellon University in 2003. His research interests include fault-tolerant computing in multiprocessor systems (during PhD studies), and, more recently, the investigation of fundamental properties of wireless multihop networks such as connectivity, topology control, lifetime, capacity, mobility modeling, and cooperation issues. He has contributed more than 40 papers and a book in the field of wireless ad hoc and sensor networking, he has been General Co-Chair of ACM VANET 2007, and he is involved in the organizational and technical program committee of several conferences in the field. Dr. Santi presented a tutorial on "Topology Control in Wireless Ad Hoc and Sensor Networks" at ACM MobiCom 2003 and ACM MobiHoc 2004. He is a senior member of ACM and SIGMOBILE.


   Tutorial 2 (half-day, afternoon)  

Wireless Network Coding

Dina Katabi (MIT, USA)
Sachin Katti (MIT, USA)

Network coding, i.e., having the routers mix packets' content, has recently attracted significant interest. Much theoretical work shows that network coding is optimal for multicast and improves throughput for unicast traffic. Emerging applications show how the theoretical results translate into practical gains in domains including peer-to-peer content delivery, anonymous communication, and switch design. Arguably, however, the most appealing domain for network coding is wireless networks, where recent advances have established network coding as an alternative design paradigm for wireless networks which delivers significant improvement in throughput and reliability. In only a couple of years, network coding has been integrated within the current network stack, proved to be an effective technique for opportunistic routing, shown robustness against Byzantine adversaries, and considered as a facilitator for mobile communication. Also, wireless network coding has been expanded from linear operations over packets to symbol-level network coding, a cross-layer approach that involves cooperation between two layers in the stack: the physical layer and the network layers. Finally, it has been further pushed all the way to the analog domain, introducing analog network coding, which operates over signals instead of bits.

Wireless packet networks offer a natural setting for network coding because the very characteristics of wireless links that complicate routing, namely, their unreliability, broadcast nature, and interference, make coding a natural fit. For example, wireless networks exhibit high redundancy because a broadcast packet is heard by multiple nearby nodes. Network coding can exploit this redundancy to perform in-network compression of the data, thereby increasing the wireless throughput. Further, while interference has traditionally been considered harmful, network coding allows the nodes to exploit interference strategically, and perceive it as a special code which compresses the number of transmissions and improves throughput. This synergy between the characteristics of the wireless medium and network coding coupled with the fact that wireless networks are more amenable to innovative designs than their wired counterparts, opens up many opportunities for successful research.

Despite the significant benefits of network coding, there is scant literature relevant to the systems and networking community introducing them to this topic. This tutorial aims to fill that gap. The tutorial will strive to point out the engineering tools network coding provides in simplifying wireless network design. It will walk the audience through the engineering process of applying these tools to wireless systems. The tutorial provides participants with the theoretical and practical knowledge necessary to understand the field of network coding, and also to conduct independent, innovative work in the area.

The tutorial will have a mixture of theoretical foundations and practical approaches. The first part of the tutorial will focus on the algebraic principles underlying network coding and will also introduce distributed randomized network codes and discuss their properties. We will not assume any prior knowledge of advanced algebra or optimization. The second part of the tutorial will discuss wireless network coding and explain how it can improve throughput and reliability. It will also discuss new codes such as symbol-level network coding and analog network coding. As we explain these concepts, we will focus on the current research trends and practical implementations.

Tutorial Outline

  1. Network Coding Basics:
    • Algebraic network coding principles
    • Distributed randomized network codes
    • Minimizing transmission cost and its relation to traditional routing
  2. Wireless Network Coding:
    • Inter-flow and intra-flow network coding
    • Symbol-level network coding
    • Analog network coding
    • Real network codes and their application to audio and video applications
  3. System Design and Implementation:
    • Integrating network coding into the network stack
    • Implementing network coding in software radios

Intended Audience and Background

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 beneficial to:
  • Researchers and graduate students in the area of networking and communications (especially wireless), who want to explore further research opportunities.
  • Practicing networking professionals in the telecommunications and networking industry, especially those who would be interested in applying new network coding primitives in the design of future wireless networking products.

Biographical Sketches

Dina Katabi is an Associate Professor in the Electrical Engineering and Computer Science department at MIT. She received her M.S. and Ph.D. degrees from MIT, in 1998 and 2003. She is a leader in the area of computer networks and distributed systems. Her work focuses on wireless networks, network security, routing, and distributed resource management. She has been awarded a the class of 1947 Career Development Chair in 2007, a Sloan Fellowship award in 2006, the NBX Career Development chair in 2006, and an NSF CAREER award in 2005. Her doctoral dissertation won an ACM Honorable Mention award and a Sprowls award for academic excellence.

Sachin Katti is a senior Ph.D. student in computer science at MIT. He received his B.Tech. in electrical engineering from the Indian Institute of Technology, Bombay, in 2003 and a M.S. in computer science from MIT. in 2005. His dissertation research focuses on redesigning wireless networks with network coding as the central unifying design paradigm. His work on practical network coding was published in SIGCOMM, NSDI, and other major networking conferences.



Home | About MobiCom | Call for Papers | Committees | Registration | Hotel and Travel | Advance Program
Tutorials | Panel | Demos and Exhibits | Workshops | Corporate Supporters | Invited Talks | Posters & SRC

 
 

ACM SIGMOBILE