Abstract | ||
---|---|---|
In wireless network, backbone network plays an important role on forwarding data. Further, in order to reduce the delay and save energy, the minimum connected dominating set (MCDS) is an effective way to construct a backbone. However, it is NP-hard to construct the MCDS. In this paper, we propose an efficient centralized algorithm, redundancy connected dominating set (RCDS), to construct a relatively optimal connected dominating set with the economic computation cost of O(Δ2n) Specifically, the local strategy is employed to obtain the maximal independent set (MIS) firstly, and then a virtual backbone network is generated by adding the local joint intermediate nodes in the general graph. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.procs.2015.07.190 | Procedia Computer Science |
Keywords | Field | DocType |
Redundancy Connected dominating set,Backbone network,maximal independent set,Wireless network,General graph | Wireless network,Graph,Computer science,Algorithm,Computer network,Redundancy (engineering),Connected dominating set,Backbone network,Computation,Distributed computing,Maximal independent set | Conference |
Volume | ISSN | Citations |
56 | 1877-0509 | 3 |
PageRank | References | Authors |
0.37 | 11 | 5 |