基于簇内能耗最优的设备到设备缓存通信内容共享算法

佟 飘，龙 隆，韩 雪，邱大伟，胡 茜

(1.重庆邮电大学宽带无线移动互联网络实验室，重庆400065;2.移动计算与新型终端北京市重点实验室(中国科学院计算技术研究所)，北京100190))

(* 通信作者电子邮箱tongpiao@ict.ac.cn)

0 引言

近年来，由于智能设备终端数量快速增长，产生了多种新的无线服务，导致无线网络的移动数据流量急剧增长，给蜂窝网通信带来了巨大的压力。根据思科的预测［1］，在未来十年，全球移动数据流量预计有500倍的增长，其中移动视频流量占移动数据总流量的50%。

目前，以蜂窝网为基础的设备到设备(Device to Device，D2D)缓存通信作为一种将流量从蜂窝网基站卸载的方案已经引起了学术界和工业界极大的兴趣［2］。事实上，随着智能终端设备的本地存储容量增加且硬件存储成本的降低，可以充分利用用户终端设备进行文件存储。在D2D网络中各个用户节点设备处缓存流行文件并进行终端设备之间文件共享能够有效地卸载蜂窝网基站流量，缓解蜂窝网通信容量瓶颈问题［3］。但终端设备电池容量有限，不能满足用户持久性的D2D内容共享，如何降低数据传输能耗、提高文件卸载率是一个亟待解决的问题。

文献［3－6］提出以用户为中心的主动缓存策略，通过优化缓存分布来提升D2D缓存通信的卸载率，但其方案都没有充分考虑到文件的获取来源、传输过程中节点的能量消耗问题以及能耗对卸载率的影响。文献［7］中报告表明，在实际生活场景中，用户的行为在时间段内具备规律性，活动区域相对固定且与邻近的用户交互较多。从目前的研究来看，基于分簇的通信方案能够有效地提高卸载率。文献［8］采用分簇的方案，通过优化传输距离提高蜂窝网流量卸载，然而该算法并未对节点能耗的问题进行研究，忽略了设备的续航时间对文件卸载的影响。文献［9］基于信道质量和传输能耗，提出了一种成簇方案，该算法可有效提高系统吞吐量增益，然而以最大功率进行文件传输的策略造成了传输过程中的设备能耗过大，并没有对能耗对卸载率的影响进行研究。

在本文的研究中，考虑D2D用户的场景，提出基于簇内节点能耗最优的缓存通信内容共享算法(Caching communication content Sharing Algorithm for minimizing inner-Cluster node energy consumption，CCSA)。其基本思路是，在全网用户节点生成D2D簇的基础上，根据簇首(Cluster Head，CH)影响因子对每个D2D簇进行CH选取，在此基础上将D2D网络的卸载率归纳为一个组合优化问题［10］。通过选取最优的CH集，促使CH能够满足其所在簇的绝大多数成员(Cluster Member)的内容需求;同时分析传输距离与文件卸载能耗的制约关系，优化传输距离;在能耗最优的条件下，实现D2D缓存通信卸载率的最大增益，并最大限度地延长系统的生存周期。

1 系统模型

考虑如图1所示的D2D用户场景中，将全网用户节点建模为泊松簇过程(Poisson Cluster Process，PCP)［9］。同簇的设备除了可以进行正常蜂窝网上下通信外，还能在D2D链路上进行设备间直接通信;D2D通信在蜂窝基站控制下进行，为了降低干扰，D2D和蜂窝通信使用正交时频资源。由于簇内各设备间距较短，如同一单位、企业、校园，D2D链路的传输速率较高，一个普通视频文件的传输可达秒级完成(如一部500 MB电影)。网络中的每一个节点都具备有限的本地数据缓存的能力，不能够缓存文件库中所有文件;可以作为内容提供者为其他用户提供服务;节点的自身的能量有限，一旦低于一定能量值就不能进行文件共享。DR表示内容请求节点，DT表示内容提供节点;DT与DR通过建立D2D链路进行文件共享。如果DT节点分布过疏，会导致通信半径rc过大，传输能耗过多;且当DT能量低于一定阈值，则不足以支撑文件传送。以上这些因素都会影响系统生存周期，导致D2D缓存通信的卸载量下降。

现实生活场景中，用户设备的缓存容量、能量有限，在不同时间段用户位置、请求的文件具有动态变化性，因此本文引入了D2D簇的机制和“轮”的概念。假设在短时间范围内用户的位置基本不变，网络中各D2D簇在每轮时间都会进行CH更新，在持续的一段时间段内(如5小时)用户的位置可能会发生移动、兴趣偏好及请求的文件的流行度可能会发生变化，因此一轮持续的时间即D2D簇的CH更迭频度与用户的移动性、设备现存能量、文件的流行度及长度有关，T={t|d，E，β，F}。

图1 D2D缓存通信网络Fig.1 D2D cache communication network

基站负责对小区中所有节点进行分簇及簇节点的管理与维护，当节点位置发生变化时需要告知基站;D2D节点需要周期性地向基站上传自身数据;簇成员需要维护与每轮所在簇的CH节点的通信;CH节点负责维护与本簇所有节点的通信。CH节点的位置疏密度、自身能量很大程度上决定了D2D网络的卸载率及生存周期，因此，CH节点的选取非常重要。每轮时间开始即簇形成的初始阶段，基站根据CH选取算法决定簇中节点是否作为本簇“CH”，并在各个簇内进行泛洪广播。在簇的稳定阶段，当成员节点与CH之间无文件请求服务时(处于空闲状态)，将成员节点与CH转换为休眠模式以降低自身能耗;当成员节点发起文件请求服务、CH收到源于簇内成员节点的文件请求时，从休眠状态转为工作状态并重新连接通信链路，本文假设节点的状态转换不消耗能量。CH负责为簇内多数成员节点提供文件服务。在D2D簇通信网络中，通过以“轮”为周期动态CH的选取，避免了CH节点能耗过大，防止低能量节点成为CH，最大限度地均衡网络能耗负载。CH选取算法不仅降低了D2D缓存通信中的能量消耗，且提高了D2D通信网络的可靠性。

本文考虑蜂窝网下单个小区的场景，用户节点的地理位置服从密度为λ的泊松簇过程［9］，如图2所示。假设网络中包含簇的数量为K，C={C1，C2，…，CK};每个簇的节点数为N，簇中节点以中心节点为中心，独立同分布，且服从方差为的正态分布，Node={node1，node2，…，nodeN}。小区中每个簇具有相同属性，且基站明确每个簇所有用户的地理位置坐标及缓存的文件的种类与数目，并协调D2D通信。

假设小区中的所有用户可能请求的文件都包含在一个静态的内容目录中，数目为Nf。文件在文件库中的排名索引值源于文件在网络中的流行度，每个文件的大小为F MB。排名为f(f=1，2，…，Nf)的文件被用户请求的概率 p(f)服从Zipf［11］分布:

当DR与DT在同一个簇，距离d小于D2D通信距离阈值rc，且两者的现存能量大于能量阈值，则能够成功建立D2D数据传输链路。如果DR在簇内不能通过D2D链路获得请求内容，则向基站请求。

图2 D2D成簇模型网络拓扑Fig.2 D2D clustering model network topology

2 自适应加权CH选取算法

2.1 CH选取及更新机制的提出

在D2D用户成簇的场景中，采用一种组合加权算法以及贪婪算法局部最优原则对每个簇进行自适应CH选取，以达到优化D2D缓存网络内容共享能耗的目的。自适应加权的原则是给每一个节点分配一个加权和(wCHi(k))，它指示节点适合充当本簇CH的程度。贪婪算法解释在某种意义上的局部最优解［12］。每轮时间初始，首先借助节点之间的距离、能量制约因素，确定不同制约因子对优化目标即节点的CH权值wCH，k={k∈C|k≤K}的贡献。其次在满足节点能量阈值Eh条件下，采用局部最优贪婪机制选择最大的链路和能量组合，即 max(珔d，Ecurrrent/E0)。CH 选择完成之后，为了满足内容共享连续性约束，D2D网络生存周期以“轮”为单位，动态地更新所有簇的可接入CH集合。

在一轮时间内，如果系统中无满足能量阈值的节点，即CH集合为空，算法结束;否则进行下一轮时间的CH选择。上述最差情况出现在所有节点的能量都小于阈值，则不能进行D2D缓存通信文件卸载。

在D2D簇初始阶段，将网络中每个簇的位置中心节点作为簇的CH，即第一轮D2D用户节点簇的CH，为成员节点提供文件服务。对于簇的稳定阶段，根据本文提出的基于节点距离和现存能量的CH选取策略，用于第一轮之后的时间段内的动态CH选择，目的是降低文件传送的能耗成本，延长每个簇的生存周期，从而提高系统D2D缓存通信的卸载率。在第一轮内容共享结束后，所有簇的CH由CH选取算法确定。

一旦DT与DR建立D2D链路，DR处的信号与干扰加噪声比(Signal to Interference plus Noise Ratio，SINR)［13］可表示为:

其中:Pt表示DT的传送功率;σ02表示高斯白噪声的方差;h和r分别表示信道系数以及DT和DR之间的距离，h服从单位方差内的零均值高斯分布;α表示路径损耗指数。

根据文献［12］，1+γ(r)约服从γ分布，对于小尺度信道衰落的平均数据传输速率［13］可以推导为:

其中W表示带宽。

通过使用一阶近似［14］，文件大小为F的平均传输时间可以表示为F/珔R。

2.2 预测节点的现存能量

假设一轮时间内每个簇存在节点个数Nx向其所在簇的CH请求文件，则通过距离为r的D2D链路的内容共享能耗为:

其中CH的能耗［10］为:

簇内成员节点的能耗为:

式中:Pr(r)和Pt(r)分别表示DT的传送功率和DR的接收功率;Pc表示节点自身的功耗;η表示功放效率。

假设簇中的每个节点在系统初始阶段所具备的能量都是E0，且节点从休眠转换为工作状态不消耗能量，经过一轮时间t后，各个节点经过传送或接收文件、自身能耗，现存能量为Ecurrent。

每个节点当前时间(第ring_c轮)现存能量模型为:

其中:ring_c≥1;k表示D2D网络中簇的编号。

2.3 节点之间的距离

假设D2D节点R与S之间的距离为d:

其中，R与S在小区中的坐标为NodeR=(xR，yR)，NodeS=(xS，yS)。

根据欧氏定理，有:

那么，簇内节点i(i=1，2，…，N)到其他节点的平均距离为:

2.4 自适应加权CH选取

针对D2D网络中的每个簇，考虑簇中节点位置的疏密度以及其现存能量，确定是否作为本簇的CH。簇中节点位置越疏，即DT与DR之间的平均距离越大，节点的传输能耗越多，自身能量越低，进而导致文件卸载量降低;反之，节点现存能量越高，系统生存周期越长，进行文件卸载的概率则越大。可能出现一种极端情形，位置越疏的节点，其现存能量越高。针对以上情景，在CH选择过程中，通过引入δ、θ作为节点的现存能量比率、地理位置疏密度的权重因子，可动态调整，某个参数对目标优化问题越重要，对应权重因子越大，并满足δ+θ=1的制约条件，具体取值根据应用环境决定。

第ring轮(ring ＞ 1)，计算簇k(k=1，2，…，K)包含的节点i的CH权值wCHi(k)，在约束条件下，从备选CH节点中选择CH权值最优的节点:

其中δ+θ=1，0≤δ≤1，0≤θ≤1。

根据式(12)，设定两个对应的阈值 dh、Eh，若 Ecurrent，i＜Eh，则能量权重因子δ取值为0;若di＞dh，则距离权重因子θ取值为0。最优的CH权重值为:

通过式(12)自适应得到网络中每个簇各个节点的当选权重，根据贪婪局部最优原则选择权值最大的节点作为本簇当前轮的CH，并通过基站在簇中进行广播。

3 基于D2D簇的内容共享算法

为了减轻蜂窝网基站负载，本文力求找出每个簇最优的CH，并通过优化通信距离最大化卸载率。在每一轮时间开始，选取当前簇的CH，并为其所在簇的成员节点提供当前轮内容服务。

蜂窝网包含簇的个数为K，用户节点在一轮持续时间段(0，t)时间内，可请求一个文件至多一次，多个用户节点可同时访问同一个文件，则同时访问文件排名为f、用户数为n的概率为:

请求文件f的节点在它所在的簇k的通信范围rc内获得缓存文件的概率［7］为:

针对文件库中的所有文件，根据式(14)、(15)可获得当前簇k的卸载率:

其中0≤n≤N。

由式(16)可推导出系统中K个簇的卸载率:

则由式(18)平均每个簇的卸载率:

于是可将优化卸载率问题建模［15］如下:

函数是关于WCH(k)、n、Nf的凸函数，n和Nf是目标函数的线性约束，根据KKT条件［14］，可求得CH权重因子的最优解WCH*(k)。具体算法流程如下:

1)根据欧氏定理，计算簇中节点i与其余节点之间的平均距离 珔di，并获取节点的当前剩余能量 Ecurrent，i(i=1，2，…，N)。

2)由式(12)，在每轮生存周期的开始阶段根据距离制约因子珔di和节点的现存能量Ecurrent，i求解当前轮所有簇包含的节点i的CH权重值wCHi(k)，为网络中CH集的选取作准备工作。

3)基于以上步骤，判断D2D簇的各节点的现存能量是否大于能量阈值，若大于则运行步骤4);否则，网络中所有簇的CH集合为空，算法结束。

4)在节点的现存能量满足能量阈值Eh的条件下求解式(13)，即得到簇k最优的CH权重值WCH*(k)，从而获取当前轮网络中所有簇的最优CH节点的集合，即:

4 实验与结果分析

实验的硬件环境为联想 G470AH-ITH(i)，Intel酷睿i3-2350M处理器，主频为2.3 GHz。利用Matlab 2014a仿真平台对成簇随机选CH(Random)算法算法及文献［15］中非成簇能耗优化(Energy Cost optimal，EC)算法进行仿真性能比较。Random算法在D2D用户成簇场景中采取随机选取CH策略，每轮时间初始阶段基站在每个簇当前所有D2D用户节点中随机选取节点作为其所在簇的CH，为其成员节点提供内容服务。

根据系统模型，对于单小区蜂窝网络，其范围设为500 m×500 m，用户节点在小区中随机分布，并进行泊松成簇，密度 λ =0.03，方差 σnode=10。

文件库中目录长度Nf=1 000，其中每个文件大小F=30 MB，Zipf分布的参数β=1，信道的传输带宽W=20 MHz，σ02=－95 dBm，路径损耗α=4。节点的最大传输功率Pmax=23 dBm，功放η=0.2，节点设备自身电量消耗Pc=115.9 mW。CH选取算法中现存能量比率权重因子和位置疏密度权重因子 δ、θ分别取 0.6、0.4。

为了反映DT传送一个文件所消耗的电量，本文将能耗比率［15］定义为:

其中:Q表示电池容量，单位是mAh;V0表示运行电压。

用户设备的运行电压 V0=4 V，电池容量 Q =1800 mAh(目前手机普遍的电池容量，如iPhone6s)。

为了验证本文提出的CCSA的性能优势，将该算法与Random算法以及EC算法进行比较。在仿真实验对比中，选取D2D缓存通信的通信距离、生存周期(以轮为单位)、现存能量比率、卸载率四个性能指标。其中:现存能量比率定义为当前时间网络中所有节点的现存能量与初始能量的比值;卸载率定义为针对文件库中所有文件平均每个簇的卸载率。

图3(a)显示了在系统运行一定时间内，CCSA、Random、EC算法在传输距离rc变化时系统卸载率的变化趋势。伴随rc在一定范围内的增大，DT能够满足更多DR节点数对文件的请求，因此三种算法的卸载率均呈现递增趋势，同时得益于CCSA算法考虑每个簇的CH节点相对于成员节点之间的位置疏密、节点现存能量的动态变化，可以观察到其卸载率性能伴随着rc的增大而逐渐凸显，相比Random及EC算法可以更加有效地提高D2D用户文件的卸载率。

网络的现存能量比率反映了节点在满足文件需求的同时自身能量的消耗情况。如图3(b)中所示，rc较小时，即CH的通信范围较短，簇中多数成员节点通过访问基站获取文件，其能耗远大于D2D缓存通信的能耗，所以系统的现存能量比率较低;随着rc的增大，簇中成员节点通过D2D缓存通信的方式获取文件所占的比重，逐渐大于通过访问基站获取文件所占的比重，所以三种算法的系统现存能量比率随着rc的增大而增大。由于EC算法在系统中随机选取DT进行文件卸载，因此在文件卸载时受限于传输距离和节点能量，网络的现存能量比率低于CCSA和Random算法。由图3(b)可见，在rc=80 m时，CCSA和Random算法的现存能耗比率相差最大，约达到40个百分点。

图3 D2D通信距离与不同性能指标之间的仿真关系Fig.3 Simulation relationship between D2D communication distance and different performance indicators

图4 (a)为了系统生存周期与D2D缓存通信卸载率的变化情况。显然，系统生存周期越长，D2D缓存通信的卸载率越高。图中CCSA、Random、EC三种算法的卸载率均随着生存周期的增加而增大，当系统运行到一定周期，CCSA算法的卸载率趋于峰值并持平。由图4(a)可知，当ring=2000时，与Random和EC算法相比，CCSA卸载性能最好，卸载率分别提升约4.6个百分点、5.5个百分点。

图4(b)为CCSA、Random、EC三种算法的系统生存周期与现存能量的关系。随着生存周期的延长，三种算法的系统现存能量比率呈现下降趋势，当生存周期达到一定长度，三种算法的现存能量比率差异逐渐消失。相比Random、EC算法，采用CCSA的系统生存周期较长，CH权值最优促使簇的能耗均衡负载，当ring=500时，现存能量比率高出约56个百分点，能耗较低，且CCSA的系统生存周期分别延长了约60个百分点、72个百分点。

综上所述，在D2D缓存通信网络中通过对簇内节点考虑位置、现存能量因素自适应选取 CH，相比随机选取 CH(Random)算法、非成簇能耗优化(EC)算法，在一定通信范围内，能够实现卸载率的提升，并降低了D2D簇节点的能耗，延长了系统生存周期。

图4 系统的生存周期与不同性能指标之间的仿真关系Fig.4 Simulation relationship between survival cycle of system and different performance indicators

5 结语

针对D2D缓存网络中用户设备电量有限的实际情况，本文提出了以最大化D2D网络卸载率为目标进行节点能耗优化的内容共享算法。在D2D网络节点成簇的基础上，设计簇内基于贪婪机制的自适应CH的动态选取方案，并对D2D缓存通信的卸载率和节点能耗进行建模与分析，在兼顾D2D缓存通信系统卸载率的同时，有效地控制了网络中各簇D2D节点的文件卸载能耗，使内容共享能耗最低。仿真结果表明，相对于Random算法及EC算法，本文提出的CCSA算法通过簇内最优CH的选取，在系统卸载率和生存周期具有明显的优势。但该研究并未涉及选取CH的更迭替换时间，即“轮”的持续时间，因此下一步研究计划以一种自学习机制从用户的移动性、兴趣偏好、文件流行度及长度等方面对系统中簇内CH的更迭频度进行优化。