DocumentCode :
2320603
Title :
A Restricted-Weakly Connected Dominating Set for Role Assignment in a Multichannel MAC for Wireless Mesh Network
Author :
Darties, Benoît ; Theoleyre, Fabrice ; Duda, Andrzej
Author_Institution :
Grenoble Inf. Lab. (LIG), Grenoble INP, St. Martin d´´Heres, France
fYear :
2009
fDate :
12-14 Oct. 2009
Firstpage :
167
Lastpage :
172
Abstract :
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.
Keywords :
access protocols; approximation theory; communication complexity; packet radio networks; radio links; telecommunication network topology; wireless LAN; wireless channels; NP-completeness; centralized 2-approximation algorithm; connected dominating set; distributed protocol; molecular MAC; molecular structure; multichannel MAC; multichannel access; network topology; packet forwarding; radio link; role assignment; wireless mesh network; Computer networks; Contracts; Deafness; Electrons; Media Access Protocol; Mobile communication; Mobile computing; Switches; Throughput; Wireless mesh networks; $2$-approximation; Molecular MAC; WCDS; wireless mesh networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Wireless and Mobile Computing, Networking and Communications, 2009. WIMOB 2009. IEEE International Conference on
Conference_Location :
Marrakech
Print_ISBN :
978-0-7695-3841-9
Type :
conf
DOI :
10.1109/WiMob.2009.37
Filename :
5325196
Link To Document :
بازگشت