در دهه‌های اخیر کارایی برنامه نویسی خطی عددی ((Integer Linear Programming)) (ILP) و ارضا کننده عددی منطقی ((Boolean Satisfiability ))(SAT) بهبود یافته است. این بهبودها باعث ترغیب کاربرد تکنولوژی SAT و ILP برای مدل کردن مسائل پیچیده مهندسی شده است. یکی از این مسائل٬ مسئله خوشه‌بندی در شبکه بدون زیرساخت متحرک (MANETs) است. مسئله خوشه‌بندی در MANETs شامل انتخاب گره با بیشترین ثبات برای سرخوشه شدن در توپولوژی MANETs و اطمینان از برقراری ارتباط منظم با سرخوشه است تا طول عمر شبکه حداکثر شود. در این مقاله٬ پیشنهاد شده فرمول ILP بهبود یافته را برای مسئله خوشه بندی گسترش بدهیم. بعلاوه٬ پیشرفت‌های متنوعی با گسترش بهبود فرمول بندی٬ شامل ثبات ارتباط بین خوشه‌ای٬ اتصالات چند گامی و تحمیل محدودیت پوششی بوجود امده است. بهبود و افزایش شکل‌دهی بوسیله ابزار طراحی ایجاد مجازی توپولوژی شبکه و خوشه‌ی آنها با استفاده از هنر کلی حل کننده های ILP عمومی و SAT است. این ابزار٬ برای استفاده از فرمول بندی (شکل دهی) و بهبود طول عمر واقعی در محیط عملی ارزیابی٬ مناسب است. مشاهده شد که ILP عمومی٬ CPLEX و SCIP میتوان توپولوژی شبکه‌های بزرگ را به پایه ۰-۱ منطقی حل کننده ILP منتقل (handle) کند و BSOLO مقیاس کوچکی از شبکه را منتقل (handling) می‌کند. همچنین بهبود شکل‌دهی اجازه ایجاد راه‌حل پیچیدگی شبکه و مناسب برای شبکه‌های کوچک مقیاس٬ در زمان ایجاد راه حل مرتبط بدون مشاهده محدودکننده در محیط تمرینی٬ مشاهده شد

کلمات کلیدی:

  1. مقدمه:

در دهه اخیر٬ حل کننده‌های برنامه نویسی خطی عددی (ILP) و ارضا کننده عددی منطقی (SAT) در معرفی الگوریتم‌های هوشمند جدید٬ بخاطر امکان حل طیف بسیاری از مسائل مهندسی دارای چالش و پیچیده بهبود عمده‌ای بخشیدند. در صورتیکه ILP-عمومی برای حل کردن از مدل حل کننده ILP مثل مسئله طول عمر بهینه بکار برده شود نسبتا شبیه استفاده از حل کننده SAT است. یکی از این مسائل٬ مسئله خوشه‌بندی در شبکه‌های متحرک بدون زیرساخت (MANETs) است.

MANETs کاربرد‌های وسیعی مثل ارتباطات در میدان جنگ٬ اجرای قانون و بازیابی بعد از فاجعه دارد. خوشه‌بندی در MANETs بطور سنتی با هدف حل موضوع مقیاس پذیری MANETs مسطح و افزایش طول عمر شبکه همراه بوده است. خوشه‌بندی درگیر ایجاد شبکه سلسله مراتبی٬ جایی که شبکه به خوشه‌ها تقسیم می‌شود٬ بهمراه انتخاب گره‌ مطمئن برای هر خوشه به عنوان سرخوشه٬ است. در این پردازش٬ انتخاب گره‌هایی که بهترین موقعیت را دارند برای سرخوشه شدن و گره‌هایی که باید منظم به سرخوشه‌ای که میشناسند متصل بشوند٬ از مسائل مهم خوشه‌بندی است. مسئله خوشه‌بندی می‌تواند بوسیله ILP به مسئله‌ای بهینه مدل شود.

این نکته اهمیت دارد که فرمول ILP حدس زده شده و راه حل ارائه شده برای مسئله خوشه‌بندی در سناریوی زمان واقعی بستگی ندارد. بهرحال کاری که شامل ۴ مرحله کلیدی زیر باشد مفید است: ۱) فرمول‌بندی بسیاری از کاربردهای متنوع مسئله خوشه‌بندی در MANETs٬ صحبت کردن درباره محدودیت‌های واقعی حسابرسی(account)٬ ارائه پایه ریاضی محکم و قوی برای مسئله خوشه‌بندی؛ ۲) ارائه محیط کاری بهینه تا به بقیه محققین اجازه داده شود تا حدس هوشمندانه هیوریستیکی و متا-هیوریستیکی بزنند و نتایج خودشان را با راه بهینه‌ای که ما فراهم آورده‌ایم مقایسه کنند؛ ۳) معرفی یک مقایسه وسیع و جامع از ارزیابی کارآیی وضعیت-هنر حل کننده ILP (که به پایه ۰-۱ SAT-منطقی مربوط شده) برای هدایت کردن فرمول‌بندی ILP پیشنهادی و حدس زدن کاری که تحت این شرایط باشد؛ و ۴) طراحی و گسترش محیط ملموس می‌باشد تا اجازه ایجاد توپولوژی سفارشی٬ یکپارچه کردن حل کننده‌های ILP-عمومی و ILP-براساس SATمنطقی٬ و توانایی مشاهده راه‌حل مجازی ارائه شده برای فرمولاسیون ILP برای توپولوژی شبکه٬ را بدهد.

این مقاله به این صورت سازماندهی شده است. در بخش ۲ اطلاعات کلی از ILP و SAT و کاربرد آنها ارائه شده است. همچنین مقدمه‌ای از MANETs و تعریف مسئله خوشه‌بندی آن است. در بخش ۳ کارهای موجود که از فرمولاسیون ILP برای مدل کردن مسئله خوشه‌بندی استفاده کرده‌اند را پوشش داده‌است. بخش ۴ فرمولاسیون ILP پیشنهادی برای مسئله خوشه‌بندی در MANETs را توضیح داده و جزئیات افزایش (بهبود) طرح پیشنهادی شامل برقراری امکان ارتباطات بین خوشه‌ای٬ ارتباطات چندگامی و محدودیت پوششی است. در بخش ۵ آزمایشات انجام شده و نتایج متناظر آن و نتیجه گیری ارائه شده است. بخش ۵ در این مقاله نیز شامل ارائه کارهای آینده است.

  1. پس زمینه
  2. برنامه نویسی خطی عددی و ارضا کننده منطقی

برنامه نویسی خطی عددی (ILP) شامل حداکثر رساندن یا به حداقل رساندن یک تابع با توجه به محدودیت‌های خاص در آن تابع مطلوب و محدودیت‌های خطی هستند و متغیرهای استفاده شده تنها می‌تواند مقادیر صحیح را بگیرد{۲}. مواردی که مقادیر صحیح محدود به (۱-۰) هستند را برنامه نویسی خطی باینری می‌گویند. در ارضا کننده منطقی(SAT) محدودیت‌های بین متغییرها با استفاده از (سوال) چه(کدام- what) را منطق گزاره‌ای می‌نامند. منظق گزاره شامل استفاده از عملیات یا (OR) ٬ و (AND) ٬ نه(NOT) برای ساخت فرمول-محاسبه(Products-of-Sums) و یا رابط فرم نرمال(CNF) است. متغیرها فقط می‌توانند مقادیر دودویی (۱-۰) را بگیرند.

با توجه به محدودیت‌های بیان شده در CNF٬ هدف شناسایی یک انتساب متغیر است که تمام محدودیت‌ها در مسئله را برآورده کند و یا ثابت کند که چنین انتسابی وجود ندارد. در یک فرمول گزاره‌ای٬ nمتغیر داده می‌شود درحالی که n۲ متغییر مختلف وجود دارد. به منظور حل و یا راضی کردن فرمول٬ SAT را از طریق فضای جستجو بروید و تعیین کنید که آیا یک متغییر رضایت بخش برای انتساب وجود دارد یا خیر. فن‌آوری تصمیم‌گیری‌ هیوریستیکی پیشرفته و تکنیک‌های پیشرفته تشخیص درگیری هوشمند را می‌توان برای جلوگیری از جستجو کل درخت n۲ تخصیص داده شده٬ مورد استفاده قرار داد.

در حالی که حل کننده SAT به طور سنتی برای حل مسئله تصمیم‌گیری استفاده شده است٬ اخیراً حل‌کننده SAT برای محدودیت‌های شبه بولی (PB) گسترش داده شده است{۳}{۴} که نامساوی ساده هستند همانند معادله ILP که با محدودیت ۰-۱ هست.

محدودیت‌های شبه بولی (PB) می‌توانند با تعدادی از محدودیت‌های نمایی CNFجایگزین شوند. یکی دیگر از مزیت کلیدی محدودیتهای PB توانایی بیان مسائل بهینه سازی که به طور سنتی برای مشکلات ILP به کار گرفته می‌شوند٬ است. مطالعات نشان داده‌اند که حل کننده ILP براساس ۰-۱ SAT می‌تواند با حل‌کننده ILP عمومی مبتنی بر بهترین دردسترس٬ برای حل مسئله ILP ٬ ۰-۱ ٬ ناشی از برنامه‌های کاربردی خاص٬ رقابت کند{۳}{۴}. پیشرفت‌های اخیر در حل‌کننده‌های SAT بعلاوه افزایش فزاینده مقرون به صرفه بودن قدرت محاسباتی بالا٬ باعث شده است که مشکلات بزرگتر در برنامه‌های کاربردی در حوزه‌های مختلف حل شوند. این کاربردها شامل بهینه سازی مصرف انرژی {۵}٬ FPGA {۶}٬ نفوذ به شبکه{۷}٬ کنترل دسترسی {۸}٬ رمزنگاری{۹}٬ نرم افزار نقشه برداری {۱۰}٬ ژنتیک {۱۱} و زمانبندی{۱۲} است.

 

  1. شبکه بدون زیرساخت متحرک و مسئله خوشه‌بندی

MANETها٬ شبکه‌های بی‌سیم٬ خود سازمانده متشکل از گره‌های متحرک با محدودیت عمومی عرضه/ذخیره انرژی هستند. این گره‌ها برای مثال می‌توانند لبتاپ٬ پایانه‌های تلفن همراه و یا دستگاه‌های دیگرکه بطور کلی توسط انسان‌ها استفاده می‌شود٬ باشند{۱۳}. MANETها برای برقراری ارتباطی پایدار٬ مقیاس پذیر٬ توپولوژی انعطاف پذیربا چالش‌های متعددی مواجه هستند. در طول این سالها تحقیقات زیادی شده است که MANETها را قادر بسازند تا در وضعیت بهینه عمل کنند٬ به عنوان مثال٬ به حداقل رساندن مصرف انرژی و اساساً تلاش برای رسیدن به حداکثر طول عمر شبکه از طریق بهینه سازی شکل‌گیری خوشه٬ مسیریابی و ارتباطی انجام شده است. در ابتدا توپولوژی شبکه MANET بصورت تخت و یا بدون سلسله مراتبی بود که در آن تمام گره‌ها نقش یکسانی داشتند. از طریق آزمایش و شبیه سازی سناریوهای مختلف نشان داده شد که زمانی که تعداد گره‌ها در شبکه تخت افزایش می‌یابد٬ توان به شدت کاهش می‌یابد {۱۴}.

علاوه بر این٬ عواملی مانند شکست مکرر مسیر٬ تغییر توپولوژی غیر قابل پیش‌بینی و سربار مسیریابی باعث مشکل شدن برای توپولوژی مسطح مقیاس پذیر می‌شود{۱۵}. مفهوم خوشه‌بندی برای غلبه بر محدودیت مقیاس پذیری در یک شبکه تخت معرفی شده است. خوشه‌بندی شامل تقسیم شبکه به خوشه‌ها با گره‌های خاص در هر خوشه انتخاب شده برای سرخوشه شدن است. سرخوشه مسئولیت مدیریت ارتباطات و مسیریابی برای خوشه‌ای خاص را دارد. در نتیجه انتخاب سرخوشه بسیار مهم است{۱۶}. از طریق این پیکربندی سلسله مراتبی شبکه٬ خوشه‌بندی دارای مزیت کاهش پیچیدگی محاسباتی شبکه‌های زیربنایی و کاهش اثرات تحرک بوسیله ساخت یک توپولوژی شبکه متحرک که به ظاهر نسبتاً ثابت به نظر برسد. اهمیت ویژه آن محدودیت‌های مربوط به اتصال به شبکه و حفظ انرژی آن است{۱۷}. خوشه‌بندی همچنین دارای مزیت کاهش سربار ذخیره سازی اطلاعات برای گره به طور منظم است و گره نیاز به آگاه بودن از تغییر محلی(تغییر در خوشه) است٬ و نیازی به تغییرات سراسری(کلی) نیست (تغییراتی که در خوشه‌های دیگر اتفاق می‌افتد){۱۸}.

علاوه بر دستیابی به بهبود مقیاس پذیری بیشتر از شبکه‌های تخت٬ خوشه‌بندی را قادر می‌سازد از پهنای باند ارتباطی بین خوشه‌ای به وسیله محدود کردن سرخوشه‌ها٬ حفاظت کند. همچنین ممکن است برای سرخوشه‌ها٬ استراتژی‌های بهینه سازی محلی پیاده سازی شود تا گره را در یک خوشه برای رسیدن به طول عمر مطلوب٬ قادر سازد. در برنامه‌های کاربردی مانند شبکه‌های حسگر بی‌سیم () که در آن ممکن است حسگرها مناطق تحت پوششان با هم تداخل داشته باشند٬ سرخوشه‌ها می‌توانند گره‌ی خاصی در خوشه خود را می‌تواند به حالت فعال و یا حالت خواب ببرند درنتیجه طول عمر شبکه بهبود یافته و داده‌های جمع اوری شده تکراری(تقلیدی) کاهش یابند{۱۹}.

در {۱۸} نویسندگان یک برشی از روش‌های مختلف دسته‌بندی و تکنیک خوشه‌بندی را ارائه داده‌اند. از جمله:

  • مجموعه تسلط(DS) براساس گره: تاکید بر کاهش پیچیدگی مسیریابی.
  • خوشه‌بندی با تعمیر و نگهداری کم: تاکید بر به حداقل رساندن هزینه تعمیر و نگهداری خوشه.
  • خوشه‌بندی با آگاهی از تحرک: تاکید بر ترکیب رفتار حرکتی گره‌ها در پردازش خوشه‌بندی به منظور افزایش ثبات خوشه و حداکثر کردن زمان قبل از نیاز به خوشه‌بندی دوباره.
  • صرفه جویی در انرژی خوشه: تاکید بر دستیابی به حداکثر طول عمر شبکه.
  • خوشه‌بندی تعادل بار: تاکید بر توزیع برابر بار بین سرخوشه‌ها.
  • خوشه‌بندی مبتنی بر ترکیب معیارها: تاکید بر بهینه سازی طول عمر شبکه بوسیله ترکیب معیارهای متعددی که تحت تاثیر انتخاب سرخوشه قرار دارد مانند انرژی اولیه٬ انرژی باقی مانده٬ ترافیک و تحرک.

بسته به ماهیت کاربرد٬ الگوریتم خوشه‌بندی همچنین ممکن است به عوامل دیگری که نیاز به بهینه سازی دارند نیز تمرکز کنند{۱۹}.

  • مقدار حداقلی خوشه: تاکید بر به حداقل رساندن تعداد خوشه‌ها با توجه به اینکه در شبکه‌های ناهمگن که گره‌های قدرتمندی وجود دارد که مناسب سرخوشه شدن هستند اما این گره‌ها گران هستند و باید مقادیر محدودی از آنها مستقر شوند. تمرکز بر به حداقل رساندن تعداد خوشه‌ها (یا به حداقل رساندن هزینه) و به حداکثر رساندن طول عمر شبکه است
  • افزایش اتصال: تاکید بر تضمین این که تمام گره‌های شبکه دارای مسیرهای موجود٬ از طریق اتصال سرخوشه‌های خود به جمع کننده ((چاهک))(sink) و یا ایستگاه پایه هستند. این ویژگی در شبکه‌های حسگر بی‌سیم حساس که در آن هر گره باید یک مسیر کارآمد به یک جمع کننده (sink) از پیش تعیین شده٬ داشته باشند.

از آنجا که سرخوشه عمدتاً مسئول مسیریابی٬ مدیریت خوشه خود٬ رله(هدایت) کردن پیام از/به خوشه‌های دیگر است انرژی باقی مانده خود را سریعتر از بقیه گره‌ها از دست می‌دهد. از این رو٬ انتخاب سرخوشه دیگر برای مدیریت خوشه یا گاهی اوقات خوشه‌بندی دوباره کل شبکه یک عملیات لازم است. یکی دیگر از دلایل خوشه‌بندی دوباره ممکن است بخاطر تحرک گره‌ها (یا سرخوشه‌ها) باشد که در آن برخی گره‌ها ممکن است به خارج از محدوده یک سرخوشه برود و به محدوده دیگری وارد شود و در نتیجه توپولوژی شبکه باید بر این اساس تنظیم شود. در نتیجه٬ خوشه‌بندی دوباره به یک فاکتور مهم در مسئله خوشه‌بندی بهینه با هدف رسیدن به تحمل خطا٬ تبدیل شده است. اما خوشه‌بندی دوباره به منابع شدید و اختلال شبکه نیاز دارد. بنابراین٬ در موردی که٬ پیکربندی مقاوم در برابر خطا با کارآیی بالا٬ نیاز است٬ بهتر است که شامل انتخاب سرخوشه‌های پشتیبان در طول فرایند خوشه‌بندی باشد.