移動(dòng)Ａｄ Ｈｏｃ網(wǎng)絡(luò)中節(jié)能的路由協(xié)議研究

移動(dòng)Ad Hoc 網(wǎng)絡(luò)是由一組具有路由功能的移動(dòng)節(jié)點(diǎn)自組織成的無線多跳系統(tǒng)。由于網(wǎng)絡(luò)規(guī)模小、無基礎(chǔ)設(shè)施和構(gòu)建快速等特點(diǎn)，而廣泛應(yīng)用于野外考察、作戰(zhàn)現(xiàn)場(chǎng)、災(zāi)難救助等場(chǎng)合。其中由于網(wǎng)絡(luò)中的節(jié)點(diǎn)通常是以有限能量的電池供電的，限制了節(jié)點(diǎn)生存時(shí)間，從而使得節(jié)能策略成為當(dāng)前一個(gè)研究熱點(diǎn)。目前研究較多的是在路由協(xié)議上實(shí)現(xiàn)節(jié)能控制。本文對(duì)這些節(jié)能路由協(xié)議進(jìn)行了分類和研究，并指出了進(jìn)一步的可能發(fā)展方向。

目前對(duì)移動(dòng)Ad hoc 網(wǎng)絡(luò)路由協(xié)議能量問題的研究有兩種出發(fā)點(diǎn)：一種是尋找一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由，使得路由上所有節(jié)點(diǎn)的能量消耗之和為最低；另一種是調(diào)整網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)使得網(wǎng)絡(luò)的連通時(shí)間達(dá)到最大值。下面從這兩個(gè)方面闡述相關(guān)協(xié)議。

一、主動(dòng)節(jié)能路由協(xié)議

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

2.MTPR (最小總傳輸功率路由算法)。MTPR是一個(gè)分布式的算法。在任一時(shí)刻，Ad Hoc網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可看作是一個(gè)帶權(quán)有向圖，任一條弧上的權(quán)重可量化為發(fā)送節(jié)點(diǎn)所需的最小發(fā)送能量。從而可以用標(biāo)準(zhǔn)的最短路徑算法求出源節(jié)點(diǎn)到目的節(jié)點(diǎn)最小總傳輸能量的路徑。

3.LAPAR（Location Aided Power Aware Routing）。LAPAR協(xié)議是個(gè)GPS輔助型的分布式的能量路由協(xié)議，在此協(xié)議中，發(fā)送節(jié)點(diǎn)首先根據(jù)相鄰節(jié)點(diǎn)的地理位置劃分最佳的轉(zhuǎn)發(fā)區(qū)域。LAPAR的優(yōu)勢(shì)表現(xiàn)為：有效的能量路由；容易嫁接到現(xiàn)有的協(xié)議上；由于采用了僅基于鄰居信息的平面圖，減少了擁塞現(xiàn)象；需要的開銷有最小的變化。

4.PADSR（Power Aware DSR）。節(jié)能的動(dòng)態(tài)源路由協(xié)議PADSR是通過在DSR協(xié)議的基礎(chǔ)上運(yùn)行LAPAR協(xié)議進(jìn)行節(jié)能控制來實(shí)現(xiàn)的。選擇DSR的原因是它在以下方面的優(yōu)秀性能：非常低的傳輸帶寬（許多按需路由協(xié)議的特征）；最小的路由表更新次數(shù)；選擇最短路徑的簡(jiǎn)單方法，等等。LAPAR算法能夠在現(xiàn)有的任何路由協(xié)議上運(yùn)行。

二、基于電池能量感知的路由協(xié)議

1.節(jié)能的單播路由算法

⑴MBCR（最小電池開銷路由算法）。MTPR算法是以總傳輸能量作為衡量標(biāo)準(zhǔn)的。在此算法中定義了節(jié)點(diǎn)電池開銷函數(shù)，從而計(jì)算出包含n個(gè)節(jié)點(diǎn)的路徑m的總電池開銷，而最大剩余電池能量的路徑即是擁有最小電池開銷的那條路徑。

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

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

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

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

2.自適應(yīng)的節(jié)能路由協(xié)議

⑴MREP（最大最小剩余能量路由算法）。MREP目的是工作在網(wǎng)絡(luò)層，其中所有的節(jié)點(diǎn)以一個(gè)統(tǒng)一的發(fā)射功率工作。在此協(xié)議中并不考慮節(jié)點(diǎn)的拓?fù)湫畔ⅲ瑥亩苊饬祟~外的開銷。MREP也基于按需路由的思想，自適應(yīng)地選擇出一組中間節(jié)點(diǎn)來轉(zhuǎn)發(fā)自己的RREQs分組。因此MREP需要維護(hù)一種路由選擇機(jī)制，來控制通信開銷和所選路徑的優(yōu)劣。其中選擇中間節(jié)點(diǎn)的標(biāo)準(zhǔn)是根據(jù)節(jié)點(diǎn)的剩余能量決定的，MREP的路由選擇機(jī)制逐漸減小此能量值，直到找到一條路由，或者是能量值減小到零或最小。

⑵MLRP（最小最大鏈路功率路由協(xié)議）。MLRP算法旨在尋找一條低功率的路由，其中每個(gè)節(jié)點(diǎn)都能根據(jù)自己要進(jìn)行通信的鄰近節(jié)點(diǎn)自適應(yīng)地調(diào)整發(fā)射功率。MLRP的路由發(fā)現(xiàn)思想和MREP基本是一致的，但測(cè)量標(biāo)準(zhǔn)不同，相應(yīng)地采用的方法也不同。在此算法中，路由尋找的發(fā)起者決定轉(zhuǎn)發(fā)RREQs請(qǐng)求的中間節(jié)點(diǎn)的統(tǒng)一發(fā)射功率，當(dāng)路由建立嘗試失敗時(shí)，就相應(yīng)地減小此功率值。因此，此路由進(jìn)程主要考慮最小化每個(gè)參與節(jié)點(diǎn)消耗的能量，以及減小所選路徑消耗的能量。

這兩種路由算法都延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間，同時(shí)也極大地減小了所選路由上的通信開銷。

⑶PMADSR（基于能量和移動(dòng)性感知的自適應(yīng)動(dòng)態(tài)源路由協(xié)議）。在此協(xié)議中，設(shè)置有兩個(gè)極限值r1，r2（r1

3.其他對(duì)DSR改進(jìn)的路由協(xié)議

⑴節(jié)能的動(dòng)態(tài)源路由協(xié)議（ESDSR）。ESDSR是對(duì)DSR算法的一種改進(jìn)。與DSR相比，ESDSR算法中每個(gè)分組可以節(jié)省40％的能量，對(duì)于相同的電池能量消耗，它可以多傳送20％的分組。然而其中的分組并不是通過最小跳數(shù)來傳送的，平均跳數(shù)將會(huì)增加，因此，ESDSR中的網(wǎng)絡(luò)延遲可能會(huì)比DSR中的大。

⑵DSR-ERP(DSR-based energy-aware routing protocols)。DSR-ERP是在DSR(dynamic source routing)的基礎(chǔ)上提出的，包括2個(gè)能量路由策略：RDRP(request-delay routing protoco1)和MMRP(max-min routing protoco1)。兩種策略都是通過對(duì)DSR中路由請(qǐng)求廣播的控制，達(dá)到保護(hù)低能量水平節(jié)點(diǎn)的目的。

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

⑷JPBDSR。JPBDSR (Joint Power-aware and Battery-aware DSR)要求在原有的DSR路由請(qǐng)求包中添加兩個(gè)字段：總的傳送功率字段(TTP)和最小的電池功率比字段(LBP)。當(dāng)中間節(jié)點(diǎn)接收到一個(gè)路由請(qǐng)求包時(shí)，如果該節(jié)點(diǎn)已經(jīng)接收過該請(qǐng)求包，或者該節(jié)點(diǎn)包括了到達(dá)目標(biāo)節(jié)點(diǎn)的路徑信息，則按照原有的DSR策略反饋，如果沒有到達(dá)相關(guān)目標(biāo)節(jié)點(diǎn)的信息，則執(zhí)行相關(guān)操作后繼續(xù)前傳該路由請(qǐng)求包。

研究表明，JPBDSR路由策略是一種有效的節(jié)能路由策略，它不僅延長(zhǎng)了系統(tǒng)的生存時(shí)間，而且具有較好的能耗和路由綜合性能。因?yàn)镴PBDSR可以通過對(duì)DSR路由策略的簡(jiǎn)單修改得到，實(shí)用性強(qiáng)。

三、 節(jié)能的多播和廣播路由協(xié)議

1.節(jié)能的廣播路由協(xié)議

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

2.節(jié)能的多播路由協(xié)議

⑴E2MPR (Energy-Efficient Multicast Routing Protoco1)。E2MPR協(xié)議在創(chuàng)建和維護(hù)中繼組的過程中交替采用分組平均能量消耗最少和最大節(jié)點(diǎn)花費(fèi)最小兩種標(biāo)準(zhǔn)，同時(shí)采用了基于圖的多播結(jié)構(gòu)，而不是基于樹的。研究表明較一般的多播選路協(xié)議，E2MPR降低了節(jié)點(diǎn)的能量消耗，特別是在節(jié)點(diǎn)移動(dòng)性較低、多播成員較少時(shí)更是如此。

⑵PMRP （Power-Aware Multicast Routing Protocol）。PMRP是在移動(dòng)預(yù)測(cè)機(jī)制的條件下提出的。為了選擇一組能夠提供更為穩(wěn)定和可靠路由的路徑，在路由發(fā)現(xiàn)中，每個(gè)節(jié)點(diǎn)接收到RPEQ分組，并利用能量感知策略來獲得轉(zhuǎn)發(fā)分組所消耗的能量。如果節(jié)點(diǎn)還有足夠的剩余能量來轉(zhuǎn)發(fā)數(shù)據(jù)分組，它就利用GPS確定移動(dòng)節(jié)點(diǎn)的某些特定信息（如位置、速度和方向等），并利用這些信息計(jì)算出兩個(gè)有相連節(jié)點(diǎn)的鏈路終止時(shí)間（LET）。分析表明，PMRP要優(yōu)于MAODV，尤其是在一個(gè)節(jié)點(diǎn)頻繁移動(dòng)的環(huán)境下。

四、基于中繼組的節(jié)能路由算法

RGRP是一個(gè)基于中繼組的節(jié)能型路由建立模型。首先，是按分組方式組織網(wǎng)絡(luò)，每一組中只需要一個(gè)節(jié)點(diǎn)處于活動(dòng)狀態(tài)，負(fù)責(zé)接收和暫存該組中所有節(jié)點(diǎn)的信息，組中的其它節(jié)點(diǎn)則處于非活動(dòng)狀態(tài)，這樣能有效地節(jié)約整個(gè)網(wǎng)絡(luò)的維護(hù)能量消耗。其次，源節(jié)點(diǎn)可以通過位置查詢方法獲得目的節(jié)點(diǎn)的大致位置 ，從而RREQ 并不是在整個(gè)網(wǎng)絡(luò)中擴(kuò)散，而是區(qū)域性有方向性地?cái)U(kuò)散，然后為源節(jié)點(diǎn)和目的節(jié)點(diǎn)尋找一條中繼次數(shù)最佳的路由，從而使信息傳輸能耗減小。研究表明， RGRP不管其穩(wěn)定性還是節(jié)能性都明顯優(yōu)于動(dòng)態(tài)源路由模型DSR。

五、拓?fù)淇刂乒?jié)能路由協(xié)議

1.與功率控制相結(jié)合的路由協(xié)議

網(wǎng)絡(luò)拓?fù)涫峭ㄟ^網(wǎng)絡(luò)中節(jié)點(diǎn)的連接形成的。在無線網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)所維持的鏈路主要是由它的傳輸功率決定的。節(jié)點(diǎn)通過妥善管理自己的傳輸功率，可以維持所有必須的鏈路，同時(shí)也能減小它的能量消耗。COMPOW (COMmon Power Protoco1)協(xié)議是結(jié)合節(jié)點(diǎn)功率控制的路由策略，它可以和任何表驅(qū)動(dòng)的路由算法結(jié)合使用。目前的無線網(wǎng)卡一般都只有有限的幾個(gè)發(fā)射功率檔，精確估計(jì)每條鏈路的發(fā)射功率并不是很有必要。COMPOW 就是針對(duì)這樣的一個(gè)現(xiàn)實(shí)展開的。在此協(xié)議中，每個(gè)節(jié)點(diǎn)的發(fā)射功率是統(tǒng)一的，這個(gè)功率是維持整個(gè)網(wǎng)絡(luò)聯(lián)通的最小功率，采用統(tǒng)一的功率是一種近似最優(yōu)的功率調(diào)整方案。

2.基于拓?fù)涔芾淼墓?jié)能路由策略

在Ad Hoc無線網(wǎng)絡(luò)中，通信節(jié)點(diǎn)一般會(huì)處于接收、發(fā)送、偵聽以及空閑狀態(tài)。當(dāng)節(jié)點(diǎn)處于偵聽和空閑狀態(tài)時(shí)，仍要不同程度的消耗能量，實(shí)驗(yàn)和觀察表明，在現(xiàn)有的MANET中能量通常并不與網(wǎng)絡(luò)中的主動(dòng)通信量成正比，這進(jìn)一步說明設(shè)備空閑狀態(tài)下的能耗在總能耗中占相當(dāng)?shù)谋戎亍Ｒ虼耍F(xiàn)在有許多協(xié)議提出關(guān)掉空閑節(jié)點(diǎn)的無線電，使其進(jìn)入睡眠模式。一般的無線網(wǎng)卡也都支持睡眠操作模式。這種路由策略通常也稱為被動(dòng)路由策略。它的主要目的就是在維持網(wǎng)絡(luò)連通性的基礎(chǔ)上，盡可能多地關(guān)掉節(jié)點(diǎn)的無線電已達(dá)到節(jié)能的目的。研究表明，每個(gè)cell中僅需要一個(gè)節(jié)點(diǎn)處于活動(dòng)狀態(tài)。

其它相關(guān)的路由協(xié)議如Span，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)運(yùn)行Span協(xié)議，根據(jù)自己的現(xiàn)有能量和對(duì)鄰居節(jié)點(diǎn)的影響，自主決定成為合作伙伴或者進(jìn)入睡眠；GAF（Geographical Adaptive Fidelity）算法，使用地理位置信息來延長(zhǎng)節(jié)點(diǎn)的睡眠時(shí)間，等等，在此不再詳細(xì)描述。

（作者單位：陜西工業(yè)職業(yè)技術(shù)學(xué)院 信息工程系）