Abstract-We propose a general family of MAC scheduling algorithms that achieve any rate-point on a uniform discretelattice within the throughput-region (i.e., lattice-throughputoptimal) under a physical interference model. Under the physical interference model, a centralized algorithm requires information on node locations (and distance among nodes) to determine a schedule that is provably throughput-optimal. In this paper, we propose a distributed, synchronous contention-based scheduling algorithm that (i) is lattice-throughput-optimal, (ii) does not require node location information, and (iii) has a signaling complexity that does not depend on network size. Thus, it is amenable to simple implementation, and is robust to network dynamics such as topology and load changes. We consider a MAC link scheduling algorithm for a timeslotted wireless ad-hoc network under a physical interference model. The MAC scheduling problem for such networks has been an active research topic during the past decades, with much of the research focusing on a graph-based interference model, where primary (i.e., one-hop) and secondary (i.e., twohop) conflict models are considered. However, the graph-based interference model is a tremendous simplification of wireless communications mainly because it is oblivious to a realistic aggregate interference [1], [2] , i.e., the interference caused by various transmitters may accumulate to eventually impede reception. MAC scheduling algorithms under graph-based interference models can be broadly classified into: (i) distributed suboptimal algorithms with partial throughput-guarantees (e.g., [3]-[6]), where distributed, fast algorithms achieving provable lower bounds on the throughput region have been proposed based on sub-optimal choices for a schedule on each time-slot (e.g., maximal scheduling used in switch scheduling [7] ), and (ii) graph-coloring based algorithms (see [8] and references therein), where the coloring problem (which is NP-complete) is formulated by transforming the original graph into a link contention graph, and suboptimal polynomial centralized or distributed heuristics algorithms have been proposed. In this paper, under the physical interference model, we propose a family of dynamic, randomized, distributed MAC scheduling algorithms and associated generalized conditions, which, if satisfied, ensure lattice-throughput-optimality, i.e., achieving any rate-point on a uniform discrete-lattice within Y. Yi is with the Department of Electrical Engineering, Princeton University (e-mail: yyi@princeton.edu). G. de Veciana and S. Shakkottai are with the Department of Electrical and Computer Engineering, The University of Texas at Austin (email: {gustavo, shakkott}@ece.utexas.edu). This research was supported by NSF grants CNS-043507, CNS-0347400, CCF-0634898, and the DARPA ITMANET program. the throughput-region. Note that under the physical interference model, even a centralized scheduling algorithm requires exact topology knowledge (i.e., node locations and network connectivity) to achieve throughput-optimality, which is needed to compute the amount of interference generated by simultaneously activated nodes. However, somewhat surprisingly, we propose a distributed algorithm that achieves lattice-throughput-optimality without centralized geographical information. To the best of our knowledge, this paper is the first attempt to propose a distributed, throughput-optimal scheduling algorithm under the physical interference model. As an instance of the proposed family of lattice-throughputoptimal algorithms, we develop a synchronized contention based algorithm, RCAMA (Randomized Contention Aware Multiple Access), which requires only a simple contention signaling on each time-slot, leading to significant simplification of implementation. In addition to being provably latticethroughput-optimal, RCAMA operates in a "dynamic" manner, i.e., determined schedules are not necessarily conflict-free, but they are progressively improved to approach an optimal schedule (see Figure 1) . Further, simple contention signaling enables RCAMA to adapt to changes in traffic load and network topology by learning a neighborhood's contention patterns in an autonomous way. The main motivation of RCAMA is that although individual (end-to-end) traffic loads may change quickly, the aggregates on some congested links may, in many relevant applications, change more slowly and locally. Similarly, node mobility (that leads to changes in topology and load) might be slow enough to permit a MAC scheduler to learn and exploit the offered traffic characteristics so as to quickly realize "good" schedules. There has been much recent work in the context of algorithms with provable (partial) throughput guarantees under the graph-based interference model. Examples include distributed suboptimal schemes [3]- [6] , which provide lower-bounds on the throughput-region with no explicit knowledge of the offered load (i.e., statistics/knowledge of the load over any link in the network). These algorithms require either control message overheads growing with the network size [3]- [5] or constant overhead but can only realize limited throughput guarantees [6] . Clearly, their message complexities will significantly increase under the physical interference model due to the more complex interference relationships among links. Recently, the authors in [9], [10] have proposed scheduling algorithms with a 100% throughput guarantee under graphbased interference models, but they still require high control message complexity. In contrast with the above sub-optimal, distributed approaches, we assume that a node only has explicit knowl- This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2007 proceedings. edge of the local (long-term) offered load (i.e., offered load on each of its outgoing links). However, we are able to prove that this extra local-information at nodes leads to a distributed, lattice-throughput-optimal algorithm that requires only three-stages of simple contention signaling (which leads to six signaling messages over one-hop) on each time-slot, irrespective of network size. In our preliminary work [11] , a family of lattice-throughput-optimal scheduling algorithms was proposed based on a graph based interference model. However, as discussed earlier, under the physical interference model, finding a throughput-optimal algorithm seems to be a much more difficult task, since the maximum number of hops that need to be considered is at most two for the graph-based interference model, whereas under the physical interference model, interference is aggregate, leading to the possibility that an arbitrary number of hops must be considered in deciding a "good" schedule. In practice, depending on the service supported by the network, information on the offered load can either be explicitly given to the nodes or be measured by the nodes. If we have a guaranteed-service network based on a resource reservation signaling (e.g., RSVP [12] ), the amount of load could be known a priori by nodes in the path of a reserved flow. However, in a typical best-effort service network, the amount of load is not explicitly provided to the nodes, but the nodes could measure/estimate offered load over a suitable time-period. Because the loads might exhibit some variation, or measurements might be noisy, a node might use an upper estimate for it (i.e., overbook). Recently, there have been several efforts towards analysis and design of wireless multi-hop networks under more general interference models than the graph-based interference model. The work of [13] develops a mathematical programming formulation for minimizing the frame size over a TDMA wireless multi-hop networks, based on the optimal joint MAC scheduling and power control under the physical interference model. This work differs from ours in that the proposed distributed, heuristic algorithm in [13] is sub-optimal, and it operates under a "relaxed physical interference model," where the interference generated by only a single interfering transmitter closest to the intended receiver is considered. The authors in [14] , [15] also adopt this relaxed physical interference model to design and study the performance of a MAC protocol. The authors in [15] consider a mathematical optimization formulation for MAC scheduling under the physical interference model, and propose a heuristic centralized scheme with the goal of using the centralized heuristic as a benchmark of other distributed on-line algorithms. In [16] , the authors introduce a new class of interference models characterized by the parameter K, where a successful reception of a message at a receiver requires no transmission from nodes that are K-hops away from the receiver. The work of [17] defines the "scheduling complexity," which corresponds to the minimum amount of time required until a connected graph structure can be scheduled. However, they do not address the scheduling problem directly, and focus only on asymptotic analysis of scheduling complexity. In [18] , [19] , the authors have focused only on computing maximum throughput under the physical interference model by jointly considering routing, MAC scheduling, and power control in an optimization framework. However, in [18] , [19] , the MAC scheduling part is captured using an abstract fluid model, and no practical, throughput-optimal, distributed algorithm is presented. The main contributions of this paper are as follows: (i) Under the physical interference model, we first propose a family of scheduling algorithms (DRS: Dynamic Randomized Scheduling) that achieves any rate-point on a uniform discretelattice within the throughput region (i.e., lattice-throughputoptimal). To that end, we give two general conditions, which, if satisfied, ensure that an algorithm in the DRS family is lattice-throughput-optimal, and we further study their rate of convergence. (ii) Next, as an instance of the DRS family, we propose a synchronous contention-based algorithm, RCAMA (Randomized Contention-Aware Multiple Access), where multi-stage contention signaling in conjunction with randomized timeslot selection is used. We prove lattice-throughput-optimality of RCAMA, by showing that RCAMA satisfies the two conditions in (i). Further, we propose an adaptive variation of RCAMA, ARCAMA (Adaptive RCAMA), which again satisfies the two conditions in (i) and adaptively biases slot selection probabilities based on the past contention histories. We show via simulation that only a short duration of memory is enough to increase performance, resulting in good adaptation to load/topology changes. The paper is organized as follows: We begin with a description of the system model, notations, and definitions in Section II. Next, in Section III, we define the DRS algorithm family, and present two general conditions for a DRS algorithm to be lattice-throughput-optimal. In Section IV, as an instance of such a lattice-throughput-optimal family, we propose RCAMA, and discuss its variations for better adaptation to load/topology changes. Finally, in Section VI, we validate our results using simulations. II. S M, N,  D We assume that time is slotted. A time-slot duration is suitably chosen to accommodate the transmission of one fixed-size packet and includes a guard time corresponding to the maximum differential propagation delay between pairs of nodes in the network. We model the wireless multi-hop network by a graph G(L, V), where L and V denote a set of directional links, and a set of nodes, respectively. We assume that for any link between two nodes there is a counter-part in the opposite direction. We denote a directed link from node i to node j by i→ j. The wireless system has a single frequency/code, which is available for both data and control message transmission, and there is no separate physical channel for control messages (i.e., in-band signaling). Each node in the system is equipped with an omni-directional antenna, and synchronized. We assume 295 that each transmission is intended for only one receiver 1 , and each node has only a single transceiver (i.e., half-duplex radio). We denote the (fixed) power level which a transmitter uses for data transmission by P, and the physical interference model based on SINR (Signal-to-Interference-Noise Radio) is considered. In this interference model, a link i→ j, i, j ∈ V is connected, if G i j P/η j ≥ γ, where G i j is the propagation loss from i to j, and η j is the thermal noise power at j. The SINR threshold γ depends on the desired bit rate, bit error rate, and design parameters such as modulation, coding, and so on. A message (e.g., data, ack, or control messages) from i to j is decodable, if where V I is the set of nodes, which transmit simultaneously with i on a given time-slot. In practice, in addition to interference, wireless links are prone to errors due to many other factors (e.g., fading). This leads to high packet loss rate detrimental to upper-layer performance. Thus, in many MAC protocols, reliability is provided by acknowledging transmissions and possibly retransmitting. Thus, we define the following: Definition 2.1: We say that a transmission over i→ j is successful, if both the data message from i to j and the corresponding ack message from j to i are decodable at j and i, respectively, where ack message from j will be launched only when the data message is decodable at i. In this paper, we focus only on link-level flows, and we do not consider routing and transport-layer end-to-end flows. A link schedule A = (A l : l = 1, . . . , |L|), A l ∈ {0, 1} is a binary vector representing the set of links scheduled for transmission attempt on a time-slot, where A l = 1 if the link l is scheduled, and 0 otherwise. We define a reverse of a link schedule A, R( A) = (B l ) to be: B ( j,i) = 1, if A (i, j) = 1, and 0 otherwise. Definition 2.3: A link schedule A is said to be successful, if the transmissions scheduled by A and R( A) are successful, respectively. We denote the collection of all successful link schedules by A. Definition 2.4: We define the throughput region Λ by: Definition 2.5: For any fixed positive integer F, we define the F-lattice-throughput region Λ F by: Intuitively, Λ F is the lattice-sampling of Λ with adjacent points having a distance of 1/F. Note that Λ = CL(∪ F=1,...,∞ Λ F ), where CL(Z) is the closure of a set Z. Definition 2.6: A scheduling algorithm Π chooses a sequence of link schedules (which are not necessarily success-1 In other words, we consider a "link" scheduling, not "node" scheduling. ful), ( A[s] : s = 0, 1, . . .), where A[s] is the link schedule on time-slot s. Definition 2.7: For a fixed F, the offered load ρ is said to be F-lattice-feasible if ρ ∈ Λ F . Definition 2.8: A scheduling algorithm Π is said to be Flattice-throughput-optimal, if Π achieves any F-lattice-feasible load. For a F-lattice-feasible load ρ, by multiplying the offered load by F, we henceforth deal with positive integer-valued load, θ ∈ Z |L| + , i.e., θ l corresponds to the number of requested time-slots over link l out of F time-slots. We call a group of F time-slots a frame throughout this paper. In our framework, the lattice-parameter F is a systemwide parameter that is known to every node in the network a-priori. Thus, throughout this paper, we implicitly assume that the lattice-parameter, denoted by F, is fixed. Further, for simplicity, we use the terms "throughput-optimal" and "feasible" to refer to "F-lattice-throughput-optimal" and "Flattice-feasible," respectively, unless explicitly needed. T-O In this paper, we consider "frame-based" scheduling algorithms, where scheduling patterns are determined on a frameby-frame basis (i.e., F time-slots) 2 , and we will see that it is sufficient to consider such class of algorithms. Definition 3.1: We define a frame schedule (FS) to be a consecutive sequence of F link schedules, i.e., a |L|×F matrix, C(F, θ) = (c ls : l = 1, . . . , |L|, s = 1, . . . , F), where c ls = 1 if a transmission is scheduled over link l on time slot s, and 0 otherwise. Further, the l-th row vector of C(F, θ), is said to be a slot schedule over l. A FS C(F, θ) is said to be feasible, if all of F link schedules (column vectors) in C(F, θ) are successful. As mentioned in Section I, we assume that a node has knowledge only of the local offered load (i.e., arrival rate) on each of its outgoing links. Thus, for all l ∈ L, θ l = F s=1 c ls , i.e., the number of scheduled time-slots on each link is equal to the load offered on that link. Definition 3.2: We additionally define a transmission priority, R = (r ls : l = 1, . . . , |L|, s = 1, . . . , F) where r ls = 1 (r ls = 0) if c ls = 1 and its priority is high (low), and NULL otherwise (c ls = 0). In this paper, we consider the following class of framescheduling algorithms: (F, θ) , by Definition 2.5. Our objective in this paper is to develop a DRS 2 Thus, we henceforth use a term 'time-slot s' to refer to the s-th timeslot inside a frame. We typically use 's' and 't' to refer to the indexes of a time-slot and a frame, respectively. This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2007 proceedings. scheduling algorithm which finds a feasible frame schedule within a finite number of frames, and sustains the schedule thereafter, for any given feasible load. It can be easily seen that a DRS algorithm satisfying such properties achieves latticethroughput-optimality. Thus, it suffices to consider the family of DRS algorithms. Now, we derive two conditions, which, if met, ensure that a DRS algorithm is throughput-optimal: (i) FSC (Feasibility Sustenance Condition), where if a FS converges to a feasible one, it has to be sustained thereafter, and (ii) FIC (Finite Improvement Condition), where before converging to a feasible FS, a sequence of FSs over frames tend to be progressively "closer" to a feasible FS with positive probability. We first define a "distance" between two FSs (under the same topology and load), C = (c ls ) and C = (c ls ), to be: Note that D(C, C ) = 0 implies C = C . Definition 3.4: For a given fixed load and topology, let the current frame to be t i . Subject these two conditions, we have the following theorem: Theorem 3.1: For any fixed feasible offered load and topology, consider a DRS algorithm Π which satisfies FSC and FIC. We have that (i) Π converges to a feasible FS, and thus Π is throughputoptimal. (ii) Let τ Π (C) be the convergence time of Π to a feasible FS for a given initial frame schedule C. Then, ∀t ∈ Z + , there exist constants 0 < K Π < ∞ and 0 < p Π < 1, such that Pr τ Π (C) > tK Π ≤ p t Π . Due to space limitations, we skip the proof, which is available in [20] . The sketch of proof is as follows: First, it is easily seen that a sequence of FSs over frames forms a Markov chain. Then, FIC implies that we can construct a converging path to a feasible FS (say, C ) within a finite time, since D(C, C ) is upper-bounded. FIC and FSC enable us to verify throughput-optimality of a DRS algorithm. In addition, it can be customized/enhanced, and still be throughput-optimal, as long as the extended version satisfies FIC and FSC. In this paper, we develop a "base-line" DRS algorithm (RCAMA) with history 1 in Section IV, and then extend RCAMA to ARCAMA (Adaptive RCAMA) with multiple frame histories for better adaptation to load/topology changes in Section V, with both RCAMA and ARCAMA satisfying FSC and FIC.
In REF , a contention based distributed algorithm, RCAMA, is proposed, using a physical interference model.
On Optimal MAC Scheduling With Physical Interference
IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications
IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications
Computer Science