On the other hand, multithreading is extremely useful in reactive programming, where it allows the programmer to separate concerns and increase the responsiveness of the program, which is able to effectively handle multiple events at the same time.

While listening to reports on various WSN experiments carried out with motes programmed under TinyOS I have heard (with a nauseating consistency) about two types of problems:

1. Difficulty of implementing certain types of simultaneous activities. A typical example was a complaint that a sensor measurement was disrupted by packet transmissions, because it was impossible to carry it out while an outgoing packet was being processed by the RF module.

2. Stack overrun errors resulting from too many interrupt service routines stacked up at the same time.

The two problems are in a sense complementary. Non-trivial (multimodal and state-driven) activities are best implemented as threads. With the shortage thereof, one can resort to interrupt service routines as a substitute. However, multiple, asynchronous interrupt service routines permitted to interrupt each other make it very difficult to estimate the maximum stack size.  Moreover, they lead to situations where the typical (average) demand for stack space may be quite modest, while the maximum (possibly reachable on extremely rare occasions) is truly large and may be difficult to pre-compute.

Indeed, multithreading is all about the stack space. A traditional scheme of implementing multiple threads assigns to every thread a separate stack, which is supposed to cater to the thread’s maximum need determined by the maximum reachable depth of function calls and their demands for automatic (local) variables. When the thread is preempted (by an interrupt service routine or by another thread), its stack preserves the thread’s context allowing it to later continue as if nothing happened. Even if the stack size per thread is drastically limited, it still remains the most significant component of the total amount of memory resources needed to describe and sustain a single thread. With 1 or 2KB of RAM available on a small microcontroller, this problem makes it very difficult to implement classical multithreading involving any non-trivial number of threads.

One should also keep in mind that the stack space is practically wasted from the viewpoint of the application: it is merely a working storage needed to build the high-level structure of the program, and it steals the scarce resource from where it is truly needed, i.e., for building the proper (global) data structures.

Somewhat paradoxically, large systems can cope with the stack problem much better, not only because of the abundance of memory, but also owing to the standard memory mapping techniques that virtualize the stacks and prevent memory fragmentation.  On a microcontroller, you are basically stuck: once you decide that a thread may ever need so much stack memory, you have to cut a rigid chunk just for its own use.

So what are the options? The obvious one (and the one de facto adopted in TinyOS) is to give up multithreading.  Within the model of a single thread supported by interrupt service routines, everything happens on a single, global stack. This is possible, because the (single) thread can only be preempted by interrupt service routines and their preemption/resumption regime is precisely single-stack-oriented. While the interrupt service routines can assume some aspects of threads, that mentioned regime makes it difficult to implement in them many functions that rightfully belong to threads, like waiting for some complex conditions expected to materialize in response to some complex actions. In particular, the inherent lack of a mechanism whereby an interrupt-service routine can wait for memory (which may become temporarily absent) seems to be the primary excuse for the rigid (static) memory allocation model in TinyOS.

Had such a model been adopted in PicOS, it would have killed the essence of our holistic approach to networking (e.g., dynamic buffers are pivotal to VNETI).

But there is another option: to redefine thread preemption. PicOS follows this avenue and adopts a non-classical flavor of multithreading, which allows all threads to share the same global stack. A PicOS thread looks like a finite state machine (FSM) that changes its states in response to events. The CPU is multiplexed among the multiple threads, but only at state boundaries. This simplifies (to the point of practically eliminating them) all synchronization problems within the application, while still providing a reasonable degree of concurrency and responsiveness. By enforcing the FSM appearance of a thread, PicOS stimulates its clarity and self-documentation, which is especially useful and natural in reactive applications, i.e., ones that are not CPU bound, but perform finely-grained operations in response to possibly complicated configurations of (asynchronous) events.

A somewhat similar approach has been taken in Contiki (but we were there first). While the basic premise is essentially the same: to give up the stack as a means of preserving a thread’s context, Contiki (quite unnecessarily in my opinion) abhors the idea of FSM as a way to describe what a thread might do when resumed. They put the cart in front of the horse by complaining upfront about the unnatural “look” of an FSM programmed within the confines of a single traditional thread (see this presentation, e.g., slide 14), which argument I find hard to buy even in that grossly unfair (to FSM) context, and then proceed to advocate their thread model failing to notice that its basic premise throws a completely different light on their original criticism (the unnecessarily ugly FSM would look quite different in that new model).  Especially within the domain of reactive applications (of the kind typically found in WSNs) the FSM paradigm is very natural and powerful.

Within Contiki, multiple alternative paths of execution triggered by different events must be always taken care of by different threads (which then must synchronize somehow), while in our case a logically unified set of actions can be conveniently taken care of by a single FSM-like thread. Our experience strongly supports the FSM model of PicOS threads, which we would find difficult to live without.

To sum up, PicOS offers an extremely convenient and memory-frugal multithreading environment for programming reactive systems, whose efficiency and expressing power are practically unmatched by the competition. Even with 256 bytes of RAM (the absolutely lowest end of microcontrollers that one may ever consider for WSN), you can run a few threads implementing a non-trivial networked application (with dynamic memory allocation!). The single shared stack can be quite short (e.g., 48 bytes will go a long way), because interrupt service routines need not be interruptible (their role is to quickly handle an event and turn it into a waking condition for a thread). Consequently, the single-at-a-time thread frame on the stack can only be augmented by at most one extra frame belonging to no more than one interrupt service routine.

Within the broad retirement community category, there are two types of residences known as Independent Living and Assisted Living which each offer a range of care and services. While Independent Living programs offer a supportive environment, Assisted Living programs offer additional nursing care for those who may require more assistance or supervision in a controlled and supportive environment.

The challenge to a successful independent or assisted living community is to provide the level of support and service required by the residents, when and where they need it, while providing the services without crossing the line into Dependent Living.

The corporations that provide these services and manage the communities and facilities must provide safety and security to the residents and this is usually done through standard security practices – security guards, monitoring of entries/exits, fire protection, availability of health practitioners are some examples.

The requirement put forward by one such Independent Living Community in New Jersey was simple and straightforward and the direct result of unfortunate circumstances.   The question was put to ComIP, a division of Combat Networks……

“We have a number of safety policies and procedures for our residents to allow them to be independent but in the case of an emergency they have a way to engage Health and Security Personnel if needed. The first system requires a resident to dial an extension every morning as a primary method of notification that everything is ok – proactively letting the Health and Security know that at that particular moment in time, everything is in fact fine.  The second method, and one of the most widely deployed assisted and independent living security policies is to equip each home or the residents themselves with a panic button that transmits a one way signal to the security office to alert personnel to a potential problem.   Even with these policies in place, we are still faced with the unfortunate scenario of a resident requiring assistance without the ability to reach the phone or the panic button.  Can ComIP use Ad Hoc Sensor Networks to provide a replacement/alternative technology to reduce or eliminate the possibility that  a resident becomes immobilized, while maintaining an independent living environment.”

Obviously the phone-in system was fraught with problems.  Frankly, it’s a pain to call every day and that translated directly to low resident usage of the system, it wasn’t capable of alerting security when there was a problem (only when there wasn’t, which is most of the time), and because so few residents used the procedure, there is no way of knowing if there is a problem or not.  The panic button is also a very onerous security practice on behalf of the residents.  First residents needed to keep a pendent on their person (hardly independent living –  very much tethered) and if it wasn’t kept close by all the time and an accident occurred can you remember or get to where you last left it.

ComIP’s core technology held promise as a method of creating a wireless sensor network throughout the community to transmit sensor data collected (light, motion) from individual residences and display the information to the security office in the administration building.  One of the key benefits of the implementation was that it didn’t require the residents to do anything.  It is a completely passive solution.  With the addition of management software, ComIP was able to reliably collect the sensor data, present it to the Security Office through an analysis of the data received.

Real-time wireless sensor network data are presented within the framework of an interactive graphical user interface as shown below. Security officials or health professionals can observe the data and are notified when alarm conditions are present.

Additionally, the data collected can be analyzed to create a truly adaptive system. From the sample figures below (click to enlarge) we can observe a person’s behaviour and analyze trends allowing the system to adapt to changes over time. In this particular example, we can observe from the average daily motion that they typically rise for the day between 7am and 8am. The system can also determine which areas of their living space are most frequented.

a) Average Daily Motion and Light Values	b) Daily Percentage Motion

The solution is designed to overcome two of the fundamental issues with current mesh networking technology:

1. That of large memory (RAM) requirements and consequently high product cost and power requirements;
2. The inefficient and difficult connection discovery and maintenance options (routing) which render true ad hoc networking cumbersome, and difficult to deploy in large, changing networks where nodes may appear, disappear or change locations.

What ComIP has developed and markets is a solution that is designed for extremely low power consumption, low memory and processor requirements and uses a layerless, auto-scalable, ad-hoc forwarding (routing) scheme enabling large and very large wireless mesh networks.

We have built and tested diverse applications based on the technology but for developers we can also provide authoritative product development and testing without the need for hardware deployment, allowing for truly rapid application development.

This integrated solution allows developers to focus on value added application development and not worry about the intricacies of wireless mesh networking.

In our next blog post, we will introduce TARP…our Tiny Ad-Hoc Routing Protocol – the new defacto standard and key building block of the next generation of wireless ad hoc network applications.

The goal of the NSERC DIVA network is to:

• Develop innovative large-scale communication architecture and wireless network technologies;
• Make Canada’s transportation systems in urban, rural and highway environments more efficient, safer as well as offering revolutionary services;
• Develop Technology for Intelligent Transport Systems (ITS).

ComIP in collaboration with our partner Olsonet Communications share a similar vision that parallels the research objectives of the DIVA Strategic Network. The companies share ideas and facilitate the transition of their intellectual property to the market, as well as increase the industrial reach of wireless ad hoc, sensor and vehicular networks. Within the framework of this partnership, ComIP develops custom networking solutions for wireless sensing, monitoring, location tracking, and social networking. They envision this technology to be an important building block in the creation of the next generation of intelligent vehicular ad hoc networks with multimedia capabilities.

ComIP is looking forward to its active participation in the cutting edge research to be undertaken in the DIVA strategic network, and is particularly interested in its demands for secure, efficient and effective solutions to wireless communication and vehicular networking problems posed by the complexities of vehicular mobility patterns and the inherently unreliable nature of the wireless medium.

Visit the NSERC DIVA Network website over here:  http://www.nsercdiva.com