# A Power Planning Algorithm Based on RPL for AMI Wireless Sensor Networks
## 4 DODAG-Oriented Power Planning Algorithm  
The proposed power-planning algorithm is designed to be executed offline. An optimal solution to the power assignment in RPL-based networks depends on the objective function. Having multiple parents is a key concept for RPL. A lot of effort is spent to build the DODAG, so it must be as stable as possible. The path cost to the root is another key concept. A lower path cost may be achieved by increasing the transmission power, which also decreases the average rank of the nodes. However, increasing transmission power also increases interference and may unnecessarily decrease the network performance due to excessive contention. In order to address the number of parents and the path cost issues simultaneously, and propose a solution that is traffic independent, we have designed an algorithm that targets the following property: \"find the minimal transmission power configuration that permits to build a DODAG where each node has at least \(k\) parents accessible with link quality \(ETX\leq Q\)\". Finding the optimal solution for DODAG-based power assignment is equivalent to solving the NP-hard problem of power level assignment [14; 15], as discussed in the introductory section. Therefore, we adopt a heuristic approach that is based on the logic of the RPL protocol. The following statements are important to understand the heuristics used to design the algorithm:  
1. The algorithm assumes that RPL will use the minimum rank with hysteresis objective function (MRHOF) with non-greedy approach [13], i.e., nodes will ignore parent offers from nodes with rank equal or higher than its current rank. 2. When computing the parent set size of a node, the algorithm will consider only parents with very similar path costs, or more precisely, parents that result in the same rank for the node. 3. The power of a node is increased only to the point that it achieves the minimum required number of parents or it can transmit directly to the root. The first statement is a design choice. Because we are adjusting the transmission power to permit a certain number of parents accessible through links with controlled quality, a node does not need to decrease its rank to accommodate bad positioned parents. This is the non-greedy behavior, one of the solutions recommended to prevent loops [1]. According to RPL, the rank advertised by a node is strongly dependent on the worst element in the parent set [13]. This approach may mask the actual path cost if the elements of the parent set are too diverse. Therefore, it may lead to sub-optimal choice of routes, which is one of most severe critiques addressed regarding RPL. The second statement is a design choice that minimizes the selection of sub-optimal routes. It requires that parents who induce a higher rank be removed from the parent set, when the algorithm finds a parent that reduces the the rank of the node. Therefore, increasing the power of a node does not necessarily increase the number of parents. The third statement is a direct consequence of this condition. Please refer to Table 1 for a description of the symbols used in the remainder of this section. To perform the power adjustment, the algorithm defines two important metrics related to the DODAG: the path cost from node \(n\) to the root through parent \(i\):  
\[\text{cost}(n,i)=r_{i}+m*etx_{n,i} \tag{4}\]  
and the calculated rank of node \(n\) through parent \(i\):  
\[\text{rank}(n,i)=r_{i}+\text{Floor}(1+m*etx_{n,i}/h)*h, \tag{5}\]  
where \(r_{i}\), represents the absolute rank of the node, and \(etx_{n,i}\) is the ETX of the link between nodes \(n\) and \(i\). The Floor operation and the parameters \(h\) and \(m\) are defined in RPL to represent the rank and ETX by unsigned integer values with 16 bits. The default value of \(h\) is 256 while the default value of \(m\) is 128. Please note that Equation (5) is not the equation defined in [13] to compute the rank of node \(n\), which is computed considering all nodes in the parent set.