邵 杰,劉 晶

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

1 引言

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

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

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

2 獲取離散變量

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

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

由于網(wǎng)絡(luò)數(shù)據(jù)之間具有關(guān)聯(lián)性,所以對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)時(shí),可將衡量數(shù)據(jù)變量作為數(shù)據(jù)相關(guān)系數(shù)。設(shè)定網(wǎng)絡(luò)中兩個(gè)數(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?；谏鲜鲇?jì)算結(jié)果獲取網(wǎng)絡(luò)數(shù)據(jù)離散化標(biāo)準(zhǔn)[7],結(jié)果如下式所示

(2)

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

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

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

2.2 停止準(zhǔn)則

在對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行離散化時(shí),不僅需要獲取相關(guān)離散化標(biāo)準(zhǔn),還需要提出一個(gè)停止準(zhǔn)則。使用β-近似精度控制法對(duì)數(shù)據(jù)離散信息進(jìn)行控制,以防止信息出現(xiàn)丟失現(xiàn)象,并允許數(shù)據(jù)中存有錯(cuò)誤,達(dá)到對(duì)離散化數(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ù)近似精度控制值獲取過(guò)程如下式所示

(3)

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

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

(4)

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

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

2.3 離散流程

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

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

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

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

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

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

最后通過(guò)上述流程實(shí)現(xiàn)無(wú)線傳感網(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)化模型,通過(guò)FW-PSO算法對(duì)模型進(jìn)行求解實(shí)現(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。粒子的搜索速度與位置的獲取過(guò)程如下式所示:

(5)

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

使用線性遞減策略[11]計(jì)算粒子群慣性權(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,二者的獲取過(guò)程如下式所示

(7)

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

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

(8)

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

(9)

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

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

設(shè)定網(wǎng)絡(luò)的無(wú)權(quán)向圖為G=(V,E),其中V、E均為網(wǎng)絡(luò)節(jié)點(diǎn),網(wǎng)絡(luò)邊節(jié)點(diǎn)數(shù)量為W,將無(wú)權(quán)向圖鄰接矩陣設(shè)定成A(G)=(aij)N×N形式,拉普拉斯矩陣設(shè)定成L(G)形式,代數(shù)連通程度用μ表示。基于上述各項(xiàng)參數(shù),對(duì)網(wǎng)絡(luò)的冗余路徑進(jìn)行計(jì)算,結(jié)果如下式所示

(10)

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

(11)

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

(12)

(13)

3.3 模型求解

使用FW-PSO算法對(duì)模型進(jìn)行求解,過(guò)程如下:

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

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

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

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

4 實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

3)連通性測(cè)試

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

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

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

5 結(jié)束語(yǔ)

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