基于RA-IDNC的D2D辅助F-RANs协作重传方案.pdf

文章编号：1003-0530（2023）08-1510-11第 39 卷 第 8 期2023 年8 月信号处理Journal of Signal ProcessingVol.39 No.8Aug.2023基于RA-IDNC的D2D辅助F-RANs协作重传方案姚玉坤 孙宇 谢雨珈 张斐翔（重庆邮电大学通信与信息工程学院，重庆 400065）摘 要：针对D2D辅助F-RANs场景中网络资源利用不充分、重传平均完成时延较高的问题，提出了一种基于速率感知IDNC（Rate perception IDNC，RA-IDNC）的D2D辅助F-RANs重传策略，通过利用不同频段的蜂窝链路和带外D2D链路进行网络编码传输。在重传阶段，首先推导了D2D辅助F-RANs中使用网络编码重传的最小完成时间公式；然后利用图论的方法构造终端和增强远程无线电头（enhanced Remote Radio Head，eRRH）联合的RA-IDNC图，将最小化重传完成时间问题转换为联合图的最大权重独立集搜索问题，并综合考虑链路丢包率、终端丢失数据包个数、设备接口传输速率、接收终端个数等因素设计权重，为了降低运算复杂度，采用贪婪算法对联合RA-IDNC图进行搜索选取最优的编码传输策略；最后，利用接口传输速率不一致造成的发送持续时间不同，搜索满足再次发送条件的设备，并构建空闲时间下设备的联合RA-IDNC图，从提前处于空闲状态的终端和eRRH中搜索可行的编码传输方案，在不增加传输时间的基础上尽可能多的恢复单次重传过程中终端丢失数据包的个数。仿真结果表明，与现有的RA-IDNC编码方案相比，本文所提方案能够有效提高F-RANs中的重传效率，降低重传平均完成时间。关键词：RA-IDNC；D2D通信；蜂窝通信；雾无线接入网；协作重传中图分类号：TN929.5 文献标识码：A DOI：10.16798/j.issn.1003-0530.2023.08.016引用格式：姚玉坤，孙宇，谢雨珈，等.基于RA-IDNC的D2D辅助F-RANs协作重传方案 J.信号处理，2023，39（8）：1510-1520.DOI：10.16798/j.issn.1003-0530.2023.08.016.Reference format：YAO Yukun，SUN Yu，XIE Yujia，et al.D2D-assisted F-RANs cooperative retransmission scheme based on RA-IDNC J.Journal of Signal Processing，2023，39（8）：1510-1520.DOI:10.16798/j.issn.1003-0530.2023.08.016.D2D-assisted F-RANs Cooperative Retransmission Scheme Based on RA-IDNCYAO Yukun SUN Yu XIE Yujia ZHANG Feixiang（School of Communications and Information Engineering，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）Abstract:Aiming at the problems of insufficient utilization of network resources and high average completion delay of retransmission in D2D assisted F-RANs scenarios，a D2D assisted F-RANs retransmission strategy based on Rate perception IDNC（RA-IDNC）was proposed.Network coding transmission is carried out by using cellular links in different frequency bands and out-of-band D2D links.In the retransmission stage，the minimum completion time formula of retransmission using network coding in D2D assisted F-RANs is derived.Then，the RA-IDNC graph combined with the terminal and the enhanced Remote Radio Head（eRRH）is constructed using the graph theory method，and the problem of minimizing the completion time of retransmission is transformed into the maximum weight independent set search problem of the union graph.The weight is designed by considering factors such as link packet loss rate，number of terminal lost packets，transmission rate of device interface and number of receiving terminals.In order to reduce the computational complexity，greedy algorithm is 收稿日期：2023-05-08；修回日期：2023-05-30基金项目：国家自然科学基金（61971080）资助项目第 8 期姚玉坤 等：基于RA-IDNC的D2D辅助F-RANs协作重传方案used to search the joint RA-IDNC graph and select the optimal encoding transmission strategy.Finally，based on the different transmission duration caused by inconsistent interface transmission rates，the device that meets the retransmission condition is searched，and the joint RA-IDNC diagram of the device under idle time is constructed，and the feasible encoding transmission scheme is searched from the terminal that is idle in advance and eRRH.The number of packets lost by the terminal in a single retransmission process can be recovered as much as possible without increasing the transmission time.Compared with the existing RA-IDNC encoding scheme，simulation results show that the scheme mentioned in this article is able to efficaciously increase retransmission efficiency in F-RANs and decrease the average length of time of retransmission.Key words:RA-IDNC；device-to-device communication；cellular communication；fog radio access network；cooperative retransmission1引言随着用户需求的爆炸性增长，无线电接入网的传输速率和服务质量也需要得到提高。雾无线接入网（Fog Radio Access Networks，F-RANs）通过边缘缓存和集中控制进行内容传递，能够有效地满足5G蜂窝网络通信流量日益增长的需求1。同时为应对用户流量激增对无线网络带来的巨大负担，将基站流量卸载至用户并在用户之间直接进行数据交互的设备到设备（Device-to-Device，D2D）通信技术为其提供了一种有效的解决方案2。D2D通信技术可以与 F-RANs 相结合，这个集成系统被称为D2D辅助的F-RANs3，通过云基站将流行的文件下发至支持缓存的增强远程无线电头（enhanced Remote Radio Head，eRRH）并利用用户之间的D2D链路进行合作通信，在资源利用、减少用户内容交付时间以及减轻前端链接负担方面有着显著的优势4。Ahlswede 等5在 2000 年第一次提出了提高网络吞吐量的新研究领域：网络编码（Network Coding，NC）。按照编码系数是否固定选择可以分为随机线性网络编码（Random Linear Network Coding，RINC）6和机会式网络编码（Opportunistic Network Coding，ONC），其中立即可解网络编码（Instantly Decodable Network Coding，IDNC）作 为 ONC 的 子类，通过简单异或方式将接收到的不同数据包进行编码传输从而降低编解码时延，能够很好的平衡吞吐量和时延性能7-8。因此越来越多的学者选择将IDNC应用于不同网络中，以解决网络传输完成时间最小化问题9-14。文献 9 在蜂窝和D2D异构的网络中，使用配备双接口的设备进行网络编码重传，针对RLNC和IDNC分别提出了对应联合编码方案。为了避免D2D网络场景中应用IDNC产生的传输冲突和解码冲突，文献 10 开发了一种低复杂度分簇网络编码方案以解决最小化传输时延问题。文献 11 在 F-RANs场景下使用局部 IDNC图找到设备的最优编码包并通过构造合作图搜寻无碰撞的传输设备。文献 12 针对需求不同的接收终端构造两层IDNC图以利用不需要的数据包提供编码机会，减少了网络的完成时延。文献 13-14 在传统的IDNC基础上引入缓存网络编码（Cache IDNC，C-IDNC），考虑接收到的不可解码编码包对后续传输的影响，增加终端的解码机会。然而上述文献在使用NC减小网络传输完成时间和重传时延上只考虑了网络层对恢复数据包时延的影响忽视了物理层接口发送速率的因素，设备在发送编码包时默认选择接收终端中的最小信道容量作为接口的发送速率以保证终端的成功接收。但是较低的发送速率会造成重传发送持续时间的增加，因此，为了在网络中获得最小的重传完成时间需要在编码策略和发送速率之间取得平衡。速率感知 IDNC（Rate perception IDNC，RA-IDNC）的出现则为解决跨层网络编码提供了新的解决思路15-21，与传统的IDNC图不同，RA-IDNC将接口可行的发送速率融入顶点的构造和权重设计中，以平衡不同发送速率和对应接收终端个数对重传时延的影响，从而搜索出最佳的编码传输策略。文献21 将 RA-IDNC 应用于云无线电接入网络（Cloud radio access networks，C-RANs），通过搜寻RA-IDNC图找到RRH最优的编码传输组合。文献 17 设计F-RANs下拥有三级缓存设备的网络编码策略，利用三级缓存设备同时对丢包用户进行数据的编码恢复。文献 19-20 针对配备双接口的异构设备进行研究，通过LTE和Wi-Fi技术同时从两个eRRH获取编码包，减少了网络重传次数。然而现有的RA-1511信号处理第 39 卷IDNC结合F-RANs的编码重传研究，只单方面关注了eRRH或D2D对重传性能的影响，针对D2D辅助的F-RANs场景中联合使用蜂窝链路的eRRH通信和D2D链路的终端通信并结合物理层速率进行编码重传的研究仍有欠缺。综上所述，本文以最小化D2D辅助F-RANs的重传完成时间为目标，提出基于RA-IDNC的D2D辅助F-RANs协作重传方案（D2D Assisted F-RANs Cooperative Retransmission scheme based on RA-IDNC，DAFCR）。在重传阶段，通过设计联合的RA-IDNC图并采用贪婪算法搜索出可行的编码传输策略；同时考虑接口发送速率不一致导致部分设备提前处于空闲，在空闲时间内再次搜索可行的发送设备进行编码传输，以最大化单次传输的恢复丢包个数，降低网络重传平均完成时间。2网络模型及相关定义2.1网络层模型D2D辅助F-RANs模型如图1所示，由一个云基站（Cloud Base Station，CBS），N 个单天线 eRRH（N=e1，e2，en）和 K 个终端用户（K=u1，u2，uk）构成。其中所有用户共同需要接收 M 个数据包（M=P1，P2，PM）；由于链路质量的不稳定造成链路之间的传输存在丢包，假设终端到终端和eRRH到终端的丢包率分别为k，j和i，j且链路之间的丢包率相互独立，并且蜂窝链路和D2D链路使用不同频段同时通信。每个eRRH都随机缓存了终端所需的部分数据包，缓存个数为|Fn|=M，en N，其中为 eRRH的缓存比，表示 eRRH缓存的数据包个数与总的数据包个数之比，取值范围为0 1。CBS、eRRH和终端UE拥有各自的通信范围CBS、Cen和Cuk，所有编码传输决策均由CBS决定。传输共分为两个阶段，在广播阶段，CBS将用户共同需求的M个数据包通过蜂窝链路广播发送至K个用户，由于无线链路传输的不稳定造成每个终端用户只成功接收到了部分需要的数据包；在重传阶段通过使用蜂窝链路的eRRH和使用带外D2D链路的终端用户进行联合的编码重传直至恢复所有用户需求的数据包，假设重传阶段前所有终端拥有的数据包构成完整的包集合，各终端数据包根据是否被成功接收可以划分为两类：1）终端UEi拥有的数据包集合Hi：由终端UEi正确接收的数据包组成。2）终端UEi想要的数据包集合Wi：由终端UEi未正确接收的数据包组成。2.2物理层模型为了准确衡量接口的传输速率，收发终端之间采用的信道通信容量如公式（1）所示13，其中Wuk表示发送终端的带宽，huk，ul表示发送终端uk到接收终端ul的复杂信道增益；Quk表示发送终端的发送功率；2表示高斯噪声方差。CCuk，ul=Wuklog2(1+Quk|huk，ul22)（1）同样Wen表示发送eRRH en的带宽，en，ui为en到接收终端ui的复杂信道增益；Qen表示发送en的发送功率，因此en与接收终端ui之间的信道通信容量为公式（2）所示：CCen，ui=Wenlog2(1+Qen|en，ui22)（2）与现有文献相同，本文假设任何传输装置eRRH和终端可以调整自身发送功率以获取相应的传输速率Ren，ul和Ruk，ui，此外，如果设备传输速率小于或等于该设备到接收终端的信道容量(Ren，ulCCen，ulor Ruk，ui CCuk，ui)，则接收终端能够正确接收到eRRH或发送终端传输的数据，否则接收终端将无eRRH1eRRH2UE1UE2UE5UE4eRRH3UE6UE3CBS蜂窝链路UEeRRHCBSeRRH通信范围UE7D2D传输CBS通信范围 图1D2D辅助F-RANs通信模型Fig.1D2D assisted F-RANs communication model1512第 8 期姚玉坤 等：基于RA-IDNC的D2D辅助F-RANs协作重传方案法成功接收。假设发送eRRH以最终速率ren，t向一组接收终端发送编码包，则本次传输的发送持续时间为Ten，t=Bren，t，其中B为编码包或数据包的大小；同样发送终端以最终速率ruk，t发送编码包时的发送持续时间为Tuk，t=Bruk，t，本次传输中的最大发送持续时间为Tmax，t=maxn N&k KTen，t，Tuk，t。假设每个终端设备都配备有单天线，采用半双工通信方式，每个终端可以选择通过蜂窝链路与eRRH进行通信或通过D2D链路与范围内的其余终端通信。此外，假设分配的D2D链路频段为ISM频段，即采用带外的D2D方式进行通信，因此蜂窝链路与D2D链路共同传输不会产生额外的干扰。本文所涉及的符号如表1所示。2.3相关定义定义1 拓扑连接矩阵（Topological Connection Matrix，TCM）：反映设备之间包括eRRH与终端、终端与终端是否能够相互通信的（K+N）N 维关系矩阵。TCM=yi，j=1 uj(Cei|Cui)0 uj(Cei|Cui)（3）定义 2 状态反馈矩阵（State Feedback Matrix，SFM）：CBS根据终端接收数据包后返回的ACKNACK确认消息建立的KM维反馈矩阵，表示终端丢失和拥有的数据包信息。SFM=fi，j=1 Pj Wi0 Pj Hi（4）定义 3 信道容量矩阵（Channel capacity Matrix，CM）：由所有的eRRH到终端和终端之间的信道容量组成的（K+N）N维矩阵。CM=CCen，ul CCuk，ui，if yi，j=1，if yi，j=0（5）定义 4 累积时延增量（Accumulated Delay Increment，ADI）：如果终端用户在第t次传输中没有收到任何可立即解码的编码包，则该用户将增加Tmax，t的时延。ADIi，t=ADIi，t-1+0，|(kuk，t fen，t)Wi|=1 Tmax，t，other（6）定 义 5 用 户 预 期 完 成 时 间（User expected completion Time，UT）：终端用户ui在经过 t次传输后恢复自身所有丢失数据包的预计时间。UTiB|Wi，0Rui，t+ADIi，t（7）其中|Wi，0|表示重传开始前终端用户ui丢失的数据包个数，Rui，t表示终端用户ui在第t次传输之前能够立即解码的传输速率的谐波平均值，ADIi，t表示第t次传输前ui的累积时延增量。定 义 6 重 传 总 完 成 时 间（Total completion Time for Retransmission，TTR）：从重传阶段开始到恢复网络中所有终端用户自身丢失数据包的过程中，所有终端用户完成时间的总和。TTR=i KUTi（8）表1本文主要符号及含义Tab.1Main symbols and meanings in this article符号uienn,jk,jCBS,Cen,Cukfen,t,kuk,tu(fen,t),(kuk,t)Ntra,KtraWen,Wuk含义终端设备UEi增强远程无线电头eRRHneRRHn到接收终端UEj的链路丢包率UEk到UEj的链路丢包率CBS、eRRHn、UEk对应的通信范围发送eRRHn和终端UEk在第t次传输发送的编码数据包发送eRRHn和终端UEk对应的接收终端集当前时刻t的发送eRRH集和发送终端集发送eRRHn和终端UEk对应的带宽符号CCen,ui,CCuk,uiRen,ui,Ruk,ulren,t,ruk,tG(V,E)Ten,t,Tuk,tTmax,tTidleen,t,Tidleuk,tBFn含义eRRHn和UEk到终端UEi的信道容量eRRHn和UEk到接收终端UEi的可行的发送速率eRRHn和UEk作为发送方的最终发送速率终端和eRRH联合的RA-IDNC图第t次传输中eRRHn和UEk发送持续时间第t次传输中最长的发送持续时间第t次传输中eRRH和UE的剩余时间传输文件大小eRRHn缓存的部分数据包集1513信号处理第 39 卷3协作重传方案D2D辅助F-RANs的网络编码协作重传方案通过使用蜂窝链路和带外D2D链路选择eRRH和发送终端以共同恢复一组用户终端的丢失数据包，首先分析了影响重传完成时间的因素并构建最小完成时间的非线性公式，然后通过基于图论的方法构造联合RA-IDNC图搜索权重最大独立集找到最优的编码发送策略，最后利用发送接口发送速率不一致导致的时间剩余，在空闲时间内再次寻找编码机会，以最大程度恢复丢包个数。如图2所示，为2个eRRH和5个终端用户构成的F-RANs通信场景示例。所有终端需要接收数据包P1-P4，由于链路不稳定在基站广播后每个终端用户接收数据包情况如图2（a）所示；eRRH缓存数据包情况和发送速率如图2（b）所示，其中eRRH1缓存数据包 P1、P2、P4，eRRH2缓存数据包 P1、P3、P4，发送速率 0 表示该终端超出了 eRRH 的通信范围；D2D 网络拓扑连接情况和发送速率如图 2（c）所示。3.1问题分析D2D辅助F-RANs的网络重传完成时间最小化问题涉及发送eRRH和发送终端、对应编码传输策略以及接口发送速率三方面的联合调度问题，因此所有终端用户成功恢复自身丢失数据包的最小完成时间公式如（9）所示。minfen，t，kuk，ten Ntra&uk Ktra&t 1，.，T ui u(fen，t)&ul(kuk，t)t=1Tmax(Ten，t，Tuk，t)（9）subject C1：u(fen，t)u(fen，t)=&(kuk，t)(kuk，t)=，en en Ntra，uk uk KtraC2：(kuk，t)u(fen，t)=，uk Ktra，en NtraC3：fen，t P(Fn)&kuk，t P(Hk)C4：ren minCCen，ui&ruk minCCuk，ul，ui u(fen，t)，ul(kuk，t)C5：ren Rth&ruk Rth条件1保证了任意一个终端不能同时被多个发送终端或eRRH服务；条件2保证了任意一个终端不能同时被eRRH和发送终端服务；条件3保证了任意发送设备发送的编码包为自身所拥有的数据包；条件4保证了发送设备的发送速率满足对应接收终端信道容量需求；条件5保证了满足服务质量的最低速率要求。3.2联合RA-IDNC构造由文献 22 可知公式（9）的非线性问题为 NP难问题，直接求解计算复杂度较高，因此本方案采用基于图论的方式搜索最优的编码传输方案。与现有文献采取的多层IDNC图不同，本方案构造联合的RA-IDNC图G(V，E)对eRRH和终端的编码发送策略进行统一的调度，其中顶点包括eRRH和终端构造的顶点ri，j，k和ri，j，k，利用边的连接条件将冲突顶点相连，通过对联合RA-IDNC图的独立集搜索找到eRRH和终端的最佳编码发送策略。3.2.1联合RA-IDNC顶点构造联合 RA-IDNC 图的顶点由 eRRH 缓存数据包和终端拥有数据包共同创建。在以下两种情况下，从eRRH和终端角度分别生成顶点。1u2u3u4P1P3P1P1P4P2P4u2P5u3P4PP1、P2、P4P1、P3、P44P2P2P3P 4u4210455u0003u2u1u3nF 1u2u3u212.53424u455u(a)终端缓存数据包(a)Terminal Caching Packets(b)eRRH缓存数据包与发送速率(b)eRRH Cache data packet and interface rate(c)D2D拓扑连接情况和发送速率(c)D2D topology connection and transmission rateRe1,ulRe2,ul图2D2D辅助F-RANs通信场景示例Fig.2Example of D2D assisted F-RANs communication scenario1514第 8 期姚玉坤 等：基于RA-IDNC的D2D辅助F-RANs协作重传方案1）为 每 个 eRRH 构 建 顶 点ri，j，k：ei Ntra&Pk(Fi Wj)&uj Cei，表示如果 eRRHi缓存了数据包Pk并且在它的通信范围内存在设备UEj丢失该数据包，则建立顶点，其中r为传输至UEj所有满足条件的可行发送速率。2）为 每 个 终 端 构 建 顶 点vri，j，k：ui Ktra&Pk(Hi Wj)&uj Cui，如果设备UEi自身拥有数据包Pk并且在它的传输范围内存在设备UEj丢失该数据包，则建立顶点，其中r为传输至UEj所有满足条件的可行发送速率。3.2.2联合RA-IDNC边构造本节在同时隙的条件下，为了衡量可行的编码传输策略，避免解码冲突、传输冲突以及速率不同带来的干扰，构造IDNC图的冲突边，满足以下任意一个条件则顶点vri，j，k与vsm，n，l相连：条 件 1：Pk Pl&uj un&Pl Wj|Pk Wn，由同一个发送设备导出的两个顶点对应不同接收终端的不同丢失数据包，且至少一方丢失了另一方参与编码的数据包。条 件 2：Pk Pl&uj=un&(ui=um|ei=em)&Pl，Pk Wj，由同一发送设备导出的两个顶点对应同一个接收终端丢失的两个数据包。条件3：uj=un&(ui um|ei em)，不同发送终端或不同 eRRH 导出的两个顶点对应同一个接收终端。条件 4：(r，s Rei|r，s Rui)&r s，同一发送设备导出的两个顶点发送速率不相同。条件5：ui=un|uj=um，终端同时作为发送方和其他终端的接收方。同样顶点ri，j，k与sm，n，l满足条件 14 中任意一条则顶点相连，同时ri，j，k和vri，j，k顶点之间通过条件6、7相连以构造联合的RA-IDNC图G(V，E)，顶点之间满足以下任意一个条件则顶点相连：条件 6：uj(kui，t)&uj u(fei，t)，同一个接收终端被eRRH和其他发送终端同时服务。条件 7：ui Ktra&ui u(fei，t)，终端同时作为发送方和eRRH的接收方。继图 2中的通信场景示例，构建 eRRH和终端的联合RA-IDNC图如图3所示，虚线代表了满足条件6、7的两类顶点之间的连接情况，灰色顶点为搜索出的一种独立顶点集，表示可行的编码传输策略：其中终端u2以速率2 Mbit/ms传输编码包P1P2至终端u1和u3，eRRH2以速率4 Mbit/ms传输P3至终端u4和u5。3.2.3顶点权重设计为了准确衡量顶点的选择对传输时延的影响，综合考虑链路传输速率、接收终端个数、顶点对应数据包对后续解码的能力以及链路传输成功率四个因素为每个顶点构建权重值。1）考虑发送设备的发送速率，较快的发送速率能够降低单次发送的时间，从而降低网络整体的重传完成时延。1(ri，j，k)=rB（10）2）考虑速率r下发送设备通信范围内满足传输信道容量的接收终端个数，r过大可能导致接收终端的个数减少，从而增加重传的次数。2(ri，j，k)=um(Cei Cui)&r (CCei，um CCui，um)&Wm(Hi Fi)|um|（11）3）考虑接收设备通信范围内与自身丢失同一个数据包的终端个数，优先恢复该终端丢失的数据包，能够在后续的传输时刻中将其传输至范围内的其他终端。3(ri，j，k)=un Cuj&Pk Wnfn，k（12）4）考虑链路的传输成功率，优先满足成功率高的链路能够降低重传的次数，其中eRRH与终端以及终端之间的传输成功率为：1-i，j和1-i，j。联合IDNC图中顶点的权重设置为上述考虑权41,1,121,1,111,1,111,3,252,4,342,4,352,4,442,4,442,5,122,1,1v22,3,2v2.52,4,4v22,4,4v44,5,1v34,5,1v55,4,4v条件15连接情况条件6连接情况条件7连接情况42,5,32.52,4,3v22,4,3v图3D2D辅助F-RANs联合RA-IDNCFig.3D2D assisted F-RANs combined with RA-IDNC1515信号处理第 39 卷重值因素的综合，如式（13）所示：()=(1-i，j)1n=23n，if vri，j，k(1-i，j)1n=23n，if ri，j，k （13）3.2.4贪婪搜索算法由文献 15 证明可知，单次重传时延最小化问题等价于联合IDNC图中最大权重独立集的搜索问题，然而随着网络中无线设备的不断增加，搜索复杂度也会随之升高，因此本节采用贪婪搜索算法对联合IDNC图中的最大权重独立集进行搜索。首先优化顶点的权重，使其能够选择到独立的大量顶点。定义7 非邻接指示器，用于表示IDNC图G(V，E)中顶点之间是否相连接。，=0，(，)1，(，)（14）优化后的顶点权重值为：*()=()G(，)，()（15）首先遍历图中所有节点，找到权重值最大的顶点并记录在集合D中；然后删除与权重值最大顶点相邻的顶点和边，在剩余的图中再次搜索权重最大顶点加入集合 D 中，重复删除相邻顶点和边的操作，直至图中所有节点和边被移除。贪婪搜索算法如表2所示。3.3基于空闲时间的再编码策略在一次重传过程中由于信道容量不同，每个发送eRRH和发送终端的发送持续时间也不相同，造成了部分eRRH和终端提前处于了空闲状态，这部分设备距离单次传输的最长持续时间存在一段空闲时间。发送eRRH和对应的接收终端以及未参与本次传输的 eRRH 空闲时间为：Tidleen，t=Tmax，t-Ten，t，其中未参与eRRH满足Ten，t=0；发送终端和对应的接收终端以及未参与本次传输的终端空闲时间为：Tidleuk，t=Tmax，t-Tuk，t，其中未参与本次传输的终端满足Tuk，t=0。定义8 空闲设备集合（Idle device gather，I）：Ten，t Tmax，t&Tuk，t Tmax，t，由eRRH和终端组成，包括发送持续时间小于最大发送持续时间的eRRH和终端。3.3.1空闲发送设备选择处于空闲设备集合中的终端和eRRH并不能都作为发送方进行编码传输，需要同时满足以下两个条件：1）在空闲设备集合中的终端和eRRH的通信范围内存在其余的空闲终端，并且信道容量满足收发方最小的剩余时间内的传输：Bmin Tidleuk，t，Tidleui，t CCuk，ui（16）Bmin Tidleen，t，Tidleul，t CCen，ul（17）2）在空闲设备集合中的终端和eRRH拥有覆盖范围内其余空闲终端丢失的数据包，并且该数据包不是独立集中搜索出的恢复数据包。对空闲设备集合中的eRRH和终端依次进行判断，同时满足上述两个条件的eRRH和终端则可作为空闲时间内的编码发送方，并记录在集合S中。3.3.2空闲发送设备编码策略为了满足发送方能够在剩余时间内将编码包传输至接收设备，发送eRRH en和发送终端uk到接收终端ul和ui的发送速率应当满足：Bmin Tidleen，t，Tidleul，t Ren，ul CCen，ul（18）Bmin Tidleuk，t，Tidleui，t Ruk，ui CCuk，ui（19）在联合RA-IDNC图中，删除不满足S集合中发送设备条件和发送速率条件的终端生成的顶点和边，则剩余顶点和边构成了空闲时间下的RA-IDNC图，搜索该图的最大权重独立集则为空闲时间下的编码传输策略。由于满足发送条件的发送方一定能够在剩余时间内完成编码包的发送，所以在权重设计时不再考虑发送速率的影响，而是最大化当前表2最大权重独立集贪婪搜索算法Tab.2Maximum weight independent set greedy search algorithm1.输入：TCM、SFM、CM、uk,ulN、enK。2.输出：权重最大独立集D。3.初始化：最大权重独立集D=。4.根据顶点和边连接条件构建联合RA-IDNC。5.根据公式（11）、（12）计算顶点权重。6.whileG do7.选择=argmax G*()8.D D9.删去G中的顶点以及相连的其他顶点。10.end while1516第 8 期姚玉坤 等：基于RA-IDNC的D2D辅助F-RANs协作重传方案速率下恢复数据包的个数，更新顶点权重计算：记RA-IDNC图中由终端ui和eRRH ei导出的顶点中非邻接且速率同为r的顶点集合为Arui和Arei，空闲时间下RA-IDNC图权重更改如公式（20）所示。()=(1-i，j)|Arui，if vri，j，k(1-i，j)|Arei，if ri，j，k（20）由于空闲时间内发送设备需要满足自身与所有接收终端同时处于空闲状态，因此空闲时间段内eRRH en的开始发送时间应当为发送持续时间最长的设备即：Tbeginen=max(Ten，t，Tul，t)，其中ul为空闲时间下RA-IDNC图搜索出的接收终端；同样D2D链路的发送终端uk开始时间为Tbeginuk=max(Tuk，t，Tui，t)，其中ui为空闲时间下发送终端uk对应的接收终端。继图2中的通信场景示例和图3中搜索结果，假设编码包和数据包大小为10 Mbit，则发送终端u2发送持续时间为5 ms，e2发送持续时间为2.5 ms，此时搜索空闲设备为e1、e2和u4、u5，满足发送条件的空闲设备为e2和u4、u5，保留联合RA-IDNC图中满足条件的顶点，如图4所示。在空闲时间内，再次搜索可行的编码策略为e2发送编码包P1P4至终端u4、u5。3.4协作重传步骤在D2D辅助的F-RANs中，应用网络编码进行重传的DAFCR方案总体步骤如下所示：a）终端将自身数据包的接收情况和连接情况传输至云基站，云基站生成TCM、SFM和CM。b）CBS构建联合RA-IDNC图G(，)，并计算顶点对应的权重值选择出权重最大独立集记为集合D。c）对比发送持续时间判断是否存在提前处于空闲的eRRH和终端，如果存在则转d），如果不存在则该独立集D作为eRRH和终端的最优编码传输策略。d）计算空闲设备集合中eRRH和终端的剩余时间，并判断是否存在空闲设备满足传输信道容量和数据包条件，满足则转e），不满足则独立集D作为eRRH和终端的最优编码传输策略。e）将满足条件的eRRH和终端作为空闲发送设备集合S，并根据集合S和速率条件构建空闲时间下的RA-IDNC图，搜索权重最大独立集D，作为空闲传输的可行编码策略，并记录空闲发送开始时间。f）CBS将独立集D和D对应的最优编码传输策略告知eRRH和发送终端。g）eRRH和发送终端发送对应编码数据包，接收终端收到编码包后解码自身的丢包，更新接收信息，并将接收状态反馈给CBS，CBS更新状态反馈矩阵，重复步骤a）g）直到所有用户恢复需要的全部数据包。3.5算法复杂度分析在所提出的DAFCR策略中，每个eRRH和终端都可能成为发送设备，所以需要为共计|N+K|个设备构建顶点。其中每个 eRRH 设备构造顶点个数为V1=|Fn|Cen|，每个终端设备构造顶点个数为V2=|Hk|Cuk|，因此构造所有设备顶点的复杂度为O(NV1+KV2)；构造联合RA-IDNC图的连接条件计算复杂度为O(NV1+KV2)2)；权重计算和使用贪婪算法的权重最大独立集搜索的计算复杂度为O(|R|(NV1+KV2+N+K-1)；遍历联合RA-IDNC图找到空闲时间中满足条件的顶点计算复杂度为O(NV1+KV2)，空闲时间下的RA-IDNC图计算权重和搜索权重最大独立集的计算复杂度为O(|R|(|S V+I-1)，其中V和R分别为满足空闲发送条件的顶点个数和发送速率。所以DAFCR算法总复杂度为O(2(NV1+KV2)+(NV1+KV2)2+|R|(NV1+KV2+N+K-1)+O(|R|(|S|V+I-1)，由于计算复杂度取次数最高项，因此本文提出算法的计算复杂度为O(NV1+KV2)2)。4仿真分析本文使用OPNET14.5进行仿真，将本文所提出的DAFCR方案与仅使用D2D链路的降低