Ad hoc networks beyond unit disk graphs

被引：65

作者：

Kuhn, Fabian ^{[2
]}

Wattenhofer, Roger ^{[3
]}

Zollinger, Aaron ^{[1
]}

机构：

[1] Univ Calif Berkeley, Dept Elect Engn & Comp Sci, Berkeley, CA 94720 USA

[2] Microsoft Res, Mountain View, CA 94043 USA

[3] Swiss Fed Inst Technol, CH-8092 Zurich, Switzerland

来源：

WIRELESS NETWORKS | 2008年 / 14卷 / 05期

关键词：

algorithmic analysis; cost metrics; geographic routing; network models; wireless ad hoc networks;

D O I：

10.1007/s11276-007-0045-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we study an algorithmic model for wireless ad hoc and sensor networks that aims to be sufficiently close to reality as to represent practical realworld networks while at the same time being concise enough to promote strong theoretical results. The quasi unit disk graph model contains all edges shorter than a parameter d between 0 and 1 and no edges longer than 1. We show that-in comparison to the cost known for unit disk graphs-the complexity results of geographic routing in this model contain the additional factor 1/d(2). We prove that in quasi unit disk graphs flooding is an asymptotically message-optimal routing technique, we provide a geographic routing algorithm being most efficient in dense networks, and we show that classic geographic routing is possible with the same asymptotic performance guarantees as for unit disk graphs if d >= 1/root 2.

引用

页码：715 / 729

页数：15