(57)【要約】  複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムにおいて各ノードの重要度を生成する重要度生成方法は、各ノードが、前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットを調べて記憶装置に記憶し、各ノードが、自ノードと相互に接続する他ノードに前記分断ポイントセットを含むパケットを送信し、発信ノードから発信されたデータの最終的な宛先となる目的ノードが、中継ノードから受信したパケットに含まれる前記分断ポイントセットに基づいて、送信元ノードと送信先ノードの各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算し、前記中継ノードの障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成するように構成される。
2014192142.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムの無線端末であって、
発信ノードから発信されたデータの最終的な宛先となる目的ノードを形成し、
前記ネットワークシステム内の中継ノードから受信したパケットに含まれ前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットに基づいて、送信元ノードと送信先ノードの各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算する手段と、
前記中継ノードの障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成する手段
を備えたことを特徴とする、無線端末。
【請求項２】
多重化された経路毎の各ノードの重要度から経路の評価値を計算する手段をさらに備え、
前記評価値に基づいて保守の対象となるノードに優先順位を付けて前記保守の対象となるノードを絞り込む
ことを特徴とする、請求項１記載の無線端末。
【請求項３】
前記重要度は、前記分断確率が大きい程高いことを特徴とする、
請求項１または２記載の無線端末。
【請求項４】
複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムの無線端末であって、
発信ノードから発信されたデータの最終的な宛先となる目的ノード以外のノードを形成し、
前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットを調べて記憶装置に記憶する手段と、
自ノードと相互に接続する他ノードに前記分断ポイントセットを含むパケットを送信する手段
を備えたことを特徴とする、無線端末。
【請求項５】
自ノードと相互に接続する他ノードから、前記目的ノードへパケットを送信する際の経路を示す経路情報と各経路の経路数を含むパケットを受信し、前記経路情報と各経路の経路数を前記記憶装置に記憶する
ことを特徴とする、請求項４記載の無線端末。
【請求項６】
自ノードで障害が発生した場合の分断ポイントセットを調べ、各分断ポイントから自ノードを除いた残りの要素を分断ポイントに変更し、同一の分断ポイント及び上位の分断ポイントを除く
ことを特徴とする、請求項５記載の無線端末。
【請求項７】
複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムにおいて各ノードの重要度を生成する重要度生成方法であって、
各ノードが、前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットを調べて記憶装置に記憶し、
各ノードが、自ノードと相互に接続する他ノードに前記分断ポイントセットを含むパケットを送信し、
発信ノードから発信されたデータの最終的な宛先となる目的ノードが、中継ノードから受信したパケットに含まれる前記分断ポイントセットに基づいて、送信元ノードと送信先ノードの各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算し、前記中継ノードの障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成する
ことを特徴とする、重要度生成方法。
【請求項８】
前記目的ノードが、多重化された経路毎の各ノードの重要度から経路の評価値を計算し、
前記評価値に基づいて保守の対象となるノードに優先順位を付けて前記保守の対象となるノードを絞り込む
ことを特徴とする、請求項７記載の重要度生成方法。
【請求項９】
各ノードが、自ノードと相互に接続する他ノードから、前記目的ノードへパケットを送信する際の経路を示す経路情報と各経路の経路数を含むパケットを受信し、前記経路情報と各経路の経路数を前記記憶装置に記憶する
ことを特徴とする、請求項７または８記載の重要度生成方法。
【請求項１０】
各ノードが、自ノードで障害が発生した場合の分断ポイントセットを調べ、各分断ポイントから自ノードを除いた残りの要素を分断ポイントに変更し、同一の分断ポイント及び上位の分断ポイントを除く
ことを特徴とする、請求項９記載の重要度生成方法。
【請求項１１】
前記重要度は、前記分断確率が大きい程高いことを特徴とする、
請求項７乃至１０のいずれか１項記載の重要度生成方法。
【請求項１２】
前記発信ノード及び中継ノードは無線端末であり、
前記目的ノードはゲートウェイである
ことを特徴とする、請求項７乃至１１のいずれか１項記載の重要度生成方法。
【請求項１３】
複数の無線端末間の経路が環境に応じて動的に調整されるネットワークシステムを有する無線通信システムであって、
各無線端末は、
前記ネットワークシステム内の経路を分断する無線端末を分断ポイントとする分断ポイントセットを調べて記憶装置に記憶し、
自無線端末と相互に接続する他無線端末に前記分断ポイントセットを含むパケットを送信し、
発信無線端末から発信されたデータの最終的な宛先となる目的無線端末は、
中継無線端末から受信したパケットに含まれる前記分断ポイントセットに基づいて、送信元無線端末と送信先無線端末の各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算し、前記中継無線端末の障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成する
ことを特徴とする、無線通信システム。
【請求項１４】
複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムにおいて、発信ノードから発信されたデータの最終的な宛先となる目的ノードの処理をコンピュータに実行させるプログラムであって、
前記ネットワークシステム内の中継ノードから受信したパケットに含まれ前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットに基づいて、送信元ノードと送信先ノードの各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算する手順と、
前記中継ノードの障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成する手順
を前記コンピュータに実行させることを特徴とする、プログラム。
【請求項１５】
多重化された経路毎の各ノードの重要度から経路の評価値を計算する手順をさらに前記コンピュータに実行させ、
前記評価値に基づいて保守の対象となるノードに優先順位を付けて前記保守の対象となるノードを絞り込む
ことを特徴とする、請求項１４記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線端末、重要度生成方法及び無線通信システムに関する。
【背景技術】
【０００２】
近年、複数の無線端末の各々が自立的に相互接続するアドホックネットワークシステムが提案されている。アドホックネットワークシステムでは、アクセスポイントは設置されず、各無線端末が、経路情報に基づいて自端末と相互に接続する無線端末から受信したパケットを隣接端末に対して中継することで、環境に応じた経路を形成する。例えば、各無線端末で測定されたセンサデータは、生成された経路に基づいて、１または複数の無線端末に中継され、目的の端末に送信される（例えば、特許文献１，２）。【０００３】
上記の如きアドホックネットワークシステムでは、無線端末の故障、電池切れ等により機能停止等の障害が発生する場合がある。無線端末に障害が発生すると、中継する無線端末はデータを送受信することができず、障害が発生した無線端末を迂回する代替の経路が無い場合には、センサデータは目的の無線端末に送信されない。無線端末の障害に対しては、修理、電池または機器の置き換え等の人手による対応、即ち、保守（または整備）が必要となる。しかし、無線端末の障害に対応可能な人員が限られている場合、障害が発生した無線端末が多数ある場合等には、障害が発生した無線端末に即座に対応することは難しい。【０００４】
例えば軽微な障害が発生した無線端末については、即座ではなくある程度まとめて対応することで、障害への対応の効率化を図ることができる。一方、例えばセンサデータの多くが失われる、ネットワーク機能が停止してしまう等といった大きな障害が発生した無線端末については、即座に対応することが望ましい。【０００５】
アドホックネットワークシステムの場合、障害が発生した無線端末を含む経路によっては、他の無線端末で中継する経路に動的に変更することで、中継する無線端末の代替が可能である。しかし、障害が発生した無線端末の配置によっては、代替経路が存在しない場合もある。【０００６】
そこで、障害が発生した無線端末の重要度に基づいて、障害への対応の優先度を設定することが望ましい。無線端末の重要度は、例えば代替経路数、対象無線端末を経由している経路数等に基づいて計算しても良い。【０００７】
しかし、代替経路数は、例えばアドホックネットワークシステム内の全ての無線端末における隣接テーブルを所定の無線端末に集約し、各無線端末の隣接テーブルの情報に基づいて構築される経路情報に基づいて計算される。１つの無線端末における隣接テーブルは、この１つの無線端末に隣接する無線端末の情報を有する。このため、隣接テーブルの収集のための通信量が増大し、アドホックネットワークシステムに負荷がかかると共に、無線端末の記憶装置は隣接テーブルを格納するのに十分な記憶容量を要する。さらに、隣接テーブルが集約される所定の無線端末は、隣接テーブルに基づく経路情報の構築と類似した処理を繰り返すことで代替経路を計算するため、高負荷状態となり易く、処理に時間がかかる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１２−１９９７０３号公報
【特許文献２】特許第４９４１３９７号公報
【特許文献３】特開２００３−２０３０２１号公報
【特許文献４】特開２００３−１７７９４５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従来技術では、障害が発生した無線端末がアドホックネットワークシステム全体に及ぼす影響の重要度を計算する処理に時間がかかり、無線端末が高負荷状態となり易い。このため、障害が発生した無線端末の保守を優先的に行うべきかを重要度に基づいて判断するには時間がかかる。【００１０】
そこで、本発明は、無線端末の重要度を短時間で計算可能な無線端末、重要度生成方法及び無線通信システムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の一観点によれば、複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムにおいて各ノードの重要度を生成する重要度生成方法であって、各ノードが、前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットを調べて記憶装置に記憶し、各ノードが、自ノードと相互に接続する他ノードに前記分断ポイントセットを含むパケットを送信し、発信ノードから発信されたデータの最終的な宛先となる目的ノードが、中継ノードから受信したパケットに含まれる前記分断ポイントセットに基づいて、送信元ノードと送信先ノードの各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算し、前記中継ノードの障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成する重要度生成方法が提供される。
【発明の効果】
【００１２】
開示の無線端末、重要度生成方法及び無線通信システムによれば、無線端末の重要度を短時間で計算可能となる。
【図面の簡単な説明】
【００１３】
【図１】アドホックネットワークシステムの全体構成の一例を示す図である。
【図２】一実施例におけるノードの構成の一例を示すブロック図である。
【図３】ノードの機能ブロック図である。
【図４】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図５】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図６】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図７】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図８】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図９】経路情報が有する各経路と経路数の一例を説明する図である。
【図１０】ステップＳ１２の送信元無線端末と送信先無線端末間の経路数の抽出処理の一例を説明する図である。
【図１１】代替経路数の計算方法の一例を説明する図である。
【図１２】図４〜図８の具体例における代替経路数の一例を説明する図である。
【図１３】ノードにおける処理の一例を説明するフローチャートである。
【図１４】ゲートウェイにおける処理の一例を説明するフローチャートである。
【図１５】アドホックネットワークシステムの一例を示す図である。
【図１６】図１５に示すアドホックネットワークシステムについて、送信元ノード、分断ポイントを構成するノード数、分断確率の近似値、及び代替経路数の一例を示す図である。
【図１７】ノードにおけるデータパケットの送信処理の一例を説明するフローチャートである。
【図１８】分断ポイントセットの計算方法の第２の例を説明する図である。
【図１９】分断ポイントセットの計算方法の第３の例を説明する図である。
【図２０】分断ポイントセットの計算方法の第４の例を説明する図である。
【図２１】経路変更の第１の例を説明する図である。
【図２２】経路変更の第２の例を説明する図である。
【図２３】ノードにおける分断ポイントセットと経路テーブルの一例を示す図である。
【図２４】ノードにおけるＨｅｌｌｏパケットの送信処理の一例を説明するフローチャートである。
【図２５】Ｈｅｌｌｏヘッダの一例を示す図である。
【図２６】ノードにおけるＨｅｌｌｏパケットの受信処理の一例を説明するフローチャートである。
【図２７】ノードにおけるデータパケットの受信処理の一例を説明するフローチャートである。
【図２８】ノードにおけるデータパケットの再送処理の一例を説明するフローチャートである。
【図２９】データ管理テーブルのレコードの一例を示す図である。
【図３０】目的ノードにおける重要度生成処理の一例を説明するフローチャートである。
【図３１】目的ノードにおける分断ポイントテーブルと重要度テーブルの一例を説明する図である。
【発明を実施するための形態】
【００１４】
開示の無線端末、重要度生成方法及び無線通信システムでは、アドホックネットワークシステム等のノード間の経路が環境に応じて動的に調整されるネットワークシステムにおいて、各中継ノードの障害がネットワークシステム全体に及ぼす影響の重要度をネットワークシステムにおける伝送の障害確率で表す。具体的には、送信元ノードと送信先ノードの各対に対してどこを分断すると伝送が途絶するかを表す分断確率を調べることにより、各ノードに障害が発生した時のネットワークシステム上のデータ伝送に与える影響の大きさを見積もる。分断確率が大きい程、重要度が高いものとする。
【００１５】
従って、多数のノードを含むネットワークシステムにおいて、多重化された経路毎の各ノードの重要度から経路の評価値を計算すれば、評価値に基づいて保守の対象となるノードに優先順位を付けて保守の対象となるノードを絞り込むことができる。
【００１６】
以下に、開示の無線端末、重要度生成方法及び無線通信システムの各実施例を図面と共に説明する。
【実施例】
【００１７】
図１は、アドホックネットワークシステムの全体構成の一例を示す図である。図１に示すアドホックネットワークシステム１は、無線通信システムの一例であり、この例ではゲートウェイＧＷ及び無線端末ａ〜ｉを有する。ゲートウェイＧＷ及び無線端末ａ〜ｉは、ノード（または、ノード装置）の一例であり、同じ構成を有しても良い。【００１８】
アドホックネットワークシステム１において、無線端末ａ〜ｉは、自律的にルーティングを行い、マルチホップ通信を行う。この例では、実線はルーティングによって生成されたデータ転送経路を示し、点線は相互に通信可能であるが転送経路に該当しない経路を示す。例えば、無線端末ｄにおいて測定されたセンサデータは、無線端末ｃ，ｅ，ｆ，ａを経由してゲートウェイＧＷに到達する。【００１９】
図２は、一実施例におけるノードの構成の一例を示すブロック図である。図２に示すノード５は、プロセッサの一例であるＣＰＵ（Central Processing Unit）１１、記憶装置またはコンピュータ読取可能な記憶媒体の一例であるメモリ１２、送受信機１３及びセンサ１４を有する。ＣＰＵ１１、メモリ１２、送受信機１３及びセンサ１４は、バス１５を介して相互に接続されている。【００２０】
メモリ１２は、例えば制御プログラム２１を含む各種プログラム、及び各種テーブル２２を記憶する。ＣＰＵ１１は、例えば制御プログラム２１を実行し、後述する重要度生成処理等を行い、各種テーブル２２等を生成する。なお、ＣＰＵ１１が実行する処理は、専用のハードウェアで実行しても良い。センサ１４は、例えば所定の対象を測定してセンサデータを生成する。送受信機１３は、アンテナ１６を介してセンサデータ等を有するデータパケット及び通信用の制御パケットの送受信を、ＣＰＵ１１の制御下で行う。【００２１】
図３は、ノードの機能ブロック図である。図３に示すノード５は、Ｈｅｌｌｏパケット受信部３１、Ｈｅｌｌｏパケット送信部３３、Ｈｅｌｌｏパケット生成部３４、経路情報抽出部３２、経路テーブルＴｔ及び隣接テーブルＴｙを有する。経路テーブルＴｔ及び隣接テーブルＴｙは、各種テーブル２２に含まれる。経路テーブルＴｔは、例えば自ノード５から送信先となる他ノード５にパケットを送信する際の経路を示す経路情報を格納する。隣接テーブルＴｙは、隣接するノード５の情報を格納する。【００２２】
Ｈｅｌｌｏパケット受信部３１は、Ｈｅｌｌｏパケットを受信し、経路情報抽出部３２は、受信したＨｅｌｌｏパケットに含まれるデータから経路情報及び経路数を抽出し、経路テーブルＴｔに格納する。また、Ｈｅｌｌｏパケット生成部３４は、経路テーブルＴｔを参照して経路情報及び経路数を有するＨｅｌｌｏパケットを生成する。Ｈｅｌｌｏパケット送信部３３は、生成されたＨｅｌｌｏパケットを送信する。【００２３】
また、ノード５は、データパケット生成部４１、経路選択部４２、データパケット送信部４３、及びデータパケット受信部４４を有する。データパケット生成部４１は、データパケットを生成する。データパケットは、所定のデータを有し、送信先となる他ノード５に送信される。【００２４】
経路選択部４２は、経路テーブルＴｔを参照してノード５の分断ポイントセットを計算し、データパケットのデータ部にノード５の分断ポイントセットを追加し、経路テーブルＴｔから送信先となるノード５に対応する送信先ノード５を選択する。データパケット送信部４３は、センサデータを有するデータパケットを送信する。データパケット受信部４４は、データパケットを受信する。【００２５】
図４〜図８は、本実施例におけるＨｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。図４〜図８は、本実施例におけるアドホックネットワーク１の一部を示す。図４〜図８に示す例において、ＧＷはゲートウェイを示す。この例において、経路テーブルＴｔは、目的ノードを含む送信先ノードＴ、送信先ノードＴへの経路において経由する隣接ノードｌ（エル）、送信先ノードＴまでのホップ数ｈ、及び自ノードと送信先ノードＴとの間の経路数ｋを有する。なお、経路テーブルＴｔにおいて、ゲートウェイＧＷは便宜上Ｇと表記されている。なお、経路テーブルＴｔは、変更フラグＦ及び分断ポイントセットＤＰＳをさらに有するが、変更フラグＦ及び分断ポイントセットＤＰＳについては後述する。【００２６】
本実施例では、経路情報の生成のために、Ｈｅｌｌｏパケットと呼ばれる制御パケットが用いられる。ノード５は、周期的にＨｅｌｌｏパケットをブロードキャストする。そして、ノード５は、Ｈｅｌｌｏパケットを送受信して他のノード５と経路情報を交換し、経路テーブルＴｔを生成する。また、本実施例において、Ｈｅｌｌｏパケットには、経路情報に加えて経路数が付加される。【００２７】
ノード５は、Ｈｅｌｌｏパケットを受信すると、Ｈｅｌｌｏパケットが有する経路情報に基づいて、自ノード５の経路テーブルＴｔを更新する。具体的に、ノード５は、Ｈｅｌｌｏパケットを受信すると、Ｈｅｌｌｏパケットが有する経路情報のうち、自ノード５の経路テーブルＴｔに存在しない経路の情報を経路数ｋと共に、自ノード５の経路テーブルＴｔに追加する。また、ノード５は、Ｈｅｌｌｏパケットが、経路テーブルＴｔの経路情報よりもホップ数ｈの少ない経路情報を有する場合、Ｈｅｌｌｏパケットが有する経路情報を経路テーブルＴｔに上書きする。また、送信先ノードＴ及びリンクＬに同一の経路が複数ある場合、ノード５は、経路数の総和を経路テーブルＴｔに登録する。経路テーブルＴｔは、このようにして生成できる。【００２８】
図４の（１）において、例えば、ゲートウェイＧＷは、ゲートウェイＧＷがネットワーク上に存在することを示すＨｅｌｌｏパケットＨ１１，Ｈ１２を隣接するノードｃ及びノードｄに送信する。ノードｃは、受信したＨｅｌｌｏパケットＨ１１に基づいて経路情報を生成し、経路テーブルＴｃ−１に格納する。具体的には、ノードｃは、ゲートウェイＧＷ（Ｔ）まで自ノードｃから１ホップ（ｈ）である旨の経路情報を生成する。なお、ノードｃとゲートウェイＧＷ間の経路数は１つである。このため、経路数１（ｋ）が登録される。【００２９】
図４の（１）において、同様にして、ノードｄは、ゲートウェイＧＷから送信されたＨｅｌｌｏパケットＨ１２を受信する。ノードｄは、受信したＨｅｌｌｏパケットＨ１２に基づいて、自ノードｄからゲートウェイＧＷ（Ｔ）まで１ホップ（ｈ）である旨の経路情報、及び、経路数１（ｋ）を生成し、経路テーブルＴｄ−１に格納する。このように、ノード５は、隣接ノード５への経路を初めに生成する場合は、その経路数（ｋ）を1とする。【００３０】
図４の（２）は、ノードｃが、ＨｅｌｌｏパケットＨ２１，Ｈ２２をノードａ及びノードｂに送信する場合を例示する。このとき、ＨｅｌｌｏパケットＨ２１は、ノードｃがゲートウェイＧＷまで１ホップ（ｈ）である旨の経路情報を有する。そこで、ノードａは、ＨｅｌｌｏパケットＨ２１が有する経路情報に基づいて、ノードｃ（ｌ）をリンクしてゲートウェイＧＷ（Ｔ）まで２ホップ（ｈ）である旨の経路情報とその経路数１（ｋ）を経路テーブルＴａ−２に追加する。このとき、Ｈｅｌｌｏパケットが有する経路数（ｋ）が経路テーブルに転記される。このように、ＨｅｌｌｏパケットＨ２１が有する経路情報のリンク（ｌ）とホップ（ｈ）が変更され、自ノードａの経路テーブルＴａ−２に追加されることによって、経路情報が延長される。また、ノードａは、ノードｃ（Ｔ）まで１ホップ（ｈ）である旨の経路情報とその経路数１（ｋ）を経路テーブルＴａ−２に追加する。【００３１】
また、ノードｂは、ノードｃ（Ｔ）まで１ホップである旨の経路情報とその経路数１（ｋ）、及び、隣接ノードｃ（ｌ）をリンクしてゲートウェイＧＷ（Ｔ）まで２ホップ（ｈ）である旨の経路情報とその経路数１（ｋ）を、経路テーブルＴｂ−２に追加する。このように、Ｈｅｌｌｏパケットの伝搬によって経路情報が延長される。【００３２】
図５は、Ｈｅｌｌｏパケットに基づく経路情報の生成処理の具体例の続き（３），（４）を説明する図である。図５の（３）において、ノードａがノードｃにＨｅｌｌｏパケットＨ３１を送信すると、ノードｃは、Ｈｅｌｌｏパケットに含まれる経路情報に基づいて経路情報を生成する。このとき、ＨｅｌｌｏパケットＨ３１は、ノードｃ（ｌ）をリンクしてゲートウェイＧＷ（Ｔ）まで２ホップ（ｈ）である旨の経路情報を有する。ただし、ノードｃの経路テーブルＴｃ−３は、既にゲートウェイＧＷ（Ｔ）まで１ホップである旨の経路情報を有する。この場合、例えばノードｃは、ノードａ（ｌ）をリンクしてゲートウェイＧＷ（Ｔ）まで３ホップ（ｈ）である旨の非効率な経路情報を、経路テーブルＴｃ−３に追加しなくても良い。【００３３】
このように、経路テーブルに追加される経路は、経路長であるホップ（ｈ）に基づいて、制限されても良い。図５の（３）の例において、例えば、経路テーブルにおける同一の送信先ゲートウェイＧＷ（Ｔ）への最短ホップ数１から２ホップ以上長い３ホップの経路（この例ではノードａをリンクする経路）については除外される。このように、ホップ数に基づいて経路が除外されることにより、非効率な経路が除外される。これにより、例えば重要ととして利用可能な経路数を計算する場合には、計算誤差を回避できる。【００３４】
また、図５の（３）において、ノードｂは、ノードｄからＨｅｌｌｏパケットＨ３２を受信すると、ノードｄ（Ｔ）まで１ホップ（ｈ）である旨の経路情報とその経路数１（ｋ）、及び、隣接ノードｄ（ｌ）をリンクしてノードＧＷ（Ｔ）まで２ホップ（ｈ）である旨の経路情報とその経路数１（ｋ）を経路テーブルＴｂ−３に追加する。【００３５】
図５の（４）において、ノードｂはノードｃ、ノードａ及びノードｄにＨｅｌｌｏパケットＨ４１〜Ｈ４３を送信する。ノードａは、ノードｂからＨｅｌｌｏパケットＨ４１を受信すると、ノードｂ（Ｔ）までの経路情報とその経路数１（ｋ）、及び、ノードｂ（ｌ）をリンクするノードｃ（Ｔ）までの経路情報とその経路数１（ｋ）を追加する。また、ノードｂの経路テーブルＴｂ−３は、ゲートウェイＧＷを送信先（Ｔ）とし、ノードｃ（ｌ）またはノードｄ（ｌ）をリンクする２つの経路情報を有する。このため、ノードａは、ノードｂ（ｌ）をリンクするゲートウェイＧＷ（Ｔ）までの経路情報とその経路数２（ｋ）を経路テーブルＴａ−４に追加する。このように、ノード５は、リンク（ｌ）と送信先ノード５までの経路が複数ある場合、各リンクの経路数の和を経路テーブルに格納する。同様にして、ＨｅｌｌｏパケットＨ４２，Ｈ４３に基づいて、経路テーブルＴｃ−４，Ｔｄ−４が更新される。【００３６】
このように、リンク（ｌ）から送信先ノード（Ｔ）まで複数の経路がある場合、経路の和が、自ノード５から当該リンク（ｌ）を中継する送信先ノード５間の経路数として、経路テーブルに格納される。これにより、経路テーブルに基づいて、経路情報に加えてその経路数（ｋ）が検知可能になる。【００３７】
図６は、Ｈｅｌｌｏパケットに基づく経路情報の生成処理の具体例の続き（５）を説明する図である。図６の（５）において、ノードａは、ノードｂ及びノードｃにＨｅｌｌｏパケットＨ５１，Ｈ５２を送信する。これにより、ノードｂの経路テーブルＴｂ−５に、ノードａをリンク（ｌ）とする３つの経路情報とその経路数（ｋ）が追加される。また、ノードｃの経路テーブルＴｃ−５に、ノードａをリンク（ｌ）とする２つの経路情報とその経路数（ｋ）が追加される。【００３８】
図７は、Ｈｅｌｌｏパケットに基づく経路情報の生成処理の具体例の続き（６）を説明する図である。図７の（６）において、ノードｂは、ノードｃ及びノードｄにＨｅｌｌｏパケットＨ６１，Ｈ６２を送信する。ノードｃの経路テーブルＴｃ−６は、ノードｂをリンク（ｌ）とする経路情報を既に有するが、ノードｂをリンク（ｌ）とする送信先ノードａ（Ｔ）の経路情報は有していない。このため、ノードｃは、ノードｂをリンク（ｌ）とする送信先ノードａ（Ｔ）の経路情報と、その経路数１（ｋ）を、経路テーブルＴｃ−６に追加する。同様にして、ノードｄは、ノードｂをリンク（ｌ）とする送信先ノードａ（Ｔ）の経路情報とその経路数１（ｋ）を経路テーブルＴｄ−６に追加する。【００３９】
図８は、Ｈｅｌｌｏパケットに基づく経路情報の生成処理の具体例の続き（７）を説明する図である。図８の（７）において、ノードｃは、ノードａ及びノードｂにＨｅｌｌｏパケットＨ７１，Ｈ７２を送信する。図７の（６）と同様にして、ノードａは、ノードｃをリンク（ｌ）とする送信先ノードｄ（Ｔ）の経路情報とその経路数１（ｋ）を、経路テーブルＴａ−７に追加する。同様にして、ノードｂは、ノードｃをリンク（ｌ）とする送信先ノードａ（Ｔ）の経路情報とその経路数１（ｋ）を経路テーブルＴｂ−７に追加する。【００４０】
このように、Ｈｅｌｌｏパケットの伝搬経路の相違によって、同一の送信先ノードについて複数の経路を有する経路テーブルが生成される。例えば、図８のノードａの経路テーブルＴａ−７は、点線で囲むように、ノードｃを送信先ノードとする計２つの経路、ノードｄを送信先ノードとする計２つの経路、ゲートウェイＧＷを送信先ノードとする計３つの経路を有する。【００４１】
図９は、経路情報が有する各経路と経路数の一例を説明する図である。図９のテーブルＴａ−８〜Ｔｄ−８は、図８の経路テーブルの情報に加えて、経路情報に対応する送信元ノードと送信先ノード（Ｔ）との間における総経路数を有する。【００４２】
図９のノードａの経路テーブルは、前述したとおり、ノードａとゲートウェイＧＷ（Ｔ）との間の経路として、隣接ノードｃをリンク（ｌ）とする１つの経路「ノードａ→ノードｃ→ゲートウェイＧＷ」と、隣接ノードｂをリンク（ｌ）とする２つの経路「ノードａ→ノードｂ→ノードｃ→ゲートウェイＧＷ」及び「ノードａ→ノードｂ→ノードｄ→ゲートウェイＧＷ」を有する。つまり、ノードａの経路テーブルＴａ−８は、ゲートウェイＧＷ（Ｔ）を送信先とする３つの経路を有する。【００４３】
同様にして、図９のノードａの経路テーブルＴａ−８は、ノードｄ（Ｔ）との間の経路として、隣接ノードｃをリンク（ｌ）とする１つの経路「ノードａ→ノードｃ」と、隣接ノードｂをリンク（ｌ）とする１つの経路「ノードａ→ノードｂ→ノードｃ」を有する。これは、経路テーブルＴａ−８が、ノードｃを送信先とする２つの経路を有することを意味する。同様にして、経路テーブルＴａ−８は、ノードｄ（Ｔ）を送信先とする２つの経路「ノードａ→ノードｂ→ノードｄ」及び「ノードａ→ノードｃ→ゲートウェイＧＷ→ノードｄ」を有する。【００４４】
また、図９において、ノードｂの経路テーブルＴｂ−８は、ゲートウェイＧＷ（Ｔ）を送信先とする経路として、ノードａ、ノードｃ、ノードｄを夫々リンク（ｌ）とする経路を有する。つまり、経路テーブルＴｂ−８は、ゲートウェイＧＷ（Ｔ）を送信先とする３つの経路を有する。また、経路テーブルＴｂ−８は、ノードａを送信先とする２つの経路、ノードｃを送信先とする２つの経路、及びノードｄを送信先とする１つの経路を有する。他のノードの経路テーブルについても、同様である。【００４５】
このように、本実施例では、Ｈｅｌｌｏパケットに経路数が付加されることによって、自ノード５と送信先ノード５との経路情報に加えて、自ノード５と送信先ノード５との総経路数を計算可能となる。【００４６】
ノード５は、データパケット中継時に、データパケットの送信元ノード５と送信先ノード５との間の総経路数を抽出する。【００４７】
図１０は、送信元ノードと送信先ノード間の経路数の抽出処理の一例を説明する図である。この例において、実線の矢印はデータパケットの送信経路を示し、点線の矢印は相互に通信可能であるが、データパケットの送信経路には該当しない経路を示す。【００４８】
図１０の例において、例えばノードａは、測定したセンサデータを有するデータパケットを、ノードｃを経由してゲートウェイＧＷに送信する。この場合、送信元ノードはノードａ、送信先ノードはゲートウェイＧＷに相当する。また、図１０の例において、例えばノードｂは、測定したセンサデータを有するデータパケットを、ノードｄを経由してゲートウェイＧＷに送信する。この場合、送信元ノードはノードｂ、送信先ノードはノードｄに相当する。なお、ノードｃ及びノードｄについても、夫々送信元ノードとなり得る。【００４９】
先ず、ノードａから送信先ゲートウェイＧＷにデータパケットが送信される場合を例示する。この場合、送信元ノードａは、自ノードａと送信先ゲートウェイＧＷとの間の総経路数３をデータパケットに付加する。そして、中継ノードｃは、データパケット中継時に、データパケットに含まれる、送信元ノードａと送信先ゲートウェイＧＷとの総経路数３を抽出する。ノードｂから送信先ゲートウェイＧＷにデータパケットが送信される場合についても同様である。中継ノードｄは、データパケット中継時に、データパケットに含まれる、送信元ノードｂと送信先ゲートウェイＧＷとの総経路数３を抽出する。このように、本実施例では、送信元ノードと送信先ノードとの間の総経路数が、各中継のノードに伝達される。【００５０】
送信元ノード５と送信先ノード５との間の総経路数は、既存のデータパケットに追加されることにより、効率的に中継ノード５に伝達される。総経路数を格納するフィールドのサイズは小さく、データパケットの数についても増加しないため、ネットワークの負荷は増加しない。【００５１】
次に、代替経路数の計算方法の一例を説明する。図１１は、代替経路数の計算方法の一例を説明する図である。図１１の例において、データパケットの送信元ノード５はノードｄであって、目的ノード５はゲートウェイＧＷである。この例では、発信ノードｄから目的ゲートウェイＧＷまでの経路における、中継ノードｆの代替経路数の計算方法について例示する。本実施例において、代替経路数は、計算式「（発信ノードから目的ノードまでの経路総数）−（ノードを中継する経路数）」に基づいて計算される。また、ノードを中継する経路数は、「（ノードと発信ノードと間の経路数）×（ノードと目的ノードとの間の経路数）」を示す。【００５２】
図１１の例において、発信ノードｄと目的ゲートウェイＧＷとの間の経路数は９である。また、発信ノードｄと中継ノードｆとの間の経路数は２であって、中継ノードｆと目的ゲートウェイＧＷとの間の経路数は３である。従って、発信ノードｄと目的ゲートウェイＧＷとの間の総経路数９から、発信ノードｄと中継ノードｆとの間の経路数２と中継ノードｆと目的ゲートウェイＧＷとの間の経路数３との乗算値（＝２×３）を減算する。これにより、発信ノードｄから目的ゲートウェイＧＷまでの経路における中継ノードｆの代替経路数３（＝９−２×３）を計算できる。【００５３】
なお、この例では、ノードｆについて代替経路数を計算したが、代替経路数は他の中継ノード５においても同様に計算できる。また、同一の中継ノード５における代替経路数は、データパケットの発信ノード５と目的ノード５によって異なる。【００５４】
次に、代替経路数の一例を説明する。図１２は、図４〜図８の具体例における代替経路数の一例を説明する図である。図１２は、ノードｃ及びノードｄについて、経路数テーブルＴｃ−９，Ｔｄ−９と代替経路数テーブルＴｃｘ，Ｔｄｘとを示す。代替経路数テーブルＴｃｘ，Ｔｄｘは、データパケットの送信元ノードｔｒと代替経路数ｄを有する。図１２の例において、各データパケットの送信先ノードは、ゲートウェイＧＷである。【００５５】
先ず、送信元ノードａ（ｔｒ）から送信先ゲートウェイＧＷまでの経路における、中継ノードｃの代替経路数（ｄ）を説明する。この場合、ノードｃの代替経路数（ｄ）は、計算式「｛送信元ノードａから送信先ゲートウェイＧＷまでの経路総数（＝３）｝−｛ノードｃと送信元ノードａとの間の経路数（＝２）｝×｛ノードｃと送信先ゲートウェイＧＷとの間の経路数（＝１）｝」に基づいて、１（＝３−２×１）が計算される。なお、この場合、代替経路は、ノードａ→ノードｂ→ノードｄ→ゲートウェイＧＷの経路である。また、送信元ノードｃ（ｔｒ）から送信先ゲートウェイＧＷまでの経路における、ノードｃの代替経路数（ｄ）は、ノードｃが送信元ノードであることにより０である。【００５６】
同様にして、送信元ノードｂ（ｔｒ）から送信先ゲートウェイＧＷまでの経路における、中継ノードｄの代替経路数（ｄ）を説明する。この場合、ノードｄの代替経路数（ｄ）は、計算式「｛送信元ノードｂから送信先ゲートウェイＧＷまでの経路総数（＝３）｝−｛ノードｂと送信元ノードａとの間の経路数（＝１）｝×｛ノードｄと送信先ゲートウェイＧＷとの間の経路数（＝１）｝」に基づいて、２（＝３−１×１）が計算される。なお、この場合、代替経路は、ノードｂ→ノードｃ→ゲートウェイＧＷ、または、ノードｂ→ノードａ→ノードｃ→ゲートウェイＧＷの経路である。【００５７】
以上のように、送信元ノード５と送信先ノード５との総経路数、中継ノード５と送信元ノード５との経路数、及び中継ノード５と送信先ノード５との経路数とに基づいて、中継ノード５の代替経路数の計算することができる。また、経路数は、既存の制御パケットであるＨｅｌｌｏパケットに基づいて効率的に生成可能である。このように、ノード５は、他ノード５の中継時における代替経路数を、ネットワークへの負荷をかけることなく、迅速に、効率的に計算することができる。【００５８】
なお、図８において前述したとおり、例えば経路のホップ数に基づいて、検出される経路が制限されても良い。これにより、非効率な経路が除外され、計算される代替経路数の誤差が回避される。例えば、送信元ノード５から送信先ノード５までの経路総数には非効率な経路の数が含まれ、ノード５を中継する経路数には非効率な経路の数が含まれない場合、計算される代替経路数は誤差を含んでしまう。このため、代替経路数の精度を向上するために、例えば経路は最短の経路数から所定のホップ分だけ長い経路以内に制限される。【００５９】
このように、本実施例における経路情報は、同一経路における最短距離から基準距離範囲内（例えば、２ホップ以内）の経路を有する。そして、ノード５は、当該経路情報に基づいた、送信元ノード５から送信先ノード５までの経路総数、及び、ノード５を中継する経路数に基づいて、代替経路数を計算しても良い。この場合、送信元ノード５から送信先ノード５までの経路総数、及び、ノード５を中継する経路数から、非効率な経路が除外して、高精度の代替経路数を計算できる。【００６０】
次に、各ノード５の具体的な処理の流れについてより詳細に説明する。【００６１】
図１３は、ノードにおける処理の一例を説明するフローチャートである。なお、ノード５は、発信ノード５及び中継ノード５に相当する。発信ノード５とは、データの発信元となるノードである。中継ノード５とは、あるノード５から受信したデータを中継して他のノード５へ送信するノードである。発信ノード５には送信元ノードが含まれ、中継ノード５には送信元ノード５及び送信先ノード５が含まれる。送信元ノード５とは、データを他のノード５へ送信する側の中継ノードである。一方、送信先ノード５とは、データをあるノード５から受信する側のノードである。また、目的ノード５とは、発信ノード５から発信されたデータの最終的な宛先となるノードである。【００６２】
ステップＳ２１では、ノード５は、パケットデータの管理を行うデータ管理テーブルＴｍにおいて、時刻ＴＴＷが現時刻と一致するレコードが存在するか否かを判定する。データ管理テーブルＴｍは、各種テーブル２２に含まれる。データパケットの送信後、ノード５は、当該データパケットに対応するエントリをデータ管理テーブルＴｍに登録する。そして、データパケットの送信に対応するアクノレッジ（Acknowledge、以下、「ＡＣＫ」とも言う）を送信先ノード５から受信したとき、ノード５は、データ管理テーブルＴｍから該当するデータパケットのエントリを削除する。【００６３】
時刻ＴＴＷは、データ管理テーブルＴｍにおいて、データパケットに対応して設定される時刻であって、データパケットの送信時間からＡＣＫ待ち時間経過後の時刻に設定される。データ管理テーブルＴｍにおいて、時刻ＴＴＷが現時刻と一致するレコードが存在してステップＳ２１の判定結果がＹＥＳの場合、データパケットの送信後、ＡＣＫ待ち時間が経過しても、ＡＣＫが返ってきていないことを示す。即ち、送信したデータパケットが送信先ノード５により受信されていないことを意味する。【００６４】
そこで、ステップＳ２１の判定結果がＹＥＳの場合、ステップＳ２２では、ノード５は、データパケットの送信または再送処理を行う。データパケットの送信または再送処理については、別のフローチャートに基づいて後述する。ステップＳ２１，Ｓ２２は、パケットデータを送信後、一定期間内にＡＣＫが戻って来ない場合にデータパケットを再送するための処理を行うことができる。【００６５】
一方、データ管理テーブルＴｍにおいて、時刻ＴＴＷが現時刻と一致するレコードが存在せずステップＳ２１の判定結果がＮＯの場合、ステップＳ２３では、ノード５は、時刻ＴＴＷ１が現在の時刻と一致するか否かを判定する。時刻ＴＴＷ１は、Ｈｅｌｌｏパケットの送信後に設定される時刻であって、Ｈｅｌｌｏパケットの送信周期の時間経過後の時刻を示す。Ｈｅｌｌｏパケットは、周期的にブロードキャストされる。即ち、時刻ＴＴＷ１は、次のＨｅｌｌｏパケットの送信時刻を示す。このため、時刻ＴＴＷ１が現在の時刻と一致してステップＳ２３の判定結果がＹＥＳの場合、Ｈｅｌｌｏパケットの送信時間であることを意味する。これにより、ステップＳ２４では、ノード５は、Ｈｅｌｌｏパケットの送信処理を行う。本実施例におけるノード５は、経路データを有するＨｅｌｌｏパケットを送信する。Ｈｅｌｌｏパケットの送信処理については、別のフローチャートに基づいて、後述する。ステップＳ２３，Ｓ２４は、Ｈｅｌｌｏパケットを周期的にボードキャストするための処理を行う。【００６６】
時刻ＴＴＷ１と現在の時刻とが一致せずステップＳ２３の判定結果がＮＯの場合、ステップＳ２５では、ノード５は、時刻ＴＴＷ２が現在の時刻と一致するか否かを判定する。時刻ＴＴＷ２は、データパケットの送信後に設定される時刻であって、データパケットの送信周期の時間経過後の時刻を示す。この例において、データパケットは、周期的に送信される。即ち、時刻ＴＴＷ２は、次のデータパケットの送信時刻を示す。このため、時刻ＴＴＷ２が現在の時刻と一致してステップＳ２５の判定結果がＹＥＳの場合、データパケットの送信時間であることを意味する。これにより、ステップＳ２６では、ノード５は、センサデータ（即ち、データパケット）の送信処理を行う。本実施例におけるノード５は、送信元ノードである自ノードと、目的ノード５までの経路の総経路数とを有するデータパケットを送信する。ステップＳ２５，Ｓ２６は、各送信元ノード５から周期的にセンサデータを送信するための処理を行う。【００６７】
一方、時刻ＴＴＷ２と現在の時刻とが一致せずステップＳ２５の判定結果がＮＯの場合ステップＳ２７では、ノード５は、パケットを受信したか否かを判定する。パケットを受信してステップＳ２７の判定結果がＹＥＳの場合、ステップＳ２８では、ノード５は、パケットのタイプを判定する。一方、パケットを受信しておらずステップＳ２７の判定結果がＮＯの場合、ノード５は、ステップＳ２１の判定処理に戻る。【００６８】
パケットを受信してステップＳ２７の判定結果がＹＥＳの場合、ステップＳ２８の判定の結果、受信したパケットがＨｅｌｌｏパケットである場合、ステップＳ２９では、ノード５は、Ｈｅｌｌｏパケットの受信処理を行う。一方、受信したパケットがデータパケットである場合、ステップＳ３０では、ノード５は、データパケットの受信処理を行う。ステップＳ２９におけるＨｅｌｌｏパケットの受信処理及びステップＳ３０におけるデータパケットの受信処理については、別のフローチャートに基づいて後述する。また、受信したパケットがＡＣＫである場合、ステップＳ３１では、ノード５は、データ管理テーブルＴｍから、ＡＣＫに対応するデータパケットのエントリを削除する。これにより、送信済みのデータパケットの受信確認が行われる。【００６９】
図１４は、ゲートウェイにおける処理の一例を説明するフローチャートである。この例では、ゲートウェイＧＷは目的ノードの一例である。図１４において、ステップＳ２１では、ゲートウェイＧＷは、時刻ＴＴＷ３が現時刻と一致するか否かを判定する。時刻ＴＴＷ３は、ノード５の重要度の計算（または、生成）後に、現時点の重要度の計算（または、生成）周期後の時刻を示す。時刻ＴＴＷ３が現時刻と一致してステップＳ２１の判定結果がＹＥＳの場合、ステップＳ１２２では、ゲートウェイＧＷは、重要度テーブルの形成を行い、処理はステップＳ１２１へ戻る。重要度テーブルは、送信元ノード５毎に重要度を記述したテーブルであり、この重要度テーブルによって複数のノード５の障害に対応する場合の優先順位を付けることができる。ゲートウェイＧＷの構成がノード５の構成と同じ場合、重要度テーブルは、図２に示す各種テーブル２２に含まれる。【００７０】
一方、時刻ＴＴＷ３が現時刻と一致せずステップＳ１２１の判定結果がＮＯの場合、ステップＳ１２３では、ゲートウェイＧＷは、データパケットを受信したか否かを判定する。データパケットを受信しておらずステップＳ１２３の判定結果がＮＯの場合、処理はステップＳ１２１へ戻る。データパケットを受信しておりステップＳ１２３の判定結果がＹＥＳの場合、ステップＳ１２４では、ゲートウェイＧＷは、送信元ノード５にＡＣＫを送信する。ステップＳ１２５では、ゲートウェイＧＷは、受信したデータパケットのデータ部分から発信ノード５の分断ポイントセットを抽出して分断ポイントテーブルに登録する。分断ポイントセットとは、後述するように、発信ノード５から目的ノード５までの経路を分断するノード５のセットである。また、分断ポイントテーブルとは、後述するように、発信ノード５と、発信ノード５に対する分断ポイントセットとを含む。ステップＳ２３６では、ゲートウェイＧＷは、受信したデータパケットの残りの部分の処理を行い、処理はステップＳ１２１へ戻る。【００７１】
次に、分断ポイントセットについて説明する。発信ノードから目的ノードまでの経路が多数ある場合であっても、異なる経路で共通するノードの数が多ければ、経路が分断される可能性が高くなる。また、経路が長くなれば、経路が分断される可能性が高くなる。そこで、複数のノードに障害が発生した場合、例えば分断確率が最も高くなるものを重要なノードであると判断する。【００７２】
例えば図１５に示すアドホックネットワークシステム１において、先ず経路の分断ポイント、即ち、経路を分断するノードのセットを調べる。図１５の例では、ノードａが発信ノード（経路の起点）、ゲートウェイＧＷが目的ノード（目的点）であるものとする。また、分断ポイントは、破線で示す。【００７３】
次に、経路上の各ノードについて、自ノードで障害が発生した場合の分断ポイントセットを調べる。つまり、各分断ポイントから自ノードを除いた残りの要素を分断ポイントに変更する。例えば、ノードｂの分断ポイントｂ−ｉ→ｂ、分断ポイントｂ−ｅ→ｅに変更する。また、同一の分断ポイント及び上位の分断ポイントを除く。例えば、分断ポイントｉ−ｅと分断ポイントｅがあれば、分断ポイントｉ−ｅを除く。【００７４】
そして、得られた分断ポイントの分断確率を、例えばノード故障確率Ｐを用いて計算する。図１６は、図１５に示すアドホックネットワークシステム１について、送信元ノードｔｒ、分断ポイントを構成するノード数Ｎ＝１〜３、分断確率の近似値、及び代替経路数の一例を示す図である。【００７５】
この例では、発信ノードａから目的ノードであるゲートウェイＧＷまでの経路における、中継ノードｆの代替経路数の計算方法について例示する。代替経路数は、計算式「（発信ノードから目的ノードまでの経路総数）−（ノードを中継する経路数）」に基づいて計算できる。また、ノードを中継する経路数は、「（ノードと発信ノードと間の経路数）×（ノードと目的ノードとの間の経路数）」を示す。図１５の例において、発信ノードａと目的ノードであるゲートウェイＧＷとの間の経路数は４である。また、発信ノードａと中継ノードｂとの間の経路数は３であって、中継ノードｂとゲートウェイＧＷとの間の経路数は１である。従って、発信ノードａとゲートウェイＧＷとの間の総経路数４から、発信ノードａと中継ノードｂとの間の経路数３と中継ノードｂとゲートウェイＧＷとの間の経路数１との乗算値（＝３×１）を減算する。これにより、発信ノードａからゲートウェイＧＷまでの経路における中継ノードｂの代替経路数１（＝４−３×１）が計算できる。【００７６】
なお、この例では、中継ノードｂについて代替経路数を計算したが、代替経路数は他の中継ノードにおいても同様に計算できる。また、同一の中継ノードにおける代替経路数は、データパケットの発信ノードと、目的ノードによって異なる。【００７７】
図１６は、発信ノードａから送信されるトラヒックに対する分断ポイントの変化を、各ノードが単独故障した場合について示す。この例では、発信ノードａは、分断ポイントを構成するノード数Ｎ＝２については分断ポイントｅ−ｆ，ｅ−ｇ，ｂ−ｉ，ｂ−ｅを含み、分断ポイントを構成するノード数Ｎ＝３については分断ポイントｇ−ｈ−ｉを含む。図１６に示すように、例えばノードｂについては、分断ポイントを構成するノード数Ｎ＝１については分断ポイントｉ，ｅを含み、分断確率の近似値は２＊Ｐであり、代替経路数は１である。また、例えばノードｆについては、分断ポイントを構成するノード数Ｎ＝１については分断ポイントｅを含み、分断ポイントを構成するノード数Ｎ＝２については分断ポイントｂ−ｉを含み、分断ポイントを構成するノード数Ｎ＝３については分断ポイントｇ−ｈ−ｉを含み、分断確率の近似値はＰ＋Ｐ＊＊２＋Ｐ＊＊３であり、代替経路数は３である。なお、「＊」は乗算を表し、「＊＊」はべき乗を表す。このように、分断確率によれば、ノードの故障の影響度を、図１６中、比較例として示す代替経路の数に比べてより精密に評価できる。つまり、分断確率は、代替経路の数よりもノードの重要度をより精密に表すことができる。【００７８】
従って、多数のノード５を含むアドホックネットワークシステム１において、多重化された経路毎の各ノード５の重要度から経路の評価値を計算すれば、評価値に基づいて保守の対象となるノード５に優先順位を付けて保守の対象となるノード５を絞り込むことができる。【００７９】
次に、図１３のステップＳ２２が実行するデータパケットの送信処理、図１３のステップＳ２４が実行するＨｅｌｌｏパケットの送信処理、図１３のステップＳ２９が実行するＨｅｌｌｏパケットの受信処理、図１３のステップＳ３０が実行するデータパケットの送信処理、及び図１３のステップＳ２２が実行するデータパケットの再送処理を説明する。【００８０】
図１７は、ノードにおけるデータパケットの送信処理の一例を説明するフローチャートである。図１７の処理は、図１３のステップＳ２２により実行される。ステップＳ４１では、ノード５の経路選択部４２が経路テーブルＴｔを参照して、ノード５の分断ポイントセットを計算する。ステップＳ４２では、データパケット生成部４１及び経路選択部４２がデータパケットのデータ部に、センサデータに加えて、ステップＳ４１で計算したノード５の分断ポイントセットを追加する。ステップＳ４３では、経路選択部４２が経路テーブルＴｔを参照して、目的ノード５への経路における中継ノードが示す、次の送信先ノード５の情報を選択する。ステップＳ４４では、データパケット送信部４３が送信するデータパケットの情報をデータ管理テーブルＴｍに登録し、ステップＳ４５では、データパケット送信部４３がデータパケットを送信し、送信処理は終了する。【００８１】
図１８は、分断ポイントセットの計算方法の第１の例を説明する図である。この第１の例は、直近ノードに対する計算結果を再利用することで、アドホックネットワークシステム１の全ノードに対して別々に分断ポイントを計算するよりも効率的に分断ポイントを計算する。先ず、各送信元ノードに分断ポイントセットの情報を保存する。図１８中、各ノードの横には、当該ノードが保存する分断ポイントセットの情報を示す。なお、この例では、ノードａが発信ノードであり、ノードｄが目的ノードであるものとする。目的ノードｄは、ゲートウェイＧＷであっても良い。【００８２】
自ノードから目的ノードへの中継ノードが１つのみの場合、中継ノードのみからなる分断ポイントを中継ノードの持つ分断ポイントセットに追加して、自ノードの分断ポイントセットとする。従って、例えばノードｌ（エル）の分断ポイントセットの場合、中継ノードはノードｏのみでありノードｏの分断ポイントセットがｐなので、このｐを中継ノードｏに加えたｐ，ｏをノードｌ（エル）の分断ポイントセットとして計算する。ノードｐの分断ポイントセットの場合、目的ノードｄと直接通信可能であるため、分断ポイントは無い。【００８３】
一方、自ノードから目的ノードへの中継ノードが複数ある場合、各中継ノードの分断ポイントセットに中継ノード自体を追加する。また、各中継ノードの分断ポイントセットから１つずつ要素を選択し、積集合から重複を除いた分断ポイントセットを自ノードの分断ポイントセットとする。従って、例えばノードｋの分断ポイントセットの場合、中継ノードはノードｌ（エル），ｍの２つであり、各々の中継ノードｌ（エル），ｍの分断ポイントセットはｐ，ｏで同じであるため、これらの分断ポイントセットｐ，ｏに自身を追加することで、２つの分断ポイントセットｐ，ｏ，ｌ（エル）とｐ，ｏ，ｍを計算する。また、２つの分断ポイントセットｐ，ｏ，ｌ（エル）とｐ，ｏ，ｍの直積集合から重複要素を取り除くことで、分断ポイントセットｐ，ｏ，ｌ（エル）−ｍを計算する。同様に、例えばノードｊの分断ポイントセットの場合、中継ノードはノードｋ，ｎの２つであり、中継ノードｋの分断ポイントセットはｐ，ｏ，ｌ（エル）−ｍであり、中継ノードｎの分断ポイントセットはｐであるため、これらの分断ポイントセットｐ，ｏ，ｌ（エル）−ｍとｐに自身を追加することで、２つの分断ポイントセットｐ，ｏ，ｌ（エル）−ｍ，ｋとｐ，ｎを計算する。また、２つの分断ポイントセットｐ，ｏ，ｌ（エル）−ｍ，ｋとｐ，ｎの直積集合から重複要素を取り除くことで、分断ポイントセットｋ−ｎ、ｌ（エル）−ｍ−ｎ，ｐ，ｏ−ｎを計算する。【００８４】
図１９は、分断ポイントセットの計算方法の第２の例を説明する図である。図１９中、図１８と同一部分には同一符号を付し、その説明は省略する。一般的に、経路の多重度が増加すると分岐も多くなり、集合の直積の計算量が増大する。そこで、この第２の例は、要素数の多い分断ポイントは計算量が多い割には重要度への寄与が少なく、ノードの重要度に大きく寄与するのは経路数の少ない、即ち、要素数の少ない分断ポイントである点に着目する。【００８５】
つまり、この第２の例は、分断ポイントの要素数をチェックし、要素数の多い分断ポイントをノードの分断ポイントセットから削除することで、重要度判断の精度を落とすことなく計算量を減らす。図１９は、分断ポイントの要素数の上限を２とした場合に減らせる要素を四辺形で囲んで示す。図１９では、例えばノードｊの分断ポイントセットｋ−ｎ，ｌ（エル）−ｍ−ｎ，ｐ，ｏ−ｎから要素ｌ（エル）−ｍ−ｎが削除される。また、例えばノードｅの分断ポイントセットｐ，ｊ，ｋ−ｎ，ｏ−ｎ，ｂ−ｉ，ｇ−ｈ−ｉ，ｌ（エル）−ｍ−ｎから要素ｇ−ｈ−ｉ，ｌ（エル）−ｍ−ｎが削除される。【００８６】
図２０は、分断ポイントセットの計算方法の第３の例を説明する図である。図２０中、図１８と同一部分には同一符号を付し、その説明は省略する。例えばセンサネットワークシステムは、状況に応じて経路を変更する仕組みを備え、経路は常に部分的な修正を受ける。しかし、ローカルな経路変化であっても、変化のあった経路の先に経路変化の影響が及ぶ可能性があるため、センサネットワークシステム内の全てのノード（例えば、センサネットワーク装置）について分断ポイントセットを再計算しなければならない。【００８７】
そこで、この第３の例は、分断ポイントの要素数に上限を設け、上限を超える要素数の分断ポイントを除去する。また、自ノードにおける分断ポイントセットが再計算によって変化した場合にのみ変化のあった経路の先のノードに再計算を行うように通知する。図２０は、ノードｋとノードｏの間に新しいノードｑを追加した場合を示す。この例では、ノードｊではノードｎへの経路があるため、元々ｌ（エル）−ｍを含む分断ポイントがない。このため、ノードｑを追加しても、ノードｊの分断ポイントセットに変化はなく、図２０中破線で囲んだノードｊの手前のノードａ，ｂ，ｅ，ｆ，ｇ，ｈ，ｉへの再計算の通知は不要であり、ノードｊの先のノードｍ，ｎ，ｏ，ｐへの再計算の通知も不要である。一方、ノードｋについては、ノードｑの追加により、中継路が２つから３つに多重化されるため、分断ポイントセットから要素ｌ（エル）−ｍがなくなる。【００８８】
図２１は、経路変更の第１の例を説明する図である。図２１中、図１９と同一部分には同一符号を付し、その説明は省略する。図２１は、ノードｌ（エル）が除去される場合を示す。この例では、ノードｊではノードｎへの経路があるため、元々ｌ（エル）−ｍを含む分断ポイントがない。このため、ノードｌ（エル）を除去しても、図２１中破線で囲んだノードｊの手前のノードａ，ｂ，ｅ，ｆ，ｇ，ｈ，ｉへの再計算の通知は不要であり、ノードｊの先のノードｍ，ｎ，ｏ，ｐへの再計算の通知も不要である。一方、ノードｌ（エル）の除去により、ノードｊについては分断ポイントセットの要素がｋ−ｎ，ｐ，ｏ−ｎ，ｍ−ｎとなり、ノードｋについては分断ポイントセットの要素がｐ，ｏ，ｍになる。【００８９】
図２２は、経路変更の第２の例を説明する図である。図２２中、図１８と同一部分には同一符号を付し、その説明は省略する。図２２は、ノードｎが除去される場合を示す。この例では、ノードｎの除去により、ノードｊについては分断ポイントセットに要素ｋ，ｏ，ｌ（エル）−ｍ等が出現するため、ノードｊの手前のノードａ，ｂ，ｅ，ｆ，ｇ，ｈ，ｉへの再計算の通知が必要であり、ノードｊの先のノードｋへの再計算の通知も必要である。一方、ノードｌ（エル），ｍ，ｏ，ｐについては再計算の通知は不要である。【００９０】
図２３は、ノードにおける分断ポイントセットと経路テーブルの一例を示す図である。図２３中、（ａ）に示すように、分断ポイントセットＦＰＳは、目的ノードと共にメモリ１２に記憶される。また、図２３中、（ｂ）に示すように、経路テーブルＴｔには、送信先ノードＴ、隣接ノードｌ（エル）、送信先ノードＴまでのホップ数ｈ、自ノードと送信先ノードＴとの間の経路数ｋ、変更フラグＦ、及び分断ポイントセットＤＰＳが格納される。変更フラグＦは、オン状態により経路変更があることを示し、例えばデフォルト値はオンである。【００９１】
図２４は、ノードにおけるＨｅｌｌｏパケットの送信処理の一例を説明するフローチャートである。図２４の処理は、図１３のステップＳ２４により実行される。ステップＳ５１では、ノード５のＨｅｌｌｏパケット生成部３４が経路テーブルＴｔを参照して、未処理のエントリがあるか否かを判定する。未処理のエントリがありステップＳ５１の判定結果がＹＥＳの場合、ステップＳ５２では、Ｈｅｌｌｏパケット生成部３４が経路テーブルＴｔにおける未処理のエントリのうち、特定の目的ノードを選択する。例えばセンサネットワークシステムでは、通常、目的ノードはゲートウェイＧＷの１つだけである。【００９２】
ステップＳ５３では、Ｈｅｌｌｏパケット生成部３４が経路テーブルＴｔに変更フラグＦがオンであるエントリが存在するか、或いは、エントリ数が変化しているか否かを判定し、経路テーブルＴｔに変更フラグＦがオンであるエントリが存在せず、或いは、エントリ数が変化しておらずステップＳ５３の判定結果がＮＯの場合、処理は後述するステップＳ５７へ進む。一方、経路テーブルＴｔに変更フラグＦがオンであるエントリが存在するか、或いは、エントリ数が変化しておりステップＳ５３の判定結果がＹＥＳの場合、ステップＳ５４では、Ｈｅｌｌｏパケット生成部３４が分断ポイントセットの再計算を行う。ステップＳ５５では、Ｈｅｌｌｏパケット生成部３４が分断ポイントセットの値が変化しているか否かを判定し、分断ポイントセットの値が変化しておらずステップＳ５５の判定結果がＮＯの場合、処理は後述するステップＳ５７へ進む。【００９３】
一方、分断ポイントセットの値が変化しておりステップＳ５５の判定結果がＹＥＳの場合、ステップＳ５６では、ＨｅｌｌｏパケットのＨｅｌｌｏヘッダの変更フラグＦをオンにして、分断ポイントセットＤＰＳをＨｅｌｌｏヘッダに書き込み、処理はステップＳ５７へ進む。図２５は、Ｈｅｌｌｏヘッダの一例を示す図である。図２５に示すＨｅｌｌｏヘッダは、目的ノード、目的ノードまでのホップ数ｈ、経路品質重み、復路リンク重み、変更フラグＦ、及び分断ポイントセットＤＰＳを有する。経路品質重みには、経路品質の重み付けを行う場合に必要に応じて重み付けの値が設定される。復路リンク重みには、復路リンクの重み付けを行う場合に必要に応じて重み付けの値が設定される。【００９４】
ステップＳ５７では、Ｈｅｌｌｏパケット生成部３４がＨｅｌｌｏパケットに付加する経路データを形成する。具体的に、Ｈｅｌｌｏパケット生成部３４は、選択した目的ノードの経路情報及び経路数を、Ｈｅｌｌｏパケットに追加する。ステップＳ５８では、Ｈｅｌｌｏパケット生成部３４が経路テーブルＴｔにおいて、選択した目的ノードのエントリを処理済みのステータスに更新し、処理はステップＳ５１へ戻る。【００９５】
経路テーブルＴｔに未処理のエントリがなくなりステップＳ５１の判定結果がＮＯになると、ステップＳ５９では、Ｈｅｌｌｏパケット生成部３４が隣接ノードテーブルＴｙを参照して、隣接ノードテーブルＴｙのエントリからＨｅｌｌｏパケットの経路データを生成する。具体的に、Ｈｅｌｌｏパケット生成部３４は、隣接ノードテーブルＴｙを参照して隣接ノードの情報を取得し、Ｈｅｌｌｏパケットに設定する。ステップＳ６０では、ノード５のＨｅｌｌｏパケット送信部３３が、Ｈｅｌｌｏパケット生成部３４において生成されたＨｅｌｌｏパケットを送信し、Ｈｅｌｌｏパケットの送信処理は終了する。【００９６】
図２６は、ノードにおけるＨｅｌｌｏパケットの受信処理の一例を説明するフローチャートである。図２６の処理は、図１３のステップＳ２９により実行される。図２６において、ステップＳ６１では、ノード５のＨｅｌｌｏパケット受信部３１がＨｅｌｌｏパケットを受信すると、Ｈｅｌｌｏパケットがデータを有するか否かを判定する。受信したＨｅｌｌｏパケットがデータを有しステップＳ６１の判定結果がＹＥＳの場合、ステップＳ６２では、ノード５の経路情報抽出部３２が、Ｈｅｌｌｏパケットが有するデータである経路情報を経路テーブル情報に変換する。具体的には、経路情報抽出部３２は、例えばＨｅｌｌｏパケットが有する経路情報における中継ノードを、Ｈｅｌｌｏパケットの送信元ノードに書き換えると共に、ホップ数ｈをカウントアップする。また、経路情報抽出部３２は、Ｈｅｌｌｏパケットが有する経路情報が、目的ノードと中継ノードとが同一の経路を複数有する場合、各経路の経路数の合計を経路数とする。つまり、ステップＳ６２では、経路情報抽出部３２が受信したＨｅｌｌｏパケットの経路情報を経路テーブルＴｔのエントリへ変換する。【００９７】
ステップＳ６３では、経路情報抽出部３２が受信したＨｅｌｌｏパケットのＨｅｌｌｏヘッダの変更フラグＦがオンであるか、或いは、経路テーブルＴｔに新エントリがあるか否かを判定し、判定結果がＮＯの場合、処理は後述するステップＳ６５へ進む。一方、Ｈｅｌｌｏヘッダの変更フラグＦがオンであるか、或いは、経路テーブルＴｔに新エントリがありステップＳ６３の判定結果がＹＥＳの場合、ステップＳ６４では、経路情報抽出部３２が経路テーブルＴｔのエントリの変更フラグＦをオンにし、処理はステップＳ６５へ進む。【００９８】
ステップＳ６５では、ノード５の経路情報抽出部３２が変換した経路情報を経路テーブルＴｔに書き込む。ステップＳ６６では、経路情報抽出部３２が受信したＨｅｌｌｏパケットが有するデータから、経路テーブル情報に変換済みのエントリを削除し、処理はステップＳ６１へ戻る。【００９９】
ノードの経路情報抽出部３２は、Ｈｅｌｌｏパケットが有するデータについて、未処理のエントリがなくなるまで、経路情報の経路テーブル情報への変換処理から経路テーブルＴｔへの書き込み処理（ステップＳ６２〜Ｓ６５）を行う。一方、Ｈｅｌｌｏパケットがデータを有さずステップＳ６１の判定結果がＮＯの場合、即ち、初めのＨｅｌｌｏパケットの送信時、ノード５の経路情報抽出部３２はＨｅｌｌｏパケットの受信処理は終了する。【０１００】
図２７は、ノードにおけるデータパケットの受信処理の一例を説明するフローチャートである。図２７の処理は、図１３のステップＳ３０により実行される。図２７において、ステップＳ７１では、ノード５のデータパケット受信部４４がデータパケットを受信すると、受信したデータパケットに対応するエントリがデータ管理テーブルＴｍに登録されているか否かを判定する。受信したデータパケットに対応するエントリがデータ管理テーブルＴｍに登録されておりステップＳ７１の判定結果がＹＥＳの場合、ステップＳ７２では、ノード５の経路選択部４２は、経路テーブルＴｔから、エントリに対応する送信先ノードの情報を削除し、処理はステップＳ７３へ進む。【０１０１】
受信したデータパケットに対応するエントリがデータ管理テーブルＴｍに登録されておりステップＳ７１の判定結果がＮＯの場合、或いは、ステップＳ７２の後、ステップＳ７３では、データパケット受信部４４は、受信したデータパケットに対応するエントリがデータ管理テーブルＴｍに登録されていたか否かに関わらず、データパケットを受信したことを示すＡＣＫを、データパケットの送信元ノードに送信する。【０１０２】
ステップＳ７４では、経路選択部４２が経路テーブルＴｔを参照し、データパケットの次の送信先ノードを選択し、データパケットの情報をデータ管理テーブルＴｍに登録する。ステップＳ７５では、ノード５のデータパケット送信部４３がデータパケットを送信し、データパケットの受信処理は終了する。【０１０３】
図２８は、ノードにおけるデータパケットの再送処理の一例を説明するフローチャートである。図２８の処理は、図１３のステップＳ２２により実行される。図２８において、ステップＳ１４１では、ノード５の経路選択部４２がデータ管理テーブルＴｍの対象レコードの次の送信先ノードに未使用のものがあるか否かを判定し、未使用のものがなく判定結果がＮＯの場合、処理はステップＳ１４２へ進む。ステップＳ１４２では、経路選択部４２が対象レコードをデータ管理テーブルＴｍから削除し、データパケットの再送処理は終了する。一方、データ管理テーブルＴｍの対象レコードの次の送信先ノードに未使用のものがありステップＳ１４１の判定結果がＹＥＳの場合、処理はステップＳ１４３へ進む。【０１０４】
ステップＳ１４３では、経路選択部４２がデータ管理テーブルＴｍの対象レコードの次の送信先ノードを選択し、選択した経路に使用フラグを立てる。ステップＳ１４４では、経路選択部４２がデータ管理テーブルＴｍの対象レコードの時刻ＴＴＷを現時刻（即ち、データパケットの再送信時間）からＡＣＫ待ち時間経過後の時刻に再設定する。ステップＳ１４５では、ノード５のデータパケット送信部４３が対象レコードに対応するデータパケットを選択した経路に向けて送信し、データパケットの再送処理は終了する。データパケットの再送後は次の時刻ＴＴＷまで待ち、次の時刻ＴＴＷまでにＡＣＫが帰ってこないと、さらに未使用の経路があれば再度上記の如きデータパケットの再送処理を行う。【０１０５】
図２９は、データ管理テーブルのレコードの一例を示す図である。説明の便宜上、図２９はデータ管理テーブルＴｍの一部のみを示す。この例では、データ管理テーブルＴｍのレコードは、時刻、発信ノード、レコードの識別子ＦＩＤ、時刻ＴＴＷ、及び送信先ノードＬＤ１，ＬＤ２，ＬＤ３を有する。送信先ノードＬＤの左側の数字は、使用時に「１」に設定される使用フラグを示し、右側のアルファベットは送信先のノード名を示す。【０１０６】
図２９中、（ａ）は図１６に示すノードｅにおいて発信ノードａから最初のデータパケットを受信した時のレコードを示し、送信先ノードＬＤ１の「１」，「ｇ」はノードｇに送信することを表す。図２９中、（ｂ）は、（ａ）においてノードｇへの送信に失敗してデータパケットが再送された後のレコードを示し、送信先ノードＬＤ２の「１」，「ｈ」はノードｈに送信することを表す。図２９中、（ｃ）は、（ｂ）においてノードｈへの発信に失敗してデータパケットが再送された後のレコードを示し、送信先ノードＬＤ３の「１」，「ｉ」はノードｉに送信することを表す。【０１０７】
図３０は、目的ノードにおける重要度生成処理の一例を説明するフローチャートである。図３０に示す処理は、例えばゲートウェイＧＷのＣＰＵ１１により実行される。【０１０８】
図３０において、ステップＳ８１では、ゲートウェイＧＷのＣＰＵ１１が重要度テーブルに未処理のノードがあるか否かを判定し、未処理のノードがあり判定結果がＹＥＳの場合、処理はステップＳ８２へ進む。アドホックネットワークシステム１全体について上記の分断ポイントセットの再計算を行う場合、アドホックネットワークシステム１の全てのノードの処理が未処理とみなされる。このため、ステップＳ８２では、ゲートウェイＧＷのＣＰＵ１１が特定のノードを選択する。ステップＳ８３では、ＣＰＵ１１が分断ポイントテーブルから選択した特定のノードを含む分断ポイントを抽出し、各分断ポイントの出現回数をカウントする。【０１０９】
図３１は、目的ノードにおける分断ポイントテーブルと重要度テーブルの一例を説明する図である。図３１中、（ａ）は分断ポイントテーブルを示し、（ｂ）は重要度テーブルを示す。分断ポイントテーブルは、中継ノードから受信したＨｅｌｌｏパケットのＨｅｌｌｏヘッダに含まれる分断ポイントセットＤＰＳに基づいて、ゲートウェイＧＷ（即ち、目的ノード）が生成し、ノードと、対応する分断ポイントセットＤＰＳを有する。重要度テーブルは、中継ノードから受信したＨｅｌｌｏパケットのＨｅｌｌｏヘッダに含まれる分断ポイントセットＤＰＳに基づいて、ゲートウェイＧＷ（即ち、目的ノード）が生成し、ノードと、対応する重要度を有する。分断ポイントテーブル及び重要度テーブルは、例えばゲートウェイＧＷのメモリ１２に記憶された各種テーブル２２に含まれる。【０１１０】
ステップＳ８４では、ゲートウェイＧＷのＣＰＵ１１が特定のノードの故障時の分断箇所出現数の期待値を、分断ポイントの出現回数のカウント値に基づいて計算する。ステップＳ８５では、ゲートウェイＧＷのＣＰＵ１１が特定のノードについて計算した分断箇所出現数の期待値を、重要度を表す分断確率として生成し、図３１中、（ｂ）に示す重要度テーブルに書き込む。ステップＳ８６では、ゲートウェイＧＷのＣＰＵ１１が重要度テーブルの特定ノードを処理済みとして、処理はステップＳ８１へ戻る。【０１１１】
重要度テーブルに未処理のノードがなく、ステップＳ８１の判定結果がＮＯの場合、ステップＳ８７では、ゲートウェイＧＷのＣＰＵ１１が重要度テーブルを参照し、ノードの重要度から経路の評価値を計算し、重要度生成処理は終了する。経路の評価値は、例えばノードの重要度が高い程高い優先順位を示す値である。ステップＳ８７では、ゲートウェイＧＷのＣＰＵ１１がノードの重要度から計算した経路の評価値に基づいて、保守対象のノードに優先順位を付けることで、保守対象のノードに係る保守の優先度を判定するようにしても良い。また、保守対象のノードに係る保守の優先度の判定は、ユーザが重要度テーブルの重要度に基づいて行うようにしても良い。これにより、例えば少ない人員であっても、ノードの保守の優先度に基づいて、多数のノードの効率的な保守が可能になる。【０１１２】
本実施例におけるノードは、既存の制御パケット（例えば、Ｈｅｌｌｏパケット）を送受信することによって、簡易に、各ノードにおける経路の経路数を計算することができる。  また、本実施例におけるノードは、制御パケットの種別、及び、パケット数を増加させることなく、既存の制御パケットのデータサイズを、経路数を格納するフィールド分と分断ポイントセットを格納するフィールド分だけ僅かに増加させることにより、各経路の経路数を取得することができる。既存のデータパケットのデータサイズを僅かに増加させることにより、ノードは、送信元ノードと送信先ノードとの間の総経路数を取得することができる。さらに、ネットワークシステムへの負荷を増大させることなく、既存のリソースを用いて、簡易に、常に最新の経路数をノードに保持させることができる。また、ゲートウェイは、ノードから取得した分断ポイントセットから分断確率を重要度として計算することができる。【０１１３】
これに対し、一般的な方法に基づくと、例えば、経路数は、各ノードの隣接テーブルが集約ノードに送信され、集約ノードにおいて各ノードの隣接テーブルに基づいて計算される。このため、集約ノードにおける処理負荷が高くなると共に、集約ノードにおける経路構築処理は、各ノードにおける経路構築処理と冗長してしまう。また、隣接テーブルを集約ノードに周期的に送信することにより、パケット数が増加し、ネットワークの負荷が増大する。隣接テーブルの送信確認を行う場合、送信確認のためのＡＣＫ等の制御パケットが必要となり、さらに、制御パケット数が増加する。これにより、ネットワークが高負荷状態となり、隣接テーブルの集約ノードへの伝送に時間がかかることがある。【０１１４】
具体的に、一般的な方法によると、隣接テーブル送信処理に係るデータ量は、隣接テーブルを周期的に収集することを想定した場合、計算式「（全てのノード数）×（隣接テーブルの平均サイズ）×（経路平均長）×（テーブルデータ収集頻度）」によって計算される。なお、隣接テーブルは全ての隣接ノードの情報を有することにより、ノード数の増加に従ってサイズも増加する。また、ＡＣＫパケット等の制御パケットを要する場合、隣接テーブル送信処理に係るデータ量は、ＡＣＫ用のデータ量分「（全てのノード数）×（ＡＣＫパケットサイズ）×（経路平均長）」だけ増加する。【０１１５】
これに対し、本実施例におけるノードは、隣接テーブルの送受信を要することなく、既存の制御パケットに経路数の情報を付加することにより、各経路の経路数を計算可能になる。具体的に、本実施例において、増加するデータ量は、例えば、計算式「（全てのノード数）×１ｂｙｔｅ（経路数を格納する数値フィールドのサイズ）×（Ｈｅｌｌｏパケットの送信頻度）」によって計算される。また、データパケット中継時に、中継ノードに伝達される経路数の増加データ量は、例えば、計算式「（全てのノード数）×１ｂｙｔｅ（総経路数を格納する数値フィールドのサイズ）×｛（経路平均長）−１｝×（センサデータ収集頻度）」によって計算される。【０１１６】
このように、本実施例によると、制御パケットを新たに用意する必要がなく、経路数の計算のために増加するデータ量の増加量も少ない。【０１１７】
また、上記の如き分散型の実装では、各ノード内で分断ポイントセットを計算し、計算結果をＨｅｌｌｏパケットを利用して通知し、ノード間で共有する。このような分散型の実装では、経路テーブルのデータの送信に伴うトラヒックの輻輳や遅延を考慮しなくて済むという利点がある。しかし、一旦経路テーブルのデータをゲートウェイ等の一か所のノードに集めて全ての処理を行う集中型の実装も可能である。【０１１８】
上記実施例によれば、多数ノードからなるネットワークシステムにおいて、多重化された経路毎の各ノードの重要度から経路の評価値を計算し、評価値に基づいて対象ノードに優先順位を付けることで、保守（または整備）対象のノードの検出を高速化できる。【０１１９】
センサデータの完全性を保証する必要のあるシステムへの応用例として、例えば課金データを扱うシステムが挙げられる。課金データは、１つでも失われると大きな問題となるため、センサネットワークシステムによってこのようなデータの収集を行う際には、障害によるネットワークシステム機能の停止への対応が重要となる。障害の起こる可能性をできるだけ減らすために予防的な整備を行う場合（例えば、古くなった機器を置き換える場合）、整備に割くことのできるリソースは有限なので、大きな影響の出そうなところから保守（または整備）を進めることで、ネットワークシステム全体としてデータ喪失のリスクを抑えることが可能となる。或いは、ネットワークシステム内で実際に障害が発生した後でも、複数の障害が発生した場合にどの障害の緊急性が高いかを判断し、障害の優先度順に対処することによって、データ喪失のリスクを抑えることが可能となる。【０１２０】
以上、開示の無線端末、重要度生成方法及び無線通信システムを実施例により説明したが、本発明は上記実施例に限定されるものではなく、本発明の範囲内で種々の変形及び改良が可能であることは言うまでもない。
【符号の説明】
【０１２１】
１      アドホックネットワークシステム
５      ノード
１１      プロセッサ
１２      メモリ
１３      送受信機
１４      センサ
１５      バス
１６      アンテナ
２１      制御プログラム
２２      テーブル類
【図１】
2014192142.tif 000003
【図２】
2014192142.tif 000004
【図３】
2014192142.tif 000005
【図４】
2014192142.tif 000006
【図５】
2014192142.tif 000007
【図６】
2014192142.tif 000008
【図７】
2014192142.tif 000009
【図８】
2014192142.tif 000010
【図９】
2014192142.tif 000011
【図１０】
2014192142.tif 000012
【図１１】
2014192142.tif 000013
【図１２】
2014192142.tif 000014
【図１３】
2014192142.tif 000015
【図１４】
2014192142.tif 000016
【図１５】
2014192142.tif 000017
【図１６】
2014192142.tif 000018
【図１７】
2014192142.tif 000019
【図１８】
2014192142.tif 000020
【図１９】
2014192142.tif 000021
【図２０】
2014192142.tif 000022
【図２１】
2014192142.tif 000023
【図２２】
2014192142.tif 000024
【図２３】
2014192142.tif 000025
【図２４】
2014192142.tif 000026
【図２５】
2014192142.tif 000027
【図２６】
2014192142.tif 000028
【図２７】
2014192142.tif 000029
【図２８】
2014192142.tif 000030
【図２９】
2014192142.tif 000031
【図３０】
2014192142.tif 000032
【図３１】
2014192142.tif 000033
【手続補正書】
【提出日】平成27年12月2日(2015.12.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムの無線端末であって、
発信ノードから発信されたデータの最終的な宛先となる目的ノードを形成し、
前記ネットワークシステム内の中継ノードから受信したパケットに含まれ前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットに基づいて、送信元ノードと送信先ノードの各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算する手段と、
前記中継ノードの障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成する手段
を備えたことを特徴とする、無線端末。
【請求項２】
多重化された経路毎の各ノードの重要度から経路の評価値を計算する手段をさらに備え、
前記評価値に基づいて保守の対象となるノードに優先順位を付けて前記保守の対象となるノードを絞り込む
ことを特徴とする、請求項１記載の無線端末。
【請求項３】
複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムの無線端末であって、
発信ノードから発信されたデータの最終的な宛先となる目的ノード以外のノードを形成し、
前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットを調べて記憶装置に記憶する手段と、
自ノードと相互に接続する他ノードに前記分断ポイントセットを含むパケットを送信する手段
を備えたことを特徴とする、無線端末。
【請求項４】
複数のノード間の経路が環境に応じて動的に調整されるネットワークシステムにおいて各ノードの重要度を生成する重要度生成方法であって、
各ノードが、前記ネットワークシステム内の経路を分断するノードを分断ポイントとする分断ポイントセットを調べて記憶装置に記憶し、
各ノードが、自ノードと相互に接続する他ノードに前記分断ポイントセットを含むパケットを送信し、
発信ノードから発信されたデータの最終的な宛先となる目的ノードが、中継ノードから受信したパケットに含まれる前記分断ポイントセットに基づいて、送信元ノードと送信先ノードの各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算し、前記中継ノードの障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成する
ことを特徴とする、重要度生成方法。
【請求項５】
前記目的ノードが、多重化された経路毎の各ノードの重要度から経路の評価値を計算し、
前記評価値に基づいて保守の対象となるノードに優先順位を付けて前記保守の対象となるノードを絞り込む
ことを特徴とする、請求項４記載の重要度生成方法。
【請求項６】
各ノードが、自ノードと相互に接続する他ノードから、前記目的ノードへパケットを送信する際の経路を示す経路情報と各経路の経路数を含むパケットを受信し、前記経路情報と各経路の経路数を前記記憶装置に記憶する
ことを特徴とする、請求項４または５記載の重要度生成方法。
【請求項７】
複数の無線端末間の経路が環境に応じて動的に調整されるネットワークシステムを有する無線通信システムであって、
各無線端末は、
前記ネットワークシステム内の経路を分断する無線端末を分断ポイントとする分断ポイントセットを調べて記憶装置に記憶し、
自無線端末と相互に接続する他無線端末に前記分断ポイントセットを含むパケットを送信し、
発信無線端末から発信されたデータの最終的な宛先となる目的無線端末は、
中継無線端末から受信したパケットに含まれる前記分断ポイントセットに基づいて、送信元無線端末と送信先無線端末の各対に対してどこを分断すると伝送が途絶するかを表す分断確率を計算し、前記中継無線端末の障害が前記ネットワークシステムに及ぼす影響を伝送の障害確率で表す重要度を生成する
ことを特徴とする、無線通信システム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
【図１】アドホックネットワークシステムの全体構成の一例を示す図である。
【図２】一実施例におけるノードの構成の一例を示すブロック図である。
【図３】ノードの機能ブロック図である。
【図４】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図５】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図６】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図７】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図８】Ｈｅｌｌｏパケットに基づく経路情報の生成処理の一例を説明する図である。
【図９】経路情報が有する各経路と経路数の一例を説明する図である。
【図１０】送信元無線端末と送信先無線端末間の経路数の抽出処理の一例を説明する図である。
【図１１】代替経路数の計算方法の一例を説明する図である。
【図１２】図４〜図８の具体例における代替経路数の一例を説明する図である。
【図１３】ノードにおける処理の一例を説明するフローチャートである。
【図１４】ゲートウェイにおける処理の一例を説明するフローチャートである。
【図１５】アドホックネットワークシステムの一例を示す図である。
【図１６】図１５に示すアドホックネットワークシステムについて、送信元ノード、分断ポイントを構成するノード数、分断確率の近似値、及び代替経路数の一例を示す図である。
【図１７】ノードにおけるデータパケットの送信処理の一例を説明するフローチャートである。
【図１８】分断ポイントセットの計算方法の第１の例を説明する図である。
【図１９】分断ポイントセットの計算方法の第２の例を説明する図である。
【図２０】分断ポイントセットの計算方法の第３の例を説明する図である。
【図２１】経路変更の第１の例を説明する図である。
【図２２】経路変更の第２の例を説明する図である。
【図２３】ノードにおける分断ポイントセットと経路テーブルの一例を示す図である。
【図２４】ノードにおけるＨｅｌｌｏパケットの送信処理の一例を説明するフローチャートである。
【図２５】Ｈｅｌｌｏヘッダの一例を示す図である。
【図２６】ノードにおけるＨｅｌｌｏパケットの受信処理の一例を説明するフローチャートである。
【図２７】ノードにおけるデータパケットの受信処理の一例を説明するフローチャートである。
【図２８】ノードにおけるデータパケットの再送処理の一例を説明するフローチャートである。
【図２９】データ管理テーブルのレコードの一例を示す図である。
【図３０】目的ノードにおける重要度生成処理の一例を説明するフローチャートである。
【図３１】目的ノードにおける分断ポイントテーブルと重要度テーブルの一例を説明する図である。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
図５の（４）において、ノードｂはノードｃ、ノードａ及びノードｄにＨｅｌｌｏパケットＨ４１〜Ｈ４３を送信する。ノードａは、ノードｂからＨｅｌｌｏパケットＨ４１を受信すると、ノードｂ（Ｔ）までの経路情報とその経路数１（ｋ）、及び、ノードｂ（ｌ）をリンクするノードｃ（Ｔ）までの経路情報とその経路数１（ｋ）を経路テーブルＴａ−４に追加する。また、ノードｂの経路テーブルＴｂ−３は、ゲートウェイＧＷを送信先（Ｔ）とし、ノードｃ（ｌ）またはノードｄ（ｌ）をリンクする２つの経路情報を有する。このため、ノードａは、ノードｂ（ｌ）をリンクするゲートウェイＧＷ（Ｔ）までの経路情報とその経路数２（ｋ）を経路テーブルＴａ−４に追加する。このように、ノード５は、リンク（ｌ）と送信先ノード５までの経路が複数ある場合、各リンクの経路数の和を経路テーブルに格納する。同様にして、ＨｅｌｌｏパケットＨ４２，Ｈ４３に基づいて、経路テーブルＴｃ−４，Ｔｄ−４が更新される。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５８
【補正方法】変更
【補正の内容】
【００５８】
なお、図８において前述したとおり、例えば経路のホップ数に基づいて、検出される経路が制限されても良い。これにより、非効率な経路が除外され、計算される代替経路数の誤差が回避される。例えば、送信元ノード５から送信先ノード５までの経路総数には非効率な経路の数が含まれ、ノード５を中継する経路数には非効率な経路の数が含まれない場合、計算される代替経路数は誤差を含んでしまう。このため、代替経路数の精度を向上するために、例えば経路は最短のホップ数から所定のホップ分だけ長い経路以内に制限される。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
図１４は、ゲートウェイにおける処理の一例を説明するフローチャートである。この例では、ゲートウェイＧＷは目的ノードの一例である。図１４において、ステップＳ１２１では、ゲートウェイＧＷは、時刻ＴＴＷ３が現時刻と一致するか否かを判定する。時刻ＴＴＷ３は、ノード５の重要度の計算（または、生成）後に、現時刻の重要度の計算（または、生成）周期後の時刻を示す。時刻ＴＴＷ３が現時刻と一致してステップＳ１２１の判定結果がＹＥＳの場合、ステップＳ１２２では、ゲートウェイＧＷは、重要度テーブルの形成を行い、処理はステップＳ１２１へ戻る。重要度テーブルは、送信元ノード５毎に重要度を記述したテーブルであり、この重要度テーブルによって複数のノード５の障害に対応する場合の優先順位を付けることができる。ゲートウェイＧＷの構成がノード５の構成と同じ場合、重要度テーブルは、図２に示す各種テーブル２２に含まれる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
一方、時刻ＴＴＷ３が現時刻と一致せずステップＳ１２１の判定結果がＮＯの場合、ステップＳ１２３では、ゲートウェイＧＷは、データパケットを受信したか否かを判定する。データパケットを受信しておらずステップＳ１２３の判定結果がＮＯの場合、処理はステップＳ１２１へ戻る。データパケットを受信しておりステップＳ１２３の判定結果がＹＥＳの場合、ステップＳ１２４では、ゲートウェイＧＷは、送信元ノード５にＡＣＫを送信する。ステップＳ１２５では、ゲートウェイＧＷは、受信したデータパケットのデータ部分から発信ノード５の分断ポイントセットを抽出して分断ポイントテーブルに登録する。分断ポイントセットとは、後述するように、発信ノード５から目的ノード５までの経路を分断するノード５のセットである。また、分断ポイントテーブルとは、後述するように、発信ノード５と、発信ノード５に対する分断ポイントセットとを含む。ステップＳ１２６では、ゲートウェイＧＷは、受信したデータパケットの残りの部分の処理を行い、処理はステップＳ１２１へ戻る。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
受信したデータパケットに対応するエントリがデータ管理テーブルＴｍに登録されておらずステップＳ７１の判定結果がＮＯの場合、或いは、ステップＳ７２の後、ステップＳ７３では、データパケット受信部４４は、受信したデータパケットに対応するエントリがデータ管理テーブルＴｍに登録されていたか否かに関わらず、データパケットを受信したことを示すＡＣＫを、データパケットの送信元ノードに送信する。
【国際調査報告】
2014192142.tif 000034
2014192142.tif 000035
2014192142.tif 000036
2014192142.tif 000037
2014192142.tif 000038
2014192142.tif 000039
2014192142.tif 000040