移動社交網(wǎng)絡中基于用戶動態(tài)需求的D2D數(shù)據(jù)分流方法

李志云 李英 李建波

摘要：針對因數(shù)據(jù)流量的爆炸式增長給蜂窩網(wǎng)絡帶來的流量負擔和網(wǎng)絡擁塞等問題，提出一種基于移動社交網(wǎng)絡中用戶動態(tài)需求的D2D數(shù)據(jù)分流方法。考慮用戶在一天中不同時段的興趣和移動軌跡，構建用于描述用戶流量需求的圖結(jié)構。通過Newman快速算法將移動用戶劃分為不同的社團，同一社團中的用戶具有相似的數(shù)據(jù)需求并且經(jīng)常彼此聯(lián)系。在此情況下，每個社團挑選不同的種子用戶進行數(shù)據(jù)共享。為了最大化蜂窩網(wǎng)絡的數(shù)據(jù)分流，對比五種不同的中心性度量方法選擇種子節(jié)點，采用對比實驗，證明新提出的DDS方案的有效性。 實驗結(jié)果表明，在DDS策略中，PageRank度量方法選擇的種子節(jié)點分流表現(xiàn)最好。

關鍵詞：移動社交網(wǎng)絡;蜂窩網(wǎng)絡;度中心性;種子節(jié)點;D2D數(shù)據(jù)分流

中圖分類號：TP391

文獻標志碼：A

文章編號：1006-1037（2021）01-0001-06

基金項目：國家自然科學基金（批準號：2018YFB2100303）資助;中國基金會（批準號：61802216）資助;中國博士后科學金（批準號：2018M642613）資助;山東省重點研究發(fā)展計劃項目（批準號：2016GGX101032）資助;山東省博士后創(chuàng)新人才（批準號：40618030001）資助。

通信作者：李英，女，博士，副教授，研究方向為移動社交網(wǎng)絡，數(shù)據(jù)分流等。E-mail：yingli_2016@163.com

近年來，隨著移動社交網(wǎng)絡的不斷興起和智能終端設備的不斷發(fā)展，數(shù)據(jù)流量正呈現(xiàn)爆炸式的增長，勢必給移動蜂窩網(wǎng)絡（Mobile Cellular Network ）造成巨大的流量負載和網(wǎng)絡擁塞。因此，移動數(shù)據(jù)分流[1]應運而生并在移動社交網(wǎng)絡（MSN）中引起了廣泛關注。用戶可以找到興趣相同的鄰居，并建立短距離連接以接收內(nèi)容，例如藍牙，Wi-Fi Direct，近場通信（NFC）等，意圖在于充分利用機會網(wǎng)絡的通信優(yōu)勢，將用戶從蜂窩網(wǎng)絡獲取數(shù)據(jù)的方式轉(zhuǎn)移到本地機會通信上。目前，根據(jù)輔助網(wǎng)絡有無基礎設施，數(shù)據(jù)分流方法大體可分為基于基礎設施的數(shù)據(jù)分流和無基礎設施的數(shù)據(jù)分流[2]?；诨A設施的數(shù)據(jù)分流是通過部署一些具有通信、計算和存儲功能的基礎設施來輔助數(shù)據(jù)傳輸[3]。比如，部署毫微微蜂窩基站（Femtoccll）、無線接入點（Wi-Fi AP）等基礎設施。蜂窩網(wǎng)絡的數(shù)據(jù)流量可以通過這些基礎設施實現(xiàn)分流，降低蜂窩網(wǎng)絡的數(shù)據(jù)負載[4]。相比之下，無基礎設施的數(shù)據(jù)分流方法通過用戶之間的機會通信來傳輸數(shù)據(jù)，以減輕蜂窩網(wǎng)絡的負擔。目前一種流行的減輕移動流量負載方法是在盡可能的情況下促進移動用戶之間的機會主義D2D通信[5-6]。CHEN等[7] 通過探索社交網(wǎng)絡中的社交聯(lián)系，研究了合作式D2D通信，基于社會信任和互惠的現(xiàn)象，設計了一種合作機制，以增強用戶之間D2D通信中的有效合作。文獻[8]提出了預期的可用持續(xù)時間（EAD）指標，以評估用戶通過D2D數(shù)據(jù)分流下載對象的機會。這些工作僅專注于用戶在日常生活中的興趣，將其設為固定值，過于片面化，沒有考慮用戶在一天中不同時段的內(nèi)容需求[9]。為此，本文提出了一種動態(tài)的D2D數(shù)據(jù)分流方法，根據(jù)移動用戶在網(wǎng)絡中的動態(tài)需求，分時段選擇一組最佳的種子用戶來共享數(shù)據(jù)。如果某些用戶在一定的時間延遲后仍無法接收內(nèi)容，則直接通過蜂窩網(wǎng)絡下載內(nèi)容。

1 系統(tǒng)模型

在日常生活中，人們對于事物的興趣并不是一成不變的，在不同的時段會擁有不同的興趣內(nèi)容。例如，用戶通常在早上獲取天氣預報信息以便出門，而在晚間休息時更多的會選擇娛樂新聞休閑放松[10]。為此，可以根據(jù)用戶在不同時段的動態(tài)需求來選擇種子用戶進行數(shù)據(jù)分流，以減輕蜂窩網(wǎng)絡的流量負擔。考慮D2D輔助的蜂窩網(wǎng)絡數(shù)據(jù)分流（圖1），假設總共有N個用戶N={1，…，N}，所有用戶都從蜂窩網(wǎng)絡請求某種流行的數(shù)據(jù)[11-12]。運營商首先選擇一些用戶作為種子用戶，通過蜂窩網(wǎng)絡向他們發(fā)送數(shù)據(jù)。其次，種子用戶收到數(shù)據(jù)后，發(fā)送給其附近的用戶。超過時間T后，未收到數(shù)據(jù)的用戶將通過蜂窩網(wǎng)絡獲取數(shù)據(jù)。

1.1 基于用戶動態(tài)需求的權重圖模型

該算法將以最大增加或最小減少的Q值合并兩個社區(qū)。迭代持續(xù)到整個圖網(wǎng)絡合并為一個社團為止。最終的社區(qū)檢測結(jié)果對應于整個合并過程中的最大Q值。

1.3 種子用戶選擇

節(jié)點在社團中的重要性取決于其在社團中的影響力。 節(jié)點與離它最近的節(jié)點分發(fā)請求數(shù)據(jù)，社團中節(jié)點的重要性通常用節(jié)點中心度來衡量。 對此，探索多種中心性度量方法，選擇種子節(jié)點最大化數(shù)據(jù)分流。

（1）度中心性（Degree Centrality）。度中心性是刻畫節(jié)點中心性的最直接度量指標，根據(jù)直連邊的數(shù)量對節(jié)點進行排名識別社團中最受歡迎的節(jié)點。 給定社團Gk，節(jié)點i的度中心性

其中，Ci，j表示與節(jié)點i相鄰的邊的數(shù)量。

（2）緊密中心性（Closeness Centrality）。緊密中心性反映在網(wǎng)絡中某一節(jié)點與其他節(jié)點之間的緊密程度。緊密中心性是由某節(jié)點到網(wǎng)絡中其他節(jié)點最短距離來確定的，越高的緊密中心性意味著這個節(jié)點距離網(wǎng)絡中其他節(jié)點越接近，也就越趨近網(wǎng)絡的中心。緊密中心性

（3）介數(shù)中心性（Betweenness Centrality）。介數(shù)中心性是衡量節(jié)點對信息在整個網(wǎng)絡內(nèi)傳播的重要性的度量，是由節(jié)點出現(xiàn)在其他節(jié)點之間的最短路徑上的情況來決定的[14]，通常具有較高介數(shù)中心性的節(jié)點在網(wǎng)絡中起關鍵作用

其中，F(xiàn)i為在給定社團Gk中與節(jié)點i相連的節(jié)點集合，ρ為阻尼因子，滿足0<ρ<1，通常取0.85。

2 實驗結(jié)果與分析

2.1 實驗環(huán)境

本文運用Visual Studio 2017編譯環(huán)境，采用R語言，選取Infocom2006數(shù)據(jù)集來進行仿真實驗。Infocom2006數(shù)據(jù)集是對Infocom會議人員的流動聯(lián)系進行跟蹤，選擇了具有79個短距離設備和20個遠程設備的參與者來生成連接性跟蹤。原始跟蹤中ID為99的節(jié)點實際上沒有遇到任何其他用戶，因此參與者總數(shù)減少到98個。模擬持續(xù)時間為337 418秒，約391天，依賴于工作區(qū)域的交通需要[17]，將一天分為三個時段：[0，7]、[8，20]、[21，24]，實驗參數(shù)如表1所示。

2.2 仿真結(jié)果

本文通過實驗對以下方法進行比較：1）隨機選擇種子節(jié)點的蜂窩網(wǎng)絡流量負載（Random Scenario，RS）;2）根據(jù)用戶聯(lián)系選擇種子節(jié)點的蜂窩網(wǎng)絡流量負載（Contact-based Scenario， CS）;3）基于用戶動態(tài)需求的種子節(jié)點選擇的蜂窩網(wǎng)絡流量負載（Dynamic Demand Scenario， DDS）。

調(diào)查上述三種策略隨著時間的變化的數(shù)據(jù)分流情況。種子節(jié)點個數(shù)初始化為5。為了選擇合適的種子節(jié)點，CS和DDS策略考慮5種不同的中心性度量，包括度中心性（Degree）、緊密中心性（Closeness）、中間中心性（Betweenness）、PageRank和特征向量中心性（Eigenvector）。隨機選取10次種子節(jié)點，取其每次分流數(shù)據(jù)量的均值作為實驗結(jié)果來準確地估計RS策略分流的效果。如圖2所示，DDS策略顯然在這3種策略中取得了最佳效果。 此外，CS 策略優(yōu)于RS策略，尤其是將PageRank和特征向量用于種子節(jié)點選擇的性能優(yōu)于DDS中的其他三種方法。 相比較而言，RS和CS策略的數(shù)據(jù)分流量均低于500 M。因此，考慮基于移動社交網(wǎng)絡中用戶動態(tài)需求的D2D數(shù)據(jù)分流方法可以最大程度地減少過載網(wǎng)絡中的數(shù)據(jù)。

隨后，研究CS和DDS在不同時段的數(shù)據(jù)分流性能，種子節(jié)點的數(shù)量初始化為5，實驗結(jié)果如圖3所示。與CS相比，DDS的數(shù)據(jù)分流效果在使用度中心性，緊密中心性度和介數(shù)中心性這3種度量方法進行種子選擇方面沒有明顯的改進。但是，通過使用PageRank和特征向量中心性度量方法，可以明顯增加DDS的數(shù)據(jù)分流量，尤其在第二個時段，采用這種兩種方法的DDS策略的流量分流量最大可達到636 M和666 M。

與其他兩種策略相比，DDS策略實現(xiàn)了最佳數(shù)據(jù)分流效果，下一個關鍵步驟是確定種子節(jié)點的數(shù)量。圖4顯示了分流的數(shù)據(jù)量隨種子節(jié)點數(shù)量的變化情況，隨著種子節(jié)點數(shù)量的增多，數(shù)據(jù)的分流量也在呈現(xiàn)一個明顯的上升趨勢，當種子節(jié)點數(shù)量達到25時，數(shù)據(jù)的分流量基本不再發(fā)生變化，保持平穩(wěn)。

當種子節(jié)點數(shù)量低于20時，DDS策略在PageRank和特征向量中心性兩種屬性方面表現(xiàn)良好，這與之前的結(jié)果相一致。這兩個屬性的使用最大程度地減少了2 433 M和 2 376 M流量。隨著種子節(jié)點數(shù)量超過20時，特征向量中心性屬性的優(yōu)勢不再明顯，而PageRank屬性依然保持較好效果，最終分流量達3 000 M。因此，在DDS策略中PageRank是一個較好的度量方法來選擇種子節(jié)點。

3 結(jié)論

本文提出一種基于移動社交網(wǎng)絡中用戶動態(tài)需求的D2D數(shù)據(jù)分流方法（DDS），根據(jù)一天中不同時段的用戶需求構建一個用于社團檢測的圖結(jié)構。為了找到適合社團內(nèi)數(shù)據(jù)共享的種子用戶，比較5種種子節(jié)點選擇方法。研究結(jié)果表明，采用 PageRank種子選擇方法的DDS策略可以實現(xiàn)更好的數(shù)據(jù)分流效果。實驗中，移動用戶不考慮自身損耗的進行彼此合作。實際上，移動用戶由于其用于數(shù)據(jù)傳輸?shù)馁Y源消耗而表現(xiàn)自私性。因此，在以后的研究中將討論用戶對種子選擇的自私性來最大化數(shù)據(jù)分流效果。

參考文獻

[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]姚紅， 白長敏， 胡成玉， 等. 移動數(shù)據(jù)分流研究綜述[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.