چکیده

شبکههای سیار موردی((mobile ad hoc network شبکههایی هستند که بوسیله گرههای متحرک شکل گرفته و به زیرساخت ثابت و از قبل تعریفشدهای متکـی نمیباشند.

هنگام انتخاب مجموعه مسیرهای پشتیبان، باید اشتراک و همبستگی مسیرها در یک مجموعه مسیر انتخاب شده تا حد ممکن کم باشد. الگوریتم هایی که برای ایـن منظور وجود دارند دارای تأثیرپذیری کمی بوده و قادر نیستند همه مسیرهای مطمئن را با پیچیدگی محاسباتی کم تولید کنند. این مقاله یـک روش مفیـد و مـوثر، برای انتخاب مجموعه مسیر های مجزا و پشتیبان در شبکه موردی معرفی مینماید. این پروتکل بسیار سریع به یک مجموعه مسیر مطمئن همگرا شده و مجموعـهای از مسیرهای پشتیبان را با قابلیتاطمینان بسیار بالا تولید خواهد کرد. همچنین در این مقاله از یک شبکه عصـبی پرسـپترون چنـد لایـه((MLP بـرای پـیشبینـی قابلیتاطمینان خطوط ارتباطی استفاده میگردد. همچنین اثرات افزایش تعداد لایهها بر روی کارایی شبکه عصبی نشان داده میشود.

.

واژه های کلیدی: شبکه های موردی سیار، مسیریابی، قابلیت اطمینان، شبکه عصبی

-۱ مقدمه
اغلب ممکن است کاربران سیار تمایل داشته باشند بدون استفاده از یک زیرساخت ثابت و مدیریت متمرکز، با هم ارتباط برقرار کنند.

در چنین شرایطی مجموعه ای از میزبانهای سیار یک شـبکه مـوقتی را شکل داده در حالی که از یک زیربنای ثابت و مدیریت متمرکز استفاده نمیکنند. به چنین شبکه بی سیمی، شبکه موردی سیار گویند. گـره هـا در این شـبکه دارای موقعیـت ثـابتی نبـوده و بطـور اختیـاری حرکـت می کنند، لذا باید قطع ارتباط را بهعنوان یک رفتار طبیعی شبکه در نظر گرفت که ناشی از تغییر همبندی شبکه موردنظر میباشد.

انفصال مسیر، کشف مسیرهای جدید را طلب کرده و باعث ایجاد تأخیر در ارسال بستههای داده شده که بر روی کیفیـت سـرویس کاربردهـای حساس به تأخیر اثر خواهد گذاشت.

یک روش مناسب برای مقابله با این نقیصه، بهرهگیری از چندین مسـیر بین مبدأ و مقصد می باشد. اگر برای برقراری ارتباط بین هر زوج مبدأ و مقصد یک مجموعه مسیر انتخاب شود، زمان کشف مسیرها را می تـوان تا حد زیادی کاهش داد. این مجموعه مسـیرهـای انتخـاب شـده نبایـد هیچگونه همپوشانی داشته باشند؛ چون در صورتی که یک خط ارتباطی متعلق به چند مسیر دچار نقص شود، همه مسیر هـای مربوطـه از بـین خواهنــد رفــت. بنــابراین بــرای انتخــاب یــک مجموعــه مســیر کــه قابلیتاطمینان بالایی را فراهم کند باید ارتباط و همبستگی مسـیرهای موجود در آن مجموعه تـا حـد ممکـن کـم شـود. بـه مسـیرهـایی کـه

هیچگونه خط ارتباطی مشترکی در آنها وجود ندارد، مسـیر هـای مجـزا گفته میشود.

مسأله یافتن مسیر های مجزا کـه قابلیـت اطمینـان را بهبـود دهـد کـار سادهای نیست.

یک روش سـاده بـرای تعیـین مسـیر هـای مجـزا ایـن اسـت کـه ابتـدا مطمئنترین مسـیر را انتخـاب کـرده و سـپس خطـوط ارتبـاطی آن را برداریم تا الگوریتم مسیریابی در تکرار بعـدی از ایـن خطـوط ارتبـاطی استفاده نکند.

در این مقاله یک روش بهینه برای انتخاب مجموعه مسـیرهای مجـزا و مطمئن بهعنوان مسـیرهای پشـتیبان در شـبکه هـای مـوردی معرفـی میگردد تا قابلیتاطمینان این مجموعه مسیر را به حداکثر برساند.

در این پروتکل از یک متریک مناسب بـرای محاسـبه قابلیـت اطمینـان مسیرها استفاده شده که با اختصاص یک وزن منفی به بعضی از خطوط ارتباطی هدایتشده، از آنها برای انتخاب مسیر مطمـئن بعـدی مجـدداً بهره خواهد گرفت.

خط ارتباطی هدایت شده به خطی گفته می شود که دارای جهتی رو به جلو یا رو عقب باشد و قـبلاً الگـوریتم مسـیریابی از آن اسـتفاده کـرده است.

-۲ پژوهش های مربوطه

۱

j بصورت

در اکثر کارهـای مربوطـه، از ارسـال بسـتههـای درخواسـت مسـیر RREQ برای انتخاب یـک مجموعـه مسـیر اسـتفاده مـی شـود کـه بـا بکارگیری روش سیلابی در سراسر شبکه، مسیر را انتخاب میکننـد. در این پروتکل ها از شماره ردیف هایی استفاده می شود تا بسـته هـا بـیش از یک بار بوسیله هر گره پخش نگردند.

Das et all [1] از یک مکانیزم سیلابی استفاده کرده اسـت کـه بـرای بستههای درخواست مسیر یک زمان خروج در نظر میگیرد و مقدار آن بعد از هر پرش یک واحد کم می گردد. در این روش به هر بسته انتخاب مسیر یک ثبتکننده مسیر( (Route catch نیز اختصـاص داده شـده که مسیر جاری دنبالشده توسط این بسته را در خود ذخیره میکند.

مشکل اساسی این روش آن است که چون گره هـا از مکـانیزم سـیلابی برای ارسال بسته استفاده می کنند، لذا تعداد بسته های تولیـد شـده آن بسیار بالا بوده و برای یافتن مسیر بین یک زوج گره، مدت زمان بسـیار زیادی تلف میشود. بنابراین این پروتکل تنها مـیتوانـد در شـبکههـای کوچک و در فواصل کوتاه بکار رود.

Hauspie et all [2] یک طـرح مسـیریابی را بـرای یـافتن مسـیرهای مجزا در شـبکه هـای مـوردی سـیار ارائـه کـرده اسـت کـه بـر مبنـای کاربردهای گره سرویس دهنده- گره استفادهکننده عمل مـیکنـد. ایـن طرح با استفاده از یک روش سـیلابی هـدایت شـده بـه سـمت مقصـد، مسیرهای مجزا را انتخاب خواهند کرد و از این مسیرها برای شناسـایی تفکیک در شبکه استفاده می گردد. در این طرح نیاز است کـه هـر گـره فاصله خود را از گره مبدأ بداند. برای این کار باید از پیامهـای راهنمـای دورهای استفاده کرد که سرریز بالایی را تولید می کنند. همچنـین گـره مقصد باید تعدادی شماره ردیف را در بسته جواب مسیر قـرار دهـد کـه پهنای باند بسیار زیادی از شبکه را مصرف خواهد کرد و حجـم بسـته را افزایش میدهد.

روشهای ارائه شـده در[۳-۱۷]، روش هـای دیگـری هسـتند کـه بـرای محاسبه مسیرهای متعدد و مجزا ارائه شده اند تا انرژی مصرفی گره ها را به حداقل برسانند یا عمل کنترل ترافیک و توزیع بار را در شبکه انجـام دهند. در این پروتکل ها از روش های بنا بـر تقاضـایی ماننـد مسـیریابی منبع پویا DSR و روش مسیریابی بردار فاصله بلادرنگ موردی استفاده شده که با بهره گیـری از یـک مکـانیزم درخواسـت- پاسـخ مسـیرها را محاسبه خواهنـد کـرد. در تمـام ایـن روش هـا مسـیرهایی بـا حـداکثر قابلیتاطمینان محاسبه نشده یا مسیرهای بدسـت آمـده کـاملاً از هـم مجزا نخواهند بود.

-۳ طرح پیشنهادی

۰-۲ مدل و فرضیات

ابتدا قابلیتاطمینان یک عنصر شبکه را به عنوان احتمال عملکرد صحیح آن تعریف میکنیم.

در این پروتکل احتمال درست عمل کردن یـک خـط ارتبـاطی بـا Pij link مشخص میشود که i,j نشانی گره هـایی اسـت کـه بـا هـم ارتباط دارند.

Pij link احتمال درست کار کردن یک خط ارتباطی هدایت نشده یا بی جهت خواهد بود. بر طبق این روش، برای گـره مبـدأ S و گـره مقصد (S  D) D ، Reliability SD احتمـال سـالم بـودن مسیر اتصالدهنده S به D در سراسر گراف GP میباشد.

بمنظور کسب تخمینی از قابلیتاطمینان خطوط ارتباطی، از زمان انقضای ارتباط((link expiration time استفاده میشود.

در این روش با توجه به سرعت و جهت حرکت گره ها، زمان قطـع ارتباط محاسبه شده و سپس بر اساس آن، تعدادی قابلیتاطمینان به ارتباطات اختصاص داده خواهد شد.

فرض میکنیم دو گره i,j در شـعاع ارسـال r از هـم قـرار دارنـد.

مختصات گره سیار i برابر( (X i ,Yi و مختصات گره سیار

(X j ,Yj ) می باشد. Vi ,V j سرعت گرهها و i , j جهـت حرکـت آنها خواهد بود ( . (۰  i,j  ۲ در اینصورت مدت زمـانی کـه
ارتباط این دو گره وصل باقی می ماند از طریق رابطه زیـر حاصـل میگردد:[۱۸]

(a 2  b 2 )r 2  (ad  bc)2 (1) (abcd) LETi, j 
a 2  c 2

که در آن

a  Vi cosi Vj cos j c Vi sini Vj sin j

b  Xi  X j ,d  Yi Yj

بعد از محاسبه زمان انقضای تمـام ارتباطـات موجـود در شـبکه، حــداکثر آنهــا ( (LETmax را تعیــین مــینمــاییم. احتمــال درســت کــارکردن خــط ارتبــاطی بــین گــره j و i از رابطــه زیــر بدســت

میآید:
(۲) LETi, j link  p
LETmax ij

۲

در این رابطه LETmax حداکثر مدت زمانی است که ارتباط دو گره موجـود در شـبکه متصـل بـاقی مــیمانـد. بـا ایـن روش تخمــین

قابلیتاطمینان ارتباطات روی تمامی گره ها توزیع میگـردد. ایـن پروتکل طبیعت بلادرنگ مسیریابی در شبکه های موردی را حفـظ کرده و مقیاسپذیری را محدود نمیکند.