research-article

VCM: the vector-based coloring method for grid wireless ad hoc and sensor networks

Authors:

Ichrak Amdouni,

Pascale MinetAuthors Info & Claims

MSWiM '12: Proceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems

Pages 213 - 222

https://doi.org/10.1145/2387238.2387275

Published: 21 October 2012 Publication History

Abstract

Graph coloring is used in wireless ad hoc and sensor networks to optimize network resources: bandwidth and energy. Nodes access the medium according to their color. It is the responsibility of the coloring algorithm to ensure that interfering nodes do not have the same color. In this paper, we focus on wireless ad hoc and sensor networks with grid topologies. How does a coloring algorithm take advantage of the regularity of grid topology to provide an optimal periodic coloring, that is a coloring with the minimum number of colors? We propose the Vector-Based Coloring Method, denoted VCM, a new method that is able to provide an optimal periodic coloring for any radio transmission range and for any h-hop coloring, he1. In h-hop coloring, no nodes that are p-hop away, with 1 d p d h use the same color. This method consists in determining where a color can be reproduced in the grid without creating interferences while minimizing the number of colors used. We compare the number of colors provided by VCM with the number of colors obtained by a distributed coloring algorithm with line and column priority assignments. Finally, we discuss the applicability of this method to a real wireless network.

References

[1]

Garey, M.; Johnson, D., Computers and intractability: a guide to theory of NP-completeness, W.H. Freeman, San Francisco, California, 1979.

Digital Library

[2]

McCormick, S. T., Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem, Math. Programming, v26, pp. 153--171, 1983.

Digital Library

[3]

Amdouni, I.; Minet, P.; Adjih, C., Node coloring for dense wireless sensor networks, INRIA Research Report 7588, Paris-Rocquencourt, France, March 2011.

[4]

Baumgartner, T.; Fekete, S. P.; Kamphans T.; Kröller A., Pagel, M. Hallway Monitoring: Distributed Data Processing with Wireless Sensor Networks, REALWSN, December 2010.

Digital Library

[5]

Chakrabarty, K.; Iyengar S. S.; Qi H. R. and Cho E., Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks, IEEE Transactions on Computers, Vol. 51, No. 12, 2002, pp. 1448--1453.

Digital Library

[6]

McCulloch, J.; Mccarthy, P.; Siddeswara M. Guru; Wei, P.; Hugo, D.; Terhorst, A.; Wireless sensor network deployment for water use efficiency in irrigation, Proc. of the workshop on Real-world wireless sensor networks, March 2008.

Digital Library

[7]

J.C. Bermond, F. Havet, F. Huc, C. Linhares-Sales, Improper colouring of weighted grid and hexagonal graphs, Discrete Mathematics, Algorithms and Applications, 2(3):395--411, 2010.

[8]

Cargiannis, I.; Fishkin A.; Kaklamanis C.; Papaioannou E., A tight bound for online coloring of disk graphs, Theoretical Computer Science, 384, 2007.

Digital Library

[9]

Kierstead H. A., Qin J., Coloring interval graphs with First-Fit, Discrete Math, Vol. 144, pp. 47--57, Sept. 1995.

Digital Library

[10]

Riihijarvi J., Petrova M., Mahonen P., Frequency Allocation for WLANs Using Colouring Techniques, Journal of Ad Hoc and Sensor Wireless Networks, Vol. 3, pp. 121--139, 2007.

[11]

Even G., Lotker Z., Ron D., Smorodinsky S., Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks, SIAM J. Comput, Vol. 33, No. 1, pp 94--136, 2004.

Digital Library

[12]

Shakhar Smorodinsky, Conflict-Free Coloring and its Applications, CoRR abs/1005.3616, 2010.

[13]

Schneider, J. and Wattenhofer R., Coloring unstructured wireless multi-hop networks, The 28th ACM symposium on Principles of distributed computing, PODC'09, USA, 2009.

Digital Library

[14]

Rajendran, V.; Obraczka, K.; Garcia-Luna-Aceves, J.-J., Energy-efficient, collision-free medium access control for wireless sensor networks, Sensys'03, Los Angeles, California, November 2003.

Digital Library

[15]

Rajendran, V.; Garcia-Luna-Aceves, J.J.; Obraczka, K., Energy-efficient, application-aware medium access for sensor networks, IEEE MASS 2005, Washington, November 2005.

[16]

Rhee, I.; Warrier, A.; Aia, M.; Min, J., Z-MAC: a hybrid MAC for wireless sensor networks, SenSys'05, San Diego, California, November 2005.

Digital Library

[17]

Rhee, I.; Warrier, A.; Xu, L., Randomized dining philosophers to TDMA scheduling in wireless sensor networks, Technical Report TR-2005-21, Dept of Computer Science, North Carolina State University, April 2005.

[18]

Gobriel, S.; Mosse, D.; Cleric, R., TDMA-ASAP: sensor network TDMA scheduling with adaptive slot stealing and parallelism, ICDCS 2009, Montreal, Canada, June 2009.

Digital Library

[19]

Lee, W. L.; Datta A.; Cardell-Oliver, R., FlexiTP: a flexible-schedule-based TDMA protocol for fault-tolerant and energy-efficient wireless sensor networks, IEEE Transactions on Parallel and Distributed Systems, vol. 19, 6, June 2008.

Digital Library

[20]

Vector-Based Coloring Method page, http://hipercom.inria.fr/SensorNet/VCM/, INRIA, 2011.

[21]

WulLbben, D.; Seethaler, D.; Jalden, J.; Matz, G., Lattice Reduction, A survey with applications in wireless communications, IEEE Signal Processing Magazine, vol. 29, May 2011.

[22]

Vallée, B.; Vera, A.; Lattice reduction in two dimensions: analyses under realistic probabilistic models, Proceedings of AofA'07.

[23]

Minet, P.; Mahfoudh, S., SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks, IWCMC 2008, IEEE International Wireless Communications and Mobile Computing Conference, Crete Island, Greece, August 2008.

[24]

Thue, A., Über die dichteste Zusammenstellung von kongruenten Kreisen in einer Ebene, Norske Vid. Selsk. Skr. No.1 (1910), 1--9.

[25]

Tóth, L.F.; Über die dichteste Kugellagerung, Math. Z. 48 (1943), 676--684.

[26]

Amdouni, I.; Adjih, C.; Minet, P.; On the Coloring of Grid Wireless Sensor Networks: the Vector-Based Coloring Method, Inria Research Report, RR-7756, September 2011.

Cited By

Amdouni IAdjih CMinet PPlesse T(2016)Delay analysis of STDMA in grid wireless sensor networks2016 International Conference on Military Communications and Information Systems (ICMCIS)10.1109/ICMCIS.2016.7496580(1-8)Online publication date: May-2016
https://doi.org/10.1109/ICMCIS.2016.7496580
Amdouni IAdjih CMinet P(2014)Delay and Energy-Efficient STDMA for Grid Wireless Sensor NetworksProceedings of the 2014 IEEE 11th International Conference on Mobile Ad Hoc and Sensor Systems10.1109/MASS.2014.83(262-266)Online publication date: 28-Oct-2014
https://dl.acm.org/doi/10.1109/MASS.2014.83

Index Terms

VCM: the vector-based coloring method for grid wireless ad hoc and sensor networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Constructing efficient rotating backbones in wireless sensor networks using graph coloring

For a dense deployment of sensors modeled as a random geometric graph of minimum degree @d, we introduce efficient algorithms both centralized and distributed for selecting (@d+1) backbones with disjoint node sets that are each independent and fully (or ...
Minimum order of graphs with given coloring parameters

A complete k -coloring of a graph G = ( V , E ) is an assignment : V { 1 , , k } of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively ...
Energy-Aware Data Aggregation for Grid-Based Wireless Sensor Networks with a Mobile Sink

Wireless sensor networks (WSNs) are made up of many small and highly sensitive nodes that have the ability to react quickly. In WSNs, sink mobility brings new challenges to large-scale sensor networks. Almost all of the energy-aware routing protocols ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MSWiM '12: Proceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems

October 2012

428 pages

ISBN:9781450316286

DOI:10.1145/2387238

General Chair:
Albert Zomaya
University of Sydney, Australia
,
Program Chairs:
Bjorn Landfeldt
Lund University, Sweden
,
Ravi Prakash
University of Texas at Austin, USA

Copyright © 2012 ACM.

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]

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MSWiM '12

Sponsor:

SIGSIM

MSWiM '12: The 15th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

October 21 - 25, 2012

Paphos, Cyprus

Acceptance Rates

Overall Acceptance Rate 398 of 1,577 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
97
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Amdouni IAdjih CMinet PPlesse T(2016)Delay analysis of STDMA in grid wireless sensor networks2016 International Conference on Military Communications and Information Systems (ICMCIS)10.1109/ICMCIS.2016.7496580(1-8)Online publication date: May-2016
https://doi.org/10.1109/ICMCIS.2016.7496580
Amdouni IAdjih CMinet P(2014)Delay and Energy-Efficient STDMA for Grid Wireless Sensor NetworksProceedings of the 2014 IEEE 11th International Conference on Mobile Ad Hoc and Sensor Systems10.1109/MASS.2014.83(262-266)Online publication date: 28-Oct-2014
https://dl.acm.org/doi/10.1109/MASS.2014.83

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents