基于離散變量和FW-PSO的網(wǎng)絡(luò)拓?fù)鋬?yōu)化的算法

邵 杰,劉 晶

(1. 遼東學(xué)院數(shù)學(xué)系,遼寧 丹東 118000;2. 遼寧石油化工大學(xué)理學(xué)院,遼寧 撫順 113000)

1 引言

近年來,隨著網(wǎng)絡(luò)技術(shù)的不斷進步,無線傳感網(wǎng)絡(luò)[1]自尖端領(lǐng)域走入千家萬戶,成為人們?nèi)粘Ｉ钪斜夭豢缮俚囊徊糠?。無線傳感網(wǎng)絡(luò)具有靈活性強、可靠性高的特性,但是由于無線傳感網(wǎng)絡(luò)應(yīng)用環(huán)境復(fù)雜,傳感器本身極易衰變,從而導(dǎo)致信號在傳輸過程中發(fā)生中斷現(xiàn)象。其中,傳感器網(wǎng)絡(luò)經(jīng)過長時間工作后,會出現(xiàn)傳輸能量受限問題,這時提出有效的無線傳感網(wǎng)絡(luò)[2]拓?fù)鋬?yōu)化算法,對傳感器網(wǎng)絡(luò)進行拓?fù)鋬?yōu)化處理,能夠有效降低無線傳感網(wǎng)絡(luò)因為時長帶來的故障問題。

文獻[3]提出分布式綜合化航空電子網(wǎng)絡(luò)拓?fù)鋬?yōu)化技術(shù)。該算法基于優(yōu)化組合方法對網(wǎng)絡(luò)數(shù)據(jù)進行計算,依據(jù)計算結(jié)果獲取全局最優(yōu)解;通過預(yù)計路徑算法對網(wǎng)絡(luò)路徑進行初步估計,從而減少優(yōu)化時間;最后整合獲取的全局最優(yōu)解以及最佳路徑,完成網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)優(yōu)化。該算法在進行拓?fù)鋬?yōu)化時,未能離散化網(wǎng)絡(luò)數(shù)據(jù),獲取網(wǎng)絡(luò)離散變量,所以該算法的網(wǎng)絡(luò)節(jié)點覆蓋度不高。文獻[4]提出多狀態(tài)空間信息網(wǎng)絡(luò)拓?fù)渖蓛?yōu)化算法。該算法基于網(wǎng)絡(luò)動態(tài)特性建立網(wǎng)絡(luò)拓?fù)渲芷?依據(jù)可視性、連接程度等基本要求制定相關(guān)約束條件以及網(wǎng)絡(luò)拓?fù)鋬?yōu)化目標(biāo),并以此建立拓?fù)涠嗄繕?biāo)優(yōu)化模型;最后使用模擬退火算法求解模型,獲取全局最優(yōu)解實現(xiàn)拓?fù)浣Y(jié)構(gòu)的優(yōu)化。該算法在建立拓?fù)淠Ｐ蜁r存在誤差,所以該算法的網(wǎng)絡(luò)能耗大。文獻[5]提出基于GSO算法的無線監(jiān)測網(wǎng)絡(luò)拓?fù)鋬?yōu)化方法。該算法依據(jù)建立網(wǎng)絡(luò)無線單、雙跳能耗模型獲取能耗最小目標(biāo),監(jiān)測范圍、節(jié)點距離等指標(biāo),并以此構(gòu)建網(wǎng)絡(luò)拓?fù)鋬?yōu)化模型;最后通過GSO算法對模型進行求解,從而實現(xiàn)網(wǎng)絡(luò)的拓?fù)鋬?yōu)化。該算法制定約束條件時存在問題,所以該算法的優(yōu)化性能差。

為解決上述網(wǎng)絡(luò)拓?fù)鋬?yōu)化過程中存在的問題,提出基于離散變量和FW-PSO的網(wǎng)絡(luò)拓?fù)鋬?yōu)化的算法。

2 獲取離散變量

在對無線傳感網(wǎng)絡(luò)進行拓?fù)浣Y(jié)構(gòu)優(yōu)化前,需要使用統(tǒng)計相關(guān)系數(shù)[6]對網(wǎng)絡(luò)數(shù)據(jù)進行離散化處理,獲取網(wǎng)絡(luò)的離散變量。

2.1 獲取相關(guān)系數(shù)

由于網(wǎng)絡(luò)數(shù)據(jù)之間具有關(guān)聯(lián)性,所以對網(wǎng)絡(luò)數(shù)據(jù)進行統(tǒng)計時,可將衡量數(shù)據(jù)變量作為數(shù)據(jù)相關(guān)系數(shù)。設(shè)定網(wǎng)絡(luò)中兩個數(shù)據(jù)的相關(guān)系數(shù)為λ,自變量標(biāo)記成x形式,因變量標(biāo)記成y形式,網(wǎng)絡(luò)系數(shù)的相關(guān)系數(shù)獲取結(jié)果如下式所示

(1)

式中,變量y的最大值標(biāo)記為My,數(shù)據(jù)樣本出現(xiàn)次數(shù)標(biāo)記為N。基于上述計算結(jié)果獲取網(wǎng)絡(luò)數(shù)據(jù)離散化標(biāo)準(zhǔn)[7],結(jié)果如下式所示

(2)

1)數(shù)據(jù)各自的對應(yīng)類別均屬同類。

2)數(shù)據(jù)各自對應(yīng)類別均不相同。

若計算出的數(shù)據(jù)屬于第一種情況,那么數(shù)據(jù)集中最大樣本數(shù)量較多,數(shù)據(jù)相關(guān)系數(shù)較小,證明數(shù)據(jù)之間類別、屬性不相關(guān)。若為第二種情況,數(shù)據(jù)集最大樣本數(shù)量較少,數(shù)據(jù)相關(guān)性較強,證明二者之間存在強相關(guān)性。由此可知,使用相關(guān)系數(shù)作為網(wǎng)絡(luò)數(shù)據(jù)的離散化標(biāo)準(zhǔn)較為合理。

2.2 停止準(zhǔn)則

在對網(wǎng)絡(luò)數(shù)據(jù)進行離散化時,不僅需要獲取相關(guān)離散化標(biāo)準(zhǔn),還需要提出一個停止準(zhǔn)則。使用β-近似精度控制法對數(shù)據(jù)離散信息進行控制,以防止信息出現(xiàn)丟失現(xiàn)象,并允許數(shù)據(jù)中存有錯誤,達到對離散化數(shù)據(jù)[8]與分類數(shù)據(jù)之間權(quán)衡的目的。

設(shè)定數(shù)據(jù)集類別為S,其中包括數(shù)據(jù)屬性集A、屬性取值集合V,數(shù)據(jù)論域U以及集合映射F。其中,A=C∪D,決策屬性集為D,條件屬性集為C。

將論域子集設(shè)定成X?U形式,數(shù)據(jù)近似精度控制值獲取過程如下式所示

(3)

式中,數(shù)據(jù)等價關(guān)系標(biāo)記為P,數(shù)據(jù)論域在等價關(guān)系下的元素集合標(biāo)記為[x]P,基數(shù)標(biāo)記為CP(Y|xi)。數(shù)據(jù)樣本近似控制值能夠決定數(shù)據(jù)的正確分類程度。

基于上述計算結(jié)果,對條件屬性集C的近似精度進行具體表述,結(jié)果如下式所示

(4)

式中,網(wǎng)絡(luò)數(shù)據(jù)樣本點的決策屬性[9]分類程度標(biāo)記為Cβ(D),樣本點分類精準(zhǔn)度為γβ。

網(wǎng)絡(luò)數(shù)據(jù)在離散化過程中,設(shè)定數(shù)據(jù)容忍丟失度閾值為ξ。當(dāng)計算出的原始網(wǎng)絡(luò)數(shù)據(jù)β-近似精度γβ-original大于離散數(shù)據(jù)β-近似精度γβ-discretized時,即可將其看作γβ-original-γβ-discretized>ξ,這時可停止離散化。

2.3 離散流程

網(wǎng)絡(luò)數(shù)據(jù)的離散化過程如下:

1)設(shè)定數(shù)據(jù)集類別為S,樣本屬性為m。

2)對無線傳感網(wǎng)絡(luò)原始數(shù)據(jù)進行計算,獲取數(shù)據(jù)的β-近似精度γβ-original。

3)對網(wǎng)絡(luò)數(shù)據(jù)的屬性值進行排序處理,獲取排序結(jié)果{d1,d2,…,dn},并對其進行初始化。

4)計算數(shù)據(jù)屬性的候選斷點,并通過屬性區(qū)間獲取數(shù)據(jù)的sc2值。將其中sc2值最大的斷點作為離散結(jié)束斷點。

5)對網(wǎng)絡(luò)數(shù)據(jù)當(dāng)前β-近似精度進行計算,依據(jù)建立的停止準(zhǔn)則γβ-original-γβ-discretized>ξ,判斷是否停止數(shù)據(jù)的離散化。

最后通過上述流程實現(xiàn)無線傳感網(wǎng)絡(luò)[10]的離散化處理,獲取網(wǎng)絡(luò)數(shù)據(jù)的離散化變量。

3 網(wǎng)絡(luò)拓?fù)鋬?yōu)化

基于獲取的網(wǎng)絡(luò)數(shù)據(jù)離散變量建立網(wǎng)絡(luò)拓?fù)鋬?yōu)化模型,通過FW-PSO算法對模型進行求解實現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化。

3.1 算法描述

3.1.1 粒子群算法

設(shè)定粒子群數(shù)量為n,搜索空間為D維,粒子的位置標(biāo)記為Xi,速度標(biāo)記為Vi,最佳搜索位置用Pi表述,全局粒子最佳位置標(biāo)記為Pg。粒子的搜索速度與位置的獲取過程如下式所示:

(5)

式中,加速因子標(biāo)記為c1、c2,隨機數(shù)用r1、r2表述,慣性權(quán)值標(biāo)記為w,獲取的粒子搜索速度標(biāo)記為vid(t),粒子位置標(biāo)記為xid(t)。

使用線性遞減策略[11]計算粒子群慣性權(quán)值,結(jié)果如下式所示

(6)

式中,粒子群的最小權(quán)重標(biāo)記為wmin,最大慣性權(quán)重用wmax標(biāo)記,迭代次數(shù)標(biāo)記為iter,最大迭代值用itermax表示。

3.1.2 煙花算法

一般情況下,煙花算法[12]由爆炸算子、變異算子以及選擇策略組成。設(shè)定煙花數(shù)量為Num,煙花的爆炸半徑標(biāo)記為Ai,火花數(shù)目標(biāo)記為Si,二者的獲取過程如下式所示

(7)

式中,常數(shù)標(biāo)記成A、M形式,適應(yīng)度值標(biāo)記為f(xi)形式,計算精度用ε表示,最小適應(yīng)度值標(biāo)記為ymin、最大適應(yīng)度值用ymax表示。

在上述計算結(jié)果中加入高斯變異算子,提升煙花[13]多樣性,過程如下式所示

(8)

式中,均值方差標(biāo)記為e形式,變異算子為xik。使用輪盤算法,選擇固定的適應(yīng)度值對上述計算結(jié)果進行迭代處理,結(jié)果如下式所示

(9)

式中,爆炸煙花與變異煙花集合標(biāo)記為K,當(dāng)前煙花個體與其它個體距離標(biāo)記為R(Xi),煙花選取概率標(biāo)記為P(Xi)。

3.2 建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化模型

設(shè)定網(wǎng)絡(luò)的無權(quán)向圖為G=(V,E),其中V、E均為網(wǎng)絡(luò)節(jié)點,網(wǎng)絡(luò)邊節(jié)點數(shù)量為W,將無權(quán)向圖鄰接矩陣設(shè)定成A(G)=(aij)N×N形式,拉普拉斯矩陣設(shè)定成L(G)形式,代數(shù)連通程度用μ表示?；谏鲜龈黜梾?shù),對網(wǎng)絡(luò)的冗余路徑進行計算,結(jié)果如下式所示

(10)

設(shè)定無權(quán)向圖的矩陣特征根為λi,通過計算獲取無權(quán)向圖G=(V,E)的路徑自然連通程度,結(jié)果如下式所示

(11)

分析上述計算結(jié)果可知,網(wǎng)絡(luò)路徑的自然連通程度可以直觀描述網(wǎng)絡(luò)路徑的冗余特性,連通程度越小,網(wǎng)絡(luò)抗毀性能越差,所以網(wǎng)絡(luò)自然連通程度計算是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化過程中重要的一環(huán)。由于網(wǎng)絡(luò)的運行受運行成本限制,所以要依據(jù)上述分析結(jié)構(gòu)建立網(wǎng)絡(luò)尋優(yōu)函數(shù)[14]并制定相關(guān)約束條件,過程如下式所示

(12)

(13)

3.3 模型求解

使用FW-PSO算法對模型進行求解,過程如下:

1)利用粒子群算法[15]對模型進行迭代處理,獲取粒子群最優(yōu)適應(yīng)度粒子,剔除剩余粒子。

2)利用煙花算法對獲取的粒子最佳適應(yīng)度進行爆炸、變異計算,獲取gronum-n粒子。

3)將粒子群中保留的最佳適應(yīng)度粒子與經(jīng)過煙花優(yōu)化獲取的獲取gronum-n粒子進行合并,產(chǎn)生新的粒子群,設(shè)定固定的迭代閾值。

4)對獲取的新粒子群進行迭代計算,直至達到迭代閾值上限后,實現(xiàn)拓?fù)浣Y(jié)構(gòu)優(yōu)化

4 實驗

為了驗證上述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化算法的整體有效性,需要對此算法進行測試。

4.1 實驗結(jié)果及分析

分別采用基于離散變量和FW-PSO的網(wǎng)絡(luò)拓?fù)鋬?yōu)化的算法(本文所提算法)、分布式綜合化航空電子網(wǎng)絡(luò)拓?fù)鋬?yōu)化技術(shù)(文獻[3]算法)、基于GSO算法的無線監(jiān)測網(wǎng)絡(luò)拓?fù)鋬?yōu)化方法(文獻[5]算法)進行測試;

在對無線傳感網(wǎng)絡(luò)進行網(wǎng)絡(luò)拓?fù)鋬?yōu)化時,網(wǎng)絡(luò)節(jié)點覆蓋度、移動能耗以及網(wǎng)絡(luò)連通度的高低,會直接影響網(wǎng)絡(luò)拓?fù)鋬?yōu)化性能。采用本文所提算法、文獻[3]算法以及文獻[5]算法進行無線傳感網(wǎng)絡(luò)拓?fù)鋬?yōu)化時,對上述三種指標(biāo)進行測試,從而檢測三種算法的優(yōu)化性能。

1)網(wǎng)絡(luò)節(jié)點覆蓋度測試

網(wǎng)絡(luò)在進行拓?fù)鋬?yōu)化時,節(jié)點覆蓋度的高低會給優(yōu)化效果帶來巨大的影響,節(jié)點覆蓋度越高,拓?fù)鋬?yōu)化效果越好,反之越差。采用本文所提算法、文獻[3]算法以及文獻[5]算法進行網(wǎng)絡(luò)拓?fù)鋬?yōu)化時,對三種方法的網(wǎng)絡(luò)節(jié)點覆蓋程度進行測試,測試結(jié)果如圖1所示。

圖1 不同算法的網(wǎng)絡(luò)節(jié)點覆蓋程度測試結(jié)果

分析圖1可知,隨著測試時間的增加,網(wǎng)絡(luò)節(jié)點覆蓋度較低。當(dāng)測試時間在50s時,三種算法的網(wǎng)絡(luò)節(jié)點覆蓋程度測試結(jié)果一致,但是當(dāng)測試時間到100s時,本文所提算法與文獻[3]算法測試結(jié)果一致,文獻[5]算法的測試結(jié)果與其它兩種算法測試結(jié)果之間出現(xiàn)差距。隨著測試時間的拉長,三種算法在150s時測試結(jié)果差距拉開,并隨著測試時間的增長差距逐漸變大。本文所提方法在進行拓?fù)浣Y(jié)構(gòu)優(yōu)化前,對網(wǎng)絡(luò)數(shù)據(jù)進行了離散化處理,獲取了網(wǎng)絡(luò)離散變量,所以本文所提算法在進行網(wǎng)絡(luò)拓?fù)鋬?yōu)化時的網(wǎng)絡(luò)節(jié)點覆蓋度高。

2)網(wǎng)絡(luò)移動能耗與節(jié)點覆蓋度關(guān)系測試

基于上述實驗結(jié)果,利用三種優(yōu)化算法對網(wǎng)絡(luò)拓?fù)鋬?yōu)化時,網(wǎng)絡(luò)移動能耗與網(wǎng)絡(luò)節(jié)點覆蓋度關(guān)系進行測試,測試結(jié)果如圖2所示。

圖2 不同算法的網(wǎng)絡(luò)能耗測試結(jié)果

分析圖2可知,在進行網(wǎng)絡(luò)拓?fù)鋬?yōu)化時,網(wǎng)絡(luò)移動能耗會隨著網(wǎng)絡(luò)節(jié)點覆蓋度的增加而增高。當(dāng)網(wǎng)絡(luò)的節(jié)點覆蓋程度為0.2時,本文所提算法與文獻[3]算法測試結(jié)果一致,文獻[5]算法略高于其它兩種算法,但是隨著網(wǎng)絡(luò)節(jié)點覆蓋度的增加,三種算法測試結(jié)果差距逐漸變大,文獻[3]算法的網(wǎng)絡(luò)節(jié)點能耗高于本文所提算法,文獻[5]算法測試結(jié)果不理想。

3)連通性測試

網(wǎng)絡(luò)連通性的大小會對網(wǎng)絡(luò)拓?fù)鋬?yōu)化性能帶來直觀影響,連通性越大,拓?fù)鋬?yōu)化性能越高。采用本文所提算法、文獻[3]算法以及文獻[5]算法進行拓?fù)鋬?yōu)化時,對三種算法的網(wǎng)絡(luò)連通性進行測試,測試結(jié)果如表1所示。

表1 不同算法的網(wǎng)絡(luò)連通性測試結(jié)果

分析表1可知,本文所提算法在對網(wǎng)絡(luò)連通性進行計算時,所用耗時低于其它兩種算法且測試出的連通性高于其它兩種算法。文獻[3]算法測試結(jié)果低于本文所提方法,文獻[5]算法測試出的網(wǎng)絡(luò)連通性最差,由此證明本文所提方法的優(yōu)化性能好。

5 結(jié)束語

網(wǎng)絡(luò)拓?fù)鋬?yōu)化作為保障網(wǎng)絡(luò)負(fù)載平衡,延長網(wǎng)絡(luò)壽命的關(guān)鍵,是無線傳感領(lǐng)域近年來亟待解決的問題。針對傳統(tǒng)網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法中存在的問題,提出基于離散變量和FW-PSO的網(wǎng)絡(luò)拓?fù)鋬?yōu)化的算法。該算法通過獲取的網(wǎng)絡(luò)數(shù)據(jù)離散變量完成網(wǎng)絡(luò)拓?fù)鋬?yōu)化模型的建立;再使用FW-PSO算法對模型進行求解,實現(xiàn)網(wǎng)絡(luò)的拓?fù)鋬?yōu)化。