# Offloaded Computation for QoS Routing in Wireless Sensor Networks
## 4 Proposed Methodology
### Conflict-Free DODAG Construction (Algorithm 2)
Existing exact solutions, such as Integer Linear Programming (ILP), require evaluating all possible combinations of path superpositions, which is computationally unfeasible for large networks. The ILP formulation interprets each path as a flow from the BR to a destination, and the optimal hierarchy emerges from the superposition of these flows. To overcome the scalability limitations of such approaches, we propose a greedy and conflict-resilient algorithm (cf. Algorithm 2) to construct one or more conflict-free DODAGs. The stored paths are explored in ascending order of non-linear length--a composite metric reflecting the aggregated QoS cost. Before integrating a candidate path into the DODAG under construction, a conflict check is performed as follows:  
1. A common prefix between the candidate path and the current DODAG is computed, starting from the BR. If no common prefix exists, the prefix is simply \(\{BR\}\). 2. A _conflict_ is detected if the candidate path shares any nodes with the DODAG that lie beyond the common prefix. This structural ambiguity could render routing decisions invalid or contradictory. An example conflict is illustrated in Figure 3. Suppose a path \(P_{2}\) is to be added to a DODAG that already includes path \(P_{1}\). If node \(f\) exists in both paths but is reached via different parent nodes (\(c\) in \(P_{1}\) and \(e\) in \(P_{2}\)), this results in an inconsistency in routing decisions, thereby violating DODAG correctness. The candidate path is added to the DODAG if no conflict is found. The algorithm proceeds iteratively until no further paths can be integrated without conflict. At this point, if feasible nodes remain not yet included in any DODAG, a new DODAG is initialized, and the process repeats. The final result is a set of conflict-free DODAGs covering all feasible nodes. For use in the RPL, the direction of the arcs is reversed. If the computed DODAG(s) do not span all nodes with feasible paths, the greedy algorithm is reapplied to construct additional DODAG(s) from the remaining paths. The third and final step introduces redundancy into the DODAG(s) to support local repair mechanisms. Paths from the leaves to the BR are examined to identify alternate parent links. Let \(a\) be a node on such a path with rank \(k\) (i.e., hop distance from the BR), and let \(\vec{L_{a}}\) be the maximum vector of QoS metrics from the leaves up to \(a\) in its subtree. Consider an adjacent node \(b\) with rank \(\leq k\) that is reachable via a different path. Denote the QoS metric vectors along edge \((a,b)\) and from \(b\) to the BR as \(L_{a,b}^{\rightarrow}\) and \(\vec{L_{b}}\), respectively. If the total cost \(\vec{L_{a}}+\vec{L_{a,b}}+\vec{L_{b}}\leq\vec{L}\) (where \(\vec{L}\) denotes the end-to-end QoS threshold), then \((a,b)\) is considered a valid backup link and is added as an alternative arc. This process is formalized in Algorithm 3. ```
1:Topology graph \(G=(V,E)\);
2:a constructed DODAG \(D=(V_{D},E_{D})\);
3:maximum allowable QoS vector \(\vec{L}\)
4:Modified DODAG \(D\) with additional redundant links
5:for all\(a\in V_{D}\)do\(\triangleright\) For each node already covered in the DODAG
6:\(Adj\leftarrow\) adjacentNodes\((a)\)
7:for all\(b\in Adj\)do
8:if\(b\in V_{D}\)and\(\text{rank}(a)\geq\text{rank}(b)\)then
9: Compute \(\vec{L_{a}}\leftarrow\) max QoS from leaves to \(a\) in subtree
10: Compute \(\vec{L_{a,b}}\leftarrow\) QoS on link \((a,b)\)
11: Compute \(\vec{L_{b}}\leftarrow\) QoS from \(b\) to BR in \(D\)
12:if\(\vec{L_{a}}+\vec{L_{a,b}}+\vec{L_{b}}\leq\vec{L}\)then
13:\(E_{D}\gets E_{D}\cup\{(a,b)\}\)\(\triangleright\) Add alternative parent link
14:endif
15:endif
16:endfor
17:endfor
18:endfor
19:return\(D\)
```  
**Algorithm 3** Add Redundant Links to a DODAG