ترجمه مقاله مسیریابی ویژه متحرک هندسی Asymptotically Optimal Geometric Mobile AdHoc Routing

مسیریابی ویژه متحرک هندسی مسیریابی ویژه متحرک هندسی Asymptotically Optimal Geometric Mobile AdHoc Routing

مسیریابی ویژه متحرک هندسی Asymptotically Optimal Geometric Mobile AdHoc Routing

مسیریابی ویژه (Ad-hoc) متحرک هندسی بهینه ویژه)

خلاصه :

در این مقاله ما اطلاعاتی را در مورد AFR برای شما بیان می کنیم . AFR یک وسیله متحرک هندسی جدید است که الگوریتم را مسیر یابی می کنیم الگوریتم بطور کامل توزیع شده است (پراکنده شده است) گره ها باید فقط با همسایه های مستقیم شان که در محدوده انتقال آنها قرار دارند در تماس بوده و ارتتباط برقرار کنند ما نشان می دهیم که اگر بهترین مسیر AFR است که هزینه ای به مقدار C دارد ، ترمینال هایی که ارزشی به اندازه O (c2) دارند بدترین مورد می باشند AFR یک الگوریتم rst با هزینه است که بوسیله عملکرد یک مسیر بهینه و مطلوب محدود شده است.

ما همچنین با نشان دادن این موضوع که هر الگوریتم مسیریابی مهندسی بدترین ارزش و هزینه را دارد یعنی (c2) یک محدوده زیرین محکم و استواری را ارائه می دهیم بنابراین AFR کاملا مطلوب و بهینه است ما یک الگوریتم غیر هندسی را ارائه می دهیم که با محدوده (مرز- حدود ) زیرین هم مطابقت دارد اما مقداری حافظه در هر گره نیاز دارد این مطلب باعث بوجود آمدن یک تجارت وسوسه گر بین هندسه و حافظه می گردد.

– طبقه بندیها و توصیفهای موضوعات:

F.2.2 ( تجزیه و تحلیل الگوریتم ها و مشکلات پیچیده ) الگوریتم های غیر عددی و مشکلات و مسائل آن .

مسائل هندسی و محاسبات . مسیر یابی و طرح C.22.2 .(شبکه های ارتباطی کامپیوتر ): پروتکل های شبکه ای (شبکه ) پروتکل های مسیر یابی

ABSTRACTIn this paper we present AFR a new geometric mobile adhocrouting algorithm. The algorithm is completely distributed;nodes need to communicate only with direct neighborsin their transmission range. We show that if a bestroute has cost c AFR nds a route and terminates withcost O(c2) in the worst case. AFR is the rst algorithmwith cost bounded by a function of the optimal route. Wealso give a tight lower bound by showing that any geometricrouting algorithm has worst-case cost(c2). Thus AFR isasymptotically optimal. We give a non-geometric algorithmthat also matches the lower bound but needs some memoryat each node. This establishes an intriguing trade-o between geometry and memory

ABSTRACTIn this paper we present AFR a new geometric mobile adhocrouting algorithm. The algorithm is completely distributed;nodes need to communicate only with direct neighborsin their transmission range. We show that if a bestroute has cost c AFR nds a route and terminates withcost O(c2) in the worst case. AFR is the rst algorithmwith cost bounded by a function of the optimal route. Wealso give a tight lower bound by showing that any geometricrouting algorithm has worst-case cost(c2). Thus AFR isasymptotically optimal. We give a non-geometric algorithmthat also matches the lower bound but needs some memoryat each node. This establishes an intriguing trade-obetween geometry and memory