基于節點剩余能量和最大角度的無線傳感器網絡路由算法*

曹海英，元 元，劉志強

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

0 引 言

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

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

1 無線傳感器網絡能耗模型

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

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

傳感器節點i 在所有狀態下的能量消耗為

2 無線傳感器路由算法設計

2.1 節點與匯聚節點的最大角度計算

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

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

從圖1 可知，無線傳感器網絡節點的角度計算方式具體如下

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

2.2 角度和節點剩余能量聯合設計

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

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

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

式中 i 為候選節點的序列號。

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

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

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

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

3)根據已經建立的路由路徑，匯聚節點將確認信息發送到源節點，這樣就建立了無線傳感器網絡的初始路由路徑。

4)當源節點有數據包需要傳輸時，那么就可以通過已經建立好的初始路由路徑將數據包傳送至匯聚節點，并通過確認機制提高數據包傳輸的可靠性。

2.4 無線傳感器路由的修復

隨著無線傳感器網絡工作時間的延長，節點能量慢慢被消耗，初始路由路徑上的一些傳感器節點會因為能量耗盡而失效，影響信息傳輸的可靠性［13］。因此，本文采用路由修改算法對路由進行重新初始化，提高數據傳輸的可靠性，具體步驟如下:

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

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

3)路由修復完成。

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

3 仿真實驗

3.1 仿真場景參數

圖2 無線傳感器網絡路由的修復過程Fig 2 Repairing process of WSNs routing

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

表1 仿真場景參數Tab 1 Parameters of simulation scene

3.2 結果與分析

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

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

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

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

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

3.2.2 節點的平均能耗

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

圖5 網絡節點平均能耗的比較Fig 5 Comparison of average energy consumption of network nodes

3.2.3 無線傳感器網絡生存時間的比較

無線傳感器網絡的生存時間定義為網絡中第一個傳感器節點的死亡時間，用輪數來表示，不同路由算法的無線傳感器網絡的生存時間變化情況如圖6 所示。從圖6 可以看出:相對于對比路由算法，本文路由算法有效延長了無線傳感器網絡的生存時間，較好地解決了當前無線傳感器網絡路由算法存在的不足，使得網絡的能耗更加均衡，提高了數據傳輸的可靠性，具有更高的實用價值。

4 結束語

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

圖6 不同算法的網絡生存時間對比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，Ferrari 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，Fahmy 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］ 江禹生，李 萍，馬 超.一種能量高效的無線傳感器網絡拓撲控制算法［J］.傳感器與微系統，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］朱全政，楊 樂.能量角度聯合自適應路由修復新算法［J］.計算機應用研究，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－hop routing based optimization of the number of cluster heads in wireless sensor networks［J］.Sensors，2011，11(3):2875－2884.

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