计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 122-127.doi: 10.11896/jsjkx.180801602

• 网络与通信 • 上一篇    下一篇

基于Whittle索引的RFID多阅读器信道资源分配算法

石静, 郑嘉利, 袁源, 王哲, 李丽   

  1. (广西大学计算机与电子信息学院 南宁530004)
    (广西多媒体通信与网络技术重点实验室 南宁530004)
  • 收稿日期:2018-08-30 修回日期:2019-02-02 出版日期:2019-10-15 发布日期:2019-10-21
  • 通讯作者: 郑嘉利(1979-),男,教授,主要研究方向为多媒体通信、物联网技术,E-mail:zhengjiali@vip.163.com。
  • 作者简介:石静(1992-),女,硕士生,主要研究方向为多媒体通信网络理论与技术;袁源(1995-),女,硕士生,主要研究方向为多媒体通信网络理论与技术;王哲(1992-),男,硕士生,主要研究方向为多媒体通信及其网络工程;李丽(1994-),女,硕士生,主要研究方向为多媒体通信网络理论与技术。
  • 基金资助:
    本文受国家自然科学基金项目(61761004)资助。

RFID Multi-reader Channel Resources Allocation Algorithm Based on Whittle Index

SHI Jing, ZHENG Jia-li, YUAN Yuan, WANG Zhe, LI Li   

  1. (School of Computer,Electronics and Information,Guangxi University,Nanning 530004,China)
    (Guangxi Key Laboratory of Multimedia Communications and Network Technology,Nanning 530004,China)
  • Received:2018-08-30 Revised:2019-02-02 Online:2019-10-15 Published:2019-10-21

摘要: 针对无线射频识别(RFID)系统中多标签-多阅读器环境下标签与信道资源的分配问题,提出了一种基于Whittle索引的多阅读器信道资源分配算法。在RFID多阅读器信道分配问题中建立无休止多臂赌博机(RMAB)模型,并采用Whittle索引算法进行求解。该算法依据信道前期的忙、闲状态,将信道空闲概率作为信任值赋予每个信道,并根据信道当前的信任值计算其Whittle索引值。标签选择索引值最大的信道作为可能感知接入的信道,随后根据每个时隙数据发送成功与否来动态更新信道信任值。对信道分配过程中可能出现的标签碰撞问题,采用等待一个时隙后再根据识别反馈信息重新选择接入信道的方式来解决。将文中所提算法从两个方面与典型的DiCa算法和Gentle算法进行比较:一是在阅读器数量固定的前提下,其系统吞吐量随待识别标签数量的变化情况;二是在待识别标签数量固定的前提下,其系统吞吐量随阅读器数量的变化情况。仿真结果表明,所提算法在上述两种情况下的系统吞吐量均优于DiCa算法和Gentle算法,其吞吐量在阅读器数量固定的前提下分别平均提高了150.34%和23.98%,在待识别标签数量固定的前提下分别平均提高了205.01%和43.37%。随着阅读器和待识别标签数量的增多,所提算法在系统吞吐量方面的优势更加明显。因此,采用提出的算法可以对有限的信道资源进行合理的动态分配,有效提高RFID多阅读器系统的识别效率。

关键词: 无线射频识别, 多标签-多阅读器, 无休止多臂赌博机模型, Whittle索引算法

Abstract: This paper proposed amulti-reader channel resources allocation algorithm based on Whittle index for the problem that how to allocate the correspondence between tags and channel resources in the environment of Radio Frequency Identification (RFID) system with multi-tag and multi-reader.The Restless Multi-Armed Bandit (RMAB) mo-del is established and the Whittle index algorithm is adopted to solve the problem of RFID multi-reader channels allocation.According to the previous state of channels:idle or busy,the readers achieve one trust value for every channel based on its idle probability and use the current trust value to calculate the Whittle index for each channel.The tags choose the one with the largest index value as a possible sensing and accessing channel.Then,the trust value of the channels is dynamically updated based on the successful or failing data transmission in each time slot.For the collisions that may occur between tags during channel allocation,the method of reselecting and accessing based on the identified feedback information after waiting for one time slot can solve it.The proposed algorithm is compared with the typical DiCa algorithm and Gentle algorithm in the following two aspects.Firstly,the system throughput varies with the number of tags to be identified under the premise that the number of readers is fixed.Secondly,the system throughputvaries with the number of readers to be identified under the premise that the number of tags is fixed.The simulation results show that the system throughput of the proposed algorithm is superior to DiCa algorithm and Gentle algorithm in both cases.The throughput increases by an average of 150.34% and 23.98% respectively on the premise of fixed number of readers,205.01% and 43.37% respectively on the premise of fixed number of tags to be identified.Moreover,with the increase of the number of readers and tags to be identified,the advantages of the proposed algorithm in terms of system throughput are more obvious.Therefore,the proposed algorithm can be used to reasonably allocate the limited channel resources,thus effectively improving the recognition efficiency of the RFID multi-reader system.

Key words: Radio frequency identification, Multi-tag and multi-reader, Restless multi-armed bandit model, Whittle index algorithm

中图分类号: 

  • TN92
[1]RAJARAMAN V.Radio frequency identification[J].Re-sonance,2017,22(6):549-575.
[2]YU Y,YU X,ZHAO Z,et al.Image Analysis System for Optimal Geometric Distribution of RFID Tags Based on Flood Fill and DLT[J].IEEE Transactions on Instrumentation and Mea-surement,2018,67(4):839-848.
[3]DU J,SUGUMARAN V,GAO B.RFID and Multi-Agent Based Architecture for Information Sharing in Prefabricated Component Supply Chain[J].IEEE Access,2017,5:4132-4139.
[4]REZAIE H,GOLSORKHTABARAMIRI M.A fair reader collision avoidance protocol for RFID dense reader environments[J].Wireless Networks,2018,24(6):1953-1964.
[5]CHEN H,WANG Z,XIA F,et al.Efficiently and Completely Identifying Missing Key Tags for Anonymous RFID Systems[J].IEEE Internet of Things Journal,2018,5(4):2915-2926.
[6]NAFAR F,SHAMSI H.Design and Implementation of an RFID-GSM based Vehicle Identification System on Highways[J].IEEE Sensors Journal,2018,18(17):7281-7293.
[7]ZHANG Y,YANG F,WANG Q,et al.An anti-collision algorithm for RFID-based robots based on dynamic grouping binary trees[J].Computers & Electrical Engineering,2017,63:91-98.
[8]ZHOU S K,DENG M L.Survey on ALOHA tag anti-collision algorithm[J].Computer Engineering and Applications,2017,53(14):9-17.(in Chinese)
周少珂,邓淼磊.ALOHA标签防碰撞算法综述[J].计算机工程与应用,2017,53(14):9-17.
[9]WANG C H,LIU C S,XU H,et al.An enhanced binary tree-based anti-collision algorithm[J].Journal of Hunan University(Natural Sciences),2013,40(8):97-101.(in Chinese)
王春华,刘迟时,徐浩,等.一种改进的基于二叉树的防碰撞算法[J].湖南大学学报(自科版),2013,40(8):97-101.
[10]GOLSORKHTABARAMIRI M,ISSAZADEHKOJIDI N.A Distance Based RFID Reader Collision Avoidance Protocol for Dense Reader Environments[J].Wireless Personal Communications,2017,95(2):1781-1798.
[11]YANG X M,DU L,WANG J H,et al.Improved RFID anti-collision algorithm based on identity competition and cooperation[J].Journal of University of Electronic Science and Technology of China,2015,44(5):764-768.(in Chinese)
杨晓明,杜力,王佳昊,等.基于身份竞争与协作的RFID阅读器防碰撞算法[J].电子科技大学学报,2015,44(5):764-768.
[12]SAFA H,EL-HAJJ W,MEGUERDITCHIAN C.A distributed multi-channel reader anti-collision algorithm for RFID environments[J].Computer Communications,2015,64(1):44-56.
[13]SOHN S,JUNG J J.Channel and time slot allocation for dense RFID networks[J].Wireless Personal Communications,2013,73(2):329-339.
[14]ZHU J,HAN C,YANG H L,et al.Dynamic spectrum access mechanism of multi-users based on restless multi-armed bandit model in cognitive networks[J].Journal of Computer Applications,2014,34(10):2782-2786.(in Chinese)
朱江,韩超,杨浩磊,等.认知无线网络中基于无休止多臂赌博机模型的多用户频谱接入机制[J].计算机应用,2014,34(10):2782-2786.
[15]REVERDY P,SRIVASTAVA V,LEONARD N E.Satisficing in multi-armed bandit problems[J].IEEE Transactions on Automatic Control,2015,62(8):3788-3803.
[16]HE X,YANG X S,KARAMANOGLU M,et al.Global convergence analysis of the flower pollination algorithm:a discrete-time Markov chain approach[J].Procedia Computer Science,2017,108:1354-1363.
[17]BORKAR V S.Whittle index for partially observed binary Markov decision processes[J].IEEE Transactions on Auto-matic Control,2017,62(12):6614-6618.
[18]MOSHREF M.Improved Anti-Collision Algorithm for Tag Identification in Future Internet of Things[J].International Journal of Computer Network and Information Security,2017,9(3):11.
[1] 袁源, 郑嘉利, 石静, 王哲, 李丽. 基于Q-learning的RFID多阅读器防碰撞算法[J]. 计算机科学, 2019, 46(6): 124-127.
[2] 甘勇, 王凯, 贺蕾. 一种全新的RFID标签所有权转移协议[J]. 计算机科学, 2018, 45(11A): 369-372.
[3] 张亚力,郭亚军,崔建群,曾庆江. 一种新的超轻量级RFID认证协议[J]. 计算机科学, 2017, 44(1): 183-187.
[4] 孟凡振,吴杰,卜旭松,冯锋. 基于马尔可夫链模型的井下目标轨迹预测算法[J]. 计算机科学, 2014, 41(Z6): 321-323.
[5] 钱晓军,朱颖,吉根林. 一种改进的物联网二进制防碰撞算法[J]. 计算机科学, 2012, 39(9): 24-27.
[6] 邓淼磊,黄照鹤,鲁志波. EPCGen2标准下安全的RFID认证协议[J]. 计算机科学, 2010, 37(7): 115-117.
[7] 邓森磊,马玉军,石金娥,周利华. 安全的航空物品管理RFID系统[J]. 计算机科学, 2010, 37(11): 107-110.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .