曹海英，元 元，劉志強(qiáng)

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

0 引 言

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

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

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

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

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

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

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

2.1 節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的最大角度計(jì)算

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

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

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

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

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

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

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

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

式中 i 為候選節(jié)點(diǎn)的序列號(hào)。

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

2.3 無(wú)線傳感器路由算法的工作步驟

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

3.1 仿真場(chǎng)景參數(shù)

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

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

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

3.2 結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

圖6 不同算法的網(wǎng)絡(luò)生存時(shí)間對(duì)比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ú)線傳感器網(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］朱全政，楊 樂(lè).能量角度聯(lián)合自適應(yīng)路由修復(fù)新算法［J］.計(jì)算機(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.