TY - JOUR
T1 - On achieving local view capacity via maximal independent graph scheduling
AU - Aggarwal, Vaneet
AU - Avestimehr, A. Salman
AU - Sabharwal, Ashutosh
N1 - Funding Information:
Manuscript received April 30, 2010; revised October 13, 2010; accepted January 10, 2011. Date of current version April 20, 2011. V. Aggarwal was with the Department of Electrical Engineering, Princeton University, Princeton, NJ, when this work was carried out. V. Aggarwal was supported in part by Princeton University’s Porter Ogden Jacobus Fellowship. A. S. Avestimehr was supported in part by the NSF CAREER award 0953117. A. Sabharwal was supported in part by the NSF under grants CNS 1012921 and CCF 0635331. This paper was presented in part at the Allerton Conference on Communication, Control, and Computing 2009; in part at the IEEE Asilomar Conference on Signals, Systems, and Computers 2009; in part at the IEEE Conference on Information Sciences and Systems 2010; and in part at the IEEE International Symposium on Information Theory 2010.
PY - 2011/5
Y1 - 2011/5
N2 - "If we know more, we can achieve more." This adage also applies to communication networks, where more information about the network state translates into higher sum-rates. In this paper, we formalize this increase of sum-rate with increased knowledge of the network state. The knowledge of network state is measured in terms of the number of hops, h, of information available to each transmitter and is labeled as h-local view. To understand how much capacity is lost due to limited information, we propose to use the metric of normalized sum-capacity, which is the h -local view sum-capacity divided by global-view sum capacity. For the cases of one and two-local view, we characterize the normalized sum-capacity for many classes of deterministic and Gaussian interference networks. In many cases, a scheduling scheme called maximal independent graph scheduling is shown to achieve normalized sum-capacity. We also show that its generalization for 1-local view, labeled coded set scheduling, achieves normalized sum-capacity in some cases where its uncoded counterpart fails to do so.
AB - "If we know more, we can achieve more." This adage also applies to communication networks, where more information about the network state translates into higher sum-rates. In this paper, we formalize this increase of sum-rate with increased knowledge of the network state. The knowledge of network state is measured in terms of the number of hops, h, of information available to each transmitter and is labeled as h-local view. To understand how much capacity is lost due to limited information, we propose to use the metric of normalized sum-capacity, which is the h -local view sum-capacity divided by global-view sum capacity. For the cases of one and two-local view, we characterize the normalized sum-capacity for many classes of deterministic and Gaussian interference networks. In many cases, a scheduling scheme called maximal independent graph scheduling is shown to achieve normalized sum-capacity. We also show that its generalization for 1-local view, labeled coded set scheduling, achieves normalized sum-capacity in some cases where its uncoded counterpart fails to do so.
KW - Coded set scheduling
KW - interference network
KW - local view
KW - maximal independent graph scheduling
KW - maximal independent set scheduling
KW - normalized sum-capacity
KW - normalized sum-rate
UR - http://www.scopus.com/inward/record.url?scp=79955498876&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79955498876&partnerID=8YFLogxK
U2 - 10.1109/TIT.2011.2119630
DO - 10.1109/TIT.2011.2119630
M3 - Article
AN - SCOPUS:79955498876
SN - 0018-9448
VL - 57
SP - 2711
EP - 2729
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 5
M1 - 5752418
ER -