面向柔性制造車間的多目標RFID網絡規劃方法

摘 要： "針對具有多種覆蓋需求的柔性制造車間RFID網絡規劃問題，以部署成本、閱讀器干擾與閱讀器效能為多優化目標，提出一種分層聚類、冗余消減與梯度下降方法集成的RFID網絡規劃方法，采用分層聚類算法確定RFID初始數量與部署位置，采用冗余閱讀器消減算法優化RFID數量，采用梯度下降算法優化RFID部署位置從而實現網絡規劃多目標優化。實驗研究表明，提出的方法在多目標綜合性能方面優于傳統基于分層聚類方法、遺傳算法、粒子群與冗余消減混合方法的RFID網絡規劃方法，驗證了該方法的有效性。

關鍵詞： "柔性制造車間； RFID； 網絡規劃； 多目標

中圖分類號： "TP301 """文獻標志碼： A

文章編號： "1001-3695（2022）02-012-0398-04

doi：10.19734/j.issn.1001-3695.2021.06.0300

Multi-objective RFID network planning approach for "flexible manufacturing workshop

Wu Lihui1， Li Yuansheng2， Hu Wenbo2， Dai Zhengzheng2， Meng Ya2， Zhang Zhongwei2

（1.School of Mechanical Engineering， Shanghai Institute of Technology， Shanghai 201418， China； 2.School of Electromechanical Enginee-ring， Henan University of Technology， Zhengzhou 450001， China）

Abstract： "To solve the RFID network planning problem of flexible manufacturing workshops with multiple coverage requirements，this paper proposed an RFID network planning approach integrating hierarchical clustering，redundancy reduction，and gradient descent，where the deployment cost，reader interference，and reader efficiency were taken as multi-optimization objectives.Firstly，it designed a hierarchical clustering algorithm to determine the initial number and deployment location of RFID.Then，it constructed a redundancy reader reduction algorithm to optimize the number of RFID.Finally，it built a gradient descent algorithm to adjust the RFID deployment location，so as to achieve multi-objective optimization of the RFID network planning.Experimental results show that the proposed approach has better multi-objective comprehensive performance than the traditional RFID network planning methods，including the hierarchical clustering method，genetic algorithm，particle swarm optimization，and redundancy subtraction method.It means the proposed approach is effective.

Key words： "flexible manufacturing workshop； RFID； network planning； multi-objective

0 引言

隨著我國制造強國戰略的實施，廣大制造企業逐漸向數字化、網絡化、智能化方向轉型，柔性制造車間作為智能制造實施的重要單元，被國內外企業與學者廣泛關注［1］。物料信息感知與采集是柔性制造車間智能運行與決策的基礎，無線射頻識別技術（radio frequency identification，RFID）因具有非接觸、非視距、多標簽并行感知等優點成為車間中信息采集的重要手段。然而在柔性制造車間中，在制品、加工機床、檢測設備等均為金屬材質，容易導致RFID信號大量反射及交叉干擾，如何優化RFID網絡規劃（RFID network planning，RNP）以提高其信息采集質量成為國內外研究的焦點。

RNP是指對系統中的RFID閱讀器節點位置進行規劃布局，以期獲得優化的RFID數量與位置。唐琳等人［2］建立多目標非線性整數規劃模型以優化汽車混流裝配線RFID網絡規劃；唐向紅等人［3］通過構建基于網格的覆蓋模型并提出一種配置算法實現RFID優化布局；Jaballah等人［4］提出一種約束滿足模型用于RFID網絡規劃，實驗結果表明該方法具有較好的綜合性能；吳瓊等人［5］提出一種速度差分變異粒子群算法實現RFID網絡優化布局；全藝璇等人［6］提出一種改進型灰狼算法以提高RFID網絡規劃多目標性能；Cao等人［7］提出一種混合粒子群算法以降低系統中RFID數量及各讀寫器之間的干擾；Zahran等人［8］提出一種混合生物地理學算法實現RFID網絡規劃的多目標優化；Xu等人［9］提出一種魯棒粒子群算法用于物流網絡環境下的RFID網絡優化布局。由文獻分析可知，現有研究主要集中在基于數學模型求解和元啟發式方法改進兩方面，較少關注柔性制造車間本身的特點及需求。實際生產中，柔性制造車間存在多個障礙區（如加工設備、檢測設備區域等），區內無須RFID信號覆蓋，且易導致RFID信號反射；車間內圍繞物料跟蹤和在制品定位存在目標點覆蓋、區域覆蓋、柵欄覆蓋等多種覆蓋需求。本文研究面向柔性制造車間的RNP問題，以部署成本、閱讀器干擾和閱讀器效能為目標，設計適用于柔性制造車間的多階段RFID網絡規劃方法，以實現車間內RFID網絡優化配置，提高信息采集的質量。

1 柔性制造車間規劃空間建模

柔性制造車間環境下進行RNP首先需要對布局空間進行建模，主要有空間連續化處理和離散化處理兩種模式。離散化處理模式將布局空間離散化為有限數量的方形網格單元，從而使各網格單元是否被覆蓋問題轉換為0-1整數規劃問題，具有縮小問題規模、降低RNP難度等優點［10］。本文采用離散化處理模式對柔性制造車間進行建模處理。

設定某柔性制造車間目標區域長、寬分別為 x和y ，將該區域沿長和寬的方向進行方形網格劃分，設定網格單元邊長為 l ，則該柔性制造車間長與寬方向網格單元數量分別為 x/l和y/l ，總的網格單元數量為（ x×y）/l 2。設定柔性制造車間中無覆蓋需求的障礙區采用黑色網格表示，有覆蓋需求區采用白色網格表示，無RFID信號反射干擾但亦無覆蓋需求的區域采用灰色網格表示，則該車間離散化建模處理如圖1所示。

2 RFID網絡規劃模型

為對柔性制造車間進行RNP，首先建立RFID閱讀器輻射模型，在此基礎上以RNP研究中廣泛采用的部署成本、閱讀器干擾和閱讀器效能［11］為優化目標建立相應的RNP模型。

2.1 RFID閱讀器輻射模型

RFID天線輻射范圍是其閱讀器的關鍵參數之一。全向天線閱讀器因其具有圓形輻射信號能力，在生產制造中被廣泛采用，其輻射模型如圖2所示。定義 d 表示電子標簽與閱讀器節點間的歐氏距離； r 表示閱讀器圓形輻射半徑。當 d≤r 時，標簽可以被閱讀器感知，否則標簽不可以被閱讀器感知。則RFID閱讀器天線輻射模型如式（1）所示，式中“1”表示電子標簽被感知，“0”為未被感知。

Per （d）= 1 d≤r

0 d＞r """"（1）

2.2 網絡規劃多目標模型

在柔性制造車間中，由于物料跟蹤和在制品定位存在目標點覆蓋、區域覆蓋、柵欄覆蓋等多種覆蓋需求，各種覆蓋需求的離散不均勻分布特點容易導致RFID閱讀器之間干擾，影響物料跟蹤和在制品定位準確性，且容易導致RFID部署成本增加。此外，柔性制造車間中加工、檢測等金屬設備容易導致RFID信號反射干擾，該反射干擾受閱讀器天線節點輻射半徑影響，而輻射半徑可根據各閱讀器與其覆蓋區域內的電子標簽之間的距離進行調節。因此，柔性制造車間的RFID網絡規劃采用閱讀器部署成本、閱讀器干擾和閱讀器效能為優化目標。

定義 M 為柔性制造車間中可放置閱讀器的網格點集合， m i 為集合中網格點 i 的狀態變量， m i ∈{0，1}， i =1，2，…，| M |，當網格點 i 上被放置閱讀器，則 m i =1； c i 為網格點上配置閱讀器的成本； P 為柔性制造車間中有目標點覆蓋、區域覆蓋、柵欄覆蓋的單元格集合， p j 為該集合中單元格 j 的狀態變量， p j ∈{0，1}， j =1，2，…，| P |，當單元格 j 被閱讀器信號覆蓋，則 p j=1；v ij 為單元格 j 被網格點 i 上閱讀器信號覆蓋的狀態變量， v ij ∈{0，1}，如果被覆蓋，則 v ij =1； S 為柔性制造車間中的電子標簽集合， s ik 為電子標簽 k 被網格點上閱讀器信號覆蓋的狀態變量， s ik ∈{0，1}， k =1，2，…，| S |，如果電子標簽 k 被覆蓋，則 s ik =1。建立多目標RFID網絡規劃數學模型如下：

a）部署成本。RNP部署成本即柔性制造車間中配置RFID的總成本，其主要取決于部署的閱讀器數量及各閱讀器配置成本，定義部署成本 N req ，其數學描述為

N req=∑ |M| i=1 c i·m i ""（2）

b）閱讀器干擾。柔性制造車間規劃空間中，當某一單元格被兩個及以上閱讀器同時覆蓋時，則存在閱讀器干擾。 閱讀器干擾發生在閱讀器密集部署區域，容易導致該區域中電子標簽無法被閱讀器正確識別。定義閱讀器干擾為 N int ，則其數學描述為

N int=∑ |P| j=1 （

∑ |M| i=1 v ijm i-p j ） "（3）

c）閱讀器效能。RFID工作過程中，減小各閱讀器與其覆蓋區域內的電子標簽之間的距離，可使各閱讀器以更小功率工作，減少閱讀器天線節點輻射半徑，從而減少柔性制造車間內RFID信號反射干擾，且可提高閱讀器讀取覆蓋區域內的電子標簽信息的可靠性。將各閱讀器與其覆蓋區域內的電子標簽之間的距離采用閱讀器效能指標描述。定義電子標簽 k 與網格點 i 上閱讀器的歐氏距離為 d ik ，則閱讀器效能數學描述為

E=∑ |M| i=1 ∑ |S| k=1 m i·s ik·d ik ""（4）

d）多目標模型。在滿足柔性制造車間覆蓋需求的前提下，建立RNP多目標0-1整數規劃模型為

min= """f 1=N req

f 2=N int

f 3=E """（5）

約束條件為 """p j＞0， εj ""（6）

式（5）中： f 1、f 2、f "3分別為RFID部署成本、閱讀器干擾與閱讀器效能目標模型；式（6）表示柔性制造車間的覆蓋需求必須被RFID閱讀器信號覆蓋。

3 RFID網絡規劃模型

由面向柔性制造車間的RNP模型可知，該RNP問題是典型的多目標優化問題，為快速有效求解該問題，設計一種分層聚類、冗余消減與梯度下降方法集成（integration of hierarchical clustering，redundant reader elimination，and gradient descent，IHCRREGD）的網絡規劃方法，流程如圖3所示。首先采用層次聚類算法［12］確定RFID讀寫器的初始數量與位置，在滿足多覆蓋需求前提下實現RFID讀寫器部署成本優化；其次，設計冗余閱讀器消減算法進一步優化RFID讀寫器數量；再次，采用梯度下降法［13］調整RFID閱讀器在柔性制造車間規劃空間中的位置，以降低RFID閱讀器干擾，并提高其閱讀器效能。

3.1 分層聚類算法

分層聚類是一種典型的無指導學習聚類算法，聚類原理是通過計算數據點之間相似度來創建樹狀圖層次結構，因其無須提前指定聚類個數而被廣泛應用。針對柔性制造車間RNP的層次聚類方法具體設計步驟如下：

a）獲取柔性制造車間中所有具有覆蓋需求的單元格集合 P ，并將每個單元格的中心點作為該單元格的數據點。

b）將每個數據點視為單獨的簇，合并歐氏距離最近的兩個數據點成為新的一簇。設定單元格 p m和p n 的數據點坐標為（ x m，y m）和（x n，y n ），則其歐氏距離計算公式為

D（p m，p n）= （x2 m-x2 n）+（y2 m-y2 n） """（7）

c）繼續合并歐氏距離最近的兩個簇成為新簇，簇與簇之間距離通過complete-linkage算法［14］來確定。

d）重復c），直到所有簇劃入同一簇，最后形成分層嵌套簇樹。

e）沿分層嵌套簇樹頂部到底部挑選出直徑接近RFID閱讀器輻射直徑的簇，使集合 P 中所有單元格均被所挑選的簇所覆蓋，則所選簇的數量即為RFID閱讀器的優化數量，各簇的中心坐標即為RFID閱讀器的初始位置。

以某柔性制造車間的八個離散網格單元作為基礎數據點，分層聚類方法具體實施過程如圖4所示。

3.2 冗余閱讀器消減算法

冗余閱讀器消減算法的主要目的是在保證閱讀器覆蓋需求的基礎上消除冗余閱讀器，降低閱讀器部署成本和閱讀器干擾。該方法設計思路如下：a）計算所有閱讀器之間的距離值，當某兩個閱讀器間距離值小于閱讀器直徑時，嘗試將該兩閱讀器進行融合；b）如果該兩閱讀器所覆蓋數據點能被一個新的閱讀器完整覆蓋時，則該兩閱讀器即被新的閱讀器替代，實現該兩閱讀器的融合。以上過程不斷循環，直到所有滿足條件的冗余閱讀器被融合處理。該方法的具體流程如圖5所示。

3.3 梯度下降算法

梯度下降算法是一種基于搜索的優化方法，其具有快速收斂的優點。以閱讀器干擾和閱讀器效能優化為目標，設計針對柔性制造車間RNP的梯度下降算法具體步驟如下：

a）基于分層聚類算法獲取 q 個RFID閱讀器的初始位置集合 M 0，C 0={c 10，c 20，…，c q0}。

b）求解目標函數 f "2的梯度，其計算公式如式（8）所示。

f 2（C）=" "f 2（C） c 1 ，

f 2（C） c 2 ，…，" f 2（C） c q """"（8）

c）基于目標函數 f "2的梯度值計算 q 個RFID閱讀器的更新位置集合 C "1，其計算公式如式（9）所示。

C 1=C 0-α f 2（C） ""（9）

d）置 C 0=C 1 ，判斷各數據點是否超出所屬簇的范圍。如未超出，則返回步驟b）；否則，流程結束，所獲得的RFID閱讀器更新位置 C "1即為優化位置，所獲得的函數值 f "2即為考慮閱讀器干擾和閱讀器效能的優化目標值。

4 實驗研究

4.1 實驗設計

采用河南某柔性制造車間數據，對本文提出的IHCRREGD方法進行驗證。該車間為精密刀具加工車間，大小為28 m×25 m，車間內共有數控機床及加工中心10臺、檢測設備兩臺、毛坯及成品庫一個，各加工設備設置有上、下料區，檢測設備設置有暫存區，設備之間物料搬運采用自動化物料運輸小車進行搬運，車間具體布置如圖6所示。考慮該柔性制造車間的目標點覆蓋、區域覆蓋、柵欄覆蓋需求，對其進行規劃空間建模如圖7所示。

將本文提出的IHCRREGD方法與分層聚類方法（hierarchical clustering，HC）［15］、遺傳算法（genetic algorithm，GA）［16］、粒子群與冗余消減混合方法（particle swarm optimization and redundant reader elimination-based approach，PSO-RRE）［17］進行比較，對比實驗考慮閱讀器覆蓋半徑 r 的影響，共考慮12種情況，分別為 r = 2 ，2， 5 ，2 2 ，3， 10 ， 13 ，4， 17 ，3 2 ，2 5 ，5。對比的性能指標為RFID閱讀器部署成本、閱讀器干擾和閱讀器效能。各方法采用MATLAB編程實現，計算機平臺配置為Windows 10操作系統、CPU i9-9900K、16 GB內存。

4.2 實驗分析

各方法的實驗結果如表1所示。從表1中可知：a）隨著閱讀器半徑逐漸增大，閱讀器部署成本逐漸降低，閱讀器干擾和閱讀器效能指標逐漸升高；b）在閱讀器部署成本性能方面，IHCRREGD、HC、GA、PSO-REE方法在各實驗場景下的目標函數均值分別為33、35、36、34，與HC、GA、PSO-REE方法相比較，IHCRREGD方法的平均性能指標分別提高了6.1%、9.1%、3.0%；c）在閱讀器干擾性能方面，IHCRREGD、HC、GA、PSO-REE方法在各實驗場景下的目標函數均值分別為36.60、42.31、52.52和44.53，IHCRREGD方法相對于HC、GA、PSO-REE方法的平均性能指標分別改善了15.6%、43.5%、21.7%； d）在閱讀器效能指標方面，IHCRREGD、HC、GA、PSO-REE方法在各實驗場景下的目標函數均值分別為180.8、180.2、248.3、239.8，IHCRREGD方法相對于HC、GA、PSO-REE方法的平均性能指標分別提高了-0.3%、37.3%、32.6%。

在此基礎上，采用綜合期望函數指標D［18］和方差分析方法對各方法進行對比分析，結果如表2所示。從表2可知，IHCRREGD與HC、GA、PSO-REE方法的 F 統計值分別為4.8、180.5、111.1，表明本文提出的IHCRREGD方法與HC、GA、PSO-REE方法的綜合期望函數值有顯著差異（顯著差異水平 P lt;0.05）。

此外，對IHCRREGD、HC、GA、PSO-REE方法在各場景下的平均運行時間進行分析比較，結果如表3所示。表3表明了IHCRREGD、HC、GA、PSO-REE方法的平均計算時間為1.3 s、1.1 s、37.1 s、1.2 s，IHCRREGD方法的平均運行時間并未明顯高于HC和PSO-REE方法。

上述實驗分析結果表明：a）與HC、GA、PSO-REE方法相比，本文提出的IHCRREGD方法在閱讀器部署成本和閱讀器干擾指標方面明顯具有更好的單項性能；b）IHCRREGD方法在閱讀器效能指標方面明顯優于GA、PSO-REE方法，略遜于HC方法；c）IHCRREGD方法在多目標綜合性能方面優于HC、GA、PSO-REE方法；d）與HC、GA、PSO-REE方法相比，IHCRREGD方法計算時間并未顯著增加。以上分析表明IHCRREGD方法是有效的。

5 結束語

針對具有多種覆蓋需求的柔性制造車間RNP問題，以閱讀器部署成本、閱讀器干擾和閱讀器效能為目標， 建立了相應RNP模型，提出了一種IHCRREGD網絡規劃方法。基于某柔性制造車間數據進行案例分析并與傳統HC、GA、PSO-REE方法進行比較，實驗結果表明IHCRREGD方法在閱讀器部署成本、閱讀器干擾和閱讀器效能性能指標方面具有更優的綜合性能，且平均運行時間未明顯高于上述傳統方法，驗證了本文提出方法的有效性。定向閱讀器具有閱讀可靠性高、沖突率低等優點，如何基于定向和全向閱讀器對多種覆蓋需求下的柔性制造車間進行混合網絡規劃以提高其多目標性能是進一步研究的方向。

參考文獻：

［1］ "Yadav A，Jayswal S C.Modelling of flexible manufacturing system：a review［J］. International Journal of Production Research ，2018， 56 （7）：2464-2487.

［2］ 唐琳，鄭力，曹暉，等.面向混流裝配線的無線射頻識別網絡規劃［J］.計算機集成制造系統，2014， 20 （1）：37-44. （Tang Lin，Zheng Li，Cao Hui， et al .RFID network planning for mixed model assembly line［J］. Computer Integrated Manufacturing Systems ，2014， 20 （1）：37-44.）

［3］ 唐向紅，吳新淼，李少波.基于網格與覆蓋模型的RFID閱讀器部署算法研究［J］.計算機應用研究，2015， 32 （10）：2967-2969，2972. （Tang Xianghong，Wu Xinmiao，Li Shaobo.Research on deployment algorithm of RFID readers based on grid and coverage model［J］. Application Research of Computers ，2015， 32 （10）：2967-2969，2972.）

［4］ Jaballah A，Meddeb A.A new algorithm based CSP framework for RFID network planning［J］. Journal of Ambient Intelligence and Humanized Computing ，2021， 12 （2）：2905-2914.

［5］ 吳瓊，紀志成，吳定會.基于速度差分變異粒子群的RFID網絡優化［J］.計算機工程與設計，2015， 36 （2）：325-329. （Wu Qiong，Ji Zhicheng，Wu Dinghui.Optimization of RFID networks based on velocity differential mutation-particle swarm algorithm［J］. Computer Engineering and Design ，2015， 36 （2）：325-329.）

［6］ "全藝璇，鄭嘉利，羅文聰，等.基于改進型灰狼算法的RFID網絡規劃［J］.計算機科學，2021， 48 （1）：253-257. （Quan Yixuan，Zheng Jiali，Luo Wencong， et al .improved grey wolf optimizer for RFID network planning［J］. Computer Science ，2021， 48 （1）：253-257.）

［7］ Cao Yating，Liu Jing，Xu Zhouwu.A hybrid particle swarm optimization algorithm for RFID network planning［J］. Soft Computing ，2021， 25 （4）：5747-5761.

［8］ Zahran E G，Arafa A A，Saleh H I， et al. "A self learned invasive weed-mixed biogeography based optimization algorithm for RFID network planning［J］. Wireless Networks ，2020， 26 （3）：4109-4127.

［9］ Xu Bowei，Li Junjun，Yang Yongsheng， et al .Robust modeling and planning of radio-frequency identification network in logistics under uncertainties［J］. International Journal of Distributed Sensor Networks ，2018， 14 （4）：DOI：10.1177/1550147718769781.

［10］ Campioni F，Choudhury S，AI-Turjman F.Scheduling RFID networks in the IoT and smart health era［J］. Journal of Ambient Intelligence and Humanized Computing ，2019， 10 （10）：4043-4057.

［11］ Jaballah A，Meddeb A.A new variant of cuckoo search algorithm with self-adaptive parameters to solve complex RFID network planning problem［J］. Wireless Networks ，2019， 25 （4）：1585-1604.

［12］ Cai Qing，Liu Jiming.Hierarchical clustering of bi-partite networks based on multi-objective optimization［J］. IEEE Trans on Network Science amp; Engineering ，2018， 7 （1）：421-434.

［13］ Kamsing P，Torteeka P，Yooyen S.An enhanced learning algorithm with a particle filter-based gradient descent optimizer method［J］. Neural Computing amp; Applications ，2020， 32 （8）：12789-12800.

［14］ "Sharbati R，Mostafaei S，Khoshnoudian F， et al. Cluster analysis of near-fault ground motions based on the intensity of velocity pulses［J］. Journal of Engineering Mechanics ，2020， 146 （10）：40201171.

［15］ Cai Qing，Liu Jiming.Hierarchical clustering of bipartite networks based on multi-objective optimization［J］. IEEE Trans on Network Science and Engineering ，2020， 7 （1）：421-434.

［16］ Guan Qiang，Liu Yu，Yang Yiping， et al .Genetic approach for network planning in the RFID systems［C］//Proc of the 6th Internatio-nal Conference on Intelligent Systems Design and Applications.Washington DC：IEEE Computer Society，2006：567-572.

［17］ Lyu Shilei，Yu Shunzheng.A novel middleware-based approach for redundant reader elimination using PSO［J］. International Journal of Security and Networks ，2012， 7 （4）：220-227.

［18］ Wu Lihui，Mok P Y，Zhang Jie.An adaptive multi-parameter based dispatching strategy for single-loop interbay material handling systems［J］. Computers in Industry ，2011， 62 （2）：175-186.