| Autor: |
Li, Xianyue, Gao, Xiaofeng, Wu, Weili |
| Zdroj: |
Wireless Algorithms, Systems & Applications (9783540885818); 2008, p162-175, 14p |
| Abstrakt: |
Connected Dominating Set is widely used as virtual backbone in wireless Ad-hoc and sensor networks to improve the performance of transmission and routing protocols. Based on special characteristics of Ad-hoc and sensor networks, we usually use unit disk graph to represent the corresponding geometrical structures, where each node has a unit transmission range and two nodes are said to be adjacent if the distance between them is less than 1. Since every Maximal Independent Set (MIS) is a dominating set and it is easy to construct, we can firstly find a MIS and then connect it into a Connected Dominating Set (CDS). Therefore, the ratio to compare the size of a MIS with a minimum CDS becomes a theoretical upper bound for approximation algorithms to compute CDS. In our paper, with the help of Voronoi diagram and Euler΄s formula, we improved this upper bound, so that improved the approximations based on this relation. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
