楊 挺，楊 青，唐 勇

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

WSN的移動Agent隨機(jī)模式與分析

楊 挺1，楊 青2，唐 勇1

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

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

覆蓋; 移動代理; 群智能; 無線傳感器網(wǎng)絡(luò)

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

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

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

1 相關(guān)工作

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

為了提高數(shù)據(jù)融合精度，減少傳輸數(shù)據(jù)的能量消耗，研究WSN的數(shù)據(jù)和壓縮融合技術(shù)是必要的，相關(guān)研究主要集中在成簇、成鏈、樹和移動agent等方面。事件檢測是基于移動agent的WSN研究重點，文獻(xiàn)[4]給出了使用MA產(chǎn)生和維護(hù)從設(shè)計用戶界面到發(fā)現(xiàn)事件節(jié)點的最優(yōu)路徑的技術(shù)，從而達(dá)到WSN快速響應(yīng)的目的。MA由當(dāng)?shù)氐拇懋a(chǎn)生并在網(wǎng)絡(luò)中遷徙，對最優(yōu)路徑進(jìn)行維護(hù)和升級。但根據(jù)仿真結(jié)果，MA在事件發(fā)生處的密集較高，可能導(dǎo)致節(jié)點的能量消耗過快。

除了研究基于移動agent的WSN結(jié)構(gòu)外，還有一些專用移動agent結(jié)構(gòu)，如文獻(xiàn)[5]通過建立容錯模型和分布式數(shù)據(jù)庫，構(gòu)建能夠檢測錯誤并修復(fù)的移動agent結(jié)構(gòu)，以減少持續(xù)維護(hù)網(wǎng)絡(luò)管理流量的開銷。發(fā)放子代理的過程可以程序化，并且能夠分批進(jìn)行。

2 RMAWSN系統(tǒng)模型

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

RMAWSN中的MA有兩種狀態(tài)，即激活與休眠狀態(tài)。每個代理激活狀態(tài)意味著代理能夠執(zhí)行代理各種行為，如環(huán)境檢測。處于休眠狀態(tài)的代理能夠自動激活，或者根據(jù)網(wǎng)絡(luò)狀態(tài)激活。休眠狀態(tài)的代理不意味著節(jié)點也處于休眠狀態(tài)，節(jié)點依然能夠接收無線信號，執(zhí)行其他日常工作。

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

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

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

如圖1c所示，RMAWSN模式的節(jié)點在本地即可獲取數(shù)據(jù)。MA并不由sink節(jié)點發(fā)出，而在網(wǎng)絡(luò)中自動生成，并能夠隨機(jī)地遷移。代理在發(fā)現(xiàn)事件后可以根據(jù)行程規(guī)劃進(jìn)行遷移，獲取數(shù)據(jù)后，再單程返回sink節(jié)點。這種模式在WSN網(wǎng)絡(luò)規(guī)模較大時，能得到更佳的能耗效率。

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

代理遷移行為通過中繼節(jié)點對MA代碼進(jìn)行接收和發(fā)送實現(xiàn)，設(shè)未攜帶數(shù)據(jù)的代理在中繼節(jié)點的能耗為：

MA獲得數(shù)據(jù)后，中繼節(jié)點的能耗也相應(yīng)地增加為：

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

在圖1b中，MA從sink節(jié)點出發(fā)，遷移至源節(jié)點，并將數(shù)據(jù)返回到sink節(jié)點的過程，總能耗為：

在圖1c中，假設(shè)節(jié)點隨機(jī)游動k次后發(fā)現(xiàn)事件，在遍歷n個源節(jié)點后返回sink節(jié)點的能耗為：

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

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

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

3 RMAWSN的覆蓋區(qū)域

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

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

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

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

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

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

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

根據(jù)式(7)，λs和Ps的關(guān)系為：

物體移動一個步長的時間后，所有探測節(jié)點根據(jù)部署密度λs重新部署。物體穿過m個步長被發(fā)現(xiàn)的概率為：

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

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

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

4 RMAWSN仿真結(jié)果

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

MA在網(wǎng)絡(luò)中的移動情況如圖2所示。根據(jù)表2，在3步后，7個事件被發(fā)現(xiàn)，同時接近半數(shù)的節(jié)點被訪問到；在7步后，即圖2c，接近80%的節(jié)點被訪問，覆蓋率接近80%，并發(fā)現(xiàn)了所有的事件。在圖2d中，MA覆蓋了近90%的節(jié)點。根據(jù)表2，在第7步時覆蓋率接近80%，并發(fā)現(xiàn)了所有的事件。

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

4.1 RMAWSN的覆蓋性能

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

4.2 RMAWSN的參數(shù)分析

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

1) MA的數(shù)量與覆蓋率

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

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

節(jié)點之間的無線通信是重要的能量消耗因素。越長的通信距離意味著相同密度下的網(wǎng)絡(luò)將消耗更多的通信能量。有意思的是，算法分析中發(fā)現(xiàn)延長通信距離并不能增加網(wǎng)絡(luò)覆蓋的效果。

為研究通信距離與覆蓋率的關(guān)系，圖3和圖4統(tǒng)計了在50×50的范圍內(nèi)部署450個節(jié)點，并且運(yùn)行10步后的結(jié)果。圖3研究節(jié)點在不同通信距離下的累計激活節(jié)點，圖4統(tǒng)計在不同通信距離下的覆蓋率，兩圖結(jié)果均顯示了激活節(jié)點的密度和覆蓋范圍與通信距離無關(guān)?；蛘哒f，通信距離對RMAWSN模式的性能影響很小。實驗說明采用RMAWSN模式的WSN，節(jié)點可以采用較短的通信距離節(jié)約能量，且不影響網(wǎng)絡(luò)的覆蓋率。

5 結(jié) 束 語

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

[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

四川省省級戰(zhàn)略性新興產(chǎn)業(yè)發(fā)展促進(jìn)資金(SC2011510703011)

楊挺(1975 ? )，男，博士，講師，主要從事計算機(jī)網(wǎng)絡(luò)方面的研究.