石峻嶺 , 王興偉 , 黃 敏

1(東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院,遼寧 沈陽 110169)2(東北大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽 110819)

移動社交網(wǎng)絡(luò)(mobile social network,簡稱MSN)是一種利用移動用戶之間存在的社交關(guān)系進(jìn)行無線通信的系統(tǒng)[1].隨著大數(shù)據(jù)時代的到來,移動用戶對多媒體內(nèi)容(如視頻)的需求日益增加.為滿足移動用戶的內(nèi)容需求,配備高效的路由機(jī)制尤為重要.現(xiàn)有的MSN 路由機(jī)制[2-10]均基于已知消息的目的節(jié)點進(jìn)行交付,即假設(shè)已知內(nèi)容提供者地址.然而這種假設(shè)在實際中是不可行的,因為一旦內(nèi)容提供者地址發(fā)生變化,請求者將無法通過變化前的地址獲取內(nèi)容.因此,需要尋求一種能夠克服這種移動性的路由模式實現(xiàn)內(nèi)容查找.此外,盡管在MSN路由中,通過利用移動用戶的社交關(guān)系(如興趣相似程度)能夠使包的轉(zhuǎn)發(fā)更加準(zhǔn)確,并實現(xiàn)改善路由效率的目的,然而由于用戶的興趣等有效的社會信息難以準(zhǔn)確獲取[11],因此需要有效的方法實現(xiàn)用戶的社交信息挖掘.進(jìn)一步,在MSN 中,“存儲-攜帶-轉(zhuǎn)發(fā)”式的消息交付模式要求節(jié)點對消息進(jìn)行本地緩存.對于包含內(nèi)容數(shù)據(jù)的消息,現(xiàn)有的MSN 路由僅僅根據(jù)消息的跳數(shù)[12]、到達(dá)時間等指標(biāo)對消息進(jìn)行緩存,沒有提取消息中的內(nèi)容,也沒有對內(nèi)容單獨進(jìn)行緩存.然而,對內(nèi)容進(jìn)行有效的緩存,能夠更加快速地滿足用戶后續(xù)相同或者相似的內(nèi)容需求,從而不需要重新從內(nèi)容提供者處獲取內(nèi)容.因此,需要對現(xiàn)有的MSN 架構(gòu)進(jìn)行改善,以滿足用戶對內(nèi)容的需求.

信息中心網(wǎng)絡(luò)(information-centric networking,簡稱ICN)將面向主機(jī)的通信方式轉(zhuǎn)變?yōu)槊嫦騼?nèi)容的通信方式,關(guān)注內(nèi)容“是什么”,而不關(guān)心內(nèi)容“在哪里”[13].將ICN 的這種以內(nèi)容為中心的通信方式應(yīng)用于MSN 中,用戶僅需知道自己所需內(nèi)容的名字,而不需要知道內(nèi)容的地址,從而有助于解決MSN 中由于內(nèi)容提供者地址變化而導(dǎo)致的無法有效路由的問題.此外,在ICN 中,內(nèi)容以名字進(jìn)行命名,用戶的興趣請求使用的是內(nèi)容的名字,這些內(nèi)容名字體現(xiàn)了用戶對內(nèi)容的偏好.通過有效挖掘用戶對內(nèi)容的偏好,能夠計算節(jié)點的興趣,獲得節(jié)點之間興趣的相似程度,因而有助于解決MSN 中用戶間社交關(guān)系難以準(zhǔn)確獲取的問題.最后,ICN 關(guān)注節(jié)點的內(nèi)容緩存,支持節(jié)點對緩存內(nèi)容的優(yōu)化處理[14].當(dāng)緩存空間不足時,盡可能緩存后續(xù)可能被其他用戶以較高概率訪問的內(nèi)容,后續(xù)被訪問概率低的內(nèi)容不被緩存或被替換.因此,通過在MSN 的節(jié)點中引入內(nèi)容緩存機(jī)制,對內(nèi)容進(jìn)行有效管理,可以提高對用戶后續(xù)內(nèi)容訪問需求的滿足程度.基于上述考慮,本文基于ICN 架構(gòu),提出一種MSN 中的新型路由機(jī)制.

社區(qū)發(fā)現(xiàn)通常是一種能有效解決MSN 路由的社會學(xué)方法,它能夠使路由更高效、穩(wěn)定和具有可擴(kuò)展性[15].在基于社區(qū)的路由[5,8,16-18]中,包通過先發(fā)送到目標(biāo)社區(qū)、再發(fā)送給目標(biāo)節(jié)點的方式實現(xiàn)交付.與ICN 相同,本文使用兩種包來滿足用戶對內(nèi)容的訪問需求,即用于查找內(nèi)容的興趣包和用于返回內(nèi)容的數(shù)據(jù)包.為了實現(xiàn)兩種包不同的目標(biāo),本文根據(jù)不同的社交度量劃分了兩種社區(qū):一種是基于用戶興趣偏好劃分的興趣社區(qū),在路由興趣包時,將興趣包發(fā)送給內(nèi)容提供者的興趣社區(qū),再發(fā)送給內(nèi)容提供者;另一種是基于節(jié)點的相遇規(guī)律劃分的社交社區(qū),在路由數(shù)據(jù)包時,將數(shù)據(jù)包發(fā)送給內(nèi)容請求者的社交社區(qū),再交付至內(nèi)容請求者.

在MSN 中,基于社交關(guān)系的路由存在多副本和單副本兩種方式:多副本路由在將消息轉(zhuǎn)發(fā)給下一跳節(jié)點后,保存消息的副本并進(jìn)一步轉(zhuǎn)發(fā),因此交付率相對較高但轉(zhuǎn)發(fā)開銷巨大;單副本路由在將消息轉(zhuǎn)發(fā)給下一跳節(jié)點后,節(jié)點不存儲消息的副本,因此網(wǎng)絡(luò)開銷小,但是需要準(zhǔn)確的社交關(guān)系才能保證交付率.單副本路由容易陷入局部最優(yōu),即容易陷入“死胡同”(dead end)[16],因為節(jié)點總是將消息轉(zhuǎn)發(fā)給與目的節(jié)點社交關(guān)系更緊密(即社會地位更高)的節(jié)點,但有時聯(lián)系更緊密的節(jié)點由于突發(fā)事件而無法與目的節(jié)點及時相遇,因此造成消息不能繼續(xù)轉(zhuǎn)發(fā)而無法交付.本文提出一種消息轉(zhuǎn)發(fā)的回溯策略,如果節(jié)點持有消息超過預(yù)定時間,則不再將消息發(fā)送給社會地位更高的節(jié)點,而是把消息發(fā)送給社交地位較低的節(jié)點,以防止路由陷入“死胡同”.

本文的主要貢獻(xiàn)如下:基于ICN 架構(gòu)提出了一種MSN 中的路由機(jī)制,以滿足移動用戶對內(nèi)容的需求;針對興趣包和數(shù)據(jù)包,分別提出了社區(qū)發(fā)現(xiàn)方法,以高效地實現(xiàn)包交付;提出了一種路由轉(zhuǎn)發(fā)回溯策略,以解決路由陷入“死胡同”的問題;節(jié)點根據(jù)劃分的興趣社區(qū)和社交社區(qū)對內(nèi)容進(jìn)行有效緩存,以滿足后續(xù)用戶內(nèi)容請求.

本文第1 節(jié)介紹相關(guān)工作.第2 節(jié)是本文機(jī)制的系統(tǒng)框架.第3 節(jié)描述社區(qū)發(fā)現(xiàn)方法.第4 節(jié)介紹路由決策.第5 節(jié)是仿真與性能評價.第6 節(jié)給出結(jié)論.

1 相關(guān)工作

關(guān)于MSN 路由已經(jīng)有一些研究工作.文獻(xiàn)[3]提出了一種基于社交簇的路由機(jī)制,每個節(jié)點都選擇與之關(guān)系緊密的其他節(jié)點形成本地簇,將消息首先轉(zhuǎn)發(fā)給目的節(jié)點的簇成員節(jié)點,再由簇成員節(jié)點發(fā)送給目的節(jié)點.文獻(xiàn)[4]在MSN 中提出了一種截止期限敏感(dead line sensitive)的基于效用的路由模型,如果一個消息在截止期限前成功得到交付,則它的源節(jié)點將得到一個積極的收益;否則,源節(jié)點不會得到任何收益.文獻(xiàn)[5]提出了一種MSN 中基于社交關(guān)系的路由方法,引入社會能量來衡量節(jié)點的消息轉(zhuǎn)發(fā)能力,將消息轉(zhuǎn)發(fā)給社會能量強(qiáng)的節(jié)點.文獻(xiàn)[6]在MSN 中提出了一種基于參數(shù)最優(yōu)化的路由協(xié)議,在選擇中繼節(jié)點時,綜合考慮3 個社交度量,即LinkRank、相似度和接觸強(qiáng)度.3 個度量的權(quán)重由配對學(xué)習(xí)算法(pair-wise learning algorithm)推導(dǎo)得到.文獻(xiàn)[7]面向移動用戶提出了一種兩段式動態(tài)路由轉(zhuǎn)發(fā)算法,設(shè)計了基于節(jié)點社交活躍度的多副本傳播策略和基于節(jié)點物理接觸因子的單副本轉(zhuǎn)發(fā)策略.文獻(xiàn)[8]提出了一種社區(qū)感知的網(wǎng)絡(luò)模型,將MSN 轉(zhuǎn)變?yōu)閮H包含社區(qū)的網(wǎng)絡(luò),進(jìn)而給出了一種分布式最優(yōu)社區(qū)感知機(jī)會路由算法.文獻(xiàn)[9]指出,MSN 呈現(xiàn)出一種嵌套式的分層結(jié)構(gòu),少數(shù)活躍的節(jié)點構(gòu)成網(wǎng)絡(luò)的核心,而多數(shù)不活躍的節(jié)點構(gòu)成網(wǎng)絡(luò)的邊緣.提出了一種上傳-下載式的路由協(xié)議,消息通過迭代地轉(zhuǎn)發(fā)給更活躍的中繼節(jié)點被上傳至網(wǎng)絡(luò)核心,基于布魯姆過濾器,從網(wǎng)絡(luò)核心下載消息到目的節(jié)點.文獻(xiàn)[10]提出一種基于蟻群算法的MSN 路由機(jī)制,根據(jù)節(jié)點的傳輸路徑信息得到節(jié)點對之間的信息列表.設(shè)計信息素的更新方法,在轉(zhuǎn)發(fā)數(shù)據(jù)給其他節(jié)點時,提供有效的信息以選擇合適的中繼節(jié)點.與上述工作不同,本文基于ICN 架構(gòu)提出了一種MSN 中的路由機(jī)制,根據(jù)用戶請求中的內(nèi)容名字挖掘用戶之間關(guān)于興趣的社交度量進(jìn)行路由.

已經(jīng)有一些研究工作基于ICN 架構(gòu)設(shè)計了MSN 路由.文獻(xiàn)[17]根據(jù)移動節(jié)點的移動性,在每個社區(qū)中確定一個代理節(jié)點,負(fù)責(zé)接收和轉(zhuǎn)發(fā)用戶的興趣包.由于代理節(jié)點可能需要同時轉(zhuǎn)發(fā)多個興趣包,根據(jù)用戶興趣和請求數(shù)量設(shè)計需求度,以確定每個興趣包的優(yōu)先級.通過比較不同節(jié)點彼此相遇的可能,選擇轉(zhuǎn)發(fā)節(jié)點傳輸數(shù)據(jù)包.由于具有更高社會地位的節(jié)點在網(wǎng)絡(luò)中更受歡迎,文獻(xiàn)[18]令用戶將興趣包發(fā)送給具有更高社會地位的節(jié)點.如果不能夠在請求者的社區(qū)實現(xiàn)興趣包的內(nèi)容查找,它將被轉(zhuǎn)發(fā)給其他社區(qū).基于節(jié)點的相遇歷史,數(shù)據(jù)包轉(zhuǎn)發(fā)給更有可能與請求者相遇的節(jié)點.但是,文獻(xiàn)[17,18]的社區(qū)中存儲的為相遇頻繁的節(jié)點,在劃分社區(qū)時沒有考慮用戶對內(nèi)容的興趣.然而,有效挖掘用戶對內(nèi)容的偏好,能夠有助于為興趣包查找內(nèi)容.本文的社區(qū)發(fā)現(xiàn)方法不僅考慮了節(jié)點的相遇規(guī)律,同時考慮了用戶興趣的相似程度,能夠有效實現(xiàn)內(nèi)容查找,實現(xiàn)興趣包和數(shù)據(jù)包的交付.此外,文獻(xiàn)[17,18]沒有在路由數(shù)據(jù)包的過程中對節(jié)點緩存的內(nèi)容有效管理,因此對于后續(xù)節(jié)點相同或相似內(nèi)容請求,仍需要從原始的內(nèi)容提供者那里獲取.而本文設(shè)計了節(jié)點的內(nèi)容緩存機(jī)制,滿足后續(xù)到達(dá)的內(nèi)容請求.文獻(xiàn)[19]通過使用命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking,簡稱NDN)規(guī)則,提出了一種社交感知的NDN 架構(gòu),將具有高物理臨近度和內(nèi)容相似度的親密用戶定義為朋友圈,根據(jù)朋友圈相遇頻率構(gòu)建路由表,在朋友圈之間路由興趣包和數(shù)據(jù)包.雖然在形成朋友圈的過程中,文獻(xiàn)[19]同時考慮了相遇規(guī)律與用戶的興趣相似程度,但沒有考慮在節(jié)點中引入內(nèi)容緩存機(jī)制.此外,作為基于單副本轉(zhuǎn)發(fā)的路由,文獻(xiàn)[6-9]均存在消息轉(zhuǎn)發(fā)陷入“死胡同”的問題.本文路由機(jī)制為了避免消息轉(zhuǎn)發(fā)陷入“死胡同”,提出了一種回溯策略,可以將陷入“死胡同”的消息發(fā)送給具有較低社會地位的節(jié)點.

2 系統(tǒng)框架

2.1 系統(tǒng)模塊

如圖1 所示,本文提出的基于ICN 網(wǎng)絡(luò)架構(gòu)的社區(qū)感知型路由機(jī)制(ICN based community aware routing scheme,簡稱ICRS)主要包含兩個組件,分別是社區(qū)發(fā)現(xiàn)和路由決策.前者為基于用戶的興趣偏好劃分興趣社區(qū),同時基于節(jié)點的相遇規(guī)律劃分社交社區(qū);后者為負(fù)責(zé)轉(zhuǎn)發(fā)興趣包的興趣決策和數(shù)據(jù)包的數(shù)據(jù)決策.具體而言,在興趣決策中包含社區(qū)內(nèi)轉(zhuǎn)發(fā)和社區(qū)間轉(zhuǎn)發(fā);在數(shù)據(jù)決策中包含網(wǎng)絡(luò)內(nèi)緩存、社區(qū)內(nèi)轉(zhuǎn)發(fā)和社區(qū)間轉(zhuǎn)發(fā).

Fig.1 System framework圖1 系統(tǒng)架構(gòu)

2.2 工作流程

MSN 分為集中式、分布式和混合式這3 種網(wǎng)絡(luò)結(jié)構(gòu).在集中式MSN 中,節(jié)點通過基礎(chǔ)設(shè)施與Internet 相連;在分布式MSN 中,節(jié)點通過設(shè)備對設(shè)備(device to device)的通信模式進(jìn)行數(shù)據(jù)傳輸;而混合式是這兩種網(wǎng)絡(luò)結(jié)構(gòu)的結(jié)合.ICRS 采用混合式網(wǎng)絡(luò)結(jié)構(gòu),如圖2 所示.

Fig.2 Workflow and scenario圖2 工作場景與流程

當(dāng)節(jié)點在基站的信號覆蓋范圍內(nèi)時(圖中節(jié)點B和D),它們將自己的興趣信息(具體為用戶對于不同內(nèi)容分類的歷史請求次數(shù))和社交信息(具體為節(jié)點與其他節(jié)點的歷史相遇情況)通過基站和Internet 發(fā)送給負(fù)責(zé)社區(qū)劃分的服務(wù)器.服務(wù)器根據(jù)節(jié)點上傳的興趣信息和社交信息將節(jié)點劃分為興趣社區(qū)和社交社區(qū),通過基站下發(fā)給各個節(jié)點,因此,社區(qū)發(fā)現(xiàn)組件采用集中式結(jié)構(gòu).基于得到的社區(qū)劃分結(jié)果,節(jié)點相互協(xié)作進(jìn)行路由決策以完成興趣包和數(shù)據(jù)包的交付,因此,路由決策組件為分布式結(jié)構(gòu).

例如,在圖2 中,假設(shè)節(jié)點A,B和D屬于同一個社交社區(qū),節(jié)點C,E和F屬于同一個興趣社區(qū).當(dāng)請求者A生成一個興趣包后,A根據(jù)興趣決策中的社區(qū)間轉(zhuǎn)發(fā)(因為A不屬于目標(biāo)興趣社區(qū))將請求發(fā)送給C.如果C緩存有請求內(nèi)容,則它會產(chǎn)生相應(yīng)的數(shù)據(jù)包返回給A;否則,C會根據(jù)興趣決策中的社區(qū)內(nèi)轉(zhuǎn)發(fā)(因為C屬于目標(biāo)興趣社區(qū))將內(nèi)容請求發(fā)送給E.假設(shè)E為內(nèi)容提供者,則它產(chǎn)生數(shù)據(jù)包返還給A.之后,E根據(jù)數(shù)據(jù)決策中的社區(qū)間轉(zhuǎn)發(fā)(因為E和A不屬于同一社交社區(qū))將數(shù)據(jù)包發(fā)送給D,D根據(jù)網(wǎng)絡(luò)內(nèi)緩存規(guī)則對數(shù)據(jù)包中的內(nèi)容進(jìn)行本地緩存.最后,D根據(jù)數(shù)據(jù)決策中的社區(qū)內(nèi)轉(zhuǎn)發(fā)(因為D和A屬于同一社交社區(qū))將數(shù)據(jù)包交付給A.

3 社區(qū)發(fā)現(xiàn)

3.1 興趣社區(qū)發(fā)現(xiàn)

3.1.1 興趣距離

在ICN 架構(gòu)中,請求者生成的請求由分層的內(nèi)容名字構(gòu)成,如/c/…/c/fname/version/s.用戶的歷史請求能夠體現(xiàn)用戶對于不同類型內(nèi)容的偏好.當(dāng)用戶對某一類型的內(nèi)容感興趣時,其請求會多次包含這一內(nèi)容對應(yīng)的字段;否則,用戶的請求會較少包含對應(yīng)字段.因此,本文根據(jù)用戶的歷史請求所包含的內(nèi)容字段計算用戶對于不同內(nèi)容分類的興趣偏好.假設(shè)存在n個不同的內(nèi)容字段,fieldk為任意內(nèi)容字段,1≤k≤n.設(shè)網(wǎng)絡(luò)中有m個節(jié)點,Ri為其中任意節(jié)點,1≤i≤m.

定義1(興趣權(quán)值).興趣權(quán)值為節(jié)點對一個字段的歷史請求次數(shù).令代表Ri對fieldk的興趣權(quán)值,則當(dāng)Ri生成一個包含fieldk的請求時:

將n個興趣權(quán)值降序排列,和它們對應(yīng)的內(nèi)容字段一起組成Ri的興趣集合.令I(lǐng)ni代表Ri的興趣集合,Ini中存儲的元素為二元組〈字段,興趣權(quán)值〉.假設(shè)n=2,Ri的興趣集合中包含field2,field6以及它們對應(yīng)的興趣權(quán)值,則:

定義2(興趣距離).興趣距離為兩個節(jié)點的興趣集合中,相同字段對應(yīng)興趣權(quán)值的絕對值之和,如果兩個節(jié)點的興趣集合中沒有相同的字段,則興趣距離為+∞.

假設(shè)Rj為網(wǎng)絡(luò)中任意節(jié)點,1≤j≤m且i≠j,用idesij表示Ri和Rj之間的興趣距離,則:

興趣距離衡量和節(jié)點之間的興趣相似度.根據(jù)公式(3)可得:兩個節(jié)點之間興趣距離的值越小,節(jié)點間的興趣相似度越高.

3.1.2 基于節(jié)點興趣的社區(qū)發(fā)現(xiàn)

基于文獻(xiàn)[20]中的社區(qū)劃分方法,將節(jié)點劃分為不同的興趣社區(qū).首先,根據(jù)收集到的節(jié)點的歷史請求內(nèi)容的信息,能夠計算節(jié)點之間的興趣距離.本文將網(wǎng)絡(luò)抽象為無向帶權(quán)圖G(V,E,W),其中:V是網(wǎng)絡(luò)中所有的節(jié)點集合;E是邊集合(每對節(jié)點存在一條邊);W是邊的權(quán)值集合,每條邊的權(quán)值為其兩端節(jié)點興趣距離的倒數(shù).興趣社區(qū)劃分方法步驟如下.

1) 將所有節(jié)點作為一個初始社區(qū);

2) 計算對應(yīng)無權(quán)圖中所有邊的邊介數(shù),再將邊介數(shù)除以其權(quán)重得到邊權(quán)比;

/*這里的邊介數(shù)采用最短路徑邊介數(shù)方法,即一條邊的邊介數(shù)是指從某個源節(jié)點出發(fā)通過該邊的最短路徑的數(shù)目,對所有可能的源節(jié)點,重復(fù)做同樣的計算,并將得到的相對于各個不同的源節(jié)點的邊介數(shù)相加,所得的累加和為該邊的邊介數(shù)*/

3) 刪除邊權(quán)比最高的邊,并計算網(wǎng)絡(luò)的模塊度Q(見公式(4))[20]來衡量網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的顯著性.在計算時,若邊權(quán)比最高的邊有多條,則同時移除這些邊,并將移除的邊和模塊度進(jìn)行存儲:

其中,aij為網(wǎng)絡(luò)鄰接矩陣的元素,若節(jié)點Ri和Rj相連,則aij為邊的權(quán)重,否則等于0;δ為隸屬函數(shù),若Ri和Rj屬于同一個社區(qū),則其值為1,否則等于0;,即網(wǎng)絡(luò)中邊的權(quán)重之和.在網(wǎng)絡(luò)劃分結(jié)構(gòu)固定且兩節(jié)點的邊隨機(jī)連接時,節(jié)點間存在邊的可能性為kikj/(2M),其中,ki為節(jié)點i的點權(quán),計算方法為對連通矩陣的第i行求和.

4) 重復(fù)步驟2)、步驟3),直到所有的邊被刪除.

當(dāng)所有邊均被刪除時,對應(yīng)于模塊度最大的社區(qū)劃分(每個連通圖為一個社區(qū))即為最終的興趣社區(qū)劃分.

3.2 社交社區(qū)發(fā)現(xiàn)

3.2.1 相遇規(guī)律

節(jié)點間的歷史相遇體現(xiàn)了它們之間的相遇規(guī)律,包括相遇的頻率、持續(xù)時間和周期性等.節(jié)點間規(guī)律強(qiáng)的歷史相遇往往意味著它們未來相遇的頻率可能高、持續(xù)時間可能長、周期性可能比較強(qiáng).

本文根據(jù)節(jié)點之間的歷史相遇信息計算節(jié)點的相遇規(guī)律,將其作為劃分社交社區(qū)的度量.首先,將Ri和Rj在τ時間內(nèi)的相遇歷史劃分為σ個相等的時間段,其中每個時間段的時長為.令Hij代表Ri和Rj的這σ個時間段的集合,則:

定義3(相遇項).相遇項代表兩節(jié)點在一個時間段內(nèi)是否相遇.令代表Ri和Rj在內(nèi)的相遇項,則:

定義4(單位相遇強(qiáng)度).一個時間段內(nèi)的單位相遇強(qiáng)度為相遇項與時間段個數(shù)的比值.令代表內(nèi)的單位相遇強(qiáng)度,則:

定義5(周期比對集).設(shè)Γ為比對周期,則一個周期內(nèi)的時間段個數(shù)noh為

將所有σ個時間段中上標(biāo)對noh取余后得到余數(shù)相等的相遇項定義為一個周期比對集,則可得到noh個周期比對集,每個周期比對集中有個時間段和個相遇項.令Compareij代表Ri和Rj所有的周期比對集合,則:

定義6(周期度量).周期度量是一個周期比對集中所有非零的相遇項之和與這個周期比對集中的相遇項總數(shù)量的比值,代表兩個節(jié)點相遇周期性的強(qiáng)度.令代表的周期度量,則:

定義7(單位相遇規(guī)律).兩個節(jié)點在一個時間段的單位相遇規(guī)律為其單位相遇強(qiáng)度和對應(yīng)周期度量的乘積.令代表Ri和Rj在內(nèi)的單位相遇規(guī)律,則:

其中,q=p%noh+1.

Ri和Rj的相遇規(guī)律為它們所有的單位相遇規(guī)律的總和.令regij代表Ri和Rj的相遇規(guī)律,其計算如下:

舉例計算相遇規(guī)律如下:設(shè)σ=10,τ=50 小時,則每個時間段的時長為50/10=5h.假設(shè)圖3 表示Ri和Rj在50h的時間內(nèi)的相遇歷史.從圖3 可見:共有10 個時間段,每個時間段有對應(yīng)的相遇項和單位相遇強(qiáng)度.

Fig.3 Example of encounter regularity calculation圖3 相遇規(guī)律計算舉例

設(shè)Γ=10h,則一個周期內(nèi)的時間段個數(shù)為noh=(10×10)/50=2,兩個周期比對集(時間段的上標(biāo)對2 取余等于0)和0}(時間段的上標(biāo)對2 取余等于1).進(jìn)而得到兩個周期比對集合的周期度量.據(jù)此可得Ri和Rj的單位相遇規(guī)律;同理可得,而其余項均為0.最后,將各單位相遇規(guī)律求和,可得Ri和Rj的相遇規(guī)律regij=0.16.

3.2.2 基于節(jié)點社交關(guān)系的社區(qū)發(fā)現(xiàn)

基于節(jié)點社交關(guān)系的社區(qū)發(fā)現(xiàn)與第3.1.2 節(jié)基于節(jié)點興趣的社區(qū)發(fā)現(xiàn)相類似.不同地,邊的權(quán)值為兩個端節(jié)點的相遇規(guī)律.

4 路由決策

4.1 興趣決策

4.1.1 社區(qū)內(nèi)轉(zhuǎn)發(fā)

本文中,每個節(jié)點存儲興趣社區(qū)成員持有的內(nèi)容情況.令Conti代表Ri存儲的興趣成員持有內(nèi)容的集合,Conti中存儲二元組〈內(nèi)容名字,節(jié)點〉.特別地,如果興趣社區(qū)中有多個成員持有一個內(nèi)容,則Conti中存儲對應(yīng)于這個內(nèi)容的節(jié)點為這些節(jié)點中與Ri社交規(guī)律值最大的節(jié)點.令cnip代表興趣包ip請求的內(nèi)容字段,如果:

則Ri對ip執(zhí)行社區(qū)內(nèi)轉(zhuǎn)發(fā).

根據(jù)Conti能夠獲知持有請求內(nèi)容的節(jié)點,興趣包路由即從未知目的節(jié)點的情形轉(zhuǎn)化為已知目的節(jié)點的情形.由于本文的數(shù)據(jù)包轉(zhuǎn)發(fā)過程已知目的節(jié)點(詳見第4.2.2 節(jié)),因此興趣包的社區(qū)內(nèi)轉(zhuǎn)發(fā)根據(jù)數(shù)據(jù)包轉(zhuǎn)發(fā)策略進(jìn)行(詳見后文第4.2.2 節(jié)和第4.2.3 節(jié)).

4.1.2 社區(qū)間轉(zhuǎn)發(fā)

如果接收到興趣包的節(jié)點的興趣社區(qū)成員均未持有請求內(nèi)容,則節(jié)點進(jìn)行社區(qū)間興趣包轉(zhuǎn)發(fā).令Fieldip代表ip請求的內(nèi)容名字中包含的所有字段的集合,即:

定義8(興趣度量).節(jié)點的興趣度量為請求內(nèi)容名字包含所有字段的興趣權(quán)值總和.令代表節(jié)點Ri對cnip的興趣度量,則:

為了防止單副本轉(zhuǎn)發(fā)方式易造成路由陷入“死胡同”,本文提出如下回溯策略進(jìn)行興趣包社區(qū)間轉(zhuǎn)發(fā).當(dāng)節(jié)點持有興趣包的時間超過時間閾值ψ,則認(rèn)為興趣包陷入“死胡同”.令代表Ri持有ip的時間,即,如果:

則認(rèn)為ip陷入“死胡同”.

如果興趣包沒有陷入“死胡同”,則將興趣包轉(zhuǎn)發(fā)給具有更高興趣度量的相遇節(jié)點.令Rx代表Ri的任意相遇節(jié)點,1≤x≤m且代表相遇節(jié)點Rx對cnip的興趣度量,則,如果:

則Ri將ip轉(zhuǎn)發(fā)給Rx.

若不滿足公式(17),即ip陷入“死胡同”,則降低ip的轉(zhuǎn)發(fā)條件,即不再只將ip發(fā)送給對興趣包的內(nèi)容名字的興趣度量更高的相遇節(jié)點,而是對于具有低于范圍[0,ξ]的興趣度量的相遇節(jié)點,同樣將ip轉(zhuǎn)發(fā)給它,即,如果:

則Ri將ip轉(zhuǎn)發(fā)給Rx.興趣決策見算法1.

算法1.興趣決策.

4.2 數(shù)據(jù)決策

4.2.1 網(wǎng)絡(luò)內(nèi)緩存

由于在MSN 中的節(jié)點存儲空間有限,因此,節(jié)點無法實現(xiàn)在本地存儲所有內(nèi)容.本文設(shè)定節(jié)點相遇時交換各自的興趣集合.當(dāng)節(jié)點接收到一個數(shù)據(jù)包時,根據(jù)數(shù)據(jù)包中的內(nèi)容名字,為每一個內(nèi)容計算一個存儲權(quán)值.存儲權(quán)值的計算考慮所有社交社區(qū)和興趣社區(qū)共同成員對這個內(nèi)容的偏好程度.如果社交社區(qū)成員對其偏好程度較大,則存儲時間較長.存儲權(quán)值為所有的社交社區(qū)和興趣社區(qū)的共同成員對這個內(nèi)容名字的興趣度量的總和.當(dāng)緩存空間不足時,將權(quán)值最低的內(nèi)容首先丟棄.令SCoMi代表Ri的上述共同成員集合.假設(shè)SCoMi共包含d個節(jié)點,令Rc代表其中任意一個節(jié)點,1≤c≤d.令代表Ri對名字為cn的內(nèi)容的緩存權(quán)值,則:

4.2.2 社區(qū)內(nèi)轉(zhuǎn)發(fā)

在MSN 中,節(jié)點的移動會造成網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化.因此在ICRS 中,為了將數(shù)據(jù)包發(fā)送給請求節(jié)點而不受變化的拓?fù)溆绊?在興趣包中標(biāo)記請求節(jié)點.當(dāng)內(nèi)容提供者收到興趣包后產(chǎn)生數(shù)據(jù)包時,同樣為數(shù)據(jù)包標(biāo)記請求節(jié)點.這樣,數(shù)據(jù)包路由過程即轉(zhuǎn)化為已知目的節(jié)點的路由過程.令Rr代表一個數(shù)據(jù)包dp的內(nèi)容請求者,當(dāng)Ri接收到dp時,Ri判斷Rr是否為Ri的社交社區(qū)成員.即,如果:

則Ri執(zhí)行社區(qū)內(nèi)轉(zhuǎn)發(fā)規(guī)則;否則執(zhí)行社區(qū)間轉(zhuǎn)發(fā)規(guī)則(后文第4.2.3 節(jié)).

根據(jù)第3.1.2 節(jié)社交社區(qū)的劃分方法,一個社交社區(qū)的成員具有相互之間比較緊密的相遇規(guī)律,即相互均具有較高的相遇概率.首次相遇路由[21]將包發(fā)送給第1 次相遇的節(jié)點,其轉(zhuǎn)發(fā)機(jī)制簡單且計算復(fù)雜度低.本文基于首次相遇路由,提出社區(qū)內(nèi)首次相遇路由(intra-community first contact routing,簡稱ICFC)機(jī)制,將數(shù)據(jù)包發(fā)送給首次相遇的、從未接收過該數(shù)據(jù)包的社交社區(qū)成員.

令Pkx代表任意相遇節(jié)點Rx攜帶的包集合,如果:

則Ri將dp發(fā)送給Rx.

4.2.3 社區(qū)間轉(zhuǎn)發(fā)

與第4.1.2 節(jié)興趣決策中的社區(qū)間轉(zhuǎn)發(fā)相類似,數(shù)據(jù)包的社區(qū)間轉(zhuǎn)發(fā)包括兩種轉(zhuǎn)發(fā):陷入“死胡同”時基于回溯策略的轉(zhuǎn)發(fā),沒有陷入“死胡同”時的轉(zhuǎn)發(fā).當(dāng)節(jié)點持有dp的時間超過閾值ε,則認(rèn)為dp陷入“死胡同”.令holdtimdp代表節(jié)點持有dp的時間,即,如果:

則認(rèn)為dp陷入“死胡同”.

如果數(shù)據(jù)包沒有陷入“死胡同”,則將數(shù)據(jù)包轉(zhuǎn)發(fā)給與Rr相遇規(guī)律更高的相遇節(jié)點.令regxr代表任意相遇節(jié)點Rx與Rr的相遇規(guī)律,如果:

則Ri將dp轉(zhuǎn)發(fā)給Rx.

若未陷入“死胡同”,則將dp發(fā)送給這樣的節(jié)點Rx,其中,Ri和Rr的相遇規(guī)律與Rx和Rr的相遇規(guī)律的差值范圍在[0,?],?是決定回溯節(jié)點范圍的閾值.即,如果:

則Ri將dp轉(zhuǎn)發(fā)給Rx.數(shù)據(jù)決策見算法2.

算法2.數(shù)據(jù)決策.

5 仿真實現(xiàn)與性能評價

5.1 仿真設(shè)置

采用兩種拓?fù)?劍橋軌跡(Cambridge trace)[22]和在文獻(xiàn)[18]中使用的合成軌跡(synthetic trace)在機(jī)會網(wǎng)絡(luò)環(huán)境(opportunistic network environment,簡稱ONE)[23]上進(jìn)行仿真實驗.在Cambridge 軌跡中,Haggle Project 將iMotes 分發(fā)給Cambridge 計算機(jī)實驗室的36 個大學(xué)生,并收集他們歷時11 天的實驗性數(shù)據(jù).Synthetic 軌跡包含120 個節(jié)點,它們被分為兩個社區(qū):一個社區(qū)包含50 個節(jié)點,另一個包含70 個節(jié)點且其中有20 個節(jié)點頻繁地在兩個社區(qū)之間移動.將本文提出的ICRS 與文獻(xiàn)[18]提出的社區(qū)間基于社交聯(lián)系的內(nèi)容查找(social-tie based content retrieval among communities,簡稱STCRC)策略進(jìn)行對比,因為STCRC 同樣是基于ICN 和社區(qū)結(jié)構(gòu)的路由機(jī)制,與ICRS 較為相似.STCRC 令社區(qū)中具有高社交地位的節(jié)點記錄社區(qū)成員所持有內(nèi)容的情況,節(jié)點將內(nèi)容請求發(fā)送給具有較高社會地位的節(jié)點.如果社區(qū)成員沒有匹配的內(nèi)容,則進(jìn)行社區(qū)間內(nèi)容查找.一旦獲知內(nèi)容提供者,則根據(jù)與內(nèi)容提供者的相遇可能進(jìn)行路由.

采用如下4 個指標(biāo)進(jìn)行性能評價:包交付率(packet delivery ratio,簡稱PDR)、平均跳數(shù)(average HoP,簡稱AHP)、平均延遲(average DeLay,簡稱ADL)和網(wǎng)絡(luò)開銷(network OverHead,簡稱NOH).PDR 是交付的包數(shù)量(包括興趣包和數(shù)據(jù)包)與生成包的總量的比值,AHP 是所有交付的包所經(jīng)歷的跳數(shù)與交付的包的數(shù)量的比值,ADL 是所有交付的包經(jīng)歷的時長與交付的包的數(shù)量的比值,NOH 是所有生成的包被轉(zhuǎn)發(fā)的次數(shù)與所有交付的包的數(shù)量的比值.

ICRS 有網(wǎng)絡(luò)內(nèi)緩存機(jī)制,而STCRC 沒有緩存機(jī)制.由于本文的網(wǎng)絡(luò)內(nèi)緩存機(jī)制基于第3.1.1 節(jié)提出的興趣集,因此無法直接用于STCRC.為了更好地對比這兩種算法的轉(zhuǎn)發(fā)機(jī)制,為ICRS 和STCRC 配置先進(jìn)先出(first in first out,簡稱FIFO)緩存機(jī)制,從而產(chǎn)生了兩種新的算法,即ICRS-F 和STCRC-F.其中,FIFO 緩存機(jī)制的規(guī)則是:當(dāng)節(jié)點緩存空間不足時,刪除最早進(jìn)入緩存區(qū)的內(nèi)容.仿真參數(shù)設(shè)置如下:σ=6,ξ=?=0.2.在Cambridge trace 中,τ=24h,Γ=8h,ψ=ε=0.5h;在Synthetic trace 中,τ=3600s,Γ=1200s,ψ=ε=60s.

5.2 性能評價

5.2.1 社區(qū)結(jié)構(gòu)

每個場景(Cambridge 和synthetic)的社區(qū)劃分情況如圖4 和圖5 所示,圖中虛線對應(yīng)的社區(qū)劃分狀態(tài)為采用的社區(qū)劃分結(jié)構(gòu),此時對應(yīng)于圖4(a)、圖4(b)、圖5(a)和圖5(b)的模塊度分別為0.354 5,0.240 9,0.493 8 和0.499 5.此外,通過在Cambridge 中為τ配置不同取值(3h 和24h),能夠得到不同的社交社區(qū)結(jié)構(gòu)(不同社區(qū)結(jié)構(gòu)的模塊度對應(yīng)于3h 和24h 分別為Q=0.2338 和0.3545).

為了分析社區(qū)劃分的結(jié)果對路由性能的影響,測試這兩種模塊度的社交社區(qū)結(jié)構(gòu)下的包交付率,如圖6 所示.結(jié)果表明,較高的社區(qū)結(jié)構(gòu)的模塊度能夠得到較高的包交付率.

Fig.4 Social community detection圖4 社交社區(qū)劃分

Fig.5 Interest community detection圖5 興趣社區(qū)劃分

Fig.6 Performance influence by communities圖6 社區(qū)對性能的影響

5.2.2 包交付率

ICRS,STCRC,ICRS-F 和STCRC-F 在兩種拓?fù)洹⒉煌陌鏁r間(time to live,簡稱TTL)下的包交付率如圖7(a)、圖9(a)所示;在兩種拓?fù)洹⒉煌\行時間下的包交付率如圖8(a)、圖10(a)所示.對比ICRS 和STCRC,可以發(fā)現(xiàn)ICRS 具有更高的包交付率.原因如下:ICRS 進(jìn)行有效的網(wǎng)絡(luò)內(nèi)緩存,基于其他節(jié)點在未來訪問的可能性對緩存的內(nèi)容進(jìn)行有效的管理.因此,ICRS 能夠在有限的包的TTL 內(nèi)響應(yīng)更多的興趣包,而不是僅僅由源內(nèi)容提供者獲得內(nèi)容.進(jìn)一步,在路由興趣包時,ICRS 基于根據(jù)節(jié)點興趣劃分的興趣社區(qū),而在路由數(shù)據(jù)包時,基于根據(jù)節(jié)點相遇規(guī)律劃分的社交社區(qū).這使對興趣包和數(shù)據(jù)包的轉(zhuǎn)發(fā)更加精確,從而提高了包交付率.然而,STCRC 根據(jù)基于節(jié)點間的相遇規(guī)律得到的社區(qū)轉(zhuǎn)發(fā)興趣包和數(shù)據(jù)包,這會使興趣包的路由不準(zhǔn)確,因為相遇規(guī)律強(qiáng)的節(jié)點不一定持有請求的內(nèi)容.

對比ICRS-F 和STCRC-F 可知,ICRS-F 具有較高的包交付率.這說明除去網(wǎng)絡(luò)內(nèi)緩存為ICRS 帶來的優(yōu)勢,ICRS 的轉(zhuǎn)發(fā)機(jī)制相比于STCRC 仍然具有更好的性能.進(jìn)一步,對比ICRS 和ICRS-F 可知,ICRS 具有更高的包交付率.這是因為ICRS 使用本文提出的網(wǎng)絡(luò)內(nèi)緩存機(jī)制,允許節(jié)點緩存后續(xù)以較大可能被其他節(jié)點請求的內(nèi)容,進(jìn)而提高了網(wǎng)絡(luò)的交付率.相比之下,FIFO 緩存機(jī)制在緩存空間不足時,僅僅將先到達(dá)緩存空間的內(nèi)容進(jìn)行刪除,沒有考慮內(nèi)容是否可能被其他節(jié)點在未來請求.同樣,由于STCRC-F 進(jìn)行了網(wǎng)絡(luò)內(nèi)緩存,它比STCRC 具有更高的包交付率.

Fig.7 Cambridge (varying TTL)圖7 Cambridge(變化TTL)

Fig.8 Cambridge (varying running time)圖8 Cambridge(變化運行時間)

Fig.9 Synthetic (varying TTL)圖9 Synthetic(變化TTL)

Fig.10 Synthetic (varying running time)圖10 Synthetic(變化運行時間)

5.2.3 平均跳數(shù)

ICRS,STCRC,ICRS-F 和STCRC-F 在兩種拓?fù)?、不同的包TTL 下的平均跳數(shù)如圖7(b)、圖9(b)所示;在兩種拓?fù)?、不同運行時間下的平均跳數(shù)如圖8(b)、圖10(b)所示.對比ICRS 和STCRC 可以發(fā)現(xiàn):ICRS 具有更低的平均跳數(shù),且跳數(shù)在1 和2 之間.之所以ICRS 的平均跳數(shù)只有不到2 跳,一方面是因為ICRS 進(jìn)行了網(wǎng)絡(luò)內(nèi)緩存的緣故.根據(jù)ICRS 的網(wǎng)絡(luò)內(nèi)緩存規(guī)則,節(jié)點基于其社交社區(qū)和興趣社區(qū)的共同成員對內(nèi)容的興趣偏好總和進(jìn)行計算,并決定緩存時間.因此,得益于網(wǎng)絡(luò)內(nèi)緩存,節(jié)點能夠以最大概率從其鄰近的其他節(jié)點處獲得感興趣的內(nèi)容.另一方面,是因為實驗中內(nèi)容數(shù)量和節(jié)點的緩存空間的設(shè)置導(dǎo)致的.

在Cambridge 軌跡中,實驗設(shè)置36 個不同內(nèi)容種類,節(jié)點的緩存空間設(shè)置為10 個內(nèi)容(假設(shè)內(nèi)容尺寸相同).由于實驗中節(jié)點對不同內(nèi)容的請求符合冪律分布(實驗中冪律分布的指數(shù)設(shè)為2.5),因此經(jīng)常被用戶請求的內(nèi)容不超過8 個(約為36×20%).所以,大多數(shù)的請求能夠在不到2 跳獲得內(nèi)容.

在Synthetic 軌跡中,其原因類似,只是不同內(nèi)容種類設(shè)置為120 個,節(jié)點的緩存空間設(shè)置為30 個.對于STCRC,當(dāng)節(jié)點為興趣包查找內(nèi)容提供者時,首先需要從社區(qū)內(nèi)中心度最高的節(jié)點處獲知社區(qū)內(nèi)是否有成員持有該內(nèi)容.如果社區(qū)內(nèi)沒有內(nèi)容提供者,則需要進(jìn)一步向社區(qū)外節(jié)點進(jìn)行查找.這種內(nèi)容查找方法使興趣包的檢索經(jīng)歷了較多轉(zhuǎn)發(fā)節(jié)點,從而導(dǎo)致平均跳數(shù)較高.在圖7(a)、圖7(b)中可見,ICRS 和ICRS-F 的AHP 呈現(xiàn)下降趨勢.這是因為隨著運行時間的增加,社區(qū)結(jié)構(gòu)趨于穩(wěn)定,使路由過程的準(zhǔn)確性得到了提高,包能夠經(jīng)歷更少的跳數(shù)得到交付.

5.2.4 平均延遲

ICRS,STCRC,ICRS-F 和STCRC-F 在兩種拓?fù)?、不同的包TTL 下的平均延遲如圖7(c)、圖9(c)所示;在兩種拓?fù)洹⒉煌\行時間下的平均延遲如圖8(c)、圖10(c)所示.對比ICRS 和STCRC 可以發(fā)現(xiàn),ICRS 具有更低的平均延遲.ICRS 依據(jù)不同的社區(qū)劃分結(jié)果分別對興趣包和數(shù)據(jù)包進(jìn)行路由,適當(dāng)使用的社區(qū)加快了包交付的過程.雖然STCRC 同樣基于社區(qū)進(jìn)行路由,然而,當(dāng)路由興趣包時,STCRC 根據(jù)基于相遇規(guī)律劃分的社區(qū)無法有效找到內(nèi)容提供者,從而使興趣包交付具有較長時間的延遲.

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

ICRS,STCRC,ICRS-F 和STCRC-F 在兩種拓?fù)洹⒉煌陌黅TL 下的網(wǎng)絡(luò)開銷如圖7(d)、圖9(d)所示;在兩種拓?fù)?、不同運行時間下的網(wǎng)絡(luò)開銷如圖8(d)、圖10(d)所示.對比ICRS 和STCRC 可以發(fā)現(xiàn),ICRS 具有更低的網(wǎng)絡(luò)開銷.得益于網(wǎng)絡(luò)內(nèi)緩存和準(zhǔn)確的社區(qū)劃分,ICRS 減少了對包無用的轉(zhuǎn)發(fā),因此具有較低的網(wǎng)絡(luò)開銷.

在圖7(d)、圖9(d)中,對于STCRC,由于包所經(jīng)歷的較高平均跳數(shù),因此當(dāng)TTL 過期時包還未實現(xiàn)交付,使其轉(zhuǎn)發(fā)沒有對全網(wǎng)范圍內(nèi)的最終交付產(chǎn)生貢獻(xiàn),導(dǎo)致較高的網(wǎng)絡(luò)開銷.

在圖8(d)和圖10(d)中可見,ICRS 的NOH 呈現(xiàn)下降趨勢.這是因為隨著運行時間的增加,社區(qū)結(jié)構(gòu)趨于穩(wěn)定;同時,隨著運行時間增加,網(wǎng)絡(luò)內(nèi)緩存趨于優(yōu)化,節(jié)點存儲后續(xù)被其他節(jié)點請求的重復(fù)或者相似的內(nèi)容,使路由開銷下降.

從圖7～圖10 可以觀察到,Synthetic 比Cambridge 總體呈現(xiàn)更好的性能,即更高的包交付率、更低的包交付延遲、平均跳數(shù)和網(wǎng)絡(luò)開銷.原因如下.

· Synthetic 軌跡是120 個節(jié)點所組成的較密集拓?fù)?運行時間為43 200s,節(jié)點之間的相遇頻率較高且相遇間隔較小;

· 而Cambridge 軌跡是36 個點所組成的較稀疏拓?fù)?運行時間為987 530s,節(jié)點之間的相遇頻率較低且相遇間隔較大.

因此,Synthetic 能夠比Cambridge 在有限的生存時間TTL(time to live)內(nèi)用更短的時間、更少的跳數(shù)和開銷交付更多的包.

6 結(jié) 論

對于移動社交網(wǎng)絡(luò),提出一種基于信息中心網(wǎng)絡(luò)架構(gòu)的路由機(jī)制.通過節(jié)點的歷史請求內(nèi)容,刻畫節(jié)點的興趣差異度量,并劃分興趣社區(qū);依據(jù)興趣社區(qū),進(jìn)行興趣包轉(zhuǎn)發(fā).通過節(jié)點的相遇歷史,刻畫節(jié)點間的相遇規(guī)律度量,并劃分社交社區(qū);依據(jù)社交社區(qū),進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā).實驗結(jié)果表明,本文提出的機(jī)制在包交付率、平均跳數(shù)、平均延遲和網(wǎng)絡(luò)開銷上均優(yōu)于對比機(jī)制.在實際網(wǎng)絡(luò)背景下進(jìn)行實驗,進(jìn)一步驗證和提高本文機(jī)制的實用性,是未來研究工作的重點.