Search

Wireless communications have gained much currency in the last few decades. In this thesis we present results regarding several wireless communication systems, in particular, wireless networks. For some time now, it has been known that in an ad hoc network in which nodes share the wireless medium, and the connection strengths between nodes follow a distance-based decay law, the throughput scales like O(√n), where n is the number of nodes. In Chapter 2 we introduce randomness in the connection strengths and examine the effects of this on the throughput. We assume that all the channels are drawn independently from a common distribution and are not governed by a distance-decay law. It turns out that the aggregate information flow depends strongly on the distribution from which the channel strengths are drawn. For certain distributions, a throughput of n/(log n)d with d>0 is possible, which is a significant improvement over the O(√n) results known previously. In Chapter 3, we generalize the network model to two-scale networks. This model incorporates the distance-decay law for nodes that are separated by large distances, while maintaining randomness in close neighborhoods of a node. For certain networks, we show that a throughput of the form n1/t-1/log2n is achievable, where t>2 is a parameter that depends on the distribution of the connection at the local scale and is independent of the decay law that operates at a global scale. In Chapter 4, we consider a model of an erasure wireless network, in which every node is connected to certain other nodes by erasure links, on which packets or bits are lost with some probability and received accurately otherwise. Each node is constrained to send the same message on all outgoing channels, thus incorporating the broadcast feature, and we assume that there is no interference in the network, other than through the possible correlation of erasure occurrences. For such networks and in certain multicast scenarios, we obtain the precise capacity region. This region has a nice max-flow, min-cut interpretation and can be achieved using linear codes. We do require the side-information regarding erasure locations on all links to be available to the destinations. Thus, we have the capacity region for a non-trivial class of wireless networks. Recent results for wireline networks show that in several scenarios, it is optimal to operate these networks by making each link error-free. In Chapter 5, we consider Gaussian networks with broadcast and interference, and erasure networks with broadcast, and show that in the presence of these wireless features, it is suboptimal to make each link or sub-network error-free. We then consider these networks with the constraint that each node is permitted to either retransmit the received information or decode it and retransmit the original source information. We propose a greedy algorithm that determines the optimal operation for each node, such that the rate achievable at the destination is maximized. Further, we present decentralized implementations of this algorithm that allow each node to determine for itself the optimal operation that it needs to perform. In Chapter 6, we consider a point-to-point communication system, involving multiple antennas at the transmitter and the receiver. These systems can give high data rates provided we can perform optimum, or maximum-likelihood, decoding of the received message. This problem typically reduces to that of finding the lattice point closest to a given point x in N-dimensional space. This is an integer least-squares problem and is NP-complete. The sphere decoder is an algorithm that performs decoding in an efficient manner by searching for the closest point only within a spherical region around x. In Chapter 6, we propose an algorithm that performs decoding in a sub-optimal manner by pruning the search region based on the statistics of the problem. This algorithm offers significant computational savings relative to the sphere decoder and allows us to tradeoff performance with computational complexity. Bounds on the error performance as well the complexity are presented.

We propose and analyze two models of networks in which pairs of nodes communicate over a shared wireless medium. We are interested in the maximum total aggregate traffic flow that is possible through the network. Our first model differs substantially from most existing models in that the channel connections in our network are entirely random: we assume that, rather than being governed by geometry and a decay law, the strength of the connections between nodes is drawn independently from a common distribution. The next model is more general and works at two scales. At a local scale, characterized by nodes being within a distance r from each other, connections are drawn independently from some distribution, but at a global scale, characterized by nodes being further apart from each other than a distance r, channel connections are governed by a Rayleigh distribution, with the power satisfying a distance-based decay law. For both models we show that an appropriate distribution for the channel strengths and other parameters can give a throughput that scales almost linearly in the number of nodes of the network. This is a significant improvement over the square-root scaling that has been shown in several previous works.

In this paper, we consider a special class of wireless networks, called wireless erasure networks. In these networks, each node is connected to a set of nodes by independent erasure channels. The network model incorporates the broadcast nature of the wireless environment in that each node sends out the same signal on its outgoing channels. However, we assume there is no interference in reception. In this paper we first look at the single source single destination unicast problem. We obtain the capacity under the assumption that erasure locations on all the links of the network are provided to the destination. It turns out that the capacity has a nice max-flow min-cut interpretation. The definition of cut-capacity in these network is such that it incorporates the broadcast property of the wireless medium. In the second part of the paper, a time-sharing scheme for broadcast problems over these networks is proposed and its achievable region is analyzed. We show that for some special cases, this time-sharing scheme is optimal.

We determine the capacity of a certain class of wireless erasure relay networks. We first find a suitable definition for the "cut-capacity" of erasure networks with broadcast at transmission and no interference at reception. With this definition, a maxflow mincut capacity result holds for the capacity of these networks.

In this paper we show that to achieve capacity of a wireless network, the global structure of the network should be considered. In other words, achieving capacity on the sub-networks of a wireless network does not guarantee achieving capacity globally. We illustrate this fact by some examples. Then we consider packet erasure wireless networks with limited sets of operations allowed at each node. We pose some interesting problems related to the optimal achievable rate of these networks and provide partial answers to some of them.