無線傳感器網(wǎng)絡(luò)是當(dāng)前網(wǎng)絡(luò)技術(shù)界備受關(guān)注的前沿?zé)狳c(diǎn)研究領(lǐng)域,，涉及多學(xué)科，高度交叉,，知識(shí)高度集成,。無線傳感器網(wǎng)絡(luò)集成了傳感器技術(shù)、計(jì)算機(jī)技術(shù)和通信技術(shù),，在軍事,、環(huán)境、健康,、家庭,、商業(yè)等許多方面有著巨大的潛在應(yīng)用前景。無線傳感器網(wǎng)絡(luò)由大量密集分布的傳感器節(jié)點(diǎn)通過自組織的方式形成網(wǎng)絡(luò),，節(jié)點(diǎn)通過網(wǎng)絡(luò)協(xié)議快速形成自主構(gòu)建,、自主組織和自主管理的通信網(wǎng)絡(luò)。這種通過數(shù)千個(gè)微小的節(jié)點(diǎn)之間互相通信,，通過接力的方法實(shí)現(xiàn)大范圍監(jiān)控的模式極大地提高了工作效率,。然而節(jié)點(diǎn)大都需要在無人看管、不更換電池或者不可能更換電池的條件下長(zhǎng)時(shí)間地工作,，因此高效,、低功耗路由算法在無線傳感器網(wǎng)絡(luò)中就顯得非常重要。

　　1 基于LEACH的經(jīng)典分簇算法分析

　　1．1 LEACH路由算法分析

　　為了提高整個(gè)網(wǎng)絡(luò)的的生存時(shí)間,，將功耗均衡的分配到網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn),，麻省理工學(xué)院的Wendi Rabiner Heinzelman等人提出了一種低功耗的自適應(yīng)路由協(xié)議——LEACH協(xié)議(Low-Energy Adaptive ClusteriingHierarchy)。在LEACH協(xié)議中,，每個(gè)傳感節(jié)點(diǎn)都有機(jī)會(huì)充當(dāng)簇頭節(jié)點(diǎn),，簇頭節(jié)點(diǎn)的選擇主要依據(jù)網(wǎng)絡(luò)中所需要的簇頭節(jié)點(diǎn)個(gè)數(shù)與到目前為止每個(gè)節(jié)點(diǎn)已經(jīng)充當(dāng)簇頭節(jié)點(diǎn)的次數(shù)來判定的。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)在0～1之間隨機(jī)選擇一個(gè)數(shù),，如果選擇的數(shù)小于規(guī)定閥值T(n),，則該節(jié)點(diǎn)就充當(dāng)簇首節(jié)點(diǎn)。T(n)的計(jì)算如下：

　　式(1)中,，p表示在無線網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)所占的百分比,，r為當(dāng)前循環(huán)次數(shù)，G是在前1／p輪中未充當(dāng)過簇頭節(jié)點(diǎn)的集合,。LEACH算法通過設(shè)置T(n)值,，以保證每個(gè)節(jié)點(diǎn)在1／p輪內(nèi)都有機(jī)會(huì)充當(dāng)一次簇頭節(jié)點(diǎn)，從而平衡了節(jié)點(diǎn)的能量消耗,。簇頭節(jié)點(diǎn)確定之后,，簇頭節(jié)點(diǎn)通過廣播告知整個(gè)網(wǎng)絡(luò)自己已經(jīng)成為簇頭節(jié)點(diǎn),，簇頭節(jié)點(diǎn)在廣播過程中采用CSMA MAC協(xié)議來避免沖突。這時(shí),，網(wǎng)絡(luò)中的非簇頭節(jié)點(diǎn)可以根據(jù)接收到的信號(hào)強(qiáng)度來決定自己要從屬于哪個(gè)簇,，選擇信號(hào)強(qiáng)度最強(qiáng)的源節(jié)點(diǎn)作為自己的簇頭節(jié)點(diǎn)，并告知相關(guān)的簇頭節(jié)點(diǎn),，自己則成為簇內(nèi)組員,。

　　LEACH分簇算法缺點(diǎn)：

　　①剛開始假設(shè)每個(gè)節(jié)點(diǎn)能量相同,，在現(xiàn)實(shí)環(huán)境中很難做到,。

　　②每個(gè)節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率相同,，這樣可能導(dǎo)致一些高能量節(jié)點(diǎn)沒機(jī)會(huì)成為簇首節(jié)點(diǎn),，而一些低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)。一旦這些低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn),，將會(huì)很快耗盡其能量,。

　　③LEACH協(xié)議不能保證簇頭在每個(gè)區(qū)域都分布均勻,，雖然統(tǒng)計(jì)上面是均勻的,，但是由于簇頭產(chǎn)生帶有極大的隨機(jī)性，有些區(qū)域可能簇頭數(shù)會(huì)較多,。

　?、艽厥坠?jié)點(diǎn)在通信過程中采用單跳與基站通信，這樣就會(huì)導(dǎo)致較遠(yuǎn)的簇首節(jié)點(diǎn)能量消耗過大,，而過早死亡,，影響整個(gè)網(wǎng)絡(luò)的性能。

　?、菡麄€(gè)網(wǎng)絡(luò)節(jié)點(diǎn)在兩跳范圍內(nèi),，這樣不符合大規(guī)模網(wǎng)絡(luò)需求,。

　　1．2 根據(jù)節(jié)點(diǎn)初始能量不同改進(jìn)

　　根據(jù)整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)能量的初始不同,，Georgios Smaragdakis等人提出了一種改進(jìn)行分簇算法——SEP算法(a Stable Election Proto-col for clustered heterogeneous)，先把整個(gè)網(wǎng)絡(luò)分成兩類節(jié)點(diǎn),，能量較高的節(jié)點(diǎn)稱為高能量節(jié)點(diǎn),，能量低的稱為正常節(jié)點(diǎn)。高能量節(jié)點(diǎn)則根據(jù)式(2)進(jìn)行選擇成為簇首節(jié)點(diǎn)的概率,，而正常節(jié)點(diǎn)則根據(jù)式(3)選擇成為簇首節(jié)點(diǎn)的概率,。可以看出,，高能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的機(jī)會(huì)大于低能量節(jié)點(diǎn),。相較于LEACH算法,，充分利用了整個(gè)網(wǎng)絡(luò)的功耗。

　　為整個(gè)網(wǎng)絡(luò)簇首節(jié)點(diǎn)的概率,，Pnrm為正常節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率,，Padv為高能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率。r為當(dāng)前循環(huán)次數(shù),，G1是在前1／p輪中正常節(jié)點(diǎn)未充當(dāng)過簇頭節(jié)點(diǎn)的集合,。G2是在前1／p輪中高能量節(jié)點(diǎn)未充當(dāng)過簇頭節(jié)點(diǎn)的集合。m為網(wǎng)絡(luò)中高能量節(jié)點(diǎn)的比例,。a為高能量節(jié)點(diǎn)高于正常節(jié)點(diǎn)能量部分,。

　　在參考文獻(xiàn)中，作者對(duì)SEp算法進(jìn)行再次改進(jìn),，利用整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的平均能量與節(jié)點(diǎn)當(dāng)前能量的比值來限制節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率,，兩類節(jié)點(diǎn)成為簇首節(jié)點(diǎn)概率如式(4)所示。

　　根據(jù)式(4),，可以看出進(jìn)一步限制的低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率,。

　　1．3 根據(jù)節(jié)點(diǎn)剩余能量的不同而改進(jìn)

　　M．J．Handy等人提出了DCHS(Deterministic Clus-ter-Head Selection)算法，根據(jù)LEACH算法中的T(n)計(jì)算不足之處,，對(duì)其進(jìn)行改進(jìn),，如式(5)所示。式(5)中En_current表示節(jié)點(diǎn)當(dāng)前的能量,，En_max表示節(jié)點(diǎn)初始的能量,。

　　由改進(jìn)后的算法可以看出，當(dāng)前節(jié)點(diǎn)能量比較高的節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率變大,，從而降低了低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率,，提高了整個(gè)網(wǎng)絡(luò)的性能。然而根據(jù)式(5)可以看出,，當(dāng)整個(gè)網(wǎng)絡(luò)運(yùn)行到一定的時(shí)間后,，大部分節(jié)點(diǎn)的能量都將剩余不多，相應(yīng)的T(n)就會(huì)變小,，那么整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)成為簇首的概率變小,，從而影響到整個(gè)網(wǎng)絡(luò)的性能。M．J．Handy等人對(duì)式(5)進(jìn)一步改進(jìn),，得到式(6),，從而有效解決了式(5)的不足之處。在式(6)中rs表示節(jié)點(diǎn)連續(xù)未當(dāng)選過簇頭的輪次,。一旦節(jié)點(diǎn)當(dāng)選為簇首節(jié)點(diǎn),，則rs置零。

　　1．4 根據(jù)簇首節(jié)點(diǎn)隨機(jī)分布不均而改進(jìn)

　　LEACH-C算法是LEACH算法的集中式控制版本,，采用模擬退火算法獲得更優(yōu)的簇頭選舉策略,，克服了LEACH算法中每輪產(chǎn)生的簇頭數(shù)與位置的隨機(jī)性,。

　　LEACH-C算法可以把每個(gè)節(jié)點(diǎn)的地理位置以及節(jié)點(diǎn)當(dāng)前的能量報(bào)告給基站?；景阉泄?jié)點(diǎn)的能量取平均,，當(dāng)網(wǎng)絡(luò)中某些節(jié)點(diǎn)的能量低于平均值時(shí)，將不能成為候選簇頭節(jié)點(diǎn),，從而更加有效地解決了低能量節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的概率,。

　　1．5 根據(jù)LEACH實(shí)時(shí)性不強(qiáng)而改進(jìn)

　　根據(jù)LEACH算法實(shí)時(shí)性不強(qiáng)的問題，Manjeshwar A等人提出了TEEN算法,，TEEN算法與LEACH算法較大的不同點(diǎn)是,，在簇首節(jié)點(diǎn)的選舉過程中，協(xié)議設(shè)置了兩個(gè)閾值,，分別為硬閾值,、軟閾值兩個(gè)參數(shù)。硬閾值是被檢測(cè)數(shù)據(jù)不能超過的數(shù)值,，而且軟閾值決定了被測(cè)數(shù)據(jù)的波動(dòng)范圍,。只有當(dāng)被監(jiān)測(cè)數(shù)據(jù)超過硬閾值且被監(jiān)測(cè)數(shù)據(jù)的變化幅度大于軟閾值時(shí)，節(jié)點(diǎn)才會(huì)傳送最新的監(jiān)測(cè)數(shù)據(jù),，并設(shè)置為新的硬閾值,。相對(duì)于LEACH算法，TEEN算法能夠較大地減少節(jié)點(diǎn)之間數(shù)據(jù)傳送的次數(shù),，從而有效減少了整個(gè)網(wǎng)絡(luò)的功耗,，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。APTEEN算法則結(jié)合了LEACH與TEEN兩種算法,，是一種主動(dòng)型與響應(yīng)型混合的數(shù)據(jù)傳輸模式,。但網(wǎng)絡(luò)中有突發(fā)事件時(shí)，數(shù)據(jù)傳輸模式將會(huì)采用與TEEN相同的模式(響應(yīng)型模式),，只不過AFTEEN算法多了一個(gè)計(jì)數(shù)器,，節(jié)點(diǎn)每傳送一次數(shù)據(jù)，對(duì)應(yīng)的計(jì)數(shù)器將清零,。當(dāng)計(jì)數(shù)器的時(shí)間到達(dá)的時(shí)候,，將采取主動(dòng)發(fā)送這個(gè)數(shù)據(jù)，不再判斷軟,、硬門限值,。

　　1．6 根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)分布密度不均而改進(jìn)

　　在LEACH算法中并未考慮節(jié)點(diǎn)分布密度對(duì)網(wǎng)絡(luò)的影響,，在分布密度大的區(qū)域,，相對(duì)簇首節(jié)點(diǎn)的負(fù)擔(dān)也較重，能量也容易耗盡,，因此應(yīng)該增加該區(qū)域簇首節(jié)點(diǎn)的個(gè)數(shù),。參考文獻(xiàn)中根據(jù)無線網(wǎng)絡(luò)中周圍節(jié)點(diǎn)存活個(gè)數(shù)不同,，來改變?cè)搮^(qū)域內(nèi)節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率。為了在節(jié)點(diǎn)密集區(qū)域增加簇頭的個(gè)數(shù),，只需要增大對(duì)應(yīng)節(jié)點(diǎn)成為簇頭的概率,，對(duì)于節(jié)點(diǎn)稀疏區(qū)域則降低其中節(jié)點(diǎn)成為簇頭的概率即可。因此將簇頭選舉的閾值修改為：

　　式(7)中Neighbor(n)_alive與Network_alive分別表示表示節(jié)點(diǎn)n鄰居集中以及整個(gè)網(wǎng)絡(luò)中存活節(jié)點(diǎn)的數(shù)目,，1／p表示平均每簇中節(jié)點(diǎn)的個(gè)數(shù),，從式(7)可以看出當(dāng)節(jié)點(diǎn)周圍存活個(gè)數(shù)大于平均值時(shí)，該區(qū)域節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率將增大,，反之則降低,。

　　1．7 根據(jù)大規(guī)模多跳網(wǎng)絡(luò)而改進(jìn)

　　根據(jù)LEACH算法跳距的局限性，在LEACH算法中,，整個(gè)網(wǎng)絡(luò)最大跳距為兩跳,，這樣就會(huì)導(dǎo)致遠(yuǎn)離基站的簇首節(jié)點(diǎn)，能量消耗太大而過早死亡,，影響到整個(gè)網(wǎng)絡(luò)的性能,，Siva D．Muruganathan等人提出了BCDCP多跳分簇算法，簇首節(jié)點(diǎn)的選擇由基站來控制,，基站首先將每個(gè)節(jié)點(diǎn)的當(dāng)前能量取平均,，只有大于平均值的節(jié)點(diǎn)才有機(jī)會(huì)成為簇首節(jié)點(diǎn)，這樣就避開了低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的可能,。當(dāng)簇首節(jié)點(diǎn)與基站的距離超過一定時(shí),，不直接與基站通信，而是借助其他簇首節(jié)點(diǎn)轉(zhuǎn)發(fā)到基站,，選擇其他簇首節(jié)點(diǎn)是采用的是最小生成樹算法,，這樣就減輕了遠(yuǎn)離基站簇首節(jié)點(diǎn)的負(fù)擔(dān)，也擴(kuò)展了整個(gè)網(wǎng)絡(luò)的規(guī)模,。

　　1．8 節(jié)點(diǎn)能量傳輸模型與最優(yōu)簇首節(jié)點(diǎn)概率

　　大部分作者都把節(jié)點(diǎn)傳輸模型采用公式(8)與(9),，式中k為傳輸信息的比特?cái)?shù)，d為節(jié)點(diǎn)之間距離,。εfs為自由空間傳送方式下的功率放大參數(shù),。式(8)為節(jié)點(diǎn)接收數(shù)據(jù)所消耗的能量，式(9)是發(fā)送數(shù)據(jù)所消耗的能量,，因本文針對(duì)的是小規(guī)模無線傳感器網(wǎng)絡(luò),，所以采用的是自由空間模型。

　　因?yàn)椴煌?guī)模的網(wǎng)絡(luò),，節(jié)點(diǎn)密度的不同,，最優(yōu)簇首個(gè)數(shù)也不相同，采用參考文獻(xiàn)提出的最優(yōu)簇首個(gè)數(shù)公式(10)，采用的是自由空間模型,。

　　2 分簇路由算法設(shè)計(jì)

　　2．1 算法設(shè)計(jì)

　　本文主要針對(duì)一些特定的環(huán)境下,，對(duì)經(jīng)典的LEACH算法進(jìn)行改進(jìn)。目前關(guān)于無線傳感器網(wǎng)絡(luò)測(cè)距技術(shù),，普遍采用信號(hào)強(qiáng)度與信號(hào)差往返時(shí)間來測(cè)距兩種方法,。前者在理論上較難實(shí)現(xiàn)，一般很難在現(xiàn)實(shí)中使用,。而后者理論簡(jiǎn)單,，但由于硬件成本的限制，只能采用一般的時(shí)鐘晶振,，這時(shí)就對(duì)節(jié)點(diǎn)之間的時(shí)間同步提出了較高的要求,。而目前傳統(tǒng)的時(shí)間同步算法都會(huì)隨著跳數(shù)的增加，誤差越變?cè)酱?，而在小?guī)模測(cè)距定位系統(tǒng)中,，節(jié)點(diǎn)之間無需傳輸大量的數(shù)據(jù)，因此簇首節(jié)點(diǎn)無需進(jìn)行大量的數(shù)據(jù)融合,，因此本文設(shè)計(jì)的初衷是減少傳輸跳數(shù),、延長(zhǎng)整個(gè)網(wǎng)絡(luò)生存時(shí)間。因此對(duì)傳統(tǒng)的LEACH算法作以下改進(jìn),。能量傳輸模型采用式(8)與式(9),，網(wǎng)絡(luò)中最優(yōu)簇首個(gè)數(shù)比例采用式(10)，規(guī)定閾值T(n)采用式(6),。

　　條件1：如圖1所示,，當(dāng)dBD>dAD或dAB>dAD，直接讓簇內(nèi)節(jié)點(diǎn)D把數(shù)據(jù)傳輸給基站,，與簇內(nèi)節(jié)點(diǎn)D先把數(shù)據(jù)傳給簇首B,，在轉(zhuǎn)發(fā)給基站A的能量要少。

　　顯然可以看出當(dāng)dBD>dAD時(shí),，ETxDB>ETxDA,，接收能量是相同的。這樣就很容易得到當(dāng)dBD>dAD時(shí),，直接讓簇內(nèi)節(jié)點(diǎn)把數(shù)據(jù)傳輸給基站,，與簇內(nèi)節(jié)點(diǎn)先把數(shù)據(jù)傳給簇首，在轉(zhuǎn)發(fā)給基站的能量要少是成立的,。同理當(dāng)dAB>dAD時(shí)也是成立的,。

　　條件2：如圖1所示，當(dāng)時(shí),，則直接讓簇內(nèi)節(jié)點(diǎn)D把數(shù)據(jù)傳輸給基站,，與簇內(nèi)節(jié)點(diǎn)D先把數(shù)據(jù)傳給簇首B,，在轉(zhuǎn)發(fā)給基站A的能量要少。

　　2．2 算法性能分析

　　根據(jù)2．1小節(jié)所討論的條件下對(duì)LEACH算法進(jìn)行改進(jìn),，在其他參數(shù)都相同的條件下,，改進(jìn)前與改進(jìn)后死亡節(jié)點(diǎn)個(gè)數(shù)隨選舉輪數(shù)增加而變化情況如圖2所示,。從圖2中可以看出,，改進(jìn)后的算法節(jié)點(diǎn)生存時(shí)間優(yōu)于改進(jìn)前的算法，尤其隨著選舉輪數(shù)增加,，優(yōu)勢(shì)越來越明顯,。改進(jìn)前第一個(gè)節(jié)點(diǎn)的死亡時(shí)間為1051輪，改進(jìn)后第一個(gè)節(jié)點(diǎn)死亡時(shí)間為1062輪,，改進(jìn)前一半節(jié)點(diǎn)死亡時(shí)間為1273輪,，改進(jìn)后為1301輪。從2．1小節(jié)也可以知道,，部分簇內(nèi)節(jié)點(diǎn)可以直接與基站通信,，從而減少了部分節(jié)點(diǎn)的傳輸跳數(shù)。