基于蟻群優(yōu)化的WSN網(wǎng)絡(luò)數(shù)據(jù)融合算法*

丁 華

(南京師范大學(xué)泰州學(xué)院 教育技術(shù)中心，江蘇 泰州 225300)

近年來(lái)，隨著無(wú)線通信技術(shù)、傳感器技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)作為一種自組織無(wú)線網(wǎng)絡(luò)已經(jīng)獲得了越來(lái)越廣泛的重視和應(yīng)用[1-2].WSN網(wǎng)絡(luò)能夠?qū)崟r(shí)感知、采集覆蓋范圍內(nèi)各種環(huán)境信息，并使用多跳路由完成數(shù)據(jù)聚合和傳輸.WSN網(wǎng)絡(luò)能夠不受時(shí)間、地點(diǎn)、環(huán)境限制地采集和獲取信息，并且其具有自組織、部署迅捷、高容錯(cuò)性和強(qiáng)隱蔽性等技術(shù)優(yōu)勢(shì).

為了全面監(jiān)測(cè)網(wǎng)絡(luò)部署環(huán)境，WSN網(wǎng)絡(luò)一般密集布設(shè)無(wú)線節(jié)點(diǎn)，且需要定時(shí)頻繁采集數(shù)據(jù)并向鄰居節(jié)點(diǎn)發(fā)送.這樣不僅導(dǎo)致網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)高度重復(fù)冗余，而且加重了節(jié)點(diǎn)能耗負(fù)擔(dān)，影響了WSN網(wǎng)絡(luò)的工作時(shí)長(zhǎng)和使用.針對(duì)上述問(wèn)題，在WSN網(wǎng)絡(luò)中通過(guò)聚合無(wú)線傳輸，減少節(jié)點(diǎn)能量損耗，并提升WSN網(wǎng)絡(luò)的工作時(shí)長(zhǎng)，已經(jīng)成為業(yè)內(nèi)重點(diǎn)關(guān)注的研究方法之一.

無(wú)線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)能耗最大的模塊是數(shù)據(jù)通信模塊，因此減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸是節(jié)能的關(guān)鍵.數(shù)據(jù)融合可以利用無(wú)線傳感器節(jié)點(diǎn)的運(yùn)算和對(duì)多源數(shù)據(jù)的互補(bǔ)性來(lái)提高信息的質(zhì)量，并通過(guò)中間融合節(jié)點(diǎn)消除數(shù)據(jù)之間的冗余性和相似性，降低無(wú)線數(shù)據(jù)的傳輸量[3].數(shù)據(jù)融合將感知節(jié)點(diǎn)采集的各種初始信息進(jìn)行聚合、去冗余處理，并通過(guò)數(shù)據(jù)融合算法選取合適的傳感器節(jié)點(diǎn)作為融合的中間節(jié)點(diǎn)，最終將精簡(jiǎn)后的數(shù)據(jù)發(fā)送至匯聚節(jié)點(diǎn)，從而實(shí)現(xiàn)減少節(jié)點(diǎn)能耗，提升網(wǎng)絡(luò)工作時(shí)長(zhǎng)的目標(biāo).

圖1 WSN網(wǎng)絡(luò)中數(shù)據(jù)融合傳輸示意圖Fig.1 Schematic diagram of data aggregation transmission in WSN

蟻群算法一般劃分為適應(yīng)階段與協(xié)作階段.在適應(yīng)階段，被選擇路徑根據(jù)螞蟻留下的信息素調(diào)整自身節(jié)點(diǎn)選擇概率，某條路徑上的信息素越多，被選擇的概率越大；在協(xié)作階段，各條候選路徑通過(guò)信息的交流，搜索最優(yōu)路徑解.蟻群算法可視為分布式智能系統(tǒng)，分布在區(qū)域內(nèi)的多個(gè)點(diǎn)同時(shí)出發(fā)進(jìn)行搜索，具有全局搜索能力，增加了算法的可靠性.

為減少WSN網(wǎng)絡(luò)中數(shù)據(jù)傳輸量、優(yōu)化無(wú)線傳輸距離，本文提出了一種基于蟻群優(yōu)化的WSN網(wǎng)絡(luò)數(shù)據(jù)融合算法.該算法在構(gòu)造數(shù)據(jù)融合樹(shù)時(shí)，根據(jù)WSN網(wǎng)絡(luò)的傳輸特點(diǎn)改進(jìn)了蟻群算法，考慮了路徑偏轉(zhuǎn)角對(duì)路由的影響，調(diào)整節(jié)點(diǎn)選擇概率；同時(shí)對(duì)最優(yōu)的多個(gè)路徑更新信息素，以提升最優(yōu)路徑的搜索能力.為了驗(yàn)證算法的有效性，在WSN網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗、傳輸延遲方面與經(jīng)典算法對(duì)比，經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)，該算法能夠有效延長(zhǎng)網(wǎng)絡(luò)的生命周期、降低節(jié)點(diǎn)能耗，并能改善網(wǎng)絡(luò)負(fù)載均衡性.

1 融合算法模型設(shè)計(jì)

為了減少WSN網(wǎng)絡(luò)數(shù)據(jù)傳輸量，均衡節(jié)點(diǎn)能耗負(fù)載，并改善數(shù)據(jù)傳輸時(shí)延，本文將數(shù)據(jù)融合與節(jié)點(diǎn)路由相結(jié)合，利用改進(jìn)的蟻群算法尋找從源節(jié)點(diǎn)到宿節(jié)點(diǎn)的最優(yōu)路徑.

1.1 算法模型

基于蟻群算法的數(shù)據(jù)融合算法利用人工螞蟻模擬真實(shí)螞蟻，根據(jù)節(jié)點(diǎn)的信息素量和能量狀態(tài)啟發(fā)因子進(jìn)行權(quán)衡，尋找最優(yōu)的數(shù)據(jù)融合路徑.在搜索過(guò)程中，螞蟻根據(jù)待選擇路徑上的啟發(fā)信息和殘留信息量，計(jì)算狀態(tài)轉(zhuǎn)移概率.轉(zhuǎn)移概率計(jì)算表達(dá)式為

(1)

(2)

本文算法首先計(jì)算鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率，從中選取最優(yōu)路由路徑.轉(zhuǎn)發(fā)概率由路徑信息素和啟發(fā)因子決定.啟發(fā)因子需要根據(jù)算法應(yīng)用環(huán)境的不同而改變；信息素由螞蟻經(jīng)過(guò)此段路徑的頻率決定，需要設(shè)定有效的更新策略.為了避免殘留信息太多，減弱啟發(fā)信息的作用，螞蟻在每走完一步之后，對(duì)殘留的節(jié)點(diǎn)信息素進(jìn)行更新.t+n時(shí)刻路徑(i，j)上信息素表示為

τij(t+n)=(1-ρ)τij(t)+Δτij

(3)

(4)

(5)

分取10.00 mL濃度為5 mg/mL鉛標(biāo)準(zhǔn)溶液于300 mL燒杯中，按分析步驟進(jìn)行測(cè)定,沉淀后分別放置不同的時(shí)間，測(cè)定結(jié)果見(jiàn)表2。

1.2 構(gòu)造數(shù)據(jù)融合樹(shù)

在無(wú)線傳感器網(wǎng)絡(luò)中，分散在監(jiān)測(cè)區(qū)域的傳感器節(jié)點(diǎn)將采集到的信息逐步傳輸至匯聚節(jié)點(diǎn)，從而形成一棵反向組播樹(shù)，即無(wú)線數(shù)據(jù)包融合樹(shù)[6-7]，其結(jié)構(gòu)如圖2所示.融合樹(shù)模型中包含：葉子節(jié)點(diǎn)、中間節(jié)點(diǎn)和宿節(jié)點(diǎn).葉子節(jié)點(diǎn)負(fù)責(zé)采集數(shù)據(jù)，并將數(shù)據(jù)匯聚至中間節(jié)點(diǎn)；中間節(jié)點(diǎn)將子節(jié)點(diǎn)傳送過(guò)來(lái)的數(shù)據(jù)進(jìn)行融合處理，通過(guò)路由選擇，最終將數(shù)據(jù)傳輸至宿節(jié)點(diǎn).

圖2 無(wú)線數(shù)據(jù)融合樹(shù)模型Fig.2 Model for wireless data aggregation tree

WSN網(wǎng)絡(luò)可描述為一個(gè)簡(jiǎn)化的網(wǎng)絡(luò)圖G={V，E}，V為WSN網(wǎng)絡(luò)中的無(wú)線傳感器節(jié)點(diǎn)集，E為節(jié)點(diǎn)間的無(wú)線鏈路集.若節(jié)點(diǎn)vi與vj支持點(diǎn)對(duì)點(diǎn)直傳，則表示為無(wú)線鏈路eij=(vi，vj)，eij∈E.基于此，本文算法將WSN網(wǎng)絡(luò)中的節(jié)點(diǎn)生成無(wú)線數(shù)據(jù)融合樹(shù)，沿著數(shù)據(jù)融合樹(shù)提供的路由路徑進(jìn)行數(shù)據(jù)融合與傳輸，并發(fā)送至匯聚節(jié)點(diǎn).

1.3 算法設(shè)計(jì)

算法對(duì)最優(yōu)的多個(gè)路徑更新信息素，以提升最優(yōu)路徑的全局搜索能力，并進(jìn)行數(shù)據(jù)融合與傳輸.基于蟻群優(yōu)化的WSN網(wǎng)絡(luò)數(shù)據(jù)融合算法具體步驟如下：

1) 將無(wú)線傳感器節(jié)點(diǎn)和相關(guān)參數(shù)初始化.

2) 源節(jié)點(diǎn)以固定功率向周圍廣播請(qǐng)求信息，鄰居節(jié)點(diǎn)收到請(qǐng)求信息后，根據(jù)接收的信號(hào)強(qiáng)度計(jì)算節(jié)點(diǎn)距離.

3) 獲取節(jié)點(diǎn)鄰居列表信息.源節(jié)點(diǎn)周期性地對(duì)鄰居節(jié)點(diǎn)發(fā)送hello數(shù)據(jù)包，更新距離信息.無(wú)線傳感器網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都需要更新、維護(hù)鄰居列表，鄰居列表內(nèi)容包含：匯聚節(jié)點(diǎn)的位置信息、本節(jié)點(diǎn)和鄰節(jié)點(diǎn)的位置信息.

4) 基于偏轉(zhuǎn)角確定轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇概率，以獲取最優(yōu)路徑.雖然源節(jié)點(diǎn)與宿節(jié)點(diǎn)之間的直線距離最短，但所有數(shù)據(jù)轉(zhuǎn)發(fā)都采用直線路徑，會(huì)造成該路線負(fù)載過(guò)重，轉(zhuǎn)發(fā)沖突和能量消耗也急劇上升.需要利用轉(zhuǎn)發(fā)節(jié)點(diǎn)間的偏轉(zhuǎn)角定義轉(zhuǎn)發(fā)概率，從而選擇最優(yōu)的下一跳父節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā).

偏轉(zhuǎn)角定義如下：設(shè)節(jié)點(diǎn)i和節(jié)點(diǎn)j相鄰，稱θ=〈i，j〉為邊e(i，j)在節(jié)點(diǎn)j相對(duì)于宿節(jié)點(diǎn)的偏轉(zhuǎn)角.定義節(jié)點(diǎn)i在節(jié)點(diǎn)j處的偏轉(zhuǎn)角選擇參數(shù)為

(6)

由式(6)可知，宿節(jié)點(diǎn)的偏轉(zhuǎn)角越小，被選擇路徑越接近直線，該節(jié)點(diǎn)越有可能被選擇.

蟻群算法一般根據(jù)節(jié)點(diǎn)間距離、啟發(fā)因子大小計(jì)算選擇概率.節(jié)點(diǎn)距離越小，啟發(fā)因子越大，選擇概率越大.這種單一的選擇機(jī)制可能引導(dǎo)蟻群局限于當(dāng)前一跳的距離優(yōu)勢(shì)，選擇偏離方向的某個(gè)節(jié)點(diǎn)，造成局部最優(yōu)解.基于此，本文通過(guò)在啟發(fā)因子中加入偏轉(zhuǎn)角，從而調(diào)整轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇概率.在選擇下一跳節(jié)點(diǎn)時(shí)，若選擇節(jié)點(diǎn)相對(duì)于宿節(jié)點(diǎn)的偏轉(zhuǎn)角越小，則到達(dá)宿節(jié)點(diǎn)的路徑越近.

5) 更新節(jié)點(diǎn)信息素.本算法對(duì)節(jié)點(diǎn)信息素進(jìn)行動(dòng)態(tài)自適應(yīng)調(diào)節(jié)策略，初始時(shí)取一個(gè)相對(duì)較大的初始值ρinit；經(jīng)過(guò)T1時(shí)間段后對(duì)ρ進(jìn)行調(diào)節(jié)，取值λρ(t-1)；T2過(guò)后，調(diào)整為最小值ρmin.更新表達(dá)式為

(7)

式中，λ為信息素調(diào)節(jié)參數(shù).

節(jié)點(diǎn)信息素的設(shè)定策略決定著蟻群算法的搜索能力和收斂速度.若ρ太小，節(jié)點(diǎn)信息素?fù)]發(fā)慢，會(huì)使收斂速度降低；若ρ太大，節(jié)點(diǎn)信息素?fù)]發(fā)較快，會(huì)使算法過(guò)早收斂，無(wú)法達(dá)到最優(yōu)解.

在更新策略上，多只螞蟻從源節(jié)點(diǎn)出發(fā)，最后會(huì)尋找到多條到達(dá)匯聚節(jié)點(diǎn)的較優(yōu)路徑.由于WSN網(wǎng)絡(luò)狀況是不斷變化的，路由路徑只需要一條，因而無(wú)需將每次循環(huán)經(jīng)歷的所有節(jié)點(diǎn)信息素都同步更新；但若只更新當(dāng)前最優(yōu)路徑上的節(jié)點(diǎn)信息素，往往使螞蟻滿足于局部最優(yōu)解，降低了算法全局搜索和優(yōu)化能力.為此，在每次循環(huán)完成后，同時(shí)更新最優(yōu)及次優(yōu)路徑的節(jié)點(diǎn)信息素，使得算法的收斂速度和全局搜索能力最優(yōu).利用改進(jìn)后蟻群算法的概率公式尋找到達(dá)匯聚節(jié)點(diǎn)的最短路徑，這些最短路徑最終形成從源節(jié)點(diǎn)到宿節(jié)點(diǎn)的最短路徑樹(shù)，本算法的流程圖如圖3所示.

圖3 算法流程圖Fig.3 Flow chart of algorithm

2 仿真實(shí)驗(yàn)與分析

實(shí)驗(yàn)采用MATLAB進(jìn)行仿真，構(gòu)建一個(gè)半徑為100 m的圓形區(qū)域，在其中隨機(jī)部署10～100個(gè)無(wú)線傳感器節(jié)點(diǎn).為驗(yàn)證算法的性能，將本文算法與經(jīng)典算法SPT、ACO[8]和AEDT[9]進(jìn)行對(duì)比.由于蟻群算法中存在多項(xiàng)參數(shù)，不同的參數(shù)組合會(huì)影響算法的收斂速度以及路徑搜索質(zhì)量.表1中各參數(shù)的獲取是通過(guò)仿真試驗(yàn)調(diào)試獲取，經(jīng)過(guò)仿真運(yùn)行6～7次，在相關(guān)參數(shù)的設(shè)置區(qū)間內(nèi)稍作調(diào)整，最終獲取表1所示的本算法參數(shù)配置.

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameter settings

假定4種算法都采用相同的網(wǎng)絡(luò)覆蓋策略，當(dāng)WSN網(wǎng)絡(luò)中生存節(jié)點(diǎn)逐步減少，直至無(wú)法有效覆蓋所在區(qū)域時(shí)的時(shí)長(zhǎng)稱為該WSN的網(wǎng)絡(luò)生命周期.圖4顯示了4種算法在不同節(jié)點(diǎn)個(gè)數(shù)下，WSN網(wǎng)絡(luò)的生命周期變化趨勢(shì).隨著節(jié)點(diǎn)個(gè)數(shù)的增多，WSN網(wǎng)絡(luò)的生命周期都呈現(xiàn)上升趨勢(shì).因?yàn)殡S著WSN網(wǎng)絡(luò)節(jié)點(diǎn)的增多，即使有少數(shù)傳感器節(jié)點(diǎn)由于能量耗盡而無(wú)法工作，WSN網(wǎng)絡(luò)有更多的備份節(jié)點(diǎn)維持網(wǎng)絡(luò)的運(yùn)行.比較4種算法可知，SPT與ACO算法對(duì)應(yīng)的WSN網(wǎng)絡(luò)生命周期較短.當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)較少時(shí)，本文算法的生命周期略低于AEDT算法，隨著節(jié)點(diǎn)的增多，本文算法網(wǎng)絡(luò)生命周期長(zhǎng)的優(yōu)勢(shì)逐漸凸顯，在4種算法中具有最長(zhǎng)的網(wǎng)絡(luò)生命周期.這說(shuō)明本文算法能夠根據(jù)節(jié)點(diǎn)能量選擇融合路徑，減少網(wǎng)絡(luò)整體的無(wú)線傳輸能耗.

圖4 4種算法的網(wǎng)絡(luò)生命周期對(duì)比Fig.4 Comparison of network life cycles of 4 algorithms

在WSN網(wǎng)絡(luò)中，節(jié)點(diǎn)負(fù)載均衡也是影響網(wǎng)絡(luò)工作周期的重要因素.有效的路由融合算法需要能夠均衡WSN網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載，使得各個(gè)節(jié)點(diǎn)的能量平均消耗，不會(huì)因部分節(jié)點(diǎn)能量提前耗盡而影響網(wǎng)絡(luò)通信.圖5為4種算法的節(jié)點(diǎn)負(fù)載方差對(duì)比圖.

圖5 4種算法的節(jié)點(diǎn)負(fù)載方差對(duì)比Fig.5 Comparison of node load variance of 4 algorithms

如圖5所示，SPT、ACO算法由于沒(méi)有充分考慮節(jié)點(diǎn)能量，節(jié)點(diǎn)傳輸負(fù)載的差異性也極大.這使得WSN網(wǎng)絡(luò)會(huì)由于部分節(jié)點(diǎn)過(guò)早的能量耗盡而無(wú)法工作.而AEDT和本文算法節(jié)點(diǎn)負(fù)載方差較為平穩(wěn)，網(wǎng)絡(luò)中的節(jié)點(diǎn)負(fù)載處于均衡狀態(tài).其中，本文算法隨著節(jié)點(diǎn)的增多，負(fù)載方差還略有下降，從而保證各個(gè)節(jié)點(diǎn)的能量均衡消耗，提升整個(gè)網(wǎng)絡(luò)的工作周期.

圖6為4種算法在無(wú)線數(shù)據(jù)包匯聚延遲方面的性能對(duì)比.綜合而言，隨著網(wǎng)絡(luò)規(guī)模的增大，4種算法的無(wú)線數(shù)據(jù)包的匯聚延遲也在逐漸增大.其中，SPT、ACO算法時(shí)延性能較差，隨著節(jié)點(diǎn)的增多，無(wú)線數(shù)據(jù)包匯聚時(shí)延增長(zhǎng)接近線性.而AEDT算法考慮了數(shù)據(jù)延遲的因素，時(shí)延效果相對(duì)更好.而本文算法的時(shí)延性能較優(yōu)，尤其是當(dāng)節(jié)點(diǎn)數(shù)大于60時(shí)，時(shí)延增長(zhǎng)趨勢(shì)暫緩.這是因?yàn)楸疚乃惴ǖ穆窂竭x擇策略綜合考慮距離與負(fù)載的影響，能夠自主選擇最優(yōu)的傳輸路徑.

圖6 4種算法的數(shù)據(jù)包匯聚延遲對(duì)比Fig.6 Comparison of data package aggregation delay of 4 algorithms

3 結(jié) 論

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)存在的數(shù)據(jù)傳輸量大、局部節(jié)點(diǎn)負(fù)載過(guò)重等問(wèn)題，本文提出一種基于蟻群算法的數(shù)據(jù)融合算法.該算法根據(jù)路徑偏轉(zhuǎn)角調(diào)整節(jié)點(diǎn)選擇概率，改進(jìn)了信息素更新策略，采用新型策略指引螞蟻和數(shù)據(jù)有偏向性地進(jìn)行路徑搜素，并能有效適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和能量變化.經(jīng)實(shí)驗(yàn)仿真和分析發(fā)現(xiàn)，本文算法能夠有效延長(zhǎng)網(wǎng)絡(luò)的生命周期、降低節(jié)點(diǎn)能耗，并能改善網(wǎng)絡(luò)負(fù)載.

本文提出的基于WSN網(wǎng)絡(luò)的數(shù)據(jù)融合算法也存在一定的局限性，比如：節(jié)點(diǎn)選擇概率除了考慮路徑偏轉(zhuǎn)角，也需要考慮估計(jì)鏈路質(zhì)量、節(jié)點(diǎn)負(fù)載等因素；節(jié)點(diǎn)信息素更新的策略也需要進(jìn)一步優(yōu)化.這些問(wèn)題將在下一步研究中重點(diǎn)關(guān)注，提出更優(yōu)的解決方案.