探索能量最優(yōu)化的傳感網(wǎng)絡(luò)路由算法及部署方案

崔宇等

摘 要：傳感器在區(qū)域內(nèi)對(duì)數(shù)據(jù)的采集、傳遞都需要消耗大量的能量，而傳感網(wǎng)絡(luò)的壽命長(zhǎng)短傳感器的能量又取決于傳感器的能量是否耗盡，某項(xiàng)目中，當(dāng)傳感網(wǎng)絡(luò)中20%的傳感器能量耗盡時(shí)，該傳感網(wǎng)絡(luò)就失去作用，根據(jù)傳感器能量消耗公式，在傳感器傳遞數(shù)據(jù)包時(shí)將數(shù)據(jù)傳輸均分到整個(gè)網(wǎng)絡(luò)中便可以將能量的損耗平均到每個(gè)傳感器中，相比較于僅將數(shù)據(jù)包通過(guò)一個(gè)傳感器傳至基站的情況，該方法不僅大大提高了傳遞效率并且大大延長(zhǎng)了傳感網(wǎng)絡(luò)的壽命?；诼酚伤惴ǖ乃枷?，對(duì)于區(qū)域內(nèi)所有傳感器的排布情況，首先考慮對(duì)網(wǎng)絡(luò)進(jìn)行按“跳數(shù)”（數(shù)據(jù)傳遞至基站的傳遞次數(shù)）進(jìn)行劃分，將有相同跳數(shù)的傳感器作為一層；分層后，通過(guò)經(jīng)典的LEACH算法，在每輪中選取出各層中的簇頭進(jìn)行數(shù)據(jù)傳遞，提高了數(shù)據(jù)傳遞的效率，并且在每輪中擔(dān)任簇頭的節(jié)點(diǎn)在下輪中不會(huì)擔(dān)任簇頭，因此也使得能量的損耗均勻到各層的每個(gè)節(jié)點(diǎn)中，不會(huì)出現(xiàn)數(shù)據(jù)集中在某個(gè)節(jié)點(diǎn)的情況，延長(zhǎng)了傳感網(wǎng)絡(luò)的壽命。根據(jù)以往所做的三種（矩形，蜂窩1，蜂窩2）排布情況，文章利用設(shè)計(jì)的算法對(duì)三種情況進(jìn)行仿真，檢驗(yàn)出三種排布方式中較優(yōu)的一種。

關(guān)鍵詞：傳感網(wǎng)絡(luò)部署；能量?jī)?yōu)化；LEACH算法；分層路由算法

中圖分類(lèi)號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8937（2013）17-0005-03

隨著信息技術(shù)的飛速發(fā)展，信息網(wǎng)絡(luò)對(duì)于信息的傳輸顯得日益重要，現(xiàn)今很多研究者針對(duì)于定向傳感器、全向傳感器的覆蓋問(wèn)題已經(jīng)做了大量的研究，但相對(duì)于傳感網(wǎng)絡(luò)能量方面的研究并不是很多，所以現(xiàn)在越來(lái)越多的研究關(guān)注于傳感網(wǎng)絡(luò)的能量問(wèn)題。

在傳感器采集、傳遞數(shù)據(jù)和接收其它傳感器所傳遞的數(shù)據(jù)包時(shí)都對(duì)傳感器的能量有一定的損耗，當(dāng)某傳感器的能量消耗盡時(shí)便無(wú)法采集及傳輸數(shù)據(jù)，某項(xiàng)目中，當(dāng)整個(gè)傳感網(wǎng)絡(luò)中20%的傳感器能量耗盡時(shí)，該片區(qū)域內(nèi)的傳感網(wǎng)絡(luò)便無(wú)法正常工作，可認(rèn)為項(xiàng)目終結(jié)，因此，在合理排布傳感器位置的基礎(chǔ)上，如何延長(zhǎng)傳感網(wǎng)絡(luò)的使用壽命是本文所研究的關(guān)鍵問(wèn)題。

1 假 設(shè)

基站位于左邊界上端，r為通信距離，傳感器相同且有一樣的初始能量，通信信號(hào)穩(wěn)定，按蜂窩式分布。

2 模型、算法及符號(hào)說(shuō)明

2.1 傳感器能量消耗

通過(guò)查閱相關(guān)文獻(xiàn)及資料，傳感器節(jié)點(diǎn)的剩余能量Energy可以表示為：

Energy=e0-e1t-e2m

其中，e0為初始能量，er為單次采集能耗，ep為節(jié)點(diǎn)傳輸能耗，t為時(shí)間，m為數(shù)據(jù)包總數(shù)。

2.2 網(wǎng)絡(luò)壽命

①當(dāng)節(jié)點(diǎn)耗盡能量（Energy變?yōu)樨?fù)數(shù)）后，該節(jié)點(diǎn)無(wú)法繼續(xù)采集或傳輸數(shù)據(jù)。定義項(xiàng)目的生存周期為傳感網(wǎng)絡(luò)從開(kāi)始運(yùn)行到超過(guò)20%節(jié)點(diǎn)耗盡能量所經(jīng)歷的時(shí)間。

②顯然距離基站最近的一層，即第一層，由于轉(zhuǎn)發(fā)數(shù)據(jù)包的數(shù)量是最大的，所以節(jié)點(diǎn)損耗的能量也是最大的一層。若第一層的能量消耗完全的時(shí)候，網(wǎng)絡(luò)就無(wú)法傳輸數(shù)據(jù)包。

2.3 路由算法

路由算法是提高路由協(xié)議功能，盡量減少路由時(shí)所帶來(lái)開(kāi)銷(xiāo)的算法。當(dāng)實(shí)現(xiàn)路由算法的軟件必須運(yùn)行在物理資源有限的計(jì)算機(jī)上時(shí)高效尤其重要。路由器使用路由算法來(lái)找到到達(dá)目的地的最佳路由。當(dāng)說(shuō)“最佳路由”時(shí)，考慮的參數(shù)包括諸如跳躍數(shù)（分組數(shù)據(jù)包在網(wǎng)絡(luò)中從一個(gè)路由器或中間節(jié)點(diǎn)到另外的節(jié)點(diǎn)的行程）、延時(shí)以及分組數(shù)據(jù)包傳輸通信耗時(shí)。

對(duì)于本文來(lái)說(shuō)，在基于某區(qū)域傳感器排布位置已知的情況下，我們考慮對(duì)該片區(qū)域內(nèi)的傳感網(wǎng)絡(luò)進(jìn)行分層然后在層與層之間的數(shù)據(jù)傳遞（能量消耗）方面進(jìn)行優(yōu)化，在提高數(shù)據(jù)傳遞效率的同時(shí)也延長(zhǎng)了傳感網(wǎng)絡(luò)的壽命，算法具體流程如圖1所示。

2.4 LEACH算法及改進(jìn)

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算法在執(zhí)行過(guò)程被分為一個(gè)個(gè)小的輪，而在每輪中又分為建立階段和穩(wěn)定階段。

2.4.1 建立階段

一個(gè)節(jié)點(diǎn)在新的一輪中能否成為簇頭節(jié)點(diǎn)取決于兩個(gè)因素，一是網(wǎng)絡(luò)中假定的簇頭節(jié)點(diǎn)所占的百分比，二是最近1/p輪中是否成為過(guò)簇頭節(jié)點(diǎn)。在新的一輪中，節(jié)點(diǎn)通過(guò)由自身產(chǎn)生的隨機(jī)數(shù)與閾值進(jìn)行比較，小于閾值則成為簇頭節(jié)點(diǎn)：

閾值T（n）為：

節(jié)點(diǎn)在成為簇頭節(jié)點(diǎn)之后，設(shè)置已成為簇頭節(jié)點(diǎn)的標(biāo)志，即設(shè)置自己不屬于最近1/p輪中沒(méi)有當(dāng)選簇頭節(jié)點(diǎn)的節(jié)點(diǎn)集合，則相應(yīng)的閾值T（n）將為0。

簇頭產(chǎn)生后，將自己的信息進(jìn)行廣播，沒(méi)有成為簇頭的節(jié)點(diǎn)根據(jù)收到廣播信號(hào)的強(qiáng)弱可以選擇是否加入該簇頭，簇頭節(jié)點(diǎn)則根據(jù)收到的所有的加入信息，生成一個(gè)為本簇內(nèi)的節(jié)點(diǎn)分配發(fā)送信息的TDMA時(shí)隙信息，為本簇內(nèi)的節(jié)點(diǎn)分配發(fā)送信息的時(shí)隙，并發(fā)送廣播信息給本簇內(nèi)所有節(jié)點(diǎn)。簇頭的選擇隨機(jī)進(jìn)行，所有節(jié)點(diǎn)輪流擔(dān)當(dāng)簇頭，可避免簇頭節(jié)點(diǎn)能耗太大。

2.4.2 穩(wěn)定階段

在該階段中，如圖2所示，簇成員節(jié)點(diǎn)先將感知到信息經(jīng)處理后在自己的TDMA時(shí)隙內(nèi)發(fā)送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)在收到本簇內(nèi)所有節(jié)點(diǎn)發(fā)送過(guò)來(lái)的數(shù)據(jù)之后，對(duì)接收的數(shù)據(jù)進(jìn)行融合和壓縮，并監(jiān)聽(tīng)信道，空閑時(shí)將融合壓縮后的數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。

2.5 改進(jìn)LEACH算法

3 算法仿真及實(shí)驗(yàn)結(jié)果

本文針對(duì)于某一矩形區(qū)域（200×100 m2）內(nèi)三種不同的傳感器位置分布方式對(duì)上述算法進(jìn)行檢驗(yàn)，確定排布方式中網(wǎng)絡(luò)壽命較長(zhǎng)的一個(gè)，矩陣排布如圖3及表1所示，蜂窩排布1如圖4及表2所示，蜂窩排布2如圖5及表3所示。

4 結(jié) 論

通過(guò)對(duì)該算法對(duì)實(shí)際排布中的仿真測(cè)試，可以看出該算法可以將傳感網(wǎng)絡(luò)的能量較平均地分到每一層中，而對(duì)于每一層中的節(jié)點(diǎn)能耗方面，也盡可能的避免單一節(jié)點(diǎn)的能量大量消耗，使得每一層消耗的能量均勻分到每一個(gè)節(jié)點(diǎn)上，從而大大延長(zhǎng)了該傳感網(wǎng)絡(luò)的壽命。但對(duì)于靠近數(shù)據(jù)中心的傳感器的能量消耗依然比較大，因此在實(shí)際應(yīng)用過(guò)程中可以考慮在靠近數(shù)據(jù)中心排布時(shí)增加備用節(jié)點(diǎn)以更好地延長(zhǎng)網(wǎng)絡(luò)壽命。

參考文獻(xiàn)：

[1] 陳光亭，裘哲勇數(shù)學(xué)建模[M].北京：高等教育出版社，2010.

[2] 田鐵紅，程賡，毛松，等.面向環(huán)境保護(hù)的物聯(lián)網(wǎng)發(fā)展探討[J].信息通信技術(shù)，2010，（5）.

[3] 楊云，田浩澄，顧沈君，等.無(wú)線傳感器網(wǎng)絡(luò)分層聚類(lèi)路由算法[J].計(jì)算機(jī)研究與發(fā)展，2011，（S2）.