一种结合威望的D2D通信中继选择算法

王汝言， 缪 懿， 闫俊杰

(1. 重庆邮电大学 通信与信息工程学院，重庆 400065；2. 重庆高校市级光通信与网络重点实验室，重庆 400065)

一种结合威望的D2D通信中继选择算法

王汝言1,2， 缪 懿1,2， 闫俊杰1,2

(1. 重庆邮电大学 通信与信息工程学院，重庆 400065；2. 重庆高校市级光通信与网络重点实验室，重庆 400065)

为了使终端直通通信能够公平有效地选择中继节点，提出了一种基于威望的中继选择算法．利用威望从社会域的角度描述了设备作为中继的意愿和能力; 同时在物理域分析了设备之间在不同传输模式下的数据传输情况; 采用博弈论的方法在候选中继设备中选出适合的中继，避免了社会关系弱、剩余能量低的设备被选作中继．结果表明，与随机选择算法和最大吞吐量算法相比，该算法提高了系统的吞吐量、终端直通链路的覆盖率以及中继选择的合理性．

终端直通;中继;威望;吞吐量

从2015年到2020年，全球移动数据流量将增长近8倍．更多的数据流量将会从蜂窝网络上卸载下[1]，即需要利用新技术分流基站的数据流，减轻基站负担．第三代合作伙伴计划(the 3rd Generation Partnership Project，3GPP)在R12版本中为长期演进(Long Term Evolution，LTE)引入了终端直通(Device-to-Device，D2D)通信技术，以解决近距离服务的使用场景[2]．其通信过程与传统通信明显不同，当两个通信设备在空间上距离比较近时，设备之间可以不通过基站而直接传输数据，其中直接传输数据使用的频谱资源是蜂窝小区的授权频谱资源．引入D2D通信技术后可以带来一系列的益处，例如，大幅提升蜂窝小区的系统容量、网络可容纳用户数以及频谱效率[3]．

由于D2D通信是短距离通信，其有效通信覆盖面积有限，许多应用场景下两个用户并不在直接通信范围内，若仍采用单跳通信模式，则通信链路质量会较差甚至中断．因此可以考虑采用多跳的通信模式，即选择适合的用户作为中继节点进行D2D中继通信[4]．此种方式可以扩大D2D通信的覆盖面积，减轻基站的负载，进而优化整个网络的传输容量和功耗．

目前，因为中继技术的潜在优势，许多关于D2D通信的研究都已将其引入．文献[5]研究了包含D2D通信的蜂窝网中基站的最佳调度．在系统传输容量保证的前提下，通过引入D2D中继协助传输，使某些基站可以暂时关闭，达到节约资源的目的．文献[6]中研究了全双工模式下D2D中继通信的自干扰情况．通过提出的最佳功率分配方法，使D2D中继通信可以在全双工模式下为系统提供传输容量的增益．文献[7]中联合研究了D2D通信的中继选择、子信道分配和功率分配问题，提出了一种迭代算法以解决网络吞吐量最大化的问题，获得了接近最优的结果．文献[8]通过先确定候选中继的范围、后选择中继的两步方法，有效地缩小了D2D通信候选中继的范围，降低了中继选择的复杂度，且提高了系统的吞吐量．文献[9]考虑了D2D通信的功率控制和中继选择，利用博弈论设计出一种竞标的中继选择方法．在基站辅助计算下，获得了系统传输容量的最大收益．文献[10]研究了3种基于物理位置的中继选择方式，通过权衡中继探测代价和系统传输容量增益，得到了最佳的基于物理位置的中继选择方式．从上述文献可以看出，当D2D通信引入中继技术后，整个网络的性能获得有效的提升．但是这些研究都将中继用户进行理想化的处理，即空闲状态的设备都能有效地协助转发数据，并未考虑候选中继的具体情况．而研究D2D通信中继选择的文献多是只在物理域进行研究，以追求网络的吞吐量增益为目的．这种从单一维度选择出的中继是否能适应真实的场景值得思考．从社会域的角度看，由于社会关系、资源受限、隐私保护等原因，设备并不具有较强的协助转发数据的意愿[11]．因此，以上研究并未考虑候选中继设备具体的意愿和能力，在实际场景下极有可能造成用户体验降低和通信链路质量下降的问题．

基于此，笔者首先从社会网络中引入威望这一概念，在社会网络中威望描述了人们寻求帮助时向谁求助的问题．对于小区中的设备，通过设备之间的探测接触率以及设备剩余能量定义了设备的威望值，同时考虑了物理层信道条件和数据传输率的需求．再利用博弈论中一级密封价格报价拍卖方式进行中继设备的选择．设计出的这种基于威望的中继选择算法(based on Prestige for Relay Selection Algorithm， PRSA)，既保证了网络的数据传输率，又考虑了设备持有者的特性和服务质量．

图1 单小区网络构架

1 单小区网络构架

如图1所示，考虑单小区场景，其中包含1个基站(Base Station，BS)，N个空闲的候选中继设备(R1,R2, …,RN)，M个D2D用户(D1,D2, …,DM)以及K个蜂窝用户(U1,U2, …,UK)．整个小区中的无线网络由蜂窝通信和D2D通信构成，移动用户可以进行传统蜂窝传输、D2D直接传输或者D2D中继传输．为了提高频谱资源的利用率，D2D通信复用蜂窝通信的频谱资源．

从物理域的角度看，当采用无线资源非正交复用模式时，无论是D2D直接通信还是D2D中继通信，都会与小区中的某个蜂窝用户产生同频干扰．从社会域的角度看，这些集中在一起的用户彼此之间的社会联系要强于区域外的用户．图1中，若用户活跃在不同的区域，则彼此之间的接触较弱；若用户活跃在相同的区域，则彼此之间的接触较强．而在集中区域中，那些活跃的用户帮助传输数据的意愿更强，因此这类活跃的用户更适合被选作中继．单纯考虑物理域，极有可能选择到通信链路质量好但意愿不强的中继，影响用户的服务质量，不适用于实际场景．所以，笔者从物理属性和社会属性分析通信模型，得到更符合实际场景的中继选择方式．

2 中继选择算法

受社会网络中威望概念的启发，通过设备间的接触率和设备剩余能量，充分考虑移动设备被选作中继的意愿和能力．同时，在物理域分析信道质量，保证系统的吞吐量．最后引入博弈论中的一级密封价格报价拍卖机制进行中继节点的选择．

2.1 基于设备接触和剩余能量的威望

网络中每个移动设备都利用点对点方法感知周围的情况[12]，且每个设备都有一个探测半径，设定每个设备的探测半径是相同的．当两个设备彼此进入对方的探测半径时，相互之间能探测到对方，此时接触开始;当两个设备彼此离开对方的探测半径时，此时接触结束．所以定义设备i和设备j之间的接触间隔Ti,j为

Ti，j={t-t0:Lt(i，j)≤r，i≠j} ,

(1)

其中，t0表示设备i和设备j上一次接触结束的时刻;t表示设备i和设备j紧接着的这一次接触开始的时刻;Lt(i，j)表示在t时刻设备i和设备j之间的物理距离;r表示设备的探测半径．Lt(i,j)≤r，表示设备i和设备j已经互相进入彼此的探测半径，开始接触．

定义用户i与小区中其他用户相遇的平均概率: 设小区中有M个用户，i，j分别是其中任意两个用户，且i≠j，则

(2)

(3)

根据文献[14]提出的无线信道能量模式，且考虑瑞利衰落，则传输l位数据且传输距离为d的发送能耗为

Et(l,d)=Eelecl+lεampd4,

(4)

其中，Eelec为电路损耗常量，εamp是能耗系数．所以中继设备在转发数据后的剩余能量为

(5)

(6)

2.2 物理域分析

以上通过威望从社会域的角度提出了中继选择的原则之一．笔者采用无线资源非正交复用方式，D2D链路复用蜂窝上行链路的频谱资源，两种通信方式之间会产生同频干扰．

图2 信道模型

如图2所示，考虑一个蜂窝小区中的基本情况．包括基站BS、蜂窝用户U1、D2D发送机D1、D2D接收机D2以及中继设备R，采用经典的3节点中继通信模式．中继采用半双工解码转发中继模式，整个传输被分为两个阶段，每一阶段有相同的时隙．D2D通信共享蜂窝通信的频谱资源，为了限制同频干扰，一条D2D链路共享一个蜂窝用户的资源，一个蜂窝用户的资源只能被一条D2D链路共享．

对于D2D直接通信，D2D接收机在接收D2D发送机的信号时也会受到蜂窝上行用户的同频干扰，因此D2D接收到的信噪比为

γD1,D2=PD1hD1,D2/(PU1hU1,D2+σ2) ,

(7)

其中，PD1和PD2分别是D2D发送机和蜂窝用户的发送功率，σ2是信道中的均值为零的高斯白噪声，hD1,D2和hU1,D2分别是D2D发送机到D2D接收机的信道增益和蜂窝用户到D2D接收机的信道增益．信道模型考虑路径损耗和瑞利衰落．路径损耗与距离和路径损耗因子α有关，而每条链路都是独立的瑞利衰落，且期望E[h0]=1，则考虑信道增益hi，j=L-αh0，式中h0是高斯信道系数，是一个常数．因此，根据香农公式，D2D直接通信的传输速率为

RD1，D2=Wlb(1+γD1，D2) ,

(8)

其中，W表示信道宽度．

同理，D2D发送机选择蜂窝模式时，它与基站BS之间的传输速率为

Rcell=Wlb(1+PUhD1，BS/σ2) ．

(9)

对于D2D中继链路，通信过程分为两跳，分别对应T1时隙和T2时隙．第1跳和第2跳的数据传输速率为

(10)

(11)

简单而不失一般性，只要D2D链路的传输速率能够不小于蜂窝链路的最低值，就可以选择D2D模式进行数据传输，所以

mRcell+(1-m)RD2D≥Rcell,

(12)

其中，m∈(0,1)．当m=1时，表示设备选择蜂窝模式．

2.3 中继选择

以上部分分别从社会域和物理域分析了移动设备的属性，在本部分中主要分析怎样选择出满足要求的中继，为此引入博弈论中的一级密封价格报价拍卖机制进行中继节点的选择．

对于D2D中继选择算法，应该考虑复杂度不能太高的算法．复杂度太高会提高中继传输的时延，影响用户的服务质量．假设设备在提交收集到的数据时是可靠的．在这种拍卖中，每个报价者都单独地将报价装入信封，密封以后交于拍卖者，相互之间不知道报价．拍卖者收集所有报价，从中选择出报价最高者获得拍卖物品．获得物品的赢家需要支付自己所出的报价，而未获得物品的竞拍者不需要任何支付．

根据以上思路，中继选择如下：小区移动设备在移动过程中，通过与其他移动设备的历史相遇情况计算了自己在这个网络中与其他移动设备的相遇概率．当D2D直接链路发现难以达到需求的数据传输速率或者链路不能建立时，D2D发送机向周围发送信号通知候选设备进行中继节点的拍卖．在收到信号需要作为候选中继进行竞标时，周围设备会探测D2D接收端，计算剩余能量以形成威望;同时计算链路的传输速率．因此，对于每个中继候选节点而言，在竞标时所出的价格包含两个方面:威望值和实时中继传输速率．

为了节约设备的资源及降低设备转发数据的复杂度，设定正在进行数据传输的设备不进行中继的竞拍，在接收到竞标信号后可以不参与．对于每个中继候选节点，它的策略集合是

(13)

其中，φ表示空集，即不上传威望和数据速率信息；β表示设备威望．

D2D发送机作为拍卖者，并不需要关心中继候选者的数目，且候选中继数目越多越好，即使在报价的过程中有其他节点进入，也不会影响整个拍卖．因为报价只有一轮，且新加入的节点没有收到拍卖者发出的拍卖信息[15]，因此新加入的设备不属于候选设备．

当拍卖者D2D发送机收到候选中继设备的报价后，会从中选出赢家作为中继用户．因为关注的主要问题是链路的传输速率和中继设备的威望，因此效用函数构建如下:

(14)

其中，a是单位速率的价值常数．中继设备的传输速率和威望值都是越大越好．等式中大于零，表示D2D中继方式可达到的数据速率应该比蜂窝通信的数据速率大；否则，不能保证用户链路的质量，也失去了中继通信的意义．

3 仿真分析

通过仿真对以上算法的性能进行验证，对比算法包括基于最大吞吐量的中继选择算法(based on Maximum Throughput for Relay Selection agorithm，MTRS)；单一D 2D直接通信，即D 2D通信模式下只进行D 2D直接通

表1 主要仿真参数

信；随机选择中继算法(Random Relay Selection algorithm， RRS)．主要仿真参数如表1所示．

如图3所示，有10对用户需要通信时，不考虑其他蜂窝用户的吞吐量．比较了随着小区中空闲用户数的增加4种模式下10对用户的吞吐量，因此可以直观地看出中继技术带来的收益，φmin= 0.3．当选择进行蜂窝模式通信时，这些用户就是蜂窝用户，小区中的空闲用户的多少不影响其通信．在RRS模式、MTRS模式和PRSA模式下，空闲用户数的增加意味着中继通信可能性的增加．对于PRSA模式，当判定D2D通信不能进行时，用户就选择蜂窝通信模式．从图中3可以看出，在相同空闲用户数下，因为随机选择的中继用户信道条件可能不满足通信，系统吞吐量在使用笔者提出的方法下大于RSS方法的，但要小于MTRS模式的．

图4展示了随着空闲用户数的增加，D2D用户在不同中继选择方式下可以进行D2D通信的可能性，即D2D覆盖率，φmin= 0.3．在小区中有10对用户可以进行D2D通信，可以选择3种D2D通信模式(D2D直接通信、RRS和PRSA)．D2D直接通信不需要中继协助传输，所以小区中空闲用户的数量对其覆盖率没有影响．对于笔者提出的模式和随机选择中继模式，当小区中空闲用户数量增多时，可以作为中继设备的用户就增多，进行中继通信的可能性增大．但是随机选择的中继有可能信道质量差或者设备的剩余能量严重不足，就会造成D2D链路不能建立; 而笔者提出的模式考虑了这些问题，因此相比较性能更好．例如在空闲用户为200时，笔者提出的模式比随机选择模式覆盖率高约20%．

图3 4种模式下吞吐量随空闲用户数的变化图4 3种模式下覆盖率随空闲用户数的变化

在图5中展示了RRS和PRSA模式下的威望选择．有10对用户将进行D2D中继通信，可以通过RRS和PRSA模式，比较了这10对D2D用户选择的中继的威望之和．从图中可见，RRS模式下威望增长幅度较小，而PRSA模式下威望增长幅度较大．而且随着空闲用户数的增加，两者的差距变大，这是因为空闲用户数的增加使候选的中继设备越多，而笔者提出的模式选择了其中性能较好的用户．但是当空闲用户数较小时，候选中继设备不充足，笔者提出的方法由于条件的限制有可能不能选择中继，因此在这种情况下RRS模式选择的中继的威望之和可能大于PRSA模式．所以，笔者提出的PRSA方法在用户密集的情况下更具有优势．从社会域的角度，威望越高，说明选择的设备更有意愿和能力作为中继，保证了中继选择的公平合理．

图5 两种模式下威望的比较图6 吞吐量与剩余能量阈值的关系

图7 吞吐量与中继移动速度的关系

在图6中展示了剩余能量阈值对4种模式下D2D链路吞吐量的影响．设定小区中有250个空闲设备，且有10对设备需要通信．在蜂窝模式下，吞吐量不受空闲用户的影响; 在RRS和MTRS模式下，由于不考虑剩余能量阈值，所以吞吐量也不会受影响．对于笔者提出的PRSA模式，随着阈值的增加，可选作中继的设备减少，能进行D2D中继通信的可能性降低，PRSA的吞吐量会小于RRS，逼近蜂窝模式．

图7描述了MTRS和PRSA模式下，所选中继的移动速度对中继通信系统吞吐量的影响．以250个空闲用户为例，由图7可知，随着中继的移动速度增加，两种模式的吞吐量都降低了; 但MTRS模式更严重，因为MTRS模式选择的中继设备物理位置都较好，中继的移动对其影响更大．

分析PRSA、MTRS和RRS算法的复杂度．假设有n个空闲用户可以作为中继．在PRSA算法下，候选中继设备记录了历史相遇概率和剩余能量并计算出了目前的威望．D2D发送机获得中继竞标上传的数据后，将威望值由大到小排序，该步骤复杂度为O(n2)．下一步根据威望值由大到小依次判断对应中继的传输速率是否满足条件，其复杂度为O(n)，所以PRSA算法总体复杂度为O(n2)．MTRS算法选择传输速率最大的中继，其复杂度为O(n)，而RRS算法随机选择中继，所以复杂度为O(1)．

4 结 束 语

笔者首次引入社会网络中的威望概念，提出一种基于威望的D2D中继选择算法．在保证系统容量的前提下，从社会域角度考虑设备被选作中继的意愿和能力，使中继的选择更公平合理．其过程首先通过设备之间的历史相遇概率和剩余能量确定设备的威望; 然后考虑信道的物理属性，保证系统的传输容量．最后通过一级密封价格报价拍卖方法选择出适合的中继．与其他D2D中继选择算法相比，笔者考虑了中继设备的社会属性，更符合实际的应用．仿真表明，笔者提出的算法能够在保证中继设备意愿和能力的前提下，提高系统的性能．

参考文献：

[1] CISCO. Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update, 2016-2021 White Paper[R/OL].[2017-03-10]. https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html.

[2] LIN X, ANDREWS J G, GHOSH A, et al. An Overview of 3GPP Device-to-device Proximity Services[J]. IEEE Communications Magazine, 2014, 52(4): 40-48.

[3] 张锐, 李勇朝, 崔建国, 等. LTE-A网络下支持终端直通的资源复用选择策略[J]. 西安电子科技大学学报, 2016, 43(2): 17-22.

ZHANG Rui, LI Yongzhao, CUI Jianguo, et al. Resource Reusing Selection Scheme for Device-to-device Communication Underlaying LTE-A Networks[J]. Journal of Xidian University, 2016, 43(2): 17-22.

[4] ALKURD R, SHUBAIR R M, ABUALHAOL I. Survey on Device-to-device Communications: Challenges and Design Issues[C]//Proceedings of the 2014 IEEE 12th International New Circuits and Systems Conference. Piscataway: IEEE, 2014: 361-364.

[5] LI Y, JIN D P, HUI P, et al. Optimal Base Station Scheduling for Device-to-device Communication Underlaying Cellular Networks[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(1): 27-40.

[6] ZHANG G P, YANG K, LIU P, et al. Power Allocation for Full-duplex Relaying-based D2D Communication Underlaying Cellular Networks[J]. IEEE Transactions on Vehicular Technology, 2015, 64(10): 4911-4916.

[7] KIM T, DONG M. An Iterative Hungarian Method to Joint Relay Selection and Resource Allocation for D2D Communications[J]. IEEE Wireless Communications Letters, 2014, 3(6): 625-628.

[8] ZHAO M, GU X Y, WU D, et al. A Two-stages Relay Selection and Resource Allocation Joint Method for D2D Communication System[C]//Proceedings of the IEEE Wireless Communications and Networking Conference. Piscataway: IEEE, 2016: 7565070.

[9] CHEN Y C, HE S B, HOU F, et al. Optimal User-centric Relay Assisted Device-to-device Communications: an Auction Approach[J]. IET Communications, 2015, 9(3): 386-395.

[10] FENG H, WANG H B, CHU X L, et al. On the Tradeoff between Optimal Relay Selection and Protocol Design in Hybrid D2D Networks[C]//Proceedings of the 2015 IEEE International Conference on Communication Workshop. Piscataway: IEEE, 2015: 705-711.

[11] WU D P, ZHANG H P, WANG H G, et al. Quality of Protection-driven Data Forwarding for Intermittently Connected Wireless Networks[J]. IEEE Wireless Communications, 2015, 22(4): 66-73.

[12] WANG R Y, YANG H P, WANG H G, et al. Social Overlapping Community Aware Neighbor Discovery for D2D Communications[J]. IEEE Wireless Communications, 2016, 23(4): 28-34.

[13] ZHANG B T, LI Y, JIN D P, et al. Social-aware Peer Discovery for D2D Communications Underlaying Cellular Networks[J]. IEEE Transactions on Wireless Communications, 2015, 14(5): 2426-2439.

[14] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[15] MUKHERJEE A, KWON H M. General Auction-theoretic Strategies for Distributed Partner Selection in Cooperative Wireless Networks[J]. IEEE Transactions on Communications, 2010, 58(10): 2903-2915.

RelayselectionalgorithmincorporatedwithprestigeforD2Dcommunication

WANGRuyan1,2，MIAOYi1,2，YANJunjie1,2

(1. School of Telecommunication and Information Chongqing Univ. of Posts and Telecommunications, Chongqing 400065, China; 2. Optical Communication and Network Key Lab. of Chongqing, Chongqing 400065, China)

For the sake of enabling the device-to-device (D2D) communication to impartially and effectively select the relay node, a prestige-based relay selection algorithm is proposed. From a social domain perspective,the prestige is used to describe the will and ability of an equipment to be selected as a relay. Meanwhile the data transmission of the equipment in different transmission modes is analyzed. Finally, a suitable relay is selected amongst the candidate relay equipments by the method of game theory. This algorithm avoids a device with a weak social relation and a low residual energy being selected as a relay. The results manifest that the proposed algorithm improves the throughput of the system, the coverage probability of D2D link, and the rationality of the relay selection, compared with the random selection algorithm and the maximum throughput algorithm.

device-to-device; relays; prestige; throughput

2017-01-15

时间：2017-06-29

国家自然科学基金资助项目(61371097,61271261)；重庆市青年科学人才培养计划资助项目(CSTC2014KJRC-QNRC40001)；重庆高校创新团队建设计划资助项目(CXTDX201601020)

王汝言(1969-)，男，教授，博士，E-mail：wangry@cqupt.edu.cn．

http://kns.cnki.net/kcms/detail/61.1076.TN.20170629.1734.028.html

10.3969/j.issn.1001-2400.2018.01.014

TN925.1

A

1001-2400(2018)01-0076-07

(编辑： 郭 华)