A Deadline-Aware and Distance-Aware Packet Scheduling Algorithm for Wireless Multimedia Sensor Networks

Abstract

We propose a wireless differentiated queuing service (WDQS) algorithm to meet the diverse delay requirements in wireless multimedia sensor networks (WMSNs). WDQS adopts novel latest departure time (LDT) scheduling criteria to differentiate forwarding emergency by considering the packets’ lifetime, the known delay it has already experienced, and the remaining delay it will experience. We also propose an effective approach to estimate the unknown delay for the remaining journey without any message overhead by exploiting the query mechanism of the sink. We further discuss analytically the packet's lifetime setting to meet the end-to-end (e2e) delivery requirement. The simulation results verify our analytical discussion and show performance improvements in terms of e2e delay and packet drop rate.

1. Introduction

The integration of low-power wireless networking technologies with inexpensive hardware such as complementary metaloxide semiconductor (CMOS) cameras and microphones is now enabling the development of WMSNs, where wirelessly interconnected smart devices are deployed to retrieve video and audio streams, still images, and scalar sensor data [1]. WMSNs promise a wide range of potential applications in both civilian and military areas, such as surveillance sensor networks, law-enforcement reports, traffic control systems, advanced health care delivery, automated assistance to elderly telemedicine, and industrial process control [2].

A WMSN often consists of a large number of sensors, which constantly generate all kinds of traffic, including target detection data, measurement data, and video flows. The packets of these event-driven data belong to different levels of emergencies and have their own valid periods. Thus, the packets are required to be delivered to the sink before their expiration deadlines which are their quality-of-service (QoS) requirements. There are two challenges for WMSNs to support a huge amount of data that has diverse deadlines. First, the sensor nodes have very limited resources of energy supply, bandwidth, memory, and processing capability due to the physically small size of sensors. The limited resources require a fair and efficient utilization. Second, the packets with the same level of emergency have the same deadline requirement. The packets from the sensors which are far from the sink have to traverse more hops to reach the sink than the packets from the sensors which are close to the sink. Thus the delay requirement of remote event report packets at every intermediate node is more stringent than that of nearby event report packets.

Packet scheduling is an important scheme to address the QoS requirement issues in WMSNs. Generally, packet scheduling assigns priorities to traffic flows with QoS considerations. Then packets are queued and scheduled according to the assigned priorities, which are related to the effective periods of event reports. If a packet cannot be sent to the sink in time, it will be discarded, resulting in high packet drop rate. With the limited resource in WMSNs, the packets of the most emergent event, which have the closest deadline, should be serviced with the highest priority. On the other hand, the geographic distribution of sensors also has impact on the scheduling priorities. The delay requirement of the packets from the remote sensors is more stringent than that of nearby event report packets, so they should be serviced with higher priority. For these considerations, packet scheduling should be both deadline-aware and distance-aware [3].

Multiple kinds of packet scheduling algorithms have been already proposed. However most of them are not both deadline-aware and distance-aware. We find that our previous proposed differentiated queueing scheduling (DQS) fits WMSNs well. DQS is first put forward for the traditional wired network in [4]. It has been extended into wireless area in [5] and been improved in [6]. DQS queues packets at intermediate node by their LDT. The smaller the LDT, the higher the priority. A packet's LDT is determined by its lifetime, the known delay which it has already experienced and the remaining delay which it will experience. A packet's deadline is determined by the difference between the known delay and its lifetime. The known delay and remaining delay correspond to the distance from its source to the sink since our study is based on geographic routing. Thus the packet's priority is related to its deadline and the distance from its source to the destination. We can see DQS is both deadline-aware and distance-aware to meet the requirements of WMSNs. But how to estimate the unknown remaining delay and how to set the packet's lifetime have not been resolved in DQS.

In this paper, we propose a new packet scheduling algorithm: wireless differentiated queuing service (WDQS) for WMSNs. WDQS inherits the enqueue principle of DQS and resolves these two problems of DQS. Our contributions include the following.

(i)

Effective delay estimation approach. We propose an effective delay estimation for the remaining journey of a packet to implement WDQS by exploiting the unique characteristics of WMSNs. Our approach introduces no extra message overhead and energy consumption into WMSNs.

(ii)

Packet lifetime setting and performance analysis. We discuss the packet's lifetime setting approach and get the general setting conditions. We also analyze the e2e performance of traffic in WMSNs when applying WDQS.

The reminder of this paper is organized as follows. Section 2 presents the related works. Section 3 describes the system model. Section 4 proposes WDQS including scheduling principle, remaining delay estimating approach, packet's lifetime setting approach, and algorithm implementation. Section 5 verifies WDQS via simulations. Finally, the paper is summarized in Section 6.

2. Related Works

Multiple kinds of packet scheduling algorithms have been already proposed for traditional networks [7]. Priority Queuing (PQ) [8], Queue Length Threshold (QLT) [9], and proportional differentiation approaches such as Hybrid Proportional Delay (HPD) [10] and Waiting-time Priority (WTP) [11] are based on static priority. Earliest Deadline First (EDF) [12] assigns packets with static deadlines. It will service the packets before their deadlines to guarantee their delay requirements. In the core stateless algorithms such as Core Stateless Fair Queuing (CSFQ) [13], all the packets are tagged by the edge nodes and the core nodes schedule the packet by its tag.

Few existing packet scheduling algorithms are dedicated to WMSNs. The literature [14, 15] applied EDF to WMSNs. The algorithms proposed in the literature [16] determine a packet's priority according to its elapsed hops. The reference [17] categorized dynamically real-time packets with high priority to preemptive data packets in the queues. Some algorithms proposed in the literature [18–20] focus on fairness and energy consumption rather than deadline-aware and distance-aware scheduling. Velocity Monotonic Scheduling (VMS) [3] assigns the priority of a packet based on its requested velocity which is the ratio of the packet's deadline and elapsed time to its Euclidean distance from the arriving node to the destination. It is one of the most suitable algorithms for WMSNs so far. It is both deadline-aware and distance-aware. However the distance is the Euclidean distance rather than the distance which a packet really passed.

3. System Model

We study packet scheduling algorithms on multitier heterogeneous architecture which is shown in Figure 1 [21], where the high tier is composed of high-end cameras, the middle tier is composed of low-end image sensors, and the bottom tier is composed of scalar sensors. Sensors from different tiers work in a coordinated way to detect and identify targets. When the scalar sensors or image sensors find some targets entering, the high-end cameras start to shoot and identify the targets through image processing.

Figure 1

Multitier heterogeneous architecture of WMSNs.

The number of scalar and image sensors is large in WMSNs since they have simple circuit and low costs. These two types of sensors generally have the same task that is target detection. In this case, they collectively have the same traffic characteristics and requirements. Although each of them generates small amount of data and requires low bandwidth for communications, the aggregated traffic from these kinds of sensors is not ignorable. There are fewer camera sensors in WMSNs. However, they have stringent QoS requirement for their real-time video traffic. The real-time and non-real-time traffic often coexists in the same WMSNs. How to provide QoS guarantee for the mixed traffic for WMSNs is an important research issue [22].

4. Wireless Differentiated Queueing Service (WDQS)

As mentioned in Section 1, WDQS inherits the enqueue principles of DQS and resolves the problems which DQS has to face. In this section we will first describe the enqueue principles of DQS, then propose a delay estimating approach for the remaining journey of a packet, next put forward the packet lifetime setting conditions, at last describe the implementation of WDQS.

WDQS is based on the following assumptions. Any application should have a maximum e2e delay (D). If an application can have an arbitrary D, it can be set to a certain value artificially. D should be treated as the lifetime of the associated packet. If a packet is confirmed that its lifetime has expired, it should be dropped immediately.

The notions in Table 1 are used to present our proposed WDQS.

Table 1

Notations for WDQS.

Sym.	Value
a	Report packet's arrival time
g	Report packet's departure time at the source
$μ_{sink}$	Querying packet's departure time
e	Report packet's latest departure time
D	Packet's lifetime
$μ$	Querying packet's e2e delay

4.1. Enqueue Principle of DQS

Suppose that parameters with subscript “i” denote that they are for node i. To simplify the discussion, the propagation delay is not addressed since it is a constant for a given path. Therefore, for a path consisting of n nodes, we can have the following relation for the sojourn of a packet arriving at node i:

\begin{array}{l} {\hat{d}}_{i} = D - \sum_{j = 1}^{i - 1} ‍ {\tilde{d}}_{j} - \sum_{j = i + 1}^{n} ‍ {\tilde{d}}_{j} \\ = D - (a - g) - \sum_{j = i + 1}^{n} ‍ {\tilde{d}}_{j}, \end{array}

(1)

where ${\tilde{d}}_{j}$ is the actual delay that the packet experiences at node j, ${\hat{d}}_{i}$ is the effective packet's maximum delay allowed at node i subject to its e2e delay, $\sum_{j = 1}^{i - 1} ‍ {\tilde{d}}_{j}$ is the delay that the packet has already experienced before it arrives at node i, and $\sum_{j = i + 1}^{n} ‍ {\tilde{d}}_{j}$ is the delay that the packet will experience after it leaves node i. So the LDT e of this packet at node i is given by

\begin{array}{l} e = a + {\hat{d}}_{i} \\ = D + g - \sum_{j = i + 1}^{n} ‍ {\tilde{d}}_{j} . \end{array}

(2)

DQS will enqueue packets according to the value of e at node i. Thus, packets with smaller e will be serviced earlier. In multihop WMSNs, $\sum_{j = 1}^{i} {\tilde{d}}_{j}$ depends on the distance from the source node to node i and $\sum_{j = i + 1}^{n} {\tilde{d}}_{j}$ depends on the remaining distance from node i to the sink. According to (1) the longer the distance from the source to the sink, the smaller the value of e; thus DQS is distance-aware. Also according to (2), the smaller the value of D and g, the smaller the value of e, so DQS is deadline-aware. Thus DQS is one of the most suitable packet scheduling algorithms of WMSNs.

4.2. Delay Estimation

From what was mentioned, we can see that the value of LDT of a packet (i.e., e) is critical to implement WDQS. It is difficult to implement WDQS since although the value of a, g, and D is known, the delay for the remaining journey (i.e., $\sum_{j = i + 1}^{n} ‍ {\tilde{d}}_{j}$ ) can not be known in advance and is difficult to evaluate at node i. One possible approach is constantly sending probe packets and estimating the delay for the remaining journey by the replied messages [5]. This approach introduces extra message overhead and consumes more energy, which are both limited resources in WMSNs. We exploit the unique characteristics of WMSNs to estimate the delay for the remaining journey as follows.

There are some characteristics of WMSNs different from traditional wireless networks:

(1)

the destination of sensors’ packets are the same sink;

(2)

the distance between sensor nodes and the sink is fixed;

(3)

the sink sends out querying packet periodically;

(4)

sensors’ position information is available; thus,

(5)

geolocation based shortest path routing can be used for data transmissions.

We can evaluate the value of e more easily by taking advantage of these characteristics in WMSNs. Because of the characteristics $(1)$ , $(2)$ , and $(4)$ , the shortest path from node i to the sink is constant. According to characteristic $(5)$ , $\sum_{j = i + 1}^{n} ‍ {\tilde{d}}_{j}$ is the delay along the remaining shortest path. According to characteristic $(3)$ , the querying packets will arrive at node i along the shortest path from the sink. So we can evaluate $\sum_{j = i + 1}^{n} ‍ {\tilde{d}}_{j}$ by the e2e delay of the querying packet from the sink to node i.

Suppose $μ_{sink}$ is the querying packet's departure time and $μ_{i}$ is the querying packet's arrival time at node i. So the e2e delay of a querying packet from the sink to node i is given by

\begin{matrix} μ = μ_{i} - μ_{sink} . \end{matrix}

(3)

The sink sends out querying packets periodically, and the value of μ is updated accordingly. In practice, we adopt a weighted average approach to update the delay for the remaining journey μ; that is,

\begin{matrix} μ_{d} = (1 - α) μ_{d} + α μ, \end{matrix}

(4)

where $α (0 \leq α \leq 1)$ is the smoothing factor. On the first arriving of the query packet, we set $μ_{d} = μ$ . $μ_{d}$ is updated by (4) on receiving the querying packets.

With the approach in (4), we can estimate the delay from node i to the sink as

\begin{matrix} \sum_{j = i + 1}^{n} ‍ {\tilde{d}}_{j} = μ_{d} . \end{matrix}

(5)

Together with (2), the LDT for a packet is computed as follows:

\begin{matrix} e = D + g - μ_{d} . \end{matrix}

(6)

By (6), Packets with longer distance to the sink and later deadline will be serviced by WDQS with a higher priority. Note that the estimation of the delay for the remaining journey exploits the existing sink's query mechanism and thus introduces no extra message overhead and resource consumption to WMSNs.

4.3. Packets’ Lifetime Setting and Performance Analysis

The real-time packets have stringent delay requirements so they must have higher priority than the scalar packets at the intermediate nodes. WDQS makes sure that all the real-time packets are delivered in time.

According to (6) only the packet's lifetime can be set artificially to affect its position in the queue of WDQS and further affect its QoS. If a real-time packet is serviced earlier than other scalar packets, its lifetime D must be set to a smaller value. However, if D is too small it might be discarded before reaching the destination. So in this section, we will discuss the approaches of lifetime setting. Then we will also analyze the forwarding ratio and e2e delay performance with these approaches. In the following discussion, we assume that the arrival process functions of the scalar packet and the real-time packet are known, and the notions in Table 2 are used.

Table 2

Notations for WDQS.

Sym.	Value
$a_{c i} (t)$	Scalar packet's arrival rate at node i
$C_{i}$	Forwarding rate of node i
$g_{T}$	g of real-time packets
$e_{T}$	e of real-time packets
$D_{T}$	D of real-time packets
$δ_{T}$	Forwarding ratio of real-time packets
$d_{T}$	Actual e2e delay of real-time packets
$A_{T i} (t)$	Real-time packet's arrival process
$a_{T i} (t)$	Real-time packet's arrival rate
$L_{i}$	Buffer length of node i
$g_{c}$	g of scalar packets
$e_{c}$	e of scalar packets
$D_{c}$	D of scalar packets
$δ_{c}$	Forwarding ratio of scalar packets
$d_{c}$	Actual e2e delay of scalar packets

4.3.1. Lifetime Setting

According to (6), $e_{T}$ and $e_{c}$ are given by

\begin{matrix} e_{T} = D_{T} + g_{T} - μ_{d}, \\ e_{c} = D_{c} + g_{c} - μ_{d} . \end{matrix}

(7)

In order to queue real-time packets always in front of scalar packets, there must be

\begin{matrix} e_{T} < e_{c}; \end{matrix}

(8)

that is

\begin{matrix} D_{T} + g_{T} < D_{c} + g_{c}, \end{matrix}

(9)

where $D_{T} < D_{c}$ can be set artificially. But if $g_{c}$ is small enough, there may be $e_{T} > e_{c}$ , and the real-time packet would be inserted into the queue behind some scalar packets. We will discuss how to set the lifetime of real-time packets and the scalar packets to meet the condition of $e_{T} < e_{c}$ in the following network scenarios.

(1)

If $a_{T_{i}} (t) > C_{i}$ , the bandwidth can not satisfy the requirement of real-time communications. The network can not support this case.

(2)

If $a_{T_{i}} (t) + a_{c i} (t) < C_{i}$ , there are adequate bandwidths for node i to forward all the packets. All the packets’ QoS requirements are met.

(3)

Case of $a_{T_{i}} (t) + a_{c i} (t) \geq C_{i}$ but $a_{T_{i}} (t) < C_{i}$ . The packet lifetime setting approach in this case is much more complicated, which is discussed in detail next.

Our lifetime setting approach for case $(3)$ is making $D_{c}$ and $D_{T}$ meet the following condition expression:

\begin{matrix} D_{c} - D_{T} > \sum_{j = 1}^{n} ‍ \frac{L_{j}}{C_{j} - a_{T_{j}} (t)} . \end{matrix}

(10)

It is proved as follows.

Because $i \leq n$ , we have

\begin{matrix} \sum_{j = 1}^{n} ‍ \frac{L_{j}}{C_{j} - a_{T_{j}} (t)} > \sum_{j = 1}^{i - 1} ‍ \frac{L_{j}}{C_{j} - a_{T_{j}} (t)} . \end{matrix}

(11)

If (10) is met, we get

\begin{matrix} D_{c} - D_{T} > \sum_{j = 1}^{i - 1} ‍ \frac{L_{j}}{C_{j} - a_{T_{j}} (t)} . \end{matrix}

(12)

Suppose e of every real-time packet is smaller than e of all the scalar packets which are waiting in the queue; the forwarding rate for scalar packets at node i is $C_{i} - a_{T_{i}} (t)$ . Suppose again that a scalar packet arrives at node i with $l_{i}$ packets already in the buffer queue; the queueing delay of this scalar packet at node i will be

\begin{matrix} {\tilde{d}}_{i} \leq \frac{l_{i}}{C_{i} - a_{T_{i}} (t)} \leq \frac{L_{i}}{C_{i} - a_{T_{i}} (t)} . \end{matrix}

(13)

With (12), we get

\begin{matrix} D_{c} - D_{T} > \sum_{j = 1}^{i - 1} ‍ {\tilde{d}}_{i} . \end{matrix}

(14)

This scalar packet's experienced delay from the source to node i is $\sum_{j = 1}^{i - 1} ‍ {\tilde{d}}_{j}$ . We can then infer its departure time at the source as

\begin{matrix} g_{c} = a - \sum_{j = 1}^{i - 1} ‍ {\tilde{d}}_{j} . \end{matrix}

(15)

When a real-time packet is always serviced first, there is no queuing delay for it. So if a real-time packet arrives at node i at the same time, its departure time is $g_{T} \approx a$ since the propagation delay is very small. So

\begin{matrix} g_{T} - g_{c} \approx \sum_{j = 1}^{i - 1} ‍ {\tilde{d}}_{j} . \end{matrix}

(16)

With (14) there will be $D_{c} + g_{c} > D_{T} + g_{T}$ ; that is, $e_{T} < e_{c}$ .

Thus we prove that if (10) is met, $e_{T} < e_{c}$ .

4.3.2. Performance Analysis

Now let us look into the performance of real-time traffic. In our analysis, we study the metrics of the forwarding ratio and the e2e delay. The forwarding ratio is defined as the ratio of the forwarding rate to the arriving rate.

Obviously, when (10) is met, all the real-time packets will be serviced earlier than the scalar packets. Thus, all arriving real-time packets are forwarded and there is no queueing delay; that is, $δ_{T} = 1$ and $d_{T} = 0$ . When (10) is not met, there exists a critical queue length $l_{cr}$ determining the enqueueing order of real-time and scalar packets. If the queue length is less than $l_{cr}$ , the real-time packets are always queued in front of the scalar packets. Otherwise, some scalar packets will go ahead of a real-time packet. Suppose the time reaching $l_{cr}$ is $t_{cr}$ , when $e_{T} = e_{c}$ .

The queue length grows over time. At the time $t_{cr}$ ,

\begin{matrix} l_{cr} = \int_{0}^{t_{cr}} ‍ a_{T i} (t) d t + \int_{0}^{t_{cr}} ‍ a_{c i} (t) d t - C_{i} t_{cr} . \end{matrix}

(17)

According to (6), when $D_{c} + g_{c} = D_{T} + g_{T}$ , there would be $e_{T} = e_{c}$ . It means at $t_{cr}$ , $g_{T} - g_{c} = D_{c} - D_{T}$ . What is more is that there are only scalar packets in the queue before $t_{cr}$ . From this perspective,

\begin{matrix} l_{cr} = \int_{0}^{D_{c} - D_{T}} ‍ a_{c i} (t) d t . \end{matrix}

(18)

Then,

\begin{matrix} \int_{0}^{t_{cr} - D_{c} + D_{T}} ‍ a_{c i} (t) d t + \int_{0}^{t_{cr}} ‍ a_{T i} (t) d t - C_{i} t_{cr} = 0 . \end{matrix}

(19)

We can get the value of $t_{cr}$ from the above equation by applying the specific forms of arrival rate. Based on $t_{cr}$ , we study the following two cases.

(i)

$t \leq t_{cr}$ : the performance of this case is the same as that in the case satisfying (10).

(ii)

$t > t_{cr}$ : real-time packets and scalar packets will share the bandwidth in this case. The forwarding rates for real-time and scalar packets are $a_{T_{i}} (t) C_{i} / (a_{c i} (t) + a_{T_{i}} (t))$ and $a_{c i} (t) C_{i} / (a_{c i} (t) + a_{T_{i}} (t))$ . Thus, their forwarding ratios are

\begin{matrix} δ_{T} = \frac{C_{i}}{a_{c i} (t) + a_{T_{i}} (t)}, \end{matrix}

(20)

\begin{matrix} δ_{c} = \frac{C_{i}}{a_{c i} (t) + a_{T_{i}} (t)}, \end{matrix}

(21)

respectively, subject to

\begin{matrix} d_{T} < D_{T}, \end{matrix}

(22)

\begin{matrix} d_{c} < D_{c} . \end{matrix}

(23)

4.4. Implementation of WDQS

In this subsection, we discuss the implementation of WDQS in WMSNs.

WDQS requires a slight modification to the packet format. Figure 2 shows the packet format expected by WDQS. The field TYPE distinguishes the packet and is one of the following: report packet and querying packet. SP refers to the position of its source node. All the report packets’ destinations are the sink. Querying packets come from the sink and they are broadcasting packets. So we need not indicate the destination position in the packet header. In the report packets’ header, $μ_{sink}$ is zero, and D and g are set by sensor nodes. In querying packets’ header, $μ_{sink}$ is set by the sink. LEN is the length of the entire packet and CRC is the checksum.

Figure 2

Packet format for WDQS implementation.

Figure 3 shows the calculating process of e when a packet arrives at node i.

Figure 3

Calculation process of the LDT e at node i.

5. Simulation

We implement and study WDQS in NS2. 200 sensor nodes were randomly positioned in a 100 × 100 sensor field. Node parameters such as radio range were carefully chosen to mirror typical sensor mote values [23]. One of these nodes was chosen as the sink to which all source data was sent. Real-time packets’ source nodes and scalar packets’ source nodes were randomly chosen and generate Poission traffics. In order to communicate source data to the sink, we employed a simple CSMA/CA based MAC protocol and Geographic and Energy Aware Routing (GEAR) [24]. The parameter settings are shown in Table 3. According to the routing mechanism of GEAR, the area of sensor fields, and the radio range of a sensor node, the number of nodes of the longest path from source to sink is $n = 3$ . With the parameters in Table 3, we have the following conditional expression according to (10):

\begin{matrix} D_{c} - D_{T} > 75 ms . \end{matrix}

(24)

Table 3

Parameter settings in the simulations.

Sym.	Value
Area of sensor field	100 * 100 m²
Radio range of a sensor node	40 m
IFQ length (L)	4 kb
Receive power	0.395 W
Mean arriving rate of real-time packet ( $λ_{T}$ )	320 kbps
Forwarding rate (C)	480 kbps
Number of sensor nodes	200
Packet length	30 bytes
Transmit power	0.66 W
Decision interval	10 sec
Mean arriving rate of scalar packet ( $λ_{c}$ )	240 kbps

We conduct two sets of experiments. The first set of experiments verify the effectiveness of lifetime setting condition. The second set of experiments compare WDQS with some famous packet scheduling algorithms.

5.1. Experiment Set 1

In this set of experiments $D_{c}$ is fixed and $D_{c} = 200 ms$ . We conduct 9 experiments to study packets’ e2e delay and drop rate with the change of $D_{T}$ . The value of $D_{T}$ of every experiment is shown in Table 4. In the table, the first three $D_{T}$ meet (10), the middle three $D_{T} < D_{c}$ but do not meet (10), and the last three $D_{T}$ are much larger than $D_{c}$ . The results are shown in Figures 4 and 5. Figure 4 shows the e2e delay of real-time packets and scalar packets. Figure 5 shows the packet drop rate. From the simulation results we find the following.

(i)

In the first three experiments, the e2e delay of real-time packets is very small and that of scalar packets is much larger. The drop rate of real-time packets is much smaller than that of scalar packets. That is because when (10) is met, real-time packets are all forwarded with higher priority.

(ii)

In the middle three experiments, the e2e delay of real-time packets increases and that of scalar packets decreases. Drop rates of these two kinds of packets become close to each other. That is because when $D_{T} < D_{c}$ but do not meet (10), packets are fair forwarded, real-time packets and scalar packets share the bandwidth equitably.

(iii)

In the last three experiments, the e2e delay of real-time packets increases further and that of scalar packets drops further. The drop rate of real-time packets becomes much larger and that of scalar packets becomes smaller. That is because when $D_{T}$ is much larger than $D_{c}$ , scalar packets are forwarded with higher priority while real-time packets only take the remaining bandwidth.

From the simulation results, we can see the conditional expression (24) is reasonable. That is to say the conditional expression (10) is suitable for WMSN applications.

Table 4

The value of $D_{T}$ .

Experiment	1	2	3	4	5	6	7	8	9
Value of $D_{T}$ (ms)	60	80	100	140	160	180	280	300	320

Figure 4

Packet's e2e delay.

Figure 5

Packet drop rate.

5.2. Experiment Set 2

In this set of experiments we compare WDQS with FCFS, EDF, DM, and VMS. FCFS is selected as an opponent in order to show the great improvements of network performances made by WDQS compared with nonpriority scheduling algorithms. EDF and DM are famous scheduling algorithms, priorities of which are all related to the packet's lifetime. VMS is one of the most suitable algorithms for WMSNs so far as mentioned in Section 2, priorities of which are also related to the packet's lifetime. We compare with these algorithms in order to show the performance improvements compared with the same type of algorithms. We let $D_{c} = 200 ms$ and $D_{T} = 100 ms$ which meet (10). We simulate three times to study e2e delay and drop rate with the change of $λ_{T}$ . Other parameters and experiment topology are the same as the first set of experiments. The results are shown in Figures 6 and 7. From the simulation results we find that the e2e delay and the drop rate of WDQS are the smallest. Packet's e2e delay and drop rate of FCFS are much larger than those of WDQS. That is to say WDQS improves the network performance greatly and it has better performance than other packet scheduling algorithms which are chosen.

Figure 6

Packet's e2e delay comparison.

Figure 7

Packet drop rate comparison.

All in all, the simulation results in this section show that our proposed WDQS improves the network performances in WMSNs and the packet lifetime setting approach is effective.

6. Conclusion

We have studied the QoS issues in WMSNs and propose a WDQS algorithm for packet scheduling to support the QoS requirements of WMSN applications. We put forward an estimating approach of remaining delay and a conditional expression of lifetime setting in order to calculate the LDT of a packet which affects the packet's position in the queue. WDQS is deadline-aware and distance-aware by exploiting the unique characteristics of WMSNs to guarantee the end-to-end delay of packets with diverse QoS requirements in WMSNs. Simulation results show the performance improvements in provisioning e2e QoS in WMSNs.

Footnotes

Conflict of Interests

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

Acknowledgments

This work was supported in part by the 973 Programs of China (no. 2011CB707003), the NSFC (nos. 61302058 and 61201256), the Fundamental Research Funds for the Central Universities of China (no. 2014ZZ0030), the Key Grant Project of Chinese Ministry of Education (no. 313021), and the NCET Program (no. NCET-12-0196).

References

Akyildiz

I. F.

Melodia

Chowdury

K. R.

Wireless multimedia sensor networks: a survey

IEEE Wireless Communications 2007 14 6 32 39

10.1109/mwc.2007.4407225

2-s2.0-37249066703

Akyildiz

I. F.

Melodia

Chowdhury

K. R.

Wireless multimedia sensor networks: applications and testbeds

Proceedings of the IEEE 2008 96 10 1588 1605

10.1109/JPROC.2008.928756

2-s2.0-55549094400

Blum

B. M.

Abdelzaher

T. F.

Stankovic

J. A.

RAP: a real-time communication architecture for large-scale wireless sensor networks

Proceedings of the 8th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '02)

September 2002

55 66

10.1109/rttas.2002.1137381

2-s2.0-84884315660

Jiang

Granular differentiated queueing services for qos: structure and cost model

ACM SIGCOMM Computer Communication Review 2005 35 2 13 22

10.1145/1064413.1064416

Teng

Jiang

Wei

Liu

A cross-layer implementation of differentiated queueing service (DQS) for wireless mesh networks

Proceedings of the IEEE Vehicular Technology Conference (VTC '08)

May 2008

Singapore

IEEE

2233 2237

10.1109/vetecs.2008.497

2-s2.0-47749111367

Jiang

Differentiated queueing service (DQS) for granular QoS

Future Wireless and Optical Networks 2012

Berlin, Germany

Springer

73 87

10.1007/978-1-4471-2822-9_5

Hasegawa

Matsuo

Murata

Miyahara

Comparisons of packet scheduling algorithms for fair service among connections on the Internet

Journal of High Speed Networks 2003 12 1 1 27

2-s2.0-0037247930

Jacobson

Nichols

Poduri

An expedited forwarding phb

RFC 1999 2598

Choudhury

A. K.

Hahne

E. L.

Dynamic queue length thresholds for shared-memory packet switches

IEEE/ACM Transactions on Networking 1998 6 2 130 140

10.1109/90.664262

2-s2.0-0032047476

10.

Dovrolis

Stiliadis

Ramanathan

Proportional differentiated services: delay differentiation and packet scheduling

ACM SIGCOMM Computer Communication Review 1999 29 4 109 120

10.1145/316194.316211

11.

Dovrolis

Stiliadis

Relative differentiated services in the internet: issues and mechanisms

ACM SIGMETRICS Performance Evaluation Review 1999 27 1 204 205

12.

Andrews

Probabilistic end-to-end delay bounds for earliest deadline first scheduling

Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '00)

March 2000

Tel Aviv, Israel

603 612

2-s2.0-0033876311

10.1109/INFCOM.2000.832234

13.

Stoica

Shenker

Zhang

Core-stateless fair queueing: a scalable architecture to approximate fair bandwidth allocations in high-speed networks

IEEE/ACM Transactions on Networking 2003 11 1 33 46

10.1109/tnet.2002.808414

2-s2.0-0037295811

14.

Xiahou

S. J.

X. Y.

A survey of studying on task scheduling mechanism for TinyOS

Proceedings of the 4th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM '08)

October 2008

Dalian, China

1 4

10.1109/wicom.2008.960

15.

Mizanian

Hajisheykhi

Baharloo

Jahangir

A. H.

Race: a real-time scheduling policy and communication architecture for large-scale wireless sensor networks

Proceedings of the 7th Annual Communication Networks and Services Research Conference (CNSR '09)

May 2009

458 460

10.1109/cnsr.2009.84

2-s2.0-67650340173

16.

Lee

E.-M.

Kashif

Lee

D.-H.

Kim

I.-T.

Park

M.-S.

Location based multi-queue scheduler in wireless sensor network

Proceedings of the 12th International Conference on Advanced Communication Technolog (ICACT '10)

February 2010

551 555

2-s2.0-77952628596

17.

Nasser

Karim

Taleb

Dynamic multilevel priority packet scheduling scheme for wireless sensor network

IEEE Transactions on Wireless Communications 2013 12 4 1448 1459

10.1109/twc.2013.021213.111410

2-s2.0-84877729089

18.

Tirkawi

Fischer

Adaptive tasks balancing in wireless sensor networks

Proceedings of the 3rd International Conference on Information and Communication Technologies: From Theory to Applications (ICTTA '08)

April 2008

1 6

10.1109/ictta.2008.4530162

2-s2.0-49149092487

19.

Yang

Ulukus

Optimal packet scheduling in an energy harvesting communication system

IEEE Transactions on Communications 2012 60 1 220 230

10.1109/TCOMM.2011.112811.100349

2-s2.0-84857361411

20.

Capozzi

Piro

Grieco

L. A.

Boggia

Camarda

Downlink packet scheduling in LTE cellular networks: key design issues and a survey

IEEE Communications Surveys & Tutorials 2013 15 2 678 700

10.1109/surv.2012.060912.00100

2-s2.0-84877584112

21.

Melodia

Akyildiz

I. F.

Research challenges for wireless multimedia sensor networks

Distributed Video Sensor Networks 2011

London, UK

Springer

233 246

10.1007/978-0-85729-127-1_16

22.

Yaghmaee

M. H.

Adjeroh

D. A.

Priority-based rate control for service differentiation and congestion control in wireless multimedia sensor networks

Computer Networks 2009 53 11 1798 1811

10.1016/j.comnet.2009.02.011

2-s2.0-67349276016

23.

Sankarasubramaniam

Akan

Ö. B.

Akyildiz

I. F.

ESRT: event-to-sink reliable transport in wireless sensor networks

Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing

June 2003

ACM

177 188

2-s2.0-0242443772

24.

Govindan

Estrin

Geographical and energy aware routing: a recursive data dissemination protocol for wireless sensor networks

2001 ucla/csd-tr-01-0023

UCLA Computer Science Department