改進(jìn)LEACH的傳感器網(wǎng)絡(luò)分簇路由算法

潘繼強(qiáng)， 馮永政

(陜西理工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 陜西 漢中 723000)

隨著通訊技術(shù)、 信息技術(shù)的快速發(fā)展, 許多微型傳感器節(jié)點(diǎn)被部署在一個(gè)區(qū)域, 采用自組織、 協(xié)作方式進(jìn)行信息和數(shù)據(jù)的通信, 形成一個(gè)無(wú)線傳感器網(wǎng)絡(luò), 對(duì)目標(biāo)的監(jiān)測(cè)信息進(jìn)行收集, 數(shù)據(jù)采集的成本低, 在工業(yè)、 農(nóng)業(yè)、 軍事等領(lǐng)域應(yīng)用廣泛[1-6]. 在無(wú)線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用中, 通常需要考慮網(wǎng)絡(luò)的安全性、 數(shù)據(jù)的通信成本、 數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性及網(wǎng)絡(luò)能耗等問(wèn)題. 無(wú)線傳感器網(wǎng)絡(luò)通常采用無(wú)線通信方式, 部署在人無(wú)法達(dá)到的環(huán)境中, 而且傳感器節(jié)點(diǎn)的電池能量有限, 節(jié)點(diǎn)能量一旦消耗完畢, 節(jié)點(diǎn)就會(huì)在網(wǎng)絡(luò)失效, 導(dǎo)致數(shù)據(jù)丟失, 因此節(jié)點(diǎn)能耗是無(wú)線傳感器網(wǎng)絡(luò)路由算法的關(guān)鍵[7].

無(wú)線傳感器網(wǎng)絡(luò)路由算法旨在建立一條通信路由, 將節(jié)點(diǎn)、 目標(biāo)與信息最終使用者聯(lián)系起來(lái), 在數(shù)據(jù)傳輸中一些節(jié)點(diǎn)的死亡會(huì)影響數(shù)據(jù)轉(zhuǎn)發(fā), 簇首的死亡會(huì)導(dǎo)致整個(gè)無(wú)線傳感器網(wǎng)絡(luò)過(guò)早失效, 縮短生存時(shí)間[8]. 目前, 無(wú)線傳感器網(wǎng)絡(luò)路由算法主要分為平面型和分層型兩類. 平面型的無(wú)線傳感器網(wǎng)絡(luò)路由算法中傳感器節(jié)點(diǎn)的地位對(duì)等, 沒(méi)有簇首, 所有節(jié)點(diǎn)處于一個(gè)平面, 組網(wǎng)過(guò)程簡(jiǎn)單、 易維護(hù), 由于沒(méi)有管理節(jié)點(diǎn), 全部傳感器節(jié)點(diǎn)參與數(shù)據(jù)傳輸, 節(jié)點(diǎn)能耗大、 能量浪費(fèi)嚴(yán)重, 當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí), 路由算法的動(dòng)態(tài)調(diào)整能力差, 因此只適合小規(guī)模的無(wú)線傳感器網(wǎng)絡(luò), 無(wú)法適應(yīng)當(dāng)前大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用要求[9-11]. 分層型的無(wú)線傳感器網(wǎng)絡(luò)路由算法將整個(gè)網(wǎng)絡(luò)劃分為多個(gè)簇, 每個(gè)簇又包括簇首和普通節(jié)點(diǎn), 因此又稱為分簇路由算法. 簇內(nèi)的普通節(jié)點(diǎn)信息均要發(fā)送到簇首, 簇首對(duì)信息進(jìn)行選擇性收集, 并轉(zhuǎn)發(fā)到基站, 減少數(shù)據(jù)轉(zhuǎn)發(fā)的次數(shù), 節(jié)約節(jié)點(diǎn)能量, 可擴(kuò)展性強(qiáng), 相對(duì)于平面路由算法, 生存時(shí)間明顯延長(zhǎng), 已成為當(dāng)前主要的無(wú)線傳感器網(wǎng)絡(luò)路由算法[12]. 低功耗自適應(yīng)分簇(low energy adaptive clustering hierarchy, LEACH)算法是最經(jīng)典的分簇路由算法， 其以簇為基礎(chǔ), 簇在不斷地重建, 一次簇重建稱為一輪, 但基本的LEACH算法有許多局限性, 如簇首選擇、 能量消耗不均衡等， 因此出現(xiàn)許多改進(jìn)的LEACH算法, 如LEACH-K算法、 LEACH-R算法等, 相對(duì)于LEACH算法, 改進(jìn)算法的性能有一定的提高, 但仍存在不足, 如網(wǎng)絡(luò)生存時(shí)間短、 簇首死亡過(guò)快等[13-15].

針對(duì)當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法的節(jié)點(diǎn)能耗不平均、 節(jié)點(diǎn)過(guò)早死亡等缺陷, 本文提出一種改進(jìn)LEACH的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法. 先引入簇半徑動(dòng)態(tài)調(diào)整方式將網(wǎng)絡(luò)劃分為多個(gè)不均勻的簇, 再綜合簇首的位置和節(jié)點(diǎn)剩余能量選擇每輪中的簇首, 對(duì)數(shù)據(jù)傳輸機(jī)制進(jìn)行優(yōu)化. 仿真測(cè)試結(jié)果表明, 本文改進(jìn)LEACH算法的能耗、 網(wǎng)絡(luò)生存時(shí)間、 節(jié)點(diǎn)能量利用率等性能均顯著優(yōu)于當(dāng)前其他分簇路由算法, 具有較高的實(shí)際應(yīng)用價(jià)值.

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)體系結(jié)構(gòu)

無(wú)線傳感器網(wǎng)絡(luò)的基站常位于監(jiān)測(cè)區(qū)域外部, 負(fù)責(zé)將無(wú)線傳感器網(wǎng)絡(luò)采集的信息發(fā)送給信息最終使用者, 能量不受限制, 具有無(wú)限的通信能力. 在整個(gè)監(jiān)測(cè)區(qū)域內(nèi)有大量傳感器節(jié)點(diǎn), 初始能量相同且能量受限, 在工作過(guò)程中由于能耗完畢而不斷死亡, 位置一旦部署完后即固定不變, 它們可分為簇首和普通節(jié)點(diǎn), 均有一個(gè)編號(hào), 通過(guò)單跳或多跳方式將信息發(fā)給基站. 無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)[16]如圖1所示. 一個(gè)傳感器節(jié)點(diǎn)通常包括4個(gè)功能模塊： 傳感、 數(shù)據(jù)處理、 通信和能量供應(yīng). 傳感模塊主要負(fù)責(zé)數(shù)據(jù)的感知和采集, 將模擬信號(hào)轉(zhuǎn)換為數(shù)字信號(hào)； 數(shù)據(jù)處理模塊主要負(fù)責(zé)數(shù)據(jù)處理, 如數(shù)據(jù)融合去冗余； 通信模塊主要負(fù)責(zé)節(jié)點(diǎn)之間的信息傳輸； 能量供應(yīng)模塊主要負(fù)責(zé)節(jié)點(diǎn)的能量管理. 通信模塊包括發(fā)送、 接收、 空閑和睡眠狀態(tài), 所有模塊的能量如圖2所示. 由圖2可見(jiàn), 節(jié)點(diǎn)在感知與數(shù)據(jù)處理的能量消耗相對(duì)較少, 睡眠狀態(tài)消耗的能量也少, 發(fā)送、 接收、 空閑狀態(tài)下消耗能量較大, 因此降低節(jié)點(diǎn)通信的能耗是延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的關(guān)鍵.

圖1 無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)Fig.1 Topology structure of wireless sensor networks

圖2 傳感器節(jié)點(diǎn)的能量消耗分布Fig.2 Energy consumption distribution of sensor nodes

圖3 無(wú)線通信模型Fig.3 Wireless communication model

1.2 能耗模型

傳感器節(jié)點(diǎn)的無(wú)線通信模型如圖3所示, 包括發(fā)送能耗模型和接收能耗模型. 發(fā)送能耗主要為信號(hào)發(fā)射和信號(hào)放大電路消耗的能量, 接收能耗主要為信號(hào)接收電路消耗的能量[17]. 當(dāng)信號(hào)發(fā)射距離為d時(shí), 發(fā)送和接收kbit數(shù)據(jù)的能量消耗計(jì)算公式為

其中：Ee表示發(fā)射電路能耗；εamp表示信號(hào)放大電路能耗；n表示衰減指數(shù).

2 LEACH算法

LEACH算法的步驟如下.

1) 確定簇首和分簇. 每個(gè)節(jié)點(diǎn)均可成為簇首, 每個(gè)節(jié)點(diǎn)均產(chǎn)生一個(gè)隨機(jī)數(shù)rand( ), 將rand( )與門限閾值T(n)進(jìn)行比較, 若滿足條件rand( )≥T(n), 則該節(jié)點(diǎn)即為簇首,T(n)計(jì)算公式為

(3)

其中:p為簇首的百分?jǐn)?shù)；r為輪數(shù)；G為不是簇首的節(jié)點(diǎn)集.

某個(gè)節(jié)點(diǎn)一旦成為簇首, 就會(huì)向整個(gè)網(wǎng)絡(luò)廣告消息, 不是簇首的節(jié)點(diǎn)會(huì)收到多個(gè)簇首廣播的消息, 加入到接到信號(hào)強(qiáng)度最大的簇首所在的簇, 并向簇首發(fā)送加入信息, 因?yàn)樾盘?hào)強(qiáng)度越大, 表示距離越近, 接發(fā)消息的能耗越少.

2) 建立時(shí)隙表. 完成分簇后, 簇首根據(jù)簇內(nèi)節(jié)點(diǎn)數(shù)產(chǎn)生時(shí)隙表, 每個(gè)節(jié)點(diǎn)只能在自己時(shí)隙內(nèi)向簇首發(fā)送數(shù)據(jù), 否則處于睡眠狀態(tài)以節(jié)約能量.

3) 數(shù)據(jù)發(fā)送. 簇首將接收機(jī)處于開(kāi)啟狀態(tài), 等待各簇成員節(jié)點(diǎn)發(fā)送數(shù)據(jù), 簇首會(huì)對(duì)數(shù)據(jù)進(jìn)行壓縮和融合, 并將數(shù)據(jù)發(fā)送到基站.

圖4 LEACH算法的工作流程Fig.4 Workflow of LEACH algorithm

LEACH算法的工作流程如圖4所示. 由圖4可見(jiàn), LEACH算法采用隨機(jī)方式確定簇首, 簇內(nèi)成員數(shù)量差異較大, 簇首的負(fù)載不均衡, 導(dǎo)致一些簇首過(guò)早死亡, 簇內(nèi)節(jié)點(diǎn)采用單跳方式與簇首進(jìn)行通信, 能耗大, 對(duì)網(wǎng)絡(luò)生存時(shí)間產(chǎn)生不利影響.

3 改進(jìn)LEACH算法

3.1 “熱區(qū)”和“非熱區(qū)”的劃分

基站向目標(biāo)監(jiān)測(cè)區(qū)域廣播消息, 根據(jù)消息將目標(biāo)監(jiān)測(cè)區(qū)域分為多個(gè)子區(qū)域, 與基站距離近的子區(qū)域稱為“熱區(qū)”, 其他區(qū)域稱為“非熱區(qū)”. 每個(gè)節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度確定自己所在區(qū)域, 第i個(gè)子區(qū)域的上下邊界分別為：

(4)

(5)

其中：dmax和dmin分別表示節(jié)點(diǎn)與基站的最大和最小距離;m表示子區(qū)域的數(shù)量.

3.2 簇半徑動(dòng)態(tài)調(diào)整原則

設(shè)簇半徑為R, 節(jié)點(diǎn)密度為p, 則該簇內(nèi)的成員節(jié)點(diǎn)數(shù)為

m=πR2p.

(6)

簇首能量消耗值的計(jì)算公式為

Etotal=Erec+Et=(πR2p×k+l)×Ee+b×(Ee+εampd2),

(7)

其中：b表示簇內(nèi)成員節(jié)點(diǎn)的數(shù)據(jù)量；l表示其他簇首轉(zhuǎn)發(fā)的數(shù)據(jù)量.

由式(7)可知, 簇首能量消耗的大小與簇半徑R和節(jié)點(diǎn)密度p密切相關(guān).R越大, 表示簇內(nèi)信息發(fā)送量越大, 簇首負(fù)載越大; 而p與簇首所在位置相關(guān), 簇首數(shù)量越多, 簇首的密度越大, 可在周圍找到距離近的簇首轉(zhuǎn)發(fā)數(shù)據(jù), 降低簇首能耗. 節(jié)點(diǎn)競(jìng)爭(zhēng)半徑與簇首位置間的關(guān)系[18]為

(8)

其中：d表示簇首與基站的距離;c表示距離對(duì)競(jìng)爭(zhēng)半徑的影響程度. 式(8)只考慮了簇首位置, 而未考慮節(jié)點(diǎn)的剩余能量, 在綜合考慮節(jié)點(diǎn)剩余能量的基礎(chǔ)上, “熱點(diǎn)區(qū)”和“非熱點(diǎn)區(qū)”節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑計(jì)算公式分別為：

其中：Eres表示傳感器節(jié)點(diǎn)剩余能量;Eave表示鄰居節(jié)點(diǎn)的剩余能量平均值;d(si,BS)表示節(jié)點(diǎn)si到基站的距離; ΔR表示競(jìng)爭(zhēng)半徑調(diào)整值;x和m分別表示所在區(qū)域和整個(gè)區(qū)域的節(jié)點(diǎn)數(shù).

在選擇簇首前, 所有節(jié)點(diǎn)都對(duì)自己的競(jìng)爭(zhēng)半徑進(jìn)行自適應(yīng)調(diào)整, 自動(dòng)加入相應(yīng)的簇, 產(chǎn)生多個(gè)不均勻的簇, 防止簇首節(jié)點(diǎn)由于能量過(guò)早消耗完而死亡.

3.3 簇首的選擇

首先根據(jù)rand( )與門限閾值T(n)間的關(guān)系確定候選簇首, 對(duì)一個(gè)候選簇首si, 如果其收到了成為簇首的消息, 則在其競(jìng)爭(zhēng)半徑內(nèi)的節(jié)點(diǎn)均放棄競(jìng)選簇首. 候選簇首確定后, 根據(jù)剩余能量的高低對(duì)候選簇首進(jìn)行排序, 選擇剩余能量最高者作為簇首.

3.4 數(shù)據(jù)通信方式

本文對(duì)無(wú)線網(wǎng)絡(luò)中的數(shù)據(jù)通信方式進(jìn)行優(yōu)化, 流程如下:

1) 若簇首si位于“熱區(qū)”內(nèi), 則其與基站進(jìn)行直接通信, 不需要其他簇首節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā), 從而節(jié)省能量消耗；

2) 若簇首si位于“非熱區(qū)”內(nèi), 則建立一個(gè)鄰簇首集合, 計(jì)算數(shù)據(jù)通信的代價(jià)函數(shù), 選擇值最小的節(jié)點(diǎn)作為數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)sj, 通過(guò)該方式找到一系列的轉(zhuǎn)發(fā)節(jié)點(diǎn), 最后將數(shù)據(jù)發(fā)送到基站, 代價(jià)函數(shù)計(jì)算公式為

(11)

4 仿真分析

4.1 網(wǎng)絡(luò)參數(shù)設(shè)置

為了測(cè)試改進(jìn)LEACH算法的性能, 采用MATLAB 2014作為仿真軟件平臺(tái), 無(wú)線傳感器網(wǎng)絡(luò)的仿真參數(shù)列于表1. 為使改進(jìn)LEACH算法的仿真測(cè)試結(jié)果更有說(shuō)服力, 選擇文獻(xiàn)[19]的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法進(jìn)行對(duì)比測(cè)試.

表1 仿真測(cè)試參數(shù)設(shè)置Table 1 Parameter settings for simulation tests

4.2 網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)對(duì)比

整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)變化曲線如圖5所示. 由圖5可見(jiàn), 相對(duì)文獻(xiàn)[19]的網(wǎng)絡(luò)分簇路由算法, 本文改進(jìn)LEACH算法的第一個(gè)節(jié)點(diǎn)死亡時(shí)間顯著延遲, 這主要是因?yàn)楦倪M(jìn)LEACH算法引入了非均勻分簇方式, 綜合了節(jié)點(diǎn)位置和剩余能量確定簇首, 并對(duì)數(shù)據(jù)通信方式進(jìn)行了改進(jìn), 可大幅度減少節(jié)點(diǎn)的能量消耗, 且減少了簇首負(fù)載, 整個(gè)網(wǎng)絡(luò)生存時(shí)間延長(zhǎng). 圖6為兩種算法網(wǎng)絡(luò)節(jié)點(diǎn)死亡百分?jǐn)?shù)對(duì)比結(jié)果. 由圖6可見(jiàn), 改進(jìn)LEACH算法的第一個(gè)節(jié)點(diǎn)死亡、 50%節(jié)點(diǎn)死亡及所有節(jié)點(diǎn)死亡的時(shí)間都延遲了, 這主要是由于整個(gè)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的利用率得到提高, 延長(zhǎng)了節(jié)點(diǎn)生命周期.

圖5 網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)變化曲線Fig.5 Change curves of number of network survival nodes

圖6 網(wǎng)絡(luò)節(jié)點(diǎn)死亡百分?jǐn)?shù)對(duì)比Fig.6 Comparison of death percentage of network nodes

4.3 網(wǎng)絡(luò)剩余能量對(duì)比

隨著仿真時(shí)間的不斷變化, 整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的剩余能量變化曲線如圖7所示. 由圖7可見(jiàn), 文獻(xiàn)[19]網(wǎng)絡(luò)分簇路由算法的剩余能量小, 表明整個(gè)無(wú)線傳感器網(wǎng)絡(luò)消耗能量較多, 這是因?yàn)閿?shù)據(jù)通信消耗的能量大, 而本文改進(jìn)LEACH算法的剩余能量大, 說(shuō)明整個(gè)無(wú)線傳感器網(wǎng)絡(luò)消耗能量少, 能較好地節(jié)約網(wǎng)絡(luò)能量. 當(dāng)出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)時(shí), 其他傳感器節(jié)點(diǎn)的剩余能量分布如圖8所示. 由圖8可見(jiàn), 當(dāng)出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)時(shí), 文獻(xiàn)[19]網(wǎng)絡(luò)分簇路由算法的剩余能量分布極不平衡, 使節(jié)點(diǎn)死亡的速度加快, 而改進(jìn)LEACH算法的剩余能量分布均衡, 較好地均衡了節(jié)點(diǎn)的能耗.

圖7 網(wǎng)絡(luò)剩余能量的變化曲線Fig.7 Change curves of network residual energy

圖8 第一個(gè)節(jié)點(diǎn)死亡時(shí)其他節(jié)點(diǎn)的剩余能量分布Fig.8 Residual energy distribution of other nodes when the first node died

綜上所述, 為了解決當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法存在的不足, 本文提出了一種改進(jìn)LEACH的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法, 并采用MATLAB 2014仿真軟件進(jìn)行了仿真測(cè)試. 測(cè)試結(jié)果表明, 改進(jìn)LEACH算法較好地解決了節(jié)點(diǎn)過(guò)早死亡的難題, 無(wú)線傳感器網(wǎng)絡(luò)的壽命時(shí)間得以延長(zhǎng), 較好地平衡了各節(jié)點(diǎn)的能量消耗, 整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的性能顯著優(yōu)于當(dāng)前其他路由算法設(shè)計(jì)的無(wú)線傳感器網(wǎng)絡(luò).