1- مقدمه[1]

شبکه‌های لوزی ازجمله شبکه‌های متعارفی هستند که برای بررسی جنبه‌‌های همکاری[i] در شبکه‌های بی‌سیم به کار می‌روند. این‌ شبکه‌ها دو پرش[ii] را شامل می‌شوند که در پرش اول، گره منبع[iii] اطلاعات را ازطریق یک کانال پخشی[iv] به  رله ارسال می‌کند و در پرش دوم، رله‌ها داده‌های دریافتی را ازطریق یک کانال دسترسی چندگانه[v] به گره مقصد[vi] ارسال می‌کنند ]۱،۲[. درواقع، رله‌ها در شبکه سعی می‌کنند به‌صورت همکارانه، اطلاعات را از گره منبع به گره مقصد با بیشترین نرخ ممکن ارسال کنند.

معاوضۀ تسهیم و چندگانگی[vii] (DMT) به‌عنوان یک معیار برای مقایسۀ روش‌های مختلف مخابره در شبکه‌های رله، زمانی استفاده می‌شود که نسبت سیگنال به نویز[viii] (SNR) در شبکه بالا باشد. معاوضۀ تسهیم و چندگانگی به نوعی معاوضۀ بین نرخ ارسال و احتمال خطا در مخابره را برای کانال‌های محوشدگی[ix] نشان می‌دهد ]۳[. در معاوضۀ تسهیم و چندگانگی، دو مفهوم بهرۀ چندگانگی[x] و بهرۀ تسهیم[xi] استفاده می‌شوند. بهرۀ چندگانگی به نوعی روند کاهش احتمال خطا با افزایش سیگنال به نویز در مخابره را نشان می‌دهد و بهرۀ تسهیم روند افزایش نرخ مخابره با افزایش سیگنال به نویز در شبکه را مشخص می‌کند. فرض شود یک خانواده کد  برای مخابره در کانال بی‌سیم استفاده می‌شود. اگر نرخ ارسال خانواده کد با  نمایش داده شود و احتمال خطای مخابره با  نشان داده شود، آنگاه بهرۀ تسهیم که با  نمایش داده می‌شود، برای خانوادۀ کد با رابطۀ زیر تعریف می‌شود:

و بهرۀ چندگانگی که با نمایش داده می‌شود، با رابطۀ زیر تعریف می‌شود:

ماکزیمم بهرۀ چندگانگی حصول‌شده روی تمام خانواده‌های کدهای موجود برای یک بهرۀ تسهیم خاص معاوضۀ بهرۀ تسهیم و چندگانگی برای شبکه در آن بهرۀ تسهیم، تعریف و با  نمایش داده می‌شود ]۴[.

در شبکه‌های لوزی، رله‌ها عموماً در دو حالت مختلف نیمه دوسویه[xii] و دوسویه[xiii] عمل می‌کنند. اگر رله به‌طور همزمان در یک بازۀ فرکانسی و در یک زمان اطلاعات را ارسال و دریافت کند، رله به‌صورت دوسویه کار می‌کند. در روش انتقال داده‌ها به‌صورت دوسویه نشان داده شده است که ارسال به کمک روش کوانتیزه – نگاشت - ارسال[xiv] (QMF) می‌تواند به معاوضۀ تسهیم و چندگانگی بهینه در شبکه برسد ]۲[. در ]۵[ اوستی‌مهر و همکاران نشان داده‌اند در یک شبکه با توپولوژی دلخواه، روش ارسال کوانتیزه –نگاشت - ارسال به یک تقریب جمعی[xv] از ظرفیت کانال می‌رسد که این تقریب مستقل از توان ارسال و بهره‌های کانال‌های شبکه است و تنها تابع تعداد رله‌ها در شبکه است؛ بنابراین در سیگنال به نویز‌های بالا تقریباً ظرفیت کانال با ظرفیت ارسال به کمک روش کوانتیزه – نگاشت -ارسال یکی است و معاوضۀ تسهیم و چندگانگی کانال به کمک محاسبۀ معاوضۀ تسهیم و چندگانگی روش کوانتیزه –نگاشت - ارسال به دست می‌آید ]۳[.

برای اجتناب از پدیدۀ خود تداخلی[xvi]، در عمل در بسیاری از شبکه‌های رله، از رله‌های نیمه دوسویه برای ارسال اطلاعات استفاده می‌شود. در روش ارسال نیمه دوسویه، رله اطلاعت خود را با مالتی‌پلکس‌کردن در زمان یا فرکانس دریافت و ارسال می‌کند. در حالت مالتی‌پلکس در فرکانس، رله داده‌های خود را در یک باند فرکانسی دریافت و در باند فرکانسی متفاوتی ارسال می‌کند و در مالتی‌پلکس در زمان رله اطلاعات خود را در یک بازۀ زمانی خاص، ارسال و در بازۀ زمانی دیگری دریافت می‌کند.

در ارسال نیمه دوسویه انتظار می‌رود معاوضۀ تسهیم و چندگانگی، نسبت به ارسال دوسویه کاهش یابد؛ زیرا در ارسال نیمه دوسویه از تمام ظرفیت کانال برای ارسال استفاده نشده است. یک سؤال اساسی آن است که استفاده از ارسال نیمه دوسویه چه مقدار باعث کاهش در مقدار معاوضۀ تسهیم و چندگانگی نسبت به حالت ارسال دوسویه می‌شود. برای جواب دادن به این سؤال اساسی نیاز است معاوضۀ تسهیم و چندگانگی در حالت ارسال دوسویه برای شبکه‌های لوزی با  رله به دست بیاید. سپس این مقدار با معاوضۀ تسهیم و چندگانگی با ارسال نیمه دوسویه مقایسه شود. برای محاسبۀ معاوضۀ تسهیم و چندگانگی شبکۀ لوزی با  رله‌ دوسویه به حل  مسئلۀ بهینه‌سازی نیاز است و به‌خودی‌خود مسئلۀ ساده‌ای نیست. در این مقاله نشان داده شده است در شرایط خاص، محاسبۀ معاوضۀ تسهیم و چندگانگی در شبکۀ لوزی را می‌توان به یک مسئلۀ کمینه‌کردن یک تابع سابمادولار[xvii] تبدیل کرد و درنتیجه، مقدار معاوضۀ تسهیم و چندگانگی در شبکۀ لوزی با رله‌های دوسویه در زمان چندجمله‌ای[xviii] به دست می‌آید.

در این راستا، ابتدا معاوضۀ تسهیم و چندگانگی برای روش ارسال کوانتیزه – نگاشت - ارسال (روش مخابره‌ای که از لحاظ معاوضۀ تسهیم و چندگانگی بهینه است ]۳[) در یک شبکۀ لوزی در حالت کلی با  رله در حالت ارسال دوسویه به‌صورت جواب یک مسئلۀ بهینه‌سازی نوشته می‌شود. سپس نشان داده می‌شود اگر متوسط مرتبه نمایی سیگنال به نویز تمام بهره‌ها در شبکۀ لوزی بزرگ‌تر یا مساوی بهرۀ تسهیم در شبکه باشد، مسئلۀ بهینه‌سازی مطرح‌شده به کمینه‌کردن یک تابع سابمادولار تبدیل می‌شود و به کمک الگوریتم‌های چندجمله‌ای موجود برای کمینه‌کردن توابع سابمادولار، مقدار معاوضۀ تسهیم و چندگانگی در زمان چندجمله‌ای محاسبه می‌شود.

ادامۀ مقاله به‌صورت زیر سازمان داده شده است. در بخش دوم، مدل مخابراتی به‌کاررفته برای شبکۀ لوزی ارائه شده است. نتیجۀ اصلی مقاله (که همان محاسبه معاوضۀ تسهیم و چندگانگی است)، در بخش سوم آمده است. در فصل چهارم، نتایج جمع‌بندی شده‌اند.

در این مقاله تمام ها بر مبنای دو در نظر گرفته شده‌اند. یک بردار  با  نمایش داده می‌شود. برای مجموعه‌های  و  منظور از  متمم مجموعه  است و مجموعۀ  همان  است. مجموعۀ  با  نمایش داده می‌شود. منظور از  بردار با  یک و  بردار با  صفر است. مقدار  همان  است.

2- مدل مخابراتی کانال لوزی

مدل شبکه‌ای در نظر گرفته شده در این مقاله، یک شبکۀ لوزی با  رله است و فرض می‌شود رله‌ها با روش ارسال دوسویه اطلاعات را دریافت و ارسال می‌کنند.
شکل (۱) نشان‌دهندۀ مدل شبکه است که یک گره منبع (S) را شامل می‌شود که پیام مد نظر را به گره مقصد (D) با همکاری  گره رله  ارسال می‌کند. مجموعه رله‌ها با  نمایش داده می‌شود. در این شبکه فرض می‌شود مسیر مستقیمی بین گره منبع و گره مقصد وجود ندارد.

تمام گره‌ها در این شبکه مجهز به یک آنتن برای ارسال و دریافت‌اند و کانال مخابراتی در نظر گرفته شده کانال i.i.d. نیمه - ایستا با محوشدگی تخت[xix] است. در این کانال بهره‌های کانال از گره منبع به رله  برابر با  و از رله  به گره مقصد برابر با  فرض می‌شوند که در اینجا  و  متغیرهای تصادفی i.i.d. با توزیع متقارن دایروی مختلط گوسی[xx] با میانگین صفر و واریانس یک هستند و ثابت‌های  و  مقادیر حقیقی مثبت هستند و بیان‌کنندۀ مرتبه نمایی متوسط سیگنال به نویز از منبع به رله ام و از رله ام به مقصدند.

شکل (1): شبکۀ لوزی با  رله.

در این مدل کانال، فرض می‌شود بهرۀ کانال‌ها در طول ارسال یک کلمه‌کد ثابت باقی می‌ماند و بهرۀ کانال‌ها از یک کلمه‌کد به کلمه‌کد دیگر طبق توزیع معرفی‌شده به‌صورت مستقل تغییر می‌کنند. همچنین در این مدل فرض می‌شود طول کلمه‌کدها به اندازۀ کافی بلندند؛ به‌گونه‌ای‌که خطا در ارسال تنها زمانی رخ می‌دهد که کانال در حالت قطع[xxi] قرار داشته باشد ]۳[.

در این مدل مخابراتی، فرض می‌شود گره منبع از بهرۀ کانال‌ها با خبر نیست؛ ولی هر رله از بهرۀ کانال منبع به خود رله اطلاع دارد و گره مقصد به کمک کانال‌های مخابراتی شبکه از بهرۀ تمام کانال‌های مخابراتی در شبکه مطلع است. نویز کانال‌ها در رله‌ها و گره مقصد با نویز متقارن دایروی مختلط گوسی سفید جمع‌شونده با میانگین صفر و واریانس یک مدل می‌شود که از یکدیگر مستقل‌اند.

در این مدل  و  به‌ترتیب بیان‌کنندۀ متوسط سیگنال به نویز از گره منبع به رله  و از رله  به گره مقصدند. مرتبه نمایی سیگنال به نویز لحظه‌ای مسیرها به‌صورت زیر تعریف می‌شوند:

در یک شبکۀ لوزی که رله‌ها به‌صورت دوسویه کار می‌کنند، مدل مخابره به‌صورت زیر در نظر گرفته می‌شود:

که  سیگنال دریافتی رله ام،  سیگنال دریافتی در گره مقصد،  سیگنال ارسالی از گره منبع،  سیگنال ارسالی از رله ام،  نویز سفید گوسی جمع‌شونده در رله ام و  نویز سفید گوسی جمع‌شونده در گره مقصد برای  هستند.

3- نتایج اصلی

نتیجۀ اصلی این مقاله به‌طور خلاصه به شرح زیر است. زمانی که مرتبه نمایی بهرۀ کانال‌ها بزرگ‌تر یا مساوی بهرۀ تسهیم باشند ()، معاوضۀ تسهیم و چندگانگی شبکۀ لوزی با  رلۀ دوسویه با کمینه‌کردن یک تابع مجموعه‌ای سابمادولار محاسبه می‌شود که روی تمام برش‌های شبکه تعریف شده است. به سبب اینکه کمینه‌کردن یک تابع سابمادولار در زمان چندجمله امکان‌پذیر است، درنتیجه، محاسبۀ معاوضۀ تسهیم و چندگانگی در زمان چندجمله‌ای برای حالت  امکان‌پذیر است.

برای اثبات نتیجۀ اصلی، ابتدا نشان داده شده است معاوضۀ تسهیم و چندگانگی شبکه با کمینه‌کردن یک تابع آورده‌شده در رابطه (۹) روی تمام برش‌های شبکه برابر است. سپس در قضیه ۱ نشان داده شده تابع معرفی‌شده در (۹) زمانی که  یک تابع سابمادولار است و درنتیجه، محاسبۀ مقدار کمینه آن در زمان چندجلمه‌ای امکان‌پذیر است ]۹[.

برای یک شبکۀ لوزی با  رله دوسویه، در ]۵[ نشان داده شده است ظرفیت شبکۀ  در محدودۀ

قرار دارد که  یک عدد ثابت مستقل از توان ارسالی در شبکه و تنها تابع تعداد رله‌ها در شبکه است و مقدار  از رابطه (۶) محاسبه می‌شود.

که  نشان‌دهندۀ برش‌های شبکه است.

رخداد قطع شبکه، زمانی پیش می‌آید که نرخ ارسال  از ظرفیت شبکه  بیشتر باشد (). به دلیل اینکه مقدار  به اندازۀ یک ثابت مستقل از  از ظرفیت کانال فاصله دارد، در رژیم‌هایی که SNR به سمت بی‌نهایت میل می‌کند، واقعۀ قطع شبکه با  معادل است. همچنین زمانی که SNR یا  به سمت بی‌نهایت میل می‌کند، در رابطه (۶) با توجه به رابطه (۳) می‌توانیم بنویسیم:

و به همین صورت

و خواهیم داشت

بنابراین واقعۀ قطع در حالت  با نامساوی (۷) نمایش داده می‌شود:

که ها و ها در رابطه (۳) تعریف شده‌اند و . در رابطه (۸)، که در بالای صفحه بعد آمده است، زنجیره‌ای از نامساوی‌ها وجود دارد و بر این واقعیت دلالت می‌کند که برای محاسبۀ  به حل یک مسئلۀ بهینه‌سازی نیاز است. در رابطه (۸) مساوی (i) با در نظر گرفتن معادل رخداد قطع بیان شده که در رابطه (۷) آمده  است. در مساوی (ii) چگالی احتمال‌ها برای توابع احتمال  و  به کار برده می‌شود و ثابت‌ها و جملاتی که به  وابسته نیستند، حذف شده‌اند ]۳[. درنهایت، در (iii) با به‌کارگیری روش لاپلاس مشابه با ]۴[ مقدار انتگرال در حالت حدی  محاسبه شده است؛ بنابراین معاوضۀ تسهیم و چندگانگی یک شبکۀ لوزی

با  رلۀ دوسویه از حل مسئلۀ بهینه‌سازی زیر به دست می‌آید:

که تابع  روی برش‌های شبکه با بهینه‌سازی زیر تعریف می‌شود:

تعریف ۱: اگر  یک مجموعه متناهی باشد و  نشان‌دهندۀ تمام زیرمجموعه‌های باشد (مجموعه توانی )، یک تابع  یک تابع سابمادولار است. اگر برای تمام زیرمجموعه‌های  داشته باشیم ]۷[

قضیه ۱: اگر  برای تمام ، آنگاه تابع  که در (۱۰) تعریف شده، یک تابع سابمادولار بر حسب  است. به عبارت دیگر، برای هر  داریم

که  و  همانند رابطه (۱۰) هستند و برای  به‌طور مشخص داریم

و برای  داریم

اثبات: ابتدا یک کران بالا برای سمت راست نامساوی (۱۲) و یک کران پایین برای سمت چپ نامساوی به دست آورده می‌شود. سپس نشان داده می‌شود کران بالای به‌دست‌آمده کوچک‌تر از کران پایین حاصل‌شده است. برای این منظور، یک کران بالا برای مقدار مسئلۀ بهینه‌سازی (۱۳) به دست آورده می‌شود. این مسئلۀ بهینه‌سازی به‌صورت یک کمینه‌سازی برنامه‌ریزی خطی استاندارد نوشته می‌شود:

که برای به دست آوردن بهینه‌سازی (۱۳) می‌باید در (۱۵) بردار ،

،

و ماتریس  به‌صورت زیر

قرار داده می‌شود که  یک ماتریس یکه  است و منظور از  ماتریس  زیر است که از ضرب کرونیکر[xxii] ماترس یکه  و بردار  حاصل می‌شود.

 برای هر بردار  که متعلق به فضای شدنی (۱۳) باشد، داریم

می‌توان دید که برداری‌های

متعلق به فضای شدنی (۱۳) هستند و اگر آنها را در رابطه (۱۶) قرار داده شود، خواهیم داشت

به طریق مشابه، برای به دست آوردن یک کران بالا برای مقدار بهینۀ مسئلۀ (۱۴)، ابتدا به فرم برنامه‌ریزی خطی استاندارد (۱۵) نمایش داده می‌شود. برای این منظور  

و از ماتریس  به‌صورت

استفاده می‌شود. شبیه‌یافتن یک کران بالا برای (۱۳)، کران بالا برای  به‌صورت رابطه زیر به دست می‌آید:

که بردار  یک بردار در فضای شدنی بهینه‌سازی (۱۴) است. اگر در عبارت (۱۸) از مقادیر

و

که در فضای شدنی بهینه‌سازی (۱۴) هستند، استفاده شود، خواهیم داشت

با توجه به روابط (۱۷) و (۱۹) می‌توان یک کران بالا بر روی  یافت که در رابطه (۲۰) در بالای صفحه بعد داده شده است.

حال یک کران پایین برای مقدار  می‌یابیم. برای این منظور از دوگان بهینه‌سازی خطی مربوط به یافتن  استفاده می‌شود. اگر یک مسئلۀ بهینه‌سازی خطی به‌صورت (۱۵) تعریف شده باشد، دوگان آن برابر است با ]۸[

بنابراین مسئله دوگان برای یافتن مقدار  به‌صورت

نوشته می‌شود که در این رابطه ،  و ماتریس  به‌صورت

هستند. با استفاده از ویژگی دوگان، هر بردار  که در فضای شدنی (۲۱) قرار داشته باشد، یک کران پایین روی  نتیجه می‌دهد

برای حالتی که ، اگر از بردار

که در فضای شدنی (۲۱) است، در رابطه (۲۲) استفاده شود به نامساوی

خواهیم رسید. در حالتی که  یا  برابر مجموعه تهی باشند، آنگاه به سادگی می‌توان دید نامساوی (۲۳) هنوز برقرار است؛ بنابراین در حالت کلی، کران پایین (۲۳) روی مقدار  برقرار است.

برای به دست آوردن یک کران پایین برای مقدار  مشابه قبل عمل می‌شود و درنتیجه، خواهیم داشت

از روابط (۲۳) و (۲۴) می‌توان به یک کران پایین برای سمت چپ نامساوی (۱۲) رسید که در رابطه (۲۵) در بالای صفحه داده شده است. با مقایسۀ روابط (۲۰) و (۲۵) نامساوی (۱۲) ثابت می‌شود.

گزاره ۱: فرض می‌شود  یک مجموعۀ متناهی باشد و  مجموعۀ زیرمجموعه‌های  باشد. اگر  یک تابع مجموعه‌ای سابمادولار باشد و برای هر بتوانیم مقدار  را در زمان  بیابیم، آنگاه مسئلۀ کمینه‌سازی  در زمان چندجمله‌ای بر حسب  و  یافت می‌شود ]۷[.

با توجه به قضیه ۱ و گزاره ۱، نشان می‌دهیم محاسبۀ معاوضۀ تسهیم و چندگانگی در یک شبکۀ لوزی با  رله برای زمانی که بهرۀ تسهیم از  کوچک‌تر است، در زمان چندجمله‌ای بر حسب  محاسبه می‌شود. گووتچل[xxiii]، لواتس[xxiv] و شرایور[xxv] در ]۷[ یک الگوریتم زمان چندجمله‌ای قوی برای کمینه‌سازی توابع سابمادولار معرفی کرده‌اند. بسط لواتس بیان می‌کند مسئلۀ کمینه‌سازی تابع سابمادولار به‌صورت یک بهینه‌سازی محدب، مطرح و آنگاه با استفاده از روش حل بیضوی[xxvi] در زمان چندجمله‌ای حل می‌شود ]۷و۹[.

4- نتیجه‌گیری

با نشان‌دادن سابمادولاربودن تابع معاوضۀ تسهیم و چندگانگی برش‌های شبکۀ لوزی و ترکیب آن با این حقیقت که کمینه‌کردن یک تابع سابمادولار در زمان چندجمله‌ای امکان‌پذیر است، نشان داده شد محاسبۀ معاوضۀ تسهیم و چندگانگی برای یک شبکۀ لوزی با  رلۀ دوسویه در حالت کلی امکان‌پذیر است؛ البته زمانی که مقادیر مرتبه نمایی متوسط سیگنال به نویز لینک‌ها در شبکه () بزرگ‌تر یا مساوی بهره تسهیم است.

زمانی که بهرۀ تسهیم در شبکه افزایش می‌یابد باعث می‌شود بهرۀ چندگانگی کاهش یابد؛ بنابراین در بیشتر شبکه‌ها در عمل، بهرۀ تسهیم بالا استفاده نمی‌شود و درنتیجه، روش پیشنهادی برای محاسبۀ معاوضۀ تسهیم و چندگانگی در بیشتر شبکه‌های عملی کاربرد دارد.