Abstract
The communication problem is to select a minimal set of placed sensor devices in a service area so that the entire service area is accessible by the minimal set of sensors. Finding the minimal set of sensors is modeled as a vertex-cover problem, where the vertex-cover set facilitates the communications between the sensors in a multi-hop fashion keeping in mind the limited communication range and battery lifespan of all sensors. The vertex-cover is a subset of the coverage set of sensors; therefore, we transform the search space from a continuous domain into a discrete domain. We encoded the vertex-cover problem into the evolutionary domain, where the objective function is to select a minimal set of sensors out of the coverage sensors to act as the vertex-cover set so that its communication range covers all the coverage sensors. The experimental results demonstrate the feasibility of our evolutionary approach in finding minimal vertex cover set, which is less than 37% of total sensors used as communication sensors, in under 14 seconds with 100% coverage of the sensor nodes in wireless sensor network.
Chapter PDF
Similar content being viewed by others
Keywords
References
Wong, J., Neve, M., Sowerby, K.: Optimisation strategy for wireless communications system planning using linear programming. Electronic Letters 37, 1086–1087 (2001)
Yangyang, Z., Chunlin, J., Ping, Y., Manlin, L., Chaojin, W., Guangxing, W.: Particle Swarm Optimization for Base Station Placement in mobile communication. In: IEEE International Conference on Networking, Sensing and Control, Taipei, Taiwan, vol. 1, pp. 428–432 (2004)
Hurley, S., Kapp-Rawsley, R.: Towards automatic cell planning. In: The 11th IEEE International Conference on Personal, Indoor and Mobile Radio Communications, London, pp. 1583–1588 (2000)
Ishizuka, M., Aida, M.: Performance Study of Node Placement in Sensor Networks. In: IEEE International Conference on Distributed Computing Systems 2004 Workshops Assurance in Distributed Systems and Networks, Tokyo, Japan, pp. 598–603 (2004)
Han, J.K., Park, B.S., Choi, Y.S., Park, H.K.: Genetic approach with a new representation for base station placement in mobile communications. In: The proceedings of the 54th IEEE Conference on Vehicular Technology, vol. 4, pp. 2703–2707 (2001)
Butterworth, K.S., Sowerby, K.W., Williamson, A.G.: Base station placement for in-building mobile communication systems to yield high capacity and efficiency. IEEE Transactions on Communications 48, 658–669 (2000)
Takanashi, H., Rappaport, S.S.: Dynamic base station selection for personal communication systems with distributed control schemes. In: The proceedings of the 47th IEEE Conference on Vehicular Technology, vol. 3, pp. 1787–1791 (1997)
Patel, M., Chandrasekaran, R., Venkatesan, S.: Energy efficient sensor, relay and base station placements for coverage, connectivity and routing. In: The 24th IEEE International Performance, Computing, and Communications Conference (IPCCC), pp. 581–586 (2005)
Rodrigues, R.C., Mateus, G.R., Loureiro, A.: Optimal base station placement and fixed channel assignment applied to wireless local area network projects. In: IEEE International Conference on Networks, pp. 186–192 (1999)
Wright, M.H.: Optimization Methods for Base Station Placement. In: Wireless Applications the proceedings of Vehicular Technology Conference (1998)
Park, B.-S., Park, H.-K., Yook, J.-G.: The Determination of Base Station Placement and Transmit Power in an Inhomogeneous Traffic Distribution for Radio Network Planning. In: The proceedings of the 56th IEEE Conference on Vehicular Technology, vol. 4, pp. 2051–2055 (2002)
Yang, S.-T., Ephremides, A.: Optimal Network Design: the Base Station Placement Problem. In: The proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, USA, vol. 3, pp. 2381–2386 (1997)
Huang, X., Behr, U., Wiesbeck, W.: A New Approach to Automatic Base Station Placement in Mobile Network. In: The International Zurich Seminar on Broadband Communications, pp. 301–306 (2000)
Lindström, M.: Base Station Placement in Asymmetric TDD Mode Systems in a Manhattan Environment. In: The proceedings of the 59th IEEE Conference on Vehicular Technology, vol. 4, pp. 1968–1972 (2004)
Huang, X., Behr, U., Wiesbeck, W.: Automatic base station placement and dimensioning for mobile network planning. In: The proceedings of IEEE 52nd Vehicular Technology Conference (VTC2000-Fall), Boston, Massachusetts, USA, vol. 4, pp. 1544–1549 (2000)
Fruhwirth, T., Brisset, P.: Placing base stations in wireless indoor communication networks. IEEE Intelligent Systems 15, 49–53 (2000)
Habib, S.: Modeling the Coverage Problem in Wireless Sensor Networks as Floorplanning and Placement Problems. In: The proceedings of the 6th IASTED International Multi-Conference on Wireless and Optical Communications (Wireless Sensor Networks), Banff, AB, Canada (2006)
Dasgupta, K., Kukreja, M., Kalpakis, K.: Topology-Aware Placement and Role Assignment for Energy-Efficient Information Gathering in Sensor Networks. In: The proceedings of Eighth IEEE International Symposium on Computers and Communication, Turkey, vol. 1, pp. 341–348 (2003)
Quintao, F.P., Mateus, G.R., Nakamura, F.G.: An Evolutive Approach for the Coverage Problem in Wireless Sensor Network. In: The Proceeding of 24th Brazilian Computer Society Congress (2004)
Quintao, F.P., Nakamura, F.G., Mateus, G.R.: Evolutionary Algorithm for the Dynamic Coverage Problem Applied to Wireless Sensor Networks Design. In: The proceedings of IEEE Congress on Evolutionary Computations, Edinburgh, UK (2005)
Crossbow Technology Inc.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Safar, M., Habib, S. (2007). Hard Constrained Vertex-Cover Communication Algorithm for WSN. In: Kuo, TW., Sha, E., Guo, M., Yang, L.T., Shao, Z. (eds) Embedded and Ubiquitous Computing. EUC 2007. Lecture Notes in Computer Science, vol 4808. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77092-3_55
Download citation
DOI: https://doi.org/10.1007/978-3-540-77092-3_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77091-6
Online ISBN: 978-3-540-77092-3
eBook Packages: Computer ScienceComputer Science (R0)