Abstract:
Given
a d-dimensional mesh network with arbitrary node names,
we want to design a routing scheme in order to minimize
the space used by each node and to minimize the routing
path as well. I will prove that the space at each node is
\Theta(n) if the routing path is always the shortest. And
if the stretch is 1+\epsilon, namely all the routing path
is at most 1+\epsilon as long as the shortest, I will present
a compact routing scheme which only uses O(1/\epsilon^2
log(10d\epsilon n^{1/d}) log(n)) space per node, and give
a proof that the lower bound is \Omega(1/\epsilon^2 log(10d\epsilon
n^{1/d})). These are better than the previously-known results
for general graphs.
Biography:
Chengu
Wang is a fourth year undergraduate student in Special Pilot
Class in Computer Science Department in Tsinghua University.
And he will start for his PhD degree in Institution of Theoretical
Computer Science in Tsinghua University. This is his final
year project, which is in the field of Wireless Sensor Network.