基于非均勻分簇和信息熵的無線傳感網(wǎng)絡(luò)路由算法*

劉　佳，范書瑞，2，劉艷萍*，劉建龍，彭明莎，郭海紅

（1.河北工業(yè)大學(xué)電子信息工程學(xué)院，天津300401；2.昆士蘭大學(xué)信息技術(shù)與電氣工程系，澳大利亞昆士蘭4072；3.中國(guó)石油華北石化公司三聯(lián)合運(yùn)行部，河北任丘62550）

基于非均勻分簇和信息熵的無線傳感網(wǎng)絡(luò)路由算法*

劉佳1，范書瑞1，2，劉艷萍1*，劉建龍3，彭明莎1，郭海紅1

（1.河北工業(yè)大學(xué)電子信息工程學(xué)院，天津300401；2.昆士蘭大學(xué)信息技術(shù)與電氣工程系，澳大利亞昆士蘭4072；3.中國(guó)石油華北石化公司三聯(lián)合運(yùn)行部，河北任丘62550）

針對(duì)無線傳感網(wǎng)絡(luò)分簇算法中能量分布不均衡導(dǎo)致的“熱區(qū)”問題，提出一種基于非均勻分簇和信息熵的路由算法。在簇頭選舉和競(jìng)爭(zhēng)半徑計(jì)算過程中綜合考慮節(jié)點(diǎn)能量、節(jié)點(diǎn)密度和節(jié)點(diǎn)距基站距離，均衡簇頭能耗以延長(zhǎng)生存時(shí)間。采用簇間單跳多跳混合通信的路由規(guī)則，減少簇間通信能耗。對(duì)節(jié)點(diǎn)信息熵進(jìn)行數(shù)據(jù)融合，引入融合權(quán)重系數(shù)減小數(shù)據(jù)融合的不確定性，提高數(shù)據(jù)融合效率。仿真結(jié)果表明，與LEACH、EEUC和EBUCA相比，該算法能夠有效均衡網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。

無線傳感網(wǎng)絡(luò)；能量高效；非均勻分簇；路由協(xié)議；信息熵

EEACC：6250doi：10.3969/j.issn.1004-1699.2015.12.023

無線傳感網(wǎng)絡(luò)WSNs（Wireless Sensor Networks）是由分布在被監(jiān)測(cè)區(qū)域內(nèi)的大量廉價(jià)的傳感器節(jié)點(diǎn)以自組織的形式構(gòu)成的網(wǎng)絡(luò)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)被監(jiān)測(cè)對(duì)象的信息，并發(fā)送給遠(yuǎn)端的基站。由于無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)能源的有限性對(duì)網(wǎng)絡(luò)性能造成嚴(yán)重影響，很多文獻(xiàn)通過調(diào)度控制優(yōu)化［1-2］。但是延長(zhǎng)網(wǎng)絡(luò)生命周期是WSNs協(xié)議的重要設(shè)計(jì)目標(biāo)，主要方法之一就是設(shè)計(jì)高效節(jié)能的路由協(xié)議［3］。已有研究結(jié)果表明［4］，分簇路由協(xié)議可有效降低網(wǎng)絡(luò)能量消耗和延長(zhǎng)網(wǎng)絡(luò)生命周期。LEACH［5］（Low Energy Adaptive Clustering Hierarchy）是較早提出的低能量自適應(yīng)分簇路由算法，有效的延長(zhǎng)了網(wǎng)絡(luò)的生命周期，但是其單跳通信方式使遠(yuǎn)離基站的簇頭能量消耗不均衡。文獻(xiàn)［6］采用多跳路由通信方式節(jié)省節(jié)點(diǎn)能量，但基站附近節(jié)點(diǎn)由于大量任務(wù)轉(zhuǎn)發(fā)，導(dǎo)致能耗過多出現(xiàn)能量空洞（energy hole）。針對(duì)這一問題，文獻(xiàn)［7］提出了EEUC（Energy-Efficient Unequal Clustering）算法，根據(jù)節(jié)點(diǎn)到基站的距離不同構(gòu)造不同規(guī)模的簇，緩解基站附近節(jié)點(diǎn)“熱區(qū)”問題。EEUC算法候選簇頭的選擇具有隨機(jī)性，不能從整體上減少全網(wǎng)能量消耗從而緩解“熱區(qū)”問題。文獻(xiàn)［8］提出EBUCA算法基于節(jié)點(diǎn)能量、密度對(duì)閾值改進(jìn)，并引入簇頭密度和到基站距離進(jìn)行簇的設(shè)計(jì)，均衡網(wǎng)絡(luò)能耗。文獻(xiàn)［9］基于最小生成樹構(gòu)造傳輸路徑，文獻(xiàn)［10］對(duì)簇間路由進(jìn)行優(yōu)化提出改進(jìn)的簇頭多跳路由協(xié)議。這兩種算法優(yōu)化了路由路徑減少了通信能耗，但是都沒有考慮數(shù)據(jù)發(fā)送之前簇頭進(jìn)行數(shù)據(jù)融合所造成的能耗。為此文獻(xiàn)［11］采用信息熵確定數(shù)據(jù)融合閾值，進(jìn)行簇內(nèi)數(shù)據(jù)融合，節(jié)約節(jié)點(diǎn)能耗。

綜合以上算法所存在的問題，本文提出一種基于非均勻分簇和信息熵?cái)?shù)據(jù)融合方法的路由算法。算法根據(jù)節(jié)點(diǎn)能量、節(jié)點(diǎn)距基站距離和節(jié)點(diǎn)密度三種參數(shù)，設(shè)計(jì)權(quán)衡系數(shù)α平衡三者之間的關(guān)系。基于權(quán)衡系數(shù)設(shè)計(jì)權(quán)值公式，選擇權(quán)值大的節(jié)點(diǎn)作為簇首。減少基站附近節(jié)點(diǎn)能量消耗，均衡全網(wǎng)能量負(fù)載。并對(duì)競(jìng)爭(zhēng)半徑公式基于節(jié)點(diǎn)距離、能量和密度進(jìn)行改進(jìn)，減少簇頭能耗并延長(zhǎng)網(wǎng)絡(luò)生命周期。簇間采用單跳多跳的混合通信方式選擇簇頭下一跳的最優(yōu)路徑，進(jìn)一步減輕簇頭的負(fù)擔(dān)。利用節(jié)點(diǎn)信息熵進(jìn)行數(shù)據(jù)融合，引入融合權(quán)重系數(shù)減小數(shù)據(jù)融合的不確定性，提高算法數(shù)據(jù)融合效率以減少節(jié)點(diǎn)能耗。

1　系統(tǒng)模型

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

本文對(duì)網(wǎng)絡(luò)模型做如下假設(shè)：①N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在網(wǎng)路檢測(cè)區(qū)域，匯聚節(jié)點(diǎn)位于檢測(cè)區(qū)域附近。②每個(gè)節(jié)點(diǎn)有自己的ID，節(jié)點(diǎn)通過信號(hào)強(qiáng)度指示（RSSI）可感知自身的能量和坐標(biāo)信息，匯聚節(jié)點(diǎn)sink可感知所有節(jié)點(diǎn)的位置。③網(wǎng)絡(luò)以輪為周期，每輪包括分簇階段和數(shù)據(jù)傳輸階段。簇頭選擇之后，簇內(nèi)節(jié)點(diǎn)采集數(shù)據(jù)傳輸給簇頭進(jìn)行數(shù)據(jù)融合之后發(fā)送給匯聚節(jié)點(diǎn)Sink。

1.2能量消耗模型

文中采用經(jīng)典的無線通信模型［12］，節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)時(shí)消耗的能量為：

節(jié)點(diǎn)接收kbit數(shù)據(jù)時(shí)的能耗為：

其中，d為節(jié)點(diǎn)間傳輸距離，εfs、εamp為信道模型功率放大系數(shù)。選擇哪種損耗模型是由β值決定。若節(jié)點(diǎn)傳輸距離較近d＜d0，則β=2，采用空間信道模型；當(dāng)節(jié)點(diǎn)傳輸距離較遠(yuǎn)d＞d0，則β=4，采用多徑衰落信道模型。d0為傳輸距離閾值系數(shù)

2　算法

2.1簇頭選舉與簇的建立

算法通過節(jié)點(diǎn)簇頭的競(jìng)爭(zhēng)方式選舉簇頭，基于節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)到基站距離和節(jié)點(diǎn)密度的權(quán)衡系數(shù)設(shè)計(jì)簇頭的選舉公式。在無線傳感網(wǎng)絡(luò)中距離匯聚節(jié)點(diǎn)近的簇首由于承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)重而過早死亡，形成“熱區(qū)”問題。本文通過權(quán)衡節(jié)點(diǎn)的動(dòng)態(tài)能量、節(jié)點(diǎn)到基站距離和節(jié)點(diǎn)密度進(jìn)行簇頭競(jìng)爭(zhēng)選舉，均衡網(wǎng)絡(luò)負(fù)載能量，防止匯聚節(jié)點(diǎn)附近的節(jié)點(diǎn)過早死亡。

2.1.1網(wǎng)絡(luò)初始化

首先對(duì)網(wǎng)絡(luò)進(jìn)行初始化，匯聚節(jié)點(diǎn)通過RSSI感知自身位置和節(jié)點(diǎn)的位置，節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)的最遠(yuǎn)距離dmax和最近距離dmin。假設(shè)監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)經(jīng)歷輪數(shù)為n，初始能量為E0，節(jié)點(diǎn)當(dāng)前能量為Ei，距離基站的距離為di，節(jié)點(diǎn)密度為Qi。

2.1.2簇頭選舉

節(jié)點(diǎn)剩余能量與節(jié)點(diǎn)距離基站的距離和節(jié)點(diǎn)密度三者的權(quán)衡系數(shù)α為：

其中節(jié)點(diǎn)密度Qi的定義為：

其中，Neighbor（i）為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)個(gè)數(shù)，Neighbor（alive）為當(dāng)前網(wǎng)絡(luò)的存活節(jié)點(diǎn)。

權(quán)衡系數(shù)α為節(jié)點(diǎn)剩余能量、距基站距離、節(jié)點(diǎn)密度之間的融合系數(shù)，取值（0，1）。權(quán)衡系數(shù)是為了對(duì)能量、密度、距離三個(gè)參數(shù)起到相對(duì)平衡的作用。節(jié)點(diǎn)能量大但距基站遠(yuǎn)的節(jié)點(diǎn)，可能比能量較小但距基站較近的節(jié)點(diǎn)有更大的概率當(dāng)選為簇頭。可以減少基站附近節(jié)點(diǎn)能量消耗過多，避免“熱區(qū)”效應(yīng)。同樣距基站距離相同但節(jié)點(diǎn)密度高、剩余能量小的節(jié)點(diǎn)，有可能比節(jié)點(diǎn)密度小、剩余能量高的節(jié)點(diǎn)當(dāng)選簇頭的概率大。權(quán)衡系數(shù)α可以平衡節(jié)點(diǎn)的能量、距離和密度之間的關(guān)系，減少匯聚節(jié)點(diǎn)附近節(jié)點(diǎn)的能量消耗，均衡全網(wǎng)能量負(fù)載。

在簇頭選擇階段，如果節(jié)點(diǎn)收到一個(gè)簇頭的消息則加入，如果收到多個(gè)簇頭節(jié)點(diǎn)信息則計(jì)算各簇頭節(jié)點(diǎn)的競(jìng)爭(zhēng)權(quán)值，選擇競(jìng)爭(zhēng)權(quán)值大的簇頭節(jié)點(diǎn)加入簇。簇頭競(jìng)爭(zhēng)權(quán)值公式為：

其中Wi為節(jié)點(diǎn)競(jìng)爭(zhēng)簇頭的權(quán)值，α為節(jié)點(diǎn)、能量、密度的權(quán)衡系數(shù)，α1+α2+α3=α，α1=0.4α，α2=0.3α，α3=0.3α。權(quán)值Wi分別由三項(xiàng)構(gòu)成，第一項(xiàng)為節(jié)點(diǎn)剩余能量和初始能量的比值項(xiàng)，使剩余能量大的節(jié)點(diǎn)當(dāng)選為簇頭的概率大，為簇頭通信提供更多的能量。第二項(xiàng)為節(jié)點(diǎn)距基站距離項(xiàng)，使節(jié)點(diǎn)距基站距離近的節(jié)點(diǎn)當(dāng)選為簇頭的概率大，從而減少簇頭與基站之間的通信能耗。第三項(xiàng)為節(jié)點(diǎn)密度項(xiàng)，使得密度大的節(jié)點(diǎn)當(dāng)選為簇頭的概率大，減少簇內(nèi)通信能量消耗。Ei為節(jié)點(diǎn)當(dāng)前動(dòng)態(tài)能量，E0為節(jié)點(diǎn)初始能量，Qi為節(jié)點(diǎn)密度，di為節(jié)點(diǎn)距基站距離，dmax為網(wǎng)絡(luò)節(jié)點(diǎn)距基站的最遠(yuǎn)距離，N為傳感器節(jié)點(diǎn)總數(shù)，Kc為一定區(qū)域內(nèi)節(jié)點(diǎn)最優(yōu)簇頭數(shù)［13］，根據(jù)網(wǎng)絡(luò)覆蓋范圍，選擇合理的簇首數(shù)，降低整個(gè)網(wǎng)絡(luò)的簇間通信和簇內(nèi)通信的能耗，從而減少整個(gè)網(wǎng)絡(luò)能耗，以達(dá)到延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的目的。

N為節(jié)點(diǎn)數(shù)量，εfs、εamp為能量損耗系數(shù)，M為覆蓋區(qū)域面積，dtoBS表示網(wǎng)絡(luò)中心點(diǎn)到匯聚節(jié)點(diǎn)的距離。

2.1.3競(jìng)爭(zhēng)半徑

簇頭根據(jù)競(jìng)爭(zhēng)半徑形成新的簇，競(jìng)爭(zhēng)半徑的設(shè)計(jì)基于節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)距基站距離以及節(jié)點(diǎn)密度。為了減少基站附近節(jié)點(diǎn)的能量消耗過多導(dǎo)致的“熱區(qū)”問題，靠近基站的節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)重，因此為了防止節(jié)點(diǎn)過早死亡在保證節(jié)點(diǎn)剩余能量高的同時(shí)，縮小競(jìng)爭(zhēng)半徑。同時(shí)節(jié)點(diǎn)密度越大，簇內(nèi)能量消耗會(huì)越多，為了防止簇頭節(jié)點(diǎn)過早死亡，競(jìng)爭(zhēng)半徑就越小。競(jìng)爭(zhēng)半徑RC的計(jì)算公式為：

其中：R為傳感器節(jié)點(diǎn)的最大覆蓋半徑，c為（0，1）之間的常數(shù)，系數(shù)最優(yōu)值由仿真實(shí)驗(yàn)得出。

2.2路由規(guī)則

為了避免“熱區(qū)”問題和減少簇間數(shù)據(jù)傳輸能耗，本算法采用簇內(nèi)單跳通信，簇間單跳多跳的通信方式。若簇頭和基站之間距離小于單跳通信閾值d0則選擇單跳方式，否則采用多跳通信方式。在簇頭向基站傳輸數(shù)據(jù)的過程中，簇頭先對(duì)簇內(nèi)數(shù)據(jù)進(jìn)行融合處理，然后從鄰居節(jié)點(diǎn)中選擇一個(gè)簇頭作為中繼節(jié)點(diǎn)，中繼節(jié)點(diǎn)負(fù)責(zé)將融合好的數(shù)據(jù)轉(zhuǎn)發(fā)到基站。主要路由規(guī)則為：

①首先，簇頭給競(jìng)爭(zhēng)范圍內(nèi)的節(jié)點(diǎn)廣播消息。消息包括廣播簇頭ID、簇內(nèi)節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)剩余能量和距基站的距離。

②對(duì)于傳感器節(jié)點(diǎn)i和j，若節(jié)點(diǎn)i位于節(jié)點(diǎn)j的通信范圍內(nèi)，并且節(jié)點(diǎn)j位于節(jié)點(diǎn)i的通信范圍內(nèi)，則稱節(jié)點(diǎn)i和j互為鄰居節(jié)點(diǎn)。鄰居簇頭節(jié)點(diǎn)根據(jù)接收到的廣播信息，建立一張簇頭與鄰居簇頭距離的信息表，如表1所示。

表1　R鄰居簇頭節(jié)點(diǎn)信息表

③簇頭Hi采用貪婪算法在鄰居簇頭集合中選擇下一跳節(jié)點(diǎn)，候選節(jié)點(diǎn)中具有最小代價(jià)函數(shù)的節(jié)點(diǎn)被選為下一跳節(jié)點(diǎn)。代價(jià)函數(shù)定義如式（8）所示：

其中，簇頭Hj為簇頭Hi的鄰居簇頭，dCHj為簇頭Hj到基站的距離，maxdCHi為簇頭Hi鄰居簇頭中到基站距離的最大值。ECHj為簇頭Hj的當(dāng)前剩余能量，maxECHi為簇頭Hi鄰居簇頭中當(dāng)前剩余能量的最大值。NCHj為簇頭Hj簇內(nèi)節(jié)點(diǎn)數(shù)，maxNCHi為簇頭Hi鄰居簇頭中簇內(nèi)節(jié)點(diǎn)數(shù)的最大值。α、β、γ為權(quán)重因子，α+β+γ=1。代價(jià)函數(shù)的設(shè)計(jì)主要考慮到：（a）第一項(xiàng)首先考慮的是下一跳節(jié)點(diǎn)的位置，為了減少通信能耗，多跳路由應(yīng)該盡量選擇較短路徑。（b）第二項(xiàng)選擇剩余能量較大的簇頭作為下一跳節(jié)點(diǎn)，因?yàn)閿?shù)據(jù)轉(zhuǎn)發(fā)需要消耗更多的能量，所以盡量選擇能量大的簇頭作為下一跳節(jié)點(diǎn)。（c）第三項(xiàng)選擇簇內(nèi)成員節(jié)點(diǎn)較少的節(jié)點(diǎn)作為下一跳，簇內(nèi)節(jié)點(diǎn)少則簇內(nèi)通信能量少，簇頭有更多的能量用來完成數(shù)據(jù)轉(zhuǎn)發(fā)。

④如果簇頭Hi的下一跳節(jié)點(diǎn)為節(jié)點(diǎn)本身，則直接發(fā)送數(shù)據(jù)到基站；否則，簇頭將數(shù)據(jù)發(fā)送到下一跳節(jié)點(diǎn)，所有簇頭都找到下一跳節(jié)點(diǎn)后，簇間多跳路由建立完成。

2.3基于信息熵的數(shù)據(jù)融合

本文基于節(jié)點(diǎn)的信息熵對(duì)簇內(nèi)數(shù)據(jù)進(jìn)行融合，引入融合權(quán)重系數(shù)減小數(shù)據(jù)融合的不確定性，提高算法數(shù)據(jù)融合效率。信息熵是一種基于信息表現(xiàn)特征的統(tǒng)計(jì)形式，它反映信息中平均信息量的多少［14］。信息熵為信源全局的統(tǒng)計(jì)特征，表示總體的不確定性。節(jié)點(diǎn)的信息熵值反映節(jié)點(diǎn)數(shù)據(jù)的相似程度，是節(jié)點(diǎn)數(shù)據(jù)融合的有效依據(jù)。

2.3.1對(duì)數(shù)據(jù)進(jìn)行預(yù)處理

首先，由于環(huán)境等各種因素會(huì)給節(jié)點(diǎn)數(shù)據(jù)造成誤差，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。采集節(jié)點(diǎn)數(shù)據(jù)，利用格羅貝斯準(zhǔn)則對(duì)數(shù)據(jù)進(jìn)行處理。設(shè)數(shù)據(jù)x1，x2，x1，…，xn服從正態(tài)分布。

格羅貝斯統(tǒng)計(jì)分布為：

根據(jù)所給定的顯著水平（α=0.05）通過查表法得出統(tǒng)計(jì)量臨界值g0（n，α）。若節(jié)點(diǎn)數(shù)據(jù)測(cè)量值的統(tǒng)計(jì)量滿足g0≤g0（n，α），則測(cè)量數(shù)據(jù)值有效；反之，無效。

2.3.2計(jì)算節(jié)點(diǎn)二維信息熵

設(shè)C為傳感網(wǎng)絡(luò)中的一個(gè)簇，簇內(nèi)節(jié)點(diǎn)數(shù)為N，簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)采集時(shí)間長(zhǎng)度為M。節(jié)點(diǎn)數(shù)據(jù)預(yù)處理后將符合條件的數(shù)據(jù)傳送給簇頭，簇頭接收到的數(shù)據(jù)為Cij=（ci1，ci2，…，cim；其中i=1，2，…，n；j=1，2，…m）。選擇簇內(nèi)節(jié)點(diǎn)的加權(quán)數(shù)據(jù)均值作為空間特征量，分別計(jì)算節(jié)點(diǎn)i的加權(quán)數(shù)據(jù)均值di和簇內(nèi)節(jié)點(diǎn)的加權(quán)數(shù)據(jù)均值di'，組成二元特征組（di，di'）。聯(lián)合概率密度為：

簇內(nèi)的二維信息熵為：

其中Hmax為簇內(nèi)節(jié)點(diǎn)二維信息熵的最大值，Hmin為簇內(nèi)節(jié)點(diǎn)二維信息熵的最小值。

2.3.3對(duì)數(shù)據(jù)進(jìn)行融合處理

利用信息熵融合系數(shù)對(duì)數(shù)據(jù)進(jìn)行融合，對(duì)于確定性不同的數(shù)據(jù)分配不同融合權(quán)重系數(shù)。發(fā)生概率大的數(shù)據(jù)則其不確定性小，分配大的權(quán)重系數(shù)；發(fā)生概率小的數(shù)據(jù)則其不確定性大，分配小的權(quán)重系數(shù)。為不同的數(shù)據(jù)分配不同的融合權(quán)重系數(shù)，減小融合結(jié)果的不確定性。

①簇內(nèi)節(jié)點(diǎn)的自信息量為：

信息量比率為：

②信息熵融合權(quán)重系數(shù)為：

③對(duì)數(shù)據(jù)進(jìn)行融合

3　算法仿真及分析

為了驗(yàn)證改進(jìn)算法的性能，對(duì)改進(jìn)算法和LEACH算法、EEUC算法、EBUCA算法進(jìn)行多項(xiàng)性能對(duì)比。本文在MATLAB平臺(tái)下進(jìn)行仿真分析，將400個(gè)節(jié)點(diǎn)隨機(jī)分布在200 m×200 m的區(qū)域中。實(shí)驗(yàn)參數(shù)如表2所示。

表2　R實(shí)驗(yàn)參數(shù)

首先對(duì)4種算法的生命周期進(jìn)行比較，如圖1所示，改進(jìn)算法比LEACH算法、EEUC算法和EBUCA算法有效延長(zhǎng)了網(wǎng)絡(luò)生命周期。改進(jìn)算法的生命周期比LEACH算法延長(zhǎng)約2.5倍，比EEUC算法延長(zhǎng)約50%，比EBUCA算法延長(zhǎng)約14%。

圖2給出了4種算法的死亡節(jié)點(diǎn)分別為1，100，200，300，400時(shí)所對(duì)應(yīng)網(wǎng)絡(luò)周期運(yùn)行輪數(shù)。LEACH、EEUC、EBUCA算法和改進(jìn)算法出現(xiàn)首個(gè)死亡節(jié)點(diǎn)的輪數(shù)分別為304輪、530輪、600輪和780輪，改進(jìn)算法有效的延長(zhǎng)了網(wǎng)絡(luò)的穩(wěn)定期（首個(gè)節(jié)點(diǎn)死亡時(shí)間）。改進(jìn)算法最后一個(gè)節(jié)點(diǎn)死亡輪數(shù)為1 610輪，LEACH、EEUC和EBUCA分別為630輪、1 080輪和1 410輪。改進(jìn)算法有效延長(zhǎng)了網(wǎng)絡(luò)的穩(wěn)定期和生命周期。

圖1　R網(wǎng)絡(luò)生命周期對(duì)比

圖2　R死亡節(jié)點(diǎn)對(duì)比

隨機(jī)選取10輪運(yùn)行結(jié)果對(duì)比4種算法的全網(wǎng)簇頭能耗之和。如圖3所示，LEACH算法能耗最高，因?yàn)槠洳捎脝翁酚汕掖仡^分布不均勻。EEUC算法、EBUCA和改進(jìn)算法簇首能耗較低，EEUC算法采用多跳路由規(guī)則減少簇頭能量消耗，EBUCA算法基于節(jié)點(diǎn)密度優(yōu)化簇首選擇，使簇首能耗減少。本文改進(jìn)算法中簇頭采用單跳和多跳結(jié)合的路由規(guī)則，降低了簇頭能耗。

圖3　簇首能耗對(duì)比

圖4R對(duì)比了4種算法的網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量均值隨網(wǎng)絡(luò)周期的變化情況，改進(jìn)算法的節(jié)點(diǎn)剩余能量均值一直明顯高于其他三種算法，而且能量消耗趨近于直線。這表明改進(jìn)算法整個(gè)網(wǎng)絡(luò)生命周期中的能量消耗較為均衡，有效避免某些節(jié)點(diǎn)負(fù)載過度導(dǎo)致的“熱區(qū)”問題。

圖4　R網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量均值對(duì)比

4　結(jié)論

本文提出一種基于非均勻分簇和信息熵的無線傳感網(wǎng)絡(luò)路由算法，主要包括簇頭權(quán)衡系數(shù)和權(quán)值公式的設(shè)計(jì)、競(jìng)爭(zhēng)半徑的改進(jìn)、路由規(guī)則的設(shè)計(jì)、基于信息熵的數(shù)據(jù)融合，算法在延長(zhǎng)網(wǎng)絡(luò)生命周期的同時(shí)能夠減少節(jié)點(diǎn)能耗。通過仿真結(jié)果表明，改進(jìn)算法減少了簇頭能耗，顯著延長(zhǎng)了網(wǎng)絡(luò)的穩(wěn)定期和生命周期，能夠均衡節(jié)點(diǎn)能耗有效避免“熱區(qū)”問題。

［1］Bachir A，Dohler M，Watteyne T，et al.MAC Essentials for Wireless Sensor Networks［J］.IEEE Communications Surveys&Tutorials，2010，12（2）：222-248.

［2］任苗苗，范書瑞，王悅良.一種時(shí)分簇調(diào)度算法的實(shí)現(xiàn)［J］.傳感技術(shù)學(xué)報(bào)，2015，28（7）：1073-1077.

［3］Shuang-Hua Yang.Wireless Sensor Networks：Principles，Design and Applications［M］.London：Springer，2014：7-47.

［4］Santar Pal Singh，Sharma S C.A Survey on Cluster Based Routing Protocols in Wireless Sensor Networks［J］.Procedia Computer Scienc，2015（45）：687-695.

［5］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocols for Wirelesss Microsensor Networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Washington，DC：IEEE，2000：3005-3014.

［6］Mhatre V，Rosenberg C.Design Guidelines for Wireless Sensor Networks：Communication，Clustering and Aggregation［J］.Ad Hoc Networks，2004，2（1）：45-63.

［7］Chengfa Li，Mao Ye，Guihai Chen，et al.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks［C］// Proceedings of the IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems.Washington DC：IEEE，2005：7-10.

［8］盧先領(lǐng)，王瑩瑩，王洪斌，等.無線傳感網(wǎng)絡(luò)能量均衡的非均勻分簇算法［J］.計(jì)算機(jī)科學(xué)，2013，40（5）：78-81.

［9］張文梅，廖福保.改進(jìn)的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（5）：739～743.

［10］陳炳才，么華卓，楊明川.一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2014，27（3）：373～377.

［11］李懷俊，張學(xué)習(xí).基于二維信息熵的無線傳感網(wǎng)絡(luò)簇內(nèi)數(shù)據(jù)融合方法的研究［J］.計(jì)算機(jī)應(yīng)用研究，2014，31（7）：2171-2174.

［12］彭鐸，黎鎖平，楊喜娟.一種能量高效的無線傳感網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2014，27（12）：1687-1691.

［13］侯華，劉超，周武旸.能量高效均衡的動(dòng)態(tài)分簇路由設(shè)計(jì)［J］.北京郵電大學(xué)學(xué)報(bào)，2013，36（3）：54-59.

［14］唐晨，王汝傳，黃海平，等.基于信息熵的無線傳感網(wǎng)絡(luò)數(shù)據(jù)融合方案［J］.東南大學(xué)學(xué)報(bào)，2008，38（3）：275-279.

A Routing Algorithm for Wsns Based on Uneven Clustering and Entropy Theory*

LIU Jia1，F(xiàn)AN Shurui1，2，LIU Yanping1*，LIU Jianlong3，PENG Mingsha1，GUO Haihong1
（1.School of Electric Information Engineering，Hebei University of Technology，Tianjin 300401，China；2.Information Technology and Electrical Engineering，The University of Queensland，Queensland 4072，Australia；3.PetroChina Huabei Oilfield Company，Three combined operations，Renqiu Hebei 062550，China）

An energy efficient routing algorithm is the major concern in wireless sensor networks（WSNs），especially the hot spot，because of unbalanced energy consumption.Based on uneven clustering and entropy theory，a kind of improved routing algorithm is proposed for solving that problem.In the process of cluster head election and competition radius calculation，node energy，density and distance to BS are considered to effectively balance energy consumption and prolong the life cycle of cluster head nodes.Meanwhile the hybrid rules of single-hop and multi-hop routing is adopted to reduce the energy consumption among clusters.Introducing fusion weight coefficient，information entropy mechanism is used for reducing the uncertainty and improving the efficiency of data fusion.Simulation results show that compared with LEACH，EEUC and EBUCA，the new algorithm can balance energy consumption and prolong the life cycle of wireless sensor networks.

wireless sensor network；energy efficient；uneven clustering；routing protocol；entropy theory

劉佳（1989-），女，研究生，就讀河北工業(yè)大學(xué)通信與信息系統(tǒng)專業(yè)，研究方向?yàn)闊o線傳感網(wǎng)絡(luò)路由算法，344899849@qq.com；

范書瑞（1979-），男，講師，博士，研究方向無線傳感器網(wǎng)絡(luò)和嵌入式系統(tǒng)，fansr@hebut.edu.cn；

劉艷萍（1966-），女，教授，博士，主要研究方向?yàn)橥ㄐ排c信息系統(tǒng)和FPGA，15222893152@163.com。

TP273

A

1004-1699（2015）12-1867-06

項(xiàng)目來源：河北省自然科學(xué)青年基金項(xiàng)目（F2013202102）；國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃立項(xiàng)項(xiàng)目（201410080006）

2015-07-07修改日期：2015-10-15