Modeling and Mitigating Interference in Multi-Hop Wireless NetworksDouglas 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:
Biographical SketchesDouglas 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.
Wireless Network CodingDina 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.
Intended Audience and BackgroundThe 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:
Biographical SketchesDina 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.