程 楠,朱國超

(1. 新鄉(xiāng)工程學(xué)院信息工程學(xué)院,河南 新鄉(xiāng) 453000;2. 河南師范大學(xué)計算機與信息技術(shù)學(xué)院,河南 新鄉(xiāng) 453002)

1 引言

為了保證數(shù)據(jù)在網(wǎng)絡(luò)中的安全傳輸和有效應(yīng)用,需要對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)展開優(yōu)化[1,2]。無線網(wǎng)絡(luò)的底層協(xié)議是拓?fù)浣Y(jié)構(gòu),拓?fù)浣Y(jié)構(gòu)支撐著無線網(wǎng)絡(luò)的運行,優(yōu)化無線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以提高數(shù)據(jù)在網(wǎng)絡(luò)中傳輸?shù)陌踩?同時降低網(wǎng)絡(luò)能耗,因此研究無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法具有重要意義。

班玉友[3]等人通過負(fù)載方差和網(wǎng)絡(luò)延時描述網(wǎng)絡(luò)運行的負(fù)載均衡性,并將最小網(wǎng)絡(luò)負(fù)載和時延作為目標(biāo),將成本作為約束條件,建立網(wǎng)絡(luò)拓?fù)鋬?yōu)化模型,在旗魚優(yōu)化器的基礎(chǔ)上完成網(wǎng)絡(luò)拓?fù)鋬?yōu)化,該算法優(yōu)化后網(wǎng)絡(luò)中存在大量的冗余鏈路。張穎[4]等人提出了一種基于FW-PSO算法的無線傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化方法,首先,建立無線傳感網(wǎng)絡(luò)模型,利用FW-PSO算法全局搜索能力較好和收斂速度較快的優(yōu)勢,優(yōu)化拓?fù)浣Y(jié)構(gòu)的動態(tài)抗毀性和靜態(tài)抗毀性,實現(xiàn)網(wǎng)絡(luò)拓?fù)鋬?yōu)化,該算法存在網(wǎng)絡(luò)干擾高和覆蓋性差的問題。為了解決上述算法中存在的問題,提出基于離散變量的無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法。

2 一種無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法設(shè)計

2.1 無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化模型

無線網(wǎng)絡(luò)在實際運行過程中存在的節(jié)點障礙物會導(dǎo)致信號衰減問題[5,6],信號衰減過程在不可預(yù)知的情況下會發(fā)生異常,如果此時在理想模型的基礎(chǔ)上優(yōu)化無線網(wǎng)絡(luò)拓?fù)?會影響網(wǎng)絡(luò)拓?fù)涞幕拘阅?包括健壯性和連通性等。在無線通信網(wǎng)絡(luò)環(huán)境中收發(fā)設(shè)備之間可能會存在障礙物,通過衍射、吸收、散射和反射等方式障礙物會衰減無線信號在網(wǎng)絡(luò)中的能量,即陰影衰落。陰影衰落的產(chǎn)生會增加無線網(wǎng)絡(luò)的丟包率和誤碼率,導(dǎo)致無線網(wǎng)絡(luò)出現(xiàn)鏈路中斷的現(xiàn)象,因此在無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化過程中需要考慮上述問題。當(dāng)陰影衰落出現(xiàn)在無線網(wǎng)絡(luò)中時,增加了鏈路中無線信號在節(jié)點間傳輸?shù)南腫7,8]。為了解決上述問題,建立路徑障礙移除模型。

在無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化過程中,無法準(zhǔn)確的獲取損耗系數(shù),只能通過布點環(huán)境或經(jīng)驗值估計。當(dāng)障礙物存在于鏈路間時,會引起不同程度的額外能量衰減,因此每條鏈路在無線網(wǎng)絡(luò)中的損耗系數(shù)mreal值表示應(yīng)用狀態(tài)下該條鏈路的通信環(huán)境,不能用同一個路徑損耗系數(shù)表示網(wǎng)絡(luò)中所有鏈路的真實通信狀態(tài)。為了統(tǒng)一度量無線網(wǎng)絡(luò)中存在的鏈路,路徑障礙在鏈路中引起的額外衰減能量映射為節(jié)點之間在無線網(wǎng)絡(luò)中的間距。

物理距離freal描述的是節(jié)點之間在無線網(wǎng)絡(luò)環(huán)境中的直線距離;陰影衰落在網(wǎng)絡(luò)鏈路中導(dǎo)致的額外能量映射為距離的增量,將其與物理距離相加即為邏輯距離flogic。

障礙物在網(wǎng)絡(luò)鏈路中產(chǎn)生的額外衰減能量通過映射處理變?yōu)檫壿嬀嚯x后,此時可認(rèn)為已將障礙物移除路徑,設(shè)mlogic代表的是障礙物移除后對應(yīng)的損耗系數(shù),通過下式計算路徑損耗Aloss(u,v)

(1)

式中,(u,v)表示網(wǎng)絡(luò)鏈路;f0表示參考距離;K表示信號增益,其與網(wǎng)絡(luò)信道平均衰減情況和天線特性有關(guān),表達(dá)式為

(2)

式中,μ表示衰減系數(shù)。

在式(2)的基礎(chǔ)上獲得下式

(3)

Aloss(u,v)=q1freal(u,v)mrealq2flogic(u,v)mlogic

(4)

在上式的基礎(chǔ)上獲得物理與邏輯距離之間存在的關(guān)系

(5)

分析上式可知,在無線網(wǎng)絡(luò)中節(jié)點之間的物理距離會對邏輯距離產(chǎn)生影響,但在無線網(wǎng)絡(luò)實際運行過程中,由于節(jié)點的硬件條件和環(huán)境因素,無法準(zhǔn)確的獲取節(jié)點間物理距離和路徑損耗系數(shù)。因此,針對無線網(wǎng)絡(luò)中節(jié)點之間產(chǎn)生的路徑損耗展開計算

Aloss(u,v)=lAt(u)-rss

(6)

式中,rss表示接收信號強度;l表示不同射頻芯片針對不同的接收信號強度rss的表達(dá)形式;At(u)表示節(jié)點u在無線網(wǎng)絡(luò)中對應(yīng)的發(fā)射功率。

在相同鏈路中存在Aloss(u,v)=q2flogic(u,v)mlogic,以此為依據(jù)計算邏輯距離flogic(u,v)

(7)

計算鏈路的損耗系數(shù)mlogic,將其代入上式中,獲得消除路徑障礙物后無線網(wǎng)絡(luò)節(jié)點之間的邏輯距離flogic(u,v)。在不同環(huán)境中,為了使去除障礙物后的相同網(wǎng)絡(luò)鏈路具有可比性,需要選擇相同的損耗系數(shù)mlogic。

結(jié)合節(jié)點能耗模型和路徑障礙移除模型實現(xiàn)無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化,以此提高網(wǎng)絡(luò)能量利用率、增強網(wǎng)絡(luò)實用性。

數(shù)據(jù)處理和數(shù)據(jù)感知消耗的能量低于通信能耗,因此重點考慮通信能耗[9,10]。

設(shè)置路徑損耗系數(shù)b,在通信范圍r內(nèi)節(jié)點傳輸數(shù)據(jù)包產(chǎn)生的能耗為RTX(l,r)

RTX(l,r)=l(s1+s2rb)

(8)

式中,s1、s2分別表示節(jié)點接收與發(fā)送電路和放大電路消耗的能量。

設(shè)RRX(l)代表的是節(jié)點在無線網(wǎng)絡(luò)中接收數(shù)據(jù)包產(chǎn)生的能耗,其計算公式如下

RRX(l)=ls1

(9)

節(jié)點u和節(jié)點v在無線網(wǎng)絡(luò)中可通過多跳方式和單跳方式建立通信,因此在式(8)和式(9)的基礎(chǔ)上計算節(jié)點在無線網(wǎng)絡(luò)中的能耗R(l,r)

R(l,r)=RTX(l,r)+RRX(l)

(10)

當(dāng)發(fā)送范圍和轉(zhuǎn)發(fā)數(shù)據(jù)長度相同時,選擇轉(zhuǎn)發(fā)節(jié)點時需要選擇剩余能量大的節(jié)點,延長節(jié)點使用壽命,提高無線網(wǎng)絡(luò)的覆蓋性和連通性。

設(shè)置權(quán)重參數(shù)β、χ、η,結(jié)合節(jié)點剩余能量和邏輯距離通過下式計算鏈路權(quán)值Eu,v

(11)

式中,ru、rv表示節(jié)點u、v內(nèi)剩余的能量。

2.2 周期休眠機制

在無線網(wǎng)絡(luò)中選取性能良好的多個節(jié)點作為中繼節(jié)點,針對中繼節(jié)點,在無線網(wǎng)絡(luò)中設(shè)計適當(dāng)?shù)妮喰莶渴鸩呗訹11],延長網(wǎng)絡(luò)壽命:

1)分割無線網(wǎng)絡(luò),由初始簇頭節(jié)點構(gòu)成集合ΩCH,在上述集合中挑選備用中繼節(jié)點;

2)度量集合ΩCH中的簇頭節(jié)點與sink節(jié)點之間存在的距離,選取兩個距離最近的節(jié)點作為種子節(jié)點,在集合ΩCH中統(tǒng)計可以覆蓋整個無線網(wǎng)絡(luò)的節(jié)點,建立備用簇頭節(jié)點集合ΔCH[12,13];

3)在無線網(wǎng)絡(luò)中剔除被種子節(jié)點覆蓋的區(qū)域,并在集合ΔCH中挑選可以覆蓋整個無線網(wǎng)絡(luò)的備用簇頭節(jié)點,利用上述節(jié)點構(gòu)成集合ΔCH1;對上述過程展開n次迭代,當(dāng)沒有可以覆蓋整個無線網(wǎng)絡(luò)的節(jié)點時,停止迭代,獲得集合ΔCHn;

4)集合ΔCHn中存在的節(jié)點即為無線網(wǎng)絡(luò)中的中繼節(jié)點,計算上述節(jié)點的連通度,選取計算結(jié)果低于2的節(jié)點構(gòu)成集合ΔRH;

5)計算無線網(wǎng)絡(luò)中節(jié)點與ΔRH之間的距離,選取距離最小的節(jié)點作為備用中繼節(jié)點,將其劃分到集合ΔCHn中,重復(fù)上述過程,直至迭代結(jié)束。

可利用系數(shù)矩陣L和有向圖H表示集合ΔCHn,用L(i,j)表示矩陣L中存在的元素,當(dāng)元素L(i,j)的值為-1時,節(jié)點j將數(shù)據(jù)傳輸?shù)焦?jié)點i中;當(dāng)元素L(i,j)的值為0時,表明節(jié)點j、i在無線網(wǎng)絡(luò)中沒有數(shù)據(jù)中繼關(guān)系;當(dāng)元素L(i,j)的值為1時,表明節(jié)點i將數(shù)據(jù)傳輸?shù)焦?jié)點j中。

針對系數(shù)矩陣L,根據(jù)線性代數(shù)知識可知其中存在n個特征值κn,κn≥κn-1…≥κ2≥κ1≥0。當(dāng)無線網(wǎng)絡(luò)中的節(jié)點當(dāng)κn的值為1時屬于全連通狀態(tài),網(wǎng)絡(luò)在此條件下的健壯性良好;簇頭節(jié)點當(dāng)κn的值為0時,無法向sink節(jié)點傳輸或接收數(shù)據(jù)。

設(shè)E(H)表示H的權(quán)值系數(shù),其計算公式如下

(12)

式中,f(i,j)表示節(jié)點j、i之間在無線網(wǎng)絡(luò)中對應(yīng)的元素L(i,j);n表示節(jié)點在有向圖H中的數(shù)量。

結(jié)合上述分析,獲得權(quán)值系數(shù)E(H)與特征值κn之間的關(guān)系

(13)

根據(jù)E(H)在中繼節(jié)點部署過程中度量部署效果,當(dāng)E(H)<1時,中繼節(jié)點在無線網(wǎng)絡(luò)中的連通性較差,通過步驟1)～5)提高其覆蓋能力,直至E(H)>1,節(jié)點在網(wǎng)絡(luò)中的連通性得到了有效提升。

2.3 鏈路開銷函數(shù)

(14)

式中,Ji、Jj表示節(jié)點i、j在無線網(wǎng)絡(luò)中的天線增益;ath表示信號捕捉門限;υ表示路徑損耗因子,在區(qū)間[0,4]內(nèi)取值;λ表示波長;fij表示節(jié)點i、j在無線網(wǎng)絡(luò)中的距離。

當(dāng)無線網(wǎng)絡(luò)的資源有限時,可以通過分組轉(zhuǎn)發(fā)的不情愿性對網(wǎng)絡(luò)中存在的資源展開分配。節(jié)點使用資源的不情愿性隨著資源量的降低不斷增加[14],用Ti表示節(jié)點i在無線網(wǎng)絡(luò)中的可用資源,建立節(jié)點i在無線網(wǎng)絡(luò)中的不情愿性函數(shù)I(Ti,ti)

(15)

關(guān)聯(lián)節(jié)點在網(wǎng)絡(luò)鏈路中的不情愿狀態(tài)可由鏈路開銷c(rij)表示

c(rij)=ln(Ii,Ij)

(16)

根據(jù)鏈路開銷c(rij)動態(tài)調(diào)整節(jié)點在無線網(wǎng)絡(luò)中的剩余資源,實現(xiàn)網(wǎng)絡(luò)資源均衡[15],完成無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化。

3 實驗與分析

為了驗證基于離散變量的無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法的整體有效性,將文獻(xiàn)[3]算法和文獻(xiàn)[4]算法作為對比算法,通過仿真軟件MATLAB展開如下測試。在測試過程中優(yōu)化的無線網(wǎng)絡(luò)相關(guān)參數(shù)如表1所示。

表1 無線網(wǎng)絡(luò)相關(guān)參數(shù)

節(jié)點在無線網(wǎng)絡(luò)中的初始拓?fù)鋱D如圖1所示。

圖1 網(wǎng)絡(luò)初始拓?fù)鋱D

分析圖1可知,無線網(wǎng)絡(luò)的初始拓?fù)鋱D中存在大量的無意義冗余鏈路,節(jié)點在這些冗余鏈路中通過最大功率發(fā)送數(shù)據(jù),增強了節(jié)點之間在無線網(wǎng)絡(luò)中的通信干擾,進(jìn)而增大了節(jié)點能耗。

現(xiàn)采用基于離散變量的無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法、文獻(xiàn)[3]算法和文獻(xiàn)[4]算法對上述無線網(wǎng)絡(luò)拓?fù)湔归_優(yōu)化,優(yōu)化結(jié)果如圖2所示。

圖2 不同算法優(yōu)化后的網(wǎng)絡(luò)拓?fù)鋱D

分析圖2可知,采用所提算法優(yōu)化后,無線網(wǎng)絡(luò)中不存在冗余鏈路,采用文獻(xiàn)[3]算法和文獻(xiàn)[4]算法優(yōu)化后,網(wǎng)絡(luò)中還存在大量的冗余鏈路,因為所提算法在優(yōu)化無線網(wǎng)絡(luò)拓?fù)鋾r建立了路徑障礙移除模型,移除了節(jié)點之間存在的障礙物,降低了無線網(wǎng)絡(luò)對節(jié)點發(fā)射功率的要求,進(jìn)而避免了節(jié)點在網(wǎng)絡(luò)之間產(chǎn)生的互相干擾,減少了冗余鏈路。

將網(wǎng)絡(luò)最大干擾、節(jié)點平均通信半徑和網(wǎng)絡(luò)平均干擾作為指標(biāo),測試所提算法、文獻(xiàn)[3]算法和文獻(xiàn)[4]算法優(yōu)化后無線網(wǎng)絡(luò)的整體性能,測試結(jié)果如表2所示。

表2 網(wǎng)絡(luò)性能測試結(jié)果

分析表2中的數(shù)據(jù)可知,所提算法的網(wǎng)絡(luò)最大干擾和平均干擾最低,表明數(shù)據(jù)在網(wǎng)絡(luò)中具有較高的傳輸穩(wěn)定性,節(jié)點平均通信半徑最高,表明優(yōu)化后網(wǎng)絡(luò)具有良好的覆蓋性。

4 結(jié)束語

拓?fù)淇刂剖菬o線網(wǎng)絡(luò)中路由算法的基礎(chǔ),可以通過優(yōu)化網(wǎng)絡(luò)拓?fù)涮岣呔W(wǎng)絡(luò)連通性、降低節(jié)點能耗、降低通信干擾、延長網(wǎng)絡(luò)生存時間。目前無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法存在冗余鏈路數(shù)量多、網(wǎng)絡(luò)干擾大和網(wǎng)絡(luò)覆蓋性差等問題,提出基于離散變量的無線網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法,通過節(jié)點能耗模型和路徑障礙移除模型對無線網(wǎng)絡(luò)拓?fù)湔归_初始優(yōu)化,其次通過設(shè)計周期休眠機制和鏈路開銷函數(shù)進(jìn)一步優(yōu)化無線網(wǎng)絡(luò)拓?fù)?解決了目前方法中存在的問題,為無線網(wǎng)絡(luò)的運行和應(yīng)用奠定了基礎(chǔ)。