While current cellular networks are based essentially on one-to-many and many-to-one single-hop subnets and cope with inter-cell interference by careful centralized resource planning, future wireless networks must consider heterogeneous environments characterized by user-deployed and user-operated infrastructure in which multiple flows and multiple hops will play an increasingly relevant role. Indeed, such networks are expected to open doors to trillions of dollars of e-commerce, while also providing vast amounts of easily accessible knowledge to the public. Developing a fundamental understanding of multihop multiflow wireless networks is therefore critically important at this time.
This exploratory project will seek to discover the fundamentals of such networks by obtaining their information theoretic capacity in an approximated sense. It is expected that scalable and extensible solutions are possible for such networks ranging from the seemingly simple ones involving two hops and two flows to apparently more complex ones involving multiple hops and more than two flows with arbitrary connectivity. In so demonstrating, multiple metrics will be employed. These metrics in the increasing order of accuracy in the high signal-to-noise ratio regime are (a) the fundamental limit on the available signaling (temporal/spectral/spatial) dimensions of the network, (b) the fundamental limit on the available signaling and signal-level dimensions, and (c) the capacity to within a (universal) constant number of bits independently of channel parameters.
While current cellular networks are based essentially on one-to-many and many-to-one single-hop subnets and cope with inter-cell interference by careful centralized resource planning, future networks must consider heterogeneous environments characterized by user-deployed and user-operated components. Because of the lack of infrastructure, or in order to exploit a much denser spatial reuse, multiple flows and multiple hops will play a more and more relevant role. Therefore, laying down a fundamental understanding of multihop multiflow wireless networks is critically important at this time. Intellectual Merit: Solving the capacity of multihop multiflow wireless networks in the strict Shannon sense is arguably the holy grail of network information theory and a goal that is likely to challenge the skill and ingenuity of information theorists well into the foreseeable future. In this project we have discovered some fundamentals features of such networks and have characterized their capacity in an approximated sense in a number of important special cases. We demonstrated that scalable and extensible solutions are indeed possible for the problem of approximating the capacity of wireless networks ranging from seemingly simple networks involving two hops and two flows to apparently more complex ones involving multiple hops and more than two flows with arbitrary connectivity. In order to achieve these goals, we have focused on the fundamental limit on the available signaling dimensions (temporal/spectral/spatial), also known as the degrees of freedom. The main programmatic goal in this project was to demonstrate that through the characterization of the degrees of freedom, the fundamental understanding the fundamental understanding of multi-hop and multi-flow can be significantly advanced. We believe that this goal was indeed achieved. Broader Impact: At the societal and economic level, wireless multihop multiflow networks will play a more and more preeminent role in bridging the digital divide and providing broadband to rural areas in developing nations, open doors to trillions of dollars of e-commerce, provide vast amounts of easily accessible knowledge to the public, dramatically reduce operational costs to increase efficiency of most organizations, and save lives by providing much needed emergency communications in the wake of natural (or man-made) disasters. Wireless communication networks are in fact now universally considered as the solution to a low-cost, wide-area communication backbone, with possibly self-powered (e.g., solar/wind) nodes. The results of this project have illuminated a number of fundamental facts about the performance of multi hop multi flow networks, with potentially transformative long-term effects on the design guidelines for radically more efficient systems. By characterizing targeted network topologies in terms of their approximate capacity, we extracted general guidelines for larger and more complex topologies that can be applied to the design of the future generation of multihop multiflow wireless networks, to meet at once the demand for higher data rates, better connectivity, and greater energy efficiency. PI Varanasi and his student Vaze (supported under this award) published the following papers which contain detailed information on the results obtained under this project and how they are related to its overall objective. C. S. Vaze and M. K. Varanasi "Beamforming and aligned interference neutralization achieve the degrees of freedom of the MIMO 2x2x2 interference network," Proc. Information Theory and Applications (ITA) Workshop, UCSD, San Diego, CA (invited), Feb. 5-10, 2012, pp. 199 - 203. under preparation for submission as a journal paper. C. S. Vaze and M. K. Varanasi "The degree-of-freedom regions of MIMO broadcast, interference, and cognitive radio channels with no CSIT" IEEE Trans. Inform. Th., Vol. 58, No. 8, Aug. 2012, pp. 5354 - 5374. C. S. Vaze and M. K. Varanasi, "The Degrees of Freedom of the 2 x 2 x 2 Interference Network with Delayed CSIT and with Limited Shannon Feedback," Proc. 49th Allerton Conf. Commun. Cntrl. Comput. Sept. 2011. C. S. Vaze and M. K. Varanasi, "Retro-cooperative interference alignment and the DoF region of the (M,N)^3 interference network with limited Shannon feedback," Proc. Conf. Inform. Sc. Systems, Princeton University, Princeton, NJ, Mar. 21-23, 2012 (invited). C. S. Vaze and M. K. Varanasi, "The degrees of freedom regions of two-unicast multi-hop layered MIMO interference networks with limited Shannon feedback," submitted, IEEE Trans. Inform. Th., Jul. 2012. Another remarkable consequence of this collaborative EAGER project, PI Varanasi and his other collaborators on this project teamed up and submitted a follow-on proposal for a Medium Collaborative NSF-CIF Project, which builds on the findings of this project and aims at achieving even more ambitious goals. This proposal. entitled ``CIF: Medium: Collaborative Research: Multihop Multiflow Wireless Networks: A Treasure Hunt,'' was funded in 2012 and it is now under execution.
