Graph-based algorithms for point-to-point link scheduling in Spatial reuse Time Division Multiple Access (STDMA) wireless ad hoc networks often result in a significant number of transmissions having low Signal to Interference and Noise density Ratio (SINR) at intended receivers, leading to low throughput. To overcome this problem, we propose a new algorithm for STDMA link scheduling based on a graph model of the network as well as SINR computations. The performance of our algorithm is evaluated in terms of spatial reuse and computational complexity. Simulation results demonstrate that our algorithm achieves better performance than existing algorithms.
Algorithms for transmission scheduling in multihop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance, scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. It is shown that tree networks can be scheduled optimally and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network thickness times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree times optimum. Since the thickness is typically several orders of magnitude less than the maximum node degree, the algorithms presented represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods. > In this paper we define a broadcast channel access protocol called spatial TDMA, which is designed specifically to operate in a multihop packet radio environment where the location of the nodes of the network is assumed to be fixed. The defined protocol assigns transmission rights to nodes in the network in a local TDMA fashion and is collisionfree. Methods for determining slot allocations are developed, and an approximate solution is given for determining the assignment of capacities for the links of the network that minimizes the average delay of messages in the system. A parallel algorithm based on an artificial neural network model for broadcast scheduling problems in packet radio networks is presented. The algorithm requires n*m processing elements for an n-mode-m-slot radio network problem. The algorithm is verified by simulating 13 different networks. > This paper proposes a solution to providing a collision free channel allocation in a multihop mobile radio network. An efficient solution to this problem provides spatial reuse of the bandwidth whenever possible. A robust solution maintains the collision free property of the allocation under any combination of topological changes. The node organization algorithm presented in this paper provides a completely distributed, maximally localized execution of collision free channel allocation. It allows for parallel channel allocation in stationary and mobile networks with provable spatial reuse properties. A simpler version of the algorithm provides also a highly localized distributed coloring algorithm of dynamic graphs. Two polynomial-time algorithms are given for scheduling conversations in a spread spectrum radio network. The constraint on conversations is that each station can converse with only one other station at a time. The first algorithm is strongly polynomial and finds a schedule of minimum length that allows each pair of neighboring stations to converse directly for a prescribed length of time. The second algorithm is designed for the situation in which messages must be relayed multiple hops. The algorithm produces, in polynomial time, a routing vector and compatible link schedule that jointly meet a prespecified end-to-end demand, so that the schedule has the smallest possible length. > We present a distributed algorithm for obtaining a fair time slot allocation for link activation in a multihop radio network. We introduce the concept of maximal fairness in which the termination of a fair allocation algorithm is related to maximal reuse of the channel under a given fairness metric. The fairness metric can be freely interpreted as the expected link traffic load demands, link priorities, etc. Since respective demands for time slot allocation will not necessarily be equal, we define fairness in terms of the closeness of allocation to respective link demands while preserving the collision free property. The algorithm can be used in conjunction with existing link activation algorithms to provide a fairer and fuller utilization of the channel.