基于偽隨機(jī)因子修正與爬蟲(chóng)機(jī)制的無(wú)線傳感網(wǎng)路徑生成算法?

賴 玲，謝婭婭

(1.荊楚理工學(xué)院計(jì)算機(jī)工程學(xué)院，湖北 荊門(mén) 448000；2.荊楚理工學(xué)院，電子信息工程學(xué)院，湖北，荊門(mén) 448000)

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

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

針對(duì)當(dāng)前研究中存在的不足，提出了一種基于爬蟲(chóng)機(jī)制的無(wú)線傳感網(wǎng)路徑生成算法。首先，按照節(jié)點(diǎn)能量及路徑跳數(shù)部署誘餌，并根據(jù)誘餌最大化原則誘導(dǎo)爬蟲(chóng)來(lái)爬取剩余能量較高及傳輸跳數(shù)較少的節(jié)點(diǎn)，提高路徑節(jié)點(diǎn)的傳輸性能，降低能量受限而導(dǎo)致節(jié)點(diǎn)失效。并引入均等分割方法，對(duì)網(wǎng)絡(luò)區(qū)域進(jìn)行柵格化處理，采取角度最小化原則來(lái)提高爬蟲(chóng)感知能力，有效降低因熱點(diǎn)而導(dǎo)致節(jié)點(diǎn)出現(xiàn)受限現(xiàn)象，提升路徑健壯性能。隨后，通過(guò)評(píng)估節(jié)點(diǎn)剩余能量并引入回溯方式來(lái)構(gòu)建偽隨機(jī)因子修正機(jī)制，以均衡路徑能耗，降低節(jié)點(diǎn)抖動(dòng)頻次。仿真實(shí)驗(yàn)證明了本文算法的性能。

1 本文網(wǎng)絡(luò)模型

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

圖1 無(wú)線傳感網(wǎng)節(jié)點(diǎn)分布

網(wǎng)絡(luò)部署完成后，傳感節(jié)點(diǎn)中源節(jié)點(diǎn)均需要通過(guò)搜尋中繼節(jié)點(diǎn)(Relay 節(jié)點(diǎn))，并通過(guò)中繼節(jié)點(diǎn)將數(shù)據(jù)傳輸至sink 節(jié)點(diǎn)?？紤]到傳統(tǒng)被動(dòng)式路徑生成算法存在路徑篩選效率較低的問(wèn)題，本文采取基于爬蟲(chóng)機(jī)制的網(wǎng)絡(luò)模型來(lái)進(jìn)行數(shù)據(jù)爬取:將源節(jié)點(diǎn)設(shè)置為爬蟲(chóng)節(jié)點(diǎn)(Crawler)的初始位置，爬蟲(chóng)搜尋路徑過(guò)程中，將根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)能量及鏈路來(lái)設(shè)置誘餌，誘餌為節(jié)點(diǎn)能量和傳輸鏈路的加權(quán)平均，其余爬蟲(chóng)將根據(jù)誘餌的數(shù)量決定下一跳節(jié)點(diǎn)的篩選。網(wǎng)絡(luò)在搜尋路徑時(shí)，根據(jù)爬蟲(chóng)行為差異特征，將爬蟲(chóng)分為路徑生成爬蟲(chóng)(Path Generation Crawler，PGC)和路徑回退爬蟲(chóng)(Path Fallback Crawler，PFC)，其中。PGC拓?fù)湟苿?dòng)的起點(diǎn)為源節(jié)點(diǎn)，PFC 拓?fù)湟苿?dòng)的起點(diǎn)為sink 節(jié)點(diǎn)，見(jiàn)圖2。

圖2 爬蟲(chóng)網(wǎng)絡(luò)模型

在圖2 所示的爬蟲(chóng)網(wǎng)絡(luò)模型中，設(shè)無(wú)線傳感網(wǎng)在路徑生成的起始階段，整體網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)為n，網(wǎng)絡(luò)爬蟲(chóng)個(gè)數(shù)為m，第x個(gè)PGC 爬蟲(chóng)PGC(x)的起始路徑為源節(jié)點(diǎn)，按模型(1)所示的概率擇優(yōu)選取中繼節(jié)點(diǎn)。模型(2)表示PGC(x)對(duì)中繼節(jié)點(diǎn)的期望，顯然對(duì)于無(wú)線傳感網(wǎng)而言，PGC(x)需要選取距離較短的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。當(dāng)PGC(x)經(jīng)過(guò)多個(gè)中繼節(jié)點(diǎn)并抵達(dá)目標(biāo)節(jié)點(diǎn)后，將蛻變?yōu)槁窂交赝伺老x(chóng)PFC(x)，PFC(x)在從sink 節(jié)點(diǎn)回退到簇成員節(jié)點(diǎn)的過(guò)程中，將沿著誘餌最高的鏈路進(jìn)行路徑爬取，從而完成整個(gè)路徑尋找過(guò)程。在此過(guò)程中，誘餌ω(t，i，j)將會(huì)按照 一 定速度逐步被蠶食。由于PFC(x)在回退過(guò)程中各節(jié)點(diǎn)剩余能量及鏈路傳輸質(zhì)量會(huì)發(fā)生變化。因此，誘餌ω(t，i，j)也將因其余PGC 的影響而呈現(xiàn)衰弱態(tài)勢(shì)。誘餌越多的路徑將會(huì)有更高的幾率被選定為傳輸路徑，相應(yīng)的誘餌數(shù)量會(huì)不斷增加，傳輸質(zhì)量較差路徑的誘餌將不斷散發(fā)，從而被選取為傳輸路徑的概率亦將下降。其中，爬蟲(chóng)PGC(x)在選取中繼節(jié)點(diǎn)時(shí)的概率P(t，x，i，j)為:

式中:x表示爬蟲(chóng)PGC(x)，i和j分別表示爬蟲(chóng)PGC(x)起始節(jié)點(diǎn)編號(hào)，ω(t，i，j)表示誘餌，ψ(t，i，j)表示爬蟲(chóng)PGC(x) 在從移動(dòng)開(kāi)始時(shí)的期望值。ω(t，s，u)表示網(wǎng)絡(luò)中任意爬蟲(chóng)PGC 從節(jié)點(diǎn)s移動(dòng)到節(jié)點(diǎn)u時(shí)的誘餌，ψ(t，s，u)表示任意爬蟲(chóng)PGC 從節(jié)點(diǎn)s移動(dòng)到節(jié)點(diǎn)u時(shí)的期望值。L(i，j)表示節(jié)點(diǎn)i和j之間的距離，(xi，yi)和(xj，yj)分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的坐標(biāo)。a和b表示權(quán)重系數(shù)，

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

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

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

2 本文無(wú)線傳感網(wǎng)路徑生成算法

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

①存在能量受限的可能性。無(wú)線傳感網(wǎng)節(jié)點(diǎn)均需要通過(guò)無(wú)線方式進(jìn)行數(shù)據(jù)傳輸，若爬蟲(chóng)完全按能量因素并采取模型(1)進(jìn)行路徑生成時(shí)，可能導(dǎo)致優(yōu)質(zhì)傳輸路徑出現(xiàn)能量受限的現(xiàn)象[10]。

②網(wǎng)絡(luò)拓?fù)涑霈F(xiàn)空洞。無(wú)線傳感網(wǎng)均采用自組織方式進(jìn)行組網(wǎng)，爬蟲(chóng)進(jìn)行路徑爬取的過(guò)程也是網(wǎng)絡(luò)拓?fù)涓碌倪^(guò)程，若某節(jié)點(diǎn)因爬蟲(chóng)爬取頻率過(guò)快，或者該節(jié)點(diǎn)與周圍節(jié)點(diǎn)距離均較為接近，則將因節(jié)點(diǎn)能量失效較快而導(dǎo)致拓?fù)涑霈F(xiàn)空洞，降低了所生成路徑的傳輸性能[11]。

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

因此，針對(duì)單純爬取方式生成傳輸路徑存在的不足，提出了一種基于基于爬蟲(chóng)機(jī)制的無(wú)線傳感網(wǎng)路徑生成算法，其主要由基于柵格－角度機(jī)制的路徑爬取激勵(lì)和基于偽隨機(jī)因子修正機(jī)制的節(jié)點(diǎn)轉(zhuǎn)移概率更新兩部分構(gòu)成。

2.1 基于柵格－角度機(jī)制的路徑能量爬取激勵(lì)

考慮到爬蟲(chóng)PGC(x)主要按概率最大化原則并采取模型(1)來(lái)實(shí)現(xiàn)路徑生成，而模型(1)所示的概率P(t，x，i，j)在頻繁爬取過(guò)程中容易出現(xiàn)死鎖現(xiàn)象，導(dǎo)致環(huán)路徑的形成。此外，在任意時(shí)刻網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)和簇成員節(jié)點(diǎn)均存在休眠現(xiàn)象，當(dāng)且僅當(dāng)節(jié)點(diǎn)能量恢復(fù)完畢時(shí)將重新啟動(dòng)數(shù)據(jù)傳輸過(guò)程，會(huì)導(dǎo)致爬蟲(chóng)PGC(x)在進(jìn)行路徑爬取過(guò)程中將面臨網(wǎng)絡(luò)拓?fù)涓^快的問(wèn)題。此外，當(dāng)爬蟲(chóng)PGC(x)爬取過(guò)程中出現(xiàn)下一跳節(jié)點(diǎn)缺失現(xiàn)象時(shí)，將會(huì)回退至起始位置重新進(jìn)行路徑爬取，從而導(dǎo)致節(jié)點(diǎn)能量消耗較快及爬取時(shí)間過(guò)長(zhǎng)的不足。因此，為降低節(jié)點(diǎn)能量消耗并降低爬取時(shí)間，本文對(duì)網(wǎng)絡(luò)進(jìn)行柵格化分割，如圖3 所示。

圖3 網(wǎng)絡(luò)柵格化分割

采用柵格化對(duì)網(wǎng)絡(luò)區(qū)域進(jìn)行分割后，可實(shí)現(xiàn)對(duì)傳輸路徑的層次化評(píng)估，降低路徑長(zhǎng)度:在圖3 中，網(wǎng)絡(luò)按照柵格進(jìn)行分割，其中柵格間距離為R。爬蟲(chóng)PGC(x)僅能選取H－1 和H＋1 兩層節(jié)點(diǎn)進(jìn)行路徑爬取，與該爬蟲(chóng)相距在2R距離外的節(jié)點(diǎn)C、B將被拋棄，規(guī)避因傳輸路徑過(guò)長(zhǎng)而導(dǎo)致誘餌量下降的現(xiàn)象，改善節(jié)點(diǎn)能量受限概率。

但是，爬蟲(chóng)按柵格化網(wǎng)絡(luò)進(jìn)行爬取過(guò)程中可能存在多種選擇，如圖3 中的節(jié)點(diǎn)A1、A2、A3、A4均可作為下一跳傳輸節(jié)點(diǎn)。這是由于傳感網(wǎng)具有節(jié)點(diǎn)密度較高的特性，使得節(jié)點(diǎn)個(gè)數(shù)較多，爬蟲(chóng)可供選擇的下一跳中繼節(jié)點(diǎn)將存在多樣性。此外，若將鄰域范圍內(nèi)節(jié)點(diǎn)確定為下一跳傳輸節(jié)點(diǎn)，也可能存在對(duì)sink 節(jié)點(diǎn)定位不足的問(wèn)題，使得爬蟲(chóng)運(yùn)動(dòng)方向遠(yuǎn)離sink 節(jié)點(diǎn)，如圖3 所示，爬蟲(chóng)若選取A1作為下一跳傳輸節(jié)點(diǎn)，將會(huì)出現(xiàn)遠(yuǎn)離sink 的現(xiàn)象，使得傳輸路徑不斷增長(zhǎng)，降低了網(wǎng)絡(luò)傳輸性能。

為降低傳輸路徑長(zhǎng)度，提高網(wǎng)絡(luò)傳輸性能，進(jìn)一步獲取爬蟲(chóng)與各鄰域內(nèi)節(jié)點(diǎn)間的角度，如圖4 所示，爬蟲(chóng)爬取過(guò)程中，優(yōu)選角度最小的節(jié)點(diǎn)作為下一跳傳輸節(jié)點(diǎn)，此時(shí)爬蟲(chóng)對(duì)應(yīng)爬取路徑的性能要顯著低于其他可用路徑。

圖4 按角度篩選下一跳中繼節(jié)點(diǎn)

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

圖5 路徑能量爬取方法

顯然，對(duì)于圖5 節(jié)點(diǎn)B1、B2、B3而言，若所處柵格區(qū)域內(nèi)能量消耗較高，則按柵格－角度機(jī)制獲取的角度及距離均無(wú)法對(duì)這三個(gè)節(jié)點(diǎn)進(jìn)行區(qū)分。因此，爬蟲(chóng)PGC(x)在不斷進(jìn)行路徑篩選過(guò)程中，將對(duì)某柵格內(nèi)節(jié)點(diǎn)的剩余能量進(jìn)行排序并篩選出能量最低的節(jié)點(diǎn)，記錄其能量值為Emin(x)，并記錄爬蟲(chóng)PGC(x)到該節(jié)點(diǎn)的跳數(shù)L(x)，按模型(8)來(lái)構(gòu)建能量激勵(lì)閾值EJL(x)，并通過(guò)該能量激勵(lì)閾值進(jìn)行路徑爬取:

爬蟲(chóng)在下一跳節(jié)點(diǎn)選取過(guò)程中，優(yōu)先選取模型(8)所示的能量激勵(lì)閾值最高的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。不過(guò)，同層次節(jié)點(diǎn)B1、B2、B3之間可能存在數(shù)據(jù)傳輸現(xiàn)象，見(jiàn)圖6，在爬取過(guò)程中，爬蟲(chóng)將不斷計(jì)算下一跳節(jié)點(diǎn)的能量激勵(lì)閾值EJL(x)，具體工作原理見(jiàn)圖6。

圖6 能量激勵(lì)閾值對(duì)路徑的判定

在圖6 中，不妨做如下假設(shè):PGC(x1)，B2，sink為爬蟲(chóng)PGC(x1)的路徑爬取結(jié)果，PGC(x2)，A1，B1，B2，sink 為爬蟲(chóng)PGC(x2)的路徑爬取結(jié)果。當(dāng)爬蟲(chóng)PGC(x1)和爬蟲(chóng)PGC(x2)同時(shí)抵達(dá)目的節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)將按模型(8)記錄爬蟲(chóng)PGC(x1)和爬蟲(chóng)PGC(x2)的能量激勵(lì)閾值EJL(x1)和EJL(x2)，并按如下規(guī)則進(jìn)行路徑判定:

對(duì)于模型(9)而言，當(dāng)且僅當(dāng)某爬蟲(chóng)的能量激勵(lì)閾值較高時(shí)，其爬取的路徑將被選定為網(wǎng)絡(luò)傳輸路徑。

當(dāng)路徑選擇完畢時(shí)，即爬蟲(chóng)PGC(x)最終抵達(dá)sink 節(jié)點(diǎn)后，由模型(1)～(7)可知，爬蟲(chóng)PGC(x)將蛻變?yōu)槁窂交赝伺老x(chóng)PFC(x)，導(dǎo)致誘餌ω(t，i，j)發(fā)生變化。為降低誘餌失效概率并引導(dǎo)爬蟲(chóng)以較快速率接近sink 節(jié)點(diǎn)，對(duì)誘餌ω(t，i，j)進(jìn)行如下處理:

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

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

圖7 基于柵格－角度機(jī)制的路徑能量爬取激勵(lì)

2.2 基于偽隨機(jī)因子修正機(jī)制的節(jié)點(diǎn)轉(zhuǎn)移概率更新

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

針對(duì)當(dāng)前爬蟲(chóng)PGC(x)，起點(diǎn)位置為i，下一跳節(jié)點(diǎn)位置為j，按如下模型獲取偽隨機(jī)因子Ω(i，j):

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

為進(jìn)一步評(píng)估爬蟲(chóng)PGC(x)進(jìn)行回溯操作時(shí)的概率，對(duì)模型(1)改寫(xiě)如下:

爬蟲(chóng)PGC(x)進(jìn)行回溯操作時(shí)，下一跳節(jié)點(diǎn)篩選時(shí)優(yōu)先根據(jù)模型(12)所示獲取偽隨機(jī)因子，并對(duì)模型(1)修正后再進(jìn)行下一跳節(jié)點(diǎn)篩選，從而生成sink 節(jié)點(diǎn)回溯至源節(jié)點(diǎn)的可用路徑。詳細(xì)步驟如下所示:

Step 1 針對(duì)當(dāng)前爬蟲(chóng)，首先獲取節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)初始能量、下一跳節(jié)點(diǎn)剩余能量，并記錄當(dāng)前所在節(jié)點(diǎn)位置和下一跳節(jié)點(diǎn)，如圖8 所示。

圖8 基于偽隨機(jī)因子修正機(jī)制的節(jié)點(diǎn)轉(zhuǎn)移概率更新

Step 2 按模型(12)所示構(gòu)建偽隨機(jī)因子，若同時(shí)存在多個(gè)可用下一跳節(jié)點(diǎn)，將同時(shí)計(jì)算并獲取多個(gè)偽隨機(jī)因子，轉(zhuǎn)Step 3。

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

Step 4 逐次進(jìn)行Step 1～3 過(guò)程，直到sink 節(jié)點(diǎn)至源節(jié)點(diǎn)的可用路徑成功生成。

3 仿真實(shí)驗(yàn)

為便于對(duì)比本文算法的性能，設(shè)置NS2 仿真實(shí)驗(yàn)環(huán)境(Network Simulator Version 2，NS2)[12]。節(jié)點(diǎn)散布區(qū)域?yàn)榫匦危笮?12 m×512 m；部署模型采取隨機(jī)撒布模式，均采用sink 節(jié)點(diǎn)進(jìn)行遠(yuǎn)程供電，位置不變，其余仿真參數(shù)見(jiàn)表1。為突出所提算法的優(yōu)勢(shì)，將當(dāng)前常用的基于移動(dòng)數(shù)據(jù)采集機(jī)制的無(wú)線傳感網(wǎng)路徑生成算法[13](Path Discovery Approach For Mobile Data Gathering in WSN，MDG-PDA 算法)和基于集成尋徑機(jī)制的無(wú)線傳感網(wǎng)路徑生成算法[14](Ensemble Path Finding In Wireless Sensor Networks，EPF 算法)作為對(duì)照組。測(cè)試指標(biāo)選取可用路徑條數(shù)、節(jié)點(diǎn)受限比例、網(wǎng)絡(luò)數(shù)據(jù)傳輸帶寬三項(xiàng)。其中，MDG-PDA 算法一般用于需要高速傳輸數(shù)據(jù)且實(shí)時(shí)性較高的應(yīng)用場(chǎng)景，例如車載網(wǎng)等方面。EPF 算法多用于立體傳輸場(chǎng)景，諸如無(wú)人機(jī)、戰(zhàn)術(shù)數(shù)據(jù)鏈等方面。兩種算法均在當(dāng)前前沿領(lǐng)域有一定的應(yīng)用。不失一般性，采用固定方式部署節(jié)點(diǎn)，部署區(qū)域?yàn)榫匦?，詳?xì)仿真參數(shù)表見(jiàn)表1。

表1 仿真參數(shù)表

3.1 可用路徑條數(shù)

圖9 為高斯信道和萊斯信道兩種信道條件下，本文算法、MDG-PDA 算法和EPF 算法的可用路徑條數(shù)測(cè)試結(jié)果。由圖可知，本文算法具有可用路徑條數(shù)較高的優(yōu)勢(shì)，這是由于本文算法針對(duì)無(wú)線傳感網(wǎng)路徑生成過(guò)程中存在的節(jié)點(diǎn)受限現(xiàn)象，將網(wǎng)絡(luò)分布區(qū)域進(jìn)行柵格化處理，基于角度優(yōu)先原則確定中繼節(jié)點(diǎn)，可顯著降低傳輸路徑長(zhǎng)度，具有路徑生成質(zhì)量較高的特點(diǎn)。特別是本文算法針對(duì)部分中繼節(jié)點(diǎn)使用頻次較高的特點(diǎn)，在同柵格區(qū)域內(nèi)采取能量激勵(lì)閾值模式確定較低能量的節(jié)點(diǎn)作為中繼傳輸節(jié)點(diǎn)，因而可顯著降低因能量受限而導(dǎo)致路徑抖動(dòng)的現(xiàn)象，可用路徑條數(shù)較多。MDG-PDA 算法主要采取移動(dòng)sink 節(jié)點(diǎn)的方式搜尋可用路徑，將路徑切割為弦與線段之和，導(dǎo)致簇內(nèi)路徑跳數(shù)較高，使得該算法可用路徑長(zhǎng)度較長(zhǎng)，進(jìn)而使得中繼節(jié)點(diǎn)使用強(qiáng)度要顯著高于本文算法，路徑因能量受限極易出現(xiàn)抖動(dòng)現(xiàn)象，因而該算法的可用路徑條數(shù)較低。EPF 算法采用非均衡聚類模式對(duì)網(wǎng)絡(luò)區(qū)域進(jìn)行劃分，承擔(dān)中繼節(jié)點(diǎn)的簇頭節(jié)點(diǎn)亦存在非均衡特性，使得節(jié)點(diǎn)能量消耗水平較高，特別是該算法按照時(shí)長(zhǎng)反饋?zhàn)疃谭绞胶Y選中繼傳輸節(jié)點(diǎn)，初始篩選的中繼傳輸節(jié)點(diǎn)受限時(shí)易引發(fā)連鎖受限現(xiàn)象，從而降低了該算法的可用路徑條數(shù)。

圖9 可用路徑條數(shù)測(cè)試

3.2 節(jié)點(diǎn)受限比例

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

圖10 節(jié)點(diǎn)受限比例測(cè)試

3.3 網(wǎng)絡(luò)傳輸帶寬

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

圖11 網(wǎng)絡(luò)傳輸帶寬測(cè)試

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

針對(duì)當(dāng)前無(wú)線傳感網(wǎng)部署過(guò)程中存在的路徑感知能力較差、節(jié)點(diǎn)及網(wǎng)絡(luò)性能較弱等不足，提出了一種基于爬蟲(chóng)機(jī)制的無(wú)線傳感網(wǎng)路徑生成算法。通過(guò)對(duì)網(wǎng)絡(luò)區(qū)域進(jìn)行柵格－角度分割，設(shè)計(jì)了一種新的路徑爬取激勵(lì)方法。可優(yōu)化節(jié)點(diǎn)爬取路徑的健壯性能，均衡節(jié)點(diǎn)能量消耗及傳輸跳數(shù)，顯著提高爬蟲(chóng)運(yùn)動(dòng)速度及路徑生成效率。隨后，通過(guò)評(píng)估節(jié)點(diǎn)能耗，設(shè)計(jì)了基于偽隨機(jī)因子修正機(jī)制的節(jié)點(diǎn)轉(zhuǎn)移概率更新方法，主要采取均衡路徑能耗的方式，優(yōu)選能量剩余較高且被爬取頻次較高節(jié)點(diǎn)，進(jìn)一步降低節(jié)點(diǎn)抖動(dòng)頻次，提升網(wǎng)絡(luò)傳輸能力。

下一步，將針對(duì)本文算法在移動(dòng)環(huán)境中性能較差的弱點(diǎn)，擬引入移動(dòng)拓?fù)洌l次自適應(yīng)控制機(jī)制，提升爬蟲(chóng)對(duì)高拓?fù)涓h(huán)境的適應(yīng)能力，提升本文算法在節(jié)點(diǎn)移動(dòng)場(chǎng)合下的部署效果。