Title :
On self-stabilization of multi point relays for connected dominating set in adhoc networks
Author_Institution :
Dept. of Comput. Sci., Indian Inst. of Technol., Patna, India
Abstract :
Recently, Adjih proposed a source independent multipoint relay (MPR) based localized construction for small sized connected dominating set (CDS). This MPR-based CDS does not need any knowledge of global network topology, which makes it attractive to the applications in mobile adhoc networks for providing routing backbone. In this work we introduce a reverse selection heuristics and provided self-stabilization (SS) to MPR-based CDS algorithm. This SS-MPR-CDS provides tolerance to SS-MPR-CDS based virtual backbone from transient changes in topology. Our SS-MPR-CDS algorithm stabilizes with complexity of O(n.¿3) moves, where ¿ is maximum degree of node.
Keywords :
ad hoc networks; telecommunication network topology; connected dominating set; global network topology; mobile adhoc networks; multi point relays; reverse selection heuristics; self-stabilization; transient changes; Application software; Approximation algorithms; Computer science; Distributed algorithms; Greedy algorithms; Network topology; Relays; Routing; Spine; Wireless networks;
Conference_Titel :
TENCON 2009 - 2009 IEEE Region 10 Conference
Conference_Location :
Singapore
Print_ISBN :
978-1-4244-4546-2
Electronic_ISBN :
978-1-4244-4547-9
DOI :
10.1109/TENCON.2009.5395977
