基于ＭＭＡＳ的無線傳感器網絡數據融合算法

(西北工業大學， 西安 710072)



摘要：提出了一種基于MAX-MIN螞蟻系統（MMAS）無線傳感器網絡的數據融合算法。該算法采用定向擴散的機制進行興趣散布；利用MMAS算法構造一個最小Steiner樹，源節點的數據發送到構造好的最小Steiner樹上，經過融合后傳輸到sink節點，降低了網絡中傳輸的數據量。通過與Dijkstra算法比較，NS2仿真表明該算法降低了網絡能耗，增加了網絡生存時間。

關鍵詞：無線傳感器網絡；數據融合；最小Steiner樹；最大最小螞蟻系統算法

中圖分類號：TP212文獻標志碼：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引言

無線傳感器網絡（WSN）因其高可靠、易部署和易擴展等特點逐漸受到人們的重視，并迅速發展起來。與傳統的網絡相比，WSN中每個獨立節點的能量、監測范圍及可靠性是有限的。為了增強整個網絡所能獲得信息的魯棒性和準確性，在放置節點時必須使節點的監測范圍互相交疊。這樣節點所采集到的數據就存在一定的冗余性，網絡負載會隨之增加。因為處理數據所消耗的能量與傳送數據所消耗的能量相比要小得多，應對冗余數據進行網內處理，通過數據融合平衡網絡內部各節點的能量消耗，可以延長網絡的生存時間。數據融合技術是WSN研究中的重要部分^[1，2]。

WSN的數據融合可以看做是尋找覆蓋源節點和sink節點的最小Steiner樹問題。本文從節省網絡能量的角度，提出一種以數據為中心的路由協議：一種基于MAX-MIN螞蟻系統（MMAS）的數據融合算法。

1WSN中的數據融合問題

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

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

可見WSN中的數據融合實際上是尋找覆蓋源節點和sink節點的最小Steiner樹問題^[3]。

2MMAS算法

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

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

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

a）轉移概率。設在第m次迭代中從源節點vs發出的第i只螞蟻A(s)i的當前位置為vk，本次迭代中由前s-1個源節點發出的第i只螞蟻產生的部分樹為ts-1S(i)，由源節點出發的螞蟻A(s)i產生的部分樹枝為b(s)p。當vkt(s-1)S(i)時，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）

而當vk∈ts-1S(i)時：

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次迭代時鏈路(k，l)上信息素的量；α和β分別表示信息素τkl(m)和啟發信息ηkl的相對重要程度。ηkl表示節點vl對vk的啟發信息，一般取ηij=1/ω(k，l)，ω(k，l)表示節點vl到達vk的跳數。

b）信息素的更新規則。第m次迭代結束后，僅在最好的路徑進行信息素調整。當前循環中最優解的螞蟻按式（4）進行信息素更新：

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

其中：ρ為信息素揮發系數（0＜ρ＜1）；Lm表示當前循環中所找到的最優路徑長度；Q為螞蟻釋放的信息素量。

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

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

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

τkl(m)，otherwise （5）

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

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

3基于MMAS的WSN數據融合算法

WSN中源節點發送的數據對應于人工螞蟻。這樣，WSN中的數據融合問題可以視為已知sink節點，構建從源節點到達sink節點的最優路徑。約束條件是節點每一跳的通信距離必須在規定傳輸范圍內。基于MMAS的數據融合算法分為興趣報文散布、MST構造和數據傳輸三個階段來實現。

31興趣報文散布階段

對于WSN而言，源節點必須知道sink節點所需要的數據類型才能轉發相應的數據。因此本階段的主要任務就是sink節點向整個網絡散布興趣報文（interest message，IM）。本算法采用定向擴散的機制進行興趣散布，通過建立擴散梯度使每個節點明確數據傳播的方向，并且知道到達sink節點所需要的最小跳數。本階段之后，每個節點均可以知道sink節點所需要的數據類型。

32最小Steiner樹構造階段

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

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

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

｛for螞蟻i＝1 to I do

｛for源節點s＝1 to Sdo

｛把螞蟻A(s)i的當前位置k設為第s個源節點vs；同時把螞蟻A(s)i的當前樹枝b(s)p設為空表；

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

根據式（2）和（3），以概率Pk，l選擇后繼節點vl；把鏈路(k，l)加到當前樹枝b(s)p中，螞蟻A(s)i移到節點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)的費用ω(ts(i))}

記錄到目前為止找到的最優樹t*mS，根據式（4）進行信息素的更新；

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

go to b)｝

c)輸出。

d)程序結束。

33數據傳輸階段

當最小Steiner樹構造完以后，每個源節點都將探測到的數據轉發給最小Steiner樹上的節點。如果該節點僅有一個樹枝（子節點），便將數據直接轉發給它的上一級節點；如果該節點有多個樹枝（子節點），則直到其所有樹枝，都將數據轉發給它為止，然后該節點進行數據融合，再進行轉發到上一級節點這個過程一直持續到達sink節點為止。

4仿真實驗與分析

仿真基于CMU的NS2平臺。本文仿真實驗均基于同一實驗場景：節點隨機分布在200 m×200 m區域內，配置節點的傳輸范圍為R=20 m。仿真主要參數具體配置如表1所示。

表1仿真主要參數配置表

MAC協議IEEE 802.11

無線收發功率模型Two Ray Ground

節點發送/接收數據能耗0.660 W/0.395 W

節點初始能量10 J

天線類型OmniAntenna

算法參數權重I＝20，α＝1，β＝1.5，ρ＝0.4，Q＝10，NCmax＝20

仿真采用的數據融合模型分別是Dijkstra算法和本文提出的基于MMAS的數據融合算法（MMAS-Steiner）。算法性能主要從不同源節點下整個網絡消耗的能量與整個網絡生存時間兩個方面進行評估。

41網絡消耗能量分析

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

42網絡生存時間分析

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

5結束語

在WSN中，通過適當的數據融合算法可以實現網絡節能，延長整個網絡的生存時間。WSN的數據融合可以看做是尋找覆蓋源節點和sink節點的最小Steiner樹問題。本文提出了一種基于MMAS的無線傳感器網絡數據融合算法，采用定向擴散的機制進行興趣散布，通過MMAS算法構造一個最小Steiner樹，源節點的數據發送到構造好的最小Steiner樹上，經過融合后傳輸到sink節點，降低了網絡中傳輸的數據量，延長了整個網絡的生存時間。仿真實驗結果表明了本算法是可行和有效的。

參考文獻：

［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樹的蟻群優化算法及其收斂性[J].應用數學學報，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.