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

الگوریتم بوزن در تئوری صف با توجه به تئوری احتمال در ریاضی، الگوریتمی برای برای محاسبهٔ ثابت طبیعی ((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,\ldots ,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{aligned}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{aligned}}$

همچنین

$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