王 軍， 孫健程

(1.沈陽化工大學 計算機科學與技術學院， 遼寧 沈陽 110142;2.中國科學院沈陽自動化研究所， 遼寧 沈陽 110016)

基于LEACH的WSN路由協(xié)議的研究與改進

王 軍1,2， 孫健程1

(1.沈陽化工大學 計算機科學與技術學院， 遼寧 沈陽 110142;2.中國科學院沈陽自動化研究所， 遼寧 沈陽 110016)

為解決LEACH路由協(xié)議簇頭選擇算法的不足，針對在無線傳感器網絡選舉簇頭沒有考慮節(jié)點的信賴值和簇內節(jié)點能量分布不均衡等問題，設計一種基于LEACH協(xié)議改進的新算法.通過計算節(jié)點的信賴值，作為選擇新簇頭節(jié)點的標準，最后對仿真試驗進行性能分析比較，該算法能夠滿足生產需要，提高節(jié)點能量的效率，延長整個網絡的生命周期，使網絡均衡分配能量并且具有深遠的意義.

路由協(xié)議； 無線傳感器網絡； 信賴值； 網絡生命周期

無線傳感器網絡(WSN)是由大量傳感器節(jié)點通過無線通信方式形成的一個多跳的自組織網絡系統(tǒng)，它能夠實現數據的采集量化、處理融合和傳輸.它綜合了微電子技術、現代網絡及無線通信技術，能夠協(xié)同地實時監(jiān)測、感知和采集網絡覆蓋區(qū)域中各種環(huán)境或監(jiān)測對象的信息，并對其進行處理，處理后的信息通過無線方式發(fā)送，并以自組多跳的網絡方式傳送給觀察者.WSN綜合了傳感器技術、自動化控制技術、網絡技術和分布式技術等，是一種全新的信息采集和信息處理的新型技術[1-2].

隨著近年來網絡需求的加劇，其中無線傳感器網絡協(xié)議也在不斷地研究與改進，為了更好地適應當前的應用環(huán)境，對無線傳感器網絡的研究與開發(fā)成為目前信息領域的一個熱點.由于微處理器的低能耗通信科技的快速發(fā)展，從而可以搭建大規(guī)模傳感器節(jié)點的網絡拓撲結構，監(jiān)測惡劣環(huán)境的無線傳感器網絡，并且可以解決實際復雜的應用問題[3].在國際上，美國自然科學基金會開展了“嵌入式智能傳感器”項目，同時在國內的清華大學、哈爾濱理工大學也開展了對WSN領域的研究工作.盡管無線傳感器網絡在國內外被深入研究，但無線傳感器網絡還有許多技術問題有待解決，因此研究一種節(jié)約能量的無線傳感器網絡的路由協(xié)議顯得非常重要.本文提出一種基于LEACH的WSN路由協(xié)議SY_LEACH路由協(xié)議，改進的SY_LEACH協(xié)議生命周期長、性能高、功耗低.

1 無線傳感器網絡路由協(xié)議

無線傳感器網絡路由協(xié)議是無線傳感器網絡的核心技術之一，同時也是目前國內外研究技術的熱點.無線網絡的路由協(xié)議主要負責將采集到的數據分組后，從成員節(jié)點通過網絡協(xié)議發(fā)送到sink節(jié)點，其主要功能為：成員節(jié)點尋找與sink節(jié)點之間的最優(yōu)化路徑；將采集到的數據經過融合整理，然后在分組沿著最優(yōu)化路徑準確傳送[4-5].

LEACH是一種無線傳感器網絡設計的低功耗自適應分簇分層結構的路由協(xié)議，主要思想是將整個網絡節(jié)點分簇，成員節(jié)點將數據發(fā)送到簇首節(jié)點，簇首節(jié)點進行數據融合壓縮，再將數據發(fā)送給sink節(jié)點，這樣可減少網絡傳輸的數據包，降低占用的帶寬，最后把融合的數據發(fā)送給網關節(jié)點.目的是節(jié)約能量的消耗，充分利用能量資源，保證無線傳感器網絡的持續(xù)性和可擴展性[6].

2 路由協(xié)議的總體結構

路由技術是無線傳感器網絡傳輸的核心技術，其中路由協(xié)議必須能在局部網絡拓撲信息的基礎上準確選擇出從源節(jié)點到目的節(jié)點的路徑.LEACH路由協(xié)議的核心思想是分布式算法，傳感器節(jié)點通過自適應集簇分層算法，在簇內通過隨機的選舉簇頭法，然后簇內的成員節(jié)點按照TDMA方式把收集的數據包發(fā)送到簇頭節(jié)點，簇頭節(jié)點進行數據融合壓縮后把數據包發(fā)送到基站.在LEACH路由協(xié)議的操作過程中，每輪選舉分為2個階段：類建立階段和穩(wěn)定階段.

NPT_LEACH協(xié)議是基于LEACH協(xié)議改進后的協(xié)議，其協(xié)議的主要思想是在選舉簇頭時加入備選簇頭集和增加最優(yōu)簇半徑的過程.改進后的協(xié)議提高了網絡規(guī)模適應性并且延長了無線傳感器網絡的生命周期.

2.1 類建立階段

主要選擇方法：無線傳感器節(jié)點隨機的選擇0到1中間的某個值，選擇的值如果小于某一個閾值T(n)，那么該節(jié)點被選為首節(jié)點.T(n)值的計算公式：

(1)

其中:n為網絡中傳感器節(jié)點總數；p為網絡節(jié)點中成為簇頭的百分比；r為當前選舉輪數；Gr為在過去1/p輪中不是蔟頭的傳感器節(jié)點組成的集合.當簇頭節(jié)點向周圍成員節(jié)點廣播消息時，其他成員節(jié)點接收到廣播消息后，根據接收到廣播消息的強弱，確定加入哪個簇內，然后使用載波監(jiān)聽機制向各自簇頭節(jié)點發(fā)送加入通知.

2.2 穩(wěn)定階段

收到通知的簇頭節(jié)點，為簇內的成員節(jié)點創(chuàng)建時分多址，成員節(jié)點在各自時隙表中，將采集到的數據包發(fā)送給簇頭節(jié)點.簇頭節(jié)點進行數據融合壓縮后，發(fā)送給sink節(jié)點，直到循環(huán)結束，準備下一次聚簇.LEACH協(xié)議是簡單的分層路由協(xié)議，每次隨機選取簇頭節(jié)點時，根據T(n)的選擇，避免了簇頭節(jié)點因為能量耗盡而過早死亡，在無線傳感器網絡中明顯的降低了能量的消耗，延長了整個網絡的生命周期.但是在LEACH路由協(xié)議中仍然存在不足：在選舉簇頭的過程中可能會有偽造節(jié)點冒充簇頭節(jié)點的存在，有時簇頭會發(fā)送虛假信息，影響收集數據的真實性.

3 LEACH路由協(xié)議改進

LEACH路由協(xié)議在運行的過程中，為了避免壞節(jié)點篡改數據，提高無線傳感器網絡的安全性，因此對LEACH協(xié)議的改進主要通過對節(jié)點的數據、通信、能量和融合四方面綜合考慮計算節(jié)點的信賴值.綜合評估信賴值可以避免將剩余能量較少的節(jié)點選為簇首節(jié)點，并且可以解決在小范圍內，有一個或多個簇首的出現和簇首節(jié)點分布不均的現實問題.

3.1 算法的基本思想

首先假設LEACH協(xié)議的環(huán)境和改進后的SY_LEACH協(xié)議的環(huán)境相同，同時應用于LEACH協(xié)議的網絡模型下.(1) 初始化網絡節(jié)點同構；(2) 節(jié)點能量充足；(3) 基站是固定并且遠離無線傳感器網絡；(4) 節(jié)點靜止.假設LEACH協(xié)議初始化網絡節(jié)點具有相同能量，初始值為1，經過一輪后，節(jié)點消耗能量不同，節(jié)點剩余能量和信賴值產生變化，計算出第一輪節(jié)點的信賴值，作為下一輪選舉簇頭節(jié)點的標準.

在SY_LEACH協(xié)議中，根據LEACH協(xié)議選舉簇頭算法后，計算出第一輪結束各節(jié)點的信賴值，并同各自的ID一同發(fā)送給簇頭節(jié)點，簇頭節(jié)點收到消息后，數據融合發(fā)送到基站，基站計算本輪的信賴值和上一輪的信賴值，如果差值大于T(n)時，則從網絡模型中刪除該節(jié)點，然后剩余節(jié)點再根據LEACH協(xié)議規(guī)定的閾值選擇下一輪的簇頭，這個過程可以提高整個網絡傳送數據的準確性和真實性.

3.2 計算節(jié)點信賴值

在無線傳感器網絡中計算SY_LEACH協(xié)議的節(jié)點信賴值，主要從節(jié)點的數據、通信、能量和融合四方面來考慮，分別為節(jié)點n的數據信賴值Dn、通信信賴值Cn、能量信賴值En和融合信賴值Fn，最后計算出綜合的信賴值Sn.

(1) 計算數據信賴值

提高無線網絡的容錯能力，減少篡改信息，加強數據的準確性和真實性，需要評估各節(jié)點的信賴值.根據基于節(jié)點多角度信賴的無線傳感器網絡，將節(jié)點的發(fā)送報告、數據的容錯行和一致性綜合考慮，計算出數據的信賴值[7].

數據容錯信賴值為：設Dn是節(jié)點n的容錯信賴值，取值0或1.當簇內發(fā)送報告節(jié)點的個數大于未發(fā)送報告的節(jié)點個數時，取值為1.

(2)

式中：esn為節(jié)點n一致性收集的次數；enn為節(jié)點n不一致性收集的次數.

節(jié)點發(fā)送報告信賴值為：

(3)

式中：vsn為節(jié)點n成功發(fā)送次數；vln為節(jié)點n失敗發(fā)送次數.

綜合在一起的數據信賴值為：

(4)

式中:α1、α2、α3分別表示數據容錯值、數據的一致性和發(fā)送報告信賴值的權值，其值根據實際應用選取.

(2) 計算通信信賴值

在無線傳感器網絡中，數據傳輸是節(jié)點的主要行為，一些不良節(jié)點可能會篡改數據的真實性和準確性，此時需要監(jiān)測數據傳輸的過程.因此利用Beta信賴模型計算信賴值，Beta(n，m)的分布概率密度函數為[8]：

(5)

式中:n>0，m>0，0≤x≤1.

在WSN路由協(xié)議LEACH中，簇內成員節(jié)點和簇頭節(jié)點是一跳通信，所以節(jié)點n對簇頭節(jié)點m的信賴為Bn，m：

Bn,m=Beta(sn,m+1,ln,m+1)

(6)

式中:sn，m表示節(jié)點n和m通訊成功次數;ln，m表示節(jié)點n和m通訊失敗次數.

根據(6)式，可以計算出節(jié)點n的通信信賴的期望值：

(7)

(3) 計算能量信賴值

針對無線傳感器網絡節(jié)點中剩余能量分配不均衡問題，如果簇內成員節(jié)點負載過大，容易導致能量過低的節(jié)點選舉成為簇頭，發(fā)生過早死亡情況，使網絡不能完全聯(lián)通，因此要計算能量信賴值保證簇內節(jié)點能量消耗均衡，從而延長網絡的生命周期[9].節(jié)點能量信賴值為：

(8)

式中:Ec為初始化原有的能量;Es為剩余能量.

(4) 計算數據融合信賴值

在網絡中相鄰的節(jié)點感知數據特性具有相似性，并且具有大量的冗余數據，如果直接將冗余數據進行傳輸，勢必會消耗能量和占用帶寬，降低無線傳感器網絡的生命周期.在無線傳感器網絡中波束生成算法是一種加權平均法[10].該算法可將傳感器收集到的數據進行過濾和融合.節(jié)點數據融合信賴值為：

(9)

式中:si()為第i個傳感器收集的信號；N為融合傳感器的個數；wi()為第i個傳感器權重融合器；l為融合器的數量.

(5) 計算最終節(jié)點信賴值

數據、通信、能量和融合四方個面共同構成了最終節(jié)點的信賴值：

Sn=γ1Dn+γ2Cn+γ3En+γ4Fn

(10)

式中，γ1、γ2、γ3、γ4分別表示數據、通信、能量和融合的權重值，其值根據實際應用選取.

4 測 試

4.1 仿真環(huán)境

為了評估改進后的路由協(xié)議性能，采用網絡仿真工具OPNET進行仿真，采用數據分析軟件MATLAB進行數據比較[11]，從節(jié)點的剩余能量和節(jié)點的存活時間方面考慮，評價改進的新協(xié)議的性能.根據以下基本參數設定進行模擬實驗：假設SY_LEACH協(xié)議在仿真環(huán)境中，設置100個傳感器節(jié)點，監(jiān)測范圍是100 m×100 m，基站位置為(50,50)，節(jié)點的初始化能量為1 J，數據融合的能耗為5 nJ/bit，發(fā)送和接收數據的能耗為50 nJ/bit，數據包為2 000 bit.

4.2 仿真結果及分析

經過OPNET網絡仿真模型，從數據、通信、能量和融合四方面綜合選舉簇首節(jié)點，得到LEACH協(xié)議、NPT_LEACH和SY_LEACH協(xié)議剩余能量消耗對比以及網絡存活節(jié)點數對比.

在LEACH協(xié)議、NPT_LEACH協(xié)議和SY_LEACH協(xié)議中，節(jié)點剩余能量隨時間的變化如圖1所示.開始0～83輪時LEACH協(xié)議、NPT_LEACH協(xié)議和SY_LEACH協(xié)議中節(jié)點剩余能量相同，但隨時間的延續(xù)SY_LEACH協(xié)議中節(jié)點的能量消耗較慢，直到200輪結束時，在SY_LEACH協(xié)議中的節(jié)點剩余能量多于LEACH協(xié)議和NPT_LEACH協(xié)議中節(jié)點剩余能量.研究表明SY_LEACH算法能夠有效控制網絡，網絡生命周期得到延長.

圖1 三種協(xié)議剩余能量的比較

在LEACH協(xié)議、NPT_LEACH協(xié)議和SY_LEACH協(xié)議中，存活節(jié)點數的變化如圖2所示.三種協(xié)議在節(jié)點數量和網絡生存周期相同情況下，采用LEACH協(xié)議和NPT_LEACH協(xié)議的網絡節(jié)點存活數量少于采用SY_LEACH協(xié)議的網絡節(jié)點存活數量，LEACH協(xié)議在1 400輪時節(jié)點全部無效，NPT_LEACH協(xié)議在1 500輪時節(jié)點全部無效，而SY_LEACH協(xié)議在1 600輪才全部失效.仿真結果說明:SY_LEACH協(xié)議的性能優(yōu)于LEACH協(xié)議和NPT_LEACH協(xié)議，節(jié)點的存活率顯著增多.

圖2 三種協(xié)議存活節(jié)點數的比較

分析節(jié)點的分布情況，三種協(xié)議成簇后的節(jié)點分布如圖3所示.在監(jiān)測區(qū)域內隨機分布100個節(jié)點，其中簇頭數為5個.從圖3可清楚的看出： LEACH路由協(xié)議簇頭負載不均衡，嚴重出現極小極大現象；NPT_LEACH協(xié)議和SY_LEACH協(xié)議分布均衡，其中SY_LEACH協(xié)議具有更好的負載均衡效果.

(a) LEACH協(xié)議

(b) NPT_LEACH協(xié)議

(c) SY_LEACH協(xié)議

5 結束語

基于LEACH的WSN路由協(xié)議研究和仿真，改進了一種新型無線路由協(xié)議SY_LEACH.分別從數據、通信、能量和融合幾方面分析和研究現有無線傳感器網絡路由協(xié)議的基本特點和設計思想，總結了已有路由協(xié)議的優(yōu)缺點.利用OPNET軟件對分層路由協(xié)議LEACH實現仿真實驗，同時提出了對它改進的SY_LEACH協(xié)議，該協(xié)議更好的節(jié)省和均衡網絡中節(jié)點的能量消耗，并能滿足能量有效性和網絡可擴展性的要求，最后從節(jié)點剩余能量和節(jié)點的存活數量進行仿真分析，仿真結果證明SY_LEACH協(xié)議使網絡生命周期得到延長，具有顯著的理論意義和實際應用.

[1] 于海斌,曾鵬,王忠鋒.分布式無線傳感器網絡通信協(xié)議研究[J].通信學報,2004,25(10)：16-35.

[2] 魏剛.一種基于地理位置信息的高能效的WSN路由協(xié)議的研究[D].沈陽：東北大學,2008：20-23.

[3] Akyildiz I F,Su W,Sankarasubramaniam Y,et al.A Survey on Sensor Networks[J].Communication Magazine IEEE,2002,40(8)：102-114.

[4] 任豐原,黃海寧,林闖.無線傳感器網絡[J].軟件學報,2003,14(7)：1282-1291.

[5] 楊冕,秦前清.基于無線傳感器網絡的路由協(xié)議[J].計算機工程與應用,2004,40(32)：130-131.

[6] 胡鋼,謝冬梅,吳元忠.無線傳感器網絡路由協(xié)議LEACH的研究與改進[J].傳感技術學報,2007,20(6)：1391-1396

[7] 董慧慧,郭亞軍.一種基于節(jié)點多角度信任的無線傳感器網絡[J].計算機科學,2009,36(9)：43-45.

[8] 劉方圓，嚴斌宇，張永齊，等.無線傳感器網絡的信任模型研究[J].計算機測量與控制,2011,19(5)：1232-1235.

[9] Li G H,Li H,Feng H L,et al.The Effect of Wireless Sensor Nodes Deployment Density in Forest Fire Monitoring Quality Evaluation[J].Journal of Networks,2012,7(7):1116-1122.

[10]付華,胡雅馨.一種改進的無線傳感器網絡信息融合技術[J].計算機系統(tǒng)應用,2010,19(7)：114-115.

[11]楊少軍,史浩山,劉利章.無線傳感器網絡分析與仿真[J].計算機工程,2006,32(22)：116-118.

Research and Improvement of Wireless Sensor Network Routing Protocol Based on LEACH

WANG Jun1,2, SUN Jian-cheng1

(1.Shenyang University of Chemical Technology, Shenyang 110142, China;2.Shenyang Institute of Automation,Chinese Academy of Sciences, Shenyang 110016, China)

In order to solve the shortness of LEACH routing protocol cluster head selection algorithm,an improved protocol based on LEACH is proposed to solve the problems of node trust value and Energy distribution imbalance.By calculating the trust value of the node,the new cluster head node is selected as standard.Finally,by the simulation analysis and comparison of performance,not only the algorithm can be used to meet the production needs and improve efficiency in the use of node energy,but also prolonge the network life cycle,The project figured out the problem that existed in balanced distribution of network energy distribution with the wireless sensor.

routing protocol； wireless sensor network； trust value； network life cycle

2013-12-18

中國科學院重點部署項目(KGZD-EW-302)；遼寧省工業(yè)公關項目(2012219001)；遼寧省教育廳項目(L2013157)

王軍(1978-),男,遼寧大連人,博士,副教授,主要從事工業(yè)無線網絡、網絡軟件進化方面的研究.

2095-2198(2015)04-0363-05

10.3969/j.issn.2095-2198.2015.04.014

TP393

A