TinyLIME

TinyLIME in a Nutshell

Operational Setting

Most sensor network middleware operate in a setting where the sensors are fixed in the environment and report their values to a centralized point. Much work has gone into making these operations power efficient. However, this centralized model may not be ideal for all applications. Consider an application that requires information from sensors in close proximity to the user. In this case, both the location of the user and the location of the sensors must be known, the data must be requested by the sensors determined as proximate, then the data must be shipped to the central collection point. This has a number of drawbacks. First, it may not be reasonable expect to know the location of all sensors. Second, the collection of information puts a communication burden on the sensors between the proximate sensors and the collection point to forward the data. Third, it requires that all sensors be transitively connected to the base station---something that may not be feasible in all environments due to physical barriers or economic restrictions.

Considering these issues, we propose an alternative, novel operational scenario; one that naturally provides contextual information, does not require multi-hop communication among sensors, and places reasonable computation and communication demands on the motes. The scenario, depicted in the Figure below, assumes that motes are distributed sparsely throughout a region, and need not be able to communicate with one another. The monitoring application is deployed on a set of mobile hosts, interconnected through ad hoc wireless links---e.g., 802.11 in our experiments. Some hosts are only clients, without direct access to sensors, such as the PDA in the figure below. The others are equipped with a sensor base station, which however enables access only to sensors within one hop, therefore naturally providing a contextual view of the sensor sub-system.

Model

As in Lime, the core abstraction of TinyLime is the one of a transiently shared tuple space, which in our case stores tuples containing the sensed data. However, TinyLime also introduces a new component besides agents and hosts---the motes. In the physical world defined by our setting, motes are scattered around and, depending on the connectivity determined by the mobility, each may be connected with one or more base stations. Dealing explicitly with this scenario, e.g., by considering a mote just like another host, would lead to a complicated model with an inefficient implementation. Instead, in TinyLime a simpler abstraction is provided. A mote is not visible through TinyLime unless it is connected to some base station. When this is the case, the mote is represented in the model much like any other agent residing on the base station host (and therefore ``connected'' to it), with its ITS containing the set of data provided by its sensors. Clearly, things are quite different in practice: the mote is not physically on the base station, and there is no ITS physically deployed on the mote. As usual, it is the middleware that takes care of creating this abstraction to simplify the programmer's task. The support for the abstraction is described in the next section.

Once this leap is made, the rest comes naturally. For instance, operations on the federated space now span not only connected hosts and agents, but also the motes within range of some host---similarly for operations restricted to a given host. Also, the mote identifier can be used to restrict the scope of a query or reaction to a specific mote, much like agent identifiers. To make a concrete example, consider the scenario above. When an agent on the laptop base station on the right issues a rd for light data, restricted in scope to its own host, a light reading from one of the two connected motes will be returned. If, instead, an agent running on the PDA client issues the same rd query but with unrestricted scope, a light reading from any of the five sensors connected to the two base stations will be returned non-deterministically. It should be noted, however, that although TinyLime agents use the basic Lime operations to access sensor data, this data is read-only, i.e., only reactions, rd, rdp and rdg are available. Indeed, sensors measure and report properties of the environment, which cannot be changed or removed by the clients, but only inspected.

Reactions work as in Lime, modulo the changes above, and are extremely useful in this environment. Imagine a situation where a single base station agent registers a reaction to display temperature values. As the base station moves across the region, the temperature from each mote that comes into range will be displayed---with no extra effort for the programmer. TinyLime reactions also provide additional expressive power. First, it can be specified how frequently the data received through a reaction should be refreshed. The notion of data freshness is a property of a sensor in the context of an application, and it reflects the fact that sensors measure environmental properties, and every reading has a time threshold beyond which it is considered no longer useful---or fresh. In our example, this is very useful when the base station remains in a single location for an extended period of time. Second, TinyLime reactions also accept a condition, e.g., to specify reaction only to temperatures between 20 and 30 degrees. This is motivated by the need to limit communication on motes, enabling data sending only if it is useful for the application. Both these features, together with details such as the format of sensor data tuples, are described in the next section.

Data Aggregation and Sensor Operation

TinyLime also features the possibility to gather collected and transform data, aggregating values to find more useful information. As an example, it is possible to query for the average temperature in a room. Such aggregation can be applied at two different levels: globally, over the values of multiple sensors, or locally, over the values sensed by a single sensor.

Aggregation over multiple sensors is easily achieved using the basic TinyLime operations. For instance, the rdg operation can be used to collect all tuples containing light sensor readings, which can then be aggregated using application logic encoded in the agent. In principle the same strategy can be used to aggregate over the values of a single sensor-collect raw values from a sensor using a rd and aggregate them on the base station - but this is inefficient in terms of communication bandwidth and therefore power consumption on the sensor nodes. Whenever possible, aggregation should be pushed close to the data, e.g., on the sensor nodes, trading computation for communication --- a desirable strategy for sensors, where communication is much more expensive than computation and sampling.

This feature is carried out in TinyLime by making two significant extensions above what has been presented thus far. First, there must be a way to request access to data by specifying both that an aggregate value should be returned, and which aggregating function should be applied. This is achieved by expanding the format for the templates and tuples involved in operations on the tuple space. Second, implementing aggregation on the sensor nodes requires a change of perspective. Thus far, we have assumed that sensors play a passive role, acquiring and communicating data only if and when needed, i.e., when the base station makes a request with a rd or reaction operation. Instead, aggregation requires active behavior from the sensors, specifically autonomously and periodically sampling data over which an aggregation can be computed. Nevertheless, while the continuous sampling implied by this form of aggregation is fundamental for some applications, it may be overkill for others, whose needs can be met by activating sampling only when a finer-grained analysis of a phenomenon is needed-or never at all. Therefore, TinyLime gives the programmer both options. A sensor can be preprogrammed to take samples at regular intervals throughout its lifetime. Alternately, it can start in passive mode, and the application programmer can explicitly activate sampling for a given number of epochs, after which the sensor automatically switches back into passive mode without additional communication.

Tuple templates

The following figure shows the tuple templates used by TinyLime clients. In Lime, and in general tuple space models, the format of tuple templates is left to the application. However, in TinyLime four tuple templates are predefined to access different types of sensor data.

A tuple (or template) for a regular sensor reading consists of four fields. The first field indicates the type of sensor to be queried. In our mote-specific implementation, valid values are ACCELX, ACCELY, HUMIDITY, LIGHT, MAGNOMETER, MICROPHONE, RADIOSTRENGTH, TEMPERATURE, and VOLTAGE. The second field contains the actual sensor reading. The third field is the epoch number at the mote when the reading was taken, allowing temporal comparison of readings from the same mote. The last field represents information provided by the base station when the sensor value is collected. The details are left to the programmer who provides a class that decorates BaseStationInfo. In our tests we use the timestamp of the base station to approximate when the value was read. Alternatives include recording base station information such as location, remaining battery power, or the signal-to-noise ratio for communication with the mote that provided the reading.

Following this format, a client can create a MoteLimeTemplate for use in any of the allowed operations. The constructors optionally allow setting a freshness value and an operation scope. The latter allows spanning the federated tuple space, all agents or motes on a host, a single agent, or a single mote.

Tuples for retrieving aggregate information require the client to specify aggregation parameters. As before, the first field of the tuple identifies the sensor type to be aggregated. The next field uses the IAggregationOptions interface to specify the aggregation function and the interval over which to perform the aggregation. Our implementation provides AVERAGE, MAXIMUM, MINIMUM, and VARIANCE, but this can be expanded by the programmer by implementing both the IAggregationOptions interface and the mote-side code to perform the function. The start and end epochs for aggregation are expressed relative to the current epoch. For example, a range of (10, 5) aggregates values from 10 epochs ago until 5 epochs ago. The next integer in the template is the sensor reading. The following two integers represent the actual epoch interval the aggregation was executed over. They should be left formal in the template, but will be bound to the absolute epoch values from the mote that did the aggregation. The final field of the aggregate data template is the BaseStationInfo, which is the same as in other templates.

Reactions are supported by extending the regular data and aggregate templates with a condition field allowing the template to be bound to a data tuple using a match function other than the typical equality function provided by Lime and Linda-based models. In the current implementation, inequality (e.g., voltage different from 2.1V) and matching over a value range (e.g., temperature between 20 and 30 degrees) are available.

Architecture

The TinyLime model has been designed and implemented for the Crossbow Mote platform, exploiting the functionalities of TinyOS. We can identify three main components in TinyLime:

Lime integration

On standard hosts, TinyLime is implemented as a layer on top of Lime without requiring any modification to it, therefore reasserting the versatility of the Lime model and middleware. On the base stations, i.e. the laptops with the motes connected to them in the scenario image above, besides the TinyLime package there is the moteaccess package, that provides an interface that allows connection to the base station - and therefore to the motes in the adjaciencies. Indeeed, the moteaccess package is independent of the TinyLime that resides above, thus providing a Java based access to the sensor network for setting and querying it.

In the figure above, the client agent in the upper left part is the actual user of TinyLime. The client instantiates a MoteLimeTupleSpace, which offers the usual Lime operations but performed on the sensor network. Transparent to the user, two LimeTupleSpaces are created: one that actually shares the sensor-readings tuples, and the other that is used for configuration tuples, that is tuples used by the TinyLime system to exchange configuration information or to perform direct requests to the agent that resides on the host with the base station (e.g. for an explicit light request).

The right part of the image shows the MoteAgent, another agent that resides on the host which has direct connection to the motes. This agent takes care of serving the requests coming from the other agents, querying the sensor network when needed and removing the tuples when they are no longer fresh. As outlined above, TinyLime handles data freshness, basically indicating how long a sensor reading can be considered valid. The user can indicate a desired freshness f in the query, which may differ from the default freshness for the requested sensor. In such a case, if a tuple is present in the data tuple space and it was sensed less than f time units ago, then the tuple is returned to the client, without querying the sensor netowrk. Otherwise, an explicit request is made to the motes.

MoteAccess

The MoteAccess module offers primitives to access the sensor network. It takes care of accessing the hardware to query the sensors, and offers an interface (IMoteAccess) that is generic enough to make the module usable even in a context other than Lime (although its functionality was at first designed to easily allow such use).

The operations offered by the IMoteAccess interface are:

Read and reaction serve for both normal and aggregate values.

The MoteAccess module interacts asynchronously: the user declares interest in some kind of data and provides a listener (i.e. an implementation of the IMoteListener interface) to be notified of incoming matching readings. Moreover, the MoteAccess subsystem offers a GUI allows which requests are running at any time. It is most useful for debugging purposes.

The mote-level subsystem

The design of the mote level subsystem is dominated by the need to save as much power as possible in the deployed motes. This leads to the choice of duty cycling the motes, making them sleep for most of the time. When sleeping, a mote turns off its radio device: this saves a lot of power, but obviously creates problems when we need to deliver it data.

The approach we follow is based on the assumption that the Base Station has fewer power constraints than the deployed motes. This is reasonable, since even if a base station is battery powered, its batteries are typically much more powerful than those on the deployed motes. More importantly, a deployed mote will need to live off its batteries for years, without the opportunity to recharge them. Research focused on using solar panels and other energy sources to power the motes will probably make this problem less prominent, however a deployed mote's battery power is a precious resource.

Therefore, when a base station needs to deliver a packet to a mote (or to all motes in-range), it repeatedly sends (or broadcasts) the data. When a mote enters its awake phase it will receive the packet. The figure below describes this.

The epoch period, a fixed network parameter, can be used to limit the maximum time a packet needs to be repeated over the channel. The nominal awake time, on the contrary, helps determine the best rate for packets to be sent.

Motes accept two types of packets: immediate request and reaction request. Immediate requests simply ask for a single sensor reading: the mote turns on the requested sensor, performs the reading, then forges a reply packet and sends it back to the originating base station. On the contrary, reaction requests return a sensor reading to the base station once per epoch.

Base station to mote interaction is strictly one-hop: this allows for quick operations and also copes well with dynamic situations without requiring any overhead or infrastructure. Moreover, base stations are considered mobile, and no assumptions are made w.r.t. connectivity between a BS and the deployed motes.

Other activities. Motes also accept configuration requests allowing a client to tune mote behavior.

A quick peek at the mote software

The figure above shows the main structure of the mote software: the nesC implementation closely mirrors this organization. Nesc allows and encourages modularization, and our implementation takes advantage of its features.

TinyLIME