無線傳感網絡中QoS約束多播路由算法＊

伍新華

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

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

1 網絡模型

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

2 EMRA

2.1 EMRA節點選擇策略

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

2.2 EMRA實現

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

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

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

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

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

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

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

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

步驟5 如果某節點k接收到節點j發送的Accept消息，如果鏈路e（j，k）狀態為Establish.

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

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

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

3.1 EMRA正確性證明

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

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

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

定理2 EMRA搜索的最小能量路徑是無環的.

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

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

圖1 EMRA的無環路徑

3.2 EMRA復雜性分析

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

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

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

4 仿真與結果討論

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

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

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

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

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

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

圖4 EMRA的平均消息數變化

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

5 結束語

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

［1］李臘元，李春林.動態QoS多播路由協議［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約束的多播路由協議［J］，小型微型計算機系統，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.