馮諾依曼人工蜂群算法求解RFID網絡優化問題

摘 要：本文提出了一種具有馮諾依曼社會結構的新型人工蜂群算法（VNABC）。本文采用四個測試函數驗證VNABC算法性能，并將其應用于求解射頻識別系統中的讀寫器網絡覆蓋和防沖突問題。試驗結果表明，與基本人工蜂群算法和粒子群優化算法比較，VNABC算法求解復雜優化問題收斂速度較快、求解精度更高，從而為應用智能方法求解RFID系統優化問題提供了有效的可行方案。

關鍵詞：人工蜂群算法；馮諾依曼結構；群體智能；RFID網絡優化

中圖分類號：TP18 文獻標識碼：A

1 引言（Introduction）

射頻識別技術（Radio Frequency Identification， RFID）是對物理世界的信息進行感知和采集的物聯網支撐技術，被列為本世紀十大重要技術之一[1]。在大規模RFID應用中，在工作區域內部署多個RFID讀寫器，構成密集讀寫器網絡。網絡中每個RFID讀寫器分別對其識讀區域內的電子標簽進行讀寫，并將采集到的標簽數據發送到中央控制系統進行處理。由于密集讀寫器網絡要對物理環境中海量標簽進行全方位覆蓋（防止漏讀），某些讀寫器不可避免地會發生識讀區域的相互重疊情況[2]。

人工蜂群算法（Artificial Bee Colony，ABC）是近幾年來最流行的一種基于蜜蜂覓食行為的智能優化算法，由土耳其Erciyes大學的Karabog教授于2005年第一次提出[3]。ABC算法自提出以來，就以概念簡單、控制參數少、算法容易實現、優化效果良好等優點吸引了大批學者進行研究，并逐漸進入到了各個應用領域[4]。但是，基本ABC算法是典型的高度連接網絡結構，其快速收斂的代價則是容易陷入局部最優值，這主要是因為高度連接的網絡中的個體對搜索空間的覆蓋程度不如較少連接的網絡結構。

本文將馮諾依曼結構[5]引入ABC中，提出一種具有馮諾依曼信息交流拓撲結構的新型人工蜂群算法（Von Neumann Artificial Bee Colony Algorithm，VNABC）。仿真實驗首先采用四個測試函數驗證VNABC算法性能，然后應用VNABC對具有10個讀寫器的RFID網絡實例系統優化問題進行求解。RFID系統優化包括兩個目標，即最大化標簽覆蓋率和最小化網絡中的讀寫器沖突。仿真結果表明，與基本ABC算法與粒子群優化（Particle Swarm Optimization，PSO）算法相比，本文提出的VNABC算法能夠更加有效地求解RFID系統優化問題。

2 馮諾依曼人工蜂群算法（Von Neumann artificial

bee colony algorithm）

驅動群體智能算法工作的本質是社會交流。種群里的個體根據自己通過社會交流得到的知識相互學習以向更好的位置移動。為此，本文將馮諾依曼信息交流拓撲結構引入最近提出的人工蜂群優化算法中，旨在解決其在求解復雜優化問題時的早熟收斂問題。

2.1 VNABC算法模型

在ABC算法中主要包括三種元素：食物源、雇傭蜂（employed bees）和非雇傭蜂（unemployed bees）；其中的非雇傭蜂又包括了：觀察蜂（onlooker bees）和偵查蜂（scouts）。基本ABC算法中在新解產生時，是以原解為基礎隨機向任一其他解的任一維度進行學習，這是隨機式的信息學習策略。在VNABC算法中，群體已經有特殊拓撲結構，因此在這里采用的精英學習策略，即每個個體向馮諾依曼社會結構構建的本身鄰域內最優個體進行學習，而不再是隨機挑選其他個體。VNABC算法的具體步驟如下：

在VNABC算法的初始階段：產生隨機分布的SN個解，即食物源位置。每個解是一個D維的向量，D是待優化參數的個數。然后對解進行評估，得到其適應度值fit。

在雇傭蜂階段：每個雇傭蜂根據公式（1）在當前食物源位置的周圍找到一個新的位置，即產生一個新的解。

（1）

這里，（1，2，...，SN）和（1，2，...，D） 是隨機選擇的索引，并且，是在[-1，1]之間產生的一個隨機數。然后比較新產生解的值和原解的值，根據貪婪算法選擇好的一個作為其對應的食物源位置。

在觀察蜂階段：每個觀察蜂根據臨域內雇傭蜂分享的食物源適應度值的信息，以一定概率選擇一個食物源。表1給出了VNABC算法中馮諾依曼社會結構的構建策略。

表1 馮諾依曼形拓撲結構構造方法

Tab.1 Von Neumann shaped topology construction method

選擇概率以公式（2）進行計算：

（2）

在偵查蜂階段：如果一個食物源的適應值經過limit次循環之后沒有得到改善，則該食物源位置將被移除。與該食物源對應的雇傭蜂變成偵查蜂。偵查蜂根據公式（3）隨機產生一個新的食物源位置：

（3）

這里和是參數的上、下邊界。

以上步驟將被重復MCN次或者直到某個終止條件達到滿足。

2.2 函數測試

為了測試VNABC算法的性能，選擇了常用的一組標準測試函數，分別是Sphere、Rosenbrock、Rastrigrin和Griewank。并將算法與基本ABC、PSO進行了比較。測試函數表達式如下所示：

Sphere函數是單峰函數，很容易求解。該函數在解（0，0，…，0）處取得全局最優值0。函數的初始范圍為[-5.12，5.12]。Sphere函數表達式：

（4）

Rosenbrock函數是多峰函數，在解（1，1，…，1）處取得全局最優值0。函數的初始范圍為[-15，15]。該函數在全局最優點附近有一個狹窄的波谷，因此優化方法很難收斂到全局最優點。Rosenbrock函數表達式：endprint

（5）

Rastrigin函數是一個復雜的多峰函數，很難求解。該函數在解（0，0，…，0）處取得全局最優值0。函數的初始范圍為[-15，15]。該函數存在大量局部最優點，因此優化算法極容易選入其中而未能求得全局最優值。Rastrigin函數表達式：

（6）

Griewank在解（0，0，…，0）處取得全局最優值0。函數的初始范圍為[-600， 600]。該函數有一個乘積項，使得變量之間相互依賴，因此該函數很難求解到全局最優點。Griewank函數也是多峰函數，表達式：

（7）

在本實驗中，所有測試函數均設為30維。種群大小均為100。PSO慣性權重從0.9隨著迭代次數的增加線性下降到0.7，學習因子c1和c2均為2.0。實驗結果包括算法獨立運行30次后函數的平均值，數據如表2所示。

表2 測試函數實驗結果

Tab.2 The experimental results of test function

由實驗結果可以看出，VNABC算法在復雜多峰函數Rosenbrock、Rastrigin和Griewank函數上要明顯優于其他算法，而PSO算法在單峰函數Sphere上表現出了較高的性能。ABC算法在四個算法中表現相對較差。

3 RFID網絡優化問題（RFID network optimization）

本文考慮RFID網絡標簽覆蓋率和讀寫器防沖突建立RFID系統優化的目標函數，表示為：

（1）標簽覆蓋率

（8）

其中，NT表示RFID網絡工作區域中的標簽數量，表示第i個標簽接收到的讀寫器信號強度，Pd表示保證標簽和讀寫器能夠建立有效連接的最小場強閾值。該目標函數能夠將讀寫器定位在標簽密集的區域，并通過調整讀寫器發射功率來最大化工作區域中的RFID標簽覆蓋率。

（2）讀寫器防沖突

（9）

在該模型中用實數編碼的形式直接解決防沖突的問題。其中M表示工作區域中的讀寫器數量，函數dist（）表示兩兩讀寫器間的距離計算，Ri和Rj分別表示讀寫器i和j的實際位置，ri和rj則表示這兩個讀寫器的識讀范圍。該目標函數通過調整讀寫器的實際位置，即使兩兩讀寫器間的實際距離大于等于其識讀距離之和，盡量使讀寫器的識讀區域不發生重疊，從而達到防沖突的目的。

總目標函數為標簽覆蓋率和讀寫器防沖突的加權函數。

（10）

4 基于VNABC的RIFD網絡優化（RIFD network

optimization based on VNABC）

在仿真試驗中，讀寫器工作區域為30m×30m的正方形，其中隨機分布著100個RFID標簽。由十個讀寫器組成的RFID網絡對該工作區域中的標簽進行數據采集。

實驗一，只考慮工作環境中RFID標簽覆蓋率的優化結果。從仿真結果圖中可以觀察到，VNABC算法通過調整讀寫器空間位置和發射功率來獲得合適的標簽覆蓋率，有效地將讀寫器定位在標簽密集的區域，發現的最終解也要好于ABC和PSO算法。

實驗二，只考慮降低網絡中RFID讀寫器信號干擾的優化結果。同樣，VNABC以較快的收斂速度發現較好的最終解。從仿真結果中可以觀察到，VNABC算法通過調整讀寫器空間位置和發射功率來盡量使讀寫器間的信號覆蓋區域不發生重疊。

實驗三，綜合考慮兩種因素的RFID網絡優化。結果顯示VNABC算法取得的結果仍然好于其他兩種方法。

5 結論（Conclusion）

本文的研究包括兩個個方面：第一，提出了一種基于馮諾依曼社會結構的新型人工蜂群優化算法—VNABC。該算法具有更強的穩定性和整體優化性，在標準測試函數上的性能驗證表明，所提出算法在收斂速度、跳出局部最優等性能方面均優于基本ABC算法和PSO算法，具有良好的工程應用前景。第二，將VNABC應用于求解RFID網絡標簽覆蓋和防沖突優化問題，并給出了具體實例的仿真分析，從而進一步驗證本文提出的模型和算法的有效性。

參考文獻（References）

[1] 劉化君.物聯網關鍵技術研究[J].計算機時代，2010（07）：4-6.

[2] 張光山，張爍，張有光.基于隨機時隙的RFID讀寫器防沖突方

法[J].北京航空航天大學學報，2013（6）：782-786.

[3] Karaboga D，Basturk B.On the performance of artificial beecolony

（ABC） algorithm[J].Applied Soft Computing，2008：687-689.

[4] 程曉雅.人工蜂群算法理論及其在通信中的應用研究[D].山

東大學，2012.

[5] A.P.Engelbrecht.Fundamentals of Computational Swarm

Intelligence.Wiley Publishing，Inc.2009.

作者簡介：

蘇紅麗（1979-），女，碩士，講師.研究領域：計算機網絡.endprint

（5）

Rastrigin函數是一個復雜的多峰函數，很難求解。該函數在解（0，0，…，0）處取得全局最優值0。函數的初始范圍為[-15，15]。該函數存在大量局部最優點，因此優化算法極容易選入其中而未能求得全局最優值。Rastrigin函數表達式：

（6）

Griewank在解（0，0，…，0）處取得全局最優值0。函數的初始范圍為[-600， 600]。該函數有一個乘積項，使得變量之間相互依賴，因此該函數很難求解到全局最優點。Griewank函數也是多峰函數，表達式：

（7）

在本實驗中，所有測試函數均設為30維。種群大小均為100。PSO慣性權重從0.9隨著迭代次數的增加線性下降到0.7，學習因子c1和c2均為2.0。實驗結果包括算法獨立運行30次后函數的平均值，數據如表2所示。

表2 測試函數實驗結果

Tab.2 The experimental results of test function

由實驗結果可以看出，VNABC算法在復雜多峰函數Rosenbrock、Rastrigin和Griewank函數上要明顯優于其他算法，而PSO算法在單峰函數Sphere上表現出了較高的性能。ABC算法在四個算法中表現相對較差。

3 RFID網絡優化問題（RFID network optimization）

本文考慮RFID網絡標簽覆蓋率和讀寫器防沖突建立RFID系統優化的目標函數，表示為：

（1）標簽覆蓋率

（8）

其中，NT表示RFID網絡工作區域中的標簽數量，表示第i個標簽接收到的讀寫器信號強度，Pd表示保證標簽和讀寫器能夠建立有效連接的最小場強閾值。該目標函數能夠將讀寫器定位在標簽密集的區域，并通過調整讀寫器發射功率來最大化工作區域中的RFID標簽覆蓋率。

（2）讀寫器防沖突

（9）

在該模型中用實數編碼的形式直接解決防沖突的問題。其中M表示工作區域中的讀寫器數量，函數dist（）表示兩兩讀寫器間的距離計算，Ri和Rj分別表示讀寫器i和j的實際位置，ri和rj則表示這兩個讀寫器的識讀范圍。該目標函數通過調整讀寫器的實際位置，即使兩兩讀寫器間的實際距離大于等于其識讀距離之和，盡量使讀寫器的識讀區域不發生重疊，從而達到防沖突的目的。

總目標函數為標簽覆蓋率和讀寫器防沖突的加權函數。

（10）

4 基于VNABC的RIFD網絡優化（RIFD network

optimization based on VNABC）

在仿真試驗中，讀寫器工作區域為30m×30m的正方形，其中隨機分布著100個RFID標簽。由十個讀寫器組成的RFID網絡對該工作區域中的標簽進行數據采集。

實驗一，只考慮工作環境中RFID標簽覆蓋率的優化結果。從仿真結果圖中可以觀察到，VNABC算法通過調整讀寫器空間位置和發射功率來獲得合適的標簽覆蓋率，有效地將讀寫器定位在標簽密集的區域，發現的最終解也要好于ABC和PSO算法。

實驗二，只考慮降低網絡中RFID讀寫器信號干擾的優化結果。同樣，VNABC以較快的收斂速度發現較好的最終解。從仿真結果中可以觀察到，VNABC算法通過調整讀寫器空間位置和發射功率來盡量使讀寫器間的信號覆蓋區域不發生重疊。

實驗三，綜合考慮兩種因素的RFID網絡優化。結果顯示VNABC算法取得的結果仍然好于其他兩種方法。

5 結論（Conclusion）

本文的研究包括兩個個方面：第一，提出了一種基于馮諾依曼社會結構的新型人工蜂群優化算法—VNABC。該算法具有更強的穩定性和整體優化性，在標準測試函數上的性能驗證表明，所提出算法在收斂速度、跳出局部最優等性能方面均優于基本ABC算法和PSO算法，具有良好的工程應用前景。第二，將VNABC應用于求解RFID網絡標簽覆蓋和防沖突優化問題，并給出了具體實例的仿真分析，從而進一步驗證本文提出的模型和算法的有效性。

參考文獻（References）

[1] 劉化君.物聯網關鍵技術研究[J].計算機時代，2010（07）：4-6.

[2] 張光山，張爍，張有光.基于隨機時隙的RFID讀寫器防沖突方

法[J].北京航空航天大學學報，2013（6）：782-786.

[3] Karaboga D，Basturk B.On the performance of artificial beecolony

（ABC） algorithm[J].Applied Soft Computing，2008：687-689.

[4] 程曉雅.人工蜂群算法理論及其在通信中的應用研究[D].山

東大學，2012.

[5] A.P.Engelbrecht.Fundamentals of Computational Swarm

Intelligence.Wiley Publishing，Inc.2009.

作者簡介：

蘇紅麗（1979-），女，碩士，講師.研究領域：計算機網絡.endprint

（5）

Rastrigin函數是一個復雜的多峰函數，很難求解。該函數在解（0，0，…，0）處取得全局最優值0。函數的初始范圍為[-15，15]。該函數存在大量局部最優點，因此優化算法極容易選入其中而未能求得全局最優值。Rastrigin函數表達式：

（6）

Griewank在解（0，0，…，0）處取得全局最優值0。函數的初始范圍為[-600， 600]。該函數有一個乘積項，使得變量之間相互依賴，因此該函數很難求解到全局最優點。Griewank函數也是多峰函數，表達式：

（7）

在本實驗中，所有測試函數均設為30維。種群大小均為100。PSO慣性權重從0.9隨著迭代次數的增加線性下降到0.7，學習因子c1和c2均為2.0。實驗結果包括算法獨立運行30次后函數的平均值，數據如表2所示。

表2 測試函數實驗結果

Tab.2 The experimental results of test function

由實驗結果可以看出，VNABC算法在復雜多峰函數Rosenbrock、Rastrigin和Griewank函數上要明顯優于其他算法，而PSO算法在單峰函數Sphere上表現出了較高的性能。ABC算法在四個算法中表現相對較差。

3 RFID網絡優化問題（RFID network optimization）

本文考慮RFID網絡標簽覆蓋率和讀寫器防沖突建立RFID系統優化的目標函數，表示為：

（1）標簽覆蓋率

（8）

其中，NT表示RFID網絡工作區域中的標簽數量，表示第i個標簽接收到的讀寫器信號強度，Pd表示保證標簽和讀寫器能夠建立有效連接的最小場強閾值。該目標函數能夠將讀寫器定位在標簽密集的區域，并通過調整讀寫器發射功率來最大化工作區域中的RFID標簽覆蓋率。

（2）讀寫器防沖突

（9）

在該模型中用實數編碼的形式直接解決防沖突的問題。其中M表示工作區域中的讀寫器數量，函數dist（）表示兩兩讀寫器間的距離計算，Ri和Rj分別表示讀寫器i和j的實際位置，ri和rj則表示這兩個讀寫器的識讀范圍。該目標函數通過調整讀寫器的實際位置，即使兩兩讀寫器間的實際距離大于等于其識讀距離之和，盡量使讀寫器的識讀區域不發生重疊，從而達到防沖突的目的。

總目標函數為標簽覆蓋率和讀寫器防沖突的加權函數。

（10）

4 基于VNABC的RIFD網絡優化（RIFD network

optimization based on VNABC）

在仿真試驗中，讀寫器工作區域為30m×30m的正方形，其中隨機分布著100個RFID標簽。由十個讀寫器組成的RFID網絡對該工作區域中的標簽進行數據采集。

實驗一，只考慮工作環境中RFID標簽覆蓋率的優化結果。從仿真結果圖中可以觀察到，VNABC算法通過調整讀寫器空間位置和發射功率來獲得合適的標簽覆蓋率，有效地將讀寫器定位在標簽密集的區域，發現的最終解也要好于ABC和PSO算法。

實驗二，只考慮降低網絡中RFID讀寫器信號干擾的優化結果。同樣，VNABC以較快的收斂速度發現較好的最終解。從仿真結果中可以觀察到，VNABC算法通過調整讀寫器空間位置和發射功率來盡量使讀寫器間的信號覆蓋區域不發生重疊。

實驗三，綜合考慮兩種因素的RFID網絡優化。結果顯示VNABC算法取得的結果仍然好于其他兩種方法。

5 結論（Conclusion）

本文的研究包括兩個個方面：第一，提出了一種基于馮諾依曼社會結構的新型人工蜂群優化算法—VNABC。該算法具有更強的穩定性和整體優化性，在標準測試函數上的性能驗證表明，所提出算法在收斂速度、跳出局部最優等性能方面均優于基本ABC算法和PSO算法，具有良好的工程應用前景。第二，將VNABC應用于求解RFID網絡標簽覆蓋和防沖突優化問題，并給出了具體實例的仿真分析，從而進一步驗證本文提出的模型和算法的有效性。

參考文獻（References）

[1] 劉化君.物聯網關鍵技術研究[J].計算機時代，2010（07）：4-6.

[2] 張光山，張爍，張有光.基于隨機時隙的RFID讀寫器防沖突方

法[J].北京航空航天大學學報，2013（6）：782-786.

[3] Karaboga D，Basturk B.On the performance of artificial beecolony

（ABC） algorithm[J].Applied Soft Computing，2008：687-689.

[4] 程曉雅.人工蜂群算法理論及其在通信中的應用研究[D].山

東大學，2012.

[5] A.P.Engelbrecht.Fundamentals of Computational Swarm

Intelligence.Wiley Publishing，Inc.2009.

作者簡介：

蘇紅麗（1979-），女，碩士，講師.研究領域：計算機網絡.endprint