## 4 Compressed Sensing Enabled Network Tomography
### Delay Estimation
This method employs a single transceiver node that transmits probe packets along different predetermined paths and receives them after they traverse back from the network. In greater detail, there are the following two types of paths over which packet traveling time (PTT) measurements are made: fully loop paths (LPs) with nodes that do not appear more than once except for the transceiver and folded paths (FPs) with all nodes appearing twice except for the destination. The objective is the identification of a limited number of bottleneck links, whereas small link delays are approximated as zero. Therefore, compressed sensing based on \(\ell_{1}-\ell_{2}\) minimization is utilized. The routing matrix construction (i.e., the selection of measurement paths) is done in two steps. First, the set of measurement path candidates is constructed by connecting the node-disjoint paths and respective reverse paths from the transceiver \(s\) to every other node \(v\in V\setminus\{s\}\). We note that the set of node-disjoint paths from \(s\) to \(v\) signifies the shortest combination of paths among which no nodes are shared. Then, from this set of candidates, the path with the minimum cost (or the shortest path in case of a tie) is iteratively selected until the mutual coherence of the constructed routing matrix becomes less than one. The aforementioned cost is calculated based on the number of unused links in the path under examination. Another method for removing the clock synchronization requirement is presented in [47] and involves the construction of the differential routing matrix, which preserves the 1-identifiability property of the original routing matrix, by selecting a path between the source and receiver measurements nodes as the reference path. More precisely, when the measured path delays are contaminated with synchronization errors, the measurement vector is defined as \(\mathbf{Z}=\mathbf{Y}+\mathbf{\Delta}=\mathbf{A}\mathbf{X}\), where \(\mathbf{\Delta}=[\delta_{1},\delta_{2},\ldots,\delta_{m}]^{\intercal}\) is the synchronization error vector and \(m\) is the number of paths between measurement nodes \(s\) and \(d\). By defining the \(n\)-th component of \(\mathbf{Z}\) as the reference component and the \(n\)-th row of \(\mathbf{A}\) as the reference row and by subtracting them from all other components and rows, the following new equation is formed: \(\mathbf{Z}^{(n)}=\mathbf{A}^{(n)}\mathbf{X}\), where \(\mathbf{Z}^{(n)}\) is the differential measurement vector and \(\mathbf{A}^{(n)}\) the differential routing matrix. Although \(\mathbf{Z}^{(n)}\) still contains some synchronization errors, if \(\left|y_{i}-y_{n}\right|\gg\left|\delta_{i}-\delta_{n}\right|\) with \(i=1,2,...,m\) and \(i\
eq n\), then \(\mathbf{Z}^{(n)}\approx\mathbf{Y}^{(n)}\). In spite of the loss of an equation, given that the goal is the identification of a limited number of bottleneck links with large delays, \(\ell_{1}-\ell_{2}\) optimization based compressed sensing is utilized to obtain a unique solution from the under-determined linear system. In [48], a different approach on link delay inference at mobile networks is proposed. In order to apply compressed sensing, the authors ensure sparsity of vector \(\mathbf{X}\) by applying Graph Fourier Transform (GFT) at base stations' delays that are assumed to be spatially dependent (the GFT \(f\) will be sparse if \(\mathbf{X}\) is spatially dependent), while servers' delays are assumed to be sparse and delays at core routers are assumed to be negligibly small. This way, elements with different characteristics can be estimated in the same framework. All previously presented methods based on compressed sensing realized active measurements, whereas the current one employs a _crowd-sourcing_ approach, which is considered as a kind of passive measurement method. More specifically, according to this approach voluntary mobile users implement a measurement tool in their terminals.