基于ＭＭＡＳ的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法

(西北工業(yè)大學(xué)， 西安 710072)



摘要：提出了一種基于MAX-MIN螞蟻系統(tǒng)（MMAS）無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)融合算法。該算法采用定向擴(kuò)散的機(jī)制進(jìn)行興趣散布；利用MMAS算法構(gòu)造一個最小Steiner樹，源節(jié)點(diǎn)的數(shù)據(jù)發(fā)送到構(gòu)造好的最小Steiner樹上，經(jīng)過融合后傳輸?shù)絪ink節(jié)點(diǎn)，降低了網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量。通過與Dijkstra算法比較，NS2仿真表明該算法降低了網(wǎng)絡(luò)能耗，增加了網(wǎng)絡(luò)生存時(shí)間。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；數(shù)據(jù)融合；最小Steiner樹；最大最小螞蟻系統(tǒng)算法

中圖分類號：TP212文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)11-3419-02



Data aggregation algorithm based on MMAS in wireless sensor networks



LI Zhi-yu

-|，SHI Hao-shan

(Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:This paper presented a data aggregation algorithm based on MAX-MIN ant system (MMAS) in WSN. In this algorithm，used directed diffusion (DD)to deliver interest， and used MMAS algorithm to construct a minimum Steiner tree.The data sent by source nodes was transmitted to the constructed minimum Steiner tree and then was retransmitted to the sink node after aggregation. Compared with Dijkstra algorithm， NS2 simulation results show that this algorithm can help reduce network energy consumption and prolong the life span of the network.

Key words:wireless sensor networks(WSN)；data aggregation；minimum Steiner tree；MMAS algorithm 

0引言

無線傳感器網(wǎng)絡(luò)（WSN）因其高可靠、易部署和易擴(kuò)展等特點(diǎn)逐漸受到人們的重視，并迅速發(fā)展起來。與傳統(tǒng)的網(wǎng)絡(luò)相比，WSN中每個獨(dú)立節(jié)點(diǎn)的能量、監(jiān)測范圍及可靠性是有限的。為了增強(qiáng)整個網(wǎng)絡(luò)所能獲得信息的魯棒性和準(zhǔn)確性，在放置節(jié)點(diǎn)時(shí)必須使節(jié)點(diǎn)的監(jiān)測范圍互相交疊。這樣節(jié)點(diǎn)所采集到的數(shù)據(jù)就存在一定的冗余性，網(wǎng)絡(luò)負(fù)載會隨之增加。因?yàn)樘幚頂?shù)據(jù)所消耗的能量與傳送數(shù)據(jù)所消耗的能量相比要小得多，應(yīng)對冗余數(shù)據(jù)進(jìn)行網(wǎng)內(nèi)處理，通過數(shù)據(jù)融合平衡網(wǎng)絡(luò)內(nèi)部各節(jié)點(diǎn)的能量消耗，可以延長網(wǎng)絡(luò)的生存時(shí)間。數(shù)據(jù)融合技術(shù)是WSN研究中的重要部分^[1，2]。

WSN的數(shù)據(jù)融合可以看做是尋找覆蓋源節(jié)點(diǎn)和sink節(jié)點(diǎn)的最小Steiner樹問題。本文從節(jié)省網(wǎng)絡(luò)能量的角度，提出一種以數(shù)據(jù)為中心的路由協(xié)議：一種基于MAX-MIN螞蟻系統(tǒng)（MMAS）的數(shù)據(jù)融合算法。

1WSN中的數(shù)據(jù)融合問題

由于WSN具有多源節(jié)點(diǎn)、少sink節(jié)點(diǎn)的特點(diǎn)，其路由問題就是尋找網(wǎng)絡(luò)中從覆蓋需要通信的源節(jié)點(diǎn)到sink節(jié)點(diǎn)的最優(yōu)路徑問題。假設(shè)用帶權(quán)重的連通圖G=G(V，E，ω)表示給定的WSN。其中：V代表網(wǎng)絡(luò)中節(jié)點(diǎn)的集合；E表示鏈路集合；ω:E→R+為E中每條鏈路賦予一個費(fèi)用值。對于網(wǎng)絡(luò)中的兩個節(jié)點(diǎn)vk、vl，僅當(dāng)vk和vl能夠進(jìn)行信息交換時(shí)，ekl=(k，l)∈E。由于能量和發(fā)射半徑的限制，并非任意兩個節(jié)點(diǎn)之間都可以進(jìn)行信息交換，通常每個節(jié)點(diǎn)只能與它附近的幾個節(jié)點(diǎn)進(jìn)行信息交換，可見G并不是完全圖。設(shè)SV是源節(jié)點(diǎn)的集合，d∈V是網(wǎng)絡(luò)中惟一的sink節(jié)點(diǎn)，這樣多源單匯路由問題可以看做在圖G中尋找一個包含S∪g0gggggg中所有節(jié)點(diǎn)的樹ts，使得樹的費(fèi)用最?。邯?/p>

ω(ts)=mine∈tsω(e)（1）

可見WSN中的數(shù)據(jù)融合實(shí)際上是尋找覆蓋源節(jié)點(diǎn)和sink節(jié)點(diǎn)的最小Steiner樹問題^[3]。

2MMAS算法

求最小Steiner樹的算法很多，目前典型的求解最小Steiner樹的算法包括DDMC (destination driven multicast)算法、DDSP(destination driven shortest path) 算法、SBPT(shortest best path tree)算法和ACO（ant colony optimization）算法等。基于算法在WSN中的實(shí)用性方面考慮，本文選擇了改進(jìn)的ACO算法-MMAS算法作為最小Steiner樹的構(gòu)造算法。

ACO算法是模擬自然界中螞蟻搜索食物行為的一種啟發(fā)式智能算法^[4]，最早成功地應(yīng)用于解決著名的旅行商問題(traveling salesman problem，TSP)。它采用分布式并行計(jì)算機(jī)制，具有較強(qiáng)的魯棒性。ACO算法描述如下：自然界中的螞蟻在搜索食物源時(shí)，能在其走過的路徑上釋放一種信息素，使得一定范圍內(nèi)的其他螞蟻能夠察覺并影響其行為；當(dāng)某些路徑上通過的螞蟻越多時(shí)，在路徑上留下的信息素?cái)?shù)量也越多，導(dǎo)致信息素強(qiáng)度增大，螞蟻選擇該路徑的概率隨之增加，從而進(jìn)一步增加該路徑的信息素強(qiáng)度；同時(shí)，信息素也會隨著時(shí)間的推移以一定的比例發(fā)生耗散，通過螞蟻較少的路徑上的信息素就會逐漸消失。ACO算法利用群體智能建立路徑選擇機(jī)制，很適合像WSN這樣有大量節(jié)點(diǎn)的網(wǎng)絡(luò)。但是ACO算法也存在一些局限性，如計(jì)算時(shí)間長、容易出現(xiàn)停滯現(xiàn)象等。

為了能更好地避免ACO算法出現(xiàn)過早停滯現(xiàn)象，本文采用MMAS算法構(gòu)造的最小Steiner樹。MMAS算法是在螞蟻系統(tǒng)算法的基礎(chǔ)上首次提出來的^[5]。其主要思想是：

a）轉(zhuǎn)移概率。設(shè)在第m次迭代中從源節(jié)點(diǎn)vs發(fā)出的第i只螞蟻A(s)i的當(dāng)前位置為vk，本次迭代中由前s-1個源節(jié)點(diǎn)發(fā)出的第i只螞蟻產(chǎn)生的部分樹為ts-1S(i)，由源節(jié)點(diǎn)出發(fā)的螞蟻A(s)i產(chǎn)生的部分樹枝為b(s)p。當(dāng)vkt(s-1)S(i)時(shí)，A(s)i選擇下一個位置vl的概率為

Pk，l(m，ts-1S(i))=[τkl(m)]α[ηkl]β/

{vrb(s)p，(k，r)∈E[τk，r(m)]α[ηkr]β}，vlb(s)p and(k，l)∈E

0，otherwise（2）

而當(dāng)vk∈ts-1S(i)時(shí)：

Pk，l(m，ts-1S(i))=1，vl is the next node to vk in ts-1S

0，otherwise（3）

其中：τkl(m)表示是第m次迭代時(shí)鏈路(k，l)上信息素的量；α和β分別表示信息素τkl(m)和啟發(fā)信息ηkl的相對重要程度。ηkl表示節(jié)點(diǎn)vl對vk的啟發(fā)信息，一般取ηij=1/ω(k，l)，ω(k，l)表示節(jié)點(diǎn)vl到達(dá)vk的跳數(shù)。

b）信息素的更新規(guī)則。第m次迭代結(jié)束后，僅在最好的路徑進(jìn)行信息素調(diào)整。當(dāng)前循環(huán)中最優(yōu)解的螞蟻按式（4）進(jìn)行信息素更新：

Δτkl(m+1)=ρτkl(m)+Q/Lm(4)

其中：ρ為信息素?fù)]發(fā)系數(shù)（0＜ρ＜1）；Lm表示當(dāng)前循環(huán)中所找到的最優(yōu)路徑長度；Q為螞蟻釋放的信息素量。

c）為了盡量避免搜索過早收斂于并非全局最優(yōu)路徑，將所有路徑上的信息素濃度限制在τkl∈[τmin，τmax]。在每一次循環(huán)后，令

τkl(m)=τmax，τkl(m)＞τmax

τmin，τkl(m)＜τmin

τkl(m)，otherwise （5）

從而避免了某條路徑信息量遠(yuǎn)大于其他路徑，使所有螞蟻都集中在這一條路徑上，使算法不再擴(kuò)散，不會去尋找更好的路徑，結(jié)果只得到局部最優(yōu)路徑的情況。在本算法中取τmax=1/ρ，τmin=τmax/20。

d）為了算法在初始階段搜索到更多的路徑，路徑上信息素的濃度在初始化時(shí)設(shè)置成τmax。

3基于MMAS的WSN數(shù)據(jù)融合算法

WSN中源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)對應(yīng)于人工螞蟻。這樣，WSN中的數(shù)據(jù)融合問題可以視為已知sink節(jié)點(diǎn)，構(gòu)建從源節(jié)點(diǎn)到達(dá)sink節(jié)點(diǎn)的最優(yōu)路徑。約束條件是節(jié)點(diǎn)每一跳的通信距離必須在規(guī)定傳輸范圍內(nèi)。基于MMAS的數(shù)據(jù)融合算法分為興趣報(bào)文散布、MST構(gòu)造和數(shù)據(jù)傳輸三個階段來實(shí)現(xiàn)。

31興趣報(bào)文散布階段

對于WSN而言，源節(jié)點(diǎn)必須知道sink節(jié)點(diǎn)所需要的數(shù)據(jù)類型才能轉(zhuǎn)發(fā)相應(yīng)的數(shù)據(jù)。因此本階段的主要任務(wù)就是sink節(jié)點(diǎn)向整個網(wǎng)絡(luò)散布興趣報(bào)文（interest message，IM）。本算法采用定向擴(kuò)散的機(jī)制進(jìn)行興趣散布，通過建立擴(kuò)散梯度使每個節(jié)點(diǎn)明確數(shù)據(jù)傳播的方向，并且知道到達(dá)sink節(jié)點(diǎn)所需要的最小跳數(shù)。本階段之后，每個節(jié)點(diǎn)均可以知道sink節(jié)點(diǎn)所需要的數(shù)據(jù)類型。

32最小Steiner樹構(gòu)造階段

本文采用MMAS算法構(gòu)造最小Steiner樹。設(shè)網(wǎng)絡(luò)中有n個節(jié)點(diǎn)，1個sink節(jié)點(diǎn)，S個源節(jié)點(diǎn)。在每個源節(jié)點(diǎn)vs上各放I只螞蟻。NC為迭代計(jì)數(shù)器，最大迭代次數(shù)為NCmax。在每次迭代中，按順序依次從各個源節(jié)點(diǎn)放出一只螞蟻，直到放完I只螞蟻為止，此時(shí)能產(chǎn)生I棵樹；然后進(jìn)行信息素的更新，進(jìn)入下一次迭代。利用MMAS構(gòu)造最小Steiner樹的算法如下：

a)初始化。置NC＝0；對所有的(k，l)∈E，置τkl(l)=τmax，Δτkl(l)=0；每個源節(jié)點(diǎn)vs上各放I只螞蟻。

b)for迭代次數(shù)m＝1 to NCmaxdo

｛for螞蟻i＝1 to I do

｛for源節(jié)點(diǎn)s＝1 to Sdo

｛把螞蟻A(s)i的當(dāng)前位置k設(shè)為第s個源節(jié)點(diǎn)vs；同時(shí)把螞蟻A(s)i的當(dāng)前樹枝b(s)p設(shè)為空表；

while((k，l)∈E，k≠l){

根據(jù)式（2）和（3），以概率Pk，l選擇后繼節(jié)點(diǎn)vl；把鏈路(k，l)加到當(dāng)前樹枝b(s)p中，螞蟻A(s)i移到節(jié)點(diǎn)vl，并且令k=l；

NC＝NC+1｝

if(τkl (m)＞τmax)τkl(m)=τmax； 

if(τkl (m)＜τmin)τkl(m)=τmin； 

更新ts-1S(i)=ts-1S∪bs;}

記錄樹ts(i)的費(fèi)用ω(ts(i))}

記錄到目前為止找到的最優(yōu)樹t*mS，根據(jù)式（4）進(jìn)行信息素的更新；

if（NC＜ NCmax）and（不是所有螞蟻選擇同一條路徑） 

go to b)｝

c)輸出。

d)程序結(jié)束。

33數(shù)據(jù)傳輸階段

當(dāng)最小Steiner樹構(gòu)造完以后，每個源節(jié)點(diǎn)都將探測到的數(shù)據(jù)轉(zhuǎn)發(fā)給最小Steiner樹上的節(jié)點(diǎn)。如果該節(jié)點(diǎn)僅有一個樹枝（子節(jié)點(diǎn)），便將數(shù)據(jù)直接轉(zhuǎn)發(fā)給它的上一級節(jié)點(diǎn)；如果該節(jié)點(diǎn)有多個樹枝（子節(jié)點(diǎn)），則直到其所有樹枝，都將數(shù)據(jù)轉(zhuǎn)發(fā)給它為止，然后該節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合，再進(jìn)行轉(zhuǎn)發(fā)到上一級節(jié)點(diǎn)這個過程一直持續(xù)到達(dá)sink節(jié)點(diǎn)為止。

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

仿真基于CMU的NS2平臺。本文仿真實(shí)驗(yàn)均基于同一實(shí)驗(yàn)場景：節(jié)點(diǎn)隨機(jī)分布在200 m×200 m區(qū)域內(nèi)，配置節(jié)點(diǎn)的傳輸范圍為R=20 m。仿真主要參數(shù)具體配置如表1所示。

表1仿真主要參數(shù)配置表

MAC協(xié)議IEEE 802.11

無線收發(fā)功率模型Two Ray Ground

節(jié)點(diǎn)發(fā)送/接收數(shù)據(jù)能耗0.660 W/0.395 W

節(jié)點(diǎn)初始能量10 J

天線類型OmniAntenna

算法參數(shù)權(quán)重I＝20，α＝1，β＝1.5，ρ＝0.4，Q＝10，NCmax＝20

仿真采用的數(shù)據(jù)融合模型分別是Dijkstra算法和本文提出的基于MMAS的數(shù)據(jù)融合算法（MMAS-Steiner）。算法性能主要從不同源節(jié)點(diǎn)下整個網(wǎng)絡(luò)消耗的能量與整個網(wǎng)絡(luò)生存時(shí)間兩個方面進(jìn)行評估。

41網(wǎng)絡(luò)消耗能量分析

設(shè)置網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目N為100，sink節(jié)點(diǎn)數(shù)目為1（位置固定），源節(jié)點(diǎn)數(shù)目為2、4、6、8、10，網(wǎng)絡(luò)運(yùn)行時(shí)間為100 s。在兩種算法模式下，整個網(wǎng)絡(luò)消耗的能量隨源節(jié)點(diǎn)數(shù)目的變化趨勢如圖1所示。從圖中可以看出，在相同的仿真場景下，在MMAS中，整個網(wǎng)絡(luò)消耗的能量低于在Dijkstra算法下整個網(wǎng)絡(luò)消耗的能量，并且隨著源節(jié)點(diǎn)數(shù)目的增加，采用MMAS-Steiner的優(yōu)越性越明顯。這是因?yàn)樵贛MAS-Steiner中，通過構(gòu)造數(shù)據(jù)融合樹，大大減少網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量，降低了網(wǎng)絡(luò)中的能量消耗。

42網(wǎng)絡(luò)生存時(shí)間分析

設(shè)置網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目N為100，源節(jié)點(diǎn)數(shù)目為6。網(wǎng)絡(luò)的生存時(shí)間可以用節(jié)點(diǎn)平均剩余能量來表示。節(jié)點(diǎn)平均剩余能量越大，整個網(wǎng)絡(luò)的生存時(shí)間就越長。在兩種算法模式下，節(jié)點(diǎn)平均剩余能量隨時(shí)間變化趨勢如圖2所示。從圖中可以看出，在相同的仿真場景下，在MMAS-Steiner中，整個節(jié)點(diǎn)平均剩余能量高于在Dijkstra算法下節(jié)點(diǎn)平均剩余能量。通過計(jì)算可以得出，采用MMAS-Steiner可以使網(wǎng)絡(luò)節(jié)點(diǎn)的平均能耗節(jié)約20％左右，從而延長了網(wǎng)絡(luò)的生存時(shí)間。

5結(jié)束語

在WSN中，通過適當(dāng)?shù)臄?shù)據(jù)融合算法可以實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)能，延長整個網(wǎng)絡(luò)的生存時(shí)間。WSN的數(shù)據(jù)融合可以看做是尋找覆蓋源節(jié)點(diǎn)和sink節(jié)點(diǎn)的最小Steiner樹問題。本文提出了一種基于MMAS的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法，采用定向擴(kuò)散的機(jī)制進(jìn)行興趣散布，通過MMAS算法構(gòu)造一個最小Steiner樹，源節(jié)點(diǎn)的數(shù)據(jù)發(fā)送到構(gòu)造好的最小Steiner樹上，經(jīng)過融合后傳輸?shù)絪ink節(jié)點(diǎn)，降低了網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量，延長了整個網(wǎng)絡(luò)的生存時(shí)間。仿真實(shí)驗(yàn)結(jié)果表明了本算法是可行和有效的。

參考文獻(xiàn)：

［1］

LI Zhi-yu，SHI Hao-shan.Design of gradient and node remaining energy constrained directed diffusion routing for WSN[C]//Proc of the 3th International Conference on Wireless Communications， Networking and Mobile Computing.2007:2600-2603.

[2]BOULIS A，GANERIWAL S，SRIVASTAVA M B.Aggregation in sensor networks: an energy-accuracy trade-off[J].Elsevier Journal of Ad hoc Networks，2003，1(1):317-331.

[3]楊文國，郭田德.求最小Steiner樹的蟻群優(yōu)化算法及其收斂性[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，2006，20(2):352-361.

[4]DORIGO M，GAMBARDELLAL M.Ant colony systems:a cooperative learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1(1):53-66.

[5]STUTZLE T，HOOS H.Improvements on the ant system:introducing MAX-MIN ant system[C]//Proc of International Conference on Artificial Neural Networks and Genetic Algorithms.1997:245-249.