BIRI：支持信息中心范型的BBO啟發(fā)式MSN路由算法

涂盼鵬 王興偉 李 婕 黃 敏

1(東北大學(xué)計算機科學(xué)與工程學(xué)院 沈陽 110169)2(復(fù)雜網(wǎng)絡(luò)系統(tǒng)安全保障技術(shù)教育部工程研究中心(東北大學(xué)) 沈陽 110169)3(東北大學(xué)信息科學(xué)與工程學(xué)院 沈陽 110819)

社會學(xué)將人類在實際生活中形成的網(wǎng)絡(luò)關(guān)系結(jié)構(gòu)稱為社交網(wǎng)絡(luò)[1].因人類具備社會屬性，社交網(wǎng)絡(luò)得以保持相對穩(wěn)定的結(jié)構(gòu).然而在移動社交網(wǎng)絡(luò)(mobile social network， MSN)中，用戶的移動導(dǎo)致端到端路由呈現(xiàn)間歇性，使MSN具備延遲容忍網(wǎng)絡(luò)(delay tolerant network， DTN)[2-3]的諸多特征，如投遞率低、延遲高、能量和存儲受限等.“盡力而為”的數(shù)據(jù)傳輸模式難以滿足當(dāng)今互聯(lián)網(wǎng)的需求，如何設(shè)計高效的MSN路由機制成為研究的重點和難點.

互聯(lián)網(wǎng)用戶規(guī)模劇增的同時，用戶對網(wǎng)絡(luò)中內(nèi)容的需求量也急劇上漲.但現(xiàn)有的基于IP地址的端到端主機通信模式難以有效地支持以內(nèi)容為中心的數(shù)據(jù)檢索和服務(wù)訪問[4].如何設(shè)計高效的內(nèi)容檢索策略也是當(dāng)前互聯(lián)網(wǎng)亟待解決的一大難題.對用戶而言，信息本身比其存儲位置更重要[5]，因此引入信息中心網(wǎng)絡(luò)(information-centric networking, ICN)的思想，將內(nèi)容名稱作為唯一網(wǎng)絡(luò)標識進行緩存和路由，是提升MSN路由效率的良好思路.

針對上述問題，本文充分利用MSN中的社交關(guān)系和社區(qū)結(jié)構(gòu)，引入ICN以內(nèi)容為中心的思想，基于網(wǎng)絡(luò)圖論對生物地理優(yōu)化(biogeography-based optimization, BBO)算法進行改進，以此為基礎(chǔ)設(shè)計了一種支持信息中心范型的BBO啟發(fā)式MSN路由算法(BBO-inspired MSN routing algorithm with information-centric paradigm support, BIRI).

本文的主要貢獻有4個方面：

1) 綜合考慮節(jié)點的接觸規(guī)律以及興趣和內(nèi)容的相似性，提出了新的度量用以衡量節(jié)點社會關(guān)系強度，并改進了中心度的計算方式;

2) 基于節(jié)點之間的內(nèi)容相似度以及網(wǎng)絡(luò)動態(tài)特性改進了BBO算法，優(yōu)化MSN中的社區(qū)劃分過程;

3) 引入ICN內(nèi)容為中心的設(shè)計思想，為MSN節(jié)點設(shè)計了內(nèi)容緩存和緩存替換策略;

4) 通過內(nèi)容聚集、橋節(jié)點選取等機制輔助數(shù)據(jù)包和興趣包的路由，提高了內(nèi)容查找速率和路由效率.

1 相關(guān)工作

目前，對MSN中社區(qū)檢測、內(nèi)容分發(fā)以及節(jié)點安全和隱私等方面的研究都取得了諸多成果[6-7]，并且基于內(nèi)容的MSN數(shù)據(jù)傳輸機制已成為新的研究熱點，但將ICN架構(gòu)引入具備DTN特征的MSN中以提升通信效率的相關(guān)研究尚處于起步階段.相關(guān)研究工作如下：

文獻[8]基于ICN提出了一種緩存感知型MSN路由方案，充分考慮節(jié)點間的社會關(guān)系、分布規(guī)律以及存儲內(nèi)容以建立路由和緩存機制，提升了信息傳遞率并降低了網(wǎng)絡(luò)開銷.文獻[9]利用啟發(fā)式的貪婪算法針對DTN中的節(jié)點緩存選擇進行優(yōu)化，實現(xiàn)DTN中內(nèi)容分發(fā)效益最大化，降低了時延并提高了內(nèi)容接收率.文獻[10]針對DTN提出一種基于代理的內(nèi)容檢索機制(agent-based content retrieval， ACR)，無需修改現(xiàn)有的ICN消息處理流程，具有靈活性和可操作性.文獻[11]將蟻群算法引入ICN，提出了一種啟發(fā)式的路由機制，該機制的特點在于通過檢索最接近的內(nèi)容副本實現(xiàn)對節(jié)點移動性的支持.文獻[12]將移動自組織網(wǎng)絡(luò)的自治特性和內(nèi)容中心網(wǎng)絡(luò)的底層框架相結(jié)合，提出了一種拓撲感知的內(nèi)容中心網(wǎng)絡(luò)協(xié)議，該協(xié)議采用基于多點中繼的分組轉(zhuǎn)發(fā)和主動內(nèi)容發(fā)現(xiàn)以及基于鄰居信息的洪泛控制算法，有效降低了傳輸時延和網(wǎng)絡(luò)開銷.文獻[13]基于社區(qū)結(jié)構(gòu)提出了一種以內(nèi)容為中心的發(fā)布訂閱服務(wù)策略(mobile community-based pubsub scheme, MOPS)，但MOPS中網(wǎng)關(guān)節(jié)點不僅要總結(jié)本地社區(qū)的興趣還要維護其他社區(qū)的內(nèi)容索引，成為了性能瓶頸.

本文提出的BIRI機制不僅通過高效的社區(qū)劃分提升了MSN的路由效率，而且引入ICN以內(nèi)容為中心的數(shù)據(jù)請求模式，并輔以節(jié)點的緩存機制，降低路由開銷與路由時延，同時緩解了MSN因節(jié)點動態(tài)性和鏈路不穩(wěn)定性導(dǎo)致的路由難題.

2 系統(tǒng)模型

本文的研究對象為分布式MSN，其網(wǎng)絡(luò)模型主要由節(jié)點以及節(jié)點之間的邊構(gòu)成.其中，每個節(jié)點都具有計算、存儲和轉(zhuǎn)發(fā)的功能，并維護5種表結(jié)構(gòu)：內(nèi)容存儲表(CS)、轉(zhuǎn)發(fā)信息表(FIB)、社會關(guān)系表(ST)以及低中心度節(jié)點摘要(LCD)、鄰居集內(nèi)容摘要(NCD).MSN在任意時刻的拓撲可抽象為無向賦權(quán)連通圖G=(V,E,W).其中，集合V代表移動節(jié)點，即持有移動設(shè)備的用戶，移動過程中在各自的通信范圍內(nèi)與其他節(jié)點相遇并建立連接；邊集合E則表示MSN中存在于節(jié)點間的社會關(guān)系；W是網(wǎng)絡(luò)中邊的權(quán)重，即節(jié)點間的社會關(guān)系強度.

本文的主要研究內(nèi)容是在MSN的網(wǎng)絡(luò)系統(tǒng)中引入ICN范型以完成社交節(jié)點之間的數(shù)據(jù)傳輸服務(wù)，專注于基于朋友關(guān)系的數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù).因此本文的數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)基于2條假設(shè)：

1) 使用本系統(tǒng)進行數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)的節(jié)點彼此愿意進行數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)，以交換服務(wù)的互惠方式作為轉(zhuǎn)發(fā)機制的激勵因素；

2) 參與本系統(tǒng)的用戶關(guān)系為朋友關(guān)系且進行實名驗證，不考慮惡意節(jié)點及由此產(chǎn)生的安全訪問問題.

3 社交度量

3.1 社會關(guān)系強度

定義1.節(jié)點間的社會關(guān)系強度[14].它為邏輯關(guān)系強度和物理關(guān)系強度的加權(quán)和，即：

SS(i,j)=α×SSL(i,j)+(1-α)×SSP(i,j)，α∈[0,1].

(1)

邏輯關(guān)系強度SSL(i,j)正相關(guān)于2個節(jié)點中內(nèi)容的累計新鮮度的Jaccard相關(guān)度,如式(2)(3)：

(2)

(3)

其中，Tcur為當(dāng)前時刻，R(δ,t)表示在時刻t數(shù)據(jù)中是否包含詞綴δ.

物理關(guān)系強度SSP(i,j)則為描述節(jié)點的移動性對節(jié)點間的社會關(guān)系強度的影響而設(shè)計.因節(jié)點在移動過程中只有相互接觸才具備直接的社會關(guān)系，因此在設(shè)計中無需限定節(jié)點的具體運動方式，通過考慮節(jié)點接觸的物理規(guī)律，包括頻率、平均接觸間隔等指標，可以得出如式(4)所示的定義式，其實際含義是i向j發(fā)送消息的平均轉(zhuǎn)發(fā)延遲的倒數(shù)，該值越大則平均轉(zhuǎn)發(fā)延遲越小，用戶關(guān)系越緊密.

(4)

其中，fij(t)表示在時刻t時距下一次相遇的時間間隔，如果i和j正在保持聯(lián)系，那么fij(t)=0，否則fij(t)=tnext-t.

3.2 中心度

節(jié)點的中心度[15]衡量節(jié)點在MSN中的消息擴散能力.因此中心度較高的節(jié)點具備較高的轉(zhuǎn)發(fā)效率.本文在緊密中心度[16]的基礎(chǔ)上進行修改，得出了如式(5)所示的中心度定義：

Cc(i)=β×CS(i)+(1-β)×CJ(i)，β∈[0,1],

(5)

其中，CS(i)為節(jié)點i與其所有相遇節(jié)點間的社會關(guān)系強度的均值，衡量i對消息的轉(zhuǎn)發(fā)能力，如式(6)；CJ(i)是簡氏公平系數(shù)[17]，用來評價社會關(guān)系分布對中心度的影響,如式(7)；β是兩者的權(quán)重系數(shù).

(6)

(7)

其中，Nm表示與i相遇的節(jié)點總數(shù).

4 基于BBO的社區(qū)發(fā)現(xiàn)算法

BBO算法將問題的候選解模擬為棲息地[18]，并模擬生物種群在棲息地之間的遷移，使得優(yōu)秀的影響因素得以共享，進而優(yōu)化棲息地；同時模擬生物變異以增強算法的自適應(yīng)能力.因此本文引入BBO算法并針對MSN的社區(qū)發(fā)現(xiàn)問題加以改進，用以優(yōu)化社區(qū)劃分的結(jié)果.表1給出了BBO數(shù)學(xué)模型與社區(qū)發(fā)現(xiàn)算法的對應(yīng)關(guān)系.

Table 1 Mapping Relationship Between BBO Mathematical Model and Community Detection Algorithm表1 BBO數(shù)學(xué)模型與社區(qū)發(fā)現(xiàn)算法的對應(yīng)關(guān)系

4.1 優(yōu)化目標

動態(tài)的MSN被表示為隨時間變化的圖序列，所以社區(qū)發(fā)現(xiàn)應(yīng)基于當(dāng)前時刻MSN的 “快照”進行，故任意時刻每個節(jié)點僅隸屬于1個社區(qū).動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)可以看作多目標優(yōu)化問題，應(yīng)同時優(yōu)化2個目標函數(shù)：

(8)

Maximize:NMI=

(9)

其中，Q是模塊度，定義為社區(qū)內(nèi)的邊占比和跨社區(qū)的邊占比之差的期望.Q越接近1代表社區(qū)內(nèi)聚越高，劃分結(jié)果越趨于合理.式(9)表示標準化互信息.其中，設(shè)H和I是2次劃分結(jié)果，Cij代表H中的社區(qū)i與I中的社區(qū)j中相同節(jié)點的數(shù)目，Ci是模糊矩陣Cconf中表示社區(qū)i的行向量的元素之和，Nnd是節(jié)點總數(shù).對相鄰時刻的2種劃分結(jié)果而言，NMI越大則兩者越接近，因此劃分結(jié)果越符合實際.

4.2 適應(yīng)度函數(shù)

適應(yīng)度表示棲息地質(zhì)量的優(yōu)劣，作為社區(qū)搜索的依據(jù)，其定義為

(10)

其中，xi表示棲息地個體，X表示種群，N是種群規(guī)模.記(f1,f2)為目標函數(shù)向量，其中Q=f1，NMI=f2，現(xiàn)有2個解xi和xj，當(dāng)且僅當(dāng)fk(xi)≤fk(xj)(?k=1,2)且fk(xi)

4.3 確定初始社區(qū)

初始時刻，節(jié)點沒有所隸屬的社區(qū)編號，無法計算Q和NMI.所以依據(jù)內(nèi)容相似度進行聚類，在每輪迭代中合并內(nèi)容相似度最大的節(jié)點對形成社區(qū)并將其視為新節(jié)點，然后重復(fù)該過程直至社區(qū)數(shù)目達到預(yù)設(shè)值.內(nèi)容相似度如式(11)：

(11)

其中，num為全網(wǎng)中的關(guān)鍵詞總數(shù)，內(nèi)容向量u=(u1,u2,…,unum)和v=(v1,v2,…,vnum)的分量表示對應(yīng)關(guān)鍵詞的內(nèi)容權(quán)重.

4.4 遷移操作

4.5 變異操作

變異策略會改變棲息地個體的質(zhì)量.當(dāng)某個分量進行變異操作時，尋找該分量代表的節(jié)點的最多鄰居節(jié)點所屬的社區(qū)，再從中隨機挑選1個節(jié)點作為突變值進行替換.這種基于社區(qū)結(jié)構(gòu)設(shè)計的變異策略考慮到了隨機替換的差異性可能對系統(tǒng)造成不同的影響，保證節(jié)點變異后所屬社區(qū)與最多的鄰居節(jié)點所屬社區(qū)一致，使得社區(qū)結(jié)構(gòu)不會發(fā)生過大的變化.

4.6 排重操作

對比所有個體的適應(yīng)度向量，若存在xi=xj，則初始化新向量xk，并用xk替換xj.該步驟是為了降低解向量的重復(fù)率，增加算法的廣度搜索范圍.

4.7 基于BBO的社區(qū)發(fā)現(xiàn)算法描述

算法1.基于BBO的社區(qū)發(fā)現(xiàn)算法.

輸入：T個時刻下的動態(tài)網(wǎng)絡(luò)DN={G1,G2,…,GT}；

輸出：每個時刻的社區(qū)結(jié)構(gòu)C={C1,C2,…,CT}.

① 初始化總時刻T、種群規(guī)模N、棲息地維度n、最大迭代次數(shù)Gmax；

③ fort=1 toTdo

⑤ whileG

⑥ 根據(jù)式(10)計算各棲息地的HSI；

⑦ 對X中所有個體根據(jù)HSI值升序排序；

⑧ if非支配個體數(shù)>N

⑨ 選取前N個個體作為新種群X′；

⑩ else

5 基于ICN的緩存機制

5.1 緩存決策

基于ICN思想，節(jié)點可以緩存數(shù)據(jù)以響應(yīng)后續(xù)的內(nèi)容請求.在本文設(shè)計的緩存決策中，設(shè)i和j分別是數(shù)據(jù)包途經(jīng)節(jié)點和請求節(jié)點，則i為j進行數(shù)據(jù)緩存的優(yōu)先級為

(12)

χ∈[0,1]，

其中，hop表示節(jié)點i與j間隔的跳數(shù)；k是節(jié)點j幫助i緩存的累計次數(shù)，代表j對i的貢獻值.顯然，j曾經(jīng)幫助i的次數(shù)越多，兩者間的距離越近，則以j為目的地的數(shù)據(jù)包被緩存的優(yōu)先級越高.

5.2 緩存替換

當(dāng)節(jié)點的緩存空間耗盡，需要緩存替換策略置換新數(shù)據(jù).依據(jù)訪問局部性原理，節(jié)點中的緩存內(nèi)容被其他節(jié)點請求的頻率會隨時間發(fā)生變化，一定時間內(nèi)，內(nèi)容被請求得越頻繁，代表其流行度越高，因此應(yīng)當(dāng)以內(nèi)容流行度作為替換依據(jù).

(13)

θ∈[0,1]，

(14)

6 社區(qū)感知型路由

6.1 社區(qū)內(nèi)路由機制

為了加快內(nèi)容檢索過程，節(jié)點首先應(yīng)進行內(nèi)容聚集，使得中心度高的節(jié)點掌握一定范圍內(nèi)中心度低的節(jié)點所能檢索的信息.具體方案是每個節(jié)點維護LCD和NCD這2種內(nèi)容摘要，NCD記錄了鄰居節(jié)點集中占比較高的內(nèi)容摘要，且初始時刻各節(jié)點將LCD初始化為NCD.內(nèi)容聚集過程就是各節(jié)點向相遇的中心度更高的節(jié)點發(fā)布各自的LCD，因此LCD概括了節(jié)點在比其中心度低的節(jié)點范圍內(nèi)所能檢索的信息內(nèi)容，信息內(nèi)容將逐步聚集到中心度高的節(jié)點上.LCD僅存儲內(nèi)容名字以起到“索引”的作用.

另外，為提高興趣包的轉(zhuǎn)發(fā)效率，本文采用k-均值聚類算法將社區(qū)內(nèi)的節(jié)點以中心度為指標進行層次劃分，使得各層中的中心度方差值最小，達到層內(nèi)緊湊、層間獨立的效果.當(dāng)進行數(shù)據(jù)請求時，興趣包僅向更高層次的節(jié)點轉(zhuǎn)發(fā)，有效減少低效率的轉(zhuǎn)發(fā)次數(shù).

當(dāng)網(wǎng)絡(luò)工作時，興趣包的轉(zhuǎn)發(fā)策略為：內(nèi)容請求者攜帶興趣包，若遇到比自己且比上次轉(zhuǎn)發(fā)的節(jié)點的中心度層次更高的節(jié)點時才轉(zhuǎn)發(fā)興趣包.當(dāng)某節(jié)點接收到興趣包時，若本地緩存中存在對應(yīng)條目，則返回數(shù)據(jù)包以響應(yīng)請求者；否則，查找LCD，若其中有匹配信息，就根據(jù)ST將興趣包轉(zhuǎn)發(fā)到內(nèi)容源，否則繼續(xù)按照上述規(guī)則轉(zhuǎn)發(fā)興趣包.

為了避免因存儲-轉(zhuǎn)發(fā)模式的延遲產(chǎn)生的路由回路的影響，每個興趣包都設(shè)有生存時間(time-to-live， TTL).且針對存在回路的情況，設(shè)計了備用興趣包轉(zhuǎn)發(fā)策略，即中繼節(jié)點將興趣包發(fā)送給比自己中心度層次高的節(jié)點即可.

當(dāng)節(jié)點將數(shù)據(jù)包返回給請求者時，對應(yīng)的數(shù)據(jù)包轉(zhuǎn)發(fā)策略為：數(shù)據(jù)包攜帶者以與目的節(jié)點的社會關(guān)系強度為判據(jù)，對比自身與每個接觸的節(jié)點，僅當(dāng)后者判據(jù)值更大才將其作為下一跳節(jié)點進行轉(zhuǎn)發(fā).

6.2 社區(qū)間路由機制

若社區(qū)內(nèi)不存在所請求的內(nèi)容信息，則需要設(shè)計合適的“橋節(jié)點”選擇策略.在本文中，橋節(jié)點負責(zé)跨社區(qū)的興趣包的轉(zhuǎn)發(fā)，向其他社區(qū)內(nèi)的節(jié)點進行內(nèi)容請求.橋節(jié)點包含2種興趣內(nèi)容表：1)內(nèi)部興趣表(internal interest table， IIT)，記錄本社區(qū)的興趣內(nèi)容列表；2)外部興趣表(external interest table，EIT)，記錄它能到達的外部社區(qū)的興趣內(nèi)容列表.簇頭節(jié)點(即最高中心度層次內(nèi)的節(jié)點序列)定期向橋節(jié)點發(fā)送本社區(qū)的興趣列表，以便橋節(jié)點及時更新IIT.當(dāng)不同社區(qū)的橋節(jié)點相遇，則相互發(fā)送IIT以更新各自的EIT.

本文用社區(qū)隸屬度作為選取橋節(jié)點的標準.節(jié)點i在其所屬社區(qū)C的社區(qū)隸屬度CDi按照式(15)計算：

CDi=min{SS(i,j),i∈VC∧j∈VC}，

(15)

其中VC是社區(qū)C的節(jié)點集合.CDi越小代表i與隸屬社區(qū)間聯(lián)系越弱，與其他社區(qū)內(nèi)節(jié)點相遇的概率越高，因此越適合作為橋節(jié)點進行跨社區(qū)的路由.

綜上，社區(qū)間的路由策略可概括為：簇頭節(jié)點收到興趣包后，若內(nèi)容存儲表CS和LCD均無法與興趣包匹配時，首先計算各節(jié)點的CDi并選擇該值最小的節(jié)點序列作為橋節(jié)點集，簇頭節(jié)點向所有橋節(jié)點發(fā)送興趣包，僅當(dāng)橋節(jié)點的EIT中存在對應(yīng)的匹配項時才進行轉(zhuǎn)發(fā)，否則直接將其丟棄.

6.3 社區(qū)感知型路由算法描述

算法2.社區(qū)感知型路由算法.

輸出：消息的轉(zhuǎn)發(fā)路徑.

① 更新節(jié)點i，更新其生存時間nTTL；

② if 節(jié)點i的緩沖區(qū)中無待轉(zhuǎn)發(fā)的興趣包

④ end if

⑤ form∈Interests_MSGdo*遍歷節(jié)點i的緩沖區(qū)中所有興趣包*

⑥ if節(jié)點i不是本社區(qū)簇頭節(jié)點

⑦ ifm的nTTL>0

⑩ 執(zhí)行社區(qū)內(nèi)興趣包備用轉(zhuǎn)發(fā)策略；

7 實驗與結(jié)果

本文基于機會網(wǎng)絡(luò)環(huán)境[19](opportunistic network environment, ONE)這一平臺對BIRI機制進行仿真實現(xiàn)，模擬了在分布式MSN中的消息轉(zhuǎn)發(fā)過程.相關(guān)參數(shù)如表2所示.使用Infocom 2006數(shù)據(jù)集模擬MSN節(jié)點，包含節(jié)點的真實運動特征.將BIRI路由機制分別與Epidemic Routing[20]，Bubble Rap Routing[21]，SCAN[22]這3種路由算法進行對比.其中，Epidemic類似于病毒傳染，采取基于洪泛思想的多副本路由；Bubble Rap則是基于社區(qū)結(jié)構(gòu)的單副本路由機制；SCAN路由則是一種可擴展的內(nèi)容感知路由機制，可以通過掃描附近的節(jié)點內(nèi)的副本提高投遞率.3種對比指標分別為投遞率、平均時延和網(wǎng)絡(luò)開銷比率.

Table 2 The Configuration of Simulation表2 仿真配置

7.1 投遞率

投遞率代表到達目的節(jié)點的消息比例.如圖1所示，無論是所請求的內(nèi)容在社區(qū)內(nèi)的情況還是既包括社區(qū)內(nèi)又包括社區(qū)外的混合情況，BIRI在該指標上都僅次于Epidemic機制，這是因為Epidemic采取洪泛思想，大大提高了投遞率.與另外2種路由機制相比，BIRI機制在進行路由時不僅考慮社交關(guān)系、社區(qū)結(jié)構(gòu)，還能迅速匹配請求內(nèi)容信息，使得內(nèi)容檢索不僅速度快而且準確率高，提升了投遞率.

Fig. 1 Delivery rate comparison on BIRI, Epidemic, Bubble Rap and SCAN圖1 4種算法的投遞率比較

7.2 平均時延

Fig. 2 Average latency comparison on BIRI, Epidemic, Bubble Rap and SCAN圖2 4種算法的平均時延比較

平均時延體現(xiàn)了路由過程的平均時長.如圖2所示，BIRI在該指標上優(yōu)于SCAN和Bubble Rap.由于SCAN過度依賴附近節(jié)點的內(nèi)容副本且對網(wǎng)絡(luò)的間歇特性缺乏考慮,而Bubble Rap忽視了社區(qū)內(nèi)的可用內(nèi)容緩存的作用，分別導(dǎo)致了SCAN和Bubble Rap平均路由時間的增加.而Epidemic因其洪泛特性，平均時延比BIRI更低.另外，相對于圖2(a)，圖2(b)中BIRI的路由延遲明顯增大，這是因為不同社區(qū)間進行轉(zhuǎn)發(fā)時需要借助橋節(jié)點，增加了路由時延.

7.3 網(wǎng)絡(luò)開銷比率

Fig. 3 Network overhead ratio comparison on BIRI, Epidemic, Bubble Rap and SCAN圖3 4種算法的開銷比率比較

網(wǎng)絡(luò)開銷比率反映了消息在路由過程中對緩存、帶寬以及能量等網(wǎng)絡(luò)資源的消耗，定義為消息轉(zhuǎn)發(fā)的總次數(shù)與成功送達的消息之差除以消息轉(zhuǎn)發(fā)總次數(shù).如圖3所示，BIRI機制的網(wǎng)絡(luò)開銷比率僅高于Bubble Rap算法.因為BIRI在社區(qū)內(nèi)路由中劃分聚類層次減少了無效的轉(zhuǎn)發(fā)次數(shù)，且選取合適的橋節(jié)點負責(zé)跨社區(qū)的路由，這些策略不僅能保證準確地找到內(nèi)容提供者，而且在一定程度上控制了網(wǎng)絡(luò)開銷.Bubble Rap網(wǎng)絡(luò)開銷較小則是因為相比于BIRI的多副本消息傳輸，Bubble Rap采用單副本消息傳輸，減小了消息副本數(shù)量，相應(yīng)地降低了網(wǎng)絡(luò)開銷代價.

8 結(jié) 論

本文以MSN網(wǎng)絡(luò)為研究對象，充分挖掘MSN中復(fù)雜的社交關(guān)系和社區(qū)結(jié)構(gòu)，引入ICN以內(nèi)容為中心的思想，運用網(wǎng)絡(luò)圖論、BBO算法、k-均值聚類算法等，全面深入地研究了基于ICN的MSN社區(qū)感知型路由機制，旨在滿足MSN用戶多樣的內(nèi)容需求并提高MSN動態(tài)網(wǎng)絡(luò)結(jié)構(gòu)中的路由效率.通過對比實驗和分析可知，本文提出的BIRI機制在投遞率、平均延遲和路由開銷比率這3項指標上相比于對比算法表現(xiàn)出了較好的綜合性能，是ICN與MSN相結(jié)合的初步探索與嘗試.但BIRI機制仍存在改進空間，研究BBO算法中不同變異策略對性能的影響并加以改進，以及在現(xiàn)實背景下對其實用性和安全性進行驗證和優(yōu)化是今后研究工作的重點.