Go to the content. | Move to the navigation | Go to the site search | Go to the menu | Contacts | Accessibility

| Create Account

Zanella, Andrea (2010) Adaptive Batch Resolution Algorithm with Deferred Feedback for practical CSMA Wireless Networks. [Technical Report]

Questa è la versione più aggiornata di questo documento.

Full text disponibile come:

PDF Document

Abstract (english)

A batch is a group of nodes that have to transmit a single packet each to a common receiver in the shortest time. Most of existing batch resolution algorithms assume immediate feedback and generally neglect the feedback time, being considered much shorter than the packet transmission time. This conjecture, however, fails to apply in many practical high-rate wireless systems, with the consequence that the classical performance analysis of batch resolution algorithms may result overoptimistic. In this report we propose and analyze a batch resolution algorithm for CSMA wireless networks that waives the immediate feedback approach in favor of a deferred feedback method, which shall reduce the overhead costs. The scheme, named Adaptive Batch Resolution Algorithm with Deferred Feedback (ABRADE+ ), is obtained by merging a batch size estimate module with a framed ALOHA access scheme, whose frame length is dynamically adapted to the residual batch size in order to minimize the overall batch resolution time.
ABRADE’s adaptation strategy is designed under the assumption of known batch size. To remove this constraint, we propose a batch size estimation module that, coupled with ABRADE, gives rise to ABRADE+ ,
a complete batch resolution algorithm that works even with no a priori information on the batch size. We then extend ABRADE with a batch size estimation module, thus obtaining a complete batch resolution al-
gorithm, called ABRADE+ , that works even with no a priori information on the batch size. ABRADE+ is compared against the batch resolution algorithms based on the immediate feedback paradigm. Results
confirm that, in practical CSMA systems, ABRADE+ outperforms the algorithms based on the immediate feedback paradigm, both in case of partial and no a priori knowledge of the batch multiplicity.

Statistiche Download
EPrint type:Technical Report
Anno di Pubblicazione:26 November 2010
Settori scientifico-disciplinari MIUR:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/03 Telecomunicazioni
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:3250
Depositato il:08 Feb 2012 12:00
Simple Metadata
Full Metadata
EndNote Format


I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione.

[1] D. R. Hush and C. Wood, in In IEEE International Symposium on Information Theory, p. 107. Cerca con Google

[2] J. Hayes, “An adaptive technique for local distribution,” Communications, IEEE Transactions on, vol. 26, no. 8, pp. 1178–1186, Cerca con Google

Aug 1978. Cerca con Google

[3] J. Capetanakis, “Tree algorithms for packet broadcast channels,” Information Theory, IEEE Transactions on, vol. 25, no. 5, pp. Cerca con Google

505–515, Sep 1979. Cerca con Google

[4] P. Popovski, “Tree protocols for RFID tags with generalized arbitration spaces,” in IEEE 10th International Symposium on Spread Cerca con Google

Spectrum Techniques and Applications, 2008., Aug. 2008, pp. 18–22. Cerca con Google

[5] R. Gallager, “Conflict resolution in random access broadcast networks,” in AFOSR Workshop Commun. Theory Appl., Provincetown, Cerca con Google

MA, September 1978, pp. 74–76. Cerca con Google

[6] J. Mosely and P. Humblet, “A class of efficient contention resolution algorithms for multiple access channels,” Communications, Cerca con Google

IEEE Transactions on, vol. 33, no. 2, pp. 145–151, Feb 1985. Cerca con Google

[7] M. Molle and G. Polyzos, “Conflict resolution algorithms and their performance analysis,” Department of Computer Science and Cerca con Google

Engineering, UCSD, East Lansing, Michigan, Tech. Rep. CS93-300, July 1993. Cerca con Google

[8] D. Bertsekas and R. Gallager, Data networks (2nd ed.). Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1992. Cerca con Google

[9] S. Tasaka, “Stability and performance of the R-Aloha packet broadcast system,” IEEE Trans. Comput., vol. C, no. 32, pp. 717–726, Cerca con Google

Aug. 1983. Cerca con Google

[10] K. Jamieson, B. Hull, A. K. Miu, and H. Balakrishnan, “Understanding the Real-World Performance of Carrier Sense,” in ACM Cerca con Google

SIGCOMM Workshop on Experimental Approaches to Wireless Network Design and Analysis (E-WIND), Philadelphia, PA, August Cerca con Google

2005. Cerca con Google

[11] P. Mathys and P. Flajolet, “Q -ary collision resolution algorithms in random-access systems with free or blocked channel access,” Cerca con Google

Information Theory, IEEE Transactions on, vol. 31, no. 2, pp. 217–243, Mar 1985. Cerca con Google

[12] I. Cidon and M. Sidi, “Conflict multiplicity estimation and batch resolution algorithms,” Information Theory, IEEE Transactions on, Cerca con Google

vol. 34, no. 1, pp. 101–110, Jan 1988. Cerca con Google

[13] P. Popovski, F. H. P. Fitzek, and R. Prasad, “A class of algorithms for collision resolution with multiplicity estimation,” Algorithmica, Cerca con Google

vol. 49, no. 4, pp. 286–317, 2007. Cerca con Google

[14] Y. Tay, K. Jamieson, and H. Balakrishnan, “Collision-minimizing CSMA and its applications to wireless sensor networks,” Selected Cerca con Google

Areas in Communications, IEEE Journal on, vol. 22, no. 6, pp. 1048–1057, Aug. 2004. Cerca con Google

[15] G. Pierobon, A. Zanella, and A. Salloum, “Contention-TDMA protocol: Performance evaluation,” IEEE Transactions on Vehicular Cerca con Google

Technology, vol. 51, pp. 781–788, 2002. Cerca con Google

[16] F. C. Schoute, “Dynamic frame length ALOHA,” IEEE Trans. on Communications, vol. COM-31, no. 4, pp. 565–568, April 1983. Cerca con Google

[17] P. Popovski, F. H. P. Fitzek, and R. Prasad, “Batch conflict resolution algorithm with progressively accurate multiplicity estimation,” Cerca con Google

in DIALM-POMC ’04: Proceedings of the 2004 joint workshop on Foundations of mobile computing. New York, NY, USA: ACM, Cerca con Google

2004, pp. 31–40. Cerca con Google

[18] M. Kodialam and T. Nandagopal, “Fast and reliable estimation schemes in RFID systems,” in MobiCom ’06: Proceedings of the Cerca con Google

12th annual international conference on Mobile computing and networking. New York, NY, USA: ACM, 2006, pp. 322–333. Cerca con Google

[19] Q. Tong, X. Zou, and H. Tong, “Dynamic framed slotted aloha algorithm based on Bayesian estimation in RFID system,” in Computer Cerca con Google

Science and Information Engineering, 2009 WRI World Congress on, vol. 1, march 2009, pp. 384 –388. Cerca con Google

Versioni disponibili di questo documento

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record