دانلود رایگان ترجمه مقاله زمان پخش در شبکه‌ های مش بی‌ سیم (اسپرینگر 2015)

مبتدی (مناسب برای درک مفهوم کلی مطلب) (ترجمه به صورت ناقص انجام شده است)

A-TxRx گراف شبکه G^ (V^ .E^ ) را به‌عنوان ورودی دریافت می‌کند و زمان f_t (e) را به هر یال eϵE اختصاص داده می‌دهد.
A-TxRx، SF را به‌عنوان خروجی تولید می‌کند. مجموعه SF شامل جفت (A.t) است، که در آن مجموعه A نشان‌دهنده یک گروه از لینک‌های فعال است که انتقال آنها در زمان t شروع می‌شود.
خطوط 1-6: در ابتدا، t با عدد صفر مشخص می‌شود. مجموعه SF خالی است. مجموعه‌های F و R نشان‌دهنده گروهی از لینک‌های پایان و لینک‌های باقی‌مانده هستند. مجموعه‌های A؛ F و R در ابتدا خالی هستند.
خط 7: تابع ConflictG() گراف عدم تداخل متناظر را از محاسبه می‌کند. به شکل 3 نگاه کنید.
خطوط 9-12: هنگامی که R یک مجموعه تهی است، تابع MaxMIS() رنگ‌آمیزی گراف G^’ را برای پیدا کردن MISs انجام می‌دهد: {eAC؛ eAB}، {eBC؛ eBA} و {eCA؛ eCB}. سپس ما MIS حاوی بیشترین لینک را انتخاب می‌کنیم. در اینجا، بدین دلیل که هر سه MISs اندازه یکسان دارند، به طور تصادفی {eAC؛ eAB} را انتخاب می‌کنیم. بنابراین، eAB و eAC به‌عنوان لینک‌های فعال انتخاب می‌شوند و در مجموعه A جای می‌گیرند، به این معنی که تمام لینک‌ها در این MIS در t=0 شروع به انتقال می‌کنند. سپس A و t مربوطه در SF=({ eAB , eAC },0) ثبت می‌شوند. گراف G^’ با از بین بردن لینک‌ها در A از G^’ به‌روز می‌شود. در این مورد، لینک‌های را eAB و eAC حذف می‌کنیم، به‌عنوان مثال، گره AB، AC و لینک‌های تلاقی آن در شکل 3. خطوط 13-19: در میان تمام زمان لینکها در A، کوتاه‌ترین را به‌عنوان tfinish در نظر می‌گیریم. لینک‌های با کوتاهترین زمان در مجموعه Fقرار دارند. دلیل آن این است که این لینک‌ها، در میان اعضای A، زودتر پایان می‌یابند. در مثال ما، tfinish=1 است، که زمان مربوط به لینک eAB است. از این رو، مجموعه F شامل eAB است. همچنین، زمان لینک‌ها در A با کم کردن tfinish از زمان f_t (e) به روز می‌شود. برای مثال، f_t (AC)=10-1=9، به این معنی است که این نقطه زمان است، لینک eAC برای یک واحد زمان انتقال داده می‌شود، اما هنوز هم به نه واحد زمان دیگر برای تکمیل انتقال نیاز دارد.
خط 20: متغیر t از t=0+1=1 نتیجه می‌شود زیرا یک واحد زمان برای لینک‌ها در A به کار برده شده است.
خطوط 21-22: مجموعه R شامل لینک‌هایی است که در A هستند، اما نه در F. پس از آن، ما F را تنظیم می‌کنیم. در این مثال، مجموعه R شامل لینک‌های eAC است زیرا انتقال به پایان رسیده نیست. در این مرحله، به‌دلیل این که R مجموعه تهی نیست، A-TxRx از خط 24 مجددا راه‌اندازی می‌شود.
خطوط 24-25: تابع Neighbor() تمام گره‌های تداخل را از لینک‌های R برمی‌گرداند. A-TxRx، G^’ را در گراف جدید G^” کپی می‌کند و N را از G^” حذف می‌کند؛ در مثال ما، این به این معنی است که eBA، eCA و eCB ازG^” حذف شده‌اند. این گام ضروری است، زیرا تضمین می‌کند که لینک‌های به‌تازگی فعال شده با لینک‌های R تداخل ندارند.
خطوط 26-28: A-TxRx تابع MaxMIS() را در G^” برای استخراج لینک‌های که می‌توانند به مجموعه A و بدون هر گونه درگیری اضافه شوند که در این مورد eBC است فراخوانی می‌کند. به‌عنوان نتیجه، SF=({e_AB.〖 e〗_AC}.0)∪({e_BC }.1) . گراف G^’ با حذف لینک‌های فعال e_BC از G^’ به‌روز می‌شوند.
خط 29: همه لینک‌هایی که در این نقطه و در این زمان در حال انتقال هستند 〖 e〗_AC و e_BC هستند.
خطوط 30-36: کوتاه‌ترین زمان لینک‌ها در A، ft(AC)=ft(BC)=9 است. متغیر tfinish با مقدار 9 تنظیم شده است. بنابراین، لینک 〖 e〗_AC و e_BC تبدیل به لینک‌های پایان در F می‌شوند. همانند قبل، زمان لینک‌ها با کم کردن tfinish از زمان ft(e) به روز می‌شود. در این مورد، 〖f_t (BC)=f〗_t (AC)=9-9=0، به این معنی است که در این نقطه در زمان، هر دو لینک انتقالشان را پایان می‌دهند.
خطوط 37-39: متغیر t به t=1+9=10 تبدیل می‌شود. مجموعه R خالی می‌شود. پس از آن مجموعه F واضح می‌شود. در این مرحله، از آنجا که هیچ لینکی در R وجود ندارد، A-TxRx از خط 10تکرار می‌شود.
خط 10: A-TxRx ، MaxMIS() را در G^’ اجرا می‌کند. MIS، {eCA؛ eBA} و {eCA؛ eCB}است. ما {eCA؛ eBA} را در مجموعه دلخواه A انتخاب می‌کنیم. فرآیند تا هنگامی که زمان t به 13 برسد ادامه می‌یابد. در این زمان، G^’ خالی می‌شود، به این معنی که همه لینک‌ها در شبکه زمان‌بندی می‌شوند. برنامه خاتمه می‌یابد و خروجی SF=({e_AB.〖 e〗_AC}.0)∪({e_BC }.1)∪({e_BA.〖 e〗_CA}.10)∪({e_CB }.13) است. پس از سه واحد زمانی دیگر، که است که زمان آخرین لینک فعال e_CB است، همه لینک‌ها در شبکه یک بار منتقل شده‌اند. بنابراین، برای شکل 2، A-TxRx یک superframe با طول 16 تولید می‌کند، کاهش طول superframe تولید شده با استفاده از 2P تقریبا 41٪ است. خط زمان زمان‌بندی در شکل 4 نشان داده شده است.

3.1 لینک‌های فرصت طلب
ما می‌توانیم ظرفیت را با اضافه کردن ” لینک‌های فرصت طلب ” بهبود بخشیم. این لینک‌ها به‌صورت عناصری تعریف می‌شوند که می‌توانند فرصت‌های انتقال اضافی بدون تداخل موجود در لینک‌ها اختصاص دهند. در مثال فوق، توجه داشته باشید که در زمان Time=[15,16]، تنها لینک eCB در حال انتقال است. هیچ لینک دیگری فعال نیست چرا که تمام لینک‌های یک بار منتقل شده‌اند. در واقع، ما همچنین می‌توانیم لینک eCA یا لینک e_AB را به‌عنوان لینک فرصت‌طلب فعال کنیم. از این رو، ما می‌توانیم e_AB را انتخاب کنیم چرا که آن زمان یک واحد و مهمتر از آن دارد و، اضافه کردن آن تغییر طول superframe نمی‌کند. از سوی دیگر، اگر ما eCA را در زمان Time=15 با زمانی برابر با پنج واحد زمان فعال کنیم، طول superframe را از 16 تا 20 گسترش خواهد داد.
برای اضافه کردن لینک‌های فرصت طلب، بهبود زیر را بر روی A-TxRx اعمال می‌کنیم. پس از ساخت یک MIS جدید متشکل از لینک‌های جدید که به superframe در خط 10 یا خط 26 از الگوریتم 1 اضافه می‌شوند، همه لینک‌های موجود در MIS جدید و همسایگان آن در نمودار اصلی برای به‌دست آوردن نموداری که قبلا شامل لینک‌های برنامه‌ریزی شده بود حذف می‌شوند. بعد، ما گراف جدید را برای به دست آوردن بزرگترین MIS رنگ‌آمیزی می‌کنیم. این MIS شامل تمام لینک‌هایی است که می‌توانند بدون ایجاد تداخل فعال شوند. سپس لینک‌هایی که طول superframe را گسترش نمی‌دهند انتخاب می‌شوند. از این رو، زمان‌بندی ایجاد شده تنها زمان‌بندی امکان‌پذیر است، اما دارای ظرفیت شبکه بالاتری است.
یک سوال که در اینجا مطرح می‌شود این است که چرا فقط لینک‌هایی که قبلا فعال شده‌اند می‌توانند لینک‌های فرصت طلب باشند. در خط 12 و28 از الگوریتم 1، لینکی که خیلی زود در MIS انتخاب شده قرار گیرد و برای انتقال انتخاب شود، از G’ حذف می‌شود. بنابراین، هنگامی که MaxMIS() را در گراف G’ و در خط 10 و 26 فراخوانی می‌کنیم، A نتیجه شده شامل لینک‌هایی است که هنوز فعال نشده‌اند. هیچ کدام از لینک‌های موجود در G’ نمی‌تواند برنامه‌ریزی شود چرا که حداقل با یک لینک در A تداخل دارد همان‌گونه که A یک MIS است. بنابراین، تنها با جستجوی لینکهایی که در G’ نیستند، به‌عنوان مثال، لینک‌هایی که حداقل یک بار فعال شده‌اند، می‌توانیم بعضی از لینک‌های دیگر با عدم تداخل را بیابیم و از آنها به‌عنوان لینک‌های فرصت طلب استفاده کنیم.

3.2 A-TxRx حریص
در A-TxRx، تابع MaxMIS() در خط 10 و 26 ابتدا رنگ‌آمیزی گراف را در گراف تداخل G’ به منظور پیدا کردن MIS انجام می‌دهد. سپس MIS با حداکثر کاردینالیتی به عنوان مجموعه‌ای از لینک‌های فعال A انتخاب می‌شود. با این حال، رنگ‌آمیزی گراف یک عملیات وقت‌گیر است. بخش 3.3 را ببینید. بنابراین، یک A-TxRx اصلاح شده را که به‌عنوان A-TxRxGreedy نشان داده شده است معرفی می‌کنیم، که در آن تابع MaxMIS() در خط 10 و 26 را با Greedy() جایگزین کرده‌ایم. تابع Greedy()، A را با تکرار از طریق تمام لینک‌ها در E که از یک و با طولانی‌ترین زمان انتقال شروع شده‌اند می‌سازد. لینک e به مجموعه A اضافه می‌شود اگر e با هر لینک حاضر در A تداخل نداشته باشد. درغیر این صورت، لینک e برای پیوستن به A انتخاب نمی‌شود.

3.3 تجزیه و تحلیل
هم اکنون ما پیچیدگی زمانی A-TxRx را برای یک گراف دلخواه G با |v| گره محاسبه می‌کنیم به‌طوری که تعدا یال‌های |E| در G کران بالایی مانند |v|(|v|-1) (گراف کامل) دارد. به‌طور خاص، نتیجه زیر را داریم.
قضیه 1: پیچیدگی زمانی A-TxRx، O(|v|5) است.
اثبات: تمام خطوط A-TxRx زمانی برابر با O(1) دارد به جزء خط 7، 8، 10، 13، 14، 24، 26، 40 و 31. در خط 7، تابع ConflictG() زمانی برابر با O(|v|2) برای تبدیل گراف اصلی G به گراف G’ نیاز دارد. دلیل آن این است که هر یال در G به‌عنوان یک راس در G’ در نظر گرفته شده است و متصل به لینک‌های مربوط به آن است. در نتیجه، تعدادراس‌ها در G’ با تعداد یال‌ها در G برابر است، که محدود به |v|(|v|-1) است. مشابه خط 8، پیچیدگی زمانی O(|v|2) است زیرا تعداد رئوس در G’ را بیان می‌کند. در خط 10 و 26، فرآیند رنگ‌آمیزی گراف انجام شده است. با توجه به [20]، الگوریتم رنگ‌آمیزی کوچکترین-آخرین گراف دارای یک پیچیدگی زمانی O(|v’|+|E’|) برای G’(|V’|,|E’|) است. برای محاسبه تعداد کل یال‌ها در G’، ما بدترین حالت را فرض می‌کنیم، به‌طوریکه G به طور کامل متصل است. برای هر لینک، eAB، 2|v|-3 لینک از گره B به گره A که در تضاد با eAB هستند. از این رو، تعدادی از یال‌ها در G’ به صورت (2|v|-3)×|v|(|v|-1) محاسبه می‌شود. در نتیجه، پیچیدگی زمانی برای خط 10 و 26، O(|v| ^2+|v|^3 )=O(〖|v|〗^3) است. برای خطوط 13، 30، 14 و 31، در بدترین حالت، هر راس v^’ ϵV^’ در G’ تنها به یک راس که نشان دهنده لینک مربوط در جهت مخالف است متصل شده و در نتیجه اندازه بزرگترین MIS، که به‌عنوان A استفاده می‌شود، با 1/2|v|(|v|-1) برابر است. به‌طور مشابه، در بدترین حالت، اندازه R برابر است با 1/2|v|(|v|-1). بنابراین، خطوط 12، 30، 14، 31 و 24 در بیشتر مواقع زمانی برابر با O(|v| ^2 ) دارند. بر اساس محاسبات فوق، A-TxRx دارای پیچیدگی زمانی O(|v| ^2 |v|^3 )=O(〖|v|〗^5) است.
قضیه 2 : A-TxRx یک زمان‌بندی برخورد رایگان تولید می‌کند.
اثبات: از ثابتهای lتناقض استفاده می‌کنیم. فرض کنید دو لینک ارسال و دریافت در زمان یکسان داریم. ب‌ه‌طور خاص، eAB و exA یا eAB و eBy در حال انتقال به طور همزمان هستند، که در آن x می‌تواند هر گرهی باشد به جز A، y می‌تواند هر گرهی باشد به جز B. بنابراین دو مورد داریم:
مورد 1: این دو لینک تداخل شروع به انتقال از نقطه یکسانی در زمان‌ می‌کنند. در این مورد، دو لینک فعال در خط 10 هستند. پس از فرآیند رنگ‌آمیزی گراف، تنها لینک‌ها در یک مجموعه مستقل فعال می‌شوند. به یاد بیاورید که در یک مجموعه مستقل از یک گراف، هیچ دو راس از گراف مجاور نیستند. این با مورد دوم در تضاد است با این که این دو لینک با همدیگر تداخل دارد.
مورد 2: یکی از این دو لینک تداخل، با exA (یا eBy) شروع می‌شود در حالی که برای انتقال از لینک دیگر، انتقال آن به پایان نرسیده است. این نشان می‌دهد که لینک به تازگی اضافه شده در خط 26 فعال شده است، که رنگ‌آمیزی گراف را برای گراف جدید G’ به کار برده است. توجه داشته باشید که در خط 25، تمام لینک‌های باقی مانده از جمله eAB و لینک‌های همسایه آن از G’ حذف می‌شوند. بنابراین، هر لینک که با لینک eAB تداخل دارد در گراف G’ وجود ندارد. به عنوان نتیجه، غیر ممکن است A-TxRx برای استخراج یک زمان‌بندی با تداخل به کار گرفته شود.
قضیه 3: A-TxRx یک زمان‌بندی لینک تولید می‌کندکه بیشتر از 〖δ(G)=l〗_t^A+l_t^B برای یک توپولوژی گراف دوبخشی نیست.
اثبات: فرض کنید v1 و v2 دو زیرمجموعه از یک گراف دوبخشی باشند به صورتی که گره‌ها در v1(v2) تنها لینک به گره‌های در V v2(v1) دارند. خط 7 از A-TxRx گراف تداخل G’(v’,E’) را از گراف G تولید می‌کند. توجه داشته باشید که می‌توانیم دو MIS تولید کنیم برای مثال، A و B، از G’؛ A (B) شامل لینک‌های ناشی از گره‌ها در v1(v2) است. فرض کنید i1(i2) یک لینک ناشی از v1(v2) با طولانی‌ترین زمان باشد، به‌عنوان مثال، f_t (i_1 )=l_t^A ؛ به‌طور مشابه، f_t (i_2 )=l_t^B. توجه داشته باشید که می‌تواند تعداد متعددی لینک i_1 و i_2 می‌تواند وجود داشته باشد. سه مورد ممکن را در نظر بگیرید: (1) تمام لینک‌ها در (B) A زمان یکسانی دارند ، به‌عنوان مثال، یک لینک در A (B) زمان l_t^A (l_t^B) را دارد، (2) لینکi_1 و i_2 با یکدیگر تداخل دارند و (3) لینک i_1 و i_2 با یکدیگر تداخل ندارند.
برای مورد (1)، A-TxRx یک زمان‌بندی تولید می‌کند که در آن لینک‌های موجود در B بعد از همه لینک‌های B فعال می‌شوند و در نتیجه 〖δ(G)=l〗_t^A+l_t^B. به‌طور خاص، خط 10-12، MIS را تولید می‌کند و همه لینک‌ها را در شروع A در زمان t =0 برای l_t^A واحد زمان برنامه‌ریزی می‌کند. خط 14-19 F=A را تولید می‌کند چون تمام لینک‌ها زمان پایان l_t^A دارند و در نتیجه خط 20-21 ، t=〖 l〗_t^A را به‌دست می‌آورد. بنابراین، در تکرار دوم از حلقه در خط 8، خط 10-12، MIS A=B را تولید می‌کند و همه لینک‌ها را با شروع از B در زمان t=〖 l〗_t^A برنامه‌ریزی می‌کند. مشابه با A، این تکرار F=B را تولید می‌کند؛ بنابراین الگوریتم با یک زمان‌بندی که از t=0 شروع می‌شود کامل می‌شود. بنابراین زمان‌بندی در زمان l_t^A+l_t^B کامل می‌شود، برای این مورد، A-TxRx زمان‌بندی با طول فریم 〖δ(G)=l〗_t^A+l_t^B تولید می‌کند.
برای مورد دوم، برخی از لینک‌های دیگر از i_2 را می‌توان در در زمان یکسانی با لینک‌ها در A فعال کرد. با این حال، از آنجا که i_2 و i_1 لینک‌های تداخل هستند، i_2 می‌تواند تنها پس از اتمام i_1 فعال شود؛ i_2 زمان خود را در زمان l_t^A+l_t^B کامل می‌کند، به این معنی که طول superframe برای این مورد 〖δ(G)=l〗_t^A+l_t^B است زیرا تمام لینک‌ها در (B)A بعد از زمان l_t^A (l_t^A+l_t^B) کامل نمی‌شوند. به طور خاص، خط 10-12، MIS A=A و زمان‌بندی تمام لینک‌ها را در زمان صفر تولید می‌کند. از آنجا که R شامل حداقل تولید است، و G^’≠∅ در تکرار دوم، خطوط 24-27 لینک‌های موجود در B را که با لینک‌های باقی مانده در R تداخل ندارند لینک می‌کند. برای خط 30، دو حالت ممکن را درنظر می‌گیریم: (1.1) حداقل یک لینک اضافی از B دارای زمان طولانی‌تری از باقی‌مانده زمان i_1 است؛ (2.2) باقی‌مانده زمان i_1 طولانی‌ترین لینک در میان MIS جدید است. برای مورد (1.1)، A-TxRx خط 23 را تکرار می‌کند و در نهایت یک MIS که فقط شامل لینک‌ها در B است، از جمله i_2 تولید می‌کند. در این مرحله، خط 24-26، N=∅ را تولید می‌کند زیرا گره‌ها در R=G^’⊆v_2 و گره‌های همسایه هستند. در نتیجه خط 26 لینک بیشتری به لینک SF اضافه نمی‌کند، لینک‌هایی که در زمان l_t^A شروع می‌شوند در زمان l_t^B تکمیل می‌شوند، به این معنی که طول superframe ، 〖δ(G)=l〗_t^A+l_t^Bاست. برای مورد(2.2)، A-TxRx تکرار خود را از خط 24 تا رسیدن به مورد (1.1) ادامه خواهد داد. در هر صورت، در زمان l_t^A؛ R در نهایت تنها حاوی لینک‌های B خواهد شد و همان‌گونه که قبلا شرح داده شد، لینک‌ها در زمانی بیش از l_t^B فعال نخواهند شد.