Nothing Special   »   [go: up one dir, main page]

CN108156617B - 一种雾无线接入网中基于图论的协作缓存方法 - Google Patents

一种雾无线接入网中基于图论的协作缓存方法 Download PDF

Info

Publication number
CN108156617B
CN108156617B CN201711181927.XA CN201711181927A CN108156617B CN 108156617 B CN108156617 B CN 108156617B CN 201711181927 A CN201711181927 A CN 201711181927A CN 108156617 B CN108156617 B CN 108156617B
Authority
CN
China
Prior art keywords
vertex
cluster
nodes
wireless access
candidate
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201711181927.XA
Other languages
English (en)
Other versions
CN108156617A (zh
Inventor
蒋雁翔
崔潇婷
郑福春
尤肖虎
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Southeast University
Original Assignee
Southeast University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Southeast University filed Critical Southeast University
Priority to CN201711181927.XA priority Critical patent/CN108156617B/zh
Publication of CN108156617A publication Critical patent/CN108156617A/zh
Application granted granted Critical
Publication of CN108156617B publication Critical patent/CN108156617B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W24/00—Supervisory, monitoring or testing arrangements
    • H04W24/02—Arrangements for optimising operational condition
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W28/00—Network traffic management; Network resource management
    • H04W28/02—Traffic management, e.g. flow control or congestion control
    • H04W28/08—Load balancing or load distribution
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
    • H04W40/04—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
    • H04W40/246—Connectivity information discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
    • H04W40/32—Connectivity information management, e.g. connectivity discovery or connectivity update for defining a routing cluster membership

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

本发明公开了一种雾无线接入网中基于图论的协作缓存方法，包括如下步骤：1、根据F‑AP节点间的距离和负载差，构建接入层F‑AP的连接边集合；2、构建接入层邻接表集合；3、构建最大完全子图
Figure DDA0001479337280000011
4、对接入层的F‑AP节点划分候选协作缓存簇，并计算每个候选协作缓存簇的前传卸载增量值
Figure DDA0001479337280000012
5、以候选协作缓存簇作为顶点，前传卸载增量值作为权值，在含有相同F‑AP的两个不同候选协作缓存簇对应的顶点之间建立边，构建图；6、求解顶点集合的最大权独立子集，所述最大权独立子集中顶点对应的候选协作缓存簇即为使前传卸载量最大的协作缓存簇集合。该方法可以对雾无线接入网中的F‑AP进行合理分簇，且计算复杂度低、全局性能较高。

Description

一种雾无线接入网中基于图论的协作缓存方法
技术领域
本发明涉及一种雾无线接入网中基于图论的协作缓存方法，属于5G移动通信系统中的缓存技术领域。
背景技术
雾无线接入网(F-RAN，Fog-Radio Access Network)作为5G通信系统的新型系统架构，以其缓解前传拥塞和降低通信时延等方面的巨大优势，得到了通信领域的广泛关注。F-RAN中的雾无线接入节点F-AP(Fog-Access Point)能够在非高峰时刻提前缓存流行内容，这是实现前传卸载和时延降低的关键。但是F-AP的存储空间有限，而F-AP覆盖区域上的内容流行度分布较为分散，F-RAN的边缘缓存性能增益因而受到极大地制约。将F-AP划分成簇，节点之间以协作的方式部署并共享缓存内容，可使得节点簇内的缓存容量扩大，簇内的内容流行度分布情况也随之改善，协作缓存可以为进一步提升5G系统性能增益带来巨大帮助。
实际场景中由于F-AP之间的内容流行度分布差异较为复杂，而F-AP呈现密集部署状态，F-AP覆盖区域上的内容请求达到率也随时间变化且不均匀分布，这些因素导致从大量的雾无线接入节点中快速准确地选择合适的协作节点簇非常困难，而不准确的分簇方案极易导致协作缓存的局部性能提升而全局性能较差的结果。
在雾无线接入网中，以往曾假设不同的雾无线接入节点覆盖区域上的内容流行度分布均相同，即服从全局内容流行度分布，在这种假设条件下，若簇内节点数量相同，选择哪些节点成簇进行协作对协作缓存的性能增益是没有影响的，而实际情况下，因用户所具备的独有的内容偏好性，不同的区域上的内容流行度分布存在着较为复杂的差异，在考虑到本地内容流行度分布的差异性之后，协作簇的构建方式直接影响簇内内容流行度分布，从而影响缓存内容部署以及所有节点协作缓存所能获得的前传卸载量，如何将密集部署的雾无线接入节点快速准确地构建为合适的协作簇，使得簇内内容流行度分布的集中性以及簇间内容流行度分布的差异性均得以优化，从而最大程度的提升所有雾无线接入节点协作缓存的总前传卸载量，这是一个非常复杂的问题。
发明内容
发明目的：针对现有技术中存在的问题，本发明提供了一种雾无线接入网中基于图论的协作缓存方法，该方法可以对雾无线接入网中的F-AP进行合理分簇，且计算复杂度低、全局性能较高。
技术方案：本发明采用如下技术方案：
一种雾无线接入网中基于图论的协作缓存方法，所述雾无线接入网接入层中有N个F-AP，所有F-AP构成集合
Figure BDA0001479337260000021
包括如下步骤：
(1)根据F-AP节点间的距离和负载差，构建接入层F-AP的连接边集合ε；
(2)根据接入层F-AP的边连接集合ε，构建接入层邻接表集合
Figure BDA0001479337260000022
(3)根据接入层邻接表集合
Figure BDA0001479337260000023
构建最大完全子图
Figure BDA0001479337260000024
(4)对接入层的F-AP节点划分候选协作缓存簇，并计算每个候选协作缓存簇的前传卸载增量值
Figure BDA00014793372600000213
(5)将步骤(4)中得到的每一个候选协作缓存簇作为一个顶点，在含有相同F-AP的两个不同候选协作缓存簇对应的顶点之间建立边，构建图，令第n个顶点的权值
Figure BDA0001479337260000025
其中，
Figure BDA0001479337260000026
是步骤(4)中求得的第n个候选协作缓存簇的前传卸载增量值；
(6)对步骤(5)中构建的图，求解顶点集合的最大权独立子集，所述最大权独立子集中顶点对应的候选协作缓存簇即为使前传卸载量最大的协作缓存簇集合。
步骤(1)具体包括：初始化集合ε为空集，遍历
Figure BDA0001479337260000027
中的元素，对
Figure BDA0001479337260000028
中第m个节点APm，遍历其他N-1个节点APm'，如果满足条件Dmm'≤γd，且Lmm'≥γl，且集合ε中没有节点对(APm',APm)，则将节点对(APm,APm')加入到集合ε中。
步骤(2)具体包括：
(2.1)对集合
Figure BDA0001479337260000029
中的每个F-AP节点，构建其邻接表集合，对于
Figure BDA00014793372600000210
中第m个节点APm，其邻接表集合
Figure BDA00014793372600000211
由节点APm、所有与节点APm有边连接的节点组成，即：
Figure BDA00014793372600000212
(2.2)对所有F-AP节点的邻接表集合，剔除元素个数为1或者自身是其他F-AP节点邻接表集合的子集的邻接表集合，将剩余的邻接表集合按照集合中元素个数降序排序，构建集合
Figure BDA0001479337260000031
其中M为剔除后剩余的邻接表集合个数。
步骤(3)具体包括：
初始化
Figure BDA0001479337260000032
为空集，i＝1，对集合
Figure BDA0001479337260000033
中的每个元素执行以下步骤：
选定集合
Figure BDA0001479337260000034
中的第i个元素
Figure BDA0001479337260000035
k＝1，j＝1，集合T′初始化为
Figure BDA0001479337260000036
对集合
Figure BDA0001479337260000037
中的第j个元素APj的邻接表集合
Figure BDA0001479337260000038
做如下(A)和(B)判断交集运算：
(A)若
Figure BDA0001479337260000039
则构建第k个集合
Figure BDA00014793372600000310
并且更新
Figure BDA00014793372600000311
k＝k+1；
(B)若
Figure BDA00014793372600000312
则
Figure BDA00014793372600000313
保持不变，并且更新j=j+1。
随着j的变化，对集合
Figure BDA00014793372600000314
中的每一个元素依次执行以上(A)和(B)判断交集运算，运算结束后得到的T′以及每次运算过程中得到的
Figure BDA00014793372600000315
成为
Figure BDA00014793372600000316
中的元素添加到
Figure BDA00014793372600000317
中，并且更新i＝i+1。
随着i的变化，对集合
Figure BDA00014793372600000318
中的每个元素依次执行以上计算，每次计算都将获得
Figure BDA00014793372600000319
中的元素，对集合
Figure BDA00014793372600000320
中的所有元素执行以上计算后，可得到完整的
Figure BDA00014793372600000321
集合。
步骤(4)具体包括：
对步骤(3)得到的集合
Figure BDA00014793372600000322
中的每一个元素对应的最大完全子图顶点集合做拆分，拆分时需满足拆分出的子集合元素个数不小于2的条件；
每个子集合中的元素构成相应的完全子图的顶点，子集合对应的雾无线接入节点集合构成一个候选协作缓存簇，计算每个候选簇的前传卸载增量值，第n个候选簇的前传卸载增量值
Figure BDA00014793372600000323
计算式为：
Figure BDA00014793372600000324
其中
Figure BDA00014793372600000325
代表第n个候选簇，APq代表簇内的雾无线接入节点，λq代表雾无线接入节点APq覆盖区域上的请求到达率，f代表按照流行度降序排列的内容的序号，
Figure BDA00014793372600000326
代表雾无线接入节点APq覆盖区域上第f个本地最流行内容的请求概率，K代表雾无线接入节点m所能缓存的内容数量，
Figure BDA0001479337260000041
代表第n个候选簇中第f个簇内最流行内容的请求概率，Kn代表第n个候选簇中所有雾无线接入节点协作缓存的不相同内容的数量，L代表每个内容的大小。
求解最大权独立子集的具体步骤为：
随机选定一个顶点作为起始顶点，然后在顶点集合中剔除与该顶点有边连接的顶点，本次剔除的顶点组成一个顶点子集；在剩余顶点中选出权值最大的一个顶点，重复上述剔除与顶点子集构建的过程，直到顶点集合为空，每次剔除的顶点构成原始顶点集合的一组独立子集，将顶点集合中的每一个顶点依次作为起始顶点，相应的可得到多组独立子集，在所有独立子集中选出顶点总权值最大的一组，其对应的候选簇即为所求的前传卸载量最大的协作缓存簇集合。
有益效果：与现有技术相比，本发明公开的雾无线接入网中的基于图论的协作缓存方法具有以下优点：1、通过构建顶点的邻接表集合，避免了从不同顶点重复搜索同一个最大完全子图的情况，对邻接表集合做剔除处理，避免了搜索得到的完全子图是其他最大完全子图的一部分这种无效搜索的情况，有利于协作缓存方法的低复杂度实现；2、通过集合分解快速获得候选簇，全面考虑不同协作方式下的前传卸载增量，便于求解全局性能较高的协作缓存簇集合；3、以分阶段的方式，首先利用可低复杂度搜索最大完全子图的优势快速求得候选簇，然后利用最大权独立子集的特点以多项式时间求解出前传卸载量最大的不相交候选簇，整个过程大大简化了直接求解前传卸载量最大的协作簇的运算。
附图说明
图1为雾无线接入网中的基于图论的协作缓存方法的应用场景图；
图2为本发明公开方法的流程示意图。
具体实施方式
本发明公开了一种雾无线接入网中的基于图论的协作缓存方法，下面结合附图进一步阐述本发明。
一种雾无线接入网中基于图论的协作缓存方法，所述雾无线接入网接入层中有N个F-AP，所有F-AP构成集合
Figure BDA0001479337260000042
包括如下步骤：
(1)根据F-AP节点间的距离和负载差，构建接入层F-AP的连接边集合ε；
初始化集合ε为空集，遍历
Figure BDA0001479337260000043
中的元素，对
Figure BDA0001479337260000044
中第m个节点APm，遍历其他N-1个节点APm'，如果满足条件Dmm'≤γd，且Lmm'≥γl，且集合ε中没有节点对(APm',APm)，则将节点对(APm,APm')加入到集合ε中。Dmm′＝||dm-dm′||2，dm和dm′分别代表雾无线接入节点APm和APm'在欧式空间中的坐标，Lmm′＝||λm-λm′||2，λm和λm′分别代表雾无线接入节点APm和APm'覆盖区域上的请求到达率，γd代表雾无线接入节点之间距离的阈值，γl代表负载差的阈值。||·||2表示L2范数算子。
(2)根据接入层F-AP的边连接集合ε，构建接入层邻接表集合
Figure BDA0001479337260000051
(2.1)对集合
Figure BDA0001479337260000052
中的每个F-AP节点，构建其邻接表集合，对于
Figure BDA0001479337260000053
中第m个节点APm，其邻接表集合
Figure BDA0001479337260000054
由节点APm、所有与节点APm有边连接的节点组成，即：
Figure BDA0001479337260000055
(2.2)对所有F-AP节点的邻接表集合，剔除元素个数为1或者自身是其他F-AP节点邻接表集合的子集的邻接表集合，将剩余的邻接表集合按照集合中元素个数降序排序，构建集合
Figure BDA0001479337260000056
其中M为剔除后剩余的邻接表集合个数。
(3)根据接入层邻接表集合
Figure BDA0001479337260000057
构建最大完全子图
Figure BDA0001479337260000058
初始化
Figure BDA0001479337260000059
为空集，i＝1，对集合
Figure BDA00014793372600000510
中的每个元素执行以下步骤：
选定集合
Figure BDA00014793372600000511
中的第i个元素
Figure BDA00014793372600000512
k＝1，j＝1，集合T′初始化为
Figure BDA00014793372600000513
对集合
Figure BDA00014793372600000514
中的第j个元素APj的邻接表集合
Figure BDA00014793372600000515
做如下(A)和(B)判断交集运算：
(A)若
Figure BDA00014793372600000516
则构建第k个集合
Figure BDA00014793372600000517
并且更新
Figure BDA00014793372600000518
k＝k+1；
(B)若
Figure BDA00014793372600000519
则T′保持不变，并且更新j＝j+1。
随着j的变化，对集合
Figure BDA00014793372600000520
中的每一个元素依次执行以上(A)和(B)判断交集运算，运算结束后得到的T′以及每次运算过程中得到的
Figure BDA00014793372600000521
成为
Figure BDA00014793372600000522
中的元素添加到
Figure BDA00014793372600000523
中，并且更新i＝i+1。
随着i的变化，对集合
Figure BDA0001479337260000061
中的每个元素依次执行以上计算，每次计算都将获得
Figure BDA0001479337260000062
中的元素，对集合
Figure BDA0001479337260000063
中的所有元素执行以上计算后，可得到完整的
Figure BDA0001479337260000064
集合。
(4)对接入层的F-AP节点划分候选协作缓存簇，并计算每个候选协作缓存簇的前传卸载增量值
Figure BDA0001479337260000065
对步骤(3)得到的集合
Figure BDA0001479337260000066
中的每一个元素对应的最大完全子图顶点集合做拆分，拆分时需满足拆分出的子集合元素个数不小于2的条件；
所得到的子集合的数量与
Figure BDA0001479337260000067
中的元素有关，即与步骤(3)中添加到
Figure BDA0001479337260000068
中的集合
Figure BDA0001479337260000069
或者
Figure BDA00014793372600000610
自身的规模有关；每个子集合中的元素构成相应的完全子图的顶点，子集合对应的雾无线接入节点集合构成一个候选协作缓存簇，计算每个候选簇的前传卸载增量值，第n个候选簇的前传卸载增量值
Figure BDA00014793372600000617
计算式为：
Figure BDA00014793372600000611
其中
Figure BDA00014793372600000612
代表第n个候选簇，APq代表簇内的雾无线接入节点，λq代表雾无线接入节点APq覆盖区域上的请求到达率，f代表按照流行度降序排列的内容的序号，
Figure BDA00014793372600000613
代表雾无线接入节点APq覆盖区域上第f个本地最流行内容的请求概率，K代表雾无线接入节点m所能缓存的内容数量，
Figure BDA00014793372600000614
代表第n个候选簇中第f个簇内最流行内容的请求概率，Kn代表第n个候选簇中所有雾无线接入节点协作缓存的不相同内容的数量，L代表每个内容的大小。
(5)将步骤(4)中得到的每一个候选协作缓存簇作为一个顶点，在含有相同F-AP的两个不同候选协作缓存簇对应的顶点之间建立边，构建图，令第n个顶点的权值
Figure BDA00014793372600000615
其中，
Figure BDA00014793372600000616
是步骤(4)中求得的第n个候选协作缓存簇的前传卸载增量值；
(6)对步骤(5)中构建的图，求解顶点集合的最大权独立子集，所述最大权独立子集中顶点对应的候选协作缓存簇即为使前传卸载量最大的协作缓存簇集合。求解最大权独立子集的具体步骤为：
随机选定一个顶点作为起始顶点，然后在顶点集合中剔除与该顶点有边连接的顶点，本次剔除的顶点组成一个顶点子集；在剩余顶点中选出权值最大的一个顶点，重复上述剔除与顶点子集构建的过程，直到顶点集合为空，每次剔除的顶点构成原始顶点集合的一组独立子集，将顶点集合中的每一个顶点依次作为起始顶点，相应的可得到多组独立子集，在所有独立子集中选出顶点总权值最大的一组，其对应的候选簇即为所求的前传卸载量最大的协作缓存簇集合。

Claims (3)

1.一种雾无线接入网中基于图论的协作缓存方法，所述雾无线接入网接入层中有N个F-AP，所有F-AP构成集合
Figure FDA0002668756200000011
其特征在于，包括如下步骤：
(1)根据F-AP节点间的距离和负载差，构建接入层F-AP的连接边集合ε；
(2)根据接入层F-AP的边连接集合ε，构建接入层邻接表集合
Figure FDA0002668756200000012
(3)根据接入层邻接表集合
Figure FDA0002668756200000013
构建最大完全子图
Figure FDA0002668756200000014
(4)对接入层的F-AP节点划分候选协作缓存簇，并计算每个候选协作缓存簇的前传卸载增量值，其中第n个候选协作缓存簇的前传卸载增量值为
Figure FDA0002668756200000015
(5)将步骤(4)中得到的每一个候选协作缓存簇作为一个顶点，在含有相同F-AP的两个不同候选协作缓存簇对应的顶点之间建立边，构建图，令第n个顶点的权值
Figure FDA0002668756200000016
其中，
Figure FDA0002668756200000017
是步骤(4)中求得的第n个候选协作缓存簇的前传卸载增量值；
(6)对步骤(5)中构建的图，求解顶点集合的最大权独立子集，所述最大权独立子集中顶点对应的候选协作缓存簇即为使前传卸载量最大的协作缓存簇集合；
步骤(1)具体包括：初始化集合ε为空集，遍历
Figure FDA0002668756200000019
中的元素，对
Figure FDA0002668756200000018
中第m个节点APm，遍历其他N-1个节点APm'，如果满足条件Dmm'≤γd，且Lmm'≥γl，且集合ε中没有节点对(APm',APm)，则将节点对(APm',APm)加入到集合ε中；Dmm′＝||dm-dm′||2，dm和dm′分别代表雾无线接入节点APm和APm'在欧式空间中的坐标，Lmm′＝||λm-λm′||2，λm和λm′分别代表雾无线接入节点APm和APm'覆盖区域上的请求到达率，γd代表雾无线接入节点之间距离的阈值，γl代表负载差的阈值；
步骤(3)具体包括：
初始化
Figure FDA00026687562000000110
为空集，i＝1，对集合
Figure FDA00026687562000000111
中的每个元素执行以下步骤：
选定集合
Figure FDA00026687562000000112
中的第i个元素
Figure FDA00026687562000000113
集合T′初始化为
Figure FDA00026687562000000114
对集合
Figure FDA00026687562000000115
中的第j个元素APj的邻接表集合
Figure FDA00026687562000000116
做如下(A)和(B)判断交集运算：
(A)若
Figure FDA00026687562000000117
则构建第k个集合
Figure FDA00026687562000000118
并且更新
Figure FDA00026687562000000119
k＝k+1；
(B)若
Figure FDA0002668756200000021
则T′保持不变，并且更新j＝j+1；
随着j的变化，对集合
Figure FDA0002668756200000022
中的每一个元素依次执行以上(A)和(B)判断交集运算，运算结束后得到的T′以及每次运算过程中得到的共k-1个集合：
Figure FDA0002668756200000023
这些集合可以表示为
Figure FDA0002668756200000024
成为
Figure FDA0002668756200000025
中的元素添加到
Figure FDA0002668756200000026
中，并且更新i＝i+1；
随着i的变化，对集合
Figure FDA0002668756200000027
中的每个元素依次执行以上计算，每次计算都将获得
Figure FDA0002668756200000028
中的元素，对集合
Figure FDA0002668756200000029
中的所有元素执行以上计算后，可得到完整的
Figure FDA00026687562000000210
集合；
步骤(4)具体包括：
对步骤(3)得到的集合
Figure FDA00026687562000000211
中的每一个元素对应的最大完全子图顶点集合做拆分，拆分时需满足拆分出的子集合元素个数不小于2的条件；
所得到的子集合的数量与
Figure FDA00026687562000000212
中的元素有关，即与步骤(3)中添加到
Figure FDA00026687562000000213
中的集合
Figure FDA00026687562000000214
或者
Figure FDA00026687562000000215
自身的规模有关；
每个子集合中的元素构成相应的完全子图的顶点，子集合对应的雾无线接入节点集合构成一个候选协作缓存簇，计算每个候选簇的前传卸载增量值，第n个候选簇的前传卸载增量值
Figure FDA00026687562000000216
计算式为：
Figure FDA00026687562000000217
其中
Figure FDA00026687562000000218
代表第n个候选簇，APq代表簇内的雾无线接入节点，λq代表雾无线接入节点APq覆盖区域上的请求到达率，f代表按照流行度降序排列的内容的序号，
Figure FDA00026687562000000219
代表雾无线接入节点APq覆盖区域上第f个本地最流行内容的请求概率，
Figure FDA00026687562000000220
代表第n个候选簇中第f个簇内最流行内容的请求概率，Kn代表第n个候选簇中所有雾无线接入节点协作缓存的不相同内容的数量，L代表每个内容的大小。
2.根据权利要求1所述的雾无线接入网中基于图论的协作缓存方法，其特征在于，步骤(2)具体包括：
(2.1)对集合
Figure FDA00026687562000000221
中的每个F-AP节点，构建其邻接表集合，对于
Figure FDA00026687562000000222
中第m个节点APm，其邻接表集合
Figure FDA00026687562000000223
由节点APm、所有与节点APm有边连接的节点组成，即：
Figure FDA0002668756200000031
(2.2)对所有F-AP节点的邻接表集合，剔除元素个数为1或者自身是其他F-AP节点邻接表集合的子集的邻接表集合，将剩余的邻接表集合按照集合中元素个数降序排序，构建集合
Figure FDA0002668756200000032
Figure FDA0002668756200000033
其中M为剔除后剩余的邻接表集合个数，
Figure FDA0002668756200000034
表示这些降序排序的邻接表集合中第i个邻接表集合。
3.根据权利要求1所述的雾无线接入网中基于图论的协作缓存方法，其特征在于，步骤(6)中求解最大权独立子集的具体步骤为：
随机选定一个顶点作为起始顶点，然后在顶点集合中剔除与该顶点有边连接的顶点，本次剔除的顶点组成一个顶点子集；在剩余顶点中选出权值最大的一个顶点，重复上述剔除与顶点子集构建的过程，直到顶点集合为空，每次剔除的顶点构成原始顶点集合的一组独立子集，将顶点集合中的每一个顶点依次作为起始顶点，相应的可得到多组独立子集，在所有独立子集中选出顶点总权值最大的一组，其对应的候选簇即为所求的前传卸载量最大的协作缓存簇集合。
CN201711181927.XA 2017-11-23 2017-11-23 一种雾无线接入网中基于图论的协作缓存方法 Active CN108156617B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201711181927.XA CN108156617B (zh) 2017-11-23 2017-11-23 一种雾无线接入网中基于图论的协作缓存方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201711181927.XA CN108156617B (zh) 2017-11-23 2017-11-23 一种雾无线接入网中基于图论的协作缓存方法

Publications (2)

Publication Number Publication Date
CN108156617A CN108156617A (zh) 2018-06-12
CN108156617B true CN108156617B (zh) 2020-11-20

Family

ID=62469017

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201711181927.XA Active CN108156617B (zh) 2017-11-23 2017-11-23 一种雾无线接入网中基于图论的协作缓存方法

Country Status (1)

Country Link
CN (1) CN108156617B (zh)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108881444B (zh) * 2018-06-22 2020-11-03 东南大学 一种内容流行度分布不一致的雾无线接入网非同步编码缓存方法
CN108881445B (zh) * 2018-06-22 2021-04-27 南京理工大学 一种雾计算中基于古诺博弈的协作缓存方法
CN108900617B (zh) * 2018-07-03 2020-09-18 东南大学 一种雾无线接入网的三层协作式缓存方法
CN109039706B (zh) * 2018-07-03 2021-05-11 东南大学 基于图论的雾无线接入网协作内容部署方法
CN109831790B (zh) * 2019-03-05 2021-11-12 东南大学 雾无线接入网中基于头脑风暴优化算法的协作缓存方法
CN111510477B (zh) * 2020-04-07 2021-05-11 河海大学 基于改进合同网协议和bas的雾计算网络任务卸载方法

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2016114767A1 (en) * 2015-01-13 2016-07-21 Hitachi, Ltd. Location based cooperative caching at the ran
CN106507415B (zh) * 2016-10-20 2019-06-28 北京工业大学 一种面向移动网络的内容缓存及网络协同方法
CN106550039B (zh) * 2016-11-08 2017-08-11 华中科技大学 一种基于sd‑ran的跨层协作内容缓存方法及系统
CN107343304B (zh) * 2017-05-15 2019-10-11 中国科学院信息工程研究所 内容中心网络的协作缓存方法
CN107241790A (zh) * 2017-05-24 2017-10-10 沈阳航空航天大学 基于内容缓存的基站协作节能策略

Also Published As

Publication number Publication date
CN108156617A (zh) 2018-06-12

Similar Documents

Publication Publication Date Title
CN108156617B (zh) 一种雾无线接入网中基于图论的协作缓存方法
CN112488322B (zh) 一种基于数据特征感知聚合的联邦学习模型训练方法
CN111741054B (zh) 一种移动用户深度神经网络计算卸载时延最小化方法
EP3014444A1 (en) Computing connected components in large graphs
CN104936186B (zh) 基于布谷鸟搜索算法的认知无线电网络频谱分配方法
CN112464784A (zh) 一种基于混合并行的分布式训练方法
CN109739585A (zh) 基于spark集群并行化计算的交通拥堵点发现方法
CN112381307A (zh) 一种气象事件预测方法、装置及相关设备
CN114268967B (zh) 无人机辅助移动边缘网络用户匹配方法及装置
CN107659973A (zh) 基于密度改进K‑means算法的超密集网络分簇方法
CN110809066A (zh) IPv6地址生成模型创建方法、装置及地址生成方法
CN113988160A (zh) 一种基于时效性的半异步分层联邦学习更新方法
CN105138607B (zh) 一种基于混合粒度分布式内存网格索引的knn查询方法
CN107133877B (zh) 网络中重叠社团的挖掘方法
CN112183001B (zh) 一种基于超图的集成电路的多级聚类方法
CN113347255A (zh) 边缘服务器选址部署模型及其求解方法
CN112887943A (zh) 一种基于中心度的缓存资源分配方法及系统
CN108614889B (zh) 基于混合高斯模型的移动对象连续k近邻查询方法及系统
CN117574779A (zh) 一种改进量子粒子群的地下水监测网络优化方法
CN117014057A (zh) 一种网络切片资源分配方法、装置及存储介质
CN109039706B (zh) 基于图论的雾无线接入网协作内容部署方法
CN116723547A (zh) 一种雾无线接入网中基于本地化联邦强化学习的协作缓存方法
CN109344259A (zh) 一种基于多层划分框架的rdf分布式存储方法
CN110831106B (zh) 一种基于卷积的分簇方法
CN115344607A (zh) 一种面向图数据的批量流式边点混合切分方法

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant