基于等級的無線傳感網自適應分簇算法

肖 瑋，涂亞慶

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

基于等級的無線傳感網自適應分簇算法

肖 瑋*，涂亞慶

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

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

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

自適應分簇；等級；無線傳感器網絡；能量異構；移動性

0 引言

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

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

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

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

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

1 網絡模型和能耗模型

1.1 網絡模型

按照節點的功能不同，將節點分為三類：基站、簇首、普通節點。簇首和普通節點可以相互轉換，相關屬性設定如下：

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

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

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

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

1.2 能耗模型

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

圖1 無線通信能耗模型

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

(1)

ERx(l,d)=Eelecl

(2)

1.3 節點移動模型

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

2 算法原理

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

圖2 ACA_G算法流程

2.1 自適應分簇

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

圖3 節點初始分布

自適應分簇的實施方法如下：

(3)

(4)

其中：m∈[1,Mr-1]，Mr-1表示網絡監測區域第r-1輪劃分的子區域總數，Mr-1、r、m為大于0的整數；Nr表示第r輪網絡中存活節點的總數;ω1和ω2表示權重系數，ω1∈[0,1]，ω2∈[1,2]；符號?」表示取整數運算。

(5)

(6)

(7)

由圖4～5可知，通過自適應分簇，可實現網絡中簇首數目和成簇規模合理化。

圖4 子區域細化示意圖

圖5 就近子區域合并示意圖

2.2 簇建立

(8)

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

2.3 數據傳輸

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

3 仿真驗證與分析

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

3.1 網絡壽命情況

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

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

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

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

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

圖6 異構移動WSN環境下的網絡壽命示意圖

3.2 網絡數據吞吐量

圖7給出了上述仿真條件下網絡數據吞吐量隨輪數的變化情況。

圖7 異構移動WSN環境下的網絡數據吞吐量示意圖

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

表2 截至網絡壽命終止的網絡數據吞吐量

3.3 結果分析

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

4 結語

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

)

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

[2] 趙海軍,崔夢天,李明東,等.基于改進的洪泛廣播和粒子濾波的無線傳感器網絡節點定位[J].計算機應用,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] 蘇金樹，郭文忠，余朝龍，等.負載均衡感知的無線傳感器網絡容錯分簇算法[J].計算機學報,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] 肖竹，王東，李仁發，等.物聯網定位與位置感知研究[J].中國科學：信息科學,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] 沈永增，陳宣揚，賈蓮蓮.一種事件驅動型無線傳感器網絡的分層路由算法[J].計算機系統應用,2011,20(8):81-85.(SHENYZ,CHENXY,JIALL.Hierarchicalroutingalgorithminevent-drivenwirelesssensornetworks[J].ComputerSystems&Applications, 2011, 20(8): 81-85.)

[19] 唐加山，王燕.無線傳感器網絡中改進的EEUC路由協議[J].重慶郵電大學學報：自然科學版,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。

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

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

1001- 9081(2017)06- 1532- 07

10.11772/j.issn.1001- 9081.2017.06.1532

TP393.0

A