基于朋友圈和節點感知的內容中心MSN 路由機制*

張卜聆，王興偉+，李 婕，易 波，黃 敏

1.東北大學 計算機科學與工程學院，沈陽110169

2.東北大學 信息科學與工程學院，沈陽110819

1 引言

隨著智能手機等移動設備的普及，移動社交網絡（mobile social network，MSN）發展迅速，其相關技術成為近年來的研究熱點。當移動節點在應用場景中以自組織形式進行數據傳輸服務時，移動社交網絡是一種將網絡與節點社會特性相結合的時延容忍網絡[1]。由于節點的移動性使得端到端的路由呈現間歇性特點，導致數據傳輸時延、投遞率等方面受到了限制，因此如何設計高效的內容分發和數據傳輸方式就成為現階段研究的重點和難點。

近幾年，大部分互聯網內容以密集的信息形式存在，如視頻、音頻、文件流等，據思科（Cisco）發布的可視化網絡指數預測報告可知，截至2017 年，全世界的互聯網用戶數量已達34 億，全球移動數據流量將在2017 年至2022 年間增長7 倍[2]。互聯網的研究方向逐漸趨于高效率、大規模、更具安全性的網絡信息的接收與轉發，TCP/IP 在網絡的安全性、可靠性、移動性、可擴展性以及路由策略等方面漸漸顯現出了不足之處。信息中心網絡（information-centric networking，ICN）不同于現有的支持端到端通信的TCP/IP 互聯網體系結構，它是通過使用內容標識符將內容和位置分離[3]，形成松散耦合的通信模式，著重于內容本身以及數據的自有屬性，能很好地支持移動性，其天然的網內緩存機制，能夠大大降低網絡負載，實現高效的數據分發。但是，將信息中心網絡架構引入移動社交網絡中以解決端到端通信難問題的研究，還處于起步階段，主要研究現狀如下：

文獻[4]提出了一種選擇性緩存方法和概率轉發方法，以降低緩存冗余和最小化獲取內容的預期成本。同時，提供了一種可擴展的方法來維護路由器內緩存內容的路由信息。文獻[5]設計和分析了兩種轉發方式：盲轉發和提供者感知轉發。通過減少興趣包和數據包的數量，提供者感知轉發可以在很大程度上優于盲轉發方案，尤其是在效率方面。但在特定應用場景下，簡單的盲轉發是最佳解決方案。文獻[6]基于節點興趣的社會規律性和距離度量分別設計了興趣包和數據包的路由方案，同時提出了基于節點友好度量的網絡緩存方案降低傳輸時延。文獻[7]考慮了用戶的流動性和視頻的流行程度提出了基于ICN 的移動視頻在5G 網絡中的緩存方法，利用移動性來減少頻繁切換帶來的檢索延遲。文獻[8]通過對車輛的社區相似度和隱私等級進行評價，設計了一種動態概率緩存方案。文獻[9]考慮了節點的當前位置和節點的剩余能量，以改善數據傳輸的過程中網絡性能。同時基于節點間的距離設計高速緩存策略，以減少未來請求內容的檢索時間。如何高效使用ICN 網內緩存空間對于快速檢索和準確定位內容至關重要，文獻[10-11]利用軟件定義網絡（software defined network，SDN）的集中控制能力將內容信息進行集中管理。此外，文獻[10]提出的ICN 緩存內容定位機制聯合使用布隆過濾器和壓縮感知可有效地表示緩存的內容。文獻[11]提出了一種基于最大樹的社區劃分方案，根據劃分的結果設計了社區內和社區間路由機制。文獻[12]根據信息項需求和網絡的緩存功能制定了一種緩存感知路由方案，用最小的傳輸成本計算路徑。文獻[13]表明社區家庭是傳播信息的重要因素，通過使用社區家庭能更快地傳播消息。

以上緩存路由算法雖然在不同方面具有一定性能上的優勢，但是在移動節點劃分時，沒有考慮節點緩存內容的類型，而且在數據傳輸時缺乏對內容源、目的地的感知。基于以上問題，根據節點的實際運動情況，提出了基于朋友圈和節點感知的內容中心MSN 路由機制。本文的研究工作主要包括以下幾點：明確了節點模型的功能表，使節點具有一定的感知能力；利用節點緩存內容相似性以及節點間關系強度構造朋友圈；根據朋友節點的關系，提出相適應的緩存機制以維護朋友圈；設計基于節點感知的路由算法；利用NS3（network simulator 3）[14]對提出的路由機制進行仿真實現，并與其他算法進行對比分析。

2 問題描述

2.1 網絡模型

網絡由節點和節點之間的邊組成，網絡模型G(V,E)表示無向連通圖，其中V是具有存儲、轉發和處理能力的節點集合，表示網絡中的移動設備；E是邊集合，表示網絡中的移動設備之間存在的鏈路。

2.2 節點模型

每個移動設備需要維護5 個表：內容存儲庫（content store，CS）、轉發信息庫（forwarding information base，FIB）、未決興趣表（pending interest table，PIT）[2]、已決興趣表（settled interest table，SIT）和朋友關系表（friendship table，FST）。其中，CS 作為存儲部件，暫存內容對象及其名字的映射。FIB 記錄了節點間的轉發規則，是路由轉發的主要依據。對于已經轉發出去但對應的數據包未返回的興趣包，PIT 記錄興趣包對應的接口信息。設計的SIT 記錄PIT 中已經請求到的數據包所對應的興趣包的名字前綴與請求該內容的節點ID，使節點具有一定的感知能力。節點的社交性通過在ICN 中增添FST 體現，該表記錄本地節點ID、與鄰居節點的關系以及鄰居節點的緩存內容類型，是興趣包路由至最大概率目的地的重要依據。

3 算法設計

3.1 社交度量

在MSN 中，因為節點具有移動性，使得網絡拓撲一直在變化，因此節點之間難以存在穩定的路徑。為了促進信息交換，選用交換頻次、聯系時長和緩存相似性衡量節點之間的社會關系。同時，考慮到節點的移動特性，結合了鏈路延遲、延遲抖動、阻塞率等因素在消息路由過程中選擇合理的中繼節點，實現高效路由。

3.1.1 交換頻次

其中，Ci,j表示節點i和j互換內容的頻率，Exi,j表示節點i向j提供內容的次數，Exi表示節點i向所有節點交換內容的次數。

3.1.2 聯系時長

其中，CTi,j表示節點i和j之間的聯系時長，表示節點i與中間節點k1的聯系時長，∑cti表示節點i與其他節點的聯系時長。

3.1.3 緩存相似度

其中，節點i和節點j的內容條目的交集即為相似性的內容。CCsimi,j表示節點i和j緩存內容的相似程度，CEi表示節點i的內容條目。

3.1.4 數據交換概率

利用交換頻次、聯系時長以及緩存相似性社交度量來衡量節點之間的聯系強度。

其中，wi,j表示節點i和j之間的聯系強度。

對于i和j之間的鏈路可靠程度，還額外考慮鏈路延遲de、延遲抖動dejit、阻塞率blo等情況。因此，節點i、j之間的鏈路可靠程度計算公式如下：

其中，α1+α2+α3+α4=1，Rei,j體現了節點i、j之間進行數據交換的可靠程度，由此可得節點i向節點j發送興趣包的概率P(i,j)：

3.1.5 節點度中心性

其中，Cd(v)表示節點v的度中心性，用于選舉簇頭節點。度中心性越大，越適合選為轉發節點進行信息的傳遞。如果節點i和j之間存在連接，那么link(vi,vj)=1。為了簡化，接下來用Aij等價替換link(vi,vj)。

3.1.6 節點相似度

存在多個度中心性高的節點時，通過評價節點的相似度進一步甄選簇頭節點。dij為節點i和j的相似度。若兩節點相連，Aij=1，否則為0。dij的值越小，則兩節點的相似度越高。

3.1.7 節點與朋友圈關聯度

當節點與朋友圈內節點具有相似的興趣愛好時，說明節點與該朋友圈之間具有關聯度，用Ri,com表示。其中，m為朋友圈節點總數，r=(vi,vk)為兩節點之間的關聯度。當緩存相似度達到一定閾值時，r=1；否則為0。

3.1.8 朋友圈特征熱度值

3.2 朋友圈構造算法

在MSN 中，具有相似的緩存內容通常聯系程度密切，易形成一個朋友圈。根據這個特點，本文基于緩存內容相似度和節點中心性構造朋友圈。先選舉度中心性高且相似度大的節點作為簇頭節點，然后圍繞簇頭節點自底向上聚類朋友圈節點，直至網絡所有節點劃分完畢，形成不同的朋友圈。整個劃分過程偽代碼如下：

3.3 緩存機制

3.3.1 朋友圈的緩存特征

在MSN 中，朋友圈的結構受節點社會關系的影響。考慮到節點依據緩存內容構造朋友圈，對CS 的緩存置換策略引入了內容熱度和多樣性可以維護朋友圈的穩定性。依據二八原則，熱度內容即節點感興趣的內容在節點的CS 中占據主導地位，而緩存非熱度內容以保證朋友圈緩存內容的多樣性。

其中，n為節點內熱度內容類型的數量，可實驗測定。

3.3.2 節點緩存策略

設計中的節點有一定的概率對熱度內容進行緩存，這里采用式（4）聯系強度來衡量路徑上節點是否緩存該內容，這樣做的好處在于聯系越緊密的節點，其興趣越相似，則滿足朋友節點請求該內容的命中率越大。而對于非熱度內容，僅緩存至請求節點，以減少在路徑上不必要內容緩存而造成資源浪費。同時，由于朋友節點越來越具有相似性，鄰居節點間的緩存相似度需要控制在閾值之下：

3.3.3 節點置換策略

置換策略分為兩種情況：當節點的緩存區已滿時，需要采用適當的策略置換緩存內容；當兩個節點緩存相似度超過閾值時，需要置換熱度緩存內容以降低相似度。采用基于內容熱度和多樣性相結合的緩存置換策略，可有效提高CS 命中率。

熱度Heat為CS 緩存條目在歷史時間段的熱度值與當前時間段熱度值的加權和，即：

其中，μ+λ=1，當需要調節緩存相似的節點時，考慮節點的熱度內容向與其緩存內容相似性最低的鄰居節點轉移。當節點對的緩存相似性均低于閾值時，調節結束。

3.4 路由機制

基于朋友圈和節點感知的內容中心MSN 路由機制主要解決的是興趣包在多跳情況下的路由問題。先在朋友圈內進行內容的檢索，如若CS、SIT、PIT、FIB 表中未檢索到相關內容，則表明朋友圈內沒有所請求的內容。此時，將興趣包發給簇頭節點，以轉向全局控制器進行外部路由。興趣包在朋友圈內路由過程偽代碼如下所示：

依據全局控制器對全局緩存內容信息的掌握情況，請求節點可以獲取對目的節點ID 的感知。當請求節點接收到控制信息后，將目的節點的ID 加入興趣包路由路徑中，從而使興趣包具有感知能力，找到目的節點的緩存內容。興趣包在朋友圈間路由過程偽代碼如下所示：

考慮到網絡的動態變化，需要對傳統的ICN 數據包的名字前綴加以改進，即數據包返回時，興趣包記錄的路徑信息會被依次添加到內容名的前面，使數據包具有感知能力。當沿原路徑的方向返回時，若某條鏈路處于斷開狀態，計算兩節點的其余通路，并選取與請求者FST 關系度高的作為路由線路，依此路由直至請求者。

4 仿真與結果分析

4.1 仿真環境及場景設置

設計的路由機制通過NS3 仿真平臺進行仿真實現，使用Infocom 2006 數據集（Infocom06 dataset，http://www.crawdad.org/cambridge/haggle/20090529/），仿真場景設置如表1 所示，表中TTL 表示生存時間（time to live）。

Table 1 Configuration of simulation表1 仿真配置

4.2 性能對比

將提出的基于朋友圈和節點感知的內容中心MSN 路由機制（friend circle and node awareness based content centric MSN routing mechanism，FACMR）與基于ICN 的緩存感知路由機制（cache-aware routing in ICN，CAR）[12]、基于社區對目的零認知的MSN 多拷貝路由機制（home-based multi-copy routing with zeroknowledge about destination in mobile social network，HBMRZ）[13]從緩存置換率、誤包數、平均路由時延和投遞開銷方面進行性能評價。

4.2.1 緩存置換率

如圖1 所示，設置緩存區大小分別為50 MB 和500 MB，FACMR 在緩存空間足夠大的時候能夠保證緩存信息的資源兼具多樣性和穩定性，取得較低的緩存置換率。HBMRZ 的緩存置換率相對偏高是因為該算法在第一階段擴散內容的副本。而CAR 算法通過全局資源的管理使資源合理分布。

Fig.1 Cache replacement rate圖1 緩存置換率

4.2.2 誤包數

如圖2 所示，HBMRZ 算法誤包數最高，是因為在MSN 中，HBMRZ 包傳遞具有很大的時延。而FACMR 算法中，包的傳遞均是在具有邏輯連接的朋友節點上進行，不僅有更大的幾率獲得內容，同時在TTL 生存周期內保證有較大幾率完成包的傳遞。而CAR 算法，由于需要全局資源的協調控制，始終保持消耗資源最少，但相應的路由時延增加會導致較高的誤包數。

Fig.2 Number of packet loss圖2 誤包數

4.2.3 路由開銷

如圖3 所示，三者之間在路由開銷指標略有差異，但不是很明顯，FACMR 算法在路由開銷上與對比算法基本相同，能夠保證性能的穩定性。

Fig.3 Routing overhead圖3 路由開銷

4.2.4 平均路由時延

如圖4 所示，HBMRZ 算法時延較大是因為節點連接的隨機性，包的傳遞也具有隨機性。而FACMR算法和CAR 算法是基于ICN 設計，使得節點的相互聯系更加緊密，因此平均路由時延均低于HBMRZ 算法。但由于CAR 算法用時間換取網絡開銷，因此平均路由時延高于FACMR 算法。

Fig.4 Average routing delay圖4 平均路由時延

5 結束語

本文針對ICN 與MSN 相結合的網絡環境，提出了基于朋友圈和節點感知的內容中心MSN 路由機制。在該機制中，利用節點中心性以及緩存內容的類型進行朋友圈構造。同時提出了相適應的節點緩存、置換策略，進行朋友圈維護。設計了節點感知型路由算法，能夠依據圈內的朋友關系實現高效路由。如何更深層次挖掘節點的社會關系，利用圈內關系來提高數據分發性能是下一步的研究方向和重點。