 Hans Journal of Wireless Communications 无线通信, 2013, 3, 129-133 http://dx.doi.org/10.12677/hjwc.2013.36020 Published Online December 2013 (http://www.hanspub.org/journal/hjwc.html) A Sorting Algorithm Based on Threshold and Its Application in OFDM Wei He, Jun Guo, Hongwen Yang Beijing University of Posts and Telecommunication, Beijing Email: haishidx@163.com Received: Oct. 10th, 2013; revised: Oct. 18th, 2013; accepted: Oct. 20th, 2013 Copyright © 2013 Wei He et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: With the rapid development of technology, sort algorithm is not limited in computer areas any longer. More and more outstanding sort algorithm begins to be applied in wireless communications. OFDM needs to select good subcarrier channel conditions for data transmission. Traditional sort methods, including bubble sort and insertion sort, aim to find n best channels. Its disadvantage is that the complexity is high. This paper proposed a sorting algorithm based on threshold which sets a threshold by means of adaptive threshold and get elements that are better than the threshold. The proposed method can significantly reduce the complexity. The simulation results based on different data sample can prove that the proposed method can be better close to the ideal sort. Especially when used in OFDM sub- carrier selection, channel capacity performance is very close. Keywords: Sorting; Threshold; MSE; OFDM 一种基于门限的排序算法及其在 OFDM 中的应用 何 伟，郭 军，杨鸿文 北京邮电大学，北京 Email: haishidx@163.com 收稿日期：2013 年10 月10日；修回日期：2013 年10月18日；录用日期：2013 年10 月20 日 摘 要：随着科技的飞速发展，排序算法不再仅限于计算机领域，越来越来多优异的排序算法开始应用于无线 通信领域。OFDM 需要选择信道条件好的子载波进行数据传输。传统方法是利用冒泡排序、插入排序等算法提 取出最好的 n个信道，其缺点是复杂度高。本文提出一种基于门限的排序算法，通过自适应门限的方式设定好 一个门限，取出比门限大的元素。所提方法能显著降低复杂度。通过对不同的数据样本进行仿真比较，证明所 提方法能较好地接近理想排序。特别在用于OFDM 子载波选择时，信道容量性能非常接近。 关键词：排序；门限；均方误差；正交频分多路复用 1. 引言 排序是日常生活和工作中的一个常见问题，其目 的是将一组原本无序的数据元素(或记录)序列，按照 人们所需要的顺序，排列成有规律的按关键字有序的 序列。对于搜索大型数据库来说，对信息进行排序的 算法至关重要[1]。例如新生入学都会有相应的学号， 以便于今后的管理；用字典或电话号码本查找信息比 较容易和方便，是因为其中的信息都按字母表的顺序 排了序；学生成绩往往需要按照成绩高低或按学号从 前到后排序；在图书馆众多的图书中，需要按照各个 Open Access 129  一种基于门限的排序算法及其在 OFDM 中的应用 学科将书籍归类；排队时从高到低的顺序排队等问 题。排序是一种非常有用的技术，由于它在理论上的 重要性，2000 年被列为对科学和工程计算的研究与实 践影响最大的十大问题之一[2]。随着无线通信的快速 发展，越来越多的排序算法应用于无线通信。例如: 多用户多天线系统中基于 THP 低复杂度调度排序算 法和 V-BLAST OFDM信号检测中的分组排序算法。 目前流行的排序算法有直接插入排序，希尔排序，冒 泡排序，快速排序，直接选择排序，堆排序[3]。可以 对它们各自的时间复杂度作比较如表 1所示。而在实 际工作中，有时候我们并不关心严格排序后的结果， 而只想知道排在前面的数，而他们排列顺序不一定要 是完全按照从大到小排列。比如 1000 个高矮不等学 生排在前100 位的学生身高问题，我们只需要将排在 前面 100 个的学生身高挑出来，至于他们之间排列顺 序我们并不关心，这样我们开始考虑有没有比排序复 杂度更低的算法存在，接下来的章节介绍一种基于门 限的查找方法。 2. 自适应门限方法 2.1. 方法原理 设定一组 N个实数 12 ,,, N x xx，意欲取其前 n个 最大的数，比例为 n pN 的关 ，设定门限向下增量 以及 向上增量 ，两个增量系是 1p p ，门限 THR 的初始值为 0。然后顺序扫描数据，如果第一个数大 门 于门限，将门限更新为THR ，否则更新为 THR。扫描结束后可得 限值，令其为 然后做第二次扫描，找出比THR终大的数， 12 ,,, n 到一个 THR终。 设为 。这样得到的数有 n比例将近 似满足 个， nn 。对于本文所考虑的应用场景来 pNN 说是可以接受的。 2.2. 排序效果评估 我们用排序结果的均值与理想选择均值的均方 差作为排序效果的评估指标。 对本文方法所选出的 12 ,,, n 以精确找到 求均值，记为 。 1 U 后求 通过理想全排序方法可前 n个数， 然 均值，记为 2 U。12 ,UU之间的偏差 12 UU 显 Table 1omp of sorting meth 表 排序算法的复杂度比较 . Carisonod 排序算法 时间复杂度 1. 插入排序 2 On 冒泡排序 2 On 选择排序 2 On 希尔排序 介于插入排序和快速排序之间 快速排序 2 logOn n 堆排序 2 logOn n 与 个拟排序数然N12 ,,, N x xx 1 EU 的具体取值有关。我们 用均方误差 2 2 2 E U 来评估所提排序 方法的排序效 以下将按照不同 果。 的概率分布产生拟排序的样本数 据12 ,,, N x xx，一组给定的样本数据将相应给出 1 U现，也给出了一个误差 2 ,U的一次实 的实现。通过 行M次实验，均方误差近似为仿真进 2 1 M E M 1 Si i M ， i 其中是第 i次实验中观测到的误差。均方误差和 ，N p，都有关。 2.2.1. 样本数据服从均匀分布 分布假设样本数据服从均匀 0,1XU，取 256,512,1024,2048N ，p取0.1和0. p 2， nN ， 表示向上取整，取4 0 4i， 1 0,i, 1,2,3, 4,5 仿真曲线如 1所示。 2.2.2. 样本 服从对数正态分布 ，即 得到MSE 随变化的 图 数据 假设样本数据服从对数正态分布ln i x 取自均 值为 0，方差为 1的高斯随机数。取 256,512,1024, 2048N ，p取0.1和0.2，pnN ， 表示向上取整，取4 10 4i ， 0,1,i2,3, 4,5, 仿 真得曲线如 2所示。 2.2.3. 样本 利分布 ，取 到MSE 随变化的 图 数据服从瑞 假设样本数据服从瑞利分布 256,512,1024, 2048N ，p取0.1和0.2， nNp ， 表示向上取整，取4 10 4i ， 0,1,i2,3, 4,5, 仿 真得曲线如 3所示。 2.2.4. 样本 斯分布 到MSE 随变化的 图 数据服从莱 假设样本数据服从莱斯分 1 K ， 布，莱斯因子 Open Access 130  一种基于门限的排序算法及其在 OFDM 中的应用 Figure 1. MSE versus 图 1. MSE随变化曲线 Figure 2. MSE versus 图 ，取 0.1和0.2， 2. MSE随变化曲线 取256,512,1024, 2048Np n上 整，取4 10 Np ， 表示向 取4i ， 0,1,2,3,i， 4,5 仿真得到 MSE 随变化 如 从以上结 的曲线 图4所示。 果来看，可以得出的结论是：(1) 样本 数越 分布的样本数据排序结果的均值 多，误差越小。(2) 无论 N、p是多少，步长的设 计既不能太大，也不能太小，存在最佳点。最佳点大 致在 0.001 左右。 2.2.5. 复杂度分析 通过上面四种 与理想选择均值的均方差 MSE 随变化曲线，我们 Figure 3. MSE versus 图 3. MSE随变化曲线 Figure 4. MSE versus 图 以看出，所提的自适 作为排序方 4. MSE随变化曲线 可 应门限的方法可以 法的一种近似，即一种次优的方法。而自适应门限方 法只需要经过两次遍历，第一次确定最终的门限，第 二次查找比门限大的数，复杂度均为 On，故总的 复杂度为 On。与表 1所示的排序算 比较，其 复杂度显著降 。 3. 自适应门限方法的一个应用 法相 低 ency Division Multiplexing) 即正 3.1. OFDM及载波分配 OFDM (Orthogonal Frequ 交频分复用技术，实际上OFDM 是多载波调制的 Open Access 131  一种基于门限的排序算法及其在 OFDM 中的应用 一种。其主要思想是：将信道分成若干正交子信道， 将高速数据信号转换成并行的低速子数据流，调制到 在每个子信道上进行传输。其中涉及到了 OFDM 子载 波分配的问题。正因为在多用户环境中，根据用户的 信道状况分配OFDM 子载波，可以获取多用户分集， 从而有效地改善系统的性能或提高频谱效率[4]，所以 OFDM 要做子载波分配。目前通用的 OFDM 子载波 分配方案采用的是给每个用户分配固定的子载波，各 个用户间是频分复用的，如果我们能够将最优的子载 波序列挑选出来分配给不同的用户，系统的性能将得 到显著改善，而这样的挑选的过程就涉及到了排序。 3.2. 自适应门限方法应用 本节我们将自适应门限方法应用到 OFDM 的子载 波分配，并通过比较香农容量[5]来评估所提方法的有 效性。 设定一组个子载波 12 ,,,N N f ff，子载波个数为 N = 需 用户选取比2000，假设要为某个例为 p = 0.2 的子 载波。取门限向下增量为 = 0.001，根据香农容量公 式在第 i个子载波上的信道容量为 2 log11,2,3, ii S Cgi N 式中 i g 代表第 i个子载波上的信道功率增益[6]，S/N 代表的是平均信噪比，取值范围为‒10 dB 至10 dB， 用本文的方法对 i g 排序，筛选出比门限大的值，然 后根据公式(1)求出不同 i g 对应的子载波信道容量 CI，然后将 CI相加得到 C每个 S/N 对应一个C。。 同理通过对 i g 理想排序方法也能求出每个 S/N对 应的 C，下面我们分别以子载波信道增益服从瑞利 分布和莱斯分布作 C与S/N的关系曲线如图 5和图 6。 从以上结果可以看出，自适应门限排序和理想排 序筛 理想排序算法固然可以理想地找到前 n个最佳数 据， 选出来信道容量值比较接近。所以说自适应门限 的方法可以作为理想排序方法的一种近似情况，而且 根据前面的分析我们知道复杂度降低了。 4. 结论 但在无线通信的某些应用中，并不需要知道样本 数据的准确顺序，同时也只关注一个大致的比率，不 Figure 5. Channel capacity versus SNR 图5. 信道容量随信噪比变化曲线 Figure 6. Channel capacity versus SNR 求准确的选出的个数。针对此类应用，本文提出了 参考文献 (References) ivest, R.L. and Stein, C. (2009) 图6. 信道容量随信噪比变化曲线 要 一种自适应门限的排序方法，所提方法和已有的各类 排序方法相比，可以显著降低排序复杂度。我们将此 方法应用到 OFDM 中用户子载波选择的场景，结果表 明采用所提方法时的信道容量能接近理想排序。 [1] Cormen, T.H., Leiserson, C.E., R Introduction to algorithms. 3rd Edition, The MIT Press, Cam- bridge, 71-112. [2] Frances, G. (2005) An in-place sorting with o(nlogn) com- parisons and o(n) moves. Journal of the ACM (JACM), 52, 515-537. [3] Chien, M.V. and Oruc, A.Y. (1994) Adaptive binary sorting Open Access 132  一种基于门限的排序算法及其在 OFDM 中的应用 Open Access 133 associated interconnection networks. IEEE T reas in 平资源分配算法研 schemes andrans- of OFDM-based spatial multiplexing systems. IEEE Trans- actions on Communications, 50, 225-234. [6] 万庆涛 (2011) 中继 OFDMA 系统容量公 actions on Parallel and Distributed System, 5, 561-572. [4] Jang, J. and Lee, K.B. (2003) Transmit power adaptation for multiuser OFDM systems. IEEE Journal on Selected A Communications, 21, 171-178. [5] Bolckei, H., Gesbert, D. and Paulraj, A.J. (2002) On the capacity 究. 计算机工程与应用 , 47, 221-230. |