一種基于LEACH的改進(jìn)型無線傳感器網(wǎng)絡(luò)路由算法

摘要：路由算法是無線傳感器網(wǎng)絡(luò)研究的核心技術(shù)之一。在LEACH算法的基礎(chǔ)上，提出了一種基于距離和能量考慮選擇第二層簇頭的兩層LEACH算法DE—LEACH，有效避免了低能量且離基站較遠(yuǎn)的節(jié)點(diǎn)與基站直接通信，提高了網(wǎng)絡(luò)生存時(shí)間和數(shù)據(jù)采集能力。利用事件驅(qū)動的方法，減少了發(fā)送數(shù)據(jù)量，進(jìn)一步延長了網(wǎng)絡(luò)生存期。
關(guān)鍵詞：路由算法；第二層簇頭選擇；網(wǎng)絡(luò)生存時(shí)間；數(shù)據(jù)采集能力；數(shù)據(jù)融合；事件驅(qū)動

0 引 言
    微電子技術(shù)、計(jì)算機(jī)技術(shù)和無線通信等技術(shù)的不斷發(fā)展，使設(shè)計(jì)低功耗多功能的無線傳感器成為可能。無線傳感器網(wǎng)絡(luò)在監(jiān)測區(qū)域內(nèi)部署大量的廉價(jià)低功耗傳感器節(jié)點(diǎn)，其目的是協(xié)作的感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對象的信息，并以無線通信的方式通過多跳自組織網(wǎng)絡(luò)發(fā)送給遠(yuǎn)程基站(BS)。無線傳感器網(wǎng)絡(luò)是未來全球的三大高科技產(chǎn)業(yè)之一，具有廣闊的應(yīng)用前景，在軍事國防、災(zāi)害預(yù)警、環(huán)境監(jiān)測、醫(yī)療等許多領(lǐng)域都有巨大的應(yīng)用價(jià)值。
    作為無線傳感器網(wǎng)絡(luò)核心技術(shù)之一，路由協(xié)議的性能在很大程度上決定了網(wǎng)絡(luò)的整體性能，因此，路由算法始終是無線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)。根據(jù)各個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中功能的異同，可將路由算法分為平面型和層次型路由。由于平面型路由可擴(kuò)展性差，且維護(hù)動態(tài)變化的路由需要大量的控制信息，若部署在人類到達(dá)比較困難的地區(qū)，維護(hù)相對困難。層次型路由算法克服了以上不足，可擴(kuò)充性好，網(wǎng)絡(luò)中控制信息相對較少，得到了廣泛的應(yīng)用。LEACH是第一個(gè)基于多簇結(jié)構(gòu)的層次型路由協(xié)議，其成簇思想在其后很多協(xié)議中都被用到，如TEEN等。
    在LEACH算法中，各節(jié)點(diǎn)根據(jù)簇頭概率p自主決定在該輪是否充當(dāng)簇頭，一旦成為簇頭便通過廣播告知整個(gè)網(wǎng)絡(luò)，由于簇頭選擇是完全自主和隨機(jī)的，不需要節(jié)點(diǎn)間通信協(xié)調(diào)，因此LEACH算法具有節(jié)約能量、實(shí)現(xiàn)簡單、可擴(kuò)展性好等特點(diǎn)，便于部署于人們難以到達(dá)區(qū)域。但是，隨機(jī)簇頭選擇不能保證每輪簇頭節(jié)點(diǎn)的數(shù)目和分布，易造成網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)能量損耗不均，節(jié)點(diǎn)生存期散布較大，到網(wǎng)絡(luò)生存期后期會形成監(jiān)控盲點(diǎn)，影響了網(wǎng)絡(luò)的整體性能。
    本文在LEACH的基礎(chǔ)上提出了一種兩層簇頭算法DE—LEACH(Distance—Energy LEACH)，第一層簇頭選舉機(jī)制與LEACH相同，之后從已選出的簇頭中根據(jù)剩余能量大小和距離基站(BS)的遠(yuǎn)近折衷考慮選出第二層簇頭。第一層簇頭采集到的數(shù)據(jù)經(jīng)過融合處理后發(fā)送到第二層簇頭，再由第二層簇頭完成二次融合和將監(jiān)測數(shù)據(jù)轉(zhuǎn)發(fā)到基站的工作。由于第二層簇頭選舉機(jī)制綜合考慮了節(jié)點(diǎn)剩余能量和其到基站的距離，因此避免了剩余能量較少且距基站較遠(yuǎn)的第一層簇頭與基站間的直接通信。仿真結(jié)果表明，DE—LEACH延長了網(wǎng)絡(luò)首節(jié)點(diǎn)死亡時(shí)間，縮短了首節(jié)點(diǎn)死亡到末節(jié)點(diǎn)死亡的時(shí)間間隔，同時(shí)網(wǎng)絡(luò)總的數(shù)據(jù)采集能力得到明顯提高。

1 LEACH算法簡介
    LEACH算法引入了輪的概念，每輪簇頭節(jié)點(diǎn)進(jìn)行輪換，以達(dá)到分散各節(jié)點(diǎn)能量消耗的目的。每一輪包括簇建立和穩(wěn)定運(yùn)行兩個(gè)階段。為減少管理消耗，穩(wěn)定運(yùn)行階段時(shí)間要長于簇建立階段。
    在簇建立階段，每個(gè)節(jié)點(diǎn)自主決定是否在本輪充當(dāng)簇頭，具體的選舉辦法是：由各節(jié)點(diǎn)自主生成0～1之間的隨機(jī)數(shù)，若此隨機(jī)數(shù)小于某門限T(n)，則此節(jié)點(diǎn)在本輪充當(dāng)簇頭。這種簇頭產(chǎn)生的隨機(jī)性保證了簇頭與基站之間較高的通信代價(jià)在網(wǎng)內(nèi)各節(jié)點(diǎn)之間得到分?jǐn)偂?br />    門限T(n)定義為：

   
其中：p是網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的百分比；r是已完成輪數(shù)；G是在前1／p輪中沒有充當(dāng)過簇頭節(jié)點(diǎn)的節(jié)點(diǎn)集合。舉例來說，第1輪(r=0)，每個(gè)節(jié)點(diǎn)成為簇頭的概率都是p，第1輪的簇頭在包括此輪之后的1／p輪中都不再充當(dāng)簇頭節(jié)點(diǎn)(即第1～20輪)。此后，由于能夠充當(dāng)簇頭節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)目變少了，因此每個(gè)節(jié)點(diǎn)成為簇頭的概率就必須增加以保證每輪簇頭數(shù)。1／p一1輪過后，沒當(dāng)過簇頭的節(jié)點(diǎn)充當(dāng)簇頭的概率都是1，都能夠成為簇頭節(jié)點(diǎn)。1／p輪后，所有節(jié)點(diǎn)又都可以自主隨機(jī)決定是否充當(dāng)簇頭節(jié)點(diǎn)。在文獻(xiàn)中，作者論證了最優(yōu)簇頭節(jié)點(diǎn)百分比為p=5％。
    一旦簇頭選定后，簇頭節(jié)點(diǎn)會利用CSMA MAC協(xié)議對全網(wǎng)所有節(jié)點(diǎn)發(fā)送廣播數(shù)據(jù)包，其中包含該節(jié)點(diǎn)成為簇頭的信息。根據(jù)網(wǎng)絡(luò)的對稱性原則，其他節(jié)點(diǎn)選擇接收到信號最強(qiáng)的簇頭加入，至此簇建立階段完成。
    在穩(wěn)定運(yùn)行階段，普通節(jié)點(diǎn)利用CSMA MAC協(xié)議向其簇頭發(fā)送加入數(shù)據(jù)包。簇頭節(jié)點(diǎn)收到加入數(shù)據(jù)包后，會產(chǎn)生一個(gè)TDMA時(shí)刻表，為簇內(nèi)所有節(jié)點(diǎn)分配發(fā)送時(shí)隙，并將此時(shí)刻表向各成員廣播。此后，簇頭節(jié)點(diǎn)即開始接收各成員采集到的數(shù)據(jù)，并將其融合后發(fā)送到基站。簇頭節(jié)點(diǎn)在此階段保持接收機(jī)始終處于開機(jī)狀態(tài)以便接收數(shù)據(jù)，而普通節(jié)點(diǎn)只有在自己發(fā)送時(shí)打開發(fā)射機(jī)，其余時(shí)刻關(guān)閉發(fā)射機(jī)以節(jié)約能量。
    相比于平面路由算法，LEACH算法明顯減少了能量消耗，并且將能量耗散分?jǐn)偟秸麄€(gè)網(wǎng)絡(luò)，有效延長了網(wǎng)絡(luò)生存時(shí)間。在文獻(xiàn)中，作者的仿真表明LEACH比平面型的Direct communication協(xié)議網(wǎng)絡(luò)生存時(shí)間提高了約6倍，比層次型固定簇頭協(xié)議StaticClusters網(wǎng)絡(luò)生存時(shí)間提高了約10倍。
    然而，完全自主隨機(jī)的簇頭選擇不能保證每輪簇頭節(jié)點(diǎn)的數(shù)目和分布，存在距離基站較遠(yuǎn)且能量較少的節(jié)點(diǎn)擔(dān)當(dāng)簇頭的可能性，造成網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)能量損耗不均，節(jié)點(diǎn)的生存期散布較大，到網(wǎng)絡(luò)生存期后期會形成監(jiān)控盲點(diǎn)，影響了網(wǎng)絡(luò)的整體性能。為了改善這種情況，本文提出了基于距離和能量選擇第二層簇頭的兩層LEACH算法DE—LEACH。

2 基于距離能量選擇的兩層LEACH算法DE—LEACH
    DE—LEACH算法與LEACH算法一樣，分為簇建立階段與穩(wěn)定運(yùn)行階段。
    在簇建立階段，首先，各節(jié)點(diǎn)仍然利用自身產(chǎn)生的隨機(jī)數(shù)自主決定是否成為簇頭并通知網(wǎng)絡(luò)中所有節(jié)點(diǎn)，在此不再贅述。不同之處在于，選出的簇頭節(jié)點(diǎn)將自己的剩余能量和到基站的距離加入到廣播數(shù)據(jù)包中進(jìn)行廣播。之后，在已選出的第一層簇頭中根據(jù)其剩余能量和到基站的距離關(guān)系參數(shù)Th選出第二層簇頭。
    Th定義為：

   
其中i是網(wǎng)絡(luò)中節(jié)點(diǎn)編號，En(i)是i節(jié)點(diǎn)剩余能量，Dist(i)是i節(jié)點(diǎn)到基站的距離。
    具體的選舉第二層簇頭的策略為：簇頭j將自己的Th(i)值與接收、計(jì)算出到的其他簇頭Th值進(jìn)行比較，若自己最大，則成為第二層簇頭；若比較中發(fā)現(xiàn)簇頭i節(jié)點(diǎn)的Th(i)值最大，則認(rèn)為i是第二層簇頭。這里需要注意的是：
    (1)第二層簇頭同時(shí)也完成第一層簇頭的廣播、分配時(shí)隙、采集數(shù)據(jù)和融合的工作；
    (2)各個(gè)簇頭節(jié)點(diǎn)在計(jì)算Th值并比較過后，已經(jīng)能夠確認(rèn)哪個(gè)第一層簇頭節(jié)點(diǎn)同時(shí)承擔(dān)第二層簇頭節(jié)點(diǎn)職能，因此第二層簇頭節(jié)點(diǎn)不需要再就自己身份進(jìn)行廣播；又由于各簇頭節(jié)點(diǎn)已經(jīng)收到其他簇頭節(jié)點(diǎn)編號，可按編號順序進(jìn)行數(shù)據(jù)傳遞，因此第二層簇頭節(jié)點(diǎn)不需要為第一層簇頭節(jié)點(diǎn)分配時(shí)隙而進(jìn)行廣播；這樣就省去了廣播開銷；
    (3)各個(gè)普通節(jié)點(diǎn)無需知道誰是第二層簇頭，他們只與第一層簇頭通信，而第二層簇頭同時(shí)也承擔(dān)第一層簇頭的功能。
    在穩(wěn)定運(yùn)行階段，普通節(jié)點(diǎn)與第一層簇頭通信方式與LEACH相同。但數(shù)據(jù)采集、融合工作完成之后不是將數(shù)據(jù)包直接發(fā)送到基站，而是依據(jù)簇頭節(jié)點(diǎn)編號順序分時(shí)隙由第一層簇頭發(fā)送到第二層簇頭節(jié)點(diǎn)。再由第二層簇頭節(jié)點(diǎn)進(jìn)行二次融合后，發(fā)送至基站。
    LEACH算法假設(shè)基站離監(jiān)控區(qū)域較遠(yuǎn)，若第一層簇頭節(jié)點(diǎn)均與基站直接通信，則通信能量消耗較大，且易造成網(wǎng)絡(luò)中各節(jié)點(diǎn)剩余能量差距較大的情況，使首末節(jié)點(diǎn)死亡時(shí)間間隔較長，產(chǎn)生監(jiān)控盲點(diǎn)。而DE—LEACH算法能夠有效推遲首節(jié)點(diǎn)死亡時(shí)間，縮小首末節(jié)點(diǎn)死亡時(shí)間間隔，使監(jiān)控盲點(diǎn)出現(xiàn)時(shí)間明顯縮短。這樣，在所有節(jié)點(diǎn)集中死亡后再進(jìn)行拋撒，無疑在經(jīng)濟(jì)上和控制上都將更加高效。
    另外，考慮到傳感器節(jié)點(diǎn)所采集的數(shù)據(jù)在較短時(shí)間內(nèi)具有相關(guān)性，可以采用事件驅(qū)動的方式進(jìn)一步延長網(wǎng)絡(luò)生存期。下面將對DE—LEACH與LEACH進(jìn)行性能上的比較，并仿真分析了加人事件驅(qū)動因素后DE—LEACH的生存期改善程度。

3 仿真分析
3．1 DE—LEACH與LEACH性能比較
    利用Matlab工具對LEACH算法和DE—LEACH算法進(jìn)行仿真比較，主要比較：
    (1)存活節(jié)點(diǎn)數(shù)隨輪次變化曲線；
    (2)數(shù)據(jù)采集總比特?cái)?shù)(二次融合前)隨輪次變化曲線。
    仿真中，假設(shè)無線傳感器網(wǎng)絡(luò)由100個(gè)相同的無線傳感器節(jié)點(diǎn)組成，隨機(jī)拋撒在100 m×100 m的區(qū)域內(nèi)，遠(yuǎn)程基站位于坐標(biāo)點(diǎn)(x=0，y=一100)。每個(gè)節(jié)點(diǎn)初始能量為O．5 J，發(fā)送和接收電路損耗為Elec=50 nJ／b，數(shù)據(jù)融合消耗為Eda=5 nJ／b。放大系數(shù)為Efs=10 pJ／b／m2(d<d0)，Emp=O．001 3 pJ／b／m4(d>d0)，其中數(shù)據(jù)包長度為2 000 b，廣播包長度
為200 b，總帶寬為1 MHz。為簡化仿真復(fù)雜度，監(jiān)測區(qū)域內(nèi)通信按自由空間模型取Efs=10 pJ／b／m2，而簇頭節(jié)點(diǎn)與基站通信由于距離較遠(yuǎn)(>100 m)，按多徑傳播模型取Emp=O.001 3 pJ／b／m4。
    根據(jù)第二層簇頭對收到的第一層簇頭數(shù)據(jù)進(jìn)行二次融合的融合率不同，這里分完全不融合、50％融合、完全融合分別進(jìn)行了仿真比較。
    完全不融合，即將第一層簇頭發(fā)送來的數(shù)據(jù)包不加處理地組成一個(gè)長數(shù)據(jù)包發(fā)送到基站，這時(shí)第二層簇頭相當(dāng)于只是完成了數(shù)據(jù)接收和轉(zhuǎn)發(fā)的功能。仿真發(fā)現(xiàn)，即使在完全不融合的情況下，DE—LEACH的首節(jié)點(diǎn)死亡時(shí)間也要比LEACH晚30％，50％節(jié)點(diǎn)死亡時(shí)間晚15％(如圖1)。數(shù)據(jù)采集總比特?cái)?shù)DE—LEACH比LEACH高出12％(如圖2)。雖然末節(jié)點(diǎn)死亡時(shí)間早于LEACH，但網(wǎng)絡(luò)中存活期非常集中，網(wǎng)絡(luò)出現(xiàn)大面積監(jiān)控盲區(qū)的時(shí)間短，若要保證數(shù)據(jù)采集的持續(xù)性和完整性，對監(jiān)控區(qū)域重新部署節(jié)點(diǎn)將比LEACH算法更經(jīng)濟(jì)有效。

    50％融合，即將第一層簇頭發(fā)送來的數(shù)據(jù)包壓縮一半之后發(fā)送到基站。各個(gè)第一層簇頭發(fā)送的數(shù)據(jù)包中仍然含有第一層簇頭數(shù)據(jù)包的包頭等基站不需要的冗余信息，可以進(jìn)行進(jìn)一步融合。仿真發(fā)現(xiàn)，進(jìn)行50％融合后，DE—LEACH的首節(jié)點(diǎn)死亡時(shí)間比LEACH晚40％，50％節(jié)點(diǎn)死亡時(shí)間晚25％(如圖3)。數(shù)據(jù)采集總比特?cái)?shù)DE—LEACH比LEACH高出22％(如圖4)。

    完全融合，即將第一層簇頭發(fā)送來的數(shù)據(jù)包壓縮成一個(gè)2 000 b的數(shù)據(jù)包發(fā)送到基站。由于融合率較大，不僅要用到數(shù)據(jù)級融合，特征級融合，還要用到?jīng)Q策級融合。即最后傳輸?shù)交镜囊巡皇呛唵蔚臄?shù)據(jù)，而是第二層簇頭節(jié)點(diǎn)對采集到的數(shù)據(jù)進(jìn)行綜合分析后所得到的結(jié)果。仿真發(fā)現(xiàn)，完全融合后，DE—LEACH的首節(jié)點(diǎn)死亡時(shí)間比LEACH晚40％，50％節(jié)點(diǎn)死亡時(shí)間晚30％(如圖5)。數(shù)據(jù)采集總比特?cái)?shù)DE—LEACH比LEACH高出28％(如圖6)。
    由仿真比較可見，綜合考慮了簇頭節(jié)點(diǎn)到基站的距離以及剩余能量并據(jù)此選出第二層簇頭的DE—LEACH算法，性能較LEACH有明顯的改善。
    DE—LEAcH算法的優(yōu)點(diǎn)：延長了首節(jié)點(diǎn)死亡時(shí)間，曲線斜率明顯比LEACH大，縮短了首末節(jié)點(diǎn)死亡時(shí)間間隔，相比于LEACH，節(jié)點(diǎn)死亡時(shí)間更加集中，監(jiān)控盲點(diǎn)出現(xiàn)時(shí)間短，重新部署傳感器節(jié)點(diǎn)更加經(jīng)濟(jì)高效；數(shù)據(jù)采集總量明顯提高。DE—LEACH算法的不足：由于在原來LEACH算法的簇頭與基站之間又增加了一跳路由，網(wǎng)絡(luò)延遲有所增加。另外，節(jié)點(diǎn)的運(yùn)算能力要有所提高。就仿真來看，要想得到更長的網(wǎng)絡(luò)生存時(shí)間和更高的數(shù)據(jù)采集量，就要加大數(shù)據(jù)融合率，這對節(jié)點(diǎn)的數(shù)據(jù)融合能力提出了更高的要求。在實(shí)際應(yīng)用中，需要根據(jù)應(yīng)用對性能和成本的要求進(jìn)行綜合考慮。

3．2 事件驅(qū)動型DE—LEACH生存期分析
    針對傳感器節(jié)點(diǎn)所采集的數(shù)據(jù)(如溫度、壓力等)在較短時(shí)間內(nèi)的相關(guān)性，可設(shè)定一個(gè)門限值，當(dāng)相鄰兩次所采集數(shù)據(jù)變化超過此門限值時(shí)，節(jié)點(diǎn)才向簇頭發(fā)送數(shù)據(jù)，并保留后一次數(shù)據(jù)在該節(jié)點(diǎn)存儲器中；若變化小于門限值，則不進(jìn)行發(fā)送，仍保留前一次數(shù)據(jù)以防止數(shù)據(jù)以漸進(jìn)的方式變化。門限值可設(shè)定為前次采集數(shù)據(jù)的百分比或具體的數(shù)值，視具體情況而定。圖7的仿真設(shè)定門限值為前次采集數(shù)據(jù)的10％(完全不融合情況)。

    由圖7可見加入事件驅(qū)動因素后，網(wǎng)絡(luò)生存期延長約9％，仿真中為方便采集數(shù)據(jù)用隨機(jī)數(shù)的方式產(chǎn)生，不具有相關(guān)性。當(dāng)實(shí)際應(yīng)用中的數(shù)據(jù)具有相關(guān)性時(shí)，生存期延長將更加明顯。另外，門限值的大小可根據(jù)需要更改，適應(yīng)性較強(qiáng)。加入事件驅(qū)動的缺點(diǎn)：由于需要存儲兩次采集的數(shù)據(jù)進(jìn)行比較，提高了對傳感器節(jié)點(diǎn)存儲能力的要求。

4 結(jié) 語
    路由協(xié)議在很大程度上決定了網(wǎng)絡(luò)的整體性能。因此，作為無線傳感器網(wǎng)絡(luò)核心技術(shù)之一，路由協(xié)議一直是研究的熱點(diǎn)。LEACH算法是一種經(jīng)典的層次型路由協(xié)議，它利用簇頭輪換機(jī)制有效的將能量消耗較均勻地分?jǐn)偟秸麄€(gè)網(wǎng)絡(luò)。在LEACH算法的基礎(chǔ)上提出了一種基于距離和能量選擇第二層簇頭的兩層改進(jìn)型LEACH算法DE—LEACH，并簡要分析了事件驅(qū)動對網(wǎng)絡(luò)生存期的影響。仿真結(jié)果表明，該算法進(jìn)一步平均了網(wǎng)絡(luò)中的能量消耗，有效延長了網(wǎng)絡(luò)生存時(shí)間，提高了網(wǎng)絡(luò)的數(shù)據(jù)采集能力。
    LEACH算法的實(shí)現(xiàn)作了一些假設(shè)。其中一點(diǎn)是網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)當(dāng)選簇頭后都進(jìn)行全網(wǎng)廣播，這樣的假設(shè)在網(wǎng)絡(luò)覆蓋范圍較大的情況下?lián)p耗將明顯加大，因此在大規(guī)模應(yīng)用中多層多跳路由成為必然的選擇。這也將是今后工作繼續(xù)探討的方向之一。