Response to DARPA RFI 06-17
Information Theory for Mobile Ad-Hoc Networks (MANETS)
Fundamental Capacity Limits and
Optimized Node Cooperation in MANETs
Stephen Boyd / Vincent Chan / Todd Coleman / Michelle Effros
Andrea Goldsmith / Robert Gallager / Ralf Koetter
Ramesh Johari / Muriel Medard / Sean Meyn
Balaji Prabhakar / Asuman Ozdaglar / Pierre Moulin
Devavrat Shah / Ada Poon
Lizhong Zheng
Abstract:
While there has been much progress in obtaining the fundamental capacity limits of wireless single and multiuser channels, there is very limited understanding about the fundamental capacity limits associated with mobile ad-hoc networks (MANETs), even under fairly simple modeling assumptions. More realistic system assumptions, such as fading, node mobility, heterogeneous bursty traffic, delay and energy constraints, limited channel side information, distributed control, robustness, and security may lead to new definitions of fundamental capacity that differ from the traditional Shannon capacity associated with infinite complexity and delay. Moreover, even if the fundamental capacity of a network can be obtained, it is not that valuable in the absence of separation theorems between the source encoding strategy and the networking strategy. Thus, along with fundamental limits on network capacity, separation theorems between source coding, channel transmission, and networking must be investigated. When such theorems fail, we must pursue either bounds to demonstrate that separated strategies yield good performance or strategies for node cooperation via low complexity non-separated codes.
We have brought together a strong team of interdisciplinary researchers with an extensive history of collaboration to address these issues. We believe our team is uniquely poised to characterize upper and lower bounds and scaling laws for the fundamental capacity limits of MANETs, to develop techniques that approach these fundamental limits given realistic system models and constraints, and to investigate source/channel/network separation theorems along with optimal node cooperation. The proposed work along these lines will be described below in response to the questions posed in the RFI.
Question 1: To what extent is a precise characterization of mobile wireless network capacity achievable?
Before one can speculate about a precise characterization, it is necessary to define fundamental network capacity. For a network with n nodes, its capacity region is of dimension n(n-1), since it defines all rates simultaneously achievable between any two nodes in the network via single and/or multiple hop transmission [TouG03]. The shape of this region will depend on the system parameters and constraints such as energy/power, bandwidth, channel characteristics, node mobility, delay constraints, traffic characteristics, and robustness to uncertainty and attack. In many settings, most notably delay constrained situations; the capacity region will be zero if there is no notion of outage or message error. Indeed, defining capacity only in the case of asymptotically small probability of error, infinite delay, and infinite complexity has been, at the same time, the enabling but also one of the most limiting aspects of Shannon theory and a major reason why the marriage between information theory and network theory remains unconsummated [EphH98]. We believe that a fundamental capacity theory for networks must include notions of nonzero error probability, channel outage, and lost packets/messages, which give rise to new capacity definitions such as capacity versus outage and throughput capacity [EffG98a]. Indeed, one of the most challenging aspects of an information theory for networks is just to find a way that partial decoding, yielding non-vanishing error probabilities, may be incorporated into operational limits.Thus, our characterization of network capacity will include both traditional Shannon theoretic capacity (which will often be zero under practical constraints) as well as these more general capacity definitions, which provide more insightful capacity metrics under the typical operating conditions of practical networks. In the discussion below on capacity regions, the capacity we compute will encompass this more general metric.
Unfortunately, a precise characterization of the Shannon capacity region for a general ad-hoc network under the simplest of assumptions - an AWGN channel with no delay or complexity constraints - has been an open problem for decades. Even simple channels within the broader context of an ad-hoc network, such as the relay channel or interference channel, have unknown capacity in the general case. However, much progress has been made on obtaining upper and lower bounds for these component channels in some settings (e.g. [KraGG05, HosZ05, RezKV05, VisJ04]), as well as in scaling laws for uniform capacity in some asymptotic settings (e.g. [XieK04, ElG05, GasV05, DigGT05]). Thus, we believe that a tractable formulation of network capacity for this program must be in terms of upper and lower bounds, which would be made progressively tighter over the five year program duration via acquired insights to refine the cut-set upper bounds and more sophisticated networking techniques to increase the lower bounds. Such bounds will provide tremendous new insights into network performance and practical designs. Specifically, tight upper bounds would define the best performance that could be expected of the network and how various constraints and assumptions affect this performance. Tight lower bounds provide much insight into near-optimal strategies for user cooperation and resource allocation over available degrees of freedom, with significant potential impact for practical designs. Large gaps between the upper and lower bounds would indicate that more work is needed to develop new techniques to significantly improve the lower bounds and/or new insights are necessary to constrain the upper bounds and thereby tighten them. The upper and lower bounds will meet under certain system parameterizations and/or constraints, as well as in certain asymptotic regimes associated with single-letter characterizations (such as scaling laws for homogeneous traffic and node capabilities), in which case a precise capacity characterization would be determined. Part of the proposed work would be to determine scenarios where the upper and lower capacity bounds meet, which would help in tightening the bounds over the entire set of system constraints.
There are many ways to study the impact of various system assumptions and constraints on the n(n-1)-dimensional capacity region bounds. We propose the following characterization. We view energy and delay as fundamental axes of the capacity region. Hence, for a given set of system assumptions and constraints, the network capacity upper and lower bounds will be characterized as a 3n(n-1)-dimensional region, of which a 3-dimensional slice indicating capacity or throughput as a function of energy and delay between any two nodes in the network is shown in the figure below. This region is then parameterized by various system assumptions and constraints. For example, multiple antennas at each node will increase the upper and lower bounds (added degrees of freedom), whereas robustness to attack will decrease these bounds (reduced degrees of freedom). The precision to which these network capacity bounds can be characterized will depend on how many network and system parameters one wishes to allow in the characterization. We will begin our capacity characterization under the most basic assumptions (e.g. heterogeneous nodes, continuous traffic, no fading or mobility) and, once these bounds have been obtained, consider the most promising directions in which to generalize them under more complex assumptions. Note that these bounds will require precise information about the network setup, in particular either the network topology and channel models or the channel gains between nodes.
Figure 1: Three-dimensional slice of 3n(n-1)-dimensional capacity region
In many circumstances, especially when parameters such as latency, mobility, and heterogeneity are included, it will be difficult to obtain these multidimensional upper and lower capacity bounds. In these cases we plan to investigate a rate of growth characterization with upper and lower bounds that match in an order sense. We have already determined such bounds to characterize a fundamental relationship between capacity, delay, and energy [GamMPS04a, GamMPS04b, TouG04]. Such single-letter characterizations of the capacity region coincide with letting one or more of the parameters in the capacity region of Figure 1 go to infinity. Determining which asymptotics are of value for capacity characterization will be part of the proposed work.
Question 2: How would one recognize a “complete” mobile wireless network capacity limit formulation if one were to see it?
A complete mobile wireless network capacity formulation must be sufficiently general to characterize the capacity region under various system parameterizations, constraints, and assumptions, through either the exact region when possible or through bounds and scaling laws. However, the region characterization must be complemented by a characterization of the optimal forms of node cooperation and network resource allocation that achieve these bounds. Hence, a large part of our efforts will be focused on investigating optimal forms of node cooperation and resource allocationover the network degrees of freedom. These optimal strategies will generally depend on the network topology, the channel SNR, and the channel side information available at the nodes. A complete network capacity formulation must also consider the fragility of the result to the underlying modeling assumptions: small changes in these assumptions should not fundamentally change the capacity, and thus any capacity theory for networks requires robustness to the modeling assumptions, analogous to robust strategies developed by control theorists in the face of modeling errors.
Novel forms of node cooperation have been the focus of much recent work in MANETs, including network coding, virtual MIMO, cooperation diversity, conferencing, and relaying with no, full, and partial decoding. Network coding has proven to be an effective way to increase network capacity over traditional routing schemes for multicast [KoeM03, LunRKM05, LunMK06, LunMKE05, LunMK05, DebEHKKLMR05]. Virtual MIMO leverages the diversity and multiplexing benefits of multiple antennas by pooling antenna resources of nodes that are close together on the transmit and/or receive end to increase capacity [SenEA, LanTW04, Hos04, Hos05, KhoSA04, NgA04, NgA05, NgA06, NgLG06, JinMA04Summary:Not available.....
]]]. The capacity benefits of conferencing have been characterized for MAC channels and for relay channels [Wil83, NgMGSY06], and our proposed work will investigate the benefits of conferencing in a more general network setting. Relaying via Decode-and-Forward (DF) and Amplify-and-Forward (AF) has been well studied and is capacity achieving in some limited settings [KraGG05, NgA05]. However, more general forms of relaying need to be developed and explored, especially the notion of partial message decoding at each node. Network coding is one example where nodes cooperate without decoding at intermediate nodes. Another form of relaying with partial decoding that we plan to explore is error exponents in list decoding, which is a natural generalization of DF and AF. . Indeed, we view list decoding as an integral part of expanding the consideration of issues of distortion measures, which are intrinsically linked to the types of trade-offs we propose to study [Gur06]. A take-away lesson from all work on node cooperation is that - contrary to popular belief - interference is not always bad. If coding is done properly and a small amount of coordination between users is done, low-complexity transmission schemes can be constructed that allow for an aggregate benefit to the system [ColMEM05].
Part of the complete capacity characterization for MANETs must include the optimal resource allocation across its many degrees of freedom. We plan to explore dynamic resource allocation over multiple dimensions including bandwidth, power, rate, antennas, and end-to-end routes, using both centralized and distributed optimization techniques. Power control impacts many aspects of MANET design and is therefore a critical parameter to optimize: it can be used at the link layer to compensate for random variations in the channel, at the MAC layer to maintain tolerable interference between users, and to change network connectivity, which impacts routing protocols [TouG03]. Another key area of investigation is to consider how the degrees of freedom associated with multiple antennas – which can be used for interference cancellation, MIMO, and/or beamforming - should be allocated in conjunction with the upper layers of a wireless network to optimize network performance [Poo05, PooBT05]. In many resource allocation problems, sensitivity to certain ‘control parameters’ is extremely low in heavy traffic (operation near capacity) [ChePM03], which implies a certain robustness of resource allocation techniques in such settings.
Even in the cases where significant progress has been made in determining network capacity, these results are often highly fragile relative to the assumptions used in the problem formulation. In this context a central step towards an information theory for networks that is relevant to practical designs must include capacity characterizations that are relatively insensitive to small variation in the investigated scenario, e.g. when the network topology, the channel state information (CSI), or the characteristics of interfering signals are not perfectly known or cover a range of parameters. For example, the capacity regions obtained through network coding are demonstrated in [DouFZ05] to be highly dependent in methodology and final result on the network in question. Similarly, it is known that capacity of a broadcast channel with perfect transmit and receive CSI is achieved with dirty paper coding [WigSS05]. However, it was shown in [LapSW05] that the sum rate capacity of this channel is greatly reduced if the fading in the channel is not known precisely, and therefore there is no graceful transition from a perfectly known channel to approximate knowledge in terms of channel capacity. The development of robust capacity characterizations that are relatively insensitive to small variations in the investigated scenario is essential for practically useful results.
A companion question to how a complete capacity characterization would be recognized is how such a characterization would be used. Shannon’s landmark source-channel separation theorem decoupled the design of source encoders and channel transmission techniques in theory and (mostly) in practice as well. In other words, when separation is optimal on a point-to-point link, channel capacity becomes the only metric of importance to source code design: the underlying capacity-achieving techniques are irrelevant to this design. While separation greatly simplifies source and channel code design, it does entail some performance penalty in practice, especially under delay and complexity constraints [EffG98b]. However, it is not at all clear that the optimality of source-channel separation in point-to-point links can be extended to optimality in separating the source coding, channel modulation and coding, multiple access, and routing/relaying in MANETs [EffKGM04]. In fact, it is known that separation of source and channel coding does not hold even for simple networks like a multiple access channel [CovT91]. Likewise, separation between source and network coding and channel and network coding can also fail in simple networks [EffMHRKK03]. Mirror site selection is another example that separation between source coding and networks is suboptimal. Indeed, if such separation were optimal, then the deliberate duplication of information at the ingress of the network would never be of use. In effect, the presence of duplicated information allows connections to occur even in the event of congestion, which may throttle information sufficiently to preclude certain connections from taking place. There is in effect a lack of source/network coding separation [RamKCE04].
We plan to investigate under what conditions separation of source-channel-network coding is optimal, where coding in this context is generalized to encompass all transmission strategies associated with the source, channel, and network, respectively. When such separation is not optimal, it is critical to understand the performance cost of separation, as design modularity is clearly desirable and often essential in complex systems. Performance cost must also be clearly defined, and this cost definition will depend on the nature of the sources, channels, and networks. When the cost of separation is high, then we will explore joint source-channel-network coding to close the capacity gap while maintaining feasibility and scalability of the overall network design. For example, it has recently been shown [ColMO06, RKCE04] that when correlated sources are broadcast across a network, separation of the distributed data compression from the channel coding at the encoders and decoders does not in general achieve capacity. However, separate distributed compression and channel encoding with joint source-channel decoding does achieve capacity. We plan to explore such ideas for more general source-channel-network designs. An interesting open question here is whether partial joint designs are feasible while providing significant performance gains and, if so, which parts should be jointly designed: the source and channel codes, the channel and network codes, or the source and network codes (source coding for multihop networks). These results could have great practical relevance because source-channel separation at the encoders (which are usually the most energy and resource-constrained - for instance sensor networks) is a very pleasing, modular and robust engineering solution that many network designers would embrace.
Joint source-network coding also naturally exploits arbitrary correlation of sources. Such correlation may be aided by the natural correlation of data in the system (for instance spatially-induced correlation in a sensor setting) or introduced deliberately in a way similar to that in which mirror sites are created. We plan to explore such joint source-network coding based on random code constructions that generalize those of the Slepian-Wolf settings. While the decoding of such codes using traditional methods such as minimum-entropy approaches is NP-complete, our recent results [ColME05] have shown that an asymptotically error-free approach can be implemented using relaxation methods that yield polynomial-time complexity.
Regardless of the optimality of separation, the capacity region of a MANET, once characterized, can be used to optimize end-to-end performance using network-aware application design. In particular, the network capacity region captures the tradeoffs between capacity, energy, and delay for various network parameterizations. The performance metric associated with a given application can then be optimized by finding the best operating point on this tradeoff curve. Thus, network-aware application design entails finding this optimal operating point, which is a nontrivial optimization problem given the dimensions of the capacity region. Our team includes significant expertise in optimization of complex systems, and this expertise will be applied to defining appropriate metrics for simultaneous heterogeneous applications with different QoS requirements as well as optimizing the network operation with respect to these metrics.