الگوریتم تشکیل خوشه برپایه – پویایی برای شبکه های تک کاره وایرلس موبایل
خلاصه
دردهه گذشته تلاشهای زیادی به طراحی الگوریتم های کارا برای خوشه بندی شبکه های تک کاره وایرلس موبایل(MANET) اختصاص داده شده است که مشخصات پویایی شبکه را لحاظ میکنند. هرچند در الگوریتم های موجود فرض میشود که پارامترهای پویایی شبکه ها ثابت میباشند درحالیکه آنها احتمالی میباشند و با زمان تغییر میکنند. لذا الگوریتمهای خوشه بندی پیشنهادی در MANET های واقع گرایانه که در آنها پارامترهای پویایی میزبانها بطور آزادانه و تصادفی در هر زمانی تغییر میکند بخوبی مقیاس نمیشوند. اگر ما فرض کنیم که جهت حرکت و سرعت پویایی میزبانها متغیرهای تصادفی میباشند، پیداکردن راه حل بهینه برای مسئله تشکیل خوشه بطور باورنکردنی مشکل میباشد. این امر سخت تر میشود هنگامیکه فرض میشود که تابع توزیع احتمال این متغیرهای تصادفی نامشخص باشد. در این مقاله ما یک الگوریتم تشکیل خوشه وزن شده برپایه- ماشین یادگیری (learning automata) را پیشنهاد میکند که به آن MCFA میگویند که درآن فرض میشود که پارامترهای پویایی میزبانها متغیرهای تصادفی با توزیع های نامشخص باشند. در الگوریتم خوشه بندی پیشنهادی ، پویایی نسبی موردانتظار هر میزبان نسبت به تمام همسایگان بوسیله نمونه گیری از پارامترهای توزیع شده اش در بازه های مختلف پیش بینی میشود. نمونه گیری MCFA یک الگوریتم بطور کامل توزیع شده میباشد که در آن هر موبایل بطور مستقل میزبان همسایه را با پویایی نسبی موردانتظار حداقلی بعنوان سر-خوشه اش انتخاب میکند. این امر فقط براساس اطلاعات محلی که هر میزبان از همسایگانش دریافت میکند انجام میشود و میزبانها نیاز دارند تا همگام (همزمان) نباشند. نتایج آزمایشی برتری MCFA بر بهترین الگوریتمهای خوشه بندی برپایه-پویایی موجود را از نظر تعداد خوشه ها، طول عمر خوشه، نرخ اتصال مجدد (reaffiliation rate)، و سرریز پیام کنترل(control message overhead) نشان میدهد.
1. مقدمه
تغییرات مکان شناسی شبکه دینامیک، پویایی شبکه، محدودیت های سخت برروی منابع شبکه نظیر پهنای باند کانال ارتباطات، قدرت پیشروی، و عمر باتری، و کمبود یک زیرساخت ثابت یا مدیریت متمرکزشده، مهمترین موضوعات چالش برانگیزی میباشند که پروتوکولهای شبکه تک کاره(ad hoc) آنرا تحمل مینمایند. یک شبکه تک کاره موبایل یک شبکه ارتباطی وایرلس چندهوپی (مالتی هاپ) میباشد که از یک کلکسیون از میزبانهای موبایل پشتیبانی میکند که میتواند بطور فوری در وضعیتهایی که در آن هم یک زیرساخت ثابت موجود نمیباشد (نظیر بازیابی حادثه) و هم یک زیرساخت ثابت بسختی نصب میشود (نظیر میدان های جنگ) توسعه داده شود. دو میزبان میتوانند بطور مستقیم ارتباط برقرار کنند اگر آنها در محدوده ارسال همدیگر باشند و در غیراینصورت (هنگامیکه منبع بخاطر محدودیت محدوده ارسال رادیویی نمیتواند بطور مستقیم پاکتها را به مقصد بفرستند) میزبانهای واسطه نقش مسیریاب را برعهده میگیرند و پاکتها را بسمت مقصدهای نهایی بازپخش میکنند. لذا هر گره در یک MANET بعنوان هم میزبان و هم مسیریاب عمل میکند. درکنار طبیعت چند-هوپی MANET و کمبود یک زیرساخت ثابت، این شبکه ها مشکلات سنتی سیستمهای ارتباط موبایلی و وایرلس را به ارث میبرند. پویایی میزبان یک محدوده وسیعی از چالشهای جدید در طراحی پروتوکولهای MANET را میاورد. تغییرات مکان شناسی متناوب و بسختی قابل پیش بینی ناشی از پویایی میزبان و محدودیتهای شدید منبع مهمترین موضوعاتی اند که باید در شبکه سازی تک کاره موبایل موردلحاظ قرار بگیرند [14,22,28].
Abstract
In the last decade, numerous efforts have been devoted to design efficient algorithms for clustering the wireless mobile ad-hoc networks (MANET) considering the network mobility characteristics. However, in existing algorithms, it is assumed that the mobility parameters of the networks are fixed, while they are stochastic and vary with time indeed. Therefore, the proposed clustering algorithms do not scale well in realistic MANETs, where the mobility parameters of the hosts freely and randomly change at any time. Finding the optimal solution to the cluster formation problem is incredibly difficult, if we assume that the movement direction and mobility speed of the hosts are random variables. This becomes harder when the probability distribution function of these random variables is assumed to be unknown. In this paper, we propose a learning automatabased weighted cluster formation algorithm called MCFA in which the mobility parameters of the hosts are assumed to be random variables with unknown distributions. In the proposed clustering algorithm, the expected relative mobility of each host with respect to all its neighbors is estimated by sampling its mobility parameters in various epochs. MCFA is a fully distributed algorithm in which each mobile independently chooses the neighboring host with the minimum expected relative mobility as its cluster-head. This is done based solely on the local information each host receives from its neighbors and the hosts need not to be synchronized. The experimental results show the superiority of MCFA over the best existing mobility-based clustering algorithms in terms of the number of clusters, cluster lifetime, reaffiliation rate, and control message overhead.
1 Introduction
Dynamic network topology changes, network mobility, severe constraints on network resources such as communication channel bandwidth, processing power, and battery life, and the lack of a fixed infrastructure or centralized administration are the major challenging issues from which the ad hoc networking protocols suffer. A mobile ad-hoc network is a self-organizing and self-configuring multi-hop wireless communication network supporting a collection of mobile hosts which can be instantly developed in situations where either a fixed infrastructure is unavailable (e.g., disaster recovery), or a fixed infrastructure is difficult to install (e.g., battlefields). Two hosts can directly communicate if they are within the transmission range of each other and otherwise (i.e., when the source can not directly send the packets to the destination due to the limitation of the radio transmission range) the intermediate hosts assume the role of router and relay the packets toward the final destinations. Hence, each node in a MANET acts as both host and router. Besides the multi-hop nature of the MANET and the lack of a fixed infrastructure, these networks inherit the traditional problems of the wireless and mobile communication systems. Host mobility brings about a wide range of new challenges in the design of the MANET protocols. Frequent and hard to predict topology changes due to the host mobility, and sever resource constraints are the most important issues must be taken into consideration in mobile ad-hoc networking [14, 22, 28].
خلاصه
1. مقدمه
2. پیش زمینه ها و مقدمات
2.1 کارهای مرتبط
2.2 تئوری ماشین یادگیری
2.3 پویایی نسبی مورد انتظار
3. توضیح الگوریتم خوشه بندی
3.1 خوشه بندی اولیه
3.2 نگهداری خوشه
4. نتایج آزمایشی
4.1 تعداد خوشه ها
4.2 طول عمر خوشه
4.3 نرخ اتصال مجدد
4.4 سرریز پیام کنترل
5. نتیجه
Abstract
1 Introduction
2 Backgrounds and preliminaries
2.1 Related work
2.2 Learning automata theory
2.3 Expected relative mobility
3 Description of clustering algorithm
3.1 Initial clustering
3.2 Cluster maintenance
4 Experimental results
4.1 Number of clusters
4.2 Cluster lifetime
4.3 Reaffiliation rate
4.4 Control message overhead
5 Conclusion
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه