基于偽隨機因子修正與爬蟲機制的無線傳感網路徑生成算法?

賴 玲，謝婭婭

(1.荊楚理工學院計算機工程學院，湖北 荊門 448000；2.荊楚理工學院，電子信息工程學院，湖北，荊門 448000)

無線傳感網(Wireless Sensor Network，WSN)技術作為“中國制造2025”重要組成部分之一，正在工業化4.0 進程中起到舉足輕重的支撐作用[1]。該技術主要采取自組織模式在一定地域內部署成本低廉的傳感節點，通過傳感節點進行數據采集、匯聚、傳輸至sink 節點，最終實現對某一空間分布區域內客體實現自主控制及數據感知，從而節約人力、物力并充分提升現有基礎設施的服務支撐能力[2]。由于傳感節點均采取無線通信方式，多部署在環境較為惡劣地域，若節點出現物理性損耗或能量受限，整個網絡的數據采集將會受到嚴重影響[3]。此外，無線傳感網多采用一次布撒成型的自組織部署模式，若某些節點及路徑因傳輸過載而導致能量消耗過高，則將因能量受限而導致出現路徑抖動，從而嚴重影響網絡性能[4]。因此，采取一定措施降低節點能耗并優化網絡傳輸路徑，成為當前無線傳感網研究領域的熱點[5]。

針對無線傳感網實際部署過程中存在的若干問題，研究者提出了一些具有前瞻性的無線傳感網路徑優化方案，如Gundabatini 等[6]提出了一種基于果蠅機制的無線傳感網路徑生成算法，將數據傳輸報文進行類型區分，盡量降低網絡節點及鏈路負載，并將若干能量較低的節點及路徑進行關閉處理，可顯著抑制鏈路抖動現象，使其具有較好的節點休眠性能。但是，該算法也存在節點利用率較低的不足，在網絡帶寬負載較高時，其路徑生成效果不佳，難以進一步降低鏈路抖動現象。Naim 等[7]基于網絡分層結構，提出了一種利用k-means 機制的無線傳感網路徑生成算法，其主要對層次數據分組報文定義傳輸數據結構，引入跳數搜集及路徑負反饋方案進行傳輸編碼，通過能量優化方式進行全網路由統一調度，可顯著降低因數據報文過載而導致路徑抖動問題，使其具有較好的網絡傳輸性能。然而，該算法在分層過程中需要頻繁對網絡節點進行層次分割，節點能量消耗水平較高，容易導致傳輸路徑出現抖動現象。Seyedakbar 等[8]鑒于被動式尋徑機制存在的網絡擁塞控制困難的不足，提出了一種基于主動式路徑搜尋機制的無線傳感網路徑生成算法，將節點剩余能量引入鏈路搜尋過程，采取平均能量最優準則裁決傳輸鏈路，優選能量較高的鏈路承擔數據傳輸功能，可顯著改善傳輸鏈路抖動問題，網絡實時傳輸性能卓越。但是，該算法需要頻繁進行網絡節點遍歷及能量排序操作，鏈路選取過程中對網絡穩定性要求較高，使得算法在節點及鏈路出現抖動時存在路徑生成效率較低的不足，難以適應較為復雜的網絡部署環境。

針對當前研究中存在的不足，提出了一種基于爬蟲機制的無線傳感網路徑生成算法。首先，按照節點能量及路徑跳數部署誘餌，并根據誘餌最大化原則誘導爬蟲來爬取剩余能量較高及傳輸跳數較少的節點，提高路徑節點的傳輸性能，降低能量受限而導致節點失效。并引入均等分割方法，對網絡區域進行柵格化處理，采取角度最小化原則來提高爬蟲感知能力，有效降低因熱點而導致節點出現受限現象，提升路徑健壯性能。隨后，通過評估節點剩余能量并引入回溯方式來構建偽隨機因子修正機制，以均衡路徑能耗，降低節點抖動頻次。仿真實驗證明了本文算法的性能。

1 本文網絡模型

典型的無線傳感網節點分布如圖1 所示:節點分布為矩形區域，網絡節點分為簇頭節點(Cluster Head，CH 節點)和簇成員節點(Cluster Members，CM節點)。其中，節點采用隨機部署模型，采用一次性布撒方式成網[9]。

圖1 無線傳感網節點分布

網絡部署完成后，傳感節點中源節點均需要通過搜尋中繼節點(Relay 節點)，并通過中繼節點將數據傳輸至sink 節點。考慮到傳統被動式路徑生成算法存在路徑篩選效率較低的問題，本文采取基于爬蟲機制的網絡模型來進行數據爬取:將源節點設置為爬蟲節點(Crawler)的初始位置，爬蟲搜尋路徑過程中，將根據網絡節點能量及鏈路來設置誘餌，誘餌為節點能量和傳輸鏈路的加權平均，其余爬蟲將根據誘餌的數量決定下一跳節點的篩選。網絡在搜尋路徑時，根據爬蟲行為差異特征，將爬蟲分為路徑生成爬蟲(Path Generation Crawler，PGC)和路徑回退爬蟲(Path Fallback Crawler，PFC)，其中。PGC拓撲移動的起點為源節點，PFC 拓撲移動的起點為sink 節點，見圖2。

圖2 爬蟲網絡模型

在圖2 所示的爬蟲網絡模型中，設無線傳感網在路徑生成的起始階段，整體網絡節點個數為n，網絡爬蟲個數為m，第x個PGC 爬蟲PGC(x)的起始路徑為源節點，按模型(1)所示的概率擇優選取中繼節點。模型(2)表示PGC(x)對中繼節點的期望，顯然對于無線傳感網而言，PGC(x)需要選取距離較短的節點作為中繼節點。當PGC(x)經過多個中繼節點并抵達目標節點后，將蛻變為路徑回退爬蟲PFC(x)，PFC(x)在從sink 節點回退到簇成員節點的過程中，將沿著誘餌最高的鏈路進行路徑爬取，從而完成整個路徑尋找過程。在此過程中，誘餌ω(t，i，j)將會按照 一 定速度逐步被蠶食。由于PFC(x)在回退過程中各節點剩余能量及鏈路傳輸質量會發生變化。因此，誘餌ω(t，i，j)也將因其余PGC 的影響而呈現衰弱態勢。誘餌越多的路徑將會有更高的幾率被選定為傳輸路徑，相應的誘餌數量會不斷增加，傳輸質量較差路徑的誘餌將不斷散發，從而被選取為傳輸路徑的概率亦將下降。其中，爬蟲PGC(x)在選取中繼節點時的概率P(t，x，i，j)為:

式中:x表示爬蟲PGC(x)，i和j分別表示爬蟲PGC(x)起始節點編號，ω(t，i，j)表示誘餌，ψ(t，i，j)表示爬蟲PGC(x) 在從移動開始時的期望值。ω(t，s，u)表示網絡中任意爬蟲PGC 從節點s移動到節點u時的誘餌，ψ(t，s，u)表示任意爬蟲PGC 從節點s移動到節點u時的期望值。L(i，j)表示節點i和j之間的距離，(xi，yi)和(xj，yj)分別表示節點i和節點j的坐標。a和b表示權重系數，

由模型(1)可知，爬蟲PGC(x)在進行路徑爬取過程中，將按照概率最大原則選取下一跳節點，并將距離因子按模型(2)賦予初始誘餌ω(t，i，j)。顯然，當期望值ψ(t，i，j)較高時，說明爬蟲與節點j間的距離較近，因此節點j將會有更高的概率被選舉為中繼節點。權重系數a越高，說明路徑中能量因素占比也將越高；權重系數b越高，說明路徑中距離因素占比也將越高。

此外，單純按能量因素對誘餌ω(t，i，j)進行賦值可能存在能量受限的不足，因此，本文采取迭代模型對誘餌ω(t，i，j)進行處理:

式中:Δω(t，i，j)表示誘餌增加系數，Δω(t，x，i，j)表示爬蟲PGC(x)在節點i和j之間爬取過程中的誘餌增加值，L(x，i，j)表示爬蟲PGC(x)在節點i和j之間反復爬取過程中所遍歷路徑的總長度；t＋n表示本次誘餌經歷n次爬取后形成的新誘餌。

2 本文無線傳感網路徑生成算法

由上文可知，采取模型(1)～模型(7)所示的爬取過程可在網絡中初步建立起可用傳輸路徑。但是，基于能量和路徑因素，單純采取爬取方式進行路徑篩選將會存在如下三點不足:

①存在能量受限的可能性。無線傳感網節點均需要通過無線方式進行數據傳輸，若爬蟲完全按能量因素并采取模型(1)進行路徑生成時，可能導致優質傳輸路徑出現能量受限的現象[10]。

②網絡拓撲出現空洞。無線傳感網均采用自組織方式進行組網，爬蟲進行路徑爬取的過程也是網絡拓撲更新的過程，若某節點因爬蟲爬取頻率過快，或者該節點與周圍節點距離均較為接近，則將因節點能量失效較快而導致拓撲出現空洞，降低了所生成路徑的傳輸性能[11]。

③中繼節點的多跳性能出現下降現象。模型(6)基于爬取路徑長度的方式增加誘餌量，雖然能夠以較快速度積累誘餌，但誘餌量增加可能會導致路徑以更高的頻率被爬蟲爬取，導致中繼節點出現能量受限現象，從而降低了中繼節點的多跳性能。

因此，針對單純爬取方式生成傳輸路徑存在的不足，提出了一種基于基于爬蟲機制的無線傳感網路徑生成算法，其主要由基于柵格－角度機制的路徑爬取激勵和基于偽隨機因子修正機制的節點轉移概率更新兩部分構成。

2.1 基于柵格－角度機制的路徑能量爬取激勵

考慮到爬蟲PGC(x)主要按概率最大化原則并采取模型(1)來實現路徑生成，而模型(1)所示的概率P(t，x，i，j)在頻繁爬取過程中容易出現死鎖現象，導致環路徑的形成。此外，在任意時刻網絡中的簇頭節點和簇成員節點均存在休眠現象，當且僅當節點能量恢復完畢時將重新啟動數據傳輸過程，會導致爬蟲PGC(x)在進行路徑爬取過程中將面臨網絡拓撲更迭較快的問題。此外，當爬蟲PGC(x)爬取過程中出現下一跳節點缺失現象時，將會回退至起始位置重新進行路徑爬取，從而導致節點能量消耗較快及爬取時間過長的不足。因此，為降低節點能量消耗并降低爬取時間，本文對網絡進行柵格化分割，如圖3 所示。

圖3 網絡柵格化分割

采用柵格化對網絡區域進行分割后，可實現對傳輸路徑的層次化評估，降低路徑長度:在圖3 中，網絡按照柵格進行分割，其中柵格間距離為R。爬蟲PGC(x)僅能選取H－1 和H＋1 兩層節點進行路徑爬取，與該爬蟲相距在2R距離外的節點C、B將被拋棄，規避因傳輸路徑過長而導致誘餌量下降的現象，改善節點能量受限概率。

但是，爬蟲按柵格化網絡進行爬取過程中可能存在多種選擇，如圖3 中的節點A1、A2、A3、A4均可作為下一跳傳輸節點。這是由于傳感網具有節點密度較高的特性，使得節點個數較多，爬蟲可供選擇的下一跳中繼節點將存在多樣性。此外，若將鄰域范圍內節點確定為下一跳傳輸節點，也可能存在對sink 節點定位不足的問題，使得爬蟲運動方向遠離sink 節點，如圖3 所示，爬蟲若選取A1作為下一跳傳輸節點，將會出現遠離sink 的現象，使得傳輸路徑不斷增長，降低了網絡傳輸性能。

為降低傳輸路徑長度，提高網絡傳輸性能，進一步獲取爬蟲與各鄰域內節點間的角度，如圖4 所示，爬蟲爬取過程中，優選角度最小的節點作為下一跳傳輸節點，此時爬蟲對應爬取路徑的性能要顯著低于其他可用路徑。

圖4 按角度篩選下一跳中繼節點

采取遍歷模式對柵格進行處理，按角度篩選下一跳中繼節點，雖然能夠精確生成路徑最佳的傳輸路徑。但是，若某柵格內節點較多時將會出現多種選擇，如圖5 所示。對于sink 節點隸屬柵格內的節點而言，因其均有可能承擔最后一跳節點的傳輸任務，導致能量消耗量急劇上升。若節點能量耗盡，則整個網絡傳輸路徑將會受到嚴重影響，導致路徑質量再次出現下降現象。為了降低柵格節點過載現象，本文基于柵格－角度機制，設計了一種路徑能量爬取激勵方法:方法對柵格內被爬取頻次較多的節點進行標識，禁止其余爬蟲對該節點進行爬取。此外，將能量剩余較高的節點增補進入路徑，以便能夠讓柵格內節點有均等機會承擔數據傳輸任務，從而降低網絡平均能量消耗，增加網絡生存時間。

圖5 路徑能量爬取方法

顯然，對于圖5 節點B1、B2、B3而言，若所處柵格區域內能量消耗較高，則按柵格－角度機制獲取的角度及距離均無法對這三個節點進行區分。因此，爬蟲PGC(x)在不斷進行路徑篩選過程中，將對某柵格內節點的剩余能量進行排序并篩選出能量最低的節點，記錄其能量值為Emin(x)，并記錄爬蟲PGC(x)到該節點的跳數L(x)，按模型(8)來構建能量激勵閾值EJL(x)，并通過該能量激勵閾值進行路徑爬取:

爬蟲在下一跳節點選取過程中，優先選取模型(8)所示的能量激勵閾值最高的節點作為下一跳節點。不過，同層次節點B1、B2、B3之間可能存在數據傳輸現象，見圖6，在爬取過程中，爬蟲將不斷計算下一跳節點的能量激勵閾值EJL(x)，具體工作原理見圖6。

圖6 能量激勵閾值對路徑的判定

在圖6 中，不妨做如下假設:PGC(x1)，B2，sink為爬蟲PGC(x1)的路徑爬取結果，PGC(x2)，A1，B1，B2，sink 為爬蟲PGC(x2)的路徑爬取結果。當爬蟲PGC(x1)和爬蟲PGC(x2)同時抵達目的節點時，網絡將按模型(8)記錄爬蟲PGC(x1)和爬蟲PGC(x2)的能量激勵閾值EJL(x1)和EJL(x2)，并按如下規則進行路徑判定:

對于模型(9)而言，當且僅當某爬蟲的能量激勵閾值較高時，其爬取的路徑將被選定為網絡傳輸路徑。

當路徑選擇完畢時，即爬蟲PGC(x)最終抵達sink 節點后，由模型(1)～(7)可知，爬蟲PGC(x)將蛻變為路徑回退爬蟲PFC(x)，導致誘餌ω(t，i，j)發生變化。為降低誘餌失效概率并引導爬蟲以較快速率接近sink 節點，對誘餌ω(t，i，j)進行如下處理:

式中:i表示當前爬蟲PGC(x)所處的節點，j表示爬蟲PGC(x)擬爬取的下一跳節點，E(t，i，j)表示爬蟲PGC(x)從i移動至j時所剩余的能量，Eall(t，i，j)表示路徑上全部節點所剩下的能量，θ表示按柵格－角度處理后所選取的最小角度。L(i，j)表示節點i和節點j之間路徑距離，L(j，sink)表示節點j與sink節點的路徑距離。

PGC(x)對路徑爬取完畢并按模型(10)更新誘餌后，將進入休眠狀態，如圖7 所示。

圖7 基于柵格－角度機制的路徑能量爬取激勵

2.2 基于偽隨機因子修正機制的節點轉移概率更新

完成基于柵格－角度機制的路徑能量爬取激勵過程后，源節點與sink 節點間將建立數據交互關系，然而由于無線傳感網節點具有的高密集度特性，使得爬蟲難以實時獲取各節點的剩余能量，特別是網絡節點處于休眠狀態時，爬蟲對路徑感知的能力將急劇下降，導致模型(1)所示的狀態轉移概率難以及時獲取，因此sink 節點回溯至源節點的路徑難以生成。針對該問題，本文設計了偽隨機因子，用以提高爬蟲PGC(x)對路徑感知的能力，均衡路徑上能量剩余較低且被爬取頻次較高節點的能耗，進一步增強網絡傳輸穩定性能。

針對當前爬蟲PGC(x)，起點位置為i，下一跳節點位置為j，按如下模型獲取偽隨機因子Ω(i，j):

式中:E0(x，i)表示節點i的剩余能量，E0(x，j)表示節點j的剩余能量，E0(x)表示節點i的初始能量。

為進一步評估爬蟲PGC(x)進行回溯操作時的概率，對模型(1)改寫如下:

爬蟲PGC(x)進行回溯操作時，下一跳節點篩選時優先根據模型(12)所示獲取偽隨機因子，并對模型(1)修正后再進行下一跳節點篩選，從而生成sink 節點回溯至源節點的可用路徑。詳細步驟如下所示:

Step 1 針對當前爬蟲，首先獲取節點剩余能量、節點初始能量、下一跳節點剩余能量，并記錄當前所在節點位置和下一跳節點，如圖8 所示。

圖8 基于偽隨機因子修正機制的節點轉移概率更新

Step 2 按模型(12)所示構建偽隨機因子，若同時存在多個可用下一跳節點，將同時計算并獲取多個偽隨機因子，轉Step 3。

Step 3 按模型(1)重新生成并更新節點轉移概率，僅僅選取更新概率最高的節點作為下一跳節點。

Step 4 逐次進行Step 1～3 過程，直到sink 節點至源節點的可用路徑成功生成。

3 仿真實驗

為便于對比本文算法的性能，設置NS2 仿真實驗環境(Network Simulator Version 2，NS2)[12]。節點散布區域為矩形，大小為512 m×512 m；部署模型采取隨機撒布模式，均采用sink 節點進行遠程供電，位置不變，其余仿真參數見表1。為突出所提算法的優勢，將當前常用的基于移動數據采集機制的無線傳感網路徑生成算法[13](Path Discovery Approach For Mobile Data Gathering in WSN，MDG-PDA 算法)和基于集成尋徑機制的無線傳感網路徑生成算法[14](Ensemble Path Finding In Wireless Sensor Networks，EPF 算法)作為對照組。測試指標選取可用路徑條數、節點受限比例、網絡數據傳輸帶寬三項。其中，MDG-PDA 算法一般用于需要高速傳輸數據且實時性較高的應用場景，例如車載網等方面。EPF 算法多用于立體傳輸場景，諸如無人機、戰術數據鏈等方面。兩種算法均在當前前沿領域有一定的應用。不失一般性，采用固定方式部署節點，部署區域為矩形，詳細仿真參數表見表1。

表1 仿真參數表

3.1 可用路徑條數

圖9 為高斯信道和萊斯信道兩種信道條件下，本文算法、MDG-PDA 算法和EPF 算法的可用路徑條數測試結果。由圖可知，本文算法具有可用路徑條數較高的優勢，這是由于本文算法針對無線傳感網路徑生成過程中存在的節點受限現象，將網絡分布區域進行柵格化處理，基于角度優先原則確定中繼節點，可顯著降低傳輸路徑長度，具有路徑生成質量較高的特點。特別是本文算法針對部分中繼節點使用頻次較高的特點，在同柵格區域內采取能量激勵閾值模式確定較低能量的節點作為中繼傳輸節點，因而可顯著降低因能量受限而導致路徑抖動的現象，可用路徑條數較多。MDG-PDA 算法主要采取移動sink 節點的方式搜尋可用路徑，將路徑切割為弦與線段之和，導致簇內路徑跳數較高，使得該算法可用路徑長度較長，進而使得中繼節點使用強度要顯著高于本文算法，路徑因能量受限極易出現抖動現象，因而該算法的可用路徑條數較低。EPF 算法采用非均衡聚類模式對網絡區域進行劃分，承擔中繼節點的簇頭節點亦存在非均衡特性，使得節點能量消耗水平較高，特別是該算法按照時長反饋最短方式篩選中繼傳輸節點，初始篩選的中繼傳輸節點受限時易引發連鎖受限現象，從而降低了該算法的可用路徑條數。

圖9 可用路徑條數測試

3.2 節點受限比例

圖10 為高斯信道和萊斯信道條件下，本文算法與MDG-PDA 算法和EPF 算法在節點受限比例的測試結果。由圖可知，本文算法節點受限比例始終處于較低水平，顯示了較高的路徑節點爬取質量。這是由于本文算法除對網絡分布區域進行柵格化處理從而減少路徑重復選擇，針對傳輸熱點現象，采用能量激勵閾值均衡化熱點區域節點使用頻次，因而降低傳感節點被反復選取概率，節點較少出現因能量消耗過高而受限的現象。MDG-PDA 算法雖然采用分區機制，并結合邊長切割方案初選簇內傳輸路徑，由于該算法路徑冗余度較高，使得傳輸拓撲較為復雜，中繼節點同時被多個節點爬取的概率要顯著高于本文算法，導致節點能量消耗水平較高，從而引發節點較易出現受限現象。EPF 算法考慮到簇頭節點作為中繼傳輸節點的重要性，優選時長反饋較短的節點作為下一跳節點，然而由于該方案未對簇頭節點附近區域出現的傳輸熱點現象進行處理，使得簇頭節點易出現頻繁的數據重傳輸事件，導致節點能耗水平高于本文算法，從而增加了節點受限比例，表現出了較為不穩定的數據傳輸性能。

圖10 節點受限比例測試

3.3 網絡傳輸帶寬

圖11 為高斯信道和萊斯信道條件下，本文算法、MDG-PDA 算法和EPF 算法的網絡傳輸帶寬測試結果。為不失一般性，本文將網絡傳輸帶寬規定為sink 節點接收的實時帶寬。由圖11 可知，本文算法執行過程中，同等節點傳輸率條件下能實現更高的網絡帶寬，體現了較好的網絡傳輸性能。這是由于本文算法除通過柵格－角度機制優化傳輸路徑之外，還采用能量激勵閾值方式進一步降低網絡傳輸熱點現象，因而具有較低的節點受限現象。此外，本文算法設計了偽隨機因子機制，均衡路徑上能量剩余較低且被爬取頻次較高節點的能耗，可實現逐點爬取能量較為均衡的網絡節點，因而網絡傳輸性能較高，體現了較高的網絡傳輸帶寬。MDG-PDA算法在采用邊長切割方案生成簇內傳輸路徑時，未對臨近簇頭附近的熱點進行能量均衡化處理，節點受限現象較為嚴重，使得該算法的路徑抖動情況要高于本文算法，網絡傳輸帶寬因而較低。EPF 算法雖然采用時長反饋最短機制對高負載進行均衡化處理，然而由于采用非均衡聚類模式對網絡區域進行劃分，使得網絡節點傳輸流量亦呈現非均衡特性，導致節點負載程度要顯著高于本文算法，降低了算法的傳輸性能，因而同等節點傳輸率條件下該算法占用的網絡帶寬要低于所提算法。

圖11 網絡傳輸帶寬測試

4 結束語

針對當前無線傳感網部署過程中存在的路徑感知能力較差、節點及網絡性能較弱等不足，提出了一種基于爬蟲機制的無線傳感網路徑生成算法。通過對網絡區域進行柵格－角度分割，設計了一種新的路徑爬取激勵方法。可優化節點爬取路徑的健壯性能，均衡節點能量消耗及傳輸跳數，顯著提高爬蟲運動速度及路徑生成效率。隨后，通過評估節點能耗，設計了基于偽隨機因子修正機制的節點轉移概率更新方法，主要采取均衡路徑能耗的方式，優選能量剩余較高且被爬取頻次較高節點，進一步降低節點抖動頻次，提升網絡傳輸能力。

下一步，將針對本文算法在移動環境中性能較差的弱點，擬引入移動拓撲－頻次自適應控制機制，提升爬蟲對高拓撲更迭環境的適應能力，提升本文算法在節點移動場合下的部署效果。