NDLI: An optimal solution to the MCDS problem for topology construction in wireless sensor networks

Content Provider	IEEE Xplore Digital Library
Author	Wightman, P.M. Fabregasy, A. Labradorz, M.A.
Copyright Year	2010
Description	Author affiliation: Department of Computer Science and Engineering, University of South Florida, Tampa, 33620, USA (Labradorz, M.A.) \|\| Center for Urban Transportation Research, University of South Florida, Tampa, 33620, USA (Fabregasy, A.) \|\| Department of Systems Engineering, Universidad del Norte, Barranquilla, Colombia (Wightman, P.M.)
Abstract	Topology Construction (TC) is a very well-known technique to save energy and extend the lifetime of wireless sensor networks. One common approach to implement TC is to select a small subset of nodes that can accomplish the global objective of the network and put the rest of the nodes in a low energy consumption mode to use their energy in the future. One way to select this subset of nodes is by solving the Minimum Connected Dominating Set problem (MCDS). This paper presents a Mixed Integer Programming (MIP) formulation that finds the optimal solution to this problem. The formulation is proposed as a benchmarking tool to compare the performance of existing and new heuristics that approximate the solution to the same problem. In fact, the paper compares the performance of three well-known CDS-based topology construction protocols versus the MIP-MCDS formulation. The results show that, in terms of the size of the CDS, the distance between the optimal and the approximate solutions increases with the communication radius and the number of nodes. In terms of the solution time, for low density and high node degree topologies the mathematical programming formulation is comparable, and sometimes better, to that of the heuristics. However, in topologies with low node degree and high node density the heuristic solutions outperform the mathematical programming solution.
Starting Page	1
Ending Page	6
File Size	1009299
Page Count	6
File Format	PDF
ISBN	9781424471713
e-ISBN	9781424471737
DOI	10.1109/LATINCOM.2010.5641018
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-09-15
Publisher Place	Colombia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Wireless sensor networks Protocols Network topology Approximation algorithms Topology Approximation methods Equations
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Mathematical Solution to the MCDS Problem for Topology Construction in Wireless Sensor Networks

Optimization Algorithm to Eliminate Solitary Point in the Tree Network

Power control based topology construction for the distributed wireless sensor networks

Hierarchical averaging over wireless sensor networks

Redeployment Problem for Wireless Sensor Networks

Decentralized Algorithms for Operating Coded Wireless Networks

Near-optimal routing for contour detection in wireless sensor networks

CDS-HG: A New Distributed MCDS Approximation Algorithm for Wireless Sensor Networks

An Efficient Localized Chain Construction Scheme for Chain Oriented Wireless Sensor Networks

An optimal solution to the MCDS problem for topology construction in wireless sensor networks

Similar Documents

A Mathematical Solution to the MCDS Problem for Topology Construction in Wireless Sensor Networks

Optimization Algorithm to Eliminate Solitary Point in the Tree Network

Power control based topology construction for the distributed wireless sensor networks

Hierarchical averaging over wireless sensor networks

Redeployment Problem for Wireless Sensor Networks

Decentralized Algorithms for Operating Coded Wireless Networks

Near-optimal routing for contour detection in wireless sensor networks

CDS-HG: A New Distributed MCDS Approximation Algorithm for Wireless Sensor Networks

An Efficient Localized Chain Construction Scheme for Chain Oriented Wireless Sensor Networks

An optimal solution to the MCDS problem for topology construction in wireless sensor networks