互聯(lián)網(wǎng)傳播行為的時序演化與預測

田鶴，趙海，王進法，林川

（1. 遼寧科技學院工程實踐中心，遼寧 本溪 117004；2. 東北大學計算機科學與工程學院，遼寧 沈陽 110004）

1 引言

互聯(lián)網(wǎng)作為一種典型的復雜網(wǎng)絡，其宏觀拓撲結(jié)構表現(xiàn)出明顯的復雜網(wǎng)絡特性[1-3]。從網(wǎng)絡病毒傳播以及網(wǎng)絡拓撲結(jié)構的統(tǒng)計特征和演化等方面研究互聯(lián)網(wǎng)的性能、結(jié)構和發(fā)展趨勢已取得了豐碩的成果[4-6]。隨著互聯(lián)網(wǎng)的飛速發(fā)展，人們對網(wǎng)絡的需求不斷增加，使網(wǎng)絡的應用得到廣泛的擴展?；ヂ?lián)網(wǎng)已經(jīng)發(fā)展成為一個復雜的、非線性的系統(tǒng)。然而，網(wǎng)絡的大規(guī)模擴張使網(wǎng)絡安全性、資源調(diào)度與優(yōu)化以及服務質(zhì)量等方面也面臨著巨大挑戰(zhàn)，僅從網(wǎng)絡宏觀拓撲靜態(tài)特征指標的度量、統(tǒng)計和建模不足以形象地描述網(wǎng)絡的傳播行為。為提高網(wǎng)絡各方面的性能，人們需要對網(wǎng)絡行為的特征規(guī)律有深刻的認識，發(fā)現(xiàn)網(wǎng)絡行為的內(nèi)在機制是認識網(wǎng)絡的必然過程。網(wǎng)絡的傳播行為包含了多種網(wǎng)絡動態(tài)行為[7]，如鏈路訪問、分組時延以及路由轉(zhuǎn)發(fā)等，反映了網(wǎng)絡拓撲結(jié)構對動態(tài)行為的影響。掌握網(wǎng)絡傳播行為的特征和規(guī)律有助于對網(wǎng)絡的異常行為做出分析與評估，為防范網(wǎng)絡攻擊和病毒傳播提供預警手段，在一定程度上可控制和預測網(wǎng)絡動態(tài)行為的發(fā)生。

網(wǎng)絡的傳播行為特征規(guī)律可通過定義一些能夠反映網(wǎng)絡行為的特征指標來描述，然后實時監(jiān)測網(wǎng)絡，從中獲取這些特征指標的樣本數(shù)據(jù)，并對測量結(jié)果進行整理、統(tǒng)計、歸納和推斷，透過指標的變化和性質(zhì)對網(wǎng)絡行為的各方面表現(xiàn)進行解釋。研究初期，徐野等[8]定義并分析了訪問直徑網(wǎng)絡物理特征量，利用其演化特征分析網(wǎng)絡漲落現(xiàn)象。然而，互聯(lián)網(wǎng)的規(guī)模呈指數(shù)級增長態(tài)勢，導致僅從時間維度并不足以分析網(wǎng)絡動態(tài)行為。結(jié)合非線性動力學和混沌理論對網(wǎng)絡傳播特征量進行統(tǒng)計，進而分析互聯(lián)網(wǎng)傳播行為特征，為互聯(lián)網(wǎng)的演化分析開辟了新思路。隋巖等[9]從混沌學角度分析互聯(lián)網(wǎng)群體傳播特性，表明互聯(lián)網(wǎng)群體傳播就是一種混沌系統(tǒng)，具有非線性秩序性和自組織性等特征。Ye等[10]基于ARIMA和Holt-Winters，用多元時間序列方法建立長期預測模型，但只適用于網(wǎng)絡靜態(tài)預測，動態(tài)性較差。Chai等[11]將時延坐標嵌入方法和混沌分析方法應用于神經(jīng)網(wǎng)絡構建預測模型，測試結(jié)果表明混沌方法可以顯著提高預測能力?；谝陨涎芯勘尘埃疚囊詴r間為主線，統(tǒng)計和篩選 CAIDA_Ark項目下位于不同大洲的4個監(jiān)測點的有效路徑樣本數(shù)據(jù)，對互聯(lián)網(wǎng)傳播行為進行統(tǒng)計和分析，利用非線性時間序列分析方法對網(wǎng)絡訪問時間序列的時序演化特征進行混沌辨識。在此基礎上，引入Logistic方程建立以混沌網(wǎng)絡訪問時間序列為基礎的網(wǎng)絡傳播行為預測模型，采用粒子群優(yōu)化算法對模型參數(shù)取優(yōu)。最后，分別將4個監(jiān)測點的網(wǎng)絡訪問時間序列在預測模型上進行實驗與驗證，對預測模型的有效性和準確性做出評價。

2 數(shù)據(jù)與推演指標

CAIDA是一個對互聯(lián)網(wǎng)的網(wǎng)絡結(jié)構和數(shù)據(jù)進行獲取、測量、可視化以及分析的國際合作研究機構。2007年9月，CAIDA開展Ark探測項目計劃，將原有的Skitter探測架構升級，采用Scamper技術、traceroute主動探測方式和元組空間實現(xiàn)各監(jiān)測點間的探測和通信。本文選取 CAIDA_Ark項目下 4個位于不同大洲的監(jiān)測點amw、san、bcn和mnl，利用Scamper技術對網(wǎng)絡中隨機抽取的目的IP地址發(fā)送 ICMP探測數(shù)據(jù)分組，同時 traceroute檢查ICMP的 E cho_request分組頭部的TTL值的有效性，追蹤路由的地址路徑。其中，每一個監(jiān)測點在同一探測周期內(nèi)只能探測到一個IP地址。

探測源SRC向目的端DST發(fā)送探測數(shù)據(jù)分組，經(jīng)過中轉(zhuǎn)路由器 R1, R2,… ,Rn，則探測數(shù)據(jù)分組從SRC到DST所經(jīng)過的路徑表示為 R = (S RC,R1,R2,… ,Rn?1,D ST )。探測數(shù)據(jù)分組的路由選擇與轉(zhuǎn)發(fā)都是由各中間路由器決定的，然而，由于監(jiān)測點內(nèi)的分組發(fā)送設置、中間路由器的個體差異性以及受ICMP分組接收率的限制等原因，網(wǎng)絡中并不是所有的中轉(zhuǎn)路由器都能對ICMP分組做出響應，所以探測數(shù)據(jù)分組在某些中轉(zhuǎn)路由器處有可能不可達。雖然SRC未收到中轉(zhuǎn)路由器的響應，但Scamper探測技術仍能夠增加TTL值直至探測到DST，而這時生成的R是不完整的。若所經(jīng)過的中轉(zhuǎn)路由器都能對探測數(shù)據(jù)分組做出響應并返回到SRC，則所生成的R是一個完整的有效路徑。IP級拓撲是抽取網(wǎng)絡IP接口和鏈路而成的，數(shù)據(jù)包含了網(wǎng)絡拓撲最原始的內(nèi)容，數(shù)據(jù)量非常龐大，忽略不可達路徑，提取完整的有效路徑上的樣本數(shù)據(jù)。選取2012-2015年共48個月 IPv4互聯(lián)網(wǎng)IP級拓撲數(shù)據(jù)，以3～4天為一個探測周期，每個月選取一個探測周期的結(jié)果并提取有效路徑樣本，統(tǒng)計結(jié)果如表1所示。

表1 有效路徑樣本數(shù)的統(tǒng)計結(jié)果

從表1可知，提取的有效路徑樣本數(shù)達900多萬條。高冗余數(shù)據(jù)更有利于網(wǎng)絡傳播行為的研究分析。本文從時間維度上對網(wǎng)絡傳播行為進行統(tǒng)計，相關定義如下。

定義1 訪問時間[12]。在網(wǎng)絡中，將監(jiān)測點發(fā)送探測數(shù)據(jù)分組的時間與收到目的端返回響應時間之差定義為該條路徑的一次訪問時間，記為d()T t。

定義 2 網(wǎng)絡訪問時間。大量探測數(shù)據(jù)分組從任一源IP地址到任一目的IP地址所經(jīng)過的有效路徑的訪問時間均值，記為

其中，n為數(shù)據(jù)樣本總數(shù)。

定義 3 訪問直徑[8]。在一個完整的有效路徑中，探測數(shù)據(jù)分組所經(jīng)過的路由跳數(shù)。

定義4 Pearson相關系數(shù)。用來衡量定距變量間的線性關系，計算式為

3 網(wǎng)絡傳播行為特征

3.1 網(wǎng)絡訪問時間的分布特征

首先，提取 4個監(jiān)測點 amw、san、bcn和mnl探測得到的 2012-2015年每月同一周期的有效路徑樣本數(shù)據(jù)。然后，分別對4個監(jiān)測點的有效路徑數(shù)據(jù)的訪問時間做概率分布統(tǒng)計，結(jié)果如圖1所示。

從圖1可直觀看出，4個監(jiān)測點在探測期間有效路徑中網(wǎng)絡訪問時間分布至少有2個峰值，且它們的尾部幾乎重合，呈多峰重尾分布[13]，并且在這4年內(nèi)，同一個監(jiān)測點的網(wǎng)絡訪問時間的分布具有較強的相似性，這是由于不同的監(jiān)測點所處的不同地理位置影響了對目的端的訪問。對于網(wǎng)絡的動態(tài)傳播行為，網(wǎng)絡的訪問時間直接影響有效路徑上網(wǎng)絡端到端的連接行為，例如，對互聯(lián)網(wǎng)傳輸協(xié)議中重傳超時時間（RTO）的設置，若RTO值過小則會加重網(wǎng)絡不必要的負載，若RTO值過大則會浪費網(wǎng)絡帶寬。此外，各監(jiān)測點的高冗余數(shù)據(jù)在探測有效路徑中所呈現(xiàn)的網(wǎng)絡訪問時間的相似分布特征說明互聯(lián)網(wǎng)具有自相似特性。

在網(wǎng)絡動態(tài)傳播演化的過程中，網(wǎng)絡訪問時間越短，數(shù)據(jù)分組在一定有效路徑傳輸距離的時延越小，網(wǎng)絡的傳播性能和效率越高。觀察圖1可以進一步發(fā)現(xiàn)，網(wǎng)絡訪問時間大于400 ms的有效路徑只占很小的比例，這說明雖然各監(jiān)測點所處地理位置相距甚遠，但它們的通信效率仍然很高，探測期間內(nèi)整個網(wǎng)絡的性能非常好。隨著互聯(lián)網(wǎng)的飛速發(fā)展，依靠互聯(lián)網(wǎng)來實現(xiàn)跨國家、跨海洋以及跨大洲通信已不是問題。由于峰值附近的有效路徑樣本數(shù)據(jù)比例較大，具有代表性，本文截取各監(jiān)測點的網(wǎng)絡訪問時間分布在峰值附近較密集的有效路徑樣本數(shù)據(jù)做統(tǒng)計分析。amw、san、bcn和mnl這 4個監(jiān)測點的網(wǎng)絡訪問時間主要集中的區(qū)間如表2所示。

圖1 有效路徑網(wǎng)絡訪問時間分布

表2 截取的網(wǎng)絡訪問時間區(qū)間

3.2 相關性分析

對于IP級拓撲，探測數(shù)據(jù)分組從探測源SRC到目的端DST以動態(tài)選路的方式得到的有效路徑是IP級路徑，其中，每個中轉(zhuǎn)路由器 R1, R2,… ,Rn對應的IP地址為 I P1, I P2,… ,I Pn，中轉(zhuǎn)路由器的個數(shù)即跳數(shù)。訪問直徑是網(wǎng)絡拓撲傳輸效率的度量指標，反映了網(wǎng)絡宏觀拓撲結(jié)構對網(wǎng)絡動態(tài)傳播行為特征的影響。圖2為4個監(jiān)測點在探測有效路徑中網(wǎng)絡訪問直徑的累積分布。

圖2 有效路徑中網(wǎng)絡訪問直徑的累積分布

從圖2可以看到，只有不到10%的有效路徑的訪問直徑在 15跳以下，說明數(shù)據(jù)分組從有效路徑的源IP地址到目的IP地址傳輸一般要經(jīng)過較多的中轉(zhuǎn)路由器。分別來看，amw監(jiān)測點探測的有效路徑訪問直徑有90%超過12跳，bcn監(jiān)測點是15跳，而san和mnl監(jiān)測點是13跳。選取4個監(jiān)測點探測的具有代表性的訪問直徑區(qū)間內(nèi)有效路徑樣本數(shù)據(jù)，amw、bcn、san和mnl監(jiān)測點的有效訪問直徑區(qū)間分別為7～35跳、8～39跳、8～36跳和7～37跳，相應的平均訪問直徑分別為14跳、16跳、14跳和15跳。統(tǒng)計不同訪問直徑的有效路徑的網(wǎng)絡訪問時間，在4個監(jiān)測點的有效路徑的網(wǎng)絡訪問時間分布的峰值范圍內(nèi)（如表2所列的每個監(jiān)測點截取的2個區(qū)間），結(jié)果如圖3所示。

圖3 訪問直徑對網(wǎng)絡訪問時間的影響

從整體趨勢上看，區(qū)間1和區(qū)間2中有效路徑的訪問直徑與網(wǎng)絡訪問時間的變化趨勢是振蕩上升的，也就是說，隨著訪問直徑的增大，網(wǎng)絡訪問時間也隨之增大，說明網(wǎng)絡拓撲中有效路徑的訪問直徑越大，數(shù)據(jù)分組經(jīng)過的中轉(zhuǎn)路由器越多，所需的網(wǎng)絡訪問時間就越長。進一步觀察圖3，對于區(qū)間 1，如圖 3(a)所示，san和 mnl監(jiān)測點的網(wǎng)絡訪問時間開始時急劇下降，然后大幅上升，而amw和bcn監(jiān)測點則相反；amw、bcn和san監(jiān)測點的訪問直徑在13～33跳時，網(wǎng)絡訪問時間變化的振蕩幅度較小，而mnl監(jiān)測點的網(wǎng)絡訪問時間的平緩變化區(qū)間相對較小，主要集中在9～23跳。對于區(qū)間 2，如圖 3(b)所示，4個監(jiān)測點的網(wǎng)絡訪問時間隨著訪問直徑的增大并沒有大幅的振蕩，并且也沒有出現(xiàn)相對平緩的變化。相較于其他 3個監(jiān)測點，mnl監(jiān)測點的網(wǎng)絡訪問時間隨著訪問直徑的增大而小幅增大，盡管出現(xiàn)微小的波動，但總體趨勢是平緩的。

為了深入分析訪問直徑與網(wǎng)絡訪問時間的關系，截取4個監(jiān)測點的2個峰值范圍內(nèi)有效路徑的網(wǎng)絡訪問時間與訪問直徑進行量化統(tǒng)計，如表 3所示。

表3 有效路徑的網(wǎng)絡訪問時間與訪問直徑的統(tǒng)計結(jié)果分析

由表3可得，4個監(jiān)測點提取的網(wǎng)絡訪問時間區(qū)間內(nèi)訪問時間的均值與中位數(shù)相差不大，訪問直徑的均值與中位數(shù)也很相近，說明區(qū)間內(nèi)均為有效樣本。從Pearson相關系數(shù)值看到，最大值只有0.201，最小值是 0.068，所以可以認為訪問直徑與訪問時間是不相關的。進一步分析4個監(jiān)測點的訪問直徑與訪問時間Pearson相關系數(shù)隨著時間的演化趨勢，如圖4所示。以月為單元，在2012-2015年共 48個月Pearson相關系數(shù)值的演化范圍集中在0.05～0.25，期間并沒有呈現(xiàn)增大或減小的變化趨勢，而是隨著時間振蕩演化，出現(xiàn)的最大值也不超過 0.35，說明訪問直徑與訪問時間之間是一種極弱的關系，可以視為是不相關的。而圖3所示的網(wǎng)絡訪問時間隨著訪問直徑增大的可能的原因是對整體樣本數(shù)據(jù)進行統(tǒng)計時，由于數(shù)據(jù)的高冗余性，有效路徑的某一訪問直徑下個體樣本數(shù)據(jù)中較大的訪問時間樣本數(shù)據(jù)沒有體現(xiàn)出來，對總體樣本數(shù)據(jù)的統(tǒng)計掩蓋了個體之間的真實關系。

圖4 訪問直徑與訪問時間Pearson相關系數(shù)演化趨勢

然而，縱向觀察表3，對于同一監(jiān)測點的不同訪問時間區(qū)間，訪問時間的均值和中位數(shù)相差很大，但訪問直徑的均值和中位數(shù)很相近，也就是說，在訪問直徑相差不大的情況下，訪問時間卻相差很大。數(shù)據(jù)分組從網(wǎng)絡中某一源IP地址到任一目的IP地址傳播過程中，由于鏈路吞吐量的差異以及數(shù)據(jù)傳輸過程中的分組丟失、鏈路消耗和時延等原因，造成網(wǎng)絡拓撲中某一特定的訪問直徑下，大量數(shù)據(jù)分組的訪問時間是不同的。在實際的網(wǎng)絡傳播過程中，訪問直徑對數(shù)據(jù)分組訪問時間的影響并不大。

4 網(wǎng)絡訪問時間的演化

4.1 網(wǎng)絡訪問時間演化序列

無論是網(wǎng)絡本身內(nèi)部拓撲結(jié)構還是其外在狀態(tài)表現(xiàn)，網(wǎng)絡都時刻處于動態(tài)變化中，因此網(wǎng)絡的行為也是隨著時間不斷變化的。選取 amw、san、bcn和mnl監(jiān)測點探測得到的2012-2015年共48個月的有效路徑樣本數(shù)據(jù)，根據(jù)定義2，結(jié)合圖1的有效路徑中網(wǎng)絡訪問時間分布，對4個監(jiān)測點的有效路徑中網(wǎng)絡訪問時間演化序列的結(jié)果做統(tǒng)計，如圖5所示。

圖5 網(wǎng)絡訪問時間的演化

從圖5可以看到，網(wǎng)絡訪問時間整體的演化趨勢是緩慢下降的，表明隨著時間的推移，網(wǎng)絡的有效性能不斷增強，網(wǎng)絡的傳播效率不斷提高。然而，這種下降趨勢不會一直出現(xiàn)，數(shù)據(jù)分組在網(wǎng)絡中傳播會受到多方面因素的影響，例如，互聯(lián)網(wǎng)服務提供商因為一些特殊情況對局部地區(qū)的網(wǎng)絡結(jié)構進行調(diào)整，尤其是骨干網(wǎng)上的網(wǎng)絡結(jié)構調(diào)整，引起網(wǎng)絡繞路問題等原因使網(wǎng)絡訪問時間不會無限減小。聚焦各趨勢線上的波動點，4個監(jiān)測點在探測期間網(wǎng)絡訪問時間是振蕩變化的，甚至在某些月份的振蕩幅度較大，說明互聯(lián)網(wǎng)在平穩(wěn)演化的過程中時常伴有突變的發(fā)生，導致這一現(xiàn)象的原因可從主、客觀因素這2個方面來分析：就互聯(lián)網(wǎng)本身而言，在時間和空間的有限結(jié)合中，世界上每天都會有大量的節(jié)點接入互聯(lián)網(wǎng)，同時也會有許多節(jié)點由于各種原因而消亡，互聯(lián)網(wǎng)不斷破壞自身系統(tǒng)的平衡，卻又平穩(wěn)地選擇生成新的拓撲結(jié)構，互聯(lián)網(wǎng)的演化使其內(nèi)部各組織之間以及與其他外界社會環(huán)境之間不斷地相互作用和影響，為了能夠長期穩(wěn)定地生存，演化必須進行物質(zhì)、能量和信息代謝，而代謝活動勢必會使自身的拓撲結(jié)構產(chǎn)生重組（自復制）與變異（突變）以適應變化的環(huán)境，在某一個較短的時間內(nèi)不精確的自復制或是有誤差的數(shù)據(jù)傳輸使參數(shù)大幅動蕩，但是為了維持自身拓撲結(jié)構的穩(wěn)定，動蕩持續(xù)時間并不會太長；另一方面，在互聯(lián)網(wǎng)演化過程中時刻存在著互聯(lián)網(wǎng)異常事件，如DDoS攻擊、僵尸網(wǎng)絡、病毒傳播和網(wǎng)絡群體事件等，這些異常事件將直接帶來網(wǎng)絡中流量增加，引起局部路由上的吞吐量突然增加，進而使網(wǎng)絡時延增加，網(wǎng)絡訪問時間會突然增加。另外，由于CAIDA多點探測方式的限制、路由配置問題以及隨機噪聲的干擾，會使網(wǎng)絡通信路徑和傳輸發(fā)生異常，也會使網(wǎng)絡訪問時間的演化產(chǎn)生振蕩。由此來看，由于網(wǎng)絡自身拓撲結(jié)構和通信鏈路的變化以及本地網(wǎng)絡環(huán)境的影響，網(wǎng)絡訪問時間的演化并沒有一些明顯的特定規(guī)律，但從圖1可知，有效路徑中網(wǎng)絡訪問時間的分布特征又表現(xiàn)出一種規(guī)律性，說明互聯(lián)網(wǎng)宏觀拓撲結(jié)構帶有一種序，具有自相似性，這種自相似性是由于互聯(lián)網(wǎng)拓撲演化時不斷進行自復制行為而產(chǎn)生的，盡管網(wǎng)絡演化時常出現(xiàn)突變，但從總體來看，互聯(lián)網(wǎng)仍是一個穩(wěn)定的確定系統(tǒng)。從另一角度來說，新事物的產(chǎn)生通常由許多差異引起，突變是新信息的主要來源，所以，大幅異常的波動點并不是一種壞現(xiàn)象，它們是網(wǎng)絡進化的動力，也是改造網(wǎng)絡的有利時機。

4.2 混沌特征

根據(jù)非線性動力學理論，一些看似無規(guī)則的隨機行為實際上是一個真實的非線性確定系統(tǒng)內(nèi)在隨機性的表現(xiàn)，這種現(xiàn)象可用混沌運動來解釋，即在非線性確定系統(tǒng)中不需要附加任何隨機因素就能發(fā)生類隨機行為[14]。因此，互聯(lián)網(wǎng)訪問時間的時序演化符合混沌運動特征，同時，互聯(lián)網(wǎng)拓撲有序?qū)哟位淖韵嗨菩哉f明互聯(lián)網(wǎng)具有分形特征。

以混沌理論來分析非線性時間序列的基礎是相空間重構[15]，即把低維的時間序列重構成一個高維的相空間。重構的關鍵是確定2個參數(shù)，即時延τ和嵌入維數(shù)m。

對于網(wǎng)絡訪問時間的n個一維時間序列x1,… ,xn，采用時延坐標法[16]，重構相空間為

其中，重構相空間矢量長度為 N = n ? ( m ? 1 )τ。

1) 時延τ

時延τ的選取應使重構相空間中各矢量相互獨立，統(tǒng)計網(wǎng)絡訪問時間跨度為k的自相關系數(shù)，計算式為

當kR下降至初始值的時，即最佳時延τ。

2) 嵌入維數(shù)m

首先，定義相空間矢量間的關聯(lián)積分為

其中， H (X ) 是Heaviside函數(shù)，當 X ＜ 0 時，H(X)= 0 ；當 X ≥ 0 時， H (X)=1。 R (i , j)是相空間矢量 Y ( ti)和Y ( tj)間的距離，于是 Cm(r)則表示相空間矢量間距離小于r的比例。根據(jù)重建復雜系統(tǒng)動力學原理，當r足夠小而N足夠大時，Cm(r )與 rD(m)成正比，即 Cm(r) = ArD(m)，D (m )就是混沌吸引子的關聯(lián)維數(shù)，其值等于 ln Cm(r)與lnr的斜率 ， 則 有 l n Cm(r) = D(m ) l n r + c onst(常 數(shù) ) 。 若D(m )隨著m的增大而保持收斂，則系統(tǒng)是混沌的，此時， D (m)為飽和關聯(lián)維，m為最小嵌入維。

利用混沌理論來分析非線性訪問時間序列，首先，確定時延τ。網(wǎng)絡訪問時間演化序列的 Rk隨k的變化如圖6所示。由圖6可知，最佳時延τ=3。然后，利用分形維的 G - P算法[17]，繪制最佳時延τ= 3 下，嵌入維數(shù)m為3～12時 ln Cm(r)?lnr曲線，如圖7所示。

圖6 網(wǎng)絡訪問時間演化序列的Rk隨k的變化

圖7 網(wǎng)絡訪問時間演化序列的關聯(lián)積分

從圖7可以看到，隨著m的增大， ln Cm(r)隨lnr變化的曲線斜率逐漸收斂。當 m ＞ 4 時，各條曲線斜率趨于平行。當 m ＞ 9 時，各條曲線幾乎重疊，說明 D (m )趨于收斂，由此得出重構相空間的最小嵌入維數(shù) m = 9 。進一步對 m = 9 時 ln Cm(r)?lnr曲線做線性回歸分析，得到飽和關聯(lián)維 D (m =9,τ =3)=2.8304，是一個分數(shù)維，說明網(wǎng)絡訪問時間演化序列具有混沌特征。

5 網(wǎng)絡傳播行為的預測模型

依據(jù)網(wǎng)絡訪問時間演化序列的混沌特性，在網(wǎng)絡時序演化中引入Logistic方程[18]并加以改進，基于網(wǎng)絡訪問時間演化序列建立預測模型，并進行仿真分析與驗證。

5.1 模型的建立

第 4節(jié)通過對網(wǎng)絡訪問時間演化序列分析得到，在探測期間網(wǎng)絡訪問時間演化趨勢是緩慢振蕩下降的，其振蕩的幅度相對并不大，由于自身拓撲結(jié)構的突變或節(jié)點間通信異常使其呈現(xiàn)出一種準周期性振蕩衰減趨勢。但是隨著互聯(lián)網(wǎng)的迅猛發(fā)展，網(wǎng)絡業(yè)務不斷增多，給網(wǎng)絡通信傳輸帶來了一定的壓力，網(wǎng)絡訪問時間并不會一直衰減，且一定存在某一下限。因此，采用Logistic方程描述網(wǎng)絡訪問時間演化行為是可行的。建模過程如下。

步驟1 將網(wǎng)絡訪問時間演化序列代入Logistic模型的非線性微分方程，有

其中，r為網(wǎng)絡訪問時間變化率，T為t時刻（以月為單位）的網(wǎng)絡訪問時間。

步驟2 對式(6)進行積分，得

由式(7)可得，當 0r＞ 時，T隨著t的增大而單調(diào)遞增。

步驟3 對 Logistic方程變換，使其符合網(wǎng)絡訪問時間演化序列的振蕩衰減特征，變換式為

步驟 4 引入帶正余弦的指數(shù)線性組合作為振蕩衰減因子，同時引入校正系數(shù)p確保模型能反映實際演化特征，最終得到Logistic方程的改進模型為

其中，r1和 r2為振幅， v1和 v2為初始幅角， u1和 u2為振蕩半周期，T為輸出值。模型方程簡化表示為T =f(d,K,m,p,r1, u1, v1, r2, u2, v2,t )。

5.2 參數(shù)的確定

模型參數(shù)的選擇對預測模型的準確性有很大影響。本文采用粒子群優(yōu)化算法（PSO）[19]根據(jù)探測期間網(wǎng)絡訪問時間演化序列對 Logistic模型取優(yōu)。算法流程如下。

輸入 網(wǎng)絡訪問時間演化序列

輸出 最優(yōu)適應度個體 T =f(d,K,m,p,r1, u1,v1, r2, u2, v2,t)

步驟 1 設置初始參數(shù)最大迭代次數(shù)、群體規(guī)模M和加速度c等，并確定各參數(shù)的取值范圍。根據(jù)問題的復雜程度和需求設置群體規(guī)模和算法的終止條件。

步驟2 定義適應度函數(shù)。標準的PSO算法中，適應度函數(shù) f (X ) 是一個最小優(yōu)化目標距離，即xi為第i個粒子的空間位置，那么個體經(jīng)歷的最優(yōu)位置所對應的適應度為fbest( xi)；所有粒子經(jīng)歷的最優(yōu)位置所對應的適應度為 fbest。本模型以評價標準的角度出發(fā)，建立模型的輸出值 T*(i)與實際值 T (i)的累積誤差作為適應度函數(shù)，為

其中，n為以月為單元統(tǒng)計的時間跨度。 S (i)值越小，模型的輸出值與真實數(shù)據(jù)總體誤差越小，預測模型就能夠準確地模擬真實數(shù)據(jù)。

步驟3 在參數(shù)的取值范圍內(nèi)隨機生成初始群體，計算每個個體的適應度 S (i)。若 S (i) ＜ fbest( xi)，則個體所處于局部最好位置；若 S (i) ＜ fbest，則個體處于全局最好位置。

步驟 4 判斷適應值是否超過最大迭代次數(shù)或預設值。若不滿足則繼續(xù)進行步驟3的計算和判斷；若滿足則結(jié)束，輸出結(jié)果。

5.3 實驗與分析

以月為單元，選擇4個監(jiān)測點的2012-2015年共48個月的網(wǎng)絡訪問時間演化序列。分別將4個監(jiān)測點的前 40個月作為預測模型的輸入值進行模擬演化，然后，對比后8個月的數(shù)據(jù)輸出值，以此來評價預測模型的準確度。

首先，設置群體規(guī)模 50M= ，最大迭代次數(shù)為1 000，加速度為2。然后，根據(jù)第3節(jié)和第4節(jié)對網(wǎng)絡訪問時間序列的分布特征與演化特征的分析，確定模型中各參數(shù)的取值范圍。接著，對每個監(jiān)測點在預測模型中進行反復多次實驗以取得最優(yōu)解，如圖8所示。

實際上，由于系統(tǒng)的復雜性、算法的缺陷以及外界隨機噪聲等因素的影響，PSO輸出會帶有一定的誤差，絕對最優(yōu)解是不存在的。理想狀態(tài)并不存在，尋找完備空間也沒有必要，只要能在一個非完備空間中找到相對最優(yōu)解就是合理的。從圖8可以看到，對4個監(jiān)測點的數(shù)據(jù)進行實驗，當?shù)螖?shù)超過800以后，群體較難產(chǎn)生更優(yōu)的個體，說明模型參數(shù)算法的收斂性很好，此時參數(shù)的選擇較為合理。將4個監(jiān)測點PSO輸出的參數(shù)優(yōu)化值代入預測模型，為

5.4 模型評價

為了評價模型的預測準確性，引入相對平均誤差作為模型評價指標，計算式為

圖8 PSO收斂過程

首先，分別計算4個監(jiān)測點的預測模型的擬合值和預測值，并與其實際值對比，如圖9所示。

從整體演化趨勢來看，模型計算的擬合值和預測值的趨勢走向與實際數(shù)據(jù)所表現(xiàn)出的網(wǎng)絡訪問時間演化序列的變化態(tài)勢大致相同，且隨著時間的推移，其都是呈局部緩慢振蕩下降的。在探測時間內(nèi)，開始時擬合效果并不好，直觀上來看，amw、bcn、san和mnl監(jiān)測點模型計算值與實際值分別在14個月、9個月、11個月和10個月前差距較大，這是因為初期粒子群體需要一段時間的適應過程。之后除了個別異常波動點以外，擬合值與實際值的重合性相對較好。而對于后8個月的預測值卻有不同表現(xiàn)，在振蕩幅度較小的時間點上，預測值和實際值差距不大，但從實際數(shù)據(jù)來看，短短8個月的序列演化仍會出現(xiàn)突變點，尤其bcn監(jiān)測點后期各月波動性最大，這種情況下的預測準確度會受到影響，但是可以通過振蕩的幅度和頻率來判斷未來的演化趨勢，在實際應用中可以將這部分時間做記錄，后續(xù)演化時需對它們進行密切關注以及重點研究。分別計算4個監(jiān)測點的預測模型的擬合相對平均誤差和預測相對平均誤差，然后用1分別減去相應的相對平均誤差值，得出擬合準確度和預測準確度，結(jié)果如表4所示。

表4 模型評價指標

由表4可知，模型擬合準確度和預測準確度都滿足評價判定標準。這說明預測模型的構建合理，應用該模型能夠?qū)W(wǎng)絡傳播行為的演化做出準確的預測。

圖9 實際值、擬合值和預測值的對比

時間序列分析是一種廣泛應用的數(shù)據(jù)分析方法，它研究的是代表某一現(xiàn)象的一串隨時間變化而又相關聯(lián)的動態(tài)數(shù)據(jù)，從而描述和探索該現(xiàn)象隨時間發(fā)展變化的規(guī)律性。時間序列分析利用的手段可以是直觀簡便的數(shù)據(jù)圖法、指標法、模型法等。而模型法相對來說更具體也更深入，能更本質(zhì)地了解數(shù)據(jù)的內(nèi)在結(jié)構和復雜特征，以達到控制與預測的目的。傳統(tǒng)的一維擬合模型僅能表現(xiàn)目標系統(tǒng)的一維物理過程，在宏觀拓撲結(jié)構下，網(wǎng)絡的傳播行為能夠表征網(wǎng)絡拓撲結(jié)構對網(wǎng)絡動態(tài)行為的影響?；ヂ?lián)網(wǎng)是基于時間和空間運行的抽象體，時間序列的演化是網(wǎng)絡特征表現(xiàn)最直接的載體。網(wǎng)絡訪問時間序列的混沌特性說明了網(wǎng)絡訪問時間的自相似和穩(wěn)定性，進而通過預測模型建立訪問時間預測算法，可得到當前和未來一段網(wǎng)絡環(huán)境的訪問時間，這為面臨惡意網(wǎng)絡傳播時有效的內(nèi)容劫持提供約束條件，并為網(wǎng)絡劫持提供時間約束條件，促進構建強大的、安全的網(wǎng)絡空間。

但由于混沌系統(tǒng)的初始敏感性、初始場的不準確性以及復雜系統(tǒng)內(nèi)部隨機性使計算極易出現(xiàn)較大的誤差，隨著時間的推移，誤差會不斷累積增大。另一方面，由于數(shù)據(jù)采樣過程中可能帶有噪聲等因素的影響，使混沌序列的時序演化不斷地振蕩，長時間跨度下很難做出精準的預測。但混沌時間序列是由確定性非線性系統(tǒng)產(chǎn)生的，其內(nèi)部存在確定性規(guī)律，因此，短期內(nèi)預測模型可以對網(wǎng)絡傳播行為演化做出較好的預測。實際上，這樣一個預測模型對于互聯(lián)網(wǎng)來說是十分實用的，因為互聯(lián)網(wǎng)自身的發(fā)展迅速，并且?guī)в泻芏辔粗?，長期預測并沒有意義，浪費了時間和資源。如果在某段時間范圍內(nèi)能夠準確地預測網(wǎng)絡行為的演化特征和規(guī)律，在預測能力消失之前對網(wǎng)絡進行適當?shù)募夹g改善，那么這個預測模型也是圓滿完成了任務。

6 結(jié)束語

為保證網(wǎng)絡的正常服務、提升網(wǎng)絡性能和應用拓展，在提取CAIDA_Ark項目下4個監(jiān)測點的有效路徑樣本數(shù)據(jù)的基礎上，本文從大時間尺度上對網(wǎng)絡訪問時間的分布和演化進行統(tǒng)計和描述。對 4個監(jiān)測點在探測期間內(nèi)的有效路徑中網(wǎng)絡訪問時間和訪問直徑進行分析，得出網(wǎng)絡訪問時間呈多峰重尾分布，具有自相似性；訪問直徑與網(wǎng)絡訪問時間具有極弱相關性，可認為不相關，說明在網(wǎng)絡傳播過程中，訪問直徑對數(shù)據(jù)分組的訪問時間的影響并不大。因此在路由算法設計上，不僅要關注路由鏈路的長度還要注重路由鏈接的性能，從而改善了路由算法，提高網(wǎng)絡的通信效率。

統(tǒng)計4個監(jiān)測點的網(wǎng)絡訪問時間演化序列，以非線性時間序列分析方法對其時序演化特征進行混沌辨識，得出網(wǎng)絡訪問時間演化序列具有混沌特征。借此可分析最大的網(wǎng)絡時延點，通過在該點放置內(nèi)容緩存服務器，降低訪問時間和訪問直徑，提高網(wǎng)絡內(nèi)容傳播效率，為內(nèi)容分發(fā)網(wǎng)絡中的內(nèi)容緩存服務器部署提供指導建議。最后，引入Logistic模型并適當改進，采用粒子群算法（PSO）對模型參數(shù)取優(yōu)，建立以網(wǎng)絡訪問時間演化序列為基礎的網(wǎng)絡傳播預測模型。通過對4個監(jiān)測點數(shù)據(jù)在模型中的實驗分析，驗證了模型的有效性，該模型短期內(nèi)能夠?qū)W(wǎng)絡傳播行為做出準確的預測，可為下一代互聯(lián)網(wǎng)建設提供指導性意見。