具有路由性能和蟻群優化的移動Ｐ２Ｐ路由策略

（電子科技大學 計算機科學與工程學院， 成都610054）

摘 要：目前的移動P2P網絡路由策略不能較好適應網絡拓撲結構的動態多變、網絡和移動設備的資源有限等特點，以及不能較好解決路由建立和維護所帶來的網絡擁塞和資源消耗。針對上述問題，采用有限洪泛路由查詢和移動agent路由查詢相結合的策略，為每個移動節點提供豐富可靠、及時高效的路由信息。同時，使用改進的蟻群算法，綜合考慮網絡帶寬、時延等多個路由性能指標，作為路由策略中路由選擇機制。仿真研究證明，將所提出的理論與方法應用于移動P2P的路由選擇和維護等問題，本算法在控制消息的開銷、平均響應效率等方面具有良好的性能，對于網絡的動態多變具有很強的適應能力。

關鍵詞：移動P2P網絡;路由策略;蟻群算法;移動agent;信息素

中圖分類號：TP393 文獻標志碼：A

文章編號：10013695(2009)01025606

Routing scheme based on routing performance and antcolonyoptimization for mobile peertopeer networks

NIU Xinzheng， ZHOU Mingtian， SHE Kun

(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:Current routing algorithms were not suitable for mobile P2P networks because of topology variability and resource limitation. Besides， these algorithms did’t reduce the network congestion and resource cost problem caused by routing establishment and maintenance. To solve this problem， this paper proposed a routing discovery algorithm based on the restriction flooding and mobile agents routing search， which could establish effective routing resources with enough information. Moreover，this paper used improved ant colony algorithm and synthetically analyze routing performance objects such as network bandwidth， delay for routing selection algorithm. The analytical and experimental results show this algorithm performs well in controlling the route overhead and average recall efficiency， etc. And it can tolerate the situation such as dynamic and changeful network.

Key words:mobile P2P(peertopeer) network; routing scheme; ant colony algorithm; mobile agent; pheromone

同傳統Internet下的P2P相比，移動P2P網絡會遇到以下挑戰[1]：基礎設施；命名和路由；資源發現；安全等。而其中路由策略問題尤其關鍵，它是整個移動P2P網絡能否滿足用戶移動應用的重要保證。

1 相關工作

研究者對移動P2P網絡的路由問題進行了深入的研究。文獻[2]展示了如何在沒有任何全局網絡拓撲的情況下，通過建立簇頭間的連接來建立節點間全局的骨干連接。文獻[3]提出了基于hash結構的移動P2P中間件框架。該框架包括兩個部分，即固定層和移動層。固定層部分可以幫助移動層部分得到路由策略中移動節點的網絡地址。文獻[4]重用了擴展的動態源路由協議，并且采用按需路由的算法，以及廣播的方式進行路由發現。文獻[5]提出了一個支持動態網絡中上下文感知應用的中間件框架（TOTA）。通過在網絡上傳播的自保持的分布式元組，提出了基于內容的動態網絡信息訪問和路由。文獻[6]提出了一種移動P2P網絡的資源發現協議。該協議是CAN的一種改進，加速了資源搜索過程，實現卻相對比較復雜。文獻[7]提出內容驅動路由和數據分發算法。通過建立數據的內容概要，及分發該內容概要到最適合的節點。同時，資源的查詢包會被發送到最大可能提供資源的節點上。基于這種內容概要驅動和數據分發的方式，路由機制被建立。而該算法在網絡中傳輸的數據的內容概要是網絡最大的隱患，尤其是對于網絡的節點數目上升時，會帶來過大的信息傳輸數量。文獻[8]通過擴展ODMRP協議，提出了一套適應性消息分發機制和路由算法。而由于ODMRP采用洪泛的方式，路由協議開銷特別大，冗余數據比較多。

通過上述分析，文獻[2]啟示可以通過分簇，建立簇頭連接的方法實現全網的連接。文獻[3]需要固定層中節點的支撐。文獻[5]啟示可以通過在網絡上傳播的自保持的分布式元組，提供有效的動態網絡信息訪問和路由。而文獻[4，6~8]提到的路由算法均有缺陷，如洪泛消息的方式、實現復雜等。



2 路由算法思路描述

本文根據文獻[2，5]的啟示，分析了文獻[3，4，6~8]中存在的問題，并且考慮到基于移動agent設計的路由策略比較適合動態多變、對等式結構的移動網絡[12~17]，提出了一種新的基于移動agent的具有路由性能和蟻群優化的路由策略。路由思路簡述如下：

a）在系統運行的初期，移動用戶的路由表為空。通過局部路由搜索，初步建立移動用戶的路由表。同時，當解決移動用戶路由表中的路由經常發生錯誤等問題時，也需要局部路由搜索。

b）隨著系統的運行，移動agent可以為每個移動用戶帶來廣泛的路由信息。其中，移動節點或移動agent有選擇地使用對方的路由信息，有選擇地進行交互和合作。路由發現工作不斷進行。同時，根據路由選擇策略，移動節點決定數據包的轉移方向，移動agent決定下一步巡游的移動節點。

c）在系統穩定后，隨時監控網絡的擁塞、移動agent的錯誤等，并及時作出調整。

3 基于移動agent的路由算法

31 路由發現策略

定義1 n＋m表示所有移動節點和移動agent的總數。其中：n表示移動節點平均個數，m表示網絡中巡游的移動agent平均個數，則網絡中第i個移動節點惟一的網絡標志ID可以表示為Mi，m≤i≤n+m，第i個移動agent惟一的網絡標志ID表示為MAi，1≤i≤m。同時，第i個移動節點的鄰居節點集合表示為NMi，NMi=MjMj為Mi傳輸半徑內的移動節點m≤i，j≤n+m，i≠j，移動agent MAi或者移動節點Mi的路由表表示為LUi，LUi={lUi1，lUi2，…，lUiN}。其中N≥0，1≤i≤n+m。而具體第N條路由lUiN(如路徑Mi→Mk→Mj)表示為(Mi，Mk，Mj)，縮寫為(Mi，Mj)。每個移動agent的生命期均設置相同的值，表示為TLMA。

定義2 使用移動Ad hoc網絡中的分簇的方法[9]，將整個移動P2P網絡分成w個簇，1≤w≤n。Ci(1≤i≤w)表示移動節點組成的第i個簇集合，wi=1Ci=n。其中，簇頭是按照分簇算法選舉出來的負責協調和管理其簇內所有節點的節點。本文規定一個簇的簇頭數等于2，包括主簇頭和備份簇頭。第i個簇的主簇頭表示為ci0，備份簇頭表示ci1。除簇頭外的其他簇內節點稱為簇成員，可以表示為cij，2≤j≤|Ci|。

311 局部路由搜索

由于鄰居節點能夠得到的路由信息有限，頻繁地通過廣播來查找路由信息的局部路由搜索，會造成網絡的擁塞。同時，基于agent的全局路由搜索需要一定收斂時間，并且移動P2P網絡中不允許充斥過多巡游的移動agent，以及為了防止從移動agent帶來的路由陷入局部最優等。因此，路由發現策略分為全局路由搜索和局部路由搜索。為了較迅速地發現路由，通過控制跳數的洪泛方法，向鄰居節點發送路由查詢廣播，獲取鄰居節點可用的路由信息，展開局部路由搜索。本文控制洪泛的跳數為1跳，只是通過鄰居節點來應答該查詢包。

312 全局路由搜索

1）移動agent的路由搜索

本文根據基于移動agent的路由搜索模式，設計了路由策略的全局路由搜索。簡述如下：

移動agent采集的路由信息來自兩個部分：a）節點自身采集到的路由信息，這部分路由信息具有最直接的來源；b）通過移動agent間以及與移動節點的協作帶來的路由信息，對于間接獲得的路由信息給予標志，表明該路由信息是旁聽得到，也方便移動節點有選擇地使用移動agent的路由信息。移動節點對移動agent所攜帶的信息進行過濾，找出感興趣和值得信賴的路由信息如根據路由信息所包含的信任度判斷，記錄在自己的路由表中。同時，移動agent也有選擇的部分采納通過協作獲得的路由信息。正如研究者們所采用的基于黑板的路由知識協作、交換模式，這也是在蟻群算法［11］中用到的方法。通過在每個移動節點中一塊發布信息的黑板來共享和交換信息，所有的移動節點、移動agent均可以讀寫黑板，通過這塊黑板來交互路由信息。

2）移動agent的產生和管理

本文選用最低節點移動性分簇算法[9]，每個簇頭負責本簇移動agent的產生和維護，并保存本簇移動agent的相關數據，簇頭間可以互相通信以及協調管理移動agent。當系統運行的初期，在劃分網絡成不同的簇以及建立簇頭后，簇頭間開始協商，確定初期每個簇投放的移動agent的數目和移動agent生命期結束的機制。本文采用基于時間的方式來結束移動agent的生命。簇頭在確定移動agent生命期的長短和數量后，在自己簇內投放適當的移動agent運行，并監控本簇內所有運行的移動agent，包括別的簇投放移動到本簇內的移動agent。

32 路由選擇策略

移動agent的全局搜索行為，可以描述為蟻群尋路的群體行為。移動agent巡游的本質問題可以通過蟻群算法［11］來設法解決，現簡述路由選擇策略思路如下：a）通過使用蟻群算法信息素擴散的特征和求出的轉移概率值的高低排序的方法指導移動agent和移動節點數據包的路由選擇；b）兼顧考慮路由信息中重要的路由性能指標，共同作為路由算法中的路由選擇策略。

321 蟻群路由選擇模型

1）模型建立思想

移動節點和移動agent路由表中的每條路由表項均包含了一個表示該路徑可信任大小的參數，稱為信任度。該參數越大，表示這條路徑越值得信任，可以優先使用。對于移動節點來說，如果是轉發的數據包，該數據包會攜帶發送數據包的節點給予的路由項，而該數據包應該是按照該路由項的指示完成路由選擇，但也必須根據實際情況作出調整，如網絡發生了變化等。因此，需要根據該數據包攜帶的路由，以及3.2.2節中路由性能指標，判斷該路由是否仍然可達目的節點。如果是移動節點本身發送的數據包或者對別的移動節點轉發的數據包的調整，查詢自己的路由表，找到可到達數據包目的節點的路由。對于同時可滿足節點需求的多個路由表項，根據轉移概率值和路由性能指標共同作為選擇路徑的依據。對于移動agent來說，為了擴大其搜索區域，根據經過的移動節點的路由表，計算所有以該節點的鄰居節點（上一步經過的節點除外）為出口的路由概率值，根據概率值以及路由性能指標，綜合考慮選擇的路徑。

2）模型具體描述

定義3 對于移動節點或移動agent的路由表中的路徑表項（Mi，Mk，…，Ms，…，Mj）表示的路徑為Mi→Mk…→Ms…→Mj，Mk表示該路由的第二個移動節點，節點Ms是該路由的中間節點。從移動節點Mi到移動節點Mj之間的跳數表示為dMiMjτMiMkMj(t)表示t時刻該路徑的信任度大小。系統運行的開始時，各移動節點間建立的路徑信任度為1（即保證新建立的路由能夠被使用）。 當τMiMkMj(t)0.1時，表示該路由表項的路徑不可信任，不被使用。同時，有τMiMkMj(t)=τMiMkMs(t)。allowedMi是路徑上的移動節點Mi數據包或移動agent MAi在移動節點Mi處的下一步可以選擇移動的移動節點的集合，allowedMiNMi。

1)移動節點路由選擇

τMiMkMj(t)表示t時刻從移動節點Mi到移動節點Mj之間存在路徑的信任度大小，Mk表示下一步轉移的移動節點，Mk∈allowedMi。ηMiMkMj為選擇從移動節點Mi轉移到移動節點Mj的路徑表項的期望程度。可以取

ηMiMkMj=1/dMiMj(1)

基于蟻群算法構造移動節點Mi的數據包轉移概率函數PMiMiMj(t)，PMiMiMj(t)表示在t時刻移動節點Mi的數據包選擇路由表中的路徑表項(Mi，Mj)的概率。其計算式如式(2)所示。

PMiMiMj=ταMiMkMj(t)ηβMiMkMj(t)/Mg∈allowedMiταMiMgMj(t)′η βMiMgMj(t)′

if Mk∈allowedMi，路由可以表示為（Mi，Mk，…，Mj）

并且Mg∈allowedMs，路由可以表示為（Mi，Mg，…，Mj）

0otherwise(2)

其中：α表示該路徑表項的信任度對移動節點選擇路徑所起的作用大小；β表示ηMiMkMj的重要程度。

2)移動agent的路由選擇

MiMk(t)表示在t時刻移動agent MAi選擇所經過移動節點Mi的路由表中所有以鄰居節點Mk為下一個移動節點的路徑表項的信任度平均值。而ηMiMk=1，LkUi表示移動節點Mi的路由表中所有以鄰居節點Mk為出口的路由表項的集合。

MiMk(t)=[τMiMkMj(t)(Mi，Mj)∈LkUi/|allowedMi| ]Mk∈allowedMi(3)

基于蟻群算法構造移動agent MAi轉移概率函數PMiMiMk(t)，

PMiMiMk(t)表示在t時刻移動agent MAi選擇所經過移動節點Mi的鄰居節點Mk的概率。其計算式如式(4)所示。

PMiMiMk=αMiMk(t)/Mg∈allowedMiαMiMg(t)′

if Mk∈allowedMi

0otherwise(4)

其中：α表示該路徑表項的信任度對移動agent選擇路徑所起的作用大小。

3)信任度的修改

移動節點的路由表項信任度發生改變，主要有兩種原因：

a）隨著時間的推移，路徑被信任的程度應該被下降，移動節點的所有路由表項信任度需要發生改變。因此，當每次移動節點的數據包或移動agent需要通過信任度因素決定路由的下一個移動節點時，需要對移動節點的所有路由表項的信任度作一次更新。

b)移動節點獲得了新的路由信息，并且包含節點路由表中的相關表項，移動節點的該路由表項信任度需要發生改變。因此，當移動節點通過洪泛的方法或者移動agent巡游方式，帶來的路由信息中包含移動節點路由表中的相關表項時，需要對該相關表項的信任度進行更新。

移動agent的路由表項信任度發生改變，主要是由于以下兩種原因：

（a）隨著時間的推移，路徑所包含的信任度值應該被下降，移動agent攜帶的所有路由表項的信任度需要發生改變。因此，在別的移動agent或移動節點使用前，需要對移動agent的所有路由表項的信任度作一次更新。

(b)移動agent獲得了新的路由信息，并且包含移動agent路由表中的相關表項，移動agent的該路由表項信任度需要發生改變。因此，當移動agent通過移動節點或別的移動agent的路由表，帶來的路由信息中包含移動agent路由表中的相關表項時，需要對該相關表項的信任度進行更新。

信任度可以通過下面的方法來修改。在經過了w個時刻，移動節點Mi或移動agent MAi的某條路徑(Mi，Mj)上的信任度大小要根據式(5)調整。

τMiMkMj(t+w)=

ρ×τMiMkMj(t)if 第一種原因調整信任度ΔτMiMkMj=0

ρ×τMiMkMj(t)+ΔτMiMkMjif 第二種原因調整信任度ΔτMiMkMj≠0（5）

其中：ρ為一個取值在0~1的常數系數，表示殘留信任度的保留部分，(1-ρ)表示信任度的揮發程度。

對于移動節點Mi

ΔτMiMkMj表示在時間w內通過洪泛或所有移動agent帶來的路由信息，在移動節點Mi的路由表項(Mi，Mj)上所釋放的信任度值之和。

ΔτMiMkMj=mr=1

ΔτrMiMkMj+ΔτFMiMkMj

（6）

ΔτrMiMkMj表示第r個移動agent在時間w內，留在移動節點Mi的路由表項(Mi，Mj)上的信任度值。其中，如果第h個移動agent在w時間段內，沒有經過移動節點Mi或沒有包含路由表項(Mi，Mj)的路徑，

ΔτhMiMkMj=0。ΔτFMiMkMj表示在時間w內，通過洪泛帶來的路由信息對信任度的增強值。

根據Dorigo M給出的ant quantity system模型，ΔτrMiMkMj、ΔτFMiMkMj分別為

ΔτrMiMkMj=Q/dMiMj

if 在w時間段內收到的移動agent MAr中包含的路由表項含有（Mi，Mj）路徑0otherwise（7）

Q是一個變量，為修改移動節點Mi路由表的移動agent MAr路由表項(Mi，Mj)信任度的大小。

ΔτFMiMkMj=Q/dMiMj

if 在w時間段內收到的洪泛信息中包含的路由表項含有（Mi，Mj）路徑0otherwise（8）

Q表示修改移動節點Mi路由表的洪泛信息中路由表項(Mi，Mj)信任度的大小。

對于移動agent MAi

ΔτMiMkMj=

m-1r=1ΔτrMiMkMj+

ΔτIMiMkMj（9）

ΔτrMiMkMj表示第r個移動agent在時間w內，留在移動agent MAi的路由項(Mi，Mj)上的信任度值。ΔτIMiMkMj表示時間w內，經過節點Mi時，路由項(Mi，Mj)上信任度的增強值。ΔτIMiMkMj、ΔτrMiMkMj的算法同式(7)(8)的方法。

322 路由選擇的優化

1)路由性能指標描述以及獲取

對于路由選擇策略來說，除了根據蟻群路由選擇模型找到可達目的節點的路由以外，還需要根據不同移動應用，分析一些重要的路由性能指標，對路由選擇進行優化調整，共同作為移動節點或者移動agent選擇路徑的依據。對于移動P2P網絡，以下幾個方面的性能指標應該作為路由選擇的重點：

a）SMR(Mi，Mj)表示路由(Mi，Mj)是否穩定的性能指標。它的獲取：通過信任度因素，每條路由的信任度濃度可以表示該路由被使用的頻度，也表示了該路由具有的任務執行成功率，即該路由的穩定性。

b）BMR(Mi，Mj)表示路由(Mi，Mj)是否擁塞的性能指標。它的獲取：通過路由探測因素，可以通過移動agent巡游、向鄰居節點發送探測包等方式探測帶寬等資源使用情況；通過路由轉移的下一跳節點因素，過多地選擇某個鄰居節點為路由轉移的下一跳節點，會造成以該鄰居節點為下一跳鏈路的擁塞、延遲；通過時間因素，記錄的最后一次與鄰居節點交互的時間，可以分析判斷通過該鄰居節點的路由是否存在擁塞。

c）DMR(Mi，Mj)表示路由(Mi，Mj)是否過期的性能指標。它的獲取：通過時間因素，在移動節點或者移動agent的路由表中，每條路由表項都包含路由最初被建立和最后被修改的時間，可判斷路由是否過期，使移動用戶能夠丟棄過期的路由，選擇修改時間最近的可用路由。

d）HMR(Mi，Mj)表示路由(Mi，Mj)是否長度最短的性能指標。它的獲取：通過路由長度因素，路由表中的每條路由表項均記錄了經歷該路徑的具體跳數，表示了路徑的具體長度，可判斷路由是否路程最短。

e)TMR(Mi，Mj)表示路由(Mi，Mj)是否時間最短的性能指標。它的獲取：通過時間因素，路由表中的每條路由表項均記錄了經歷該路徑的具體耗費時間，可判斷路由是否時間最短。

2)移動節點的數據結構

根據上文的分析，本文使用下面陳述的移動節點和移動agent的數據結構來作為五個關鍵的路由性能指標的數據來源。

如果該路由可以表示為(Mi，Mk，…，Mj)，本文用F(Mi，Mk)表示移動節點Mi使用鄰居節點Mk的頻度；用B(Mi，Mk)表示移動節點Mi與鄰居節點Mk之間的剩余可用帶寬；用LTMiMkMj表示移動節點Mi最后收到、發送該鄰居節點Mk傳輸數據包的時間；用HMiMkMj表示該路由的總跳數；用ITMiMkMj表示該路由建立初始時間；用LTMiMkMj表示該路由信息最后修改時間；用TMiMkMj表示經歷路徑總時間。其中:m≤i，k，j≤n+m。這些參數的值可以通過底層的探測和記錄等方式獲得，它們共同組成了下面各個數據表。

a）鄰居節點使用頻度表（neighbor node using frequency table，NNUFT）。對每個移動節點的路由轉移的下一跳進行控制。向相鄰的鄰居節點發送數據包時，需要作記錄。當以該鄰居節點為出口的數據包過多時，需要作調整。通過該表的值可以具體評價路由是否存在擁塞或擁塞隱患，即BMR(Mi，Mj)。舉例如表1所示。

表1 鄰居節點使用頻度表

節點Mi的鄰居M11…M20

鄰居使用頻度F（Mi，M11）…F（Mi，M20）

b）移動節點的路由表（mobile node routing table，MNRT）。該路由表包括了以移動節點Mi為出發點的具體路由表項的信任度的濃度值、最后修改時間等。通過該表的值可以具體評價路由是否穩定等，即SMR(Mi，Mj)、DMR(Mi，Mj)、HMR(Mi，Mj)、TMR(Mi，Mj)。舉例如表2所示。

表2 移動節點的路由表

節點Mi的鄰居節點該路由的具體描述信任度濃度總跳數/跳路由建立初始時間最后修改時間經歷路徑總時間/s

M20(Mi，M20，…，M40)τMiM20M40(t1)HMiM20M40ITMiM20M40LTMiM20M40TMiM20M40

c）出口網絡資源狀態表（out network resource table，ONRT）。移動節點Mi具有多個不同的鄰居節點作為下一跳的路由轉移節點，這些鄰居節點稱為路由出口。探測所有的鄰居節點為出口的路徑的帶寬等，是該路徑可用網絡資源的狀態估計。通過該表的值具體評價路由是否存在擁塞等，即BMR(Mi，Mj)。舉例如表3所示。

表3 出口網絡資源狀態表

節點Mi的鄰居M11…M20

剩余可用帶寬B(Mi，M11)…B(Mi，M20)

最后傳輸時間LT(Mi，M11)…LT(Mi，M20)

3)移動agent的數據結構

本文用TMAj(Mi，Mk)表示移動agent MAj記錄的從移動節點Mi到達移動節點Mk花費的時間；用BMAj(Mi，Mk)表示移動agent MAj記錄的從節點Mi與Mk之間的可用帶寬。這些參數的值可通過經過的移動節點等方式間接獲得。

a）移動agent的路由表（mobile agent routing table，MART）。通過該表的值可以具體評價路由是否穩定等，即SMR(Mi，Mj)、DMR(Mi，Mj)、HMR(Mi，Mj)、TMR(Mi，Mj)等。舉例如表4所示。

表4 移動agent的路由表

第j個移動agent該路由的具體描述信任度濃度總跳數(跳)路由建立初始時間最后修改時間經歷路徑總時間/s

MAj(Mi，M20，…，M18)τMiM20M18(t2)HMiM20M18ITMiM20M18LTMiM20M18TMiM20M18

b）移動節點間的路程時間表（mobile node distance time table，MNDTT）。移動agent MAj(從Mi出發)記錄從出發節點到目前所在移動節點中所有移動節點間的路程所花費時間，通過該表的值可以具體評價路由是否時間最短，即TMR(Mi，Mj)。舉例如表5(TMAj(M20，M30)表示從移動節點M20~M30花費的時間)所示。

表5 移動節點間的路程時間表

MAjM20…M18

花費時間TMAj(Mi，M20)…TMAj(M35，M18)

c）移動節點間的可用帶寬表（mobile node usable bandwidth table，MNUBT）。移動agent MAj(從Mi出發)記錄從出發節點到目前所在移動節點中所有移動節點間的可用帶寬，通過該表的值可以評價路由是否存在擁塞或擁塞隱患，即BMR(Mi，Mj)。舉例如表6(如BMAj(Mi，Mk)字節表示從移動節點M20~M30可用帶寬)所示。

表6 移動節點間的可用帶寬表

MAjM20…M18

可用帶寬/bps

BMAj(Mi，M20)…BMAj(M35，M18)

4 算法有效性證明

41 正確性證明

定理1 該算法搜索的路由是無環的路徑。

證明 a)局部路由搜索。對于移動節點Mi，向鄰居節點集合NMi所有的移動節點發送路由探測包REQUEST。由于在算法的初期，移動節點Mi與移動節點Mj均只是知道身邊可達的鄰居節點的信息。所以移動節點Mj返回的移動節點Mi的信息一定是移動節點Mj的鄰居節點集合NMi的可達信息，如(Mi，Mk)。若加上移動節點Mi后，路徑(Mi，Mj，Mk，Mi)是條環路，那么移動節點Mk一定是移動節點Mi的鄰居節點。由于Mk是移動節點Mi的直接鄰居節點，因此，這樣的路徑對其沒有任何價值，移動節點Mi不予采用。b）全局路由搜索。隨著系統的運行，移動agent MAj為移動節點Mi帶來了更多的路由信息。由于每個簇頭ci0對該簇Ci的移動agent MAj的行動進行管理，如果某個移動agent MAn長時間在一條路徑上不停地循環，則調整其移動agent MAn的運行。移動agent MAj搜索的路由信息是不含環路的，因此，移動節點之間由移動agent傳播的路由信息也是不含環路的路由。c)有環路由的調整。由于移動agent MAj錯誤的路由搜索行為等特殊錯誤發生，會帶來小部分的有環路由，而該有環路由不會被移動節點Mi使用。假設移動agent MAj經過移動節點Mi。其中移動節點Mi采納移動agent MAj中的一條路由信息(Mi，Mj，…)。Mj是移動節點Mi的鄰居節點。若(Mi，Mj，…)有環，那么移動節點Mi在該路由中一定出現了兩次以上。即該有環路由可以表示為(Mi，Mj，…，Mi，Mk，…)。而由于以鄰居節點Mk為出口的路由信息可以由局部搜索等方式獲得，以及為了防止路由環路，本文規定在路由項中存在的再次經過移動節點Mi的鄰居節點的路由部分如(Mi，Mk，…)，移動節點Mi不予采納。因此，該路由(Mi，Mj，…)存在環路的部分，被移動節點Mi丟棄。

定理2 該算法的路由選擇策略是一種具有優先級別順序的路由選擇。

證明 對于如果有多條可以到達目的節點的路由來說，移動agent有多個出口節點可以選擇。

路由選擇優先順序判斷原則可以詳細敘述為：首先根據蟻群路由選擇模型，計算出基于概率公式求出的轉移概率的高低排序(見3.2.1節中描述)。其次，根據下面的順序對已經排好序的路由表項所關聯的鄰居節點進行過濾。a）出口網絡資源狀態表(ONRT)查看剩余可用帶寬(B(Mi，Mk))和最后收到該鄰居節點傳輸數據包的時間(LT(Mi，Mk))參數，判斷節點的某個鄰居節點出口是否存在瓶頸，對于有擁塞或者可用帶寬缺乏的鄰居節點不予選擇；b)根據移動節點的路由表(MNRT)查看總跳數(HMiMkMj)、最后修改時間(LTMiMkMj)、經歷的路程總時間(TMiMkMj)等參數，并按照不同應用的需要決定過濾的優先順序；c)根據鄰居節點使用頻度表(NNUFT)的鄰居節點被使用的頻度(F(Mi，Mk))參數決定選用的鄰居節點作為下一跳的節點，對于可以有多個路由選擇的，選擇鄰居節點使用頻度少的節點。

定理3 對于連通的網絡任意移動節點Mi，能夠通過該算法找到到達目的節點的可行路由。 

證明 假設路由的源節點Mi處于簇Ci，目的節點Mj處于簇Cj，在簇Ci與簇Cj之間間隔Cl和Ck等x個簇，移動節點Mi需要的完成移動應用的可行路由(Mi，Mk，…，Ms，…，Mj)也確實存在。a)由于移動節點Mi可以向所有鄰居發送路由搜索包REQUEST，移動節點Mi在算法運行初期就能夠通過鄰居節點的應答消息REPLY，獲得兩跳以內的所有移動節點Mk路由信息LUk。b)假設移動節點Mi的局部路由查詢包REQUEST不能從它的鄰居節點集合NMi獲得需要的路由(Mi，Mk，…，Ms，…，Mj)。由于簇Ci中某個移動agent MAi以及簇Cj中某個移動agent MAj的巡游，通過簇頭ci0以及簇頭cj0的管理，保證了移動agent不會只是在環路上來回移動。同時，根據蟻群路由選擇模型，對移動agent MAj和移動agent MAi路由選擇的控制，選擇轉移概率值最小的移動節點Mg和Mv巡游，保證了移動agent MAj和移動Agent MAi能夠在每個節點上較均勻地巡游，因此，移動agent MAi和移動agent MAj會在某個時刻分別移動到別的簇Cl和Ck內。除此外，通過移動節點與移動agent，以及移動agent之間的交互，路由局部查詢(check_N_part())，處于簇Cj的目的節點Mj路由信息會交互到簇Cl和Ck等內，并且交互到簇Ci。若所有簇Cj相鄰簇的路由信息均無法交互到簇Cj，證明簇Cj是一個信息孤島，與移動P2P網絡是一個連通的網絡矛盾。因此，在一定時間內，路由信息能夠被傳播到移動節點Mi，移動節點Mi能找到需要的合適路由。

42 復雜性分析

定理4 路由選擇算法的運算復雜度為O(|Ti|+|Ri|)。其中：Ti表示移動節點Mi中路由性能指標包含的表數目，Ri表示路由表的路由條數。

證明 路由選擇的運算復雜度主要包括讀所有關聯路由性能指標的讀表操作和對所有路由表中的路由表項計算轉移概率值的操作。對于所有的數據表，移動節點可以使用并行操作一次全部讀出，因此，讀表操作的復雜度O(|Ti|)。在表被讀出后，需要通過表中每條路由數據的信用度，計算轉移概率。假設路由表中的所有路由信息均滿足該移動節點目前的移動應用需求，每次計算一條路由的轉移概率值運行一次操作。則計算復雜度是O(|Ri|)。因此，路由選擇算法的運算復雜度為O(|Ti|+|Ri|)。由于Ti和Ri的數量有限，同時該運算復雜度僅隨Ti和Ri數目呈線性增長，該算法具有可擴展性，可應用于一定規模的移動P2P網絡。

定理5 路由發現的消息復雜度為O(n+m)，網絡穩定后網絡中的移動節點平均數量是n個，移動agent的平均數量是m個(m＜n)。

證明 移動節點Mi運行路由發現策略，在某個時刻t最多同時會收到其余n-1個移動節點的路由發現查詢包。由于移動節點的局部路由搜索包的TTL時間很短，路由查詢的跳數不會超過一跳。如果所有n-1個移動節點同時向移動節點Mi發路由查詢，該移動節點Mi最多會收到n-1個路由查詢消息。同時，如果m個移動agent在時刻t同時經過該移動節點Mi，進行全局路由搜索，每個移動agent看做是一條路由查詢的消息。所以路由發現的消息復雜度為O(n+m)。

定理6 本文提出的路由算法(表示為MA)在時間復雜度和消息復雜度上具有一定的性能優勢。

證明 該算法在路由發現過程中，最差情況下的時間復雜度為某個移動agent從目的節點巡游到需要尋找該目的節點的源節點處，也即最大為穿越網絡，時間復雜度是O(D)(D為網絡直徑)。而ALR[7]基于消息驅動的路由算法，是通過消息摘要和鄰居節點轉發查詢包，因此，最壞的情況是，源節點發送一個路由查詢分組，目的節點返回一個確認分組，來回穿越網絡兩次，時間復雜度是O(2D)。消息復雜度最壞是在各個節點同時向鄰居節點轉發請求包，消息復雜度是O(2n)。同時，AntHocNet[17]需要前向螞蟻和后向螞蟻配合進行路由發現，因此，時間復雜度是O(2D)。在最壞狀況下，前向螞蟻負責尋找到目的節點的多條路由，后向螞蟻返回源節點建立路由。每條路由的發現由z個前向螞蟻和n個后向螞蟻(每個移動節點均回復路由消息)－兩種移動agent完成，消息復雜度是O(n+z)，并且為了獲得高路由命中率，由于該策略的路由發現完全由移動agent實現，z＞m。 

5 仿真

51 仿真模型

本文討論100個移動節點、20個移動agent規模的移動P2P網絡，仿真工具為NS2[18]。具體仿真模型為在1 500 m×300 m的矩形移動P2P網絡區域內，分布100個移動節點和20個移動agent，這個1 500 m×300 m的區域可被分成相同尺寸更小的區域，即分簇。每個簇中的簇頭以低速移動，其余簇成員的移動速度為0~10 m/s之間變化。移動節點的移動模型采用了Random Waypoint運動模型。移動節點的通信范圍為250 m，信道速率為2 Mbps。同時，業務流為CBR，本文使用20條CBR流，每個流每秒發送4個數據分組。每個數據分組為512 bit。MAC層協議是802.11。通過這些參數建立的仿真模型，將目前移動P2P領域中路由研究成果被引用次數最多的文獻[7]的路由策略與本文提出的基于移動agent的路由策略進行分析比較。

52 仿真結果

為了有效地評價本文提出的路由策略，本文同文獻[7]中關鍵的性能參數進行比較，如圖1~4所示。盡管文獻[7]中消息驅動的路由算法可以極大程度地減少資源查詢的平均傳輸消息數目，但是由于網絡的動態性，分發出去的消息摘要很容易因為節點的移動或退出等就失效了。而本文提出的路由策略防止了由于資源位置等發生變化，而需要再次進行查詢所帶來的更多消息，即減少了平均傳輸消息數，如圖1所示。文獻[7]展示了在發出的資源查找消息的平均響應效率方面，ALR的性能優勢。雖然基于ALR的消息驅動路由算法能夠幫助節點較快進行資源定位，但是由于網絡的多變性，命中率卻不高，也會影響消息的平均響應效率。本文提出的路由策略，不但能夠保證節點可以更快的路由，并且使用路由性能參數對路由選擇進行控制，防止了網絡擁塞等影響消息的響應率。通過及時得到網絡的狀況，以及使用蟻群尋路的方法，對資源查找消息進行調整，增加了找到需求資源的可能，提高了消息的響應率，如圖2所示。

本文的MA算法采用了有限制的洪泛局部路由搜索和基于簇頭控制的移動agent巡游的全局路由搜索方法。不僅縮短了尋路的時間，增加了找到可行路由的可能性，而且同文獻中的基于內容驅動的路由相比，更加適應網絡的變化、節點的移動等。因此，MA算法更加穩定以及能得到更高的命中與失效比，如圖3所示。除此之外，由于MA路由算法通過路由性能指標參數以及路由保持策略的方式，保證了即使在較多移動節點均處于不連接的情況下，仍然具有較好的命中與失效比，表明該路由策略對于節點的失效等網絡變化具有很強的適應能力。最后，由于網絡的資源非常珍貴，文獻[7]采用分發消息摘要的方式會帶來很多網絡的問題。由此可見，本文的MA算法具有較明顯的性能優勢。

6 結束語

本文敘述的路由策略在路由發現方面，搜索到準確可靠、及時豐富的路由信息。在路由選擇方面，使用改進的蟻群尋路模型，以及綜合考慮傳輸延遲、擁塞大小、可用帶寬等因素進行路由選擇。通過算法有效性和仿真實驗證明，該路由策略在平均傳輸消息數和平均響應效率等均具有性能優勢。

參考文獻：

［1］

KALOGERAKI V.Mobile peertopeer computing: challenges， metrics and applications[C]//Proc of the 6th International Conference on Mobile Data Management.New York:ACM，2005:331332.

［2］CHLAMTAC I，FARAG’O A.A new approach to the design and analysis of peertopeer mobile networks[J].Wireless Networks，1999，5(3):149156.

［3］HSIAO H C，KING C T.Bristle:a mobile structured peertopeer architecture[C]//Proc of International Parallel and Distributed Processing Symposium.Washington DC:IEEE Computer Society Press，2003:3341.

［4］SCHOLLMEIERR，GRUBER I，NIETHAMMER F.Protocol for peertopeer networking in mobile environments[C]//Proc of the 12th International Conference on Computer Communications and Networks.Washington DC:IEEE Computer Society Press，2003:121127.

［5］MAMEI M.Creating overlay data structures with the TOTA middleware to support contentbased routing in mobile P2P networks[C]//Proc ofInternational Workshop on Hot Topics in PeertoPeer Systems.New York:Springer，2004:7479.

［6］PENG G，LI Shanping，JIN Hairong，et al.MCAN:a lookup protocol for mobile peertopeer environment[C]//Proc of the 7th International Symposium on Parallel Architectures， Algorithms and Networks.Washington DC:IEEE Computer Society Press，2004:544549.

［7］REPANTIS T，KALOGERAKI V.Data dissemination in mobile peertopeer networks[C]//Proc of the 6th International Conference on Mobile Data Management.New York:ACM Press，2005:211219.

［8］YONEKI E，BACON J.Dynamic group communication in mobile peertopeer environments[C]//Proc of the 20th Annual ACM Symposium on Applied Computing.New York:ACM Press，2005:986992.

［9］鄭少仁，王海濤，趙志峰，等.Ad hoc網絡技術[M].北京:人民郵電出版社，2005:2948.

［10］OBERENDER J O，ANDERSENF U，De MEER H，et al.Enabling mobile peertopeer networking[C]//Proc of the 1st International Workshop of the EURONGI Network of ExcellenceWireless Systems and Mobility in Next Generation Internet.New York:Springer，2005:219234.

［11］DORIGO M，MANIEZZO V，COLORNI A.Ant system: optimization by a colony of cooperating agents[J].IEEE Trans on Systems， Man， and Cybernetics， Part B，1996，26(1):2961.

［12］MARWAHA S，THAM C K，SRINIVASAN D.Mobile agents based routing protocol for mobile Ad hoc networks[C]//Proc of IEEE Global Telecommunications Conference.Washington DC:IEEE Computer Society Press， 2002:163167.

［13］SHEKHAR H M P，RAMANATHA K S.Mobile agents based congestion aware routing in mobile Ad hoc networks[C]//Proc of the 6th IEEE International Conference on 3G and Beyond.Washington DC:IEEE Computer Society Press， 2005:17.

［14］ZHAO Chenchen，YANG Zhen.A new EAAODV routing protocol based on mobile agent[C]//Proc of International Conference on Systems and Networks Communication.Washington DC:IEEE Computer Society Press，2006:410.

［15］HURAKADLI J M，MANVI S S，MALLAPUR J D.Agent based connectivity detection and routing in mobile Ad hoc networks[C]//Proc of the 3rd International IEEE Conference on Intelligent Systems.Washington DC:IEEE Computer Society Press，2006:390394.

［16］AISSANI M，FENOUCHE M，SADOUR H.AntDSR:cache maintenance based routing protocol for mobile Ad hoc networks[C]//Proc of the 3rd Advanced International Conference on Telecommunications.Washington DC:IEEE Computer Society Press， 2007:3541.

［17］DUCATELLE F，DI CARO G，GAMBARDELLA L M.Ant agents for hybrid multiple routing in mobile Ad hoc networks[C]//Proc of the 2nd Annual Conference on Wireless Ondemand Network Systems and Services.Washington DC:IEEE Computer Society Press，2005:4453.

［18］The VINT Project. The UCB/LBNL/VINT network simulator:ns version 2[EB/OL].(200511)[20060211]. http://mash.cs.berkeley.edu/ns.