# Analyzing Multimode Wireless Sensor Networks Using the Network Calculus

Authors: Xi Jin; Nan Guan; Jintao Wang; Peng Zeng
Journal: Journal of Sensors
 (2015)

---

## Abstract

The network calculus is a powerful tool to analyze the performance of wireless sensor networks. But the original network calculus can only model the single-mode wireless sensor network. In this paper, we combine the original network calculus with the multimode model to analyze the maximum delay bound of the flow of interest in the multimode wireless sensor network. There are two combined methods A-MM and N-MM. The method A-MM models the whole network as a multimode component, and the method N-MM models each node as a multimode component. We prove that the maximum delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM. Experiments show that our proposed methods can significantly decrease the analytical delay bound comparing with the separate flow analysis method. For the large-scale wireless sensor network with 32 thousands of sensor nodes, our proposed methods can decrease about 70% of the analytical delay bound.


---

## Body

## 1. Introduction

Network calculus (NC) [1, 2] is a theory of deterministic queuing systems. NC analyzes the performance characteristics of the system based on min-plus algebra and has been widely used in numerous applications to provide deterministic delay and backlog bounds.Some wireless sensor networks must meet high reliability and real-time requirements. For example, in industrial wireless sensor networks, sensor data must be transmitted to their destination before a deadline; otherwise, terrible disasters may happen. So the performance analysis of the data flow is very important at design time. NC is a powerful tool for this problem. There have been some works on using NC to analyze network performance, for example, [3–6].However, these works only focus on single-mode systems, in which the workload and resource information is fixed. In this paper, our work is based on multimode wireless sensor networks.Multimode means that the workload and resource information is allowed to be different for different modes in a network, and the mode change is determined by the system information or external operations. Multimode wireless sensor networks are commonly used in real applications. For example, Figure 1 shows the wireless sensor network of a cement manufacturer. The working process of the wireless sensor network consists of three modes. The first one is the normal mode, in which sensor nodes and all equipment normally work. Then, to improve yield, the system changes to the full-load mode, in which the high-speed wireless sensor network is used to monitor the full-load equipment. Finally, if the rotary kiln is overheated due to the full-load working, the system changes to the high-temperature mode, in which the temperature-related data (part A in Figure 1) are delivered more frequently. The system changes from the first mode to the third mode in order. When the system is in the third mode and the temperature exceeds a specified threshold, workers will handle the problem.Figure 1
The wireless sensor network in a cement manufacturer.In multimode wireless sensor networks, a variety of workload and resource information need to be considered simultaneously. But the original network calculus cannot model the multimode model due to its natural way. Some researchers combine the multimode model with the real-time calculus to analyze multimode embedded systems (e.g., [7–10]). The real-time calculus is the extended network calculus for performance analysis of real-time embedded system. But the system models of these works are not based on networks. Therefore, they cannot be used without modification. In this paper, we present a multimode wireless sensor network model and extend the network calculus to multimode networks. We propose two methods to compute the maximum delay bound of the flow of interest and discuss which one of the methods has the tighter delay bound. Experiments show that our proposed methods are effective and scalable.The rest of paper is organized as follows: Section2 introduces the related work. Section 3 reviews network calculus basics. Section 4 describes our multimode wireless sensor networks. Section 5 introduces our proposed end-to-end delay bound analysis methods and the corresponding comparative analysis. Section 6 shows evaluation results. Finally, Section 7 concludes this paper.


## 2. Related Work

The related work is classified into the following two categories: the analysis of networks and the analysis of multimode embedded systems.


### 2.1. The Analysis of Networks

Schmitt and Roedig present a series of works on the analysis of sensor networks. In [11], they extend the network calculus to sink-tree sensor networks and propose a general framework, called sensor network calculus, for analyzing the performance. The framework illustrates the various trade-offs between node power consumption, buffer requirement, and the data transfer delay bound. The main contribution of the general framework is the proposal that computes the total flow delay bound under the arbitrary multiplexing. The work in [12] focuses on the uncertain topologies. They compute the worst-case topology and then use the method of [11] to analyze sensor networks. In [13, 14], the sensor network calculus is extended to the networks with multiple sink nodes and in-network processing, respectively. The work in [15] proposes the method Pay Multiplexing Only Once (PMOO) for arbitrary multiplexing networks, and in [16, 17] the method PMOO is illustrated more clearly. The work in [18] focuses on arbitrary multiplexing networks with FIFO per microflow. The work in [5] uses the linear program to compute the end-to-end delay bound.In [6], Bouillard et al. also propose an analysis method based on the linear program, which can be used in any feed-forward network under blind multiplexing. In [19], the same authors study the exact worst-case delay for FIFO multiplexing tandem networks and propose the analysis method that only requires two linear problems to compute the upper and lower delay bounds.In [4], the authors propose the separated flow analysis (SFA) method for sensor network calculus. SFA can be adopted in general feed-forward networks. It makes use of the concatenation theorem, which provides a tighter delay bound than additive per-node bounds. In [20, 21], the same authors extend the work of [4] to allocate the implicit guaranteed time slots and balance the trade-off between energy efficiency and delay guarantees.In addition, some researchers make use of stochastic network calculus (e.g., [22–26]) to analyze the performance. But in this paper we only focus on the deterministic network calculus. Using the stochastic network calculus to analyze multimode networks will be studied in our future work.These prior works do not consider the networks with multiple modes. In [27], sensor nodes exhibit different operative modes. Each mode has the given requirement in terms of energy and bandwidth. The service and arrival curves represent the incoming bandwidth and the bandwidth requirement. Then the bandwidth allocation and the mode assignment are formulated as two nonlinear optimization problems, and the service and arrival curves are used as the constraints of optimization problems. This work focuses on multimode sensor nodes but does not consider the performance analysis.


### 2.2. The Analysis of Multimode Embedded Systems

Some researchers combine the real-time calculus (RTC) with the multimode model to analyze the performance of embedded systems. Phan et al. have done a lot of works ([7–9, 28]) about it. In [7], the real-time calculus is used to describe the workload and service models, and the event count-automata (ECA) [29] explicates the state-based models. These heterogeneous models are connected by specified interfaces. The hybrid method is more expressive and efficient comparing to the pure RTC and ECA. In [8], the authors extend RTC to the timed automata, which is introduced to model the multimode information. The method combining RTC and the timed automata is more universal for all the components in embedded systems. But it faces the problem of state space explosion, since the workload and resource information of each processing element is modeled as a automata, respectively. In [9], the authors propose the richer processing semantics to represent different scheduling policies and the dynamic characteristics of data/event streams. In [28], the authors extend the work of [9] to the system that executes multiple multimode applications concurrently.Lampka et al. propose a hybrid framework ([10, 30]), which describes the state-based component as the timed automata and the state-less component as the real-time calculus. The hybrid method can balance the expressiveness and scalability in the analysis of complex systems. And in [31], they introduce properties established to the component interface. This method can support a rigorous compositional design methodology for a complex system. Then in [32], the authors embed the methods described in [7, 10] into a framework for system-level performance analysis. However, these system models cannot be used in the analysis of wireless sensor networks.


## 2.1. The Analysis of Networks

Schmitt and Roedig present a series of works on the analysis of sensor networks. In [11], they extend the network calculus to sink-tree sensor networks and propose a general framework, called sensor network calculus, for analyzing the performance. The framework illustrates the various trade-offs between node power consumption, buffer requirement, and the data transfer delay bound. The main contribution of the general framework is the proposal that computes the total flow delay bound under the arbitrary multiplexing. The work in [12] focuses on the uncertain topologies. They compute the worst-case topology and then use the method of [11] to analyze sensor networks. In [13, 14], the sensor network calculus is extended to the networks with multiple sink nodes and in-network processing, respectively. The work in [15] proposes the method Pay Multiplexing Only Once (PMOO) for arbitrary multiplexing networks, and in [16, 17] the method PMOO is illustrated more clearly. The work in [18] focuses on arbitrary multiplexing networks with FIFO per microflow. The work in [5] uses the linear program to compute the end-to-end delay bound.In [6], Bouillard et al. also propose an analysis method based on the linear program, which can be used in any feed-forward network under blind multiplexing. In [19], the same authors study the exact worst-case delay for FIFO multiplexing tandem networks and propose the analysis method that only requires two linear problems to compute the upper and lower delay bounds.In [4], the authors propose the separated flow analysis (SFA) method for sensor network calculus. SFA can be adopted in general feed-forward networks. It makes use of the concatenation theorem, which provides a tighter delay bound than additive per-node bounds. In [20, 21], the same authors extend the work of [4] to allocate the implicit guaranteed time slots and balance the trade-off between energy efficiency and delay guarantees.In addition, some researchers make use of stochastic network calculus (e.g., [22–26]) to analyze the performance. But in this paper we only focus on the deterministic network calculus. Using the stochastic network calculus to analyze multimode networks will be studied in our future work.These prior works do not consider the networks with multiple modes. In [27], sensor nodes exhibit different operative modes. Each mode has the given requirement in terms of energy and bandwidth. The service and arrival curves represent the incoming bandwidth and the bandwidth requirement. Then the bandwidth allocation and the mode assignment are formulated as two nonlinear optimization problems, and the service and arrival curves are used as the constraints of optimization problems. This work focuses on multimode sensor nodes but does not consider the performance analysis.


## 2.2. The Analysis of Multimode Embedded Systems

Some researchers combine the real-time calculus (RTC) with the multimode model to analyze the performance of embedded systems. Phan et al. have done a lot of works ([7–9, 28]) about it. In [7], the real-time calculus is used to describe the workload and service models, and the event count-automata (ECA) [29] explicates the state-based models. These heterogeneous models are connected by specified interfaces. The hybrid method is more expressive and efficient comparing to the pure RTC and ECA. In [8], the authors extend RTC to the timed automata, which is introduced to model the multimode information. The method combining RTC and the timed automata is more universal for all the components in embedded systems. But it faces the problem of state space explosion, since the workload and resource information of each processing element is modeled as a automata, respectively. In [9], the authors propose the richer processing semantics to represent different scheduling policies and the dynamic characteristics of data/event streams. In [28], the authors extend the work of [9] to the system that executes multiple multimode applications concurrently.Lampka et al. propose a hybrid framework ([10, 30]), which describes the state-based component as the timed automata and the state-less component as the real-time calculus. The hybrid method can balance the expressiveness and scalability in the analysis of complex systems. And in [31], they introduce properties established to the component interface. This method can support a rigorous compositional design methodology for a complex system. Then in [32], the authors embed the methods described in [7, 10] into a framework for system-level performance analysis. However, these system models cannot be used in the analysis of wireless sensor networks.


## 3. Network Calculus Basics

Network calculus is a mathematical tool for analyzing the system performance. The functions involved in this paper belong to the spaceF:(1)
F
=
f
:
R
+
⟶
R
+
,
∀
t
⩾
s
:
f
t
⩾
f
s
,
f
0
=
0
.They are nonnegative and wide-sense increasing. For a given data flow, the input cumulative function R
(
t
) (R
(
t
)
∈
F) is used to denote the number of bits that arrive in the time interval [
0
,
t
]. The output cumulative function C
(
t
) (C
(
t
)
∈
F) means the number of bits which the system resource can process in the time interval [
0
,
t
]. In abacklogged period, for any t belonging to the backlogged period R
(
t
) is greater than C
(
t
). Based on the two functions R
(
t
) and C
(
t
), NC usesarrival curves andservice curves to model the system workload and resource information.Definition 1 (arrival curve).
Given a functionR
(
t
), the arrival curve α (α
∈
F) satisfies(2)
∀
s
,
0
⩽
s
⩽
t
,
R
(
t
)
-
R
(
s
)
⩽
α
(
t
-
s
)
.Definition 2 (strict service curve).
Given a functionC
(
t
), the strict service curve β (β
∈
F) satisfies(3)
for
any
backlogged
period
s
,
t
,
C
(
t
)
-
C
(
s
)
⩾
β
(
t
-
s
)
.The affine functionγ
r
,
b
(
t
)
=
b
+
r
t (t
>
0) and the rate-latency function β
R
,
T
(
t
)
=
R
[
t
-
T
]
+ are the typical arrival and service curves. The operator [
]
+ is defined as [
x
]
+
=
max
⁡
(
0
,
x
).NC makes use of the min-plus operations convolution and deconvolution to analyze the system performance.Definition 3 (min-plus convolution and deconvolution).
Letf and g be two curves. The min-plus convolution ⊗ and the min-plus deconvolution ⊘ are defined as(4)
f
⊗
g
t
=
inf
⁡
0
⩽
s
⩽
t
f
t
-
s
+
g
s
,
(
f
⊘
g
)
(
t
)
=
sup
⁡
s
⩾
0
f
t
+
s
-
g
s
.For the convolution operation, its rule ofconvex functions is represented as follows.Rule (Convex Functions) [2]. Let f
,
g
∈
F. If f and g are convex, then f
⊗
g is convex. In particular if f, g are convex and piecewise linear, f
⊗
g is obtained by putting end to end the different linear pieces of f and g, sorted by increasing slopes.Figure2 shows the relations between curves. The input data denoted by α are stored in data buffer until they are processed by β. The maximum processed data is bounded by α
′
=
α
⊘
β, and the left-over service is β
′
=
[
β
-
α
]
+. For a flow, we consider it to be served in FIFO order. So given the arrival curve α and the service curve β, the maximum delay bound D
(
α
,
β
) is expressed as follows:(5)
D
α
,
β
=
sup
⁡
s
⩾
0
inf
⁡
t
∈
0
,
s
:
α
s
-
t
⩽
β
s
=
sup
⁡
s
⩾
0
inf
⁡
t
∈
0
,
s
:
α
⊘
β
-
t
⩽
0
.Figure 3 shows an example, where the arrival curve is γ
1,10 and the service curve is β
2,10. D
(
α
,
β
) is the maximal horizontal distance between the two curves.Figure 2
Component model.Figure 3
Illustration ofD
(
α
,
β
).


## 4. System Model and Problem Statement

The key notations used in this paper are summarized in the Appendix.In our system, a sink-tree wireless sensor network is characterised by a tupleW
=
N
,
E.(i)
N
=
{
n
1
,
n
2
,
…
} is the set of sensor nodes, where n
1 is the root. A node n
i is characterised by n
i
=
α
i
,
β
i
,
n
i
p
,
N
i
c. We use the classical arrival curve γ
r
i
,
b
i and service curve β
R
i
,
T
i to describe the input data α
i and the supplied service β
i by the node n
i; that
is
,
α
i
=
γ
r
i
,
b
i and β
i
=
β
R
i
,
T
i. Each node has a parent n
i
p and several children N
i
c
=
{
n
1
c
,
n
2
c
,
…
}. Note that, for the sink node n
1
,
n
1
p
=
ϕ, and, for leaf nodes, N
i
c
=
Φ.
(ii)
MatrixE
:
N
×
N is the set of links. If n
i sends data to n
j, the element e
i
j in E is equal to 1; otherwise, e
i
j
=
0.We use the source node to tag a data flow. The input data flow of the noden
i is f
i. The flow f
i is transmitted from the node n
i to its parent n
i
p and then to the parent of the node n
i
p, until the flow arrives at the sink node. The path of the flow f
i is denoted by p
i
=
{
n
i
,
n
i
p
,
…
,
n
1
}.The wireless sensor network consists of multiple work modes. External signals or the amount of running time triggers the mode change. A mode graph can fully express this system information. The multimode wireless sensor network is modeled by the mode graphG
=
M
,
E
,
U
,
Λ.(i)
M is the set of all modes. In each mode m
i, two curve sets α
i and β
i are used to represent all sensor nodes’ workload and resource information. The curves of the node n
j in the mode m
i are represented by α
j
i and β
j
i. m
0 is the initial mode.
(ii)
E denotes the set of external signals, for example, high-temperature alarms and manual operations.
(iii)
U is the set of the upper bounds of running time. Each element U
i represents the maximum amount of time that is spent in the mode m
i. Note that U
i can be infinity.
(iv)
Λ
⊆
M
×
E
×
U
×
M is the set of mode change relations. An element λ
i
j
=
(
m
i
,
E
i
,
U
i
,
m
j
) denotes a change from the mode m
i to the mode m
j. If the amount of time spent in the mode m
i exceeds its upper bound of running time U
i, the wireless sensor network must change to the mode m
j; otherwise, only external signals E
i can trigger the mode change.Figure4 shows an example. The mode graph consists of five modes. Each mode corresponds to the given arrival and service curves. The network starts from the mode m
0 and then changes to the mode m
1 or m
2 due to external signals E or too much running time. Similarly, other mode changes can be triggered by some conditions.Figure 4
A mode graph.The problem that we address is stated as follows. Given the wireless sensor networkW and the corresponding mode graph G, our objective is to analyze the maximum delay bound of the flow of interest, such that the system performance can be tested at design time.


## 5. Analysis

In this section, we combine the network calculus and the multimode model to analyze the end-to-end delay bound of multimode wireless sensor networks. We first introduce using the network calculus to analyze one component with multiple modes and then extend it to the wireless sensor network.


### 5.1. Network Calculus for One Component with Multiple Modes

Assume that in our system model there is only one component, which works in different modes. The mode changes are described in the mode graphG.The component in each mode has the given arrival and service curves. When the component enters the modem
j from the mode m
i, the backlog and the supplied resources by the mode m
i will impact on the component execution in the mode m
j. So the original arrival and service curves cannot fully represent the component’s information. In this paper, we call the curves that describe the maximum workload and minimum service information in any time interval before the component leaves the mode m
j themultimode curves and use α
∗ and β
∗ to denote them.When the component is in the initial modem
0, its multimode arrival and service curves are the original curves; that
is
,
α
∗
0
=
α
0 and β
∗
0
=
β
0. Then we compute multimode curves of other modes based on mathematical induction. We define the path from the initial mode to the mode m
j as P
j
=
{
m
0
,
…
,
m
j
}. Assume that when the component is in the mode m
i we have obtained its multimode curves α
∗
i and β
∗
i. If there exists the mode change λ
i
j, then the multimode arrival and service curves, when the component is in the mode m
j, are denoted as follows:(6)
α
∗
j
t
=
max
⁡
0
⩽
s
⩽
U
i
,
0
⩽
t
-
s
⩽
U
j
α
∗
i
s
+
α
j
t
-
s
,
(7)
β
∗
j
t
=
min
⁡
0
⩽
s
⩽
U
i
,
0
⩽
t
-
s
⩽
U
j
β
∗
i
s
+
β
j
t
-
s
,where U
i
=
∑
∀
m
g
∈
P
i
‍
U
g represents the latest time instance when the component enters the mode m
j; that is, it is the maximum time interval before the component enters the mode m
j. The maximum amount of data that arrive in the last t time units consists of two parts. The first part is the arrival data in the last s time units before the component enters the mode m
j and can be obtained by the multimode arrival curve α
∗
i. The s time units must not be larger than the maximum time units U
i. The second part is the arrival data when the component is in the mode m
j. The (
t
-
s
) time units cannot be larger than the maximum amount of time that is spent in the mode m
j; otherwise the component will change to the next mode. The maximum sum of the two parts is the upper bound of the arrival data in any t time units before the component leaves the mode m
j; that
is
,
α
∗
j is the multimode arrival curve when the component is in the mode m
j. Similarly, the multimode service curve β
∗
j can be computed using the same way.Assume that some data arrive when the component is in the modem
i. Due to the mode change, these data may be processed in the mode m
i or its any following mode. We use D
i
g to denote the delay bound when the data are processed in the mode m
g. So(8)
D
i
g
(
α
∗
i
,
β
∗
g
)
=
sup
⁡
0
⩽
t
+
d
⩽
U
g
inf
⁡
d
:
α
∗
i
t
⩽
β
∗
g
t
+
d
,
t
∈
0
,
U
i
.We useζ
i to denote all following modes of the mode m
i. Then the end-to-end delay bound of the data flow is denoted as(9)
max
⁡
∀
m
i
∈
M
,
∀
m
g
∈
{
ς
i
+
m
i
}
D
i
g
.In the following, we analyze the end-to-end delay bound of the multimode wireless sensor networks based on the above result.


### 5.2. End-to-End Delay Bound Analysis

Theseparate flow analysis (SFA) [4] is the classical delay bound analysis method for general single-mode feed-forward networks. For the flow of interest, SFA first computes the left-over service curves for all nodes on the path of the flow and then computes the convolution of them as the service curve of the flow of interest. For example, a simple sink tree is shown in Figure 5. According to the analysis method SFA, the end-to-end delay bound of the flow of interest f
k is D
SFA
=
D
(
α
k
,
β
2
′
⊗
β
1
′
).Figure 5
A sink-tree network.Note that the left-over service curve is independent of the arrival curve of the flow of interestf
k. For brevity, in the remaining of the Section 5.2 the arrival curves of the flow α
k are not involved in the computation of left-over service curves.We extend the topology of sink-tree network to any depth. The computation of left-over service curves in the pathp
k is shown as follows:(10)
∀
n
i
∈
p
k
,
β
i
′
=
β
i
-
α
i
-
∑
∀
n
j
∈
N
i
c
‍
α
j
′
+
,where(11)
α
j
′
=
α
j
+
∑
∀
n
g
∈
N
j
c
‍
α
g
′
⊘
β
j
.Recall thatα
i
=
γ
r
i
,
b
i and β
i
=
β
R
i
,
T
i. Then we obtain(12)
∀
n
i
∈
p
k
,
β
i
′
=
R
i
′
t
-
T
i
′
+
.
α
i
′
=
b
i
′
+
r
i
′
t
,where(13)
R
i
′
=
R
i
-
r
i
-
∑
∀
n
j
∈
N
i
c
‍
r
j
′
,
(14)
r
j
′
=
r
j
+
∑
∀
n
g
∈
N
j
c
‍
r
g
′
,
(15)
T
i
′
=
R
i
T
i
+
b
i
+
∑
∀
n
j
∈
N
i
c
‍
b
j
′
R
i
′
,
(16)
b
j
′
=
b
j
+
∑
∀
n
g
∈
N
j
c
‍
b
g
′
+
r
j
′
T
j
.For example, in Figure 5,(17)
β
1
′
=
R
1
-
r
1
-
r
3
t
-
R
1
T
1
+
b
1
+
b
3
+
r
3
T
3
R
1
-
r
1
-
r
3
+
.SFA focuses on signal-mode wireless sensor networks. We combine it with the multimode model to analyze multimode wireless sensor networks.The delay bound of the flow of interestf
k is determined by its multimode arrival curve α
k
∗
i and the supplied service in each mode. The multimode arrival curve relates only to the node n
k. The node can be modeled as a multimode component. So the computation of its multimode arrival curves is the same as that of one multimode component (shown in Section 5.1); that is, we can use (6) and the mode graph G to compute multimode arrival curves α
k
∗
i
(
∀
m
i
∈
M
).The computation of the supplied service relates to all nodes in the pathp
k. We can model either each of these nodes or all of them as a multimode component. This leads to two methods N-MM and A-MM. In the following, we will introduce them and discuss which one of the methods is more effective.


#### 5.2.1. N-MM

In this method, each node in the pathp
k is modeled as a multimode component. We first compute their multimode service curves and then convolute the curves of all nodes in the same mode as the multimode service curve of the whole network in the mode. We use β
¯
i
j to denote the multimode service curve of the node n
i in the mode m
j and β
¯
j to denote the multimode service curve of the whole network in the mode m
j. We formulate the steps of the computation as follows.Step 1.
For alln
i
∈
p
k
,
m
j
∈
M,(18)
β
¯
i
j
t
=
min
⁡
0
⩽
x
⩽
U
j
-
1
,
0
⩽
t
-
x
⩽
U
j
β
¯
i
j
-
1
x
+
β
i
′
j
t
-
x
,where we assume that the mode m
j
-
1 is the parent node of the mode m
j. β
i
′
j denotes the left-over service curve of n
i in the mode m
j and is computed based on (10) and the given α
i, β
i in the network model.Step 2.
For allm
j
∈
M,(19)
β
¯
j
(
t
)
=
⨂
∀
n
i
∈
p
k
β
¯
i
j
(
t
)
.From the definition of the convolution operation, we know thatβ
¯
i
j can also be represented as β
i
′
j
⊗
β
¯
i
j
-
1, where their ranges are limited in [
0
,
U
j
] and [
0
,
U
j
-
1
], respectively. Then, we have(20)
β
¯
i
j
t
=
⨂
∀
m
g
∈
P
j
β
i
′
g
t
for
each
β
i
′
g
x
,
x
∈
0
,
U
g
,
(21)
β
¯
j
(
t
)
=
⨂
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
β
i
′
g
t
for
each
β
i
′
g
x
,
x
∈
0
,
U
g
.So, based on (8) and (9), the end-to-end delay bound of the flow f
k is(22)
max
⁡
∀
m
j
∈
M
,
∀
m
g
∈
{
ς
j
+
m
j
}
D
j
g
α
k
∗
j
,
β
¯
g
.


#### 5.2.2. A-MM

Contrary to the method N-MM, the method A-MM first convolutes all of original left-over service curves that are in the same mode; that is, it models the whole network as a multimode component. Then the computation of multimode curves is the same as that in a component. We useβ
′
j to denote the left-over service curves of the whole network in the mode m
j and β
^
j to denote the whole multimode service curve, which corresponds to β
¯
j of the method N-MM. The formulations are shown as follows.Step 1.
For allm
j
∈
M,(23)
β
′
j
(
t
)
=
⨂
∀
n
i
∈
p
k
β
i
′
j
(
t
)
.Step 2.
For allm
j
∈
M,(24)
β
^
j
t
=
min
⁡
0
⩽
x
⩽
U
j
-
1
,
0
⩽
t
-
x
⩽
U
j
β
^
j
-
1
x
+
β
i
′
j
t
-
x
,where the mode m
j
-
1 is the parent node of the mode m
j.Similarly, according to the definition of the convolution operation, we have(25)
β
^
j
(
t
)
=
⨂
∀
m
g
∈
P
j
β
′
g
(
t
)
,
for
each
β
′
g
x
,
x
∈
0
,
U
g
.Then, the delay bound of the flowf
k computed by the method A-MM is(26)
max
⁡
∀
m
j
∈
M
,
∀
m
g
∈
{
ς
j
+
m
j
}
D
j
g
α
k
∗
j
,
β
^
g
.In the following, we discuss which one of the methods is more effective. The delay bound is the maximal horizontal distance between the arrival curve and the service curve. The arrival curves used in the two methods are the same. So the service curves of the two methods determine which one of the methods is effective.Recall that our system model is based on the typical affine arrival curve and rate-latency service curve. So from (20), (21), (23), (25), and the ruleConvex functions, we know that the two methods are based on the convolution operation and all service curves are piecewise linear and convex. Then, based on the ruleConvex functions, we analyze β
¯
j and β
^
j. For the method N-MM, Figure 6 shows service curves β
i
′
g and β
¯
i
j. β
¯
i
j is the convolution of β
i
′
g that is limited in a range. So the length of the first segment is the sum of all delay T
i
′
g (∀
m
g
∈
P
j and ∀
n
i
∈
p
k). The rate of the second segment is the minimum rate among the rate set R
¯
i
j
=
R
i
′
g
∣
∀
m
g
∈
P
j, where R
i
′
g can be computed based on (13). We use σ
(
R
¯
i
j
,
x
) (δ
x for short) to denote the mode m
δ
x with the xth minimum rate in the rate set R
¯
i
j. So the rate of the xth segment in Figure 6(b) is R
i
′
δ
(
x
-
1
), and the length of the projection of the xth segment onto the horizontal axis is the difference between the range U
δ
(
x
-
1
), which is limited in (20), and the delay T
i
′
δ
(
x
-
1
). Similarly, we can obtain β
¯
j (shown in Figure 7) based on β
¯
i
j (∀
n
i
∈
p
k). The length of the first segment is also the sum of all delay T
i
′
g. For the rate set R
¯
j
=
R
¯
i
j
∣
∀
n
i
∈
p
k, σ
(
R
¯
j
,
x
) returns (
δ
x
,
h
x
), which denotes that the xth minimum rate belongs to the mode m
δ
x of the sensor node n
h
x.Figure 6
Illustration ofβ
i
′
g and β
¯
i
j.
(a)
β
i
′
g
(b)
β
¯
i
jFigure 7
Illustration ofβ
¯
j.For the method A-MM,β
′
j is not limited by any time constraint (shown in Figure 8(a)), and its rate R
′
j is the minimum rate among all rates of the mode m
j. The computation of β
^
j limits the range of β
′
j. So β
^
j also contains multiple segments as shown in Figure 8(b), where R
^
j
=
R
′
g
∣
∀
m
g
∈
P
j.Figure 8
Illustration ofβ
′
j and β
^
j.
(a)
β
′
j
(b)
β
^
jComparing with the two methods, we obtain three properties as follows.Property 1.
The two first segments ofβ
¯
j and β
^
j are the same and they are equal to ∑
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
‍
T
i
′
g.R
¯
j is the rate set for all sensor nodes before the network leaves the mode m
j, and R
^
j is a subset of R
¯
j. We can get the following properties.Property 2.
Thexth minimum rate of R
¯
j must be less than or equal to the xth minimum rate of R
^
j.Inβ
¯
j, on the horizontal axis the length of the segment with R
b
′
a is U
a
-
T
b
′
a, and in β
^
j the length of the segment is U
a
-
∑
∀
n
i
∈
p
k
‍
T
i
′
a. We know that n
b
∈
p
k. So T
b
′
a
⩽
∑
∀
n
i
∈
p
k
‍
T
i
′
a. Then we have the following.Property 3.
If a rateR
b
′
a occurs in both β
¯
j and β
^
j, the corresponding segment’s length on the horizontal axis in β
¯
j is longer than or equal to that in β
^
j.According to the three properties, we can prove the following theorem.Theorem 4.
Given a wireless sensor network and its corresponding mode graph, the maximum delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM.Proof.
According to Property1, the first segments of the two methods are the same. And the rates of their second segments are also the same. Since R
¯
j can be written as R
i
′
g
∣
∀
n
i
∈
p
k
,
∀
m
g
∈
P
j, then(27)
σ
R
¯
j
,
1
=
arg
min
⁡
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
R
i
′
g
,while(28)
σ
R
^
j
,
1
=
arg
min
⁡
∀
m
g
∈
P
j
R
′
g
=
arg
min
⁡
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
R
i
′
g
.And according to Property 3, the length of the second segment of β
¯
j is longer than or equal to that of β
^
j. So in the first and second segments of β
¯
j, β
¯
j
⩽
β
^
j.
After the second segment, we assume that there existsz such that β
¯
j
(
z
)
>
β
^
j
(
z
) (shown in Figure 9). Before z, there must exist a value y
=
sup
⁡
z
′
∣
z
′
⩽
z
,
β
¯
j
z
′
=
β
^
j
z
′, which belongs to the x
¯th segment of β
¯
j and the x
^th segment of β
^
j, and the rate of the x
¯th segment is larger than that of the x
^th segment. According to Property 2, we know x
¯
>
x
^. Then we have x
¯
-
1
⩾
x
^. Since R
^
j is the subset of R
¯
j, the rates of the second segment to x
^th segments of β
^
j must have occurred in prior x
¯
-
1 segments of β
¯
j. Then, according to Property 3, the sum of lengths of x
¯
-
1 segments of β
¯
j is longer than or equal to the sum of lengths of x
^ segments of β
^
j; that is, the x
¯th segment and the x
^th segment cannot intersect at y. Therefore, there are no y and z.
So, for eachi on the horizontal axis, β
^
j
(
i
)
⩾
β
¯
j
(
i
). The horizontal distance between the multimode arrival curve and β
^
j
(
i
) is less than or equal to the horizontal distance between the multimode arrival curve and β
¯
j
(
i
); that is, the maximum delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM.Figure 9
Comparing withβ
¯
j and β
^
j.We further illustrate the effectiveness of the method A-MM as follows. In the method N-MM, the multimode service curveβ
¯
i
j represents the minimum service of the node n
i in all modes of the path P
j. When multiple nodes are convoluted, the segments of different nodes in the same mode may be put together. It means that a flow is supplied for the minimum service of a sensor node in the mode m
j, and in other sensor nodes it also suffers from the minimum service of the same mode m
j. However, there are no constraints to limit the sum of the amount of time, in which the flow is supplied for the service of the mode m
j. This leads to the fact that the sum of the amount of time may exceed the upper bound U
j. And the cause of this case is that the service supplied by the mode m
j is minimum. But, in the method A-MM, the flow cannot suffer from the minimum service that is supplied after the time instance U
j, because of the time interval constraints of (25). So the multimode service curve of the method A-MM is larger than or equal to that of the method N-MM.For the example of Figure5, we set that R
1
′
1
=
2, R
1
′
2
=
4, R
2
′
1
=
1, R
2
′
2
=
3, U
1
=
U
2
=
10, and all T
′ are equal to 2. The computations of β
^
2 and β
¯
2 are shown in Figures 10(a) and 10(b). From these figures, we know that in the method N-MM the two segments of the mode 1 are used in β
¯
2, and the sum of the amount of time exceeds the maximum amount of time U
1. This case is impossible in the method A-MM. The method N-MM introduces more pessimism.Figure 10
Comparing with A-MM and N-MM.
(a)
The example of A-MM (β
^
2)
(b)
The example of N-MM (β
¯
2)


## 5.1. Network Calculus for One Component with Multiple Modes

Assume that in our system model there is only one component, which works in different modes. The mode changes are described in the mode graphG.The component in each mode has the given arrival and service curves. When the component enters the modem
j from the mode m
i, the backlog and the supplied resources by the mode m
i will impact on the component execution in the mode m
j. So the original arrival and service curves cannot fully represent the component’s information. In this paper, we call the curves that describe the maximum workload and minimum service information in any time interval before the component leaves the mode m
j themultimode curves and use α
∗ and β
∗ to denote them.When the component is in the initial modem
0, its multimode arrival and service curves are the original curves; that
is
,
α
∗
0
=
α
0 and β
∗
0
=
β
0. Then we compute multimode curves of other modes based on mathematical induction. We define the path from the initial mode to the mode m
j as P
j
=
{
m
0
,
…
,
m
j
}. Assume that when the component is in the mode m
i we have obtained its multimode curves α
∗
i and β
∗
i. If there exists the mode change λ
i
j, then the multimode arrival and service curves, when the component is in the mode m
j, are denoted as follows:(6)
α
∗
j
t
=
max
⁡
0
⩽
s
⩽
U
i
,
0
⩽
t
-
s
⩽
U
j
α
∗
i
s
+
α
j
t
-
s
,
(7)
β
∗
j
t
=
min
⁡
0
⩽
s
⩽
U
i
,
0
⩽
t
-
s
⩽
U
j
β
∗
i
s
+
β
j
t
-
s
,where U
i
=
∑
∀
m
g
∈
P
i
‍
U
g represents the latest time instance when the component enters the mode m
j; that is, it is the maximum time interval before the component enters the mode m
j. The maximum amount of data that arrive in the last t time units consists of two parts. The first part is the arrival data in the last s time units before the component enters the mode m
j and can be obtained by the multimode arrival curve α
∗
i. The s time units must not be larger than the maximum time units U
i. The second part is the arrival data when the component is in the mode m
j. The (
t
-
s
) time units cannot be larger than the maximum amount of time that is spent in the mode m
j; otherwise the component will change to the next mode. The maximum sum of the two parts is the upper bound of the arrival data in any t time units before the component leaves the mode m
j; that
is
,
α
∗
j is the multimode arrival curve when the component is in the mode m
j. Similarly, the multimode service curve β
∗
j can be computed using the same way.Assume that some data arrive when the component is in the modem
i. Due to the mode change, these data may be processed in the mode m
i or its any following mode. We use D
i
g to denote the delay bound when the data are processed in the mode m
g. So(8)
D
i
g
(
α
∗
i
,
β
∗
g
)
=
sup
⁡
0
⩽
t
+
d
⩽
U
g
inf
⁡
d
:
α
∗
i
t
⩽
β
∗
g
t
+
d
,
t
∈
0
,
U
i
.We useζ
i to denote all following modes of the mode m
i. Then the end-to-end delay bound of the data flow is denoted as(9)
max
⁡
∀
m
i
∈
M
,
∀
m
g
∈
{
ς
i
+
m
i
}
D
i
g
.In the following, we analyze the end-to-end delay bound of the multimode wireless sensor networks based on the above result.


## 5.2. End-to-End Delay Bound Analysis

Theseparate flow analysis (SFA) [4] is the classical delay bound analysis method for general single-mode feed-forward networks. For the flow of interest, SFA first computes the left-over service curves for all nodes on the path of the flow and then computes the convolution of them as the service curve of the flow of interest. For example, a simple sink tree is shown in Figure 5. According to the analysis method SFA, the end-to-end delay bound of the flow of interest f
k is D
SFA
=
D
(
α
k
,
β
2
′
⊗
β
1
′
).Figure 5
A sink-tree network.Note that the left-over service curve is independent of the arrival curve of the flow of interestf
k. For brevity, in the remaining of the Section 5.2 the arrival curves of the flow α
k are not involved in the computation of left-over service curves.We extend the topology of sink-tree network to any depth. The computation of left-over service curves in the pathp
k is shown as follows:(10)
∀
n
i
∈
p
k
,
β
i
′
=
β
i
-
α
i
-
∑
∀
n
j
∈
N
i
c
‍
α
j
′
+
,where(11)
α
j
′
=
α
j
+
∑
∀
n
g
∈
N
j
c
‍
α
g
′
⊘
β
j
.Recall thatα
i
=
γ
r
i
,
b
i and β
i
=
β
R
i
,
T
i. Then we obtain(12)
∀
n
i
∈
p
k
,
β
i
′
=
R
i
′
t
-
T
i
′
+
.
α
i
′
=
b
i
′
+
r
i
′
t
,where(13)
R
i
′
=
R
i
-
r
i
-
∑
∀
n
j
∈
N
i
c
‍
r
j
′
,
(14)
r
j
′
=
r
j
+
∑
∀
n
g
∈
N
j
c
‍
r
g
′
,
(15)
T
i
′
=
R
i
T
i
+
b
i
+
∑
∀
n
j
∈
N
i
c
‍
b
j
′
R
i
′
,
(16)
b
j
′
=
b
j
+
∑
∀
n
g
∈
N
j
c
‍
b
g
′
+
r
j
′
T
j
.For example, in Figure 5,(17)
β
1
′
=
R
1
-
r
1
-
r
3
t
-
R
1
T
1
+
b
1
+
b
3
+
r
3
T
3
R
1
-
r
1
-
r
3
+
.SFA focuses on signal-mode wireless sensor networks. We combine it with the multimode model to analyze multimode wireless sensor networks.The delay bound of the flow of interestf
k is determined by its multimode arrival curve α
k
∗
i and the supplied service in each mode. The multimode arrival curve relates only to the node n
k. The node can be modeled as a multimode component. So the computation of its multimode arrival curves is the same as that of one multimode component (shown in Section 5.1); that is, we can use (6) and the mode graph G to compute multimode arrival curves α
k
∗
i
(
∀
m
i
∈
M
).The computation of the supplied service relates to all nodes in the pathp
k. We can model either each of these nodes or all of them as a multimode component. This leads to two methods N-MM and A-MM. In the following, we will introduce them and discuss which one of the methods is more effective.


### 5.2.1. N-MM

In this method, each node in the pathp
k is modeled as a multimode component. We first compute their multimode service curves and then convolute the curves of all nodes in the same mode as the multimode service curve of the whole network in the mode. We use β
¯
i
j to denote the multimode service curve of the node n
i in the mode m
j and β
¯
j to denote the multimode service curve of the whole network in the mode m
j. We formulate the steps of the computation as follows.Step 1.
For alln
i
∈
p
k
,
m
j
∈
M,(18)
β
¯
i
j
t
=
min
⁡
0
⩽
x
⩽
U
j
-
1
,
0
⩽
t
-
x
⩽
U
j
β
¯
i
j
-
1
x
+
β
i
′
j
t
-
x
,where we assume that the mode m
j
-
1 is the parent node of the mode m
j. β
i
′
j denotes the left-over service curve of n
i in the mode m
j and is computed based on (10) and the given α
i, β
i in the network model.Step 2.
For allm
j
∈
M,(19)
β
¯
j
(
t
)
=
⨂
∀
n
i
∈
p
k
β
¯
i
j
(
t
)
.From the definition of the convolution operation, we know thatβ
¯
i
j can also be represented as β
i
′
j
⊗
β
¯
i
j
-
1, where their ranges are limited in [
0
,
U
j
] and [
0
,
U
j
-
1
], respectively. Then, we have(20)
β
¯
i
j
t
=
⨂
∀
m
g
∈
P
j
β
i
′
g
t
for
each
β
i
′
g
x
,
x
∈
0
,
U
g
,
(21)
β
¯
j
(
t
)
=
⨂
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
β
i
′
g
t
for
each
β
i
′
g
x
,
x
∈
0
,
U
g
.So, based on (8) and (9), the end-to-end delay bound of the flow f
k is(22)
max
⁡
∀
m
j
∈
M
,
∀
m
g
∈
{
ς
j
+
m
j
}
D
j
g
α
k
∗
j
,
β
¯
g
.


### 5.2.2. A-MM

Contrary to the method N-MM, the method A-MM first convolutes all of original left-over service curves that are in the same mode; that is, it models the whole network as a multimode component. Then the computation of multimode curves is the same as that in a component. We useβ
′
j to denote the left-over service curves of the whole network in the mode m
j and β
^
j to denote the whole multimode service curve, which corresponds to β
¯
j of the method N-MM. The formulations are shown as follows.Step 1.
For allm
j
∈
M,(23)
β
′
j
(
t
)
=
⨂
∀
n
i
∈
p
k
β
i
′
j
(
t
)
.Step 2.
For allm
j
∈
M,(24)
β
^
j
t
=
min
⁡
0
⩽
x
⩽
U
j
-
1
,
0
⩽
t
-
x
⩽
U
j
β
^
j
-
1
x
+
β
i
′
j
t
-
x
,where the mode m
j
-
1 is the parent node of the mode m
j.Similarly, according to the definition of the convolution operation, we have(25)
β
^
j
(
t
)
=
⨂
∀
m
g
∈
P
j
β
′
g
(
t
)
,
for
each
β
′
g
x
,
x
∈
0
,
U
g
.Then, the delay bound of the flowf
k computed by the method A-MM is(26)
max
⁡
∀
m
j
∈
M
,
∀
m
g
∈
{
ς
j
+
m
j
}
D
j
g
α
k
∗
j
,
β
^
g
.In the following, we discuss which one of the methods is more effective. The delay bound is the maximal horizontal distance between the arrival curve and the service curve. The arrival curves used in the two methods are the same. So the service curves of the two methods determine which one of the methods is effective.Recall that our system model is based on the typical affine arrival curve and rate-latency service curve. So from (20), (21), (23), (25), and the ruleConvex functions, we know that the two methods are based on the convolution operation and all service curves are piecewise linear and convex. Then, based on the ruleConvex functions, we analyze β
¯
j and β
^
j. For the method N-MM, Figure 6 shows service curves β
i
′
g and β
¯
i
j. β
¯
i
j is the convolution of β
i
′
g that is limited in a range. So the length of the first segment is the sum of all delay T
i
′
g (∀
m
g
∈
P
j and ∀
n
i
∈
p
k). The rate of the second segment is the minimum rate among the rate set R
¯
i
j
=
R
i
′
g
∣
∀
m
g
∈
P
j, where R
i
′
g can be computed based on (13). We use σ
(
R
¯
i
j
,
x
) (δ
x for short) to denote the mode m
δ
x with the xth minimum rate in the rate set R
¯
i
j. So the rate of the xth segment in Figure 6(b) is R
i
′
δ
(
x
-
1
), and the length of the projection of the xth segment onto the horizontal axis is the difference between the range U
δ
(
x
-
1
), which is limited in (20), and the delay T
i
′
δ
(
x
-
1
). Similarly, we can obtain β
¯
j (shown in Figure 7) based on β
¯
i
j (∀
n
i
∈
p
k). The length of the first segment is also the sum of all delay T
i
′
g. For the rate set R
¯
j
=
R
¯
i
j
∣
∀
n
i
∈
p
k, σ
(
R
¯
j
,
x
) returns (
δ
x
,
h
x
), which denotes that the xth minimum rate belongs to the mode m
δ
x of the sensor node n
h
x.Figure 6
Illustration ofβ
i
′
g and β
¯
i
j.
(a)
β
i
′
g
(b)
β
¯
i
jFigure 7
Illustration ofβ
¯
j.For the method A-MM,β
′
j is not limited by any time constraint (shown in Figure 8(a)), and its rate R
′
j is the minimum rate among all rates of the mode m
j. The computation of β
^
j limits the range of β
′
j. So β
^
j also contains multiple segments as shown in Figure 8(b), where R
^
j
=
R
′
g
∣
∀
m
g
∈
P
j.Figure 8
Illustration ofβ
′
j and β
^
j.
(a)
β
′
j
(b)
β
^
jComparing with the two methods, we obtain three properties as follows.Property 1.
The two first segments ofβ
¯
j and β
^
j are the same and they are equal to ∑
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
‍
T
i
′
g.R
¯
j is the rate set for all sensor nodes before the network leaves the mode m
j, and R
^
j is a subset of R
¯
j. We can get the following properties.Property 2.
Thexth minimum rate of R
¯
j must be less than or equal to the xth minimum rate of R
^
j.Inβ
¯
j, on the horizontal axis the length of the segment with R
b
′
a is U
a
-
T
b
′
a, and in β
^
j the length of the segment is U
a
-
∑
∀
n
i
∈
p
k
‍
T
i
′
a. We know that n
b
∈
p
k. So T
b
′
a
⩽
∑
∀
n
i
∈
p
k
‍
T
i
′
a. Then we have the following.Property 3.
If a rateR
b
′
a occurs in both β
¯
j and β
^
j, the corresponding segment’s length on the horizontal axis in β
¯
j is longer than or equal to that in β
^
j.According to the three properties, we can prove the following theorem.Theorem 4.
Given a wireless sensor network and its corresponding mode graph, the maximum delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM.Proof.
According to Property1, the first segments of the two methods are the same. And the rates of their second segments are also the same. Since R
¯
j can be written as R
i
′
g
∣
∀
n
i
∈
p
k
,
∀
m
g
∈
P
j, then(27)
σ
R
¯
j
,
1
=
arg
min
⁡
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
R
i
′
g
,while(28)
σ
R
^
j
,
1
=
arg
min
⁡
∀
m
g
∈
P
j
R
′
g
=
arg
min
⁡
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
R
i
′
g
.And according to Property 3, the length of the second segment of β
¯
j is longer than or equal to that of β
^
j. So in the first and second segments of β
¯
j, β
¯
j
⩽
β
^
j.
After the second segment, we assume that there existsz such that β
¯
j
(
z
)
>
β
^
j
(
z
) (shown in Figure 9). Before z, there must exist a value y
=
sup
⁡
z
′
∣
z
′
⩽
z
,
β
¯
j
z
′
=
β
^
j
z
′, which belongs to the x
¯th segment of β
¯
j and the x
^th segment of β
^
j, and the rate of the x
¯th segment is larger than that of the x
^th segment. According to Property 2, we know x
¯
>
x
^. Then we have x
¯
-
1
⩾
x
^. Since R
^
j is the subset of R
¯
j, the rates of the second segment to x
^th segments of β
^
j must have occurred in prior x
¯
-
1 segments of β
¯
j. Then, according to Property 3, the sum of lengths of x
¯
-
1 segments of β
¯
j is longer than or equal to the sum of lengths of x
^ segments of β
^
j; that is, the x
¯th segment and the x
^th segment cannot intersect at y. Therefore, there are no y and z.
So, for eachi on the horizontal axis, β
^
j
(
i
)
⩾
β
¯
j
(
i
). The horizontal distance between the multimode arrival curve and β
^
j
(
i
) is less than or equal to the horizontal distance between the multimode arrival curve and β
¯
j
(
i
); that is, the maximum delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM.Figure 9
Comparing withβ
¯
j and β
^
j.We further illustrate the effectiveness of the method A-MM as follows. In the method N-MM, the multimode service curveβ
¯
i
j represents the minimum service of the node n
i in all modes of the path P
j. When multiple nodes are convoluted, the segments of different nodes in the same mode may be put together. It means that a flow is supplied for the minimum service of a sensor node in the mode m
j, and in other sensor nodes it also suffers from the minimum service of the same mode m
j. However, there are no constraints to limit the sum of the amount of time, in which the flow is supplied for the service of the mode m
j. This leads to the fact that the sum of the amount of time may exceed the upper bound U
j. And the cause of this case is that the service supplied by the mode m
j is minimum. But, in the method A-MM, the flow cannot suffer from the minimum service that is supplied after the time instance U
j, because of the time interval constraints of (25). So the multimode service curve of the method A-MM is larger than or equal to that of the method N-MM.For the example of Figure5, we set that R
1
′
1
=
2, R
1
′
2
=
4, R
2
′
1
=
1, R
2
′
2
=
3, U
1
=
U
2
=
10, and all T
′ are equal to 2. The computations of β
^
2 and β
¯
2 are shown in Figures 10(a) and 10(b). From these figures, we know that in the method N-MM the two segments of the mode 1 are used in β
¯
2, and the sum of the amount of time exceeds the maximum amount of time U
1. This case is impossible in the method A-MM. The method N-MM introduces more pessimism.Figure 10
Comparing with A-MM and N-MM.
(a)
The example of A-MM (β
^
2)
(b)
The example of N-MM (β
¯
2)


## 5.2.1. N-MM

In this method, each node in the pathp
k is modeled as a multimode component. We first compute their multimode service curves and then convolute the curves of all nodes in the same mode as the multimode service curve of the whole network in the mode. We use β
¯
i
j to denote the multimode service curve of the node n
i in the mode m
j and β
¯
j to denote the multimode service curve of the whole network in the mode m
j. We formulate the steps of the computation as follows.Step 1.
For alln
i
∈
p
k
,
m
j
∈
M,(18)
β
¯
i
j
t
=
min
⁡
0
⩽
x
⩽
U
j
-
1
,
0
⩽
t
-
x
⩽
U
j
β
¯
i
j
-
1
x
+
β
i
′
j
t
-
x
,where we assume that the mode m
j
-
1 is the parent node of the mode m
j. β
i
′
j denotes the left-over service curve of n
i in the mode m
j and is computed based on (10) and the given α
i, β
i in the network model.Step 2.
For allm
j
∈
M,(19)
β
¯
j
(
t
)
=
⨂
∀
n
i
∈
p
k
β
¯
i
j
(
t
)
.From the definition of the convolution operation, we know thatβ
¯
i
j can also be represented as β
i
′
j
⊗
β
¯
i
j
-
1, where their ranges are limited in [
0
,
U
j
] and [
0
,
U
j
-
1
], respectively. Then, we have(20)
β
¯
i
j
t
=
⨂
∀
m
g
∈
P
j
β
i
′
g
t
for
each
β
i
′
g
x
,
x
∈
0
,
U
g
,
(21)
β
¯
j
(
t
)
=
⨂
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
β
i
′
g
t
for
each
β
i
′
g
x
,
x
∈
0
,
U
g
.So, based on (8) and (9), the end-to-end delay bound of the flow f
k is(22)
max
⁡
∀
m
j
∈
M
,
∀
m
g
∈
{
ς
j
+
m
j
}
D
j
g
α
k
∗
j
,
β
¯
g
.


## 5.2.2. A-MM

Contrary to the method N-MM, the method A-MM first convolutes all of original left-over service curves that are in the same mode; that is, it models the whole network as a multimode component. Then the computation of multimode curves is the same as that in a component. We useβ
′
j to denote the left-over service curves of the whole network in the mode m
j and β
^
j to denote the whole multimode service curve, which corresponds to β
¯
j of the method N-MM. The formulations are shown as follows.Step 1.
For allm
j
∈
M,(23)
β
′
j
(
t
)
=
⨂
∀
n
i
∈
p
k
β
i
′
j
(
t
)
.Step 2.
For allm
j
∈
M,(24)
β
^
j
t
=
min
⁡
0
⩽
x
⩽
U
j
-
1
,
0
⩽
t
-
x
⩽
U
j
β
^
j
-
1
x
+
β
i
′
j
t
-
x
,where the mode m
j
-
1 is the parent node of the mode m
j.Similarly, according to the definition of the convolution operation, we have(25)
β
^
j
(
t
)
=
⨂
∀
m
g
∈
P
j
β
′
g
(
t
)
,
for
each
β
′
g
x
,
x
∈
0
,
U
g
.Then, the delay bound of the flowf
k computed by the method A-MM is(26)
max
⁡
∀
m
j
∈
M
,
∀
m
g
∈
{
ς
j
+
m
j
}
D
j
g
α
k
∗
j
,
β
^
g
.In the following, we discuss which one of the methods is more effective. The delay bound is the maximal horizontal distance between the arrival curve and the service curve. The arrival curves used in the two methods are the same. So the service curves of the two methods determine which one of the methods is effective.Recall that our system model is based on the typical affine arrival curve and rate-latency service curve. So from (20), (21), (23), (25), and the ruleConvex functions, we know that the two methods are based on the convolution operation and all service curves are piecewise linear and convex. Then, based on the ruleConvex functions, we analyze β
¯
j and β
^
j. For the method N-MM, Figure 6 shows service curves β
i
′
g and β
¯
i
j. β
¯
i
j is the convolution of β
i
′
g that is limited in a range. So the length of the first segment is the sum of all delay T
i
′
g (∀
m
g
∈
P
j and ∀
n
i
∈
p
k). The rate of the second segment is the minimum rate among the rate set R
¯
i
j
=
R
i
′
g
∣
∀
m
g
∈
P
j, where R
i
′
g can be computed based on (13). We use σ
(
R
¯
i
j
,
x
) (δ
x for short) to denote the mode m
δ
x with the xth minimum rate in the rate set R
¯
i
j. So the rate of the xth segment in Figure 6(b) is R
i
′
δ
(
x
-
1
), and the length of the projection of the xth segment onto the horizontal axis is the difference between the range U
δ
(
x
-
1
), which is limited in (20), and the delay T
i
′
δ
(
x
-
1
). Similarly, we can obtain β
¯
j (shown in Figure 7) based on β
¯
i
j (∀
n
i
∈
p
k). The length of the first segment is also the sum of all delay T
i
′
g. For the rate set R
¯
j
=
R
¯
i
j
∣
∀
n
i
∈
p
k, σ
(
R
¯
j
,
x
) returns (
δ
x
,
h
x
), which denotes that the xth minimum rate belongs to the mode m
δ
x of the sensor node n
h
x.Figure 6
Illustration ofβ
i
′
g and β
¯
i
j.
(a)
β
i
′
g
(b)
β
¯
i
jFigure 7
Illustration ofβ
¯
j.For the method A-MM,β
′
j is not limited by any time constraint (shown in Figure 8(a)), and its rate R
′
j is the minimum rate among all rates of the mode m
j. The computation of β
^
j limits the range of β
′
j. So β
^
j also contains multiple segments as shown in Figure 8(b), where R
^
j
=
R
′
g
∣
∀
m
g
∈
P
j.Figure 8
Illustration ofβ
′
j and β
^
j.
(a)
β
′
j
(b)
β
^
jComparing with the two methods, we obtain three properties as follows.Property 1.
The two first segments ofβ
¯
j and β
^
j are the same and they are equal to ∑
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
‍
T
i
′
g.R
¯
j is the rate set for all sensor nodes before the network leaves the mode m
j, and R
^
j is a subset of R
¯
j. We can get the following properties.Property 2.
Thexth minimum rate of R
¯
j must be less than or equal to the xth minimum rate of R
^
j.Inβ
¯
j, on the horizontal axis the length of the segment with R
b
′
a is U
a
-
T
b
′
a, and in β
^
j the length of the segment is U
a
-
∑
∀
n
i
∈
p
k
‍
T
i
′
a. We know that n
b
∈
p
k. So T
b
′
a
⩽
∑
∀
n
i
∈
p
k
‍
T
i
′
a. Then we have the following.Property 3.
If a rateR
b
′
a occurs in both β
¯
j and β
^
j, the corresponding segment’s length on the horizontal axis in β
¯
j is longer than or equal to that in β
^
j.According to the three properties, we can prove the following theorem.Theorem 4.
Given a wireless sensor network and its corresponding mode graph, the maximum delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM.Proof.
According to Property1, the first segments of the two methods are the same. And the rates of their second segments are also the same. Since R
¯
j can be written as R
i
′
g
∣
∀
n
i
∈
p
k
,
∀
m
g
∈
P
j, then(27)
σ
R
¯
j
,
1
=
arg
min
⁡
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
R
i
′
g
,while(28)
σ
R
^
j
,
1
=
arg
min
⁡
∀
m
g
∈
P
j
R
′
g
=
arg
min
⁡
∀
m
g
∈
P
j
,
∀
n
i
∈
p
k
R
i
′
g
.And according to Property 3, the length of the second segment of β
¯
j is longer than or equal to that of β
^
j. So in the first and second segments of β
¯
j, β
¯
j
⩽
β
^
j.
After the second segment, we assume that there existsz such that β
¯
j
(
z
)
>
β
^
j
(
z
) (shown in Figure 9). Before z, there must exist a value y
=
sup
⁡
z
′
∣
z
′
⩽
z
,
β
¯
j
z
′
=
β
^
j
z
′, which belongs to the x
¯th segment of β
¯
j and the x
^th segment of β
^
j, and the rate of the x
¯th segment is larger than that of the x
^th segment. According to Property 2, we know x
¯
>
x
^. Then we have x
¯
-
1
⩾
x
^. Since R
^
j is the subset of R
¯
j, the rates of the second segment to x
^th segments of β
^
j must have occurred in prior x
¯
-
1 segments of β
¯
j. Then, according to Property 3, the sum of lengths of x
¯
-
1 segments of β
¯
j is longer than or equal to the sum of lengths of x
^ segments of β
^
j; that is, the x
¯th segment and the x
^th segment cannot intersect at y. Therefore, there are no y and z.
So, for eachi on the horizontal axis, β
^
j
(
i
)
⩾
β
¯
j
(
i
). The horizontal distance between the multimode arrival curve and β
^
j
(
i
) is less than or equal to the horizontal distance between the multimode arrival curve and β
¯
j
(
i
); that is, the maximum delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM.Figure 9
Comparing withβ
¯
j and β
^
j.We further illustrate the effectiveness of the method A-MM as follows. In the method N-MM, the multimode service curveβ
¯
i
j represents the minimum service of the node n
i in all modes of the path P
j. When multiple nodes are convoluted, the segments of different nodes in the same mode may be put together. It means that a flow is supplied for the minimum service of a sensor node in the mode m
j, and in other sensor nodes it also suffers from the minimum service of the same mode m
j. However, there are no constraints to limit the sum of the amount of time, in which the flow is supplied for the service of the mode m
j. This leads to the fact that the sum of the amount of time may exceed the upper bound U
j. And the cause of this case is that the service supplied by the mode m
j is minimum. But, in the method A-MM, the flow cannot suffer from the minimum service that is supplied after the time instance U
j, because of the time interval constraints of (25). So the multimode service curve of the method A-MM is larger than or equal to that of the method N-MM.For the example of Figure5, we set that R
1
′
1
=
2, R
1
′
2
=
4, R
2
′
1
=
1, R
2
′
2
=
3, U
1
=
U
2
=
10, and all T
′ are equal to 2. The computations of β
^
2 and β
¯
2 are shown in Figures 10(a) and 10(b). From these figures, we know that in the method N-MM the two segments of the mode 1 are used in β
¯
2, and the sum of the amount of time exceeds the maximum amount of time U
1. This case is impossible in the method A-MM. The method N-MM introduces more pessimism.Figure 10
Comparing with A-MM and N-MM.
(a)
The example of A-MM (β
^
2)
(b)
The example of N-MM (β
¯
2)


## 6. Evaluation

There are no previous works on multimode networks. Therefore, we compare our proposed analysis methods with the original single-mode analysis method SFA [4]. These methods are implemented in RTC Toolbox [33]. RTC Toolbox is a set of MATLAB libraries and provides basic min-plus and max-plus operations. All experiments run on a desktop computer with 3.4 GHz Intel Core i7 processor and 4 GB memory.We adopt the fully occupied binary tree, where in different modes all nodes have the same latencyT and the same burst b. The arrival rate r
=
ω
×
i, where i denotes the ith mode and ω is a coefficient. We use the service rate R to limit the node’s utilization. For each node, its service rate R is equal to the quotient of its arrival rate (14) and the utilization. The mode graph consists of three successive modes, and all modes have the same U
i. The method SFA cannot analyze multimode networks. In order to use it in the evaluation, the multimode model must be changed to the single-mode model, in which each node consists of one service curve and one arrival curve. So the arrival curve of the single-mode network is the maximum arrival curve between the three modes and the service curve is the minimum service curve. Then the method SFA can analyze the delay bound of the flow of interest based on the single-mode model. Only in this way the delay analyzed by the method SFA is the reliable delay bound.Figure11 shows the delay bound comparison between the different configurations when the tree depth varies. In the single-mode binary tree network, the arrival rate r is 3
×
ω and the service rate R is the quotient of ω and the utilization. In order to make the network analyzable by the method SFA, the service rate R must be greater than the arrival rate r. So the utilization is set as 0.3. Under this utilization configuration, the results of A-MM and N-MM are the same. So we use MM to tag them in Figure 11. U
i varies as the depth increases, and it is set as just enough for which any flow can be delivered to the destination in any two successive modes. From the figure, we have the following.(i)
The delay bound of MM is tighter than that of SFA, since MM supplies the fine-grained model for analysis.
(ii)
The more the tree depth, the longer the end-to-end delay bound. It is because that the increase of nodes leads to the long latencyT
′ (15) and burst b
′ (16). From Figure 3, we know that these parameters relate closely to the delay bound.
(iii)
The parameterT has more impact on the delay bound. It is because that in (15) and (16) its coefficient is r
j
′
/
R
′
(
r
j
′
⩾
1
), while the coefficients of other parameters are 1
/
R
′ and T
j
/
R
′ (when r becomes T
j
=
1).
(iv)
Only the increase ofω leads to the shorter delay bound. In this case, b
′ increases, but R
′ expands ten times and T
′ decreases. So the delay bound decreases slightly when ω changes from 1 to 10.Figure 11
The end-to-end delay bound comparison with different depths.Figure12 shows the ratio of MM to SFA. SFA introduces more pessimism to the complex system. So the ratio decreases as the depth increases. The delay bound of MM is about 30
% of the delay bound of SFA when the large-scale network contains 32 thousands of sensor nodes. The execution time of all programs is less than 1 minute. Therefore, our proposed analysis methods are thigh and scalable.Figure 12
The ratio of MM to SFA with different depths.In the following, we compare our proposed methods A-MM and N-MM. There is no SFA, since SFA cannot analyze the system with high utilization. Figure13 shows the delay bound comparison with different utilizations when the tree depth is 8. And Figure 14 shows the delay bound comparison with different numbers of modes. The utilization is short for u. As our analyzed results, the delay bound of A-MM is tighter than that of N-MM, and N-MM is more pessimistic in the complex system.Figure 13
The end-to-end delay bound comparison and the ratio of A-MM to N-MM with different utilizations.Figure 14
The comparison with different numbers of modes.


## 7. Conclusion

Multimode wireless sensor networks are commonly used in real applications. In this paper, we combine the separate flow analysis, which is the classical delay bound analysis method based on the original network calculus for general single-mode feed-forward networks, and the multimode model to analyze the end-to-end delay bound of multimode wireless sensor networks. We propose two combined methods: the first method N-MM models each sensor node in the path of the flow of interest as a multimode component; the second method A-MM models the whole network as a multimode component. Comparing with the two methods, we obtain three properties. According to these properties and the rule of convolution operation, we prove that the delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM. Experiments show that, comparing with the analysis method SFA, our proposed methods can be used in high utilization and large-scale wireless sensor networks and can significantly decrease the analytical delay bound of the flow of interest (about70
% for the network with 32 thousands of sensor nodes). And in the future work we will extend the stochastic network calculus to multimode wireless sensor networks.



---

*Source: 851608-2015-03-31.xml*