## 2 Distributed Fair Rate Allocation Algorithm
### Proposed Algorithm
#### 2.4.2 Primal Projection  
In primal projection, the following optimization problem is solved,  
\[ \begin{array}{ll}\min_{\hat{\mathbf{y}}^{k}}&||(\mathbf{y}^{k}-\hat{\mathbf{y}}^{k})||^ {2}\\ s.t.&[\mathbf{A}]_{j}\hat{\mathbf{y}}^{k}\leq c_{j}\quad\forall j\,|\,\mu_{j}^{k}=0\\ &[\mathbf{A}]_{j}\hat{\mathbf{y}}^{k}=c_{j}\quad\forall j\,|\,\mu_{j}^{k}>0\end{array}  \tag{14}\]  
and we get the modified variables \(\hat{\mathbf{y}}^{k}\) as the optimal solution of Problem (14). As it is discussed in Section 2.8, the algorithm guarantees that Problem (14) has at least one feasible point so that Problem (14) is well-defined. However, we need a distributed solution of the primal projection in order to avoid sending all the information to the sink node and computing Problem (14) there. Fortunately, we can benefit from the tree structure of the network to find the optimal solution of Problem (14) distributedly. Note that in cluster-tree topologies, the subset of nodes associated with the i-th constraint is always a subset of the nodes related to the constraint immediately above \(c_{i}\). See this in the small network example of Figure 3, where  
\[\left[ \begin{array}{c}c_{1}\\ c_{2}\end{array} \right]\succeq\left[ \begin{array}{cccc}1&1&1&1\\ 0&0&1&1\end{array} \right]\left[ \begin{array}{c}\hat{y}_{1}\\ \hat{y}_{2}\\ \hat{y}_{3}\\ \hat{y}_{4}\end{array} \right] \tag{15}\]  
For the sake of brevity, we describe the distributed computation of Problem (14) using the example in Figure 3, which can be easily extended to the general case. Let us assume that \([\mathbf{A}]_{1}\hat{\mathbf{y}}=c_{1}\) (this is usually the case) and \([\mathbf{A}]_{2}\hat{\mathbf{y}}\leq c_{2}\)[31]. For the sake of simplicity, we omit the index \(k\) in this example. As depicted in Figure 3, the idea is to compute the projection at the parent nodes, that is, first the sink allocates \(\hat{y}_{1}\) and \(\hat{y}_{2,ag}\) and thereafter, sensor 2 allocates \(\hat{y}_{2,ag}\) to sensors 3-4 and itself, thus obtaining \(\hat{y}_{2}\), \(\hat{y}_{3}\) and \(\hat{y}_{4}\). On the other hand, the application of the KKT optimality conditions to our simplified problem reveals us that the optimal solution must satisfy  
\[ \begin{array}{rcl}\hat{y}_{j}&=&y_{j}-\mu_{1},\qquad j=1,2\\ \hat{y}_{k}&=&y_{k}-(\mu_{1}+\mu_{2}),\qquad k=3,4\end{array}  \tag{16}\]  
where \(\mu_{1}\in\mathbb{R}\) forces \(\sum_{i}\hat{y}_{i}=c_{1}\) and \(\mu_{2}\in\mathbb{R}^{+}\cup\{0\}\) prevents \(\hat{y}_{3}+\hat{y}_{4}\) from exceeding \(c_{2}\). In other words, \(\mu_{2}\) is bigger than 0 only when the constraint \(\hat{y}_{3}+\hat{y}_{4}\leq c_{2}\) is violated given \(\mu_{1}\). Therefore, there are only two possible projections, that is, either i) \(\hat{y}_{3}+\hat{y}_{4}<c_{2}\) or ii) \(\hat{y}_{3}+\hat{y}_{4}=c_{2}\). Let us consider a virtual sensor 2\({}_{ag}\) that groups sensors 2-4 with \(y_{2,ag}=\sum_{i=2}^{4}y_{i}\) as in Figure 3. In case (i), the projection is straightforwardly computed [18] (Section 8.1.1) as  
\[\hat{\mathbf{y}}_{ag}=\mathbf{y}_{ag}-\frac{(\mathbf{1}^{T}\mathbf{y}_{ag}-c_{1})\mathbf{n}_{ag}} {\mathbf{1}^{T}\mathbf{n}_{ag}} \tag{17}\]  
where \(\hat{\mathbf{y}}_{ag}=[\hat{y}_{1,ag},\hat{y}_{2,ag}]^{T}\) is the aggregated allocation to the virtual sensors, \(\mathbf{y}_{ag}=[y_{1,ag},y_{2,ag}]^{T}\) is their aggregated demand and \(\mathbf{n}_{ag}=[n_{1,ag},n_{2,ag}]^{T}\) is the number of sensors inside each virtual sensor. In our example, \(\mathbf{n}_{ag}=[1,3]^{T}\). However, if (ii) is the case, we allocate \(c_{1}-c_{2}\) to sensors 1-2 similarly as in Equation (17), as well as \(c_{2}\) to sensors 3-4. Finally, we need to distinguish between situations (i) and (ii), which can be done using the following threshold for virtual node 2\({}_{ag}\),  
\[\hat{y}_{2,ag}^{th}=y_{2,ag}-\frac{n_{2,ag}}{n_{2,ag}-1}(y_{2,ag}-y_{2}) \tag{18}\]  
This value is the minimum necessary allocation to virtual node 2\({}_{ag}\) so that the inner rate constraint, _i.e._, \(\hat{y}_{3}+\hat{y}_{4}\leq c_{2}\), is satisfied with equality.