随着互联网技术的飞速发展,网络的规模和复杂性日益提高,准确及时的性能数据对网络管理至关重要。然而,庞大的现代网络以及现有测量技术的限制使得收集完整的测量结果是不切实际的。网络断层扫描是从医学中CT扫描衍生出来的概念,其核心是通过易于观察的量来推断所需测量的量。网络断层扫描可分为两大类,第一类用于推导网络内部链路的性能指标,如链路时延、丢包率等;第二类用于估计网络中源到目的的流量强度。不管是推导网络链路的性能指标还是估计网络OD流,直接测量通常是极其困难的。网络断层扫描并非直接测量这些性能指标,而是从其他易得到的测量量估计出来。然而,从易于观察的量来推断网络的性能数据往往是一个非常难的问题,当前大多数工作采用统计推理的方式。在本文中,我们分析网络数据具有稀疏特性,即网络性能指标本身具有稀疏性或在某些字典下具有稀疏性。作为一种新兴的信号分析和综合方法,信号的稀疏表示吸引了研究者的大量关注,已成功应用到信号编码、压缩感知、盲源分离等领域。当前一些网络断层扫描工作已经展示了网络数据的稀疏特性,因而我们期待充分挖掘网络数据的这种特性能得到良好的估计性能。本文针对这个交叉领域展开研究,取得以下相应成果:1.作为整个论文的基石,本文首先分析了网络数据的稀疏性,包括网络链路参数如延时、丢包率的稀疏性,并以实际网络流量为例,阐述了OD流在基变换下的稀疏表达。然后提出利用稀疏性从路径测量进行链路估计,除了压缩感知领域经典的l1最小化,特别提出了一种稀疏贝叶斯学习的方法对网络链路状态进行推理。实验结果验证了所提方案的有效性。2.针对网络断层扫描中的测量路径选择问题,提出了一种基于路由矩阵互相干值的路径选择算法。该方法利用了链路参数的固有稀疏性,选择那些路径使得构造的路由矩阵的互相干值最小。首先证明了该方法的NP完全性,并采用子模理论分析优化目标性质。然后提出一种贪婪式算法,在每次迭代,算法优先选择测量路径使得互相干值增长量最小。实验结果证实所提方案能选择少量的测量路径数,同时保持较高的链路辨识度。3.除了链路状态的稀疏特征,本文进一步探索了链路时间相关性,提出一种时空网络拥塞诊断方法:加权l1最小化方法。该算法结合了链路性能参数的稀疏性和拥塞先验概率,如果把稀疏性看作是链路参数的空间属性的话,那么先验概率就是链路参数的时间相关性。首先在理论上分析了加权l1最小化的恢复误差,并指出选取合适的权值最终会改善恢复精度。然后采用最大后验概率的方法使用拥塞先验概率来确定权值。实验结果证实所提方案优于仅利用稀疏性的方法或仅利用拥塞概率的算法,具有较高的估计精度。4.针对网络中的OD流矩阵估计问题,提出一种利用流量矩阵稀疏表达的估计方法。该方法将小波基的一部分作为字典表达序列,并以OD流矩阵的列l1范数的和最小化为优化目标,成功解决了流量估计中的病态性问题。本文从理论上证明所提出方法的无误差估计条件。由于真实的OD流量中通常含有异常分量,因此分别对两者进行建模能得到更精确的结果。理论分析若异常分量和正常分量在各自的字典下充分稀疏,则可无误差恢复OD流矩阵的正常分量和异常分量。实验结果证实从链路测量估计OD流矩阵时,所提方案不管是异常检测还是流量矩阵恢复均具有较高的精度。通过解决上述问题,将稀疏性理论引入到网络断层扫描中,取得了比传统方法更好的结果。同时,由于本文包含了若干关于稀疏性的理论分析,这些分析得出的结论也丰富了稀疏信号处理相关领域的理论体系。