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

龔娉婷，周金和

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

0 引 言

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

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

1 蟻群算法的研究

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

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

圖1 蟻群搜索過程

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

1.2 蟻群算法的應用

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

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

2 基于蟻群算法的ICN路由

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

2.1 總體思路

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

圖2 總體設計框架

2.2 內容濃度模型

假設：興趣螞蟻只能感知一跳間的內容濃度；當一只IA到達一個新的節點，沿邊均釋放數值為τ的內容濃度；每一條邊的初始內容濃度值為τ0。

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

圖3 內容濃度變化曲線

(1)

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

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

(2)

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

(3)

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

(4)

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

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

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

圖5n個時隙劃分原理

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

rc

i,j

(

t

k

),1≤

k

≤

n

， 最后歸納總結得

rc

i,j

(

t

n

)。

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

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

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

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

(5)

(6)

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

(7)

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

2.3 內容相似度模型

杰拉德相似系數是衡量兩個集合相似度的一種指標。本文將每個內容路由器的內容樣本等效為一個集合，運用杰拉德相似系數來斷定兩相鄰內容路由器的相似性程度的高低，最終過濾到相似度高的內容路由器，使整個網絡具有更高的內容多樣性。

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

(8)

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

算法1：

(1)找尋請求節點的轉發節點集(見2.5)；

(2)提取各節點(源節點和轉發節點集)CS表中的內容成分，各自保存在集合中；

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

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

(5)運用式(8)計算請求節點與轉發節點集間的杰拉德相似系數。

2.4 隊列長度

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

(9)

2.5 轉發概率

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

(10)

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

下面確定內容路由器CRi的轉發接口集。假設集合中具有μ個轉發接口，則有Fwiλ={CRio|1≤o≤μ}，Fwiλ的選取原則見下：

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

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

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

(4)興趣螞蟻在節點i的轉發節點集合記為Fwiλ，Fwiλ=Reiλ-Reiλ∩Triλ， 這一設計是為了防止路由出現環路的現象，做到高效路由，表1為圖4部分節點的轉發節點。

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

表1 圖4部分節點的轉發節點

例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)計算出兩節點之間的轉發概率的值分別為：fB,C(tn)=0.097，fB,D(tn)=0.708，fB,E(tn)=0.142，fB,F(tn)=0.053。

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

2.6 路由(Routing)

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

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

(11)

(12)

以請求節點B節點為例，設請求興趣螞蟻m=10， 節點間的轉發概率見2.5例1，運用輪盤賭模型分配興趣螞蟻轉發個數見下：

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

(2)又取stri=0.75， 0.097+0.708+0.172>0.75， 滿足條件，則向節點E處轉發，轉發數目為2只。

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

運用此方法轉發興趣螞蟻，使興趣螞蟻盡可能往大概率接口轉發，符合實際要求，而且此方法會盡可能避免擁塞的出現，平衡網絡負載。

3 算法仿真及結果分析

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

圖6 BA(10,1)

圖7 BA(20,2)

3.1 平均路由命中率ARSR

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

(13)

表2 IRABA算法的參數設置

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

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

3.2 平均時延AD

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

(14)

表3 不同算法在兩個BA網絡中的ARSR

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

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

表4 不同算法在兩個BA網絡中的AD

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

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

3.3 平均負載均衡度ALBD

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

(15)

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

表5 不同算法在兩個BA網絡中的ALBD

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

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

4 結束語

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

移動ICN的進一步發展，海量用戶的接入加重了網絡的負載，運用此路由算法可以改善當前網絡擁塞的環境，促進網絡的負載均衡，能進一步提高Qos，降低網絡運行成本。