Blast: Multihop Routing Stack for Tinyos Introduction

Blast is a routing stack for general sensing application. Sensor readings are collected and encapsulated to packets by the applications. Blast will then create an adaptive, self organizing network, route these packets to a (or a few) basestation.

Installation

Let's begin with installing and compiling the code before we moved on to configuration. Download the stack code and some sample multihop applications. Unzip it and move it to anywhere you want. For simplicity, let's extract both zip files to the apps directory. You will then see two directories, Blast which contains the stack code and Blast-app which contains a sample multihop application.

In apps/Blast-app/Makefile, make sure the cflags is pointing to the right path of blast. It will be something like this.

CFLAGS=-I../Blast/Sender -I../Blast/Interface -I../Blast/DataStructure -I../Blast/VirtualComm -I../Blast/RoutingStack

This will make sure the compiler will find the right files to compile. For those mica 2 people out there, please check this out, before you compile the code. To compile the sample application, go to Blast-app directory and type make mica, (or mica2, mica2dot) and type make mica reinstall.1 to install a basestation. Node 1 is by default the base station. Node x (for any x bigger than 1) are those "normal" nodes that sense data and in terms of the running code, there are no difference between these nodes and the base station.

Running

After you downloaded the code to the basestation, listen to the uart. You should be able to see

7e 00 66 09 06 01 0c 0c 01 01 15
7e 00 66 09 06 01 0d 0d 01 01 19
7e 00 66 09 06 01 0e 0e 01 01 19
7e 00 66 09 06 01 0f 0f 01 01 1d
7e 00 66 09 06 01 10 10 01 01 1d

The first five bytes are am header. The last four bytes are Blast header. You can see 01 0c are the data from the CollectData application.

If you use GenericBase to listen to the air, you should be able to see

7e 00 02 09 07 7e 00 00 00 00 01 20

These packets with types 2 are the route messages. They are broadcast periodically to tell its neighbors about its parent, hop, cost, receive estimates.

Next, download node number 2. Plug in node 1 to your serial port. This may take a while for node 2 to join the network. For the default setting, this should take 30 packets, (that is 90 seconds for collect data). You should be able to see data like this

7e 00 66 09 06 01 0c 0c 01 01 15
7e 00 66 09 06 02 02 03 02 01 19
7e 00 66 09 06 01 0e 0e 01 01 19
7e 00 66 09 06 02 03 03 02 01 1d
7e 00 66 09 06 01 10 10 01 01 1d

Congrutulation! You did it! (and I did it too!)

Visualization Installation

I hacked up something real quick for network visualization. The gui files are here. I also wrote a shell script so that installation can be easier. Please notice that this is a fast hack. All I did is to make Surge GUI to display some lines. The advance features in SurgeGUI, like focus and sleep does not work. I don't plan to support those features.

Here are the installation steps.

1) Set your TOSDIR to tos directory.

export TOSDIR="path/to/tos" 

2) Untar my compressed file, run

cd SurgeInstall; ./SurgeInstall

3) I am lazy, especially typing those long long tinyos path. I put the following lines in ~/.bash_profile for convenience

# Make sure you are using COM1 for serial port! if not change the below line
# If you are using mica2, please add -baud 57600
alias startsf="cd ~/projects/tinyos-1.x/tools/java; java net.tinyos.sf.SerialForward -comm COM1 &"
# Replace 9 with the right group id. You can find this in your TOSDIR/apps/Makerules
alias startsurge="cd ~/projects/tinyos-1.x/tools/java; java net.tinyos.surge.MainClass 9 &"
# Again, are you using COM1?
alias startlisten="cd ~/projects/tinyos-1.x/tools/java; java net.tinyos.tools.ListenRaw COM1 &"
# This should be fine
alias startfl="cd ~/projects/tinyos-1.x/tools/java; java net.tinyos.tools.ForwarderListen.java localhost 9000 &"

After you put that in yoru .bash_profile, remember to do

source ~/.bash_profile

Running Visualization

1) Instead of running collectdata, use Surge as your app. All you need to do is to edit the Makefile and change COMPONENT to

COMPONENT=BlastGUI

2) Download and run the code as collect data.

3) Start your Serial Forwarder by typing startsf as you defined earlier

4) Start your surge gui by typing startsurge as you defined earlier.

5) Wait and See

6) Email me if you get that to work! :)

Configuration

Blast allow you to use 8 bit or 16 bit addressing. The reason is that 8 bit addressing is simplay smaller! This means that application can put more data in their packets; more neighbors can be feedback in a route message; smaller route table size, etc. We provide 16 bit addressing because some applications do need more than 256 nodes! To change this, go to RoutingStack/RoutingStack.h,

typedef uint8_t address_t;

Base Station by default is node 1. You can also change this in RoutingStack.h. Just want you to know that zero for node id is a bad number for LFSR random generator.

  BASE_STATION = 1,

Blast periodically broadcast route messages. You can specify how often you send this updates. A general rule is about 2 times your data rate. If it is too frequent, it wastes energy and congests the network. If it is infrequent, it is not adaptive.

  ROUTE_FREQ = 6000

Mica2

This section was written for the mica2 radio stack dated on June 2003. The following inconsistencies may have been fixed. I am not sure what is the status for today. If Blast works without any modification, then goes with it. If not, you need to change two settings in order for Blast to work. In Blast/VirtualComm/VirtualCommM.nc, search for

call CommControl.setCRCCheck(TRUE);

and comment it out. This is because Mica2 radio stack does not set the CRC flag. If we set that to true, AMPromicious will filter out all the packets. Hopefully, this inconsistency in the radio stack will be corrected soon. If the motes doesn't receive any packets using AMPromicicious, this may be a sign. In Blast/RoutingStack/RoutingStack.h, search for

MHSENDER_RETRANSMIT_TRIAL = 3,

change this to 0. Since mica2 radio stack does not set the ack flag of the packet to true, (even though it does not have the ack mechanism), Blast will automatically retransmit 3 times. That is why we need to disable retransmission for mica2.

FAQ

Can multiple application use Blast at the same time to send packets to Base Station?
Yes, you can! You can have BlastGUI running to display the network topology, while you have another application sending sensor value. All you need to do is to connect different parametric interface to the stack.

What is the difference between GenericComm and VirtualComm? Why do you want me to use VirtualComm?
If there are multiple applications sending to GenericComm at the same time, only one can get through. It will return send fail for all of them except one. Application, either start a timer to resend or discard the packet. With VirtualComm, application can treat the comm as its own. Other applications comm activities do not affect each other.
VirtualComm also provides a retransmission interface. If there is no acknowledgement for a sent packet, VirtualComm will fire up a event, asking the application how many times at most the applications want to retransmit. VirtualComm will then try its best before giving up.
VirtualComm also provides a snooping interface. Applications can sniff all packets on the air, even it is not destinated to local node.

How do we debug?
Leds and sniffing on the air. No Jtag or fancy stuff like that! :(

Why does it takes so long for the nodes to join the network?
We are currently working on this issue. The problem is that we need x number of packets in order to get a reasonable estimation. In the beginning, nodes are just broadcasting packets on the air. It does not send packets through the route tree.

Why do I see some more gabbage at the end of a Collect Data packet when I use ForwarderListen?
ForwarderListen expects 36 number of bytes. Collect Data only send about 13 bytes of data. Anything beyond this 13 bytes are garbbage. You can change SerialForwarder so that it accept the exact same number of bytes. Using ListenRaw instead can also solve the problem.

How good is Blast?
For the experiments we did in Hearst, Blast can get 85% - 93% of data to the basestation. We are using 50 nodes, sending at a power of 40. (about 16 feet of effective range) Each node is 8 feet apart, sending data packets every 20 to 30 seconds. Please notice that one link alone can have up to 25% packet lost, achieving 85% overall with in average two retranmissions per packet is pretty good.

What platform did we test Blast on?
We did our 50 nodes experiment on mica. We also get it working with Great Duck Island Project. The platform they are using is mica2dot. Although we did not do extensive studies on mica2, I believe it works pretty well.

Who are using Blast?
Firebug Project from Civil Engineering.
Ivy, A Sensor Network Infastructure for College of Engineering
Great Duck Island, Habitat Monitoring

Hey dude, your thing is not low power?
But hey, we need to tackle problems one by one. It is impossible to solve the whole world in one semester! The next thing we are going to look at is scheduling.
The GDI Project used Blast for Habital Monitoring. In order for their nodes to last long, they used the Low Power Listening mode of mica2. All you need to do is wired up SetTransmitMode, SetListeningMode from CC1000RadioIntM. From what they told me, it worked really well on the island. If you have burning desire about using Blast in low power mode, send me an email. It can be done fairly easily.

Did you guys have any publication on this?
Yes, we submitted our paper to Sensys 2003. The camera ready version is going to be available soon.

Is this FAQ frequently asked?
No!

Why does it take so long to boot up? How often do they change parent? How do I control adaptivity? Since the default minimum transmission algorithm for Blast depends on estimations, so whenever estimations changed, parents change. Although nodes evaluate its neighbors every "route freq" as defined in RoutingStack.h, their best parents stay the same because estimations of neighbors don't change, so technically for big changes (such as node die or node moves away) to propagate, it will takes "route freq" times "estimate to route freq" seconds. (it takes "estimate to route freq" route update to compute a new estimation of neighbor). Therefore, you will notice a phenomenon that most parent changes occur when a new estimation is evaluated, then it continues to be not so stable for another few route updates because routing cost takes a few rounds to propagate down the tree. Then they remain to be stable for quite a long time until a new estimations is calculated. This will also answer the question of "why does it take so long to boot up". It takes roughly "route freq" times "estimate to route freq" seconds for nodes to get parents initially.
If this wait is too long, you can either increase your "route freq" or decrease "estimate to route freq". But care should be taken when you tuned these parameters. If route freq is too small (or too fast), the network will be congested. If "estimate to route ratio" is too small, then estimation will be less accurate causing poor decisions (and therefore poor reliability) and also unstable network.
Another thing to look at is the the estimator's "sensitivity" which is also defined in RoutingStack.h. This value is defined between 1 to 7. The higher the value, the less sensitive it is, that is more stable. If you want fast adaptation, you should decrease the value, but that may result in network unstability.
You can tell me what sort of application you are attempting to use Blast with. I will be happy to tune the parameter for you.
Pretty soon we are going to release a second version that is easy to be tuned. It will have one to one support, flooding support, fast tree building support and many other features included. The software has already been written long time ago, but I am too lazy or too busy to test it throughly. I promise you it will be soon!

TroubleShooting

For 8 bit addressing, both VirtualComm and MHSender uses 2 bytes header (so totally 4 for the whole thing), If you are sending a message to VirtualComm with length bigger than TOSH_DATA_LENGTH - 2 or to MHSender with length bigger than TOSH_DATA_LENGTH - 4, packet will be rejected, so make sure you are packets with the right length.

VirtualComm can only allow VC_QUEUESIZE of applications using it simultaneously. If the Routing Stack is used, there will be VC_QUEUESIZE - 1 (1 for Route Beacon) application available. Make this bigger if you have too many applications sending to the comm.

Things are not going to work if you are sending too fast because the network will be congested around basestation. Use the following formula to calculate the highest frequency. We can roughly have 20 packets per seconds
1 / Route Message Rate (msg/seconds) * number of nodes + 1 / Data Rate (seconds/msg)* number of nodes * expected retransmission (say 2) < 20
Make sure you are not sending too fast

Check to see if your application data type conflict with the predefined type in RoutingStack.h

Make sure all your applications are using virtualcomm, instead of GenericComm.

Increase your task queue in tos/system/sched.c (We use 128) The default task queue size is not going to work when it is run in a large scale. You don't want things to fail apart after running of serveral hours. We are going to make our stack will be taskless in future version

Make sure you wired up the InFowardReceive of ParentSelection

If you get low realiability on mica one
1) make sure your network is not too sparse. Nodes have to be in range in order to route!
2) the programming broad has great effect on the base station reception.
3) Make all your attena pointing up. That has a big influence on reception
4) Make sure you specify number of MHSENDER_RETRANSMIT_TRIAL > 0