基于SIR沖突圖和最大獨(dú)立集的無(wú)線Mesh網(wǎng)絡(luò)信道分配方案

戴 冬， 衛(wèi) 娟， 王 磊

(1.河南工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，河南 新鄉(xiāng) 453003;2.西南財(cái)經(jīng)大學(xué) 經(jīng)濟(jì)信息工程學(xué)院，四川 成都 610074)

?

基于SIR沖突圖和最大獨(dú)立集的無(wú)線Mesh網(wǎng)絡(luò)信道分配方案

戴 冬1， 衛(wèi) 娟1， 王 磊2*

(1.河南工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，河南 新鄉(xiāng) 453003;2.西南財(cái)經(jīng)大學(xué) 經(jīng)濟(jì)信息工程學(xué)院，四川 成都 610074)

針對(duì)現(xiàn)有無(wú)線Mesh網(wǎng)絡(luò)信道分配方案中的沖突模型不能反映真實(shí)網(wǎng)絡(luò)干擾，提出一種基于信號(hào)干擾比(SIR)沖突圖和最大獨(dú)立集的信道分配方案.首先，由于射頻信號(hào)的反射干擾遠(yuǎn)高于噪聲，所以利用節(jié)點(diǎn)間的SIR代替?zhèn)鹘y(tǒng)信號(hào)干擾噪聲比(SINR)來(lái)構(gòu)建沖突圖，同時(shí)考慮了節(jié)點(diǎn)累積干擾.然后，在沖突圖基礎(chǔ)上，通過(guò)提出的信道分配算法構(gòu)建節(jié)點(diǎn)最大獨(dú)立集，最終獲得最低干擾的信道分配方案.實(shí)驗(yàn)結(jié)果表明，該方案在不同節(jié)點(diǎn)度下都具有較低的干擾比例和較高的網(wǎng)絡(luò)吞吐量.

無(wú)線Mesh網(wǎng)絡(luò)；信道分配；沖突圖；信號(hào)干擾比；最大獨(dú)立集

無(wú)線Mesh網(wǎng)絡(luò)(WMN)是一種由網(wǎng)關(guān)、無(wú)線路由器和移動(dòng)站組成的網(wǎng)絡(luò)[1].WMN的多跳特性和快速增長(zhǎng)的吞吐量需求使其形成多信道、多接口的網(wǎng)狀網(wǎng)絡(luò)[2]，然而這也增加了信道之間的干擾[3].在WMN中，信道分配是一種NP-Hard問(wèn)題.最近十年間，研究者提出了多種信道分配方法.[4]提出一種基于集中式算法的信道分配方法，該方法提供了一種結(jié)合連通性和流量模式的信號(hào)分配方法，但是會(huì)導(dǎo)致一系列連鎖反應(yīng)，即已經(jīng)分配的鏈路會(huì)重新被訪問(wèn)，增加了時(shí)間復(fù)雜度. [5]提出一種基于禁忌搜索的圖著色算法(TABU)，然而，該算法通過(guò)迭代共享分配的兩種無(wú)線電來(lái)避免沖突增加，因此，增加了復(fù)雜度且降低了系統(tǒng)性能.[6]提出一種基于離散粒子群優(yōu)化算法(DPSO)的拓?fù)浔Ｐ涡诺婪峙洳呗?，以最小化網(wǎng)絡(luò)中的信道干擾為目標(biāo)，通過(guò)粒子運(yùn)動(dòng)來(lái)尋找最優(yōu)解.然而，這些方案都在基于傳統(tǒng)信號(hào)干擾噪聲比(SINR)模型的沖突圖上執(zhí)行[7]，只有構(gòu)建出能夠真切反映網(wǎng)絡(luò)干擾情況的沖突圖，才能有效合理分配信道并降低干擾.傳統(tǒng)SINR模型不能反映無(wú)線連接中信號(hào)傳播的實(shí)際情況.在真實(shí)的無(wú)線信道中，射頻信號(hào)會(huì)從附近物體反射回來(lái)并圍繞物體，這導(dǎo)致了信號(hào)強(qiáng)度在空間內(nèi)波動(dòng)[8].由于同波段干擾遠(yuǎn)高于噪聲，所以本文使用信號(hào)干擾比(SIR)代替?zhèn)鹘y(tǒng)SINR，提出一種基于SIR沖突圖和最大獨(dú)立集的WMN信道分配方案.首先，基于節(jié)點(diǎn)間的SIR和累積干擾構(gòu)建網(wǎng)絡(luò)沖突圖.然后，在沖突圖上，通過(guò)提出的信道分配算法構(gòu)建節(jié)點(diǎn)最大獨(dú)立集，最終獲得最低干擾的信道分配方案.實(shí)驗(yàn)結(jié)果表明，本文方案具有較低的干擾比例和較高的網(wǎng)絡(luò)吞吐量.

1 基于SIR模型的沖突圖

不同于包含1(表示沖突)和0(表示非沖突)的傳統(tǒng)沖突圖矩陣[9]，本文基于SIR模型沖突圖中的沖突矩陣元素為1和一個(gè)鏈接從其他鏈接接收到的最大功率.沖突圖的輸入如下：f：頻率；Gt：發(fā)射器的增益；Gr：接收器的增益；ht：發(fā)射器天線的高度；hr：接收器天線的高度；n：節(jié)點(diǎn)數(shù)量；RxThresh_dBm：dBm中的接收閾值；SIRThresh_dB：dB中的SIR閾值；L：路由中包含的鏈接集；locations_x：節(jié)點(diǎn)橫坐標(biāo)集；locations_y：節(jié)點(diǎn)縱坐標(biāo)集.

輸入:f、Gr、ht、hr、n、RxThresh_dBm、SIRThresh_dB、L、locations_x、locations_y.輸出:沖突圖conflict_matrix1.RxThresh_mwatts←10SIRThresh_dB/10()2.SIRThresh←10SIRThresh_dB/10()3.m←L4.Fori=1ton:5.Forj=1ton:6.dist_alli,j()←節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離7.endFor8.endFor9.Fori=1tom:10.Li,3()←鏈接i中兩節(jié)點(diǎn)之間的距離11.Li,4()←鏈接i的傳輸功率12.endFor13.初始化一個(gè)m×mconflict_matrix14.Fori1=1tom:15.初始化一個(gè)空的沖突表16.Forj=1tom:17.conflict_tablej,1()←鏈接i1上的節(jié)點(diǎn)x18.conflict_tablej,2()←鏈接i1上的節(jié)點(diǎn)y19.conflict_tablej,3()←鏈接j上的節(jié)點(diǎn)p20.conflict_tablej,4()←鏈接j上的節(jié)點(diǎn)q21.Pr,xp←使用公式(2)或(4)得到的鏈接i1上的節(jié)點(diǎn)x從鏈接j上的節(jié)點(diǎn)p接收的功率22.Pr,xq←使用公式(2)或(4)得到的鏈接i1上的節(jié)點(diǎn)x從鏈接j上的節(jié)點(diǎn)q接收的功率23.Pr,yp←使用公式(2)或(4)得到的鏈接i1上的節(jié)點(diǎn)y從鏈接j上的節(jié)點(diǎn)p接收的功率24.Pr,yq←使用公式(2)或(4)得到的鏈接i1上的節(jié)點(diǎn)y從鏈接j上的節(jié)點(diǎn)q接收的功率25.conflict_tablej,5()←Pr,xp26.conflict_tablej,6()←Pr,xq27.conflict_tablej,7()←Pr,yp28.conflict_tablej,8()←Pr,yq29.conflict_tablej,9()←maxPr,xp,Pr,xq,Pr,yp,Pr,yq()30.conflict_tablej,10()←RxThresh_mwatts/maxPr,xp,Pr,xq,Pr,yp,Pr,yq()31.endFor32.Fori2=1tom:33.如果conflict_tablei2,10()>SIRThresh:34.conflict_matrixi1,i2()←conflict_tablei2,9()35.endIf36.endFor37.endFor38.輸出conflict_matrix結(jié)束

圖1 基于SIR模型構(gòu)建沖突圖過(guò)程

Fig.1 Theprocess of building conflict graph based on the SIR model

2 基于沖突圖的信道分配

本文信道分配算法的基本思想是：首先從沖突圖中選擇具有最大節(jié)點(diǎn)度的頂點(diǎn)并將該頂點(diǎn)加入到建設(shè)中的臨時(shí)WMIS中.然后逐一檢查該沖突圖的其他頂點(diǎn)，如果這些頂點(diǎn)沒有邊與已在該集合中的任何頂點(diǎn)連接，那么將其放入WMIS中.然而，上述思想考慮了單一干擾，為了進(jìn)一步提高其實(shí)用性，本文添加考慮了累積干擾，即WMIS上每個(gè)頂點(diǎn)的累積SIR都必須比SIR閾值大，其中，一個(gè)頂點(diǎn)的累積SIR為RxThresh_mwatts與從WMIS中所有其他頂點(diǎn)接收的最大功率總和的比值.這解釋了WMIS中一個(gè)頂點(diǎn)從該集合中所有其他頂點(diǎn)受到的累積干擾.那么，此時(shí)本文信道分配算法可描述為，如果一個(gè)頂點(diǎn)w不受到WMIS中頂點(diǎn)的干擾，那么將w和該頂點(diǎn)加入到WMIS的一個(gè)臨時(shí)集合中.如果此時(shí)臨時(shí)集合中的每個(gè)頂點(diǎn)從該集合中的所有其他頂點(diǎn)得到累積SIR都大于SIR閾值，那么就將w加入WMIS.圖2顯示了本文提出的信道分配算法的偽代碼.

3 實(shí)驗(yàn)及分析

3.1 網(wǎng)絡(luò)環(huán)境

利用NS-2網(wǎng)絡(luò)仿真器構(gòu)建500 m×500 m大小的無(wú)線Mesh網(wǎng)絡(luò)，并劃分成單元格，將節(jié)點(diǎn)隨機(jī)放入單元格中，構(gòu)建10個(gè)包含51個(gè)節(jié)點(diǎn)的不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò).將節(jié)點(diǎn)15設(shè)定為網(wǎng)關(guān)節(jié)點(diǎn)，并放置在網(wǎng)絡(luò)中央，用于匯聚各節(jié)點(diǎn)信息.那么，網(wǎng)絡(luò)中存在35個(gè)流量源，通過(guò)不同路徑到達(dá)網(wǎng)關(guān)節(jié)點(diǎn).為了構(gòu)建基于SIR模型的沖突圖，本文設(shè)定通信頻率為5.805 GHz，Gt和Gr都為1，ht和hr都為3 m，接收SIR閾值為65 dBm，鏈接數(shù)據(jù)率為24 Mbps，網(wǎng)絡(luò)中可用信道數(shù)為12.

輸入:L:路由包含鏈接的集合;FVF,EF():沖突圖;SIRThresh_dB:SIR在dB中的閾值;RxThresh_dBm:dB中接收器的閾值.輸出:VWMIS:頂點(diǎn)的WMIS;LWMIS:中相應(yīng)于WMIS中頂點(diǎn)的鏈接的集合;c:WMIS的數(shù)量.1.c←02.m←L=VF3.SIRThresh←10SIRThresh_dB/10()4.RxThresh_mwatts←10SIRThresh_dB/10()5.當(dāng)m≥16.如果F是全連接或m=1dist_alli,j()←節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離7.Ford=1tom:8.初始化空的VWMIS和LWMIS9.將頂點(diǎn)d添加到VWMIS并且將相應(yīng)的鏈接添加到LWMIS10.輸出VWMIS和LWMIS11.c←c+112.endFor13.輸出c和信道14.endIf15.初始化空的VWMIS和LWMIS16.將F中具有最大節(jié)點(diǎn)度的頂點(diǎn)添加到VWMIS并將相應(yīng)的鏈接添加到LWMIS17.Fori=1tom:18.如果頂點(diǎn)i與VWMIS中的節(jié)點(diǎn)沒有界限:19.Vtemp←VWMIS∪i20.endIf21.如果Vtemp中的每個(gè)頂點(diǎn)從Vtemp中其他頂點(diǎn)得到的累積SIR大于SIRThresh:22.將頂點(diǎn)i添加到VWMIS并將相應(yīng)的鏈接添加到LWMIS23.endIf24.endFor25.輸出VWMIS和LWMIS26.c←c+127.VF←VFVWMIS28.L←LLWMIS29.m←L30.endWhile31.輸出c結(jié)束

圖2 本文提出的信道分配算法

Fig.2 The channel allocation algorithm

3.2 性能比較

本文在網(wǎng)絡(luò)干擾比例和網(wǎng)絡(luò)吞吐量方面，與[5]提出的禁忌搜索方案和[6]提出的離散粒子群方案進(jìn)行比較，其中網(wǎng)絡(luò)干擾比例為受干擾的鏈接占所有鏈接的數(shù)量，網(wǎng)絡(luò)吞吐量為網(wǎng)絡(luò)中所有50個(gè)流量源所傳輸?shù)牧髁靠偤?實(shí)驗(yàn)中，設(shè)定節(jié)點(diǎn)度(NDC)為2～7不同的場(chǎng)景.通常節(jié)點(diǎn)度越多(即鏈路數(shù)量越多)，干擾越強(qiáng)[12].實(shí)驗(yàn)中的數(shù)據(jù)都為在10個(gè)不同拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)上實(shí)驗(yàn)結(jié)果的平均值.

圖3顯示了節(jié)點(diǎn)具備不同節(jié)點(diǎn)度時(shí)的網(wǎng)絡(luò)干擾比值.可以看出，隨著節(jié)點(diǎn)度的增加，網(wǎng)絡(luò)干擾量也在增加，這是因?yàn)槊總€(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的鏈路增加，但網(wǎng)絡(luò)信道數(shù)量是一定的，所以增加了鏈路間的干擾概率.其中，本文方案具有最低的網(wǎng)絡(luò)干擾比例，在NDC=2時(shí)，約為0.8%；NDC=7時(shí)，約為7.9%，明顯低于其他兩種方案.這是因?yàn)椋疚姆桨咐肧IR構(gòu)建沖突圖，并考慮了累積干擾，同時(shí)利用提出的信道分配算法獲得頂點(diǎn)加權(quán)最大獨(dú)立集(WMIS)，實(shí)現(xiàn)了網(wǎng)絡(luò)的最低干擾.

圖4顯示了不同節(jié)點(diǎn)度下的網(wǎng)絡(luò)總吞吐量.同樣，隨著節(jié)點(diǎn)度的增加，網(wǎng)絡(luò)吞吐量也增加，但達(dá)到一定程度后趨于穩(wěn)定.這是因?yàn)楣?jié)點(diǎn)度的增加使網(wǎng)絡(luò)中鏈路數(shù)量增加，從而使節(jié)點(diǎn)發(fā)送數(shù)據(jù)的量增加，最終提高了網(wǎng)絡(luò)吞吐量.但增加鏈路數(shù)量也增加了網(wǎng)絡(luò)干擾，影響了吞吐量，所以最終會(huì)趨于穩(wěn)定.其中，本文方案具有最高的吞吐量.例如，在節(jié)點(diǎn)具有4個(gè)接口時(shí)，與[5]和[6]相比，吞吐量分別提高了25.6%和10.7%.

4 結(jié) 論

由于在障礙物較多的環(huán)境中，射頻信號(hào)的反射干擾遠(yuǎn)高于噪聲，傳統(tǒng)基于SINR構(gòu)建的沖突圖不能反映真實(shí)網(wǎng)絡(luò)干擾情況.為此，提出了一種基于信號(hào)干擾比(SIR)沖突圖和最大獨(dú)立集的信道分配方案.利用SIR模型構(gòu)建沖突圖，并利用提出的分配算法構(gòu)建節(jié)點(diǎn)最大獨(dú)立集，獲得干擾最低的信道分配方案.與現(xiàn)有方案相比，本文方案獲得了較低的干擾和較高的網(wǎng)絡(luò)吞吐量.

[1] 鄺祝芳, 陳志剛. 認(rèn)知無(wú)線Mesh網(wǎng)絡(luò)中一種有效的多目標(biāo)優(yōu)化頻譜分配算法[J]. 中南大學(xué)學(xué)報(bào)：自然科學(xué)版, 2013, 44(6):124-129.

[2] 黃向黨, 羊秋玲, 金志剛. 無(wú)線Mesh網(wǎng)絡(luò)延遲及丟包控制機(jī)制研究[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 2013, 35(3):95-101.

[3] PENG Y, YU Y, GUO L, et al. An efficient joint channel assignment and Q°S routing protocol for IEEE 802.11 multi-radio multi-channel wireless mesh networks[J]. Journal of Network and Computer Applications, 2013, 36(2): 843-857.

[4] LIN T Y,HSIEH K C,HUANG H C. Applying genetic algorithms for multiradio wireless mesh network planning[J]. Vehicular Technology, Transactions on IEEE, 2012, 61(5):2 256-2 270.

[5] GIRGIS M R, MAHMOUD T M, ABDULLATIF B A, et al. Solving the wireless mesh network design problem using genetic algorithm and tabu search optimization methods[J]. Ijcnwc Org, 2014, 4(11):2 250-3 501.

[6] VAEZPOUR E, DEHGHAN M. Evolutionary-based channel assignment in multi-radio multi-channel wireless mesh networks for multicast applications[J]. International Journal of Ad Hoc & Ubiquitous Computing, 2013, 13(1):38-47.

[7] 胡首都, 胡捍英, 仵國(guó)鋒. 一種認(rèn)知無(wú)線電網(wǎng)絡(luò)接入控制和功率控制聯(lián)合設(shè)計(jì)[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2011, 28(9):70-72.

[8] 田啟明, 余官定. 無(wú)線Mesh網(wǎng)絡(luò)中基于信道流量干擾感知的路由協(xié)議[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(6):2 254-2 256.

[9] SIRIS V A, DELAKIS M. Interference-aware channel assignment in a metropolitan multi-radio wireless mesh network with directional antennas[J]. Computer Communications, 2011, 34(12):1 518-1 528.

[10] 謝琦, 黃廷磊. 基于節(jié)點(diǎn)度優(yōu)化的無(wú)線mesh網(wǎng)絡(luò)拓?fù)淇刂扑惴╗J]. 桂林電子科技大學(xué)學(xué)報(bào), 2012, 32(3):233-236.

[11] ZHU G, JIANG X, WU C, et al. A cluster head selection algorithms in wireless network based on maximal weighted independent set[C]// Ubiquitous Information Technologies and Applications (CUTE), 2010 Proceedings of the 5th International Conference on IEEE, 2010:1-6.

[12] 邱振謀, 姚國(guó)祥, 官全龍,等. 多信道無(wú)線Mesh網(wǎng)絡(luò)的多播信道分配算法[J]. 計(jì)算機(jī)工程, 2011, 37(6):107-109.

責(zé)任編輯：龍順潮

Wireless Mesh Network Channel Assignment Scheme Based on SIR Conflict Graph and Maximal Independent Set

DAIDong1,WEIJuan1,WANGLei2*

(1.Department of Computer Science and Technology, Henan Institute of Technology, Xinxiang 453003; 2.College of Economic Information Engineering, Southwestern University of Finance and Economics, Chengdu 610074 China)

For the issues that the existing conflict model in wireless Mesh network channel allocation scheme can not reflect the real network interference, a channel assignment scheme based on signal interference ratio (SIR) conflict graph and maximum independent set is proposed. Firstly, because the reflection interference of radio frequency signal is much higher than the noise, the SIR is used to instead the traditional signal to interference noise ratio (SINR) for constructing the conflict graph. Then, the maximum independent set of nodes is constructed by the proposed channel assignment algorithm based on the conflict graph, and the minimum interference channel allocation scheme is obtained. Experimental results show that the proposed scheme has a lower interference ratio and higher network throughput at different node degrees.

wireless mesh network; channel assignment; conflict graph; signal interference ratio; maximal independent set

2016-02-17

國(guó)家自然科學(xué)基金(71473201)；中央高?；究蒲袠I(yè)務(wù)費(fèi)重大基礎(chǔ)理論研究項(xiàng)目(JBK151127)；河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(16A520048，15B520007)

王磊(1978-)，男，河南 信陽(yáng)人，博士，副教授，碩士生導(dǎo)師.E-mail:wanglei_t@swufe.edu.cn

TP393

A

1000-5900(2016)02-0109-05