史霄波，張引，趙杉，肖登明

?

基于離散多目標(biāo)優(yōu)化粒子群算法的多移動代理協(xié)作規(guī)劃

史霄波1,2,3，張引4，趙杉2，肖登明2

（1. 河南師范大學(xué)計算機與信息工程學(xué)院，河南新鄉(xiāng) 453007；2. 華中科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，湖北武漢 430074； 3. 智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實驗室，河南新鄉(xiāng) 453007；4. 中南財經(jīng)政法大學(xué)信息與安全工程學(xué)院，湖北武漢 430073）

無線傳感器網(wǎng)絡(luò)中多移動代理協(xié)作能快速高效地完成感知數(shù)據(jù)匯聚任務(wù)，但是隨著移動代理訪問數(shù)據(jù)源節(jié)點數(shù)的增加，移動代理攜帶的數(shù)據(jù)分組會逐漸增大，導(dǎo)致傳感器節(jié)點能量負載不均衡，部分數(shù)據(jù)源節(jié)點能耗過快，網(wǎng)絡(luò)生存期縮短。目前，針對該問題所設(shè)計的能耗均衡算法，多以降低多移動代理總能耗為目標(biāo)，卻未充分考慮部分數(shù)據(jù)源節(jié)點能量消耗過快對網(wǎng)絡(luò)生存期造成的影響。提出離散多目標(biāo)優(yōu)化粒子群算法，以網(wǎng)絡(luò)的總能耗和移動代理負載均衡作為適應(yīng)度函數(shù)，在多移動代理協(xié)作路徑規(guī)劃中尋求近似最優(yōu)解。通過仿真實驗驗證，所提出的多移動代理協(xié)作路徑規(guī)劃，在網(wǎng)絡(luò)總能耗和網(wǎng)絡(luò)生存期方面的性能優(yōu)于同類其他算法。

移動代理；無線傳感器網(wǎng)絡(luò)；負載均衡；網(wǎng)絡(luò)生存期

1 引言

無線傳感器網(wǎng)絡(luò)（WSN, wireless sensor network）可以將大規(guī)模的傳感器部署在各種各樣的地形甚至危險地區(qū)。WSN多采用自組網(wǎng)的方式進行通信，若和無人機等其他無人操控設(shè)備共同構(gòu)建網(wǎng)絡(luò)，可用于天氣預(yù)測、災(zāi)情監(jiān)測、軍事、交通管理、野外火災(zāi)監(jiān)測等[1,2]。由于傳感器節(jié)點能量有限，因此，如何最大限度利用有限的能量，盡可能延長網(wǎng)絡(luò)生存期，是無線傳感器網(wǎng)絡(luò)的研究熱點之一[3]。Konstantopoulos等[4]將無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)融合技術(shù)歸結(jié)為4類:簇式、鏈?zhǔn)?、樹狀和移動代?MA, mobile agent)的方法。文獻[5]提出，地面?zhèn)鞲衅骶W(wǎng)絡(luò)采用簇式結(jié)構(gòu)，簇頭與無人機進行通信，但是在監(jiān)測點分布分散，簇頭與感知數(shù)據(jù)的傳感器之間距離已經(jīng)超出傳輸范圍的情況下，地面?zhèn)鞲衅骶W(wǎng)絡(luò)適合使用移動代理數(shù)據(jù)融合技術(shù)代替簇式結(jié)構(gòu)[6]。圖1使用移動代理融合技術(shù)的WSN（MAWSN, mobile agent wireless sensor network）中部署數(shù)據(jù)匯聚節(jié)點Sink與無人機進行通信，數(shù)據(jù)收集包括2部分：無人機與Sink通信，Sink派出移動代理收集數(shù)據(jù)源傳感器數(shù)據(jù)。此外，移動代理技術(shù)應(yīng)用于物聯(lián)網(wǎng)領(lǐng)域可以增強系統(tǒng)的智能性，如智慧城市[7]、RFID[8]等。

MAWSN中隨著MA訪問數(shù)據(jù)源傳感器數(shù)量增多，攜帶的數(shù)據(jù)量增大，經(jīng)過傳感器節(jié)點的能耗逐漸增大，路徑遠端的數(shù)據(jù)源節(jié)點能耗遠遠大于路徑近端的數(shù)據(jù)源節(jié)點能耗。在單代理路徑規(guī)劃（SIP，single agent itinerary planning）中，由Sink派出單個移動代理訪問所有的數(shù)據(jù)源傳感器節(jié)點，將傳感器感知的數(shù)據(jù)匯聚到Sink節(jié)點。在SIP算法中（如LCF/GCF[9]、IEMF/IEMA[10]等算法），單個MA需要訪問所有的數(shù)據(jù)源節(jié)點，帶來較嚴重的能耗不均衡和較大的數(shù)據(jù)延遲問題。多代理路徑協(xié)作規(guī)劃（MIP, multi agent itinerary planning）[11]將傳感器節(jié)點進行分組，每組由Sink派出一個移動代理進行訪問，分別將傳感器感知的數(shù)據(jù)匯聚到Sink節(jié)點，如GA-MIP[12]算法、DSG-MIP[13]算法、TBID[14]算法、NOID[15]算法、BST/MST[16]算法等。MIP算法可以看作是SIP算法的迭代。

MIP算法在一定程度上緩解了數(shù)據(jù)源節(jié)點能耗不均衡和數(shù)據(jù)延遲的問題，但是現(xiàn)有的MIP算法仍存在局限性。如MST/BST算法、NOID算法、TBID算法考慮總能耗最小構(gòu)建生成樹，但會因為數(shù)據(jù)源節(jié)點分布密度不均衡而造成單個移動代理訪問數(shù)據(jù)源節(jié)點過多，延遲大，部分數(shù)據(jù)源節(jié)點能耗過高，移動代理能量負載不均衡。GA-MIP算法使用遺傳算法進行移動代理的路徑規(guī)劃，通過若干次迭代尋找優(yōu)化的路徑規(guī)劃方案，但由于評價函數(shù)僅考慮總能耗，也會因為能量負載不均衡影響網(wǎng)絡(luò)的生存期。DSG-MIP算法根據(jù)設(shè)定的半徑尋找Sink的鄰居節(jié)點，以每個鄰居節(jié)點為起點規(guī)劃一條能耗最小的MA路徑訪問指定扇形區(qū)域內(nèi)的數(shù)據(jù)源節(jié)點。當(dāng)數(shù)據(jù)源節(jié)點分布均勻時，DSG-MIP算法可以規(guī)劃出能量效率高的路徑，但是當(dāng)數(shù)據(jù)源節(jié)點密集分布在少數(shù)以Sink節(jié)點鄰居節(jié)點為圓心的扇形區(qū)域時，單個MA訪問數(shù)據(jù)源節(jié)點數(shù)量過多，部分數(shù)據(jù)源節(jié)點能量消耗過快。

綜上所述，現(xiàn)有多移動代理的算法規(guī)劃MA協(xié)作路徑時只考慮總的能量消耗，會因為數(shù)據(jù)源節(jié)點分布密度的不均衡造成單個移動代理訪問的節(jié)點數(shù)過多，部分數(shù)據(jù)源節(jié)點能耗過高，移動代理能量負載不均衡，影響網(wǎng)絡(luò)的生存期。

針對多MA協(xié)作路徑規(guī)劃存在的問題，考慮WSN中MIP的特性，本文設(shè)計離散多目標(biāo)優(yōu)化粒子群算法（DMP-MIP, discrete multi-objectives optimization particle swarm optimizer for MIP），用粒子表示移動代理訪問數(shù)據(jù)源傳感器的分組和訪問順序，通過每次迭代更新粒子得到移動代理新的路徑，以總能耗和移動代理的負載均衡為優(yōu)化目標(biāo)評價粒子，尋找近似最優(yōu)解。文中用到的主要符號定義如表1所示。

表1 主要符號說明

2 問題描述

假設(shè)在MAWSN中隨機密集部署無線傳感器，傳感器節(jié)點的能量有限，個監(jiān)測點作為數(shù)據(jù)源節(jié)點，所有傳感器節(jié)點初始能量已知，網(wǎng)絡(luò)中設(shè)置一個匯聚節(jié)點（Sink），且能量不受限制。當(dāng)異常情況發(fā)生時，無人機向地面無線傳感器網(wǎng)絡(luò)中Sink發(fā)出命令，Sink派出MA按照規(guī)劃好的路徑以無線多跳的方式訪問所有個監(jiān)測點的數(shù)據(jù)源傳感器節(jié)點，將數(shù)據(jù)源傳感器節(jié)點執(zhí)行監(jiān)測任務(wù)感知數(shù)據(jù)帶回Sink節(jié)點。

2.1 數(shù)據(jù)融合模型

本文采用與文獻[10]相同的數(shù)據(jù)融合模型，Sink派出MA時包括固定的數(shù)據(jù)大小，l0表示第個MA的初始大小，l0=proc+head，其中，proc和head分別表示MA中處理模塊和MA自身數(shù)據(jù)。假設(shè)所有數(shù)據(jù)源傳感器感知的數(shù)據(jù)大小相同為data，第個MA訪問路徑中第個數(shù)據(jù)源傳感器節(jié)點后的大小用l表示。MA訪問第1個數(shù)據(jù)源節(jié)點后的大小為l1= l0+rd，其中，rd=(1?)data表示壓縮后的感知數(shù)據(jù)，表示壓縮率。MA訪問路徑中第2個到第個數(shù)據(jù)源傳感器節(jié)點時為了減少數(shù)據(jù)冗余，將當(dāng)前傳感器節(jié)點感知的數(shù)據(jù)和MA傳遞的數(shù)據(jù)進行融合。(0≤≤1)表示數(shù)據(jù)的融合率，1表示數(shù)據(jù)完全融合，0表示數(shù)據(jù)沒有融合，假設(shè)所有數(shù)據(jù)源節(jié)點的融合率相同。MA訪問第個數(shù)據(jù)源節(jié)點后的大小為

MA訪問所有的個數(shù)據(jù)源節(jié)點后，l的值在內(nèi)，取值時表示個傳感器感知的數(shù)據(jù)完全融合成一個數(shù)據(jù)，取值時表示個傳感器的數(shù)據(jù)完全沒有融合。

2.2 能耗模型

根據(jù)2.1節(jié)數(shù)據(jù)融合模型MA訪問節(jié)點后的大小對MA訪問傳感器的能耗進行估算，主要包括數(shù)據(jù)感知、接收、發(fā)送、數(shù)據(jù)壓縮、數(shù)據(jù)融合等能耗[10]。表示第個MA的路徑，MA從Sink節(jié)點出發(fā)訪問所有的個傳感器節(jié)點后返回。每一個節(jié)點的通信能耗包括接收數(shù)據(jù)分組的能耗、控制能耗和發(fā)送能耗。定義ctrl為節(jié)點數(shù)據(jù)通信的控制能耗，rx和tx分別是接收和發(fā)送一個數(shù)據(jù)位的能耗。一個數(shù)據(jù)源節(jié)點的通信能耗表示為

(3)

個MA的總能耗為

2.3 移動代理負載均衡

移動代理負載均衡表示移動代理訪問的所有數(shù)據(jù)源節(jié)點之間的能耗均衡性，定義如下

2.4 多移動代理協(xié)作路徑規(guī)劃

將MAWSN抽象為圖(，)，將數(shù)據(jù)源傳感器節(jié)點的集合分成個子集1～V，=1∪2…∪V，是移動代理的數(shù)量，對于每一個V(1≤≤)找出一個Sink出發(fā)，連接所有數(shù)據(jù)源節(jié)點，返回Sink的回路，作為一條MA訪問傳感器節(jié)點的路徑。多MA協(xié)作路徑規(guī)劃的目標(biāo)是為尋找到評價函數(shù)值最優(yōu)的MA路徑，評價函數(shù)如下

評價函數(shù)中包括總能量消耗和負載均衡2個目標(biāo)，多目標(biāo)優(yōu)化算法尋找最優(yōu)解就是建立非支配解集，類似于單目標(biāo)優(yōu)化問題尋找最優(yōu)解[17]。

定義1 設(shè)1和2是多MA協(xié)作路徑規(guī)劃的2個可行解，如果，稱1支配2，否則，稱1、2互相非支配。

定義2 非支配解是不被可行解集中的任何解支配的解，非支配解集是所有非支配解的集合[18]。

3 DMP-MIP算法

3.1 MOCLPSO算法

粒子群算法(PSO, particle swarm optimization)是仿生進化算法，模仿自然界鳥群覓食的行為，粒子群中每個粒子通過向粒子歷史最優(yōu)解，以及當(dāng)前群內(nèi)最優(yōu)解學(xué)習(xí)改變粒子的速度和位置，最終接近最優(yōu)解。MOCLPSO算法[17]是用于解決多目標(biāo)優(yōu)化問題的PSO算法，結(jié)構(gòu)簡單，收斂迅速，在解決優(yōu)化問題時具有較好的優(yōu)勢，算法在每一代更新粒子速度和位置時選擇使用粒子歷史最優(yōu)解、其他粒子歷史最優(yōu)解、全局最優(yōu)解，保證了粒子群的多樣性有效地避免早熟收斂的出現(xiàn)。

MOCLPSO算法中粒子速度的更新分3種情況，使用粒子群最優(yōu)解更新速度用式(7)，使用其他粒子歷史最優(yōu)解用式(8)，使用粒子歷史最優(yōu)解更新速度用式(9)。粒子位置的更新使用式(10)。

(8)

(9)

其中，X和V分別代表第個粒子的位置和速度，pbest是第個粒子位置的歷史最優(yōu)解，是整個粒子群中粒子位置的當(dāng)前最優(yōu)解，pbest是第f個粒子位置的歷史最優(yōu)解是慣性權(quán)值，()是[0,1]的隨機數(shù)。

粒子位置和速度更新后，尋找當(dāng)前粒子和所有粒子的非支配解更新歷史最優(yōu)解pbest和全局最優(yōu)解。最終得到非支配解的集合是全局最優(yōu)解，等價于單目標(biāo)優(yōu)化算法尋找到最優(yōu)解。MOCLPSO在非支配解集合中隨機選擇一個解作為算法的解。

3.2 DMP-MIP算法研究

PSO算法和MOCLPSO算法用于解決連續(xù)的問題，經(jīng)過離散化處理后可以用于解決TSP問題[19]。多移動代理協(xié)作路徑規(guī)劃問題是離散化問題，本文根據(jù)多移動代理協(xié)作路徑規(guī)劃的特點，設(shè)計離散多目標(biāo)優(yōu)化粒子群算法用于多移動代理協(xié)作路徑規(guī)劃。

3.2.1 編碼

每一個多代理協(xié)作路徑規(guī)劃作為一個粒子，采用整數(shù)編碼的方式，分為2個部分：數(shù)據(jù)源分組編碼和數(shù)據(jù)源順序編碼[12]。數(shù)據(jù)源分組編碼表示派出移動代理的分組情況，以及每個移動代理訪問數(shù)據(jù)源節(jié)點數(shù)，個數(shù)據(jù)源節(jié)點最多分為組派出個移動代理。數(shù)據(jù)源順序編碼表示每個移動代理訪問數(shù)據(jù)源節(jié)點的順序。

如圖2所示，共有8個數(shù)據(jù)源節(jié)點，分為3組：第1個移動代理訪問4個數(shù)據(jù)源節(jié)點{6,3,2,4}，第2個移動代理訪問3個數(shù)據(jù)源節(jié)點{8,1,7}，第3個移動代理訪問1個數(shù)據(jù)源節(jié)點{5}。

數(shù)據(jù)源分組編碼按照訪問節(jié)點的數(shù)量降序排列，如果不按分組節(jié)點數(shù)降序排列，就會出現(xiàn)不同編碼表示相同的多代理路徑規(guī)劃。

3.2.2 粒子速度和位置更新

每一次迭代進化操作對粒子的位置和速度進行更新操作，這里為粒子設(shè)計更新操作。粒子速度式參照式(7)~式(9)修改為式(11)，粒子位置的更新參照式(10)修改為式(12)。

(12)

1) 粒子自學(xué)習(xí)更新速度

粒子速度更新式(11)中的第一項分別使用式(13)和式(14)實現(xiàn)。

(14)

其中，(X_group)表示粒子數(shù)據(jù)源分組編碼變異操作[12]，隨機數(shù)()<時執(zhí)行更新操作。更新時從第個粒子的數(shù)據(jù)源分組編碼X_group中隨機選擇2組分別進行減1和加1操作，然后降序排列，得到更新后的分組編碼。(X_sequences)表示粒子數(shù)據(jù)源順序編碼變異操作[12]，隨機數(shù)()<時執(zhí)行更新操作。變異時隨機選擇第個粒子的數(shù)據(jù)源順序編碼X_sequences中一定數(shù)量的數(shù)據(jù)源節(jié)點，兩兩進行交換，得到更新之后的數(shù)據(jù)源順序編碼。

2) 粒子學(xué)習(xí)最優(yōu)解更新速度

粒子速度更新式(11)中的第2項使用式(15)實現(xiàn)。

其中，Cross表示粒子數(shù)據(jù)源順序編碼更新操作，更新時考慮到編碼由數(shù)據(jù)源分組編碼和數(shù)據(jù)源順序編碼2部分組成，更新操作選擇一組數(shù)據(jù)源節(jié)點，整組進行交換操作。Cross操作和文獻[12]中交叉操作相似，但文獻[12]中只有分組完全相同的兩組編碼才能將對應(yīng)的源順序編碼進行交叉操作，Cross操作對分組沒有限制。

粒子學(xué)習(xí)最優(yōu)解更新速度時，判斷隨機數(shù)()滿足的條件，第個粒子的數(shù)據(jù)源順序編碼_sequences中的一組數(shù)據(jù)源節(jié)點分別和其歷史最優(yōu)解_sequences、全局最優(yōu)解_sequences或第f個粒子的歷史最優(yōu)解中的一組數(shù)據(jù)源節(jié)點進行更新操作。Cross操作分3步完成：①在2個待更新粒子的數(shù)據(jù)源分組編碼中分別選擇一組；②在一個粒子選定組的位置添加另一個粒子選定組的對應(yīng)編碼；③刪除重復(fù)的數(shù)據(jù)源節(jié)點編碼。

3) 粒子位置更新

粒子位置更新使用式(12)，隨機數(shù)()<時粒子位置用更新后的粒子速度更新；否則，保持當(dāng)前的粒子位置。

3.2.3 更新最優(yōu)解

適應(yīng)度函數(shù)中包含網(wǎng)絡(luò)負載均衡和總能耗I這2個目標(biāo)，對每一個粒子計算其負載均衡值和能耗I值。

使用文獻[17]更新粒子歷史最優(yōu)解算法更新pbest，根據(jù)適應(yīng)度函數(shù)中網(wǎng)絡(luò)負載均衡和總能耗I這2個目標(biāo)值判斷當(dāng)前的粒子X是否滿足更新其歷史最優(yōu)解pbest條件，設(shè)置常量б（值根據(jù)具體情況選擇），當(dāng)粒子的歷史最優(yōu)解超過б代都沒更新時拋棄原有的粒子，產(chǎn)生新的第個粒子。

全局最優(yōu)解是一個集合，也就是非支配解的集合。更新全局最優(yōu)解算法[17]使用粒子歷史最優(yōu)解pbest對全局最優(yōu)解進行更新。根據(jù)pbest和中所有粒子的網(wǎng)絡(luò)負載均衡和總能耗I進行判斷，如果pbest被支配全局最優(yōu)解不變；如果pbest支配中的部分粒子，被支配的粒子刪除掉，pbest加入；如果pbest和互相非支配，pbest加入。

3.2.4 算法實施

算法的執(zhí)行分為3個步驟：①初始化粒子群，計算每一個粒子適應(yīng)度函數(shù)值，初始化粒子最優(yōu)解和全局最優(yōu)解集合；②迭代更新粒子速度和位置，更新粒子歷史最優(yōu)解pbest和全局最優(yōu)解集合；③滿足迭代結(jié)束條件時從全局最優(yōu)解集合中選擇能耗最小的粒子作為算法最優(yōu)解輸出。算法流程如圖3所示。

3.2.5 算法復(fù)雜度分析

定理1 設(shè)表示粒子群空間大小，表示粒子群維度（數(shù)據(jù)源順序編碼維度+數(shù)據(jù)源分組編碼維度），表示迭代次數(shù)，算法時間復(fù)雜度是()。

證明 從算法的流程可以看到每一次迭代執(zhí)行更新粒子位置和速度操作的時間復(fù)雜度為()，更新粒子全局最優(yōu)解和粒子最優(yōu)解操作的時間復(fù)雜度為()，所以算法的時間復(fù)雜度為()。

4 仿真

文獻[12]中多移動代理算法GA-MIP算法和本文提出的算法都屬于仿生進化算法，文獻[13]中DSG-MIP算法是解決MA路徑規(guī)劃問題的新方法融合了多種方法的優(yōu)勢，文獻[9]中單移動代理LCF算法是單移動代理的經(jīng)典算法，所以用本文提出的DMP-MIP算法和以上3種方法進行仿真實驗對比。使用OPNET[20]在1 000 m×500 m的范圍內(nèi)隨機部署800個傳感器節(jié)點，Sink節(jié)點部署在網(wǎng)絡(luò)的中心，隨機選取一定數(shù)量的數(shù)據(jù)源傳感器節(jié)點。

如圖4所示，隨機選擇10個數(shù)據(jù)源節(jié)點，Sink節(jié)點派出2個移動代理訪問數(shù)據(jù)源節(jié)點。

移動代理從Sink節(jié)點派出，以無線多跳的方式到達規(guī)劃路徑中的每個傳感器節(jié)點，將數(shù)據(jù)源傳感器節(jié)點感知的數(shù)據(jù)匯聚，傳遞給Sink節(jié)點。網(wǎng)絡(luò)仿真參數(shù)設(shè)置如表2所示。

4.1 評價指標(biāo)

為了評價移動代理路徑規(guī)劃的時間和能量效率，這里使用以下的幾個評價指標(biāo)。

總能耗：包括移動代理中從Sink節(jié)點出發(fā)到返回Sink節(jié)點經(jīng)過的所有數(shù)據(jù)源節(jié)點和中間節(jié)點的數(shù)據(jù)感知能耗、數(shù)據(jù)壓縮能耗、數(shù)據(jù)融合能耗、數(shù)據(jù)接收能耗、數(shù)據(jù)發(fā)送能耗、監(jiān)聽能耗、串?dāng)_能耗等。

表2 移動代理WSN仿真參數(shù)

生存期：數(shù)據(jù)源節(jié)點是數(shù)據(jù)感知任務(wù)的關(guān)鍵節(jié)點，數(shù)據(jù)源節(jié)點的生存期定義為現(xiàn)有能量可以執(zhí)行任務(wù)的次數(shù)，以WSN中所有數(shù)據(jù)源節(jié)點中最短生存期作為WSN的生存期。

任務(wù)延遲：SIP算法中延遲指MA從Sink出發(fā)到返回Sink的時間，MIP算法同時派出多個MA，以最后返回Sink節(jié)點MA的時間作為其延遲時間。

EDP：總能耗和延遲的乘積，總能耗和時間綜合評價性能，值越小表示算法的整體性能越好。

4.2 DMP-MIP算法參數(shù)設(shè)置

粒子群空間大小和迭代次數(shù)對算法的性能有影響，下面對群空間和迭代次數(shù)對總能耗的影響進行分析。仿真結(jié)果顯示大的粒子群搜索空間和較多的迭代次數(shù)搜索到的路徑解具有較小的能耗，但是計算量大。實驗在迭代次數(shù)達到300時總能耗的變化趨于平穩(wěn)，粒子群空間80時總能能耗接近最小，所以選擇粒子群空間大小80、迭代300代，如圖5和圖6所示。

4.3 仿真結(jié)果

數(shù)據(jù)源傳感器節(jié)點數(shù)設(shè)置為5~40，步長5，數(shù)據(jù)源傳感器節(jié)點的位置隨機分布，設(shè)置200個不同的隨機數(shù)種子運行仿真，對DMP-MIP算法和文獻[12]中GA-MIP算法、文獻[9]中LCF算法、文獻[13]中DSG-MIP算法性能取平均值進行比較。

如圖7所示，3種MIP算法在數(shù)據(jù)源節(jié)點數(shù)較少的情況下總能耗和LCF基本相同，隨著節(jié)點數(shù)的增加雖然總能耗高于LCF算法，因為MIP算法派出多個移動代理，每個移動代理自身的數(shù)據(jù)增加了額外的能耗，DMP-MIP算法在能耗上明顯低于同類的GA-MIP算法和DSG-MIP算法。

圖8為數(shù)據(jù)源節(jié)點數(shù)對生存期的影響，DMP-MIP、GA-MIP、DSG-MIP算法生存期超出LCF算法多倍，因為SIP算法用一個MA訪問所有數(shù)據(jù)源節(jié)點，MA最后訪問的數(shù)據(jù)源傳感器節(jié)點能耗過高，而MIP算法派出多個MA訪問數(shù)據(jù)源節(jié)點，每個MA訪問數(shù)據(jù)源節(jié)點數(shù)相對SIP少，數(shù)據(jù)源傳感器節(jié)點的能耗相對均衡，從而延長網(wǎng)絡(luò)的生存期。數(shù)據(jù)源傳感器節(jié)點數(shù)增大時LCF算法生存期急劇下降。DMP-MIP、DSG-MIP和GA-MIP生存期隨著數(shù)據(jù)源節(jié)點數(shù)的增加也呈現(xiàn)緩慢下降的趨勢，DMP-MIP算法在路徑規(guī)劃時考慮移動代理負載均衡，生存期比GA-MIP和DSG-MIP算法長。

圖9為數(shù)據(jù)源節(jié)點數(shù)對任務(wù)延遲的影響，MIP算法任務(wù)延遲明顯小于LCF算法。LCF算法Sink派出一個MA訪問分布在WSN中的所有傳感器節(jié)點延遲較大，而MIP算法Sink派出多個MA訪問傳感器節(jié)點，節(jié)省較多的時間。GA-MIP、DMP-MIP、DSG-MIP 3種算法在數(shù)據(jù)源節(jié)點數(shù)增加時，因為單個移動代理要訪問的數(shù)據(jù)源節(jié)點數(shù)增加，任務(wù)延遲呈增加趨勢。

EDP在衡量路徑規(guī)劃算法的效率是一項非常重要的參數(shù)，圖10顯示3種MIP算法的EDP明顯低于LCF算法，DMP-MIP算法的EDP低于GA-MIP和DSG-MIP。

5 結(jié)束語

移動代理的使用可以促進WSN智能化，多移動代理協(xié)作是優(yōu)化移動代理能耗的關(guān)鍵問題。本文首先介紹了現(xiàn)有SIP算法和MIP算法，這些算法在規(guī)劃路徑時考慮總能耗，忽略單個傳感器節(jié)點的能耗均衡問題，影響網(wǎng)絡(luò)的生存期。為了解決這個問題，本文設(shè)計了基于總能耗和移動代理負載均衡2個約束目標(biāo)的DMP-MIP算法，通過大量的仿真對比實驗，仿真結(jié)果顯示該算法在各項評價指標(biāo)上均優(yōu)于同類算法。

WSN中使用多移動代理協(xié)作規(guī)劃下一步研究，可以將固定的Sink改變?yōu)橐苿拥腟ink，更適應(yīng)于真實的應(yīng)用，路徑規(guī)劃仿真假設(shè)所有的傳感器節(jié)點都是可用的，真實的環(huán)境中可能有些傳感器無法使用，設(shè)計動態(tài)的路徑規(guī)劃才能滿足需要。

[1] VARAKLIOTIS S, HAILES S, DENARIDI R, et al. UAV and cognitive radio technologies in the emergency services arena[J/OL]. British Association of Public Safety Communications Officials, http://eprints. ucl.ac.uk.

[2] ZAJKOWSKI T, DUNAGAN S, EILERS J. Small UAS communications mission[C]//Eleventh Biennial USDA Forest Service Remote Sensing Applications. Salt Lake City, UT, c2006.

[3] SALEEM F, MOEEN Y, BEHZAD M, et al. IDDR: Improved density controlled divide-and-rule scheme for energy efficient routing in wireless sensor networks[J]. Procedia Computer Science, 2014, 34: 212-219.

[4] KONSTANTOPOULOS C, MPITZIOPOULOS A, GAVALAS D, et al. Effective determination of mobile agent itineraries for data aggregation on sensor networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(12): 1679-1693.

[5] ABDULLA A E A A, FADLULLAH Z M, NISHIYAMA H, et al. An optimal data collection technique for improved utility in UAS-aided networks[C]//INFOCOM 2014. Toronto, Canada, c2014: 736-744.

[6] 蘇金樹, 郭文忠, 余朝龍, 等. 負載均衡感知的無線傳感器網(wǎng)絡(luò)容錯分簇算法[J]. 計算機學(xué)報, 2014, 37(2): 445-456.

SU J S, GUO W Z, YU C L, et al. Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network[J]. Chinese Journal of Computers,2014,37(2): 445-456.

[7] CHEN M. Towards smart city: M2M communications with software agent intelligence[J]. Multimedia Tools and Applications, 2013, 67(1):167-178.

[8] CHEN M, GONZALEZ S, ZHANG Q, et al. Code-centric RFID systems based on software agent intelligence[J]. IEEE Intelligent Systems, 2010,25(2):12-19.

[9] QI H R, WANG F Y. Optimal itinerary analysis for mobile agents in ad hoc wireless sensor networks[C]//Proceedings of the IEEE, c2001: 147-153.

[10] CHEN M, YANG L T, KWON T, et al. Itinerary planning for energy-efficient agent communications in wireless sensor networks[J]. IEEE Transactions on Vehicular Technology, 2011, 60(7): 3290-3299.

[11] CHEN M, LEUNG V, MAO S.W, et al. Energy-efficient itinerary planning for mobile agents in wireless sensor networks[C]//IEEE International Conference on Communications (ICC'09). Dresden, Germany, c2009: 1-5.

[12] CAI W, CHEN M, HARA T, et al. A genetic algorithm approach to multi-agent itinerary planning in wireless sensor networks[J]. Mobile Networks and Applications, 2011, 16(6): 782-793.

[13] WANG J F, ZHANG Y, CHENG Z L, et al. EMIP: energy-efficient itinerary planning for multiple mobile agents in wireless sensor network[J/OL]. Telecommunication Systems, http://eprints.ucl.ac.uk.

[14] KONSTANTOPOULOS C, MPITZIOPOULOS A, GAVALAS D, et al. Effective determination of mobile agent itineraries for data aggregation on sensor networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(12): 1679-1693.

[15] GAVALAS D, MPITZIOPOULOS A, PANTZIOU G, et al. An approach for near-optimal distributed data fusion in wireless sensor networks[J]. Wireless Networks, 2010, 16(5): 1407-1425.

[16] CHEN M, CAI W, GONZALEZ S, et al. Balanced itinerary planning for multiple mobile agents in wireless sensor networks[M].Ad Hoc Networks. Springer Berlin Heidelberg, 2010: 416-428.

[17] HUANG V L, SUGANTHAN P N, LIANG J J. Comprehensive learning particle swarm optimizer for solving multiobjective optimization problems[J]. International Journal of Intelligent Systems, 2006, 21(2): 209-226.

[18] MAO W T, ZHAO S J, MU X X, et al. Multi-dimensional extreme learning machine[J]. Neurocomputing, 2015, 149(4): 160-170.

[19] CLERC M. Discrete particle swarm optimization, illustrated by the traveling salesman problem[M].New optimization techniques in engineering. Springer Berlin Heidelberg, 2004.

[20] 陳敏. OPNET物聯(lián)網(wǎng)仿真[M].武漢：華中科技大學(xué)出版社. 2015.

CHEN M. OPNET Internet of things simulation[M]. Wuhan: Huazhong University of Science and Technology Press, 2015.

Discrete multi-objective optimization of particle swarm optimizer algorithm for multi-agents collaborative planning

SHI Xiao-bo1,2,3, ZHANG Yin4, ZHAO Shan2, XIAO Deng-ming2

(1. College of Computer and Information Engineering, Henan Normal University, Xinxiang 453007, China; 2. School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China; 3. Engineering Lab of Intelligence Business & Internet of Things, Henan Province, Xinxiang 453007, China; 4. School of Information and Safety Engineering, Zhongnan University of Economics and Law, Wuhan 430073, China)

Although multiple mobile agents (MA) collaboration can quickly and efficiently complete data aggregation in wireless sensor network, the MA carrying data packages extensively increase along with a raise in the number of data source nodes accessed by MA, which causes unbalanced energy load of sensor nodes, high energy consumption of partial source nodes, and shortened lifetime of networks. The existing related works mainly focus on the objective of decreasing total energy consumption of multiple MA, without considering that rapidly energy consumption of partial source nodes has a negative effect on networks lifetime. Therefore, discrete multi-objective optimization of particle swarm algorithm was proposed, which used the total network energy consumption and mobile agent load balancing as fitness function for the approximate optimal itinerary plan in multiple mobile agent collaboration. Furthermore, the simulation result of the proposed algorithm is better than the similar algorithm in total energy consumption and network lifetime.

mobile agent, wireless sensor network, load balancing, lifetime of WSN

TP393

A

10.11959/j.issn.1000-436x.2016113

2015-08-27；

2016-04-05

河南省重點科技攻關(guān)基金資助項目（No.132102210483, No.102102210178）；河南省基礎(chǔ)與前沿技術(shù)研究

項目（No.122300410344）；河南省教育廳自然科學(xué)研究計劃基金資助項目（No.2008A520013）

Key Science and Technology Program of Henan Province (No.132102210483, No.102102210178), The Foundation and Cutting-edge Technologies Research Program of Henan Province (No.122300410344), Natural Science Research Projects of Department of Education of Henan Province (No.2008A520013)

史霄波（1972-），女，河南焦作人，河南師范大學(xué)副教授，華中科技大學(xué)博士生，主要研究方向為無線傳感器網(wǎng)絡(luò)、機器學(xué)習(xí)、智能醫(yī)療等。

張引（1986-），男，江西九江人，中南財經(jīng)政法大學(xué)講師，主要研究方向為數(shù)據(jù)挖掘、推薦系統(tǒng)、智能服務(wù)等。

趙杉（1993-），男，安徽宿州人，華中科技大學(xué)碩士生，主要研究方向為大數(shù)據(jù)、云平臺等。

肖登明（1989-），男，湖北仙桃人，華中科技大學(xué)碩士生，主要研究方向為云計算、大數(shù)據(jù)分析、數(shù)據(jù)挖掘。