1         引言

Ad hoc網絡是由一組自主的無線節點或終端組成的，獨立于固定的基礎設施、采用分布式管理的多跳網絡。通常由于無線設備的無線電傳輸范圍有限，當無線節點和目的端不能直接通信時，中間節點同時充當了終端系統和路由器兩種角色。Ad hoc網絡一般可以分為兩類：靜態Ad hoc，移動Ad hoc。在靜態Ad hoc中，一旦節點加入到網絡中，節點位置不再變化；在移動Ad hoc中，節點可能隨時發生位置改變。正是由于這種無預先報告的頻繁拓撲變化使得路由問題成為此類網絡中的一個挑戰。

通常在Ad hoc網絡中，節點設備都是由電池供能的，并且由于便于攜帶、體積小的設備特點，很大程度上限制了電池的大小和電量。一旦設備電量耗盡，即認為此節點不再有效，不僅此節點被排出網絡，而且會影響到其他有效節點正常工作。Vikas Kawadia et al.[1] 指出降低能耗設計可以在無線網絡的任何一層無線網絡協議棧中實現。而節點發送、接收、轉發數據包損耗的能量也有所不同，其中在無線信道中用于數據包傳輸的能量最不可忽視，是設備能量消耗最高的一部分。因此，非常有必要設計低能耗路由協議來確保電池的有效使用時間更長。

2         傳統Ad hoc網絡路由協議

近年來，許多研究者針對Ad hoc網絡的特點設計了大量的路由協議。歸納起

來，所有這些協議可以分為兩大類：基于拓撲的與基于位置的路由。

2.1 基于拓撲的路由協議

基于拓撲的路由協議利用現存于網絡中的鏈路信息完成數據包轉發。根據獲得路由信息的時機，又可以將基于拓撲的路由協議細分為先驗式,按需式或反應式，和混合式路由協議。先驗式路由協議采用傳統的路由策略，如：DSDV[2]基于距離矢量路由；OLSR[3]與TBRPF[4]基于鏈路狀態路由。即使當前網絡中的部分路徑未被使用，先驗式路由協議中每個節點也會維護到網絡中其他所有節點的路由表。當拓撲頻繁發生變化時，很大程度上增大網絡維護路由表的額外開銷。由于這個缺點，按需路由協議(DSR[5], TORA[6], and AODV[7]等)問世了，他們只需要維護當前使用的路由。如果當前只使用了很少一部分路由，大部分節點既不需要廣播，又不需要更新路由信息，減輕了網絡負擔，減少了節點的能量損耗。但是兩個節點想要通信，除了維護在使用中的路由，還需要一個路由發現的過程，這將導致第一個包的傳輸延遲。除此之外，由于到目的節點的路由發生變化而引起的數據包丟失也是按需路由算法仍然不能解決的問題�；旌闲�Ad hoc路由協議(如ZRP[8])使用局部先驗路由與全局按需路由的策略，以獲得更高的效率。但即使綜合使用兩種策略，仍不免要在一定時間內限制拓撲的變化次數，來利用有限的資源維護正在使用的路由。

2.2 基于位置的路由協議

基于位置的路由算法降低了基于拓撲的路由算法的局限性。但是所有加入網絡

的節點都必須通過GPS或者其他種類的定位服務來提供物理位置這樣的額外信

息。每個源節點首先要通過發送一個數據包測定目的節點位置。路由由目的節

點位置和前驅節點位置決定。此路由策略無需建立和維護路由，所有節點既不

需要保存路由表，也不需要更新路由表信息，從某種程度上減少了節點通信所

耗費的能量，但是仍然不能解決Ad hoc無線網絡中的能耗問題。

3         Ad hoc網絡中基于能量有效的路由協議

 在通信過程中，能量開銷主要在以下四個方面：

1）  發送消息所耗費的能量；

2）  接收消息所耗費的能量；

3）  系統空閑所耗費的能量（此種情況下，無線電仍然開啟，但沒有接收信號）；

4）  系統休眠所耗費的能量（此種情況下，無線電關閉）。

節點在空閑狀態下通過關閉無線電可以大量節省由于處于監聽狀態所消耗的過多能量。[2]提出的兩種算法建立在按需路由協議的基礎上，根據實際需求通過應用層關閉無線電，讓系統休眠，以期在能量消耗和數據傳輸質量之間達到折中。

相對而言，無線網絡協議棧中第三層協議的設計可以更顯著的優化系統能耗。與傳統Ad hoc路由協議不同，基于能量有效的路由協議的目標為最大化網絡生命周期。網絡生命周期即網絡中的一個節點首次耗盡電量的時間[9]。如果一個節點停止運行，會導致網絡分裂，部分通信中斷。而不同的路由選擇標準也會影響網絡性能，這些路由選擇度量標準的主要基于以下幾點：(1)網絡中轉發信息所消耗的總能量，(2)每個節點的初始電池電量，(3)每個節點的剩余電量。因此，路由選擇不僅需要從網絡角度考慮，最小化網絡路由總能耗，而且需要從節點角度考慮，確保節點壽命最大化。任何一個基于能量有效的路由算法都能達到這一個或者兩個目標。顯而易見，選擇最小跳數路由可使總傳輸能量損耗最小化；但是，如果最小跳數路由多次包含某一個節點，此節點就會比其他節點更早衰竭，網絡生命周期也會隨之降低，因此很難同時達到最小化總能耗和最大化節點壽命兩個目標。

3.1 最小總傳輸能量路由（MTPR）

為確保主機 與 能夠成功通信，端信噪比必須大于給定閾值 。

等式中， 為主機的傳輸能量， 為 與之間的能量滾降（n=2為近距離，n＝4為遠距離)，為主機的熱噪聲， 閾值與接收信號的比特差錯率（BER）相關。

由上可見，噪聲、距離、BER等因素的影響可以通過調整傳輸能量來補償。換言之，為使傳輸總能量最小化，主機和間的傳輸能量 可以作為一種計量標準。

路由 的總傳輸能量為 ，其中 、 分別為源與目的節點。

則總傳輸能量最小的路由 ，其中A為所有可選路由集合。

因此，可以在標準最短路徑算法（如Dijkstra或Bellman-Ford）的基礎上稍作修改以獲得期望路由。同等情況下，傳輸能量和傳輸距離 成正比，本算法較傾向于節點之間距離較近的多跳路由。然而，在一條路由中包含的節點越多，端到端的延遲則越大；中間節點移出的概率越高；路由越不穩定。

3.2 最小電池開銷路由（MBCR）

雖然總傳輸能量可以作為一個非常重要的度量標準，但是它有非常明顯的缺

陷。如前所述，MTPR雖然降低了整個網絡的能量消耗，但是它并未考慮到單個

主機的使用壽命。當某個節點多次被路由，此節點的電池會很快被用盡。因

此，可以考慮采用移動節點的電池剩余能量作為其生存時間的度量標準。

根據節點轉發數據包的情況，某時刻 的電池開銷為函數，其中為 時刻電池電量。

路由 的電量開銷為 。由此可知， 時刻電池剩余電量越大，則越小， 越小。

即最大剩余電量路由為 。

MBCR有效防止某主機被過度使用，從而延遲網絡被分隔的時間，增加網絡生命周期。

但是由于MBCR考慮的是某路由中所有節點的剩余電量之和，而非單個節點的狀態，所以MBCR仍然會選擇某些具有極少電量的節點來路由，造成這些節點提前衰竭。

3.3 最大——最小電池開銷路由（MMBCR）

路由的電量開銷定義為 。則最大——最小電池開銷路由為 。

圖1 最大——最小電池開銷路由（MMBCR）

如圖1所示，路由1中3號節點剩余電量最少，即 ；路由2中5號節點剩余電量最少，即 。兩者取其小，即路由2為最佳路由。

MMBCR可以有效避免路由含有最小剩余電量節點（如路由1中3號節點），但是很多情況下為了保證節點使用的均衡性，卻選擇了較長的路徑，犧牲了網絡性能。

3.4 受限的最大——最小電量路由（CMMBCR）

CMMBCR既考慮MTPR的總傳輸能量，又考慮MMBCR中的節點剩余電量。即在幾條所有節點都有足夠的剩余電量（大于閾值 ）的路由中，挑選出一條總傳輸能量最小的路由。

路由在時刻的電池電量  ，以此來選擇每條路由中最小剩余電量做 。

令 ，A為滿足此條件的所有路由集合。 是電量閾值（0―100），可看作保護此節點電量消耗的臨界值。當電池電量小于，則此節點不會被路由。

令Q為時刻所有S到D的可用路由的集合。

如果，即找到了若干條節點電量大于等于的路由，在他們之間再利用MTPR選擇一條總傳輸能量最小的路由。

如果，就利用 選擇一條剩余電量最大的路由。

圖2 閾值的選取與平均路徑長度之間的關系

如圖2.可見，閾值越大，對單個節點的保護程度越強，但是卻增大了平均路徑長度，犧牲了網絡中的其他節點。如果=0，則CMMBCR等同于MTPR；如果=100，CMMBCR等同于MMBCR�？梢钥隙�，CMMBCR的性能很大程度上依賴于閾值的選取。但是由于CMMBCR增加的額外控制量影響了網絡性能，網絡生命周期的延長并不明顯。

4         基于能量有效的路由協議的比較與分析

基于能量有效的路由協議的宗旨在于最大化網絡生命周期。Ad hoc網絡會因為

某一關鍵節點首次耗盡電量而被分隔，導致各部分通信中斷。因此，基于能量

有效的路由協議既要全局考慮整個網絡的能耗問題，又要局部考慮單個節點的

有效存活時間。

相對于其他路由協議而言，MTPR只考慮總傳輸能量，而某些用于轉發數據包，

作為中繼的節點由于被路由次數過多，節點電量很快被耗盡，生存期就要短很

多。但是，由于MTPR傾向于最短路徑算法，它的平均路徑長度最小，這樣最小

跳數的度量標準保證了除關鍵節點之外的其他節點的生存期。MBCR的平均路由

長度小于MMBCR，同樣MBCR犧牲了單個節點的壽命換來較小的總傳輸能量，網絡生命周期小于MMBCR。

對于CMMBCR來說，它的主要性能影響因子在于閾值。當=0，沒有考慮網絡中節點的剩余電量，CMMBCR的性能與MTPR相同。隨著閾值的增大，CMMBCR意于保護剩余電量較少的節點，使它們不會提前耗盡剩余電量，越大，對單個

節點保護強度越大。但是，由于避免路由這些剩余電量較少的節點，必然選擇

較長路徑路由，中繼負載變大，網絡節點總平均壽命降低，犧牲了網絡性能。

所以，基于能量優化的路由協議要均衡考慮單個節點壽命、整個網絡生命周期兩個目標。如果網絡中的節點分布均勻，節點地位相同，閾值取值偏高有益于網絡優化。相反，如果少量節點提前失效并不影響網絡性能，取值偏小較為合適。具體情況應該根據實際網絡規模、節點移動頻率等因素具體分析。

5         結論

在這篇文章中，主要介紹了基于能量有效的Ad hoc無線網絡路由協議的性能特

點。由于網絡中各個節點都是電池供電，在發現路由的過程中就不得不考慮節

點的能量因素，以此來延長網絡生命周期。為達到此目的，有兩種策略，一是

以整個網絡中的大部分節點為側重，增加整個網絡的生命周期；二是犧牲網絡

性能，均衡使用網絡中的各個節點，避免個別節點的過度使用。兩種策略不能

并存，必須基于網絡實際狀況均衡考慮。未來，對于Ad hoc網絡，可能還需要

對基于安全和QOS的網絡協議作出更進一步的研究。

參考文獻 (References)