## 4 Compressed Sensing Enabled Network Tomography
### Loss Estimation
In order to estimate \(Q_{w_{i}}^{(t)}\), the authors assume that all measurement paths are in the normal quality states and that the number of packets lost on each path, \(L_{w_{i}}^{(t)}\), follows a binomial distribution. Since \(Q_{w_{i}}^{(t)}\) constitute a proportion of total \(L_{w_{i}}^{(t)}\), the conjugate prior distribution of \(Q_{w_{i}}^{(t)}\) corresponds to the beta distribution. When \(L_{w_{i}}^{(t)}\) at a certain time window \(t\) is measured, the posterior distribution of \(Q_{w_{i}}^{(t)}\) can be computed. Then, using the Exponentially Weighted Moving Average (EWMA), \(Q_{w_{i}}^{(t)}\)'s posterior distribution is estimated by the mode in the posterior distribution of \(Q_{w_{i}}^{(t-1)}\). After estimating \(Q_{w_{i}}^{(t)},\forall i\in\{1,...,n\}\), the authors subtract them from the path loss rates \(P_{w_{i}}^{(t)}=\frac{L_{w_{i}}^{(t)}}{N_{pkt}},\forall i\in\{1,...,n\}\), where \(N_{pkt}\) is the number of packets transmitted from the source node to its destination node during time window \(t\). The modified measurement vector, \(\mathbf{Y}^{(t)}\), is set as follows:  
\[Y_{i}^{(t)}= \begin{cases}-\log(1-P_{w_{i}}^{(t)})-(-\log(1-Q_{w_{i}})),&\text {if }P_{w_{i}}^{(t)}-Q_{w_{i}}>T_{p}\\ 0,&\text{otherwise},\end{cases}  \tag{14}\]  
where \(T_{p}\) is a threshold. In order to classify estimated \(\hat{X}_{i}^{(t)}\) as a low or high quality link, the authors compare it to a threshold \(T_{l}^{(t)}\), which is set using [PERSON]'s binarization method [55]. This paper is the first to discuss measurement path construction based on compressed sensing. A Graph Fourier Transform (GFT) based tomography approach for the estimation of packet loss rates at nodes in wireless multihop networks with spatially dependent channels is presented in [56]. The basic idea is similar to the previously described delay tomography method of [48] (see Section 4.1). Namely instead of estimating the node state vector (i.e., the vector whose components are the packet loss rates at the respective nodes) directly, the proposed scheme employs CS to first estimate the GFT of the node state vector (which has a few dominant components due to the spatially dependent channels) and then examines the network internal characteristics in the transformed domain. In [57], the authors propose a scalable (the total number of measurements scales logarithmically with the number of links) adaptive CS based tomographic scheme for fault localization. The proposed approach consists of two stages. First, the network is monitored (with a few tomographic path measurements) for the detection of faults (the initial set of measurements although not sufficient for localizing the faults, it is indicative of their presence). Then, upon detection of one or more faults, the adaptive fault localization stage is initiated, during which further path measurements are iteratively carried out (each adaptive measurement covers a set of links that is identified based on the previous iteration) in order to localize the faults. Three conditions for convergence (termination) and two selection criteria for the adaptive measurements are determined, whereas the performedsimulations demonstrate that the proposed scheme achieves a very high detection rate and a very low false positive rate.