基于能量約束的Ａｄ ｈｏｃ網絡多播路由協議研究

摘要:探討了移動Ad hoc網絡中基于能量約束的多播路由問題，并分析了幾種目前具有代表性的關于能量約束的多播路由算法，從適應環境#65380;可擴展性等多個方面對這些算法進行了分析比較，最后給出了基于能量約束的多播路由算法的下一步研究方向#65377;

關鍵詞:移動自組網;多播路由;能量;能量感知

中圖分類號:TP393.04文獻標志碼:A

文章編號:1001-3695(2007)04-0311-04

無線自組網(Ad hoc Networks)是由一組帶有無線通信收發裝置的移動終端節點組成的一個多跳#65380;臨時#65380;無中心網絡，可以在任何時候，任何地點快速構建起來的移動通信網絡，并且不需要現有基礎網絡設施的支持#65377;Ad hoc網絡在民用和軍事應用中具有非常廣泛的應用前景，如災難恢復#65380;搜索和救援以及自動化戰爭等#65377;該網絡已經成為計算機網絡領域一個新的研究熱點^[1]#65377;

在Ad hoc網絡中每一個節點既是通信終端又必須具有路由功能，所以能量約束問題成了Ad hoc無線網絡的一個非常重要的問題#65377;在一次通信過程中，不可能給電池充電或更換電池，如果部分節點的電池被耗盡，整個網絡將變成幾個分離的網絡，網絡的生命周期減少#65377;在設計Ad hoc路由協議時如何考慮能量約束，盡量延長網絡中每個節點的壽命是一個關鍵問題#65377;

目前，國內外研究人員針對基于能量約束的單播路由算法及廣播和多播的路由算法進行了一些研究#65377;在基于能量約束的多播路由算法方面的研究主要從構建最小能量消耗廣播/多播樹和平衡網絡節點能量消耗等方面著手，構建最小能量廣播/多播樹的算法可以分為基于圖論和基于幾何的算法#65377;在文獻[2]中將基于圖論的最小能量廣播/多播問題歸納為最小能量Steiner子圖(Minimum Energy Steiner Subgraph，MESS)問題#65380;最小能量廣播樹(Minimum Energy Broadcast Tree，MEBT)問題#65380;最小能量多播樹(Minimum Energy Multicast Tree，MEMT)問題和基于節點權重的Steiner樹(NodeWeighted Steiner Tree，NWST)等問題，并提出了一種對數逼近算法來求解具有對稱邊費用函數的MEMT和MEBT問題#65377;在文獻[3]中提出了一種求解具有非對稱邊費用函數的最小能量消耗廣播子圖問題的算法#65377;該算法復雜度為O(|D|ε)#65377;在文獻[4]中提出了基于節點權重的Steiner樹的對數逼近算法來解決MEBT問題#65377;

基于幾何的算法思想最早在文獻[5]中提到#65377;該算法思想認為網絡中所有節點處在歐幾里得平面內，在這種情況下，MEBT問題在文獻[6]中已被證明是一個NP完全問題，Wieselthier在文獻[7]中最早提出基于幾何的MEBT問題的算法#65377;基于幾何的算法多數是以圖的最小生成樹和最短路徑樹為基礎#65377;

基于最小能量消耗的廣播/多播算法沒有考慮節點剩余能量的問題，而片面追求整體能量消耗最小，會導致一些處于優勢地位的節點被過度使用造成節點能源枯竭，致使整個網絡的存活期變短#65377;一些研究者提出了基于平衡節點能量消耗的思想^[8，9]，通過平衡節點能量的消耗或減少能量低的節點參與路由的幾率來提高網絡的壽命#65377;

1能量模型

1.1無線通信模型

在一個Ad hoc網絡中，所有節點隨機地分布在一個給定的區域內#65377;假設每個節點配置一個全向天線，兩個移動節點間能否進行通信取決于節點的發射功率，典型的無線通信能量衰減模型^[2]是1/rα#65377;其中r是信號傳輸距離，α是一個依賴于無線通信環境的常量(典型的取值是1~6之間)，所以一個節點將信息發送到接收節點，需要滿足條件Ps/d(s，t)≥r#65377;其中Ps是節點的發射能量，d(s，t)是兩個通信節點間的距離，r是接收節點能夠檢測到信號的能量閾值，通常取值為1#65377;

根據前面的假設，移動節點采用全向天線，這種節點具有天生的“多播特性”，即所有處于一個發送節點通信范圍內的節點均可收到信號#65377;如圖1所示，節點S為源節點，D1#65380;D2為目的節點#65377;節點S發送信號到達D1所需能量為P1，到達D2所需能量為P3，節點D1發送信號到達D2所需能量為P2#65377;當S的發射能量取值為P=max{P1，P3}時，節點D1#65380;D2均可收到S的信號#65377;這種情況下，無線網絡總的能量消耗為P，這與有線網絡是不同的#65377;在有線網絡中，總的能量是兩條鏈路能量之和，這種特性在文獻[10]中被稱為“wireless multicast advantage”#65377;

根據圖1，源節點S與目的節點D2的通信可以有兩條路徑供選擇:

(1)節點S將信號發送到節點D1，然后由節點D1將信號發送到D2，總的能量消耗為P1+P2;

(2)節點S將信號直接發送到D2，其總的能量消耗為P3#65377;

顯然，若要選擇一條最小能量路由，需要比較P3與P1+P2的大小#65377;實際上，當α>1時存在(P1+P2)

1.2網絡模型

在研究基于能量約束的Ad hoc無線網絡多播路由問題時，多數學者將問題建立在一個靜態Ad hoc網絡的基礎上#65377;靜態Ad hoc網絡的模型可以描述為一個完全有向圖G=(V，E)#65377;其中|V|=n，代表網絡中所有節點的集合，每條邊有一個正的費用函數c:E→R+，代表兩個相鄰節點間通信所需的能量，E代表網絡中節點間鏈路(邊)的集合，矩陣R=(rij)∈{0，1}#65377;其中rij是節點vi到節點vj的路徑數#65377;

1.3最小能量多播樹問題

在研究基于能量約束的Ad hoc無線網絡多播路由問題時，很多學者都是圍繞最小能量多播樹問題的求解，如參考文獻[10~17]#65377;該問題可以描述為給定一個Ad hoc網絡和一個多播需求，要求尋找一個多播樹使其總能量消耗最小#65377;該問題的數學描述如下:

輸入G=(V，E)和一個多播需求(vo，D)

輸出T是(vo，D)的一個多播樹，且其總能量消耗最小

即MEMT問題是一個根節點vo和一組節點DV-{vo}，同時要求滿足當i = 0并且vj ∈ D時rij=1;否則rij=0#65377;

當D=V-{vo}時就是一個求最小能量廣播樹問題#65377;文獻[3，6]已證明MEBT問題是一個NP完全問題，因此MEBT可以采用一些啟發式算法加以解決#65377;

2基于能量約束的多播路由算法

在Ad hoc網絡的能量約束問題上，目前得到了國內外學者的關注，并提出了一些基于能量約束的多播路由算法#65377;它們可以劃分為三大類，即基于最小總能量的多播路由，基于能量均衡的多播路由和基于節點壽命感知的多播路由#65377;基于最小總能量的多播路由要求尋找總體最節能的路由，如果每個節點的發射功率相同，尋找最小總能量的路由就變成尋找最少跳數路由;基于能量均衡的多播路由要求在設計時應盡可能使各節點的能量消耗平衡;基于節點壽命感知的多播路由要求尋找路由時盡量選擇剩余能量最高的節點加入路由，同時避免使用能量已不足的節點加入路由#65377;對于基于能量約束的路由又可稱為功率感知路由#65377;下面首先介紹功率感知路由的度量指標#65377;

2.1功率感知路由的度量指標

1998年，Singh等人在文獻 [9]中提出了五種功率感知路由的度量指標:

(1) 最小化每個分組消耗的能量

假設某分組經過了節點n1，n2，…，nk，節點n1是源節點，nk是目的節點#65377;用T(ni，ni+1)表示分組從節點ni成功發送到節點ni+1消耗的能量，則分組在整條路由上消耗的能量是:e=∑k-1i=1T(ni，ni+1)#65377;

該度量指標的優化目標是:對于任意分組要求其總能量消耗最小#65377;其缺點是可能導致部分節點能量過度消耗，從而使這些節點過早死亡#65377;

(2)最大化到網絡出現分割的時間

在給定的網絡拓撲上，能夠找到一些關鍵節點，如果這些節點死亡，則引起網絡分割#65377;顯然，在兩個分區間的路由必定通過這些關鍵節點中的一個，因此路由算法必須在這些節點間分攤從而使網絡的壽命最大#65377;

該度量指標的優化目標是:轉發分組時考慮節點功率的分攤使得網絡出現分割的情況盡可能推遲#65377;

(3)最小化節點能量水平差異

使每個節點的剩余能量盡量保持相等#65377;

(4)最小化代價/分組

這個指標的目的是使網絡中所有節點的壽命最大化#65377;當使用這個度量指標時，應盡量使那些能量即將耗盡的節點不在路徑上#65377;

定義沿某一路徑轉發一分組的總代價為路徑上所有節點代價的總和，即假設某分組經過節點n1，n2，…，nk，節點n1是源節點，nk是目的節點，用f(xi)表示節點i的代價函數，xi可以代表兩個變量，既可以代表節點i的測量電壓又可以表示節點i迄今消耗的總能量，則分組在整條路由上的總代價是: c=∑k-1i=1f(xi)#65377;

該度量指標的優化目標是:對于任意分組都要求其總代價c 最小#65377;

顯然，如果f(xi)是一個單調增函數，則剩余能量小的節點不會被過度使用，從而延長了它們的壽命#65377;

(5)最小化最大的節點代價

用Ci(t)表示在t時刻通過節點i傳送一個分組的代價，用(t)表示一條路徑中Ci(t)的最大值，則該度量指標的優化目標函數為min (t)#65377;

該度量標準明顯延長了從開始到節點第一次發生死亡的時間#65377;

在這些指標中，指標最小化每個分組消耗的能量，從網絡層來說就是需要獲得最小總能量的路由#65377;該指標存在缺陷，指標最大化到網絡出現分割的時間和指標最小化節點能量水平差異較難應用;指標最小化代價/分組和指標最小化最大的節點代價應用較多#65377;

2.2基于最小總能量的多播路由

基于最小總能量的多播路由算法最為典型的是Wieselthier在文獻[7，10]中提出的MIP(Multicast Incremental Power)算法，該算法的基礎是BIP(Broadcast Incremental Power)算法#65377;在該算法的基礎上，很多研究人員進行了優化和改進，可參考文獻[8，12]#65377;

2.2.1BIP算法

BIP算法是一種與用來構造最小生成樹(Minimum Spanning Tree，MST)的Prim算法相類似的算法#65377;BIP算法的基本目標是構造一個最小能量廣播樹(MEBT)，以源節點為根節點，首先找到一個能量耗費最小的節點添加到樹中，然后BIP使用最小能量增量的原則每次往樹中添加一個節點，直到所有的節點全部加入到樹中，最后得到的樹即是一個最小能量廣播樹的近似解#65377;BIP算法與Prim算法的主要區別是Prim算法中輸入是鏈路的費用，在整個運算過程中該值不發生變化，而BIP算法在每一次添加節點后要重新計算費用#65377;假設節點i與節點j之間的連接費用為Pij，并且節點i目前的發射功率為P(i)，則連接到節點j的費用增量為Pij′=Pij-Pi#65377;Prim算法采用Pij作為輸入，而BIP采用Pij'作為輸入#65377;

2.2.2 MIP算法

首先，需要通過BIP算法得到一個廣播樹，然后通過剪枝(Prune)算法得到多播樹，即將不含有多播節點的樹枝從廣播樹中剪去，使用類似方法的還有文獻[14]中提到的算法#65377;在文獻[7]中，已指出MIP算法的復雜度是O(N3)#65377;MIP算法相對比較簡單，但在某些情況下，可能得不到最優解#65377;

2.3平衡網絡節點能量消耗的多播路由算法

2.3.1MST算法

最小總能量耗費已經成了評價一個Ad hoc網絡的重要指標#65377;但是從長遠來看，該評價指標具有負面影響，即會導致部分節點過度使用#65377;除了最小總能量耗費指標外，單個節點最大能量耗費(Maximum Energy Consumption)也是一個需要考慮的問題#65377;因為Ad hoc網絡通常是成片部置的，如果某個處于關鍵位置的節點能量枯竭，則網絡會被分割#65377;在文獻[8]中，提出了一種基于均衡能量耗費的MST算法#65377;該算法的基本思想是首先使用最小生成樹MST算法構建一個以源節點為根節點的廣播樹，然后，根據無線通信的多播特性，即一個節點同時可以與多個節點通信的特點，刪除一些不必要的通信，從而達到減少能量耗費的目的#65377;作者同時證明了使用該算法獲得的最小生成樹具有最小最長邊(Minimum Longest Edge，MLE)特性#65377;由于節點發射功率與距離相關，MST算法能夠使節點能量消耗相對均衡#65377;作者比較了BIP和MST算法，試驗表明MST算法在單一會話情況下，單個節點最大能量消耗只有BIP算法的58%#65377;在多會話情況下，單個節點最大能量消耗比BIP算法減少15%的能量消耗#65377;

2.4基于節點壽命感知的多播路由

該類路由以指標(4)和(5)為標準，基于節點壽命的單播路由研究較為廣泛，而廣播與多播研究較少#65377;文獻[18]提出了一種稱為 LMT(Lifetimeaware Multicast Tree)的多播路由算法#65377;該算法設計目標是設計一種不依賴全局信息僅需節點能量信息，能夠避免能量較少的節點參與路由的分布式能量感知多播路由算法#65377;LMT算法借鑒了單播路由算法PSR(Poweraware Source Routing)的費用函數:

其中ρi是節點i的常規發射功率;

Fi是電池的最大電量;

Ri(t)是在t時刻節點i的剩余能量;

αi(t)是一個正的影響因子#65377;

式(1)用于獲取具有最小能量消耗的路徑，式(2)用于平衡網絡中節點能量消耗的均衡#65377;顯然，當節點的剩余能量小時，費用函數的值越大，從而達到均衡能量消費的效果#65377;LMT算法利用式(1)和(2)計算最小費用多播樹，仿真試驗表明該算法能夠有效提高網絡壽命#65377;

2.5幾種基于能量約束的多播路由的比較

基于最小總能量多播樹的多播路由算法MIP具有算法簡單容易實現的優點#65377;但多數文獻中提到的算法采用的是貪婪算法，不一定總能得到最優解，同時會導致一些處在關鍵位置的節點能量被過度消耗，從而使這些節點能源枯竭#65377;均衡能量消費的多播路由算法MST能夠緩解部分節點被過度使用的問題，但其前提條件是節點的初始能量必須相等，且與MIP算法一樣需要提供全局信息，對于Ad hoc網絡來說，維護全局信息的代價較高#65377;基于節點壽命感知的多播路由算法LMT無須維護全局信息，且能夠均衡節點能量消耗，有效防止能量過小的節點參與路由，提高網絡的壽命，但其算法相對復雜#65377;上述三種協議的比較如表1所示#65377;

比較項MIPMSTLMT

適應環境靜態#65380;全向天線靜態#65380;全向天線動態，全向天線

是否分布式算法否否是

可擴展性一般一般較好

是否需要全網信息是是否

是否均衡能量消費否是是

通過對現有的基于能量約束的多播路由協議的研究和分析，筆者認為以下幾個方面是進一步研究的重點:

(1)基于能量和帶寬約束的多播路由協議

現有的基于能量約束的多播路由帶寬對于Ad hoc網絡來說也是一個非常有限的資源#65377;綜合考慮能量和帶寬約束，提高網絡通信質量的研究是非常有必要的#65377;

(2)具有綜合策略的多播路由

現有的基于能量的多播路由一般只針對某一種評價指標，如基于最小總能量的多播路由只考慮找到一個總能量最小的多播路由，基于壽命感知的多播路由重點考慮減少剩余能量小的節點參與路由的幾率等#65377;因此，綜合考慮不同能量指標可以作為下一步的研究方向#65377;

(3)跨層設計基于能量約束的多播路由協議

Ad hoc網絡能量約束問題在網絡各層次均有研究，如在MAC層可以采用功率控制機制實現節能，網絡層采用節能的路由協議等#65377;事實上，基于能量約束的多播路由協議的跨層設計方法已成為一個新的研究熱點#65377;

3結束語

本文在基于能量約束的網絡模型基礎上，描述了最小能量多播樹問題，根據文獻[9]提出的度量指標，介紹了幾種不同的基于能量約束的多播路由算法，最后給出了在Ad hoc網絡中研究基于能量約束多播路由應該注意的問題和今后的研究方向#65377;

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。