مقاله یک الگوریتم تشکیل خوشه برپایه – پویایی برای شبکه های تک کاره وایرلس موبایل (2011 اشپرینگر)

1. مقدمه

2. پیش زمینه ها و مقدمات

2.1 کارهای مرتبط

2.2 تئوری ماشین یادگیری

2.3 پویایی نسبی مورد انتظار

3. توضیح الگوریتم خوشه بندی

3.1 خوشه بندی اولیه

3.2 نگهداری خوشه

3.2.1 اتصال شبکه

3.2.2 ترک کردن شبکه

4. نتایج آزمایشی

4.1 تعداد خوشه ها

4.2 طول عمر خوشه

4.3 نرخ اتصال مجدد

4.4 سرریز پیام کنترل

5. نتیجه

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.

دردهه گذشته تلاشهای زیادی به طراحی الگوریتم های کارا برای خوشه بندی شبکه های تک کاره وایرلس موبایل(MANET) اختصاص داده شده است که مشخصات پویایی شبکه را لحاظ میکنند. هرچند در الگوریتم های موجود فرض میشود که پارامترهای پویایی شبکه ها ثابت میباشند درحالیکه آنها احتمالی میباشند و با زمان تغییر میکنند. لذا الگوریتمهای خوشه بندی پیشنهادی در MANET های واقع گرایانه که در آنها پارامترهای پویایی میزبانها بطور آزادانه و تصادفی در هر زمانی تغییر میکند بخوبی مقیاس نمیشوند. اگر ما فرض کنیم که جهت حرکت و سرعت پویایی میزبانها متغیرهای تصادفی میباشند، پیداکردن راه حل بهینه برای مسئله تشکیل خوشه بطور باورنکردنی مشکل میباشد. این امر سخت تر میشود هنگامیکه فرض میشود که تابع توزیع احتمال این متغیرهای تصادفی نامشخص باشد. در این مقاله ما یک الگوریتم تشکیل خوشه وزن شده برپایه- ماشین یادگیری (learning automata) را پیشنهاد میکند که به آن MCFA میگویند که درآن فرض میشود که پارامترهای پویایی میزبانها متغیرهای تصادفی با توزیع های نامشخص باشند. در الگوریتم خوشه بندی پیشنهادی ، پویایی نسبی موردانتظار هر میزبان نسبت به تمام همسایگان بوسیله نمونه گیری از پارامترهای توزیع شده اش در بازه های مختلف پیش بینی میشود. نمونه گیری MCFA یک الگوریتم بطور کامل توزیع شده میباشد که در آن هر موبایل بطور مستقل میزبان همسایه را با پویایی نسبی موردانتظار حداقلی بعنوان سر-خوشه اش انتخاب میکند. این امر فقط براساس اطلاعات محلی که هر میزبان از همسایگانش دریافت میکند انجام میشود و میزبانها نیاز دارند تا همگام (همزمان) نباشند. نتایج آزمایشی برتری MCFA بر بهترین الگوریتمهای خوشه بندی برپایه-پویایی موجود را از نظر تعداد خوشه ها، طول عمر خوشه، نرخ اتصال مجدد (reaffiliation rate)، و سرریز پیام کنترل(control message overhead) نشان میدهد.