基于病毒-抗體免疫博弈的WSN鏈路穩定算法

徐 鋒,王 佶

(浙江大學 信息技術中心,杭州 310058)

0 概述

為提高無線傳感器網絡(Wireless Sensor Networks,WSN)在數據激增、吞吐受限等情景下的數據傳輸能力[1],研究人員提出了較多解決方案,主要從鏈路、能量、路由分區等方面,通過改進數據傳輸及節點分區方式,以提高WSN的數據傳輸質量[2-3]。路由分區解決方案主要分平面型和區域型兩類[4],平面型方案需要大規模存儲路由鏈路信息數據,難以適應超寬帶網絡環境下WSN的網絡傳輸需求,區域型方案主要通過分層、分簇、區域分割等方式形成層次性傳輸結構,其具有較強的鏈路穩定性能。

在當前的WSN數據傳輸方案中,LEACH算法作為一種基本解決方案[5],主要采用簇狀網絡部署模式,結合更新機制穩定傳輸鏈路,最終改善網絡能耗。但是,LEACH算法未能綜合考慮網絡運行參數,如節點分布、簇頭能量、傳輸鏈路抖動等數據傳輸的影響因素,其性能難以滿足當前WSN網絡的超寬帶傳輸需求。文獻[6]提出了一種基于群擴散方案的WSN傳輸協議,該協議在LEACH算法的基礎上引入節點能量裁決機制,采用周期統計機制獲取能量最佳節點,將該節點作為中繼傳輸節點,借助中繼節點均值能量并群擴散方法來獲取可使用的中繼節點集合,從而提高鏈路在高抖動環境下的適應能力,降低網絡抖動發生概率并達到鏈路穩定的效果,實驗結果表明,該算法的傳輸性能優于LEACH算法。然而,文獻[6]算法也存在網絡吞吐受限的不足,在一定程度上限制了其適用范圍。文獻[7]基于數據分組報文集約化控制方案,提出了一種能夠穩定傳輸鏈路的傳輸協議,該協議采用能量控制方式穩定中繼傳輸鏈路節點,在區域分割完畢后將距離中繼傳輸鏈路節點最近的節點作為備用節點,當主節點失效時自動啟用備用節點,從而提高鏈路傳輸質量,并在一定程度上降低因網絡抖動而導致的傳輸受阻、吞吐不暢等問題。然而,文獻[7]協議僅選取能量最優的節點作為中繼傳輸鏈路節點,未考慮網絡出現大面積波動時導致備用節點失效的問題,難以適應復雜網絡狀況,特別是網絡處于超寬帶傳輸時,易因主、備節點均處于失效狀態而出現鏈路抖動,降低了其實際部署價值。

針對WSN部署運行過程中存在的“熱點”現象,文獻[8]提出了一種基于輪詢替換機制的傳輸協議,該協議首先在熱度較高的區域插入標簽,選取服務能力較高的節點作為中繼節點,若區域熱度較高,將自動啟用周期輪詢機制逐次替換區域中承擔業務交換的中繼節點,若鏈路出現抖動,也將自動進行切換。此外,該協議引入群分類機制訓練能量較高的后備節點,能夠顯著降低WSN中因“熱點”失效而導致的鏈路癱瘓概率,改善數據傳輸質量,且具有實現過程簡單等優勢。但是,文獻[8]協議對超寬帶傳輸場景考慮不足,單純采用節點更換方式,難以應對鏈路抖動場景,在實際部署中容易因鏈路抖動而出現較為嚴重的擁塞現象,難以大范圍推廣。

綜上,當前WSN數據傳輸解決方案難以將鏈路與節點納入統一的優化機制中進行綜合考慮,尤其無法通過訓練方式實現節點的傳輸優化及區域分割,導致網絡出現擁塞狀況時極易引發節點癱瘓與鏈路抖動。為解決上述問題,本文提出一種基于病毒-抗體免疫博弈機制的超寬帶WSN鏈路穩定算法。該算法主要由基于覆蓋劃分方法的網絡初始化、基于病毒-抗體免疫博弈機制的區域最優分割、基于多參數判定機制的中繼鏈路篩選方法3個部分構成。通過基于覆蓋劃分方法的網絡初始化,可提高網絡區域分割的效率,優化網絡初始化過程中的節點覆蓋性能。通過基于病毒-抗體免疫博弈機制的區域最優分割,以篩選出性能優越的區域節點與備用區域節點,使得算法網絡區域初始化過程具有顯著的分區優勢。利用基于多參數判定機制的中繼鏈路篩選方法,以改善區域節點間存在的鏈路抖動現象,提高網絡的超寬帶傳輸能力與鏈路運行質量。

1 網絡模型

為便于研究,本文假定WSN節點的分布區域為矩形,大小為A×B。節點由sink節點、普通節點、區域節點3種構成:sink節點作為全局控制節點,具有最高的網絡控制權及管理權,能夠對網絡中普通節點和區域節點進行統一管理及調配;普通節點主要承擔數據采集及匯聚上傳功能;區域節點主要用于匯聚區域數據并通過其余區域節點將數據上傳至sink節點。此外,本文作如下假設:

1)節點不具有流動性,即節點在因失效而被更換前,其地理位置將不發生變化。

2)區域節點個數不具有稀疏性,即區域節點能夠覆蓋矩形區域,無死角現象。

3)傳感器標識ID具有唯一性,且節點能夠根據當前能量、數據采集、帶寬、鏈路抖動等情況自主調節傳輸參數,依據傳輸距離優化傳輸鏈路。

4)區域內普通節點具有相似性,與區域節點處于高度融合狀態;不同區域間的普通節點具有一定的不兼容性,且不同的區域節點無法跨區域管理普通節點。

1.1 節點能量消耗模型

圖1所示為WSN數據傳輸及能量消耗模型結構,當傳輸帶寬為B、傳輸距離為l時,節點能耗EEtran(B,l)滿足:

EEtran(B,l)=BEEnode+BlxEEline

(1)

下一跳節點在接收數據時,其能耗EErecv(B,l)為:

EErecv(B,l)=BEEnode

(2)

其中,EEnode表示節點內部電路能耗功率,EEline表示天線對當前信號的放大功率,x表示傳輸模型指數[8],一般而言,當節點間的傳輸模型指數大于2時,兩者間將不再建立直連鏈路。

圖1 數據傳輸模型

根據上述假設,區域內普通節點具有相似性,與區域節點處于高度融合狀態[9]。因此,區域節點能夠將區域內k個普通節點的上傳帶寬B1,B2,…,Bk融合為區域帶寬BBlocal并進行數據上傳,區域節點因此所產生的能耗EElocal(BBlocal,k)滿足:

EElocal(BBlocal,k)=BBlocalEElocal

(3)

其中,EElocal表示區域節點內部的電路能耗功率。

設WSN中區域數量為N,區域覆蓋半徑為d,任取一個區域并統計普通節點個數,可知區域內包含k個普通節點。由于區域內節點具有高度融合特性,因此普通節點的上傳帶寬為固定值BBlevel。區域節點需要匯聚數據并傳輸至sink節點,因此,區域內普通節點整體能耗EEall(BBlevel,d,k)滿足:

EEall(BBlevel,d,k)=kBBlevelEEnode+kBBleveldxEEline

(4)

考慮到區域節點與該區域內普通節點的拓撲距離一般不超過1跳,因此,設傳輸模型指數x=1。此外,區域節點間同樣需要進行數據中繼,k個普通節點按均值BBlevel進行數據傳輸,區域節點將該數據匯聚到下一跳區域節點時能耗EEall(BBlevel,k)滿足:

EEall(BBlevel,k)=kBBlevelEEnode

(5)

可以看出,能量消耗模型主要采用區域傳輸模式,以避免出現跨多個區域進行數據傳輸的情況。由式(3)、式(4)可知,節點進行數據傳輸時所消耗的能量與區域覆蓋半徑密切相關,通過區域劃分的方式能夠提高區域節點對普通節點的控制能力,避免因跳數過多而導致難以完全覆蓋以及數據頻繁重傳的問題,最終改善網絡傳輸質量。

1.2 鏈路覆蓋模型

為保障節點間的鏈路均處于暢通狀態,即普通節點-區域節點、區域節點-區域節點間鏈路暢通,區域節點應覆蓋全部的普通節點。設區域節點LS的坐標為(Xa,Xb),任意普通節點OS的坐標為(Ya,Yb)。節點間的鏈路覆蓋判決公式如下:

(6)

對網絡中的全部區域節點進行遍歷,按式(6)獲取P(LS,OS),當鏈路覆蓋全部節點時,滿足:

(7)

其中,N為網絡節點總個數。顯然,當且僅當區域節點與各自所轄范圍內普通節點均能建立鏈路時,網絡中節點才均被鏈路覆蓋。

本文算法將整個網絡分割為非均勻分布的若干個區域,在滿足鏈路穩定傳輸的情況下,網絡能量開支最低,且數據傳輸帶寬得到均衡。本文算法目標如下:

目標1區域內能量消耗盡量最低。聯立式(4)、式(5)可知:

Target1=min(2kBBlevelEEnode+kBBleveldxEEline)

(8)

目標2鏈路覆蓋范圍最大化。由式(7)可知:

(9)

目標3區域分割數量m最少,其中,網絡節點總數為N。

Target3=min(m/N)

(10)

聯立Target1～Target3,本文目標可歸結為如下模型:

(11)

其中,μi表示權重系數,取值為0～1,*表示目標選擇。此外,權重系數滿足:

(12)

鏈路覆蓋模型主要采用等覆蓋思想對網絡節點進行均衡覆蓋,并綜合考慮能量消耗因素,通過式(6)、式(7)進行覆蓋分割,能夠提高鏈路覆蓋能力,降低節點處于離線狀態的概率。

2 WSN鏈路穩定算法設計

由于最終的網絡數據均需要傳輸至sink節點[10],因此普通節點到sink節點間的傳輸鏈路具有多跳特性[11],若網絡中存在多條傳輸鏈路時則會出現“熱點”現象:某些區域節點因處于多條傳輸鏈路交匯處,其能量消耗將遠超其余的區域節點[12]。此外,區域內的普通節點由于距離區域節點有遠有近,由式(1)可知,它們的能耗也將有所不同。本文算法通過以下方式來解決網絡中的“熱點”問題,以穩定傳輸鏈路,改善節點能耗情況:

1)利用節點與鏈路之間存在的拮抗特性來構建病毒-抗體博弈機制,將區域內性能較優的節點視為病毒體,按照多維網絡編碼算法來建立病毒種群,并對其進行感染,將感染形成的抗體通過變異方式對鏈路抖動進行適應,以優化鏈路質量及區域傳輸性能,從而降低數據傳輸中存在的鏈路抖動現象。

2)基于能量-跳數均衡方法,設計多參數判定機制,按能量大小進行中繼節點篩選,將全鏈路節點耗能總和作為判決指標,在跳數可達范圍內實現能量和跳數的綜合最優,確保每一個區域節點與sink節點間的鏈路處于穩定狀態,從而改善鏈路傳輸質量。

如圖2所示,本文算法在進行網絡初始化時包含2個部分:1)區域節點選取階段T1,sink節點選取最佳分區數量并通過路由表方式初始化鏈路數據;2)鏈路穩定傳輸階段T2。為降低網絡初始化過程中節點因發送各種數據分組而導致的能量消耗,僅當區域節點剩余能量低于閾值時進行區域節點主備切換。

圖2 網絡初始化示意圖

考慮到WSN中節點處于密集狀態時網絡初始化過程較慢,因此,本文算法根據隨機分布原則,將矩形區域按照覆蓋點進行均勻分割,并將各覆蓋區域中性能較好的節點建立為區域節點聚類集Ωlocal。sink節點通過病毒-抗體免疫博弈機制從Ωlocal中擇優選取性能具有優勢的區域節點,且將Ωlocal中最靠近被選區域節點的節點設置為備用節點,當區域節點發生故障時直接進行主備切換。圖3所示為本文算法詳細流程。

圖3 WSN鏈路穩定算法流程

2.1 基于覆蓋劃分方法的網絡初始化

在網絡初始化過程中,sink節點通過監聽網絡數據分組對覆蓋區域進行均勻分割。首先,sink發送Hello_c數據分組,節點收到該數據分組后,將自身ID與位置通過Re_hello數據分組發送到sink節點,其中,Re_hello數據分組包含節點剩余能量與位置信息;sink節點收到Re_hello數據分組后,保存全部節點信息并默認節點均為普通節點,當且僅當區域分割完畢后,做進一步區分;隨后,sink節點根據網絡中全部區域節點中覆蓋半徑最小節點的覆蓋半徑r,將區域分割為Llocal(Nnum)個覆蓋,如圖4所示。

圖4 覆蓋劃分示意圖

Llocal(Nnum)計算如下:

(13)

2.2 基于病毒-抗體免疫博弈機制的區域最優分割

在區域分割階段,sink節點需要建立鏈路最穩定且區域分割數量最少的區域最優分割方案,并為節點之間的鏈路建立路由表。首先,sink節點根據距離-剩余能量建立閾值Δ:

(14)

其中,d(max,sink)表示節點與sink節點間的最大距離,d(min,sink)表示節點與sink節點間的最小距離,d表示節點與sink節點間的距離,E表示節點當前剩余能量,Emax表示網絡中節點的最大能量,ω和σ表示裁決系數,R為節點的最大覆蓋距離。

根據式(14)逐個對節點計算閾值,并按如下公式求取判決量ν:

(15)

其中,N表示網絡中的節點個數。

當且僅當節點按式(14)求取的閾值大于判決量ν時,將自行加入區域節點聚類集Ωlocal,作為待選的區域節點。

2.2.1 區域節點選擇

本文算法采用病毒-抗體免疫博弈機制,結合免疫算法進行區域節點及備用區域節點的選擇,算法步驟具體如下:

1)收集網絡中節點的詳細信息,主要包括節點ID、節點坐標及節點剩余能量。

2)按如下方式確定區域節點與備用區域節點:

(1)設置免疫算法的基本參數。

(2)將區域節點聚類集Ωlocal視為種群集合并進行劃分。

(3)確定基本目標參數,輸出結果。

2.2.2 病毒種群初始化

按照式(16)構建區域節點聚類集Ωlocal,區域節點從該聚類集中選出。

Ωlocal={X1,X2,…,Xgroup(NUM)}

(16)

其中,group(NUM)表示病毒種群的總數量。結合式(16)和式(13),將區域節點納入覆蓋劃分中:

Ωlocal∈A×B={D1,D2,…,Dgroup(NUM)}

(17)

相關參數同式(13)、式(16),Di表示第i個節點坐落在由式(13)確立的覆蓋范圍之內,即相應的節點坐標可被區域完全覆蓋。

sink節點按照多維網絡編碼算法[13],將式(17)所示的待定區域節點的ID、初始能量、距離3個參數進行網絡編碼,形成樣本空間為group(NUM)的病毒種群Ggroup:

Ggroup={V1,V2,…,Vgroup(NUM)}

(18)

病毒種群Ggroup中每一個病毒均為待選區域節點,需要通過感染機制篩選出感染能力最強的一組區域節點及備用節點,感染過程中需要充分考慮傳染力及抗體博弈強度,以便能夠篩選出變異效果最佳的病毒。

2.2.3 感染效果評估

由于WSN節點的能量基本上被數據傳輸所消耗[14],因此針對式(18)中的病毒,采用式(11)進行目標評估,并根據評估結果按降序方式對式(18)進行傳染力排序,如下:

Ggroup={M1,M2,…,Mgroup(NUM)}

(19)

2.2.4 抗體博弈

本文基于蒙特卡洛方法[15],針對每個病毒因子感染能力的高低進行排序,某個病毒因子傳染能力越高,則對應的抗體博弈強度也越大。對式(19)所示的病毒群體進行抗體復制操作,選取當前感染力最強的0.5Ggroup(NUM)病毒進行變異。初始變異率等于鏈路抖動率,針對感染力最強的0.5Ggroup(NUM)病毒進行變異處理,每個病毒均產生Ggroup(NUM)個抗體并形成抗體種群:

Ggroup(KT)={Y1,Y2,…,Ygroup(NUM)}

(20)

其中,KT∈(X,Ωlocal)。

在網絡進行每一輪區域節點更新過程中,將抗體種群與病毒進行博弈,當且僅當病毒無法進行變異時,抗體種群才得到更新。其中,博弈方式如下:

(21)

2.2.5 博弈結束判定

本文病毒-抗體免疫博弈機制的結束條件定義為變異之后抗體種群與病毒種群間的差異值Γ無變化,Γ計算如下:

(22)

即網絡在進行區域初始化的過程中,區域節點(對應病毒種群)與備用區域節點(對應抗體種群)之間可以互相取代時,博弈過程結束。此時,區域節點與備用區域節點的覆蓋范圍相同,且具有相同的鏈路覆蓋能力(路由表相同),普通節點自行選擇距離最近的區域節點并加入到該區域中。

2.3 基于多參數判定機制的中繼鏈路篩選方法

通過病毒-抗體免疫博弈機制,可以從WSN中篩選出性能最佳的區域節點集合。然后,將普通節點納入到各自所管轄的區域中。但是,由于區域節點往往無法通過一跳的方式與sink實現鏈路直連,因此需要通過多跳方式保證每一個區域節點與sink節點間的鏈路處于穩定狀態,且跳數盡可能少,據此構建中繼鏈路篩選方法如下:

(23)

其中,E(j)表示下一跳節點的剩余能量,Emax表示可達的下一跳節點中能量最高的節點所剩余能量,i_T表示區域節點i與sink節點間的跳數,max_T表示可達的下一跳區域節點中與sink節點的最大跳數,k1和k2表示權重系數,滿足:

k1+k2=1

(24)

2.4 數據傳輸

通過上述過程,普通節點采集的數據即可通過區域節點發送到sink節點。然而,由于WSN均采用無線方式進行數據傳輸[16-17],為防止區域節點間存在頻率干涉現象,本文按QPSK預發射方式[18-19]對區域節點逐個采用不同的發射頻率,且信號處于正交狀態。處于中繼狀態的區域節點收到上一跳區域節點后,將自動采用本區域內的發射頻率并將數據發送到下一跳區域節點或sink節點,直到數據能夠完整地傳輸至sink節點為止。

3 實驗結果與分析

3.1 實驗環境與指標參數

為便于評估本文算法的性能,選取NS2仿真環境,計算機操作系統為Win10,CPU主頻為5.5 GHz,16 GB內存。WSN節點分布區域為矩形,大小為1 000 m×1 000 m,節點密度不低于1個/m2,采用隨機撒點分布模型。實驗中選擇的性能指標為:1)中繼鏈路首次癱瘓發生的輪數,主要用于評估區域節點的運行質量;2)網絡穩定時間,即從網絡開始采集數據直到中繼鏈路癱瘓的時間;3)擁塞發生次數,用以評估鏈路擁塞情況。此外,為降低誤差,每組仿真重復10次,取均值作為最終結果。在式(11)中,μ1取0.4,μ2取0.3,μ3取0.3;在式(23)中,權重系數k1和k2作為仿真評估參數,將在下文實驗中進行對比。將文獻[20]中的LEACH算法和文獻[21]中的LMS-A算法作為對照算法。

3.2 中繼鏈路首次癱瘓發生輪數

為測試WSN中中繼鏈路首次出現故障的輪數,將3種算法的區域節點最大覆蓋半徑R均設定為50 m。其中,本文算法權重系數k1和k2均設為0.5。由圖5可以看出,本文算法發生中繼鏈路首次癱瘓的輪數要遠高于LEACH算法和LMS-A算法,說明本文算法采用的病毒-抗體免疫博弈機制及多參數判定機制能夠獲取較高質量的網絡區域分割效果,且能夠顯著提高中繼鏈路的傳輸質量,降低區域節點發生癱瘓的概率。LEACH算法由于未能綜合考慮能量、鏈路等因素,因此傳輸過程中發生中繼鏈路抖動的概率較高,LMS-A算法雖然從鏈路角度對區域節點傳輸質量進行了監控,但該算法未消除區域節點數據傳輸時的頻率干涉現象,容易導致較為嚴重的鏈路抖動,因此,其發生中繼鏈路抖動并癱瘓的概率高于本文算法。

圖5 3種算法中繼鏈路首次癱瘓發生輪數對比

3.3 網絡穩定時間

參數設置同3.2節,由圖6可以看出,本文算法網絡穩定時間始終較高,說明病毒-抗體免疫博弈機制及多參數判定機制能夠較好地穩定數據傳輸鏈路,減少鏈路癱瘓和網絡癱瘓現象。LEACH算法對鏈路因素考慮不足,且未對網絡區域初始過程進行優化,因此,其網絡運行穩定程度低于本文算法。LMS-A算法雖然從傳輸鏈路角度對區域節點進行了優化,但是未能消除頻率干涉現象,容易導致區域節點間吞吐困難等問題,因此,其網絡穩定性也低于本文算法。

圖6 3種算法網絡穩定時間對比

3.4 擁塞發生次數

參數設置同3.2節,由圖7可以看出,本文算法采用的病毒-抗體免疫博弈機制及多參數判定機制能夠大幅降低擁塞發生次數,與LEACH算法和LMS-A算法相比優勢明顯,主要原因在于病毒-抗體免疫博弈機制能夠實現區域節點的最優選取,且通過主備方式避免因區域節點失效而導致的擁塞現象,此外,多參數判定機制能起到穩定鏈路的作用,因此,本文算法擁塞發生概率較低。LEACH算法和LMS-A算法的中繼鏈路癱瘓概率較高,這是由于LEACH算法未對鏈路抖動情況加以考慮,出現區域傳輸抖動概率較高,而LMS-A算法未能消除區域間的干涉現象,容易因區域節點失效而發生擁塞現象,因此,這2種算法的擁塞發生次數顯著高于本文算法。

圖7 3種算法擁塞發生次數對比

4 結束語

本文提出一種基于病毒-抗體免疫博弈機制的超寬帶WSN鏈路穩定算法,通過病毒-抗體免疫博弈機制改善區域節點的初始化及后續更新過程,采用多參數判定機制進一步優化區域間的鏈路,使用PSK預發射方式降低區域節點間的頻率干涉概率,最終解決鏈路擁塞問題并降低鏈路癱瘓概率。實驗結果表明,該算法具有良好的鏈路穩定性。下一步將引入區域間的鏈路綜合判定機制,以提高本文算法的鏈路切換效率及其在復雜環境下的部署性能。