There are many protocols for MAC-layer rate control and scheduling of wireless ad hoc networks. Yet, network nodes are often compromised, and thus cannot trust one another to be running a given protocol correctly. This paper proposes a secure protocol for fair rate allocation and rate-stable scheduling at the MAC layer for wireless ad hoc networks. We assume the physical hardware is secure, and design our protocol to be secure against software attacks, i.e., hacking. Software vulnerabilities are divided into three parts: (1) the inputs to the program; (2) the program itself; (3) the output of the program. Our proposed secure fair MAC protocol leverages trusted computing technology. A typical (insecure) fair MAC protocol is first described, and simulations show that our proposed secure fair MAC protocol achieves comparable performance even while under attack.

We consider a general class of low complexity distributed scheduling algorithms in wireless networks, prioritized maximal scheduling, which compute a maximal set of transmitting links in each time slot according to certain pre-specified static priorities. The proposed scheduling scheme has low complexity, and is easily amendable for distributed implementation, such as adjusting inter-frame space (IFS) parameters under the ubiquitous 802.11 protocols. We provide throughput guarantees on the proposed scheduling scheme, by proving tight lower bound on the stability region and scheduling efficiency associated with a fixed priority vector. We next propose an online low complexity priority assignment algorithm, which can stabilize any arrival rate that is in the union of the lower bound regions of all priorities. The throughput guarantees are proved by fluid limits, and therefore can be applied to very general stochastic arrival processes. Finally, the performance of the proposed prioritized maximal scheduling scheme is verified by simulation results.

In this paper, we propose a distributed throughput-optimal ad hoc wireless network scheduling algorithm, which is motivated by the celebrated simplex algorithm for solving linear programming (LP) problems. The scheduler stores a sparse set of basic schedules, and chooses the max-weight basic schedule for transmission in each time slot. At the same time, the scheduler tries to update the set of basic schedules by searching for a new basic schedule in a throughput increasing direction. We show that both of the above procedures can be achieved in a distributed manner. Specifically, we propose an average consensus based link contending algorithm to implement the distributed max weight scheduling. Further, we show that the basic schedule update can be implemented using CSMA mechanisms, which is similar to the one proposed by Jiang et al. Compared to the optimal distributed scheduler, where schedules change in a random walk fashion, our algorithm has a better delay performance by achieving faster schedule transitions in the steady state. The performance of the algorithm is finally confirmed by simulation results.

This paper proposes a dynamic primal-dual type scheduling algorithm in wireless networks, which achieves optimal throughput even with uncertain parameters. In wireless networks, such uncertain parameters are generated by complicated stochastic dynamics, such as random packet arrivals, channel fading, and node mobilities. The algorithm is a generalization of the well-known max-weight scheduling algorithm proposed by Tassiulas et al., where the only uncertain parameters are the packet arrival rates. Using the technique of fluid limits, sample path convergence result of the algorithm to an arbitrarily close to optimal solution is proved, under the assumption that the Strong Law of Large Numbers (SLLN) applies to the random processes which generate these uncertain parameters. The performance of the algorithm is further verified by simulation results. This method may potentially be applied to other cross-layer optimization problems, where dynamic algorithms for convex problems with uncertain parameters are needed.

In this paper we consider greedy scheduling algorithms in wireless networks, i.e., the schedules are computed by adding links greedily based on some priority vector. Two special cases are considered: 1) Longest Queue First (LQF) scheduling, where the priorities are computed using queue lengths, and 2) Static Priority (SP) scheduling, where the priorities are pre-assigned. We first propose a closed-form lower bound stability region for LQF scheduling, and discuss the tightness result in some scenarios. We then propose an lower bound stability region for SP scheduling with multiple priority vectors, as well as a heuristic priority assignment algorithm, which is related to the well-known Expectation Maximization (EM) algorithm. The performance gain of the proposed heuristic algorithm is finally confirmed by simulations.

We consider a general scheduling problem in wireless networks under uncertain arrival and channel state statistics. The objective is to minimize a linear cost function, which can be used to model wireless communication constraints, such as power consumption. We assume that the arrival processes and the network states are random, and with unknown distributions. In each time slot, the schedule can only be computed based on past history. We propose a conditional-gradient type scheduling algorithm and a priority queuing mechanism with auxiliary dummy queues. We show that these can achieve an objective function value which is arbitrarily close to the optimal, while guaranteeing network stability. The performance of the algorithm is further confirmed by simulation results.

This paper considers the joint routing and scheduling problem in wireless networks with lossy channels. In order to combat channel loss, packets are assumed to be transmitted by nodes using broadcast, instead of traditional point-to-point communication. We first analyze the network capacity region, and then propose a back-pressure routing with max-weight scheduling algorithm to achieve it. The proposed algorithm is a generalization of the algorithm proposed by Tassiulas to wireless broadcast networks. Further, we propose a random low complexity scheduling algorithm which, combined with backpressure routing, also achieves the same capacity region. Both stability results are proved by the method of fluid limits.

In this paper we consider prioritized maximal scheduling in multi-hop wireless networks, where the scheduler chooses a maximal independent set greedily according to a sequence specified by certain priorities. We show that if the probability distributions of the priorities are properly chosen, we can achieve the optimal (maximum) stability region using an i.i.d random priority assignment process, for any set of arrival processes that satisfy Law of Large Numbers. The pre- computation of the priorities is, in general, NP-hard, but there exists polynomial time approximation scheme (PTAS) to achieve any fraction of the optimal stability region. We next focus on the simple case of static priority and specify a greedy priority assignment algorithm, which can achieve the same fraction of the optimal stability region as the state of art result for longest queue first (LQF) schedulers. We also show that this algorithm can be easily adapted to satisfy delay constraints in the large deviations regime, and therefore, supports quality of service (QoS) for each link.

This paper considers the scheduling problem in wireless networks. We focus on prioritized maximal scheduling, where a maximal scheduler chooses the links in an order specified by certain priority. We first analyze the capacity region of a maximal scheduler with fixed priority, where a lower bound is formulated and shown to be tight. Next we propose both centralized and distributed algorithms to search for the optimal priority for a given arrival rate. The algorithms are optimal in the sense that, if the arrival rate is in the lower bound region of any prioritized maximal scheduling, it is stable under the result of our algorithms. Finally, by combining the priority assignment and maximal scheduling, we prove that we can achieve a certain fraction of the optimal capacity region, which is bounded below by a constant for most networks.

Scheduling in an ad hoc wireless network suffers from the non-convexity of the cost function, caused by the interference between communication links. In previous optimization theoretic analysis, the weighted sum-rate maximization (WSRM) which inherits the non-convexity has been identified as a core problem of the hard scheduling problem. In this paper, we propose a polynomial-time approximation algorithm with guaranteed accuracy for WSRM under an Ultra- wide band (UWB) assumption. The algorithm is obtained by an appropriate adaptation of the 'shifting' strategy (a well- known approximation technique for some geometric problems) for the wireless broadcast environment. The worst case accuracy and complexity of the algorithm are analyzed by utilizing the quadratic link rate function derived in previous research, under the assumption of a large bandwidth, as is typical in UWB networks. The average case performance of the algorithm is investigated by simulations on random ad hoc networks.

We introduce a hypergraph based interference model for scheduling in wireless networks. As a generalization of the graph model, hypergraph considers the conflicts caused by sum interference. We show in an arbitrary network, the successful transmissions under any graph model can be improved by a hypergraph. In some networks, a hypergraph can double the uniform throughput compared to the disk graph. We then analyze the capacity region of maximal scheduling in the hypergraph, where a linear programming (LP) based lower bound is formulated and proven to be tight. We also show that the maximal scheduling in hypergraph can guarantee a certain fraction of the capacity region. Simulation results show that maximal scheduling in hypergraph can achieve about 40% more uniform throughput than in graph for random networks.

For decades, a disk-graph model has been used to design scheduling (coloring) in wireless networks, influencing many practical medium access control schemes. The pairwise - interference model used by a disk graph, however, has a fundamental limitation because it does not account for the sum- interference. Thus, a coloring algorithm that uses such a model cannot guarantee the originally intended rate on all links. In this paper, we specify a mapping to a flow-contention graph, which fully considers the aggregated effect of all interferers (sum- interference), and thus, guarantees the originally intended rate on all links. A coloring algorithm, specific to the generated graph, is presented along with a bound on the required number of colors (channels). Further, a mathematical analysis of the scheduling is presented along with simulation results, to show that the minimum number of channels required in a random network is Theta(logn/log log n), where n is the number of links, even after accounting for the sum-interference. This allows us to investigate the effect of the underlying physical layer, thus demonstrating the utility of the presented algorithm and analysis results.