UC San Diego

This thesis considers three problems arising in the study of network communications. The first two relate to the use of network coding, while the third deals with wireless sensor networks. In a traditional communications network, messages are treated as physical commodities and are routed from sources to destinations. Network coding is a technique that views data as information, and thereby permits coding between messages. Network coding has been shown to improve performance in some networks. The first topic considered in this thesis is the routing capacity of a network. We formally define the routing and coding capacities of a network, and determine the routing capacity for various examples. Then, we prove that the routing capacity of every network is achievable and rational, we present an algorithm for its computation, and we prove that every rational number in (0, 1] is the routing capacity of some solvable network. We also show that the coding capacity of a network is independent of the alphabet used. The second topic considered is the network coding capacity under a constraint on the total number of nodes that can perform coding. We prove that every non-negative, monotonically non-decreasing, eventually constant, rational-valued function on the non- negative integers is equal to the capacity as a function of the number of allowable coding nodes of some directed acyclic network. The final topic considered is the placement of relays in wireless sensor networks. Wireless sensor networks typically consist of a large number of small, power-limited sensors which collect and transmit information to a receiver. A small number of relays with additional processing and communications capabilities can be strategically placed to improve system performance. We present an algorithm for placing relays which attempts to minimize the probability of error at the receiver. We model communication channels with Rayleigh fading, path loss, and additive white Gaussian noise, and include diversity combining at the receiver. For certain cases, we give geometric descriptions of regions of sensors which are optimally assigned to the same, fixed relays. Finally, we give numerical results showing the output and performance of the algorithm