能量均衡的無線傳感器網絡多跳非均勻分簇算法

馬威風，陳桂芬

(長春理工大學 電子信息工程學院，吉林 長春 130022)

0　引言

無線傳感器網絡(Wireless Sensor Networks, WSNs)是由部署在監測區域內大量廉價的微型傳感器節點組成，通過無線通信方式形成的一個多跳的自組織的網絡系統[1]。隨著傳感器、嵌入式計算、通信和計算機網絡等技術的日趨成熟，無線自組織網絡的各種應用逐漸成為可能，成為21世紀信息產業的重要支柱[2]。WSNs節點作為微小器件只能配備有限電源，而且多數部署在危險地帶或人難以到達的環境中，后期維護難以實現，使節點壽命很大程度上依賴電池壽命，因此，如何減少節點的能量消耗對于傳感器網絡而言至關重要[3]，同時也是設計協議時面臨的重要問題之一。

WSNs中節點布設密度大，節點感知到的數據存在大量的冗余信息[4]，而通信耗能為總能耗的主要部分。因此，必須嚴格控制數據包傳輸量來減少不必要的開銷。以LEACH[5]為典型代表的分簇算法將節點分為簇頭和簇內節點，簇內節點負責采集數據，而簇頭負責管理簇內節點，并進行簇內節點信息的采集、融合及轉發[6]。LEACH算法在一定程度上實現了能耗均衡，但存在簇頭分布位置的隨機性、選取簇頭未考慮節點剩余能量以及與基站直接進行數據傳輸導致能耗過大的問題[7]。

EEUC[8]算法采用非均勻分簇和簇間多跳的方式。網絡被劃分為大小不等的簇，遠離基站的簇內節點較多，避免過快消耗能量，而且簇間多跳路由方式可以進一步均衡簇頭能量消耗[9]，較好地解決了“熱區”問題[10]。

DEEUC[11]算法在EEUC基礎上優化了簇頭選舉和路由選擇，算法中候選簇頭由上一輪簇頭根據簇內剩余能量選出，再通過能量因素選出最終簇頭。下一跳路由簇頭選擇正向單位能量消耗最小的鄰簇首，有效地提高簇頭間傳輸數據的效率。

本文基于非均勻分簇算法提出一種能量均衡多跳非均勻分簇算法(Energy Balance Multi-hops Uneven Clustering, EBMUC)，算法首先比較節點剩余能量與鄰節點平均剩余能量選出候選簇頭，再考慮距離、能量和鄰節點數因素選出最終簇頭；簇構造在節點入簇公式[12]中加入簇頭剩余能量；簇間選擇中繼節點協助傳輸數據，數據通過中繼節點和鄰簇頭多跳傳輸到基站(BS)，進一步延長網絡生存時間。

1　相關理論

1.1　網絡模型

正方形監測區域內隨機分布N個周期性收集數據的WSNs節點，假設：(1)BS位于監測區域邊緣，BS和節點部署后位置不再變動；(2)節點具有全網絡唯一的標識ID號，節點同構且具備一定的存儲能力，可以由信號強度估算距離；(3)BS能夠與全網絡的節點通信，通信方式為半雙工；(4)無線信道對稱，數據傳輸過程中融合數據減少數據量，融合單位數據耗能相同；(5)忽略外界影響，節點周期性采集數據并始終有數據傳輸到BS。

1.2　能量模型

本文采用文獻[13]中的無線通信能耗模型，kbit的數據包發送到距離d的一個節點，能耗主要由無線信號收發和功率放大產生，功放器件的耗能與環境和距離密切相關，可分為自由空間模型和多徑衰落模型。發送模塊能耗計算如式(1)所示：

(1)

ERx(k)=kEelec

(2)

1.3　最優簇數目和最優簇通信半徑

采用文獻[13]中的方法計算最優簇數目(mopt)，假定在一個M×M的區域內均勻部署N個節點，產生m個簇，m個簇的總能耗如式(3)所示：

(3)

對式(3)中m求導并令式等于0, 求出mopt，由mopt計算均勻分簇情況下最優簇通信半徑ropt、最優跳數τopt，如式(4)所示，式中為向上取整。

(4)

2　EBMUC協議算法設計

(1)簇頭選擇：BS首先廣播初始化消息(包括mopt、ropt和d0)。節點收到消息后由信號強度估算到BS的距離dtoBS(i)，然后節點以ropt為半徑向周圍鄰節點廣播消息(包括節點剩余能量和到BS距離)，節點收到鄰節點消息后建立鄰節點信息表并統計鄰節點個數，計算其鄰節點平均剩余能量。若節點剩余能量大于鄰節點平均剩余能量，則當選候選簇頭并廣播消息，反之節點進入休眠。候選簇頭收到鄰候選簇頭的消息后建立鄰候選簇頭信息表，然后計算并廣播適應值(如式(5)所示)，通過交換適應值選擇值最大的候選簇頭為最終簇頭并廣播當選消息，休眠中的節點收到最終簇頭的消息后喚醒。

f(i)=w1N+w2E+w3D

(5)

(2)簇結構形成：①簇內結構。節點收到最終簇頭當選消息后建立簇頭信息表并估算到各簇頭距離，對每個簇頭的飽和度進行判斷(即表達式P2)，由式(6)選擇值大于0的簇頭發送加入消息(包括剩余能量和基站距離)。

Add(i, CHj)=αP1+(1-α)P2

(6)

簇頭記錄節點發送的加入消息(若收到競選簇頭失敗的候選簇頭的消息則將其標記為副簇頭)，根據成員節點數分配發送數據幀間隔。成員數較少的簇對應幀時間間隔較大，反之，幀時間間隔較小，以此來保證單位時間內不同簇內數目不同的節點傳輸的數據次數相同。最后，簇頭采用TDMA方式向簇內成員廣播工作時隙。

②簇間結構。簇頭收到周圍其他最終簇頭當選消息后建立鄰簇頭信息表，計算并廣播簇間數據轉發代價值(如式(7)所示)，通過比較代價值來決定下一跳簇頭。

(7)

下一跳簇頭確定后，若簇頭間距離大于d0，則在傳輸數據的簇內選擇靠近下一跳簇頭的中繼節點輔助傳輸數據，反之則簇頭間傳輸數據。中繼節點由節點剩余能量與到兩簇頭間的距離兩因素確定(如式(8)所示)，其中Erel、drel to CHj分別為中繼節點剩余能量和到下一跳簇頭距離。

(8)

(3)數據傳輸：簇成員節點在分配的時隙段向距離自己最近的副簇頭傳輸數據(若無副簇頭，則通過鄰節點，若無鄰節點則增大功率與簇頭之間通信，將數據多跳傳輸至簇頭)，副簇頭收集并融合數據后向簇頭轉發，每次多跳傳輸過程中都有數據融合，數據傳輸后簇成員節點進入休眠狀態；對于簇間數據傳輸則根據簇頭間的距離情況選擇中繼節點輔助數據傳輸。同樣，到BS距離小于d0的節點以單跳形式向BS傳輸數據，大于則多跳傳輸到BS。此外，靠近BS的簇頭或普通節點并不是有數據就立即向BS傳輸，而是等待數據量匯聚到一定程度后再向BS傳輸，這樣階段地一次性向BS傳送數據，大大減少了數據包的發送次數，從而使得距離BS較遠的節點可以向基站附近匯聚更多信息量的數據。網絡整體示意圖如圖1所示。

圖1　EBMUC協議節點示意圖

3　仿真實驗與分析

3.1　仿真實驗

在1 000 m×1 000 m區域中仿真比較了LEACH、EEUC、DEEUC和EBMUC，節點數為1 000個，初始能量為0.5 J，BS坐標為(1 000,500)。成簇權值α=0.6，w1、w2與w3分別取0.3、0.4和0.3，距離常數d0為87 m。其他參數見表1。

表1　仿真相關參數

3.2　仿真實驗結果分析

通過仿真網絡的生存時間、BS接收數據量和網絡剩余能量來研究本文算法的性能。

3.2.1網絡生存時間

網絡生存時間是衡量網絡性能的重要指標之一[14]，表2統計了圖2中四種算法的第一個死亡節點(FND)和死亡一半節點(HND)的輪數,若是以HND作為網絡生存時間評判標準，四種算法網絡生存時間分別為215、273、297和362，與LEACH比較，EEUC采用了非均勻分簇的方式，很好地解決了“熱區”問題，延遲了FND的出現；DEEUC在EEUC的基礎上優化了簇頭選取以及最小正向單位路由選擇，能耗比EEUC算法得到進一步降低；而本文的EBMUC算法在由候選簇頭選取簇頭時，考慮了能量、距離以及鄰節點數等因素，比DEEUC由候選簇頭通過能量因素競爭選取出的簇頭更為合理，出現FND輪數也更遲。EEUC、DEEUC以及本文算法會在某個時間段出現節點迅速死亡，產生這種現象的原因是由于這三種算法覆蓋面積遠大于LEACH，網絡中節點能量得到均衡消耗，會在某一刻存活的節點少于LEACH中的節點數。EBMUC由于中繼節點的加入，數據多跳傳輸到BS，更好地均衡了簇間能量消耗，所以后期節點死亡速度略快于DEEUC。

圖2　存活節點數對比圖

算法名稱FND輪數HND輪數LEACH34215EEUC201273DEEUC236297EBMUC298362

3.2.2基站BS接收數據量

圖3為四種算法BS接收數據量對比圖，在FND之前，EBMUC中基站收到的數據包總量約是LEACH算法的1.5倍，約是EEUC與DEEUC的1.3、1.1倍。這是因為EBMUC改進的簇頭選擇與簇間通信方式，延長了網絡的生命周期，使數據量有所增加，在EBMUC的HND之前，LEACH、EEUC和DEEUC中的大部分節點已經死亡，網絡存在覆蓋率低的區域，節點難以將數據傳輸到BS。

圖3　基站BS接收數據量對比圖

3.2.3網絡剩余能量

圖4比較了四種算法的網絡剩余能量隨運行輪數的變化情況。EEUC、DEEUC和EBMUC的多跳非均勻策略比單跳均勻的LEACH有明顯的節能優勢。EBMUC網絡剩余能量在700輪之前大于其他三種算法，體現了本文算法的能量利用高效性。之后，由于EBMUC覆蓋面積較大，消耗了一定的網絡剩余能量，因此小于LEACH算法，同樣地，EEUC和DEEUC也出現了這種情況。EEUC、DEEUC和EBMUC相比，DEEUC中簇頭指定能量最高的節點為下輪的簇頭，均衡了節點間能耗同時也避免多個節點成為候選簇頭參與最終簇頭競爭，節省了網絡能量。而EBMUC是先選擇候選簇頭，再由候選簇頭綜合考慮能量、距離以及鄰節點數來競爭最終簇頭，得到的簇頭更為合理，同時在節點入簇時考慮了簇頭能量與簇規模，有效地減輕了簇頭負擔，降低了網絡能耗。

圖4　網絡剩余能量對比圖

4　結論

本文在研究現有的非均勻分簇算法基礎上，設計了一種能量均衡的多跳非均勻分簇算法，算法考慮了節點的距離、能量以及鄰居數等因素來選取最終的簇頭節點。節點入簇階段考慮了簇頭的能量與距離，同時也考慮了簇頭的鄰節點數，避免形成的簇結構規模過大。為了防止簇頭間出現遠距離傳輸數據的情況，采取選擇待傳輸數據簇內最遠處的節點作為中繼節點來輔助數據傳輸，縮短數據傳輸路徑，最小化簇間數據通信開銷。與LEACH、EEUC和DEEUC算法相比，本文算法平衡了節點能耗，延緩了網絡中死亡節點的出現輪數，從而延長了網絡生存時間。

[1] 蘇兵,張鈺婧.基于非均勻分簇的無線傳感器網絡路由協議[J].計算機測量與控制,2016, 24(2):325-327.

[2] 劉半藤,周瑩,陳友榮,等.基于移動-能量代價函數的無線自組織網絡路由策略研究[J].傳感技術學報, 2017,30(2):302-305.

[3] 林德鈺,王泉,劉伎昭.無線傳感網的移動與靜態sink相結合的節能策略[J].哈爾濱工業大學學報, 2016,48(11):162-168.

[4] 張策,張霞,李鷗,等.基于CS的無線傳感器網絡動態分簇數據收集算法[J].計算機研究與發展,2016, 53(9):2000-2008.

[5] ZHANG X L, LI Q, FU Y, et al. An energy balancing LEACH algorithm for wireless sensor network[C]. International Conference on Electrical, Computer Engineering and Electronics, 2015:752-756.

[6] 張軍強,王汝傳,黃海平.基于分簇的無線多媒體傳感器網絡數據聚合方案研究[J].電子與信息學報, 2014,36(1):8-14.

[7] SALMABADI H, ADIBNIA F, SARRAM M A. An improvement on LEACH protocol (EZ-LEACH)[C]. International Conference on Knowledge-Based Engineering and Innovation(KBEI)，2015:956-970.

[8] LI C F, YE M, CHEN G H, et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]. IEEE International Conference on Mobile Ad-hoc and Sensor Systems Conference， IEEE, 2005:597-604.

[9] 劉洲洲,王福豹,張克旺.基于混合蛙跳算法的非均勻分簇WSNs路由協議[J].計算機應用研究,2013,30(7):2173-2176.

[10] 岳麗穎, 戴月明, 吳定會. 一種能量優化WSNs非均勻分簇路由協議[J]. 計算機工程與應用, 2015(15)： 80-85.

[11] 曾華圣, 熊慶宇, 杜敏,等. 一種分布式能量高效的WSNs非均勻分簇路由協議[J]. 傳感器與微系統, 2014, 33(3):146-149.

[12] 江禹生, 李萍, 馬超. 一種能量高效的無線傳感器網絡拓撲控制算法[J]. 傳感器與微系統, 2014, 33(2):146-149.

[13] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[14] 劉半藤, 周瑩, 陳友榮,等. 基于加權路由思想的無線自組織網絡生存時間優化算法研究[J]. 傳感技術學報, 2017,30(3):463-466.