Randomized 3D Position-based Routing Algorithms for Ad-hoc Networks

摘要

In position-based routing algorithms for ad-hoc networks, the nodes use the geographical information to make the routing decisions. Recent research in this field primarily addresses such routing algorithms in two dimensional space (2D). However, in real applications, nodes may be distributed in 3D space. In this paper we extend previous randomized routing algorithms from 2D space to 3D space, and we propose two new position-based routing algorithms that combine randomized AB3D routing algorithms with a deterministic CFace (coordinate face) algorithm. The first algorithm AB3D-CFace(1)-AB3D starts with AB3D routing algorithm until a local minimum is reached. The algorithm then switches to CFace routing using one projected coordinate. If CFace(1) enters a loop, the algorithm switches back to AB3D. The second algorithm AB3D-CFace(3) starts with AB3D, until a local minimum is reached The algorithm then permanently switches to CFace routing using three projected coordinates, in order. We evaluate our mechanisms and compare them with the current routing algorithms. The simulation results show the significant improvement in delivery rate over pure AB3D randomized routing (97% compared to 70%) and reduction in path dilation (up to 50%) over pure CFace algorithm