We consider the problem of scheduling in multihop wireless networks subject to interference constraints. We consider a graph based representation of wireless networks, where scheduled links adhere to the K-hop link interference model. We develop a distributed greedy heuristic for this scheduling problem. Further, we show that this distributed greedy heuristic computes the exact same schedule as the centralized greedy heuristic.
A commonly used model is the @math -hop link interference model, in which two links that are not within K-hops of each other can communicate simultaneously, and the capacity of a link is a constant value if there is no interference @cite_15 , @cite_13 , @cite_8 , @cite_1 , @cite_12 , @cite_10 . In @cite_15 , the Maximal Matching (MM) scheduling algorithm is used under the node exclusive interference model. This algorithm can operate in a distributed fashion and is proven to achieve at least one half of the achievable throughput. This has motivated subsequent research on distributed algorithms with provable performance @cite_13 , @cite_8 , @cite_10 , @cite_1 , @cite_12 .
@cite_8 @cite_10 @cite_1 @cite_15 @cite_13 @cite_12
2118844846 207247871 2088693732 1901187898 2005076479
We consider wireless networks with a special type of spectral allocation, where the only constraint is that a node cannot transmit to more than one receiver at a time and cannot receive more than one transmission at a time. We introduce a scheduling algorithm called regulated maximal matching which is fully distributed and guarantees a throughput that is at least half of the throughput achievable by a centralized algorithm. Abstract— We consider wireless networks with interference constraints. The network consists of a set of links and a set of users who generate packets that traverse these links. Each user is associated with a route consisting of a sequence of links. The links are subject to the usual interference constraints: (i) if link l interferes with link k, then link k also interferes with link l, and (ii) two links that interfere with each other cannot transmit simultaneously. The interference set of a link is defined to be the set of links that interfere with the link, along with the link itself. A greedy scheduler is one which selects an arbitrary set of links to transmit subject only to the interference constraint. We use a traffic regulator at each link along the route of each flow which shapes the traffic of the flow. We prove that the network is queue-length stable under any maximal greedy scheduling policy provided that the total arrival rate in the interference set of each link is less than one. The scheduling problem in multi-hop wireless networks has been extensively investigated. Although throughput optimal scheduling solutions have been developed in the literature, they are unsuitable for multi-hop wireless systems because they are usually centralized and have very high complexity. In this paper, we develop a random-access based scheduling scheme that utilizes local information. The important features of this scheme include constant-time complexity, distributed operations, and a provable performance guarantee. Analytical results show that it guarantees a larger fraction of the optimal throughput performance than the state-of-the-art. Through simulations with both single-hop and multi-hop traffics, we observe that the scheme provides high throughput, close to that of a well-known highly efficient centralized greedy solution called the greedy maximal scheduler. In this paper, we study cross-layer design for rate control in multihop wireless networks. In our previous work, we have developed an optimal cross-layered rate control scheme that jointly computes both the rate allocation and the stabilizing schedule that controls the resources at the underlying layers. However, the scheduling component in this optimal cross-layered rate control scheme has to solve a complex global optimization problem at each time, and hence is too computationally expensive for online implementation. In this paper, we study how the performance of cross-layer rate control can be impacted if the network can only use an imperfect (and potentially distributed) scheduling component that is easier to implement. We study both the case when the number of users in the system is fixed and the case with dynamic arrivals and departures of the users, and we establish desirable results on the performance bounds of cross-layered rate control with imperfect scheduling. Compared with a layered approach that does not design rate control and scheduling together, our cross-layered approach has provably better performance bounds, and substantially outperforms the layered approach. The insights drawn from our analyses also enable us to design a fully distributed cross-layered rate control and scheduling algorithm for a restrictive interference model. We propose two new distributed scheduling policies for ad hoc wireless networks that can achieve provable capacity regions. Known scheduling policies that guarantee comparable capacity regions are either centralized or need computation time that increases with the size of the network. In contrast, the unique feature of the proposed distributed scheduling policies is that they are constant-time policies, i.e., the time needed for computing a schedule is independent of the network size. Hence, they can be easily deployed in large networks.