潘雪峰，李臘元，，何延杰

（1.武漢生物工程學(xué)院 計算機(jī)與信息工程系，湖北 武漢430415；2.武漢理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢430063）

0 引 言

無線傳感器網(wǎng)絡(luò)的應(yīng)用較為廣泛，其中一個重要的研究方向就是路由協(xié)議的研究與分析［1］。路由協(xié)議對無線通信模塊的能量消耗起著關(guān)鍵影響。路由協(xié)議的研究一般放在路由機(jī)制和數(shù)據(jù)驅(qū)動上，由此劃分了階段，并出現(xiàn)了一些優(yōu)秀的路由算法［2－3］。

針對LEACH協(xié)議和PEGASIS協(xié)議的不足，給出了改進(jìn)方案。在簇首選取的過程中經(jīng)過公式推導(dǎo)，找出最優(yōu)簇首的數(shù)量與參數(shù)間的關(guān)系；簇的建立的過程中給出了算法流程；并對簇間路由中路由樹建立的過程進(jìn)行了描述。最后使用NS2.27進(jìn)行了仿真，并給出了數(shù)據(jù)分析及結(jié)論。

1 具有代表性的無線傳感器網(wǎng)絡(luò)路由協(xié)議的分析

無線傳感器網(wǎng)絡(luò)路由協(xié)議所包含內(nèi)容較多，但其核心內(nèi)容是選擇簇首節(jié)點、形成簇、簇間數(shù)據(jù)的路由［4－5］。分簇方式種類較多，一個簇能夠使用不同的數(shù)據(jù)交換方式［6］。同時，由于選擇簇首節(jié)點機(jī)制的不同，算法也不同［7－8］。課題分析研究了兩種典型的層次路由協(xié)議，它們屬于分布式算法。

1.1 LEACH協(xié)議 （低功耗自適應(yīng)簇分層型協(xié)議）

在LEACH協(xié)議中，形成簇時使用自我組織、自動適應(yīng)性、隨機(jī)選擇的機(jī)制［9］。圖1描述了無線傳感器網(wǎng)絡(luò)中的節(jié)點分為5個簇，使用的是LEACH協(xié)議，圖中簇首節(jié)點用黑色圓圈表示，非簇首節(jié)點用白色圓圈表示。協(xié)議隨機(jī)選擇簇首節(jié)點，使每個傳感器節(jié)點平均分配了整個網(wǎng)絡(luò)的能量消耗［10］。

圖1 低功耗自適應(yīng)簇分層型協(xié)議的簇結(jié)構(gòu)

低功耗自適應(yīng)簇分層型協(xié)議的執(zhí)行過程是周而復(fù)始的，每一個周期又分為很多輪，每輪中簇首的選擇是隨機(jī)的［11－12］。簇建立階段和穩(wěn)定傳輸階段是一輪中的兩個重要組成部分。

從以上分析看出LEACH協(xié)議具有以下不足：①使用簇首節(jié)點隨機(jī)輪換法雖然能降低能量消耗，但反復(fù)重建簇還是會消耗更多的能量；②不同的簇內(nèi)，簇首節(jié)點與非簇首節(jié)點的距離各不相同，通信過程中簇首的能量消耗增多；③由于簇首節(jié)點需要與匯聚節(jié)點通信、完成數(shù)據(jù)融合等工作，能量消耗增多。

1.2 PEGASIS協(xié)議

PEGASIS協(xié)議在進(jìn)行鏈接時，節(jié)點采用鏈?zhǔn)浇Y(jié)構(gòu)。使用PEGASIS協(xié)議時，首先根據(jù)接收的信號的強(qiáng)度，區(qū)分鄰居節(jié)點距離的遠(yuǎn)近，在尋找距離最近鄰居的時，為了使信號僅有該鄰居接收，還要調(diào)整發(fā)送信號的強(qiáng)度。接下來，每個節(jié)點向鏈路中鄰居節(jié)點發(fā)送隨機(jī)數(shù)據(jù)，并且只選擇一個節(jié)點作為鏈?zhǔn)紫騾R聚節(jié)點傳輸數(shù)據(jù)［13－15］。

從以上分析看出PEGASIS協(xié)議有以下不足：①協(xié)議設(shè)計鏈路過于理想化，將匯聚節(jié)點與簇首節(jié)點通信時，能夠直接通信，在實際情況中，簇首節(jié)點需要用多跳的方式與匯聚節(jié)點通信；②協(xié)議對各節(jié)點能量的設(shè)計有所不足，假定它們的能量基本相當(dāng)，在能量耗盡的情況下，它們可能會全部脫離網(wǎng)絡(luò)或在網(wǎng)絡(luò)中消失；③協(xié)議對拓?fù)浣Y(jié)構(gòu)的設(shè)計有所不足，節(jié)點要獲取周圍節(jié)點的狀態(tài)及能量，這樣便于收發(fā)數(shù)據(jù)，但拓?fù)浣Y(jié)構(gòu)同時也會受到影響；④設(shè)計協(xié)議時，未引入備用鏈?zhǔn)坠?jié)點，鏈路如果過長，就會產(chǎn)生數(shù)據(jù)發(fā)送接收的滯后。

2 EBLP協(xié)議的設(shè)計

2.1 改進(jìn)切入點

通過對低功耗自適應(yīng)簇分層型協(xié)議和低功耗傳感器信息系統(tǒng)協(xié)議的分析，找出這兩個協(xié)議的不足，從選擇簇首節(jié)點、形成簇、簇間路由等方面對LEACH協(xié)議進(jìn)行了改進(jìn)。給出了以下改進(jìn)的切入點：①減少簇重組次數(shù)，從而降低了簇多次反復(fù)形成而損失的能量；②改變選擇簇首節(jié)點的算法，考慮決定能耗的參數(shù)的影響和減小簇首節(jié)點之間的距離；③調(diào)整簇和簇成員的個數(shù)，使得簇首的負(fù)載均衡，簇的劃分合理；④在建立路由樹的過程中，要考慮簇首節(jié)點與匯聚節(jié)點的距離遠(yuǎn)近，還要考慮簇首節(jié)點的能量，簇首節(jié)點采用多跳通信的方式，可以解決一些簇首節(jié)點因離匯聚節(jié)點過遠(yuǎn)，在采用單跳收發(fā)數(shù)據(jù)時，消耗能量太大的問題。

2.2 具體描述

2.2.1 簇首選取

在LEACH協(xié)議中選取簇首時，存在著一定的不足，由于簇首是在簇內(nèi)選取出來，所處的位置相對不固定，如果簇首節(jié)點位置相對集中，某些節(jié)點會被孤立，出現(xiàn)未被分到任何簇中的情況，這時候網(wǎng)絡(luò)就會局部不連通。與此同時，簇首節(jié)點位置相對集中，還會使系統(tǒng)內(nèi)部重復(fù)數(shù)據(jù)過多，收發(fā)這些數(shù)據(jù)需要更多的能量，如果能減少這些重復(fù)的數(shù)據(jù)，就能在降低能耗。設(shè)計的EBLP算法近似求出簇首節(jié)點個數(shù)較為合理的值，結(jié)合無線傳感器網(wǎng)絡(luò)中的節(jié)點分布、規(guī)模大小，求出簇首節(jié)點之間間隔的最小值，然后根據(jù)式 （1）中改進(jìn)后的閾值T （n）來選擇簇首。

式中：p——選為簇首的節(jié)點占所有總節(jié)點數(shù)的百分比，r——所經(jīng)歷的輪數(shù)，rs——一直沒被選為簇首的輪數(shù)，En＿current——當(dāng)前能量，En＿initial——初始能量。如果節(jié)點被選為簇首，rs便重置為0。

簇首節(jié)點消耗的能量會受到各種因素的影響，由于簇首節(jié)點的主要工作是與匯聚節(jié)點、簇內(nèi)節(jié)點進(jìn)行通信，因而簇首節(jié)點的能耗主要用于與簇內(nèi)成員進(jìn)行數(shù)據(jù)收發(fā)消耗的能量 （N／K－1）Eelec，以及與匯聚節(jié)點通信消耗的能量（Eelec＋εamp（）），其中簇的數(shù)量用K表示，接收或發(fā)送數(shù)據(jù)所需的能量用Eelec表示，簇首節(jié)點到匯聚節(jié)點的距離用dtoBS表示，簇首與匯聚節(jié)點通信時的無線信號傳播參數(shù)為εamp。簇內(nèi)成員節(jié)點在一輪中消耗的能量EnonCH為：（Eelec＋εfsE（）），其中成員節(jié)點到簇首節(jié)點的距離用dtoCH表示，成員與簇首通信時的無線信號傳播參數(shù)為εfs。在一輪中每個簇消耗的能量Ecluster包括兩部分，分別是一個簇首所需能量ECH，及簇內(nèi)成員所需能量 （N／K－1）EnonCH。因此在一輪中K個簇消耗的能量的累加和可使用全網(wǎng)消耗的能量Etotal來表示，代入前面的表達(dá)式后可得到：Etotal＝KEcluster＝K （N／K－1） （2Eelec＋εfsE））＋ （KEelec＋KεampE（））；考慮到K的值較大，那么K－1的值驅(qū)近于K的值，即可得到

假設(shè)模擬區(qū)域為正方形區(qū)域，其邊長為A，則無線傳感器網(wǎng)絡(luò)覆蓋的面積是A2，很容易得到，網(wǎng)絡(luò)中的一個簇得到的平均面積應(yīng)是A2／K。簇內(nèi)非簇首節(jié)點分布于簇首節(jié)點周圍，構(gòu)成一個圓形，得到半徑為r＝A／的圓，根據(jù)半徑的值能夠算出圓心與圓內(nèi)的點的距離平方的平均值，即數(shù)學(xué)期望為：E （） ＝ A2／2Kπ，同時，E（）與K無關(guān)，將其用常量L表示，因此式 （2）可變?yōu)?/p>

為了求出Etotal的最小值，對式 （3）左右兩邊同時對K求導(dǎo)數(shù)，令結(jié)果為0，這時就可以求出最優(yōu)的K值

通過推導(dǎo)出的式 （4）找出結(jié)論：Kopt與N、A、dtoBS有關(guān)。為得到最優(yōu)簇首數(shù)，可在設(shè)置網(wǎng)絡(luò)時設(shè)置時，給出這幾個具體的參數(shù)值。

2.2.2 簇的建立

當(dāng)選取好簇首節(jié)點之后，為了建立簇，簇首會向周圍的非簇首節(jié)點發(fā)出簇首特有的信號，周圍的非簇首節(jié)點對接收到的信號的強(qiáng)弱進(jìn)行判斷，一般加入信號強(qiáng)的簇首節(jié)點的那一簇中，并控制節(jié)點加入的數(shù)量，控制簇的大小。如果簇首同意周圍的非簇首節(jié)點加入簇中，會向該非簇首節(jié)點發(fā)送允許加入的信號，否則就發(fā)送拒絕加入信號。待簇建立完成，通過一條鏈路將簇首和成員節(jié)點鏈接，鏈接是采用貪婪算法，鏈的形成過程與PEGASIS協(xié)議相同。這樣一來，在每個簇中的節(jié)點數(shù)會比要比整個網(wǎng)絡(luò)中的節(jié)點少很多，傳輸?shù)奈恢眯畔⒁蚕鄬^少，使得傳輸數(shù)據(jù)的延遲也不很明顯。

2.2.3 簇間路由

匯聚節(jié)點一般在無線傳感器網(wǎng)絡(luò)外部，與無線傳感器網(wǎng)絡(luò)所在的區(qū)域有一定的距離，在簇首節(jié)點都與匯聚節(jié)點進(jìn)行數(shù)據(jù)交互的過程中，根據(jù)前面的推導(dǎo)，系統(tǒng)中節(jié)點的能耗將與它們之間距離的四次方成正比。在設(shè)計LEACH協(xié)議時，有著一定的不足，體現(xiàn)在簇間路由中，就是簇首在與匯聚節(jié)點進(jìn)行信息交換時，對簇首的當(dāng)前能量考慮不足，簇首可能會因能量損耗過快，能量耗盡而停止工作。為了解決上述的不足，同時還要考慮離匯聚節(jié)點較遠(yuǎn)的簇首的能耗，在設(shè)計EBLP協(xié)議時，采用了多跳的方式，由此只需少量的簇首與匯聚節(jié)點直接通信。

簇首間層次路由樹的建立過程如圖2所示，其中M為匯聚節(jié)點，A、B、C、D均為無線傳感器網(wǎng)絡(luò)中的簇首節(jié)點。①M首先向整個WSN發(fā)出一個消息，能量設(shè)為∞，設(shè)置跳數(shù)為0。②收到這個消息的簇首，加上匯聚節(jié)點一起構(gòu)造路由樹，路由樹中的根節(jié)點是匯聚節(jié)點，路由樹中葉子節(jié)點是簇首節(jié)點，將自身的剩余能量的值保存為包中的能量值，將收到的數(shù)據(jù)包經(jīng)過的跳數(shù)值增加1，并轉(zhuǎn)發(fā)此廣播包給周圍的簇首。③由于B、C兩個簇首節(jié)點距離近，B會先收到來自于C的廣播包 （1，EC），后收到來自于A的廣播包 （1，EA）。但是由于A、C兩節(jié)點剩余能量不同，且EA＞EC，雖然兩者的跳數(shù)值都為1，但是節(jié)點B會選擇剩余能量較大的節(jié)點作為其父節(jié)點，因此構(gòu)造路由樹時，節(jié)點A是節(jié)點B的父節(jié)點。依照上述規(guī)則可構(gòu)造出路由樹的結(jié)構(gòu)。

圖2 簇首間路由樹

3 仿真實驗和結(jié)果分析

3.1 仿真環(huán)境

為了驗證EBLP協(xié)議的有效性，在Linux下進(jìn)行仿真實驗，實驗環(huán)境為：NS2.27。選取99m＊99m的正方形區(qū)域為仿真實驗區(qū)域，在仿真區(qū)域中隨機(jī)地分布著99個節(jié)點，設(shè)置匯聚節(jié)點位置在坐標(biāo) （59，179）處。如圖3所示。

圖3 EBLP算法的網(wǎng)絡(luò)拓?fù)?/p>

3.2 設(shè)置仿真參數(shù)

在測試EBLP協(xié)議的仿真前，應(yīng)構(gòu)建仿真環(huán)境、設(shè)置仿真參數(shù)，以上工作需要寫入腳本文件。主要腳本如下：

.／ns tclfile／eblp／wsn.tcl－sc setting／nodescen

－rp eblp＼

－x 99＼

－y 99＼

－nn 99＼

－stop 1200

－eq＿energy 1 ＼－init＿energy 2＼－filename result－bs＿x 59＼－bs＿y 179＼

3.3 仿真結(jié)果及分析

3.3.1 最優(yōu)簇首數(shù)的仿真

在無線傳感器網(wǎng)絡(luò)區(qū)域中，在 （59，99）和 （0，0）的位置的簇首結(jié)點，距離匯聚節(jié)點 （59，179）的距離dtoBS的值分別是80至188.4，同樣也選取99m＊99m的正方形區(qū)域為仿真實驗區(qū)域，在仿真區(qū)域中隨機(jī)地分布著99個節(jié)點，εfs為10pJ／bit／m2將，εamp為0.0013pJ／bit／m4，將以上參數(shù)代入網(wǎng)絡(luò)最優(yōu)簇首個數(shù)的計算式 （4）中，可得最優(yōu)簇首數(shù)的值在2到5.5間。仿真后，得出了簇首數(shù)目與平均每輪能耗的關(guān)系如圖4所示。

圖4 簇首數(shù)與能耗的關(guān)系

3.3.2 能量消耗的仿真

在圖5中可以看到全網(wǎng)的能耗的比較，可以看出：實線為EBLP協(xié)議，兩條虛線分別是LEACH協(xié)議和PEGASIS協(xié)議；在網(wǎng)絡(luò)在前180輪，使用EBLP協(xié)議的無線傳感器網(wǎng)絡(luò)能耗高于LEACH和PEGASIS；在180輪后，使用EBLP協(xié)議的無線傳感器網(wǎng)絡(luò)能耗略低于LEACH和PEGASIS。

根據(jù)圖5可以得出以下結(jié)論：由于EBLP協(xié)議要進(jìn)行簇首選擇、簇的建立和簇間路由樹的建立，而該過程都與簇首有關(guān)，其它非簇首節(jié)點協(xié)同工作，因此前180輪EBLP協(xié)議消耗的能量較多；但是網(wǎng)絡(luò)運行穩(wěn)定后，由于簇間使用了路由樹來多跳通信，能量消耗相對較少。

4 結(jié)束語

通過對LEACH協(xié)議和PEGASIS協(xié)議進(jìn)行了重點的分析，總結(jié)出這兩種協(xié)議各自的優(yōu)缺點，針對LEACH協(xié)議生成非均勻的簇造成能量損耗的問題，以降低能量損耗為研究目的，結(jié)合PEGASIS協(xié)議的特點，從選擇簇首節(jié)點、形成簇、簇間路由等方面對LEACH協(xié)議進(jìn)行了改進(jìn)。經(jīng)過理論分析和仿真實驗，對該協(xié)議的性能進(jìn)行測試。可以得出結(jié)論，整個無線傳感器網(wǎng)絡(luò)的能量消耗上，EBLP路由算法要優(yōu)于LEACH協(xié)議和PEGASIS協(xié)議。

圖5 全網(wǎng)能耗比較

［1］LI Shuhua，LIU Zhenyu，LI Yingqiu.Energy adaptive clustering in wireless sensor network routing protocol［J］.Computer Engineering and Design，2010，31 （3）：504－507 （in Chinese）.［李樹華，劉振宇，李迎秋.能量自適應(yīng)的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議 ［J］.計算機(jī)工程與設(shè)計，2010，31 （3）：504－507.］

［2］LI Chengfa，CHEN Guihai，YE Mao，et al.A clustering based on non－uniform routing protocol for wireless sensor networks ［J］.Journal of Computers，2007，30 （1）：27－36 （in Chinese）.［李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議 ［J］.計算機(jī)學(xué)報，2007，30（1）：27－36.］

［3］GONG Haigang，LIU Ming.DEED：A wireless sensor network energy－efficient data communication protocol ［J］.Chinese Journal of Electronics，2005，33 （8）：1392－1396 （in Chinese）.［龔海剛，劉明.DEED：一種無線傳感器網(wǎng)絡(luò)中高效節(jié)能的數(shù)據(jù)通信協(xié)議 ［J］.電子學(xué)報，2005，33 （8）：1392－1396.］

［4］SHEN Bo，ZHANG Shiyong.Wireless sensor network clustering routing protocol ［J］.Journal of Software，2006，17（7）：1588－1600 （in Chinese）.［沈波，張世永.無線傳感器網(wǎng)絡(luò) 分 簇 路 由 協(xié) 議 ［J］. 軟 件 學(xué) 報，2006，17 （7）：1588－1600.］

［5］SUN Yugeng，ZHOU Yin，BIAN Guinian，et al.Wireless sensor networks a network of energy efficient clustering algorithm ［J］.Chinese Journal Sensors and Actuators，2007，20（2）：377－381 （in Chinese）.［孫雨耕，周寅，邊桂年，等.無線傳感器網(wǎng)絡(luò)中一種能量有效的分簇組網(wǎng)算法 ［J］.傳感技術(shù)學(xué)報，2007，20 （2）：377－381.］

［6］Muruganathan S D，MA D C F，Bhasin R I，et al.A centralized energy－efficient routing protocol for wireless sensor networks［J］.IEEE Communications Magazine，2005，43（3）：8－13.

［7］WANG Chunlei，CHAI Qiaolin，WANG Hua，et al.Based on cluster energy efficient routing algorithm for wireless sensor networks ［J］.Journal of Computer Applications，2007，27 （2）：342－345（in Chinese）.［王春雷，柴喬林，王華，等.基于分簇的無線傳感器網(wǎng)絡(luò)節(jié)能路由算法 ［J］.計算機(jī)應(yīng)用，2007，27 （2）：342－345.］

［8］TAO Xiaoling，WANG Guifeng，WANG Yong.Dijkstra for wireless sensor networks based on clustering routing algorithm［J］.Computer Engineering and Design，2010，31 （17）：3807－3811（in Chinese）.［陶曉玲，王桂鳳，王勇.基于Dijkstra的無線傳感器網(wǎng)絡(luò)分簇路由算法 ［J］.計算機(jī)工程與設(shè)計，2010，31 （17）：3807－3811.］

［9］WU Zhenhua，YIN Zhijun.WSNs based on optimization of non－uniform cluster radius clustering routing ［J］.Computer Engineering and Design，2010，31 （15）：3374－3378 （in Chinese）.［吳振華，尹志軍.基于優(yōu)化簇半徑的 WSNs非均勻分簇路由 ［J］.計算機(jī)工程與設(shè)計，2010，31（15）：3374－3378.］

［10］NIU Kang，DENG Yaping，MAN Wen.Low－latency data fusion algorithms for wireless sensor networks ［J］.Computer Engineering and Design，2010，31 （12）2710－2712 （in Chinese）.［牛康，鄧亞平，滿文.低時延的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合 算 法 ［J］.計 算 機(jī) 工 程 與 設(shè) 計，2010，31 （12）2710－2712.］

［11］TANG Yong，ZHOU Mingtian，ZHANG Xin.Routing protocol for wireless sensor networks research progress ［J］.Journal of Software，2006，17 （3）：410－421 （in Chinese）.［唐勇，周明天，張欣.無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展［J］.軟件學(xué)報，2006，17 （3）：410－421.］

［12］WU Chenwen，WANG Tiejun.NS2－based model of wireless sensor network routing protocol design and study ［J］.Journal of Lanzhou Jiaotong University，2007，26 （1）：1－5 （in Chinese）.［吳辰文，王鐵君.基于NS2無線傳感器網(wǎng)絡(luò)路由協(xié)議模型的設(shè)計與研究 ［J］.蘭州交通大學(xué)學(xué)報，2007，26（1）：1－5.］

［13］FU Jun，ZHANG Xiaofeng.A cluster head selection model based on wireless sensor network clustering algorithm ［J］.Journal of Computer Applications，2007，20 （8）：1856－1859（in Chinese）.［傅軍，張曉鋒.一種基于簇頭選擇模型的無線傳感器網(wǎng)絡(luò)分簇算法 ［J］.傳感技術(shù)學(xué)報，2007，20 （8）：1856－1859.］

［14］LIU Qin，WANG Fubao，MA Junyan，et al.A wireless sensor network effective distributed clustering ［J］.Computer Application，2007，27 （1）：4－6（in Chinese）. ［劉琴，王福豹，馬峻巖，等.無線傳感器網(wǎng)絡(luò)中一種有效的分布式簇劃分算法 ［J］.計算機(jī)應(yīng)用，2007，27 （1）：4－6.］

［15］JIANG Shaofeng，YANG Minghua，SONG Hantao，et al.Sensor networks centroid－based distributed clustering algorithm ［J］.Journal of Computer Applications，2007，27（1）：1－3 （in Chinese）.［姜少峰，楊明花，宋瀚濤，等.傳感器網(wǎng)絡(luò)中一種基于質(zhì)心的分布式成簇算法 ［J］.計算機(jī)應(yīng)用，2007，27 （1）：1－3.］