TARP (the Tiny Ad-hoc Routing Protocol) is our proprietary routing solution. The platform has been designed with the premise of self-scalable, ad-hoc oriented collaboration of small and generally unreliable nodes. By assuming that the nodes are unreliable our solution is more resilient than typical wireless sensor network protocols. TARP is based on an ad-hoc mesh network that:

• Requires no central authority (no access points)
• Self-organizing into local micro-networks based on population of users rather than pre-deployed infrastructure
• Good for network applications driven by personal proximity rules

Before we describe TARP in depth, take a look at a traditional ad-hoc routing scheme (e.g., AODV in ZigBee®), which operates like this:

• Nodes advertise themselves by broadcasting HELLO messages. This way a node is able to learn the identity of neighbors, i.e., other nodes within its communication range.
• When node S wants to establish a data path to node D, it initiates a route discovery procedure, whereby the prospective intermediate nodes exchange special messages to figure out the best path among them.
• Once the best path has been established, every node on it knows the identity of the next hop neighbor on the path. On every leg of its trip, the packet is forwarded to a single specific neighbor.
• If the path breaks (because of mobility or node failure), the first node discovering the breakage starts a route recovery procedure, which essentially works in the same way as the original route discovery.

The network combines broadcasting (HELLO messages, route discovery or recovery) with point-to-point transmissions (the actual forwarding). It operates in several different MODES (neighborhood identification, route discovery, forwarding, failure detection, route recovery). The implied assumption is that forwarding is something special and quite different from the other modes. In our opinion, there is no rationale for this assumption! It appears to us an atavistic desire to see wires where they do not exist. This is not ad-hoc routing! This is routing along virtual wires laid in an ad-hoc and potentially dynamic environment.

Any packet forwarded to a specific next-hop node (along the red arrows) is in fact overheard by all one-hop-neighbors of the forwarding node (transparent arrows). The best path is an illusion. There is no such thing in the network any more than there are direct links between adjacent pairs of nodes on the alleged path. Isn’t “wireless” another word for “link-less?” This is the right way:

In the traditional approach, the dilemma of a forwarding node is this “To which neighbor should I direct the packet?” With TARP, the forwarding node has no dilemma at all – it simply sends the packet out. Note that the net outcome is the same in both cases: the packet has been broadcast to all nodes in the neighborhood.

But now a receiving node faces a dilemma: “Should I become a forwarding node for the received packet?” Thus, TARP changes the paradigm of forwarding: the basic question is not “where?” but “whether?” With a bit of insight, this change brings about the following features:

• Controllable redundancy of paths. Alternative paths can be explored simultaneously with no need to “recover” them upon a node’s disappearance or failure. This may be highly advantageous from the viewpoint of reliability and fault tolerance.
• Mode-less operation and no bureaucratic traffic. All packets ever transmitted through the network originate at the application.
• No need to re-frame packets on every hop. As the forwarded packet is not addressed to any specific neighbor, it needs no neighbor address. This avoids extra overhead, which tends to be particularly painful for short packets, as most packets in sensor networks actually are.
• Intermediate nodes, i.e., ones that are never sources nor destinations need no addresses.
• Simplicity and automatic scalability: route quality trades for node footprint.

TARP solves the dilemma of a receiving node by applying a chain of rules to the received packet. Each rule bases its decision on some information cached by the node while listening to the packets. When a rule succeeds, the packet is dropped (the node concludes that it shouldn’t forward the packet). Otherwise, the next rule takes over. If all the rules have failed, the packet is rebroadcast. Here is how it all looks:

The rules are implemented in such a manner that they fail if not enough information is available in the cache to make an authoritative decision. This way a node with less memory will tend to drop fewer packets, which may result in more redundant (suboptimal) routing. But no packets will be lost (dropped incorrectly) because of the lack of storage. Thus, TARP automatically trades the quality of routes for device footprint.

The quintessence of TARP is the so-called SPD rule (for Suboptimal Path Discard), which acts to shrink the population of forwarding nodes to a controllable-width stripe along the shortest paths between source and destination. The width of this stripe may be controlled by the application for the desired degree of redundancy.

**comparison** TARP versus mesh networks

All commercial ad-hoc ideas are based on point-to-point forwarding which:

• is complicated
• is messy (there shouldn’t be any p-p links in wireless)
• requires resources (RAM) which are poorly scalable
• cannot be easily “fuzzied” (i.e., you cannot have an “approximate point-to-point routing” traded for reduced resources)

TARP, in contrast:

• is stage-less and simple …
• … but most importantly it self-scales to the amount of resources (or work) the node can afford
• trading quality for footprint is automatic (even a tiny node can help, perhaps just a little bit)

**comparison** TARP versus Zigbee

Zigbee

• ZigBee purports to provide a complete solution to your connectivity problems
• It tries to impose on us ready network-layer paradigms for implementing operations as delicate as forwarding within unknown networks catering to unknown applications

TARP is a component of a holistic platform; its premises are:

• wireless is not wired
• nodes are only a bunch of cogs in the complete system
• nodes can only have a vague idea of what is expected from them; they are not in charge!
• nodes are inherently unreliable, wireless is inherently unreliable; so TARP is more robust in that it expects the worse from nodes and designs protocol that takes failure into account