Ad-hoc networks represent distributed systems that comprise wireless nodes which can dynamically self-organize into arbitrary and temporary network topologies, without relying on pre-existing infrastructure, and thus network hierarchy formation via clustering is vital for them. The present article conducts a comprehensive simulation-based evaluation of the performance achieved by a recently proposed, biology-inspired, clustering algorithm used in wireless ad hoc networks, namely the Randomized Beep Based Maximum Independent Set (RanMIS) (Afek et al., 2011). This is the first evaluation done for this high-performance algorithm. The evaluation is done for a set of metrics (measures for protocol cost, backbone description and robustness) some of which has not been used in earlier simulation studies and are developed here. Our study confirms the virtues (message complexity) and reveals the shortcomings of RanMIS(latency issues), and quantifies the impact of some of its administratively-tuned parameters. RanMIS is compared with two representative graph-theoretic node clustering methods and a new one developed here; the results confirm the message optimality of RanMIS, but reveal some shortcomings of it, basically related to the excessive number of rounds that needs to run in order to complete the network clustering

چکیده

شبکه‌های اقتضایی، سیستم‌های توزیع‌شده‌ای را ارائه می‌کند که شامل گره‌های بی‌سیمی هستند که می‌توانند به صورت پویا به توپولوژی‌های شبکه‌ی موقتی و دلخواه، بدون نیاز به زیرساخت‌های پیش‌نیاز، خود-سازمان‌دهی شوند و بنابراین ساخت سلسله‌مراتب شبکه با استفاده از خوشه‌بندی برای آن‌ها ضروری است. مقاله‌ی موجود، یک ارزیابی مبتنی بر شبیه‌سازی کامل، از عملکرد به دست‌آمده توسط یک الگوریتم خوشه‌بندی الهام گرفته شده از بیولوژی اخیر به نام مجموعه مستقل ماکیزمم مبتنی بر صدای تصادفی(RanMIS) که در شبکه‌های بی‌سیم و اقتضایی استفاده شده است را ارائه می‌کند(Afek و همکاران 2011). این اولین ارزیابی انجام شده برای این الگوریتم بسیار کارا می‌باشد. ارزیابی برای یک مجموعه از متریک‌ها (معیارهای هزینه‌ی پروتکل، توضیح استقامت و توانمندی) انجام می‌شود که برخی از آن‌ها در مطالعات شبیه‌سازی قبلی استفاده نشده و در این‌جا توسعه یافته‌اند. مطالعه‌ی ما، مزایا(پیچیدگی پیام) را تأیید می‌کند و نقاط ضعف RanMIS(مباحث تأخیر) را نشان  می‌دهد و اثر برخی از پارامترهای تنظیم شده را مشخص می‌کند. RanMIS با دو روش تکراری خوشه‌بندی گره‌ی نظریه‌ی گراف مقایسه شده و یک روش جدید در این‌جا ایجاد شده است. نتایج، بهینگی پیام RanMIS را تأیید می‌کنند ولی برخی نقاط ضعف آن را نشان می‌دهد که اساساً مربوط به روندهای بسیاری است که به منظور تکمیل خوشه‌بندی شبکه، باید اجرا شوند.

1- مقدمه

یک شبکه‌ی بی‌سیم اقتضایی، نوعی از شبکه‌های بی‌سیم است که در آن پیچیدگی‌های نصب زیرساخت و مدیریت را برطرف کرده‌اند. در این شبکه‌ها هر گره می‌تواند، در هر مکان و در هر زمان و برای هر برنامه‌ای، ایجاد شود و به صورت «در پرواز» به شبکه بپیوندد. ذات غیر متمرکز شبکه‌های بی‌سیم اقتضایی، آن‌ها را برای برنامه‌های کاربردی بسیاری که گره‌های مرکزی نمی توانند به آن‌ها مرتبط باشند، مناسب می‌کند و ممکن است مقیاس پذیری شبکه‌ی  بی‌سیم اقتضایی را در مقایسه با شبکه‌هایی که به صورت بی‌سیم مدیریت می‌شوند، بهبود دهد. کمترین پیکربندی مورد نیاز، به کار اندازی سریع و وجود پروتکل‌های مسیریابی پویا و انطباقی است که به آن‌ها اجازه می‌دهد که سریع تشکیل شوند و شبکه‌های اقتضایی را برای موقعیت‌هایی مانند نظارت محل، نجات از فاجعه، عملیات اجرای قانون، ارتباطات میدان جنگ، تعقیب مسیر و غیره مناسب می‌سازد...