وبلاگ

الگوریتم حلقه‌نشانه
یک روش کاملاً متفاوت برای رسیدن به انحصار متقابل قطعی در سیستم توزیع شده در شکل ۴-۳ آمده است در اینجا یک شبکه خطی داریم (شکل ۴-۳ الف) مثل اترنت، که فاقد ترتیب فرایندها است. در نرم افزار یک حلقه منطقی ساخته می‌شود که در آن به هر فرایند مکانی در حلقه داده می‌شود (شکل ۴-۳ ب) موقعیت‌های حلقه ممکن است به ترتیب عددی آدرس‌های شبکه یا ابزارهای دیگری تخصیص یابد مهم نیست که ترتیب چه باشد. مهم این است که هر فرایند می‌داند بعد از آن چه کسی قرار دارد]۷۰[.

شکل ‏۴‑۳- الگوریتم حلقه نشانه ]۷۰[
وقتی حلقه آماده شد به فرایند، یک نشانه داده می‌شود این نشانه در حلقه دور می‌زند از فرایند k به k+1 می‌رود و بررسی می‌کند که آیا این فرایند نیاز به دستیابی به منبع مشترک دارد یا خیر. اگر نیاز داشته باشد فرایند به پیش می‌رود تمام کارهای خودش را انجام می‌دهد و منابع را آزاد می‌کند پس از پایان کار نشانه را در امتداد حلقه رها می‌کند اجازه ندارد که فوراً با بهره گرفتن از همان نشانه وارد منبع دیگری شود.
اگر فرایندی نشانه را از همسایه خود بگیرد و به منبعی علاقه‌مند نباشد فقط آن را به فرایند دیگر می‌فرستد در نتیجه وقتی هیچ فرایندی به منبع نیاز ندارد نشانه فقط با سرعت بالایی در حلقه دور می‌زند.
صحت این الگوریتم را می‌توان مشاهده کرد در هر زمان فقط یک فرایند نشانه را در اختیار دارد، لذا فقط یک فرایند می‌تواند به منبع دستیابی داشته باشد چون نشانه بین فرایندها به ترتیب تعریف شده‌ای حرکت می‌کند گرسنگی رخ نمی دهد]۷۰[. وقتی فرایندی تصمیم می‌گیرد که به منبعی دستیابی داشته باشد در بدترین حالت باید منتظر بماند تا هر فرایند دیگری را منبع استفاده نماید.
طبق معمول این الگوریتم نیز مشکلاتی دارد اگر نشانه مفقود شود باید دوباره تولید شود در حقیقت تشخیص مفقود شدن نشانه دشوار است زیرا مدت زمان بین ظهور متوالی نشانه در شبکه، مفید نیست. این حقیقت که نشانه به مدت یک ساعت مشاهده نشده است به معنای این نیست که مفقود شده است؛ ممکن است هنوز کسی در حال استفاده از آن باشد.
اگر فرایندی خراب شود الگوریتم دچار دردسر می‌شود اما ترمیم آن نسبت به موارد دیگر آسان تر است اگر لازم باشد فرایند گیرنده نشانه، دریافت آن را اعلام وصول کند.
اگر فرایند مرده باشد هنگامی که همسایه آن سعی می‌کند نشانه را به آن بدهد ولی با شکست مواجه می‌شود قابل تشخیص است در آن نقطه فرایند مرده می‌تواند از گروه حذف شود و صاحب نشانه را می‌تواند از فرایند مرده عبور دهد و به فرایند بعد از آن تحویل دهد. البته این کار مستلزم این است که هر کسی پیکربندی فعلی حلقه را نگهداری نماید.
شباهت‌های شبکه‌عصبی و سیستم توزیع‌شده
ما به‌خوبی می‌دانیم که شبکه‌های عصبی بدن انسان از هر برخورد و تصادفی بدور بوده است و مدل‌های شبکه عصبی اثبات شده هستند. بنابراین اگر ما یک سیستم توزیع‌شده را با یک شبکه عصبی تطبیق دهیم (مدلسازی نماییم) در نتیجه یک سیستم قابل اطمینان و تحمل‌پذیر خطا را خواهیم داشت [۴۸].
در این شبیه‌سازی، هر گره با یک پیام از یک سلول عصبی (نرون) شبیه‌سازی می‌شود زیرا آنها یکی از اجزایی هستند که برای ساخت سیستم‌های همروند استفاده می‌شود. گره‌ها یک نقش اساسی در شبکه‌های حسگر بازی می‌کنند و به عنوان یک پایه و اساس در ارتباطات بین سایر گره‌ها می‌باشد. یکی از موضوعات مهم برای سیستم‌های توزیع‌شده از جمله شبکه‌های حسگر مهاجرت کد بین ماشین‌های مختلف است که یک نرم افزار عامل و یک نوع خاص از فرآیندها است و بصورت یک واحد مستقل عمل می کند ولی می‌تواند با عوامل دیگر نیز همکاری نماید. ویژگی‌های هر فرایند می‌تواند مشابه با یک نرون باشد زیرا هر نرون دارای هوش مخصوص به خود بوده و می‌تواند به عنوان یک سیستم عمل نماید و به‌صورت مستقل دارای ورودی، پردازش و خروجی است [۴۹, ۵۰, ۵۱]. برخی از سلول‌های عصبی (نرون‌ها) می‌توانند بعنوان واحد تصمیم‌گیرنده عمل کنند و بعضی از آن‌ها تنها انتقال دهنده اطلاعات و داده در سراسر شبکه عصبی هستند. در سیستم‌های توزیع‌شده، برای مثال در الگوریتم متمرکز، هماهنگ‌کننده‌ها یک فرایند انتقال‌دهنده است که تعداد فرآیندهای موجود در صف و فرآیندی که اجازه ورود به بخش بحرانی را گرفته‌ است انتقال داده و به سایرین اطلاع می‌دهد. همچنین، از سوی دیگر در یک سیستم توزیع‌شده هر فرایند می‌تواند درخواستی داشته باشد و با دریافت پاسخ از سیستم کار نماید. بنابراین هر فرایند یک سیستم بوده زیرا دارای ورودی، پردازش و خروجی است. خروجی هر فرایند می‌تواند توسط خود و یا دیگر فرایند‌ها مورد استفاده قرار گیرد [۵۲].
منابع
اولاً، منابع در هر دو سیستم بین فرایند‌ها و نرون‌ها به اشتراک گذاشته می‌شود بنابراین آن‌ها می‌توانند از این منابع استفاده نمایند. دوماً، ناحیه بحرانی در هر سیستمی وجود دارد. در یک مدل رقابتی شبکه عصبی جهت رقابت برروی دسترسی به منابع ایجاد و ساخته می‌شود؛ در یک سیستم توزیع‌شده نیز یک منبع داخل ناحیه بحرانی نشان دهنده نیاز به رقابت برای دسترسی به آن است. نظام یک سیستم توزیع شده بدین‌صورت تعریف می‌شود: مجموعه‌ای از اجزا که برای رسیدن به یک هدف منحصر به فرد و واحد با هم همکاری می‌کنند. همچنین یک فکر یا فرمان در ذهن انسان هدفی است که با همکاری سلول‌های عصبی به آن می‌رسد. بنابراین یک شبکه عصبی یک سیستم است [۵۳].
شفافیت
«یک سیستم توزیع شده از تعدادی سیستم مستقل تشکیل شده است که از دید کاربر یک سیستم واحد و منسجم می‌باشد» [۵۴]. در یک شبکه عصبی نیز هر سلول بصورت جداگانه عمل می کند و مستقل از سایر سلول‌ها می‌باشد. بنابراین رفتار شبکه خروجی رفتارهای محلی سلول‌ها است. این ویژگی سبب می‌شود که خطاهای محلی شبکه عصبی پوشش داده شود و برروی خروجی نهایی تاثیرگذار نباشد. همچنین همکاری سلول‌ها سبب می‌شود خطاهای محلی اصلاح شوند. یک نتیجه از این ویژگی دست‌یابی به تحمل‌پذیری بالاتر و استحکام و مقاوم‌بودن در یک سیستم شبکه عصبی کامل است. از سوی دیگر این ویژگی همان شفافیت است که در سیستم‌های توزیع‌شده ذکر شده است.
عملیات یادگیری
عملیات یادگیری که در شبکه‌های عصبی مورد استفاده قرار می‌گیرد شبیه به الگوریتم‌هایی است که ما در سیستم‌های توزیع‌شده به‌کار می‌بریم. در واقع، ما به سیستم توزیع‌شده با الگوریتم‌ها یاد می‌دهیم که چطور آن‌ها روی یک سیستم کلی اجرا شوند.
مدل مشتری - خدمت‌گذار
همانطور که می‌دانید، یک سیستم توزیع‌شده شامل سرویس‌گیرندگان و سرورهایی می‌شود و هر یک از آنها نیز شامل فرایند‌هایی هستند. سلول‌های عصبی نیز بطور مشابه بوده زیرا بعضی از آنها سلول‌هایی هستند که حس می‌کنند (کلاینت) و مابقی آن‌ها محرک‌ها (سرورها) هستند. دسته دیگر از سلول‌های عصبی، نرون‌های ارتباطی هستند که مشابه تجهیزات شبکه (کابل، روتر و مانند آن‌ها) بوده است. ارتباطات در یک شبکه عصبی مشابه یک شبکه حسگر که نوعی از سیستم توزیع‌شده است، می‌باشد. از آنجا که، فرآیندها می‌توانند داده‌ها را در کل شبکه منتقل نمایند و بدین ترتیب زیرساخت سیستم‌های توزیع‌شده ایجاد شود در شبکه‌های عصبی نیز سیانپس‌ها (محل اتصال دو عصب) و برخی از نرون‌ها این کار را انجام می‌دهند و بنابراین این زیرساخت ایجاد می‌شود [۵۵].
پردازش موازی
موازی بودن نیز در هر دو سیستم اتفاق می‌افتد. در شبکه‌های عصبی همه سلول‌هایی که در یک سطح قرار دارند می‌توانند بصورت موازی عمل نمایند. از سوی دیگر، یک سیستم توزیع شده دارای زیرساخت‌های مناسب برای پردازش موازی است (در هر مکان دارای حافظه‌های محلی و حافظه‌های توزیع شده اشتراکی است).
شبکه‌های عصبی یک سیستم خودسازمان‌ده هستند و بنابراین می‌توانند بعنوان یک سیستم کنترلی با بازخورد در نظر گرفته شود [۵۶,۵۷]. بازخورد سبب می‌شود که سیستم پایدار باشد [۵۸]. همانگونه که مشخص است استمرار اجرای سیستم و مقایسه خروجی و مقدار هدف در یک سیستم سبب می‌شود خطا به حداقل خود ‌رسد. هنگامی که ما یک سیستم توزیع‌شده را بر یک شبکه عصبی تطبیق می‌دهیم باید یک سیستم پایدار داشته باشیم. بنابراین خطا باید کاهش یابد. حداقل نمودن خطا در هرسیستمی به قابلیت اطمینان آن سیستم کمک می کند. از سویی دیگر کاهش خطا سبب می‌شود که سیستم متحمل‌پذیر خطا باشد.
سخت‌افزار و نرم‌افزار
سخت‌افزار سیستم‌‌های توزیع شده دارای ارتباطات غیر محکم (سست) می‌باشند. در یک شبکه عصبی نیز، اگر یک بخش شبکه آسیب ببیند یا پاک شود یا از کار بیفتد بخش یا بخش‌های دیگر کار خواهند کرد. بنابراین سخت‌افزار در یک سیستم‌توزیع شده همانند یک بخش از شبکه عصبی است. همچنین نرم‌افزار سیستم توزیع‌شده دارای ارتباطات محکم هستند. بنابراین هر بخشی از نرم‌افزار مهم است. در یک شبکه عصبی فکر کردن بعنوان نرم‌افزار برروی سیستم است. بنابراین اگر بخشی از نرم‌افزار خراب شود سیستم دقیقا به هدف تعریفی نخواهد رسید. به عبارت دیگر، خروجی سیستم دچار مشکل خواهد بود. در واقع یک شبکه عصبی یک سیستم توزیع‌شده حقیقی و درست نیست ولی یک سیستم توزیع شده است[۵۴].
مدل پیشنهادی
روش ارائه شده در این پایان‌نامه یکی از مدل‌های شبکه عصبی رقابتی، مدل رقابتی همینگ [۱] را بکار برده است. این مدل که از مدل‌های خود سازمانده می‌باشد و دارای سه لایه: لایه بازخورد، لایه رقابت (رقابت بین سلول‌ها و تعیین یک سلول به عنوان سلول برنده بر سایر سلول‌ها) و لایه خروجی که نمونه سازی و مقایسه هر سلول را تعریف می‌کند، است [۱,۵۹].
ورودی‌های شبکه فاصله بردارهای ورودی از بردار مرجع می‌باشد. هر بردار از تعدادی مولفه تشکیل شده است و به شکل V=I₁,I₂, … , I_n نشان داده می‌شود که هر کدام از مولفه‌ها متشکل از نام بردار و مقدار می‌باشد. آیتم‌های تشکیل دهنده بردار‌ها برچسب زمانی، زمان اجرا و اولویت است. رقابت بین فرآیندها برای در اختیار گرفتن ناحیه بحرانی با توجه به این سه مورد انجام خواهد شد. با توجه به عدم نیاز به وجود ساعت زمانی در یک سیستم توزیع شده، برچسب‌های زمانی به فرآیندها با توجه به ساعت لمپورت اختصاص داده می‌شود [۴۷]. در زمینه انحصار متقابل ساعت لمپورت بدین‌صورت عمل می‌کند: هر فرایند یک مقدار عددی نشان‌دهنده ساعت با مقدار اولیه صفر را نگهداری می‌کند؛ با هر بار دسترسی فرایند به ناحیه بحرانی یک واحد به این برچسب زمانی افزوده می‌شود.
حالا ما فرض می‌کنیم که این سه پارامتر مهم سه بعد از مدل همینگ می‌باشد. در گام اول این شبیه‌سازی با توجه به این موضوع، بردار وزن در این محیط را تعریف می‌کنیم. بنابراین برای ایجاد بردار وزن ما خواهیم داشت:
(۱)
که در آن a,b,c مقادیر و x,y,z سه مولفه (برچسب زمانی، زمان اجرا و اولویت) از بردار V می‌باشند. i نیز که از ۱..n بوده تعداد درخواست‌ها می‌باشد. در شکل ۴-۱ سه بعد از بردارهای ورودی برای رقابت را مشاهده می‌نمایید.
شکل ‏۴‑۴- سه بعد شرکت کننده در رقابت
این عمل را برای تمام درخواست‌ها انجام می‌دهیم. شرکت کنندگان در رقابت را به دو روش مشخص می‌نماییم:
تمامی درخواست کنندگان منتظر برای در اختیار گرفتن ناحیه بحرانی
تنها درخواست کنندگان دارای کمترین برچسب زمانی همسان
در روش اول با توجه به بردار مرجعی که در ادامه ساخته می‌شود برنده رقابت مشخص می‌شود و روش دوم با دیدگاه اولویت قرار دادن به درخواست‌هایی که کمتر ناحیه بحرانی را در اختیار گرفتند و برای مبارزه با بن‌بست و گرسنگی این عمل را انجام می‌دهد اما در سیستم‌هایی که درخواست‌های فراوانی و با فواصل زمانی کم ایجاد و به صف درخواست‌ها افزوده می‌شود روش مناسبی نیست. بطور کلی می‌توان به تنهایی روش اول و یا ترکیب دو روش را برگزید و یا لیست درخواست‌های ورودی را در اختیار گرفت و همه آن‌ها را پاسخ داد و بعد از پاسخدهی به همه درخواست‌ها دوباره این عمل را روی لیست درخواست‌های رسیده بعد از در اختیار گرفتن لیست قبلی تکرار نمود. در نهایت علاوه بر ایجاد همه بردارهای وزن مربوط به درخواست‌ها، با توجه به انتخاب یکی از روش‌های مزبور نیاز به ساخت یک بردار مرجع نیز داریم. که برداری با بیشترین شباهت با این بردار در نهایت برنده رقابت خواهد بود. برای ساخت بردار وزن مرجع از فرمول زیر استفاده می‌نماییم:
(۲)
حال برای ایجاد ورودی‌های مناسب برای شبکه‌های عصبی رقابتی بردارهای وزن همه درخواست‌ها به همراه بردار وزن مرجع را به یک عدد با بهره گرفتن از فرمول ۳ نگاشت می‌نماییم. برای این عمل از فاصله اقلیدسی [۶۰] استفاده نموده و بردار وزن مرجع را با مبداء مختصات و سایر بردارها را با بردار مرجع در نظر می‌گیریم.
(۳)
که در آن p و q دو بردار وزن مورد محاسبه بوده و p_i و q_i مولفه‌های این دو بردار می‌باشند.
پس از این مرحله همه بردارهای حاصل از درخواست‌ها و بردار مرجع، ایجاد شده و رقابت شروع می‌شود. یادگیری رقابتی بکاربردن رقابت بین سلول‌های عصبی، یک شبکه عصبی، برای مشخص نمودن اینکه کدام یک فعال باشد. در شبکه عصبی که براساس سایر یادگیری‌ها می‌باشد ممکن است چندین سلول عصبی بطور همزمان فعال باشند ولی در یادگیری رقابتی تنها یک سلول عصبی، به عنوان خروجی فعال در هر دفعه خواهد بود. این ویژگی می‌تواند برای دسته‌بندی مجموعه الگوهای ورودی مورد استفاده قرار گیرد. سه جزء پایه برای یک قاعده یادگیری رقابتی وجود دارد:
مجموعه‌ای از سلول‌های عصبی که در همه اجزا مانند هم هستند به جز وزن سیناپس‌ها بصورت تصادفی توزیع‌شده است که این موضوع سبب می‌شود جواب‌های مختلفی به مجموعه الگوهای ورودی داده شود.
محدودیت‌های اعمال شده برروی هر نرون.
روشی که به سلول‌های عصبی اجازه رقابت دهد تا جوابی درست را برای زیرشبکه ورودی داده شده تولید نماید. در این جواب تنها یک نرون و یا تنها یک نرون در هر گروه بعنوان خروجی در هر بار فعال خواهد بود. نرون برنده رقابت بعنوان برنده بین همه نرون‌ها نامیده می‌شود.
بر این اساس سلول‌های عصبی بطور مجزا از شبکه یاد می‌گیرند و گروه الگوهای مشابه را تشخیص می‌دهند برای انجام این کار آن‌ها، ویژگی‌های تشخیص داده شده، الگوهای ورودی را به دسته‌ه ای مختلف تبدیل می‌کنند.
در ساده‌ترین شکل از یادگیری رقابتی، شبکه عصبی یک لایه بوده و متشکل از سلول‌های عصبی خروجی است که هر کدام بطور کامل به گره‌های ورودی متصل هستند. در معماری شبکه، اتصالات بازخورد مهار جانبی را فراهم می‌آورند بطوریکه هر سلول عصبی، نرون‌هایی که با آن اتصال جانبی دارند را مهار می‌نمایند.
یک سلول عصبی k در صورتی سلول برنده خواهد بود که همه فیلدهای محلی V_k برای الگوی ورودی مشخص شده X، باید بزرگترین مقدار را در میان همه سلول‌های شبکه داشته باشد. طبق رابطه ۴ سیگنال خروجی y_k سلول عصبی برنده k با یک نشان داده می‌شود و سیگنال خروجی همه سلول‌های عصبی دیگر که در رقابت بازنده شده‌اند برابر با صفر قرارداده می‌شود.
y_k=1 if V_k>V_j for all j , j≠k (4)
y_k=0 Otherwise
در اینجا فیلد‌های محلی V_k نشان داده شده، شامل ترکیب همه ورودی‌های بازخوردی و پیش‌رونده سلول‌های عصبی k می‌باشد. اجازه دهید که W_kj مشخص کننده وزن سیناپسی باشد که گره ورودی j را به سلول عصبی k متصل می کند. فرض کنید به هر سلول عصبی یک مقدار ثابت به عنوان وزن سیناپسی اختصاص داده شده است (همه وزن سیناپسی مثبت هستند) که میان گره‌های ورودی خودش توزیع شده است و بدین صورت است که:
(۵)
سلول‌های عصبی با تغییر وزن سیناپس‌ها یاد می‌گیرند که کدام گره ورودی فعال و کدام یک غیرفعال است. اگر یک سلول عصبی پاسخی به الگو ورودی خاصی ندهد، هیچ یادگیری در آن سلول عصبی اتفاق نخواهد افتاد. اگر یک سلول عصبی خاص برنده رقابت شود، به هر سلول از نرون‌های ورودی با نسبتی یک وزن سیناپسی تعلق می‌گیرد که این نسبت بطور مساوی بین همه گره‌های فعال توزیع می‌شود. با توجه به قاعده استاندارد یادگیری رقابتی، تغییرات W_kj∆ اعمال شده به وزن سیناپسی W_kj بصورت زیر تعریف می‌شود:
∆W_kj =(X_j-W_kj)برنده شده باشد kاگر نرون (۶)
∆W_kj =۰ بازنده رقابت باشد k اگر نرون
در اینجا η پارامتر نرخ یادگیری است. این قاعده تاثیر کلی روی حرکت بردار وزن سیناپسی W_k مربوط به نرون برنده k به سمت الگوی ورودر X دارد. فرض بر این است که همه سلول‌های عصبی در شبکه بوسیله طول اقلیدسی مشابه محدود شده‌اند و این موضوع بصورت زیر نشان داده می‌شود:
(۷)
طبق قواعد همینگ هر فرآیندی که شبیه به بردار مرجع خواهد بود آن بر همه چیره خواهد شد و ناحیه بحرانی را در دست خواهد گرفت. در شکل ۴-۲ مثالی از این رقابت را و ترتیب برنده شدن درخواست‌ها را مشاهده می‌نمایید.
شکل ‏۴‑۵- انتخاب یک بردار (درخواست) غالب