無線傳感器網(wǎng)絡(luò)（WSN）[1]是集數(shù)據(jù)采集,、處理及通信功能于一體的分布式自組織網(wǎng)絡(luò),，其特點是能量、計算能力和存儲空間有限,。無線傳感器網(wǎng)絡(luò)中的路由協(xié)議必須時刻關(guān)注降低能耗,、延長網(wǎng)絡(luò)生命周期這一核心問題。設(shè)計精良的網(wǎng)絡(luò)協(xié)議就可以降低能耗,，延長網(wǎng)絡(luò)的生命周期,。通常無線傳感器網(wǎng)絡(luò)的路由協(xié)議[2]可以分為平面路由協(xié)議和層次路由協(xié)議兩種。目前,，路由協(xié)議的主流是層次路由協(xié)議,，該協(xié)議具有代表性的路由算法是低功耗自適應(yīng)分簇（LEACH）算法[3]。LEACH協(xié)議中,，簇首形成高一層的網(wǎng)絡(luò),，這樣簇內(nèi)成員的功能就變相地簡單，大大減少了路由控制信息的數(shù)量,。但該協(xié)議也存在耗能大,、能量不均衡的問題。針對以上問題,，本文通過對經(jīng)典的分簇路由協(xié)議LEACH的分析,，并且以降低功耗、實現(xiàn)能量均衡,、延長網(wǎng)絡(luò)壽命為主要目的,，對LEACH協(xié)議進(jìn)行改進(jìn)。
1 LEACH算法分析
LEACH算法（Low Energy Adaptive Clustering Hierarchy）是MIT的Chandrakasan等人為無線傳感器網(wǎng)絡(luò)設(shè)計的低功率自適應(yīng)分簇路由算法,。它的基本思想是：以循環(huán)的方式隨機選擇簇首節(jié)點,，將整個網(wǎng)絡(luò)的能量負(fù)載平均分配到每個傳感器節(jié)點中,，從而達(dá)到提高網(wǎng)絡(luò)整體生存時間的目的。LEACH在運行過程中不斷地循環(huán)執(zhí)行簇的重構(gòu)過程,，每個簇重構(gòu)過程可以用“輪（round）”來描述,，每一輪包含簇的建立和穩(wěn)定運行兩個階段。其中穩(wěn)定階段持續(xù)時間要比簇建立階段持續(xù)的時間長得多,。
1.1 LEACH算法的工作流程
該算法的建立主要包括三個階段：
（1）簇首的建立
簇頭節(jié)點的選取是LEACH算法中的關(guān)鍵,，具體的選擇方法是：各節(jié)點產(chǎn)生一個[0，1]之間的隨機數(shù),，若該數(shù)小于某一個閾值T(n)[4],，則該節(jié)點成為簇頭。
式中,，p是網(wǎng)絡(luò)中簇頭數(shù)與總節(jié)點數(shù)的百分比,，r是當(dāng)前的選舉輪數(shù)，G是最近1/p輪而不是簇頭的節(jié)點集合,。
被選為簇首的節(jié)點會利用CSMA MAC協(xié)議廣播ADV消息,，宣布自己成為簇首。非簇首節(jié)點收到來自各簇首的消息,，并根據(jù)接收信號的強度選擇強度最大的簇首發(fā)送加入請求JOIN-REQ（其包含了節(jié)點的ID和要求加入簇首的ID信息）,。
（2）時隙表建立
當(dāng)簇首確定并且簇域劃分工作完成后，簇頭將根據(jù)成員節(jié)點的數(shù)目,，產(chǎn)生TDMA時隙表,。成員節(jié)點通過接收簇首的廣播獲取該表，并在自己的時隙到達(dá)時才開啟發(fā)送裝置向簇首發(fā)送數(shù)據(jù),，其余時間處于休眠狀態(tài)以節(jié)省能量,。
（3）穩(wěn)定
相對于簇的建立階段，穩(wěn)定階段是相對較長的一個階段,，該階段主要是各節(jié)點完成數(shù)據(jù)傳輸?shù)娜蝿?wù),。一旦簇形成，TDMA時刻表確定,，則數(shù)據(jù)傳輸開始,。簇首節(jié)點在收到成員節(jié)點傳來的數(shù)據(jù)后對數(shù)據(jù)進(jìn)行數(shù)據(jù)融合和壓縮，將壓縮處理后的信號傳輸給基站,。
1.2 LEACH算法存在的問題
（1）壽命不均：簇首的選舉策略是隨機的,，可能造成簇首分布不均，簇成員個數(shù)也有較大差異,，使得各簇首負(fù)載不均衡,，造成個別簇首較早死亡。
（2）距離受限：LEACH協(xié)議只適用于小規(guī)模的無線傳感器網(wǎng)絡(luò),。由于基站與簇首之間采用單跳路徑選擇模式,，所以簇首與基站必須布置在通信可達(dá)的范圍內(nèi)。
2 LEACH算法的改進(jìn)
2.1 改進(jìn)算法的設(shè)計思路
針對LEACH算法中存在的問題,，結(jié)合無線傳感器網(wǎng)絡(luò)的特點,，本文從以下幾個方面對LEACH協(xié)議進(jìn)行改進(jìn)。
（1）改變簇首產(chǎn)生方式
主要從以下兩個方面改變簇首的產(chǎn)生：
①基于節(jié)點的剩余能量選擇簇首,?？紤]到無線傳感器網(wǎng)絡(luò)的能耗問題，選取能量較多的節(jié)點作為簇首,。將節(jié)點的剩余能量作為選擇簇首的一個重要衡量標(biāo)準(zhǔn),，以保證區(qū)域內(nèi)剩余能量較多的節(jié)點被選為簇首。
②基于節(jié)點與簇首之間的距離選擇簇首,?？紤]到簇首地理分布平均的問題，每個簇首發(fā)射信號,，其他節(jié)點則根據(jù)接收到的信號判斷離簇首的距離,，離簇首距離小于設(shè)定值M的節(jié)點不再選為簇首，從而保證所有簇首之間距離不小于M,。
（2）改變簇首與基站之間的通信方式
LEACH算法中,，簇首與基站（BS）之間的數(shù)據(jù)發(fā)送過程采用單跳的方式。由于基站距離傳感區(qū)域很遠(yuǎn),，所以簇首將數(shù)據(jù)發(fā)送給基站時所消耗的能量很多,。基于這一點,，在簇首向基站發(fā)送數(shù)據(jù)的時候采用多跳的方式,，這樣可以使簇首節(jié)點能量的消耗相對減少。本文提出的改進(jìn)算法是把簇首組織起來,，以多跳的方式向基站發(fā)送融合后的數(shù)據(jù),。
2.2 改進(jìn)算法的實現(xiàn)
在第一輪開始時，傳感區(qū)域內(nèi)的所有節(jié)點需要將自己的地理位置信息和節(jié)點能量發(fā)送給基站,基站收集到區(qū)域內(nèi)各個節(jié)點的位置信息后,，根據(jù)這些信息將傳感器網(wǎng)絡(luò)按面積平均劃分為k個區(qū)域（本文設(shè)定k=3）,，即需要將整個區(qū)域劃分為如圖1所示的三部分。
區(qū)域劃分完成以后,，每個節(jié)點隨機地產(chǎn)生一個0~1之間的隨機數(shù),，如果小于閾值T(n)，則該節(jié)點當(dāng)選為候補簇首(T(n)的計算與LEACH中相同),；然后把選出的候補簇首按能量的大小遞減排列成一個隊列,，從隊列中第一個節(jié)點開始，取消以節(jié)點為圓心,、半徑為M的圓內(nèi)的其他候補簇首成為簇首的資格,，并將其從列隊中刪除,。
最優(yōu)簇頭數(shù)(kopt)個節(jié)點完全無縫覆蓋檢測區(qū)域需要滿足的條件[5]是：
依次遍歷其他節(jié)點，重復(fù)上述操作,。最后剩下的候補簇首即成為最終的簇首,。
當(dāng)選為簇首的節(jié)點會將自己的ID添加到該簇域的全局變量ch_list_中去，最終得到的ch_list_就是該簇域內(nèi)所有簇首節(jié)點ID的列表,。通過簇域的ch_list_即可以得到下游（下游指的是指向BS方向的下一個簇域）簇域內(nèi)的所有節(jié)點的ID列表,。有了該列表，就相當(dāng)于得到了下一跳的候選列表,。如圖2所示,，簇首只需從這些候選節(jié)點中隨機選出一個節(jié)點作為自己的下一跳節(jié)點，這樣就將各個簇首的多跳路徑建立起來了,。
3 算法的仿真及分析
3.1 仿真環(huán)境
本文采用NS2[6]對LEACH及改進(jìn)后的LEACH算法進(jìn)行仿真,。仿真環(huán)境設(shè)定如下：
(1)傳感器節(jié)點和虛擬聚類區(qū)域具有全局唯一的ID標(biāo)識；
(2)網(wǎng)絡(luò)內(nèi)所有傳感器節(jié)點均相同,，具有相同的初始能量2J,，且信號均可到達(dá)基站。
(3)各個傳感器節(jié)點具備GPS功能,，即節(jié)點能定位其位置,。
3.2 仿真結(jié)果與分析
(1)在仿真過程中，節(jié)點的能量會隨著時間的推移逐漸減少,，直至能量耗盡而死,，所以在各個時段傳感區(qū)域內(nèi)仍未耗盡能量的節(jié)點個數(shù)是不同的。圖3是LEACH和改進(jìn)后的LEACH兩種算法在不同時段仍然存活的節(jié)點個數(shù)比較,。
從圖3中可以得出以下結(jié)論：
①LEACH算法在365 s時出現(xiàn)節(jié)點死亡,，而改進(jìn)后的算法在375 s時開始有節(jié)點出現(xiàn)死亡。從節(jié)點開始死亡的時間上說明,，改進(jìn)后的算法相對于LEACH算法提高了2.73%,。
②LEACH算法在500 s左右時結(jié)束了網(wǎng)絡(luò)生命，而改進(jìn)后的算法在580 s左右時才結(jié)束網(wǎng)絡(luò)生命,。從網(wǎng)絡(luò)存活時間比較說明,，改進(jìn)后的算法比LEACH算法存活時間延長了16%。
(2)不同時段網(wǎng)絡(luò)內(nèi)存活節(jié)點數(shù)目的比較很直觀地說明了兩種算法下網(wǎng)絡(luò)生命周期的不同,。下面從能量消耗的角度來進(jìn)一步對兩種算法進(jìn)行比較,。
圖4為兩種算法下在不同時段網(wǎng)絡(luò)消耗總能量的值，由圖4可以看出,，LEACH算法在500 s結(jié)束網(wǎng)絡(luò)生命時的總能耗為450 J左右,，而改進(jìn)后的算法在580 s時結(jié)束生命周期時總能耗是350 J。對比結(jié)果進(jìn)一步印證了本文算法較LEACH算法延長了網(wǎng)絡(luò)生命周期。
（3）兩種協(xié)議的性能比較如表1所示,。
從表1可以看出,，改進(jìn)-LEACH協(xié)議和LEACH協(xié)議相比，如果以節(jié)點開始死亡的時間為標(biāo)準(zhǔn),，改進(jìn)-LEACH協(xié)議相比LEACH協(xié)議可有2.73%的提高,；若以網(wǎng)絡(luò)生命周期為標(biāo)準(zhǔn),，則有16%的提高,；如果以網(wǎng)絡(luò)總能耗為標(biāo)準(zhǔn)，相比LEACH協(xié)議,，改進(jìn)-LEACH協(xié)議其性能提高了21%,。
本文針對無線傳感器網(wǎng)絡(luò)，在理論分析的基礎(chǔ)上提出了一種改進(jìn)的LEACH協(xié)議,。該協(xié)議在選擇簇首方面,，充分考慮了網(wǎng)絡(luò)中節(jié)點的位置和剩余能量，進(jìn)而使簇的大小更為合理,；在簇首與基站之間的路徑選擇方面,，采取了多跳傳輸?shù)姆绞健Ｍㄟ^NS2的仿真實驗表明,，將改進(jìn)后的算法應(yīng)用于傳感器網(wǎng)絡(luò)中,，能更有效地降低與均衡網(wǎng)絡(luò)的能量消耗，從而較大幅度地延長了傳感器網(wǎng)絡(luò)的生命周期,。
參考文獻(xiàn)
[1] 孫利民,，李建中，陳渝,，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社,，2005：124-151.
[2] 余勇昌，韋崗.無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的 改進(jìn)算法[J].電子學(xué)報,，2008,，36(7)：1309-1313.
[3] SHAH R C，RABAEY J.Energy aware routing for low energy Ad hoc sensor networks[C].Orlando：IEEE Wireless Communications and Networking Conferenee(WCNC),，2002：350-355.
[4] 陶東.基于無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的仿真分析研究[J].現(xiàn)代電子技術(shù),，2011(12)：11.
[5] 王盛.基于NS2的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的改進(jìn)仿真研究[D].武漢：武漢理工大學(xué)，2010.
[6] 徐雷鳴.NS與網(wǎng)絡(luò)模擬[M].北京：人民郵電出版,，2003.