بخشی از مقاله
چکیده
شبکههای فر صتطلبانه زیر مجموعهای از شبکههای تحملپذیر تأخیر میبا شد که در این شبکهها لینکهایارتباطی دائماً قطع و وصل میشوند و حتی ممکن است که هیچ مسیر کاملی از مبدأ به مقصد وجود نداشته باشد و یا فقط برای مدت زمان کوتاه وغیرقابل پیشبینی م سیر وجود دا شته با شد از این رو در شبکههای فر صتطلبانه گرهها از هر فر صت ارتباطی پیشآمده بهره میگیرند و از ارتباطات گامبهگام برای انتقال داده به مقصد استفاده میکنند. چون فرصتهای تماس از دست رفته سبب افزایش تاخیر تحویل* و کاهش نرخ موفقیت† می شود، برای همین در پژوهشهای اخیر برای ت سهیل ارتباط از د ستگاهی به نام جعبهداده† ا ستفاده می شود که افزون بر معیارهای ذکر شده سبب افزایش نرخ د ستیابی به دادهها و افزایش فر صتهای تماس نیز می شود.
به دلیل نبود ارتباط پایدار، یکی از چالشهای مهم در این شبکهها مسئله مسیریابی میباشد . در این مقاله روش جعبهداده مبتنی بر علایق را ارائه دادهایم که دادهها را بر ا ساس علایق گرههای منطقه ذخیره میکند. در روش پی شنهادی، اطلاعات علایق و موقعیت گرههای منطقه بهکار برده می شود همچنین برای یافتن دو ستان از الگوریتم ج ستجوی ممنوعه† نیز ا ستفاده شده ا ست تا د ستیابی به دادهها افزایش یابد و همچنین بسته با تأخیر کمی در شبکه مواجه شود. پارامترهای مذکور با روشهای مسیریابی اپیدمیک محدود شده**،آن ساید†† و ام ال سور†† مقای سه می شود. نتایج حا صل از شبیه سازی تو سط نرمافزار موبیمو†† ن شان میدهد که عملکرد روش پیشنهادی از لحاظ نرخ موفقیت و تأخیر تحویل از سه روش دیگر بهتر میباشد.
کلمات کلیدی:شبکههای تحمل پذیر تاخیر، جعبه داده، مسیریابی، شبکه های فرصتطلبانه
-1 مقدمه
در سالهای اخیر استفاده از دستگاههای قابل حمل نظیر تلفن همراه، تبلت و لپ تاپ و ... رشد چشمگیری داشته اند که برقراری ارتباط بین این دستگاهها به دو روش صورت میگیرد: در روش اول فناوری بیسیم به کاربرده میشود و در روش دوم جابهجایی کاربران نقش رسانهی انتقال داده را ایفا میکند که در روش اول به علت هزینهی زیاد و سختی ایجاد زیرساختهای لازم، سرعت گسترش شبکهها کاهش پیدا میکند. درحالیکه در روش دوم انتقال داده وابسته به فرصتهای برخوردی است که بهوسیلهی جابهجایی گرهها به وجود میآید. گرههای شبکههای فرصتطلبانه، دستگاههای قابلحمل سیاری هستند که ارتباط م یان آن ها از طریق فناوری بیسیمو معمولاً بهصورت غیر همزمان هست و حتی ممکن است هرگز یک مسیر ارتباطی پایدار بین فرستنده و گیرندهی پیام به وجود نیاید.
درنتیجه ارتباط میان گرهها ازنظر زمانی بسیار متغیر بوده و ارسال پیام در آنها با تأخیر زیادی مواجه است. در این شبکهها برای تحویل پیام از الگوریتم ذخیره – حمل - ارسال استفاده میشود؛ یعنی دادهها در بافر گره های متحرک ذخیره شده و همراه با آن ها حمل میشوند و هنگامیکه فرصتی برای ارتباط با گره دیگری به وجود بیاید که بتواند پیام را به مق صد نهایی نزدیکتر کند، به آن گره ار سال شده و آن گره به عنوان گام بعدی تع یین می گردد - Poonguzharselvi and .Vetriselvi 2013 - از این رو در شبکههای فر صتطلبانه گرهها از هر فرصت ارتباطی پیشآمده بهره میبرند و از ارتباطات گامبهگام برای انتقال داده به مقصد استفاده میکنند، به همین دلیل این شبکهها »فرصتطلبانه« نامیده میشوند - . - Huang, Lan, and Tsai 2008
در این شبکهها گرهها هیچ اطلاعاتی از توپولوژی شبکه ندارند و م سیرها صرفاً در هر گره و هنگام ار سال اطلاعات به جلو تعیین می شود. مزیت ا صلی شبکههای فر صتطلبانه این ا ست که در صورت قطع ار سال با شبکه اصلی، همچنان میتوان از ارتباطات نظیربهنظیر برای انتقال داده بهره گرفت و ملزم به دا شتن زیر ساختی برای شبکهها نی ستند. چالشا صلی که طراحان شبکه فر صتطلبانه با آن مواجه ه ستند، چگونگی کاهش تاخیر تحویل میباشد بنابراین لازم هست که به پیام های انتخاب شده برای انتقال به گره های دیگر در طول تماس بی شتر توجه کنند. شبکه های فرصتطلبانه از جابهجایی گرهها و ارتباطات بین گره ها برای پخش داده ها استفاده می کند. تصور کنید که زمین لرزهای اتفاق افتاده است که به زیرساخت های شبکه های تلفن همراه صدمه زده است، به طوری که به مدت طولانی باعث از کارافتادن خدمات رسانی شبکه های تلفن همراه شده است.
تحت چنین سناریوی بحرانی، بازماندگان سعی می کنند با خویشاوندان یا دوستان خود تماس بگیرند تا از ایمنی و سلامت آنها اطمینان حاصل کنند که این باعث ترافیکی بزرگ می شود که ممکن ا ست پهنای باند محدود و ف ضای بافر گره های موبایل را بیش از حد تحمل م صرف کند.در این سناریو پس از زلزله، بازماندگان تمایل دارند که به صورت گروهی برای کمک به دیگران عمل کنند. در این شرایط، تلفن های همراه بازماندگان می توانند یک شبکه فرصتطلبانه ایجاد کند و در این راستا کمک بزرگی ک ند - . - H. Chen and Lou 2014 این نوع شب که ها در سناریوهایی کاربرد دارند که تحمل پذیر تاخیر باشند مثل پروژه ارتباط بین ساکنان منطقه لاپ لند - - Kaur and Mathur 2016 یا پروژه ردگیری گورخرهای وحشی.
جعبه داده نخستین بار در سال 2006 معرفی شد هدف از ارائه جعبه داده افزایش گنجایش شبکه و افزایش فر صتهای تماس بود - . - Zhao et al. 2006 عملکرد آن به این صورت بود که گره ها داده های خود را به جعبه داده تحویل میدادند تا گره دیگر در زمان دیگر و فرصت مناسب پیام را از جعبهداده دریافت کند در نتیجه نرخ تحویل و کارایی شبکه بهطور چشمگیری افزایش مییابد. در نظرگیری علایق و موقع یت گره ها س بب کاهش تاخیر تحو یل ،افزایش نرخ موفقیت میشود . پژوهش های زیادی قبلا به منظور بهبود نرخ تحویل و نرخ موفقیت صورت گرفته است. مقالههایی در زمینه م سیریابی آگاه از اجتماع ارائه شده که مبتنی بر ویژگیهای اجتماعی هستند نظیر مقاله های - Ying et al. 2015 - ، - Wu, Xiao , and Huang 2013 - ، - X. Chen et al. 2016 - ، - - Socievole et al. 2015اما این الگوریتم ها صرفا از تعدادی م شخ صی از ویژگی اجتماعی نظیرمرکزیت و سوابق تماسها استفاده کردند در حالی که در روش پیشنهادی از دو ویژگی اجتماعی گره ها یعنی موقعیت و علایق گره ها جهت ایجاد بهبود استفاده شده است .
1-2 الگوریتم جستجوی ممنوعه
الگوریتم جستجوی ممنوع یک استراتژی جستجوی حافظهای میباشد که برای اولین بار توسط گلوور در سال 1986مطرح شده است. این الگوریتم تقریبا مانند الگوریتم های جستجوی محلی کار میکند، با این تفاوت که برای جلوگیری از دور و ت سل سل در جوابها و افتادن در دام جوابهای بهینه محلی، از مفهومی به نام فهرست ممنوع استفاده میکند. جابهجایی از جواب جاری به جواب همسایه امکانپذیر زمانی انجام می شود که در فهر ست تابو قرار ندا شته با شد. در غیر این صورت، جواب هم سایه دیگری که در ارزیابی جوابهای هم سایه در رده بعدی قرار گرفته ا ست، انتخاب شده و جابهجایی به آن صورت میگیرد . این لیست که دارای ابعادی ثابت یا متغیر می باشد، جابهجاییهای منع شده را نگهداری میکند و کاربرد اصلی آن، پرهیز از همگرا شدن به جوابهای بهینه محلی است. به عبارت دیگر، به کمک فهرست ج ستجوی ممنوعه جابهجایی به جوابهایی که اخیراً ج ستجو شدهاند، ممنوع خواهد شد و فقط بخشهایی از مجموعه جواب که پیش از این مورد بررسی قرار نگرف ته، مد نظر خواه ند بود. نحوه ورود و خروج جوابها به فهر ست ممنوع به صورت ورودی اول خروجی اول ا ست . فرمول محاسبه گام بعدی در رابطه - 1 - آورده شده است.
-2-2جعبهداده مبتنی برعالقهمندی
این بخش دیدگاه ما از الگوریتم پیشنهادی را ارائه می دهد که از موقعیت و ویژگی اجتماعی گره برای برچسب گذاری موضوعات در جعبه داده محلی و انتخاب جعبه داده در شبکه های فرصت طلبانه استفاده می کند. در این بخش ابتدا فرایند انتخاب دوستان معرفی شده است. سپس، فرایند جستجو برای پیام درخواست شده و فرایند برچسب گذاری موضوعات در جعبه داده شرح داده میشود. در نهایت، ج ستجوی پیام درخوا ست شده تو ضیح داده می شود. این الگوریتم برای شبکه فرصتطلبانه که در گرههای سیار از طریق بیسیم یا بلوتوث متصل هستند، قابل استفاده ا ست. استراتژی مسیریابی شامل دو جزء است: فرایند انتخاب دوستان و فرآیند درخواست پیامها. عملکرد اولی به این صورت است که بر اساس زمان های ملاقات گره ها، سه دو ست انتخاب می شود. همچنین به منظور جلوگیری از ایجاد چرخه و عملکرد کاراتر این انتخاب الگوریتم جستجوی ممنوعه نیز به کار برده شده است. عملکرد مولفه دوم، ارسال درخواست توسط گره به گره های دیگر و یا جعبه های داده به منظور یافتن پیام است.
1-2-2 عالیق گره
هر گره دارای یک سری علایق هست مانند فوتبال، فیلم و غیره که گره تمایل دارد با گرههایی ملاقات کند که دارای علایق مشترک هستند. هر گره، گرههایی را در مجاورت خود دارد که هم سایههایش را ت شکیل میدهند که با آنها میتواند ارتباط برقرار کند. در این پژوهش فرض شده است که هر گره با 10 گره دیگر در ارتباط است که هرکدام از این گرهها به یک تعدادی موضوعات علاقهمند هستند. وقتی گره با گره دیگری ملاقات میکند، چون بافر گره ظرفیت محدودی دارد و همچنین زمان ملاقات هم محدود است بر این اساس اگر این گره با گره ملاقات شده علایق مشترک داشته باشد اطلاعات مربوطه را دانلود میکنند، در غیر این صورت از اطلاعات یکدیگر صرفنظر میکنند.
در این روش، گره به علایق دوستان خود هم توجه میکند و اگر موضوعی بود که اکثریت دوستهایش به آن علاقهمند باشند با اینکه خودش بیعلاقه ه ست آن را هم در بافر خود ذخیره میکند و زمانی که با گره جدیدی مواجه می شود علاوه بر علایق خود، علایق دوستهایش را هم به آن گره پیشنهاد میدهد. گره ملاقات شده نیز این علاقهمندی را بررسی میکند اگر علاقهمند باشد دانلود میکند و اگر علاقهمند نباشد صرفنظر میکند. در این پژوهش سه دوست از بین گرههایی که بیشترین تعداد ملاقات را با آنها داشته به عنوان دوست انتخاب میکنیم. مزیت روش پیشنهادی این است که ممکن است دو گرهی که همدیگر را ملاقات میکنند علایق مشترکی نداشته باشند ولی گره بعدی به مو ضوع دو ست گره علاقهمند با شد، در نتیجه اطلاعات مورد علاقهاش را دانلود کند و به این نحو این فرایند ادامه پیدا کند تا زمانی که داده به مقصد تحویل داده شود.
2-2-2 فرایند انتخاب دوست
هر گره علاوه بر بافر یک جدول ملاقات دارد که در ابتدا خالی هست یعنی هیچ دادهای در آن وجود ندارد - مرحله اول - . وقتی با یک گرهی ملاقات کرد یک درایه جدید برای گره ایجاد میکند و آن گره را به جدول ملاقات خود اضافه میکند و هر بار که اینگره را مجدداً ملاقات میکند، یک واحد به مقدار درایه گره افزوده می شود - مرحله دوم - . یک بازه زمانی W به مدتزمان دو ساعت فرض میکنیم که این بازه در واقع بازه یادگیری هست و در این بازه زمانی، گره اطلاعات را جمعآوری میکند در مدت زمانی که این بازهی زمانی به اتمام نر سیده ا ست گره به جمعآوری اطلاعات درباره تعداد ملاقات ادامه میدهد و اگر با گرهی ملاقاتی صورت گرفت فقط موضوعاتی را که خودش علاقهمند هست و در بافرش هست را به آن گره معرفی میکند. زمانی که این مدت یادگیری به پایان رسید، گره تعداد ملاقات را به صورت نزولی مرتب میکند - مرحله سوم - . سه گرهی که بی شتر ملاقات دا شته ا ست را به عنوان دوست خود در نظر میگیرد - مرحله چهارم - . اگر تعداد ملاقات
