移動社交網絡中基于用戶動態需求的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.