WSN中基于鏈路質量和節點能量的AODV路由算法研究*

杜海韜，李　強，丁廣太，王營冠，朱磊基

（1.上海大學計算機工程與科學學院，上海200444；2.中國科學院上海微系統所與信息技術研究所，上海201899；3.上海物聯網有限公司，上海201899）

WSN中基于鏈路質量和節點能量的AODV路由算法研究*

杜海韜1，2，李強2，3*，丁廣太1，王營冠2，朱磊基3

（1.上海大學計算機工程與科學學院，上海200444；2.中國科學院上海微系統所與信息技術研究所，上海201899；3.上海物聯網有限公司，上海201899）

為了滿足無線傳感網絡能量的高效使用以及數據傳輸的穩定性的要求，需要對無線傳感網絡路由層協議進行改進。本文提出一種基于節點之間鏈路質量和節點能量狀態的LE-AODV路由協議，LE-AODV路由協議采用跨層設計，路由發現過程中通過MAC層和物理層獲取鏈路質量信息和節點能量信息來選取最優路徑，并通過節點能量狀態更新機制避免網絡中熱點的產生。本文使用Castalia仿真器對LE-AODV路由協議進行仿真，仿真結果表明，LE-AODV路由協議可以有效的提高分組投遞率和網絡生存時間。

無線傳感網絡；鏈路質量；節點能量；LE-AODV路由協議；Castalia仿真器

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.07.016

無線傳感網絡WSN（Wireless Sensor Network）［1］是隨著無線通信技術、嵌入式計算技術、傳感器技術和網絡技術的發展出現的一種新型的數據監控網絡，被認為是21世紀最重要的技術之一，它能夠實施監測、感知和采集網絡分布區域內各種環境或監測對象的信息，并對其進行合理的處理，獲得詳盡而準確的現場信息。WSN由于其快速展開、自組網、抗毀性強、檢測精度高、覆蓋區域大等特點，在軍事通信安防監控，城市交通管理，家庭保健，環境監測，搶險，遠程控制等許多領域都有重要的科研價值和巨大的使用價值。目前WSN的研究主要集中在網絡層和鏈路層，網絡層路由協議和算法是WSN研究熱點。WSN與傳統無線網絡有很大不同，傳統網絡路由協議設計目標是降低通訊延遲，提高網絡帶寬利用率，進行流量控制，而WSN由于具有分布式、節點能量有限、通訊鏈路容易受環境影響等特點，因此WSN路由協議更加關注網絡能量的高效使用以及數據傳輸的穩定性［2］。本文結合WSN的特點對AODV（Ad Hoc on Demand Distance Vector）［3］路由協議進行了改進，提出了基于鏈路質量和節點能量的LE-AODV（AODV Routing Dased on Link Quality and Energy）路由協議，改進了AODV路由協議的路由發現過程和選取路徑的機制，提高了數據傳輸的穩定性，使網絡中節點能量消耗更加均衡，延長了網絡生存時間［4］。

1　相關工作

AODV路由協議是一種反應式按需路由協議［5］。當一個節點需要一條路由時，它通過廣播路由請求RREQ（Route Request）消息啟動路由發現過程，每個節點轉發RREQ消息直到這個節點存在到目的節點的路徑或者這個節點就是目的節點，這時這個節點會發送一個路由回復RREP（Route Replay）消息給源節點并忽略之后從其他路徑發送過來的RREQ消息，因此AODV路由協議路由發現過程中選取的是最短路徑。這樣的路由發現過程存在以下不足之處：首先，最短路徑意味著路由跳數較少，那么節點之間的距離較長，長距離的鏈路質量較差，容易受到噪聲和干擾的影響而造成丟包；其次，AODV路由協議沒有對點能量消耗進行管理，容易在網絡中產生熱點現象［6］，如圖1所示，由于選取最短路徑，節點6～節點8都通過節點5向Sink節點發送信息，節點5被過度使用了，造成節點5能量消耗過快，使整個網絡的能量消耗分布不均衡，最終在網絡中產生能量空洞；最后，對于給定的目的節點，AODV路由協議只保存一條最短路徑，如果這條路徑失效了，那么必須重新進行路由發現過程，這樣會需要更多的時間造成發包的遲延。因此AODV路由協議路由發現的過程和選取最短路徑的機制不能滿足WSN對能量的高效使用以及數據傳輸的穩定性的要求。

圖1　熱點現象

目前WSN中對AODV路由協議主要有以下一些改進，L-AODV［7］是基于鏈路質量的改進的 AODV路由協議，L-AODV使用 LQI［8］（Link Quality Indicator）來表示鏈路質量，通過設定一個LQI閾值LQIth來判斷鏈路的好壞，LQI值低于這個LQI閾值的鏈路是差的鏈路，LQI值高于這個LQI閾值的鏈路是好的鏈路。在路由發現的過程中對路徑中差的鏈路的數量進行統計，并在RREQ消息和RREP消息中添加一個Link字段來記錄這個值，通過比較Link值的大小來選取路徑。L-AODV選取是鏈路質量最好的路徑提高了網絡數據傳輸的穩定性，但是由于L-AODV沒有考慮節點能量，網絡中仍然會產生熱點，造成網絡能量消耗不均衡。E-AODV［9］是基于能量的改進的AODV路由協議，E-AODV考慮整條路徑的能量消耗和整條路徑中節點的最低能量狀態，E-AODV在RREQ中添加了一個字段來記錄路徑中節點的最低能量狀態，通過設定一個Energy閾值Eth來判斷路徑中是否有節點被過度使用而成為熱點。當一個節點在t時刻能量狀態為E（t），如果E（t）與t-1時刻的能量狀態E（t-1）的差值大于Eth，那么說明該節點發生了熱點現象，如果某條路徑中存在熱點，則選擇其他路徑。EAODV提高了網絡能量消耗的均衡性，延長了網絡生存時間，但是由于E-AODV沒有考慮節點之間的鏈路質量，因此E-AODV的數據傳輸穩定性不佳。

綜上所述，本文結合WSN的特點，采用跨層的設計［10］，如圖2，依據物理層和MAC層提供的具體的鏈路信息和節點能量信息，提出了基于鏈路質量和節點能量的LE-AODV路由協議。仿真實驗將LE-AODV路由協議與AODV、L-AODV、E-AODV路由協議進行比較，結果表明，LE-AODV路由協議能有效改善網絡能量消耗均衡性，延長了網絡生存時間，提高了數據傳輸穩定性。

圖2　跨層設計

2　AODV路由協議算法改進

2.1路由發現和最優路徑選取機制

LE-AODV路由協議在路由發現過程中，發送的RREQ消息通過物理層和MAC層獲得節點之間的鏈路質量LQI和節點的剩余能量，在RREQ消息中添加Link和Energy這兩個字段，Link表示路徑中鏈路質量較差的鏈路的數量Q，Energy表示路徑中最低節點能量狀態E，LE-AODV路由協議RREQ消息幀格式如表1所示。LE-AODV路由協議路由表中存儲多條到達目的節點的路徑，當一個節點需要發送數據包到目的節點時，該節點會從路由表中選取一條最優路徑。

表1　RREQ消息幀格式

①低質量鏈路數Q［11］：

假設一條路徑L的跳數為N+1，則L經過N個中間節點，節點i與節點i+1之間鏈路質量L為：

整條路徑中低質量鏈路數Q為：

設定LQI閾值為LQIth，當L＞LQIth時，節點之間鏈路數據傳輸穩定，不容易丟包，當L＜LQIth時，節點之間鏈路數據傳輸不穩定，容易丟包。LQI閾值LQIth可由實際場景下的實驗得到，當節點之間鏈路的分組投遞率PDR［9］（Packet Delivery Radio）達到80%以上時，說明這條鏈路傳輸數據是穩定的，取此時鏈路的LQI值作為LQIth閾值。鏈路的LQI值容易受環境的影響，在實際的室內場景中，使用CC2420芯片作為WSN工作節點，實驗測得LQI值與PDR之間的關系如圖3所示，取LQIth值為220。

圖3　CC2420分組投遞率PDR與LQI之間的關系

②路徑中最低節點能量狀態E［12］：

中間節點i的能量狀態為節點剩余能量和初始能量的比值：

整條路徑中節點最低能量狀態為：

③路徑跳數差H［13］：

假設一個節點到目的節點還存在一條路徑L1，L1的跳數為M+1，則L與L1的跳數差H為：

在LE-AODV路由協議中最優路徑的選取機制中，對于同一個目的節點，可能存在多條路徑，設定一個跳數差閾值Hth，路徑之間的跳數差不能超過Hth。Hth是對新發現路徑跳數的限制，如果沒有對路徑的跳數進行限制，在LE-AODV路由協議的路由發現過程中，節點會收到大量路由回復RREP消息，RREP消息的爆炸性增長會降低路由發現的效率，同時路徑的數量并不是越多越好。Hth越大，路由發現過程中產生的可選路徑越多，考慮到在實際的應用場景中，如果整個網絡的節點數較少，可以取Hth值為2，如果整個網絡的節點數量較多達到上百個節點，Hth的值需要通過仿真實驗來確定。

LE-AODV路由協議最優路徑選取綜合考慮路徑中路徑中鏈路質量較差的鏈路的數量Q和節點最低能量狀態E以及路徑之間的跳數差H，算法流程圖如圖4所示。

由圖4可知，當路由發現過程中發現了一條到達目的節點新的路徑B，將路徑B與當前正在使用的最優路徑A進行比較。如果路徑A和路徑B的節點最低能量狀態相等，那么需要比較路徑A和路徑B的跳數HA、HB，如果路徑B的跳數HB大于路徑A的跳數HA，那么顯然路徑A仍為最優路徑，路徑B的跳數多會比路徑A消耗更多的能量，如果路徑B的跳數HB小于路徑A的跳數HA，這時需要使用跳數差閾值Hth對跳數進行限制，如果滿足HA-HB＞Hth且路徑A的低質量鏈路數QA大于等于路徑B的低質量鏈路數QB，那么路徑B為最優路徑；當路徑A的節點最低能量狀態小于路徑B時，如果滿足HB-HA＜Hth且路徑A的低質量鏈路數QA大于等于路徑B的低質量鏈路數QB，此時選擇路徑B為最優路徑；當路徑A的節點最低能量狀態大于路徑B時，如果滿足路徑A的低質量鏈路數QA大于等于路徑B的低質量鏈路數QB且HA-HB＞Hth時，此時路徑B為最優路徑。最優路徑選取算法綜合考慮了可選路徑的跳數，路徑中節點的能量狀態以及整條路徑的鏈路質量。

圖4　LE-AODV路由協議最優路徑選取算法流程圖

2.2節點能量狀態更新機制

在LE-AODV路由協議中，節點周期性的維護自身的能量狀態和周圍鄰居節點的能量狀態，并通過發送EnergyPacket數據包來更新自身能量狀態和鄰居節點的能量狀態，EnergyPacket數據包幀格式如表2所示。設定一個能量狀態變化閾值Eth，在t時刻節點的能量狀態為E（t），如果E（t）與t-1時刻的能量狀態E（t-1）的差值大于Eth，，說明自身能量消耗過快，發生了熱點現象，那么該節點通過發送EnergyPacket數據包來更新鄰居節點中自身的能量狀態，并且更新相關路由表中路徑的最低節點能量狀態。Eth的值需要通過仿真實驗確定，如果Eth過大，那么節點不能感知到熱點的產生，會造成能量消耗的不均衡，如果Eth過小，那么節點需要發送更多的EnergyPacket數據包來進行節點能量的更新，會消耗更多的節點能量。

表2　EnergyPacket數據包幀格式

節點能量狀態更新機制流程圖如圖5所示。

圖5　節點能量狀態更新機制

3　仿真過程與結果分析

本文采用Castalia仿真器［14］對LE-AODV路由協議和AODV、E-AODV、L-AODV路由協議進行仿真對比實驗，分別從節點能量消耗、分組投遞率PDR、網絡生存時間、節點存活數量這幾個方面進行比較分析，驗證了LE-AODV路由算法可以提高網絡能量利用率，延長網絡生存時間，提高數據傳輸穩定性。Castalia仿真器是Linux操作系統下的、基于OMNET++平臺的、針對WSN場景的低能耗嵌入式設備仿真器，本文使用的Castalia仿真器版本為Castalia-3.2。在仿真過程中設計了兩種仿真場景：仿真場景一仿真區域較小，節點數較少，模擬室內場景，通過對比分析不同Eth值情況下LE-AODV路由協議的網絡生存時間，確定Eth的值；仿真場景二仿真區域較大，節點數較多，模擬室外場景，通過比較分析不同Hth值情況下LE-AODV路由協議的分組投遞率，來選取合適的Hth值。

仿真場景一仿真參數如表3所示。

表3　仿真場景一參數表

Eth取不同的值時，LE-AODV路由協議網絡中平均能量狀態隨時間變化的關系如圖6所示。

由圖6可以發現當Eth大于6時，網絡的生存時間反而降低了，這是因為Eth較大時，LE-AODV路由協議并不能及時發現成為熱點的節點，整個網絡的能量消耗會不均勻，導致了網絡生存時間的降低。Eth=2時的網絡生存時間比Eth=4時的網絡生存時間多2 min，Eth=2時的網絡生存時間最高，因此取Eth=2。

圖6　不同Eth下網絡平均能量狀態隨時間變化的關系

取 Eth=2，在上述仿真場景下仿真 AODV、E-AODV、L-AODV和LE-AODV路由協議，仿真時間為12 min，圖7和圖8分別為節點的分組投遞率PDR和節點的能量狀態。

由圖7、圖8可以發現LE-AODV、E-AODV、LAODV路由協議中節點的分組投遞率PDR和節點能量狀態都要高于AODV路由協議。LE-AODV路由協議中節點的分組投遞率PDR與L-AODV路由協議接近，LE-AODV路由協議中節點能量狀態與E-AODV路由協議接近，同時在AODV路由協議中，節點5的分組投遞率最低，這因為AODV路由協議選取的是最短路徑，節點（7、8、9）向節點5發送的數據包較多，造成了節點5分組投遞率的降低，結合圖7可以發現節點5的能量狀態也最低，說明節點5需要轉發更多的數據包，消耗更多的能量。圖7和圖8說明E-AODV路由協議能提高網絡能量利用率，但是由于E-AODV路由協議沒有考慮鏈路質量，因此E-AODV路由協議不能改善網絡數據傳輸的穩定性，L-AODV路由協議提高了網絡數據傳輸的穩定性，但是由于沒有考慮節點能量，因此L-AODV沒有改善網絡能量的利用率，而LE-AODV路由協議由于綜合考慮了鏈路質量和節點能量，因此LE-AODV路由協議不僅可以提高網絡能量利用率也能提高網絡數據傳輸的穩定性。

圖7　節點的分組投遞率對比圖

圖8　節點能量狀態對比圖

仿真場景二仿真參數如表4。

表4　仿真場景二參數表

在仿真節點數量為100時，取不同Hth值，通過比較分析不同Hth值情況下LE-AODV路由協議的分組投遞率，來選取合適的Hth值，仿真結果如圖9所示。當Hth取不同值時，整個網絡的分組投遞率都超過了80%，當Hth值從2增加到5時，整個網絡的分組投遞率逐漸增加，而當Hth值繼續增加時，整個網絡的分組投遞率開始降低，這說明Hth值增加，備選路徑的數量也會增加，雖然LE-AODV路由協議最優路徑選取的算法可以選取到最優路徑，但是較多備選路徑和產生的大量的路由回復信息RREP會增加整個網絡的延遲，降低整個網絡的生存時間。因此綜合考慮分組投遞率和整個網絡的效率，Hth值可以取5。

圖9　不同Hth取值LE-AODV路由協議的分組投遞率

取Hth值為5，設定仿真時間設為60 min，改變節點的數量，圖10為不同節點數量情況下的網絡生存時間。由圖10可知，節點數量的增加會增加網絡生存時間，這是因為更多的節點提供了更多的路徑選擇，LE-AODV、E-AODV路由協議的網絡生存時間要高于AODV、L-AODV路由協議。在圖10中，在節點數量為120時，LE-AODV路由協議的網絡生存時間為58 min，AODV路由協議的網絡生存時間為42 min，網絡生存時間增加了16 min，在節點數量為60時，LE-AODV路由協議的網絡生存時間為51 min，AODV路由協議的網絡生存時間為41 min，網絡生存時間增加了10 min。隨著節點數量的增加，LE-AODV路由協議能增加更多的網絡生存時間。LE-AODV、E-AODV路由協議由于考慮了節點能量，避免了網絡中發生熱點現象，延長了網絡生存時間，但是由于E-AODV路由協議沒有最優路徑的選取機制，E-AODV路由協議需要頻繁的發起路由發現的過程，因此會消耗額外的能量，導致E-AODV路由協議的網絡生存時間要低于LE-AODV路由協議。

圖10　網絡生存時間對比圖

圖11為不同節點數量情況下分組投遞率PDR。由圖11可知，隨著節點數的增加，網絡的分組投遞率會降低，這是因為節點數量增加后，路徑的跳數會增加，跳數增加后提高了丟包的可能性導致了分組投遞率的下降。在圖11中，LE-AODV、L-AODV路由協議的分組投遞率要高于AODV、E-AODV路由協議，說明AODV、E-AODV路由協議由于沒有考慮鏈路質量，選取的路徑丟包的可能性增加，因此分組投遞率低于LE-AODV、L-AODV。LE-AODV路由協議的分組投遞率要高于L-AODV路由協議，這是因為L-AODV路由協議僅考慮了鏈路質量，因此L-AODV路由協議路由發現過程中可能選取到跳數比較多的路徑，跳數比較多的路徑也會降低分組投遞率，而LE-AODV路由協議由于有最優路徑選取的機制，閾值Hth限制了LE-AODV路由協議路徑的跳數，隨著節點數量的增加，LE-AODV路由協議仍能保持較高的分組投遞率，保證了數據傳輸的穩定性。

圖11　分組投遞率對比圖

4　總結

本文針對WSN對網絡能量的高效使用以及數據傳輸的穩定性的要求，考慮節點之間鏈路質量和節點能量，對AODV路由協議進行改進，提出了基于鏈路質量和節點能量的LE-AODV路由協議。在路由發現過程中選取鏈路質量較高的鏈路，通過最優路徑選取的機制對路徑的最低節點能量狀態和跳數進行限制，節點能量狀態更新機制避免了網絡中熱點的產生。仿真結果顯示，LE-AODV路由協議能夠延長網絡生存時間，提高分組投遞率，從而保證了WSN網絡能量的高效使用和數據傳輸的穩定性。在本文的研究中，在不同節點數量情況下，路徑跳數差Hth閾值的取值對最優路徑選取的影響以及在不同的環境情況下，LQIth閾值的設定對路由發現過程的影響還需要進行深入研究。在后續的工作中，需要針對不同Hth閾值和LQIth閾值對路由選取和路徑發現的影響進行進一步的研究。

［1］ 錢志鴻，王義君.面向物聯網的無線傳感器網絡綜述［J］.電子與信息學報，2013（1）：215-227.

［2］ 王境，徐楨，劉曉春.基于鏈路質量的無線傳感器網絡抗干擾路由協議［J］.傳感技術學報，2012，25（1）：87-93.

［3］ 王巍，李叢，王云.基于WSN的AODV路由協議的研究與改進［J］.計算機與現代化，2012（11）：182-185.

［4］ 路綱，周明天，佘堃.無線傳感器網絡路由協議的壽命分析［J］.軟件學報，2009，20（2）：375-393.

［5］ Ren J，Zhang Y，Zhang K，et al.Lifetime and Energy Hole Evolution Analysis in Data-Gathering Wireless Sensor Networks［J］. IEEE Transactions on Industrial Informatics，2015：1.

［6］ 孫彥景，林昌林，江海峰.一種能量高效的分布式非均勻分簇路由算法［J］.傳感技術學報，2015，28（8）：1194-1200.

［7］ Butt M R，Akbar A H，Kim K H，et al.LABILE：Link Quality-Based Lexical Routing Metric for REactive Routing Protocols in IEEE 802.15.4 Networks［J］.Journal of Supercomputing，2012，62（1）：84-104.

［8］ Standard I.Wireless Medium Access Control（MAC）and Physical Layer（PHY）Specifications for Low-Rate Wireless Personal Area Networks（LR-WPANs）［C］.IEEE Std.2010.

［9］ Samundiswary P，Bhardwaj H.Performance Analysis of Energy Aware AODV Routing Protocol For IEEE 802.15.4 Enabled WSN［J］.International Journal of Computer Applications，2013，63（19）：43-46.

［10］Mammu A S，Hernandez-Jayo U，Sainz N，et al.Cross-Layer Cluster-Based Energy-Efficient Protocol for Wireless Sensor Networks［J］.Sensors，2015，15（4）：8314-8336.

［11］Gomez C，Boix A，Paradells J.Impact of LQI-Based Routing Metrics on the Performance of a One-to-One Routing Protocol for IEEE 802.15.4 Multihop Networks［J］.Eurasip Journal on Wireless Communications&Networking，2010，4（2）：50-50.

［12］劉大勇，趙春江.基于AODV的農田無線傳感器網絡路由和休眠算法［J］.微電子學與計算機，2015（10）：115-120.

［13］Farooq H，Jung L T.Energy，Traffic Load，and Link Quality Aware Ad Hoc Routing Protocol for Wireless Sensor Network Based Smart Metering Infrastructure［J］.International Journal of Distributed SensorNetworks，2013，13：264-273.

［14］Boulis A.Castalia a Simulator for Wireless Sensor Networks and Body Area Networks，Version 3.2，User'smanual［EB/OL］.http：// castalia.npc.nicta.com.au/.

杜海韜（1988-），男，碩士研究生。研究領域為無線傳感網絡路由協議的優化與應用，banehallow@126.com；

李強（1973-），男，山東煙臺人，博士，研究員。研究方向為移動通信、超寬帶、物聯網技術、數據融合等，liqiang@mail.sim.ac.cn；

丁廣太（1966-），男，博士，副教授，研究領域為數字圖像處理。

The Research of AODV Routing Protocol Based on Link Quality and Node Energy in WSN*

DU Haitao1，2，LI Qiang2，3*，DING Guangtai1，WANG Yingguan2，ZHU Leiji3
（1.School of Computer Engineering and Science，Shanghai University，Shanghai 20044，China；2.Shanghai Institute of Microsystem and Information Technology Chinese Academy of Sciences，Shanghai 201899，China；3.Shanghai Internet of Things CO.LTD，Shanghai 201899，China）

In order to meet the demands of energy efficiency use and data transmission stability，the routing protocol of the wireless sensor network needs to be further improved.This paper proposes a LE-AODV routing protocol based on the link quality and energy status of node.The LE-AODV routing protocol adopts the cross-layer design. During the route discovery process，optimal path is selected by acquiring the link quality information and the node energy information from MAC layer and physical layer.Meanwhile，hot spots in the network will be avoided by the node energy status updating mechanism.In this paper，the Castalia simulator is applied to accomplish the simulation of the LE-AODV routing protocol.The research result shows that the LE-AODV routing protocol can effectively improve the packet delivery rate and prolong the network lifetime.

wireless sensor network；link quality；node energy；LE-AODV routing protocol；castalia simulator

TP393

A

1004-1699（2016）07-1042-07

項目來源：上海市浦江人才計劃項目（14PJ1433100）

2016-01-16修改日期：2016-02-24