Gネットワ​​ーク

待ち行列理論（確率論の一分野）において、Gネットワ​​ーク（一般化待ち行列ネットワーク、[ 1 ] [ 2 ]ゲレンベネットワーク[ 3 ]とも呼ばれる ）は、エロル・ゲレンベによって初めて導入されたGキューのオープンネットワークであり、トラフィックの再ルーティングやトラフィックの破壊などの特定の制御機能を備えた待ち行列システムのモデルとして、また ニューラルネットワークのモデルとして提案された。[ 4 ] [ 5 ] Gキューは、いくつかの種類の新しく有用な顧客を持つキューのネットワークである。

  • 正の顧客は他のキューから到着するか、ポアソン到着として外部から到着し、従来のネットワークモデルと同様に標準的なサービスとルーティングの規律に従います。
  • 負の顧客は、別のキューから到着するか、ポアソン到着として外部から到着し、空でないキューの顧客を削除（または「削除」）します。これは、ネットワークが混雑しているときにトラフィックを削除する必要があることを表し、顧客の「バッチ」の削除も含まれます[ 6 ] [ 7 ]
  • 「トリガー」は他のキューまたはネットワーク外から到着し、顧客を他のキューに移動させます。

Gネットワ​​ークの定常分布には、ジャクソンの定理に表面的には類似するが、交通流に関する非線形方程式系の解を必要とする積形解が存在する。しかし、Gネットワ​​ークの交通方程式は実際には驚くほど非線形であり、モデルは部分均衡に従わない。これは、部分均衡が積形解の必要条件であるという従来の仮定を覆すものである。Gネットワ​​ークの強力な特性は、連続関数および有界関数の普遍近似値であり、非常に一般的な入出力挙動を近似するために使用できることである。[ 8 ]

意味

m個の相互接続されたキューのネットワークは、次の条件を満たすとき Gネットワ​​ークである。

  1. 各キューには1台のサーバーがあり、そのサーバーは速度μ iでサービスを提供する。
  2. ポジティブ顧客やトリガーやリセットの外部到着はポジティブ顧客の率のポアソン過程を形成し、ネガティブ顧客を含むトリガーとリセットは率のポアソン過程を形成する。Λ私{\displaystyle \scriptstyle {\Lambda _{i}}}λ私{\displaystyle \scriptstyle {\lambda_{i}}}
  3. サービスを完了すると、顧客は確率 でキューiからキューjに正の顧客として、確率 でトリガーまたはリセットとして移動し、確率 でネットワークを離れます。p私j+{\displaystyle \scriptstyle {p_{ij}^{+}}}p私j−{\displaystyle \scriptstyle {p_{ij}^{-}}}d私{\displaystyle \scriptstyle {d_{i}}}
  4. キューに到着すると、陽性顧客は通常通り行動し、キューの長さを1増やします。
  5. キューに到着すると、ネガティブ顧客はキューの長さをランダムな数値だけ減らします（キューに少なくとも1人のポジティブな顧客がいる場合）。一方、トリガーは顧客を確率的に別のキューに移動させ、リセットはキューが空の場合にリセットが到着し、キューの状態を定常状態に戻します。すべてのトリガー、ネガティブ顧客、リセットはアクションを実行した後に消滅するため、ネットワークにおける「制御」信号となります。
  • キューを離れる通常の顧客は、次のキューにアクセスしたときにトリガーまたはリセットおよびネガティブ顧客になる可能性があることに注意してください。

このようなネットワーク内のキューはG キューと呼ばれます。

定常分布

各ノードでの利用率を定義する。

ρ私＝λ私+μ私+λ私−{\displaystyle \rho_{i}={\frac {\lambda_{i}^{+}}{\mu_{i}+\lambda_{i}^{-}}}}

満足 できる場所λ私+、λ私−{\displaystyle \scriptstyle {\lambda_{i}^{+},\lambda_{i}^{-}}}私＝1、…、メートル{\displaystyle \scriptstyle {i=1,\ldots,m}}

次に、ネットワークの状態（ノードiのキューの長さがn iである）を ( n 1 , ... , n m ) と書き、上記の式 ( 1 ) と ( 2 ) に、すべての i に対して ρ i となる唯一の非負解が存在する場合、定常確率分布 π が存在し、次のように与えられる。 （λ私+、λ私−）{\displaystyle \scriptstyle {(\lambda _{i}^{+},\lambda _{i}^{-})}}

π（n1、n2、…、nメートル）＝∏私＝1メートル（1−ρ私）ρ私n私。{\displaystyle \pi (n_{1},n_{2},\ldots ,n_{m})=\prod _{i=1}^{m}(1-\rho _{i})\rho _{i}^{n_{i}}.}

証拠

ジャクソンネットワークとは全く異なり、非線形である グローバルバランス方程式を満たすことを示すだけで十分です。このモデルは複数のクラスも許容することに注意してください。π{\displaystyle \pi }

G ネットワークは、遺伝子制御ネットワーク、パケット ネットワークでの制御とペイロードの混合、ニューラル ネットワーク、カラー画像や磁気共鳴画像などの医療画像の表現など、幅広いアプリケーションで使用されています。

応答時間の分布

応答時間とは、顧客がシステム内で過ごす時間の長さである。単一のGキューにおける応答時間分布は既知である[ 9 ]。この場合、顧客はFCFS規律を用いてレートμでサービスを受け、正の到着レートλ +と負の到着レートλ−で顧客がキューの最後尾から排除される。この状況における応答時間分布のラプラス変換は[ 9 ] [ 10 ]である。

W∗（s）＝μ（1−ρ）λ+s+λ+μ（1−ρ）−[s+λ+μ（1−ρ）]2−4λ+λ−λ−−λ+−μ（1−ρ）−s+[s+λ+μ（1−ρ）]2−4λ+λ−{\displaystyle W^{\ast }(s)={\frac {\mu (1-\rho )}{\lambda ^{+}}}{\frac {s+\lambda +\mu (1-\rho )-{\sqrt {[s+\lambda +\mu (1-\rho )]^{2}-4\lambda ^{+}\lambda ^{-}}}}{\lambda ^{-}-\lambda ^{+}-\mu (1-\rho )-s+{\sqrt {[s+\lambda +\mu (1-\rho )]^{2}-4\lambda ^{+}\lambda ^{-}}}}}}

ここで、 λ  =  λ +  +  λ −およびρ  =  λ + /( λ −  +  μ ) であり、安定性のためにρ  < 1 が必要です。

Gキューのタンデムペア（最初のノードでサービスを終えた顧客がすぐに2番目のノードに移動し、その後ネットワークを離れる）の応答時間もわかっており、より大規模なネットワークへの拡張は困難であると考えられています。[ 10 ]

参考文献

  1. ^ Gelenbe, Erol (1991). 「負の顧客と正の顧客を持つ積形待ち行列ネットワーク」(PDF) .応用確率誌. 28 (3): 656– 663. doi : 10.2307/3214499 .
  2. ^ Gelenbe, Erol (1993年9月). 「トリガーされた顧客移動を伴うGネットワ​​ーク」.応用確率ジャーナル. 30 (3): 742– 748. doi : 10.2307/3214781 . JSTOR 3214781 . 
  3. ^ Gelenbe, Erol ; Fourneau, Jean-Michel (2002). 「リセット機能付きGネットワ​​ーク」.パフォーマンス評価. 49 (1/4): 179– 191. doi : 10.1016/S0166-5316(02)00127-X .
  4. ^ Gelenbe, Erol (1989). 「負信号と正信号を持つランダムニューラルネットワークと積形式解」(PDF) . Neural Computation . 1 (4): 502– 510. doi : 10.1162/neco.1989.1.4.502 .
  5. ^ハリソン、ピーター(2009). 「時間を巻き戻す ― パフォーマンスへの影響は？」コンピュータジャーナル53 ( 6): 860– 868. CiteSeerX 10.1.1.574.9535 . doi : 10.1093/comjnl/bxp021 . 
  6. ^ Gelenbe, Erol (1993). 「シグナルとバッチ除去を備えたGネットワ​​ーク」.工学情報科学における確率. 7 (3): 335– 342. doi : 10.1017/s0269964800002953 .
  7. ^ Artalejo, JR (2000年10月). 「Gネットワ​​ーク：待ち行列ネットワークにおける作業削減のための汎用的なアプローチ」. European Journal of Operational Research . 126 (2): 233– 249. doi : 10.1016/S0377-2217(99)00476-2 .
  8. ^ Gelenbe, Erol; Mao, Zhi-Hong; Da Li, Yan (1999). 「スパイクランダムネットワークによる関数近似」. IEEE Transactions on Neural Networks . 10 (1): 3– 9. CiteSeerX 10.1.1.46.7710 . doi : 10.1109/72.737488 . PMID 18252498 .  
  9. ^ a b Harrison, PG ; Pitel, E. (1993). 「ネガティブな顧客がいるシングルサーバーキューの滞在時間」.応用確率ジャーナル. 30 (4): 943– 963. doi : 10.2307/3214524 . JSTOR 3214524 . 
  10. ^ a bハリソン、ピーター・G. (1998). Gネットにおける応答時間. 第13回国際コンピュータ情報科学シンポジウム (ISCIS 1998). pp.  9– 16. ISBN 9051994052。
「 https://en.wikipedia.org/w/index.php?title=G-network&oldid=1267299060」より取得