高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于加权二部图及贪婪策略的蜂窝网络D2D通信资源分配

申滨 孙万平 张楠 崔太平

申滨, 孙万平, 张楠, 崔太平. 基于加权二部图及贪婪策略的蜂窝网络D2D通信资源分配[J]. 电子与信息学报, 2023, 45(3): 1055-1064. doi: 10.11999/JEIT220029
引用本文: 申滨, 孙万平, 张楠, 崔太平. 基于加权二部图及贪婪策略的蜂窝网络D2D通信资源分配[J]. 电子与信息学报, 2023, 45(3): 1055-1064. doi: 10.11999/JEIT220029
SHEN Bin, SUN Wanping, ZHANG Nan, CUI Taiping. Resource Allocation Based on Weighted Bipartite Graph and Greedy Strategy for D2D Communication in Cellular Networks[J]. Journal of Electronics & Information Technology, 2023, 45(3): 1055-1064. doi: 10.11999/JEIT220029
Citation: SHEN Bin, SUN Wanping, ZHANG Nan, CUI Taiping. Resource Allocation Based on Weighted Bipartite Graph and Greedy Strategy for D2D Communication in Cellular Networks[J]. Journal of Electronics & Information Technology, 2023, 45(3): 1055-1064. doi: 10.11999/JEIT220029

基于加权二部图及贪婪策略的蜂窝网络D2D通信资源分配

doi: 10.11999/JEIT220029
基金项目: 国家自然科学基金(62071078)
详细信息
    作者简介:

    申滨:男,教授,研究方向为认知无线电、动态频谱接入等

    孙万平:男,硕士生,研究方向为图论、无线资源分配

    张楠:女,硕士生,研究方向为NOMA技术

    崔太平:男,讲师,研究方向为认知无线电、车联网等

    通讯作者:

    申滨 shenbin@cqupt.edu.cn

  • 中图分类号: TN929.5

Resource Allocation Based on Weighted Bipartite Graph and Greedy Strategy for D2D Communication in Cellular Networks

Funds: The National Natural Science Foundation of China (62071078)
  • 摘要: D2D(Device-to-Device)通信是解决频谱资源稀缺问题的关键技术之一。该文研究蜂窝网络中“many-to-many”的复杂场景,即单个RB(Resource Block)可以分配给多对D2D用户重用,并且允许单个D2D用户对使用多个RB,其中D2D用户对数量远多于蜂窝用户设备(Cellular User Equipment, CUE)数量和RB数量。考虑CUE对资源使用具有更高优先级,将此优化问题分解为蜂窝用户资源分配和D2D用户资源重用两个阶段。在第1阶段,提出基于公平性的循环二部图匹配(Fairness-based Circular Bipartite Graph Matching, FCBGM)算法,将现有的RB分配给所有CUE,以最大化蜂窝用户和速率。在第2阶段,分别提出基于二部图的资源重用(Bipartite Graph-based Resource Reuse, BGRR)算法和基于贪婪策略的资源重用(Greedy-based Resource Reuse, GRR)算法,目标是将已经分配给CUE的RB再次分配给D2D用户重用,以最大化系统和速率,同时确保CUE的基本速率需求。仿真结果表明,在D2D用户对数量远大于CUE数量和RB数量的情况下,与现有典型算法相比,所提算法能够有效提高系统和速率,增加D2D接入率,同时兼顾用户公平性和服务质量需求。
  • 图  1  系统模型

    图  2  不同D2D用户对数量下的D2D和速率

    图  3  D2D用户对数量对CUE和速率的影响

    图  4  平均系统和数据速率

    图  5  每个算法所支持的通信链路数量

    图  6  D2D接入率与D2D用户对数量的关系

    图  7  不同D2D用户对数量下的Jain公平指数

    表  1  本文所提算法与现有典型算法的比较

    算法名称执行过程性能对比
    系统和速率D2D接入率公平性
    GORA[13]GORA独立完成整个资源分配仅次于BGRR和GRR最差最差
    ORA[8]CUE资源分配:FCBGMD2D资源重用:ORA仅优于GSA仅优于GORA仅优于GORA
    GSA[9]CUE资源分配:FCBGMD2D资源重用:GSA最差最优仅次于BGRR
    FCBGM + BGRR(本文算法)CUE资源分配:FCBGMD2D资源重用:BGRR最优仅次于GSA和GRR最优
    FCBGM + GRR(本文算法)CUE资源分配:FCBGMD2D资源重用:GRR仅次于BGRR仅次于GSA仅次于BGRR和GSA
    下载: 导出CSV

    表  2  信道增益

    ${\text{R}}{{\text{B}}_k}$信道增益${\text{A}}{\mkern 1mu} {\mkern 1mu} \Rightarrow {\mkern 1mu} {\mkern 1mu} {\text{B}}{\mkern 1mu} {\mkern 1mu} $(${\text{from A to B}}$)
    $g_{m,{\text{B}}}^k$蜂窝通信链路${C_m} \Rightarrow {\text{BS}}{\mkern 1mu} {\mkern 1mu} $
    $g_{n,{\text{t}},n,{\text{r}}}^k$D2D通信链路${D_{n,{\text{t}}}} \Rightarrow {D_{n,{\text{r}}}}$
    $g_{n,{\text{t}},{\text{B}}}^k$干扰链路${D_{n,{\text{t}}}} \Rightarrow {\text{BS}}{\mkern 1mu} {\mkern 1mu} $
    $g^k_{m,n,{\text{r} } }$干扰链路${C_m} \Rightarrow {D_{n,{\text{r}}}}$
    $g_{_{n,{\text{t,}}n',{\text{r}}}}^k$干扰链路${D_{n,{\text{t}}}} \Rightarrow {D_{n',{\text{r}}}}$
    下载: 导出CSV
    算法1 基于公平性的循环二部图匹配算法
     输入:$\mathcal{C},\mathcal{R}$
     输出:${{\boldsymbol{A}}_{\text{C}}}$
     1:初始化
       ${{\boldsymbol{A}}_{\text{C}}} = {[\alpha _m^k]_{M \times K}}$,$\alpha _m^k = 0$,$\forall m \in \mathcal{M},\forall k \in \mathcal{K}$,${\mathcal{R}_1} = \mathcal{R}$
     2:While ${\mathcal{R}_1} \ne \varnothing $ do
     3:根据$\mathcal{C}$和${\mathcal{R}_1}$构造加权完全二部图${\boldsymbol{G}} = \left( {{{\boldsymbol{V}}_1},{{\boldsymbol{V}}_2},{\boldsymbol{E}},{\boldsymbol{W}}} \right)$
     4:添加虚拟顶点,使得$\left| {{{\boldsymbol{V}}_1}} \right| = \left| {{{\boldsymbol{V}}_2}} \right| = L$
     5:根据式(14)计算${{\boldsymbol{W}}_1}$
     6:通过KM算法求解问题式(15)获得${{\boldsymbol{M}}_0}$
     7:获得匹配${{\boldsymbol{M}}^*} \leftarrow {{\boldsymbol{M}}_0} \setminus {{\boldsymbol{E}}_{{\text{virtual}}}}$
     8:更新${{\boldsymbol{A}}_{\text{C}}}$
       for each${e_{m,k}} \in {{\boldsymbol{M}}^*}$do
        $\alpha _m^k = 1$,${\mathcal{R}_1} \leftarrow {\mathcal{R}_1} \setminus {\text{ R}}{{\text{B}}_k}$
       end for
     9: end While
    下载: 导出CSV
    算法2 基于二部图的资源重用算法
     输入:$\mathcal{C},\mathcal{R},\mathcal{D}$
     输出:${{\boldsymbol{A}}_{\text{C}}},{{\boldsymbol{A}}_{\text{D}}}$
     1:初始化
      $\beta _n^k = 0$,${R_{n,k}} = 0$,${R'_{m,k,n}} = 0$,${f_{n,k}} = 1$,$\Delta {R_{n,k}} = 0$,
      $\forall n \in \mathcal{N},\forall k \in \mathcal{K},\forall m \in \mathcal{M}$
     2:根据FCBGM算法求得${{\boldsymbol{A}}_{\text{C}}}$,根据式(22)计算${\boldsymbol{R}}_{{\text{C}},{\text{RB}}}^{{\text{req}}}$
     3:While${\boldsymbol{f}} \ne {\boldsymbol{0}}$do
     4:根据$\mathcal{D},\mathcal{R}$构造加权二部图${\boldsymbol{G'}} = ({{\boldsymbol{V'}}_1},{{\boldsymbol{V'}}_2},{\boldsymbol{E'}},{\boldsymbol{W'}})$
     5:添加虚拟顶点使得$\left| {{{{\boldsymbol{V'}}}_1}} \right| = \left| {{{{\boldsymbol{V'}}}_2}} \right| = L'$
     6:令${f_{n,k}} = 0$$\forall n,k \in \left\{ {1,2, \cdots ,L'} \right\}$
     7:根据式(23)计算权重矩阵${{\boldsymbol{W'}}_1}$并更新${\boldsymbol{f}}$
     8:if${f_{n,k}} = 0$,$\forall n,k \in \left\{ {1,2, \cdots ,L'} \right\}$then
       break
      else
     9: 把${{\boldsymbol{W'}}_1}$作为KM算法的输入,获得最大权完美匹配${{\boldsymbol{M'}}_0}$
     10: 删除${{\boldsymbol{M'}}_0}$中与虚拟顶点关联的边,得到匹配${\boldsymbol{M}}_1^*$
     11: 根据重用标准(1)和标准(2)更新${{\boldsymbol{A}}_{\text{D}}}$
     12:end While
    下载: 导出CSV
    算法3 基于贪婪策略的资源重用算法
     输入:$\mathcal{C},\mathcal{R},\mathcal{D}$
     输出:${{\boldsymbol{A}}_{\text{C}}},{{\boldsymbol{A}}_{\text{D}}}$
     1:初始化
      $\beta _n^k = 0$,${R_{m,k}} = 0$,$\forall n \in \mathcal{N},\forall k \in \mathcal{K},\forall m \in \mathcal{M}$
     2:根据FCBGM算法求得${{\boldsymbol{A}}_{\text{C}}}$,根据式(16)更新${{\boldsymbol{R}}_{\text{C}}}$
     3:假设D2D用户重用RB,根据式(17)、式(18)、式(19)、
      式(20)分别计算${R_{n,k}}$,${R'_{m,k,n}}$,$\Delta {R'_{n,k}}$,$\Delta {R_{n,k}}$
     4:找出$\Delta {\boldsymbol{R}}$中最大值对应的D2D和RB以及与该RB关联的CUE
      $\left( {n*,k*} \right) = \arg \max \Delta {R_{n,k}},\forall n \in \mathcal{N},\forall k \in \mathcal{K}$
      $m* = \{ m:\alpha _m^{k*} = 1,\forall m \in \mathcal{M}\} $
     5:计算${C_{m*}}$的传输速率
      ${R_{m*}} = {R'_{m*,k*,n*}} + \displaystyle\sum\nolimits_{k' = 1,k' \ne k*}^K {{R_{m*,k'}}} $
     6:判断${D_{n*}}$重用${\text{R}}{{\text{B}}_{k*}}$是否满足重用标准来决定资源重用结果
      if $\Delta {R_{n*,k*}} \ge 0$ and ${R_{m*}} \ge R_{m*}^{{\text{req}}}$ then
       $\beta _{n*}^{k*} = 1$ and ${R_{m*,k*}} = {R'_{m*,k*,n*}}$
       转到步骤3
      else if $\Delta {R_{n*,k*}} \ge 0$ and ${R_{m*}} < R_{m*}^{{\text{req}}}$ then
       $\Delta {R_{n*,k*}} = - {\text{ }}\infty $
       转到步骤4
      end if
    下载: 导出CSV

    表  3  主要仿真参数

    参数数值
    蜂窝层单小区
    蜂窝半径500 m
    RB数量$K$25
    CUE数量$M$10
    D2D用户对数量$N$35~70
    CUE的最大发射功率$P_m^{{\text{max}}}$24 dBm
    D2D用户对的最大发射功率$P_n^{{\text{max}}}$24 dBm
    CUE的最小速率需求$R_m^{{\text{req}}}$5 bit/(s·Hz)和15 bit/(s·Hz)
    路径损耗常数$G$10–2
    路径损耗指数$\gamma $3
    大尺度衰落增益$F$标准差为8 dB的对数正态阴影
    小尺度衰落增益$h$均值为1的指数分布
    D2D用户对的收发距离50 m
    噪声功率谱密度–174 dBm/Hz
    下载: 导出CSV
  • [1] WEI Lili, HU R Q, QIAN Yi, et al. Enable device-to-device communications underlaying cellular networks: Challenges and research aspects[J]. IEEE Communications Magazine, 2014, 52(6): 90–96. doi: 10.1109/MCOM.2014.6829950
    [2] CAO Jin, MA Maode, LI Hui, et al. A survey on security aspects for 3GPP 5G networks[J]. IEEE Communications Surveys & Tutorials, 2020, 22(1): 170–195. doi: 10.1109/COMST.2019.2951818
    [3] LIANG Le, XIE Shijie, LI G Y, et al. Graph-based resource sharing in vehicular communication[J]. IEEE Transactions on Wireless Communications, 2018, 17(7): 4579–4592. doi: 10.1109/TWC.2018.2827958
    [4] 易鑫, 裴二荣. D2D辅助NB-IoT系统的传输设备数优化算法[J]. 重庆邮电大学学报:自然科学版, 2021, 33(4): 606–613. doi: 10.3979/j.issn.1673-825X.201910310378

    YI Xin and PEI Errong. Transmission device number optimization algorithm for D2D-assisted NB-IoT system[J]. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition, 2021, 33(4): 606–613. doi: 10.3979/j.issn.1673-825X.201910310378
    [5] AHMED M, LI Yong, WAQAS M, et al. A survey on socially aware device-to-device communications[J]. IEEE Communications Surveys & Tutorials, 2018, 20(3): 2169–2197. doi: 10.1109/COMST.2018.2820069
    [6] WAQAS M, NIU Yong, LI Yong, et al. A comprehensive survey on mobility-aware D2D communications: Principles, practice and challenges[J]. IEEE Communications Surveys & Tutorials, 2020, 22(3): 1863–1886. doi: 10.1109/COMST.2019.2923708
    [7] ZHANG Shangwei, LIU Jiajia, GUO Hongzhi, et al. Envisioning device-to-device communications in 6G[J]. IEEE Network, 2020, 34(3): 86–91. doi: 10.1109/MNET.001.1900652
    [8] FENG Daquan, LU Lu, YUAN-WU Y, et al. Device-to-device communications underlaying cellular networks[J]. IEEE Transactions on Communications, 2013, 61(8): 3541–3551. doi: 10.1109/TCOMM.2013.071013.120787
    [9] ZHAO Wentao and WANG Shaowei. Resource sharing scheme for device-to-device communication underlaying cellular networks[J]. IEEE Transactions on Communications, 2015, 63(12): 4838–4848. doi: 10.1109/TCOMM.2015.2495217
    [10] HAMDOUN S, RACHEDI A, and GHAMRI-DOUDANE Y. Radio resource sharing for MTC in LTE-A: An interference-aware bipartite graph approach[C]. 2015 IEEE Global Communications Conference (GLOBECOM), San Diego, USA, 2015: 1–7.
    [11] KÖSE A and ÖZBEK B. Resource allocation for underlaying device-to-device communications using maximal independent sets and knapsack algorithm[C]. 2018 IEEE 29th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), Bologna, Italy, 2018: 1–5.
    [12] CAI Xuejia, ZHENG Jun, and ZHANG Yuan. A Graph-coloring based resource allocation algorithm for D2D communication in cellular networks[C]. 2015 IEEE International Conference on Communications (ICC), London, UK, 2015: 5429–5434.
    [13] ZHANG Rongqing, CHENG Xiang, YANG Liuqing, et al. Interference Graph-based resource allocation (InGRA) for D2D communications underlaying cellular networks[J]. IEEE Transactions on Vehicular Technology, 2015, 64(8): 3844–3850. doi: 10.1109/TVT.2014.2356198
    [14] KAI Caihong, LI Hui, XU Lei, et al. Joint subcarrier assignment with power allocation for sum rate maximization of D2D communications in wireless cellular networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(5): 4748–4759. doi: 10.1109/TVT.2019.2903815
    [15] LAI Weikuang, WANG Y C, LIN H C, et al. Efficient resource allocation and power control for LTE-A D2D communication with pure D2D model[J]. IEEE Transactions on Vehicular Technology, 2020, 69(3): 3202–3216. doi: 10.1109/TVT.2020.2964286
    [16] ABANTO-LEON L F, KOPPELAAR A, and DE GROOT S H. Graph-based resource allocation with conflict avoidance for V2V broadcast communications[C]. 2017 IEEE 28th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), Montreal, Canada, 2017: 1–7.
    [17] LI Y B, DONG G, and LIU D D. An improved multi-cell resource allocation scheme based on graph theory[C]. 2015 International Conference on Information and Communications Technologies (ICT 2015), Xi'an, China, 2015: 1–6.
    [18] FERDOUSE L, WOUNGANG I, ANPALAGAN A, et al. Energy efficient downlink resource allocation in cellular iot supported H-CRANs[J]. IEEE Transactions on Vehicular Technology, 2021, 70(6): 5803–5816. doi: 10.1109/TVT.2021.3076825
  • 加载中
图(7) / 表(6)
计量
  • 文章访问数:  809
  • HTML全文浏览量:  303
  • PDF下载量:  118
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-01-10
  • 修回日期:  2022-05-29
  • 网络出版日期:  2022-06-10
  • 刊出日期:  2023-03-10

目录

    /

    返回文章
    返回