The task of estimating path available bandwidth is difficult but paramount for QoS routing in supporting bandwidth-demanding traffic in multirate and multihop wireless ad hoc networks. The multirate capability and the impact of background traffic has not been carefully studied for the problem of estimating path available bandwidth in prior works. In this paper, we develop a theoretical model for estimating the available bandwidth of a path by considering interference from both background traffic and traffic along the path. We show that the clique constraint widely used to construct upper bounds does not hold any more when links are allowed to use different rates at different time. In our proposed model, traditional clique is coupled with rate vector to more properly characterize the conflicting relationships among links in wireless ad hoc networks where time-varying link adaption is used. Based on this model, we also investigate the problem of joint optimization of QoS routing and link scheduling. Several routing metrics and a heuristic algorithm are proposed. The newly proposed conservative clique constraint performs the best among the studied metrics in estimating available bandwidth of flows with background traffic.

Microeconomics-inspired spectrum auctions can effectively improve the spectrum utilization for wireless networks to satisfy the ever increasing service demands. Considering the spatial reuse, the bidding nodes without mutual interference are grouped as virtual bidders competing for the spectrum bands, which turns a multi-winner spectrum auction into a traditional single-winner auction. To make the participating nodes bid truthfully, strategy-proof auctions are exploited to allocate the vacant spectrum bands. However, how to fairly allocate the profits of the virtual bidder among the winning bidders is still an imperative problem to solve. In this paper, we propose a shapley value based profit allocation (SPA) to distribute the profit among the bidding nodes according to their marginal contributions, which are both from helping the virtual bidder to win the auction and from generating the revenue during the auction period. Our simulation and analysis show that SPA can effectively integrate the contributions from the two stages in the spectrum auction and fairly allocate the profit among the winning bidders.

In this paper, we derive a theoretical model to calculate the available bandwidth of a path and study its upper and lower bounds with background traffic. We show that the clique constraint widely used to construct upper bounds does not hold any more when links are allowed to use different rates at different time. In our proposed model, traditional clique is coupled with rate vector to more properly characterize the conflicting relationships among links in wireless sensor networks where time-varying link adaption is used. Based on the model, we also investigate the problem of joint optimization of QoS routing and propose several routing metrics. The newly proposed conservative clique constraint performs the best among the studied metrics in estimating available bandwidth of flows with background traffic.

In this paper, we solve the problem of a joint optimal design of congestion control and wireless MAC-layer scheduling using a column generation approach with imperfect scheduling. We point out that the general subgradient algorithm has difficulty in recovering the time-share variables and experiences slower convergence. We first propose a two-timescale algorithm that can recover the optimal time-share values. Most existing algorithms have a component, called global scheduling, which is usually NP-hard. We apply imperfect scheduling and prove that if the imperfect scheduling achieves an approximation ratio rho, then our algorithm produces a suboptimum of the overall problem with the same approximation ratio. By combining the idea of column generation and the two-timescale algorithm, we derive a family of algorithms that allows us to reduce the number of times the global scheduling is needed.

Multi-channel multi-radio technology offers a great space of resource diversity. In this paper, we propose an opportunistic multiradio MAC (OMMAC) protocol to improve system performance by utilizing multiradio diversity. The proposed OMMAC collects the physical layer feedback over multiple radios simultaneously and schedules multiple transmissions on the available channels accordingly. The channel based packet scheduling leverages the channel quality information to jointly select data rates, channels and packets to increase the overall spectral usage of multiple radios which have not been exploited in previous literature. Extensive results from both analysis and ns2 simulations demonstrate that OMMAC significantly improves the network throughput in both single- and multi-hop wireless multirate networks in terms of both aggregate and per-radio throughput.

Broadcast scheduling is a fundamental problem in wireless ad hoc networks. The objective of a broadcast schedule is to deliver a message from a given source to all other nodes in a minimum amount of time. At the same time, in order for the broadcast to proceed as predicted in the schedule, it must not contain parallel transmissions which can be conflicting based on the collision and interference parameters in the wireless network. Most existing work on this problem use a limited network model which accounts only for conflicts occurring inside the transmission ranges of the nodes. The broadcast schedules produced by these algorithms are likely to experience unpredictable delays when deployed in the network. This is because they do not take into consideration other important sources of conflict in parallel transmissions, namely the interference range and the carrier sensing range. In this paper we develop a conflict-aware network model, which uses these parameters to increase the probability of scheduling conflict-free transmissions, and thereby improve the reliability of the broadcast schedule. We present and prove correctness of a constant approximation algorithm for minimum-latency broadcast scheduling under this network model. We also present a greedy heuristic algorithm for the same problem. Experimental results are provided to evaluate the performance of our algorithms. In addition, the algorithms are analyzed to justify their performance trends.

Opportunistic scheduling has been known as one of the possible ways of exploiting multi-user diversity, which comes from the time-varying propagation characteristics and broadcast nature of wireless radios, to improve communication efficiency and reliability. Multi-channel multi-radio technology has offered great opportunity in designing wireless network MAC protocol to utilize all kinds of resource diversities. Other than multi-user diversity, we identify the unique multi-radio diversity which can be exploited in multi-radio wireless network to improve network throughput performance. The proposed opportunistic multi-radio MAC (OMMAC) takes advantage of multi-radio diversity to increase the spectrum usage as much as possible. Extensive NS2 simulation results demonstrate that OMMAC significantly improves the network throughput in both single and multi-hop wireless networks.