نوع مقاله : مقاله پژوهشی فارسی
نویسندگان
1 دانشجوی کارشناسی ارشد- گروه مهندسی کامپیوتر- دانشگاه شهید باهنر کرمان- کرمان- ایران
2 دانشیار- گروه مهندسی کامپیوتر- دانشگاه شهید باهنر کرمان- کرمان- ایران
چکیده
کلیدواژه‌ها
عنوان مقاله [English]
نویسندگان [English]
In Network-on-Chip architecture, wired structure and multi-step communication increase consumption power and latency. Combining wired media for a regular transmission and high-bandwidth wireless media for multi-step communication is a way to reduce latency and consumption of power. Wireless nodes are prone to error in on-chip wireless networks due to their complexity and relatively high usage; they are also crowded due to their sharing between several nodes, but their job is to increase efficiency. However, the presence of wireless nodes in wireless networks on the chip increases the cost and area. Therefore, finding an optimal structure for communication between cores is necessary. In this paper, a new three-dimensional architecture for a Wireless Network on Chip is presented, which has two levels; depending on the location of the error in the second level, the wireless routers in the first level are assigned to the processing elements. The demand matrix is used to optimize different traffic patterns. The performance of 3D architecture has been compared under different traffic patterns. The obtained results show that the proposed structure has a relatively good performance and increases the network's reliability.
کلیدواژه‌ها [English]
با افزایش تعداد هسته‌ها در شبکه روی تراشه [3-5]، هنگام برقراری ارتباطات چندگامی باعث بروز مشکلاتی ازقبیل افزایش تأخیر و توان مصرفی می‌شود. برای بهبود کارایی شبکه روی تراشه، روش‌هایی مانند معماری سه‌بعدی [6]، شبکه‌های روی تراشه نوری [7,9]، شبکه‌های روی تراشه با فرکانس رادیویی [8] ارائه شده‌اند. اگرچه این روش‌ها تأخیر و توان مصرفی را کاهش می‌دهند، با مشکلات طراحی و ساخت روبه‌رو هستند.
وجود مشکلات در معماری شبکۀ روی تراشه باعث ظهور ایدۀ شبکۀ بی‌سیم روی تراشه شده است [9-12]. در ابتدا استفاده از ارتباطات بی‌سیم روی تراشه، برای توزیع سیگنال ساعت بوده است [22,23]. با ترکیب مناسبی از هردو رسانۀ سیمی و بی‌سیم معماری‌های مختلفی ایجاد شد تا مشکلات معماری شبکه روی تراشه سیمی سنتی رفع شوند.
اضافه‌کردن قسمت‌های بی‌سیم [13]، باعث افزایش هزینه و مساحت خواهد شد. برخی از گرهها را به فرستنده و گیرندۀ بی‌سیم مجهز می‌کنند؛ بنابراین، مکان قرارگیری گرههای بی‌سیم بسیار مهم است. گرههای بی‌سیم به دلیل اشتراک‌گذاری بین چندین گره و پیچیدگی پیاده‌سازی آنها، نرخ شکست بالاتری نسبت به اجزای دیگر تراشه دارند [15,16] و در معرض خطا و ازدحام قرار دارند.
براساس نحوۀ قرارگیری گرههای بی‌سیم، در سال‌های اخیر تحقیقات بسیاری در زمینۀ معماری شبکه‌های بی‌سیم روی تراشه انجام شده است. در ادامه برخی از آنها معرفی شده‌اند.
در مرجع [36]، شبکۀ جهانی کوچک با معماری چندبعدی و سلسله‌مراتبی معرفی شده است. ابتدا کل شبکه به چند زیر شبکه تقسیم می‌شود و در هر زیرشبکه بسته به نوع توپولوژی آن، مسیریاب‌ها به‌صورت سیمی باهم در ارتباط هستند. در مرکز هر زیرشبکه یک هاب وجود دارد که مسیریاب‌ها به‌صورت سیمی به هاب متصل می‌شوند. سطح بالاتر شامل اتصال هاب‌ها است که به‌صورت بی‌سیم با هم در ارتباط هستنند.
در این شبکه‌ها از هاب‌ها برای برقراری ارتباط بین زیرشبکه‌های مختلف استفاده می‌شود. در این حالت، در مقایسه با شبکه‌های مش معمولی کارایی بالاتری دارند [20]؛ اما درجۀ بالای اتصال در هاب‌ها بین سطوح مختلف سلسله‌مراتبی، باعث سربار بیش از حد در معماری شبکۀ جهانی کوچک می‌شود. به‌علاوه به دلیل اشتراک‌گذاری بین چند گره، ممکن است هاب‌ها تبدیل به گلوگاه شوند. درصورت خرابی هاب‌ها، زیرشبکۀ متصل به آن هاب کاملاً از شبکه جدا می‌شود.
درجۀ اتصال هاب‌ها در معماری پیشنهادی در [29]، کاهش پیدا کرده است؛ اما در صورت وجود خطا این معماری کارایی چندانی ندارد و همچنین، از الگوریتم مسیریابی دیجکسترا استفاده شده که سایز جدول‌ها بسیار زیاد است.
معماری دیگری که در شبکه‌های بی‌سیم روی تراشه استفاده می‌شود، یک شبکۀ مش جهانی، به‌عنوان پایه در نظر گرفته می‌شود [21-26]. در معماری مش، کل شبکه به چند زیرشبکه تقسیم می‌شود. در مرکز هر زیرشبکه، مسیریاب بی‌سیم قرار می‌گیرد. مسیریابی با توجه به مکان زیرشبکۀ گرۀ مبدأ و زیرشبکۀ گرۀ مقصد انجام می‌شود. اگر مقصد بسته در زیرشبکۀ فعلی باشد، مسیریابی ازطریق مسیریاب‌های معمولی، بدون درگیرشدن کانال بی‌سیم انجام می‌شود و هنگامی که گرۀ مقصد در زیرشبکۀ دیگری باشد، مسیر سیمی و بی‌سیم بین مبدأ و مقصد، محاسبه و کوتاه‌ترین مسیر انتخاب می‌شود. از آنجا که کوتاه‌ترین مسیر معمولاً مسیری است که شامل مسیریاب‌های بی‌سیم است، آنها می‌توانند به‌سرعت تبدیل به نقاط مهم شوند.
در معماری‌های پیشنهادشده در [17,35]، با انتقال بسته‌های اطلاعاتی از زیرشبکه‌هایی با هاب‌های بی‌سیم معیوب و ازدحام زیاد به زیرشبکه‌هایی با هاب‌های سالم و بدون تراکم در برابر خطاهای متناوب و گذرا، عملکرد شبکه را بهبود می‌بخشند؛ اما به دلیل زیادبودن تعداد هاب‌ها و همچنین اتصالتمام گرههای زیرشبکه به هاب، مساحت شبکه بسیار زیاد است.
برای کاهش ازدحام در گرههای بی‌سیم، الگوریتم‌های مسیریابی ارائه‌شده در [9,10,11,14]، یک پارامتر d را تعیین می‌کنند که مسیریابی را از یک مسیر سیمی یا بی‌سیم تعیین می‌کنند. d بزرگ‌تر به این معنی است که فقط بسته‌های دارای فاصله طولانی بین مبدأ و مقصد از کانال بی‌سیم استفاده کنند؛ اما این الگوریتم‌های مسیریابی، تحمل خطا را در نظر نگرفته‌اند.
فرستنده‌ها و گیرنده‌های مبتنی بر پهنای باند گسترده [1]که در [27,28] استفاده می‌شوند، به دلیل پهنای باند بالایی که دارند، به انتقال بستۀ چندگامی نیاز دارند که عملکرد کلی شبکه را کاهش دهند؛ در غیر این صورت در عملکرد شبکه تغییری صورت نمی‌گیرد.
عملکرد شبکه‌های بی‌سیم با معماری شبکۀ مش جهانی، در صورت وجود خطاهای دائمی، در [15,16] با استفاده از گرههای بی‌سیم کمکی بهبود می‌یابد. هرچند تحمل‌پذیری خطا در یک سیستم با افزونگی به دست می‌آید [1,2]، به دلیل زیادبودن تعداد گرههای افزونه، مساحت و هزینه افزایش یافته است.
در جدول 1، ویژگی‌های مهم‌ترین روش‌های ارائه‌شده در سال‌های اخیر، آورده شده‌اند.
جدول (1): ویژگی ساختارهای ارائه‌شده
|
تعداد مسیریاب‌های بی‌سیم |
تعداد هاب‌ها در یک زیرشبکه |
تعداد مسیریاب‌ها در هر زیرشبکه |
اندازه زیرشبکه |
تعداد گرههای شبکه |
|
|
16 |
- |
25 |
5×5 |
400 |
Ref. [23] |
|
6 |
1 |
16 |
4×4 |
256 |
Ref. [11] |
|
28-32 |
- |
25 |
5×5 |
400 |
Ref. [15,16] |
|
4 |
1 |
16 |
4×4 |
256 |
Ref. [29] |
|
16 |
1 |
25 |
5×5 |
400 |
Ref. [36] |
|
8-20 |
1 |
25 |
5×5 |
400 |
This work |
هدف ما در این مقاله ارائۀ یک معماری سه‌بعدی تحمل‌پذیر خطا است. معماری پیشنهادی با ترکیبی از معماری شبکۀ جهانی کوچک و شبکۀ مش جهانی، مزایای هردو شبکه را دارد. در صورت عدم وجود خطا و ازدحام، معماری مشابه با معماری شبکۀ کوچک جهانی است؛ زیرا این شبکه‌ها عملکرد بهتری نسبت به شبکه‌های دیگر دارند. به‌منظور کاهش مساحت و درجۀ اتصال هاب‌ها، در هر زیرشبکه چند گره انتخاب شده است که ازطریق سیم به هاب مرکزی متصل شده‌اند. همچنین برای کاهش مساحت، تعداد گرههای بی‌سیم در سطح دوم معماری کاهش یافته‌اند؛ به طوری که فقط هاب‌های دور از هم به‌صورت بی‌سیم با هم در ارتباط هستند.
در صورت وجود خطا و ازدحام، برای جلوگیری از تبدیل‌شدن هاب به گلوگاه و خارج‌شدن زیرشبکه متصل به هاب معیوب از شبکه، از مسیریاب بی‌سیم افزونه استفاده می‌کنیم که این مسیریاب‌ها در سطح اول معماری پیشنهادی قرار می‌گیرند و سیستم با وجود خطا و ازدحام به عملکرد خود ادامه می‌دهد و کارایی خود را از دست نمی‌دهد.
برای داشتن یک معماری تحمل‌پذیر، باید یک موازنه‌ای بین مساحت و هزینه با قابلیت اطمینان ایجاد شود؛ به طوری که با کمترین افزایش مساحت و هزینه بیشترین قابلیت اطمینان و بهره‌وری به دست آید. به همین منظور برای کاهش مساحت و هزینه سربار ناشی از اضافه‌کردن مسیریاب‌های بی‌سیم افزونه در سطح اول و بهینه‌سازی معماری پیشنهادی، از ماتریس تقاضا استفاده شده است.
این مقاله به‌صورت زیر سازماندهی شده است: در قسمت دوم، معماری پیشنهادی، مطرح و در قسمت سوم، معماری پیشنهادی براساس ماتریس تقاضا بهینه شده‌اند و در قسمت چهارم، چگونگی انتشار اطلاعات ازدحام و خطا در هاب بیان شده است. در قسمت پنجم الگوریتم مسیریابی توضیح داده شده است. در قسمت ششم، معماری پیشنهادی، ارزیابی و در پایان نتیجه‌گیری انجام شده است
معماری شبکۀ بی‌سیم روی تراشه با توپولوژی شبکه و الگوریتم مسیریابی مشخص می‌شود. در این بخش، یک معماری سه‌بعدی آگاه از ازدحام و مقاوم در برابر خطا، همراه با توپولوژی سطوح مختلف و الگوریتم مسیریابی آن ارائه شده است.
هدف یک سیستم تحمل‌پذیر خطا این است که با وجود خطا بتواند عملکرد خودش را به‌درستی انجام دهد. برای رسیدن به این قابلیت، باید از نوعی افزونگی استفاده کرد. هدف ما در این مقاله ارائۀ یک معماری تحمل‌پذیر خطا است که با افزونگی همراه است. در ابتدا، شبکه به چند زیرشبکه تقسیم می‌شود. بسته به نوع پیکربندی انتخاب‌شده، گرهها با سیم به هم متصل می‌شوند. هر زیرشبکه یک هاب مرکزی و یک مسیریاب مرکزی بی‌سیم افزونه دارد. از لحاظ ساختاری، هاب‌ها و مسیریاب‌ها شبیه به یکدیگرند. در هر زیرشبکه پنج گره انتخاب شده است که به هاب مرکزی ازطریق سیم به هم متصل شده‌اند. برای اتصال هاب‌ها، سطح دوم معماری دوسطحی تشکیل می‌شود.
در سطح دوم، هاب‌های دور از هم به‌صورت بی‌سیم با هم در ارتباط هستند. هاب‌ها به جای درگاه محلی، درگاههای اضافی برای ارتباط با گرههای داخل زیرشبکه دارند. برای افزایش قابلیت اطمینان معماری پیشنهادی، مسیریاب بی‌سیم در سطح اول معماری دو سطحی قرار می‌دهیم که در صورت معیوب‌شدن هاب‌ها، سیستم به عملکرد خود ادامه دهد. مسیریاب‌های بی‌سیم نیز دارای ارتباط بی‌سیم اضافی برای ارتباط با زیرشبکه‌های همسایه هستند؛ بنابراین، هاب بی‌سیم و مسیریاب بی‌سیم قابلیت انتقال بسته را ازطریق ارتباط سیمی و بی‌سیم دارند. در ادامه، سطوح مختلف این معماری بیان می‌شود.
در این کار، یک شبکه با 400 گره بررسی می‌شود. این شبکه به 16 زیرشبکه تقسیم و هر زیرشبکه در اندازه 5×5 ساخته می‌شود. دربارۀ معماری هابی معمولی، هر 25 گرۀ زیرشبکه به هاب متصل می‌شوند؛ بنابراین، مساحت ارتباطات سیمی افزایش می‌یابد. برای کاهش تعداد ارتباطات، فقط 5 گره از بین گرههای موجود در هر زیرشبکه، به‌طور مستقیم به هاب وصل می‌شوند. این گرهها را به نام ترمینال می‌شناسیم. نامگذاری این گرهها به این علت است که مانند ترمینال بسته‌ای را از یک گره می‌گیرند و به گرۀ دیگر تحویل می‌دهند. انتخاب مکان قرارگیری ترمینال‌ها بسیار مهم است؛ زیرا این گرهها باید تمام گرههای داخل شبکه را پوشش دهند. برای اتصال گرههای دیگر به این گرهها باید شرایط زیر برقرار شود:
با توجه به این شرایط، چگونگی ارتباط بین گرهها و ترمینال‌ها و همچنین ارتباط بین هاب و ترمینال‌ها در شکل 1 نشان داده شده است. هرکدام از گرهها که بخواهند به هاب دسترسی داشته باشند، ابتدا باید با یکی از این ترمینال‌ها ارتباط برقرار کنند.
شکل (1): انتخاب ترمینال و چگونگی ارتباط آنها با هاب مرکزی
برای افزایش قابلیت اطمینان شبکه، مسیریاب‌های بی‌سیم افزونه را در این سطح قرار می‌دهیم. برای پوشش خطایی که در هاب رخ می‌دهد و همچنین، برای جلوگیری ازدحام در آن، در هر زیرشبکه، یک مسیریاب بی‌سیم کمکی قرار می‌دهیم. مکان قرارگیری این گرۀ بی‌سیم در زیرشبکه مهم است تا فاصلۀ همۀ گرههای زیرشبکه با این گرۀ بی‌سیم کمینه شود. به علت فردبودن تعداد گرهها در تمام زیرشبکه‌ها، مرکز هر زیرشبکه محل مناسب برای قرارگیری آنتن است؛ زیرا تعداد فردبودن تعداد گرههای زیرشبکه‌ها، پیچیدگی را کم می‌کند. شکل 2، چگونگی ارتباط بین مسیریاب‌های بی‌سیم را در سطح اول نشان می‌دهد.
شکل (2): چگونگی ارتباطات بین گرهها در سطح اول پیکربندی
در سطح دوم، هاب‌های زیرشبکه‌ها به یکدیگر متصل می‌شوند. در این معماری، هر زیرشبکه 25 گره دارد؛ بنابراین، اگر n تعداد تمام گرههای شبکه باشد، تعداد هاب‌های موردنیاز برابر است با k=n/25؛ بنابراین، تعداد هاب موردنیاز 16 است. اگر ارتباط بین همۀ هاب‌ها از نوع بی‌سیم باشد، این مسئله به افزایش مساحت منجر خواهد شد و همچنین، توان مصرفی افزایش می‌یابد؛ بنابراین، تعداد هاب‌های بی‌سیم و مکان قرارگیری آنها نیز باید بررسی شود. براساس [30]، برای اینکه ارتباطات بی‌سیم مؤثر باشند، باید طول مسیر از 3 گام بیشتر باشد. k تعداد هاب‌های موردنیاز است. پس تعداد هاب بی‌سیم موردنیاز برابر با k/4 است. در این کار، 4 هاب بی‌سیم لازم است. حال آنچه اهمیت دارد، مکان قرارگیری هاب‌های بی‌سیم است. به دلیل شباهت بین پیکربندی مش و صفحۀ شطرنج، می‌توان از مسئلۀ چند وزیر برای مکان قرارگیری هاب‌ها استفاده کرد.
انتخاب مکان هاب‌های بی‌سیم
در نظر گرفته می‌شود هاب‌ها مانند مربع‌های صفحۀ شطرنج باشند و ارتباط سیمی بین دو هاب مانند دو مربع همسایه در یک صفحۀ شطرنج باشد، باید گفت این مسئله برای دو یا سه وزیر تعریف نشده است. با توجه به راه‌حل مسئلۀ چند وزیر، زمانی که اولین وزیر در صفحه قرار می‌گیرد، به دلیل اینکه وزیر به‌صورت افقی، عمودی و قطری حرکت می‌کند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد. برای وزیر بعدی، نباید آن را در جاهای ناپذیرفتنی که از قرارگرفتن نخستین وزیر به وجود آمده‌اند، گذاشت؛ به طوری که مورد تهدید وزیر قبلی نباشد. شکل 3، جاهای ناپذیرفتنی را برای وزیر بعدی نشان می‌دهد. در این شکل، خانه‌های به رنگ سبز جاهای پذیرفتنی را برای قرارگیری وزیر بعدی نشان می‌دهد.
شکل (3): مکان‌های ناپذیرفتنی برای وزیر بعدی
برای انتخاب مکان برای قرارگرفتن هاب‌های بی‌سیم و پیداکردن بهترین مکان، از الگوریتم شبیه‌سازی سردکردن و الگوریتم ژنتیک استفاده می‌شود. فرض می‌شود وزیرها با حرف i شماره‌گذاری شده باشند که وزیر i در ردیف i قرار گرفته باشد. شماره ستونی که وزیر ردیف i در آن قرار گرفته باشد را با نمایش می‌دهند؛ آنگاه یک جواب به‌صورت نمایش داده می‌شود.
الگوریتم شبیه‌سازی سردکردن: در این الگوریتم از فرایند سردکردن مواد استفاده شده است. در این فرایند، یک ماده تا نقطۀ ذوب گرم می‌شود. سپس به آهستگی، کاهش می‌یابد. در این روش، با تغییر در جواب‌های قبلی، راه‌حل جدید تولید می‌شود. این تغییرات باعث ایجاد راه‌حل‌های بهینه است. ممکن است در اثر تغییرات، راه‌حل بدتر پذیرفته شود که احتمال این کار با کاهش دما کم می‌شود. در اولین خط از شبه کد در الگوریتم 1، جواب اولیه با تابع تولید اعداد تصادفی ایجاد می‌شود. این تابع آرایه‌ای از اعداد صفر و یک را تولید می‌کند. در خط دوم پارامتر دما نیز مقداردهی می‌شود. در خط چهارم یک راه‌حل در همسایگی ایجاد می‌شود. برای افزایش همسایگی‌ها از توابع جابه‌جایی، بازگشت و درج‌کردن به‌صورت تصادفی استفاده می‌شود. راه‌حل جدید زمانی پذیرفتنی است که هزینه کمتری داشته باشد.
الگوریتم(1): الگوریتم SA
|
Input Model T0=1000 % Temperature Number of Queens f: Cost function Output: The location of queens (Hubs) 1: Set the initial temperature(T=T0) 2: Creat initial solution (s0 ) 3: P= Calculate f (s0 ) 4: while ( P>0) 5: Creat Neighbor (s) 6: Calculate f (s) 7: if ( f(s)<P) then 8: s0 = s 9: p= f(s) 10: else 11: Generate r: A uniform random number between 0 and 1 12: if r < then 13: s0 = s 14: p= f(s) 15: reduce temperature 16: return s0 |
الگوریتم ژنتیک: با استفاده از الگوریتم ژنتیک می‌توان به جواب‌هایی رسید که تا حد کافی مناسب باشند. با توجه به الگوریتم 2، مراحل الگوریتم عبارت‌اند از تولید نسل اولیه، انتخاب و عملگرهای ژنتیکی. در مرحلۀ تولید نسل اولیه تعدادی پاسخ به‌صورت تصادفی ایجاد می‌شوند. در مرحلۀ بعد، از نسل قبلی تعدادی از پاسخ‌ها انتخاب می‌شوند تا مولد پاسخ‌های جدید باشند. پس از انتخاب والدهای نسل بعد، با استفاده از عملگرهای ژنتیک، نسل بعدی ایجاد می‌شود. نکتۀ مهم اینکه تعداد پاسخ‌های هر نسل را برابر در نظر می‌گیرند و اندازه نسل را معمولاً تغییر نمی‌دهند.
دو عملگر معروف برای ایجاد نسل جدید عبارت‌اند از برش (خطوط 9-13) و جهش (خطوط 14-18). عمل برش اینگونه است که از ترکیب اطلاعات دو والد یک پاسخ جدید به وجود می‌آید. عمل جهش اینگونه است که مقادیر پاسخ به‌صورت تصادفی با یک احتمال (معمولاً این احتمال کم است) تغییر می‌کند و مقادیر دیگری اختیار می‌کنند؛ برای مثال، در یک نمایش دنباله بیتی می‌توان عمل جهش را به تغییر تصادفی هر کدام از بیت‌ها از یک به صفر یا برعکس تعریف کرد. شرایط پایان (خطوط 19-25): پس از انجام عملیات بالا یک نسل جدید از پاسخ‌ها به دست می‌آید.
سؤال این است که چه وقت ادامه فرآیند باید متوقف شود. برای شرط پایان پاسخ دقیقی مطرح نیست. یک پیشنهاد آن است که تعداد نسل ثابتی بررسی شود؛ برای مثال، فرآیند بالا را برای ۱۰۰۰ نسل تکرار شود و بهترین پاسخ از میان آنها انتخاب شود. پیشنهاد دیگر می‌تواند آن باشد که تا رسیدن به مقدار ارزیابی (fitness) مدنظر این فرآیند، تکرار شود.
در شکل (4) سطح دوم معماری نشان داده شده است. در این سطح، 16 هاب وجود دارد که یک مش 4×4 را تشکیل می‌دهد و در این کار، 4 هاب بی‌سیم لازم است و برای مکان قرارگیری این هاب‌های بی‌سیم، می‌توان از مسئله 4 وزیر استفاده کرد.
مطابق با الگوریتم‌های سردکردن و ژنتیک فرض می‌شود در ابتدا یک پاسخ به‌طور تصادفی به‌صورت ایجاد شود؛ به این معنا که اولین هاب بی‌سیم، در ردیف اول در ستون 4 که در شکل 4، همان گره 4 است، قرار می‌گیرد و دومین هاب بی‌سیم، در ردیف دوم در ستون 3 که همان گره 7 است، قرار می‌گیرد. طبق مسئله چند وزیر، در مکان گره 7 هاب بی‌سیم نمی‌تواند قرار بگیرد؛ زیرا مورد تهدید هاب بی‌سیم واقع در ردیف اول است؛ بنابراین، اگر در ستون 2 قرار بگیرد، مورد تهدید نیست. پس جواب بعدی به‌صورت می‌شود. با توجه به این جواب، مکان اولین و دومین هاب بی‌سیم مشخص شده است. هاب بی‌سیم سوم در ردیف سوم و ستون دوم که همان گره 10 است، باید قرار بگیرد که در ردیف سوم هیچ هاب بی‌سیمی را نمی‌توان قرار داد؛ زیرا مورد تهدید دو هاب بی‌سیم قبلی است؛ پس این جواب پذیرفتنی نیست.
در این صورت یک جواب دیگر به‌صورت بررسی می‌شود. بر اساس این جواب، هاب بی‌سیم اول به جای گره 3 قرار می‌گیرد و دومین هاب بی‌سیم باید در مکان گره 5 قرار گیرد تا مورد تهدید هاب بی‌سیم قبلی نباشد. پس جواب به‌صورت می‌شود. بر اساس این جواب، سومین هاب بی‌سیم باید ردیف سوم و ستون دوم قرار بگیرد که در این صورت مورد تهدید دومین هاب بی‌سیم است؛ اما اگر به جای گره 12 قرار گیرد، مورد تهدید نیست. به همین صورت، چهارمین هاب بی‌سیم به جای گره 14 قرار می‌گیرد. پس یکی از جواب‌های مسئله که از الگوریتم ژنتیک یا سردکردن به دست می‌آید، به‌صورت است که در شکل 4 هاب‌های بی‌سیم با رنگ قرمز نشان داده شده‌اند. برای این مسئله راه‌حل‌های متفاوتی وجود دارد. هرکدام از راه‌حل‌های بهینه برای مکان قرارگیری هاب‌های بی‌سیم استفاده می‌شوند.
شکل )4(: مکان هاب‌های بی‌سیم
الگوریتم(2): الگوریتم ژنتیک
|
Input Model: n pop : population size MaxIt: Maximum Number of Iteration nc: Number of offspring nm: Number of Mutants Output: The location of queens (Hubs) %% Initialization 1: for i= 1 to n pop do 2: initialize: Creat Random Solution 3: Evaluation 4: end 5: Sort Population 6: Store Best Solution 7: Store Cost
%%Main Loop 8: for it=1 to MaxIt do
%Crossover 9: for i=1 to (nc/2) do 10: Select Parents Indices 11: Select Parents 12: Apply Crossover 13: end
%Mutation 14: for j=1 to nm do 15: Select Parent 16: Apply mutation 17: Evaluate Mutation 18:end 19: Create Merged Population 20:Sort population 21: Update Worst Cost 22: Tnucation 23:Stor Best solution ever found 24: stor Bestevevfound 25:end |
3- بهینه‌سازی معماری پیشنهادی
با استفاده از ارتباط‌های بی‌سیم بین هسته‌ها، شبکۀ بی‌سیم روی تراشه به‌طور منطقی، عملکرد شبکۀ روی تراشه را افزایش داده است؛ با این حال، گیرنده‌های بی‌سیم به همراه آنتن مربوطه، فضا و مصرف انرژی درخور توجهی را به شبکۀ بی‌سیم روی تراشه تحمیل می‌کنند. در این مقاله یک معماری تحمل‌پذیر خطا ارائه شده که با افزونگی همراه است. در این قسمت به‌منظور افزایش قابلیت اطمینان معماری پیشنهادی، چندین مسیریاب بی‌سیم در سطح اول معماری دو سطحی فعال می‌شوند که در صورت معیوب‌شدن هاب‌ها، سیستم به عملکرد خود ادامه دهد؛ به طوری که کمترین افزونگی را داشته باشد.
در این مقاله که حل مشکل بالاست، سعی شده است تا فاصلۀ محل آنتن با عنصرهای پردازشی با سطح تقاضای بالا حداقل شود. براساس نتایج و مطالعات انجام‌شده [22,33,34]، به نظر می‌آید به علت فردبودن تعداد گرهها در تمام زیرشبکه‌ها مرکز هر زیرشبکه محل مناسب برای قرارگیری آنتن است. مسئله اینجاست که این مسیریاب بی‌سیم در مرکز کدام زیرشبکه قرار گیرد تا بهره‌وری شبکه افزایش پیدا کند.
اگر این روش به همۀ گرههای شبکه اعمال شود، درنهایت یک ماتریس تقاضا تشکیل شده است که مقدار مجموع روی ردیف iام ماتریس، سطح تقاضای آن گره خواهد بود. اگر تعداد گرههای یک شبکه n باشد، ماتریس تقاضا n×n خواهد بود. برای روشن‌شدن این مسئله، شکل 5 یک مثال ساده‌ای از یک شبکه با توپولوژی مش 2×2 است که درمجموع، 4 گره دارد و همچنین، یک الگوی ترافیکی فرضی قرار داده شده است.
براساس ترافیک داده‌شده، همۀ گرههای شبکه، مبدأ هستند؛ پس درایه‌های روی قطر اصلی ماتریس باید برابر یک باشند. گره 1 به‌عنوان مقصد گره 4 تعریف شده است؛ درنتیجه، در ماتریس درایۀ (1،4) باید یک باشد. با استفاده از الگوریتم DoR، برای انتقال یک بسته از گره 2 به گره 3، گره 4 ملاقات می‌شود؛ بنابراین درایۀ (4،2) باید یک شود. در شکل6، ماتریس تقاضا مربوط به شبکۀ شکل 5 و الگوی ترافیکی فرضی آن آمده است. سطح تقاضای هر گره نیز مجموع هر ردیف ماتریس است. در این مثال گرههای 3 و 4 بیشترین تقاضا را دارند؛ یعنی ازدحام در این گرهها بیشتر است. این ماتریس در مدل ورودی ذخیره شده است.
|
4 |
3 |
2 |
1 |
مبدأ |
|
1 |
4 |
3 |
2 |
مقصد |
شکل (5): یک شبکه مش 2×2 با یک الگوی ترافیکی فرضی
|
4 |
3 |
2 |
1 |
گره |
|
3 |
3 |
2 |
2 |
سطح تقاضا |
= ماتریس تقاضا
شکل (6): ماتریس تقاضا و سطح تقاضای هرگره
در معماری پیشنهادی، از ماتریس تقاضا برای انتخاب زیرشبکه‌هایی استفاده می‌شود که محل قرارگیری مسیریاب‌های افزونه در سطح اول هستند. براساس این ماتریس، مشخص می‌شود هاب مربوط به کدام زیرشبکه، سطح تقاضای بالایی دارد و در آن زیرشبکه مسیریاب بی‌سیم افزونه را قرار می‌دهیم. براساس ماتریس تقاضا می‌خواهیم 8 مسیریاب بی‌سیم افزونه در سطح اول قرار دهیم؛ به گونه‌ای که بهره‌وری سیستم افزایش پیدا کند و این مسیریاب‌ها را در زیرشبکه‌هایی قرار دهیم که ازدحام در آنجا بیشتر است و گره کمکی برای هاب آن زیرشبکه باشد.
الگوی ترافیکی فرضی در اینجا ترافیک نقطه داغ در نظر گرفته شده است. مقصد در زیرشبکۀ 11 قرار دارد؛ یعنی تمام گرههای شبکه، مقصدشان گره‌ای است که در زیرشبکۀ 11 قرار دارد. شکل 7، ماتریس تقاضای این شبکه را نشان می‌دهد. تمام زیرشبکه‌ها مبدأ هستند؛ پس تمام درایه‌های قطر اصلی ماتریس برابر یک است. براساس این الگوی ترافیکی، زیرشبکۀ 11 مقصد تمام زیرشبکه‌ها است؛ پس تمام درایه‌های سطر 11 نیز برابر یک است. با استفاده از الگوریتم DoR، گرههایی که در مسیر انتقال بسته از مبدأ به مقصد قرار دارند، مشخص می‌شود و به این صورت درایه‌های دیگر ماتریس صفر یا یک می‌شوند.
براساس ماتریس تقاضا در شکل 7، سطح تقاضای هرگره محاسبه شده است. گرههای بی‌سیم به همراه گرههای 7، 10 و11 بیشترین سطح تقاضا را دارند. سطح تقاضای بقیۀ گرهها یک است که یکی از این زیرشبکه‌ها برای فعال‌کردن مسیریاب بی‌سیم باید انتخاب شود. به دلیل اینکه زیرشبکه‌های بالاتر از زیرشبکۀ 11، فاصلۀ بیشتری تا این زیرشبکه دارند، زیرشبکۀ 6 انتخاب می‌شود. شکل 8، مسیریاب‌های بی‌سیم فعال در زیرشبکه‌های مربوطه در سطح اول معماری را نشان می‌دهد. در این صورت تعداد مسیریاب‌های بی‌سیم کاهش می‌یابد و بقیۀ مسیریاب‌های بی‌سیم در زیرشبکه‌های دیگر غیرفعال می‌شود.
4- انتشار اطلاعات ازدحام و خطا در هاب
در شبکه‌ها و الگوریتم‌های مسیریابی بدون ازدحام، تصمیمات مسیریابی بسته‌ها مستقل از شرایط ازدحام در شبکه انجام می‌شود؛ در این صورت، ممکن است توازن بار را مختل کند؛ زیرا وضعیت ترافیک شبکه در زمان مسیریابی بسته‌ها در نظر گرفته نشده است.
در الگوریتم‌های مسیریابی آگاه از ازدحام، مسیر بسته‌ها با توجه به شرایط ترافیک کانال‌های شبکه تعیین می‌شود. در شبکه‌های بی‌سیم روی تراشه به علت اشتراک‌گذاری هاب‌ها در بین هسته‌های یک زیرشبکه، هاب‌ها در معرض ازدحام قرار می‌گیرند؛ درنتیجه، تأخیر افزایش می‌یابد و ممکن است بعضی از بسته‌ها در اثر ازدحام از بین بروند و هیچ‌گاه به مقصد نرسند. اگر بافر انتقال‌داده به مرحلۀ بحرانی برسد، به طوری که اگر بستۀ جدیدی وارد بافر شود، بافر انتقال داده سرریز می‌کند و بسته‌ها از بین می‌روند، در این صورت در هاب ازدحام رخ داده است.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
گره |
|
1 1 3 1 2 1 3 1 1 2 16 8 1 2 1 1 |
سطح تقاضا |
شکل (7): ماتریس تقاضا و سطح تقاضای هر هاب
شکل (8): بهینه‌سازی سطح اول معماری
در [35]، برای توصیف درجۀ احتقان در بافر انتقال داده از استفاده شده است که از رابطۀ (1) به دست می‌آید:
|
(1) |
|
N تعداد فلیت‌های ذخیره‌شده در بافر انتقال داده و D عمق بافر است. براساس این رابطه هرچه بزرگ‌تر شود، ازدحام بیشتر می‌شود. با توجه به [35]، از برای نشان‌دادن آستانۀ ازدحام که مقدار بحرانی بافر را نشان می‌دهد، استفاده شده است و مقدار این پارامتر ازطریق چندین شبیه‌سازی به دست می‌آید؛ زیرا اگر بسیار کوچک در نظر گرفته شود، هاب خیلی زود در معرض ازدحام قرار می‌گیرد و اگر نزدیک به یک در نظر گرفته شود، ممکن است بعضی از بسته‌ها از بین بروند.
برای نشان‌دادن مشخصۀ ازدحام از استفاده شده است. اگر باشد، بافر انتقال داده به مرحلۀ بحرانی رسیده است و هاب از ازدحام رنج می‌برد؛ پس مقدار برابر با یک می‌شود و اگر باشد، مقدار صفر در نظر گرفته می‌شود. ترمینال‌ها ازطریق یک سیم تک‌بیتی مقدار هاب را دریافت می‌کنند و سپس مقدار را ازطریق سیم تک‌بیتی به چهار گره دیگر ارسال می‌کنند.
زمانی که هاب مربوط به یک زیرشبکه خراب شود، مانند شرایط ازدحام در هاب، مقدار برابر با یک می‌شود. ترمینال‌ها همانند شرایط ازدحام، مقدار را در سراسر زیرشبکه منتشر می‌کنند تا گرههای درون زیرشبکه از معیوب‌بودن تت هاب مرکزی آگاه شوند تا بسته‌های داده را به تاتتتتسمت ترمینال‌ها ارسال نکنند. شکل 9 نحوۀ انتشار مقدار را در شبکه نشان می‌دهد.
شکل (9): چگونگی انتشار اطلاعات تراکم و خطا
5-الگوریتم مسیریابی پیشنهادی
الگوریتم خوشه‌بندی که براساس تقسیم شبکه به مجموعه‌ای از گرهها در شرایط خاص است، برای حل مشکلات شبکه استفاده می‌شود. الگوریتم‌های خوشه‌بندی برای برآوردن اهداف خاص بسته به زمینه‌ای که خوشه در آن استفاده شده است، طراحی شده‌اند. خوشه‌بندی می‌تواند ایستا یا پویا باشد؛ در خوشه‌بندی ایستا شکل و اندازه خوشه در زمان اجرا تغییر نمی‌کند؛ ولی در خوشه‌بندی پویا اندازه خوشه در زمان اجرا تغییر می‌کند.
در این مقاله هر زیرشبکه به‌عنوان یک خوشه در نظر گرفته شده است؛ در این صورت خوشه‌بندی ایستا است؛ زیرا اندازۀ خوشه‌ها تغییر نمی‌کند؛ به همین دلیل می‌توان از الگوریتم‌های مسیریابی مربوط به مسیریابی بین خوشه‌های شبکه استفاده کرد. در اینجا از الگوریتم مسیریابی مبتنی بر جدول Q-table برای مسیریابی بین زیرشبکه‌ها استفاده شده است. زمانی که مبدأ و مقصد در یک زیرشبکه باشند، بسته با الگوریتم مسیریابی XY به مقصد ارسال می‌شود؛ اما اگر مبدأ و مقصد در یک زیرشبکه نباشند، دو حالت در نظر گرفته می‌شود:
در هر گره یک جدول به نام Q-table مطابق جدول 2، که برای گره صفر در نظر گرفته شده است، ذخیره می‌شود. از این جدول برای مسیریابی بین زیرشبکه‌ها استفاده می‌شود. براساس این جدول، زمانی که خطا یا ازدحام وجود ندارد، گرۀ صفر ترمینال نیست. گرۀ ترمینال همسایۀ پایینی این گره است. زمانی که خطا یا ازدحام وجود دارد، در صورت فعال‌بودن مسیریاب بی‌سیم در مرکز زیرشبکه، بسته به سمت شرق ارسال می‌شود. اگر مسیریاب بی‌سیم فعال نباشد، ازطریق سیمی به مقصد ارسال می‌شود. اندازۀ این جدول نسبت به جداول Look up table بسیار کوچک است.
جدول (2): Q-table
|
|
|
|
|
East |
South |
Output port |
5-1- مسیریابی در حالت اول
زمانی‌که گره مبدأ و گره مقصد در یک زیرشبکه نباشند، فاصلۀ بین گره مبدأ تا مقصد که شامل مسیر هابی و مسیر بدون هاب است، محاسبه می‌شود. با توجه به الگوریتم 3، (خطوط 15-6) اگر مسیرهابی کوتاه‌تر باشد، از همین مسیر برای ارسال بسته استفاده می‌شود. اگر گرۀ فعلی ترمینال نباشد، با استفاده از جدول Q-table، بسته به سمت ترمینال و سپس به هاب ارسال می‌شود در غیر این صورت، بسته به سمت هاب ارسال می‌شود؛ اما اگر مسیر سیمی کوتاه‌تر باشد، بسته با الگوریتم مسیریابی XY به سمت مقصد فرستاده می‌شود. در ادامه چگونگی محاسبۀ مسیرها بیان شده است.
مسیر بین گره مبدأ و مقصد ازطریق هاب: در بدترین حالت، گرۀ مبدأ و مقصد ترمینال نیستند و در زیرشبکه‌ای قرار دارند که هاب مرکزی آنها نیز بی‌سیم نیست. گره مبدأ یک گام تا ترمینال فاصله دارد و ترمینال مستقیماً به هاب متصل است؛ پس فاصلۀ مبدأ تا هاب مرکزی 2 است.
طبق معماری سلسله‌مراتبی، هاب مرکزی در صورتی که خودش بی‌سیم نباشد، با هاب بی‌سیم یک گام فاصله دارد؛ این هاب مرکزی بی‌سیم با یک گام به هاب مرکزی بی‌سیم دیگر که در همسایگی هاب زیرشبکۀ مقصد قرار دارد، فاصله دارد. اکنون فاصلۀ بین گره مبدأ تا هاب بی‌سیم در همسایگی زیرشبکۀ مقصد، 4 گام است. فاصلۀ هاب بی‌سیم تا هاب مرکزی زیرشبکۀ مقصد، یک گام است و هاب مرکزی به ترمینال مستقیماً متصل است و گره مقصد نیز به این ترمینال متصل است که درمجموع فاصلۀ بین گره مبدأ تا مقصد 7Hhub = می‌شود. در حالت‌های دیگر فاصلۀ بین مبدأ تا مقصد از 7 بیشتر نیست؛ بلکه کمتر از این مقدار است.
مسیر بین گره مبدأ و مقصد بدون استفاده از هاب: برای به دست آوردن این فاصله، یک شبکۀ مش دوبعدی با 400 گره در نظر گرفته می‌شود و مختصات گره مبدأ (Xs , Ys) و گره مقصد (Xd , Yd) است. فاصلۀ بین گره مبدأ و مقصد از رابطۀ (2) به دست می‌آید:
|
(2) |
Hnon-hub = | Xd - Xs | + | Yd - Ys | |
5-2- مسیریابی در حالت دوم
زمانی که مقدار برابر با یک می‌شود، نمی‌توان از هاب مرکزی برای ارسال بسته‌هایی استفاده کرد که گره مبدأ و مقصد آنها در یک زیرشبکه قرار ندارند. برای جلوگیری از سه نوع خطای گذرا، متناوب و پایدار از تکنیک افزونگی استفاده می‌شود. در این معماری پیشنهادی از تکنیک افزونگی سخت‌افزاری استفاده شده است. زمانی که هاب به هر علت از دسترس خارج می‌شود، با یک سیم تک‌بیتی خروج خود را از شبکه به تمام گرههای زیرشبکۀ محلی ازطریق ترمینال‌ها، اعلام می‌کند. در این صورت جای خود را به مسیریاب بی‌سیم در مرکز زیرشبکه می‌دهد.
با توجه به الگوریتم 3 (خطوط 19-16)، گرهها بسته‌های خود را با استفاده از جدول Q-table به سمت مسیریاب بی‌سیم هدایت می‌کنند. زمانی که بسته‌ها به مسیریاب بی‌سیم ارسال می‌شوند، مسیریاب بی‌سیم، بسته‌ها را با ارتباط بی‌سیم به نزدیک‌ترین زیرشبکۀ مقصد ارسال می‌کند. اگر مقصد در همان زیرشبکه‌ای باشد که هاب مرکزی آن بی‌سیم است، با الگوریتم XY به سمت مقصد هدایت می‌شود؛ اما اگر مقصد در زیرشبکۀ همسایه باشد، اگر هاب مرکزی آن زیرشبکه دچار خطا یا ازدحام نشده باشد، بسته ازطریق هاب به مقصد هدایت می‌شود.
الگوریتم( 3): الگوریتم مسیریابی پیشنهادی
|
Input: Source-Subnet-Number(S), Destination-Subnet-Number(D) Output: Routing path Begin
1. Hhub : Distance between source and distination using Hub 2. Hnon-hub : Distance between source and distination without using Hub 3. if (S == D ) then 4. using XY routing algorithm; 5. else 6. if ((Hhub Hnon-hub) & ( then 7. if ( Current node is not terminal) then 8. Send packet to the terminal; 9. Send packet from terminal to the hub; 10. else 11. Send packet to the hub; 12. end; 13. else if ((Hhub Hnon-hub) & ( then 14. using XY routing algorithm; 15. end; 16. else if ( then 17. Send packet to the wireless_router; 18. end; 19. end; |
6- ارزیابی معماری پیشنهادی
برای ارزیابی معماری پیشنهادی، از ابزار شبیه‌سازی OMNET++ با پکیج HNoC استفاده شده است [37,18]. شبیه‌ساز با پیاده‌سازی مسیریاب و ارتباط‌های بی‌سیم، توسعه داده شده است. در جدول 3، پارامترهای استفاده‌شده برای آنالیز آورده شده‌اند. روش پیشنهادی با معماری‌های پیشنهادی در مرجع [29] - که از آن به‌عنوان معماری سلسله‌مراتبی - و معماری پیشنهادی در مرجع [36] - که از آن به عنوان معماری پاند و همکارانش یاد می‌شود - مقایسه شده است.
جدول (3): پارامترهای شبیه‌سازی
|
Setting |
Parameters |
|
1 GHz 65nm 400 32Gbps Wormhole 4 32 bits |
Frequency Technology Number of cores on a chip Wireless channel bandwith Switching technique Number of wireless hob Flit width |
در این مقاله، از الگوی ترافیکی معرفی‌شده در مرجع [18] استفاده شده است. این الگوی ترافیکی بسیار شبیه به برنامۀ واقعی است. برای تولید یک الگوی ترافیکی نزدیک به برنامۀ واقعی نیاز به داشتن سه پارامتر مهم است. سه پارامتر مهم عبارت‌اند از: پشت‌سرهم[2]، تزریق[3] و فاصلۀ گامی[4].
پارامتر پشت‌سرهم، مدل‌کردن فرکانس است. در مدل‌کردن این ویژگی، از یک پارامتر به نام Hurst استفاده شده که مقدار آن بین 0.5 تا 1 است. در این مقاله، پارامتر پشت‌سرهم با مقدار H=0.65 که سطح moderate و H=0.9 که سطح High نامیده می‌شود، مدل شده است. از پارامتر تزریق برای مدل‌کردن تعداد بسته‌های تزریق‌شده به شبکه استفاده شده است. این پارامتر در دو مود نقطۀ داغ[5] و ترمیم‌شده[6] است. پارامتر فاصلۀ گامی یعنی فاصلۀ بین گره مبدأ تا مقصد است که در دو مود فاصلۀ زیاد [7] و محلی[8] است. این پارامترها در جدول 4 لیست شده‌اند.
در این مقاله، پارامترهای تأخیر، توان مصرفی و استفاده از ارتباط[9] و احتمال از دست رفتن بسته[10] ارزیابی شده‌اند.
جدول (4): الگوهای ترافیکی
|
Hop distance |
Injection |
Burstiness |
|
|
Local |
Hot-spot |
Moderate |
3tc0 |
|
Local |
Hot-spot |
High |
3tc1 |
|
Local |
Evened-out |
Moderate |
3tc2 |
|
Local |
Evened-out |
High |
3tc3 |
|
Long distance |
Hot-spot |
Moderate |
3tc4 |
|
Long distance |
Hot-spot |
High |
3tc5 |
|
Long distance |
Evened-out |
Moderate |
3tc6 |
|
Long distance |
Evened-out |
High |
3tc7 |
6-1- ارزیابی استفاده از ارتباط
گرههای بی‌سیم بین چندین گره به اشتراک گذاشته می‌شوند. به دلیل استفادۀ زیاد از آنها، منابعی آسیب‌پذیرند؛ بنابراین، استفاده از ارتباط بی‌سیم، بسیار مهم است. این پارامتر مهم از رابطۀ (3) به دست آمد:
|
(3) |
Link utilization = |
Busy time، مدت زمانی که از کانال استفاده می‌شود و Total time، زمان کل شبیه‌سازی است.
شکل 10 استفاده از ارتباط‌های بی‌سیم در معماری پیشنهادی با تعداد گرههای کمکی متفاوت، معماری سلسله‌مراتبی و معماری pande و همکارانش را نشان می‌دهد. براساس نتایج به‌دست‌آمده، استفاده از ارتباط‌های بی‌سیم، دلیل بر این نیست که همیشه تأخیر نیز کاهش پیدا می‌کند، بلکه ممکن است استفاده از ارتباط‌های بی‌سیم باعث افزایش ازدحام و درنتیجه، افزایش تأخیر شود. این نمودار نشان می‌دهد هرچه تعداد گرههای بی‌سیم کمکی بیشتر شود، ترافیک در کل شبکه توزیع می‌شود؛ درنتیجه، باعث کاهش ازدحام و تأخیر می‌شود.
شکل (10): استفاده از ارتباط بی‌سیم در الگوهای ترافیکی
براساس شکل 11، مجموع استفاده از ارتباط‌های بی‌سیم و سیمی در معماری پیشنهادی بیشتر از معماری سلسله‌مراتبی و معماری pande و همکارانش است. درواقع الگوریتم مسیریابی پیشنهادی علاوه بر اینکه از ازدحام جلوگیری می‌کند، باعث ایجاد تعادل بین ارتباط‌های سیمی و بی‌سیم می‌شود. در معماری پیشنهادی انتظار می‌رود هرچه تعداد گرههای کمکی در سطح اول بیشتر شود، میانگین استفاده از ارتباط‌های بی‌سیم و سیمی نیز افزایش یابد؛ اما در نمودار شکل 11، معماری پیشنهادی با 16 گرۀ کمکی، کاهش یافته است؛ زیرا با توجه به الگوی ترافیکی، از بعضی از ارتباطات استفاده نمی‌شود و بدین ترتیب مقدار آن پارامتر صفر منظور می‌شود؛ در این صورت، میانگین استفاده از ارتباط برای شبکه کاهش می‌یابد.
شکل (11): میانگین استفاده از ارتباط بی‌سیم و سیمی در الگوهای ترافیکی
6-2- احتمال از دست رفتن بسته
در معماری سلسله‌مراتبی و معماری pande و همکارانش قابلیت اطمینان و ازدحام در نظر گرفته نشده است. در این نوع معماری‌ها با وجود ازدحام، هاب‌ها تبدیل به گلوگاه می‌شوند و در صورت بروز خطا، تمام گرههای زیرشبکه از شبکه خارج می‌شوند؛ زیرا هیچ ارتباطی با زیرشبکه‌های دیگر ندارند. شکل 12، نمودار از دست رفتن بسته در شرایط وجود ازدحام و خطا را در یکی از هاب‌های بی‌سیم نشان می‌دهد. همان‌طور که مشاهده می‌شود این احتمال کاهش پیدا کرده و معماری به‌خوبی عمل کرده است.
شکل (12): احتمال از دست رفتن بسته
6-3- ارزیابی تأخیر
میانگین تأخیر بسته، یکی از مهم‌ترین پارامترهایی است که کارایی الگوریتم مسیریابی و معماری را مشخص می‌کند. براساس نمودار الف در شکل‌های 20-13، این نکته برداشت می‌شود که در تمام الگوهای ترافیکی میزان تأخیر برای معماری پیشنهادی کاهش یافته است. استفاده از گرههای کمکی در سطح اول معماری، باعث کاهش ازدحام شده است که در این صورت بسته‌ها مدت طولانی در بافر انتقال داده منتظر نمی‌مانند. همچنین، براساس انتخاب مسیر کوتاه‌تر بین گره مبدأ و مقصد، میانگین شمارش گام‌ها کاهش می‌یابد و درمجموع، باعث کاهش تأخیر می‌شود. حداکثر بهبود تأخیر با هر تعداد گرۀ کمکی، به‌طور میانگین با مقدار 45% در ترافیک 3tc4 رخ داده است.
6-4- ارزیابی توان عملیاتی
نمودار ب در شکل‌های 20-13 مربوط به پارامتر توان عملیاتی است که مقدار این پارامتر از رابطه (4) به دست می‌آید:
|
(4) |
|
طبق این رابطه، تعداد بسته‌های دریافت‌شده در معماری پیشنهادی، نسبت به معماری سلسله‌مراتبی افزایش یافته است، زیرا با استفاده از گرههای کمکی، بسته‌ها در اثر ازدحام یا خطا از بین نمی‌روند و به مقصد می‌رسند و همچنین، با کاهش زمان انتظار در بافر انتقال داده و انتخاب مسیر کوتاه، تعداد بسته‌های بیشتری در کل زمان دریافت می‌شود؛ درنتیجه، مقدار این پارامتر افزایش می‌یابد و معماری پیشنهادی با هر تعداد گرۀ کمکی در عملکرد عملیاتی بهبود بیشتری دارد. حداکثر بهبود توان عملیاتی با حدود 15% در ترافیک 3tc0 رخ داده است.
7- نتیجه‌گیری
با توجه به اینکه تعداد کانال‌های بی‌سیم محدود است و آنها در میان تمام عناصر پردازشی مشترک‌اند، استفاده بهینه از این منابع ارزشمند است. در صورتی که تعداد زیادی بسته بخواهد ازطریق کانال‌های بی‌سیم عبور کنند، در گرههای بی‌سیم و گرههای مجاور آنها ازدحام رخ می‌دهد و به کاهش کارایی منجر می‌شود. همچنین، در صورت خطا در گرههای بی‌سیم، ارتباط بعضی از گرهها با گرههای دیگر قطع می‌شود و از شبکه خارج می‌شوند؛ بنابراین، باید از مکانیزم‌های خاصی برای جلوگیری از انتقال بیش از حد بسته‌ها به سمت گرههای بی‌سیم استفاده شود.
در این مقاله یک معماری دو سطحی آگاه از ازدحام با قابلیت تحمل‌پذیری خطا ارائه شده است. استفاده از گرههای کمکی در سطح اول، تأثیر چشمگیری در کاهش تأخیر دارد و علاوه بر کاهش ازدحام، استفاده از ارتباط سیم و بی‌سیم را متعادل می‌کند. نتایج ارزیابی، بهبود درخور توجهی در پارامترهای تأخیر، توان عملیاتی، احتمال از دست رفتن بسته و استفاده از ارتباط را نشان می‌دهد.
در کارهای آینده، معماری و الگوریتم مسیریابی پیشنهادی در این مقاله، می‌توانند با رویکردهای دیگر ترکیب شوند. علاوه بر این، اطلاعات ازدحام با استفاده از ویژگی‌های منحصربه‌فرد کانال‌های بی‌سیم مانند خاصیت پخشی در زیرشبکه‌های مختلف منتشر شود.
|
|
|
|
(ب) |
(الف) |
شکل (13): مقایسۀ الف) تأخیر و ب) توان عملیاتی در الگوی ترافیکی 3tc0
|
|
|
|
(ب) |
(الف) |
شکل (14): مقایسۀ الف) تأخیر و ب) توان عملیاتی در الگوی ترافیکی 3tc1
|
|
|
|
(ب) |
(الف) |
شکل (15): مقایسۀ الف) تأخیر و ب) توان عملیاتی در الگوی ترافیکی 3tc2
|
|
|
|
(ب) |
(الف) |
شکل (16): مقایسۀ الف) تأخیر و ب) توان عملیاتی در الگوی ترافیکی 3tc3
|
|
|
|
(ب) |
(الف) |
شکل (17): مقایسۀ الف) تأخیر و ب) توان عملیاتی در الگوی ترافیکی 3tc4
|
|
|
|
(ب) |
(الف) |
شکل (18): مقایسۀ الف) تأخیر و ب) توان عملیاتی در الگوی ترافیکی 3tc5
|
|
|
|
(ب) |
(الف) |
شکل (19): مقایسۀ الف) تأخیر و ب) توان عملیاتی در الگوی ترافیکی 3tc6
|
|
|
|
(ب) |
(الف) |
شکل (20): مقایسۀ الف) تأخیر و ب) توان عملیاتی در الگوی ترافیکی 3tc7
[1] تاریخ ارسال مقاله: 30/05/1400
تاریخ پذیرش مقاله: 17/08/1401
نام نویسندۀ مسئول: وحید ستاری نایینی
نشانی نویسندۀ مسئول: ایران - کرمان - دانشگاه شهید باهنر کرمان - گروه مهندسی کامپیوتر
[1] Ultra Wide Band (UWB)
[2] Burstiness
[3] Injection
[4] Hop distance
[5] Hotspot
[6] evened-out
[7] Long distance
[8] Local
[9] Link utilization
[10] Packet-loss probability
)