無線傳感器網(wǎng)絡LEACH算法的研究與改進

池 濤，嚴浩偉，陳 明

1(上海海洋大學 信息學院，上海 201306)

2(農(nóng)業(yè)部漁業(yè)信息重點實驗室，上海 201306)

1 引 言

物聯(lián)網(wǎng)一般由傳感器節(jié)點部署在監(jiān)控區(qū)域內(nèi)，通過無線通信方式將采集到的信息發(fā)送給技術(shù)人員.由于傳感器節(jié)點通常是一個微型的嵌入式系統(tǒng)，由干電池供電，它的處理能力、存儲能力和通信能力都相對較弱，所以采用合理的調(diào)度算法，節(jié)省節(jié)點的能量以及延長網(wǎng)絡生存時間都十分重要.LEACH(Low Energy Adaptive Clustering Hierachy)算法[1]將網(wǎng)絡變成層次型拓撲結(jié)構(gòu)，數(shù)據(jù)通信階段是通過簇內(nèi)節(jié)點收集信息發(fā)送給簇頭節(jié)點，簇頭進行數(shù)據(jù)融合并且把結(jié)果發(fā)送給匯聚節(jié)點，較好地解決了網(wǎng)絡節(jié)點能量消耗不均衡的問題.但是該算法中由于簇頭節(jié)點需要完成數(shù)據(jù)融合、與匯聚節(jié)點通信等工作，所以能量消耗十分大.目前許多學者對LEACH算法進行了改進.文獻[2]將網(wǎng)絡劃分為不同的集群層，采用簇頭與簇頭之間的通信來節(jié)省能量.文獻[3]考慮到節(jié)點的剩余能量與網(wǎng)絡負載平衡，通過選擇簇的大小來更改周期.文獻[4]提出了VLEACH協(xié)議版本，旨在降低節(jié)點功耗.文獻[5]提出了基于功率管理、能量管理、網(wǎng)絡壽命、最佳簇頭選擇以及多跳數(shù)據(jù)傳輸?shù)戎笜说腤SN中各種聚類法.文獻[6]根據(jù)模糊算法根據(jù)節(jié)點剩余能量和節(jié)點與基站距離計算節(jié)點競爭力，通過節(jié)點競爭力采用非均勻分簇方法進行簇首選擇.文獻[7]結(jié)合PEGASIS協(xié)議提出一種新的能耗均衡的多跳路由算法，優(yōu)化了簇的結(jié)構(gòu)，均衡了網(wǎng)絡能耗，延長了網(wǎng)絡生命周期.但迄今為止，改進的算法不是僅考慮了節(jié)點的剩余能量就是僅考慮了位置信息，或者倆者結(jié)合考慮的時候沒有從根源上減小節(jié)點能量的消耗.

2 LEACH算法

2.1 算法介紹

LEACH算法選取簇頭的過程如下：節(jié)點產(chǎn)生一個0～1之間的隨機數(shù)與預設閾值做對比，如果該數(shù)小于T(n)，該節(jié)點自動成為簇頭節(jié)點.閾值公式如下：

(1)

其中P是簇頭在全部節(jié)點中所占的比例，r為經(jīng)過的輪數(shù)，rmod(1/P)表示一輪循環(huán)中已經(jīng)當選過簇頭的節(jié)點個數(shù)，G表示一輪循環(huán)中未當選過簇頭的節(jié)點集合.節(jié)點成為簇頭以后，廣播消息通知其他節(jié)點自己是新簇頭，非簇頭節(jié)點根據(jù)自己與簇頭節(jié)點之間的距離來決定加入哪個簇頭，并通知該簇頭.當簇頭接收完所有的節(jié)點加入信息后，隨即產(chǎn)生一個TDMA定時消息，并且通知簇中所有節(jié)點.LEACH算法選擇出的簇頭節(jié)點進行數(shù)據(jù)融合可以降低全網(wǎng)數(shù)據(jù)冗余，降低網(wǎng)絡能量開銷，選擇出的簇頭進行數(shù)據(jù)融合后需要定時將數(shù)據(jù)結(jié)果發(fā)送給匯聚節(jié)點.

2.2 LEACH算法問題描述

LEACH算法使得節(jié)點通信變成層次通信，且簇頭個數(shù)難以控制，容易造成節(jié)點分布不均勻.簇頭擔當了數(shù)據(jù)融合的任務，減少了其他節(jié)點的數(shù)據(jù)通信量，但簇頭節(jié)點因為大量的數(shù)據(jù)通信任務，容易造成節(jié)點死亡，從而可能導致網(wǎng)絡的癱瘓.同時簇頭的選取也沒有考慮地理位置和節(jié)點能量信息，會造成部分節(jié)點死亡過快，從而可能導致系統(tǒng)的網(wǎng)絡生命周期縮短.目前相關學者提出的改進算法都存在各自的問題，例如LEACH-C算法[8]利用了模擬退火算法只考慮了節(jié)點的能量負載，并未考慮節(jié)點位置情況，SEP算法僅考慮了簇頭的選取[9].本文結(jié)合這三者對LEACH算法進行了改進，提出了GEC算法.

3 GEC算法

3.1 算法詳解

GEC算法思想是首先根據(jù)簇頭計算經(jīng)驗公式得出簇頭個數(shù)，利用K-means算法將傳感器節(jié)點進行分簇，分好簇以后將簇內(nèi)節(jié)點距離匯聚節(jié)點最近的點作為首輪簇頭節(jié)點;然后通過分層模型將簇內(nèi)節(jié)點分為3個層次，同時使用分層功率控制技術(shù)減小節(jié)點能量消耗;最后備選簇頭節(jié)點直接在簇內(nèi)第一層內(nèi)按照節(jié)點剩余能量的大小進行選取，GEC算法很好地解決了傳統(tǒng)LEACH算法簇頭選取的不足，同時通過實驗比較，GEC算法相對于LEACH算法以及LEACH的一些改進算法提升了網(wǎng)絡生存周期，使得系統(tǒng)更加穩(wěn)定.

3.2 K-means聚類算法

K-means聚類算法是將n個樣本點分成k個聚類，具有方法簡單、快速、效果好等特點.本文使用K-means聚類算法首先將n個傳感器節(jié)點分成k個類，由于K-means聚類算法中k值難以確定，而將它和LEACH算法結(jié)合，可以通過簇頭經(jīng)驗公式(2)確定k值，而K-means的分類效果遠遠好于LEACH算法，所以本文結(jié)合兩者算法思想.

(2)

其中，N是傳感器節(jié)點總數(shù)，Efs是自由空間能量，Emp是衰減空間能量，M是區(qū)域邊長，dBS為節(jié)點到基站的平均距離.根據(jù)本文仿真實驗參數(shù)的設置，求得簇頭個數(shù)為5.因此K-means算法下的簇頭個數(shù)為5.本文使用了100個節(jié)點進行仿真實驗，K-means算法步驟如下：

第1步.從100個傳感器節(jié)點中隨機選中5個簇頭點；

第2步.然后求得所有節(jié)點到這5個簇頭的距離，如節(jié)點a距離簇頭c值最小，則節(jié)點a屬于c簇；

第3步.重新計算簇內(nèi)中心點作為簇頭；

第4步.重復2、3步，直到簇頭點位置不變.

3.3 簇內(nèi)分層模型

本文考慮到每次選取簇頭時計算量較大，提出基于地理位置的簇內(nèi)分層算法.具體思路如下：改進的LEACH算法通過K-means算法分好簇以后，我們標記簇內(nèi)離匯聚節(jié)點最近的點，這個點就選為簇頭節(jié)點，本文設定的仿真實驗網(wǎng)絡區(qū)域為100m*100m，根據(jù)節(jié)點的實際通訊距離，將簇內(nèi)節(jié)點按照與標記節(jié)點的距離分為三個層次.具體過程為：標記節(jié)點向簇內(nèi)節(jié)點廣播消息，首先標記節(jié)點使用功率等級Level a廣播數(shù)據(jù)包，簇內(nèi)節(jié)點收到信息后，反饋一個信息，并將自己處于休眠狀態(tài)，所有收到信息的節(jié)點為簇內(nèi)第一層.標記節(jié)點使用功率等級Level b廣播數(shù)據(jù)包，所有簇內(nèi)節(jié)點收到信息后依照上一步工作，此次所有節(jié)點為第二層，剩下的簇內(nèi)所有節(jié)點為第三層Level c.圖1是簇內(nèi)分層的模型，一共將簇分成三個層次.

表1 功率等級與距離的關系

圖1 簇內(nèi)分層模型Fig.1 Hierarchical model of the cluster

3.4 簇頭的選取

考慮到LEACH算法選取出的簇頭計算量較大且能量消耗大[10]，當?shù)谝惠喆仡^節(jié)點死亡以后，備選簇頭節(jié)點直接在簇內(nèi)第一層內(nèi)根據(jù)節(jié)點剩余能量的大小進行選取.當?shù)诙喆仡^節(jié)點開始選取時，Level a內(nèi)的節(jié)點發(fā)送數(shù)據(jù)包(包括頭部00和節(jié)點剩余能量)，簇頭節(jié)點判斷該節(jié)點是否為第一層節(jié)點，如果是則通過節(jié)點剩余能量的大小來選舉.當?shù)谝粚庸?jié)點都死亡之后，簇頭節(jié)點從第二層內(nèi)依據(jù)節(jié)點剩余能量大小來進行選取，當?shù)诙庸?jié)點也都死亡之后，第三層的節(jié)點通過剩余能量大小來進行簇頭節(jié)點的選舉，這樣只需通過數(shù)據(jù)包就能判斷出節(jié)點的位置層次，并且選出的簇頭節(jié)點具有距匯聚節(jié)點距離近和能量多的優(yōu)勢，通過功率的調(diào)整，可以盡可能地延長簇頭的網(wǎng)絡周期，增加了網(wǎng)絡的魯棒性，大大減少了節(jié)點的通信開銷.

第一輪簇頭選?。簩⒐?jié)點分為五類S(0)、S(1)、S(2)、S(3)、S(4)，根據(jù)公式(3)計算每類中節(jié)點到匯聚節(jié)點的距離，每類中選擇最近的點作為簇頭節(jié)點，首輪為5個簇頭節(jié)點.

distance=sqrt((S(i).xd-(S(n+1).xd))2+
(S(i).yd-(S(n+1).yd))2)

(3)

備選簇頭節(jié)點選?。簩⒐?jié)點按照所處位置層次進行選擇，處在第一層的節(jié)點具有高優(yōu)先級，首先系統(tǒng)判斷節(jié)點是否處于第一層，若滿足，則根據(jù)節(jié)點的剩余能量看是否為第一層內(nèi)最多來進行選取，若第一層內(nèi)的節(jié)點都死亡，則第二層節(jié)點當選簇頭的優(yōu)先級大于第三層節(jié)點，備選簇頭節(jié)點將在第二層內(nèi)按照節(jié)點剩余能量進行選取.節(jié)點剩余能量根據(jù)公式(4)計算，備選簇頭節(jié)點由節(jié)點剩余能量最多者當選.

S(i).E=S(i).E-ETX

(4)

其中S(i).E表示節(jié)點能量，ETX表示節(jié)點發(fā)送數(shù)據(jù)的能量消耗.

3.5 分層功率控制技術(shù)

簇內(nèi)分好層以后，得到了一個三層節(jié)點模型，由于標記節(jié)點使用不同的功率等級可以和簇內(nèi)節(jié)點順利通信，所以簇內(nèi)節(jié)點依據(jù)不同的位置層次，使用Level a、Level b、Level c三個不同的發(fā)射功率可以保證和簇頭節(jié)點順利通信，這樣保證了簇內(nèi)節(jié)點的連通性.簇頭節(jié)點的發(fā)射功率依據(jù)和下一跳節(jié)點的距離進行設定.對此本文使用了傳感器節(jié)點進行試驗，芯片為CC2530，Z-Stack可設置功率范圍在-22dBm～+3dBm，設定一個板子為終端設備發(fā)送數(shù)據(jù)，一個板子為協(xié)調(diào)器節(jié)點進行接收數(shù)據(jù)，調(diào)節(jié)發(fā)射節(jié)點的功率，這里測試的功率范-22dBm～2dBm，定時發(fā)送數(shù)據(jù)，通過協(xié)調(diào)器顯示信息在串口上.因為實驗參數(shù)設置，節(jié)點的通信半徑在87m左右，所以這里選擇了可到達的通信距離結(jié)果，實驗結(jié)果見表1.通過分層功率控制技術(shù)，可以減小節(jié)點的能量消耗，節(jié)點功率與距離的關系參照公式(5).

(5)

P表示發(fā)射功率，εami和εamo表示放大參數(shù)，Rb表示傳輸速率，distance表示接收節(jié)點的距離，do表示節(jié)點通信可達距離.通過調(diào)整節(jié)點發(fā)射功率，可以得出節(jié)點發(fā)送數(shù)據(jù)時的能耗，見公式(6).

(6)

ETX表示發(fā)射單位報文損耗能量，EDA表示多路徑衰減能量，εamia表示第一層節(jié)點的放大參數(shù)，εamib表示第二層節(jié)點的放大參數(shù)，εamic表示第三層節(jié)點的放大參數(shù)，K表示數(shù)據(jù)的發(fā)送量.根據(jù)式(5)可以求得放大參數(shù)，代入式(6)可得節(jié)點能量消耗，剩余能量通過初始能量減去消耗的能量求得.通過分層功率控制技術(shù)可以減小節(jié)點傳輸數(shù)據(jù)時的能量開銷，而且保證了網(wǎng)絡了拓撲結(jié)構(gòu)，延長了網(wǎng)絡壽命.

4 模擬實驗

GEC算法實驗采用MATLAB 2016a進行仿真，仿真參數(shù)設置見表2.

表2 仿真參數(shù)表

通過MATLAB仿真，LEACH算法和K-means聚類算法分好簇的結(jié)果如圖2、圖3所示，圖2LEACH算法隨機生成100個節(jié)點，產(chǎn)生了8個簇頭(圖中+號表示簇頭，其他表示節(jié)點)且位置分布不合理，分類效果差，有些簇頭負載過重，而有的負載過少，圖3 K-means聚類算法將100個節(jié)點分為了5類，節(jié)點分簇效果較好.

通過MATLAB仿真得出的一個簇內(nèi)分層仿真圖如圖4所示，通過節(jié)點所處位置將簇內(nèi)節(jié)點分為三個層次，依次為Level a(+節(jié)點)、Level b(*節(jié)點)、Level c(o節(jié)點).LEACH算法和GEC算法死亡節(jié)點數(shù)目對比如圖5所示，LEACH算法在進行到900輪次左右時，出現(xiàn)了第一個節(jié)點的死亡，到950次左右時，節(jié)點開始出現(xiàn)大面積死亡;LEACH-C算法在進行到940輪次左右時，出現(xiàn)了第一個節(jié)點的死亡，到950次左右時，節(jié)點開始出現(xiàn)大面積死亡;SEP算法在進行到990輪次左右時，出現(xiàn)了第一個節(jié)點的死亡，到1110次左右時，節(jié)點開始出現(xiàn)大面積死亡.GEC算法在1040輪次左右的時候，開始出現(xiàn)第一個節(jié)點死亡，首個節(jié)點死亡時間較LEACH算法延長了16%左右，較LEACH-C算法延長了11%左右，較SEP算法延長了5%左右.GEC算法節(jié)點在1040-1150 輪次的時候節(jié)點死亡較少， 到1150輪次左右的時候，節(jié)點開始出現(xiàn)大面積死亡.所以本文提出的GEC算法比LEACH算法系統(tǒng)魯棒性更強，系統(tǒng)更加穩(wěn)定，節(jié)點生存周期延長.

如圖6所示，使用LEACH算法，網(wǎng)絡系統(tǒng)進行到2000輪次左右的時候，網(wǎng)絡剩余能量幾乎耗盡;使用LEACH-C算法，網(wǎng)絡系統(tǒng)進行到1800輪次左右的時候，網(wǎng)絡剩余能量幾乎耗盡;使用SEP算法，網(wǎng)絡系統(tǒng)進行到1400輪次左右的時候，網(wǎng)絡剩余能量幾乎耗盡，當使用GEC算法時，網(wǎng)絡進行到2000次左右的時候，網(wǎng)絡剩余能量幾乎耗盡.網(wǎng)絡剩余能量耗盡的時間相較于LEACH算法相近，相較于LEACH-C算法提升了11%左右，相較于SEP算法43%左右.綜上兩者分析，使用本文的GEC算法延長了整個網(wǎng)絡的生命周期，使得網(wǎng)絡系統(tǒng)更加穩(wěn)定.

圖2 LEACH算法示意圖

圖3 K-means聚類算法示意圖Fig.3 K-means clustering algorithm

圖4 簇內(nèi)節(jié)點分層Fig.4 Hierarchical nodes in cluster

圖5 存活節(jié)點Fig.5 Surviving nodes 圖6 網(wǎng)絡剩余能量Fig.6 Residual energy of network

5 結(jié)語及展望

本文較其他改進LEACH算法的不同點在于，通過K-means算法可以較好地實現(xiàn)聚類效果，通過簇內(nèi)分層技術(shù)，可以較快地選擇靠近匯聚節(jié)點并且剩余能量較大的節(jié)點作為簇頭節(jié)點，延長了網(wǎng)絡的生命周期.同時通過分層功率控制技術(shù)，使得節(jié)點可以順利通信，保證了不必要的能量浪費.基于粗糙集的數(shù)據(jù)融合可以很好地去除冗余信息，得出決策規(guī)則.本文提出的GEC算法較LEACH算法以及其他改進算法有了較大的提升，延長了系統(tǒng)的生命周期.

針對本文提出的方案，接下來的工作可以從兩方面進行加強：首先，本文提出的實驗環(huán)境沒有考慮異構(gòu)性，如何保證節(jié)點在不受其他通信方式影響下順利工作，是將來工作的研究重點.此外，本文提出的GEC算法只是在MATLAB上進行了仿真，在實際環(huán)境中可能受到電磁、環(huán)境、硬件本身等影響，稍微影響實驗結(jié)果.