無線傳感器網絡是當前網絡技術界備受關注的前沿熱點研究領域，涉及多學科，高度交叉，知識高度集成。無線傳感器網絡集成了傳感器技術、計算機技術和通信技術，在軍事、環境、健康、家庭、商業等許多方面有著巨大的潛在應用前景。無線傳感器網絡由大量密集分布的傳感器節點通過自組織的方式形成網絡，節點通過網絡協議快速形成自主構建、自主組織和自主管理的通信網絡。這種通過數千個微小的節點之間互相通信，通過接力的方法實現大范圍監控的模式極大地提高了工作效率。然而節點大都需要在無人看管、不更換電池或者不可能更換電池的條件下長時間地工作，因此高效、低功耗路由算法在無線傳感器網絡中就顯得非常重要。
1 基于LEACH的經典分簇算法分析
1．1 LEACH路由算法分析
為了提高整個網絡的的生存時間，將功耗均衡的分配到網絡中的每個節點，麻省理工學院的Wendi Rabiner Heinzelman等人提出了一種低功耗的自適應路由協議——LEACH協議(Low-Energy Adaptive ClusteriingHierarchy)。在LEACH協議中，每個傳感節點都有機會充當簇頭節點，簇頭節點的選擇主要依據網絡中所需要的簇頭節點個數與到目前為止每個節點已經充當簇頭節點的次數來判定的。網絡中每個節點在0～1之間隨機選擇一個數，如果選擇的數小于規定閥值T(n)，則該節點就充當簇首節點。T(n)的計算如下：
式(1)中，p表示在無線網絡中簇頭節點所占的百分比，r為當前循環次數，G是在前1／p輪中未充當過簇頭節點的集合。LEACH算法通過設置T(n)值，以保證每個節點在1／p輪內都有機會充當一次簇頭節點，從而平衡了節點的能量消耗。簇頭節點確定之后，簇頭節點通過廣播告知整個網絡自己已經成為簇頭節點，簇頭節點在廣播過程中采用CSMA MAC協議來避免沖突。這時，網絡中的非簇頭節點可以根據接收到的信號強度來決定自己要從屬于哪個簇，選擇信號強度最強的源節點作為自己的簇頭節點，并告知相關的簇頭節點，自己則成為簇內組員。
LEACH分簇算法缺點：
?、賱傞_始假設每個節點能量相同，在現實環境中很難做到。
?、诿總€節點成為簇首節點的概率相同，這樣可能導致一些高能量節點沒機會成為簇首節點，而一些低能量節點成為簇首節點。一旦這些低能量節點成為簇首節點，將會很快耗盡其能量。
③LEACH協議不能保證簇頭在每個區域都分布均勻，雖然統計上面是均勻的，但是由于簇頭產生帶有極大的隨機性，有些區域可能簇頭數會較多。
?、艽厥坠濣c在通信過程中采用單跳與基站通信，這樣就會導致較遠的簇首節點能量消耗過大，而過早死亡，影響整個網絡的性能。
⑤整個網絡節點在兩跳范圍內，這樣不符合大規模網絡需求。
1．2 根據節點初始能量不同改進
根據整個網絡中節點能量的初始不同，Georgios Smaragdakis等人提出了一種改進行分簇算法——SEP算法(a Stable Election Proto-col for clustered heterogeneous)，先把整個網絡分成兩類節點，能量較高的節點稱為高能量節點，能量低的稱為正常節點。高能量節點則根據式(2)進行選擇成為簇首節點的概率，而正常節點則根據式(3)選擇成為簇首節點的概率。可以看出，高能量節點成為簇首節點的機會大于低能量節點。相較于LEACH算法，充分利用了整個網絡的功耗。
為整個網絡簇首節點的概率，Pnrm為正常節點成為簇首節點的概率，Padv為高能量節點成為簇首節點的概率。r為當前循環次數，G1是在前1／p輪中正常節點未充當過簇頭節點的集合。G2是在前1／p輪中高能量節點未充當過簇頭節點的集合。m為網絡中高能量節點的比例。a為高能量節點高于正常節點能量部分。
在參考文獻中，作者對SEp算法進行再次改進，利用整個網絡節點的平均能量與節點當前能量的比值來限制節點成為簇首節點的概率，兩類節點成為簇首節點概率如式(4)所示。
根據式(4)，可以看出進一步限制的低能量節點成為簇首節點的概率。
1．3 根據節點剩余能量的不同而改進
M．J．Handy等人提出了DCHS(Deterministic Clus-ter-Head Selection)算法，根據LEACH算法中的T(n)計算不足之處，對其進行改進，如式(5)所示。式(5)中En_current表示節點當前的能量，En_max表示節點初始的能量。
由改進后的算法可以看出，當前節點能量比較高的節點成為簇首節點的概率變大，從而降低了低能量節點成為簇首節點的概率，提高了整個網絡的性能。然而根據式(5)可以看出，當整個網絡運行到一定的時間后，大部分節點的能量都將剩余不多，相應的T(n)就會變小，那么整個網絡中節點成為簇首的概率變小，從而影響到整個網絡的性能。M．J．Handy等人對式(5)進一步改進，得到式(6)，從而有效解決了式(5)的不足之處。在式(6)中rs表示節點連續未當選過簇頭的輪次。一旦節點當選為簇首節點，則rs置零。
1．4 根據簇首節點隨機分布不均而改進
LEACH-C算法是LEACH算法的集中式控制版本，采用模擬退火算法獲得更優的簇頭選舉策略，克服了LEACH算法中每輪產生的簇頭數與位置的隨機性。
LEACH-C算法可以把每個節點的地理位置以及節點當前的能量報告給基站。基站把所有節點的能量取平均，當網絡中某些節點的能量低于平均值時，將不能成為候選簇頭節點，從而更加有效地解決了低能量節點成為簇頭節點的概率。
1．5 根據LEACH實時性不強而改進
根據LEACH算法實時性不強的問題，Manjeshwar A等人提出了TEEN算法，TEEN算法與LEACH算法較大的不同點是，在簇首節點的選舉過程中，協議設置了兩個閾值，分別為硬閾值、軟閾值兩個參數。硬閾值是被檢測數據不能超過的數值，而且軟閾值決定了被測數據的波動范圍。只有當被監測數據超過硬閾值且被監測數據的變化幅度大于軟閾值時，節點才會傳送最新的監測數據，并設置為新的硬閾值。相對于LEACH算法，TEEN算法能夠較大地減少節點之間數據傳送的次數，從而有效減少了整個網絡的功耗，延長了整個網絡的壽命。APTEEN算法則結合了LEACH與TEEN兩種算法，是一種主動型與響應型混合的數據傳輸模式。但網絡中有突發事件時，數據傳輸模式將會采用與TEEN相同的模式(響應型模式)，只不過AFTEEN算法多了一個計數器，節點每傳送一次數據，對應的計數器將清零。當計數器的時間到達的時候，將采取主動發送這個數據，不再判斷軟、硬門限值。
1．6 根據網絡節點分布密度不均而改進
在LEACH算法中并未考慮節點分布密度對網絡的影響，在分布密度大的區域，相對簇首節點的負擔也較重，能量也容易耗盡，因此應該增加該區域簇首節點的個數。參考文獻中根據無線網絡中周圍節點存活個數不同，來改變該區域內節點成為簇首節點的概率。為了在節點密集區域增加簇頭的個數，只需要增大對應節點成為簇頭的概率，對于節點稀疏區域則降低其中節點成為簇頭的概率即可。因此將簇頭選舉的閾值修改為：
式(7)中Neighbor(n)_alive與Network_alive分別表示表示節點n鄰居集中以及整個網絡中存活節點的數目，1／p表示平均每簇中節點的個數，從式(7)可以看出當節點周圍存活個數大于平均值時，該區域節點成為簇首節點的概率將增大，反之則降低。
1．7 根據大規模多跳網絡而改進
根據LEACH算法跳距的局限性，在LEACH算法中，整個網絡最大跳距為兩跳，這樣就會導致遠離基站的簇首節點，能量消耗太大而過早死亡，影響到整個網絡的性能，Siva D．Muruganathan等人提出了BCDCP多跳分簇算法，簇首節點的選擇由基站來控制，基站首先將每個節點的當前能量取平均，只有大于平均值的節點才有機會成為簇首節點，這樣就避開了低能量節點成為簇首節點的可能。當簇首節點與基站的距離超過一定時，不直接與基站通信，而是借助其他簇首節點轉發到基站，選擇其他簇首節點是采用的是最小生成樹算法，這樣就減輕了遠離基站簇首節點的負擔，也擴展了整個網絡的規模。
1．8 節點能量傳輸模型與最優簇首節點概率
大部分作者都把節點傳輸模型采用公式(8)與(9)，式中k為傳輸信息的比特數，d為節點之間距離。εfs為自由空間傳送方式下的功率放大參數。式(8)為節點接收數據所消耗的能量，式(9)是發送數據所消耗的能量，因本文針對的是小規模無線傳感器網絡，所以采用的是自由空間模型。
因為不同規模的網絡，節點密度的不同，最優簇首個數也不相同，采用參考文獻提出的最優簇首個數公式(10)，采用的是自由空間模型。
2 分簇路由算法設計
2．1 算法設計
本文主要針對一些特定的環境下，對經典的LEACH算法進行改進。目前關于無線傳感器網絡測距技術，普遍采用信號強度與信號差往返時間來測距兩種方法。前者在理論上較難實現，一般很難在現實中使用。而后者理論簡單，但由于硬件成本的限制，只能采用一般的時鐘晶振，這時就對節點之間的時間同步提出了較高的要求。而目前傳統的時間同步算法都會隨著跳數的增加，誤差越變越大，而在小規模測距定位系統中，節點之間無需傳輸大量的數據，因此簇首節點無需進行大量的數據融合，因此本文設計的初衷是減少傳輸跳數、延長整個網絡生存時間。因此對傳統的LEACH算法作以下改進。能量傳輸模型采用式(8)與式(9)，網絡中最優簇首個數比例采用式(10)，規定閾值T(n)采用式(6)。
條件1：如圖1所示，當dBD>dAD或dAB>dAD，直接讓簇內節點D把數據傳輸給基站，與簇內節點D先把數據傳給簇首B，在轉發給基站A的能量要少。
顯然可以看出當dBD>dAD時，ETxDB>ETxDA，接收能量是相同的。這樣就很容易得到當dBD>dAD時，直接讓簇內節點把數據傳輸給基站，與簇內節點先把數據傳給簇首，在轉發給基站的能量要少是成立的。同理當dAB>dAD時也是成立的。
條件2：如圖1所示，當
時，則直接讓簇內節點D把數據傳輸給基站，與簇內節點D先把數據傳給簇首B，在轉發給基站A的能量要少。
2．2 算法性能分析
根據2．1小節所討論的條件下對LEACH算法進行改進，在其他參數都相同的條件下，改進前與改進后死亡節點個數隨選舉輪數增加而變化情況如圖2所示。從圖2中可以看出，改進后的算法節點生存時間優于改進前的算法，尤其隨著選舉輪數增加，優勢越來越明顯。改進前第一個節點的死亡時間為1051輪，改進后第一個節點死亡時間為1062輪，改進前一半節點死亡時間為1273輪，改進后為1301輪。從2．1小節也可以知道，部分簇內節點可以直接與基站通信，從而減少了部分節點的傳輸跳數。
