## 2 Distributed Fair Rate Allocation Algorithm
### Proposed Algorithm
#### 2.4.4 Dual Projection
An example can be found in Figure 5, where we assume that the selected value from \(\mathcal{A}_{1}^{k}\) is \(\hat{\lambda}_{5}^{k}\) and that the selected value from \(\mathcal{A}_{3}^{k}\) is \(\hat{\lambda}_{8}^{k}\). Therefore, we take into account only rows 5 and 8 of \(\mathbf{A}^{T}\) in order to obtain \(\mathbf{B}_{D}^{k}\). Furthermore, since channel 2 is not congested (that's why we have not defined \(\mathcal{A}_{2}^{k}\)), we already know that \(\mu_{2}^{k+1}=0\). Consequently, we also discard the second column of \(\mathbf{A}^{T}\). The resulting linear system of equations is determined and allows us to obtain \(\mu_{1}^{k+1}=\mu_{1,D}^{k+1}\) and \(\mu_{3}^{k+1}=\mu_{2,D}^{k+1}\). However, we want \(\mathbf{\mu}^{k+1}\) to verify Equation (12) and thus, we propose next a distributed approach to compute \(\mathbf{\mu}^{k+1}\) and \(\mathbf{\lambda}^{k+1}\) in a cluster-tree WSN. Our mechanism solves \(\mathbf{\lambda}_{D}^{k}=\mathbf{B}_{D}^{k}\mathbf{\mu}_{D}^{k+1}\) if \(\mathbf{\mu}_{D}^{k+1}\succeq\mathbf{0}\) and finds an alternative positive solution otherwise, which guarantees the convergence of the method (see Section 2.8). Note that, due to the specific structure of \(\mathbf{A}^{T}\) and also of \(\mathbf{B}_{D}^{k}\), we can apply some sort of Gauss elimination as discussed next. The proposed solution has two phases. The first phase begins at the lowest levels of the cluster-tree and each node sends its current value of \(\hat{\lambda}_{j}^{k}\) to its parent. The parent, in turn, first checks if the channel with its child nodes is congested. If true, it sends its own value of \(\hat{\lambda}_{j}^{k}\). If false, it takes the values from the child nodes and also its own value and selects one candidate according to (SR1)-(SR2). This is the value that is sent to the parent in this second case. This process is successively applied until the sink node is reached. Thereafter, the second phase begins. The sink node checks if it attains its own rate constraint. If true, it selects one value taking into account (SR1)-(SR2), fixes \(\mu_{1}\) to that value and sends it to its child nodes. If false, it fixes \(\mu_{1}=0\) and sends it. When the child nodes receive that value, say \(v_{i}\), select one \(\hat{\lambda}_{j}^{k}\) among its gathered values using again (SR1)-(SR2) and compute \(\mu_{i}\) (the dual multiplier associated with its rate constraint) as \(\mu_{i}=\hat{\lambda}_{j}^{k}-v_{i}\). If the resulting \(\mu_{i}\geq 0\), the parent node sends \(\hat{\lambda}_{j}^{k}\) to its child nodes; if \(\mu_{i}<0\) or if the channel between the node and its children is not congested, the parent fixes \(\mu_{i}=0\) and sends the received \(v_{i}\) to its child nodes. This process is repeated until all the values in \(\mathbf{\mu}^{k+1}\) are updated. Note that, as a result of the proposed distributed dual projection, each parent node only knows one value in \(\mathbf{\mu}^{k+1}\) but each node receives its own \(\lambda_{j}^{k+1}\) so that the next iteration of the method can begin. Finally, we have to decide when to stop the iterations of the CDM, that is, when the current solution is close enough to the optimum. One possibility is to monitor the distance between \(\mathbf{y}^{k}\) and \(\hat{\mathbf{y}}^{k}\) and to stop when the relative distance between both quantities drops below a predefined value \(\epsilon\), that is, when  
\[\frac{||\mathbf{y}^{k}-\hat{\mathbf{y}}^{k}||^{2}}{||\hat{\mathbf{y}}^{k}||^{2}}<\epsilon \tag{20}\]  
Figure 5: Dual projection example. The reduced system of equations \(\mathbf{\lambda}_{D}^{k}=\mathbf{B}_{D}^{k}\mathbf{\mu}_{D}^{k+1}\) is constructed and used in the dual projection to update the non-zero values in \(\mathbf{\mu}^{k+1}\). However, this approach requires some signalling because we do not have all the necessary data available at a single node. An alternative approach with a very reduced signalling, which is preferred, is to compute the same relative distance at the sink node taking into account aggregated rate values of the child nodes.