改進的基于能量的多播路由算法

李 帥， 蔡 明

(江南大學 物聯網工程學院，江蘇 無錫214122)

區別于傳統有線通信網絡，無線自組織網絡是一種由大量移動節點組成，具有流動性、自組織、分布式等特點的無線網絡，又稱Ad hoc 網絡［1］。Ad hoc 網絡由于布設靈活、簡單操作，不受地理位置、環境因素等的限制，被廣泛應用于農林、工程、生態等領域。

Ad hoc 網絡中，常用的通信方式有兩種:多播和單播。多播是指一對多或多對多形式的通信，如單個源節點向多個目的節點傳送數據分組。單播是Ad hoc 網絡中另一種通信方式，實現一對一形式的通信。多播與單播通信方式相比，數據傳送效率高，能夠使網絡中的資源得到充分有效的利用［2］。

網絡的生命周期可以理解為從網絡投入運行到廢棄使用的時間。一般地，當網絡中節點的能量耗盡或者小于某個閾值時，不足以滿足信息處理和正常工作的要求，即認為此節點死亡。當網絡中死亡節點的數量占到網絡中節點總數的某個限定比例時，將認為該網絡不再能正常發揮作用，該網絡也會被廢棄不用。因此，為延長網絡的生命周期，使得網絡能夠更長時間地發揮其作用，降低網絡的節點死亡率是一個很有意義的研究方向。

1 相關工作

基于地理位置信息的無線多播路由協議中，GEographic Multicast(GEM［3］)是很典型的一種，其設計靈感源于Euclidean Steiner Tree(EST［4］，歐式Steiner 樹)模型。GEM 路由協議中，鄰居節點之間可以直接通信。GEM 協議的中心工作是挑選合適的下一轉發節點和傳輸數據，直到將數據傳送給所有目的節點。與同類路由協議相比，GEM 協議中節點不需要維護全局或局部路由信息，需要知道節點的位置信息完成路由過程。然而，在其路由算法設計過程中，沒有考慮節點的剩余能量。因此，可以改進GEM 路由算法，對所選的節點增加能量約束，以此降低節點死亡率，從而延長應用網絡的使用壽命。

文獻［5-7］介紹了Ad hoc 網絡中常見的基于能量的路由協議。在文獻［5］中，提出了一個能量消耗模型。在該模型中，節點狀態分為4 種，分別為發送狀態、接收狀態、空閑狀態和休眠狀態。節點處于休眠狀態時消耗的能量可以忽略不計，能量消耗主要集中在節點收發狀態和空閑狀態。文獻［6］提出的GEAR 中，采用能量感知的啟發式路由策略選擇地理位置相近的鄰居節點來轉發分組，并通過發送HELLO 報文獲取鄰居節點的位置信息和剩余能量值。文獻［7］介紹了一種無線傳感網中的層次路由協議，協議中根據節點與基站的距離將網絡節點劃分為不同層次，低層節點數據匯聚后由高層剩余能量較大的節點傳送給基站。

基于上述研究，為延長網絡的使用壽命，改造GEM 路由算法，對節點的剩余能量加以約束，文中提出一種改進的多播路由算法。算法中系統采用了類似文獻［5］中的能量消耗模型，以解決節點在信息傳輸過程中的能量消耗問題。

2 改進后的多播路由算法EGEM

2.1 系統模型和標記

將網絡抽象為一個無向圖G = (V，E)，其中V是節點的集合，E 是節點間有效鏈路的集合。有效鏈路指此鏈路為雙工類型的鏈路，雙工鏈路指構成鏈路的兩節點可以同時進行雙向信息傳輸，任一節點既是信息發送方又是信息接收方。假設網絡中所有節點具有相似的特征，如節點無線覆蓋半徑相等，記為R。

將網絡中第i 個節點記為vi，同時vi代表節點在網絡中的地理位置標識。此網絡模型中，節點的位置信息用二維坐標對表示，如vi= (xi，yi)表示節點vi的地理位置坐標。d(vi，vj)表示節點vi和vj之間的歐式距離，在二維直角坐標系中，兩點間的歐式距離即兩點間的幾何距離計算公式如下:

記v 到目的節點集合V(D)的累積距離［4］為cd(v，V(D))，其中V(D)是V 的子集。累積距離計算公式如下:

給定節點v 和w，集合V(D)，V(D)是V 的一個子集，定義節點w 相對于v 到集合V(D)的累積距離為cp(v，w，V(D))，即v 到集合V(D)的累積距離與w 到集合V(D)累積距離的差值，計算公式如下:

用公式3 比較候選節點的優劣程度。在cd(v，V(D))值一定的情況下，cp(v，w，V(D))值越大，cd(w，V(D))的值越小。根據cd(w，V(D))的含義可知，節點w 到目的節點集合V(D)累積距離越小，節點w 越接近目的節點群，這樣節點v 通過節點w 到達目的節點群的可能性就越大，w 作為下一中繼節點的可能性就越大。

一般地，網絡中目的節點的分布不總是集中的，經常會出現孤立節點或節點群的情形。為解決這個問題，在選擇下一中繼節點的過程中，引入分支的概念。為實現分支，在選擇下一中繼節點時，考慮了所有可能的節點對并挑選出最佳的一對，與不引入分支情況下選擇的節點作比較。在引入分支的情況下，衡量節點作為候選節點的優劣程度時，公式3 不能很好地滿足這種需求。

為滿足此需求，引入參數ap(v，w，V(D))，用來比較引入分支時節點作為下一中繼節點的優劣程度，計算公式如下:

其中| V(D)| 表示集合V(D)包含節點的個數。這樣，在使用公式4 的方法比較優劣程度值時，孤立的目的節點或目的節點群在下一中繼節點選擇的過程中所占的權值越大，這樣使得在靠近源點處分支的可能性更大，一定程度上減少了到孤立目的節點或目的節點群的跳數，從而減少了開銷。

2.2 選擇轉發方向

假設當前轉發節點為vi，負責將數據分組轉發到目的節點集合V(D)。假設節點vi知道V(D)中目的節點的地理位置信息，對于節點位置信息的更新和維護策略參閱文獻［8］。

要解決的重要問題之一是如何挑選合適的下一轉發節點。在選擇過程中，還要考慮是否引入分支的問題。在選擇轉發方向時，每一個當前中繼節點均要考慮是否在本節點處引入分支。這一步很重要，因為在合適的位置分支將減少當前轉發節點到目的節點或節點群的中間節點的數目，從而減少開銷。另外，基于EST 的理論研究還表明，引入分支的數目最多不超過2 個。下面分步詳細介紹其選擇流程。

1)假設vj為節點vi無線覆蓋范圍內的節點，即節點vi的鄰居節點。由于vi的鄰居節點能直接接收來自節點vi的所有消息，因此首先要從V(D)中移除所有在其無線傳輸范圍內的目的節點。

2)不分支情形下，求取使得ap(vi，vθ，V(D))取得最大值的轉發方向角θ0。節點無線覆蓋半徑為R，則以節點vi為圓心、R 為半徑的圓周上任一點坐標可表示為

選取最佳轉發方向時，選取使得ap(vi，vθ，V(D))取最大值對應的θ 值，求解公式如下:

其中θ 為節點vi，vθ連線與x 軸所成夾角。為計算方便，選取θ = μ* Δθ，μ = 0，1，2，…，μmax。Δθ 稱為搜索粒度，計算表達式為Δθ = ［2π/μmax］。可以看出，Δθ 越大，θ 值取值個數就越少，很大程度上能減少計算負擔。

3)分支情況下，計算ap(vi，vθ，V(D))最大值之和與對應的方向對(θ1，θ2)。ap(vi，vθ，V(D))值的計算過程與2)相似，不同之處有3 點。首先，在計算前，要將目的節點集合V(D)劃分。其中，V(D1)表示相對于vi節點、分布靠近θ1的目的節點集合。同樣的，V(D2)表示相對于vi節點、分布靠近θ2的目的節點集合。V(D1)和V(D2)存在如下關系:V(D1)= V(D)－V(D2)。其次，在選擇轉發方向對(θ1，θ2)時，從［0，2π］* ［0，2π］區間內選取，為減少計算負擔，令θ2=θ1+2π/3，這樣只需比較μmax個方向對。最后，在兩轉發方向計算出相應ap(vi，vθ，V(D))值后，求和，記為sap(vi，vθ，V(D))。

4)比較ap(vi，vθ，V(D))和sap(vi，vθ，V(D))的大小并判定在當前中繼節點vi處是否分支。若ap(vi，vθ，V(D))大于等于sap(vi，vθ，V(D))，不分支，否則分支。

2.3 選擇下一轉發節點

確定轉發方向后，當前轉發節點在其無線覆蓋范圍內廣播消息，并選出最佳下一轉發節點。此階段，節點vi產生一個控制消息Request_Forward，并廣播給其無線覆蓋范圍內的所有鄰居節點。這個控制消息包含轉發方向值、vi及目的節點對應的標識和位置信息、分支標識FLAG。其中，若不引入分支，置FLAG = 0，否則，置FLAG = 1。

記t0為vi發送Request_Forward 消息的時刻，此刻起，vi節點的鄰居節點開始下一中繼節點的競爭。假設vj是無線傳輸范圍中任一節點，即vi的鄰居節點。當vj接收到Request_Forward 消息后，會將此消息存儲在本地內存中。首先，vj會讀取控制消息中FLAG 的值，并根據FLAG 的不同值執行不同的操作。但無論FLAG 取值如何，都需引入一個參數，用來衡量vj沿轉發方向θ 作為下一中繼節點的好壞程度，此參數標記為μ(vj，vi，θ*)，表示vj，vi連線在某一方向θ*上的投影值，如圖1 所示。計算公式如下:

其中，d(vj，vi)是節點vi和vj之間的歐式距離，θ 為vi，vj兩節點連線與x 軸所成夾角(見圖1)。θ 計算公式如下:

圖1 中繼節點選擇Fig.1 Graph of the relay node selection

從式7 中可以看出，θ 與轉發方向角θ*偏離程度越小，μ(vj，vi，θ*)值越大，節點vj距離目的集合就相對越近，節點vi沿θ 方向轉發數據分組的概率越大。

以FLAG = 0 為例說明vj執行的操作。FLAG =0，令θ*= θ0，計算μ(vj，vi，θ0)。然后vj會依據一個指數分布函數產生一個隨機值ζj，這個函數以μ(vj，vi，θ0)為參數，且μ(vj，vi，θ0)值越大，ζj值越小。vj在(t0+ζj)時刻發送一個Reply_Forward 消息，內容包括分支標識FLAG、轉發方向值θ0、轉發方向對應的μ(vj，vi，θ0)，vj的標識、位置和節點的剩余能量e。很 明 顯，μ(vj，vi，θ0) 值 越 大，vj就 越 早 發 送Reply_Forward 消息。針對FLAG = 1，要計算μ(vj，vi，θ1)和μ(vj，vi，θ2)兩個值并比較，vj會根據μ(vj，vi，θ*)值較大者產生隨機值ζj。

在時刻t0發送Request_Forward 消息后，節點vi會等待一段時間，這段時間用來接收來自其鄰居節點發回的Reply_Forward 消息。vi節點在發送Request_Forward 消息后，也會產生一條記錄，稱為最佳記錄，同時產生一條備用記錄，記錄包含下述信息:分支標識FLAG;轉發方向值θ0，θ1，θ2;沿對應轉發方向的射影μ0，μ1，μ2;取相應射影節點的標識v0，v1，v2;剩余能量值e。

vi收到一個Reply_Forward 消息后，會將所需的信息插入到此記錄的相應位置。插入時注意，若FLAG = 0，θ1，θ2，μ1，μ2，v1，v2置為空，對應地，若FLAG = 1，θ0，μ0，v0也置空。需要說明一下，節點vi產生的最佳記錄用來存放最優解，備用記錄用來存放次優解。最優解是指μ 值較大，同時剩余能量值e滿足能量約束e_need 的解;次優解是指滿足約束條件，但μ 值較小或其他情況。節點vi收到Reply_Forward 信息的過程中，不斷更新最佳記錄和備用記錄中的信息。

在TEND時，vi停止接收Reply_Forward 信息。此時節點vi會檢查最佳記錄中是否有節點信息，如果沒有則到備用記錄中查詢節點信息，并將此節點作為下一中繼節點。

篩選出下一中繼節點后，當前中繼節點vi會在其無線傳輸范圍內以廣播的方式發送一個CT 消息結束選擇過程。該CT 消息包括下一中繼節點的標識和位置信息、數據分組信息。節點vj接收到此CT消息后，讀取此消息內容并判斷是否被選為下一中繼節點。如果是，vj將接收包含在CT 消息中的數據分組，轉發該數據分組的副本并開始新一輪的競爭選擇，否則vj忽略此數據分組。當vi監聽到下一中繼節點轉發數據分組后，會將最佳記錄和備用記錄刪除。

3 實 驗

實驗以eclipse 軟件為工具，以50* 100 m2的矩形作為實驗區域，節點均勻散落在此區域中，每個節點的無線傳輸半徑R = 10 m。源節點和目的節點的位置信息用二維坐標對表示，實驗過程中預設目的節點數量10 個。節點密度定義為節點數量與仿真場景面積的比值，記為σ，分別取σ1= 0.03 m－2，σ2=0.04 m－2。節點能量初始化為10 J，能量閾值為2 J，發送狀態下能量消耗1.4 J，接收和空閑狀態下能量消耗均為0.8 J［9］。實驗中，考察改進前后算法在不同實驗次數下節點的死亡率和平均跳數等性能參數。

定義節點死亡率為網絡中能量耗盡的節點數目與節點總數的比值，平均跳數為路由選擇過程中經歷的總跳數與實驗次數的比值。通常情況下，網絡中節點死亡率越高，不能發揮正常作用的節點數目越多，對應網絡的使用壽命越短，節點死亡率超過某個限值網絡將會被廢棄使用。表1，2 中分別表示σ1= 0.03 m－2，σ2= 0.04 m－2時不同實驗次數下節點的死亡率及其他性能參數。

表1 σ1 下性能參數結果Tab.1 Results of performance parameters under σ1

表2 σ2 下性能參數結果Tab.2 Results of performance parameters under σ2

從表1，2 中可以看出，隨著實驗次數的增加，兩者的節點死亡率基本呈增加趨勢;相同實驗次數下EGEM 的節點死亡率明顯小于GEM 對應的節點死亡率，但平均跳數保持不變或增加。原因在于，在選擇下一轉發節點過程中，GEM 總是選擇μ(vj，vi，θ*)值最大的節點作為下一轉發節點，保證了跳數最少，但是未考慮節點的剩余能量，在多次傳輸之后，節點能量耗盡導致節點死亡。而EGEM 在選擇下一轉發節點時，總是選擇剩余能量較多者進行轉發，在相同實驗次數下對應的節點死亡率較小。但由于EGEM 挑選的節點對應的μ(vj，vi，θ*)值并不一定保證最大，導致路由過程中平均跳數不變或增加。

4 結 語

文中研究了Ad Hoc 網絡中幾種常見的基于能量的無線路由協議，提出了一種改進的提供能量約束的多播路由算法。與原算法相比，新算法中引入了能量消耗模型。新算法對節點剩余能量加以約束，選擇剩余能量較多的節點進行數據傳輸，一定程度上降低了節點死亡率，延長了網絡的使用壽命。由于在數據傳送過程中節點需要知道目的節點的地理位置信息，會導致消息頭部開銷增加，下一步將集中在降低開銷上。

［1］閆麗麗，彭代淵，高悅翔. Ad hoc 網絡中認證路由協議的改進及其安全性分析［J］. 電子科技大學學報，2011，40(4):578-581.YAN Lili，PENG Daiyuan，GAO Yuexiang.An improved routing protocol in ad hoc networks with safety analysis［J］. Journal of University of Electronic Science and Technology，2011，40(4):578-581.(in Chinese)

［2］李群.Ad hoc 網絡多播路由協議研究進展分析［J］.計算機技術與發展，2014，24(2):187-188.LI Qun.Research and analysis of multicast routing protocol in ad hoc networks［J］. Computer Technology and Development，2014，24(2):187-188.(in Chinese)

［3］Galluccio L，Morabito G，Palazzo S. GEographic Multicast for dense wireless networks:protocol and performance analysis［J］.IEEE/ACM，2012，4(21):1332-1346.

［4］Herring M.The euclidean steiner tree problem［R］.Granville:Denison University，2004.

［5］陳祖爵，歐陽燁龍.一種層次蜂窩結構的負載均衡GAF 算法［J］.計算機工程，2012，38(3):105-118.CHEN Zujue，OUYANG Hualong. The load balancing GAF algorithm based on hierarchical cellular structure［J］. Computer Engineer，2012，38(3):105-118.(in Chinese)

［6］魏斌，王維先.基于模糊區域寬松距離的改進GEAR 傳感網絡均衡算法［J］.計算機科學，2012，39(9):71-73.WEI Bin，WANG Weixian. The improved GEAR sensor network balancing algorithm based on relaxed distance in fuzzy region［J］.Computer Science，2012，39(9):71-73.(in Chinese)

［7］康一梅，趙磊，胡江.基于能量感知的無線傳感器網絡層次型路由協議［J］.計算機工程與設計，2011，32(12):3948-3956.KANG Yimei，ZHAO Lei，HU Jiang.An hierarchical routing protocol in sensor networks based on energy awareness［J］.Computer Engineer and Design，2011，32(12):3948-3956.(in Chinese)

［8］林彥汝，周繼鵬.基于地理位置的Ad Hoc 路由協議［J］.計算機應用，2011，31(1):226-228.LIN Yanru，ZHOU Jipeng.The routing protocol based on geographic information in ad hoc networks［J］.Computer Application，2011，31(1):226-228.(in Chinese)

［9］葉海濱，張華熊，馬漢杰.基于NS2 的能量模型的研究［J］.工業控制計算機，2013，26(1):77-79.YE Haibin，ZHANG Huaxiong，MA Hanjie.The survery of energy model bases on NS2［J］.Industrial Control Computer，2013，26(1):77-79.(in Chinese)