An Application of an Initialization Protocol to Permutation Routing in a Single-Hop Mobile Ad Hoc Networks

In 1999 Nakano, Olariu, and Schwing in [20], they showed that the permutation routing of n items pretitled on a mobile ad hoc network (MANET for short) of p stations (p known) and k channels (MANET{(n, p, k)) with k < p, can be carried out in broadcast rounds if k p and if each station has a -memory locations. And if k and if each station has a -memory locations, the permutations of these n pretitled items can be done also in broadcast rounds. They used two assumptions: first they suppose that each station of the mobile ad hoc network has an identifier beforehand. Secondly, the stations are partitioned into k groups such that each group has stations, but it was not shown how this partition can be obtained. In this paper, the stations have not identifiers beforehand and p is unknown. We develop a protocol which first names the stations, secondly gives the value of p, and partitions stations in groups of stations. Finally we show that the permutation routing problem can be solved on it in broadcast rounds in the worst case. It can be solved in broadcast rounds in the better case. Note that our approach does not impose any restriction on k.