改進的無線傳感器網絡非均勻分簇路由算法*

張文梅,廖福保

(1.廣東農工商職業技術學院機電系,廣州 510507;2.廣東農工商職業技術學院計算機系,廣州 510507)

?

改進的無線傳感器網絡非均勻分簇路由算法*

張文梅1,廖福保2*

(1.廣東農工商職業技術學院機電系,廣州 510507;2.廣東農工商職業技術學院計算機系,廣州 510507)

針對無線傳感器網絡中不均勻分簇引起能量空洞的問題,提出了改進的無線傳感器網絡非均勻分簇路由算法。該算法先根據節點剩余能量、節點到基站的距離、節點“度”和節點到簇頭的距離等因素選舉簇頭;沒有成為簇頭的節點選擇加入到距離最近的簇頭所在的簇中,從而將整個網絡劃分為大小不等的簇;然后簇頭再根據簇頭剩余能量、簇頭到基站的距離構造基于最小生成樹的最優傳輸路徑;通過簇內節點單跳、樹內簇頭多跳通信的方式將數據最終傳輸到基站。仿真結果表明,該路由算法能有效節約能量和均衡節點能耗,從而延長網絡的生命周期。

無線傳感器網絡;能量均衡;非均勻分簇;最小生成樹

無線傳感器網絡通常包括了大量的傳感器節點和用于收集和發送數據的基站組成,這些傳感器節點采集監控區域的數據,通過自組網方式將采集到的數據上傳給基站。由于傳感器節點大多采用電池供電,很難對傳感器節點進行能量補充,因此設計能量高效的路由算法是WSN研究的熱點[1-2]。

LEACH[3]為最早提出的分簇路由算法,它能有效降低能耗并提高網絡生命周期,但簇頭到基站通過單跳方式傳輸會使距離基站遠的簇頭消耗過多能量。研究表明在簇頭到基站間采用多跳方式傳輸更節約能量[4],然而距離基站近的簇頭需要轉發其他簇頭的數據,必然造成離基站近的簇頭消耗過快,導致能耗不均衡。針對近基站簇頭能耗過大造成能耗不平衡的問題,文獻[5]提出的EEUC算法、文獻[6]提出的DEBUC算法均采用非均勻分簇,能有效均衡能量消耗,延長網絡生命周期,但其簇頭選擇采用概率和門限值來決定,不能保證所選擇的簇頭最優。文獻[7]提出EBUCA算法利用剩余能量和節點密度設置簇頭選擇閾值,并根據簇頭密度及與基站的距離構建非均勻的簇半徑,達到均衡節點能耗的目的;文獻[8]提出冗余簇頭并減少簇頭選擇的次數來延長網絡生命周期;文獻[9]對簇頭選擇與簇頭更換提出了改進措施,能提高網絡性能,但其簇頭更換僅在簇內進行也會造成能耗不均衡。

文獻[10]在非均勻分簇的基礎上,簇頭路由中采用蟻群算法進行優化,能延長網絡生命周期,但并沒有考慮鏈路質量,可能造成局部路徑最優。文獻[11-12]在非均勻分簇的基礎上,簇頭路由構造最小生成樹,在構造樹時只考慮了傳輸能耗以及簇頭的剩余能量或只考慮了與基站的距離。

本文綜合以上問題,提出了改進的非均勻分簇路由算法。算法在簇頭選擇時綜合考慮節點剩余能量、節點“度”、簇內節點與簇頭的距離、節點到基站的距離等因素,將整個網絡劃分為不均勻的簇,簇內節點通過單跳方式將數據發送給簇頭;然后簇頭與基站之間根據簇頭剩余能量以及與基站的距離構造以基站為根節點的最小生成樹,簇頭通過最小生成樹組織的路由以多跳方式將數據傳送給基站。該算法能很好地均衡節點能耗,達到有效延長網絡生命周期的目的。

1 相關模型

1.1 網絡模型

為便于研究,本文假設傳感器網絡具有如下性質:①節點部署后不再移動且能量有限,基站位置固定而能量不受限;②每個節點具有相同的初始能量,且有相同的通信和數據處理能力,可自由調整發射功率;③每個節點具有唯一的標識,用Si表示第i各節點,則節點集合S={S1,S2,…,Sn};④節點可以根據接收到的信號強度RSSI來計算發出者到自己的近似距離;⑤基站能夠和所有節點進行通信。

1.2 能量模型

由于無線傳感器網絡中節點進行數據傳輸時所耗的能量遠大于其他的能耗[13]。本文采用文獻[3]中的無線通信能耗模型,發送數據時其能耗公式如下:

(1)

節點接收k比特數據的能耗為:

ERx(k)=kEelec

(2)

為簡化問題,假定通信均采用自由空間模型,簇頭j內的節點數為n,則簇內成員節點i發送k比特數據到簇頭j所消耗的能量為

(3)

式中:dij為成員節點i與簇頭j之間的距離。

簇頭j所消耗的能量包括接收簇內n個節點數據所耗能量、發送這些數據所耗的能量、接收和轉發來自其他m個簇頭數據所耗的能量,其公式如下(為方便研究,假如每個簇內均有n個節點數據):

Ej=(m+1)n[ETx(k,d)+ERx(k)]=

(m+1)nk(2Eelec+εfsd2)

(4)

式中:d為簇頭到下一跳的距離。

由式(3)、式(4)可知,簇頭的能耗由簇內節點數n、要轉發的數據量k以及簇內節點與簇頭的距離dij以及到下一跳的距離d決定的,因此優化簇頭選擇和數據傳輸路徑能有效降低能耗。

2 改進的無線傳感器網絡非均勻分簇路由算法

類似于LEACH,本算法采用“輪”方式運行,每輪分為簇建立階段和數據傳輸階段。在簇建立階段選擇綜合考慮剩余能量、節點與基站的距離、節點的“度”以及簇內節點與簇頭距離等因素,采用時序的方式選擇簇頭。在數據傳輸階段,根據簇頭剩余能量及簇頭與基站間的距離建立基于最小生成樹的最優傳輸路徑。

2.1 概念描述

為便于描述,對本文所涉及的概念說明如下:

①競選半徑。節點競選簇頭時的半徑,本文采用文獻[5]的公式計算競選半徑。

(5)

②鄰居節點。節點Si和Sj互為鄰居節點滿足

dij

(6)

式中:dij節點i和節點j之間的距離。

③鄰居表。每個節點保存一個鄰居節點表以存儲鄰居節點的相關信息,如表1所示。

表1 節點的鄰居表內容

④平均剩余能量Eavg。節點根據鄰居表中鄰居節點的剩余能量計算出平均剩余能量。

(7)

⑤平均距離davg。節點根據鄰居表中鄰居節點與該節點的距離計算出平均距離。

(8)

⑥簇頭競爭時間t。從節點收到基站通知簇頭競爭到本節點發出簇頭競爭消息的等待時間。

(9)

式中:α為[0.9,1]之間的隨機數,T為規定的簇頭競爭持續時間,ei為節點剩余能量,β、γ為距離調節因子。從式中可以看出,簇頭競爭時間t由節點剩余能量、到基站的距離以及鄰居節點與該節點的距離決定,剩余能量越低、到基站越遠、鄰居節點平均距離越大,t的取值就越大。

2.2 簇頭選舉

在無線傳感器網絡分簇算法中,簇頭選舉對有效管理網絡能耗至關重要。文獻[5-7]均證明了非均勻分簇能有效均衡簇頭能耗,緩解能量空洞。本文在非均勻分簇的基礎上建立了本文的簇頭選舉算法,網絡中所有節點都參與簇頭競爭,采用時序的方式選擇簇頭。

簇頭選擇的算法步驟:

第1步 基站向全網廣播一個分簇信號PAR_MSG,所有節點根據接收到的信號強度計算其到基站的距離Di,然后根據式(5)確定其競爭半徑Ri。

第2步 各節點競選半徑Ri/2范圍內廣播競選消息Comp_MSG,該消息包括節點的ID、剩余能量ei。

第3步 各節點收到來自另外節點的競選消息Comp_MSG,根據接收到的信號強度計算兩節點間的距離d,再根據式(6)將滿足條件的節點加入到鄰居節點表中。

第4步 各節點根據鄰居節點表中的信息,按照式(7)、式(8)分別計算出平均剩余能量Eavg和平均距離davg。節點再根據式(9)計算出自身的簇頭競爭時間t。

第5步 基站廣播簇頭選舉信號Sel_MSG,以同步各節點的時間。

第6步 節點接收到Sel_MSG信號后,啟動自身時鐘開始計時并監聽其他節點信號。

第7步 若節點i在本身的簇頭競爭時間t到來前收到鄰居表中其他節點的簇頭宣告成功的消息SUC_MSG,節點i廣播競選失敗的消息FAI_MSG,退出簇頭競選。

第8步 若節點i收到鄰居表其他節點的FAI_MSG消息,就把這個節點從鄰居表中刪除。

第9步 若節點i在本身的簇頭競爭時間t到之后還沒有收到鄰居表中其他節點的SUC_MSG消息,則該節點在競選半徑內廣播SUC_MSG消息成為簇頭。

第10步 選舉結束后,沒有成為簇頭的節點選擇加入到鄰居表中距離最近的簇頭所在的簇中。離簇頭越近,簇內通信可以節省能量。

第11步 分簇完成后,各個簇頭在競選半徑范圍內廣播簇頭消息CLU_MSG,并收集其他簇頭廣播的消息,為后續路由做準備。CLU_MSG信息包括簇頭ID、剩余能量。

算法中將整個網絡劃分為大小不等的簇,靠近基站的簇半徑小,有利于均衡能耗;簇頭競爭時間考慮了剩余能量、到基站距離以及簇內節點到簇頭的平均距離等因素,能夠保證選舉的簇頭綜合性能最優。

2.3 簇間路由

分簇及簇頭選舉結束后,簇間通信采用多跳路由,以基站為樹根,簇間路由采用最小生成樹方式來組織。先將每個簇抽象為一個點,用邊把相鄰的簇連接起來,構造一個帶權的連通圖G=(V,E)表示無線傳感器網絡,其中V是點集(包括所有簇頭和基站的集合),E為邊集。

發送和接收同樣長度的數據,通信能耗由節點間距離決定,因此權值計算時綜合考慮簇頭間距離和簇頭剩余能量,權值計算如式(10)所示:

(10)

式中:wij為簇頭i、j的邊的權值,dij簇頭i、j之間的距離,ei、ei為簇頭i、j的剩余能量,ρ為可變參數,不能相互接收信息的兩個簇頭的邊的權值w設為無窮大。從式中可以看出,權值由簇頭間距離和簇頭的剩余能量決定,剩余能量越低、簇頭間距離越遠,wij的取值就越大,則簇頭要負責數據轉發的概率降低,從而節省自身能量,延長生命周期,達到整個網絡能量均衡。

根據簇頭選擇過程中計算得到的簇頭到基站的距離Di以及相鄰簇頭的廣播信息CLU_MSG,簇間路由利用Prim構造最小生成樹的具體算法步驟:

第1步 各簇頭根據本身到基站的距離Di及剩余能量ei,計算Di/ei的值,若Di/ei值小于h(h為常量)的簇頭集合為C={C1,C2,…},集合C中的簇頭可以直接將數據傳輸給基站。

第2步 在有向連接圖G=(V,E)中,將集合C中的簇頭節點和基站加入到集合U中,將集合C中的簇頭到基站的邊加入到集合T中。

第3步 各簇頭根據接收到的CLU_MSG信息,依照接收到的信號強度計算兩節點間的距離d,再依據式(10)計算出簇頭間每條邊的權值w(不包括集合C中簇頭到基站的邊)。

第4步 從所有u∈U,v∈V-U的邊中選擇權值wuv最小的邊,將簇頭v加入到U中,將邊(u,v)加入到集合T中。

第5步 重復執行第4步,直到U=V為止。此時集合T中的所有邊就構造了一棵最小生成樹。

第6步 依據已確定的最小生成樹的結構,節點調整傳輸功率,調整為能夠到達其最小生成樹的所有一跳鄰居,從而節省能量。

當節點數據到達簇頭時,簇頭根據以上生成的最小生成樹,以多跳方式將數據傳輸到基站。

2.4 算法分析

假定無線傳感器網絡中共有個N節點,產生了M個簇頭,則算法時間復雜度為O(N2)。

證明 成簇開始時,基站廣播PAR_MSG信息,各節點計算競選半徑,時間復雜度為O(N);每個節點計算節點間距離并加入到對應鄰居表中,時間復雜度為O(N2);每個節點計算自身的簇頭競爭時間,時間復雜度為O(N2);基站廣播簇頭選舉信號Sel_MSG,各節點啟動時鐘計時,時間復雜度為O(N);各節點計時開始根據簇頭競爭時間來進行簇頭選舉,時間復雜度為O(N2)。因此非均勻分簇及簇頭選舉的成簇算法時間復雜度為O(N+N2+N2+N+N2),即O(N2)。

簇間路由中,算法開始時構造帶權的連通圖的時間復雜度為O(M2);各簇頭計算Di/ei值的時間復雜度為O(M);計算簇頭間距離和權值w的時間復雜度為O(M2);依照權值w構造最小生成樹的時間復雜度為O(M2)。因此簇間路由算法的時間復雜度為O(M2+M+M2+M2),即O(M2)。

根據以上分析,因為N?M,因此整個算法的時間復雜度為O(N2)。

3 實驗仿真

采用OPNET仿真軟件對本文算法、EEUC協議和EBUCA協議進行比較仿真模擬。實驗仿真參數如表2所示,傳感器節點隨機分布,簇點融合數據的能量忽略不計。為了比較,本實驗相關參數與文獻[5]的相同,取c=0.5,而ρ=0.5。圖1為存活節點數隨運行輪數的變化情況,圖2為剩余總能量隨運行輪數的變化情況。

表2 實驗仿真參數表

圖1 生命周期對比

圖2 剩余總能量對比

由圖1可以看出,本文算法從第1個節點失效到最后一個節點死亡的時間都比EEUC和EBUCA算法滯后,這說明本文算法能夠很好的均衡網絡能耗從而延長網絡生命周期。不管是以首個節點死亡時間還是以最后一個節點死亡時間作為判斷標準,本文算法都更優。

圖2對比了3種算法每輪過后的剩余總能量,可以看出本文算法具有較小的坡度,波動較小且生存時間更長,表明本文算法相對于EEUC和EBUCA算法能耗速度較慢且能耗較 小,更能有效地節約能量。

4 結語

本文對已有的無線傳感器網絡路由算法及其存在的問題,借鑒非均勻分簇的思想,提出了改進的無線傳感器網絡非均勻分簇路由算法。改進的算法在簇頭選擇階段綜合考慮剩余能量、節點到簇頭的距離、節點“度”以及節點到基站距離等因素,通過時序方式選擇簇頭;在數據傳輸階段,綜合考慮剩余能量和簇頭到基站距離建立最小生成樹,通過多跳方式進行數據傳輸。實驗結果表明,本文算法可以延長節點的死亡時間,有效均衡網絡能耗,從而延長網絡生命周期。

[1] 李亞男,徐夫田,陳金鑫. 基于LEACH的WSNs分簇優化策略[J]. 傳感技術學報,2014,27(5):670-674.

[2]李建洲,王海濤,陶安. 一種能耗均衡的WSN分簇路由協議[J]. 傳感技術軟件學報,2013,26(3):396-401.

[3]Heinzelman W,Chandrakasan A,Balakrishnam H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc of the 33rd Conf on System Sciences.Piscataway. NJ:IEEE.2000:3005-3014.

[4]Mhatre V,Rosenberg C. Design Guidelines for Wireless Sensor Networks:Commnunication,Clustering and Aggregation[J]. Ad Hoc Networks,2004,2(1):45-63.

[5]李成法,陳貴海,葉懋,等. 一種基于非均勻分簇的無線傳感器網絡路由協議[J]. 計算機學報,2007,30(1):27-36.

[6]蔣暢江,石為人,唐賢倫,等. 能量均衡的無線傳感器網絡非均勻分簇路由協議[J]. 軟件學報,2012,23(5):1222-1232.

[7]盧先順,王瑩瑩,王洪斌,等. 無線傳感器網絡能量均衡的非均勻分簇算法[J]. 計算機科學,2013,40(5):78-81.

[8]馮冬芹,李光輝,全劍敏,等. 基于簇頭冗余的無線傳感器網絡可靠性研究[J]. 浙江大學學報:工學版,2009,43(5):849-854.

[9]姚光順,溫衛敏,張永定,等. 改進的無線傳感器網絡簇首選擇策略及其路由算法[J]. 計算機應用,2013,33(4):908-911,915.

[10]張榮博,曹建福. 利用蟻群優化的非均勻分簇無線傳感器網絡路由算法[J]. 西安交通大學學報,2010,44(6):33-38.

[11]陸晶,馬悅,吳曉軍. 一種基于最小生成樹的非均勻分簇路由算法[J]. 小型微型計算機系統,2012,33(10):2293-2296.

[12]鄒杰,史長瓊,姬文燕. 基于粒子群優化的非均勻分簇路由算法[J]. 計算機應用,2012,32(1):131-133.

[13]Estrin D. Wireless Sensor Networks Tutorial Part Ⅳ:Sensor Network Protocols[C]//Proc of the ACM Mobil Computing and Networking. New York:ACM,2002.1-5.

Improved Uneven Clustering Routing Algorithm for Wireless Sensor Networks*

ZHANGWenmei1,LIAOFubao2*

(1.Department of Mechanics and Electronics,Guang Dong AIB Polytechnic College,Guangzhou 510507,China;2.Department of Computer,Guang Dong AIB Polytechnic College,Guangzhou 510507,China)

In order to solve the problem of energy hole in wireless sensor networks caused by uneven clustering protocol,an improved uneven clustering routing algorithm is proposed. In the cluster heads selection stage,the algorithm selects the cluster heads based on several factors,including the residual energy of node,the distance between node and base station,the "degree" of the node,and the distance between node and cluster head. Other nodes that can’t be cluster heads select to join the cluster nearest to complete the process of clustering and the network is divided into clusters with different size. In the stage of data transmission,the algorithm constructs the optimal transmission path based on minimum spanning tree,according to the residual energy of cluster heads,and the distance between cluster heads and base station as well. The ordinary nodes of a cluster sends the data to cluster head through a single jump,and cluster heads send the data to base station through the nodes of the tree by the more jumping communication. The simulation shows that the routing algorithm can efficiently reduce and balance the energy consumption,and prolong the wireless sensor network survival period.

wireless sensor networks;energy balance;uneven clustering;minimum spanning tree

張文梅(1978-),女,碩士,副教授,研究方向為計算機應用、物聯網,zwm200718@126.com;

廖福保(1976-),男,碩士,副教授,研究方向為計算機應用、無線傳感器網絡與路由,fbliao2000@163.com。

項目來源:科技部國家星火計劃項目(2013GA780003)

2014-11-28 修改日期:2015-01-26

C:6150P

10.3969/j.issn.1004-1699.2015.05.021

TP3931

A

1004-1699(2015)05-0739-05