Paper Info

Title | ||
---|---|---|

Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks |

Abstract | ||
---|---|---|

The paper studies the problem of computing a minimal energy cost range assignment in a ad-hoe wireless network which allows a station s to perform a broadcast operation in at most h hops. The general version of the problem (i.e., when transmission costs are arbitrary) is known to be log-APX hard even for h = 2. The current paper considers the well-studied real case in which n stations are located on the plane and the cost to transmit from station i to station j is proportional to the alpha-th power of the distance between station i and j, where alpha is any positive constant. A polynomial-time algorithm is presented for finding an optimal range assignment to perform a 2-hop broadcast from a given source station. The algorithm relies on dynamic programming and operates in (worst-case) time O(n(7)). Then, a polynomial-time approximation scheme (PTAS) is provided for the above problem for any fixed h greater than or equal to 1. For fixed h greater than or equal to 1 and epsilon > 0, the PTAS has time complexity O(n(mu)) where mu = O((alpha2(alpha)h(alpha)/epsilon)(alphah)). |

Year | DOI | Venue |
---|---|---|

2004 | 10.1007/978-3-540-24749-4_37 | Lecture Notes in Computer Science |

Keywords | Field | DocType |

ad hoc wireless network,time complexity,polynomial time approximation scheme | Discrete mathematics,Broadcasting,Wireless network,Dynamic programming,Combinatorics,Low energy,Algorithm,Wireless ad hoc network,Hop (networking),Time complexity,Mathematics,Bounded function | Conference |

Volume | ISSN | Citations |

2996 | 0302-9743 | 17 |

PageRank | References | Authors |

0.74 | 9 | 8 |

Authors (8 rows)

Cited by (17 rows)

References (9 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Christoph Ambühl | 1 | 357 | 18.50 |

Andrea E. F. Clementi | 2 | 1168 | 85.30 |

Miriam di Ianni | 3 | 144 | 17.27 |

Nissan Lev-Tov | 4 | 137 | 7.91 |

Angelo Monti | 5 | 671 | 46.93 |

David Peleg | 6 | 6662 | 824.19 |

Gianluca Rossi | 7 | 235 | 21.60 |

Riccardo Silvestri | 8 | 1324 | 90.84 |