黃少芬， 王 楊， 孟 丹， 趙傳信， 趙晨曦， 許閃閃， 方 群

0 引 言

機(jī)會社會網(wǎng)絡(luò)(Opportunistic Social Network，OSN)是一種以人為主體的機(jī)會網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)具有社會屬性。其主要特點(diǎn)：一是源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間進(jìn)行通信時(shí)不存在完整的路徑[3]，二是消息的轉(zhuǎn)發(fā)主要依賴節(jié)點(diǎn)的“存儲—攜帶—轉(zhuǎn)發(fā)”方法，將消息送達(dá)到目標(biāo)節(jié)點(diǎn)。

針對機(jī)會社會網(wǎng)絡(luò)轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇問題，目前，國內(nèi)外的相關(guān)研究主要分為以下三類：1)傳染病轉(zhuǎn)發(fā)(Epidemic Forwarding)機(jī)制[4]：運(yùn)用洪泛的思想去復(fù)制網(wǎng)絡(luò)中節(jié)點(diǎn)的消息副本，其優(yōu)點(diǎn)是具有較高的消息投遞成功率，但是緩存資源開銷大。2)基于上下文感知(Context-aware Forwarding)轉(zhuǎn)發(fā)機(jī)制[7]：主要通過獲取節(jié)點(diǎn)移動速度、緩存大小、移動方向，并結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等特點(diǎn)，消息傳輸過程中根據(jù)上下文感知判斷并決定合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)。3)基于社區(qū)感知(Community-aware Forwarding)轉(zhuǎn)發(fā)機(jī)制[8]：采用單副本半隱式馬爾可夫模型轉(zhuǎn)發(fā)方法，通過節(jié)點(diǎn)在不同周期下的接觸方式相似性進(jìn)行社區(qū)發(fā)現(xiàn)。

以上三種轉(zhuǎn)發(fā)方法主要針對節(jié)點(diǎn)消息轉(zhuǎn)發(fā)機(jī)制問題，忽略了轉(zhuǎn)發(fā)節(jié)點(diǎn)的相遇概率大小以及節(jié)點(diǎn)之間的社會關(guān)系強(qiáng)度差異。本文主要工作是在充分考慮節(jié)點(diǎn)的社會屬性,利用社區(qū)內(nèi)節(jié)點(diǎn)的活躍度能夠增加社區(qū)之間聯(lián)系的基礎(chǔ)上,提出了一種基于貝葉斯概率樹節(jié)點(diǎn)選擇方法以減少消息平均時(shí)延和路由開銷比，提高消息投遞成功率。

1 網(wǎng)絡(luò)模型及問題描述

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

定義1:本文定義網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)包含節(jié)點(diǎn)和鏈路組成的連通圖，即為G=(N,L)，N代表節(jié)點(diǎn)組成的集合，則L代表節(jié)點(diǎn)間存在邊的集合,表示節(jié)點(diǎn)與節(jié)點(diǎn)的連接狀態(tài)。節(jié)點(diǎn)之間存在連接表示節(jié)點(diǎn)在過去的時(shí)間內(nèi)相遇過并轉(zhuǎn)發(fā)消息，否則沒有。

定義2:(社區(qū)活躍度)表示節(jié)點(diǎn)離開所在社區(qū)去訪問網(wǎng)絡(luò)中其他社區(qū)的次數(shù)，同時(shí)也表示社區(qū)的聚集情況[8]。社區(qū)活躍度越大，節(jié)點(diǎn)離開本地社區(qū)的概率就越大，與其他社區(qū)節(jié)點(diǎn)相遇次數(shù)增加。反之，概率越小，相遇機(jī)會變小。

1.2 問題描述

圖1 機(jī)會社會網(wǎng)絡(luò)應(yīng)用場景示意圖Fig.1 Opportunity social network scenario diagram

假設(shè)該網(wǎng)絡(luò)模型由m個(gè)社區(qū)、n個(gè)節(jié)點(diǎn)所組成，在消息轉(zhuǎn)發(fā)時(shí)每個(gè)節(jié)點(diǎn)只屬于一個(gè)社區(qū)，不考慮節(jié)點(diǎn)自私行為。處于同一個(gè)社區(qū)，節(jié)點(diǎn)間交互次數(shù)較多，聯(lián)系較頻繁。因此，可以利用社會關(guān)系強(qiáng)度選擇節(jié)點(diǎn)進(jìn)行消息傳輸，從而降低消息平均時(shí)延。相反，若節(jié)點(diǎn)處于不同的社區(qū)，就要先通過尋找社區(qū)，其次在社區(qū)內(nèi)查找社會關(guān)系強(qiáng)度高的節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)。根據(jù)社交權(quán)值大小，根據(jù)節(jié)點(diǎn)的權(quán)值判斷是否可作為消息轉(zhuǎn)發(fā)節(jié)點(diǎn)，保證消息在社區(qū)內(nèi)能夠迅速轉(zhuǎn)發(fā)。如圖1所示。

由圖1的機(jī)會社會網(wǎng)絡(luò)應(yīng)用場景示意圖可看出，節(jié)點(diǎn)分布在同一個(gè)社區(qū)比較密集，聯(lián)系較頻繁，傳輸效率高。而不同社區(qū)之間進(jìn)行連接就需要選擇社交權(quán)值比較大的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，保證了消息傳輸?shù)母咝浴?/p>

圖2 社團(tuán)結(jié)構(gòu)示意圖Fig.2 Community structure diagram

1.2.1 社團(tuán)結(jié)構(gòu) 在機(jī)會社會網(wǎng)絡(luò)的應(yīng)用場景中，節(jié)點(diǎn)由于地理位置、興趣愛好等劃分為不同社團(tuán)。而社團(tuán)結(jié)構(gòu)又把節(jié)點(diǎn)劃分成不同的社區(qū)，社區(qū)內(nèi)的節(jié)點(diǎn)分布均勻，連接頻繁，社區(qū)間的節(jié)點(diǎn)連接匱乏。在日常生活中和專業(yè)合作中，人們往往會因?yàn)楣餐d趣、工作地點(diǎn)等形成社團(tuán)結(jié)構(gòu)，圖2表示為機(jī)會社會網(wǎng)絡(luò)一個(gè)具有3個(gè)社團(tuán)結(jié)構(gòu)和15個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖。

1.2.2 節(jié)點(diǎn)消息轉(zhuǎn)發(fā)策略 應(yīng)用場景假設(shè)為某省一所高校，同一院系的同學(xué)、老師等可以看作一個(gè)小社團(tuán)，同一院系的成員聯(lián)系緊密，具有很強(qiáng)的社會關(guān)系，能夠?qū)⑾⒀杆僭谄渲袀鬏敚欢幱诓煌合档某蓡T，聯(lián)系稀疏，社會關(guān)系強(qiáng)度較低。各院系之間的聯(lián)系又需要社會關(guān)系度高的人員在其中進(jìn)行連接，進(jìn)而達(dá)到消息轉(zhuǎn)發(fā)的目的。

圖3所示為某高校的院系間領(lǐng)導(dǎo)與學(xué)生進(jìn)行消息轉(zhuǎn)發(fā)的示意圖，源節(jié)點(diǎn)S與目標(biāo)節(jié)點(diǎn)所在的社區(qū)節(jié)點(diǎn)D通信時(shí)，在t1時(shí)刻，由圖中可看出兩個(gè)節(jié)點(diǎn)進(jìn)行間接通信，此時(shí)需要在源節(jié)點(diǎn)所在的社區(qū)內(nèi)找出比當(dāng)前節(jié)點(diǎn)活躍度高的節(jié)點(diǎn)，即節(jié)點(diǎn)A。在t2時(shí)刻，轉(zhuǎn)發(fā)節(jié)點(diǎn)A向目標(biāo)節(jié)點(diǎn)所在的區(qū)域范圍移動，此時(shí)與E節(jié)點(diǎn)相遇并完成消息的轉(zhuǎn)發(fā)，到達(dá)t3時(shí)刻，將消息轉(zhuǎn)發(fā)給目標(biāo)節(jié)點(diǎn)D。該方法在消息平均時(shí)延得到進(jìn)一步改善，使得消息傳輸率提高。

圖3 消息轉(zhuǎn)發(fā)示意圖

2 社區(qū)劃分及轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇算法

2.1 社區(qū)劃分策略

由于機(jī)會社會網(wǎng)絡(luò)中的節(jié)點(diǎn)移動具有隨機(jī)性，將網(wǎng)絡(luò)劃分為不同的社區(qū)，分別在社區(qū)內(nèi)和社區(qū)間完成消息的轉(zhuǎn)發(fā)過程。同一社區(qū)的節(jié)點(diǎn)聯(lián)系密切，相遇次數(shù)較高；不同社區(qū)間的節(jié)點(diǎn)因?yàn)檫M(jìn)行消息的轉(zhuǎn)發(fā)時(shí)相遇次數(shù)較少，相遇概率也隨之降低。

定義3：(相遇頻率)指節(jié)點(diǎn)i和節(jié)點(diǎn)j的相遇總次數(shù)與節(jié)點(diǎn)j從初始狀態(tài)到t時(shí)間段內(nèi)與其他節(jié)點(diǎn)相遇的總次數(shù)比值，即

(1)

其中Mi,j(t)表示網(wǎng)絡(luò)中節(jié)點(diǎn)i與節(jié)點(diǎn)j在t時(shí)間段內(nèi)進(jìn)行消息轉(zhuǎn)發(fā)時(shí)相遇的總次數(shù)，Mj(t)表示節(jié)點(diǎn)i和節(jié)點(diǎn)j從起初到t時(shí)間段內(nèi)與其他節(jié)點(diǎn)相遇的總次數(shù)。

定義4：(社交權(quán)值)若兩個(gè)節(jié)點(diǎn)i和節(jié)點(diǎn)j相互聯(lián)系,其中節(jié)點(diǎn)與節(jié)點(diǎn)之間熟悉強(qiáng)度的取值范圍為[0，1],數(shù)值越大說明個(gè)體之間越熟悉，社交強(qiáng)度越高。

根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)具有的社會關(guān)系特征，按照該特征將節(jié)點(diǎn)劃分為不同的社區(qū)。其中節(jié)點(diǎn)表示攜帶移動設(shè)備的個(gè)體，節(jié)點(diǎn)之間存在的邊表示移動設(shè)備攜帶者之間的社會關(guān)系，邊所在的權(quán)值表示移動設(shè)備攜帶者之間的社會關(guān)系強(qiáng)度?，F(xiàn)將網(wǎng)絡(luò)中的節(jié)點(diǎn)按照上述方法進(jìn)行劃分，結(jié)果如圖4所示。

圖4 社區(qū)劃分的結(jié)果

2.1.1 貝葉斯概率樹 在許多消息轉(zhuǎn)發(fā)方法中使用單副本機(jī)制，當(dāng)攜帶節(jié)點(diǎn)和節(jié)點(diǎn)相遇時(shí)直接進(jìn)行消息的轉(zhuǎn)發(fā)或接收。在這種情況下，未考慮到轉(zhuǎn)發(fā)過程中更好的相遇機(jī)會。為了解決上述問題，本文提出一種基于貝葉斯概率樹轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇(Bayesian Probability Tree-Based Forwarding Node Selection,BFANS)方法。該方法結(jié)合源節(jié)點(diǎn)到相遇節(jié)點(diǎn)間的概率及節(jié)點(diǎn)間的貝葉斯概率去選擇下一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)。此外，攜帶節(jié)點(diǎn)作為樹的根節(jié)點(diǎn)，攜帶節(jié)點(diǎn)所遇到的節(jié)點(diǎn)作為樹的二級和三級節(jié)點(diǎn)。滿足這些節(jié)點(diǎn)的貝葉斯概率值位于兩個(gè)節(jié)點(diǎn)所在的邊，并且樹節(jié)點(diǎn)上的內(nèi)容表示消息由每個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)成功交付的概率。

本文主要針對某個(gè)網(wǎng)絡(luò)中含有i,a,b,c,和d節(jié)點(diǎn)，如下圖5(a)所示。節(jié)點(diǎn)i將產(chǎn)生的消息存儲后并轉(zhuǎn)發(fā)給目標(biāo)節(jié)點(diǎn)j，在某一時(shí)刻t0遇見了節(jié)點(diǎn)a，如果僅僅依賴于傳輸消息給攜帶節(jié)點(diǎn)和節(jié)點(diǎn)相遇的概率做出決定，發(fā)送給節(jié)點(diǎn)a后不會考慮所遇到的下一個(gè)機(jī)會。是否將消息發(fā)送給下一個(gè)節(jié)點(diǎn)a根據(jù)BFANS算法決定，如下圖5(b)所示。在此情況下，將根節(jié)點(diǎn)的發(fā)送概率與滿足節(jié)點(diǎn)的貝葉斯概率的值乘積和節(jié)點(diǎn)相遇的概率值進(jìn)行比較。如果節(jié)點(diǎn)i在遇到節(jié)點(diǎn)a之后再遇到節(jié)點(diǎn)b的概率乘以b節(jié)點(diǎn)將消息傳遞到目標(biāo)節(jié)點(diǎn)j概率高于由節(jié)點(diǎn)i到a的傳輸概率，節(jié)點(diǎn)i存儲消息后遇到節(jié)點(diǎn)a后并希望遇見節(jié)點(diǎn)b，重復(fù)上述步驟，直到與目標(biāo)節(jié)點(diǎn)j相遇并轉(zhuǎn)發(fā)。

圖5 貝葉斯概率樹的產(chǎn)生過程

2.1.2 相遇概率估計(jì) 利用經(jīng)典的算法Prophet來計(jì)算每個(gè)節(jié)點(diǎn)發(fā)送到目標(biāo)節(jié)點(diǎn)的概率，其中P(i,j)是節(jié)點(diǎn)i發(fā)送消息到節(jié)點(diǎn)j的發(fā)送概率，Pinit∈[0,1]為初始化常數(shù)[2]。

P(i,j)=P(i,j)old+(1-P(i,j)old)×Pinit

(2)

其中Pinit為節(jié)點(diǎn)i發(fā)送消息給節(jié)點(diǎn)j首次相遇概率。

如果節(jié)點(diǎn)i發(fā)送消息到節(jié)點(diǎn)j在某段時(shí)間內(nèi)不存在相遇情況，則傳輸概率將會降低。如式(3)所示。

P(i,j)=P(i,j)old×λω

(3)

其中λ是一個(gè)初始化常數(shù),ω是一個(gè)時(shí)間單元個(gè)數(shù)，ω受社區(qū)內(nèi)的時(shí)間間隔影響。

通過公式(4)計(jì)算節(jié)點(diǎn)與節(jié)點(diǎn)之間的貝葉斯概率。

(4)

2.2 BFANS消息傳輸過程

由于本文按照節(jié)點(diǎn)的社交權(quán)值及相遇概率值劃分社區(qū)，源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)想要進(jìn)行消息傳輸，就需要利用社區(qū)內(nèi)社交權(quán)值高的節(jié)點(diǎn)來輔助消息的傳輸。而在社區(qū)間的消息傳輸，利用BFANS將源節(jié)點(diǎn)作為根節(jié)點(diǎn)，其次將相遇的節(jié)點(diǎn)作為二級根節(jié)點(diǎn)，選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)需要考慮相遇概率和貝葉斯概率，直到將消息轉(zhuǎn)發(fā)給目標(biāo)節(jié)點(diǎn)為止。

2.2.1 社區(qū)內(nèi)消息傳輸 在社區(qū)內(nèi)的消息傳輸主要是根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的相遇概率值大小來判定，并且利用相遇的概率值構(gòu)建貝葉斯概率樹，在該樹中選擇比此刻攜帶節(jié)點(diǎn)相遇概率值大的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。在轉(zhuǎn)發(fā)過程中，對于轉(zhuǎn)發(fā)的消息會生成相應(yīng)的副本，按照“先進(jìn)先出”的原則進(jìn)行消息的存儲管理，直到遇見目標(biāo)節(jié)點(diǎn)為止。從節(jié)約能量的角度來說，選擇概率值高的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)這種方式，提高了消息傳輸效率。社區(qū)內(nèi)消息轉(zhuǎn)發(fā)方法如算法1所示。

2.2.2 社區(qū)間消息傳輸策略 節(jié)點(diǎn)在同一個(gè)社區(qū)內(nèi)緊密相連，相遇機(jī)會較多，消息傳輸效率也得到進(jìn)一步提高；而社區(qū)間消息傳輸?shù)姆椒ㄊ紫仁菍⒃垂?jié)點(diǎn)所攜帶的消息傳輸?shù)侥繕?biāo)節(jié)點(diǎn)所在的社區(qū)內(nèi)，再根據(jù)社區(qū)內(nèi)的節(jié)點(diǎn)權(quán)值去尋找合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)，社區(qū)之間的消息傳輸目的是根據(jù)貝葉斯概率樹選擇最佳轉(zhuǎn)發(fā)路徑。節(jié)點(diǎn)之間的移動按照各自的興趣愛好漫游在各個(gè)社區(qū)之間，使得社區(qū)之間存在連通性。對于存在單個(gè)節(jié)點(diǎn)時(shí)，只能訪問節(jié)點(diǎn)所在的社區(qū)，因此節(jié)點(diǎn)只提供節(jié)點(diǎn)所在社區(qū)到目標(biāo)社區(qū)的連通路徑。節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)社區(qū)需要通過中間節(jié)點(diǎn)的協(xié)助，大量的節(jié)點(diǎn)在社區(qū)之間移動可能存在許多條連通路徑，找出其中最佳的路徑可以優(yōu)化社區(qū)間的消息傳輸。

在本文中，選擇節(jié)點(diǎn)相遇概率高的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，由于節(jié)點(diǎn)在漫游社區(qū)之間概率具有傳遞性，因此選取一條社交權(quán)值最高的路徑。假設(shè)源節(jié)點(diǎn)S和目標(biāo)節(jié)點(diǎn)D進(jìn)行消息的轉(zhuǎn)發(fā)時(shí)，詳細(xì)過程如算法2所示。

算法1:社區(qū)內(nèi)消息傳輸算法Input:Message m,encountering node viOutput:Node vi encounters va(a=1,2,3…)When va is not the destination node vjthen Calculate Piaa=1,2,3…)according Eq.(4) When Pia==max(Pia(a=1,2,3…)) Send m to the encounter node vaIf vi is the destination node vj Send m to the destination vj算法2:社區(qū)間消息傳輸算法Input:Message m,encountering node vi,forwarding node vcOutput:If vi and vj both in a community use 社區(qū)內(nèi)傳輸算法When vi and vj are not in a community Send m to the most active community(vi?vj)If vj and vc are in a community use 社區(qū)內(nèi)傳輸算法 end ifend if

2.3 算法分析

針對上述模型，通過貝葉斯概率及相遇概率算法描述，并對算法進(jìn)行相關(guān)分析。算法中將處于同一個(gè)社區(qū)內(nèi)不同節(jié)點(diǎn)屬性進(jìn)行劃分，并選擇源節(jié)點(diǎn)作為根節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)相遇的概率構(gòu)建貝葉斯概率樹，并將消息存儲在節(jié)點(diǎn)緩存區(qū)，消息轉(zhuǎn)發(fā)時(shí)需要從節(jié)點(diǎn)緩存區(qū)找到，并轉(zhuǎn)發(fā)給相遇的節(jié)點(diǎn)。算法通過一次深度遍歷即可選擇出最佳路徑。時(shí)間復(fù)雜度為O(n2)。

3 仿真實(shí)驗(yàn)和結(jié)果分析

3.1 模擬環(huán)境設(shè)置

本文提出的BFANS算法在ONE[6]仿真平臺上進(jìn)行實(shí)驗(yàn)，與典型的消息轉(zhuǎn)發(fā)算法Epidemic，Prophet兩種進(jìn)行實(shí)驗(yàn)對比[2]。參數(shù)設(shè)置如表1所示：

3.2 仿真結(jié)果分析

將本文算法與傳統(tǒng)的Epidemic、Prophet算法在消息投遞成功率、平均時(shí)延以及路由開銷比率進(jìn)行比較。下面分別介紹三個(gè)指標(biāo)的定義[2]。

1)消息投遞成功率 消息投遞成功率是指成功到達(dá)目標(biāo)節(jié)點(diǎn)的消息總數(shù)占網(wǎng)絡(luò)中源節(jié)點(diǎn)發(fā)送消息的總數(shù)比例，計(jì)算公式為：

Dratio=R/S

(5)

該公式中R代表成功到達(dá)目標(biāo)節(jié)點(diǎn)發(fā)送的消息總個(gè)數(shù)，S代表源節(jié)點(diǎn)已經(jīng)發(fā)送到目標(biāo)節(jié)點(diǎn)的消息個(gè)數(shù)[6]。

2)平均時(shí)延 平均時(shí)延為節(jié)點(diǎn)發(fā)送的消息的總時(shí)間占成功到達(dá)目標(biāo)節(jié)點(diǎn)總個(gè)數(shù)之比，計(jì)算公式為：

(6)

其中Tι表示第i個(gè)節(jié)點(diǎn)在時(shí)間t內(nèi)發(fā)送的消息到達(dá)目標(biāo)節(jié)點(diǎn)的消息傳輸時(shí)延，R為成功到達(dá)目標(biāo)節(jié)點(diǎn)的總數(shù)。

3)路由開銷比率 表示在進(jìn)行實(shí)驗(yàn)情況下，節(jié)點(diǎn)未能成功到達(dá)目的地消息總數(shù)占成功到達(dá)目的地的消息總數(shù)比值，計(jì)算公式為：

(7)

表1 主要參數(shù)設(shè)置

3.2.1 緩存空間對傳輸策略的影響分析 在機(jī)會社會網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動速度、方向都具有隨機(jī)性，而節(jié)點(diǎn)的緩存大小也是有限的。本小節(jié)主要針對節(jié)點(diǎn)緩存空間大小，對提出的BFANS方法及先前的兩種算法在消息成功投遞率方面作出對比。

從圖6中可看出，三種算法在不同緩存空間下有著明顯的增長趨勢。當(dāng)緩存空間達(dá)到20MB時(shí)，在消息成功投遞率方面呈下降的趨勢，原因在于增大節(jié)點(diǎn)緩存空間及消息緩存空間有限導(dǎo)致丟棄的數(shù)量增加。BFANS算法之所以會優(yōu)于其他兩種路由算法，是因?yàn)橄啾扔趥鹘y(tǒng)的Prophet，該算法在社區(qū)內(nèi)部選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)采用了貝葉斯概率思想計(jì)算相遇概率值，能夠精確的選擇最佳的轉(zhuǎn)發(fā)節(jié)點(diǎn)。

圖6 不同緩存空間下消息投遞成功率的比較Fig.6 Comparison of delivery rates in different buffersizes

圖7 不同緩存空間下消息平均時(shí)延的比較
Fig.7 Comparison of the average latency in different buffersize

從圖7結(jié)果顯示可知，在平均時(shí)延方面的結(jié)果與消息成功投遞率相似。平均時(shí)延越長，表明路徑的選擇優(yōu)化能力越弱。因此，轉(zhuǎn)發(fā)節(jié)點(diǎn)的正確選擇能夠減少消息的平均時(shí)延。隨著節(jié)點(diǎn)自身的緩存空間不斷增加，Prophet算法的傳輸平均時(shí)延與BFANS傳輸平均時(shí)延相接近。

圖8 不同緩存空間下路由開銷比率的比較Fig.8 Comparison of overhead ratio in different buffersizes

由圖8可以看出，本文提出的BFANS算法低于其他兩種算法在路由開銷方面。Epidemic算法在路由開銷方面比其他兩種算法開銷率要高，這是因?yàn)槠渌麅煞N算法在起初的時(shí)候控制消息副本的數(shù)量，而在消息副本數(shù)量方面Epidemic算法未得到限制，在消息轉(zhuǎn)發(fā)的過程同時(shí)會產(chǎn)生冗余，因此導(dǎo)致開銷率較高。

由以上結(jié)果可看出，當(dāng)節(jié)點(diǎn)的緩存空間變化時(shí)，可用于作為轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)量也隨之增加，節(jié)點(diǎn)轉(zhuǎn)發(fā)的概率也增加。本文提出的BFANS方法與傳統(tǒng)的Prophet算法相結(jié)合，在此基礎(chǔ)上加以修改，提高了消息的投遞率，而由于社區(qū)間可用于轉(zhuǎn)發(fā)的節(jié)點(diǎn)選擇不恰當(dāng)，導(dǎo)致了消息在轉(zhuǎn)發(fā)過程中傳輸延遲高，并造成了網(wǎng)絡(luò)負(fù)載。文中所提出的BFANS消息轉(zhuǎn)發(fā)方法主要是對節(jié)點(diǎn)的社會屬性進(jìn)行社區(qū)的劃分，并且根據(jù)節(jié)點(diǎn)的移動規(guī)律及節(jié)點(diǎn)的相遇概率，完成轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇過程。

3.2.2 節(jié)點(diǎn)數(shù)量對傳輸策略影響分析 從以上結(jié)果看出，網(wǎng)絡(luò)中的節(jié)點(diǎn)移動范圍已知及節(jié)點(diǎn)緩存空間大小確定的情況下，節(jié)點(diǎn)之間相遇的總次數(shù)和網(wǎng)絡(luò)中存在的節(jié)點(diǎn)總數(shù)有關(guān)。本部分主要針對網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的變化進(jìn)行實(shí)驗(yàn)，分別從消息在轉(zhuǎn)發(fā)過程中的消息成功投遞率、發(fā)送消息平均時(shí)延及網(wǎng)絡(luò)中路由開銷比率3個(gè)方面。

Epidemic、Prophet、BFANS三種算法在不同節(jié)點(diǎn)個(gè)數(shù)下的消息成功率如圖9所示，從圖中可明顯看出，消息成功投遞率會受到節(jié)點(diǎn)數(shù)量的影響，節(jié)點(diǎn)數(shù)量達(dá)到一定個(gè)數(shù)，呈現(xiàn)出下降趨勢。因?yàn)楣?jié)點(diǎn)數(shù)量比較多，在消息的傳輸過程中，可用于轉(zhuǎn)發(fā)的次數(shù)也多，從而導(dǎo)致投遞率下降。隨著節(jié)點(diǎn)數(shù)量的增加，本文提出的方法在消息成功投遞率方面優(yōu)于另外兩種方法。

圖9 不同節(jié)點(diǎn)個(gè)數(shù)下消息投遞成功率的比較Fig.9 Comparison of delivery ratio in different node numbers

圖10 不同節(jié)點(diǎn)個(gè)數(shù)下消息平均時(shí)延的比較
Fig.10 Comparison of average latency in different node numbers

圖10顯示了在節(jié)點(diǎn)個(gè)數(shù)不同的情況下對消息傳輸平均時(shí)延的影響，由圖可以看出Epidemic、Prophet及BFANS三種算法的消息傳輸時(shí)延與消息成功投遞率結(jié)果接近。隨著節(jié)點(diǎn)個(gè)數(shù)增加，網(wǎng)絡(luò)資源緩存空間有限，節(jié)點(diǎn)的選擇方法沒有針對性，導(dǎo)致傳輸?shù)钠骄鶗r(shí)延也不斷增加。而本文所提出的算法相比于其他兩種算法平均時(shí)延會降低，因?yàn)楣?jié)點(diǎn)選擇的同時(shí)會考慮下一節(jié)點(diǎn)相遇的概率，并確定是否轉(zhuǎn)發(fā)消息給該節(jié)點(diǎn)。

圖11不同節(jié)點(diǎn)個(gè)數(shù)下路由開銷比率的比較Fig.11 Comparison of overhead ratio in different node numbers

圖11所示的是不同節(jié)點(diǎn)個(gè)數(shù)下路由的開銷比率，從圖中可以看出Epidemic算法的開銷隨著節(jié)點(diǎn)增加會上升，原因在于網(wǎng)絡(luò)中節(jié)點(diǎn)轉(zhuǎn)發(fā)消息時(shí)采用洪泛法的思想。本文提出的方法在開銷率方面低于其他兩種算法，由于在消息的傳輸過程中，利用所提出的方法對社區(qū)進(jìn)行劃分，并計(jì)算節(jié)點(diǎn)之間的相遇概率，根據(jù)歷史相遇概率值大小與貝葉斯概率值進(jìn)行比較，來確定轉(zhuǎn)發(fā)節(jié)點(diǎn)，直到將消息轉(zhuǎn)發(fā)給目標(biāo)節(jié)點(diǎn)結(jié)束轉(zhuǎn)發(fā)。

由上圖可知，在節(jié)點(diǎn)消息轉(zhuǎn)發(fā)時(shí)采用Prophet算法，盡管增加網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量可獲取所有節(jié)點(diǎn)歷史的相遇情況。但是，該算法在社區(qū)間傳輸時(shí)沒有考慮社區(qū)之間的連接情況，因此，消息被轉(zhuǎn)發(fā)次數(shù)較多，說明該節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)距離越長。隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量增加，節(jié)點(diǎn)之間相遇機(jī)會變多，利用BFANS能夠更好的利用機(jī)會社會網(wǎng)絡(luò)的消息傳輸特性，節(jié)點(diǎn)通過將消息存儲，并利用相遇機(jī)會轉(zhuǎn)發(fā)給其他節(jié)點(diǎn)，進(jìn)而以同樣方式尋找目標(biāo)節(jié)點(diǎn)，使得消息可靠并迅速傳輸。

4 結(jié)束語

針對現(xiàn)有的機(jī)會社會網(wǎng)絡(luò)轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇存在的不足及低效的消息傳輸方法，根據(jù)貝葉斯概率提出了一種轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇方法，該方法在Prophet算法基礎(chǔ)上進(jìn)行修改，根據(jù)節(jié)點(diǎn)特有的社會屬性，對網(wǎng)絡(luò)中存在的節(jié)點(diǎn)進(jìn)行社區(qū)劃分。在消息的傳輸過程中分別從社區(qū)內(nèi)和社區(qū)間進(jìn)行分析，合理的選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，利用節(jié)點(diǎn)的相遇概率及貝葉斯概率構(gòu)建樹，選擇符合條件的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，否則等待下一次相遇機(jī)會。實(shí)驗(yàn)結(jié)果表明，文中所提出的算法，相比于其他兩種方法能夠提高消息投遞成功率，降低消息平均延時(shí)以及路由開銷比率。

參考文獻(xiàn):

[1] ZHU K，LI W，F(xiàn)U X，et al.Data routing strategies in opportunistic mobile social networks:Taxonomy and open challenges [J].Computer Networks，2015，93(P1):183-198.

[2] DERAKHSHANFARD N，SABAEI M，RAHMANI A M.CPTR:conditional probability tree based routing in opportunistic networks [J].Wireless Networks，2015，23(1):1-8.

[3] RANGO F D，SOCIEVOLE A，Exploiting online and offline activity-based,metrics for opportunistic forwarding [J].Wireless Networks，2015,21(4):1163-1179.

[4] REN ZHI,PENG SHUANG,CHEN Hong,et al.Epidemic routing based on adaptive compression of vectors:efficient low-delay routing for opportunistic networks based on adaptive compression of vextors [J].International Journal of Communication Systems,2015,28(3):560-573.

[5] LINDGREN A，DORIA A，SCHELéN O.Probabilistic routing in intermittently connected networks [J].Acm Sigmobile Mobile Computing & Communications Review，2004，7(3):19-20.

[6] MA X，BAI X.A community-based routing algorithm for opportunistic networks [C]//Fifth International Conference on Ubiquitous and Future Networks.IEEE，2013:701-706.

[7] LEE J，KIM S K，YOON J H，et al.Snapshot:a forwarding strategy based on analyzing network topology in opportunistic networks [J].Wireless Networks，2015，21(6):2055-2068.

[8] RAVAEI B，SABAEI M，Pedram H，et al.Community-aware single-copy content forwarding in Mobile Social Network [J].Wireless Networks，2017(7):1-17.

[9] VENDRAMIN A C K，MUNARETTO A，DELGADO M R，et al.A social-aware routing protocol for opportunistic networks [J].Expert Systems with Applications，2016(54):351-363.

[10] 熊永平,孫利民,牛建偉,等.機(jī)會網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，2009(1)：124-137.