(57)【要約】【課題】低速／省電力の無線端末装置において使用可能なマルチホップピア・ツー・ピア通信プロトコルを提供する【解決手段】本プロトコルにおいては隣接する端末間のリンク状態情報は必要なときのみ端末間で相互に交換される。すなわち、リンク状態情報が収束した後、リンク状態情報に変化が生じたことを端末間の通信を通じて端末が検知したときにリンク状態情報を交換する。リンク状態情報の送受信の頻度を少なくすることができ、端末の消費電力を低減することができる。【選択図】        図２
2004320658.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線端末を含むワイヤレスネットワークにおいてマルチホップピア・ツー・ピア通信を行うための方法であって、
端末がネットワークに加入するための起動パケットを送信するステップと、
前記起動パケットを受けて自分のリンク状態情報を更新するとともに、前記リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
前記経路変換行列を受けて自分のリンク状態情報を更新するとともに、更新された結果自分のリンク状態情報が変化したとき更新されたリンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
メッセージの受信及び中継を行うステップと、
メッセージを送信するステップとを備え、
さらに、隣接する端末間のリンク状態を記述するためのマトリックスを作成し、前記マトリックスの第１の部分に他の端末から受けた前記経路変換行列により更新されたリンク状態情報を格納し、第２の部分に他の端末との通信により直接検出したリンク状態情報を格納するステップと、
前記第１の部分のリンク状態情報と前記第２の部分のリンク状態情報を比較して両者が一致しないときに、前記第１の部分のリンク状態情報を修正し、当該リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップとを備えることを特徴とするマルチホップピア・ツー・ピア通信を行うための方法。
【請求項２】
所定回数以上メッセージを再送してもアクノリッジが返らないときに送信先の端末が削除されたと判定し、端末削除パケットを送信するステップと、
前記端末削除パケットを受けて、自分のリンク状態情報から当該端末を削除するステップとを備えることを特徴とする請求項１記載のマルチホップピア・ツー・ピア通信を行うための方法。
【請求項３】
メッセージの中継を行った後において、送信先の端末から前記メッセージと同じメッセージを受信したとき、メッセージの中継が成功したと判定するステップを備えることを特徴とする請求項１記載のマルチホップピア・ツー・ピア通信を行うための方法。
【請求項４】
メッセージの受信及び中継を行う前記ステップは、
メッセージを受信するステップと、
前記メッセージが処理済であるか判定するステップと、
前記メッセージが処理済であるときに、前記メッセージの中継が成功しているかどうか判定するステップと、
前記メッセージが処理済であり、かつ、前記メッセージの中継が成功しているときに、前記メッセージを破棄するステップと、
前記メッセージが処理済でないとき、又は、前記メッセージの中継が成功していないときに、前記メッセージを再度送信するステップと、を備えることを特徴とする請求項１記載のマルチホップピア・ツー・ピア通信を行うための方法。
【請求項５】
ワイヤレスネットワークを構成する無線端末の通信方法であって、
ネットワークに加入するための起動パケットを送信するステップと、
他の端末から前記起動パケットを受けたとき、自分のリンク状態情報を更新するとともに、前記リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
他の端末から前記経路変換行列を受けたとき、自分のリンク状態情報を更新するとともに、更新された結果自分のリンク状態情報が変化したとき更新されたリンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
メッセージの受信及び中継を行うステップと、
メッセージを送信するステップとを備え、
さらに、隣接する端末間のリンク状態を記述するためのマトリックスを作成し、前記マトリックスの第１の部分に他の端末から受けた前記経路変換行列により更新されたリンク状態情報を格納し、第２の部分に他の端末との通信により直接検出したリンク状態情報を格納するステップと、
前記第１の部分のリンク状態情報と前記第２の部分のリンク状態情報を比較して両者が一致しないときに、前記第１の部分のリンク状態情報を修正し、当該リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップとを備えることを特徴とする無線端末の通信方法。
【請求項６】
プロセッサに、ワイヤレスネットワークを構成する無線端末の通信方法を行わせるためのプログラムであって、
ネットワークに加入するための起動パケットを送信するステップと、
他の端末から前記起動パケットを受けたとき、自分のリンク状態情報を更新するとともに、前記リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
他の端末から前記経路変換行列を受けたとき、自分のリンク状態情報を更新するとともに、更新された結果自分のリンク状態情報が変化したとき更新されたリンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
メッセージの受信及び中継を行うステップと、
メッセージを送信するステップとを備え、
さらに、隣接する端末間のリンク状態を記述するためのマトリックスを作成し、前記マトリックスの第１の部分に他の端末から受けた前記経路変換行列により更新されたリンク状態情報を格納し、第２の部分に他の端末との通信により直接検出したリンク状態情報を格納するステップと、
前記第１の部分のリンク状態情報と前記第２の部分のリンク状態情報を比較して両者が一致しないときに、前記第１の部分のリンク状態情報を修正し、当該リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップとを実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ワイヤレスネットワークにおいてマルチホップＰｅｅｒ−ｔｏ−Ｐｅｅｒ通信を行うためのプロトコル及び無線端末装置の通信方法に関する。
【０００２】
【従来の技術】
従来のこの種のルーティングプロトコルは、隣接する端末間でリンク状態を一定間隔ごとに相互に交換し、データ送信のタイミングと無関係にルーティングテーブルをあらかじめ構築しておくｐｒｏａｃｔｉｖｅ型のものであった。その際、各端末は自分の知っているすべてのリンク情報を一度に交換するのではなく、端末のスコープ（相手までのホップ数）に応じてリフレッシュレートを変化させている。なぜならモバイル環境では経路の変化が激しいため、必要以上に遠いスコープにある端末のリンク情報は、それが相手にリレー伝達されるまでに無効になっている確率が高いためである。この工夫によって、リンク情報交換のために定期的に消費する通信帯域を低く押さえると同時に、自分にとって重要な数ホップ圏内の経路情報を安定して取得可能となる。
【０００３】
上述のように各端末は所定数のホップ圏内の端末のリンク状態のみを持ち、当該ホップ圏外の端末についてのリンク情報を持たない。そうすると、ホップ圏外の同士がパケットを交換するためにブロードキャストしか使えないことになり、ホップ数の短さに比べて非効率的である。そこでパケット構造を利用したｏｎ−ｄｅｍａｎｄ型のソースルーティングを併用している。このルーティングを実現するための経路スタックテーブルを利用する。
【０００４】
従来のプロトコルでは、パケットが端末を通過する度にその途中経路情報をパケット内部に記憶させておく。これを経路スタックと呼ぶ。また、パケットはこの経路スタックから次に取得すべき値の場所を指し示すスタックポインタを持っている。データの送信元端末がパケットをブロードキャストすることにより、目的の端末に辿り着いた時点でそのパケットの経路スタックには送信元への戻り経路が詰め込まれていることになる。
【０００５】
端末がパケットを送り返す時（ｓｅｎｄｂａｃｋ  ｕｎｉｃａｓｔ）には、途中経路の端末はスタックポインタを移動させると同時にリンクＩＤまたはＩｄｅｎｔｉｔｙを取り出し、その値に対応する隣接端末へパケットを転送する。この処理を途中経路の各端末が行うことでデータを送信元へ送り返すことが可能である。この処理は経路表を引く必要がないため転送速度が高速である。
【０００６】
送信元の端末は送り返されたパケットの経路スタックに基づき目的端末へパケットを送ることができる。
【０００７】
【発明が解決しようとする課題】
ところで、低速／省電力の無線端末装置を用いるシステムとして、温度、湿度等のデータをセンサで検出し、それを無線で収集するセンサーネットワークがある。センサーネットワークのような用途では、無線モジュール自体が低速で動作し低機能であり、通信処理を行うためのＣＰＵのメモリーも限られた量しかない、というような制約が課されている。このような用途には、従来のようなパソコンと無線ＬＡＮを対象にしたマルチホップＰｅｅｒ−ｔｏ−Ｐｅｅｒ通信の方法／装置よりも、さらに小型、省電力なマルチホップＰｅｅｒ−ｔｏ−Ｐｅｅｒ通信の方法／装置が求められている。
【０００８】
従来のマルチホップＰｅｅｒ−ｔｏ−Ｐｅｅｒ通信の方法／装置を低速／省電力の無線端末装置を用いるシステムに適用すると次のような問題がある。
（１）リンク状態を定期的に交換するため消費電力が大きい。電池を頻繁に交換しなければならず、保守にコストがかかる。
（２）低速／省電力の無線端末装置は外部から影響を受けやすく、送信中にデータの欠落が生じやすい。データの再送機能を充実させる必要がある。
（３）メモリ容量が小さい。プログラムやデータサイズは小さくなければならない。
【０００９】
以上の点に鑑み、この発明は、低速／省電力の無線端末装置においてマルチホップＰｅｅｒ−ｔｏ−Ｐｅｅｒ通信を実現できるプロトコルを提供することを目的とする。
【００１０】
【課題を解決するための手段】
この発明は、複数の無線端末を含むワイヤレスネットワークにおいてマルチホップピア・ツー・ピア通信を行うための方法であって、
端末がネットワークに加入するための起動パケットを送信するステップと、
前記起動パケットを受けて自分のリンク状態情報を更新するとともに、前記リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
前記経路変換行列を受けて自分のリンク状態情報を更新するとともに、更新された結果自分のリンク状態情報が変化したとき更新されたリンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
メッセージの受信及び中継を行うステップと、
メッセージを送信するステップとを備え、
さらに、隣接する端末間のリンク状態を記述するためのマトリックスを作成し、前記マトリックスの第１の部分に他の端末から受けた前記経路変換行列により更新されたリンク状態情報を格納し、第２の部分に他の端末との通信により直接検出したリンク状態情報を格納するステップと、
前記第１の部分のリンク状態情報と前記第２の部分のリンク状態情報を比較して両者が一致しないときに、前記第１の部分のリンク状態情報を修正し、当該リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップとを備えることを特徴とするマルチホップピア・ツー・ピア通信を行うものである。
【００１１】
好ましくは、
所定回数以上メッセージを再送してもアクノリッジが返らないときに送信先の端末が削除されたと判定し、端末削除パケットを送信するステップと、
前記端末削除パケットを受けて、自分のリンク状態情報から当該端末を削除するステップとを備える。
【００１２】
好ましくは、メッセージの中継を行った後において、送信先の端末から前記メッセージと同じメッセージを受信したとき、メッセージの中継が成功したと判定するステップを備える。
【００１３】
好ましくは、
メッセージの受信及び中継を行う前記ステップは、
メッセージを受信するステップと、
前記メッセージが処理済であるか判定するステップと、
前記メッセージが処理済であるときに、前記メッセージの中継が成功しているかどうか判定するステップと、
前記メッセージが処理済であり、かつ、前記メッセージの中継が成功しているときに、前記メッセージを破棄するステップと、
前記メッセージが処理済でないとき、又は、前記メッセージの中継が成功していないときに、前記メッセージを再度送信するステップと、を備える。
【００１４】
この発明は、ワイヤレスネットワークを構成する無線端末の通信方法であって、
ネットワークに加入するための起動パケットを送信するステップと、
他の端末から前記起動パケットを受けたとき、自分のリンク状態情報を更新するとともに、前記リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
他の端末から前記経路変換行列を受けたとき、自分のリンク状態情報を更新するとともに、更新された結果自分のリンク状態情報が変化したとき更新されたリンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
メッセージの受信及び中継を行うステップと、
メッセージを送信するステップとを備え、
さらに、隣接する端末間のリンク状態を記述するためのマトリックスを作成し、前記マトリックスの第１の部分に他の端末から受けた前記経路変換行列により更新されたリンク状態情報を格納し、第２の部分に他の端末との通信により直接検出したリンク状態情報を格納するステップと、
前記第１の部分のリンク状態情報と前記第２の部分のリンク状態情報を比較して両者が一致しないときに、前記第１の部分のリンク状態情報を修正し、当該リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップとを備えるものである。
【００１５】
この発明は、プロセッサに、ワイヤレスネットワークを構成する無線端末の通信方法を行わせるためのプログラムであって、
ネットワークに加入するための起動パケットを送信するステップと、
他の端末から前記起動パケットを受けたとき、自分のリンク状態情報を更新するとともに、前記リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
他の端末から前記経路変換行列を受けたとき、自分のリンク状態情報を更新するとともに、更新された結果自分のリンク状態情報が変化したとき更新されたリンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップと、
メッセージの受信及び中継を行うステップと、
メッセージを送信するステップとを備え、
さらに、隣接する端末間のリンク状態を記述するためのマトリックスを作成し、前記マトリックスの第１の部分に他の端末から受けた前記経路変換行列により更新されたリンク状態情報を格納し、第２の部分に他の端末との通信により直接検出したリンク状態情報を格納するステップと、
前記第１の部分のリンク状態情報と前記第２の部分のリンク状態情報を比較して両者が一致しないときに、前記第１の部分のリンク状態情報を修正し、当該リンク状態情報に基づき経路変換行列を作成し、他の端末へ前記経路変換行列を送るステップとを実行させるためのプログラムである。
【００１６】
この発明に係るプログラムは、例えば、記録媒体に記録される。
媒体には、例えば、ＥＰＲＯＭデバイス、フラッシュメモリデバイス、フレキシブルディスク、ハードディスク、磁気テープ、光磁気ディスク、ＣＤ（ＣＤ−ＲＯＭ、Ｖｉｄｅｏ−ＣＤを含む）、ＤＶＤ（ＤＶＤ−Ｖｉｄｅｏ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭを含む）、ＲＯＭカートリッジ、バッテリバックアップ付きのＲＡＭメモリカートリッジ、フラッシュメモリカートリッジ、不揮発性ＲＡＭカートリッジ等を含む。
【００１７】
また、電話回線等の有線通信媒体、マイクロ波回線等の無線通信媒体等の通信媒体を含む。インターネットもここでいう通信媒体に含まれる。
【００１８】
媒体とは、何等かの物理的手段により情報（主にデジタルデータ、プログラム）が記録されているものであって、コンピュータ、専用プロセッサ等の処理装置に所定の機能を行わせることができるものである。
【００１９】
【発明の実施の形態】
発明の実施の形態に係る無線端末装置１の概略ブロック図を図１に示す。１０は処理部（ＣＰＵ）であり、図示しないＲＯＭ、ＲＡＭ、Ｉ／Ｏなどを備える。ＲＯＭには後述の各シーケンスを実行するためのプログラムが記憶されている。ＲＡＭには各種データが記憶され、各種バッファ、フラグ、テーブルとして機能する。１１は微弱無線モジュールであり、例えば数十ｍ内にある他の無線端末装置と通信することができる。通信速度は数百ｂｐｓ程度であり低速である。１２は温度などを測定するセンサ、１３は電源としての電池である。
【００２０】
無線端末装置１はさまざまな場所に設置され、例えばその場所の温度等のデータを収集し、それをサーバ等へ送信するためのものである。複数の無線端末装置１が互いに通信可能な間隔で設置されていれば、本発明の実施の形態に係るマルチホップＰｅｅｒ−ｔｏ−Ｐｅｅｒ通信プロトコルによりデータをリレー式にサーバへ送ることができ、そのための通信回線を特に設ける必要はない。無線端末装置１は電池で長時間動作するように消費電流は小さい。例えば、送信時に約２０ｍＡ、受信時に約１０ｍＡ、受信待機時に約１ｍＡである。送信の際に最も電流を消費するので、送信動作をなるべく少なくすることが好ましい。この発明の実施の形態に係るプロトコルは送信動作の低減を可能にしている。
【００２１】
以下、本発明の実施の形態に係る装置／方法の動作を詳細に説明する。
まず、その説明中の用語について簡単に説明する。
ノードとは、本方法が実行される無線デバイスのことである。
ホップとは送受信の経路のことで、ノードが他のノードの中継なしに直接データを送受信できる関係を１ホップと呼ぶ。
隣接ノードとは、あるノードから見て１ホップで通信できる全てのノードのことである。
ブロードキャストとは、ノードが装備する無線メディアの同報機能を利用して、隣接ノードにデータを一斉送信することである。
【００２２】
１．概要
本方法における動作を規定するシーケンスは以下の９パターンに分類される。
・初期ディスカバリーシーケンス（端末がネットワークに加入するための起動パケット（ＷＡＫＥＵＰパケット）を送信するシーケンス）
・受信待機シーケンス
・初期ディスカバリー受信シーケンス（ＷＡＫＥＵＰパケットを受けて自分のリンク状態情報を更新するとともに、他のノードへ経路変換行列を送るシーケンス）
・経路変換行列受信シーケンス（経路変換行列を受けて自分のリンク状態情報を更新するシーケンス）
・端末削除処理シーケンス（あるノードがなくなったと判定されたときに送られる端末削除パケットを受けて、自分のリンク状態情報から当該ノードを削除するシーケンス）
・メッセージ処理シーケンス（メッセージの受信、中継、再送、アクノリッジパケットの送信、端末削除パケットの送信を行うシーケンス）
・アクノリッジパケット処理シーケンス（アクノリッジパケットを受けたときのシーケンス）
・送信シーケンス（データや経路変換行列情報を送信するシーケンス）
・テーブル欠損確認シーケンス
これらシーケンスの関係を図２に示す。
【００２３】
２．各シーケンスの動作
電源投入またはリセットの後、あるいは指定されたトリガーが外部から与えられた場合、端末は初期ディスカバリーシーケンスに移行する。本方法におけるデータの送信はデータ送信シーケンスに従う。また、バックグラウンドでテーブル欠損確認シーケンスを行う。
【００２４】
２．１  初期ディスカバリーシーケンス（図３参照）
（１）周囲の端末に対して”ＷＡＫＥＵＰパケット”をブロードキャストする（Ｓ２−１）。
（２）受信待機シーケンスへ移行する。
【００２５】
２．２  受信待機シーケンス（図４参照）
（１）微弱無線からデータの受信があるまで待機する（Ｓ２−２ａ，Ｓ２−２ｂ）。
（２）１パケット受信したらパケット内容を確認する。
（２．１）”ＷＡＫＥＵＰパケット”なら、初期ディスカバリー受信シーケンスへ移行する（Ｓ２−２−１）。
（２．２）”経路変換行列パケット”なら、経路変換行列受信シーケンスへ移行する（Ｓ２−２−２）。
（２．３）”端末削除パケット”なら、端末削除処理シーケンスへ移行する（Ｓ２−２−３）。
（２．４）”メッセージ送信パケット”なら、メッセージ処理シーケンスへ移行する（Ｓ２−２−４）。
（２．５）”アクノリッジパケット”なら、アクノリッジパケット処理シーケンスへ移行する（Ｓ２−２−５）。
【００２６】
２．３  初期ディスカバリーシーケンス（図５参照）
（１）微弱無線のデータフレームから送信元アドレスを取得し（Ｓ２−３−１ａ）、一旦送信元アドレスに関するリンク状態情報を破棄する（Ｓ２−３−１ｂ）。この送信元アドレスのノードが隣接しているという前提で、改めて”ＷＡＫＥＵＰパケット”の送信元を隣接ノードテーブルへ追加する（Ｓ２−３−１ｃ）。
（２）以下の処理を行う。
（２．１）自身がデータ送信中であるかどうか判定し（Ｓ２−３−２−１ａ）、データ送信中でなければ（Ｓ２−３−２−２）へ処理を移し、データ送信中であれば送信バッファに蓄積する（Ｓ２−３−２−１ｂ）。
（２．２．）自身のリンク状態情報を経路変換行列に変換し、ブロードキャストする（Ｓ２−３−２−２）。
２．４  経路変換行列受信シーケンス（図６参照）
（１）経路変換行列情報を受信する（Ｓ２−４−１ａ）。経路情報のページ番号、最大ページ番号を読みこむ（Ｓ２−４−１ｂ）。
（１．１）受け取った経路情報のページ番号が、直前に受け取った経路情報の次ページ番号でなければ（Ｓ２−４−１−１ａでＮＯ）、経路情報全体を破棄して１へ戻る（Ｓ２−４−１−１ｂ）。
（１．２）経路情報の最大ページ番号が受信したページ番号より大きいならば、後続するページの受信を行う（Ｓ２−４−１−２でＹＥＳ）。
（２）微弱無線のデータフレームから送信元アドレスを取得（Ｓ２−４−２ａ）、”経路変換行列パケット”の送信元を隣接ノードテーブルへ追加する（Ｓ２−４−２ｂ）。
（３）経路変換行列情報をページ番号に従ってマージし（Ｓ２−４−３ａ）、そこからリンク状態情報へ変換する（Ｓ２−４−３ｂ）。同時にリンク状態情報のテーブル補完を行う（Ｓ２−４−３ｃ）。
（３．１）受信した経路変換情報で「可視」となっている端末はリンク状態情報でも可視とする。
（３．２）受信した経路変換情報で「不可視」となっている端末はリンク状態情報を変更しない。
（４）２，３の結果、リンク状態情報に変化がなければ受信シーケンスを終了する（Ｓ２−４−４ａ）。変化があった場合、または、経路変換行列情報に再送フラグがセットされていたら（Ｓ２−４−４ｂ）、以下の処理を行う。
（４．１）データ送信中でなければ（４．２）へ、データ送信中であれば送信バッファに蓄積する（Ｓ２−４−４−１ｂ）。
（４．２）自分のＩＤ番号に応じた待ち時間［参考値：（ＩＤ  ％  １６）×２．５秒］の間待機する（Ｓ２−４−４−２）。これは複数の端末による送信が相互に衝突しないようにするためである（以下同様）。
（４．３）自身のリンク状態情報を経路変換行列に変換し、ブロードキャストする（Ｓ２−４−４−３）。
【００２７】
２．５  端末削除処理シーケンス（図７参照）
（１）微弱無線のデータフレームから送信元アドレスを取得（Ｓ２−５−１ａ）、”端末削除パケット”の送信元を隣接ノードテーブルへ追加する（Ｓ２−５−１ｂ）。
（２）端末削除パケットに書き込まれている「削除されるべき端末」をリンク状態情報から削除する（Ｓ２−５−２）。
（３）１，２の結果、リンク状態情報に変化がなければ端末削除処理シーケンスを終了する（Ｓ２−５−３）。変化があった場合は以下の処理を行う。
（３．１）データ送信中でなければ（Ｓ２−５−３−２）へ、データ送信中であれば送信バッファに蓄積する（Ｓ２−５−３−１ｂ）。
（３．２）自分のＩＤ番号に応じた待ち時間［参考値：（ＩＤ  ％  １６）×２．５秒］の間待機する（Ｓ２−５−３−２）。
（３．３）端末削除情報をブロードキャストする（Ｓ２−５−３−３）。
【００２８】
２．６  メッセージ処理シーケンス（図８〜図１０参照）
（１）メッセージ送信主ＩＤとメッセージＩＤを確認し（Ｓ２−６−１ａ）、処理済メッセージＩＤバッファと比較する（Ｓ２−６−１ｂ）。本発明の実施の形態においてはデータ送信はもっぱらブロードキャストを用いて行われるので、同じメッセージが他の端末から送られて来たり、同じ端末から再送されて来たりして、何度も受信することが考えられるので、この処理が必要である。同じメッセージを受けた場合、アクノリッジが未確認であったり、再送要求があったときのみ、データを送信する。これにより消費電力を減らすことができる。
（１．１）すでに処理したことのあるメッセージならアクノリッジ未確認フラグを調べる（Ｓ２−６−１−１）。
（１．１．１）アクノリッジ未確認フラグがセットされていれば２へ
（１．１．２）アクノリッジ未確認フラグがクリアされていれば３へ
（１．２）未処理ならば処理済メッセージＩＤバッファへＩＤを追加し、アクノリッジ未確認フラグをクリアする（Ｓ２−６−１−２）。
（１．３）処理済メッセージＩＤバッファは最新８メッセージのみ保存し、古いものから順に破棄する。
（２）メッセージ送信パケット内に書き込まれたＩＤと微弱無線（中継端末）のデータフレーム内のＩＤを比較し（Ｓ２−６−２）
（２．１）送信先ＩＤが自身のＩＤと一致したら（Ｓ２−６−２−１）
（２．１．１）既に処理したことのあるメッセージであれば
（２．１．１．１）再送フラグがセットされていたら５へ移行する。受信した旨のアクノリッジを返すためである。
（２．１．１．２）再送フラグがクリアされていれば破棄する（Ｓ２−６−２−１−１−２）。他の端末から同じデータが送られてきたと考えられるからである。
（２．１．２）処理したことのないメッセージであれば４へ移行する（Ｓ２−６−２−２からＳ２−６−４へ）。
（２．２）送信先ＩＤ、送信元ＩＤ、自身のＩＤ、微弱無線送信元ＩＤ（中継した端末のＩＤ）を比較し（Ｓ２−６−２−２）
（２．２．１）微弱無線送信元ＩＤ→送信先ＩＤの経路内に自身のＩＤが含まれる場合（自身がデータを中継した場合）
（２．２．１．１）既に処理したことのあるメッセージであれば
（２．２．１．１．１）再送フラグがセットされていたらメッセージ５へ移行する。例えば同じ中継端末から繰り返し同じデータを受信したときに、受信した旨のアクノリッジを返すためである。
（２．２．１．１．２）再送フラグがクリアされていたら破棄する（Ｓ２−６−２−２−１−１−２）。データを中継済みだからである。
（２．２．１．２）処理したことのないメッセージであれば中継端末ＩＤを書き換えたＩＤパケットをブロードキャストし（Ｓ２−６−２−２−１−２ａ）、処理済メッセージＩＤバッファのアクノリッジ未確認フラグをセットする（Ｓ２−６−２−２−１−２ｂ）。この処理がデータの中継処理である。
（２．２．２）自身のＩＤ→送信先ＩＤの経路内に微弱無線送信元ＩＤが含まれる場合（データの中継を完了した後に送信先の中継端末の電波を受信した場合）、処理済メッセージＩＤバッファのアクノリッジ未確認フラグをクリアする（Ｓ２−６−２−２−２）。他の中継端末から同じデータを受信したような場合なので、データを中継済みなので再度送信する必要はない。相手の中継端末の信号を受信することにより、データの中継を確認できたことになる。
【００２９】
（３）アクノリッジ未確認フラグがセットされたまま、最後の送信から自分のＩＤ番号に応じた待ち時間［参考値：（１６−（ＩＤ  ％  １６）×３秒］の間経過したら（Ｓ２−６−３ａ）、再送処理を行う。再送時は先に送信したメッセージ送信パケットのうち、再送フラグをセットする（Ｓ２−６−３ｂ）。
（３．１）アクノリッジが確認されたらシーケンスを終了する（Ｓ２−６−３−１）。
（３．２）アクノリッジが確認されないままであれば再送を待つ。
（３．３）５回再送を行ってもアクノリッジが確認できなかった場合（Ｓ２−６−３−３）
（３．３．１）メッセージ送信先ＩＤが自身の隣接ノードであった場合（最終アクノリッジがアクノリッジパケットによって確認される場合）は（Ｓ２−６−３−３−１ａ）、送信先ノードの端末削除パケットを送信して終了する（Ｓ２−６−３−３−１ｂ）。
（３．３．２）メッセージ送信先ＩＤが自身の隣接ノードでなかった場合は終了する。
（４）（以下メッセージ送信先ＩＤが自分自身の場合）ＯＳを通じ処理ルーチンへメッセージを渡す（Ｓ２−６−４）。自分宛てのメッセージを受けて所定の処理を行う。
（５）”アクノリッジパケット”を送信する
（５．１）データ送信中でなければ５．２へ、データ送信中であれば送信バッファに蓄積する（Ｓ２−６−５−１）。
（５．２）自分のＩＤ番号に応じた待ち時間［参考値：（１６−（ＩＤ  ％  １６）×３秒］の間待機する（Ｓ２−６−５−２）。
（５．３）受信したメッセージのメッセージＩＤを受信した旨のアクノリッジパケットを送信する（Ｓ２−６−５−３）。
【００３０】
２．７  アクノリッジパケット処理シーケンス（図１１参照）
（１）微弱無線のデータフレームから送信元アドレスを取得（Ｓ２−７−１ａ）、メッセージＩＤの送信先ＩＤ、送信元ＩＤ、自身のＩＤ、微弱無線送信元ＩＤ（中継した端末のＩＤ）を比較し（Ｓ２−７−１ｂ）、
（１．１）送信先ＩＤと微弱無線送信元ＩＤが一致する場合、処理済メッセージＩＤバッファのアクノリッジ未確認フラグをクリアする（Ｓ２−７−１−１）。
（１．２）微弱無線送信元ＩＤ→送信先ＩＤの経路内に自身のＩＤが含まれる場合、パケットを破棄する（Ｓ２−７−１−２）。
（１．３）自身のＩＤ→送信先ＩＤの経路内に微弱無線送信元ＩＤが含まれる場合、処理済メッセージＩＤバッファのアクノリッジ未確認フラグをクリアする（Ｓ２−７−１−３）。
【００３１】
２．８  送信シーケンス（図１２参照）
（１）送信内容が経路変換行列情報の場合（Ｓ２−８−１）
（１．１）送信バッファに未送信データの蓄積がある場合、バッファ内未送信データと比較する（Ｓ２−８−１−１）。
（１．２）バッファ内に経路変換行列情報の送信があった場合、そのデータをクリアする（Ｓ２−８−１−２）。
（２）端末が現在微弱無線送受信中の場合（Ｓ２−８−２ａ）、送信バッファに追加して終了する（Ｓ２−８−２ｂ）。
（３）微弱無線が送信中でない場合、キャリアセンスを行う（Ｓ２−８−３）。
（３．１）キャリアを検出した場合、１秒から４秒の間でランダムな期間ウエイトする（Ｓ２−８−３）。
（４）バッファにデータが蓄積されていたら（Ｓ２−８−４ａ）、バッファの最初のデータを送信する（Ｓ２−８−４ｂ）。バッファが空であれば送信要求データを送信する（Ｓ２−８−４ｃ）。
【００３２】
２．９  テーブル欠損確認シーケンス（図１３参照）
（１）２０秒から３０秒の間のランダムな時間ごとに以下の確認を行う（Ｓ２−９−１）。
（１．１）自身のリンク状態情報を確認し、自身側からリンクしているという情報が記録されており、かつ、相手側からリンクが確認されていない、という状況のときテーブルに欠損があると判断する（Ｓ２−９−１−１）。
（１．２）テーブルに欠損を発見した場合は、自身のリンク状態情報を経路変換行列に変換し、ブロードキャストする（Ｓ２−９−１−２ａ）。その際テーブル再送フラグをセットする（Ｓ２−９−１−２ｂ）。
（１．３）同じ端末のテーブル欠損に対しては再送は最大５回までとする（Ｓ２−９−１−３）。
【００３３】
３．データフォーマット
３．１  本方法全体で使用するフレームデータフォーマット
本方法では微弱無線モジュール上での１５バイトパケットを使用して全体のデータを送受信する。当該パケットの無線フレームの定義を図１４に示す。
ＣＲＣ７はＣＲＣ部以外の１４バイトのデータに対し７ビットＣＲＣを求めたもので、全体フレームのエラーチェックに使用される。
【００３４】
Ｆｒａｍｅ＿ｔｙｐｅは以降のデータ（ＤＡＴＡ部）の種別を定義する。その定義を図１５に示す。ＤＡＴＡ［０］〜ＤＡＴＡ［１２］は１３バイトのデータで、各Ｆｒａｍｅ＿ｔｙｐｅ毎にその内容が定義される。フレームタイプで定義されないＤＡＴＡ部は０とし、ＣＲＣの計算ではこの０も計算に含まれる。
【００３５】
３．２  ＰＩＮＧパケットフォーマット
ＰＩＮＧパケットフォーマットを図１６に示す。ＳｅｎｄｅｒＩＤには、ＰＩＮＧパケットを送信したノードのＩＤ番号が入る。
【００３６】
３．３  経路変換行列パケット
経路変換行列パケットを図１７に示す。
ｐａｇｅは経路変換行列情報のページ番号である。送信する経路情報が無線モジュールの１パケットの最大サイズ（ＭＴＵ）を超える場合、経路情報を複数ページに分割して連続送信する。１パケットに納まる場合は０ｘ１が入る。
ｍａｘ＿ｐａｇｅは経路変換行列情報の最大ページ番号を表す。４ビットなので最大１５ページまで分割可能である。ページ分割がない場合は０ｘ１が入る。
ｌｉｎｅ＿ｌｅｎは経路情報の全ページを結合した後の表の中に入っているアドレスの数を８で割った数である。４ビットなので０，８，１６、・・・、１２８台までのノードを表で交換可能である。
ａｄｄｒｅｓｓ（ｎ）は端末のアドレスを示す。
ｌｉｎｅ（ｎ）は経路の接続関係を表す隣接行列である。
【００３７】
３．４  メッセージ送信パケット
メッセージ送信パケットを図１８に示す。
ＳｅｎｄｅｒＩＤにはメッセージを最初に送信したノードのＩＤ番号が入る。
ＴｏＩＤにはメッセージの送信先ノードのＩＤ番号が入る。
ＴＴＬにはＴｉｍｅ  Ｔｏ  Ｌｉｖｅ情報が入る。パケットの残存時間が記録され、中継動作されるごとに１減らされる。０になったパケットはそれ以上転送されない。
【００３８】
Ｆｌａｇｓはメッセージ送信パケットに付随する動作を示す。Ｆｌａｇｓの詳細を図１９に示す。この図において、Ｒｅｔｒｙは、このパケットがアクノリッジ確認できなかったことによる「再送されたパケット」であることを示す（Ｒｅｔｒｙｊ＝１：再送パケット）。
ＭｅｓｓａｇｅＩＤにはメッセージを一意に識別するＩＤ番号が入る。送信元のノードは起動時に乱数で初期値を設定し、その後個別のメッセージを送信するごとにインクリメントする。各ノードはメッセージ送信元のノード番号とＭｅｓｓａｇｅＩＤの組み合わせでメッセージの一意性を確認する。
Ｐａｙｌｏａｄには送信されるデータ本体が入る。このデータはそのままＯＳを通じてメッセージ処理ルーチンに引き渡される。
【００３９】
３．５  ＷＡＫＥＵＰパケット
ＷＡＫＥＵＰパケットを図２０に示す。
ＳｅｎｄｅｒＩＤには、ＷＡＫＥＵＰパケットを送信したノードのＩＤ番号が入る。受信したノードはこのノードに関する情報を一旦破棄した後、このノードが隣接しているという前提でテーブルの初期化を行う。
【００４０】
３．６  端末削除パケット
端末削除パケットを図２１に示す。
ＳｅｎｄｅｒＩＤには、端末削除パケットを送信したノードのＩＤ番号が入る。受信したノードはこのノードに関する情報を一旦破棄し、状況に応じて転送を行う。
【００４１】
３．７  アクノリッジパケットフォーマット
アクノリッジパケットフォーマットを図２２に示す。
ＳｅｎｄｅｒＩＤにはアクノリッジを返信するメッセージを最初に送信したノードのＩＤ番号が入る。
ＴｏＩＤにはアクノリッジを返信するメッセージの送信先ノードのＩＤ番号が入る。
ＭｅｓｓａｇｅＩＤにはアクノリッジを返信するメッセージを一意に識別するＩＤ番号が入る。送信元のノードは起動時に乱数で初期値を設定し、その後個別のメッセージを送信するごとにインクリメントする。
【００４２】
４．テーブルの遷移
テーブルの遷移について具体例に基づき説明する。
（１）ルーティングテーブルが空の状態のノードが４つあると想定し、説明の便宜上その通信順がＡ−Ｂ−Ｃ−Ｄとなるとする（図２３参照）。また、各ノードは他の全てと隣接ノードの関係にある。なお図においてノードＡ，Ｂ，Ｃ，Ｄの近傍の四角は各ノードのテーブルの内容を示し、ノード間の矢印はデータの流れを示し、矢印上の四角は送信されたテーブルの内容を示す。
【００４３】
テーブルの概念図を図２９に示す。自身を含む隣接するノード（図２３の例ではＡ，Ｂ，Ｃ，Ｄ）によりマトリックスが構成されている。図２９においてノードの配列ａは隣接ノードテーブルに相当し、マトリックスのデータ部ｂはリンク状態情報テーブルに相当する。リンクは双方向性をもつから、リンク状態を表現するためにはデータ部ｂだけで十分である。しかし、この発明の実施の形態において、自身と直接通信を行い、物理的なリンクを直接検出できたノードの情報を残りのデータ部ｃに記録している。データ部ｂ、ｃにおいて、１が記録されていれば対応する２つの端末間でリンクが確立されている。０が記録されていればリンクがない。１，０以外のデータ（＊）を用意し、これによりリンクの有無の未確認を示すようにしてもよい。
【００４４】
データ部ｂとｃを比較することにより、リンク状態情報テーブルの内容と実際のリンクの状態の間で矛盾が生じているかどうか判定することができる。矛盾が生じたときは、ネットワークのトポロジーが変化したと考えられるので、当該端末は経路変換行列を送信し、リンク状態情報テーブルの更新を試みる（図１３のテーブル欠損確認シーケンス参照）。
【００４５】
（２）状態１（図２４、図３０参照）：Ａがブロードキャストして自分の存在を告知する。Ｂ−Ｃ−Ｄはそれを受信し、自分のテーブルにＡと自分との位置関係を加える。
図３０において、Ａは全ての端末と通信できたのでｃ部においてＡ−Ｂ、Ａ−Ｃ、Ａ−Ｄ間のリンクを示す３つの１がセットされる。Ｂ，Ｃ，ＤにおいてはそれぞれＡから受けたテーブルに基づきｂ部においてＡの対応箇所に１がセットされ、Ａと通信できたことによりｃ部においてＡの対応箇所に１がセットされる。
【００４６】
（３）状態２（図２５、図３１参照）：ＢはＡからのブロードキャストによって自分のテーブルが更新されたので（または起動後一度もブロードキャストしていないので）、自分のテーブルをブロードキャストする。Ａ−Ｃ−Ｄはそれを受信し、自分のテーブルにＢのテーブル情報と自分との位置関係を計算し、加える。同時に他のノード間のリンクを推測し、自分のテーブル情報に加える（補完する）。
図３１において、Ｂは全ての端末と通信できたのでｃ部においてＢ−Ａ、Ｂ−Ｃ、Ｂ−Ｄ間のリンクを示す３つの１がセットされる。Ａ，Ｃ，ＤにおいてはそれぞれＢから受けたテーブルに基づきｂ部においてＢの対応箇所に１がセットされ、Ｂと通信できたことによりｃ部においてＢの対応箇所に１がセットされる。そしてこのことに基づき補完を行い、ｂ部のＢの対応箇所に１がセットされる。
【００４７】
（４）状態３（図２６、図３２参照）：前プロセスと同様にＣはブロードキャストし、Ａ−Ｂ−Ｄは受信し、それぞれテーブルを更新する。
【００４８】
（５）状態４（図２７、図３３参照）：前プロセスと同様にＤはブロードキャストし、Ａ−Ｂ−Ｃは受信し、それぞれテーブルを更新する。この時点でｂ部のテーブルが完成する。
【００４９】
（６）状態５（図２８）：Ａは自分のテーブルが更新されたことをトリガーにして、前プロセスと同様に自分のテーブル情報をブロードキャストする。Ｂ−Ｃ−Ｄは受信し、自分のテーブルと比較するが差分がないため、ここで４つのノードのテーブルが完成する。この例ではＡｘ２  Ｂ−Ｃ−Ｄｘ１の合計５回のブロードキャストが発生したことになる。
【００５０】
なお、リンク状態情報テーブル（ｂ部）が更新されて図３４のようにＡ−Ｄのリンクがなくなったとすると、ｃ部のＡ−Ｄの情報と矛盾する。ｃ部のＡ−Ｄのリンクは直接確認されたもので確実である。ｃ部のＡ−Ｄの値は１が正しい。当該Ａ−Ｄの値は０から１に直され、そして、図１３のテーブル欠損確認シーケンスに従って、Ａは経路変換行列を送信し、リンク状態情報テーブルの更新を試みる。
【００５１】
従来のマルチホップＰｅｅｒ−ｔｏ−Ｐｅｅｒ通信プロトコルにおいては、端末同士が定期的に経路表を交換していた。すなわち定期的にトラヒックが生じていた。
これに対し、本発明の実施の形態においては端末同士が経路表（リンク状態情報）を交換するが、前回の経路表と今回の経路表に差がなくなった時点で交換を停止する。経路表を交換するというフェーズ（図５、図６、図７、図１３参照）があり、そこで各端末で経路表が完成したら経路表の交換を停止するのである。このようにすることにより定期的な送受信の発生を抑えて消費電力を節約することができる。経路表の交換は定期的になされず、端末の加入等の変化が生じたときのみ経路表を交換する。データ送信は当該経路表を引きながら行う。従来のプロトコルにはあったブロードキャストして経路表を入手し、ユニキャストするやり方はない。
【００５２】
本プロトコルにおいて、端末の加入の際にはＷＡＫＥＵＰパケットを用いる（図３、図５参照）。これに対し、端末がなくなったかどうかは実際にデータを送らない限りわからない。例えば、Ａ→Ｂ→Ｃ→Ｄというようにデータを送るとき、ＡからＢへデータを送り、その後ＢからＣへデータを送る。このときのデータはＡにも届く（Ｂの電波はＡとＢの両方に届く）。Ａはこれを見て転送がうまくいったかどうか判定できる（図９参照）。ＢがＣへ再送しても応答を受けず、転送が失敗したとき経路表を修正する（Ｃを削除、図１０参照）。Ｂは他の全員に対してＣがなくなったことを知らせる。
【００５３】
経路表を修正するやり方として、図１３のテーブル欠損確認シーケンスがある。これは外から来た経路表と自分の通信の実績による経路表が一致しているかどうか調べ、一致していないとき経路表を修正するものである（不一致については図３４参照）。
【００５４】
以上説明したように、従来のルーティングプロトコルは、隣接する端末間でリンク状態を一定間隔ごとに相互に交換し、データ送信のタイミングと無関係にルーティングテーブルをあらかじめ構築しておくものであったが、本発明の実施の形態においては隣接する端末間のリンク状態情報は必要なときのみ端末間で相互に交換される。すなわち、リンク状態情報が収束した後、リンク状態情報に変化が生じたことを端末間の通信を通じて端末が検知したときにリンク状態情報を交換する。リンク状態情報の送受信の頻度を少なくすることができ、端末の消費電力を低減することができる。
【００５５】
低速／省電力の無線端末装置においてデータ欠落がしばしば発生するため、データの受信確認及びデータの再送の手順は必須である。しかし、データの受信確認やデータの再送には端末の送信動作が伴うので消費電力が増加する。送信動作において受信動作の約２倍の電力を消費するため、特に送信動作の増加は問題である。そこで本発明の実施の形態においては受信確認（アクノリッジ）をデータの送信と兼用することにより送信動作を減らしている。
【００５６】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図面の簡単な説明】
【図１】発明の実施の形態に係る無線端末装置の概略ブロック図である。
【図２】発明の実施の形態に係る無線端末装置の動作シーケンスの概要を示す図である。
【図３】発明の実施の形態に係る初期ディスカバリーシーケンスのフローチャートである。
【図４】発明の実施の形態に係る受信待機シーケンスのフローチャートである。
【図５】発明の実施の形態に係る初期ディスカバリー受信シーケンスのフローチャートである。
【図６】発明の実施の形態に係る経路変換行列受信シーケンスのフローチャートである。
【図７】発明の実施の形態に係る端末削除処理シーケンスのフローチャートである。
【図８】発明の実施の形態に係るメッセージ処理シーケンスのフローチャートである。
【図９】発明の実施の形態に係るメッセージ処理シーケンスのフローチャート（続き）である。
【図１０】発明の実施の形態に係るメッセージ処理シーケンスのフローチャート（続き）である。
【図１１】発明の実施の形態に係るアクノリッジパケット処理シーケンスのフローチャートである。
【図１２】発明の実施の形態に係る送信シーケンスのフローチャートである。
【図１３】発明の実施の形態に係るテーブル欠損確認シーケンスである。
【図１４】発明の実施の形態に係る無線フレームの説明図である。
【図１５】発明の実施の形態に係るＦｒａｍｅ＿ｔｙｐｅの種別の定義の説明図である。
【図１６】発明の実施の形態に係るＰＩＮＧパケットフォーマットの図である。
【図１７】発明の実施の形態に係る経路変換行列パケットの説明図である。
【図１８】発明の実施の形態に係るメッセージ送信パケットフォーマットの図である。
【図１９】発明の実施の形態に係るＦＬＡＧＳの説明図である。
【図２０】発明の実施の形態に係るＷＡＫＥＵＰパケットフォーマットの図である。
【図２１】発明の実施の形態に係る端末削除パケットフォーマットの図である。
【図２２】発明の実施の形態に係るアクノリッジパケットフォーマットの図である。
【図２３】発明の実施の形態に係るテーブル遷移の説明図である。
【図２４】発明の実施の形態に係るテーブル遷移の説明図（続き）である。
【図２５】発明の実施の形態に係るテーブル遷移の説明図（続き）である。
【図２６】発明の実施の形態に係るテーブル遷移の説明図（続き）である。
【図２７】発明の実施の形態に係るテーブル遷移の説明図（続き）である。
【図２８】発明の実施の形態に係るテーブル遷移の説明図（続き）である。
【図２９】発明の実施の形態に係るリンク状態情報テーブルの概念の説明図である。
【図３０】発明の実施の形態に係るリンク状態情報の遷移の説明図である。
【図３１】発明の実施の形態に係るリンク状態情報の遷移の説明図（続き）である。
【図３２】発明の実施の形態に係るリンク状態情報の遷移の説明図（続き）である。
【図３３】発明の実施の形態に係るリンク状態情報の遷移の説明図（続き）である。
【図３４】発明の実施の形態に係るテーブル欠損の説明図である。
【符号の説明】
１０    処理部（ＣＰＵ）
１１    微弱無線モジュール
１２    センサ
１３    電池
【図１】
2004320658.tif 000003
【図２】
2004320658.tif 000004
【図３】
2004320658.tif 000005
【図４】
2004320658.tif 000006
【図５】
2004320658.tif 000007
【図６】
2004320658.tif 000008
【図７】
2004320658.tif 000009
【図８】
2004320658.tif 000010
【図９】
2004320658.tif 000011
【図１０】
2004320658.tif 000012
【図１１】
2004320658.tif 000013
【図１２】
2004320658.tif 000014
【図１３】
2004320658.tif 000015
【図１４】
2004320658.tif 000016
【図１５】
2004320658.tif 000017
【図１６】
2004320658.tif 000018
【図１７】
2004320658.tif 000019
【図１８】
2004320658.tif 000020
【図１９】
2004320658.tif 000021
【図２０】
2004320658.tif 000022
【図２１】
2004320658.tif 000023
【図２２】
2004320658.tif 000024
【図２３】
2004320658.tif 000025
【図２４】
2004320658.tif 000026
【図２５】
2004320658.tif 000027
【図２６】
2004320658.tif 000028
【図２７】
2004320658.tif 000029
【図２８】
2004320658.tif 000030
【図２９】
2004320658.tif 000031
【図３０】
2004320658.tif 000032
【図３１】
2004320658.tif 000033
【図３２】
2004320658.tif 000034
【図３３】
2004320658.tif 000035
【図３４】
2004320658.tif 000036