無線傳感器網絡查詢式分簇路由算法研究

摘 要： 為避免LEACH算法因遠端節點與匯聚節點長距離通信能耗過大而提前死亡的弊端，提出一種查詢式多路徑分簇路由算法——QMR?LEACH算法，該算法按需對監測區域進行查詢，由查詢所在簇的簇頭對查詢進行響應，在數據回傳過程中引入節點剩余能量、傳輸消耗能量和跳數等參數，選取最優路徑完成數據轉發工作。計算機仿真結果表明，所提出算法可以根據節點剩余能量、傳輸能耗和跳數等參數自適應的選擇一條最優路徑或以單跳形式轉發數據，能夠有效地延長節點和整個網絡的生命周期，并降低了數據丟失率。

關鍵詞： 無線傳感器網絡； 路由協議； 多路徑； 查詢式

中圖分類號： TN711?34 文獻標識碼： A 文章編號： 1004?373X（2013）15?0036?05

Research on query?based clustering routing algorithm for wireless sensor networks

ZHANG Chi， XIN Yun?hong

（School of Physics and Information Technology， Shaanxi Normal University， Xi’an 710062， China）

Abstract： A query?based multi?hop clustering routing algorithm （QMR?LEACH algorithm）， which queries the monitoring area according to the demand and responses the query by the cluster?head， is proposed to avoid the disadvantage that the long?distance communication between remote node and the sink node could lead to premature death of LEACH algorithm because of much energy consumption. During the process of data pass back， the parameters such as node residual energy， transmission energy consumption and hop count are led in the algorithm， and a optimal path is chosen to complete the data forwarding. The computer simulation results show that the QMR?LEACH algorithm can adaptively select an optimal path according to the parameters of residual energy， transfer energy consumption and hop， or transmit the data in single hop form， it can effectively extend the life cycle of nodes and the entire network， and also can reduce the data loss rate.

Keywords： wireless sensor network； routing protocol； multipath； query method

0 引 言

無線傳感器網絡（Wireless Sensor Network，WSN）是繼因特網之后，對21世紀人類生活方式產生重大影響的熱點技術之一。傳感器節點常常被投放在條件惡劣的環境或場景中，往往是人們無法涉足的地域，節點的能量補給、電源更換是無法完成的，所以無線傳感器網絡路由協議的設計，對其本身而言意義重大[1]。

路由協議的主要功能是在源節點和目的節點間建立優化路徑，并將人們所關心的感知數據沿著優化路徑進行轉發[2]。路由協議是否高效節能會對網絡的整體質量造成一定程度的影響，例如減少網絡擁塞、節省網絡帶寬、降低數據沖撞、均衡網絡流量和延長網絡生命周期等，而對無線傳感器網絡而言，由于節點能量的嚴格受限，一個高效節能的路由協議更是提高整體網絡性能的關鍵技術。

目前，按網絡管理的邏輯結構劃分的無線傳感器網絡路由協議分為平面路由和分層次路由兩類[3?4]，其中分層路由協議更適合無線傳感器網絡，已成為當前國內外無線傳感器網絡方面研究的熱點之一，但這類方法仍存在許多不足，需要進一步研究和待改進。因此，本文在LEACH協議的基礎上提出了查詢式多路徑分簇路由協議QMR?LEACH，其思想是根據需求由匯聚節點發出查詢指令，被查詢的簇頭進行響應，通過判斷與匯聚節點之間的距離關系決定以單跳或多跳方式[5?6]進行通信，若選擇多跳方式，則根據節點剩余能量、消耗能量和跳數等參數確定一條最優路徑。該方法利用多跳的通信方式可將能量消耗分攤在路徑節點上，有效地節省了遠離匯聚節點的簇頭能耗。

1 查詢式的多路徑分簇路由（QMR?LEACH）

算法

LEACH算法是經典的無線傳感器網絡分簇路由協議之一，它在均衡網絡整體能耗上貢獻突出，提高了網絡生命周期，為網絡提供了良好的擴展性。LEACH算法是分層路由的代表方法之一，是最早提出的分簇路由算法[7]，對路由協議方面的研究做出了巨大貢獻。但該協議簇頭與匯聚節點的通信方式單一，且距離匯聚節點越遠的節點會越早的死亡，影響整體網絡的功能。然而，LEACH的不足之處仍需研究和改進，已有大量相關研究人員對LEACH算法提出改進。例如，引入半網全網概念的LEACH改進算法[8]、引入簇半徑概念的LEACH改進算法[9]、基于蟻群算法的LEACH改進算法[10?11]等，這些改進算法部分解決了原算法的缺陷與不足。

查詢式的多路徑分簇路由（QMR?LEACH）算法是對LEACH算法的數據通信階段進行改進，具體過程為：簇頭向匯聚節點發送消息由單跳方式改為多跳與單跳相結合的方式。多跳時路徑的選取由該路徑總能耗、跳數和該路徑剩余能量綜合決定；簇內節點仍采用定時傳輸數據的方式，而將簇頭定時廣播消息模式改為匯聚節點按需對監測區域查詢模式。這樣做既可以解決網絡邊緣節點因長距離傳輸數據耗能較大而提早死亡的弊端，同時減少數據碰撞，降低網絡傳輸誤碼率。

1.1 能量模型

本文選取能量模型參考原LEACH算法的無線電通信能量模型[12]。根據發送節點與接收節點的距離[d]與參考距離[dp]的關系，節點無線通信耗能情況被分為兩種情況：若[d

[Etx（l，d）=Etx-elec（l）+Etx-amp（l）=lEelec+lεfsd2，d

[Erx（l）=Erx-elec（l）=lEelec] （2）

[dp=εfsεamp] （3）

式中：[l]為數據長度；[Eelec，][εfs，][εamp]均為常數，具體取值視硬件電路配置而定。

1.2 路徑選取

現將傳感器節點工作時的狀態分為初始狀態、工作狀態和死亡狀態[13]。假設網絡運行前各節點的初始狀態相同，初始能量均為[Eo；]網絡正常運行后，節點進入工作狀態，假設此時能量為[Et；]當節點因能量耗盡或其他原因死亡脫離網絡時，能量為[Ee。]節點工作時，任何一個節點[Ni]到下一跳節點[Ni+1]之間工作1 s（仿真環境取能量消耗參數為1 mJ/s，傳輸速率為250 Kb/s），數據能量消耗假設為[λ。]則每次節點[Ni]工作[Ti]秒后的能耗參數為：

[Ei（Ti）=Ti×λ] （4）

假設從源節點[S]到目的節點[D]有[N]個節點，[m]條完全不相交路徑，如圖1所示。

圖1 無共享節點多跳路徑圖

假設所有傳感器節點是同構的，且發射功率為恒定值，那么從源節點[S]到目的節點[D]上存在[m]條無共享節點的路徑，跳數與該路徑的總能耗成正比，跳數和總能耗成反比，然而，在跳數最少的路徑上可能存在不穩定狀態的節點，那么這條路徑也不是最優選擇的。因此，通過引入節點剩余能量、單路徑總能耗和跳數等參數，對其綜合考慮的到一條優先級最高的路徑，來確保數據沿該路徑傳輸可以達到高效節能的目的。以下內容為優先級參數推導過程：

第[i]條路徑（跳數為[ki]）的總的能量消耗參數[Ei]為：

[Ei=（Ti1×λ+Ti2×λ+…+Tiki×λ）=λj=1kjTij， i=1，2，…，m] （5）

節點[Nij]在工作[T]秒后的剩余能量參數[ηi]為：

[ηi=（Eo-Ee）-TijλEo， i=1，2，…，ki] （6）

在每個節點完成一次通信時，按式（6）更新當前節點的剩余能量參數[Et。]第[i]條路徑的能量剩余參數如下：

[Ri=（Eo-Ee）-Ti1?λEo×（Eo-Ee）-Ti2?λEo×…×（Eo-Ee）-Tiki?λEo=j=1kj（Eo-Ee）-Tij?λEo，i=1，2，…，m] （7）

式中，[Tij]為第[t]條路徑上第[j]個節點進行一次數據傳輸的時間，綜合路徑的總能耗、跳數，路由優先級參數可表示為：

[Pr（i）=（Eo-Ee）×RiEi×Hhop，i=1，2，…，m] （8）

式中：[Hhop]表示[S→D]的跳數；[Ri]表示路徑[i]剩余能量參數，[Ei]表示路徑[i]的能量消耗參數。

將式（5），式（7）代入式（8）得第[i]條路徑的優先級參數為：

[Pr（i）=（Eo-Ee）×j=1kj（Eo-Ee）-Tij?λEoHhop×j=1kjTij?λ，i=1，2，…，m] （9）

1.3 按查詢需求轉發感知數據

圖2給出了查詢式多路徑分簇路由算法的數據傳輸流程圖，其具體過程為：分簇完成后，簇頭節點只將簇頭自身及簇內成員節點的信息（節點位置、剩余能量、簇內成員節點數和節點編號）發送給匯聚節點，在未接收到具體查詢消息前不進行其他消息的轉發。當有查詢需求時，匯聚節點根據之前獲得的節點信息計算出需查詢的節點所在簇，并將此簇簇頭設置為源節點，視匯聚節點自身為目標節點，首先判斷源節點與匯聚節點之間的距離[d]和閾值[d0]之間的大小關系，若[d≤d0]，則源節點根據查詢句柄對已獲取的簇內信息進行數據融合，然后直接發送數據到匯聚節點；若[d>d0]，則根據公式（9）計算得到一條最優多跳路徑，沿此路徑反向發送查詢句柄，當源節點收到查詢請求后，按照查詢句柄對感知數據進行數據融合，再沿這條已確定的路徑發送數據。

圖2 數據傳輸流程圖

2 仿真與評估

本文選取1 000 m×1 000 m的矩形區域作為無線傳感器網絡的感應范圍，在該區域內隨機分布1 000個傳感器節點，隨后對網絡局部進行仿真實驗，模擬查詢需求發出后簇頭節點響應并回傳數據過程中路徑的選取和整條路徑能量消耗的情況，并對比與匯聚節點不同距離的簇頭采用多跳和單跳通信方式的能量消耗。本仿真實驗假設網絡系統不存在鏈路丟包現象，即理想環境。實驗中，仿真環境Matlab 7.1，其他試驗參數如下：1 000個節點均勻隨機分布；每個節點初始能量恒定：[E0=0.5 J；]根據不同的網絡環境進行分簇實驗，設置普通節點成為簇頭的概率[P=]0.1。

根據節點的分布選取350 m×350 m范圍進行節點和路徑能耗實驗。圖3為實驗區域節點及簇頭分布情況，其中，空心圓點表示源節點，實心圓點為簇頭節點。假設在節點[S]（源節點）和[D]（目的節點）之間存在四條無共享節點的四條不相交路徑，即Path1，Path2，Path3，Path4，如圖4所示，其中Path1經過N1，N2，N3，N4幾個節點，Path2經過N5，N6，N7幾個節點。

圖3 實驗選取簇頭分布圖

圖4 無共享多跳路徑圖

路徑確定后，每隔10 s從源節點向目標節點發送50 KB的數據，統計Path1，Path2，Path3，Path4上各節點不同時刻剩余能量參數：[E0=]0.5，[Ee=]0.01。圖5，圖6為Path1和Path2上7個節點剩余能量參數對比和能量消耗對比圖。

由圖5可以看出，剩余能量參數與節點間的通信距離成反比關系，通信距離越大時，該節點剩余能量參數越小，也就是在通信過程中能量消耗越大，如Path2中的節點N6。同理，通信距離相對較短的傳感器節點在通信過程中，其剩余能量參數較大，如試驗中Path1上的節點N4。圖6給出了節點N1～N7的能量消耗參數對比，從圖6中可以看出，各節點能量消耗成比例增長，整體網絡結構較為穩定。

圖5 節點剩余能量參數圖

圖6 節點能量消耗參數圖

由式（9）獲得如圖7所示的路徑能量優先級參數曲線圖，圖中星形線段表示Path1在第10 s～第40 s通信時的優先級參數，紅色方塊線段表示Path2在第10 s～第40 s通信時的優先級參數。從圖中可以看出，在前14 s，Path1的優先級參數較高，即選擇Path1進行通信將獲得更高的通信質量，更低的通信耗能。在14～40 s，Path2的優先級參數相對較高，此時Path2為合適的通信路徑選擇對象。

圖7 路徑優先級參數對比圖

圖8～圖10為個別節點在多次通信后的能量消耗對比統計。

圖8選取了距離匯聚節點較遠的簇頭節點通信能耗對比圖，圖9選取了距離匯聚節點較遠的簇頭節點通信能耗對比圖，圖10為距離匯聚節點適中的簇頭節點通信能耗對比圖。方框線段表示本文提出的QMR?LEACH算法能耗，點線段表示經典LEACH算法的能耗。這次試驗中選取實驗節點有以下特點：節點通信距離較遠時，直接通信（LEACH算法）將產生較高的能量消耗，也就是在這種情況下，選擇基于查詢的多跳算法能夠降低通信能耗，提高通信效率，結果如圖8所示。同樣的，在選擇通信距離較近節點進行通信時，本文算法的能耗高于LEACH算法，如圖9所示，原因是多跳的通信模式將節點能耗分攤給路徑上其他節點，這樣便避免了遠端節點因長距離傳輸耗能過大而提前死亡的弊端。如圖10所示，此時選取的簇頭節點距離匯聚節點距離適中，此時兩種方法的能耗雖有差別，但未體現出數量級上的優勢，在大量節點長時間通信時才能有所體現。

圖8 簇頭距離匯聚節點較遠時節點通信能耗對比圖

圖9 簇頭距離匯聚節點較近時節點通信能耗對比圖

圖10 簇頭距離匯聚節點適中時節點通信能耗對比圖

3 結 語

無線傳感器網絡作為計算機科學領域的一個研究熱點受到學術界和工業界的廣泛關注。網絡節點資源受限，尤其是傳感器能量有限，提高路由效率節省能耗，從而達到延長整個網絡生命周期的目的是目前研究的一個主要方向。本文對LEACH路由協議的優缺點進行了分析，并提出新的QMR?LEACH改進算法，在數據通信階段，根據簇頭節點與匯聚節點的距離關系，使用多跳與單跳相結合的方式通信，并引入跳數、剩余能量和下一跳消耗能量等參數選取最優路徑。仿真實驗結果表明，改進的QMR?LEACH算法對解決網絡邊緣節點提前死亡的問題有一定的改善，均衡了節點能耗，延長了網絡的生命周期。

參考文獻

[1] 沈玉龍，費慶祺，馬建峰，等.無線傳感器網絡安全技術概論[M].北京：人民郵電出版社，2010.

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

[3] AKYILDIZ I F， MELODIA T， CHOWDHURY K R. A survey on wireless multimedia sensor networks [J]. Computer Networks， 2007， 51（4）： 921?960.

[4] AKYILDIZ I F， SU W L， SANKARASUBRAMANIAM Y， et al. A survey on sensor network [J]. IEEE Communications Magazine. 2002， 40（8）： 102?114.

[5] CHEN C F， WU W L， ZHENG L. Multipath routing modeling in Ad Hoc networks [C]// Proceedings of 2005 IEEE International Conference on Communications. Seoul， Korea： IEEE， 2005： 2794?2798.

[6] GANESAN D， GOVINDAN R， SHENKER S， et al. Highly?resilient， energy?efficient multipath routing in wireless sensor networks [J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2001， 5（4）： 11?25.

[7] HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy?efficient communication protocol for wireless microsensor networks [C]// Proceeding of the 33rd Annual Hawaii International Conference on System Sciences. Maui： IEEE Computer Society， 2000： 8020?8026.

[8] 李天池.無線傳感器網絡LEACH協議的算法改進[D].濟南：山東大學，2012.

[9] 石清泉.無線傳感器網絡LEACH路由協議的研究與改進[D].武漢：華中科技大學，2012.

[10] 王林，潘軍.無線傳感器網絡中基于能量優化的路由協議ANT?LEACH[J].計算機應用，2011，31（11）：2891?2894.

[11] 夏威.基于蟻群算法的無線傳感器網絡優化路由協議[D].上海：華東師范大學，2012.

[12] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An application?specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications. 2002， 1（4）： 660?670.

[13] NASIPURI A， CASTA?EDA R， DAS S R. Performance of multipath for on?demand protocols in mobile Ad Hoc networks [J]. Mobile Networks and Applications， 2001， 6（4）： 339?349.