// The Song Remains The Same

saw them hurrying from either side

and each shade kissed another, without pausing,

Each by the briefest society satisfied.

(Ants, in their dark ranks, meet exactly so,

rubbing each other’s noses, to ask perhaps

What luck they’ve had, or which way they should go.)

— Dante, Purgatorio, Canto XXVI

Before I went back to grad school, I had been studying self organization and emergent systems as a side interest. While in grad school, when the opportunity to work on mobile ad hoc networks came along, I jumped at the chance to apply a swarm based routing algorithm in real research. My master’s thesis (TinyTermite [1,3]) ended up applying social insect inspired routing algorithms on wireless mesh networks (along with improving security in the base routing algorithm). In a previous article, we took a look at discovery and social insects;  Just like in nature, the base algorithm Termite [2] uses local information to make the wireless mobile ad hoc networks (MANET) self organize and adapt to their conditions.

TinyTermite is a novel probabilistic routing algorithm that is secure against selective forwarding and replay attacks. We use a technique called “suspicion” (or suspicion pheromone) to track possibly compromised neighbor nodes. As suspicion builds up and decays for each neighbor, TinyTermite is able to deal with uncertain stimulus and react properly. TinyTermite is fully implemented on the TinyOS based Intel Mote2 platform and experiments were done to compare its performance with that of the traditional Termite algorithm. With TinyTermite we implemented a swarm based routing algorithm that uses a digital pheromone to drive stigmergy among nodes in a mobile ad hoc network. The network is completely decentralized, just like the ants, and can adapt in uncertain conditions by leveraging stigmergy and indirect communication.

MANETs use a group of nodes to move information from a source node to a destination node without having a central authority directing the operations. MANETs can be quickly and inexpensively set up as needed and require no centralized administration or fixed network infrastructure such as base stations or access points. MANETs have begun to move into the commercial industry as a way to track inventory, route traffic, and move information. However, for applications such as military uses, disaster relief, and mine site operation, security and reliability are key.

With MANETs, we do not assume every node can hear every other node; This is a typical characteristic of these type networks. Wireless networks are inherently less reliable than wired networks due to interference. Routing is a key problem in any information network. MANETs are very dynamic when compared with their statically wired cousins. To route a packet, a node needs to know only the next hop to forward a packet to; However, this can be quite a difficult problem when a MANET’s topology changes frequently. Some key routing algorithms in the field are:

• AODV
• DSR
• OSLR
• DSDV

The underlying algorithm that TinyTermite is based on is called Termite. Termite is a biologically inspired routing algorithm for MANETs that is based on previous work in adapting the effects of stigmergy. Termite models how termite colonies lay pheromone to communicate in a decentralized manner. The concept of pheromone (as I’ve talked about before) is taken directly from the social insect metaphor where social insects use the chemical pheromone as a way to communicate indirectly. Termite piggybacks pheromone on normal network traffic which “trains” the network in an “on-line” manner. A more common technique is to send special packets out with the purpose of updating routing information around the network.

Termite is based on stigmergy powered by digital pheromone, which creates patterns of self organization in the ad hoc network. Termite was developed by Martin Roth and Stephen Wicker at Cornell. I’ve talked about stigmergy quite a bit in previous articles and in my graduate research I actually got a chance to create social intelligence between embedded devices. It was a lot of fun to see a flock of tiny devices “come alive” and show “bottom up” intelligence.

TinyOS is an open source operating system and platform intended for wireless sensor networks. TinyOS is an embedded operating system written in the nesC programming language as a set of cooperating tasks and processes. TinyOS started as a collaboration between the University of California, Berkeley in co-operation with Intel Research. Since that time the project has grown into an international consortium, the TinyOS Alliance. There is a lot of interesting research based around wireless mobile ad hoc network (MANETs).

The primary language, nesC (network embedded systems C), used for development on TinyOS is a component-based, event-driven programming language (quick tutorial for the interested). It’s basically C with some minor quirks and less features. However, the real difference is whichever compiler variant you end up using for your mote platform as some compilers are far more mature than others.  We worked on the Imote2 hardware which is considerably more advanced than earlier TinyOS based motes. Each Imote2 mote has a 415MHZ clock rate and 32 Megs or ram running on an Intel XScale2 processor. The one thing the XScale2 does not have is a floating point processor on its ALU, which provided some hurdles to overcome with floating point processing. I taught 3 days of a graduate class on communications as part of my graduate research work. I’ve posted my slides (slides are located here and here) from class on developing for the platform for those interested in what the platform is like. My sessions were on specifically the TinyOS platform and programming in the nesC language.

I spent a lot of time studying the basics of ad hoc networks, routing, and self organization while doing our research. It really made me re-evaluate what an operating system actually is and is not (a browser is not an operation system). I also became a tremendously better programmer having to work on an embedded processor with much tighter constraints that on a desktop machine. Spending a lot of time in ad hoc networks also made me think about other domains where we having an uncertain topology of “nodes” where dynamic decentralized discovery is needed — namely linked web data and the self organizing web data ecosystem. It also made me think of new ideas on how computing is evolving and where we can draw on themes from wireless ad hoc networks and apply them to other domains.

The field of self organization is amazing and I really enjoyed being able to work in academia doing research in that arena. It gave me a new appreciation for the non-mainstream area of computer science where I had to rely more on theory background and less of dogmatic ideas of mainstream programming. I also got to see my own work in self organization come alive, which was a thrill for me. Somewhere along the dull days of research, I scribbled down the words “elegant complexity emerges from brilliant simplicity” as a footnote on a draft of my thesis; I think that holds, especially in “bottom up” emergent systems. I think all too often in design we forget occam’s razor and try to overdo it. Termite is a great example of this as it uses no special packets to broadcast network topology yet continuously explores possible new routing solutions.

TinyTermite is completely decentralized and I believe provides a good example of the possibilities of decentralized dynamic discovery. I’ve already touched on some ways that this type of discovery could be useful in other domains, such as open linked web data. I also believe as the web continues to take over the desktop that we will see more techniques borrowed from mesh networks and applied to the internet as it becomes more like a single machine. In future articles I want to sketch out more ways I believe that could happen.

References

[1] J Patterson, TinyTermite: A Secure Routing Algorithm (Master’s Thesis)

[2] M Roth, S Wicker, Termite: A Swarm Intelligent Routing Algorithm for Mobile Wireless Ad-Hoc Networks

[3] M Sartipi, J Patterson, TinyTermite: A Secure Routing Algorithm on Intel Mote 2 Sensor Network Platform, Innovative Applications of Artificial Intelligence 2009