Concurrent broadcasts-based permutation routing algorithms in radio networks

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 ≤ p < p, can be carried out in 2 n/k + k - 1 broadcast rounds if k ≤ √p and if each processor has an O(n/k)-memory locations. If k ≤ √(p/2) and if each processor has an O(n/p)-memory locations, the permutations of these n pretitled items can also be done in 2 n/k + k - 1 broadcast rounds. They left the permutation routing on an O(n/p)-RN(p,k) when k > √(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 < √p can be carried out in 2 n/k + z - 1 broadcast rounds. We also prove that the permutation routing problem on an O(n/p)-RN(p,k) with k > √(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.