李志云 李英 李建波

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

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

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

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

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

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

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

1 系統(tǒng)模型

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

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

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

1.3 種子用戶選擇

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

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

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

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

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

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

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

2.1 實驗環(huán)境

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

2.2 仿真結(jié)果

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)

[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]. 計算機(jī)科學(xué)， 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.