一種基于LEACH路由協議的改進算法

蔡悅潔，胡方明

(西安電子科技大學電子工程學院，陜西西安 710071)

一種基于LEACH路由協議的改進算法

蔡悅潔，胡方明

(西安電子科技大學電子工程學院，陜西西安 710071)

無線傳感器網絡的生存時間受傳感器節點軟硬件條件的限制，改進傳感器網絡路由協議是延長網絡生存時間的有效途徑。LEACH協議是最早提出的經典分層路由協議，文中基于LEACH協議提出改進，應用K－medoids算法改進LEACH協議的簇首分簇機制，并通過Matlab仿真實驗，證實了改進后的LEACH算法在均衡化網絡能耗，延長網絡的生命周期方面具有優越性。

無線傳感器網絡;路由協議;LEACH;K－medoids

隨著通信、傳感器和嵌入式計算技術的快速發展，具有通信、感知和數據計算處理能力的微型傳感器節點得到廣泛應用。由這些傳感器節點構成的無線傳感器網絡(Wireless Sensor Network，WSN)在軍事、醫療健康、環境監測、深空探測等領域有廣闊的應用前景，已經引起了人們的關注［1－5］。

由于無線傳感器網絡中傳感器節點受其自身軟硬件條件的限制，其能源有限，計算、存儲和通信能力較弱，同時存在節點死亡而退出網絡以及新節點加入擴展網絡使得無線傳感器網絡的拓撲結構處于動態變化中的情況，因此急需深入研究無線傳感器網絡路由協議，從而延長無線傳感器網絡的生命周期［6－7］。

無線傳感器網絡的路由協議主要功能是尋找源節點和目的節點之間的優化路徑，實現數據分組沿著優化路徑正確轉發。按照網絡的邏輯結構分類，路由協議可以分為平面路由協議和分層路由協議。平面路由中各個節點都將數據傳送到Sink節點，所有節點都具有相同的地位和功能，節點之間相互協作共同完成感知和數據處理任務。分層路由協議引入分層管理機制，網絡節點通常按照不同的分簇算法分成相應的簇(Cluster)。每個簇由一個簇首(Cluster Head)和多個簇成員(Cluster Member)組成，多個簇首節點形成更高一級的網絡，在高一級網絡中，又可以分簇，再次形成更高一級的網絡，直至最高級。LEACH協議就是最為典型的一種分層路由協議，針對LEACH協議的成簇方式引入一種K－中心點算法來改進LEACH算法的成簇機制，從而降低網絡成簇階段的能耗［8］。

1 LEACH協議

1.1 算法描述

LEACH協議將無線傳感器網絡中的節點分成若干個簇，通過隨機選擇簇首節點，平均分擔網絡的能量負載來實現降低網絡能耗、延長網絡生命周期。LEACH定義了“輪”(Round)的概念，協議分為多輪，每一輪由簇準備階段和穩定階段組成，簇準備階段和穩定的時間總和稱為一輪［9－10］。

在簇準備階段，LEACH協議采用完全分布式機制產生簇頭，設定一閾值T(n)，每個傳感器節點從0～1隨機數中任意選擇一個值，若當前輪中這個隨機數值小于設定的閾值T(n)，那么這個節點就當選為簇頭，閾值T(n)按式(1)計算。

其中，p是網絡中簇首所占比例;r是當前輪數;G是在最后1/p輪中沒有成為簇首節點集合;n指某一節點;T(n)實際上是在第r輪尚未做過簇首的節點當選為簇首的平均概率。

節點被選為簇首節點后，會主動向網絡發送廣播信息。其他節點根據接收到的信息選擇合適的發送簇首作為自己的簇首，并加入這個簇首的簇，節點選擇簇首的原則是選取信號強度最大的簇首加入。之后簇首節點建立TDMA調度，保證了簇內節點只在相應的時隙發送數據，減少了數據傳輸時的沖突。

在穩定階段，成員節點在自己的時隙里將數據發送給簇首節點，簇首節點對收集的數據進行融合，并將結果發送給Sink節點。之后重新選舉簇首節點進入新一輪循環。

1.2 LEACH協議的優缺點

LEACH協議的優點:隨機選取簇首節點，將能量消耗平均分配到所有節點，網絡負載比較均衡，仿真表明，相比于一般的平面路由協議，LEACH協議可以將網絡生命周期延長15%;由于采用層次結構，簇首節點形成高一層的網絡，使得節點路徑的選擇及路由信息的儲存都非常的簡單直接，節點不需要儲存大量路由信息，對于節點的要求降低;LEACH中采用的成簇技術使網絡具有較好的擴展性，同時簇首節點的輪流選擇使網絡具有較強的健壯性。

LEACH協議的缺陷:LEACH協議簇首的選取是隨機的，無法控制簇首在網絡中分布的位置，建簇時可能出現一些不合理的分簇方案，出現簇首分布過于集中或者分布于網絡邊緣，各個簇中節點數量不均衡，簇首與簇內節點的通信距離過遠，從而造成不必要的能量消耗;LEACH協議節點當選為簇首節點的概率均等，這可能會使一部分能量少的節點被選為簇首，能量低的節點擔任簇首節點時，將導致節點能量會過快地耗盡自身能量而影響網絡的正常運行;LEACH協議要求網絡中的節點與Sink節點能夠直接通信，這就限制了網絡的擴展性，使其不適用于大型網絡。因為對于大型網絡中里簇首節點較遠的成員節點和離Sink節點較遠的簇首節點而言，通信所造成的能耗將遠遠大于其他節點，這就影響了網絡的生命周期，降低網絡性能。

針對LEACH協議的簇首選取機制存在的缺陷，引入K－medoids算法改進簇首選取過程。

2 K－medoids算法改進LEACH協議

K－medoids算法屬于劃分方法中一種常見的聚類算法，圍繞中心點的劃分PAM(Partitioning Around Medoids)是最早提出的K－中心點算法之一［11］。當存在噪聲和孤立點時，算法仍具有較好的健壯性和魯棒性。

K－medoids算法先給每個簇隨機選擇一個初始代表對象。剩余的對象根據與其代表對象的距離分配給最近的一個簇，然后反復用非代表對象來替換代表對象，以改進聚類的質量。聚類質量用一個代價函數來估算，該函數度量一個非代表對象是否是當前一個代表對象的適合的代替者，如果是就進行替換，否則不替換［12－15］。

為判定一個非代表對象Orandom是否為當前代表對象Oi合適的替代者，對于每個非中心點對象P，每當重新分配時，平方誤差對代價函數有影響。

平均誤差公式

替代的總代價是所有非中心點對象所產生的代價之和。如果總代價是負的，那么實際的平方誤差將減小，即替換后的簇內差異會變小，Oi可以被Orandom替代。如果總代價總是正的或者為零，那么就表示算法不能產生一個有效的替換，即此時算法收斂。

算法描述:輸入，結果簇的數目k，包含n個對象的數據庫。輸出，k個簇，使得所有對象與其最近中心點的相異度總和取得最小。

(1)選擇、優化初始中心點并作初步劃分。選擇中心點，在n個對象中隨意選擇k個對象作為初始的中心點;初始劃分，以當前中心點對其他對象進行初始劃分;微調，在劃分得的各簇中對中心點進行微調。繼續劃分，以當前中心點對其他對象進行劃分。

(2)執行增量中心候選集K－medoids算法。主要有兩步:1)輪換中心并計算代價。2)實施中心替換。該階段算法流程如圖1 所示［17－18］。

通過初始中心的調整，使更多的中心點都有可能是最后聚類結果對應的中心點，收斂速度快。

K－medoids算法能在付出較小內存代價的前提下有效處理大數據集，適合大量樣本的情況，適用于LEACH協議分簇選舉簇首的要求。

另外，由于在每輪分簇選簇首節點時都采用K－medoids算法，從初始點到結束所需迭代的次數較多，這樣在選擇簇首節點時會消耗過多的能量來調整簇首的位置，所以需要合理地設定每一次使用K－medoids算法迭代的次數，使簇首在盡量少的調整次數中被調整到理想的位置［19－20］。

圖1 執行增量中心候選集K－medoids算法流程

3 Matlab仿真

本文使用Matlab分別對傳統LEACH算法和引入K－medoids算法改進后的LEACH算法進行仿真。

3.1 簇首分簇仿真比較

仿真環境:

(1)100個隨機分布的節點和一個固定的Sink節點，Sink 節點坐標為(0，0)。

(2)網絡平面區域:100×200，等價于50 m×100 m。

(3)網絡分簇:6個簇。

(4)每個無線傳感器節點的初始能量:2 J。

(5)仿真次數:10次。

圖2為其中一次傳統LEACH協議通過隨機選取簇首節點的仿真圖，圖中最小的簇僅含有7個節點，最大的簇含有29個節點。經多次仿真發現傳統LEACH協議的分簇不均衡，關鍵是同一個簇中不同的成員節點到簇首的距離相差很大。

圖3是采用K－medoids算法分簇選舉簇首的一張示意圖，其中包含節點最多的簇有24個節點，包含節點最少的簇有12個節點。經多次仿真發現，相比于傳統的LEACH協議隨機選舉簇首分簇的方法，采用了K－medoids算法改進后整個網絡劃分相對而言更均衡，同時，大部分節點到簇首的距離更接近平均值。

圖2 傳統LEACH協議分簇產生簇首的示意圖

圖3 采用K－medoids算法分簇產生簇首的示意圖

3.2 改進前后節點存活數目的比較

網絡中每輪存活的節點數目反映了無線傳感器網絡性能的優劣。存活的節點數目越多，網絡覆蓋區域就越廣，下一輪參與選舉簇首的節點就越多，也延長了網絡的生命周期。下面是傳統LEACH協議和改進LEACH協議在節點存活數目上的比較。

參數:節點數目NodeNums=100;仿真區域AreaR=100;節點數據傳輸半徑 NodeTranR=10;仿真時間MaxInteral=200 s;簇首節點的百分比Pch=0.05，即100個節點的網絡形成5個簇首劃分為5個簇節點每次發送的數據量Kbit=2 000 kbit。

圖4 節點存活數目對比

由圖4可見，改進型LEACH協議在同一時間點的節點存活數目明顯比傳統LEACH多，并且節點存活時間相對而言更長。所以優化后的網絡簇首選擇方案能提網絡的性能，延長網絡的生命周期。

4 結束語

在LEACH協議的基礎上，引入K－medoids改進傳統LEACH算法的簇首分簇機制，均衡化網絡的能量損耗，從而延長無線傳感器網絡的生命周期。

［1］李建中，李金寶，石勝飛.傳感器網絡及其數據管理的概念、問題與進展［J］.軟件學報，2003，14(10):1717 －1727.

［2］司海飛，楊忠，王珺.無線傳感器網絡研究現狀與應用［J］.機電工程，2011，28(1):16 －20.

［3］葉湘濱，陳利虎，胡罡.無線傳感器網絡在環境監測中的應用［J］.計算機測量與控制，2004，12(11).

［4］李翔，譚敏生，李攀.淺析無線傳感器網絡在醫療系統中的應用［J］.工業控制計算機，2011，24(4).

［5］卿利，朱清新，王明文.異構傳感器網絡的分布式能量有效成簇算法［J］.軟件學報，2006，43(5):51－58.

［6］TERRY J.Ten emerging technologies that will change the world［J］.Technology Review，2003，106(1):22 －49.

［7］MHATRE V，ROSENBERG C.Design guidelines for wireless sensor networks communication clusetering and aggregation［J］.Ad － hoc Networks Journal Elsevier Science，2004，2(1):45－63.

［8］ROYER E M，TOH C K.A review of current routing protocols for Ad hoc networks［J］.IEEE Personal Communications，1996，6(2):45 －55.

［9］WENDI B HEINZELMAN，ANANTHA P CHANDRAKASAN，HARI BALAKRISHNAN.An application specific protocol architecture for wireless microsensor networks ［J］.IEEE Transactions on Wirel Ess Communications，2002，1(4):660－670.

［10］WENDI B HEINZELMAN，ANANTHA P CHANDRAKASAN，HARI BALAKRISHNAN.Energy efficient communication protocols for wireless microsensor networks［C］.the Hawaii International Conference on System Sciences，2000.

［11］HAN Jiawei，KAMBER M.數據挖掘概念與技術［M］.2版.北京:機械工業出版社，2008.

［12］呂振，白婷婷，馬興朋，等.淺談無線傳感器網絡路由協議［J］.微計算機信息，2010，26(10):98 －100.

［13］任豐原，黃海寧，林闖.無線傳感器網絡［J］.軟件學報，2003，14(7):1282 －1291.

［14］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005.

［15］PERILLO M，CHENG Z，HEINZLEMAN W.An analysis of strategies for mitigating the sensor network hot spot problem［C］.Proc.of Collaboratecom，2005.

［16］NISHIMURA C E，CONLON D M.IUSS dual use:Monitoring whales and earthquakes using SOSUS ［J］.Mar Technol.Soc.J，1994，27(4):13 －21.

［17］夏寧霞，蘇一丹，覃希.一種高效的K－medoids聚類算法［J］.計算機應用研究，2010，27(12):4517 －4519

［18］李鋼.無線傳感器網絡路由協議的研究與仿真［D］.北京:北京郵電大學，2008.

［19］李巖.無線網絡路由協議的研究——基于LEACH的無線傳感網絡路由協議研究［D］.無錫:江南大學，2008.

［20］陳耀典.無線傳感器網絡LEACH分簇路由協議的改進與仿真［D］.廣州:中山大學，2010.

An Improved Algorithm of Routing Protocol Based on LEACH

CAI Yuejie，HU Fangming
(School of Electronic Engineering，Xidian University，Xi'an 710071，China)

Due to the limitation of software and hardware of the sensor node，lifetime of Wireless sensor network(WSN)is limited，and the research of WSN routing protocol is one of the most effective ways to extend the network lifetime.LEACH protocol is a classical cluster routing protocol.This paper proposes an improvement based on LEACH protocol，applying K-medoids algorithms to improve the mechanism of the selection of cluster head.Simulation results have confirmed that the improved LEACH protocol is superior in extending network lifetime and equalizing energy wastage.

wireless sensor network;routing protocol;LEACH;K-medoids

TP212.9

A

1007－7820(2012)08－128－04

2012-01-17

中央高校基本科研業務費專項基金資助(K50510020034)

蔡悅潔(1986—)，男，碩士研究生。研究方向:無線傳感器網絡。