Abstract
One of the most important problems for Wireless Sensor Networks (WSNs) is energy consumption since it ultimately determines the lifetime of the system. Medium Access Control (MAC) protocols based on schedules (e.g., TDMA) play an important role, since collisions and idle listening can be avoided, effectively reducing energy consumption. The problem of determining good transmission schedules for WSNs can be mapped to the distance-2 edge coloring problem in graphs, where edge colors represent slots in a TDMA-based MAC protocol, for example. In this paper, we propose and evaluate two new probabilistic and distributed distance-2 edge coloring algorithms that require no global node identifiers. We obtain analytical results for the worst-case convergence time. Moreover, we use simulations to evaluate the performance of the algorithms with respect to several metrics. Our findings indicate a tradeoff between convergence time and message overhead versus number of colors used.
Chapter PDF
Similar content being viewed by others
Keywords
References
Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: A Survey on Sensor Networks. IEEE Communications Magazine 40(8), 102–114 (2002)
Angluin, D.: Local and Global Properties in Networks of Processors. In: Proc. of 12th ACM Symposium on Theory of Computing, pp. 82–93 (1980)
Reason, J., Rabaey, J.M.: A Study of Energy Consumption and Reliability in a Multi-hop Sensor Network. ACM Mobile Comp. and Comm. Rev. 8(1), 84–97 (2004)
Ye, W., Heidemann, J.: Medium Access Control in Wireless Sensor Networks, USC/ISI Tech. Rep. ISI-TR-580 (October 2003)
Balakrishnan, et al.: The Distance-2 Matching Problem and its Relationship to the MAC-layer Capacity of Ad hoc Wireless Networks. IEEE J. on Selected Areas in Communications 22(6), 1069–1079 (2004)
Gandham, S., Dawande, M., Prakash, R.: Link Scheduling in Sensor Networks: Distributed Edge Coloring Revisited. J. of Par. and Distr. Comp. 68(8), 1122–1134 (2008)
Trigoni, N., Yao, Y., Demers, A., Gehrke, J., Rajaraman, R.: WaveScheduling: energy-efficient data dissemination for sensor networks. In: Proc. of the 1st Inter. Work. on Data Management for Sensor Networks, pp. 48–57 (2004)
Arumugam, M., Kulkarni, S.: Self-Stabilizing deterministic TDMA for Sensor Networks. In: Chakraborty, G. (ed.) ICDCIT 2005. LNCS, vol. 3816, pp. 69–81. Springer, Heidelberg (2005)
Kulkarni, S., Arumugam, M.: SS-TDMA: A self-stabilizing MAC for sensor networks. In: Sensor Network Operations, Wiley-IEEE Press (2006)
Ergen, S.C., Varaja, P.: TDMA scheduling algorithms for sensor networks, Tech. Rep., University of California, Berkley (2005)
Cui, S., Madan, R., Goldsmith, A., Lall, S.: Joint routing, Mac, and link layer optimization in sensor networks with energy constraints. In: Proc. of IEEE ICC 2005, vol. 2, pp. 725–729 (2005)
Pantazis, N.A., Vergados, D.J., Vergados, D.D., Douligeris, C.: Energy Efficiency in Wireless Sensor Networks using Sleep Mode TDMA Scheduling. Ad Hoc Networks 7(2), 322–343 (2009)
Arantes Jr., M., França, F.M.G., Martinhon, C.A.: Randomized Generation of Acyclic Orientations upon Anonymous Distributed Systems. J. of Par. and Distr. Comp. 69(3), 239–246 (2009)
Spiegel, M.R.: Mathematical Handbook of Formulas and Tables. Makron, MacGraw-Hill (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 IFIP International Federation for Information Processing
About this paper
Cite this paper
Pinho, A.C., Santos, A.A., Figueiredo, D.R., França, F.M.G. (2009). Two ID-Free Distributed Distance-2 Edge Coloring Algorithms for WSNs. In: Fratta, L., Schulzrinne, H., Takahashi, Y., Spaniol, O. (eds) NETWORKING 2009. NETWORKING 2009. Lecture Notes in Computer Science, vol 5550. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01399-7_72
Download citation
DOI: https://doi.org/10.1007/978-3-642-01399-7_72
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01398-0
Online ISBN: 978-3-642-01399-7
eBook Packages: Computer ScienceComputer Science (R0)