A study on algorithms for establishing smaller connected dominating sets in wireless ad hoc networks
| Autor: | Hung-Yuan Tsai, 蔡宏源 |
|---|---|
| Rok vydání: | 2008 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 96 Given a graph G = (V, E) and a subset M of V. If any element v in set M either belongs to M or is connected to at least one element of M, then M is called a dominating set of V. A dominating set is connected if there exists a path between any two nodes in the set and the path only consists of the nodes in the set. A connected dominating set (CDS) is a dominating set that is connected. The size of a CDS is the number of nodes it contains. A CDS may constitute a virtual backbone in a wireless ad hoc network (WAN). One of effective approaches to implementing broadcasting/routing in a WAN is to establish a CDS. In general, through a connected dominating set, broadcasting/routing will become more efficient and adaptable to the unpredictable topological changes of WAN. The overhead of a CDS-based broadcasting/routing scheme is in direct proportion to the size of CDS and the complexity of the associated CDS-forming algorithm. In this thesis, we propose six efficient algorithms for establishing smaller CDS in WANs. These proposed algorithms are operated in a distributed manner and only need 2-hop neighborhood information. Furthermore, the resultant CDS size is related to the complexity of the used CDS-forming algorithm. That is, the higher the complexity of a CDS-forming algorithm, the smaller the size of its CDS. Computer simulations show that, compared with other known CDS-forming algorithms, our algorithms can generate smaller CDSs or have less time complexities. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|