基于地理位置的HEED非均勻分簇算法

渠帥軍，　呂紅芳，　趙　靜

(上海電機學院 電氣學院, 上海 201306)

?

基于地理位置的HEED非均勻分簇算法

渠帥軍，呂紅芳，趙靜

(上海電機學院 電氣學院, 上海 201306)

摘要HEED-M分簇算法中，簇首節點與匯聚節點采用多跳路由的方式進行通信，距匯聚節點越近的節點越容易過早地耗盡能量而失效。針對上述問題，提出基于地理位置的HEED非均勻分簇路由算法(LHEED)，根據簇首節點距離匯聚節點的距離動態地調整簇半徑的大小。使距匯聚節點近的簇首簇半徑較小，距匯聚節點遠的簇首簇半徑較大，從而有效地均衡網絡的能量消耗。仿真結果表明，該算法可有效延長網絡的壽命。

關鍵詞地理位置; HEED; 非均勻分簇; 簇半徑

無線傳感網絡(Wireless Sensor Network, WSN)是由分布在被監測區域內的大量廉價的傳感器節點以自組織的形式構成的網絡。設計能量高效的路由協議是WSN路由協議設計中需要重點考慮的一個問題[1]。目前，在WSN路由協議研究領域中主要采用分簇的方法來解決這一問題[2]，其基本思想是將WSN劃分為多個簇的結構，由簇首節點負責搜集簇內成員節點采集的數據，并進行數據聚合處理，然后，簇首節點間通過協作的方式將融合后的數據傳送回sink節點。

針對分簇路由算法，國內外學者進行了許多研究。LEACH(Low Energy Adaptive Clustering Hierarchy)協議[3]是第一個提出數據聚合的分簇路由協議。在LEACH協議中，由于簇首是隨機選擇的，故簇首節點的分布是不均勻的。HEED(Hybrid, Energy-Efficient Distributed Clustering)[4]算法針對此問題進行了改進，產生了分布均勻的簇首，以均衡全網能耗。但是，HEED算法也存在一些問題，目前許多文獻對HEED算法進行了改進。文獻[5]中針對HEED協議中簇首與基站直接通信能量消耗過大的問題，根據能耗模型與網絡模型提出了一種基于HEED的簇首多跳融合路由算法(HEED-M)，在簇首與基站之間采用多跳路由的方式通信。文獻[6]中提出了一種A-HEED算法，降低了各節點間廣播通信的能耗。文獻[7]中提出了一種基于HEED的多層分簇路由算法，在網絡拓撲的底層構建了多個簇首節點的簇集合，在拓撲的頂層構建了多跳轉發機制。文獻[8]中提出了HEED-CHEE分簇算法，對于“孤兒”節點和“孤立”簇首節點，采用最優鄰居中繼入簇策略加入鄰近簇，從而減少了簇首數目和簇首節點間的通信開銷。文獻[9]中使用非均勻分簇機制，計算得出最優簇半徑并設定了上、下限，使得網絡中的節點分簇更合理。

上述對HEED分簇算法的改進，都是改變簇首與sink節點的通信方式，并沒有考慮內層節點能量消耗過多這一問題。本文將非均勻分簇的思想[10]運用到HEED分簇算法中，研究了一種基于地理位置的HEED非均勻分簇算法(The HEED Non-uniform Clustering Algorithm Based on Geographic Loction, LHEED)分簇算法。該算法根據簇首節點與匯聚節點的距離動態地調整簇半徑的大小，即距匯聚節點近的簇首，簇半徑較小，距匯聚節點遠的簇首，簇半徑較大，從而均衡網絡的能量消耗，同時在簇間通信中引入了簇首通信代價函數，從而有效地延長了網絡的壽命。

1能耗模型

1.1能耗模型

WSN中的節點在通信過程中的能耗模型采用自由空間模型和多路徑衰減模型[11]，如圖1所示。圖中，Eelec為電路處理單位比特數據消耗的能量，Eamp為放大器的系數；d為發送器與接收器之間的距離；ETx、ERx分別為發送和接收單位比特數據所消耗的能量；n=2或n=4。

圖1　WSN的能耗模型Fig.1　Energy consumption model of wireless sensor network

在WSN模型中，有

(1)

由式(1)可見，WSN節點發送的能耗隨著發送距離的增加而迅速增多。在HEED算法中，簇首的選擇主要依據主、次兩個參數[12]，其中主參數依賴于剩余能量，具有較多剩余能量的節點成為臨時簇首的概率更大，次參數為簇內平均可達能量[4](Average Miximum Reachability Power, AMRP)。

(2)

式中，M為簇內節點個數；Pri為節點與簇首節點間通信能耗。

由于簇首節點與sink節點直接通信，故距離sink節點遠的簇首發送的能耗遠大于距離sink節點近的簇首發送的能耗，從而造成距離遠的簇首能量過早耗盡而死亡。在文獻[5]中提出的HEED-M分簇算法針對這一問題進行了改進。該算法與HEED算法的唯一區別就是后者采用單跳的方式與sink節點通信，而前者采用多跳路由的方式與sink節點通信[13]，如圖2所示，其中，j、k、q為簇首節點。

圖2　HEED-M算法中的簇間通信Fig.2　Communication between clusters and clusters of HEED-M

文獻[14]中研究表明，雖然多跳路由的通信方式可以從整體上降低網絡能量消耗，但是，由于距離sink節點近的簇首也會因轉發大量數據而消耗能量，這種內層節點消耗的能量是不可忽略的。而非均勻分簇可以使內層節點在分簇時通過控制成簇半徑來控制簇內節點個數，若簇半徑相對較小，則簇內成員節點數目就比較少，從而可減少簇首接收成員節點傳遞數據所消耗的能量，為內層簇首轉發遠端簇首的數據預留了能量。本文在HEED-M分簇算法的基礎上引入非均勻分簇機制，來均衡網絡能量的消耗。

2網絡模型與LHEED分簇算法

2.1網絡模型

WSN中的節點隨機分布，本文對網絡模型做如下假設：

(1) 由N個傳感器節點組成的網絡，節點隨機部署在監測區域，所有節點地位平等；

(2) 各節點一旦部署就無法更換；

(3) 監測區域中的無線傳感器節點位置固定；

(4) 整個網絡中只有一個sink節點，且sink節點是靜止的；

(5) 無線傳感器節點可以感知自身位置。

2.2算法的描述

本文研究的LHEED分簇算法根據節點與sink節點的距離動態地調整簇半徑的大小，簇首距匯聚節點近，則簇半徑較小；簇首距匯聚節點遠，則簇半徑較大，以此來均衡網絡的能量消耗。同時，在簇間通信時，簇首選擇下一跳節點應考慮到該節點的地理位置和剩余能量，故引入了一種新的簇首間的通信代價函數，通過計算選擇中繼簇首。

2.3算法的實現

2.3.1初始化階段在隨機分布的WSN區域內，首先匯聚節點向監測區域內的無線傳感器節點播報自己的地理位置，無線傳感器節點根據自身的地理位置計算出與匯聚節點的距離dto-sink，若該節點當選為簇首節點，則計算得到該簇首的最優簇半徑為[15]

(3)

式中，α為距離調節因子(其值為0～1)的值，系統最優值由仿真實驗得出；dmax和dmin分別為所有節點距離sink節點的最大值和最小值；Rmax為節點的最大通信半徑。

各節點根據其最優簇半徑確定其鄰居節點的個數，以及各自的AMRP，并根據系統規定的簇首比例Cprob計算得到該節點成為族首的概率為[10]

(4)

式中，Pmin為最小剩余能量比例；Eres為節點剩余能量；Emax為節點初始能量。

簇首選擇的主參數依賴于剩余能量，剩余能量多的節點將有較大的概率成為簇首。

2.3.2迭代階段每個節點在每輪的迭代過程中判斷鄰居節點中是否有臨時簇首節點，若有且該節點也是臨時簇首，則比較該節點與鄰居節點中臨時簇首的AMRP，若該節點的AMRP最小，則該節點就被推舉為最終簇首；否則，該節點的CHprob×2，并與1相比較，將兩者中的較小值賦予CHprob進行下一輪迭代，直到CHprob為1，此時迭代結束。若該節點的鄰居節點中沒有臨時簇首，則該節點按照一定的概率成為臨時簇首。

2.3.3分簇完成若臨時簇首的鄰居節點中沒有臨時簇首或其他臨時簇首的AMRP都較該節點大，則該臨時簇首就宣布自己成為最終的簇首。若普通節點處于多個簇的覆蓋范圍，則加入簇首AMRP最小的簇。

本文研究的LHEED分簇算法具有以下特點： 節點先根據自身的地理位置計算出自己的最優簇半徑，然后，根據最優簇半徑進行動態分簇，在有限迭代次數內完成簇首的選擇。

2.4簇間通信

圖3所示為LHEED分簇算法的簇間通信過程。圖中，d(q，j)、d(q，k)為簇首節點q與j、k間的距離，dto-sink(q)、dto-sink(j)、dto-sink(k)分別為簇首節點q、j、k到sink節點的距離。利用LHEED分簇算法完成節點的分簇后，普通節點將采集到的數據傳輸給簇首節點，由簇首節點通過中繼簇首以多跳的方式將數據傳輸到sink節點。當簇首節點q向sink節點傳輸數據時，假設候選中繼簇首節點為j、k。由于簇首節點發送的能耗與該節點距sink節點的距離有很大關系，簇首之間的通信距離應小于d0，本文所研究的網絡中sink節點在監測區域附近，故WSN的能耗模型采用自由空間模型。圖3中，簇首節點q通過簇首j向sink節點傳輸單位bit數據消耗的能量為

(5)

圖3　LHEED算法中的簇間通信Fig.3　Communication between clusters and clusters of LHEED

q的路由代價也就越小。由于簇首節點通過多跳路由的方式向sink節點傳輸數據，故在選擇中繼簇首時應考慮該節點的剩余能量，以及其與sink節點的距離。基于此，本文引入了簇首間的路由通信代價函數

(6)

式中，β、λ分別為距離均衡因子、能量均衡因子，最優值由仿真實驗得出；Emax(j)為中繼簇首j的最大能量。每個簇首依次計算其到其他簇首的路由通信代價，cost(q，j)大的簇首節點將更容易成為簇首節點的中繼簇首。

分簇完成后，在開始傳送數據之前所有簇首節點向全網中節點廣播一條包含其節點ID、剩余能量和至sink節點距離的信息。

3仿真驗證與分析

為分析LHEED算法的性能，分析該算法與HEED算法的網絡拓撲結構，比較其與HEED-M及HEED算法的節點存活個數，本文使用MATLAB軟件作為仿真平臺，在100m×100m的區域內，取100個節點進行仿真實驗。實驗參數如表1所示。

表1　試驗參數Tab.1　Experimental parameters

圖4給出了HEED和LHEED分簇算法的網絡拓撲結構。由圖可見，LHEED分簇算法中采用基于地理位置的非均勻分簇，所形成的網絡拓撲結構與HEED分簇算法不同。HEED算法中，簇首節點的分布是隨機的，簇的大小也都相同。而LHEED算法中，簇的大小根據簇首節點與sink間的距離動態地調整，簇首節點距匯聚節點較近，則其簇半徑較小；簇首節點距匯聚節點較遠，則其簇半徑較大。由于α的取值直接影響最優簇半徑，進而對網絡的拓補結構產生影響，通過大量仿真實驗得到當α=0.6時，網絡分簇比較均衡(見圖4(b))。

圖4　HEED和LHEED分簇算法的網絡拓撲結構Fig.4　Network topology of HEED and LHEED clustering algorithm

圖5給出了LHEED、HEED-M和HEED分簇算法的存活節點數比較。由圖可知，HEED算法中能量消耗最快，這是由于簇首節點與sink節點直接通信造成的。而在HEED-M算法中，簇首節點與sink節點采用多跳路由的方式通信，故能量消耗次之。在LHEED算法中，簇首節點距sink節點較近，則其簇半徑較小；簇首節點距sink節點較遠，則其簇半徑較大。由于簇首節點在接收成員節點傳輸數據和傳輸其他簇首節點發送來的數據時，都要消耗能量，且當簇半徑較小時，其覆蓋的成員節點就少，所消耗的能量就較少；而簇半徑較大時，其覆蓋的成員節點就多，所消耗的能量就較多；故距離sink節點近的簇首節點在接收成員節點傳輸數據上的能量消耗就較少，為距離sink節點遠的簇首轉發數據預留了能量；同時，由于使用了路由代價函數來選擇中繼簇首，故該算法的能量消耗最慢。由大量仿真實驗表明，當β=0.6、λ=0.4時能量消耗最慢。

圖5　3種算法的存活節點數比較Fig.5　Comparison of three kinds of algorithm in the number of surviving nodes

表2給出了3種算法節點運行周期的比較。由表可見，LHEED分簇算法運行周期最長，HEED-M分簇算法次之，HEED分簇算法運行周期最短。這是由于LHEED分簇算法采用非均勻分簇機制有效地均衡了網絡的能量消耗；HEED-M分簇算法雖采用多跳路由的方式傳輸數據，但是也加重了內層節點負擔；HEED分簇算法由于簇首節點與sink節點直接通信，使遠離sink節點的簇首因能量消耗過快而較早死亡。

表2　3種算法節點運行周期的比較Tab.2　Comparison of three kinds of algorithms of node operation cycle

4結語

本文研究了基于地理位置的HEED非均勻分簇算法，根據簇首節點距匯聚節點的距離動態調整簇半徑的大小，距匯聚節點近的簇首簇半徑較小，距匯聚節點遠的簇首，簇半徑較大，通過調整成簇半徑來均衡網絡的能量消耗，簇間通信也考慮到節點剩余能量和地理位置，從而有效的延長了網絡的壽命。本文未能考慮整個網絡的連通性[16]，以及節點密度大的地區節點間的干擾，這些將在以后的工作中展開研究。

參考文獻

[1]YANG Shuang Hua.Wireless Sensor Networks： Principles，Design and Applications[M].[S.L.]Springer，2014： 7-15.

[2]宋寧博.基于能量優化的無線傳感器網絡分簇路由協議研究[D].重慶： 重慶大學，2014： 24-31.

[3]HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy-Efficient communication protocol for wireless microsensor networks[C]∥Proceedings of the 33rd Annual Hawaii International Conference on System Science(HICSS 2000).[S.L.]: IEEE，2000: 1-10.

[4]YOUNIS O，FAHMY S.Heed： A hybrid，Energy-efficient，Distributed clustering approach for ad-hoc sensor networks[J].IEEE Transactions on Mobile Computing，2004，3(4)： 366-379.

[5]姚新兵, 王向東.一種基于HEED的簇首多跳融合路由算法[J].通信技術，2011，44(4)： 106-108，111.

[6]李晶，史杏榮.無線傳感器網絡中改進的 HeeD路由協議[J].計算機工程與應用，2007，43(25)： 165-167.

[7]王秀花，張國榮.無線傳感器網絡中基于HEED的多層分簇路由算法[J].甘肅聯合大學學報(自然科學版)，2011，25(1)： 78-81，90.

[8]尹安，汪秉文，戴志誠，等.無線傳感器網絡HEED分簇協議的研究與改進[J].小型微型計算機系統，2010，31(10)： 2002-2006.

[9]陳良文.無線傳感器網絡分簇式路由算法研究與改進[D].合肥： 安徽理工大學，2014.

[10]劉佳，范書瑞，劉艷萍，等.基于非均勻分簇和信息熵的無線傳感網絡路由算法[J].傳感技術學報，2015，28(12)： 1867-1872.

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

[12]康瓊.無線傳感器網絡中分簇算法的研究[D].長春： 吉林大學，2013： 10-12.

[13]趙海榮.無線傳感器網絡能量高效的分簇路由協議研究[D].上海： 東華大學，2013： 39-41.

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

[15]張瑞華，賈智平，程合友，等.基于非均勻分簇和最小能耗的無線傳感網絡路由算法[J].上海交通大學學報(自然科學版)，2012，46(11)： 1774-1778.

[16]孫毅，孫躍，曾璐琨，等.基于最優連通功率控制的WSNs跨層路由優化算法[J].傳感器與微系統，2014，33(11)： 135-138.

收稿日期：2016-04-17

基金項目：上海市經濟和信息化委員會專項資金項目資助(12AZ22)

作者簡介：渠帥軍(1991-)，男，碩士生，主要研究方向為無線傳感器網絡路由算法，E-mail： 523078212@qq.com

文章編號2095-0020(2016)03-0170-06

中圖分類號TP 212.9

文獻標識碼A

HEED Non-uniform Clustering Algorithm Based on Geographic Location

QUShuaijun，LüHongfang，ZHAOJing

(School of Electrical Engineering, Shanghai Dianji University, Shanghai 201306, China)

AbstractFor HEED-M clustering algorithm, cluster head nodes and sink node communicate in a multi-hop routing way so that energy easily depletes prematurely near the sink node more, causing system failure. To solve the problem, this paper proposes a HEED non-uniform clustering algorithm based on geographic location. The algorithm dynamically adjusts size of radius of the cluster according to the distance between cluster head nodes and sink node. Cluster of the head nodes near the sink node is small, and that of the head nodes far from the sink node is large. This way, energy consumption of the network is balanced effectively. Simulation results show that the algorithm is effective in prolonging the network life.

Keywordsgeographic location; HEED; non-uniform clustering; radius of cluster