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

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

?

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

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

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

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

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

1 引言

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

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

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

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

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

表1 主要符號(hào)說(shuō)明

2 問(wèn)題描述

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

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

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

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

2.2 能耗模型

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

(3)

個(gè)MA的總能耗為

2.3 移動(dòng)代理負(fù)載均衡

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

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

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

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

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

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

3 DMP-MIP算法

3.1 MOCLPSO算法

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

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

(8)

(9)

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

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

3.2 DMP-MIP算法研究

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

3.2.1 編碼

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

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

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

3.2.2 粒子速度和位置更新

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

(12)

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

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

(14)

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

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

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

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

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

3) 粒子位置更新

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

3.2.3 更新最優(yōu)解

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

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

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

3.2.4 算法實(shí)施

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

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

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

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

4 仿真

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

如圖4所示，隨機(jī)選擇10個(gè)數(shù)據(jù)源節(jié)點(diǎn)，Sink節(jié)點(diǎn)派出2個(gè)移動(dòng)代理訪問(wèn)數(shù)據(jù)源節(jié)點(diǎn)。

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

4.1 評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)移動(dòng)代理路徑規(guī)劃的時(shí)間和能量效率，這里使用以下的幾個(gè)評(píng)價(jià)指標(biāo)。

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

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

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

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

EDP：總能耗和延遲的乘積，總能耗和時(shí)間綜合評(píng)價(jià)性能，值越小表示算法的整體性能越好。

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

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

4.3 仿真結(jié)果

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

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

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

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

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

5 結(jié)束語(yǔ)

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

WSN中使用多移動(dòng)代理協(xié)作規(guī)劃下一步研究，可以將固定的Sink改變?yōu)橐苿?dòng)的Sink，更適應(yīng)于真實(shí)的應(yīng)用，路徑規(guī)劃仿真假設(shè)所有的傳感器節(jié)點(diǎn)都是可用的，真實(shí)的環(huán)境中可能有些傳感器無(wú)法使用，設(shè)計(jì)動(dòng)態(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] 蘇金樹(shù), 郭文忠, 余朝龍, 等. 負(fù)載均衡感知的無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)分簇算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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

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

項(xiàng)目（No.122300410344）；河南省教育廳自然科學(xué)研究計(jì)劃基金資助項(xiàng)目（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é)博士生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)、智能醫(yī)療等。

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

趙杉（1993-），男，安徽宿州人，華中科技大學(xué)碩士生，主要研究方向?yàn)榇髷?shù)據(jù)、云平臺(tái)等。

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