[發明專利]基于網絡層析成像技術的網絡流量矩陣預測方法

有效

• 申請號: 201811096285.8
• 申請日: 2018-09-19
• 公開（公告）號: CN109088796B
• 公開（公告）日: 2020-09-15
• 發明（設計）人: 楊京禮;鄭可昕;崔征
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: H04L12/26
• 分類號: H04L12/26
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 劉冰

1.基于網絡層析成像技術的網絡流量矩陣預測方法，其特征在于，該方法包括以下步驟：

步驟一、基于路由矩陣構造觀測矩陣R和觀測結果矩陣L，并建立觀測矩陣R和觀測結果矩陣L的關系式；

步驟一一：初始化觀測矩陣R等于路由矩陣，R＝A＝(A₁；A₂；...；A_M)，其中：A₁、A₂和A_M分別為觀測矩陣的第1列、第2列和第M列；

初始化待選路徑矩陣為對角陣

其中：i＝1,2,…N，j＝1,2,…N，N代表對角陣的行數和列數；且初始化最大路徑數量為γ，且γ＜N；初始化觀測結果矩陣L為鏈路流量數據Y^T；

步驟一二：對于對角陣Ω中的每個行向量Ω_i，分別構造中間變量矩陣代表矩陣Ξⁱ的第1行，|R|代表矩陣R的行數；

通過公式(1)計算矩陣Ξⁱ的Spark常數下限Spark(Ξⁱ)；

其中：||·||代表2范數，表示求向量的內積，表示向量的內積的絕對值；

步驟一三：選擇Spark常數下限最大值所對應的行向量Ω_i，將其添加到觀測矩陣中，令得到的觀測矩陣R＝(A；Ω_i)，將Ω_i從對角陣Ω中刪除；使用SNMP工具收集第i條OD流在各個時間點上數據組成的向量Υ，并將向量Υ添加到觀測結果矩陣中，令得到的觀測結果矩陣L＝(Y^T；Υ)；

步驟一四：重復執行步驟一二與步驟一三，直到觀測矩陣中的行向量數量達到M+γ，得到優化后的觀測矩陣R和觀測結果矩陣L，優化后的觀測矩陣R和觀測結果矩陣L的關系表示如下：

L＝RX^T (2)

其中：X為網絡流量矩陣的樣本數據，X^T為X的轉置；

步驟二、對網絡流量矩陣的樣本數據X進行等間隔劃分，得到π個網絡流量矩陣的子樣本片段X(1),X(2),...,X(π)，分別計算每個子樣本片段對應的重建網絡流量矩陣的一組正交基，得到過完備正交基的集合為

所述步驟二的具體過程為：

按照間隔Δ對網絡流量矩陣的樣本數據X進行等分，得到π個網絡流量矩陣的子樣本片段X(1),X(2),...,X(π)，X(1)代表第1個子樣本片段；對于第t個子樣本片段X(t)，1≤t≤π，通過X(t)的SVD分解得到重建網絡流量矩陣的一組正交基：

X(t)＝U(t)S(t)V^T(t) (3)

其中，S(t)是一個對角陣；V(t)為正交矩陣，且V(t)的列為X(t)的左奇異向量，U(t)是一個正交矩陣，U(t)的列稱為X(t)的右奇異向量，u_i′(t)和v_i′(t)分別表示U(t)和V(t)的列向量，為v_i′(t)的轉置；s_i′(t)表示X(t)的奇異值，i′代表對應矩陣的第i′列，K為稀疏度，是X(t)的近似值，是U(t)的近似值，是S(t)的近似值，將式(4)帶入式(2)得到：

中間變量矩陣為重建網絡流量矩陣的一組正交基；

通過對所有π個網絡流量矩陣的子樣本片段的SVD分解，得到過完備正交基的集合為

步驟三、設定中間變量矩陣觀測信號為l_q，稀疏度為K；初始化殘差r₀＝l_q，初始化信號支撐集

所述步驟三的具體過程為：

設定中間變量矩陣觀測信號為l_q，稀疏度為K；其中：l_q和θ_q分別為優化后的觀測結果矩陣L和中間變量矩陣Θ的第q列，Θ＝{Θ(1),Θ(2),…,Θ(t),…,Θ(T)}，Θ(t)為Θ^T(t)的轉置；初始化殘差r₀＝l_q，初始化信號支撐集

步驟四、從中間變量矩陣Φ中尋找與信號相關性最強的信號支撐索引，將尋找到的最強信號支撐索引I對應的φ_j′加入信號支撐集，其中，φ_j′為矩陣Φ的第j′列，得到更新后的信號支撐集Φ₁；利用更新后的信號支撐集Φ₁計算稀疏系數估計值利用稀疏系數估計值更新殘差，得到更新后的殘差r₁；

所述步驟四的具體過程為：

步驟四一：從中間變量矩陣Φ中尋找與信號相關性最強的信號支撐索引I：

I＝argmax_{j′＝1,2,...,N×π}|r₀,φ_j′| (6)

其中，φ_j′為矩陣Φ的第j′列，j′＝1,2,...,N×π；

將尋找到的最強信號支撐索引I對應的φ_j′加入信號支撐集Φ₀，得到更新后的信號支撐集Φ₁；

Φ₁＝Φ₀∪φ_j′ (7)

利用更新后的信號支撐集Φ₁計算稀疏系數估計值

步驟四二：利用稀疏系數估計值更新殘差，得到更新后的殘差r₁：

步驟五、重復執行步驟四的操作，直至迭代次數達到K，利用第K次迭代對應的稀疏系數估計值重構出測量時間點q上的網絡流量矩陣

同理，重構出其它測量時間點上的網絡流量矩陣，得到網絡流量矩陣

所述步驟五的具體過程為：

步驟五一：重復執行步驟四一至步驟四二的過程，直至迭代次數達到K次；對于第K次迭代，I＝argmax_{j′＝1,2,...,N×π}|r_K-1,φ_j′|，Φ_K＝Φ_K-1∪φ_j′，利用更新后的信號支撐集Φ_K計算出稀疏系數估計值

步驟五二：利用步驟五一第K次迭代計算得到的稀疏系數估計值重構出測量時間點q上的網絡流量矩陣

同理，即可重構出其余測量時間點上的網絡流量矩陣，即網絡流量矩陣的重構結果為其中，Q為測量時間點的個數。