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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

آماده سازی مسئله[ویرایش]

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

\sum_{i=1}^M n_i = N

فرض می کنیم که زمان سرویس دهی برای یک مشتری در iمین جایگاه توسط توزیع نمایی با متغیر تصادفی با میانگین ۱/μi است و بعد از اتمام سرویس دهی در iمین جایگاه با احتمال pij به جایگاه 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}

که می توان Xi را از معادله ی زیر بدست آورد:

\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{align}
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{align}

همچنین

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 محاسبه شوند.

پیاده سازی[ویرایش]

فرض می کنیم که Xm با حل معادلات مرتبط بدست آمده است و به عنوان ورودی برای پیاده سازی ما موجود است. هرچند 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است. [۱]

منابع[ویرایش]

  1. ۱٫۰ ۱٫۱ ۱٫۲ Buzen, Jeffrey (September 1973). "Computational algorithms for closed queueing networks with exponential servers". Communications of the ACM 16 (9): 527. DOI:10.1145/362342.362345.  [۱]

پیوند به بیرون[ویرایش]