摘 要： 提出一種可以延長移動Ad Hoc網(wǎng)絡(luò)壽命的節(jié)能路由協(xié)議" title="路由協(xié)議">路由協(xié)議ESR。它集成了傳輸功率控制" title="功率控制">功率控制和負(fù)載均衡" title="負(fù)載均衡">負(fù)載均衡兩種方式的優(yōu)點(diǎn)來實(shí)現(xiàn)節(jié)能路由協(xié)議。在通過負(fù)載均衡確定路由后，根據(jù)傳輸功率控制來調(diào)整鏈路" title="鏈路">鏈路間數(shù)據(jù)包的傳輸功率。仿真結(jié)果表明，與DSR相比，ESR協(xié)議可以有效地節(jié)能并延長Ad Hoc網(wǎng)絡(luò)的壽命。
關(guān)鍵詞：Ad Hoc網(wǎng)絡(luò)? 路由? 節(jié)能? 功率調(diào)整

?

移動Ad Hoc網(wǎng)絡(luò)作為一種即時的無中心、自組織、多跳網(wǎng)絡(luò)得到了飛速的發(fā)展。網(wǎng)絡(luò)中的節(jié)點(diǎn)一般借助電池供電，因此節(jié)點(diǎn)的可用性對于成功傳遞數(shù)據(jù)包非常重要。任意一個節(jié)點(diǎn)失效都會影響整個網(wǎng)絡(luò)的性能。由于節(jié)點(diǎn)均由電池提供能量，節(jié)點(diǎn)失效的一個重要原因就是電量耗盡。為了延長節(jié)點(diǎn)的生存時間，有必要減少節(jié)點(diǎn)在傳輸數(shù)據(jù)包時所消耗的能量。
近年來，對于Ad Hoc網(wǎng)絡(luò)如何節(jié)能已經(jīng)作了一系列的研究，這些研究可以分為兩類：傳輸功率控制和負(fù)載均衡。其中，傳輸功率控制決定了從源端到目的端傳輸數(shù)據(jù)包所需要最小能量的路徑。負(fù)載均衡主要通過將負(fù)載均勻地分配到各個節(jié)點(diǎn)來使網(wǎng)絡(luò)耗能均勻。但并沒有一種或一系列專門的協(xié)議適合所有的場景。
文獻(xiàn)[1]提出了從源端到目的端耗能最小的路由協(xié)議。它的缺點(diǎn)：總是選擇功率最小的路由，致使這條路徑上的節(jié)點(diǎn)過早地消亡。文獻(xiàn)[2]中給出了基于GPS信息的傳輸功率調(diào)整，但是GPS信息不包括諸如噪聲、干擾和沖突等環(huán)境信息。許多學(xué)者試圖用負(fù)載均衡來克服傳輸功率控制的缺陷。文獻(xiàn)[3]提到了最小電量消耗路由協(xié)議，它以傳輸所需電量最小為衡量路由的尺度。文獻(xiàn)[4]中，節(jié)點(diǎn)是否轉(zhuǎn)發(fā)路由請求包取決于它剩余電量的多少，如果剩余電量超過門限值，則可以轉(zhuǎn)發(fā)；否則，就丟棄該請求包。負(fù)載均衡的缺點(diǎn)：假定所有節(jié)點(diǎn)以相同的功率進(jìn)行傳輸而不考慮接收端的位置是否會造成能量的浪費(fèi)。因?yàn)楫?dāng)發(fā)送端與接收端相距較近時，就可以很小的功率進(jìn)行傳輸，從而節(jié)省很多能量。
本文提出的節(jié)能路由協(xié)議ESR集成了以上兩種方法的優(yōu)點(diǎn)，在其路由查找階段，可以避免節(jié)點(diǎn)過早地消亡。節(jié)點(diǎn)的消亡趨勢可以通過剩余能量和當(dāng)前傳輸功率來描述，稱為節(jié)點(diǎn)的期望時間。當(dāng)路徑確定后，即可根據(jù)接收端接收到的數(shù)據(jù)包的信號強(qiáng)度來調(diào)整鏈路間的功率。
1 DSR協(xié)議
動態(tài)源路由協(xié)議DSR[5]是一種基于源路由的按需路由協(xié)議，它使用源路由算法，發(fā)送方知道應(yīng)該經(jīng)過哪些中間節(jié)點(diǎn)逐跳到達(dá)目的地，這些路由存儲在一個緩存中。數(shù)據(jù)包在包頭攜帶所需的源路由信息。DSR路由協(xié)議主要包括兩個過程：路由發(fā)現(xiàn)和路由維持。
路由發(fā)現(xiàn)：當(dāng)節(jié)點(diǎn)S向節(jié)點(diǎn)D發(fā)送數(shù)據(jù)時，它首先檢查緩存是否存在未過期的到目的節(jié)點(diǎn)的路由，如果存在，則直接使用可用的路由，否則啟動路由發(fā)現(xiàn)過程。具體過程如下：源節(jié)點(diǎn)S將使用洪泛法發(fā)送路由請求消息（RREQ），RREQ包含源和目的節(jié)點(diǎn)地址以及惟一的標(biāo)志號，中間節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQ，并附上自己的節(jié)點(diǎn)標(biāo)識。當(dāng)RREQ消息到達(dá)目的節(jié)點(diǎn)D或任何一個到目的節(jié)點(diǎn)路由的中間節(jié)點(diǎn)時（此時，RREQ中已記錄了從S到D或該中間節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)標(biāo)識），D或該中間節(jié)點(diǎn)將向S發(fā)送路由應(yīng)答消息（RREP），該消息中將包含S到D的路由信息，并反轉(zhuǎn)S到D的路由供RREP消息使用。源節(jié)點(diǎn)將此路由寫入自己的緩存中以備今后使用。
路由維持：一旦某個節(jié)點(diǎn)在發(fā)送數(shù)據(jù)時發(fā)現(xiàn)需要使用的鄰接鏈路斷開，它立即發(fā)送一個路由錯誤（RERR）包給源節(jié)點(diǎn)S，源節(jié)點(diǎn)S收到這一錯誤包后在緩存中刪除所有使用到這條鏈路的路由，并在必要時再啟動路由發(fā)現(xiàn)過程。而沿途轉(zhuǎn)發(fā)這一錯誤包的節(jié)點(diǎn)也從自己的路由表中刪除該斷開鏈路的所有路由。
DSR協(xié)議以最小跳數(shù)為路由衡量尺度。路由確定以后，源端以默認(rèn)的最大功率傳輸數(shù)據(jù)包，但沒有考慮節(jié)能問題。
2 ESR協(xié)議
在ESR協(xié)議的路由查找階段，可以避免節(jié)點(diǎn)過早地消亡。在確定路由時，綜合考慮了節(jié)點(diǎn)的剩余能量和傳輸功率。剩余能量與傳輸功率之比顯示了節(jié)點(diǎn)的耗能趨勢。源端在時間t發(fā)現(xiàn)路由，并選擇具有最大值的那條路由。

其中，Rj(t)為路徑j(luò)的能量與傳輸功率比的最小值;Ei為這條路徑上節(jié)點(diǎn)i的剩余能量;Pti為節(jié)點(diǎn)i的傳輸功率。
?ESR協(xié)議中的路由查詢機(jī)制如圖1所示。節(jié)點(diǎn)1為源端，節(jié)點(diǎn)5為目的端。假定所有節(jié)點(diǎn)的緩存都為空,t時刻，當(dāng)源端發(fā)起路由查詢時，各節(jié)點(diǎn)的能量和傳輸功率如圖1所示。源端通過廣播一個路由請求包來啟動路由查詢機(jī)制。節(jié)點(diǎn)2和節(jié)點(diǎn)4都在節(jié)點(diǎn)1的傳輸范圍內(nèi)。因?yàn)橹虚g節(jié)點(diǎn)2和4都非目的節(jié)點(diǎn)，這兩個節(jié)點(diǎn)必須把自己的ID寫入路由請求包中，繼續(xù)廣播該路由包。當(dāng)目的節(jié)點(diǎn)5接收到該路由請求包時，通過反轉(zhuǎn)節(jié)點(diǎn)1到節(jié)點(diǎn)5的路由，立即向節(jié)點(diǎn)1發(fā)送一個路由回復(fù)包。

?

假定目的節(jié)點(diǎn)5通過路由5-3-2-1回復(fù)到節(jié)點(diǎn)1。當(dāng)中間節(jié)點(diǎn)3收到該路由回復(fù)包時，它通過來估計(jì)自己的“生存時間”。假定這個值為 0.2，節(jié)點(diǎn)3在路由回復(fù)包里記錄這個值，然后轉(zhuǎn)發(fā)該路由回復(fù)包到節(jié)點(diǎn)2。節(jié)點(diǎn)2用同樣的公式來估計(jì)其“生存時間”，假定為0.1。同時，節(jié)點(diǎn)2讀取路由回復(fù)包里記錄的上一個節(jié)點(diǎn)的“生存時間”值（此時這個值為0.2）。由于節(jié)點(diǎn)2的生存時間相對節(jié)點(diǎn)3的生存時間要小，因此，它將取代路由回復(fù)包中節(jié)點(diǎn)3的“生存時間”。此時，路徑1-2-3-5的路由回復(fù)包中攜帶的“生存時間”為0.1。源節(jié)點(diǎn)1將在路由緩存中記錄這一路由。假定此時源節(jié)點(diǎn)1也發(fā)現(xiàn)了另一條路徑1-4-5，這條路徑的“生存時間”為0.005。在這兩條路徑中，源節(jié)點(diǎn)1將選擇1-2-3-5，因?yàn)檫@條路徑的“生存時間”高于路徑1-4-5。但是以最小跳數(shù)為衡量尺度的DSR協(xié)議將會選擇路徑1-4-5。
當(dāng)源節(jié)點(diǎn)查詢完路徑并按照上述方法選擇完路徑后，開始在這條路徑上發(fā)送數(shù)據(jù)。此時，鏈路間的功率調(diào)整根據(jù)以下的步驟來完成：每一個節(jié)點(diǎn)都在數(shù)據(jù)包中記錄自己的發(fā)送功率，然后將數(shù)據(jù)發(fā)送到下一跳節(jié)點(diǎn)。當(dāng)下一跳節(jié)點(diǎn)以功率Precv接收到數(shù)據(jù)包時，同時讀取數(shù)據(jù)包內(nèi)上一節(jié)點(diǎn)的傳輸功率Ptx，然后為上一跳節(jié)點(diǎn)重新計(jì)算發(fā)送功率。
P_min=P_tx-P_recv+P_{threshold??????????????????????? ?} (3)
其中，所有單位都為dbW。P_threshold為接收節(jié)點(diǎn)所能成功接收該數(shù)據(jù)包所要求的功率門限。在LAN 802.11中，P_threshold為3.652×10^-10 W。為了克服由于信道波動帶來的鏈路不穩(wěn)定性，在等式3中加入一個差值P_margin。
P_min=P_tx-P_recv+P_threshold+P_{margin????????????????} (4)
重新計(jì)算得到的傳輸功率記錄在功率表" title="功率表">功率表中。每一個節(jié)點(diǎn)都包含一個功率表，用來記錄目標(biāo)節(jié)點(diǎn)的ID和到目標(biāo)節(jié)點(diǎn)的傳輸功率。重新計(jì)算的傳輸功率記錄在ACK包中。當(dāng)ACK包被發(fā)送節(jié)點(diǎn)接收到時，在功率表中更新傳輸功率，并且以更新后的傳輸功率來傳送數(shù)據(jù)包。
在本次試驗(yàn)中，假定差值為1dB，通常差值為3dB^[6]。因?yàn)樵诒敬卧囼?yàn)中，傳輸功率的監(jiān)視是通過數(shù)據(jù)包來實(shí)現(xiàn)的，所以差值采用1dB。數(shù)據(jù)包監(jiān)視的目的是:當(dāng)數(shù)據(jù)包傳輸過程中信道狀況發(fā)生改變時，傳輸功率也能隨之改變。同時，因?yàn)楸驹囼?yàn)的功率采用了一個很小的差值，因此相比文獻(xiàn)[6]中提到的協(xié)議能節(jié)省很多的能量。
當(dāng)節(jié)點(diǎn)接收到來自鄰居節(jié)點(diǎn)的數(shù)據(jù)包時，功率表將隨之更新。當(dāng)一個節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)包到另一個節(jié)點(diǎn)時，它就會查找功率表中到該節(jié)點(diǎn)的發(fā)送功率，若查詢到，就以該功率發(fā)送數(shù)據(jù)包。若沒有查詢到相應(yīng)的功率值，則以默認(rèn)的功率傳輸(默認(rèn)功率為280mW，傳輸范圍為250m)。為了體現(xiàn)DSR協(xié)議的查詢功能，所有路由包（路由請求包、路由回復(fù)包）都以默認(rèn)的功率傳輸。另外，為了維持MAC層操作的一般性，所有MAC層的包（TRS、CTS、ACK）都以默認(rèn)的功率傳輸。
為了觀察功率調(diào)整對能量消耗的影響，應(yīng)用了文獻(xiàn)[6]中的模型。在給定鏈路上，每D字節(jié)數(shù)據(jù)包消耗的能量為：?

E(D，P_t)=K₁P_tD+K_{2?????????????????????????????????????????} (5)
在數(shù)據(jù)傳輸速率為2Mbps的802.11MAC環(huán)境中，K₁、K₂分別為。
3 仿真模型
因?yàn)榻邮展β适且粋€常數(shù)，當(dāng)節(jié)點(diǎn)接收數(shù)據(jù)包時會有一部分固定的能量被消耗，故令接收功率為0。媒體接入控制(MAC)協(xié)議為IEEE802.11，信道速率為2Mbps。802.11分布式協(xié)調(diào)功能利用請求發(fā)送（RTS）和清除發(fā)送(CTS)來控制數(shù)據(jù)包的發(fā)送。利用虛擬載波監(jiān)聽和信道預(yù)留來減少隱藏終端帶來的影響。無線傳輸模型為雙向路徑損耗。在仿真中，不考慮信道的衰落。業(yè)務(wù)源為固定比特率(CBR)，數(shù)據(jù)包長為512B,發(fā)送速度為4包/秒。每個節(jié)點(diǎn)都包含一個功率表。包頭結(jié)構(gòu)增加傳輸功率域和接收功率門限域。
在一個靜態(tài)場景中，40個節(jié)點(diǎn)隨機(jī)分布在正方形的仿真區(qū)域內(nèi)。仿真區(qū)域?yàn)?00m×200m、300m×300m、400m×400m和500m×500m；源節(jié)點(diǎn)和目的節(jié)點(diǎn)隨機(jī)組合。仿真周期為250s；計(jì)算所有節(jié)點(diǎn)消耗的能量和仿真結(jié)束前節(jié)點(diǎn)的消亡數(shù)。每個節(jié)點(diǎn)的初始化能量為1.0J。
為了與DSR協(xié)議的性能作比較，需關(guān)注以下性能參數(shù)：
成功投遞的數(shù)據(jù)包數(shù)：在仿真結(jié)束時，成功到達(dá)目的端的所有數(shù)據(jù)包的總和。
每個數(shù)據(jù)包的耗能：網(wǎng)絡(luò)中消耗的總能量與成功到達(dá)目的端的數(shù)據(jù)包的數(shù)目之比。
消亡的節(jié)點(diǎn)數(shù)：在仿真結(jié)束時，由于能量耗盡而過早消亡的節(jié)點(diǎn)數(shù)總和。
4 仿真結(jié)果分析
圖2顯示了成功投遞的數(shù)據(jù)包數(shù)。ESR協(xié)議中成功投遞的數(shù)據(jù)包數(shù)明顯大于DSR協(xié)議。原因是：DSR協(xié)議在仿真階段有一些節(jié)點(diǎn)電量過早地耗盡而消亡，因此，它們不能發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)包。但在ESR協(xié)議中，節(jié)點(diǎn)的生存時間卻很長，所有節(jié)點(diǎn)都有能力發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)包。每個數(shù)據(jù)包的能量消耗如圖3所示。當(dāng)網(wǎng)絡(luò)范圍是200m×200m時，每個數(shù)據(jù)包的耗能約在0.75mJ。但在同樣的場景下，DSR協(xié)議中每個數(shù)據(jù)包卻消耗約1.25mJ。當(dāng)擴(kuò)大網(wǎng)絡(luò)范圍時，每個數(shù)據(jù)包的耗能也在增加。因?yàn)樵诖蟮木W(wǎng)絡(luò)范圍內(nèi)，數(shù)據(jù)要經(jīng)過多跳才能到達(dá)目的節(jié)點(diǎn)，所以每個數(shù)據(jù)包的耗能就會增加。當(dāng)網(wǎng)絡(luò)范圍為500m×500m時，ESR與DSR中數(shù)據(jù)包耗能基本相同。ESR中節(jié)能百分比如圖4所示，ESR與DSR相比可以節(jié)能37%。仿真結(jié)束時，節(jié)點(diǎn)消亡的個數(shù)如圖5所示，當(dāng)ESR中有一個節(jié)點(diǎn)消亡時，DSR中就有5個節(jié)點(diǎn)消亡。但當(dāng)網(wǎng)絡(luò)范圍擴(kuò)大為200m×200m時，節(jié)點(diǎn)消亡個數(shù)趨于相等。這是因?yàn)榫W(wǎng)絡(luò)范圍變大時，ESR中的傳輸功率與DSR中的傳輸功率基本相等，所以ESR與DSR有相同的消亡節(jié)點(diǎn)數(shù)。

?

?

?

?

文章提出了一個節(jié)能路由協(xié)議（ESR）。仿真結(jié)果表明：與DSR相比，ESR協(xié)議可以有效地節(jié)能、延長Ad Hoc網(wǎng)絡(luò)的壽命。同時ESR協(xié)議也帶來開銷：數(shù)據(jù)包頭部附加的信息改變了數(shù)據(jù)包的結(jié)構(gòu)，增加了數(shù)據(jù)包的長度。傳輸功率控制的引進(jìn)將會導(dǎo)致無線設(shè)備的硬件改動。由于數(shù)據(jù)包不是通過最小跳數(shù)傳送的，所以平均跳數(shù)就會增加，因此，ESR中的延遲將會大于DSR。
參考文獻(xiàn)
[1]?SINGH S, WOO M, RAGHAVENDRA C S. Power-aware?routing in mobile Ad Hoc networks. In:Proc.of the Fourth
????? Annual ACM/IEEE International Conference on Mobile?Computing and Networking, October, 1998：181-190.
[2]?IVAN S, LIN X.Power-aware localized routing in wireless?networks. In: Proc.of the 14th International Symposium on??Parallel and Distributed Processing, May 1-5,2000:371.
[3] ?TOH C K. Maximum battery life routing to support?ubiquitous mobile computing in wireless Ad Hoc networks.
?IEEE Communication Magazine, 2001,6:138-147.
[4] ?WOO K, YU C, YOUN H Y et al. Non-Blocking localized routing ?algorithm for balanced energy consumption
?in mobile Ad Hoc networks. In:Proc. of International Symp.On Modeling,Analysis and Simulation of Computer and??Telecommunication Systems (MASCOTS 2001):117-124.
[5] ?BROCH J, JOHNSON D B, MALTZ D A. The dynamic?source routing protocol for mobile Ad Hoc networks. IETF ??Internet-Draft, draft-ietf-manet-dsr-00.txt, March 1998.
[6]?SHEETAL K D, TIMOTHY X B.An on demand minimum?energy routing protocol for a wireless Ad Hoc network.
?Proc. of ACM SIGMOBILE Mobile Computing and Communication Review.2002,6(3):50-66.