基于壓縮感知的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)算法

陸興華，黃浩瀚，邱紀濤，孫宜帆

(廣東工業(yè)大學(xué)華立學(xué)院，廣東 廣州 511325)

0 引 言

當下網(wǎng)絡(luò)應(yīng)用規(guī)模不斷擴大，現(xiàn)有的以節(jié)點為核心的網(wǎng)絡(luò)架構(gòu)已經(jīng)在超負荷運作，異構(gòu)網(wǎng)絡(luò)應(yīng)運而生。所謂異構(gòu)網(wǎng)絡(luò)，是由不同制造商生產(chǎn)的計算機、網(wǎng)絡(luò)設(shè)備和系統(tǒng)組成的[1]，在大部分情況下運行在不同的協(xié)議上支持不同的功能或應(yīng)用。異構(gòu)網(wǎng)絡(luò)通過為用戶提供網(wǎng)絡(luò)數(shù)據(jù)，實現(xiàn)對數(shù)據(jù)可動態(tài)重構(gòu)和擴展物理網(wǎng)絡(luò)的共享[2]。

文獻[3]提出了基于一對多匹配算法的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)重構(gòu)方法。在D2D高密度部署場景下，同時使多個用戶采用相同的蜂窩資源，完成數(shù)據(jù)重構(gòu)；文獻[4]提出基于直覺模糊時間序列的網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)算法，根據(jù)IFCM平衡節(jié)點資源，根據(jù)節(jié)點反饋完成數(shù)據(jù)調(diào)度，據(jù)此完成網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)。以上方法在數(shù)據(jù)動態(tài)重構(gòu)過程中，異構(gòu)網(wǎng)絡(luò)資源的均衡度較低，數(shù)據(jù)重構(gòu)算法有待優(yōu)化。

針對現(xiàn)有的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)算法存在的問題，設(shè)計一種基于節(jié)點拓撲感知的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)算法。在時間復(fù)雜度內(nèi)計算出節(jié)點位置和權(quán)重，建立異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的目標矩陣模型，得到階矩陣與權(quán)矩陣，進而劃分出具體的節(jié)點核心區(qū)，設(shè)置路由器物理鏈路的帶寬約束優(yōu)化數(shù)據(jù)重構(gòu)資源的分配路徑，將節(jié)點核心區(qū)劃分為聚類節(jié)點來感知數(shù)據(jù)的動態(tài)變化，實現(xiàn)數(shù)據(jù)的動態(tài)重構(gòu)。

1 基于節(jié)點拓撲感知的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)算法研究

異構(gòu)網(wǎng)絡(luò)是將網(wǎng)絡(luò)拓撲與資源狀態(tài)等條件優(yōu)化考慮，提供資源服務(wù)的承載網(wǎng)絡(luò)，其中，可重構(gòu)數(shù)據(jù)可通過動態(tài)重構(gòu)實現(xiàn)資源共享，其重構(gòu)網(wǎng)絡(luò)示意圖如圖1所示。

圖1 重構(gòu)網(wǎng)絡(luò)示意圖

如圖1所示，數(shù)據(jù)通過節(jié)點和鏈路實現(xiàn)動態(tài)重構(gòu)，實現(xiàn)資源均衡，然而重構(gòu)網(wǎng)絡(luò)資源的均衡度過低。其主要原因一是沒有完善的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的目標矩陣模型，二是對于資源分配路徑?jīng)]有動態(tài)優(yōu)化措施。因此針對這兩個問題，重新設(shè)計基于節(jié)點拓撲感知的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)算法。

1.1 數(shù)據(jù)目標聚類

通過模糊核聚類算法利用非線性變化將待挖掘數(shù)據(jù)樣本集映射至高維空間內(nèi)，在高維空間內(nèi)聚類目標數(shù)據(jù)，模糊核函數(shù)聚類目標函數(shù)公式如下：

(1)

其中，n表示數(shù)據(jù)目標分類數(shù)量，且滿足n≥2；T(xk)與Y(xi)分別表示樣本集合的聚類中心以及非線性變換函數(shù)。

令目標函數(shù)G最小值的聚類準則對樣本集合的聚類中心元素xk以及非線性變換函數(shù)元素xi的偏導(dǎo)數(shù)為零，可得公式如下：

(2)

(3)

選取符合Mercer條件的高斯核函數(shù)作為以上公式的核函數(shù)，具體公式為：

(4)

其中，δ表示數(shù)據(jù)多尺度參數(shù)。式(4)也可表示為：

Γ(xk)-Γ(xi)=K(xk,xi)

(5)

將核函數(shù)K(xk,xi)=〈Γ(xk),Γ(xi)〉與目標函數(shù)相結(jié)合，可得：

(6)

其中，Anew與Aold分別表示矩陣更新后與更新前。當‖Anew-Aold‖<δ時，停止迭代計算，通過以上步驟獲取樣本集合的聚類中心元素xk以及非線性變換函數(shù)元素xi，當‖Anew-Aold‖≥δ時，轉(zhuǎn)換至式(6)更新隸屬度矩陣重新計算，其中δ>0為迭代截止誤差值。

通過以上步驟將異構(gòu)網(wǎng)絡(luò)的目標數(shù)據(jù)映射至高維空間，并利用符合Mercer條件的高斯核函數(shù)實現(xiàn)目標數(shù)據(jù)的有效聚類。

1.2 構(gòu)建異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的目標矩陣模型

為構(gòu)建異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的目標矩陣，首先要將基礎(chǔ)物理網(wǎng)絡(luò)拓撲抽象成數(shù)學(xué)表達式：

Gs=(Ns,Ls,Cs)

(7)

式中，Ns表示基礎(chǔ)網(wǎng)絡(luò)中的節(jié)點集合，Ls表示基礎(chǔ)網(wǎng)絡(luò)中的鏈路集合，Cs表示基礎(chǔ)網(wǎng)絡(luò)的資源提供能力，主要包括節(jié)點資源與鏈路資源，節(jié)點資源主要包括內(nèi)存與CPU性能，鏈路資源主要包括鏈路帶寬[5]。在通常情況下，整個網(wǎng)絡(luò)的布局規(guī)劃中，能夠在時間復(fù)雜度內(nèi)計算出每個節(jié)點在網(wǎng)絡(luò)中的坐標位置，如表1所示。

在表1中，節(jié)點的x坐標為節(jié)點到固定邊框左邊界的距離，這時所有節(jié)點的權(quán)重為節(jié)點的寬度，節(jié)點的y坐標為節(jié)點到固定邊框下邊界的距離，節(jié)點的權(quán)重為節(jié)點的高度[6-7]。在得到各個節(jié)點坐標后，能夠建立異構(gòu)網(wǎng)絡(luò)拓撲模型，如圖2所示。

表1 節(jié)點在網(wǎng)絡(luò)中所對應(yīng)的坐標

圖2 異構(gòu)網(wǎng)絡(luò)拓撲模型

在構(gòu)建的模型中，要確定聚類節(jié)點的數(shù)目，也就是路由器的數(shù)目，這影響異構(gòu)網(wǎng)絡(luò)的路由器數(shù)量和路由器之間的通信需求，對拓撲結(jié)構(gòu)也有一定的影響。在構(gòu)建的異構(gòu)網(wǎng)絡(luò)拓撲模型中，其連接信息可以用權(quán)矩陣來表達[8]，權(quán)矩陣本質(zhì)上是一個包含節(jié)點之間連接權(quán)重的二維矩陣，其元素的生成方式如下式所示：

(8)

在構(gòu)建的網(wǎng)絡(luò)模型中，構(gòu)造出M×M的階矩陣A=(aij)，其中節(jié)點i和節(jié)點j之間如果相連，對應(yīng)的系數(shù)為1，否則，對應(yīng)系數(shù)為0，即相同節(jié)點之間的對角線系數(shù)為0[9]。

上述簡易6節(jié)點異構(gòu)網(wǎng)絡(luò)圖中的數(shù)據(jù)權(quán)矩陣模型可以表示為：

(9)

至此完成了異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)目標矩陣模型的構(gòu)建。

1.3 數(shù)據(jù)重構(gòu)資源的分配路徑優(yōu)化

在上文構(gòu)建的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)目標矩陣模型中，包含著一定數(shù)量的節(jié)點和布圖規(guī)劃，節(jié)點之間的數(shù)據(jù)重構(gòu)資源的通信流分配路徑的優(yōu)化成為設(shè)計的關(guān)鍵問題。數(shù)據(jù)重構(gòu)資源通信流的路徑分配結(jié)果決定著異構(gòu)網(wǎng)絡(luò)的資源均衡度[10]，為了確保鏈路帶寬的負載平衡，在路徑分配過程中可以通過設(shè)置路由器物理鏈路的帶寬約束來實現(xiàn)。路由器頂點si∈S，其資源通信量大小的關(guān)系表達公式為：

(10)

si,sj均代表路由器節(jié)點，負責與矩陣模型中的節(jié)點進行數(shù)據(jù)重構(gòu)的資源分配[11]，節(jié)點之間的分配路徑如圖3所示。

圖3 節(jié)點核心區(qū)數(shù)據(jù)重構(gòu)分配路徑

從圖3可以得知，6個節(jié)點核心區(qū)之間的資源數(shù)據(jù)流只需要通過總線進行通信。至此完成了數(shù)據(jù)重構(gòu)資源分配路徑的優(yōu)化。

1.4 利用節(jié)點拓撲感知實現(xiàn)數(shù)據(jù)的動態(tài)重構(gòu)

在上述優(yōu)化過的分配路徑中，為了實現(xiàn)數(shù)據(jù)的動態(tài)重構(gòu)，需要將節(jié)點核心區(qū)通過特定的聚類方式劃分為3個聚類節(jié)點，即clu1、clu2和clu3，為每一個節(jié)點核心聚類節(jié)點拓撲感知一個路由器數(shù)據(jù)的動態(tài)變化，來實現(xiàn)全局的數(shù)據(jù)動態(tài)重構(gòu)[12-13]。聚類節(jié)點的詳細劃分如圖4所示。

圖4 節(jié)點聚類

通過上述的節(jié)點聚類劃分，能夠完成全局范圍的動態(tài)配置，在資源感知和數(shù)據(jù)重構(gòu)階段串行進行交替，減少資源的空閑時間，其公式化定義如下所示：

(11)

其中，fcap(i,j)表示任意兩個異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)之間的重構(gòu)階段，對于一些約束條件的限制問題，可以通過拉格朗日乘子吸收到目標路徑中，減少了一些約束條件，轉(zhuǎn)化為拉格朗日乘子問題。至此完成了基于節(jié)點拓撲感知的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)算法的設(shè)計[14-16]。

2 仿真實驗

為驗證文中設(shè)計算法的有效性，設(shè)計仿真實驗。并采用文獻[3]方法和文獻[4]方法為實驗對照組，對3種算法的資源均衡度進行討論。實驗選取不同方法的節(jié)點均衡度以及鏈路均衡度作為測試指標，指標的計算方法在下文給出，具體實驗結(jié)果如下：

2.1 實驗設(shè)置

算法的資源均衡度主要包括兩個方面，一是節(jié)點均衡度，另一個是鏈路均衡度。為了使實驗結(jié)果更加具有說服力，需要將兩種算法的節(jié)點均衡度與鏈路均衡度分別進行比較。本實驗采用OPNET Technology公司的OPNET Modeler平臺進行仿真，它能夠提供三層建模機制，基本模型庫也相對齊全，提供了和網(wǎng)管系統(tǒng)、流量監(jiān)測系統(tǒng)的接口，能夠方便地利用現(xiàn)有的拓撲和流量數(shù)據(jù)建立仿真模型，同時還可對仿真結(jié)果進行驗證。仿真網(wǎng)絡(luò)中的實驗測試用例以及參數(shù)如表2所示。

表2 實驗測試用例以及參數(shù)設(shè)置

在本實驗的網(wǎng)絡(luò)架構(gòu)中，總的配置比特流長度為148 561 285 bits，當采用最大帶寬的配置模式，能夠計算出配置時間，并取10次獨立運行的平均值，進而計算出異構(gòu)網(wǎng)絡(luò)中的節(jié)點均衡度和鏈路均衡度。

2.2 節(jié)點均衡度實驗結(jié)果與分析

在構(gòu)建異構(gòu)網(wǎng)絡(luò)時，整個底層網(wǎng)絡(luò)上所用節(jié)點的平均處理能力與最大處理能力之比，為節(jié)點均衡度，其計算方程式為：

(12)

圖5 節(jié)點均衡度對比結(jié)果

從節(jié)點均衡度的對比結(jié)果可以看出，隨著構(gòu)建請求數(shù)量的增多，兩種算法的節(jié)點均衡度都有所變化。在構(gòu)建請求總數(shù)為80次的實驗中，文獻[3]算法的節(jié)點均衡度平均值為0.68，文獻[4]算法的節(jié)點均衡度平均值為0.52，文中算法的節(jié)點均衡度的平均值為0.93。根據(jù)上述實驗結(jié)果可以得出，文中算法的節(jié)點均衡度高于傳統(tǒng)算法。

2.3 鏈路均衡度實驗結(jié)果與分析

整個底層網(wǎng)絡(luò)上所用鏈路的平均利用率與最大鏈路利用率之比，為鏈路均衡度，其計算方程式為：

(13)

式中，M為鏈路總數(shù)，Lj為單條鏈路的平均利用率，Lmax為最大鏈路利用率。實驗中隨著異構(gòu)網(wǎng)絡(luò)構(gòu)建數(shù)量的增加，計算并統(tǒng)計出3種算法的鏈路均衡度情況，如圖6所示。

圖6 鏈路均衡度對比結(jié)果

從鏈路均衡度的對比結(jié)果可以看出，隨著構(gòu)建請求數(shù)量的增多，兩種算法的鏈路均衡度都有所變化。在構(gòu)建請求總數(shù)為80次的實驗中，文獻[3]算法的鏈路均衡度的平均值為0.65，文獻[4]算法的鏈路均衡度的平均值為0.55，文中算法的鏈路均衡度的平均值為0.90，由此能夠得出，文中算法的鏈路均衡度高于傳統(tǒng)算法。

2.4 不同算法的數(shù)據(jù)重構(gòu)資源分配路徑精度測試

為進一步驗證所提算法的應(yīng)用有效性，以數(shù)重構(gòu)資源分配路徑作為實驗指標，對比不同算法的性能測試結(jié)果。數(shù)據(jù)重構(gòu)資源分配路徑的精度越高，說明資源分配的越精準，算法的數(shù)據(jù)重構(gòu)效果越好。具體實驗結(jié)果如圖7所示。

圖7 不同算法的數(shù)據(jù)重構(gòu)資源分配路徑精度

根據(jù)圖7的實驗結(jié)果可知，所提算法下數(shù)據(jù)重構(gòu)資源的分配路徑精度更高，平均精度水平在95%以上。而另外兩種算法的資源分配精度測試結(jié)果并不理想，說明傳統(tǒng)方法無法得以有效應(yīng)用。

綜上所述，通過對三種算法的節(jié)點均衡度、鏈路均衡度以及數(shù)據(jù)重構(gòu)資源分配路徑精度的比較，實驗結(jié)果顯示所提算法的節(jié)點均衡度比傳統(tǒng)算法高0.29，所提算法的鏈路均衡度比傳統(tǒng)算法高0.32，且該算法的數(shù)據(jù)重構(gòu)資源分配路徑精度更高，因此可以得出結(jié)論，文中算法的數(shù)據(jù)重構(gòu)效果優(yōu)于傳統(tǒng)算法。

3 結(jié)束語

高效地利用異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)資源，使資源均衡度最大化，是數(shù)據(jù)動態(tài)重構(gòu)算法的主要目標。通過聚類目標數(shù)據(jù)，建立異構(gòu)網(wǎng)絡(luò)拓撲模型和優(yōu)化資源分配路徑，對基于節(jié)點拓撲感知的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)動態(tài)重構(gòu)算法進行設(shè)計，實驗結(jié)果表明，設(shè)計的算法節(jié)點均衡度高于對比算法，鏈路均衡度同樣高于對比算法，因此可以得出，設(shè)計的算法的資源均衡度更優(yōu)。