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

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

0 引 言
微電子技術(shù)、計算機(jī)技術(shù)和無線通信等技術(shù)的不斷發(fā)展，使設(shè)計低功耗多功能的無線傳感器成為可能。無線傳感器網(wǎng)絡(luò)在監(jiān)測區(qū)域內(nèi)部署大量的廉價低功耗傳感器節(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)用價值。
作為無線傳感器網(wǎng)絡(luò)核心技術(shù)之一，路由協(xié)議的性能在很大程度上決定了網(wǎng)絡(luò)的整體性能，因此，路由算法始終是無線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)。根據(jù)各個節(jié)點(diǎn)在網(wǎng)絡(luò)中功能的異同，可將路由算法分為平面型和層次型路由。由于平面型路由可擴(kuò)展性差，且維護(hù)動態(tài)變化的路由需要大量的控制信息，若部署在人類到達(dá)比較困難的地區(qū)，維護(hù)相對困難。層次型路由算法克服了以上不足，可擴(kuò)充性好，網(wǎng)絡(luò)中控制信息相對較少，得到了廣泛的應(yīng)用。LEACH是第一個基于多簇結(jié)構(gòu)的層次型路由協(xié)議，其成簇思想在其后很多協(xié)議中都被用到，如TEEN等。
在LEACH算法中，各節(jié)點(diǎn)根據(jù)簇頭概率p自主決定在該輪是否充當(dāng)簇頭，一旦成為簇頭便通過廣播告知整個網(wǎng)絡(luò)，由于簇頭選擇是完全自主和隨機(jī)的，不需要節(jié)點(diǎn)間通信協(xié)調(diào)，因此LEACH算法具有節(jié)約能量、實現(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)死亡時間，縮短了首節(jié)點(diǎn)死亡到末節(jié)點(diǎn)死亡的時間間隔，同時網(wǎng)絡(luò)總的數(shù)據(jù)采集能力得到明顯提高。

1 LEACH算法簡介
LEACH算法引入了輪的概念，每輪簇頭節(jié)點(diǎn)進(jìn)行輪換，以達(dá)到分散各節(jié)點(diǎn)能量消耗的目的。每一輪包括簇建立和穩(wěn)定運(yùn)行兩個階段。為減少管理消耗，穩(wěn)定運(yùn)行階段時間要長于簇建立階段。
在簇建立階段，每個節(jié)點(diǎn)自主決定是否在本輪充當(dāng)簇頭，具體的選舉辦法是：由各節(jié)點(diǎn)自主生成0～1之間的隨機(jī)數(shù)，若此隨機(jī)數(shù)小于某門限T(n)，則此節(jié)點(diǎn)在本輪充當(dāng)簇頭。這種簇頭產(chǎn)生的隨機(jī)性保證了簇頭與基站之間較高的通信代價在網(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)，每個節(jié)點(diǎn)成為簇頭的概率都是p，第1輪的簇頭在包括此輪之后的1／p輪中都不再充當(dāng)簇頭節(jié)點(diǎn)(即第1～20輪)。此后，由于能夠充當(dāng)簇頭節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)目變少了，因此每個節(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％。