Wireless Networks: New Models and Results

Citation

Gowaikar, Radhika (2007) Wireless Networks: New Models and Results. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/9652-QK53. https://resolver.caltech.edu/CaltechETD:etd-10032006-113124

Abstract

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 n^1/t-1/log²n 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.

Thesis Files