考慮陰影衰落的無線網絡拓撲離散優化算法

程 楠,朱國超

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

1 引言

為了保證數據在網絡中的安全傳輸和有效應用,需要對網絡拓撲結構展開優化[1,2]。無線網絡的底層協議是拓撲結構,拓撲結構支撐著無線網絡的運行,優化無線網絡拓撲結構可以提高數據在網絡中傳輸的安全性,同時降低網絡能耗,因此研究無線網絡拓撲優化算法具有重要意義。

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

2 一種無線網絡拓撲優化算法設計

2.1 無線網絡拓撲優化模型

無線網絡在實際運行過程中存在的節點障礙物會導致信號衰減問題[5,6],信號衰減過程在不可預知的情況下會發生異常,如果此時在理想模型的基礎上優化無線網絡拓撲,會影響網絡拓撲的基本性能,包括健壯性和連通性等。在無線通信網絡環境中收發設備之間可能會存在障礙物,通過衍射、吸收、散射和反射等方式障礙物會衰減無線信號在網絡中的能量,即陰影衰落。陰影衰落的產生會增加無線網絡的丟包率和誤碼率,導致無線網絡出現鏈路中斷的現象,因此在無線網絡拓撲優化過程中需要考慮上述問題。當陰影衰落出現在無線網絡中時,增加了鏈路中無線信號在節點間傳輸的消耗[7,8]。為了解決上述問題,建立路徑障礙移除模型。

在無線網絡拓撲優化過程中,無法準確的獲取損耗系數,只能通過布點環境或經驗值估計。當障礙物存在于鏈路間時,會引起不同程度的額外能量衰減,因此每條鏈路在無線網絡中的損耗系數mreal值表示應用狀態下該條鏈路的通信環境,不能用同一個路徑損耗系數表示網絡中所有鏈路的真實通信狀態。為了統一度量無線網絡中存在的鏈路,路徑障礙在鏈路中引起的額外衰減能量映射為節點之間在無線網絡中的間距。

物理距離freal描述的是節點之間在無線網絡環境中的直線距離;陰影衰落在網絡鏈路中導致的額外能量映射為距離的增量,將其與物理距離相加即為邏輯距離flogic。

障礙物在網絡鏈路中產生的額外衰減能量通過映射處理變為邏輯距離后,此時可認為已將障礙物移除路徑,設mlogic代表的是障礙物移除后對應的損耗系數,通過下式計算路徑損耗Aloss(u,v)

(1)

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

(2)

式中,μ表示衰減系數。

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

(3)

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

(4)

在上式的基礎上獲得物理與邏輯距離之間存在的關系

(5)

分析上式可知,在無線網絡中節點之間的物理距離會對邏輯距離產生影響,但在無線網絡實際運行過程中,由于節點的硬件條件和環境因素,無法準確的獲取節點間物理距離和路徑損耗系數。因此,針對無線網絡中節點之間產生的路徑損耗展開計算

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

(6)

式中,rss表示接收信號強度;l表示不同射頻芯片針對不同的接收信號強度rss的表達形式;At(u)表示節點u在無線網絡中對應的發射功率。

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

(7)

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

結合節點能耗模型和路徑障礙移除模型實現無線網絡拓撲優化,以此提高網絡能量利用率、增強網絡實用性。

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

設置路徑損耗系數b,在通信范圍r內節點傳輸數據包產生的能耗為RTX(l,r)

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

(8)

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

設RRX(l)代表的是節點在無線網絡中接收數據包產生的能耗,其計算公式如下

RRX(l)=ls1

(9)

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

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

(10)

當發送范圍和轉發數據長度相同時,選擇轉發節點時需要選擇剩余能量大的節點,延長節點使用壽命,提高無線網絡的覆蓋性和連通性。

設置權重參數β、χ、η,結合節點剩余能量和邏輯距離通過下式計算鏈路權值Eu,v

(11)

式中,ru、rv表示節點u、v內剩余的能量。

2.2 周期休眠機制

在無線網絡中選取性能良好的多個節點作為中繼節點,針對中繼節點,在無線網絡中設計適當的輪休部署策略[11],延長網絡壽命:

1)分割無線網絡,由初始簇頭節點構成集合ΩCH,在上述集合中挑選備用中繼節點;

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

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

4)集合ΔCHn中存在的節點即為無線網絡中的中繼節點,計算上述節點的連通度,選取計算結果低于2的節點構成集合ΔRH;

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

可利用系數矩陣L和有向圖H表示集合ΔCHn,用L(i,j)表示矩陣L中存在的元素,當元素L(i,j)的值為-1時,節點j將數據傳輸到節點i中;當元素L(i,j)的值為0時,表明節點j、i在無線網絡中沒有數據中繼關系;當元素L(i,j)的值為1時,表明節點i將數據傳輸到節點j中。

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

設E(H)表示H的權值系數,其計算公式如下

(12)

式中,f(i,j)表示節點j、i之間在無線網絡中對應的元素L(i,j);n表示節點在有向圖H中的數量。

結合上述分析,獲得權值系數E(H)與特征值κn之間的關系

(13)

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

2.3 鏈路開銷函數

(14)

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

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

(15)

關聯節點在網絡鏈路中的不情愿狀態可由鏈路開銷c(rij)表示

c(rij)=ln(Ii,Ij)

(16)

根據鏈路開銷c(rij)動態調整節點在無線網絡中的剩余資源,實現網絡資源均衡[15],完成無線網絡拓撲優化。

3 實驗與分析

為了驗證基于離散變量的無線網絡拓撲優化算法的整體有效性,將文獻[3]算法和文獻[4]算法作為對比算法,通過仿真軟件MATLAB展開如下測試。在測試過程中優化的無線網絡相關參數如表1所示。

表1 無線網絡相關參數

節點在無線網絡中的初始拓撲圖如圖1所示。

圖1 網絡初始拓撲圖

分析圖1可知,無線網絡的初始拓撲圖中存在大量的無意義冗余鏈路,節點在這些冗余鏈路中通過最大功率發送數據,增強了節點之間在無線網絡中的通信干擾,進而增大了節點能耗。

現采用基于離散變量的無線網絡拓撲優化算法、文獻[3]算法和文獻[4]算法對上述無線網絡拓撲展開優化,優化結果如圖2所示。

圖2 不同算法優化后的網絡拓撲圖

分析圖2可知,采用所提算法優化后,無線網絡中不存在冗余鏈路,采用文獻[3]算法和文獻[4]算法優化后,網絡中還存在大量的冗余鏈路,因為所提算法在優化無線網絡拓撲時建立了路徑障礙移除模型,移除了節點之間存在的障礙物,降低了無線網絡對節點發射功率的要求,進而避免了節點在網絡之間產生的互相干擾,減少了冗余鏈路。

將網絡最大干擾、節點平均通信半徑和網絡平均干擾作為指標,測試所提算法、文獻[3]算法和文獻[4]算法優化后無線網絡的整體性能,測試結果如表2所示。

表2 網絡性能測試結果

分析表2中的數據可知,所提算法的網絡最大干擾和平均干擾最低,表明數據在網絡中具有較高的傳輸穩定性,節點平均通信半徑最高,表明優化后網絡具有良好的覆蓋性。

4 結束語

拓撲控制是無線網絡中路由算法的基礎,可以通過優化網絡拓撲提高網絡連通性、降低節點能耗、降低通信干擾、延長網絡生存時間。目前無線網絡拓撲優化算法存在冗余鏈路數量多、網絡干擾大和網絡覆蓋性差等問題,提出基于離散變量的無線網絡拓撲優化算法,通過節點能耗模型和路徑障礙移除模型對無線網絡拓撲展開初始優化,其次通過設計周期休眠機制和鏈路開銷函數進一步優化無線網絡拓撲,解決了目前方法中存在的問題,為無線網絡的運行和應用奠定了基礎。