⃝⃝可在www.sciencedirect.com在线获取ScienceDirectICT Express 3（2017）38www.elsevier.com/locate/icte最小化色数的频率和极化联合分配古邦宏，H.Birkan Yilmaza，Chan-Byoung Chaea，Chang，Sung-Ho Parkb，Hwi-Sung Parkc，Jae-Hyun Hamc，a大韩民国延世大学延世融合技术研究所综合技术学院bOpen SNS，大韩c大韩民国国防部各机构接收日期：2016年7月21日;接受日期：2016年2016年8月21日在线发布摘要在这封信中，我们提出了基于图论的算法，用于在基于集群的战术通信环境中联合分配频率和天线极化（例如，军事通信）。除了考虑频率分配问题（这是一个NP难问题），我们还考虑极化分配问题。一个实际的天线和三维射线跟踪为基础的模拟器被用来测量的干扰。我们表明，所建议的mixistics是接近最佳的色彩和他们的低复杂性，使他们适合于实际使用。c2016韩国通信信息科学研究所。出版社：Elsevier B.V.这是一篇开放获取的文章，CC BY-NC-ND许可证（http：//creativecommons. org/licenses/by-nc-nd/4. 0/）。关键词：图论;频率分配问题;极化1. 介绍由于频谱是一种稀缺且宝贵的资源，因此最大化地利用无线电资源是频率分配问题（FAP）的目标。为了优化FAP的这样一个目标，一个众所周知的工具是图论[1]。图论中一个熟悉的话题是确定图最小化色的任务是一个NP困难问题[1]。在文献中，已经为FAP设计了不同的次优算法，包括贪婪和禁忌搜索[2，3]。作者在[4，5]中考虑了现实的天线方向图和滤波技术。在通信*通讯作者。电子邮件地址：harpeng7675@yonsei.ac.kr（B.- H.yonsei.ac.kr（H.B. Yilmaz），cbchae@yonsei.ac.kr（C.- B. Chae），shpark@opensns.co.kr（S.- H. Park），7hwisung7@add.re.kr（H.-S. Park），mjhham@add.re.kr（J.- H. 火腿）。同行评审由韩国通信信息科学研究所负责。这篇论文已经由教授处理许俊链接.分配给干扰设备的频率必须充分分离以减轻干扰;因此，减少使用频率的数量受到干扰约束的限制。文献还没有考虑到只有频率，但很少到极化。通过采用如[6]中的双极化天线，设备可以选择天线的垂直或水平极化。当收发器使用不同的极化时，与使用相同的极化相比，可能发生额外的信号衰减。因此，我们必须设计一种自适应和时间有效的算法来分配频率和极化。在这封信中，我们提出了基于图着色的次优算法，该算法在合理的时间内联合分配频率和极化。我们证明，所提出的算法是接近最佳的（在频率的数量），使用解析推导的下限。2. 系统模型Topology.目标环境是实际设置，其中通信节点使用实现的天线并且分布在实际地图上，如图1所示。的http://dx.doi.org/10.1016/j.icte.2016.08.0042405-9595/c2016韩国通信信息科学研究所。Elsevier B. V.的出版服务。这是CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4. 0/）。B.- H. Koo等人/ICT Express 3（2017）3839×P=×一L=：→=：→==−=(a) 天线。（b）基于3D射线跟踪的模拟器的顶视图(c)基于3D光线跟踪的模拟器的前视图Fig. 1.实际天线方向图和目标环境，包括实际地图上的精确位置和3D路径剖面。通信设备在100km × 100km的地图上以集群的形式分布。每个群集最多包含四个设备，并且每个设备与不同群集中的另一个节点只有一个通信链路;设备可以执行双向通信。通信距离限制为20 km。假设节点使用相同的发射功率（1W），并且天线指向它们的对以最大化天线增益。干扰测量。为了评估所提出的算法，我们利用真实和人工情况下的干涉图。对于现实场景，我们考虑了20、50和200个节点的情况。考虑天线方向图、频率间隔、地理数据、气候和波传播路径轮廓，使用3D射线追踪来测量功率衰减。3-D射线追踪利用我们自己实现的天线，如图1（a）所示，以及节点的确切位置，如图1（b）所示（对于50个节点的情况）。每个天线有两个有效的极化垂直和水平，额外的功率衰减时，实现分配的天线极化是不同的。对于人工场景，我们在2D空间上生成了10个随机节点拓扑。大约240个节点内的80个集群产生超过100公里100公里大小的地图。发射信号在到达接收器之前经历来自线路损耗、天线滤波器和传播的衰减。如果接收功率大于接收器灵敏度的水平，则必须通过分离频率和极化来衰减间隙它可以通过（1）获得，并定义为设备之间的干扰。X= max （ P + A − PL （ f ， d ） − L − T， 0 ） 。（一）由于物理距离PL（ f， d）引起的功率衰减遵循ITU P.525模型[7]，该模型是发射频率f和距离d。天线增益由测量的天线方向图确定。频率和偏振分离的衰减分别通过净滤波器鉴别（NFD）[8]和交叉偏振鉴别（XPD）的测量获得。后者被假定为30dB的恒定值。每个发射器和接收器的线路损耗为3 dB;接收器灵敏度水平为−70 dBm。图构造。干扰图G（ V， E）由顶点V的集合和边矩阵E组成，其中顶点V的元素对应于通信链路，边矩阵E指示通信链路之间的干扰（即，顶点节点）。从链路-i到链路-j的干扰被定义为从链路-i发射的链路-j处的接收功率。为了确保图是无向的，Eij和Eji的值被取为链路-i和链路-j之间的相互干扰的最大值。问题定义。我们首先分配极化（即，变换输入图形）并继续频率分配。极化分配函数P G GP（ VP， EP）将垂直或水平极化分配给V中的每个节点。干涉元件保持恒定（即， 当VPi和VPj具有相同的极化时，EPij Eij）;否则，它是EPij Eij30。在设置极化之后，频率分配函数A GP GA（VA，EA）将来自所有频带F的集合的频率分配给考虑更新的GP的链路。VA的第i个元素包含链路-i的分配信息，EAij表示最终分配后链路之间的干扰。我们将fi定义为F中的第i个元素，这在物理上表明该频带的中心频率为fi。频带具有相同的带宽，并且相邻元件的中心相等地分开。40B.- H. Koo等人/ICT Express 3（2017）38=：→2≥22图二.利用极化来实现减少数量的示例使用的频率。由于XPD减少10，允许节点1和2在双极化情况下使用相同的与单一情况相比，这分配问题的目标是最小化分配的频率的数量，其中每个通信链路被分配一个极化和一个频带，使得任何两个链路不会相互干扰。极化和频率可以利用如图2中所指示的约束来联合管理，其中在频率索引方面的XPD由10给出，使得设备1和2能够使用具有分离的极化的相同频率。为了公式化联合指派问题，我们定义J 一P作为频率和极化分配函数A和P的合成函数。最后的作业形式为J G GJ，并附有作业信息。目标是使频带的数量在图论中，一个图的色数是使顶点着色所需的最小颜色数，使得没有两个相邻的顶点具有相同的颜色;它通常用χ（G）表示。由于理论值不能有效地 获 得 ， 我 们 定 义 了 一 个 实 用 的 色 函 数 的 转 换 图 χ（GJ），计数的唯一频率的数量。优化问题旨在确定在满足干扰约束的同时最小化χη（J（ G））的分配函数J3. 提算法贪婪分配函数AH（参考实现）按节点的度、边权重和索引号连续地对节点进行排序。排序后，它将最小可用频率分配给节点，避免干扰现有的分配。 图形顶点着色问题，与FAP密切相关，考虑连接的节点是否被分配到不同的颜色（FAP考虑它们分离的程度）。基于着色的贪婪分配AC遵循相同的顺序，并将颜色分配给节点。在着色之后，它按照颜色索引对节点进行排序并分配频率;但是，这一次必须将相同的频带分配给相同颜色的节点。基于着色的算法保证较低的色数。基于团着色的贪婪分配AQ的功能类似于AC;但是，它首先对最大团成员着色。基于（2）的直觉，我们能达到的最好结果是最大团大小的一半，极化函数PQ以类似于AQ的方式分配极化。它像在AQ中一样为节点着色，并识别颜色元素之间的匹配[9]。匹配被定义为一对两种颜色，使得颜色之间的最大干扰小于30 dB。颜色A和B之间的干扰表示A色节点和B色节点之间的最大干扰。组成匹配的一对颜色表示当偏振分离时允许使用相同频率的两组节点，这减少了全色数。在确定最大匹配之后，该函数将垂直或水平分配给每个成对的颜色并统一颜色。如果多个颜色仍然存在，并且不再组成匹配，则将垂直分配给其余部分。如果图中有完美匹配，则可以将数量减少到最小。因为赋值依赖于给节点着色的方法，我们可以在导出AC的着色顺序后定义PC。4. 结果和最优性下限。图G的最大团的大小通常表示为w（G），并且是χ（G）的下界。它们相等当且仅当一个图G是完美图;判定G是否是完美图是NP-困难的。然而，确定w（G）值确实为解决分配问题提供了有意义的见解。最大团搜索提供的下界接近基于给团成员分配优先级的算法的色数。如果我们假设具有分离的极化的节点之间没有干扰，那么我们可以将G视为两个分离的图GV和GH的并集，使得每个图都包含具有相同极化的节点。因此，χ（P（ G））1χ（G）成立。另一个不平等来自集团概念。如前所述，图G的最大团的大小通常表示为w（G），并且是χ（G）的下界。而它是NP难枚举的 所有可能的最大团，有一个更简单的方法来确定一个图是否有大小为k的团[10]。我们结合两个不等式，得到χ∈（J（G））≥ χ（P（G））≥111χ（G）∈≥ 111w（G）∈.（二）B.- H. Koo等人/ICT Express 3（2017）3841表1单极化算法的结果。#Vw（G） X（JH（G）X（JCH（G）XJQH（G）1238751128079224468967072324486114908642428011286925230861168786表2频率和极化联合分配的结果。#V算法χ（·）1w（G）21238JQ40 382244JC36 343244JQ45 434242JC43 405230JQ48 43结果我们首先在人工案例上执行算法，因为不同案例的算法可用于比较。 总算法J是频率分配算法A和极化分配P的组合。我们将JH表示为AH和默认极化分配P H的组合，该默认极化分配PH将垂直分配给所有节点。符号JCH和JQH表示AC和AQ与PH的组合。PC的AC用JC表示，PQ的AQ用JQ表示。第一种算法JH是不考虑极化的贪婪分配算法。很明显，基于着色的贪婪算法在色度方面优于参考算法。表1中的结果证实了这一点。考虑到这封信单极化算法的下界为w（G）。这两种基于着色的算法表现出接近最佳的性能。无论是基于贪婪着色的JCH还是基于团着色的JQH都没有显着的优势;然而，对于JQH占主导地位的情况，它们都设法实现了最优解，如案例3和案例5所示。对于联合分配算法，我们提出了一种联合算法，该算法源于针对每种情况的改进的着色算法方法（例如，拓扑情况1）。表2的第二列表示选择了什么样的着色方法，并且随后的结果平行呈现。通过将表2的第三列与表1中的相关结果进行比较，我们可以看到，实际上一半的单极化结果是通过联合分配极化实现的。实际测量数据表明，由于精心选择的位置，消除干扰的优越性能。实际天线优于分析天线的理论天线退化到其最低能力。基于着色的算法在贪婪分配和极化联合分配中占主导地位，表3真实数据的结果。频率表示与单一分配相比的优点，如表3所示。5. 结论我们提出了三种频率分配算法：贪婪AH算法、基于着色的贪婪AC算法和基于团着色的AQ算法。本文还提出了一种利用着色后的匹配算法得到的极化算法，不同的着色方法得到不同的极化算法，分别用PC和PQ表示。所有提出的算法都是贪婪次优算法，在MATLAB上执行不超过一分钟。在真实地图上建立了一个基于簇的分布模型来描述战术拓扑。由于频谱效率是FAP的关键性能，因此我们选择最小化使用频率的数量。我们提出了联合分配算法来分配极化和频率，同时考虑到不同极化提供的额外分离。测量数据表明，极化算法也表现出改进。在人为产生的恶化环境中，基于着色的方法明显优于贪婪算法，偶尔基于团着色的算法也能得到最优解，进一步考虑极化分配问题。基于匹配算法的极化分配提供了单独FAP的最小解的近一半，这意味着联合分配算法有效地降低了客观成本值（即，色数）。我们未来的工作包括联合考虑频率/极化分配和采用大规模MIMO系统[11引用[1] 帕 达 洛 斯 湖 Pitsoulis ， NonlinearAssignmentProblems ：Algorithmsand Applications，Vol. 7，Springer，2013。[2] K.I. Aardal，S.P.M. Van Hocker，A.M.C.A.科斯特角Mannino，A. 李志华，频率分配问题的数学模型与求解方法，北京：计算机科学出版社。第153（1）（2007）号决议第79-129段。[3] P. Galinier，M. Gendreau，P. Soriano，S. Bisaillon，通过局部搜索和禁忌求解具有极化的频率分配问题，4 OR 3 1（2005）59-78。[4] B.- H. 古永锵耶尔马兹角B. Chae，H.- S.帕克，J. - H.帕克，P.S.-H、具有实际干扰约束的频率分配问题的启发式，Proc. IEEE Int.Conf. Comm.（ICC）（2016）。[5] B.- H. Koo，C.- B. Chae，H.- S.帕克，J. - H. Ham，S. H. Park，Anovelfrequencyallocationalgorithmforlimitedradioresourceenvironments，KICS Letter 40（9）（2015）1719-1721.[6] T. 哦，耶。G. Lim，C.-B. Chae，Y.李，双极化缝隙天线与高交叉极化歧视室内小型MIMO系统，IEEE蚂蚁。和Wireless Prop. Letters14（2）（2015）374-377。[7] ITU-R建议书P.525-2，自由空间衰减的计算（1994年）。VX（JH（ G））算法χ（·）2001年w（G）2002年507JQ4220014JQ6342B.- H. Koo等人/ICT Express 3（2017）38[8] ETSI TR 101 854 ， Derivation of receiver interference parametersuseful for planning fixed service point-to-point systems operatingdifferent equipment classes and/or capacities（2005）.[9] A.K. 南迪范文，编码与匹配问题中的应用定理，电子学报。26（23）（1990）1928-1930。[10] N. 莫达尼湾Dey，稀疏图中的大最大团枚举，ACMConference on Information and Knowledge Management，2008，pp. 1377 -1378年。[11] M.S. Sim，J. Park，C.- B. Chae，R.W.小希斯，相关大规模MIMO系统的压缩信道反馈，IEEE/KICS Jour. Comm. Networks 18（1）（2016）95-104.[12] Y.-- G. Lim，C.- B. Chae，G.Caire，小区边界用户的大规模MIMO性能分析，IEEE Trans.Wireless Commun。14（12）（2016）6827-6842。[13] C.- B. 蔡岛Hwang，R.W.小希斯诉Tarokh，干扰感知-多小区系统中的协调波束成形，IEEE Trans.WirelessCommun. 11（10）（2012）3692
我的内容管理
展开
