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

龔娉婷，周金和

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

0 引 言

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

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

1 蟻群算法的研究

1.1 蟻群算法的由來與基本原理

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

圖1 蟻群搜索過程

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

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

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

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

2 基于蟻群算法的ICN路由

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

2.1 總體思路

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

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

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

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

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

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

(1)

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

圖4 基于蟻群算法的ICN模型實例

(2)

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

(3)

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

(4)

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

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

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

圖5n個時隙劃分原理

(2)分別計算每一小時隙段的

rc

i,j

(

t

k

),1≤

k

≤

n

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

rc

i,j

(

t

n

)。

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

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

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

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

(5)

(6)

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

(7)

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

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

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

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

(8)

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

算法1：

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

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

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

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

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

2.4 隊列長度

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

(9)

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

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

(10)

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

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

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

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

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

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

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

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

例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)， 運用式(10)計算出兩節(jié)點之間的轉(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é)點D處轉(zhuǎn)發(fā)，其次往E節(jié)點轉(zhuǎn)發(fā)，然后往C點轉(zhuǎn)發(fā)，最后才考慮往F處轉(zhuǎn)發(fā)。因此最后考慮的就是路由問題，如何依概率將興趣螞蟻分配到轉(zhuǎn)發(fā)節(jié)點集合中，在不造成擁塞的情況下改善Qos。

2.6 路由(Routing)

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

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

(11)

(12)

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

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

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

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

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

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

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

圖6 BA(10,1)

圖7 BA(20,2)

3.1 平均路由命中率ARSR

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

(13)

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

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

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

3.2 平均時延AD

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

(14)

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

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

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

表4 不同算法在兩個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ù)載的變化率，用來表征網(wǎng)絡(luò)整體的擁塞性能。網(wǎng)絡(luò)的擁塞狀況可用式(15)來表示

(15)

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

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

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

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

4 結(jié)束語

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

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