基于ICN網(wǎng)絡(luò)架構(gòu)的社區(qū)感知型MSN路由機(jī)制*

石峻嶺 , 王興偉 , 黃 敏

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

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

信息中心網(wǎng)絡(luò)(information-centric networking,簡(jiǎn)稱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)行命名,用戶的興趣請(qǐng)求使用的是內(nèi)容的名字,這些內(nèi)容名字體現(xiàn)了用戶對(duì)內(nèi)容的偏好.通過有效挖掘用戶對(duì)內(nèi)容的偏好,能夠計(jì)算節(jié)點(diǎn)的興趣,獲得節(jié)點(diǎn)之間興趣的相似程度,因而有助于解決MSN 中用戶間社交關(guān)系難以準(zhǔn)確獲取的問題.最后,ICN 關(guān)注節(jié)點(diǎn)的內(nèi)容緩存,支持節(jié)點(diǎn)對(duì)緩存內(nèi)容的優(yōu)化處理[14].當(dāng)緩存空間不足時(shí),盡可能緩存后續(xù)可能被其他用戶以較高概率訪問的內(nèi)容,后續(xù)被訪問概率低的內(nèi)容不被緩存或被替換.因此,通過在MSN 的節(jié)點(diǎn)中引入內(nèi)容緩存機(jī)制,對(duì)內(nèi)容進(jìn)行有效管理,可以提高對(duì)用戶后續(xù)內(nèi)容訪問需求的滿足程度.基于上述考慮,本文基于ICN 架構(gòu),提出一種MSN 中的新型路由機(jī)制.

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

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

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

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

1 相關(guān)工作

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

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

2 系統(tǒng)框架

2.1 系統(tǒng)模塊

如圖1 所示,本文提出的基于ICN 網(wǎng)絡(luò)架構(gòu)的社區(qū)感知型路由機(jī)制(ICN based community aware routing scheme,簡(jiǎn)稱ICRS)主要包含兩個(gè)組件,分別是社區(qū)發(fā)現(xiàn)和路由決策.前者為基于用戶的興趣偏好劃分興趣社區(qū),同時(shí)基于節(jié)點(diǎn)的相遇規(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é)點(diǎn)通過基礎(chǔ)設(shè)施與Internet 相連;在分布式MSN 中,節(jié)點(diǎn)通過設(shè)備對(duì)設(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 工作場(chǎng)景與流程

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

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

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

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

3.1.1 興趣距離

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.1 相遇規(guī)律

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

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

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

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

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

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

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

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

其中,q=p%noh+1.

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

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

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

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

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

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

4 路由決策

4.1 興趣決策

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

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

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

根據(jù)Conti能夠獲知持有請(qǐng)求內(nèi)容的節(jié)點(diǎn),興趣包路由即從未知目的節(jié)點(diǎn)的情形轉(zhuǎn)化為已知目的節(jié)點(diǎn)的情形.由于本文的數(shù)據(jù)包轉(zhuǎn)發(fā)過程已知目的節(jié)點(diǎn)(詳見第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é)點(diǎn)的興趣社區(qū)成員均未持有請(qǐng)求內(nèi)容,則節(jié)點(diǎn)進(jìn)行社區(qū)間興趣包轉(zhuǎn)發(fā).令Fieldip代表ip請(qǐng)求的內(nèi)容名字中包含的所有字段的集合,即:

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

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

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

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

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

若不滿足公式(17),即ip陷入“死胡同”,則降低ip的轉(zhuǎn)發(fā)條件,即不再只將ip發(fā)送給對(duì)興趣包的內(nèi)容名字的興趣度量更高的相遇節(jié)點(diǎn),而是對(duì)于具有低于范圍[0,ξ]的興趣度量的相遇節(jié)點(diǎn),同樣將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é)點(diǎn)存儲(chǔ)空間有限,因此,節(jié)點(diǎn)無法實(shí)現(xiàn)在本地存儲(chǔ)所有內(nèi)容.本文設(shè)定節(jié)點(diǎn)相遇時(shí)交換各自的興趣集合.當(dāng)節(jié)點(diǎn)接收到一個(gè)數(shù)據(jù)包時(shí),根據(jù)數(shù)據(jù)包中的內(nèi)容名字,為每一個(gè)內(nèi)容計(jì)算一個(gè)存儲(chǔ)權(quán)值.存儲(chǔ)權(quán)值的計(jì)算考慮所有社交社區(qū)和興趣社區(qū)共同成員對(duì)這個(gè)內(nèi)容的偏好程度.如果社交社區(qū)成員對(duì)其偏好程度較大,則存儲(chǔ)時(shí)間較長(zhǎng).存儲(chǔ)權(quán)值為所有的社交社區(qū)和興趣社區(qū)的共同成員對(duì)這個(gè)內(nèi)容名字的興趣度量的總和.當(dāng)緩存空間不足時(shí),將權(quán)值最低的內(nèi)容首先丟棄.令SCoMi代表Ri的上述共同成員集合.假設(shè)SCoMi共包含d個(gè)節(jié)點(diǎn),令Rc代表其中任意一個(gè)節(jié)點(diǎn),1≤c≤d.令代表Ri對(duì)名字為cn的內(nèi)容的緩存權(quán)值,則:

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

在MSN 中,節(jié)點(diǎn)的移動(dòng)會(huì)造成網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化.因此在ICRS 中,為了將數(shù)據(jù)包發(fā)送給請(qǐng)求節(jié)點(diǎn)而不受變化的拓?fù)溆绊?在興趣包中標(biāo)記請(qǐng)求節(jié)點(diǎn).當(dāng)內(nèi)容提供者收到興趣包后產(chǎn)生數(shù)據(jù)包時(shí),同樣為數(shù)據(jù)包標(biāo)記請(qǐng)求節(jié)點(diǎn).這樣,數(shù)據(jù)包路由過程即轉(zhuǎn)化為已知目的節(jié)點(diǎn)的路由過程.令Rr代表一個(gè)數(shù)據(jù)包dp的內(nèi)容請(qǐng)求者,當(dāng)Ri接收到dp時(shí),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ū)的劃分方法,一個(gè)社交社區(qū)的成員具有相互之間比較緊密的相遇規(guī)律,即相互均具有較高的相遇概率.首次相遇路由[21]將包發(fā)送給第1 次相遇的節(jié)點(diǎn),其轉(zhuǎn)發(fā)機(jī)制簡(jiǎn)單且計(jì)算復(fù)雜度低.本文基于首次相遇路由,提出社區(qū)內(nèi)首次相遇路由(intra-community first contact routing,簡(jiǎn)稱ICFC)機(jī)制,將數(shù)據(jù)包發(fā)送給首次相遇的、從未接收過該數(shù)據(jù)包的社交社區(qū)成員.

令Pkx代表任意相遇節(jié)點(diǎn)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ā):陷入“死胡同”時(shí)基于回溯策略的轉(zhuǎn)發(fā),沒有陷入“死胡同”時(shí)的轉(zhuǎn)發(fā).當(dāng)節(jié)點(diǎn)持有dp的時(shí)間超過閾值ε,則認(rèn)為dp陷入“死胡同”.令holdtimdp代表節(jié)點(diǎn)持有dp的時(shí)間,即,如果:

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

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

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

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

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

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

5 仿真實(shí)現(xiàn)與性能評(píng)價(jià)

5.1 仿真設(shè)置

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

采用如下4 個(gè)指標(biāo)進(jìn)行性能評(píng)價(jià):包交付率(packet delivery ratio,簡(jiǎn)稱PDR)、平均跳數(shù)(average HoP,簡(jiǎn)稱AHP)、平均延遲(average DeLay,簡(jiǎn)稱ADL)和網(wǎng)絡(luò)開銷(network OverHead,簡(jiǎn)稱NOH).PDR 是交付的包數(shù)量(包括興趣包和數(shù)據(jù)包)與生成包的總量的比值,AHP 是所有交付的包所經(jīng)歷的跳數(shù)與交付的包的數(shù)量的比值,ADL 是所有交付的包經(jīng)歷的時(shí)長(zhǎ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.為了更好地對(duì)比這兩種算法的轉(zhuǎn)發(fā)機(jī)制,為ICRS 和STCRC 配置先進(jìn)先出(first in first out,簡(jiǎn)稱FIFO)緩存機(jī)制,從而產(chǎn)生了兩種新的算法,即ICRS-F 和STCRC-F.其中,FIFO 緩存機(jī)制的規(guī)則是:當(dāng)節(jié)點(diǎn)緩存空間不足時(shí),刪除最早進(jìn)入緩存區(qū)的內(nèi)容.仿真參數(shù)設(shè)置如下:σ=6,ξ=?=0.2.在Cambridge trace 中,τ=24h,Γ=8h,ψ=ε=0.5h;在Synthetic trace 中,τ=3600s,Γ=1200s,ψ=ε=60s.

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

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

每個(gè)場(chǎng)景(Cambridge 和synthetic)的社區(qū)劃分情況如圖4 和圖5 所示,圖中虛線對(duì)應(yīng)的社區(qū)劃分狀態(tài)為采用的社區(qū)劃分結(jié)構(gòu),此時(shí)對(duì)應(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)的模塊度對(duì)應(yīng)于3h 和24h 分別為Q=0.2338 和0.3545).

為了分析社區(qū)劃分的結(jié)果對(duì)路由性能的影響,測(cè)試這兩種模塊度的社交社區(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ū)對(duì)性能的影響

5.2.2 包交付率

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

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

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

Fig.10 Synthetic (varying running time)圖10 Synthetic(變化運(yùn)行時(shí)間)

5.2.3 平均跳數(shù)

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

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

在Synthetic 軌跡中,其原因類似,只是不同內(nèi)容種類設(shè)置為120 個(gè),節(jié)點(diǎn)的緩存空間設(shè)置為30 個(gè).對(duì)于STCRC,當(dāng)節(jié)點(diǎn)為興趣包查找內(nèi)容提供者時(shí),首先需要從社區(qū)內(nèi)中心度最高的節(jié)點(diǎn)處獲知社區(qū)內(nèi)是否有成員持有該內(nèi)容.如果社區(qū)內(nèi)沒有內(nèi)容提供者,則需要進(jìn)一步向社區(qū)外節(jié)點(diǎn)進(jìn)行查找.這種內(nèi)容查找方法使興趣包的檢索經(jīng)歷了較多轉(zhuǎn)發(fā)節(jié)點(diǎn),從而導(dǎo)致平均跳數(shù)較高.在圖7(a)、圖7(b)中可見,ICRS 和ICRS-F 的AHP 呈現(xiàn)下降趨勢(shì).這是因?yàn)殡S著運(yùn)行時(shí)間的增加,社區(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ù)?、不同運(yùn)行時(shí)間下的平均延遲如圖8(c)、圖10(c)所示.對(duì)比ICRS 和STCRC 可以發(fā)現(xiàn),ICRS 具有更低的平均延遲.ICRS 依據(jù)不同的社區(qū)劃分結(jié)果分別對(duì)興趣包和數(shù)據(jù)包進(jìn)行路由,適當(dāng)使用的社區(qū)加快了包交付的過程.雖然STCRC 同樣基于社區(qū)進(jìn)行路由,然而,當(dāng)路由興趣包時(shí),STCRC 根據(jù)基于相遇規(guī)律劃分的社區(qū)無法有效找到內(nèi)容提供者,從而使興趣包交付具有較長(zhǎng)時(shí)間的延遲.

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

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

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

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

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

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

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

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

6 結(jié) 論

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