引言

　　無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network ,簡(jiǎn)稱WSN）是監(jiān)視遠(yuǎn)程環(huán)境的有力工具之一，它的基本功能是收集并返回傳感器節(jié)點(diǎn)所在監(jiān)測(cè)區(qū)域的信息。由于工作環(huán)境和自身構(gòu)造的限制，傳感器節(jié)點(diǎn)一般是電池供電，并且節(jié)點(diǎn)的更換和充電也較難實(shí)現(xiàn)。因此，降低節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期是無線傳感器網(wǎng)絡(luò)傳輸機(jī)制的一個(gè)主要研究目標(biāo)。

　　網(wǎng)絡(luò)數(shù)據(jù)傳輸離不開路由協(xié)議，路由協(xié)議對(duì)網(wǎng)絡(luò)的整體性能有重要影響，因此，作為無線傳感器網(wǎng)絡(luò)技術(shù)之一的路由協(xié)議一直是研究的熱點(diǎn)。

　　路由算法在路由協(xié)議中起著至關(guān)重要的作用，無線傳感器網(wǎng)絡(luò)中的路由算法從網(wǎng)絡(luò)邏輯結(jié)構(gòu)角度可以分為平面路由和層次路由。層次路由算法是無線傳感器網(wǎng)絡(luò)路由算法的研究重點(diǎn)，其中，LEACH算法是比較具有代表性的層次型路由算法。

　　本文在LEACH 算法的基礎(chǔ)上，介紹一種改進(jìn)的路由算法，改進(jìn)算法的成簇方式相對(duì)固定，減少了構(gòu)造簇的能量消耗。簇形成之后，在簇頭間構(gòu)造生成樹，簇間通過多跳方式通信，降低了簇頭節(jié)點(diǎn)之間長(zhǎng)距離通信的能耗。

　　2 LEACH 算法

　　2. 1 LEACH 算法描述

　　LEACH （Low2Energy Adaptive ClusteringHierarchy）算法是由MIT 的Heinzelman 等人提出的一種低功耗自適應(yīng)分簇算法。其基本思想是以循環(huán)的方式隨機(jī)選擇簇頭節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載均勻分配到網(wǎng)絡(luò)中的每個(gè)傳感器節(jié)點(diǎn)，從而達(dá)到降低網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)生存周期的目的。

　　LEACH 在運(yùn)行過程中不斷地循環(huán)執(zhí)行簇的重構(gòu)。算法操作使用了“輪”的概念，每一輪由初始化和穩(wěn)定的工作兩個(gè)階段組成。在初始化階段，每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，如果某個(gè)節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)小于所設(shè)的閾值T（n），則該節(jié)點(diǎn)發(fā)布自己是簇頭的消息，T（n）的計(jì)算公式設(shè)為：

　　其中，p是簇頭占所有節(jié)點(diǎn)的百分比，即節(jié)點(diǎn)當(dāng)選簇頭的概率；r表示目前進(jìn)行的輪數(shù)；G代表近1/p輪中還沒有當(dāng)選過簇頭的節(jié)點(diǎn)集合。

　　非簇頭節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)弱來選擇加入到哪個(gè)簇，并通知相應(yīng)的簇頭。在穩(wěn)定階段，簇內(nèi)的節(jié)點(diǎn)通過TDMA 方式與簇頭進(jìn)行通信，簇頭節(jié)點(diǎn)接收簇內(nèi)其它節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，并將這些數(shù)據(jù)進(jìn)行融合，然后發(fā)送給基站。

　　2. 2 LEACH算法的不足及其改進(jìn)算法

　　在LEACH算法中，每一輪循環(huán)都要重新構(gòu)造簇，而構(gòu)造簇的能量開銷比較大。其次，遠(yuǎn)離匯聚節(jié)點(diǎn)的簇頭節(jié)點(diǎn)可能會(huì)由于長(zhǎng)距離發(fā)送數(shù)據(jù)而過早耗盡自身能量，造成網(wǎng)絡(luò)分割。另外，LEACH算法沒有考慮簇頭節(jié)點(diǎn)當(dāng)前的能量狀況，如果能量很低的節(jié)點(diǎn)當(dāng)選為簇頭節(jié)點(diǎn)，那么將會(huì)加速該節(jié)點(diǎn)的死亡，影響整個(gè)網(wǎng)絡(luò)的生命周期。

　　以LEACH算法的思想為基礎(chǔ)，針對(duì)LEACH存在的不足，研究人員提出了很多的改進(jìn)算法，例如LEACH2C（LEACH2Cent ralized）， LEACH2EA（Energy Average）等算法。LEACH2C算法是由基站基于整個(gè)網(wǎng)絡(luò)信息集中挑選簇頭，每個(gè)節(jié)點(diǎn)把自身地理位置和當(dāng)前能量給基站，基站根據(jù)所有節(jié)點(diǎn)的信息計(jì)算出平均能量，低于平均能量的節(jié)點(diǎn)不能成為候選簇頭，基站根據(jù)所有成員節(jié)點(diǎn)到簇頭的距離平方和的原則，從剩余候選節(jié)點(diǎn)中選出合適數(shù)量和地理位置的簇頭集合，由基站將簇頭集合以及簇的結(jié)構(gòu)廣播出去。

　　基于LEACH2C的思想，針對(duì)LEACH 的不足，提出了可有效解決網(wǎng)絡(luò)能耗不均衡問題，延長(zhǎng)網(wǎng)絡(luò)生命周期的LEACH2EA（Energy Average ） 算法。

　　LEACH2EA算法的簇頭選擇綜合考慮了節(jié)點(diǎn)的當(dāng)前能量和每輪結(jié)束后的節(jié)點(diǎn)平均能量，比較適用于長(zhǎng)時(shí)間運(yùn)行且規(guī)模較大的網(wǎng)絡(luò)。

　　3 改進(jìn)的算法

　　3. 1 改進(jìn)算法的基本思想

　　本文的改進(jìn)算法也按輪的機(jī)制運(yùn)行，但是與LEACH不同的是，改進(jìn)后的算法不必每一輪都重新構(gòu)建簇。

　　改進(jìn)算法運(yùn)行到第N輪，當(dāng)N為奇數(shù)時(shí)，新算法采用與LEACH2EA相同的機(jī)制選擇簇頭，這樣產(chǎn)生的簇頭在新算法中稱為活動(dòng)簇頭，活動(dòng)簇頭選定后，該活動(dòng)簇頭發(fā)布自己是簇頭的消息，非簇頭節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)弱來選擇加入哪個(gè)簇，并通知相應(yīng)的活動(dòng)簇頭，完成簇的建立。簇建立之后，簇內(nèi)節(jié)點(diǎn)通過單跳通信方式直接向其簇頭節(jié)點(diǎn)傳送數(shù)據(jù)。當(dāng)N為偶數(shù)時(shí)，原來的簇固定不變。如果此時(shí)活動(dòng)簇頭節(jié)點(diǎn)能量低于某一個(gè)門限值時(shí)，則在原簇內(nèi)重新選擇簇頭節(jié)點(diǎn)，以簇內(nèi)剩余能量多的節(jié)點(diǎn)為新的簇頭節(jié)點(diǎn)，這樣產(chǎn)生的簇頭在新算法中稱為固定簇頭。為降低簇頭（包括活動(dòng)簇頭和固定簇頭）節(jié)點(diǎn)的通信代價(jià)，在簇頭間構(gòu)造樹形路由，簇頭間以多跳方式通信。

　　3. 2 改進(jìn)算法的描述

　　3. 2. 1 簇的建立和簇內(nèi)通信

　　改進(jìn)算法第N輪的開始，首先判斷N是奇數(shù)還是偶數(shù)。當(dāng)N是奇數(shù)時(shí)，就需要重新構(gòu)建簇，此時(shí)，采用與LEACH2EA相同的簇頭選擇機(jī)制?；顒?dòng)簇頭選擇過程如下：每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，如果這個(gè)數(shù)小于閾值T（n），則該節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播它是簇頭的消息，參照LEACH2EA 的閾值計(jì)算公式T（n）可表示為：

　　其中，p是簇頭占所有節(jié)點(diǎn)的百分比，即節(jié)點(diǎn)當(dāng)選簇頭的概率；r代表目前進(jìn)行的輪數(shù)；G表示近1/p輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)集合； En2current表示節(jié)點(diǎn)的當(dāng)前能量；Eaver表示每一輪結(jié)束后節(jié)點(diǎn)的平均能量。

　　節(jié)點(diǎn)當(dāng)選為活動(dòng)簇頭后，該活動(dòng)簇頭廣播自己是簇頭的消息，非簇頭節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)弱來選擇加入哪個(gè)簇，并通知相應(yīng)的活動(dòng)簇頭，完成簇的建立?；顒?dòng)簇頭接收到所有的加入信息后，就產(chǎn)生一個(gè)TDMA定時(shí)信息表，給簇中每個(gè)非簇頭成員節(jié)點(diǎn)分配傳送數(shù)據(jù)的時(shí)間片，成員節(jié)點(diǎn)只能在其特定的時(shí)間片內(nèi)與簇頭節(jié)點(diǎn)進(jìn)行通信。算法執(zhí)行首輪時(shí)，簇的建立與此種情況相同。

　　當(dāng)N是偶數(shù)時(shí)，則原來的簇固定不變。如果活動(dòng)簇頭節(jié)點(diǎn)能量低于某一個(gè)規(guī)定的門限值，則在原簇內(nèi)重新選擇簇頭節(jié)點(diǎn)，以簇內(nèi)剩余能量多的節(jié)點(diǎn)為簇頭節(jié)點(diǎn)，這樣產(chǎn)生的簇頭稱為固定簇頭。

　　固定簇頭與簇內(nèi)成員的通信方式和活動(dòng)簇頭一樣。

　　當(dāng)節(jié)點(diǎn)持續(xù)采集監(jiān)測(cè)數(shù)據(jù)時(shí)，在其相應(yīng)時(shí)間片，使用能量傳給簇頭節(jié)點(diǎn)。節(jié)點(diǎn)不發(fā)送數(shù)據(jù)時(shí)，關(guān)閉節(jié)點(diǎn)以節(jié)約能量。簇頭節(jié)點(diǎn)必須保持其接收器一直打開，以接收簇內(nèi)不同節(jié)點(diǎn)的數(shù)據(jù)，然后進(jìn)行數(shù)據(jù)融合。

　　3. 2. 2 簇頭間樹形路由的構(gòu)建與簇間通信

　　假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要n-1條線路。如果用連通網(wǎng)的頂點(diǎn)來表示城市，邊表示兩城市之間的線路，賦予邊的權(quán)值代表相應(yīng)的代價(jià)，需要考慮如何在節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通信網(wǎng)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個(gè)通信網(wǎng)，要選擇一棵生成樹，使總的代價(jià)少，這就是構(gòu)造連通網(wǎng)的代價(jià)生成樹（Minimum Cost Spanning Tree） 問題（簡(jiǎn)稱為生成樹問題）?？紤]將此問題中的城市與無線傳感器網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)相對(duì)應(yīng)，可以在簇頭節(jié)點(diǎn)之間構(gòu)造生成樹，降低簇頭節(jié)點(diǎn)間的通信代價(jià)。

　　prim算法構(gòu)造生成樹的過程：假設(shè)N =（V ,{ E}）為連通網(wǎng)，V表示網(wǎng)中頂點(diǎn)的集合，E表示邊的集合，U是V的一非空子集，TE為生成樹中邊的集合。首先，從集合V中取一個(gè)頂點(diǎn)V0加入集合U中，這時(shí)U={ V 0 }, 集合TE={ },接著重復(fù)執(zhí)行以下操作：從V0出發(fā)，在集合V中尋找與U中頂點(diǎn)相鄰頂點(diǎn)中權(quán)值的邊的另一頂點(diǎn)V1,然后將V1并入U(xiǎn)中，并將該邊加入集合TE中，直到U=V為止。這時(shí)TE中有n-1條邊，T =（U ,TE）為N的生成樹。

　　利用prim算法構(gòu)造生成樹的原理在簇頭間構(gòu)造樹形路由，改進(jìn)過程如下：

　　1） 選出的簇頭節(jié)點(diǎn)將自己的剩余能量和到基站的距離加入到廣播數(shù)據(jù)包中進(jìn)行廣播，根據(jù)其剩余能量和到基站的距離關(guān)系參數(shù)Ped ,選取Ped 的簇頭節(jié)點(diǎn)作為樹根節(jié)點(diǎn)。Ped 的定義公式：

　　其中，i是傳感器節(jié)點(diǎn)編號(hào)，Ey（i）是節(jié)點(diǎn)i 的剩余能量，De（i）是節(jié)點(diǎn)i 到基站的距離。

　　2） 利用prim算法構(gòu)造生成樹原理，樹根節(jié)點(diǎn)選擇下一跳中有效簇頭節(jié)點(diǎn)作為其子節(jié)點(diǎn)，該子節(jié)點(diǎn)以樹根節(jié)點(diǎn)為父節(jié)點(diǎn)，同時(shí)向下一跳簇頭節(jié)點(diǎn)繼續(xù)搜索。若該子節(jié)點(diǎn)搜索成功，則繼續(xù)執(zhí)行路由算法，若沒有搜索到有效簇頭節(jié)點(diǎn)，則返回該根節(jié)點(diǎn)繼續(xù)搜索。

　　3） 重復(fù)2），直到所有節(jié)點(diǎn)加入到樹中，構(gòu)成樹形網(wǎng)絡(luò)路由。

　　簇頭節(jié)點(diǎn)通過樹網(wǎng)絡(luò)路由，以多跳方式通信，作為樹根節(jié)點(diǎn)的簇頭將數(shù)據(jù)傳給基站。簇頭間的樹形路由如圖1所示。

　　4 算法的仿真分析

　　采用Matlab仿真工具，對(duì)LEACH算法、LEACH2EA算法和改進(jìn)的算法進(jìn)行仿真比較。仿真場(chǎng)景假設(shè)有100個(gè)傳感器節(jié)點(diǎn)組成，節(jié)點(diǎn)隨機(jī)分布在一個(gè)介于（x=0 ,y=0） 與（x=100,y=100）的區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)都擁有相同的初始能量E0=0.5J,仿真模型參照文獻(xiàn)。

　　如圖2 所示，前1000 輪中，LEACH和LEACH2EA 算法的節(jié)點(diǎn)存活數(shù)比較接近，改進(jìn)算法相對(duì)來說比前兩種算法更優(yōu)越。

　　網(wǎng)絡(luò)生命周期是衡量網(wǎng)絡(luò)質(zhì)量的一個(gè)重要標(biāo)志，圖3 顯示了當(dāng)節(jié)點(diǎn)死亡率為1%,50%,100%時(shí)所經(jīng)過的輪數(shù)。從圖中可以看出新算法的通信輪數(shù)高于LEACH和LEACH2EA算法，表明改進(jìn)之后得到的新算法降低了能耗，延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。

　　5 結(jié)語

　　LEACH算法是一種經(jīng)典的層次型路由算法，它利用簇頭輪換機(jī)制將能量消耗較均勻地分?jǐn)偟搅苏麄€(gè)網(wǎng)絡(luò)。在LEACH 的基礎(chǔ)上提出了一種改進(jìn)的路由算法，改進(jìn)算法的簇相對(duì)固定，在一定程度上避免了頻繁分簇造成的能量浪費(fèi)，降低了整個(gè)網(wǎng)絡(luò)的能耗。簇頭節(jié)點(diǎn)接收簇中其它節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，并將這些數(shù)據(jù)進(jìn)行融合，通過樹形路由，以多跳方式進(jìn)行通信，降低了簇頭節(jié)點(diǎn)的通信代價(jià)。仿真結(jié)果表明，該算法進(jìn)一步降低了網(wǎng)絡(luò)中的能量消耗，有效延長(zhǎng)了網(wǎng)絡(luò)生命周期。

　　本文在基于網(wǎng)絡(luò)數(shù)據(jù)傳輸可以進(jìn)行數(shù)據(jù)融合的前提下，對(duì)LEACH 算法進(jìn)行了改進(jìn)，但改進(jìn)算法沒有考慮具體的數(shù)據(jù)融合方法。下一步的工作，將在本文算法的基礎(chǔ)上研究如何提高數(shù)據(jù)融合與傳輸?shù)男屎涂煽啃浴?/FONT>