蔡悅潔，胡方明

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

一種基于LEACH路由協(xié)議的改進(jìn)算法

蔡悅潔，胡方明

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

無(wú)線傳感器網(wǎng)絡(luò)的生存時(shí)間受傳感器節(jié)點(diǎn)軟硬件條件的限制，改進(jìn)傳感器網(wǎng)絡(luò)路由協(xié)議是延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的有效途徑。LEACH協(xié)議是最早提出的經(jīng)典分層路由協(xié)議，文中基于LEACH協(xié)議提出改進(jìn)，應(yīng)用K－medoids算法改進(jìn)LEACH協(xié)議的簇首分簇機(jī)制，并通過(guò)Matlab仿真實(shí)驗(yàn)，證實(shí)了改進(jìn)后的LEACH算法在均衡化網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期方面具有優(yōu)越性。

無(wú)線傳感器網(wǎng)絡(luò);路由協(xié)議;LEACH;K－medoids

隨著通信、傳感器和嵌入式計(jì)算技術(shù)的快速發(fā)展，具有通信、感知和數(shù)據(jù)計(jì)算處理能力的微型傳感器節(jié)點(diǎn)得到廣泛應(yīng)用。由這些傳感器節(jié)點(diǎn)構(gòu)成的無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)在軍事、醫(yī)療健康、環(huán)境監(jiān)測(cè)、深空探測(cè)等領(lǐng)域有廣闊的應(yīng)用前景，已經(jīng)引起了人們的關(guān)注［1－5］。

由于無(wú)線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)受其自身軟硬件條件的限制，其能源有限，計(jì)算、存儲(chǔ)和通信能力較弱，同時(shí)存在節(jié)點(diǎn)死亡而退出網(wǎng)絡(luò)以及新節(jié)點(diǎn)加入擴(kuò)展網(wǎng)絡(luò)使得無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)處于動(dòng)態(tài)變化中的情況，因此急需深入研究無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議，從而延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期［6－7］。

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

1 LEACH協(xié)議

1.1 算法描述

LEACH協(xié)議將無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)分成若干個(gè)簇，通過(guò)隨機(jī)選擇簇首節(jié)點(diǎn)，平均分擔(dān)網(wǎng)絡(luò)的能量負(fù)載來(lái)實(shí)現(xiàn)降低網(wǎng)絡(luò)能耗、延長(zhǎng)網(wǎng)絡(luò)生命周期。LEACH定義了“輪”(Round)的概念，協(xié)議分為多輪，每一輪由簇準(zhǔn)備階段和穩(wěn)定階段組成，簇準(zhǔn)備階段和穩(wěn)定的時(shí)間總和稱為一輪［9－10］。

在簇準(zhǔn)備階段，LEACH協(xié)議采用完全分布式機(jī)制產(chǎn)生簇頭，設(shè)定一閾值T(n)，每個(gè)傳感器節(jié)點(diǎn)從0～1隨機(jī)數(shù)中任意選擇一個(gè)值，若當(dāng)前輪中這個(gè)隨機(jī)數(shù)值小于設(shè)定的閾值T(n)，那么這個(gè)節(jié)點(diǎn)就當(dāng)選為簇頭，閾值T(n)按式(1)計(jì)算。

其中，p是網(wǎng)絡(luò)中簇首所占比例;r是當(dāng)前輪數(shù);G是在最后1/p輪中沒(méi)有成為簇首節(jié)點(diǎn)集合;n指某一節(jié)點(diǎn);T(n)實(shí)際上是在第r輪尚未做過(guò)簇首的節(jié)點(diǎn)當(dāng)選為簇首的平均概率。

節(jié)點(diǎn)被選為簇首節(jié)點(diǎn)后，會(huì)主動(dòng)向網(wǎng)絡(luò)發(fā)送廣播信息。其他節(jié)點(diǎn)根據(jù)接收到的信息選擇合適的發(fā)送簇首作為自己的簇首，并加入這個(gè)簇首的簇，節(jié)點(diǎn)選擇簇首的原則是選取信號(hào)強(qiáng)度最大的簇首加入。之后簇首節(jié)點(diǎn)建立TDMA調(diào)度，保證了簇內(nèi)節(jié)點(diǎn)只在相應(yīng)的時(shí)隙發(fā)送數(shù)據(jù)，減少了數(shù)據(jù)傳輸時(shí)的沖突。

在穩(wěn)定階段，成員節(jié)點(diǎn)在自己的時(shí)隙里將數(shù)據(jù)發(fā)送給簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)對(duì)收集的數(shù)據(jù)進(jìn)行融合，并將結(jié)果發(fā)送給Sink節(jié)點(diǎn)。之后重新選舉簇首節(jié)點(diǎn)進(jìn)入新一輪循環(huán)。

1.2 LEACH協(xié)議的優(yōu)缺點(diǎn)

LEACH協(xié)議的優(yōu)點(diǎn):隨機(jī)選取簇首節(jié)點(diǎn)，將能量消耗平均分配到所有節(jié)點(diǎn)，網(wǎng)絡(luò)負(fù)載比較均衡，仿真表明，相比于一般的平面路由協(xié)議，LEACH協(xié)議可以將網(wǎng)絡(luò)生命周期延長(zhǎng)15%;由于采用層次結(jié)構(gòu)，簇首節(jié)點(diǎn)形成高一層的網(wǎng)絡(luò)，使得節(jié)點(diǎn)路徑的選擇及路由信息的儲(chǔ)存都非常的簡(jiǎn)單直接，節(jié)點(diǎn)不需要儲(chǔ)存大量路由信息，對(duì)于節(jié)點(diǎn)的要求降低;LEACH中采用的成簇技術(shù)使網(wǎng)絡(luò)具有較好的擴(kuò)展性，同時(shí)簇首節(jié)點(diǎn)的輪流選擇使網(wǎng)絡(luò)具有較強(qiáng)的健壯性。

LEACH協(xié)議的缺陷:LEACH協(xié)議簇首的選取是隨機(jī)的，無(wú)法控制簇首在網(wǎng)絡(luò)中分布的位置，建簇時(shí)可能出現(xiàn)一些不合理的分簇方案，出現(xiàn)簇首分布過(guò)于集中或者分布于網(wǎng)絡(luò)邊緣，各個(gè)簇中節(jié)點(diǎn)數(shù)量不均衡，簇首與簇內(nèi)節(jié)點(diǎn)的通信距離過(guò)遠(yuǎn)，從而造成不必要的能量消耗;LEACH協(xié)議節(jié)點(diǎn)當(dāng)選為簇首節(jié)點(diǎn)的概率均等，這可能會(huì)使一部分能量少的節(jié)點(diǎn)被選為簇首，能量低的節(jié)點(diǎn)擔(dān)任簇首節(jié)點(diǎn)時(shí)，將導(dǎo)致節(jié)點(diǎn)能量會(huì)過(guò)快地耗盡自身能量而影響網(wǎng)絡(luò)的正常運(yùn)行;LEACH協(xié)議要求網(wǎng)絡(luò)中的節(jié)點(diǎn)與Sink節(jié)點(diǎn)能夠直接通信，這就限制了網(wǎng)絡(luò)的擴(kuò)展性，使其不適用于大型網(wǎng)絡(luò)。因?yàn)閷?duì)于大型網(wǎng)絡(luò)中里簇首節(jié)點(diǎn)較遠(yuǎn)的成員節(jié)點(diǎn)和離Sink節(jié)點(diǎn)較遠(yuǎn)的簇首節(jié)點(diǎn)而言，通信所造成的能耗將遠(yuǎn)遠(yuǎn)大于其他節(jié)點(diǎn)，這就影響了網(wǎng)絡(luò)的生命周期，降低網(wǎng)絡(luò)性能。

針對(duì)LEACH協(xié)議的簇首選取機(jī)制存在的缺陷，引入K－medoids算法改進(jìn)簇首選取過(guò)程。

2 K－medoids算法改進(jìn)LEACH協(xié)議

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

K－medoids算法先給每個(gè)簇隨機(jī)選擇一個(gè)初始代表對(duì)象。剩余的對(duì)象根據(jù)與其代表對(duì)象的距離分配給最近的一個(gè)簇，然后反復(fù)用非代表對(duì)象來(lái)替換代表對(duì)象，以改進(jìn)聚類的質(zhì)量。聚類質(zhì)量用一個(gè)代價(jià)函數(shù)來(lái)估算，該函數(shù)度量一個(gè)非代表對(duì)象是否是當(dāng)前一個(gè)代表對(duì)象的適合的代替者，如果是就進(jìn)行替換，否則不替換［12－15］。

為判定一個(gè)非代表對(duì)象Orandom是否為當(dāng)前代表對(duì)象Oi合適的替代者，對(duì)于每個(gè)非中心點(diǎn)對(duì)象P，每當(dāng)重新分配時(shí)，平方誤差對(duì)代價(jià)函數(shù)有影響。

平均誤差公式

替代的總代價(jià)是所有非中心點(diǎn)對(duì)象所產(chǎn)生的代價(jià)之和。如果總代價(jià)是負(fù)的，那么實(shí)際的平方誤差將減小，即替換后的簇內(nèi)差異會(huì)變小，Oi可以被Orandom替代。如果總代價(jià)總是正的或者為零，那么就表示算法不能產(chǎn)生一個(gè)有效的替換，即此時(shí)算法收斂。

算法描述:輸入，結(jié)果簇的數(shù)目k，包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出，k個(gè)簇，使得所有對(duì)象與其最近中心點(diǎn)的相異度總和取得最小。

(1)選擇、優(yōu)化初始中心點(diǎn)并作初步劃分。選擇中心點(diǎn)，在n個(gè)對(duì)象中隨意選擇k個(gè)對(duì)象作為初始的中心點(diǎn);初始劃分，以當(dāng)前中心點(diǎn)對(duì)其他對(duì)象進(jìn)行初始劃分;微調(diào)，在劃分得的各簇中對(duì)中心點(diǎn)進(jìn)行微調(diào)。繼續(xù)劃分，以當(dāng)前中心點(diǎn)對(duì)其他對(duì)象進(jìn)行劃分。

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

通過(guò)初始中心的調(diào)整，使更多的中心點(diǎn)都有可能是最后聚類結(jié)果對(duì)應(yīng)的中心點(diǎn)，收斂速度快。

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

另外，由于在每輪分簇選簇首節(jié)點(diǎn)時(shí)都采用K－medoids算法，從初始點(diǎn)到結(jié)束所需迭代的次數(shù)較多，這樣在選擇簇首節(jié)點(diǎn)時(shí)會(huì)消耗過(guò)多的能量來(lái)調(diào)整簇首的位置，所以需要合理地設(shè)定每一次使用K－medoids算法迭代的次數(shù)，使簇首在盡量少的調(diào)整次數(shù)中被調(diào)整到理想的位置［19－20］。

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

3 Matlab仿真

本文使用Matlab分別對(duì)傳統(tǒng)LEACH算法和引入K－medoids算法改進(jìn)后的LEACH算法進(jìn)行仿真。

3.1 簇首分簇仿真比較

仿真環(huán)境:

(1)100個(gè)隨機(jī)分布的節(jié)點(diǎn)和一個(gè)固定的Sink節(jié)點(diǎn)，Sink 節(jié)點(diǎn)坐標(biāo)為(0，0)。

(2)網(wǎng)絡(luò)平面區(qū)域:100×200，等價(jià)于50 m×100 m。

(3)網(wǎng)絡(luò)分簇:6個(gè)簇。

(4)每個(gè)無(wú)線傳感器節(jié)點(diǎn)的初始能量:2 J。

(5)仿真次數(shù):10次。

圖2為其中一次傳統(tǒng)LEACH協(xié)議通過(guò)隨機(jī)選取簇首節(jié)點(diǎn)的仿真圖，圖中最小的簇僅含有7個(gè)節(jié)點(diǎn)，最大的簇含有29個(gè)節(jié)點(diǎn)。經(jīng)多次仿真發(fā)現(xiàn)傳統(tǒng)LEACH協(xié)議的分簇不均衡，關(guān)鍵是同一個(gè)簇中不同的成員節(jié)點(diǎn)到簇首的距離相差很大。

圖3是采用K－medoids算法分簇選舉簇首的一張示意圖，其中包含節(jié)點(diǎn)最多的簇有24個(gè)節(jié)點(diǎn)，包含節(jié)點(diǎn)最少的簇有12個(gè)節(jié)點(diǎn)。經(jīng)多次仿真發(fā)現(xiàn)，相比于傳統(tǒng)的LEACH協(xié)議隨機(jī)選舉簇首分簇的方法，采用了K－medoids算法改進(jìn)后整個(gè)網(wǎng)絡(luò)劃分相對(duì)而言更均衡，同時(shí)，大部分節(jié)點(diǎn)到簇首的距離更接近平均值。

圖2 傳統(tǒng)LEACH協(xié)議分簇產(chǎn)生簇首的示意圖

圖3 采用K－medoids算法分簇產(chǎn)生簇首的示意圖

3.2 改進(jìn)前后節(jié)點(diǎn)存活數(shù)目的比較

網(wǎng)絡(luò)中每輪存活的節(jié)點(diǎn)數(shù)目反映了無(wú)線傳感器網(wǎng)絡(luò)性能的優(yōu)劣。存活的節(jié)點(diǎn)數(shù)目越多，網(wǎng)絡(luò)覆蓋區(qū)域就越廣，下一輪參與選舉簇首的節(jié)點(diǎn)就越多，也延長(zhǎng)了網(wǎng)絡(luò)的生命周期。下面是傳統(tǒng)LEACH協(xié)議和改進(jìn)LEACH協(xié)議在節(jié)點(diǎn)存活數(shù)目上的比較。

參數(shù):節(jié)點(diǎn)數(shù)目NodeNums=100;仿真區(qū)域AreaR=100;節(jié)點(diǎn)數(shù)據(jù)傳輸半徑 NodeTranR=10;仿真時(shí)間MaxInteral=200 s;簇首節(jié)點(diǎn)的百分比Pch=0.05，即100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)形成5個(gè)簇首劃分為5個(gè)簇節(jié)點(diǎn)每次發(fā)送的數(shù)據(jù)量Kbit=2 000 kbit。

圖4 節(jié)點(diǎn)存活數(shù)目對(duì)比

由圖4可見(jiàn)，改進(jìn)型LEACH協(xié)議在同一時(shí)間點(diǎn)的節(jié)點(diǎn)存活數(shù)目明顯比傳統(tǒng)LEACH多，并且節(jié)點(diǎn)存活時(shí)間相對(duì)而言更長(zhǎng)。所以優(yōu)化后的網(wǎng)絡(luò)簇首選擇方案能提網(wǎng)絡(luò)的性能，延長(zhǎng)網(wǎng)絡(luò)的生命周期。

4 結(jié)束語(yǔ)

在LEACH協(xié)議的基礎(chǔ)上，引入K－medoids改進(jìn)傳統(tǒng)LEACH算法的簇首分簇機(jī)制，均衡化網(wǎng)絡(luò)的能量損耗，從而延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期。

［1］李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問(wèn)題與進(jìn)展［J］.軟件學(xué)報(bào)，2003，14(10):1717 －1727.

［2］司海飛，楊忠，王珺.無(wú)線傳感器網(wǎng)絡(luò)研究現(xiàn)狀與應(yīng)用［J］.機(jī)電工程，2011，28(1):16 －20.

［3］葉湘濱，陳利虎，胡罡.無(wú)線傳感器網(wǎng)絡(luò)在環(huán)境監(jiān)測(cè)中的應(yīng)用［J］.計(jì)算機(jī)測(cè)量與控制，2004，12(11).

［4］李翔，譚敏生，李攀.淺析無(wú)線傳感器網(wǎng)絡(luò)在醫(yī)療系統(tǒng)中的應(yīng)用［J］.工業(yè)控制計(jì)算機(jī)，2011，24(4).

［5］卿利，朱清新，王明文.異構(gòu)傳感器網(wǎng)絡(luò)的分布式能量有效成簇算法［J］.軟件學(xué)報(bào)，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.數(shù)據(jù)挖掘概念與技術(shù)［M］.2版.北京:機(jī)械工業(yè)出版社，2008.

［12］呂振，白婷婷，馬興朋，等.淺談無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.微計(jì)算機(jī)信息，2010，26(10):98 －100.

［13］任豐原，黃海寧，林闖.無(wú)線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，2003，14(7):1282 －1291.

［14］孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，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］.計(jì)算機(jī)應(yīng)用研究，2010，27(12):4517 －4519

［18］李鋼.無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議的研究與仿真［D］.北京:北京郵電大學(xué)，2008.

［19］李巖.無(wú)線網(wǎng)絡(luò)路由協(xié)議的研究——基于LEACH的無(wú)線傳感網(wǎng)絡(luò)路由協(xié)議研究［D］.無(wú)錫:江南大學(xué)，2008.

［20］陳耀典.無(wú)線傳感器網(wǎng)絡(luò)LEACH分簇路由協(xié)議的改進(jìn)與仿真［D］.廣州:中山大學(xué)，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

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)基金資助(K50510020034)

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