改進(jìn)無線傳感器網(wǎng)絡(luò)路由算法

張曉偉

泰山職業(yè)技術(shù)學(xué)院 山東 泰安 271000

0 引言

無線傳感技術(shù)在信息化的社會得到飛速發(fā)展和應(yīng)用，無線傳感器網(wǎng)絡(luò)簡稱WSN（wireless sensor networks），其特征由傳感器節(jié)點組成，眾多節(jié)點組織成網(wǎng)絡(luò)系統(tǒng)，通過無線網(wǎng)絡(luò)間信息的處理并傳遞給用戶。在農(nóng)業(yè)、航天、交通、物業(yè)管理、地質(zhì)災(zāi)害等諸多方面得到廣泛應(yīng)用。大多傳感器節(jié)點的能量通過外在能源（電池）提供，在進(jìn)行無線傳感器網(wǎng)絡(luò)路由設(shè)計過程中，要考慮降低節(jié)點的能量損耗，延長節(jié)點的使用壽命。

無線傳感器網(wǎng)絡(luò)的特點是節(jié)點數(shù)目大，節(jié)點能量有限，節(jié)點失效概率高。無線傳感器網(wǎng)絡(luò)與傳統(tǒng)無線網(wǎng)絡(luò)的路由算法相比，需要進(jìn)行改進(jìn)。從無線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)角度考慮，無線傳感器網(wǎng)絡(luò)的路由算法分為：平面路由算法、分簇路由算法。在平面路由算法中，傳感器各節(jié)點地位平等，結(jié)構(gòu)簡單、容易擴(kuò)展，通過信息反饋和相應(yīng)操作生成網(wǎng)絡(luò)路由，維持路由表需要占用大量的存儲空間，路由信息發(fā)送時會增加通信負(fù)擔(dān)，通信資源的優(yōu)化管理欠缺，因此平面路由算法不適合大規(guī)模傳感器網(wǎng)絡(luò)。分簇路由算法彌補(bǔ)了平面路由算法的缺陷，一是可擴(kuò)展性好，二是網(wǎng)絡(luò)中控制信息相對較少。該算法是無線傳感器網(wǎng)絡(luò)中應(yīng)用最為廣泛的路由算法。其基本思想是：整個無線傳感器網(wǎng)絡(luò)劃分為多個小的區(qū)域，小區(qū)域稱為簇（cluster）。簇內(nèi)所有眾多節(jié)點中只能產(chǎn)生一個簇首節(jié)點，這個簇首節(jié)點就是負(fù)責(zé)本簇內(nèi)信息收集、融合及簇間數(shù)據(jù)的轉(zhuǎn)發(fā)。其余節(jié)點稱為普通節(jié)點，負(fù)責(zé)數(shù)據(jù)的采集和發(fā)送。

無線傳感器網(wǎng)絡(luò)中基于分簇的路由算法之一是低功耗自適應(yīng)分簇路由算法 （low-energy adaptive clustering hierarchy，LEACH）， LEACH算法存在一些不足，主要表現(xiàn)兩點：一是無線傳感器節(jié)點數(shù)巨大，由于采用隨機(jī)部署方式，造成本簇內(nèi)節(jié)點分布不均而導(dǎo)致簇首節(jié)點負(fù)載的不均衡；二是簇首節(jié)點能量損耗大，主要是因為簇首節(jié)點距離基站較遠(yuǎn)，在與基站進(jìn)行通信時損耗能量，從而形成盲節(jié)點，會使網(wǎng)絡(luò)生存時間壽命縮短。對于LEACH算法存在的不足，提出一種改進(jìn)的無線傳感路由算法。本算法對LEACH算法的簇首節(jié)點隨機(jī)選擇進(jìn)行改進(jìn)，在通信機(jī)制中考慮簇首節(jié)點的位置，采用單跳（single－h(huán)op）和多跳（multi－h(huán)op）相互結(jié)合的通信方式提高算法的有效性和優(yōu)越性。

1 LEACH算法的工作原理

1.1 LEACH算法的工作進(jìn)程

LEACH算法是一種低功耗自適應(yīng)無線傳感器路由算法，該算法是指：通過等概率、周期性的方式選擇簇首節(jié)點，簇內(nèi)的普通節(jié)點是通過“就近原則”進(jìn)行劃分確定的，形成虛擬簇；簇首節(jié)點對簇內(nèi)節(jié)點感知的信息進(jìn)行數(shù)據(jù)融合，將融合好評的數(shù)據(jù)再以單跳的通信方式轉(zhuǎn)發(fā)給Sink（基站節(jié)點），其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 LEACH算法的拓?fù)浣Y(jié)構(gòu)

在LEACH算法中包括簇建立階段和穩(wěn)定工作階段，穩(wěn)定工作階段持續(xù)時間相對簇建立階段要長。

第一階段是簇建立，簇的建立首先選擇建立簇首，在LEACH算法中隨機(jī)循環(huán)方式選擇簇首，因此在每一輪簇建立階段，各個節(jié)點都要判斷自己是否可以成為簇首。具體的過程是：每一個節(jié)點隨機(jī)生成0～1之間的隨機(jī)數(shù)，如果得到的隨機(jī)數(shù)小于規(guī)定的一個閥值T（i），那么該節(jié)點就成為簇首節(jié)點。

其中，n表示進(jìn)行的選舉輪數(shù)，p表示本輪中簇首節(jié)點在全部網(wǎng)絡(luò)節(jié)點中所占百分比數(shù)，G表示余下1/p輪循環(huán)中沒有成為簇首節(jié)點的節(jié)點集合。

選出簇首節(jié)點成功后，通過廣播通知整個網(wǎng)絡(luò)簇首節(jié)點的相關(guān)信息，網(wǎng)絡(luò)中的普通節(jié)點根據(jù)收到的信息及信號強(qiáng)度決定要加入哪一個簇，向簇首發(fā)出加入簇的請求信息，至此完成簇的確定過程。

第二階段是簇的穩(wěn)定工作階段，進(jìn)入穩(wěn)定工作階段過程，普通節(jié)點在屬于自己時間間隙的時刻利用CSMA MAC協(xié)議向本簇首發(fā)送數(shù)據(jù)，其余時間進(jìn)入休眠狀態(tài)，關(guān)閉發(fā)送，以節(jié)約能量。簇首節(jié)點接收本簇成員節(jié)點的數(shù)據(jù)信息后，進(jìn)行融合后發(fā)送到基站。經(jīng)過這個穩(wěn)定工作階段時間后，再進(jìn)入新一輪的循環(huán)。

2.2 LEACH算法不足

LEACH算法是通過隨機(jī)選擇簇首，使全部所有節(jié)點公平地分擔(dān)能量的消耗，通過融合機(jī)制減少數(shù)據(jù)傳輸過程的數(shù)據(jù)包的大小，節(jié)約能耗，延長了整個無線傳感器網(wǎng)絡(luò)的生存周期，但仍存在許多不足。

隨機(jī)選擇簇首時沒有考慮節(jié)點剩余能量的多少，會產(chǎn)生當(dāng)前剩余能量較小的節(jié)點承擔(dān)簇首的工作，這樣的簇首節(jié)點生存周期短而成為盲節(jié)點。同時在選擇簇首過程中忽略了節(jié)點位置信息，在每一輪選擇簇首節(jié)點時就不能保證選出的簇首都是最合適的，如果簇首位置處于邊緣位置時，與基站節(jié)點距離增加，會增大能量的耗損，壽命很短。盲節(jié)點出現(xiàn)的頻率大就會降低網(wǎng)絡(luò)平均壽命，導(dǎo)致算法效率低下。

LEACH算法中能量消耗與距離有直接關(guān)系。設(shè)網(wǎng)絡(luò)中傳感器節(jié)點屬于同構(gòu)節(jié)點；通信是對稱的，即從A傳輸?shù)紹一個信息與從B傳輸?shù)紸消耗的能量相同。則傳感器網(wǎng)絡(luò)通信過程中傳送k bit數(shù)據(jù)且傳送距離d時，消耗的能量：

其中，Eelec是發(fā)送電路和接收電路所消耗的能量，εfs、εmp是兩種情況下放大器功率放大需要的能量，d0為門限值。

從上述公式中可以看出，節(jié)點發(fā)送信息消耗的能量與距離d成正比，當(dāng)距離小于門限值d0時與距離平方成正比，大于門限值d0時與距離的四次方成正比，這表明離簇首越遠(yuǎn)的節(jié)點完成數(shù)據(jù)通信需要消耗更多的能量，這就引起傳感器網(wǎng)絡(luò)內(nèi)節(jié)點的剩余能量不均衡的狀態(tài)出現(xiàn)。在LEACH算法中，與基站距離遠(yuǎn)的簇首的能量消耗很快，成為盲節(jié)點。同時所有節(jié)點都能與簇首節(jié)點和基站進(jìn)行通信，這種單跳機(jī)制限制了網(wǎng)絡(luò)規(guī)模，傳感器網(wǎng)絡(luò)的擴(kuò)展性不強(qiáng)。

3 改進(jìn)的LEACH算法

對于上面提到LEACH算法中存在的不足，對算法進(jìn)行如下的改進(jìn)。

3.1 簇首的選擇

在傳統(tǒng)的LEACH算法中是假設(shè)所有節(jié)點初始能量相同，每一個節(jié)點都有相同的概率擔(dān)任簇首節(jié)點，經(jīng)過幾輪簇首選擇之后，節(jié)點剩余能量就會出現(xiàn)很大的差異，選擇出的簇首節(jié)點能耗可能會遠(yuǎn)大于普通節(jié)點。為此可將節(jié)點的剩余能量作為選取簇首的重要因素，按照此思路，可確保能量較大的節(jié)點成為簇首的概率增加，改善網(wǎng)絡(luò)的穩(wěn)定性。

設(shè)某輪節(jié)點當(dāng)前剩余能量為Ec，初始能量為Eo，將二者的比值考慮到傳統(tǒng)選擇簇首的閾值計算中，依據(jù)公式（1），改進(jìn)后的閾值公式為：

或者 T（i）=0 其它

引進(jìn)EC、EO比值后，可避免剩余能量相對較小的節(jié)點成為簇首，減少了簇首能量因消耗過快而出現(xiàn)盲節(jié)點的現(xiàn)象。

圖2 改進(jìn)LEACH算法的流程

3.2 簇首的分布

從考慮傳感器節(jié)點在網(wǎng)絡(luò)中均勻分布出發(fā)，要使簇首節(jié)點與基站距離不能太遠(yuǎn)，不能出現(xiàn)簇首分布聚堆現(xiàn)象。

設(shè)在一個面積為S區(qū)域內(nèi)有n個節(jié)點，在這n個節(jié)點中產(chǎn)生簇首比例為P。要使整個區(qū)域被覆蓋，應(yīng)滿足條件，R為簇的平均半徑，即假設(shè)兩個相鄰簇首節(jié)點之間的間距為D，D就應(yīng)該滿足：D＜2R。在一輪簇首選擇過程中，為使簇首分布均勻，相鄰簇首節(jié)點間距D應(yīng)滿足下面條件：

通過這樣一種機(jī)制，某一簇首確定后，在通信半徑R內(nèi)的節(jié)點就是此簇的成員，使傳感器網(wǎng)絡(luò)中所有簇首節(jié)點的間距均限定在一個相對合理的范圍內(nèi)，確保了簇首的較為合理的分布。

3.3 通信方式

在LEACH算法中規(guī)定了簇首與Sink（基站節(jié)點）采用單跳通信方式，前面提到這種方式容易使離基站遠(yuǎn)的簇首消耗能量過大成為盲節(jié)點。采用混合的通信機(jī)制方式，基本思路是一個簇內(nèi)的節(jié)點間采用單跳的通信方式；簇間進(jìn)行信息傳遞時，若簇首靠近基站就采用單跳的通信方式，如果與基站距離很遠(yuǎn)就采用簇首之間的多跳通信方式。

改進(jìn)后的LEACH算法同樣按輪劃分，某一輪分成簇的建立和簇穩(wěn)定兩個階段，流程圖如圖2所示。

4 結(jié)束語

無線傳感器網(wǎng)絡(luò)的路由算法中的LEACH算法是分簇算法的一種典型代表，在量能受限的網(wǎng)絡(luò)中得到了廣泛應(yīng)用。本文在分析LEACH算法存在的不足基礎(chǔ)上，提出了簇首選擇、網(wǎng)絡(luò)通信兩方面的改進(jìn)，考慮了節(jié)點能量在選擇簇首節(jié)點的因素，提出了基于LEACH的改進(jìn)路由算法。

[1] 武春濤，胡艷軍.無線傳感器網(wǎng)絡(luò)LEACH算法的改進(jìn)[J].計算機(jī)技術(shù)與發(fā)展，2009，19（3）： 80－83.

[2] 付華，趙剛. 無線傳感器網(wǎng)絡(luò)中一種能量均衡的分簇策略[J].計算機(jī)應(yīng)用研究，2009，26（4）：1949－1496.

[3] 顧明霞.一種新的基于LEACH的WSN路由算法[J].計算機(jī)仿真，2011，28（8）：129－133.