抵御相繼故障的無線網(wǎng)絡(luò)路由增強算法研究

郭艷光，何 婷，魯曉波

(內(nèi)蒙古農(nóng)業(yè)大學(xué)計算機技術(shù)與信息管理系，內(nèi)蒙古 包頭 014109)

1 引言

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

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

為了解決上述方法中存在的問題，對抵御相繼故障的無線網(wǎng)絡(luò)路由增強算法進(jìn)行研究。

2 相繼故障模型

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

2.1 負(fù)荷-容量原理

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

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

2.2 二值影響模型

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

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

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

(1)

式中，δ代表符號函數(shù)。

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

(2)

式中

(3)

(4)

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

2.3 耦合印象格子模型

常規(guī)狀態(tài)下，耦合印象格子模型為拓?fù)浣Y(jié)構(gòu)，且具有一定的規(guī)則可循[11]。對數(shù)量為N的節(jié)點的耦合印象格子模型進(jìn)行定義，具體如下：

xi(t+1)

(5)

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

A=(aij)N×N

(6)

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

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

1)如果0

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

(7)

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

3 無線網(wǎng)絡(luò)路由增強算法研究

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

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

(8)

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

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

(9)

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

(10)

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

(11)

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

(12)

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

(13)

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

1)單位時間內(nèi)，可通過整個網(wǎng)絡(luò)完成對節(jié)點虛擬負(fù)載的處理操作；

2)若網(wǎng)絡(luò)中所有節(jié)點均包含虛擬負(fù)載，那么i節(jié)點的虛擬負(fù)載可通過下式進(jìn)行表達(dá)

(14)

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

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

(15)

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

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

(16)

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

(17)

式中，h表示可調(diào)參數(shù)，且該參數(shù)對節(jié)點有著極大影響，h參數(shù)數(shù)值越大，對關(guān)鍵節(jié)點產(chǎn)生的削弱作用越大。

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

4 實驗結(jié)果與分析

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

1)平均傳輸效率對比

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

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

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

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

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

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

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

3)故障檢測準(zhǔn)確率對比

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

圖3 不同算法的故障檢測準(zhǔn)確率

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

5 結(jié)論

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