[發明專利]一種基于時間序列分析的網絡拓撲推斷方法及裝置

有效

• 申請號: 202111036139.8
• 申請日: 2021-09-06
• 公開（公告）號: CN113489619B
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 束妮娜;馬濤;王晨;牛釗;汪明智;劉春生;常超;李磊
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 中國和平利用軍工技術協會專利中心 11215
• 代理人: 劉光德

1.一種基于時間序列分析的網絡拓撲推斷方法，其特征在于，包括以下步驟：

步驟S101：獲取信息數據，將所述信息數據以時間序列進行表征；

步驟S102：根據表征結果，對各節點進行排序，并按照排序次序將各節點對應的時間序列進行拼接；

步驟S103：對拼接后的時間序列進行分段近似聚合；

步驟S104：使用格拉姆角差場算法對分段近似聚合后的時間序列進行編碼，構建類格拉姆矩陣；

步驟S105：根據所述類格拉姆矩陣，對網絡進行拓撲推斷；

所述步驟S101：獲取信息數據，將所述信息數據以時間序列進行表征，包括：

獲取信息數據，設定采樣時間間隔，對所述信息數據進行分析，若在采樣間隔內有信號發送，則該采樣間隔對應的時間序列中的值為1，否則為0；

所述步驟S102：根據表征結果，對各節點進行排序，并按照排序次序將各節點對應的時間序列進行拼接，包括：

所述信息數據的時間序列的表征方式是0和1組成的序列，將各節點首次出現1的時間進行比較，即按照1出現的時間對節點進行排序，1出現的早的節點排在前面；按照排序次序將各節點對應的時間序列進行拼接；

所述步驟S103：對拼接后的時間序列進行分段近似聚合，包括：

對于一個包含n個觀測值的時間序列T，T={t₁,t₂,…,t_n}，使用N_d表示時間序列被處理后得到的最終維數；設定壓縮率ψ用于表示原始時間序列的長度與其分段聚合后的長度之比，ψ的計算公式如下：

（1）

使用表示時間序列T壓縮后得到的結果，T^ψ中第r個元素對應的計算公式如下：

（2）

其中，t_j為T中的第j個元素；

在分段近似聚合的基礎上，將T^ψ中元素歸一化到[-1,1]區間內，得到集合，，其中，為聚合結果歸一化后集合中的第i個元素，的計算公式為：

（3）

為中第i個元素，max(T^ψ)為T^ψ中最大值，min(T^ψ)為T^ψ中最小值；

步驟S104：使用格拉姆角差場算法對分段近似聚合后的時間序列進行編碼，構建類格拉姆矩陣，包括：

根據歸一化的結果，將分段近似聚合后的時間序列從笛卡爾坐標系轉換到極坐標系，將縮放后得到的數值編碼為角度，且存在，將對應的時間戳t_i^’編碼為半徑r_i，坐標變換公式如下：

（4）

其中，t_i^’是時間序列中第i個元素對應的時間戳，是對極坐標系統生成空間進行正則化的常數因子，為常數集合；

利用格拉姆角差場算法對分段近似聚合后的時間序列進行編碼構建類格拉姆矩陣，其計算公式如下：

其中，G為編碼得到的類格拉姆矩陣，為對應的角度值大小，為對應的角度值大小，是的平方操作，I是單位行向量[1,1,…,1]，是的轉置操作，為的轉置向量；

所述步驟S105：根據所述類格拉姆矩陣，對網絡進行拓撲推斷，包括：

根據節點之間是否存在通聯關系為不同節點對形成的類格拉姆矩陣增加標簽，即節點對之間存在通聯關系則其對應的標簽為1，否則為0；

在標簽數據構建的基礎上，使用K最近鄰算法進行判定，使用余弦相似度來衡量樣本之間的相似性，余弦相似度的計算公式為：

（6）

其中P為已訓練好模型中的一個序列，p_k為P中第k個元素，P^’為待判定序列，p^’_k為P^’中第k個元素；

在樣本相似度求取得基礎上，根據樣本相似性找出相似度最高的K個訓練樣本作為待分類樣本的K個近鄰，再根據K個近鄰采用投票策略實現對待分類樣本類型的判定，判定待分類樣本對應的兩個節點之間是否存在通聯關系，根據判定結果和節點位置信息完成拓撲推斷結果的輸出。