6533b7d3fe1ef96bd125ff86
RESEARCH PRODUCT
A Restricted-Weakly Connected Dominating Set for Role Assignment in a Multichannel MAC for Wireless Mesh Network
Andrzej DudaBenoit DartiesFabrice Theoleyresubject
Computer scienceDistributed computing[ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI]Mesh networking0102 computer and information sciences02 engineering and technologyNetwork topology01 natural sciencesConnected dominating setlaw.invention[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]law0202 electrical engineering electronic engineering information engineeringComputer Science::Networking and Internet ArchitectureWireless mesh network[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]business.industryRadio Link ProtocolComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKSPacket forwarding020206 networking & telecommunicationsOrder One Network Protocol010201 computation theory & mathematicsbusinessAssignment problemComputer networkdescription
International audience; 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-10-01 |