基于速度差分變異粒子群的RFID網(wǎng)絡(luò)優(yōu)化

吳 瓊，紀(jì)志成，吳定會

（江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫214122）

0 引 言

RFID 網(wǎng)絡(luò)規(guī)劃問題可描述為在工作區(qū)域內(nèi)部署m 個讀寫器讀取n 個電子標(biāo)簽信息。合理的RFID 網(wǎng)絡(luò)規(guī)劃不僅可以提高網(wǎng)絡(luò)的覆蓋質(zhì)量，還可以提高網(wǎng)絡(luò)的成本效率，保證 網(wǎng)絡(luò)的連通 質(zhì)量［1－3］。

目前，針對RFID 網(wǎng)絡(luò)規(guī)劃即優(yōu)化部署問題已有一定的研究，文獻 ［4］利用混沌原理優(yōu)化粒子群算法，以提高網(wǎng)絡(luò)覆蓋率為目標(biāo)，對RFID 與WSNs集成網(wǎng)絡(luò)智能節(jié)點的部署進行優(yōu)化。文獻 ［5］將遺傳算法與粒子群算法相結(jié)合，利用兩種算法并行優(yōu)化的方式實現(xiàn)RFID 網(wǎng)絡(luò)中讀寫器的合理部署。文獻 ［6］利用改進粒子群算法，根據(jù)工作區(qū)域內(nèi)電子標(biāo)簽的實際數(shù)量與位置分布，動態(tài)調(diào)整讀寫器個數(shù)，減少區(qū)域內(nèi)讀寫器的冗余。文獻 ［7］以加強網(wǎng)絡(luò)覆蓋率和降低網(wǎng)絡(luò)成本為目標(biāo)，采用一種禁忌搜索算法對帶有容量約束的讀寫器部署模型進行優(yōu)化。文獻 ［8］將遺傳算法變異機制引入到粒子群算法中，提出了一種帶變異機制的粒子群優(yōu)化算法，以提高讀寫器對電子標(biāo)簽的覆蓋率，降低信號間的干擾為目標(biāo)，對RFID 網(wǎng)絡(luò)進行優(yōu)化部署。上述文獻的研究都取得了可觀的結(jié)果，但都未考慮到RFID網(wǎng)絡(luò)實際的經(jīng)濟效益。

粒子群算法具有收斂速度快，搜索精度高，操作簡單，易實現(xiàn)等優(yōu)點，但在進化后期算法易陷入局部最優(yōu)解，不能保證找到全局最優(yōu)解。因此本文將差分變異思想引入到粒子群算法中，提出了一種利用差分算法進一步優(yōu)化粒子群算法的速度差分變異粒子群算法，并將其應(yīng)用到優(yōu)化RFID網(wǎng)絡(luò)規(guī)劃中，在保證網(wǎng)絡(luò)負(fù)載平衡的前提下，提高網(wǎng)絡(luò)中讀寫器對電子標(biāo)簽的覆蓋率和網(wǎng)絡(luò)經(jīng)濟效益。

1 網(wǎng)絡(luò)優(yōu)化模型

在實際應(yīng)用中，RFID 網(wǎng)絡(luò)規(guī)劃不僅要保證目標(biāo)區(qū)域內(nèi)讀寫器對電子標(biāo)簽的覆蓋率達到要求，同時要降低讀寫器與讀寫器之間干擾，降低網(wǎng)絡(luò)成本，提高網(wǎng)絡(luò)的經(jīng)濟效益。因此RFID 網(wǎng)絡(luò)模型應(yīng)同時滿足以下3個方面的問題：

（1）讀寫器對標(biāo)簽的覆蓋：在RFID 網(wǎng)絡(luò)規(guī)劃中，讀寫器對標(biāo)簽的覆蓋問題是首要問題，要盡可能的保證讀寫器的高覆蓋率，減少網(wǎng)絡(luò)設(shè)備成本，RFID 網(wǎng)絡(luò)覆蓋率性能指標(biāo)表示如下

式中：n——目標(biāo)區(qū)域內(nèi)電子標(biāo)簽的個數(shù)，Ci——電子標(biāo)簽i的覆蓋情況，當(dāng)標(biāo)簽i被一個或多個讀寫器覆蓋時，Ci＝1，否則Ci＝0。

（2）網(wǎng)絡(luò)經(jīng)濟效益：為了提高網(wǎng)絡(luò)的經(jīng)濟效益，讀寫器應(yīng)盡可能部署在電子標(biāo)簽密集區(qū)域，該性能指標(biāo)可用下式表示

式中：m——目標(biāo)區(qū)域內(nèi)讀寫器的個數(shù)，di——第i個讀寫器距離標(biāo)簽密集區(qū)域的距離，f2越大，網(wǎng)絡(luò)經(jīng)濟效益越高。

（3）網(wǎng) 絡(luò) 負(fù) 載 平 衡［9］：RFID 網(wǎng) 絡(luò) 負(fù) 載 平 衡 問 題 是RFID 網(wǎng)絡(luò)規(guī)劃的必備問題，網(wǎng)絡(luò)中讀寫器的負(fù)載分布情況關(guān)乎網(wǎng)絡(luò)的使用壽命和穩(wěn)定性，是RFID 網(wǎng)絡(luò)規(guī)劃的一個重要組成部分，該性能指標(biāo)可如下表示

式中：ki——讀取i電子標(biāo)簽的讀寫器的個數(shù)，通過均衡每個讀寫器讀取的電子標(biāo)簽數(shù)量來達到RFID 讀寫器網(wǎng)絡(luò)負(fù)載均衡的目的，f3越大，網(wǎng)絡(luò)負(fù)載分配的越均衡。

為了同時滿足上述3個優(yōu)化目標(biāo)，采用加權(quán)和的方式，將上述多目標(biāo)問題轉(zhuǎn)換成單目標(biāo)問題進行求解，因此RFID網(wǎng)絡(luò)規(guī)劃問題的優(yōu)化目標(biāo)函數(shù)可表示為

其中，w1＋w2＋w3＝1，w1，w2和w3分別表示覆蓋率、網(wǎng)絡(luò)經(jīng)濟效益和負(fù)載平衡的權(quán)重，其大小表示實際工程應(yīng)用中RFID 網(wǎng)絡(luò)規(guī)劃部署的具體要求。

2 算法描述

2.1 算法基本思想

（1）粒子群 （PSO）算法M 個粒子構(gòu)成的種群在D 維的工作區(qū)域內(nèi)飛行搜索，每個粒子是待求解問題的一個解決方案，解的優(yōu)劣由求解問題的目標(biāo)函數(shù)決定。所有粒子在工作區(qū)域內(nèi)以一定的速度飛行并不斷追尋群體中的最優(yōu)粒子，直至達到終止條件或找到滿意解為止，粒子i在t次迭代后的狀態(tài)如下所示：

位置：xi＝ （xi1，xi2，…，xiD），xid∈ ［a，b］其中a、b分別表示工作區(qū)域上、下界；

速度：vi＝ （vi1，vi2，…，viD），vid∈ ［vmin，vmax］其中vmin、vmax分別粒子運動的最小、最大速度；當(dāng)前個體最優(yōu)位置：pi＝ （pi1，pi2，…，piD）；當(dāng)前種群最優(yōu)位置：pg＝ （pg1，pg2，…，pgD）；其中1≤d≤D，1≤i≤M。

第t＋1次迭代后，粒子i速度和位置的更新機制如下所示［4］

式中：t——當(dāng)前迭代次數(shù)，T——算法總的迭代次數(shù)，wmax、wmin——慣性權(quán)重的最大和最小值。

粒子群算法具有記憶搜索過程中的個體最優(yōu)解和種群最優(yōu)解的能力，并通過個體和種群最優(yōu)解以及本身狀態(tài)指導(dǎo)粒子下一步的尋優(yōu)過程，算法搜索速度快，搜索精度高。但在進化后期，粒子都趨于最優(yōu)解，種群多樣性降低，算法易陷入局部最優(yōu)解。

（2）差分進化算法：差分進化（DE）算法是一種基于群體差異的全局并行搜索算法［11，12］。其基本思想是，與粒子群算法相似，隨機產(chǎn)生一個初始群體，對該群體中的個體按照一定規(guī)則進行變異、交叉和選擇操作，不斷地迭代計算，根據(jù)群體內(nèi)各個體的適應(yīng)值，優(yōu)勝劣汰，引導(dǎo)搜索過程向群體內(nèi)最優(yōu)解逼近。DE算法在種群進化前期尋優(yōu)能力強，搜索速度快，穩(wěn)??；算法可記憶個體最優(yōu)解，通過粒子的交叉和變異操作有效保持種群的多樣性，從而保證全局最優(yōu)。

（3）速度差分變異粒子群 （VDM－PSO）算法 為了改進粒子群算法尋優(yōu)后期進化停滯現(xiàn)象，本文將差分變異思想引入到粒子群算法中，取長補短，提出了一種帶壓縮因子和慣性權(quán)重的速度差分變異粒子群優(yōu)化算法，在保證算法前期收斂速度和后期搜索精準(zhǔn)性的前提下，增強算法鄰域搜索能力和進化后期種群多樣性，提高算法進化后期的尋優(yōu)速度和尋優(yōu)能力，保證全局最優(yōu)解的獲取。粒子速度差分變異公式定義如下

其中：k表示粒子的任一維度，以保證粒子至少有一個維度的速度發(fā)生了變異；r表示 ［0，1］間的隨機數(shù)；CR 為粒子變異概率即交叉因子。F 表示變異因子，為 ［0，2］之間的一個常數(shù)。v1d，v2d為vi中隨機選取的兩個粒子d維的速度。粒子的變異時機由粒子的進化停滯步數(shù)t0確定，當(dāng)t0大于停滯閾值T0時，粒子開始變異。

2.2 算法設(shè)計

以式 （4）為網(wǎng)絡(luò)規(guī)劃的優(yōu)化目標(biāo)，設(shè)計算法的具體步驟如下所示：

（1）初始化種群以及算法運行參數(shù)。

（2）根據(jù)式 （4）計算種群內(nèi)各粒子的適應(yīng)度。

（3）找出群體內(nèi)每個粒子的個體歷史最優(yōu)解和種群全局最優(yōu)解。

（4）對種群中的各個粒子，按式 （5）和式 （6）更新速度和位置。

（5）當(dāng)粒子進化停滯步數(shù)大于設(shè)定值時，轉(zhuǎn)入步驟（6），否則轉(zhuǎn)入步驟 （9）。

（6）產(chǎn)生一個隨機數(shù)，若隨機數(shù)小于變異概率，則對種群內(nèi)的各粒子進行變異交叉操作；否則轉(zhuǎn)入步驟 （7）。

（7）隨機選取群體內(nèi)粒子的任一維度進行變異交叉操作。

（8）若變異后的粒子適應(yīng)值優(yōu)于變異前，則用變異后的粒子取代變異前，否則轉(zhuǎn)入步驟 （6）繼續(xù)變異，直至成功。

（9）若達到算法的終止條件，則優(yōu)化過程結(jié)束，輸出算法獲取的最優(yōu)解，否則轉(zhuǎn)入步驟 （2）繼續(xù)尋優(yōu)過程。

算法流程如圖1所示。

圖1 算法流程

3 實例仿真

3.1 仿真環(huán)境及參數(shù)設(shè)定

本文采用MATLAB7.1仿真軟件對RFID 網(wǎng)絡(luò)中讀寫器的部署規(guī)劃進行仿真。讀寫器的工作區(qū)域為30m×30m的正方形，利用9個讀寫器對該工作區(qū)域內(nèi)隨機分布的50個電子標(biāo)簽進行數(shù)據(jù)采集。粒子種群大小M 為150，搜索空間維數(shù)D 為27，算法的最大迭代次數(shù)T 為500。當(dāng)種群進化停滯步數(shù)大于設(shè)定的停滯閾值時，粒子根據(jù)變異條件進行變異和交叉操作。由于在實際應(yīng)用中RFID 網(wǎng)絡(luò)中讀寫器的覆蓋區(qū)域并非一個理想的圓形，而是一個近似的橢圓形，因此本文采用橢圓模型進行實例仿真，此處取橢圓長軸5m，短軸4m［8］，橢圓的位置、旋轉(zhuǎn)角度由粒子維度分量確定。算法其它仿真參數(shù)見表1。

表1 仿真參數(shù)

為了驗證VDM－PSO 算法在RFID 網(wǎng)絡(luò)規(guī)劃部署問題求解上的應(yīng)用效果，將其優(yōu)化結(jié)果與PSO 算法在相同讀寫器初始分布下進行了比較，為保證比較結(jié)果的公平性，兩種算法采用相同的仿真參數(shù)。圖2為工作區(qū)域內(nèi)讀寫器的初始分布，其中星形點表示電子標(biāo)簽的位置，空心圓點表示讀寫器的位置，橢圓區(qū)域表示讀寫器的通信邊界。

圖2 初始讀寫器分布

3.2 仿真結(jié)果與分析

利用VDM－PSO 和PSO 兩種優(yōu)化算法優(yōu)化后工作區(qū)域內(nèi)讀寫器的分布和適應(yīng)度函數(shù)變化曲線分別如圖3 和圖4所示。

圖3 讀寫器分布對比

圖4 適應(yīng)值對比

由圖3可以看出，VDM－PSO 算法較PSO 算法可以獲得更好的標(biāo)簽覆蓋率，且在標(biāo)簽密集區(qū)域，采用VDM－PSO算法優(yōu)化后，各讀寫器讀寫區(qū)域重疊減少，網(wǎng)絡(luò)的負(fù)載更為均衡，網(wǎng)絡(luò)的經(jīng)濟效益更高。對比兩種算法的適應(yīng)度函數(shù)曲線，可以看到，兩種算法都具有很快的收斂速度，但VDM－PSO 算法能夠避免早熟問題，及時跳出局部極點，防止算法陷入局優(yōu)，如圖4所示，PSO 算法在迭代初步即陷入局優(yōu)，尋優(yōu)結(jié)果不佳，相比PSO 算法，VDM－PSO 算法適應(yīng)值曲線的跳變?yōu)榱Ｗ舆^早收斂時，采用差分原理對粒子進行變異交叉操作，有效保持了粒子群體的多樣性，從而擺脫局部極點的束縛，增強了粒子的鄰域搜索能力，保證全局最優(yōu)解的獲取。

為了進一步驗證VDM－PSO 算法在RFID 網(wǎng)絡(luò)規(guī)劃方面的性能，在不同初始讀寫器分布情況下，將兩種算法分別運行10次［13］，優(yōu)化后的平均最優(yōu)適應(yīng)值，達到最優(yōu)適應(yīng)值的迭代次數(shù)和讀寫器平均移動距離對比見表2。

表2 10次獨立優(yōu)化性能對比

由表2可知，VDM－PSO 算法的平均最大適應(yīng)值和讀寫器的平均移動距離顯著優(yōu)于PSO 算法，提高了網(wǎng)絡(luò)優(yōu)化效果，同時降低了因讀寫器移動帶來的能量消耗，降低了網(wǎng)絡(luò)成本，提高了網(wǎng)絡(luò)總體經(jīng)濟效益，說明了該算法在求解網(wǎng)絡(luò)規(guī)劃問題上的有效性。由于VDM－PSO 算法在進化停滯時加入了速度差分變異、交叉操作，使得算法陷入局部最優(yōu)時能夠及時跳出，增強了算法的全局與鄰域搜索能力，保證全局最優(yōu)，也因此算法達到最大適應(yīng)值的迭代次數(shù)相比PSO 算法要高，但仍具有較快的收斂速度。

4 結(jié)束語

本文針對RFID 網(wǎng)絡(luò)讀寫器的優(yōu)化部署問題，建立多目標(biāo)網(wǎng)絡(luò)優(yōu)化部署模型，提出一種基于速度差分變異粒子群的RFID 網(wǎng)絡(luò)優(yōu)化算法。利用差分算法對粒子群算法速度更新機制進行改進，提高進化后期種群的多樣性，增強算法的鄰域搜索能力，有效防止算法陷入局部最優(yōu)解，保證全局最優(yōu)解。仿真實驗結(jié)果表明，該算法在提高RFID網(wǎng)絡(luò)覆蓋率，加強網(wǎng)絡(luò)負(fù)載平衡和增加網(wǎng)絡(luò)經(jīng)濟效益方面，顯著優(yōu)于標(biāo)準(zhǔn)粒子群算法，能夠有效實現(xiàn)RFID 網(wǎng)絡(luò)資源的合理分布。但該算法在求解較大規(guī)模的RFID 網(wǎng)絡(luò)規(guī)劃問題方面的有效性還有待進一步的研究與驗證。

［1］Kranzfelder Michael，Schneider Armin，F(xiàn)iolka Adam，et al.Real－time instrument detection in minimally invasive surgery using radiofrequency identification technology ［J］.Journal of Surgical Research，2013，185 （2）：704－710.

［2］Hinkka Ville，Tatila Jaakko.RFID tracking implementation model for the technical trade and construction supply chains［J］.Automation in Construction，2013，35 （1）：405－414.

［3］Xu Zhitao，Ming X G，Zhou Jingling，et al.Management optimisation based on dynamic SKU for RFID－enabled warehouse management in the steel supply chain ［J］.International Journal of Production Research，2013，51 （10）：2981－2996.

［4］JI Zhicheng，ZHANG Yunya.Optimization of the integrated networks based on chaos particle swarm algorithm ［J］.Control Engineering of China，2012，19 （5）：737－739 （in Chinese）.［紀(jì)志成，張云亞.基于混沌粒子群算法的集成網(wǎng)絡(luò)優(yōu)化 ［J］.控制工程，2012，19 （5）：737－739.］

［5］Chiu Chuiyu，Ke Chenghsin，Chen K Y.Optimal RFID net－works scheduling using genetic algorithm and swarm intelligence［C］／／Proc of the IEEE International Conference on System，Man，and Cybernetics，2009：1201－1208.

［6］Gong Yuejiao，Shen Meie，Zhang Jun，et al.Optimizing RFID network planning by using aparticle swarm optimization algorithm with redundant reader elimination ［J］.IEEE Transactions on Industrial Informatics，2012，8 （4）：900－912.

［7］WANG Yonghua，YANG Jian，ZHAN Yiju，et al.RFID networks planning based on tabu search algorithms［J］.Application Research of Computers，2011，28 （6）：2116－2119 （in Chinese）.［王永華，楊健，詹宜巨，等.一種基于禁忌搜索的RFID讀寫器部署算法 ［J］.計算機應(yīng)用研究，2011，28（6）：2116－2119.］

［8］FENG Han.RFID systems optimization deployment research and application ［D］.Shanghai：Donghua University，2013：18－37 （in Chinese）.［馮晗.RFID 系統(tǒng)優(yōu)化部署研究與應(yīng)用［D］.上海：東華大學(xué)，2013：18－37.］

［9］Chen Hanning，Zhu Yunlong.RFID networks planning using a multi－swarm optimizer ［C］／／Proc of Chinese Control and Descision Conference.Piscataway.NJ：IEEE Press，2009：3548－3552.

［10］Li Yanliang，Shao Wei，You Long，et al.An improved PSO algorithm and its application to UWB antenna design ［J］.IEEE Antennas and Wireless Propagation Letters，2013，12：1236－1239.

［11］Mandal KK，Chakraborty N.Differential evolution techniquebased short－term economic generation scheduling of hydrothermal systems ［J］.Electric Power Systems Research，2008，78 （11）：1972－1979.

［12］YANG Yan，CHEN Ruqing，YU Jinshou.Study on differential evolution－particle swarm optimization based hybrid optimization algorithm and its application［J］.Computer Engineering and Applications，2010，46 （25）：238－241（in Chinese）. ［楊妍，陳如清，俞金壽.差分進化粒子群混合優(yōu)化算法的研究與應(yīng)用［J］.計算機工程與應(yīng)用，2010，46 （25）：238－241.］

［13］LIU Weiting，F(xiàn)AN Zhouyuan.Based on chaotic particle swarm optimization of wireless sensor network coverage ［J］.Computer Applications，2011，31 （2）：338－341 （in Chinese）.［劉維亭，范洲遠(yuǎn).基于混沌粒子群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化 ［J］.計算機應(yīng)用，2011，31 （2）：338－341.］