无线D2D网络中基于干扰感知的最小跳数的路由选择方法

摘要

本发明提供一种无线D2D网络中基于干扰感知的最小跳数的路由选择方法，包括：1)限制D2D节点的发射功率；2)计算每一跳最高传输速率，构建最小化路径跳数的路由优化模型；3)根据MR‑DA算法逐跳建立从源节点到目的节点的路由。本发明可以在保证蜂窝用户通信质量和D2D传输速率的前提下，建立跳数尽可能少的路由。通过考察候选节点到目的节点的最高传输速率以及候选节点与当前节点和目的节点的位置关系，本发明综合考虑了地理位置信息和干扰控制，使生成的路径在靠近目的节点的同时远离基站，减小对蜂窝通信的干扰，增大每一跳的传播能力。理论分析和仿真结果表明，本发明方法具有复杂度低、平均跳数少、中断概率低的优点。

权利要求

1.一种无线D2D网络中基于干扰感知的最小跳数的路由选择方法，用于一蜂窝网络和D2D网络并存的小区，其中D2D网络由N个设备节点构成，所述设备节点通过共享蜂窝网上行频谱资源进行通信，其特征在于，包括以下步骤：

1)限制D2D网络中设备节点的发射功率；

2)在设备节点的发射功率受限的条件下，计算D2D网络中每一跳的最高传输速率，从而构建最小化路径跳数的路由优化模型；

2-1)计算节点i到节点j的最高传输速率Ri,j，其计算公式如下：其中，B为蜂窝用户的带宽，Δj为节点j和蜂窝用户之间的距离，di,j为节点i和节点j之间的距离；A是天线的固定功率增益，P0为蜂窝用户的发射功率，Pi为节点i的发射功率，d0为蜂窝用户和基站之间的距离，Di为节点i和基站之间的距离，η为路径损耗指数，ρth为蜂窝链路信干比SIR的门限值；

2-2)使用(π(k),π(k+1))代表路径中的第k跳，计算第k跳的最高传输速率，其计算公式如下：

2-3)将最小化路径跳数的路由问题归纳为一个数学模型，其模型的具体表达式如下：其中，代表源节点Msr到目的节点Mdest的路径节点对， 是 的势；式(6)中第一个限制条件代表D2D通信每一跳的传输速率不低于门限值Rth；

3)根据MR-DA算法，对路由优化模型逐跳建立从源节点Msr到目的节点Mdest的路由，得到路由的选择方法；所述的MR-DA算法具体为：

3-1)对于当前节点π(k)，计算作为其接收节点π(k+1)的候选节点集合Nk，其计算公式如下：

3-2)根据集合Nk中各节点与当前节点π(k)和目的节点的位置关系，将Nk划分为两个集合Φ1和Φ2，Φ1的计算公式如下：Φ2的计算公式如下：

3-3)优先从集合Φ1中根据到目的节点最高传输速率最大化准则选取节点π(k+1)，若则，从Φ2中按到目的节点最高传输速率最大化准则选取节点π(k+1)，该准则下节点选取的计算公式为：

3-4)令k＝k+1，重复步骤3-1)至步骤3-3)，直到建立起从Msr到Mdest的路由。

2.根据权利要求1所述的无线D2D网络中基于干扰感知的最小跳数的路由选择方法，其特征在于，所述步骤1)的具体方法如下：

1-1)计算基站端的路径增益，其计算公式如下：

其中，P0为蜂窝用户的发射功率，d0为蜂窝用户和基站之间的距离，η为路径损耗指数，A是天线的固定功率增益；

1-2)计算蜂窝链路的信干比SIR，并且设置其值不低于门限值ρth，其计算公式如下：其中，Pi为节点i的发射功率，Di为节点i和基站之间的距离；

1-3)由式(2)计算出节点i发射功率Pi的上界，其计算公式如下：

说明书

无线D2D网络中基于干扰感知的最小跳数的路由选择方法

技术领域

[0001] 本发明属于无线通信技术领域，尤其涉及一种无线D2D网络中基于干扰感知的最小跳数的路由选择方法。

背景技术

[0002] 近几年来，随着无线技术的飞速发展和仪器设备的日益智能化，D2D(设备到设备)作为一种可以提供高质量设备间通信的局域无线通信技术而受到广泛关注，在传统的蜂窝通信系统中引入D2D技术更是可以提高蜂窝网络的频谱效率和系统容量。当D2D节点以underlay的方式共享蜂窝网络资源时，D2D节点和蜂窝用户间存在交叉干扰。在共享蜂窝上行频谱的场景中，D2D通信影响基站对蜂窝信号的接收，降低了基站端的SIR(信干比)；蜂窝用户影响D2D链路的通信质量，限制了D2D每一跳的最高传输速率。为避免对蜂窝用户造成过度干扰，保证蜂窝通信的质量，D2D节点的发射功率受到限制，常常需要建立多跳路由来实现源节点和目的节点间的通信。在这种干扰环境下，多跳路由的设计需要联合考虑地理位置信息、干扰控制、D2D通信速率需求和算法复杂度等因素。同时，所选择的路由应具有尽可能少的跳数以减小端到端通信延时。针对以上问题，研究高效合理的路由选择算法具有重要意义。

发明内容

[0003] 针对上述缺陷或不足，本发明提供了无线D2D网络中基于干扰感知的最小跳数的路由选择方法。

[0004] 为达到以上目的，本发明的技术方案为：

[0005] 一种无线D2D网络中基于干扰感知的最小跳数的路由选择方法，用于一蜂窝网络和D2D网络并存的小区，其中D2D网络由N个设备节点构成，所述设备节点通过共享蜂窝网上行频谱资源进行通信，包括以下步骤：

[0006] 1)限制D2D网络中设备节点的发射功率；

[0007] 2)在设备节点的发射功率受限的条件下，计算D2D网络中每一跳的最高传输速率，从而构建最小化路径跳数的路由优化模型；

[0008] 3)根据MR-DA算法，对路由优化模型逐跳建立从源节点Msr到目的节点Mdest的路由，得到路由的选择方法。

[0009] 所述步骤1)的具体方法如下：

[0010] 1-1)计算基站端的路径增益，其计算公式如下：

[0011]

[0012] 其中，P0为蜂窝用户的发射功率，d0为蜂窝用户和基站之间的距离，η为路径损耗指数，A是天线的固定功率增益；

[0013] 1-2)计算蜂窝链路的信干比SIR，并且设置其值不低于门限值ρth，其计算公式如下：

[0014]

[0015] 其中，Pi为节点i的发射功率，Di为节点i和基站之间的距离；

[0016] 1-3)由式(2)计算出节点i发射功率Pi的上界，其计算公式如下：

[0017]

[0018] 所述步骤2)的具体步骤如下：

[0019] 2-1)计算节点i到节点j的最高传输速率Ri,j，其计算公式如下：

[0020]

[0021] 其中，B为蜂窝用户的带宽，Δj为节点j和蜂窝用户之间的距离，di,j为节点i和节点j之间的距离；

[0022] 2-2)使用(π(k),π(k+1))代表路径中的第k跳，计算第k跳的最高传输速率，其计算公式如下：

[0023]

[0024] 2-3)将最小化路径跳数的路由问题归纳为一个数学模型，其模型的具体表达式如下：

[0025]

[0026] s.t.:Rπ(k),π(k+1)≥Rth  (6)

[0027] π(1)＝Msr

[0028] π(K+1)＝Mdest

[0029] 其中，代表源节点Msr到目的节点Mdest的路径节点对， 是 的势；式(6)中第一个限制条件代表D2D通信每一跳的传输速率不低于门限值Rth。

[0030] 所述步骤3)的具体方法如下：

[0031] 3-1)对于当前节点π(k)，计算作为其接收节点π(k+1)的候选节点集合Nk，其计算公式如下：

[0032]

[0033] 其中，Rth为D2D通信每一跳的最低传输速率；

[0034] 3-2)根据集合Nk中各节点与当前节点π(k)和目的节点的位置关系，将Nk划分为两个集合Φ1和Φ2，Φ1的计算公式如下：

[0035]

[0036] Φ2的计算公式如下：

[0037]

[0038] 3-3)优先从集合Φ1中根据到目的节点最高传输速率最大化准则选取节点π(k+1)，若 则，从Φ2中按到目的节点最高传输速率最大化准则选取节点π(k+1)，该准则下节点选取的计算公式为：

[0039]

[0040] 3-4)令k＝k+1，重复步骤3-1)至步骤3-3)，直到建立起从Msr到Mdest的路由。

[0041] 与现有技术比较，本发明的有益效果为：

[0042] 本发明提供了一种无线D2D网络中基于干扰感知的最小跳数的路由选择方法，首先通过限制D2D节点的发射功率保证了蜂窝链路的SIR不低于某一门限值；其次，在设备节点的发射功率受限的条件下，计算D2D网络中每一跳的最高传输速率，从而构建最小化路径跳数的路由优化模型，考虑了靠近目的节点和远离基站以减小对蜂窝通信的干扰这两个因素，从而达到减少路由跳数的效果；所生成的路由具有较少的平均跳数，从而减小了端到端延时；同时该算法具有较低的路由中断概率和较低的计算复杂度，从而保证了高效性。

[0043] 进一步的，通过将候选节点集合Nk划分为集合Φ1和Φ2，并优先从Φ1中选取接收节点，避免了所选节点与目的节点“背道而驰”的情况，使路由生成更具有方向性；在从Φ1或Φ2中选取接收节点时，我们依据到目的节点最高传输速率最大化准则，通过考察候选节点到目的节点的最高传输速率，我们综合考虑了靠近目的节点和远离基站以减小对蜂窝通信的干扰这两个因素，从而达到减少路由跳数的效果；仿真实验表明，本发明中的MR-DA算法在平均跳数和路由中断概率这两个指标上的性能均与最优解Dijkstra算法的性能相近，并且优于已有的FN算法和CD算法；理论分析表明，MR-DA算法的计算复杂度与FN算法和CD算法相同，且低于Dijkstra算法。

附图说明

[0044] 图1为本发明的系统模型图；

[0045] 图2为本发明中MR-DA路由算法的流程图；

[0046] 图3为MR-DA路由算法和三种对比算法所生成路由的仿真示例；

[0047] 图4为不同的D2D节点个数情况下，四种路由算法对路由平均跳数的仿真曲线；

[0048] 图5为不同的D2D节点个数情况下，四种路由算法对路由中断概率的仿真曲线。

具体实施方式

[0049] 下面结合附图对本发明做详细描述。

[0050] 本发明所使用的系统模型中共有N个D2D设备节点和若干个蜂窝用户。该系统中的D2D节点通过共享蜂窝网上行频谱进行直接通信，因此D2D节点与蜂窝用户间存在交叉干扰。在D2D网络中，定义一个源节点和一个目的节点组成一个D2D通信对。由于发射功率有限，这两个节点间常常需要通过其他节点来建立一条多跳路由，以实现从源节点到目的节点的通信。在这里，我们假设不同的通信对使用不同的频率，并且同一条多跳路由上的D2D节点均使用同一频率。这样，我们只需考虑一条D2D多跳路由和一个蜂窝用户之间的干扰，如图1所示。

[0051] 针对以上系统模型，本发明的主要步骤包括：

[0052] 1)为避免对蜂窝用户产生过度干扰，限制D2D节点的发射功率：

[0053] 记蜂窝用户的发射功率为P0，蜂窝用户和基站之间的距离为d0。假定小尺度衰落通过分集技术得到了补偿，只考虑大尺度路径损耗，则在基站处接收到蜂窝用户的功率G0为：

[0054]

[0055] 其中，η是路径损耗指数，A是天线的固定功率增益，A的取值由放大器和天线等因素决定。

[0056] 为了保障D2D通信的服务质量(QoS)，规定D2D每跳的最低传输速率为Rth。将节点i和节点j之间的距离记作di,j,i＝1,2,...,N,j＝1,2,...,N，记节点i和基站的距离为Di，节点j和蜂窝用户之间的距离为Δj。若节点i的发射功率为Pi，则蜂窝链路所受干扰必须满足：

[0057]

[0058] 由式(2)我们可以得到节点i发射功率的上限为：

[0059]

[0060] 2)在节点功率受限的条件下，计算每一跳最高传输速率，从而构建最小化路径跳数的路由优化模型；

[0061] 式(3)给出了发射功率Pi的上界，我们令Pi取其上界值以计算D2D每一跳的最高传输速率。用B表示蜂窝用户的带宽，通过香农公式计算出节点i到节点j的最高传输速率Ri,j为：

[0062]

[0063] 我们使用 来表示从源节点Msr到目的节点Mdest所建立路由上所有路径节点对构成的集合，用 表示该集合的势。不失一般性，我们将路径上的节点按顺序排列，并记节点对(π(k),π(k+1))之间的链路为该多跳路由的第k跳。由式(4)可以得到第k跳的最高传输速率为

[0064]

[0065] 由此，我们将最小化路径跳数的路由问题归纳为一个数学模型，其模型的具体表达式如下：

[0066]

[0067] s.t.：Rπ(k)，π(k+1)≥Rth  (6)

[0068] π(K+1)＝Mdest

[0069] π(K+1)＝Mdest

[0070] 式(6)中第一个限制条件代表D2D通信每一跳的传输速率不低于Rth。

[0071] 3)根据MR-DA算法逐跳建立从源节点Msr到目的节点Mdest的路由。

[0072] 根据D2D通信每一跳传输速率不低于Rth的要求，对于当前节点π(k)，通过式(4)可以计算出可作为接收节点π(k+1)的候选节点集合Nk。同时，Nk中也不应该包含前k-1跳中已经走过的节点。由此，可以得到Nk的表达式为：

[0073]

[0074] 我们根据Nk中各节点与当前节点π(k)和目的节点Mdest的位置关系，将集合Nk划分为两个子集Φ1和Φ2，Φ1的计算公式如下：

[0075]

[0076] Φ2的计算公式如下：

[0077]

[0078] 相比于Φ2中的节点，集合Φ1中的节点可以保证逐跳生成的路径朝目的节点延伸，使路由的生成更具有方向性。因此，我们优先从集合Φ1中根据到目的节点最高传输速率最大化准则选取某一节点作为节点π(k+1)，若 则从Φ2中按同样的准则选取节点π(k+1)，该准则下节点选取的计算公式为：

[0079]

[0080] 分析式(10)可知， 越大，则所选择节点距目的节点越近，并且距基站的距离越远。离目的节点越近，则每一跳都尽可能靠近目的节点，从而减少路由跳数；距基站越远，由式(3)可知，节点的发射功率可以越大，从而每一跳的传播距离会更远，也有利于路由跳数的减少。因此，到目的节点最高传输速率最大化准则综合考虑了目的节点、基站、蜂窝用户等地理位置信息，也考虑了干扰控制因素。

[0081] 最后，令k＝k+1，即将选择出的节点π(k+1)作为当前节点，按照式(10)所示的选择方法逐跳生成路径，重复该过程直到建立起从源节点Msr到目的节点Mdest的路由。

[0082] 图2给出了本发明中MR-DA路由算法的流程图，其具体步骤如下：

[0083] 初始化：令π(1)＝Msr,k＝1，表示路由从源节点开始，令 表示路由还未开始生成；

[0084] 步骤1：判断当前节点π(k)是否为目的节点，若是则表明路由已经生成，结束路由建立过程，若不是则进行下一步骤；

[0085] 步骤2：判断当前节点是否可以直接与目的节点通信，即 是否成立，若成立则令接收节点π(k+1)＝Mdest，否则，先按照式(7)计算候选节点集合Nk，再按照式(8)和式(9)将Nk划分为集合Φ1和Φ2，最后按照式(10)选择节点π(k+1)；

[0086] 步骤3：将新生成的路径节点对(π(k),π(k+1))添加进路径节点对集合 中，并令k＝k+1，进入步骤1。

[0087] 图3给出了MR-DA路由算法和三种对比算法的一次路由仿真示例。在该网络拓扑中，Dijkstra算法和本次发明的MR-DA算法均生成了4跳的路由，FN算法生成5跳的路由，而CD算法所生成的路由跳数最多，有7跳。相比于CD算法，Dijkstra算法和MR-DA算法所生成的路由距离基站更远。这是因为CD算法仅仅考虑最大程度地靠近目的节点，忽略了基站带来的影响。而为了限制D2D通信对蜂窝用户产生的干扰，D2D传输节点越靠近基站，其发射功率的上限就会越低，这直接导致下一跳传播距离的减小，从而增加了路由的跳数。类似的问题也会出现在FN算法中，这是因为该算法也没有将下一跳的传播能力纳入考虑因素中。

[0088] 下面，我们给出上述四种路由算法的复杂度分析。首先，我们对三种对比算法：Dijkstra算法、FN算法和CD算法进行简单介绍。

[0089] a)Dijkstra算法

[0090] 定义点集 其中VN是第n个D2D节点。在此点集的基础上进一步定义边的集合 其中，边Ei,j的权值wi,j为：

[0091]

[0092] 由此，式(6)所述的路径跳数最小化问题可以转化为有向图中的最短路径问题，该问题可以通过著名的Dijkstra算法求得最优解。

[0093] b)FN算法

[0094] 该算法在通过角度阈值所限定的区域内，选择满足速率要求的离当前节点距离最远的点作为接收节点。对于当前节点π(k)，其接收节点π(k+1)的计算公式如下：

[0095]

[0096] 其中，Gk(Ψ)的定义为

[0097]

[0098] Ψ＝60°是所取的角度阈值。该算法在控制路由方向性的同时，每一跳都尽可能跳得远一些。

[0099] c)CD算法

[0100] 与FN算法不同，CD算法旨在选取距离目的节点最近的点作为下一跳节点。以当前节点π(k)为例，π(k+1)的选取满足下式：

[0101]

[0102] 现在，我们对本次发明的MR-DA算法和上述三种路由算法的复杂度进行如下分析。首先，我们分析MR-DA算法的复杂度。对于节点π(k)，为确定集合Nk，需要考察π(k)到网络中所有节点的传输速率，该步骤的计算复杂度不超过O(N)。而将集合Nk划分为集合Φ1和Φ2，至多需要考察N个节点与当前节点和目的节点的位置关系，因此其复杂度的上限为O(N)。其余步骤的计算复杂度为O(1)。因此，若路由总跳数为K，则复杂度上限为O(KN)。由于FN算法和CD算法也是通过从Nk中选取节点来逐跳建立路由，因此这两种算法的复杂度与MR-DA算法相同，即为O(KN)。而Dijkstra算法的复杂度为O(N2)。在通常情况下，网络中节点个数较多，K的值远远小于N。因此，MR-DA算法的复杂度远远小于Dijkstra算法。

[0103] 图4和图5给出了上述四种路由算法的性能仿真曲线。

[0104] 仿真条件：考虑一个扇区，该扇区的圆心角设为120°，半径设为500m。蜂窝用户的发射功率P0为23dBm，SIR门限值ρth＝8dB，路径损耗指数η＝3，天线固定功率增益A的选取使得蜂窝用户的发射功率在500m处增益为0dB。源节点、目的节点和蜂窝用户的位置同图3。图中其他节点的拓扑服从在该扇区内(除去以基站为圆心半径为1m的圆形区域)的均匀分布。随后的仿真结果都是通过随机生成1000次拓扑，经过统计平均得到的。

[0105] 图4给出了路由的平均跳数关于网络中D2D节点个数N的曲线。如图所示，Dijkstra算法，FN算法以及本次发明的MR-DA算法，其平均跳数均随N的增加而减小。这是因为随着D2D节点个数的增加，寻找到跳数更少路由的概率也在增加。相反，CD算法的平均跳数有随N的增加而增大的趋势。这是因为在该仿真中，蜂窝用户几乎位于连接源节点和目的节点的线段上，如图3所示。因此，当D2D节点个数增加时，CD算法趋向于选择靠近该线段的路由。路由越靠近该线段，其上的D2D传输节点也就越靠近基站，节点发射功率受到的限制就会越大，从而减小了每一跳的传输距离，导致路由跳数的增加。

[0106] 图5给出了路由中断概率随节点个数N的变化曲线。其中，我们设置参数Rth＝2Mb/s。观察此图可以发现，本次发明的MR-DA算法的中断概率与Dijkstra算法几乎一致，这意味着在中断概率方面，MR-DA算法是近似最优的。这是因为MR-DA算法使路径尽可能远离基站，从而提高了节点发射功率的上限，增大了下一跳成功传输的概率。相反，FN算法和CD算法的中断概率明显较高，这是因为这两种算法都没有考虑下一跳的传播能力。