结合模拟退火与启发式演算法应用於RFID系统之读取器通道配置.PDFVIP

結合結合模擬退火模擬退火 與啟發式演算法與啟發式演算法 應用於應用於 RFID系統RFID系統之讀取器通道配置之讀取器通道配置 結合結合模擬退火模擬退火 與與啟發式演算法啟發式演算法 應用於應用於 RFIDRFID系統系統之讀取器通道配置之讀取器通道配置 1 2 1 1 黃永發黃永發 、、 沈培輝沈培輝 、、 洪勝偉洪勝偉 、、 丁賢丁賢 黃永發黃永發 、、 沈培輝沈培輝 、、 洪勝偉洪勝偉 、、 丁賢丁賢 1 朝陽科技大學資訊與通訊系 yfahuang@cyut.edu.tw 2 國立中興大學電子商務研究所 摘要摘要 題存在 ，但為達成良好之覆蓋率(coverage rate) ，必 摘要摘要 須使用許多個讀取器 ，於是密集的部署讀取器是必 我們探討在一個密集的環境下隨機部署讀取 要的 ，但在大規模的部署或在密集的部署環境下， 器的通道配置 ，以演算法來配置讀取器傳送時所需 讀取器之間會有干擾 (interference)的問題 ，甚至會有 的通道 ，啟發式(Heuristics)演算法的快速收斂 碰撞 (collision)的問題 ，因為在頻率與通道相同時， (Converge)特性優於模擬退火(Simulated annealing) 所產生的干擾與碰撞會造成 RFID 系統的不穩定甚 演算法 ，但模擬退火演算法卻可以利用較少的通道 至癱瘓[6] [7] [8] ，因此解決RFID的路徑損失與干 配置達到沒有碰撞的發生 ，且在資料傳輸通道數的 擾碰撞問題是必要的 。所以我們將針對在密集環境 使用也較為均勻 。最後，為了提升通通道配置的速 下 RFID讀取器與讀取器之間所產生的碰撞的問題 度及通道使用率的平衡 ，在一個無法預設可用通道 來提出一個通道分配的方法在二維空間隨機部署 數的情況下 ，我們提出一個複合式演算法(Hybrid 讀取器做解決 ，並利用不同的演算法做實驗與比 Algorithm ，Heur-SA) ，首先以啟發式演算法快速收 較。 斂的特性 ，尋找一個零碰撞的通道配置後，設這個 本文分為五小節，在第二節中我們介紹我們所 解為模擬退火演算法的初始條件 ，以達到一個通道 運用的演算法 ，並從中我們了解兩種演算法的優缺 使用率平衡的配置 ，修正後的演算法有效的減少了 點，在第三節中我們假設我們的模擬環境且 分別在 50%的時間花費 。 實驗中 比較不同演算法中的(1)碰撞數 、(2) 收斂速 度、 (3)通道配置平均度 ，在第四節描述我們所提出 關鍵詞關鍵詞 ：無線射頻識別系統，讀取器，收斂，模擬 關鍵詞關鍵詞 的複合式演算法所改善的優點 ，最後在第五節中是 退火演算法 ，啟發式演算法。 總結 。 1.前言前言 前言前言 2.最佳化最佳化演算法演算法 最佳化最佳化演算法演算法 無線射頻識別 （Radio Frequency Identification, 近年來許多利用分頻多工的方式來解決讀取器 RFID ）技術，是一種