趙克華,陳友榮*,萬(wàn)錦昊,任條娟,王章權(quán),周駿華

(1.浙江樹人大學(xué)信息科技學(xué)院,杭州 310015;2.中移(杭州)信息技術(shù)有限公司,杭州 311100)

無(wú)線傳感網(wǎng)(Wireless Sensor Networks,WSNs)中所有傳感節(jié)點(diǎn)可協(xié)同完成信息采集任務(wù),但是目前在危險(xiǎn)環(huán)境(如火山、放射區(qū)、有毒化工區(qū)等)監(jiān)測(cè)、災(zāi)難搜救、軍事領(lǐng)域、水下監(jiān)測(cè)等應(yīng)用領(lǐng)域中,通常采用傳感節(jié)點(diǎn)周期性上報(bào)數(shù)據(jù)且節(jié)點(diǎn)位置固定不變的靜態(tài)無(wú)線傳感網(wǎng)。但是該靜態(tài)無(wú)線傳感網(wǎng)一般隨機(jī)部署傳感節(jié)點(diǎn),很容易造成節(jié)點(diǎn)分布和能耗的不均勻,很容易形成監(jiān)測(cè)區(qū)域的能量空穴問(wèn)題,縮短了網(wǎng)絡(luò)生存時(shí)間[1-2]。因此考慮Sink節(jié)點(diǎn)的移動(dòng),解決靜態(tài)無(wú)線傳感網(wǎng)的能量空穴問(wèn)題,從而達(dá)到平衡節(jié)點(diǎn)能耗、延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間和降低數(shù)據(jù)丟包率的目的。

目前,很多學(xué)者側(cè)重于研究二維無(wú)線傳感網(wǎng)下的Sink移動(dòng)路徑、數(shù)據(jù)收集等問(wèn)題。如文獻(xiàn)[3]建立Sink節(jié)點(diǎn)停留在若干位置上的網(wǎng)絡(luò)生存時(shí)間優(yōu)化模型,并求解該模型獲得最優(yōu)方案,但是沒(méi)有考慮Sink節(jié)點(diǎn)的移動(dòng)路徑選擇。文獻(xiàn)[4]將監(jiān)測(cè)區(qū)域分成若干個(gè)三角形和其外圓,Sink節(jié)點(diǎn)停留在圓心,采用貪婪算法獲知下一時(shí)刻的停留位置,單跳收集傳感節(jié)點(diǎn)的數(shù)據(jù)。文獻(xiàn)[5]將傳感節(jié)點(diǎn)分簇,并選擇簇頭。Sink遍歷所有簇頭收集數(shù)據(jù)。但是文獻(xiàn)[3-5]側(cè)重于考慮Sink節(jié)點(diǎn)的移動(dòng)路徑,只是采用單跳數(shù)據(jù)采集方法收集數(shù)據(jù)。文獻(xiàn)[6-7]綜合考慮Sink節(jié)點(diǎn)的移動(dòng)路徑選擇和最優(yōu)化方法,建立Sink節(jié)點(diǎn)移動(dòng)的無(wú)線傳感網(wǎng)生存時(shí)間優(yōu)化模型,并提出對(duì)應(yīng)方法求解。但是文獻(xiàn)[3-7]只考慮二維無(wú)線傳感網(wǎng)下Sink移動(dòng)的數(shù)據(jù)收集問(wèn)題,即Sink節(jié)點(diǎn)在同一個(gè)水平面上移動(dòng),沒(méi)有考慮豎軸方向和三維場(chǎng)景,其移動(dòng)路徑選擇方法很難適用于三維無(wú)線傳感網(wǎng)。

目前部分學(xué)者側(cè)重于研究三維無(wú)線傳感網(wǎng)的節(jié)點(diǎn)路徑規(guī)劃、數(shù)據(jù)收集等問(wèn)題。如文獻(xiàn)[8]考慮障礙物的三維結(jié)構(gòu),根據(jù)高度分成多個(gè)層,并在每一個(gè)層上確定可停留位置。提出近似三維歐幾里德最短路徑算法尋找到目的地址的最短路徑。文獻(xiàn)[9]采用模糊聚類方法尋找最小化節(jié)點(diǎn)能耗的最優(yōu)分簇,采用粒子群優(yōu)化方法尋找最優(yōu)簇頭,從而解決因網(wǎng)絡(luò)總能量消耗下降而導(dǎo)致的網(wǎng)絡(luò)分裂問(wèn)題。文獻(xiàn)[10-11]提出了基于偏心率的數(shù)據(jù)路由算法,該算法將網(wǎng)絡(luò)劃分為三維子空間,在子空間中選擇路由質(zhì)心節(jié)點(diǎn)進(jìn)行數(shù)據(jù)路由算法,從而降低了選舉階段節(jié)點(diǎn)的能耗、內(nèi)部通信的能耗和數(shù)據(jù)傳輸跳數(shù)。但是文獻(xiàn)[6-11]只是考慮Sink靜止的數(shù)據(jù)收集方法,同樣存在能量空穴問(wèn)題。文獻(xiàn)[12]提出一種Sink移動(dòng)的有效數(shù)據(jù)收集算法(Efficient Data Gathering in 3D linear underwater wireless sensor networks using Sink mobility,EDG_3D)。EDG_3D考慮移動(dòng)Sink節(jié)點(diǎn)和快遞節(jié)點(diǎn)的線性移動(dòng),建立和求解最大化網(wǎng)絡(luò)生存時(shí)間、最小化數(shù)據(jù)傳輸時(shí)延和最大化吞吐率的優(yōu)化模型,盡可能降低節(jié)點(diǎn)的通信能耗,但是其線性移動(dòng)路徑較簡(jiǎn)單。

綜上所述,為克服能量空穴問(wèn)題和提高網(wǎng)絡(luò)生存時(shí)間,考慮Sink節(jié)點(diǎn)移動(dòng)。目前節(jié)點(diǎn)分布在同一個(gè)平面上的二維無(wú)線傳感網(wǎng)的Sink節(jié)點(diǎn)移動(dòng)、數(shù)據(jù)收集等問(wèn)題研究成果較多,但是沒(méi)有考慮豎軸方向和三維場(chǎng)景,其算法很難適用于節(jié)點(diǎn)分布在立體空間區(qū)域中的三維無(wú)線傳感網(wǎng)。目前三維無(wú)線傳感網(wǎng)主要側(cè)重于到目的節(jié)點(diǎn)的路徑規(guī)劃,靜態(tài)傳感節(jié)點(diǎn)的數(shù)據(jù)收集,較少涉及Sink節(jié)點(diǎn)的三維移動(dòng)路徑選擇和數(shù)據(jù)收集問(wèn)題。由于Sink節(jié)點(diǎn)移動(dòng)方向、Sink節(jié)點(diǎn)是否停留、數(shù)據(jù)收集方法等因素都能影響網(wǎng)絡(luò)生存時(shí)間、數(shù)據(jù)傳輸率等網(wǎng)絡(luò)性能,因此綜合考慮多種因素,提出Sink節(jié)點(diǎn)移動(dòng)的三維無(wú)線傳感網(wǎng)數(shù)據(jù)收集算法(Data Collection Algorithm of Three-dimensional Wireless Sensor Network with mobile Sink node,DCA_TWSN)。即提出三維環(huán)境下的正方體網(wǎng)格劃分方法,建立包括Sink移動(dòng)路徑選擇約束、數(shù)據(jù)流量約束、能耗約束、鏈路約束等約束條件的數(shù)據(jù)收集優(yōu)化模型。采用最優(yōu)化和修正蟻群算法求解該優(yōu)化模型,獲得最優(yōu)方案,即Sink節(jié)點(diǎn)能尋找到較優(yōu)移動(dòng)路徑,傳感節(jié)點(diǎn)能尋找到較優(yōu)數(shù)據(jù)傳輸方案,從而提高網(wǎng)絡(luò)生存時(shí)間和數(shù)據(jù)傳輸率、降低移動(dòng)路徑長(zhǎng)度、平均節(jié)點(diǎn)能耗方差和丟包率。

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

在 DCA_TWSN中,假設(shè):在三維立體監(jiān)測(cè)區(qū)域中,存在多個(gè)位置靜止的傳感節(jié)點(diǎn)和一個(gè)可移動(dòng)的Sink節(jié)點(diǎn)。移動(dòng)Sink節(jié)點(diǎn)可移動(dòng)到監(jiān)測(cè)區(qū)域的任一正方體中心;靜態(tài)傳感節(jié)點(diǎn)安裝有相同類型的傳感器且具有相同的能耗參數(shù),初始能量和通信半徑;靜態(tài)傳感節(jié)點(diǎn)和Sink節(jié)點(diǎn)可通過(guò)GPS、北斗等衛(wèi)星定位模塊或其他定位算法,獲知自身的位置坐標(biāo);靜態(tài)傳感節(jié)點(diǎn)的初始能量有限。

圖1 正方體網(wǎng)格劃分

如圖1所示,將三維長(zhǎng)方體監(jiān)測(cè)區(qū)域分成若干個(gè)大小一致的正方體網(wǎng)格,并根據(jù)從左到右,從前到后和從上到下的原則對(duì)每一個(gè)正方體網(wǎng)格進(jìn)行編碼。如Cu(Lv,Hv,Gv)表示從左開始計(jì)數(shù)的第Hv列中從前到后開始計(jì)數(shù)的第Lv行中從下到上的第Gv個(gè)正方體網(wǎng)格。如圖2所示,靜態(tài)傳感節(jié)點(diǎn)分布在長(zhǎng)方體監(jiān)測(cè)區(qū)域內(nèi),移動(dòng)Sink節(jié)點(diǎn)隨機(jī)分布在某一個(gè)正方體網(wǎng)格中心,且節(jié)點(diǎn)可獲知自身的位置。當(dāng)網(wǎng)絡(luò)運(yùn)行后,移動(dòng)Sink節(jié)點(diǎn)根據(jù)靜態(tài)傳感節(jié)點(diǎn)的信息和正方體網(wǎng)格中心位置,選擇移動(dòng)到下一時(shí)刻的鄰居網(wǎng)格中心位置上收集靜態(tài)傳感節(jié)點(diǎn)的信息。如果靜態(tài)傳感節(jié)點(diǎn)能與Sink節(jié)點(diǎn)通信,則將數(shù)據(jù)通過(guò)多跳的方式發(fā)送給Sink節(jié)點(diǎn),否則將數(shù)據(jù)存儲(chǔ)到緩存中。但是 DCA_TWSN仍需要解決以下二個(gè)問(wèn)題:一是如何考慮Sink節(jié)點(diǎn)的移動(dòng)路徑選擇和Sink節(jié)點(diǎn)與靜態(tài)傳感節(jié)點(diǎn)的數(shù)據(jù)通信,建立包括移動(dòng)選擇約束、數(shù)據(jù)傳輸約束、流量最大約束、節(jié)點(diǎn)能耗約束等約束條件的Sink節(jié)點(diǎn)數(shù)據(jù)收集優(yōu)化模型。二是如何采用修正的蟻群算法求解優(yōu)化模型,獲得最優(yōu)方案。這二個(gè)問(wèn)題的具體解決如下。

圖2 算法原理

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

網(wǎng)絡(luò)啟動(dòng)后,Sink節(jié)點(diǎn)停留在正方體網(wǎng)格中心間移動(dòng)收集傳感節(jié)點(diǎn)數(shù)據(jù)。傳感節(jié)點(diǎn)判斷自身是否能與Sink節(jié)點(diǎn)通信,如果能,則將數(shù)據(jù)通過(guò)多跳方式發(fā)送給Sink節(jié)點(diǎn),否則感知數(shù)據(jù),并更新緩存空間。根據(jù)上述分析,數(shù)據(jù)收集算法應(yīng)讓Sink節(jié)點(diǎn)在最短的移動(dòng)路徑下能全覆蓋所有靜態(tài)傳感節(jié)點(diǎn),其數(shù)據(jù)傳輸率和網(wǎng)絡(luò)生存時(shí)間盡可能高且移動(dòng)路徑長(zhǎng)度盡可能小,即建立以下優(yōu)化模型。

max(RT/Lpath)

(1)

s.t. CRate==1

(1a)

(1b)

(1c)

(1d)

(1e)

(1f)

(1g)

(1h)

(1j)

(2)

(3)

(4)

式中:Cmax表示傳感節(jié)點(diǎn)的最大存儲(chǔ)容量。約束條件(1g)表示在整個(gè)網(wǎng)絡(luò)生存時(shí)間內(nèi)節(jié)點(diǎn)能耗不大于其初始能量。約束條件(1h)表示鏈路傳輸?shù)臄?shù)據(jù)總量有限,節(jié)點(diǎn)間數(shù)據(jù)傳輸值不大于最大鏈路傳輸量。

3 算法求解

3.1 Sink節(jié)點(diǎn)移動(dòng)路徑的適應(yīng)度值

假設(shè)已知能滿足約束條件(1a)-(1e)約束條件的Sink節(jié)點(diǎn)移動(dòng)路徑和該Sink節(jié)點(diǎn)路徑能最大化優(yōu)化模型(1)的目標(biāo)函數(shù),且Sink節(jié)點(diǎn)是在移動(dòng)路徑上的每一個(gè)網(wǎng)格中心停留和收集數(shù)據(jù),則將Sink節(jié)點(diǎn)沿著該移動(dòng)路徑的數(shù)據(jù)收集轉(zhuǎn)換成若干個(gè)在某一個(gè)網(wǎng)格中心位置上停留的優(yōu)化模型,即當(dāng)Sink節(jié)點(diǎn)停留在位置g上時(shí),以多跳方式接收傳感節(jié)點(diǎn)的數(shù)據(jù)。不能與Sink節(jié)點(diǎn)通信的傳感節(jié)點(diǎn)處于休眠狀態(tài),自動(dòng)更新自身的存儲(chǔ)數(shù)據(jù)。此時(shí)Sink節(jié)點(diǎn)的數(shù)據(jù)收集應(yīng)該考慮盡可能讓其通信能耗短,網(wǎng)絡(luò)生存時(shí)間最大,即Sink節(jié)點(diǎn)停留在位置g上時(shí)的數(shù)據(jù)收集優(yōu)化模型為:

min(qg=1/Tg)

(5)

(5a)

(5b)

(5c)

(5d)

(6)

(7)

(8)

fitness=RT/Lpath

(9)

3.2 蟻群算法求解

3.1節(jié)可獲得Sink節(jié)點(diǎn)路徑已知的所有節(jié)點(diǎn)間的數(shù)據(jù)轉(zhuǎn)發(fā)量,即最優(yōu)數(shù)據(jù)收集方案。該數(shù)據(jù)通信方案和已知的Sink節(jié)點(diǎn)路徑,可構(gòu)成優(yōu)化模型(1)的最優(yōu)解。因此優(yōu)化模型(1)需解決以下路徑優(yōu)化模型。

(10)

蟻群算法(Ant Colony Optimization,ACO)是一種受真實(shí)螞蟻覓食行為啟發(fā)的算法。在ACO中,螞蟻隨機(jī)產(chǎn)生,并在構(gòu)建圖上不停行走搜索解決方案。這種搜索行為使得ACO適合于解決旅行商等組合優(yōu)化問(wèn)題,且已成功應(yīng)用于許多工業(yè)和科學(xué)問(wèn)題。因此采用修正的蟻群算法求解優(yōu)化模型(10),尋找Sink節(jié)點(diǎn)的移動(dòng)路徑。如圖3所示。

圖3 DCA_TWSN的收斂圖

具體求解步驟如下:

步驟2 初始化螞蟻m的初始位置,并令初始位置為螞蟻m的當(dāng)前位置。

步驟3 螞蟻m在當(dāng)前位置上停留,分析所有傳感節(jié)點(diǎn)是否能以多跳的方式與該位置上的Sink節(jié)點(diǎn)通信,如果能,則標(biāo)記傳感節(jié)點(diǎn),表示Sink節(jié)點(diǎn)已經(jīng)覆蓋到該傳感節(jié)點(diǎn)。統(tǒng)計(jì)所有傳感節(jié)點(diǎn)是否全覆蓋,如果全覆蓋,則m=m+1。如果m>M,則獲得符合約束條件(1a)-(1e)的螞蟻m移動(dòng)路徑,m=1,跳到步驟5,否則跳到步驟2。如果不是全覆蓋,則跳到步驟4。

步驟4 記錄當(dāng)前網(wǎng)格,并讓當(dāng)前位置網(wǎng)格覆蓋次數(shù)加1。根據(jù)當(dāng)前位置,獲得鄰居網(wǎng)格集合。選擇該鄰居網(wǎng)格集合中的網(wǎng)格覆蓋次數(shù)最小的網(wǎng)格,獲得可停留的下一時(shí)刻網(wǎng)格集合。通過(guò)式(11)計(jì)算下一時(shí)刻網(wǎng)格集合中每一個(gè)網(wǎng)格的概率,并計(jì)算累計(jì)概率。隨機(jī)選擇一個(gè)[0,1]的隨機(jī)數(shù)。選擇累計(jì)概率大于該隨機(jī)數(shù)的網(wǎng)格,并從中選擇第一個(gè)網(wǎng)格作為下一個(gè)時(shí)刻的停留網(wǎng)格,令當(dāng)前位置為該下一個(gè)時(shí)刻的停留網(wǎng)格,跳到步驟3。

(11)

步驟6 通過(guò)式(9),計(jì)算螞蟻m的適應(yīng)度值。m=m+1。如果m>M,則完成所有螞蟻移動(dòng)路徑的適應(yīng)度值計(jì)算,跳到步驟7,否則跳到步驟5。

步驟7 根據(jù)當(dāng)前所有螞蟻的移動(dòng)路徑和適應(yīng)度值,揮發(fā)所有網(wǎng)格的信息素值。且選擇當(dāng)前適應(yīng)度值最大的螞蟻,增加該螞蟻移動(dòng)路徑上的所有網(wǎng)格的信息素。

(12)

式中:fitness(k)表示第k個(gè)迭代中最優(yōu)適應(yīng)度值,Rho表示揮發(fā)因子,Q表示信息素增加因子。

步驟8 如果k

循環(huán)執(zhí)行關(guān)鍵步驟2～步驟8,則可獲得優(yōu)化模型(1)的一個(gè)最優(yōu)解,即當(dāng)前最優(yōu)的Sink節(jié)點(diǎn)的移動(dòng)路徑和傳感節(jié)點(diǎn)的數(shù)據(jù)傳輸路徑,從而達(dá)到提高網(wǎng)絡(luò)生存時(shí)間和數(shù)據(jù)傳輸率,降低移動(dòng)路徑長(zhǎng)度的目的。

4 算法仿真

4.1 仿真參數(shù)選擇

如表1所示,選擇表1中參數(shù)進(jìn)行仿真實(shí)驗(yàn),采用MATLAB軟件進(jìn)行仿真實(shí)驗(yàn),獲得Sink節(jié)點(diǎn)的移動(dòng)該路徑長(zhǎng)度,網(wǎng)絡(luò)生存時(shí)間,傳感節(jié)點(diǎn)的平均數(shù)據(jù)傳輸率,平均節(jié)點(diǎn)能耗方差和丟包率等性能參數(shù)值。其中網(wǎng)絡(luò)生存時(shí)間,傳感節(jié)點(diǎn)的數(shù)據(jù)傳輸率分別根據(jù)式(7)和式(8)計(jì)算,Sink節(jié)點(diǎn)的移動(dòng)該路徑長(zhǎng)度定義為Sink節(jié)點(diǎn)經(jīng)過(guò)的網(wǎng)格數(shù)量,平均節(jié)點(diǎn)能耗方差定義為網(wǎng)絡(luò)生存時(shí)間內(nèi),傳感節(jié)點(diǎn)消耗能量的方差。由于移動(dòng)傳感節(jié)點(diǎn)會(huì)因自身數(shù)據(jù)存儲(chǔ)容量有限導(dǎo)致自身數(shù)據(jù)的丟失,則丟棄的數(shù)據(jù)量定義為:

(13)

(14)

式中:Losstotal表示所有傳感節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)包總量。

表1 仿真參數(shù)表

4.2 仿真結(jié)果分析

首先分析 DCA_TWSN的收斂性。選擇移動(dòng)傳感節(jié)點(diǎn)個(gè)數(shù)100,Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)4和表1中參數(shù),循環(huán)200次計(jì)算 DCA_TWSN中當(dāng)前螞蟻的最優(yōu)適應(yīng)度值,獲得收斂圖3。如圖3所示,前期經(jīng)過(guò)多次迭代,每輪最優(yōu)適應(yīng)度值不斷上升。當(dāng)?shù)?0次迭代以后,每輪最優(yōu)適應(yīng)度值一直收斂到114。因此DCA_TWSN是收斂的,可尋找到優(yōu)化模型(1)的最優(yōu)解。

4.2.1 Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)變化的仿真結(jié)果分析

選擇Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)1,2,3,4,5,6,選擇移動(dòng)傳感節(jié)點(diǎn)個(gè)數(shù)100,選擇表1中的參數(shù),循環(huán)計(jì)算RAND、GREED[14]、EDG_3D[12]和DCA_TWSN的Sink節(jié)點(diǎn)的移動(dòng)該路徑長(zhǎng)度、網(wǎng)絡(luò)生存時(shí)間、傳感節(jié)點(diǎn)的平均數(shù)據(jù)傳輸率、平均節(jié)點(diǎn)能耗方差和丟包率。其中在RAND中,移動(dòng)傳感節(jié)點(diǎn)隨機(jī)選擇和感知未覆蓋的網(wǎng)格。在GREED中,移動(dòng)傳感節(jié)點(diǎn)在距離最近且未經(jīng)過(guò)的網(wǎng)格集合中隨機(jī)選擇一個(gè),作為下一個(gè)時(shí)刻的感知位置。在EDG_3D中,根據(jù)當(dāng)前三維網(wǎng)格的數(shù)量,選擇遍歷所有網(wǎng)格的線性移動(dòng)路徑。在RAND、GREED和EDG_3D中,移動(dòng)傳感節(jié)點(diǎn)選擇下一個(gè)時(shí)刻的停留網(wǎng)格方法不一致,但是采用相同的Sink節(jié)點(diǎn)停留在某一個(gè)網(wǎng)格中心的數(shù)據(jù)收集方法。具體仿真結(jié)果內(nèi)容如下。

如圖4所示,隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,RAND和GREED的Sink節(jié)點(diǎn)移動(dòng)路徑長(zhǎng)度上下起伏,EDG_3D和DCA_TWSN的Sink節(jié)點(diǎn)移動(dòng)路徑長(zhǎng)度下降,但是DCA_TWSN的Sink節(jié)點(diǎn)移動(dòng)路徑長(zhǎng)度都遠(yuǎn)低于RAND、GREED和EDG_3D的Sink節(jié)點(diǎn)移動(dòng)路徑長(zhǎng)度。這是因?yàn)?RAND中移動(dòng)傳感節(jié)點(diǎn)從周圍鄰居網(wǎng)格中心中隨機(jī)選擇一個(gè)作為下一跳的停留網(wǎng)格中心,這種選擇比較盲目和隨機(jī),因此其Sink節(jié)點(diǎn)移動(dòng)路徑長(zhǎng)度最短。GREED從距離最近的鄰居網(wǎng)格中心中隨機(jī)選擇未停留過(guò)的網(wǎng)格中心作為下一個(gè)停留網(wǎng)格,選擇也具有一定的隨機(jī)性。EDG_3D是尋找遍歷所有網(wǎng)格中心的線性移動(dòng)路徑,并從頭開始選擇能全覆蓋傳感節(jié)點(diǎn)的最小子路徑。這三個(gè)算法的都沒(méi)有考慮尋找移動(dòng)路徑長(zhǎng)度最優(yōu)問(wèn)題,因此其Sink節(jié)點(diǎn)的移動(dòng)路徑長(zhǎng)度較長(zhǎng)。DCA_TWSN在螞蟻選擇路徑時(shí)將Sink節(jié)點(diǎn)的移動(dòng)路徑長(zhǎng)度作為該路徑適應(yīng)度值的一個(gè)重要參數(shù),并影響路徑上網(wǎng)格的信息素更新,經(jīng)多次迭代后螞蟻能尋找到較優(yōu)移動(dòng)路徑,從而降低其移動(dòng)路徑長(zhǎng)度。

圖4 Sink節(jié)點(diǎn)的移動(dòng)路徑長(zhǎng)度比較圖

如圖5所示,隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,RAND、GREED、EDG_3D和DCA_TWSN的網(wǎng)絡(luò)生存時(shí)間明顯下降,但是 DCA_TWSN的網(wǎng)絡(luò)生存時(shí)間遠(yuǎn)大于RAND、GREED、EDG_3D的網(wǎng)絡(luò)生存時(shí)間。這是因?yàn)?隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,與Sink節(jié)點(diǎn)通信的傳感節(jié)點(diǎn)數(shù)量變大,處于Sink節(jié)點(diǎn)周圍的傳感節(jié)點(diǎn)需要轉(zhuǎn)發(fā)更多的其他傳感節(jié)點(diǎn)的數(shù)據(jù),其能耗增加,因此所有算法的網(wǎng)絡(luò)生存時(shí)間降低。但是由于DCA_TWSN將網(wǎng)絡(luò)生存時(shí)間作為適應(yīng)度函數(shù)的重要參數(shù)之一,且在蟻群求解過(guò)程中螞蟻根據(jù)信息素的結(jié)果,盡量向具有較多傳感節(jié)點(diǎn)的網(wǎng)格移動(dòng),降低了這些節(jié)點(diǎn)的能耗,從而提高了網(wǎng)絡(luò)生存時(shí)間,RAND、GREED和EDG_3D在移動(dòng)路徑選擇時(shí)沒(méi)有考慮網(wǎng)絡(luò)生存時(shí)間,這三個(gè)算法的網(wǎng)絡(luò)生存時(shí)間相對(duì)較短。

圖5 網(wǎng)絡(luò)生存時(shí)間比較圖

如圖6所示,隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,RAND、GREED、EDG_3D和DCA_TWSN的傳感節(jié)點(diǎn)的平均數(shù)據(jù)傳輸率會(huì)提高,但是DCA_TWSN的平均數(shù)據(jù)傳輸率略高于RAND、GREED、EDG_3D的平均數(shù)據(jù)傳輸率。這是因?yàn)?隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,傳感節(jié)點(diǎn)有更多的機(jī)會(huì)與Sink節(jié)點(diǎn)通信,上傳自身感知和其他傳感節(jié)點(diǎn)的數(shù)據(jù),RAND、GREED、EDG_3D和DCA_TWSN的平均數(shù)據(jù)傳輸率相對(duì)提高。但是由于 DCA_TWSN能尋找到較優(yōu)的移動(dòng)路徑,增加了傳感節(jié)點(diǎn)與Sink節(jié)點(diǎn)的通信時(shí)間,導(dǎo)致所有傳感節(jié)點(diǎn)成功發(fā)送數(shù)據(jù)的概率提高,因此其傳感節(jié)點(diǎn)的平均數(shù)據(jù)傳輸率變大。

如圖7所示,隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,RAND、GREED、EDG_3D和DCA_TWSN的平均節(jié)點(diǎn)能耗方差上升,但是DCA_TWSN的平均節(jié)點(diǎn)能耗方差低于RAND、GREED、EDG_3D的平均節(jié)點(diǎn)能耗方差。這是因?yàn)?隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,Sink節(jié)點(diǎn)在某一個(gè)網(wǎng)格中心停留時(shí),其接收的傳感節(jié)點(diǎn)數(shù)量變多,這導(dǎo)致跳數(shù)較少的傳感節(jié)點(diǎn)不僅需要發(fā)送自身的數(shù)據(jù),還需要承受更多其他傳感節(jié)點(diǎn)的數(shù)據(jù),增加自身能耗,導(dǎo)致傳感節(jié)點(diǎn)間能量消耗不平衡,平均節(jié)點(diǎn)能耗方差上升。但是 DCA_TWSN建立了三維無(wú)線網(wǎng)數(shù)據(jù)收集算法的優(yōu)化模型,采用蟻群算法求解該模型,獲得全覆蓋所有傳感節(jié)點(diǎn)的最優(yōu)移動(dòng)路徑,讓傳感節(jié)點(diǎn)盡可能出現(xiàn)在Sink節(jié)點(diǎn)的附近,平衡了傳感節(jié)點(diǎn)的能量消耗,降低了平均節(jié)點(diǎn)能耗方差。

圖7 平均節(jié)點(diǎn)能耗比較圖

如圖8所示,隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,RAND、GREED、EDG_3D和DCA_TWSN的丟包率下降,但是DCA_TWSN的丟包率低于RAND、GREED和EDG_3D的丟包率。這是因?yàn)?隨著Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)增加,能與Sink節(jié)點(diǎn)通信的傳感節(jié)點(diǎn)數(shù)量變大,導(dǎo)致傳感節(jié)點(diǎn)有更多的機(jī)會(huì)和時(shí)間與Sink節(jié)點(diǎn)通信,從而提高了自身的數(shù)據(jù)傳輸率,降低了丟包率。同時(shí) DCA_TWSN找到了能全覆蓋傳感節(jié)點(diǎn)的移動(dòng)路徑,讓所有傳感節(jié)點(diǎn)都能與Sink節(jié)點(diǎn)的通信,發(fā)送自身的數(shù)據(jù),因此其丟包率最低,當(dāng)Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)為5和6時(shí),其丟包率接近于0。

圖8 丟包率比較圖

總之,不管Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)如何變化,DCA_TWSN都能尋找到較優(yōu)的Sink節(jié)點(diǎn)移動(dòng)路徑,從而提高網(wǎng)絡(luò)生存時(shí)間和傳感節(jié)點(diǎn)的平均數(shù)據(jù)傳輸率、降低移動(dòng)路徑長(zhǎng)度、平均節(jié)點(diǎn)能耗方差和丟包率。

4.2.2 傳感節(jié)點(diǎn)數(shù)量變化的仿真結(jié)果分析

選擇Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)4,選擇移動(dòng)傳感節(jié)點(diǎn)個(gè)數(shù)100,120,140,160,180,200和選擇表1中的參數(shù),循環(huán)計(jì)算RAND、GREED、EDG_3D和DCA_TWSN的Sink節(jié)點(diǎn)的移動(dòng)該路徑長(zhǎng)度,網(wǎng)絡(luò)生存時(shí)間,傳感節(jié)點(diǎn)的平均數(shù)據(jù)傳輸率,平均節(jié)點(diǎn)能耗和平均丟包率。具體仿真結(jié)果如下:

如圖9所示,DCA_TWSN的移動(dòng)路徑長(zhǎng)度遠(yuǎn)低于RAND、GREED和EDG_3D的移動(dòng)路徑長(zhǎng)度,且其移動(dòng)路徑長(zhǎng)度不受傳感節(jié)點(diǎn)數(shù)量的影響。這是因?yàn)?不管傳感節(jié)點(diǎn)數(shù)量多少,DCA_TWSN都能通過(guò)求解優(yōu)化模型(1),尋找到權(quán)衡網(wǎng)絡(luò)生存時(shí)間、移動(dòng)路徑長(zhǎng)度和傳感節(jié)點(diǎn)數(shù)據(jù)傳輸率的Sink節(jié)點(diǎn)移動(dòng)路徑,降低了其移動(dòng)長(zhǎng)度。而RAND、GREED和EDG_3D在移動(dòng)過(guò)程中,沒(méi)有考慮傳感節(jié)點(diǎn)與Sink節(jié)點(diǎn)的通信問(wèn)題,其移動(dòng)長(zhǎng)度較長(zhǎng)。

圖9 移動(dòng)路徑長(zhǎng)度比較圖

如圖10所示,DCA_TWSN不受監(jiān)測(cè)區(qū)域內(nèi)傳感節(jié)點(diǎn)數(shù)量的影響,各個(gè)傳感節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)生存時(shí)間相差不大,且遠(yuǎn)高于RAND、GREED、EDG_3D的網(wǎng)絡(luò)生存時(shí)間。這是因?yàn)?DCA_TWSN可根據(jù)傳感節(jié)點(diǎn)數(shù)量和位置,通過(guò)蟻群算法自動(dòng)尋找較優(yōu)的Sink節(jié)點(diǎn)路徑方案,讓所有傳感節(jié)點(diǎn)都能與Sink節(jié)點(diǎn)通信,較好完成了Sink節(jié)點(diǎn)的數(shù)據(jù)收集,而其他算法都存在一定的局限性,因此DCA_TWSN的網(wǎng)絡(luò)生存時(shí)間最高。

圖10 網(wǎng)絡(luò)生存時(shí)間比較圖

如圖11所示,DCA_TWSN充分利用傳感節(jié)點(diǎn)的信息,評(píng)估每個(gè)螞蟻的適應(yīng)度值,實(shí)現(xiàn)傳感節(jié)點(diǎn)數(shù)據(jù)的有效上報(bào),其數(shù)據(jù)傳輸率最高。RAND、GREED和EDG_3D在Sink節(jié)點(diǎn)路徑尋找過(guò)程中沒(méi)有考慮數(shù)據(jù)傳輸率,傳感節(jié)點(diǎn)的數(shù)據(jù)通信路徑較差,其數(shù)據(jù)傳輸率較低。傳感節(jié)點(diǎn)數(shù)量變化的各個(gè)算法的平均節(jié)點(diǎn)能耗方差和丟包率的仿真結(jié)果和具體原因與4.2.1節(jié)中Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)變化下的仿真結(jié)果和具體原因基本一致,本文不再重復(fù)說(shuō)明,可參考4.2.1節(jié)。

圖11 傳感節(jié)點(diǎn)的平均數(shù)據(jù)傳輸率比較圖

5 總結(jié)

本文提出一種Sink節(jié)點(diǎn)移動(dòng)的三維無(wú)線傳感網(wǎng)數(shù)據(jù)收集算法(DCA_TWSN)。首先,提出算法假設(shè)、三維環(huán)境下的正方體網(wǎng)格劃分方法和基本原理。其次,用數(shù)學(xué)公式建立包括Sink移動(dòng)路徑選擇約束,數(shù)據(jù)流量約束、能耗約束、鏈路約束等約束條件的數(shù)據(jù)收集優(yōu)化模型。接著,提出了Sink節(jié)點(diǎn)移動(dòng)路徑的適應(yīng)度值計(jì)算方法,即采用最優(yōu)化方法求解已知Sink節(jié)點(diǎn)移動(dòng)路徑的數(shù)據(jù)收集優(yōu)化問(wèn)題。采用修正的蟻群算法求解Sink節(jié)點(diǎn)的移動(dòng)路徑問(wèn)題,獲得最優(yōu)方案。最后給出算法的仿真參數(shù),仿真比較DCA_TWSN、RAND、GREED和EDG_3D的性能。

總之,不管Sink節(jié)點(diǎn)的最大數(shù)據(jù)收集跳數(shù)和傳感節(jié)點(diǎn)數(shù)量如何變化,DCA_TWSN都能尋找到較優(yōu)的移動(dòng)路徑和數(shù)據(jù)傳輸方案,從而提高網(wǎng)絡(luò)生存時(shí)間和傳感節(jié)點(diǎn)的平均數(shù)據(jù)傳輸率、降低移動(dòng)路徑長(zhǎng)度、平均節(jié)點(diǎn)能耗方差和丟包率。但是DCA_TWSN 算法采用次梯度算法求解優(yōu)化模型(6),采用修正的蟻群算法求解優(yōu)化模型(10),其算法的時(shí)間復(fù)雜度相對(duì)較高,因此下一個(gè)階段目標(biāo)是通過(guò)Sink節(jié)點(diǎn)和傳感節(jié)點(diǎn)的相互通信,獲知周圍傳感節(jié)點(diǎn)的信息,分布式計(jì)算Sink節(jié)點(diǎn)的移動(dòng)路徑和傳感節(jié)點(diǎn)的通信方案,從而降低算法的時(shí)間復(fù)雜度。