無線多跳網絡中吞吐量優化的多播路由算法研究

摘要：現有網絡中提高多播吞吐量的算法通常是以提高鏈路速率為目的，但單純地提高鏈路速率而忽略多播樹的度也限制了多播吞吐量的提高。主要研究了多跳無線網絡中多播吞吐量最優化問題，深入分析了無線多跳網絡特點，并在綜合考慮鏈路速率和多播樹度對多播吞吐量影響的基礎上，提出了應用于節點發射功率相同環境下的UUP_MTOA算法和應用于節點發射功率不同環境下的UNP_MTOA算法。通過仿真實驗與同類近似最優化算法相比，UUP_MTOA算法和UNP_MTOA算法能夠獲得更高的吞吐量，更適應于多跳無線網絡環境。

關鍵詞：多跳無線網絡；多播；吞吐量最優化

中圖分類號：TP393； TP301文獻標志碼：A

文章編號：1001-3695(2008)05-1513-04

0引言

無線多跳網絡(wireless multi－hop networks)是一種新型的無線網絡，它沒有中心接入節點或固定的基礎通信設施，在無線多跳網中，每個節點既是終端、接入設備，又是路由器。各個節點通過分布式控制算法相互協調完成網絡的通信功能。由于無須固定通信設施的支持，無線多跳網絡具有可快速部署和不依賴固定通信設施的特點，非常適合軍事戰術通信和民用應急通信，如野戰通信、緊急搜救、臨時會議等。

多播是一種實現從源節點同時向多個目標節點發送信息而僅在分叉的節點轉發數據包復本的通信形式。這一技術有效地解決了單（多）點發送、多點接收的通信問題，在多媒體會議、數據分發、分布式并行處理和分布式交互仿真等方面得到了廣泛的應用。采用多播通信方式能夠有效利用網絡帶寬，減少網絡擁塞。隨著高性能網絡技術的迅速發展，多播在各種網絡應用中發揮著越來越重要的作用，而關于多播的研究近幾年也成為國際上一個廣泛研究的熱點問題[1]。

本文介紹了多播路由協議國內外的研究現狀，給出了無線多跳網絡環境下的多播傳輸模型及改進算法的仿真和比較。

1國內外研究現狀

對于多播路由協議的設計與方法的研究，國內外許多學者都提出了不同多播路由協議和算法。但是，對無線多跳網絡而言，要實現多播通信，不僅要處理多播中相對獨立的組成員關系，還要處理由移動主機自身特點所引起的單向鏈路問題。特別是無線多跳網絡本身具有通信帶寬有限、能量受限等特征，更加限制了多播通信技術在無線多跳網絡中的應用。

目前關于無線多跳網絡多播路由協議的研究方向主要可分為以下幾類：

a)設計高效快速的多播路由協議，處理多跳無線網絡中通信帶寬受限、鏈路單向性等問題[2~4]。文獻[2]提出的協議CAMP (core－assisted mesh protocol)在網格中采用核的技術，從而減少了控制消息泛播傳輸的開銷。該協議能夠保證任何一個多播組成員節點都能在有限的時間內找到通往源節點的反向最短路徑。T. Ozaki等人[3]提出的Bandwidth－Efficient協議則采用一種新的路由創建過程(route seup process)來減少轉發節點的數量，并通過路由優化過程(route optimization process)來移除不必要的轉發節點和冗余低效的路由信息，最終依靠實施需求驅動的路由建立與修復過程(recovery process)來避免周期性地發送控制消息。而文獻[4]提出了一種基于節點分類策略的多播路由協議。該協議為發送者和接收者建立一個基于mesh結構數據轉發組，對無線網絡拓撲變化具有良好的適應性。

b）以減少單位數據傳輸的能量損耗為目的[5~7]。文獻[5]提出了一種分布式算法G－REMiT，通過優化多播共享樹中節點間的連接關系來使整個多播的總能耗趨向最低。文獻[6]提出EWMA算法和對應的分布式算法，通過精簡一棵最小權值的源組樹來提高網絡傳輸能量效率。而文獻[7]中所提出的D－REMiT路由算法則利用概率生成基于能量效率的共享樹的分布式算法，降低了多播總能耗，提高了共享樹的生存時間，具有較好的收斂性。

c)通過分析研究多播樹可獲得最大吞吐量[8]來改進多播路由協議。這種方法叫做多播吞吐量最優化問題MTOP(multicast throughput optimization problem)。文獻[8]從MAC層采用單播和廣播以及多播節點發射功率相同和不同幾個方面分析了多播吞吐量最優化問題，且提出了相應算法。對于MAC層采用單播的情況，如果節點發射功率相同，多播路由協議最大吞吐量可達到最優狀態的1/5；如果節點發射功率不同，多播路由協議吞吐量最大可達到最優狀態下的1/24。對以上兩種情況，文獻分別提出了5－近似算法和24－近似算法。這兩個算法能夠較好地提高多播的吞吐量，但它們都是集中式多播算法，不適應無線多跳網絡這樣的分布式環境。并且本文在設計算法的過程中只考慮到了鏈路速率對多播吞吐量的影響，而忽略了多播樹節點的度同樣也制約多播吞吐量的提高，從而不能最大限度地提高多播吞吐量。本文通過深入分析無線多跳網絡的特點，在綜合考慮了鏈路速率和多播樹的度對多播吞吐量影響的基礎上，針對不同傳播模型分別提出了兩種分布式路由算法：UUP_MTOA(unicast uniform power_multicast throughput optimization algorithm)和UNP_MTOA(unicast nun uniform power_multicast throughput optimization algorithm)。

2網絡模型分析

以下將給出多跳無線網絡環境下的多播傳輸模型及分析。

當網絡中MAC層采用單播傳輸時，用一個有向圖G=(V，E)表示一個多跳無線網絡。其中：V表示網絡中節點的集合；E表示網絡中所有鏈路的集合。在某時刻，如果節點u能夠直接與節點v通信，則用一條從節點u到v的有向邊表示。整個網絡是一個時間片同步的網絡，具有一個發送節點和一組接收節點，這些節點即多播節點。

3UUP_MTOA算法

3．1UUP_MTOA算法描述

UUP_MTOA算法是UUP_MTOP模式下的多播樹構建算法。文獻[8]分析了在UUP_MTOP模式下，多播吞吐量至少可達到最優吞吐量的1/5，并相應地提出了5－近似算法(5－Approximation)。算法簡單描述如下：從源節點出發，以節點間的距離作為圖中相應邊的代價，構建一棵最小生成樹作為多播樹。如果所有多播節點都已經在這個最小生成樹中，則算法停止。將樹T放到歐式平面考慮，每個鏈路的長度等于歐式距離。由文獻[11]得知，樹T的度最大為5。假設生成的多播樹T中代價最大的邊為emax，對應的鏈路速率為Rmin是樹中最小的鏈路速率。這樣，可以理論計算出整個多播樹的吞吐量至少為Rmin/5。由最小生成樹算法可知，在G=(V，E)找不到所有鏈路距離都小于d(emax)的樹，可以連通所有多播節點。同樣，對于最優多播樹，其鏈路速率ROPT≤Rmin，于是5－近似算法得到多播吞吐量至少是最優多播吞吐量的1/5。5－近似算法主要以提高多播樹鏈路速率為目的，而忽略了多播樹的度對多播吞吐量的影響。它還是一個集中式的多播樹構建算法，無法有效地在實際網絡中應用。

對于一棵多播樹，由于每個多播節點接收的數據是一樣的，整體吞吐量就是所有多播樹節點中吞吐量最小的那一個。對于某個節點v，吞吐量Th(v)＝mine∈N(v)f(e)R(e)＝Rmin/δ，Rmin＝mine∈N(v)R(e)即為與節點v相關的所有鏈路的最小速率。于是求最大吞吐量的問題便轉換為如何使每個多播樹節點的Th(v)較大。由Th(v)＝Rmin/δ可知，在多播樹的生成中，如果同時考慮每個節點的兩個參數Rmin和δ，則可以近似得到較大吞吐量。在多播樹生成過程中不僅是比較邊的代價，而是節點的度和代價最大的邊的比較，即讓每個節點的Rmin/δ盡可能大。根據以上的論述，可以設計出一個具有較大吞吐量的多播樹構建算法——UUP_MTOA算法。



3．2模擬結果

為了驗證算法的準確性和有效性，本文將UUP_MTOA算法與5－近似算法進行了仿真比較。假設100個節點隨機分布在1 600 m×1 600 m的平面上，多播節點在5~30個變化。UUP_MTOP模式下，每個節點發射功率相同，鏈路速率由節點間距離決定。且根據802.11b的特性，仿真設定四種不同的網絡傳輸速率，對應關系分別為11，5.5，2，1(Mbps)對應250，350，400，500(m)。實驗生成100個拓撲圖，即進行100次數據統計。

圖1給出了UUP_MTOP模式下不同算法構建多播樹的吞吐量的比較。UUP_MTOA算法得到的吞吐量明顯高于5－近似算法。其主要原因是UUP_MTOA算法綜合考慮了節點度對吞吐量的影響。從圖2中可以看出，UUP_MTOA算法構建的多播樹的度一般都是3，比5－近似算法要低，這是由于UUP_MTOA算法在構建多播樹的過程中，根據UUP因子加入新的多播樹節點，UUP因子一定程度上制約了多播樹度的增大。從圖3中還可以看出，UUP_MTOA算法構建的多播樹的最遠跳數比5－近似算法稍大。

4UNP_MTOA算法

4．1UNP_MTOA算法描述

UNP_MTOA算法由UUP_MTOA算法改進得到，適用于節點發射功率不同的環境模式。設節點最大發射功率和最小發射功率的比率不大于16，即Pmax/Pmin≤16，參數β＝4。這種網絡環境比較符合實際的多跳無線網絡，如在cisco350構建的網絡下。

文獻[7]在UNP_MTOP模式下提出24－近似算法(24－Approximation)。算法分兩部分完成：a）找到一個能連通所有多播節點的最小鏈路速率Rc。對于一個固定的Rc，由表達式Rc＝W log2[1+Pmin /(N0W dc4)]可確定相應的dc。在圖G=(V，E)中去掉距離大于dc的鏈路和相應的節點，構成圖Gc=(Vc，Ec)。如果Vc包含所有多播節點，則算法a)完成；否則，將速率大于Rc的鏈路和相應節點添加到Gc中，構成圖Gc′。如果圖Gc′沒有包含所有多播節點，則調整Rc，重新執行a）。b)在圖Gc的每個連通部分中執行5－近似算法，可得到一個森林Ti。在圖Gc′中，將森林Ti組成樹T。由算法可知，最優多播樹鏈路速率ROPT≤Rc；否則多播樹不能連通所有多播節點。圖中Gc′最多有19個連通部分，即19棵樹[11]。而每個樹Ti的度不大于5。故上述算法得到的多播吞吐量可達到最優多播吞吐量的1/24。24－近似算法解決了功率不同情況下多播樹的構成問題，但是算法比較復雜，且不適合分布式網絡環境。

在UNP_MTOP模式下，鏈路速率由發送節點的發射功率和鏈路長度兩個參數決定，這使得相同兩個節點間傳輸數據，傳輸方向不一樣，鏈路速率也不一樣。UUP_MTOA算法根據UUP因子生成多播樹，而UUP因子根據鏈路長度和節點的度決定，所以UUP_MTOA算法不能應用于UNP_MTOP模式。多播的數據傳輸都是從某個源節點到其他多播節點，在生成多播樹的過程中，計算鏈路速率可以只考慮臨近多播源節點的發射功率。因此在UUP_MTOA算法上作適當改進，我們得到適用于節點發射功率不同環境下的UNP_MTOA算法。

UNP_MTOA算法根據UNP(unicast nun uniform power)因子生成多播樹。UNP因子由多播樹中的節點計算得出。假設某多播樹上的節點為N，其鄰居節點（不包含已加入到多播樹的節點）為W1，W2，Wi，…，Wn。節點Wi的UNP因子=R(S， Wi)/(δ+1)。其中：R(S，Wi)＝W log2{1+PS/[N0Wdβ]}；d表示節點S與Wi間距離；PS表示源節點S的發射功率；δ表示源節點S的度。一個UNP因子對應一個尚未加入多播樹的節點，表示如果此節點加入多播樹將對多播樹中與其相連多播數節點吞吐量影響的數值。UNP_MTOA算法與UUP_MTOA算法基本一致，只是在選擇節點的過程中用UNP因子替換UUP因子，算法的具體描述就此省略。

4．2仿真及算法分析

在UNP_MTOP模式下，由于每個節點發射功率不同，鏈路速率由節點間距離和節點發射功率同時決定。節點的發射功率隨機分配60~300 mW的數值，符合Pmax/Pmin≤16；帶寬W=2.4 GHz，參數β＝4。圖4為UNP－MTOP模式下吞吐量比較，圖5為UNP－MTOP模式下多播樹度比較。

仿真生成10個拓撲圖，即進行10次數據統計。由圖4可以看出，UNP_MTOA算法得到的吞吐量明顯高于24－近似算法。這是由于UNP_MTOA算法構建多播樹過程中綜合考慮了多播樹的度對多播樹吞吐量的影響。如圖5所示，UNP_MTOA算法構建的多播樹的度一般為3，比24－近似算法低，這是由于UNP_MTOA算法構建多播樹的過程中根據UNP因子加入新的多播樹節點，UNP因子一定程度上制約了多播樹度的增大。

5結束語

本文主要研究了無線多跳網絡中多播吞吐量最優化問題，深入分析了無線多跳網絡特點， 并在綜合考慮鏈路速率和多播樹度對多播吞吐量影響的基礎上，針對網絡不同節點發射功率相同和不同的情況，分別提出了UUP_MTOA算法和UNP_MTOA算法。從仿真結果可看出，與同類算法相比較，UUP_MTOA算法和UNP_MTOA算法所構建的多播樹吞吐量更高。并且與其他算法不同，UUP_MTOA算法和UNP_MTOA算法都是分布式算法，更加適用于多跳無線網絡這樣的分布式網絡環境。

參考文獻：

［1］鄭相全.無線自組網技術實用教程[M].北京：清華大學出版社，2004.

[2]GARCIA－LUNA－ACEVES J J，MADRUGA E L.A multicast routing protocol for Ad hoc networks[C]//Proc of IEEE INFOCOM.1999：784－792.

[3]OZAKI T，KIM H B，SUDA T.Bandwidth－Efficient multicast routing for multihop， Ad hoc wireless networks[C]//Proc of IEEE INFOCOM.2001:1181－1191.

[4]DENG Xia， SUN Li－min， WANG Jian－xin，et al.An Ad hoc multicast protocol based on node classification[J].Journal of Central South University，2006，13(2):190－195.

[5]WANG B， GUPTA S K S.G－REMiT.an algorithm for building energy efficient multicast trees in wireless Ad hoc networks[C]//Proc of IEEE Int’l Sym Network Comp and Applications.Los Alamitos， CA:IEEE Comput Soc， 2003：265-272.

[6]CAGALJ M， HUBAUX J P， ENZ C.Minimum－energy broadcast in all wireless networks: NP－completeness and distribution issues[C]//Proc of ACM MobiCom.Atlanta，GA:ACM Press，2002:172－182.

[7]羅玉宏，王建新，陳松喬.一種基于共享樹的能量優化組播路由算法[J].通信學報，2006，27(6): 1-9.

[8]BHATIA R，LE Li.Characterizing achievable multicast rates in multi－hop wireless networks[C]//Proc of the 6th ACM International Symposium on Mobile.New York:ACM Press，2005:133－144.

[9]RAPPAPORT T S.Wireless communication principle and practice[M].New Jersey:Prentice Hall，1996.

[10]COVER T M，THOMAS J A.Elements of information theory[M].[S.l.]:Wiley，1991.

[11]MONMA C L，PATERSON M，SURI S，et al.Computing euclidean maximum spanning trees[J].Algorithmica，1990，5(3):407-419.

[12]GASPAR Z，TARNAI T.Upper bound of density for packing of equal circles in special domains in the plane[J]. Per Pol Civil Eng，2000，44(1):13-32.

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