2009 · 14 citations · 13 references
ComputingComputer ScienceComputer NetworksOptimizationWireless CommunicationsInterference ManagementLatency OptimizationNetwork ProtocolsWireless Communication ProtocolsWireless NetworksWireless Sensor NetworksBeaconing AnalysisBest ApproximationInterferenceInterference ModelingInterference-aware Scheduling
Minimum-latency beaconing schedule (MLBS) in synchronous multihop wireless networks seeks a schedule for beaconing with the shortest latency. This problem is NP-hard even when the interference radius is equal to the transmission radius. All prior works assume that the interference radius is equal to the transmission radius, and the best-known approximation ratio for MLBS under this special interference model is 7. In this paper, we present a new approximation algorithm called strip coloring for MLBS under the general protocol interference model. Its approximation ratio is at most 5 when the interference radius is equal to transmission radius, and is between 3 and 6 in general.
13
The capacity of wireless networks
Piyush Gupta, P. R. Kumar · IEEE Transactions on Information Theory · 2000 · 8.4K citations
Brent N. Clark, Charles J. Colbourn, David Johnson · Discrete Mathematics · 1990 · 1.4K citations