In this section we build a sample collection application, very similar to the Surge program in TinyOS, except that in this application nodes will send only a sequence number, which is incremented in every packet.
We begin my moving into the snlog/collection directory, and creating a new file called sampleCollection.snl.
In order to create a DSN application, the algorithm or logic must be flushed out, as this greatly facilitates the
implementation process. As a result, we begin by writing the pseudo code for our application:
1. A routing tree must be formed, with a single destination, and each node maintains a parent to which it can forward packets to the route through.
2. Each node, except for the destination, creates messages periodically, each time incrementing the sequence number in the packet.
3. Upon creation of a packet, the node forwards it to the destination by sending it to its next hop.
4. If a node receives a packet, one of two things can happen:
4a. If it is the destination, then it must store the packet.
4b. If it is not the destination, it must forward the packet onto the next hop in its route to the destination
For the sake of this example, our focus is on the collection aspect, so for now we will use an existing implementation
of the tree formation and management protocol. We will actually implement our own version in the next section.
The existing implementation of tree routing resides in tree/tree-lqi.snl (assuming the base directory
is that which was set by DSNPATH. Using library modules such as this is nearly equivalent to the use of the
#include statement in C. Therefore, we begin our program with the following command:
! import ('tree/tree-lqi.snl').
For the moment, we won't concern ourselves with the contents of this file, except to note the following:
1. The protocol expects the user to specify the eventual destination of all packets (on a per node basis) using the following predicate: dest(@Source, Dest) 2. The protocol exports the following predicate for use by higher-layer applications: nextHop(@Source, Destination, Parent, Cost) In essence this predicate implies that node Source can send a packet to node Destination by using node Parent as the next hop, with the cost metric specified by Cost 3. Finally, Timer #2 specifies how often routing beacons are sent by each node.
In order to satisfy requirement number one, we assume that the TOS_LOCAL_ADDR of our base station is 0, and so at every node we must specify the destination as such:
dest(@1,0).
dest(@2,0).
...
dest(@35,0).
...
However, such an approach is not only cumbersome, but also impractical because it requires one to know exactly how many nodes will be in my deployment, and what their local addresses are. Furthermore, if these change, one would have to modify the program accordingly. Instead, DSN allows the user to use the '*' operator to specify all locations. Consequently, all that code can be rewritten using a single fact:
dest(@*,0).
One last problem remains with such an approach: In some cases, one might want to specify an exception. For example, I might not want such a fact to be specified at the destination itself, as it might disrupt the logic of my program. In those cases, users can use the following construct:
dest(@X,0) X != 0.
Using this approach, the fact will be instantiated at all nodes except for 0, our base station. (For our program, use the '*' version because we will want the destination node to know it is the destination.)
The next aspect is to utilize the nextHop predicate provided by the tree library module, and we will do this when implementing the second step of the pseudo code, which was generating messages periodically.
We can rephrase the pseudo code in the following way. Generating a message to send, with a specified sequence number
X is equivalent to having a predicate, such as toTransmit(@Src,Count), where a tuple of the form
toTransmit(@Local,X) will be inserted in the table to represent that we have a message to send.
Okay, now that we've decided to use this predicate, we have to tell DSN what it is before using it, much like one must declare a variable in other programming languages. We do this using the typedef statement:
! typedef(toTransmit, uint16_t, uint16_t).
This statement effectively says that we are creating a user-defined predicate named toTransmit which will have two parameters, both 16-bit unsigned integers. By convention, all declarations, and other configuration options (denoted by the preceding '!') reside at the beginning of an Snlog file, before any rules or facts.
As we mentioned, each predicate is in essence a table in a database. Although future work includes the implementation of a dynamic memory manager, TinyOS's static allocation scheme currently mandates space for each predicate table to be allocated at compile-time. By default, DSN sets the size of each table to be 10 rows. However, there are certain cases where the number of necessary rows is clear at compile-time, and so can be specified in order to reduce wasted space. DSN provides the materialize mechanism to provide this and other features. For our program, we use the following command:
! materialize(toTransmit,infinite,1,evict_random).
The first parameter indicates the predicate being configured. The next parameter indicates the length of time in milliseconds a tuple remains in the table before it expires, with the infinite option indicating no expiry. The third parameter specifies the size of the table in terms of number of tuples, and the final parameter is the eviction policy. Current options for this are evict_random and evict_deny with evict_random as default. We only need one row for our table because at any given time each node will only have one message to send to the destination.
The predicates dest and nextHop are also declared. Although we don't declare them using typedef statements here, they are declared in the tree-routing module's specification. If typedefs are missing for any predicate, type inference is used with incomplete type specifications yielding errors. If materialize statements are missing for any predicate, default values are used.
Now we need to use this new predicate to generate messages periodically at each node. We do this by utilizing the built-in timer predicate we discussed in the previous section. So suppose that we want a new message generated and transmitted every 4 seconds (except at the base station , and hence need a periodic timer. We can do so with the following fact and rules:
timerx(@X, 3, 4096), X != 0. timer(@S,TimerID,TimerVal) :- timerx(@S,TimerID,TimerVal). timer(@S,3,TimerVal) :- timer(@S,3,TimerVal).
Using the format discussed earlier, we are able to instantiate a fact at all nodes except the base station. Furthermore, we use an ID of 3 for our timer, (as 1 and 2 are already in use), and set the period to 4096 milliseconds, or 4 seconds.
Next, we specify the beaconing frequency for the tree-routing layer using timer 2 and a frequency of 32000 milliseconds:
timerx(@*,2,32000).
The first rule from the instantiation of timer 2 already handles converting a timerx tuple into a timer tuple. We only need to setup a one-shot timer as the tree module already handles periodicity
So now we get back to creating messages periodically at all the nodes. The code is simply one fact and one rule:
toTransmit(@X,0), X != 0.
toTransmit(@Src, newVal) :- toTransmit(@Src, oldVal), timer(@Src,3,_), newVal = f_incr(oldVal).
The fact is simple; it creates the first message to be transmitted, with a sequence number of 0, at every node except for the base station. The rule in essence says that if Timer 3 fires (the underscore implies we don't care what the period of the timer is), then take the last message generated (remember, our toTransit table only holds one predicate), and increment the sequence number, creating a new message to transmit.
The last predicate is functionally equivalent to the code:
... newVal = oldVal + 1.
While DSN does allow such equations when all the parameters are variables, it currently does not allow such an operation with numerical constants. Instead, basic functions can be used, in this case the f_incr function, which increments a numerical variable by 1. Although this function is 'built-into DSN', it must still be declared for the compiler to understand it.
Open up the file snlog2/defs.snl. Looking at the code, we see a series of compiler-oriented
directives. The first two lines deal with timers:
! typedef(timer, uint16_t, uint8_t, uint32_t).
! builtin(timer, BuiltinTimer).
The syntax of the first command should be familiar, as it tells the compiler what the timer predicate looks like. The second command is a new one. It tells the compiler that timer is not a regular user-defined predicate. Rather there is a native nesC module that implements its functionality, which is specified by the second parameter.
A little further down, we see the declaration of four built in functions, in a similar fashion. The four functions perform the following operations:
f_add(Var1, Var2): Var1 + Var2
f_incr(Var): Var + 1
f_mult2(Var): Var * 2
f_div2(Var) - Var / 2
In order to utilize these functions, we have to import them into our program, much like the tree routing module, inserting the following command:
! import('defs.snl').
One thing to note is that timer 3 now appears in the body, or right side, of two rules. Consequently, that means that when timer 3 fires, both rules should be executed, right? Correct. The runtime daemon will put both rules in the queue to be executed; there is no guarantee on ordering. DSN does allow the user to specify the order of execution and priority of rules, which we discuss in the tree routing example, as this mechanism is not needed in this exercise.
Now that we've generated the messages, it's time to implement the routing logic. We start with our own messages. If we have a message to transmit, symbolized by a toTransmit tuple, and have a path to our destination, symbolized by the nextHop predicate, then we want to send this message the next hop along our given path. This indicates that we have to define a new predicate to symbolize this message. It should contain four fields: one that determines where the tuple currently is (required), one for the origin of the message, one for the eventual destination (to allow for multiple destinations), and one that contains the actual payload, which is the sequence number.
So we begin by declaring the predicate:
! typedef(message, uint16_t, uint16_t, uint16_t, uint16_t).
Next we insert the needed rule:
message(@Next,Source,Dest,Val) :- toTransmit(@Source,Val), nextHop(@Source,Dest,Next,Cost,Hops).
By specifying @Next for the location of the message predicate, this automatically tells DSN to send the tuple when it is created, rather than keeping it locally.
This rule poses a problem, however. New nextHop tuples are created often, as a route change, or even something as simple as a routing beacon leading to a new link cost value, result in a new tuple. Consequently, the rule gets executed numerous times for each toTransmit tuple, resulting in a single message being sent multiple times, which is unwanted. To solve this problem, DSN allows for the user to designate non-triggering predicates, meaning that the creation of a new instance of that predicate will not lead to the rule being reevaluated. This is done by placing a '~' after the predicate, and so our rule now becomes:
message(@Next,Source,Dest,Val) :- toTransmit(@Source,Val), nextHop(@Source,Dest,Next,Cost,Hops)~.
Next we move onto forwarding messages from other nodes. The rule will be nearly identical, except that we replace the toTransmit predicate with the message predicate:
message(@Next,Source,Dest,Val) :- message(@Current,Source,Dest,Val), nextHop(@Current,Dest,Next,Cost,Hops)~.
One issue now presents itself. We can't limit the size of the table for the message predicate because not every node will have the same number of children using it as a next hop in their path to the destination, and so it is not apparent precisely how many message tuples will be at a given node at any particular time. However, each (Source,Destination) pair should only be allotted one row in the table that gets overwritten when new messages are received.
DSN provides a mechansim for specifying a predicate's 'primary key' and resulting duplicate resolution policy. A primary key specifies a set of fields whose specific combination must be unique in the table. In DSN, one can specify the parameters that make up the primary key by placing a '^' before the parameter in the appropriate typedef statement. Now, when the system receives a tuple that has a primary key identical to an existing tuple, there are two options: deny insertion, or overwrite the existing tuple. The default policy is to deny insertion, but placing a '#' before the predicate name in the typedef statement. As such, we change the typedef statement for message to the following:
! typedef(#message, ^uint16_t, ^uint16_t, ^uint16_t, uint16_t).
Including the first parameter, the address of the local node, in the primary key is simply a formality as this table is stored locally and so all tuples will share the same location parameter value. The second and third fields are the source and destination of the message, and so by making them part of the primary key, we achieve our goal of only allowing a single message for each (Source, Destination) pair. We also choose to have new tuples overwrite existing tuples because otherwise all packets after the intial one for a given (Source, Destination) pair will be ignored.
The final step is to record, or store, all messages received at the destination. We can do this in predicate form because the address of this store predicate could be the UART, so the PC could pick it up. With the current set-up, a copy of all tuples stored at nodes with backchannels are sent over the UART so they can be analyzed by the PC data analysis tools.
The logic for this last rule is simple. If a node receives a message, and it is the destination, then store the message.
First we must declare this new predicate, store. In addition to the obligatory location parameter, only two other parameters are needed: one indicating the original source of the message, and the other holding the sequence number of the packet. As such, our declaration looks as follows:
! typedef(store, uint16_t, uint16_t, uint16_t).
Now as we think about this a little bit, we realize that we don't want multiple copies of the same message to be stored, and in fact want to suppress duplicate messages. This simply requires making all the fields of the predicate part of the primary key, and denying insertion of new identical tuples. The modified command looks like this:
! typedef(store, ^uint16_t, ^uint16_t, ^uint16_t).
Notably, not including any '^' indicators for primary keys is equivalent to marking all fields as part of the primary key, so the two previous rules are equivalent.
Finally, we specify the last rule:
store(@Current,Source,Val) :- message(@Current,Source,Dest,Val), Source==Dest.
The rule is as we discussed, with the interesting aspect being the equality check at the end, which determines whether the current node is the destination specified in the message. DSN allows this because both parameters are variables.
Congrats. You have now coded an entire DSN collection application, and your code should look like the following(lines starting with '%' are comments):
% Include function/built-in definitions and tree-routing module
! import('defs.snl').
! import('tree/tree-lqi.snl').
! typedef(toTransmit, uint16_t, uint16_t).
! typedef(#message, ^uint16_t, ^uint16_t, ^uint16_t, uint16_t).
! typedef(store, ^uint16_t, ^uint16_t, ^uint16_t).
! materialize(toTransmit,infinite,1,evict_random).
%Setup destination at all nodes.
dest(@*,0).
% Define beaconing frequency (needed by tree routing module)
timerx(@Src,2,32000).
% Generate messages periodically
timerx(@X, 3, 4096), X != 0.
timer(@Src,timerID,timerVal) :- timerx(@Src,timerID,timerVal).
timer(@Src,3,timerVal) :- timer(@Src,3,timerVal).
toTransmit(@X,0), X != 0.
toTransmit(@Src, newVal) :- toTransmit(@Src, oldVal), timer(@Src,3,_), newVal = f_incr(oldVal).
% Forward received messages
message(@Next,Source,Dest,Val) :- toTransmit(@Source,Val), nextHop(@Source,Dest,Next,Cost,Hops)~.
message(@Next,Source,Dest,Val) :- message(@Current,Source,Dest,Val), nextHop(@Current,Dest,Next,Cost,Hops)~.
store(@Current,Source,Val) :- message(@Current,Source,Dest,Val), Source==Dest.
One final item remains, which is more a matter of style rather than a requirement. It makes sense to separate general protocol functionality from application-specific commands. In other words, if we wanted to use this collection layer for another application, all the facts that need to be modified should be in a separate file.
Therfore, what we'll do is move all the application specific facts to a new file, TestSampleCollection.snl,
and simply import SampleCollection.snl. We'll also have to import our definition file, defs.snl, as we use
timers.
After the modifications the files look as follows:
TestSampleCollection.snl
! import('defs.snl).
! import('collection/SampleCollection.snl').
%Setup destination at all nodes.
dest(@*,0).
% Define beaconing frequency (needed by tree routing module)
timerx(@Src,2,32000).
% Define frequency of message generation (used in collection module)
timerx(@Src,3,4096).
timer(@Src,timerID,timerVal) :- timerx(@Src,timerID,timerVal).
% Generate first message at all nodes except for destination
toTransmit(@X,0), X!=0.
SampleCollection.snl
% Include function/built-in definitions and tree-routing module
! import('defs.snl').
! import('tree/tree-lqi.snl').
! typedef(toTransmit, uint16_t, uint16_t).
! typedef(#message, ^uint16_t, ^uint16_t, ^uint16_t, uint16_t).
! typedef(store, ^uint16_t, ^uint16_t, ^uint16_t).
! materialize(toTransmit,infinite,1,evict_random).
% Generate messages periodically
timer(@Src,3,timerVal) :- timer(@Src,3,timerVal).
toTransmit(@Src, newVal) :- toTransmit(@Src, oldVal), timer(@Src,3,_), newVal = f_incr(oldVal).
% Forward received messages
message(@Next,Source,Dest,Val) :- toTransmit(@Source,Val), nextHop(@Source,Dest,Next,Cost,Hops)~.
message(@Next,Source,Dest,Val) :- message(@Current,Source,Dest,Val), nextHop(@Current,Dest,Next,Cost,Hops)~.
store(@Current,Source,Val) :- message(@Current,Source,Dest,Val), Source==Dest.
One can argue that the rule that generates toTransmit tuples SampleCollection.snl should be moved to TestSampleCollection.snl as it embraces the assumption that each new message simply increments the sequence number of the previous message. Since this approach is somewhat general, its inclusion in either file is fine.
At this point, you can skip ahead to utilizing PC data analysis tools, or continue onto implementing tree-routing, which is a more involved example.