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

黃靜，許力

（1.福建師范大學 數學與計算機科學學院，福建 福州 350007；2.泉州經貿職業技術學院 輕工與信息專業部，福建 泉州 362411）

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

黃靜1，2，許力1

（1.福建師范大學 數學與計算機科學學院，福建 福州 350007；2.泉州經貿職業技術學院 輕工與信息專業部，福建 泉州 362411）

通過分析低功耗自適應集簇分層型協議（LEACH）和基于可信度的低功耗自適應集簇分層型協議（TE－LEACH）算法的不足，提出一種基于可信度的簇間多跳低功耗自適應集簇分層型協議（TEM－LEACH）算法 .該算法既考慮簇頭節點傳輸數據的可信度，又引入網關節點構建路由主干網，保證數據經過最少的跳數傳輸到基站，有效地延長無線傳感器網絡生存時間，增加了LEACH算法的適用范圍.

無線傳感器網絡；低功耗自適應集簇分層型協議；可信度；多跳；生存時間

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

1 算法的提出

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

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

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

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

2 算法的描述

在無線傳感器網絡中，假設每個節點具有唯一的節點標識ID（1≤ID≤n），所屬簇標識為CID.每個節點都可以通過一定的定位機制知道自己的位置及自身的剩余能量.

2.1 網關的選取

假設兩簇頭的距離為d，則簇域間存在以下4種可能的關系.

1）當0＜d≤r時，兩簇頭節點可以直接通信，轉發數據，如圖2（a）所示.

2）當r＜d≤2r時，兩簇間存在公共節點，則在bb公共節點中選取一個節點做為網關節點；若公共節點同時屬于多個簇，則從同時屬于最多簇的候選網關節點集合中選擇一個作為網關節點，承擔數據轉發任務，如圖2（b）所示.

3）當2r＜d≤3r時，兩簇間不存在公共節點，則在各簇內選取一個節點做為網關節點，使選取的網關節點可以直接通信，如圖2（c）所示.

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

圖2 簇域間的關系Fig.2 Relationship between clusters

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

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

式中：e為節點的自身剩余能量與網絡的平均能量的比值；t為可信度值；c為候選網關節點連接簇頭的個數與網絡中節點的總數的比值；α，β，γ為參數因子，α＋β＋γ＝1，且α，β，γ＞0.

通過α，β，γ參數因子可以動態調節節點剩余能量、可信度和節點的連接度對f的影響.若f值相同，再根據節點的標識ID，選取標識ID最小的節點做為網關.

2.2 網關部分偽代碼的選取

2.3 網絡數據傳輸的實現

網絡中所有節點都是同構的，在成簇階段，普通節點在自己的時隙內發送完數據后就關閉節點處于休眠狀態.進入數據轉發階段，被選為網關的普通節點會根據需要被喚醒，承擔簇間的數據轉發任務.網關進行數據轉發后，節點能量發生變化，為保持網絡的連通，當網關能量變化超過一個變化閾值的時候，向其所屬簇的簇頭發送一個更新信號，通知各簇頭更換剩余候選網關中平均度量值最大的節點為新的網關.

網絡配置完成后，假設各節點（包括基站）時鐘同步，或者通過基站向各節點發送同步脈沖信號實現基站與節點的時鐘同步.

1）簇內通信.所有簇成員節點將各自檢測感應到的數據在簇頭分配的時間片內，以單跳的形式傳輸給簇頭，而簇頭在一定得時間內將收到簇內節發送的數據進行數據融合.

2）簇間通信.簇頭節點和網關節點構成無線傳感器網絡的路由主干網.簇頭節點通過路由主干網將收集到的數據采用多跳傳輸至基站；簇頭節點根據貪心算法來選擇下一跳數據轉發節點，在其通信范圍內選取一個離基站最近的路由主干網節點做為下一跳數據轉發節點.

3 仿真結果與分析

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

3.1 網絡生存時間的比較

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

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

圖3 不同算法的網絡生命周期Fig.3 Network lifetime of different algorithms

3.2 能量消耗比較

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

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

圖4 各算法的每輪網絡消耗能量Fig.4 Each algorithm′s energy consumption per round

4 結論

提出的基于可信度的簇間多跳LEACH算法，既考慮到簇頭節點傳輸數據的可信度，又引入網關節點構建路由主干網，保證了數據經過最少的跳數傳輸到基站，彌補了LEACH和TE－LEACH算法的不足，從而使網絡壽命得到了相應的延長.

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

從LEACH，TE－LEACH和TEM－LEACH算法的仿真中可以看出：對于節點密度越高的無線傳感器網絡，TEM－LEACH算法的網絡生命周期就越長 .這是由于采用了多跳的數據傳輸方式，每輪網絡的能量消耗總額大大減少，直觀地體現了TEM－LEACH算法在高密度、大規模網絡下的優勢.該算法不僅可以有效地延長無線傳感器網絡生存時間，也增加了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 拓撲算法改進［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，Fujian Normal University，Fuzhou 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－hop 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－hop；survival time

TP 393.02；TP 212.9

A

1000－5013（2012）03－0255－05

2011－10－16

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

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

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