## 3 Efficient Multi-Parent Hierarchical Routing Protocol  
We have proposed a routing protocol that creates a logical hierarchical network topology, where the node hierarchy is given by its location level in the hierarchy (the lower the level, the lower the hierarchy) [13]; basically, the root hierarchy (coordinator node) will have the highest hierarchy. When a node is in a specific hierarchical level (or generation), the nodes that are connected to it and have a higher hierarchical level are parent nodes. On the other hand, nodes that are connected to any parent node and have a lower hierarchical level are child nodes. Thus, we named our proposal the multi-parent hierarchical (MPH) protocol. The hierarchical topology will be formed with routes that minimize the number of hops from a given node to the coordinator; this restriction will reduce the overall energy consumption of the network. The MPH routing protocol allows a child node to have one or more parents. As a result, a node can share both children and parents with another node belonging to the same hierarchical level or generation. The coordinator might also send packets to nodes in the network. We adopt a source-routing approach for traffic to be sent from the coordinator to a node, because the coordinator node has more resources and capacity than the rest of the nodes. This means that it can easily gather information from the network, such as data generated by sensors, links quality metrics, neighborhood tables and other variables, that can be used for route finding, performance analysis and network optimization. MPH protocol operates as a hierarchical tree: the nodes establish parent and child links that constitute the possible routes. Node hierarchies are used to establish parent-child links based on radio coverage. The coordinator node is the root node, and all nodes send information to that destination. If a node wants to send a packet to the destination node, it looks for its parents in its neighbor table, chooses a parent and sends the packet. This process is repeated until the packet reaches its final destination. The coordinator node knows the entire network topology through inquiry packets that it sends from time to time. They are passed through the hierarchical branches and, in their way, ask each node to send its information to the coordinator node. Thus, the coordinator node has valuable information of all nodes of the network, such as statistics, position, routing tables, and so on. The MPH protocol has the advantage of rapid self-configuring links under node connections and disconnections. The node hierarchies are updated based on the highest hierarchy among directly-connected neighbors reestablishing parent-child relationships. Thus, MPH presents some mechanisms aimed at optimizing the communications among nodes and the coordinator: (1) The neighbor table maintaining process is originated by a \(ND\)(Neighbor Discovery) packet transmission. The sending and receiving nodes can update their neighbor tables with the other node address, once each node receives the corresponding acknowledgment. \(ND\) packets are delivered at regular specified intervals, so that nodes rediscover their neighbors at these intervals. The response to a \(ND\) packet is called \(NDR\)(Neighbor Discovery Response) and the response to a \(NDR\) packet is another packet, called \(NDRACK\) (Neighbor Discovery Response ACK). Both the \(NDR\) and \(NDRACK\) packets contain node hierarchy information; (2) Each time a node is involved in a neighbor table maintenance process, it should check if it is going to maintain or change its hierarchy. The rule is that the node selects as parents the set of neighbor nodes with the highest hierarchy among the registered nodes in its neighbor table and assigns itself a hierarchy that is one unit lower than his parent node(s). If a node has no neighbors or all neighbors have zero hierarchy, it will have zero hierarchy, too.