基于節(jié)點剩余能量和最大角度的無線傳感器網(wǎng)絡(luò)路由算法*

曹海英，元 元，劉志強

(1.內(nèi)蒙古工業(yè)大學(xué) 信息工程學(xué)院，內(nèi)蒙古 呼和浩特010051;2.河套學(xué)院 理學(xué)系，內(nèi)蒙古 巴彥淖爾015001)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)可以感知，采集與處理監(jiān)測對象的信息，并將其傳遞給信息獲取方，因此，在環(huán)境監(jiān)測、災(zāi)害污染監(jiān)測、智能家居等領(lǐng)域都具有很高的應(yīng)用價值［1］。網(wǎng)絡(luò)路由主要完成信息從源節(jié)點傳送到目標(biāo)節(jié)點的任務(wù)，是實現(xiàn)網(wǎng)絡(luò)高效通信的基礎(chǔ)，因此，路由優(yōu)化成為一個具有挑戰(zhàn)性的問題［2］。為了解決傳感器路由優(yōu)化難題，國內(nèi)外學(xué)者對其進行了深入的研究，提出了許多的路由算法［3］。早期傳感器網(wǎng)路由算法一般將網(wǎng)絡(luò)劃分為均勻的簇，采用隨機分簇和周期性輪換策略，簇頭與基站采用單跳通信，距離基站越遠(yuǎn)的簇頭消耗的能量越大，易造成網(wǎng)絡(luò)生存時間縮短［4］。文獻［5］提出了非均勻分簇的思想，簇間采用多跳方式達到減少節(jié)點能耗的目的;文獻［6］提出基于蟻群算法的無線傳感器網(wǎng)絡(luò)路由機制，選擇找代價最小的多跳路由;文獻［7］提出基于據(jù)概率分層的無線傳感器路由算法，距離基站越近，族內(nèi)節(jié)點數(shù)越多;反之，相對較少，減少簇內(nèi)節(jié)點通信的能量開銷;文獻［8］提出了基于拓?fù)鋬?yōu)化控制的無線傳感器網(wǎng)絡(luò)路由算法，通過加權(quán)概率方式選擇簇頭，達到節(jié)點間的能量平衡。在無線傳感器網(wǎng)絡(luò)路由過程中，經(jīng)常會出現(xiàn)因節(jié)點能量不足而死亡現(xiàn)象，為此，要求一個好的路由協(xié)議必須具備良好的可靠性和容錯性［9］。文獻［10］提出了基于路由修復(fù)機制的路由算法，提高了數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

本文提出一種基于節(jié)點剩余能量和最大角度相融合的無線傳感器網(wǎng)絡(luò)路由算法，結(jié)合初始路由路徑的信息，通過設(shè)計的代價函數(shù)對出現(xiàn)故障的初始路由路徑進行局部自適應(yīng)修復(fù)，仿真結(jié)果表明:本文路由算法延長了整個網(wǎng)絡(luò)的存活時間。

1 無線傳感器網(wǎng)絡(luò)能耗模型

在無線傳感器網(wǎng)絡(luò)路由過程中，除了發(fā)送和接收數(shù)據(jù)包消耗的能量之外，其它能量消耗相對較小，因此，路由算法的節(jié)點能耗只考慮節(jié)點傳送(ETX)數(shù)據(jù)包和接收(ERX)數(shù)據(jù)包所消耗的能量［11］。因此當(dāng)兩個距離為d 的節(jié)點接收和發(fā)送l bit 數(shù)據(jù)時，ETX和ERX計算公式分別如下

其中，d0為距離閾值;Eelec為每接收、發(fā)送單位bit 所消耗的能量，εfx，εmp分別為功率放大所消耗的能量。

傳感器節(jié)點i 在所有狀態(tài)下的能量消耗為

2 無線傳感器路由算法設(shè)計

2.1 節(jié)點與匯聚節(jié)點的最大角度計算

在無線傳感器路由過程中，路由上的中間節(jié)點S 在選擇下一跳節(jié)點時，傳統(tǒng)方法忽略相鄰傳感器節(jié)點之間的角度關(guān)系，選擇的傳感器節(jié)點不一定最優(yōu)，因此，本文考慮相鄰節(jié)點之間的關(guān)系，在匯聚節(jié)點(Sink)一側(cè)選擇角度最大的傳感器節(jié)點，具體如圖1 所示。

圖1 最大角度計算的示意圖Fig 1 Diagram of the maximum angle calculation

從圖1 可知，無線傳感器網(wǎng)絡(luò)節(jié)點的角度計算方式具體如下

式中 i 為下一跳候選節(jié)點的序號;n 為通信范圍內(nèi)的相鄰節(jié)點的個數(shù);θ1表示夾角大小。

2.2 角度和節(jié)點剩余能量聯(lián)合設(shè)計

無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點能量十分有限，如何提高能量的利用率，盡量保持剩余能量最大化，是無線傳感器網(wǎng)絡(luò)路由算法設(shè)計的關(guān)鍵［12］。因此，本文路由算法把節(jié)點剩余能量作為路由選擇一個關(guān)鍵指標(biāo)，若路由的某個傳感器節(jié)點的剩余能量Eresidual小于預(yù)先設(shè)置的能量閾值Ethreshold，那么就需要替換該節(jié)點，重新初始無線傳感器的路由

式中 Einitial和E 分別為節(jié)點初始和消耗的能量。

在無線傳感器路由重新初始過程中，下一跳傳感器節(jié)點的路由選擇準(zhǔn)則具體如下

式中 i 為候選節(jié)點的序列號。

在無線傳感器路由開始階段，選擇剩余能量最大的節(jié)點作為下一跳節(jié)點，如果有多個剩余能量相同的節(jié)點，那么就選擇與匯聚角度最大的傳感器節(jié)點作為下一跳節(jié)點。

2.3 無線傳感器路由算法的工作步驟

1)在無線傳感器網(wǎng)絡(luò)的初始化階段，源傳感器節(jié)點向自己通信半徑范圍內(nèi)的全部鄰居節(jié)點發(fā)布相關(guān)信息，并根據(jù)式(4)和式(5)計算節(jié)點與匯聚節(jié)點的角度，然后根據(jù)計算結(jié)果選擇下一跳路由節(jié)點。

2)從當(dāng)前傳感器節(jié)點出發(fā)，然后根據(jù)式(4)和式(5)再次計算計算節(jié)點與匯聚節(jié)點的角度，并從候選傳感器節(jié)點集中選擇下一跳節(jié)點，不斷重復(fù)該操作，直到發(fā)布的相關(guān)信息到達匯聚節(jié)點。

3)根據(jù)已經(jīng)建立的路由路徑，匯聚節(jié)點將確認(rèn)信息發(fā)送到源節(jié)點，這樣就建立了無線傳感器網(wǎng)絡(luò)的初始路由路徑。

4)當(dāng)源節(jié)點有數(shù)據(jù)包需要傳輸時，那么就可以通過已經(jīng)建立好的初始路由路徑將數(shù)據(jù)包傳送至匯聚節(jié)點，并通過確認(rèn)機制提高數(shù)據(jù)包傳輸?shù)目煽啃浴?/p>

2.4 無線傳感器路由的修復(fù)

隨著無線傳感器網(wǎng)絡(luò)工作時間的延長，節(jié)點能量慢慢被消耗，初始路由路徑上的一些傳感器節(jié)點會因為能量耗盡而失效，影響信息傳輸?shù)目煽啃裕?3］。因此，本文采用路由修改算法對路由進行重新初始化，提高數(shù)據(jù)傳輸?shù)目煽啃裕唧w步驟如下:

1)當(dāng)某個傳感器節(jié)點的剩余能量小于預(yù)先設(shè)定的能量時，那么就從該傳感器節(jié)點的上一跳節(jié)點出發(fā)，利用公式(7)計算節(jié)點選擇的代價函數(shù)，并根據(jù)計算結(jié)果從鄰居節(jié)點集中選擇出最優(yōu)的傳感器節(jié)點對失效傳感器節(jié)點進行替換，其它節(jié)點不做處理，完成初始無線傳感器路由路徑的第一次修復(fù)。

2)隨著通信時間的不斷增加，無線傳感器路由過程中，繼續(xù)會出現(xiàn)一些能量低于預(yù)先設(shè)置能量閾值的傳感器節(jié)點，采用步驟(1)的方式對路由進行修改，直到初始無線傳感器網(wǎng)絡(luò)路由路徑所有低于能量閾值的傳感器節(jié)點均被替換掉。

3)路由修復(fù)完成。

無線傳感器路由修復(fù)過程具體如如圖2 所示。

3 仿真實驗

3.1 仿真場景參數(shù)

圖2 無線傳感器網(wǎng)絡(luò)路由的修復(fù)過程Fig 2 Repairing process of WSNs routing

為了測試本文無線傳感器路由算法的整體性能、有效性和實用性，在PIV 4 核2.80GHz CPU，4GRAM，Windows 7的操作系統(tǒng)上，采用Matlab 2012 仿真工具實現(xiàn)仿真實驗。為了使仿真實驗的結(jié)果更具說服力，選擇文獻［14，15］的無線傳感器路由算法進行對比實驗，從初始路由的節(jié)點跳數(shù)、節(jié)點的平均能耗、網(wǎng)絡(luò)生存時間等方面對它們性能進行綜合分析。不考慮無線通信鏈路的信號沖突和噪聲等因素，仿真參數(shù)如表1 所示。

表1 仿真場景參數(shù)Tab 1 Parameters of simulation scene

3.2 結(jié)果與分析

3.2.1 初始路由路徑選擇的比較

源節(jié)點和匯聚節(jié)點采用隨機方式部署，在給定的條件下，采用本文算法、文獻［14，15］的無線傳感器路由算法對初始路由路徑進行選擇，建立相應(yīng)的初始路由，結(jié)果如圖3所示，其中，□表示文獻［14］路由算法所建立的路徑;◇表示文獻［15］路由算法建立的路徑;○表示本文算法所建立的路徑，由圖3 可知，不同路由算法建立的路由路徑截然不同，本文初始路徑的跳數(shù)相對較少，可以加快數(shù)據(jù)傳輸速度，具有一定的優(yōu)勢。

圖3 不同算法建立的初始路由路徑Fig 3 Initial routing paths established by different algorithms

在傳感器節(jié)點數(shù)目為25～200 的情況，所有無線傳感器網(wǎng)絡(luò)路由算法的路徑跳數(shù)變化結(jié)果如圖4 所示。從圖4 可知，隨著傳感器節(jié)點數(shù)目逐漸增加，各路由算法的跳數(shù)也發(fā)生相應(yīng)的變化，但跳數(shù)并不一定增加，本文路由算法建立的路由跳數(shù)小于對比算法建立的路由路徑跳數(shù)，獲得更加理想的數(shù)據(jù)路由。

圖4 不同算法路由跳數(shù)的對比Fig 4 Comparison of routing hops of different algorithms

3.2.2 節(jié)點的平均能耗

不同無線傳感器路由算法的節(jié)點平均能量消耗變化趨勢如圖5 所示。從圖5 可知，隨著傳感器節(jié)點數(shù)量的增加，網(wǎng)絡(luò)節(jié)點的平均能耗發(fā)生相就的波動，文獻［14，15］的節(jié)點平均能耗變化幅度比較大，極不穩(wěn)定，對整個無傳感器網(wǎng)絡(luò)的生命時間產(chǎn)生不利影響。而本文路由算法的節(jié)點平均能耗變化比較平穩(wěn)，網(wǎng)絡(luò)節(jié)點平均能遠(yuǎn)遠(yuǎn)小于對比算法的平均節(jié)點能耗，這主要是由于本文算法對數(shù)據(jù)傳輸路徑進行了修復(fù)，當(dāng)一些剩余能量低于閾值的傳感器節(jié)點進行替換，并重新初始化路由，保證了網(wǎng)絡(luò)通信的可靠性和穩(wěn)定性。

圖5 網(wǎng)絡(luò)節(jié)點平均能耗的比較Fig 5 Comparison of average energy consumption of network nodes

3.2.3 無線傳感器網(wǎng)絡(luò)生存時間的比較

無線傳感器網(wǎng)絡(luò)的生存時間定義為網(wǎng)絡(luò)中第一個傳感器節(jié)點的死亡時間，用輪數(shù)來表示，不同路由算法的無線傳感器網(wǎng)絡(luò)的生存時間變化情況如圖6 所示。從圖6 可以看出:相對于對比路由算法，本文路由算法有效延長了無線傳感器網(wǎng)絡(luò)的生存時間，較好地解決了當(dāng)前無線傳感器網(wǎng)絡(luò)路由算法存在的不足，使得網(wǎng)絡(luò)的能耗更加均衡，提高了數(shù)據(jù)傳輸?shù)目煽啃裕哂懈叩膶嵱脙r值。

4 結(jié)束語

針對當(dāng)前無線傳感器網(wǎng)絡(luò)路由算法存在的缺陷，本文提出了一種綜合考慮節(jié)點剩余能量和最大角度的無線傳感器網(wǎng)絡(luò)路由優(yōu)化算法。首先根據(jù)能量、角度等準(zhǔn)則建立無線傳感器網(wǎng)絡(luò)的初始路由路徑，然后對網(wǎng)絡(luò)中的失效節(jié)點進行替換，修復(fù)相應(yīng)的路由路徑，最后采用仿真實驗測試算法的有效性和優(yōu)越性，仿真結(jié)果表明:本文可以更加均衡傳感器節(jié)點的能量消耗，延長了網(wǎng)絡(luò)的生存時間，顯著改善了網(wǎng)絡(luò)的性能，更加適應(yīng)適合規(guī)模較大的無線傳感器網(wǎng)絡(luò)。

圖6 不同算法的網(wǎng)絡(luò)生存時間對比Fig 6 Comparison of network survival time of different algorithms

［1］ Giuseppe A，Marco C，Mario D F.Energy conservation in wireless sensor networks:A survey［J］.Ad Hoc Networks，2009，7(3):537－568.

［2］ Baumgartner K，F(xiàn)errari S.A geometric transversal approach to analyzing trunk coverage in sensor network［J］.IEEE Transactions on Computers，2008，57(8):1113－1128.

［3］ Liang H F，Qian J S，Sun Y L，et al.Energy optimal routing for long chaintype wireless sensor networks in under ground mines［J］.Mining Science and Technology(China)，2011(17):17－21.

［4］ Younis O，F(xiàn)ahmy S.A hybrid，energy－efficient distributed clustering approach for Ad－Hoc sensor networks［J］.IEEE Transaction on Mobile Computing，2011，3(4):366－379.

［5］ Li Q，Zhu Q X，Wang M W.Design of a distributed energy－efficient clustering algorithm for heterogeneous wireless sensor networks［J］.Computer Communications，2006，29(12):2230－2237.

［6］ Li Q，Zhang B H，Cui L G，et al.Immunizations on small worlds of tree－based wireless sensor networks［J］.Chinese Phys B，2012，21(5):1－9.

［7］ 江禹生，李 萍，馬 超.一種能量高效的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǎ跩］.傳感器與微系統(tǒng)，2014，33(2):146－149.

［8］ Hoon O，Han T D.A demand－based slot assignment algorithm for energy－aware reliable data transmission in wireless sensor networks［J］.Wireless Networks，2012，18(5):523－534.

［9］ Lindsey S，Raghavendra C，Krishna M.Data gathering algorithms in sensor networks using energy metrics［J］.IEEE Transactions on Parallel and Distributed Systems，2011，13(9):924－935.

［10］朱全政，楊 樂.能量角度聯(lián)合自適應(yīng)路由修復(fù)新算法［J］.計算機應(yīng)用研究，2014，31(6):1779－1783.

［11］Lu X J，Ding Y S，Hao K R.Immune colonel selection algorithm for target coverage of wireless sensor networks［J］.Int’l J Modeling，Identification and Control，2011，12(1):119－124.

［12］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application－specific protocol architecture for wireless micro－sensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［13］Helio M S，Claudio M，Paula L，et al.Intrusion detection system for wireless sensor networks using danger theory immune－inspired techniques［J］.International Journal of Systems Science，2012，23(10):1－28.

［14］Nam C S，Han Y S，Shin D R.Multi－h(huán)op routing based optimization of the number of cluster heads in wireless sensor networks［J］.Sensors，2011，11(3):2875－2884.

［15］Zytoune O，F(xiàn)akhri Y，Aboutajdine D.A fairly balanced clustering algorithm for routing in wireless sensor networks［J］.Sensor Review，2010，30(3):242－249.