چکیده: امروزه با گسترش روزافزون فضای اینترنت و افزایش تعداد کاربران این حوزه و مطرح شدن مواردی مانند اینترنت چیزها و محاسبات ابری، شاخه جدید و نوپایی در علم کامپیوتر به اسم محاسبات لبه اهمیت زیادی پیدا کرده است. تکنولوژی های لبه شبکه سعی دارند که منابع محاسباتی را به کاربران نزدیکتر نمایند، با این هدف که نزدیکتر کردن سرورهای محاسباتی به کاربران و کلاینتها، منجر به تسریع در فرایند محاسبات گردد. به علت افزوده شدن بر حجم داده‌های اینترنتی کاربران و کلاینتها، محدودیتهای پهنای باند، محدودیتهای منابع در سرورهای ابری، مساله مهم بهینگی انرژی و فاصله طولانی سروهای ابر نسبت به کاربران و کلاینتها و در شبکه‌های کامپیوتری، رایانش ابری با چالشهایی روبرو شده است. محاسبات در لبه، قدمی با هدف کمک به این مساله می‌باشد. کاربران و کلاینتهایی که در چنین شبکه‌هایی هستند می‌توانند بخشی از محاسبات خود را برای اجرا به سرورهای لبه یا ابر واگذار نمایند که به این فرایند آفلودینگ اتلاق میشود. شبکه‌ها و سیستم‌های زیادی اعم از شبکه‌های مربوط به اینترنت چیزها، شبکه‌های سلولی نسل پنجم، شبکه‌های توزیع محتوا، اتوموبیل‌های خودران و وسایل نقلیه هوشمند، شهرهای هوشمند، شبکه‌های انرژی هوشمند، اپلیکیشنهای واقعیت افزود و واقعیت مجازی، سیستم‌های ماینتورینگ سلامتی و پزشکی از راه دور ، سیستم‌های استریم و پردازش ویدیو، سیستم‌های مدیریت ترافیک هوشمند و بسیاری از سیستم‌های دیگر از فناوری محاسبات لبه استفاده مستقیم میکنند. از این رو در سالهای اخیر مبحث محاسبات لبه در مرکز توجه قرار گرفته است.یکی از مباحث پایه‌ای در وادی محاسبات لبه، مساله مدیریت بهینه منابع در محاسبات لبه می‌باشد که یکی از مهم‌ترین چالشهای مطرح در این حوزه محسوب میشود. سیستم‌های محاسباتی که دارای سرورهای لبه شبکه و سرورهای ابری هستند، سعی دارند که تسکهای درخواستی کاربران را حدالمقدور با منابع لبه شبکه پاسخ دهند و از ارسال آنها به فضای ابری با هدف بهینگی و تسریع فرایند جلوگیری نمایند. هدف ما ارائه رویکردی مبتنی بر الگوریتم کوله‌پشتی (Knapsack) جهت مدلسازی مساله تخصیص منابع در یک شبکه شامل سرورهای لبه و سرورهای ابری و حل آن در یک زمان معقول می‌باشد. مساله کوله‌پشتی یکی از مسائل مطرح در بهینه‌سازی ترکیبیاتی است. نوع خاصی از این مساله با عنوان مساله کوله‌پشتی چندگانه (MKP) این حالت را بررسی میکند که با داشتن چندین آیتم با ارزشها و وزنهای متفاوت، و داشتن چندین کوله‌پشتی با ظرفیتهای محدود، کدام مجموعه از آیتم‌ها را به ازای هر کوله‌پشتی میتوانیم انتخاب کنیم که ارزش کلی بیشینه شود. مساله کوله‌پشتی چندگانه در دسته مسائل NP-Hard قرار دارد از این رو حل کردن آن در یک زمان معقول و با منابع محدود دارای پیچیدگی‌های خاصی می‌باشد. ما در کار خود با فرض این که سرورهای موجود در لبه و همچنین در سرورهای ابر کوله‌پشتی های ما هستند و تسکهای کاربر که قرار است روی منابع موجود در لبه یا ابر آفلود شوند آیتم‌های ما هستند و هر کدام وزن و ارزش مختص به خود را دارند، مساله را مدلسازی کرده و حل می‌نمائیم. برای این منظور ما یک الگوریتم نهایی پیشنهاد می‌دهیم که میتواند مساله MKP را در سناریوی مذکور در زمانی کمینه و با حداقل منابع حل نماید. الگوریتم پیشنهادی ما از دو بخش تشکیل شده است که بخش اول در صورتی که تعداد منابع و تسکها زیاد نباشد، پاسخ دقیق مساله را محاسبه میکند و بخش دوم در صورتی که تعداد منابع و تسکها بسیار زیاد شود بطوریکه محاسبه آن در زمانی معقول غیرممکن باشد، با یک راه‌حل حریصانه پاسخی تقریبی برای مساله پیدا میکند. ما پس از بیان و مدلسازی مساله و ارائه الگوریتم پیشنهادی خود بصورت تئوری، الگوریتم خود را در عمل با شبیه‌ساز ECHOES که شبیه‌سازی طراحی شده برای تست کردن روشهای بهینه‌سازی در محیطهای متشکل از ابر و لبه می‌باشد، آزمایش میکنیم که نتایج گزارشمان در عمل به سناریوهای دنیای واقعی نزدیکتر شود.