بخشی از مقاله
چکیده
شبکههای اجتماعی متحرک نقش مهمی در زندگی شخصی و اجتماعی انسانها ایفا میکنند. دلیل رشد چشمگیر این شبکهها، ارتباطی است که این شبکهها بین تکنولوژی تلفن همراه و علوم اجتماعی برقرار میکنند. یکی از مهمترین چالشهای موجود در شبکههای اجتماعی سیار، توجه به نحوه مسیریابی پیامها با در نظر گرفتن شرایط و توپولوژیهای این شبکهها است. در روشهای قبلی فرض بر این بود که وقتی دو گره یکدیگر را ملاقات میکنند فقط یکی از آنها بستهای برای ارسال دارد. به عبارت دیگر نقش گره ارسال کننده و دریافت کننده از قبل مشخص است. درصورتی که ممکن است دو گرهای که همدیگر را ملاقات میکنند ممکن است هر دو در بافرهایشان بستههایی برای ارسال داشته باشند.
اینکه هردوی این گرهها بستههای خود را ارسال کنند عملی نیست. چرا که گرهها متحرک هستند و زمان کافی برای ارسال توسط هر دو گره وجود ندارد. در این مقاله روشی ارائه شدهاست که بر اساس وابستگی بین گره و بسته، ارسالکننده و دریافتکننده تشخیص داده میشود. به همین منظور در هنگام ملاقات گرهها، وابستگی هر بسته به گره حامل بسته و گره مقابل محاسبه میشود. سپس نسبت این دو عدد محاسبه شده و مقدار هر کدام که کمتر باشد آن گره به عنوان ارسالکننده انتخاب شده و بسته با مقدار کمتر ارسال میشود. نتایج شبیهسازی نشان میدهد که کارایی روش پیشنهادی براساس معیارهای میانگین تأخیر و نسبت تحویل درمقایسه با روشهای مشابه بهبود یافته است.
کلمات کلیدی: شبکههای اجتماعی سیار، مسیریابی، گره ارسالکننده،گره دریافتکننده.
-1 مقدمه
مقاله در پنج بخش سازماندهی شده ا ست، در بخش دوم مروری بر روی کارهای تحقیقاتی پیشین در زمینه مسیربابی شبکههای اجتماعی سیار شده ا ست. در بخش سوم روش پی شنهادی با جزئیات کامل بررسی میشود. در بخش چهارم، ارزیابی کارایی روش پیشنهادی به همراه مقایسه آن با برخی از سیاستهای موجود بر اساس پارامترهای مورد ارزیابی مانند نسبت تحویل و میانگین تاخیر نشان داده شده ا ست. در بخش پنجم جمعبندی کلی از روش پی شنهادی به همراه زمینههای کارهای آتی تنظیم و ارائه شده است.
-2 کارهای مرتبط
شبکههای اجتماعی متحرک به دلیل وجود انواع خدمات تحویل دادهای و ویژگیهای خاص خود روشهای مسیریابی متفاوتی نسبت به شبکههای سنتی دارند. در طراحی پروتکلهای مسیریابی این شبکههاسعی بر این است تا نسبت تحویل پیام با توجه به توپولوژی پویای شبکه افزایش یابد. در این راستا کارهایی انجام شده است.مسیریابی 2SimBet این روش مبتنی بر اطلاعات محلی و روابط دوستانه بین گرهها است. گرههایی را که میتوانند به عنوان پل ارتباطی بین گروههای غیرمتصل به هم باشند را شناسایی کرده و با استفاده از آنها ارتباط بین این گروهها را برقرار میسازد. برای شناسایی پلهای بین گروهها ابتدا مرکزیت گرهها را محاسبه میکنیم.
همانطورکه در نظریهی گرافها مرکزیت میزان اهمیت یک رأس در گراف است؛ در یک شبکهی اجتماعی مرکزیت میتواند نشانگردرجهی3 اهمیت یک فرد باشد.. یک گره مرکزی توانایی بیشتری برای برقراری ارتباط بین اعضای دیگر شبکه دارد.اندازههای مرکزیت عبارتند از: درجهی مرکزیت، نزدیکی4 مرکزیت، میانی مرکزیت. به تعداد روابط مستقیم یک گره درجهی مرکزیت گفته میشود. گرهی که درجهی مرکزیت بالایی داشته باشد، امکان ملاقاتهای بیشتری با گرههای دیگر شبکه دارد؛ چنین گرهی میتواند به عنوان مجرای تبادل اطلاعات عمل کند؛ در حالیکه گرههای محیطی ارتباط کمتری با گرههای دیگر دارند و در حاشیههای شبکه جای میگیرند .
معیار دیگر، نزدیکی مرکزیت میباشد که برابر معکوس میانگین کوتاهترین فاصلهی هر گره با تکتک گرههای دیگر است. این مقدار نشان میدهد که توزیع بسته از یک گره تا گرههای دیگر چقدر طول میکشد. میانی5 مرکزیت نشان میدهد که یک گره چقدر میتواند باعث ارتباط بین گرههایی شود که بهطور مستقیم باهم درارتباط نیستند.[2]الگوریتم بعدی ML-SOR میباشد.این الگوریتم از سه لایه شبکه اجتماعی استفاده میکند: شبکه تماس، شبکه های اجتماعی آنلاین و علاقهمندی شبکه. شبکه تماس نمودار نزدیکی می باشد که از طریق تماس بین دستگاهها ایجاد میگردد، در حالی که شبکههای اجتماعی آنلاین از تماسهای مجازی استخراج میگردد.
یک تاپل از لایههای متعدد در چنین شبکههای اجتماعی، به عنوان شبکه اجتماعی چند لایه تعریف میشود. بنابراین ML-SOR اطلاعات شبکه اجتماعی را از زمینههای متعدد استخراج کرده و گرههای تصادفی را از لحاظ مرکزیت گره، قدرت گره و پیش بینی لایههای مختلف شبکههای اجتماعی تجزیه و تحلیل میکند. در الگوریتم ML-SOR زمانی که گره A با گره B ملاقات میکند، معیار اجتماعی به نام MLS را برای تمامی پیامها هم نسبت به گره خودش و همچنین نسبت به گره B محاسبه می کند. اگر MLS برای گره A بالاتر باشد، درخواست دانلود برای آن پیام خاص میفرستد. معیارهای اجتماعی بر اساس سه مولفه محاسبه میگردند: TSS ,CS و LPS. CS نشان دهنده مرکزیت گره در گراف تاریخچه تماسها میباشد، در حالی که TSS و LPS با توجه به مقصد پیام محاسبه میگردند.
TSS قدرت شبکههای اجتماعی آنلاین بین گره تحلیل و مقصد است و LPS به عنوان پیش بینی لینک می باشد که در لایه شبکه مورد نظر محاسبه میگردد. LPS تعداد علاقهمندی مشترک بین گره تصادفی و مقصد پیام را محاسبه میکند.[7]الگوریتم ONSIDE از علاقهمندی مشترک بین گرهها استفاده میکند . هنگامی که دو گره در ONSIDE همدیگر را ملاقات میکنند، لیستی از پیامهایی موجود در بافر خود - با شناسههای منحصر به فرد و اطلاعات کانال - را با فهرست موضوعات مورد علاقهشان مبادله میکنند. بر اساس این اطلاعات هر گره پیام های گره دیگر را تجزیه و تحلیل می کند و تصمیم میگیرد که پیام تبادل شود یا نه. سپس یک درخواست تبادل برای کسانی که پیام را میخواهند ارسال کنند، میفرستد.[7]
در مسیریابی آگاه از خودخواهی اجتماعی اغلب افراد جامعه دارای خودخواهی اجتماعی هستند؛ یعنی میخواهند بستهها را به گرههایی که با آنها روابط اجتماعی دارند، ارسال کنند؛ البته میزان رضایت آنها باتوجه به قدرت رابطهی اجتماعی متفاوت است. ارسال بستهها به گرههایی که تمایلی به بازپخش آنها ندارند، موجب حذف آنها خواهد شد. این روش با مورد توجه قراردادن میزان رضایت کاربران برای ارسال بستهها نرخ حذف آنها را کاهش میدهد. هرچه رابطهی اجتماعی بین دو گره قویتر باشد، میزان رضایت آنها برای ارسال بستههای یکدیگر بالاتر خواهد بود.. [6 ]
3.روش پیشنهادی
در روش های قبلی زمانی که دو گره همدیگر را ملاقات میکردند فرض بر این بود که فقط یکی از آنها بستهای برای ارسال دارد. اما در روش پیشنهادی فرض شدها ست در هنگام ملاقات ممکن ا ست هر دو گره ملاقاتکننده بستههایی برای ارسال در بافر خود داشته باشند. در این شرایط با یکی از سه حالت زیر روبرو خواهیم شد.-1اگر بافر هر دوگره خالی با شد. پس هیچ ب ستهای برای تبادل نی ست در نتیجه کاری انجام نمیدهیم. -2 اگر بافر یکی از گرهها خالی باشد، نیازی به تعیین گره ار سالکننده و دریافتکننده نی ست، گرهای که بافرش خالی ا ست به عنوان دریافتکننده و گره دیگر ارسالکننده انتخاب میشود.
در این حالت برای تعیین اینکه کدام بسته ارسال شود، ابتدا مقدار عددی وابستگی بستهها نسبت به گره حامل بسته و گره مقابل محاسبه میشود. با تقسیم کردن این دو مقدار به هم امتیاز بسته بدست میآید. حال با یک مقایسه، بستهای که کوچکترین امتیاز را دارد پیدا میکنیم. اگر امتیاز این بسته از 1 کوچکتر بود، یعنی وابستگی بسته به گره مقابل بیشتر از وابستگی بسته به گره حامل بسته است؛ پس بسته به گره مقابل ارسال می شود. در غیر اینصورت بسته ارسال نمی شود.در این مقاله فرض میکنیم اگر دو و یا بیشتر از دو بسته دارای امتیازیکسانی بودند، یکی از بسته ها به تصادف ارسال می شود.
فرض بعدی این است که اگر یک بسته هیچ وابستگی به گره مقابل نداشته و مقدار عددی وابستگی صفر باشد، آن بسته نادیده گرفته شده و ارسال نمیشود.-3در صورتی که بافر دو گره حاوی بسته باشند. در این حالت هم مانند حالت قبلی امتیاز بستهها را محاسبه میشود . با بررسی امتیاز بستهها، کمترین امتیاز بسته مشخص میشود، در صورت کوچکتر بودن از عدد 1، آن بسته در هر کدام از گرهها قرار داشت آن گره ارسالکننده و گره مقابل دریافتکننده انتخاب میشود. حال اگر در بافر دریافتکننده فضای خالی موجود بود بسته ارسال میشود. در غیر اینصورت بستههای با کمترین امتیاز در هر گره تبادل میشوند.
-1-3 فلو چارت های تعیین ارسال کننده ودریافت کننده
برای اینکار با استفاده از شکل - - 1 ابتدا بررسی میکنیم که دو گره i و j هنگامی که یکدیگر را ملاقات میکنند، بافرهایشان خالی است یا نه، که در صورت خالی بودن بافرها کاری انجام نمیگیرد ولی در غیر اینصورت، با محاسبه امتیاز بستهها، بسته با کمترین امتیاز را پیدا میکنیم. اگر امتیاز این بسته از 1 کوچکتر بود، یعنی وابستگی بسته به گره مقابل بیشتر از وابستگی بسته به گره حامل بسته است، پس بسته با امتیاز کمتر به گره مقابل ارسال می شود. اما اگر از 1 کوچکتر نیست کاری انجام نمیگیرد.