基于稀疏性的網(wǎng)絡(luò)斷層掃描研究
發(fā)布時間:2020-11-11 03:35
隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展,網(wǎng)絡(luò)的規(guī)模和復雜性日益提高,準確及時的性能數(shù)據(jù)對網(wǎng)絡(luò)管理至關(guān)重要。然而,龐大的現(xiàn)代網(wǎng)絡(luò)以及現(xiàn)有測量技術(shù)的限制使得收集完整的測量結(jié)果是不切實際的。網(wǎng)絡(luò)斷層掃描是從醫(yī)學中CT掃描衍生出來的概念,其核心是通過易于觀察的量來推斷所需測量的量。網(wǎng)絡(luò)斷層掃描可分為兩大類,第一類用于推導網(wǎng)絡(luò)內(nèi)部鏈路的性能指標,如鏈路時延、丟包率等;第二類用于估計網(wǎng)絡(luò)中源到目的的流量強度。不管是推導網(wǎng)絡(luò)鏈路的性能指標還是估計網(wǎng)絡(luò)OD流,直接測量通常是極其困難的。網(wǎng)絡(luò)斷層掃描并非直接測量這些性能指標,而是從其他易得到的測量量估計出來。然而,從易于觀察的量來推斷網(wǎng)絡(luò)的性能數(shù)據(jù)往往是一個非常難的問題,當前大多數(shù)工作采用統(tǒng)計推理的方式。在本文中,我們分析網(wǎng)絡(luò)數(shù)據(jù)具有稀疏特性,即網(wǎng)絡(luò)性能指標本身具有稀疏性或在某些字典下具有稀疏性。作為一種新興的信號分析和綜合方法,信號的稀疏表示吸引了研究者的大量關(guān)注,已成功應用到信號編碼、壓縮感知、盲源分離等領(lǐng)域。當前一些網(wǎng)絡(luò)斷層掃描工作已經(jīng)展示了網(wǎng)絡(luò)數(shù)據(jù)的稀疏特性,因而我們期待充分挖掘網(wǎng)絡(luò)數(shù)據(jù)的這種特性能得到良好的估計性能。本文針對這個交叉領(lǐng)域展開研究,取得以下相應成果:1.作為整個論文的基石,本文首先分析了網(wǎng)絡(luò)數(shù)據(jù)的稀疏性,包括網(wǎng)絡(luò)鏈路參數(shù)如延時、丟包率的稀疏性,并以實際網(wǎng)絡(luò)流量為例,闡述了OD流在基變換下的稀疏表達。然后提出利用稀疏性從路徑測量進行鏈路估計,除了壓縮感知領(lǐng)域經(jīng)典的l_1最小化,特別提出了一種稀疏貝葉斯學習的方法對網(wǎng)絡(luò)鏈路狀態(tài)進行推理。實驗結(jié)果驗證了所提方案的有效性。2.針對網(wǎng)絡(luò)斷層掃描中的測量路徑選擇問題,提出了一種基于路由矩陣互相干值的路徑選擇算法。該方法利用了鏈路參數(shù)的固有稀疏性,選擇那些路徑使得構(gòu)造的路由矩陣的互相干值最小。首先證明了該方法的NP完全性,并采用子模理論分析優(yōu)化目標性質(zhì)。然后提出一種貪婪式算法,在每次迭代,算法優(yōu)先選擇測量路徑使得互相干值增長量最小。實驗結(jié)果證實所提方案能選擇少量的測量路徑數(shù),同時保持較高的鏈路辨識度。3.除了鏈路狀態(tài)的稀疏特征,本文進一步探索了鏈路時間相關(guān)性,提出一種時空網(wǎng)絡(luò)擁塞診斷方法:加權(quán)l(xiāng)_1最小化方法。該算法結(jié)合了鏈路性能參數(shù)的稀疏性和擁塞先驗概率,如果把稀疏性看作是鏈路參數(shù)的空間屬性的話,那么先驗概率就是鏈路參數(shù)的時間相關(guān)性。首先在理論上分析了加權(quán)l(xiāng)_1最小化的恢復誤差,并指出選取合適的權(quán)值最終會改善恢復精度。然后采用最大后驗概率的方法使用擁塞先驗概率來確定權(quán)值。實驗結(jié)果證實所提方案優(yōu)于僅利用稀疏性的方法或僅利用擁塞概率的算法,具有較高的估計精度。4.針對網(wǎng)絡(luò)中的OD流矩陣估計問題,提出一種利用流量矩陣稀疏表達的估計方法。該方法將小波基的一部分作為字典表達序列,并以O(shè)D流矩陣的列l(wèi)_1范數(shù)的和最小化為優(yōu)化目標,成功解決了流量估計中的病態(tài)性問題。本文從理論上證明所提出方法的無誤差估計條件。由于真實的OD流量中通常含有異常分量,因此分別對兩者進行建模能得到更精確的結(jié)果。理論分析若異常分量和正常分量在各自的字典下充分稀疏,則可無誤差恢復OD流矩陣的正常分量和異常分量。實驗結(jié)果證實從鏈路測量估計OD流矩陣時,所提方案不管是異常檢測還是流量矩陣恢復均具有較高的精度。通過解決上述問題,將稀疏性理論引入到網(wǎng)絡(luò)斷層掃描中,取得了比傳統(tǒng)方法更好的結(jié)果。同時,由于本文包含了若干關(guān)于稀疏性的理論分析,這些分析得出的結(jié)論也豐富了稀疏信號處理相關(guān)領(lǐng)域的理論體系。
【學位單位】:電子科技大學
【學位級別】:博士
【學位年份】:2018
【中圖分類】:TP393.0
【文章目錄】:
摘要
ABSTRACT
第一章 緒論
1.1 研究工作的背景與意義
1.2 網(wǎng)絡(luò)斷層掃描概述
1.2.1 基本概念
1.2.2 基本原理
1.3 網(wǎng)絡(luò)斷層掃描國內(nèi)外研究歷史與現(xiàn)狀
1.3.1 探測路徑選擇
1.3.2 鏈路參數(shù)估計
1.3.2.1 鏈路時延估計
1.3.2.2 鏈路丟包率估計
1.3.2.3 鏈路擁塞檢測
1.3.3 流量矩陣估計
1.3.4 稀疏性網(wǎng)絡(luò)斷層掃描
1.4 本文的主要貢獻與創(chuàng)新
1.5 本論文的結(jié)構(gòu)安排
第二章 網(wǎng)絡(luò)數(shù)據(jù)的稀疏性及稀疏求解方法研究
2.1 引言
2.2 網(wǎng)絡(luò)數(shù)據(jù)稀疏模型
2.2.1 稀疏信號
2.2.2 網(wǎng)絡(luò)鏈路參數(shù)的稀疏性
2.2.3 OD流的稀疏表達
2.3 鏈路參數(shù)的稀疏求解
2.3.1 線性方程的稀疏解
1優(yōu)化尋求稀疏解'> 2.3.2 l1優(yōu)化尋求稀疏解
2.3.3 稀疏貝葉斯學習
2.4 實驗與分析
2.4.1 時延仿真
2.4.2 實際網(wǎng)絡(luò)數(shù)據(jù)分析
2.5 本章小結(jié)
第三章 基于稀疏性的探測路徑選擇算法
3.1 引言
3.2 模型和符號定義
3.3 互相干最小算法
3.3.1 壓縮感知測量矩陣設(shè)計
3.3.2 測量路徑選擇
3.3.2.1 設(shè)計目標
3.3.2.2 算法流程
3.4 互相干最小算法的可擴展性
3.5 實驗與分析
3.5.1 互相干最小算法對最佳解的近似
3.5.2 鏈路參數(shù)估計
3.5.3 實驗結(jié)果及分析
3.6 本章小結(jié)
第四章 基于稀疏性的時空網(wǎng)絡(luò)擁塞診斷
4.1 引言
4.2 網(wǎng)絡(luò)模型
1優(yōu)化'> 4.3 加權(quán)l(xiāng)1優(yōu)化
1優(yōu)化的恢復誤差'> 4.3.1 加權(quán)l(xiāng)1優(yōu)化的恢復誤差
4.3.2 權(quán)重的確定
4.3.3 先驗概率的估計
4.4 整體框架
1算法的討論'> 4.4.1 加權(quán)l(xiāng)1算法的討論
4.5 實驗與分析
4.5.1 網(wǎng)絡(luò)拓撲
4.5.2 模擬器
4.5.3 性能指標
4.5.4 實驗結(jié)果及分析:丟包率估計
4.5.5 實驗結(jié)果及分析:擁塞檢測
4.5.6 實際拓撲分析
4.6 本章小結(jié)
第五章 基于稀疏性的流量矩陣估計和異常點檢測
5.1 引言
5.2 模型和符號定義
5.3 基于稀疏性的流量矩陣估計
5.3.1 OD流的稀疏表達
1最小化估計'> 5.3.2 列l(wèi)1最小化估計
5.4 異常流量
5.4.1 基于稀疏性的流量矩陣估計和異常點檢測算法
5.5 實際考慮
5.6 實驗與分析
5.6.1 稀疏性對估計誤差的影響
5.6.2 OD流量矩陣估計和異常檢測
5.6.2.1 數(shù)據(jù)集
5.6.2.2 性能指標及比對方法
5.6.2.3 實驗結(jié)果
5.6.2.4 結(jié)合部分OD流數(shù)據(jù)進行估計
5.7 本章小結(jié)
第六章 結(jié)束語
6.1 全文總結(jié)
6.2 后續(xù)工作展望
致謝
參考文獻
攻博期間取得的研究成果
【參考文獻】
本文編號:2878687
【學位單位】:電子科技大學
【學位級別】:博士
【學位年份】:2018
【中圖分類】:TP393.0
【文章目錄】:
摘要
ABSTRACT
第一章 緒論
1.1 研究工作的背景與意義
1.2 網(wǎng)絡(luò)斷層掃描概述
1.2.1 基本概念
1.2.2 基本原理
1.3 網(wǎng)絡(luò)斷層掃描國內(nèi)外研究歷史與現(xiàn)狀
1.3.1 探測路徑選擇
1.3.2 鏈路參數(shù)估計
1.3.2.1 鏈路時延估計
1.3.2.2 鏈路丟包率估計
1.3.2.3 鏈路擁塞檢測
1.3.3 流量矩陣估計
1.3.4 稀疏性網(wǎng)絡(luò)斷層掃描
1.4 本文的主要貢獻與創(chuàng)新
1.5 本論文的結(jié)構(gòu)安排
第二章 網(wǎng)絡(luò)數(shù)據(jù)的稀疏性及稀疏求解方法研究
2.1 引言
2.2 網(wǎng)絡(luò)數(shù)據(jù)稀疏模型
2.2.1 稀疏信號
2.2.2 網(wǎng)絡(luò)鏈路參數(shù)的稀疏性
2.2.3 OD流的稀疏表達
2.3 鏈路參數(shù)的稀疏求解
2.3.1 線性方程的稀疏解
1優(yōu)化尋求稀疏解'> 2.3.2 l1優(yōu)化尋求稀疏解
2.3.3 稀疏貝葉斯學習
2.4 實驗與分析
2.4.1 時延仿真
2.4.2 實際網(wǎng)絡(luò)數(shù)據(jù)分析
2.5 本章小結(jié)
第三章 基于稀疏性的探測路徑選擇算法
3.1 引言
3.2 模型和符號定義
3.3 互相干最小算法
3.3.1 壓縮感知測量矩陣設(shè)計
3.3.2 測量路徑選擇
3.3.2.1 設(shè)計目標
3.3.2.2 算法流程
3.4 互相干最小算法的可擴展性
3.5 實驗與分析
3.5.1 互相干最小算法對最佳解的近似
3.5.2 鏈路參數(shù)估計
3.5.3 實驗結(jié)果及分析
3.6 本章小結(jié)
第四章 基于稀疏性的時空網(wǎng)絡(luò)擁塞診斷
4.1 引言
4.2 網(wǎng)絡(luò)模型
1優(yōu)化'> 4.3 加權(quán)l(xiāng)1優(yōu)化
1優(yōu)化的恢復誤差'> 4.3.1 加權(quán)l(xiāng)1優(yōu)化的恢復誤差
4.3.2 權(quán)重的確定
4.3.3 先驗概率的估計
4.4 整體框架
1算法的討論'> 4.4.1 加權(quán)l(xiāng)1算法的討論
4.5 實驗與分析
4.5.1 網(wǎng)絡(luò)拓撲
4.5.2 模擬器
4.5.3 性能指標
4.5.4 實驗結(jié)果及分析:丟包率估計
4.5.5 實驗結(jié)果及分析:擁塞檢測
4.5.6 實際拓撲分析
4.6 本章小結(jié)
第五章 基于稀疏性的流量矩陣估計和異常點檢測
5.1 引言
5.2 模型和符號定義
5.3 基于稀疏性的流量矩陣估計
5.3.1 OD流的稀疏表達
1最小化估計'> 5.3.2 列l(wèi)1最小化估計
5.4 異常流量
5.4.1 基于稀疏性的流量矩陣估計和異常點檢測算法
5.5 實際考慮
5.6 實驗與分析
5.6.1 稀疏性對估計誤差的影響
5.6.2 OD流量矩陣估計和異常檢測
5.6.2.1 數(shù)據(jù)集
5.6.2.2 性能指標及比對方法
5.6.2.3 實驗結(jié)果
5.6.2.4 結(jié)合部分OD流數(shù)據(jù)進行估計
5.7 本章小結(jié)
第六章 結(jié)束語
6.1 全文總結(jié)
6.2 后續(xù)工作展望
致謝
參考文獻
攻博期間取得的研究成果
【參考文獻】
相關(guān)期刊論文 前1條
1 費高雷;胡光岷;;基于k階馬爾可夫鏈的單播網(wǎng)絡(luò)丟包層析成像[J];電子與信息學報;2011年09期
本文編號:2878687
本文鏈接:http://www.lk138.cn/guanlilunwen/ydhl/2878687.html
最近更新
教材專著