基于模糊算法和最短路徑的LEACH改進協(xié)議

劉泳志,劉國繁

(1．湘潭大學 信息工程學院，湘潭 411105；2.湖南工程學院 電氣信息學院，湘潭 411104；3. 湖南省風電裝備與電能變換協(xié)同創(chuàng)新中心，湘潭 411104)

基于模糊算法和最短路徑的LEACH改進協(xié)議

劉泳志1,劉國繁2，3

(1．湘潭大學 信息工程學院，湘潭 411105；2.湖南工程學院 電氣信息學院，湘潭 411104；3. 湖南省風電裝備與電能變換協(xié)同創(chuàng)新中心，湘潭 411104)

無線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測區(qū)域的大量傳感器節(jié)點通過無線通信形成的自組織網(wǎng)絡(luò)系統(tǒng)，傳感器節(jié)點存在著電源能量、計算和通信能力有限等制約因素.為了均衡無線傳感器網(wǎng)絡(luò)中節(jié)點能量的消耗，延長無線傳感器網(wǎng)絡(luò)的工作壽命，提出一種基于模糊算法和最短路徑的LEACH改進協(xié)議ILAFASP.該協(xié)議簇頭選舉時，采用模糊算法考慮相對節(jié)點剩余能量、相對集中度、相對節(jié)點度計算出每個節(jié)點的優(yōu)先度，根據(jù)優(yōu)先度選舉簇頭；在數(shù)據(jù)傳送階段，在源節(jié)點和基站之間建立最短多跳數(shù)據(jù)傳輸路徑，減少簇頭數(shù)據(jù)傳輸?shù)哪芎?仿真表明，該協(xié)議能夠均衡節(jié)點能量的消耗，延長整個網(wǎng)絡(luò)的工作壽命.

無線傳感器網(wǎng)絡(luò)；模糊算法；LEACH協(xié)議；CMRAOL協(xié)議；多跳通信

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由部署在監(jiān)測區(qū)內(nèi)的大量微型傳感器節(jié)點組成，通過無線通信方式形成一個多跳的，自組織網(wǎng)絡(luò)系統(tǒng)[1].無線傳感器網(wǎng)絡(luò)中的節(jié)點的能量、信息處理能力和通信能力都十分有限.如何降低WSN的能量消耗、延長網(wǎng)絡(luò)壽命一直是WSN研究的熱點[2].在WSN的能量消耗中，數(shù)據(jù)通信能量消耗所占比例最大[3]，因此如何減少通信過程的能量消耗[4-5]成為WSN研究的一個重要問題.

Leach(Low Energy Adaptive Clustering Hierarchy)協(xié)議[6]是最具代表性的一種基于分簇的自適應(yīng)層次型路由協(xié)議，由于簇頭隨機選取且直接與基站進行通信，消耗能量較多，為此，很多人提出了改進的算法：文獻[7] 提出了一種ESSCSTA協(xié)議，該協(xié)議采用休眠機制結(jié)合最小生成樹將數(shù)據(jù)發(fā)送給基站，減少數(shù)據(jù)傳輸能量消耗.文獻[8]提出了CMRAOL(Cluster head Multi-hops Routing Algorithm On LEACH)協(xié)議，該算法中引入能量因子和距離因子修正LEACH算法的閾值函數(shù)，采用簇間多跳通信方式，延長了網(wǎng)絡(luò)壽命.本文針對簇頭節(jié)點能量消耗過大，數(shù)據(jù)傳輸路徑不合理等問題，提出一種基于模糊算法和最短路徑的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議ILAFASP(Improved LEACH algorithm based on fuzzy algorithm and the shortest path)，該協(xié)議能有效地均衡節(jié)點能量消耗，提高網(wǎng)絡(luò)的生存時間.

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

假設(shè)N個傳感器節(jié)點隨機分布在二維的正方形區(qū)域內(nèi)，區(qū)域內(nèi)的節(jié)點周期性地搜集周圍的信息，并且具有以下性質(zhì)：

(1)傳感器網(wǎng)絡(luò)為靜態(tài)網(wǎng)絡(luò)，節(jié)點一經(jīng)部署后就不能移動；

(2)基站的能量是無限的；

(3)所有節(jié)點都有一個唯一的ID；知道自身在區(qū)域中的坐標；具有相同的通信半徑且可以調(diào)節(jié)；具有相同的初始能量且不能補充能量；具有數(shù)據(jù)融合和功率控制功能.

(4)簇內(nèi)節(jié)點與簇頭節(jié)點采用單跳方式通信，簇頭與基站之間采用單跳和簇頭間多跳相結(jié)合的方式進行通信.

2 能量消耗模型

(1)

傳感器節(jié)點接收kbit數(shù)據(jù)所消耗的能量為：

Erx(k)=Erx-elec(k)=kEelec

(2)

其中，ξfs、ξmp分別為自由空間模型和多路徑衰減模型下的放大系數(shù)，單位分別為J/(bit·m2)和J/(bit·m4)；Eelec為1 bit數(shù)據(jù)在發(fā)送或者接收過程中所消耗的能量.

3 ILAFASP協(xié)議設(shè)計

ILAFASP協(xié)議與LEACH協(xié)議一樣，采用輪循環(huán)機制，每輪分為兩個階段：成簇階段和數(shù)據(jù)傳輸階段.在成簇階段，監(jiān)測區(qū)域中的節(jié)點自組織成簇，每一個簇中只有一個簇頭，負責收集、融合和轉(zhuǎn)發(fā)其簇內(nèi)普通節(jié)點采集的數(shù)據(jù)；數(shù)據(jù)傳輸階段包括簇內(nèi)數(shù)據(jù)傳輸和簇間數(shù)據(jù)傳輸，簇內(nèi)節(jié)點發(fā)送采集的數(shù)據(jù)給簇頭，簇頭對候選中繼節(jié)點進行比較，選擇最佳的中繼節(jié)點以減少簇間數(shù)據(jù)傳輸?shù)哪芎?每隔一個周期，整個網(wǎng)絡(luò)進入成簇階段，且不斷循環(huán)，直至區(qū)域內(nèi)所有節(jié)點的能量耗盡.下面對兩個階段做詳細說明.

3.1 成簇階段

模糊算法對被控對象數(shù)學模型的信息要求不高[10]，通過對多個因素的綜合評價得出一個優(yōu)先度AD(advance degree)，這一特點可以用于簇頭的選舉.在選舉簇頭時，根據(jù)模糊算法原理，先輸入節(jié)點自身的相關(guān)參數(shù)，再計算出這個節(jié)點當選簇頭的優(yōu)先度，根據(jù)區(qū)域內(nèi)各節(jié)點優(yōu)先度的大小設(shè)置節(jié)點廣播當選簇頭消息的時間，選擇優(yōu)先度大的節(jié)點當選簇頭.

模糊控制器[11]是用模糊邏輯來模仿人的邏輯思維[12]來對難以建立數(shù)學模型的系統(tǒng)進行控制的設(shè)備，模糊算法主要在于模糊控制器的設(shè)計[13]，基本元素是隸屬函數(shù)、模糊規(guī)則表和解模糊過程[14]，下面對整個過程做詳細描述.

3.1.1 簇頭選舉參考的模糊變量

(1)節(jié)點的相對剩余能量：

(3)

其中Ei(r)表示第r輪節(jié)點i的剩余能量，Ei-max(r)為節(jié)點i的成簇半徑Rc內(nèi)的所有鄰居節(jié)點剩余能量最大值.

(2)節(jié)點相對集中度：

(4)

其中，n為節(jié)點i在成簇半徑Rc之內(nèi)鄰居節(jié)點個數(shù)，di-j是節(jié)點i到其鄰居節(jié)點j距離.

相對集中度：

(5)

FDi-max和FDi-min分別是節(jié)點i的鄰居節(jié)點FD的最大值和最小值.RFD的值越小，說明節(jié)點i的鄰居節(jié)點分布更加集中，簇內(nèi)通信消耗更小.

(3)改進的相對節(jié)點度：

節(jié)點i節(jié)點度：

(6)

其中Numi是以節(jié)點i為圓心，Rc為半徑的圓內(nèi)所有鄰居節(jié)點數(shù)，Dmax是距離節(jié)點i到最遠的鄰居節(jié)點距離.相對節(jié)點度：

RDi(releative degree)=Di/Di-max

(7)

其中Di-max是節(jié)點i成簇半徑內(nèi)的鄰居節(jié)點的節(jié)點度最大值.

相對節(jié)點度不僅考慮了鄰居節(jié)點的個數(shù)，還考慮了鄰居節(jié)點的分布情況，其參數(shù)越大，則說明節(jié)點的鄰居節(jié)點較多，且分布相對集中，有利于減少簇內(nèi)通信代價.

3.1.2 變量的模糊化

本文的模糊控制器包含節(jié)點相對剩余能量，相對密集度和相對節(jié)點度三個輸入?yún)?shù)，一個輸出參數(shù).其中三個模糊輸入?yún)?shù)都分為三個等級：Low，Middle，high；其中相對剩余能量采用梯形隸屬函數(shù)，相對密集度和相對節(jié)點度采用正態(tài)波隸屬函數(shù)，如圖1～圖3所示.

圖1 相對剩余能量的隸屬函數(shù)

圖2 相對集中度隸屬函數(shù)

圖3 相對節(jié)點度隸屬函數(shù)

經(jīng)過模糊化計算，輸出的chance的值分為1～11一共11個等級，采用三角波隸屬函數(shù)，如圖4所示.

圖4 chance隸屬函數(shù)

模糊推理過程遵循“IF——THEN”規(guī)則，本文設(shè)定如下形式:

IFRE∈A,RFD∈B,RD∈CTHENchance∈D

其中，A,B,C分別對應(yīng)三個輸入變量模糊集合定義的語言值，D對應(yīng)輸出變量模糊集合的語言值.

節(jié)點的相對剩余能量越多，相對集中度越大，相對節(jié)點度越高，它的chance的級別也越高，其27條模糊規(guī)則如表1所示.

表1 模糊規(guī)則表

3.1.3 解模糊化

通過解模糊化將chance的模糊值轉(zhuǎn)化為精確的數(shù)值，求得節(jié)點的優(yōu)先度AD值.本文的解模糊化方法采用常用的質(zhì)心法，其公式[15]如下：

(8)

3.1.4 簇頭的選舉

選舉簇頭時結(jié)合模糊控制算法，每個節(jié)點通過模糊算法得到每個節(jié)點的優(yōu)先度AD值.根據(jù)公式(9)設(shè)置發(fā)送當選簇頭消息的等待時間，時間到了，就發(fā)送當選簇頭的消息，在半徑Rc內(nèi)的節(jié)點偵聽到消息后自動放棄競爭簇頭，成為普通節(jié)點.

(9)

其中，T是一固定的時間，V是介于[0.9,1]之間隨機數(shù).

首先，選擇相對剩余能量較多了節(jié)點，有利于均衡節(jié)點的能耗，選擇鄰居節(jié)點數(shù)量多且相對密集度較大，分布集中的節(jié)點做簇頭，有利于減少簇內(nèi)通信能耗；此外，監(jiān)測區(qū)域中各個部分節(jié)點的能耗不是均勻的，有些區(qū)域的節(jié)點消耗可能相對較大，如果與全部節(jié)點作比較，這些剩余能量較小的區(qū)域可能選不出簇頭，所以以上三個參數(shù)都是在自己成簇半徑Rc內(nèi)的比較，選擇局部區(qū)域內(nèi)較優(yōu)的節(jié)點作為簇頭；此外，一旦某個節(jié)點發(fā)布當選簇頭消息，其半徑內(nèi)的其他簇頭則成為普通節(jié)點，這樣防止了LEACH協(xié)議采用隨機機制選舉簇頭造成的簇頭過于密集的情況.

普通節(jié)點選擇最近的簇頭發(fā)送入簇請求，簇頭收到入簇請求后將該節(jié)點加入路由表中，向簇內(nèi)的成員節(jié)點發(fā)布確認消息并且分配TDMA時隙，簇內(nèi)成員節(jié)點依據(jù)自己的TDMA時隙將數(shù)據(jù)發(fā)送給簇頭.

3.2 數(shù)據(jù)傳輸階段

簇形成之后，簇中的普通節(jié)點將采集到的數(shù)據(jù)發(fā)送給自己的簇頭，由于簇內(nèi)數(shù)據(jù)傳輸距離較短，所以普通節(jié)點和簇頭節(jié)點之間采用單跳通信的方式.

而簇間數(shù)據(jù)傳輸由于部分簇頭距離基站較遠，而通信能耗隨距離的增加呈幾何增長，因此為了減少數(shù)據(jù)傳輸?shù)哪芎?，ILAFASP協(xié)議簇間數(shù)據(jù)傳輸采用單跳與多跳相結(jié)合的方式，在源節(jié)點與基站間建立最短數(shù)據(jù)傳輸路徑，降低簇頭在簇間數(shù)據(jù)傳輸過程中的能耗，下面作詳細敘述.

如果簇頭到基站的距離小于d0，則簇頭直接與基站通信，這樣可以減少不必要的數(shù)據(jù)轉(zhuǎn)發(fā)能量消耗.

如果簇頭到基站的距離大于d0，則采用簇間多跳通信方式.源節(jié)點在選擇合適的簇頭作為中繼節(jié)點，中繼節(jié)點將簇內(nèi)數(shù)據(jù)和接收的轉(zhuǎn)發(fā)數(shù)據(jù)融合后再轉(zhuǎn)發(fā)給中繼節(jié)點，一直傳輸?shù)交?中繼節(jié)點的選擇方法如下：

首先源節(jié)點i把滿足公式(10)的簇頭作為其候選中繼節(jié)點.

(10)

其中，i為源節(jié)點，j為某個其它簇頭節(jié)點.R的值為70 m.條件(10)使選取的中繼節(jié)點比源節(jié)點更靠近基站，且距離源節(jié)點不至于太遠(R

之后在這些候選中繼節(jié)點中根據(jù)公式(11)選擇Q值最大的作為其中繼節(jié)點.

(11)

式(11)中的路徑因子hij是指候選中繼節(jié)點j到簇頭節(jié)點與i基站連線的垂直距離，如圖5所示.

圖5 路徑因子hij示意圖

hij的值計算方式如下：設(shè)簇頭節(jié)點i的坐標為(xi,yi)，候選中繼節(jié)點j的坐標為(xj,yj)，基站坐標為(x0,y0)，則簇頭節(jié)點i到基站BS的連線可表示為：

(12)

式(12)可化為如下形式：

Cx+Dy+E=0

(13)

其中：

C=y0-yi，D=xi-x0

E=xi(yi-y0)+yi(x0-xi)

那么，根據(jù)點到直線的距離公式可得：

(14)

hij的值越小，說明簇頭節(jié)點j越靠近基站和源節(jié)點i的連接線，這時d(i,j)+d(j,BS)的值也越小.當hij的值為0時,d(i,j)+d(j,BS)的值最小，此時d(i,j)+d(j,BS)=d(i,BS)，傳輸距離最短，數(shù)據(jù)傳輸過程的能量消耗最小.

此外，當部分節(jié)點死亡導致簇頭找不到滿足公式(10)的候選簇頭的極端情況時，則簇頭i擴大發(fā)射功率，在滿足條件d(j,BS)

4 仿真實驗和性能分析

采本文用MATLAB軟件對ILAFASP協(xié)議、CMRAOL協(xié)議和LEACH協(xié)議進行仿真.對三種協(xié)議的簇頭節(jié)點分布情況、首個節(jié)點死亡時間、網(wǎng)絡(luò)生存周期和網(wǎng)絡(luò)能量消耗幾個方面進行對比分析.

4.1 實驗參數(shù)設(shè)置

仿真實驗的參數(shù)設(shè)置如表2所示，其中，R=70 m，a、b的值，通過仿真結(jié)果的對比分別取最優(yōu)值為：a=0.8，b=0.2.

表2 實驗參數(shù)表

4.2 實驗結(jié)果及分析

圖6 CMROAL協(xié)議和ILAFASP協(xié)議節(jié)點分布圖

由圖6(a)可以看出，CMROAL協(xié)議的簇頭在網(wǎng)絡(luò)中分布不均勻，比如在靠近基站的區(qū)域簇頭分布過于密集；而從圖6(b)可以看出本文提出的ILAFASP協(xié)議中，簇頭在網(wǎng)絡(luò)中的分布比較均勻，這樣更利于均衡簇頭的能耗，避免簇頭的過早死亡.

圖7 三種協(xié)議存活節(jié)點數(shù)

圖7給出了LEACH、CMRAOL和ILAFASP協(xié)議首個節(jié)點死亡時間、網(wǎng)絡(luò)生存周期的比較.LEACH、CMRAOL、ILAFASP協(xié)議第一個節(jié)點死亡的輪數(shù)分別為241、523、756，ILAFASP協(xié)議的生存周期也大于CMRAOL協(xié)議.本文提出的ILAFASP協(xié)議有明顯的優(yōu)勢，這是因為ILAFASP協(xié)議選取簇頭時使用模糊控制算法，選擇節(jié)點的相對剩余能量多，相對集中度大，相對節(jié)點度大的節(jié)點作為簇頭，不僅減少簇內(nèi)通信的能耗而且均衡網(wǎng)絡(luò)節(jié)點的能耗；此外采用了時間競爭機制，使節(jié)點的分布更加均勻.在簇間數(shù)據(jù)傳輸階段，選擇單跳與多跳相結(jié)合的通信方式，當簇頭到基站距離小于d0時，直接向基站傳輸數(shù)據(jù)，避免了多余的轉(zhuǎn)發(fā)能量消耗；當采用多跳通信時，綜合考慮了候選中繼節(jié)點本身和其前向傳輸區(qū)域的剩余能量和路徑因子，尋找一條從源節(jié)點到基站的最短路徑，節(jié)省了簇頭轉(zhuǎn)發(fā)數(shù)據(jù)的能耗，從而在首個節(jié)點死亡時間和網(wǎng)絡(luò)生存時間等性能上都有明顯的提升.

圖8 三種協(xié)議的網(wǎng)絡(luò)剩余的總能量

圖8給出了LEACH、CMRAOL和ILAFASP協(xié)議網(wǎng)絡(luò)能量消耗情況的對比. 可以看出ILAFASP協(xié)議的網(wǎng)絡(luò)剩余能量下降曲線比LEACH和CMRAOL協(xié)議更加平緩，且剩余總能量一直高于CMRAOL協(xié)議，在生存周期的前面絕大部分輪數(shù)高于LEACH協(xié)議，這表明ILAFASP協(xié)議能夠更加有效的減少網(wǎng)絡(luò)中節(jié)點的能耗.

5 結(jié)論

由于監(jiān)測區(qū)域中節(jié)點的能量有限，如何減少和均衡網(wǎng)絡(luò)中節(jié)點的能耗成為我們路由協(xié)議設(shè)計的最重要的問題，本文提出了一種基于模糊算法和最短路徑的LEACH改進協(xié)議ILAFASP，對簇頭的選舉方式做了改進，結(jié)合模糊控制算法選舉簇頭，綜合考慮節(jié)點的相對剩余能量，相對集中度和相對節(jié)點度，均衡網(wǎng)絡(luò)節(jié)點的能耗，減少簇內(nèi)通信的代價，并使簇頭的分布更加合理；此外，采用單跳與多跳相結(jié)合的簇間數(shù)據(jù)傳輸方式，在源節(jié)點和基站間尋找一條最短數(shù)據(jù)傳輸路徑，減少簇間數(shù)據(jù)傳輸?shù)哪芎?，避免簇頭節(jié)點在數(shù)據(jù)傳輸過程中能量消耗過快.通過仿真對比，ILAFASP可以有效均衡網(wǎng)絡(luò)中節(jié)點的能耗，延長網(wǎng)絡(luò)工作壽命.

[1] 曹建玲,任 智. 無線傳感器網(wǎng)絡(luò)路由協(xié)議綜述[J]. 微計算機信息, 2010,26(7-1):3-5.

[2] 唐甲東,蔡 明. 基于LEACH協(xié)議的能耗均衡路由算法[J].計算機工程,2013,39(7):133-141.

[3] 張興強，楊科華,羅 娟. 一種異構(gòu)傳感器網(wǎng)絡(luò)下的節(jié)能分簇路由算法[J]. 計算機工程與應(yīng)用,2011,47(11): 81-83

[4] 廖先林,陸 暢,姜 婷,等.一種能耗均勻的WSN分簇路由協(xié)議研究與設(shè)計[J].小型微型計算機系統(tǒng), 2014,10(35):2199-2202.

[5] Jing Yan, Cailian Chen, Xiaoyuan Luo, et al.Topology Optimisation-based Distributed Estimation in Relay Assisted Wireless Sensor Networks[J]. IET Control Theory & Applications,2014,8(18): 2219-2229.

[6] 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 Sciences, 2000.

[7] Chauhan R, Gupta V. Energy Efficient Sleep Scheduled Clustering & Spanning Tree Based Data Aggregation in Wireless Sensor Network[C]// Proceedings of the 1st International Conference on Recent Advances in Information Technology (RAIT), 2012: 536-541.

[8] 陳炳才,么華卓,楊明川,等. 一種基于LEACH協(xié)議改進簇間多跳路由協(xié)議[J].傳感技術(shù)學報,2014,27(3) :373-377.

[9] 張 淳,費樹岷.能耗均衡的自組織無線傳感器網(wǎng)絡(luò)分簇算法[J].控制工程,2012,19(1):90-93.

[10]B.Baranidharan, B.Santhi.DUCF: Distributed Load Balancing Unequal Clustering in Wirelesssensor Networks Using Fuzzy Approach[J].Applied Soft Computing,2015,40:495-506.

[11]Taheri H,Neamatollahi P,Younis O M,et al.An Energy-aware Distributed Clustering Protocol in Wireless Sensor Networks Using Fuzzy Logic[J].Ad Hoc Networks,2012,10(7):1469-1481.

[12]Vilem Novak.Reasoning About Mathmatical Fuzzy Logic and Future[J].Fuzzy Sets and Systems,2012,192:25-44.

[13]Gupta I,Riordan D,Sampalli S.Cluster-head Election Using Fuzzy Logic for Wireless Sensor Networks[C]//Proceedings of the 3rd Annual Communication Networks and Services Research Conference, 2005:255-260.

[14]Feng Renjian,Che Shenyun,Wang Xiao. A Credible Cluster-head Election Algorithm Based on Fuzzy Logic in Wireless Sensor Networks[J].Journal of Computational Information Systems,2012,15(8):6241-6248.

[15]Kim J M, Park S H, Han Y J, et al. CHEF Cluster Head Election Mechanism Using Fuzzy Logic in Wireless Sensor Networks[C].Proceedings of Advanced Communication Technology, 2008: 654-659.

An Improved LEACH Algorithm Based on Fuzzy Algorithm andShortest Path.Computer Engineering and Applications

LIU Yong-zhi1,LIU Guo-fan2

(1. College of Information Engineering, Xiangtan University, Xiangtan 411105, China；2. College of Electrical Information, Hunan Institute of Engineering, Xiangtan 411104, China；3. Hunan Province Cooperative Innovation Center for Wind Power Equipment and Energy Conversion, Xiangtan 411104, China)

Wireless sensor network is a self-organized network system which is formed by the large number of sensor nodes deployed in the monitoring area. The sensor nodes have limited power, computation and communication ability.In order to balance the energy consumption of nodes and prolong the working life of the wireless sensor network,an improved LEACH algorithm based on fuzzy algorithm and the shortest path ispraposed. The cluster head of this agreement is elected by using fuzzy algorithm considering the relative residual energy of nodes, the relative focus degree and the degree of node of calculating the priority degree of each node, for cluster head electing. In data transmission phase, a multi-hop shortest path between source node and base station is set up to balance energy consumption of cluster data transmission. Simulation shows that the protocol can balance the node energy consumption and prolong the working life of the whole network.

wireless sensor network; fuzzy algorithm; LEACH protocol; CMRAOL protocol; multi-hop communication

2016-07-28

湖南省科技計劃資助項目(2012SK3173);廣東省普及型高性能計算機重點實驗室開放課題(SZU-GDPHPCL201303).

劉泳志(1991-),男,碩士,研究方向：無線傳感器網(wǎng)絡(luò).

劉國繁(1959-)，男，教授，研究方向：信號檢測與處理、圖像傳輸、嵌入式系統(tǒng)及應(yīng)用.

TP393

A

1671-119X(2017)01-0010-07