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

陸興華，黃浩瀚，邱紀(jì)濤，孫宜帆

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

0 引 言

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

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

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

1 基于節(jié)點(diǎn)拓?fù)涓兄漠悩?gòu)網(wǎng)絡(luò)數(shù)據(jù)動(dòng)態(tài)重構(gòu)算法研究

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

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

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

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

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

(1)

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

令目標(biāo)函數(shù)G最小值的聚類準(zhǔn)則對(duì)樣本集合的聚類中心元素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)〉與目標(biāo)函數(shù)相結(jié)合，可得：

(6)

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

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

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

為構(gòu)建異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的目標(biāo)矩陣，首先要將基礎(chǔ)物理網(wǎng)絡(luò)拓?fù)涑橄蟪蓴?shù)學(xué)表達(dá)式：

Gs=(Ns,Ls,Cs)

(7)

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

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

表1 節(jié)點(diǎn)在網(wǎng)絡(luò)中所對(duì)應(yīng)的坐標(biāo)

圖2 異構(gòu)網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

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

(8)

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

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

(9)

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

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

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

(10)

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

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

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

1.4 利用節(jié)點(diǎn)拓?fù)涓兄獙?shí)現(xiàn)數(shù)據(jù)的動(dòng)態(tài)重構(gòu)

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

圖4 節(jié)點(diǎn)聚類

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

(11)

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

2 仿真實(shí)驗(yàn)

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

2.1 實(shí)驗(yàn)設(shè)置

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

表2 實(shí)驗(yàn)測(cè)試用例以及參數(shù)設(shè)置

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

2.2 節(jié)點(diǎn)均衡度實(shí)驗(yàn)結(jié)果與分析

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

(12)

圖5 節(jié)點(diǎn)均衡度對(duì)比結(jié)果

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

2.3 鏈路均衡度實(shí)驗(yàn)結(jié)果與分析

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

(13)

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

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

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

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

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

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

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

綜上所述，通過對(duì)三種算法的節(jié)點(diǎn)均衡度、鏈路均衡度以及數(shù)據(jù)重構(gòu)資源分配路徑精度的比較，實(shí)驗(yàn)結(jié)果顯示所提算法的節(jié)點(diǎn)均衡度比傳統(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ù)動(dòng)態(tài)重構(gòu)算法的主要目標(biāo)。通過聚類目標(biāo)數(shù)據(jù)，建立異構(gòu)網(wǎng)絡(luò)拓?fù)淠Ｐ秃蛢?yōu)化資源分配路徑，對(duì)基于節(jié)點(diǎn)拓?fù)涓兄漠悩?gòu)網(wǎng)絡(luò)數(shù)據(jù)動(dòng)態(tài)重構(gòu)算法進(jìn)行設(shè)計(jì)，實(shí)驗(yàn)結(jié)果表明，設(shè)計(jì)的算法節(jié)點(diǎn)均衡度高于對(duì)比算法，鏈路均衡度同樣高于對(duì)比算法，因此可以得出，設(shè)計(jì)的算法的資源均衡度更優(yōu)。