# Discrete Data Rate Adaptation for Wireless Body Area Networks
## 4 Optimization Algorithms
### Dynamic Programming  
We could not directly apply the dynamic programming solution for the multiple-choice knapsack problem to the sensor data rate adaptation. The problem of rate adaptation is more complex than the MCKP because it contains not a single capacity but multiple capacities. We applied the dynamic programming method to our problem in the following way. We defined an MCKP instance for each node of the routing tree, where the problem inputs include the possible variations of the data streams coming to the node. The possible variations of the data stream can be determined from the output of the problem instance at the source node of the incoming edge. For this reason, the optimal data rate adaptation can be found by solving a series of MCKP instances while traversing the routing tree. The output of the MCKP is usually one solution with the highest value under the given capacity constraint (\(U(n,C)\)). We extend the output at the nodes to a list of the highest values for all capacity values in the array at class \(S_{n}\) (\(U(n,k)\), \(0\leq k\leq C\)). At the leaves of the tree, the problem is simplified to the special case when there is only one class. This case can be solved by simply omitting the items with larger weights than the current capacity of the leaf. For the other nodes, the streams through the incoming edges should be optimized by considering the capacity of the node. This can also be considered an MCKP instance in the following way. Each incoming stream can be considered as a class, where the items are the optimal solution belonging to the different resource constraints. These items are stored in the output of the MCKP solved at the source node of the incoming edge of the stream. For this reason, the sensor data rate values can be found by recursively solving MCKP instances starting from the sink of the WBAN. After solving the knapsack problem for all vertices, the utility of the proposed solution can be found in \(U_{s}(m_{s}C_{s})\) of the dynamic programming solution at the sink, where \(C_{s}\) denotes the available capacity at the sink and \(m_{s}\) is the number of incoming edges at the sink. Algorithm 2 provides the pseudocode for the dynamic programming on the routing tree. See Figure 4 for the flow chart of the algorithm. Figure 3: Flowchart of the greedy method. The algorithm calls the \(DP()\) function in Line 13, which is a dynamic programming method to solve the MCKP. See [43] for an example of the implementation of the algorithm. The input parameters of \(DP()\) include the list of classes \(S_{l}\), \(S_{2}\),..., \(S_{n}\), where each class contains items with weights and values and the size of the knapsack \(C\). The algorithm adapted to our problem returns a list of value and weight pairs. ```
1 input: node \(n\)
2 output:\(L\): list of the possible data variations that can be transmitted by node \(n\) if \(n\) is not the sink
3 max: the maximum utility if \(n\) is the sink
4 if\(n\) is a leaf of the routing tree \(G_{r}(V,E_{r})\)
5 Create an empty list \(L\)
6 Calculate the minimum available capacity (\(C_{i}\)) along the route \(R_{i}\) from node \(v_{i}\) to the sink in the routing tree \(G_{r}(V,E_{r})\)
7 foreach variant \(d_{ui}\) in the set of possible data variations \(D_{u}\)
8 if\(r(d_{ui})\leq C_{i}\)
9 add\(d_{ui}\) to \(L\)
10 return\(L\)
11 else
12 foreach node \(j\) where \(e_{ij}\in E_{r}\)
13\(Lj\): = call Transverse()
14\(L\) = call DP([Lj: \(e_{ij}\in E_{r}\)], \(C_{i}\))
15 if\(n\) is not the sink
16 return\(L\)
17 else
18\(max:=0\)
19 forach variant \(d_{i}\) in list \(L\)
20 if\(r(d_{i})\leq C_{i}\)
21 if\(u(d_{i})>max\)
22\(max=u(d_{i})\)
23 return\(max\)
```  
**Algorithm 2**Dynamic programming on the routing tree (Traverse)  
The method runs a dynamic programming solution algorithm of the MCKP for each node of the routing tree. The time complexity of the algorithm for the MCKP is \(O(n_{i}\cdot C_{i}\cdot max_{v})\), where \(n_{i}\) and \(C_{i}\) denote the number of incoming edges and the capacity at node \(v_{i}\).