陳友榮,陸思一,劉半藤,楊海波,許 森,祝云凱,盧允偉

(1.浙江樹人大學信息科技學院,杭州 310015;2.常州大學信息科學與工程學院,江蘇 常州 213164;3.浙江杭佳科技發(fā)展有限公司,杭州 310015;4.浙江建設(shè)職業(yè)技術(shù)學院,杭州 311231)

近幾年,我國地震、危險品爆炸等重大自然或事故災(zāi)害頻發(fā),造成大量的建筑物倒塌和人員傷亡[1-2]。當交通受阻、人力不足、救援現(xiàn)場環(huán)境惡劣(如余震不斷、存在有毒氣體)等原因造成救援人員無法第一時間攜帶救援設(shè)備抵達受災(zāi)區(qū)域時,救援設(shè)備就無法發(fā)揮作用,因此迫切需要一種技術(shù)手段——無線傳感網(wǎng)技術(shù)[3],實現(xiàn)自主搜尋受災(zāi)人員。目前傳統(tǒng)靜態(tài)無線傳感網(wǎng)適用于火山地震、森林火災(zāi)、土壤環(huán)境等對象的實時長期監(jiān)測。由于重大災(zāi)難的受災(zāi)區(qū)域面積大、大規(guī)模部署時系統(tǒng)成本高等原因,因此靜態(tài)傳感網(wǎng)不適用于短期使用的重大災(zāi)難現(xiàn)場緊急救援,需要考慮移動無線傳感網(wǎng)MWSNs(Mobile Wireless Sensor Networks)[4-5]。移動無線傳感網(wǎng)中部分或全部節(jié)點除了具有傳統(tǒng)靜態(tài)節(jié)點的傳感、計算和通信能力外,還具有一定的機動能力。但是由于建筑物倒塌后,廢墟處存在大量垃圾和被破壞物,很難實現(xiàn)地面小車的移動和自主搜索,因此考慮設(shè)備的飛行,但是需要增加成本較高的移動設(shè)備,較大提高了移動傳感節(jié)點的硬件成本。為降低系統(tǒng)成本,可利用少量節(jié)點移動覆蓋和分時感知整個監(jiān)測區(qū)域,從而實現(xiàn)監(jiān)測區(qū)域的全覆蓋。

為實現(xiàn)稀疏網(wǎng)絡(luò)環(huán)境下移動傳感節(jié)點的飛行全覆蓋監(jiān)測區(qū)域,需要考慮移動傳感節(jié)點的飛行路徑選擇問題,在保證區(qū)域覆蓋率的前提下,提高移動傳感節(jié)點的數(shù)據(jù)傳輸率,降低到匯聚節(jié)點的數(shù)據(jù)傳輸時延。因此,一些學者研究移動傳感節(jié)點的移動路徑選擇算法,并取得一定的成果。如文獻[6]針對高超聲速飛行器,考慮有限轉(zhuǎn)彎半徑約束和最短飛行路徑約束,提出一種基于Dubins曲線的高超聲速飛行器路徑規(guī)劃算法。文獻[7]在三維空間上尋找路徑,在該路徑上分解關(guān)鍵位置,并在A*算法的基礎(chǔ)上提出三維路徑規(guī)劃算法。文獻[8]利用無人機跟蹤冰山的位置和移動方向,建立了飛行器移動輪數(shù)最大和移動路程最小的優(yōu)化模型,并采用CPLEX 求解器獲得最優(yōu)方案。文獻[9]考慮障礙物的3D結(jié)構(gòu),根據(jù)高度分成多個層,并在每一個層上確定可停留位置。提出近似3D歐幾里德最短路徑算法尋找到目的地址的最短路徑。文獻[10]提出路徑長度、高度方差和路徑光滑度的評價函數(shù),建立最小優(yōu)化模型,并采用改進的中心力優(yōu)化算法求解優(yōu)化模型,獲得最優(yōu)解。文獻[6-10]主要尋找飛行器從源位置到目標位置的路徑,但是需要獲知整個監(jiān)測區(qū)域內(nèi)包括障礙物的所有物體的結(jié)構(gòu)和位置分布,且沒有考慮如何高效的全覆蓋整個監(jiān)測區(qū)域。文獻[11]將監(jiān)測區(qū)域分成多個移動監(jiān)測的普通六邊形網(wǎng)格和實時監(jiān)測的關(guān)鍵六邊形網(wǎng)格,提出了移動傳感節(jié)點的移動策略TCM(Temporal Coverage Mechanism for distinct quality)避開關(guān)鍵節(jié)點的網(wǎng)格。文獻[12]將監(jiān)測區(qū)域分成多個三角形,將三角形的內(nèi)圓圓心位置作為移動傳感節(jié)點的停留位置。采用貪婪算法確定下一個時刻位置。如果兩個位置間存在障礙物,則考慮障礙物的四個角,采用Dijkstra最短路徑算法確定兩個位置間移動路徑,但是障礙物存在不規(guī)則性,其四個角位置坐標很難在實際中獲取。同時,文獻[11-12]只是考慮一個移動傳感節(jié)點的移動覆蓋問題,沒有考慮數(shù)據(jù)的傳輸問題和多個移動傳感節(jié)點的協(xié)作感知問題。

綜上所述,較多飛行器或移動傳感節(jié)點的移動路徑選擇算法沒有考慮多個節(jié)點協(xié)同感知問題和數(shù)據(jù)傳輸問題,且每個設(shè)備需要獲知監(jiān)測區(qū)域內(nèi)的障礙物等物體的位置和形狀,這在實際應(yīng)用中較難實現(xiàn)且需要增加較大的成本。因此,上述文獻的基礎(chǔ)上,提出一種移動無線傳感網(wǎng)的移動感知路徑選擇算法MSPS(Mobile Sensing Path Selection algorithm for mobile wireless sensor networks)。MSPS算法考慮將監(jiān)測區(qū)域劃分成多個大小相同的六邊形網(wǎng)格,每一個移動傳感節(jié)點在初始位置移動到下一個鄰居網(wǎng)格中心感知數(shù)據(jù),提出多目標函數(shù),建立保證區(qū)域覆蓋率100%下的移動路徑選擇優(yōu)化模型。提出修正多種群遺傳算法求解該優(yōu)化模型,獲得移動傳感節(jié)點的最優(yōu)移動路徑,移動傳感節(jié)點沿著該路徑移動,從而在保證區(qū)域全覆蓋的前提下提高數(shù)據(jù)傳輸率,降低數(shù)據(jù)傳輸時延和丟棄數(shù)據(jù)的總量。

1 算法假設(shè)和基本原理

在MSPS算法中,假設(shè):①在2維無線傳感網(wǎng)中,存在多個移動傳感節(jié)點和一個靜態(tài)的匯聚節(jié)點。移動傳感節(jié)點可移動到監(jiān)測區(qū)域的任一網(wǎng)格中心。②移動傳感節(jié)點具有相同的感知覆蓋半徑、通信半徑和初始能量,且可獲知自身的位置坐標。③移動傳感節(jié)點的初始能量有限。④移動傳感節(jié)點移動到監(jiān)測區(qū)域內(nèi)未被其他移動傳感節(jié)點感知過的網(wǎng)格內(nèi)采集數(shù)據(jù)。如果存在到匯聚節(jié)點的路徑,則并將數(shù)據(jù)發(fā)送給匯聚節(jié)點。

如圖1所示,將監(jiān)測區(qū)域分成若干個大小一致的六邊形網(wǎng)格[10],并根據(jù)從左到右,從上到下的原則對每一個六邊形網(wǎng)格進行編碼。如grid(v,w)表示從左開始計數(shù)的第v列中從下到上開始計數(shù)的第w個六邊形網(wǎng)格。移動傳感節(jié)點隨機分布在監(jiān)測區(qū)域內(nèi)且可獲知自身的位置。當網(wǎng)絡(luò)運行后,移動傳感節(jié)點向不存在障礙物且未經(jīng)過的鄰居網(wǎng)格中心位置移動,感知該網(wǎng)格區(qū)域內(nèi)的數(shù)據(jù)。如果移動傳感節(jié)點可尋找到匯聚節(jié)點的路徑時,將數(shù)據(jù)通過多跳的方式發(fā)送給匯聚節(jié)點,否則和相遇的傳感節(jié)點通信,計算轉(zhuǎn)發(fā)概率,將自身傳感的數(shù)據(jù)發(fā)送給轉(zhuǎn)發(fā)概率高的傳感節(jié)點。但是MSPS算法仍需要解決以下二個問題:一是如何考慮存在障礙物和移動傳感節(jié)點的移動感知,用數(shù)學公式建立保證區(qū)域全覆蓋且權(quán)衡數(shù)據(jù)傳輸率、數(shù)據(jù)傳輸時延和節(jié)點平均能耗的優(yōu)化模型。二是如何采用修正的多種群遺傳算法求解優(yōu)化模型,獲得最優(yōu)方案。這二個問題的具體解決如下。

圖1 MSPS算法原理

2 優(yōu)化模型的建立

令Pi表示移動傳感節(jié)點i的飛行路徑,是多個網(wǎng)格中心位置的集合,即Pi={pi,1,pi,2,…,pi,Ni},其中pi,j表示移動傳感節(jié)點i的第j個停留位置,Ni表示移動傳感節(jié)點i的飛行路徑中停留位置個數(shù)。由于移動傳感節(jié)點要從一個網(wǎng)格中心移動到其鄰居網(wǎng)格中心,因此集合Pi中除初始位置的其他所有位置需是上一時刻位置的鄰居網(wǎng)格中心,可表示為

pi,j+1∈Hv,w,j=1,2,…,Ni-1

(1)

當v=1且w=1時,

當v=1且w=n時,

當v=1且1

當v=m,w=1且m是奇數(shù)時,

當v=m,w=n且m是奇數(shù)時,

當v=m,1

當v=m,w=1且m是偶數(shù)時,

當v=m,w=n+1且m是偶數(shù)時,

當v=m,1

當w=1,1

當w=n+1,1

當w=n,1

當其他情況中1

當其他情況中1

(2)

同時,為提高移動傳感節(jié)點的區(qū)域覆蓋率,要求每一個傳感節(jié)點不走重復(fù)的網(wǎng)格中心,即每一個傳感節(jié)點的移動路徑中所有停留位置不相同,則可表示為

pi,j≠pi,k,?j,k且j≠k

(3)

如果網(wǎng)格grid(v,w)被移動傳感節(jié)點覆蓋,即其網(wǎng)格中心位置在該移動傳感節(jié)點的路徑中,則

(4)

(5)

區(qū)域覆蓋率可表示為

C=NC/NG

(6)

式中:NG表示監(jiān)測區(qū)域內(nèi)不存在障礙物的網(wǎng)格總數(shù)量。

如果移動傳感節(jié)點在匯聚節(jié)點的1跳范圍內(nèi),則直接將數(shù)據(jù)發(fā)送給匯聚節(jié)點,否則采用機會路由方法,計算自身的傳輸概率。低傳輸概率的移動傳感節(jié)點將數(shù)據(jù)轉(zhuǎn)發(fā)給高傳輸概率的移動傳感節(jié)點。具體轉(zhuǎn)發(fā)概率的計算方法如下:如果移動傳感節(jié)點在匯聚節(jié)點的1跳范圍內(nèi),則傳輸概率為100%,否則根據(jù)存在的兩種情況,計算自身的傳輸概率。一種是當兩個傳感節(jié)點都未獲知匯聚節(jié)點的位置坐標時,直接根據(jù)存儲空間的狀態(tài)和隨機值計算傳輸概率。

Pit=e-1-2Di/Dt

(7)

式中:Pit表示移動傳感節(jié)點i在t時將消息成功傳輸給匯聚節(jié)點的概率,Di表示傳感節(jié)點i的空閑存儲空間,Dt表示傳感節(jié)點的總存儲空間。另一種是通過數(shù)據(jù)通信,獲知匯聚節(jié)點的位置坐標,根據(jù)到匯聚節(jié)點的距離和移動方向計算傳輸概率值為

(8)

式中:(xit,yit)表示時刻t時移動傳感節(jié)點i的位置坐標,(xs,ys)表示匯聚節(jié)點的位置坐標,dmax表示匯聚節(jié)點到監(jiān)測區(qū)域邊界的距離,s5表示移動方向指示符號,s5=0表示傳感節(jié)點移動靠近匯聚節(jié)點,否則s5=1,表示傳感節(jié)點移動遠離匯聚節(jié)點,即

(9)

式中:θ表示傳感節(jié)點移動方向與傳感節(jié)點到匯聚節(jié)點的有向線段的夾角。

根據(jù)上述的機會路由方法,移動傳感節(jié)點感知監(jiān)測區(qū)域,產(chǎn)生數(shù)據(jù)包,并通過機會路由傳輸給匯聚節(jié)點,此時會造成較大的數(shù)據(jù)傳輸時延。因此當前時刻數(shù)據(jù)傳輸時延估計值可定義為

(10)

由于在實際系統(tǒng)中,路由信息包、路由發(fā)送包等信息包的傳輸能耗和數(shù)據(jù)計算能耗等能耗較小,因此移動傳感節(jié)點的能耗主要由感知數(shù)據(jù)的無線通信能耗和節(jié)點移動能耗兩部分組成,即移動傳感節(jié)點的能耗定義為

(11)

式中:Fij表示移動傳感節(jié)點i發(fā)送給移動傳感節(jié)點j的數(shù)據(jù)量,Eelec表示無線收發(fā)單位比特數(shù)據(jù)時電路的電子能耗,εfs表示放大單位比特信號時信號放大器的電子能耗,dij表示移動傳感節(jié)點i和移動傳感節(jié)點j之間的距離,Ji表示移動傳感節(jié)點i的接收數(shù)據(jù)總量,εmove表示移動傳感節(jié)點的移動能耗因子,di表示移動傳感節(jié)點i的移動總距離。則平均節(jié)點能耗Eaverage定義為

(12)

式中:Ns表示移動傳感節(jié)點個數(shù)。

由上所述,網(wǎng)絡(luò)啟動后,所有移動傳感節(jié)點自主飛行,探測監(jiān)測區(qū)域,相互協(xié)作傳輸數(shù)據(jù)。在數(shù)據(jù)傳輸過程中,數(shù)據(jù)包存在以下三種狀態(tài),一是成功傳輸?shù)絽R聚節(jié)點,二是仍存在節(jié)點的存儲空間中,三是由于存儲空間滿了,被節(jié)點丟棄。因此移動傳感網(wǎng)的移動感知路徑選擇問題是在滿足監(jiān)測區(qū)域全覆蓋下盡可能提高數(shù)據(jù)傳輸率,降低數(shù)據(jù)傳輸時延和平均節(jié)點能耗,即可轉(zhuǎn)換成以下優(yōu)化模型。

min(x1Daverage/Dyu+x2/Trate+x3Eaverage/Eyu)

(13)

s.t.C=100%

(13.1)

式(1)～式(6),式(10)～式(12)

式中:Dyu表示數(shù)據(jù)傳輸時延閾值,Eyu表示平均節(jié)點能耗閾值,x1表示數(shù)據(jù)傳輸時延權(quán)重因子,x2表示數(shù)據(jù)傳輸率權(quán)重因子,x3表示平均節(jié)點能耗權(quán)重因子,且x1+x2+x3=1。

3 算法求解

由于單種群的遺傳算法存在易受適應(yīng)度超常個體和群體規(guī)模影響、交叉概率和變異概率選擇不恰當?shù)葐栴}[13],很容易出現(xiàn)早熟收斂,因此采用修正的多種群遺傳算法求解優(yōu)化模型(13),即在多種群遺傳算法基本原理的基礎(chǔ)上,提出了到目標網(wǎng)格的路徑尋找方法、初始染色體的確定方法和染色體適應(yīng)度值計算方法,并對每一輪交叉和變異后的染色體進行修正,使其符合優(yōu)化模型的約束條件。具體求解方法如下。

3.1 到目標網(wǎng)格的路徑尋找

3.2 初始染色體的確定

種群中初始染色體表示所有移動傳感節(jié)點全覆蓋監(jiān)測區(qū)域的一種移動方案。在算法初始化階段,需要初始化染色體,即在實際路徑尋找過程,先隨機尋找未經(jīng)過的網(wǎng)格,但是會出現(xiàn)“進入死胡同”情況,即周圍網(wǎng)格都已經(jīng)訪問過,此時需要進入重復(fù)區(qū)域。初始染色體確定的具體實現(xiàn)步驟如下:

步驟1 初始化所有移動傳感節(jié)點的初始停留網(wǎng)格,移動傳感節(jié)點的當前網(wǎng)格和移動路徑均為初始停留網(wǎng)格,k=1;

步驟2 選擇移動傳感節(jié)點k的當前網(wǎng)格,判斷當前網(wǎng)格的鄰居網(wǎng)格集合。如果該集合中存在未被移動傳感節(jié)點停留過且不存在障礙物的網(wǎng)格,則隨機選擇集合中一個網(wǎng)格作為下一個時刻的停留網(wǎng)格,并將該網(wǎng)格添加到移動傳感節(jié)點k的移動路徑中,跳到步驟4,否則跳到步驟3;

步驟3 選擇離當前網(wǎng)格距離最短的網(wǎng)格,尋找一條從當前網(wǎng)格到該網(wǎng)格的移動路徑,并將該路徑添加到移動傳感節(jié)點k的移動路徑中,跳到步驟4;

步驟4k=k+1。如果k≤Ns,則跳到步驟2,否則根據(jù)所有移動傳感節(jié)點的移動路徑和式(4)～式(6)計算區(qū)域覆蓋率C。如果C為100%,則所有移動傳感節(jié)點的移動路徑達到全覆蓋監(jiān)測區(qū)域的要求,結(jié)束返回所有移動傳感節(jié)點的移動路徑,否則k=1,跳到步驟2。

3.3 染色體適應(yīng)度值計算

步驟1 初始化所有移動傳感節(jié)點的初始能量、存儲空間等參數(shù),且t=1,k=1;

步驟2 根據(jù)各個移動傳感節(jié)點位置和通信半徑,設(shè)置移動傳感節(jié)點與其通信范圍內(nèi)的鄰居傳感節(jié)點的鏈路權(quán)值為1,采用最短路徑樹算法構(gòu)建以匯聚節(jié)點為根的最短路徑樹。

步驟3 如果移動傳感節(jié)點在匯聚節(jié)點的最短路徑樹內(nèi),則可通過匯聚節(jié)點的廣播自身位置信息和移動傳感節(jié)點的轉(zhuǎn)發(fā)獲知匯聚節(jié)點的位置坐標,否則移動傳感節(jié)點未知匯聚節(jié)點的位置坐標。

步驟4 所有移動傳感節(jié)點感知和存儲數(shù)據(jù),記錄該數(shù)據(jù)且當前存儲空間大小加1,如果存儲空間大于最大存儲空間,則刪除時間最早的一個數(shù)據(jù)。

步驟5t=t+1,移動傳感節(jié)點移動到下一個時刻位置。如果移動傳感節(jié)點已知匯聚節(jié)點的位置坐標,則根據(jù)自身的移動方向、存儲空間大小等信息,通過式(8)計算自身的數(shù)據(jù)轉(zhuǎn)發(fā)概率,否則根據(jù)自身的存儲空間大小,通過式(7)計算自身的數(shù)據(jù)轉(zhuǎn)發(fā)概率;

步驟6 如果移動傳感節(jié)點k在匯聚節(jié)點的1跳范圍內(nèi),則直接將存儲空間中所有數(shù)據(jù)發(fā)送給匯聚節(jié)點,否則判斷是否具有鄰居移動傳感節(jié)點。如果不存在鄰居移動傳感節(jié)點,跳到步驟7,否則比較自身數(shù)據(jù)轉(zhuǎn)發(fā)概率和鄰居移動傳感節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)概率。如果移動傳感節(jié)點k的鄰居移動傳感節(jié)點具有更高的數(shù)據(jù)轉(zhuǎn)發(fā)概率,則將數(shù)據(jù)發(fā)送給最高數(shù)據(jù)轉(zhuǎn)發(fā)概率的鄰居移動傳感節(jié)點,自身存儲空間中刪除該數(shù)據(jù),否則接收鄰居移動傳感節(jié)點的數(shù)據(jù)。如果存儲空間大于最大存儲空間,則刪除時間最早的一個數(shù)據(jù),存儲接收到數(shù)據(jù)。

步驟7k=k+1。如果k≤Ms,跳到步驟6,否則如果t≤Ts,跳到步驟4,否則根據(jù)匯聚節(jié)點接收到數(shù)據(jù)的信息,計算數(shù)據(jù)傳輸時延Daverage,數(shù)據(jù)傳輸率Trate和節(jié)點平均能耗Eaverage,通過式(14)計算染色體的適應(yīng)度值。

fitness=x1Daverage/Dyu+x2/Trate+x3Eaverage/Eyu

(14)

3.4 多種群遺傳算法實現(xiàn)

根據(jù)上述的計算步驟,如圖2所示,求解模型(13)的具體實現(xiàn)步驟如下:

步驟2 計算每一個種群中每一個染色體的適應(yīng)度值。在每一個種群中根據(jù)染色體的適應(yīng)度值排序,選出每一個種群的適應(yīng)度值最大的染色體和所有種群的全局最優(yōu)染色體;

步驟3 將不具有最優(yōu)染色體的所有種群的最差染色體替換為全局最優(yōu)染色體。

步驟6 分析種群i的每一個染色體。如果染色體存在相同的元素,則刪除重復(fù)元素。采用最近鄰算法[14]尋找遍歷所有剩余元素的最短路徑。如果染色體沒有全覆蓋監(jiān)測區(qū)域,則尋找未覆蓋且不存在障礙物的網(wǎng)格元素,將其加入到使移動傳感節(jié)點移動路程增幅最小的路徑中,獲得全覆蓋監(jiān)測區(qū)域的染色體,使其符合約束條件(13.1)。如果染色體的移動路徑中下一個元素不是前一個元素的鄰居網(wǎng)格,則采用到目標網(wǎng)格的路徑尋找方法,尋找兩者間的移動路徑,添加到該移動路徑中,更新染色體。如果染色體中存在具有障礙物的網(wǎng)格,則刪除該網(wǎng)格,添加可繞過該網(wǎng)格的鄰居網(wǎng)格,更新染色體。

步驟7i=i+1。如果i≤MZ,跳到步驟4,否則rn=rn+1,i=1。如果rn≤Repeat,跳到步驟2,否則結(jié)束算法,輸出全局最優(yōu)染色體。

4 算法仿真

4.1 仿真參數(shù)選擇

在算法仿真中,將監(jiān)測區(qū)域分成多個網(wǎng)格,移動傳感節(jié)點在網(wǎng)格中心間移動。如果移動傳感節(jié)點移動到未被其他移動傳感節(jié)點覆蓋過的網(wǎng)格,則感知數(shù)據(jù)到存儲空間中,否則不感知數(shù)據(jù)。如表1所示,選擇表1中參數(shù)進行仿真實驗,獲得數(shù)據(jù)傳輸率,數(shù)據(jù)傳輸時延,節(jié)點丟棄的總數(shù)據(jù)量和平均節(jié)點能耗等性能參數(shù)值。其中數(shù)據(jù)傳輸時延和平均節(jié)點能耗分別根據(jù)式(10)和式(12)計算,數(shù)據(jù)傳輸率定義為從網(wǎng)絡(luò)啟動到全覆蓋整個監(jiān)測區(qū)域時,移動傳感節(jié)點成功傳輸?shù)絽R聚節(jié)點的數(shù)據(jù)包數(shù)量與總數(shù)據(jù)包數(shù)量的比值。節(jié)點丟棄的總數(shù)據(jù)量定義為移動傳感節(jié)點因存儲空間有限丟棄數(shù)據(jù)的總量。

表1 仿真參數(shù)表

4.2 仿真結(jié)果分析

首先分析MSPS算法的收斂性。假設(shè)監(jiān)測區(qū)域內(nèi)不存在障礙物,選擇移動傳感節(jié)點個數(shù)6和表1中參數(shù),循環(huán)80次計算MSPS算法中每一輪多個種群的全局最優(yōu)適應(yīng)度值,獲得收斂圖3。如圖3所示,前期經(jīng)過多次迭代,每輪最優(yōu)適應(yīng)度值不斷下降。當?shù)?1次迭代以后,每輪最優(yōu)適應(yīng)度值收斂到0.449。因此MSPS算法可尋找到優(yōu)化模型(13)的最優(yōu)解。

圖3 MSPS算法的收斂圖

其次,考慮監(jiān)測區(qū)域內(nèi)是否存在障礙物兩種情況,選擇移動傳感節(jié)點個數(shù)2,3,4,5,6,7,選擇MSPS算法中5個種群的交叉因子為(0.5 0.5 0.4 0.4 0.4),染色體變異因子為(0.1 0.15 0.2 0.25 0.3),基因變異因子為(0.4 0.35 0.3 0.25 0.2)和表1中參數(shù),循環(huán)計算MSPS、RAND、RAND_D、TCM_M和SGA的數(shù)據(jù)傳輸率,數(shù)據(jù)傳輸時延,節(jié)點丟棄的總數(shù)據(jù)量和平均節(jié)點能耗。其中在RAND中,移動傳感節(jié)點隨機選擇和感知未覆蓋的網(wǎng)格。在RAND_D中,移動傳感節(jié)點在距離最近的網(wǎng)格集合中隨機選擇一個網(wǎng)格,作為下一時刻的感知位置。在TCM_M中,根據(jù)移動傳感節(jié)點個數(shù),將文獻[11]所獲得的移動路徑平均劃分成多個子路徑,分別分配給不同的移動傳感節(jié)點。RAND、RAND_D和TCM_M中,雖然移動傳感節(jié)點選擇下一時刻感知網(wǎng)格的方法不一致,但是采用相同的到目標網(wǎng)格的路徑尋找方法(3.1節(jié))和相同的機會路由算法。在SGA中,采用單種群遺傳算法求解模型(13),其他方法和MSPS相同。具體仿真結(jié)果內(nèi)容如下。

圖4 無障礙物下的數(shù)據(jù)傳輸率比較圖

4.2.1 無障礙物的仿真結(jié)果分析

如圖4所示,考慮監(jiān)測區(qū)域內(nèi)不存在障礙物,在RAND_D算法中移動傳感節(jié)點在初始位置隨機選擇距離最近的未覆蓋網(wǎng)格移動,TCM_M算法將一條遍歷經(jīng)過所有網(wǎng)格的路徑平均分成多個子路徑。這兩個算法在路徑選擇時沒有考慮移動傳感節(jié)點與其他傳感節(jié)點的路由通信問題,因此他們的數(shù)據(jù)傳輸率比較差。RAND算法隨機選擇監(jiān)測區(qū)域內(nèi)未覆蓋的網(wǎng)格,其部分停留網(wǎng)格在匯聚節(jié)點的附近。SGA算法采用單種群遺傳算法求解,可獲得局部最優(yōu)解。因此RAND算法和SGA算法的數(shù)據(jù)傳輸率高于RAND_D和TCM_M算法。MSPS算法采用多種群遺傳算法,每一個種群采用不同的交叉因子和變異因子,各自尋找種群的最優(yōu)解,并讓全局最優(yōu)染色體替換種群中最差的染色體,經(jīng)過多次迭代MSPS算法能尋找每一個移動傳感節(jié)點的最優(yōu)移動路徑。移動傳感節(jié)點沿著該路徑移動,可通過節(jié)點間數(shù)據(jù)通信將感知數(shù)據(jù)成功傳輸給匯聚節(jié)點。因此MSPS算法的數(shù)據(jù)傳輸率最高。當移動傳感節(jié)點的個數(shù)較少時,節(jié)點間相互通信的幾率較低。當移動節(jié)點的個數(shù)增加時,節(jié)點間相互通信幾率和與匯聚節(jié)點的通信幾率都增加,數(shù)據(jù)傳輸率增加。因此MSPS算法的數(shù)據(jù)傳輸率隨著節(jié)點個數(shù)的增加而提高,且當節(jié)點個數(shù)為7時,數(shù)據(jù)傳輸率可高達97%。

由于RAND算法隨機選擇下一時刻的感知網(wǎng)格,移動路徑較長,其數(shù)據(jù)傳輸時延是MSPS算法的5倍以上,如果同時顯示在仿真圖上會導(dǎo)致其他算法的數(shù)據(jù)傳輸時延曲線集中在一起,很難區(qū)別。因此圖5只顯示MSPS、SGA、TCM_M和RAND_D算法的仿真結(jié)果。如圖5所示,MSPS算法的適應(yīng)度函數(shù)包括占較大比重的數(shù)據(jù)傳輸時延,讓每一個迭代中具有較低數(shù)據(jù)傳輸時延的節(jié)點路徑方案的適應(yīng)度值較低,更容易被選擇成為下一代染色體。而SGA算法只是尋找到局部最優(yōu)方案。TCM_M算法中每一個節(jié)點的移動路徑較短,部分節(jié)點直接將數(shù)據(jù)1跳發(fā)送給匯聚節(jié)點。RAND_D隨機移動,沒有考慮數(shù)據(jù)傳輸時延,因此MSPS算法的數(shù)據(jù)傳輸時延低于SGA、TCM_M、RAND_D和RAND算法。

圖5 無障礙物下的數(shù)據(jù)傳輸時延比較圖

圖6 無障礙物下丟棄的總數(shù)據(jù)量比較圖

如圖6所示,MSPS算法尋找到能提高數(shù)據(jù)傳輸率和降低數(shù)據(jù)傳輸時延的移動傳感節(jié)點的移動路徑方案,讓每一個傳感節(jié)點的感知數(shù)據(jù)盡可能快的傳輸給匯聚節(jié)點。SGA算法只尋找到某個局部最優(yōu)解,TCM_M算法考慮盡可能短的完成全覆蓋監(jiān)測區(qū)域,節(jié)點間通信較少,RAND和RAND_D具有隨機選擇路徑,容易出現(xiàn)孤立節(jié)點,因此MSPS算法丟棄的總數(shù)據(jù)量最少。當節(jié)點個數(shù)較少時,移動傳感節(jié)點需要覆蓋所有的網(wǎng)格,其感知數(shù)據(jù)較多,且相互間通信的幾率較低,會導(dǎo)致較多數(shù)據(jù)丟失。因此當節(jié)點個數(shù)較少時,這些算法丟棄的總數(shù)據(jù)量較多。

由于RAND算法移動路徑長,其移動能耗非常大,是MSPS算法的幾十倍,如果同時顯示在仿真圖上會導(dǎo)致其他算法的數(shù)據(jù)傳輸時延曲線集中在一起,很難區(qū)別。因此圖7只顯示MSPS、SGA、TCM_M和RAND_D算法的仿真結(jié)果。如圖7所示,TCM_M算法由于較快完成了全覆蓋監(jiān)測區(qū)域,數(shù)據(jù)傳輸率較低,傳感節(jié)點的移動路徑較短,因此其移動能耗和通信能耗都較低。RAND_D丟棄的總數(shù)據(jù)量高,其完成的數(shù)據(jù)傳輸量較少,通信能耗較少。MSPS和SGA算法為了實現(xiàn)較高的數(shù)據(jù)傳輸率和較低的數(shù)據(jù)傳輸時延,一定程度上增加了傳感節(jié)點的移動路程,提高了節(jié)點間數(shù)據(jù)轉(zhuǎn)發(fā)的次數(shù),因此其平均節(jié)點能耗較高,但是與其他算法相比,這兩種算法增加的平均節(jié)點能耗不多。

圖7 無障礙物下的平均節(jié)點能耗比較圖

圖8 監(jiān)測區(qū)域的障礙物分布圖

總之,當監(jiān)測區(qū)域內(nèi)不存在障礙物時,MSPS算法能尋找到移動傳感節(jié)點的最優(yōu)移動方案,提高了數(shù)據(jù)傳輸率,降低了數(shù)據(jù)傳輸時延和節(jié)點丟棄的總數(shù)據(jù)量,且其增加的平均節(jié)點能耗不多。

4.2.2 有障礙物的仿真結(jié)果分析

如圖8所示,在仿真中將監(jiān)測區(qū)域分成多個網(wǎng)格。假設(shè)第二列從下到上的第6個～第7個網(wǎng)格,第三列的第5個～第6個網(wǎng)格,第七列的第3個～第4個網(wǎng)格和第八列的第3個～第4個網(wǎng)格上存在障礙物。移動傳感節(jié)點不需要移動到這些網(wǎng)格中心感知數(shù)據(jù)。根據(jù)圖8的障礙物分布,比較MSPS、SGA、TCM_M、RAND_D和RAND算法的仿真結(jié)果。

如圖9所示,有障礙物下MSPS算法不受監(jiān)測區(qū)域存在障礙物的影響,其數(shù)據(jù)傳輸率與無障礙物下的數(shù)據(jù)傳輸率相差不大,且高于SGA、TCM_M、RAND_D和RAND算法。這是因為MSPS算法排除了存在障礙物的網(wǎng)格,采用多種群修正算法尋找到移動傳感節(jié)點最優(yōu)路徑方案,提高了移動傳感節(jié)點轉(zhuǎn)發(fā)其他傳感節(jié)點數(shù)據(jù)到匯聚節(jié)點的概率,較好利用機會路由方法,而其他算法都存在節(jié)4.2.1中說明的局限性,因此MSPS算法的數(shù)據(jù)傳輸率最高。

圖9 有障礙物下的數(shù)據(jù)傳輸率比較圖

圖10 有障礙物下的數(shù)據(jù)傳輸時延比較圖

如圖10所示,有障礙物下MSPS算法規(guī)劃了能避開存在障礙物網(wǎng)格的最優(yōu)路徑,充分利用機會路由方法較快實現(xiàn)移動傳感節(jié)點數(shù)據(jù)的上報,其數(shù)據(jù)傳輸時延最低。SGA和TCM_M算法尋找到移動傳感節(jié)點的較優(yōu)路徑,較好完成監(jiān)測區(qū)域的感知覆蓋,其數(shù)據(jù)傳輸時延低于RAND和RAND_D算法。同時,當監(jiān)測區(qū)域內(nèi)存在障礙物時,移動傳感節(jié)點的移動路徑會繞過存在障礙物的網(wǎng)格,降低了所有算法的移動路程和平均節(jié)點能耗,但是有障礙物下MSPS算法平均節(jié)點能耗和丟棄總數(shù)據(jù)量的仿真結(jié)果和具體原因與無障礙物下的場景基本一致,本文不再重復(fù)說明,可參考4.2.1節(jié)。

5 總結(jié)

本文提出了一種移動無線傳感網(wǎng)的移動感知路徑選擇算法(MSPS)。首先,提出算法假設(shè)和基本原理。其次,用數(shù)學公式分析了鄰居網(wǎng)格集合、區(qū)域覆蓋率、數(shù)據(jù)傳輸時延、節(jié)點平均能耗等參數(shù)。根據(jù)節(jié)點的機會路由方法,建立了能保證全覆蓋監(jiān)測區(qū)域且權(quán)衡數(shù)據(jù)傳輸時延、數(shù)據(jù)傳輸率和節(jié)點平均能耗的移動路徑選擇優(yōu)化模型。接著,提出了修正的多種群遺傳算法求解優(yōu)化模型,包括到目標網(wǎng)格的路徑尋找方法、初始染色體的確定方法、染色體適應(yīng)度值計算方法和多種群遺傳算法的實現(xiàn)方法。最后給出算法的仿真參數(shù),仿真比較MSPS、SGA、TCM_M、RAND_D和RAND算法的性能。

總之,不管監(jiān)測區(qū)域內(nèi)是否存在障礙物,相比SGA、TCM_M、RAND_D和RAND算法,MSPS算法能尋找到移動傳感節(jié)點的最優(yōu)移動方案,提高了數(shù)據(jù)傳輸率,降低了數(shù)據(jù)傳輸時延和節(jié)點丟棄的總數(shù)據(jù)量。但是MSPS算法采用多種群遺傳算法求解優(yōu)化模型,其算法的時間復(fù)雜度相對較高,需要將移動路徑最優(yōu)方案發(fā)送給移動傳感節(jié)點,因此下一個階段目標是研究節(jié)點路徑選擇的分布式方法,即移動傳感節(jié)點通過相互通信和自身的信息,判斷下一時刻的感知網(wǎng)格,從而提高區(qū)域覆蓋率和數(shù)據(jù)傳輸率,降低數(shù)據(jù)傳輸時延。