%0 Journal Article
%T A Near-Optimal Optimization Algorithm for Link Assignment in Wireless Ad-Hoc Networks
%A Heng-Chang Liu
%A Bao-Hua Zhao
%A
Heng-Chang
%A Liu
%A and
%A Bao-Hua
%A Zhao
%J 计算机科学技术学报
%D 2006
%I
%X Over the past few years, wireless networking technologies have made vast forays in our daily lives. In wireless ad-hoc networks, links are set up by a number of units without any permanent infrastructures. In this paper, the resource optimization is considered to maximize the network throughput by efficiently using the network capacity, where multi-hop functionality and spatial TDMA (STDMA) access scheme are used. The objective is to find the minimum frame length with given traffic distributions and corresponding routing information. Because of the complex structure of the underlying mathematical problem, previous work and analysis become intractable for networks of realistle sizes. The problem is addressed through mathematical programming approach, the linear integer formulation is developed for optimizing the network throughput, and then the similarity between the original problem and the graph edge coloring problem is shown through the conflict graph concept, A column generation solution is proposed and several enhancements are made in order to fasten its convergence. Numerical results demonstrate that the theoretical limit of the throughput can be efficiently computed for networks of realistic sizes.
%K link scheduling
%K STDMA
%K wireless network
%K mathematical modeling
%K column generation
最佳优化算法
%K 路由链接
%K STDMA
%K 无线网络
%K 数学模型
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=B91FE041BE7BBBC7BD17D6C479D2080D&yid=37904DC365DD7266&vid=659D3B06EBF534A7&iid=CA4FD0336C81A37A&sid=CFAC5CB624A41AFD&eid=BB0EA31DB1B01173&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=2&reference_num=23