Article

Free access

Efficient memoryless protocol for tag identification (extended abstract)

Authors:

Ching Law,

Kayi Lee,

Kai-Yeung SiuAuthors Info & Claims

DIALM '00: Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications

Pages 75 - 84

https://doi.org/10.1145/345848.345865

Published: 01 August 2000 Publication History

PDF eReader

Abstract

This paper presents an efficient collision resolution protocol and its variations for the tag identification problem, where an electromagnetic reader attempts to obtain within is read range the unique ID number of each tag. The novelty of our main protocol is that each tag is memoryless, i.e., the current response of each tag only depends on the current query of the reader but not on the past history of the reader's queries. Moreover, the only computation required for each tag is to match its ID against the binary string in the query. Theoretical resulst in both time and communication complexities are derived to demonstrate the efficiency of our protocols.

References

[1]

MIT Auto-ID Center. http://auto-id.mit.edu/.

Google Scholar

[2]

Dimitri Bertsekas and Robert Gallager. Data Networks. Prentice-Hall, second edition, 1992.

Digital Library

Google Scholar

[3]

J. I. Capetanakis. The Multiple Access Broadcast Channel: Protocol and Capacity Considerations. PhD thesis, 1977.

Google Scholar

[4]

Shun Chan, Harley Heinrich, Dilip Kandlur, and Arvind Krishna. U.S. Patent: Multiple item radio frequency tag identification protocol. Patent number: US5550547. August 1996.

Google Scholar

[5]

G. Fayolle, P. Flajolet, M. Hofri, and P. Jacquet. Analysis of a stack algorithm for random access communication. IEEE 2~ansactions on Information Theory, IT-31(2):244-254, March 1985. (Special Issue on Random Access Communication, J. Massey editor).

Crossref

Google Scholar

[6]

Robert G. Gallager. A perspective on multiaccess channels. IEEE 2~ansactions on Information Theory, IT-31(2):124-142, March 1985. (Special Issue on Random Access Communication, J. Massey editor).

Crossref

Google Scholar

[7]

C. Law, K. Lee, and K. Siu. Efficient memoryless protocol for tag identification (full version paper). http: //perth. mit. edu/pub/D IAi,NO0. ps.

Google Scholar

[8]

J. L. Ma~sey. Collision-resolution algorithms and random-access communications. Multi. User Communication Systems, pages 73-99, 1981.

Crossref

Google Scholar

[9]

P. Mathys and P. Flajolet. Q-ary collision resolution algorithms in random access systems with free or blocked channel access. IEEE 2~ansactions on Information Theory, IT-31(2):217-243, March 1985. (Invited Paper, Special Issue on Random Access Communication, J. Massey editor).

Crossref

Google Scholar

[10]

Mart L. Molle and George C. Polyzos. Conflict resolution algorithms and their performance analysis. Technical report, 1993.

Google Scholar

[11]

Sheldon Ross. Stochastic Processes. John Wiley & Sons, Inc., second edition, 1996.

Google Scholar

[12]

Boris Tsybakov. Survey of USSR contributions to random multiple-access communications. IEEE 2~ansactions on Information Theory, IT-31(2):143-165, March 1985. (Special Issue on Random Access Communication, J. Massey editor).

Crossref

Google Scholar

Cited By

View all

Liu YTang QLi GHuang ZHuang ZFang XWen G(2024)A Memoryless Information Sharing RFID Tag Anti-Collision ProtocolData Science and Information Security10.1007/978-981-97-1280-9_8(95-109)Online publication date: 3-Apr-2024
https://doi.org/10.1007/978-981-97-1280-9_8
Pal K(2023)RFID Tag Anti-Collision Algorithms in Industrial Information SystemsHandbook of Research on Advancements of Contactless Technology and Service Innovation in Library and Information Science10.4018/978-1-6684-7693-2.ch008(146-162)Online publication date: 30-Jun-2023
https://doi.org/10.4018/978-1-6684-7693-2.ch008
Pal K(2023)Challenges of Using Wireless Sensor Network-Based RFID Technology for Industrial IoT ApplicationsHandbook of Research on Advancements of Contactless Technology and Service Innovation in Library and Information Science10.4018/978-1-6684-7693-2.ch005(80-100)Online publication date: 30-Jun-2023
https://doi.org/10.4018/978-1-6684-7693-2.ch005
Show More Cited By

Index Terms

Efficient memoryless protocol for tag identification (extended abstract)

Recommendations

An efficient certified email protocol
ISC'07: Proceedings of the 10th international conference on Information Security

A certified email protocol, also known as a nonrepudiation protocol, allows a message to be exchanged for an acknowledgement of reception in a fair manner: a sender Alice sends a message to a receiver Bob if and only if Alice receives a receipt from ...
Perfectly-Secure Asynchronous MPC for General Adversaries (Extended Abstract)
Progress in Cryptology – INDOCRYPT 2020
Abstract
We study perfectly-secure Multiparty Computation (MPC) in the asynchronous communication setting, tolerating a generalized non-threshold adversary, characterized by an adversary structure. Ashwin Kumar et al. (ACISP2002) presented a condition ...
An Efficient Deniable Key Exchange Protocol (Extended Abstract)
Financial Cryptography and Data Security

A deniable key exchange allows two parties to jointly share a secret key while neither of two nor an outsider can prove to a third party that the communication between the two happened. This is an important mechanism for realizing a deniably secure ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DIALM '00: Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications

August 2000

104 pages

ISBN:1581133014

DOI:10.1145/345848

Chairman:
Errol Lloyd
Univ. of Delaware, Newark

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DIAL-M00

Sponsor:

DIAL-M00: 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Computations

August 11, 2000

Massachusetts, Boston, USA

Acceptance Rates

DIALM '00 Paper Acceptance Rate 11 of 33 submissions, 33%;

Overall Acceptance Rate 21 of 68 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

298
Total Citations
View Citations
1,127
Total Downloads

Downloads (Last 12 months)103
Downloads (Last 6 weeks)6

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu YTang QLi GHuang ZHuang ZFang XWen G(2024)A Memoryless Information Sharing RFID Tag Anti-Collision ProtocolData Science and Information Security10.1007/978-981-97-1280-9_8(95-109)Online publication date: 3-Apr-2024
https://doi.org/10.1007/978-981-97-1280-9_8
Pal K(2023)RFID Tag Anti-Collision Algorithms in Industrial Information SystemsHandbook of Research on Advancements of Contactless Technology and Service Innovation in Library and Information Science10.4018/978-1-6684-7693-2.ch008(146-162)Online publication date: 30-Jun-2023
https://doi.org/10.4018/978-1-6684-7693-2.ch008
Pal K(2023)Challenges of Using Wireless Sensor Network-Based RFID Technology for Industrial IoT ApplicationsHandbook of Research on Advancements of Contactless Technology and Service Innovation in Library and Information Science10.4018/978-1-6684-7693-2.ch005(80-100)Online publication date: 30-Jun-2023
https://doi.org/10.4018/978-1-6684-7693-2.ch005
Wang LLuo ZGuo RLi Y(2023)A Review of Tags Anti-Collision Identification Methods Used in RFID TechnologyElectronics10.3390/electronics1217364412:17(3644)Online publication date: 29-Aug-2023
https://doi.org/10.3390/electronics12173644
Su JSheng ZHuang CLi GLiu AFu Z(2023)Identifying RFID Tags in CollisionsIEEE/ACM Transactions on Networking10.1109/TNET.2022.321901631:4(1507-1520)Online publication date: Aug-2023
https://doi.org/10.1109/TNET.2022.3219016
Benedetti DMaselli G(2022)Robust RFID Tag IdentificationSensors10.3390/s2221840622:21(8406)Online publication date: 1-Nov-2022
https://doi.org/10.3390/s22218406
Dujić Rodić LStančić IZovko KPerković TŠolić P(2022)Tag Estimation Method for ALOHA RFID System Based on Machine Learning ClassifiersElectronics10.3390/electronics1116260511:16(2605)Online publication date: 19-Aug-2022
https://doi.org/10.3390/electronics11162605
Xie XLiu XQi HGuo SLi K(2022)A Tag-Correlation-Based Approach to Fast Identification of Group TagsIEEE Transactions on Mobile Computing10.1109/TMC.2021.305257221:9(3096-3109)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TMC.2021.3052572
Rodic LStansic IZovko KSolic P(2021)Machine Learning as Tag Estimation Method for ALOHA-based RFID system2021 6th International Conference on Smart and Sustainable Technologies (SpliTech)10.23919/SpliTech52315.2021.9566455(1-6)Online publication date: 8-Sep-2021
https://doi.org/10.23919/SpliTech52315.2021.9566455
Blobel JTran VMisra ADressler F(2021)Low-Power Downlink for the Internet of Things using IEEE 802.11-compliant Wake-Up ReceiversIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488838(1-10)Online publication date: 10-May-2021
https://doi.org/10.1109/INFOCOM42981.2021.9488838
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An efficient certified email protocol

Perfectly-Secure Asynchronous MPC for General Adversaries (Extended Abstract)

An Efficient Deniable Key Exchange Protocol (Extended Abstract)