袁俊嶺,李旭紅,楊麗華

(1.鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院,河南鄭州450001;2.中原工學(xué)院理學(xué)院,河南鄭州450007)

無線蜂窩網(wǎng)中基于Δ-鄰域超圖的信道重用模型*

袁俊嶺1,李旭紅2,楊麗華2

(1.鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院,河南鄭州450001;2.中原工學(xué)院理學(xué)院,河南鄭州450007)

信道重用問題是基于頻分多址技術(shù)的無線蜂窩網(wǎng)絡(luò)中的一項(xiàng)關(guān)鍵技術(shù),它關(guān)系到信道的傳輸效率,傳統(tǒng)的方式是用沖突圖模型來表示該問題。但是,由于沖突圖模型中只考慮了兩個(gè)小區(qū)之間的干擾,無法反映多個(gè)小區(qū)之間干擾的情況,又有人用超圖模型來描述該問題。超圖的建模為指數(shù)時(shí)間的,為了降低建模的計(jì)算復(fù)雜度,將該問題描述為Δ-鄰域超圖模型。性能分析結(jié)果表明,該模型既可以在多項(xiàng)式時(shí)間內(nèi)完成建模,又可以充分反映多個(gè)小區(qū)之間的干擾關(guān)系。

無線蜂窩網(wǎng) 信道重用 超圖 Δ-鄰域超圖

0 引 言

在基于頻分多址技術(shù)的無線蜂窩網(wǎng)中,頻譜資源通常被劃分為多個(gè)相互獨(dú)立的信道,這些信道被分配給不同的蜂窩小區(qū),供小區(qū)內(nèi)的呼叫請(qǐng)求使用[1]。每個(gè)呼叫請(qǐng)求需要使用一個(gè)信道,由于總的頻譜資源是有限的,為了能夠同時(shí)容納更多的呼叫請(qǐng)求,小區(qū)之間需要對(duì)信道資源進(jìn)行重用[2]。當(dāng)多個(gè)小區(qū)使用同一個(gè)信道進(jìn)行通信時(shí),會(huì)產(chǎn)生同信道干擾;在進(jìn)行信道重用時(shí),就需要合理選擇共用同一個(gè)信道的小區(qū),以滿足通信的最小信干比(SIR,Signal to Interference Ratio)要求。

最常用的方式是將信道重用問題表示為沖突圖模型[2]。在該模型中,每個(gè)小區(qū)被看作一個(gè)節(jié)點(diǎn);若兩個(gè)小區(qū)共用一個(gè)信道時(shí),相互間的干擾使得接收機(jī)處的信干比小于給定的閾值,則認(rèn)為這兩個(gè)小區(qū)在進(jìn)行信道重用時(shí)存在“沖突”,此時(shí)就在這兩個(gè)小區(qū)所對(duì)應(yīng)的節(jié)點(diǎn)之間連接一條邊。在模型建好之后,只需要尋找沖突圖的最大獨(dú)立集即可。假設(shè)網(wǎng)絡(luò)中共有N個(gè)小區(qū),建立沖突圖模型時(shí)最多需要檢查對(duì)小區(qū)之間是否存在沖突,故其計(jì)算復(fù)雜度為O(N2)。

干擾不只存在于兩個(gè)小區(qū)之間,還存在于多個(gè)小區(qū)之間。為了描述多個(gè)小區(qū)之間的干擾,Sarkar和Sivarajan在1998年提出了描述該問題的超圖模型[3]。超圖是圖的一種擴(kuò)展,其節(jié)點(diǎn)的概念與圖中相同,而把圖中“每條邊只包含兩個(gè)節(jié)點(diǎn)”擴(kuò)展為“每條超邊可以包含任意個(gè)數(shù)的節(jié)點(diǎn)”。因此,用超圖模型可以描述多個(gè)小區(qū)之間的干擾。若由多個(gè)小區(qū)組成的集合滿足:①它們之間的相互干擾使得其中至少一個(gè)小區(qū)內(nèi)的信干比小于給定閾值;②它們的任何一個(gè)真子集都不滿足此條件,則這幾個(gè)小區(qū)就組成一個(gè)超邊。該模型由于需要檢查所有的小區(qū)集合是否為超邊,最多需要檢查2N-N個(gè)集合,故其計(jì)算復(fù)雜度為O(2N)。

超圖模型可以完整地描述小區(qū)之間的干擾,但是其計(jì)算復(fù)雜度為指數(shù)時(shí)間的。為了降低計(jì)算復(fù)雜度,Li等人在2008年考慮了一般無線網(wǎng)絡(luò)中限定超邊規(guī)模的超圖模型[4]。在該模型中,限定每個(gè)超邊不超過k個(gè)節(jié)點(diǎn),并把由此得到的超圖稱作k-超圖。該建模方法最多需要考慮+…+個(gè)集合是否構(gòu)成超邊,由于k為一個(gè)遠(yuǎn)小于N的常數(shù),故其計(jì)算復(fù)雜度為O(Nk)。該建模方法以降低模型精確度為代價(jià)換取了計(jì)算復(fù)雜度的降低。如何以最小的精確度代價(jià)來換取最大程度的計(jì)算復(fù)雜度降低,是需要進(jìn)一步研究的內(nèi)容。

本文給出一種稱為Δ-鄰域超圖的建模方法,該方法尋找每個(gè)小區(qū)的Δ-鄰域,然后在該鄰域內(nèi)組建超邊。該方法既可以降低計(jì)算復(fù)雜度,又能夠較為精確地反映小區(qū)之間的干擾情況。在本文的剩余部分,首先介紹Δ-鄰域超圖的構(gòu)建方法,然后對(duì)幾種建模方法的性能進(jìn)行比較,最后對(duì)本文進(jìn)行總結(jié)。

1 Δ-鄰域超圖模型

1.1 小區(qū)之間的干擾

在無線網(wǎng)絡(luò)中,若發(fā)射機(jī)與接收機(jī)之間的距離為d,發(fā)射功率為PT,則接收功率PR與PT·d-α成正比,其中α為3到5之間的常數(shù)。假設(shè)網(wǎng)絡(luò)中共有K個(gè)小區(qū)共用一個(gè)信道,在不考慮背景噪聲的情況下,其中一個(gè)小區(qū)k0中的接收機(jī)接收到的信干比為[2,5]:

式中,dk為該接收機(jī)到第k個(gè)小區(qū)中發(fā)射機(jī)的距離。系統(tǒng)通常會(huì)有一個(gè)保證通信質(zhì)量的最小信干比閾值,閾值的大小與系統(tǒng)的編碼和調(diào)制方式、以及解碼和解調(diào)方式有關(guān)。只有接收機(jī)接收到的信干比不小于給定閾值時(shí),才能保證正常通信。

由于信號(hào)功率隨著傳輸距離的增加而快速衰減,故此當(dāng)兩個(gè)小區(qū)之間的距離超過一定距離之時(shí),它們之間的干擾會(huì)變得非常小。基于這種觀察,在建模時(shí)可以只考慮一個(gè)小區(qū)周圍一定距離內(nèi)的小區(qū)對(duì)它的干擾,Δ-鄰域超圖的概念就是基于這種考慮而提出的。

1.2 小區(qū)的鄰域

在無線蜂窩網(wǎng)中,記相鄰兩個(gè)小區(qū)之間的距離為1,則一個(gè)小區(qū)與其它小區(qū)之間的距離可以表示為離散的數(shù)值:1、、2、、3、…。圖1是由37個(gè)小區(qū)組成的無線蜂窩網(wǎng),可以看出,與小區(qū)1之間距離為1、、2的小區(qū)個(gè)數(shù)都為6,距離為7和3的小區(qū)個(gè)數(shù)都為12。對(duì)于給定的距離Δ,則與小區(qū)1之間的距離不大于Δ的小區(qū)可以組成一個(gè)集合,由此可以給出小區(qū)的Δ-鄰域的概念。

圖1 由37個(gè)小區(qū)組成的無線蜂窩網(wǎng)Fig.1 Cellular network composed of 37 cells

定義1：對(duì)于無線蜂窩網(wǎng)中的一個(gè)小區(qū)ni,稱與其距離不大于Δ的所有小區(qū)所組成的集合為該小區(qū)的Δ-鄰域,記為NΔ(ni)。

例如在圖1中,小區(qū)1的1-鄰域?yàn)閧1,2,3,4, 5,6,7},1.5-鄰域與1-鄰域完全相同;-鄰域?yàn)閧1,2,3,4,5,6,7,9,11,13,15,17,19};而2-鄰域中則包含編號(hào)從1到19的所有小區(qū)?？梢钥闯?隨著Δ的增加,一個(gè)小區(qū)的Δ-鄰域中所包含的小區(qū)個(gè)數(shù)是階梯增加的。

1.3 Δ-鄰域超圖的組建方法

定義2：對(duì)于一個(gè)超圖H,若其中任何一個(gè)超邊e中的任何兩個(gè)節(jié)點(diǎn)之間的距離都不超過2Δ,則稱超圖H是一個(gè)Δ-鄰域超圖。

在構(gòu)建Δ-鄰域超圖時(shí),首先需要針對(duì)每個(gè)小區(qū)尋找其Δ-鄰域,然后在該鄰域內(nèi)尋找構(gòu)成超邊的小區(qū)集合。假設(shè)網(wǎng)絡(luò)中共有N個(gè)小區(qū),記所有小區(qū)的集合為S={n1,n2,…,nN};假設(shè)通信系統(tǒng)的信干比閾值為SIRmin。構(gòu)建Δ-鄰域超圖的具體步驟如下:

步驟1:從集合S中取出一個(gè)小區(qū)(假設(shè)為ni),尋找其Δ-鄰域NΔ(ni),并將ni從S中刪除;

步驟2:以元素個(gè)數(shù)從少到多的順序,列出NΔ(ni)的所有“元素個(gè)數(shù)不少于2”的子集;并根據(jù)閾值SIRmin判斷每個(gè)子集是否構(gòu)成超邊。

步驟3:查看S中是否還存在元素,若存在,則返回步驟1;否則,超圖構(gòu)建完成。

在構(gòu)建超圖的過程中,步驟一需要遍歷所有的小區(qū),故共需要N步;而針對(duì)每個(gè)小區(qū)的Δ-域(記其最大勢(shì)為),需要逐個(gè)檢查其元素個(gè)數(shù)大于1的子集是否構(gòu)成超邊,故最多需要步。兩個(gè)步驟之間是嵌套關(guān)系,故該算法共需要N·次運(yùn)算。由于對(duì)于給定的Δ,是一個(gè)常數(shù),故算法的計(jì)算復(fù)雜度為O(N)。

2 性能比較

本文提出Δ-鄰域超圖的目的是為了在模型精確度與計(jì)算復(fù)雜度之間進(jìn)行折中,在這里比較幾種建模方法的兩種性能,一是建模方法的計(jì)算復(fù)雜度,二是模型的精確度。

2.1 計(jì)算復(fù)雜度的比較

通過上述的分析可知,沖突圖模型的計(jì)算復(fù)雜度為O(N2),最多需要次運(yùn)算;超圖模型的計(jì)算復(fù)雜度為O(2N),最多需要2N-N次運(yùn)算;k-超圖模型的計(jì)算復(fù)雜度為O(Nk),最多需要的運(yùn)算次數(shù)為+…+;Δ-鄰域超圖的計(jì)算復(fù)雜度為O(N),最多需要的運(yùn)算次數(shù)為。

圖2給出了幾種建模方式計(jì)算復(fù)雜度的比較結(jié)果?？梢钥闯?所有建模方式的運(yùn)算次數(shù)都隨著小區(qū)個(gè)數(shù)N的增加而增加。超圖模型的計(jì)算復(fù)雜度為指數(shù)時(shí)間的,其增加速度最快;Δ-鄰域(包括1-鄰域和2-鄰域)超圖模型的計(jì)算復(fù)雜度為線性時(shí)間的,其增加速度最慢。在小區(qū)個(gè)數(shù)較少時(shí),k-超圖(包括3-超圖和4-超圖)模型所需要的運(yùn)算次數(shù)小于Δ-鄰域超圖模型;隨著小區(qū)個(gè)數(shù)的增多,其運(yùn)算次數(shù)逐漸超過了Δ-鄰域超圖模型。

圖2 幾種建模方式的計(jì)算復(fù)雜度比較結(jié)果Fig.2 Comparison of computation complexity of different modeling methods

2.2 模型精確度的比較

為了比較幾種建模方式的精確度,此處考察在不同模型中每個(gè)小區(qū)所屬于的超邊個(gè)數(shù)。一般超圖模型能夠完整反映小區(qū)之間的干擾關(guān)系,故此每個(gè)小區(qū)所屬于的超邊個(gè)數(shù)最多;其它模型會(huì)忽略一些干擾以換取計(jì)算復(fù)雜度的降低,故此每個(gè)小區(qū)所屬于的超邊個(gè)數(shù)可能會(huì)小于一般超圖。模型中每個(gè)小區(qū)所屬于的超邊個(gè)數(shù)越接近一般超圖模型,該模型的精確度就越高;反之,精確度就越低。

假設(shè)網(wǎng)絡(luò)中的小區(qū)個(gè)數(shù)是無窮多的(或者說服務(wù)區(qū)域是無限大的),此時(shí)小區(qū)之間的關(guān)系是對(duì)等的。表1顯示了在不同信干比閾值下,不同模型中每個(gè)小區(qū)所屬于的超邊個(gè)數(shù)的比較結(jié)果。表中第一行給出了不同的信干比閾值;第二行給出了一般超圖模型中每個(gè)小區(qū)所屬于的超邊個(gè)數(shù);后幾行給出了其它模型中每個(gè)小區(qū)所屬于的超邊個(gè)數(shù)與一般超圖模型中的差值。由表1可以看出,2-鄰域超圖模型的精確度最高,4-超圖模型的精確度次之,而沖突圖模型的精確度最低。

3 結(jié) 語

本文給出了一種用來描述基于頻分多址技術(shù)的無線蜂窩網(wǎng)中小區(qū)之間干擾的Δ-鄰域超圖模型。該模型與k-超圖類似,都在一般超圖模型的基礎(chǔ)上,以降低精確度為代價(jià)來換取計(jì)算復(fù)雜性的降低。通過性能分析結(jié)果可以看出,與3-超圖和4-超圖模型相比,2-鄰域超圖模型可以在較低的計(jì)算復(fù)雜度下獲得與一般超圖相當(dāng)?shù)哪Ｐ途_度。故此,Δ-鄰域超圖模型是一種性能良好的建模方法。本模型只是一般超圖模型的一種近似,如何設(shè)計(jì)更高精確度的具有多項(xiàng)式時(shí)間的信道重用模型,是需要進(jìn)一步研究的內(nèi)容。

表1 在各種模型中每個(gè)小區(qū)所屬于的超邊個(gè)數(shù)的比較結(jié)果Table 1 Comparison of hyperedges that each cell belonging to in different modeling methods

[1] 張翠英,葛萬成.蜂窩系統(tǒng)中分布式空域基站協(xié)作的仿真研究[J].通信技術(shù),2013,46(12):11-14.

ZHANG C.Y,GE W.C.,Simulation of Distributed Base-Station Collaboration in Cellular System[J], Communications Technology,2013,46(12),11-14.

[2] KATZELA I,NAGHSHINEH M.Channel Assignment Schemes for Cellular Mobile Telecommunication Systems:A Comprehensive Survey[J].IEEE Communications Surveys&Tutorials,2000,3(02),10-31.

[3] SARKAR S,SIVARAJAN K N,Hypergraph Models for Cellular Mobile Communication Systems[J].IEEE Transactions on Vehicular Technology,1998,47(02), 460-471.

[4] LI Q,KIM G,NEGI R.Maximal Scheduling in a Hypergraph Model for Wireless Networks[C]//IEEE International Conference on Communications 2008.Beijing: IEEE,2008:3853-3857.

[5] LI Q,NEGI R.Maximal Scheduling in Wireless Ad Hoc Networks With Hypergraph Interference Models[J]. IEEE Transactions on Vehicular Technology,2012, 61(01):297-310.

YUAN Jun-ling(1980-),male.Ph.D., lecturer,mainly engaged in optical communications and wireless communications..

李旭紅(1980—),女,碩士,講師,主要研究方向?yàn)樾畔⑻幚?

LI Xu-hong(1980-),female,M.Sci.,lecturer,majoring in information processing.

楊麗華(1978—),女,碩士,講師,主要研究方向?yàn)榇鷶?shù)圖論。

YANG Li-hua(1978-),female,M.Sci.,lecturer,majoring in algebraic graph theory.

A Δ-Neighborhood-Hypergraphy-based Channle Reuse Model for Wireless Cellular Networks

YUAN Jun-ling1,LI Xu-hong,YANG Li-hua2
(1.School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou Helan 450001,China; 2.School of Science,Zhongyuan University of Technology,Zhengzhou Helan 450007,China)

Channel reuse problem is one of the key technologies for FDMA-based wireless cellular networks,and it determines the transmission efficiency of channels.The problem is traditionally modeled as a conflict graph.Since a conflict graph just considers the interference between two cells,it cannot show the interferences among several cells.For overcoming this defect,the hypergraph model is additionally used to express the problem.Unfortunately,the modeling time is exponential.To reduce the computational complexity,a Δ-neighborhood hypergraph model is designed for the problem in this paper.The results of performance analysis show that the proposed model cannot only be completed in polynomial time,but also adequately express the interferences among several cells.

wireless cellular networks,channel reuse,hypergraph,Δ-neighborhood hypergraph

TN929.5

A

1002-0802(2014)08-0896-04

10.3969/j.issn.1002-0802.2014.08.011

袁俊嶺(1980—),男,博士,講師,主要研究方向?yàn)楣馔ㄐ拧o線通信;

2014-04-23;

2014-06-13 Received date：2014-04-23;Revised date：2014-06-13

鄭州輕工業(yè)學(xué)院博士科研基金項(xiàng)目(No.2013BSJJ048);國(guó)家自然科學(xué)基金項(xiàng)目(No.61309033)

Foundation Item:Doctoral Foundation of Zhengzhou University of Light Industry(No.2013BSJJ048),National Science Foundation of China (No.61309033)