الگوریتم بوزن

الگوریتم بوزن در تئوری صف با توجه به تئوری احتمال در ریاضی، الگوریتمی برای برای محاسبهٔ ثابت طبیعی ((normalization constant G(K) در تئوری Gordon-Newell است. این روش را ابتدا Jeffrey P. Buzen در سال ۱۹۷۳ مطرح کرد.الگو:سخ هنگامی که G محاسبه شود می‌توان توزیع احتمالی شبکه را بدست آورد. در مقابل این روش، آنالیز مقدار میانی، الگوریتمی است که می‌توان برای بدست آوردن بعضی از اندازه‌گیری‌های کارایی استفاده کرد (مانند میانگین طول صف) بدون نیاز به محاسبهٔ مستقیم ثابت طبیعی.الگو:سخ

محرک اصلی این الگوریتم کارایی است. روش محاسبهٔ مستقیم Gordon-Newell نیاز به شمارش تمامی حالت‌هایی که سیستم می‌تواند در آن باشد است که باعث combinatorial explosion می‌شود. الگوریتم بوزن از زمان اجرایی n^۲ است که منجر به عملی شدن تئوری Gordon-Newell و باز شدن کلاس بزرگی از صف‌ها برای مدل کردن دقیق می‌شود.الگو:سخ در نوشته‌های مربوط به صف‌ها، از الگوریتم بوزن گاهی به عنوان الگوریتم convolution یاد می‌کنند.

آماده‌سازی مسئله

یک صفِ شبکه‌ای بسته را در نظر بگیرید که M جایگاه سرویس دهی و N کاربر چرخشی داشته باشند. n_i را تعداد مشتریانی که در iمین جایگاه قرار دارند در نظر بگیریم؛ رابطه زیر برقرار است:الگو:سخ

$\sum _{i=1}^M{n}_i=N$الگو:سخ

فرض می کنیم که زمان سرویس دهی برای یک مشتری در iمین جایگاه توسط توزیع نمایی با متغیر تصادفی با میانگین ۱/μi است و بعد از اتمام سرویس دهی در iمین جایگاه با احتمال p_ij به جایگاه jمین جایگاه می‌رود. با استفاده از تئوری Gordon-Newell توزیع تعادل (equilibrium) مشتریان در شبکه به صورت زیر است:الگو:سخ

$P(n_1,n_2,\cdots ,n_M)=\frac{1}{G(N)}\prod _{i=1}^M{\left(X_i\right)}^{n_i}$الگو:سخ

که می‌توان X_i را از معادله ی زیر بدست آورد:الگو:سخ

${\mu }_j{X}_j=\sum _{i=1}^M{\mu }_i{X}_i{p}_{ij}\text{ for }j=1,\dots ,N.$

(G(N ثابت طبیعی است به‌طوری‌که احتمالات بالا در مجموع یک شود. الگو:سخ هدف الگوریتم بوزن این است که مقدار G را به صورت عددی محاسبه کند.

تعداد کاربران قابل انتظار

توزیع عادی Gordon-Newell که در بالا آماده است معمولاً برای موارد تئوری است؛ با این حال می‌توان اندازه‌گیری‌های کارایی مفیدی را از آن استخراج کرد. بوزن نشان می دهد که احتمال اینکه دقیقاً k کاربر در جایگاه i باشند از معادله ی زیر بدست می‌آید.الگو:سخ

$P(n_i=k)=\frac{X_i^k}{G(N)}[G(N-k)-X_{i}G(N-k-1)]$الگو:سخ

همچنین تعداد کاربرانی که انتظار می‌رود در iمین جایگاه باشند از رابطه ی زیر بدست می‌آید.الگو:سخ

$E[n_i]=\sum _{k=1}^N{X}_i^k\frac{G(N-k)}{G(N)}.$الگو:سخ

توجه داشته باشید که این معادلات نیز شامل G هستند.الگو:سخ در معادلات بالا ارزشمندی این الگوریتم هویدا می‌شود.

نتایج و مشتقات الگوریتم

الگوریتم تنها G را حساب نمی‌کند، بلکه تابع دو بعدی زیر را حساب می‌کندالگو:سخ

$g(n,m)\text{ for }n=0,1,\cdots ,N\text{ and }m=1,\cdots ,M$الگو:سخ

هنگامی که محاسبات به پایان رسید، مقادیری که مورد نظر ما است از طریق رابطه ی زیر بدست می‌آید.الگو:سخ

$G(n)=g(n,M)\text{ for }n=0,1,\cdots ,N$.الگو:سخ

تعریف g و تابع بازگشتی برای محاسبه ی آن به ترتیب زیر است:الگو:سخ

$\begin{array}{cc}g(n,m)& =\sum _{n_1+\cdots +n_m=n}\prod _{i=1}^m(X_i{)}^{n_i}\\ & =\sum _{(n_1+\cdots +n_m=n)\wedge (n_m=0)}^n\prod _{i=1}^m(X_i{)}^{n_i}+\sum _{(n_1+\cdots +n_m=n)\wedge (n_m>0)}^n\prod _{i=1}^m(X_i{)}^{n_i}\\ & =g(n,m-1)+X_{m}g(n-1,m)\end{array}$الگو:سخ

همچنینالگو:سخ

$g(n,1)=(X_1{)}^n\text{ for }n=0,1,\cdots ,N$الگو:سخ

والگو:سخ

$g(0,m)=1\text{ for }m=1,2,\cdots ,M$الگو:سخ

رابطه ی بازگشتی اجازه می دهد تمامی (G(Nها در زمان محاسباتی (O(MN محاسبه شوند.

پیاده‌سازی

فرض می کنیم که X_m با حل معادلات مرتبط بدست آمده‌است و به عنوان ورودی برای پیاده‌سازی ما موجود است. هرچند g به صورت ماتریس دوبعدی است، می‌توان آن را به صورت ستون به ستون، و شروع از چپ‌ترین ستون محاسبه کرد. برنامه از یک ستون vector، C برای نشان دادن ستونی از g که در آن است استفاده می‌کند.الگو:سخ

C[0] := 1
for n := 1 step 1 until N do
   C[n] := 0;

for m := 1 step 1 until M do
for n := 1 step 1 until N do
   C[n] := C[n] + X[m]*C[n-1];

الگو:سخ در نهایت C حاوی مقادیر مورد نظر (G(۰)، G(۱) to G(Nاست.

منابع

• Jain: The Convolution Algorithm (class handout)
• Menasce: Convolution Approach to Queueing Algorithms (presentation)

پیوند به بیرون

• example.com