## 4 Compressed Sensing Enabled Network Tomography
### Delay Estimation
When mobile users connect to servers (e.g., Web servers), RTTs (Round Trip Times) are measured and reported to a data collection center. Although the crowd-sourcing approach has several issues such as privacy protection, it is promising because no measurement nodes need to be deployed. Each path of the given network can be identified by a pair of a base station and a server, so measurements referring to such a path are given by the following equation:  
\[\mathbf{Z}=\mathbf{R_{B}}\mathbf{X}+\mathbf{R_{S}}\mathbf{Y}, \tag{8}\]  
where \(R_{B}\in\{0,1\}^{M\times N_{B}}\), \(R_{S}\in\{0,1\}^{M\times N_{S}}\) and where \(N_{B}\) and \(N_{S}\) are the number of base stations and servers, respectively. The rank of \(\mathbf{R}=\mathbf{(R_{B}}\mathbf{R_{S}})\) is proven to be strictly less than \(N_{B}+N_{S}\), \(\forall M\in\{1,2,...,N_{B}N_{S}\}\), so even if all possible paths are used, \(\mathbf{X}\) and \(\mathbf{Y}\) cannot be uniquely determined by Equation (8). Therefore, the GFT of \(\mathbf{X}\) is calculated and approximated by a sparse vector. In [49], the authors address the _dynamic network tomography problem_ by extending the work of [50] to link delay estimation with dynamic link operations. In order to use the concept of compressed sensing, the authors, unlike all previously mentioned works, use a _hub_ set to measure the links with \"small\" delays--the remaining links. The set of remaining links is selected randomly in order to ensure that the measurement matrix satisfies the _restricted isometry property_ (RIP) that characterizes matrices which are nearly orthonormal, at least when operating on sparse vectors. Then, they adopt a _line graph model_ and use the vertices of a _connected dominated set_ (CDS--a set of vertices \(\mathcal{C}\) of the line graph \(\mathcal{L}_{\mathcal{G}}\) of graph \(\mathcal{G}\), such that every vertex in \(\mathcal{L}_{\mathcal{G}}\) either belongs to \(\mathcal{C}\) or is adjacent to a vertex in \(\mathcal{C}\), and \(\mathcal{C}\) is connected) on that line graph model as the _hub_ vertices that will be used for recovering the states of all others. A line graph model \(\mathcal{L}_{\mathcal{G}}=(\mathcal{V}_{\mathcal{L}},\mathcal{E}_{\mathcal{L}})\) refers to a model where every vertex in \(\mathcal{L}_{\mathcal{G}}\) corresponds to a link in \(\mathcal{G}\), i.e., \(\mathcal{V}_{\mathcal{L}}=\mathcal{E}\) and two vertices are adjacent in \(\mathcal{L}_{\mathcal{G}}\) if and only if their corresponding links in \(\mathcal{G}\) are incident, i.e., they share a common end vertex. By assuming that a vertex subset \(\mathcal{V}^{\prime}\) of a graph \(\mathcal{G}\) can be measured together in one measurement if and only if the subgraph induced by \(\mathcal{V}^{\prime}\) is connected and that the measurement is an additive sum of values at the corresponding vertices, then in a graph, a maximal independent set \(\mathfrak{S}\) (i.e., a set of vertices for which no pair of vertices are adjacent to each other and which is not a subset of any other set with the same property) is also a dominating set, namely every vertex is either in \(\mathfrak{S}\) or has at least one neighbor in \(\mathfrak{S}\). This means that a matching (i.e., a set of edges without common vertices) in a graph \(\mathcal{G}\) corresponds to an independent set in the line graph \(\mathcal{L}_{\mathcal{G}}\) of \(\mathcal{G}\), which in turn allows the authors to reduce the computation cost of transforming the network tomography problem to a sparse recovery problem by means of achieving a better selection of _hub_ vertices at \(\mathcal{O}(|\mathcal{E}||\mathcal{V}|^{0.5})\) time compared to \(\mathcal{O}(|\mathcal{E}|^{2}\log|\mathcal{E}|+|\mathcal{E}||\mathcal{E}_{ \mathcal{L}}|)\) time achieved in [50]. Eventually, they propose an algorithm for link insertion and deletion, thus adopting a dynamic strategy when dynamic link operations are taking place, instead of simply rerunning the original algorithm, which would mean that all data--even the unchanged parts--would be recomputed.