移動(dòng)社交網(wǎng)絡(luò)中基于影響力的數(shù)據(jù)轉(zhuǎn)發(fā)算法

劉艷萍， 王青山， 王 琦， 付沙沙， 任麗麗

（合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院，安徽 合肥 230009）

移動(dòng)社交網(wǎng)絡(luò)中基于影響力的數(shù)據(jù)轉(zhuǎn)發(fā)算法

劉艷萍， 王青山， 王 琦， 付沙沙， 任麗麗

（合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院，安徽 合肥 230009）

在移動(dòng)社交網(wǎng)絡(luò)中，人們通過(guò)攜帶無(wú)線設(shè)備在近距離范圍內(nèi)彼此傳遞信息，從而達(dá)到信息的傳播。由于移動(dòng)社交網(wǎng)絡(luò)中一般不存在端到端的連接，使得數(shù)據(jù)轉(zhuǎn)發(fā)算法成為一個(gè)重要問(wèn)題。文章從社區(qū)和節(jié)點(diǎn)的社會(huì)屬性角度，利用社區(qū)和節(jié)點(diǎn)的影響力，提出了一種基于影響力的數(shù)據(jù)轉(zhuǎn)發(fā)算法（data forwarding algorithm based on impact，DFAI）。在該算法中，攜帶數(shù)據(jù)包的節(jié)點(diǎn)只有在遇到影響力達(dá)到一定要求的節(jié)點(diǎn)時(shí)，才拷貝數(shù)據(jù)包給相遇節(jié)點(diǎn)。仿真試驗(yàn)結(jié)果顯示，與經(jīng)典的Epidemic和Label算法相比，DFAI可以明顯降低網(wǎng)絡(luò)開(kāi)銷，同時(shí)接近Epidemic算法達(dá)到的最大傳遞率。

移動(dòng)社交網(wǎng)絡(luò)；影響力；轉(zhuǎn)發(fā)；延遲

網(wǎng)絡(luò)中由于節(jié)點(diǎn)密度稀疏、電量有限等原因?qū)е聰?shù)據(jù)在傳輸過(guò)程中不能確保端到端之間存在一條路徑，這類網(wǎng)絡(luò)被稱為時(shí)延容忍網(wǎng)絡(luò)，也叫容遲網(wǎng)絡(luò)（delay and disruption－tolerant interoperable networking，DTN）［1－2］。DTN 的提出是為了解決網(wǎng)絡(luò)中端到端連接和節(jié)點(diǎn)資源都有限的問(wèn)題，滿足隨意異步消息的可靠傳遞。DTN的研究和發(fā)展將為軍事戰(zhàn)爭(zhēng)、航天通信、災(zāi)難恢復(fù)、應(yīng)急搶險(xiǎn)等領(lǐng)域的消息交互提供有力的科學(xué)理論和技術(shù)支持，并會(huì)有力地推進(jìn)未來(lái)網(wǎng)絡(luò)通信智能化、泛在化、融合化的發(fā)展。

移動(dòng)社交網(wǎng)絡(luò)是DTN網(wǎng)絡(luò)［3］應(yīng)用中的一種，即攜帶移動(dòng)無(wú)線終端設(shè)備的網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)設(shè)備近距離傳遞數(shù)據(jù)并共享網(wǎng)絡(luò)中的服務(wù)。近年來(lái)，智能手機(jī)和無(wú)線網(wǎng)絡(luò)技術(shù)（WIFI、3G、藍(lán)牙等）的發(fā)展使得移動(dòng)社交網(wǎng)絡(luò)成為無(wú)線網(wǎng)絡(luò)研究領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題。由于在一般情況下此網(wǎng)絡(luò)中不存在端到端的連接，所以傳統(tǒng)的路由協(xié)議無(wú)法直接應(yīng)用于移動(dòng)社交網(wǎng)絡(luò)，因此數(shù)據(jù)轉(zhuǎn)發(fā)策略是一個(gè)關(guān)鍵且極具挑戰(zhàn)性的問(wèn)題。在移動(dòng)社交網(wǎng)絡(luò)中往往采取“存儲(chǔ)－攜帶－轉(zhuǎn)發(fā)”的方法來(lái)傳輸報(bào)文。Epidemic算法［4］是信息在相遇節(jié)點(diǎn)之間存儲(chǔ)并被轉(zhuǎn)發(fā)給所有相鄰節(jié)點(diǎn)，達(dá)到最大化傳遞率和最小化延遲的目的；但是，該算法容易引起信息洪泛和較多資源開(kāi)銷，受緩存及帶寬影響很大，因此一些路由算法期望以較低的開(kāi)銷達(dá)到Epidemic算法的傳遞率和延遲性能。Spray and Wait算法［5］和 Spray and Focus算法［6］都將路由算法分為2個(gè)階段，第1階段稱為噴灑（spray），即在網(wǎng)絡(luò)中產(chǎn)生固定數(shù)目的拷貝進(jìn)行傳播；第2階段分別為等待（wait）和焦點(diǎn)（focus），在等待階段攜帶數(shù)據(jù)包的節(jié)點(diǎn)除碰到目的節(jié)點(diǎn)外，不再傳播數(shù)據(jù)包，在焦點(diǎn)階段攜帶數(shù)據(jù)包的節(jié)點(diǎn)除碰到目的節(jié)點(diǎn)或效用值比本節(jié)點(diǎn)高的節(jié)點(diǎn)外，不再傳播數(shù)據(jù)包。Delegation forwarding算法［7］假定每個(gè)節(jié)點(diǎn)都有一個(gè)相關(guān)的質(zhì)量參數(shù)，節(jié)點(diǎn)在遇到質(zhì)量參數(shù)比之前遇到的任何節(jié)點(diǎn)質(zhì)量參數(shù)都高的節(jié)點(diǎn)時(shí)才轉(zhuǎn)發(fā)數(shù)據(jù)包；該算法雖然思想簡(jiǎn)單，但有效地減少了資源開(kāi)銷。

近年來(lái)的研究熱點(diǎn)是利用人類的社會(huì)聯(lián)系模式設(shè)計(jì)路由算法，Label算法［8］針對(duì)同一社區(qū)的節(jié)點(diǎn)聯(lián)系緊密的特性，僅將數(shù)據(jù)包拷貝給目的節(jié)點(diǎn)所在的社區(qū)節(jié)點(diǎn)，從而大大提高了數(shù)據(jù)包傳輸?shù)男?。Bubble rap算法［9］從社區(qū)以及節(jié)點(diǎn)的中心性2個(gè)方面來(lái)設(shè)計(jì)轉(zhuǎn)發(fā)算法；在該算法中，每個(gè)節(jié)點(diǎn)具有全局秩和局部秩，當(dāng)攜帶數(shù)據(jù)包的節(jié)點(diǎn)A和一個(gè)節(jié)點(diǎn)B相遇時(shí)，在以下2種情況下節(jié)點(diǎn)A產(chǎn)生一個(gè)拷貝給節(jié)點(diǎn)B：①節(jié)點(diǎn)A、B和目的節(jié)點(diǎn)同時(shí)屬于同一社區(qū)且節(jié)點(diǎn)A的局部秩比節(jié)點(diǎn)B大；② 節(jié)點(diǎn)A和目的節(jié)點(diǎn)不屬于同一社區(qū)，如果節(jié)點(diǎn)B和目的節(jié)點(diǎn)屬于同一社區(qū)或者節(jié)點(diǎn)B全局秩比節(jié)點(diǎn)A大。Del Que算法［10］從源節(jié)點(diǎn)的鄰居中選擇若干節(jié)點(diǎn)去目的社區(qū)查詢信息并且返回信息，同時(shí)滿足信息查詢概率大于等于一定概率。

本文同時(shí)考慮節(jié)點(diǎn)和社區(qū)的社會(huì)屬性，設(shè)計(jì)基于它們影響力的數(shù)據(jù)轉(zhuǎn)發(fā)算法（data forwarding algorithm based on impact，DFAI）。在一些有較多節(jié)點(diǎn)出現(xiàn)的社區(qū)，源節(jié)點(diǎn)有更大的機(jī)會(huì)偶遇目的節(jié)點(diǎn)，如學(xué)校食堂、迎新晚會(huì)現(xiàn)場(chǎng)、學(xué)術(shù)交流會(huì)場(chǎng)等，定義這些社區(qū)的影響力為大；同時(shí)，經(jīng)常出現(xiàn)在這些社區(qū)的節(jié)點(diǎn)，與其他節(jié)點(diǎn)相比有更大的概率遇到目的節(jié)點(diǎn)，相應(yīng)定義這些節(jié)點(diǎn)的影響力為較大。因此，從社會(huì)網(wǎng)的觀點(diǎn)來(lái)看，人們共享一些興趣愛(ài)好而成為一個(gè)團(tuán)體，通過(guò)DFAI算法盡量選擇影響力大的節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包，達(dá)到提高傳遞率和減少網(wǎng)絡(luò)開(kāi)銷的目的。

1 網(wǎng)絡(luò)模型

由聞名的小世界模型可知，人們通常因?yàn)榕d趣愛(ài)好、職業(yè)及一些社會(huì)屬性屬于多個(gè)社區(qū)。若移動(dòng)社交網(wǎng)絡(luò)包含N1個(gè)“熱點(diǎn)”地理區(qū)域社區(qū)，每個(gè)社區(qū)有一個(gè)固定的AP（access point）配置無(wú)線訪問(wèn)設(shè)備，N2個(gè)攜帶無(wú)線訪問(wèn)設(shè)備的人可以在網(wǎng)絡(luò)中隨意走動(dòng)。將該網(wǎng)絡(luò)模型化為一個(gè)圖G＝（V，E），其中V為N1個(gè)AP和N2個(gè)人組成的N（N＝N1＋N2）頂點(diǎn)集合；E為頂點(diǎn)之間形成的邊集合。定義ti，j（1≤i≤N，1≤j≤N1）為節(jié)點(diǎn)i位于社區(qū)j中的累積時(shí)間。

定義1 當(dāng)且僅當(dāng)ti，j≥λ（1≤i≤N，1≤j≤N1）時(shí)，節(jié)點(diǎn)i屬于社區(qū)j，其中λ是閾值。

在上述定義的基礎(chǔ)上，社區(qū)j的影響力Icj定義為該社區(qū)中節(jié)點(diǎn)的個(gè)數(shù)，則節(jié)點(diǎn)的影響力In i為其所在社區(qū)的影響力之和，即

其中，xi，j表示節(jié)點(diǎn)i是否屬于社區(qū)j，如果節(jié)點(diǎn)i屬于社區(qū)j，則xi，j＝1，否則xi，j＝0。由（1）式可知，若社區(qū)l、m、n的影響力分別為9、8、6，節(jié)點(diǎn)i屬于社區(qū)l、m，節(jié)點(diǎn)k屬于社區(qū)m、n，則節(jié)點(diǎn)i、j的影響力分別為17和14，節(jié)點(diǎn)i比k有更好的數(shù)據(jù)轉(zhuǎn)發(fā)性能。

2 基于影響力的數(shù)據(jù)轉(zhuǎn)發(fā)算法

作為AP，將統(tǒng)計(jì)每個(gè)進(jìn)入本社區(qū)的節(jié)點(diǎn)的累積時(shí)間，然后根據(jù)定義1判斷該節(jié)點(diǎn)是否屬于本社區(qū)，從而計(jì)算出社區(qū)的影響力。同樣當(dāng)節(jié)點(diǎn)進(jìn)入社區(qū)時(shí)，也會(huì)根據(jù)定義1判斷自己是否屬于該社區(qū)，如果屬于該社區(qū)，則通過(guò)和AP聯(lián)系獲得該社區(qū)的影響力，再計(jì)算出自己的影響力。

在基于影響力的數(shù)據(jù)轉(zhuǎn)發(fā)算法（DFAI）中，希望影響力越大的節(jié)點(diǎn)越多地參與數(shù)據(jù)轉(zhuǎn)發(fā)。假設(shè)攜帶數(shù)據(jù)包p的節(jié)點(diǎn)i遇到節(jié)點(diǎn)j時(shí)，DFAI算法步驟如下：

（1）當(dāng)節(jié)點(diǎn)j也攜帶數(shù)據(jù)包p時(shí)，轉(zhuǎn)到步驟（3）。

（2）當(dāng)節(jié)點(diǎn)j不攜帶數(shù)據(jù)包p時(shí)，若節(jié)點(diǎn)j和目的節(jié)點(diǎn)屬于同一社區(qū)且Inj≥βIni，則拷貝數(shù)據(jù)包給節(jié)點(diǎn)j；若節(jié)點(diǎn)j和目的節(jié)點(diǎn)不屬于同一社區(qū)且Inj≥Ini，也拷貝數(shù)據(jù)包給節(jié)點(diǎn)j。

（3）結(jié)束。

在步驟（2）中，β∈［0，1］為一個(gè)閾值；條件表達(dá)式Inj≥βIni表示目的社區(qū)的節(jié)點(diǎn)只要其影響力達(dá)到攜帶數(shù)據(jù)包節(jié)點(diǎn)影響力的β倍，就可以獲得拷貝。

若節(jié)點(diǎn)i同時(shí)屬于社區(qū)l和m，節(jié)點(diǎn)k同時(shí)屬于社區(qū)m 和n，且Inl＝9，Inm＝8，Inn＝6，β＝0.8，則Ini＝17，Ink＝14。根據(jù)DFAI算法，如果節(jié)點(diǎn)k不屬于目的節(jié)點(diǎn)社區(qū)，則根據(jù)Ink＜Ini可知節(jié)點(diǎn)i不會(huì)拷貝數(shù)據(jù)包給節(jié)點(diǎn)k；否則根據(jù)Ink≥Ini拷貝數(shù)據(jù)包給節(jié)點(diǎn)k。DFAI考慮了具有相同興趣的節(jié)點(diǎn)有較大概率再次相遇，通過(guò)選擇影響力較大的節(jié)點(diǎn)來(lái)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，使轉(zhuǎn)發(fā)策略達(dá)到最優(yōu)。

3 性能評(píng)價(jià)

本文使用Infocom06的真實(shí)跟蹤數(shù)據(jù)進(jìn)行模擬實(shí)驗(yàn)，該數(shù)據(jù)是2006年西班牙巴塞羅那的Infocom會(huì)議上由78個(gè)學(xué)生通過(guò)攜帶Imote設(shè)備采集得到的，會(huì)場(chǎng)布置20個(gè)固定Imote設(shè)備作為AP，分布在不同區(qū)域形成社區(qū)。本文將DFAI算法與Epidemic和Label算法進(jìn)行比較。

在Epidemic算法中，信息被相遇節(jié)點(diǎn)存儲(chǔ)并被轉(zhuǎn)發(fā)給所有相鄰節(jié)點(diǎn)；在Label算法中，攜帶數(shù)據(jù)包的節(jié)點(diǎn)只是將數(shù)據(jù)包拷貝給目的社區(qū)節(jié)點(diǎn)，從而減少網(wǎng)絡(luò)開(kāi)銷。用以下量度來(lái)衡量不同轉(zhuǎn)發(fā)策略的性能：① 傳遞率，網(wǎng)絡(luò)中被成功傳遞到目的節(jié)點(diǎn)的數(shù)據(jù)包占所有發(fā)送數(shù)據(jù)包的比率；② 延遲，數(shù)據(jù)包從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)所經(jīng)歷的時(shí)間；③ 開(kāi)銷，采用一個(gè)數(shù)據(jù)包被成功傳遞時(shí)在網(wǎng)絡(luò)中產(chǎn)生的拷貝數(shù)目。數(shù)據(jù)包存在時(shí)間（time－to－live）為24 h，源節(jié)點(diǎn)和目的節(jié)點(diǎn)從移動(dòng)節(jié)點(diǎn)中隨機(jī)選取，每個(gè)實(shí)驗(yàn)結(jié)果都是300次運(yùn)行結(jié)果的平均值。

研究將λ從10 min變化到40 min對(duì)3種算法性能的影響，仿真結(jié)果如圖1所示。

從圖1a中可以看出，DFAI算法傳遞率接近Epidemic算法，高于Label算法；Epidemic取得最大傳遞率，是因?yàn)椴捎昧撕榉翰呗裕浑S著λ增大，DFAI算法和Epidemic算法的傳遞率幾乎不變，而Label算法的傳遞率有所變小。從圖1b中可以看出，DFAI算法的開(kāi)銷最小，最多比Epidemic和Label算法分別降低35.0%和27.4%。從圖1c中可以看出，DFAI算法的延遲比Epi－demic和Label算法稍有提高，最多提高3.1%和2.5%。

圖1 3種算法的網(wǎng)絡(luò)性能隨閾值λ的變化

將節(jié)點(diǎn)的發(fā)包時(shí)刻從上午8：00變化到下午14：00，仿真結(jié)果如圖2所示。

由圖2a可以看出，3種算法的傳遞率隨著時(shí)間的變大而降低，在相同條件下DFAI算法的傳遞率都比Label算法高。由圖2b可以看出，DFAI算法開(kāi)銷比Epidemic算法和Label算法都低，最多降低35.0%和26.3%，這是因?yàn)镈FAI算法只有在遇到目的節(jié)點(diǎn)社區(qū)中的節(jié)點(diǎn)或者其他影響力達(dá)到一定要求的節(jié)點(diǎn)時(shí)，才會(huì)轉(zhuǎn)發(fā)數(shù)據(jù)包給它們，從而減少了網(wǎng)絡(luò)中拷貝數(shù)目。由圖2c可以看出，DFAI算法的延遲比其他2種算法稍許提高。

圖2 3種算法的網(wǎng)絡(luò)性能隨發(fā)包時(shí)刻的變化

本文提出的DFAI算法考慮了具有相同興趣的節(jié)點(diǎn)有較大概率再次相遇，或經(jīng)較少轉(zhuǎn)發(fā)次數(shù)到達(dá)目的節(jié)點(diǎn)，通過(guò)選擇影響力大的節(jié)點(diǎn)來(lái)使轉(zhuǎn)發(fā)性能達(dá)到最優(yōu)；與Epidemic和Label算法相比，DFAI算法依賴于社區(qū)和節(jié)點(diǎn)的影響力進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，能夠提供更好的轉(zhuǎn)發(fā)效果。

4 結(jié)束語(yǔ)

隨著無(wú)線移動(dòng)設(shè)備數(shù)量的高速增長(zhǎng)以及功能的不斷豐富，移動(dòng)社交網(wǎng)絡(luò)越來(lái)越廣泛地被關(guān)注。

本文提出了基于影響力的數(shù)據(jù)轉(zhuǎn)發(fā)算法DFAI，利用節(jié)點(diǎn)的影響力對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)，使信息在盡量小的網(wǎng)絡(luò)開(kāi)銷下成功地交付給目的節(jié)點(diǎn)。仿真結(jié)果表明，相比于經(jīng)典的Epidemic和Label算法，DFAI算法明顯降低了網(wǎng)絡(luò)開(kāi)銷，并且在傳遞率方面接近于Epidemic算法。

［1］Balasubramanian A，Levine B N，Venkataramani A.DTN routing as a resource allocation problem［C］／／Proceedings of SIGCOMM 2007，Kyoto，2007：373－384.

［2］柏亞平，王青山，孫雪蓮.DTN網(wǎng)絡(luò)中一種基于區(qū)域的緩存區(qū)管理策略［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，36（9）：1063－1067.

［3］Ioannidis S，Chaintreau A，Massoulie L.Optimal and scalable distribution of content updates over a mobile social network［C］／／Proceedings of INFOCOM 2009，IEEE，Rio de Janeiro，2009：1422－1430.

［4］Vahdat A，Becker D.Epidemic routing for partially－connected ad hoc networks［R］.San Diego：University of California，San Diego，2000.

［5］Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait：an efficient routing scheme for intermittently connected mobile networks［C］／／Proceedings of the 2005 ACM SIGCOMM Workshop.New York：ACM Press，2005：252－259.

［6］Spyropoulos T，Psounis K，Raghavendra C S.Spray and focus：efficient mobility－assisted routing for heterogeneous and correlated mobility［C］／／Proceedings of Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops.White Plains：IEEE Press，2007：79－85.

［7］Erramilli V，Crovella M，Chaintreau A，et al.Delegation forwarding［C］／／Proceedings of MobiHoc’08.New York：ACM Press，2008：251－260.

［8］Pan Hui，Crowcroft J.How Small labels create big improvements［C］／／Proceedings of Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops. White Plains：IEEE Press，2007：65－70.

［9］Pan Hui，Crowcroft J，Yoneki E.Bubble rap：social－based forwarding in delay－tolerant networks［J］.IEEE Transactions on Mobile Computing，2011，10（11）：1576－1589.

［10］Fan Jialu，Chen Jiming，Du Yuan，et al.Del Que：a socially－aware delegation query scheme in delay－tolerant networks［J］.IEEE Transactions on Vehicular Technology，2011，60（5）：2181－2193.

Data forwarding algorithm based on impact in mobile social networks

LIU Yan－ping， WANG Qing－shan， WANG Qi， FU Sha－sha， REN Li－li
（School of Mathematics，Hefei University of Technology，Hefei 230009，China）

Mobile social users can communicate by physical interact with each other via mobile device in mobile social networks.In view of the intermittent and uncertain network connectivity in the mobile social network，the data forwarding algorithm becomes important.From the social perspective of community and node，a data forwarding algorithm based on impact（DFAI）is proposed in this paper.In DFAI，the node with the packet only copies to the encounter node whose impact meets certain requirement.The simulation results show that the proposed algorithm can reduce network overhead obviously compared with Epidemic algorithm and Label algorithm，and its maximum delivery ratio is close to that obtained by Epidemic algorithm.

mobile social network；impact；forwarding；delay

TP301.6

A

1003－5060（2015）02－0195－04

10.3969／j.issn.1003－5060.2015.02.012

2014－01－15；

2014－04－15

安徽省自然科學(xué)基金資助項(xiàng)目（1208085MF89；1308085MF87）；教育部留學(xué)回國(guó)人員科研基金資助項(xiàng)目

（2013JYLH0280）和高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目（2013111120018）

劉艷萍（1985－），女，安徽阜陽(yáng)人，合肥工業(yè)大學(xué)碩士生；

王青山（1987－），男，安徽合肥人，博士，合肥工業(yè)大學(xué)副教授，碩士生導(dǎo)師.

（責(zé)任編輯 胡亞敏）