一種基于興趣挖掘的機(jī)會網(wǎng)絡(luò)內(nèi)容分發(fā)策略

孫立奮, 潘達(dá)儒

(華南師范大學(xué)物理與電信工程學(xué)院， 廣州 510006)

一種基于興趣挖掘的機(jī)會網(wǎng)絡(luò)內(nèi)容分發(fā)策略

孫立奮, 潘達(dá)儒*

(華南師范大學(xué)物理與電信工程學(xué)院， 廣州 510006)

提出了一種新的基于興趣挖掘的機(jī)會網(wǎng)絡(luò)內(nèi)容分發(fā)策略(Interest Mining Based Scheme,IMBS),通過貝葉斯理論分析節(jié)點(diǎn)的興趣以及節(jié)點(diǎn)基于興趣的相遇頻率,挖掘移動節(jié)點(diǎn)隨機(jī)運(yùn)動背后所蘊(yùn)含的人類社交特征和情感特征. 此外,IMBS采用發(fā)布/訂閱機(jī)制,收集節(jié)點(diǎn)的訂閱信息,以獲取消息在整個網(wǎng)絡(luò)中的需求量. 在轉(zhuǎn)發(fā)消息的時候,IMBS把消息的需求總量和節(jié)點(diǎn)的情感特征以及社交特征結(jié)合起來選擇下一跳節(jié)點(diǎn). 仿真實(shí)驗(yàn)及算法復(fù)雜度分析表明,在不提高算法復(fù)雜度的情況下，IMBS可顯著減少消息的傳輸延時和網(wǎng)絡(luò)開銷,并提高消息傳輸?shù)某晒β?

機(jī)會網(wǎng)絡(luò)； 內(nèi)容分發(fā)； 興趣挖掘； 貝葉斯理論； 訂閱/發(fā)布機(jī)制

Keywords： opportunistic networks; content dissemination; interests mining; Bayesian theory; publish/subscribe

隨著大數(shù)據(jù)時代的到來,無線資源緊缺的問題日益顯著,機(jī)會網(wǎng)絡(luò)下的內(nèi)容分發(fā)備受關(guān)注. 機(jī)會網(wǎng)絡(luò)不要求源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間存在著完整路徑,通過節(jié)點(diǎn)移動帶來的相遇機(jī)會實(shí)現(xiàn)網(wǎng)絡(luò)通信[1-5]. 在這種動態(tài)拓?fù)涞木W(wǎng)絡(luò)中，如何高效轉(zhuǎn)發(fā)消息是亟待解決的問題. 針對該問題,相關(guān)的研究主要基于節(jié)點(diǎn)間的相遇頻率和節(jié)點(diǎn)的興趣.

基于節(jié)點(diǎn)間相遇頻率的研究已經(jīng)比較成熟,常見的有經(jīng)典路由算法[6-9]以及基于社區(qū)理論的算法[10-13]. 例如,Epidemic算法[6]利用節(jié)點(diǎn)的相遇將消息泛洪,SprayAndWait算法[7]選取前n個相遇的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，控制消息的副本數(shù),Prophet算法[8]利用節(jié)點(diǎn)間的相遇概率轉(zhuǎn)發(fā)消息；Maxprop[9]算法也是基于相遇概率.

基于節(jié)點(diǎn)興趣的研究主要根據(jù)節(jié)點(diǎn)的興趣推送消息[14-15]，如：PrefCast算法基于節(jié)點(diǎn)的興趣轉(zhuǎn)發(fā)消息,以便滿足更多節(jié)點(diǎn)的興趣需求[14].

為了吸取這2類算法的優(yōu)點(diǎn),學(xué)者們試圖結(jié)合節(jié)點(diǎn)的相遇頻率和興趣選取下一跳節(jié)點(diǎn)[16-17]. 其基本思路是：把節(jié)點(diǎn)分成興趣組和本地組，在轉(zhuǎn)發(fā)消息的時候,優(yōu)先選取和目的節(jié)點(diǎn)存在共同興趣和社區(qū)的節(jié)點(diǎn)作為消息的攜帶者. 然而，即便是同屬于一個社區(qū)又有共同興趣愛好,這些節(jié)點(diǎn)也有概率處于該社區(qū)不同的地方,從而導(dǎo)致消息無法傳遞到目的節(jié)點(diǎn). 所有的這些研究方法,僅僅是利用節(jié)點(diǎn)興趣或者節(jié)點(diǎn)所處的地理社區(qū),并沒有根據(jù)這些興趣以及地理社區(qū)深入挖掘其中所蘊(yùn)含的人類活動特征和情感特征，難以有效分發(fā)內(nèi)容.

基于此，本文提出了一種新的基于興趣挖掘的機(jī)會網(wǎng)絡(luò)內(nèi)容分發(fā)策略(Interest Mining Based Scheme,IMBS)，充分考慮了節(jié)點(diǎn)興趣、節(jié)點(diǎn)活動以及消息需求量等因素,通過貝葉斯理論對節(jié)點(diǎn)的活動以及節(jié)點(diǎn)的興趣進(jìn)行分析,挖掘節(jié)點(diǎn)活動的人類社交特征和情感特，并以此選擇出一個合適的節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)；通過仿真實(shí)驗(yàn)比較IMBS與Epidemic、SprayAndWait、Prophet、Maxprop路由算法在網(wǎng)絡(luò)延遲、網(wǎng)絡(luò)消耗以及消息傳輸成功率等方面的性能,并分析這些算法的復(fù)雜度，從而驗(yàn)證了IMBS的有效性.

1 內(nèi)容分發(fā)策略的設(shè)計(jì)與實(shí)現(xiàn)

在介紹IMBS策略之前,先給出IMBS所使用的新概念、內(nèi)容分發(fā)網(wǎng)絡(luò)模型、相關(guān)假設(shè)及標(biāo)注和相關(guān)計(jì)算.

1.1 相關(guān)概念的定義

(1)朋友圈：存在共同興趣的兩節(jié)點(diǎn)相遇時,節(jié)點(diǎn)此時所處的活動圈子稱作朋友圈,用F表示. 一般而言，朋友間最大的特點(diǎn)就是存在共同興趣，本文以共同興趣這個特征表示朋友關(guān)系. 此外，本文研究的是節(jié)點(diǎn)活動的社交圈子,則相遇的朋友才有研究價值.

(2)熟人圈：不存在共同興趣的兩節(jié)點(diǎn)經(jīng)常相遇時,節(jié)點(diǎn)此時所處的活動圈子稱作熟人圈,用A表示. 一般而言，不管是否存在共同興趣,熟人間經(jīng)常會相遇. 因此本文把經(jīng)常相遇抽取為熟人之間最大的特征. 同時為了與朋友圈區(qū)分,本文假設(shè)熟人之間不存在共同興趣.

(3)陌生圈：不存在共同興趣的兩節(jié)點(diǎn)偶然相遇時,節(jié)點(diǎn)此時所處的活動圈子稱作陌生圈,用S表示. 一般而言,偶然相遇是陌生人之間最大的特征.為了與朋友圈區(qū)分,本文假設(shè)所有的陌生人都不存在共同興趣.

1.2 內(nèi)容分發(fā)網(wǎng)絡(luò)模型

基于大學(xué)校園構(gòu)建機(jī)會網(wǎng)絡(luò)內(nèi)容分發(fā)網(wǎng)絡(luò)模型，主要由網(wǎng)關(guān)、靜止節(jié)點(diǎn)及移動節(jié)點(diǎn)等3類節(jié)點(diǎn)組成(圖1). 移動節(jié)點(diǎn)代表網(wǎng)絡(luò)用戶,隨機(jī)分布在網(wǎng)絡(luò)的各個地方；靜止節(jié)點(diǎn)分布在各個社區(qū)中,如圖書館、教學(xué)樓等.

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

不同類型的節(jié)點(diǎn)負(fù)責(zé)網(wǎng)絡(luò)不同的任務(wù). 簡而言之,網(wǎng)關(guān)負(fù)責(zé)接受來自靜止節(jié)點(diǎn)的訂閱消息,并且根據(jù)訂閱產(chǎn)生相應(yīng)的消息,滿足用戶的需求. 靜止節(jié)點(diǎn)分散在整個網(wǎng)絡(luò)的各處：一是為了收集來自移動節(jié)點(diǎn)的訂閱消息,使得節(jié)點(diǎn)在不同的地方都可以提交自己的訂閱消息；二是為了更好地把消息轉(zhuǎn)發(fā)出去,滿足更多移動節(jié)點(diǎn)的需求. 移動節(jié)點(diǎn)則根據(jù)自己的興趣設(shè)置訂閱消息. 在移動的過程中,每當(dāng)遇到其他移動節(jié)點(diǎn),移動節(jié)點(diǎn)將會相互協(xié)助轉(zhuǎn)發(fā)訂閱信息,以便更快地向網(wǎng)絡(luò)提交或獲取訂閱消息.

1.3 假設(shè)及標(biāo)注

(1)X表示移動節(jié)點(diǎn)當(dāng)前的活動狀態(tài).

(2)假設(shè)節(jié)點(diǎn)在開始時處于3個圈子的概率相等,即1/3.

(3)每個節(jié)點(diǎn)都維護(hù)1個興趣列表和2個普通列表,分別用I、O1、O2來表示.I用來存儲當(dāng)前移動節(jié)點(diǎn)訂閱的消息，O1用來存儲首次遇到的其他節(jié)點(diǎn)的訂閱消息,O2用來存儲多次遇到的其他節(jié)點(diǎn)的訂閱消息.

(4)用MIi表示遇到其他移動節(jié)點(diǎn)的數(shù)量,且這些移動節(jié)點(diǎn)都對興趣列表I中第i個消息感興趣；同理,用MO1i表示遇到其他移動節(jié)點(diǎn)的數(shù)量,且這些移動節(jié)點(diǎn)都對普通列表O1中第i個消息感興趣；用MO2i表示遇到其他移動節(jié)點(diǎn)的數(shù)量,而且這些移動節(jié)點(diǎn)都對普通列表O2中第i個消息感興趣.

(5)用RIi表示興趣列表I中第i個消息在整個網(wǎng)絡(luò)中的需求量,用RO1i表示普通列表O1中第i個消息在整個網(wǎng)絡(luò)中的需求量,用RO2i表示普通列表O2中第i個消息在整個網(wǎng)絡(luò)中的需求量.

(6)每個節(jié)點(diǎn)維護(hù)一個消息列表,記為Mes,存儲其他節(jié)點(diǎn)所感興趣的消息,以幫助其他節(jié)點(diǎn)轉(zhuǎn)發(fā)消息.

(7)每一個消息都維護(hù)一個訂閱列表,記為P,用以記錄對該消息訂閱的移動節(jié)點(diǎn).

(8)對于一個連接,把連接發(fā)起者的興趣列表和2個普通列表分別記作SI、SO1和SO2；把連接接受者的興趣列表和2個普通列表分別記作RI、RO1和RO2.

1.4 概率計(jì)算

由于移動節(jié)點(diǎn)在網(wǎng)絡(luò)中移動,不同時刻可能處于不同的活動圈子. 而節(jié)點(diǎn)的3個活動圈子是相互獨(dú)立的,本文根據(jù)貝葉斯定理實(shí)時計(jì)算節(jié)點(diǎn)在各個活動圈子的概率,以此實(shí)時判斷節(jié)點(diǎn)所處的活動圈子,從而選取出適合轉(zhuǎn)發(fā)消息的節(jié)點(diǎn).

當(dāng)移動節(jié)點(diǎn)處于活動狀態(tài)X時,由貝葉斯定理可知,該移動節(jié)點(diǎn)處于朋友圈的概率為

(1)

該節(jié)點(diǎn)處于熟人圈的概率為

(2)

該節(jié)點(diǎn)處于陌生圈的概率為

(3)

由式(1)～(3)可知,狀態(tài)X出現(xiàn)的概率P(X)對于所有類別都一樣. 而本文所研究的活動圈子是單屬性的,由此可得

P(X|F)=P(X|A)=P(X|S)=1.

(4)

由式(1)～(4)可得,節(jié)點(diǎn)在狀態(tài)X的條件下處于各個圈子的概率的相對大小可以通過節(jié)點(diǎn)在各個圈子的概率來比較,即P(F)、P(A)和P(S). 下面,本文根據(jù)節(jié)點(diǎn)的歷史活動估算節(jié)點(diǎn)在各圈子的概率.

假設(shè)興趣列表I中存在NI個消息,普通列表O1中存在NO1個消息,O2中存在NO2個消息,則該節(jié)點(diǎn)在朋友圈中遇到的節(jié)點(diǎn)總數(shù)為

(5)

該移動節(jié)點(diǎn)在熟人圈中遇到的節(jié)點(diǎn)總數(shù)為

(6)

該移動節(jié)點(diǎn)在陌生圈中遇到的節(jié)點(diǎn)總數(shù)為

(7)

由式(5)～(7)可知,該移動節(jié)點(diǎn)在朋友圈中出現(xiàn)的概率為

(8)

該移動節(jié)點(diǎn)在熟人圈中出現(xiàn)的概率為

(9)

該移動節(jié)點(diǎn)在陌生圈中出現(xiàn)的概率為

(10)

因此,通過比較P(F)、P(A)及P(S)的大小就可判斷節(jié)點(diǎn)此時所處的社交圈子.

1.5 效用值函數(shù)

在實(shí)際的網(wǎng)絡(luò)中,一個移動節(jié)點(diǎn)可攜帶多個消息,一個消息可被多個節(jié)點(diǎn)所訂閱,而處于朋友圈、熟人圈和陌生圈的節(jié)點(diǎn)可能有多個. 為了選擇出一個更適合轉(zhuǎn)發(fā)消息的節(jié)點(diǎn),本文基于消息在整個網(wǎng)絡(luò)的需求以及節(jié)點(diǎn)所處的社交圈子提出效用函數(shù).

1.5.1 朋友圈效用函數(shù) 當(dāng)鄰居節(jié)點(diǎn)中存在多個節(jié)點(diǎn)對源節(jié)點(diǎn)所攜帶的消息感興趣,而且都處于朋友圈，則朋友圈效用函數(shù)G=RIi×P(F). 可知,當(dāng)節(jié)點(diǎn)在它的朋友圈的活躍度P(F)越大,消息的需求量RIi越大,則該節(jié)點(diǎn)可以更短的時間滿足更多節(jié)點(diǎn)的訂閱需求,因此朋友圈效用也就越高.

1.5.2 熟人圈效用函數(shù) 當(dāng)鄰居節(jié)點(diǎn)中不存在任何節(jié)點(diǎn)對中間節(jié)點(diǎn)所攜帶的消息感興趣,但是鄰居節(jié)點(diǎn)熟人圈中存在對中間節(jié)點(diǎn)所攜帶的消息感興趣的節(jié)點(diǎn),則熟人圈效用函數(shù)H=RO2i×P(A). 可知,當(dāng)節(jié)點(diǎn)在熟人圈中的活躍度P(A)越高,消息的網(wǎng)絡(luò)需求量RO2i越大,則該節(jié)點(diǎn)可以更短的時間滿足更多節(jié)點(diǎn)的需求,因此該節(jié)點(diǎn)所處的熟人圈的效用也越高.

1.5.3 陌生圈效用函數(shù) 當(dāng)接受者的朋友圈和熟人圈都不存在節(jié)點(diǎn)對中間節(jié)點(diǎn)所攜帶的消息感興趣,則陌生圈效用函數(shù)J=RO1i×P(S). 可知,當(dāng)節(jié)點(diǎn)在陌生圈中越活躍,即遇到的陌生節(jié)點(diǎn)越多,消息的需求量越大,則有更大的概率成功轉(zhuǎn)發(fā)消息，因此,陌生圈的效用也就越大.

1.6 內(nèi)容分發(fā)策略

本文所提出的IMBS是基于發(fā)布/訂閱機(jī)制的,包含消息的訂閱過程和分發(fā)過程.

1.6.1 訂閱過程 主要完成移動節(jié)點(diǎn)對消息的訂閱,實(shí)現(xiàn)過程如下：

if (發(fā)起連接)

if (發(fā)起者是移動節(jié)點(diǎn)) //移動節(jié)點(diǎn)

if (接受者是移動節(jié)點(diǎn))

fo r (SI中的每一個消息id)

i f (RI中包含id)

把接受者添加到該id的P列表；

MIi++；

els e if (RO2中包含id)

MO2i++；

else if (RO1中包含id)

MO2i++；

把id添加到RO2中；

RO1列表刪除該id；

else

MO1i++；

把id添加到Ro1中；

end if

end for

else if (接受者是靜止節(jié)點(diǎn))

向靜止節(jié)點(diǎn)訂閱消息.

end if

else if(發(fā)起者是靜止節(jié)點(diǎn))//靜止節(jié)點(diǎn)

if (收到移動節(jié)點(diǎn)新的訂閱信息)

向網(wǎng)關(guān)訂閱信息;

end if

else if(發(fā)起者是網(wǎng)關(guān))//網(wǎng)關(guān)

if (收到靜止節(jié)點(diǎn)新的訂閱信息)

根據(jù)訂閱產(chǎn)生新的消息；

刪除訂閱列表中相應(yīng)的id；

end if

end if

end if

節(jié)點(diǎn)在訂閱的過程中,算法也會收集一些網(wǎng)絡(luò)信息,比如消息的需求量、節(jié)點(diǎn)與節(jié)點(diǎn)之間的興趣以及相遇情況等,并利用這些信息動態(tài)識別移動節(jié)點(diǎn)的活動圈子,以便更好地為內(nèi)容分發(fā)做準(zhǔn)備.

1.6.2 分發(fā)過程 主要把各個消息分發(fā)到各個訂閱者,其實(shí)現(xiàn)過程如下：

for(每一個連接)//獲取有效的連接

for(發(fā)起者緩存列表每一個消息)

//緩存列表存儲別人訂閱的消息

if(接受者緩存列表Mes有該消息)

Continue；

else if(接受者接受列表有該消息)

//接受列表存儲自己訂閱的消息

Continue；

end if

把消息及連接添加到Sending列表；

//Sending 列表為待轉(zhuǎn)發(fā)列表

end for

end for

Sending列表按消息效用值降序排序；

for (Sending列表中的每一個值)

if (傳輸完畢)

消息傳輸成功;

else if (掉包)

存儲空間不足,需要緩存管理.

下一個待轉(zhuǎn)發(fā)的連接；

end if

if (緩存不足) //緩存管理

按消息效用值對Mes排序；

刪除Mes中效用值最低的消息;

end if

end for

在分發(fā)消息時,按照節(jié)點(diǎn)的興趣以及節(jié)點(diǎn)所處的社交圈子轉(zhuǎn)發(fā)消息. 簡而言之,如果鄰居節(jié)點(diǎn)都對消息感興趣,優(yōu)先把消息分發(fā)給處于朋友圈的節(jié)點(diǎn),然后是處于熟人圈的節(jié)點(diǎn),最后是處于陌生圈的節(jié)點(diǎn). 對于處于同一個圈子的節(jié)點(diǎn),將按照效用值的大小先后轉(zhuǎn)發(fā). 但如果不存在對消息感興趣的節(jié)點(diǎn),則只把消息轉(zhuǎn)發(fā)給處于熟人圈和陌生圈的節(jié)點(diǎn),因?yàn)樘幱谂笥讶Φ墓?jié)點(diǎn)很難遇到與自己不存在共同興趣的節(jié)點(diǎn),從而難以將消息轉(zhuǎn)發(fā)給訂閱者. 這樣就避免了無效消息的產(chǎn)生,減少網(wǎng)絡(luò)開銷. 為了進(jìn)一步管理緩存,本文限制每個消息的生命周期,并且假定緩存容量有限,只有效用值較大的消息才能緩存到消息列表.

2 仿真實(shí)驗(yàn)

在機(jī)會網(wǎng)絡(luò)仿真平臺ONE中對IMBS、Epidemic、SprayAndWait、Prophet和Maxprop路由算法進(jìn)行了仿真實(shí)驗(yàn)，并從傳輸延遲、網(wǎng)絡(luò)消耗量以及傳輸成功率等3個方面進(jìn)行比較. 仿真測試環(huán)境如下：網(wǎng)關(guān)1個,靜止節(jié)點(diǎn)8個,移動節(jié)點(diǎn)176個,移動節(jié)點(diǎn)運(yùn)動速度0.7～4 m/s,節(jié)點(diǎn)緩存容量大小為50 M.

2.1 傳輸延遲

圖2顯示了IMBS與其他路由算法在消息傳輸延遲方面的比較. 在整個仿真過程中,IMBS算法的傳輸延遲低且穩(wěn)定,比傳統(tǒng)最優(yōu)的MaxProp算法平均還要低71.9%. 這主要有兩方面的原因：(1)IMBS算法根據(jù)消息的網(wǎng)絡(luò)需求量、節(jié)點(diǎn)的興趣以及節(jié)點(diǎn)的活動圈子轉(zhuǎn)發(fā)消息,能夠迅速地把消息分發(fā)給訂閱者；(2)IMBS算法根據(jù)用戶的興趣分發(fā)消息,因此一個消息可以滿足多個用戶的需求,從而大大減少網(wǎng)絡(luò)延遲.

圖2 各種路由算法的平均延遲

2.2 網(wǎng)絡(luò)開銷

圖3顯示了IMBS算法與其他路由算法在網(wǎng)絡(luò)開銷方面的比較. 在整個仿真過程中,IMBS的網(wǎng)絡(luò)開銷與MaxProp算法的相似,但遠(yuǎn)低于Epidemic算法和Prophet算法. 這主要是因?yàn)镮MBS算法設(shè)定了每個消息的生命周期以及緩存容量,并根據(jù)節(jié)點(diǎn)的活動圈子避免無效的消息轉(zhuǎn)發(fā)以及及時清理緩存列表中的無效消息. 而SprayAndWait算法的網(wǎng)絡(luò)開銷最低,這主要是因?yàn)樵撍惴◤?qiáng)制控制消息副本的數(shù)量,防止消息泛洪.

圖3 各種路由算法的網(wǎng)絡(luò)開銷

2.3 傳輸成功率

如圖4所示,與MaxProp算法和Prophet算法相比,IMBS算法在仿真開始時消息轉(zhuǎn)發(fā)成功率波動比較大. 這主要有兩方面的原因:(1)移動節(jié)點(diǎn)在網(wǎng)絡(luò)中動態(tài)訂閱消息,消息訂閱不穩(wěn)定；(2)消息達(dá)到生命周期就會消失. 但是隨著時間的轉(zhuǎn)移,IMBS算法在傳輸成功率方面趨于穩(wěn)定,而且遠(yuǎn)遠(yuǎn)優(yōu)于Epidemic算法和SprayAndWait算法,并且接近MaxProp算法和Prophet算法.

圖4 各路由算法的傳輸成功率

3 算法復(fù)雜度分析

本文所設(shè)計(jì)的IMBS算法與其他4種經(jīng)典路由算法都是在ONE平臺上實(shí)現(xiàn)的,因此只討論路由算法方面的算法復(fù)雜度. IMBS算法主要分為信息收集的訂閱過程和轉(zhuǎn)發(fā)消息的分發(fā)過程. 因此，也將從這2個方面分析算法的時間復(fù)雜度和空間復(fù)雜度.

3.1 時間復(fù)雜度

在信息收集方面,IMBS算法、MaxProp算法及Prophet算法需要收集節(jié)點(diǎn)的歷史數(shù)據(jù)信息,而SprayAndWait算法和Epidemic算法不需要收集歷史數(shù)據(jù). 因此，SprayAndWait算法和Epidemic算法在信息收集方面的時間復(fù)雜度為Ο(1). 對于本文所提出的IMBS算法,如第1.6.1節(jié)訂閱過程的偽代碼,算法的時間復(fù)雜度主要由一個for循環(huán)和一個查詢語句決定,for循環(huán)是遍歷節(jié)點(diǎn)的興趣列表,由于IMBS算法限定移動節(jié)點(diǎn)每次最多可以訂閱的消息數(shù),因此該for循環(huán)的復(fù)雜度為Ο(1). 而查詢語句是Java內(nèi)置的List列表中的contain函數(shù),屬于線性查詢,最壞時間復(fù)雜度為Ο(n)，最好時間復(fù)雜度為Ο(1). 由于每個節(jié)點(diǎn)設(shè)置訂閱消息是隨機(jī)的，假設(shè)節(jié)點(diǎn)訂閱每個消息的概率相等,則該查詢的平均復(fù)雜度為Ο(n(n+1)/(2n))=Ο(n). 因此,IMBS算法訂閱過程在最壞的情況下,時間復(fù)雜度為Ο(n),平均復(fù)雜度為Ο(n)，最好的情況下是Ο(1). 通過分析MaxProp算法以及Prophet算法的源代碼可知,MaxProp算法以及Prophet算法的時間復(fù)雜度由一個for循環(huán)決定,遍歷整個列表,因此MaxProp算法以及Prophet算法在收集信息方面的時間復(fù)雜度在最好、最壞及平均的情況皆為Ο(n)(表1).

表1 各算法訂閱過程的時間復(fù)雜度Table 1 Time complexities of algorithms in subscription process

在分發(fā)過程,IMBS算法與MaxProp算法、Prophet算法相似,只是在對Sending列表的排序以及緩存管理策略有所不同. 在獲取待轉(zhuǎn)發(fā)連接中,涉及2個for循環(huán)以及一個線性查詢(分發(fā)過程第1、2、4行代碼),因此，時間復(fù)雜程度在最壞的情況下為Ο(n3)，最好的情況下為Ο(n2). 假設(shè)每次要查詢的消息出現(xiàn)的概率相等，則平均情況下也為Ο(n3). Sending列表的排序時間復(fù)雜度遠(yuǎn)低于Ο(n3)，緩存管理策略只需遍歷一次緩存列表即可. SprayAndWait算法和Epidemic算法的分發(fā)過程也類似. 通過分析這2種算法在消息分發(fā)部分的源代碼,雖然不存在對Sending列表的排序,但是發(fā)現(xiàn)其存在3個嵌套型for循環(huán)進(jìn)行遍歷,因此在最好、最壞及平均情況下，時間復(fù)雜度都為Ο(n3)(表2).

表2 各算法分發(fā)過程的時間復(fù)雜度Table 2 Time complexities of algorithms in publishing process

3.2 空間復(fù)雜度

空間復(fù)雜程度是對一個算法在運(yùn)行過程中占用存儲空間大小的量度，也是問題規(guī)模n的函數(shù),其中所占用的存儲空間包括固定空間與可變空間. 但是由于機(jī)會網(wǎng)絡(luò)路由算法研究的是消息的傳輸，需要緩存消息，可變部分遠(yuǎn)遠(yuǎn)大于固定部分，因此，本文主要分析可變部分，而可變部分表現(xiàn)在信息收集過程和消息緩存過程.

在信息收集過程，通過分析算法源代碼可知，SprayAndWait算法和Epidemic算法在信息收集過程沒有收集任何信息，不存在空間復(fù)雜程度問題. IMBS算法只需要遍歷有限的興趣列表，空間復(fù)雜程度為Ο(1).而MaxProp算法和Prophet算法不存在for循環(huán)，空間復(fù)雜程度為Ο(1).

在消息分發(fā)過程，IMBS算法與MaxProp算法、Prophet算法相似，空間復(fù)雜度主要由獲取待轉(zhuǎn)發(fā)連接過程和存儲消息過程決定. 在對Sending隊(duì)列進(jìn)行添加操作時經(jīng)歷了2個for循環(huán)，如分發(fā)過程中的第1、2、14行所示，因此空間復(fù)雜度為Ο(n2). 消息傳輸完畢需要存儲消息，如分發(fā)過程的第18、20行所示，這個存儲過程的空間復(fù)雜度為Ο(n). 而SprayAndWait算法與Epidemic算法的空間復(fù)雜程度主要由存儲過程決定，也是Ο(n). 在存儲過程中，由于存儲的是消息,占用空間資源量比較大,超過了Sending隊(duì)列的添加操作，故存儲過程決定了整個算法的存儲空間的消耗. 因此，各算法的緩存管理策略決定了該算法的空間資源開銷. 各算法在分發(fā)過程的空間復(fù)雜度見表3.

表3 各算法分發(fā)過程空間復(fù)雜度Table 3 Space complexities of algorithms in publishing process

4 結(jié)論

本文通過節(jié)點(diǎn)的興趣與節(jié)點(diǎn)運(yùn)動分析出節(jié)點(diǎn)的活動圈子,在看似毫無規(guī)律的運(yùn)動中找出移動節(jié)點(diǎn)的人類活動特征和情感特征,進(jìn)而為選擇一個合適的節(jié)點(diǎn)進(jìn)行內(nèi)容分發(fā)提供了一種方法. 仿真實(shí)驗(yàn)表明,與傳統(tǒng)路由算法相比,IMBS算法顯著降低了消息傳輸?shù)钠骄舆t,并且把網(wǎng)絡(luò)開銷和消息傳輸成功率控制在一定范圍內(nèi),具有一定的可行性和有效性.

[1] 潘達(dá)儒,麥立峰,齊小宇. 機(jī)會計(jì)算研究綜述[J]. 華南師范大學(xué)學(xué)報(自然科學(xué)版),2016,48(5):116-122.

PAN D R,MAI L F,QI X Y. Survey on opportunistic computing[J]. Journal of South China Normal University(Natural Science Edition),2016,48(5):116-122.

[2] PELUSI L,PASSARELLA A,CONTI M. Opportunistic networking:data forwarding in disconnected mobile ad hoc networks[J]. IEEE Communications Magazine,2006,44(11):134-141.

[3] WANG Y,JAIN S,MARTONOSI M,et al. Erasure-coding based routing for opportunistic networks[C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking. New York:ACM,2005:229-236.

[4] RAMANATHAN R,HANSEN R,BASU P,et al. Prioritized epidemic routing for opportunistic networks[C]//Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking. New York:ACM,2007:62-66.

[5] YOUNIS O,FAHMY S. HEED:a hybrid,energy-efficient,distributed clustering approach for ad hoc sensor networks[J]. IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[6] VAHDAT A,BECKER D. Epidemic routing for partially-connected ad hoc networks[D]. Durham:Duke University,2000.

[7] 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 on Delay-Tolerant Networking. New York:ACM,2005:252-259.

[8] LINDGREN A,DORIA A,SCHELéN O. Probabilistic routing in intermittently connected networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.

[9] BURGESS J,GALLAGHER B,JENSEN D,et al. MaxProp:routing for vehicle-based disruption-tolerant networks[C]// Proceedings of 25th IEEE International Conference on Computer Communications. Barcelona:IEEE,2006:1-11.

[10] XIAO M,WU J,HUANG L. Community-aware opportu-nistic routing in mobile social networks[J]. IEEE Transactions on Computers,2014,63(7):1682-1695.

[11] NIU J,ZHOU X,WANG K,et al. A data transmission scheme for community-based opportunistic networks[C]// Proceedings of the 5th International Conference on Wireless Communications,Networking and Mobile Computing. Beijing:IEEE,2009:1-5.

[12] LI F,ZHAO L,ZHANG C,et al. Routing with multi-level cross-community social groups in mobile opportunistic networks[J]. Personal and Ubiquitous Computing,2014,18(2):385-396.

[13] NIU J W,WU F F,HUO D,et al. Message publish/subscribe scheme based on opportunistic networks[C]// Proceedings of the 2010 Symposia and Workshops on Ubiquitous,Autonomic and Trusted Computing. Xi’an:IEEE,2010:180-184.

[14] LIN C J,CHEN C W,CHOU C F. Preference-aware content dissemination in opportunistic mobile social networks[C]∥Proceedings of the 31st Annual IEEE International Conference on Computer Communications. Orlando:IEEE,2012,131(5):1960-1968.

[15] GREIFENBERG J,KUTSCHER D. Efficient publish/subscribe-based multicast for opportunistic networking with self-organized resource utilization[C]// Proceedings of the 22nd International Conference on Advanced Information Networking and Applications-Workshops. Okinawa:IEEE,2008:1708-1714.

[16] PATEL J A,RIVIERE E,GUPTA I,et al. Rappel:exploiting interest and network locality to improve fairness in publish-subscribe systems [J]. Computer Networks,2009,53(13):2304-2320.

[17] JAHO E,STAVRAKAKIS I. Joint interest- and locality-aware content dissemination in social networks[C]//Proceedings of the Sixth International Conference on Wireless On-Demand Network Systems and Services. Snowbird:IEEE,2009:161-168.

An Opportunistic Network Content Distribution Strategy Based on Interest Mining

SUN Lifen, PAN Daru*

(School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China)

A new interest mining based scheme(IMBS) is proposed. In IMBS, the interest and meeting frequency are analyzed based on interest of mobile nodes according to Bayesian theory, to find out the human social and emotional characteristics behind the random movement of the mobile nodes. In addition, the publish/subscribe mechanism is adopted to collect the node’s subscription information, in order to obtain the total demand of messages in the whole networks. When forwarding a message, the total demand of messages with the emotional characteristics and the social characteristics of the nodes are combined to select the next-hop node. The results of simulation experiment and the analysis of complexities of algorithms show that IMBS can significantly reduce the message delivery delay and network overhead, and improve the delivery ratio of message transmission without increasing the complexity of the algorithm.

2017-01-22 《華南師范大學(xué)學(xué)報(自然科學(xué)版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學(xué)基金項(xiàng)目(61471175)；教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃項(xiàng)目(NCET-13-0805)

*通訊作者:潘達(dá)儒,教授,Email:pandr@scnu.edu.cn.

TP393

A

1000-5463(2017)05-0108-07

【中文責(zé)編：莊曉瓊 英文審校：肖菁】