肖 瑋，涂亞慶

(后勤工程學(xué)院 后勤信息與軍事物流工程系,重慶 401311)

基于等級的無線傳感網(wǎng)自適應(yīng)分簇算法

肖 瑋*，涂亞慶

(后勤工程學(xué)院 后勤信息與軍事物流工程系,重慶 401311)

(*通信作者電子郵箱wzwry@163.com)

為解決現(xiàn)有無線傳感器網(wǎng)絡(luò)(WSN)分簇算法難以同時兼顧其異構(gòu)性和移動性，從而引發(fā)網(wǎng)絡(luò)壽命較短、網(wǎng)絡(luò)數(shù)據(jù)吞吐量較低等問題，提出了基于節(jié)點等級的自適應(yīng)分簇算法。該算法按輪運行，每輪分為自適應(yīng)分簇、簇建立、數(shù)據(jù)傳輸三個階段。為解決節(jié)點移動性引發(fā)的簇首數(shù)目和成簇規(guī)模不合理的問題，在自適應(yīng)分簇階段，根據(jù)子區(qū)域內(nèi)節(jié)點數(shù)目變化對相應(yīng)子區(qū)域進行細化或就近合并，以確保每個子區(qū)域內(nèi)節(jié)點數(shù)目在合理范圍內(nèi)。在簇建立階段，選舉簇內(nèi)等級最高的節(jié)點為簇首，解決異構(gòu)性引發(fā)的部分節(jié)點能耗過快、網(wǎng)絡(luò)壽命縮短的問題；節(jié)點等級除考慮節(jié)點剩余能量外，還結(jié)合WSN實際應(yīng)用，由節(jié)點剩余能量、能量消耗速率、到基站的距離、到簇內(nèi)其他節(jié)點的距離綜合決定?；贠MNeT++和Matlab 的仿真實驗結(jié)果表明，在節(jié)點移動速度為0～0.6 m/s的能量異構(gòu)WSN環(huán)境下，較移動低功耗自適應(yīng)集簇分層(LEACH-Mobile)算法和分布式能量有效分簇(DEEC)算法，運用所提算法分簇的WSN壽命延長了30.9%以上，網(wǎng)絡(luò)數(shù)據(jù)吞吐量是其他兩種算法分簇的網(wǎng)絡(luò)的1.15倍以上。

自適應(yīng)分簇；等級；無線傳感器網(wǎng)絡(luò)；能量異構(gòu)；移動性

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)是由大量的靜止或移動的傳感器以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò)，以協(xié)作地感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)被感知對象的信息，并最終把這些信息發(fā)送給網(wǎng)絡(luò)所有者，廣泛應(yīng)用于軍事、航空、防爆、救災(zāi)、環(huán)境、醫(yī)療、保健、家居、工業(yè)、商業(yè)等諸多領(lǐng)域[1-2]。由于WSN中節(jié)點體積小、攜帶能量有限，因此如何利用節(jié)點有限的能量延長網(wǎng)絡(luò)壽命，增大網(wǎng)絡(luò)數(shù)據(jù)吞吐量一直是WSN亟需解決的問題之一。相關(guān)研究表明，分簇技術(shù)能均衡節(jié)點能量消耗，延長節(jié)點存活時間，是降低節(jié)點能耗和延長網(wǎng)絡(luò)壽命的一種有效途徑。經(jīng)過數(shù)十年快速穩(wěn)健發(fā)展，WSN分簇技術(shù)取得了較為豐碩的成果[3-6]。比較經(jīng)典的是層次路由協(xié)議，典型代表是文獻[5]提出的低功耗自適應(yīng)集簇分層(Low Energy Adaptive Clustering Hierarchy, LEACH)協(xié)議。該協(xié)議通過隨機選舉簇首，平均分擔能量負載，延長了網(wǎng)絡(luò)生命周期。但存在簇首分布隨機、節(jié)點能量利用率不高的問題。文獻[6]在其基礎(chǔ)上進行改進，提出了傳感器信息系統(tǒng)的高效采集(Power-Efficient Gathering in Sensor Information System, PEGASIS)協(xié)議，該協(xié)議通過在網(wǎng)絡(luò)中只形成一個簇，稱為“鏈”，有效避免了LEACH協(xié)議頻繁選舉簇首帶來的通信開銷，減少了數(shù)據(jù)傳輸次數(shù)和通信量；但如果鏈過長，延遲更嚴重。

在WSN中，傳感器節(jié)點能量異構(gòu)的現(xiàn)象普遍存在。因為在布置網(wǎng)絡(luò)時傳感器節(jié)點可能會配置不同的初始能量；此外，在具體工作過程中，每個節(jié)點的能量消耗不同也會導(dǎo)致網(wǎng)絡(luò)中出現(xiàn)能量異構(gòu)現(xiàn)象。目前，針對能量異構(gòu)WSN的分簇算法主要有如下幾種：針對二級能量異構(gòu)網(wǎng)絡(luò)設(shè)計的可靠選舉協(xié)議(Stable Election Protocol, SEP)[7]，該協(xié)議將節(jié)點分為高能量和低能量兩種，并為兩種不同節(jié)點設(shè)置不同的當選簇頭的門限。針對三級異構(gòu)網(wǎng)絡(luò)，文獻[8]對集中能量高效分簇(Centralized Energy Efficient Clustering, CEEC)算法進行改進，提出了兩種新算法，主要綜合考慮初始能量、剩余能量、區(qū)域標識和到基站的距離選擇簇首。文獻[9]提出了適用于多級能量異構(gòu)網(wǎng)絡(luò)設(shè)計的分布式能量有效成簇算法(Distributed Energy-Efficient Clustering algorithm, DEEC)，其核心思想是讓剩余能量高的節(jié)點有更大的概率當選簇首節(jié)點，通過動態(tài)調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)充分利用網(wǎng)絡(luò)能量。文獻[10]提出一種能量敏感的非均勻分簇(Energy Aware Distributed Unequal Clustering, EADUC)協(xié)議，該協(xié)議主要以鄰居節(jié)點個數(shù)、基站位置和剩余能量為主要指標來選擇簇首，用以解決異構(gòu)網(wǎng)絡(luò)中的能量空洞問題。

此外，WSN應(yīng)大量應(yīng)用于節(jié)點移動領(lǐng)域[11-13]。由于節(jié)點移動造成網(wǎng)絡(luò)拓撲變化，針對靜止WSN的大部分路由算法并不能很好地適用于移動WSN，因此針對移動WSN，大量專門的路由算法應(yīng)運而生。例如，文獻[11]提出的移動LEACH(LEACH-Mobile, LEACH-Mobile)算法沿用LEACH按輪進行，當節(jié)點因移動遠離原簇首而更靠近新的簇首時，建立一種機制幫助其判斷是否換簇首。簇建立之后，簇首維護一個成員節(jié)點列表，簇首向各個成員節(jié)點發(fā)送請求數(shù)據(jù)消息，簇首與成員節(jié)點根據(jù)該消息機制來維護簇的動態(tài)結(jié)構(gòu)。但實驗表明 LEACH-Mobile算法在簇首輪換選舉前，存在大量丟失數(shù)據(jù)包的情況。文獻[12-13]提出分布式安全加權(quán)的系列分簇算法，通過綜合五大標準來確定簇首，并檢測和剔除惡性節(jié)點。

近年來隨著對物聯(lián)網(wǎng)(Internet of Things, IOT)研究的興起，對作為物聯(lián)網(wǎng)感知層的WSN的研究顯得尤為基礎(chǔ)和重要[14]。由于物聯(lián)網(wǎng)的移動性和能量異構(gòu)性十分顯著，使得WSN的應(yīng)用拓展到諸多移動性和能量異構(gòu)性顯著的領(lǐng)域，如軍隊集團作戰(zhàn)、部隊后勤保障、反恐抗災(zāi)行動等[15-16]。但現(xiàn)有分簇技術(shù)難以同時應(yīng)對具有能量異構(gòu)和移動性的無線傳感器網(wǎng)絡(luò)。這些算法或僅考慮無線傳感器移動性，如LEACH-Mobile算法；或僅考慮網(wǎng)絡(luò)異構(gòu)性，如DEEC算法和僅適用于二級異構(gòu)網(wǎng)絡(luò)的SEP算法，和三級異構(gòu)網(wǎng)絡(luò)的CEEC算法；鮮見同時兼顧移動性和異構(gòu)性的分簇算法。此外，LEACH及其改進算法Q-LEACH[17]、門限敏感能量高效(Threshold sensitive Energy Efficient sensor Network, TEEN)算法[18]中的簇首均是隨機產(chǎn)生，因此常出現(xiàn)簇首數(shù)目不合理、簇首分布和成簇規(guī)模不均的情況，這些情況將直接導(dǎo)致節(jié)點能耗不均、網(wǎng)絡(luò)壽命縮短。能量高效非均勻分簇(Energy-Efficient Uneven Clustering, EEUC)算法[19]、能量高效異構(gòu)分簇(Energy Efficient Heterogeneous Clustered, EEHC)算法[20]、DEEC算法則以節(jié)點剩余能量作為選舉簇首的主要指標，使剰余能量高的節(jié)點有更大的概率成為簇首，但在能量異構(gòu)性顯著的WSN應(yīng)用中，存在剩余能量大同時能量消耗也快的節(jié)點，從網(wǎng)絡(luò)整體性能來看，這類節(jié)點并不是簇首節(jié)點的最佳選擇；同時，節(jié)點能耗與通信距離成正比，但現(xiàn)有分簇算法鮮見將其作為簇首選擇參考因素。

為此，本文兼顧WSN的移動性和能量異構(gòu)性，提出了基于節(jié)點等級的自適應(yīng)分簇算法(Adaptive Clustering Algorithm based on Grades, ACA_G)。該算法利用自適應(yīng)分簇解決節(jié)點移動引發(fā)的簇首數(shù)目和成簇規(guī)模不合理的問題。通過選舉簇內(nèi)等級最高的節(jié)點為簇首，解決異構(gòu)性引發(fā)的部分節(jié)點能耗過快、網(wǎng)絡(luò)壽命縮短問題。節(jié)點等級除考慮節(jié)點剩余能量外，還結(jié)合WSN的實際應(yīng)用，綜合考慮節(jié)點剩余能量、能量消耗速率、到基站的距離、到簇內(nèi)其他節(jié)點的距離等因素。

1 網(wǎng)絡(luò)模型和能耗模型

1.1 網(wǎng)絡(luò)模型

按照節(jié)點的功能不同，將節(jié)點分為三類：基站、簇首、普通節(jié)點。簇首和普通節(jié)點可以相互轉(zhuǎn)換，相關(guān)屬性設(shè)定如下：

1)基站固定于WSN監(jiān)測區(qū)域中心位置，能量無限；其余節(jié)點初始位置隨機分布，能量有限且不能補充。

2)WSN的異構(gòu)性體現(xiàn)為能量異構(gòu)，異構(gòu)節(jié)點的初始能量和能量消耗速率不同，同構(gòu)節(jié)點的初始能量和能量消耗速率相同；節(jié)點可感知自身的剩余能量和計算能量消耗速率。

3)節(jié)點移動方向和移動角度在每輪中恒定。

4)節(jié)點能夠參照信標節(jié)點或錨節(jié)點，感知自身位置。

1.2 能耗模型

本文算法中使用的無線通信能耗模型參照Heinzelman等[5]提供的一階無線通信能耗模型，該模型如圖1所示。

圖1 無線通信能耗模型

由于節(jié)點的收發(fā)能耗遠大于節(jié)點感知和處理信息的能耗及節(jié)點閑置、休眠時的能耗，因此在該模型中，主要考慮節(jié)點的收發(fā)能耗。其中，節(jié)點的發(fā)送能耗包含發(fā)送電路能耗、放大電路能耗；節(jié)點的接收能耗僅包含接收電路能耗。該模型根據(jù)數(shù)據(jù)傳輸距離的遠近，采用兩種不同的信道模型。當傳輸距離d小于閾值距離d0時，采用自由空間信道模型；反之，采用多徑衰落信道模型。式(1)、(2)分別給出了向距離d處的節(jié)點發(fā)送/接收lb數(shù)據(jù)的能耗ETx(l,d)和ERx(l,d)。

(1)

ERx(l,d)=Eelecl

(2)

1.3 節(jié)點移動模型

本文算法的節(jié)點移動模型選用隨機移動模型[21]。隨機移動模型中，節(jié)點隨機選擇在[0，vmax]內(nèi)均勻分布的某個值作勻速運動，到達目的地后，停留Tpause時間后，節(jié)點又隨機選擇新的目的地移動。如果Tpause=0，則表示節(jié)點連續(xù)運動。由此可見，節(jié)點最大運動速率vmax和停留時間Tpause是隨機移動模型的兩個關(guān)鍵參數(shù)。如果vmax小而Tpause大，則網(wǎng)絡(luò)拓撲相對穩(wěn)定；反之，則網(wǎng)絡(luò)拓撲具有較高的動態(tài)性。此外，ACA_G算法基于以下假設(shè)進行驗證：簇首在當選時間內(nèi)處于基本靜止狀態(tài)，其余的節(jié)點移動主要集中在數(shù)據(jù)傳輸階段。

2 算法原理

ACA_G算法按輪依次運行，每一輪包括自適應(yīng)分簇、簇建立、數(shù)據(jù)傳輸三個階段。ACA_G算法算法流程如圖2所示。

圖2 ACA_G算法流程

2.1 自適應(yīng)分簇

初始化時，根據(jù)網(wǎng)絡(luò)監(jiān)測區(qū)域大小，按一定原則，如從左到右-從上到下原則將網(wǎng)絡(luò)監(jiān)測區(qū)域等分成M0(M0≥1)個子區(qū)域，每個子區(qū)域中所有節(jié)點自成一簇，初始節(jié)點分布如圖3所示，監(jiān)測區(qū)域中心位置為能量無限大、位置固定的基站。圖3中，通過節(jié)點顏色表征當前節(jié)點的能量高低，顏色越深的節(jié)點表示能量越高。網(wǎng)絡(luò)運行過程中，由于節(jié)點移動或因能量消耗殆盡死亡，每個子區(qū)域內(nèi)的節(jié)點數(shù)目是動態(tài)變化的。本文算法通過監(jiān)測每個子區(qū)域內(nèi)節(jié)點數(shù)目變化，實現(xiàn)自適應(yīng)分簇，以防止因簇首分布不均、簇規(guī)模不合理造成的部分節(jié)點能量衰減過快，網(wǎng)絡(luò)整體壽命縮短。

圖3 節(jié)點初始分布

自適應(yīng)分簇的實施方法如下：

(3)

(4)

其中：m∈[1,Mr-1]，Mr-1表示網(wǎng)絡(luò)監(jiān)測區(qū)域第r-1輪劃分的子區(qū)域總數(shù)，Mr-1、r、m為大于0的整數(shù)；Nr表示第r輪網(wǎng)絡(luò)中存活節(jié)點的總數(shù);ω1和ω2表示權(quán)重系數(shù)，ω1∈[0,1]，ω2∈[1,2]；符號?」表示取整數(shù)運算。

(5)

(6)

(7)

由圖4～5可知，通過自適應(yīng)分簇，可實現(xiàn)網(wǎng)絡(luò)中簇首數(shù)目和成簇規(guī)模合理化。

圖4 子區(qū)域細化示意圖

圖5 就近子區(qū)域合并示意圖

2.2 簇建立

(8)

選舉本簇內(nèi)等級最高的節(jié)點為第r輪簇首，具體實施步驟如下：網(wǎng)絡(luò)中每個節(jié)點廣播自身等級和ID號、自身所在的簇號，并設(shè)置定時器T1。T1的時間長度應(yīng)使廣播信息能夠往返于監(jiān)測網(wǎng)絡(luò)中的任一節(jié)點為宜。節(jié)點僅對同簇內(nèi)比自身等級低的節(jié)點進行反饋，反饋信息包括自身等級和ID號。在定時器T1時間內(nèi)，如節(jié)點i在定時器T1結(jié)束時收到同簇內(nèi)比自身等級高的節(jié)點的反饋信息，則轉(zhuǎn)為簇內(nèi)成員節(jié)點，等待接收簇首當選的消息；如節(jié)點i在定時器T1結(jié)束時未收到任何反饋信息，則表明自己為本輪次本簇等級最高的節(jié)點，隨即向簇內(nèi)其余節(jié)點廣播當選簇首的消息和自身ID號，并設(shè)置定時器T2。T2的時間長度應(yīng)使廣播信息能夠往返于網(wǎng)絡(luò)中的任一節(jié)點為宜。簇內(nèi)成員節(jié)點收到簇首的當選消息后，向簇首發(fā)送請求加入信息，加入信息包括自身ID號和等級；簇首根據(jù)成員節(jié)點的加入信息確定本簇的成員個數(shù)，根據(jù)成員節(jié)點等級高低制定不同時隙長度的時分多址(TimeDivisionMultipleAccess,TDMA)表廣播給成員節(jié)點；等級越高的成員節(jié)點分配到的TDMA時隙越長。當簇內(nèi)所有成員節(jié)點接收到入簇確認信息和TDMA表，簇建立完成。

2.3 數(shù)據(jù)傳輸

成員節(jié)點與簇首，簇首與基站間均采用單跳通信。簇內(nèi)成員節(jié)點在自己的TDMA時隙發(fā)送監(jiān)測信息給簇首。為避免不同簇中成員節(jié)點的TDMA時隙沖突，成員節(jié)點在發(fā)送信息后將對信道進行檢測，如果發(fā)現(xiàn)通信沖突，等級高的節(jié)點將停止發(fā)送數(shù)據(jù)，讓出信道，讓等級低的節(jié)點優(yōu)先與自身簇首通信，確保等級低的節(jié)點盡量一次性與自己的簇首通信成功。由于在TDMA時隙分配時高等級節(jié)點分得的時隙較長，在發(fā)生沖突后退出信道競爭的高等級節(jié)點隨機等待Tx時間后(Tx為遠小于該節(jié)點分得的TDMA時隙長度的一個隨機數(shù))，繼續(xù)同簇首通信，同時按上述策略減少不同簇中成員節(jié)點的通信沖突。如果發(fā)生沖突的節(jié)點等級相同，它們均隨機等待Tx后再向自己的簇首發(fā)送信息。簇首收集、匯總、融合成員節(jié)點信息后上傳給基站，直到本輪時間Tr結(jié)束(Tr應(yīng)遠大于T1和T2)，進行下一輪自適應(yīng)分簇、簇首選舉和簇建立、信息傳輸，直到節(jié)點全部死亡，網(wǎng)絡(luò)壽命終止。

3 仿真驗證與分析

為驗證ACA_G算法，使用OMNeT++仿真軟件對其進行仿真驗證，并使用Matlab進行數(shù)據(jù)分析。為驗證ACA_G算法對網(wǎng)絡(luò)移動特性的性能，將其與LEACH-Mobile算法進行對比實驗；為驗證ACA_G算法對網(wǎng)絡(luò)異構(gòu)特性的性能，將其與DEEC算法進行對比實驗。其中：基站位于方形網(wǎng)絡(luò)監(jiān)測區(qū)域中心，能量無限大；其余節(jié)點初始位置隨機分布在網(wǎng)絡(luò)監(jiān)測區(qū)域內(nèi)。在網(wǎng)絡(luò)監(jiān)測區(qū)域四周邊界處等間距部署12個信標節(jié)點用于節(jié)點定位。節(jié)點通信能耗模型、移動模型參見1.2、1.3節(jié)。網(wǎng)絡(luò)的異構(gòu)性主要體現(xiàn)為能量異構(gòu)，如圖3～5所示，圖中節(jié)點顏色越深表示能量越高。其余實驗參數(shù)設(shè)置如表1所示。根據(jù)以上仿真條件，每個實驗在相同的條件下進行500次實驗，然后取其整數(shù)平均值。為簡化仿真，不考慮節(jié)點因移動帶來的能耗。并假設(shè)每個成員節(jié)點均向簇首發(fā)送4kb的數(shù)據(jù)，無論簇內(nèi)成員節(jié)點數(shù)目為多少，簇首將其成員節(jié)點的數(shù)據(jù)壓縮為4kb數(shù)據(jù)轉(zhuǎn)發(fā)給基站，簇內(nèi)數(shù)據(jù)融合能耗設(shè)定為5nJ/b。ω1=0.54，ω2=1.26，ω3=1。

3.1 網(wǎng)絡(luò)壽命情況

由于WSN布置一般存在冗余節(jié)點，只要能保證一定比例的節(jié)點存活，就能覆蓋監(jiān)測區(qū)域并上傳監(jiān)測信息到基站，因此本文中網(wǎng)絡(luò)壽命定義為從網(wǎng)絡(luò)運行開始到半數(shù)節(jié)點死亡的時間。當節(jié)點能耗等于或小于0時表明節(jié)點死亡。由于圖6(a)～(d)給出了節(jié)點移動速度v分別為0m/s、0.2m/s、0.4m/s、0.6m/s時的節(jié)點死亡發(fā)生的輪次。其余實驗參數(shù)設(shè)置如表1所示。

當節(jié)點隨機移動速度為0m/s時，運用ACA_G算法、LEACH-Mobile算法和DEEC算法進行分簇，網(wǎng)絡(luò)中半數(shù)節(jié)點死亡分別發(fā)生在2 733輪、1 767輪、1 909輪，如圖6(a)所示。運用ACA_G算法分簇后的網(wǎng)絡(luò)，半數(shù)節(jié)點死亡時間比運用LEACH-Mobile算法和DEEC算法分簇的WSN分別延長了54.7%和43.2%。

當節(jié)點隨機移動速度為0.2m/s時，運用ACA_G算法、LEACH-Mobile算法和DEEC算法進行分簇，網(wǎng)絡(luò)中半數(shù)節(jié)點死亡分別發(fā)生在2 098輪、1 603輪、1 491輪，如圖6(b)所示。ACA_G算法分簇后的網(wǎng)絡(luò)，半數(shù)節(jié)點死亡時間比LEACH-Mobile算法和DEEC算法分簇的WSN分別延長了30.9%和40.7%。

當節(jié)點隨機移動速度為0.4m/s時，運用ACA_G算法、LEACH-Mobile算法和DEEC算法進行分簇，網(wǎng)絡(luò)中半數(shù)節(jié)點死亡分別發(fā)生在1 733輪、1 080 輪、529輪，如圖6(c)所示。運用ACA_G算法分簇后的網(wǎng)絡(luò)，半數(shù)節(jié)點死亡時間比運用LEACH-Mobile算法和DEEC算法分簇的WSN分別延長了60.5%和227.6%。

當節(jié)點隨機移動速度為0.6m/s時，運用ACA_G算法、LEACH-Mobile算法和DEEC算法進行分簇，網(wǎng)絡(luò)中半數(shù)節(jié)點死亡分別發(fā)生在1 106輪、363輪、80輪，如圖6(d)所示。運用ACA_G算法分簇后的網(wǎng)絡(luò)，半數(shù)節(jié)點死亡時間比運用LEACH-Mobile算法和DEEC算法分簇的WSN分別延長了204.7%和1 382.5%。

圖6 異構(gòu)移動WSN環(huán)境下的網(wǎng)絡(luò)壽命示意圖

3.2 網(wǎng)絡(luò)數(shù)據(jù)吞吐量

圖7給出了上述仿真條件下網(wǎng)絡(luò)數(shù)據(jù)吞吐量隨輪數(shù)的變化情況。

圖7 異構(gòu)移動WSN環(huán)境下的網(wǎng)絡(luò)數(shù)據(jù)吞吐量示意圖

當節(jié)點以隨機移動速度在0～0.6m/s范圍內(nèi)以0.2m/s遞增時，截至網(wǎng)絡(luò)壽命終止，運用上述三種算法進行分簇的WSN，其網(wǎng)絡(luò)數(shù)據(jù)吞吐量都有所降低，但運用ACA_G算法分簇的網(wǎng)絡(luò)，其數(shù)據(jù)吞吐量仍高于其余兩種算法，如表2所示。當v=0m/s時，運用ACA_G算法分簇的網(wǎng)絡(luò)，其網(wǎng)絡(luò)數(shù)據(jù)吞吐量分別是運用LEACH-Mobile算法、DEEC算法分簇的網(wǎng)絡(luò)的2.24倍、2.11倍；當v=0.2m/s時，運用ACA_G算法分簇的網(wǎng)絡(luò)，其網(wǎng)絡(luò)數(shù)據(jù)吞吐量分別是運用LEACH-Mobile算法、DEEC算法分簇的網(wǎng)絡(luò)的1.15倍、1.24倍；當v=0.4m/s時，運用ACA_G算法分簇的網(wǎng)絡(luò)，其網(wǎng)絡(luò)數(shù)據(jù)吞吐量分別是運用LEACH-Mobile算法、DEEC算法分簇的網(wǎng)絡(luò)的1.79倍、3.67倍；當v=0.6m/s時，運用ACA_G算法分簇的網(wǎng)絡(luò)，其網(wǎng)絡(luò)數(shù)據(jù)吞吐量分別是運用LEACH-Mobile、DEEC算法分簇的網(wǎng)絡(luò)的2.60倍、8.24倍。

表2 截至網(wǎng)絡(luò)壽命終止的網(wǎng)絡(luò)數(shù)據(jù)吞吐量

3.3 結(jié)果分析

由上述仿真結(jié)果可知，當節(jié)點移動速度在0～0.6m/s范圍內(nèi)越來越快時，網(wǎng)絡(luò)拓撲變化也越快；分別運用三種算法分簇后，節(jié)點的死亡速度均在加快，與LEACH-Mobile算法和DEEC算法相比，本文算法的半數(shù)節(jié)點死亡時間明顯滯后，網(wǎng)絡(luò)壽命更長，網(wǎng)絡(luò)數(shù)據(jù)吞吐量更多。這是因為在LEACH-Mobile算法中，簇首是隨機選舉產(chǎn)生的，因此在能量異構(gòu)的網(wǎng)絡(luò)中，很可能是一些低能量節(jié)點來當選簇首，這樣勢必造成這些低能量節(jié)點能量消耗過快，從而加速它們的死亡。DEEC算法則是選舉剩余能量高的節(jié)點當選簇首，但在異構(gòu)網(wǎng)絡(luò)中，由于監(jiān)測對象不同，存在剩余能量大同時能量消耗也快的節(jié)點，從網(wǎng)絡(luò)整體性能來看，這類節(jié)點并不是簇首的最佳選擇。同時節(jié)點通信能耗與通信距離成正比，像DEEC算法這樣僅僅以剩余能量為標準來選舉簇首在實際應(yīng)用中是不合理的，同時，DEEC算法并無應(yīng)對節(jié)點移動的機制，因此，在節(jié)點靜止時，其性能略優(yōu)于LEACH-Mobile算法，但節(jié)點移動速度加快時，其性能卻遜于LEACH-Mobile算法。ACA_G算法通過自適應(yīng)分簇克服節(jié)點移動性帶來的網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化影響，均衡網(wǎng)絡(luò)簇首數(shù)目和簇規(guī)模，綜合考慮節(jié)點剩余能量、能量消耗速率、到基站的距離、到簇內(nèi)其他節(jié)點的距離計算節(jié)點等級；且ACA_G算法通過選舉簇內(nèi)等級最高的節(jié)點為簇首，均衡節(jié)點能量消耗、延長網(wǎng)絡(luò)壽命、提高網(wǎng)絡(luò)數(shù)據(jù)吞吐量。因此，較LEACH-Mobile算法和DEEC算法，本文提出的ACA_G算法具有明顯優(yōu)勢。

4 結(jié)語

本文提出的基于節(jié)點等級的自適應(yīng)分簇算法ACA_G，通過自適應(yīng)分簇、選舉簇內(nèi)等級高的節(jié)點為簇首等措施，分別解決WSN異構(gòu)性和移動性對網(wǎng)絡(luò)壽命、網(wǎng)絡(luò)數(shù)據(jù)吞吐量帶來的影響。實驗結(jié)果表明，在節(jié)點移動速度0～0.6m/s的能量異構(gòu)WSN環(huán)境下，與LEACH-Mobile算法和DEEC算法相比，本文算法優(yōu)勢明顯。下一步應(yīng)進行算法參數(shù)優(yōu)化，如參數(shù)ω1、ω2、ω3的取值等，進一步提高算法性能。

)

[1]DONGM,OTAK,LIUA.RMER:reliableandenergy-efficientdatacollectionforlarge-scalewirelesssensornetworks[J].IEEEInternetofThingsJournal, 2016, 3(4): 511-519.

[2] 趙海軍,崔夢天,李明東,等.基于改進的洪泛廣播和粒子濾波的無線傳感器網(wǎng)絡(luò)節(jié)點定位[J].計算機應(yīng)用,2016,36(10):2659-2663.(ZHAOHJ,CUIMT,LIMD,etal.Nodelocalizationbasedonimprovedfloodingbroadcastandparticlefilteringinwirelesssensornetwork[J].JournalofComputerApplications, 2016, 36(10): 2659-2663.)

[3]MANNPS,SINGHS.Improvedmetaheuristicbasedenergy-efficientclusteringprotocolforwirelesssensornetworks[J].EngineeringApplicationsofArtificialIntelligence, 2017, 57: 142-152.

[4] 蘇金樹，郭文忠，余朝龍，等.負載均衡感知的無線傳感器網(wǎng)絡(luò)容錯分簇算法[J].計算機學(xué)報,2014,37(2):445-456.(SUJS,GUOWZ,YUCL,etal.Fault-toleranceclusteringalgorithmwithload-balanceawareinwirelesssensornetwork[J].ChineseJournalofComputers, 2014, 37(2): 445-456.)

[5]HEINZELMANW,CHANDRAKASANA,BALAKRISHNANH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]//HICSS’00:Proceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences.Washington,DC:IEEEComputerSociety, 2000, 8: 8020.

[6]LINDSEYS,RAGHAVENDRACS.PEGASIS:power-efficientgatheringinsensorinformationsystems[C]//Proceedingofthe2002IEEEAerospaceConference.Piscataway,NJ:IEEE, 2002: 1125-1130.

[7]GURRUTXAGAI,ALBISUAI,ARBELAITZO,etal.SEP/COP:anefficientmethodtofindthebestpartitioninhierarchicalclusteringbasedonanewclustervalidityindex[J].PatternRecognition, 2010, 43(10): 3364-3373.

[8]ASLAMM,MUNIREU,RAFIQUEMM,etal.Adaptiveenergy-efficientclusteringpathplanningroutingprotocolsforheterogeneouswirelesssensornetworks[J].SustainableComputing:InformaticsandSystems, 2016, 12: 57-71.

[9]SINGHS,MALIKA,KUMARR.EnergyefficientheterogeneousDEECprotocolforenhancinglifetimeinWSNs[J].EngineeringScienceandTechnology,anInternationalJournal, 2017, 20(1): 345-353.

[10]GUPTAV,PANDEYR.Animprovedenergyawaredistributedunequalclusteringprotocolforheterogeneouswirelesssensornetworks[J].EngineeringScienceandTechnology,anInternationalJournal, 2016, 19(2): 1050-1058.

[11]KIMDS,CHUNGYJ.Self-organizationroutingprotocolsupportingmobilenodesforwirelesssensornetwork[C]//IMSCCS’06:Proceedingsofthe2006FirstInternationalMulti-SymposiumsonComputerandComputationalSciences.Piscataway,NJ:IEEE, 2006: 622-626.

[12]AMINED,NASSREDDINEB,BOUABDELLAHK.Energyefficientandsafeweightedclusteringalgorithmformobilewirelesssensornetworks[J].ProcediaComputerScience, 2014, 34: 63-70.

[13]AMINED,NASR-EDDINEB,ABDELHAMIDL.Adistributedandsafeweightedclusteringalgorithmformobilewirelesssensornetworks[J].ProcediaComputerScience, 2015, 52(34): 641-646.

[14]ZHANGD-G,ZHUY-N,ZHAOC-P,etal.Anewconstructingapproachforaweightedtopologyofwirelesssensornetworksbasedonlocal-worldtheoryfortheInternetofThings(IOT) [J].ComputerandMathematicswithApplications, 2012, 64(5):1044-1055.

[15]ZORZIM,GLUHAKA,LANGES,etal.Fromtoday’sINTRAnetofthingstoafutureINTERnetofthings:awireless-andmobility-relatedview[J].IEEEWirelessCommunications, 2010, 17(6): 44-51.

[16] 肖竹，王東，李仁發(fā)，等.物聯(lián)網(wǎng)定位與位置感知研究[J].中國科學(xué)：信息科學(xué),2013,43(10):1265-1287.(XIAOZ,WANGD,LIRF,etal.Localizationandnodeslocation-awareinInternetofthings[J].SCIENTIASINICAInformationis, 2013, 43(10): 1265-1287.

[17]MANZOORB,JAVAIDN,REHMANO,etal.Q-LEACH:anewroutingprotocolforWSNs[J].ProcediaComputerScience, 2013, 19: 926-931.

[18] 沈永增，陳宣揚，賈蓮蓮.一種事件驅(qū)動型無線傳感器網(wǎng)絡(luò)的分層路由算法[J].計算機系統(tǒng)應(yīng)用,2011,20(8):81-85.(SHENYZ,CHENXY,JIALL.Hierarchicalroutingalgorithminevent-drivenwirelesssensornetworks[J].ComputerSystems&Applications, 2011, 20(8): 81-85.)

[19] 唐加山，王燕.無線傳感器網(wǎng)絡(luò)中改進的EEUC路由協(xié)議[J].重慶郵電大學(xué)學(xué)報：自然科學(xué)版,2013,25(2):172-177.(TANGJS,WANGY.ImprovedEEUCroutingprotocolforwirelesssensornetworks[J].JournalofChongqingUniversityofPostsandTelecommunications(NaturalScienceEdition), 2013, 25(2): 172-177.)

[20]KUMARD,ASERITC,PATELRB.EEHC:energyefficientheterogeneousclusteredschemeforwirelesssensornetworks[J].ComputerCommunications, 2009, 32(4): 662-667.

[21]SILVART,COLLETTIRR,PIMENTELC,etal.BETArandomwaypointmobilitymodelforwirelessnetworksimulation[J].AdHocNetworks, 2016, 48: 93-100.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61302175),theYouthScienceFoundationofLogisticalEngineeringUniversity(X2050114).

XIAO Wei, born in 1982, Ph. D., lecturer. Her research interests include wireless sensor network, Internet of things, digital signal processing.

TU Yaqing, born in 1963, Ph. D., professor. His research interests include intelligent control, signal processing.

An adaptive clustering algorithm based on grades for wireless sensor networks

XIAO Wei*, TU Yaqing

(DepartmentofLogisticalInformation&LogisticsEngineering,LogisticalEngineeringUniversity,Chongqing401311,China)

To solve the short life time and low network throughput problems caused by the heterogeneity and mobility of Wireless Sensor Network (WSN) clustering algorithm, an Adaptive Clustering Algorithm based on Grades (ACA_G) was proposed. The proposed algorithm was run on rounds, which was composed of three stages: the adaptive clustering stage, the cluster construction stage and the data transmission stage. In the adaptive clustering stage, every partition may be subdivided or united adjacently according to the change of the number of nodes in each partition to keep an appropriate number of nodes in it. The adaptive clustering measure could be able to solve the unreasonable problems of the number of cluster-heads and the scale of clusters caused by the node mobility in WSN. In order to deal with the phenomena of some nodes died too fast and the life time of WSN was shortened caused by the heterogeneity in WSN, the node with the highest grade was selected as the cluster-head in the cluster construction stage. In the WSN application, the grade of each node was calculated according to the node residual energy, the speed of energy consumption, the distance between the node and the base station, the accumulated distance between the node and other nodes in the same cluster. The experiment was simulated by OMNeT++ and Matlab on a WSN with energy heterogeneity, in which node’s mobile speed is 0～0.6 m/s randomly. The experimental results show that, compared with the Low Energy Adaptive Clustering Hierarchy -Mobile (LEACH-Mobile) algorithm and the Distributed Energy-Efficient Clustering (DEEC) algorithm, the life time of WSN clustered by the proposed algorithm is 30.9% longer than the other two algorithms, its network throughout is 1.15 times at least as much as the other two algorithms.

adaptive clustering; grade; Wireless Sensor Network (WSN); energy heterogeneity; mobility

2016- 10- 11;

2017- 01- 08。

國家自然科學(xué)基金資助項目(61302175)；后勤工程學(xué)院青年科學(xué)基金資助項目(X2050114)。

肖瑋(1982—)，女，重慶人，講師，博士，主要研究方向：無線傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)、數(shù)字信號處理; 涂亞慶(1963—)，男，重慶人，教授，博士，主要研究方向：智能控制、信號處理。

1001- 9081(2017)06- 1532- 07

10.11772/j.issn.1001- 9081.2017.06.1532

TP393.0

A