非變換簇的WSN分簇路由算法.doc

非變換簇的WSN分簇路由算法 張巖 （西安文理學院信息工程學院，陜西西安710065） 摘要：針對LEACH算法簇頭選取及能量消耗方面的不足，提出一種基于能量、距離和節(jié)點度的分簇路由算法CMEDD，通過均勻分簇減少重建過程，對簇頭選舉公式進行改進，合理選擇簇頭，從而均衡節(jié)點能耗。采用基于代價因子的單跳和多跳相結(jié)合的方式建立最優(yōu)路徑進行數(shù)據(jù)傳輸。仿真結(jié)果表明，與LEACH算法和RMCRW算法相比，CMEDD算法能夠有效均衡節(jié)點能耗，可相對延長網(wǎng)絡(luò)生存周期。 關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；能耗均衡；簇頭選??；網(wǎng)絡(luò)生命周期 ：TN711?34；TP393：A：1004?373X（xx）18?0026?04 ：xx?03?25 基金項目：西安市科技計劃項目（CXY1443WL19）；國家自然科學基金資助項目（41301413） 無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點多采用能量有限的電池供電，使得整個網(wǎng)絡(luò)對數(shù)據(jù)的存儲處理和傳輸能力受到了限制。所以如何有效使用傳感器節(jié)點能量，以及如何延長網(wǎng)絡(luò)的生命周期就成為設(shè)計無線傳感器網(wǎng)絡(luò)路由協(xié)議的一個重點，其中從管理的角度上對網(wǎng)絡(luò)進行層次化管理是目前該領(lǐng)域的一個研究熱點。 文獻1提出了無線傳感網(wǎng)拓撲控制典型的低功耗自適應(yīng)算法LEACH，與平面拓撲算法相比，該協(xié)議可以延長網(wǎng)絡(luò)生命期約30%。但是LEACH算法沒有考慮能量不平衡問題，存在很大改進空間。 針對LEACH算法存在的問題，學者們提出一系列改進的算法2?7。文獻2?4均提出基于剩余能量的自適應(yīng)分簇算法，算法選擇剩余能量最大的節(jié)點作為簇頭，平衡能耗。文獻5提出了基于節(jié)點能量閾值的簇頭競爭算法，當簇頭節(jié)點的剩余能量值降低到特定閾值下時，算法就啟動新一輪簇的建立過程。文獻6利用節(jié)點到基站的距離作為簇頭選擇的權(quán)重對LEACH算法進行改進。文獻7LEACH?EI算法，考慮節(jié)點初始能量和當前能量2個因素，利用動態(tài)分簇的方式計算能量閾值，根據(jù)能量閾值選擇簇頭。文獻8ECRED算法通過引入備選簇頭減少簇的重建，用以降低簇頭選舉的能耗。文獻9RMCRW算法提出基于環(huán)的簇頭選舉方式，引入權(quán)值控制簇頭轉(zhuǎn)發(fā)路徑，達到節(jié)能目的。另外也有研究者將已有的一些優(yōu)化算法如遺傳算法、蟻群算法等應(yīng)用到路由算法的設(shè)計中，從而延長網(wǎng)絡(luò)壽命。 在深入研究無線傳感器網(wǎng)絡(luò)LEACH及其相關(guān)改進協(xié)議的基礎(chǔ)上，本文設(shè)計了一種基于能量、距離、節(jié)點度的算法（AClusterHeadMakeup?Energy?Distance?Densi?tyAlgorithmImprovedBasedonLEACHAlgorithm，CMEDD）。 1網(wǎng)絡(luò)模型 1.1本文采用的節(jié)點模型假設(shè)如下： （1）基站距離較遠且能量無限，位置不發(fā)生改變； （2）節(jié)點同構(gòu)且初始能量相等，一經(jīng)部署其位置不再發(fā)生改變； （3）節(jié)點發(fā)送功率可以進行調(diào)整，即具有調(diào)節(jié)無線收發(fā)器工作能耗的控制功能； （4）節(jié)點能夠支持多種MAC協(xié)議（如TDMA等）； （5）傳感器節(jié)點具有足夠的計算能力，即具有一定的數(shù)據(jù)融合功能。 1.2能耗模型 節(jié)點l位的數(shù)據(jù)包傳送長度為d，通信模型為9： 2CMEDD算法描述 2.1簇頭選擇 在分簇結(jié)構(gòu)的無限傳感器網(wǎng)絡(luò)中簇頭個數(shù)k是影響分簇路由算法網(wǎng)絡(luò)能耗的一個重要參數(shù)。CMEDD算法采用文獻10中簇頭個數(shù)k的取值算法。本算法規(guī)定首輪成簇及廣播工作由基站完成，基站按照最佳簇頭個數(shù)將網(wǎng)絡(luò)化分成k個虛擬網(wǎng)格，進而基站在每個網(wǎng)格內(nèi)隨機選取一個節(jié)點作為本簇的簇頭，同時生成一個鄰居列表消息Message_neighbour，并將此信息廣播給各自簇（網(wǎng)格）內(nèi)成員節(jié)點11?；竟急敬蔚男畔⑵ヅ渲埃泄?jié)點不知道自己所屬的簇區(qū)域，因此基站發(fā)布的Message_neighbour消息覆蓋范圍要確保網(wǎng)絡(luò)內(nèi)所有節(jié)點都能接收到。 基站可以從第1輪各簇頭發(fā)送的數(shù)據(jù)確定所有節(jié)點及基站之間的距離關(guān)系，為第2輪及以后的簇頭選舉提供必要數(shù)據(jù)。在經(jīng)過Nk輪的工作之后，由于各種隨機事件使得簇內(nèi)節(jié)點能量可能差異較大。為了均衡網(wǎng)絡(luò)能耗并延長其使用周期，在隨后的簇頭選舉中將綜合考慮到節(jié)點剩余能量、簇內(nèi)節(jié)點平均距離及節(jié)點距基站距離、節(jié)點度等三方面因素： （1）節(jié)點剩余能量 首先引入節(jié)點剩余能量參數(shù)E(n)： 式中:En(r)為節(jié)點n在r輪的剩余能量；Eeverage(r)為r輪時刻簇內(nèi)平均能量。則： 在每一輪的工作結(jié)束時，每個節(jié)點查看自身的En(r)值，并向簇頭報告，簇頭計算簇內(nèi)的平均能量值，并向簇內(nèi)廣播。 （2）簇內(nèi)節(jié)點平均距離及節(jié)點距基站距離 其次分析節(jié)點與簇內(nèi)其余節(jié)點以及與基站之間的距離參數(shù)D(n)： 式中：節(jié)點n坐標為(x,y)；(x)i,yi為簇內(nèi)其余節(jié)點的坐標值；(xtoBS),ytoBS為基站的坐標值；D1(n)為節(jié)點n到簇內(nèi)其余節(jié)點的距離之和；D2(n)為節(jié)點n到基站的距離，則： 在網(wǎng)絡(luò)運行中傳感器節(jié)點一經(jīng)部署其位置不會改變，因此每個節(jié)點的距離參數(shù)只需要計算1次。節(jié)點位置信息的傳遞是在簇建立過程中對能量消息的傳遞中一起進行的，從而減少了信息交互中的通信損耗。 （3）節(jié)點度析節(jié)點的度 節(jié)點為布爾感知模型12，即每個節(jié)點都具有一個固定的感知半徑R，其感知范圍是以節(jié)點為圓心，R為半徑的圓。簇內(nèi)處于某節(jié)點感知半徑內(nèi)的節(jié)點為此節(jié)點的一步通信節(jié)點。一步通信節(jié)點個數(shù)稱作節(jié)點的度Measure(n)。一步通信節(jié)點較多，即其周圍節(jié)點分布較為密集，則該節(jié)點當選簇頭的概率也應(yīng)隨之增大。節(jié)點的度調(diào)節(jié)參數(shù)M(n)的模型及約束條件如下： 各節(jié)點根據(jù)各項參數(shù)調(diào)整各自成為簇頭的閾值，經(jīng)過對比閾值較大者成為簇頭。 調(diào)整后的閾值公式為： 改進后的公式使得當前節(jié)點的剩余能量越大、節(jié)點到基站以及到其他節(jié)點之間的平均距離的關(guān)系參數(shù)越大，節(jié)點的度越大，則閾值T(n)越大，從而該節(jié)點當選為簇頭的幾率越大，反之當選為簇頭的幾率越小。 2.2簇間路由 網(wǎng)絡(luò)中的簇頭節(jié)點與普通節(jié)點一樣也有通信模型閾值dcrosscover，當傳輸距離小于此值時，其能耗與距離平方成線性關(guān)系。網(wǎng)絡(luò)中簇頭選取完畢則存在G=V,E，V=v1,v2,?,vk，V為簇頭集，E為可直接通信的兩節(jié)點間的通信能耗。則距離基站較遠的簇頭節(jié)點直接向基站發(fā)送數(shù)據(jù)能量會損失較快，不利于網(wǎng)絡(luò)能量均衡。CMEDD算法在簇頭向基站傳輸數(shù)據(jù)時，按照代價因子公式尋找下一跳中轉(zhuǎn)接點。 假定在網(wǎng)絡(luò)中vi,vj均為簇頭，則簇頭節(jié)點vj作為簇頭節(jié)點vi的下一跳中轉(zhuǎn)節(jié)點的代價因子為： 式中：E(i,j)E；E(v)j為簇頭節(jié)點vj的當前能量；sij為vi,vj之間距離，且sij?dcrosscover；Sj為vj到基站的距離，j=1,2,?,k。節(jié)點vi從屬于集合V并且與自身距離小于dcrosscover的節(jié)點中找到代價因子最小的節(jié)點vj，作為自己的下一跳中轉(zhuǎn)節(jié)點。vj再以同樣的方式找到自己的下一跳中轉(zhuǎn)節(jié)點，從而形成一條通向基站的通信鏈路。則vj可作為vi的中轉(zhuǎn)節(jié)點，vi向vj發(fā)送數(shù)據(jù)符合自由空間模型，通信鏈路上的總體能量消耗遠小于多路衰減模型。 3算法仿真與性能驗證 為了驗證CMEDD算法的有效性，對CMEDD，RMCRW和LEACH算法進行對比。仿真實驗在MatlabRxxa環(huán)境下進行，以隨機方式在監(jiān)測區(qū)域內(nèi)部署傳感器節(jié)點，假設(shè)節(jié)點分布在坐標為(0,0)到(100,100)的區(qū)域內(nèi)。仿真實驗使用參數(shù)取值分別為：N=100，M=100，數(shù)據(jù)包長度l=500，基站的坐標（50，175），Efs=10pJ，Eamp=0.0013pJ，節(jié)點初始能量E0=21010pJ，EDA=5103pJ，Eelec=50103pJ。 無線傳感器網(wǎng)絡(luò)的生命周期著重從首節(jié)點能量耗盡所用時間進行考慮?；谶@一原因?qū)嶒瀸W(wǎng)絡(luò)節(jié)點數(shù)分別為100，200時三種算法運行期間存活節(jié)點數(shù)進行仿真，其仿真圖分別如圖1，圖2所示。 如圖1所示，模擬環(huán)境與初始能量相同，100個節(jié)點時LEACH算法運行16輪，第17輪出現(xiàn)節(jié)點能量耗盡；RMCRW算法運行20輪，第21輪出現(xiàn)節(jié)點能量耗盡；而CMEDD算法運行22輪左右開始出現(xiàn)能量耗盡的節(jié)點。CMEDD算法首節(jié)點死亡輪數(shù)較LEACH算法延長了37.5%、較RMCRW算法延長了10.1%。說明同樣的運行時間，CMEDD算法節(jié)點能耗更低，并使節(jié)點能耗的分布更加均勻，即有效延長了節(jié)點的生存時間。由圖2可知，在各項參數(shù)保持不變的環(huán)境下，將節(jié)點數(shù)增至200，CMEDD，RMCRW和LEACH三種算法的首節(jié)點死亡輪數(shù)分別為31，28和23，即CMEDD算法首節(jié)點死亡輪數(shù)較LEACH和RMCRW分別提高了34.8%和10.7%。說明本算法對網(wǎng)絡(luò)密度具有較好的適應(yīng)性。綜合分析圖1，圖2可以看出，CMEDD算法節(jié)點生命曲線與LEACH和RMCRW相比較而言坡度較大，說明節(jié)點能耗更為均衡。 當網(wǎng)絡(luò)節(jié)點分別為100和200時，CMEDD算法與LEACH和RMCRW算法節(jié)點的能量消耗曲線如圖3，圖4所示。 分析圖3，圖4可知，初始階段三者能耗差別較小，但隨著運行輪數(shù)的增加，CMEDD算法的節(jié)點存活數(shù)目及平均能量逐漸高于LEACH和RMCRW算法，即CMEDD算法對網(wǎng)絡(luò)密度具有良好適應(yīng)性。 4結(jié)語 本文提出了基于能量、距離及節(jié)點度的非變換分簇的一種能耗均衡的路由算法（CMEDD）。算法給出了分簇方式、簇頭選擇公式及簇間路由形式，首輪由基站選擇簇頭，第2輪以后利用基于節(jié)點的剩余能量、節(jié)點到基站以及到其他節(jié)點之間的平均距離和節(jié)點的度3項參數(shù)的閾值公式選取簇頭；數(shù)據(jù)傳輸階段簇頭根據(jù)代價因子選擇中繼節(jié)點，從而實現(xiàn)單、多跳結(jié)合的路由方式，降低網(wǎng)絡(luò)能耗。仿真實驗及對比表明，CMEDD算法能夠有效均衡網(wǎng)絡(luò)能耗、延長網(wǎng)絡(luò)生命周期。 CMEDD算法在均衡網(wǎng)絡(luò)能耗方面有一定優(yōu)勢，但是仍然存在一些問題，如在網(wǎng)絡(luò)運行中簇頭進行數(shù)據(jù)融合的高效性以及在較大網(wǎng)絡(luò)中算法的安全性和可擴展性都有待進一步的研究。 參考文獻 1HEINZELLNANWB，CHANDRAKASANAP，BALAKRISH?NANH.Anapplication?specificprotocolarchitectureforwire?lessmicrosensorworksJ.IEEETransactionsonWirelessCommunications，xx，1（4）：660?670. 2KUBISCHM，KARLH，WOLISZA，etal.Distributedalgo?rithmfortransmissionpowercontrolinwirelesssensor?worksC/ProceedingsofthexxIEEEWirelessCommunica?tionsNetworking.Washington，USA：IEEECommunicationsSo?ciety，xx：16?20. 3BAIL，ZHAOL，LIAOZ.Energybalanceincooperativewire?lesssensorworksC/Proceedingsofthe14thEuropeanwirelessconference.Prague，CzechRepublic：IEEE，xx：143?145. 4LIYL，DINGLW，LIUF.TheimprovementofLEACHproto?colinWSNC/ProceedingsofthexxInternationalConferenceonComputerScienceandNetworkTechnology.Harbin，Chi?na：IEEE，xx：1345?1348. 5AKYILDIZIF，SANKARASUBRAMANIAMY，SUW，etal.AsurveyonsensorworksJ.ProcIEEECommunicationsMagazine，xx，40（8）：102?114. 6ENAMIN，MOGHADAMRA，DADASHTABARK.Neuralworkbasedenergyefficiencyinwirelesssensorworks：AsurveyJ.InternationalJournalofComputerScience&Engi?neeringSurvey，xx：1（1）：39?53. 7白鳳娥，王莉莉，馬艷艷，等.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的算法分析J.太原理工大學學報，xx，40（4）：348?352. 8張詩悅，吳建德，王曉東，等.一種能耗均衡的無線傳感器網(wǎng)絡(luò)分簇路由算法J.計算機工程，xx，40（8）：6?9. 9魯松，徐文春，楊云.一種分環(huán)多跳的無線傳感器網(wǎng)絡(luò)分簇路由加權(quán)算法J.山東大學學報：工學版，xx，42（4）：24?28. 10CHANDRAKASANA，REXM，BHARDWAJM，etal.Pow?erawar