柴遠波，賈宇飛，周明亮

（黃河科技學(xué)院 河南 鄭州 450063）

1 網(wǎng)絡(luò)層路由協(xié)議

在無線傳感器網(wǎng)絡(luò)系統(tǒng)網(wǎng)絡(luò)中，網(wǎng)絡(luò)層上的路由技術(shù)對無線傳感器系統(tǒng)網(wǎng)絡(luò)的性能有非常重要的影響。隨著國內(nèi)外對無線傳感器網(wǎng)絡(luò)的研究發(fā)展，許多針對無線傳感器的路由協(xié)議被提出來。在網(wǎng)絡(luò)拓撲的結(jié)構(gòu)看法上，我們可以把這些路由協(xié)議分分成兩大類，平面路由協(xié)議和層次路由協(xié)議。

在平面路由這一類協(xié)議中，它的所有網(wǎng)絡(luò)節(jié)點地位都是一樣的。在等級上和層次上不存在差異。它們能夠在局部操作和信息反饋相互之間的數(shù)據(jù)傳輸來生成路由。在這一類的協(xié)議中，其中目的節(jié)點（source）首先發(fā)出去查詢命令，通過在檢測區(qū)域的節(jié)點收到查詢的命令后，在去向目的節(jié)點發(fā)送監(jiān)測的數(shù)據(jù)。

其中平面路由優(yōu)點主要是：簡單、易擴展性，不需要進行結(jié)構(gòu)維護、所有節(jié)點地位一樣，基本不產(chǎn)生瓶頸效應(yīng)、有較好的健壯性。DD（Directed Diffusion）、SAR（Sequential Assignment Routing）、SPIN（Sensor Protocolsfor Informationvia Negotiation）、Romor Routing等這些都是典型的平面路由算法。平面路由目前的缺點：由于各節(jié)點地位平等，不存在管理節(jié)點。無法對通信資源進行優(yōu)化的管理，自組織協(xié)同方面的算法也較為復(fù)雜，應(yīng)對網(wǎng)絡(luò)的動態(tài)變化反應(yīng)速度也比較慢。在分簇路由這方面協(xié)議中，網(wǎng)絡(luò)是被劃分成簇（cluster）的。簇就是具有某種關(guān)聯(lián)的各網(wǎng)絡(luò)節(jié)點集合。每一個的簇都是有一個簇頭（clusterhead）與多個簇內(nèi)的成員（clustermember）構(gòu)成，低一級網(wǎng)絡(luò)的簇頭是比它高一級的簇內(nèi)成員，其中最高層的簇頭與基站BS（basestation）通信。這一類的算法是將整個網(wǎng)絡(luò)劃分成相連的區(qū)域。在這種分簇拓撲的管理機制下，可以網(wǎng)絡(luò)中的節(jié)點劃分成簇頭節(jié)點和成員節(jié)點。在一個簇內(nèi)，是根據(jù)某一些機制算法來選取簇頭節(jié)點，用來管理整個簇內(nèi)的成員節(jié)點和協(xié)調(diào)成員節(jié)點之間的工作，簇頭節(jié)點負責(zé)簇內(nèi)信息的收集和數(shù)據(jù)的融合處理以及簇之間的轉(zhuǎn)發(fā)。LEACH是最早提出的應(yīng)用在無線傳感器網(wǎng)絡(luò)中分簇路由協(xié)議。它的這種成簇思想給后來的很多分簇路由協(xié)議提供了寶貴的思想，例如TEEN協(xié)議和HEED協(xié)議等。

本文提出的是基于LEACH算法的多跳路由算法，采用簇頭之間多跳算法，而簇頭節(jié)點的選取可根據(jù)節(jié)點能量剩余情況。盡量選取能量較高的簇頭節(jié)點把信息傳遞到基站。均衡地消耗節(jié)點能量。從而延長網(wǎng)絡(luò)生存時間[2]。

2 LEACH協(xié)議

LEACH協(xié)議的全稱是 “低功耗自適應(yīng)集簇分層次型路由協(xié)議”（Low Energy Adaptive Clustering Hierarchy）， 它是國外科學(xué)家來為無線傳感網(wǎng)設(shè)計的低功耗自適應(yīng)分層路由算法。LEACH這種算法的基本原理就是在運行過程中不斷用循環(huán)這種方式執(zhí)行簇的重構(gòu) ，它是根據(jù)網(wǎng)絡(luò)中節(jié)點能量剩余的不同情況，動態(tài)地去選擇集中式或者是分布式分簇算法，這樣可以有效地延長整個網(wǎng)絡(luò)的生命周期，同時也考慮到了網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化，從而保證了整個網(wǎng)絡(luò)的穩(wěn)定性。經(jīng)過系統(tǒng)仿真實驗表明，LEACH的網(wǎng)絡(luò)生命周期比一般的平面多跳路由協(xié)議和靜態(tài)分層算法長15%。

LEACH在運行的過程中是不間斷循環(huán)去執(zhí)行簇的重新建立過程。每一個簇的重新建立過程都可以用“輪（round）”的概念來描述它。每個輪是劃分成兩個階段，分別是：每個簇的建立階段與傳輸數(shù)據(jù)的穩(wěn)定階段。為了去節(jié)省資源的開銷，要求穩(wěn)定階段的持續(xù)時間要高于簇建立階段的持續(xù)時間。其中又可以把簇的建立分成4個階段:

(4)對熱點學(xué)科進行分析，發(fā)現(xiàn)臨床醫(yī)學(xué)主要研究內(nèi)容集中在護理上，腫瘤學(xué)主要研究類型涉及鼻咽癌、肝細胞癌、肺腫瘤、乳腺癌、鼻咽腫瘤、肝癌、肺癌、乳腺腫瘤、胃癌、肝腫瘤、非小細胞肺癌等，中藥學(xué)主要研究藥物成分以及細胞增殖與凋亡；

1）簇頭節(jié)點的選擇

2）簇頭節(jié)點的廣播

3）簇的建立

4）調(diào)度機制的生成

簇頭節(jié)點的選擇是根據(jù)整個系統(tǒng)網(wǎng)絡(luò)中需要的簇頭節(jié)點的總數(shù)和目前為止每一個節(jié)點成為簇頭的次數(shù)來決定。選擇的具體辦法是：每一各節(jié)點都選擇0到1間的一個值，如果選的值大于閾值T（n），則這個節(jié)點成為簇頭節(jié)點。

T（n）值計算如下:

式（1）中的p是網(wǎng)絡(luò)中簇頭總數(shù)占總節(jié)點數(shù)的百分比值；r是代表目前選舉輪數(shù)；G是最近1/p輪沒有成為簇頭的節(jié)點集。

定下簇頭這個節(jié)點后，是通過廣播的方式來告之整個網(wǎng)絡(luò)。網(wǎng)絡(luò)中的其他節(jié)點根據(jù)接收到的信號強度去判定屬于哪個簇，然后去通知相對應(yīng)的簇頭節(jié)點來完成簇的建立。到最后，簇頭節(jié)點采用是TDMA方法去為簇中的每一個節(jié)點來分配向其傳送數(shù)據(jù)時間片。

在穩(wěn)定階段中，普通節(jié)點把采集到的數(shù)據(jù)發(fā)送到簇頭節(jié)點。簇頭節(jié)點對所有普通節(jié)點采集的數(shù)據(jù)進行融合后再傳送到基站，這種方法可以減少通信業(yè)務(wù)量，是一種合理的工作模式。

穩(wěn)定階段持續(xù)一定的時間后，整個網(wǎng)絡(luò)又重新進入到簇的建立階段，去進行下一輪簇的重新構(gòu)成，這樣來不斷的循環(huán)。每個簇用的是不同的CDMA代碼進行通信去減少其他簇里面的節(jié)點干擾。

圖1 LEACH路由協(xié)議拓撲結(jié)構(gòu)Fig.1 Topology structure of LEACH routing protocol

LEACH算法特點：

1）數(shù)據(jù)聚合度高：簇頭節(jié)點融合并篩選來自于簇內(nèi)不同源節(jié)點所產(chǎn)生的數(shù)據(jù)，并將數(shù)據(jù)發(fā)送到基站，避免了數(shù)據(jù)的重復(fù)冗雜，有效的減少通信量，減小了能耗，提高了網(wǎng)絡(luò)的生存時間可以對系統(tǒng)變化作出快速反應(yīng)；

2）高效的數(shù)據(jù)沖突解決機制：LEACH采用基于TDMA/CDMA的MAC層機制來減少簇內(nèi)和簇間的沖突；

3）保持通信量負載平衡：通過更加靈活地使用路由策略讓各個節(jié)點分擔(dān)數(shù)據(jù)傳輸，平衡節(jié)點的剩余能量，提高整個網(wǎng)絡(luò)的生存周期。例如，可在層次路由中采用動態(tài)的簇頭[3]。

3 簇頭節(jié)點信息的轉(zhuǎn)發(fā)路徑

基于LEACH算法提出簇頭節(jié)點之間形成多跳路由，在根據(jù)簇頭節(jié)點的能量剩余情況選擇選擇傳遞信息的簇頭節(jié)點。最后選取一個簇頭節(jié)點把信息傳遞給基站。這種可稱為LEACH——DE。

現(xiàn)在根據(jù)簇頭節(jié)點剩余情況劃分。設(shè)定兩個臨界值分別為a，b將簇頭節(jié)點劃分為3個能量狀態(tài)。

（1）正常值：簇頭節(jié)點能量剩余大于a，能量充足?？蛇M行信息的發(fā)送和轉(zhuǎn)發(fā)。

（2）偏低值：簇頭節(jié)點能量剩余大于a小于b。一般只需要進行信息的發(fā)送。

（3）危險值：簇頭節(jié)點能量剩余小于b。此時應(yīng)考慮更換簇頭（其他節(jié)點代替）[4]。

下面是做出的一個簡單模型圖。此圖為理想狀態(tài)下。

圖2 基于LEACH協(xié)議的高效聚類路由算法的數(shù)據(jù)傳輸和聚合過程Fig.2 Based on data transmission and efficient clustering routing algorithm of LEACH protocolandthe polymerization process

圖3 WSN簇頭節(jié)點轉(zhuǎn)發(fā)信息模型Fig.3 WSNcluster head nodes forwarding informationmodel

A，B，C，D，E，F(xiàn) 簇頭節(jié)點，都需要把信息發(fā)送到基站。 有圖可知C點能量大于F點能量。而此時這些根據(jù)上述所提到的把所有簇頭節(jié)點需要轉(zhuǎn)發(fā)的信息轉(zhuǎn)發(fā)到一個簇頭節(jié)點上。由于在無線通信中，能量消耗E與通信距離d存在關(guān)系:

其中k表示一個常量，n是無線產(chǎn)品或者站點能量和站點之間的一個常量系數(shù)，這個值不是一個確定的值，根據(jù)不同的產(chǎn)品這個值有大有小，2≤n≤4。由于傳感器網(wǎng)絡(luò)中節(jié)點一般都是貼近地面的，應(yīng)用環(huán)境中可能有很多的障礙物，導(dǎo)致接收天線的接受能力也有限，n這個值接近于4?？芍跓o線通信中，能量的消耗E與距離四次方成正比。因此隨著通信距離的增加，能量消耗E將會急劇的增加。為了降低能量的消耗應(yīng)該盡量減小單跳通信距離的增加。其中多個短距離跳的數(shù)據(jù)傳輸比一個長跳的傳輸能耗會低些，所以要盡量使用多跳的無線通信方式[5]。

有上述可知應(yīng)選取F點或者C點接受所有節(jié)點轉(zhuǎn)發(fā)過來的信息然后發(fā)送到基站。假設(shè)各節(jié)點信息都轉(zhuǎn)發(fā)到F點。但F點節(jié)點能量偏低。在轉(zhuǎn)發(fā)有限的次數(shù)將要“死亡”。這就不利于網(wǎng)絡(luò)的生存。假設(shè)選取C點，C點能量充足。轉(zhuǎn)發(fā)的次數(shù)遠大于F點。這樣就延長了網(wǎng)絡(luò)的生存時間。這個簡單模型驗證了選取能量過高的簇頭節(jié)點去轉(zhuǎn)發(fā)所有簇頭節(jié)點的信息?？纱蟠笤黾泳W(wǎng)絡(luò)生存時間。

在以E為例說明，在E簇頭節(jié)點要把信息轉(zhuǎn)發(fā)到基站?，F(xiàn)在有兩條鏈路選擇，一條為E——B——C在到基站，另一條為E——F——C在到基站。 其中E——F——C到基站鏈路中有F簇頭節(jié)點能量處于偏低狀態(tài)。如果F簇頭節(jié)點過多的轉(zhuǎn)發(fā)信息，將導(dǎo)致能量很快用盡，這就不利于整個網(wǎng)絡(luò)的生存。只讓F點發(fā)送自身信息轉(zhuǎn)發(fā)到下一個簇頭節(jié)點，這樣相對而言可以延長網(wǎng)絡(luò)的生存時間。

4 結(jié) 論

本文提出的LEACH——DE算法是在李巖先生基礎(chǔ)上提出。在LEACH算法中，簇頭的選擇是以輪的方式進行，能夠可以均衡的消耗各網(wǎng)絡(luò)節(jié)點的能量。但是如果只是在簇頭節(jié)點傳遞到基站上按貪心算法進行。是無法考慮到節(jié)點固有能量剩余的問題。當(dāng)簇頭節(jié)點間傳遞信息以多跳方式進行，能夠很快的使數(shù)據(jù)傳送到基站。在以LEACH——DE算法顧及到簇頭節(jié)點能量偏低狀態(tài)，避免轉(zhuǎn)發(fā)信息。可以使能量偏低的節(jié)點延長生存時間。在整個網(wǎng)絡(luò)節(jié)點上考慮，優(yōu)先使用能量充足的簇頭節(jié)點?？梢赃_到均衡消耗網(wǎng)絡(luò)節(jié)點能量[6]。

[1]李巖，張曦煌，李彥中.LEACH-EE——基于LEACH協(xié)議的高效聚類路由算法[J].計算機應(yīng)用，2007（5）:1103-1105.LIYan，ZHANG Xi-huang，LIYan-zhong，LEACH-EE.efficient clusteringrouting algorithm of LEACH protocol[J].Computer Application，2007（5）:1103-1105.

[2]韋宏利，方玉杰.LEACH協(xié)議算法改進及仿真[J].西安工業(yè)大學(xué)學(xué)報，2010，30（6）:570-573.WEIHong-li，F(xiàn)ANG Yu-jie.Improvement and simulation of LEACH protocol algorithm[J].Journal of Xi’an Technological University，2010，30（6）:570-573.

[3]趙清華.無線傳感器節(jié)點能量管理系統(tǒng)的研究 [D].太原：太原理工大學(xué)，2010.

[4]孫麗莉.無線傳感器節(jié)點能量管理技術(shù)研究[D].廣州：華南理工大學(xué)，2009.

[5]王慧，陸曉希.基于LEACH協(xié)議的研究與改進[J].火力與指揮控制，2010（4）:124-127.WANG Hui，LU Xiao-xi.Researchand improvement based on LEACH protocol[J].Fire and Command Control，2010（4）:124-127.

[6]張強，盧瀟，崔曉臣.基于能量高效的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議改進[J].計算機工程與設(shè)計，2011（2）:427-429.ZHANG Qiang，LU Xiao，CUI Xiao-chen.Improved energy efficient LEACH protocol in wireless sensor network based on[J].Computer Engineering and Design，2011（2）:427-429.