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

袁俊嶺,李旭紅,楊麗華

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

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

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

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

信道重用問題是基于頻分多址技術的無線蜂窩網絡中的一項關鍵技術,它關系到信道的傳輸效率,傳統的方式是用沖突圖模型來表示該問題。但是,由于沖突圖模型中只考慮了兩個小區之間的干擾,無法反映多個小區之間干擾的情況,又有人用超圖模型來描述該問題。超圖的建模為指數時間的,為了降低建模的計算復雜度,將該問題描述為Δ-鄰域超圖模型。性能分析結果表明,該模型既可以在多項式時間內完成建模,又可以充分反映多個小區之間的干擾關系。

無線蜂窩網 信道重用 超圖 Δ-鄰域超圖

0 引 言

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

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

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

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

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

1 Δ-鄰域超圖模型

1.1 小區之間的干擾

在無線網絡中,若發射機與接收機之間的距離為d,發射功率為PT,則接收功率PR與PT·d-α成正比,其中α為3到5之間的常數。假設網絡中共有K個小區共用一個信道,在不考慮背景噪聲的情況下,其中一個小區k0中的接收機接收到的信干比為[2,5]:

式中,dk為該接收機到第k個小區中發射機的距離。系統通常會有一個保證通信質量的最小信干比閾值,閾值的大小與系統的編碼和調制方式、以及解碼和解調方式有關。只有接收機接收到的信干比不小于給定閾值時,才能保證正常通信。

由于信號功率隨著傳輸距離的增加而快速衰減,故此當兩個小區之間的距離超過一定距離之時,它們之間的干擾會變得非常小。基于這種觀察,在建模時可以只考慮一個小區周圍一定距離內的小區對它的干擾,Δ-鄰域超圖的概念就是基于這種考慮而提出的。

1.2 小區的鄰域

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

圖1 由37個小區組成的無線蜂窩網Fig.1 Cellular network composed of 37 cells

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

例如在圖1中,小區1的1-鄰域為{1,2,3,4, 5,6,7},1.5-鄰域與1-鄰域完全相同;-鄰域為{1,2,3,4,5,6,7,9,11,13,15,17,19};而2-鄰域中則包含編號從1到19的所有小區。可以看出,隨著Δ的增加,一個小區的Δ-鄰域中所包含的小區個數是階梯增加的。

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

定義2：對于一個超圖H,若其中任何一個超邊e中的任何兩個節點之間的距離都不超過2Δ,則稱超圖H是一個Δ-鄰域超圖。

在構建Δ-鄰域超圖時,首先需要針對每個小區尋找其Δ-鄰域,然后在該鄰域內尋找構成超邊的小區集合。假設網絡中共有N個小區,記所有小區的集合為S={n1,n2,…,nN};假設通信系統的信干比閾值為SIRmin。構建Δ-鄰域超圖的具體步驟如下:

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

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

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

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

2 性能比較

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

2.1 計算復雜度的比較

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

圖2給出了幾種建模方式計算復雜度的比較結果。可以看出,所有建模方式的運算次數都隨著小區個數N的增加而增加。超圖模型的計算復雜度為指數時間的,其增加速度最快;Δ-鄰域(包括1-鄰域和2-鄰域)超圖模型的計算復雜度為線性時間的,其增加速度最慢。在小區個數較少時,k-超圖(包括3-超圖和4-超圖)模型所需要的運算次數小于Δ-鄰域超圖模型;隨著小區個數的增多,其運算次數逐漸超過了Δ-鄰域超圖模型。

圖2 幾種建模方式的計算復雜度比較結果Fig.2 Comparison of computation complexity of different modeling methods

2.2 模型精確度的比較

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

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

3 結 語

本文給出了一種用來描述基于頻分多址技術的無線蜂窩網中小區之間干擾的Δ-鄰域超圖模型。該模型與k-超圖類似,都在一般超圖模型的基礎上,以降低精確度為代價來換取計算復雜性的降低。通過性能分析結果可以看出,與3-超圖和4-超圖模型相比,2-鄰域超圖模型可以在較低的計算復雜度下獲得與一般超圖相當的模型精確度。故此,Δ-鄰域超圖模型是一種性能良好的建模方法。本模型只是一般超圖模型的一種近似,如何設計更高精確度的具有多項式時間的信道重用模型,是需要進一步研究的內容。

表1 在各種模型中每個小區所屬于的超邊個數的比較結果Table 1 Comparison of hyperedges that each cell belonging to in different modeling methods

[1] 張翠英,葛萬成.蜂窩系統中分布式空域基站協作的仿真研究[J].通信技術,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—),女,碩士,講師,主要研究方向為信息處理;

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

楊麗華(1978—),女,碩士,講師,主要研究方向為代數圖論。

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—),男,博士,講師,主要研究方向為光通信、無線通信;

2014-04-23;

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

鄭州輕工業學院博士科研基金項目(No.2013BSJJ048);國家自然科學基金項目(No.61309033)

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