Handling Interservice Time Constraints in Wireless Networks

Abstract

Cyber physical systems collect plenty of information from physical world. This information must be transmitted to the base station immediately to support the making of controlling orders since the physical world keeps transforming rapidly. Such a fact needs the support of real-time transmitting in CPS. Real-time traffic often has some extra QoS requirements. For example, regulating the interservice time, which is the time between two consecutive transmissions of a link, is essential for the real-time traffic in wireless networks. A guarantee of the interservice time of a single user is a precondition to support the normal operating of a system. As far as we know, none of previous work can guarantee the performance on the interservice time. Motivated by this, we design a framework for interservice time guaranteed scheduling. We first define a new capacity region of networks with a strict interservice time guarantee. It is an extension of the well-accepted definition on basic capacity region. Then we propose a novel scheduling policy that is both throughput-optimal and interservice time guaranteed. Simulation results show the policy performs well in interservice time and throughput.

1. Introduction

As mobile devices and wireless communication technology keep improving in recent years, there have been more and more complicated wireless networks based applications like cyber physical systems, mobile social networks, and so forth. Real-time traffic occurs frequently in these applications. For example, in a cyber physical system, the sensors collect huge size of information from physical world. And the data is sent to the base station for further decision making [1]. Due to the quick evolving of physical world [2, 3], the CPS must ensure a rapid response to events in the physical world. Then a basic condition of CPS systems is that packets must be delivered to the base or cluster head before their bringing ground truth [4, 5] goes out of date. Such a condition will lead to a great many real-time transmissions in wireless network. Meanwhile, real-time traffic often has some quality-of-service requirements besides the basic need of throughput optimizing and bandwidth saving [6, 7]. These QoS requirements mainly include regularity of the interservice times, packet delay constraints, and packet delivery ratio. As we know, such requirements fail to be captured by those works that only focus on the optimality of throughput performance when scheduling [8] or routing [9, 10]. Some efforts have been made to improve different aspects of QoS. For example, many scheduling policies [11–16] are proposed to handle the transmitting of packets with deadlines. These policies differ in their definitions of delay constraints. And the performance of packet delivery ratio is considered in [17].

Interservice time is the time between two consecutive services for a user, and regularizing the interservice time means a user can get a second chance to transmit in less than a bounded period of time since its last transmission. The regularity of the interservice time is a precondition to support real-time applications like multimedia streaming [18] and also an index to assess the performance of real-time traffic. It is also very important for data collection in CPS systems, since each node must periodically upload its data to the sink, to make sure the sink can capture the event in the corresponding area. However, only very few works study the regularity of the interservice times [18, 19]. Li et al. design a new scheduling policy [18] that keeps the stability of the system under an arriving rate vector while ensuring the regularity of interservice time for each user. The policy is mainly designed to achieve provable performance on the mean value of interservice time. However, to guarantee the interservice time of a single user is also essential. A user may grow into impatience with large interservice time, besides the risk in the nonsupport of its real-time traffic. Some problems remain open when the system has a strict constraint on the length of interservice time for every user. (1)

What is the set of arriving rate vectors under which the system is stable and each user keeps a guarantee of the interservice time (i.e., the interservice time of any user is less than a threshold)?

(2)

Is there a scheduling policy that supports such set of arriving rate vectors while meeting the requirement on service regularity?

In this work, we focus on designing a scheduling policy that keeps the wireless network stable while providing a guarantee of the regularity of interservice time for each user. The contributions of this paper are summarized as follows. (i)

We formulate the problem of handling interservice time constraint in wireless network and define the service-regularity guaranteed capacity region of the system with a given interservice time constraint.

(ii)

We propose a novel scheduling policy in which the interservice time of any user is exactly below the required upper bound given by the constraint. We derive the set of arriving rate vectors inside the service-regularity guaranteed capacity region and prove that the proposed scheduling policy is throughput-optimal, which means it can support all the arriving rate vectors in the capacity region.

(iii)

Simulation results indicate that our scheduling policy can meet the interservice time constraint and performs well on the stability of networks.

The rest of the paper is organized as follows. In Section 2, we bring a literature of the review on the development of scheduling policies in wireless network. In Section 3, we introduce the network model used by our work. In Section 4, the novel scheduling policy is proposed. In Section 5, we prove some properties of the scheduling policy. In Section 6, we show and analyse the simulation results of our scheduling policy. And Section 7 concludes the paper.

2. Related Work

Job scheduling is extensively studied in the real-time operating system [20]. However, link scheduling in wireless network is different from the job scheduling. For example, the length of standard packet is often fixed in a wireless network, which means a link with few data may waste the bandwidth. In the operation system, a proper quantum length can be selected to minimize the waste. There are also many differences in the model assumptions. Thus the conclusions for the operating systems can not be directly used for wireless networks.

Link scheduling is a fundamental challenge in the design of wireless networks. It is well-known that the max weight scheduling policy is throughput-optimal [8]. However, the problem of finding the disjoint set of links with max weight is NP-hard. Hence, a max weight scheduling policy incurs high overhead. There have been many efforts to design low complexity scheduling policies with throughput performance guarantees. Some policies are based on the picking-and-comparing method [21] or carrier sensing multiple access (CSMA) [22]. Those policies gradually achieve the optimal throughput after many iterations but are insensitive to the channel fading [23]. Other policies focus on finding a maximal weight independent set (MWIS) of links. Sakai et al. [24] and Wan et al. [25] designed centralized policies that could find a MWIS with provable ratio bounds. Basagni [26], Hoepman [27], and Joo et al. [28] separately propose distributed scheduling policies for different network models. However, none of these works deal with the QoS requirements of users.

Some scheduling policies are designed to meet the packet delay constraint for each user [11, 12, 14–16]. They all partition the time into frames, and packets will run out of time before the end of their arriving frames. They are different in the assumption of the traffic. Some of them assume the traffic arrives at the beginning of the frame [11, 12], while others assume the arriving happens any time in the frame [14–16]. They also differ in the introducing of channel fading [13], nonidentical delays [16], and so forth. Kang et al. [17] propose a new policy that accommodates packet delivery ratio.

For all we know, very few works [18, 19] deal with the performance of interservice time. Li et al. [18] use a new type of weight to capture the interservice time performance. The weight is a combination of queue length and time-since-last-service. Then under the max weight scheduling policy, a user will get a second service with a growing probability as the time-since-last-service increases. And the interservice time can be regulated. Li et al. [19] extend his work to consider the interservice time performance of rate vectors close to the edge of capacity region. Li et al.'s works fail in the situation when the interservice time of each user is strictly bounded and one hopes to know the exact set of arriving rate vectors that can meet the boundary.

3. Network Model

In our network, N users hope to transmit to a common destination via the same channel. Time is partitioned into slot, and in each slot only one user can communicate with the destination because of the destructive interference in wireless communication. In each slot, $A_{i} [t]$ packets arrive in user i. $A_{i} [t]$ is randomly and identically distributed over time with the expectation $E (A_{i} [t]) = λ_{i}$ . These packets will join the delivering queue and be transmitted to the destination. We assume that the wireless channel is always in good condition, and user i can send $r_{i}$ packets in a slot. In our model, both $λ_{i}$ s and $r_{i}$ s are heterogeneous, which indicates the fact that the size of traffic and communication capability of different mobile device are often various.

We use boolean variable $S_{i} [t] \in {0,1}$ to denote whether user i is scheduled in slot t. Only one user can be scheduled in each slot; thus, we have

\begin{matrix} \sum_{i = 1}^{N} ‍ S_{i} [t] = 1 \end{matrix}

(1)

for arbitrary slot t.

$Q_{i} [t]$ is the size of packets waiting for transmission by user i at the beginning of slot t. $Q_{i} [t]$ is determined by three parts: $Q_{i} [t - 1]$ , $A_{i} [t - 1]$ , and $r_{i} S_{i} [t - 1]$ , with the following equation:

\begin{matrix} Q_{i} [t] = Max \{Q_{i} [t - 1] + A_{i} [t - 1] - r_{i} S_{i} [t - 1], 0\}, \end{matrix}

(2)

where

Q_{i} [t] = 0

means that user i has delivered all its packets in slot

t - 1

Now we formalize the stability of networks by the following definitions.

Definition 1.

We say that the network is stable under an arriving rate vector if the underlying Markov chain $Q_{i} [t]$ is positive recurrent for each user, and

\begin{matrix} \lim_{t \to \infty} \sum_{i = 1}^{N} ‍ Q_{i} [t] \leq \infty . \end{matrix}

(3)

An arriving rate vector $λ = {λ_{i}}_{i = 1, \dots, N}$ is supported by a network if the network is stable under λ by utilizing some scheduling policy. All supportable rate vectors compose the capacity region of the network, denoted by Λ.

Definition 2.

A scheduling policy is throughput-optimal for a network if $Λ^{'} = Λ$ , where $Λ^{'}$ is the set of rate vectors supported by the network when using the scheduling policy.

Interservice time is the number of slots between two consecutive transmissions of a user. We use $T_{i} [m]$ to denote the number of time slots between the $m - 1$ th and mth transmissions of user i. Accordingly, $T_{i} = \lim_{m \to \infty} (\sum_{j = 1}^{m} ‍ T_{i} [j] / m)$ is the long-term average interservice time of user i.

In this paper, we focus on the network model with an extra constraint that $T_{i} \leq N + ϵ$ , for all i, where ϵ is a nonnegative real. Then the network not only is required to be stable, but also guarantees a bounded interservice time for all users. ϵ is always nonnegative since N is the lower bound for the constraint, and the proof is trivial. Then we can extend the definitions of stability, capacity region, and throughput-optimal scheduling policies.

Definition 3.

We say that the network is ϵ-stable under a rate vector λ if the network is stable and $T_{i} \leq N + ϵ$ , for all i.

The definitions of ϵ-supported and ϵ-capacity region $Λ_{ϵ}$ are similar.

Definition 4.

A scheduling policy is ϵ-throughput-optimal for a network if $Λ_{ϵ}^{'} = Λ_{ϵ}$ , where $Λ_{ϵ}^{'}$ is the set of rate vectors ϵ-supported by the network when using the scheduling policy.

Our objection is to design a scheduling policy that is ϵ-throughput-optimal for our network model.

4. Service-Guaranteed Maximum Weight Scheduling Policy

In this section, we propose our scheduling policy (see Algorithm 1). The novel scheduling policy is a maximum weight type policy, while guaranteeing an upper bound on the average interservice time of all users. We call this policy service-guaranteed maximum weight scheduling (SGMW for short).

Algorithm 1

Service-Guaranteed Maximum Weight Policy:

Input : N users, rate vector λ, ϵ

Output : scheduling sequence $u_{1}, u_{2}, \dots, u_{t}$ , $u_{i}$ is the user

scheduled in ith slot

For each interval:

For each time slot t:

For each user i:

$Q_{i} [t] = Max {Q_{i} [t - 1] + A_{i} [t - 1] - r_{i} S_{i} [t - 1], 0}$

If all user has been scheduled in current interval

set all $I [i] = 1$ ;

go to next interval;

Else if the slots left equal the users have not been

scheduled in current interval

set $I [i] = - 1$ for the users scheduled;

schedule the user j with maximum $w_{j} [t]$ ;

set $I [j] = - 1$

Else

schedule the user j with maximum $w_{j} [t]$ ;

SGMW partitions time into equal sized intervals. Each interval contains $N + ϵ$ slots, where $N + ϵ$ is the upper bound of the average interservice time.

In each interval, the scheduling policy is composed of two components: loose phase and tight phase. The policy first starts in loose phase at the beginning of each interval. In loose phase, all users compete for the channel, and our policy is the same as maximum weight scheduling. SGMW goes into tight phase when the number of time slots left in an interval is the same as the number of users that have not been scheduled in this interval. In tight phase, the policy repeatedly chooses the user whose weight is the largest among the set of users never scheduled in current interval. Obviously, the tight phase lasts until the end of the interval. An interval will terminate before $N + ϵ$ slots if all the users have been scheduled at least once. Then the scheduling policy turns into the next interval.

The weight of user i at time slot t is calculated by the following equation:

\begin{matrix} w_{i} [t] = \frac{I_{i} [t] Q_{i} [t]}{r_{i}}, \end{matrix}

(4)

where

Q_{i} [t]

is the length of packets at user i at the beginning of slot t and

r_{i}

is transmission rate.

I_{i} [t] = - 1

when the policy is in tight phase and the user has been scheduled in current interval, and

I_{i} [t] = 1

otherwise.

Our scheduling policy is a maximum weight type policy and here is an instance about how it processes.

Example 5.

There are two users in the network, with $A_{1} [t] = λ_{1}$ , $A_{2} [t] = λ_{2}$ , $λ_{1} / r_{1} = 1 / 2$ , and $λ_{2} / r_{2} = 1 / 8$ . $ϵ = 1$ , so the upper bound of average interservice time is $3$ .

In slot 1, the SGMW is in loose phase. $w_{1} [1] = 1 / 2$ and $w_{2} [1] = 1 / 8$ ; then, user 1 is scheduled.

In slot 2, the SGMW is still in loose phase because there are 2 slots left and only user 2 has not been scheduled. $w_{1} [2] = 1 / 2$ , $w_{2} [2] = 1 / 4$ , and user 1 is scheduled.

In slot 3, the SGMW turns to the tight phase. $w_{1} [3] = - 1 / 2$ since user 1 has been scheduled in current interval. $w_{2} [3] = 3 / 8$ ; user 2 is scheduled.

In slot 4, a new interval begins, and the process repeats itself. Figure 1 shows the evolution of the network in an interval.

Figure 1

An instance of SGMW.

The time complexity of the policy is analyzed as follows. In each slot, the policy needs to check the weight of each user and selects the largest one. This requires linear scanning of all users, and the time complexity is $O (N)$ . We need to store the weight of all N users; thus, the space complexity is $O (N)$ . We present the pseudocode of the SGMW as the end of this section.

5. Properties of SGMW

In Section 5.1, we prove that SGMW is ϵ-throughput-optimal. We first put forward a necessary condition for a rate vector to be ϵ-supportable. Then we prove that SGMW can support all rate vectors following the necessary condition. SGMW can also bound the average interservice time for each user; thus, it is ϵ-throughput-optimal. In Section 5.2, we derive the ratio between ϵ-capacity region and the original capacity region. The interservice time guarantee of a given rate vector is discussed at the end of this section.

5.1. ϵ-Throughput-Optimality

We first give the necessary condition for a rate vector to be ϵ-supportable.

Lemma 6.

For any arriving rate vector $λ = {λ_{i}}_{i}$ that is ϵ-supportable by a network with some scheduling policies, $\sum_{i = 1}^{N} ‍ Max {(λ_{i} * (N + ϵ) / r_{i}) - 1,0} \leq ϵ$ .

Proof.

We prove the lemma by contradiction. Assume $λ^{'} = {λ_{i}^{'}}_{i}$ is an ϵ-supportable arriving rate vector, and $\sum_{i = 1}^{N} ‍ Max {(λ_{i}^{'} * (N + ϵ) / r_{i}) - 1,0} \geq ϵ$ .

The number of slots in which user i transmits during a total of T slots is no less than $T / (N + ϵ)$ . $Q_{i}^{'} [T]$ denotes the number of packets that remain in $Q_{i} [T]$ when user i is only scheduled once in each interval:

\begin{matrix} E (Q_{i}^{'} [T]) = Max \{\frac{λ_{i}^{'}}{r_{i}} * T - \frac{T}{N + ϵ}, 0\}, \\ \sum_{i = 1}^{N} ‍ E (Q_{i}^{'} [T]) = \frac{T}{N + ϵ} \sum_{i = 1}^{N} ‍ Max \{\frac{λ_{i}^{'} * (N + ϵ)}{r_{i}} - 1,0\} . \end{matrix}

(5)

There are in total $T - N * (T / (N + ϵ))$ extra slots except the basic scheduling for all users. The expectation of total queue length is estimated as follows:

\begin{array}{l} E (\sum_{i = 1}^{N} ‍ Q_{i} [T]) \\ = \sum_{i = 1}^{N} ‍ E (Q_{i} [T]) \\ = \sum_{i = 1}^{N} ‍ E (Q_{i}^{'} [T]) - (T - N * \frac{T}{N + ϵ}) * 1 \\ = \frac{T}{N + ϵ} \sum_{i = 1}^{N} ‍ Max \{\frac{λ_{i}^{'} * (N + ϵ)}{r_{i}} - 1,0\} - \frac{ϵ * T}{N + ϵ} \\ = \frac{T}{N + ϵ} (\sum_{i = 1}^{N} ‍ Max \{\frac{λ_{i}^{'} * (N + ϵ)}{r_{i}} - 1,0\} - ϵ) . \end{array}

(6)

According to the constraint that $\sum_{i = 1}^{N} ‍ Max {(λ_{i}^{'} * (N + ϵ) / r_{i}) - 1,0} \geq ϵ$ ,

\begin{matrix} E (\sum_{i = 1}^{N} ‍ Q_{i} [T]) ⟶ + \infty as T ⟶ + \infty . \end{matrix}

(7)

Then the network is instable under $λ^{'}$ , which contradicts with the assumption. So the condition $\sum_{i = 1}^{N} ‍ Max {(λ_{i} * (N + ϵ) / r_{i}) - 1,0} \leq ϵ$ holds for all ϵ-supportable rate vectors.

Lemma 7 proves that SGMW can support (may not be ϵ-supportable) all the rate vectors following the condition in Lemma 6.

Lemma 7.

For any arriving rate vector $λ = {λ_{i}}_{i}$ with the condition that $\sum_{i = 1}^{N} ‍ Max {(λ_{i} * (N + ϵ) / r_{i}) - 1,0} \leq ϵ$ , the network is stable by utilizing the SGMW.

Proof.

Each interval can be partitioned into two parts: round robin stage and max weight stage. The round robin stage is composed of N slots, one for each user. The max weight stage includes ϵ slots, and the user with the largest weight in each of these slots is scheduled. Slots of two stages may appear crosswise with each other. A slot belongs to the round robin stage if it is the only slot that the user transmits in current interval. And if a user transmits multitimes, arbitrary one of them belongs to the round robin stage.

Then we are about to prove the system is stable in both of the two stages. For any user i,

\begin{matrix} \frac{λ_{i}}{r_{i}} = \{\begin{cases} \frac{λ_{i}}{r_{i}} + 0, & when \frac{λ_{i}}{r_{i}} \leq \frac{1}{N + ϵ} \\ \frac{1}{N + ϵ} + (\frac{λ_{i}}{r_{i}} - \frac{1}{N + ϵ}), & when \frac{λ_{i}}{r_{i}} > \frac{1}{N + ϵ} . \end{cases} \end{matrix}

(8)

The first part of the right side of the equation is supportable in the round robin stage since it is no larger than $1 / (N + ϵ)$ .

The second part of the right side is supported by the max weight stage, which can be deduced as follows:

\begin{array}{l} \sum_{i = 1}^{N} ‍ Max \{\frac{λ_{i}}{r_{i}} - \frac{1}{N + ϵ}, 0\} \\ = \frac{1}{N + ϵ} \sum_{i = 1}^{N} ‍ Max \{\frac{λ_{i} (N + ϵ)}{r_{i}} - 1,0\} \\ \leq \frac{ϵ}{N + ϵ} . \end{array}

(9)

The network is stable in its max weight stage when $t * \sum_{i = 1}^{N} ‍ Max {(λ_{i} / r_{i}) - (1 / (N + ϵ)), 0} \leq (t / (N + ϵ)) * ϵ$ , just as what is proved in 9.

Then the whole rate vector is supportable under our interval-based scheduling policy SGMW.

Lemma 8 is to prove that SGMW can also keep a bound on the interservice time for all users.

Lemma 8.

If an arriving rate vector $λ = {λ_{i}}_{i}$ is supported by SGMW, the average interservice time $T_{i}$ of any user i is no more than $N + ϵ$ .

Proof Sketch. Time slots are partitioned into intervals in SGMW, and length of each interval is less than $N + ϵ$ . Each user can be scheduled at least once in each interval; thus, the number of services for any user is no less than $t / (N + ϵ)$ , and average interservice time $T_{i}$ of any user i is no more than $t / (t / (N + ϵ)) = N + ϵ$ .

SGMW is then ϵ-throughput-optimal by combining Lemmas 7 and 8, which is concluded as Theorem 9.

Theorem 9.

SGMW is ϵ-throughput-optimal scheduling policy in the proposed network model.

5.2. Discussion

The constraint on interservice time reduces the size of capacity region. This is due to the fact that some users with long queue and large arriving rate have to wait for other users to meet the constraint, and length of their queues could possibly tend to infinity. A smaller ϵ often leads to larger decrease in capacity region since the waiting appears more frequently. We formulate the decreasing in the size of capacity region in Theorem 11. Lemma 10 estimates the size of vector space composed of all vectors $k = (k_{1}, k_{2}, \dots, k_{N})$ that follow $k_{i} \geq 0$ , for all i, and $\sum_{1}^{N} ‍ k_{i} \leq β$ . The result of Lemma 10 is applied for the proof of Theorem 11.

Lemma 10.

For any vector $k = (k_{1}, k_{2}, \dots, k_{N})$ , $\oint_{0}^{β} ‍ 1 d σ = β^{n} / n!$ if $k_{i} \geq 0$ , for all i, and $\sum_{1}^{N} ‍ k_{i} \leq β$ . $\oint_{0}^{β} ‍ 1 d σ$ is a multiple integration on the N dimensions, also defined as the size of vector space composed of all vectors like k.

Proof.

We prove the lemma by induction.

Obviously, when $N = 1$ , $\oint_{0}^{β} ‍ 1 d σ = β$ and when $N = 2$ , $\oint_{0}^{β} ‍ 1 d σ = β^{2} / 2$ .

Assume $\oint_{0}^{β} ‍ 1 d σ = β^{k} / k!$ is true when $N = k$ . When $N = k + 1$ ,

\begin{matrix} \oint_{0}^{β} ‍ 1 d σ = \int_{0}^{β} ‍ \oint_{β}^{0} ‍ 1 d σ^{'} d x, \end{matrix}

(10)

where

σ^{'}

is a k-dimensional space with

\sum_{i = 1}^{k} ‍ r_{i} \leq β - r_{k + 1}

, and

\begin{array}{l} \int_{0}^{β} ‍ \oint_{β}^{0} ‍ 1 d σ^{'} d x & = \int_{0}^{β} ‍ \frac{{(β - x)}^{n}}{n!} d x \\ = - \int_{β}^{0} ‍ \frac{{(β - x)}^{n}}{n!} d (β - x) \\ = - \int_{β}^{0} ‍ \frac{{(y)}^{n}}{n!} d (y) \\ = - {\frac{1}{(n + 1)!} (y)^{n + 1}|}_{β}^{0} \\ = \frac{β^{n + 1}}{(n + 1)!} . \end{array}

(11)

Theorem 11 gives the ratio between ϵ-capacity region and the original one.

Theorem 11.

The size of ϵ-capacity region $Λ_{ϵ}$ of a network is no more than $(N! / (N + ϵ)^{N}) \sum_{i = 1}^{N} ‍ (C_{N}^{i} / i!) ϵ^{i}$ of its original capacity region Λ.

Proof.

Based on Lemma 6, $\sum_{i = 1}^{N} ‍ Max {(λ_{i} * (N + ϵ) / r_{i}) - 1,0} \leq ϵ$ holds for any rate vector inside the ϵ-capacity region. We denote $λ_{i} / r_{i}$ by $k_{i}$ and rewrite the inequality as follows:

\begin{matrix} \sum_{i = 1}^{N} ‍ Max \{k_{i} - \frac{1}{N + ϵ}, 0\} \leq \frac{ϵ}{N + ϵ} . \end{matrix}

(12)

Assume there are t users with $k_{i} \geq 1 / (N + ϵ)$ , $t = 0,1, \dots, N$ , and we define $σ_{t}$ as the size of vector space:

\begin{matrix} σ_{t} = C_{N}^{t} \oint_{0}^{ϵ / (N + ϵ)} ‍ 1 d σ_{t}^{'} * {(\frac{1}{N + ϵ})}^{N - t} . \end{matrix}

(13)

C_{N}^{t}

is the combinatorial number of picking t out of N. The second part

\oint_{0}^{ϵ / (N + ϵ)} ‍ 1 d σ_{t}^{'}

is the size of space composed by the vector

{k_{1} - (1 / (N + ϵ)), k_{2} - (1 / (N + ϵ)), \dots, k_{t} - (1 / (N + ϵ))}

, where

\sum_{i = 0}^{t} ‍ (k_{i} - (1 / (N + ϵ))) \leq ϵ / (N + ϵ)

and

k_{i} \geq 1 / (N + ϵ)

for

i = 1, \dots, t

. The third part

(1 / (N + ϵ))^{N - t}

is the vector space of the users, whose

k_{i} \leq 1 / (N + ϵ)

According to Lemma 10, $\oint_{0}^{ϵ / (N + ϵ)} 1 d σ_{t}^{'} = ϵ^{t} / t! (N + ϵ)^{t}$ . We add up all the $σ_{t}$ from $t = 0$ to $t = N$ :

\begin{array}{l} σ & = \sum_{t = 0}^{N} ‍ σ_{t} \\ = \sum_{t = 0}^{N} ‍ C_{N}^{t} \oint_{0}^{ϵ / (N + ϵ)} ‍ 1 d σ_{t}^{'} * {(\frac{1}{N + ϵ})}^{N - t} \\ = \sum_{t = 0}^{N} ‍ C_{N}^{t} \frac{ϵ^{t}}{t! {(N + ϵ)}^{t}} * {(\frac{1}{N + ϵ})}^{N - t} \\ = {(\frac{1}{N + ϵ})}^{N} \sum_{t = 0}^{N} ‍ \frac{C_{N}^{t} ϵ^{t}}{t!} . \end{array}

(14)

The size of original capacity region is $Λ = 1 / N!$ ; thus, $Λ_{ϵ} / Λ \leq (N! / (N + ϵ)^{N}) \sum_{t = 0}^{N} ‍ (C_{N}^{t} ϵ^{t} / t!)$ .

We find that when $ϵ \to \infty$ , $Λ_{ϵ} / Λ \leq (N! / (N + ϵ)^{N}) \sum_{t = 0}^{N} ‍ (C_{N}^{t} ϵ^{t} / t!) \to 1$ . The two capacity regions are relatively identical since the loose interservice time constraint can be omitted. When $ϵ \to 0, Λ_{ϵ} / Λ \leq (N! / (N + ϵ)^{N}) \sum_{t = 0}^{N} ‍ (C_{N}^{t} ϵ^{t} / t!) = N! / N^{N}$ , the ϵ-capacity region of a round robin manner is much smaller than the max weight scheduling policy.

The performance of a system under an arriving rate vector is mainly represented by the total and max queue length of all users. An interservice time constraint can impair the performance due to the following reasons. (1) Some users with few data are scheduled for meeting the constraints, which potentially wastes the bandwidth. (2) A user with high arriving rate and large queue length still has to wait for other users due to the constraint, which potentially aggravates the max queue length. SGMW can achieve the best performance when it is always in the loose phase. Such situations occur when the constraint $N + ϵ$ is larger than the max interservice time of users under the max weight scheduling policy. This max interservice time is determined by the variance of the rate vector, which means it can be small when each user has a relatively identical arriving rate. Meanwhile, the max interservice time has nothing to do with the average arriving rate. We will investigate the relation between the variance and max interservice time in future work. On the other hand, there is a lower bound on the constraint $N + ϵ$ for any arriving rate vector. the vector is not ϵ-supportable when the required constraint is below the bound. According to Lemma 6, we can derive a lower bound $ϵ_{L}$ for an arbitrary arriving rate vector from the inequality $\sum_{i = 1}^{N} ‍ Max {(λ_{i} * (N + ϵ) / r_{i}) - 1,0} \leq ϵ$ . The bound $ϵ_{L}$ is tight since SGMW can support the vector under all $ϵ \geq ϵ_{L}$ .

6. Evaluation

In this section, we provide the simulation results of SGMW. Our results mainly include three parts. In Section 6.1, we check the interservice time performance of the policy. In Section 6.2, we compare the SGMW with baseline max weight scheduling policy. Both the total queue length and the max single queue length are selected as the evaluation criterion. In Section 6.3, we simulate the performance of SGMW under various arriving rate vectors. The vectors differ in the means and variances. The performance is evaluated by the statistics of the average appearance slot of tight phase in each interval. We assume $r_{i} = 1$ for all user i in this section.

6.1. Interservice Time Guarantee

To illustrate the interservice time performance of SGMW, we assume four groups of flows, each with 4/8/16/32 flows. The arriving rate of user i is $(1 / (N + ϵ)) + (ϵ / (N + ϵ)) * 0 . 5^{i}$ , where N is the number of flows, ϵ is the interservice time constraint, and i stands for the ith user. Such a rate vector is supportable by the system since its summation is less than 1. Our result considers both the max and average interservice time, as is shown in Figure 2.

Figure 2

Interservice time performance under various users.

It is observed in Figure 2 that the max interservice time never violates the constraint while N and ϵ vary. We also find that the max interservice time when $N = 64$ is equivalent to the constraint $N + ϵ$ , and this indicates the fact that some users with small rate can be scheduled only once in each interval. The average interservice time increases with ϵ since the number of users only scheduled in the tight phase keeps increasing under our setting of arriving rates.

In Figure 3, we investigate the performance of SGMW when the variance of arriving rate vector changes. The system is composed of 8 users, with $ϵ = 8$ . $λ_{i} = (1 / (N + ϵ)) + (ϵ / (N + ϵ)) * (1 - δ)^{i - 1} * δ$ for each user i. Obviously, the max interservice time in Figure 3 is staying below the constraint of $N + ϵ = 16$ as δ increases.

Figure 3

Interservice time performance under various arriving vectors.

6.2. Throughput Performance

This subsection illustrates the throughput performance of SGMW. We compare it with the max weight scheduling policy. The total queue length and max queue length are two indicators that define the loads of a system and a single user. In Figure 4, we check the performance under different number of users. We assume $ϵ = N$ , and $λ_{i} = (1 / (N + ϵ)) * 0.9 9^{i} + (ϵ / (N + ϵ)) * 0 . 5^{i}$ , where N is the number of users.

Figure 4

Throughput and interservice time performance under various users.

The total queue length of SGMW grows faster than max weight scheduling policy. This is due to the increasing number of users whose rate is less than $1 / (N + ϵ)$ . To schedule such users will cause the waste of bandwidth and a longer tight phase. The increasing in max queue length is also caused by this reason: some users have to keep waiting in the tight phase; then, their queue length grows rapidly. Meanwhile, some users perform bad in the interservice time under max weight scheduling, as can be found in the third graph of Figure 4.

In Figure 5, we investigate the throughput performance of SGMW when the variance of arriving rate vector changes. The setting of the system is the same with that of simulation in Figure 3. The two policies are the same when δ is relatively small since the weight of any user can always grow to the maximum before the tight phase occurs. As δ keeps increasing, a growing number of users with small rate will only be scheduled in tight phase. Then the throughput performance of SGMW is no longer optimal.

Figure 5

Throughput and interservice time performance under various arriving vectors.

As a result, we find that SGMW achieves interservice time guaranteed by potentially increasing the total and max queue length. SGMW will schedule users with very small queue length for meeting the interservice time constraints. This leads to the increasing of the max queue length since a user with max queue length may still wait for other users. The total length of the system is further increased when SGMW schedules the user with queue length smaller than its transmitting rate. But the total and max queue length are still finite in the ϵ-capacity region.

6.3. Adaptability under Various Rate Vectors

As we can see, the performance of SGMW is mainly determined by the proportion of time that SGMW is in the tight phase and the number of users that are scheduled in this phase. We evaluate them in this subsection. There are 8 flows in the system, with arriving rate $λ_{i} = (1 / (N + 2)) * 0 . 9^{i} + (2 / (N + 2)) * 0 . 5^{i}$ . The constraint ϵ varies from 2 to 32. In Figure 6, the number of intervals that have a tight phase decreases as ϵ grows. The tight phase disappears when $ϵ \geq 25$ . It indicates the fact that max weight scheduling policy can also ensure a loose constraint on interservice time. And SGMW is the same as max weight scheduling when ϵ is sufficiently large. In the second part of Figure 6, there is only one flow scheduled in the tight phase when $ϵ = 24$ , which means all the left flows can accumulate its weight to the maximum in a long loose phase.

Figure 6

Performance of SGMW under various interservice constraints.

7. Conclusion

This paper investigates the problem of interservice time guaranteed scheduling policy designing in wireless networks. We formalize the definition of modified capacity region with interservice time guarantee and propose a scheduling policy that meets the interservice time guarantee for all users. The scheduling policy is also proved to be throughput-optimal for the modified capacity region. Simulation results demonstrate that the scheduling policy has good performance on both the guarantee of interservice time and the stability of networks.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

The work in this paper was partially supported by the National Natural Science Foundation of China (NSFC) under Grant nos. 61190115 and 61033015.

References

Guo

Cai

Minimum-latency aggregation scheduling in wireless sensor network

Journal of Combinatorial Optimization 2014

10.1007/s10878-014-9748-7

2-s2.0-84901731672

Ding

Chen

Xing

Cheng

Localized fault-tolerant event boundary detection in sensor networks

Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′05)

March 2005

902 913

2-s2.0-25844521520

Cheng

Thaeler

Xue

Chen

TPS: a time-based positioning scheme for outdoor wireless sensor networks

Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′04)

March 2004

IEEE

2685 2696

10.1109/INFCOM.2004.1354687

2-s2.0-8344222870

Cheng

Cai

O(ε)-Approximation to physical world by sensor networks

Proceedings of the 32nd IEEE Conference on Computer Communications (INFOCOM ′13)

April 2013

3084 3092

2-s2.0-84883127209

10.1109/INFCOM.2013.6567121

Cheng

Gao

Cai

Approximate physical world reconstruction algorithms in sensor networks

IEEE Transactions on Parallel and Distributed Systems 2014

10.1109/TPDS.2013.2297121

Boukerche

Cheng

Linus

Energy-aware data-centric routing in microsensor networks

Proceedings of the 6th ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM ′03)

September 2003

42 49

2-s2.0-1542286866

Cai

Lin

Xue

Improved approximation algorithms for the capacitated multicast routing problem

Computing and combinatorics 2005 3595

Springer

136 145 Lecture Notes in Computer Science

MR2190278

10.1007/11533719_16

Tassiulas

Ephremides

Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

IEEE Transactions on Automatic Control 1992 37 12 1936 1948

10.1109/9.182479

MR1200609

Cheng

D.-Z.

Wang

Relay sensor placement in wireless sensor networks

Wireless Networks 2008 14 3 347 355

2-s2.0-43949136957

10.1007/s11276-006-0724-8

10.

Cheng

Huang

D.-Z.

A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks

Networks 2003 42 4 202 208

10.1002/net.10097

MR2016521

2-s2.0-2142846003

11.

Hou

I.-H.

Borkar

Kumar

P. R.

A theory of QoS for wireless

Proceedings of the 28th Conference on Computer Communications (INFOCOM ′09)

April 2009

IEEE

486 494

10.1109/INFCOM.2009.5061954

2-s2.0-70349690122

12.

Hou

I.-H.

Kumar

P. R.

Admission control and scheduling for QoS guarantees for variable-bit-rate applications on wireless channels

Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′09)

May 2009

New Orleans, La, USA

175 184

10.1145/1530748.1530772

2-s2.0-70450159043

13.

Hou

I.-H.

Kumar

P. R.

Scheduling heterogeneous real-time traffic over fading wireless channels

Proceedings of the IEEE INFOCOM

March 2010

IEEE

1 9

10.1109/INFCOM.2010.5462090

2-s2.0-77953310199

14.

Hou

I. H.

Kumar

P. R.

Utility-optimal scheduling in time-varying wireless networks with delay constraints

Proceedings of the 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing

September 2010

ACM

31 40

10.1145/1860093.1860099

2-s2.0-78649248360

15.

Jaramillo

J. J.

Srikant

Optimal scheduling for fair resource allocation in ad hoc networks with elastic and inelastic traffic

Proceedings of IEEE INFOCOM

2010

1 9

16.

Jaramillo

J. J.

Srikant

Ying

Scheduling for optimal rate allocation in ad hoc networks with heterogeneous delay constraints

IEEE Journal on Selected Areas in Communications 2011 29 5 979 987

10.1109/JSAC.2011.110508

2-s2.0-84055176710

17.

Kang

Wang

Jaramillo

J. J.

Ying

On the performance of largest-deficit-first for scheduling real-time traffic in wireless networks

Proceddings of the 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′13)

August 2013

ACM

99 108

10.1145/2491288.2491298

2-s2.0-84882942305

18.

Eryilmaz

Throughput-optimal wireless scheduling with regulated inter-service times

Proceedings of the 32nd IEEE Conference on Computer Communications (INFOCOM ′13)

April 2013

Turin, Italy

2616 2624

10.1109/INFCOM.2013.6567069

2-s2.0-84883061512

19.

Eryilmaz

Heavy-traffic-optimal scheduling with regular service guarantees in wireless networks

Proceedings of the 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′13)

August 2013

79 87

10.1145/2491288.2491304

2-s2.0-84883011958

20.

Jaiswal

N. K.

Priority Queues 1968

New York, NY, USA

Elsevier

21.

Bui

L. X.

Sanghavi

Srikant

Distributed link scheduling with constant overhead

IEEE/ACM Transactions on Networking 2009 17 5 1467 1480

10.1109/TNET.2009.2013621

2-s2.0-70350534448

22.

Tan

Srikant

Q-CSMA: queue-length-based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks

IEEE/ACM Transactions on Networking 2012 20 3 825 836

10.1109/TNET.2011.2177101

2-s2.0-84862566458

23.

Liu

Chong

E. K. P.

Shroff

N. B.

A framework for opportunistic scheduling in wireless networks

Computer Networks 2003 41 4 451 474

2-s2.0-0037444521

10.1016/S1389-1286(02)00401-2

24.

Sakai

Togasaki

Yamazaki

A note on greedy algorithms for the maximum weighted independent set problem

Discrete Applied Mathematics 2003 126 2-3 313 322

10.1016/S0166-218X(02)00205-6

MR1948221

2-s2.0-84867932159

25.

Wan

P.-J.

Frieder

Jia

Yao

Tang

Wireless link scheduling under physical interference model

Proceedings of the IEEE INFOCOM

April 2011

Shanghai, China

IEEE

838 845

10.1109/INFCOM.2011.5935307

2-s2.0-79960857901

26.

Basagni

Finding a maximal weighted independent set in wireless networks

Telecommunication Systems 2001 18 1–3 155 168

10.1023/A:1016747704458

2-s2.0-23044529826

27.

Hoepman

J.-H.

Simple distributed weighted matchings

http://arxiv.org/abs/cs/0410047v1

28.

Joo

Lin

Ryu

Shroff

N. B.

Distributed greedy approximation to maximum weighted independent set for scheduling with fading channels

Proceedings of the 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′13)

August 2013

89 98

10.1145/2491288.2491297

2-s2.0-84883035120