移動Ａｄ Ｈｏｃ網絡中節能的路由協議研究

移動Ad Hoc 網絡是由一組具有路由功能的移動節點自組織成的無線多跳系統。由于網絡規模小、無基礎設施和構建快速等特點，而廣泛應用于野外考察、作戰現場、災難救助等場合。其中由于網絡中的節點通常是以有限能量的電池供電的，限制了節點生存時間，從而使得節能策略成為當前一個研究熱點。目前研究較多的是在路由協議上實現節能控制。本文對這些節能路由協議進行了分類和研究，并指出了進一步的可能發展方向。

目前對移動Ad hoc 網絡路由協議能量問題的研究有兩種出發點：一種是尋找一條從源節點到目的節點的路由，使得路由上所有節點的能量消耗之和為最低；另一種是調整網絡的拓撲結構使得網絡的連通時間達到最大值。下面從這兩個方面闡述相關協議。

一、主動節能路由協議

1.MPR（最小功率路由）。MPR(Minimum Power Routing)是基于最小傳送功率的表驅動路由協議。在MPR中，每條鏈路上計算進行可靠通信所需要的最小發射功率并將此作為該鏈路的代價函數，通過分布式的Bellman-Ford算法，即將傳統的鏈路距離替代為新的代價函數。

2.MTPR (最小總傳輸功率路由算法)。MTPR是一個分布式的算法。在任一時刻，Ad Hoc網絡的拓撲結構可看作是一個帶權有向圖，任一條弧上的權重可量化為發送節點所需的最小發送能量。從而可以用標準的最短路徑算法求出源節點到目的節點最小總傳輸能量的路徑。

3.LAPAR（Location Aided Power Aware Routing）。LAPAR協議是個GPS輔助型的分布式的能量路由協議，在此協議中，發送節點首先根據相鄰節點的地理位置劃分最佳的轉發區域。LAPAR的優勢表現為：有效的能量路由；容易嫁接到現有的協議上；由于采用了僅基于鄰居信息的平面圖，減少了擁塞現象；需要的開銷有最小的變化。

4.PADSR（Power Aware DSR）。節能的動態源路由協議PADSR是通過在DSR協議的基礎上運行LAPAR協議進行節能控制來實現的。選擇DSR的原因是它在以下方面的優秀性能：非常低的傳輸帶寬（許多按需路由協議的特征）；最小的路由表更新次數；選擇最短路徑的簡單方法，等等。LAPAR算法能夠在現有的任何路由協議上運行。

二、基于電池能量感知的路由協議

1.節能的單播路由算法

⑴MBCR（最小電池開銷路由算法）。MTPR算法是以總傳輸能量作為衡量標準的。在此算法中定義了節點電池開銷函數，從而計算出包含n個節點的路徑m的總電池開銷，而最大剩余電池能量的路徑即是擁有最小電池開銷的那條路徑。

⑵ MMBCR（最小最大電池開銷路由算法）

由于MBCR考慮的僅僅是電池開銷函數的總和，因此，也可能將剩余很少電量的節點選進來。為了避免節點使用過度，在MBCR的基礎上進行了改進，重新定義了路徑m的電池開銷，即選出電池開銷最大的路徑，然后再在這些路徑中選出相對開銷最小的路徑。這種路由策略會盡量避免每條可能路徑上所有節點中擁有最少電池容量的節點，較之MBCR路由算法更公平一些。

⑶ CMMBCR（有條件最大最小電池容量路由算法）。CMMBCR也是對MBCR的改進，設計CMMBCR的出發點是希望算法能夠使整個網絡的生命周期最大，同時又公平地使用每個節點。其基本思想是首先找出從源節點到目的節點的所有電量充足的路徑(即路徑上的所有節點都具有大于某個閾值(其范圍為[0，100]的剩余電量)，然后從中選擇出總傳輸能量最小的那條路徑作為路由選擇的最終結果。

⑷ MRPC（最大剩余分組容量路由算法）。MRPC算法不僅考慮了節點的相關因素，如節點的剩余能量等，它還考慮到了與鏈路有關的參數。在概念上與MMBCR算法類似，即要尋找那條最小容量最大的路徑，但“容量”的考慮因素和衡量方法不同。

2.自適應的節能路由協議

⑴MREP（最大最小剩余能量路由算法）。MREP目的是工作在網絡層，其中所有的節點以一個統一的發射功率工作。在此協議中并不考慮節點的拓撲信息，從而避免了額外的開銷。MREP也基于按需路由的思想，自適應地選擇出一組中間節點來轉發自己的RREQs分組。因此MREP需要維護一種路由選擇機制，來控制通信開銷和所選路徑的優劣。其中選擇中間節點的標準是根據節點的剩余能量決定的，MREP的路由選擇機制逐漸減小此能量值，直到找到一條路由，或者是能量值減小到零或最小。

⑵MLRP（最小最大鏈路功率路由協議）。MLRP算法旨在尋找一條低功率的路由，其中每個節點都能根據自己要進行通信的鄰近節點自適應地調整發射功率。MLRP的路由發現思想和MREP基本是一致的，但測量標準不同，相應地采用的方法也不同。在此算法中，路由尋找的發起者決定轉發RREQs請求的中間節點的統一發射功率，當路由建立嘗試失敗時，就相應地減小此功率值。因此，此路由進程主要考慮最小化每個參與節點消耗的能量，以及減小所選路徑消耗的能量。

這兩種路由算法都延長了網絡生存時間，同時也極大地減小了所選路由上的通信開銷。

⑶PMADSR（基于能量和移動性感知的自適應動態源路由協議）。在此協議中，設置有兩個極限值r1，r2（r1

3.其他對DSR改進的路由協議

⑴節能的動態源路由協議（ESDSR）。ESDSR是對DSR算法的一種改進。與DSR相比，ESDSR算法中每個分組可以節省40％的能量，對于相同的電池能量消耗，它可以多傳送20％的分組。然而其中的分組并不是通過最小跳數來傳送的，平均跳數將會增加，因此，ESDSR中的網絡延遲可能會比DSR中的大。

⑵DSR-ERP(DSR-based energy-aware routing protocols)。DSR-ERP是在DSR(dynamic source routing)的基礎上提出的，包括2個能量路由策略：RDRP(request-delay routing protoco1)和MMRP(max-min routing protoco1)。兩種策略都是通過對DSR中路由請求廣播的控制，達到保護低能量水平節點的目的。

⑶E-DSR。通過在DSR協議中引入路由的生存時間預測、路由建立時間以及自適應的免費路由應答模式等機制，提出了一種有效的路由算法，即E-DSR。在此協議模型中，網絡中的每個節點首先都以一個恒定的速率移動，在一個任意周期之后，改變自己的移動方向。研究表明此自適應的免費路由應答模式有效地減小了路由開銷，同時也一定程度上影響了網絡的性能。相對DSR來說，E-DSR更加健壯，節點也更加靈活，但由于不是基于跳數的，所以分組端到端的延遲要大一些。另外，由于速率的多元化，E-DSR中的路由比基于跳數的DSR中的更加可靠。

⑷JPBDSR。JPBDSR (Joint Power-aware and Battery-aware DSR)要求在原有的DSR路由請求包中添加兩個字段：總的傳送功率字段(TTP)和最小的電池功率比字段(LBP)。當中間節點接收到一個路由請求包時，如果該節點已經接收過該請求包，或者該節點包括了到達目標節點的路徑信息，則按照原有的DSR策略反饋，如果沒有到達相關目標節點的信息，則執行相關操作后繼續前傳該路由請求包。

研究表明，JPBDSR路由策略是一種有效的節能路由策略，它不僅延長了系統的生存時間，而且具有較好的能耗和路由綜合性能。因為JPBDSR可以通過對DSR路由策略的簡單修改得到，實用性強。

三、 節能的多播和廣播路由協議

1.節能的廣播路由協議

BIP是一個基本的廣播路由算法，它類似與Prim提出的最小生成樹算法（MST），它利用無線通信環境下廣播的特性，建立以源端為根節點的最小能量廣播樹。最初，樹中只包括源節點，BIP開始查找源端能以最小能量開銷到達的節點，并把新發現的節點加進樹中。然后繼續以同樣的方法查找樹中已有節點所能到達的節點，并加入樹中，直到所有的節點都已包含在廣播樹中。許多節能的多播算法都是對BIP的擴展。通過BIP構建好廣播樹后，進行剪枝，即除去那些不需要到達多播組成員的傳輸，從而形成多播樹。

2.節能的多播路由協議

⑴E2MPR (Energy-Efficient Multicast Routing Protoco1)。E2MPR協議在創建和維護中繼組的過程中交替采用分組平均能量消耗最少和最大節點花費最小兩種標準，同時采用了基于圖的多播結構，而不是基于樹的。研究表明較一般的多播選路協議，E2MPR降低了節點的能量消耗，特別是在節點移動性較低、多播成員較少時更是如此。

⑵PMRP （Power-Aware Multicast Routing Protocol）。PMRP是在移動預測機制的條件下提出的。為了選擇一組能夠提供更為穩定和可靠路由的路徑，在路由發現中，每個節點接收到RPEQ分組，并利用能量感知策略來獲得轉發分組所消耗的能量。如果節點還有足夠的剩余能量來轉發數據分組，它就利用GPS確定移動節點的某些特定信息（如位置、速度和方向等），并利用這些信息計算出兩個有相連節點的鏈路終止時間（LET）。分析表明，PMRP要優于MAODV，尤其是在一個節點頻繁移動的環境下。

四、基于中繼組的節能路由算法

RGRP是一個基于中繼組的節能型路由建立模型。首先，是按分組方式組織網絡，每一組中只需要一個節點處于活動狀態，負責接收和暫存該組中所有節點的信息，組中的其它節點則處于非活動狀態，這樣能有效地節約整個網絡的維護能量消耗。其次，源節點可以通過位置查詢方法獲得目的節點的大致位置 ，從而RREQ 并不是在整個網絡中擴散，而是區域性有方向性地擴散，然后為源節點和目的節點尋找一條中繼次數最佳的路由，從而使信息傳輸能耗減小。研究表明， RGRP不管其穩定性還是節能性都明顯優于動態源路由模型DSR。

五、拓撲控制節能路由協議

1.與功率控制相結合的路由協議

網絡拓撲是通過網絡中節點的連接形成的。在無線網絡中，一個節點所維持的鏈路主要是由它的傳輸功率決定的。節點通過妥善管理自己的傳輸功率，可以維持所有必須的鏈路，同時也能減小它的能量消耗。COMPOW (COMmon Power Protoco1)協議是結合節點功率控制的路由策略，它可以和任何表驅動的路由算法結合使用。目前的無線網卡一般都只有有限的幾個發射功率檔，精確估計每條鏈路的發射功率并不是很有必要。COMPOW 就是針對這樣的一個現實展開的。在此協議中，每個節點的發射功率是統一的，這個功率是維持整個網絡聯通的最小功率，采用統一的功率是一種近似最優的功率調整方案。

2.基于拓撲管理的節能路由策略

在Ad Hoc無線網絡中，通信節點一般會處于接收、發送、偵聽以及空閑狀態。當節點處于偵聽和空閑狀態時，仍要不同程度的消耗能量，實驗和觀察表明，在現有的MANET中能量通常并不與網絡中的主動通信量成正比，這進一步說明設備空閑狀態下的能耗在總能耗中占相當的比重。因此，現在有許多協議提出關掉空閑節點的無線電，使其進入睡眠模式。一般的無線網卡也都支持睡眠操作模式。這種路由策略通常也稱為被動路由策略。它的主要目的就是在維持網絡連通性的基礎上，盡可能多地關掉節點的無線電已達到節能的目的。研究表明，每個cell中僅需要一個節點處于活動狀態。

其它相關的路由協議如Span，網絡中每個節點運行Span協議，根據自己的現有能量和對鄰居節點的影響，自主決定成為合作伙伴或者進入睡眠；GAF（Geographical Adaptive Fidelity）算法，使用地理位置信息來延長節點的睡眠時間，等等，在此不再詳細描述。

（作者單位：陜西工業職業技術學院 信息工程系）