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
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||