{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:43:19Z","timestamp":1760222599866,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2010,10,13]],"date-time":"2010-10-13T00:00:00Z","timestamp":1286928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>In wireless sensor networks, energy efficiency is mainly achieved by making nodes sleep. In this paper, we present the combination of SERENA, a new node activity scheduling algorithm based on node coloring, with TDMA\/CA, a collision avoidance MAC protocol. We show that the  combination of these two protocols enables substantial bandwidth and energy benefits for both general and data gathering applications. As a first contribution, we prove that the three-hop node coloring problem is NP-complete. As a second contribution, the overhead induced by SERENA during network coloring is reduced, making possible the use of these protocols even in dense networks with limited bandwidth. The third contribution of this paper is to show that applying any slot assignment algorithmwith spatial reuse based on node neighborhood without taking into account link quality can lead to poor performances because of collisions. The use of good quality links will prevent this phenomenon. The fourth contribution consists of optimizing end-to-end delays for data gathering applications, by means of cross-layering with the application. However, color conflicts resulting from topology changes, mobility and late node arrivals can give rise to collisions. As a fifth contribution, we show how the MAC layer can detect color conflicts, and cope with them at the cost of a slightly reduced throughput. Then, we discuss the tradeoffbetween requesting SERENA to solve the color conflicts and dealing with them at the MAC layer, our third contribution. The combination of SERENA and TDMA\/CA is evaluated through simulations on realistic topologies.<\/jats:p>","DOI":"10.3390\/fi2040469","type":"journal-article","created":{"date-parts":[[2010,10,13]],"date-time":"2010-10-13T11:10:49Z","timestamp":1286968249000},"page":"469-504","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Node Coloring and Color Conflict Detection in Wireless Sensor Networks"],"prefix":"10.3390","volume":"2","author":[{"given":"Saoucene","family":"Mahfoudh","sequence":"first","affiliation":[{"name":"INRIA, Rocquencourt, 78153 Le Chesnay Cedex, France"}]},{"given":"Gerard","family":"Chalhoub","sequence":"additional","affiliation":[{"name":"LIMOS-CNRS, Clermont Universit\u00e9, Les C\u00e9seaux, 63177 Aubi\u00e8re Cedex, France"}]},{"given":"Pascale","family":"Minet","sequence":"additional","affiliation":[{"name":"INRIA, Rocquencourt, 78153 Le Chesnay Cedex, France"}]},{"given":"Michel","family":"Misson","sequence":"additional","affiliation":[{"name":"LIMOS-CNRS, Clermont Universit\u00e9, Les C\u00e9seaux, 63177 Aubi\u00e8re Cedex, France"}]},{"given":"Ichrak","family":"Amdouni","sequence":"additional","affiliation":[{"name":"INRIA, Rocquencourt, 78153 Le Chesnay Cedex, France"}]}],"member":"1968","published-online":{"date-parts":[[2010,10,13]]},"reference":[{"key":"ref_1","unstructured":"IEEE Computer Society (1999). Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Computer Society. ANSI\/IEEE Standard 802.11."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/293927.293928","article-title":"PAMAS\u2014Power Aware Multi-access protocol with Signalling for Ad Hoc Networks","volume":"28","author":"Singh","year":"1998","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_3","unstructured":"Ye, W., Heidemann, J., and Estrin, D. An Energy-efficient MAC Protocol for Wireless Sensor Networks. Proceedings of the IEEE Infocom."},{"key":"ref_4","unstructured":"Van Dam, T., and Langendoen, K. (, January November). An Adaptive Energy-efficient MAC Protocol for Wireless Sensor Networks. Proceedings of ACM Sensys, Los Angeles, CA, USA."},{"key":"ref_5","unstructured":"Lu, G., Krishnamachari, B., and Raghavendra, C. (, January April). An adaptive energy-efficient and low-latency MAC for data gathering in sensor networks. Proceedings of International Parallel and Distributed Processing Symposium, Santa Fe, NM, USA."},{"key":"ref_6","unstructured":"IEEE Computer Society (2006). Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (WPANs), IEEE Computer Society. ANSI\/IEEE Standard 802.15.4."},{"key":"ref_7","unstructured":"Rhee, I., Warrier, A., Aia, M., and Min, J. (, January November). Z-MAC: A hybrid (MAC) for wireless sensor networks. Proceedings of SenSys\u201905, San Diego, CA, USA."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Rhee, I., Warrier, A., and Xu, L. (2005). Randomized dining philosophers to TDMA scheduling in wireless sensor networks, North Carolina State University. Technical Report TR-2005-21.","DOI":"10.1145\/1132905.1132927"},{"key":"ref_9","unstructured":"Jain, K., Padhye, J., Padmanabhan, V., and Qiu, L. (, January September). Impact of interference on multi-hop wireless network performance. Proceedings of ACM MobiCom, San Diego, CA, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.jpdc.2007.12.006","article-title":"Link scheduling in sensor networks: distributed edge coloring revisited","volume":"68","author":"Gandham","year":"2008","journal-title":"J. Paral. Distrib. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ma, J., Lou, W., Wu, Y., and Li, X.-Y. (, January April). Energy efficient TDMA sleep scheduling in wireless sensor networks. Proceedings of INFOCOM 2009, Rio de Janeiro, Brazil.","DOI":"10.1109\/INFCOM.2009.5061970"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/TCOMM.2004.826234","article-title":"Genetic algorithm to solve optimum TDMA transmission schedule in broadcast packet radio networks","volume":"52","author":"Chakraborty","year":"2004","journal-title":"IEEE Trans. Commun."},{"key":"ref_13","unstructured":"Rajendran, V., Obraczka, K., and Garcia-Luna-Aceves, J.-J. (, January November). Energy-efficient, collision-free medium access control for wireless sensor networks. Proceedings of Sensys\u201903, Los Angeles, CA, USA."},{"key":"ref_14","unstructured":"Rajendran, V., Garcia-Luna-Aceves, J.J., and Obraczka, K. (, January November). Energy-efficient, application-aware medium access for sensor networks. Proceedings of IEEE MASS 2005, Washington, DC, USA."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ramaswami, R., and Parhi, K. (, January April). Distributed scheduling of broadcasts in a radio network. Proceedings of INFOCOM 1989, Ottawa, Canada.","DOI":"10.1109\/INFCOM.1989.101493"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1023\/A:1012311216333","article-title":"Models and approximation algorithms for channel assignment in radio networks","volume":"7","author":"Krumke","year":"2000","journal-title":"Wirel. Netw."},{"key":"ref_17","unstructured":"Gandham, S., Dawande, M., and Prakash, R. (, January March). Link scheduling in sensor networks: distributed edge coloring revisited. Proceedings of INFOCOM 2005, Miami, FL, USA."},{"key":"ref_18","unstructured":"Garey, M., and Johnson, D. (1979). Computers and Intractability: A Guide to Theory of NP-Completeness, W.H. Freeman and Co."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","article-title":"New methods to color the vertices of a graph","volume":"22","author":"Brelaz","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Hansen, J., Kubale, M., Kuszner, L., and Nadolski, A. (, January August). Distributed largest-first algorithm for graph coloring. Proceedings of EURO-PAR 2004, Pisa, Italy.","DOI":"10.1007\/978-3-540-27866-5_107"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Minet, P., and Mahfoudh, S. (, January August). SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks. Proceedings of IWCMC 2008, IEEE International Wireless Communications and Mobile Computing Conference, Crete Island, Greece.","DOI":"10.1109\/IWCMC.2008.89"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Mahfoudh, S., and Minet, P. (, January March). Performance evaluation of the SERENA algorithm to SchEdule Router Nodes Activity. Proceedings of AINA 2008, Ginowan, Japan.","DOI":"10.1109\/AINA.2008.76"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Gobriel, S., Mosse, D., and Cleric, R. (, January June). TDMA-ASAP: sensor network TDMA scheduling with adaptive slot stealing and parallelism. Proceedings of ICDCS 2009, Montreal, Canada.","DOI":"10.1109\/ICDCS.2009.80"},{"key":"ref_24","unstructured":"Chalhoub, G., Guitton, A., Jacquet, F., Freitas, A., and Misson, M. (, January November). Medium Access Control for a Tree-Based Wireless Sensor Network: Synchronization Management. Proceedings of IFIP Wireless Days, Dubai, United Arab Emirates."},{"key":"ref_25","unstructured":"Zigbee-Alliance (2008). Zigbee Specification."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"4266","DOI":"10.1109\/TIE.2009.2027253","article-title":"Which wireless technology for industrial wireless sensor network? The development of OCARI technology","volume":"56","author":"Dang","year":"2009","journal-title":"IEEE Trans. Ind. Electron."},{"key":"ref_27","first-page":"411","article-title":"Cross-layering in an industrial wireless sensor network: Case study of OCARI","volume":"4","author":"Chalhoub","year":"2009","journal-title":"J. Netw."},{"key":"ref_28","unstructured":"Minet, P., and Mahfoudh, S. (, January December). Energy, bandwidth and time efficiency in data gathering applications. Proceedings of IFIP Wireless Days, Paris, France."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Minet, P., Mahfoudh, S., Chalhoub, G., and Guitton, A. (, January April). Node coloring in a wireless sensor network with unidirectional links and topology changes. Proceedings of IEEE WCNC 2010, Sidney, Australia.","DOI":"10.1109\/WCNC.2010.5506267"}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/2\/4\/469\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:03:33Z","timestamp":1760220213000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/2\/4\/469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,13]]},"references-count":29,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2010,12]]}},"alternative-id":["fi2040469"],"URL":"https:\/\/doi.org\/10.3390\/fi2040469","relation":{},"ISSN":["1999-5903"],"issn-type":[{"type":"electronic","value":"1999-5903"}],"subject":[],"published":{"date-parts":[[2010,10,13]]}}}