توضیحات
ABSTRACT
In this paper, a new mathematical programming model and assignment algorithms are developed for minimizing the schedule length in adaptive power and adaptive rate link scheduling in spatial-TDMA wireless networks. The underlying problem entails the optimal joint scheduling of transmissions across multi-access communication links combined with the simultaneous allocation of transmit power levels and data rates across active links, while meeting required Signal-to-Interferenceplus-Noise Ratio (SINR) levels at intended receivers. We prove that the problem can be modeled as a Mixed Integer-Linear Programming (MILP) and show that the latter yields a solution that consists of transmit power levels that are strongly Pareto Optimal. We note this problem to be NP-complete. For comparison purposes, we employ the MILP formulation for computing the optimal schedule for networks with small number of designated links and limited number of data rate levels. We proceed to develop and investigate a heuristic algorithm of polynomial complexity for solving the problem in a computationally effective manner. The algorithm is based on the construction of a Power Controlled Rate adaptation Interference Graph. The desired schedule is then derived by using a greedy algorithm to construct an independence set from this graph. Based on system analyses, we show, for smaller illustrative networks, the performance behavior realized by the heuristic algorithms to generally be in the 75 percentile of those attained by the optimal schedule. We also show that performance of our heuristic algorithm is on average 20% better than that attained under prior algorithms that were developed for use under fixed transmit power and fixed rate link scheduling.
INTRODUCTION
CONSIDER a wireless mesh network (Fig. 1) that consists of interconnected wireless Local Area Networks (LANs), a metropolitan area network and its backbone, and others that employ meshed backbones and multi-hop access nets. Assume that a scheduling based Medium Access Control (MAC) protocol such as spatial-Time Division Multiple Access (TDMA) is used. Time slots are allocated to stations to transmit their messages across their established links. To achieve high level of network throughput, it is desirable to assign a schedule that will achieve a high level of spatial reuse (i.e. high number of simultaneous transmissions). To enhance the efficiency of physical and MAC layer processes, stations employ adaptable Software Defined Radios.
چکیده
در این مقاله، یک الگوریتم جدید برنامه ریزی ریاضی و الگوریتم انتساب برای به حداقل رساندن طول زمان برنامه ریزی شده در شبکه های بی سیم فضایی TDMA در سرعت و انطباق پذیری پیاده سازی شده است. مشكل اساسي، برنامه ريزي مشترك بهينه را در ارتباطات ارتباطات چند منظوره همراه با تخصيص همزمان سطوح قدرت انتقال و نرخ داده ها در ميان لينك فعال فعال مي كند، در حالي كه در مقايسه با سطوح نسبت سيگنال به Interference Plus-Noise Ratio (SINR) در گيرنده هاي مورد نظر . ما ثابت می کنیم که مشکل را می توان به عنوان یک برنامه ریزی صحیح زنجیره ای یکپارچه (MILP) مدل سازی کرد و نشان می دهد که دومین راه حل را فراهم می کند که شامل سطوح قدرت انتقال است که به طور قابل توجهی Pareto Optimal است. ما این مشکل را NP-complete می دانیم. برای مقاصد مقایسه، از فرمول MILP برای محاسبه برنامه بهینه برای شبکه ها با تعداد کمی از لینک های تعیین شده و تعداد محدودی از سطوح سرعت داده استفاده می کنیم. ما در حال توسعه و بررسی یک الگوریتم اکتشافی پیچیدگی چند جمله ای برای حل مشکل در یک روش محاسباتی موثر است. الگوریتم بر اساس ساخت گرافن تداخل انطباق نرخ کنترل قدرت است. سپس برنامه مورد نظر با استفاده از یک الگوریتم حریص برای ساختن مجموعه استقلال از این نمودار مشتق می شود. بر اساس تجزیه و تحلیل سیستم، برای شبکه های کوچکتر نشان داده شده، رفتار عملکردی که توسط الگوریتم های اکتشافی به دست می آید به طور کلی در 75 درصد از مقادیر به دست آمده از برنامه بهینه است. ما همچنین نشان می دهیم که عملکرد الگوریتم اکتشافی ما به طور متوسط 20٪ بهتر از آنچه که در الگوریتم های پیشین بدست آمد، برای استفاده در زمان انتقال قدرت ثابت و نرخ ثابت نرخ ثابت طراحی شده است.
مقدمه
یک شبکه مشبک بی سیم (شکل 1) را که شامل شبکه های محلی محلی بی سیم (LAN)، یک شبکه بزرگ شهری و ستون فقرات و دیگران است که از ستون فقرات شبکه ای و شبکه های دسترسی چند منظوره استفاده می کنند، در نظر بگیرید. فرض کنید که یک پروتکل مدیریت دسترسی (MAC) مبتنی بر زمانبندی مانند Access Time Division Multiple Access (TDMA) استفاده شده است. اسلات های زمان به ایستگاه های اختصاص داده شده برای ارسال پیام های خود را در سراسر لینک های ثابت شده خود را. برای دستیابی به سطح بالای بازده شبکه، مطلوب است تا برنامه ای را تعیین کند که به سطح بالایی از استفاده مجدد فضایی (یعنی تعداد زیادی از انتقال همزمان) دست یابد. برای افزایش بهره وری از فرآیندهای لایه فیزیکی و مک، ایستگاه ها از رادیوهای قابل تعریف نرم افزاری قابل انعطاف استفاده می کنند.
Year: 2010
Publisher : IEEE
By : Kian Hedayati, Izhak Rubin, Arash Behzad
File Information: English Language/ 9 Page / size: 360 KB
Only site members can download free of charge after registering and adding to the cart
سال : 1389
ناشر : IEEE
کاری از : کیان هدایی، اصحاب روبین، آرش بهزاد
اطلاعات فایل : زبان انگلیسی / 9 صفحه / حجم : KB 360
نقد و بررسیها
هنوز بررسیای ثبت نشده است.