基于聚類挖掘的移動通信網絡鏈路優化設計

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

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

1 引言

隨著移動網絡通信迅速技術發展，人們將注意力從網絡通信設計的拓撲優化、信道容量的合理分配等問題轉向了應充分利用信道能力，減少虛耗現象，從而使移動通信網絡鏈路優化設計成為重點。鏈路優化是將網絡與信息傳輸緊密聯系的重要橋梁，通信網絡中的鏈路優化表示根據尚有的網絡節點與結構特征，對節點連接方式進行優化。由于移動網絡通信結構較為復雜，且統計數量龐大，很難對不同機制的性能進行比較，而鏈路優化可以為其提供平臺，有助于提升復雜通信網絡的穩定性。傳統鏈路優化方法對節點密度影響考慮較少，在節點密度超高時，鏈路優化的性能會大大降低，為此相關學者對移動通信網絡鏈路問題做了大量研究。

文獻[1]提出基于高階近似的鏈路優化方法。首先對通信網絡的歸一化相鄰矩陣與相似度矩陣進行構建，并分解相似度矩陣，獲得節點表示的向量數值；其次利用高階網絡對相似度矩陣進行優化處理，并獲取更高階矩陣函數表達式，最后通過在真實數據集合中的多次試驗，將優化后的鏈路與原始鏈路對比，證明該優化方法的可行性。

文獻[2]在高負載MANET環境下，提出基于灰色區域估計的自適應鏈路優化方法。通過對基于卡爾曼濾波的灰色區域預測分析，計算通信過程信噪比，判斷鏈路狀態情況，并在鏈路發生失效之前，重新選擇新路由，提高效率；處理通信網絡中的灰色區域，利用多路徑冗余傳輸方式提高鏈路性能的同時改善網絡通信質量。

雖然上述方法在一定程度上改善了鏈路性能，但是在通信過程中，傳輸功能受到帶寬限制，基于此，本文在聚類挖掘基礎上對移動通信網絡鏈路優化進行設計。聚類挖掘算法是根據統計學的聚類分析方法對數據信息進行挖掘。通過對聚類挖掘各項指標的分析，獲取節點特性，判斷鏈路最佳帶寬值，根據非線性規劃原理實現鏈路優化設計。所提方法能夠提升通信節點帶寬，減少節點擁塞現象發生，實現移動通信網絡鏈路優化。

2 方法

2.1 通訊網絡聚類挖掘算法原理

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

其鏈路優化過程如下述內容所示：

1)在通信網絡中存在節點x，將其附近集合表示為Γ(x)，節點x與y的相似程度可以表示它們相同的鄰近節點數量[4]。

2)通過兩個節點相同鄰近節點數量在節點總數量中所占比重，對節點x與y的相似性進行描述

(1)

式中，Γ(y)表示通信網絡中的節點y附近集合。

3)按照最佳比例權重對鄰近集合中的節點進行合理分配[5]，任意節點的權重表示為

(2)

4)作為通信網絡整體結構的估計方式，對網絡中全部路徑進行考慮。其表達式為

(3)

5)利用x與y節點之間存在的不同路徑數量，描述節點之間相似度。表達式為

(4)

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

6)將共同鄰近節點數據以節點聚類系數的方式體現出來，把x與y節點存在的相似度作為鄰近節點的系數之和

(5)

式中，tz表示經過節點z的三角形個數。

2.2 聚類邊信息獲取

通常情況下，聚類信息可以表示節點聚類系數[6]，但是聚類系數代表的是全部預測節點，并不是局部的，因此對于不同節點，所得到的預測值相同。這會影響對鏈路性能的判斷，因為不同節點在相同的局部網絡通信情況下擁有與其對應的聚類信息。

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

(6)

式(6)中，CN(x，z)代表穿過鏈路(x，z)的三角形個數，kx、kz分別代表節點x、節點z的度。該表達式也可描述節點x對節點z的聚類系數容納度。

三元閉包是通信網絡中最根本的局部特征與連接機制，平衡性與穩定性較強[7]。所以本文對估計節點存在的端節點和鄰近節點的性能加以分析，完成挖掘閉包機構存在的信息特征，因此式(6)能簡化為以下表達式

(7)

融合節點的數量會對邊的聚類系數造成影響，因此對鏈路相似性進行定義，相似性指標表達式如下所示

(8)

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

(9)

上述公式中，相乘因子的首個分量是鄰近節點z和端點x造成的影響占比，將該值與邊聚類系數相乘可以獲得估計鏈路的局部信息特征量。所以指標為鄰近節點z在通信網絡中x與y節點鏈路的信息貢獻總和。節點與鏈路是移動通信網絡的兩個關鍵角度。廣泛挖掘節點自身和邊構成的局部結構對估計鏈路的價值，有顯著優勢。

2.3 通信網絡鏈路優化設計

2.3.1 節點狀態判斷

根據上述節點對鏈路存在的價值和節點狀態進行判斷。由于移動通信網絡的移動節點尋在較強的流動性[8]，因此節點之間只能利用一對一的方法進行信息交互。即不相同節點的信息交互都不由自身區域中的節點傳輸，所以鏈路存在間斷性特點，在任意節點和某個節點進行交互時，取得的鏈路信息并不是完整的。針對上述問題，本文利用本地節點對鏈路信息進行實施檢測，再通過馬爾科夫信道轉移模型完成鏈路建模，結合采樣時間段和本地節點相關的信息交互節點狀態，構建矩陣模型。

因為全部節點運動狀態的性質都屬于有限移動狀態，節點運動環境與最大速度都能夠進行測量，并且區域與運動速度不同導致信噪比也隨之產生變化，信噪比情況可以表示為多個持續狀態

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

(10)

式中，[Ωn，Ωn+1]表示不同信環境中信噪比取值范圍，設定信道屬于瑞利信道，衰落情況為緩慢衰落，并且節點所在的信道較為穩定，沒有跳變情況出現，節點信道存在的信噪比范圍只會持續變化，因此節點所在的不同信道中具有的轉移概率Sn，n+1表示為

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

(11)

式(12)中，St代表在t時間段上節點的信噪比情況，Sn，n+1為節點從t時間點移動到t+1時間點上信噪比的變換情況。

由于節點信道全部符合瑞利分布狀態要求，因此節點在實現信息傳輸時[9，10]，傳輸規律都屬于瑞利變換規律，假設信噪比是ni(x)，則ni(x)計算模型表示為

(12)

結合式(10)，獲得節點在興狀態時[Ωn，Ωn+1]的概率ni(n)表示為

(13)

為方便對式(13)進行計算，對函數F(x)進行下述定義

(14)

由以上公式可知，假如節點處在[Ωn，Ωn+1]狀態，則在t+1時間點上狀態轉移的概率ni(n)表達式如下

(15)

式(15)中的f表示現有節點的頻率轉移情況，式(15)T表示節點運動情況變化周期。

結合式(15)獲得節點狀態更迭的變化矩陣I表示為

(16)

2.3.2 鏈路最大傳輸帶寬確定

當節點發生數據交互時，節點狀態一定屬于興態[11]，在下一刻發生時才會進行狀態轉移。假如處于當前周期T內，節點屬于興態，則對該節點來說，聚集的數據帶寬值Bi應該滿足下述條件

Bi=T×IT(V×ST)

(17)

式(18)中，T表示節點數據收發周期，V=(v1，v2，v3，…vn)代表節點在不同時間段內聚集信息時丟失的信息量，ST為矩陣的轉秩。

假如在t+1時刻，節點和鄰近節點傳輸信息總量為B，假如此節點傳輸信息總和高于聚集的信息帶寬平均值時，該節點會出現狀態轉移現象，同時鏈路也會隨之轉移，判斷轉移的條件為

B>Bi

(18)

再結合式(16)可得，在經歷t+1時刻后，表示節點i狀態的向量Ri滿足如下條件

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

(19)

如果節點i的狀態描述為Ti，結合上述公式獲得該節點的狀態表達式為

Ti=Ri(n)ITIRi(n)T

(20)

公式中Ti為節點i在該時刻的興態，將其設置為Si，當得到節點i的興態后，對此興態進行計算，就可以獲得該節點在興態時鏈路的最大信息傳輸帶寬[12]。

2.3.3 鏈路優化

(21)

(22)

經過證明D(c)為凸函數，g(c)為凹函數，由于這兩個函數在定義域中是持續可微的，C*在兩個定義域內，因此D(c)與g(c)在C*處屬于連續可微。C*滿足K-T的要求，所以C*屬于該線性規劃問題的最優解。其表達式為

(23)

3 實驗研究

為了驗證基于聚類挖掘的移動通信網絡鏈路優化設計的效果及可行性，設置實驗，實驗對象以一個公用數據移動通信網絡為例。A設為中心點，B、C、D分別代表1、2、3級節點，將這三個節點與上一級節點互相連接，此時產生3條鏈路。

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

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

圖1 不同方法傳輸中斷概率對比圖

圖2 不同方法鏈路信噪比對比圖

圖3 不同方法傳輸功率對比圖

表1 不同優化方法仿真對比結果

根據表1可以看出，經過不同方法對通信鏈路進行優化后，所提方法的鏈路容量最大，鏈路消耗與傳輸平均延時均低于文獻[1]、文獻[2]方法。

4 結論

移動通信網絡鏈路優化屬于多目標優化問題，要想找到最佳解較為困難，因此本文提出基于聚類挖掘的移動通信網絡鏈路優化設計。通過對聚類挖掘算法的分析，對失效鏈路進行估計，減少無用鏈路對整體網絡結構的干擾；挖掘節點與鄰近節點對鏈路優化的作用，并通過馬爾科夫轉移法構建通信鏈路矩陣，獲取最佳解，完成鏈路優化。仿真表明聚類挖掘方法用于鏈路優化中性能良好，適用于不同環境下的鏈路容量優化。