Gネットワ​​ーク

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

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

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

定義

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

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

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

定常分布

各ノードにおける利用

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

ここで、λi+、λi−{\displaystyle \scriptstyle {\lambda _{i}^{+},\lambda _{i}^{-}}}i＝1、…、m{\displaystyle \scriptstyle {i=1,\ldots,m}}

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

π（n1、n2、…、nm）＝∏i＝1m（1−ρi）ρini.{\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) . Journal of Applied Probability . 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」より取得