Concurrent broadcasts-based permutation routing algorithms in radio networks
Jean‐Frédéric Myoupo · 2004
In their recent work in 1999, 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 /spl les/ p/spl radic/(p/2) c as open problems. This paper shows how to handle efficiently these open problems. In order to get efficiency, we show that these 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/spl radic/(p/2) can be performed in 2 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.