伍新華

（武漢理工大學計算機學院 武漢 430063）

QoS多播路由技術的目標是找到一種算法或策略，在給定的網(wǎng)絡和多播需求的情況下，尋求一種鏈路連接方式，使網(wǎng)絡資源能夠得到有效利用［1］.文獻［2］中將基于圖論的最小能量廣播／多播問題歸納為最小能量廣播樹和最小能量多播樹問題，文獻［3］中提出最大剩余能量的QoS多播路由算法，文獻［4］提出了基于平衡節(jié)點能量消耗的思想，通過平衡節(jié)點能量的消耗或減少能量低的節(jié)點參與路由的幾率來提高網(wǎng)絡的壽命.本文討論了延時、帶寬及節(jié)點剩余能量的問題，提出了一種多QoS約束的能量有效多播路由算法（EMRA）.

1 網(wǎng)絡模型

定義2 如果p（s，t）滿足（d（s，＊）＋d（k，t）≤ Dmax）∧ （b（i，j）≥ Bmin）∧ （R（P（s，t））＝min［r1，…，rf］，則滿足此約束的路徑為能量消費最小路徑；滿足帶寬和時延約束的最小能量路徑多播樹問題是一個NP完全問題［5］，可以采用一些啟發(fā)式算法加以解決.

2 EMRA

2.1 EMRA節(jié)點選擇策略

多播節(jié)點的加入操作涉及到加入點的選擇問題，一般有隨機點策略、最小時延點和能量消耗最小三種選擇策略.隨機點策略就是從多播子樹中任選一個路由節(jié)點作為多播終點的加入點.最小時延點策略是s到d的最小時延路由路徑與多播子樹的交點作為多播終點d的加入點.最小能量點策略則是選擇從s到d的能量消耗最小路由路徑與多播子樹的交點作為多播終點d的加入點.仿真實驗結果表明，最小能量消耗策略費用精度最好，所以，EMRA選擇最小能量點策略.

2.2 EMRA實現(xiàn)

EMRA基本思想是利用可行鏈路來構建滿足帶寬和延時約束的最小能量消耗的多播路由樹，因此利用文獻［6］中的BIP最小生成樹的Prim算法的基本思想來構成.以源節(jié)點s為根節(jié)點，首先找到一個能量耗費最小的節(jié)點添加到樹中，然后BIP使用最小能量增量的原則每次往樹中添加一個節(jié)點，直到所有的節(jié)點全部加入到樹中，最后得到的樹即是一個最小能量多播樹的解.

EMRA首先選擇多播信源構成初始多播樹，然后根據(jù)多播成員的連接請求或退出請求，依照加入和退出操作規(guī)則，動態(tài)地建立或切斷連接，多播樹的形成過程就是多播成員的動態(tài)加入和退出過程.在EMRA的形成過程中，路由器或節(jié)點需在其路由表保存一些特定的信息.為了描述方便，定義EMRA的主要消息如下：Request（加入請求消息），節(jié)點t向多播信源s發(fā)送請求加入多播；Accept（加入確認消息），源節(jié)點s向請求授權點t發(fā)送確認加入請求；Delete（鏈路刪除消息），節(jié)點t沿多播樹向父節(jié)點w逆向發(fā)送請求刪除鏈路（w，t）；Establish（建立狀態(tài)），路由資源在該節(jié)點已分配完畢.

EMRA是以分布的方式來建立多播樹的，每個節(jié)點以同樣的算法，四種不同的節(jié)點（源節(jié)點、樹節(jié)點、中間節(jié)點和目標節(jié)點）在協(xié)議中以不同的方式交換信息，每個節(jié)點的操作由到達的控制消息所觸發(fā)（Request，Accept，Delete，Establish）.鏈路e的帶寬、延時和能量分別為B（e），D（e），R（e）；而r＿table為局部路由表；對于任何節(jié)點v，r＿table［v］.b為在最短路徑上的有用的帶寬；r＿table［v］.d為在最短路徑上的有用的延時；r＿table［v］.r為在最短路徑上的有用的能量.EMRA步驟如下.

步驟1 初始化，刪除所有帶寬大小于Bmin約束的鏈路.

步驟2 多播源節(jié)點s廣播Request請求報文，開始鏈路的查找.

制造任務分解的主要目的是為了獲得一定粒度的子制造任務，實現(xiàn)生產(chǎn)過程的均衡和制造服務的合理匹配。制造任務分解的基本過程如下：

步驟3 當某節(jié)點i接收到Request后，如果已經(jīng)接收并處理過該Request，則向其相鄰節(jié)點轉發(fā)；否則，如果delay（p（u，v））＞Dmax，則指針poi［u］指向節(jié)點u的父節(jié)點.

步驟4 計算能量最小路徑 如路徑滿足能量最小定義2，則poi［y］＝x；如x的狀態(tài)為Establish，則計算d（P（s，x））；如delay（P（s，x））≤Dmax，則 While poi［u］NIL，發(fā)出加入請求消息Request.

步驟5 如果某節(jié)點k接收到節(jié)點j發(fā)送的Accept消息，如果鏈路e（j，k）狀態(tài)為Establish.

步驟6 檢查多播目的節(jié)點是否全部加入多播樹T（s，M），如果沒有，則源節(jié)點s繼續(xù)廣播Request報文，轉步驟2，否則執(zhí)行步驟7.

步驟7 執(zhí)行剪枝算法，利用后序遍歷算法以多播源節(jié)點s為根節(jié)點遍歷以上生成的多播樹，并且在訪問某葉節(jié)點時，如果該葉子節(jié)點是一個非多播節(jié)點，則刪除該節(jié)點，直到多播樹中所有葉子節(jié)點均為多播目的節(jié)點.

3 EMRA正確性證明與復雜性分析

3.1 EMRA正確性證明

定理1 EMRA所構造的多播樹T（s，M）定能滿足帶寬、延時、最小能量約束.

證明 （1）EMRA是根據(jù)定義2來計算能量最小路徑；（2）在EMRA中，當且僅當d（P（s，v））≤Dmax和b（P（s，v））≥Bmin），才發(fā)出加入請求消息，所以，對于?P（s，v）?T（s，M），有P（s，v）定能滿足延時和帶寬約束.

結合證明（1）和（2）知，EMRA所構造的多播樹T（s，M）定能滿足帶寬、延時和能量約束，證畢.

定理2 EMRA搜索的最小能量路徑是無環(huán)的.

證明 首先，增加第一個目標節(jié)點到樹上的過程中沒有產(chǎn)生環(huán)路.設當前要增加到樹中的節(jié)點為vd∈V，則增加vd到樹上（當前只有一個多播源節(jié)點s）的過程即為尋找路徑P（vs，vd）使之能量增加最小的過程.在EMRA的執(zhí)行過程中，選擇滿足定義1的方式構造，同時每條最小能量路徑都是以源節(jié)點s為起始節(jié)點加入的.在r＿table路由表中只存在一個輸入和一個或多個輸出接口，所搜索到的路徑形成的是一種樹結構.在新節(jié)點加入后，組內(nèi)各節(jié)點間仍構成一棵多播樹，故TsM 必是無環(huán)的樹型結構.其次，假設已構造部分沒有環(huán)路，新增加節(jié)點的過程產(chǎn)生環(huán)路［6］.

采用反證法，如圖1所示，使用實線表示已經(jīng)構造的多播樹，虛線表示即將加入到多播樹上的部分.如果P（v8，v10）是EMRA選擇路徑存在的環(huán)路，則必有P（vt，v10）包含多播樹上的某個節(jié)點，不妨設為v9；由于P（v8，v10）是v10與樹上所有節(jié)點S＝｛v1，v2，v3，v4，v5，v6，v7，v8，…｝中所有路徑中滿足帶寬和延時約束的最小能量路徑，則有路徑P（v8，v10）的能量代價必小于 P（v9，v10）；而路徑P（v8，v10）包含節(jié)點v9，則路徑P（v8，v10）的能量就等于路徑P（v8，v9）的能量加上路徑P（v9，v10）的能量之和，顯然兩者相互矛盾，原假設不能成立.即新增節(jié)點過程中沒有產(chǎn)生環(huán)路，所以EMRA在多播樹的產(chǎn)生過程中是無環(huán)路的.

圖1 EMRA的無環(huán)路徑

3.2 EMRA復雜性分析

定理3 EMRA的消息的復雜度為O（｜M｜｜E｜），計算復雜度為O（｜n｜2）［7］.

證明 EMRA的復雜度可根據(jù)生成多播樹的計算復雜度和所需的報文數(shù)來進行分析；前者主要涉及到摸索路徑和多播生成樹所需要的開銷，后者主要根據(jù)生成多播樹的報文交換功能所需要的計算開銷.在EMRA中，路徑計算一般在端點進行，根據(jù)QoS需要計算新節(jié)點加入多播樹的路徑.而EMRA的計算復雜度由加入請求、加入和退出等操作部分組成.加入請求操作消息的復雜度最多為O（｜E｜），M 個多播節(jié)點加入操作消息的復雜度最多為O（｜M｜｜E｜）；退出操作的退出請求消息的復雜度最多為O（｜E｜），刪除請求和刪除操作消息的復雜度都為O（1），故EMRA消息的復雜度由加入操作消息的復雜度決定，即為O（｜M｜｜E｜）.

同時在EMRA中，每個節(jié)點實際表示一個路由器，算法在每個路由器上進行.算法將每個目的節(jié)點加入到樹中所需的控制信息算作一次信息傳遞，而不考慮中間節(jié)點的信息傳遞.如果沒有回路產(chǎn)生的情況下，就有連接n個目標需要從源節(jié)點或分支節(jié)點發(fā)送n個Request加入請求消息到目標節(jié)點，至多n－1次信息從n－1個目的節(jié)點發(fā)出.EMRA在最壞情況下需要2n＋k 次信息傳遞，這時最壞情況為每次在加入一個目的節(jié)點時，k＝（n－2）＋（n－3）＋…＋1＝（n－2）×（n－3）／2，因此，EMRA共需要O（n2）次信息傳遞，如果每次信息傳遞用一個單位時間，這時EMRA的收斂時間就為O（n2）.

4 仿真與結果討論

網(wǎng)絡仿真平臺為NS2，實驗中的網(wǎng)絡圖由Waxman隨機圖模型生成，對 EMRA，BIP［8］和MEMT算法進行了仿真實驗中.每次實驗中，隨機選擇多播源節(jié)點和若干個請求點，每種類型的實驗重復100次，取各次結果的平均值，以保證結果的可信度.

圖2表示多播樹的能量消耗隨多播節(jié)點數(shù)增加的變化曲線.在該仿真實驗中網(wǎng)絡節(jié)點數(shù)被設為500，時延為300.當多播節(jié)點數(shù)增加時，對EMRA，BIP和MEMT算法所產(chǎn)生的能量消耗也增加，但EMRA增加程度較小，相同多播組EMRA的能量消耗較小.由于控制報文長度增大，其能耗也會相應增加.因此，在網(wǎng)絡規(guī)模較小的情景下路由控制報文帶來的額外能耗抵消了能控機制節(jié)省的能量，然而隨著網(wǎng)絡節(jié)點數(shù)目的增多，EMRA其能耗將大大低于BIP和MEMT算法.

圖2 3種算法的多播樹能量消耗

圖3給出了EMRA，BIP和MEMT算法路由請求平均成功率的隨時延約束變化時的曲線.從圖中可以看出，EMRA的路由請求平均成功率高于BIP和MEMT算法.

圖3 3種算法路由請求平均成功率

圖4顯示了在時延限制Δ＝1008060時，網(wǎng)絡節(jié)點數(shù)在［50，500］間變化時，EMRA的平均消息數(shù).可以看出，隨著節(jié)點數(shù)的增加，EMRA的平均消息數(shù)增加很慢，不會產(chǎn)生消息風暴，這表明EMRA可以在大型網(wǎng)絡中應用.

圖4 EMRA的平均消息數(shù)變化

通過對EMRA，BIP和MEMT三種算法的仿真結果進行比較發(fā)現(xiàn)，EMRA在性能上較優(yōu)越于其它兩種算法，能很好地滿足多QoS約束的無線傳感網(wǎng)絡的實時應用需要.

5 結束語

EMRA在實驗中反映無線網(wǎng)絡真實特性的帶寬、剩余能量和延時等重要因素，同時通過可行鏈路的定義使生成的多播鏈路滿足QoS約束，這樣有效地減少了生成多播樹的開銷.仿真實驗結果表明EMRA為多QoS約束的無線傳感網(wǎng)絡多播路由技術提供了一種新的有效途徑，能適用于各種網(wǎng)絡規(guī)模和群組規(guī)模，可擴展性良好，具有較好的應用前景.

［1］李臘元，李春林.動態(tài)QoS多播路由協(xié)議［J］.電子學報，2003，9（9）：1345－1352.

［2］Ioannis C，Panagiotisk C.Energy－efficient wireless network design：lecture notes in computer science（ISAAC03），LNCS 2906［C］／／Berlin：Springer－Verlag，2003：585－594.

［3］Younism A.An energy－aware Qos routing protocol for wireless sensor networks［C］／／Proceedings of the 23rd International Conference on Distributed Computer Systems Workshops Los Alamitos USA IEEEE Computer Society，2003：710－715.

［4］Cheng M X，Sun Jianhua，Min Mank，et al.Energyefficient broadcast and multicast routing in Ad Hoc wireless networks［C］／／Proceedings of the 2003 IEEE International，2003：87－94.

［5］Mario Z，Hubaux J P，Christian E.Minimum－energy broadcast in all－wireless networks：NP－completeness and distribution issues：proceedings of the 8th annual international conference on mobile computing and networking（MOBICOM）［C］／／Atlanta，Georgia：ACM Press，2002：172－182.

［6］孔令山，丁 煒.一種多約束QoS多播路由算法［J］.通信學報，2003，24（7）：30－36.

［7］許 毅，李臘元.一種支持多QoS約束的多播路由協(xié)議［J］，小型微型計算機系統(tǒng)，2005，26（12）：2065－2068.

［8］Kim Y，Li S.Timescale of interest in traffic measurement for link bandwidth allocation design［C］／／Proceedings of IEEE INFOCOM：1996.