Abstract
There is a long-standing vision of embedding backscatter nodes like RFIDs into everyday objects to build ultra-low power ubiquitous networks. A major problem that has challenged this vision is that backscatter communication is neither reliable nor efficient. Backscatter nodes cannot sense each other, and hence tend to suffer from colliding transmissions. Further, they are ineffective at adapting the bit rate to channel conditions, and thus miss opportunities to increase throughput, or transmit above capacity causing errors.
This paper introduces a new approach to backscatter communication. The key idea is to treat all nodes as if they were a single virtual sender. One can then view collisions as a code across the bits transmitted by the nodes. By ensuring only a few nodes collide at any time, we make collisions act as a sparse code and decode them using a new customized compressive sensing algorithm. Further, we can make these collisions act as a rateless code to automatically adapt the bit rate to channel quality --i.e., nodes can keep colliding until the base station has collected enough collisions to decode. Results from a network of backscatter nodes communicating with a USRP backscatter base station demonstrate that the new design produces a 3.5× throughput gain, and due to its rateless code, reduces message loss rate in challenging scenarios from 50% to zero.
- Alien Technology Inc. ALN-9640 Squiggle Inlay. www.alientechnology.com.Google Scholar
- Alien Technology Inc. Common RFID Implementation Issues. Tech. Report. http://www.alientechnology.com/docs/.Google Scholar
- P. Bardell, W. McAnney, and J. Savir. Built-In Test for VLSI: Pseudorandom Techniques. John Wiley & Sons, 1987. Google ScholarDigital Library
- R. Berinde, A. Gilbert, P. Indyk, H. Karloff, and M. Strauss. Combining geometry and combinatorics: a unified approach to sparse signal recovery. Allerton Conference, 2008.Google ScholarCross Ref
- R. Berinde and P. Indyk. Sequential sparse matching pursuit. Allerton Conference, 2009. Google ScholarDigital Library
- M. Brazeal. RFID: Improving the Customer Experience. Paramount Market Publishing, 2009.Google Scholar
- M. Buettner and D. Wetherall. A Gen 2. RFID Monitor Based on the USRP. SIGCOMM Communication Review, 2010. Google ScholarDigital Library
- M. Buettner and D. Wetherall. A Software Radio-based UHF RFID Reader for PHY/MAC Experimentation. IEEE RFID, 2011.Google ScholarCross Ref
- E. Candès, J. Romberg, and T. Tao. Stable signal recovery incomplete and inaccurate measurements. Comm. Pure Appl. Math., 2006.Google ScholarCross Ref
- E. Candes and T. Tao. Near-optimal signal recovery from random projections and universal encoding strategies. IEEE Transactions on Information Theory, November 2004. Google ScholarDigital Library
- I. Carron. Compressive sensing: Section 4 sparse recovery solvers. http://sites.google.com/site/igorcarron2/cs, 2012.Google Scholar
- N. Cho, S.-J. Song, S. Kim, S. Kim, and H.-J. Yoo. A 5.1-μw UHF RFID tag chip integrated with sensors for wireless environmental monitoring. In ESSCIRC, 2005.Google Scholar
- D. Donoho. Compressed sensing. IEEE Trans. on Info. Theory, 2006. Google ScholarDigital Library
- EPCglobal Inc. EPCglobal Class 1 Generation 2 V. 1.2.0. http://www.gs1.org/gsmp/kc/epcglobal/uhfc1g2.Google Scholar
- C. Estan, G. Varghese, and M. Fisk. Bitmap algorithms for counting active flows on high speed links. In IMC, 2003. Google ScholarDigital Library
- K. Finkenzeller. RFID Handbook. John Wiley & Sons, 2010.Google Scholar
- A. Fletcher, V. Goyal, and S. Rangan. A sparsity detection framework for on-off random access channels. In ISIT, 2009. Google ScholarDigital Library
- Frost & Sullivan. Global RFID healthcare and pharmaceutical market. Industry Report, 2011.Google Scholar
- Frost & Sullivan. Global RFID market. Industry Report, 2011.Google Scholar
- R. Gallager. Low-density parity-check codes. IEEE Transactions on Information Theory, 1962.Google ScholarCross Ref
- S. Gollakota and D. Katabi. ZigZag decoding: Combating hidden terminals in wireless networks. In SIGCOMM, 2008. Google ScholarDigital Library
- M. Grant, S. Boyd, and Y. Ye. CVX: Matlab software for disciplined convex programming. http://cvxr.com/cvx.Google Scholar
- R. E. Greeff, F. W. Smith, and D. K. Ovard. RFID device time synchronization. Patent US7889083, 2006.Google Scholar
- J. Griffin and G. Durgin. Complete link budgets for backscatter-radio and RFID systems. IEEE Antennas and Propagation Magazine, 2009.Google ScholarCross Ref
- A. Gudipati and S. Katti. Strider: Automatic rate adaptation and collision handling. In ACM SIGCOMM, 2011. Google ScholarDigital Library
- D. Halperin, T. Anderson, and D. Wetherall. Taking the sting out of carrier sense: Interference cancellation for wireless lans. In ACM MobiCom, 2008. Google ScholarDigital Library
- Impinj Speedway. R420 RFID reader. www.impinj.com.Google Scholar
- E. Inc. Universal Software Radio Peripheral. http://ettus.com.Google Scholar
- T. Jayram and D. Woodruf. Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error. In SODA, 2011. Google ScholarDigital Library
- M. Karim and M. Sarraf. W-CDMA and CDMA2000 for 3G mobile networks. McGraw-Hill, 2002. Google ScholarDigital Library
- D. Klair, K.-W. Chin, and R. Raad. A survey and tutorial of RFID anti-collision protocols. IEEE Comm. Surveys, 2010. Google ScholarDigital Library
- M. Kodialam and T. Nandagopal. Fast and reliable estimation schemes in RFID systems. MobiCom, 2006. Google ScholarDigital Library
- Y. Kou, S. Lin, and M. Fossorier. Low-density parity-check codes based on finite geometries: a rediscovery and new results. Transactions on Information Theory, 2001. Google ScholarDigital Library
- Laird Technologies. Crushcraft S9028PCRW RFID antenna. http://www.arcadianinc.com/.Google Scholar
- T. Lee. The Design of CMOS Radio-Frequency Integrated Circuits. Cambridge University Press, 1998.Google Scholar
- H.-C. Liu and J.-P. Ciou. Performance analysis of multi-carrier RFID systems. In SPECTS, 2009. Google ScholarDigital Library
- C. Mutti and C. Floerkemeier. CDMA-based RFID systems in dense scenarios: Concepts and challenges. In IEEE Int. Conf. RFID, 2008.Google ScholarCross Ref
- M. Pelino, C. Mines, J. Warner, and S. Musto. M2M connectivity helps telcos offset declining traditional services. Forrester Research, 2011.Google Scholar
- J. Perry, H. Balakrishnan, and D. Shah. Rateless spinal codes. In HotNets-X, 2011. Google ScholarDigital Library
- E. Porat and M. Strauss. Sublinear time, measurement optimal, sparse recovery for all. In SODA, 2012. Google ScholarDigital Library
- J. Posamentier. RFID tag clock synchronization. Patent US20070205871, 2006.Google Scholar
- PowerID. Battery assisted passive RFID tags read at 160Google Scholar
- feet. The RFID Network, 2012. www.rfid.net.Google Scholar
- D. Shen, G. Woo, A. Lippman, D. Reed, and J. Wang. Separation of multiple passive RFID signals using software defined radio. In IEEE Int. Conference on RFID, 2009.Google Scholar
- M. Sipser and D. Spielman. Expander codes. IEEE Transactions on Information Theory, 42:1710--1722, 1996. Google ScholarCross Ref
- C. Swedberg. Visual data center combines RFID with 3-d thermal imaging. RFID Journal, July 2010.Google Scholar
- D. Tse and P. Vishwanath. Fundamentals of Wireless Communications. Cambridge University Press, 2005. Google ScholarDigital Library
- M. Vutukuru, H. Balakrishnan, and K. Jamieson. Cross-layer wireless bit rate adaptation. In ACM SIGCOMM, 2009. Google ScholarDigital Library
- A. Wang, S. Cho, C. Sodini, and A. Chandrakasan. Energy efficient modulation and mac for asymmetric RF microsensor systems. In Int. Symposium on Low Power Electronics, 2001. Google ScholarDigital Library
- J. Yu, K. Liu, and G. Yan. A novel RFID anti-collision algorithm based on sdma. In WiCOM, 2008.Google ScholarCross Ref
- H. Zhang, J. Gummeson, B. Ransford, and K. Fu. Moo: A batteryless computational RFID and sensing platform. Tech Report UMASS, 2011. http://spqr.cs.umass.edu/moo/.Google Scholar
- Y. Zhang, H.-H. Chen, and M. Guizani. Cooperative Wireless Communications. CRC Press, 2009. Google ScholarDigital Library
- T. Zimmerman. Assessing the capabilities of RFID technologies. Gartner, 2009.Google Scholar
Index Terms
- Efficient and reliable low-power backscatter networks
Recommendations
Efficient and reliable low-power backscatter networks
SIGCOMM '12: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communicationThere is a long-standing vision of embedding backscatter nodes like RFIDs into everyday objects to build ultra-low power ubiquitous networks. A major problem that has challenged this vision is that backscatter communication is neither reliable nor ...
Performance analysis of unslotted CSMA/CA in wireless networks
In this paper a novel analytical model for the saturation throughput of unslotted Carrier Sensing Multiple Access with Collision Avoidance (CSMA/CA) in wireless networks is proposed. A fixed point procedure is developed based on the interaction of the ...
Contention in multi-hop wireless networks: model and fairness analysis
MSWiM '09: Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systemsIn multi-hop wireless networks with Carrier Sense Multiple Access (CSMA), unfairness may arise due to a number of reasons. A majority of the existing work focuses on fairness issues due to hidden terminals and the impact on backoff mechanisms. This ...
Comments