MSN下族內(nèi)可信蟻群機會路由改進算法

金小俊，吳 軍，薛冒杰，白光偉

(南京工業(yè)大學 計算機科學與技術(shù)學院，江蘇 南京 211816)

0 引 言

隨著移動設(shè)備(如手機、PDA等)的大量普及，通過設(shè)備的移動帶來機會式連接從而搭建起臨時網(wǎng)絡(luò)，使得在不具備通信基礎(chǔ)設(shè)施的網(wǎng)絡(luò)環(huán)境中設(shè)備間通信成為可能，這種具備移動特性和社會性的新型網(wǎng)絡(luò)形式稱為移動社會網(wǎng)絡(luò)[1](mobile social networks，MSN)。由于人們之間社會關(guān)系相當穩(wěn)定且存在一定的依賴性，網(wǎng)絡(luò)中會出現(xiàn)簇聚現(xiàn)象，節(jié)點以自組織的方式形成族，族內(nèi)的節(jié)點聯(lián)系緊密且處于相對穩(wěn)定狀態(tài)，因此通過蟻群算法可以有效設(shè)計分布式且自適應(yīng)性的路由算法。在移動網(wǎng)絡(luò)的環(huán)境中，節(jié)點的自私性體現(xiàn)為節(jié)點對消息的轉(zhuǎn)發(fā)意愿的強弱，節(jié)點的轉(zhuǎn)發(fā)意愿的強弱與節(jié)點間的社會關(guān)系強度有關(guān)[2]。社會關(guān)系越強，節(jié)點的轉(zhuǎn)發(fā)意愿就越強，相應(yīng)的消息轉(zhuǎn)發(fā)效益就越大，因此消息發(fā)送節(jié)點在消息傳輸過程中會選擇社會關(guān)系更親密且傳輸意愿更高的節(jié)點作為中繼節(jié)點。但由于移動智能設(shè)備的資源受限且聯(lián)絡(luò)廣泛，節(jié)點容易受網(wǎng)絡(luò)中不可信自私節(jié)點的影響。網(wǎng)絡(luò)中自私節(jié)點會表現(xiàn)出惰性自私，中繼節(jié)點與消息發(fā)送節(jié)點的社會關(guān)系親密但不愿意參與消息的轉(zhuǎn)發(fā)甚至惡意丟包，導(dǎo)致整個網(wǎng)絡(luò)消息傳輸性能的降低，造成網(wǎng)絡(luò)消息傳輸?shù)牟豢尚?。如何利用蟻群算法特性的同時有效解決網(wǎng)絡(luò)中自私節(jié)點惰性傳輸問題以提高消息傳輸可信性，并利用節(jié)點的社會關(guān)系選擇傳輸意愿高的中繼節(jié)點，成為設(shè)計可信移動社會網(wǎng)絡(luò)路由算法的關(guān)鍵問題。

1 相關(guān)工作

1.1 蟻群算法

蟻群優(yōu)化算法(ACO)是意大利學者Dorigo M等[3]提出的分布式智能模擬算法。螞蟻在覓食過程時隨機搜索自身周圍的環(huán)境，并在所經(jīng)過的路徑上留下具有信息傳遞作用的信息素以指導(dǎo)其它螞蟻進行路徑選擇。在搜索路徑過程中某條路徑長度越短，螞蟻在該路徑來回次數(shù)越多，因此較短路徑上的信息素含量就越高，最終所有螞蟻尋找食物的路徑會收斂到較短的路徑上。這種蟻群協(xié)作行為便表現(xiàn)出一種信息正反饋現(xiàn)象，即某一路徑長度越短，則其它螞蟻選擇該路徑的概率越大[4]。

文獻[5]中提出的改進蟻群算法在原有蟻群算法的基礎(chǔ)上引入了位置帶概念并使用抵抗素策略達到能量均衡，但該算法對路由性能的提升有限。文獻[6]提出了一種多目標蟻群優(yōu)化算法，該算法通過最小化傳輸距離、傳輸延時和方向且最大化進展和生存時間構(gòu)造移動概率函數(shù)，選擇移動概率最大的節(jié)點作為最佳下一跳節(jié)點，但忽略了節(jié)點的移動性和社會屬性。文獻[7]提出了兼顧能量平衡和擁塞控制的蟻群優(yōu)化路由算法，該算法，選擇具有最大剩余能量、最小路徑花費和最小時延變化的最優(yōu)節(jié)點構(gòu)建路由，同時限制能量不滿足條件的節(jié)點或者路徑傳輸數(shù)據(jù)，但該算法只考慮到節(jié)點的能量消耗，不能避免自私節(jié)點對網(wǎng)絡(luò)的影響。文獻[8]提出了基于蟻群智能的MSN路由算法，通過節(jié)點對間的消息列表為其它節(jié)點發(fā)送消息時選擇合適的中繼節(jié)點提供有效信息，但該算法只考慮到路徑最短和節(jié)點交互次數(shù)，沒有考慮到節(jié)點間路徑的可信。

1.2 可信機會路由

機會網(wǎng)絡(luò)[9]是一種不需要源節(jié)點和目標節(jié)點之間存在完整鏈路，通過節(jié)點隨機移動帶來的相遇實現(xiàn)節(jié)點通信的自組織網(wǎng)絡(luò)。MSN網(wǎng)絡(luò)[10]是具備社會屬性的機會網(wǎng)絡(luò)，其節(jié)點主要是人類使用的移動設(shè)備，節(jié)點之間的通信依靠節(jié)點協(xié)同合作的網(wǎng)絡(luò)。文獻[11]提出網(wǎng)絡(luò)中自私節(jié)點對路由傳輸?shù)挠绊戵w現(xiàn)在傳輸成功率、傳輸延遲和網(wǎng)絡(luò)開銷，中繼節(jié)點的自私行為會導(dǎo)致網(wǎng)絡(luò)中消息傳輸性能的降低。文獻[12]提出了可信概念，可信表示網(wǎng)絡(luò)節(jié)點的行為及其結(jié)果是可以預(yù)測的，利用節(jié)點的可信解決網(wǎng)絡(luò)中自私節(jié)點不參與網(wǎng)絡(luò)合作轉(zhuǎn)發(fā)及惡意節(jié)點丟包行為的問題。文獻[13]提出一種基于蟻群算法的節(jié)點可信安全路由協(xié)議，將節(jié)點信任評估模型引入到蟻群路由算法中，提高無線傳感器網(wǎng)絡(luò)的節(jié)點可信度，以節(jié)點可信度為依據(jù)隔離惰性節(jié)點，增強網(wǎng)絡(luò)安全性，但其迭代算法復(fù)雜度高，對節(jié)點資源消耗較大。文獻[14]提出了動態(tài)信任信息聚合算法，該算法利用反饋信任值聚合方法進行探索，然后基于蟻群算法通過多次循環(huán)尋找出多條較優(yōu)的獨立信任路徑,并獲得最終的反饋信任值，該算法計算周期長，無法適應(yīng)網(wǎng)絡(luò)拓撲的快速變化。文獻[15]提出了基于社會自私性的路由算法，消息在轉(zhuǎn)發(fā)過程中要考慮到節(jié)點的社會屬性和傳輸消息的優(yōu)先級以提高消息傳輸效率，但該算法沒有考慮到節(jié)點的自私行為。

2 可信鄰居節(jié)點集的構(gòu)建

本文基于社會網(wǎng)絡(luò)分析理論描述移動社會網(wǎng)絡(luò)模型和網(wǎng)絡(luò)節(jié)點的社會特征。假設(shè)網(wǎng)絡(luò)節(jié)點同屬于一個族內(nèi)，節(jié)點狀態(tài)相對穩(wěn)定。用圖G=(V,E) 表示一個包含n個節(jié)點的MSN，V={V1,V2,…,Vn}(n≥1) 表示網(wǎng)絡(luò)中移動節(jié)點的集合， ?Vi∈V，Vi表示網(wǎng)絡(luò)中第i個移動節(jié)點，E為節(jié)點間邊e的集合。本文使用二元組 〈Tij,Iij〉 表示消息發(fā)送節(jié)點i對鄰居節(jié)點j的綜合信任值評估和社會親密度評估。

定義1 因節(jié)點社會自私性導(dǎo)致丟包行為的節(jié)點為惰性自私節(jié)點，即自私節(jié)點。

定義2 與節(jié)點進行正常消息交互且沒有自私行為的節(jié)點為可信節(jié)點。

2.1 綜合信任值

綜合信任值Tij是根據(jù)節(jié)點間的歷史交互信息和公共相遇節(jié)點的推薦信息進行的信任值評估，可以有效分析判斷節(jié)點的可信狀態(tài)。通過節(jié)點的綜合信任值評估可以隔離自私節(jié)點參與到消息轉(zhuǎn)發(fā)過程中，保證網(wǎng)絡(luò)消息轉(zhuǎn)發(fā)選擇可信的中繼節(jié)點，避免自私節(jié)點的惰性傳輸。

(1)直接信任值

基于TMS[16]中提出的信任模型，網(wǎng)絡(luò)節(jié)點間的信任值評估服從Beta分布，即Beta(α,β)， 其中αij和βij分別表示節(jié)點i與節(jié)點j成功交互消息的次數(shù)和失敗的次數(shù)。但在實際情況中，Beta分布可能無法準確反映真實的轉(zhuǎn)發(fā)行為，例如由于鏈路的丟失帶來消息的轉(zhuǎn)發(fā)失敗。因此，在評估節(jié)點信任值的時候應(yīng)當考慮消息轉(zhuǎn)發(fā)的不確定性。為了解決這個問題，本文采用了文獻[17]提出的方法，利用D-S理論來量化消息傳輸過程中的不確定性，將節(jié)點i與節(jié)點j之間的交互分為成功交互Sij、 失敗交互Fij和不確定交互Uij， 其計算公式為

(1)

(2)

(3)

(4)

其中，θ是不確定交互中實際成功交互的占比，默認值為0.5[18]。

(2)間接信任值

定義4 節(jié)點i與節(jié)點j對公共相遇節(jié)點直接信任值的相似程度稱為信任相似度cos(i,j)。

節(jié)點i為節(jié)點j的鄰居節(jié)點，節(jié)點i與節(jié)點j相交集的公共相遇節(jié)點集為Ns， 信任相似度cos(i,j) 的公式為

(5)

其中，Ns={N1,N2,…,Nn} 表示公共相遇節(jié)點集，采用信任向量表示節(jié)點i對所有公共相遇節(jié)點的直接信任評估，其表達式為：Tis=[TiN1,TiN2,…,TiNp,…,TiNn]，TiNp(Np∈Ns,1≤p≤n) 表示在節(jié)點i的公共相遇節(jié)點集中節(jié)點Np的直接信任值。

(6)

(3)綜合信任值

(7)

(4)綜合信任值的更新

(8)

其中，ρT是信任值時間衰減系數(shù)。綜合信任值時間衰減系數(shù)ρT取值為0.8。

2.2 構(gòu)建可信鄰居節(jié)點集

消息發(fā)送節(jié)點通過定期發(fā)送Hello報文給通信范圍內(nèi)的中繼節(jié)點，中繼節(jié)點在收到消息發(fā)送節(jié)點發(fā)送的Hello報文后會立刻回應(yīng)ACK報文，消息發(fā)送節(jié)點將發(fā)送ACK報文的中繼節(jié)點構(gòu)建為鄰居節(jié)點集Nv。 蟻群算法通常會將消息發(fā)送節(jié)點通信范圍之內(nèi)的鄰居節(jié)點集Nv都納入到螞蟻探索的節(jié)點候選集中，但鄰居節(jié)點集Nv中可能會存在自私節(jié)點，通過對路由節(jié)點進行信任評估確定中繼節(jié)點的可信狀態(tài)，以有效規(guī)避自私節(jié)點惰性傳輸對消息傳輸?shù)挠绊?，增強網(wǎng)絡(luò)傳輸?shù)目尚判?。依?jù)得到的消息發(fā)送節(jié)點i對中繼節(jié)點j的綜合信任值，對中繼節(jié)點j進行判別：

(1)0

(2)Y≤Tij≤1，表示節(jié)點j是可信節(jié)點，節(jié)點j直接進入節(jié)點i的可信鄰居節(jié)點集Ni。

其中，Y表示可信閾值，Ni為節(jié)點i的可信鄰居節(jié)點集。根據(jù)實驗仿真可知，可信閾值Y取值為0.6。

3 螞蟻啟發(fā)函數(shù)的改進

3.1 社會親密度

移動社會網(wǎng)絡(luò)的主要載體是人，因此節(jié)點移動過程中帶有人類社會關(guān)系特征。在MSN網(wǎng)絡(luò)中，節(jié)點的自私性表現(xiàn)為中繼節(jié)點是否愿意轉(zhuǎn)發(fā)消息，而中繼節(jié)點的轉(zhuǎn)發(fā)意愿強度取決于節(jié)點間的社會關(guān)系強度，即節(jié)點間的消息交互是否頻繁。

定義7 節(jié)點i與節(jié)點j間社會關(guān)系強度的度量稱為社會親密度Iij。

社會親密度Iij反映了網(wǎng)絡(luò)局部拓撲情況，將消息轉(zhuǎn)發(fā)給社會關(guān)系緊密、頻繁接觸的節(jié)點更容易建立穩(wěn)定的消息傳遞鏈路。社會親密度Iij的值越大，說明節(jié)點i和節(jié)點j之間的關(guān)系越緊密，中繼節(jié)點傳輸意愿更積極，傳輸消息的可靠性越高；反之說明節(jié)點i與節(jié)點j之間的關(guān)系越疏遠，傳輸消息的可靠性越低。設(shè)Cij為節(jié)點i向節(jié)點j轉(zhuǎn)發(fā)的消息次數(shù)，即節(jié)點i到節(jié)點j的出度值。社會親密度Iij計算公式為

(9)

(10)

(11)

3.2 構(gòu)建啟發(fā)函數(shù)

蟻群算法中的啟發(fā)素具有局部性，配合具有全局性的信息素，使得轉(zhuǎn)發(fā)決策更高效。但傳統(tǒng)的啟發(fā)函數(shù)僅考慮到節(jié)點間的距離，將節(jié)點間距離作為唯一的啟發(fā)式因子，無法引導(dǎo)消息傳輸給傳輸意愿更高的節(jié)點。本算法在原啟發(fā)函數(shù)的基礎(chǔ)上增加了社會親密度，通過節(jié)點間的社會關(guān)系構(gòu)建新的啟發(fā)函數(shù)，在充分利用傳輸意愿高且傳輸可信中繼節(jié)點基礎(chǔ)上，提高節(jié)點中繼傳輸?shù)目煽啃?。啟發(fā)函數(shù)計算公式為

(12)

其中，Iij表示節(jié)點i評估節(jié)點j社會親密度，dij表示節(jié)點i和節(jié)點j的空間距離。

通過將反映節(jié)點間社會關(guān)系強度的社會親密度引入到啟發(fā)函數(shù)中，可引導(dǎo)節(jié)點將消息轉(zhuǎn)發(fā)給關(guān)系更緊密、消息交互更頻繁的中繼節(jié)點，增加了網(wǎng)絡(luò)傳輸?shù)目煽啃浴?/p>

4 Trust-ACO算法的提出

傳統(tǒng)蟻群算法通過螞蟻在其所經(jīng)過路徑上留下的信息素進行路由選擇，但其不能應(yīng)對MSN網(wǎng)絡(luò)中節(jié)點社會自私性導(dǎo)致的消息傳輸問題。Trust-ACO算法在傳統(tǒng)蟻群算法基礎(chǔ)上進行了算法改進，通過綜合信任值構(gòu)建消息發(fā)送節(jié)點可信鄰居節(jié)點集，避免惰性自私節(jié)點參與到消息傳輸中以提高消息傳輸?shù)目尚判裕灰蒙鐣H密度改進啟發(fā)函數(shù)，將消息轉(zhuǎn)發(fā)給傳輸距離近且社會關(guān)系緊密、傳輸意愿積極的中繼節(jié)點提高消息傳輸性能。

4.1 狀態(tài)轉(zhuǎn)移概率函數(shù)

消息發(fā)送節(jié)點在進行消息傳輸時，如果目的節(jié)點在其鄰居節(jié)點集Nv中，則直接轉(zhuǎn)發(fā)給目的節(jié)點，并更新相應(yīng)的鏈路信息。如果目的節(jié)點不在其鄰居節(jié)點集Nv范圍內(nèi)，則查看可信鄰居節(jié)點集Ni并按照狀態(tài)轉(zhuǎn)移概率函數(shù)來確定下一跳中繼節(jié)點。狀態(tài)轉(zhuǎn)移概率函數(shù)由信息素和啟發(fā)函數(shù)綜合決定，根據(jù)文獻[20]其計算公式為

(13)

其中，Ni為消息發(fā)送節(jié)點i通過綜合信任值構(gòu)建的可信鄰居節(jié)點集，τij為消息發(fā)送節(jié)點i到中繼節(jié)點j的信息素值，ηij為消息發(fā)送節(jié)點i到中繼節(jié)點j基于社會關(guān)系強度的啟發(fā)函數(shù)值；參數(shù)α與β分別為信息素τij和啟發(fā)值ηij的權(quán)重。

4.2 螞蟻信息素含量更新

蟻群每次迭代完成后，會對螞蟻發(fā)現(xiàn)的路徑進行路徑質(zhì)量評估，并對本次迭代中的路徑進行信息素含量更新。螞蟻路徑質(zhì)量計算公式為

(14)

其中，A=0.5[21]是一個預(yù)設(shè)值常量，Iij表示消息發(fā)送節(jié)點i評估中繼節(jié)點j的社會親密度，dij表示消息發(fā)送節(jié)點i與中繼節(jié)點j之間的距離。路徑質(zhì)量評估是基于節(jié)點間的社會親密度，社會親密度越高，節(jié)點間消息傳輸意愿越積極，那么節(jié)點間的路徑質(zhì)量也越高。信息素的更新公式為

(15)

4.3 消息轉(zhuǎn)發(fā)策略

(1)若目的節(jié)點在鄰居節(jié)點集中，則將消息發(fā)送給目的節(jié)點，并更新相關(guān)信息；

(2)若消息發(fā)送節(jié)點不在目的節(jié)點的鄰居節(jié)點中，則該節(jié)點根據(jù)式(8)計算當前鄰居節(jié)點綜合信任值決定鄰居節(jié)點是否加入可信鄰居節(jié)點集Ni， 對可信鄰居節(jié)點按式(13)中的狀態(tài)轉(zhuǎn)移概率函數(shù)選擇下一跳中繼節(jié)點；若可信鄰居節(jié)點集Ni中沒有可信節(jié)點，則不進行消息轉(zhuǎn)發(fā)，將消息保留在本節(jié)點中；

(3)重復(fù)以上過程直到消息到達目的節(jié)點或者超時被丟棄為止。

算法主要流程如圖1所示。

圖1 算法流程

算法的偽代碼如下：

算法： 族內(nèi)可信蟻群機會路由改進算法(Trust-ACO)

Input： 網(wǎng)絡(luò)中所有節(jié)點

Output： 下一跳節(jié)點

Begin

節(jié)點i接收消息(destd) //消息目的節(jié)點為節(jié)點d

節(jié)點i發(fā)送Hello報文，構(gòu)建鄰居節(jié)點集Nv

If(d∈Nv) //目的節(jié)點d在鄰居節(jié)點集Nv中

節(jié)點i發(fā)送消息

Else //目的節(jié)點d不在鄰居節(jié)點集Nv中

節(jié)點i計算鄰居節(jié)點集Nv中所有節(jié)點的綜合信任值T

For (j=0;j

If(Y≤Tij≤1)

jjoinNi//節(jié)點j加入節(jié)點i的可信鄰居節(jié)點集Ni

Else

dropj//節(jié)點j不加入節(jié)點i的可信鄰居節(jié)點集Ni

If(Ni≠?) //可信鄰居節(jié)點集Ni中存在可信節(jié)點

If(NUM(Ni)>1) //可信鄰居節(jié)點集Ni中有一個以上可信節(jié)點

For (j=0;j

計算節(jié)點i的螞蟻啟發(fā)函數(shù)ηij

計算節(jié)點i的狀態(tài)轉(zhuǎn)移函數(shù)Pij

按Pij選擇下一跳節(jié)點， 轉(zhuǎn)發(fā)消息

評估螞蟻路徑質(zhì)量Qij， 更新螞蟻信息素

Else //可信鄰居節(jié)點集Ni中只有一個可信節(jié)點

節(jié)點i轉(zhuǎn)發(fā)消息

評估螞蟻路徑質(zhì)量Qij， 更新螞蟻信息素

Else //可信鄰居節(jié)點集Ni中沒有可信節(jié)點

節(jié)點i保留消息

Return 下一跳節(jié)點

End

5 仿真實驗

本文利用ONE仿真軟件作為實驗?zāi)M平臺來實現(xiàn)Trust-ACO算法，并對其性能進行驗證。本文將Trust-ACO算法與Epidemic、PROPHET、ACO(ant colony optimization)算法進行比較。Epidemic算法在兩個節(jié)點相遇時交換對方緩存隊列中的消息ID，交換對方攜帶而自己沒有攜帶的消息。PROPHET算法是一種基于節(jié)點接觸概率的路由算法，當兩個節(jié)點相遇時，它們的接觸概率增加，否則隨時間衰退。ACO算法是一種基于蟻群算法優(yōu)化的網(wǎng)絡(luò)路由算法，通過探測消息發(fā)送節(jié)點與中繼節(jié)點間的距離大小和路徑上的信息素引導(dǎo)消息傳輸給下一跳節(jié)點。

5.1 仿真環(huán)境

實驗采用ONE模擬器中MIT Reality[22]數(shù)據(jù)集一個月中連續(xù)工作日的相遇數(shù)據(jù)，該數(shù)據(jù)集對隨機抽取的97名MIT的學生和教職工進行了數(shù)據(jù)采樣，采樣時間為246天，共記錄了110多次彼此間的相遇機會。MIT Reality數(shù)據(jù)集將移動基站信息作為用戶的位置軌跡數(shù)據(jù)，同時還包含了用戶的社會關(guān)系屬性。數(shù)據(jù)集由于受節(jié)點間社會關(guān)系及節(jié)點個體自私趨利等因素的影響，適用于本文的研究背景。本文使用其數(shù)據(jù)集中240 min內(nèi)移動軌跡作為實驗中節(jié)點的移動軌跡。具體設(shè)置見表1。

表1 實驗仿真參數(shù)設(shè)置

網(wǎng)絡(luò)性能評估主要為傳輸成功率和消息傳輸時延。傳輸成功率為發(fā)送成功的消息數(shù)與產(chǎn)生的總消息數(shù)的比值，表征了算法的傳輸可靠性；消息傳輸時延為消息從源節(jié)點轉(zhuǎn)發(fā)到目的節(jié)點的平均消耗時間，指標評估路由算法的延遲性。

5.2 實驗結(jié)果與分析

本實驗通過分析不同消息生存時間、網(wǎng)絡(luò)中自私節(jié)點數(shù)和對社會親密度的情況下算法的性能，并與其它算法在相同環(huán)境下進行性能對比，分析本算法性能優(yōu)劣。

如圖2所示，仿真顯示Trust-ACO算法隨著可信閾值增加其傳輸成功率的變化情況。隨著可信閾值的增加，傳輸成功率先增加后減少。在低可信閾值時，存在自私行為的中繼節(jié)點被判定為可信節(jié)點加入到消息傳輸過程中，該節(jié)點因社會自私性存在的丟包行為影響了網(wǎng)絡(luò)中消息的傳輸成功率；在高可信閾值時，網(wǎng)絡(luò)中可信的中繼節(jié)點數(shù)量減少，消息無法有效轉(zhuǎn)發(fā)到目標節(jié)點，導(dǎo)致傳輸成功率下降。從實驗仿真圖可以看到可信閾值在區(qū)間[0.5,0.7]時，有較好的傳輸成功率，因此可信閾值取0.6時，網(wǎng)絡(luò)性能最佳。

圖2 不同可信譽值時算法性能對比

如圖3所示，仿真顯示4種路由算法隨著消息生存周期的增加其性能指標的變化情況。隨著消息生存周期的增加，Epidemic和PROPHET算法傳輸率隨時間緩慢提升，因為這兩種算法采用了無限副本轉(zhuǎn)發(fā)策略，消息生存周期的增加會讓網(wǎng)絡(luò)存在大量的消息，導(dǎo)致節(jié)點緩存中沒有及時轉(zhuǎn)發(fā)的消息被刪除從而降低了傳輸率。而Trust-ACO算法由于考慮了綜合信任值和社會親密度在傳輸成功率方面有一定程度的提升，在消息生存時間達到120 min后其傳輸成功率達到60%且繼續(xù)增加。ACO算法隨著消息生存周期的增加消息轉(zhuǎn)發(fā)成功率最低。在消息傳輸時延方面Trust-ACO算法相對于其它算法比較小。

如圖4所示，在網(wǎng)絡(luò)中設(shè)置一定數(shù)量的自私節(jié)點，顯示4種路由算法隨著自私節(jié)點數(shù)量的增加其性能指標的變化情況。當自私節(jié)點數(shù)量的增加時，4種路由算法的傳輸成功率都有一定下降。Trust-ACO算法在性能方面較優(yōu)越，當自私節(jié)點數(shù)不超過20時傳輸成功率在80%以上；當網(wǎng)絡(luò)中自私節(jié)點數(shù)量為40時傳輸成功率為69%。Epidemic和PROPHET算法因無法抑制節(jié)點的自私行為，消息傳輸成功率下降明顯。ACO算法由于沒有采用避免自私節(jié)點的路由策略，節(jié)點自私行為對其影響較大。

如圖5所示，設(shè)置不同的消息發(fā)送間隔時間，顯示4種路由算法性能的變化情況。在網(wǎng)絡(luò)中節(jié)點產(chǎn)生消息越多，節(jié)點間消息交互越頻繁，則節(jié)點間社會關(guān)系越親密，即消息產(chǎn)生間隔時間越短，節(jié)點社會親密度越高。隨著消息產(chǎn)生間隔時間的增加，Epidemic和PROPHET算法的傳輸成功率和消息傳輸時延沒有明顯的變化。由于Trust-ACO算法考慮到節(jié)點間的社會親密度，表現(xiàn)出一定程度上的性能優(yōu)勢，在消息產(chǎn)生間隔時間為5 min時，由于節(jié)點間頻繁的消息傳輸，其節(jié)點間社會親密度變高，消息的傳輸成功率為85%，且隨著間隔時間增加，消息傳輸成功率呈下降趨勢。ACO算法由于沒有考慮社會屬性，消息傳輸率保持60%左右。在消息傳輸時延方面，Trust-ACO算法在消息產(chǎn)生間隔時間低于20 min時優(yōu)于其它算法。

圖3 不同消息生存周期時算法性能對比

圖4 不同自私節(jié)點數(shù)量時算法性能對比

圖5 不同消息產(chǎn)生間隔時間時算法性能對比

如圖6所示，顯示設(shè)值不同的消息周期數(shù)，可信節(jié)點和自私節(jié)點的綜合信任值變化情況。可信節(jié)點的平均綜合信任值隨著周期的增加呈上升趨勢且最后接近于1；而自私節(jié)點的平均綜合信任值隨著周期增加呈下降趨勢且最后接近于0.1，表明綜合信任值可有效區(qū)分出網(wǎng)絡(luò)中的可信節(jié)點和自私節(jié)點。

圖6 節(jié)點綜合信任值隨周期變化情況

6 結(jié)束語

本文通過分析移動社會網(wǎng)絡(luò)的特征，提出了一種族內(nèi)基于可信蟻群算法的路由算法。該算法利用蟻群算法分布式、自適應(yīng)的特性在網(wǎng)絡(luò)中尋找最優(yōu)路徑，首先利用節(jié)點間的歷史交互信息評估節(jié)點綜合信任值以有效選擇網(wǎng)絡(luò)中的可信鄰居節(jié)點，然后基于社會親密度的狀態(tài)轉(zhuǎn)移函數(shù)選擇轉(zhuǎn)發(fā)意愿更高、關(guān)系更緊密的中繼節(jié)點進行消息的傳輸，最后實現(xiàn)族內(nèi)的可信消息轉(zhuǎn)發(fā)策略。然而，MSN網(wǎng)絡(luò)中移動設(shè)備自身能量和緩存資源有限且計算資源較弱，算法如何在節(jié)點資源受限時依然有較優(yōu)的傳輸成功率和傳輸時延，是進一步研究重點。