微信服务号

微信订阅号

2025-5-11- 8
Home > Archive>Volume 21, Issue 6, 2010 >1416-1425
PDF HTML XML Export Cite reminder
Distributed Virtue Backbone Network Algorithm Based on Topology Characteristic
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [29]
    • |
  • Related [20]
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    Because finding a minimum connected domination set (MCDS) for a general connected network is NP-complete, a topology-aware heuristic algorithm is proposed in this paper whose correctness is proved. By taking advantage of the topology characteristic of nodes, the algorithm can reduce the blindness in the process of selecting dominating nodes, and form a smaller CDS (connected domination set) based on 2-hop local information, consequently obtain a virtue backbone network with the CDS. The simulation results show that the algorithm is superior to other distributed CDS algorithms, and closer to minimum CDS.

    Reference
    [1] Blum J, Ding M, Thaeler A, Cheng XZ. Connected dominating set in sensor networks and MANETs. Handbook of Combinatorial Optimization, 2004,5:329-369. [doi: 10.1007/b102533]
    [2] Sun LM, Li JZ, Chen Y, Zhu HS. Wireless Sensor Networks. Beijing:Tsinghua University Press, 2005. (in Chinese).
    [3] Chen B, Jamieson K, Balakrishnan H, Morris R. Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. ACM Wireless Networks Journal, 2002,8(5):481-494. [doi: 10.1023/A:1016542229220]
    [4] Deb B, Bhatnagar S, Nath B. Multi-Resolution state retrieval in sensor networks. In: Proc. of the IEEE ICC Workshop on Sensor Network Protocols and Applications. 2003. 19-29.
    [5] An B, Papavassiliou S. A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks. Int’l Journal of Network Management, 2001,11:387-395. [doi: 10.1002/nem.415]
    [6] Basagni S, Mastrogiovanni M, Panconesi A, Petrioli C. Localized protocols for ad hoc clustering and backbone formation: A performance comparison. IEEE Trans. on Parallel and Distributed Systems, 2006,17(4):292-306. [doi: 10.1109/TPDS.2006.52]
    [7] Gupta H, Navda V, Das SR, Chowdhary V. Efficient gathering of correlated data in sensor networks. ACM Trans. on Sensor Networks, 2008,4(1):1-31.
    [8] Shaikh J, Solano J, Stojmenovic I, Wu J. New metrics for dominating set based energy efficient activity scheduling in ad hoc networks. In: Proc. of the IEEE Conf. on Local Computer Networks (LCN 2003). 2003. 726-735.
    [9] Das B, Sivakumar R, Bhargavan V. Routing in ad hoc networks using a spine. In: Proc. of the 6th IEEE Int’l Conf. on Computers and Communications Networks (ICCCN 1997). 1997. 34-39.
    [10] Wu J. Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links. IEEE Trans. on Parallel and Distributed Systems, 2002,9(3):189-200.
    [11] Wu J, Li H. On calculating connected dominating sets for efficient routing in ad hoc wireless networks. In: Proc. of the 3rd Int’l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm. 1999. 7-14.
    [12] El-Hajj W, Trabelsi Z, Kountanis D. Fast distributed dominating set based routing in large scale MANETs. Computer Communications, 2007,30:2880-2891. [doi: 10.1016/j.comcom.2007.03.011]
    [13] Li J, Foh CH, Andrew LLH, Zukerman M. Sizes of minimum connected dominating sets of a class of wireless sensor networks. In: Proc. of the ICC 2008. 2008. 332-336.
    [14] Ahmed DT, Shirmohammadi S, Saddik AE. A dominating set based peer-to-peer protocol for real-time multi-source collaboration. In: Proc. of the 16th IEEE Int’l Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE 2007). 2007. 119-124.
    [15] Shaikot SH, Sarangan V. Energy aware routing in high capacity overlays in wireless sensor networks. In: Proc. of the IEEE/ACS Int’l Conf. on Computer Systems and Applications (AICCSA 2008). 2008. 276-283.
    [16] Acharya T, Chattopadhyay S, Roy R. Multiple disjoint power aware minimum connected dominating sets for efficient routing in wireless ad hoc network. In: Proc. of the Int’l Conf. on Information and Communication Technology (ICICT 2007). 2007. 336-340.
    [17] Teymoori P, Yazdani N. Local reconstruction of virtual backbone to support mobility in wireless ad hoc networks. In: Proc. of the Int’l Symp. on Telecommunications (IST 2008). 2008. 382-387.
    [18] Mao YC, Feng GF, Chen LJ, Chen DX. A location-Independent connected coverage protocol for wireless sensor networks. Journal of Software, 2007,18(7):1672-1684 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/18/1672.htm [doi: 10.1360/jos181672]
    [19] Chvatal V. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 1979,4(3):233-235.
    [20] Guha S, Khuller S. Approximation algorithms for connected dominating sets. Algorithmica, 1998,20(4):374-387. [doi: 10.1007/ PL00009201]
    [21] Das B, Bharghavan V., Routing in ad-hoc networks using minimum connected dominating sets. In: Proc. of the IEEE Int’l Conf. on Communications (ICC 1997). 1997 376-380.
    [22] Alzoubi KM, Wan PJ, Frieder O. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, 2002,4(1):1-8.
    [23] Alzoubi KM, Wan PJ, Frieder O. Message-Optimal connected dominating sets in mobile ad hoc networks. In: Proc. of the 3rd ACM international symposium on Mobile ad hoc networking and computing (MOBIHOC 2002). 2002. 157-164.
    [24] Adjih C, Jacquet P, Viennot L. Computing connected dominated sets with multipoint relays. Ad Hoc & Sensor Networks, 2005,1: 27-39.
    [25] Dai F, Wu J. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. on Parallel and Distributed Systems, 2004,15(10):908-920. [doi: 10.1109/TPDS.2004.48]
    [26] Wu J, Lou W, Dai F. Extended multipoint relays to determine connected dominating sets in MANETs. IEEE Trans. on Computers, 2006,55(3):334-347. [doi: 10.1109/TC.2006.40]
    [27] Dimokas N, Katsaros D, Manolopoulos Y. Node clustering in wireless sensor networks by considering structural characteristics of the network graph. In: Proc. of the 4th Int’l Conf. on Information Technology (ITNG 2007). 2007. 122-127.
    附中文参考文献: [2] 孙利民,李建中,陈渝,朱红松.无线传感器网络.北京:清华大学出版社,2005.
    [18] 毛莺池,冯国富,陈力军,陈道蓄.与位置无关的无线传感器网络连通性覆盖协议.软件学报,2007,18(7):1672-1684. http://www.jos. org.cn/1000-9825/18/1672.htm [doi: 10.1360/jos181672]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

解文斌,李 佳,鲜 明,陈永光.基于拓扑特性的分布式虚拟骨干网算法.软件学报,2010,21(6):1416-1425

Copy
Share
Article Metrics
  • Abstract:4890
  • PDF: 6267
  • HTML: 0
  • Cited by: 0
History
  • Revised:January 15,2009
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2043741Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063