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

涂盼鵬 王興偉 李 婕 黃 敏

1(東北大學計算機科學與工程學院 沈陽 110169)2(復雜網絡系統安全保障技術教育部工程研究中心(東北大學) 沈陽 110169)3(東北大學信息科學與工程學院 沈陽 110819)

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

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

針對上述問題，本文充分利用MSN中的社交關系和社區結構，引入ICN以內容為中心的思想，基于網絡圖論對生物地理優化(biogeography-based optimization, BBO)算法進行改進，以此為基礎設計了一種支持信息中心范型的BBO啟發式MSN路由算法(BBO-inspired MSN routing algorithm with information-centric paradigm support, BIRI).

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

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

2) 基于節點之間的內容相似度以及網絡動態特性改進了BBO算法，優化MSN中的社區劃分過程;

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

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

1 相關工作

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

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

本文提出的BIRI機制不僅通過高效的社區劃分提升了MSN的路由效率，而且引入ICN以內容為中心的數據請求模式，并輔以節點的緩存機制，降低路由開銷與路由時延，同時緩解了MSN因節點動態性和鏈路不穩定性導致的路由難題.

2 系統模型

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

本文的主要研究內容是在MSN的網絡系統中引入ICN范型以完成社交節點之間的數據傳輸服務，專注于基于朋友關系的數據轉發服務.因此本文的數據轉發服務基于2條假設：

1) 使用本系統進行數據轉發服務的節點彼此愿意進行數據轉發服務，以交換服務的互惠方式作為轉發機制的激勵因素；

2) 參與本系統的用戶關系為朋友關系且進行實名驗證，不考慮惡意節點及由此產生的安全訪問問題.

3 社交度量

3.1 社會關系強度

定義1.節點間的社會關系強度[14].它為邏輯關系強度和物理關系強度的加權和，即：

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

(1)

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

(2)

(3)

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

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

(4)

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

3.2 中心度

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

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

(5)

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

(6)

(7)

其中，Nm表示與i相遇的節點總數.

4 基于BBO的社區發現算法

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

Table 1 Mapping Relationship Between BBO Mathematical Model and Community Detection Algorithm表1 BBO數學模型與社區發現算法的對應關系

4.1 優化目標

動態的MSN被表示為隨時間變化的圖序列，所以社區發現應基于當前時刻MSN的 “快照”進行，故任意時刻每個節點僅隸屬于1個社區.動態網絡社區發現可以看作多目標優化問題，應同時優化2個目標函數：

(8)

Maximize:NMI=

(9)

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

4.2 適應度函數

適應度表示棲息地質量的優劣，作為社區搜索的依據，其定義為

(10)

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

4.3 確定初始社區

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

(11)

其中，num為全網中的關鍵詞總數，內容向量u=(u1,u2,…,unum)和v=(v1,v2,…,vnum)的分量表示對應關鍵詞的內容權重.

4.4 遷移操作

4.5 變異操作

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

4.6 排重操作

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

4.7 基于BBO的社區發現算法描述

算法1.基于BBO的社區發現算法.

輸入：T個時刻下的動態網絡DN={G1,G2,…,GT}；

輸出：每個時刻的社區結構C={C1,C2,…,CT}.

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

③ fort=1 toTdo

⑤ whileG

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

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

⑧ if非支配個體數>N

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

⑩ else

5 基于ICN的緩存機制

5.1 緩存決策

基于ICN思想，節點可以緩存數據以響應后續的內容請求.在本文設計的緩存決策中，設i和j分別是數據包途經節點和請求節點，則i為j進行數據緩存的優先級為

(12)

χ∈[0,1]，

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

5.2 緩存替換

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

(13)

θ∈[0,1]，

(14)

6 社區感知型路由

6.1 社區內路由機制

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

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

當網絡工作時，興趣包的轉發策略為：內容請求者攜帶興趣包，若遇到比自己且比上次轉發的節點的中心度層次更高的節點時才轉發興趣包.當某節點接收到興趣包時，若本地緩存中存在對應條目，則返回數據包以響應請求者；否則，查找LCD，若其中有匹配信息，就根據ST將興趣包轉發到內容源，否則繼續按照上述規則轉發興趣包.

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

當節點將數據包返回給請求者時，對應的數據包轉發策略為：數據包攜帶者以與目的節點的社會關系強度為判據，對比自身與每個接觸的節點，僅當后者判據值更大才將其作為下一跳節點進行轉發.

6.2 社區間路由機制

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

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

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

(15)

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

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

6.3 社區感知型路由算法描述

算法2.社區感知型路由算法.

輸出：消息的轉發路徑.

① 更新節點i，更新其生存時間nTTL；

② if 節點i的緩沖區中無待轉發的興趣包

④ end if

⑤ form∈Interests_MSGdo*遍歷節點i的緩沖區中所有興趣包*

⑥ if節點i不是本社區簇頭節點

⑦ ifm的nTTL>0

⑩ 執行社區內興趣包備用轉發策略；

7 實驗與結果

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

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

7.1 投遞率

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

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種算法的平均時延比較

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

7.3 網絡開銷比率

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

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

8 結 論

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