TinyOS
Morgan Leider
Computer Science
UW-Platteville
Abstract
As technology advances, the hardware to create wireless sensor networks is quickly being realized. But the software of the past is not capable of driving this new revolution in wireless networking. TinyOS and it’s many applications are the answer to the networking problems of tomorrow.
Introduction
This paper examines TinyOS, the most popular operating system used to drive wireless networks. Created at UC-Berkeley, TinyOS is an open-source project available for free on the internet. The problems of power usage, data collision, and mass propagation are all addressed by TinyOS and its’ applications. Throughout this paper, TinyOS and several of the most popular applications used with it will be examined and explained.
History and General Features
What features was TinyOS designed to support? First of all, it was designed for cross-layer control. A wireless node often has to handle multiple jobs at once, and be able to control its resources in order to prevent device conflicts and maintain data integrity. After that, it was coded for static resource allocation. All resources are known at compile-time and nothing is dynamically allocated. This was mainly due to the very limited resources of wireless nodes. And lastly, it was designed for snooping and maintaining scheduled communication. Snooping allows nodes to hear what other nodes are talking about. This allows nodes to determine if their current data is up to date or not. If its not, they can request the new data be sent, or just download it as their snooping. Scheduled communication is a very important part of wireless networking. If nodes don’t operate on schedules, their lifetime is measured in days to weeks due to the power consumption of always being powered up and listening. Scheduling allows nodes to go into a powered down state a great deal of the time, extending their lifetime to months and years.
Design
What was TinyOS designed to do? Obviously it was designed to work with current and future sensor networks. It was made highly modular, with the ability to customize and adapt it to almost any hardware and support almost any feature someone would want to add. It was written in a C like language so that most programmers could sit down and understand it with little research. And most importantly, it was designed to address the unusual challenges posed by wireless sensor networks. Things like power consumption, collisions, data propagation, dynamically changing network environments, and synchronization all have to be supported.
Applications
Next I’ll go into some of the real world applications that TinyOS can be applied to.
Habitat Monitoring
Scientists and biologists could use nodes to track the changes in temperature, moisture, air movement, and almost any other environmental factor with wireless sensor networks. This would allow widespread and accurate monitoring of places like rainforests, remote islands, deserts, and other places separated from civilization.
Shooter Localization
Another use of wireless networks would be shooter localization. Imagine there is a war in a dense jungle or swampland. A sniper or two in this area is almost impossible to see, and could pick your people off for hours with little rebuttal. However, if you have a wireless network air-dropped on the area, you could then tap into it. Due to synchronization, you could determine the origin of a gun shot by which nodes pick up the sound first. Then examine which nodes after the first incrementally detected the gunshot. Using this information you can then quickly assess the direction and distance the shot came from, allowing you to track down that sniper and protect your men.
Pursuer-Evader
Wireless networks can also be used in urban warfare. The ability to track down your enemies and expose their hiding places could cut years off of wars and save countless lives. This can be done by using wireless nodes to pick up the sounds or vibrations of footsteps, or the sound of someone breathing. Through network communication and a limited amount of mapping, you can have nodes track people or things.
Hardware
The typical sensor node used in a wireless network is a mica mote. A mote is another name for a sensor node. Mica motes generally run a four megahertz eight big microprocessor. They have a radio capable of transmitting at 40 Kbps. Typical data packets are designed to be 48 bytes each. And the motes are normally limited by the OS to only broadcast a maximum of 10 of these 48 byte packets per minute. This is mainly due to the massive power consumption of radio usage. Broadcasting 1 bit of data costs around a thousand CPU cycles worth of energy. As for memory, the mica motes have around 128 Kbytes of flash storage capacity, and 1.8 to 4 Kbytes of memory. Every mote generally has a 32 KHz external clock which can keep time to within the 1 millisecond to microsecond range.
Wireless Routing
Wireless sensor networks have to be able to handle multi-hop communication. This allows nodes to communicate through each other across vast networks to a base node used to gather the information from the network. There are 3 major methods of multi-hop communication used in wireless networks.
Tree
In tree collection, nodes all go and determine their distance from the root of the network tree. They then go and find a parent node that is 1 hop closer to the root of the tree then they are. This creates a large branching network of parents/root and leaves.
Intra-network
Intra-network communication is basically how the internet works. The wireless nodes go and discover their neighbors. They then make routing tables which they use to send data around, and work around problems the same way a router on the internet would. However, this can cause problems as nodes run out of power, and interference sets in on the network. Interference could potentially cause a network to have to totally re-map itself.
Dissemination
Dissemination is basically mass data propagation to the entire network. There are two major methods of dissemination.
Broadcast Dissemination
In broadcast dissemination, every node broadcasts the data once, immediately after they receive that data. This method floods the entire network, is prone to data collisions, and wastes a lot of power broadcasting a message which might not need to be broadcasted by every node.
Epidemic Dissemination
In epidemic dissemination, data is only sent when needed. Nodes will snoop in on the broadcasts of other nodes to see how old the data being sent is, and if it’s newer than what it has. If a node detects data that is older than its own data is being broadcast, it will broadcast an update to the node sending the outdated data. If newer data is detected, it will simply download it. And if a node goes long enough without an update, it will ask its neighbors if they have any new data.
Scheduling and Synchronization
Scheduling and synchronization are some of the most important aspects of a wireless network. If managed effectively, scheduling and synchronization can multiply a nodes lifetime and efficiency by fifty. Synchronization is used to make sure that nodes talk and listen at the same time. If a node were to be powered down ninety eight percent of the time, and it’s not synchronized with the other nodes around it, there is about a two percent chance of that node being able to talk with the rest of the network. This would effectively disconnect a node from the network and make it useless. Scheduling allows a node to only power-up and work a small fraction of the time and still be effective. A node might be on a schedule pattern to take environmental samples every two hours, broadcast once every six hours, and listen once every 60 minutes for 30 seconds. This kind of tight scheduling allows a group of nodes to use very little power and still be productive. Minor synchronization problems can be solved by broadcasting a time stamp with all messages. That way the child nodes can synchronize with their parent nodes and the whole network will stay relatively synchronized to within a few microseconds.
nesC
TinyOS is written in a language called nesC. nesC is a stripped down extension of C, designed specifically for the development of wireless network operating systems. It’s so bare that TinyOS’s core functions take up only 400 bytes of code and data memory combined. It’s a static language with no dynamic memory allocation. This means that the call-graph is fully known at compile time, and all resources are accounted for. Additionally, nesC has no function pointers; everything is passed directly in this language. nesC incorporates event-driven execution, a flexible concurrency model, and a component oriented application design, which will be talked about more later.
Event-driven Execution
Event-driven execution is basically another way of saying that it supports interrupts. This allows nodes to handle important things like incoming messages, and events worthy of data recording instead of doing whatever lower priority busywork the node was planning on doing.
Flexible Concurrency Model
Having a flexible concurrency model allows TinyOS to prevent resource conflicts from I/O devices, and software processes which want to use the same information at the same time. It is normally handled by executing the first process to request the resources, while scheduling the next process for after the current process is finished. There are two types of concurrency.
Task-based Concurrency
Tasks run to completion and do not pre-empt or interrupt each other. They are the normal scheduled activities.
Event-based Concurrency
Events are also run to completion, but can pre-empt or interrupt tasks or other events.
Component Oriented Application Design
Component oriented application design is done by writing applications to use only the components they need, cutting out all the useless fat and shrinking the code. TinyOS also supports split-phase operations. There is no event blocking like in a normal operating system. Instead, long-latency operations are split phase and signal their completion with events. This is very similar to DMA or direct memory access in a normal operating system. The processor is only involved in the very beginning and very end of a process. And if a new request appears that would require resources that are already being used, TinyOS will deny the new request, and schedule it to process after the current one is finished.
Flexible Power Scheduling
Flexible power scheduling in sensor networks is needed for a number of reasons. The main reason is that idle listening is a large power drain on nodes, so they must turn off to conserve energy. Flexible power scheduling is a method of providing local communication scheduling for a multi-hope sensor network. It relies on locally acquired info, using tree based topology and a flexible communication schedule to route packets through a network. Slotted time division schedules are energy efficient because idle and non-idle radio time can be predicted. This allows the creation of global schedules to prevent collisions and allow rapid propagation across a network. And if nothing is scheduled to be sent or received the nodes will shut down. An unfortunate side effect of flexible power scheduling is that nodes closer to the base or root of the tree have to spend a lot more power and time on communication. This is a result of the tree based model. As messages propagate towards the root of the tree you get fewer and fewer nodes transferring the messages from many more branches and leaves. This leads to the nodes towards the root running out of power far quicker than the further out branches.
Nodes States
Flexible power scheduling supports several node states which describe their general state of operation. The first is the sending state. It is when the radio is working and sending data to other nodes. The second is the receiving state. During this state the node is listening for data from other nodes. The third is the advertisement state. During the advertisement state nodes transmit their available reservation slots to other nodes, so the neighbor nodes can schedule a communication with the parent node. The fourth is the transmit pending state. In this state child nodes send reservation requests to parent nodes in an attempt to reserve one of their open reservation slots. The fifth is the receive pending state. In this state the parent node has received a reservation request from a child, and is waiting to receive a transfer from that child. The sixth and final state in flexible power scheduling is the idle state. During this state the node powers down, turning off its radio entirely and going into a sleep mode.
Effects of Flexible Power Scheduling
To give an idea of the increase in efficiency given by power management, a high efficiency AA battery gives about 221 hours or 9 days of operation time to a node with no power management. The same node with power management can work for approximately 1274 hours or 53 days on average.
Trickle
Trickle is a propagation algorithm for code and maintenance delivery in a wireless sensor network. Trickle supports a type of communication referred to as “Polite Gossip” where a node periodically broadcasts a summary of its code to its neighbors.
Polite Gossip
If a node has recently heard a neighbor broadcast a summary that is identical to its own, that node will stay quiet. If it hears a neighbor broadcast an older code summary than the code the node currently has, that node will spring into action and broadcast an update to the out-of-date node. And if a node hears a code summary that is newer than its own, its will request that node to send the newer code. And if a node is disconnected from the network for a few days then regains connection, its neighbors can bring it up to date with trickle. This is in contrast to traditional sensor networks where the only way to bring a lost node up to date is to resend the update to the entire network. This burns the battery life on all the nodes that already have the update.