The problem of determining what links can be simultaneously activated in a wireless network such that a signal-to-interference-and-noise (SINR) constraint is satisfied at all receivers is considered. The term "feasible matching" is introduced to describe a set of (transmitter, receiver) pairs for which there exists some set of transmit powers which can simultaneously meet the SINR requirements at the receivers. Given disjoint equally sized sets of transmitters and receivers, it is shown that when the SINR requirement at the receivers is greater than 1, no more than one feasible matching between the transmitters and the receivers exists. Sufficient conditions are provided under which certain broad classes of matchings in a network are guaranteed to be feasible; for example all matchings involving k or fewer links. The application of these results to ad hoc wireless networks and to scheduling is discussed.

The problem of determining a minimal length schedule to satisfy given link demands in a wireless network is considered. Links are allowed to be simultaneously active if no node can simultaneously transmit and receive, no node can transmit to or receive from more than one node at a time, and a given signal-to-interference and noise ratio (SINR) is exceeded at each receiver when transmitters use optimally chosen transmit powers. We show that a) the general problem is at least as hard as the MAX-SIR-MATCHING problem, which is easier to describe and b) when the demands have a superincreasing property the problem is tractable.

Scheduling is important in wireless networks for two reasons. First, a schedule of minimum length provides an upper bound on the network's throughput. Second, scheduling is necessary to avoid collisions. Collisions cost energy, making them undesirable in wireless networks whose nodes have limited energy. To produce good link schedules we need large activation sets, sets of links, which can be used concurrently. We call these "feasible matchings". The larger a matching, greater is the parallelism, and the shorter the schedule. In this work, we prove theorems that show how to infer whether certain sets of links are feasible or not, without actually computing eigenvalues.

In this paper, we address two problems associated with static ad hoc wireless networks; methods of saving energy during a deployment of the nodes, and efficient methods of performing adjacent neighbor discovery. To meet these goals we introduce a family of "birthday protocols"which use random independent transmissions to discover adjacent nodes. Various modes of the birthday protocol are used to solve the two problems. We provide a mathematical model and analysis of two modes of the protocol and are led to a third mode which is the probabilistic analog of the deterministic round robin scheduling algorithm. We show by analysis and simulation that the birthday protocols are a promising tool for saving energy during the deployment of an ad hoc network as well as an efficient and flexible means of having the nodes discover their neighbors