## 2 Distributed Fair Rate Allocation Algorithm
### Convergence to the Optimal Rate Allocation
Application to Cluster-Tree Wireless Sensor Networks  
The algorithm developed in the previous section can be applied to cluster-tree WSNs with the aim of providing global fair resource allocations with a reduced impact in terms of energy consumption due to signalling. In this work, in particular, we focus on the beacon-enabled mode of IEEE 802.15.4 [1]. This mode divides the transmission through time slots and, besides, two periods are defined depending on the kind of access used by the nodes in the network: contention access period (CAP), where slotted CSMA/CA is adopted, and contention-free period (CFP), where GTS slots are distributed to the nodes (see Figure 8). Since time slots can have different sizes from one cluster to another, we distribute resources in terms of rate, _i.e._, \(r_{j}\) is the rate allocated to the j-th sensor. Thereafter, we use these rates to derive the time slot allocation. Note that depending on each specific Superframe (SF) configuration, the maximum transmission rate in each cluster changes. Furthermore, we will also take into account the quality of the radio links by means of the Packet Delivery Ratio (PDR), that is, \(PDR_{j}\) is the ratio between correctly received packets and sent packets at the j-th sensor. As previously commented, beacon collision problems can appear in a cluster-tree WSN based on the beacon enabled mode. For that reason, we take into account a beacon collision mechanism. In particular, we consider the time-division approach adopted by the Zigbee specification [9], _i.e._, time is divided in such a way that the beacon frame of each coordinator is sent during the inactive periods of the rest of coordinators (see Figure 9). Figure 8: Beacon frame configuration adopted by the IEEE 802.15.4 standard [1]. Figure 9: Beacon frame collision avoidance based on the time division approach adopted by the Zigbee specification [9]. Given the sensor demands in \(\mathbf{M}=[M_{1},\ldots,M_{N}]^{T}\) and the minimum guaranteed allocation in \(\mathbf{m}=[m_{1},\ldots,m_{N}]^{T}\) (both in terms of rate), the optimum allocation is computed by solving the following optimization problem using the CDM,  
\[\max_{\{r_{j}\}} \sum_{j=1}^{N}U_{j}(r_{j}\cdot PDR_{j};w_{j},\gamma)\] \[s.t. m_{j}\leq r_{j}\leq M_{j}, j=1,\ldots,N \tag{27}\] \[\sum_{j\in\mathcal{A}_{m}^{k}}\hat{y}_{j}^{k}=\sum_{j\in\mathcal{A}_{m}^{k}}y_ {j}^{*} \tag{22}\]0  
where the priority values \(w_{j}\) allow us to balance the allocation towards some sensors in the network and \(\gamma\) fixes the degree of fairness as discussed in Equation (2). Moreover, the radio link qualities are also considered as far a \(r_{j}\cdot PDR_{j}\) is the effective data rate assigned to the j-th user. In particular, note that when \(U_{j}(r_{j})=w_{j}\log(r_{j}\cdot PDR_{j})\) the resulting allocation is insensitive to \(PDR_{j}\) because \(U_{j}(r_{j}\cdot PDR_{j})=w_{j}[\log(PDR_{j})+\log(r_{j})]\) and thus, proportional fairness does not benefit sensors with bad channel condition. If we fix \(\gamma>1\) instead, the resulting allocation is balanced towards the bad sensors. Note that in the limit, _i.e._, with \(\gamma\rightarrow\infty\), max-min fairness does not admit low effective data rates even if this implies a significant reduction in terms of the network throughput. Once the optimal allocation is obtained, it has to be mapped onto a time slot assignment. Since the WSN scenario can be assumed quasi-static in most of the real-life applications, it is reasonable to sustain an allocation for a given number of Beacon Intervals (BI), say \(nBI\). Therefore, the real-valued number of time slots assigned to the j-th sensor on the \(nBI\) periods is  
\[\sum_{j\in\mathcal{A}_{m}^{k}}\hat{y}_{j}^{k}=\sum_{j\in\mathcal{A}_{m}^{k}}y_ {j}^{*} \tag{22}\]1  
where \(r_{j}^{\prime}\) is the rate across the j-th sensor, that is, its own rate plus the rate of all the nodes below it. Furthermore, \(T_{BI}\) is the BI duration and \(b_{j}\) is the packet size in bits at the j-th sensor.