柴遠(yuǎn)波，賈宇飛，周明亮

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

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

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

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

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

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

2 LEACH協(xié)議

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

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

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

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

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

3）簇的建立

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

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

T（n）值計(jì)算如下:

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

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

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

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

圖1 LEACH路由協(xié)議拓?fù)浣Y(jié)構(gòu)Fig.1 Topology structure of LEACH routing protocol

LEACH算法特點(diǎn)：

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

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

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

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

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

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

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

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

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

下面是做出的一個(gè)簡(jiǎn)單模型圖。此圖為理想狀態(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é)點(diǎn)轉(zhuǎn)發(fā)信息模型Fig.3 WSNcluster head nodes forwarding informationmodel

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

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

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

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

4 結(jié) 論

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

[1]李巖，張曦煌，李彥中.LEACH-EE——基于LEACH協(xié)議的高效聚類路由算法[J].計(jì)算機(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ìn)及仿真[J].西安工業(yè)大學(xué)學(xué)報(bào)，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é)點(diǎn)能量管理系統(tǒng)的研究 [D].太原：太原理工大學(xué)，2010.

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

[5]王慧，陸曉希.基于LEACH協(xié)議的研究與改進(jìn)[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]張強(qiáng)，盧瀟，崔曉臣.基于能量高效的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，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.