一种基于社交的移动边缘计算方法

摘要

移动边缘计算（MEC）为将大量数据从云迁移至信息实际访问的地理位置提供了机遇。通过结合移动群智感知方法，并使用相对于基站数量较少的设备，该方案能够达到与传统移动边缘计算中间件层相当的性能，同时保持相同的空间覆盖范围。

在本研究中，我们设想了一种由移动边缘和固定边缘节点组成的移动边缘计算架构，其目标是通过利用用户的移动性和社交性来优化用户间的内容共享。我们首先提出一种算法，用于识别一组合适的移动边缘节点，并展示了这种选择如何提升内容共享场景的性能。我们的实验基于ParticipAct数据集，该数据集记录了约170名用户持续10个月的移动轨迹。实验结果表明，移动边缘节点所能服务的请求数量与固定边缘节点相近，因此移动边缘可被视为固定边缘的一种可行且低成本的替代方案。

关键词 ——移动群智感知，以人为本的边缘计算，社会移动性

一、引言

互联互通是新千年的关键词。城市正逐步但持续地基于新的连接机遇改变其地缘政治格局。除此之外，我们正处于一个几乎所有有用的物体都可无差别地接入互联网的时代。在此背景下，智能手机和可穿戴设备总体上发挥着重要作用。这些工具已摆脱最初仅作为个体间通信手段的功能局限，配备了短距离通信接口，能够在没有物理网络基础设施的情况下相互交换信息。随着技术进步，新一代传感器被嵌入到这些设备中。磁力计、陀螺仪、加速度计以及嵌入所有个人设备中的多种其他传感器，能够在其所处位置采集信息，从而产生无限量的数据采集。

我们所处环境中大量设备的普及，使得能够以无缝方式利用漫游人员，通过移动群智感知（MCS）平台增强信息的收集与交换。与此同时，多接入边缘计算（MEC）一种近期发展的技术，通过演进双层云设备集成模型，减轻了设备承担的计算负载。本研究旨在建立一种新的信息交换模型，该模型以移动群智感知（MCS）技术和多接入边缘计算架构的协同使用为特征，以促进固定或移动设备之间和通过设备的数据传播。

在我们之前的工作中，我们提出了一种人类驱动的边缘计算（HEC）模型[1]，以简化MEC平台的部署，提高其可扩展性，并支持更强大的移动群智感知（MCS）应用，从而激活原本静态的信息交换平台。为了增强云与个人设备之间的信息交换，HEC在基本MEC模型的固定边缘计算节点（FMEC）基础上，引入了在网络节点中以非任意方式选定的临时移动边缘（M2EC）。可以将M2EC实体识别为一种中间件代理，该代理在人们倾向于停留一段时间的地点被动态激活。通过这种方式，标准的三层分层MEC架构在其中间件部分得到了增强，新增加的边缘节点能够像固定节点一样发挥作用，克服了与社交和空间覆盖相关的问题。在此背景下，从网络节点中选择M2EC至关重要，应优先选择那些与其他节点具有更高数据交换机会的节点。

本文提出了一种用于选择M2EC的新算法。该算法利用MEC用户的关系和社区信息，选择那些与尽可能多的其他用户具有更好连接关系的用户（即在MCS用户社区中处于中心位置的用户）。这是因为所选用户的设备也有更高的概率与其他设备保持连接，从而与MCS中更大比例的设备交换数据，促进数据流向M2EC，进而传输至云。我们通过在来自ParticipAct移动群智感知平台的数据集上测试该“社交感知”的M2EC选择策略进行评估，仅使用其中的移动轨迹数据，结果表明M2EC移动边缘在收集数据方面的性能可达到与固定边缘计算节点（FMECs）相同的水平。考虑到M2EC移动边缘是从参与者的设备中选出的，无需专门维护，并且可以频繁更换以避免单个设备过载，因此在MCS平台设计中，采用M2EC移动边缘是一种可行且低成本的固定边缘替代方案。

II. 相关工作

在不声称完整性的前提下，以下简要介绍一些相关工作，以构建必要的背景知识，并展望当前移动群智感知（MCS）、多接入边缘计算（MEC）的发展现状，及其向能够利用人类移动性和社会性特征的更动态HEC模型演进的趋势。

从移动群智感知（MCS）出发，近年来，移动和可穿戴设备的广泛普及为MCS作为数据收集与共享的新范式奠定了基础。借助人类移动性以及配备传感器和短距离通信接口设备的普遍性，MCS为参与式与机会感知开辟了新的前景[2]。目前已有一些优秀且详尽的综述文献，涵盖了MCS领域中较为成熟的研究方向，例如移动群智感知与计算、用户招募，以及通过预测性移动计算与网络研究用户重复性行为模式[3, 4, 5]。近期的研究正致力于解决该领域中一些尚未攻克的问题。在能耗方面，参与真实环境MCS活动的用户经常抱怨其设备电池的能耗问题[6]，而文献[7]提出了一种可行的上下文感知解决方案。另一个热点问题是数据质量。事实上，由于数据交换和数据收集过程中的保密性较低，大量MCS志愿者的参与成为一个备受争议的问题，近期已出现多种不同的应对方案[8,9]。环境覆盖是任何MCS活动都具备的一个及时且重要的特征，文献[10]提出了克服这一问题的可能解决方案。

转向与MEC相关的研究工作，MEC在云和移动设备之间引入了一个中间件层作为中介。MEC旨在减轻委托给设备的计算负载，并通过在基站部署虚拟化云资源，提升网络边缘的响应速度，从而将云的计算能力向设备侧靠近[11]。MEC中间层的主要优势在于降低计算成本，从通信角度来看，则减少了网络负载。MEC的一个主要缺点是网络边的安装与维护操作成本不可忽略[12]。为解决这一问题，我们最近探索了利用MCS与移动社交网络交叉领域的新研究趋势，以促进M2EC的识别和临时组建（作为传统FMEC的低成本替代方案）[1]。

沿着相同的方向进一步推进，本节最后介绍了一些关于新HEC架构模型提出的开创性工作。在这一新兴领域中，多接入边缘计算/雾计算文献已经产生了一些重要的建模工作以及一些开创性的设计与实现成果。聚焦于与我们研究相近的工作，如[13]所述，一些初步探索性研究已考虑了边缘与核心之间的协作问题，但仅有极少数工作集中探讨了设备与边缘之间协作的机会。以移动群智感知（MCS）作为应用场景，[14]和[15]提出利用中间MEC节点来增强MCS过程，即FMEC用于增强从移动节点到基础设施的数据上传[14]，并为靠近终端移动设备的位置提供更多计算/存储能力[15]。最近一项非常新颖且有趣的研究，在涉及边缘共置实体之间实现更多协作方面，与我们的HEC概念最为接近，即[16]：该研究不仅提出了设备、多接入边缘计算和云层级之间的传统“垂直”协作，还通过自组织通信实现了同一层级实体间的“水平”协作；然而，它忽略了人类因素以及社会性/移动性影响，也就是说，不像我们提出的创新性HEC方案那样，具备动态识别并临时组建M2EC的能力。

III. M2EC选择算法

在我们的架构中，M2EC是个人设备，在有限的时间内充当移动边缘计算架构的边缘，通过向其他用户设备提供与固定边缘计算节点相同（或其子集）的服务，扩展FMEC已有的覆盖范围。由于M2EC是用户的个人设备，因此具有移动性，并根据其移动性覆盖时空域的某一区域。因此，它可以向与其相遇、即进入其低距离通信接口范围内的设备提供服务。

然而，由于这些设备是用户随身携带的移动设备，它们与其他设备的通信机会在很大程度上取决于用户的移动性以及他们在移动群智感知（MCS）中与其他用户的关系。因此，M2EC的选择应优先考虑属于用户的设备。

算法1 - M2EC检测

设S为给定CS的强社区集合{S1,…, Sn}

对于所有Si ∈ S执行
设Ei为Si的自我网络
对于所有uj ∈ Si执行
Bj = 介数中心性(ui, Ei)
Mi = {argmax(Bj)} // M是Si的M2EC候选者

对{Ei}进行排序 // 不失一般性，我们假设
|Ei| ≥ |Ej| 当且仅当 i < j

选择前k个节点M1,…,Mk作为M2EC，满足：
- |E1 ∪ … ∪ Ek| ≥ α
- |E1 ∪ … ∪ Ek+1| – |E1 ∪ … ∪ Ek| ≤ β

那些更具“社交性”的节点，即与其他更多用户频繁接触的节点。换句话说，我们的目标是选择M2EC以增加多接入边缘计算基础设施的社交覆盖范围，从而克服当前移动边缘计算架构由于缺乏基于人类行为的移动结构所带来的局限性。为此，我们定义了一种利用个体之间社会关系的M2EC选择算法。事实上，人们基于其习惯和职责在不同地点之间移动，而同样确凿的事实是，人们会基于性别、种族等聚合因素建立社会关系[17]。我们所关注的社区正是由这些联系紧密连接而成的群体（图1展示了我们使用数据集检测到的社区的图形表示——见第二节）。假设每个社区内部仅有极少数节点比其他节点更加凝聚，形成一个强社区。这些强社区是选择M2EC的起点。一旦识别出一个由节点组成的强社区，我们便针对每个节点找出其自我中心网络，即与其有联系的所有节点的集合（强社区中各节点的自我中心网络的并集构成一个扩展社区）。然后，我们在强社区的节点中选择与扩展社区具有最多接触的节点作为扩展社区的代表节点。具体而言，我们使用介数中心性[18]来确定该扩展社区的代表节点：该节点即为成为该社区M2EC的候选者。这些M2EC选择步骤总结于算法1中。

原则上，每个强社区的候选者都可能被选为M2EC，但出于效率考虑，我们仅从这些候选者中选择那些有助于最大化系统社交覆盖范围的成员。为此，我们根据自我网络的规模对其进行排序，并将前k个自我网络中的候选者指定为M2EC，使得所选自我网络的并集超过给定阈值α，且第k+1个自我网络对所选自我网络并集的贡献低于阈值β。参数α和β表示系统总人口的一个比例，其设置目的是避免将无法显著增加M2EC覆盖范围的节点纳入M2EC。

算法M2EC检测假设社区和强社区是已知的。为此，它基于邻近性维护一个社会关系图用户之间的因素。具体而言，通过全球定位系统或设备短距离通信接口（如Wi-Fi直连模式或蓝牙）测量距离，来计算节点间的邻近程度。为了发现社区和强社区，可以使用任何社区检测算法。在本例中，我们使用了TILES[19]，它是一种用于动态社交网络中社区发现的算法。简而言之，TILES基于模式识别的过程，提取重叠社区并跟踪其时间演化。该算法采用一种多米诺效应策略，在每次新交互发生时重新计算节点的社区成员资格，并且不对网络划分和社区提取设置固定时间阈值。一个重要特点是，TILES在计算中不排除重叠社区，这意味着每个强社区节点可以属于多个不同的强社区。后者代表了个人所处的社会世界的各个范畴。

IV. 实验设置

接下来，我们将介绍实验所使用的ParticipAct数据集，阐述实验设置，并描述在不同场景下获得的结果。

A. ParticipAct数据集

ParticipAct[20, 21]项目提供了一个来自意大利艾米利亚-罗马涅大区的移动性数据集。该数据集覆盖了大约15个月，从2013年12月到2015年2月。在本研究中，我们将观察时间限制在2014年10月之前（即10个月的观察期）。ParticipAct用户使用配备ParticipAct移动应用的基于安卓的智能手机。该应用能够通过利用谷歌定位API定期计算用户位置。位置信息是通过融合全球定位系统、Wi-Fi热点坐标或手机基站的数据获得的。每个用户的设备以2.5分钟的采样周期上报其位置。这些用户主要是意大利博洛尼亚大学的学生，因此他们的移动模式严格遵循大学生的移动规律。其中一些人每天从农村地区通勤到城市地区，而另一些用户大部分时间在市中心活动。

我们从ParticipAct数据集中提取了用户的共现轨迹，该轨迹并不追踪设备的全局位置或相对位置，而是以给定的时间分辨率追踪设备对之间接触的开始和结束时间。因此，共现轨迹可以被视为一个随时间演化的图，其中节点是用户设备，边则表示在特定时间点设备对之间的连接。我们认为，如果一对设备在10米范围内持续至少2.5分钟的时间间隔，则该设备对处于接触状态。

B. 仿真实验

为了测试第三节中提出的选择算法的效率，我们利用了ParticipAct数据集中的共现轨迹，该数据集涉及约170名学生。我们将实验位置限定在博洛尼亚市，持续30天。具体而言，我们的分析覆盖2014年5月31日至6月30日。我们选择这一时间段来测量我们的性能。

属性	值
α‐值	55%
β‐值	2%
数据集	ParticipAct
算法	M2EC检测
观察时间	30天
位置	博洛尼亚（意大利）纬度 45° 27’ 55.6’’ 经度 9° 11’ 11.4’’
参与者人数	170
观察期	30天
请求生成	5x10³

在学生与其他学生进行有意义社交互动的期间，研究该架构。我们实验的目标有两个：一方面，我们希望使用第三节中提出的算法来选择FMEC和M2EC，并评估每种边缘满足请求的平均延迟；另一方面，我们希望评估M2EC在满足来自相应自我网络节点所发起请求方面的性能。表1列出了我们实验的配置。

我们比较了在三种不同场景下获得的结果。具体而言，我们考虑了仅FMEC运行的场景、仅M2EC运行的场景，以及将FMEC与M2EC结合使用的场景。针对每种场景，我们考虑两个关键指标：延迟和满足的请求数量。关于延迟，它衡量了我们的架构在向场景中漫游的节点分发相关内容时的效率。我们通过以下延迟来评估M2EC的效率：

• 固定边缘延迟：仅由固定边缘节点满足的请求的平均延迟。
• M2EC延迟：仅由移动边缘满足的请求的平均延迟。
• 综合延迟：由固定和移动边缘共同满足的请求的平均延迟。

关于满足的请求数量，我们对选择算法的有效性进行了评估。首先，我们将仅由FMEC满足的请求百分比与仅由M2EC满足的请求百分比进行比较。其次，我们评估M2EC对我们模型的贡献。为此，我们测量由属于同一社区的节点或由其他M2EC满足的请求。具体而言，针对每个M2EC，我们测量以下百分比：

• M2EC在自我网络中的占比，即由特定M2EC在其自我网络中满足的请求数量与该自我网络中生成的总请求数量之比。
• M2EC在自我网络之外，即由其他M2EC满足的请求数量与生成的总请求数量之比在其自我网络中以及在该自我网络中生成的请求数量。
• 未满足的自我网络请求，即在M2EC自我网络中生成的未回答请求的数量与在该自我网络中生成的总请求数量之比。

我们的实验工作如下：首先选择一些兴趣点来部署FMEC。我们认为FMEC的数量通常是有限的（这是由于部署要求、安装问题和维护成本所致）。在本例中，我们考虑在6个位置部署我们的FMEC[1]。关于M2EC的部署，我们运行第三节中定义的选择算法。如前所述，我们的算法依赖于两个关键信息：强社区以及ParticipAct中节点的中心性度量。

C. 仿真结果

我们现在展示我们方案的评估结果。为此，我们考虑ParticipAct中不作为M2EC运行的节点，并让它们周期性地生成请求。每个请求代表需要访问一个边缘（固定或移动）以上传在移动群智感知（MCS）活动中由设备产生的数据。同样，每个请求代表一种特定资源节点所需的内容，例如多媒体内容、文本数据或需要收集的感知信息。此外，每个生成的请求都表示为一个对：<节点ID，时间戳>。我们限制请求的生成时间不超过总仿真时间的四分之三，以便为所有请求在仿真结束前被满足留出足够的时间。这是因为观察期为一个月，而满足请求的最长期限为一个月的四分之一。因此，每个生成的请求都有相等的机会被满足。对于每个请求，我们测量其相应的延迟。该指标计算为t’ – 时间，其中t’ ≥ 时间是指生成请求的节点首次遇到以下任一情况的时间：FMEC（固定边缘延迟）、M2EC（M2EC延迟）或上述两者中的任意一个（综合延迟）。而时间变量是当前时间戳。关于延迟的结果如图2和图3所示。从这两个图中可以明显看出，我们得到了几乎相似的趋势，长尾向右延伸，大多数已满足的请求集中在最初的时间区间内（0 – 0.5）。一个初步的总体结论如下：尽管在仿真环境中运行的FMEC数量是M2EC的两倍，但后者在已满足请求方面的性能大致与前者相当。

图3显示了FMEC与M2EC组合所获得的平均延迟。可以看出，延迟的降低微乎其微。这种现象是预期之中的，因为FMEC的数量多于M2EC，且其在区域中的位置具有战略性，因此FMEC通常服务于大多数节点的请求。所有直方图在单次和联合测试中均表现出相似的分布。具体而言，ParticipAct中节点发起的大部分请求都能在相对较短的时间内得到满足，报告的平均延迟为1.5天至7.5天，这是固定和移动边缘能够满足请求的时间限制。一旦超过此时间限制，请求将直接由节点与云交互来满足，不再与FMEC或M2EC通信。

关于固定边缘计算节点和M2ECs满足的请求数量，我们观察到FMEC相比M2ECs能够响应更多的请求。平均而言，固定边缘节点满足的请求数量百分比为73.5%，而移动边缘满足的请求百分比为26.5%。我们通过运行额外的测试进一步研究了这些百分比，测试中改变了FMEC的位置。我们观察到，在特定设置下，M2ECs满足的请求百分比可增加至40.4%。

我们还研究了所选M2EC的性能。参考给定M2EC的自我网络，我们测量了以下百分比：（1）由该M2EC满足的请求；（2）由其他M2EC满足的请求；（3）未被满足的请求百分比。我们在图4中报告了所选3个M2EC各自的测试结果。结果表明，仅有一个M2EC（如图4中的M2EC 82）存在少量未响应的请求，其数量略高于已满足的请求数量。而在所有情况下，由某个自我网络发起并由其自身的M2EC满足的请求百分比，远高于由其他M2EC满足的请求百分比。在总共生成的5000个请求中，多次单独和联合测试共满足了超过3100个请求，平均请求满足率达到62%。

根据我们之前的实验，得出以下观察结果。首先，我们的M2EC检测算法无法在没有对用户移动性进行先验评估的情况下运行。更具体地说，人类移动性的特征只能通过长期的数据收集活动才能揭示。持续几周的数据集不能代表人类移动性的动态，因此对于FMEC和M2EC的选择均无用处。其次，我们的移动边缘架构依赖于人类移动性的两个关键特征：空间覆盖和社会覆盖。关于空间覆盖，我们首先通过检测ParticipAct中在24小时内拥挤的位置来分析FMEC的部署位置。为此，在[1]中，我们描述了一种利用空间聚类算法揭示兴趣点的方法。另一方面，我们也考虑社会覆盖，即在ParticipAct中检测robust用户社区的能力。为此，我们采用第三节中所述的TILES算法。空间覆盖与社会覆盖的结合，有助于识别不同类型的边缘节点（FMEC和M2EC），这些节点充当用户与云之间的桥梁，使用户能够随时随地访问信息。最后一点涉及周期性选举作为M2EC的节点的机会。我们的结果展示了在预定义数量的M2EC下的性能表现。然而，我们认为研究周期性选举M2EC时的性能表现是有意义的，例如一旦检测到人类移动性规律中的显著偏差时即进行选举。这种情况包括体育比赛、政治会议或常规交通状况中的异常等拥挤事件。

在这些情况下，可以重新执行第3节中提出的M2EC检测算法，以揭示可能被选为M2EC的新节点。我们将这种最后的情况视为下一个目标。

五、讨论与结论

在本研究中，我们探讨了使用移动边缘计算（MEC）架构来支持MCS平台的潜力。采用该架构的优势在于，它能够简化数据在设备之间（无论是固定还是移动设备）的传播，因为MCS平台所采集的数据均可通过短距离通信链路由用户个人设备传输至边缘节点，从而提升架构的可扩展性，并且相比使用宽带通信链路，无需额外成本且对用户设备资源的占用更低。然而，引入MEC架构也带来了新的挑战，包括如何确定安装固定边缘节点的物理位置、架构对用户移动性的适应能力，以及固定边缘节点的维护问题。

基于这些原因，我们建议将传统的多接入边缘计算架构与移动边缘（M2EC）相结合，其中移动边缘是一些被选中的个人设备，在有限的时间内被要求作为移动群智感知（MCS）平台中其他个人设备的边缘节点。引入此类移动边缘具有双重优势：一方面，由于其用户具有移动性，它们可以随机地与其他MCS平台中的设备相遇，即使在没有固定边缘节点的区域也能提供服务，从而以更动态和自适应的方式实现多接入边缘计算的功能；另一方面，它们不会增加架构的额外成本，因为无需进行安装与维护，反而有助于减少对固定边缘节点的需求，从而降低平台的整体成本。然而，由于这些设备本质上属于用户的个人设备，因此必须根据其用户的社会特征进行选择。应优先选择那些在其用户社区中处于中心位置的用户所拥有的设备，因为这些设备更有可能与其他非M2EC设备进行通信。为此，我们提出了一种基于用户社区识别的M2EC选择算法。在真实MCS平台的移动性数据集上进行仿真的结果表明，M2EC能够很好地融入传统的MEC平台，甚至有可能替代固定边缘节点，从而降低整个MCS平台的成本。然而，本次试验的定量实验以及影响M2EC选择的其他因素（如设备能力、电池电量等）的研究将留待未来工作完成。

基于这些结果，我们认为基于M2EC的MAC架构为未来的MCS平台开辟了新颖且有趣的前景，但也引发了关于架构各个方面的新的研究挑战，从固定与移动边缘节点之间的平衡，到M2EC与平台其余部分以及固定边缘节点的交互方式，再到M2EC选择的动态策略，以使承担边缘节点的负担能够在用户之间更好地分担，可能还涉及许多其他方面。目前，我们的研究重点是优化我们的选择算法，以找到固定和移动边缘的最佳组合。