دانلود پایان نامه با موضوع زمانبندي، گره‌‌‌ها، BS، لينک

نشانه‌هاي موجود خود از پنجره‌هاي زماني براي ارسال استفاده نمايد. با اختصاص هر پنجره به يک گره‌‌‌، يکي از تعداد نشانه‌هاي فرستنده آن لينک کاسته شده و يکي به تعداد نشانه‌هاي گيرنده يک گره‌‌‌، يکي از تعداد نشانه‌هاي فرستنده آن لينک کاسته شده و يکي به تعداد نشانه‌هاي گيرنده BS هدايت کند. لذا به اين وسيله مدل ذاتي رله ترافيک در شبکه‌هاي مش در الگوريتم گنجانده شده است. همچنين سعي شـده است به اين وسيـله عدالت در شبـکه رعايت شود و برخي گره‌‌‌ها دچار گرسنـگي نشوند. تعداد نشانـه‌هايي که به گره‌‌‌ i اختصـاص داده مي شود (Tokeni) از رابطه tokeni = tri/g، که در آن g بزرگترین مقسوم علیه مشترک ترافیک ها و tri ترافیک درخواستی هرگره‌‌‌ است محاسبه می‌شود.
اگر سه مرحله زمانبندي در [a241]نظرگرفته[a242] شود، الگوريتم TTS در مرحله رتبه‌بندي چهار سياست مختلف براي انتخاب لينک‌ها در هر پنجره زماني را معرفي کرده است. در زير اين چهارروش آورده شده است.
تصادفي : انتخاب لينک به صورت تصادفي انجام مي شود.
مينيمم تداخل: [a243]لينکي براي زمانبندي انتخاب مي شود که فرستنده آن، تعداد SS هاي کمتري را دچار تداخل مينمايد.
تعداد گام کمتر تا BS: لينکي براي زمانبندي انتخاب مي شود که فرستنده آن، تعداد گام‌هاي کمتري تا BS دارد.
تعداد گام [a244]بيشتر تا BS: لينکي براي زمانبندي انتخاب مي شود که فرستنده آن، تعداد گام‌هاي بيشتري تا BS دارد.
هنگاميکه که گره‌‌‌ها در شرايط مساوي هستند(تعداد گام‌هايشان تا BS يکسان است يا تداخلي که ايجاد مي‌کنند برابر باشد) گره‌‌‌ي که شناسه کوچکتري دارد، اولويت بيشتري دارد. در نهايت با مقايسه‌هاي صورت گرفته، سياست سوم، انتخاب گره‌‌‌ي که تعداد گام کمتري تا BS دارد، به عنوان سياست برتر معرفي شده است.
در مرحله دوم، به منظور انجام زمانبندي در ابتدا وضعيت تمام لينک‌هايي که تعداد نشانه‌هاي فرستنده بر روي آن لينک غير صفر است، فعال[a245] برچسب مي‌خورد. ساير لينک‌ها نيز بيکار هستند. هدف زمانبندي لينک‌هاي فعال است. لذا در هر پنجره زماني ابتدا يک لينک فعال براي زمانبندي انتخاب شده و در وضعيت زمانبندي شده قرار مي‌گيريد و از تعداد نشانه هاي گره‌‌‌ فرستنده بر روي اين لينک يکي کاسته شده و به نشانه‌هاي گره‌‌‌ گيرنده يکي افزوده مي‌شود. پس از آن تمام لينک‌هاي همسايه که با اين لينک تداخل دارند، مشخص مي‌شوند و برچسب ” تداخل[a246] ” مي‌خورند. سپس از ميان ساير لينکها، با توجه به سياست بکار گرفته شده لينک موجود ديگري براي زمانبندي در اين پنجره زماني انتخاب مي شود. اين کار تا زماني ادامه مي‌يابد که ديگر نتوان لينکي را در اين پنجره زماني با وضعيت موجود انتخاب کرد. پس از آن، زمانبندي لينکها در پنجره زمانبندي بعدي ادامه مي‌يابد تا زمانيکه نشانه‌هاي تمام SS ها صفر شود. در اين الگوريتم کاهش تناسبی[a247] طول ارسال، ديده نشده است.
الگوريتم LA[20]
شرایط: زمان بندی متمرکز، مش مبتنی بر TDMA، آنتن همه جهته، توپولوژی درخت
ورودی: مسیریابی مشخص، رادیو تک کاناله، مدل تداخل اولیه و ثانویه ، نرخ ارسال مشخص گره‌‌‌ها
هدف:رعایت عدالت در گره‌‌‌ها، خدمات سرویس درنظر گرفته نشده است.
تکنیک: اکتشافی
این الگوریتم از دو فاز تشکيل شده است. به خاطر فاز دوم اين الگوريتم، در اين پايان نامه از LA158 براي ناميدن آن استفاده شده است. در فاز اول که توسط BS اجراء مي شود، ترتيب ارسال گره‌‌‌ها(رتبه‌بندي) مشخص مي‌گردد. BS ترتيب ارسال و پهناي باند تخصيص داده شده به تمامي گره‌‌‌ها را در سطح شبکه پخش مي‌کند. در اين فاز از معياري به نام شاخص رضايت159 استفاده مي‌شود. اين پارامتر ميزان توجهي [a248]به درخواست‌هاي هر گره‌‌‌ در پنجره زماني مشخصي شده را نشان مي‌دهد. در ابتداي هر تکرار، الگوريتم مقدار شاخص رضايت متناظر با هر لينک را با توجه به زمانبندي تعيين مي‌کند. شاخص [a249]رضايت رابطه مستقيم با نسبت نرخ متوسط تخصيصي به گره‌‌‌ i به نرخ عادلانه آن دارد. نرخ عادلانه متناظر با مقدار وزن هر گره‌‌‌ مي باشد. BS اين پارامتر را براي تمام گره‌‌‌ها محاسبه مي‌نمايد. هنگاميکه که BS درخواست پهناي باند را از گره‌‌‌ها دريافت مي‌کند، اين درخواستها را با توجه به ترتيب صعودي شاخص رضايت گره‌‌‌ها، مرتب مي‌کند که این[a250] ترتيب ارسال گره‌‌‌ها را تعيين مي‌‌نماید[a251]. در فاز دوم الگوريتم، گره‌‌‌ها با توجه به درخت مسيريابي شبکه، ترتيب ارسال حاصل از فاز ۱ و پهناي باند مورد نياز ساير گره‌‌‌هاي شبکه، الگوريتم زمانبندي را اجراء مي‌کنند تا با زمانبندي يک يا چندين گره‌‌‌ در هر پنجره زماني، دسترسي همزمان به کانال فراهم آورده شود.
الگوریتم مقیاس بلوک کردن160 [44]
شرایط: زمان بندی متمرکز، مش مبتنی بر TDMA، آنتن همه جهته، توپولوژی درخت
ورودی: مسیریابی مشخص، رادیو تک کاناله، مدل تداخل اولیه و ثانویه ، نرخ ارسال مشخص گره‌‌‌ها
هدف: محاسبه مسیر امکان پذیر، خدمات سرویس درنظر گرفته نشده است.
تکنیک: اکتشافی
این روش از پارامتری به عنوان مقیاس بلوک کردن در زمان‌بندی استفاده می‌کند. همانطور که در شکل (4-12) نشان داده شده است مقایس بلوک کردن یک مسیر، مجموع مقادیر گره‌‌‌هایی است که در ارسال یک گره‌‌‌ تداخل ایجاد می‌کند. این بدان معناست[a252] که مقیاس بلوک کردن مشخص می‌کند [a253]که در [a254]صورت پذیرش[a255] در خواست گره‌‌‌، چند ارسال دیگر رد یا بلوک می شوند. بنابراین از تمام مسیرهای ممکن از گره به ریشه، مسیری که منجر به حداقل تداخل هست انتخاب می‌شود. سپس لینک‌ها روی مسیر به شیوه‌ی تکراری براساس بالاترین تقاضای ترافیکی تخصیص نیافته زمان بندی می‌شود. زمان‌بندی لینک ها[a256]، که در شیار مشابه تداخل دارند، تا گام بعد به تأخیر می‌افتد. در عین حال برای به حداکثر رساندن ارسال‌های همزمان، لینک های غیر تداخلی در همان شیار[a257] زمانی زمان بندی می‌شوند.

شکل ‏412-مثالی برای نشان دادن مفهوم مقیاس بلوک کردن b(path)=2+4+3+4=13[44]
الگوریتم زمان‌بندی برپایه تئوری صف [45]
شرایط: زمان بندی متمرکز، مش مبتنی بر TDMA، آنتن همه جهته، توپولوژی درخت
ورودی: مسیریابی مشخص، رادیو تک کاناله، بدون درنظرگرفتن تداخل ثانویه، نرخ ارسال مشخص گره‌‌‌ها
هدف: تعیین مسیریابی، محاسبه مسیر امکان پذیر، در نظر گرفتن خدمات سرویس(پهنای باند)