移动社交网络中基于用户动态需求的D2D数据分流方法

李志云 李英 李建波

摘要：针对因数据流量的爆炸式增长给蜂窝网络带来的流量负担和网络拥塞等问题，提出一种基于移动社交网络中用户动态需求的D2D数据分流方法。考虑用户在一天中不同时段的兴趣和移动轨迹，构建用于描述用户流量需求的图结构。通过Newman快速算法将移动用户划分为不同的社团，同一社团中的用户具有相似的数据需求并且经常彼此联系。在此情况下，每个社团挑选不同的种子用户进行数据共享。为了最大化蜂窝网络的数据分流，对比五种不同的中心性度量方法选择种子节点，采用对比实验，证明新提出的DDS方案的有效性。 实验结果表明，在DDS策略中，PageRank度量方法选择的种子节点分流表现最好。

关键词：移动社交网络;蜂窝网络;度中心性;种子节点;D2D数据分流

中图分类号：TP391

文献标志码：A

文章编号：1006-1037（2021）01-0001-06

基金项目：国家自然科学基金（批准号：2018YFB2100303）资助;中国基金会（批准号：61802216）资助;中国博士后科学金（批准号：2018M642613）资助;山东省重点研究发展计划项目（批准号：2016GGX101032）资助;山东省博士后创新人才（批准号：40618030001）资助。

通信作者：李英，女，博士，副教授，研究方向为移动社交网络，数据分流等。E-mail：yingli_2016@163.com

近年来，随着移动社交网络的不断兴起和智能终端设备的不断发展，数据流量正呈现爆炸式的增长，势必给移动蜂窝网络（Mobile Cellular Network ）造成巨大的流量负载和网络拥塞。因此，移动数据分流[1]应運而生并在移动社交网络（MSN）中引起了广泛关注。用户可以找到兴趣相同的邻居，并建立短距离连接以接收内容，例如蓝牙，Wi-Fi Direct，近场通信（NFC）等，意图在于充分利用机会网络的通信优势，将用户从蜂窝网络获取数据的方式转移到本地机会通信上。目前，根据辅助网络有无基础设施，数据分流方法大体可分为基于基础设施的数据分流和无基础设施的数据分流[2]。基于基础设施的数据分流是通过部署一些具有通信、计算和存储功能的基础设施来辅助数据传输[3]。比如，部署毫微微蜂窝基站（Femtoccll）、无线接入点（Wi-Fi AP）等基础设施。蜂窝网络的数据流量可以通过这些基础设施实现分流，降低蜂窝网络的数据负载[4]。相比之下，无基础设施的数据分流方法通过用户之间的机会通信来传输数据，以减轻蜂窝网络的负担。目前一种流行的减轻移动流量负载方法是在尽可能的情况下促进移动用户之间的机会主义D2D通信[5-6]。CHEN等[7] 通过探索社交网络中的社交联系，研究了合作式D2D通信，基于社会信任和互惠的现象，设计了一种合作机制，以增强用户之间D2D通信中的有效合作。文献[8]提出了预期的可用持续时间（EAD）指标，以评估用户通过D2D数据分流下载对象的机会。这些工作仅专注于用户在日常生活中的兴趣，将其设为固定值，过于片面化，没有考虑用户在一天中不同时段的内容需求[9]。为此，本文提出了一种动态的D2D数据分流方法，根据移动用户在网络中的动态需求，分时段选择一组最佳的种子用户来共享数据。如果某些用户在一定的时间延迟后仍无法接收内容，则直接通过蜂窝网络下载内容。

1 系统模型

在日常生活中，人们对于事物的兴趣并不是一成不变的，在不同的时段会拥有不同的兴趣内容。例如，用户通常在早上获取天气预报信息以便出门，而在晚间休息时更多的会选择娱乐新闻休闲放松[10]。为此，可以根据用户在不同时段的动态需求来选择种子用户进行数据分流，以减轻蜂窝网络的流量负担。考虑D2D辅助的蜂窝网络数据分流（图1），假设总共有N个用户N={1，…，N}，所有用户都从蜂窝网络请求某种流行的数据[11-12]。运营商首先选择一些用户作为种子用户，通过蜂窝网络向他们发送数据。其次，种子用户收到数据后，发送给其附近的用户。超过时间T后，未收到数据的用户将通过蜂窝网络获取数据。

1.1 基于用户动态需求的权重图模型

该算法将以最大增加或最小减少的Q值合并两个社区。迭代持续到整个图网络合并为一个社团为止。最终的社区检测结果对应于整个合并过程中的最大Q值。

1.3 种子用户选择

节点在社团中的重要性取决于其在社团中的影响力。 节点与离它最近的节点分发请求数据，社团中节点的重要性通常用节点中心度来衡量。 对此，探索多种中心性度量方法，选择种子节点最大化数据分流。

（1）度中心性（Degree Centrality）。度中心性是刻画节点中心性的最直接度量指标，根据直连边的数量对节点进行排名识别社团中最受欢迎的节点。 给定社团Gk，节点i的度中心性

其中，Ci，j表示与节点i相邻的边的数量。

（2）紧密中心性（Closeness Centrality）。紧密中心性反映在网络中某一节点与其他节点之间的紧密程度。紧密中心性是由某节点到网络中其他节点最短距离来确定的，越高的紧密中心性意味着这个节点距离网络中其他节点越接近，也就越趋近网络的中心。紧密中心性

（3）介数中心性（Betweenness Centrality）。介数中心性是衡量节点对信息在整个网络内传播的重要性的度量，是由节点出现在其他节点之间的最短路径上的情况来决定的[14]，通常具有较高介数中心性的节点在网络中起关键作用

其中，Fi为在给定社团Gk中与节点i相连的节点集合，ρ为阻尼因子，满足0<ρ<1，通常取0.85。

2 实验结果与分析

2.1 实验环境

本文运用Visual Studio 2017编译环境，采用R语言，选取Infocom2006数据集来进行仿真实验。Infocom2006数据集是对Infocom会议人员的流动联系进行跟踪，选择了具有79个短距离设备和20个远程设备的参与者来生成连接性跟踪。原始跟踪中ID为99的节点实际上没有遇到任何其他用户，因此参与者总数减少到98个。模拟持续时间为337 418秒，约391天，依赖于工作区域的交通需要[17]，将一天分为三个时段：[0，7]、[8，20]、[21，24]，实验参数如表1所示。

2.2 仿真結果

本文通过实验对以下方法进行比较：1）随机选择种子节点的蜂窝网络流量负载（Random Scenario，RS）;2）根据用户联系选择种子节点的蜂窝网络流量负载（Contact-based Scenario， CS）;3）基于用户动态需求的种子节点选择的蜂窝网络流量负载（Dynamic Demand Scenario， DDS）。

调查上述三种策略随着时间的变化的数据分流情况。种子节点个数初始化为5。为了选择合适的种子节点，CS和DDS策略考虑5种不同的中心性度量，包括度中心性（Degree）、紧密中心性（Closeness）、中间中心性（Betweenness）、PageRank和特征向量中心性（Eigenvector）。随机选取10次种子节点，取其每次分流数据量的均值作为实验结果来准确地估计RS策略分流的效果。如图2所示，DDS策略显然在这3种策略中取得了最佳效果。 此外，CS 策略优于RS策略，尤其是将PageRank和特征向量用于种子节点选择的性能优于DDS中的其他三种方法。 相比较而言，RS和CS策略的数据分流量均低于500 M。因此，考虑基于移动社交网络中用户动态需求的D2D数据分流方法可以最大程度地减少过载网络中的数据。

随后，研究CS和DDS在不同时段的数据分流性能，种子节点的数量初始化为5，实验结果如图3所示。与CS相比，DDS的数据分流效果在使用度中心性，紧密中心性度和介数中心性这3种度量方法进行种子选择方面没有明显的改进。但是，通过使用PageRank和特征向量中心性度量方法，可以明显增加DDS的数据分流量，尤其在第二个时段，采用这种两种方法的DDS策略的流量分流量最大可达到636 M和666 M。

与其他两种策略相比，DDS策略实现了最佳数据分流效果，下一个关键步骤是确定种子节点的数量。图4显示了分流的数据量随种子节点数量的变化情况，随着种子节点数量的增多，数据的分流量也在呈现一个明显的上升趋势，当种子节点数量达到25时，数据的分流量基本不再发生变化，保持平稳。

当种子节点数量低于20时，DDS策略在PageRank和特征向量中心性两种属性方面表现良好，这与之前的结果相一致。这两个属性的使用最大程度地减少了2 433 M和 2 376 M流量。随着种子节点数量超过20时，特征向量中心性属性的优势不再明显，而PageRank属性依然保持较好效果，最终分流量达3 000 M。因此，在DDS策略中PageRank是一个较好的度量方法来选择种子节点。

3 结论

本文提出一种基于移动社交网络中用户动态需求的D2D数据分流方法（DDS），根据一天中不同时段的用户需求构建一个用于社团检测的图结构。为了找到适合社团内数据共享的种子用户，比较5种种子节点选择方法。研究结果表明，采用 PageRank种子选择方法的DDS策略可以实现更好的数据分流效果。实验中，移动用户不考虑自身损耗的进行彼此合作。实际上，移动用户由于其用于数据传输的资源消耗而表现自私性。因此，在以后的研究中将讨论用户对种子选择的自私性来最大化数据分流效果。

参考文献

[1]REBECCHI F， DE AMORIM M D， CONAN V， et al. Data offloading techniques in cellular networks： a survey[J]. IEEE Communications Surveys &; Tutorials， 2014，17（2）： 580-603.

[2]姚红， 白长敏， 胡成玉， 等. 移动数据分流研究综述[J]. 计算机科学， 2014， 41（11）：182-186.

[3]KOLODZIEJ J， ULLAH K S， WANG L Z， et al. An application of Markov jump process model for activity-based indoor mobility prediction in wireless networks[J]. Frontiers of Information Technology， 2011：17-28.

[4]WANG T， LI P C， WANG X B， et al. A comprehensive survey on mobile data offloading in heterogeneous network[J]. Wireless Networks， 2017， 25（2）：573-584.

[5]ADNAN A， AGHVAMI H， AMANI M. A survey on mobile data offloading： Technical and business perspectives[J]. IEEE Wireless Communications， 2013，20（2）：104-112.

[6]SANJIT K D， SIDDHANT D， JIBITESH M， et al. Opportunistic mobile data offloading using machine learning approach[J]. Wireless Personal Communications， 2020， 110（1）： 125-139.

[7]CHEN X， PROULX B， GONG X W， et al. Exploiting social ties for cooperative D2D communications： A mobile social networking case[J]. IEEE/ACM Transactions on Networking， 2015，23（5）：1471-1484.

[8]WANG Z H， SHAH-MANSOURI H. How to download more data from neighbors？ A metric for D2D data offloading Opportunity[J]. IEEE Transactions on Mobile Computing， 2017，16（6）： 1658-1675.

[9]LI Y H， LI J B， CHEN J W， et al. Seed selection for data offloading based on social and interest graphs[J]. Tech Science Press， 2018， 57（3）： 571-587.

[10] YANG H， ZHANG X T， CHEN H K， et al. DEED： Dynamic energy-efficient data offloading for IoT applications under unstable channel conditions[J]. Future Generation Computer Systems， 2019， 96： 425-437.

[11] EMMANOUIL P， EIRINI K， HADEER E， et al. A game theoretic path selection to support security in device-to-device communications[J]. Ad Hoc Networks， 2017， 56： 28-42.

[12] QIN J， ZHU H Z， ZHU Y M， et al. Exploiting dynamic sociality for mobile advertising in vehicular networks[J]. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（6）： 1770-1782.

[13] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E， 2004， 69（6）： 066133.

[14] Freeman C. Centrality in social networks I： Conceptual clarification[J]. Social Networks， 1979，1（3）： 215-239.

[15] BRIN S， PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks And ISDN System，1998， 30（1-7）： 107-119.

[16] BONACICH P. Power and centrality： a family of measures[J]. American Journal of Sociology， 1987， 92（5）：1170-1182.

[17] XU F L， LI Y， WANG H D. Understanding mobile traffic patterns of large scale cellular towers in urban environment[J]. Internet Measurement Conference， 2015， 25：225-238.