無線傳感網(wǎng)絡(luò)中QoS約束多播路由算法＊

伍新華

（武漢理工大學(xué)計(jì)算機(jī)學(xué)院 武漢 430063）

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

1 網(wǎng)絡(luò)模型

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

2 EMRA

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

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

2.2 EMRA實(shí)現(xiàn)

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

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

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

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

步驟2 多播源節(jié)點(diǎn)s廣播Request請(qǐng)求報(bào)文，開始鏈路的查找.

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

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

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

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

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

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

3 EMRA正確性證明與復(fù)雜性分析

3.1 EMRA正確性證明

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

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

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

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

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

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

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

3.2 EMRA復(fù)雜性分析

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

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

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

4 仿真與結(jié)果討論

網(wǎng)絡(luò)仿真平臺(tái)為NS2，實(shí)驗(yàn)中的網(wǎng)絡(luò)圖由Waxman隨機(jī)圖模型生成，對(duì) EMRA，BIP［8］和MEMT算法進(jìn)行了仿真實(shí)驗(yàn)中.每次實(shí)驗(yàn)中，隨機(jī)選擇多播源節(jié)點(diǎn)和若干個(gè)請(qǐng)求點(diǎn)，每種類型的實(shí)驗(yàn)重復(fù)100次，取各次結(jié)果的平均值，以保證結(jié)果的可信度.

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

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

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

圖3 3種算法路由請(qǐng)求平均成功率

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

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

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

5 結(jié)束語

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

［1］李臘元，李春林.動(dòng)態(tài)QoS多播路由協(xié)議［J］.電子學(xué)報(bào)，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］.通信學(xué)報(bào)，2003，24（7）：30－36.

［7］許 毅，李臘元.一種支持多QoS約束的多播路由協(xié)議［J］，小型微型計(jì)算機(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.