عنوان پایان‌نامه
ارائه یک روش بهینه سازی میان لایه ای برای شبکه های بی سیم سرعت بالا
- رشته تحصیلی
- مهندسی فناوری اطلاعات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس 2 فنی شماره ثبت: E 2131;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 55124
- تاریخ دفاع
- ۳۰ شهریور ۱۳۹۱
- دانشجو
- مازیار میرزازادباریجوق
- استاد راهنما
- ناصر یزدانی
- چکیده
- شبکه‌های مقاوم در برابر تاخیر از قطعی مکرر لینک‌ها در شبکه و چند بخشی شدن توپولوژی گره‌ها رنج می‌برند. همینطور به دلیل محیط بسیار پویای این شبکه‌ها و نبود دانش کلی از توپولوژی شبکه برای تمام گره‌ها، مسیریابی در شبکه‌های مقاوم در برابر تاخیر بسیار سخت و چالش برانگیز می‌باشد. این شبکه‌ها عموما برای محیط‌های بین سیاره ای و بین ماهواره ای ، شبکه‌های ماشینی ، شبکه‌های زیر دریایی و غیره استفاده می‌شوند. ویژگی مشترک این شبکه‌ها، تراکم پایین، تحرک بسیار زیاد و تاخیر در تحویل پیغام بسیار بالا می‌باشد به طوری که تاخیر انتها به انتها در این شبکه‌ها، بسته به نوع شبکه، از چند ثانیه تا چند روز می‌تواند باشد. همینطور با توجه به این شرایط نرخ ریزش بسته ها و پیغام ها نیز بسیار بالا می‌باشد. به همین دلیل ارائه الگوریتم مسیریابی که بتواند با نرخ تحویل بالاتری میزان تاخیر در این شبکه‌ها را کاهش دهد بسیار حائز اهمیت می‌باشد. الگوریتم‌های مسیریابی زیادی در این زمینه ارائه شده‌اند. برخی از این الگوریتم ها بر پایه انتشار می‌باشند که به دلیل ایجاد تعداد بسیار زیاد نسخه از یک پیغام در سطح شبکه، باعث تحمیل سربار بسیار زیاد به شبکه می‌شوند. الگوریتم های دیگری ارائه شده اند که سعی در محدود کردن تعداد نسخه‌های یک پیغام و در نتیجه کاهش سربار شبکه داشته اند. الگوریتم های تک نسخه ای ارائه شده تا بحال، عموما به صورت حریصانه عمل کرده و در صورتی که گره‌ای از نظر معیار های الگوریتم گره بهتری برای رساندن پیغام ها به مقصد با گره حامل پیغام‌ها ارتباط پیدا کند، این گره پیغام ها را برای او ارسال می‌کند. در این رساله، الگوریتم مسیریابی تک نسخه ای ریسک پذیری ارائه می‌شود که با الگوریتم‌های قبلی ارائه شده در پیش‌بینی ارتباطات آینده بین گره ها و ارزیابی ریسک و پاداش عملکرد بر اساس این پیش‌بینی، تفاوت دارد. در الگوریتم ارائه شده، گره حامل پیغام ها، به پیش بینی در مورد ارتباطات آینده پرداخته و در صورتی که پیش بینی کند که احتمال ارتباط در آینده نزدیک با گره ای بهتر از گره‌های اطراف کنونی وجود دارد، به تحلیل ریسک و پاداش منتظر ماندن برای این گره و نادیده گرفتن گره‌هایی که در حال حاضر در ارتباط می‌باشند پرداخته و در صورتی که میزان ریسک پذیری الگوریتم اجازه دهد این عمل را انجام می‌دهد. در غیر اینصورت پیغام ها را به یکی از گره های اطراف می‌فرستد. اما اینکه چگونه می‌توان ریسک و پاداش هر پیش‌بینی را تحلیل و ارزیابی کند، سوالی می‌باشد که در این رساله به آن پاسخ خواهیم داد. این روش بر الگوریتم PROPHET اعمال شده و در شبیه ساز The ONE پیاده سازی شده و نتایج حاصل از شبیه سازی با الگوریتم PROPHET مقایسه گشته است. نتایج این شبیه سازی نشان از بهبود بسیار زیاد در این الگوریتم دارد. نتایج شبیه سازی نشانگر افزایش 19% در میزان تحویل بسته ها، 10% کاهش در تعداد هاپ ها، 23% بهبود در نرخ سربار و اما 1 % افزایش در تاخیر میانگین می‌باشد.
- Abstract
- Delay Tolerant Networks (DTNs) suffer from frequent disruptions and partitioning. Because of dynamic environment and lack of knowledge about the whole network topology, routing is quiet challenging in DTNs. Prediction based algorithms in DTNs are able to predict nodes future contacts in the case where each node has a movement model. In this thesis we propose a risk taking routing algorithm, which differs from previous algorithms in predicting the future contacts and taking the risk of waiting for those nodes instead of forwarding to the currently in contact good forwarders. Considering the forwarding strategy as an online problem, we evaluate the forwarding strategies using a risk reward competitive analysis. In addition a probabilistic graph model of network is made using history of contacts. Using this model contact times of network nodes is approximately predictable. Moreover we propose a risk-reward framework for message forwarding in delay tolerant networks. Using this framework, algorithm is able to calculate the values for Risk and Reward of its predictions and based on these values, it chooses the best action to perform. Simulations are done using The Opportunistic Network Environment Simulator for different risk tolerance of the algorithm. Simulation results show that our algorithm performs much better than PROPHET which is a base to our algorithm: In case of Delivery Ratio, we see 19% improvement. Average Hop Count is decreased about 10%. In addition, we see 23% improvement in Overhead Ratio. But in the average latency chart we see 1% increase. The results also show that taking risk up to value of 2, gives us a better performance.
