A Compact Hard Real-Time Operating System for Wireless Sensor Nodes
Shunsuke Saruwatari, Makoto Suzuki, and Hiroyuki Morikawa
Morikawa Laboratory
Research Center for Advanced Science and Technology
The University of Tokyo
Meguro-ku, Tokyo 153-8904, Japan
Email: {saru,makoto,mori}@mlab.t.u-tokyo.ac.jp
Abstract—The paper shows a compact hard real-time operating system for wireless sensor nodes called PAVENET OS.
PAVENET OS provides hybrid multithreading: preemptive multithreading and cooperative multithreading. Both of the multithreading is optimized for two kinds of task on wireless sensor
networks, and the kinds are real-time tasks and best-effort tasks.
PAVENET OS can efficiently perform hard real-time tasks thatcannot be performed by TinyOS. The paper demonstrates the
hybrid multithreading realizes compactness and low overhead,
which are comparable to those of TinyOS, through quantitativeevaluation. The results show PAVENET OS performs 100-Hz
sensor sampling with 0.01% jitter while performing wirelesscommunication tasks, whereas optimized TinyOS has 0.62%
jitter. In addition, PAVENET OS has a small footprint and low
overhead (minimum RAM size: 29 bytes, minimum ROM size:
490 bytes, minimum task switch time: 23 cycles).

I. I NTRODUCTION
Wireless sensor networks (WSNs) have a number of potential fields of application, including habitat monitoring, military applications [21], wildland fire monitoring [12], volcano
monitoring [24], and structural monitoring [16], [25], [15].
Each application has different requirements for communication
protocols and sensing tasks, and sensor nodes have very limited physical resources because of their design requirements,
namely, low power, low cost, and small size. In some cases,
sensor nodes must perform hardware-tightened tasks suchas radio management, which must be completed by highly
constrained deadline. Any operating system running on thesensor nodes should cover these requirements.
TinyOS [14] is a standard operating system for wirelesssensor nodes. TinyOS takes up only 47 bytes of RAM and473 bytes of ROM and switches tasks in several dozens
of cycles. This excellent compactness is provided by theevent architecture of TinyOS. In the event architecture, only
one main loop executes event handlers according to received
events, and the handlers never preempt each other.
However, the event architecture causes difficulties in performing hard real-time tasks and high programming complexity. In a real-time system, a higher priority task must preempt
other tasks, but the event architecture forbids preemption for
its compactness and small overhead.
In the present paper, we show a compact hard real-time operating system called PAVENET OS. To realize the hard realtime feature, PAVENET OS is designed with a thread modeland enabling preemption. The enabling preemption causes two
problems. First, the preemption induces huge overhead forchecking task priorities and saving CPU context. Second, thepreemption induces a conflict management problem among
tasks.
To reduce the preemption overhead, PAVENET OS uses acharacteristic of wireless sensor nodes: tasks can be categorized as real-time tasks or best-effort tasks. PAVENET OS
provides two kinds of multithreading, which are preemptive
multithreading and cooperative multithreading. The preemptive multithreading is optimized for the real-time tasks witha CPU specific design, and the cooperative multithreading is
optimized for the best-effort tasks. To mitigate the conflict
management problem, PAVENET OS uses another characteristic of wireless sensor nodes: most conflicts occur between
communication layers. PAVENET OS provides a wirelesscommunication stack for hiding the exclusive controls to users.
The hard real-time feature can perform 100-Hz sensor sampling while performing radio management tasks with 0.01%
jitter, whereas optimized TinyOS has 0.62% jitter. Additionally, PAVENETOS realizes compactness and low overhead thatare comparable to those of TinyOS. For example, PAVENET
OS can implement Blink, which is a sample program in
TinyOS [1], on 63 bytes of RAM and 1,183 bytes of ROM,
whereas TinyOS implements Blink on 44 bytes of RAM and
1,428 bytes of ROM. PAVENET OS also can switch tasks in
23 cycles minimally.
The present study is not intended to show that PAVENET
OS is the best operating system. In fact, in contrast to highly
portable TinyOS, PAVENET OS sacrifices portability because
PAVENET OS has a design specific to Microchip PIC18. Lackof portability is a significant problem. However, the results ofthe present study imply a better CPU design and operating
system design may exist for future wireless sensor networks.
The remainder of the present paper is organized as follows.
In the following section, we present the motivation for thisresearch and discuss the difference between the event modeland the thread model. In Section III, we provide the implementation details for the PAVENET OS in three parts: a hard realtime task scheduler, a best-effort task scheduler, and a wirelesscommunication stack. Section IV presents an evaluation of
the performance of PAVENET OS. Section V reviews related
research, and conclusions are presented in Section VI.
II. R EQUIREMENTS
Some applications in wireless sensor networks need toobtain data of sufficient quality to have real scientific value,and the applications include earthquake monitoring [22], volcano monitoring [24], and structural health monitoring [16],[25], [15]. The applications require high fidelity sampling.
For example, earthquake monitoring requires precise timesynchronized 100-Hz sampling, and tasks are periodically
executed with strict deadlines [16], [22]. In addition, basedon the success of TinyOS which is an event driven operating
system, we know that compactness is an important factor when
covering wide-area applications for wireless sensor networks
because compactness is strongly related to power consumption
over the entire sensor network.
The advantages of using either the event model or the
thread model have been discussed thoroughly [17], [20], [23],[14], [5]. It is difficult to strictly categorize all operating
systems as event models or thread models, and there are many
variations in programming style among models. To simplify
the discussion herein, we define an event model in the mannerof TinyOS [14], [9] and a thread model as traditional timesliced multithreading, such as the POSIX thread. The event
model has only one execution stream and forbids preemption among tasks: an event loop waits for events, an event
invokes a handler, and the event handler is executed in runto-completion. The thread model has multiple independent
execution streams, shared states, preemptive scheduling, andsynchronization schemes such as locks and conditions.
A. Event ModelIn wireless sensor network research, a number of operating
systems have been implemented with the event model, including TinyOS [14], SOS [11], Contiki [5], and protothreads [6].
The event architecture has two advantages. First, the user neednot be concerned with conflict management because all event
handlers execute in a run-to-completion manner and do notpreempt each other. This feature also reduces context switch
overhead because all task switches are realized by function
call. Second, event models can be implemented using limited
resources because of their simple structure, which consistsof a memory stack, an event loop, and event handlers. This
simplicity also allows portability of the system.
However, this simplicity causes two problems. First, theevent model cannot perform hard real-time tasks. To support
hard real-time tasks, the system must allow preemption. However, the event model does not allow preemption because theadvantages are strongly related to the absence of preemption.
For example, earthquake monitoring requires radio physicallayer tasks and exact 100-Hz sensor sampling [16], [22]. The
radio physical layer task has a 26-µs deadline and cycle,
and a 12.5-µs computation time. The precise 100-Hz sensorsampling task has a 10-ms cycle, a 2.2-µs computation time,and a 3.2-µs deadline. While TinyOS is performing a radio
physical layer task, the sampling task cannot be executed until
the radio physical layer task is finished. In fact, Kim et al. [15]struggled with temporal jitter caused by logging interferencesin sampling. They succeeded to reduce the jitter with MicroTimer and turning off all unnecessary components on TinyOS.
We note that the MicroTimer breaks the simplicity of theevent model because the MicroTimer is implemented inside aninterrupt handler. The implementation causes resource conflictproblems.
Second, the event model has high programming complexity
because the event model has to divide a sequence of tasks
into multiple event handlers. With the words of Dunkels etal. [6]: “an event-driven model does not support a blocking
wait abstraction. Therefore, programmers of such systems
frequently need to use state machines to implement control
flow for high-level logic that cannot be expressed as a single
event handler.” The following code is Blink, which is a TinyOS
sample program that toggles an LED every one second [1].
[Blink.nc]
configuration Blink {}implementation {components Main, BlinkM, SingleTimer, LedsC;
Main.StdControl -> BlinkM.StdControl;
Main.StdControl -> SingleTimer.StdControl;
BlinkM.Timer -> SingleTimer.Timer;
BlinkM.Leds -> LedsC;}[BlinkM.nc]
module BlinkM {provides {interface StdControl;}uses {
interface Timer;interface Leds;}}
implementation {command result_t StdControl.init() {call Leds.init();return SUCCESS;}
command result_t StdControl.start() {return call Timer.start(TIMER_REPEAT, 1000);}
command result_t StdControl.stop() {return call Timer.stop();}
event result_t Timer.fired() {call Leds.redToggle();return SUCCESS;}}The user has to write this redundant code, even for a simple task such as making an LED blink. This redundancy
causes difficulty in understanding the code and debugging.
To reduce the programming complexity, Dunkels et al. [6]proposed a programming abstraction for the event model called
protothreads. Protothreads makes it possible to write an event
model in a thread-like style. However, protothreads still does
not support hard real-time tasks.
B. Thread Model
The thread model can support hard real-time tasks because
it allows preemption. Allowing preemption is not a sufficientcondition, but a necessary condition, to support hard real-timetasks. For example, MANTIS is a time-sliced multithreading
operating system for wireless sensor networks, but does notsupport hard real-time tasks [4]. In the thread model, the user

TABLE I
E VENT MODEL VS . THREAD MODEL

compactness
low overhead
conflict management
hard real-time support
programming complexity

event model



×
×

thread model
×
×
×



can also understand the control flow easily because he/she
can code tasks as if they dominate a CPU. Consider the
implementation of Blink with the thread model. The programis as follows:
void thread(void){
while(1){toggle_led();sleep(1);}}Compare this code to the TinyOS source code in Section II-A.
The thread model can implement this program with a smaller
code size than the event model, even if the codes represent
the same task.
However, in contrast to the event model, the thread model
does not have a simple structure, and the user must consider
conflict management with shared data, and the task switch
overhead is high because the thread model operating system
has to save the CPU context at every preemption point.
In addition, a memory stack is required for each execution
stream. These features increase the memory consumption ofoperating systems. For example, MANTIS occupies less than
500 bytes of RAM and approximately 14 KB of ROM [4]. Thisis natural because the thread model provides an intermediate
layer between the hardware and the software, whereas theevent model is placed directly on the hardware.
We conclude the discussion about the event model and thethread model to Table I. Both models have advantages anddisadvantages. The event model is compact, low overhead,and need not manage resource confliction. However, the event
model cannot handle hard real-time tasks and has high programming complexity. The thread model can support hard realtime tasks, and has lower programming complexity. However,
the thread model is not compact, has high overhead, and needmanage resource confliction among tasks. The challenge is todevelop an operating system that has the following features:• hard real-time support• compactness• low overhead• low programming complexity
III. PAVENET OS
We design a compact hard real-time operating system called
PAVENET OS with enabling preemption. As mentioned in
Section II-B, the preemption induces preemption overhead anda conflict management problem.
To reduce the preemption overhead, we use characteristics
of tasks in wireless sensor networks: tasks can be categorized

as real-time tasks or best-effort tasks. PAVENET OS provides
two kinds of multithreading: preemptive multithreading forreal-time tasks and cooperative multithreading for best-effort
tasks. Both of the multithreading is optimized for the tasks.
To mitigate the conflict management problem, PAVENET OS
also provides a wireless communication stack. The wirelesscommunication stack hides exclusive controls between layers
in wireless sensor networks.
A. Hard Real-time Task Scheduler
PAVENET OS provides a hard real-time task scheduler for
real-time tasks, and the real-time tasks have a task priorityand preempt lower priority tasks. The real-time tasks include
radio management, sensor sampling, and media access control.
Although the task priority and the preemption causes taskscheduling/switching overheads, PAVENET OS performs realtime tasks in low overhead because PAVENET OS aggressively uses functions of PIC18, namely, dynamic priority levels
and a fast return stack.
PIC18 is a microcontroller developed by Microchip andhas several interrupt sources, e.g., timers, external ports, a
Master Synchronous Serial Port (MSSP), and a Universal
Synchronous Receiver Transmitter (USART). Each sourceis dynamically assigned to a high priority level or a low
priority level. High-priority interrupt events can interrupt any
low-priority tasks and best-effort tasks. Low-priority interrupt
events can interrupt any best-effort tasks. PIC18 also has afast return stack, which automatically saves the CPU context
when an interrupt occurs. In control registers, each interrupt
has three bits to control their operation: a flag bit, an enable bit,and a priority bit. The flag bit indicates whether an interrupt
event has occurred. The enable bit allows the program to
execute an interrupt when the flag bit is set. The priority bit
selects high priority or low priority. For example, a timer0
interrupt has TMR0IF as a flag bit, TMR0IE as an enable bit,and TMR0IP as a priority bit.
In PAVENET OS, each real-time task corresponds to eachinterrupt vector. Therefore, there are no software transaction
in task switching and task scheduling. PAVENET OS decides
priority of real-time tasks according to their deadlines, andmultiple tasks can have same priority: the low priority tasks
must not have smaller deadline than high priority tasks. The
real-time task scheduling is categorized to deadline-monotonic
scheduling [18], [3]. Deadline-monotonic scheduling can assign optimized priority to guarantee a deadline in a single CPU[18].
We can test the sufficient condition of the schedulability
with deadline monotonic scheduling [18], [3]. The following
is a schedulability test presented in [3].
All tasks are characterized byCi ≤ Di ≤ Ti
where Ci is the computation time, Di is the deadline,
and Ti is the period of task τi . In addition, task τ1
represents the highest priority task and τn represents

TABLE IITASK CONTROL BLOCK. A TASK CONTROL BLOCK IN PAVENET OS USESONLY 40 BITS PER THREAD .

the lowest priority task. Then, schedulability test is
given by:∀i : 1 ≤ i ≤ n :

Ii
Ci
+
≤1
Di
Di

name
tid
state
pc
sleep_time(1)

where Ii is a measure of higher priority tasks interfering with the execution of τi :
Ii =


i−1 

Di
Tj

j=1

Cj .

If a task τi satisfies equation (1), the task τi isschedulable.
In Equations (1) and (2), the scheduler has n priority levels
and each priority corresponds to a task. However, PAVENET
OS has only two priority levels and can assign multiple tasks
to a priority level. Therefore, the schedulability test for PAVENET OS is as follows.
Suppose there are n high-priority tasks. The schedulability
test for high-priority tasks is given by:(3)

where Ii is a measure of tasks having the same priority
interfering with the execution of τi :


 

n 

Di
D
i


Ii =
Cj −
Ci
T
Ti
j
j=1



n 

Di
= 
Cj  − Ci .
Tj
j=1
Therefore, Equation (3) is:


Ci
Ii
+
Di Di

n

Di
j=1 Tj Cj − Ci
Ci
=
+
Di
Di

n
 Di  Cj=≤ 1.
T j Dij=1(4)

If a task τi satisfies equation (4), the task τi is schedulable.
Next, we show the schedulability test for low-priority tasks
τk . When there are n high-priority tasks and m low-priority
tasks, the schedulability test is given by:
Ck
Ik
+
≤1
Dk
Dk
where Ik is a measure of all tasks interfering with theexecution of τk :
 

n+m
  Dk 
Dk
Cl −
Ck
Ik =
Tl
Tk
l=1

n+m
  Dk =
Cl − Ck .
Tll=1

meaning
thread ID
thread state
program counter
time to wake

TABLE IIITASK CONTROL FUNCTIONS . PAVENET OS PROVIDES SEVEN SYSTEMCALLS FOR TASK MANAGEMENT.

(2)

Ii
Ci
+
≤1
Di
Di

size
8 bit
8 bit
16 bit8 bitfunction nameadd_task(funcname)os_yield()
sleep(time)
sig_wait()suspend_task(pid)signal_task(pid)kill_task(pid)transaction
add task to scheduler
yield control
sleep time sec
wait signal
let pid to wait
let pid to execute
let pid to be deadsetting state
executeexecutesleep
wait
executeexecuteexecuteThis gives a schedulability constraint of:n+m Dkl=1
Tl Cl − Ck
Ck
Ik
Ck
+
=
+
Dk
Dk
Dk
Dk


n+m
 Dk Cl=≤ 1.
T l Dk(5)

l=1

If a task τk satisfies equation (5), the task τk is schedulable.
B. Best-effort Task Scheduler
PAVENET OS performs hard real-time tasks with preemption, as described in Section 3.1, and other tasks are performed
with a best-effort task scheduler. The best-effort tasks include
hop-by-hop routing, delay writing to flash memory, and replying to sensor data query.
We develop the best-effort task scheduler with the thread
model and add three limitations for compactness and low
overhead to the threads. First, these threads only switch context
cooperatively. Cooperative task switching eliminates the needfor conflict management and only preserves a program counteras CPU context. Second, these threads can only yield the top
level of a function. Although we can yield anywhere in thefunction if the scheduler preserves the entire call stack, we
do not use this approach because it consumes a great deal ofmemory and computation time. Third, these threads do notuse stack memory. Because of this limitation, CPUs need nothave a stack memory. Although PIC18 has a call stack, it does
not have a stack memory, and a heap memory is assigned tovariables at compilation time. Because of these limitations,these threads forbid reentrance and duplication.
Table II represents a task control block on the best-effort
task scheduler. tid is the thread identifier, which the scheduler allocates to a thread when the thread is created. stateis the state of the thread. These threads have four states: dead,
execute, sleep, and wait. These states are transited with task
management functions as shown in Table III. pc is a programcounter at the current executing thread. sleep_time represents a time to wake. PAVENET OS ticks jiffies, and thescheduler increments jiffies every 100 ms.
Table III lists the task management functions. Since PAVENET OS has the limitations mentioned above, tasks can beswitched with very simple code:
void os_yield(void){pcounters[current_task] = TOS;
asm("pop");}where TOS is the program counter.

Fig. 1.

PAVENET modules

C. Wireless Communication Stack
To reduce user fatigue caused by conflict management, we
use a characteristic of wireless sensor nodes: most conflicts
occur between communication layers. For example, when aphysical layer receives a packet, the physical layer accesses
a receive buffer in a media access control (MAC) layer, andthe MAC layer also accesses the receive buffer to run a MAC
protocol. PAVENET OS hides these exclusive controls in thewireless communication stack, and the user need not consider
conflict management. The wireless communication stack also
realizes modularity at each communication layer, and the user
can easily develop various communication protocols according
to application demands.
To efficiently exchange data among layers, PAVENET OS
provides a buffer management mechanism called pbuf, which
is a lightweight version of BSD mbuf. Since the pbuf assigns asmall identifier to a buffer, each layer only needs to copy small
identifiers. Pbuf also provides APIs, which hides exclusive
controls for the buffer management in pbuf.
IV. E VALUATION
To evaluate PAVENET OS, we compare the precision of thehard real-time task scheduler, the compactness, the execution
overhead, and the programming complexity to those of TinyOS
1.10 running on MICA2 [13]. PAVENET OS is implemented
with the HI-TECH PICC-18 compiler and run on PAVENET
modules.
Table IV lists the specifications of PAVENET modules
and MICA2, and PAVENET modules are shown in Figure
1. PAVENET modules and MICA2 have the same level of
TABLE IVE VALUATED SENSOR NODES

CPU
frequency
instruction per second
wireless module
wireless frequency
wireless modulation
power voltage
current (receiving)current (sleep)
communication rate

PAVENET module
PIC18LF4620
20 MHz5 MIPS
CC1000315 MHz
FSK
DC3V
30 mA
0.3µA
38.4 kbps

MICA2
ATmega128L
7.4 MHz
7.4 MIPS
CC1000315 MHz
FSK
DC3V
30 mA
30µA
19.2 kbps

equipment. PAVENET modules have PIC18LF4620 as a CPU
and TI CC1000 as a radio module. The operating frequency of
the CPU is 20 MHz, but the number of instructions-per-second
is 5 MIPS because PIC18LF4620 performs an instruction
per four clock cycles. The wireless communication speedof PAVENET modules is 38.4 kbps, but we changed it to19.2 kbps in order to allow fair comparison with MICA2.
MICA2 has Atmel ATmega128 as a CPU and CC1000 asa radio module. The operating frequency of the CPU is
7.4 MHz, and the number of instructions per second is 7.4
MIPS because ATmega128 performs one instruction per one
clock cycle. Although ATmega128 and PIC18LF4620 havedifferent architectures, they target the same application area.
We note that TinyOS can port to PAVENET modules, but
PAVENET OS cannot port to MICA2 because of its CPUspecific architecture.
A. Hard Real-time Tasks
To evaluate hard real-time tasks, we assume tasks inearthquake monitoring [16], [22] as an actual application
for wireless sensor networks. Earthquake monitoring requires
sampling at precisely 100 Hz with radio communication
because each sampling must be synchronized among sensor
nodes.
Table V shows evaluation results. ‘Sampling’ is the sensor
node performing only a 100-Hz sampling task, and ‘Sampling+ RF’ is the sensor node performing a 100-Hz sampling task
while receiving packets from another node, which sends apacket every 50 ms. All of the packet loss rates were 0%.
‘TinyOS (default)’ uses the Timer component [2] for sampling,and ‘TinyOS (optimized)’ uses the MicroTimer. The optimized
TinyOS assumes a same setting with [15]. As mentioned in
Section II-A, the use of the MicroTimer breaks simplicity ofthe event model. To sample at precisely 100 Hz, the sensor
node must generate precise 10 ms intervals. We measured
the intervals 2,000 times and obtained a maximum value, aminimum value, and a jitter.
The results indicate that PAVENET OS realizes 100-Hz
sampling much more precisely than TinyOS, as shown in Table
V. The default TinyOS cannot perform precise 100-Hz sampling, even if performing only the sampling task. The Timercomponent on TinyOS adjusts the timer firing timing between

TABLE V
H ARD REAL -TIME PERFORMANCE

Sampling
Sampling + RF

max
10.001 ms
10.001 ms

PAVENET OS
minjitter
10.000 ms 0.001 ms
10.000 ms 0.001 ms

TinyOS (default)max
minjitter
9.764 ms
9.763 ms 0.001 ms
11.735 ms 7.794 ms 3.941 ms

TABLE VIK ERNEL FOOTPRINT

moduletask scheduler
wireless communication stacktotal

RAM (byte)
29
628
657

ROM(byte)
490
930
1,420

TABLE VIIF OOTPRINT SIZE ON THE SAMPLE APPLICATIONSBlink (byte)
BlinkTask (byte)
CntToLeds (byte)
CntToRfm (byte)
CntToLedsAndRfm (byte)

PAVENET OS
RAM
ROM
63
1,183
64
1,271
64
1,209
676
11,336676
11,366

TinyOS
RAM
ROM
44
1,428
45
1,452
46
1,570
388
9,918
388
10,096

9-10 ms. Therefore, when the default TinyOS samples withradio communication, the sampling error becomes significant
because the adjustment is tumbled by the radio communication
tasks. The optimized TinyOS can perform precise 100-Hz
sampling at 0.003 ms or 0.03% jitter, if performing only the
sampling task. The jitter becomes significant at 0.062 ms or
0.62%, when the optimized TinyOS performs the samplingtask with radio communication. On the other hand, PAVENET
OS can always sample at precisely 100 Hz, even with radio
communication, and the jitter is much smaller at 0.001 ms or
0.01%.
B. Compactness
We show that PAVENET OS has compactness comparable
to that of TinyOS. To evaluate the compactness, we measure
the RAM sizes and ROM sizes of PAVENET OS and TinyOS.
First, we measure the footprint of the scheduler and thewireless communication stack, as shown in Table VI. The
task scheduler occupies 29 bytes of RAM and 490 bytes of
ROM when there are no connected libraries and the maximum
number of tasks is five. As extra 5 bytes of RAM per task
is required when the user needs to increase the maximum
number of tasks. Typically, the thread model has a smaller
number of tasks than the event model, because the user uses
one task for a sequence of tasks in the thread model. Accordingto [14], TinyOS requires 47 bytes of RAM and 473 bytes
of ROM when there are no connected modules. Therefore,
the PAVENET OS scheduler footprint is as small as that of
TinyOS. The wireless communication stack consumes 628
bytes of RAM and 930 bytes of ROM. The consumed RAM

TinyOS (optimized)max
minjitter
10.003 ms 10.000 ms 0.003 ms
10.062 ms 10.000 ms 0.062 ms

size is not small because the wireless communication layer has
many buffers for receiving and sending in the physical layer,
pbuf, and queues in the layers, which consume a great deal ofmemory.
Next, we measure the size of the footprint for sample
applications. We implemented the applications provided by
TinyOS, namely, Blink, BlinkTask, CntToLeds, CntToRfm, and
CntToLedsAndRfm [1]. Blink and BlinkTask toggle an LED
on the sensor node every second. The difference between
Blink and BlinkTask is how the task is implemented. Blink
implements timer handling and LED toggling in a single
task. BlinkTask implements timer handling and LED toggling
in two different tasks, and the timer handling task signals
the LED toggling task. CntToLeds increments a counter andsends the counter value to the LEDs on the sensor node.
CntToRfm increments a counter and sends the counter value
via radio. CntToLedsAndRfm is the combination of CntToLeds
and CntToRfm. CntToLedsAndRfm increments a counter, sends
the counter value to LEDs on the sensor node, and sends thecounter value to other sensor nodes via radio.
Table VII compares the RAM size and the ROM size for applications on PAVENET OS and TinyOS. The results indicatethat PAVENET OS has comparable compactness to TinyOS.
PAVENET OS uses more RAM and less ROM than TinyOS
when the applications do not have radio communication, andthe applications are Blink, BlinkTask, and CntToLeds. The
reason for this is as follows. TinyOS divides one sequenceof tasks to many small run-to-completion tasks. The division
allows tasks to reuse the RAM area, but occupies more ROM
area. On the other hand, PAVENET OS uses one task for asequence of tasks, and this unification consumes RAM becausetasks cannot reuse RAM. However, the unification saves ROM.
When the applications have radio communication such as
CntToRfm or CntToLedsAndRfm, PAVENET OS requires more
RAM and more ROM than TinyOS because PAVENET OS has
the wireless communication stack, as shown in Table VI.
C. Overhead
Figure 2 shows the task switch overhead for various tasks,
and the tasks are the net task and the user task as best effort
tasks, the mac task as a low-priority real-time task, and thephy task as a high-priority real-time task. The low-priority task
can preempt best effort tasks in 66 cycles. The high-priority
task can preempt best effort tasks or low-priority tasks in 23
cycles. When a best effort task yields the CPU, the best effort
task switches to another best effort task in 92 cycles. Task
switch overheads are relatively low. For example, MANTIS
switches tasks in approximately 400 cycles [4], and TinyOS

phy

high

low

phy

preemption
23 cycles

return6 cyclesmac

mac

preemption
23 cycles

preemption
66 cycles

return64 cycles

net

net

normalinterrupt low

interrupt highFig. 2.

context switch
92 cycles

PAVENET OS
17.0
16.9

TinyOS
17.1
17.2

user task

interrupt highTABLE VIIIAVERAGE EXECUTION CYCLES ON SAMPLE APPLICATIONS NOTINCLUDING RADIO COMMUNICATIONPAVENET OS
8.5
134.5
147.0

RADIO COMMUNICATION

CntToRfm (ms)
CntToLedsAndRfm (ms)

Task switch overhead

Blink (cycle)
BlinkTask (cycle)
CntToLeds (cycle)

TABLE IXAVERAGE EXECUTION TIMES ON SAMPLE APPLICATIONS INCLUDING

TinyOS
19.5
123.5
155.5

switches tasks in 51 cycles [14].
PAVENET OS has low overhead, on the same level as
TinyOS, when implementing the same sample applications
provided by TinyOS. These applications are described in
Section IV-B. First, we measured the average execution cyclefrom the timer being fired until the end of the sequence oftasks on Blink, BlinkTask, and CntToLeds, as shown in Table
VIII. The average cycle was calculated from 100 execution
cycles. We use “cycle” as the unit because PAVENET modules
and MICA2 have different clock frequencies. In Blink and
CntToLeds, PAVENET OS is slightly faster than TinyOS
because TinyOS has small overhead at joints between modules.
In BlinkTask, PAVENET OS is slightly slower than TinyOS
and the result corresponds to the task switch overhead.
Second, we measured the average execution time fromthe timer being fired until the end of packet transmission
on CntToRfm and CntToLedsAndRfm, as shown in Table IX.
We use time, rather than cycles, as the unit because theexecution time is strongly related to the packet length andcommunication overhead. Although PAVENET OS has thewireless communication stack and PAVENET modules run
slower MIPS than TinyOS, the results are almost the same.
The results represent the wireless communication stack on
PAVENET OS has relatively low overhead.
V. R ELATED R ESEARCH
There are a number of operating systems for wireless sensor
nodes, including TinyOS [14], [9], SOS [11], Contiki [5],Nano-RK [8], MANTIS [4], protothreads [6], and t-kernel[10]. Most of these operating systems are designed with theevent model. As mentioned in Section II, the event modelcannot support hard real-time tasks, and has high programming
complexity.
TinyOS [14] is the de facto standard operating system
for wireless sensor nodes. TinyOS was designed with theevent model, and so does not support hard real-time tasks
and has high programming complexity. TinyOS attempts to
reduce the programming complexity through a new eventdriven specific language called nesC [9], which enhances
reusability of components. However, this solution means thatthe user has to learn a new language.
SOS [11] is another event model operating system. SOS
has a loadable programming module feature, whereas TinyOS
has a statically linked system image. The loadable module
is lightweight and can be written in C. In SOS, the user
can update modules after the sensor nodes are deployed.
However, SOS cannot support hard real-time tasks and has
high programming complexity.
Contiki [5] is an event model operating system. To reduce
the programming complexity, as an option, Contiki can support
time-sliced preemptive multithreading by assigning a memory
stack to each thread. The memory assignment consumes
computational resources. In addition, the threads destroy thesimplicity of event models, e.g., the user must manage resource
confliction. Moreover, Contiki cannot support hard real-timetasks even if the user uses the threads.
Protothreads [6] have an implementation similar to that of
the cooperative task scheduler of PAVENET OS. Protothreads
is an extension of the event model designed to reduce theprogramming complexity. The event model must divide atask into multiple run-to-completion functions. Protothreads
provide a conditional blocking wait statement to the event
model. The user can then write a program in a thread-likestyle. When using the conditional blocking wait, the user
inserts PT_BEGIN and PT_END at the top and the bottom
respectively, of the event handler. Protothreads reduce theprogramming complexity of the event model, but does not
solve all of the problems in the event model. In particular,
protothreads cannot support hard real-time tasks.
The Nano-RK[8] is the most closely related work to
PAVENET OS. Nano-RK is a preemptive multitask operating
system supporting real-time tasks. Additionally, Nano-RK ismore portable than PAVENET OS. However, Nano-RK has
more context switch overhead than PAVENET OS because
Nano-RK has to preserve CPU context by software. NanoRK needs several dozens of µs for task switching whereas
PAVENET OS needs several µs.
Like PAVENET OS, MANTIS [4] is a thread model operating system. The difference between MANTIS and PAVENET
OS is the implementation of the thread model. MANTIS
uses time-sliced multithreading, whereas the threading of
PAVENET OS is not time-sliced. To realize time-sliced multithreading, MANTIS assigns a stack memory for each task.

Therefore, MANTIS consumes more RAM than PAVENET
OS. Furthermore, MANTIS does not support hard real-timetasks.
T-kernel [10] is also a thread model operating system, andprovides virtual memory and preemptive scheduling. Since
the preemptive scheduling has 16 priority levels, the t-kernel
might be able to support hard real-time tasks. However, [10]does not evaluate its schedulability, hard real-time performance, and overhead. In addition, t-kernel does not provide
any mechanism to hide exclusive controls like the wirelesscommunication stack on PAVENET OS.
VI. C ONCLUSION
The present paper has described PAVENET OS, a compact
hard real-time operating system for wireless sensor nodes.
PAVENET OS can be implemented on the same amountof computational resources as TinyOS, and, unlike TinyOS,
PAVENET OS supports hard real-time tasks and has low
programming complexity. In addition, since a wireless communication stack is provided, the user need not consider the
exclusive controls caused by hard real-time tasks. The resultsof the present study imply that hardware support by CPU
can extend the functions of an operating system without aloss of compactness. For future wireless sensor nodes, it may
be necessary to reconsider the balance between hardware andsoftware.
We are currently working on the integration of a CPU
design and an operating system design for ultra low-power
wireless sensor networks[19]. Ekanayake et al. have alreadysucceeded to implement an ultra low-power processor using
software/hardware co-design based on the event model [7].
We believe that designing a CPU based on the thread model,such as a many-core design, also dramatically reduces energy
consumption and covers a wider range of applications for
future wireless sensor networks.
R EFERENCES[1] http://tinyos.cvs.sourceforge.net/tinyos/tinyos-1.x/apps/.
[2] http://tinyos.cvs.sourceforge.net/tinyos/tinyos-1.x/tos/system/TimerC.nc.
[3] N. Audsley, A. Burns, M. Richardson, and A. Wellings. Hard realtime scheduling: The deadline-monotonic approach. In Proceedings of
the 8th IEEE Workshop on Real-Time Operating Systems and Software(RTOSS’91), pages 133–137, Atlanta, Georgia, May 1991.
[4] S. Bhatti, J. Carlson, H. Dai, J. Deng, J. Rose, A. Sheth, B. Shucker,
C. Gruenwald, A. Torgerson, and R. Han. MANTIS OS: An Embedded
Multithreaded Operating System for Wireless Micro Sensor Platforms.
ACM Mobile Networks & Applications (MONET), Special Issue on
Wireless Sensor Networks, 10(4):563–579, August 2005.
[5] A. Dunkels, B. Gronvall, and T. Voigt. Contiki - a Lightweight andFlexible Operating System for Tiny Networked Sensors. In Proceedingsof the 29th Annual IEEE International Conference on Local Computer
Networks (LCN’04), pages 455–462, Tampa, Florida, November 2004.
[6] A. Dunkels, O. Schmidt, T. Voigt, and M. Ali. Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded
Systems. In Proceedings of the 4th ACM Conference on Embedded
Networked Sensor Systems (SenSys’06), Boulder, Colorado, November
2006.
[7] V. Ekanayake, C. Kelly, IV, and R. Manohar. An ultra low-powerprocessor for sensor networks. In Proceedings of the 11th International
Conference on Architectural Support for Programming Languages andOperating Systems (ASPLOS’04), pages 27–36, Boston, Massachusetts,
October 2004.

[8] A. Eswaran, A. Rowe, and R. Rajkumar. Nano-RK: An energyaware resource-centric rtos for sensor networks. In Proceedings of the
26th Real-Time Systems Symposium (RTSS’05), pages 256–265, Miami,
Florida, December 2005.
[9] D. Gay, P. Levis, and R. von Behren. The nesC Language: A
Holistic Approach to Networked Embedded Systems. In Proceedingsof Conference on Programming Language Design and Implementation(PLDI’03), pages 1–11, San Diego, California, June 2003.
[10] L. Gu and J. A. Stankovic. t-kernel: Provide reliable OS support for
wireless sensor networks. In Proceedings of the 4th ACM Conference on
Embedded Networked Sensor Systems (SenSys’06), Boulder, Colorado,
November 2006.
[11] C. C. Han, R. Kumar, R. Shea, E. Kohler, and M. B. Srivastava. A
Dynamic Operating System for Sensor Nodes. In Proceedings of the 3rdInternational Conference on Mobile Systems, Applications, and Services(MobiSys’05), pages 163–176, Seattle, Washington, June 2005.
[12] C. Hartung, R. Han, C. Seielstad, and S. Holbrook. FireWxNet: A MultiTiered Portable Wireless System for Monitoring Weather Conditions in
Wildland Fire Environments. In Proceedings of the 4th International
Confernce on Mobile Systems, Applications, and Services (MobiSys’06),
Uppsala, Sweden, June 2006.
[13] J. Hill and D. Culler. MICA: A Wireless Platform for Deeply Embedded
Networks. In IEEE Micro, volume 22, pages 12–24, NovemberDecember 2002.
[14] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. System
Architecture Directions for Networked Sensors. In Proceedings of the
9th International Conference on Architectural Support for Programming
Languages and Operating Systems (ASPLOS’00), pages 93–104, Boston,
Massachusetts, November 2000.
[15] S. Kim, S. Pakzad, D. Culler, J. Demmel, G. Fenves, S. Glaser, and
M. Turon. Health monitoring of civil infrastructures using wirelesssensor networks. In Proceedings of the 6th International Synposiumon Information Processing in Sensor Networks (IPSN’07), Cambridge,
Massachusetts, April 2007.
[16] N. Kurata, S. Saruwatari, and H. Morikawa. Ubiquitous Structure
Monitoring using Wireless Sensor Networks. In Proceedings of theInternational Symposium on Intelligent Signal Processing and Communication Systems (IPACS’06), Tottori, Japan, December 2006.
[17] H. C. Lauer and R. M. Needham. On the Duality of Operating System
Structure. ACM SIGOPS Operating System Review, 13(2):3–19, April
1979.
[18] J. Y. Leung and J. Whitehead. On the Complexity of Fixed-Priority
Scheduling of Periodic, Real-Time Tasks. Performance Evaluation,
2(4):237–250, December 1982.
[19] S. Ohara, M. Suzuki, S. Saruwatari, and H. Morikawa. A prototype ofa multi-core wireless sensor node for reducing power consumption. In
Proceedings of the Workshop on Power Consumption in Future Network
Systems (PCFNS’08), Turku, Finland, July 2008.
[20] J. Ousterhout. Why Threads Are A Bad Idea (for most purposes). In
USENIX 1996 Annual Technical Conference (Invited Talk), San Diego,
California, January 1996.
[21] G. Simon, M. Maroti, and A. Ledeczi. Sensor Network-Based Countersniper System. In Proceedings of the 2nd ACM Conference on Embedded
Network Sensor Systems (SenSys’04), Baltimore, Maryland, November
2004.
[22] M. Suzuki, N. Kurata, S. Saruwatari, and H. Morikawa. A highdensity earthquake monitoring system using wireless sensor networks.
In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys’07), pages 373–374, Sydney, Australia,
November 2007. demo.
[23] R. von Behren, J. Condit, and E. Brewer. Why Events Are A Bad Idea
(for High-Concurrency Server). In Proceedings of the 9th Workshop on
Hot Topics in Operating Systems (HotOS IX), Lihue, Hawaii, May 2003.
[24] G. Werner-Allen, K. Lorincz, J. Johnson, J. Lees, and M. Welsh. Fidelity
and yield in a volcano monitoring sensor network. In Proceedingsof the 7th USENIX Synposium on Operating Systems Design and
Implementation (OSDI’06), Seattle, Washington, November 2006.
[25] N. Xu, S. Rangwata, K. K. Chintalapudi, D. Ganesan, A. Broad,
R. Govindan, and D. Estrin. A Wireless Sensor Network for Structural
Monitoring. In Proceedings of the 2nd ACM Conference on Embedded
Network Sensor Systems (SenSys’04), Baltimore, Maryland, November
2004.