# Offloaded Computation for QoS Routing in Wireless Sensor Networks
## 4 Proposed Methodology
### Conflict-Free DODAG Construction (Algorithm 2)  
The computation of optimal DODAGs is a well-known NP-hard problem. Although exact solutions based on Integer Linear Programming (ILP) have been proposed [59], they are computationally prohibitive due to the exponential number of feasible path combinations. In such formulations, routing is modeled as a directed flow from the BR to each destination node, where each flow corresponds to a valid path. The superposition of these flows yields the optimal hierarchical structure. However, computing the exact solution is often unfeasible in practical deployments. Therefore, our work adopts a greedy conflict-avoidant strategy aimed at constructing efficient and structurally consistent DODAGs that meet QoS requirements while avoiding the computational overhead of exhaustive search. ```
0: Set of feasible and non-dominated paths \(P[n]\) from Algorithm 1 for all \(n\in V\)
0: Set of conflict-free DODAGs \(\mathcal{D}=\{D_{1},D_{2},\dots\}\)
1: Initialize \(\mathcal{D}\leftarrow\emptyset\)\(\triangleright\) Set of constructed DODAGs
2: Let \(U\leftarrow\{n\in V\setminus\{BR\}\mid P[n]\
eq\mathcal{O}\}\)\(\triangleright\) Unintegrated nodes with feasible paths
3:while\(U\
eq\emptyset\)do
4: Initialize a new DODAG \(D\leftarrow\emptyset\)
5:\(integrated\leftarrow\)false
6:while true do
7:\(selected\leftarrow\)null
8:\(minCost\leftarrow\infty\)
9:for all\(n\in U\)do
10:for all\(path\in P[n]\)do
11:if\(conflicts(path,D)=false\)and\(cost(path)<minCost\)then
12:\(selected\gets path\)
13:\(minCost\gets cost(path)\)
14:endif
15:endfor
16:endfor
17:if\(selected=\)nullthen
18:break\(\triangleright\) No more conflict-free paths can be added
19:else
20: Add selected to \(D\)
21: Remove destination node of \(selected\) from \(U\)
22:\(integrated\leftarrow\)true
23:endif
24:endwhile
25:if\(integrated=true\)then
26: Add \(D\) to \(\mathcal{D}\)
27:endif
28:endwhilereturn\(\mathcal{D}\)
```  
**Algorithm 2** Conflict-Free DODAG Construction  
To structure the offloaded computation, three categories of paths are distinguished:  
* _Feasible paths_: those satisfying all end-to-end QoS constraints. * _Dominated paths_: Pareto-dominated by other feasible paths. * _Ready paths_: those for which no feasible successors can be obtained by adding adjacent edges. The offloaded computation proceeds in three stages:
1. Computation of _feasible and non-dominated_ paths that meet the QoS constraints. 2. _DODAG construction:_ Construction of one or more DODAGs from the selected paths. 3. _Redundancy augmentation:_ Addition of redundant links to enhance robustness and support local repair. After computing all feasible and non-dominated paths using Algorithm 1, the second stage involves organizing these paths into valid DODAGs. This is non-trivial because multiple paths may conflict structurally when forming a shared hierarchy. Algorithm 2 constructs DODAGs using a greedy conflict-avoidance strategy to address this. The process follows these key steps:  
* **Initialization:** Identify all nodes with at least one feasible QoS-compliant path. These nodes are candidates for DODAG construction. Begin with an empty DODAG set. * **Greedy Path Selection:** For each candidate node, select the path with the shortest non-linear length (a cumulative cost over multiple QoS metrics). **Conflict Detection:** Before integrating a path into the DODAG, verify its structural compatibility:  
* Compute the _common prefix_ between the candidate path and the current DODAG, starting from the BR. * A _conflict_ is detected if the candidate path shares a node with the DODAG _outside_ of this common prefix, which may lead to ambiguous routing decisions. * **Path Integration:** If no conflict is detected, the path is added to the DODAG, and the corresponding node is marked as integrated. * **Iteration and Expansion:** Repeat the process until no additional non-conflicting paths remain. If any feasible nodes are still unintegrated, initiate a new DODAG and repeat.