2001年，Kyungate Woo等人提出了LEAR（Local Energy-Aware Routing）算法。LEAR算法是一種能量均衡路由算法，它儘量讓網路中的所有節點能量消耗儘量均衡，以延長網路壽命。
基本介紹
- 中文名：本地能量感知的路由協定
- 外文名：Local Energy-Aware Routing
- 外語縮寫：LEAR
- 類型：路由算法
- 用途：用於能量均衡
基本思想,關鍵技術問題,LEAR算法描述,總結,
基本思想
LEAR算法基於DSR路由協定。DSR路由協定包含兩個過程：路由發現和路由維護，LEAR對DSR的路由發現過程進行改進，考慮能量在所有節點中的均衡消耗。尋找路徑時，每個移動節點依據本地剩餘電池能量（Er）信息來決定是否參與路由發現過程。能量充足的節點（Er大於門限Thr）轉發ROUTE_REQ訊息，參與路由發現過程，並把該節點的標識加入該訊息頭中；能量匱乏的節點（Er<Thr）丟棄ROUTE_REQ訊息，不參與路由發現過程，以保存自己的能量。ROUTE_REQ訊息到達目的節點後，目的節點不需要等待，一旦收到第一個到達的ROUTE_REQ訊息，就立即向源節點發回ROUTE_REPLY訊息，該訊息中攜帶有到達目的節點的路徑。由於利用了路由快取，會有多個節點向源節點傳送ROUTE_REPLY訊息，源節點只對第一個到達的訊息做出反應，並沿著該訊息中攜帶的路由向目的節點傳送數據。
關鍵技術問題
LEAR方案中，每個節點是否接收並轉發ROUTE_REQ訊息取決於它的剩餘電池能量Er:Er大於門限Thr時，節點轉發ROUTE_REQ訊息；否則，丟棄ROUTE_REQ訊息。只有這條路徑上所有中間節點電池能量都比較充足時，ROUTE_REQ訊息才會到達目的節點。在選擇路徑時，只對第一個到達的ROUTE_REQ訊息做出反應，這樣，選擇的路徑的節點能量充足，並且時延最短。而最初的DSR協定最佳化了跳數，並沒有考慮均衡所有節點能量消耗的問題。
但是，這樣做存在一個問題，當一個中間節點的電池能量小於門限值，即Er<Thr，就丟棄ROUTE_REQ分組，如果每條可能的路徑都發生了這樣的情況，即使源和目的節點之間有一條路徑，源節點也不會接收到一個應答訊息。這個問題的解決辦法是：源節點增加序列號，重新傳送同樣的路由請求訊息。當中間節點接收到這個增加了序列號的請求訊息後，把它的Thr調低d，這樣就可以繼續轉發該訊息了。但是這樣做又存在級聯效應問題。而且，由於中間節點不知道快取中節點的能量信息，就不能利用路由快取向源節點發回ROUTE_REPLY訊息。
為了解決級聯效應和路由快取這兩個問題，增加了4個控制訊息：DROP_ROUTE_REQ,ROUTE_CACHE，DROP_ROUTE_CACHE和CANCEL_ROUTE_CACHE。
1、級聯效應
如圖1-1(a)所示，當源節點S傳送ROUTE_REQ訊息尋找到達目的節點D的路徑時，如果中間節點A、B、C1、C2的Er都小於門限Thr，節點A就會丟棄該請求訊息，S就增加序列號，重新傳送ROUTE_REQ訊息，節點A發現這個訊息增加了序列號，就調低它的能量門限並轉發該訊息，但是這次節點B又丟棄它，這樣，目的節點D在第五次路由發現過程時，才會收到ROUTE_REQ訊息，把這種現象稱為級聯效應。DROP_ROUTE_REQ訊息就是為了解決這個問題，如圖1-1(b)所示。當節點A丟棄ROUTE_REQ訊息時，轉發（廣播）一個DROP_ROUTE_REQ訊息，後面的節點就知道丟棄了一個請求訊息，當收到第二個ROUTE_REQ訊息後，就調低門限。這樣，第二次路由請求訊息就可以到達目的節點。
圖1-1(a) 級聯效應
圖1-1(b) 廣播DROP_ROUTE_REQ訊息
2、路由快取的利用
LEAR算法的另一個關鍵問題是路由快取的利用。原始DSR協定中，當中間節點接收到一個ROUTE_REQ訊息，並且在它的路由快取中找到一條到達目的節點的路由，就停止廣播該訊息，立即向源節點做出應答。LEAR中，當源節點S向目的節點D廣播ROUTE_REQ訊息，即使節點B從它的路由快取中知道D的路徑，由於快取條目中沒有關節點C1和C2的能量信息，它就不能向S做出應答。如圖1-2(a)，為了利用路由快取，LEAR單播一個ROUTE_CACHE訊息探測快取中到達目的節點的中間節點（C1和C2）的能量狀況。用這種方法，合理地利用了路由快取，同時避免了ROUTE_REQ訊息的廣播。目的節點可能接收到多個ROUTE_REQ訊息以及多個ROUTE_CACHE訊息，在選擇是選擇第一個到達的訊息向傳送者做出應答。
圖1-2(a)向目的節點單播ROUTE_CAHCE訊息
在單播ROUTE_CAHCE訊息時，如圖1-2(b)，當節點C1的電池能量小於門限值(Er<Thr)時，情況就變得比較複雜。與ROUTE_REQ訊息一樣，通過傳送一個DROP_ROUTE_CACHE訊息通知後面的節點（節點C2和D），使得這些後續節點在下一次路由請求訊息到達時調整自己的門限。並且向傳送ROUTE_CACHE的節點B發一個CACEL_ROUTE_CACHE訊息，刪除節點B中的路由快取，這樣做的原因是，每次節點在尋找目的節點的路由時，都是先在路由快取中尋找，因此，有可能存在另外一條從節點B到目的節點D的能量更充足的路由。
圖1-2(b)低電池容量時使路由快取失效
LEAR算法描述
表1-1詳細地給出了LEAR算法的過程。
節點 | 步驟 |
源節點 | 廣播一個ROUTE_REQ訊息； 等待第一個到達的ROUTE_REPLY訊息； 選擇包含在ROUTE_REPLY訊息中的源路由； 忽略所有以後的應答 |
中間節點 | 接收到ROUTE_REQ訊息， If訊息不是第一次到達而且Er<Thr，把Thr降低d; If快取中有到達目的節點的路由， if Er>Thr,單播ROUTE_CACHE訊息，並忽略所有以後的請求； otherwise,單播DROP_ROUTE_CACHE訊息並忽略所有以後的請求； Else if Er>Thr,廣播ROUTE_REQ訊息並忽略所有以後的請求； otherwise,廣播DROP_ROUTE_REQ訊息並忽略所有以後的請求 |
接收到ROUTE_CACHE訊息， If訊息不是第一次到達而且Er>Thr，把Thr降低d; If Er>Thr，單播ROUTE_CACHE訊息並忽略所有以後的請求； Otherwise，單播DROP_ROUTE_CACHE訊息並忽略所有以後的請求；並發回（單播）CANCEL_ROUTE_CACHE訊息 | |
目的節點 | 接收到第一次到達的ROUTE_REQ訊息或ROUTE_CACHE訊息， 向源節點發回一個攜帶有源路由的ROUTE_REPLY訊息 |
總結
DSR只最佳化了延遲，並沒有考慮能量的均衡消耗，而LEAR算法對DSR的路由發現過程進行改進，同時最佳化了延遲和能量的均衡消耗兩個參數。仿真結果表明，與DSR相比，LEAR的能量均衡消耗性能提高了10%~35%。
事實上，LEAR算法是在多條能量充足的路徑中選擇了最短路徑。LEAR算法基於本地能量信息獲得均衡的能量消耗；並且由於各個節點都只對第一個到達的訊息做出反應，所以該算法具有最短路由延遲；LEAR利用了路由快取最佳化技術。
