基于蟻群算法的ICN路由算法

龔娉婷，周金和

(北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100101)

0 引 言

信息中心網(wǎng)絡(luò)[1,2](information-centric network, ICN)以?xún)?nèi)容為中心并將內(nèi)容分散緩存在網(wǎng)絡(luò)基礎(chǔ)設(shè)施如路由器中，實(shí)現(xiàn)了數(shù)據(jù)內(nèi)容與數(shù)據(jù)位置的解耦。基于ICN路由，研究者們提出了若干路由策略,如：洪泛方式[3-5]、動(dòng)態(tài)興趣轉(zhuǎn)發(fā)[6-8]、網(wǎng)內(nèi)合作緩存[9,10]和基于SDN(軟件定義網(wǎng)絡(luò))的策略[11]等。其中，文獻(xiàn)[3]提出了一種基于相鄰組塊間關(guān)系的路由發(fā)現(xiàn)機(jī)制，以減少連續(xù)洪泛引起的開(kāi)銷(xiāo)；文獻(xiàn)[5]研究了兩種洪泛策略，并提出了用可用性的差異以及路由器的拓?fù)鋵傩詠?lái)微調(diào)洪泛半徑的建議；文獻(xiàn)[7]提出了具有名稱(chēng)映射(DIT-NM)的CCN中的動(dòng)態(tài)興趣傳輸方案，用于實(shí)時(shí)監(jiān)視網(wǎng)絡(luò)狀態(tài)和流量負(fù)載信息；文獻(xiàn)[10]提出了一種具有內(nèi)容空間分區(qū)和哈希路由的協(xié)作式網(wǎng)絡(luò)內(nèi)緩存方案(CPHR)，CPHR可以將總體命中率顯著提高多達(dá)100%，但是此方案會(huì)產(chǎn)生一定的路由開(kāi)銷(xiāo)；文獻(xiàn)[11]通過(guò)將數(shù)據(jù)平面與控制平面解耦并以集中方式管理信息，提出了一種基于SDN的路由策略，此方式便于數(shù)據(jù)的集中管理，使路由具有一定的可控性。以上方案多基于最短路徑，未綜合考慮時(shí)延、負(fù)載等多方面因素。

本文針對(duì)以上不足，綜合考慮沿邊興趣螞蟻隊(duì)列長(zhǎng)度、內(nèi)容路由器間的內(nèi)容相似度及沿邊內(nèi)容濃度三因素，提出一種基于蟻群算法的ICN路由算法(IRABA)，將傳統(tǒng)的蟻群算法結(jié)合到ICN路由中，解決了傳統(tǒng)策略存在的時(shí)延大，平均路由跳數(shù)多及負(fù)載不均衡等問(wèn)題。

1 蟻群算法的研究

1.1 蟻群算法的由來(lái)與基本原理

蟻群算法由意大利學(xué)者Dorigo M等根據(jù)自然界螞蟻覓食行為提出。螞蟻覓食行為表示大量螞蟻組成的群體構(gòu)成一個(gè)信息正反饋機(jī)制，在同一時(shí)間內(nèi)路徑越短螞蟻分泌的信息素就越多，螞蟻選擇該路徑的概率就更大。通過(guò)圖1來(lái)描述一下蟻群的搜索過(guò)程。

圖1 蟻群搜索過(guò)程

如圖1所示，設(shè)A是請(qǐng)求源節(jié)點(diǎn)(蟻巢)，D是內(nèi)容提供節(jié)點(diǎn)(食物)，共有30只螞蟻進(jìn)行覓食行為，每一只螞蟻到達(dá)一個(gè)新節(jié)點(diǎn)分泌的信息素為1(螞蟻只在相鄰節(jié)點(diǎn)之間分泌信息素)，螞蟻?zhàn)畛醯囊捠陈窂饺鐖D1(a)所示，每只螞蟻等概的選取一條路徑進(jìn)行轉(zhuǎn)發(fā)，最后每條路徑上分泌的信息素濃度相等，均為15；隨著時(shí)間的推移，因?yàn)槁窂紸ED比路徑ABCD短，路徑越短越容易積累更多的信息素，如圖1(b)所示，最后螞蟻傾向于選擇濃度更高的節(jié)點(diǎn)，即往E節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，最后盡可能快速地找尋到所需的食物。

1.2 蟻群算法的應(yīng)用

從以上分析可知，應(yīng)用蟻群算法可以?xún)?yōu)化路由尋址和路徑規(guī)劃。文獻(xiàn)[12]針對(duì)移動(dòng)機(jī)器人路徑規(guī)劃中蟻群算法的搜索效率問(wèn)題,提出一種改進(jìn)的多步長(zhǎng)蟻群算法；文獻(xiàn)[13]將蟻群優(yōu)化算法(ACO)引入船舶氣象路徑問(wèn)題，旨在快速、高效、準(zhǔn)確地找到越洋船舶的最優(yōu)航路。

蟻群算法還能應(yīng)用于信息中心網(wǎng)絡(luò)(ICN)的研究中，可以將ICN路由過(guò)程近似于蟻群覓食過(guò)程，節(jié)點(diǎn)通過(guò)感知下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的內(nèi)容濃度的高低進(jìn)行興趣包的轉(zhuǎn)發(fā)。在ICN路由中，進(jìn)行內(nèi)容請(qǐng)求的興趣包可以用興趣螞蟻(IA)來(lái)代替(一個(gè)興趣螞蟻攜帶一個(gè)特定的興趣包)，而檢索過(guò)程返回的數(shù)據(jù)包則可用數(shù)據(jù)螞蟻來(lái)表示(一個(gè)數(shù)據(jù)螞蟻攜帶一個(gè)特定的內(nèi)容數(shù)據(jù)包)。基于以上特點(diǎn)，文獻(xiàn)[14]將蟻群算法應(yīng)用于移動(dòng)ICN場(chǎng)景，忽略了IA的多樣性特征，可能導(dǎo)致負(fù)載的不均衡；文獻(xiàn)[15]綜合考慮內(nèi)容濃度和內(nèi)容相似度兩因素，進(jìn)行興趣螞蟻的轉(zhuǎn)發(fā)與內(nèi)容的獲取，此算法在無(wú)擁塞的情況下效果良好，但是當(dāng)單個(gè)節(jié)點(diǎn)聚集多個(gè)興趣螞蟻時(shí)可能導(dǎo)致瓶頸節(jié)點(diǎn)的出現(xiàn)，影響整個(gè)路由過(guò)程的順利進(jìn)行。針對(duì)以上不足，本文確定全新的興趣螞蟻概率轉(zhuǎn)發(fā)機(jī)制，綜合考慮內(nèi)容濃度(即最短路徑)、節(jié)點(diǎn)間IA隊(duì)列長(zhǎng)度以及各內(nèi)容路由器節(jié)點(diǎn)內(nèi)容多樣性等因素，選取最佳的路由路徑進(jìn)行轉(zhuǎn)發(fā)，以獲得最佳的服務(wù)質(zhì)量。

2 基于蟻群算法的ICN路由

在ICN中，內(nèi)容路由器(CR)中包含3張表：內(nèi)容存儲(chǔ)表(content store, CS)、待定信息表(pending interest table，PIT)和轉(zhuǎn)發(fā)信息表(forwarding information base,FIB)。CS用來(lái)記錄已緩存的內(nèi)容信息，包括內(nèi)容名稱(chēng)和相應(yīng)的內(nèi)容；PIT由內(nèi)容名和已接入接口ID兩部分組成，便于內(nèi)容數(shù)據(jù)包的高效轉(zhuǎn)發(fā)；FIB用于確定興趣包的下一跳，以做出最佳的路由決策。基于蟻群算法的ICN路由算法基于以上原理，IA基于CS、PIT和FIB這3張表進(jìn)行興趣包的轉(zhuǎn)發(fā)，相關(guān)興趣包的路由決策在FIB中完成。

2.1 總體思路

IRABA以傳統(tǒng)蟻群算法為基礎(chǔ)，構(gòu)建請(qǐng)求節(jié)點(diǎn)與轉(zhuǎn)發(fā)節(jié)點(diǎn)間的內(nèi)容濃度更新模型、節(jié)點(diǎn)間IA隊(duì)列長(zhǎng)度模型及相鄰兩節(jié)點(diǎn)內(nèi)容相似度模型，最終確定最佳轉(zhuǎn)發(fā)概率模型。運(yùn)用輪盤(pán)賭模型進(jìn)行IA轉(zhuǎn)發(fā)接口的分配，使在不造成節(jié)點(diǎn)擁塞的情況下概率更大的轉(zhuǎn)發(fā)接口盡可能多地轉(zhuǎn)發(fā)IA。此算法考慮了單個(gè)節(jié)點(diǎn)的處理能力，有效避免了瓶頸節(jié)點(diǎn)的出現(xiàn)，更節(jié)能更高效。圖2為總體設(shè)計(jì)框架。

圖2 總體設(shè)計(jì)框架

2.2 內(nèi)容濃度模型

假設(shè)：興趣螞蟻只能感知一跳間的內(nèi)容濃度；當(dāng)一只IA到達(dá)一個(gè)新的節(jié)點(diǎn)，沿邊均釋放數(shù)值為τ的內(nèi)容濃度；每一條邊的初始內(nèi)容濃度值為τ0。

隨著時(shí)間的推移，酒精揮發(fā)的速度越來(lái)越快，直到酒精的濃度揮發(fā)到接近0。受酒精揮發(fā)模型的啟發(fā)，內(nèi)容濃度τ(t) 隨t的變化曲線如圖3所示，具體揮發(fā)表達(dá)式見(jiàn)式(1)。

圖3 內(nèi)容濃度變化曲線

(1)

如圖4所示，m只興趣螞蟻位于請(qǐng)求源節(jié)點(diǎn)A，隊(duì)列長(zhǎng)度為m的興趣包依次從節(jié)點(diǎn)A開(kāi)始轉(zhuǎn)發(fā)，m可變，節(jié)點(diǎn)A與其轉(zhuǎn)發(fā)節(jié)點(diǎn)集間(轉(zhuǎn)發(fā)節(jié)點(diǎn)集的確定見(jiàn)2.5)的內(nèi)容濃度高低是IA選擇下一跳轉(zhuǎn)發(fā)接口的關(guān)鍵因素。其中，Tci,j(tn) 為CRi與CRj之間在 (0,tn] 內(nèi)所積累的總內(nèi)容濃度，表達(dá)式見(jiàn)式(2)。

圖4 基于蟻群算法的ICN模型實(shí)例

(2)

式中：aci,j(tn) 表示tn時(shí)刻沿邊ij(eij) 所新增的內(nèi)容濃度，rci,j(tn) 為eij在tn時(shí)刻的初始內(nèi)容濃度，aci,j(tn) 和rci,j(tn) 的具體表達(dá)式見(jiàn)式(3)、式(4)

(3)

rci,j(tn)=Tci,j(tn-1)e-θ.tn

(4)

其中，aci,jλ(tn) 表示第λ只興趣螞蟻iaλ在tn時(shí)刻釋放的內(nèi)容濃度，對(duì)于xλ： 1表示iaλ經(jīng)過(guò)節(jié)點(diǎn)j進(jìn)行興趣包的轉(zhuǎn)發(fā)，0表示iaλ未經(jīng)過(guò)eij。

以下是式(4)的推導(dǎo)過(guò)程：

(1)把 (0,tn] 時(shí)間段劃分為n個(gè)小時(shí)隙，如圖5所示；

圖5n個(gè)時(shí)隙劃分原理

(2)分別計(jì)算每一小時(shí)隙段的

rc

i,j

(

t

k

),1≤

k

≤

n

， 最后歸納總結(jié)得

rc

i,j

(

t

n

)。

1)t1時(shí)刻，已知每一條邊的初始內(nèi)容濃度值為τ0， 根據(jù)式(1)可得式(5)；

2)t2時(shí)刻，t1時(shí)刻末的總內(nèi)容濃度Tci,j(t1) 作為t2時(shí)刻的eij的初始內(nèi)容濃度值，根據(jù)式(1)、式(2)即得式(6)；

3) 以此類(lèi)推，tn時(shí)刻，tn-1時(shí)刻末的總內(nèi)容濃度Tci,j(tn-1) 作為tn時(shí)刻的eij的初始內(nèi)容濃度值，即式(4)為rci,j(tn) 的最終表達(dá)式

rci,j(t1)=τ0e-θ.t1

(5)

(6)

綜合式(2)～式(4)，eij在 (0,tn] 內(nèi)所積累的總內(nèi)容濃度是初始內(nèi)容濃度和新增內(nèi)容濃度的疊加，具體見(jiàn)式(7)

(7)

由式(7)可知，tn時(shí)刻所積累的內(nèi)容濃度是關(guān)于tn的連續(xù)函數(shù)，因此內(nèi)容濃度更新模型是連續(xù)的。

2.3 內(nèi)容相似度模型

杰拉德相似系數(shù)是衡量?jī)蓚€(gè)集合相似度的一種指標(biāo)。本文將每個(gè)內(nèi)容路由器的內(nèi)容樣本等效為一個(gè)集合，運(yùn)用杰拉德相似系數(shù)來(lái)斷定兩相鄰內(nèi)容路由器的相似性程度的高低，最終過(guò)濾到相似度高的內(nèi)容路由器，使整個(gè)網(wǎng)絡(luò)具有更高的內(nèi)容多樣性。

杰拉德相似系數(shù)等于樣本集交集個(gè)數(shù)與樣本集并集個(gè)數(shù)的比值，具體見(jiàn)式(8)

(8)

所以判斷內(nèi)容路由器內(nèi)容相似度的關(guān)鍵是獲取各內(nèi)容路由器的內(nèi)容樣本集(具體見(jiàn)算法1)，最后通過(guò)式(8)得出最終的杰拉德相似系數(shù)。

算法1：

(1)找尋請(qǐng)求節(jié)點(diǎn)的轉(zhuǎn)發(fā)節(jié)點(diǎn)集(見(jiàn)2.5)；

(2)提取各節(jié)點(diǎn)(源節(jié)點(diǎn)和轉(zhuǎn)發(fā)節(jié)點(diǎn)集)CS表中的內(nèi)容成分，各自保存在集合中；

(3)統(tǒng)計(jì)各節(jié)點(diǎn)緩存內(nèi)容的總數(shù)，確定一個(gè)內(nèi)容數(shù)目的閾值(50)，若節(jié)點(diǎn)緩存內(nèi)容的總數(shù)小于等于50，則內(nèi)容樣本集即為最初的集合，直接跳到步驟(5)，否則進(jìn)入步驟(4)；

(4)若節(jié)點(diǎn)緩存內(nèi)容的總數(shù)過(guò)多(大于50)，則要對(duì)初始集合進(jìn)行分類(lèi)，將相似的內(nèi)容歸為一類(lèi)，根據(jù)內(nèi)容名稱(chēng)進(jìn)行分類(lèi)(如：體育類(lèi)內(nèi)容、娛樂(lè)性?xún)?nèi)容、購(gòu)物類(lèi)內(nèi)容等)，得出最終的內(nèi)容樣本集；

(5)運(yùn)用式(8)計(jì)算請(qǐng)求節(jié)點(diǎn)與轉(zhuǎn)發(fā)節(jié)點(diǎn)集間的杰拉德相似系數(shù)。

2.4 隊(duì)列長(zhǎng)度

網(wǎng)絡(luò)節(jié)點(diǎn)處理能力相同，設(shè)單位時(shí)間內(nèi)單個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)興趣螞蟻的個(gè)數(shù)為c， 則經(jīng)過(guò)時(shí)間t后，節(jié)點(diǎn)所處理的興趣螞蟻的個(gè)數(shù)為ct，源節(jié)點(diǎn)i擁有m個(gè)興趣螞蟻，源節(jié)點(diǎn)i的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合為 {j1,j2,…,jn} (見(jiàn)2.5)，設(shè)每個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)在 (0,t] 時(shí)間段所接受的總興趣螞蟻的個(gè)數(shù)分別為 {Nac1,Nac2,…,Nacn}。 隊(duì)列長(zhǎng)度di,jk的大小會(huì)影響興趣螞蟻的轉(zhuǎn)發(fā)，隊(duì)列長(zhǎng)度越長(zhǎng)，表示兩節(jié)點(diǎn)間匯聚了更多的興趣螞蟻，興趣螞蟻越可能選擇其它節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)(注：隊(duì)列IA依先進(jìn)先出原則進(jìn)行轉(zhuǎn)發(fā))。隊(duì)列長(zhǎng)度的計(jì)算見(jiàn)式(9)

(9)

2.5 轉(zhuǎn)發(fā)概率

興趣螞蟻的轉(zhuǎn)發(fā)不僅與IA所釋放的內(nèi)容濃度有關(guān)，還與CR內(nèi)容相似度及IA隊(duì)列長(zhǎng)度有關(guān)。綜合考慮以上3因素，結(jié)合式(7)～式(9)，得出iaλ(1≤λ≤m) 在eij的轉(zhuǎn)發(fā)概率，以下為最佳概率轉(zhuǎn)發(fā)模型，見(jiàn)式(10)

(10)

式中：α、β、γ為大于0的正數(shù)；Fwiλ為iaλ在節(jié)點(diǎn)i的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)集；Tci,j(tn) 為tn時(shí)間內(nèi)邊eij積累的總內(nèi)容濃度，轉(zhuǎn)發(fā)概率fpi,jλ(tn) 與其呈正相關(guān)；di,j(tn) 為tn時(shí)刻eij積累的IA隊(duì)列長(zhǎng)度，fpi,jλ(tn) 與其呈負(fù)相關(guān)；Ji,j(tn) 為tn時(shí)刻請(qǐng)求節(jié)點(diǎn)i與轉(zhuǎn)發(fā)節(jié)點(diǎn)j的杰拉德相似系數(shù)，i(tn)，j(tn) 分別為tn時(shí)刻節(jié)點(diǎn)i，j的內(nèi)容樣本集，fpi,jλ(tn) 與Ji,j(tn) 呈負(fù)相關(guān)。

下面確定內(nèi)容路由器CRi的轉(zhuǎn)發(fā)接口集。假設(shè)集合中具有μ個(gè)轉(zhuǎn)發(fā)接口，則有Fwiλ={CRio|1≤o≤μ}，F(xiàn)wiλ的選取原則見(jiàn)下：

(1)Adiλ表示iaλ在節(jié)點(diǎn)i的相鄰節(jié)點(diǎn)；

(2)若iaλ從 {CRk} (前繼相鄰節(jié)點(diǎn)集)出發(fā)遍歷到CRi， 最后通過(guò)CRi進(jìn)行后繼相鄰節(jié)點(diǎn)的轉(zhuǎn)發(fā)，Reiλ即為這些后繼相鄰節(jié)點(diǎn)的集合，即Reiλ=Adiλ-{CRk}， 若i節(jié)點(diǎn)為興趣螞蟻請(qǐng)求的源節(jié)點(diǎn)，則有Reiλ=Adiλ；

(3)興趣螞蟻在請(qǐng)求內(nèi)容節(jié)點(diǎn)i途中所經(jīng)過(guò)的其它內(nèi)容節(jié)點(diǎn)集記為T(mén)riλ。 當(dāng)i為興趣螞蟻請(qǐng)求的源節(jié)點(diǎn)時(shí)，則有Triλ=?， ?表示空集；

(4)興趣螞蟻在節(jié)點(diǎn)i的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合記為Fwiλ，F(xiàn)wiλ=Reiλ-Reiλ∩Triλ， 這一設(shè)計(jì)是為了防止路由出現(xiàn)環(huán)路的現(xiàn)象，做到高效路由，表1為圖4部分節(jié)點(diǎn)的轉(zhuǎn)發(fā)節(jié)點(diǎn)。

以圖4中B節(jié)點(diǎn)為例，見(jiàn)例1：由表1，A為請(qǐng)求源節(jié)點(diǎn)，當(dāng)m只IA已從A轉(zhuǎn)發(fā)至節(jié)點(diǎn)B時(shí)，CDEF為其下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)集，令 (a,b,c) 分別為各沿邊內(nèi)容濃度、隊(duì)列長(zhǎng)度和兩節(jié)點(diǎn)間內(nèi)容相似度。

表1 圖4部分節(jié)點(diǎn)的轉(zhuǎn)發(fā)節(jié)點(diǎn)

例1：已知α=β=γ=1， (a,b,c)BC=(11,8,0.25)， (a,b,c)BD=(6,3,0.05)， (a,b,c)BE=(4,1,0.5)， (a,b,c)BF=(3,0,1)， 運(yùn)用式(10)計(jì)算出兩節(jié)點(diǎn)之間的轉(zhuǎn)發(fā)概率的值分別為：fB,C(tn)=0.097，fB,D(tn)=0.708，fB,E(tn)=0.142，fB,F(tn)=0.053。

由以上結(jié)論可得興趣螞蟻以更大的可能往節(jié)點(diǎn)D處轉(zhuǎn)發(fā)，其次往E節(jié)點(diǎn)轉(zhuǎn)發(fā)，然后往C點(diǎn)轉(zhuǎn)發(fā)，最后才考慮往F處轉(zhuǎn)發(fā)。因此最后考慮的就是路由問(wèn)題，如何依概率將興趣螞蟻分配到轉(zhuǎn)發(fā)節(jié)點(diǎn)集合中，在不造成擁塞的情況下改善Qos。

2.6 路由(Routing)

如果存在以下3種情況，單個(gè)IA轉(zhuǎn)發(fā)結(jié)束：①I(mǎi)A已找到所請(qǐng)求的內(nèi)容；②IA請(qǐng)求超時(shí) (tr>TTL)， 直接被丟棄；③興趣螞蟻所在節(jié)點(diǎn)的相鄰節(jié)點(diǎn)Fwiλ為空集，即所處節(jié)點(diǎn)已無(wú)合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)，無(wú)法進(jìn)行后續(xù)節(jié)點(diǎn)的轉(zhuǎn)發(fā)。若一只興趣螞蟻在轉(zhuǎn)發(fā)結(jié)束后仍未找到所需的內(nèi)容，則在請(qǐng)求源節(jié)點(diǎn)會(huì)同樣產(chǎn)生一只攜帶此內(nèi)容的興趣螞蟻，再一次進(jìn)行轉(zhuǎn)發(fā)，若重復(fù)轉(zhuǎn)發(fā)一次之后仍未檢索出所需內(nèi)容，默認(rèn)此內(nèi)容不存在此網(wǎng)絡(luò)節(jié)點(diǎn)中(本文假定網(wǎng)絡(luò)模型各節(jié)點(diǎn)已緩存了若干內(nèi)容)，當(dāng)所確定的m只IA全部轉(zhuǎn)發(fā)完畢，本輪路由結(jié)束，內(nèi)容濃度和隊(duì)列長(zhǎng)度置0，等待下一輪興趣請(qǐng)求重新更新，內(nèi)容相似度的更新策略依據(jù)每一節(jié)點(diǎn)的CS表，具體見(jiàn)2.3的算法1。

在路由途中，興趣螞蟻轉(zhuǎn)發(fā)節(jié)點(diǎn)的分配根據(jù)輪盤(pán)賭模型原理。設(shè)所給出的隨機(jī)值stri∈[0,1]， 將m只興趣螞蟻在請(qǐng)求節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，設(shè)興趣螞蟻在請(qǐng)求節(jié)點(diǎn)i處具有ωi個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，轉(zhuǎn)發(fā)節(jié)點(diǎn)集合表示為Fwiλ={CR1,CR2,…,CRω i}， 若對(duì)于?stri， 有式(11)存在，則向?qū)?yīng)的內(nèi)容路由器CRiκ轉(zhuǎn)發(fā)m×fpi,iκλ(tn) 只興趣螞蟻，其中fpi,iκλ(tn) 為位于節(jié)點(diǎn)i的iaλ往節(jié)點(diǎn)iκ(1≤κ≤ωi) 轉(zhuǎn)發(fā)的概率，令i節(jié)點(diǎn)的興趣螞蟻個(gè)數(shù)為m， 直到興趣螞蟻全部轉(zhuǎn)發(fā)至Fwiλ， 即滿(mǎn)足式(12)，則這一跳間的IA轉(zhuǎn)發(fā)完畢，IA繼續(xù)向其它節(jié)點(diǎn)轉(zhuǎn)發(fā)，直到IA滿(mǎn)足以上3種情況后結(jié)束轉(zhuǎn)發(fā)

(11)

(12)

以請(qǐng)求節(jié)點(diǎn)B節(jié)點(diǎn)為例，設(shè)請(qǐng)求興趣螞蟻m=10， 節(jié)點(diǎn)間的轉(zhuǎn)發(fā)概率見(jiàn)2.5例1，運(yùn)用輪盤(pán)賭模型分配興趣螞蟻轉(zhuǎn)發(fā)個(gè)數(shù)見(jiàn)下：

(1)取stri=0.5， 有0.097<0.5， 不滿(mǎn)足式(11)條件； 0.097+0.708=0.805>0.5， 滿(mǎn)足條件，興趣螞蟻往節(jié)點(diǎn)D轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)數(shù)目為7只。

(2)又取stri=0.75， 0.097+0.708+0.172>0.75， 滿(mǎn)足條件，則向節(jié)點(diǎn)E處轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)數(shù)目為2只。

(3)最后剩1個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)F，要使轉(zhuǎn)發(fā)接口集合接收10只興趣螞蟻，則要向節(jié)點(diǎn)F轉(zhuǎn)發(fā)1只興趣螞蟻。

運(yùn)用此方法轉(zhuǎn)發(fā)興趣螞蟻，使興趣螞蟻盡可能往大概率接口轉(zhuǎn)發(fā)，符合實(shí)際要求，而且此方法會(huì)盡可能避免擁塞的出現(xiàn)，平衡網(wǎng)絡(luò)負(fù)載。

3 算法仿真及結(jié)果分析

信息中心網(wǎng)絡(luò)節(jié)點(diǎn)重要性符合Zipf分布，更少的節(jié)點(diǎn)被更多的用戶(hù)訪問(wèn)，具有無(wú)標(biāo)度特性。因此無(wú)標(biāo)度網(wǎng)絡(luò)適合于信息中心網(wǎng)絡(luò)的應(yīng)用場(chǎng)景，本算法采用networkx產(chǎn)生兩個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)進(jìn)行模擬仿真，其中，圖6為頂點(diǎn)數(shù)為10，每次新增1條邊的BA網(wǎng)絡(luò)，A節(jié)點(diǎn)為興趣螞蟻請(qǐng)求源節(jié)點(diǎn)，圖7為頂點(diǎn)數(shù)為20，每次新增2條邊的BA網(wǎng)絡(luò)，B節(jié)點(diǎn)為興趣螞蟻請(qǐng)求源節(jié)點(diǎn)，已知網(wǎng)絡(luò)各節(jié)點(diǎn)已緩存若干相應(yīng)的內(nèi)容，利用這兩個(gè)網(wǎng)絡(luò)模型來(lái)檢驗(yàn)此算法的性能。本算法中的參數(shù)設(shè)置見(jiàn)表2。若干次仿真后比較IRABA、QAPSR與AIRCS這3個(gè)算法的性能，比較在不同興趣請(qǐng)求包數(shù)目下運(yùn)用這3個(gè)算法的IA在網(wǎng)絡(luò)中請(qǐng)求的平均路由命中率、平均負(fù)載均衡度以及平均執(zhí)行時(shí)間的好壞程度。

圖6 BA(10,1)

圖7 BA(20,2)

3.1 平均路由命中率ARSR

ARSR(average routing success rate)定義為成功檢索到內(nèi)容副本的興趣包請(qǐng)求數(shù)占總興趣包請(qǐng)求數(shù)的比例。見(jiàn)式(13)

(13)

表2 IRABA算法的參數(shù)設(shè)置

式中：m為興趣包總數(shù)，xi={1,0}， 1表示興趣螞蟻成功檢索出內(nèi)容副本，反之0表示興趣未能檢索出內(nèi)容副本直接消亡。

將IRABA，QAPSR和AIRCS這3個(gè)算法進(jìn)行比較，仿真發(fā)現(xiàn)，對(duì)于兩個(gè)BA網(wǎng)絡(luò)圖： BA(10,1) 和BA(20,2)， 運(yùn)用IRABA和AIRCS進(jìn)行興趣螞蟻轉(zhuǎn)發(fā)具有接近100%的ARSR，幾乎每個(gè)興趣螞蟻都能檢索出所需的內(nèi)容副本，相比前兩種算法，QAPSR的ARSR范圍為91%-92%，不同數(shù)目興趣螞蟻(50,250,350,400)運(yùn)用不同算法在兩個(gè)BA網(wǎng)絡(luò)的ARSR見(jiàn)表3。ARSR變化曲線分別如圖8和圖9所示。

3.2 平均時(shí)延AD

AD(average delay)定義為所有興趣螞蟻從產(chǎn)生到消亡所經(jīng)歷的時(shí)間的平均值。興趣螞蟻消亡的條件有兩個(gè)：其一，攜帶此興趣包的興趣螞蟻已檢索到所需的內(nèi)容副本；其二，攜帶此興趣包興趣螞蟻在指定的TTL內(nèi)未檢索出所需內(nèi)容。AD的計(jì)算公式見(jiàn)式(14)。其中，m為請(qǐng)求興趣螞蟻總數(shù)，ti為單個(gè)興趣包的存在時(shí)間

(14)

表3 不同算法在兩個(gè)BA網(wǎng)絡(luò)中的ARSR

圖9 BA(20,2)的ARSR變化曲線

由于IRABA考慮了IA的隊(duì)列長(zhǎng)度，綜合考慮了內(nèi)容濃度、節(jié)點(diǎn)負(fù)載以及節(jié)點(diǎn)內(nèi)容相似度，能有效避開(kāi)高擁塞節(jié)點(diǎn)，在請(qǐng)求數(shù)目眾多的情況下，大大節(jié)約了興趣包等待時(shí)間。因此在興趣螞蟻數(shù)量較多的情況下，相比QAPSR和AIRCS算法，IRABA在減少AD方面具有更大的優(yōu)勢(shì)，而QAPSR算法也考慮了擁塞情況，在減少平均時(shí)延性能方面效果良好。不同數(shù)目興趣螞蟻(50,250,350,400)運(yùn)用不同算法在兩個(gè)BA網(wǎng)絡(luò)的AD見(jiàn)表4，具體AD變化曲線分別如圖10和圖11所示。

表4 不同算法在兩個(gè)BA網(wǎng)絡(luò)中的AD

圖10 BA(10,1)的AD變化曲線

圖11 BA(20,2)的AD變化曲線

3.3 平均負(fù)載均衡度ALBD

ALBD(average load balance degree)定義為所有鏈路負(fù)載的變化率，用來(lái)表征網(wǎng)絡(luò)整體的擁塞性能。網(wǎng)絡(luò)的擁塞狀況可用式(15)來(lái)表示

(15)

式中： ΔNp=Np(t+Δt)-Np(t)，c為每個(gè)節(jié)點(diǎn)的處理能力 (c=3)，R為網(wǎng)絡(luò)數(shù)據(jù)產(chǎn)生率，Np(t) 為t時(shí)刻網(wǎng)絡(luò)的數(shù)據(jù)包總數(shù)。通暢狀態(tài)下，ALBD=0， 有擁塞的狀態(tài)下ALBD是一個(gè)常數(shù)。比較以上4種算法，只有IRABA考慮了單個(gè)節(jié)點(diǎn)負(fù)載情況，避免了局部擁塞節(jié)點(diǎn)的出現(xiàn)，更好地促進(jìn)了興趣螞蟻的轉(zhuǎn)發(fā)，提高了網(wǎng)絡(luò)的整體性能，其ALBD≈0。 兩個(gè)BA網(wǎng)絡(luò)的ALBD見(jiàn)表5，具體變化曲線如圖12和圖13所示。

表5 不同算法在兩個(gè)BA網(wǎng)絡(luò)中的ALBD

圖12 BA(10,1)的ALBD變化曲線

圖13 BA(20,2)的ALBD變化曲線

4 結(jié)束語(yǔ)

為了進(jìn)一步優(yōu)化ICN路由問(wèn)題，本文提出了一種基于蟻群算法的ICN路由算法(IRABA)。此算法通過(guò)構(gòu)建內(nèi)容濃度模型、節(jié)點(diǎn)內(nèi)容相似度模型和節(jié)點(diǎn)興趣螞蟻隊(duì)列長(zhǎng)度模型，最終得出最佳的概率轉(zhuǎn)發(fā)模型。此算法結(jié)合了傳統(tǒng)的酒精揮發(fā)模型、杰拉德相似系數(shù)以及輪盤(pán)賭模型等，旨在更好更高效實(shí)現(xiàn)攜帶興趣請(qǐng)求包的興趣螞蟻的轉(zhuǎn)發(fā)。此外，將IRABA與已有的基于蟻群算法改進(jìn)的算法進(jìn)行比較，仿真表現(xiàn)在請(qǐng)求數(shù)不斷增加的情況下IRABA具有更好的性能，更適合于興趣螞蟻的轉(zhuǎn)發(fā)。

移動(dòng)ICN的進(jìn)一步發(fā)展，海量用戶(hù)的接入加重了網(wǎng)絡(luò)的負(fù)載，運(yùn)用此路由算法可以改善當(dāng)前網(wǎng)絡(luò)擁塞的環(huán)境，促進(jìn)網(wǎng)絡(luò)的負(fù)載均衡，能進(jìn)一步提高Qos，降低網(wǎng)絡(luò)運(yùn)行成本。