An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks | springerprofessional.de Skip to main content
My eLearning
Close search form Enter your search terms
Access for companies
English subNavigationMarker
Javascript needed
Please enable JavaScript on your browser, so that you can use all features of this website.
Back to the search result list
previous article Videocent: a quality-oriented incentive mechani...
next article An energy management method of sensor nodes for...
Swipe to navigate through the articles of this issue
01-04-2015 | Issue 3/2015
An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks
Wireless Networks > Issue 3/2015
Namsu Ahn, Sungsoo Park
» Get access to the full-text
In wireless sensor networks (WSNs), virtual backbone has been proposed as the routing infra-structure and connected dominating set has been widely adopted as virtual backbone. However, since the sensors in WSNs are prone to failures, recent studies suggest that it is also important to maintain a certain degree of redundancy in the backbone. To construct a robust backbone, so called k-connected m-dominating set has been proposed. In this research, we propose an integer programming formulation and an optimal algorithm for the minimum k-connected m-dominating set problem. To the best of our knowledge, this is the first integer programming formulation for the problem, and extensive computational results show that our optimal algorithm is capable of finding a solution within a reasonable amount of time.
Please log in to get access to this content
Log in Register for free
To get access to this content you need the following product:
inform now
go back to reference Alzoubi, K. M., Wan, P. J., & Frieder, O. (2002). Message-optimal connected dominating sets in mobile ad hoc networks. In Proceedings of the 3rd ACM international symposium on mobile ad hoc networking and computing (pp. 157–164). ACM, Lausanne, Switzerland. Alzoubi, K. M., Wan, P. J., & Frieder, O. (2002). Message-optimal connected dominating sets in mobile ad hoc networks. In Proceedings of the 3rd ACM international symposium on mobile ad hoc networking and computing (pp. 157–164). ACM, Lausanne, Switzerland.
go back to reference Basu, P., & Redi, J. (2004). Movement control algorithms for realization of fault tolerant ad hoc robot networks. IEEE Networks, 18, 36–44. CrossRef Basu, P., & Redi, J. (2004). Movement control algorithms for realization of fault tolerant ad hoc robot networks. IEEE Networks, 18, 36–44. CrossRef
go back to reference Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization. Belmont: Athena Scientific. Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization. Belmont: Athena Scientific.
go back to reference Blum, J., Ding, M., Thaeler, A., & Cheng, X. (2004). Connected dominating set in sensor networks and MANETs, handbook of combinatorial optimization. Massachusetts: Kluwer Acacemic Publishers. Blum, J., Ding, M., Thaeler, A., & Cheng, X. (2004). Connected dominating set in sensor networks and MANETs, handbook of combinatorial optimization. Massachusetts: Kluwer Acacemic Publishers.
go back to reference Bondy, J. A., & Murty, U. S. R. (2008). Graph theory. Berlin: Springer. MATH Bondy, J. A., & Murty, U. S. R. (2008). Graph theory. Berlin: Springer. MATH
go back to reference Bredin, J. L., Demaine, E. D., Hajiaghayi, M., & Rus, D. (2005). Deploying sensor networks with guaranteed capacity and fault tolerance. In Proceedings of the 6th ACM international symposium on mobile ad hoc networking and computing (pp. 309–319). ACM SIGMOBILE, Urbana-Champaign, Illinois. Bredin, J. L., Demaine, E. D., Hajiaghayi, M., & Rus, D. (2005). Deploying sensor networks with guaranteed capacity and fault tolerance. In Proceedings of the 6th ACM international symposium on mobile ad hoc networking and computing (pp. 309–319). ACM SIGMOBILE, Urbana-Champaign, Illinois.
go back to reference Dai, F., & Wu, J. (2006). On constructing k-connected k-dominating set in wireless network. Journal of Parallel and Distributed Computing, 66, 947–958. CrossRefMATH Dai, F., & Wu, J. (2006). On constructing k-connected k-dominating set in wireless network. Journal of Parallel and Distributed Computing, 66, 947–958. CrossRefMATH
go back to reference Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W. H. Freeman and Company. MATH Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W. H. Freeman and Company. MATH
go back to reference Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20, 374–387. CrossRefMATHMathSciNet Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20, 374–387. CrossRefMATHMathSciNet
go back to reference Grotschel, M., Lovasz, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169–197. CrossRefMathSciNet Grotschel, M., Lovasz, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169–197. CrossRefMathSciNet
go back to reference Kim, D., Wang, W., Li, X., Zhang, Z., & Wu, W. (2010). A new constant factor approximation for computing 3-connected m-dominating sets in homogeneous wireless networks. In INFOCOM, IEEE (pp. 1–9). San Diego, CA. Kim, D., Wang, W., Li, X., Zhang, Z., & Wu, W. (2010). A new constant factor approximation for computing 3-connected m-dominating sets in homogeneous wireless networks. In INFOCOM, IEEE (pp. 1–9). San Diego, CA.
go back to reference Koskinen, H., & Karvo, J. (2005). On improving connectivity of static ad-hoc networks by adding nodes, 4th annual Mediterranean workshop on ad hoc network. IEEE Communications Society (pp. 169–178). Porquerolles, France. Koskinen, H., & Karvo, J. (2005). On improving connectivity of static ad-hoc networks by adding nodes, 4th annual Mediterranean workshop on ad hoc network. IEEE Communications Society (pp. 169–178). Porquerolles, France.
go back to reference Kuhn, F., Moscibroda, T., & Wattenhofer, R. (2006). Fault-tolerant clustering in ad hoc and sensor networks. In 26th international conference on distributed computing systems. IEEE Computer Society, Lisboa, Portugal. Kuhn, F., Moscibroda, T., & Wattenhofer, R. (2006). Fault-tolerant clustering in ad hoc and sensor networks. In 26th international conference on distributed computing systems. IEEE Computer Society, Lisboa, Portugal.
go back to reference Li, Y., Wu, Y., Ai, C., & Neyah, R. (2012). On the construction of k-connected m-dominating sets in wireless networks. Journal of Combinatorial Optimization, 23, 118–139. CrossRefMATHMathSciNet Li, Y., Wu, Y., Ai, C., & Neyah, R. (2012). On the construction of k-connected m-dominating sets in wireless networks. Journal of Combinatorial Optimization, 23, 118–139. CrossRefMATHMathSciNet
go back to reference Ni, S. Y., Tseng, Y. C., Chen, Y. S., & Sheu, J. P. (2002). The broadcast storm problem in a mobile ad hoc network. Wireless Networks, 8, 153–167. CrossRefMATH Ni, S. Y., Tseng, Y. C., Chen, Y. S., & Sheu, J. P. (2002). The broadcast storm problem in a mobile ad hoc network. Wireless Networks, 8, 153–167. CrossRefMATH
go back to reference Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial pptimization. Mineola, NY: Dover Publications. MATH Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial pptimization. Mineola, NY: Dover Publications. MATH
go back to reference Ryl, D. S., Stojmenović, I., & Wu, J. (2005). Energy-efficient backbone construction, broadcasting, and area coverage in sensor networks. In I. Stojmenović (Ed.), Handbook of sensor networks (pp. 343–380). Hoboken: Wiley. Ryl, D. S., Stojmenović, I., & Wu, J. (2005). Energy-efficient backbone construction, broadcasting, and area coverage in sensor networks. In I. Stojmenović (Ed.), Handbook of sensor networks (pp. 343–380). Hoboken: Wiley.
go back to reference Shang, W., Yao, F., Wan, P., & Hu, X. (2007). Algorithms for minimum m-connected k-dominating set problem. Lecture Notes in Computer Science, 4616, 182–190. CrossRefMathSciNet Shang, W., Yao, F., Wan, P., & Hu, X. (2007). Algorithms for minimum m-connected k-dominating set problem. Lecture Notes in Computer Science, 4616, 182–190. CrossRefMathSciNet
go back to reference Shang, W., Yao, F., Wan, P., & Hu, X. (2008). On minimum m-connected k-dominating set problem in unit disc graphs. Journal of Combinatorial Optimization, 16, 99–106. CrossRefMATHMathSciNet Shang, W., Yao, F., Wan, P., & Hu, X. (2008). On minimum m-connected k-dominating set problem in unit disc graphs. Journal of Combinatorial Optimization, 16, 99–106. CrossRefMATHMathSciNet
go back to reference Sinha, P., Sivakumar, R., & Bharghavan, V. (2001). Enhancing ad hoc routing with dynamic virtual infrastructures. IN 20th annual joint conference of the IEEE computer and communications societies. Technical Committees on Computer Communications (TCCC) of the Societies (Vol. 3, pp. 1763–1772). Anchorage, Alaska. Sinha, P., Sivakumar, R., & Bharghavan, V. (2001). Enhancing ad hoc routing with dynamic virtual infrastructures. IN 20th annual joint conference of the IEEE computer and communications societies. Technical Committees on Computer Communications (TCCC) of the Societies (Vol. 3, pp. 1763–1772). Anchorage, Alaska.
go back to reference Stojmenović, I., & Wu, J. (2005). Mobile ad hoc networking. Hoboken: Wiley Stojmenović, I., & Wu, J. (2005). Mobile ad hoc networking. Hoboken: Wiley
go back to reference Tarjan, R. E. (1972). Depth first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160. Tarjan, R. E. (1972). Depth first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160.
go back to reference Thai, M. T., Zhang, N., Tiwari, R., & Xu, X. (2007). On approximation algorithms of k-connected m-dominating sets in disk graphs. Theory of Computation Sc, 385, 49–59. CrossRefMATHMathSciNet Thai, M. T., Zhang, N., Tiwari, R., & Xu, X. (2007). On approximation algorithms of k-connected m-dominating sets in disk graphs. Theory of Computation Sc, 385, 49–59. CrossRefMATHMathSciNet
go back to reference Thulasiraman, K., & Swamy, M. N. S. (1992). Graphs: Theory and algorithms. New York: Wiley. MATH Thulasiraman, K., & Swamy, M. N. S. (1992). Graphs: Theory and algorithms. New York: Wiley. MATH
go back to reference Tiwari, R., & Thai, M. T. (2012). On enhancing fault tolerance of virtual backbone in a wireless sensor network with unidirectional links. Sensors: Theory, Algorithms, and Applications, 61, 3–18. Tiwari, R., & Thai, M. T. (2012). On enhancing fault tolerance of virtual backbone in a wireless sensor network with unidirectional links. Sensors: Theory, Algorithms, and Applications, 61, 3–18.
go back to reference Wang, F., Thai, M. T., & Du, D. Z. (2009). On the construction of 2-connected virtual backbone in wireless network. IEEE Transactions on Wireless Communications, 8, 1230–1237. CrossRef Wang, F., Thai, M. T., & Du, D. Z. (2009). On the construction of 2-connected virtual backbone in wireless network. IEEE Transactions on Wireless Communications, 8, 1230–1237. CrossRef
go back to reference Wang, W., Kim, D., An, M. K., Gao, W., Li, X., Zhang, Z., & Wu, W. (2012). On construction of quality fault-tolerant virtual backbone in wireless networks. Networking, IEEE/ACM Transactions, 21(5), 1499–1510. Wang, W., Kim, D., An, M. K., Gao, W., Li, X., Zhang, Z., & Wu, W. (2012). On construction of quality fault-tolerant virtual backbone in wireless networks. Networking, IEEE/ACM Transactions, 21(5), 1499–1510.
go back to reference West, D. B. (2001). Introduction to graph theory. Upper Saddle River: Prentice-Hall. West, D. B. (2001). Introduction to graph theory. Upper Saddle River: Prentice-Hall.
go back to reference Wu, Y., Wang, F., Thai, M. T., & Li, Y. (2007). Constructing k-connected m-dominating sets in wireless sensor networks. In Military communications conference. Orlando, FL. Wu, Y., Wang, F., Thai, M. T., & Li, Y. (2007). Constructing k-connected m-dominating sets in wireless sensor networks. In Military communications conference. Orlando, FL.
go back to reference Wu, Y., & Li, Y. (2008) Construction algorithms for k-connected m-dominating sets in wireless sensor networks. In 9th ACM international symposium on mobile ad hoc networking and computing (pp. 83–90). ACM SIGMOBILE, May, Hong Kong. Wu, Y., & Li, Y. (2008) Construction algorithms for k-connected m-dominating sets in wireless sensor networks. In 9th ACM international symposium on mobile ad hoc networking and computing (pp. 83–90). ACM SIGMOBILE, May, Hong Kong.
go back to reference Yu, J., Wang, N., Wang, G., & Yu, D. (2013). Connected dominating sets in wireless ad hoc and sensor networks—A comprehensive survey. Computer Communications, 36, 121–134. CrossRef Yu, J., Wang, N., Wang, G., & Yu, D. (2013). Connected dominating sets in wireless ad hoc and sensor networks—A comprehensive survey. Computer Communications, 36, 121–134. CrossRef
go back to reference Zhang, J., Gao, X., & Wu, W. (2009). Algorithms for connected set cover problem and fault-tolerant connected set cover problem. Theoretical Computer Science, 410, 812–817. CrossRefMATHMathSciNet Zhang, J., Gao, X., & Wu, W. (2009). Algorithms for connected set cover problem and fault-tolerant connected set cover problem. Theoretical Computer Science, 410, 812–817. CrossRefMATHMathSciNet
go back to reference Zhou, J., Zhang, Z., Wu, W., & Xing, K. (2014). A greedy algorithm for the fault-tolerant connected dominating set in a general graph. Journal of Combinatorial Optimization, 28(1), 310–319. Zhou, J., Zhang, Z., Wu, W., & Xing, K. (2014). A greedy algorithm for the fault-tolerant connected dominating set in a general graph. Journal of Combinatorial Optimization, 28(1), 310–319.
Namsu Ahn
Sungsoo Park
Wireless Networks The Journal of Mobile Communication, Computation and Information
Other articles of this Issue 3/2015
Go to the issue
A revocable attribute based data sharing scheme resilient to DoS attacks in smart grid
Inter-domain mobility support in Proxy Mobile IPv6 using overlap function of mobile access gateway
Exploring an energy-efficient DTN framework supporting disaster management services in post disaster relief operation
A new quality of service aware multi-channel multi-interface link layer protocol for wireless mesh networks
Upper bounds for the min–max and min–sum cost online problems in wireless ad hoc networks
Videocent: a quality-oriented incentive mechanism for video delivery in opportunistic networks
Legal Information: