无线蜂窝网中基于Δ-邻域超图的信道重用模型*

2014-02-17袁俊岭李旭红杨丽华

通信技术 2014年8期

关键词：精确度邻域蜂窝

袁俊岭,李旭红,杨丽华

(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

1002-0802(2014)08-0896-04

10.3969/j.issn.1002-0802.2014.08.011