/**
* This file is part of license combination gpl version 3 license and eCos.
* The corresponding license terms are below.
*
* gpl version 3 Licence:
*
* The file were developed during the student thesis "Datensammlung in Wireless
* Sensor Networks fuer Autonomic Home NetworkingÒ of Thomas Kothmayr and is
* included in the dissertation "Secure Data Transmission in Wireless
* Sensor Networks" by Corinna Schmitt during employment at the Technische
* UniversitŠt MŸnchen, Department Computer Science, Chair Network
* Architectures and Services (Germany).
* Copyright (C) 2013
* Authors: Thomas Kothmayr and Corinna Schmitt (schmitt[at]net.in.tum.de)
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 3 of the License
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see
The TreeRoutingEngine is responsible for computing the routes for collection. It builds a set of trees rooted at specific nodes (roots) and maintains these trees using information provided by the link estimator on the quality of one hop links.
Each node is part of only one tree at any given time, but there is no difference from the node's point of view of which tree it is part. In other words, a message is sent towards a root, but which one is not specified. It is assumed that the roots will work together to have all data aggregated later if need be. The tree routing engine's responsibility is for each node to find the path with the least number of transmissions to any one root.
The tree is proactively maintained by periodic beacons sent by each node. These beacons are jittered in time to prevent synchronizations in the network. All nodes maintain the same average beacon sending rate (defined by BEACON_INTERVAL +- 50%). The beacon contains the node's parent, the current hopcount, and the cumulative path quality metric. The metric is defined as the parent's metric plus the bidirectional quality of the link between the current node and its parent. The metric represents the expected number of transmissions along the path to the root, and is 0 by definition at the root.
Every time a node receives an update from a neighbor it records the information if the node is part of the neighbor table. The neighbor table keeps the best candidates for being parents i.e., the nodes with the best path metric. The neighbor table does not store the full path metric, though. It stores the parent's path metric, and the link quality to the parent is only added when the information is needed: (i) when choosing a parent and (ii) when choosing a route. The nodes in the neighbor table are a subset of the nodes in the link estimator table, as a node is not admitted in the neighbor table with an estimate of infinity.
There are two uses for the neighbor table, as mentioned above. The first one is to select a parent. The parent is just the neighbor with the best path metric. It serves to define the node's own path metric and hopcount, and the set of child-parent links is what defines the tree. In a sense the tree is defined to form a coherent propagation substrate for the path metrics. The parent is (re)-selected periodically, immediately before a node sends its own beacon, in the updateRouteTask.
The second use is to actually choose a next hop towards any root at message forwarding time. This need not be the current parent, even though it is currently implemented as such.
The operation of the routing engine has two main tasks and one main event: updateRouteTask is called periodically and chooses a new parent; sendBeaconTask broadcasts the current route information to the neighbors. The main event is the receiving of a neighbor's beacon, which updates the neighbor table.
The interface with the ForwardingEngine occurs through the nextHop() call.
Any node can become a root, and routed messages from a subset of the network will be routed towards it. The RootControl interface allows setting, unsetting, and querying the root state of a node. By convention, when a node is root its hopcount and metric are 0, and the parent is itself. A root always has a valid route, to itself.