Supervisor: Kaisa Sere
Tree Construction - Routing
Download 298.62 Kb.
|
5.3 Tree Construction - RoutingA new tree is created when a node boots and finds that it is not within radio range of any other node. At this point the node will declare itself as root and create a treeID with which the tree is identified when inter-tree routing occurs. Therefore, nodes can detect interlinks when receiving messages containing different treeIDs than their own. The tree will grow as other nodes approach the tree or boot-up near it, depending on the length of the radio range. A new node that is connecting to the tree will choose its shallowest neighbor as its preferred neighbor towards the root. Links that are not preferred by any node are called extralinks and are used in forwarding situations. Over time a tree will be constructed which consists of preferred links and because of the preference of neighbors close to the root, a tree as shallow as possible is constructed. The shallowness in turn, implies that known paths are as short as possible. In figure 5-2 the new nodes are presented in a differing color and extralinks are dashed. When the root is informed by the MAC layer that it has radio contact to node 2, it will send a hello message, containing its status, which is root, treeID and depth. Node 2 sees this as satisfactory and will communicate the fact that it joins the tree, which is registered by root 1 and it then sends an acknowledgement message to node 2. Node 2 receives this and calculates its depth as the parent's depth+1. When node 3 boots and receives the same piece of information and additionally a hello message form node 2, it will decide that its preferred link will be to 1 since it is at depth 0 and node 2 is at depth 1. If a node has two just as deep neighbors like node 4 has, one of the shallowest neighbors can be preferred randomly. 
Fig. 5 16: A growing tree. Thus, after these operations are completed, node 1 will know that its tree consists of nodes 1, 2, 3 and 4, because node 4 informs node 2 of its existence, node 2 will relay this information to node 1. Therefore node 2 knows of child 4, node 3 has no children in its table, but is aware of the extralinks because the MAC-layer keeps it informed about neighbors. The update messages concerning tree members will be sent from any node, when it detects a new child. Thus, the detector initializes the update procedure and sends such a message which accumulates at every node on every level in the tree. This means that every node on the path up from the detector to the root, will detect this change, as they will all receive new updates. Every node adds itself and the updates that were received from each of its children. The updates also contains the neighbors of every node, this is so that extralinks can be detected by a subroot that has to make a forwarding decision (RQM forwarding will be explained in section 5.4). The interlinks provide a way for two trees to communicate. An interlink (Fig.5-3) is set up only if two non-roots in different trees move into radio range of each other. If one of the nodes is a root, it will include its tree with the other tree. This will help to keep the amount of trees low and maximize the knowledge of roots and therefore minimize message complexity when a node needs to be found. If two roots come into the vicinity of each other, the root with higher ID number will include itself with the other root. 
Fig. 5 17: An interlink between two trees. The former paragraph specified how nodes associate themselves with other nodes when joining a tree. Now, we shall see how breakage can occur. When a mobile node is moving away from its neighbors (or powered down), some of the links to them might break. Different types of link breakage can occur in an ad hoc network. The breakage type is defined by the role of the node to which a link breaks and will require different measures. A few examples will make this clear: A node moves around in the tree if its relative speed is higher than others or moving in a opposite direction than others. A node moving towards the root will make its way up the tree levels until it is a level 1 node. When the node has passed the root it might seem that it should become root. This is not the case, because, the tree is only a conceptualization of the physical network. The node will in fact remain a level 1 node, although it is on the opposite side of the root, compared to where it was before. If there are other nodes on this side, the node's level will again increase as it moves away, otherwise it loses contact to the tree. A node moving around in a tree will cause changes in its parent's and children's routing tables. The different changes are explained below with help of figures 5-4 and 5-5. 
Fig. 5 18: A node moves “up”. In figure 5-4 node 5 is moving towards the root and at some point when node 5 is passing node 2, it will receive a hello message from the root, saying that it has a level 0 neighbor (the hello message is sent when the link layer indicates a new neighbor). This will cause node 5 to change its preferred link to the root and become a sibling of node 2 and 5, and generate possible extralinks to these if they exchange hellos. Node 2 will be informed that node 5 is no longer a child of it. The parent has to be explicitly informed of this by means of a un-association message. This is because the MAC layer information does not contain the fact with whom the child is associated. In this particular situation node 5 is still a neighbor of node 2 and the old update message would still be relied on, if the former child does not explicitly delete it. The explicit delete message causes node 2 to remove 5 from its child list and send an update message to the root. If node 5 had any children, the subroot of the children would become root if it does not have any other links than those to its children. If a link is broken before the un-association message arrives at the former parent, it can remove the former child when the MAC layer indicates that. 
Fig. 5 19: A node moves “down”. The situation in figure 5-5 is similar to the one in figure 5-4 where new siblings are formed, but here node 2 is moving in the other direction. Node 2 will become a sibling of 6 and 5, leave its former subtree containing 2, 4 and 5. Subroot 5 will prefer subroot 3 because it is the shallowest of its neighbors. Changes in tree movement can be seen from three perspectives. The moving node that becomes disconnected and will begin taking measures to find a neighbor with the lowest depth and associate with that neighbor, the perspective of the former child, which will use one of the former extralinks or interlinks as the new preferred link. If no such link exists, then it will form a new tree. The third perspective is the perspective of the parent of the moving node. Little has be done by the former parent, it should remove the invalid update when either it receives a hello saying that the parent is no longer preferred or the child moves out of range, which is indicated by the MAC layer. One special breakage situation can occur as the link from level-1 nodes to the root breaks. The root can be seen as a potential single point of failure, warranting a secure scheme to be supported for choosing a new root when it fails. In TRP this is implemented in the following way: When a root is moving away from its children, the first child to detect this will become the root of a new tree (consisting of itself and its subtree). This will only be for a brief moment if the new roots siblings are still in its vicinity. After that the new root can either include itself with the old tree if its former level-1 siblings are still near by. Therefore, every level-1 node will first become root for a while, but since the there is a rule that roots should try to include themselves with other trees, they will do so, except for the last level-1 node to experience breakage to the original root, will remain as root in the new tree. This is due to the fact that a root cannot associate with its children, and the last node to experience breakage has no other neighbors but children. Figure 5-6 shows how root link breakage can occur. 
Fig. 5 20: Change of root. Let us say that node 2 is the first to detect that the root is no longer within its radio range. Node 2 will declare itself as root, but shortly after, include itself with node 3, because of the rule. Node 2's children follow with it. If, in fact, it is the root that is on the move, node 3 will also notice what has happened and do the same except it cannot include itself with 2 or 5 because they are children of 3, consequently it will remain as root. There will not be a great delay before the new root will have the same information as the former root since nodes 2 and 3 had the second most information about the tree. Therefore, when node 2 sends its update to the new root 3, its view of the tree will be complete, eliminating the single point of failure problem. One concern that arose while developing the protocol was that the updates would become excessively large when every node adds itself and its neighbors to the message. If also, many nodes are neighbors, the same nodes will be mentioned several times in the same update. It was clear that a scheme for reducing the size of the updates had to be introduced. To address this problem a scheme proven useful in many protocols was devised in the form of incremental updates. In this way, the updates informing of the following events can be reduced to the size of a hello message: If a node leaves a subtree, only a message indicating this occurrence has to be sent to the root. The message must also include which other nodes (grandchildren of the absent node) are inaccessible. This task is performed by the parent that detects the absence of one of its children, which also informs every node on the path from itself to the root, by sending an incremental update. Another event requiring only an increment is the joining of a new leaf node. In this case the update only contains the leaf node and its neighbors. The incremental update method is not applicable in the following situations: When a subroot associates with a new parent in the tree and its children “follow” (still within radio range) with it. In this case it is clear that the parent might not know about the children of the moving subroot and thus has to be informed about them with the help of a full update. Had the children of the re-associating subroot lost contact with it, an incremental update would have sufficed. Naturally, a full update has to be sent by a level-1 node when it detects a new root since the new root in its former position as a level-1 node, had only information about its subtree. In this case the transmitted full update only affects a very local part of the tree, that is, the bandwidth of the link between root and a level-1 node. There is also another occasion when the full update has to be used and that is when a root includes its tree with another. Here, the whole path from the node with which the former root includes its tree, to the root is affected and a degradation of the available bandwidth might occur. While the updates consume bandwidth they also have positive effects, for one thing they reduce the route discovery delay dramatically. This is especially true as the RQMs travel towards the root, because higher-level nodes have more routing information about the tree. So to give a summarizing generalization of when full updates have to be used, it can be said that these are required whenever a non-leaf node associates with a new parent. This causes the parent to send an update, but its update on the other hand can be incremental in the respect that it sends only an update concerning the new child’s subtree. For example, this happens when a root of a tree associates with another. In this case, the node with whom the root includes its tree will only have to send an incremental update that contains the nodes of the including tree and leave out its other subtrees from the update. Download 298.62 Kb. Share with your friends:
|