Linear Finite-Field Deterministic Networks With Many Sources and One Destination 1 M. Majid Butt $^{∗}$, Giuseppe Caire$^{†}$, Ralf R. M¨ uller ∗ $^{∗}$Institute of Electronics and Telecommunications, Norwegian University of Science and Technology, Trondheim, Norway $^{†}$Department of Electrical Engineering, University of Southern California, Los Angeles, CA Abstract —We find the capacity region of linear finite-field deterministic networks with many sources and one destination. Nodes in the network are subject to interference and broadcast constraints, specified by the linear finite-field determinis tic model. Each node can inject its own information as well as relay other nodes’ information. We show that the capacity region coincides with the cut-set region. Also, for a specific case o f correlated sources we provide necessary and sufficient cond itions for the sources transmissibility. Given the “deterministi c model” approximation for the corresponding Gaussian network model, our results may be relevant to wireless sensor networks where the sensing nodes multiplex the relayed data from the other nodes with their own data, and where the goal is to decode all data at a single “collector” node. In [5], a simpler deterministic channel is proposed. While this channel model is significantly simpler to analyze, it is able to capture the key aspects of broadcast and interference constraints. For this model, referred to as the linear finite -field deterministic model, [5] determines the capacity for a general relay network with one source and one destination, as well as the multicast capacity with one source, multiple destinations and common information only. Our contribution in this paper builds heavily on the results and techniques of [5] and can be regarded almost as a trivial extension thereof. Nevertheless, to the best of our knowledge and somehow surprisingly, this simple extension has not been reported before. Wireless sensor networks (WSN) consist of many nodes with sensing, computation, and communication capabilities, sharing a common wireless communication channel. In a typical WSN configuration, a large number of nodes measure possibly correlated data and transmit to a single collector node. This network problem is referred to as the “sensor reachback problem” in [1]. In many applications, nodes are energy- limited and the physical distance between each sensing node and the common destination makes the transmission difficult or (energy wise) expensive. We investigate such a scenario where communicating nodes cooperate with each other and act as relays in order to transport their own data along with the data from the other sensing nodes. We consider the “sensor reachback problem” [1] for a linear finite-field deterministic network with arbitrary topology , a sin- gle destination node and independent information at the source nodes. We show that the capacity region for this network is given by the cut-set bound and takes on a very simple and appealing closed-form expression. Also, for a specific sour ces correlation model, we find necessary and sufficient conditio ns for the sources transmissibility. This result reminds closely Theorem 1 of [1], with the following main differences: on one hand, the result of [1] is more general since it applies to general correlated discrete sources observed at the sensor nodes and general noisy channels. On the other hand, our result applies to networks with broadcast and interference constraints while the result of [1] requires “orthogonal” channels, i.e ., with neither broadcast nor interference constraints. Wireless channels differ from their wired line counterpart in two fundamental aspects. On one hand, the wireless channel is a broadcast (shared) medium and the signal from any transmitter is received by potentially many receivers. This is called broadcast constraint. On the other hand, any receiver observes the superposition (linear combination) of signals from possibly many transmitters. This is called interference constraint. The simultaneous presence of these two constraints makes a general wireless network quite difficult to analyze. The multiuser Gaussian channel that models a relay network, unfortunately, has so far escaped a sharp general characteri- zation, even in the simplest case of a Gaussian relay network with a single source, single destination and a single relay [2]. The capacities of Gaussian relay channel and certain discrete relay channels are evaluated in [3] and a lower bound to the capacity of general relay channel is presented. In [4], capacity is determined for a Gaussian relay network when the number of relays is asymptotically large. We expect that the achievability technique for the Gaussian (noisy) relay network proposed in [5] can be generalized to the case of multiple independent sources and a single destination as examined in this paper, so that a scheme that achieves a bounded and fixed gap to the capacity region in the Gaussian case can be found. Also, we believe that a fixed-gap rate- distortion achievable region can be found using independent quantization and Slepian-Wolf binning for the case of cor- related Gaussian sources with mean-squared distortion and Gaussian noisy channels, at least for some specific source correlation model (see [6]), especially matched to the discrete correlated source model considered here. This, however, seems to be a far more involved result since event in the standard case of Gaussian/quadratic separated lossy encoding (that corresponds to the case where the communication network reduces to a set of orthogonal links from the sensor nodes to the destination), a general fixed-gap characterization o f the rate-distortion region is missing [6]. In this work we limit ourselves to the linear finite-field arXiv:1001.2464v1 [cs.IT] 14 Jan 2010 I. INTRODUCTION