# Discrete Data Rate Adaptation for Wireless Body Area Networks
## 4 Optimization Algorithms  
### Algorithmic Background  
The above problem can be considered as a generalization of the knapsack problem (KP), namely, the multiple-choice multidimensional knapsack problem (MMKP). In our problem, variations of data streams are selected whose utilities and data rates correspond to the values and sizes of items, respectively. In the multiple-choice knapsack problem, there are several classes of items, and it is enough to choose only one item from each class. In our case, one variant can be selected for each of the sensor data. The problem is multidimensional as well, because instead of a single knapsack capacity, a series of capacity constraints along the routing path should be satisfied, which form a vector. In our case, the available capacity for a data stream is equal to the minimum capacity of resources along the routing path to the sink, which may be different for different streams. After selecting an item, the available capacity of node and edge resources should be updated along the route.  
Several algorithms have been proposed in the literature [35; 36; 37] to solve the MMKP. They include heuristic methods and an exact branch-and-bound method that is useful for checking the validity of the solutions. [PERSON] et al. [38] applied the MMKP to congestion control, but sensors do not provide data streams in different variants in their model. Multiple choice refers to the selection from several possible streaming routes. [PERSON] et al. [39]  
Figure 2: A sensor (\(v_{i}\)) with its neighbors in the proposed model. \(v_{j}\) represents its outgoing neighbor and \(v_{k}\), \(v_{l}\ldots v_{x}\) represent its incoming neighbors in the routing tree. \(d_{ik}\) represents the data variations that can be generated by sensor \(v_{i}\). Only one of the data variations is transferred. \(C_{i}\) and \(C_{ij}\) denote the capacities of nodes and edges, respectively.  
applied the MMKP for adaptive multimedia systems. This approach proved to be an efficient method to solve problems like quality adaptation, admission control, and integrated resource management. We have selected some solution methods for the knapsack problem to perform data rate adaptation in WBANs. The algorithms run in a centralized manner on the sink node.  
Several algorithms are available to solve knapsack problems, e.g., based on greedy and dynamic programming approaches. The greedy solution of the knapsack problem offers a fast solution approach for data rate adaptation, although it usually fails to find the optimum. The greedy solution algorithm of the KP iteratively selects the item for which the ratio of the value and the size is the highest among the items whose size does not exceed the available space in the knapsack.  
Dynamic programming, introduced by [PERSON] [40], is another widely used solution method for the knapsack problem. This method can be adapted to the multiple-choice knapsack problem (MCKP) as well (see, e.g., [41; 42; 43]). Let \(U(i,k)\) denote the maximum value that can be attained with a weight less than or equal to \(k\) by selecting one item from each class \(S_{l}\), \(S_{2}\), \(\ldots\), \(S_{i}\). The dynamic programming algorithm can be formulated by the following equations:  
\[U(1,k)=max_{j\in S1:r_{ij}\leq k}\ \ u_{1j} \tag{1}\]  
\[U(i,k)=max_{j\in S1:r_{ij}\leq k}\ \left(u_{ij}+U\big{(}i-1,\ k-r_{ij}\big{)}\right) \tag{2}\]  
For the processing the first class, the achievable value is the largest value of the item in the class with weight below the capacity limit (Equation (1)). In the general case described in Equation (2), the partial solutions belonging to \(S_{l}\), \(S_{2}\), \(\ldots\), \(S_{i}\) can be regarded as extensions of partial solutions belonging to \(S_{l}\), \(S_{2}\), \(\ldots\), \(S_{i-1}\). Each \(U(i,k)\) can be calculated by using the recursive formula. After completing the calculations, \(U(n,C)\) contains the optimal value for the problem instance, where \(n\) is the number of classes and \(C\) is the capacity of the knapsack.