基于速度差分變異粒子群的RFID網絡優化

吳 瓊，紀志成，吳定會

（江南大學 物聯網工程學院，江蘇 無錫214122）

0 引 言

RFID 網絡規劃問題可描述為在工作區域內部署m 個讀寫器讀取n 個電子標簽信息。合理的RFID 網絡規劃不僅可以提高網絡的覆蓋質量，還可以提高網絡的成本效率，保證 網絡的連通 質量［1－3］。

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

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

1 網絡優化模型

在實際應用中，RFID 網絡規劃不僅要保證目標區域內讀寫器對電子標簽的覆蓋率達到要求，同時要降低讀寫器與讀寫器之間干擾，降低網絡成本，提高網絡的經濟效益。因此RFID 網絡模型應同時滿足以下3個方面的問題：

（1）讀寫器對標簽的覆蓋：在RFID 網絡規劃中，讀寫器對標簽的覆蓋問題是首要問題，要盡可能的保證讀寫器的高覆蓋率，減少網絡設備成本，RFID 網絡覆蓋率性能指標表示如下

式中：n——目標區域內電子標簽的個數，Ci——電子標簽i的覆蓋情況，當標簽i被一個或多個讀寫器覆蓋時，Ci＝1，否則Ci＝0。

（2）網絡經濟效益：為了提高網絡的經濟效益，讀寫器應盡可能部署在電子標簽密集區域，該性能指標可用下式表示

式中：m——目標區域內讀寫器的個數，di——第i個讀寫器距離標簽密集區域的距離，f2越大，網絡經濟效益越高。

（3）網 絡 負 載 平 衡［9］：RFID 網 絡 負 載 平 衡 問 題 是RFID 網絡規劃的必備問題，網絡中讀寫器的負載分布情況關乎網絡的使用壽命和穩定性，是RFID 網絡規劃的一個重要組成部分，該性能指標可如下表示

式中：ki——讀取i電子標簽的讀寫器的個數，通過均衡每個讀寫器讀取的電子標簽數量來達到RFID 讀寫器網絡負載均衡的目的，f3越大，網絡負載分配的越均衡。

為了同時滿足上述3個優化目標，采用加權和的方式，將上述多目標問題轉換成單目標問題進行求解，因此RFID網絡規劃問題的優化目標函數可表示為

其中，w1＋w2＋w3＝1，w1，w2和w3分別表示覆蓋率、網絡經濟效益和負載平衡的權重，其大小表示實際工程應用中RFID 網絡規劃部署的具體要求。

2 算法描述

2.1 算法基本思想

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

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

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

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

式中：t——當前迭代次數，T——算法總的迭代次數，wmax、wmin——慣性權重的最大和最小值。

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

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

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

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

2.2 算法設計

以式 （4）為網絡規劃的優化目標，設計算法的具體步驟如下所示：

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

（2）根據式 （4）計算種群內各粒子的適應度。

（3）找出群體內每個粒子的個體歷史最優解和種群全局最優解。

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

（5）當粒子進化停滯步數大于設定值時，轉入步驟（6），否則轉入步驟 （9）。

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

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

（8）若變異后的粒子適應值優于變異前，則用變異后的粒子取代變異前，否則轉入步驟 （6）繼續變異，直至成功。

（9）若達到算法的終止條件，則優化過程結束，輸出算法獲取的最優解，否則轉入步驟 （2）繼續尋優過程。

算法流程如圖1所示。

圖1 算法流程

3 實例仿真

3.1 仿真環境及參數設定

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

表1 仿真參數

為了驗證VDM－PSO 算法在RFID 網絡規劃部署問題求解上的應用效果，將其優化結果與PSO 算法在相同讀寫器初始分布下進行了比較，為保證比較結果的公平性，兩種算法采用相同的仿真參數。圖2為工作區域內讀寫器的初始分布，其中星形點表示電子標簽的位置，空心圓點表示讀寫器的位置，橢圓區域表示讀寫器的通信邊界。

圖2 初始讀寫器分布

3.2 仿真結果與分析

利用VDM－PSO 和PSO 兩種優化算法優化后工作區域內讀寫器的分布和適應度函數變化曲線分別如圖3 和圖4所示。

圖3 讀寫器分布對比

圖4 適應值對比

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

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

表2 10次獨立優化性能對比

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

4 結束語

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

［1］Kranzfelder Michael，Schneider Armin，Fiolka 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］.控制工程，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］.計算機應用研究，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 系統優化部署研究與應用［D］.上海：東華大學，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）. ［楊妍，陳如清，俞金壽.差分進化粒子群混合優化算法的研究與應用［J］.計算機工程與應用，2010，46 （25）：238－241.］

［13］LIU Weiting，FAN Zhouyuan.Based on chaotic particle swarm optimization of wireless sensor network coverage ［J］.Computer Applications，2011，31 （2）：338－341 （in Chinese）.［劉維亭，范洲遠.基于混沌粒子群算法的無線傳感網絡覆蓋優化 ［J］.計算機應用，2011，31 （2）：338－341.］