基于能量感知的最小能量動態(tài)源路由*

張繼鋒，周繼鵬

(暨南大學 信息科學技術學院，廣東 廣州 510632)

移動Ad hoc網絡MANET(Mobile Ad hoc Networks)是由一組具有路由功能的移動節(jié)點自組織成的無線多跳系統(tǒng)。由于網絡規(guī)模小、無基礎設施和構建快速等特點，MANET廣泛應用于野外考察、作戰(zhàn)現(xiàn)場、災難救助等場合。MANET中的節(jié)點一般通過電池供電，而目前電池容量有限。另一方面，隨著網絡終端性能的提升、功能的不斷加強，產生的能耗會越來越大，對能源的要求也會越來越高，能量問題可能成為Ad hoc網絡廣泛應用的瓶頸，從而使得節(jié)能策略成為當前一個研究熱點。

傳統(tǒng)路由協(xié)議都使用一組度量指標來尋找維護最佳路徑，最常用的度量指標是最少跳數。然而這個指標沒有考慮節(jié)點和網絡的耗能和壽命問題，可能導致節(jié)點能源的浪費和過度使用等問題，最終使得節(jié)點和網絡的壽命嚴重下降。

動態(tài)源路由(DSR)[1]協(xié)議在轉發(fā)數據時，使用最少跳數的路徑進行數據轉發(fā)。在發(fā)射器以固定能量水平發(fā)送的Ad hoc網絡中，DSR協(xié)議并沒有考慮路徑的剩余能量。由于DSR協(xié)議始終選擇最少跳數的路徑進行數據轉發(fā)，因此在最少跳數路徑上的節(jié)點被過度使用的可能性很大。節(jié)點的過度使用極易使節(jié)點死亡造成網絡發(fā)生分割，縮短網絡的使用壽命。

最小能量動態(tài)源路由MEDSR(Minimum Energy Dynamic Source Routing)[2]協(xié)議除了發(fā)射器的能量水平可調整外，其余的都與DSR協(xié)議相同，所以MEDSR協(xié)議也有DSR協(xié)議所面臨的問題。

本文針對DSR協(xié)議和MEDSR協(xié)議在節(jié)能策略方面存在的缺陷，以減少節(jié)點的過度使用和延長網絡生存時間為設計目標，以MEDSR路由協(xié)議為基礎，提出了一種基于能量感知的最小能量動態(tài)源路由協(xié)議。引入能量感知策略就是使路徑的剩余能量成為主要的度量指標來選取最佳路徑。通過在路由發(fā)現(xiàn)過程中動態(tài)地進行路徑剩余能量的計算，選擇剩余能量最大的路徑轉發(fā)數據，與傳統(tǒng)的按需路由協(xié)議相比，大大減少了節(jié)點的過度使用，延長了網絡的生存時間。

1 相關算法

最小最大鏈路功率路由協(xié)議(MLRP)算法旨在尋找一條低功率的路由，其中每個節(jié)點都能根據自己要進行通信的鄰近節(jié)點自適應地調整發(fā)射功率。在此算法中，路由尋找的發(fā)起者決定轉發(fā)RREQ請求的中間節(jié)點的統(tǒng)一發(fā)射功率，當路由建立嘗試失敗時，能相應地減小此功率值。因此，此路由進程主要考慮最小化每個參與節(jié)點消耗的能量，以及減小所選路徑消耗的能量。最小電池開銷路由(MBCR)[3]算法中定義了節(jié)點電池開銷函數，從而計算出包含n個節(jié)點的路徑m的總電池開銷，而最大剩余電池能量的路徑即是擁有最小電池開銷的那條路徑。有條件最大最小電池容量路由(CMMBCR)算法[4]也是對MBCR的改進，設計CMMBCR的出發(fā)點是能夠使整個網絡的生命周期最大，同時又公平地使用每個節(jié)點。其基本思想是首先找出從源節(jié)點到目的節(jié)點的所有電量充足的路徑(即路徑上的所有節(jié)點都具有大于某個閾值(0～100)的剩余電量)，然后從中選擇出總傳輸能量最小的那條路徑作為路由選擇的最終結果。

2 最小能量動態(tài)源路由(MEDSR)

2.1 最小能量路由協(xié)議的背景

傳統(tǒng)的路由協(xié)議都是采用固定的發(fā)射功率進行數據包的轉發(fā)，由于節(jié)點發(fā)射功率的大小直接影響到鄰近節(jié)點的通信，發(fā)射功率太小雖然可以相對減少能量消耗，但是有可能使得兩個節(jié)點的通信無法進行；發(fā)射功率太大雖然可以保證兩個節(jié)點之間的通信，但是有可能會影響其他節(jié)點的通信。

發(fā)射功率水平過高或者過低都會嚴重影響網絡的連通性，在保證節(jié)點通信成功的情況下，采用最小發(fā)射功率水平不僅可以保證網絡的連通性，而且還減少節(jié)點的能量消耗。

2.2 最小能量動態(tài)源路由簡介(MEDSR)

MEDSR協(xié)議是在DSR協(xié)議的基礎上，采用可調整的發(fā)射功率，并且在DSR協(xié)議的路由發(fā)現(xiàn)過程當中改進而得來的。最小能量體現(xiàn)在保持通信質量的情況下，使得節(jié)點的發(fā)射功率水平達到最低。

MEDSR協(xié)議的路由發(fā)現(xiàn)過程當中包含兩個機制：

(1)多功率水平路由發(fā)現(xiàn)機制

源節(jié)點首先使用低功率水平發(fā)送RREQ，RREQ中包含功率水平信息。如果使用低功率水平發(fā)送失敗，則選擇高功率水平發(fā)送。下一跳節(jié)點也選擇可調整的功率水平將RREQ轉發(fā)，并且將自己的功率水平信息加到RREQ中。此過程一直操作下去，直到RREQ到達目標節(jié)點。此時，目標節(jié)點發(fā)送RREP，RREP中同樣包含能量水平信息。功率水平的調整過程就是通過轉發(fā)RREP進行的。此過程一直進行，直到RREP到達源節(jié)點。

(2)逐段功率水平調整機制

圖1(a)中節(jié)點C接收到目標節(jié)點D發(fā)送過來的RREP，測量節(jié)點C接收到的能量水平Precv。因為RREP中包含目的節(jié)點的發(fā)送功率水平信息Pt。節(jié)點C計算到達目標節(jié)點 D所需最少的傳送能量：Pmin=Pt-Precv，然后節(jié)點C將所需的最少傳送能量存儲在自己的能量表中。節(jié)點C再將RREP轉發(fā)給節(jié)點B，重復同樣的工作，直到RREP到達源節(jié)點S。

圖1 路由發(fā)現(xiàn)

3 協(xié)議描述

3.1 能量感知

3.1.1 路由請求包(RREQ)的結構

為了實現(xiàn)MEDSR協(xié)議中功率調整，需要在RREQ中增添功率值列表字段Power list，如表1所示。

表1 路由請求包(RREQ)的結構

3.1.2 路由回復包(RREP)的結構

路徑的剩余能量是指該路徑中的節(jié)點剩余能量的最小值。

能量感知的目的就是在返回的眾多路徑中選擇剩余能量最大的路徑。

按需路由協(xié)議并不像表驅動路由協(xié)議那樣預先知道網絡全局的拓撲信息，按需路由協(xié)議是根據發(fā)送數據分組的需要按需進行路由發(fā)現(xiàn)過程，所以MEDSR協(xié)議中路徑的剩余能量只能通過路由發(fā)現(xiàn)過程動態(tài)地獲得。因此，需要在RREP中增添路徑剩余能量字段Path energy，如表 2所示。

表2 路由回復包(RREP)的結構

3.1.3 節(jié)點本地cache表的結構

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

表3 節(jié)點剩余能量值和功率水平

Residual energy字段記錄節(jié)點當前的剩余能量值，Temporary energy字段記錄Residual energy字段與Power level字段的差值，用于和RREP中的Path energy字段比較，Power level字段記錄經調整的發(fā)射功率值。

采用Temporary energy字段是因為MEDSR協(xié)議的發(fā)射功率是可調整的，即不同路徑上節(jié)點的發(fā)射功率大小不同，如果此時簡單地使用Residual energy值作為比較對象，有可能使Residual energy最大的節(jié)點由于Power level過大而造成節(jié)點能量的過快消耗。此時采用Temporary energy可預先考慮節(jié)點能量的消耗速率，這樣對路徑剩余能量的比較更公平準確。

3.1.4 能量感知過程說明

變量說明：R代表 cache中的 Residual energy字段記錄的值；P代表 cache中的 Power level字段記錄的值；T代表cache中的Temporary energy字段記錄的值(用于和RREP中的 E比較)；E代表RREP的Path energy字段記錄的值。

(1)節(jié)點剩余能量的計算過程

每個節(jié)點都保存著自己剩余能量的數值R，同時，保存著臨時的發(fā)射功率水平數值P(P是MEDSR協(xié)議經過能量水平調整而暫時存儲在本地cache表當中的)。每轉發(fā)一個數據包，節(jié)點就進行操作：R：=R-P。

(2)路徑剩余能量的計算過程

在MEDSR協(xié)議路由應答過程中，目的節(jié)點的下一跳鄰居節(jié)點進行能量水平調整以及相應的臨時剩余能量T計算。首先進行計算 T：=R-P，然后將自己的T賦值到RREP中的Path energy字段。當RREP到達目的節(jié)點的次下一跳鄰居節(jié)點時，該節(jié)點也進行能量水平調整和臨時剩余能量T計算，然后將自己的T值和RREP中的 E 值進行比較：如果 T＜E，則 E：=T；如果 T＞=E，則 E不做任何改變。

將RREP繼續(xù)往源節(jié)點轉發(fā)，RREP中只儲存唯一的一個E值。根據上面分析可知，E儲存的是該路徑的剩余能量。

當源節(jié)點接收到經過多個RREP后，比較它們當中的E值，源節(jié)點首先選擇E最大的的路徑進行數據包的轉發(fā)，即選擇剩余能量最大的路徑進行數據轉發(fā)。

3.1.5 能量感知形式化說明

圖2(a)和圖 2(b)分別用無向圖和有向圖表示同一個網絡[5]。圖2(a)中節(jié)點旁邊的數字代表節(jié)點的剩余能量R，節(jié)點之間的數字代表經過調整發(fā)射能量水平數值P。圖2(b)中節(jié)點旁邊的數字代表節(jié)點的剩余能量R，節(jié)點之間的數字代表臨時剩余能量T。

如圖 2(b)，節(jié)點 d和節(jié)點 b進行通信，d、b之間有兩條路徑，分別是d-a-b和d-c-b，路徑d-a-b的剩余能量 E是 60；路徑 d-c-b的剩余能量 E是 55，所以節(jié)點d和節(jié)點b進行通信時，會優(yōu)先選擇剩余能量值較大的d-a-b路徑。再如，節(jié)點 a和節(jié)點 c進行通信，a、c之間有兩條路徑，分別是a-b-c和 a-d-c，路徑 a-b-c的剩余能量 E是 35；路徑 a-d-c的剩余能量 E是 55，所以節(jié)點a和節(jié)點c進行通信時，會優(yōu)先選擇剩余能量值較大的a-d-c路徑。

圖2 能量感知

3.2 路由算法

3.2.1 路由請求

(1)源節(jié)點S在本地路由緩存中檢查是否存在到達目的節(jié)點D的路由。如果存在，則轉(2)，否則開始路由請求過程：節(jié)點選擇可調整的功率水平轉發(fā)RREQ。首先，源節(jié)點S使用低功率水平發(fā)送路由請求數據包RREQ，如果發(fā)送成功，則將功率水平信息存放到RREQ發(fā)射功率值列表字段Power list中；否則，選擇高功率水平發(fā)送路由請求數據包RREQ，如果發(fā)射成功，進行如上述功率水平信息同樣的操作，并轉(3)。否則，路由請求失敗。

(2)使用該路由發(fā)送數據分組。

(3)下一跳鄰居節(jié)點接收到RREQ后，首先檢查路由請求表中是否有對應的表項，如果有，直接丟棄該RREQ；否則，檢查路由請求分組的路由記錄是否已含有該節(jié)點，如果有，丟棄該分組。然后，如果路由請求分組的目的節(jié)點為節(jié)點本身，即將自己的地址信息加到RREQ中，并將功率水平信息加到RREQ中發(fā)射功率值列表字段Power list中，該節(jié)點同時反向轉發(fā)RREP，RREP中保存RREQ中功率水平信息；如果不是節(jié)點本身，也將自己的地址信息加到RREQ中，該節(jié)點同樣選擇可調整的功率水平轉發(fā)RREQ，并且將自己的功率水平信息加到RREQ功率值列表字段Power list中，并轉發(fā)RREQ。

(4)次下一跳鄰居節(jié)點接收到RREQ后，重復操作(3)。

(5)所有中間節(jié)點按照步驟(3)操作，直到所有RREQ到達目的節(jié)點D。

3.2.2 路由應答

(1)目的節(jié)點D將自己的地址信息和功率水平信息加到 RREP中，并反向轉發(fā) RREP，并轉（2），同時進行路徑剩余能量的計算。

(2)下一跳鄰居節(jié)點接收到RREP后，首先根據MEDSR協(xié)議中的功率水平調整機制進行功率的調整，并將計算得到的Pmin存放到本地cache中的 Power level字段。然后進行臨時剩余能量的計算T：=R-P，將自己的T賦值到RREP中的Path energy字段。最后繼續(xù)轉發(fā)RREP。

(3)次下一跳鄰居節(jié)點接收到RREP后，首先根據MEDSR協(xié)議中的功率水平調整機制進行功率的調整，并將計算得到的Pmin存放到本地cache中的Power level字段。然后進行臨時剩余能量的計算T：=R-P，將自己的T值和RREP中的E值進行比較：

如果 T＜E，則 E：=T；如果 T＞=E，則 E 不做任何改變。最后繼續(xù)轉發(fā)RREP。

(4)所有中間節(jié)點按照步驟(3)操作后，向下一鄰居節(jié)點繼續(xù)轉發(fā)RREP，直到RREP到達源節(jié)點S。

(5)源節(jié)點 S選取 Path energy值最大的 RREP提供的路由信息進行數據分組的轉發(fā)。

3.3 路由過程

3.3.1 路由請求過程

(1)從如圖3可以看到源節(jié)點S在路由緩存中并沒有發(fā)現(xiàn)到達目的節(jié)點D的緩存路由。源節(jié)點S開始路由請求過程：節(jié)點S使用可調整的功率水平發(fā)送路由請求數據包RREQ，將功率水平信息存放到RREQ功率值列表字段 Power list中，并轉發(fā) RREQ。圖 3中(S，B)的功率水平值為 20，(S，E)的功率水平值為 15。

(2)下一跳鄰居節(jié)點B和E接收到RREQ后，首先，節(jié)點B和E檢查路由請求表并沒有發(fā)現(xiàn)對應的表項；同時檢查路由請求分組的路由記錄也沒有發(fā)現(xiàn)含有該節(jié)點，則不丟棄RREQ。然后，節(jié)點B和E檢查路由請求分組的目的節(jié)點不是節(jié)點B和E本身，同時將自己的地址信息加到RREQ中，該節(jié)點同樣選擇可調整的功率水平轉發(fā)RREQ，將自己的功率水平信息加到RREQ功率值列表字段中，并轉發(fā)RREQ。圖3中(E，F(xiàn))的功率水平值為 15，(B，C)的功率水平值為 20。

(3)次下一跳鄰居節(jié)點 F和 C接收到 RREQ后，首先，節(jié)點F和C檢查路由請求表并沒有發(fā)現(xiàn)對應的表項；同時檢查路由請求分組的路由記錄也沒有發(fā)現(xiàn)含有該節(jié)點，則不丟棄RREQ。然后，節(jié)點F和C檢查路由請求分組的目的節(jié)點不是節(jié)點F和C本身，同時將自己的地址信息加到RREQ中，該節(jié)點同樣選擇可調整的功率水平轉發(fā)RREQ，將自己的功率水平信息加到RREQ功率值列表字段中，并轉發(fā)RREQ。圖3中(F，G)的功率水平值為 15。

但是，次下一跳鄰居節(jié)點H接收到節(jié)點B和E轉發(fā)過來的RREQ，如圖3中節(jié)點H先接收到節(jié)點B轉發(fā)過來的RREQ，并且不丟棄，節(jié)點H檢查路由請求分組的目的節(jié)點不是節(jié)點H本身，同時將自己的地址信息加到RREQ中，該節(jié)點同樣選擇可調整的功率水平轉發(fā)RREQ，將自己的功率水平信息加到RREQ功率值列表字段中，并轉發(fā)該RREQ。此后，節(jié)點H接收節(jié)點E轉發(fā)過來的RREQ，發(fā)現(xiàn)路由請求表中有對應的表項，丟棄掉該RREQ。

(4)同理，中間節(jié)點C接收到節(jié)點B和H轉發(fā)過來的RREQ，圖3中節(jié)點C先接收到節(jié)點B轉發(fā)過來的RREQ，并且不丟棄，節(jié)點C檢查路由請求分組的目的節(jié)點不是節(jié)點C本身，同時將自己的地址信息加到RREQ中，該節(jié)點同樣選擇可調整的功率水平轉發(fā)RREQ，將自己的功率水平信息加到RREQ功率值列表字段中，并轉發(fā)該RREQ。此后，節(jié)點C接收節(jié)點H轉發(fā)過來的RREQ，發(fā)現(xiàn)路由請求表中有對應的表項，丟棄掉該RREQ。圖3中(C，D)的功率水平值為 15。

(5)最后，直到所有RREQ到達目的節(jié)點D。如圖 3中(S，E，F(xiàn)，G)和(S，B，C)到達目的節(jié)點 D。

圖3 路由請求示意圖

3.3.2 路由應答過程

(1)目的節(jié)點D將自己的功率水平信息加到RREP中，并反向轉發(fā)RREP，如圖4所示。

(2)下一跳鄰居節(jié)點 C和 G接收到 RREP后，首先根據MEDSR協(xié)議中的功率水平調整機制進行功率的調整，并將計算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(xiàn)，G，D)中，M：=75。 最后繼續(xù)轉發(fā) RREP。

圖4 路由應答示意圖

(3)次下一跳節(jié)點 B和 F接收到 RREP后，首先根據MEDSR協(xié)議中的功率水平調整機制進行功率的調整，并將計算Pmin存放到cache中的Power level字段。如圖4，B和F的Pmin都是15。然后進行臨時剩余能量的計算 T：=R-P，B的剩余能量 R是 70,因此 B的 T值為55。同理，F(xiàn)的 T值為 65，然后將自己的 T值和 RREP中的M值進行比較：

(S，B，C，D)中，55＜70 則 E：=55；

(S，E，F(xiàn)，G，D)中，65＜75 則 E：=65。

(4)所有中間節(jié)點進行臨時剩余能量計算以及路徑剩余能量計算操作后，向下一節(jié)點繼續(xù)轉發(fā)RREP，直到RREP到達源節(jié)點S。

(5)源節(jié)點S選取 Path energy最大的 RREP提供的路由信息進行數據分組的轉發(fā)。

(S，B，C，D)中，E=55；

(S，E，F(xiàn)，G，D)中，E=65。

所以源節(jié)點 S 選取(S，E，F(xiàn)，G，D)進行數據分組的轉發(fā)，并不是選擇跳數較少的(S，B，C，D)進行數據分組的轉發(fā)。

本文針對MEDSR協(xié)議中存在的問題對路由發(fā)現(xiàn)過程進行改進，加入能量感知策略，能量感知可使數據流平均地分布在網絡的各個節(jié)點中，減少網絡節(jié)點的過度使用，使網絡分割的可能性減小，延長網絡的使用壽命。減少了路徑上中間節(jié)點的能量消耗，從而降低了由于能量消耗殆盡導致的網絡分割或拓撲變化發(fā)生的概率。

下一步工作是深入模擬和分析該協(xié)議的性能，并與DSR協(xié)議和MEDSR協(xié)議進行比較。

[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.