Martin Haenggi - US grants

This project evaluates the extent to which ad hoc networks of embedded systems (NESTs) may be used to implement feedback control systems. Ad hoc NESTs are inexpensive and easy to deploy, but their ad hoc nature makes it impossible to realize feedback controllers in hard real-time. NEST feedback control systems, therefore, are soft real-time systems in which feedback measurements are delayed or dropped. Maintaining specified levels of overall closed loop performance in such a soft real-time environment is extremely challenging. This project will develop methods for assuring overall closed loop performance in NEST systems. This goal will be achieved by adopting a cross-disciplinary approach that integrates
research efforts in control, real-time systems, computer systems, and communications. In particular, the project tackles this problem by 1) the dynamic re-routing of connections using a polynomial extension of minimum hop routing schemes, 2) the development of novel soft scheduling methods whose behavior can be directly related to closed loop controller performance, and 3) the dynamic re-allocation of link capacities through the use of combined channel coding and ARQ methods.

The project's broader impacts will be expressed through an undergraduate level course that integrates control theory concepts with embedded system principles. Futher project impacts will be realized by coordinating this work with an existing DARPA contract that is developing middleware technologies for NEST-type systems.

Populating our world with networks of sensors requires fundamental understanding of tech-
niques for connecting and managing sensor nodes with a communication network in scalable
and resource-e .cient ways.The proposed research involves a comprehensive program of sensor
network architecture,design,evaluation,and implementation that integrates research expertise
in the areas of wireless networking and multiuser communications and provides numerous op-
portunities for enhancing student research and education in the area of sensor networks,at both
undergraduate and graduate levels.
The dominant trend in sensor network practice is to consider a dense collection of tiny sensor
nodes with limited computation and communication capabilities,all connected via a .at,or
ad hoc,wireless network.Yet theoretical studies in multiuser communications suggest that
substantially improved performance can be obtained through sophisticated coordination among
nodes,requiring more versatile radios,hierarchy,and perhaps even sparse wired connectivity.
Thus,the objectives of the proposed research are to:1)identify network architectures that
permit the implementation of sophisticated transmission schemes that have been theoretically
studied,2)analyze such schemes in the context of sensor networks and design new ones adopting
a cross-layer approach and 3)implement these schemes and verify their behavior on a real
testbed.
The intellectual merit of the project lies in the improved understanding of an important
emerging class of wireless networks,and in the attempt to unite theory and practice.Clos-
ing the widening gap between theoretically proposed strategies and practically implemented
ones is crucial to understanding and improving the performance and lifetime of these resource-
constrained networks.Through a rigorous analytic approach,contributions to the emerging area
of network information theory are expected,leading to substantial advances in energy-e .cient
and delay-constrained protocol design.
The broader impact is manifested in part through an e .ort to integrate teaching and research.
Experimentation on a hardware platform plays an integral role in both research and education.
It will be used for veri .cation,as well as for undergraduate and graduate projects that provide
students with hands-on experience in a real sensor network testbed.This project will enable
the acquisition of the necessary hardware.Two newly developed graduate courses on multiuser
communications and wireless networking will bene .t greatly from this project.It is anticipated
that by such close linking,research and education cross-fertilize each other within the framework
of this proposal.Further,since the proposed architectures and related issues carry over to other
important classes of networks,the .ndings from this research will have an impact on a much
broader class of wireless networks,including multihop cellular networks,that may soon become
signi .cant for a major part of our society.The broader impact will also be felt through a broad
dissemination of results and through current and future interactions with other universities.
A-1

The inherent non-determinism and dynamism and the communicational limitations of wireless ad hoc and sensor networks force a reexamination of the assumptions and models used for classical networks. There is a need for sound mathematical models to explore the complexities induced by the probabilistic and dynamic interaction of the physical and information processes. Hence, this project focuses on modeling and managing uncertainty in such systems, with the goals of achieving an improved understanding, deriving performance bounds, and developing innovative strategies and guidelines for protocol design, as well as providing cutting-edge research opportunities for both undergraduate and graduate students. The two-pronged research approach includes a theoretical and an experimental component. The multidisciplinary theoretical part combines methodologies from information and communication theory, and random graph theory and stochastic geometry, whereas the experiments are based on a sensor network testbed with mobile elements.

This project will contribute significantly to the ability to analyze and design robust and resource-efficient static and mobile ad hoc and sensor networks, and it is expected that the broader networking community will benefit from the models and design guidelines. Some models will hopefully be incorporated into standard simulation tools. The research findings are disseminated not only through the traditional channels but also via an educational outreach component, and their broader impact will be felt through the application to other important classes of networks, including multi-hop cellular networks that may soon become significant for a major part of our society.

Technology is developing at a tremendous rate, and it will not be long before we shall have to face entirely new mathematical challenges as to how to make good use of this emerging technology. One of the very real possibilities is the deployment of `smart dust', a vast network of radio transceivers, in order to monitor large areas and, possibly, track movements in that area. Such `smart dust' is of any use only if the various transceivers are very cheap, use very little energy, so that they are around for a long time, and do not cost much to put in place. In particular, the transceivers cannot be expected to be able to transmit far, and must be placed in essentially random positions. This leads us to numerous mathematical problems, several of which we hope to attack.

For example, a mathematical model of one of many real-life problems goes as follows. Suppose we have a large number of points (radio transceivers) in a square or circular disc, distributed at random. Let N be the network obtained by connecting each point to the k points nearest to it (each transceiver can communicate with the k transceivers nearest to it). How large should k be in order to make it likely that the network N is connected? In other words, how large should k be to make it likely that, for any two transceivers x and y, a message can be sent from x to y via a sequence of transceivers, i.e., there are transceivers a, b, ... , u, such that the message can be sent from x to a, from a to b, etc., and finally from u to y.

There are numerous other mathematical problems related to ad hoc wireless networks: for example, in the problem above we may relax the requirement that the entire network be connected, and want only a large set of transceivers that can communicate with each other. It also makes sense to care about the speed with which a message can be transmitted to faraway transceivers, and we may want to investigate how an efficient route can be identified. In yet another problem, we should take into account the interference encountered if several nearby transceivers broadcast at the same time.

The problems above belong to the theory of random geometric graphs, an area started by Gilbert about 45 years ago, but, curiously, still not too well developed. Our aim in this NSF project is to identify a number of problems that are not only of interest from the point of view of pure mathematics, but also have substantial applications to large ad hoc wireless networks.

Multihop transmission is increasingly being incorporated into modern wireless communication networks. These networks are central to our nation's future communications and monitoring infrastructures. The
basic motivation for multihop is that transmissions occur over shorter distances -- and therefore with higher received signal strength -- via many intermediate nodes rather than over longer distances -- and
therefore with lower received signal strength -- between the source and destination of the information. However, multihop transmission involves complex interactions among channel coding at the physical
layer, distributed channel access at the link layer, and multihop routing at the network layer. These techniques have been studied largely in isolation by different communities, whereas this project
focuses on their interaction, especially in delay-constrained scenarios.

This research involves models for general wireless multihop networks, and develops tradeoffs for transmission along an individual routes of up to M + 1 nodes. Transmission between the end nodes can occur in a single hop, or up to M hops. Multihop transmission increases the received signal-to-noise ratio (SNR) at intermediate nodes; however, this observation does not take into account the important practical issues of power and bandwidth allocation, end-to-end delay, error propagation, or interference induced by other transmitters. Among other results, preliminary research indicates that the benefits of multihop are eroded by these issues, especially for high spectral efficiency, i.e., high data rates relative to the available bandwidth. The investigators take a comprehensive look at multihop transmission from the point of view of communication theory, mathematical networking, and networking practice, with the goal of offering solutions that will impact a major part of our society.

Geometric Analysis of Large Wireless Networks:
Interference, Outage, and Delay

Martin Haenggi, University of Notre Dame

Abstract:
Large wireless systems, in particular ad hoc and sensor networks, have great potential for numerous applications. They have been the subject of intense investigation over the last decade. Despite these efforts, many of their fundamental properties are still not well understood, and it is unknown how to design network protocols in an optimum fashion. Important progress has been made in determining the capacity scaling behavior of these systems, but the asymptotic nature of these results severely restricts their applicability to practical networks. This project complements such scaling studies by aiming at a precise characterization of certain performance metrics, including reliability and delay.
Further, some of the standard modeling assumptions, such as the uniformly random node distribution are questioned, and existing results are extended to other node distributions that better reflect real networks with interacting nodes.

The investigators use a rigorous analytic approach that combines tools from stochastic geometry, point process theory, branching processes, and information theory. Since the network geometry critically affects the interference and signal-to-noise-ratios, an emphasis is put on the geometric properties of the underlying node distribution. The project focuses on several concrete problems in interference characterization, link outage, and the tradeoff between end-to-end delay and outage in large networks with randomly distributed nodes. The objectives are to analytically determine or bound these quantities for general node distributions and to derive guidelines for protocol design from the theoretical insight gained.

Networked wireless communications over multiple hops is rapidly emerging as the main architecture of future wireles systems, including multihop extensions of cellular and WiFi networks, mesh networks, and sensor networks. Common among these types of networks is that they are not completely unstructured (or ad hoc) networks, but traffic is routed and accumulated towards a common destination. Due to this characteristic property, these networks will be referred to as Networks with Traffic Accumulation, or NETAs. Traffic accumulation creates hot sposts or bottlenecks around the common destination because of the increased traffic load and interference. Despite the severity of the hot spot problem, there is a lack of efficient methods to cope with it.

This research addresses the hot spot issue in NETAs by developing new distributed error correction strategies tailored to two important subclasses- line networks and tree networks. In line networks, the investigators study fundamental properties and the design of distributed channel coding protocals using serially concatenated and protograph-based constructions to strengthen the error correction capability near the destination without sacrificing badwidth efficiency. In tree networks, several source nodes may wish to employ a common relay node to broadcast their information to multiple destination nodes which may have access to side information from "overheard" source messages. The investigators explore a novel approach where each source uses a distinctlow rate code for transmission to the relay, whereas the decoded messages are re-encoded using a high rate "nested code". In addition, interlayer issues are considered, in particular the joint design of efficient channel access and routing schemes together with the porposed coding schemes.

Engineering - Electrical (55)

The project is creating a new approach for teaching systems engineering within the electrical engineering (EE) curriculum. The approach makes use of a hardware/software platform and accompanying curricular innovations to bring a more engaged, hands-on, exploratory focus to what is probably the most convention-bound component of a typical undergraduate electrical engineering education. Unlike previous attempts to create a less abstract and more engaging systems engineering curriculum, which focused almost entirely on software tools (e.g., MATLAB), the proposed project is creating a hardware/software platform and using that platform to vertically integrate key systems concepts across the undergraduate curriculum. The platform is letting students explore systems applications using a variety of hardware devices such as signal generators, filters, A/D and D/A converters, sensors, and a microprocessor. The platform contains an interface to a student's MP-3 player and cell phone to bring home the relevance of the systems perspective to modern technology. To allow students to see the signals they are generating and manipulating, the platform includes a suite of visualization software. The project is being evaluated using an assortment of tools including an established signals and systems concept inventory along with the analysis of student products and enrollments numbers. The investigators are disseminating their results by posting their material on a website, by publication and presentation in engineering education venues, and through the investigators connection with the signals and systems concept inventory community. Broader impacts include the dissemination of the material, the focus on Hispanic students, and the outreach effort to high school students.

Although theoretical results predict that significant gains can be
achieved from node cooperation, current wireless systems are exclusively
built on point-to-point communication, where transmissions are separated
in time, frequency, or space. Before cooperative techniques can be
implemented, two key questions need to be addressed: How do they perform
in the context of a larger network, and how do they perform in actual
experiments?

This project aims at providing answers to both these questions by
combining theory and experimental work. On the theory side, the
investigators use a rigorous analytic approach that combines tools from
stochastic geometry and information theory. The stochastic geometry
approach permits statements about ensembles of networks, rather than
just a single fixed network geometry, which is often more tractable and
leads to more general results. On the experimental side, performance
measurements are taken on small cooperative networks of software
radio devices. They are used to derive analytical models that can be
used at higher layers in the protocol stack and to determine the overhead
and control traffic required to set up the cooperation.

Based on the insight gained from both theory and experiments, novel
cooperative protocols for wireless networks are derived.
It is expected that the project will enable significant improvements in the
performance of wireless systems, thereby helping to overcome the
spectrum scarcity. The results are be disseminated in form of conference
and journal articles, tutorials, and short courses, and some ideas will
hopefully lead to patents.

Demands for wireless access to the Internet and voice communications
keep growing exponentially, while the available spectrum remains scarce.
As a result, cellular, WiFi, mesh, and cognitive networks are
increasingly interference-limited.

Despite significant efforts over the last decade, key aspects of the
interference are still not well understood. In particular, the spatial
and temporal correlation of the interference has been largely ignored,
despite its profound impact on the performance. With the proper
mathematical and numerical tools from stochastic geometry and spatial
statistics, the impact of protocol decisions on the interference as a
random field in space and time can be assessed, and, even more
importantly, the question of how to engineer the interference for
optimum performance can be addressed.

This project aims at taking a major step in this direction. It focuses
on developing a fundamental understanding of the structure of the
interference using a rigorous analytical approach. While the outcomes of
the project will be applicable to and relevant for most modern wireless
systems, they are particularly pertinent for cognitive systems, where
interference between primary and secondary users is not just a technical
problem leading to a performance reduction, but also a regulatory and
legal issue.

Objective:

The objective of this project is to lay a theoretical foundation for all aspects of virtual full-duplex wireless networks and to build prototypes using readily available software-defined radios and evaluate the performance. Commercial and military radios of today are half-duplex and cannot transmit and receive simultaneously over the same frequency band due to overwhelming self-interference. This project challenges the paradigm by proposing full-duplex and virtual full-duplex design of the physical, medium access control and network layers based on emerging technologies.

One key technique, called rapid on-off-division duplex, allows all nodes to transmit and receive simultaneously by choosing an on-off mask and letting each node transmit through the on-slots and receive over the off-slots. Over a single frame, every node can simultaneously broadcast a message to all neighboring nodes and receive a message from every neighbor at the same time. The transformative solution removes a major constraint on the transmission schedule and thereby increases the throughput and decreases network overhead.

Intellectual merit:

The intellectual merit lies in transformative network architectures and designs that enable nodes to transmit and receive information at the same time, contrary to conventional wisdom of separating transmission and receptions in time and/or frequency. This challenging research will draw from and, in turn, add to, communication theory, signal processing, information theory, and network theory.

Broader impacts:

The broader impacts are radically new wireless standards with robust and significantly improved performance, involving undergraduate and graduate students in cutting-edge research, and integrating new research results into the curricula.

The new center site of the Industry/University Cooperative Research Center (I/UCRC) for Broadband Wireless Technologies and Applications at the University of Notre Dame will complement the existing center?s activities through a focus on emerging wireless technology, economics, and regulatory policy challenges. The site intends to develop a cohesive and integrative approach to broadband research challenges in areas including cellular data collection, analytics, & visualization; heterogeneous network modeling, analysis, and design; electromagnetic radiation exposure; spectrum sharing; vehicular communications; inter-machine wireless; crowd-sourced approaches and advanced circuitry.

The center site addresses an area of critical economic and has the potential to support development of broadband wireless as a platform for innovation as addressed in the White House PCAST Report. The center site at Notre Dame has the potential to link an even greater diversity of member companies across the broadband industry sector with university a broader base of discovery in this area. The site will provide early exposure to the concerns of and approaches employed in industry in students? education and career development. Underrepresented undergraduate and graduate students will be recruited to the program through existing mechanisms at the site such as the REU program in Experimental Research on Wireless Networking (ERWiN), in which more than 40% of the participants were from underrepresented groups over the last five years.

Demands for wireless Internet and voice access have continued to grow exponentially, while the available spectrum remains scarce. As a result, novel architectures and transmission techniques are needed for cellular networks to improve their spectral efficiency and provide consistent and high-speed wireless service for all users. The two key approaches to achieve this goal are increased network density and heterogeneous network architectures, where multiple tiers of base stations are deployed with different capabilities, depending on the user density and traffic demands. For such networks, new mathematical models and techniques are needed that capture their inherent randomness and heterogeneity. Stochastic geometry is a mathematical theory that is ideally suited for such problems. It provides both the models and the theory for the analysis of the network performance and user experience. This project focuses on the development of stochastic geometry-based tools tailored to the fifth generation of cellular systems (5G), which will result in novel design insights and help identify promising network architectures without the need for extensive and expensive simulations. Hence it will have a significant impact on the discussions on 5G that currently dominate the wireless industry and academic research and may even influence the standardization process. In addition, the project devises novel analytical techniques and makes theoretical contributions that are applicable beyond cellular networks, and it helps train future generations of students in emerging wireless technologies and analysis techniques.

As cellular networks become denser and more heterogeneous, the locations of the base stations become more irregular due to restrictions on the placement and adaptation to users and traffic. As a result, classical network models such as lattices become outdated and need to be replaced by models that capture the inherent randomness in the base station locations. Recently, researchers have applied techniques from stochastic geometry for the analysis of some of the key metrics of cellular systems, most notably the signal-to-interference ratio, which determines the quality of the wireless connections. However, the underlying model was mostly restricted to the Poisson point process, which is analytically convenient but not very realistic. The analysis of more accurate models and of advanced transmission schemes such as base station cooperation and multi-antenna transmission has proven rather difficult. Hence there is an urgent need to devise new models that accurately describe current and future cellular networks and to significantly extend the set of tools for their analysis. This proposal aims at meeting this need by applying novel ideas and recent insights to develop new theoretical methods that expand the currently available ones in three main directions: (1) efficient ways to obtain highly accurate approximate results for diverse network models; (2) fine-grained and sharp results on the experience of individual users; (3) fundamental insight into the impact of the temporal dependence of the interference in cellular systems. The analytical methods used include Palm theory, Tauberian theorems, series and factorial moment expansions, and general probability theory, and the models will be validated with actual data.

The use of wireless networks is rapidly extending towards applications with strict reliability and/or latency constraints. For example, in 5G cellular systems, standards not only specify average data rates but also the minimum rates that 95% of the users should be able to achieve. Meanwhile, for vehicular safety messaging or in manufacturing, extremely high reliability under strict latency constraints is required. In contrast to these developments, the theoretical tools available for wireless network analysis and design mostly focus on network-wide averages, which makes them unsuitable for these new applications. As a result, there is an urgent need to develop a theory for networks with strict performance constraints and guarantees. This project focuses on the development of such a theory, which will allow a sharp performance analysis and enable researchers and engineers in industry to characterize the user experience much more efficiently than by lengthy and expensive simulations. Accordingly, it is expected to have a significant impact on the design of future wireless systems. In addition, it will help train future generations of students in emerging wireless technologies and analytical techniques.

In view of the increasing density, irregularity, and uncertainty in the locations of wireless transceivers, a probabilistic approach to modeling and analysis that includes the network geometry as its key ingredient is warranted. Stochastic geometry is the natural mathematical tool for modeling and analysis. However, its use has been largely restricted to the derivation of average performance metrics, which do not capture the disparity in the link or user performances nor incorporate reliability or latency constraints. To address these shortcomings, this project develops a new theoretical framework, called deep stochastic geometry, that focuses on spatial distributions rather than merely averages. Deep stochastic geometry enables a direct evaluation of the performance of user or link percentiles and the performance under constraints. As such, it is a theory of guaranteed performance, in contrast to the existing theory of average performance. At the heart of the new theory are so-called meta distributions, which are distributions of conditional distributions (given the network geometry). Meta distributions naturally emerge when the different sources of randomness in a network are separated according to their time scales. The specific research activities include the development of efficient numerical methods and simulation techniques to calculate meta distributions, finding effective approximation techniques, the extension of meta distributions to joint distributions, and, finally, the combination of multiple metrics into a comprehensive approach to characterize and optimize network performance under constraints.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.