loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Eighth IEEE Symposium on Computers and Communications
Concurrent Broadcast-Based Permutation Routing Algorithms in Radio Networks
Kemer-Antalya, Turkey
June 30-July 03
ISBN: 0-7695-1961-X
Jean-Fr?d?ric Myoupo, Universit? de Picardie-Jules Verne
In their recent work in1999, Nakano, Olariu and Schwing showed that the permutation routing of n items pretitled on a Radio Network Model of p processors and k channels (RN(p,k)) with k \le p < p, can be carried out in 2\frac{n} {k} + k - 1 broadcast rounds if k \leqslant \sqrt p and if each processor has an O(\frac{n} {k})-memory locations. If k > \sqrt {\frac{p} {2}} and if each processor has an O\left( {\frac{n} {p}} \right)-memory locations, the permutations of these n pretitled items can also be done in 2\frac{n} {k} + k - 1 broadcast rounds. They left the permutation routing on an O\left( {\frac{n} {p}} \right)-RN(p, k) when k > \sqrt {\frac{p} {2}} and on an O\left( {\frac{n} {p}} \right)-RN(p, k) with k > \sqrt {\frac{p} {2}} c as open problems. This paper shows how to handle efficiently these open problems. In order to get efficiency, we show that this open problems become those of concurrent broadcast on multiple channels. More precisely, in a concurrent broadcast environment, we show that the permutation routing problem on RN(p, k) with k > \sqrt p can be carried out in 2\frac{n} {k} + z - 1 broadcast rounds. We also prove that the permutation routing problem on an O\left( {\frac{n} {p}} \right) - RN\left( {p,k} \right) with k > \sqrt {\frac{p} {2}} can be performed in 2\frac{n} {k} + q - 1 broadcast rounds. Where z and q are such that p = zk + r(z) and p = q(2k) + r(q) respectively, with r(z) < k and r(q) < 2k.
Citation:
Jean-Fr?d?ric Myoupo, "Concurrent Broadcast-Based Permutation Routing Algorithms in Radio Networks," iscc, pp.1272, Eighth IEEE Symposium on Computers and Communications, 2003
Usage of this product signifies your acceptance of the Terms of Use.