Widest Spanning Tree for Multi-Channel Multi-Interface Wireless Mesh Networks
| Autor: | King-Shan Lui, K.L. Yeung, Bin Wu, Hon Sun Chiu |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Spanning tree
Job shop scheduling Wireless mesh network business.industry Computer science Distributed computing ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS Minimum spanning tree Connected dominating set Graph Bottleneck Widest path problem Distributed minimum spanning tree Constraint graph Graph (abstract data type) Graph coloring business Computer network |
| Zdroj: | WCNC |
| DOI: | 10.1109/wcnc.2008.388 |
| Popis: | Efficient broadcast schemes are essential in wireless mesh networks (WMNs) for minimizing the content update time. In this paper, we consider the widest spanning tree problem in a multi-channel multi-interface WMN, where the width of a tree is determined by the bottleneck link bandwidth. To the best of our knowledge, we present the first effort in solving the widest spanning tree problem using mathematical formulation. In our model, we jointly consider and solve the problems of channel assignment, routing, scheduling and server/root placement. Unlike other spanning tree approaches, we allow WMN nodes to have heterogeneous number of network interface cards (NICs), and multiple NICs of a node can share the same assigned set of channels. To find a practical schedule, we also introduce the channel conflict graph and NIC constraint graph, and show that the associated scheduling problem is equivalent to the classic graph coloring problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|