Scheduling in Multi-hop Wireless Networks with Priorities

Details Scheduling in Multi-hop Wireless Networks with Priorities Scheduling in Multi-hop Wireless Networks with Priorities

2009-01-19

arxiv.org/abs/0901.2922v1

Computer Science

Information Theory

9 pages, 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Scheduling in Multi-hop Wireless Networks with Priorities does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scheduling in Multi-hop Wireless Networks with Priorities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling in Multi-hop Wireless Networks with Priorities will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-434273