Consider a wireless network where each communication link has a minimum bandwidth quality-of-service requirement. Certain pairs of wireless links interfere with each other due to being in the same vicinity, and this interference is modeled by a conflict graph. Given the conflict graph and link bandwidth requirements, the objective is to determine, using only localized information, whether the demands of all the links can be satisfied. At one extreme, each node knows the demands of only its neighbors; at the other extreme, there exists an optimal, centralized scheduler that has global information. The present work interpolates between these two extremes by quantifying the tradeoff between the degree of decentralization and the performance of the distributed algorithm. This open problem is resolved for the primary interference model, and the following general result is obtained: if each node knows the demands of all links in a ball of radius @math centered at the node, then there is a distributed algorithm whose performance is away from that of an optimal, centralized algorithm by a factor of at most @math . The tradeoff between performance and complexity of the distributed algorithm is also analyzed. It is shown that for line networks under the protocol interference model, the row constraints are a factor of at most @math away from optimal. Both bounds are best possible.
Under the protocol interference model, recent work by @cite_22 @cite_10 investigates computationally efficient solutions for the scheduling problem. The problem of finding maximum weight independent sets in claw-free graphs is solvable in polynomial time. The approach taken in @cite_10 to address the situation where the conflict graphs are not claw-free is to add edges to the conflict graph to obtain a claw-free graph. This preserves the original interference constraints and gives a valid schedule in polynomial time. Because of the added interference constraints, the throughput is suboptimal.
@cite_10 @cite_22
2775104858 2963327417
In this paper, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when such scheduling problems can be represented by claw-free conflict graphs where we consider a wireless broadcast medium. It is possible to formulate a scheduling problem of network coded flows as finding maximum weighted independent set (MWIS) in the conflict graph of the network. Finding MWIS of a general graph is NP-hard leading to an NP-hard complexity of scheduling. In a claw-free conflict graph, MWIS can be found in polynomial time leading to a throughput-optimal scheduling. We show that the conflict graph of certain wireless ad hoc networks are claw-free. In order to obtain claw-free conflict graphs in general networks, we suggest introducing additional conflicts (edges) while keeping the decrease in MWIS size minimal. To this end, we introduce an iterative optimization problem to decide where to introduce edges and investigate its efficient implementation. Besides, we exemplify some physical modifications to manipulate the conflict graph of a network and also propose a mixed scheduling strategy for specific networks. We conclude that claw breaking method by adding extra edges can perform nearly optimal under the necessary assumptions. In this paper, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when such scheduling problems can be represented by claw-free conflict graphs. It is possible to formulate a scheduling problem of network coded flows as finding maximum weighted independent set (MWIS) in the conflict graph of the network. We consider activation of hyperedges in a hypergraph to model a wireless broadcast medium. We show that the conflict graph of certain wireless ad hoc networks are claw-free. It is known that finding MWIS of a general graph is NP-hard, but in a claw-free conflict graph, it is possible to apply Minty's or 's algorithms in polynomial time. We discuss our approach on some sample networks.