# A Power Planning Algorithm Based on RPL for AMI Wireless Sensor Networks
## 2 Problem Statement  
During the formation of DODAG, each node should select a set of nodes eligible as parents (the parent set), select its preferred parent, as well as calculate and propagate its rank. A node takes these decisions each time it receives an offer of a path to the root node (a DIO message). The candidate nodes to be included in the parent set are those from which a node receives a DIO message with a value of rank that is lower or equal than the current rank of the node. The cost of the path to the root through a node in the parent set is calculated by adding the rank of that node with the cost of the corresponding link. The preferred parent is the one whose path cost to the root is the lowest.  
RPL specifies the ETX as the metric for the objective function when the quality of the link is critical [13]. However, RPL does not define any protocol to measure ETX. A common approach is to use information from the MAC layer, but the estimation of ETX based on MAC layer information can only be done when unicast data traffic is sent through the links. Because RPL builds the DODAG using multicast control messages, it is forced to build DODAG based on predefined initial values for the ETX. All evaluations of RPL in Contiki referred in this paper start measuring ETX only when the unicast data traffic is actually transmitted. Figure 1 shows an example of a DODAG rooted in node 1, with the values for ETX presented beside the links. If the initial values are optimistic as in Figure 1B, the preferred route for node 5 would be (5,4,1) through bad quality links. This bad choice is only fixed when nodes start sending data and the actual values are computed. In this case, a node tends to keep changing parents until all nodes in the parent set are evaluated and receive a more realistic ETX. If initialization values are pessimistic as in Figure 1C, the rank of every node in the DODAG will be overrated, resulting in suboptimal routing. In this case, a node tends to keep using the first chosen parent, once the actual value for ETX is lower than initialization. Indeed, some performance studies have pointed out that RPL may suffer from unreliability problems as it may select suboptimal paths with highly unreliable links [2; 3], incurring a high likelihood of a DODAG fragmentation [6]. In Section 3, we propose a theoretical model which gives an initial estimate for the value of ETX.  
Adjusting the transmission power control can produce DODAGs that are more robust, avoiding disruption and reconfiguration. This is important because reconfiguration is costly in terms of the transmission of control messages and packet loss. Figure 2A shows a part of a DODAG in which all nodes are configured to the same transmission power. Each of the nodes a, b, and c have two members in their parent sets, while d only has one. If node b fails or links (d, b) degrades, the sub-tree below node d is compromised, forcing the protocol to reconfigure the DODAG. In this case, it would be helpful to make a power setting to node c to include the d node in its transmission range, as shown in Figure 2B. Usually, link failures do not trigger global network re-optimization; however, repairs may be very costly when a node detects that its parent set is empty. Once detected, the connectivity failures may cause local (and possibly global) repairs, causing data loss and delivery delays that are incompatible with the AMI requirements. In Section 4, we present a power scheduling algorithm that is capable of inducing RPL to build a DODAG with a number of parents very close to the planned quantity.  
Figure 1: Initialization of expected transmission count (ETX) metric.