(57)【特許請求の範囲】
【請求項１】
ルータとゲートウェイとを備えるネットワークを対象としたネットワーク最適化方法であって、
前記ネットワークのトラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出する第１のステップと、
前記送信成功確率からルータ内のバッファ状況を算出する第２のステップと、
前記バッファ状況に基づいて、ルータの送信確率を算出する第３のステップと、
前記ルータの送信確率に基づいて、ルータとゲートウェイとの間の送受信結果として、送信待機確率、送信成功確率、及び衝突発生確率を算出する第４のステップと、
前記送受信結果に基づいて、前記ネットワークにおける最適なルータ数を決定する第５のステップと
を有するネットワーク最適化方法。
【請求項２】
前記第５のステップでは、前記送受信結果に基づいてルータ数毎の伝送可能容量を算出し、前記ルータ数毎の伝送可能容量が最大となるルータ数を前記最適なルータ数として決定する、請求項１に記載のネットワーク最適化方法。
【請求項３】
前記ネットワークのトラヒック情報を基に、全てのクライアントのトラヒック送信に要する単位時間当たりの送信占有時間を算出する第６のステップと、
前記単位時間当たりの送信占有時間とゲートウェイの収容可能容量とに基づいて、前記収容可能容量の総和が前記単位時間当たりの送信占有時間を下回らない最小のゲートウェイ数を最適なゲートウェイ数として決定する第７のステップと
をさらに有する請求項１又は２に記載のネットワーク最適化方法。
【請求項４】
ゲートウェイとルータとの間のスループットを測定し、前記スループットと閾値とを比較して前記最適なゲートウェイ数を変更する第８のステップをさらに有する請求項３に記載のネットワーク最適化方法。
【請求項５】
ルータとゲートウェイとを備えるネットワークを対象としたネットワーク最適化方法であって、
前記ネットワークのトラヒック情報を基に、全てのクライアントのトラヒック送信に要する単位時間当たりの送信占有時間を算出する第１のステップと、
前記単位時間当たりの送信占有時間とゲートウェイの収容可能容量とに基づいて、前記収容可能容量の総和が前記単位時間当たりの送信占有時間を下回らない最小のゲートウェイ数を最適なゲートウェイ数として決定する第２のステップと、
前記最適なゲートウェイ数に基づいて分割されたサブエリアに毎に、最適なルータ数を決定するステップを実行する第３のステップと、
ゲートウェイとルータとの間のスループットを測定し、前記スループットと閾値とを比較して前記最適なゲートウェイ数を変更する第４のステップと、
変更後の最適なゲートウェイ数に基づいて分割されたサブエリアに毎に、前記最適なルータ数を決定するステップを再実行する第５のステップと
を有し、
前記最適なルータ数を決定するステップは、
前記ネットワークのトラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出する第６のステップと、
前記送信成功確率からルータ内のバッファ状況を算出する第７のステップと、
前記バッファ状況に基づいて、ルータの送信確率を算出する第８のステップと、
前記ルータの送信確率に基づいて、ルータとゲートウェイとの間の送受信結果として、送信待機確率、送信成功確率、及び衝突発生確率を算出する第９のステップと、
前記送受信結果に基づいてルータ数毎の伝送可能容量を算出し、前記ルータ数毎の伝送可能容量が最大となるルータ数を前記最適なルータ数として決定する第１０のステップと
を有するネットワーク最適化方法。
【請求項６】
ルータとゲートウェイとを備えるネットワークを対象としたネットワーク最適化装置であって、
前記ネットワークのトラヒック情報を収集するトラヒック情報収集部と、
前記トラヒック情報に基づいて、ルータ数毎の伝送可能容量を算出する無線区間解析部と、
前記ルータ数毎の伝送可能容量が最大となるルータ数を最適なルータ数として決定するルータ数算出部と
を備え、
前記無線区間解析部は、前記トラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出し、前記送信成功確率からルータ内のバッファ状況を算出し、前記バッファ状況に基づいて、ルータの送信確率を算出し、前記ルータの送信確率に基づいて、ルータとゲートウェイとの間の送受信結果として、送信待機確率、送信成功確率、及び衝突発生確率を算出し、前記送受信結果に基づいて前記ルータ数毎の伝送可能容量を算出する、ネットワーク最適化装置。
【請求項７】
ルータとゲートウェイとを備えるネットワークを対象としたネットワーク最適化装置であって、
前記ネットワークのトラヒック情報を収集するトラヒック情報収集部と、
前記トラヒック情報を基に、全てのクライアントのトラヒック送信に要する単位時間当たりの送信占有時間を算出し、前記単位時間当たりの送信占有時間とゲートウェイの収容可能容量とに基づいて、前記収容可能容量の総和が前記単位時間当たりの送信占有時間を下回らない最小のゲートウェイ数を最適なゲートウェイ数として決定するゲートウェイ数算出部と、
前記トラヒック情報に基づいて、ルータ数毎の伝送可能容量を算出する無線区間解析部と、
前記ルータ数毎の伝送可能容量が最大となるルータ数を最適なルータ数として決定するルータ数算出部と、
ゲートウェイとルータ間のスループットを測定するスループット監視部と、
前記ゲートウェイ数算出部によって決定された前記最適なゲートウェイ数に基づいて分割されたサブエリアに毎に、前記無線区間解析部及び前記ルータ数算出部によって前記最適なルータ数を決定し、前記スループット監視部によって測定された前記スループットと閾値とを比較して、前記最適なゲートウェイ数を変更し、変更後の最適なゲートウェイ数に基づいて分割されたサブエリアに毎に、前記無線区間解析部及び前記ルータ数算出部によって前記最適なルータ数を再決定する制御部と
を備え、
前記無線区間解析部は、前記トラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出し、前記送信成功確率からルータ内のバッファ状況を算出し、前記バッファ状況に基づいて、ルータの送信確率を算出し、前記ルータの送信確率に基づいて、ルータとゲートウェイとの間の送受信結果として、送信待機確率、送信成功確率、及び衝突発生確率を算出し、前記送受信結果に基づいて前記ルータ数毎の伝送可能容量を算出する、ネットワーク最適化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチホップネットワークの最適化技術に関する。
【背景技術】
【０００２】
近年、マルチホップネットワークが注目されている。マルチホップネットワークは、無線通信機能を持ったルータを設置し、それらとゲートウェイ間で自律的に伝送路を構築するものである。マルチホップネットワークでは、ルータの数を増加すれば、伝送容量の向上は期待できる。しかしながら、ルータ数を増加すると、データの衝突の発生が多くなる。また、ルータの数を増加しても、クライアントとルータとの間や、ルータとゲートウェイとの間がボトルネックになり、期待した伝送容量が得られない場合がある。このため、マルチホップメットワークでは、ルータ数を最適化することが望まれる。
【０００３】
マルチホップネットワークでのルータ数の最適化については、非特許文献１に、トラヒック情報を収集し、クライアント毎のトラヒック情報（平均データレート）から収容トラヒック量（ユーザ数×平均データレート）をスループットとして算出し、ルータ毎の伝送容量から全ユーザ収容に必要なルータ数を算出する方法が提案されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】IEEE802.11e無線LANにおけるリアルタイム系トラヒック品質保証のための受付制御およびトラヒック制御方法の提案，宮野他，信学技報 IEICE Technical Report CQ2006-40, OIS2006-42 (2006-09)
【非特許文献２】Bianchi, Giuseppe. "Performance analysis of the IEEE 802.11 distributed coordination function." Selected Areas in Communications, IEEE Journal on 18.3 (2000): 535-547.
【非特許文献３】Gebali, Fayez. Analysis of Computer and Communication Networks. Springer, 2007, pp. 233-235
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１の手法では、無線区間での衝突等の伝送結果を考慮していないため、収容トラヒック量に応じて最適なルータ数を選定できないという課題がある。
【０００６】
上記事情に鑑み、本発明は、無線区間での衝突等の伝送結果に応じた収容トラヒック量に基づいて適切なルータ数を選定できる技術の提供を目的としている。
【課題を解決するための手段】
【０００７】
本発明の一態様は、ルータとゲートウェイとを備えるネットワークを対象としたネットワーク最適化方法であって、前記ネットワークのトラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出する第１のステップと、前記送信成功確率からルータ内のバッファ状況を算出する第２のステップと、前記バッファ状況に基づいて、ルータの送信確率を算出する第３のステップと、前記ルータの送信確率に基づいて、ルータとゲートウェイとの間の送受信結果として、送信待機確率、送信成功確率、及び衝突発生確率を算出する第４のステップと、前記送受信結果に基づいて、前記ネットワークにおける最適なルータ数を決定する第５のステップとを有するネットワーク最適化方法である。
【０００８】
本発明の一態様は、上記のネットワーク最適化方法であって、前記第５のステップでは、前記送受信結果に基づいてルータ数毎の伝送可能容量を算出し、前記ルータ数毎の伝送可能容量が最大となるルータ数を前記最適なルータ数として決定する。
【０００９】
本発明の一態様は、上記のネットワーク最適化方法であって、前記ネットワークのトラヒック情報を基に、全てのクライアントのトラヒック送信に要する単位時間当たりの送信占有時間を算出する第６のステップと、前記単位時間当たりの送信占有時間とゲートウェイの収容可能容量とに基づいて、前記収容可能容量の総和が前記単位時間当たりの送信占有時間を下回らない最小のゲートウェイ数を最適なゲートウェイ数として決定する第７のステップとをさらに有する。
【００１０】
本発明の一態様は、上記のネットワーク最適化方法であって、ゲートウェイとルータとの間のスループットを測定し、前記スループットと閾値とを比較して前記最適なゲートウェイ数を変更する第８のステップをさらに有する。
【００１１】
本発明の一態様は、ルータとゲートウェイとを備えるネットワークを対象としたネットワーク最適化方法であって、前記ネットワークのトラヒック情報を基に、全てのクライアントのトラヒック送信に要する単位時間当たりの送信占有時間を算出する第１のステップと、前記単位時間当たりの送信占有時間とゲートウェイの収容可能容量とに基づいて、前記収容可能容量の総和が前記単位時間当たりの送信占有時間を下回らない最小のゲートウェイ数を最適なゲートウェイ数として決定する第２のステップと、前記最適なゲートウェイ数に基づいて分割されたサブエリアに毎に、最適なルータ数を決定するステップを実行する第３のステップと、ゲートウェイとルータとの間のスループットを測定し、前記スループットと閾値とを比較して前記最適なゲートウェイ数を変更する第４のステップと、変更後の最適なゲートウェイ数に基づいて分割されたサブエリアに毎に、前記最適なルータ数を決定するステップを再実行する第５のステップとを有し、前記最適なルータ数を決定するステップは、前記ネットワークのトラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出する第６のステップと、前記送信成功確率からルータ内のバッファ状況を算出する第７のステップと、前記バッファ状況に基づいて、ルータの送信確率を算出する第８のステップと、前記ルータの送信確率に基づいて、ルータとゲートウェイとの間の送受信結果として、送信待機確率、送信成功確率、及び衝突発生確率を算出する第９のステップと、前記送受信結果に基づいてルータ数毎の伝送可能容量を算出し、前記ルータ数毎の伝送可能容量が最大となるルータ数を前記最適なルータ数として決定する第１０のステップとを有するネットワーク最適化方法である。
【００１２】
本発明の一態様は、ルータとゲートウェイとを備えるネットワークを対象としたネットワーク最適化装置であって、前記ネットワークのトラヒック情報を収集するトラヒック情報収集部と、前記トラヒック情報に基づいて、ルータ数毎の伝送可能容量を算出する無線区間解析部と、前記ルータ数毎の伝送可能容量が最大となるルータ数を最適なルータ数として決定するルータ数算出部とを備え、前記無線区間解析部は、前記トラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出し、前記送信成功確率からルータ内のバッファ状況を算出し、前記バッファ状況に基づいて、ルータの送信確率を算出し、前記ルータの送信確率に基づいて、ルータとゲートウェイとの間の送受信結果として、送信待機確率、送信成功確率、及び衝突発生確率を算出し、前記送受信結果に基づいて前記ルータ数毎の伝送可能容量を算出する、ネットワーク最適化装置である。
【００１３】
本発明の一態様は、ルータとゲートウェイとを備えるネットワークを対象としたネットワーク最適化装置であって、前記ネットワークのトラヒック情報を収集するトラヒック情報収集部と、前記トラヒック情報を基に、全てのクライアントのトラヒック送信に要する単位時間当たりの送信占有時間を算出し、前記単位時間当たりの送信占有時間とゲートウェイの収容可能容量とに基づいて、前記収容可能容量の総和が前記単位時間当たりの送信占有時間を下回らない最小のゲートウェイ数を最適なゲートウェイ数として決定するゲートウェイ数算出部と、前記トラヒック情報に基づいて、ルータ数毎の伝送可能容量を算出する無線区間解析部と、前記ルータ数毎の伝送可能容量が最大となるルータ数を最適なルータ数として決定するルータ数算出部と、ゲートウェイとルータ間のスループットを測定するスループット監視部と、前記ゲートウェイ数算出部によって決定された前記最適なゲートウェイ数に基づいて分割されたサブエリアに毎に、前記無線区間解析部及び前記ルータ数算出部によって前記最適なルータ数を決定し、前記スループット監視部によって測定された前記スループットと閾値とを比較して、前記最適なゲートウェイ数を変更し、変更後の最適なゲートウェイ数に基づいて分割されたサブエリアに毎に、前記無線区間解析部及び前記ルータ数算出部によって前記最適なルータ数を再決定する制御部とを備え、前記無線区間解析部は、前記トラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出し、前記送信成功確率からルータ内のバッファ状況を算出し、前記バッファ状況に基づいて、ルータの送信確率を算出し、前記ルータの送信確率に基づいて、ルータとゲートウェイとの間の送受信結果として、送信待機確率、送信成功確率、及び衝突発生確率を算出し、前記送受信結果に基づいて前記ルータ数毎の伝送可能容量を算出する、ネットワーク最適化装置である。
【発明の効果】
【００１４】
本発明により、無線区間での衝突等の伝送結果に応じた収容トラヒック量に基づいて適切なルータ数を選定することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施形態において用いられるマルチホップネットワークを階層型ネットワークの説明図である。
【図２】本発明の第１の実施形態に係るネットワーク最適化装置の構成を示すブロック図である。
【図３】ルータとクライアントとの間の状態遷移モデルである。
【図４】ルータとゲートウェイとの間の状態遷移モデルである。
【図５】伝送容量を求めるための時間の説明図である。
【図６】本発明の第１の実施形態に係るネットワーク最適化装置の動作を示すフローチャートである。
【図７】本発明の第１の実施形態に係るネットワーク最適化装置の構成を示すブロック図である。
【図８】本発明の第２の実施形態の処理を示すフローチャートである。
【図９】本発明の第２の実施形態に係るネットワーク最適化装置の説明図である。
【図１０】本発明の第３の実施形態に係るネットワーク最適化装置の構成を示すブロック図である。
【図１１】本発明の第３の実施形態に係るネットワーク最適化装置の説明図である。
【図１２】本発明の第３の実施形態に係るネットワーク最適化装置の説明図に用いるグラフである。
【図１３】本発明の第３の実施形態の処理を示すフローチャートである。
【図１４】本発明の第４の実施形態に係るネットワーク最適化装置の構成を示すブロック図である。
【図１５】本発明の第４の実施形態の処理を示すフローチャートである。
【図１６】本発明の第４の実施形態に係るネットワーク最適化装置の説明図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について図面を参照しながら説明する。図１は、本発明の実施形態において用いられるマルチホップネットワークを階層型ネットワークで示したものである。
【００１７】
マルチホップネットワークは、複数のルータを設置し、それらとゲートウェイ間、ルータ間、それらとクライアント間で自律的に伝送路を構築する。各クライアントは、ツリー状に結ばれたルータと、ゲートウェイとを介して、インターネット等のネットワークに接続される。したがって、マルチホップネットワークは、図１に示すように、アクセスネットワーク層と、バックボーンネットワーク層との階層型のネットワークとして表現できる。なお、図１において、ＣＬ（Client）はマルチホップネットワークを構成するクライアントを示し、Ｒ（Router）はマルチホップネットワークを構成するルータを示し、ＧＷ（Gateway）はマルチホップネットワークを構成するゲートウェイを示している。
【００１８】
マルチホップネットワークでは、ルータの増加により、伝送容量の向上が期待できる。しかしながら、ルータの増加により、データフレームの衝突が多くなる。また、ルータを増加しても、ルータとゲートウェイとの間や、クライアントとルータとの間がボトルネックとなる。したがって、単純に、ルータを増加しても、伝送可能容量は増大しない。
【００１９】
そこで、本発明の実施形態に係るネットワーク最適化装置では、図１に示すような、階層型のネットワーク層から、マルコフ連鎖モデルによる確率理論を導入して、ルータ数毎の伝送可能容量を算出し、伝送容量が最大となるルータ数を算出している。
【００２０】
＜第１の実施形態＞
図２は、本発明の第１の実施形態に係るネットワーク最適化装置１０の構成を示すブロック図である。図２に示すように、本発明の第１の実施形態に係るネットワーク最適化装置１０は、トラヒック情報収集部１１と、無線区間解析部１２と、ルータ数算出部１３と、制御部１４と、入出力部１５とを備えている。
【００２１】
トラヒック情報収集部１１は、クライアント数、データサイズ、データ発生間隔等のトラヒック情報を収集する。これらのトラヒック情報は、例えば、ＩＥＥＥ８０２．１１ｅのＴＳＰＥＣ（Traffic Specifications）ネゴシエーション手順を利用して収集される。トラヒック情報は、トラヒック情報収集部１１から、制御部１４、ルータ数算出部１３を介して、無線区間解析部１２に送られる。
【００２２】
無線区間解析部１２は、トラヒック情報収集部１１で収集されたトラヒック情報を基に、マルコフ連鎖モデルによる確率理論により、各ルータの伝送可能容量を算出する。そして、無線区間解析部１２は、ルータ数毎に各ルータの伝送可能容量を算出し、このルータ数毎の各ルータの伝送可能容量を、最適なルータ数を算出するためのパラメータとして、ルータ数算出部１３に送る。
【００２３】
ルータ数算出部１３は、ルータ数毎の各ルータの伝送可能容量から、伝送可能容量が最大となるときのルータ数を算出する。そして、ルータ数算出部１３は、この伝送可能容量が最大となるときのルータ数を、ルータ数の最適値として、制御部１４を介して、入出力部１５に出力する。
【００２４】
次に、本発明の第１の実施形態に係るネットワーク最適化装置１０における無線区間の伝送容量の算出処理について説明する。
【００２５】
本発明の第１の実施形態に係るネットワーク最適化装置１０では、以下のようにして、トラヒック情報を基に、クライアントからルータを経由しゲートウェイへのデータ送信をもとに各ルータの伝送可能容量を算出している。
【００２６】
（Ａ）トラヒック情報を基に、ルータとクライアントとの間（アクセスネットワーク層）の送信成功確率を算出する。
（Ｂ）算出された送信成功確率に基づいて、ルータのバッファ状況を算出する。
（Ｃ）算出されたルータのバッファ状況に基づいて、バックボーンネットワーク層でのルータの送信確率を算出する。
（Ｄ）算出されたルータの送信確率に基づいて、ルータとゲートウェイとの間（バックボーンネットワーク層）の送受結果である送信待機確率、送信成功確率、衝突発生確率を算出する。
（Ｅ）算出された送信待機確率、送信成功確率、及び衝突発生確率に基づいて、各ルータの伝送可能容量を算出するためのパラメータを生成する。
【００２７】
まず、トラヒック情報を基に、ルータとクライアントとの間の送信成功確率を算出する処理について説明する。
【００２８】
図３は、ルータとクライアントとの間（アクセスネットワーク層）でのルータの状態遷移モデルである。アクセスネットワーク層での状態遷移モデルは、図３に示すように、待機状態ＳＴ１と、送信成功状態ＳＴ２と、送信衝突状態ＳＴ３とにより表される。送信するデータフレームが無いときには、待機状態ＳＴ１から待機状態ＳＴ１への状態遷移となる。データフレームが送信され、データフレームの送信が成功すると、待機状態ＳＴ１から送信成功状態ＳＴ２への状態遷移となる。データフレームが送信されたが、衝突等によりデータフレームの送信が失敗すると、待機状態ＳＴ１から送信衝突状態ＳＴ３への状態遷移となる。
【００２９】
ここで、アクセスネットワーク層での送信確率をＰｔとすると、待機状態ＳＴ１から待機状態ＳＴ１への状態遷移確率ＰＩＩ、待機状態ＳＴ１から送信成功状態ＳＴ２への状態遷移確率ＰＩＳ、待機状態ＳＴ１から送信衝突状態ＳＴ３への状態遷移確率ＰＩＣは、以下のように算出できる。nはノード数、すなわち、ルータに接続しルータへの送信が競合するクライアント数である。
【００３０】
【数１】
0006395085.tif 000002
【００３１】
ここで、送信確率Ｐｔは、以下のようにして求められる（非特許文献２参照）。
【００３２】
【数２】
0006395085.tif 000003
【００３３】
（１）、（２）及び（３）式より、定常状態確率は、以下のような演算により算出できる。
【００３４】
【数３】
0006395085.tif 000004
【００３５】
以上のように、アクセスネットワーク層での送信成功確率ｓｓは、送信確率Ｐｔと、ノード数ｎと、バックオフウィンドウサイズＷとを用いて、算出することができる。送信確率Ｐｔは、上述のように、（Ｐｔ＝２／（Ｗ＋１））として求められる。バックオフウィンドウサイズＷは、無線方式によって固定値である。
【００３６】
次に、アクセスネットワーク層での送信成功確率に基づいて、ルータのバッファ状況を算出する処理について説明する。
【００３７】
ルータは、ゲートウェイの送信バッファにデータフレームがない状態では、送信を行うことはない。このことから、ルータのバッファにデータフレームを持たない確率を算出すれば、これを基に、ルータとゲートウェイとの間（バックボーンネットワーク層）でのルータの送信待機確率が算出できる。ルータの送信待機確率が算出できれば、ルータの送信確率が算出できる。
【００３８】
ルータのバッファにデータフレームを持たない確率Ｐｅｍｐｔｙは、Ｍ／Ｍ／１Ｂのキューモデルを利用して、以下のように算出できる。
【００３９】
【数４】
0006395085.tif 000005
【００４０】
ここで、ρはルータ利用率、Ｂはバッファサイズである。ルータ利用率ρは、以下のようにして求められる（非特許文献３参照）。
【００４１】
【数５】
0006395085.tif 000006
【００４２】
ルータ内のバッファへのデータフレームの到着確率ａは、アクセスネットワーク層でのクライアントからルータへの成功確率であり、（５）式より算出する。ルータ内のバッファからの送信確率ｃは、バックボーンネットワーク層でのルータからゲートウェイへのデータフレームの成功確率であり、（５）式より算出する。このように、ルータ内のバッファ状況は、アクセスネットワーク層でのルータの送信成功確率に基づいて算出できる。
【００４３】
次に、ルータのバッファ状況に基づいて、バックボーンネットワーク層でのルータの送信確率を算出する処理について説明する。
【００４４】
図４は、ルータとゲートウェイとの間（バックボーンネットワーク層）でのルータの状態遷移モデルである。図４において、ＳＴ１１は待機状態、ＳＴ（０）はバックオフカウンタが「０」である状態、ＳＴ（１）はバックオフカウンタが「１」である状態、ＳＴ（Ｗ−２）はバックオフカウンタが「Ｗ−２」である状態、ＳＴ（Ｗ−１）はバックオフカウンタが「Ｗ−１」である状態を示す。
【００４５】
バックオフカウンタは、バックオフ時間を設定するものである。バックオフ値は、「０」から「Ｗ−１」のいずれかの値が割り当てられる。バックオフカウンタの値が「０」になると、データフレームが送信される。
【００４６】
図４において、待機状態ＳＴ１１から待機状態ＳＴ１１への状態遷移ではデータフレームは送出されないので、状態遷移確率はＰｅｍｐｔｙ（ルータのバッファにデータフレームを持たない確率）となる。また、バックオフカウンタが「０」である状態ＳＴ（０）から待機状態ＳＴ１１への状態遷移確率では、データフレームは送出されないので、状態遷移確率はＰｅｍｐｔｙとなる。他の状態への状態遷移確率Ｐｂは、確率Ｐｅｍｐｔｙを用いて、以下のように示される。
【００４７】
【数６】
0006395085.tif 000007
【００４８】
図４の状態遷移モデルから、バックボーンネットワーク層でのルータの送信確率ｓ０ｒｅａｌは、バックオフカウンタが「０」である状態ＳＴ（０）である確率ｓ０から、以下のように算出できる。
【００４９】
【数７】
0006395085.tif 000008
【００５０】
このように、バックボーンネットワーク層でのルータの送信確率ｓ０ｒｅａｌは、ルータのバッファ状況（ルータのバッファにデータフレームを持たない確率）に基づいて算出することができる。
【００５１】
次に、ルータの送信確率に基づいて、ルータとゲートウェイ間（バックボーンネットワーク層）の送受結果である送信待機確率、送信成功確率、衝突発生確率を算出する処理について説明する。
【００５２】
ルータ数ｎｍのサブエリアのルータとゲートウェイ間の送受状態は、（４）、（５）、（６）式と同様にして、算出することができる。つまり、ルータの送信確率ｓ０ｒｅａｌは、（９）式により算出できる。このルータの送信確率ｓ０ｒｅａｌを使って、ルータとゲートウェイ間の送受状態は、以下のようにして、算出できる。
【００５３】
【数８】
0006395085.tif 000009
【００５４】
ルータとゲートウェイ間の送受結果である送信待機確率ｓｉｍ、送信成功確率ｓｓｍ、衝突発生確率ｓｃｍが算出できれば、これらに基づいて、以下のようにして、各ルータの伝送可能容量Ｒが算出できる。
【００５５】
【数９】
0006395085.tif 000010
【００５６】
上式における各時間は、具体的には、図５に示すような時間となる。また、伝送速度を５４Ｍｂｐｓと仮定すると、時間は、下記で計算される。
【００５７】
【数１０】
0006395085.tif 000011
【００５８】
上述のように、（１３）式に基づいて、ルータｎｍ数での伝送可能容量Ｒが算出できる。そこで、ルータ数算出部１３は、ルータ数をパラメータに伝送可能容量Ｒを取得し、伝送可能容量Ｒが最大となるときのルータ数を、最適なルータ数として決定している。
【００５９】
図６は、本発明の第１の実施形態に係るネットワーク最適化装置の動作を示すフローチャートである。
【００６０】
図６において、トラヒック情報収集部１１は、ＴＳＰＥＣネゴシエーション手順により、クライアント数、データサイズ、データ発生間隔等をトラヒック情報として収集し、無線区間解析部１２に転送する（ステップＳ１）。
【００６１】
無線区間解析部１２は、利用可能なルータ数Ｋ（Ｋは整数）の初期値を設定する（ステップＳ２）。なお、ここでは、利用可能なルータ数は、ｐ個からｑ個に設定するものとし、ルータ数Ｋの初期値として（Ｋ＝ｐ）に設定する。
【００６２】
無線区間解析部１２は、トラヒック情報と、利用可能なルータ数を設定すると、前述した手順により、トラヒック情報から、マルコフ連鎖モデルによる確率理論で、各ルータの伝送可能容量Ｒを算出する（ステップＳ３）。すなわち、ステップＳ３において、無線区間解析部１２は、トラヒック情報を基に、ルータとクライアントの送信成功確率を算出する（（１）式〜（６）式参照）。そして、無線区間解析部１２は、算出された送信成功確率に基づいて、ルータのバッファ状況を算出する（（７）式参照）。そして、無線区間解析部１２は、算出されたルータのバッファ状況に基づいて、ルータの送信確率を算出する（（８）〜（９）式参照）。そして、無線区間解析部１２は、算出されたルータの送信確率に基づいて、ルータとゲートウェイ間の送受結果である送信待機確率、送信成功確率、衝突発生確率を算出する（（１０）〜（１２）式参照）。そして、無線区間解析部１２は、算出された送信待機確率、送信成功確率、衝突発生確率から、各ルータ数での伝送可能容量を算出する（（１３）式参照）。
【００６３】
無線区間解析部１２は、設定可能な全てのルータ数（Ｋ＝ｐからｑ）について、各ルータ数での伝送可能容量の算出を行ったか否かを判定する（ステップＳ４）。設定可能な全てのルータ数（Ｋ＝ｐからｑ）について、各ルータの伝送可能容量の算出を行っていなければ（ステップＳ４：Ｎｏ）、無線区間解析部１２は、利用可能なルータ数Ｋを例えば（Ｋ＋１）に変更して（ステップＳ５）、ステップＳ３に処理をリターンする。ステップＳ３からステップＳ５の処理を繰り返すことで、設定可能な全てのルータ数（Ｋ＝ｐ〜ｑ）について、各ルータの伝送可能容量が算出される。
【００６４】
ステップＳ４で、設定可能な全てのルータ数（Ｋ＝ｐ〜ｑ）について各ルータ数の伝送可能容量の算出が終了したら（ステップＳ４：Ｙｅｓ）、ルータ数算出部１３は、ルータ数（Ｋ＝ｐ〜ｑ）毎の各ルータの伝送可能容量を、ルータ数を算出するためのパラメータとして、ルータ数算出部１３に送る。ルータ数算出部１３は、ルータ数毎の各ルータ数の伝送容量が最大となるときのルータ数を、最適なルータ数として決定する（ステップＳ６）。
【００６５】
すなわち、ルータ数算出部１３は、ルータ数（Ｋ＝ｐ〜ｑ）毎に、（１３）式に示したパラメータＲの値を取得する。そして、ルータ数算出部１３は、伝送可能容量（Ｒ）の値が最大値となるときのルータ数を求め、この最大値となるときのルータ数を、最適なルータ数として出力する。
【００６６】
以上説明したように、本発明の第１の実施形態に係るネットワーク最適化装置１０では、トラヒック情報を基に、マルコフ連鎖モデルによる確率理論により無線区間の伝送容量を算出し、算出された伝送容量をパラメータとして、伝送可能容量を最大とするルータ数を算出している。これにより、無線区間での衝突等の伝送結果を考慮して、収容トラヒック量に応じて最適なルータ数を選定できる。
【００６７】
＜第２の実施形態＞
次に、本発明の第２の実施形態について説明する。図７は、本発明の第２の実施形態を示すものである。図７に示すように、本発明の第２の実施形態に係るネットワーク最適化装置１１０は、トラヒック情報収集部１１１と、無線区間解析部１１２と、ルータ数算出部１１３と、制御部１１４と、入出力部１１５と、ゲートウェイ数算出部１１６とを備えている。トラヒック情報収集部１１１、無線区間解析部１１２、ルータ数算出部１１３、制御部１１４、入出力部１１５は、第１の実施形態におけるトラヒック情報収集部１１、無線区間解析部１２、ルータ数算出部１３、制御部１４、入出力部１５と同様である。本発明の第２の実施形態では、更に、ゲートウェイ数算出部１１６を備えている。
【００６８】
ゲートウェイ数算出部１１６は、最適なゲートウェイ数を算出するものである。ゲートウェイ数算出部１１６には、トラヒック情報収集部１１１から制御部１１４を介して、クライアント数、データサイズ、送信頻度、物理伝送速度がトラヒック情報として送られる。ゲートウェイ数算出部１１６は、トラヒック情報から、以下に示すように、全てのトラヒック送信に要する送信占有時間Ｔｔｒａｎｓを算出する。
【００６９】
【数１１】
0006395085.tif 000012
【００７０】
そして、ゲートウェイ数算出部１１６は、送信占有時間Ｔｔｒａｎｓから、ゲートウェイの収容容量が送信占有時間Ｔｔｒａｎｓを下回らない最小の整数として、ゲートウェイ数を設定する。例えば、１つのゲートウェイの収容容量が「１」で送信占有時間が「３．５」ならば、４個のゲートウェイを配置する。
【００７１】
図８は、本発明の第２の実施形態の処理を示すフローチャートである。図８において、ゲートウェイ数算出部１１６は、トラヒック情報収集部１１１からクライアント数、クライアント毎にデータサイズ、送信頻度、物理伝送速度をトラヒック情報として収集する（ステップＳ１０１）。ゲートウェイ数算出部１１６は、トラヒック情報から、全てのクライアントのトラヒック送信に要する送信占有時間Ｔｔｒａｎｓを算出する（ステップＳ１０２）。そして、ゲートウェイ数算出部１１６は、送信占有時間Ｔｔｒａｎｓから、送信占有時間Ｔｔｒａｎｓを下回らない最小の整数として、ゲートウェイ数を算出する（ステップＳ１０３）。
【００７２】
本発明の第２の実施形態では、ゲートウェイの数を最適に設定できる。例えば、図９（Ａ）に示すように、１つのゲートウェイのみの場合には、ゲートウェイがボトルネックになり、所望の伝送容量が得られない。このような場合には、上述のようにして、最適なゲートウェイの数を算出し、図９（Ｂ）に示すように、算出された数のゲートウェイを配置する（この例では、４つのゲートウェイが配置されている）。これにより、所望の伝送容量を確保できる。
【００７３】
＜第３の実施形態＞
次に、本発明の第３の実施形態について説明する。図１０は、本発明の第３の実施形態を示すものである。図１０に示すように、本発明の第３の実施形態に係るネットワーク最適化装置２１０は、トラヒック情報収集部２１１と、無線区間解析部２１２と、ルータ数算出部２１３と、制御部２１４と、入出力部２１５と、スループット監視部２１７とを備えている。
【００７４】
トラヒック情報収集部２１１、無線区間解析部２１２、ルータ数算出部２１３、制御部２１４、入出力部２１５は、第１の実施形態におけるトラヒック情報収集部１１、無線区間解析部１２、ルータ数算出部１３、制御部１４、入出力部１５と同様である。本発明の第３の実施形態では、更に、スループット監視部２１７を備えている。
【００７５】
スループット監視部２１７は、ゲートウェイとルータとの間のスループットを監視する。そして、スループット監視部２１７は、計測されたスループットと閾値とを比較し、このスループットの監視値と閾値との比較結果に基づいて、ゲートウェイの追加又は利用停止を、制御部２１４を介して入出力部２１５に出力する。
【００７６】
つまり、図１１はクライアントの参加、離脱によるトラヒックの変化を示し、図１２は、トラヒックの変化とスループットの変化との関係を示している。図１１に示すように、クライアントの参加、離脱により、ゲートウェイとルータとの間のスループットは変化する。スループット監視部２１７は、ゲートウェイとルータとの間のスループットを一定時間の間、監視する。例えば、図１２に示すように、クライアントの参加、離脱により、トラヒックの変化が生じ、これにより、ゲートウェイとルータとの間のスループットが変化したとする。スループット監視部２１７は、計測されたスループットが閾値ＴＨ１を所定時間下回った場合、ゲートウェイの利用停止を制御部２１４を介して入出力部２１５に出力する。また、スループット監視部２１７は、計測されたスループットが閾値ＴＨ２を所定時間上回った場合、ゲートウェイの追加を制御部２１４を介して入出力部２１５に出力する。
【００７７】
図１３は、本発明の第３の実施形態の処理を示すフローチャートである。図１３において、スループット監視部２１７は、ゲートウェイとルータとの間のスループットを監視する（ステップＳ２０１）。そして、スループット監視部２１７は、計測されたスループットが所定時間閾値ＴＨ１以下か否かを判定する（ステップＳ２０２）。計測されたスループットが所定時間閾値ＴＨ１以下であると判定された場合（ステップＳ２０２：Ｙｅｓ）、スループット監視部２１７は、ゲートウェイの利用停止を制御部２１４を介して入出力部２１５に出力する（ステップＳ２０３）。
【００７８】
計測されたスループットが閾値ＴＨ１以下ではないと判定された場合（ステップＳ２０２：Ｎｏ）、スループット監視部２１７は、計測されたスループットが所定時間閾値ＴＨ２以上か否かを判定する（ステップＳ２０４）。計測されたスループットが所定時間閾値ＴＨ２以上であると判定された場合（ステップＳ２０４：Ｙｅｓ）、スループット監視部２１７は、ゲートウェイの追加を制御部２１４を介して入出力部２１５に出力する（ステップＳ２０５）。
【００７９】
このように、本実施形態では、スループット監視部２１７が設けられる。そして、スループット監視部２１７で、計測されたスループットと閾値とが比較され、このスループットの監視値と閾値との比較結果に基づいて、ゲートウェイの追加又は削除が行われる。これにより、ゲートウェイとルータとの間のスループットの変化に追従して、ゲートウェイの数を最適に設定できる。
【００８０】
なお、スループット監視部２１７は、特定のゲートウェイのスループットを監視しても良いし、全てのゲートウェイを監視しても良い。全てのゲートウェイを監視する場合、スループット監視部２１７は、ゲートウェイの平均スループットが閾値ＴＨ１を下回った場合、最もスループットの小さいゲートウェイの利用停止を、制御部２１４を介して入出力部２１５に出力し、ゲートウェイの平均スループットが閾値ＴＨ２を上回った場合、ゲートウェイの追加を制御部２１４を介して入出力部２１５に出力する。
【００８１】
＜第４の実施形態＞
次に、本発明の第４の実施形態について説明する。図１４は、本発明の第４の実施形態を示すものである。図１４に示すように、本発明の第４の実施形態に係るネットワーク最適化装置３１０は、トラヒック情報収集部３１１と、無線区間解析部３１２と、ルータ数算出部３１３と、制御部３１４と、入出力部３１５と、ゲートウェイ数算出部３１６と、スループット監視部３１７とを備えている。
【００８２】
トラヒック情報収集部３１１、無線区間解析部３１２、ルータ数算出部３１３、制御部３１４、入出力部３１５は、第１の実施形態におけるトラヒック情報収集部１１、無線区間解析部１２、ルータ数算出部１３、制御部１４、入出力部１５と同様である。ゲートウェイ数算出部３１６は、本発明の第２の実施形態におけるゲートウェイ数算出部１１６（図７参照）と同様である。スループット監視部３１７は、本発明の第３の実施形態におけるスループット監視部２１７（図１０参照）と同様である。
【００８３】
図１５は、本発明の第４の実施形態の処理を示すフローチャートである。図１５において、トラヒック情報収集部３１１は、トラヒック情報を収集し、ゲートウェイ数算出部３１６及び無線区間解析部３１２に送る（ステップＳ３０１）。
【００８４】
ゲートウェイ数算出部３１６は、トラヒック情報から、最適なゲートウェイ数を算出する（ステップＳ３０２）。なお、ステップＳ３０２の処理は、図８にフローチャートで示した処理（ステップＳ１０１〜ステップＳ１０３）と同様である。
【００８５】
ゲートウェイ数が算出されたら、オペレータは、算出した数のゲートウェイを設置し、ゲートウェイ毎にサブエリアを構成する。クライアントは最も通信状態の良いゲートウェイに接続する（ステップＳ３０３）。そして、図６にフローチャートで示した処理（ステップＳ１〜ステップＳ６）と同様に、最適なルータ数を算出する（ステップＳ３０４）。そして、オペレータは、各サブエリアに最適な数のルータを配置して、運用を行う。
【００８６】
運用中では、スループット監視部３１７は、ゲートウェイとルータとの間のスループットを監視する（ステップＳ３０５）。そして、スループット監視部３１７は、計測されたスループットが所定時間閾値ＴＨ１以下か否かを判定する（ステップＳ３０６）。計測されたスループットが所定時間閾値ＴＨ１以下であると判定された場合（ステップＳ３０６：Ｙｅｓ）、スループット監視部３１７は、ゲートウェイの利用停止を制御部３１４を介して入出力部３１５に出力する（ステップＳ３０７）。
【００８７】
計測されたスループットが閾値ＴＨ１以下ではないと判定された場合（ステップＳ３０６：Ｎｏ）、スループット監視部２１７は、計測されたスループットが所定時間閾値ＴＨ２以上か否かを判定する（ステップＳ３０８）。計測されたスループットが所定時間閾値ＴＨ２以上ではないと判定された場合（ステップＳ３０８：Ｎｏ）、ステップＳ３０５に処理をリターンする。
【００８８】
ステップＳ３０８で、計測されたスループットが閾値ＴＨ２以上であると判定された場合（ステップＳ３０８：Ｙｅｓ）、スループット監視部３１７は、ゲートウェイの追加を制御部３１４を介して入出力部３１５に出力する（ステップＳ３０９）。
【００８９】
ステップＳ３０７でゲートウェイの利用停止が出力された場合、又は、ステップＳ３０９でゲートウェイの追加が出力された場合、オペレータは、ゲートウェイを追加配置し、サブエリアを再構築する（ステップＳ３１０）。そして、図６にフローチャートで示した処理と同様に、最適なルータ数を算出する（ステップＳ３１１）。そして、オペレータは、各サブエリアに最適な数のルータを配置して、ステップＳ３０５に処理を戻し、運用を行う。
【００９０】
本実施形態では、図１６（Ａ）に示すように、図８のフローチャートで示す処理により、クライアントからトラヒック情報を取得して、図１６（Ｂ）に示すように、最適なゲートウェイの数が決定される。ゲートウェイ数が算出されたら、図１６（Ｃ）に示すように、ゲートウェイ毎にサブエリアを構成する。そして、図６にフローチャートで示した処理により、サブエリア毎に最適なルータ数が算出される。そして、各サブエリアに最適な数のルータが配置されて、運用が行われる。
【００９１】
運用中には、ゲートウェイとルータとの間のスループットが監視される。図１６（Ｄ）に示すように、クライアントの離脱により、ゲートウェイとルータとの間のスループットが変化すると、図１６（Ｅ）に示すように、再び、最適なゲートウェイの数が決定され、サブエリアを再構築する。そして、図６にフローチャートで示した処理により、最適なルータ数が算出される。
【００９２】
このように、本実施形態では、ゲートウェイの数と、ルータの数が最適に設置される。また、クライアントの参加、離脱によりゲートウェイとルータとの間のスループットが変化すると、再び、最適なゲートウェイの数が決定され、サブエリアを再構築し、最適なルータ数が算出される。
【００９３】
なお、ネットワーク最適化装置１０、１１０，２１０，３１０の全部または一部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００９４】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００９５】
１０…ネットワーク最適化装置，  １１，１１１，２１１，３１１…トラヒック情報収集部，  １２，１１２，２１２，３１２…無線区間解析部，  １３，１１３，２１３，３１３…ルータ数算出部，  １４，１１４，２１４，３１４…制御部，  １５，１１５，２１５，３１５…入出力部，  １１６，３１６…ゲートウェイ数算出部，  ２１７，３１７…スループット監視部
【図１】
0006395085.tif 000013
【図２】
0006395085.tif 000014
【図３】
0006395085.tif 000015
【図４】
0006395085.tif 000016
【図５】
0006395085.tif 000017
【図６】
0006395085.tif 000018
【図７】
0006395085.tif 000019
【図８】
0006395085.tif 000020
【図９】
0006395085.tif 000021
【図１０】
0006395085.tif 000022
【図１１】
0006395085.tif 000023
【図１２】
0006395085.tif 000024
【図１３】
0006395085.tif 000025
【図１４】
0006395085.tif 000026
【図１５】
0006395085.tif 000027
【図１６】
0006395085.tif 000028