Benoit Darties, Fabrice Theoleyre and Andrzej Duda
In Proceedings of IEEE WIMOB (Conference on Wireless and Mobile Computing, Networking and Communications), Marrakech, Morocco, October 12-14, 2009
Monday 12 October 2009
We propose an efficient way of constructing the wireless mesh structure associated with Molecular MAC, a multichannel access method designed for efficient packet forwarding. We base our role assignment on a restricted Weakly Connected Dominating Set structure. After presenting a formal definition of the role assignment problem, we prove its NP-completeness. Then, we propose a centralized 2-approximation algorithm that maximizes the sum of radio link capacities in the molecular structure. Finally, we extend this protocol so that it can operate in a distributed way still providing the same guarantee. This distributed protocol is self-stabilizing thus robust to topology changes. Our simulation results show that the 2-approximation distributed protocol provides an improvement in throughput with respect to other protocols.