Deterministic Worst-case Performance Analysis

for Wireless Sensor Networks

Huimin She1,2, Zhonghai Lu, Axel Jantsch, Li-Rong Zheng Dian Zhou
1 2
Dept. of Electronic, Computer and Software Systems ASIC & System State Key Lab.,
Royal Institute of Technology (KTH), Sweden Dept. of Microelectronics, Fudan University, China
{huimin, zhonghai, axel, lirong}@[Link] zhoud@[Link]

Abstract—Dimensioning wireless sensor networks requires demonstrated that both energy saving and high performance
formal methods to guarantee network performance and cost in can be achieved by conducting variable duty-cycle operations
any conditions. Based on network calculus, this paper presents a in media access control protocols. Secondly, we applied the
deterministic analysis method for evaluating the worst-case
performance and buffer cost of sensor networks. To this end, we network calculus theory to analyze three general traffic flow
introduce three general traffic flow operators and derive their operators, which can be used to characterize any complex
delay and buffer bounds. These operators are general because traffic flowing scenarios. The method can be applied to
they can be used in combination to model any complex traffic networks with any topologies as long as there is no loop.
flowing scenarios in sensor networks. Furthermore, our method Thirdly, traffic splitting routing can be applied in this method.
integrates variable duty cycle to allow the sensor nodes to operate With traffic splitting mechanisms, a traffic flow is split into
at lower rates thus saving power. Moreover, it incorporates
traffic splitting mechanisms in order to balance network several sub-flows and each one is sent to the destination across
workload and nodes’ buffers. To show how our method applies to different paths. Traffic splitting can be useful in improving the
real applications, we conduct a case study on a fresh food bandwidth efficiency, mitigating congestion, and increasing
tracking application, which monitors the food freshness in real- delivery reliability [8]. In addition, in [3] [4] [5], their works
time. The experimental results demonstrate that our method can are based on a common assumption that the service rate is
be either used to perform network planning before deployment, constantly bigger than the input data rate. The assumption may
or to conduct network reconfiguration after deployment.
not always be reasonable in sensor networks since nodes
should allow different operation rates for the best of power
I. INTRODUCTION saving without compromising performance. Our method can
As advances in wireless communications and electronics, incorporate the rate adjustment in nodes.
wireless sensor network (WSN) has become a promising We have described the traffic splitting mechanisms in our
technology with a wide range of applications, such as health previous work [6], from which we borrow many notations
care, supply chain management, structural monitoring, and used in this paper. However, this paper differs from [6] on the
military support [1]. In most of the applications, it is essential following aspects. In [6], the work mainly focused on
to ensure that the performance of sensor networks is analyzing traffic splitting mechanisms; in this paper our main
predictable even in the worst case. contribution is proposing a deterministic analysis method
Recently, network calculus has been developed for worst- integrating variable duty cycle and three general traffic flow
case performance analysis in packet switching networks [2]. operators. Moreover, the topology of sensor network
With network calculus, some fundamental properties of examined in [6] is a regular 2D mesh. In this paper, this
packet-switched networks, such as delay bound and backlog limitation is lifted.
bound, can be studied. Jens et al. [3] [4] extended this theory In this paper, we apply and extend the network calculus
to sensor network calculus, which can be used as a tool for theory to the worst-case performance analysis of sensor
worst case traffic analysis in sensor networks. In [5], Anis et networks. We introduce three general traffic flow operators
al. proposed a methodology for the modeling and worst-case and derive their characteristics using network calculus theory.
dimensioning of cluster-tree sensor networks. In this paper, we Based on the traffic flow operators, we present a deterministic
also apply network calculus to examine the worst-case performance analysis method which integrates variable duty
performance of sensor networks. However, our work differs cycle operations and traffic splitting mechanisms. In order to
from the previous work and makes significant improvement in show how the analysis method works, a case study of
the following aspects. Firstly, variable duty cycle (see section designing a sensor network for monitoring food freshness in
2-C) is considered in our approach, thus providing a facility to real-time (see details in section 4-A) is conducted. The
make compromises between latency and power consumption numerical results indicate that variable duty cycle operations
according to application requirements. In [7], Sang et al. and traffic splitting mechanisms have significant effects on
improving the performance of sensor networks. Thus, burst tolerance (in units of data) and the rate (in units of data
requirements of different applications can be satisfied by per unit time), respectively. Having α(t) as an arrival curve
selecting appropriate network parameters such as duty cycle, allows a source to send σ bits at once, but not more than ρ bits/s
work period and splitting coefficient. Therefore, the analysis over the long run. Similarly, the output flow from a node could
method provides a way for a sensor network designer to also be modeled by a cumulative function denoted by R*(t),
which is defined as the traffic departing from the node in time
perform network planning prior to deployment, as well as to interval [0, t]. The relation between the input flow R(t) and
reconfigure network after design. output flow R*(t) is expressed as (Fig. 2),
The rest of this paper is organized as follows: section 2
introduces the system model of sensor networks and basic R * ( t ) ≥ inf ( R ( s ) + β ( t − s )); ∀ t ≥ 0 (2)
s≤t
knowledge of network calculus theory. In section 3, three
general traffic flow operators and the deterministic analysis where β(t) is defined as the service curve [2] provided by the
method are presented. We present the wireless sensor network sensor node, which is a wide sense increasing function with β(0)
for fresh food tracking and give numerical results in section 4. = 0.
Finally, conclusions are drawn in section 5. Assume an arrival flow R(t), constrained by arrival curve
α(t), traverses a sensor node that offers a service curve β(t).
II. MODELS Then, the delay bound D(t), buffer bound B(t), and output flow
R*(t) can be derived according to the following lemmas. The
A. Sensor Netowrk System Model proofs of these lemmas can be found in [2].
Lemma 1. Delay bound
We consider a static wireless sensor network consisting of
multiple sensor nodes and one sink node. These sensors are D(t ) ≤ inf{τ ≥ 0 : α (t ) ≤ β (t + τ )} (3)
randomly scattered in a field that needs to be sensed (Fig. 1).
Sensor nodes periodically send their acquired data to the sink Lemma 2. Backlog bound
through multi-hop routing. A sensor node has the ability to B(t ) ≤ sup{α ( s ) − β ( s )}
sensing the environment and generating messages, as well as s ≥0
(4)
relaying messages for other nodes.
Lemma 3. Output flow: The output flow R*(t) is constrained by
the arrival curve,
α * (t ) = sup{α (t + s) − β (s)} (5)
s≥0

α (t )

β (t )

Fig. 1 A typical sensor network

In sensor networks, there are typically two kinds of traffic

flows, which are upstream traffic flows (from sensor nodes to Fig. 2 Traffic Model: 1) The relationship between input traffic flow R(t), outp
ut traffic flow R*(t), arrive curve α(t) and service curve β(t); 2) Delay bound
the sink) and downstream traffic flows (from the sink to a and backlog bound.
sensor node). Typically, critical messages are sent from
sensors to the sink, i.e. upstream. The methods used to analyze The backlog is the amount of bits that are held inside the
upstream traffic flows and downstream traffic flows are sensor node. The required buffer size of a sensor node is
similar. Therefore, our efforts concentrate on analyzing determined by the maximum backlog. The delay at time t is the
upstream traffic flows. time that would be experienced by a bit arriving at time t if all
bits received before it are served before it. Graphically, the
delay bound and backlog bound are the maximum horizontal
B. Traffic Model and deviation distance between arrival curve α(t) and service
To characterize the traffic generated by the sensor nodes, curve β(t), respectively (Fig. 2).
we model the arrival flow at a node using its cumulative traffic
R(t), defined as the number of bits coming from the flow in C. Variable Duty Cycle
time interval [0, t] (R(0)=0). We assume that the cumulative
traffic flow R(t) is constrained by a wide-sense increasing Waking up the nodes all the time is impossible in wireless
function α(t) , that is, sensor network since merely turning on the radio will soon
deplete the node energy. To save energy, all the existing
R (t ) − R ( s ) ≤ α (t − s ); ∀t ≥ 0, t ≥ s (1) sensor networks employ a low duty-cycle operation with a
periodic sleep and wakeup. In this paper, we also assume
α(t) is called the arrival curve of R(t) [2] (Fig. 2). In this paper,
sensor nodes have two work modes which are active mode and
we assume an affine arrival curve for all the sensor nodes,
which is defined as α(t) = ρּt + σ, where σ and ρ represent the sleep mode. Let the work period of all the sensor nodes be T,
and duty cycle of sensor node i be λ. Duty cycle is defined as this, measures should be taken either to increase the service
the percentage of time that the sensor node is active in a period. rate or constrain the input data rate. Otherwise, packets will be
It can be expressed as a ratio or a percentage. For example, a dropped when the buffer is full. From the expression of the
sensor node with a 1 second work period, which consists of service curve, we can see that the service rate can be increased
0.1s active time and 0.9s sleep time, is said to have a duty by increasing the duty cycle.
cycle of 0.1 or 10%. Assume the time for node i to process the
packets is τ. Further, let C denote the achievable link capacity. 2). Traffic merging
Therefore, sensor node i provides a rate-latency service curve For the traffic merging operator, multiple traffic flows
β(t), which is defined as, merge into one traffic flow at the sensor node (Fig. 3-b). In
β ( t ) = λ C [ t − ((1 − λ )T + τ )] + , (6) this case, it is important that a service discipline should be
applied to allocate the bandwidth. The service disciplines are
where λC and (1-λ)T + τ denote the service rate and delay, used to control the order in which packets are served, and
respectively. The expression [x]+ is equal to x when x>0, and 0 determine how packets from different connections interact
otherwise. with each other. In [10], Zhang described several service
disciplines for packet-switching networks, for example, Delay
III. A DETERMINISTIC ANALYSIS METHOD Earliest-Due-Date, Virtual Clock, Fair Queuing. However,
In this section, we present a deterministic method for worst- different service disciplines fit for different applications. The
case performance analysis of sensor networks. The method is service discipline for sensor networks should be as simple as
designed to analyze the delay bound, backlog bound, and possible since the hardware resource in a sensor node is very
delivery capability which is measured by data delivery ratio limited. Therefore, we take the following two disciplines for
(see examples in section 4-B). bandwidth allocation in sensor networks. The first one is
called rate-proportional allocation strategy, and the other one
A. Analysis of Traffic Flow Operators is called weight-proportional allocation strategy. In rate-
We defined three kinds of traffic flow operators: traffic proportional allocation, the bandwidth is allocated
passing operator, traffic merging operator, and traffic splitting proportional to the data rate of each flow; while in weight-
operator (Fig. 3). These operators are general and can be used proportional allocation, each flow is assigned a weight value
to describe any combined traffic flowing scenarios. wi, and the bandwidth is allocated according to the weight
F1 * values. In fact, the previous allocation strategy can be
F F* F regarded as a special case of the latter when all the wi equals 1.
S F* S
FM *
As shown in Fig. 3-b, we assume there are N input traffic
flows, each of which is denoted as Fi. The output is an
a) b) c) ensemble of traffic flows. Let Fi* denote the output flow
Fig. 3 Traffic flow operators. F, F*, and S denote the input flow, output flow, corresponding to Fi, and Ci denote the bandwidth allocated to
sensor node, respectively. a) Traffic passing: one input flow and one output the traffic flow Fi. Assume the arrival curve and service curve
flow; b) Traffic merging: multiple input flows and one output flow; c) Traffic
splitting: one input flow and multiple output flows. are the same as those in section 3.1-A. Then, Ci in the two
allocation strategies is calculated as expression (10). Based on
1). Traffic passing Lemma 1, 2, 3, the delay bound, backlog bound, and output
flow are derived as expression (11), (12), (13), respectively [2].
For the traffic passing operator, the sensor node has one
input link and one output link (Fig. 3-a). As we mentioned wi ρ i
above, the input traffic flow is constrained by arrival curve α(t) Ci = N
λC
(10)
= ρּt + σ, and service curve is defined as equation (6). Based ∑ wjρ j
j =1
on Lemma 1, 2, 3, we derived the delay bound, backlog bound,
and output flow, respectively [2]. The delay bound of flow i is,
The delay bound is expressed as,
σi
σ Di = + (1 − λ )T + τ (11)
D= + (1 − λ )T + τ (7) Ci
λC
And the backlog bound is expressed by,
And the backlog bound is,
N N
B = σ + ρ (1 − λ )T + ρτ (8) B = ∑ σ i + ((1 − λ )T + τ )∑ ρ i (12)
i =1 i =1
The output flow is constrained by,
The output flow Fi* is constrained by,
θ (t ) = ρ ' t + (σ + ρ (1 − λ )T + ρτ ) , (9)
θ i (t ) = Ci t + σ i + ρ i (1 − λ )T + ρ iτ (13)
where ρ ' = min( ρ , λ C ) .
In the case that λC <ρ, the backlog will increase endlessly
if the input traffic flows into the node continuously. To avoid
3). Traffic splitting of node i (i=a…g) be λi and T, respectively. Let the link
capacity be C.
In order to balance network workload, a traffic flow may
be split into multiple flows as shown in Fig. 3-c. Let the
splitting factor be γ j ( j = 1 ... M ) and ∑γ j = 1 , where M
denotes the number of output paths. We assume the node has
infinite input and output capacity. The arrival curve and
service curve are the same as those in section 2.2-B. Then, we
Fig. 4 An example of traffic flows
derived the delay bound, backlog bound, and output flow
according to Lemma 1, 2, and 3 [2]. At node c, there are two input links and one output link.
The delay bound is, Then, the output flow, delay bound and backlog bound can be
calculated according to the method described in section 3-A-2.
γ jσ Assume the allocation strategy is rate-proportional allocation
Dj = + (1 − λ )T + τ (14)
λC strategy. Then,
And the backlog bound is, F1c ~ (σ 1 + ρ1 (1 − λc )T + τ , λc Cρ1 /( ρ1 + ρ 2 )) (17)
B = σ + ρ (1 − λ )T + ρτ (15)
F2c ~ (σ 2 + ρ 2 (1 − λc )T + τ , λc Cρ 2 /( ρ1 + ρ 2 )) (18)
*
Output traffic flow Fj is constrained by,
D1c = σ 1 ( ρ1 + ρ 2 ) /( ρ1λc C ) + (1 − λc )T + τ (19)
θ j = min(γ j ρ , λC )t + γ j (σ + ρ (1 − λ ) + ρτ ) (16)
D2c = σ 2 ( ρ1 + ρ 2 ) /( ρ 2 λc C ) + (1 − λc )T + τ (20)
For the traffic splitting operator, there could be cases that
ρ>λMC, which means the output bandwidth can not satisfy the And the backlog of node c is,
requirements. To avoid this, either the input data rate should be
constrained or the service rate should be enhanced. Otherwise, Bc = σ 1 + σ 2 + ( ρ1 + ρ 2 )((1 − λc )T + τ ) (21)
the data loss rate will be increasing.
At node d, there are one input link and two output links.
B. The Deterministic Analysis Method All the calculation can follow the method described in section
3-A-3. Use the same method, at node e and f, the output flows,
In this section, we present the deterministic analysis
delay bound and backlog bound can be calculated recursively
method as a whole. It works as follows:
according to the method described in section 3-A-1.
1. According to the topology of the sensor network and
After the above calculation, the burstiness and data rate of
the routing algorithm, obtain the routing paths of each
the output of flow F1 at the sink can be derived as expressions
traffic flow.
(22) and (23), respectively.
2. Based on the general traffic flow operators and analysis
methods proposed in section 3.1, construct traffic σ 1* = σ 1 + ρ1T [(1 − λc ) + (1 − λd ) + (1 − λe ) + 3τ ] (22)
flowing scenarios using the three general operators.
Then compute the output flow, delay bound and ρ1* = min(λeC , λd C , F1c ( ρ )) (23)
backlog bound for each traffic flow starting from the
source node. where F1c ( ρ ) denotes the data rate of flow F1 at node c.
3. Calculate the end-to-end delay bound. There are two The end-to-end delay bound can be calculated by adding the
ways to compute the end-to-end delay bound. The first individual delay at each node together. For flow F2, the results
method is summing up the per-hop delay together. The can be computed using the same method. From the results, we
other method was proposed by Lenzini et al. [11]. The can see that the output data rate is mainly limited by the
main idea of this method is to derive an equivalent bottleneck link. Therefore, if the delay bound and backlog
service curve for a given traffic flow based on the bound can not satisfy the requirements of applications, the duty
network calculus theory. And then the end-to-end delay cycle needs to be dynamically adjusted.
bound is calculated using the equivalent service curve.
Both approaches can be applied in our analysis method. IV. APPLICATION AND NUMERICAL RESULTS
C. An Example A. Wireless Sensor Network for Fresh Food Tracking
We show how the deterministic analysis method works In European market, approximately 10% of the whole cargo
through an example. Assume there are two flows F1 and F2, of fruits and vegetables coming from different parts of world
which are sourced from node a and b, respectively (Fig. 4). is deteriorated during the transportation process. This leads to
F1c and F2c denote the corresponding output traffic flow of F1 a loss of billions of dollars per year [12]. With the rapid
and F2 at node c. Assume the traffic models are F1~(σ1, ρ1) development of sensor network techniques, the loss can be
and F2~(σ2, ρ2), where σ1 and σ2 describe the burstiness, and ρ1 mitigated by deploying a sensor network to track the freshness
ρ2 denote the data rate [9]. Let the duty cycle and work period status of these kinds of food in real-time.
 In the scenario of real-time fresh food (e.g. meat, vegetable, Note that at a sensor node, its input data rate can be higher
fruits) tracking, sensors are deployed in the boxes filled with than its service rate due to a lower duty cycle configuration. If
fruits, vegetables and meat in a truck carriage (Fig. 5). Since this happens, data loss may occur when the backlog buffer is
the possible causes of food deterioration are microbiological full. Apparently, data loss is a big concern. To capture this in
infestation and improper environmental condition, four kinds our experiments, we define data delivery ratio as the amount
of sensors can be used in our application, which are humidity of data received by the sink versus that of data sent by the
sensor, temperature sensor, CO2 sensor, and O2 sensor. These sources.
sensors are responsible for collecting the corresponding To study how duty cycle impacts the performance of
information of food. All the data collected by sensors are sent sensor networks, we conduct several numerical experiments.
to a base station, which is put on the top of the truck. The base The number of nodes is 30. Fig. 6 shows that the packet
station then transmits the data to a remote server through delivery ratio decreases with traffic load increasing. And the
GPRS networks and Internet. Thus an expert at the remote packet delivery ratio can be enhanced by increasing the duty
server side can read and analyze the data in real-time. If cycle. In Fig. 7, we can see that the end-to-end worst-case
something is wrong or abnormal actions have happened, he delay increases when the traffic load increases. With the same
can send instructions to the base station to take measures, such traffic load, the delay decreases with duty cycle increasing.
as lowering the temperature of the cooling system or Therefore, when the data delivery ratio or the worst-case delay
sprinkling water onto fresh vegetables and fruits, to protect the can not meet the requirement of applications, the duty cycle
food from becoming deteriorated. In addition, there is a wired needs to be increased. Meanwhile, the power consumption can
connection between the base station and the driver monitor. So be more important than delivery ratio and delay. In these
the driver can also read the information collected by the cases, low duty cycle operations can be taken to save energy.
network and take proper measures if necessary. The size of As we mentioned in previous sections, traffic splitting
sensor networks applied in this application depends on the size mechanisms play an important role in load balancing. In order
of trucks. For small trucks, a 2-hop or 3-hop sensor network is to study the efficiency of traffic splitting strategies, we
enough. While for large trucks, a network of more hops is compared the data delivery ratio and average per-hop delay in
needed. different splitting strategies, which are no traffic splitting
(NoTS), averagely traffic splitting (AvTS) and randomly
traffic splitting (RaTS). Averagely traffic splitting means that
the traffic is averagely split at each sensor nodes, while
randomly traffic splitting means that the traffic is split with
random probabilities. In the following simulations, the duty
cycle of each sensor is 0.04. Fig.8 shows that when the traffic
load is bigger than 0.5, the data delivery ratio drops
dramatically when the traffic is not split. Compared with that
in NoTS, the data delivery ratios in AvTS and RaTS are
enhanced by 17.1% and 14.8%, respectively. In Fig. 9, the
Fig. 5 A sensor network for real-time fresh food tracking
average per-hop delay in AvTS and RaTS is lower than that in
non-traffic-splitting cases, with improvement 9.65% and
B. Numerical Experiments and Results 7.81%, respectively.
We have realized our deterministic analysis method using To show the performance of different network sizes, we
Matlab. The parameters used in the numerical experiment are devise the following experiments. The traffic load is set to be
as follows. We assume a sensor network was generated by 0.6, and the duty cycle is set to be 0.04. Fig. 10 and Fig. 11
randomly putting a number of sensors in the food boxes, show the delivery ratio and the worst-case delay scale with the
which are located in a truck carriage (Fig. 5). The base station number of sensors, respectively. In Fig. 10, we can see that the
acts as the sink. Therefore, a wireless sensor network with an delivery ratio decreases as the number of sensors increases.
irregular topology is set up. According to Mica2 mote 1 [13], However, by adopting the traffic splitting strategies AvTS and
we assume the link capacity C is 38.4 kbps and work period T RaTS, the data delivery ratio is enhanced by 20.5% and 17.7%,
is 1.096s [4]. We assume the packet size is 288 bits. The respectively. Moreover, Fig. 11 shows that the end-to-end
standard reporting frequency of each sensor is assumed to be worst-case delay is reduced by 28.8% and 25.2% in AvTS and
0.1 Hz, i.e. the sensor node sends one packet in every ten RaTS, respectively.
seconds, leading to a date rate of 28.8 bits/s. The burst size is To show the backlog variation with duty cycles and traffic
assumed to be the amount of data generated in two seconds. In splitting methods, we conduct two experiments. The traffic
the experiments, the traffic load is changed by varying the load is 0.5 for both figures, and the duty cycle is 0.08 for Fig.
reporting frequency from 0.1 Hz to 1 Hz. Moreover, we 13. B_min, B_ave, and B_max denote the minimum backlog,
assume there is no collision in the network since the effect of average backlog, and maximum backlog, respectively. These
collision is independent of traffic merging and splitting. values are obtained from backlog bounds at all sensor nodes.
In Fig. 12, we can see that the backlogs do not reduce much
1
The Mica2 mote is a mote module used for low-power wireless sensor when duty cycle increases from 0.04 to 0.15. However, the
networks (see [Link]
average backlog is much smaller than the maximum backlog adopts variable duty cycle operations and traffic splitting
with the same duty cycle. In this example, adjusting duty cycle strategies. The method is applied to analyze the performance
has smaller effect on reducing the backlogs. But by applying of the sensor network for fresh food tracking. With the
traffic splitting strategies, the maximum and average backlogs numerical results, we show that (1) increasing duty cycle and
can be greatly reduced. splitting traffic flows can improve data delivery ratio and
Traffic load VS. Delivery ratio Traffic load VS. Worst-case delay reduce the delay; and (2) variable duty cycle operations have
100
less significant effect on reducing the max and average
40
Duty cycle = 0.02
35 Duty cycle = 0.04
Delievery ratio (in percentage)

90
30
Duty cycle = 0.08 backlogs, while traffic splitting mechanisms can largely

Worst-case delay (s)

80
25 reduce the maximum backlog and average backlog. Hence, by
70 20 adjusting the duty cycle and traffic splitting mechanisms, the
60
Duty cycle = 0.02
15
performance requirements (such as delay, backlog and data
delivery ratio) of different applications can be satisfied.
10
Duty cycle = 0.04
50 Duty cycle = 0.08 5

40 0
Therefore, our proposed method not only provides an effective
way for a designer to estimate the worst-case performance of
0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1
Traffic load Traffic load

Fig. 6 Data delivery ratio Fig. 7 Worst-case delay sensor networks, but also can be used as a tool for network
with various duty cycles with various duty cycles reconfiguration after design.
100
Traffic load VS. Delievery ratio
7
Traffic load VS. Average delay For the future work, we intend to integrate fault tolerance
95
NoTS
AvTS
NoTS
AvTS into the analysis method. Furthermore, it is interesting to
Delievery ratio (in percentage)

explore the optimized design space with given buffer sizes,

RaTS RaTS
90
5
Average delay (s)

85
4 performance requirements, energy constraints, and service
strategies.
80
3
75
2
ACKNOWLEDGMENT
70

65 1

60
0 0.2 0.4 0.6 0.8 1
0
0 0.2 0.4 0.6 0.8 1 This work is supported by VINN Excellence iPack Center
Traffic load

Fig. 8 Data delivery ratio

Traffic load

Fig. 9 Average delay in

at Royal Institute of Technology (KTH), Sweden.
in various split methods different split methods
REFERENCES
Network size VS. Delievery ratio
100 45
Network size VS. Worst-case delay
[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A
NoTS
AvTS 40
NoTS
AvTS survey on sensor networks”, IEEE Comm. Magazine, pp. 102-114, 2002
Delievery ratio (in percentage)

90
RaTS
35
RaTS
[2] J. –Y. Le Boudec, and P. Thiran, “Network Calculus: A Theory of
Worst-case delay (s)

80
30 Deterministic Queuing Systems for the Internet”, Springer, LNCS 2050,
70 25
2004
20
[3] J. B. Schmitt, and Utz Roedig, “Sensor network calculus – A framework
60
15
for worst case analysis”, IEEE/ACM International conference on
50
10
Distributed Computing in Sensor Systems (DCOSS’05), USA, 2005
[4] J. B. Schmitt, F. A. Zdarsky, and Utz Roedig, “Sensor network calculus
40 5
10 20 30
Number of sensors
40 50 10 20 30
Number of sensors
40 50 with multiple sinks”, In proc. of IFIP networking, workshop on
Fig. 10 Data delivery Fig. 11 End-to-end worst-case performance control in wireless sensor networks, Portugal, 2006
ratio vs. network sizes delay vs. network sizes [5] Anis Koubaa, M. Alves, and E. Tovar, “Modeling and worst-case
dimensioning of cluster-tree wireless sensor networks”, the 27th IEEE
Backlog changing with duty cycles Backlog changing with splitting methods International Real-Time Systems Symposium (RTSS’06), Brazil, 2006
8000 7000
Duty cycle = 0.04 NoTS [6] H. She, Z. Lu, A. Jantsch, L.-R. Zheng, D. Zhou, “Traffic splitting with
7000 Duty cycle = 0.08
Duty cycle = 0.15
6000 RaTS
AvTS network calculus for mesh sensor networks”, the 2007 International
6000
5000 Workshop on Wireless Ad Hoc, Mesh and Sensor Networks
(WAMSNet’07), Korea, 2007
Backlog (bits)

Backlog (bits)

5000
4000
4000 [7] Sang Hoon Lee, Joon Ho Park, and Lynn Choi, “AMAC: Traffic-
3000
3000 adaptive sensor network MAC protocol through variable duty-cycle
2000
2000
operations”, In Proceedings of IEEE International Conference on
1000 1000 Communications (ICC’07), Scotland, 2007
0 0 [8] S.-J. Lee, M. Gerla, “Split multipath routing with maximally disjoint
B_min B_ave B_max B_min B_ave B_max
paths in ad hoc networks”, IEEE International Conference on
Fig. 12 Backlogs with Fig. 13 Backlogs in different Communications (ICC’01), 2001
different duty cycles splitting strategies
[9] R. Cruz, “A calculus for network delay, part I: Network elements in
isolation”, IEEE Trans. on Info. Theory, vol. 37, pp. 114-121, 1991
V. CONCLUSIONS [10] H. Zhang, “Service disciplines for guaranteed performance service in
packet switching networks”, Proceedings of the IEEE, 1995
In this work, we proposed a deterministic method for [11] L. Lenzini, L. Martorini, E. Mingozzi, and G. Stea, “Tight end-to-end
worst-case performance analysis in wireless sensor networks. per-flow delay bounds in FIFO multiplexing sink-tree networks”,
Three general traffic flow operators are defined to model any Performance Evaluation Journal(Elsevier), vol.63, pp 956-987, 2006
[12] Billerud AB, “The Billerud book of maths”, [Link]
traffic flowing scenarios. Based on the results from the basic [13] Crossbow Technology Inc., “MICA2 Datasheet” [Link]
operators, we presented the deterministic method, which