一種基于能量均衡的水聲通信網混合樹路由算法

譚盛彪　彭凌峰

摘 要：水聲通信網在軍事、能源、自然災害預防和處理等方面均具有巨大的應用潛力。針對當前水聲通信網按需路由算法存在網絡開銷大、能量不均衡的問題，提出了旨在改善網絡整體性能的HTREB算法。通過采用洪泛抑制與優先使用剩余能量均方差較大的節點進行路由查找，來減少控制分組的轉發，并均衡節點能量。基于Opnet軟件進行了仿真。結果表明，與現有按需路由算法相比，HTREB算法降低了網絡開銷8.08% ～ 29.32%、端到端平均能耗4.70% ～ 19.86%、平均端到端延時30.58% ～ 71.63%，延長了網絡生存期29.61%以上。因此，HTREB算法明顯改善了系統的整體性能。

關鍵詞：水聲通信網；路由算法；網絡開銷；能量均衡；鏈路權值

中圖分類號：TN929.3，TP393 文獻標識碼：A 文章編號：2095-2163（2015）01-

Abstract： UACN have great application potential in military， energy source， prevention and treatment of natural disasters. The current on-demand routing algorithms have some problems such as high network overhead and unbalanced energy consumption. To solve these problems， HTREB algorithm is suggested to improve the total performance of the networks. Based on the flooding suppression， nodes with more residual energy is preferred to find the routing， and then to reduce forwarding of controlled packets and to balance the energy consumption between nodes. The algorithm is simulated based on the software Opnet. Results show that 8.08% ～ 29.32% of network overhead， 4.70% ～ 19.86% of average end-to-end energy consumption， 30.58% ～ 71.63% of the average end-to-end delay are reduced， compared to the current on-demand routing algorithms. Furthermore， the network lifetime is prolonged by at least 29.61%. Therefore， the total performance of the system is evidently improved through our algorithm.

Key words： UACN； Hybrid-tree Routing Algorithm； Network Overhead； Energy Balance； Link Weight

0 引 言

水聲通信網（UACN）是在一定水下區域內，通過固定或移動傳感器節點獲取水下信息，并對節點進行聲學通信和組網，再以無線形式將信息傳送到岸上控制中心的智能網絡[1-2]。這是當前唯一可在水下進行遠程信息傳輸的通信形式，且在軍事、環境、能源、自然災害防治等方面均已表現出良好的應用潛力，因此受到了普遍重視與高度關注[3]。同時，又隨著物理層MIMO技術的日益成熟，近年來的水聲網絡也相應獲得了長足的進步和可觀的發展 [4-8]。

如今，UACN主要采用按需路由算法及其相應的改進算法。具體來說，文獻[9]提出了無線自組網按需距離矢量（AODV）路由算法。該算法使用目的序列號來防止路由死循環。但是，AODV通過采用洪泛尋路和HELLO消息來維護路由，卻造成了過多的控制開銷。同時，還有文獻[10]結合AODV算法和地理位置路由算法，提出了一種定向搜索（DSAODV）路由算法。該算法利用地理位置信息約束請求分組RREQ查找的范圍，使得RREQ只在最優的路徑方向上傳播，從而減少了網絡擁塞和路由開銷，并提高了網絡吞吐量。但是，DSAODV算法通過節點的位置信息和網絡節點疏密來設定和計算轉發角度，則需要水下定位技術的支持，因此限制了其應用。上述算法在廣播尋路分組RREQ的過程中均使用了洪泛操作，導致了冗余開銷。更重要的是，這些算法在建立路由時并未考慮節點能量的均衡，這就明顯影響了算法的效率和網絡的壽命。此外，文獻[11]則提出了一種基于均衡網絡業務的拓撲優化控制路由算法，綜合考慮了節點的剩余能量、網絡業務量和邊緣路徑條件，從而降低了節點的能量消耗，避免了網絡節點過早死亡，進一步提升了網絡吞吐量，而且也延長了網絡壽命。但是，該算法選擇剩余能量較多的節點來轉發數據，而未考慮網絡的平均剩余能量，因此上加重了某些節點的負載量，容易造成網絡擁塞。基于此，又有文獻[12]提出一種按需多播樹路由算法（MAODV），可以支持各種密切協作的應用業務，有效節省了帶寬資源，且對于每一個數據分組均有著更好的整體控制和傳輸能力。但是，MAODV對于頻繁變化的網絡拓撲結構，其分組投遞率將會下降；同時，節點通過全網廣播加入多播樹，也隨即增加了網絡開銷。綜合以上分析，本文擬提出旨在改善網絡整體性能的一種基于能量均衡的混合樹路由（HTREB）算法。通過建立混合樹網絡拓撲圖，采用洪泛抑制，綜合考慮平均剩余能量（優先使用剩余能量均方差較大的節點）來進行路由查找，由此而減少控制分組的轉發，并均衡節點能量，以最終獲得網絡整體性能的提升。

1 網絡模型

將水聲網絡抽象為數學模型：G=（V，L）有向圖，其中，V表示所有節點的集合，且V={S}∪Vm；S表示水面網關Sink節點，Vm表示所有水聲傳感節點的集合，；所有無線水聲對稱雙向傳輸鏈路的集合L={l1，l2，···，ln}，ln表示網絡中第n條鏈路；具體地，鏈路的代價可以是鏈路長度（跳數）、數據傳輸的時延花費等。

1.1 能量模型

本文能量消耗模型[14]為：當節點A向與之相距的節點B發送k bit的信息時，A消耗的能量由兩部分組成，分別是：發射電路損耗和功率放大損耗。即：

式中，表示節點發送k bit信息的發射電路損耗，表示功率放大損耗的距離閾值，則表示節點間的通信距離。若<，功率放大損耗以自由空間模型進行計算；若≥，則需依據多徑衰減模型相應計算。另外，和分別表示自由空間模型、多徑衰減模型功率放大器的能耗因子。而且，節點接收k bit信息所消耗能量為：

1.2 問題描述

網絡中信息的發送、轉發和接收均需要消耗節點的能量，因此，UACN網絡路由算法將遵循如下準則來進行能量優化：減少不必要的開銷，降低節點的能量消耗；均衡網絡的能量消耗，避免部分節點過早死亡。但是，現有的UACN網絡按需路由算法卻存在兩個問題，具體分析如下：

（1） 源節點廣播RREQ以及中間節點轉發無效RREQ，產生了大量冗余的RREQ信息，而這些冗余RREQ信息的收發增加了網絡開銷，進而增大了k值，就造成了節點的能耗加劇。

（2） 數據傳送選路時沒有考慮節點的剩余能量均方差因素。若當前節點沒有足夠的剩余能量，而仍承擔轉發數據的任務，就會因過度使用而造成電池提前耗盡，由此導致路徑的斷裂，影響網絡通信。

1.3 能量均衡的混合樹路由算法設計

針對UACN網絡現有的按需路由算法在尋路開銷和節點能耗等方面的不足，本文提出一種基于能量均衡的水聲通信網混合樹路由算法—HTREB。HTREB算法采用洪泛抑制的優化路由建立方式，減少部分控制分組的轉發；而且使用節點距離和剩余能量均方差作為選路標準，進而達到能耗均衡效果。

1.3.1 HTREB算法描述

HTREB算法包含鄰節點信息的收集與反饋，路由建立及數據轉發兩個階段。下面給出每一階段的具體實現過程。

（1） 鄰節點信息的收集與反饋階段

信息收集：節點定期向一跳范圍內的節點發送HELLO分組，接收到HELLO分組的鄰居節點獲知其可視鄰居區內節點的網絡地址等信息。

② 信息反饋：節點向其父節點及節點與鄰居節點深度最大的公共父節點反饋自己收集的可視鄰居信息。

（2） 路由建立階段

步驟1：當源節點有數據發送時，會首先查詢路由表中是否緩存了到目的節點的有效路由。如果是，則使用此路由發送數據分組。否則，將轉為步驟2，即源節點開始路由查找過程。

步驟2：源節點欲加入到多播組，則需查找多播路由表中是否可獲得父節點信息。如果獲得，則選擇下一跳單播RREQ到父節點，否則，即向鄰居節點及所在分支樹的鄰居節點的子節點多播RREQ請求分組。

步驟3：中間節點收到RREQ分組，執行以下過程：

① 判斷該RREQ的序列號是否大于自己路由項中的序列號或者RREQ的跳數是否小于TTL（Time To Live）閾值。如果是，執行②，否則刪除該RREQ分組。

② 若當前節點是源節點的鄰樹枝節點，則轉步驟2處理該RREQ；若當前節點是源節點的子節點，則判斷當前節點及其子節點是否有鄰樹枝節點。如果有，則向其多播RREQ，否則，刪除該請求；若當前節點是目的節點的父節點或子節點，通過計算判斷自己到目的節點的跳數加上RREQ中的TTL值是否小于TTL閾值。若是，就沿著樹路由路徑轉發該請求直到目的節點，若不是，將刪除該請求。

③ 若當前節點是源節點的父節點，但不是源節點和目的節點的公共父節點，也不是源節點和目的節點的最大深度公共父節點的子節點，則轉步驟2處理該請求；而若當前節點是源節點和目的節點的最大深度公共父節點的子節點，即需判斷當前節點是否有鄰樹枝節點或與源節點不同樹枝的子節點。若為有，則向其多播該請求，否則，就刪除該請求。

步驟4：源節點發送的RREQ請求到達目的節點時，如果RREQ歷經的跳數未超過TTL閾值，則單播路由回復RREP至源節點。中間節點收到RREP后，更新RREP中相應字段的值，而后沿RREQ傳播時建立的反向路徑發送RREP給鄰節點。源節點收到RREP后，存儲鏈路權值、跳數等信息，完成正向路徑的建立。

1.3.2 路由度量新指標—鏈路權值

在HTREB算法中，提出一種新的路由度量指標—鏈路權值（Link Weight），用于在節點收到不同的路由響應時，優先選擇距離更遠、剩余能量均方差更大的節點參與路徑建立。鏈路權值定義為：

式中，k1和k2是可變參數，k1+k2=1；di表示節點i與同樹枝源節點之間的距離，dj表示節點j與不同樹枝源節點之間的距離（0

2 仿真與分析

2.1仿真統計量

仿真統計量涉及網絡開銷、端到端平均能耗、網絡生存期、數據分組平均端到端延時和分組投遞率。其中，網絡開銷是網絡中所有節點發送和轉發的控制分組比特數和到達目的節點的數據分組比特數與目的節點成功接收的數據分組比特數的比值。端到端平均能耗將具體定義為網絡中單個節點能耗與所有節點平均能耗的均方差值。而且，網絡生存期即是網絡的運行時間。當死亡節點的數量大于等于網絡總節點數30%時，判定網絡運行截止。在此，數據分組平均端到端延時就是網絡中所有數據分組從源節點到達目的節點所消耗的時間與成功接收數據分組個數的比值。分組投遞率則指網絡中目的節點成功接收的數據分組數與源節點發送數據分組數的比值。

2.2 仿真參數設置

仿真實驗使用OPNET 14.5作為軟件平臺，主要仿真參數設置如表1所示。本文采用由一個網關節點和若干個信息采集節點組成的UACN網絡模型，網關節點在場景中心，傳感器節點隨機均勻分布在網關周圍。水下節點物理層采用文獻[13]設置的水聲信道模型，定義節點的能量都是有限且均為10 J初始能量；當節點剩余能量低于0.5 J時，判定節點死亡；當網絡中死亡節點數高于30%時，網絡生存期結束。

2.3 仿真結果及分析

圖1為網絡開銷比較，與AODV算法相比，HTREB算法能夠有效減少網絡開銷8.08%（50節點數）～ 29.32%（110節點數）；與MAODV算法相比，HTREB算法減少網絡開銷0.01%（50節點數）～ 20.76%（110節點數）。主要原因在于，

AODV算法節點存儲的路由信息較少，通常使用廣播RREQ的方式來進行路由查找以及周期地發送HELLO控制分組來維護路由，如此將導致網絡開銷過大；MAODV算法和HTREB算法通過發送RREQ路由請求或者查找鄰居表來建立數據傳輸的多播樹，避免了全網洪泛查詢，同時又減少了控制分組的轉發次數；且HTREB算法在尋路過程中利用路由跳數抑制RREQ的洪泛深度，通過相鄰樹枝的節點信息找到優化路徑，減少RREQ的轉發，從而進一步降低了網絡開銷，獲得了更高效率。

圖2為端到端平均能耗比較。與AODV和MAODV算法相比，HTREB算法降低端到端平均能耗分別為4.70%（50節點數）～ 19.86%（140節點數），2.50%（50節點數）～ 15.53%（140節點數），說明HTREB算法節點的能耗偏離網絡平均能耗的程度更小，能量消耗也更為均衡。主要原因在于，AODV算法中，部分中間節點轉發數據分組較多，節點能耗偏大，而某些通信量較小的節點，能量消耗將會偏小。因而導致網絡中節點能耗速率不均衡，端到端平均能耗較大；MAODV算法則通過建立的樹路由限制RREQ的洪泛，減少了網絡中冗余的RREQ轉發，但在尋路時因未考慮節點當前剩余能量，而過度使用剩余能量均方差較小的節點轉發數據分組，另有些剩余能量均方差較大的節點卻較少地轉發數據分組，由此導致網絡中節點能耗不均衡；相應地，HTREB算法即使用鏈路權值較小的節點作為下一跳，減輕了距離近的“熱區”節點的數據分組轉發任務，且使其能量消耗速率得到緩解，這就避免了剩余能量均方差較小的節點過早死亡，從而均衡了網絡節點能耗；同時，又采用了短跳代替長跳傳送分組，節點耗能減少，端到端平均能耗也隨即更小。

網絡生存期的仿真結果如圖3所示。圖3顯示，與AODV和MAODV算法相比，HTREB算法至少能夠延長網絡生存期分別為29.61%（20節點數），11.52%（20節點數）。這是因為在AODV算法中，數據分組經常沿著某一條路徑到達目的節點，造成部分節點承擔較大的負荷量，消耗能量更多，節點死亡就越快；而MAODV算法則廣播RREQ分組尋找最短路徑生成多播樹，并沿樹路徑發送數據分組。但是MAODV在建路時卻未考慮節點當前剩余能量，若剩余能量均方差小的節點繼續轉發數據，則會加速節點的死亡，甚至網絡拓撲的分裂；另外的HTREB算法源節點比較不同路徑的鏈路權值，選擇距離遠、剩余能量均方差較大的節點，即權值較小的路徑建立路由，因而延緩了負荷重的節點死亡，使網絡中節點能耗更佳均衡，藉此延長了網絡生存期。

數據分組平均端到端延時的仿真結果如圖4所示。在圖4中，與AODV算法相比，HTREB算法能夠有效降低分組平均端到端延時30.58%（110節點數）～ 71.63%（20節點數）；與MAODV算法相比，HTREB算法分組平均端到端延時降低1.47%（50節點數）～ 16.75%（20節點數）。主要原因在于，當一條鏈路斷裂，AODV算法需要重新發送RREQ查找路由，且數據分組總是沿著單播路由進行轉發、直至到達目的節點，當網絡通信業務增大時，容易引起信道沖突，并增加延時；MAODV算法則是通過RREQ分組尋路建立多播樹，限制了RREQ的轉發次數，因而利于數據分組在樹路由節點上的快速傳送，并使得時延獲得了有效降低；而HTREB算法卻借助相鄰樹枝節點信息進行RREQ尋路，縮短了路由建立時間。且HTREB優先選擇鏈路權值較小的節點進行分組傳送，如此既平均了業務流量，又避免了網絡擁塞，進而使得分組平均端到端時延進一步減少。

3 結束語

本文提出的HTREB路由算法，采用樹路由的單、多播代替廣播，限制RREQ分組的轉發，并利用鄰居節點信息建立路由，在一定程度上減少了網絡開銷；同時，綜合節點的距離和剩余能量均方差兩種因素形成鏈路權值，且將其引入路由參照標準，由此實現節點能量均衡。具體到理論分析及仿真結果即都表明，與AODV和MAODV算法相比較而言，HTREB算法在網絡開銷，端到端平均能耗，網絡生存期和平均端到端延時等方面的性能均已得到了有效改善，因而獲得了較為理想的現實研究效果。

參考文獻：

[1]AKYILDIZ I F， POMPILI D， MELODIA T. Challenges for efficient communication in underwater acoustic sensor networks[J]. ACM Sigbed Review， 2004， 1（2）： 3-8.

[2]OTHMAN A K， WAN Z A W A， ZEN H， et al. Performance evaluation for network set up and nodes discovery protocol in underwater grid topology networks[C]//Information and Telecommunication Technologies （APSITT）， Kuching， 2010.Piscataway： IEEE， 2010： 1-6.

[3]CUI J H， KONG J， GERLA M， et al. The challenges of building mobile underwater wireless networks for aquatic applications[J]. IEEE Network， 2006， 20（3）： 12-18.

[4]HOU J Y. Mobile Ad Hoc Network of simulation framework based on OPNET[C]//Computer， Mechatronics， Control and Electronic Engineering （CMCE）， Changchun， 2010. Piscataway： IEEE， 2010： 132-135.

[5]REHAN K， QIAO G. A survey of underwater acoustic communication and networking techniques[J]. Research Journal of Applied Sciences， 2013， 5（3）： 778-789.

[6]WANG P， ZHANG X. Energy-efficient relay selection for QoS provisioning in MIMO-based underwater acoustic cooperative wireless sensor networks[C]//Information Sciences and Systems （CISS）， Baltimore， 2013. Washington： IEEE， 2013： 1-6.

[7]REAL G， BEAUJEAN P P， BOUVET P J. MIMO underwater acoustic communications in ports and shallow waters at very high frequency[J]. Journal of Sensor and Actuator Networks， 2013， 2（4）， 700-716.

[8]LI S， WANG W， ZHANG J. Efficient deployment surface area for underwater wireless sensor networks[C]//Cloud Computing and Intelligent Systems （CCIS）， Hangzhou， 2012. Washington： IEEE， 2012： 1083-1086.

[9]GOMEZ C， CATALAN M， MANTECON X， et al. Evaluating performance of real ad-hoc networks using AODV with hello message mechanism for maintaining local connectivity[C]//Personal， Indoor and Mobile Radio Communications （PIMRC）， Berlin， 2005. Piscataway： IEEE， 2005： 1327-1331.

[10]劉旬， 李宇， 張春華， 等. 水聲通信網絡定向搜索 AODV 協議研究[J]. 應用聲學， 2010， 29（6）： 458-465.

[11]FU W， LI D， CHEN J， et al. Topology optimization control with balanced energy and load in underwater Acoustic Sensor Networks[J]. International Journal on Smart Sensing & Intelligent Systems， 2011， 4（1）： 138-159.

[12]SHURDI O， MIHO R， KAMO B， et al. Performance analysis of multicast routing protocols MAODV， ODMRP and ADMR for MANETs[C]//Network-Based Information Systems （NBIS）， Tirana， 2011. Piscataway： IEEE， 2011： 596-601.

[13]WANG C， FANG Y. Channel model simulation for underwater acoustic sensor networks using OPNET[C]//Communication Technology （ICCT）， Nanjing， 2010. Piscataway： IEEE， 2010： 141-144.

[14]LIU Z X， ZHENG Q C， XUE L， et al. Energy and node degree synthesized clustering algorithm for Wireless Sensor Networks[J]. Journal of Software， 2009， 20（sup）： 250-256.