In this paper, a new mathematical programming model and assignment algorithms are developed for minimizing the schedule length in adaptive power and adaptive rate link scheduling in spatial-TDMA wireless networks. The underlying problem entails the optimal joint scheduling of transmissions across multi-access communication links combined with the simultaneous allocation of transmit power levels and data rates across active links, while meeting required Signal-to-Interference-plus-Noise Ratio (SINR) levels at intended receivers. We prove that the problem can be modeled as a Mixed Integer-Linear Programming (MILP) and show that the latter yields a solution that consists of transmit power levels that are strongly Pareto Optimal. We note this problem to be NP-complete. For comparison purposes, we employ the MILP formulation for computing the optimal schedule for networks with small number of designated links and limited number of data rate levels. We proceed to develop and investigate a heuristic algorithm of polynomial complexity for solving the problem in a computationally effective manner. The algorithm is based on the construction of a Power Controlled Rate adaptation Interference Graph. The desired schedule is then derived by using a greedy algorithm to construct an independence set from this graph. Based on system analyses, we show, for smaller illustrative networks, the performance behavior realized by the heuristic algorithms to generally be in the 75 percentile of those attained by the optimal schedule. We also show that performance of our heuristic algorithm is on average 20% better than that attained under prior algorithms that were developed for use under fixed transmit power and fixed rate link scheduling.

In this paper, the effect of transmission power on the throughput capacity of finite ad hoc wireless networks, considering a scheduling-based medium access control (MAC) protocol such as time division multiple access (TDMA) and an interference model that is based on the received signal-to-interference-plus-noise ratio (SINR) levels, is analyzed and investigated. The authors prove that independent of nodal distribution and traffic pattern, the capacity of an ad hoc wireless network is maximized by properly increasing the nodal transmission power. Under the special case of their analysis that the maximum transmission power can be arbitrarily large, the authors prove that the fully connected topology (i.e., the topology under which every node can directly communicate with every other node in the network) is always an optimum topology, independent of nodal distribution and traffic pattern. The present result stands in sharp contrast with previous results that appeared in the literature for networks with random nodal distribution and traffic pattern, which suggest that the use of minimal common transmission power that maintains connectivity in the network maximizes the throughput capacity. A linear programming (LP) formulation for obtaining the exact solution to the optimization problem, which yields the throughput capacity of finite ad hoc wireless networks given a nodal transmit power vector, is also derived. The authors' LP-based performance evaluation results confirm the distinct capacity improvement that can be attained under their recommended approach, as well as identify the magnitude of capacity upgrade that can be realized for networks with random and uniform topologies and traffic patterns.

An ad hoc wireless network with n nodes and m source-destination pairs, using a scheduling based medium access control (MAC) protocol such as time division multiple access (TDMA), and a routing mechanism that may be unicast or multicast based, is considered. Under a given nodal transmit power vector, we define the source-destination throughput vector to be achievable if there exists an associated temporal (based on the channel sharing MAC protocol) and spatial (based on the underlying routing mechanism) joint scheduling-routing scheme that yields the throughput vector. In this paper, we analyze and investigate the effect of nodal transmit power vector on the maximum (or supreme) level of a general (real-valued) function of the source-destination throughput levels. We represent the latter supreme level attained under power vector. We also derive a linear programming (LP) formulation for obtaining the exact solution to the optimization problem that yields the throughput capacity of finite ad hoc wireless networks. Our LP based performance evaluation results identify the magnitude of capacity upgrade that can be realized for networks with random topologies and traffic patterns.

In this paper, we develop and investigate a novel power control algorithm (the fair randomized power control algorithm; FRPC) to enhance the throughput level of the slotted Aloha medium access control mechanism. FRPC is developed based on the analysis of the capture effect for which the transmitter captures the channel only if the observed signal-to-interference and noise ratio (SINR) at the receiver is above a certain threshold. We first analyze the sensitivity of the generic randomized power control algorithm with respect to expected value and standard deviation of the power density function. In particular, based on the one-tailed version of Chebyshev's inequality, we derive a closed-form expression for an upper bound on the probability of capture (and an upper bound on the aggregate throughput) in the network. We then apply the latter result to the process of designing the FRPC algorithm for the slotted Aloha MAC mechanism. Our simulation results indicate that the FRPC algorithm leads to significant throughput gain while providing fairness for different mobile users in the system.

In this paper, we develop a new mathematical programming formulation for minimizing the schedule length in ad hoc wireless networks based on the optimal joint scheduling of transmissions across the multi-access communication links and allocation of transmit power levels, while meeting the requirements on the signal-to-interference and noise ratio (SINR) at intended receivers. We prove that the problem can be represented as a mixed integer linear programming (MILP) and show that the latter yields a solution that consists of transmit power levels that are strongly Pareto optimal. We demonstrate that our MILP formulation can be used effectively to derive optimal scheduling and power levels for networks with as many as 30 designated communication links. We exhibit that the MILP formulation can be also effectively solved to provide tight upper and lower bounds (corresponding to an approximation factor /spl Delta/) for the optimum schedule length of networks with as many as 100 designated links. We prove that the integrated link scheduling and power control problem is NP-complete. Consequently, we develop and investigate a heuristic algorithm of polynomial complexity (O|LO|/sup 5/) for solving the problem in a timely and practical manner. Our algorithm is based on the properties of a novel interference graph (the power-based interference graph) that we have introduced. We demonstrate that the frame length of schedules realized by our heuristic schemes reside in the 25 percentile of those attained by the optimal mechanism for randomly generated topologies.

In this paper, we analyze and investigate the effect of transmission power on the throughput capacity of finite ad hoc wireless networks. We prove that, independent of nodal distribution and traffic pattern, the capacity of an ad hoc wireless network is maximized by properly increasing the nodal transmission power. Under the special case of our analysis that the maximum transmission power can be arbitrary large, we prove that the fully connected topology (i.e. the topology under which every node can directly communicate with every other node in the network) is always an optimum topology, independent of nodal distribution and traffic pattern. Our result stands in sharp contrast with previous results that appeared in the literature for networks with random nodal distribution and traffic pattern, which suggest the use of minimal common transmission power that maintains connectivity in the network, showing it to asymptotically achieve a throughput level that is in the order of the throughput capacity. We also derive a linear programming (LP) formulation for calculating the capacity of finite ad hoc wireless networks. Our LP based performance evaluation results confirm the capacity improvement attained under our recommended approach, as well as identify the. magnitude of capacity upgrade that can be realized for networks with random topologies and traffic patterns.

We introduce an ad hoc wireless mobile network that employs a hierarchical networking architecture and uses high and low capacity nodes. We present a topological synthesis algorithm that selects a subset of high capacity nodes to form a backbone network (Bnet). The latter is multi-tiered and consists of interconnected backbone nodes that intercommunicate across higher power (or regular) links, and also makes use of unmanned vehicles, both airborne (UAV) and ground based (UGV). For such a mobile backbone network (MBN), we introduce a protocol, MBNP, to implement the key networking schemes. The MBNP system serves to allocate resources across the network to ensure acceptable user application QoS performance, and also a highly robust backbone-oriented networking architecture. We introduce a new class of on-demand (MBNP-OD) routing algorithms that use the backbone network for selective forwarding of route-request messages, while striving to achieve an efficient MAC layer operation. We enhance these new protocols by incorporating link stability estimates to attain a robust routing operation. To ensure service quality for admitted flows, we introduce flow admission control mechanisms. We present new power control spatial reuse based algorithms for efficient utilization of the net MAC resources through the use of time slot allocations and of CSMA/CA based (IEEE 802.11 type) protocols. We present elements of the protocol and key involved algorithms, and illustrate the advantages offered by the MBNP system.

We consider ad hoc wireless networks that are configured as Mobile Backbone Networks. A hierarchical network architecture is synthesized, consisting of Access Nets (ANets) and Backbone Nets (BNets). Each ANet is managed by a (dynamically elected) Backbone Node (BN) that is equipped with higher capability (transmission and processing) modules. The BNs are chosen from currently active mobile backbone-capable nodes or are represented by (ground and/or airborne) unmanned vehicles (UVs) that are guided into selected positions. We develop and investigate a new joint power controlled medium access control (MAC) algorithm for wireless access nets (ANets). Under our new protocol, the net backbone node instructs the ANet nodes to make power control adjustments while simultaneously allocating to them slots for the requested transmissions of their packets. This algorithm, in contrast to other employed conventional graph-based scheduling algorithms, satisfies the requirement that a minimum signal-to-interference and noise ratio (SINR) is met at all intended receivers. We show our algorithm to lead to a significant increase in the net throughput level by attaining high spatial reuse.

Many published algorithms used for scheduling transmissions in packet radio networks are based on finding maximal independent sets in an underlying graph. Such algorithms are developed under the assumptions of variations of the protocol interference model, which does not take the aggregated effect of interference into consideration. We provide a probabilistic analysis for the throughput performance of such graph based scheduling algorithms under the physical interference model. We show that in many scenarios a significant portion of transmissions scheduled based on the protocol interference model result in unacceptable signal-to-interference and noise ratio (SINR) at intended receivers. Our analytical as well as simulation results indicate that, counter intuitively, maximization of the cardinality of independent sets does not necessarily increase the throughput of a network. We introduce the truncated graph based scheduling algorithm (TGSA) that provides probabilistic guarantees for the throughput performance of the network.