(57)【特許請求の範囲】
【請求項１】
複数の通信ユニットで構成されるネットワークに接続され、いずれかの通信ユニットにおけるパケット転送を制御する制御装置が実行するパケット転送方法において、
前記制御装置が
記憶部に記憶された前記通信ユニット毎に隣接する通信ユニットに関する隣接ユニット情報と、各通信ユニットと前記制御装置間の経路を示す経路情報を参照して、複数の通信ユニットのうち、他通信ユニットまたは該制御装置から受信したパケットをブロードキャスト転送すべき通信ユニットを選択するステップと、
前記選択されたブロードキャスト転送すべき通信ユニットを示す情報を含むパケットを生成し、前記複数ユニットのいずれかに送信するステップと、
を有し、
前記ブロードキャスト対象ユニット選択処理において、前記各通信ユニットに隣接する通信ユニットに含まれるブロードキャスト対象ユニットの上限数を設定し、前記上限数を超えないように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とするブロードキャスト転送方法。
【請求項２】
前記ブロードキャスト対象ユニットの選択処理において、隣接する通信ユニットの数が少ない通信ユニットへブロードキャスト転送させるように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする請求項１に記載のブロードキャストパケットの転送方法。
【請求項３】
前記ブロードキャスト対象ユニット選択処理において、前記経路情報に基づいて前記ブロードキャストパケットの配信元の通信ユニットからの経路が最短経路となるように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする請求項１に記載のブロードキャストパケットの転送方法。
【請求項４】
前記ブロードキャスト対象ユニット選択処理において、既に選択されたブロードキャスト対象ユニットでカバーできていない隣接する通信ユニットをより多くカバーするように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする請求項１に記載のブロードキャストパケットの転送方法。
【請求項５】
全ての前記通信ユニットに前記ブロードキャストパケットが配信されるように、前記ブロードキャスト対象ユニットの選択処理を繰り返し実行する、
ことを特徴とする請求項１に記載のブロードキャストパケットの転送方法。
【請求項６】
前記ブロードキャスト対象ユニットを選択するステップは、
隣接する通信ユニットの数が最も少ない通信ユニットへブロードキャスト転送させるように前記ブロードキャスト対象ユニットを選択する第１のステップと、
前記経路情報に基づいて前記ブロードキャストパケットの配信元の通信ユニットからの経路が最小ホップ数と成るように前記ブロードキャスト対象ユニットを選択する第２のステップと、
既に選択されたブロードキャスト対象ユニットでカバーできていない隣接する通信ユニットをより多くカバーするように前記ブロードキャスト対象ユニットを選択する第３のステップと、
からなる、
ことを特徴とする請求項１に記載のブロードキャストパケットの転送方法。
【請求項７】
前記各通信ユニットに隣接する通信ユニットに含まれるブロードキャスト対象ユニットの上限数を設定し、前記上限数を超えないように前記ブロードキャスト対象ユニットを選択する第４のステップからなる、
ことを特徴とする請求項６に記載のブロードキャストパケットの転送方法。
【請求項８】
前記第１、第２、第３、第４のステップをパケットを送信すべき全てのユニットをカバーするまで繰り返し実行する、
ことを特徴とする請求項７に記載のブロードキャストパケットの転送方法。
【請求項９】
複数の通信ユニットで構成されるネットワークに接続され、いずれかの通信ユニットにおけるパケット転送を制御する制御装置であって、
前記通信ユニット毎に該通信ユニットに隣接する通信ユニットを示す隣接ユニット情報と、各通信ユニットと前記制御装置間の経路を示す経路情報が記憶される記憶部と、
前記隣接ユニット情報および前記経路情報を参照して、前記複数の通信ユニットのうち、他通信ユニットまたは該制御装置から受信したパケットをブロードキャスト転送すべき通信ユニットを選択する選択部と、
前記選択されたブロードキャスト転送すべき通信ユニットを示す情報を含むパケットを生成し、前記複数ユニットのいずれかに送信する送信部とを有し、
前記選択部において、前記各通信ユニットに隣接する通信ユニットに含まれるブロードキャスト対象ユニットの上限数を設定し、前記上限数を超えないように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とするブロードキャスト転送装置。
【請求項１０】
複数の通信ユニットで構成されるネットワークに接続され、いずれかの通信ユニットにおけるパケット転送を制御する制御装置に、
記憶部に記憶された前記通信ユニット毎に隣接する通信ユニットに関する隣接ユニット情報と、各通信ユニットと前記制御装置間の経路を示す経路情報を参照して、複数の通信ユニットのうち、他通信ユニットまたは該制御装置から受信したパケットをブロードキャスト転送すべき通信ユニットを選択するステップと、
前記選択されたブロードキャスト転送すべき通信ユニットを示す情報を含むパケットを生成し、前記複数ユニットのいずれかに送信するステップと、
前記ブロードキャスト対象ユニットを選択するステップにおいて、前記各通信ユニットに隣接する通信ユニットに含まれるブロードキャスト対象ユニットの上限数を設定し、前記上限数を超えないように前記ブロードキャスト対象ユニットを選択するステップと、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
アドホックネットワーク環境におけるブロードキャストパケットの転送方法、装置、およびプログラムに関する。
【背景技術】
【０００２】
ルータやアクセスポイント、基地局といったネットワーク接続装置を使わずに通信装置同士が直接または他の通信装置を経由して無線で接続するアドホック無線ネットワークが知られている。
【０００３】
アドホック無線ネットワークの環境において、数多くの通信ユニットに対して、それらを動作するためのファームウェアを更新することが求められている。ファームウェア更新方法としては従来、ブロードキャスト転送による通信ユニットへのファームウェアダウンロードを実施し、ファームウェア更新を行っていた。
【０００４】
また、ブロードキャスト転送において、送信元を中心として距離、受信電力値、送信タイミングをもとに領域を分けてブロードキャストを行うことで、パケット衝突を抑止し、効率的にパケット転送を行う従来技術が知られている（例えば特許文献１に記載の技術）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−８６６４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、上述の従来技術では、各通信ユニットがブロードキャスト転送を行うこと、かつ転送パケットサイズが大きかったことにより、無線ネットワークのトラヒックが劇的に増大する。すなわち、無線ネットワークに流れる情報量が、“通信ユニット×パケットサイズ”となる。このトラヒックの増大の結果、パケット受信が異常となり、正常にファームウェアダウンロードが完了しない通信ユニットが数多く存在していた。通信不具合によりネットワークから切断された通信ユニットも存在し、そのユニットに対しては人が通信ユニットまで赴き、ファームウェア更新作業を実施しなければならないという問題点があった。
【０００７】
図１に、全ての通信ユニットがブロードキャスト転送を実施した際の、ユニット間のパケットの流れを示す。まず、第１ホップとして、ファームウェアの送信元であるゲートウェイマシン１０２から、その周囲の通信ユニット１０１−１に対してブロードキャスト転送が実施される。次に、第２ホップとして、第１ホップの受信を行った各通信ユニット１０１−１の各々から、それぞれの周囲の通信ユニット１０１−２に対してブロードキャスト転送が実施される。さらに、第３ホップとして、第２ホップの受信を行った各通信ユニット１０１−２の各々から、それぞれの周囲の通信ユニットに対してブロードキャスト転送が実施される。このように、ゲートウェイマシン１０２から周囲の通信ユニット１０１−１、１０１−２、・・・に対して、第１、第２、第３ホップというように段階的にブロードキャスト転送が行われる。そして、各段階（ホップ）で、全通信ユニット１０１−１、１０１−２、・・・がブロードキャスト転送を実施していた。このため、細破線（第１ホップ）、細実線（第２ホップ）、太破線（第３ホップ）というように、トラヒックが爆発的に増大していることがわかる。
【０００８】
また、前述した、送信元を中心として距離、受信電力値、送信タイミングを元に領域を分けてブロードキャストを行う従来技術では、以下のような問題点があった。すなわち、ファームウェアデータのように多数のパケット(５０００パケット相当)を、少なくない数（例えば数百〜数千台規模）の通信ユニットに対して転送を必要とする場合には、各ユニットがお互いの位置検出、送信タイミング決定を行うために待ち合わせ時間が多数発生する。従って、前述したような方式は、早急にファーム更新を行うには不適格である。また、数百〜数千台相当の通信ユニットが、お互いに送信元の位置検出手段、受信電力値検出手段、領域検出手段、送信タイミング決定手段を具備／制御するには、多大なメモリ量を必要とするため、部品コスト、消費電力が高くなる場合もある。さらに、通信ユニットの配置位置が密集しており、かつブロードキャストを実施する位置であった場合、密集した通信ユニット全てがブロードキャストを行い、無線ネットワークが輻輳し、パケットロスが発生しやすくなる。このため、ファームウェアデータのように多数のパケットを効率的に全ユニットに到達させるには、的確なブロードキャスト実施ユニットの選択を行う必要があるという問題点を有していた。
【０００９】
そこで、本発明の１つの課題では、無線ネットワークに流れるパケットを抑制してネットワークトラヒックを軽減し、パケットの到達精度を向上させることである。
【課題を解決するための手段】
【００１０】
態様の一例では、複数の通信ユニットで構成されるネットワークに接続され、いずれかの通信ユニットにおけるパケット転送を制御する制御装置が実行するパケット転送方法において、前記制御装置が記憶部に記憶された前記通信ユニット毎に隣接する通信ユニットに関する隣接ユニット情報と、各通信ユニットと前記制御装置間の経路を示す経路情報を参照して、複数の通信ユニットのうち、他通信ユニットまたは該制御装置から受信したパケットをブロードキャスト転送すべき通信ユニットを選択するステップと、前記選択されたブロードキャスト転送すべき通信ユニットを示す情報を含むパケットを生成し、前記複数ユニットのいずれかに送信するステップと、を有することを特徴とするブロードキャスト転送方法を提供する。
【発明の効果】
【００１１】
通信ユニットの中から無線電波到達範囲が重ならないような選択を行うため、無線ネットワークのトラヒックを軽減でき、ブロードキャストをより効率的に行うことが可能となる。
【図面の簡単な説明】
【００１２】
【図１】全ての通信ユニットがブロードキャスト転送を実施した際の、ユニット間のパケットの流れを示す従来図である。
【図２】本実施形態の基本動作の説明図である。
【図３】本実施形態が適用されるネットワーク構成図である。
【図４】ゲートウェイの構成図である。
【図５】通信ユニットの構成図である。
【図６】アドホックＦＰＧＡの構成図である。
【図７】第１の処理シーケンス例（１／４）を示す図である。
【図８】第１の処理シーケンス例（２／４）を示す図である。
【図９】第１の処理シーケンス例（３／４）を示す図である。
【図１０】第１の処理シーケンス例（４／４）を示す図である。
【図１１】ブロードキャスト転送許可指示のメッセージフォーマット例を示す図である。
【図１２】第２の処理シーケンス例（１／４）を示す図である。
【図１３】第２の処理シーケンス例（２／４）を示す図である。
【図１４】第２の処理シーケンス例（３／４）を示す図である。
【図１５】第２の処理シーケンス例（４／４）を示す図である。
【図１６】隣接ユニット・経路情報と通信ユニットの選択例を示す図（初期状態）である。
【図１７】隣接ユニット・経路情報と通信ユニットの選択例を示す図（実施例１）である。
【図１８】各通信ユニットに隣接する選択ユニットを示す図（実施例１）である。
【図１９】隣接ユニット・経路情報と通信ユニットの選択例を示す図（実施例２）である。
【図２０】各通信ユニットに隣接する選択ユニットを示す図（実施例２）である。
【図２１】隣接ユニット・経路情報と通信ユニットの選択例を示す図（実施例３）である。
【図２２】各通信ユニットに隣接する選択ユニットを示す図（実施例３）である。
【図２３】隣接ユニット・経路情報と通信ユニットの選択例を示す図（実施例４）である。
【図２４】各通信ユニットに隣接する選択ユニットを示す図（実施例４）である。
【図２５】隣接ユニット・経路情報と通信ユニットの選択例を示す図（実施例５）である。
【図２６】各通信ユニットに隣接する選択ユニットを示す図（実施例５）である。
【図２７】隣接ユニット・経路情報と通信ユニットの選択例を示す図（実施例６）である。
【図２８】各通信ユニットに隣接する選択ユニットを示す図（実施例６）である。
【図２９】隣接ユニット・経路情報と通信ユニットの選択例を示す図（最終結果）である。
【図３０】各通信ユニットに隣接する選択ユニットを示す図（最終結果）である。
【図３１】選択ユニットの選定処理を示すフローチャートである。
【図３２】ブロードキャスト対象ユニットの選択処理の詳細を示すフローチャートである。
【図３３】本実施形態におけるパケット転送による無線ネットワークのトラヒック状態を示す図である。
【図３４】本実施形態のシステムを実現可能なハードウェアシステムの構成図である。
【発明を実施するための形態】
【００１３】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。
図２は、本実施形態の基本動作の説明図である。ＬＡＮ（ローカルエリアネットワーク）等を介して特には図示しないサーバと接続される中継装置であるゲートウェイ（Ｇａｔｅｗａｙ）１０２を中心として、無線ネットワーク環境が構築され、各通信ユニット（通信装置）１０１が、アドホックネットワークを構成する。図２において、ゲートウェイ１０２との間で第１ホップの通信を行う通信ユニット１０１は、ゲートウェイ１０２を中心とした円の内部に位置するものである。円の外部に位置するものは第２ホップでの通信を行う。
【００１４】
本実施形態では、ゲートウェイ１０２から通信ユニット１０１へのブロードキャスト転送において、全通信ユニット１０１がブロードキャスト転送を行うのではない。後述するサーバを介してゲートウェイ１０２から、以下のアルゴリズムにより通信ユニット１０１のうちから選択した特定の通信ユニットをブロードキャスト対象ユニットとして指定する。図２においてブロードキャスト対象ユニットは黒い塗りつぶしのマーク、及び白い塗りつぶしに横線のマークで示されている。そして、その選択されたブロードキャスト対象ユニットのみが、周囲の通信ユニット１０１に対してブロードキャスト転送を行う。ここで、ブロードキャスト転送を受けた通信ユニット１０１が非ブロードキャスト対象ユニットであった場合、さらなるブロードキャスト転送は実施しない。
【００１５】
この本実施形態のさらに具体的な動作について、以下に記す。
ステップ１．
各通信ユニット１０１は、定期的（１分間隔など）に、隣接する通信ユニット（以下これを「隣接ユニット」と呼ぶ）に対し、Ｈｅｌｌｏパケットを送出する。Ｈｅｌｌｏパケットを受信した通信ユニット１０１は、そのＨｅｌｌｏパケットに付加されているそのＨｅｌｌｏパケットの送信元を示す通信ユニットの識別情報(以下これを「隣接ユニット情報」と呼ぶ)を記憶しておく。各通信ユニット１０１は、定期的(１時間間隔など)に、隣接ユニット情報を、ゲートウェイ１０２を介してサーバ（図２では図示していない）へ通知する。サーバは、各通信ユニット１０１毎に、通知された隣接ユニット情報を管理する。
【００１６】
ステップ２．
通信ユニット１０１からサーバへパケットが転送される際、経路情報も同時に通知される。サーバは、経路情報を、通信ユニット１０１毎に管理する。すなわち、１つの通信ユニット１０１についての経路情報は、サーバからゲートウェイ１０２を介してその通信ユニット１０１にパケットが転送される際に経由する他の通信ユニット１０１の経路を示す情報である。パケットが転送される際に、途中の通信ユニット１０１を通過する毎に、その通過する通信ユニット１０１の識別情報が経路情報に追加されてゆく。
【００１７】
ステップ３．
サーバは、自身が管理している隣接ユニット情報と経路情報に基づいて、ブロードキャストを実施させるブロードキャスト対象ユニットを、以下のアルゴリズム（ａ）〜（ｄ）により、全ての通信ユニット１０１がパケット受信できるまで繰り返し選択していく。
（ａ）最も隣接ユニット数が少ない通信ユニット１０１に対し、確実にブロードキャスト転送させるように、ブロードキャスト対象ユニットが選択される。以下、ブロードキャスト対象ユニットとして選択される通信ユニット１０１を選択ユニットと呼ぶ。ただし、選択ユニットは、ゲートウェイ１０２と隣接していない通信ユニットとする。ゲートウェイ１０２と隣接している通信ユニット１０１については、ゲートウェイ１０２から直接パケットが転送され、中継が不要であるためである。
（ｂ）ゲートウェイ１０２からのホップ数が最小となる通信ユニット１０１が、選択ユニットとされる。すなわち、経路情報に基づいて、最短ルート（最短経路）となる通信ユニット１０１が選択ユニットとされる。最短ルートを選択するのは、パケット転送による無線ネットワークの輻輳を抑制するためである。
（ｃ）選択ユニットは、他の選択ユニットではカバーできない隣接ユニットをより多く持つように決定される。すなわち、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数が最も多いユニットが選択ユニットとして選定される。
（ｄ）予め重なり合う選択ユニット数の上限(＝Ｎ)を決めておく。すなわち、各通信ユニット１０１の隣接ユニットに含まれる選択ユニットの上限数をＮとする。そして、ある通信ユニット１０１を選択しようとしたときに、その選択ユニットが隣接ユニットとして含まれる通信ユニット１０１において、上限数Ｎを超えたときには、その選択ユニットは選択しない。そして、非ブロードキャスト対象ユニットの隣接ユニットの中で、ブロードキャスト対象ユニットの重なりがＮを超える隣接ユニット数が少ない通信ユニット１０１が、ブロードキャスト対象ユニットとして選択される。これは、無線ネットワークの輻輳を抑制するためである。
【００１８】
ステップ４．
サーバは、ステップ３．で選択したブロードキャスト対象ユニット（選択ユニット）に対し、ブロードキャスト転送許可指示をユニキャストで通知する。
【００１９】
ステップ５．
サーバは、ステップ３．で選択したブロードキャスト対象ユニットに対し、ユニキャストあるいはブロードキャストでファームプログラムデータを転送する。ブロードキャストが実施される場合、ステップ４．で許可を受けていない非ブロードキャスト対象ユニットはブロードキャスト転送を行わず、許可を受けているブロードキャスト対象ユニットのみがブロードキャスト転送を実施する。ユニキャストが実施される場合、ブロードキャスト対象ユニットはまだブロードキャスト転送は実施せず、サーバからの許可指示を待つ。
【００２０】
ステップ６．
サーバは、ファームプログラムデータをユニキャストで転送した場合、ブロードキャスト対象ユニットに対し、ブロードキャスト開始指示を通知し、その開始指示を受けたブロードキャスト対象ユニットは、隣接する通信ユニット１０１へファームプログラムデータをブロードキャスト転送する。
【００２１】
上述の本実施形態の基本動作に基づく具体的な構成について、以下に説明する。
図３は、本実施形態が適用されるネットワーク構成図である。図３において、図２と同じ部分には、同じ番号を付してある。また、図２の場合と同様に、ブロードキャスト対象ユニットは黒い塗りつぶしのマーク、及び白い塗りつぶしに横線のマークで示されている。
【００２２】
サーバ３０１は、ＬＡＮ（ローカルエリアネットワーク）等を介して中継装置であるゲートウェイ（Ｇａｔｅｗａｙ）１０２と接続される。ゲートウェイ１０２は、サーバ３０１に対する通信情報を、無線ネットワークを介して各通信ユニット１０１との間で中継する。ゲートウェイ１０２と各通信ユニット１０１は、アドホックネットワークを構成する。
【００２３】
図４は、図３のゲートウェイ１０２の構成図である。ＬＡＮ等を介したサーバ３０１との通信は、Ｌ２ＳＷ（レイヤ２スイッチ）４０１によって終端される。無線通信による通信ユニット１０１との通信は、それぞれ通信ポートを備える複数の通信部４０３によって終端され、送受信フレームの符号化または復号の処理が実行される。この通信部４０３は例えば、ＰＨＹ（ＰＨＹｓｉｃａｌ  Ｌａｙｅｒ  Ｄｅｖｉｃｅ）によって構成される。Ｌ２ＳＷ４０１または通信ユニット１０１を介して送受信されるフレームデータは、アドホックＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）４０２にて処理される。ここでは、ルーティングテーブルに基づくフレームデータのルーティングの処理や、フレームデータ中の上位レイヤ情報をＣＰＵ４０４との間で通信する処理等が実行される。ＣＰＵ４０４は、ゲートウェイ１０２の全体の処理を制御するプロセッサであり、特には図示しないフラッシュメモリに記憶されたファームウェア４０５に基づいて基本動作が実行される。また、フラッシュメモリやディスク記憶装置に記憶されたミドルウェア４０６によって上位レイヤの処理を実行する。
【００２４】
図５は、図３の通信ユニット１０１の構成図である。通信ユニット１０１の構成は、図４のゲートウェイ１０２の構成に対して、ＬＡＮを終端するＬ２ＳＷ４０１の機能が無いだけで、その他の機能は同様である。図５において、アドホックＦＰＧＡ４０２と通信部４０３は、それぞれ図４のゲートウェイ１０２の場合と同じものを使用できる。また、ＣＰＵ５０１は、通信ユニット１０１の全体の処理を制御するプロセッサであり、特には図示しないフラッシュメモリに記憶されたファームウェア５０２に基づいて基本動作が実行される。また、フラッシュメモリやディスク記憶装置に記憶されたミドルウェア５０３によって上位レイヤの処理を実行する。本実施形態では、サーバ３０１からゲートウェイ１０２を経由して転送されるファームプログラムデータに基づいて、このファームウェア５０２が更新されることになる。
【００２５】
図６は、図４または図５のアドホックＦＰＧＡ４０２の構成図である。データ解析・制御部６０１は、図４のＬ２ＳＷ４０１や図４または図５の通信部４０３に対してデータ受信部６０２およびデータ送信部６０３が送受信するフレームデータを解析し、ルーティングや上位レイヤとの通信等を制御するフィールドプログラマブルゲートアレイである。
【００２６】
上述した実施形態の構成によって、サーバ３０１、ゲートウェイ１０２、通信ユニット１０１間で実行される本実施形態のブロードキャスト転送の第１の処理シーケンス例について、図７から図１０のシーケンス図を用いて説明する。
【００２７】
始めに、図３において、ゲートウェイ１０２は１台のみ記載されているが、サーバ３０１の配下には複数のゲートウェイ１０２を接続することができ、各ゲートウェイ１０２の配下にアドホック無線ネットワークで接続される通信ユニット１０１が配置される。各通信ユニット１０１の設置位置は固定であり、サーバ３０１にてその位置情報を管理する。なお、設置位置を変更できることはもちろんである。
シーケンスＳ１（図７）
【００２８】
サーバ３０１は、ブロードキャスト対象ユニットとしていくつかの通信ユニット１０１を選択する。通信ユニット１０１の選択方法の詳細について後述する。ここでは、一例として、図３中、通信ユニット１、通信ユニット３、通信ユニット４と記述されている通信ユニット１０１がブロードキャスト対象ユニットとしてサーバ３０１によって選択されたとする。これにより、図３中、通信ユニット２、通信ユニット５と記述されている通信ユニット１０１は、非ブロードキャスト対象ユニットとなる。もちろんこれは一例であり、他の構成例であってもよい。以下の説明では、通信ユニット１から５の表記で説明する。
シーケンスＳ２〜Ｓ６（図７）
サーバ３０１からゲートウェイ（Ｇａｔｅｗａｙ）１０２経由で、図３中の通信ユニット１，３，４に対し、ブロードキャスト転送許可指示が通知される（図７のＳ２およびＳ３）。
【００２９】
これ以後、図３中の通信ユニット１，３，４がブロードキャスト対象ユニットとしてブロードキャスト転送を実施し、図３中の通信ユニット２，５は非ブロードキャスト対象ユニットとしてブロードキャスト転送は行わないことになる（図７のＳ４）。
【００３０】
ブロードキャスト転送許可指示によって転送許可指示を受けた通信ユニット１，３，４は、ブロードキャスト転送許可指示応答を、ゲートウェイ１０２を介してサーバ３０１に返信する（図７のＳ５およびＳ６）。
【００３１】
シーケンスＳ７（図７）
サーバ３０１がゲートウェイ１０２に、ファームの更新対象となるファームプログラムデータを、ＦＴＰ（ファイル転送プロトコル）を用いて配信する。
【００３２】
シーケンスＳ８（図７）
サーバ３０１がゲートウェイ１０２に、通信ユニットファーム更新開始指示を送信する。
【００３３】
シーケンスＳ９，Ｓ１０（図７，図８）
ゲートウェイ１０２は、ＦＴＰによって転送されたファームプログラムデータを、アドホック通信用フォーマットに変換する（図７のＳ９）。そして、ゲートウェイ１０２は、変換したファームプログラムデータを、各通信ユニット１〜５へブロードキャスト転送する（図８のＳ１０）。
【００３４】
シーケンスＳ１１，Ｓ１２（図８）
各通信ユニット１０１は、ブロードキャスト転送されたファームプログラムデータを受信し、内部のフラッシュメモリに格納する（図５の５０２参照）（図８のＳ１１）。
【００３５】
ここで、図７のシーケンスＳ３によりブロードキャスト転送許可指示を受けた通信ユニット１，３，４は、受信したファームプログラムデータを、ブロードキャスト転送する（図８のＳ１２）。なお、通信ユニット４は、通信ユニット１を経由して第２ホップでファームプログラムデータを受信し、それをブロードキャスト転送する（図８のＳ１０′）。また、図８の例では、通信ユニット５も、通信ユニット１を経由して第２ホップでファームプログラムデータを転送されるが、受信に失敗している例が示されている（図８のＳ１０−３）
【００３６】
シーケンスＳ１３，Ｓ１４（図９）
ゲートウェイ１０２は、ファームプログラムデータ受信結果問合せ要求を、各通信ユニット１〜５へブロードキャスト転送する。図７のシーケンスＳ３によりブロードキャスト転送許可指示を受けた通信ユニット１，３，４のみが、受信した問合せ要求を、ブロードキャスト転送する（図９のＳ１４）。通信ユニット４と５は、通信ユニット１を経由して第２ホップで問合せ要求を受信する。
【００３７】
シーケンスＳ１５等（図９）
ファームプログラムデータ受信結果問合せ要求を受信した通信ユニットは、ファームプログラムデータの受信状態を判定し、正常に受信完了していれば何もしない。受信状態が異常であれば、ファームプログラムデータ受信異常通知をＧＷへ返信する（例えば図９のＳ１５）。
【００３８】
シーケンスＳ１６（図１０）
ゲートウェイ１０２は、ファームプログラムデータ受信異常通知（図９のＳ１５等）を受信すると、受信異常となった通信ユニット（例えば通信ユニット５）に対し、ユニキャストでファームプログラムデータを送信する。
【００３９】
シーケンスＳ１７（図１０）
ゲートウェイ１０２は、ファームプログラムデータ受信結果問合せ要求を、対象となる通信ユニット５へ、ユニキャストで送信する。
【００４０】
シーケンスＳ１８（図１０）
ファームプログラムデータ受信結果問合せ要求を受信した通信ユニット５は、ファームプログラムデータの受信状態を判定し、正常に受信完了していればファームプログラムデータ受信完了通知を、受信状態が異常であれば、ファームプログラムデータ受信異常通知をゲートウェイ１０２へ返信する。
【００４１】
シーケンスＳ１７に対するＳ１８で異常が通知された場合は、シーケンスＳ１６からＳ１８までを、数回繰り返す。
【００４２】
シーケンスＳ１９（図１０）
各通信ユニット１〜５は、新ファームプログラムデータを受信してから一定時間後に、自律的に新ファームプログラムデータで再起動する。
【００４３】
シーケンスＳ２０（図１０）
ゲートウェイ１０２は、ファームプログラムバージョン問合せ要求を、各通信ユニット１〜５へブロードキャスト転送する。通信ユニット４と５は、通信ユニット１を経由して第２ホップで問合せ要求を受信する。
【００４４】
シーケンスＳ２１（図１０）
各通信ユニット１〜５は、ファームプログラムバージョン問合せ要求を受信すると、自身が実行しているファームプログラムデータのバージョンを、ゲートウェイ１０２に通知する。
【００４５】
シーケンスＳ２２（図１０）
ゲートウェイ１０２は、各通信ユニット１〜５より、ファームプログラムバージョン通知を受信した結果、バージョンが古い通信ユニット１０１が存在した場合には、シーケンスＳ１６からＳ１８により、再度ファームプログラムデータをユニキャスト送信する。
【００４６】
シーケンスＳ２３，Ｓ２４（図１０）
ゲートウェイ１０２は、全ての通信ユニット１０１に対するファームプログラムデータのバージョンアップを完了後、ファーム更新完了通知をサーバ３０１に送信する（図１０のＳ２３）。これに対して、サーバ３０１からゲートウェイ１０２に、ファーム更新完了応答が返信されて（図１０のＳ２４）、ファーム更新処理が完了する。
【００４７】
図１１は、図７のＳ２およびＳ３に示すブロードキャスト転送許可指示のメッセージフォーマットのデータ構成を示す。ユニットＩＤは、各通信ユニット１０１個別のＩＤ（識別データ）である。また、ブロードキャスト転送許可指示は、値０で転送禁止を指示し、値１で転送許可を指示する。今、シーケンスＳ１で選択された通信ユニット１，３，４に対しては、値１のブロードキャスト転送許可指示が通知される。
【００４８】
次に、本実施形態のブロードキャスト転送の第２の処理シーケンス例について、図１２から図１５のシーケンス図を用いて説明する。図１２から図１５で、図７から図１０の第１の処理シーケンス例と同じ処理のシーケンスは、同じシーケンス番号を付してある。図１２、図１４、図１５の処理シーケンスは、それぞれ図７、図９、図１０と同じである。
【００４９】
第１の処理シーケンス例における図８では、ゲートウェイ１０２から各通信ユニット１０１へのファームプログラムデータの送信は、ブロードキャスト転送によって行われていた（図８のＳ１０）。そして、図７のシーケンスＳ３によりブロードキャスト転送許可指示を受けた通信ユニット１，３，４は、ブロードキャスト転送によって受信したファームプログラムデータを、自律的にブロードキャスト転送していた（図８のＳ１２）。
【００５０】
これに対して、第２の処理シーケンス例における図１３では、ゲートウェイ１０２から各通信ユニット１０１へのファームプログラムデータの送信は、個別のユニキャスト送信によって実行される（図１３のＳ２５）。そして、図１２のシーケンスＳ３によりブロードキャスト転送許可指示を受けた通信ユニット１，３，４は、さらにゲートウェイ１０２からのユニキャスト送信によるブロードキャスト開始指示を待ってから、受信したファームプログラムデータをブロードキャスト転送する（図１３のＳ２６→Ｓ１２）。これにより、ファームプログラムデータのブロードキャスト対象ユニットへの確実な送信が実現される。
【００５１】
次に、前述したステップ１．およびステップ２．の前提のもとで、ステップ３．の（ａ）から（ｄ）のアルゴリズムによりブロードキャスト対象ユニットを選択する処理の具体例について、図１６から図３０の説明図を用いて説明する。
【００５２】
ステップ１．で前述したように、図３のサーバ３０１は、図３のゲートウェイ１０２を含む図３の各通信ユニット１０１からの通知に基づいて、各通信ユニット１０１及びゲートウェイ１０２毎に、隣接ユニット情報と経路情報を管理する。図１６（ａ）は、サーバ３０１が管理する隣接ユニット・経路情報の例を示す表である。この表で示される情報は、サーバ３０１が各通信ユニット１０１又はＧＷ１０２との間で通信する隣接ユニット情報及び経路情報とに基づいて作成される。各行左端が、管理するゲートウェイ１０２（図中「ＧＷ」）または通信ユニット１０１（図中「ユニット」）を示している。左端を除く各行の数字またはＧＷ（ゲートウェイ１０２を示す）が、左端の通信ユニット１０１またはゲートウェイ１０２に隣接する通信ユニット１０１またはゲートウェイ１０２の番号等を示している。例えば、番号１の通信ユニット１０１の隣接ユニットは、ゲートウェイ１０２（ＧＷ）、および番号が２，１４，２１，２３，２４，２５、２７，３０，３４，３５の通信ユニット１０１であることが記憶されている。また、各隣接ユニット番号をたどることにより、各通信ユニット１０１間の経路を決定することができる。
【００５３】
図１６（ｂ）は、ゲートウェイ１０２（図中「ＧＷ」）と各通信ユニット１０１（図中の数字）の位置関係を示す図である。ゲートウェイ１０２が中央に配置され、通信ユニット１０１の数が４０である場合の一例が示されている。
【００５４】
図１６の例において、前述したステップ３．の（ａ）から（ｄ）の選択アルゴリズムによりブロードキャスト対象ユニットを選択する処理の例について以下に説明する。
【００５５】
＜実施例１＞
まず、隣接ユニット数が最も少ない通信ユニット１０１をピックアップする。ステップ３．の（ａ）により、図１６（ａ）の隣接ユニット・経路情報を参照した結果、隣接ユニットが最も少ない通信ユニット１０１は、１１番のユニットであると判定される。
【００５６】
次に、隣接ユニットが最も少なく選択ユニットを含まない１１番のユニットからＧＷ１０２に向けて経路を確立できるまで、順次隣接ユニットがたどられる。
まず、１１番の隣接ユニットは、図１６（ａ）より、１３番と１５番のユニットである。１３番の隣接ユニットは２つ、１５番の隣接ユニット３つである。ここで、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。１１番のユニットへのルートは、図１６（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→２６→１５→１１
Ｎｏ．２  ＧＷ→２６→１５→１３→１１
Ｎｏ．３  ＧＷ→３４→２６→１５→１１
等がある。ＧＷはゲートウェイ１０２を示し、各番号は各通信ユニット１０１の識別番号を示すものとする。ここで、最短ルートはＮｏ．１の１つしかないため、１５番のユニットを選択ユニットとして選定する。なお、もし最短ルート数が複数ある場合は、ステップ３．の（ｂ）により、最短ルートを選ぶ。
【００５７】
次に、新たに選定された１５番の選択ユニットについて、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。１５番のユニットの隣接ユニットは３つであり、１１番と１３番と２６番である。１５番のユニットへのルートは、図１６（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→２６→１５
Ｎｏ．２  ＧＷ→２３→２６→１５
Ｎｏ．３  ＧＷ→３４→２６→１５
等があるが、最短ルートはＮｏ．１の１つしかないため、２６番のユニットを選択ユニットとして選定する。もし最短ルート数が複数ある場合は、ステップ３．の（ｂ）により、最短ルートを選ぶ。
【００５８】
２６番のユニットはＧＷ１０２の隣接ユニットであり、隣接ユニットが最も少なく選択ユニットを含まない１１番のユニットからＧＷ１０２までの経路が確立できたため、１１番のユニットに対する処理を終了する。
【００５９】
サーバ３０１で実行される実施例１の選択処理により、１５番と２６番のユニットがブロードキャスト対象ユニットとして選択される。この結果、１１番のユニットへは、ＧＷ→２６→１５→１１というルートで、ブロードキャストパケットが転送されることになる。
【００６０】
また、図１６（ｂ）に示されるＧＷ１０２と各通信ユニット１０１との位置関係において、実施例１の選択処理で選択された１５番と２６番の選択ユニットによってカバーされるユニットは、図１７（ｂ）の２つの破線の円で示される範囲内に入るユニットとなる。ここで、選択ユニットによりカバーされるユニットとは、ブロードキャスト対象ユニットとして選択されたユニットから更にブロードキャスト転送される範囲のユニットを示す。
【００６１】
実施例１の選択処理により、図１６（ａ）の隣接ユニット・経路情報は、図１７（ａ）に示されるようになる。図１７（ａ）において、左端のユニット番号およびそれに対応する隣接ユニット番号に対して、隣接ユニットが一番少ないユニット（図中実線の四角）、選択アルゴリズムにより選択されたユニット（図中二重実線の四角）、および選択ユニットによりカバーされるユニット（図中破線の四角）に、それぞれ個別のマーク情報が付与される。
【００６２】
さらに、実施例１の選択処理が終了した時点で、図１８に示されるように、各通信ユニット１０１に隣接する選択ユニット情報が管理される。図１８においても、左端の各ユニット番号に対して、隣接ユニットが一番少ないユニット（図中実線の四角）、選択アルゴリズムにより選択されたユニット（図中二重実線の四角）、および選択ユニットによりカバーされるユニット（図中破線の四角）に、それぞれ図１７（ａ）の場合と同様の個別のマーク情報が付与される。
【００６３】
＜実施例２＞
上述の実施例１の選択処理に続いて、更に以下の実施例２の選択処理が実行される。ここでは、以前に選択されたユニットの隣接ユニットを除いて考える。
【００６４】
まず、隣接ユニット数が最も少ない通信ユニット１０１をピックアップする。ステップ３．の（ａ）により、図１７（ａ）の隣接ユニット・経路情報を参照した結果、隣接ユニットが最も少ない通信ユニット１０１は、７番のユニットであると判定される。
【００６５】
次に、隣接ユニットが最も少なく選択ユニットを含まない７番のユニットからＧＷ１０２に向けて経路を確立できるまで、順次隣接ユニットがたどられる。
まず、７番の隣接ユニットは、図１７（ａ）より、６番と１４番と２５番の３つのユニットである。ここで、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。７番のユニットへのルートは、図１７（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→１→２５→７
Ｎｏ．２  ＧＷ→１→１４→７
Ｎｏ．３  ＧＷ→３４→１→２５→７
Ｎｏ．４  ＧＷ→１→２５→１４→７
等があるが、最短ルートはＮｏ．１とＮｏ．２の２ルートとなる。
【００６６】
最短ルートが複数ある場合は、ステップ３．の（ｃ）を適用する。上記２ルートにおける、７番のユニットと隣接するユニットは１４番と２５番である。このうち、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数が最も多いのは、２５番のユニットの７個である。
【００６７】
ここでさらに、ステップ３．の（ｄ）を適用する。図１８の各通信ユニット１０１に隣接する選択ユニット情報がチェックされることにより、２５番の新たな選択ユニットを加えたときに、隣接ユニット中の選択ユニットの数がＮ個（例えば４個）を超えるユニットがあるか否かが判定される。２５番の隣接ユニットは、図１７（ａ）の隣接ユニット・経路情報より、１，２，６，７，１４，２７，３０番のユニットである。図１８において、これらのユニットに２５番のユニットを隣接ユニットとして新たに加えても、Ｎ＝４個を超えるものは出現しない。
以上より、２５番のユニットが選択ユニットとして選定される。
【００６８】
続いて、新たに選定された２５番の選択ユニットについて、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。２５番のユニットへのルートは、図１７（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→１→２５
Ｎｏ．２  ＧＷ→２４→１→２５
Ｎｏ．３  ＧＷ→３４→１→２５
等があるが、最短ルートはＮｏ．１の１つしかないため、１番ユニットを選択ユニットとして選定する。
【００６９】
１番のユニットはＧＷ１０２の隣接ユニットであり、隣接ユニットが最も少なく選択ユニットを含まない７番のユニットからＧＷ１０２までの経路が確立できたため、７番のユニットに対する処理を終了する。
【００７０】
サーバ３０１で実行される実施例２の選択処理により、１番と２５番のユニットがブロードキャスト対象ユニットとして選択される。この結果、７番のユニットへは、ＧＷ→１→２５→７というルートで、ブロードキャストパケットが転送されることになる。
【００７１】
また、実施例２の選択処理で選択された１番と２５番の選択ユニットによってカバーされるユニットは、図１９（ｂ）の２つの破線の円で示される範囲内に入るユニットとなる。なお、実線の円は、実施例１の選択処理によって選択された選択ユニットによってカバーされる範囲である。
【００７２】
実施例２の選択処理により、図１７（ａ）の隣接ユニット・経路情報は、図１９（ａ）に示されるように更新される。図１９（ａ）において、左端のユニット番号およびそれに対応する隣接ユニット番号に対して、図１７（ａ）の場合と同様に、隣接ユニットが一番少ないユニット、選択アルゴリズムにより選択されたユニット、および選択ユニットによりカバーされるユニットに、それぞれ個別のマーク情報が付与される。さらに、図１９（ａ）においては、以前に（ここでは実施例１で）選定された選択ユニットの隣接ユニット（図中破線の斜線の四角）についても、マークが付与される。
【００７３】
さらに、実施例２の選択処理が終了した時点で管理されている、各通信ユニット１０１に隣接する選択ユニット情報は、図１８から図２０に示されるように更新される。図１８においても、左端の各ユニット番号に対して、隣接ユニットが一番少ないユニット（図中実線の四角）、選択アルゴリズムにより選択されたユニット（図中二重実線の四角）、および選択ユニットによりカバーされるユニット（図中破線の四角）に、それぞれ図１７（ａ）の場合と同様の個別のマーク情報が付与される。さらに、図２０においては、以前に（ここでは実施例１で）選定された選択ユニットの隣接ユニット（図中破線の斜線の四角）についても、マークが付与される。
【００７４】
＜実施例３＞
上述の実施例２の選択処理に続いて、更に以下の実施例３の選択処理が実行される。ここでは、以前に選択されたユニットの隣接ユニットを除いて考える。
【００７５】
まず、隣接ユニット数が最も少ない通信ユニット１０１をピックアップする。ステップ３．の（ａ）により、図１９（ａ）の隣接ユニット・経路情報を参照した結果、隣接ユニットが最も少ない通信ユニット１０１は、２０番のユニットであると判定される。
【００７６】
次に、隣接ユニットが最も少なく選択ユニットを含まない２０番のユニットからＧＷ１０２に向けて経路を確立できるまで、順次隣接ユニットがたどられる。
２０番の隣接ユニットは、図１９（ａ）より、５，１０，１８番の３つのユニットである。ここで、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。２０番のユニットへのルートは、図１９（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→８→５→２０
Ｎｏ．２  ＧＷ→９→５→２０
Ｎｏ．３  ＧＷ→８→１０→２０
Ｎｏ．４  ＧＷ→９→１８→２０
等があるが、最短ルートを通る隣接ユニットは、５，１０，１８番の３ユニットとなる。
【００７７】
最短ルート数が複数ある場合は、ステップ３．の（ｃ）を適用する。上記３ユニットにおける、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数は、図１９（ａ）よりそれぞれ、
ユニット５番：８個
ユニット１０番：４個
ユニット１８番：５個
となる。従って、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数が最も多いのは、５番のユニットである。
【００７８】
ここでさらに、ステップ３．の（ｄ）を適用する。図２０の各通信ユニット１０１に隣接する選択ユニット情報がチェックされることにより、５番の新たな選択ユニットを加えたときに、隣接ユニット中の選択ユニットの数がＮ個（例えば４個）を超えるユニットがあるか否かが判定される。５番の隣接ユニットは、図１９（ａ）の隣接ユニット・経路情報より、８，９，１０，１６，１９，２０，３１，３６番のユニットである。図２０において、これらのユニットに５番のユニットを隣接ユニットとして新たに加えても、Ｎ＝４個を超えるものは出現しない。
以上より、５番のユニットが選択ユニットとして選定される。
【００７９】
続いて、新たに選定された５番の選択ユニットについて、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。５番のユニットへのルートは、図１９（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→８→５
Ｎｏ．２  ＧＷ→９→５
Ｎｏ．３  ＧＷ→３３→９→５
Ｎｏ．４  ＧＷ→３３→８→５
等があるが、最短ルートを通る隣接ユニットは、８，９番の２ユニットとなる。
【００８０】
最短ルートが複数ある場合は、ステップ３．の（ｃ）を適用する。上記２ユニットにおける、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数はそれぞれ、
ユニット８番：１０個
ユニット９番：７個
となる。従って、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数が最も多いのは、８番のユニットである。
【００８１】
ここでさらに、ステップ３．の（ｄ）を適用する。図２０の各通信ユニット１０１に隣接する選択ユニット情報に上述の５番のユニットの情報を加えたものがチェックされることにより、８番の新たな選択ユニットを加えたときに、隣接ユニット中の選択ユニットの数がＮ個（例えば４個）を超えるユニットがあるか否かが判定される。８番の隣接ユニットは、図１９（ａ）の隣接ユニット・経路情報より、３，５，９，１０，１２，１６，１９，２８，３１，３３，３６番のユニットである。これらのユニットに８番のユニットを隣接ユニットとして新たに加えても、Ｎ＝４個を超えるものは出現しない。
【００８２】
以上より、８番のユニットが選択ユニットとして選定される。
８番のユニットはＧＷ１０２の隣接ユニットであり、隣接ユニットが最も少なく選択ユニットを含まない２０番のユニットからＧＷ１０２までの経路が確立できたため、２０番のユニットに対する処理を終了する。
【００８３】
サーバ３０１で実行される実施例３の選択処理により、５番と８番のユニットがブロードキャスト対象ユニットとして選択される。この結果、２０番のユニットへは、ＧＷ→８→５→２０というルートで、ブロードキャストパケットが転送されることになる。
【００８４】
また、実施例３の選択処理で選択された５番と８番の選択ユニットによってカバーされるユニットは、図２１（ｂ）の２つの破線の円で示される範囲内に入るユニットとなる。なお、実線の円は、実施例２までの選択処理によって選択された選択ユニットによってカバーされる範囲である。
【００８５】
実施例３の選択処理により、図１９（ａ）の隣接ユニット・経路情報は、図２１（ａ）に示されるように更新される。
さらに、実施例３の選択処理が終了した時点で管理されている、各通信ユニット１０１に隣接する選択ユニット情報は、図２０から図２２に示されるように更新される。
【００８６】
図２１（ａ）及び図２２において、付与される各マークの意味は、図１９（ａ）及び図２０等の場合と同様である。
【００８７】
＜実施例４＞
上述の実施例３の選択処理に続いて、更に以下の実施例４の選択処理が実行される。ここでは、以前に選択されたユニットの隣接ユニットを除いて考える。
【００８８】
まず、隣接ユニット数が最も少ない通信ユニット１０１をピックアップする。ステップ３．の（ａ）により、図２１（ａ）の隣接ユニット・経路情報を参照した結果、隣接ユニットが最も少ない通信ユニット１０１は、２２番のユニットであると判定される。
【００８９】
次に、隣接ユニットが最も少なく選択ユニットを含まない２２番のユニットからＧＷ１０２に向けて経路を確立できるまで、順次隣接ユニットがたどられる。
２２番の隣接ユニットは、図２１（ａ）より、１７，３８，４０番の３つのユニットである。ここで、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。２２番のユニットへのルートは、図２１（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→１７→２２
Ｎｏ．２  ＧＷ→１７→３８→２２
Ｎｏ．３  ＧＷ→２１→１７→２２
等があるが、最短ルートを通る隣接ユニットは、１７番のユニットのみである。
【００９０】
ここでさらに、ステップ３．の（ｄ）を適用する。図２２の各通信ユニット１０１に隣接する選択ユニット情報がチェックされることにより、１７番の新たな選択ユニットを加えたときに、隣接ユニット中の選択ユニットの数がＮ個（例えば４個）を超えるユニットがあるか否かが判定される。１７番の隣接ユニットは、図２１（ａ）の隣接ユニット・経路情報より、３，１２，１６，１９，２１，２２，２４，２８，３２，３４，３７，３８，４０番のユニットである。図２２において、これらのユニットに１７番のユニットを隣接ユニットとして新たに加えても、Ｎ＝４個を超えるものは出現しない。
【００９１】
以上より、１７番のユニットが選択ユニットとして選定される。
１７番のユニットはＧＷ１０２の隣接ユニットであり、隣接ユニットが最も少なく選択ユニットを含まない２２番のユニットからＧＷ１０２までの経路が確立できたため、２２番のユニットに対する処理を終了する。
【００９２】
サーバ３０１で実行される実施例４の選択処理により、１７番のユニットがブロードキャスト対象ユニットとして選択される。この結果、２２番のユニットへは、ＧＷ→１７→２２というルートで、ブロードキャストパケットが転送されることになる。
【００９３】
また、実施例４の選択処理で選択された１７番の選択ユニットによってカバーされるユニットは、図２３（ｂ）の１つの破線の円で示される範囲内に入るユニットとなる。なお、実線の円は、実施例３までの選択処理によって選択された選択ユニットによってカバーされる範囲である。
【００９４】
実施例４の選択処理により、図２１（ａ）の隣接ユニット・経路情報は、図２３（ａ）に示されるように更新される。
さらに、実施例４の選択処理が終了した時点で管理されている、各通信ユニット１０１に隣接する選択ユニット情報は、図２２から図２４に示されるように更新される。
【００９５】
図２３（ａ）及び図２４において、付与される各マークの意味は、図２１（ａ）及び図２２等の場合と同様である。
【００９６】
＜実施例５＞
上述の実施例４の選択処理に続いて、更に以下の実施例５の選択処理が実行される。ここでは、以前に選択されたユニットの隣接ユニットを除いて考える。
【００９７】
まず、隣接ユニット数が最も少ない通信ユニット１０１をピックアップする。ステップ３．の（ａ）により、図２３（ａ）の隣接ユニット・経路情報を参照した結果、隣接ユニットが最も少ない通信ユニット１０１は、３９番のユニットであると判定される。
【００９８】
次に、隣接ユニットが最も少なく選択ユニットを含まない３９番のユニットからＧＷ１０２に向けて経路を確立できるまで、順次隣接ユニットがたどられる。
３９番の隣接ユニットは、図２３（ａ）より、９，１８，３１，３３番の４つのユニットである。ここで、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。３９番のユニットへのルートは、図２３（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→９→３９
Ｎｏ．２  ＧＷ→３３→３９
Ｎｏ．３  ＧＷ→３３→３１→３９
等があるが、最短ルートを通る隣接ユニットは、９番と３３番の２ユニットとなる。
【００９９】
最短ルート数が複数ある場合は、ステップ３．の（ｃ）を適用する。９番と３３番のユニットのうち、選択ユニットと隣接していない隣接ユニット数はそれぞれ、２個（１８番と３９番）および１個（３９番）である。従って、選択ユニットと隣接していない隣接ユニット数が多いのは９番のユニットである。
【０１００】
ここでさらに、ステップ３．の（ｄ）を適用する。図２４の各通信ユニット１０１に隣接する選択ユニット情報がチェックされることにより、９番の新たな選択ユニットを加えたときに、隣接ユニット中の選択ユニットの数がＮ個（例えば４個）を超えるユニットがあるか否かが判定される。９番の隣接ユニットは、図２３（ａ）の隣接ユニット・経路情報より、５，８，１６，１８，１９，３１，３３，３９番のユニットである。図２４において、これらのユニットに９番のユニットを隣接ユニットとして新たに加えても、Ｎ＝４個を超えるものは出現しない。
【０１０１】
以上より、９番のユニットが選択ユニットとして選定される。
９番のユニットはＧＷ１０２の隣接ユニットであり、隣接ユニットが最も少なく選択ユニットを含まない３９番のユニットからＧＷ１０２までの経路が確立できたため、３９番のユニットに対する処理を終了する。
【０１０２】
サーバ３０１で実行される実施例５の選択処理により、９番のユニットがブロードキャスト対象ユニットとして選択される。この結果、３９番のユニットへは、ＧＷ→９→３９というルートで、ブロードキャストパケットが転送されることになる。
【０１０３】
また、実施例５の選択処理で選択された９番の選択ユニットによってカバーされるユニットは、図２５（ｂ）の１つの破線の円で示される範囲内に入るユニットとなる。なお、実線の円は、実施例４までの選択処理によって選択された選択ユニットによってカバーされる範囲である。
【０１０４】
実施例５の選択処理により、図２３（ａ）の隣接ユニット・経路情報は、図２５（ａ）に示されるように更新される。
さらに、実施例５の選択処理が終了した時点で管理されている、各通信ユニット１０１に隣接する選択ユニット情報は、図２４から図２６に示されるように更新される。
【０１０５】
図２５（ａ）及び図２６において、付与される各マークの意味は、図２３（ａ）及び図２４等の場合と同様である。
【０１０６】
＜実施例６＞
上述の実施例５の選択処理に続いて、更に以下の実施例６の選択処理が実行される。ここでは、以前に選択されたユニットの隣接ユニットを除いて考える。
【０１０７】
まず、隣接ユニット数が最も少ない通信ユニット１０１をピックアップする。ステップ３．の（ａ）により、図２５（ａ）の隣接ユニット・経路情報を参照した結果、隣接ユニットが最も少ない通信ユニット１０１は、２９番のユニットであると判定される。
【０１０８】
次に、隣接ユニットが最も少なく選択ユニットを含まない２９番のユニットからＧＷ１０２に向けて経路を確立できるまで、順次隣接ユニットがたどられる。
２９番の隣接ユニットは、図２５（ａ）より、４，３２，３７，３８，４０番の５つのユニットである。ここで、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。２９番のユニットへのルートは、図２５（ａ）の隣接ユニット・経路情報より、
Ｎｏ．１  ＧＷ→１７→４０→２９
Ｎｏ．２  ＧＷ→１７→３７→２９
Ｎｏ．３  ＧＷ→３→３７→２９
Ｎｏ．４  ＧＷ→３→４０→２９
Ｎｏ．５  ＧＷ→１７→３８→２９
Ｎｏ．６  ＧＷ→１７→３２→２９
等があるが、最短ルートを通る隣接ユニットは、３２，３７，３８，４０番の４ユニットとなる。
【０１０９】
最短ルート数が複数ある場合は、ステップ３．の（ｃ）を適用する。上記４ユニットの各隣接ユニットのうち、選択ユニットと隣接していない隣接ユニットは４番であり、この４番のユニットを隣接ユニットにもつのは、３２，３７，４０番の３つのユニットである。そして、これらのユニットの各隣接ユニット数はそれぞれ、
３２番の隣接ユニット数は１１個。
３７番の隣接ユニット数は８個。
４０番の隣接ユニット数は９個。
となって、３２番のユニットが最も隣接ユニット数が多い。
【０１１０】
ここでさらに、ステップ３．の（ｄ）を適用する。図２６の各通信ユニット１０１に隣接する選択ユニット情報がチェックされることにより、３２番の新たな選択ユニットを加えたときに、隣接ユニット中の選択ユニットの数がＮ個（例えば４個）を超えるユニットがあるか否かが判定される。３２番の隣接ユニットは、図２５（ａ）の隣接ユニット・経路情報より、３，４，１２，１６，１７，１９，２８，２９，３７，３８，４０番のユニットである。図２６において、これらのユニットに３２番のユニットを隣接ユニットとして新たに加えると、Ｎ＝４個を超えるものとして、１６番と１９番のユニットが出現する。従って、３２番のユニットは選択ユニットとして選定されない。
【０１１１】
次に、２番目に多い隣接ユニット数を持つ４０番のユニットについて、ステップ３．の（ｄ）を適用する。図２６の各通信ユニット１０１に隣接する選択ユニット情報がチェックされることにより、４０番の新たな選択ユニットを加えたときに、隣接ユニット中の選択ユニットの数がＮ個（例えば４個）を超えるユニットがあるか否かが判定される。４０番の隣接ユニットは、図２５（ａ）の隣接ユニット・経路情報より、３，４，１７，２２，２８，２９，３２，３７，３８番のユニットである。図２６において、これらのユニットに４０番のユニットを隣接ユニットとして新たに加えても、Ｎ＝４個を超えるものは出現しない。
以上より、４０番のユニットが選択ユニットとして選定される。
【０１１２】
続いて、新たに選定された４０番の選択ユニットについて、ステップ３．の（ｂ）により、最短ルート上の隣接ユニットを選ぶ。図２５（ａ）の隣接ユニット・経路情報より、４０番のユニットへのルートのうちの最短ルート上に位置する隣接ユニットは、
Ｎｏ．１  ＧＷ→１７→４０
Ｎｏ．２  ＧＷ→３→４０
より、１７番と３番の２ユニットとなる。ここでさらに、図２６の各通信ユニット１０１に隣接する選択ユニット情報より、１７番のユニットは、実施例４により経路が確立できている。このため、隣接ユニットが最も少なく選択ユニットを含まない２９番のユニットからＧＷ１０２までの経路が確立できたため、２９番のユニットに対する処理を終了する。
【０１１３】
サーバ３０１で実行される実施例３の選択処理により、４０番のユニットがブロードキャスト対象ユニットとして選択される。この結果、実施例４でされた１７番のユニットと合わせて、ＧＷ→１７→４０→２９というルートで、ブロードキャストパケットが転送されることになる。
【０１１４】
また、実施例６の選択処理で選択された４０番の選択ユニットによってカバーされるユニットは、図２７（ｂ）の１つの破線の円で示される範囲内に入るユニットとなる。なお、実線の円は、実施例５までの選択処理によって選択された選択ユニットによってカバーされる範囲である。
【０１１５】
実施例６の選択処理により、図２５（ａ）の隣接ユニット・経路情報は、図２７（ａ）に示されるように更新される。
さらに、実施例６の選択処理が終了した時点で管理されている、各通信ユニット１０１に隣接する選択ユニット情報は、図２６から図２８に示されるように更新される。
【０１１６】
図２７（ａ）及び図２８において、付与される各マークの意味は、図２５（ａ）及び図２６等の場合と同様である。
【０１１７】
＜最終結果＞
以上の実施例１から６の選択処理によって、図１６に示される全てのユニットについて、各ユニットの隣接ユニットに必ず選択ユニットが含まれるようになる。これにより、選択ユニットの選定処理が終了する
【０１１８】
最終的に選定された選択ユニットは、図２７（ａ）を更新して最終結果として得られる図２９（ａ）の隣接ユニット・経路情報から、１，５，８，９，１５，１７，２５，２６，４０番の９個のユニットとなる。非選択ユニットは、この９個の選択ユニット以外の全てのユニットとなる。
【０１１９】
そして、これら９個のユニットによってカバーされるユニットは、図２７（ｂ）を更新して最終結果として得られる図２９（ｂ）の９個の実線の円で示される範囲内に入るユニットとなる。
【０１２０】
さらに、各通信ユニット１０１に隣接する選択ユニット情報は、図２８を更新して図３０に示されるようになる。
全ての非選択ユニットは、図２９（ａ）、（ｂ）及び図３０より明らかのように、９個の選択ユニットのいずれかの隣接ユニットとなる。
【０１２１】
図３１は、上述の選択ユニットの選定処理を実現するために図３のサーバ３０１が実行する処理を示すフローチャートである。この動作フローチャートは、例えば後述する図３４のハードウェア構成を有するサーバ３０１において、メモリ３４０２や外部記憶装置３４０５に記憶された制御プログラムを、ＣＰＵ３４０１が実行することで実現される。
【０１２２】
まず、選択ユニットの選定処理は、図３１のステップＳ３１０１からＳ３１０７の繰返し処理によって、例えば前述した図１６に示される全てのユニットについて、各ユニットの隣接ユニットに必ず選択ユニットが含まれるようになるまで繰り返し実行される。全てのユニットについて、各ユニットの隣接ユニットに必ず選択ユニットが含まれるようになった時点で、例えば前述した図２９および図３０に示される最終結果が得られる。
【０１２３】
ステップＳ３１０１からＳ３１０７の繰返し処理においてはまず、選択ユニットが隣接ユニットに無いユニットの中で、一番隣接数が少ないユニットが抽出される（図３１のステップＳ３１０２）。これは、前述したステップ３．の（ａ）のアルゴリズムに対応する処理である。この処理で例えば、前述の実施例１で１１番（図１７（ａ））、実施例２で７番（図１９（ａ））、実施例３で２０番（図２１（ａ））、実施例４で２２番（図２３（ａ））、実施例５で３９番（図２５（ａ））、実施例６で２９番の通信ユニット１０１が抽出される。いま、このようにして抽出された通信ユニット１０１を、ユニットＡとする。
【０１２４】
次に、図３１のステップＳ３１０３からＳ３１０６までの繰返し処理により、ユニットＡからＧＷ１０２まで、経路を確立できるまで、ブロードキャスト対象ユニットの選択処理が実行される（図３１のステップＳ３１０４）。この選択処理は、ユニットＡからＧＷ１０２に向けて、経路情報を参照しながら隣接ユニットを順次たどる処理である。ユニットＡをスタートとして順次たどられる隣接ユニットを選定処理対象ユニットＹとする。
【０１２５】
そして、ステップＳ３１０４でブロードキャスト対象ユニットが選択ユニットとして選定されるごとに、そのユニットが既に選定されたユニットでなければ、さらにＧＷ１０２に向けて隣接ユニット（選定処理対象ユニットＹ）がたどられる（図３１のステップＳ３１０５の判定がＮＯ）。
【０１２６】
一方、ステップＳ３１０４で選定された選択ユニットが既に選定されたユニットならば、現在のユニットＡについてＧＷ１０２に向けて隣接ユニットをたどる処理が終了する（図３１のステップＳ３１０５の判定がＹＥＳ）。そして、ステップＳ３１０１からＳ３１０７の次の繰返し処理に移動して、次に一番隣接数が少ないユニットが抽出される。これは、既に選定された選択ユニットについては、そこからＧＷ１０２までの経路については既に選択処理が実行されて経路が確立されているはずであるため、それ以上隣接ユニットをたどる必要はないためである。
【０１２７】
ステップＳ３１０４のブロードキャスト対象ユニットの選択処理の詳細は、図３２のフローチャートで示される。以下、図３２のフローチャートについて説明する。
まず、選定処理対象ユニットＹにおいて、経路情報が参照されることにより、ＧＷ１０２までのルートが探索される。そして、探索されたルート中から、ＧＷ１０２までの最短ルート上に位置する隣接ユニットが抽出される（図３２のステップ３２０１）。
【０１２８】
例えば前述した実施例１では、１回目のステップＳ３１０３で１１番（ユニットＡ）が選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、１１番からＧＷ１０２までの最短ルート上の隣接ユニットとして１５番の１ユニットが選定される。また、１５番が選択ユニットとして選択され続く２回目のステップＳ３１０３で選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、１５番からＧＷ１０２までの最短ルート上の隣接ユニットとして２６番の１ユニットが選定される。
【０１２９】
実施例２では、１回目のステップＳ３１０３で７番（ユニットＡ）が選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、７番からＧＷ１０２までの最短ルート上の隣接ユニットとして２５，１４番の２ユニットが選定される。また、２つのうちから２５番が選択ユニットとして選択され続く２回目のステップＳ３１０３で選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、２５番からＧＷ１０２までの最短ルート上の隣接ユニットとして１番の１ユニットが選定される。
【０１３０】
実施例３では、１回目のステップＳ３１０３で２０番（ユニットＡ）が選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、２０番からＧＷ１０２までの最短ルート上の隣接ユニットとして５，１０，１８番のユニットが選定される。また、３つのうちから５番が選択ユニットとして選択され続く２回目のステップＳ３１０３で選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、５番からＧＷ１０２までの最短ルート上の隣接ユニットとして８，９番の２ユニットが選定される。
【０１３１】
実施例４では、１回目のステップＳ３１０３で２２番（ユニットＡ）が選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、２２番からＧＷ１０２までの最短ルート上の隣接ユニットとして１７番の１ユニットが選定される。
【０１３２】
実施例５では、１回目のステップＳ３１０３で３９番（ユニットＡ）が選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、３９番からＧＷ１０２までの最短ルート上の隣接ユニットとして９，３３番のユニットが選定される。
【０１３３】
実施例６では、１回目のステップＳ３１０３で２９番（ユニットＡ）が選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、２９番からＧＷ１０２までの最短ルート上の隣接ユニットとして３２，３７，３８，４０番のユニットが選定される。また、４つのうちから４０番が選択ユニットとして選択され続く２回目のステップＳ３１０３で選定処理対象ユニットＹとされたときに、ステップＳ３２０１では、４０番からＧＷ１０２までの最短ルート上の隣接ユニットとして１７，３番の２ユニットが選定される。
【０１３４】
上記ステップＳ３２０１の後、抽出された最短ルート上のＹの隣接ユニットが１つのみであるか否かが判定される（図３２のステップＳ３２０２）。
例えば前述した実施例１では、図３１のステップＳ３１０３からＳ３１０６の１回目の繰返し処理における図３２のステップＳ３２０１で１５番と２６番の各ユニットが抽出されたときに、ステップＳ３２０２の判定がＹＥＳとなる。
【０１３５】
実施例２では、ステップＳ３１０３からＳ３１０６の１回目の繰返し処理におけるステップＳ３２０１で２５，１４番の２ユニットが抽出されたときに、ステップＳ３２０２の判定がＮＯとなる。また、２回目の繰返し処理で１番のユニットが抽出されたときに、ステップＳ３２０２の判定がＹＥＳとなる。
【０１３６】
実施例３では、１回目の繰返し処理で５，１０，１８番の３ユニットが抽出されたときに、ステップＳ３２０２の判定がＮＯとなる。また、２回目の繰返し処理で８，９番のユニットが抽出されたときも、ステップＳ３２０２の判定がＮＯとなる。
【０１３７】
実施例４では、１回目の繰返し処理で１７番の１ユニットが抽出されたときに、ステップＳ３２０２の判定がＹＥＳとなる。
実施例５では、１回目の繰返し処理で９，３３番の２ユニットが抽出されたときに、ステップＳ３２０２の判定がＮＯとなる。
【０１３８】
実施例６では、１回目の繰返し処理で３２，３７，３８，４０番の４ユニットが抽出されたときに、ステップＳ３２０２の判定がＮＯとなる。また、２回目の繰返し処理で１７，３番のユニットが抽出されたときも、ステップＳ３２０２の判定がＮＯとなる。
【０１３９】
最短ルート上のＹの隣接ユニットが１つのみでステップＳ３２０２の判定がＹＥＳとなった場合には、その隣接ユニットをＢとして、ユニットＢが既に選択されたユニットであるか否かが判定される（図３２のステップＳ３２０３）。この判定は例えば、図１７，図１９，図２１，図２３，図２５，図２７等として示した経路情報上のユニットＢに、選択ユニットのマーク情報（図中２重実線の四角）が付与されているか否かを判定する処理として実現される。
【０１４０】
ユニットＢが未だ選択されたユニットではなくステップＳ３２０３の判定がＮＯならば、ステップＳ３２１０、続いてステップＳ３２１１の処理が実行される。一方、ユニットＢが既に選択されたユニットでステップＳ３２０３の判定がＹＥＳならば、ステップＳ３２１０は実行されずにステップＳ３２１１の処理が実行される。ステップＳ３２１０とステップＳ３２１１の処理については後述する。
【０１４１】
最短ルート上のＹの隣接ユニットが１つのみではなくステップＳ３２０２の判定がＮＯとなった場合には、ステップＳ３２０４からＳ３２０８の繰返し処理によって、最短ルート上のＹの複数の隣接ユニット数分だけ、以下の一連の処理が繰り返し実行される。ここで、各繰返しにおいて対象とされる最短ルート上のＹの隣接ユニットをＢとする。
【０１４２】
まず、ユニットＢが既に選択されたユニットであるか否かが判定される（図３２のステップＳ３２０５）。この判定はステップＳ３２０３の場合と同様に実現される。すなわち例えば、図１７，図１９，図２１，図２３，図２５，図２７，図２９等として示した経路情報上のユニットＢに、選択ユニットのマーク情報（図中２重実線の四角）が付与されているか否かを判定する処理として実現される。
【０１４３】
ユニットＢが既に選択されたユニットでステップＳ３２０５の判定がＹＥＳならば、ユニットＢからＧＷ１０２までの経路は既に確立されており他の経路を選択する必要はないため、ステップＳ３２１１で、ユニットＢがそのまま選択ユニットとして選定される。この場合にはさらに図３１に戻ってステップＳ３１０４の終了後、ステップＳ３１０５の判定がＹＥＳとなる。すなわち、現在のユニットＡからＧＷ１０２までの経路が確立されたことになるため、現在のユニットＡに対するステップＳ３１０３からＳ３１０６までの繰返し処理が終了する。
【０１４４】
例えば前述した実施例６では、図３１のステップＳ３１０３からＳ３１０６の１回目の繰返し処理において４０番が選択ユニットとして選択され続く２回目の繰返し処理のステップＳ３１０３で選定処理対象ユニットＹとされる。さらに、図３２のステップＳ３２０１では、４０番からＧＷ１０２までの最短ルート上の隣接ユニットとして１７，３番の２ユニットが選定される。そして、図３２のステップＳ３２０２の判定がＮＯとなった後、ステップＳ３２０４からＳ３２０８までの繰返し処理において、ユニットＢ＝１７番が処理されるときに、ステップＳ３２０５の判定がＹＥＳとなる。この結果、ステップＳ３２１１で、ユニットＢ＝１７番がそのまま選択ユニットとして選定される。さらに、図３１に戻ってステップＳ３１０４の終了後、ステップＳ３１０５の判定がＹＥＳとなる。これにより、隣接ユニットが最も少なく選択ユニットを含まない２９番のユニットからＧＷ１０２までの経路がＧＷ→１７→４０→２９として確立できたため、図３１のステップＳ３１０３からＳ３１０６までの２９番のユニットに対する繰返し処理を終了する。
【０１４５】
ユニットＢが未だ選択されたユニットではなくステップＳ３２０５の判定がＮＯならば、次の処理が実行される。
まず、ユニットＢの隣接ユニットの中で、選択されたユニットでカバーできていないユニット数Ｍ、すなわち、選択ユニットと選択ユニットによってカバーされる隣接ユニットを除くユニット数Ｍが算出される（図３２のステップＳ３２０６）。この算出処理は、前述したステップ３．の（ｃ）のアルゴリズムを適用するための処理である。
【０１４６】
次に、ユニットＢの隣接ユニットについて、隣接する選択ユニット数の閾値Ｎを超える数Ｋが算出される（図３２のステップＳ３２０７）。より具体的には、図１８，図２０，図２２，図２４，図２６等として示した、各通信ユニット１０１に隣接する選択ユニット情報において、以下の処理が実行される。すなわち、選択ユニット情報において、ユニットＢの隣接ユニットの各々に、ユニットＢを新たな選択ユニットとして加えたときに、合計の選択ユニットの数がＮ個（例えば４個）を超えることとなる隣接ユニットの数Ｋが算出される。この算出処理は、前述したステップ３．の（ｄ）のアルゴリズムを適用するための処理である。
【０１４７】
ステップＳ３２０６とＳ３２０７の処理が、ステップＳ３２０４からＳ３２０８の繰返し処理によって、最短ルート上のＹの複数の隣接ユニット数分だけ実行される。
上記繰返し処理が終了した後、ステップＳ３２０７で算出された数Ｋが最も少ないユニット中、ステップＳ３２０６で算出されたＭが最も多いユニットが、選択ユニットとして選定されるべきユニットと判定される。選定対象となるユニットが複数存在した場合には、経路情報から算出される隣接ユニット数が最も多いユニットが選ばれる（以上、図３２のステップＳ３２０９）。
【０１４８】
例えば前述した実施例２では、図３１のステップＳ３１０３からＳ３１０６の１回目の繰返し処理で、ステップＳ３２０１で選定処理対象ユニットＹ＝７番からＧＷ１０２までの最短ルート上の隣接ユニットとして２５，１４番の２ユニットが選定される。このとき、図３２のステップＳ３２０６において、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数Ｍがそれぞれ、７個および６個と算出される。また、図３２のステップＳ３２０７において、２５，１４番の２ユニットとも、閾値Ｎ個（例えば４個）を超えることとなる隣接ユニットの数Ｋは、０個である。これにより、ステップＳ３２０９では、Ｋの数が最少の０個である２５番と１４番のうち、Ｍの数が最多の７個となる２５番のユニットが、選択ユニットとして選定されるべきユニットと判定される。
【０１４９】
実施例３では、１回目の繰返し処理で、５，１０，１８番のユニットが選定される。このとき、図３２のステップＳ３２０６において、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数Ｍがそれぞれ、８，４，５個と算出される。また、図３２のステップＳ３２０７において、５，１０，１８番の３ユニットとも、閾値Ｎ個（例えば４個）を超えることとなる隣接ユニットの数Ｋは、０個である。これにより、ステップＳ３２０９では、Ｋの数が最少の０個である５，１０，１８番のうち、Ｍの数が最多の８個となる５番のユニットが、選択ユニットとして選定されるべきユニットと判定される。さらに２回目の繰返し処理で、８，９番のユニットが選定される。このとき、図３２のステップＳ３２０６において、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数Ｍがそれぞれ、１０，７個と算出される。また、図３２のステップＳ３２０７において、８，９番の２ユニットとも、閾値Ｎ個（例えば４個）を超えることとなる隣接ユニットの数Ｋは、０個である。これにより、ステップＳ３２０９では、Ｋの数が最少の０個である８，９番のうち、Ｍの数が最多の１０個となる８番のユニットが、選択ユニットとして選定されるべきユニットと判定される。
【０１５０】
実施例５では、１回目の繰返し処理で、９，３３番のユニットが選定される。このとき、図３２のステップＳ３２０６において、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数Ｍがそれぞれ、２，１個と算出される。また、図３２のステップＳ３２０７において、９，３３番の２ユニットとも、閾値Ｎ個（例えば４個）を超えることとなる隣接ユニットの数Ｋは、０個である。これにより、ステップＳ３２０９では、Ｋの数が最少の０個である９，３３番のうち、Ｍの数が最多の２個となる９番のユニットが、選択ユニットとして選定されるべきユニットと判定される。
【０１５１】
実施例６では、１回目の繰返し処理で、３２，３７，３８，４０番のユニットが選定される。このとき、図３２のステップＳ３２０６において、選択ユニットとそれがカバーする隣接ユニットを除いた隣接ユニット数Ｍがそれぞれ、１個（４番），１個（４番），０個，１個（４番）個と算出される。また、図３２のステップＳ３２０７において、３２番のユニットについては、閾値Ｎ個（例えば４個）を超えることとなる隣接ユニットとして１６番と１９番のユニットが出現するため、Ｋ＝２となる。また、３７番と４０番のユニットについては、閾値Ｎ個（例えば４個）を超えることとなる隣接ユニットの数Ｋは、０個である。さらに、３２番の隣接ユニット数は１１個、３７番の隣接ユニット数は８個、４０番の隣接ユニット数は９個である。これにより、ステップＳ３２０９では、Ｋの数が最少の０個でＭの数が最多の１個ある３７番，４０番のうち、隣接ユニット数が９個と多い４０番のユニットが、選択ユニットとして選定されるべきユニットと判定される。
【０１５２】
以上のようにして、図３２のステップＳ３２０９またはステップＳ３２０３で選定対象と判定されたユニットに対して、ステップＳ３２１０の処理が実行される。ここでは、ステップＳ３２０９またはＳ３２０３で判定されたユニットの隣接ユニットが、図１７，図１９，図２１，図２３，図２５等の経路情報から抽出される。そして、図１８，図２０，図２２，図２４，図２６等として示した、各通信ユニット１０１に隣接する選択ユニット情報において、経路情報から抽出された各ユニットの欄に、ステップＳ３２０９またはＳ３２０３で新たに選ばれたユニットが追加登録される。
【０１５３】
ステップＳ３２１１では、図３２のステップＳ３２０９またはステップＳ３２０３で選定対象と判定されたユニットについて、またはステップＳ３２０３またはＳ３２０５で既に選択されたユニットと判定されたユニットが、選択ユニットとして選定される。
上述の図３２のフローチャートの処理により、図３１のステップＳ３１０４のブロードキャスト対象ユニットの選択処理が実現される。
【０１５４】
以上説明した実施形態の処理により、サーバ３０１がブロードキャスト転送を行う通信ユニット１０１を選択することで、無線ネットワークに流れるパケットを抑制でき、ネットワークトラヒックを軽減することが可能で、パケットの到達精度が向上する。
【０１５５】
本実施形態によれば、無線ネットワークのトラヒック状態を、従来技術と比べ、１／３以下に軽減することができる。従来技術では、無線ネットワークの情報量は例えば、
（１ゲートウェイ＋３５通信ユニット）×パケットサイズ
となる。これに対して、本実施形態によるアドホック無線ネットワークの情報量は例えば、
（１ゲートウェイ＋１０通信ユニット）×パケットサイズ
とすることができる。
【０１５６】
図３３は、本実施形態におけるパケット転送による無線ネットワークのトラヒック状態を示す図である。本実施形態では、特定の距離にある通信ユニット全てをブロードキャスト転送許可対象とするのではなく、特定の距離にある通信ユニットの中からさらに対象を絞ってブロードキャスト転送許可対象の通信ユニットを選択する。この際、選択した通信ユニットからの無線電波到達範囲が重ならないような選択を行う。このため、従来技術よりもさらに無線ネットワークのトラヒックを軽減でき、ブロードキャストをより効率的に行うことが可能となる。また、本実施形態では、天候による無線品質の変化にも、動的にブロードキャスト対象ユニットを変更し対応することが可能となる。
【０１５７】
図３４は、本実施形態による図３のサーバ３０１を実現できるコンピュータのハードウェア構成の一例を示す図である。
図３４に示されるコンピュータは、ＣＰＵ３４０１、メモリ３４０２、入出力装置３４０３、３４０４、外部記憶装置３４０５、可搬記録媒体３４０９が挿入される可搬記録媒体駆動装置３４０６、及び通信インターフェース３４０７を有し、これらがバス３４０８によって相互に接続された構成を有する。同図に示される構成は上記システムを実現できるコンピュータの一例であり、そのようなコンピュータはこの構成に限定されるものではない。
【０１５８】
ＣＰＵ３４０１は、当該コンピュータ全体の制御を行う。メモリ３４０２は、プログラムの実行、データ更新等の際に、外部記憶装置３４０５（或いは可搬記録媒体３４０９）に記憶されているプログラム又はデータを一時的に格納するＲＡＭ等のメモリである。ＣＵＰ３４０１は、プログラムをメモリ３４０２に読み出して実行することにより、全体の制御を行う。
【０１５９】
入出力装置３４０３，３４０４は、ユーザによるキーボードやマウス等による入力操作を検出し、その検出結果をＣＰＵ３４０１に通知し、ＣＰＵ３４０１の制御によって送られてくるデータを表示装置や印刷装置に出力する。
【０１６０】
外部記憶装置３４０５は、例えばハードディスク記憶装置である。主に各種データやプログラムの保存に用いられる。
可搬記録媒体駆動装置３４０６は、光ディスクやＳＤＲＡＭ、コンパクトフラッシュ（登録商標）等の可搬記録媒体３４０９を収容するもので、外部記憶装置３４０５の補助の役割を有する。
【０１６１】
通信インターフェース３４０７は、例えばＬＡＮ（ローカルエリアネットワーク）又はＷＡＮ（ワイドエリアネットワーク）の通信回線を接続するための装置である。
本実施形態によるシステムは、本実施形態の機能を実現する図３１および図３２のフローチャートに対応する制御プログラムを、ＣＰＵ３４０１が実行することで実現される。そのプログラムは、例えば外部記憶装置３４０５や可搬記録媒体３４０９に記録して配布してもよく、或いは通信インターフェース３４０７によりネットワークから取得できるようにしてもよい。制御プログラムにおいて使用する各データは、例えば外部記憶装置３４０５又はメモリ３４０２上に記憶して運用される。また、メモリ３４０２上には、必要に応じて制御プログラムを実行するためのワーク領域が展開される。
【０１６２】
以上の実施形態に関して、更に以下の付記を開示する。
（付記１）
複数の通信ユニットで構成されるネットワークに接続され、いずれかの通信ユニットにおけるパケット転送を制御する制御装置が実行するパケット転送方法において、
前記制御装置が
記憶部に記憶された前記通信ユニット毎に隣接する通信ユニットに関する隣接ユニット情報と、各通信ユニットと前記制御装置間の経路を示す経路情報を参照して、複数の通信ユニットのうち、他通信ユニットまたは該制御装置から受信したパケットをブロードキャスト転送すべき通信ユニットを選択するステップと、
前記選択されたブロードキャスト転送すべき通信ユニットを示す情報を含むパケットを生成し、前記複数ユニットのいずれかに送信するステップと、
を有することを特徴とするブロードキャスト転送方法。（１、図７〜図１５及び図３１，３２）
（付記２）
前記ブロードキャスト対象ユニットの選択処理において、隣接する通信装置の数が少ない通信装置へブロードキャスト転送させるように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１に記載のブロードキャストパケットの転送方法。（２、図３１）
（付記３）
前記ブロードキャスト対象ユニット選択処理において、前記経路情報に基づいて前記ブロードキャストパケットの配信元の通信装置からの経路が最短経路となるように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１に記載のブロードキャストパケットの転送方法。（３、図３２）
（付記４）
前記ブロードキャスト対象ユニット選択処理において、既に選択されたブロードキャスト対象ユニットでカバーできていない隣接する通信装置をより多くカバーするように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１に記載のブロードキャストパケットの転送方法。（４、図３２）
（付記５）
前記ブロードキャスト対象ユニット選択処理において、前記各通信装置に隣接する通信装置に含まれるブロードキャスト対象ユニットの上限数を設定し、前記上限数を超えないように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１に記載のブロードキャストパケットの転送方法。（５、図３２）
（付記６）
全ての前記通信装置に前記ブロードキャストパケットが配信されるように、前記ブロードキャスト対象ユニットの選択処理を繰り返し実行する、
ことを特徴とする付記１に記載のブロードキャストパケットの転送方法。（６、図３１、３２）
（付記７）
前記ブロードキャスト対象ユニットを選択するステップは、
隣接する通信ユニットの数が最も少ない通信ユニットへブロードキャスト転送させるように前記ブロードキャスト対象ユニットを選択する第１のステップと、
前記経路情報に基づいて前記ブロードキャストパケットの配信元の通信ユニットからの経路が最小ホップ数と成るように前記ブロードキャスト対象ユニットを選択する第２のステップと、
既に選択されたブロードキャスト対象ユニットでカバーできていない隣接する通信ユニットをより多くカバーするように前記ブロードキャスト対象ユニットを選択する第３のステップと、
からなる、
ことを特徴とする付記１に記載のブロードキャストパケットの転送方法。（７）
（付記８）
前記各通信装置に隣接する通信装置に含まれるブロードキャスト対象ユニットの上限数を設定し、前記上限数を超えないように前記ブロードキャスト対象ユニットを選択する第４のステップからなる、
ことを特徴とする付記７に記載のブロードキャストパケットの転送方法。（８）
（付記９）
前記第１、第２、第３、第４のステップをパケットを送信すべき全てのユニットをカバーするまで繰り返し実行する、
ことを特徴とする付記８記載のブロードキャストパケットの転送方法。（９）
（付記１０）
複数の通信ユニットで構成されるネットワークに接続され、いずれかの通信ユニットにおけるパケット転送を制御する制御装置であって、
前記通信ユニット毎に該通信ユニットに隣接する通信ユニットを示す隣接ユニット情報と、各通信ユニットと前記制御装置間の経路を示す経路情報が記憶される記憶部と、
前記隣接ユニット情報および前記経路情報を参照して、前記複数の通信ユニットのうち、他通信ユニットまたは該制御装置から受信したパケットをブロードキャスト転送すべき通信ユニットを選択する選択部と、
前記選択されたブロードキャスト転送すべき通信ユニットを示す情報を含むパケットを生成し、前記複数ユニットのいずれかに送信する送信部
を有することを特徴とするブロードキャスト転送装置。（１０）
（付記１１）
前記ブロードキャスト対象ユニットの選択処理において、隣接する通信装置の数が少ない通信装置へブロードキャスト転送させるように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１０に記載のブロードキャストパケットの転送装置。
（付記１２）
前記ブロードキャスト対象ユニット選択処理において、前記経路情報に基づいて前記ブロードキャストパケットの配信元の通信装置からの経路が最短経路となるように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１０に記載のブロードキャストパケットの転送装置。
（付記１３）
前記ブロードキャスト対象ユニット選択処理において、既に選択されたブロードキャスト対象ユニットでカバーできていない隣接する通信装置をより多くカバーするように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１０に記載のブロードキャストパケットの転送装置。
（付記１４）
前記ブロードキャスト対象ユニット選択処理において、前記各通信装置に隣接する通信装置に含まれるブロードキャスト対象ユニットの上限数を設定し、前記上限数を超えないように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１０に記載のブロードキャストパケットの転送装置。
（付記１５）
複数の通信ユニットで構成されるネットワークに接続され、いずれかの通信ユニットにおけるパケット転送を制御する制御装置に、
記憶部に記憶された前記通信ユニット毎に隣接する通信ユニットに関する隣接ユニット情報と、各通信ユニットと前記制御装置間の経路を示す経路情報を参照して、複数の通信ユニットのうち、他通信ユニットまたは該制御装置から受信したパケットをブロードキャスト転送すべき通信ユニットを選択するステップと、
前記選択されたブロードキャスト転送すべき通信ユニットを示す情報を含むパケットを生成し、前記複数ユニットのいずれかに送信するステップと、
を実行させるプログラム。（１１）
（付記１６）
前記ブロードキャスト対象ユニットの選択処理において、隣接する通信装置の数が少ない通信装置へブロードキャスト転送させるように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１５に記載のプログラム。
（付記１７）
前記ブロードキャスト対象ユニット選択処理において、前記経路情報に基づいて前記ブロードキャストパケットの配信元の通信装置からの経路が最短経路となるように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１５に記載のプログラム。
（付記１８）
前記ブロードキャスト対象ユニット選択処理において、既に選択されたブロードキャスト対象ユニットでカバーできていない隣接する通信装置をより多くカバーするように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１５に記載のプログラム。
（付記１９）
前記ブロードキャスト対象ユニット選択処理において、前記各通信装置に隣接する通信装置に含まれるブロードキャスト対象ユニットの上限数を設定し、前記上限数を超えないように前記ブロードキャスト対象ユニットを選択する、
ことを特徴とする付記１５に記載のプログラム。
（付記２０）
全ての前記通信装置に前記ブロードキャストパケットが配信されるように、前記ブロードキャスト対象ユニットの選択処理を繰り返し実行する、
ことを特徴とする付記１５に記載のプログラム。
【符号の説明】
【０１６３】
１０１  通信ユニット
１０２  ゲートウェイ
３０１  サーバ
４０２  アドホックＦＰＧＡ
【図４】
0005387482.tif 000002
【図５】
0005387482.tif 000003
【図６】
0005387482.tif 000004
【図９】
0005387482.tif 000005
【図１１】
0005387482.tif 000006
【図１４】
0005387482.tif 000007
【図１６】
0005387482.tif 000008
【図１７】
0005387482.tif 000009
【図１８】
0005387482.tif 000010
【図１９】
0005387482.tif 000011
【図２０】
0005387482.tif 000012
【図２１】
0005387482.tif 000013
【図２２】
0005387482.tif 000014
【図２３】
0005387482.tif 000015
【図２４】
0005387482.tif 000016
【図２５】
0005387482.tif 000017
【図２６】
0005387482.tif 000018
【図２７】
0005387482.tif 000019
【図２８】
0005387482.tif 000020
【図２９】
0005387482.tif 000021
【図３０】
0005387482.tif 000022
【図３１】
0005387482.tif 000023
【図３２】
0005387482.tif 000024
【図３４】
0005387482.tif 000025
【図１】
0005387482.tif 000026
【図２】
0005387482.tif 000027
【図３】
0005387482.tif 000028
【図７】
0005387482.tif 000029
【図８】
0005387482.tif 000030
【図１０】
0005387482.tif 000031
【図１２】
0005387482.tif 000032
【図１３】
0005387482.tif 000033
【図１５】
0005387482.tif 000034
【図３３】
0005387482.tif 000035