东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

A Near-Optimal Optimization Algorithm for Link Assignment in Wireless Ad-hoc Networks

期刊名称：Journal of Computer Science and Technology
时间：0
作者或编辑：3448
第一作者所属机构：中国科技大学
页码：89-94
语言：英文
分类：TN92[电子电信—通信与信息系统;电子电信—信息与通信工程]
作者机构：[1]Department of Computer Science, University of Science and Technology of China, Hefei 230027, P.R. China, [2]Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, P.R. China
相关基金：This paper is supported by the National Natural Science Foundation of China under Grant Nos. 60241004 and 90104010, the National Basic Research 973 Program of China under Grant No, 2003CB314801, and the State Key Laboratory of Networking and Switching Technology,
相关项目：形式化的协议理论

作者： Heng-Chang Liu（刘恒昌）and Bao-Hua Zhao（赵保华）|

关键词：最佳优化算法, 路由链接, STDMA, 无线网络, 数学模型, link scheduling, STDMA, wireless network, mathematical modeling, column generation

中文摘要：

在过去几年，无线联网技术成为了广阔在我们的每日的生活袭击。在无线特定的网络，没有任何永久基础结构，连接由很多个单位被建立。在这篇论文，资源优化被认为由高效地使用网络能力最大化网络产量，在的地方 multi-hopfunctionality 和空间 TDMA (STDMA ) 存取方案被使用。目的是与给定的交通分布和相应路由选择信息发现最小的框架长度。因为内在的数学问题的复合结构，以前的工作和分析为现实主义的尺寸的网络变得难处理。这个问题通过数学规划途径被处理，线性整数明确的表达为优化网络产量被开发，然后初始问题的类似和图边缘着色问题通过冲突图概念被显示出。一个列产生答案被建议，几改进被做以便系住它的集中。数值结果证明产量的理论限制能高效地为现实主义的尺寸的网络被计算。

英文摘要：

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 realistic 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.

同期刊论文项目