TeenyLime in a Nutshell
TeenyLime targets a scenario in which all sensor network components participate in the computation without relying on an external base station. Applications exhibiting such behavior include those where actuators collect information from neighboring sensors and perform some action based on the value returned.
This need for coordination among peer devices mimics the coordination supported by Lime, thus it is natural to adopt the transiently shared tuple space as the core abstraction of TeenyLime. The coordination operations in TeenyLime are essentially those of Lime, including operations to insert, read, remove, and react-to tuples. TeenyLime tuple spaces are physically located on the devices themselves but unlike Lime they are shared only with one-hop neighbors. Because each device has a different set of one-hop neighbors, the shared tuple space view is different for each device. This is fundamentally in contrast to Lime in which the view of the transiently shared tuple space is composed of the tuple spaces of all connected hosts, and connectivity is assumed transitive. In general, limiting the scope of operations to one hop is natural for many WSN applications that need access to nearby information. For example, a fire extinguisher can make a local decision to activate based only on readings from several sensors in its vicinity, and inform other nearby extinguishers after it activates. Activation can be effected by installing a reaction on neighboring sensors for temperature readings. When sufficiently many high readings are received, the extinguisher should be activated. Notification to the other extinguishers in the area can be handled by outputting a "notification" tuple to their tuple space. The information about which devices are currently directly reachable is stored in a special tuple space called TeenyLime system, providing a single unified abstraction for representing both the application and system context. This is similar to the LimeSystem tuple space of Lime that reports which hosts are currently sharing tuple spaces, although the TeenyLime system supports weaker semantics.
TeenyLIME API
TeenyLime is written in nesC on top of TinyOS. A dedicated nesC interface (illustrated
next) is used (in the TinyOS sense) by the application to
access the transiently shared tuple space composed of the local tuple
space and that of the one-hop neighbors. Each nesC command requires
a target, a specification of the tuple space repositories in
the federation over which the operation should execute. Possible
values restrict the scope of the operation to the local tuple space
(indicated with TOS_LOCAL_ADDRESS), the tuple space
hosted by a specific one-hop neighbor (indicated with the address of
the device), the union of all tuple spaces hosted by one-hop neighbors
(TOS_BCAST_ADDR).
TupleSpace.nc
interface TupleSpace { // Standard operations command TLOpId_t out(bool reliable, TLTarget_t t, tuple *t); command TLOpId_t rd(bool reliable, TLTarget_t t, tuple *templ); command TLOpId_t in(bool reliable, TLTarget_t t, tuple *templ); // Reliable group operations command TLOpId_t rdg(bool reliable,TLTarget_t t, tuple *templ); command TLOpId_t ing(bool reliable, TLTarget_t t, tuple *templ); // Managing reactions command TLOpId_t addReaction(bool reliable, TLTarget_t t, tuple *templ); command TLOpId_t removeReaction(TLOpId_t operationId); // Request to reify a capability tuple event result_t reifyCapabilityTuple(tuple* ct); // Returning tuples event result_t tupleReady(TLOpId_t operationId, tuple *t, uint8_t n); }
Concurrency
In TeenyLIME, all read operations are split-phase: first the
operation is issued, then the tupleReady event is signaled
when the operation completes. The return parameter for each operation
is an identifier, or a special constant (TL_OP_FAIL) in
case of error. The identifier and the data tuple(s) form the contents
of the tupleReady event, allowing the application to
associate the data with its earlier request. If multiple tuples are
returned, the n parameter indicates how many.
Analogously, two asynchronous commands are offered to install or
remove reactions, taking a pattern as the parameter. When matching
data is present, the tupleReady event is signaled, returning
the tuple that triggered the reaction along with the corresponding
operation identifier.
Reliable Read/Write Operations
Typical WSN applications that focus on collecting sensor data are inherently state-less, as the core task is that of communicating sensor readings to a given collection point. Conversely, applications composed of tasks that affect the environment often require stateful coordination mechanisms, e.g., using current conditions (state) to act collaboratively. This poses more stringent requirements on the consistency of state, and consequently on the reliability of operations on the tuple space. To address both scenarios, the commands to perform read or write operations can be issued as either unreliable or reliable, using a flag. The former operations do not provide any guarantee on their successful completion, thus yielding a lightweight form of communication that is suited for state-less applications. Instead, reliable operations offer stronger guarantees at the price of higher resource consumption, allowing them to be used for coordination purposes, e.g., to implement control loops based on the representation of the current state of the environment.
Freshness
Sensor data is inherently time sensitive, a dimension that is even
more important when actions must be taken based on the values
themselves. For instance, a temperature reading might require
different responses depending on how long ago it was gathered. To
address time in general, TeenyLime divides time into epochs of
constant length, and timestamps every outputted tuple with the current
epoch value. Two helper functions are offered to the application
developers (defined in TupleSpace.h):
setFreshness(pattern,freshness) and
getFreshness(tuple). The first customizes a pattern to impose
the additional constraint to match tuples no more than
freshness epochs old (if a pattern does not specify
freshness, it matches any tuple regardless of its
timestamp). Conversely, getFreshness(tuple) returns the
number of epochs that elapsed since the tuple was created. An additional
setExpireIn(tuple,epochs) function is also provided to
set an expiration time for the tuple once output to the tuple space.
Range Matching
While the standard matching semantics of Lime suffice for basic coordination, some WSN applications require additional expressive power. For example, a fire extinguisher application only needs to obtain temperature readings above a safety threshold. However, using the standard matching semantics based on exact values, we must issue a reaction over the neighborhood with a pattern matching any temperature reading and filter the results when they arrive. This causes unnecessary communication when data is discarded upon arrival, therefore TeenyLime extends patterns to support range matching. For example, the reaction can be issued stating that the field representing the temperature value must be greater than a given value.
The following fragment of code illustrates how this is achieved
with TeenyLime. In addition to the usual formal and actual tuple
fields, patterns can also contain customized fields whose matching
semantics account for (bounded or unbounded) intervals. The following
code specifies that a tuple matches the pattern when the first field
is equal to the constant TEMPERATURE, and the second
field is an integer value above 30.
tuple t; TLOpId_t reactionId;
void addTemperatureReaction() {
t = newTuple(2, // The fields of this pattern
actualField_uint8_t(TEMPERATURE),
greaterField(TYPE_UINT16_T, 30);
reactionId = call TupleSpace.addReaction(
FALSE, TL_NEIGHBORHOOD, &t);
if (reactionId == TL_OP_FAIL)
dbg(DBG_ERR, "addReaction operation failed");
else
pendingReact[pendingReactLength++] = reactionId;
}
This mechanism is easily extensible because the matching semantics is decoupled w.r.t. distribution mechanisms. A developer needing alternate matching semantics must only define two functions: one creating a customized field for patterns, and one defining the conditions for an actual value to match the customized field.
Capability Tuples
Consider a small modification of the aforementioned scenario, namely a
device needing to read a single temperature value from a nearby
device. For the pattern to find a match, at least one tuple must be
present in the tuple space of the neighboring nodes at the time the
rd(p) operation is issued. Therefore, because a device
cannot predict when a rd(p) operation will be issued, any
sensor that can produce a temperature reading is forced to
periodically take fresh readings, and proactively output the values in
the local tuple space even if no device is currently interested in
them. This clearly constitutes a waste of resources.
To manage this problem, TeenyLime developers are given the ability
to output capability tuples, as outlined in the next code example,
indicating that a device has the capability to produce data of a given
pattern. From the point of the view of the application performing a
query nothing changes: a matching tuple containing a temperature value
is returned by raising a tupleReady event. Behind the
scenes, however, the processing occurring at the device hosting the
capability tuple is different from the normal one. A capability tuple
enjoys the same matching semantics as a normal tuple, but is not
returned directly as a result. Instead, it essentially works as a
placeholder for the real data. A positive match triggers the event
reifyCapabilityTuple, which reports the matched capability
tuple to the application running on the device hosting it. The
application can then perform the operation associated with it (e.g.,
reading the current temperature), build a tuple on the fly, and output
it to the tuple space. TeenyLime takes care of returning the tuple to the
querying node as the result of the read operation.
tuple t; TLOpId_t outOpId;
void outputCapabilityTemp() {
t = newCapabilityTuple(2, // The fields of this tuple
actualField_uint8_t(TEMPERATURE),
formalField(TYPE_UINT16_T));
outOpId = call TupleSpace.out(FALSE, TL_LOCAL, &t);
if (outOpId == OP_FAIL)
dbg(DBG_ERR, "?out? operation failed");
}
Our original concept for capability tuples was to act as
placeholders for real data, providing a mechanism to reduce the number
of sensor readings to those strictly needed to answer
queries. However, the concept naturally generalizes yielding a
powerful abstraction. Consider that with a capability tuple a device
triggers the execution of a set of operations on a neighboring
device merely by issuing a query matching the pattern of the
capability tuple. This set of operations can be more general than
simply taking a sensor reading. For example, a programmer could define
a capability tuple representing its ability to average some sensor
readings taken over a given time period. When a rd(p)
operation is issued with a pattern matching this average
capability tuple, the corresponding function is triggered and the
result returned. Additionally, actual values in the pattern can be
used as parameters, further customizing execution, e.g., to specify
the desired time period in this example.
To exploit this general capability function feature, the developer
simply defines a suitable capability tuple and the function to be
called when the corresponding reifyCapabilityTuple event
is raised. The result of the function is placed in a tuple, stored in
the tuple space, and returned to the calling device.
TeenyLIME System
As previously mentioned, the system context is represented and
accessible in TeenyLime in the same way as application data, i.e., as
tuples. In particular, TeenyLime automatically provides access to the
current neighbor set by storing a NeighborTuple for each device
in range. The content of this tuple is defined by the application
developer, allowing customization to include information such as the
current location and/or the remaining energy. To keep the information
up to date, the system periodically signals a
reifyNeighborTuple event trough
the TeenyLIMESystem interface, which the application
should handle by returning a pointer to a new version of its
NeighborTuple. If the event is ignored, TeenyLime keeps the
previous tuple.