دوشنبه 17 اردیبهشت 1403
| عنوان مقاله | |
| عنوان مقاله |
Succinct and practical greedy embedding for geometric routing |
| عنوان فارسی مقاله | تعبیه حریص موجز و عملی برای مسیریابی هندسی |
| مشخصات مقاله انگلیسی | |
| نشریه: Elsevier |
|
| سال انتشار |
2017 |
| عنوان مجله |
Procedia Computer Scienc |
| تعداد صفحات مقاله انگلیسی | 18 |
| رفرنس | دارد |
| تعداد رفرنس | 44 |
| چکیده مقاله | |
| چکیده |
The scalability challenge of geometric routing is to construct succinct coordinates for all nodes in the network. This paper presents SPrefix-B, a practical greedy embedding scheme with succinct coordinates, low path stretches and 100% routing success. In comparison to theoretical schemes with near-optimal succinctness, SPrefix-B is simple and easy to implement without requiring the whole topology and works well in both weighted and unweighted graphs. In con- trast to practical schemes, SPrefix-B is more succinct and universal. It provides O (log 2 ( n )) -bit coordinates for arbitrary graphs. This paper first proposes Prefix-B which adopts a bit-string prefix tree as a metric space and provides succinct embedding for some power law graphs. Furthermore, to extend the succinctness to arbitrary graphs, SPrefix-B is pro- posed by applying two optimizations, the compressed path decomposition and the compressed embedding, to Prefix-B. The theoretical analyses and experimental results show that SPrefix-B not only guarantees greediness, but also provides succinctness and low path stretches. |
| کلمات کلیدی |
|
| دانلود | |
