用户选择算法（精选8篇）
用户选择算法 篇1
协作通信技术使得具有单天线的中继节点或者移动终端形成虚拟天线阵列,从而实现系统的空间分集。如何为节点选择协作伙伴,即中继节点选择能够提高无线协作通信系统的性能[1],是目前协作通信领域的研究热点。文献[2]结合跨层优化的思想给出了基于MAC层的最佳中继选择算法。文献[3]为了提高Two-way中继系统总速率,提出了一种双向中继选择算法。文献[4]提出了一种基于能量有效性的中继选择策略。文献[5]提出了一种为单个节点选择多个中继的协作策略。目前,大部分研究仅仅关注系统性能的提高,并未考虑系统中各用户间的公平性。由于用户参与协作通信需要消耗自身资源,忽略公平性不利于协作通信系统的实际应用。
本文提出的中继选择算法应用于多用户多中继环境,算法在最大化系统信息速率的同时,保证各用户间基于信息速率的公平性,以满足多用户环境中各类用户各种业务所需的服务质量(QoS)。本文首先,提出了基于公平性的最优中继选择算法,然后给出了一种低复杂度次优算法,最后仿真比较了本文算法与盲选择算法的性能差异。
1系统模型
本文研究协作通信系统的多用户多中继环境,传输过程可分为两个正交的阶段:第一阶段,源节点向目的节点和各中继节点广播信息;第二阶段,中继节点将第一阶段收到的信号进行解码,采用空时编码技术重新编码,使各中继节点发送的信号相互正交,并向目的节点放大转发(Amplify-and-Forward,AF)信号。
节点i与节点j间的信道增益为
2中继选择
2.1最优算法
在多用户多中继环境中,为满足各类用户各种业务所需的服务质量(QoS),协作通信系统要求在尽可能提高系统容量的同时考虑各个用户之间的公平性。根据不同用户不同业务的QoS需求,为每个用户设定预期的信息速率。本文将多用户多中继环境下的中继选择问题建模为最优化问题,其优化目标为系统容量。通过在最优化目标函数中加入一组基于信息速率的比例公平约束条件,本文将不同用户间基于信息速率的公平性引入中继选择算法,最优化目标函数为
Subject to:
约束条件C1表示中继选择因子的正确取值。约束条件C2表示在特定时刻一个中继仅与一个用户协作通信。约束条件C3表示不同用户的已达信息速率满足比例公平性。
公式(2)中的最优化问题为非线性约束条件下的混合规划问题,能够使用诸如Newton-Raphson或Quasi-Newton等迭代方法解决。最优算法在完全获得信道状态信息的情况下能够达到基于公平性的多用户多中继系统性能理论上的上界。
2.2低复杂度次优算法
协作通信系统需要在无线信道状态变化之前完成中继选择,最优算法复杂大,工程上实现难度较大。所以,基于现实应用的考虑,需要一种低复杂度的中继选择算法。低复杂度次优中继选择算法描述如下:
1)步骤1:决定中继节点集合K。
AF模式在放大信号的同时也放大了噪声,当信道状态较差时,协作通信系统的性能会受到很大影响。基于协作增益与中继选择算法复杂度的考虑,首先对中继节点集合进行预处理:仅当中继节点k的接收信噪比高于阈值Tr时,中继节点k才会参与多用户协作通信。
2)步骤2:初步决定为用户n选择的中继节点数目Kn。
n在初始化中,使中继节点数目Kn满足
3)步骤3:当用户的已达速率小于预期速率时,为用户选择中继节点。
此步骤保证每个用户依次在中继节点集合中选择一个中继,直到用户的已达速率小于其预期速率或者剩余中继节点集合为空为止。此步骤具体的算法如下:
a.初始化所有变量,变量Rn记录用户n的已达信息速率。算法伪代码为:
b.根据归一化期望信息速率θn,对用户进行降序排列
c.依次为每个用户选择一个具有最大信息容量增益的中继节点。为满足用户间信息速率的公平性约束,具有最高期望信息速率的用户将优先选择一个对其最优的中继。本步骤算法伪代码为:
e.将初始化过程中预留的K*个中继节点选择给信息速率增益最大的用户。此步骤将有效提高系统总的信息速率,同时由于预留的中继节点数目K*较小,对前续步骤所保证的公平性影响很小,可以忽略。本步骤算法伪代码为:
3仿真结果
仿真场景为半径为1.5km的协作蜂窝小区,用户节点与中继节点随机地分布在小区内,仿真参数为
图1比较了本文提出的中继选择算法与盲中继选择算法(Blind Selection Algorithm,BSA)[7]在不同中继节点数目下的系统容量。如图1所示,系统容量随着中继节点的数目增加而增长,协作增益在多中继系统中更为显著。本文所提出的最优算法能够获得最好的系统容量性能,低复杂度次优算法的性能略低于最优算法,两者的系统性能都高于盲选择算法。
图2比较了本文提出的中继选择算法与盲选择算法在不同信噪比下的系统平均中断概率Po u t。中断概率是指信道容量小于目标传输速率的概率,中断概率越低,系统性能越好。由图2可知,最优算法所达到的中断概率最低,低复杂度次优算法盲选择算法的中断概率最高。因此,本文算法的系统性能要优于盲选择算法。
4结束语
本文提出了一种基于用户信息速率比例公平性的中继选择策略。所提出的最优算法及低复杂度次优算法通过跨层考虑物理层的信道状态信息与应用层的用户信息速率,实现了多用户多中继系统的协作增益。仿真结果表明,本文所提出的算法所达到的系统性能要优于传统算法,并且保证了用户间信息速率的公平性,更适合于协作通信技术的现实应用。
参考文献
[1]A.Bletsas,H.Shin,and M.Z.Win.Outage optimality of opportunistic amplify-and-forward relaying[J].IEEE CommunicationsLetters,2007;11:261～263
[2]邹玉龙,郑宝玉,崔景伍,陈超.基于跨层机制的最佳协作中继选择及其系统实现[J].通信学报.2008;29(8):1～10
[3]俞菲,杨绿溪.Two-way中继系统协作节点选择及功率分配策略[J].电子与信息学报.2010;31(8):2077～2082
[4]Madan,R.,Mehta,N.,Molisch,A.,Jin Zhang.Energy-Efficient CooperativeRelaying over Fading Channels with Simple RelaySelection[J].IEEE Transactions on WirelessCommunications.2008;7(8):3013～3025
[5]Single and multiple relay selection schemes andtheir achievable diversity orders[J].IEEETransactions on Wireless Communications.2009;8(3):1414-1423
[6]Furuzan A.,Yi jia F.Threshold based relayselection in cooperative wireless networks[C].GLOBECOM 2008.2008;1～5
[7]Lin Zinan,Erkip E,Steafnov A.Cooperative regions and parter choice in codedcooperative system[J].IEEE Trans commun.2006;54(7):1323～1334
如何理解“以用户选择为中心” 篇2
用户选择的标准是什么？很简单，大家都买，我就喜欢。大家都买的商品，很可能品牌好、销量好，也可能是朋友说好而带动了目标用户的购买欲望。而目标用户从有了购买欲望发展成实际的购买行为，就是对产品喜欢和满意，喜欢包括产品好看、有个性，也可能是为客户量身定制，客户在购买时通过反馈获得参与感和存在感。
满足目标用户的选择和赢得用户的满意，永远是企业的终极目标。用户既是企业的出发点又是落脚点，任何企业在提供产品或服务时，其目的在于使其提供的产品或服务得到用户的认可，并让其乐于接受。这就要求企业了解用户需要什么样的产品和服务，对产品和服务有什么样的要求——再精美的产品，用户不需要，也不会得到用户的认可。因此，企业只有掌握了这个出发点，才能为用户提供满意的产品或服务。
而且，互联网时代的到来，使得信息生产和传播的方式发生了变化。信息不再是由那么一小撮人制造，我们每个人都是信息的原产地； 信息不再是一点对多点的单向传播，而成为多点对多点的多向传播。更关键的是，在整个信息产生和传播的过程中，信息不再是这张大网的核心。在这种情况下，人已经取代了信息，处在了传播的核心位置。
因为人是核心，所以“用户思维”成为打造品牌的核心，而其他各种思维都是围绕用户思维在不同层面的展开。“以用户为中心”的用户思维，不仅仅体现在做品牌的层面，还体现在市场定位、品牌规划、产品研发、生产销售、售后服务、组织设计等各个环节。
同时，用户选择的程度决定了企业赚钱的程度和企业发展的思路。有统计数据显示，一家企业若保住5%的稳定用户，那该企业的利润至少会增加25%。因此，企业的落脚点也应在于使用户最终选择，只有掌握了“用户选择”这个原动力，企业才能得到长足的发展。而且，用户选择也能使企业获得更高的长期赢利能力。
有人说“以用户为中心”不是刚刚冒出来的概念，这是实话，很多传统品牌厂商都在叫嚷着“以用户为中心”、“以客户为中心”，或者“以消费者为中心”，但是，我们当前所处的时代是互联网时代，信息的传播方式产生了非常大的变化，举例来说，以前没有网络的时候，如果一个用户对参加的产品和服务不满意，常态的反应是自认倒霉算了，下次再也不买这家的产品和服务，顶多是向周围的朋友抱怨，提醒他们一定不要去买。这种用户的意见只能在小范围内传播，对厂家的影响不大，所以不少厂家利用这种信息不对称来算计用户，最大限度地从用户身上竭泽而渔，即使出现了用户投诉，也是能捂则捂，而不是积极改进自身的问题。所谓“买的不如卖的精”，就是在传统的营销环境中卖方处于强势地位时用户的处境。
但是，这种状态在当前互联网蓬勃发展的时候就行不通。互联网的特点是开放、透明、共享，消除了信息不对称，使得用户掌握了更多的产品、价格、品牌方面的信息。现在我们更是跨入了所谓的“移动互联网时代”，每个人都可以成为信息传播的中心，用户在选择产品和服务时，一般都会查询其他用户使用该产品后的评价情况，借此来帮助自己作决策。这在互联网之前很难做到，因为用户很难知道除了自己周边的人的使用情况，而互联网信息开放以后，共享的优势体现出来了，用户足不出户就可以知道使用这个产品的人的情况，从而更好地帮助自己做出选择。
用户选择算法 篇3
关键词：多用户MIMO系统,用户选择,BD算法,弦距离,用户相关性
多用户多输入多输出(MU-MIMO)系统可以提供分集增益及空间复用增益，引起了世界广泛的研究兴趣。基站在相同的资源块中可以与多个用户同时进行数据传输，但在发射端需要预处理技术抑制多用户的共信道干扰(CCI)。块对角化迫零算法(BD)[1,2,3,4,5,6]是一种低复杂度的线性干扰消除类预编码算法，是目前多用户预编码主要算法之一。但BD算法同时服务的用户数目受发射天线数和接收天线数的限制。因此如何从基站的待服务用户中选出满足BD算法限制的最佳用户组进行服务，以达到最优的系统性能是目前研究的热点问题。
穷举法遍历所有可能的用户组合，可以选出最优的用户组，但该算法缺点是随着用户数量的增加算法复杂度将迅速增加，因而很难应用于实时系统中。另一个典型算法是最大Frobenius范数选择算法，其核心思想是选择信道状态好的用户进行服务，复杂度大大降低，但是该算法没有考虑用户之间的相互影响，存在较大的性能损失。移动通信系统对算法实时性要求较高，因此低复杂度次最优的用户选择算法受到关注。参考文献[2]、[5]、[6]都是Greedy思想在不同场合的应用，都要考虑已选用户与剩余用户的所有组合，均没有考虑根据已选用户来排除剩余用户中的不可选用户。
本文考虑多用户MIMO下行系统，为解决BD算法中用户受限问题，设计了一种新的低复杂度用户选择算法。该算法利用聚集在同一码本中用户的互斥性，压缩了算法的搜索空间，为进一步降低算法复杂度提供了新的思路。
1 多用户MIMO下行系统模型
考虑多用户MIMO下行系统，如图1所示。
设同时服务的用户最大数为K，基站发射端配置Nt根天线，接收端用户天线数量相同，每个用户配置Nr=Nr1=Nr2=…=Nr K根天线。Hj∈￡Nr×Nt为用户j的信道矩阵(j=1,2,…,K)，其中各元素服从i.i.d的零均值单位方差的复高斯随机变量。sj是用户j的m×1维发射信号向量，假设用户j的发射协方差矩阵E(sjsjH)=I,Fj为Nr×m维发射信号预编码矩阵，Gj为m×Nr维信号解码矩阵。nj为(0,σ)复高斯噪声向量，并假设与用户发射信号独立。在本文中，AT、AH、‖A‖F分别表示矩阵A的转置、共轭转置和Frobenius范数。
此时，用户j的等效基带接收信号的表达式为:
2 BD算法介绍
2.1 BD算法原理
BD预编码算法框图如图2所示。BD算法的基本思想为利用块对角化消除用户之间的共信道干扰(CCI)，将多用户MIMO系统等效成K个相互独立的单用户MIMO系统。令H赞j=[H1T,H1T，…HTj-1HTj+1…HKT]T,H赞j为除用户j本身外，其他用户信道矩阵组成的联合矩阵。为了消除用户之间的CCI,预编码矩阵Fj要求落在Hi的零空间里，使HiFj=0,坌i≠j。对H赞j进行奇异值分解:
令为的后nT-Lj个右奇异向量,构成的零空间正交基。由于功率约束,
归一化使得‖是用户j消除了CCI之后的维等效信道，是预编码矩阵Fj的一部分，nRj和nT-Lj为等效的接收和发送天线数，对等效信道进行SVD分解，如式(3)所示，则用户j的预编码矩阵为
2.2 用户相关性对BD算法的影响
用户的相关性实质是用户信道的相关性，与用户正交性类似,也是考察用户信道之间的相互关系，只是用户的相关性与用户的正交性是一对相反的描述准则。
不失一般性，假设待服务用户中只有i,j两个用户。V軒i(0)为用户i的信道零空间，则HiV軒j(0)=0;V軒j(0)为用户j的信道零空间，则HjV軒j(0)=0。当用户i,j具有强相关性时，即θ值很小时，用户i信道在用户j信道的零空间上的投影值将很小。因此，在应用BD预编码算法消除用户间干扰时，如果用户之间具有较强的相关性时，则在信道等效过程中将损失较大的信道增益,影响系统性能。
在理想反馈的等功率分配情况下，用户j的信道容量Rj的表达式为：
j经过BD算法预处理以后的系统和容量表达式为:K
由于强相关性等效信道增益降低，使单个用户的信道容量降低，从而影响系统的和容量。接收端接收到的信号表达式为:
接收信号的协方差表达式：
由于信号与噪声之间独立，因而E(s赞jnj)=0，进一步：
同样较强的相关性,降低了接收信号的信噪比,使误码性能下降。
下面通过仿真分析用户之间的相关性对系统性能的影响。假设基站端配置nT=8根天线，用户配置相同nR=2根天线，系统中同时服务的用户数为K=4，而待服务的用户总数设定M=30。为了更好地分析用户相关性对系统性能的影响，在每次独立的仿真过程中设定一组强相关用户。图4中“有强相关用户”是指采用最大Frobenius范数选择时，不考虑用户之间的相关性，因此在选出的4名用户中，将以概率选中强相关用户;“无强相关用户”是指采用最大Frobenius范数选择时，如果选中强相关用户，则丢弃Frobenius范数较小的用户，从新选择以保证所选服务组中无强相关用户组。图3、图4是经过1 000次独立运算得到的系统和容量以及误比特性能比较图。对于“有强相关用户”曲线是以概率选中强相关用户，这样具有较强的统计特性，而对于单独选中强相关用户进行服务时，系统性能更差。
从图3中可以看出，当系统和容量在20(b/s)/Hz时，“无强相关用户”比“有强相关用户”有1 dB增益，而对于误比特性能而言，在10-1时“无强相关用户”比“有强相关用户”有5 dB的增益。
3 基于块对角化的码本聚类用户选择算法
3.1 算法思想
通过上述分析可以看出,用户之间的相关性对BD算法性能影响较大，也就是说相关性强的用户不应该在同一资源块内享受服务，否则将使系统性能恶化。当系统选中一个用户时，与该用户具有较强相关性的用户不应该选入这一服务组内，因此相关性较强的用户可以形成互斥用户组。但是，相关性的强弱需要一个门限值来衡量。在Lloyd算法实现矢量编码时，为了寻找质心，需要将大量样本划分到固定个数的初始质心上，然后更新质心位置。也就是划分到同一质心的所有样本可以被该质心所量化。利用这一思想，将待服务用户划分到一些预先设计好的固定信道空间(称其为码本空间)中，划分到相同的码本空间中的用户信道具有将强的相关性，这样将以码本空间形成互斥用户组。
互斥用户组内只能选取一个用户进行服务，也就是说一旦一个互斥用户组内选取了一个用户，该组的其他用户将不参加后面的迭代运算，这样将压缩算法的搜索空间，降低用户选择算法的复杂度。码本空间的个数的选取是本算法需要考虑的问题，码本空间个数太多，增大了用户分组时的额外开销。在后续的仿真中给出了关于码本空间个数的分析，并在该码本空间个数下给出了算法复杂度分析。
3.2 算法流程
本文将以最大和容量为准则来设计基于码本聚类的用户选择算法。首先通过计算用户与码本空间的弦距离来对用户进行分组，接着以系统和容量最大为准则选取用户，当一个码本空间已有一个用户被选中时，该码本空间置为无效码本空间，该码本空间中的其他用户将不再参与以后的迭代运算。
本文所提算法基本步骤：
(1)算法初始化，生成码本W={1,2,…N},用户空间Ω={1,2,…M}，已选用户空间S=准。将用户依据弦距离划分到不同的码本空间U={U1,U2,…UN}，其中Ui(i=1,2…N}为码本i中的用户集合,临时用户集合Ωtemp={1,2…M}。
(2)if d==1
选出使容量最大的用户u1，计算其和容量Ctemp=
U-Um，用户空间Ω=Ω-(u1∈Um)，已选用户空间
(3)for d=2:K
选择)使系统容量最大。计算Ctemp=Ctemp+Cd,分别更新码本空间U=U-Ud,用户空间Ω=Ω-(ud∈Ud),已选用户空间S=S+ud。
从未选中用户空间中Ωtemp-S中选出
(4)算法结束。
4 性能分析
4.1 复杂度分析
由于本算法对与待服务用户中用户的相关性较为敏感，对于算法复杂度的分析从用户统计方法给出。本算法的算法运算量主要集中在两个方面：一是用户分组时的运算量，二是用户选择时的运算量。对于用户分组时的运算量是相当于传统算法增加的，在码本空间个数和用户数给定的条件下，该部分的运算量将是一定的。
从上面分析可知，对于所提算法受用户分组限制较大，精确的运算复杂度很难求得，只给出统计意义上的运算复杂度。针对码本空间长度指示为6 bit(码本空间个数采用二进制表述),不同的待服务用户总数进行统计选择用户所需要进行的迭代次数比较，如表1所示。此表是从不同的待服务用户总数中选取4个用户，在不同的信噪比条件下独立运行1 000次试验下得出的。表2给出了传统贪婪算法4个最佳用户时需要进行的迭代次数，对于不同的信噪比传统贪婪算法迭代次数是固定的。
以表1中给出的用户待服务总数为10的数据为例进行分析，本文所提算法与传统贪婪算法相比降低了近11次迭代次数。
其降低的运算量为：11×(2×(48m2n+24mn2+54m3)+6×(m2n+mn2+m3))
对于基站端发射天线nT=8,用户配置nR=2根天线的系统，降低的运算量为11×(2×(48 m2n+24 mn2+54 m3)+(6×m2n+mn2+m3))=119 328次flop运算。
增加的用户分组运算量为64×10×5 mm+10×7 mm=3 270 mm=52 320次flop运算。
本文所提算法相比于传统算法而言降低的总的运算量为:119 328-52 320=67 008次flop运算。
进一步可得：(67 008/119 328)×11≈6。
由此可见运算复杂度降低了6次迭代的运算量，634=17%。总的运算复杂度降低了约17%。其他情况的运算量分析见表3。
从表3中可以看出本文所提算法与传统算法相比，在迭代次数上降低了近30%，而总的运算量降低比例也在16%～18%之间。
4.2 算法性能分析
考虑无编码多用户MIMO下行系统。假设用户信道均为准静态平稳瑞利衰落信道;采用平均分配功率方法，并且总功率归一化为1;用户信号采用QPSK调制。
仿真1：码本数量及用户数量对CodeGreedy的影响
码本总数决定了用户聚类的集中度，当码本少时，各码本空间内用户数量较多，互斥用户较多，增加了互斥用户的虚警概率，舍弃用户时将存在一定的性能损失。图5给出了0 dB、10 dB、20 dB三个信噪比条件下和容量与码本指示长度之间的关系，从图中可以看出，当码本指示长度为5 bit时，算法性能趋于稳定。图6给出了0 dB、10 dB、20 dB三个信噪比条件下不同用户数对算法性能的影响，可以看出算法不受用户数量的限制，与穷举法给出的最优结果差距稳定。
仿真2:CodeGreedy与经典算法系统和容量比较
仿真条件，基站端发射天线nT=8，每个用户有nR=2根天线，系统服务用户数为K=4，待服务用户总数为10。图7、图8分别给出了CodeGreedy算法码本指示长度为5 bit和6 bit时与经典算法的系统和容量的比较，图中方框分别给出了信噪比为0 dB、10 dB、20 dB时，CodeGreedy与Greedy算法相比和容量的损失值。可以看出，在采用6 bit码本长度指示时,与Greedy算法相比系统和容量损失非常小，但是算法迭代次数降低了30%，总的算法复杂度降低了17%。
本文分析了用户相关性对BD算法的影响，利用码本聚类原理，将相关性强的用户分到同一码本空间，形成互斥用户组。互斥用户中每一时刻只能选取一个用户进行服务，其他用户被置为无效用户，减少了算法的搜索空间。仿真结果表明，本文所提的CodeGreedy算法与Greedy算法相比系统损失很小，但是迭代次数降低了30%，总的算法复杂度降低了17%。本文所提算法是在理想反馈条件下考虑的，下一步将在更加实际的有限反馈条件下设计用户选择算法。
参考文献
[1]JINDAL N,GOLDSMITH A.Dirty paper coding vs TDMAfor MIMO broadcast channel[J].IEEE Transactions on Infor-mation Theory,2005,51(5):1783-1794.
[2]RIICHI K,YASUSHI T,KENTARO N.User selection methodfor block diagonalization in multiuser MIMO systems[J].IEEE GLOBECOM 2007 Proceeding,2007:3295-3299.
[3]KYEONGJUN K,KYUNGCHUL K,JUNGWOO L.BERbased multiuser MIMO user selection with block diagonali-zation[J].Vehicular Technology conference,2010:1-7.
[4]SHEN Z K,CHEN R H,ANDREWS J R,et al.Low com-plexity user selection algorithms for multiuser MIMO systemswith block digitalization[J].IEEE Trans.on signal Process,2006,54(9):3658-3663.
[5]XU M G,LIN D.Low-complexity user selection strategiesin the downlink of multi-user channels[C].Proc.IEEEInternational Conference on Advanved Communication Tech-nology,Korean,2006:204-206.
考虑用户预算的商品推荐算法 篇4
随着电子商务的兴起, 网购网站的规模越来越大, 用户面对的选择越来越多, 为了解决这个问题, 网购网站都为自己的的网站添加了推荐的功能。推荐系统一定程度上为用户解决了信息过载的问题, 增加了用户的购物效率, 同时也增加了网购网站的利润。
在本文中, 作者考虑的是这样一个场景: 用户已经在购物车中添加了一系列的商品, 但是还没有最终付款, 针对购物车中已近添加的一系列商品, 系统可以为用户生成一个推荐列表, 推荐列表中商品可以和购物车中的商品组合起来使用户达到最大的收益。作者考虑的用户上下文信息是用户的购物预算。在购物的过程中, 用户基本上都会对自己的消费在心里设定一个预算, 当消费额在预算范围之内时, 用户最终购买的概率远大于消费额超出预算范围的情况。所以, 在设计推荐机制的时候要考虑这一点。尤其, 在作者考虑的这种场景下, 当用户选定需要购买的商品后, 系统根据购物列表进行推荐, 推荐的商品会和购物车中的商品有很大的关联性。而且特别是当二者组合起来的消费额仍然低于自己的预算, 甚至二者组合起来会有某种折扣的时候, 用户会以相当大的概率接受系统的推荐。这中心理可以解释为个体在经济活动中总是追其利益最大化, 而人在购物的时候总是想要花少量的钱获得更多的物品。
基于上面的介绍, 作者针对前面提到的场景设计了一种推荐机制, 这种推荐机制是通过在基于物品的最近邻推荐[2]的框架内引进用户消费预算的限制来实现的。为了实现这一点, 作者对商品进行了形式化描述, 在此基础上, 给出了相似度的计算方法, 然后分析了用户和网购网站的期望收益。在这之后, 作者给出了系统的设计思路, 最后进行了总结。
2. 推荐模型
假设一个网购站点中商品种类的集合为G = { g1, g2, g3…gn} , G的子集组成的集合为S。为了下面表述问题的方便, 定义函数:
至于用户的预算, 用 θ 表示用户的预算值, 预算的值是不公开的, 但是可以认为预算的概率分布情况是公开的。假设预算的取值范围为 θ∈[a, b], 预算分布的密度函数为f ( θ) 。
目标函数中的后一部分是用户已有的购物列表和推荐的购物列表之间的关联度, 它度量了推荐的购物列表满足用户需求的程度; 前一部分表示的是如果用户接受推荐可以获得的直接的经济利益, 这对用户具有很大的吸引力, 因为用户总是想花更少的钱来得到更多的东西, 这一点在前面也已经有相应的叙述。α, β 是常数。这种将相似度进行线性组合得到新的目标函数的思想来自混合推荐[1]。
其中w表示如果用户接受系统推荐, 最终的消费额不超过自己的预算的概率, 可以通过下面的方法计算得出:
实际上这个结果是一个条件概率, 因为用户已经选择了购物列表x, 那么就说明他的预算 θ 满足 θ≥pay ( x) , 那么后面接受系统的推荐后总的预算是否会超过自己的预算都在这个前提下进行讨论。
假设用户的购物车中已经存在购物列表e, 那么推荐的结果为:
至此, 叙述了推荐算法的完整思路。
推荐模型的核心是计算目标函数的值, 而目标函数的值是由两个部分组成。第一部分是计算两个对象之间的相似度, 可以通过离线计算得到, 因为这个部分的值是相对稳定的, 所以这一部分的计算可以独立为一个模块。目标函数的第二部分需要根据用户的购物车列表来计算出概率以及经济收益, 这个部分的值需要实时生成, 无法通过离线计算来生成, 也要独立为一个模块。最终的结果需要将两者组合起来, 所以生成最终的推荐结果的过程也可以独立为一个模块。
3. 总结
在这篇文章中, 针对现在推荐系统中系统挖掘的用户偏好滞后于用户的实际偏好的情况, 考虑了用户的上下文信息。具体说来就是在传统的推荐系统的框架内引进用户的消费预算来修正推荐结果。并且基于这种思想提出了具体的推荐算法。总的来说, 这是一个尝试, 随着移动互联网甚至物联网的兴起, 用户的上下文会变得更加多样化, 而传统的推荐系统会显得更加无力。那么在设计推荐系统的时候考虑用户的上下文就显得很有必要。下一步的研究可以考虑细化上下文的信息, 考虑在上下文中纳入用户的环境, 服务的环境, 用户使用服务的差异以及商品的差异。
参考文献
[1]《推荐系统》, (奥地利) Jannach, D.等著;蒋凡译, 北京:人民邮电出版社, 2013.7.
直接序列扩频多用户检测算法 篇5
1 最优多用户检测算法 (ML)
不确定性最优多用户检测算法是1986年Verdu提出的最大似然 (ML) 多用户检测算法。对于同步CDMA系统, 接收信号的最佳解调向量如下表示:
对于CDMA系统中同时传送信息的K个用户来说, 每个用户传送信息bk的取值有+1和-1两种可能, 向量B=[b 1, b 2, , ......b K]T的组合有2K种, 这种算法的目的就是要从种组合的用户信息向量中找出一种使似然函数最大的输出信息向量。使用该算法时, 用户每发送一个比特信息, 该算法的复杂度为O (2K) 。实际的CDMA系统具有相当庞大的活动用户数量, 该算法的复杂度随用户数量的增加呈指数上涨, 实际的系统中该算法运算的复杂度会使得系统难以忍受。
2 解相关多用户检测算法 (DEC)
多址干扰是由于不同用户的扩频码不能完全正交引起的。抑制多址干扰的影响, 去除所有用户扩频码之间的相关性, 是解相关检测的基本思想。
考虑离散CDMA信号模型。
第一步, 用转置后的扩频码集矩阵S左乘信号Y得到匹配信号Z。
其中R=SST, 叫做相关矩阵, 第一步的处理实质上就是对每个用户进行匹配的单用户检测。
第二步, 对相关矩阵R求逆, 得到R-1。
第三步, 用R-1左乘第一步中得到的匹配信号z, 并对结果进行判决。
由于需要计算相关矩阵的逆矩阵, 使得解相关多用户检测算法的计算复杂度达到了O (k3) 。
3 最小均方多用户检测算法 (MMSE)
最小均方 (MMSE) 多用户检测算法同时考虑了背景噪声和多址干扰, 该多用户检测算法的实质是使发送的信息与检测输出数据的均方误差最小, 即代价函数E[B-TY2]最小, 其检测过程如下。
其中R=SST为相关矩阵, A为振幅矩阵, ∂2为高斯白噪声的方差。将线性变换矩阵与匹配滤波器组输出向量相乘得到最小均方误差检测器输出, 再对此输出进行判决。
和解相关多用户检测一样最小均方多用户检测算法也需要计算相关矩阵的逆, 在运算复杂度上相对解相关多用户检测算法没有改变。
参考文献
[1]Verdu S.Multiuser detection[M].Cambridge University Press, 1 99 8.
[2]R.Kohno, M.Hatori, H.Imai.Cancellation technique of co-channel interference in asynchronous spread spectrum mul-tiple access systems[J].Elect.And Comma.In Japan, 1983, 66:20～29.
用户选择算法 篇6
关键词：MIMO,多用户检测,遗传算法,IGA-MUD
0 引 言
新一代移动通信 (Beyond 3G/4G) , 可以提供高达100 Mb/s的数据传输速率, 以支持新业务的不断涌现。如何在有限的频谱资源上实现高速率和大容量是未来移动通信系统的关键因素之一。MIMO (Multiple-input Multiple-output) 技术利用多个天线实现多发多收, 充分开发空间资源, 可以成倍地提高信道容量, 同时也可以提高信道的可靠性, 降低误码率。多用户检测技术与MIMO结合可以进一步提高传输效率[1]。但是在MIMO系统多用户检测的研究上, 尽管全空间最大似然 (ML) [2,3]检测能获取最优的检测性能, 但由于其算法复杂度太高, 一直无法实际应用, 于是研究复杂度较低, 性能接近ML的次优多用户检测算法具有重要意义。在各种检测方法中, MMSE (Minimum Mean Square Error, 最小均方误差) 算法[1,3], ZF (Zero Forcing, 迫零) 算法[4]以及文献[5,6]提出的基于QR分解MIMO检测算法都在牺牲了一定性能的情况下降低了复杂度。近几年来, 遗传算法在复杂优化问题求解和工业工程领域应用方面, 取得了一些令人信服的结果, 引起了很多人的关注。文献[7,8,9,10]研究了CDMA系统使用遗传算法进行多用户检测的性能。本文在假设没有信道编码的前提下, 重点分析了基于V-BLAST的MIMO上行系统中多用户检测技术, 提出利用遗传算法进行MIMO多用户检测, 避免了直接使用最大似然带来算法复杂度的巨大增加, 与传统的多用户检测算法相比较, 提高了检测性能。仿真结果表明, IGA-MUD (Improved Genetic Algorithm Multi-User Detection) 在保证获得接近最佳ML检测性能的同时, 计算复杂度比ML最优多用户检测方法有明显的降低。
1 系统模型
采用V-BLAST的MIMO系统上行信道结构, 如图1所示。
假定有M个用户, 每个用户1根发射天线, N根接收天线, 发射信号为x= (x1, x2, …, xM) T, 第m根发射天线上的星座点集合为sm (1≤m≤M) , 则接收信号为:
式中:接收到的信号r= (r1, r2, …, rN) T, rn为第n根天线上的接收信号 (1≤n≤N) ;Hm表示对第m个用户而言的MIMO信道, H= (H1, H2, …, HM) , Hm= (h (1, m) , h (2, m) , …, h (N, m) ) , 其中h (i, j) 表示第j个发射天线到第i个接收天线的信道矢量, 其独立地服从复高斯分布的信道矩阵 (均值为0, 方差为1) ;n为高斯白噪声向量 (均值为0, 方差σ
假设已知接收端为理想信道, 对于ML检测, 就是要求解:
对于线性检测, 就是要求解:
式中:G的取值因不同的线性检测方法而变, 对于ZF检测, G= (HHH) -1HH;对于MMSE检测, G= (HHH+1/γI) -1HH, γ表示信噪比, I表示单位阵。
2 本文算法IGA-MUD分析
2.1 基本遗传算法SGA
SGA (Simple Genetic Algorithm) 基本框架如下, 其流程图如图2所示。
(1) 遗传代数计数器初始化:Y←1;每一代群体中的个体数为X, 遗传代数为N。
(2) 随机产生初始群体P (Y) 。
(3) 评价群体P (Y) 的适应度。
(4) 对群体P (Y) 中的个体进行选择配对。
(5) 个体交叉重组操作:P′ (Y) ←P (Y) 。
(6) 个体变异操作:P″ (Y) ←P′ (Y) 。
(7) 评价群体P″ (Y) 的适应度。
(8) 个体选择, 复制操作:
P (Y+1) ←[P (Y) ∪P″ (Y) ]
(9) 终止条件判断。若不满足终止条件, 则转到第 (4) 步, 继续进行遗传操作过程;若满足终止条件, 则输出当前最优个体, 算法结束。
遗传算法 (Genetic Algorithm) [11]是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法, 其选择、交叉、变异等运算都是以一种概率的方式来进行的, 虽然这种概率特性会使群体中产生一些适应度不高的个体, 但是这个群体每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代, 新的群体中总会更多地产生出许多优良个体, 最终在群体中将会得到一个最优良的个体, 它将以概率1收敛于问题的最优解。
2.2 基于改进遗传算法的MIMO多用户检测算法
ML是遍历所有的向量星座来寻找合适的向量, 这在天线数目较多时是一个非常困难的任务, 需要巨大的搜索判决运算, 所以可以利用遗传算法来解决这个问题。基于最大似然准则的最优判决准则式 (4) 可以作为IGA-MUD的目标函数, 由于最大似然判决式 (2) 是求解目标函数的最小值, 而标准遗传算法要求的适应度函数为非负的, 因此要求得适应度函数值最大的最优个体。所以必须将目标函数转化为适应度函数, 采用式 (5) 建构IGA-MUD的适应度函数f (Y, X) 为:
式中:max{Ω (x) }表示所有个体目标函数值中那个最大值;Ω (x (Y, X) ) 表示第Y代的第X个个体目标函数值;c是一个较小的正数, 保证了适应度函数f (Y, X) 非负, 并且把原来的最小值问题转换为IGA-MUD可实现的最大值问题。
SGA应用在多用户检测中, 由于被搜索的空间非常大, 而导致其收敛速度较慢, 收敛过早、进化速度缓慢、寻找到次优解而不是最优解、存在容易陷入局部最优等问题, 因此需要对SGA基本遗传算法进行改进。
对基本遗传算法进行改进后的MIMO多用户检测算法——IGA-MUD, 其具体实现如下 (见图3) :
(1) 编码和种群初始化
在IGA-MUD中, 需要将种群中的个体用染色体来表达, 一般来说可以采用0 和1 两个整数组成的二进制符号串表示。对于MIMO多用户检测问题, 染色体由星座符号组成, 基因单元为星座点, 种群中个体i可以表示为xi= (x1, x2, …, xM) , 个体长度即为用户数M。通常SGA是在解空间中随机选择X个个体作为初始化种群的。对于MIMO多用户检测问题, 为了加快收敛速度和减小计算复杂度, IGA-MUD将传统检测器的输出
(2) 根据各个个体的适应度值f (Y, X) , 从上一代种群中选择出适应度较高的个体遗传到下一代种群中。SGA采用的是轮盘赌选择方法, 适应度大的个体可能被选择多次, 而适应度小的个体可能被淘汰;IGA-MUD结合最优保存策略的进化模型[11]加以改进, 加快了IGA-MUD的收敛速度。
最优保存策略进化模型的具体过程是:
① 找出当前种群中max f (Y, X) 适应度最高的个体xbest和min f (Y, X) 适应度最低的个体xworst。
② 当前种群中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高, 则以当前种群中的最佳个体作为新的迄今为止的最好个体。
③ 用xbest迄今为止的最好个体替换掉xworst当前种群中的最差个体。
(3) 交叉是IGA-MUD中最主要的操作, 通过交叉可以得到新一代的个体, 新个体组合了其父辈个体的特性。交叉体现了信息交换的思想, 它将种群内各个个体随机搭配成对, 对每一对个体, 以某种概率 (称为交叉概率Pc) 交换他们之间的部分数据。交叉的方法有单点交叉和多点交叉, 其中比较好的方法是均匀交叉, 即两个配对个体的每一个基因座上的基因都以相同的交叉概率进行交换, 从而形成两个新的个体。在进行均匀交叉配对时, 随机生成一个与个体等长度的二进制交叉掩码序列, 两个个体在掩码序列元素为“1”的对应位置交换元素, 而在掩码序列元素为“0”的位置不发生交换。实验结果表明, 使用均匀交叉后, IGA-MUD的检测性能优于SGA的性能, 如图4所示。
(4) 变异是对种群中每一个个体, 以某一概率 (称为变异概率Pm) 改变某一个或某一些基因座上的基因值作为其他的等位基因。均匀变异UM (Uniform Mutation) 操作采用符合某一范围内均匀分布的随机数, 以某一较小的概率来替换个体编码串中各个基因座上的原有基因值, 使得搜索点可以在整个搜索空间内自由移动。
在IGA-MUD中, 将其改进为CNUM (Closest-Neighbor Uniform Mutation) , 即限定用户突变的方向为最近的星座点, 且突变到这些限定的星座点的概率相同。改进后加快了IGA-MUD的收敛速度。
(5) 若满足收敛条件, 达到预先设定的遗传代数Y=N, 则IGA-MUD结束, 否则转 (2) 。
IGA-MUD所得到的最优个体, 即为MIMO多用户检测得到的各个用户的信号向量。需要指出的是, IGA-MUD是把不同用户的信号联合检测, 而传统的SIC和PIC多用户检测器则是通过与其他用户干扰抵消, 实现各个用户信号的估计, 因此IGA-MUD在不同用户的信号检测之间没有错误的繁殖, 提高了多用户的检测性能。
3 算法复杂度分析
对以上提出的IGA-MUD进行计算复杂度分析, 假设所采用的调制方式对应的符号数为N, 用户数为M, 则最优最大似然检测方法是对NM种可能解进行完全搜索, 计算复杂度为O (NM) , 随着用户数M的增长成指数增长。
对于IGA-MUD, 其计算复杂度主要由搜索的个体数目决定。当种群遗传进化代数为Y, 每代种群含X个个体时, 共有X×Y个个体被代入适应度函数进行适应度评价, 其计算复杂度为O (X×Y) , 与遗传进化代数呈线性增长关系。另外, IGA-MUD还有选择、交叉和变异的附加操作。在算法的每一代, 需要产生X次选择操作, 还需要进行PcX/2次交叉操作以及进行PmX (2K+1) M 次变异操作 (这里 (2K+1) M是解的维数) ;将这几个部分相加, 乘Y, 再除以 (2K+1) M, 则选择、交叉和变异的计算复杂度为O (X×Y) 。显然X和Y的选择由解空间规模N (2K+1) M决定, 这里设X=a (2K+1) M, Y=b (2K+1) M (a 和b是与解的维数相关的两个正常数) 。因此对于一个给定的帧长度2K+1, IGA-MUD的计算复杂度为O (M2) 。显然当用户数较多时, 将在很大程度上减少计算时间。通过设置不同的种群遗传进化代数和种群个体数目, 系统可进一步在性能与复杂度之间进行有效配置。
4 仿真结果
仿真中采用基于V-BLAST的MIMO上行信道系统, 假定各个用户的信道矩阵Hm由独立同分布的复高斯随机变量组成, 均值为零, 方差为1。噪声为高斯白噪声, 均值为0, 方差σ
从图5、图6可以看出, IGA-MUD的检测性能与传统检测器相比, 得到了很大的提高, 整个系统的性能随遗传代数的增加有所提高, 并且接近ML多用户检测器的性能, 而且复杂度与ML相比有了明显的降低。在相同误比特率时, IGA-MUD与MMSE相比较, 检测性能至少提高了8 dB;随着信噪比的增加, IGA-MUD继续保持优于其他检测算法。通过设置不同的种群遗传进化代数和种群个体数目, 系统可进一步在性能与复杂度之间进行有效配置。
由图5可见, 在QPSK调制方式下, 4个用户时, IGA-MUD在种群个体数X=20, 遗传进化代数Y=6时的检测性能已经比MMSE, ZF, QR有了很大的改善, 接近ML算法的性能。此时, IGA-MUD的计算复杂度为O (X×Y) , 也就是120;ML算法的复杂度为O (NM) , 也就是256。可以看出, IGA-MUD的复杂度要小得多。从图6可以看出, 在QPSK调制方式下, 6个用户时, IGA-MUD在种群个体数X=70, 遗传进化代数Y=12时, IGA-MUD的复杂度只需要X×Y=840就可以接近ML的性能, 而此时ML的复杂度却为NK=46=4 096。因此, 当用户数量较大时, IGA-MUD的复杂度与ML相比较要小得多。
5 结 语
提出了一种基于改进遗传算法的MIMO多用户检测算法IGA-MUD, 将遗传算法用于MIMO多用户检测, 并对SGA进行了改进, IGA-MUD在性能上与SGA (基本遗传算法) 相比较有明显的改进, 是一种有效可行的多用户检测算法。IGA-MUD避免了直接使用最大似然算法带来运算复杂度的增加, 显著降低了算法的复杂度。仿真结果表明, 在垂直分层空时码系统中, 对于4个用户和6个用户的上行MIMO多用户系统, 其计算复杂度明显低于ML最优多用户检测算法, 而且其性能接近ML的性能, 与ZF, MMSE多用户检测算法相比较, 性能得到了显著的提高。
参考文献
[1]Verdu S.Multiuser Detection[M].Cambridge:CambridgeUniv.Press, 1998.
[2]Li Zi, Cai Yueming, Ni Mingfang.Low Complexity MIMODetection Based on Branch and Bound Algorithm[A].The18th Annual IEEE International Symposium on Personal, In-door and Mobile Radio Communications[C].2007.
[3]Hanzo L, Munster M, Choi B J, et al.OFDM and MC-CDMA for Broadband Multi-user Communications, WLANsand Broadcasting[M].IEEE Press/Wiley, 2003.
[4]Jankiraman, Mohinder.Space-time Codes and MIMO Sys-tems[M].Boston:Artech House INC, 2004.
[5]Wubben D, Bohnke R, Rinas J, et al.Efficient Algorithm forDecoding Layered Space-Time Codes[J].IEE ElectronicLetters, 2001, 37 (22) :1 348-1 350.
[6]Wang Zhongpeng.A Hybrid Receiver Combining QR andPIC Based on MIMO Frequency Channels[A].WirelessCommunications, Networking and Mobile Computing[C].2008.
[7]Hanzo L, Yang L L, Kuan E L, et al.Single-and Multi-Car-rier DS-CDMA:Multi-user Detection, Space-time Spreading, Synchronisation and Standards[M].IEEE Press-John Wiley&Sons Ltd., 2003.
[8]Ergun C, Hacioglu K.Multi-user Detection using a GeneticAlgorithm in CDMA Communications Systems[J].IEEETrans.on Commun., 2000, 48 (8) :1 374-1 383.
[9]Wu X, Chuah T C, Sharif B S, et al.Adaptive Robust Detec-tion for CDMA using a Genetic Algorithm[J].Inst.Electr.Eng.Communications, 2003, 150 (10) :437-444.
[10]刘洪武, 冯全源.MC-CDMA系统中基于遗传算法的多用户检测[J].电子科技大学学报, 2008, 37 (4) :485-488.
用户选择算法 篇7
在多用户MIMO下行系统中, 基站需要同时向多个用户传输数据, 由于多个用户的信道存在相关性, 将会产生多用户干扰, 多用户干扰会严重影响系统的和容量。所以, 选择空间正交性好的用户进行传输是十分必要的。此外, 由于基站能同时传输的用户数目不能大于基站的天线数, 所以在用户数大于基站天线数时需要进行用户选择。合理的用户选择可以获得更高的空间分集增益, 进而增加系统的和容量[7]。半正交用户选择算法 (SUS) 可以选择空间正交性好的用户进行通信[8], 减小了多用户干扰。但是SUS算法假设基站完全已知信道状态信息, 不适合有限反馈系统。目前, 大多数多用户MIMO有限反馈系统都采用固定码本方案, 通过有限的反馈比特选择本地码本, 基站和每个用户都已知码本信息, 用户根据自己的信道条件和本地码本做相关, 选择信干噪比 (SINR) 最大的一个码字, 并通过上行反馈信道将码字编号及相应的SINR值反馈给基站, 基站在预编码时, 将该码字作为该用户的预编码矩阵。目前的多用户选择方案很少考虑用户公平性的问题, 然而在实际系统中, 有时需要照顾信道条件差的用户, 比例公平调度 (PFS) 通过观察用户在一段时间内的平均吞吐量来判断用户是否被调度, 能够兼顾公平性和系统和容量[9,10]。
1 系统模型
本文考虑多用户MIMO下行链路系统, 系统模型如图1所示。基站配置N根天线, 每个用户配置单根天线, 基站可以同时与K (K≤N) 个用户进行通信, 系统用户数目为M (K≤M) 。用户k的信道系数可以表示为hk (t) ∈C1×N, 其中我们假设hk (t) 中的每个元素是独立但不同分布复高斯随机变量, 均值为0, 不同的方差代表不同的信道条件。本地码本采用LTE码本, 基站选择一个子码本作为预编码矩阵W (t) (∈CN×N) 形成N个预编码向量。W (t) 的列向量w (t) 代表一个预编码向量。每个时隙基站可以同时与K个用户进行通信, 第t个时隙第k个用户的接收信号可以表示为
式 (1) 中s (t) ∈CN×1代表基站的发送信号, 满足归一化功率限制E{s (t) s (t) *}=1, nk (t) 代表接收端的加性高斯白噪声向量, Pk是基站分配给用户k的发送功率, 满足功率限制。在本文中, 信道采用时变的瑞利衰落信道, 假设每个用户完全已知自己的信道状态信息hk。LTE码本集合设为{F (0) , …, F (G-1) }, 其中代表子码本, fm (g) ∈CN×1代表一个码字。LTE码本的特点是相同子码本的列元素之间相互正交, 不同子码本的列元素之间不正交。所以, 在选择预编码矩阵时需要选择一个子码本作为预编码矩阵, 子码本的每个码字作为用户的预编码向量。每个用户利用公式 (2) 计算和每个码字 (g, m) 的SINR, 其中g代表第g个子码本, m代表第m个码字。并选择使SINR最大的码字序号 (g, m) 和相应的值SINRk, g, m反馈给基站。
式 (2) 中k=1, 2, …, K, g=1, 2, …, G, m=1, 2, …, N, G代表子码本的个数 (由反馈比特数目决定) 。
基站接收到每个用户反馈信息, 首先对每个码字选择一个使SINR最大的用户如公式 (3) 所示, 之后按照公式 (4) 计算每个子码本能获得系统和容量, 选择子码本序号g*使得Rg获得最大值, 基站选择F (g*) 作为预编码矩阵, 即W (t) =F (g*) 。
式中P0=P/N代表每个用户的发送功率。在本文中, 只考虑等功率分配。
2 PFS方案
2.1 传统的PFS
大多数对多用户选择算法的研究都只关注系统和容量而忽视用户公平性。因此, 信道条件差的用户基本得不到服务, 在服务质量 (QOS) 敏感的系统中这些用户的服务质量不能得到保证。Jalali和Padovani所提出的PFS方案可以有效地解决用户公平性问题。在PFS方案中, 选择用户时不仅仅根据用户的瞬时吞吐量, 还需要考虑之前一段时间内该用户的平均吞吐量, 提高了信道条件差的用户被选择的机会, 兼顾了用户的公平性。用户选择的准则可以表示为:
式 (5) 中Rk (t) 代表第k个用户的瞬时吞吐量, Tk (t) 代表第k个用户之前tc个时隙内的平均吞吐量。每个时隙, Tk (t) 根据公式 (6) 进行更新。
传统的PFS方案在一个时隙仅仅选择一个用户, 但是在本文中, 基站每个时隙需要选择K个用户, 因此在多用户MIMO下行系统中需要修改传统的PFS方案。
2.2 多用户MIMO系统中的PFS
在本文中, 基站一个时隙需要选择多个用户进行数据传输, 但是对于一个码字, 每次只能选择一个用户。因此, 在第t个时隙, 基站通过传统的PFS方案对码字 (g, m) 进行用户选择:
式 (7) 中Rk, g, m (t) 代表第k个用户对码字 (g, m) 的瞬时信息速率, Tk (t) 代表第k个用户之前tc个时隙内的平均信息速率, 每个时隙根据公式 (8) 进行更新。
式 (8) 中Rk (t) 代表用户k在第t个时隙的瞬时信息速率。
3 用户选择方案
在本文中, 我们选择LTE码本作为本地码本, 子码本的个数由反馈比特数决定, 而每个子码本的码字数目由基站的天线数决定。
第k个用户通过下行导频信道获取信道状态信息, 计算和每个码字的SINR数值SINRk, g, m。之后选择使得SINR最大的码字序号 (g*, m*) , 通过上行反馈信道用户k将SINRk, g*, m*和相对应的码字序号 (g*, m*) 反馈给基站。基站接收到每个用户的反馈信息, 通过以下过程进行用户选择。
步骤1:对于每个码字 (g, m) , 选择用户k*使Rk, g, m (t) /Tk (t) 最大。
式 (9) 中Rk, g, m (t) =lg (1+P0SINRk, g, m) 。
步骤2:对于每个子码本g, 计算子码本容量Rg (t) 。
步骤3:选择g*=arg 1m≤ga≤xGRg (t) 使Rg (t) 获得最大值, 因此预编码矩阵为W=F (g*) , 系统和容量为R (t) =Rg* (t) 。
步骤4:通过公式 (8) 更新Tk (t) 。
上述算法为考虑用户公平性的PFS算法, 如果不考虑用户公平性只是基于系统和容量, 则在步骤1时选择用户根据公式 (11) , 并且不需要步骤4。
4 仿真结果
本节将给出仿真结果, 观察采用PFS方案和基于和容量方案的有限反馈多用户MIMO系统的用户公平性和系统容量。为了比较不同信道条件用户的公平性, 这里通过不同的方差来区分不同信道条件的用户。假设在所有的用户中, 四分之一用户服从CN (0, 1) 分布, 四分之一用户服从CN (0, 1/2) 分布, 四分之一用户服从CN (0, 1/4) 分布, 其余用户服从CN (0, 1/8) 分布。基站配置4根天线, 即N=4, 每个用户配置单天线。反馈比特数可以选择2或者4, 因此根据LTE码本的产生方式可以有1或者4个子码本。发送功率为P=10 d B, 观察窗口tc=100。采用100 000次Monte-Carlo仿真得到仿真曲线。
图2给出了2个反馈比特和4个反馈比特时, 分别采用PFS方案和基于容量的方案的系统和容量曲线。由仿真图可以很容易地看出当采用相同的方案时, 反馈比特数越多系统和容量越大, 这是由于更多的反馈比特可以携带更多的信道状态信息, 本地LTE码本数目增加, 可以获得更高的码本增益。当反馈比特数目一定时, 基于和容量的方案可以获得更高的系统和容量, 这是因为此时选择用户仅仅以和容量为依据没有考虑用户的公平性。此外, 随着用户数目的增加两种方案的差距逐渐增加, 这是因为基于和容量的方案不受信道条件差的用户的影响, 但是PFS方案由于需要照顾更多的信道条件差的用户, 使二者差距逐渐增加。
图3和图4对比了两种方案的用户公平性, 这里假设用户数目固定为16个。本文中, 将每个用户获得的平均信息速率作为衡量用户公平性的标准。从仿真图中可以很清楚地看出与基于和容量的方案相比, PFS方案中信道条件差的用户获得了更多的信息速率。此外, 比较图3和图4还可以看出, 2比特反馈可以获得更好的用户公平性, 这是因为当反馈比特数目较大时, 可以产生更多的子码本, 这时每个子码本的虚拟用户数将会减少, 没有足够的用户供基站选择, 这对于信道条件差的用户是不利的。
为了观察信道条件差的用户被服务的情况, 图5给出了信道条件最差的用户所获得信息速率随用户数目的变化曲线, 即服从CN (0, 1/8) 分布的一组用户的平均信息速率随用户数目的变化曲线。从仿真曲线可以看出, 当用户数较少时, 2比特反馈PFS方案的用户能够获得更好的公平性, 信道条件差的用户能够获得更好的服务。但是当用户数目增加时, 2比特反馈PF方案和4比特反馈PFS方案的性能逐渐接近, 而4比特反馈PFS方案能够获得更高的系统和容量。所以, 在有限反馈LTE系统中, 如果用户数目较少, 可以采用更少的反馈比特来节省带宽利用率和提高用户公平性, 当用户数目较大时, 可以采用更多的反馈比特来提高系统的和容量。
5 结论
本文研究了有限反馈多用户MIMO系统下行链路的用户选择算法, 采用LTE码本作为有限反馈码本, 比较了基于和容量的方案和考虑用户公平性的PFS方案, 并深入地分析了反馈比特数目和用户数目对系统和容量和用户公平性的影响。从仿真结果可以看出, PFS方案可以兼顾系统和容量和用户公平性;当用户数目较少时, 可以用更少的反馈比特获取用户公平性和带宽效率, 当用户数目较大时, 可以用更多的反馈比特来提高系统和容量。
摘要：在多用户多输入多输出 (MU-MIMO) 下行链路系统中, 通过合理的用户选择可以提高系统的空间分集增益。大多数目前的研究中, 往往假设基站完全已知每个用户的信道状态信息 (CSI) , 不适用于有限反馈系统。此外, 目前的用户选择算法很少考虑用户的公平性。为了有效地解决这两个问题, 采用LTE码本作为本地码本, 提出了有限反馈系统下考虑公平性的用户选择方案。并且深入地分析了反馈比特数和用户数对公平性和系统和容量的影响。仿真结果显示, 当用户数目较少时可以用更少的反馈比特来获取公平性和带宽利用率, 当用户数目较大时可以用更多的反馈比特数获取更高的系统和容量。
关键词：MU-MIMO,用户选择,用户公平性,有限反馈
参考文献
[1] 3 GPP.Evolved Universal Terrestrial Radio Access (E-UTRA) .Physical channels and modulation.3GPP TS 36.211 version 10.0.0Release 10, 2011
[2] Caire G, Shamai S.On the achievable throughput of a multiantenna Gassian broadcast channel.IEEE Transactions on Information Theory, 2003;49 (7) :1691—1706
[3] Spencer Q H, Swindlehurst A L, Haardt M.Zero-forcing methods for downlink spacial multiplexing in multiuser MIMO channels.IEEE Transactions on Signal Processing, 2004;52 (2) :461—471
[4] Masoud, BabakHassibi.On the capacity of MIMO broadcast channels with partial side information.IEEE Transanctions on Information Theory, 2003;51 (2) :506—522
[5] Taesang Y, Jindal N, Goldsmith A.Multi-antenna downlink channels with limited feedback and user selection.IEEE Journal on Selected Areas in Communications, 2007;25 (7) :1478—1491
[6] Huang K, Hearth Jr R, Andrews J.Space division multiple access with a sum feedback rate constraint.IEEE Transactions on Signal Processing, 2007;55 (7) :3879—3891
[7] Wang Youxiang, Hur Sooyung, Park Yongwan, et al.Efficient user selection algorithms for multiuser MIMO systems with zero-forcing dirty paper coding.IEEE Journal on Communications and Networks, 2011;13 (3) :232—239
[8] Yoo T, Goldsmith A.On the optimality of multiantenna broadcast scheduling using zero-forcing beamforming.IEEE Journal on Selected Areas in Communications, 2006;24 (3) :528—541
[9] Sharma, Naresh.A Study of opportunism for multiple-antenna system.IEEE Transactions on Information Theory, 2006;51 (5) :1804—1814
用户选择算法 篇8
关键词：PageRank算法,网页预分类,兴趣值,查询
0 引言
互联网的快速发展为人们提供了巨量的信息, 如何能够在大量信息中找到所需要的信息, 是互联网用户最关心的问题, 搜索引擎成为人们获取信息的重要工具。利用搜索引擎给用户带来了极大的方便, 但不足之处是它不能根据特定用户的兴趣提供合适的信息。
理想的搜索引擎应该能够为用户提供与之兴趣相关的查询信息, 这就要求需要搜索引擎具有个性。如何根据用户的兴趣来搜索重要网页逐渐成了重点研究的问题。Goolge对以前的网页重要性Page Rank算法偏重于旧网页, 事实上, 网页的重要性 (Page Rank) 不仅与超链接相关, 还应该与资料本身的信息和用户浏览的兴趣有关。所以本文在这里希望能够提供一种基于用户兴趣的Page Rank计算方法, 最终达到搜索引擎的个性化。
1 Page Rank 算法简介
网络链接对应的有向图可以表示为:
G=
(1) 式所表示的意义是假设网络中有一个由网页i指向网页j的超链接, 那么a ij=l, 否则aij =0。
大多数链接分析的算法包括Page Rank算法在内的大都是基于上面的邻接矩阵。Page Rank算法是采用随机游走模型来模拟用户浏览网页的行为, 由此来计算每个网页的重要性。Page Rank算法基于下面前提: (1) 被多次引用或者被其他重要的网页引用的一个网页可以认为是重要的;其重要性被平均传递到它所引用的网页; (2) 随机冲浪模型, 随机冲浪模型可以认为一个用户随机点击页面上的一个链接, 进入这个链接所指向的页面, 再次随机点击该页面上的链接, 直到用户不再感到兴趣了关闭网页退出。
一个页面的重要性是由所有链向它的页面的重要性来决定, 一个页面的PR是由所有链向它的页面重要性经过递归算法得到的, 也就是说一个网页的页面PR值越高, 就可认为这个页面在互联网中重要性越高。因此, 假如要计算网页A的等级, 那么它的PR值就是链入网页A的页面的PR值除以该页面的出站链接数量的和, 因此, 其算法就可以定义如下:
标准的Page Rank计算方法是:
(2) 式其中n表示网页总数, PR (A) 表示网页A的PR值, PR (Pi ) 表示链接到A的网页Pi 的PR值, C (Pi ) 表示网页Pi 的出站链接数量, d是阻尼系数一般取值为0.85。
2 Page Rank 算法分析
传统的Page Rank算法只是客观的描述了网页之间的本质特征, 是基于网页链接结构的搜索引擎排序算法, 通过用户浏览网页的概率而获得Page Rank值的, 在计算过程中, 往往是忽略了网页内容相似度对于链接指向的影响, 主要是通过用户浏览网页的过程随机进行判断, 所以排序不能满足用户的兴趣程度。
Page Rank算法是一个静态算法, 所有网页的PR值通过离线计算获得, 这样可以有效减少在线查询时的计算量, 极大降低了查询响应时间;但Page Rank算法的主要缺陷是偏重于旧网页, 决定网页Page Rank值的主要因素是指向网页的链接个数, 也就是说网页在网络上存在时间越长, 就越有可能被其它网页链接, 导致旧页面等级会比新页面高;但是对于些比如新闻类的某些网页来说, 随着时间的推延, 其重要性就越小。Page Rank算法忽略了网页主题的相关性, 导致结果的相关性和主题性降低, 这是因为人们的查询具有兴趣特征, 所以传统的Page Rank算法对网页排序不能很好的满足用户的实际需要。
为了模拟用户在互联网上的的浏览兴趣, 解决用户访问网页的绝对随机性, 可以采用网页分类技术和链接结构技术相结合, 可以根据类别加以区分网页之间的链接关系。所以网页分类技术可成为传统算法的重要补充技术。
3 Page Rank 算法的改进
针对Page Rank算法中出现的不能很好的辨别用户兴趣的重要性, 设计了一种基于用户兴趣的主题相似度的Page Rank算法的改进算法。在改进算法中, 首先按用户的兴趣将网页进行预分类, 区别不同网页对用户兴趣的重要程度, 从而使排序结果更加接近用户需求。
3.1 网页预分类方法
用户浏览网页的行为, 并不是绝对随机或盲目的, 是和用户的查询主题相关的。网页预处理就是将一个页面得到用户兴趣的关键词, 当然预处理包括去标签及广告噪声、相似网页消除其他部分, 这不在本文探讨之内。
据用户访问网页不是绝对随机这个前提, 选取若干个网页进行排序, 使用户感兴趣的网页靠前排列。按照pagerank算法, 统计出所选取的网页的链入链出量, 计算出每个网页的pagerank值, 以此为基准进行排序。对于网页的预处理, 先根据分类目录将网络信息分类, 然后将爬行到的网页按照网页类别相似度表分类, 利用用户的单击操作和类别相似度表最终确定某网页的类别, 网页类别的确定需要根据用户兴趣来确定。
具体思路是可以按照用户的兴趣给定的分类体系下, 将获得的网页进行分类, 分类体系主要由用户类别兴趣和兴趣权重来表示。将获得的网页根据查询关键词、兴趣目录等进行提取和加权, 通过分类器, 确定网页的类别, 将搜集到的页面分成不同的类别。识别和提取网页中和用户兴趣相对应的关键词, 从而取得该兴趣的特征值以及兴趣程度的权重。用兴趣集来表示若干个兴趣类, 在某个兴趣类别中包含的关键词在该分类下所占的比重就是兴趣权重。
3.2 用户兴趣值表示方法
用户的兴趣可以用向量I={i1 , i2 , i3 , …, in }表示, 对每一兴趣赋其对应的权重, 以区别兴趣程度, 设兴趣对应的兴趣值W={w1 , w2 , w3 , …, wn }。这样对每个网页A可算出所对应的兴趣值, 这里假设网页A用向量D={d1, d2, d3, …, dn) 来表示, 此时, 用户兴趣也可以表示成t维向量, 即Q= {q1 , q 2, q 3, …, qt }, 这些定义见文献[1], 网页用户对应的兴趣值Rp 计算公式为
(3) 式的原理见文献[1]。这里兴趣值W有可能变成负数, 为了避免, 可以先把W值设置大点, 再设一个临界值, 当W值小于这个临界值时就删去这个用户的兴趣, 当W值增加到某个临界值时就可以加入此兴趣。
3.3 Page Rank 算法修正
因此, 在对Page Rank算法进行修正时, 考虑首先对网页进行预处理, 然后在传统的Page Rank算法的基础考虑用户兴趣, 即网页主题相似度因素, 使得用户在进行查询时, 网页的排名Page Rank值是受到这些因素影响的, 这样, 用户查询相关的页面, 对用户比较感兴趣的比较重要网页就会获得较高的Page Rank值。修正后的Page Rank算法可以表示为:
(4) 式其中PR (A) 表示当前网页P的Page Rank值, F用来调整传统网页用户兴趣重要性, 其重要性可以根据搜索需要来调节, 也可以设成常数, 搜索引擎可以提供一个参数变化方案, 如果认为兴趣最重要的话, 可以让F的值最大。
因此本文在原有搜索引擎算法基础上, 设计基于用户兴趣的个性化搜索引擎框架 (图1) , 这是考虑用户兴趣、用户反馈处理两个模块和用户兴趣特征数据库提出的原型系统, 使用户用户能够搜索到自己最想要的信息。
4 实验结果
为了验证算法改进后的效果, 用网络爬虫工具随机选取若干个兴趣主题, 分别利用传统搜索引擎算法和改进后的算法在Google上连续抓取一定数量的网页。经过数据预处理, 将其导入到数据库中进行对比, 实验结果表明, 改进后的算法, 用户搜索信息对兴趣特征值能提高权重。
5 结语
文中在分析了现有Page Rank算法的基础上, 提出了一种基于用户兴趣的的网页预分类方法来改进传统Page Rank算法, 该算法可以有效提高网页的排名。改进后的算法是在基于网页链接结构的排序算法中, 在基于用户兴趣的网页预分类下, 根据用户的点击确定用户的兴趣类别, 进一步分析网页的相似度, 在此基础上, 通过用户对网页兴趣度的计算, 提出一种考虑用户兴趣的Page Rank算法的改进方法, 可以适当提高用户查询信息的准确率。基于用户兴趣的Page Rank改进算法只是一些前期的工作, 还用很多问题需要在以后加强工作, 例如关于网页预分娄方法和用户兴趣值计算, 以及传统Page Rank值考虑用户兴趣值后的表示方法, 仍有待今后进一步研究。
参考文献
[1]李强, 王申康.一种基于PageRank算法原理的会员人气度排序算法[J].计算机系统应用, 2008, (1) :27-31.
[2]袁毅, 徐曼.PageRank判断网页质量的可靠性分析[J].情报杂志, 2006, (2) :58-61.
[3]邵晶晶.基于PageRank排序算法改进的若干研究[D].武汉:华中师范大学, 2009.
【用户选择算法】推荐阅读：
多用户调度算法论文06-07
中继选择算法06-10
区域选择算法07-05
网络选择算法07-05
算法选择器08-26
选择排序算法10-07
克隆选择算法10-08
免疫记忆克隆选择算法07-17
选择性集成算法10-30
动态克隆选择算法论文01-30