無線傳感器網絡多跳路由協議研究

袁耀東,許紅艷

(鄭州澍青醫學高等專科學校 衛生管理系，鄭州 450064)

無線傳感器網絡多跳路由協議研究

袁耀東,許紅艷

(鄭州澍青醫學高等專科學校 衛生管理系，鄭州 450064)

無線傳感器網絡發展迅速，但傳感器的高能耗問題成為制約其發展的主要瓶頸，高效節能的路由協議設計成為研究熱點;針對目前無線傳感器網絡常用的LEACH路由協議存在的簇首能耗過分集中、簇首分布不均衡問題，提出了改進的路由協議EEACRA，在總結、分析LEACH路由協議現有問題的基礎上，給出了EEACRA路由協議的簇首選取門限值、簇首位置調整算法和基于能量代價最小的簇間多跳路由算法的實現方法，同時給出了具體的實現EEACRA協議的工作流程和關鍵算法；在MATLAB環境下對LEACH路由協議和EEACRA路由協議進行了仿真，對比了不同能耗降低措施對網絡能耗降低的貢獻;仿真結果表明EEACRA路由協議的網絡穩定期較LEACH路由協議有較大的改善;證明了改進的路由協議EEACRA可以有效地提高網絡的穩定期。

無線傳感器網絡;網絡體系結構;路由協議;分簇算法;LEACH協議

0 引言

近年來，無線傳感器網絡得到了快速發展，但能耗問題一直是無線傳感器網絡[1]發展的瓶頸，因此高效節能的路由協議設計就顯得至關重要。針對常用的LEACH路由協議進行改進的LEACH-C路由協議[2-3]能夠優化簇首分布，但在每輪簇首選舉前都必須知道全網的剩余能量；而自組織協議SOA能夠適應網絡拓撲變化，并通過調整發射功率與其距離最近的節點進行通信，有效地減少了能量開銷，但其對路由節點的運算能力、存儲空間和定位能力要求過高。

針對上述問題，提出了改進的路由協議EEACRA。通過把能量判決門限和能量因子引入簇首選舉概率閾值中，使能量較多的節點被選舉為簇首的概率增加[4-5]；同時將延時機制引入簇首廣播階段，降低簇首廣播階段報文傳送發生碰撞沖突的可能性；最后通過基于能量代價最小的簇間多跳路由算法將信息發送至基站，有效的降低了網絡能耗并延長了網絡的生存時間。

1 EEACRA協議網絡體系及能耗模型

1.1 EEACRA協議網絡體系

EEACRA協議是分層路由協議，采用分布式自舉成簇算法[6-7]，在邏輯上將整個網絡劃分為匯聚節點，簇首節點成員節點三層，具體如圖1所示。

圖1 EEACRA協議網絡體系結構模型

在數據傳送過程中，各簇首節點通過多跳方式選取最優路由線路將數據傳送至匯聚節點。簇首節點主要負責成員節點的管理和時隙分配，同時將接收到的成員節點數據進行融合后發送至匯聚節點；成員節點主要負責周圍環境信息的采集和將采集到的信息發送至簇首節點；匯聚節點主要負責與外圍網絡進行通信，將采集到的數據傳送至客戶端。

1.2 EEACRA協議能耗模型

LEACH路由協議的能耗模型如圖2所示。

圖2 路由協議能耗框圖

出現發送節點和信息接收節點之間距相近的情況時，根據無線電自由空間傳播模型，信號功率與距離的2次方成反比，接收功率如式(1)所示：

(1)

出現發送節點和信息接收節點之間距相遠的情況時，根據雙線地面反射傳播模型，信號功率與距離的4次方成反比，接收功率如式(2)所示：

(2)

在式(1)、式(2)中，Pt表示發射功率，Gt表示發射天線增益，Gr表示接收天線增益，λ表示波長，L表示系統損耗因子，hr表示接收天線高度，ht表示發射天線高度，d表示收發節點間距。

為研究問題方便，分別用近距離功率衰減系數和遠距離功率衰減系數εfs和εmp代替式(2)、式(3)中與收發節點間距d無關的量。故傳感器節點向間距d處的節點發送l bits數據的能耗如式(3)所示：

(3)

式(3)中，Eelec為節點接收或發送單位bit數據的能耗。

無線電波傳送的分界參考距離d0如式(4)所示：

(4)

傳感器節點接收lbit數據的能耗如式(5)所示：

ERx(l)=Eelec×l

(5)

簇首融合n個傳感器節點數據的能耗如式(6)所示：

E(l,n)=EDA×l×n

(6)

式(6)中，EDA為融合單位bit數據的能耗。

2 EEACRA協議實現

2.1 簇首選取門限的確定

根據文獻[8]的分析可知，LEACH路由協議無法避免能量較小的節點被選舉為簇首，也無法保證各輪簇首選舉過程中簇首數目能夠達到最優值；而當網絡中有節點的能量耗盡時，簇首數目最優值也無法進行相應的調整[9]。

為解決上述問題，提出新的簇首選舉門限。不妨設網絡初始化時的節點數目為N0，在初始化時經統計得出網絡能耗最低時的簇首數目為kep，則網絡能耗最低時的簇首比例為kep/N0。但隨著網絡節點能量的消耗，部分節點變為無效節點，整個網絡能耗最低時的簇首個數kep會發生變化，簇首選舉概率如式(7)所示：

(7)

從式(7)中可以看出，隨著網絡有效節點數量的減少，簇首選舉概率與網絡中存活的節點數目N的平方根成反比，與網絡初始化時節點數目N0的平方根成正比[10-11]。

為加大剩余能量較高的節點被選舉為簇首的概率。在考慮節點剩余能量和優化簇首選舉門限的基礎上，再引入網絡中當前存活的節點數目對網絡能耗最低時簇首比例的影響，同時在門限值T(n)中引入簇首選舉概率Pep，則EEACRA路由協議的簇首選舉公式如式(8)所示：

Tep(n)=

(8)

式(8)中，Pep表示當前輪節點n被選舉為簇首的概率，En_cur表示節點n的當前剩余能量，Ech_av(r-1)表示上一輪所有簇首剩余能量的平均值，r表示當前輪次，σ表示修正系數。

2.2 簇首位置調整算法

EEACRA路由協議最佳簇首的個數用kep表示，在傳感器節點均勻分布的情況下，各簇首間距的期望值如式(9)所示：

(9)

式中，c表示滿足網絡任務覆蓋要求所需的常數，S表示網絡覆蓋的總面積，kep表示簇首個數均值。

為解決每輪選舉過程中，各簇首距離過近引起的簇首廣播階段報文傳送發生碰撞沖突的概率，需要對各簇首位置進行調整[11-12]。具體方法如下：

1)當節點通過門限值確定可以成為簇首后，并不立刻進行簇首聲明的廣播，先根據上輪所有簇首的能量均值和節點自身的剩余能量設定一個定時器t(n)，節點自身剩余的能量越多，設定的定時時間就越短；

2)如果在到達定時器的定時時間之前接收到其它節點的簇首聲明的廣播，則先判斷其與簇首聲明節點的距離，如果間距小于分界距離d0，則該節點直接加入簇首，成為其成員節點；否則廣播簇首聲明，聲明自己為簇首。

定時器的定時時間與節點自身剩余能量的關系如式(10)所示：

0

(10)

式中，ε表示時間調整系數，En_cur表示節點n的當前剩余能量，Ech_av(r-1)表示上一輪所有簇首剩余能量的平均值。從式中可以看出，t(n)的大小由節點當前的剩余能量決定，因此，各節點通過定時器得到的廣播時延一般不同，由此可見，引入t(n)可以調整簇首位置，同時也能夠降低信道沖突的概率。但EEACRA路由協議的簇首位置調整算法將部分簇首節點重置為普通節點，這就使網絡最優簇首數目的期望值偏離了預設的簇首優化值kep，因此必須通過修正系數σ修正簇首選取公式。

2.3 基于能量代價最小的簇間多跳路由算法

2.3.1 算法概述

簇首節點需要處理接收到的成員節點數據并將融合后的數據發送至匯聚節點的雙重任務。因此，當簇首與匯聚節點的間距較大時，為減小簇首節點能耗，應采用多跳路由算法，但多跳路徑很多，EEACRA路由協議使用能量代價最小的多跳路由算法來均衡簇首能耗，具體算法如下：

1)在成簇期間，匯聚節點向整個網絡周期性的廣播包含發射功率、時鐘同步等信息的控制報文，各簇首依據發射功率和RSSI值估算其與匯聚節點的間距，然后通過式3計算其到匯聚節點的通信能耗，并將其作為初始路徑代價在簇首廣播中聲明。

2)各簇首在接收到其它簇首廣播后，比較自身的原路徑代價和通過廣播簇首為中繼節點的路徑代價，如果自身的原路徑代價大于通過廣播簇首為中繼節點的路徑代價，則對該節點的中繼節點和路徑代價進行更新，同時在備用的中繼路由信息庫中保存原中繼節點和路徑代價，隨后簇首向全網廣播更新后的路徑代價[13-14]。

2.3.2 最優中繼簇首的選擇

研究表明傳感器節點的主要能耗來源是無線通信模塊，其中空閑能耗與接收能耗基本持平，約為發送能耗的75%。在選擇最優中繼簇首的過程中，EEACRA路由協議考慮了中繼簇首發送和接收數據兩方面的能耗。最優中繼簇首選擇的的過程如下：

1)初始路徑代價的計算。各簇首先估算其到匯聚節點的通信距離dto_Sink，然后根據式3計算出自身與匯聚節點直接進行通信的能耗，記為初始路徑代價Cost0(CHi)，其計算公式如式(11)所示：

(11)

2)更新路徑代價的計算。各簇首在接收到其它簇首的廣播后，通過估算其與其它簇首的間距來計算以其它簇首作為中繼節點的路徑代價，如果中繼路徑代價比簇首的初始路徑代價低，則以中繼路徑代價作為簇首的路徑代價。但在網絡中可能存在若干個小于簇首初始路徑代價的中繼節點，簇首默認的中繼節點為路徑代價最小的中繼節點，并在隨后的廣播中聲明該路徑代價為簇首的路徑代價[15]。

簇首i以簇首j作為其中繼節點時的路徑代價如式12所示：

(12)

2.3.3 路由維護

網絡每輪簇首選舉開始時，成簇階段建立的簇間多跳路由關系都要重新建立，因此無需對路由表進行專門的維護。在各輪數據傳送過程中，如果簇首默認的中繼節點不能正常進行中繼，則選取次優中繼節點完成數據傳送；如果全部中繼節點都無法進行正常中繼，則簇首與匯聚節點直接進行數據傳送。因此EEACRA路由協議的多跳算法對于網絡應用是穩定可靠的，不會存在數據無法傳送的情況。

2.4 EEACRA協議工作流程

EEACRA路由協議為分簇層次型路由協議，采用簇首輪換的方式來均衡網絡各節點的能耗，每輪簇首輪換過程由組網和數據傳輸兩個階段組成。EEACRA路由協議的工作流程框圖如圖3所示。

圖3 EEACRA路由協議工作框圖

2.4.1 組網階段

組網初始化：首先復位各節點狀態，然后匯聚節點向全網周期性地廣播Beacon信息，信息的主要內容包括網絡初始化時的節點數N0，本輪組網前存活的節點數N，本輪簇首選舉概率Pep，上輪簇首能量均值Ech_av(r-1)，修正系數σ，距離分界值d0、發射功率和時間同步等信息。

產生準簇首：各節點隨機生成一個0到l之間的數，如果生成的隨機數小于式8中的門限值T(n)，則自舉該節點為準簇首。

產生簇首：各簇首通過式11計算自身的初始路徑代價，然后按式10計算自身的定時時間同時啟動定時器。到達定時時間時，向全網廣播簇首聲明信息。

簇首位置調整與簇間多跳路由建立：根據前述的簇首位置調整算法，可以建立整個網絡的簇首節點；然后按式12進行路徑迭代，即可建立多跳路由。

普通節點入網：普通節點會接收到周圍各簇首的簇首廣播，根據廣播的信號強度選取一個距離最近的簇首加入。選定要加入的目標簇首后，通過CSMA/CA協議接入信道，向選定簇首發出內容為簇首ID和節點ID的Join-REQ消息請求加入成為其成員節點。

分配時隙：當簇首定時器計時到時，簇首為每個成員節點分配工作時隙。簇首先通過CSMA/CA協議接入通信信道，然后廣播Join-ACK消息使其成員節點接收到時隙分配表。成員節點按照時隙分配情況設定定時器，并據此切換通信和休眠狀態。

2.4.2 數據傳送階段

簇首融合信息：簇內全部成員節點在分配的時隙內將采集到的數據傳送至簇首后，簇首按預先設定的算法對信息進行融合，成員節點則進入休眠狀態直至下個組網周期。

數據傳送：簇首將各成員節點的數據融合后發送至匯聚節點。當網絡完成一定時間的數據傳送后，根據相關算法進入下輪組網階段。

3 系統仿真

本文利用MATLAB對EEACRA路由協議和LEACH路由協議進行了對比仿真。仿真網絡傳感器節點數量為100，監測面積為100 m*100 m，無線傳感器節點隨機布置，在網絡監測中心位置設置匯聚節點，其仿真參數為：4 000 bits的數據包、1J的節點初始狀態能量、10 pJ/bit/m2的近距離功率衰減系數εfs、40 bits的控制包長度、5 nJ/bit的節點收發送單位bit數據的能耗Eelec、0.001 3 pJ/bit/m4的遠距離功率衰減系數εmp。EEACRA協議共采取了3種措施來降低LEACH協議的能耗，具體如表1所示。

表1 EEACRA協議能耗降低措施

EEACRA(EP)協議與LEACH協議的網絡穩定期仿真結果如圖4所示。

圖4 EEACRA(EP)與LEACH 網絡穩定期對比

EEACRA(EPD)協議與LEACH協議的網絡穩定期仿真結果如圖5所示。

圖5 EEACRA(EPD)與LEACH 網絡穩定期對比

EEACRA(EPDH)協議與LEACH協議的網絡穩定期仿真結果如圖6所示。

圖6 EEACRA(EPDH)與LEACH 網絡穩定期對比

從圖4中可以看出，節點隨機部署的情況下，EEACRA(EP)協議的網絡穩定期均值為2296 輪，LEACH協議的網絡穩定期均值為1892 輪，平均網絡穩定期延長比例約為21.35%。

從圖5中可以看出，節點隨機部署的情況下，EEACRA(EPD)協議的網絡穩定期均值為2415輪，LEACH協議的網絡穩定期均值為1892輪，平均網絡穩定期延長比例約為27.64%。

從圖6中可以看出，節點隨機部署的情況下，EEACRA(EP)協議的網絡穩定期均值為2444 輪，LEACH協議的網絡穩定期均值為1892 輪，平均網絡穩定期延長比例約為29.18%。

綜上可以看出，節點隨機部署的情況下，EEACRA(EP)、EEACRA(EPD)和EEACRA(EPDH)與LEACH相比，網絡穩定期均值分別提高了約21.35%、27.64%和29.18%。但各措施對協議能耗的改善貢獻不同，其中，能量加權因子使EACRA的網絡穩定期均值延長了約21.35%，延時機制使網絡穩定期均值延長了約6.29%，多跳路由機制使網絡穩定期均值延長了約1.42%。故在實際網絡應用中，可根據不同的網絡要求對協議進行適當裁剪，使協議在獲得良好增益性能的前提下降低算法的復雜度。

4 結論

針對無線傳感器網絡常用的LEACH路由協議存在的簇首能耗過分集中、簇首分布不均衡問題，提出了改進的路由協議EEACRA，有效地提高了網絡的穩定期。同時給出了EEACRA路由協議實現的關鍵算法和工作流程，并對比了不能能耗降低措施對網絡能耗降低的貢獻，對EEACRA協議在無線傳感器網絡中的實際應用具有重要意義。

[1] 孫利民, 李建中, 陳 渝，等. 無線傳感器網絡[M]. 北京: 清華大學出版社, 2005.

[2] Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless sensor network[J]. IEEE Transactions on Wireless Communications. 2002, 1(4):660-670.

[3] 俞黎陽. 無線傳感器網絡網格狀分簇路由協議和數據融合算法的研究[D]. 上海：華東師范大學, 2007(1):56-58.

[4] Kulik J, Heinzelman W, Balakrishnan H. Negotiation-based protocols for disseminating information in wireless sensor networks[J]. Wireless Networks, 2002, 8(2): 169-185.

[5] Krishnamachari B, Estrin D, Wicker S B. Impact of Data Aggregation in Wireless Sensor Networks[A]. Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS)[C].2002: 575-578.

[6] Ko Y, Vaidya N H. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks[J]. Wireless Networks. 2000, 6(4): 307-321.

[7] Hedetniemi S M, Hedetniemi S T, Liestman A L.A survey of gossiping and broadcasting in communication networks[J]. Networks, 1988, 18(4): 319-349.

[8] Estrin D. Wireless Sensor Networks Tutorial Part IV-Sensor Network Protocols[R]. 2002(1):22-24.

[9] 王萬良, 陳陪俊, 鄭建煒,等. 一種基于LEACH的無線傳感器路由算法及其仿真[J]. 系統仿真技術, 2008, 4(2): 75-79.

[10] 于立娟, 李思敏. 無線傳感器網絡LEACH改進算法的設計與仿真[J]. 光通信研究, 2008,34(5): 67-70.

[11] 蘇均宇,曾子維,石嘉鵬.基于定向擴散路由協議的改進[J].傳感技術學報.2007,20(3):673-676.

[12] Ganesan D, Govindan R, Shenker S, et al. Highly-Resilient, Energy-Efficient Multipath Routing in Wireless Sensor Newtorks[J]. Mobile Computing and Communications Review. 2011, 1(2): 1-13.

[13] Felemban E, Lee C, Ekici E, et al. Probabilistic QoS Guarantee in Reliability and Timeliness Domains in Wireless Sensor Networks[A]. Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005). [C]. 2010: 2646-2657.

[14] 畢俊蕾, 任新會, 郭拯危. 無線傳感器網絡路由協議分類研究[J]. 計算機技術與發展. 2010, 18(5): 131-137.

[15] Callaway B E H. Wireless Sensor Networks Architectures And Protocols[M]. CRC Press, 2012:255-257.

Research of Wireless Sensor Network (WSN)Multiple Hop Routing Protocol

Yuan Yaodong,Xu Hongyan

(Department of Public Science Education, Zhengzhou Shuqing Medical College, Zhengzhou 450064, China)

The wireless sensor network has developed rapidly, but the high energy consumption of the sensor has become the main bottleneck restricting its development. Based on the current LEACH routing protocol of wireless sensor network (WSN)are commonly used excessive concentration of energy consumption of cluster head, cluster head distribution imbalance problem, puts forward the improved routing protocol EEACRA. After studying the existing problems on the basis of LEACH routing protocol, gives the EEACRA routing protocol of the cluster head selecting threshold method, cluster head position adjustment algorithm and the cluster based on the minimum energy cost between multiple hops routing algorithm implementation method, finally in the MATLAB environment to LEACH routing protocol and EEACRA routing protocols are simulated, the contribution of different energy consumption reduction measures to the network energy consumption reduction is compared. The simulation results show that the network stability EEACRA routing protocol is the improvement of the LEACH routing protocol have larger. Proved that the validity of the agreement.

wireless sensor network; network architecture; routing protocols; clustering algorithms; LEACH agreement

2016-10-25；

2016-11-18。

袁耀東(1984-),男, 碩士，講師，網絡工程師，主要從事計算機網絡與云計算方向的研究。

1671-4598(2017)04-0254-05

10.16526/j.cnki.11-4762/tp.2017.04.069

TM417

A