一种基于节点竞争时延代价模型的缓存部署方法

摘要

本发明公开了一种基于节点竞争时延代价模型的缓存部署方法，在算法执行过程中确定N个节点是否是缓存节点，每次确定一个缓存服务器时确定N个节点作为缓存服务器时的性能，通过每次性能分析寻找到N个节点的最佳链路，确定基于节点竞争时延代价模型的缓存部署方法时间复杂度O(N3)，本发明对于无线Mesh网络等多跳自组织网络中针对节点获得缓存内容传输时延和缓存内容存储代价的权衡值进行了方法部署，减少了无用的链路传输，缓解网络压力，降低整个网络的信令负荷，提高系统无线资源利用率。

说明书

技术领域

本发明属于无线通信技术领域，具体涉及一种基于节点竞争时延代价模型的缓存部署方法。

背景技术

随着移动通信数据流量的飞速增长，其中视频多媒体业务在所有业务中占大多数，在黄金时段或者热门事件爆发时，网络内容资源需求量会急剧增加，可能导致网络崩溃，将高访问率的内容资源缓存到缓存服务器可以拉近资源与用户的距离，大大降低了用户的接入时延，因此，根据不同网络请求分布状况确定缓存服务器位置的缓存服务器部署方法受到广泛研究。

针对无线Mesh网络等多跳自组织网络，缓存服务器部署方法主要采用的是利用最小生成树、斯坦纳树等经典遍历算法将缓存内容从源服务器分发到每个节点，再在基于节点请求状况确定该缓存内容是否缓存。该方法在未考虑节点是否需要缓存内容的情况下，使所有节点都获得缓存内容，再根据节点自身状况判断决定是否缓存，因此具有一定的盲目性，而且在节点最终没有缓存该内容情况下可能进行了一些无用的链路传输，增加了网络的压力。此外，根据整体网络请求分布状况以及网络拓扑结构，再确定最佳缓存服务器部署位置，这个的过程是一个NP-hard(NP：Non-deterministic Polynomial)问题，研究人员通常会将其转化为经典的背包问题、推销员旅行问题等来进行分析，由于此方法求解时间复杂度很高，所以一般用于网络节点是否配置具有缓存能力的缓存服务器的判决中；对于单个缓存内容而言，根据整体网络请求分布状况以及网络拓扑结构，如何在较低时间复杂度情况下，制定其是否缓存于缓存服务器的最佳缓存部署方法是一个有待解决的难题。

缓存内容部署最主要的目标是降低用户获得资源的传输时延，对于无线Mesh网络等多跳自组织网络而言，无论是最小生成树、斯坦纳树的确定还是NP-hard问题目标代价函数的构建，其传输时延代价主要通过跳跃次数来表征的；同时，通过对链路的竞争关系的研究，基于链路的竞争时延代价模型逐渐被研究人员关注，不同于基于跳跃次数的时延代价模型仅考虑节点获得资源的链路跳跃次数，基于链路的竞争时延代价模型考虑了缓存内容传输过程中由于竞争网络传输资源的影响，更具体的反应了网络中节点的传输状况，使得传输时延的表征更合理，由此制定的缓存部署方法能更有效的优化整个网络的传输时延性能。

缓存内容部署带来的传输时延的降低，伴随着的是网络节点对缓存内容存储的能耗和缓存空间成本的增加，如何实现传输时延与缓存内容存储代价的权衡也是缓存部署方法的关键点。

发明内容

本发明所要解决的技术问题在于针对上述现有技术中的不足，提出了一种基于节点竞争时延代价模型的缓存部署方法，解决针对单个缓存内容根据网络请求分布以及网络拓扑结构确定相应的缓存部署问题，该算法的时间复杂度为O(N³)，具有一定的可行性。

本发明采用以下技术方案：

一种基于节点竞争时延代价模型的缓存部署方法，在算法执行过程中确定N个节点是否是缓存节点，每次确定一个缓存服务器时确定N个节点作为缓存服务器时的性能，通过每次性能分析寻找到N个节点的最佳链路，确定基于节点竞争时延代价模型的缓存部署方法时间复杂度O(N³)。

进一步的，包括以下步骤：

S1、在网络中只有源服务器一个缓存服务器的情况下，初始化网络配置参量和初始化迭代过程变量；

S2、在已确定的缓存服务器节点结果下，分别分析每个节点作为候选缓存服务器时的传输时延代价；

S3、挑选传输时延代价最小的节点作为待确定缓存服务器节点；

S4、比较待确定缓存服务器节点部署带来的传输时延收益与缓存内容存储代价，确定是否在待确定缓存服务器节点上部署该缓存内容；

S5、若成功添加了新的缓存服务器节点，则更新网络配置参量和迭代过程变量，返回步骤S2，若未添加新的缓存服务器节点，表明已经部署的缓存服务器节点使得整体网络传输时延代价和缓存内容存储代价最小，结束。

进一步的，步骤S1中，所述初始化网络配置参量具体为：缓存服务器集合节点被服务信息节点被服务链路路径其中：为节点集合；o为缓存内容的源服务器；

所述初始化迭代过程变量具体为：节点获得缓存内容的传输时延代价c_ok＝p_kd_f(o,k)v，所有节点总的传输时延代价其中：为节点集合；o为缓存内容的源服务器；p_k为节点k对缓存内容的请求强度；v为缓存内容大小；d_f(o,k)为节点o服务节点k的基于节点竞争时延代价模型的传输时延代价。

进一步的，所述基于节点竞争时延代价模型的传输时延代价包括：缓存服务器节点j到接入节点k的内容传输数据流的链路路径f(j,k)；内容传输数据流的链路路径上所有节点集合节点r竞争范围内节点集合起源或者经过节点n的内容传输数量流内容传输数据流f的目标节点d(f)；节点单跳时延代价统计平均值估计值T；节点n相比其竞争范围内其他节点的竞争权值系数w_n和内容传输数据流的链路路径f(j,k)的基于节点竞争时延代价模型的传输时延代价d_f(j,k)。

进一步的，节点n相比其竞争范围内其他节点的竞争权值系数w_n为：

其中，s_f为内容传输数据流f在当前跳内的传输距离；p_d(f)为内容传输数据流f在当前跳的目标节点内容资源请求强度；α为路径损耗系数。

进一步的，基于节点竞争时延代价模型考虑了节点获得缓存内容形成的链路路径每跳的竞争关系对时延的影响，所述基于节点竞争时延代价模型的传输时延代价d_f(j,k)为：

进一步的，步骤S2具体包括：

S21、选取非缓存服务器节点中未进行候选缓存服务器分析的节点j，初始化其作为候选缓存服务器时的传输时延代价Cost_after＝0；

S22、按照节点获得缓存内容的传输时延代价从小到大的顺序依次选取接入节点k，获得其被服务的缓存服务器节点和对应的传输时延代价c_qk＝p_kd_f(q,k)v，采用迪杰斯特拉算法制定节点k从候选缓存服务器节点j获得缓存内容时的节点被服务链路路径对应的传输时延代价c_jk＝p_kd_f(j,k)v；

S23、确定节点k是否改变链路路径：若c_qk≥c_jk，则节点k改变链路路径，节点j作为候选缓存服务器的传输时延代价Cost_after＝Cost_after+c_jk，节点临时被服务集合若c_qk＜c_jk，则节点k维持原有链路连接，节点被服务链路路径节点j作为候选缓存服务器的传输时延代价Cost_after＝Cost_after+c_qk，节点临时被服务集合

S24、若节点j作为候选缓存服务器时各接入节点链路没有分析完，跳转至步骤S22；否则，结束。

进一步的，步骤S3具体包括以下步骤：

S31、初始化迭代循环中添加候选缓存服务器节点时的最小传输时延代价Cost_min＝+∞；

S32、选取非缓存服务器节点作为候选缓存服务器时未进行传输时延代价比较的节点j，若Cost_min＞Cost_after，则Cost_min＝Cost_after，待确定缓存服务器节点b＝j；否则，维持不变；

S33、若非缓存服务器节点作为候选缓存服务器时的传输时延代价没有比较完，跳转至步骤S32；否则，结束。

进一步的，步骤S4具体包括：

S41、提取原缓存服务器部署方法下传输时延代价Cost_before，提取待确定缓存服务器节点b，提取候选缓存服务节点部署缓存服务器之后的最小传输时延代价Cost_min；

S42、比较传输时延收益与缓存内容存储代价，若则在待确定缓存服务器节点上部署该缓存内容，也就是添加新的缓存服务器节点；否则舍弃将节点b作为真实的缓存服务节点；

其中：λ为缓存内容存储代价与传输时延代价的权值系数，一般需要根据具体场景情况量化处理，为定值；γ为单位缓存内容大小的缓存容量存储代价，一般需要根据具体场景情况量化处理，不同缓存服务器之间是相同的，为定值。

进一步的，步骤S5中，所述更新网络配置参量和迭代过程变量包括：缓存服务器集合节点被服务信息节点被服务链路路径和新的所有节点的传输时延代价之和Cost_before＝Cost_min。

与现有技术相比，本发明至少具有以下有益效果：

本发明基于节点竞争时延代价模型的缓存部署方法在算法执行过程中确定N个节点是否是缓存节点，每次确定一个缓存服务器时确定N个节点作为缓存服务器时的性能，通过每次性能分析寻找到N个节点的最佳链路，确定基于节点竞争时延代价模型的缓存部署方法时间复杂度O(N³)，该缓存部署方法在分发缓存内容前根据缓存内容请求分布进行了合理缓存服务器节点确定，避免了传统的广播式发送再在节点处根据请求强度确定是否缓存的盲目性，极大的减少了无用的链路传输，缓解网络压力，基于节点竞争时延代价模型的缓存部署方法总的传输时延代价值更小，选择的缓存服务器位置更合理，使得部署相同缓存服务器个数条件下，节点获得缓存内容的传输时延更短。

进一步的，该缓存部署方法是基于节点竞争时延代价模型构建的传输时延代价，考虑了缓存内容传输过程中由于竞争网络传输资源的影响，更具体的反应了网络中节点的传输状况，使得传输时延的表征更合理，由此制定的缓存部署方法能更有效的优化整个网络的传输时延性能；

进一步的，该基于节点竞争时延代价模型的缓存部署方法时间复杂度为O(N³)，相比于其他NP-hard问题超高时间复杂度求解思路，其可以有效应用于直播等实时业务缓存服务器部署。

综上所述，本发明对于无线Mesh网络等多跳自组织网络中针对节点获得缓存内容传输时延和缓存内容存储代价的权衡值进行了方法部署，减少了无用的链路传输，缓解网络压力，降低整个网络的信令负荷，提高系统无线资源利用率。

下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。

附图说明

图1是本发明基于节点竞争时延代价模型的缓存部署方法流程图；

图2是本发明待确定缓存服务器节点判断流程图；

图3是本发明算法仿真节点网格分布和缓存内容源服务器示意图；

图4是本发明不同权值系数条件下缓存服务器部署数量对比图；

图5是本发明不同权值系数条件下传输时延代价值对比图；

图6是本发明性能仿真节点分布与源服务器分布示意图；

图7是本发明不同时延代价模型传输时延对比图。

具体实施方式

本发明提供了一种基于节点竞争时延代价模型的缓存部署方法，提出的基于节点竞争时延代价模型的缓存部署方法在算法执行过程中需要对N个节点是否是缓存节点进行分析，每次确定一个缓存服务器时需要对N个节点作为缓存服务器时性能进行分析，每次性能分析需要寻找到N个节点的最佳链路，因此应用本论文提出的基于节点竞争时延代价模型的缓存部署方法的时间复杂度为O(N³)。

基于节点竞争时延代价模型的缓存部署方法目的是根据节点对缓存内容请求分布，确定网络的缓存服务器节点被服务信息节点被服务链路路径

请参阅图1，具体步骤如下：

S1、在网络中只有源服务器一个缓存服务器的情况下，初始化网络配置参量和初始化迭代过程变量；

初始化网络配置参量

此时网络中缓存服务器只有源服务器，因此缓存服务器集合节点被服务信息节点被服务链路路径

其中：为节点集合；o为缓存内容的源服务器。

初始化迭代过程变量

缓存服务器只有源服务器一个节点，所有其他节点都从源服务器获得内容资源，因此节点获得缓存内容的传输时延代价c_ok＝p_kd_f(o,k)v，所有节点总的传输时延代价

其中：为节点集合；o为缓存内容的源服务器；p_k为节点k对缓存内容的请求强度；v为缓存内容大小；d_f(o,k)为节点o服务节点k的基于节点竞争时延代价模型的传输时延代价。

所述基于节点竞争时延代价模型的传输时延代价包括：

缓存服务器节点j到接入节点k的内容传输数据流的链路路径f(j,k)；

内容传输数据流的链路路径上所有节点集合

节点r竞争范围内节点集合

起源或者经过节点n的内容传输数量流

内容传输数据流f的目标节点d(f)；

节点单跳时延代价统计平均值估计值T；

节点n相比其竞争范围内其他节点的竞争权值系数w_n；

内容传输数据流的链路路径f(j,k)的基于节点竞争时延代价模型的传输时延代价d_f(j,k)。

节点n相比其竞争范围内其他节点的竞争权值系数w_n为：

其中，s_f为内容传输数据流f在当前跳内的传输距离；p_d(f)为内容传输数据流f在当前跳的目标节点内容资源请求强度；α为路径损耗系数，一般取4。

基于节点竞争时延代价模型考虑了节点获得缓存内容形成的链路路径每跳的竞争关系对时延的影响，所述基于节点竞争时延代价模型的传输时延代价d_f(j,k)为：

其中，f(j,k)为缓存服务器节点j到接入节点k的内容传输数据流的链路路径；为内容传输数据流的链路路径上所有节点集合；为节点r竞争范围内节点集合；为起源或者经过节点n的内容传输数量流；d(f)为内容传输数据流f的目标节点；T为节点单跳时延代价统计平均值估计值；w_n为节点n相比其竞争范围内其他节点的竞争权值系数。

上述所提出的竞争时延代价模型是基于内容传输数据流经过的节点数以及对应竞争范围内的节点数和起源或者经过这些竞争范围内节点的数据流来构建的，该模型的关键点在于路径选择方法和竞争关系的关联性对时延的增益。在静态路由网络中，由于介质访问的竞争关系，内容传输数据流的时延代价与其经过节点所传输的内容数据流数量成正相关，也与其经过节点竞争范围内节点的内容传输数据流数量成正相关，这些内容传输数据流也就是上述提到的

而在动态路由网络中，动态路由选择方法所确定的路径将决定内容传输数据流中每个节点的竞争范围，同时每个节点的竞争关系对该节点传输时延都有一定的增益，这些增益值是独立的，换句话说，内容传输数据流的时延代价就是节点单跳时延代价统计平均值与总增益的乘积，而总增益也就是各单跳时延增益值统计之和。

由此不难看出，无论是在静态路由网络还是在动态路由网络中，传输时延代价都可以看成时延代价统计平均值与时延增益的乘积，也就是本发明构造的基于节点竞争时延代价模型。

S2、在已确定的缓存服务器节点结果下，分别分析每个节点作为候选缓存服务器时的传输时延代价；

S21、选取非缓存服务器节点中未进行候选缓存服务器分析的节点j，初始化其作为候选缓存服务器时的传输时延代价Cost_after＝0；

S22、按照节点获得缓存内容的传输时延代价从小到大的顺序依次选取接入节点k，获得其被服务的缓存服务器节点和对应的传输时延代价c_qk＝p_kd_f(q,k)v，采用迪杰斯特拉算法制定节点k从候选缓存服务器节点j获得缓存内容时的节点被服务链路路径对应的传输时延代价c_jk＝p_kd_f(j,k)v；

S23、确定节点k是否改变链路路径：若c_qk≥c_jk，则节点k改变链路路径，节点j作为候选缓存服务器的传输时延代价Cost_after＝Cost_after+c_jk，节点临时被服务集合若c_qk＜c_jk，则节点k维持原有链路连接，节点被服务链路路径节点j作为候选缓存服务器的传输时延代价Cost_after＝Cost_after+c_qk，节点临时被服务集合

S24、若节点j作为候选缓存服务器时各接入节点链路没有分析完，跳转至步骤S22；否则，结束。

S3、挑选传输时延代价最小的节点Cost_min＝+∞作为待确定缓存服务器节点，请参阅图2，具体包括以下步骤：

S31、初始化迭代循环中添加候选缓存服务器节点时的最小传输时延代价Cost_min＝+∞；

S32、选取非缓存服务器节点作为候选缓存服务器时未进行传输时延代价比较的节点j，若Cost_min＞Cost_after，则Cost_min＝Cost_after，待确定缓存服务器节点b＝j；否则，维持不变；

S33、若非缓存服务器节点作为候选缓存服务器时的传输时延代价没有比较完，跳转至步骤S32；否则，结束。

S4、比较待确定缓存服务器节点部署带来的传输时延收益与缓存内容存储代价，确定是否在待确定缓存服务器节点上部署该缓存内容；

S41、提取原缓存服务器部署方法下传输时延代价Cost_before，提取待确定缓存服务器节点b，提取候选缓存服务节点部署缓存服务器之后的最小传输时延代价Cost_min；

S42、比较传输时延收益与缓存内容存储代价，若则在待确定缓存服务器节点上部署该缓存内容，也就是添加新的缓存服务器节点；否则舍弃将节点b作为真实的缓存服务节点。

其中：λ为缓存内容存储代价与传输时延代价的权值系数，一般需要根据具体场景情况量化处理，为定值；γ为单位缓存内容大小的缓存容量存储代价，一般需要根据具体场景情况量化处理，不同缓存服务器之间是相同的，为定值。

S5、若成功添加了新的缓存服务器节点，则更新网络配置参量和迭代过程变量，返回步骤S2，若未添加新的缓存服务器节点，表明已经部署的缓存服务器节点使得整体网络传输时延代价和缓存内容存储代价最小，结束。

所述更新网络配置参量和迭代过程变量包括：缓存服务器集合节点被服务信息节点被服务链路路径和新的所有节点的传输时延代价之和Cost_before＝Cost_min。

为验证本发明提出的缓存部署方法能有效求解上述的NP-hard问题，参考图3所示的节点网格分布和缓存内容源服务器示意图，参考表1所示的算法仿真参数设置表，将本发明提出的基于节点竞争时延代价模型的缓存部署方法求得的次优解与遍历所得的理论最优解进行对比，参考图4，不同缓存内容存储代价与传输时延代价的权值系数λ条件下，两者求得缓存服务器部署数量是相同的；参考图5，不同缓存内容存储代价与传输时延代价的权值系数λ条件下，本发明与理论最优解的传输时延代价误差在10％以内，总体而言本发明提出的部署方法在求解上述NP-hard问题具有很高的准确性。

表1算法仿真参数设置表

为验证本发明提出的基于节点竞争时延代价模型更具体的反应了网络中节点的传输状况，使得缓存部署方法更合理，参考图6所示的节点网格分布和缓存内容源服务器示意图，参考表2所示的缓存部署方法仿真参数设置表，将本发明提出的基于节点竞争时延代价模型的缓存部署方法与基于链路跳跃次数模型、基于链路竞争时延代价模型进行对比，参考图7，基于节点竞争时延代价模型的缓存部署方法相比于另外两种模型在部署相同缓存服务器个数情况下，总的传输时延代价值更小，换句话说基于节点竞争时延代价模型选择的缓存服务器位置更合理，使得部署相同缓存服务器个数条件下，节点获得缓存内容的传输时延更短。

表3-4缓存部署方法仿真参数设置表

综上所述，本发明提出了一种基于节点竞争时延代价模型的缓存部署方法，首先，该缓存部署方法在分发缓存内容前已经根据缓存内容请求分布进行了合理缓存服务器节点确定，避免了传统的广播式发送再在节点处根据请求强度确定是否缓存的盲目性，极大的减少了无用的链路传输，缓解网络压力；其次，该缓存部署方法是基于节点竞争时延代价模型构建的传输时延代价，它考虑了缓存内容传输过程中由于竞争网络传输资源的影响，更具体的反应了网络中节点的传输状况，使得传输时延的表征更合理，由此制定的缓存部署方法能更有效的优化整个网络的传输时延性能；最后，该基于节点竞争时延代价模型的缓存部署方法时间复杂度为O(N³)，相比于其他NP-hard问题超高时间复杂度求解思路，其可以有效应用于直播等实时业务缓存服务器部署。

以上内容仅为说明本发明的技术思想，不能以此限定本发明的保护范围，凡是按照本发明提出的技术思想，在技术方案基础上所做的任何改动，均落入本发明权利要求书的保护范围之内。