王 芳，程 杰，喬 木

(鄭州升達經(jīng)貿(mào)管理學院 信息工程系，河南 鄭州 451191)

基于擁擠度快速排序的物聯(lián)網(wǎng)RFID系統(tǒng)優(yōu)化設計

王 芳，程 杰，喬 木

(鄭州升達經(jīng)貿(mào)管理學院 信息工程系，河南 鄭州 451191)

大規(guī)模物聯(lián)網(wǎng)射頻識別（RFID）網(wǎng)絡規(guī)劃問題已被證明是一個NP難問題，為提高物聯(lián)網(wǎng)RFID系統(tǒng)設計的合理性，提出一種基于個體擁擠度快速排序的物聯(lián)網(wǎng)RFID系統(tǒng)設計方法。首先，將RFID網(wǎng)絡規(guī)劃問題分解為最佳標簽覆蓋、讀寫器干擾、經(jīng)濟性指標和負載均衡指標四項指標構(gòu)成的多目標優(yōu)化問題，并引入多目標人工蜂群算法（MABC）進行優(yōu)化；其次，為提高MABC算法的優(yōu)化性能，利用非支配排序方法設計了一種快速的排序方法，并利用擁擠度分析提高種群的多樣性；最后，通過實驗對比驗證了所提系統(tǒng)設計方法的有效性。

個體擁擠度；快速排序；射頻識別；物聯(lián)網(wǎng)；人工蜂群算法；多目標優(yōu)化

本文著錄格式：王芳，程杰，喬木. 基于擁擠度快速排序的物聯(lián)網(wǎng)RFID系統(tǒng)優(yōu)化設計[J]. 軟件，2017，38（1）：37-43

0 引言

射頻識別（RFID）[1~2]技術(shù)作為一種新的庫存跟蹤技術(shù)已經(jīng)取得了顯著的發(fā)展，在許多實際的工業(yè)場景，特別是在物聯(lián)網(wǎng)技術(shù)中有很大的應用潛力[3]。在許多現(xiàn)實世界的RFID應用，如生產(chǎn)、物流和供應鏈管理，越來越多的讀寫器部署在特定的區(qū)域中提供標簽的完全覆蓋。可以利用無線射頻識別技術(shù)建立的“物聯(lián)網(wǎng)”，連接到互聯(lián)網(wǎng)的物理關(guān)口，并可遠程訪問傳感器數(shù)據(jù)實現(xiàn)物理世界的控制。

然而，由于在實際應用中單一的讀寫器識別范圍有限，許多讀寫器和標簽需要進行優(yōu)化部署，以在場景區(qū)域中建立射頻識別系統(tǒng)。需要考慮的問題有[4~5]：（1）讀寫器的部署數(shù)量；（2）讀寫器的部署位置；（3）讀寫器的有效參數(shù)設置。此外，考慮到成本效益的射頻識別系統(tǒng)，網(wǎng)絡應滿足最小數(shù)量的讀寫器和最大標簽覆蓋。因此，RFID網(wǎng)絡規(guī)劃問題（RNP）是一個NP難問題[6]。

在一般情況下，定義RNP旨在通過調(diào)整混合離散和連續(xù)系統(tǒng)的控制變量，如讀寫器數(shù)量，坐標和天線參數(shù)，優(yōu)化目標包括部署成本，標簽覆蓋、負載平衡、經(jīng)濟效率和讀寫器之間干擾。在過去的二十年中，利用進化計算（EC）和群智能優(yōu)化算法（SI）求解RNP問題得到了越來越多關(guān)注，例如遺傳算法（GA）[7]、進化策略（ES）[8]、粒子群算法（PSO）[9]和人工免疫算法（AI）[10]等。最近，人工蜂群算法（ABC）[11]作為群體智能算法中的一個相對較新的成員，得到了學者的關(guān)注。由于其算法簡單、魯棒性好，ABC及其變種已用來求解RNP問題。但是這種采取單一混合目標形式的優(yōu)化策略，會出現(xiàn)指標間的吞并問題，導致部分指標無法得到優(yōu)化。

對此，本文考慮采用多目標人工蜂群算法進行RFID網(wǎng)絡規(guī)劃問題求解，獲得部署成本、標簽覆蓋、負載平衡、經(jīng)濟效率和讀寫器之間干擾多項指標的同步優(yōu)化。

1 射頻識別網(wǎng)絡規(guī)劃優(yōu)化模型

1.1 RFID系統(tǒng)構(gòu)成

一個的射頻識別系統(tǒng)由四種類型的重要部分組成，見圖1所示[12]：（1）RFID標簽，放在每個物體上，由芯片和嵌入式天線組成并包含獨特電子產(chǎn)品代碼（EPC）；（2）RFID讀寫器，每個含有一個以上的天線，并負責通過射頻波發(fā)射和接收數(shù)據(jù)；（3）RFID中間件，用于管理讀寫器，并過濾和格式化RFID原始標簽數(shù)據(jù)；（4）RFID數(shù)據(jù)庫，用于記錄RFID標簽數(shù)據(jù)中包含的信息，如閱讀時間，地點和標簽的EPC。在這一部分中，提出基于RFID中間件的RNP問題的數(shù)學優(yōu)化模型。

圖1 RFID系統(tǒng)Fig.1 RFID system

該模型包含幾個不同的方面：RFID熱點部署區(qū)域為二維正方形區(qū)域，這里的標簽是基于2代超高頻標準規(guī)范的。這意味著，他們只能從讀寫器中通過無線電頻率提供能量。該RNP模型旨在通過優(yōu)化目標，包括成本、覆蓋率、干擾、負載均衡等子指標，通過調(diào)節(jié)RFID網(wǎng)絡讀寫器的參數(shù)，包括數(shù)量，位置和輻射功率，從而提高RFID網(wǎng)絡的QoS和總效率。

1.2 RNP問題描述

本文對物聯(lián)網(wǎng)進行RFID網(wǎng)絡部署設計過程，采用如下評價指標[13]：

（1）最佳標簽覆蓋（C）：第一個目標函數(shù)是覆蓋范圍指標，其為射頻識別系統(tǒng)中最重要的指標。在本文中，如果標簽接收無線電信號高于閾值那么讀寫器和標簽之間可以建立通信。然后函數(shù)轉(zhuǎn)化為在讀寫器j的訊問區(qū)域所需的功率水平δ和標簽i實際接收功率之間的差異之和：

式中，TS和RS分別為部署在工作區(qū)域中的標簽集合讀寫器集，RSi表示在其閱讀區(qū)域中具有標記i的讀寫器集。這個目標功能是確保標簽i從RSi中的讀寫器j接收到的功率，逐漸逼近或是略高于閾值δ，可確保標簽被激活，同時能夠保持能源使用的有效性和效率。

（2）讀寫器干擾（I），發(fā)生在密集讀寫器環(huán)境中的閱讀碰撞，一般是有幾個讀寫器試圖在同一時間查詢同一區(qū)域的讀寫器。這可能會導致誤讀，而無法進行信息接受。目標函數(shù)定義形式為：

其中，TSk是在讀寫器k的查詢區(qū)域中的標簽集。對于每個標簽i，該目標考慮所有的讀寫器，除了干擾源。也就是說，通過改變讀寫器的位置和功率，該算法可調(diào)整讀寫器的位置以降低干擾。

（3）經(jīng)濟性指標（E），可從不同的角度進行定義，例如考慮到信道傳播中存在的隨機噪聲，多徑效應和衰減，讀寫器應部署在標簽熱點的中心。從這個角度來看，這個目標可以通過權(quán)衡每個標簽集的中心距離與最佳服務讀寫器的距離進行實現(xiàn)?？刹捎胟-均值聚類算法來找到標簽集群，可定義為：

其中，dist()是第k個讀寫器Ik和第個k標簽中心kθ的距離，在該目標中，算法試圖降低讀寫器與高密度標簽元素之間的距離。

（4）負載均衡指標（L），具有均勻分布的讀寫器網(wǎng)絡要比不平衡配置的網(wǎng)絡具有更優(yōu)的負載均衡成本。因此，在大型的RFID系統(tǒng)中，標簽集需要在所有讀寫器讀者之間實現(xiàn)一定的平衡。據(jù)此，目標函數(shù)可定義為：

式中，Ck是讀寫器k分配的標簽數(shù)量，為讀寫器k在單位時間內(nèi)可讀取的最大標簽數(shù)量。需要注意的是根據(jù)網(wǎng)絡中使用的讀寫器類型，需要設定不同的值。該目標是通過改變讀寫器位置和輻射功率，以降低負載均衡方差。

2 多目標人工蜂群算法

2.1 人工蜂群算法

人工蜂群（ABC）算法是一種基于蜜蜂智能覓食行為的進化算法，分為三個組成要素：被雇傭蜜蜂、偵察員以及未雇傭蜜蜂。雇傭蜜蜂搜索具體的花蜜（食品）源，并將其傳遞給跟隨蜂。每個食物源僅對應于一個雇傭蜜蜂，雇傭蜜蜂的數(shù)量等于花蜜源數(shù)量。如果雇傭蜜蜂發(fā)現(xiàn)蜜源枯竭，它將通過偵察員進行新蜜源更換。根據(jù)圖2可更好地了解蜜蜂群體覓食行為的基本行為特征。

圖2 蜜蜂采集花蜜的行為Fig.2 behavior of bees collecting nectar

在圖2中，假設有兩個食物源被發(fā)現(xiàn)：A和B。在開始的時候，一個潛在的蜜蜂作為未雇傭密封開始覓食，該蜜蜂不知道蜂巢周圍的食物源情況，這樣的蜜蜂有兩種可能選擇：

（1）它可以是一個偵察員，因為內(nèi)部動機或可能的外部線索開始搜索蜂巢周圍的食物源（圖2中的‘S’）。

（2）它可通過觀看搖擺舞，并開始尋找食物源（圖2中的‘R’）。在尋找到食物源后，蜜蜂利用其能力記住該位置，然后立即開始食物采集。此時蜜蜂會成為一個“雇傭者”。覓食蜜蜂需要在食物源上進行花蜜采集，并返回到蜂巢中在食物倉庫中進行花蜜卸載。在卸載食物后，蜜蜂有以下選項：（2-1）它可能在放棄了食物來源后，成為自由的未雇傭者（UF）。（2-2）它會跳舞然后招聘其他蜜蜂返回同一食物源（EF1）。（2-3）它可能會繼續(xù)搜尋食物源，而不招募蜜蜂（EF2）。則蜜蜂算法可構(gòu)建為：

步驟1：（初始化階段）產(chǎn)生一個隨機分布的初始食物源位置解決方案：

步驟2：（蜜蜂雇傭階段）每個受雇蜜蜂在其當前食物源xi發(fā)現(xiàn)一個新的食物來源vi，使用下列表達式計算新的食物源：

步驟3：（蜜蜂偵查階段）每個偵查員以一定概率選擇雇傭蜜蜂共享的與花蜜量相關(guān)的食物源。概率計算形式如下：

如果不能在確定周期內(nèi)實現(xiàn)食物源質(zhì)量提升，則將其從種群中移除，并重新確定為偵查蜂。偵察蜂查找新的隨機的食物源位置如下：

式中，k為蜜蜂在種群中的索引。上述步驟在預定數(shù)量周期內(nèi)被重復執(zhí)行，直到一個終止準則滿足。

2.2 非支配快速排序

對蜂群算法的初始種群使用如下非支配快速排序過程進行處理：

步驟1：對人工蜂群算法的蜜蜂種群P的蜜蜂個體p進行以下操作步驟：

1-2：對于蜜蜂種群P內(nèi)的個體q，若滿足p?q，那么可得否則q?p，并且令

1-3：若np=0，那么設定蜜蜂個體p等級為并且令蜜蜂個體p附加到蜜蜂種群的Pareto前沿內(nèi)，可表示為

步驟2：對人工蜂群算法的蜜蜂種群執(zhí)行下列步驟，直到滿足條件iF=φ：

2-1：令Q=φ，作用是對Pareto前沿iF進行臨時存放；

2-2：對于Pareto前沿iF內(nèi)蜜蜂個體p，操作如下：對Sp內(nèi)蜜蜂個體q，操作如下：令若滿足那么表示q僅被蜜蜂個體p支配，則設置蜜蜂個體q等級為并且可得

2-3：令i=i+1；

2-4：令Pareto前沿iF=Q，則同理可獲得2~n前沿集

2.3 擁擠度指標設計

在人工蜂群種群進化過程中，適應度高且同其余蜜蜂間距相對較小的個體進行保留，假定共有r組子目標形式為f1、f2…fr，蜜蜂i的在種群中的擁擠度數(shù)值為是蜜蜂i對于子目標m的對應函數(shù)取值，那么可得擁擠度指標為：

如果蜜蜂種群規(guī)模是N，那么在最壞運行狀況下，進行r組子目標的擁擠度計算復雜度為排序計算復雜度為那么可得總復雜度是

2.4 多目標人工蜂群算法步驟

步驟1：設定人工蜂群算法種群規(guī)模是N，進化終止代數(shù)為gen，蜜蜂個體取值上限為XVmax，下限為XVmin，初始化蜜蜂種群pop，進行適應值計算、排序和個體的擁擠度計算，并設定i=1；

步驟2：基于競標賽個體保留方式在種群pop內(nèi)獲得N/2數(shù)量的蜜蜂個體構(gòu)建父代蜜蜂個體parent_pop，并進行3.1節(jié)蜜蜂覓食有關(guān)操作，獲得臨時性種群pop1，規(guī)模為N/2；

步驟3：將臨時性種群pop1與原始種群pop生成混合種群intermediate_pop，進行蜜蜂的排序及相應的擁擠度值獲取，并在此基礎上選擇N個蜜蜂構(gòu)成種群pop；

步驟4：令i=i+1，若滿足i≤gen，那么重新調(diào)用步驟2；若滿足i＞gen，那么算法繼續(xù)；

步驟5：輸出pareto最優(yōu)解集pop，作為多目標人工蜂群算法的輸出結(jié)果。

3 實驗分析

3.1 多目標優(yōu)化算法性能測試

測試函數(shù)形式如下：

圖3a~圖3b分別為MOP1和MOP2函數(shù)所求解的Pareto最優(yōu)解對比情況，多目標進化算法性能評價指標主要有兩個：解的均勻性和前沿性。根據(jù)圖3所示可看出，本文算法在這兩項評價指標上均要優(yōu)于選取的對比算法，在均勻性上與SPEA和NSGAⅡ兩種算法非常接近。圖4所示為對比算法Pareto解集分布對比，可看出本文算法在上述兩項指標上也要優(yōu)于其他四種對比方法。實驗結(jié)果驗證了本文多目標人工蜂群算法有效性。

圖3 Pareto最優(yōu)解對比Fig.3 comparison of Pareto optimal solutions

圖4 最優(yōu)解分布Fig.4 optimal solution distribution

3.2 物聯(lián)網(wǎng)RFID系統(tǒng)實驗

這里使用的讀寫器是移動的，標簽是被動的。相關(guān)的射頻識別讀寫器參數(shù)設置見表1所示。查詢范圍可根據(jù)讀寫器的輻射功率進行計算，參見文獻[6]所示。RNP實例選取CD100，對所提算法的有效性進行驗證。CD100實例的工作區(qū)域大小為30m× 30m，具有100個集群分布式測試標簽。對比算法選取：（1）單目標人工蜂群算法，各指標權(quán)重均設置為0.25；（2）普通多目標人工蜂群算法（MABC）。實驗對比結(jié)果見圖5~6所示。

圖5 各指標優(yōu)化對比Fig.5 optimization and comparison of each indicator

根據(jù)圖5a~圖5d可知，最佳標簽覆蓋、讀寫器干擾、經(jīng)濟性指標和負載均衡指標四項指標的數(shù)量級并不相同，如果采用單一目標的人工蜂群算法，如果權(quán)重系數(shù)設置不合適，會造成多數(shù)指標優(yōu)化失敗的問題，如圖5a~圖5d所示，在上述四組指標中，僅有數(shù)量級較大的最佳標簽覆蓋指標得到優(yōu)化，而其他指標的優(yōu)化過程被弱化或覆蓋，無法實現(xiàn)所有指標的同步優(yōu)化。而采用多目標算法的優(yōu)化結(jié)果，雖然在最佳標簽覆蓋指標上的優(yōu)化結(jié)果不如單目標優(yōu)化結(jié)果，但是在讀寫器干擾、經(jīng)濟性指標和負載均衡指標三項指標上的優(yōu)化結(jié)果要優(yōu)于單目標優(yōu)化結(jié)果。同時可看出，本文所提方法在上述四項指標上的優(yōu)化結(jié)果均要優(yōu)于選取的普通MABC算法，體現(xiàn)了方法有效性。

采用上述三種算法的網(wǎng)絡RFID讀寫器部署對比情況見圖6所示。

圖6 RFID讀寫器部署對比情況Fig.6 compares of RFID reader-writer deployment

根據(jù)圖6a~圖6c可知，在RFID讀寫器部署效果對比情況看，本文算法所設置的讀寫器位置均適當?shù)奈挥跇撕炛車?，并且每個標簽集簇僅含有一個讀寫器，實現(xiàn)了讀寫器的相對優(yōu)化部署。普通MABC算法除個別RFID讀寫器部署出現(xiàn)問題外，整體上普通MABC算法要優(yōu)于單一目標的人工蜂群算法。

4 結(jié)束語

本論文提出一種基于個體擁擠度快速排序MABC的物聯(lián)網(wǎng)RFID系統(tǒng)設計方法，將RFID網(wǎng)絡規(guī)劃問題（RNP）分解為最佳標簽覆蓋、讀寫器干擾、經(jīng)濟性指標和負載均衡指標四項指標構(gòu)成的多目標優(yōu)化問題，并利用多目標人工蜂群算法進行優(yōu)化，同時利用非支配排序方法設計了一種多目標人工蜂群算法的快速排序方法，并利用擁擠度分析提高種群的多樣性。實驗結(jié)果驗證了所提方法的有效性。因為實驗條件所限，本文算法驗證僅通過模擬數(shù)據(jù)集實現(xiàn)，如何在實際應用中驗證算法的有效性，是今后研究的重點。

[1] Chung-Hao Huang, Lun-Hui Lee, Chian C Ho, et al. Real-Time RFID Indoor Positioning System Based on Kalman-Filter Drift Removal and Heron-Bilateration Location Estimation[J]. IEEE Transactions on Instrumentation and Measurement, 2015, 728-739.

[2] 張士庚, 劉光亮, 劉漩, 等. 大規(guī)模RFID系統(tǒng)中一種能量有效的丟失標簽快速檢測算法[J]. 計算機學報, 2014, 37(2): 434-444. Shi-Geng Zhang,Guang-Liang Liu, Xuan Liu, et al. An Energy-Efficient and Fast Missing Tag Detection Algorithm in Large Scale RFID Systems[J]. Chinese Journal of Computers, 2014, 37(2): 434-444.

[3] 李國家, 汪定偉. 分銷網(wǎng)絡多級存儲的RFID使能的Pull控制系統(tǒng)[J]. 系統(tǒng)管理學報, 2016, 25(3): 571-576. Guo-Jia Li, Ding-Wei Wang. Pull control system of RFID enable for multi-level storage in distribution network[J]. Journal of Systems & Management, 2016, 25(3): 571-576.

[4] Siddika Parlak, Ivan Marsic, Aleksandra Sarcevic, et al. Passive RFID for Object and Use Detection during Trauma Resuscitation[J]. IEEE Transactions on Mobile Computing, 2016, 15(4): 924-937.

[5] Po Yang. PRLS-INVES: A General Experimental Investigation Strategy for High Accuracy and Precision in Passive RFID Location Systems[J]. IEEE Internet of Things Journal, 2014, 2(2): 159-167.

[6] Herbj?rn Nysveen, Per Egil Pedersen. Consumer adoption of RFID-enabled services. Applying an extended UTAUT model[J]. Information Systems Frontiers, 2016, 18(2): 293-314.

[7] Tin-Yu Wu, Guan-Hsiung Liaw, Sing-Wei Huang, et al. A GA-based mobile RFID localization scheme for internet of things[J]. Personal and Ubiquitous Computing, 2012, 16(3): 245-258.

[8] Han Feng, Jie Qi. Radio frequency identification networks planning using a new hybrid evolutionary algorithm[C]//2013 15th International Conference on Advanced Communication Technology (ICACT), IEEE, PyeongChang, 2013, pp.179-188.

[9] Wen-Tsai Sung, Yen-Chun Chiang. Improved Particle Swarm Optimization Algorithm for Android Medical Care IOT using Modified Parameters[J]. Journal of Medical Systems, 2012, 36(6): 3755-3763.

[10] R J Kuo, J W Chang. Intelligent RFID positioning system through immune-based feed-forward neural network[J]. Journal of Intelligent Manufacturing, 2015, 26(4): 755-767.

[11] 周新宇, 吳志健, 王明文. 基于正交實驗設計的人工蜂群算法[J]. 軟件學報, 2015, 26(9): 2167-2190. Xin-Yu Zhou, Zhi-Jian Wu, Ming-Wen Wang. Artificial Bee Colony Algorithm Based on Orthogonal Experimental Design[J]. Journal of Software, 2015, 26(9): 2167-2190.

[12] 王雪, 錢志鴻, 劉曉慧, 等. 改進的樹型結(jié)構(gòu)RFID防碰撞算法[J]. 通信學報, 2015, 36(7): 2015161. Xue Wang, Zhi-Hong Qian, Xiao-Hui Liu, et al. Improved tree structure anti-collision algorithm of RFID[J]. Journal on Communication, 2015, 36(7): 2015161.

[13] Vishwa V Kumar, F W Liou, S N Balakrishnan, et al. Economical impact of RFID implementation in remanufacturing: a Chaos-based Interactive Artificial Bee Colony approach[J]. Journal of Intelligent Manufacturing, 2015, 26(4): 815-830.

[14] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength pareto evolutionary algorithm[R]. Zurich: Computer Engineering and Networks Laboratory(TIK), Swiss Federal Institute of Technology (ETH) Zurich, 2001.

[15] Deb K, Pratap A, Agarwal S. A fast and elitist multiobjective genetic algorithm: NSGA2[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197.

Crowding Degree Fast Sorting Based RFID System Optimal Design For Internet of Things

WANG Fang, CHENG Jie, QIAO Mu

(Department of Information Engineering, Zhengzhou Shengda College of Economics & Trade Management, Zhengzhou, 451191, China)

The mass network radio frequency identification (RFID) network planning problem has been shown to a NP hard problem, in order to improve the design of the RFID system rationality, we put forward an Individual crowding degree fast sorting MABC based RFID system design for Internet of things. Firstly, we decompose the RFID networks planning as the four indexes of multi-objective optimization problems, such an optimal tag coverage, reader interference, economic index and load balance index, and it used the multi-objective artificial bee colony algorithm (ABC) to optimize it. Secondly, in order to improve the optimization performance of ABC algorithm, a fast sorting method is designed by using non dominated sorting method, and the diversity of population is improved by using the analysis of crowding degree; Finally, the effectiveness of the proposed system design method is verified by experiments.

Individual congestion degree; Fast sorting; Radio frequency identification; Internet of things; Artificial bee colony algorithm; Multi objective optimization

TP18

A

10.3969/j.issn.1003-6970.2017.01.009

2015年度河南省重點科技攻關(guān)項目基金(152102210176)

王芳(1973-)，女，河南鄭州人，碩士，副教授，主要研究方向：網(wǎng)絡優(yōu)化、物聯(lián)網(wǎng)、真實感繪制。