An assumption that researchers have often used to model interference in a wireless network is the unit disk graph model. While many theoretical results and performance guarantees have been obtained under this model, an open research direction is to extend these results to hypergraph interference models. Motivated by recent results that the worst-case performance of the distributed maximal scheduling algorithm is characterized by the interference degree of the hypergraph, in the present work we investigate properties of the interference degree of the hypergraph and the structure of hypergraphs arising from physical constraints. We show that the problem of computing the interference degree of a hypergraph is NP-hard and we prove some properties and results concerning this hypergraph invariant. We investigate which hypergraphs are realizable, i.e. which hypergraphs arise in practice, based on physical constraints, as the interference model of a wireless network. In particular, a question that arises naturally is: what is the maximal value of$r$such that the hypergraph$K_{1,r}$is realizable? We determine this quantity for various integral and nonintegral values of the path loss exponent of signal propagation. We also investigate hypergraphs generated by line networks.

It is shown that the performance of the maximal scheduling algorithm in wireless ad hoc networks under the hypergraph interference model can be further away from optimal than previously known. The exact worst-case performance of this distributed, greedy scheduling algorithm is analyzed.

Consider a wireless network where each communication link has a minimum bandwidth quality-of-service requirement. Certain pairs of wireless links interfere with each other due to being in the same vicinity, and this interference is modeled by a conflict graph. Given the conflict graph and link bandwidth requirements, the objective is to determine, using only localized information, whether the demands of all the links can be satisfied. At one extreme, each node knows the demands of only its neighbors; at the other extreme, there exists an optimal, centralized scheduler that has global information. The present work interpolates between these two extremes by quantifying the tradeoff between the degree of decentralization and the performance of the distributed algorithm. This open problem is resolved for the primary interference model, and the following general result is obtained: if each node knows the demands of all links in a ball of radius d centered at the node, then there is a distributed algorithm whose performance is away from that of an optimal, centralized algorithm by a factor of at most (2d+3)/(2d+2). The tradeoff between performance and complexity of the distributed algorithm is also analyzed. It is shown that for line networks under the protocol interference model, the row constraints are a factor of at most 3 away from optimal. Both bounds are best possible.

Universally decodable matrices (UDMs) can be used for coding purposes when transmitting over slow fading channels. These matrices are parameterized by positive integers L and N and a prime power q. The main result of this correspondence is that the simple condition L = q + 1 is both necessary and sufficient for (L, N, q)-VDMs to exist. The existence proof is constructive and yields a coding scheme that is equivalent to a class of codes that was proposed by Rosenbloom and Tsfasman. Our work resolves an open problem posed recently in the literature.

An understanding of the interaction between the channel and the signal space is key to reliable communication. Multipath fading channels exhibit inherent diversity that can be exploited via appropriate signaling and reception. We develop a virtual multiple-input multiple-output framework for characterizing single-transmitter single-receiver multipath fading channels, where the virtual multiple inputs and outputs are created by the dimensions of the signaling scheme. The essence of the framework is a representation of the system with respect to appropriately chosen basis waveforms for the signal space that expose the inherent structure of the channel. The structure makes it possible to derive closed-form expressions for ergodic and outage capacity for a variety of transceivers and to design novel transceivers. In many cases, the analysis clearly reveals the key factors that affect system performance. We provide new capacity expressions for a variety of transceivers. In particular, by analyzing particular transceivers, we provide new expressions that bound the outage capacity performance of the multipath channel. A novelty of this work lies in being able to apply codes developed for orthogonal frequency-division multiplexing systems and multiple antenna systems to existing code-division multiple-access-based systems.