黃靜，許力

（1.福建師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州 350007；2.泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 輕工與信息專業(yè)部，福建 泉州 362411）

基于可信度的簇間多跳LEACH算法

黃靜1，2，許力1

（1.福建師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州 350007；2.泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 輕工與信息專業(yè)部，福建 泉州 362411）

通過分析低功耗自適應(yīng)集簇分層型協(xié)議（LEACH）和基于可信度的低功耗自適應(yīng)集簇分層型協(xié)議（TE－LEACH）算法的不足，提出一種基于可信度的簇間多跳低功耗自適應(yīng)集簇分層型協(xié)議（TEM－LEACH）算法 .該算法既考慮簇頭節(jié)點傳輸數(shù)據(jù)的可信度，又引入網(wǎng)關(guān)節(jié)點構(gòu)建路由主干網(wǎng)，保證數(shù)據(jù)經(jīng)過最少的跳數(shù)傳輸?shù)交?，有效地延長無線傳感器網(wǎng)絡(luò)生存時間，增加了LEACH算法的適用范圍.

無線傳感器網(wǎng)絡(luò)；低功耗自適應(yīng)集簇分層型協(xié)議；可信度；多跳；生存時間

無線傳感器網(wǎng)絡(luò)是一種新型的無線網(wǎng)絡(luò)體系，由大量具有特定功能的傳感器節(jié)點通過自組織的無線通信方式，相互傳遞信息，協(xié)同地完成特定功能的專用網(wǎng)絡(luò)［1－2］.低功耗自適應(yīng)集簇分層型協(xié)議（low energy adaptive clustering hierarchy，LEACH）算法是為無線傳感器網(wǎng)絡(luò)設(shè)計的一種周期性執(zhí)行的低功耗自適應(yīng)分簇拓?fù)渌惴ǎ?－4］.在LEACH算法中，每個節(jié)點成為簇頭的概率是相等的，能夠在一定程度上均衡分配網(wǎng)絡(luò)能量.但是通過該算法產(chǎn)生的簇頭分布具有隨機(jī)性，每輪簇頭個數(shù)也不穩(wěn)定，因此骨干網(wǎng)的形成很沒有保證.在無線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的節(jié)點既是信任的主體，又是信任的客體.文獻(xiàn)［5］基于可信度對LEACH拓?fù)渌惴ㄟM(jìn)行改進(jìn)，提出了基于可信度的低功耗自適應(yīng)集簇分層型協(xié)議（TELEACH）算法 .它引入新的簇頭選舉機(jī)制，根據(jù)鄰居節(jié)點的監(jiān)控及節(jié)點信息的交互方式來計算節(jié)點的可信度，使擔(dān)任簇頭的節(jié)點在保證有足夠的能量的同時，還有較大的可信度.該算法雖然會增加一定的延遲，但在平衡網(wǎng)絡(luò)負(fù)載，更準(zhǔn)確地獲取監(jiān)測范圍的數(shù)據(jù)等方面實現(xiàn)了優(yōu)化.其簇頭節(jié)點獲得數(shù)據(jù)向基站傳輸?shù)倪^程仍采用單跳的形式，比較適用于小型網(wǎng)絡(luò)，而對大規(guī)模的傳感器網(wǎng)絡(luò)，隨著通信距離的增加，擔(dān)任簇頭的節(jié)點能量消耗過快，不利于網(wǎng)絡(luò)均衡發(fā)展.本文提出了基于可信度的簇間多跳低功耗自適應(yīng)集簇分層型協(xié)議（TEM－LEACH）算法，彌補(bǔ)了LEACH算法和TE－LEACH算法的不足.

1 算法的提出

傳感器網(wǎng)絡(luò)的實際應(yīng)用多數(shù)在較大的網(wǎng)絡(luò)規(guī)模 .在大規(guī)模的無線傳感器網(wǎng)絡(luò)中，隨著簇頭距離匯聚節(jié)點越遠(yuǎn)，信號的空間損耗也劇烈加強(qiáng)，通信節(jié)點的能耗將大大增加，從而縮短網(wǎng)絡(luò)的生存時間.TELEACH算法沒有全面考慮數(shù)據(jù)傳輸過程中可能存在的問題.圖1為一種簡單的電信號傳輸能量模型.該模型考慮了發(fā)射機(jī)的發(fā)射能量、功率放大器的消耗能量，以及接收機(jī)的接收信號能量.

簇頭節(jié)點發(fā)送數(shù)據(jù)的能量消耗與通信距離遠(yuǎn)近有關(guān)，其關(guān)系為Er＝lEe，Es＝lEe＋lεadβ.其中：Er，Es分別為接收和發(fā)送長度為l bit的數(shù)據(jù)消耗的能量；Ee為電路消耗；εa為放大器的放大倍數(shù)；d為數(shù)據(jù)傳輸?shù)木嚯x；β為由無線電通道決定的常量，當(dāng)兩個相對較遠(yuǎn)的節(jié)點進(jìn)行通信時，適用于多徑衰落信道模型，取β＝4，而當(dāng)兩個相對較近的節(jié)點進(jìn)行通信時，適用于自由空間信道模型，取β＝2［6］.

圖1 電信號傳輸能量模型Fig.1 Electronics transmission model

由此可見，在大規(guī)模的傳感器網(wǎng)絡(luò)中，隨著通信距離的增加，節(jié)點能量消耗將急劇增加，故要減少單跳通信距離，需使用多跳短距離無線通信方式.因此，所提出的算法主要改進(jìn)是盡量避免簇頭直接向基站傳輸數(shù)據(jù)，減少簇頭節(jié)點的能量消耗.

2 算法的描述

在無線傳感器網(wǎng)絡(luò)中，假設(shè)每個節(jié)點具有唯一的節(jié)點標(biāo)識ID（1≤ID≤n），所屬簇標(biāo)識為CID.每個節(jié)點都可以通過一定的定位機(jī)制知道自己的位置及自身的剩余能量.

2.1 網(wǎng)關(guān)的選取

假設(shè)兩簇頭的距離為d，則簇域間存在以下4種可能的關(guān)系.

1）當(dāng)0＜d≤r時，兩簇頭節(jié)點可以直接通信，轉(zhuǎn)發(fā)數(shù)據(jù)，如圖2（a）所示.

2）當(dāng)r＜d≤2r時，兩簇間存在公共節(jié)點，則在bb公共節(jié)點中選取一個節(jié)點做為網(wǎng)關(guān)節(jié)點；若公共節(jié)點同時屬于多個簇，則從同時屬于最多簇的候選網(wǎng)關(guān)節(jié)點集合中選擇一個作為網(wǎng)關(guān)節(jié)點，承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，如圖2（b）所示.

3）當(dāng)2r＜d≤3r時，兩簇間不存在公共節(jié)點，則在各簇內(nèi)選取一個節(jié)點做為網(wǎng)關(guān)節(jié)點，使選取的網(wǎng)關(guān)節(jié)點可以直接通信，如圖2（c）所示.

4）當(dāng)d＞3r時，則有兩種情況：a）兩簇間有中繼簇，可以按照關(guān)系3）來選擇簇間的網(wǎng)關(guān)節(jié)點；b）孤立簇，即簇域內(nèi)的所有節(jié)點在各自發(fā)送范圍內(nèi)都無法與其他簇的節(jié)點通信，可以通過調(diào)整簇頭的發(fā)射功率，使其與基站直接通信，若簇頭與基站直接發(fā)送數(shù)據(jù)，則簇頭很快就會因為能量耗而死亡，在一般情況下，這種孤立的簇可以將其丟棄，如圖2（d）所示.

圖2 簇域間的關(guān)系Fig.2 Relationship between clusters

一般來說，無線傳感器網(wǎng)絡(luò)的節(jié)點密度都較大，網(wǎng)絡(luò)中存在孤立簇的可能性較小.因此，將孤立簇排除在考慮范圍之外對網(wǎng)絡(luò)數(shù)據(jù)收集的完整性并不會造成太大的影響.網(wǎng)關(guān)節(jié)點和簇頭節(jié)點形成網(wǎng)絡(luò)的骨干網(wǎng)，負(fù)責(zé)數(shù)據(jù)的接收與傳送.每輪產(chǎn)生的簇頭數(shù)目由算法決定，但如果以盡可能少的網(wǎng)關(guān)節(jié)點來連接各簇，在保證簇的連通性的同時，不僅可以盡量減少信道中數(shù)據(jù)沖突的概率，更重要的是多跳通信方式大大降低了節(jié)點傳輸數(shù)據(jù)的能量消耗.

目前的LEACH改進(jìn)算法都是假設(shè)節(jié)點完全可信，不存在外部攻擊或由于節(jié)點的自私性而造成的網(wǎng)絡(luò)不安全問題.如果節(jié)點不可信，在數(shù)據(jù)傳輸過程中即使可以使網(wǎng)絡(luò)生命周期延長，卻很可能出現(xiàn)網(wǎng)絡(luò)傳輸數(shù)據(jù)的效率不高，甚至數(shù)據(jù)傳輸錯誤的現(xiàn)象.為了選取性能最優(yōu)的節(jié)點做為網(wǎng)關(guān)，引入一個候選網(wǎng)關(guān)的平均度量值（f），其計算式為

式中：e為節(jié)點的自身剩余能量與網(wǎng)絡(luò)的平均能量的比值；t為可信度值；c為候選網(wǎng)關(guān)節(jié)點連接簇頭的個數(shù)與網(wǎng)絡(luò)中節(jié)點的總數(shù)的比值；α，β，γ為參數(shù)因子，α＋β＋γ＝1，且α，β，γ＞0.

通過α，β，γ參數(shù)因子可以動態(tài)調(diào)節(jié)節(jié)點剩余能量、可信度和節(jié)點的連接度對f的影響.若f值相同，再根據(jù)節(jié)點的標(biāo)識ID，選取標(biāo)識ID最小的節(jié)點做為網(wǎng)關(guān).

2.2 網(wǎng)關(guān)部分偽代碼的選取

2.3 網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膶崿F(xiàn)

網(wǎng)絡(luò)中所有節(jié)點都是同構(gòu)的，在成簇階段，普通節(jié)點在自己的時隙內(nèi)發(fā)送完數(shù)據(jù)后就關(guān)閉節(jié)點處于休眠狀態(tài).進(jìn)入數(shù)據(jù)轉(zhuǎn)發(fā)階段，被選為網(wǎng)關(guān)的普通節(jié)點會根據(jù)需要被喚醒，承擔(dān)簇間的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù).網(wǎng)關(guān)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)后，節(jié)點能量發(fā)生變化，為保持網(wǎng)絡(luò)的連通，當(dāng)網(wǎng)關(guān)能量變化超過一個變化閾值的時候，向其所屬簇的簇頭發(fā)送一個更新信號，通知各簇頭更換剩余候選網(wǎng)關(guān)中平均度量值最大的節(jié)點為新的網(wǎng)關(guān).

網(wǎng)絡(luò)配置完成后，假設(shè)各節(jié)點（包括基站）時鐘同步，或者通過基站向各節(jié)點發(fā)送同步脈沖信號實現(xiàn)基站與節(jié)點的時鐘同步.

1）簇內(nèi)通信.所有簇成員節(jié)點將各自檢測感應(yīng)到的數(shù)據(jù)在簇頭分配的時間片內(nèi)，以單跳的形式傳輸給簇頭，而簇頭在一定得時間內(nèi)將收到簇內(nèi)節(jié)發(fā)送的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合.

2）簇間通信.簇頭節(jié)點和網(wǎng)關(guān)節(jié)點構(gòu)成無線傳感器網(wǎng)絡(luò)的路由主干網(wǎng).簇頭節(jié)點通過路由主干網(wǎng)將收集到的數(shù)據(jù)采用多跳傳輸至基站；簇頭節(jié)點根據(jù)貪心算法來選擇下一跳數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點，在其通信范圍內(nèi)選取一個離基站最近的路由主干網(wǎng)節(jié)點做為下一跳數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點.

3 仿真結(jié)果與分析

仿真采用Visual C＋＋6.0開發(fā)，主要是比較LEACH算法、TE－LEACH及TEM－LEACH算法在網(wǎng)絡(luò)生存時間上和每輪消耗能量上的變化情況.試驗仿真系統(tǒng)中節(jié)點隨機(jī)分布在200×200的正方形區(qū)域內(nèi)，節(jié)點位置不移動 .仿真參數(shù)設(shè)置：發(fā)射電路損耗能量（Ee）為50nJ·bit－1；自由空間功率放大損耗（εfs）為10pJ·（bit·m2）－1；數(shù)據(jù)融合能量損耗傳輸功率（εmp）為1.3nJ·bit－1；簇首比例（p）為5%；數(shù)據(jù)融合能量（Eda）為5nJ；節(jié)點初始能量為1J；基站位置為（250，375）；數(shù)據(jù)包長度（l）為525B.

3.1 網(wǎng)絡(luò)生存時間的比較

LEACH算法中，簇頭選舉具有很大的隨機(jī)性，被選中為簇頭的節(jié)點沒有考慮其自身的剩余能量，簇頭收集數(shù)據(jù)后直接向基站發(fā)送，能量消耗占網(wǎng)絡(luò)總能量消耗的大部分，有可能會出現(xiàn)某一節(jié)點過早死亡的狀況.TE－LEACH算法中，對簇頭選舉適當(dāng)改進(jìn)，在一定程度上避免了剩余能量較小的節(jié)點成為簇頭的可能；TEM－LEACH算法中進(jìn)一步加入了多跳傳輸數(shù)據(jù)方案，大大減少了由簇頭向基站傳輸數(shù)據(jù)過程中消耗的能量.仿真過程不斷增加節(jié)點數(shù)（n），選取30次模擬實驗的平均值，各算法的網(wǎng)絡(luò)生存時間（t）如圖3所示.

由圖3可知：在網(wǎng)絡(luò)節(jié)點密度較小時，利用TEMLEACH算法的網(wǎng)絡(luò)的生命周期（以第1個節(jié)點的死亡時間作為網(wǎng)絡(luò)生命周期）比TE－LEACH及LEACH算法都有一定的延長，但差距不大；隨著節(jié)點數(shù)目的增加，差距不斷增大.這是因為在節(jié)點密度越高的網(wǎng)絡(luò)中，采用多跳路徑傳輸數(shù)據(jù)時，被選做簇頭的節(jié)點消耗的能量就越少，即在一定程度上均衡了網(wǎng)絡(luò)的能量消耗.

圖3 不同算法的網(wǎng)絡(luò)生命周期Fig.3 Network lifetime of different algorithms

3.2 能量消耗比較

LEACH及TE－LEACH算法中，簇頭收集數(shù)據(jù)后都是直接向基站發(fā)送，能量消耗較大；而TEMLEACH算法采用選取網(wǎng)關(guān)節(jié)點的辦法構(gòu)建路由主干網(wǎng)，使用多跳短距離無線通信方式，減少了單跳通信距離，即大大減少了節(jié)點傳輸數(shù)據(jù)的能量消耗.在節(jié)點為100，300，500個的情況下，分別對3種算法進(jìn)行多次模擬實驗，采用30次模擬實驗的平均值并隨機(jī)選取其中10輪，每輪節(jié)點消耗的總能量變化如圖4所示.圖4中：k為輪數(shù)；Ee為能量損耗.

由圖4可知：在固定節(jié)點的情況下，LEACH及TE－LEACH算法每輪的能量消耗相差不大；而TEM－LEACH算法每輪消耗的總能量均比前兩種的要少.在節(jié)點數(shù)100時，TEM－LEACH算法每輪消耗的能量較LEACH及TE－LEACH算法減少16%；在節(jié)點數(shù)300時，能量消耗減少21%；而在節(jié)點數(shù)500時，能量消耗則減少24%.這是因為TE－LEACH算法只是對簇頭的選取做了適當(dāng)?shù)母倪M(jìn)，并沒有改變簇頭節(jié)點單跳向基站傳輸數(shù)據(jù)的情況，甚至由于要額外判斷節(jié)點的可信度還多消耗了一部分的能量；而TEM－LEACH算法中簇頭節(jié)點采用的是多跳短距離通信，因此每輪節(jié)點總能量消耗會有所減少，并且隨著節(jié)點密度增大，這種優(yōu)勢越來越明顯.

圖4 各算法的每輪網(wǎng)絡(luò)消耗能量Fig.4 Each algorithm′s energy consumption per round

4 結(jié)論

提出的基于可信度的簇間多跳LEACH算法，既考慮到簇頭節(jié)點傳輸數(shù)據(jù)的可信度，又引入網(wǎng)關(guān)節(jié)點構(gòu)建路由主干網(wǎng)，保證了數(shù)據(jù)經(jīng)過最少的跳數(shù)傳輸?shù)交?，彌補(bǔ)了LEACH和TE－LEACH算法的不足，從而使網(wǎng)絡(luò)壽命得到了相應(yīng)的延長.

在選取網(wǎng)關(guān)節(jié)點的算法時間復(fù)雜度階段，假設(shè)網(wǎng)絡(luò)中有m個簇，每個簇平均有n個節(jié)點，選取的網(wǎng)關(guān)節(jié)點都是每個簇內(nèi)尋找能夠與相鄰簇通信的簇成員節(jié)點，即每個簇頭都要在簇內(nèi)節(jié)點尋找網(wǎng)關(guān)節(jié)點.因此，一個簇間要尋找網(wǎng)關(guān)節(jié)點最壞情況下需要n次，而對于整個網(wǎng)絡(luò)尋找網(wǎng)關(guān)節(jié)點的時間復(fù)雜度也只需O（mn），其時間復(fù)雜度較低.

從LEACH，TE－LEACH和TEM－LEACH算法的仿真中可以看出：對于節(jié)點密度越高的無線傳感器網(wǎng)絡(luò)，TEM－LEACH算法的網(wǎng)絡(luò)生命周期就越長 .這是由于采用了多跳的數(shù)據(jù)傳輸方式，每輪網(wǎng)絡(luò)的能量消耗總額大大減少，直觀地體現(xiàn)了TEM－LEACH算法在高密度、大規(guī)模網(wǎng)絡(luò)下的優(yōu)勢.該算法不僅可以有效地延長無線傳感器網(wǎng)絡(luò)生存時間，也增加了LEACH算法的適用范圍.

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks：A survey［J］.Computer Networks，2002，38（4）：393－341.

［2］AKKAYA K，YOUNIS M.A survey on routing protoeols for wireless sensor networks［J］.Ad Hoc Networks，2005，3（3）：325－349.

［3］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660－670.

［4］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy－efficient communica tion protocol for wireless microsensor networks［C］∥Proc of the 33rd Annual Hawaii Int Conf on System Sciences.Maui：IEEE Press，2000：3005－3014.

［5］黃靜，許力，林力偉.基于可信度的LEACH 拓?fù)渌惴ǜ倪M(jìn)［J］.福建電腦，2009（9）：6－10.

［6］RAPPAPORT T S.Wireless Communication：Principles and practice［M］.New Jersey：Prentice－Hall Inc，1996.

A LEACH Topology Algorithm with Multi－Hop between Clusters Based on Trust Evaluation

HUANG Jing1，2，XU Li1

（1.School of Mathematics and Computer Science，F(xiàn)ujian Normal University，F(xiàn)uzhou 350007，China；2.Department of Light Industrial and Information，Quanzhou College of Economics and Trade，Quanzhou 362411，China）

By analyzing the deficiencies of low energy adaptive clustering hierarchy（LEACH）and LEACH based on turst evaluation（TE－LEACH），this paper proposes a LEACH algorithm with multi－h(huán)op between clusters based on trust evaluation（TEM－LEACH）.It considers not only the trust evaluation of cluster heads between data transmission，but also building the routing bakcbone network through gateway nodes.The improved scheme can guarantee the data transfer with minimal hop to the sink，extend the survival time of the network effectively and enhance the scope of application.

wireless sensor networks；low energy adaptive clustering hierarchy；trust evaluation；multi－h(huán)op；survival time

TP 393.02；TP 212.9

A

1000－5013（2012）03－0255－05

2011－10－16

許力（1970－），男，教授，主要從事無線網(wǎng)絡(luò)與移動計算、網(wǎng)絡(luò)安全、網(wǎng)絡(luò)優(yōu)化的研究.E－mail：xuli＠fjnu.edu.cn.

福建省自然科學(xué)基金資助項目（2007J0316，2008J0014）；福建省教育廳重點基金資助項目（JA07030）

（責(zé)任編輯：黃曉楠 英文審校：吳逢鐵）