摘  要： 在MANET中節點必須依靠可攜帶的有限電源供電，為了盡可能延長節點及網絡的壽命， 節能方法一直是專業人員致力研究的問題。基于能量感知的最小能量動態源路由協議是針對最小能量動態源路由協議提出來的。引入能量感知策略就是使路徑的剩余能量成為主要的度量指標來選取最佳路徑，選擇剩余能量最大的路徑轉發數據，并且減少節點能源的浪費和過度使用等問題。
關鍵詞： MANET；最小能量動態源路由；能量感知

    移動Ad hoc網絡MANET(Mobile Ad hoc Networks)是由一組具有路由功能的移動節點自組織成的無線多跳系統。由于網絡規模小、無基礎設施和構建快速等特點，MANET廣泛應用于野外考察、作戰現場、災難救助等場合。MANET中的節點一般通過電池供電，而目前電池容量有限。另一方面，隨著網絡終端性能的提升、功能的不斷加強，產生的能耗會越來越大，對能源的要求也會越來越高，能量問題可能成為Ad hoc網絡廣泛應用的瓶頸，從而使得節能策略成為當前一個研究熱點。
　傳統路由協議都使用一組度量指標來尋找維護最佳路徑，最常用的度量指標是最少跳數。然而這個指標沒有考慮節點和網絡的耗能和壽命問題，可能導致節點能源的浪費和過度使用等問題，最終使得節點和網絡的壽命嚴重下降。
　動態源路由(DSR)[1]協議在轉發數據時，使用最少跳數的路徑進行數據轉發。在發射器以固定能量水平發送的Ad hoc網絡中，DSR協議并沒有考慮路徑的剩余能量。由于DSR協議始終選擇最少跳數的路徑進行數據轉發，因此在最少跳數路徑上的節點被過度使用的可能性很大。節點的過度使用極易使節點死亡造成網絡發生分割，縮短網絡的使用壽命。
　最小能量動態源路由MEDSR(Minimum Energy Dynamic Source Routing)[2]協議除了發射器的能量水平可調整外，其余的都與DSR協議相同，所以MEDSR協議也有DSR協議所面臨的問題。
　本文針對DSR協議和MEDSR協議在節能策略方面存在的缺陷，以減少節點的過度使用和延長網絡生存時間為設計目標，以MEDSR路由協議為基礎，提出了一種基于能量感知的最小能量動態源路由協議。引入能量感知策略就是使路徑的剩余能量成為主要的度量指標來選取最佳路徑。通過在路由發現過程中動態地進行路徑剩余能量的計算，選擇剩余能量最大的路徑轉發數據，與傳統的按需路由協議相比，大大減少了節點的過度使用，延長了網絡的生存時間。
1 相關算法
　最小最大鏈路功率路由協議(MLRP)算法旨在尋找一條低功率的路由，其中每個節點都能根據自己要進行通信的鄰近節點自適應地調整發射功率。在此算法中，路由尋找的發起者決定轉發RREQ請求的中間節點的統一發射功率，當路由建立嘗試失敗時，能相應地減小此功率值。因此，此路由進程主要考慮最小化每個參與節點消耗的能量，以及減小所選路徑消耗的能量。最小電池開銷路由(MBCR)[3]算法中定義了節點電池開銷函數，從而計算出包含n個節點的路徑m的總電池開銷，而最大剩余電池能量的路徑即是擁有最小電池開銷的那條路徑。有條件最大最小電池容量路由(CMMBCR)算法[4]也是對MBCR的改進，設計CMMBCR的出發點是能夠使整個網絡的生命周期最大，同時又公平地使用每個節點。其基本思想是首先找出從源節點到目的節點的所有電量充足的路徑(即路徑上的所有節點都具有大于某個閾值(0~100)的剩余電量)，然后從中選擇出總傳輸能量最小的那條路徑作為路由選擇的最終結果。
2 最小能量動態源路由(MEDSR)
2.1 最小能量路由協議的背景
　傳統的路由協議都是采用固定的發射功率進行數據包的轉發，由于節點發射功率的大小直接影響到鄰近節點的通信，發射功率太小雖然可以相對減少能量消耗，但是有可能使得兩個節點的通信無法進行；發射功率太大雖然可以保證兩個節點之間的通信，但是有可能會影響其他節點的通信。
　發射功率水平過高或者過低都會嚴重影響網絡的連通性，在保證節點通信成功的情況下，采用最小發射功率水平不僅可以保證網絡的連通性，而且還減少節點的能量消耗。
2.2 最小能量動態源路由簡介(MEDSR)
　MEDSR協議是在DSR協議的基礎上，采用可調整的發射功率，并且在DSR協議的路由發現過程當中改進而得來的。最小能量體現在保持通信質量的情況下，使得節點的發射功率水平達到最低。
　MEDSR協議的路由發現過程當中包含兩個機制：
   (1)多功率水平路由發現機制
　源節點首先使用低功率水平發送RREQ，RREQ中包含功率水平信息。如果使用低功率水平發送失敗，則選擇高功率水平發送。下一跳節點也選擇可調整的功率水平將RREQ轉發，并且將自己的功率水平信息加到RREQ中。此過程一直操作下去，直到RREQ到達目標節點。此時，目標節點發送RREP，RREP中同樣包含能量水平信息。功率水平的調整過程就是通過轉發RREP進行的。此過程一直進行，直到RREP到達源節點。
    (2)逐段功率水平調整機制
    圖1(a)中節點C接收到目標節點D發送過來的RREP，測量節點C接收到的能量水平Precv。因為RREP中包含目的節點的發送功率水平信息Pt。節點C計算到達目標節點D所需最少的傳送能量：Pmin=Pt-Precv，然后節點C將所需的最少傳送能量存儲在自己的能量表中。節點C再將RREP轉發給節點B，重復同樣的工作，直到RREP到達源節點S。

3 協議描述
3.1 能量感知
3.1.1 路由請求包(RREQ)的結構
    為了實現MEDSR協議中功率調整，需要在RREQ中增添功率值列表字段Power list，如表1所示。

3.1.2 路由回復包(RREP)的結構
   路徑的剩余能量是指該路徑中的節點剩余能量的最小值。
   能量感知的目的就是在返回的眾多路徑中選擇剩余能量最大的路徑。
　按需路由協議并不像表驅動路由協議那樣預先知道網絡全局的拓撲信息，按需路由協議是根據發送數據分組的需要按需進行路由發現過程，所以MEDSR協議中路徑的剩余能量只能通過路由發現過程動態地獲得。因此，需要在RREP中增添路徑剩余能量字段Path energy，如表2所示。

3.1.3 節點本地cache表的結構
   為了滿足能量感知的目標，需要在MEDSR協議的基礎上，對網絡節點的cache表中再增加剩余能量值字段Residual energy和臨時剩余能量字段Temporary energy，以及發射功率值字段Power level，如表3所示。

   Residual energy字段記錄節點當前的剩余能量值，Temporary energy字段記錄Residual energy字段與Power level字段的差值，用于和RREP中的Path energy字段比較，Power level字段記錄經調整的發射功率值。
   采用Temporary energy字段是因為MEDSR協議的發射功率是可調整的，即不同路徑上節點的發射功率大小不同，如果此時簡單地使用Residual energy值作為比較對象，有可能使Residual energy最大的節點由于Power level過大而造成節點能量的過快消耗。此時采用Temporary energy可預先考慮節點能量的消耗速率，這樣對路徑剩余能量的比較更公平準確。
3.1.4 能量感知過程說明
   變量說明:R代表cache中的Residual energy字段記錄的值；P代表cache中的Power level字段記錄的值；T代表cache中的Temporary energy字段記錄的值(用于和RREP中的E比較)；E代表RREP的Path energy字段記錄的值。
   (1)節點剩余能量的計算過程
   每個節點都保存著自己剩余能量的數值R，同時，保存著臨時的發射功率水平數值P(P是MEDSR協議經過能量水平調整而暫時存儲在本地cache表當中的)。每轉發一個數據包，節點就進行操作：R:=R-P。
   (2)路徑剩余能量的計算過程
   在MEDSR協議路由應答過程中，目的節點的下一跳鄰居節點進行能量水平調整以及相應的臨時剩余能量T計算。首先進行計算T：=R-P，然后將自己的T賦值到RREP中的Path energy字段。當RREP到達目的節點的次下一跳鄰居節點時，該節點也進行能量水平調整和臨時剩余能量T計算，然后將自己的T值和RREP中的E值進行比較：如果T<E，則E:=T；如果T>=E，則E不做任何改變。
   將RREP繼續往源節點轉發，RREP中只儲存唯一的一個E值。根據上面分析可知，E儲存的是該路徑的剩余能量。
   當源節點接收到經過多個RREP后，比較它們當中的E值，源節點首先選擇E最大的的路徑進行數據包的轉發，即選擇剩余能量最大的路徑進行數據轉發。
3.1.5 能量感知形式化說明
   圖2(a)和圖2(b)分別用無向圖和有向圖表示同一個網絡[5]。圖2(a)中節點旁邊的數字代表節點的剩余能量R，節點之間的數字代表經過調整發射能量水平數值P。圖2(b)中節點旁邊的數字代表節點的剩余能量R，節點之間的數字代表臨時剩余能量T。

   如圖2(b)，節點d和節點b進行通信，d、b之間有兩條路徑，分別是d-a-b和d-c-b，路徑d-a-b的剩余能量E是60；路徑d-c-b的剩余能量E是55，所以節點d和節點b進行通信時，會優先選擇剩余能量值較大的d-a-b路徑。再如，節點a和節點c進行通信，a、c之間有兩條路徑，分別是a-b-c和a-d-c，路徑a-b-c的剩余能量E是35；路徑a-d-c的剩余能量E是55，所以節點a和節點c進行通信時，會優先選擇剩余能量值較大的a-d-c路徑。
3.2 路由算法
3.2.1 路由請求
   (1)源節點S在本地路由緩存中檢查是否存在到達目的節點D的路由。如果存在，則轉(2)，否則開始路由請求過程：節點選擇可調整的功率水平轉發RREQ。首先，源節點S使用低功率水平發送路由請求數據包RREQ，如果發送成功，則將功率水平信息存放到RREQ發射功率值列表字段Power list中；否則，選擇高功率水平發送路由請求數據包RREQ，如果發射成功，進行如上述功率水平信息同樣的操作，并轉(3)。否則，路由請求失敗。
   (2)使用該路由發送數據分組。
   (3)下一跳鄰居節點接收到RREQ后，首先檢查路由請求表中是否有對應的表項，如果有，直接丟棄該RREQ；否則，檢查路由請求分組的路由記錄是否已含有該節點，如果有，丟棄該分組。然后，如果路由請求分組的目的節點為節點本身，即將自己的地址信息加到RREQ中，并將功率水平信息加到RREQ中發射功率值列表字段Power list中，該節點同時反向轉發RREP，RREP中保存RREQ中功率水平信息；如果不是節點本身，也將自己的地址信息加到RREQ中，該節點同樣選擇可調整的功率水平轉發RREQ，并且將自己的功率水平信息加到RREQ功率值列表字段Power list中，并轉發RREQ。
   (4)次下一跳鄰居節點接收到RREQ后，重復操作(3)。
   (5)所有中間節點按照步驟(3)操作，直到所有RREQ到達目的節點D。
3.2.2 路由應答
   (1)目的節點D將自己的地址信息和功率水平信息加到RREP中，并反向轉發RREP，并轉（2），同時進行路徑剩余能量的計算。
   (2)下一跳鄰居節點接收到RREP后，首先根據MEDSR協議中的功率水平調整機制進行功率的調整，并將計算得到的Pmin存放到本地cache中的Power level字段。然后進行臨時剩余能量的計算T：=R-P，將自己的T賦值到RREP中的Path energy字段。最后繼續轉發RREP。
   (3)次下一跳鄰居節點接收到RREP后，首先根據MEDSR協議中的功率水平調整機制進行功率的調整，并將計算得到的Pmin存放到本地cache中的Power level字段。然后進行臨時剩余能量的計算T：=R-P，將自己的T值和RREP中的E值進行比較：
   如果T<E，則E:=T；如果T>=E，則E不做任何改變。最后繼續轉發RREP。
   (4)所有中間節點按照步驟(3)操作后，向下一鄰居節點繼續轉發RREP，直到RREP到達源節點S。
   (5)源節點S選取Path energy值最大的RREP提供的路由信息進行數據分組的轉發。
3.3 路由過程
3.3.1 路由請求過程
   (1)從如圖3可以看到源節點S在路由緩存中并沒有發現到達目的節點D的緩存路由。源節點S開始路由請求過程：節點S使用可調整的功率水平發送路由請求數據包RREQ，將功率水平信息存放到RREQ功率值列表字段Power list中，并轉發RREQ。圖3中(S，B)的功率水平值為20，(S，E)的功率水平值為15。

   (2)下一跳鄰居節點B和E接收到RREQ后，首先，節點B和E檢查路由請求表并沒有發現對應的表項；同時檢查路由請求分組的路由記錄也沒有發現含有該節點，則不丟棄RREQ。然后，節點B和E檢查路由請求分組的目的節點不是節點B和E本身，同時將自己的地址信息加到RREQ中，該節點同樣選擇可調整的功率水平轉發RREQ，將自己的功率水平信息加到RREQ功率值列表字段中，并轉發RREQ。圖3中(E，F)的功率水平值為15，(B，C)的功率水平值為20。
   (3)次下一跳鄰居節點F和C接收到RREQ后，首先，節點F和C檢查路由請求表并沒有發現對應的表項；同時檢查路由請求分組的路由記錄也沒有發現含有該節點，則不丟棄RREQ。然后，節點F和C檢查路由請求分組的目的節點不是節點F和C本身，同時將自己的地址信息加到RREQ中，該節點同樣選擇可調整的功率水平轉發RREQ，將自己的功率水平信息加到RREQ功率值列表字段中，并轉發RREQ。圖3中(F，G)的功率水平值為15。
   但是，次下一跳鄰居節點H接收到節點B和E轉發過來的RREQ，如圖3中節點H先接收到節點B轉發過來的RREQ，并且不丟棄，節點H檢查路由請求分組的目的節點不是節點H本身，同時將自己的地址信息加到RREQ中，該節點同樣選擇可調整的功率水平轉發RREQ，將自己的功率水平信息加到RREQ功率值列表字段中，并轉發該RREQ。此后，節點H接收節點E轉發過來的RREQ，發現路由請求表中有對應的表項，丟棄掉該RREQ。
   (4)同理，中間節點C接收到節點B和H轉發過來的RREQ，圖3中節點C先接收到節點B轉發過來的RREQ，并且不丟棄，節點C檢查路由請求分組的目的節點不是節點C本身，同時將自己的地址信息加到RREQ中，該節點同樣選擇可調整的功率水平轉發RREQ，將自己的功率水平信息加到RREQ功率值列表字段中，并轉發該RREQ。此后，節點C接收節點H轉發過來的RREQ，發現路由請求表中有對應的表項，丟棄掉該RREQ。圖3中(C，D)的功率水平值為15。
   (5)最后，直到所有RREQ到達目的節點D。如圖3中(S，E，F，G)和(S，B，C)到達目的節點D。
3.3.2 路由應答過程
   (1)目的節點D將自己的功率水平信息加到RREP中，并反向轉發RREP，如圖4所示。

   (2)下一跳鄰居節點C和G接收到RREP后，首先根據MEDSR協議中的功率水平調整機制進行功率的調整，并將計算Pmin存放到cache中的Power level字段。圖4中C和G的Pmin都是15。然后進行臨時剩余能量的計算 T：=R-P， C的剩余能量R是85，因此，C的T值為70。同理，G的T值為75，然后將自己的T賦值到RREP中的Path energy字段。(S，B，C，D)中，M:=70；(S，E，F，G，D)中，M:=75。最后繼續轉發RREP。
　(3)次下一跳節點B和F接收到RREP后，首先根據MEDSR協議中的功率水平調整機制進行功率的調整，并將計算Pmin存放到cache中的Power level字段。如圖4，B和F的Pmin都是15。然后進行臨時剩余能量的計算T：=R-P，B的剩余能量R是70,因此B的T值為55。同理，F的T值為65，然后將自己的T值和RREP中的M值進行比較：
   (S，B，C，D)中，55<70則E:=55；
   (S，E，F，G，D)中，65<75則E:=65。
   (4)所有中間節點進行臨時剩余能量計算以及路徑剩余能量計算操作后，向下一節點繼續轉發RREP，直到RREP到達源節點S。
   (5)源節點S選取Path energy最大的RREP提供的路由信息進行數據分組的轉發。
   (S，B，C，D)中，E=55；
   (S，E，F，G，D)中，E=65。
   所以源節點S選取(S，E，F，G，D)進行數據分組的轉發，并不是選擇跳數較少的(S，B，C，D)進行數據分組的轉發。
   本文針對MEDSR協議中存在的問題對路由發現過程進行改進，加入能量感知策略，能量感知可使數據流平均地分布在網絡的各個節點中，減少網絡節點的過度使用，使網絡分割的可能性減小，延長網絡的使用壽命。減少了路徑上中間節點的能量消耗，從而降低了由于能量消耗殆盡導致的網絡分割或拓撲變化發生的概率。
   下一步工作是深入模擬和分析該協議的性能，并與DSR協議和MEDSR協議進行比較。
參考文獻
[1] 于宏毅.無線移動自組織網[M].北京:人民郵電出版社，2005.
[2] TARIQUE M， TEPE K E. Minimum energy hierarchical dynamic source routing for mobile ad hoc networks[J]. Ad Hoc Networks 2009，7(6):1125-1135.
[3] SINGH S， WOO M， RAGHAVENDRA C S. Power-aware routing in mobile ad hoc networks[C]. Proceedings of the 4th Annual ACM/IEEE Intemational Conferere on Mobile Computing and Netwodeing， 1998:181-190.
[4] TOH C K， COBB H， SCOTT D A. Performance evaluation of battery-lifeaware routing schemes for wireless ad hoc networks[C]. IEEE International Conference on Communications(ICC)， 2001:2824-2829.
[5] MOHANOOR A B， RADHAKRISHNAN S， SARANGAN V. Online energy aware routing in wireless networks[J]. Ad Hoc Networks， 2009，7(5):918-931.