## Local View Capacity of Networks

** Driving Question**: The operational capacity of most networks is often much lower than the information theoretic predictions. A key element of any information theoretic analysis is the amount and type of information about the network which is either implicitly or explicitly made available to the network nodes. For example, often the nodes not only know the network topology, but channel statistics and/or channel realizations of not only their one-hop neighbours but also nodes further away from them. Implicitly, the network size is assumed to be constant and known to all nodes.

On other hand, operational networks cannot make any of the above simplifying assumptions. Hence the protocol design has to account for unknown and time-varying nature of many network parameters like size, channels, queues etc. All the protocols consume valuable network resources (time/bandwidth/power) which one would ideally want to use to send data, not control information. While it is clear that we cannot escape "protocol overhead" in some form, the fundamental question is

**: Seen from the perspective of any node in the network, whether it is an infrastructure node (like a base-station or access point) or a mobile node, the knowledge it has about the network is limited. And often it is limited to be local. The locality makes sense for (i) since the local information is the easiest to measure and pass around, and (ii) the local parameters impact the success and rate of communication the most (one would guess). As a result, in all practical wireless networks, no node has a**

__Uncertainity Models__*global view*of the network. Instead the nodes have a

*local view*which are

*mismatched*from each other's. So in the figure below, Node~A's knowledge about the network is different from Node B and C's view of the network.

This mismatched view of the network is an important but poorly understood aspect in theory. A well-studied example of this mismatched information is the hidden node problem in wireless networks. The view mismatch can be related to any kind of information - channel states, number of nodes, statistics of the links, queue states, to name a few.

The seeds of mismatched local views can be traced to our prior work in understanding power control over noisy feedback links, which led to transmitter and receiver being mismatched in their knowledge about the channel (see Asilomar 2008, IEEE IT 2010 and IEEE IT 2011 papers).

** Local View Capacity**: In our initial investigation of the work, we formalized the h-hop uncertainty model, where each node only knows about the channels which are h-hops away from it. This model is simple to specify (only one parameter h) and can be motivated by message passing algorithm (which is essentially every protocol). We noted that even in this simple model, the key essence of the problem can be captured - mismatched knowledge means that nodes cannot align their decisions and as a result, these distributed decisions can lead to significantly reduced performance.

- V. Aggarwal, Y. Liu and A. Sabharwal, Message Passing in Distributed Wireless Networks, ISIT 2009.
- J. Xiao, V. Aggarwal, A. Sabharwal and Y. Liu, Interference networks with local view: A distributed optimization approach, Allerton 2009.
- V. Aggarwal, S. Avestimehr and A. Sabharwal, Distributed Universally Optimal Strategies for Interference Channels with Partial Message Passing, Allerton 2009.
- V. Aggarwal, Y. Liu and A. Sabharwal, Sum-capacity of Interference Channels with a Local View: Impact of Distributed Decisions, IEEE Transactions on Information Theory, 58(3), March 2012.

*normalized sum-capacity*- which measures the fraction of global-view capacity which can be achieved with an uncertainty model. This allows quantification of the loss due to mismatched local views. An important by-product of studying normalized sum-capacity is that it is easier to find than actual capacity of the network.

- V. Aggarwal, S. Avestimehr and A. Sabharwal, How (Information Theoretically) Optimal Are Distributed Decisions?, IEEE CISS, Mar 2010.
- V. Aggarwal, S. Avestimehr and A. Sabharwal, Normalized Sum-Capacity of Interference Networks with Partial Information, IEEE ISIT, 2010
- A. Vahid, V. Aggarwal, S. Avestimehr, and A. Sabharwal, On the Capacity of Multi-Hop Wireless Networks with Partial Network Knowledge, Proc. Allerton, 2010.
- V. Aggarwal, S. Avestimehr and A. Sabharwal, On Achieving Local View Capacity Via Maximal Independent Graph Scheduling, IEEE Transactions on Information Theory, 57(5), May 2011.
- A. Vahid, V. Aggarwal, S. Avestimehr and A. Sabharwal, Wireless Network Coding with Local Network Views: Coded Layer Scheduling,submitted to IEEE Transactions on Information Theory, June 2011.

While we continue studying the normalized sum-capacity, we have also made in-roads in defining and studying the whole capacity region with local views. It turns out that local view capacity requires a re-thinking of the definition of capacity region.

- D. Kao and A. Sabharwal, On Capacity Regions of Interference Channels with Mismatched Local Views, submitted to IEEE Transactions on Information Theory, October 2011.