پایان نامه زمان‌ بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌ های مش بی‌ سیم

فهرست:

فهرست مطالب.. یک

فهرست اشکال. پنج

فهرست جداول. هفت

چکیده. 1

1-                    فصل اول مقدمه...................................................................................................................... 2

1-1مقدمه، چشم انداز شبکه‌های مش بی‌سیم............................................................................................... 2

1-2ضرورت تضمین کیفیت سرویس، چالش اصلی در شبکه‌های مش بی‌سیم............................................ 4

1-3تعریف مسئله……………………......................……………………............................................... 6

1-4بررسی پیشینه کار............................................................................................................................................ 7

1-5 فصول بعدی این نوشتار................................................................................................................................... 9

1-6جمع‌بندی.................................................................. ................................................................................................. 9

                  2-فصل دوم شبکه‌های مش بی‌سیم................................................................................................ 11

2-1چشم‌انداز................................................................ ................................................................................................ 11

2-2توپولوژی شبکه........................................................ ............................................................................................... 14

2-2-1توپولوژی نقطه به نقطه (PTP) ..................................................... ................................................................ 14

2-2-2توپولوژی نقطه به چند نقطه (PMP) ......................................................................................................... 14

2-2-3توپولوژی مش................................................... ................................................................................................... 15

2-3شبکه‌های بی‌سیم چندگامی....................................................................................................................... 16

2-4معماری شبکه‌های مش بی‌سیم................................................................................................................... 17

2-4-1شبکه‌های  مش بی‌سیم به عنوان شبکه‌ی زیر ساخت................................................................................... 17

2-4-2شبکه‌های مش بی‌سیم کاربران.............................. .......................................................................................... 18

2-4-3شبکه‌های مش بی‌سیم ترکیبی............................. ........................................................................................... 19

2-5مقایسه شبکه‌های مش بی‌سیم  و Ad-hoc                              ...............................................................................................19

یک

2-6مسائل مربوط به لایه‌های شبکه و زمینه‌های باز تحقیقاتی................................................................................. 21

2-6-1لایه فیزیکی............................................................ ............................................................................................ 21

2-6-2لایه‌ی دسترسی در شبکه‌های مش بی‌سیم................................................................................................. 23

2-6-3MAC تک کاناله.............................................. ................................................................................................. 24

2-6-4MAC چندکاناله.............................................. ................................................................................................. 25

2-6-5لایه شبکه............................................................. .............................................................................................. 28

2-6-6لایه انتقال........................................................... ................................................................................................ 30

2-6-7لایه کاربرد................................................... ....................................................................................................... 31

2-7مدیریت شبکه....................................................... ................................................................................................ 32

2-8طراحی بین لایه ای.............................................. ................................................................................................... 33

2-9 کاربردهای WMN.............................................. ................................................................................................... 33

2-9-1شبکه‌ی خانگی باند وسیع........................................................................................................................ 33

2-9-2شبکه کردن اجتماعات و همسایگی ها........................................................................................................ 34

2-9-3شبکه کردن شرکت های تجاری.................................................................................................................... 35

2-9-4شبکه های شهری.......................................... ................................................................................................... 36

2-9-5سایر شبکه‌ها....................... .............................................................................................................................. 37

2-9-6 چند مثال موردی از شبکه‌های WMN.......................................................................................................... 38

2-10جمع‌بندی............................................................... ................................................................................................ 39

         3-فصل سوم زمان‌بندی متمرکز در شبکه‌های مش بی‌سیم...................................................................................      41

3-1مقدمه..................................................................... ................................................................................................ 41

3-2لایه فیزیکی استاندارد IEEE 802.16............................................................................................................ 42

3-2-1مدولاسیون دیجیتال............................................ ............................................................................................... 46

3-3لایه MAC استاندارد  IEEE 802.16............................................................................................................ 48

3-3-1 تطبیق لینک..................................................... ................................................................................................. 49

3-4عملکرد مد مش  در MAC استاندارد IEEE 802.16........................................................................................ 50

دو

3-4-1 ساختار فریم در مد مش استاندارد IEEE 802.16........................................................................................ 51

3-4-2زیرفریم کنترلی....................................................... ........................................................................................... 52

3-4-3زیرفریم دیتا....................................................... .................................................................................................. 54

3-4-4نحوه ورود یک گره‌‌‌ به شبکه.............................. ............................................................................................... 56

3-5الگوی زمانبندی مبتنی بر استاندارد IEEE 802.16........................................................................................... 57

3-5-1زمان‌بندی متمرکز................................... ....... ................................................................................................... 59

3-6جمع بندی................................................................................................................................................................. 60

              4-فصل چهارم مدل، چالش‌ها و روش‌های زمان‌بندی متمرکز در شبکه‌های مش بی‌سیم.............................      61

4-1مقدمه................................................................... ................................................................................................. 61

4-2نیازمند‌های  طراحی الگوریتم های زمانبندی..................................................................................................... 62

4-2-1تداخل میان لینکهای بی‌سیم.................................. .......................................................................................... 62

4-2-2سربار.................................................................. ................................................................................................. 64

4-2-3تأخیر................................................................ .................................................................................................... 65

4-2-4استفاده مجدد فرکانسی.................................... .............................................................................................. 66

4-3دسته‌بندی الگوریتم‌های زمان‌بندی.................................................................................................................. 68

4-4معرفی الگوریتم‌های زمان‌بندی با رویکرهای‌مختلف............................................................................................ 70

4-5نتیجه‌گیری............................................................. ................................................................................................. 76

5-                 فصل پنجم الگوریتم پیشنهادی بر پایه‌ی الگوریتم ژنتیک.....................................................................       78

5-1مقدمه....................................................................... .............................................................................................. 78

5-2الگوریتم ژنتیک................................................... ................................................................................................... 79

5-2-1تاریخچه.............................................................. ................................................................................................ 79

5-2-2ساختار الگوریتم‏های ژنتیکی.............................................................................................................................. 80

5-2-3عملگرهای الگوریتم  ژنتیک.......................... ................................................................................................... 82

5-2-4کدگذاری و همگرایی الگوریتم ژنتیک........................................................................................................... 86

5-3الگوریتم پیشنهادی............................................. .................................................................................................. 87

سه

5-4شبیه سازی............................................................ ................................................................................................ 96

5-4-1محیط شبیه سازی............................... ......................................................................................................... 96

5-4-2نتایج حاصل از شبیه‌سازی................................... .............................................................................................. 98

5-5جمع بندی.......................................................... ...................................................................................  111 Error! Bookmark not defined.

       فصل ششم نتیجه‌گیری و پیشنهادات...........................................................................................................112

             مراجع......................................................................................................................................................................114

منبع:

IEEE 802. 16-2004, IEEE standard for local and metropolitan area networks part 16: air interface for fixed broadband wireless access systems, Oct. 1, 2004.

IEEE 802. 16-2005, IEEE Standard for Local and Metropolitan Area Networks – Part 16: Air Interface for Fixed Broadband Wireless Access Systems for Mobile Users, December 2005. M. S. Kuran, T. Tugcu / Computer Networks 51 (2007) 3013–3046 3043.

 I.F.Akyildiz, X.Wang, “A survey on wireless mesh networks”, IEEE Communication Magazine, Vol. 43, Issue 9, pp. 23-30, Sept 2005.

S.Redana, and M.Lott, “Performance Analysis of IEEE 802. 16a in Mesh Mode”, IST SUMMIT, France, June 2004.

 S.Ramanathan, “A unified framework and algorithm for channel assignment in wireless networks”, Wireless Networks, vol. 5, Issue 2, pp. 81–94, March 1999.

 S.Ramanathan, L.Lloyd, “Scheduling algorithms for multihop radio networks”, IEEE/ACM Transactions on Networking, vol. 1, Issue 2, pp. 166–177, April 1993.

 B.Hajek, G.Sasaki, “Link scheduling in polynomial time”, IEEE Transactions on Information Theory, vol. 34, Issue 5, pp. 910–917, September 1988.

T.Salonidis, L.Tassiulas, “Distributed dynamic scheduling for end to end rate guarantees in wireless ad hoc networks”, ACM MobiHoc, pp. 145–156, 2005.

M.Kodialam, T.Nandagopal, “Characterizing achievable rates in multihop wireless networks: The joint routing and scheduling problem”, ACM MobiCom, 2003.

M.Kodialam, T.Nandagopal, “Characterizing achievable rates in multihop wireless mesh networks with orthogonal channels”, IEEE/ACM Transactions on Networking, vol. 13, Issue 4, pp. 868–880, 2005.

G.Sharma, R.Mazumdar, N.Shroff, “On the complexity of scheduling in wireless networks”, ACM Mobicom, 2006.

S.Gandham, M.Dawande, and R.Prakash, “Link scheduling in sensor networks: Distributed edge coloring revisited”, IEEE INFOCOM, 2005.

N.Bayer, B.Xu, V.Rakocevic, J.Habermann, “Improving the Performance of the Distributed Scheduler in IEEE 802. 16 Mesh Networks”, IEEE VTC, pp. 1193-1197, 2007.

H.Wei, S.Ganguly, R.Izmailov, and Z.Haas, “Interference- aware IEEE 802. 16

        WiMax mesh networks”, IEEE VTC, vol. 5, pp. 3102- 3106, , 2005.

J.Tao, F.Liu, Zh.Zeng, and Zh.Lin, “Throughput Enhancement in WiMax Mesh Networks Using Concurrent Transmission”, IEEE WiMob, Vol. 2, pp. 871 –874, 2005.

Y.Cao, Zh Liu, Y.Yang, “A Centralized Scheduling Algorithm based on Multi-path Routing in WiMAX Mesh Network”, IEEE WiCOM, 2006.

B.Han, W.Jia, and L.Lin, “Performance evaluation of scheduling in IEEE 802. 16 based wireless mesh networks”, ACM Computer Communications, vol. 30, Issue 4, pp. 782-792, 2007.

F.Jin, A.Arora, J.Hwang, A .Choi, “Routing and Packet Scheduling for Throughput Maximization in IEEE 802. 16 Mesh Networks”, IEEE Broadnets, 2007.

P.Du, W.Jia, L.Huang, W.Lu, “Centralized Scheduling and Channel Assignment in Multi-Channel Single-Transceiver WiMax Mesh Network”, IEEE WCNC, pp. 1734-1739, 2007.

D.Kim and A.Ganz, “Fair and efficient multihop scheduling algorithm for IEEE 802. 16 BWA systems”, IEEE Broadnets, Vol. 2, pp. 833 - 839, 2005.

C.Hong, A.Chun Pang, “Link Scheduling with QoS Guarantee for Wireless Relay Networks”, IEEE Transactions on Networking, 2008.

F.I.Akyildiz, X.Wang and W.Wang, “Wireless mesh networks: a survey”. Computer Networks Journal (Elsevier), 47(4), 445–487 2005.

Y.Zhang, J.Luo, and H.Honglin, “Wireless Mesh Networking Architecture, Protocols and standards”, pages 4-7, 14-15,428-429,568-590, 2007 by Taylor & Francis Group, LLC.

A.Tzamaloukas, l.Garcia, “A Receiver Initiated Collision Avoidance Protocol for Multi Channel Networks”. In Proceeding of INFOCOM, 1997.

N.Bayer, D.Sivchenko, B.Xu, V.Rakocevic, J.Habermann, “Transmission Timing of Signaling message IN IEEE 802. 16 Based on mesh network”, European wireless Athens, Greece, Apr 2-5, 2006.

B.Raman, and K.chebrolv, “Design and Evaluation of a new MAC Protocol for Long Distance 802. 11 Mesh Network”, in proc, ACM, 2005.

T. J.Tsai, H.Tseng, and A. C.Pang,”A New MAC Protocol for Wi-Fi Mesh Network”, in Proc IEEE AINA06, 2006.

D.Couto, D.Aguayo, J.Bicket, and R.Morris, “A high-throughput path metric for multi-hop wireless routing”, in MobiCom 03: Processing of the 9th Annual International conference on mobile computing and networking, ACM press, pp.134-146, New York,2003,.

R.Draves, J.Padhye, B.Zill, “Routing in multi-radio, Multi-hop wireless Mesh Networks”, Processing of ACM MobiCom, pp.114-128, 2004.

H.Fery,  “Scalable Geographic Routing Algorithms for Wireless Ad-Hoc Networks ”, IEEE Networks MAG, Vol 18, No. 4, July/Aug 2004, Pages:18-22

Z.Fu,  X.Meng,  and S.lu,  “A transport Protocol for supporting Multimedia Streaming in Mobile Adhoc Networks”, IEEE JSAC, vol. 21, no. 10. DEC,2003.

J.Bicket, D.Aguayo, S.Biswas, and R.Morris, “Architecture and evaluation of an unplanned 802. 11b mesh network”, In MobiCom ’05: Proceedings of the 11th annual international conference on Mobile computing and networking, pages 31–42, New York, NY, USA, 2005. ACM Press.

A.Benjamin, A.Chambers, “The grid roofnet: a rooftop ad hoc wireless network” Master’s thesis, Massachusetts Institute of Technology, May 2002.

V.Navda, A.Kashyap, S.Das, “Design and Evaluation of iMesh: an Infrastructure-mode Wireless Mesh Network”, In 6th IEEE WoWMoM Symposium,, June 2005.

A.Elan,  and H.Balakrishnan,  “An Evaluation of the Metricom Ricochet Wireless Network”, Class report, Dept.of Electrical Engineering and Computer Science, University of California at Berkeley, May 1996..

OPNET TECHNOLOGIES, INC., “Introduction to WiMAX: Technology Tutorials”, OPNETWORK, Washington, 2007.

B.Fong, N.Ansari, A.C.M.Fong, G. Y.Hong, and B.Predrag “On the scalability of fixed broadband wireless access network deployment”, IEEE communications Magazine, vol. 42, Issue 9, pp. 12-18, 2004.

P.Djukic, and S.Valaee, “TDMA delay aware link scheduling for multi-hop wireless networks”, IEEE Transactions on Networking, 2007.

L.Nuaymi and M.Loutfi. “WiMAX : Technology for Broadband Wireless Access”,. John Wiley & Sons, 2007.

Sh.Cheng, Ph.Lin, D.Huang, Sh.Yang, “A study on distributed/centralized scheduling for wireless mesh network”, IEEE IWCMC, pp. 599-604, 2006.

H.Zandi, and Y.Fang, “Impact of routing metrics on path capacity in multi-rate and multi-hop wireless ad-hoc networks”, in ICNP, 2006.

S.Ramanthan, and E. L.Lioyd, “Scheduling algorithms for multichip radio networks”, IEEE/ACM transaction on networking, vol. 1, no 2, pp.166-177, Apr. 1993.

Y.Qian, B.Shafaq, L.Chaudhry, and K.Ratan, “Resource Management in WiMAX Networks.” In Yang Xiao (editor(s)), WiMax/MobileFi: Advanced Research and Technology, pp 337-408. Auerbach Publications, CRC Press. Dec, 2007. 

S.Hung-Yu Wei, R.Ganguly, Z.Izmailov, and J.Haas, “Interference-aware ieee 802. 16 wimax mesh networks”, In Vehicular Technology Conference, 2005.

H.Shetiya, and V.Sharma, “Algorithms for routing and centralized scheduling to provide QoS in IEEE 802. 16 mesh networks”, In WMuNeP ’05: Proceedings of the 1st ACM workshop on Wireless multimedia networking and performance modeling, 2005.

N.Krishna, M.Ramachandran, E.Belding, K.Almeroth, and M.Buddhikot, “Interference-aware channel assignment in multi-radio wireless mesh networks”, In INFOCOM, 2006.

G.Ashutosh, and K.Abhay, “Link scheduling algorithms for wireless mesh networks”, In IEEE communications survey and tutorials, second issue, 2011.

Du.Peng, J.Weijia, H.Liusheng, and W.Lu, “Centralized scheduling and channel assignment in multi-channel single-transceiver WiMAX mesh network”, In Wireless Communications and Networking Conference, WCNC, 2007.

S.Ergen, and P.Varaiya, “TDMA scheduling algorithms for wireless sensor networks”, Wireless Networks, 2009.

M.Alicherry, R.Bhatia, and E.Li, “Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks”, In MOBICOM, 2005.

D.Ghosh, A.Gupta, and P.Mohapatra, “Admission control and interference-aware scheduling in multi-hop WiMAX networks”, In Mobile Adhoc and Sensor Systems, 2007.

P.Djukic, and S.Valaee, “Delay aware link scheduling for multi-hop TDMA wireless networks”, IEEE/ACM Transactions on Networking, 2009.

G.Narlikar, G.Wilfong, and L.Zhang, “Designing multihop wireless backhaul networks with delay guarantees”, In INFOCOM, 2006.

Sahoo, A.  and Goyal, P. “A scheduling and call admission control algorithm for WiMAX mesh network with strict QoS guarantee”, In Comsnet, 2010.

V.Gabale, A.Chiplunkar, B.Raman, and P.Dutta, “Delaycheck: Supporting voice over multi-hop multichannel wireless mesh”, In COMSNETS, 2011.

A.Raniwala, K.Gopalan, and T.Chiueh, “Centralized channel assignment and routing algorithms for multichannel wireless mesh networks”, SIGMOBILE Mob. Comput. Commun. Rev. , 8(2):50–65, 2004.

A. S.Kashyap, S. R.Ganguly, and S.Banerjee, “Voip on wireless meshes: Models, algorithms and evaluation”, In INFOCOM, 2007.

P.Dutta, S.Jaiswal, and R.Rastogi, “Routing and channel allocation in rural wireless mesh networks”, In INFOCOM, 2007.

B.Raman, and K.Chebrolu,” Design and evaluation of a new mac protocol for long-distance 802. 11 mesh networks”, In MOBICOM, 2005.

P.Dutta, S.Jaiswal, D.Panigrahi, and R.Rastogi, “A new channel assignment mechanism for rural wireless mesh networks”, In INFOCOM Mini-Conference, 2008.

L. Y.Tseng, and S.Yang, “Genetic algorithms for clustering, feature selection and classification”, IEEE Int. Conference on Neural Networks, pp. 1612-1616, 1997.

J.Bala, H.Vafaie, K.De jong, and H.Wechslev, “Hybrid learning using genetic algorithms and decision trees for pattern classification”, IJCAI conference, Montreal, 1995.

W.Siedlecki, and J.Sklansky, “A note on genetic algorithms for large scale pattern selection”, Pattern Recognition Letters, vol. 10,335-347, 1989.

H.Vafaie,  and K.De Jong, “Robust feature selection algorithms” , Proc. of the fifth conference on tools for artificial intelligence, Boston, MA: IEEE Computer Society Press. , pp. 356-363, 1993.

H.Vafaie  and K.De Jong,  “Genetic algorithms as a tool for feature selection in machine learning”, Proc. of the 4th Int. conference on tools with artificial intelligence, pp. 200-204 Arlington, VA, 1992.

H.Vafaie, and I.Imam, “Feature selection methods: genetic algorithms vs. greedy-like search”, Proc. of the Int. conference on fuzzy and intelligent control systems, 1994.

Fogel, D. B.  “What is Evolutionary Computation?” IEEE Spectrum, Feb 2000, pp. 26-32

R. L.Haupt,  and S.Ellen Haupt, “Practical Genetic Algorithm” USA, Wiley, 2004

F.Marki, M.Vogel, and M.Fischer, “Process Plan Optimization using a Genetic   Algorithm", PATAT 2006, pp. 528–531. ISBN 80-210-3726-1. 2006

R.Perzina, “Solving the University Timetabling Problem with Optimized Enrolment of Students by a Parallel Self-adaptive Genetic Algorithm”, PATAT, pp. 264–280. 2006

P.Y.Kong, H.Wang, Y.Ge, C.K.Tham, and Y.C.Liang, “PMP tree and hybrid PMP-mesh for multi-hop relay networks,” IEEE C802.16j-06/008r2, May 2006.

 H.Kang,  Y.Sun, R.Taori, Y.Lee, P.Wang, A.Chindapol,  H.Lee, Y.Takatani, H.Lee, A.Zhang, K.Zhang, F.Ren, K.Saito, K.Teo, K.Saito, K.Teo, P.Zhu, B.Kwak , “Proposed technical requirements guideline for IEEE 802. 16 Relay TG”, IEEE 802. 16j-06/016r1, Oct. 2006.

 M.Naden, D.Kitchener, W.Tong, P.Zhu, G.Senarnath, H.  D.Steer, D.Yu, and G. -Q.Wang, “Metrics for multihop systems”, IEEE C802. 16j-06/014r1, May 2006.

I. K.Fu, W. H.Sheen, C. L.Hsiao, and C.C.Tseng, “Reverse link performance of relay-based cellular systems in Manhattan-like scenario”, IEEE C80216mmr-06/004r1, Jan. 2006.

J.Cho, M.Lee, H.Kang, S.Lee, J.  P.Joo, Y.So, S.Kim, D.Hong, J.Choe, B.Shin, and H.Choi, “On the throughput enhancement of fixed relay concept in Manhattan-like urban environments”, IEEE C802. 16mmr-06/003, Jan. 2006.

 I.Guvenc, M.R.Jeong, F.Watanabe, and C. C.Chong, “Technical comments to P802. 16j baseline document: 6. 3. 23. 3 - use of ARQ in MBS,” IEEE C802. 16j-07/578r1, Nov. 2007.

N. L.Johnson, and S.Kotz, “Continuous Univariate Distributions”. New York: John Wiley & Sons, 1970.

ع.علیرضا مهدی ، "مقدمه­ای بر الگوریتم ژنتیک و کاربردهای آن" ،  انتشارات ناقوس، 1386.

ا.مسعودیان، "طراحی جدول زمانبندی خودکار با استفاده از الگوریتم های ژنتیک" ، پایان­نامه کارشناسی،  دانشگاه اصفهان، 1386.

م.عباس کیا ، "الگوریتم های فرا اکتشافی جستجو، الگوریتم های ژنتیک"، پایان نامه کارشناسی ، 1388.

ن.سادات مویدیان ،"تئوری یکپارچه مسیریابی،کنترل نرخ ورودی، زمان‌بندی و تخصیص کانال در شبکه‌های بی‌سیم"، پایان نامه دکتری، دانشگاه صنعتی اصفهان، 88.

 م.صالحی،" بهبود زمانبندی متمرکز به منظور تخصیص بهینه پنجره های خرد در شبکه های مش IEEE 802.16" ، پایان نامه کارشناسی ارشد،دانشگاه صنعتی امیرکبیر،  بهمن1386

 م.حسین الوندی ، "بهبود گذردهی و تامین QOS در شبکه‌های WiMax مش و شبیه سازی آن" ، پایان نامه کارشناسی ارشد ، دانشگاه صنعتی امیرکبیر، تیر 1388.

 ا.رستمی، "بررسی و ارائه راهکار جدید برای زمان‌بندی توزیع شده در شبکه‌های بی‌سیم مش IEEE 802.16.d" ، پایان نامه کارشناسی ارشد ، دانشگاه خواجه نصیرالدین طوسی،آذر 89.

 ش.خوشنواز،"بهبود الگوریتم زمان‌بندی در شبکه‌های WiMax"، پایان نامه کارشناسی ارشد،دانشگاه صنعتی سهند ، اردیبهشت 90.

 س.ضیایی امیری ،"طراحی MAC با پارامترهای QOS بهبود یافته در شبکه‌های مش بی‌سیم "، پایان نامه کارشناسی ارشد، دانشگاه تبریز، زمستان 89.

ف.حمیدی سپهر،"ارزیابی تحلیلی تاثیر MAC بر روی ظرفیت برون دهی در شبکه‌های بی‌سیم مش "، پایان نامه کارشناسی ارشد، دانشگاه صنعتی شریف ، مرداد 87.

ح.نورخیز محجوب ، "بهینه سازی گذردهی در شبکه‌های مش بی‌سیم"، پایان نامه کارشناسی ارشد، دانشگاه تهران، مهرماه 87.

س.میرزایی ،"ارزیابی روش‌های افزایش گذردهی با استفاده از تکنیک‌های تخصیص کانال در شبکه‌های مش بی‌سیم"، پایان نامه کارشناسی ارشد، دانشگاه یزد، مهرماه 89.

م.کرابی ،"ارائه راه حل جدید مبتنی بر الگوریتم‌های  ژنتیک برای حل مسئله چند پخشی در اینترنت  بر اساس پارامترهای QOS " ، پایان نامه کارشناسی ارشد، دانشگاه علم و صنعت ، اسفند  82.