面向RFID动态帧时隙ALOHA协议的帧长优化

doi:10.3778/j.issn.1673-9418.2006010

摘要/Abstract

摘要：

近年来，国家电网积极推动泛在电力物联网的建设，以实现电力系统的万物互联与优化管理。其中，射频识别技术（RFID）作为泛在电力物联网建设的核心技术，凭其价格低廉、无需电源、非视距通信、远距离通信等特点，被广泛应用于电力仓储物资管理、电力巡检等应用场景。为了盘点电力设备仓库中的物品，需要快速识别粘贴在物品上的标签，然而由于仓库中存在大量标签，在通信过程中容易产生标签信号冲突。针对当前商用RFID系统普遍采用的符合EPC C1G2标准的动态帧时隙ALOHA协议，提出了一种新型的基于Q-learning与神经网络的帧长优化算法（记作QN-learning）。通过将动态帧长选择问题转化为马尔可夫决策过程（MDP），即观察到的状态为不同种类时隙的个数（空时隙数、单时隙数、冲突时隙数），执行的动作为设置合理的帧长，从而利用Q-learning与神经网络来自主学习帧长选择策略，基于学习到的策略可以指导系统根据最新观察选择能够实现全局最优的帧长。仿真实验结果表明，基于QN-learning算法在动态调整帧长方面表现优异，能够实现标签的有效识别，在保障高吞吐率的同时控制阅读器的询问次数，减少数据传输量。

关键词: 射频识别（RFID）, 动态帧时隙ALOHA, 帧长优化, 马尔可夫决策过程（MDP）, Q-learning

Abstract:

In recent years, the State Grid has actively promoted the construction of ubiquitous power Internet of things, so as to realize the interconnection and optimized management of things in the power system. Specifically, radio frequency identification (RFID) is the core technology for the construction of ubiquitous power Internet of things. Due to the advantages such as low-cost, battery-less, non-line-of-sight communication and long-distance communi-cation, RFID has been widely used in the power equipment management, the power inspection, and other applications. To inventory the items in the power equipment warehouse, the ID collection requires the fast tag identification. However, there are usually a large number of tags in the warehouse, and the signals from different tags will easily conflict with each other. Considering the dynamic framed ALOHA protocol conforming to EPC C1G2 standards in commodity RFID systems, this paper proposes a frame size adjustment algorithm based on Q-learning and neural network (denoted as QN-learning). The problem of adjusting the frame size can be modeled as the Markov decision process (MDP), the observed states are the number of different kinds of slots, i.e., empty slot, single slot and collision slot, and the actions correspond to the selected frame sizes. Therefore, the neural network-based Q-learning, named as QN-learning, is preferred to learn how to adjust the frame size adaptively. Referring to the learned strategy, the agent is able to select the global-optimal frame size with the latest observation. Simulation results show that the proposed QN-learning-based method performs well in terms of the frame size adjustment. Particularly, the QN-learning-based method can identify tags fast with high throughput and few query rounds, and it reduces the data transmission as well.

Key words: radio frequency identification (RFID), dynamic framed slotted ALOHA, frame size optimization, Markov decision process (MDP), Q-learning

何金栋, 卜艳玲, 石聪聪, 谢磊. 面向RFID动态帧时隙ALOHA协议的帧长优化[J]. 计算机科学与探索, 2021, 15(7): 1227-1236.

HE Jindong, BU Yanling, SHI Congcong, XIE Lei. Frame Size Optimization for Dynamic Framed Slotted ALOHA in RFID Systems[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(7): 1227-1236.

参考文献

[1] XIE L, LU S L. Principle, protocol and system design of RFID[M]. 2nd ed. Beijing: Science Press, 2016.
谢磊，陆桑璐. 射频识别技术: 原理, 协议及系统设计[M]. 2版. 北京: 科学出版社, 2016.
[2] XIE L, YIN Y F, CHEN X, et al. RFID data management: algorithms, protocols and performance evaluation[J]. Chinese Journal of Computers, 2013, 36(3): 457-470.
谢磊, 殷亚凤, 陈曦, 等. RFID数据管理: 算法,协议与性能评测[J]. 计算机学报, 2013, 36(3): 457-470.
[3] QI S, ZHENG Y, LI M, et al. Scalable industry data access control in RFID-enabled supply chain[J]. IEEE/ACM Trans-actions on Networking, 2016, 24(6): 3551-3564.
[4] LIN Q, YANG L, DUAN C, et al. Revisiting reading rate with mobility: rate-adaptive reading of COTS RFID systems[J]. IEEE Transactions on Mobile Computing, 2018, 18(7): 1631-1646.
[5] WANG G, HAN J, QIAN C, et al. Verifiable smart packaging with passive RFID[J]. IEEE Transactions on Mobile Compu-ting, 2018, 18(5): 1217-1230.
[6] ZHU W P, MENG X, PENG X L, et al. Collisions are preferred: RFID-based stocktaking with a high missing rate[J]. IEEE Transactions on Mobile Computing, 2020, 19(7): 1544-1554.
[7] WANG X, LIU J, WANG Y, et al. Efficient missing tag iden-tification in blocker-enabled RFID systems[J]. Computer Networks, 2019, 164: 106894.
[8] LIU X, LI K, MIN G, et al. Completely pinpointing the mis-sing RFID tags in a time-efficient way[J]. IEEE Transactions on Computers, 2013, 64(1): 87-96.
[9] AN Z L, LIN Q Z, YANG L, et al. Embracing tag collisions: acquiring bloom filters across RFIDs in physical layer[C]//Proceedings of the 2019 IEEE Conference on Computer Communications, Paris, Apr 29-May 2, 2019. Piscataway: IEEE, 2019: 1531-1539.
[10] YANG L, LIN Q, DUAN C, et al. Analog on-tag Hashing: towards selective reading as Hash primitives in Gen2 RFID systems[C]//Proceedings of the 23rd Annual International Conference on Mobile Computing and Networking, Snowbird, Oct 16-20, 2017. New York: ACM, 2017: 301-314.
[11] YUAN Y, ZHENG J L, SHI J, et al. Anti-collision algorithm based on Q-learning for RFID multiple readers[J]. Computer Science, 2019, 46(6): 124-127.
袁源, 郑嘉利, 石静, 等. 基于Q-learning的RFID多阅读器防碰撞算法[J]. 计算机科学, 2019, 46(6): 124-127.
[12] PAN X F, CAO J H. Algorithm of label identification based on MDP model[J]. Computer Engineering and Design, 2017, 38(6): 1608-1613.
潘雪峰, 曹加恒. 基于MDP模型的标签识别算法[J]. 计算机工程与设计, 2017, 38(6): 1608-1613.
[13] DONG H L, ZHOU C H, LIU Z F. Formal analysis of S-ALOHA protocol based on the Markoff decision process[J]. Wireless Communication Technology, 2014, 23(4): 1-6.
董恒龙, 周从华, 刘志锋. 基于马尔科夫决策过程的S-ALOHA协议的形式化分析[J]. 无线通信技术, 2014, 23(4): 1-6.
[14] LI B B, HE Y, LIU W Y, et al. LocP: an efficient localized polling protocol for large-scale RFID systems[C]//Proceedings of the 24th IEEE International Conference on Network Protocols, Singapore, Nov 8-11, 2016. Washington: IEEE Computer Soc-iety, 2016: 1-10.
[15] UYSAL I, KHANNA N. Q-frame-collision-counter: a novel and dynamic approach to RFID Gen 2??s Q algorithm[C]//Proceedings of the 2015 IEEE International Conference on RFID Technology and Application, Tokyo, Sep 16-18, 2015. Piscataway: IEEE, 2015: 120-125.
[16] SU J, SHENG Z, HONG D, et al. An effective frame breaking policy for dynamic framed slotted Aloha in RFID[J]. IEEE Communications Letters, 2016, 20(4): 692-695.
[17] AGRAWAL T, BISWAS P K, RAOOT A D, et al. Optimum frame size evaluation framework for efficient tag identification in passive RFID systems[C]//Proceedings of the 2013 IEEE Wireless Power Transfer, Perugia, May 15-16, 2013. Piscat-away: IEEE, 2013: 48-51.
[18] FERDOUS A, JEEVARATHNAM N G, UYSAL I. Comparative analysis of tag estimation algorithms on RFID EPC Gen-2 performance[C]//Proceedings of the 2017 IEEE International Conference on RFID Technology and Application, Warsaw, Sep 20-22, 2017. Piscataway: IEEE, 2017: 186-190.
[19] XIE L, SHENG B, TAN C C, et al. Efficient tag identification in mobile RFID systems[C]//Proceedings of the 29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communica-tions Societies, San Diego, Mar 15-19, 2010. Piscataway: IEEE, 2010: 1001-1009.
[20] YANG Z W. Research of RFID anti-collision algorithm based on Q-value[D]. Nanning: Guangxi University, 2018.
杨子薇. 基于Q值的RFID防碰撞算法研究[D]. 南宁: 广西大学, 2018.
[21] EPCglobal Inc. EPC radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860 MHz-960 MHz: EPC GS1[S]. 2008.
[22] ZHOU Z H. Machine learning[M]. Beijing: Tsinghua University Press, 2016.
周志华. 机器学习[M]. 北京: 清华大学出版社, 2016.