Motivated by the fair rate allocation in a multiaccess Gaussian channel, this paper studies the problem of fair rate allocation over a generalized symmetric polymatroid with box constraints. The best-known algorithm for this problem has time complexity O(n5lnO(1)n). In this paper, we present a divide-and-conquer algorithm for this problem with quadratic running time. It is an implementation of a refined decomposing method for the more general separate concave maximization over a polymatroid with box constraints. A key ingredient of the algorithm is a linear-time algorithm for a generalized knapsack problem.

The rate capacity region of an uplink Gaussian channel is a generalized symmetric polymatroid. Practical applications impose additional lower and upper bounds on the rate allocations, which are represented by box constraints. A fundamental scheduling problem over an uplink Gaussian channel is to seek a rate allocation maximizing the weighted sum-rate (MWSR) subject to the box constraints. The best-known algorithm for this problem has time complexity O (n5 lnO(1) n). In this paper, we take a polymatroidal approach to developing a quadratic-time greedy algorithm and a linearithmic-time divide-and-conquer algorithm. A key ingredient of these two algorithms is a linear-time algorithm for minimizing the difference between a generalized symmetric rank function and a modular function after a linearithmic-time ordering.

Consider a set of point-to-point communication requests in a multi-channel multihop wireless network, each of which is associated with a traffic demand of at most one unit of transmission time, and a weight representing the utility if its demand is fully met. A subset of requests is said to be schedulable without spectral splitting if they can be scheduled within one unit of time subject to the constraint each request is assigned with a unique channel throughout its transmission. This paper develops efficient and provably good approximation algorithms for finding a maximum-weighted subset of communication requests schedulable without spectral splitting.

Maximum multiflow and maximum concurrent mul-tiflow in multi-channel multi-radio (MC-MR) wireless networks have been well-studied in the literature. They are NP-hard even in single-channel single-radio (SC-SR) wireless networks when all nodes have uniform (and fixed) interference radii and the positions of all nodes are available. While they admit a polynomial-time approximation scheme (PTAS) when the number of channels is bounded by a constant, such PTAS is quite infeasible practically. Other than the PTAS, all other known approximation algorithms, in both SC-SR wireless networks and MC-MR wireless networks, resorted to solve a polynomial-sized linear program (LP) exactly. The scalability of their running time is fundamentally limited by the general-purposed LP solvers. In this paper, we first introduce the concept of interference costs and prices of a path and explore their relations with the maximum (concurrent) multiflow. Then we develop purely combinatorial approximation algorithms which compute a sequence of least interference-cost routing paths along which the flows are routed. These algorithms are faster and simpler, and achieve nearly the same approximation bounds known in the literature.

Maximizing the wireless network capacity under physical interference model is notoriously hard due to the nonlocality and the additive nature of the wireless interference under the physical interference model. This problem has been extensively studied recently with the achievable approximation bounds progressively improved from the linear factor to logarithmic factor. It has been a major open problem whether there exists a constant-approximation approximation algorithm for maximizing the wireless network capacity under the physical interference model. In this paper, we improve the status quo for the case of linear transmission power assignment, which is widely adopted due to its advantage of energy conservation. By exploring and exploiting the rich nature of the wireless interference with the linear power assignment, we develop constant-approximation algorithms for maximizing the wireless network capacity with linear transmission power assignment under the physical interference model, in both the unidirectional mode and the bidirectional mode.

Static greedy link schedulings have much simpler implementation than dynamic greedy link schedulings such as Longest-queue-first (LQF) link scheduling. However, its stability performance in multi-channel multi-radio (MC-MR) wireless networks is largely under-explored. In this paper, we present a stability subregion with closed form of a static greedy link scheduling in MC-MR wireless networks under the 802.11 interference model. By adopting some special static link orderings, the stability subregion is within a constant factor of the stable capacity region of the network. We also obtain constant lower bounds on the throughput efficiency ratios of the static greedy link schedulings in some special static link orderings.

This paper addresses the joint selection and power assignment of a largest set of given links which can communicate successfully at the same time under the physical interference model in the duplex (i.e. bidirectional) mode. For the special setting in which all nodes have unlimited maximum transmission power, Halldorsson and Mitra [5] developed an approximation algorithm with a huge constant approximation bound. For the general setting in which all nodes have bounded maximum transmission power, the existence of constant approximation algorithm remains open. In this paper, we resolve this open problem by developing an approximation algorithm which not only works for the general setting of bounded maximum transmission power, but also has a much smaller constant approximation bound.

Longest-queue-first (LQF) link scheduling is a greedy link scheduling in multihop wireless networks. Its stability performance in single-channel single-radio (SC-SR) wireless networks has been well studied recently. However, its stability performance in multi-channel multi-radio (MC-MR)wireless networks is largely under-explored. In this paper, we present a stability subregion with closed form of the LQF scheduling in MC-MR wireless networks, which is within a constant factor of the network stability region. We also obtain constant lower bounds on the efficiency ratio of the LQF scheduling in MC-MR wireless networks under the 802.11 interference model or the protocol interference model.

This paper studies maximum multiflow (MMF) and maximum concurrent multiflow (MCMF) in muliti-channel multi-radio multihop wireless networks under the 802.11 interference model or the protocol interference model. We introduce a fine-grained network representation of multi-channel multi-radio multihop wireless networks and present some essential topological properties of its associated conflict graph. By exploiting these properties, we develop practical polynomial approximation algorithms for MMF and MCMF with constant approximation bounds regardless of the number of channels and radios. Under the 802.11 interference model, their approximation bounds are at most 20 in general and at most 8 with uniform interference radii; under the protocol interference model, if the interference radius of each node is at least c times its communication radius, their approximation bounds are at most 2 (⌈π/ arcsin c-1/2c⌉ + 1). In addition, we also prove that if the number of channels is bounded by a constant (which is typical in practical networks), both MMF and MCMF admit a polynomial-time approximation scheme under the 802.11 interference model or under the protocol interference model with some additional mild conditions.

Longest Queue First (LQF) is a well-known link scheduling strategy in multihop wireless networks. Its throughput efficiency ratio was shown to be exactly the local pooling factor (LPF) of the multihop wireless network in a recent seminar work by Joo et al.. Under the 802.11 interference model with uniform interference radii, the LPF of a multihop wireless network was known to be at least 1/6. However, little is known about the LPF of a multihop wireless network under the 802.11 interference model with arbitrary interference radii or under the protocol interference model. In this paper, we derive constant lower bounds on LPFs of these multihop wireless networks. Specifically, under the 802.11 interference model with arbitrary interference radii, the LPF is at least 1/16. Under the protocol interference model, if the communication radius of each node is at most c times its interference radius for some c <; 1, then the LPF is at least 1/ (2 ⌈π/ arcsin 1-c/2⌈ - 1)).

Link scheduling is a fundamental design issue in multihop wireless networks. All existing link scheduling algorithms require the precise information of the positions, and/or communication/interference radii of all nodes. For practical networks, it is not only difficult or expensive to obtain these parameters, but also often impossible to get their precise values. The link scheduling determined by the imprecise values of these parameters may fail to guarantee the same approximation bounds of the link scheduling determined by precise values. Therefore, the existing link scheduling algorithms lack performance robustness. In this paper, we propose a robust link scheduling, which can be easily computed with only the information on whether a given pair of links have conflict or not and therefore is robust. In addition, our link scheduling does not compromise the approximation bound and indeed sometimes can achieve better approximation bound. Particularly, under the 802.11 interference model, its approximation bound is 16 in general and 6 with uniform interference radii, an improvement over the respective best-known approximation bounds 23 and 7.

One of the most fundamental task of wireless networks is to provide coverage of a set of targets. Suppose that all nodes and targets lie in a plane, and all nodes have circular coverage ranges of arbitrary radii. The problem Minimum Wireless Cover (MWC) seeks the fewest nodes to cover the targets. If all nodes are associated with some positive prices, the problem Cheapest Wireless Cover (CWC) seeks a cheapest set of nodes to cover the targets. If all nodes have bounded lives, the problem Max-Life Wireless Cover (MLWC) seeks wireless coverage schedule of maximum life subject to the life constraints of individual nodes. In this paper, we present a polynomial time approximation scheme (PTAS) for MWC, and two randomized 2O(log* n)-approximation algorithms for CWC and MLWC respectively, where n is the number of nodes, and log* n is the iterated logarithm of n with base 2.

Beaconing is a primitive communication task in which every node locally broadcasts a packet to all its neighbors within a fixed distance. Assume that all communications proceed in synchronous time-slots and each node can transmit at most one fixed-size packet in each time-slot. The problem Minimum-latency beaconing schedule (MLBS) in multihop wireless networks seeks a shortest schedule for beaconing subject to the interference constraint. MLBS has been intensively studied since the mid-1980s, but all assume the protocol interference model with uniform interference radii. In this paper, we first present a constant-approximation algorithm for MLBS under the protocol interference model with arbitrary interference radii. Then, we develop a constant-approximation algorithm for MLBS under the physical interference model. Both approximation algorithms have efficient implementations in a greedy first-fit manner.