基于APIT的三維移動代理路由算法研究

摘 要:針對現有的移動代理路由算法都是基于二維環境的不足，提出了一種能應用于三維環境中的移動代理路由算法。首先，使用APIT定位法來獲取三維空間中的傳感器坐標;在獲取傳感器節點坐標后，引入蟻群算法對移動代理訪問傳感器節點的路徑進行優化，由此，得到了一種全新的基于APIT的三維移動代理路由算法。仿真實驗表明，新移動代理路由算法能較好地適應無線傳感器網絡的實際應用環境，且路徑優化效果明顯。

關鍵詞:無線傳感器網絡; 移動代理; APIT節點定位法; 蟻群算法

中圖法分類號:TP393;TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2246-03

doi:10.3969/j.issn.1001-3695.2010.06.071

Mobile agent routing algorithm for 3D space based on APIT

XU Yunjiana，GUO Aiyinb

(a. College of Computer Science Technology， b. College of Electrical Information Engineering， Hunan International Economics University， Changsha 410205，China)

Abstract: Aiming at the shortage of the existing mobile agent routing algorithm on 2D， this paper presented the mobile agent routing algorithm applied on 3D environment. At first， used the APIT (approximate pointintetrahedron) localization scheme to locate the coordinates of sensor. After obtaining the 3D coordinates of the sensor nodes， imported ant colony algorithm to optimize the path of the mobile agent visiting sensor nodes. It proposed a new mobile agent routing algorithm for 3D space based on APIT. The simulation results show that the proposed new algorithm can adapt to the actual wireless sensor network applications better， and have an obvious affection on the path optimization.

Key words: wireless sensor networks(WSN); mobile agent; APIT node’s localization scheme; ant colony algorithm

0 引言

無線傳感器網絡(WSN)能夠完成許多傳統計算機網絡難以完成的任務，如環境監測、遙感、危險品檢測等，這些優勢使得對無線傳感器網絡的研究成為當前的一個熱門研究領域。無線傳感器網絡通常部署在山區、水域、地下礦洞、空中等人力不易到達的環境里。在這樣的環境中，如何有效地組織數據傳輸以減少網絡能耗和網絡延時，就成為了無線傳感器網絡研究的重要課題，使用移動代理模式的無線傳感器網絡數據融合算法是一種高效節能的數據融合算法[1，2]。移動代理是一段能自動執行的特殊代碼，其中帶有處理節點分派的任務。移動代理在處理節點形成后，被分派到傳感器網絡中，它能自動地從一個傳感節點遷移到另一個傳感節點，并在傳感節點上進行數據處理。移動代理訪問節點的順序、訪問的節點總數成為了移動代理模型成功與否的關鍵因素，對網絡的性能有重大影響。目前已經有用本地最近優先(LCF)、全局最近優先(GCF)、基于遺傳算法(GA)[3]等啟發式算法來計算移動代理在傳感器網絡中的路由問題。然而，這些算法都是建立在二維平面上的路由算法，它們并不適用于真實的三維環境，并且這些現有算法僅在小規模的無線傳感器網絡中取得了成功，在大規模傳感器網絡中，當節點分布情況變得復雜時，算法性能惡化。

注意到這些不足，將移動代理的二維平面路由算法拓展到三維空間成為了本文重點解決的一個問題。除此之外，為移動代理在三維環境里尋找一條由剩余能量多、數據處理能力強、傳感距離短的傳感節點連接而成的遷移路徑，可以歸結為一個優化問題。蟻群算法是一種新型的模擬進化算法，重點始于組合優化問題的求解，它具有較強的搜索能力、很好的適應性和魯棒性等。為此，本文提出了一種能在真實三維空間定位傳感器節點的基于蟻群算法的無線傳感器網絡移動代理路由算法。

本文中，將WSN 中需要定位的節點稱為未知節點(unknown node)，而已知位置，并協助未知節點定位的稱為錨節點(anchor node)。鄰居節點是指在一個節點通信半徑內，可以直接通信的節點。

1 三維空間移動代理路徑獲取的相關研究

1.1 APIT三維空間節點定位法

要在真實環境中進行信息收集與傳遞，首先要知道傳感器節點的位置信息。假設三維空間中的研究對象是靜止的無線傳感器網絡。網絡中部署了少數已知自身位置的錨節點，而且錨節點配備有高發射功率的無線收發器。為了確保三維立體的通信范圍，錨節點和傳感器節點都裝備有全方位天線。APIT[4]定位方法的基本思想是:若未知節點判斷自身位于某個由任意四個錨節點組成的四面體內部，則認為該四面體為一個可能位置區域(possible location area， PLA)。通過循環選取不同的四面體進行測試，篩選出所有是PLA的四面體，從而不斷縮小未知節點的周邊區域，實現位置估計。判斷未知節點是否在四面體內部，可以通過PIT( point in tetrahedron)測試法解決這個問題。

PIT測試法描述如下:要判定傳感器節點是否位于某個四面體之內，可以將該問題形式化為給定四個錨節點，A(ax， ay， az)， B (bx， by， bz)， C(cx， cy， cz)和D(dx， dy， dz)，判斷未知傳感器節點M 位于▲ABCD ( ▲表示四面體)內部或外部。要判定未知節點M處于四面體的內部還是外部可以通過以下兩個條件:

條件1 若某點M 位于▲ABCD 內部，則M 沿任何方向移動時，新位置必定接近或遠離A、B、C和D中的至少一個頂點，如圖1(a)所示。

條件2 若某點M 位于▲ABCD 外部，則必定存在一個方向， 當M沿此方向移動時， 新位置會同時接近或遠離所有四個頂點A、B、 C和D，如圖1(b)所示。

在現有硬件技術條件下，無法精確測出節點間的距離，也不能在未知節點的所有方向上測試移動后的位置與四個錨節點間的距離。在大規模部署傳感器節點的環境中，可以利用未知節點的相鄰節點代替未知節點在相鄰節點方向上的移動來實現條件1的判斷;利用未知節點四周空間中的眾多相鄰節點，則可以測試未知節點在多個方向移動時是否接近或遠離用來定位的四個錨節點(條件2)。

由此得到了一種PIT測試法的近似測試方法APIT測試法。其方法描述如下:若與某點M的所有鄰居節點沒有一個比M同時接近或遠離▲ABCD所有的四個頂點A、B、C和D，則點M認為自己位于▲ABCD的內部，如圖2(a) ;否則，點M認為自己位于▲ABCD的外部，如圖2(b)。該方法在不要求節點移動的前提下，能夠高度近似地實現PIT測試。

1.2 蟻群系統的基本模型

蟻群算法的重點始于組合優化問題的求解，本文選用典型的TSP為例闡述基本的蟻群算法模型[5]。TSP就是尋找一條閉合回路，該回路能夠訪問所有的城市一次，且走這條回路所用的費用最少。設m是蟻群中螞蟻的數量;dij(i，j=1，2，…，n)表示城市i和城市j之間的路徑距離;bi(t)(i=1，2，…，n)表示時刻t在城市i中的螞蟻個數，那么n座城市中螞蟻的總數為m=∑ni=tbi(t);τij(t)表示t時刻在城市i與城市j連線上信息素的濃度，在初始時刻，各條路徑上信息素的濃度相等，設τij(0)=C(C為常數);α表示螞蟻在運動過程中所積累的信息;β表示啟發因子在螞蟻選擇路徑中所起的作用程度;ηαij表示螞蟻在運動過程中i、j城市連線上所積累的信息素濃度;ηij表示由城市i轉移到城市j的期望程度;ηβij(t)表示在啟發式因子作用下螞蟻所選擇的路徑由城市i轉移到城市j的期望程度(簡稱能見度)，它由兩城市的距離決定。當螞蟻距某城市越近，螞蟻就越有可能向該城市移動。設Pkij(t)表示在t時刻第k (k=1，2，…，m) 只螞蟻由城市i轉移到城市j的概率，根據各條路徑上信息素的濃度決定轉移方向:

Pkij(t)=ταij ηβij(t)∑ταis(t)ηβis(t) j∈allowedk

0otherwise(1)

其中:allowedk ={ntabuk }表示螞蟻k下一步允許選擇的城市。即用tabuk表示第k(k=1，2，…，m)只螞蟻的禁忌表(tabulist)，這種禁忌表的數據結構，儲存有t時刻第k只螞蟻已訪問過的城市以及在各城市之間所走過的旅程，并禁止該螞蟻再次訪問這些城市。第k只螞蟻在完成從一個城市到另一個城市的路徑選擇后，都需要更新其剛剛經過路徑的信息素，更新的原則由式(2)給出:

τ(r，s)(1-ρ)#8226;τ(r，s)+ρ#8226;Δτ(r，s)(2)

其中:ρ是一個0~1的參數，當第k只螞蟻完成一次合規則的旅行后，禁忌表可被用來計算它的當前解，即計算螞蟻在本次旅行中所走過的總旅程。隨著時間的推移，在各條路徑上的信息素逐漸消逝，用參數1-ρ表示信息素的消逝程度，經過n個時刻，螞蟻完成一次循環，設τij(t+n)表示螞蟻經過t+n時刻后在城市i與城市j連線上殘留的信息素濃度，則

τij(t+n)=ρτij(t)+Δτij

Δτij=∑mk=1Δτkij(3)

其中:Δτij表示本次循環所有螞蟻在路徑i、j上所釋放的信息素濃度之和;Δτkij表示第k只螞蟻在本次循環中留在路徑上i、j上的信息素濃度;ρ為系數，并規定系數ρ必須小于1，以避免各條路徑上信息素的數量無限制地累積。Δτkij的計算采取ant cycle system模型:

Δτkij=Q/Lkif the kth ant uses edge (i， j)

0otherwise(4)

其中:L 為第k只螞蟻完成一次旅行時所走過的總路程，Q為螞蟻釋放的信息素總濃度。該模型利用了蟻群的整體信息，使用最為廣泛。

2 基于APIT的三維空間移動代理路由算法步驟

在目標三維區域中使用APIT定位移動代理活動范圍內的未知傳感器節點，APIT定位法的具體方法[6]是:錨節點向網絡內的傳感器節點廣播信標消息，該信標消息包含了錨節點的ID、位置信息等數據;如果未知節點能夠接收到某個錨節點發射的信標消息，則將該錨節點記錄為可見錨節點;未知節點與鄰居節點交換各自的可見錨節點信息，并根據接收信號強度判斷自己與鄰居節點距離錨節點的遠近，從而將周邊區域劃分為多個互相重疊的四面體，每個四面體由任意一組可見錨節點組成;未知節點任選一個四面體進行測試，判斷自己是否位于這個四面體內部。如果未知節點在某個四面體內部，則稱這個四面體為該未知節點的一個PLA;對不同的四面體循環測試直到窮盡組合，則計算所有PLA交集區域的重心，并以此重心坐標的平均值作為未知節點的估計位置[7]。APIT定位方法的基本代碼如下:

Receive location beacons { ( xi ， yi ， zi ) } from N anchors

Exchange N anchors RSS and Location information with neighboring sensor nodes

PLASet = /* the set of tetrahedrons in which I reside， also denoted as possible location area */

For ( each tetrahedron Ti∈N4 tetrahedrons) {

If (APIT (Ti) == TRUE)

PLASet = PLASet ∪ { Ti }

If (Tested Num (PLASet) == MAX) break;}

/* Center of gravity (COG) calculation * /

Estimated Position = (COG∩ PLASet);

得到三維環境中的未知節點位置數量和具體的發射坐標后，可以把移動代理要到達的各個傳感器節點看做TSP中的城市，由此引入蟻群算法，其實現步驟如下:

a)初始化

設初始迭代次數Nc=0;為每條移動代理的路徑(r，s)設置信息素強度初值:

τ(r，s)=τ0，Δτ(r，s)=0

將m 只螞蟻隨置于處理節點(移動代理的出發節點)上，螞蟻的禁忌表置空:tabuk=;

b)求解過程

for(i=1;i<=n;i++)

for(k=1;k<=m;k++)

{

將處理節點添加到tabuk中;

If(移動代理沒有完成指定任務且禁忌表未滿)

{ 按照式(1)計算Pkrs，移動代理選擇下一個將要訪問傳感器節點s;移動到節點s，并將s添加到tabuk 中;根據式(2)對路徑(r，s)進行局部更新;}

c)應用式(3)進行全局更新

for(k=1;k<=m;k++)

{

根據tabuk分別找出本次循環中花費時間最短和最長的路徑;

}

d)輸出最優解

If ( 不滿足終止條件 ){清空所有螞蟻的禁忌表;對每條路徑(r，s)，置Δτ(r，s)=0;Nc= Nc+1;返回步驟b

);}

Else返回最優解;

算法結束后，得到了一條經過優化了的移動代理遷移路徑。由此，得到了一種能夠適用于三維空間的全新移動代理路由算法。

3 仿真實驗與分析

在APIT定位方法中有三個關鍵參數:a)未知節點密度(node density， ND)，即每個傳感器節點的通信半徑區域內的平均節點數目;b)可見錨節點數目(anchor heard， AH)，每個傳感器節點能夠接收到信標的錨節點數目;c)錨節點與傳感器節點的通信半徑比(anchor to node range ratio， ANR)。通過對這三個參數的不同設置，分別得到以下實驗結果:

從圖3可以看出，定位精度隨著錨節點數量增多而逐漸提高，即錨節點數量越多，得到的PLA體積就越小，定位精度也就越高。此外，圖3清晰地表明通信半徑比(ANR)越小， APIT的定位性能表現得越好，因為ANR值越大，意味著錨節點分布得越稀疏，累計的誤差也就越大，從而降低了定位精度。當可見錨節點數量大于40時，定位精度均可以控制在0.4R(R表示節點通信半徑的大小)左右，這個定位精度是可以接受的。圖4表明，隨著傳感器節點數目的增多，定位精度的增加趨勢并不顯著，原因是APIT算法依賴于傳感器節點彼此間的交互通信，鄰居節點越多，定位效果也就越好。

為測試蟻群算法在移動代理路徑優化中的效果，仿真實驗的基本參數設置如下: m=10，τ0=(n#8226;Lnn)-1(Lnn是由最近的傳感節點啟發產生的一個路徑長度)， N=30，每個算法實驗執行20次，每次執行2 000遍。仿真結果如表1所示。

表1本文算法的仿真結果

αβρ遷移路徑長度進化代數

140.001311.278 6165

140.6324.168 5146

220.001271.323 2155

220.5304.238 9147

410.1287.778 5120

310.001268.486 5171

表1反映了用蟻群路由算法在不同參數下得到的移動代理遷移路徑長度以及需要進化的代數。從表中的數據可以看出，當α值取4，β值取1，ρ取0.1時算法的綜合效果最好;當α值取3，β值取1，ρ取0.001時算法性能惡化。

圖5和6分別給出了基于蟻群算法的移動代理路由算法最好解和最壞解的進化曲線，可以看出，只要選取合適的參數，算法的進化代數可以控制在200代以內。綜合前面的仿真結果可以看出，APIT定位法是在單個傳感器節點上進行的，因此是一種分布式的定位方法，避免了大量數據向中心節點傳輸而造成的能量損耗，是一種低成本且適用于三維環境中的有效節點定位算法。在此基礎上應用基于蟻群算法的移動代理路由算法克服了基本蟻群算法存在的收斂速度慢、搜索時間長的問題，而且具有更強的全局搜索能力。

4 結束語

本文分析了現有無線傳感器網絡移動代理路由算法存在不適用于三維空間的問題，并引入了能夠在三維空間定位傳感器節點的APIT定位法。APIT定位法充分利用了傳感器節點密集分布的特點，該特點適合于真實的網絡環境。此外，由于APIT定位法是在單個傳感器節點上進行的，是一種分布式的定位方法，避免了大量數據向中心節點傳輸而造成的能量損耗，從而延長了網絡壽命，更加符合無線傳感器

網絡對低功耗、低成本的需要。在利用APIT定位法獲取了空間節點坐標后，將蟻群算法應用于移動代理的路由優化中，通過實驗證明，只要選取適合的參數，就能夠克服蟻群算法存在的收斂速度慢、搜索時間長的問題，高效而迅速地獲得一條最優的移動代理遷移路徑，提高了數據融合算法的性能。本文提算法是基于靜態無線傳感器網絡的，對于水下、空中等動態三維環境下的數據融合算法的研究，將是筆者下一步工作的方向。

參考文獻:

[1]周四望，林亞平，聶雅琳，等.無線傳感器網絡中基于數據融合的移動代理曲線動態路由算法研究[J]. 計算機學報，2007，30(6):895-904.

[2]QI H， IYENGAR S S， CHAKRABARTY K. Multiresolution data integration using mobile agents in distributed sensor networks[J]. IEEE Trans on Systems， Man， and CyberneticsPart C: Applications and Reviews， 2001， 31(3):383-391.

[3]DORIGO M， GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the travelling salesman problem[J]. IEEE Trans on Evolutionary Computation， 1997，1(1):53-56.

[4]ZHOU Siqing， CHEN Ruibaio. APIT location algorithm its improvement in wireless sensor networks[J]. Computer Engineering， 2009， 35(7):87-89.

[5]DORIGO M， GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Trans on Evolutionary Computation， 1977， 1(1):53-66.

[6]HE Tian， HUANG Chengdu， BLUM B M， et al .Rangefree localization schemes for large scale sensor networks[C]//Proc of MobiCom. San Diego: ACM Press， 2003:81-95.

[7]LIU Yuheng， PU Juhua， HE Yang， et al. Threedimensional selflocalization scheme for wireless sensor networks[J]. Journal of Beijing University of Aeronautics and Astronautics， 2008， 34(6):647-651.