دانلود رایگان ترجمه مقاله مسیریابی ادهاک (Ad-hoc) متحرک هندسی بهینه تقریبی

 مقاله انگلیسی رایگان

ترجمه فارسی رایگان 

بخشی از ترجمه فارسی:

خلاصه :
در این مقاله ما اطلاعاتی را در مورد AFR برای شما بیان می کنیم . AFR یک وسیله متحرک هندسی جدید است که الگوریتم را مسیر یابی می کنیم الگوریتم بطور کامل توزیع شده است (پراکنده شده است) گره ها باید فقط با همسایه های مستقیم شان که در محدوده انتقال آنها قرار دارند در تماس بوده و ارتتباط برقرار کنند ما نشان می دهیم که اگر بهترین مسیر AFR است که هزینه ای به مقدار C دارد ، ترمینال هایی که ارزشی به اندازه O (c2) دارند بدترین مورد می باشند AFR یک الگوریتم rst با هزینه است که بوسیله عملکرد یک مسیر بهینه و مطلوب محدود شده است.
ما همچنین با نشان دادن این موضوع که هر الگوریتم مسیریابی مهندسی بدترین ارزش و هزینه را دارد یعنی (c2) یک محدوده زیرین محکم و استواری را ارائه می دهیم بنابراین AFR کاملا مطلوب و بهینه است ما یک الگوریتم غیر هندسی را ارائه می دهیم که با محدوده (مرز- حدود ) زیرین هم مطابقت دارد اما مقداری حافظه در هر گره نیاز دارد این مطلب باعث بوجود آمدن یک تجارت وسوسه گر بین هندسه و حافظه می گردد.
– طبقه بندیها و توصیفهای موضوعات:
F.2.2 ( تجزیه و تحلیل الگوریتم ها و مشکلات پیچیده ) الگوریتم های غیر عددی و مشکلات و مسائل آن .
مسائل هندسی و محاسبات . مسیر یابی و طرح C.22.2 .(شبکه های ارتباطی کامپیوتر ): پروتکل های شبکه ای (شبکه ) پروتکل های مسیر یابی
عبارات و اصطلاحات معمول : الگوریتم ها ، تئوری
کلمات مهم و اساسی : شبکه های Hoc – Ad (ویژه – متخصص ) مسیریابی رودرو ، مسیر یابی هندسی ، مسیریابی گرافهای دیسک واحد ، مکالمه بدون نیاز به سیم کاری که در این مقاله ارائه شده است (بخشی از آن ) توسط مرکز ملی تحقیقات در مورد اطلاعات موبایل و سیستم های ارتباطی حمایت شده است ( یعنی مرکز MACS-NCCR ) و بخش مهم آن توسط Swiss National Science حمایت و ضمانت شده است که شماره ضمانت آن (مرکز علم ملی موسس ) Foundation 322 67- 5005 می باشد.
مقدمه:
شبکه ویژه (hoc-Ad) موبایل از گره های متحرک تشکیل شده که مجهز به رادیوی بدون سیم می باشد گره های وسیله متحرک موبایل را همانند نقطه ها در هواپیمای اقلیدسی در نظر می گیریم اگر دو گره در محدوده انتقال یکدیگر قرار گرفته باشند می توانند بطور مستقیم با یکدیگر ارتباط برقرار کنند در این مقاله ما فرض می کنیم که تمام گره ها محدوده انتقالی یکسانی دارند یعنی R1 .
دو گره با فاصله هایی بیشتر از R میتوانند از طریق تقویت پیامشان بوسیله یکی از گره های حد واسط با یکدیگر ارتباط برقرار نمایند این فرایند مسیر یابی multi-hop نامیده می شود در این مقاله ما مسیر را که به اصطلاح مسیریابی هندسی نامیده می شود را مطالعه می کنیم در شبکه هایی که مسیریابی هندسی را رعایت می کنند a ) هرگاه با یک سرویس موقعیتی مجهز شده است یعنی هر گره ، گره متناسب اقلیدسی خودش را شناسایی می کند .(می شناسد ) b) هرگره تمامی گره های همسایه اش را (گره هایی در محدوده انتقال R ) و گره های متناسبشان را می شناسد . C) فرستنده پیام گره های متناسب مقصد را شناسایی میکند .
علاوه بر فرضیه های استاندارد a,b,c ما فرض می کنیم که گره های مویابل به صورت دلخواهانه و قراردادی نزدیک یکدیگر نیستند یعنی اینکه یک فاصله دائمی do مثل همان فاصله ای که بین هر جفت از گره ها است وجود دارد . این فرضیه با این حقیقت دنبال می شود که محدودیتهای فیزیکی در مورد اینکه چطور و به چه اندازه گره های موبایل به هم نزدیک باشند ودر چه فاصله ای از هم قرار گرفته باشند وجود دارند علاوه بر این فواصل بین گره های همسایه در یک شبکه ad-hoc (ویژه) طبق محدوده انتقال خواهد بود .
– در این مقاله ما یک الگوریتم مسیریابی هندسی جدید را ارائه می کنیم که این الگوریتم مواردی را از الگوریتم مسیریابی رودرو (Fac Routing algorithy) که توسط Sinjh، Kranakis و Urrutia بیان شده است را قرض می گیرد . (یعنی درمواردی که از آن الگوریتم تبعیت می کند ) برای الگوریتم مان یک اسم انتخاب می کنیم : AFR که نشان دهنده Adaptive Face Routing می باشند الگوریتم ما کاملا محلی است گره ها فقط با همسایه های مستقیم خودشان پیامها را تبادل می کنند (تعویض می کنند ) ( یعنی با گره های در محدوده انتقال R آنها پیامها را تبادل می کنند) ما نشان می دهیم که اگر بهترین مسیر ارزش (هزینه ) C را دارد الگوریتم ما یک مسیری را پیدا می کند و در بدترین حالت باارزش o ( c2) آن را پایان می دهد این مرز و محدوده برای بسیاری از مدلهای ارزشی مهم از قبیل مساحت ، انرژی، … در نظر گرفته می شود توجه کنید که فاصله بهترین مسیر بطور دلخواهانه و قراردادی می تواند بزرگتر از فاصله (مسافت ) اقلیدسی مبدا و مقصد باشد الگوریتم ما اولین الگوریتمی است که توسط عملکرد یک مسیر مطلوب و بهینه محصور شده است الگوریتم مسیریابی رودروی اصلی و سایر الگوریتم های مسیر یابی هندسی تنها بوسیله عملکردی از تعداد گره ها محدود شده اند.
– علاوه براین ما نشان می دهیم که هر الگوریتم مسیر یابی هندسی ارزش (c2 ) را دارند این مرزخفیف محکم تایید می کند که الگوریتم ما از لحاظ خط مجانب کمال مطلوب را دارد و بهینه است مرز پایینی مهم چنین نمایان گر الگوریتم های تصادفی است علاوه بر نتایج تئوریتیک این مقاله ما احساس میکنیم الگوریتم ما پتانسیل عملی شده را نیز دارد بویژه به عنوان مکانیزمی برای الگوریتم های مسیریابی هندسه .
– باعث شگفتی است که هزینه الگاریتم مسیریابی هندسی مجذور هزینه بهترین مسیر است ما نشان می دهیم که این مرزهمچنین می تواند که بوسیله الگوریتم مسیر یابی غیر هندسی ساده بدست آید به عوض خدمات محل از دست رفته ما به الگوریتم مقداری حافظه در هر گره می دهیم ما نشان مید هیم که این الگوریتم هم ارزش (هزینه ) (c2) O بزرگ را دارد که تایید می کند در بدترین مورد یک GPS می توانند به اندازه مقادیر اضافه ای از ذره های حافظه مفید باشد .
– این مقاله به روشی که در زیر دنبال می شود سازماندهی شده است در بخش بعدی ما در مورد کارهای مرتبط با این مقاله بحث می کنیم در بخش ۳ ما مدل شبکه های ویژه (ad-hoc) موبایل را و الگوریتم های مسیریابی هندسی را ارائه می دهیم در بخش ۴ ، ما الگوریتم مسیر یابی هندسی خودمان یعنی AFR را ارائه کرده و آن را تجزیه و تحلیل می نماییم در بخش ۵ یک مرز پایین ( bound lower) را ارائه می دهیم ودر بخش ۶ نتیجه گیری کرده ودر مورد مقاله بحث می کنیم .
– (۲) کارها مرتبط
– بطور سنتی مسیریابی multi-hopبرای شبکه های ad –hoc (ویژه) موبایل (متحرک) یک فهرست مسیریابی را نگهداری می کند و مشخص می کند که چطور پیام فرستاده شود گره های موبایل به صورت محلی وضعیت جغرافیایی شبکه را تغییر می دهد الگوریتم های مسیریابی راکتیو فقط زمانی که نسبت تحرک و جابجایی و ارتباط پایین است می تواند مفید و سودمند باشد اگر گره های موجود در شبکه به لحاظ منطقی متحرک هستند بطور کلی پیام های کنترل جهت بروز کردن فهرست مسیریابی بطور غیرقابل قبولی بالا می شود همچنین ذخیره کردن فهرست های مسیر یابی بزرگ در گره های متحرک ارزان می تواند گران باشد .
از طرف دیگر الگوریتم های مسیر یابی ریاکتیو مسیرها را فقط از طریق مطالبه و درخواست کردن پیدا می کنند وضعیت این روش این است که هیچ هزینه ثابتی برای کاغذ بازی و بروکراسی وجود ندارد . با این وجود زمانی که یک گره نیاز دارد تا یک پیام را به گره دیگر بفرستند فرستنده نیاز است که شبکه را بررسی کرده تا بتواند یک دریافت کننده و یک مسیر در آن پیدا کنند اگرچه هزاران حیله مطلوب وجود دارد که (گاهی واضح و گاهی مفید ) هستند این فرایند می توانند از مقادیری مناسبی از باندهای بی سیم نادر استفاده کنند مروری بر الگوریتم های مسیریابی در شبکه ویژه (ad-hoc) موبایل و (متحرک) در (۴) و (۲۱) وجود دارد حدود ۱۰ سال پیش محققان شروع کردند به حمایت از تجهیز کردن هر گره با سیستم اطلاعات محلی (۷،۱۱،۲۳و ) هرگرهی ، گره متناسب هندسی خود را می شناسد اگر تقریبا گره های متناسب با مقصد هم شناخته شوند یک پیام می تواند به سادگی به بهترین جهت به مسیر فرستاده شود این نظریه مسیریابی براساس موقعیت جغرافیایی و هندسی و مسیر یابی جهت دار نامیده می شود با افزایش دسترسی به سیستمهای موقعیت جهانی (یعنی GPS یا Galileo) میتواند باسانی تصور شود که در گرهی یک دریافت کننده وجود داشته باشد حتی اگر این مورد هم نباشند گره ها می توانند موقعیت خودشان را از طریق طرح و نقشه محلی محاسبه کنند این یک بخش از تحقیقات است که اخیرا به خوبی در مورد آن مطالعه شده است .
مسیریابی هندسی فقط هنگامی کار می کند که گره ها موقعیت مقصد را بشناسند بطور واضح (تقریبا ) موقعیت مقصد بطور متناوب تراز ساختار گراف زیرین و زیرساز تغییر پیدا می کند در این مورد مطمئنا نگهداری موقعیت های تقریبی مقصد هزینه کمتری را نسبت به کل گراف دربر می گیرد . در زمینه شبکه peert tp peer تعداد زیادی از ساختارهای اطلاعاتی ارائه شده اند که این نوع از اطلاعات را به روش مفید موثری را ذخیره میکند . این امکان وجود خواهد داشت که از شبکه peert tp peer استفاده شود تا موقعیت تمام مقصد های نگهداری شود (۱۶) مطلب آخر اینکه کسی میتواند تصور کند که ما می خواهیم یک پیامی را به گرهی را در منطقه برسانیم یا مفهوم مسیریابی که به عنوان jeocastinj شناخته شده است (۱۳و۱۹) الگوریتم های مسیریابی هندسی در ۲۰-۱۸-۹ داده شده است.
– الگوریتم های مسیر یابی هندسی کاملا حریص بودند : پیام همیشه فرستاده می شود به گره همسایه که مجاور است به مقصد (۲۳ و ۱۱ و ۷) نشان داده است که حتی وضعیت های محلی ساده این مطلب را ضمانت نمی کنند که یک پیام به مقصدش خواهد رسید زمانی که بطور حریصانه (jreedlvi) برای مثال به ما شبکه ای داده شده است که گره هایی دارد که روی حرف c توزیع شده اند (پراکنده اند)فرض کنید که گره s از c می خواهد یک پیامی را به مقصد t یعنی نوک جنوب شرقی c با مسیریابی حریصانه پیام از منبع به بهترین همسایه در جهت جنوب شرقی فرستاده می شود در گره U شمال شرقی نوک C گره همسایه ای که نزدیک به مقصد باشد وجود ندارد و الگوریتم مسیریابی با شکست مواجه می شود برای گیرانداختن شکاف C بهترین همسایه یعنی بهترین همسایه کدام است برای مثال بهترین زاویه A.K.A، Compass Routinj تضمینی ندارد .
– الگوریتم مسیریابی هندسی اول که ضمانت دارد الگوریتم مسیریابی رودرو است که درمقاله ای توسط Kranakis Urrutia,Singh پیشنهاد داده شده است در مقاله کوتاه آنها ، آنها الگوریتم را routinj Comeass می نامند . الگوریتم مسیر یابی رودرو یک بخش سازنده از الگوریتم مسیر یابی AFR ما می باشد و بعدا در مورد جزئیات آن بحث خواهد شد الگوریتم مسیریابی رودررو تضمین میکند که پیام خواهد رسید به مقصد و پایان خواهد یافت در قدمهای On پایان می پذیرد در مواردی که منبع مبدا و مقصد نزدیک هم هستند و ترجیح می دهیم که الگوریتمی داشته باشیم که زودترپایان پذیرد بطور خاص علاقمند به نسبت رقابتی مسیر پیدا شده توسط الگوریتم به بهترین مسیر ممکن هستیم .

بخشی از مقاله انگلیسی:

ABSTRACT In this paper we present AFR, a new geometric mobile adhoc routing algorithm. The algorithm is completely distributed; nodes need to communicate only with direct neighbors in their transmission range. We show that if a best route has cost c, AFR finds a route and terminates with cost O(c 2 ) in the worst case. AFR is the first algorithm with cost bounded by a function of the optimal route. We also give a tight lower bound by showing that any geometric routing algorithm has worst-case cost Ω(c 2 ). Thus AFR is asymptotically optimal. We give a non-geometric algorithm that also matches the lower bound, but needs some memory at each node. This establishes an intriguing trade-off between geometry and memory. Categories and Subject Descriptors F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—geometrical problems and computations, routing and layout; C.2.2 [Computer-Communication Networks]: Network Protocols—routing protocols General Terms Algorithms, Theory Keywords Ad-Hoc Networks, Face Routing, Geometric Routing, Routing, Unit Disk Graphs, Wireless Communication ∗The work presented in this paper was supported (in part) by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center supported by the Swiss National Science Foundation under grant number 5005-67322. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Dial-M’۰۲, September 28, 2002, Atlanta, Georgia, USA. Copyright 2002 ACM 1-58113-587-4/02/0009 …$5.00. 1. INTRODUCTION A mobile ad-hoc network consists of mobile nodes equipped with a wireless radio. We think of mobile nodes as points in the Euclidean plane. Two nodes can directly communicate with each other if and only if they are within transmission range of each other. Throughout this paper we assume that all nodes have the same transmission range R 1 . Two nodes with distance greater than R can communicate by relaying their messages through a series of intermediate nodes; this process is called multi-hop routing. In this paper we study so-called geometric routing; in networks that support geometric routing a) each node is equipped with a location service, i.e. each node knows its Euclidean coordinates, b) each node knows all the neighbor nodes (nodes within transmission range R) and their coordinates, and c) the sender of a message knows the coordinates of the destination. In addition to the standard assumptions a), b) and c), we take for granted that mobile nodes are not arbitrarily close to each other, i.e. d) there is a positive constant d0 such that the distance between any pair of nodes is at least d0. This is motivated by the fact that there are physical limitations on how close to each other two mobile nodes can be placed. Further, distances between neighboring nodes in an ad-hoc network will typically be in the order of the transmission range.2 In this paper we present a new geometric routing algorithm which borrows from the eminent Face Routing algorithm by Kranakis, Singh, and Urrutia [14]. As it is the tradition in the community, we give our algorithm a name: AFR which stands for Adaptive Face Routing3 . Our algorithm is completely local; nodes only exchange messages with their direct neighbors, i.e. nodes in their transmission range R. We show that if a best route has cost c, our algorithm finds a route and terminates with cost O(c 2 ) in the worst case. This bound holds for many prominent cost models such as distance, energy, or the link metric. Note that the distance of the best route (the sum of the distances of the single hops) can be arbitrarily larger than the Euclidean distance of source and destination. Our algorithm is the first algorithm that is bounded by a function of the optimal route; the original Face Routing algorithm and all other geo- 1 In the technical part of the paper we simplify the presentation by scaling the coordinates of the system such that R = 1. 2Meanwhile, we have achieved similar results without assumption d) in [15]. 3 Is it a coincidence that AFR also reflects our first names? metric routing algorithms are only bounded by a function of the number of nodes. Moreover we show that any geometric routing algorithm has cost Ω(c 2 ). This tight lower bound proves that our algorithm is asymptotically optimal4 . The lower bound also holds for randomized algorithms. Apart from the theoretical relevance of our results, we feel that our algorithm has practical potential, especially as a fall-back mechanism for greedy geometric routing algorithms (which are efficient in an average case). It is surprising that the cost of geometric routing algorithms is quadratic in the cost of the best route. We show that this bound can also be achieved by a simple non-geometric routing algorithm. In exchange for the missing location service we give the algorithm some extra memory at each node. We show that this algorithm also has cost O(c 2 ), which, contrary to intuition, proves that in the worst case a GPS is about as useful as some extra bits of memory. The paper is organized as follows. In the next section we discuss the related work. In Section 3 we formally model mobile ad-hoc networks and geometric routing algorithms. In Section 4 we present and analyze our geometric routing algorithm AFR. We give a matching lower bound in Section 5. Section 6 concludes and discusses the paper.