DSN New User Programming Tutorial
June 2007

Tree Routing: Another Example

In this example we essentially design the tree-routing module used in the previous example from scratch. We assume that application-specific declarations, such as the destination and the beacon frequency, will be set elsewhere.

Before we start, let's sketch out the pseudo code for our algorithm. In essence we are striving to implement MintRoute (or rather MultiHopLQI), the popular TinyOS 1.x tree-routing protocol:

1.  At the core of the algorithm is the use of routing beacons for a node to alert its neighbors about its current route to the destination.
1a. The information stored in each beacon is the starting point of the path (the node itself), the eventual destination, the link quality or cost, and the number of hops the node is from the destination (mostly for debugging/visualization purposes)
2. The root node or destination should begin by sending the first beacon, and continue to do this periodically.
3. If a node does not have a path to the base station, it should not send any beacons.
4. When a node receives its first beacon, it creates a path to the destination by incrementing the number of hops by one, adding the cost of the link with the neighbor to the exposed path cost, and setting its parent as the source of the beacon.
5. After a node has a path, it should send beacons periodically.
6. Once a node has an established path, there are two possible cases when it receives a beacon.
6a. Beacon is from current parent - In this case, the path cost and hop count are updated with the new information.
6b. Beacon is from another parent - If the advertised path cost is less than the current cost, and the path doesn't create a cycle, use this new path.

So let's begin with the beaconing. From the pseudocode, we see that our beacon predicate will have 6 fields (because of extra location parameter). Consequently, we declare it as such:

! typedef(beacon, uint16_t, uint16_t, uint16_t, uint16_t, uint16_t, uint16_t)

So our beacon predicate looks as such:

beacon(@Location, Source, Destination, NextHop, LinkCost, Hops)

Now let's apply some of the lessons from the previous section. We can't limit the size of the table because we don't know a priori how many neighbors each node will have. We don't want entries to time out, and a random eviction policy is fine. Since these are the defaults, we have no need for a materialize statement. However, looking at the structure of the predicate, we realize that we only want to maintain a single beacon for each (Source, Destination) pair, as a new beacon will update the last 3 fields, but will render the previous beacon useless, so it should replace it. Using the syntax we learned, our statement gets modified slightly:

! typedef (#beacon, ^uint16_t, ^uint16_t, ^uint16_t, uint16_t, uint16_t, uint16_t).

Alright, now that we've set up, let's get to actually issuing some beacons. Since beacons are periodic, the first thing we need to do, is set up a periodic timer. Remember that we decided to assign timer #2 to the beaconing frequency. So we set up our periodic timer in the following manner:

! import('defs.snl')
...
timer(@Source,2,Period) :- timer(@Source,2,Period).

Remember, the file defs.snl provides a lot of useful definitions, including timer. You will probably need to include it for basically any DSN program.

So now we want the sink node, or the destination, to send out beacon messages advertising its presence periodically. First we need to introduce a predicate that indicates who the destination is, and as seen in the last section, the predicate takes the following form:

dest(@Source, Destination)

As such, our formal definition that we insert into our program is:

! typedef(dest,uint16_t,uint16_t).

Now, since we are implementing the MultiHopLQI algorithm, we only need to support a single destination, and as such can restrict the size of the table to 1 with the following command:

! materialize(dest,infinite,1,evict_random).

Remember that the user program uses facts to define the destination at every node. With this setup, we can schedule periodic beacons from the base station with the following code:

beacon(@*,Source,Source,Source,0,0) :- timer(@Source,2,Period), dest(@Source,Destination), Source == Destination.

So the timer predicate is just to maintain the periodic nature, and the third clause will only evaluate to true at the destination. Therefore, only the destination is sending this out. As for the beacon predicate that is formed, we see it is broadcast to all nodes. As for the rest of the fields, the source of the beacon is obvious, the destination of the path is again, itself, and the next hop in the path is itself. Furthermore, it is 0 hops away from itself, and its link quality is 0, which is perfect.

So now that we have the base sending periodic beacons, we have to tell the other nodes what to do when they receive this beacon, as well as future ones from other nodes. We break the receiving of a beacon into two possible cases: the first beacon a node receives, and subsequent ones. The reason for this distinction is that the first case initializes the node with a path to the base station, and subsequent offerings can be compared against the existing path.

Before we do anything, we need to create the predicate that will maintain our path to the destination. Given that the beacon message is essentially a broadcast of this information, the two predicates will look very similar. We will call our predicate nextHop, and it will look as such:

nextHop(@Location, Destination, Next_Hop, Link_Cost, Hops)

Formally, we define it in our program as follows:

! typedef(#nextHop,^uint16_t,^uint16_t,uint16_t,uint16_t,uint16_t).

We make Location and Destination primary keys because, as per MultiHopLQI, we should only maintain a single path to each destination. Furthermore, as this information gets updated, it should replace the existing tuple in the table. Going further, if we only have a single destination, then we should only have a single nextHop tuple at any given time. Consequently, we can add the following command:

! materialize(nextHop,infinite,1,evict_random).

Now, we need a rule that says if this is the first beacon message, then create a nextHop tuple by using the information from the received beacon, adding the cost of the link with source of the beacon and the advertised link cost, and incrementing the number of hops by 1. This poses two problems that we have not yet discussed how to handle: How do we write a rule that only executes the first time a beacon is received, and also how do we derive the cost of a link?

To solve the first problem, DSN provides a negation operator, '-', that in essence acts as a clause that only evaluates to true if the specified instance of that predicate does not exist. A potential usage scenario would be as follows:

head(@A,B,C) :- bodyOne(@A,B,C), -bodyTwo(@A,C)

This says that if an instance of the bodyOne predicate exists with the given parameter values, and no bodyTwo exists with those parameter values, then the head tuple is created with the appropriate parameter values.

To address the second concern, we use a built-in function that we designed as it requires the utilization of hardware-specific information. MultiHopLQI uses a transformation of the LQI value provided by the CC2420 radio for each received packet. With the value provided by the radio, a higher value indicates a higher quality link. However, MultiHopLQI's transformation inverts this relationship, and also adds link costs to be added across multiple hops to obtain an end-to-end link quality measurement

We have designed a built-in module that maintains this transformed value for the last packet received from any node. In other words, the predicate, shown below, has only one tuple for any neighboring node at a given time which provides the tLQI (Transformed LQI) of the last received packet from that source:

linklqi(@Location,Destination,Link_Cost)

In order to use this predicate, we have to formally define it in our program as a built-in predicate:

! builtin(linklqi,BuiltinLinkLqiC).
! typedef(linklqi,uint16_t,uint16_t,uint16_t).

With that out of the way, we're now ready to write our rule for the first beacon message received (For ease of reading it has been spread over multiple lines, but should only be one line in actual program):

nextHop(@Source,Dest,nextNextHop,newCost,newHops) :-
  beacon(@Source,newNextHop,Dest,oldNextHop,oldCost,oldHops), 
  -nextHop(@Source,Dest,_,_,_), 
  linklqi(@Source,newNextHop,linkCost)~, 
  oldNextHop != Source, 
  newCost = f_add(oldCost,linkCost), 
  newHops = f_incr(oldHops), 
  dest(@Source,Dest), 
  Source != Dest.

While the rule may seem long, it is basically a direct conversion of our pseudocode above. The first clause is obviously the received beacon. The second clause uses Don't Cares for the last three parameter values to say that any tuple that has that destination would cause the rule to evaluate to false. The third clause grabs us the cost of our direct link to the beacon source. We use the '~' symbol because we do not want the rule to fire every time a new packet from that destination is received, which would create a new linklqi tuple. The fourth clause is designed to prevent simple loops: in essence it says if the beacon source was using the local node as its next hop to the destination then we don't want to use this path. The fourth clause adds our link cost with the existing path cost to get the new path cost, and the fifth clause increments the number of hops to the destination by one. Finally, the sixth clause defines the destination that we are routing to, and the last clause ensures that the current node is not indeed the destination itself.

We had said that we wanted each non-destination node to begin generating periodic routing beacons as soon as they a path to the root. We can now do that with the following rule:

beacon(@*,Source,Dest,nextHop,Cost,Hops) :- timer(@Source,2,Interval), nextHop(@Source,Dest,nextHop,Cost,Hops).

This will only fire if a nextHop tuple exists. Note that we make the design decision to not only send periodic beacons, but also send a beacon as soon as a new nextHop tuple is created. If strict periodicity is desired, one can just make nextHop a non-firing predicate using the '~' symbol, as described in the previous section.

Now we move onto the final step: implementing the node logic for subsequently received beacons. In essence, there is again two cases: a node's current parent (i.e. next hop in the routing tree) sending it a beacon, in which path information must be updated, and the case where another node advertises a different path to the destination.

In order to make this task easier, we define an intermediate predicate that will hold information about the path being advertised, from the perspective of the local node. In essence, its format is identical to the nextHop predicate, and we will call it candidate. The form is as follows:

candidate(@Location, Destination, Next_Hop, Total_Cost, Total_Hops)

The formal definition in the program follows from this (Note: Since this declaration uses all default options, it can be excluded, forcing the DSN compiler to infer its structure):

! typedef(candidate,uint16_t,uint16_t,uint16_t,uint16_t,uint16_t).

The rule for creating a candidate tuple is essentially identical to the rule above for creating a nextHop tuple, except that instead of demanding the absence of a nextHop tuple, we remove the negation to demand that a nextHop tuple does exist:

candidate(@Source,Dest,nextNextHop,newCost,newHops) :-
  beacon(@Source,newNextHop,Dest,oldNextHop,oldCost,oldHops), 
  nextHop(@Source,Dest,_,_,_)~, 
  linklqi(@Source,newNextHop,linkCost)~, 
  oldNextHop != Source, 
  newCost = f_add(oldCost,linkCost), 
  newHops = f_incr(oldHops), 
  dest(@Source,Dest), 
  Source != Dest.

We append the '~' to the nextHop predicate because we want the rule to only fire (i.e. execute) when a new beacon is received. As per the similarity to the rule for creating our first nextHop tuple, if accepted, a candidate tuple basically translates directly into a new nextHop tuple.

So now we look at the first case in which this candidate tuple is created using a beacon that came from our current recognized parent in the routing tree. We can determine this by checking whether the next hop of the new candidate tuple and our existing nextHop tuple match. If so, then we just update the link cost and hops information for our existing nextHop tuple: (we actually create a new tuple and overwrite the old one, but the concept is the same)

nextHop(@Source,Dest,nextHop,newCost,newHops) :- 
  candidate(@Source,Dest,nextHop,newCost,newHops), 
  nextHop(@Source,Dest,nextHop,oldCost,oldHops)~, 
  dest(@Source,Dest).

Again, we make the nextHop predicate non-firing to allow only a new candidate tuple to cause the rule to be executed.

Now in the second case where a new parent is being proposed, we check to see if the cost of the new path is less than the cost of the old path, and if so we use the new path:

nextHop(@Source,Dest,newNextHop,newCost,newHops) :-
  candidate(@Source,Dest,nextNextHop,newCost,newHops),
  nextHop(@Source,Dest,oldNextHop,oldCost,oldHops)~,
  dest(@Source,Dest),
  newNextHop != oldNextHop,
  newCost < oldCost.

The first three clauses are self explanatory. The fourth clause ensures that the new parent in fact differs from the old parent, and the final clause ensures that the cost of the new path is less than that of the old path.

We are almost done; just one optimization remains. As we look at the code, we realize that if a new beacon comes in and the system is busy processing other rules, the execution of the rule for the candidate predicate will get delayed as it must wait in a queue, although we would want it to process immediately so that we could then send out our own new beacon if necessary.

DSN provides a priority mechanism for specifiying the relative importance of different rules. The only rule we care about here is the candidate rule, and so by only assigning it a priority, we ensure the rule is always executed immediately. We do this with the following command:

! priority(candidate,1).

Prioritized deduction offers a simple way for users to express processing preferences, while not worrying about the underlying mechanism. It also differs from traditional deduction where execution preferences are not directly exposed to users.

Additionally, priorities can address race conditions that may arise when using intermediate temporary predicates, since DSN does not provide multi-rule atomicity. These races can be avoided by assigning high priority to temporary predicates.

Congratulations! You're done with the tree routing protocol. Your code should look similar to the following: (Again, long rules have been broken up for aesthetic purposes, but should not be in the actual program)

! import('defs.snl')

! typedef (#beacon, ^uint16_t, ^uint16_t, ^uint16_t, uint16_t, uint16_t, uint16_t).
! typedef(dest,uint16_t,uint16_t).
! typedef(#nextHop,^uint16_t,^uint16_t,uint16_t,uint16_t,uint16_t).
! builtin(linklqi,BuiltinLinkLqiC).
! typedef(linklqi,uint16_t,uint16_t,uint16_t).
! typedef(candidate,uint16_t,uint16_t,uint16_t,uint16_t,uint16_t).
! priority(candidate,1).

! materialize(dest,infinite,1,evict_random).
! materialize(nextHop,infinite,1,evict_random).

% Setup periodic timer
timer(@Source,2,Period) :- timer(@Source,2,Period).

% Periodic beacons from the root
beacon(@*,Source,Source,Source,0,0) :- timer(@Source,2,Period), dest(@Source,Destination), Source == Destination.

% Creating first nextHop tuple after first beacon received
nextHop(@Source,Dest,nextNextHop,newCost,newHops) :-
  beacon(@Source,newNextHop,Dest,oldNextHop,oldCost,oldHops), 
  -nextHop(@Source,Dest,_,_,_), 
  linklqi(@Source,newNextHop,linkCost)~, 
  oldNextHop != Source, 
  newCost = f_add(oldCost,linkCost), 
  newHops = f_incr(oldHops), 
  dest(@Source,Dest), 
  Source != Dest.

% Create periodic beacons at non-root nodes
beacon(@*,Source,Dest,nextHop,Cost,Hops) :- timer(@Source,2,Interval), nextHop(@Source,Dest,nextHop,Cost,Hops).

% Received a new beacon msg
candidate(@Source,Dest,nextNextHop,newCost,newHops) :-
  beacon(@Source,newNextHop,Dest,oldNextHop,oldCost,oldHops), 
  nextHop(@Source,Dest,_,_,_)~, 
  linklqi(@Source,newNextHop,linkCost)~, 
  oldNextHop != Source, 
  newCost = f_add(oldCost,linkCost), 
  newHops = f_incr(oldHops), 
  dest(@Source,Dest), 
  Source != Dest.

% Update information about current parent
nextHop(@Source,Dest,nextHop,newCost,newHops) :- 
  candidate(@Source,Dest,nextHop,newCost,newHops), 
  nextHop(@Source,Dest,nextHop,oldCost,oldHops)~, 
  dest(@Source,Dest).
  
% Insert a new and better parent
nextHop(@Source,Dest,newNextHop,newCost,newHops) :-
  candidate(@Source,Dest,nextNextHop,newCost,newHops),
  nextHop(@Source,Dest,oldNextHop,oldCost,oldHops)~,
  dest(@Source,Dest),
  newNextHop != oldNextHop,
  newCost < oldCost.