Towards an information theory of large networks: An achievable rate region

Abstract—We study communication networks of arbitrary size and topology and communicating over a general vector discrete memoryless channel (DMC). We propose an information-theoretic constructive scheme for obtaining an achievable rate region in such networks. Many well-known capacity-defining achievable rate re-gions can be derived as special cases of the proposed scheme. A few such examples are the physically degraded and reversely de-graded relay channels, the Gaussian multiple-access channel, and the Gaussian broadcast channel. The proposed scheme also leads to inner bounds for the multicast and allcast capacities. Applying the proposed scheme to a specific wireless network of nodes located in a region of unit area, we show that a transport ca-pacity of ( ) bit-meters per second (bit-meters/s) is feasible in a certain family of networks, as compared to the best possible trans-port capacity of ( ) bit-meters/s in [16], where the receiver capabilities were limited. Even though the improvement is shown for a specific class of networks, a clear implication is that designing and employing more sophisticated multiuser coding schemes can provide sizable gains in at least some large wireless networks. Index Terms—Discrete memoryless channels (DMCs), Gaussian channels, multiuser communications, network information theory, relay networks, transport capacity, wireless networks. I