張建偉，崔夢(mèng)夢(mèng)，蔡增玉

（1.鄭州輕工業(yè)大學(xué) 軟件學(xué)院；2.鄭州輕工業(yè)大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，河南 鄭州 450002）

0 引言

傳統(tǒng)基于TCP/IP 的網(wǎng)絡(luò)架構(gòu)不能很好地滿(mǎn)足日益增加的網(wǎng)絡(luò)流量需求［1-4］，用戶(hù)在請(qǐng)求內(nèi)容時(shí)，往往不知道內(nèi)容提供者，從而造成無(wú)法將目的地址嵌入到興趣包中進(jìn)行轉(zhuǎn)發(fā)的問(wèn)題。以?xún)?nèi)容為中心的網(wǎng)絡(luò)（Content Centric Network，CCN）從提供商驅(qū)動(dòng)的端到端通信模式轉(zhuǎn)換到了興趣驅(qū)動(dòng)的內(nèi)容檢索通信模式，這使得CCN 不能像TCP/IP那樣根據(jù)源、目的IP 地址采用逐跳返回的方法進(jìn)行路由，因此，怎樣設(shè)計(jì)更高效的CCN 路由方案是CCN 網(wǎng)絡(luò)架構(gòu)亟需解決的一個(gè)問(wèn)題。近年來(lái)，CCN 路由機(jī)制得到了廣泛的研究［5-7］，為解決CCN 的可擴(kuò)展性和大規(guī)模部署問(wèn)題，有兩個(gè)較為有效的方案：一是與SDN 的結(jié)合［8-10］，因?yàn)镾DN作為未來(lái)互聯(lián)網(wǎng)的一種獨(dú)特的模型，實(shí)現(xiàn)了控制平面與數(shù)據(jù)平面相分離；另一個(gè)方案是進(jìn)行社區(qū)劃分［11-14］，但在進(jìn)行社區(qū)劃分時(shí)社區(qū)的大小和內(nèi)容很難確定，給社區(qū)劃分帶來(lái)了新的挑戰(zhàn)。

現(xiàn)有若干社區(qū)發(fā)現(xiàn)算法，如Girvan 等［15］的基于邊介數(shù)的分裂GN 算法，每次刪除邊介數(shù)最大的邊，直到所有的邊都被移除；Blondel 等［16］提出模塊度最大化的louvain 算法，將每個(gè)點(diǎn)看作獨(dú)立社區(qū)，計(jì)算社區(qū)折疊后社區(qū)間和社區(qū)內(nèi)的連邊權(quán)重，直到最后合為一個(gè)社區(qū)；Raghavan 等［17］提出標(biāo)簽傳播算法（LPA），相比前兩種算法，該算法具有線(xiàn)性的時(shí)間復(fù)雜度，適合用于大型網(wǎng)絡(luò)中的社區(qū)劃分。

LPA 算法的核心思想為：給途中每個(gè)節(jié)點(diǎn)分配標(biāo)簽值，以代表節(jié)點(diǎn)所在的社區(qū)。找出鄰居節(jié)點(diǎn)中標(biāo)簽傳播值最大的節(jié)點(diǎn)（最大值不唯一時(shí)，隨機(jī)選擇一個(gè)），將該節(jié)點(diǎn)加入該社區(qū)，并更新節(jié)點(diǎn)的標(biāo)簽傳播值，當(dāng)節(jié)點(diǎn)標(biāo)簽傳播值不再變化時(shí)，停止迭代；否則重復(fù)上述步驟。

在傳統(tǒng)LPA 算法中，初始標(biāo)簽值的確定具有隨機(jī)性，這使劃分好的社區(qū)存在穩(wěn)定性差和準(zhǔn)確性低的缺點(diǎn)，為解決該問(wèn)題，很多學(xué)者提出了改進(jìn)措施。Luo 等［18］通過(guò)優(yōu)化目標(biāo)函數(shù)來(lái)提升社區(qū)劃分的質(zhì)量，但LPA 的穩(wěn)定性較差；張猛等［19］通過(guò)計(jì)算標(biāo)簽重要性，改變標(biāo)簽更新序列，但未考慮節(jié)點(diǎn)之間的相似性；Song 等［20］通過(guò)計(jì)算節(jié)點(diǎn)相似性，改變標(biāo)簽更新序列，但未考慮節(jié)點(diǎn)的重要性。

目前，LPA 算法在社區(qū)劃分實(shí)際應(yīng)用中仍存在不足之處，為進(jìn)一步提高社區(qū)劃分的穩(wěn)定性和準(zhǔn)確性，本文提出一種基于節(jié)點(diǎn)興趣相似度和社交影響力的CCN 社區(qū)劃分方法（SI-LPA），綜合考慮節(jié)點(diǎn)相似性和重要性對(duì)于社區(qū)的影響，并引入特征向量中心性?xún)?yōu)化初始社區(qū)結(jié)構(gòu)，使其劃分的社區(qū)更具有代表性與穩(wěn)定性。

1 SI-LPA算法

1.1 興趣相似度

興趣權(quán)重表示節(jié)點(diǎn)對(duì)一個(gè)興趣字段的歷史請(qǐng)求次數(shù)，用Wik表示節(jié)點(diǎn)vi對(duì)興趣字段fk的興趣權(quán)重，當(dāng)vi生成一個(gè)包含fk的請(qǐng)求時(shí)：

節(jié)點(diǎn)的興趣相似度為兩個(gè)節(jié)點(diǎn)的興趣集合中相同興趣字段的興趣權(quán)重集合對(duì)應(yīng)的Tanimoto系數(shù)相關(guān)性。假設(shè)節(jié)點(diǎn)vi與vj相同的興趣字段個(gè)數(shù)為p，則節(jié)點(diǎn)vi與vj的興趣相似度為：

1.2 節(jié)點(diǎn)社交影響力

節(jié)點(diǎn)之間的社交距離與通過(guò)這兩點(diǎn)時(shí)間的數(shù)據(jù)流量成正比，與兩節(jié)點(diǎn)間距離成反比，且與節(jié)點(diǎn)的度有關(guān)。

其中，dij為流經(jīng)節(jié)點(diǎn)vi與vj數(shù)據(jù)流量的總和，Γ（i）與Γ（j）分別為節(jié)點(diǎn)vi與vj鄰居節(jié)點(diǎn)的集合，ki與kj分別為節(jié)點(diǎn)vi與vj的度，dis（i，j）為節(jié)點(diǎn)vi與vj之間的歐氏距離。

1.3 特征向量中心性

用A=（eij）n×n表示無(wú)向圖對(duì)應(yīng)的鄰接矩陣，X=（x1，x2，…，xn）表示該矩陣的一個(gè)特征向量。對(duì)于任意路由節(jié)點(diǎn)vi，其對(duì)應(yīng)的特征向量值為xi，λ為鄰接矩陣A的特征向量X對(duì)應(yīng)的特征值，則：

利用上述公式，當(dāng)對(duì)特征向量值進(jìn)行多次迭代，其值達(dá)到穩(wěn)態(tài)時(shí)，此時(shí)的xi為節(jié)點(diǎn)vi對(duì)應(yīng)的特征向量中心性。為方便計(jì)算，在區(qū)間（0，1）內(nèi)對(duì)特征向量中心性進(jìn)行標(biāo)準(zhǔn)化，用表示標(biāo)準(zhǔn)化后特征向量中心性的值，則：

1.4 標(biāo)簽傳播值

對(duì)n個(gè)特征向量中心性的值降序排列，選擇其中前k個(gè)值對(duì)應(yīng)的節(jié)點(diǎn)作為初始社區(qū)，用C1，C2，…，Ck表示，對(duì)k個(gè)社區(qū)以并行方式基于層次便利的方法發(fā)展其它節(jié)點(diǎn)作為其社區(qū)成員。其中標(biāo)簽傳播值的更新規(guī)則如下：

其中，Ni為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)的集合，laj為鄰居節(jié)點(diǎn)vj的標(biāo)簽活性值，kj為鄰居節(jié)點(diǎn)vj的度，wij為節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間興趣相似度和社交影響力的擬合，α為相應(yīng)的常數(shù)系數(shù)，反映節(jié)點(diǎn)興趣相似度和社交影響力所占的權(quán)重。

2 社區(qū)劃分方案

社區(qū)Cx不能無(wú)限制地發(fā)展其社區(qū)成員，因此在進(jìn)行社區(qū)決策時(shí)需要一些限制條件，以此來(lái)確定劃分的社區(qū)個(gè)數(shù)以及每個(gè)社區(qū)中包含的節(jié)點(diǎn)個(gè)數(shù)。

關(guān)于劃分社區(qū)個(gè)數(shù)的問(wèn)題，初始化k個(gè)社區(qū)，在社區(qū)劃分層次遍歷過(guò)程中，若兩個(gè)社區(qū)中新遍歷的待加入節(jié)點(diǎn)vi與vj直接相連，則將這兩個(gè)社區(qū)合并為一個(gè)社區(qū)；若存在η個(gè)相似的情況，則最終劃分好的社區(qū)個(gè)數(shù)為k-η=p。

關(guān)于社區(qū)中包含節(jié)點(diǎn)個(gè)數(shù)的問(wèn)題，首先給定一個(gè)社區(qū)中成員個(gè)數(shù)的上限lim，在層次遍歷過(guò)程中，若一個(gè)社區(qū)中節(jié)點(diǎn)個(gè)數(shù)超過(guò)該上限值，則不再加入新的節(jié)點(diǎn)，終止對(duì)該社區(qū)的成員開(kāi)發(fā)。也就是說(shuō)，在社區(qū)成員開(kāi)發(fā)的過(guò)程中，一個(gè)節(jié)點(diǎn)會(huì)被不同的社區(qū)競(jìng)爭(zhēng)，而這個(gè)節(jié)點(diǎn)的最終歸屬權(quán)根據(jù)該節(jié)點(diǎn)在不同社區(qū)的標(biāo)簽傳播值來(lái)確定，因?yàn)樵趯哟伪闅v過(guò)程中，同一節(jié)點(diǎn)會(huì)因?qū)?yīng)社區(qū)的不同擁有不用的標(biāo)簽傳播值。假設(shè)節(jié)點(diǎn)vi對(duì)于分別從Cx和Cy遍歷的兩個(gè)社區(qū)，若從社區(qū)Cx遍歷節(jié)點(diǎn)的標(biāo)簽傳播值大于從Cy遍歷的標(biāo)簽傳播值，且社區(qū)Cx的成員個(gè)數(shù)未達(dá)到上限值，則節(jié)點(diǎn)vi從屬于社區(qū)Cx，繼續(xù)社區(qū)Cx的成員發(fā)展；若社區(qū)Cy的成員數(shù)未達(dá)上限，節(jié)點(diǎn)vi從屬于社區(qū)Cy。

基于特征向量中心性和改進(jìn)標(biāo)簽傳播算法劃分的網(wǎng)絡(luò)社區(qū)是非重疊的，且最終劃分好的社區(qū)個(gè)數(shù)已知。根據(jù)描述，社區(qū)劃分的偽碼算法如算法1 所示。算法1 的時(shí)間復(fù)雜度取決于計(jì)算特征向量中心性值、特征向量中心性值排序、層次遍歷、計(jì)算標(biāo)簽傳播值和社區(qū)合并。其中，特征向量中心性值排序只需要找到前k個(gè)最大值，相當(dāng)于Top k問(wèn)題，算法時(shí)間復(fù)雜度為O（nlogk），其余部分的時(shí)間復(fù)雜度均為O（n）。由于這5 個(gè)部分是串行工作的，因此算法1的時(shí)間復(fù)雜度為O（n）。

算法1社區(qū)劃分算法

3 社區(qū)管理

對(duì)于每一個(gè)劃分好的社區(qū)Cx，要在社區(qū)中選擇一個(gè)競(jìng)爭(zhēng)力最大的節(jié)點(diǎn)vi，在該節(jié)點(diǎn)上部署一個(gè)控制器Sx，以方便管理本社區(qū)中的信息和拓?fù)浣Y(jié)構(gòu)以及與其他社區(qū)之間的交互。

3.1 控制器部署

控制器的部署基于社區(qū)中節(jié)點(diǎn)的競(jìng)爭(zhēng)力確定，通過(guò)對(duì)節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)能力和通信代價(jià)等方面進(jìn)行研究，將SDN控制器分配到競(jìng)爭(zhēng)力最大的社區(qū)節(jié)點(diǎn)。對(duì)于社區(qū)Cx，用Cpxi表示社區(qū)節(jié)點(diǎn)vi的競(jìng)爭(zhēng)力，可以得到：

其中，Dfxi為節(jié)點(diǎn)vi數(shù)據(jù)轉(zhuǎn)發(fā)能力，Coxi為控制器Sx部署在社區(qū)Cx的節(jié)點(diǎn)vi上的通信代價(jià)，φ為調(diào)節(jié)系數(shù)。節(jié)點(diǎn)的競(jìng)爭(zhēng)力與數(shù)據(jù)轉(zhuǎn)發(fā)能力成正比，與通信代價(jià)成反比。

節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)能力與其標(biāo)簽傳播值和網(wǎng)絡(luò)帶寬有關(guān)，用表示標(biāo)準(zhǔn)化后的標(biāo)簽傳播值，用Bwi＇表示標(biāo)準(zhǔn)化的網(wǎng)絡(luò)帶寬。則：

節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)能力可以表示為：

其中，β為標(biāo)簽傳播值和網(wǎng)絡(luò)帶寬所占的權(quán)重。

通信代價(jià)可用路由器的傳輸時(shí)延和能量耗損表示，傳輸時(shí)延與通過(guò)節(jié)點(diǎn)路由器vi的請(qǐng)求次數(shù)Nui和路由器固定的時(shí)延消耗Csi有關(guān)；能量消耗與流經(jīng)路由器vi的數(shù)據(jù)流量Tfi與處理每比特?cái)?shù)據(jù)的能量消耗Eci有關(guān)。則：

對(duì)通信代價(jià)進(jìn)行標(biāo)準(zhǔn)化，將值分布在區(qū)間（0，1）之間，則可以將Coix＇標(biāo)準(zhǔn)化后的通信代價(jià)：

控制器部署節(jié)點(diǎn)Vi選擇的偽碼算法如算法2 所示。算法2 的時(shí)間復(fù)雜度取決于計(jì)算數(shù)據(jù)轉(zhuǎn)發(fā)能力、通信代價(jià)和節(jié)點(diǎn)競(jìng)爭(zhēng)力，每個(gè)部分計(jì)算的時(shí)間復(fù)雜度均為O（n），且每一部分并行工作，因此算法2總的時(shí)間復(fù)雜度為O（n）。

算法2控制器部署節(jié)點(diǎn)選擇

3.2 控制器信息管理

為使控制器有效地管理社區(qū)內(nèi)容，提升內(nèi)容檢索速度，為每個(gè)控制器設(shè)計(jì)信息索引表（SIT），記錄社區(qū)內(nèi)的內(nèi)容所在節(jié)點(diǎn)的映射并為社區(qū)內(nèi)路由提供支持；設(shè)計(jì)社區(qū)拓?fù)浣Y(jié)構(gòu)表（SCT），幫助維護(hù)社區(qū)拓?fù)湫畔⒉⑦M(jìn)行社區(qū)間路由。

信息索引表由三個(gè)字段組成：內(nèi)容名稱(chēng)前綴（PRE）、內(nèi)容名（CNA）、內(nèi)容持有者（CHL）。其主要作用是在控制器上建立社區(qū)中各節(jié)點(diǎn)上內(nèi)容的映射，以使控制器能清晰地掌握社區(qū)成員的內(nèi)容持有情況，以方便準(zhǔn)確轉(zhuǎn)發(fā)內(nèi)容給請(qǐng)求者。在一個(gè)社區(qū)中一個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)不同的內(nèi)容（但對(duì)同一個(gè)內(nèi)容不會(huì)存儲(chǔ)多次），同一個(gè)內(nèi)容也可能被多個(gè)不同的節(jié)點(diǎn)持有。

拓?fù)浣Y(jié)構(gòu)表由相鄰社區(qū)（ACS）、內(nèi)容名稱(chēng)前綴（PRE）、內(nèi)容傳輸次數(shù)（NCT）三個(gè)字段組成。其中，相鄰社區(qū)指與當(dāng)前社區(qū)相鄰的社區(qū)；內(nèi)容名稱(chēng)前綴指在兩個(gè)社區(qū)間傳輸?shù)膬?nèi)容的前綴標(biāo)簽；內(nèi)容傳輸次數(shù)指兩個(gè)社區(qū)之間總共傳輸數(shù)據(jù)的次數(shù)。主要功能是記錄社區(qū)之間不同類(lèi)型內(nèi)容傳輸?shù)目偞螖?shù)，為后續(xù)的興趣包在社區(qū)間的路由查詢(xún)提供支撐。

4 實(shí)驗(yàn)及性能評(píng)價(jià)

實(shí)驗(yàn)使用的對(duì)比算法包括LPA-h、S-LPA 和HPILPA，實(shí)驗(yàn)結(jié)果采用100 次不同運(yùn)行結(jié)果之后的平均值，在Intel（R）Core（TM）i7-9700CPU@3.00GHzCPU、32GBRAM的Windows 系統(tǒng)上進(jìn)行。實(shí)驗(yàn)數(shù)據(jù)選取karate、dolphins、polbooks和football等4個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集及仿真網(wǎng)絡(luò)。

4.1 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)

采用模塊度標(biāo)準(zhǔn)差（Qsd）作為社區(qū)劃分穩(wěn)定性的評(píng)價(jià)指標(biāo)，標(biāo)準(zhǔn)差越接近于0，則劃分社區(qū)結(jié)構(gòu)越穩(wěn)定。其中t表示算法運(yùn)行次數(shù)，Qi表示第i次運(yùn)行得到的模塊度的值。

從表1 可見(jiàn)，在模塊度標(biāo)準(zhǔn)差上，SI-LPA 算法的Qsd值均為0，說(shuō)明本文提出的SI-LPA 算法具有較強(qiáng)的穩(wěn)定性。

Table 1 Comparison of network stability表1 網(wǎng)絡(luò)穩(wěn)定性比較

4.2 仿真網(wǎng)絡(luò)實(shí)驗(yàn)

采用ndnSIM 進(jìn)行數(shù)據(jù)仿真與性能分析，使用由100 個(gè)點(diǎn)、474 條邊構(gòu)成的人工合成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中98 個(gè)為路由器節(jié)點(diǎn)，2 個(gè)為服務(wù)器節(jié)點(diǎn)。初始狀態(tài)下，所有的數(shù)據(jù)內(nèi)容僅存儲(chǔ)在服務(wù)器節(jié)點(diǎn)上，路由器節(jié)點(diǎn)不存儲(chǔ)內(nèi)容。實(shí)驗(yàn)采用的社區(qū)劃分對(duì)比算法為L(zhǎng)PAh、HPI-LPL、S-LPA 等，統(tǒng)一采用蟻群算法進(jìn)行CCN 數(shù)據(jù)路由。對(duì)每個(gè)劃分算法進(jìn)行100 次實(shí)驗(yàn)，在不同的興趣請(qǐng)求次數(shù)下計(jì)算各社區(qū)劃分算法的平均路由跳數(shù)以及緩存命中率。

4.2.1 仿真環(huán)境與參數(shù)設(shè)置

本文涉及到的所有參數(shù)及其值如表2 所示。通過(guò)在不同參數(shù)設(shè)置下進(jìn)行模擬實(shí)驗(yàn)，確定一個(gè)具體的數(shù)值，使得整個(gè)路由決策能夠達(dá)到最優(yōu)性能。在所有參數(shù)中，社區(qū)內(nèi)成員個(gè)數(shù)上限lim是絕對(duì)關(guān)鍵的，將直接影響到路由的性能。

Table 2 Parameter value setting表2 參數(shù)值設(shè)置

為評(píng)價(jià)社區(qū)劃分結(jié)果的好壞，引入模塊度Q 的概念來(lái)衡量社區(qū)劃分的質(zhì)量，其值越接近1，社區(qū)的劃分質(zhì)量越好，但通常很難達(dá)到1。對(duì)于不同的lim值，對(duì)應(yīng)的模塊度值變化如圖1 所示。觀察到圖1 出現(xiàn)了一個(gè)峰值，當(dāng)lim=20 時(shí)，模塊度最接近于1。此外，在達(dá)到峰值之前，模塊度值的變化迅速增加，峰值之后模塊度降低逐漸變緩。這說(shuō)明，強(qiáng)模塊度的建立過(guò)程是快速的，而破壞相對(duì)緩慢。

Fig.1 Modularity values corresponding to different lim values圖1 不同lim值對(duì)應(yīng)的模塊度值

4.2.2 平均路由數(shù)

在不同的興趣請(qǐng)求次數(shù)下，觀察平均路由跳數(shù)，結(jié)果如圖2 所示。由圖2 可知，①隨著興趣請(qǐng)求次數(shù)增加，SILPA 算法的平均路由跳數(shù)明顯低于S-LPA、LPAh 與HPI_LPA。這是因?yàn)镾I-LPA 引入了SDN 控制器對(duì)社區(qū)進(jìn)行管理，隨著請(qǐng)求次數(shù)的增加，同一個(gè)內(nèi)容再次請(qǐng)求的概率增加，此時(shí)便直接根據(jù)控制器在社區(qū)內(nèi)獲取相應(yīng)內(nèi)容，減少路由的跳數(shù)。且SI-LPA 綜合使用節(jié)點(diǎn)的興趣相似度和社交影響力，所以每次劃分的社區(qū)結(jié)構(gòu)趨于穩(wěn)定；②SILPA、S-LPA 和HPI-LPA 的路由跳數(shù)最終趨于穩(wěn)定，但是LPAh 的路由條數(shù)一直處于波動(dòng)狀態(tài)。這是因?yàn)長(zhǎng)PAh 利用目標(biāo)函數(shù)優(yōu)化社區(qū)劃分質(zhì)量，但未解決穩(wěn)定性差的問(wèn)題。

4.2.3 平均緩存命中率

對(duì)社區(qū)內(nèi)的不同節(jié)點(diǎn)請(qǐng)求相同的內(nèi)容，觀察不同的興趣請(qǐng)求次數(shù)，得到社區(qū)內(nèi)的緩存命中率如圖3 所示。由圖3 可知，隨著請(qǐng)求次數(shù)增加，各個(gè)劃分策略的緩存命中率上升，且SI-LPA 具有最高的緩存命中率。這是因?yàn)镾DN 控制器的管理功能為SI-LPA 策略的社區(qū)內(nèi)內(nèi)容的緩存提供了較好支撐，使社區(qū)內(nèi)請(qǐng)求內(nèi)容具有較高優(yōu)先級(jí)，從而增加了緩存命中率。

Fig.2 Average routing hops under different interest requests圖2 不同興趣請(qǐng)求下的平均路由跳數(shù)

Fig.3 Average cache hit rate under different interest requests圖3 不同興趣請(qǐng)求下的平均緩存命中率

5 結(jié)語(yǔ)

本文通過(guò)引入SDN 控制器和社區(qū)劃分對(duì)CCN 路由進(jìn)行研究。結(jié)合特征向量中心性和標(biāo)簽傳播兩種主流方法進(jìn)行社區(qū)劃分，并通過(guò)部署控制器，進(jìn)行網(wǎng)絡(luò)信息維護(hù)和拓?fù)涔芾恚瑢?duì)提出的方案進(jìn)行了穩(wěn)定性驗(yàn)證與仿真。實(shí)驗(yàn)結(jié)果表明，利用該方案能夠獲得較好的社區(qū)劃分結(jié)果，在此基礎(chǔ)上的路由策略能夠降低路由條數(shù)并提升緩存命中率。然而，隨著網(wǎng)絡(luò)流量的劇增，CCN 中采用的路由策略會(huì)造成PIT 表的爆炸式增長(zhǎng)，從而導(dǎo)致大量的路由冗余，路由策略的優(yōu)化成為CCN 研究的重點(diǎn)。在今后的研究工作中，希望能夠在此基礎(chǔ)上進(jìn)一步提升CCN 的性能。