WSN的移動Agent隨機模式與分析

楊 挺，楊 青，唐 勇

(1. 電子科技大學計算機科學與工程學院 成都 611731；2. 蒙大拿州立大學計算機科學系 美國 博茲曼 59717)

WSN的移動Agent隨機模式與分析

楊 挺1，楊 青2，唐 勇1

(1. 電子科技大學計算機科學與工程學院 成都 611731；2. 蒙大拿州立大學計算機科學系 美國 博茲曼 59717)

提出了一種隨機的移動agent模式。該模式通過移動agent提供的遷移能力，支持基于群算法的事件監測，優化網絡覆蓋方案。通過移動agent隨機生成和隨機遷移，在確保對事件的檢測和覆蓋率的前提下，能夠減少監測領域中的活動節點。通過移動agent提供的群智能提高無線傳感器網絡在不同環境的適應能力，適用于當網絡由于能量損耗導致的分割或孤立的環境。仿真結果顯示，基于該模式的算法在覆蓋效率和通信距離要求上，表現出了良好的性能。

覆蓋; 移動代理; 群智能; 無線傳感器網絡

無線傳感器網絡涉及如覆蓋、檢測時間、能量消耗、網絡生存時間、魯棒性、安全、隱私、數據共享、延遲等問題通常需要較為復雜的算法和技術。為了實現其特有目的，WSN需要成為可自動配置、可調、遠程控制的網絡。移動agent(mobile agent，MA)技術可為WSN應用領域中的若干目標提供可行的解決方案。

MA是一種特殊的軟件，能夠自主運行，并在部署后能夠從一個節點移動到另一個節點進行自動的數據處理，是WSN完成復雜應用、實現節點自治的有效途徑。文獻[1]使用MA在WSN中對移動目標進行自動跟蹤。與傳統的agent不同，MA在無線傳感器網絡中通過其移動性能夠承擔很多重復工作，并由于MA是目標指向的，能夠為用戶提供管理抽象能力，當其部署在網絡中后能夠獨立完成工作。MA僅在需要時才通知用戶目標的完成狀態。基于WSN的agent需要具有遷移能力，能夠在確保其數據完整的前提下完成狀態的轉移。移動agent具有比固定的agent更強的自治性。

基于移動agent技術的WSN架構能夠為群智能算法[2]提供支撐框架。該研究有以下特點：1) 移動agent在局部隨機產生降低了sink節點的數據傳輸量。2) 多移動agent協同能夠擴大區域覆蓋率。3) 隨機生成和隨機遷移的活動節點需要較少的活動完成對事件監控。

1 相關工作

由于WSN節點幾乎都在無人管理的環境部署，因此WSN節點需要極強的自適應能力。文獻[3]提出動態宏程序(dynamic macro-programming)的WSN的概念。該研究定義了元代理(meta-agent)的概念，即固定代理給遠端的移動agent發出查詢消息(uQueries)以完成相應的任務。由于該技術提出基于移動agent的節點能夠被賦予多種不同的能力，因此通過uQueries能夠增加節點的動態工作能力。

為了提高數據融合精度，減少傳輸數據的能量消耗，研究WSN的數據和壓縮融合技術是必要的，相關研究主要集中在成簇、成鏈、樹和移動agent等方面。事件檢測是基于移動agent的WSN研究重點，文獻[4]給出了使用MA產生和維護從設計用戶界面到發現事件節點的最優路徑的技術，從而達到WSN快速響應的目的。MA由當地的代理產生并在網絡中遷徙，對最優路徑進行維護和升級。但根據仿真結果，MA在事件發生處的密集較高，可能導致節點的能量消耗過快。

除了研究基于移動agent的WSN結構外，還有一些專用移動agent結構，如文獻[5]通過建立容錯模型和分布式數據庫，構建能夠檢測錯誤并修復的移動agent結構，以減少持續維護網絡管理流量的開銷。發放子代理的過程可以程序化，并且能夠分批進行。

2 RMAWSN系統模型

移動agent通過遷移代碼可以方便地進行任務重置，在本地進行數據處理，完成多點協同合作等功能，較通過固定節點完成所有獨立任務的WSN而言更為靈活。圖1展示了3種基于移動agent的無線傳感器數據傳輸模式。圖1c為本文討論的采用隨機產生和遷移的無線傳感器獲取數據的模式，稱為基于隨機移動agent的WSN(random mobile agent-based WSN，RMAWSN)。

RMAWSN中的MA有兩種狀態，即激活與休眠狀態。每個代理激活狀態意味著代理能夠執行代理各種行為，如環境檢測。處于休眠狀態的代理能夠自動激活，或者根據網絡狀態激活。休眠狀態的代理不意味著節點也處于休眠狀態，節點依然能夠接收無線信號，執行其他日常工作。

RMAWSN中，每個激活狀態的代理運行一個定時器，限制MA的激活時間，因此MA擁有短周期特點。定時器的計數根據代理移動步數減少。每個代理處于休眠狀態并等待被激活。采用短周期MA的原因有以下幾點：1)能夠避免激活代理的分布不均；2) 能夠避免MA在一個區域重復遷移；3) 能夠控制網絡中激活狀態代理的數目，提高能量的使用率。

圖1a為移動agent的分布式傳感器網絡(mobile agent-based distributed sensor network, MADSN)[6]的示意圖，該移動agent采用CS模式的WSN的數據傳輸過程。在sink節點需要多次往返傳輸數據。監控區域發生異常事件后，附近的傳感器需要通知sink節點，在sink節點決策后，派出MA進行監測。該過程需要確定源節點，即能夠探測到事件的傳感器節點，MA能夠根據源節點的分布自行完成行程規劃。

如圖1b所示，基于移動agent的WSN(mobile agent-based WSN，MAWSN)[7]提出了采用母agent (mother agent)的結構以減少數據傳輸量。sink節點向目標區域發送母agent，母代理到達目的節點后，發送若干子代理到事件區域周圍。每個子代理在完成事件檢測后，需要單獨從sink節點出發并返回sink節點。

如圖1c所示，RMAWSN模式的節點在本地即可獲取數據。MA并不由sink節點發出，而在網絡中自動生成，并能夠隨機地遷移。代理在發現事件后可以根據行程規劃進行遷移，獲取數據后，再單程返回sink節點。這種模式在WSN網絡規模較大時，能得到更佳的能耗效率。

定義節點發送、接收、感知過程的單位能耗分別為et、er、es；未攜帶數據的代理lnew假設從每個節點能夠獲取的數據為lnode。假設圖1中訪問的所有節點傳輸距離相同，代理頭部信息相同，圖1中，代理訪問的源節點數為n，從sink節點到源節點經過的節點數為m。

代理遷移行為通過中繼節點對MA代碼進行接收和發送實現，設未攜帶數據的代理在中繼節點的能耗為：

MA獲得數據后，中繼節點的能耗也相應地增加為：

在圖1a中，m個MA從sink節點出發，遷移到事件附近的m個源節點，并返回sink節點，總能耗為：

在圖1b中，MA從sink節點出發，遷移至源節點，并將數據返回到sink節點的過程，總能耗為：

在圖1c中，假設節點隨機游動k次后發現事件，在遍歷n個源節點后返回sink節點的能耗為：

由式(1)和式(2)，將圖1a的MADSN構架與圖1b的MAWSN構架的能耗進行對比，得：

通過式(4)能夠看出，若源節點與sink節點越遠，源節點數量越多，MAWSN模式較MADSN模式的效率要高很多。

圖1c的RMAWSN模式與圖1b的MAWSN模式相比，得：

3 RMAWSN的覆蓋區域

隨機產生和隨機移動的MA能夠獲取更好的目標監測能力和更少的活動傳感器。本節采用區域覆蓋方法評估RMAWSN的隨機模型，基于文獻[8-9]中尋找最佳突破路徑(maximal breach path)和最佳支撐路徑(maximal support path)使用的部分定義。

定義節點的感知范圍半徑為r；被測物體從S點到D點的路徑軌跡為曲線p。設曲線p1和p2在p的兩側，并分別離曲線p的距離為r。p1和p2構成的封閉區域為

設S、D兩點之間曲線p的長度為x，即：

式中，2rx為p1和p2構成的條狀區域面積；2πr為條狀區域兩端分別與點S和點D為中心的兩個半圓面積(其半徑為r)。將式(7)代入式(6)，得檢測到的概率：

通過式(7)，確定發現物體的概率和穿過該區域的最短路徑長度，可以推算出穿過區域時，節點能夠發現試圖穿過該區域的物體所需部署的密度：

若確定檢測到目標的概率Pd(p)和目標穿越區域的路徑長度x，即區域中活動節點的密度就能根據式(9)計算出。需要提出，當x→∞時，表示被測物體在區域中不斷徘徊，被測的可能性為百分之百。即當x→∞時，且物體不知活動節點位置

定義被測物體移動速度為v，節點部署密度為λs，將傳感器區域分為n個小區域，即||Zi||(i=1,2,,n)，節點穿過區域的時間t = n/v。將t分為m份，定義每一份為一個步長，一個步長的距離為n/m。若物體在||Z||移動一個步長的距離，被發現的概率定義為ps。

根據式(7)，λs和Ps的關系為：

物體移動一個步長的時間后，所有探測節點根據部署密度λs重新部署。物體穿過m個步長被發現的概率為：

若m足夠大，且探測物體的速度已知時，Ps可以設置很小，即根據式(9)，傳感器節點部署密度λs可以設置得很小。

由于激活的移動agent密度較隨機固定激活節點數量少，顯然該算法在網絡中所需的總能量要小。同時由于移動agent的隨機移動和自動隨機產生機制，能量消耗的分布也能滿足均勻分布的目標，避免監測區域中過早出現監測空洞。因此通過移動agent形式的MA在尋找事件的過程中，能量消耗和覆蓋效率均能獲得很好的平衡。

根據式(11)，若網絡中激活狀態的代理密度接近λs，傳感器網絡能夠有效地檢測和跟蹤到目標。為了獲得所需密度λs，每個代理保持一個定時器t1，t1記錄未被MA訪問的時間。假設網絡中所有節點數為代理將根據概率激活，并設置定時器t1=0。若t1

4 RMAWSN仿真結果

本文采用基于RMAWSN模式的人工魚群算法(short life artificial fish swarm algorithm, SLAFSA)[11]進行仿真驗證。表1為實驗的詳細參數。網絡存在10個MA，在50×50的網絡中一共部署136個節點，節點的通信距離為10，感知距離為4。RMAWSN的MA將運行15次。實驗中隨機放置了10個事件，仿真結果顯示所有事件在5步后均被發現。設定發現事件的MA消失，長時間未被訪問的節點根據概率afP自動激活MA。

MA在網絡中的移動情況如圖2所示。根據表2，在3步后，7個事件被發現，同時接近半數的節點被訪問到；在7步后，即圖2c，接近80%的節點被訪問，覆蓋率接近80%，并發現了所有的事件。在圖2d中，MA覆蓋了近90%的節點。根據表2，在第7步時覆蓋率接近80%，并發現了所有的事件。

在圖2b的右下角區域幾乎沒有節點訪問，該區域被當前MA訪問的幾率很小。圖中在點(45,11)處一個新的MA被激活，在5步后，該MA將對該區域探索一遍。這種自我激活的機制能夠讓算法避開空洞區域。

4.1 RMAWSN的覆蓋性能

本文將文獻[12]中描述的兩種基于AFSA和OAFSA算法與基于RMAWSN的SLAFSA算法進行比較，在表3中顯示了3種算法的網絡覆蓋率。每種算法使用相同的網絡參數，如50×50的區間，50個節點，通信距離為12，感知距離為4。從表3中可以看到，SLAFSA算法在5步時獲得近80%的覆蓋率，而在10步時獲得了近90%的覆蓋率。

4.2 RMAWSN的參數分析

從仿真結果看，在節點密度固定時，RMAWSN節點覆蓋率與兩個因素相關：MA的數量和MA移動的步數。顯然，步數越多獲得的覆蓋率越高。其次，仿真發現RMAWSN模式下，覆蓋率與通信距離無關。

1) MA的數量與覆蓋率

MA的數量是網絡覆蓋中重要的參數之一。在表4中顯示了不同的起始MA數量與MA移動了15步之后的節點覆蓋率的關系。根據RMAWSN的隨機模型，SLAFSA算法的節點能夠在時間1t后隨機激活MA，因此即使起始MA的數量為2個，在20步后，網絡也能獲得接近80%的節點覆蓋率。

2) 通信距離對覆蓋率的影響

節點之間的無線通信是重要的能量消耗因素。越長的通信距離意味著相同密度下的網絡將消耗更多的通信能量。有意思的是，算法分析中發現延長通信距離并不能增加網絡覆蓋的效果。

為研究通信距離與覆蓋率的關系，圖3和圖4統計了在50×50的范圍內部署450個節點，并且運行10步后的結果。圖3研究節點在不同通信距離下的累計激活節點，圖4統計在不同通信距離下的覆蓋率，兩圖結果均顯示了激活節點的密度和覆蓋范圍與通信距離無關。或者說，通信距離對RMAWSN模式的性能影響很小。實驗說明采用RMAWSN模式的WSN，節點可以采用較短的通信距離節約能量，且不影響網絡的覆蓋率。

5 結 束 語

本文提出了一種新的基于移動agent的WSN模式RMAWSN，在減少能量消耗和提高事件的覆蓋檢測能力上有較好的表現。通過實驗，發生在監測區域的事件能夠有效地在較短時間內被隨機游動的MA發現。由于MA的隨機行為和短周期特點，網絡需要的活動節點更少，并能有效地發現事件。實驗表明，在該模式下節點通信距離可以與覆蓋率無關。

[1] SUENAGA S, HONIDEN S. Constructing locally centralized applications by mobile agents in wireless sensor networks[C]//Proc of the ATSN. Estoril, Portugal: [s.n.], 2006.

[2] LEE J W, CHOI B S, LEE J J. Energy-efficient coverage of wireless sensor networks using ant colony optimization with three types of pheromones[J]. IEEE Transactions on Industrial Informatics, 2011, 7(3): 419-427.

[3] RAZAVI R, MECHITOV K, AGHA G, et al. Dynamic macroprogramming of wireless sensor networks with mobile agents[J]. Policy, 2007(1): 1-6.

[4] KAKKASAGERI M S, MANVI S S, SORAGAVI G D. Mobile agent based event discovery in wireless sensornetworks[C]//Proc of the 5th WSEAS Intl Conf on Applied Computer Science. Hangzhou: [s.n.], 2006.

[5] SALIM S, JAVED M, AKBAR A H. A mobile agent-based architecture for fault tolerance in wireless sensor networks [C]//Communication Networks and Services Research Conference (CNSR). Montreal, QC, Canada: IEEE, 2010.

[6] QI Hai-rong, XU Ying-yue, WANG Xiao-ling. Mobileagent-based collaborative signal and information processing in sensor networks[J]. Proceedings of the IEEE, 2003, 91(8): 1172-1183.

[7] CHEN M, KWON T, YUAN Y, et al. Mobile agent based wireless sensor networks[J]. Journal of Computers, 2006, 1(1): 14-21.

[8] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawwii: USA, IEEE, 2000.

[9] HUANG C F, TSENG Y C, LO L C. The coverage problem in three-dimensional wireless sensor networks[J]. Journal of Interconnection Networks, 2007, 8(3): 209-227.

[10] LIU B, TOWSLEY D. A study of the coverage of large-scale sensor networks[C]//IEEE International Conference on Mobile Ad-hoc and Sensor Systems. Fort Lauderdale, FL, USA: IEEE, 2004.

[11] YANG T, YONG T. Short life artificial fish swarm algorithm for wireless sensor network[C]//International Conference on Computational Problem-solving (ICCP). Beijing: IEEE, 2013.

[12] WANG Yi-yue, LIAO Hong-mei, HU Heng-yang. Wireless sensor network deployment using an optimized artificial fish swarm algorithm[C]//International Conference on Computer Science and Electronics Engineering (ICCSEE). Hangzhou: IEEE, 2012.

編 輯 張 俊

Random Mobile Agent Based WSN Model and Its Analysis

YANG Ting1, YANG Qing2, and TANG Yong1
(1. School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. Department of Computer Science, Montana State University Bozeman, USA 59717)

In order to optimize wireless sensor network coverage scheme, a random mobile agent-based wireless sensor network model (RMAWSN) is presented in this paper. The model uses swarm optimization algorithm to relocate active mobile agent for event detection. In this model, active mobile agent provides several advantages by the characteristics of random generation and movement: reducing active nodes in monitored area on the premise of coverage rate and the adaptation of divided or isolated network. Experiment results show that this model effectively improves network coverage and reduces consideration of communication distance.

coverage; mobile agent; swarm intelligence; wireless sensor network

TP393.02

A

10.3969/j.issn.1001-0548.2015.03.021

2014 ? 03 ? 03；

2015 ? 01 ? 13

四川省省級戰略性新興產業發展促進資金(SC2011510703011)

楊挺(1975 ? )，男，博士，講師，主要從事計算機網絡方面的研究.