Details

Autor(en) / Beteiligte

• Hoffmann, Stefan
• Wanke, Egon

Titel

Generic Route Repair: Augmenting Wireless Ad Hoc Sensor Networks for Local Connectivity

Ist Teil von

• 2016 15th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), 2016, p.1-10

Ort / Verlag

IEEE

Erscheinungsjahr

2016

Link zum Volltext

Quelle

IEEE Electronic Library (IEL)

Beschreibungen/Notizen

• Routes in a wireless network can be repaired reactively after node failures by broadcasting the message across the neighborhood of the failed node. This broadcast problem is easily solvable, if the neighborhood of every node in the network induces a connected subgraph of the communication graph. Graphs with this property are called locally connected. This paper considers the edge augmentation problem for undirected graphs G = (V, E) that asks for a minimum set E' of additional edges such that the neighborhoods defined by G induce connected subgraphs of the augmented graph G' = (V, E∪E'). We develop a practical approximation algorithm with an approximation factor of 1 + ln (|V|) for general graphs and a constant approximation factor for several special cases such as unit disk graphs (factor 3/2), d-quasi unit disk graphs having d ≥ √3-1 ≈ 0.732 (factor 11/6) or graphs with a constant maximum vertex degree. Additionally we prove the NP-completeness of the augmentation problem above and the related augmentation problem that asks for a locally connected graph.