MSN下族內可信蟻群機會路由改進算法

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

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

0 引 言

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

1 相關工作

1.1 蟻群算法

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

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

1.2 可信機會路由

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

2 可信鄰居節點集的構建

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

定義1 因節點社會自私性導致丟包行為的節點為惰性自私節點，即自私節點。

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

2.1 綜合信任值

綜合信任值Tij是根據節點間的歷史交互信息和公共相遇節點的推薦信息進行的信任值評估，可以有效分析判斷節點的可信狀態。通過節點的綜合信任值評估可以隔離自私節點參與到消息轉發過程中，保證網絡消息轉發選擇可信的中繼節點，避免自私節點的惰性傳輸。

(1)直接信任值

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

(1)

(2)

(3)

(4)

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

(2)間接信任值

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

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

(5)

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

(6)

(3)綜合信任值

(7)

(4)綜合信任值的更新

(8)

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

2.2 構建可信鄰居節點集

消息發送節點通過定期發送Hello報文給通信范圍內的中繼節點，中繼節點在收到消息發送節點發送的Hello報文后會立刻回應ACK報文，消息發送節點將發送ACK報文的中繼節點構建為鄰居節點集Nv。 蟻群算法通常會將消息發送節點通信范圍之內的鄰居節點集Nv都納入到螞蟻探索的節點候選集中，但鄰居節點集Nv中可能會存在自私節點，通過對路由節點進行信任評估確定中繼節點的可信狀態，以有效規避自私節點惰性傳輸對消息傳輸的影響，增強網絡傳輸的可信性。依據得到的消息發送節點i對中繼節點j的綜合信任值，對中繼節點j進行判別：

(1)0

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

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

3 螞蟻啟發函數的改進

3.1 社會親密度

移動社會網絡的主要載體是人，因此節點移動過程中帶有人類社會關系特征。在MSN網絡中，節點的自私性表現為中繼節點是否愿意轉發消息，而中繼節點的轉發意愿強度取決于節點間的社會關系強度，即節點間的消息交互是否頻繁。

定義7 節點i與節點j間社會關系強度的度量稱為社會親密度Iij。

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

(9)

(10)

(11)

3.2 構建啟發函數

蟻群算法中的啟發素具有局部性，配合具有全局性的信息素，使得轉發決策更高效。但傳統的啟發函數僅考慮到節點間的距離，將節點間距離作為唯一的啟發式因子，無法引導消息傳輸給傳輸意愿更高的節點。本算法在原啟發函數的基礎上增加了社會親密度，通過節點間的社會關系構建新的啟發函數，在充分利用傳輸意愿高且傳輸可信中繼節點基礎上，提高節點中繼傳輸的可靠性。啟發函數計算公式為

(12)

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

通過將反映節點間社會關系強度的社會親密度引入到啟發函數中，可引導節點將消息轉發給關系更緊密、消息交互更頻繁的中繼節點，增加了網絡傳輸的可靠性。

4 Trust-ACO算法的提出

傳統蟻群算法通過螞蟻在其所經過路徑上留下的信息素進行路由選擇，但其不能應對MSN網絡中節點社會自私性導致的消息傳輸問題。Trust-ACO算法在傳統蟻群算法基礎上進行了算法改進，通過綜合信任值構建消息發送節點可信鄰居節點集，避免惰性自私節點參與到消息傳輸中以提高消息傳輸的可信性；引用社會親密度改進啟發函數，將消息轉發給傳輸距離近且社會關系緊密、傳輸意愿積極的中繼節點提高消息傳輸性能。

4.1 狀態轉移概率函數

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

(13)

其中，Ni為消息發送節點i通過綜合信任值構建的可信鄰居節點集，τij為消息發送節點i到中繼節點j的信息素值，ηij為消息發送節點i到中繼節點j基于社會關系強度的啟發函數值；參數α與β分別為信息素τij和啟發值ηij的權重。

4.2 螞蟻信息素含量更新

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

(14)

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

(15)

4.3 消息轉發策略

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

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

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

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

圖1 算法流程

算法的偽代碼如下：

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

Input： 網絡中所有節點

Output： 下一跳節點

Begin

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

節點i發送Hello報文，構建鄰居節點集Nv

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

節點i發送消息

Else //目的節點d不在鄰居節點集Nv中

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

For (j=0;j

If(Y≤Tij≤1)

jjoinNi//節點j加入節點i的可信鄰居節點集Ni

Else

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

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

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

For (j=0;j

計算節點i的螞蟻啟發函數ηij

計算節點i的狀態轉移函數Pij

按Pij選擇下一跳節點， 轉發消息

評估螞蟻路徑質量Qij， 更新螞蟻信息素

Else //可信鄰居節點集Ni中只有一個可信節點

節點i轉發消息

評估螞蟻路徑質量Qij， 更新螞蟻信息素

Else //可信鄰居節點集Ni中沒有可信節點

節點i保留消息

Return 下一跳節點

End

5 仿真實驗

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

5.1 仿真環境

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

表1 實驗仿真參數設置

網絡性能評估主要為傳輸成功率和消息傳輸時延。傳輸成功率為發送成功的消息數與產生的總消息數的比值，表征了算法的傳輸可靠性；消息傳輸時延為消息從源節點轉發到目的節點的平均消耗時間，指標評估路由算法的延遲性。

5.2 實驗結果與分析

本實驗通過分析不同消息生存時間、網絡中自私節點數和對社會親密度的情況下算法的性能，并與其它算法在相同環境下進行性能對比，分析本算法性能優劣。

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

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

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

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

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

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

圖4 不同自私節點數量時算法性能對比

圖5 不同消息產生間隔時間時算法性能對比

如圖6所示，顯示設值不同的消息周期數，可信節點和自私節點的綜合信任值變化情況?？尚殴濣c的平均綜合信任值隨著周期的增加呈上升趨勢且最后接近于1；而自私節點的平均綜合信任值隨著周期增加呈下降趨勢且最后接近于0.1，表明綜合信任值可有效區分出網絡中的可信節點和自私節點。

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

6 結束語

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