An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks

详细信息    查看全文

• 作者：Namsu Ahn (1)
  Sungsoo Park (2)
  
  1. Defense Agency for Technology and Quality ; 420 ; Dongjin-ro ; Jinju-si ; Gyeongsangnam-do ; 660-031 ; Republic of Korea
  2. Department of Industrial and Systems Engineering ; KAIST ; 291 ; Daehak-ro ; Yuseong-gu ; Daejeon-si ; 305-701 ; Republic of Korea
  
• 关键词：Wireless sensor network ; Robust connected dominating set ; Integer programming ; Optimal algorithm
• 刊名：Wireless Networks
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：21
• 期：3
• 页码：783-792
• 全文大小：425 KB
• 参考文献：1. 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鈥?64). ACM, Lausanne, Switzerland.
  2. Basu, P, Redi, J (2004) Movement control algorithms for realization of fault tolerant ad hoc robot networks. IEEE Networks 18: pp. 36-44 CrossRef
  3. Bertsimas, D, Tsitsiklis, JN (1997) Introduction to Linear Optimization. Athena Scientific, Belmont
  4. Blum, J, Ding, M, Thaeler, A, Cheng, X (2004) Connected dominating set in sensor networks and MANETs, handbook of combinatorial optimization. Kluwer Acacemic Publishers, Massachusetts
  5. Bondy, JA, Murty, USR (2008) Graph Theory. Springer, Berlin
  6. 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鈥?19). ACM SIGMOBILE, Urbana-Champaign, Illinois.
  7. Dai, F, Wu, J (2006) On Constructing k-Connected k-Dominating Set in Wireless Network. J. Parallel Distr. Com. 66: pp. 947-958 CrossRef
  8. Garey, MR, Johnson, DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco
  9. Guha, S, Khuller, S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20: pp. 374-387 CrossRef
  10. Grotschel, M, Lovasz, L, Schrijver, A (1981) The Ellipsoid Method and Its Consequences in Combinatorial Optimization. Combinatorica 1: pp. 169-197 CrossRef
  11. 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鈥?). San Diego, CA.
  12. 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鈥?78). Porquerolles, France.
  13. 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.
  14. Li, Y, Wu, Y, Ai, C, Neyah, R (2012) On the construction of k-connected m-dominating sets in wireless networks. J. Comb. Optim. 23: pp. 118-139 CrossRef
  15. Ni, SY, Tseng, YC, Chen, YS, Sheu, JP (2002) The broadcast storm problem in a mobile ad hoc network. Wirel. Netw. 8: pp. 153-167 CrossRef
  16. Papadimitriou, CH, Steiglitz, K (1998) Combinatorial Optimization. Dover Publications, N.Y.
  17. Ryl, DS, Stojmenovi膰, I, Wu, J Energy-Efficient Backbone Construction, Broadcasting, and Area Coverage in Sensor Networks. In: Stojmenovi膰, I eds. (2005) Handbook of sensor networks. John Wiley & Sons Inc, Hoboken, pp. 343-380
  18. Shang, W, Yao, F, Wan, P, Hu, X (2007) Algorithms for minimum m-Connected k-Dominating Set Problem. Lect. Notes Comput. SC. 4616: pp. 182-190 CrossRef
  19. Shang, W, Yao, F, Wan, P, Hu, X (2008) On minimum m-connected k-dominating set problem in unit disc graphs. J. Comb. Optim. 16: pp. 99-106 CrossRef
  20. 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鈥?772). Anchorage, Alaska.
  21. Stojmenovi膰, I, Wu, J (2005) Mobile ad hoc networking. John Wiley & Sons Inc, Hoboken
  22. Tarjan, R. E. (1972). Depth first search and linear graph algorithms. / SIAM Journal on Computing, / 1(2), 146鈥?60.
  23. Thai, MT, Zhang, N, Tiwari, R, Xu, X (2007) On approximation algorithms of k-connected m-dominating sets in disk graphs. Theor. Comput. SC. 385: pp. 49-59 CrossRef
  24. Thulasiraman, K, Swamy, MNS (1992) Graphs: Theory And Algorithms. Wiley, New York
  25. Tiwari, R, Thai, MT (2012) On Enhancing Fault Tolerance of Virtual Backbone in a Wireless Sensor Network with Unidirectional Links. Sensors: Theory. Algorithms, and Applications 61: pp. 3-18
  26. Wang, F, Thai, MT, Du, DZ (2009) On the construction of 2-connected Virtual Backbone in Wireless Network. IEEE T. Wirel. Commun. 8: pp. 1230-1237 CrossRef
  27. 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鈥?510.
  28. West, DB (2001) Introduction to Graph Theory. Prentice-Hall, Upper Saddle River
  29. 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.
  30. 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鈥?0). ACM SIGMOBILE, May, Hong Kong.
  31. Yu, J, Wang, N, Wang, G, Yu, D (2013) Connected dominating sets in wireless ad hoc and sensor networks - A comprehensive survey. Comput. Commun. 36: pp. 121-134 CrossRef
  32. Zhang, J, Gao, X, Wu, W (2009) Algorithms for connected set cover problem and fault-tolerant connected set cover problem. Theor. Comput. SCI. 410: pp. 812-817 CrossRef
  33. 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鈥?19.
  
• 刊物类别：Computer Science
• 刊物主题：Computer Communication Networks
  Electronic and Computer Engineering
  Business Information Systems
  
• 出版者：Springer Netherlands
• ISSN：1572-8196

文摘

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.