楊藝清，陳志剛

(中南大學(xué) 信息科學(xué)與工程學(xué)院， 湖南 長(zhǎng)沙　410083)

?

認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)中資源節(jié)約的最小信道沖突值組播路由算法*

楊藝清，陳志剛

(中南大學(xué) 信息科學(xué)與工程學(xué)院， 湖南 長(zhǎng)沙410083)

認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)中滿足服務(wù)質(zhì)量約束的多目標(biāo)優(yōu)化組播路由問題比單目標(biāo)優(yōu)化組播問題更加復(fù)雜，為了快速求解認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)中滿足服務(wù)質(zhì)量約束的、以最小化資源消耗與最小化信道沖突值為目標(biāo)的多目標(biāo)優(yōu)化組播路由問題，提出一種基于粒子群優(yōu)化算法的問題求解框架，包括問題描述、粒子編碼與粒子初始化、適應(yīng)度函數(shù)、粒子飛行、粒子變異、粒子消環(huán)。粒子由表示節(jié)點(diǎn)之間連接關(guān)系的帶權(quán)鄰接矩陣表示，重新定義了用于粒子飛行的3種運(yùn)算規(guī)則以及粒子飛行運(yùn)算和粒子變異運(yùn)算。仿真結(jié)果表明提出的算法能達(dá)到預(yù)定目標(biāo)，資源消耗較低且能獲得較低的信道沖突值。

認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)；組播；頻譜分配；粒子群優(yōu)化

認(rèn)知無(wú)線電(Cognitive Radio, CR)技術(shù)可以很好地緩解無(wú)線通信系統(tǒng)中的頻譜缺乏問題，而無(wú)線Mesh網(wǎng)絡(luò)(Wireless Mesh Networks，WMNs)將成為下一代寬帶接入網(wǎng)絡(luò)，故將CR技術(shù)應(yīng)用于WMNs中解決頻譜缺乏問題具有潛在的優(yōu)勢(shì)[1-2]。在認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)(Cognitive Wireless Mesh Networks, CWMNs)中，每一個(gè)CR-Mesh節(jié)點(diǎn)通過頻譜感知技術(shù)能夠智能地接入主用戶(Primary Users, PUs)未使用的頻譜資源[3]。

本文以資源節(jié)約和最小化總的信道沖突值為目標(biāo)，研究CWMNs中滿足服務(wù)質(zhì)量(Quality of Service, QoS)約束的多目標(biāo)優(yōu)化組播路由與頻譜(信道)分配問題。其中資源節(jié)約表示最小化新到組播業(yè)務(wù)對(duì)應(yīng)組播樹的傳輸節(jié)點(diǎn)數(shù)，最小化總的信道沖突值即為最小化新到組播業(yè)務(wù)對(duì)已接受組播業(yè)務(wù)的沖突。同時(shí)，考慮已接受組播業(yè)務(wù)的權(quán)重，具有較高權(quán)重的已接受組播業(yè)務(wù)相比低權(quán)重的已接受組播業(yè)務(wù)受到的信道沖突更低。本文的QoS約束指組播業(yè)務(wù)的帶寬約束。

學(xué)界對(duì)WMNs中的組播路由問題的研究已經(jīng)有一段時(shí)間，取得了較多的研究成果[4-5]，但是這些研究成果不能直接應(yīng)用于CWMNs中[6]。同時(shí)，針對(duì)CWMNs中的組播路由問題，也取得了一些研究成果[7-19]。

Almasaeid等[8]研究了CWMNs中的組播路由問題，針對(duì)CWMNs中組播目的節(jié)點(diǎn)具有可用信道的異構(gòu)性，因而組播源節(jié)點(diǎn)成功將數(shù)據(jù)傳輸?shù)剿心康墓?jié)點(diǎn)的總時(shí)間較長(zhǎng)的問題，以減少組播總時(shí)間為目標(biāo)，提出了一種基于組播目的協(xié)作的組播路由算法。在文獻(xiàn)[9]中，Almasaeid等針對(duì)由于主用戶節(jié)點(diǎn)使用授權(quán)信道的差異，CR-Mesh路由器節(jié)點(diǎn)必須進(jìn)行信道切換，從而導(dǎo)致延遲增加的問題，以降低端到端延遲為目標(biāo)，提出了一種CWMNs中基于動(dòng)態(tài)規(guī)劃的組播路由算法。鄺祝芳等在文獻(xiàn)[10-11]中提出了CWMNs中2種組播路由算法。文獻(xiàn)[10]針對(duì)CWMNs中無(wú)線組播業(yè)務(wù)數(shù)據(jù)流保持時(shí)間較長(zhǎng)且比較固定，需事先構(gòu)造其組播樹的情形，以最小化組播樹的信道沖突總數(shù)為目標(biāo)，提出了基于智能計(jì)算的GA-MRSA和SA-MRSA算法。文獻(xiàn)[11]針對(duì)CR-Mesh節(jié)點(diǎn)可用信道差異導(dǎo)致CR-Mesh節(jié)點(diǎn)、CR-Mesh鏈路負(fù)載不均衡的問題，以節(jié)點(diǎn)負(fù)載均衡為目標(biāo)，提出了一種CWMNs中負(fù)載均衡的組播路由與頻譜分配算法LMRS2A。Xie等[12]以最小化組播樹消耗的總帶寬為目標(biāo)，研究了認(rèn)知無(wú)線自組織網(wǎng)絡(luò)(Cognitive Radio Ad Hoc Networks, CRAHNs)中滿足QoS約束的組播路由問題，針對(duì)該問題提出了兩種解決方法。第一種方法：首先基于最小生成樹算法構(gòu)造組播路由樹，然后提出一個(gè)時(shí)間槽分配算法給組播路由樹中的無(wú)線鏈路分配時(shí)間槽。第二種方法：將上述兩個(gè)階段合并，同時(shí)考慮組播樹構(gòu)造與時(shí)間槽分配。Pan等[13]研究了認(rèn)知無(wú)線多跳網(wǎng)絡(luò)中，以最大化吞吐量為目標(biāo)的組播路由問題，同時(shí)還考慮頻譜的可用性和共享的公平性。Naeem等[14]研究了認(rèn)知無(wú)線網(wǎng)絡(luò)中多組播組考慮最大最小公平性的聯(lián)合功率、子載波分配以及中繼分配的問題。Shu等[15]以最大化網(wǎng)絡(luò)吞吐量為目標(biāo)，研究了認(rèn)知無(wú)線網(wǎng)絡(luò)中的組播路由與頻譜分配問題。Gao等[16]研究了CRAHNs中的組播路由問題，以最小化需要的網(wǎng)絡(luò)資源為目標(biāo)，提出了一種多項(xiàng)式時(shí)間算法求解混合整數(shù)線性規(guī)劃問題。Hu等[17]研究了認(rèn)知無(wú)線網(wǎng)絡(luò)中的可擴(kuò)展流媒體組播問題，其以優(yōu)化網(wǎng)絡(luò)的流媒體質(zhì)量、達(dá)到各組播用戶之間的公平性和對(duì)PU產(chǎn)生的干擾低于某一個(gè)閾值為目標(biāo)。Jie等[18]針對(duì)認(rèn)知無(wú)線網(wǎng)絡(luò)中的組播路由問題，提出了一種多速率多層混合圖模型，目標(biāo)是實(shí)現(xiàn)最小化組播樹最差情況下的端到端延遲、最大化組播樹的速率以及最小化組播樹的傳輸鏈路。Tan等[19]在考慮主用戶活動(dòng)的情況下，研究了認(rèn)知無(wú)線網(wǎng)絡(luò)中基于正交頻分復(fù)用技術(shù)(Orthogonal Frequency Division Multiplexing, OFDM)的組播路由問題，組播成員中的各次用戶基于其感知的可用信道，被分為多個(gè)簇，目標(biāo)是最大化聚合數(shù)據(jù)率。

1　網(wǎng)絡(luò)模型及問題描述

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

簡(jiǎn)單無(wú)向圖G=(V,E)建模認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)，其中V表示CR-Mesh節(jié)點(diǎn)的集合，E表示鏈接2個(gè)能相互通信的CR-Mesh節(jié)點(diǎn)的無(wú)線鏈路的集合。每個(gè)節(jié)點(diǎn)vi∈V都有一個(gè)可用信道集合Ki以及一個(gè)認(rèn)知射頻接口數(shù)RFi。每個(gè)節(jié)點(diǎn)均存在一個(gè)通信距離TR和一個(gè)干擾距離IR。一般情況下滿足3TR>IR>TR，本文假設(shè)IR=2×TR。假設(shè)存在一個(gè)公共控制通道(Common Control Channel, CCC)用于各CR-Mesh節(jié)點(diǎn)之間傳遞控制信息。

d(vi,vj)表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的物理距離。N(vi)={vj|vj∈V,d(vi,vj)

設(shè)X={x(vi,vj)}n×n，x(vi,vj)=k表示無(wú)線鏈路(vi,vj)分配的信道是k，x(vi,vj)=0表示無(wú)線鏈路(vi,vj)沒有分配任何信道，規(guī)定只給每條無(wú)線鏈路分配一個(gè)信道，或者不分配任何信道。Bk表示信道k的帶寬，單位是Mbps，由于不同的信道通常具有不同的帶寬，因此，對(duì)于不同的信道k和k′，有Bk≠Bk′。

無(wú)線鏈路(u1,v1)和(u2,v2)相互沖突必須滿足以下條件：①d(u1,u2)

1.2問題描述

研究的問題是以資源節(jié)約和最小化組播業(yè)務(wù)信道沖突值為目標(biāo)的滿足無(wú)線業(yè)務(wù)QoS約束的多目標(biāo)優(yōu)化組播路由問題。對(duì)新到組播業(yè)務(wù)本身，希望構(gòu)造資源節(jié)約組播樹，其目的是希望預(yù)留更多的資源以便能接受更多的無(wú)線組播業(yè)務(wù)；對(duì)已接受組播業(yè)務(wù)，希望受到較少的信道沖突。

本文的第一個(gè)目標(biāo)是資源節(jié)約，資源節(jié)約指的是最小化組播樹的傳輸節(jié)點(diǎn)。

定義1(傳輸節(jié)點(diǎn))在組播樹Tp中，節(jié)點(diǎn)vi存在到其鄰居節(jié)點(diǎn)分配信道k的數(shù)據(jù)通道(邏輯鏈路)，則稱信道k為傳輸節(jié)點(diǎn)。

V(Tp,k)表示在組播樹Tp中工作在信道k上的傳輸節(jié)點(diǎn)集合。

定義2組播樹Tp的花費(fèi)Cost(Tp)，指在組播樹Tp中所有可用信道上的傳輸節(jié)點(diǎn)數(shù)之和，即如式(1)所示：

(1)

本文的第二個(gè)目標(biāo)是最小化信道沖突值，I(Tp)表示總的信道沖突值，其定義如式(2)所示：無(wú)線組播業(yè)務(wù)γp的組播樹Tp與所有已接受組播業(yè)務(wù)的組播樹的無(wú)線信道沖突值的和。

(2)

式中，?p是除組播樹Tp之外的所有組播樹的集合，Tq是已接受無(wú)線組播業(yè)務(wù)γq對(duì)應(yīng)的組播樹，H(Tp,Tq)表示組播樹Tp與Tq的無(wú)線信道沖突值，如式(3)所示:

(3)

式中，fq(k,u,v)表示組播樹Tp中的無(wú)線鏈路(u,v)分配信道k時(shí)與組播樹Tq的信道沖突值，其定義如式(4)所示:

(4)式中，w(k,a,b)表示組播樹Tq中無(wú)線鏈路(a,b)分配信道k的信道沖突值。 用組播樹Tq對(duì)應(yīng)組播業(yè)務(wù)γq的權(quán)重wq表示無(wú)線鏈路(a,b)的信道沖突值，目的是為了讓較高權(quán)重的組播業(yè)務(wù)相比較低權(quán)重的組播業(yè)務(wù)獲得更高吞吐量，受到盡可能少的沖突。 即無(wú)線鏈路的信道沖突值如式(5)所示:

(5)

本文求解問題的形式描述如式(6)～(11)所示：

(6)

(7)

(8)

(9)

ρ(u)

(10)

x(u,v)∈{0}∪K，?(u,v)∈Tp

(11)

2　多目標(biāo)優(yōu)化的粒子群優(yōu)化算法

為了求解前文提出的多目標(biāo)優(yōu)化問題，本節(jié)提出一個(gè)針對(duì)CWMNs中滿足QoS約束的多目標(biāo)優(yōu)化組播路由與頻譜分配問題求解框架，包括問題描述、粒子編碼與粒子初始化、適應(yīng)度函數(shù)、粒子飛行、粒子變異和粒子消環(huán)。

2.1粒子群優(yōu)化算法簡(jiǎn)介

粒子群優(yōu)化 (Particle Swarm Optimization, PSO) 算法是一種群體智能算法，由Kennedy和Eberhart于1995年提出[20]。它是模擬自然界中飛鳥集群活動(dòng)的規(guī)律，在狀態(tài)空間中搜索問題的最優(yōu)解。在PSO算法中，每一個(gè)個(gè)體被稱為一個(gè)粒子，它代表問題中的一個(gè)可能解。每一個(gè)粒子根據(jù)自我經(jīng)驗(yàn)以及向其他粒子的學(xué)習(xí)來(lái)調(diào)整飛行軌跡，改善搜索效率，促進(jìn)整個(gè)群體向最優(yōu)解收斂。每一個(gè)粒子具有一個(gè)位置向量和一個(gè)速度向量，算法在搜索過程中記錄下每一個(gè)粒子搜索到的最優(yōu)位置以及整個(gè)粒子群中搜索到的最優(yōu)位置。每次迭代過程中，粒子通過跟蹤個(gè)體最優(yōu)位置和群體最優(yōu)位置來(lái)更新自己。基本的PSO算法[21]還無(wú)法直接用于求解本文研究的滿足QoS約束的多目標(biāo)優(yōu)化組播路由與頻譜分配問題。因此，需重新定義粒子編碼和粒子飛行，并且定義粒子變異和粒子消環(huán)操作。

2.2粒子編碼

(12)

對(duì)于無(wú)線組播業(yè)務(wù)γp=(A,{G,H,F,I},4,20)，圖1所示為Tp的組播樹，圖2所示為組播樹Tp的粒子編碼表示。

圖1　組播樹TpFig.1　Multicast tree Tp

圖2組播樹Tp的粒子編碼

Fig.2Particle encode of multicast treeTp

2.3粒子初始化

本文提出粒子初始化算法InitPSO，基本步驟如下：

步驟1：初始化種群集合Q為空集，初始化組播樹Tp為空集，初始化粒子Xi中的所有元素為0，將源節(jié)點(diǎn)Sp添加到Tp中。

步驟2：在目的節(jié)點(diǎn)集合Dp中選擇一個(gè)目的節(jié)點(diǎn)dj，從Dp中刪除dj，dj添加到分支Branch(dj)，dj作為當(dāng)前節(jié)點(diǎn)v。

步驟3：構(gòu)造當(dāng)前節(jié)點(diǎn)v的未添加到Branch(dj)的鄰居節(jié)點(diǎn)集合，在該集合中隨機(jī)選擇一個(gè)節(jié)點(diǎn)u，將節(jié)點(diǎn)u添加到Branch(dj)中，為無(wú)線鏈路(u,v)從其可用的信道集合K(u,v)中隨機(jī)選擇一個(gè)信道分配給(u,v)，更新當(dāng)前節(jié)點(diǎn)。

步驟4：判斷當(dāng)前節(jié)點(diǎn)是否屬于正在構(gòu)造的組播樹Tp，若屬于，則將分支Branch(dj)添加到Tp，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟3。

步驟5：若目的節(jié)點(diǎn)集合Dp為空，則粒子Xi已經(jīng)生成，繼續(xù)產(chǎn)生下一個(gè)粒子；否則，返回步驟2。

算法InitPSO詳見算法1。

算法1　InitPSO算法

2.4適應(yīng)度函數(shù)

本文的目標(biāo)是資源節(jié)約和最小化信道沖突值，形式定義分別如式(1)和式(2)所示，適應(yīng)度函數(shù)的定義如式(13)所示：

f(Xi)=α×Cost(Tp)+β×I(Tp)

(13)

f(Xi)的值越小，說明粒子Xi越靠近極值。

2.5粒子飛行

定義粒子飛行方法是設(shè)計(jì)粒子群優(yōu)化算法的重要內(nèi)容，基本PSO算法中的位置和速度更新公式無(wú)法適應(yīng)于本文研究的問題，因此，重新定義了粒子的飛行以及粒子飛行中用到的3種基本運(yùn)算。

2.5.1加法(⊕)運(yùn)算

(14)

加法運(yùn)算的作用是把原來(lái)組播樹中的一部分用新的分支進(jìn)行替換，或者組播樹中某分支的頻譜分配方案用新的頻譜分配方案替換。

2.5.2 減法(Θ)運(yùn)算

減法運(yùn)算可以描述為：

(15)

2.5.3乘法(?)運(yùn)算

乘法(?)運(yùn)算的作用是實(shí)現(xiàn)截取，計(jì)算公式如式(16)所示：

(16)

2.5.4粒子飛行運(yùn)算

粒子Xi飛行運(yùn)算的作用是向全局最優(yōu)位置和局部最優(yōu)位置學(xué)習(xí)，更新粒子當(dāng)前的位置，表達(dá)式如式(17)所示：

Xi=(Xi⊕Vg)⊕Vl

(17)

粒子Xi與Vg相加表示粒子向全局優(yōu)化目標(biāo)逼近，其結(jié)果再與Vl相加表示粒子向局部?jī)?yōu)化目標(biāo)逼近。

更新粒子Xi的位置時(shí)，同時(shí)與Vg和Vl兩個(gè)速度相加得到一個(gè)新的位置，這個(gè)新位置包含全局最優(yōu)的信息、局部最優(yōu)的信息、粒子本身的信息，這完全符合PSO算法的本質(zhì)特征。

2.6粒子變異

為了使粒子包含新的分支以及給無(wú)線鏈路分配新的信道，本文借鑒遺傳算法的變異操作設(shè)計(jì)了組播樹的變異操作。變異操作可看作是粒子向組播樹與頻譜分配方案解空間中某個(gè)隨機(jī)生成的粒子的一次飛行?；诹Ｗ语w行運(yùn)算可以定義粒子變異操作，如式(18)所示：

(18)

本文中，以變異概率Pm在粒子種群中選擇待變異的粒子。

2.7粒子消環(huán)

圖3　Xi⊕Vi運(yùn)算之后產(chǎn)生的環(huán)Fig.3　Directed circles generated after Xi⊕Vi

消環(huán)操作的基本步驟包括：

步驟3：如果沒有環(huán)，則返回；否則，轉(zhuǎn)步驟4。

步驟4：初始化組播樹T′p使之只包括源節(jié)點(diǎn)Sp。

步驟5：從目的節(jié)點(diǎn)集合Dp中選擇一個(gè)目的節(jié)點(diǎn)dj，從Dp中刪除dj，dj添加到分支Branch(dj)，dj作為當(dāng)前節(jié)點(diǎn)v。

步驟6：判斷節(jié)點(diǎn)v的入度in-degree(v)是否等于1，若是，則只需將N-in(v)中弧尾節(jié)點(diǎn)u添加到Branch(dj)中，更新當(dāng)前節(jié)點(diǎn)，轉(zhuǎn)步驟9。

步驟7：如果in-degree(v)不等于1，則對(duì)N-in(v)中每一個(gè)弧尾節(jié)點(diǎn)u，判斷其是否包括在T′p中，若是，則轉(zhuǎn)步驟5；否則，比較N-in(v)中所有弧尾節(jié)點(diǎn)u到節(jié)點(diǎn)v的鏈路(u,v)對(duì)其他組播業(yè)務(wù)的信道沖突值f(u,v)，計(jì)算公式如式(19)所示。

(19)

其中fq(k,u,v)的定義如式(4)所示。

步驟8：比較所有鏈路(u,v)的f(u,v)，u′記為具有最小值f(u,v)的節(jié)點(diǎn)，u′添加到Branch(dj)，并且更新當(dāng)前節(jié)點(diǎn)。

步驟9：判斷當(dāng)前節(jié)點(diǎn)是否屬于正在構(gòu)造的組播樹T′p，若屬于，則將分支Branch(dj)添加到組播樹T′p，轉(zhuǎn)步驟10；否則，轉(zhuǎn)步驟6。

步驟10：若目的節(jié)點(diǎn)集合Dp為空，則環(huán)已經(jīng)消除，不含環(huán)的組播樹T′p已經(jīng)生成；否則，返回步驟5。

粒子消環(huán)步驟詳見算法2。

算法2　消環(huán)算法

2.8算法MRC3-PSO

本小節(jié)提出滿足QoS約束的多目標(biāo)優(yōu)化組播路由與頻譜分配問題的粒子群優(yōu)化算法MRC3-PSO。步驟包括：

步驟1：調(diào)用粒子初始化算法InitPSO初始化粒子種群；

步驟2：對(duì)每一個(gè)粒子Xi，初始化其局部最優(yōu)位置Pl(i)，根據(jù)式(13)計(jì)算粒子的適應(yīng)度函數(shù)值，初始化全局最優(yōu)位置Pg；

步驟3：對(duì)每一個(gè)粒子Xi，隨機(jī)產(chǎn)生R1,R2和R3，粒子根據(jù)式(17)執(zhí)行飛行操作；

步驟4：以變異概率Pm從粒子種群中選擇變異粒子，隨機(jī)產(chǎn)生R4和R5，根據(jù)式(18)執(zhí)行粒子變異操作；

步驟5：對(duì)經(jīng)過飛行操作和變異操作之后存在環(huán)的粒子，首先進(jìn)行消環(huán)，然后根據(jù)式(13)計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)值;

步驟6：將每一個(gè)粒子與其經(jīng)歷過的局部最好位置Pl(i)進(jìn)行比較，如果優(yōu)于Pl(i)，則更新Pl(i)；

步驟7：比較所有粒子的局部最好位置與整個(gè)種群全局最好位置Pg，如果粒子的局部最好位置優(yōu)于Pg，則更新Pg；

步驟8：如果算法滿足終止條件(算法終止條件為迭代次數(shù)Generation)，則全局最優(yōu)位置Pg為所求的路由與頻譜分配方案，否則轉(zhuǎn)步驟3。

算法MRC3-PSO詳見算法3。

3　性能分析

本節(jié)對(duì)提出的算法MRC3-PSO進(jìn)行性能分析，與之對(duì)比的算法為MSTTP[12]和CL-MTO[13]，其中MSTTP算法是以最小化組播樹的帶寬總消耗為目標(biāo)的組播路由算法，MSTTP算法的基本思想是，單個(gè)組播樹消耗的資源越小，整個(gè)網(wǎng)絡(luò)就可以接受更多的無(wú)線組播業(yè)務(wù)。 CL-MTO算法是以最大化網(wǎng)絡(luò)吞吐量為目標(biāo)的組播路由算法。 仿真采用Microsoft Visual C++ 6.0。

算法3　MRC3-PSO算法

以下所有的仿真結(jié)果均為500次獨(dú)立仿真結(jié)果的均值。仿真主要以無(wú)線組播業(yè)務(wù)數(shù)、組播目的節(jié)點(diǎn)數(shù)和可用信道數(shù)作為參數(shù)，從2個(gè)方面進(jìn)行仿真：組播樹的花費(fèi)；總的信道沖突值。

3.1組播樹花費(fèi)比較

在本仿真中，分析比較不同無(wú)線組播業(yè)務(wù)數(shù)、不同組播目的節(jié)點(diǎn)數(shù)和不同可用信道數(shù)對(duì)組播樹花費(fèi)的影響。仿真結(jié)果如圖4～6所示。

圖4　無(wú)線業(yè)務(wù)需求數(shù)對(duì)組播樹花費(fèi)的影響Fig.4　Comparison of multicast tree cost at different number of multicast requests

圖5　組播目的節(jié)點(diǎn)數(shù)對(duì)組播樹花費(fèi)的影響Fig.5　Comparison of multicast tree cost at different number of multicast destination nodes

圖6　可用信道數(shù)對(duì)組播樹花費(fèi)的影響Fig.6 Comparison of multicast tree cost at different number of available channels

由圖4可知，提出的MRC3-PSO算法的組播樹花費(fèi)低于其他2個(gè)算法，這是因?yàn)槠溥m應(yīng)度函數(shù)中包含資源節(jié)約的目標(biāo)，通過粒子的飛行和變異操作能夠搜索到具有較低組播樹花費(fèi)的解決方案。隨著組播業(yè)務(wù)數(shù)的增多，3個(gè)算法的組播樹花費(fèi)隨之增大。當(dāng)無(wú)線組播業(yè)務(wù)數(shù)為50時(shí)，MRC3-PSO的組播樹花費(fèi)比MSTTP和CL-MTO的分別低24%和23%。

由圖5可知，隨著組播目的節(jié)點(diǎn)數(shù)的增多，3個(gè)算法的組播樹花費(fèi)隨之增多，提出的MRC3-PSO算法的組播樹花費(fèi)低于其他2個(gè)算法。當(dāng)組播目的節(jié)點(diǎn)數(shù)為10時(shí)，MRC3-PSO的組播樹花費(fèi)比MSTTP和CL-MTO的分別低51%和52%。

由圖6可知，隨著可用信道數(shù)的增多，3個(gè)算法的組播樹花費(fèi)隨之減少，這是因?yàn)榭捎眯诺涝蕉?，一個(gè)傳輸可到達(dá)的鄰居節(jié)點(diǎn)越多，所以將需要較少的傳輸節(jié)點(diǎn)。提出的MRC3-PSO算法的組播樹花費(fèi)低于其他2個(gè)算法，當(dāng)可用信道數(shù)為13時(shí)，MRC3-PSO的組播樹花費(fèi)比MSTTP和CL-MTO的分別低35%。

3.2總的信道沖突值比較

在本仿真中，分析比較不同無(wú)線組播業(yè)務(wù)數(shù)、不同組播目的節(jié)點(diǎn)數(shù)和不同可用信道數(shù)對(duì)總的信道沖突值的影響。仿真結(jié)果如圖7～9所示。

由圖7可知，隨著組播業(yè)務(wù)數(shù)的增多，3個(gè)算法的信道沖突值隨之增大，這是因?yàn)橥瑯拥木W(wǎng)絡(luò)資源，組播業(yè)務(wù)數(shù)越多，組播業(yè)務(wù)直接產(chǎn)生沖突的可能性越大。提出的MRC3-PSO算法的信道沖突值低于其他2個(gè)算法，這是因?yàn)槠溥m應(yīng)度函數(shù)中包含最小化信道沖突值的目標(biāo)。當(dāng)無(wú)線組播業(yè)務(wù)數(shù)為50時(shí)，MRC3-PSO的總信道沖突值比MSTTP和CL-MTO的分別低48%和50%。

圖7　無(wú)線業(yè)務(wù)需求數(shù)對(duì)總的信道沖突值的影響Fig.7　Comparison of channel collision value at different number of multicast requests

由圖8可知，隨著組播目的節(jié)點(diǎn)數(shù)的增多，3個(gè)算法的信道沖突值隨之增大。提出的MRC3-PSO算法的信道沖突值低于其他2個(gè)算法。當(dāng)組播目的節(jié)點(diǎn)數(shù)為10時(shí)，MRC3-PSO的總信道沖突值比MSTTP和CL-MTO的分別低53%和55%。

圖8　組播目的節(jié)點(diǎn)數(shù)對(duì)總的信道沖突值的影響Fig.8　Comparison of channel collision value at different number of multicast destination nodes

由圖9可知，隨著可用信道數(shù)的增多，3個(gè)算法的信道沖突值隨之減少，這是因?yàn)榭捎眯诺罃?shù)越多，給各組播業(yè)務(wù)分配的信道產(chǎn)生沖突的可能性越低。提出的MRC3-PSO算法的信道沖突值低于其他2個(gè)算法。當(dāng)可用信道數(shù)為13時(shí)，MRC3-PSO的總信道沖突值比MSTTP和CL-MTO的分別低54%和58%。

圖9　可用信道數(shù)對(duì)總的信道沖突值的影響Fig.9　Comparison of channel collision value at different number of available channels

4　結(jié)論

研究了認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)中，滿足QoS約束的多目標(biāo)優(yōu)化組播路由與頻譜分配問題，目標(biāo)是資源節(jié)約和最小化信道沖突值。不僅考慮為新到組播業(yè)務(wù)構(gòu)造資源節(jié)約的組播樹，而且還考慮新到組播業(yè)務(wù)對(duì)已接受組播業(yè)務(wù)的影響，同時(shí)區(qū)別對(duì)待已接受組播業(yè)務(wù)的影響，考慮各無(wú)線組播業(yè)務(wù)具有不同的權(quán)重，高權(quán)重的已接受組播業(yè)務(wù)相比低權(quán)重的已接受組播業(yè)務(wù)將受到較低的信道沖突。基于粒子群優(yōu)化算法提出了一個(gè)滿足QoS約束的多目標(biāo)優(yōu)化組播路由問題求解框架，包括問題描述、粒子編碼與粒子初始化、適應(yīng)度函數(shù)、粒子飛行、粒子變異、粒子消環(huán)。

通過大量的仿真發(fā)現(xiàn)，MRC3-PSO算法不僅具有較低的組播樹花費(fèi)，達(dá)到了資源節(jié)約的目的，而且達(dá)到了最小化信道沖突值的目的。下一步工作將研究資源節(jié)約和最小化沖突的滿足QoS約束的分布式組播路由與頻譜分配算法。

References)

[1]Chowdhury K R, Akyildiz I F. Cognitive wireless Mesh networks with dynamic spectrum access [J].IEEE Journal on Selected Areas in Communications, 2008, 26(1): 168-181.

[2]Chen T, Zhang H G, Maggio G M, et al. CogMesh:a cluster-based cognitive radio network[C] //Proceeding of IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks(DySPAN), Piscataway, NJ, 2007: 168-178.

[3]賈杰, 林秋思, 陳劍, 等. 認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)中聯(lián)合功率控制與信道分配的擁塞避免[J].計(jì)算機(jī)學(xué)報(bào), 2013, 36(5): 915-925.

JIA Jie, LIN Qiusi, CHEN Jian, et al. Joint power control and channel assignment for congestion avoidance in cognitive radio Mesh network[J]. Chinese Journal of Computers, 2013, 36(5): 915-925. (in Chinese)

[4]方藝霖, 李方敏, 吳鵬, 等. 無(wú)線Mesh網(wǎng)絡(luò)組播路由協(xié)議[J].軟件學(xué)報(bào), 2010, 21(6): 1308-1325.

FANG Yilin, LI Fangmin, WU Peng, et al. Multicast routing protocol for wireless Mesh networks [J]. Journal of Software, 2010, 21(6): 1308-1325. (in Chinese)

[5]Jahanshahi M, Barmi A T.Multicast routing protocols in wireless mesh networks: a survey[J].Computing, 2014, 96(11): 1029-1057.

[6]Cesana M, Cuomo F, Ekici E. Routing in cognitive radio networks: challenges and solutions [J].Ad Hoc Networks, 2011, 9(3): 228-248.

[7]Qadir J, Baig A, Ali A, et al. Multicasting in cognitive radio networks: algorithms, techniques and protocols[J].Journal of Network and Computer Applications， 2014， 45: 44-61.

[8]Almasaeid H M, Kamal A E. Exploiting multichannel diversity for cooperative multicast in cognitive radio mesh networks [J].IEEE/ACM Transactions on Networking, 2014, 22(3): 770-783.

[9]Almasaeid H M, Jawadwala T H, Kamal A E. On-demand multicast routing in cognitive radio Mesh networks[C] // Proceeding of IEEE Global Telecommunications Conference (GLOBECOM), Piscataway, NJ, 2010: 1-5.

[10]鄺祝芳, 陳志剛. 認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)中QoS約束的組播路由算法[J].軟件學(xué)報(bào), 2012, 23(11): 3029-3044.

KUANG Zhufang, CHEN Zhigang. Research on joint multicast routing and spectrum allocation algorithm with QoS constraints in cognitive wireless Mesh networks[J].Journal of Software, 2012, 23(11): 3029-3044. (in Chinese)

[11]鄺祝芳, 陳志剛, 劉蕙. 一種認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)中負(fù)載均衡的組播路由算法[J].計(jì)算機(jī)學(xué)報(bào),2013, 36(3):521-531.

KUANG Zhufang, CHEN Zhigang, LIU Hui. A load-balanced multicast routing algorithm in cognitive wireless Mesh networks[J]. Chinese Journal of Computers, 2013, 36(3): 521-531. (in Chinese)

[12]Xie L M, Jia X H, Zhou K X. QoS multicast routing in cognitive radio ad hoc networks [J].International Journal of Communication Systems, 2012, 25(1): 30-46.

[13]Pan M, Long Y, Yue H, et al. Multicast throughput optimization and fair spectrum sharing in cognitive radio networks[C] // Proceeding of IEEE Global Communications Conference (GLOBECOM), Piscataway, NJ, 2012: 1085-1089.

[14]Naeem M, Pareek U, Lee D C. Max-min fairness aware joint power, subcarrier allocation and relay assignment in multicast cognitive radio [J]. IET Communications, 2012, 6(11): 1511-1518.

[15]Shu Z H, Qian Y, Yang Y Q, et al. Channel allocation and multicast routing in cognitive radio networks[C]//Proceeding of IEEE Wireless Communications and Networking Conference(WCNC), Piscataway, NJ, 2013: 1703-1708.

[16]Gao C H, Shi Y, Hou Y T, et al. Multicast communications in multi-hop cognitive radio networks [J].IEEE Journal on Selected Areas in Communications, 2011, 29(4): 784-793.

[17]Hu D L, Mao S W, Hou Y T, et al. Scalable video multicast in cognitive radio networks [J].IEEE Journal on Selected Areas in Communications, 2010, 28(3): 434-444.

[18]Jie Y, Kamal A E. Multi-objective multicast routing optimization in cognitive radio networks[C]// Proceeding of IEEE Wireless Communications and Networking Conference, 2014: 2576-2581.

[19]Tan C K, Chuah T C,Tan S W. A coalitional game-based algorithm for OFDMA resource allocation in multicast cognitive radio networks[J]. Wireless Personal Communications, 2015， 80(1): 415-427.

[20]Kennedy J, Eberhart R. Particle swarm optimization[C]// Proceeding of IEEE Conference on Neural Network, Perth, Australia, 1995， 4: 1942-1948.

[21]劉安豐, 吳賢佑, 陳志剛. 一種基于PSO的有效能量空洞避免的無(wú)線傳感器路由算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2009, 46(4): 575-582.

LIU Anfeng, WU Xianyou, CHEN Zhigang. An energy-hole avoidance routing algorithm for WSN based on PSO[J]. Journal of Computer Research and Development, 2009, 46(4): 575-582.(in Chinese)

Multicast routing algorithm with minimizing channel collision and resource consumption in cognitive wireless Mesh networks

YANG Yiqing, CHEN Zhigang

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

In cognitive wireless Mesh networks, the multiple-objective optimization problem with quality of service constraints is more complicated than the single objective optimization problem. To obtain the optimal multicast routing solution which satisfies the quality of service constraints and is aimed at minimizing the channel collision and the resource consumption, a problem solving framework which contains problem description, particle encoding, particle initialization, fitness function, particle flight, particle mutation, particle elimination circle, was proposed on the basis of particle swarm optimization. Adjacency matrix which shows the connection relation between nodes was used to represent particle. Three operation rules, particle flight operation and particle mutation operation were redefined. Simulation results show that the proposed algorithm can achieve the expected goal. It can achieve the effect of a lower resource consumption and a smaller channel collision value.

cognitive wireless Mesh network; multicast; spectrum allocation; particle swarm optimization

10.11887/j.cn.201604012http://journal.nudt.edu.cn

2015-12-18

國(guó)家自然科學(xué)基金資助項(xiàng)目(61379057， 61309027， 61073186);湖南省教育廳優(yōu)秀青年基金資助項(xiàng)目(13B148);中國(guó)博士后基金面上資助項(xiàng)目(2013M542136)

楊藝清(1973─)，男，湖南韶山人，博士研究生，E-mail: yyq@hunnu.edu.cn；陳志剛(通信作者)，男，教授，博士，博士生導(dǎo)師，E-mail：czg@mail.csu.edu.cn

TP393

A

1001-2486(2016)04-076-09