抵御相繼故障的無線網絡路由增強算法研究

郭艷光，何 婷，魯曉波

(內蒙古農業(yè)大學計算機技術與信息管理系，內蒙古 包頭 014109)

1 引言

無線網絡中節(jié)點之間均存在耦合關系[1]，因此當某節(jié)點發(fā)生故障時，會導致其它節(jié)點或者邊隨之發(fā)生故障，產生連鎖反應，最后形成相繼故障[2-4]。為了有效抵御相繼故障的發(fā)生，減少相繼故障帶來的危害，提升網絡的可靠性，提出一種抵御相繼故障的無線網絡路由增強算法顯得尤為重要和迫切[5]。

蔣占軍[6]等人提出基于改進蟻群算法的無線網絡路由增強算法，該算法首先將限制搜索角、距離帶以及距離因子進行融合，同時利用激勵機制對“熱”節(jié)點中所包含的路徑較長、能量較低的節(jié)點進行剔除處理。其次通過跳數少且能力足的節(jié)點對“熱”節(jié)點傳輸進行均衡處理。最后利用偽隨機比例規(guī)則對概率轉移函數進行優(yōu)化處理，實現對無線路由的增強。實驗結果表明，該算法能夠有效對節(jié)點進行均衡處理，但是該算法沒有將耦合印象格子模型的網絡拓撲結構影響充分體現至鏈路傳輸效率中，節(jié)點負載具有較高的異質性，傳輸能力偏弱，導致該算法的平均傳輸效率較低，且在故障檢測中消耗的時間較長。劉寧[7]等人提出基于貝葉斯聯(lián)合博弈的無線網絡路由增強算法，該算法首先通過節(jié)點信念更新參數獲取網絡中所有的不良節(jié)點，利用所獲取的不良節(jié)點對網絡環(huán)境進行預估。其次歸一化處理所預估的網絡環(huán)境聯(lián)合信念概率，通過各節(jié)點安全效益數值的計算結果獲取相對合約，并利用先驗中期拒絕貝斯穩(wěn)態(tài)合約。最后根據安全容量計算權值對網絡中不良節(jié)點進行處理，實現無線網絡路由增強算法的研究。實驗結果表明，該算法沒有充分研究分析負荷-容量模型，導致所分析的相繼故障產生原因較為片面，因此，該算法的故障檢測準確率較低。除此之外，還有學者提出了基于改進支持向量機的無線網絡路由增強算法，該算法雖然能夠完成對無線網絡路由的增強，但是該算法沒有對二值影響模型進行研究，對不同節(jié)點狀態(tài)及時間下故障節(jié)點產生條件進行分析，導致該算法在故障檢測中消耗時間的較長[8，9]。

為了解決上述方法中存在的問題，對抵御相繼故障的無線網絡路由增強算法進行研究。

2 相繼故障模型

在以往的網絡模型研究中，只有節(jié)點的動態(tài)行為會被納入到考慮范圍內。但是隨著網絡問題不斷地發(fā)生，邊的動態(tài)行為以及邊和節(jié)點的綜合動態(tài)行為也被納入到了考慮范圍內。因此，依據負荷-容量原理，通過構建多個模型可以對相繼故障發(fā)生的原因做出相對直觀與全面的分析。

2.1 負荷-容量原理

在負荷-容量模型中，所有節(jié)點都會被定義成一個負荷量或一個容量。容量代表安全閾值[10]，即模型中每一個節(jié)點能夠負荷的最大值。當其中一個節(jié)點因為某種特殊原因超出所能承受的最大負荷時，該節(jié)點就會產生故障問題并脫離網絡，那么該節(jié)點所屬的負荷就會被分配給其它相關的節(jié)點，在其它節(jié)點接收到額外負荷后，也有可能產生同樣的問題。以此類推，重復發(fā)生類似情況，節(jié)點的負荷被一次又一次地向下分配，故障問題不斷發(fā)生，導致網絡中失效的節(jié)點數量也不斷增加，越來越多的節(jié)點從網絡中脫離，因此產生了相繼故障。

因為在負荷-容量模型中，對負荷、容量兩定義的設定以及產生故障時節(jié)點負荷的分配條件都不是唯一的。因此，負荷-容量原理對于相繼故障研究而言有著極為重要的意義。

2.2 二值影響模型

根據無線網絡負荷-容量原理，構建一個隨機網絡具有N個節(jié)點，Pk代表節(jié)點分布，同時在該網絡中，任意節(jié)點都必須包含故障及正常兩種狀態(tài)，分別用1和0進行表示。在某一時刻，網絡中節(jié)點故障的發(fā)生與否完全取決于與其相鄰的節(jié)點。設定初始時間并保證在當下時間內網絡中的所有節(jié)點都是正常狀態(tài)，即t=0，并且令該網絡中含有極少的故障節(jié)點。因此，在即將發(fā)生的時間內，網絡中是否會產生新的故障節(jié)點取決于下述條件：

1)如果網絡中某節(jié)點的鄰節(jié)點數量為n個，故障節(jié)點數量與n之比大于轉換閾值φ，密度函數如下式

f(φ)=δ(φ-φ*)n

(1)

式中，δ代表符號函數。

2)假設節(jié)點的度是k，則故障發(fā)生的概率用Pk進行表示，并對最有可能發(fā)生故障的節(jié)點的度函數進行定義，如下式

(2)

式中

(3)

(4)

式中，該節(jié)點是值為1的故障節(jié)點，且不會隨著網絡狀態(tài)的改變而產生變化。若在該網絡中節(jié)點的轉換閾值與度分布符合某種條件，那么極小部分的故障節(jié)點會引發(fā)相繼故障。

2.3 耦合印象格子模型

常規(guī)狀態(tài)下，耦合印象格子模型為拓撲結構，且具有一定的規(guī)則可循[11]。對數量為N的節(jié)點的耦合印象格子模型進行定義，具體如下：

xi(t+1)

(5)

式中，i=1，2，3，…N；k(i)代表節(jié)點i的參數度代表與其鄰接的節(jié)點數量；ε代表耦合度，且ε∈(0，1)。時刻為t時節(jié)點i的狀態(tài)量通過xi(t)進行表示。節(jié)點間的連接關系通過鄰接矩陣進行表達，如下式

A=(aij)N×N

(6)

若i、j兩節(jié)點之間存在邊連接，則aij=1，反之，aij=0。

網絡中所有節(jié)點都沒有自環(huán)[12]，同時每對節(jié)點中間有且僅有一條邊。利用Logistic進行混沌映射的同時，通過f對節(jié)點的自身動態(tài)行為進行定義

1)如果0

2)相反，如果0m，且xi(m)≥1，那么時間m內i節(jié)點始終是故障節(jié)點，同時在未來時間內故障節(jié)點狀態(tài)始終是正常狀態(tài)。m時間下c節(jié)點會被R所干擾，且R≥1，綜合以上分析，假設

(7)

式中，m時間下c節(jié)點產生故障，若t>m，則xc(t)=0；當時間為m+1，c節(jié)點的相鄰接點將被xc(m)所干擾，同時在很大程度上其狀態(tài)值將大于1。因此，有可能產生新的故障節(jié)點并引發(fā)相繼故障。

3 無線網絡路由增強算法研究

為了更好地解決相繼故障問題，以二值影響模型和耦合印象格子模型為基礎，對無線網絡路由算法進行研究，將最短路徑路由算法進行改進，從而有效提高相繼故障的抵御能力。

首先構建一個網絡，通過G進行表示，同時利用A代表在該網絡中所有相鄰節(jié)點的鄰接矩陣，具體如下式

(8)

式中，aij表示鄰接矩陣A中所包含的某一元素；i、j兩節(jié)點的連接通過eij進行表示。

假設在上述建立的網絡中有n個節(jié)點，且該網絡中包含實際耗費因子向量，則

(9)

通過該向量可以獲取到網絡中由于節(jié)點與其鄰邊傳輸所產生的實際耗費影響。同時邊傳輸產生的實際耗費也可通過節(jié)點實際耗費因子獲得，具體如下式

(10)

節(jié)點之間度數的分布存在著異質性的特點，因此需要充分利用節(jié)點度數修改實際耗費因子并獲取到其虛擬耗費因子，避免度數較大節(jié)點負擔過重等情況的發(fā)生。對i節(jié)點的虛擬耗費因子進行設定，具體如下式

(11)

對上式進行計算，可獲得節(jié)點的虛擬耗費因子向量，具體如下

(12)

同時，通過式(12)可以獲得參數eij的虛擬耗費值，具體如下式

(13)

節(jié)點的度數以及實際耗費因子對節(jié)點虛擬耗費因子的確定起著決定性的作用，因此需要對節(jié)點度數進行計算，并做出如下假設：

1)單位時間內，可通過整個網絡完成對節(jié)點虛擬負載的處理操作；

2)若網絡中所有節(jié)點均包含虛擬負載，那么i節(jié)點的虛擬負載可通過下式進行表達

(14)

式中，ki表示i節(jié)點的度數值。

3)單位時間內，節(jié)點度數與其可成功處理的負載成正比，但是節(jié)點虛擬負載與所求出的數值成反比。

(15)

式中，βi代表一定時間段中節(jié)點所解決的虛擬負載；βj代表虛擬負載的總和。被傳遞給節(jié)點自身和鄰節(jié)點的負載分別通過1以及βi×ki進行表示。若參數kj的值為0，那么與其相對應的參數βj值也等于0。

通過對式(15)的計算，可獲得如下公式

(16)

通過對上述公式的計算分析可獲得節(jié)點的虛擬耗費因子，具體如下式

(17)

式中，h表示可調參數，且該參數對節(jié)點有著極大影響，h參數數值越大，對關鍵節(jié)點產生的削弱作用越大。

利用上述算法可有效控制節(jié)點度數較大時由于負載所產生的相關問題，該算法不僅有效地提升了網絡中節(jié)點之間的負載平衡性，同時也提升了抵御相繼故障發(fā)生的能力。

4 實驗結果與分析

為了驗證所提方法的整體有效性，需要對所提方法進行測試。通過MATLAB實驗環(huán)境，分別采用抵御相繼故障的無線網絡路由增強算法研究(所提算法)、基于改進蟻群算法的無線網絡路由增強算法(算法1)和基于貝葉斯聯(lián)合博弈的無線網絡路由增強算法(算法2)進行測試。

1)平均傳輸效率對比

圖1代表平均傳輸效率測試結果如圖1所示。

圖1 不同算法的平均傳輸效率

平均傳輸效率越高代表算法的傳輸能力越強，網絡狀態(tài)越好。由圖1可知，在初始故障節(jié)點不斷增加的狀態(tài)下，三種算法的網絡平均傳輸效率均呈現出先快速提升后減緩的趨勢。但是所提算法相對于其它兩種算法，平均傳輸效率較高，說明運用所提算法對無線網絡路由進行增強后，網絡狀態(tài)更好。

2)故障檢測消耗時間對比

圖2代表故障節(jié)點不斷增長的狀態(tài)下，不同算法在故障檢測中所消耗的時間。

圖2 不同算法故障檢測消耗時間

通過圖2可以看出在故障節(jié)點數量不斷增長的過程中，不同算法的消耗時間整體上呈上漲趨勢，但所提算法所消耗的時間始終低于其它兩種算法。因為所提通過修改節(jié)點傳輸過程中產生的實際耗費獲得了節(jié)點的虛擬耗費，有效降低了大度數節(jié)點的數量，從而減少了大度數節(jié)點路徑計算所消耗的時間。

3)故障檢測準確率對比

圖3代表不同故障節(jié)點數量下，不同算法的故障檢測結果準確率。

圖3 不同算法的故障檢測準確率

由圖3可知，所提算法的故障節(jié)點檢測準確率高于其它兩種算法，其檢測準確率最高值達到了90%以上，因為該算法通過對負荷-容量原理進行分析，準確直觀地分析了相繼故障的產生原因，因此大大增強了網絡故障節(jié)點檢測準確率。

5 結論

網絡技術的不斷發(fā)展給當今社會生活帶來了極大的便利，但是網絡的相繼故障問題也給網絡化社會帶來了巨大的挑戰(zhàn)。目前無線網絡路由增強算法存在平均傳輸效率較低、故障檢測所消耗時間較長以及故障檢測準確率較低等問題，因此提出抵御相繼故障的無線網絡路由增強算法研究，首先在構建相繼故障模型的基礎上對最短路徑路由算法進行改進，其次將獲取到的大度數節(jié)點進行重要性降低處理，最后利用該節(jié)點均衡節(jié)點負載分布。在有效提升了負載均衡性的同時減小了關鍵節(jié)點對網絡產生的影響，進而提升了相繼故障的抵御能力。