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

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

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

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

???
其中：p是網(wǎng)絡中簇頭節(jié)點占總節(jié)點數(shù)的百分比；r是已完成輪數(shù)；G是在前1／p輪中沒有充當過簇頭節(jié)點的節(jié)點集合。舉例來說，第1輪(r=0)，每個節(jié)點成為簇頭的概率都是p，第1輪的簇頭在包括此輪之后的1／p輪中都不再充當簇頭節(jié)點(即第1～20輪)。此后，由于能夠充當簇頭節(jié)點的節(jié)點數(shù)目變少了，因此每個節(jié)點成為簇頭的概率就必須增加以保證每輪簇頭數(shù)。1／p一1輪過后，沒當過簇頭的節(jié)點充當簇頭的概率都是1，都能夠成為簇頭節(jié)點。1／p輪后，所有節(jié)點又都可以自主隨機決定是否充當簇頭節(jié)點。在文獻中，作者論證了最優(yōu)簇頭節(jié)點百分比為p=5％。

一旦簇頭選定后，簇頭節(jié)點會利用CSMA MAC協(xié)議對全網(wǎng)所有節(jié)點發(fā)送廣播數(shù)據(jù)包，其中包含該節(jié)點成為簇頭的信息。根據(jù)網(wǎng)絡的對稱性原則，其他節(jié)點選擇接收到信號最強的簇頭加入，至此簇建立階段完成。
??? 在穩(wěn)定運行階段，普通節(jié)點利用CSMA MAC協(xié)議向其簇頭發(fā)送加入數(shù)據(jù)包。簇頭節(jié)點收到加入數(shù)據(jù)包后，會產(chǎn)生一個TDMA時刻表，為簇內所有節(jié)點分配發(fā)送時隙，并將此時刻表向各成員廣播。此后，簇頭節(jié)點即開始接收各成員采集到的數(shù)據(jù)，并將其融合后發(fā)送到基站。簇頭節(jié)點在此階段保持接收機始終處于開機狀態(tài)以便接收數(shù)據(jù)，而普通節(jié)點只有在自己發(fā)送時打開發(fā)射機，其余時刻關閉發(fā)射機以節(jié)約能量。
??? 相比于平面路由算法，LEACH算法明顯減少了能量消耗，并且將能量耗散分攤到整個網(wǎng)絡，有效延長了網(wǎng)絡生存時間。在文獻中，作者的仿真表明LEACH比平面型的Direct communication協(xié)議網(wǎng)絡生存時間提高了約6倍，比層次型固定簇頭協(xié)議StaticClusters網(wǎng)絡生存時間提高了約10倍。
??? 然而，完全自主隨機的簇頭選擇不能保證每輪簇頭節(jié)點的數(shù)目和分布，存在距離基站較遠且能量較少的節(jié)點擔當簇頭的可能性，造成網(wǎng)絡內節(jié)點能量損耗不均，節(jié)點的生存期散布較大，到網(wǎng)絡生存期后期會形成監(jiān)控盲點，影響了網(wǎng)絡的整體性能。為了改善這種情況，本文提出了基于距離和能量選擇第二層簇頭的兩層LEACH算法DE—LEACH。

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

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

另外，考慮到傳感器節(jié)點所采集的數(shù)據(jù)在較短時間內具有相關性，可以采用事件驅動的方式進一步延長網(wǎng)絡生存期。下面將對DE—LEACH與LEACH進行性能上的比較，并仿真分析了加人事件驅動因素后DE—LEACH的生存期改善程度。

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

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

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

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

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

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