کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431875 688644 2006 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks
چکیده انگلیسی

A wireless ad hoc network is often composed of a set V of n wireless devices distributed in a two-dimensional domain. For each wireless device (also called node) u∈V, there is a transmission region within which signal-to-noise-ratio (SNR) is at least a threshold γ so that the signal transmitted by u can be correctly received by other nodes with high probability. The transmission region is often modeled as a disk centered at the node u. In addition, for each node u, there is an interference region within which the transmission from u makes the signal-to-interference-and-noise-ratio (SINR) of the legitimate receiver smaller than the threshold γ so that the legitimate receiver cannot correctly receive the message from the legitimate transmitter.In this paper, we first present new graph models to model the communication graphs and the interference graphs defined by wireless ad hoc networks with attention to interference-free channel assignment or scheduling. Then we propose some simple approximation algorithms and/or PTASs (polynomial time approximation scheme) to approximate several classical graph problems such as maximum independent set, minimum vertex cover and minimum vertex coloring in these graph models. In addition, we also discuss various possible applications for these simple approximation algorithms and/or PTASs in wireless ad hoc networks.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 66, Issue 4, April 2006, Pages 515-530