# Offloaded Computation for QoS Routing in Wireless Sensor Networks
## 4 Proposed Methodology
### Conflict-Free DODAG Construction (Algorithm 2)
* **Output:** A set of conflict-free DODAGs that preserve QoS constraints and allow for consistent routing semantics. This method efficiently avoids the computational cost of evaluating all combinations of path superpositions, which would be necessary for exact optimization. This approach avoids the combinatorial explosion associated with exact path superposition and efficiently produces conflict-free topologies. The first step of this pipeline--feasible path computation--is implemented by Algorithm 1, which explores the network in the reverse direction, from the BR to the source nodes. The output is an array \(P\) where each element \(P[n]\) contains a set of feasible non-dominated paths ending at node \(n\). Initially, a fictive path with zero weight is created for the BR and marked as _not ready_. A main while loop then iterates over all paths and nodes. If a path is not yet ready, its successors are generated by appending one-hop neighbors. Each new path is evaluated for feasibility and dominance; if both conditions are satisfied, it is added to the respective node's path set as a _not ready_ path. Once all of a path's successors are evaluated, it is marked as _ready_, thus preventing redundant checks. **DODAG construction:** Using these feasible paths, Algorithm 2 incrementally builds the DODAG by evaluating paths in increasing order of non-linear length. A path is added only if it introduces no conflicts, as described above. Figure 3 illustrates a typical conflict scenario, where two paths share a node beyond the common prefix, making routing decisions at that node unfeasible. If the constructed DODAG does not cover all feasible nodes, additional DODAGs are created using the same method, restricted to the remaining nodes. Figure 3: Conflict between a candidate path \(P2\) and an existing path \(P1\) in the DODAG. **Redundancy augmentation:** The third step in the pipeline enhances robustness by adding redundant links that support local repair. For each path from a leaf node to the BR, potential alternative parents are evaluated as follows:  
Let \(a\) be a node with rank \(k\) (i.e., \(k\) hops from the BR), and let \(\vec{L_{a}}\) be the cumulative QoS metric vector for the subtree rooted at \(a\). For each adjacent node \(b\) (with rank \(\leq k\)), we compute  
\[\vec{L_{a}}+\vec{L_{a,b}}+\vec{L_{b}}\]  
where \(L_{a,b}^{-}\) is the metric vector on arc \((a,b)\), and \(\vec{L_{b}}\) is the cumulative vector from \(b\) to the BR. If this sum satisfies the global QoS bound \(\vec{L}\), then arc \((a,b)\) is added as an _alternate link_ to support local recovery. The procedure is implemented in Algorithm 3. The first step in the proposed architecture involves the computation of feasible non-dominated paths. Algorithm 1 describes the centralized computation of these paths in the reverse direction: from the sink, i.e., the BR, to all source nodes. This reverse construction is reverted at the end of the computation to match the data-forwarding direction. The algorithm maintains an array \(P\), where \(P[n]\) stores a set of feasible non-dominated paths from the BR to node \(n\). Initially, a fictive zero-cost path consisting of a single node (the BR) is created and marked as _not ready_. The algorithm then iteratively expands each path in \(P\) by appending adjacent edges. Whenever a successor path satisfies all QoS constraints and is non-dominated with respect to existing paths in \(P[n]\), it is stored as a candidate. Each new path is initially marked as _not ready_ to allow for its further expansion in subsequent iterations. Once all possible successors of a path have been evaluated, the path is marked as _ready_ to avoid redundant computation. Based on the set of feasible non-dominated paths, the second step constructs the DODAGs. Computing the optimal DODAG structure--or the minimal number of DODAGs that span all feasible nodes--is known to be NP-hard [59].