考慮陰影衰落的無(wú)線網(wǎng)絡(luò)拓?fù)潆x散優(yōu)化算法

程 楠,朱國(guó)超

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

1 引言

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

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

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

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

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

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

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

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

(1)

式中,(u,v)表示網(wǎng)絡(luò)鏈路;f0表示參考距離;K表示信號(hào)增益,其與網(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ú)線網(wǎng)絡(luò)中節(jié)點(diǎn)之間的物理距離會(huì)對(duì)邏輯距離產(chǎn)生影響,但在無(wú)線網(wǎng)絡(luò)實(shí)際運(yùn)行過(guò)程中,由于節(jié)點(diǎn)的硬件條件和環(huán)境因素,無(wú)法準(zhǔn)確的獲取節(jié)點(diǎn)間物理距離和路徑損耗系數(shù)。因此,針對(duì)無(wú)線網(wǎng)絡(luò)中節(jié)點(diǎn)之間產(chǎn)生的路徑損耗展開(kāi)計(jì)算

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

(6)

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

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

(7)

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

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

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

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

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

(8)

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

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

RRX(l)=ls1

(9)

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

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

(10)

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

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

(11)

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

2.2 周期休眠機(jī)制

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

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

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

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

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

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

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

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

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

(12)

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

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

(13)

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

2.3 鏈路開(kāi)銷函數(shù)

(14)

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

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

(15)

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

c(rij)=ln(Ii,Ij)

(16)

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

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

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