On Channel-Discontinuity-Constraint Routing in Wireless Networks

Area of Science:

• Computer Science
• Wireless Networking
• Distributed Systems

Background:

• Multi-channel wireless networks with directional antennas are common in urban areas.
• Efficient path computation with channel assignments is crucial for maximizing throughput.
• Channel-Discontinuity-Constraint (CDC) paths ensure consecutive links use different channels, beneficial for TDMA systems.

Purpose of the Study:

• To develop a t-spanner for CDC-paths to approximate path costs efficiently.
• To design a distributed algorithm for finding minimum-cost CDC-paths.
• To improve the time complexity of centralized CDC-path computations.

Main Methods:

• Developed a t-spanner using spatial properties with O(n/θ) links.
• Proposed a distributed algorithm for spanner computation using O(n log n) messages.
• Extended Edmonds' algorithm for minimum-cost perfect matching to find minimum-cost CDC-paths in O(n^2) messages.

Main Results:

• The t-spanner increases CDC-path costs by at most a factor t = (1-2 sin (θ/2))⁻².
• The distributed algorithm for spanner computation uses an expected O(n log n) fixed-size messages.
• The distributed algorithm for minimum-cost CDC-paths uses O(n^2) fixed-size messages.
• Centralized implementation achieves O(n^2) time complexity, an improvement over O(n^3).
• Combined with the spanner, centralized computation time improves to O(n/θ).

Conclusions:

• The developed t-spanner provides an efficient approximation for CDC-paths.
• Novel distributed algorithms significantly reduce message complexity for spanner and path computations.
• The proposed methods offer substantial improvements in both distributed and centralized CDC-path finding.