基于聚類挖掘的移動(dòng)通信網(wǎng)絡(luò)鏈路優(yōu)化設(shè)計(jì)

陳俊霖，齊繼東，鮮 娟*，鄧 娟

(1. 重慶郵電大學(xué)移通學(xué)院，重慶 合川 401520；2. 重慶郵電大學(xué)，重慶 400065)

1 引言

隨著移動(dòng)網(wǎng)絡(luò)通信迅速技術(shù)發(fā)展，人們將注意力從網(wǎng)絡(luò)通信設(shè)計(jì)的拓?fù)鋬?yōu)化、信道容量的合理分配等問(wèn)題轉(zhuǎn)向了應(yīng)充分利用信道能力，減少虛耗現(xiàn)象，從而使移動(dòng)通信網(wǎng)絡(luò)鏈路優(yōu)化設(shè)計(jì)成為重點(diǎn)。鏈路優(yōu)化是將網(wǎng)絡(luò)與信息傳輸緊密聯(lián)系的重要橋梁，通信網(wǎng)絡(luò)中的鏈路優(yōu)化表示根據(jù)尚有的網(wǎng)絡(luò)節(jié)點(diǎn)與結(jié)構(gòu)特征，對(duì)節(jié)點(diǎn)連接方式進(jìn)行優(yōu)化。由于移動(dòng)網(wǎng)絡(luò)通信結(jié)構(gòu)較為復(fù)雜，且統(tǒng)計(jì)數(shù)量龐大，很難對(duì)不同機(jī)制的性能進(jìn)行比較，而鏈路優(yōu)化可以為其提供平臺(tái)，有助于提升復(fù)雜通信網(wǎng)絡(luò)的穩(wěn)定性。傳統(tǒng)鏈路優(yōu)化方法對(duì)節(jié)點(diǎn)密度影響考慮較少，在節(jié)點(diǎn)密度超高時(shí)，鏈路優(yōu)化的性能會(huì)大大降低，為此相關(guān)學(xué)者對(duì)移動(dòng)通信網(wǎng)絡(luò)鏈路問(wèn)題做了大量研究。

文獻(xiàn)[1]提出基于高階近似的鏈路優(yōu)化方法。首先對(duì)通信網(wǎng)絡(luò)的歸一化相鄰矩陣與相似度矩陣進(jìn)行構(gòu)建，并分解相似度矩陣，獲得節(jié)點(diǎn)表示的向量數(shù)值；其次利用高階網(wǎng)絡(luò)對(duì)相似度矩陣進(jìn)行優(yōu)化處理，并獲取更高階矩陣函數(shù)表達(dá)式，最后通過(guò)在真實(shí)數(shù)據(jù)集合中的多次試驗(yàn)，將優(yōu)化后的鏈路與原始鏈路對(duì)比，證明該優(yōu)化方法的可行性。

文獻(xiàn)[2]在高負(fù)載MANET環(huán)境下，提出基于灰色區(qū)域估計(jì)的自適應(yīng)鏈路優(yōu)化方法。通過(guò)對(duì)基于卡爾曼濾波的灰色區(qū)域預(yù)測(cè)分析，計(jì)算通信過(guò)程信噪比，判斷鏈路狀態(tài)情況，并在鏈路發(fā)生失效之前，重新選擇新路由，提高效率；處理通信網(wǎng)絡(luò)中的灰色區(qū)域，利用多路徑冗余傳輸方式提高鏈路性能的同時(shí)改善網(wǎng)絡(luò)通信質(zhì)量。

雖然上述方法在一定程度上改善了鏈路性能，但是在通信過(guò)程中，傳輸功能受到帶寬限制，基于此，本文在聚類挖掘基礎(chǔ)上對(duì)移動(dòng)通信網(wǎng)絡(luò)鏈路優(yōu)化進(jìn)行設(shè)計(jì)。聚類挖掘算法是根據(jù)統(tǒng)計(jì)學(xué)的聚類分析方法對(duì)數(shù)據(jù)信息進(jìn)行挖掘。通過(guò)對(duì)聚類挖掘各項(xiàng)指標(biāo)的分析，獲取節(jié)點(diǎn)特性，判斷鏈路最佳帶寬值，根據(jù)非線性規(guī)劃原理實(shí)現(xiàn)鏈路優(yōu)化設(shè)計(jì)。所提方法能夠提升通信節(jié)點(diǎn)帶寬，減少節(jié)點(diǎn)擁塞現(xiàn)象發(fā)生，實(shí)現(xiàn)移動(dòng)通信網(wǎng)絡(luò)鏈路優(yōu)化。

2 方法

2.1 通訊網(wǎng)絡(luò)聚類挖掘算法原理

對(duì)一個(gè)移動(dòng)通信網(wǎng)絡(luò)G(V，E)進(jìn)行定義[3]，V表示節(jié)點(diǎn)集合，E為鏈路集合。網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)量與總邊數(shù)，分別表示為N與M。假設(shè)U是數(shù)量為U(N-1)/2個(gè)節(jié)點(diǎn)構(gòu)成的集合，則U-E為網(wǎng)絡(luò)中缺失的鏈路集合。鏈路優(yōu)化就是要達(dá)到在U-E集合中篩選出失效鏈路，此時(shí)需要設(shè)定鏈路估計(jì)方法，對(duì)不發(fā)生連邊現(xiàn)象的節(jié)點(diǎn)(x，y)給予分?jǐn)?shù)值Sx，y。此分?jǐn)?shù)值具有接近性特征，它和節(jié)點(diǎn)聯(lián)通的概率成正相關(guān)。將失效鏈路按照分?jǐn)?shù)高低進(jìn)行降序排列，分?jǐn)?shù)越高，證明失效可能性越大。

其鏈路優(yōu)化過(guò)程如下述內(nèi)容所示：

1)在通信網(wǎng)絡(luò)中存在節(jié)點(diǎn)x，將其附近集合表示為Γ(x)，節(jié)點(diǎn)x與y的相似程度可以表示它們相同的鄰近節(jié)點(diǎn)數(shù)量[4]。

2)通過(guò)兩個(gè)節(jié)點(diǎn)相同鄰近節(jié)點(diǎn)數(shù)量在節(jié)點(diǎn)總數(shù)量中所占比重，對(duì)節(jié)點(diǎn)x與y的相似性進(jìn)行描述

(1)

式中，Γ(y)表示通信網(wǎng)絡(luò)中的節(jié)點(diǎn)y附近集合。

3)按照最佳比例權(quán)重對(duì)鄰近集合中的節(jié)點(diǎn)進(jìn)行合理分配[5]，任意節(jié)點(diǎn)的權(quán)重表示為

(2)

4)作為通信網(wǎng)絡(luò)整體結(jié)構(gòu)的估計(jì)方式，對(duì)網(wǎng)絡(luò)中全部路徑進(jìn)行考慮。其表達(dá)式為

(3)

5)利用x與y節(jié)點(diǎn)之間存在的不同路徑數(shù)量，描述節(jié)點(diǎn)之間相似度。表達(dá)式為

(4)

式中，A描述鄰接矩陣，ε表示自由參數(shù)。

6)將共同鄰近節(jié)點(diǎn)數(shù)據(jù)以節(jié)點(diǎn)聚類系數(shù)的方式體現(xiàn)出來(lái)，把x與y節(jié)點(diǎn)存在的相似度作為鄰近節(jié)點(diǎn)的系數(shù)之和

(5)

式中，tz表示經(jīng)過(guò)節(jié)點(diǎn)z的三角形個(gè)數(shù)。

2.2 聚類邊信息獲取

通常情況下，聚類信息可以表示節(jié)點(diǎn)聚類系數(shù)[6]，但是聚類系數(shù)代表的是全部預(yù)測(cè)節(jié)點(diǎn)，并不是局部的，因此對(duì)于不同節(jié)點(diǎn)，所得到的預(yù)測(cè)值相同。這會(huì)影響對(duì)鏈路性能的判斷，因?yàn)椴煌?jié)點(diǎn)在相同的局部網(wǎng)絡(luò)通信情況下?lián)碛信c其對(duì)應(yīng)的聚類信息。

由于邊可以提供很多局部信息特征，因此本文利用邊聚類信息，通過(guò)與相似度指標(biāo)的結(jié)合，判斷邊聚類信息在估計(jì)鏈路性能方面的作用。邊聚類數(shù)可以表示為

(6)

式(6)中，CN(x，z)代表穿過(guò)鏈路(x，z)的三角形個(gè)數(shù)，kx、kz分別代表節(jié)點(diǎn)x、節(jié)點(diǎn)z的度。該表達(dá)式也可描述節(jié)點(diǎn)x對(duì)節(jié)點(diǎn)z的聚類系數(shù)容納度。

三元閉包是通信網(wǎng)絡(luò)中最根本的局部特征與連接機(jī)制，平衡性與穩(wěn)定性較強(qiáng)[7]。所以本文對(duì)估計(jì)節(jié)點(diǎn)存在的端節(jié)點(diǎn)和鄰近節(jié)點(diǎn)的性能加以分析，完成挖掘閉包機(jī)構(gòu)存在的信息特征，因此式(6)能簡(jiǎn)化為以下表達(dá)式

(7)

融合節(jié)點(diǎn)的數(shù)量會(huì)對(duì)邊的聚類系數(shù)造成影響，因此對(duì)鏈路相似性進(jìn)行定義，相似性指標(biāo)表達(dá)式如下所示

(8)

由式(8)簡(jiǎn)化得到下列公式

(9)

上述公式中，相乘因子的首個(gè)分量是鄰近節(jié)點(diǎn)z和端點(diǎn)x造成的影響占比，將該值與邊聚類系數(shù)相乘可以獲得估計(jì)鏈路的局部信息特征量。所以指標(biāo)為鄰近節(jié)點(diǎn)z在通信網(wǎng)絡(luò)中x與y節(jié)點(diǎn)鏈路的信息貢獻(xiàn)總和。節(jié)點(diǎn)與鏈路是移動(dòng)通信網(wǎng)絡(luò)的兩個(gè)關(guān)鍵角度。廣泛挖掘節(jié)點(diǎn)自身和邊構(gòu)成的局部結(jié)構(gòu)對(duì)估計(jì)鏈路的價(jià)值，有顯著優(yōu)勢(shì)。

2.3 通信網(wǎng)絡(luò)鏈路優(yōu)化設(shè)計(jì)

2.3.1 節(jié)點(diǎn)狀態(tài)判斷

根據(jù)上述節(jié)點(diǎn)對(duì)鏈路存在的價(jià)值和節(jié)點(diǎn)狀態(tài)進(jìn)行判斷。由于移動(dòng)通信網(wǎng)絡(luò)的移動(dòng)節(jié)點(diǎn)尋在較強(qiáng)的流動(dòng)性[8]，因此節(jié)點(diǎn)之間只能利用一對(duì)一的方法進(jìn)行信息交互。即不相同節(jié)點(diǎn)的信息交互都不由自身區(qū)域中的節(jié)點(diǎn)傳輸，所以鏈路存在間斷性特點(diǎn)，在任意節(jié)點(diǎn)和某個(gè)節(jié)點(diǎn)進(jìn)行交互時(shí)，取得的鏈路信息并不是完整的。針對(duì)上述問(wèn)題，本文利用本地節(jié)點(diǎn)對(duì)鏈路信息進(jìn)行實(shí)施檢測(cè)，再通過(guò)馬爾科夫信道轉(zhuǎn)移模型完成鏈路建模，結(jié)合采樣時(shí)間段和本地節(jié)點(diǎn)相關(guān)的信息交互節(jié)點(diǎn)狀態(tài)，構(gòu)建矩陣模型。

因?yàn)槿抗?jié)點(diǎn)運(yùn)動(dòng)狀態(tài)的性質(zhì)都屬于有限移動(dòng)狀態(tài)，節(jié)點(diǎn)運(yùn)動(dòng)環(huán)境與最大速度都能夠進(jìn)行測(cè)量，并且區(qū)域與運(yùn)動(dòng)速度不同導(dǎo)致信噪比也隨之產(chǎn)生變化，信噪比情況可以表示為多個(gè)持續(xù)狀態(tài)

T={T1，T2，T3，…Tn}，Tn∈[Ωn，Ωn+1]

(10)

式中，[Ωn，Ωn+1]表示不同信環(huán)境中信噪比取值范圍，設(shè)定信道屬于瑞利信道，衰落情況為緩慢衰落，并且節(jié)點(diǎn)所在的信道較為穩(wěn)定，沒(méi)有跳變情況出現(xiàn)，節(jié)點(diǎn)信道存在的信噪比范圍只會(huì)持續(xù)變化，因此節(jié)點(diǎn)所在的不同信道中具有的轉(zhuǎn)移概率Sn，n+1表示為

Sn，n+1=St{St+1=n+1|St=n}

(11)

式(12)中，St代表在t時(shí)間段上節(jié)點(diǎn)的信噪比情況，Sn，n+1為節(jié)點(diǎn)從t時(shí)間點(diǎn)移動(dòng)到t+1時(shí)間點(diǎn)上信噪比的變換情況。

由于節(jié)點(diǎn)信道全部符合瑞利分布狀態(tài)要求，因此節(jié)點(diǎn)在實(shí)現(xiàn)信息傳輸時(shí)[9，10]，傳輸規(guī)律都屬于瑞利變換規(guī)律，假設(shè)信噪比是ni(x)，則ni(x)計(jì)算模型表示為

(12)

結(jié)合式(10)，獲得節(jié)點(diǎn)在興狀態(tài)時(shí)[Ωn，Ωn+1]的概率ni(n)表示為

(13)

為方便對(duì)式(13)進(jìn)行計(jì)算，對(duì)函數(shù)F(x)進(jìn)行下述定義

(14)

由以上公式可知，假如節(jié)點(diǎn)處在[Ωn，Ωn+1]狀態(tài)，則在t+1時(shí)間點(diǎn)上狀態(tài)轉(zhuǎn)移的概率ni(n)表達(dá)式如下

(15)

式(15)中的f表示現(xiàn)有節(jié)點(diǎn)的頻率轉(zhuǎn)移情況，式(15)T表示節(jié)點(diǎn)運(yùn)動(dòng)情況變化周期。

結(jié)合式(15)獲得節(jié)點(diǎn)狀態(tài)更迭的變化矩陣I表示為

(16)

2.3.2 鏈路最大傳輸帶寬確定

當(dāng)節(jié)點(diǎn)發(fā)生數(shù)據(jù)交互時(shí)，節(jié)點(diǎn)狀態(tài)一定屬于興態(tài)[11]，在下一刻發(fā)生時(shí)才會(huì)進(jìn)行狀態(tài)轉(zhuǎn)移。假如處于當(dāng)前周期T內(nèi)，節(jié)點(diǎn)屬于興態(tài)，則對(duì)該節(jié)點(diǎn)來(lái)說(shuō)，聚集的數(shù)據(jù)帶寬值Bi應(yīng)該滿足下述條件

Bi=T×IT(V×ST)

(17)

式(18)中，T表示節(jié)點(diǎn)數(shù)據(jù)收發(fā)周期，V=(v1，v2，v3，…vn)代表節(jié)點(diǎn)在不同時(shí)間段內(nèi)聚集信息時(shí)丟失的信息量，ST為矩陣的轉(zhuǎn)秩。

假如在t+1時(shí)刻，節(jié)點(diǎn)和鄰近節(jié)點(diǎn)傳輸信息總量為B，假如此節(jié)點(diǎn)傳輸信息總和高于聚集的信息帶寬平均值時(shí)，該節(jié)點(diǎn)會(huì)出現(xiàn)狀態(tài)轉(zhuǎn)移現(xiàn)象，同時(shí)鏈路也會(huì)隨之轉(zhuǎn)移，判斷轉(zhuǎn)移的條件為

B>Bi

(18)

再結(jié)合式(16)可得，在經(jīng)歷t+1時(shí)刻后，表示節(jié)點(diǎn)i狀態(tài)的向量Ri滿足如下條件

Ri(n)=[S0，1，S1，2，S2，3，…，Sn，n+1]

(19)

如果節(jié)點(diǎn)i的狀態(tài)描述為T(mén)i，結(jié)合上述公式獲得該節(jié)點(diǎn)的狀態(tài)表達(dá)式為

Ti=Ri(n)ITIRi(n)T

(20)

公式中Ti為節(jié)點(diǎn)i在該時(shí)刻的興態(tài)，將其設(shè)置為Si，當(dāng)?shù)玫焦?jié)點(diǎn)i的興態(tài)后，對(duì)此興態(tài)進(jìn)行計(jì)算，就可以獲得該節(jié)點(diǎn)在興態(tài)時(shí)鏈路的最大信息傳輸帶寬[12]。

2.3.3 鏈路優(yōu)化

(21)

(22)

經(jīng)過(guò)證明D(c)為凸函數(shù)，g(c)為凹函數(shù)，由于這兩個(gè)函數(shù)在定義域中是持續(xù)可微的，C*在兩個(gè)定義域內(nèi)，因此D(c)與g(c)在C*處屬于連續(xù)可微。C*滿足K-T的要求，所以C*屬于該線性規(guī)劃問(wèn)題的最優(yōu)解。其表達(dá)式為

(23)

3 實(shí)驗(yàn)研究

為了驗(yàn)證基于聚類挖掘的移動(dòng)通信網(wǎng)絡(luò)鏈路優(yōu)化設(shè)計(jì)的效果及可行性，設(shè)置實(shí)驗(yàn)，實(shí)驗(yàn)對(duì)象以一個(gè)公用數(shù)據(jù)移動(dòng)通信網(wǎng)絡(luò)為例。A設(shè)為中心點(diǎn)，B、C、D分別代表1、2、3級(jí)節(jié)點(diǎn)，將這三個(gè)節(jié)點(diǎn)與上一級(jí)節(jié)點(diǎn)互相連接，此時(shí)產(chǎn)生3條鏈路。

為使計(jì)算過(guò)程更加簡(jiǎn)便，設(shè)置3級(jí)節(jié)點(diǎn)的報(bào)文流相同，為1報(bào)文/s，因此整個(gè)通信網(wǎng)絡(luò)的吞吐量為：γ=1×30×5×10=1500。每一級(jí)鏈路產(chǎn)生的報(bào)文流量記為：λ1=120、λ2=50、λ2=5。假如每條鏈路上的報(bào)文長(zhǎng)度都相等，1/μ=1000。C*表示鏈路容量，D*為鏈路消耗，T*代表網(wǎng)絡(luò)通信平均延時(shí)。為更直觀看出本文方法優(yōu)越性，下述對(duì)比圖分別從移動(dòng)網(wǎng)絡(luò)通信中斷概率、鏈路信噪比與傳輸功率方面進(jìn)行對(duì)比描述。

從圖1到圖3可以看出，在用戶數(shù)量增加的前提下，所提方法的中端概率比文獻(xiàn)[1]方法和文獻(xiàn)[2]方法小，且信噪比高，保證通信質(zhì)量，在迭代次數(shù)增加時(shí)，傳輸功率有所降低，從而減少了對(duì)用戶的干擾。使用本文方法與文獻(xiàn)[1]方法和文獻(xiàn)[2]方法進(jìn)行優(yōu)化對(duì)比實(shí)驗(yàn)，其結(jié)果如表1所示：

圖1 不同方法傳輸中斷概率對(duì)比圖

圖2 不同方法鏈路信噪比對(duì)比圖

圖3 不同方法傳輸功率對(duì)比圖

表1 不同優(yōu)化方法仿真對(duì)比結(jié)果

根據(jù)表1可以看出，經(jīng)過(guò)不同方法對(duì)通信鏈路進(jìn)行優(yōu)化后，所提方法的鏈路容量最大，鏈路消耗與傳輸平均延時(shí)均低于文獻(xiàn)[1]、文獻(xiàn)[2]方法。

4 結(jié)論

移動(dòng)通信網(wǎng)絡(luò)鏈路優(yōu)化屬于多目標(biāo)優(yōu)化問(wèn)題，要想找到最佳解較為困難，因此本文提出基于聚類挖掘的移動(dòng)通信網(wǎng)絡(luò)鏈路優(yōu)化設(shè)計(jì)。通過(guò)對(duì)聚類挖掘算法的分析，對(duì)失效鏈路進(jìn)行估計(jì)，減少無(wú)用鏈路對(duì)整體網(wǎng)絡(luò)結(jié)構(gòu)的干擾；挖掘節(jié)點(diǎn)與鄰近節(jié)點(diǎn)對(duì)鏈路優(yōu)化的作用，并通過(guò)馬爾科夫轉(zhuǎn)移法構(gòu)建通信鏈路矩陣，獲取最佳解，完成鏈路優(yōu)化。仿真表明聚類挖掘方法用于鏈路優(yōu)化中性能良好，適用于不同環(huán)境下的鏈路容量?jī)?yōu)化。