第３２卷第１期 ２０１４年１月 应用科学学报 Ｖｏ１．３２ Ｎ０．１ Ｊａｎ．２Ｏ１４ ＪＯＵＲＮＡＬ ＯＦ ＡＰＰＬＩＥＤ ＳＣＩＥＮＣＥＳ＿——Ｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ ＤＯｈ １０．３９６９／ｊ．ｉｓｓｎ．０２５５—８２９７．２０１４．０１．００１ ＳＣ—ＦＤＭＡ中继系统中最大化容量的资源分配 朱宇， 张梦莹 复旦大学通信科学与工程系，上海２００４３３ 摘 要：针对单载波频分￣：ｋｌｋ（ｓｉｎｇｌｅ ｃａｒｒｉｅｒ Ｋｅｑｕｅｎｃｙ ｄｉｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃｃｅｓｓ，ＳＣ—ＦＤＭＡ）系统的子信道相邻 ，研究了适用于ＳＣ—ＦＤＭＡ中继系统中最大化容量的资源分配算法，提出将该资源分配问题重构为一个集合 划分问题，并借助运筹学中的相关算法求出最优解．为降低最优资源分配算法的计算复杂度，还提出了一种采用贪 婪试探法的次优算法．仿真结果表明，在放大转发和解码转发中继协助的ＳＣ—ＦＤＭＡ系统中，最优算法的频谱利用 率显著高于随机算法，而贪婪次优算法能达到接近最优算法的性能，并且具有较低的计算复杂度． 关键词：３ＧＰＰ ＬＴＥ：单载波频分多址；资源分配；协作中继；集合划分问题；贪婪算法 中图分类号：ＴＮ９１４．５１，ＴＮ９２５ 文章编号：０２５５—８２９７（２０１４）０１—０００１—０６ Ｒｅｓｏｕｒｃｅ Ａｌｌｏｃａｔｉｏｎ ｆｏｒ Ｃａｐａｃｉｔｙ—Ｍａｘｉｍｉｚａｔｉｏｎ ｉｎ ＳＣ—ＦＤＭＡ Ｒｅｌａｙ Ｓｙｓｔｅｍｓ ＺＨＵ Ｙｕ， ＺＨＡＮＧ Ｍｅｎｇ—ｙｉｎｇ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｆｕｄａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０ｏ４３３，Ｃｈｉｎａ Ａｂｓｔｒａｃｔ：Ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｐｒｏｐｏｓｅｄ ｔｏ ｍａｘｉｍｉｚｅ ｔｈｅ ｃａｐａｃｉｔｙ ｏｆ ｓｉｎｇｌｅ ｃａｒｒｉｅｒ Ｋｅｑｕｅｎｃｙ ｄｉｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃｃｅｓｓ（ＳＣ—ＦＤＭＡ）ｒｅｌａｙ ｓｙｓｔｅｍｓ．Ｔａｋｉｎｇ ｉｎｔｏ ａｃｃｏｕｎｔ ｔｈｅ ｓｕｂｃｈａｎｎｅｌ ａｄｊａｃｅｎｃｙ ｒｅｓｔｒｉｃｔｉｏｎ ｏｆ ＳＣ—ＦＤＭＡ，ａｎ ｏｐｔｉｍａｌ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｅｓｅｎｔｅｄ ｔｏ ｒｅｆｏｒｍｕｌａｔｅ ｔｈｉｓ ｐｒｏｂｌｅｍ ａｓ ａ ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇ ｐｒｏｂｌｅｍ． Ｂｙ ｕｓｉｎｇ ｔｈｅ ｒｅｌｅｖａｎｔ ｍｅｔｈｏｄｓ ｉｎ ｏｐｅｒａｔｉｏｎｓ ｒｅｓｅａｒｃｈ，ｔｈｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｃａｎ ｂｅ ｏｂｔａｉｎｅｄ．Ａ ｓｕｂｏｐｔｉｍａｌ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｇｒｅｅｄｙ ｈｅｕｒｉｓｔｉｃ ｔｈｉｎｋｉｎｇ ｉｓ ａｌｓｏ ｐｒｏｐｏｓｅｄ ｔｏ ｒｅｄｕｃｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｏｐｔｉｍａｌ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ．ｉｎ ａｍｐｌｉｆｙ—ａｎｄ—ｆｏｒｗａｒｄ ａｎｄ ｄｅｃｏｄｅ—ａｎｄ—ｆｏｒｗａｒｄ ｒｅｌａｙ—ａｓｓｉｓｔｅｄ ＳＣ—ＦＤＭＡ ｓｙｓｔｅｍｓ，ｓｐｅｃｔｒａｌ ｅｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｏｐｔｉｆｍａｌ ａｌｇｏｒｉｔｈｍ ｉｓ ｍｕｃｈ ｈｉｇｈｅｒ ｔｈａｎ ｔｈａｔ ｏｆ ｔｈｅ ｒａｎｄｏｍ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｍｕｃｈ ｌｏｗｅｒ ｃｏｍｐｌｅｘｉｔｙ ｐｅｒｆｏｒｍｓ ｑｕｉｔｅ ｃｌｏｓｅ ｔｏ ｔｈｅ ｏｐｔｉｍａｌ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：３ＧＰＰ—ＬＴＥ，ｓｉｎｇｌｅ ｃａｒｒｉｅｒ ｆｒｅｑｕｅｎｃｙ ｄｉｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃｃｅｓｓ（ＳＣ—ＦＤＭＡ），ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ， ｃｏｏｐｅｒａｔｉｖｅ ｒｅｌａｙ，ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇ ｐｒｏｂｌｅｍ，ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ 单载波频分多址ｆｓｉｎｇｌｅ ｃａｒｒｉｅｒ ｆｒｅｑｕｅｎｃｙ ｄｉ— 另外，在无线网络中利用中继进行传输能够有效 ｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃｃｅｓｓ，ＳＣ—ＦＤＭＡ）是除正交频分 多址ｆｏｒｔｈｏｇｏｎａｌ ｆｒｅｑｕｅｎｃｙ ｄｉｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃ— 提高系统容量及可靠性［３Ｊ＿常见的中继方式包括放大 转发（ａｍｐｌｉｆｙ—ａｎｄ—ｆｏｒｗａｒｄ，ＡＦ）和解码转发（ｄｅｃｏｄｅ— ａｎｄ—ｆｏｒｗａｒｄ，ＤＦ１．基于ＡＦ的中继站只是放大每个源 节点的信号并转发给目的节点；而基于ＤＦ的中继站 将接收到的信号进行解码并重新编码后再转发给目的 节点 ｃｅｓｓ，ＯＦＤＭＡ）之外的一种适用于宽带移动通信的 多址接入技术［１—２１．ＳＣ—ＦＤＭＡ采用单载波调制，发送 信号的功率峰均比较低［ ］，因此被第３代合作伙伴计 划一长期演进（３ｒｄ ｇｅｎｅｒａｔｉｏｎ ｐａｒｔｎｅｒｓｈｉｐ ｐｒｏｊｅｃｔ－ｌｏｎｇ ｔｅｒｍ ｅｖｏｌｕｔｉｏｎ，３ＧＰＰ—ＬＴＥ）以及ＬＴＥ—Ａｄｖａｎｃｅｄ标 准采纳为上行多址接入方案［２】＿ 收稿日期：２０１３—０６—１９； 修订日期：２０１３—０９—１０ 在中继协助的ＳＣ．ＦＤＭＡ系统中，采用灵活的资 源分配可以进一步提高系统容量，但用户只能分配到 基金项目：国家自然科学基金（Ｎｏ．６１２７１２２３）；国家重大科技专项基金（Ｎｏ．２０１２ＺＸ０３００１０１３—００４）资助 作者简介：朱宇，博士，副教授，研究方向：无线通信、移动通信，Ｅ—ｍａｉｌ：ｚｈｕｙｕ＠ｆｕｄａｎ．ｅｄｕ．ｃｎ ２ 应用科学学报 第３２卷 相邻的多个子信道，从而加大了资源分配问题的求解 １．２ ＡＦ中继系统容量 首先，用户ｍ将需要发射的Ｑ个信息符号 难度，且适用于０ＦＤＭＡ的技术［５］不能直接应用．文 献ｆ６１研究了ＡＦ中继协助ＳＣ ＦＤＭＡ系统中的子信 道分配方法，但仅适用于单用户系统，且并没有考虑 子信道相邻． 为在满足功率的情况下最大化系统容量，本 文提出将ＳＣ—ＦＤＭＡ中继系统的资源分配问题重构 为一个集合划分问题［７】．借助集合划分问题在运筹学 中的求解方法［７】，计算该资源分配问题的最优解．为 （０≤ｑ≤Ｑ一１）经过Ｑ点的归一化离散傅里叶变换 （ｄｉｓｃｒｅｔｅ Ｆｏｕｒｉｅｒ ｔｒａｎｓｆｏｒｍ，ＤＦＴ）到频域，即 Ｑ １ ∑ｑ＝０ 培＿，Ｊｑ。≤ｐ≤Ｑ—ｌ（１） ，然后，将这 个频率分量Ｓ 通过 ｆ信道分配 进一步降低最优资源分配算法的计算复杂度，还提出 了一 一种基于贪婪试探策略的次优算法．基于３ＧＰＰ— ＬＴＥ上行方案的仿真结果表明，在ＡＦ和ＤＦ中继协 助的ＳＣ—ＦＤＭＡ系统中，最优算法的频谱利用率大大 高于随机算法，而贪婪次优算法的性能接近最优算 法，还具有较低的计算复杂度． １ 系统模型 １．１ 中继协助的ＳＣ．ＦＤＭＡ系统模型 考虑采用ＳＣ—ＦＤＭＡ的多用户单扇区上行中继 网络 ８．假设扇区内共有Ｍ个用户，标识为集合 ／＝－ｋ｛１ …，ｍ，…，Ｍ｝，传输带宽Ｂ被正交地划分 为 个子信道，标识为集合 ＝．／－ｋ｛１，…，ｋ，…， ｝． 在集中式子信道分配ＳＣ—ＦＤＭＡ系统中有两个 ｆ信 道分配：１１排他性，即一个子信道最多只能分配 给一个用户；２）相邻性，即一个用户只能分配给相邻 的多个子信道． 系统的中继协助方式如图１所示．整个中继过程 分为两个时隙完成．在第１个时隙 中，用户ｍ发 射信息８ｍｆｍ＝１，… ），它们被基站和中继同时 接收．在第２个时隙 中，中继将接收到的信号转发 给基站，中继方式可以选择ＡＦ或者ＤＦ．假设各用户 与基站及ｒｆ１继理想同步，并且基站已知所有的信道状 态信息（ｃｈａｎｎｅｌ ｓｔａｔｅ ｉｎｆｏｒｍａｔｉｏｎ ＣＳＩ）． ｄ 用户 用户Ｍ 第１个时隙 １的传输 ……一 第２个时隙，，２的传输 图１ ＳＣ—ＦＤＭＡ中继系统 Ｆｉｇｕｒｅ １ ＳＣ—ＦＤＭＡ ｒｅｌａｙ ｓｙｓｔｅｍ 分别映射到正交的 （＞Ｑ）个频域ｒ信道之…．定义 为分配给用户ｍ的 信道集合，对于集中式子信 道分配ＳＣ—ＦＤＭＡ系统，集合中的子信道必须是相邻 的，于是可将子信道映射过程表示为 ㈤ ｎ （２） ： 【０， ｋ 式中， （．）为用户ｍ的子信道映射函数， ＝ （ｐ） 表示用户ｍ的第Ｐ个频率分量被映射到系统的第 个子信道上． 各频率分量经子信道映射后，冉通过一个 点 归一化反离散傅里叶变换ｆｉｎｖｅｒｓｅ ｄｉｓｃｒｅｔｅ Ｆｏｕｒｉｅｒ ｔｒａｎｓｆｏｒｍ ＩＤＦＴ１回到时域，即 Ｋ －１ ＝ 】ｅｊ跏，。≤ｎ≤Ⅳ一１（３） 在发送前，将数据块的最后一段符号重复插入到 整个数据块的前端作为循环前缀（ｃｙｃｌｉｃ ｐｒｅｆｉｘ，ＣＰ１， 以消除块间干扰并使数据块在传输过程ｒｆＪ与信道的线 性卷积可以被等效为循环卷积． 在第１个时隙 中，基站和中继接收到的时域 信号ＹＤ 和ｙＲ［ｎ］可以分别表示为 ＹＤ［ｎ］ ∑∑ ｈ Ｄ［１］ｓ ［（ｎ ｍ＝１ ｆ＝０ １）ｒｏｏｄ Ｎ］＋ＷＤ 几，Ｌ一１ ｙＲ［ｎ］ ∑∑ｘ／Ｇ￣ｍｈ Ｒｉｌｌｓ 【（礼 ｍ＝１ ７＝＝０ １）ｒｏｏｄ Ｎ］十ｗＲＩｎ］ 式中，ｆ．）ｍｏｄ Ｎ表示模Ｊ７ｖ运算； 为用户ｍ的信 号发射功率； Ｄ［ｆ］和ｈｍＲ＿ｆ］分别为用户ｍ和基站、 用户ｍ和中继之间第ｆ条路径的复路径增益，其中包 括大尺度和小尺度衰落的影响；ＷＤ 和ＷＲ 分别 是均值为０方差为 ０的加性高斯白噪声． 对时域信号ＹＤ 和蛐 进行Ｎ点ＤＦＴ处理 及频率分量抽取后，基站和中继接收到的用户ｍ在子 第１期 朱宇等：ＳＣ ＦＤＭＡ中继系统中最大化容量的资源分配 ３ 信道ｋ上的频域信号可以表示为 ｙｍＤ ｙｍＲ［ｋ］、 Ｄ 表示为 ｛Ｉ Ｄ ［叫＝ Ｄ［纠 ］＋ ］， ∈ （５） Ｉ Ｄ ＝ Ｈ，ｎＤ［ｋＪＳｍ［ｋ］＋ ｛Ｙ￣Ｒ［ｋ】＝ Ｒ ｓｍ ＋ ， ∈ （１１） Ｒ ＝ｖ／Ｐ－－￣ＨｍＲ［－ｋ］Ｓｍ［ｋ］＋ 一 式中， Ｄ 和ＨｍＲ［ｋ］分别是用户ｍ和基站、用 户ｍ和中继之间第 个子信道的信道增益；ＷＤ［ｋ］和 分别是基站和中继在第 个子信道上的噪声 分量． 同理，在第２个时隙 中，基站接收到的子信道 上的频域信号可以表示为 Ｄ ：Ｖ＠—．￣［ｋ］Ｐ—ｍＰＲＨＲＤ ＨｍＲ ＋ＷＤ［ ］， ∈ （６） 式中， 为中继的发射功率；ＨＲＤ［ｋ】为中继和基站 间第 个子信道的信道增益； 为中继在第ｋ个 子信道上的放大因子，可以表示为 ＝丽 丽＝ １ 式中，Ｅ（．）表示求数学期望；ＷＤ［ｋ］为基站在第ｋ个 子信道上的噪声分量，其均值为０，方差为 ＝０－２（ｇｍ［ｋ］ＰＲ ＩＨＲＤ ＋１） （８） 基站接收信号 Ｄ［ｋ］和 Ｄ 的信噪比（ｓｉｇｎａｌ ｔｏ ｎｏｉｓｅ ｒａｔｉｏ，ＳＮＲ）ｒｍＤ［ｋ］和Ｉ＇ＲＤ［ｋ］分别为 １，ＲＤ ＝ ｒ ［ ］＝ １ ｌｂ（１＋ 。 ＋ 。㈣ ＝ ＋鲁ｌ 删。 １＋ 。 ＰｍＰＲＩＨｍＲ［ｋ＋ＰＲＩＨ】】ｌ２ｌ ２ｍ Ｒ［ｋ］１２１ＨＲＤ ＨＲＤ ［ｋ］Ｉ２ Ｐｍｌ＋ ／＋２／（ １。） １．３ ＤＦ中继系统容量 类似于ＡＦ中继系统，本文可以推导出ＤＦ中继 系统的信道容量． ＤＦ中继会将接收到的信号进行解码并重新编码 后再转发，使中继的加性高斯白噪声得以去除，于是 可以将中继和基站在第尼个子信道上的频域接收信号 Ｉ Ｄ ＝￣ＲＨＲＤ［ｋ］Ｓｍ［ｋ］＋ 式中，ＷＤ 、ＷＲ［ｋ］、 的噪声功率均为盯 ． 在整个中继过程中，为了保证中继可以正确可靠 地解码信息，用户ｍ和中继之间第 个子信道的最大 信息速率为 ｒ 纠＝去ｌｂ（１＋Ｐ￣ ＩＨｍ ）（１２） 同理，在整个中继过程中，为了保证基站正确地 解码所有信息，用户？ＴＬ和基站间第 个子信道的最大 信息速率应为 ｒ 。［ ］＝ ｌ ｌｂ（１＋Ｐｍ Ｉｇ￣。［ ］Ｉ ＋ ｌ 。 ） （１３） 假设中继和基站都能够正确解码用户信息，那么 在整个系统中，用户ｍ在第 个子信道的信道容量为 ｒｍＲ［ｋ］和ｒ Ｄ［ｋ］之间的最小值［４】’即 ｒｍ ＝ｍｉｎ（ｒ Ｒ ｒｎｉｄ ） （１４） １．４ 中继协助的ＳＣ—ＦＤＭＡ资源分配问题 ＳＣ．ＦＤＭＡ系统的资源分配问题包括子信道分配 和功率分配，旨在最大化系统容量．由于本文着重研 究子信道分配问题，于是假设每个用户都使用最大允 许总功率 发射，且所有分配给同一个用户的子信 道发射功率相同，从而将该资源分配问题简化为决定 子信道分配 ，再加上排他性和相邻性，该问 题可以写成 ｛ ，…，ｍ Ｍ）∈ ａ ｘ、 ∑∑ｒ … ｓ．ｔ． ｎ ，＝ ，Ｖｍ≠ｍ ，ｆ０ｒ ｍ，ｍ ∈ （１５） 尸ｍ＝ ／ｌ ｌ，ｆｏｒ ｍ∈ 式中，ｒｍ 为用户ｍ在子信道尼上的容量，如式（１０） 和（１４）所示； 为所有遵循相邻的子信道分配 的集合；ｌ ｌ表示集合 中元素的数目． ２ ＳＣ．ＦＤＭＡ中继系统资源分配算法 ２．１ 最优资源分配算法 值得注意的是：式（１５）是一个非常复杂的组合优 化问题，若用穷举法遍历所有子信道分配模式的方法 显然不实际［１ｏ］，于是需要更有效的方法来解决这个问 ４ 应用科学学报 第３２卷 题．解决方法是将该问题重构为一个集合划分问题 ７Ｊ’ 其一般形式为 ｉｎａＸｃＴｘ 式中， ． 三｛ ∈ ： （ ，Ｊ）＝１｝表示用户ｍ采 １ ０ ０ ０ １ ０ ０ ０ １ ０ Ｏ ０ ０ ０ ０ ０ 用分配模式Ｊ时使用的子信道指标的集合；ｒ 『ｋ１表 示用户ｍ在子信道ｋ上的容量，ＡＦ中继方式对应 ｆ１６１ ｓ．ｔ．Ａｘ＝１０ 于式（１０），ＤＦ中继方式对应式（１４）．若以ｃ＝『Ｃ．ｃ１１， ０ Ｏ ０ １ Ｔ ＣＭ 就成为，ＪｆＩ表示权重向量，则需要最大化的目标函数 …，ｃ＿ｌ ：． １ ０ １ １ ０ １ ０ ０ Ｘｉ∈｛０，１｝，Ｖｉ 式中， 是由优化变量组成的长度为 的决策向量， 每个优化变量可以取值０或１；Ｃ为权重向量；Ａ为 接下来要决定的是 的约束矩阵，在式（１６） ０ ０ １ １ 中表示为Ａ．为了执行排他性子信道分配， １ １ １ ０ 只能选择一个第惫行为１的了信道分配模式，即 ｇ×Ｖ的约束矩阵，由０和１组成；１ …，１１ 是一 个由１组成的长度为ｇ的矢量，其中９既是的数 量，同时又是约束矩阵Ａ的行数．在对式ｆ１５］的转化 过程中，决策向量ｚ中的每个元素对应于一个具体的 子信道分配模式，而权重向量ｃ中的每个元素对应于 使用该子信道分配模式的用户容量．约束矩阵Ａ被用 于执行子信道的排他性． 刚开始转化时，首先为每个用户确定所有可行的 子信道分配模式．假设有Ｋ ４个子信道，Ｍ ２个用 户．对于一个具体的用户，由于子信道相邻，只 有少数可行的子信道分配模式．将分配给用户？Ｔｔ的子 信道标识为１，没有分配的标识为０，于是形成了用户 ｍ的子信道分配模式矩阵 ．这个矩阵的行对应于 子信道标识，列对应于子信道分配模式，例如 Ｖｍ∈ ｆ１７） 这个矩阵对于所有用户是相同的． 当多个子 信道分配给一个用户时，它们必须是相邻的ｆ如第 ６ １１列）．当… 个用户分配给叩（＞０）个子信道时，只 有 一（叩一１）种可能的分配，故列的总数为Ｊ＝１＋ ∑ １（Ｋ一（即一１））＝Ｋ。／２＋Ｋ／２＋１，在本例中是１１． 得到子信道分配模式矩阵后，将用户？Ｔｔ的每个子 信道分配模式与一一个二进制决策变量 ，∈｛０，１｝， Ｊ＝１，…， 关联，这表示子信道分配模式 被选 择与否．共有Ｍ个用户，可形成长度为Ｍ Ｘ Ｊ的 决策向量，标识为 ＝ｆ １，…， Ｍ］Ｔ，其中 ＝ ［Ｘ 一，Ｘｒ￣ ，Ｊ 然后把每个子信道分配模式与一个权重Ｃ ｊ关联，这表示当ｚ ．ｊ＝１，即采用子信道 分配模式 时，用户ｍ的信道容量和 ｃ哪＝∑ｒ （１８） ｋＥ ｍ ，∑ ：１∑ ∈／ｌ Ｘｍ，ｊ＝１，Ｖｋ∈ ，其中Ａｍ，０ １ １ １ 是 中行指标 ｆ子信道ｋ）为１的列指标（；子信道分配模 ｌ 式１的集合．这Ｋ个约束可以写成 除了 个排他性子信道分配约束外，还需要Ｍ 个约束保证 中有且仅有一个模式（列）可以被选 择，即∑ １ ｚ ，Ｊ＝１，Ｖｍ∈ ，则可将这Ｍ个约束 写成矩阵形式，即 １ ０ …０ １ ● ● ０ １ ’・ ： Ｘ２ ’． ０苫 ０ … ０苫 １ 合并式（１９）和（２０），可得这个问题的总约束矩阵为 ＵＭ １ ０ Ａ ｆ２１１ ● ： ０ １ 至此，可采用式（１６）、式（１８）、式（２１）将式（１５） 中的原始问题转换成一个普通的集合划分问题．集合 划分问题在运筹学中已得到广泛研究［ ］，可以直接使 用ＭＡＴＬＡＢ软件的内置函数“ｂｉｎｔｐｒｏｇ”求其最优 解．这个方法相对于穷举法，显著降低了找到最优解 的复杂度． ２．２ 贪婪次优算法 虽然最优算法得到的结果是最佳的，但要付出的 代价是在解集合划分问题时的计算复杂度．在计算资 源有限的情况下，贪婪次优算法简单得多，而且仍能 得到相当可观的结果． 贪婪算法的目的是要找到能使系统容量“上Ｊｔ 最 快”的分配，其基本处理流程是在每一～ 次迭代中把… 个子信道分配给一个用户，赢得分配的是能使系统容 第１期 朱宇等：ＳＣ—ＦＤＭＡ中继系统中最大化容量的资源分配 ５ 量的增量最大化的用户和子信道配对．贪婪次优算法 配一个资源块．假设所有用户都以１０ ｋｍ／ｈ的速度移 的伪代码如下． 输入： 、Ｋ、Ｏ－２、信道信息、功率 输出： ，Ｖｍ∈ 行 操作 １ ＝｛１，－一， ） ２ ＝ ，Ｖｍ∈ ３ ）： ，ｖｍ∈力 ４ ｗｈｉｌｅ少≠ ５ Ｖｍ∈／２ ６ Ｖ ∈ ｎ ７ Ａｃｒｅ，ｋ＝ ∑ ｒｍ ］一∑ｒｍ［ｋ ］ ∈ ｍＵｋ ｋ ∈ ｍ ８ （ｍ ， ）＝ａｒｇｍａｘ△ｃｍ． ９ ＝ Ｕ １０ ＝｛ｍｉｎ（ ）一１，ｍａｘ（ ．ｎ ）＋１）ｎ １１ ＝ｅ＼ｋ １２ ｅｎｄ 集合 表示在每次迭代中能够被分配的子信道， 因此当集合 为空时，算法终止．集合 表示用户 ｍ的子信道分配结果，蟛 表示每次迭代中用户ｍ 可以分配到的候选子信道指标的集合．对于从未分配 到子信道的用户而言， 中的所有子信道都可以分配 给该用户；但对于已经分配到一个或多个子信道的用 户而言，只有与已分配子信道相邻的子信道才可以分 配给该用户ｆ行ｌｏ）．在算法的主体ｆ行４ １２），对于所 有用户和每个用户的候选子信道，计算当候选子信道 被分配给用户ｍ时系统容量的增量△ｃ ． （行７）， 即当子信道 被分配给用户ｍ时的容量ｆ第１项）ｉｎ没 有分配时的原始容量ｆ第２项）的差值．能得到最大容 量增量的用户和子信道配对（ｍ ，ｋ ）赢得这一次的分 配（行８），相应地更新集合 和 （行９ １１）， 经 次迭代就能得到最终的子信道分配结果． ３ 仿真结果 考虑一个采用ＳＣ ＦＤＭＡ技术的多用户单扇区 上行中继网络．用户的最大发射功率为５ ｍＷ，系统带 宽为５ ＭＨｚ，噪声功率谱密度为－１６０ ｄＢｍ／Ｈｚ．载波 频率为２ ＧＨｚ，传输时间间隔（ｔｒａｎｓｍｉｔ ｔｉｍｅ ｉｎｔｅｒｖａｌ， ＴＴＩ）为１ ｍｓ．路径损耗指数为３．５，阴影损耗标准差 为８ ｄＢ［¨］．频率选择性信道模型为２０径的典型城市 信道模型［１２】．假设用户和中继的发射功率相同，系统 带宽被划分为Ｋ＝２４个子信道． 图２比较了在ＡＦ与ＤＦ中继协助通信情况下， 当用户数分别为５、１０、１５、２０时，各算法的频谱利用 率．比较的基准方案为随机资源分配算法，即将相等 数量的相邻子信道合并为资源块，每个用户被随机分 动，并且基站具有理想的ＣＳＩ．从图２中可以看出：无 论在哪种情况下，最优算法的频谱利用率最高，贪婪 算法略低于最优算法，而这两种算法的性能均显著优 于随机资源分配．而且随着用户数的增大，贪婪算法 与最优算法之间的差距逐渐缩小． ＩＮ ● ＿＿ｌ∞ 未 糌 旺 用户数目Ｍ 图２ ＡＦ与ＤＦ中继协助通信情况下的频谱利用率 Ｆｉｇｕｒｅ ２ Ｓｐｅｃｔｒａｌ ｅｆｉｆｃｉｅｎｃｙ ｉｎ ＡＦ ａｎｄ ＤＦ ｒｅｌａｙ—ａｓｓｉｓｔｅｄ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃａｓｅｓ 此外，从图２中也可以看出，相较于ＡＦ中继系 统，各算法在ＤＦ中继协助通信情况下的频谱利用率 较高．这是由于ＤＦ中继协助通信系统去除了中继产 生的加性高斯白噪声，提高了基站接收信号的信噪比． 考虑到时变信道和信道估计误差的影响，图３展 示了在非理想ＣＳＩ情况下，最优算法和贪婪算法在 ＡＦ与ＤＦ中继协助通信情况下的频谱利用率．用户数 目固定为ｌ０．信道的多普勒频率根据ＴＴＩ进行归～ 化处理［１３］．由于信道是时变的，基站估计的信道增益 不同于数据传输时的实际信道，其变化快慢的程度由 多普勒频率决定．类似于文献『１４１，基站估计的信道 增益Ｈ［ｋ］被建模为实际信道增益Ｈ［ｋ］加上一个随机 估计误差＜ ，其中Ｃ［ｋ］是一个均值为０、方差为 的同分布高斯变量．在仿真中考虑了两种信道估 计误差的方差，其中 ＝０（虚线）表示仅考虑多普勒 频率的影响， ２＝０．０１ ｆ实线）表示既考虑了多普勒频 率的影响，又考虑了信道估计误差的影响．从图３中 可以看出，在非理想ＣＳＩ的情况下最优算法和贪婪算 法的频谱利用率都相应降低，但降低的幅度并不明显． 在当前仿真环境中，假设实际传输与信道估计之间问 隔了一个ＴＴＩ，用户移动速度为１０ ｋｍ／ｈ，对应的归 一化多普勒频率为０．０１９，各算法的频谱利用率平均 降低了１．５％．通过信道预测等方法增加信道估计的精 确度，可以进一步缩小这一差距． ６ 应用科｝Ｎ ● 一｝∞ 毫 ｅ 辟 旺 归一化多普勒频率 图３非理想ＣＳＩ情况下的频谱利用率 Ｆｉｇｕｒｅ ３ Ｓｐｅｃｔｒａｌ ｅｆｆｉｃｉｅｎｃｙ ｗｉｔｈ ｉｍｐｅｒｆｅｃｔ ＣＳＩ 类似于文献『１０１的方法，通过使用ＭＡＴＬＡＢ软 件中的“ｔｉｃ—ｔｏｃ”函数对最优算法和贪婪算法的平均 计算时间进行统计，可以反映出它们的计算复杂度． 由表１可以看出，贪婪算法的计算复杂度约为最优算 法的１２％，但具有与最优资源分配算法相近的频谱利 用率，因此贪婪算法具有较高的工程应用价值． 表１ ＡＦ ＤＦ中继协助通信情况下的计算时间 Ｔａｂｌｅ １ Ｃｏｍｐｕｔａｔｉｏｎａｌ ｔｉｍｅ ｉｎ ＡＦ ａｎｄ ＤＦ ｒｅｌａｙ ａｓｓｉｓｔｅｄ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃａｓｅｓ ４ 结 语 本文研究了适用于ＳＣ—ＦＤＭＡ中继系统中最大 化容量的资源分配算法．基于运筹学中的集合划分 问题，推导了最优的ＳＣ—ＦＤＭＡ资源分配算法．借助 集合划分问题在运筹学中的求解方法，求得了该资 源分配的最优解，且其复杂度远低于穷举法．为进 一步降低资源分配算法的计算复杂度，还提出了一 种基于贪婪试探策略的次优算法．基于３ ＧＰＰ—ＬＴＥ ＿｝：行方案的仿真结果表明，在ＡＦ和ＤＦ中继协助的 ＳＣ—ＦＤＭＡ系统中，最优算法的频谱利用率显著高于 随机算法，贪婪次优算法的性能虽然略低于最优算 法，但具有较低的复杂度． 学学报 第３２卷 参考文献： Ｉ１ｌ ＭＹＵＮＧ Ｈ Ｇ，ＬＩＭ Ｊ，ＧＯＯＤＭＡＮ Ｄ Ｊ．Ｓｉｎｇｌｅ ｃａｒｒｉｅｒ ＦＤＭＡ ｆｏｒ ｕｐｌｉｎｋ ｗｉｒｅｌｅｓｓ ｔｒａｎｓｍｉｓｓｉｏｎ『Ｊ１．ＩＥＥＥ Ｖｅ— ｈｉｃｕｌａｒ Ｔｅｃｈｎｏｌｏｇｙ Ｍａｇａｚｉｎｅ，２００６，１ ｆ３１：３０—３８． １２Ｉ ３ＧＰＰ．Ｅｖｏｌｖｅｄ Ｕｎｉｖｅｒｓａｌ Ｔｅｒｒｅｓｔｒｉａｌ Ｒａｄｉｏ Ａｃ— ｃｅｓｓ （Ｅ—ＵＴＲＡ１．Ｆｕｒｔｈｅｒ ａｄｖａｎｃｅｍｅｎｔｓ ｆｏｒ Ｅ— ＵＴＲＡ ｐｈｙｓｉｃａｌ ｌａｙｅｒ ａｓｐｅｃｔｓ：ＴＲ ３６．８１４ Ｖ９．０．０ 【ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．３ｇｐｐ．ｏｒｇ ｆｔｐ ｓｐｅｃｓ ｈｔＨ１ｌ— ｉｎｆｏ／３６８１４．ｈｔｍ．２０１０一Ｏ３—３Ｏ． 【３】ＬＯＡ Ｋ，ｗｕ Ｃ Ｃ，ＳＨＥＵ Ｓ Ｔ，ＹＵＡＮ Ｙ Ｆ，ＣＨＩＯＮ Ｍ， Ｈｖｏ Ｄ，Ｘｕ Ｌ．ＩＭＴ—ａｄｖａｎｃｅｄ ｒｅｌａｙ ｓｔａｎｄａｒｄｓ【Ｊ１． ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ，２０１０，４８（８）：４０— ４８． 【４ ＬＡＮＥＭＡＮ Ｊ Ｎ，ＴＳＥ Ｄ Ｎ Ｃ，ＷＯＲＮＥＬＬ Ｇ Ｗ．Ｃｏｏｐ— ｅｒａｔｉｖｅ ｄｉｖｅｒｓｉｔｙ ｉｎ ｗｉｒｅｌｅｓｓ ｎｅｔｗｏｒｋｓ：ｅｆｉｆｃｉｅｎｔ ｐｒｏｔｏ— ｃｏｌｓ ａｎｄ ｏｕｔａｇｅ ｂｅｈａｖｉｏｒ【Ｊ１．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，２００４，５０（１２）：３０６２—３０８０． Ｉ５】万庆涛，马冠 ．放大一转发ＯＦＤＭＡ中继系统多业务 资源分配方案ｌ Ｊ１．应用科学学报，２０１２，３０（１）：７－１３． ＷＡＮ Ｑｉｎｇｔａｏ，ＭＡ Ｇｕａｎｙｉ．Ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｓｃｈｅｍｅ ｆｏｒ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｓｅｒｖｉｃｅｓ ｉｎ ａｍｐｌｉｆｙ ．ａｎｄ．． ｆｏｒｗａｒｄ ＯＦＤＭ ｒｅｌａｙ ｓｙｓｔｅｍ ｆＪ１．Ｊｏｕｒｎａｌ ｏｆ Ａｐｐｌｉｅｄ Ｓｃｉｅｎｃｅｓ，２０１２，３０（１）：７—１３．（ｉｎ Ｃｈｉｎｅｓｅ１ 【６】ＮＡＫＡＤＡ Ｍ，ＴＡＫＥＤＡ Ｋ，ＡＤＡＣＨＩ Ｆ．Ｃｈａｎｎｅｌ ｃａ－ ｐａｃｉｔｙ ｏｆ ＳＣ—ＦＤＭＡ ｃｏｏｐｅｒａｔｉｖｅ ＡＦ ｒｅｌａｙ ｕｓｉｎｇ ｓｐｅｃｔｒｕｍ ｄｉｖｉｓｉｏｎ＆ａｄａｐｔｉｖｅ ｓｕｂｃａｒｒｉｅｒ ａｌｌｏｃａｔｉｏｎ 【Ｃ］／／ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｔｗｏｒｋ Ｉｎ一 ￣ａｓｔｒｕｃｔｕｒｅ ａｎｄ Ｄｉｇｉｔａｌ Ｃｏｎｔｅｎｔ，Ｂｅｉｊｉｎｇ，２０１０：５７９— ５８３． １７ｌ ＢＡＬＡＳ Ｅ，ＰＡＤＢＥＲＧ Ｍ．Ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇ：ａ ｓｕｒｖｅｙ 『Ｊ１．ｓＩＡＭ Ｒｅｖｉｅｗ，１９７６，１８（４）：７１０—７６０． Ｉ８ｌ ＺＨＡＮＧ Ｊ Ｙ， ＮＧ Ｌ Ｌ，ＨＡＮＺＯ Ｌ．Ｅｎｅｒｇｙ— ｅ币ｃｉｅｎｔ ｃｈａｎｎｅｌ—ｄｅｐｅｎｄｅｎｔ ｃｏｏｐｅｒａｔｉｖｅ ｒｅｌａｙｉｎｇ ｆｏｒ ｔｈｅ ｍｕｌｔｉ—ｕｓｅｒ ＳＣ—ＦＤＭＡ ｕｐｌｉｎｋ ｆＪ１．ＩＥＥＥ ｎａｎｓ— ａｃｔｉｏｎｓ ｏｎ Ｖｅｈｉｃｕｌａｒ Ｔｅｃｈｎｏｌｏｇｙ，２０１１，６０（３１：９９２一 】００４． ｌ９ｌ ＧＯＬＤＳＭＩＴＨ Ａ．Ｗｉｒｅｌｅｓｓ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｆＭ１．Ｎｅｗ Ｙｏｒｋ：Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，２００５：２１４—２１６． １１０１ ｗＯＮＧ Ｉ Ｃ，ＯＴＥＲＩ Ｏ，ＭＣＣＯＹ Ｗ．Ｏｐｔｉｍａｌ ｒｅ— ｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｉｎ ｕｐｌｉｎｋ ＳＣ—ＦＤＭＡ ｓｙｓｔｅｍｓ【Ｊ１． ＩＥＥＥ ｎａｎｓａｃｔｉｏｎｓ ｏｎ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ２００９，８（５）：２１６１—２１６５． １１１Ｉ ＲＡＰＰＡＰＯＲＴ Ｔ Ｓ．Ｗｉｒｅｌｅｓｓ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ：ｐｒｉｎｃｉ— ｐｌｅｓ ａｎｄ ｐｒａｃｔｉｃｅ ＩＭ１．Ｎｅｗ Ｊｅｒｓｅｙ：Ｐｒｅｎｔｉｃｅ Ｈａｌｌ， ２００２． Ｉ１２Ｉ ３ＧＰＰ．Ｔｅｃｈｎｉｃａｌ Ｓｐｅｃｉｉｆｃａｔｉｏｎ Ｇｒｏｕｐ Ｒａｄｉｏ Ａｃｃｅｓｓ ｎｅｔｗｏｒｋ．Ｄｅｐｌｏｙｍｅｎｔ ａｓｐｅｃｔｓ：ＴＲ ２５．９４３ Ｖｌ １．Ｏ．０ 【ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．３ｇｐｐ．ｏｒｇ／ｆｔｐ／Ｓｐｅｃｓ／ｈｔｍｌ— ｉｎｆｏ／２５９４３．ｈｔｍ，２０１２—０９—２４． 【１３ｌ ＺＨＡＮＧ Ｙ Ｊ，ＬＥＴＡＩＥＦ Ｋ Ｂ．Ｍｕｌｔｉｕｓｅｒ ａｄａｐｔｉｖｅ ｓｕｂｃａｒｒｉｅｒ—ａｎｄ—ｂｉｔ ａｌｌｏｃａｔｉｏｎ ｗｉｔｈ ａｄａｐｔｉｖｅ ｃｅｌｌ ｓｅ— ｌｅｃｔｉｏｎ ｆｏｒ ＯＦＤＭ ｓｙｓｔｅｍｓ ｆＪ１．ＩＥＥＥ Ｉ１ｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００４，３（５）：１５６６—１５７５． 【１４Ｊ ＮＧ Ｄ Ｗ Ｋ，ＳＣＨＯＢＥＲ Ｒ．Ｃｒｏｓｓ—ｌａｙｅｒ ｓｃｈｅｄｕｌｉｎｇ ｏｆｒ ＯＦＤＭＡ ａｍｐｌｉｆｙ—ａｎｄ—ｆｏｒｗａｒｄ ｒｅｌａｙ ｎｅｔｗｏｒｋｓ ＩＪ１． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｖｅｈｉｃｕｌａｒ Ｔｅｃｈｎｏｌｏｇｙ，２０１０， ５９ｆ３）：１４４３—１４５８． （编辑：秦巍１
