JP2019508000A - 水中無線移動ネットワークのためのスケジューリング方法 - Google Patents

Abstract

本発明は、水中無線移動ネットワークのためのスケジューリング方法に係り、特に、時間領域で衝突が発生しないスケジューリング方法を考慮するが、特定の瞬間に転送時間が重ならないように直交化するよりは、音波の伝達速度及びパケット長を考慮してシンクノードにパケットがパケットトレインの形態で連続的に受信されるようにすることにより、ネットワークの効率を向上させることができる、水中無線移動ネットワークのためのスケジューリング方法に関する。

Description

発明の詳細な説明

〔技術分野〕
本発明は、水中無線移動ネットワークのためのスケジューリング方法に係り、特に、時間領域で衝突が発生しないスケジューリング方法を考慮するが、特定の瞬間に転送時間が重ならないように直交化するよりは、音波の伝達速度及びパケット長を考慮してシンクノードにパケットがパケットトレインの形態で連続的に受信されるようにすることにより、ネットワークの効率を向上させることができる、水中無線移動ネットワークのためのスケジューリング方法に関する。

また、本発明は、水中音響無線移動ネットワークなどのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、多数のノードがシンクノードへデータパケットを時分割多重アクセス方式で伝送しようとするときに、ノードの移動性による往復時間遅延をサイクル単位で追跡してシンクノードがノードからデータパケットを受信する上で遊休時間を最小化することにより、チャンネル使用効率の向上によるネットワーク効率が大幅に向上することができる、水中無線移動ネットワークのためのスケジューリング方法に関する。

また、本発明は、水中音響無線移動ネットワークなどのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、多数のノードがシンクノードへデータパケットを時分割多重アクセス方式で伝送しようとするときに、ノードの移動性による往復時間遅延をサイクル単位で追跡してシンクノードがノードからデータパケットを受信する上で遊休時間を最小化することにより、チャンネル使用効率の向上によるネットワーク効率が大幅に向上することができる、水中無線移動ネットワークのためのスケジューリング方法に関する。

〔背景技術〕
通常、水中無線ネットワークは音波を用いる。このように音波を用いる水中無線ネットワークでは、電磁波に比べて相対的に伝達速度が非常に遅い音波の伝達速度に起因する非常に長い伝播遅延、及び水中音響モデムの狭い帯域幅に起因する物理階層の遅いデータ伝達速度によって長くなるパケット長により発生するネットワーク効率性の低下を克服することが最も重要である。

水中無線ネットワークトポロジーは、一つまたは多数のシンクノードへ多数のノードが情報を伝達することをメイントラフィックとする中央集中方式と、分散型のマルチホップ方式があるが、ネットワーク効率の面で中央集中方式が有利である。現在商用で運用されているすべてのネットワーク方式も中央集中方式である。中央集中方式は、空間／時間／周波数／符号などのリソースを直交化して使用するのが一般的である。

伝搬時間遅延が「０」に近い空気中での電磁波を利用する通信ネットワークシステムでは、同じ衝突領域にある２つのノードが同時にパケット送信を行うと、互いに衝突を起こすが、水中では遅い音波の伝達速度により衝突を起こさないこともある。例えば、音波の伝達速度を１，５００ｍ／ｓと仮定し、互いに１．５ｋｍ離れている２つのノードが１秒長さのデータパケットを同時に伝送すると、送信−受信間のスイッチングに必要な時間を無視すれば、各ノードで送信が終わるや否や他のノードのパケット受信が始まる。具体的には、０秒に２つのノードが１秒長さのパケットを同時に伝送すると、１秒の時点で、２つのノードは送信が終了し、すぐに相手ノードのデータを受信し始めるので、自分のパケット送信が相手ノードのパケットを受信する上で問題を起こさなくなり、２秒の時点では、２つのノードの両方ともパケット受信が完了する。もし順次データを伝送するならば合計４秒の時間がかかるので、この場合には、ネットワークの効率が２倍に向上する効果を持つ。しかし、このような場合にも、２つのノードが互いに近づく方向に動けば衝突が発生するが、既存のほとんどの水中無線媒体アクセス制御プロトコルは、このようなノードの移動性を考慮していない。

韓国特許登録第１５２２２７９号公報（発明の名称：水中音響ネットワークの精密時間−境界時分割多重アクセス方法、以下「特許文献」という）は、ノードの移動性を考慮しているが、各ノードの初期位置を知らなければならず、初期化過程でノードが固定されていなければならず、各ノードの移動速度情報がサイクルごとに持続的に更新されなければならず、時間同期化が不可欠であるという欠点がある。しかも、前記特許文献は、各ノードの速度情報を用いて位置推定を行い、これをベースにして往復時間遅延を推定する方法を提示しているが、これは時間が経つほど水中ノードの速度情報の累積による誤差が大きくなる環境で適用するのに限界があった。また、前記特許文献は、時間同期化のための具体的な方案が提示されておらず、同期化誤差への対応策がないため、各ノードの初期位置情報または速度を知ることができないか、或いは時間同期化が不可能な場合には、活用が不可能であるという問題点があった。

〔発明の概要〕
〔発明が解決しようとする課題〕
そこで、本発明は、かかる点に着目してなされたもので、その目的は、水中で移動ノードの航法情報とは無関係に動作するとともに、時間同期化が不要なので時間同期化のための別途のパケット交換が必要ないから、ネットワークの歩留まりを向上させることができる、水中無線移動ネットワークのためのスケジューリング方法を提供することにある。

本発明の他の目的は、水中音響無線移動ネットワークのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、チャンネル使用効率の向上によるネットワークの効率を向上させることができ、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であり、誤差が累積されないため周期的な再初期化が必要ない、水中無線移動ネットワークのためのスケジューリング方法を提供することにある。

本発明の別の目的は、水中音響無線移動ネットワークのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、チャンネル使用効率の向上によるネットワークの効率を向上させることができ、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であり、誤差が累積されないため周期的な再初期化が必要ない、水中無線移動ネットワークのためのスケジューリング方法を提供することにある。

〔課題を解決するための手段〕
上記の目的を達成するために、本発明の一実施形態による水中無線移動ネットワークのためのスケジューリング方法は、シンクノードから多数のノードへ初期化パケットを放送する第１段階と、前記シンクノードが多数のノードから第１設定時間

の間に初期化応答パケットを受信する第２段階と、前記シンクノードが前記第２段階で受信した初期化応答パケットから前記シンクノードと多数のノード間の往復時間遅延

を計算する第３段階と、前記シンクノードによって、初期化応答パケットの受信に衝突が存在するか否かを決定する第４段階と、前記第４段階で初期化応答パケットの受信に衝突が存在しなければ、前記シンクノードが、前記第３段階で計算された往復時間遅延

を用いて往復時間遅延の小さい順にノードを整列する第５段階と、前記シンクノードによって変数ｋが１に設定され、１番目のノードの待機時間

が「０」に設定される第６段階と、前記シンクノードによって、１番目のノードのデータパケットが前記シンクノードに受信され始める時刻の最大値

が計算される第７段階と、前記変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第８段階と、前記第８段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記変数ｋをｋ＋１に設定する第９段階と、前記シンクノードによって、ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値

が計算される第１０段階と、前記シンクノードによって前記ｋ番目のノードの待機時間

が計算される第１１段階と、前記シンクノードによって、前記ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最大値

を計算した後、前記第８段階へ移行する第１２段階と、前記第８段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードによって１番目のビーコンパケットが第３設定時刻

に多数のノードへ放送される第１３段階と、前記シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記第１３段階による１番目のビーコンパケットの放送後に第４設定時間

を待機する第１４段階と、前記シンクノードによって前記シンクノードと前記ｋ番目のノード間の往復時間遅延

が計算される第１５段階と、前記シンクノードが、前記第１５段階で計算された往復時間遅延

を用いて往復時間遅延の小さい順にノードを整列する第１６段階と、前記シンクノードによって、１サイクルの間に変化することが可能なノードの往復時間遅延変動幅

が計算される第１７段階と、前記変数ｋを１に設定し、前記シンクノードが、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットを受信し始める時刻の最大値

を計算する第１８段階と、前記変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第１９段階と、前記第１９段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記変数ｋをｋ＋１に設定する第２０段階と、前記シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値

を計算する第２１段階と、前記シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延

を計算する第２２段階と、前記シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値

を計算した後、前記第１９段階へ移行する第２３段階と、前記第１９段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードによって、ビーコンパケット放送が行われるか否かが決定される第２４段階と、前記第２４段階でビーコンパケット放送が行われなければ終了する第２５段階とを含むことを特徴とする。

前記一実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第２４段階でシンクノードによってビーコンパケット放送が決定されれば、前記シンクノードによってｎ番目のサイクルのビーコンパケットが放送される時刻

にビーコンパケットがノードに放送される第２６段階と、前記シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記ｎ番目のサイクルで最後番目のノードのデータパケットが受信され始める時刻の最大値

を待機する第２７段階と、前記シンクノードによってサイクルが１だけ増加した後、前記第１５段階へ移行する第２８段階とが行われ得る。

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第４段階で初期化応答パケットの受信に衝突が存在すれば、前記シンクノードによって再初期化パケットがノードに放送される第２９段階と、前記シンクノードによって第２設定時間

だけ再初期化応答パケットが受信される第３０段階と、前記シンクノードが、前記第３０段階で受信した再初期化応答パケットから前記シンクノードとノード間の往復時間遅延

を計算する第３１段階と、前記シンクノードによって、再初期化応答パケットの受信に衝突が存在するか否かを決定する第３２段階とが行われ、前記第３２段階で再初期化応答パケットの受信に衝突が存在すれば前記第２９段階へ移行することができる。

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第３２段階で再初期化応答パケットの受信に衝突が存在しなければ、前記第５段階へ移行することができる。

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１設定時間

は下記数式１０１によって決定できる。

［式中、

は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、

は初期化パケット長の時間換算値であり、

は初期化応答パケット長の時間換算値であり、

はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。

（ｒはモデムの最大通信半径であり、ｃは音波速度である。）］

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードと多数のノード間の往復時間遅延

は下記数式１０３によって決定できる。

（式中、

はノードＨから受信された初期化応答パケットの受信時刻であり、

は初期化パケット放送時間である。）

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記１番目のノードのデータパケットが前記シンクノードに受信され始める時刻の最大値

は、下記数式１０８によって決定できる。

（式中、

はシンクノードによる最初のビーコンパケット放送時刻であり、

はビーコンパケット長の時間換算値であり、

は１番目のノードの往復時間遅延であり、

は１番目のノードのシンクノードとの往復時間遅延が取得された時点であり、

はシンクノードとノード間の最大相対速度である。）

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値

は、下記数式１１３によって決定できる。

（式中、

はｋ番目のノードの往復時間遅延であり、

は

が取得された時刻である。）

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記ｋ番目のノードの待機時間

は下記数式１１４によって決定できる。

［式中、

はＡとＢの両者から大きい値を選択する関数であり、

は、ｋ−１番目のノードのデータパケットがシンクノードに到着する時刻の最大値であって、下記数式１１２によって決定され、

はｋ−１番目のノードのデータパケット長の時間換算値である。

（式中、

はｋ−１番目のノードの往復時間遅延であり、

はｋ−１番目のノードの待機時間であり、

は

が取得された時間である。）］

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードと前記ｋ番目のノード間の往復時間遅延

は下記数式１１５によって決定できる。

（式中、

はｎ番目のサイクルのビーコンパケットが放送される時刻であり、

はｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻であり、

はｎ番目のサイクルでｋ番目のノードに付与される時間遅延であり、

はｎ番目のサイクルにおけるビーコン長の時間換算値である。）

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記１サイクルの間に変化することが可能なノードの往復時間遅延変動幅

は下記数式１１６によって決定できる。

（式中、

は（ｎ−１）番目のサイクルにおけるデータパケットの受信開始時刻である。）

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、各ノードの（ｎ−１）番目のサイクルにおけるデータパケットの受信時刻

とｎ番目のサイクルにおけるデータパケットの受信時刻

との差は下記数式１１７のように近似することができる。

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第２設定時間

は下記数式１０５によって決定できる。

（式中、

は再初期化パケット長の時間換算値であり、

は再初期化応答パケット長の時間換算値である。）

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値

は、下記数式１１８によって決定できる。

（式中、

はｎ−１番目のサイクルにおける１番目のノードの往復時間遅延であり、

はｎ番目のサイクルにおける１番目のノードのデータパケット長の時間換算値である。）

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードにｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値

は、下記数式１１９によって計算できる。

（式中、

はｎ−１番目のサイクルにおけるｋ番目のノードの往復時間遅延である。）

前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延

は、下記数式１２０によって計算できる。

(式中、

はｎ番目のサイクルでｋ−１番目のノードのデータパケットが受信され始める時刻の最大値である。)
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードにｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値

は、下記数式１２１によって計算できる。

（式中、

はｎ番目のサイクルにおけるｋ番目のノードのデータパケット長の時間換算値である。）

上記の他の目的を達成するために、本発明の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法は、伝送スケジュールを含んでいるビーコンパケットを放送する一つのシンクノードと、前記シンクノードのビーコンパケットを受信して伝送スケジュールに従ってデータパケットを前記シンクノードへ伝送する多数のノードとから構成されたネットワークトポロジーで時分割多重アクセスを行う、水中無線移動ネットワークのためのスケジューリング方法であって：前記シンクノードが初期化過程を行う第１’段階と、前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を０に設定する第２’段階と、前記シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算する第３’段階と、前記シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第４’段階と、前記第４’段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記シンクノードが前記変数ｋをｋ＋１に設定する第５’段階と、前記シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定する第６’段階と、前記シンクノードが、前記第６’段階で推定されたｋ番目のノードの往復時間遅延

を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を計算する第７’段階と、前記シンクノードが、前記第７’段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を用いて、ｋ番目のノードの待機時間

を計算する第８’段階と、前記シンクノードが、前記第７’段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

と前記第８’段階で計算されたｋ番目のノードの待機時間

を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値

を計算した後、前記第４’段階へ移行する第９’段階とを含むことを特徴とする。

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第４’段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードがビーコンパケットの放送有無を判断する第１０’段階をさらに含み、前記第１０’段階でビーコンパケットが放送されなければすべての手続きを終了することができる。

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１０’段階でビーコンパケットが放送されれば、前記シンクノードが、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻

にビーコンパケットを放送する第１１’段階と、Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値

が超過する第１２’段階と、前記シンクノードが、ｎ番目のサイクルでｋ番目のノードの往復時間遅延

を計算し、往復時間遅延取得有効性値

及び直近に取得された往復時間遅延関連情報

を更新する第１３’段階と、前記シンクノードがｎを１だけ増加させた後、前記第２’段階へ移行する第１４’段階とを含むことができる。

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１’段階で、前記シンクノードは下記［数式２０１］のように初期化過程を行うことができる。

（式中、

はｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、

はｎ番目のサイクルで、（ｎ−２）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、

は直近に取得されたｋ番目のノードの往復時間遅延であり、

は

が得られたサイクルであり、

はシンクノードと各ノード間の最初の往復時間遅延であり、

は１番目のサイクル前の持続時間であり、

は下記数式２０２のように推定されて定められる。）

（

は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第３’段階は、直近の２サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合には、下記［数式２０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算することができる。

（式中、

はガード時間であり、

はｎ−１番目のサイクルで取得された１番目のノードの往復時間遅延であり、

はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、

はｎ−１番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻であり、

は下記数式２０４のとおりである。）

（式中、

はｎ−２番目のサイクルで取得された１番目のノードの往復時間遅延であり、

はｎ−２番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻である。）

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記［数式２０３］は、下記の連立方程式である［数式２０６］を解いて得られる。

（式中、

はｎ番目のサイクルで１番目のノードのデータパケット受信時刻

に対する推定値である。）

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第３’段階は、直近の２サイクルの間に１番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２０５］のようにｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算することができる。

（式中、

は往復時間遅延の最大値であり、

は直近に取得された１番目のノードの往復時間遅延であり、

はシンクノードとｋ番目のノード間の最大相対速度であり、

はｎ−１番目のサイクルの持続時間であり、

は１番目のノードの往復時間遅延が取得された直近のサイクルであり、

は水中での最小音波伝達速度である。）

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６’段階は、直近の２サイクルの間にｋ番目のノードの往復時間遅延

が成功的に取得された場合には、下記［数式２０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定することができる。

（式中、

はｎ−１番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、

はｋ−１番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値であり、

はｎ−１番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻であり、

は下記数式２１１のとおりである。）

（式中、

は、ｎ−２番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、

はｎ−２番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻である。）

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、第６’段階は、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２１２］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定することができる。

（式中、

は、

が得られたサイクルである。）

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第７’段階で、前記ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

は、下記［数式２１３］のように計算できる。

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第８’段階で、前記ｋ番目のノードの待機時間

は、下記［数式２１４］のように計算できる。

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第９’段階で、直近の２サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値

は、下記［数式２１５］のように計算できる。

（式中、

はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第９’段階で、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値

は、下記［数式２１６］のように計算できる。

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１３’段階で、前記往復時間遅延取得有効性値

を更新するために、下記［数式２１７］のように、すべてのノードに対して前記往復時間遅延取得有効性値

を更新し、ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式２１８］のようにし、ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式２１９］のようにし、前記直近に取得された往復時間遅延関連情報

は下記［数式２２０］のように更新し、また、前記往復時間遅延取得有効性値

が１である場合には、下記［数式２２１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を計算し、直近に取得された往復時間遅延関連情報

を更新することができる。

上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延

を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻

は、下記［数式２０８］のように計算される。このとき、

の場合には、次のように［数式２０９］を解いて、下記［数式２１０］のようにｋ番目のノードの往復時間遅延を推定し、前記［数式２１０］における

は前記［数式２１１］のとおりであり得る。

上記の目的を達成するために、本発明の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法は、伝送スケジュールを含んでいるビーコンパケットを放送する一つのシンクノードと、前記シンクノードのビーコンパケットを受信して伝送スケジュールに従ってデータパケットを前記シンクノードへ伝送する多数のノードとから構成されたネットワークトポロジーで時分割多重アクセスを行う、多項式補間法を用いた水中無線移動ネットワークのためのスケジューリング方法であって：前記シンクノードが初期化過程を行う第１”段階と、前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を０に設定する第２”段階と、前記シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算する第３”段階と、前記シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第４”段階と、前記第４”段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記シンクノードが前記変数ｋをｋ＋１に設定する第５”段階と、前記シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定する第６”段階と、前記シンクノードが、前記第６”段階で推定されたｋ番目のノードの往復時間遅延

を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を計算する第７”段階と、前記シンクノードが、前記第７”段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を用いて、ｋ番目のノードの待機時間

を計算する第８”段階と、前記シンクノードが、前記第７”段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

と前記第８”段階で計算されたｋ番目のノードの待機時間

を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値

を計算した後、前記第４”段階へ移行する第９”段階とを含むことを特徴とする。

上記別の実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第４”段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードがビーコンパケットの放送有無を判断する第１０”段階をさらに含み、前記第１０”段階でビーコンパケットが放送されなければすべての手続きを終了することができる。
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第１０”段階でビーコンパケットが放送されれば、前記シンクノードが、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻

にビーコンパケットを放送する第１１”段階と、Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値

が超過する第１２”段階と、前記シンクノードが、ｎ番目のサイクルでｋ番目のノードの往復時間遅延

を計算し、往復時間遅延取得有効性値

及び直近に取得された往復時間遅延関連情報

を更新する第１３”段階と、前記シンクノードがｎを１だけ増加させた後、前記第２”段階へ移行する第１４”段階とを含むことができる。

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１”段階で、前記シンクノードは下記［数式３０１］のように初期化過程を行うことができる。

（式中、

は

よりも小さいか同じ自然数であり、

であり、

はｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、

はｎ番目のサイクルで、（ｎ−ｍ）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、

は直近に取得されたｋ番目のノードの往復時間遅延であり、

は

が得られたサイクルであり、

はシンクノードと各ノード間の最初の往復時間遅延であり、

は１番目のサイクル前の持続時間であり、

は下記数式３０２のように推定されて定められる。）

（式中、

は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第３”段階は、直近のＭサイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が

（２以上の自然数という）回以上であれば、下記［数式３０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を下記［数式３０５］のように計算することができる。

（式中、

は、

座標を通る最小次数の多項式であり、

はｎ番目のサイクルで１番目のノードのデータパケット受信時刻

に対する推定値であり、

はｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻であり、

はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、

は下記数式３０４のように値を制限する。）

（式中、

は往復時間遅延の最大値である。）

（式中、

はｎ番目のサイクルで１番目のノードのデータパケット長を時間に換算した値であり、

はガード時間である。）

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記［数式３０３］は次のように反復的に解が求められる。

１）

の初期値を

または

のように定め、
２）前記初期値

を用いて［数式３０３］から

を

のように計算し、
３）前記２）で計算された

を用いて

を

のように計算し、
４）前記３）で計算された

から

を

のように計算し、
５）前記４）で計算された

を用いて

を

のように計算し、
６）前記５）で計算された

から

を

のように計算する過程を、設定された回数だけ繰り返した後、最終的に計算される値を

と

に確定する（このとき、繰り返し回数を定めず、以前に計算された

と現在計算された

との差が一定値以下である場合に繰り返し過程を中断し、或いは、以前に計算された

と現在計算された

との差が一定値以下である場合に繰り返し過程を中断する。）

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第３”段階は、直近の

サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が

回未満であれば、下記［数式３０６］のようにｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算することができる。

（式中、

は直近に取得された１番目のノードの往復時間遅延であり、

はシンクノードとｋ番目のノード間の最大相対速度であり、

はｎ−１番目のサイクルの持続時間であり、

は１番目のノードの往復時間遅延が取得された直近のサイクルであり、

は水中での音波伝達速度の最小値である。）

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６”段階は、直近の

サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が

回以上であれば、下記［数式３０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定することができる。

（式中、

は

座標を通る最小次数の多項式であり、

は

サイクルでｋ番目のノードの有効な往復時間遅延値であり、


は（ｋ−１）番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値である。）

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６”段階でｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延

を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻

は、下記［数式３０８］のように計算できる。

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６”段階は、

の場合には、下記［数式３０９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定することができる。

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記［数式３０９］は、次のように反復的に解が求められる。

１’）

の初期値を

または

のように定め、
２’）前記初期値

を用いて［数式３０９］から

を

のように計算し、
３’）計算された

を用いて

を

のように計算し、
４’）前記３’）で計算された

から

を

のように計算し、
５’）前記４’）で計算された

を用いて

を

のように計算し、
６’）前記５’）で計算された

から

を

のように計算する
過程を、設定された回数だけ繰り返した後、最終的に計算される値を

と

に確定する（このとき、繰り返し回数を定めず、以前に計算された

と現在計算された

との差が一定値以下である場合に繰り返し過程を中断し、あるいは、以前に計算された

と現在計算された

との差が一定値以下である場合に繰り返し過程を中断する。）

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記

は下記［数式３１０］のように値を制限することができる。

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６”段階は、直近の

サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が

回未満であれば、下記［数式３１１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定することができる。

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第７”段階で前記ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

は、下記［数式３０８］によって計算できる。

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第８’段階で前記ｋ番目のノードの待機時間

は、下記［数式３１２］によって計算できる。

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第９”段階で、直近の

サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が

回以上であれば、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値

は、下記［数式３１３］のように計算できる。

（式中、

はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第９”段階で、直近の

サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が

回未満であれば、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値

は、下記［数式３１４］のように計算できる。

上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１３”段階で、前記往復時間遅延取得有効性値

を更新するために、下記［数式３１５］のようにすべてのノードに対して前記往復時間遅延取得有効性値

を更新し、ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式３１６］のようにし、ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式３１７］のようにし、前記直近に取得された往復時間遅延関連情報

は、下記［数式３１８］のように更新し、また、前記往復時間遅延取得有効性値

が１である場合には、下記［数式３１９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を計算し、直近に取得された往復時間遅延関連情報

を更新することができる。

〔発明の効果〕
本発明の一実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードから多数のノードへ初期化パケットを放送し、シンクノードが多数のノードから第１設定時間

の間に初期化応答パケットを受信し、前記シンクノードが受信した初期化応答パケットからシンクノードと多数のノード間の往復時間遅

を計算し、シンクノードによって初期化応答パケットの受信に衝突が存在するか否かを決定し、初期化応答パケットの受信に衝突が存在しなければ、シンクノードが計算された往復時間遅延

を用いて往復時間遅延の小さい順にノードを整列し、シンクノードによって変数ｋが１に設定され、１番目のノードの待機時間

が「０」に設定され、シンクノードによって１番目のノードのデータパケットがシンクノードに受信され始める時刻の最大値

が計算され、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し、変数ｋが最後番目（Ｋ番目）より小さければ、変数ｋをｋ＋１に設定し、シンクノードによってｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値

が計算され、シンクノードによってｋ番目のノードの待機時間

が計算され、シンクノードによってｋ番目のノードのデータパケットがシンクノードに到着する時刻の最大値

を計算した後、変数ｋが最後番目（Ｋ番目）より小さくなければ、シンクノードによって１番目のビーコンパケットが第３設定時刻

に多数のノードに放送され、シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または１番目のビーコンパケット放送後に第４設定時間

を待機し、シンクノードによってシンクノードとｋ番目のノード間の往復時間遅延

が計算され、シンクノードが計算された往復時間遅延

を用いて往復時間遅延の小さい順にノードを整列し、シンクノードによって１サイクルの間に変化することが可能なノードの往復時間遅延変動幅

が計算され、変数ｋを１に設定し、シンクノードがｎ番目のサイクルで１番目のノードに付与される時間遅延

を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値

を計算し、変数ｋが最後番目（Ｋ番目）より小さいか否かを判断して、変数ｋが最後番目（Ｋ番目）より小さければ変数ｋをｋ＋１に設定し、シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値

を計算し、シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延

を計算し、シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値

を計算した後、変数ｋが最後番目（Ｋ番目）より小さくなければ、シンクノードによってビーコンパケット放送が行われるか否かが決定され、ビーコンパケット放送が行われなければ終了するように構成されることにより、
第一に、水中で移動ノードの航法情報とは無関係に動作し、
第二に、時間同期化が不要なので、時間同期化のための別途のパケット交換が必要ないから、ネットワークの歩留まりを向上させることができ、
第三に、スケジュール情報が絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作し、
第四に、毎サイクル終了時点でシンクノードとノード間の往復時間遅延情報に対する正確な値が測定されるので、スケジュール情報は、時間が経過するにつれて誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。

また、本発明の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードが初期化過程を行い；シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を０に設定し；シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算し；シンクノードによって変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し；前記判断で変数ｋが最後番目（Ｋ番目）より小さければ、シンクノードが前記変数ｋをｋ＋１に設定し；シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定し；シンクノードが、前記推定されたｋ番目のノードの往復時間遅延

を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を計算し；シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を用いてｋ番目のノードの待機時間

を計算し；及び、シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

と前記計算されたｋ番目のノードの待機時間

を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値

を計算した後、前記判断過程へ移行するように構成されることにより：
すなわち、水中音響無線移動ネットワークなどのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、多数のノードがシンクノードへデータパケットを時分割多重アクセス方式で伝送しようとするとき、ノードの移動性による往復時間遅延をサイクル単位で追跡して、シンクノードがノードからデータパケットを受信する上で遊休時間を最小化することにより、チャンネル使用効率の向上によるネットワークの効率が大幅に向上することができるという優れた効果がある。特に、ノード数が増加すればするほど、ネットワーク効率の向上程度はさらに増加する。本発明に係る水中無線移動ネットワークのためのスケジューリング方法は、絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作する。したがって、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であるという利点がある。
また、往復時間遅延情報に対する正確な値がサイクルごとに得られるので、誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。

本発明の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードが初期化過程を行い；前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を０に設定し；シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算し；シンクノードによって変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し；前記判断で変数ｋが最後番目（Ｋ番目）より小さければ、シンクノードが変数ｋをｋ＋１に設定し；シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定し；シンクノードが、前記推定されたｋ番目のノードの往復時間遅延

を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を計算し；シンクノードが、計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を用いて、ｋ番目のノードの待機時間

を計算し；前記シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

と前記計算されたｋ番目のノードの待機時間

を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値

を計算した後、前記判断過程へ移行するように構成されることにより：
すなわち、水中音響無線移動ネットワークのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、チャンネル使用効率の向上によるネットワークの効率を向上させることができ、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であり、誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。特に、ノード数が増加すればするほど、ネットワーク効率の向上程度はさらに増加する。本発明に係る水中無線移動ネットワークのためのスケジューリング方法は、絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作する。したがって、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であるという利点がある。

また、往復時間遅延情報に対する正確な値がサイクルごとに得られるので、誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。

〔図面の簡単な説明〕
〔図１〕本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図２ａ乃至図２ｆ〕本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
〔図３〕本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。
〔図４〕本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。
〔図５〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図６〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
〔図７ａ及び図７ｂ〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
〔図８〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図９〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
〔図１０ａ乃至図１０ｃ〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。

〔発明を実施するための形態〕
以下、本発明の実施形態を、添付図面を参照して詳細に説明する。

［第１実施形態］
図１は本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図であって、ネットワークトポロジーは、一つのシンクノードと多数のノードとから構成されている。水中で音波を用いて多数のノードが一つのシンクノードへデータパケットを送る中央集中方式のネットワークトポロジーにおけるスケジューリング方法である。シンクノード以外のノードは「ノード」と略記することがある。シンクノードは、ノードの伝送スケジュールを含んでいるビーコンパケットを放送し、ビーコンパケットを受信したノードは、ビーコンパケットに指示されている各ノードの伝送スケジュールに従ってデータパケットをシンクノードへ伝送する。シンクノードとノード間の最大相対速度を知っていると仮定し、Ｖで表示する。

以下、前述のように構成されたネットワークトポロジーで行われる、本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法について説明する。

図２ａ乃至図２ｆは本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートであり、ここで、Ｓはステップ（Ｓｔｅｐ）を意味する。

本発明のスケジューリング方法は、シンクノードと多数のノード間の往復時間遅延（ＲＴＴ：Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ）を求め、これに基づいて最初の衝突回避スケジュールを導出する初期化過程と、初期化過程でシンクノードがビーコンパケット放送してすべてのノードからデータパッケージの受信が完了する１番目のサイクル後に行われる正規過程とを含む。

初期化過程
まず、シンクノードから多数のノードへ初期化（ＩＲＱ）パケットを放送し（Ｓ１０１０）、シンクノードが多数のノードから第１設定時間

の間に初期化応答（ＩＲＰ）パケットを受信する（Ｓ１０２０）。

初期化パケットは、ノードが初期化パケットを受信したときに初期化パケットであることを知ることができるパケット種類識別情報のみを含んでいればよいので、その長さが非常に短い。初期化応答パケットはは、該当初期化応答パケットを送信するノードのアドレス情報と、初期化応答パケットであることを示すパケット種類識別情報とを含む。モデムの最大通信半径をｒとし、音波の速度をｃとすると、シンクノードは、初期化パケット放送の後、次のとおり、第１設定時間

以内にすべてのノードから初期化応答パケットの受信が完了する。

第１設定時間

は、下記数式１０１によって決定される。

(式中、

は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、

は初期化パケット長の時間換算値であり、

は初期化応答パケット長の時間換算値であり、

はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。)

（式中、ｒはモデムの最大通信半径であり、ｃは音波の速度である。）

次いで、シンクノードが前記ステップ（Ｓ１０２０）で受信した初期化応答パケットからシンクノードと多数のノード間の往復時間遅延

を計算する（Ｓ１０３０）。具体的には、シンクノードは、初期化パケット送信時間

をシンクノード自身のローカルクロックから知ることができ、ノードＨから受信された初期化応答パケットの受信時刻

もシンクノード自身のローカルクロックから知ることができる。したがって、シンクノードは、時間同期化なしにシンクノードとノードＨ間の往復時間遅延情報

を初期化応答パケット受信時刻と初期化パケット送信時刻との差から取得することができる。

シンクノードと多数のノード間の往復時間遅延

は、下記数式１０３によって決定される。

その後、シンクノードによって初期化応答パケットの受信に衝突が存在するか否かを決定する（Ｓ１０４０）。

シンクノードがノードから初期化応答（ＩＲＰ）パケットを受信するときに多数のノードから初期化応答パケットを受信するが、シンクノードと各ノード間の往復時間遅延差が初期化応答パケット長より大きいさえすれば衝突が発生しない。例えば、物理階層の伝送速度が１００ｋｂｐｓであり、音波の伝達速度が１，５００ｍ／ｓである場合を考えると、一つのビットが占める長さは０．０１ｍｓであり、初期化応答パケットはノードのアドレスとパケットタイプの情報だけを含めばよいので、３０ｂｉｔと仮定すれば、このときの初期化応答パケット長は０．３ｍｓであり、０．３ｍｓの間に音波が移動する距離は０．４５ｍであるので、任意の２つのノードに対してシンクノードとノード間の距離に対する相対的な差が０．５ｍ以上であれば、衝突が発生しないので、衝突の確率が非常に小さくなる。これは音波の遅い伝達速度が作り出す自然なランダムバックオフ（ｒａｎｄｏｍ ｂａｃｋ ｏｆｆ）効果を活用することを意味する。一般に、空気中で電磁波を利用する無線ネットワークでは、パケットの受信衝突を防止するためにランダムな時間遅延を与えるが、水中で音波を利用する無線通信ネットワークでは、音波の遅い伝達速度が自然にランダム時間遅延を誘発する原理を利用するのである。それにもかかわらず、シンクノードで初期化応答パケットに対する受信衝突が発生するおそれがあるが、このような初期化応答パケットの受信衝突が発生したノードにのみ選択的に初期化応答パケットの受信衝突回避を適用することが、本発明に対する初期化過程の最も重要な特徴である。

最初に行われる初期化パケット放送及びこれに対するノードの初期化応答パケット受信過程を経ながら、シンクノードは、物理階層での信号の受信は行われたが、情報がまともに復元されなかった場合の発生有無から初期化応答パケットの受信衝突の発生有無を知ることができる。

前記ステップ（Ｓ１０４０）で初期化応答パケットの受信に衝突が存在しなければ（Ｎ）、初期スケジューリング手続きに進入して次のステップ（Ｓ１０５０）へ移行する一方、初期化応答パケットの受信に衝突が発生した場合には（Ｙ）、シンクノードによって再初期化（ＲＩＲＰ）パケットが多数のノードに放送されて衝突回避による往復時間遅延取得手続きに進入する（Ｓ１２６０）。

再初期化（ＲＩＲＰ）パケットは、シンクノードとノード間の往復時間遅延の取得が行われたノードに対するリストを含むようにして、再初期化パケットを受信したノードは、自分が再初期化パケットのリストにない場合にのみランダムバックオフ（ｂａｃｋ ｏｆｆ）を介して再初期化応答パケットをシンクノードへ送信するようにする。ここで、ランダムバックオフとは、再初期化パケットを受信したノードが再初期化パケットを受信するや否や再初期化応答パケットを送信するのではなく、

長さを有する時間スロットの任意の整数倍だけ再初期化応答パケットの送信を先送りすることを意味する。すなわち、再初期化パケットを受信したノードは、再初期化パケットの受信が完了した後、下記数式１０４のように与えられる

時間だけ待機した後に再初期化応答パケットをシンクノードへ送信するようにする。

（式中、ｍはユーザーが指定する最大値（Ｍ）よりも小さい整数の中からランダムに選択される負数ではない整数であり、

は、好ましくは初期化応答パケット長の２倍以上となるようにする。）

次に、ステップ（Ｓ１２７０）では、シンクノードによって第２設定時間

だけ再初期化応答パケットが受信される。再初期化応答パケットは、初期化応答パケットが含んでいる情報に加えて、さらにｍ値が含まれるようにする。

つまり、シンクノードは、最初の初期化応答パケット受信の場合と同様に、再初期化パケット放送後に、下記数式１０５によって決定されたような第２設定時間

以内にすべてのノードから再初期化応答パケットの受信が完了する。

（式中、

は再初期化パケット長の時間換算値であり、

は再初期化応答パケット長の時間換算値である。）

次いで、シンクノードが前記ステップ（Ｓ１２７０）で受信した再初期化応答パケットからシンクノードと多数のノード間の往復時間遅延

を計算する（Ｓ１２８０）。

具体的には、シンクノードは、再初期化パケット送信時間

をシンクノード自身のローカルクロックから知ることができ、ノードＨから受信された再初期化応答パケットの受信時刻

もシンクノード自身のローカルクロックから知ることができる。したがって、シンクノードは、時間同期化なしにシンクノードとノードＨ間の往復時間遅延情報

を再初期化応答パケット受信時刻と再初期化パケット送信時刻との差から下記数式１０６のように取得することができる。

(式中、

はノードＨから受信された再初期化応答パケットの受信時刻であり、

は再初期化パケットの送信時刻である。)

その後、シンクノードによって再初期化応答パケットの受信に衝突が存在するか否かを決定する（Ｓ１２９０）。

前記ステップ（Ｓ１２９０）で再初期化応答パケットの受信に衝突が存在すれば（Ｙ）、前記ステップ（Ｓ１２６０）へ移行し、これに対し、前記ステップ（Ｓ１２９０）で再初期化応答パケットの受信に衝突が存在しなければ（Ｎ）、前記ステップ（Ｓ１０５０）へ移行する。

つまり、再初期化応答パケットの受信衝突が発生しないときまで再初期化パケット放送を繰り返し行ってすべてのノードに対してシンクノードとノード間の往復時間遅延を取得するようにする。ただし、すべてのノードに対してシンクノードとノード間の往復時間遅延の取得が必ずしも必要ではない場合には、前記繰り返し回数に制限を置くことができる。

前述のように初期化過程でシンクノードが往復時間遅延情報の取得を完了すると、シンクノードは、このように取得された往復時間遅延情報を用いて、シンクノードでノードのデータパケットの受信衝突が発生しないように初期スケジュールを計算し、シンクノードは、このスケジュール情報をビーコンパケット含むようにビーコンパケットを生成し、このビーコンパケットをすべてのノードに放送する。

このため、シンクノードが、前記ステップ（Ｓ１０３０）で計算された往復時間遅延

を用いて往復時間遅延の小さい順にノードを整列する（Ｓ１０５０）。

合計Ｋ個のノードがあれば、往復時間遅延がｋ番目に小さいノードを「ｋ番目のノード」と命名する。ｋ番目のノードの往復時間遅延を

と表示する。

は、数式１０３及び数式１０６を介して取得された往復時間遅延を小さい順に整列して得られる値である。

が取得された時刻を

と表示する。

は、

に相応する

または

値である。シンクノードが最初にビーコンパケットを放送する時刻を

と表示する。

はシンクノードのローカルクロックから当然に知ることが可能な値である。

以後、シンクノードは、往復時間遅延の小さい順に、次のように、各ノードのスケジューリングを行う。スケジューリングとは、ノードがビーコンパケットを受信した後にデータパケットを送信するまで待機する時間であって、ｋ番目のノードの待機時間を

と表示する。

まず、シンクノードによって変数ｋが１に設定され、１番目のノードの待機時間

が下記数式１０７のように「０」に設定される（Ｓ１０６０）。つまり、１番目のノードは、ビーコンパケットを受信するや否や待機時間なしに直ちにデータパケットを送信する。

そうすれば、シンクノードによって１番目のノードのデータパケットがシンクノードに受信され始める時刻の最大値

が、下記数式１０８のように計算される（Ｓ１０７０）。

（式中、

はシンクノードによる最初のビーコンパケット放送時刻であり、

はビーコンパケット長の時間換算値であり、

は１番目のノードの往復時間遅延であり、

は１番目のノードのシンクノードとの往復時間遅延が取得された時点であり、

はシンクノードとノード間の最大相対速度である。］

数式１０８は、１番目のノードのＲＴＴ取得時点から、１番目のノードがビーコンパケットの受信後にデータパケットを送信するまで１番目のノードの移動性により発生する１番目のノードの往復時間遅延の最大変動幅を考慮する方法である。１番目のノードのＲＴＴが取得された時点は

であるので、１番目のノードのＲＴＴが決定された時点は

であり、１番目のノードは、

時刻以前にはビーコンメッセージを必ず受信する。ｙって、１番目のノードのＲＴＴ決定時点から１番目のノードがデータパケットを伝送し始める時点まで、１番目のノードがシンクノードから最大相対速度Ｖで離れるとき、往復時間遅延は最大に増加するが、これは、数式１０８において、

と表現されている。

したがって、１番目のノードのデータパケットがシンクノードに受信完了する時刻の最大値は、下記数式１０９のとおりである。すなわち、前記時刻の最大値に受信が終了する。

（式中、

は１番目のノードのデータパケット長を時間に換算した値である。］

後に２番目のノードのデータパケットの受信が始まる。

（式中、

は２番目のノードのデータパケットがシンクノードに到着する時刻の最小値である。）

したがって、下記数式１１１のように２番目のノードに時間遅延を付与すると、シンクノードで１番目のノードのデータパケットとの受信衝突を回避することができる。

（式中、

はＡ及びＢの両者から大きい値を選択する関数である。）
同様の方法で、Ｋ番目のノードの時間遅延が計算されるまで回帰的に各ノードの時間遅延を計算することができるが、具体的には、（ｋ−１）番目のノードのデータパケットがシンクノードに到着する時刻の最大値

は、下記数式１１２のように計算される。

ステップ（Ｓ１０８０）では、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する。

前記ステップ（Ｓ１０８０）で前記変数ｋが最後番目（Ｋ番目）よりも小さい場合（Ｙ）、前記変数ｋをｋ＋１に設定する（Ｓ１０９０）。
ステップ（Ｓ１１００）では、ｋ番目のノードのデータパケットがシンクノードに到着する時刻の最小値

が下記数式１１３のように計算される。

（式中、

はｋ番目のノードの往復時間遅延であり、

は

が取得された時刻である。）

ステップ（Ｓ１１１０）では、シンクノードによってｋ番目のノードの待機時間

が下記数式１１４のように計算される。

このように、ｋ番目のノードに待機時間

を付与すると、（ｋ−１）番目のノードのデータパケットとｋ番目のノードのデータパケットがシンクノードで受信衝突を起こすことを回避することができる。

ステップ（Ｓ１１２０）では、シンクノードが、ｋ番目のノードのデータパケットがシンクノードに到着する時刻の最大値

を前記数式１１２のように計算した後、前記ステップ（Ｓ１０８０）へ移行する。

一方、前記ステップ（Ｓ１０８０）で、前記変数ｋが最後番目（Ｋ番目）より小さくなければ（Ｎ）、すなわち、すべてのＫ個のノードに対してスケジュール計算が完了すると、ステップ（Ｓ１１３０）へ移行する。

ステップ（Ｓ１１３０）では、シンクノードによって１番目のビーコンパケットが第３設定時刻

にノードへ放送される。

ステップ（Ｓ１１４０）では、シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または、前記ステップ（Ｓ１１３０）による１番目のビーコンパケットの放送後に第４設定時間

を待機し、次の正規過程に進入する。

正規過程
図３は本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。初期化過程でシンクノードがビーコンパケットを放送し、すべてのノードからデータパケットの受信が完了する瞬間までを１番目のサイクルと定義すれば、正規過程は２番目のサイクルからである。ここで、ｎ番目のサイクルとは、図３に示すように、シンクノードがｎ番目のビーコンパケットを放送し、すべてのノードからデータパケットの受信が完了する瞬間までを意味する。ｎ番目のサイクルのビーコンパケットが放送される時刻を

と表記する。ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻を

と表記する。ｎ番目のサイクルでｋ番目のノードに付与される時間遅延を

と表記する。

ｎ番目のサイクルが終了すると、シンクノードによってシンクノードとｋ番目のノード間の往復時間遅延

が下記数式１１５のように計算される（Ｓ１１５０）。

（式中、

はｎ番目のサイクルのビーコンパケットが放送される時刻であり、

はｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻であり、

はｎ番目のサイクルでｋ番目のノードに付与される時間遅延であり、

はｎ番目のサイクルにおけるビーコン長の時間換算値である。）

ステップ（Ｓ１１５２）では、シンクノードが前記ステップ（Ｓ１１５０）で計算された往復時間遅延

を用いて往復時間遅延の小さい順にノードを整列する。
ステップ（Ｓ１１５４）では、シンクノードによって１サイクルの間に変化することが可能なノードの往復時間遅延変動幅

が下記数式１１６によって計算される。

（式中、

は（ｎ−１）番目のサイクルにおけるデータパケットの受信開始時刻である。）

シンクノードは、（ｎ−１）番目のサイクルにおけるビーコンパケット送信時刻、及び各ノードからのデータパケット受信時刻を用いてシンクノードと各ノード間の往復時間遅延値を得ることができるが、ｎ番目のサイクルで各ノードがデータパケットを送信する時点におけるシンクノードと各ノード間の往復時間遅延はノードの移動性により正確に知ることが難しい。本発明では、各ノードの（ｎ−１）番目のサイクルにおけるデータパケット受信開始時刻とｎ番目のサイクルにおけるデータパケット受信時刻との差を下記数式１１７のように近似し、

１サイクルの間に変化することが可能なシンクノードと各ノード間の往復時間遅延の変動幅を前記数式１１６のように計算する。数式１１７において、ｎ番目のスケジュール情報は、ｎ番目のサイクルでビーコンパケットに含ませて放送するので、ｎ番目のスケジュールを計算して導出する瞬間には

値は知ることができない値であることに留意すべきである。

図４は本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。ｎ番目のサイクルで（ｋ−１）番目のノードのデータパケットはｎ番目のビーコンパケット放送時刻を基準に

と

との間に受信完了する。したがって、本発明では、

が

よりも大きくなるようにして、ｎ番目のサイクルで（ｋ−１）番目のノードのデータパケットとｋ番目のノードのデータパケットがシンクノードで受信衝突を起こさないようにしなければならない。

ステップ（Ｓ１１６０）では、シンクノードが変数ｋを１に設定し、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値

を下記数式１１８のように計算する。

ステップ（Ｓ１１７０）では、シンクノードが、変数

が

より小さいか否かを決定し、変数

が


より小さければ（Ｙ）、

を「１」だけ増加させ（Ｓ１１８０）、次のステップ（Ｓ１１９０）を行う一方で、

が

以上であれば（Ｎ）、下記ステップ（Ｓ１２２０）を行う。

ステップ（Ｓ１１９０）では、シンクノードが、ｎ番目のサイクルでノードのデータパケットが受信され始める時刻の最小値

を下記数式１１９のように計算する。

ステップ（Ｓ１２００）では、シンクノードがｎ番目のサイクルでノードに付与される時間遅延

を下記数式１２０のように計算する。

ステップ（Ｓ１２１０）では、シンクノードが、ｎ番目のサイクルでノードのデータパケットが受信され始める時刻の最大値

を下記数式１２１のように計算した後、前記ステップ（Ｓ１１７０）へ移行する。

ステップ（Ｓ１２２０）では、シンクノードによってビーコンパケット放送が行われるか否かが決定される。

前記ステップ（Ｓ１２２０）でビーコンパケット放送が行われなければ（Ｎ）、スケジューリング過程を終了する。

一方、前記ステップ（Ｓ１２２０）でシンクノードによってビーコンパケット放送が決定されれば（Ｙ）、シンクノードによってｎ番目のサイクルのビーコンパケットが放送される時刻

にビーコンパケットが多数のノードに放送される（Ｓ１２３０）。

続いて、シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記ｎ番目のサイクルで最後番目のノードのデータパケットが受信され始める時刻の最大値

を待機し（Ｓ１２４０）、シンクノードによってサイクルが１だけ増加した後（Ｓ１２５０）、前記ステップ（Ｓ１１５０）へ移行する。

上述のように構成された本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードから多数のノードへ初期化パケットを放送し、シンクノードが多数のノードから第１設定時間

の間に初期化応答パケットを受信し、前記シンクノードが受信した初期化応答パケットからシンクノードと多数のノード間の往復時間遅延

を計算し、シンクノードによって初期化応答パケットの受信に衝突が存在するか否かを決定し、初期化応答パケットの受信に衝突が存在しなければ、シンクノードが計算された往復時間遅延

を用いて往復時間遅延の小さい順にノードを整列し、シンクノードによって変数ｋを１に設定し、１番目のノードの待機時間

を「０」に設定し、シンクノードによって１番目のノードのデータパケットがシンクノードに受信され始める時刻の最大値

を計算し、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し、変数ｋが最後番目（Ｋ番目）より小さければ、変数ｋをｋ＋１に設定し、シンクノードによってｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値

を計算し、シンクノードによってｋ番目のノードの待機時間

を計算し、シンクノードによってｋ番目のノードのデータパケットがシンクノードに到着する時刻の最大値

を計算した後、変数ｋが最後番目（Ｋ番目）より小さくなければ、シンクノードによって１番目のビーコンパケットが第３設定時刻

に多数のノードに放送され、シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または１番目のビーコンパケットの放送後に第４設定時間

を待機し、シンクノードによってシンクノードとｋ番目のノード間の往復時間遅延

を計算し、シンクノードが計算された往復時間遅延

を用いて往復時間遅延の小さい順にノードを整列し、シンクノードによって１サイクルの間に変化することが可能なノードの往復時間遅延変動幅

を計算し、変数ｋを１に設定し、シンクノードがｎ番目のサイクルで１番目のノードに付与される時間遅延

を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値

を計算し、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し、変数ｋが最後番目（Ｋ番目）より小さければ、変数ｋをｋ＋１に設定し、シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値

を計算し、シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延

を計算し、シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値

を計算した後、変数ｋが最後番目（Ｋ番目）より小くなければ、シンクノードによってビーコンパケット放送が行われるか否かが決定され、ビーコンパケット放送が行われなければ終了するように構成されることにより、水中で移動ノードの航法情報とは無関係に動作し、時間同期化が不要なので、時間同期化のための別途のパケット交換が必要ないから、ネットワークの歩留まりを向上させることができ、スケジュール情報が絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作し、各サイクル終了時点でシンクノードとノード間の往復時間遅延情報に対する正確な値が測定されるので、スケジュール情報は、時間が経過するにつれて誤差が累積されないため、周期的な再初期化が必要ない。

［第２実施形態］
図５は本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図であって、シンクノードがノードの伝送スケジュールを含んでいるビーコンパケットを放送し、シンクノードのビーコンパケットを受信したシンクノード以外のノードがビーコンパケットに含まれている各ノードの伝送スケジュールに従ってデータパケットをシンクノードへ伝送する。シンクノード以外のノードは「ノード」と略記することがある。本発明では、水中で音波を利用して通信が行われる場合を考慮し、シンクノードとｋ番目のノード間の最大相対速度

、水中での最小音波伝達速度

、シンクノードを除くノードの総数

は知っていると仮定する。

図６は本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。

本発明において、ｎ番目のサイクルとは、図６に示すように、シンクノードがｎ番目ビーコンパケットを放送する時刻から、すべてのノードからデータパケットの受信が完了した後に（ｎ＋１）番目のビーコンパケットを放送し始める時刻までの区間を意味する。

ｎ番目のサイクルのビーコンパケットが放送される時刻を

と表記する。すると、

である（式中、

はｎ番目のサイクルの持続時間である。）。ｎ番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻を

と表記する。

本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法は、各ノードがビーコンパケット受信時刻からどれほどの時間遅延の後にデータパケットを送信すべきかについての情報をシンクノードがビーコンパケットに含ませて送る。
ｎ番目のサイクルでｋ番目のノードのビーコン受信後にデータパケットを送信するときまでの待機時間を

と表記する。

でｎ番目のサイクルであることを明示する必要はないが、本発明を説明する上での明確性のために、

にｎ番目のサイクルを明示する添字を使用する。ノードの移動性により、ノードの往復時間遅延はサイクルごとに変化するが、本発明では、このように変化する往復時間遅延を過去の２サイクルの往復時間遅延情報を用いて推定し、シンクノードでノードのデータパケットの受信衝突が発生しないように

を定める。

本発明では、シンクノードと各ノード間の最初の往復時間遅延

、及びシンクノードと各ノード間の最初の往復時間遅延


が取得された時間

は知っていると仮定する。

及び

を取得することができるさまざまな方法が存在し、いかなる方法を使用しても、本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法は、サイクル数が増加すればするほど、

及び

とは無関係に正常状態に至るので、

及び

を取得するために使用する方法による本発明の時分割多重アクセス方法の性能変化は非常に小さい。

以下、上述のように構成されたネットワークトポロジーで行われる、本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法について説明する。
図７ａ及び図７ｂは本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作のフローチャートであって、ここで、Ｓはステップ（Ｓｔｅｐ）を意味する。

まず、シンクノードは、

及び

を用いて１番目のサイクルのスケジュールである

を決めるためには、まず、下記［数式２０１］のように初期化過程を行う（Ｓ２０１０）。

（式中、

は

よりも小さいか同じ自然数である。

は、ｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、

値を知っているので、すべて１に設定する。

はｎ番目のサイクルで、（ｎ−）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、

より過去に取得された往復時間遅延情報は最初に存在しないので、０にする。

は、直近に取得されたｋ番目のノードの往復時間遅延であり、現在の状態で

が直近に取得された往復時間遅延（すなわち、シンクノードと各ノード間の最初の往復時間遅延）であるので、

に設定する。

は、

が得られたサイクルであり、０に設定する。

はｎ番目のサイクルの持続時間であり、１番目のサイクル前のサイクル持続時間は知ることができないので、ユーザーが適正な

値を定めなければならないが、ここでは、その値を

と表示した。

は経験的に知っている平均的な

値にするか、或いは、サイクル持続時間は全体データパケット長の和とノードの往復時間遅延の最小値との和よりは大きいので、下記数式２０２のように推定されて定められる。）

（式中、

は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）

次いで、シンクノードは、次の手続きでｎ番目のサイクルでｋ番目のノードのビーコン受信後にデータパケット送信時までの待機時間

を計算してサイクル単位で各ノードのデータパケットを受信する（Ｓ２０２０乃至Ｓ２１４０）。

［ステップＳ２０２０］
シンクノードがデータパケットの受信順序を決定した後にｎ番目のサイクルで１番目のノードに付与される時間遅延

を０に設定する。

さらに詳細に説明すると、

の小さい順に整列した後、

とし、

とする。ｋ番目のノードとは、

がｋ番目に小さいノードを意味する。ｎ番目のサイクルでｋ番目のノードのデータパケットは、シンクノードにｋ番目に受信される。すなわち、ここで整列された順序は、シンクノードにデータパケットが到着する順序である。整列する方法としてさらに考慮できる方法は、

値が１であるノードを、

の小さい順に整列し、次に

値が０であるノードのうち、

値が１であるノードを、

の小さい順に整列し、次に

及び

値が全て０であるノードを

の小さい順に整列するようにすることにより、直近に往復時間遅延が取得されたノードに優先順位を付与する方法を使用することもできる。これ以外にも、応用分野に応じて、優先順位ベースの様々な整列方法が存在することができる。

［ステップＳ２０３０］
シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算する。

さらに詳細には、もし

であれば、つまり、直近の２サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合には、下記［数式２０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算する。

（式中、

はガード時間であり、

はｎ−１番目のサイクルで取得された１番目のノードの往復時間遅延であり、

はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、

はｎ−１番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻であり、

は下記数式２０４のとおりである。）

（式中、

は、ｎ−２番目のサイクルで取得された１番目のノードの往復時間遅延であり、

は、ｎ−２番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻である。）

もし、

値が２よりも小さい場合、すなわち、直近の２サイクルの間に１番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２０５］のようにｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算する。

（式中、

は往復時間遅延の最大値であり、

は直近に取得された１番目のノードの往復時間遅延であり、

はシンクノードとｋ番目のノード間の最大相対速度であり、

はｎ−１番目のサイクルの持続時間であり、

は１番目のノードの往復時間遅延が取得された直近のサイクルであり、

は水中での最小音波伝達速度である。）
前記［数式２０３］は、次の連立方程式である［数式２０６］を解いて得られる。

（式中、

はｎ番目のサイクルで１番目のノードのデータパケット受信時刻

に対する推定値である。）

前記［数式２０６］において、一番目の式は２点

及び

）を通る直線で１番目のノードのデータパケット受信時刻と往復時間遅延との関係を近似し、

で往復時間遅延

を計算したものである。一方、

はｎ番目のサイクルのスケジュール情報を計算する時点で正確に知ることができないが、１番目のノードの往復時間遅延とデータパケット受信時刻は、前記［数式２０６］における２番目の式のような関係を持つので、前記［数式２０６］を解くと、［数式２０３］のように

を計算することができる。［数式２０３］は、

であれば計算が不可能であるが、この場合は、１番目のノードとシンクノードの相対速度が音波の速度と同じ場合に該当するので、現実的に発生しない。

（ｎ−１）番目のサイクル及び（ｎ−２）番目のサイクルのうち、少なくとも１サイクルで１番目のノードの往復時間遅延が取得されなければ、［数式２０６］のように１番目のノードの往復時間遅延を求めることができないので、［数式２０５］のように１番目のノードの往復時間遅延が取得された直近の時点からできる限り最大変動幅を用いて往復時間遅延を推定するようにして衝突を回避する。［数式２０５］において、

は１番目のノードの往復時間遅延が取得された直近のサイクルであるので、

は往復時間遅延の取得後に費やされた時間を意味し、このとき、平均的なサイクル持続時間を、直近のサイクルである（ｎ−１）番目のサイクル持続時間に近似すると、

は直近に往復時間遅延が取得された後にｎ番目のサイクルでの往復時間遅延が持つことが可能な最大変動幅になる。したがって、

は、ｎ番目のサイクルで１番目のノードの最大往復時間遅延となり、この値が

を超えることができないので、［数式２０５］のように１番目のノードの往復時間遅延を計算する。（ｎ−１）番目のサイクル及び（ｎ−２）番目のサイクルのうちの少なくとも１サイクルで１番目のノードの往復時間遅延が取得されなかったというのは、物理階層が完璧であれば、１番目のノードの移動性が急に変わって他のノードのパケットとの衝突を発生したものと認知することができる。よって、過去の往復時間遅延情報からｎ番目のサイクルにおける往復時間遅延を推定することは好ましくないことに留意すべきである。また、このように計算された

は、

が持つことが可能な最大の値なので、

を計算するにあたり、［数式２０５］では、［数式２０３］とは異なり、ガード時間を含まない。

［ステップＳ２０４０］
シンクノードによって変数ｋが最後番目（Ｋ番目）より小さいか否かを判断する。

［ステップＳ２０５０］
前記ステップ（Ｓ２０４０）で前記変数ｋが最後番目（Ｋ番目）より小さければ（Ｙ）、シンクノードが前記変数ｋをｋ＋１に設定する。

［ステップＳ２０６０］
シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定する。

さらに詳細には、もし

であれば、すなわち、直近の２サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合には、下記［数式２０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定する。

（式中、

はｎ−１番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、

はｋ−１番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値であり、

はｎ−１番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻であり、

は下記数式２１１のとおりである。）

（式中、

はｎ−２番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、

はｎ−２番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻である。）

前記［数式２０７］は、２点

及び

を通る直線でｋ番目のノードのデータパケット受信時刻と往復時間遅延との関係を近似し、直前のデータパケットである（ｋ−１）番目のノードのデータパケットの受信が完了する時刻である

時刻にｋ番目のデータパケットが受信されるときに往復時間遅延

を計算したものである。したがって、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延

を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻

は、下記［数式２０８］のように計算される。

このとき、もし

であれば、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信しても、（ｋ−１）番目のノードのデータパケットの受信が完了してから、

だけの時間が経過した後にｋ番目のノードのデータパケットの受信が始まるので、前記［数式２０７］によって推定した

時刻でのｋ番目のノードの往復時間遅延は、実際のｋ番目のノードのデータパケットが到着する時点での往復時間遅延推定値として適切ではない。したがって、前記［数式２０６］を解いて前記［数式２０３］のように１番目のノードの往復時間遅延を推定した方式でｋ番目のノードの往復時間遅延を推定しなければならない。したがって、

の場合には、次のように［数式２０９］を解いて下記［数式２１０］のようにｋ番目のノードの往復時間遅延を推定する。前記［数式２１０］において、前記

は前記［数式２１１］のとおりである。

もし

値が２より小さい場合、すなわち、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２１２］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定する。

（式中、

は、

が得られたサイクルである。）

前記［数式２１２］は、［数式２０５］とは異なるが、これは、連続するデータパケットの衝突を回避するためには以前のデータパケットの終了時刻は遅く推定される方向にしなければならず、次のデータパケットの受信時刻は速く推定される方向にしなければならないからである。

［ステップＳ２０７０］
シンクノードが、前記ステップ（Ｓ２０６０）で推定されたｋ番目のノードの往復時間遅延

を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を下記［数式２１３］のように計算する。

［ステップＳ２０８０］
シンクノードが、前記ステップ（Ｓ２０７０）で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を用いて、ｋ番目のノードの待機時間

を下記［数式２１４］のように計算する。

［ステップＳ２０９０］
シンクノードが、前記ステップ（Ｓ２０７０）で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

と、前記ステップ（Ｓ２０８０）で計算されたｋ番目のノードの待機時間

を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値

を計算した後、前記ステップ（Ｓ２０４０）へ移行する。

さらに詳細には、もし

であれば、すなわち、直近の２サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値

は、下記［数式２１５］のように計算される。

（式中、

はｎ番目ののサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）

もし、

値が２より小さければ、すなわち、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値

は、下記［数式２１６］のように計算される。

ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値

の計算が完了すると、前記ステップ（Ｓ２０４０）へ移行する。

［ステップＳ２１００］
前記ステップ（Ｓ２０４０）で変数ｋが最後番目（Ｋ番目）より小さくなければ（Ｎ）、シンクノードがビーコンパケットの放送有無を判断してサイクルの進行如何を決定する。

このステップ（Ｓ２１００）でビーコンパケットが放送されないためサイクルが進行しない場合（Ｎ）には、すべての手続きを終了する。

［ステップＳ２１１０］
前記ステップ（Ｓ２１００）でビーコンパケットが放送されてサイクルが継続して進行する場合（Ｙ）には、シンクノードは、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻

にビーコンパケットを放送する。

［ステップＳ２１２０］
Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値

が超過する。

［ステップＳ２１３０］
前記ステップ（Ｓ２１２０）が行われた後、シンクノードは、ｎ番目のサイクルでｋ番目のノードの往復時間遅延

を計算し、往復時間遅延取得有効性値

及び直近に取得された往復時間遅延関連情報

を更新する。

より詳細には、往復時間遅延取得有効性値

を更新するために、下記［数式２１７］のようにすべてのノードに対して往復時間遅延取得有効性値

を更新し、もしｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式２１８］のようにする。

もしｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式２１９］のようにする。

直近に取得された往復時間遅延関連情報

は、下記［数式２２０］のように更新する。

また、往復時間遅延取得有効性値

が１である場合には、下記［数式２２１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を計算し、直近に取得された往復時間遅延関連情報


を更新する。

［ステップＳ２１４０］
シンクノードがｎを１だけ増加させた後、（ｎ＋１）番目のサイクルのための

計算のために、前記ステップ（Ｓ２０２０）へ移行する。

前述のように構成された本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードが初期化過程を行い；シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を０に設定し；シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算し；シンクノードによって変数ｋが最後番目（Ｋ番目）より小さいか否かを判断し；前記判断で変数ｋが最後番目（Ｋ番目）より小さければ、シンクノードが前記変数ｋをｋ＋１に設定し、シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定し；シンクノードが、前記推定されたｋ番目のノードの往復時間遅延

を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を計算し；シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を用いて、ｋ番目のノードの待機時間

を計算し；及び、シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

と前記計算されたｋ番目のノードの待機時間

を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値

を計算した後、前記判断過程へ移行するように構成されることにより：
すなわち、水中音響無線移動ネットワークなどのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、多数のノードがシンクノードへデータパケットを時分割多重アクセス方式で伝送しようとするとき、ノードの移動性による往復時間遅延をサイクル単位で追跡してシンクノードがノードからのデータパケットを受信する上で遊休時間を最小化することにより、チャンネル使用効率の向上によるネットワークの効率が大幅に向上することができる。特に、ノード数が増加すればするほど、ネットワーク効率の向上程度はさらに増加する。本発明に係る水中無線移動ネットワークのためのスケジューリング方法は、絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作する。したがって、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能である。

また、往復時間遅延情報に対する正確な値がサイクルごとに得られるので、誤差が累積されないため周期的な再初期化が必要ない。

［第３実施形態］
図８は本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図であって、シンクノードが、ノードの伝送スケジュールを含んでいるビーコンパケットを放送し、シンクノードのビーコンパケットを受信したシンクノード以外のノードが、ビーコンパケットに含まれている各ノードの伝送スケジュールに従ってデータパケットをシンクノードへ伝送する。シンクノード以外のノードは「ノード」と略記することがある。本発明では、水中で超音波を利用して通信が行われる場合を考慮し、シンクノードとｋ番目のノード間の最大相対速度

、水中での音波伝達速度の最小値

、シンクノードを除くノードの総数

は知っていると仮定する。

図９は本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。

本発明において、ｎ番目のサイクルとは、図９に示すように、シンクノードがｎ番目のビーコンパケットを放送する時刻から、すべてのノードからデータパケットの受信が完了した後に（ｎ＋１）番目のビーコンパケットを放送し始める時刻までの区間を意味する。

ｎ番目のサイクルのビーコンパケットが放送される時刻を

と表記する。そうすれば、

である（式中、

はｎ番目のサイクルの持続時間である。）。ｎ番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻を

と表記する。

本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法は、各ノードがビーコンパケット受信時刻かからどれほどの時間遅延後にデータパケットを送信しなければならないかについての情報をシンクノードがビーコンパケットに含ませて送る。

ｎ番目のサイクルでｋ番目のノードのビーコン受信後にデータパケット送信時までの待機時間を

と表記する。

でｎ番目のサイクルであることを明示する必要はないが、本発明を説明する上での明確性のために、

にｎ番目のサイクルを明示する添字を使用する。ノードの移動性により、ノードの往復時間遅延はサイクルごとに変化するが、本発明では、このように変化する往復時間遅延を過去のＭ個のサイクルの往復時間遅延情報を用いて推定し、シンクノードでノードのデータパケットの受信衝突が発生しないように

を定める。

本発明では、シンクノードと各ノード間の最初の往復時間遅延

、及びシンクノードと各ノード間の最初の往復時間遅延

が取得された時間

は知っていると仮定する。

及び

を取得することができるさまざまな方法が存在し、いかなる方法を使用しても、本発明の第３実施形態による多項式補間法を用いた水中無線移動ネットワークのためのスケジューリング方法は、サイクル数が増加すればするほど、

及び

とは無関係に正常状態に至るので、

及び

を取得するために使用する方法による本発明のスケジューリング方法の性能変化は非常に小さい。

以下、上述のように構成されたネットワークトポロジーで行われる本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法について説明する。
図１０ａ乃至図１０ｃは本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートであって、ここで、Ｓはステップ（Ｓｔｅｐ）を意味する。

まず、シンクノードは、

及び

を用いて１番目のサイクルのスケジュールである

を定めるためには、まず、下記［数式３０１］のように初期化過程を行う（Ｓ３０１０）。

（式中、

は

よりも小さいか同じ自然数であり、

である。

は、ｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、

値を知っているので、すべて１に設定する。

は、ｎ番目のサイクルで、（ｎ−ｍ）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、

より過去に取得された往復時間遅延情報は最初に存在しないので、

が１よりも大きい場合には０とする。

は直近に取得されたｋ番目のノードの往復時間遅延であり、現在の状態で

が直近に取得された往復時間遅延であるので、

に設定する。

は、

が得られたサイクルであり、０に設定する。

はｎ番目のサイクルの持続時間であり、１番目のサイクル前のサイクル持続時間は知ることができないので、ユーザーが適正な

値を定めなければならないが、数式３０１ではその値を

と表示した。

は経験的に知っている平均的な

値にするか、或いはサイクル持続時間は全体データパケット長の和とノードの往復遅延時の最小値との和よりは大きいので、下記数式３０２のように推定されて定められる。）

（式中、

は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）

次いで、シンクノードは、次のような手続きでｎ番目のサイクルでｋ番目のノードのビーコン受信後にデータパケット送信時までの待機時間

を計算してサイクル単位で各ノードのデータパケットを受信する（Ｓ３０２０乃至Ｓ３１４０）。

［ステップＳ３０２０］
シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を０に設定する。

さらに詳細に説明すると、

の小さい順に整列した後、

とし、

とする。ｋ番目のノードとは、

がｋ番目に小さいノードを意味する。ｎ番目のサイクルでｋ番目のノードのデータパケットはシンクノードにｋ番目に受信される。すなわち、ここで整列された順序は、シンクノードにデータパケットが到着する順序である。整列する方法としてさらに考慮できる方法は、

値が１であるノードを

の小さい順に整列し、次に

値が０であるノードのうち、

値が１であるノードを

の小さい順に整列し、次に

及び

値がすべてが０であるノードを

の小さい順に整列し、以下反復であって、次に

値がすべて０であるノードを

の小さい順に整列する方式とすることにより、直近に往復時間遅延が取得されたノードに優先順位を付与する方法を使用することもできる。これ以外にも、応用分野に応じて、優先順位ベースの様々な整列方法が存在することができる。

［ステップＳ３０３０］
シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算する。

さらに詳細には、

と定義しよう。

は２以上の自然数とする。

は、ユーザーが定める値である。もし

であれば、すなわち、直近の

サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が

回以上である場合には、ｎ番目のサイクルで１番目のノードの往復時間遅延

を下記［数式３０３］のように連立方程式を解いて推定する。

（式中、

は

座標を通る最小次数の多項式である。ここで、

サイクルで１番目のノードの有効な往復時間遅延が取得された。そのとき、１番目のノードの往復時間遅延値は

である。

は

次の多項式であって、多項式補間法を用いて容易に求めることができる。例えば、分割された差（ｄｉｖｉｄｅｄ ｄｉｆｆｅｒｅｎｃｅ）方法を用いることができる。［数式３０３］は、

次多項式と１次多項式の連立方程式であって、［数式３０３］の２番目の１次多項式を［数式３０３］の１番目の

次多項式に代入すると、結果的に

次多項式の解を求める問題に帰結する。［数式３０３］は、解が唯一に存在するか、解が存在しないか、解が多数存在するか、或いは解が数多く存在することができる。［数式３０３］の解が存在するためには、［数式３０３］の１番目の

次多項式が［数式３０３］の２番目の１次多項式の上または下にあるべきである。本発明において、

であるので、すなわち、

値は範囲が制限されているので、［数式３０３］の１番目の

次多項式は

の変化に応じて一定の範囲内で

軸と平行に近い形態でグラフが表現される。一方、［数式３０３］の２番目の１次多項式は、傾きが「１」である。したがって、解が存在しない場合は発生しない。また、

が２である場合には、［数式３０３］の１番目の

次多項式が１次多項式になるが、上述したような理由で、［数式３０３］を構成する２つの１次多項式の傾きが互いに変わり、［数式３０３］の実数解が唯一に存在する。

が３以上である場合には、複素数の解を含んで多数の解が存在することができ、実数解も複数個存在することができる。実数解が複数個存在するためには、［数式３０３］の１番目の

次多項式が傾き「１」以上の急激な変化を示さなければならず、これは、

であることを考慮すれば、

値のヒストリーが両端値である「０」または

値を持つことを意味するので、この場合にも、実数解は１つを持つ確率が非常に高い。別の方法で解釈すると、このように急激なトポロジーの変化を示す環境は、過去の往復時間遅延情報を用いて現在の往復時間遅延情報を推定することが難しい場合に該当する。この際にも、本発明は、往復時間遅延情報を保守的に適用するように設計され、安定的に動作することができる。先立って、［数式３０３］を解くことは

次多項式の解を求めるのと同様であると述べたが、一般に、

次多項式は、

個の解を有し、ここには複素数の解と実数の解とが混合されている。本発明では、［数式３０３］を解析的に直接解く場合よりは次のようにインタラクティブ（ｉｔｅｒａｔｉｖｅ）に求める。まず、

の初期値を定める。例えば、

とする。これ以外にも、

などのように初期値を定める方法は多様にあり、

に近接する値となるように設定するのが良い。この際、初期値

を用いて［数式３０３］から

を

のように計算する。そして、このように計算された

を用いて

を

のように計算し、このとき、計算された

から

を

のように計算する。

を用いて

を

のように計算し、計算された

から

を

のように計算する過程を、定められた回数だけ繰り返した後、最終的に計算される値を

と

に確定する。このとき、繰り返し回数を定めず、以前に計算された

と現在計算された

との差が一定値以下である場合に繰り返し過程を中断する方法がある。同様に、以前に計算された

と現在計算された

との差が一定値以下である場合に繰り返し過程を中断する方法もある。

は

よりは小さいので、下記数式３０４のように値を制限する。）

（式中、

は往復時間遅延の最大値である。）

そして、１番目のノードのデータパケット受信完了時点

を下記［数式３０５］のように計算する。

（式中、

はｎ番目のサイクルで１番目のノードのデータパケット長を時間に換算した値であり、

はガード時間である。）

もし

であれば、すなわち、直近の

サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が

回未満であれば、過去に取得された時間遅延から現在の時間遅延を推定することが妥当ではないと判断する。このときは、下記［数式３０６］のようにｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算する。

（式中、

は、直近に取得された１番目のノードの往復時間遅延であり、

はシンクノードとｋ番目のノード間の最大相対速度であり、

はｎ−１番目のサイクルの持続時間であり、

は１番目のノードの往復時間遅延が取得された直近のサイクルであり、

は水中での最小音波伝達速度である。）

［数式３０６］のように１番目のノードの往復時間遅延が取得された直近の時点からできる限り最大変動幅を用いて往復時間遅延を推定すると、衝突を根本的に回避することができる。［数式３０６］において、

は１番目のノードの往復時間遅延が取得された直近のサイクルであるため、

は往復時間遅延の取得後に費やされた時間を意味し、このとき、平均的なサイクル持続時間を直近のサイクルである（ｎ−１）番目のサイクル持続時間に近似すると、

は、直近に往復時間遅延が取得された後、ｎ番目のサイクルでの往復時間遅延が持つことが可能な最大変動幅になる。よって、

はｎ番目のサイクルで１番目のノードの最大往復時間遅延となり、この値が

を超えることができないので、［数式３０６］のように１番目のノードの往復時間遅延を計算する。直近の

個のサイクルのうち、

個未満のサイクルでのみ１番目のノードの往復時間遅延が取得されたというのは、物理階層が完璧であれば、１番目のノードの移動性が急に変わって他のノードのパケットとの衝突を発生したものと認知することができる。よって、過去の往復時間遅延情報からｎ番目のサイクルでの往復時間遅延を推定することは好ましくないことに留意すべきである。また、このように計算された

は、

が持つことが可能な最も大きい値なので、

を計算するにあたり、［数式３０６］では、［数式３０５］とは異なり、ガード時間を含まない。

［ステップＳ３０４０］
シンクノードによって変数ｋが最後番目（Ｋ番目）より小さいか否かを判断する。

［ステップＳ３０５０］
前記ステップ（Ｓ３０４０）で前記変数ｋが最後番目（Ｋ番目）より小さければ（Ｙ）、シンクノードが前記変数ｋをｋ＋１に設定する。

［ステップＳ３０６０］
シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定する。

さらに詳細には、

と定義しよう。もし

であれば、すなわち、直近の

サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が

回以上であれば、下記［数式３０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定する。

（式中、

は

座標を通る最小次数の多項式である。ここで、

サイクルでｋ番目のノードの有効な往復時間遅延が取得された。そのとき、ｋ番目のノードの往復時間遅延値は

である。

は、

次の多項式であって、多項式補間法を用いて容易に求めることができる。数式３０７は、過去に取得された往復時間遅延情報を数値解析的補間法で近似し、直前のデータパケットである（ｋ−１）番目のノードのデータパケットの受信が終了する時刻である

時刻にｋ番目のデータパケットが受信されるときに往復時間遅延

を計算したものである。）

したがって、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延

を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻

は、下記［数式３０８］のように計算される。

このとき、もし

であれば、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信しても、（ｋ−１）番目のノードのデータパケットの受信が完了してから

だけの時間が経過した後にｋ番目のノードのデータパケットの受信が始まるので、［数式３０７］によって推定した

時刻でのｋ番目のノードの往復時間遅延は、実際のｋ番目のノードのデータパケットが到着する時点での往復時間遅延推定値として適切ではない。よって、［数式３０３］を反復的な方法で解いて１番目のノードの往復時間遅延を推定した方式でｋ番目のノードの往復時間遅延を推定しなければならない。したがって、

の場合には、次のように連立方程式である［数式３０９］を解いてｋ番目のノードの往復時間遅延

を推定する。

［数式３０３］と同様に、［数式３０９］は、

次多項式の解を求める問題であって、

が２である場合には、実数解が唯一に存在するので、解析的解を利用し、

が３以上である場合には、次のように反復的な方法を用いて解を求める。まず、

の初期値を定める。例えば、

とする。これ以外にも、

などのように初期値を定める方法は多様にあり、

に近接する値となるように設定するのが良い。このとき、初期値

を用いて、［数式３０９］から

を

のように計算する。このように計算された

を用いて

を

のように計算し、このとき、計算された

から

を

のように計算する。

を用いて

を

のように計算し、計算された

から

を

のように計算する過程を、定められた回数だけ繰り返し行った後、最終的に計算された値を

と

に確定する。このとき、繰り返し回数を定めず、以前に計算された

と現在計算された

との差が一定値以下である場合に繰り返し過程を中断する方法がある。同様に、以前に計算された

と現在計算された

との差が一定値以下である場合に繰り返し過程を中断する方法もある。

よりも小さいので、下記［数式３１０］のように値を制限する。

もし

であれば、すなわち、直近の

サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が

回未満であれば、過去に取得された時間遅延から現在の時間遅延を推定することが妥当ではないと判断する。この際には、下記［数式３１１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定する。

前記［数式３１１］は［数式３０６］とは異なるが、これは、連続するデータパケットの衝突を回避するためには以前データパケットの終了時刻は遅く推定される方向にしなければならず、次のデータパケットの受信時刻は速く推定される方向にしなければならないからである。

［ステップＳ３０７０］
シンクノードが、前記ステップ（Ｓ３０６０）で推定されたｋ番目のノードの往復時間遅

を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を前記［数式３０８］のように計算する。

［ステップＳ３０８０］
シンクノードが、前記ステップ（Ｓ３０７０）で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を用いて、ｋ番目のノードの待機時間

を下記［数式３１２］のように計算する。

このように、ｎ番目のサイクルでｋ番目のノードがビーコンパケットを受信した後、

時間だけ待機してからデータパケットを送信すると、（ｋ−１）番目のノードのデータパケットが受信完了した後にｋ番目のノードのデータパケットが受信され、シンクノードでデータパケットの受信衝突が発生しない。

［ステップＳ３０９０］
シンクノードが、前記ステップ（Ｓ３０７０）で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

と、前記ステップ（Ｓ３０８０）で計算されたｋ番目のノードの待機時間

を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値

を計算した後、前記ステップ（Ｓ３０４０）へ移行する。

より詳細には、もし

であれば（すなわち、直近の

サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が

回以上であれば）、ｋ番目のノードのデータパケットが受信終了する時刻

は、下記［数式３１３］のように計算される。

（

はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）

一方、もし

であれば（すなわち、直近の

サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が

回未満であれば）、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値

は、下記［数式３１４］のように計算される。

［ステップＳ３１００］
前記ステップ（Ｓ３０４０）で変数ｋが最後番目（Ｋ番目）より小さくなければ（Ｎ）、シンクノードがビーコンパケットの放送有無を判断する。

すなわち、Ｋ番目のノードのスケジュール計算が完了すると、シンクノードがビーコンパケットの放送有無を判断してサイクルの進行如何を決定する。

一方、ステップ（Ｓ３０４０）でビーコンパケットが放送されなければ（Ｎ）（すなわち、サイクルを進行しない場合には）、すべての手続きを終了する。

［ステップＳ３１１０］
前記ステップ（Ｓ３１００）でビーコンパケットが放送されてサイクルが継続して進行する場合には（Ｙ）、シンクノードは、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻

にビーコンパケットを放送する。

［ステップＳ３１２０］
Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値

が超過する。

［ステップＳ３１３０］
前記ステップ（Ｓ３１２０）が行われた後、シンクノードは、ｎ番目のサイクルでｋ番目のノードの往復時間遅延

を計算し、往復時間遅延取得有効性値

及び直近に取得された往復時間遅延関連情報

を更新する。

より詳細には、

時刻にビーコンパケットを放送した後、Ｋ番目のノードのデータパケットの受信が完了したか或いは

時刻を超過すれば、シンクノードは、ｎ番目のサイクルにおける各ノードからのデータパケットの成功的な受信か否かを知ることができる。まず、

値を更新するために、下記［数式３１５］のようにすべての

及び

について、ノードに対して

値を下記［数式３１５］のように更新する。

ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式３１６］のようにする。

ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式３１７］のようにする。

そして、直近に取得された往復時間遅延関連情報

は、下記［数式３１８］のように更新する。

また、往復時間遅延取得有効性値

が１である場合には、下記［数式３１９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延

を計算し、直近に取得された往復時間遅延関連情報

を更新する。

［ステップＳ３１４０］
シンクノードがｎを１だけ増加させた後、（ｎ＋１）番目のサイクルのための

計算のために、前記ステップ（Ｓ３０２０）へ移行する。

本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードが初期化過程を行い；前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延

を０に設定し；シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延

を推定し、１番目のノードのデータパケット受信完了時点

を計算し；シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し；前記判断で変数ｋが最後番目（Ｋ番目）より小さければ、シンクノードが変数ｋをｋ＋１に設定し；シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延

を推定し；シンクノードが、前記推定されたｋ番目のノードの往復時間遅延

を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を計算し；シンクノードが、計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

を用いて、ｋ番目のノードの待機時間

を計算し；前記シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値

と、前記計算されたｋ番目のノードの待機時間

を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値

を計算した後、前記判断過程へ進むように構成されることにより：
つまり、水中音響無線移動ネットワークのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、チャンネル使用効率の向上によるネットワーク効率を向上させることができ、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であり、誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。特に、ノード数が増加すればするほど、ネットワーク効率の向上程度はさらに増加する。本発明に係る多項式補間法を用いた水中無線移動ネットワークのためのスケジューリング方法は、絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作する。したがって、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能である。

また、往復時間遅延情報に対する正確な値がサイクルごとに得られるので、誤差が累積されないため周期的な再初期化が必要ない。

図面と明細書には好適な実施形態が開示されており、特定の用語が使用されているが、これは、単に本発明の実施形態を説明するための目的で使用されたものであり、意味を限定し或いは特許請求の範囲に記載された本発明の範囲を制限するために使用されたものではない。したがって、本技術分野における通常の知識を有する者であれば、これから様々な変形及び均等な他の実施形態が可能であることを理解することができるだろう。よって、本発明の真正な技術的保護範囲は、添付された特許請求の範囲の技術的思想によって定められなければならないだろう。

本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。 本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。

［式中、
は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、
は初期化パケット長の時間換算値であり、
は初期化応答パケット長の時間換算値であり、
はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。

〔図面の簡単な説明〕
〔図１〕本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図２ａ乃至図２ｆ〕本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
〔図３〕本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。
〔図４〕本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。
〔図５〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図６〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
〔図７ａ乃至図７ｃ〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
〔図８〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図９〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
〔図１０ａ乃至図１０ｃ〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。

(式中、
は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、
は初期化パケット長の時間換算値であり、
は初期化応答パケット長の時間換算値であり、
はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。)

は、１番目のノードのデータパケットがシンクノードに到着する時刻の最大値である。したがって、２番目のノードは、シンクノードに最も速くデータパケットが受信され始める場合にも、１番目のノードのデータパケットがシンクノードで受信完了した後に受信が始まるように待機時間を付与することが、シンクノードでノードのデータパケットの受信衝突を回避する核心アイデアである。２番目のノードのデータパケットがシンクノードに最も速く受信され始める場合は、２番目のノードがシンクノードの動き方向とは正反対の方向に最大速度で動く場合であるが、すなわち、２番目のノードとシンクノードとが最大相対速度で互いに遠ざかるとき、２番目のノードがビーコンパケットの受信後に時間遅延なしに直ちにデータパケットを送信すると、シンクノードでは、いくら速くても下記数式１１０のように与えられる
後に２番目のノードのデータパケットの受信が始まる。

は、
よりも小さいので、下記［数式３１０］のように値を制限する。

計算が完了すると、ステップ（Ｓ３０４０）に戻る。

本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。 本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリ ング方法を説明するための動作フローチャートである。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。 本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。

Claims (50)

1. 一つのシンクノードと多数のノードとから構成されたネットワークトポロジーでスケジューリングを行う、水中無線移動ネットワークのためのスケジューリング方法であって：
   シンクノードから多数のノードへ初期化パケットを放送する第１段階と、
   前記シンクノードが多数のノードから第１設定時間
   
   の間に初期化応答パケットを受信する第２段階と、
   前記シンクノードが、前記第２段階で受信した初期化応答パケットから前記シンクノードと多数のノード間の往復時間遅延
   
   を計算する第３段階と、
   前記シンクノードによって、初期化応答パケットの受信に衝突が存在するか否かを決定する第４段階と、
   前記第４段階で初期化応答パケットの受信に衝突が存在しなければ、前記シンクノードが、前記第３段階で計算された往復時間遅延
   
   を用いて往復時間遅延の小さい順にノードを整列する第５段階と、
   前記シンクノードによって変数ｋが１に設定され、１番目のノードの待機時間
   
   が「０」に設定される第６段階と、
   前記シンクノードによって、１番目のノードのデータパケットが前記シンクノードに受信され始める時刻の最大値
   
   が計算される第７段階と、
   前記変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第８段階と、
   前記第８段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記変数ｋをｋ＋１に設定する第９段階と、
   前記シンクノードによって、ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値
   
   が計算される第１０段階と、
   前記シンクノードによって前記ｋ番目のノードの待機時間
   
   が計算される第１１段階と、
   前記シンクノードによって前記ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最大値
   
   を計算した後、前記第８段階へ移行する第１２段階と、
   前記第８段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードによって１番目のビーコンパケットが第３設定時刻
   
   に多数のノードへ放送される第１３段階と、
   前記シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記第１３段階による１番目のビーコンパケットの放送後に第４設定時間
   
   を待機する第１４段階と、
   前記シンクノードによって前記シンクノードと前記ｋ番目のノード間の往復時間遅延
   
   が計算される第１５段階と、
   前記シンクノードが、前記第１５段階で計算された往復時間遅延
   
   を用いて往復時間遅延の小さい順にノードを整列する第１６段階と、
   前記シンクノードによって、１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
   
   が計算される第１７段階と、
   前記変数ｋを１に設定し、前記シンクノードが、ｎ番目のサイクルで１番目のノードに付与される時間遅延
   
   を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値
   
   を計算する第１８段階と、
   前記変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第１９段階と、
   前記第１９段階で前記変数ｋ最後番目（Ｋ番目）より小さければ、前記変数ｋをｋ＋１に設定する第２０段階と、
   前記シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値
   
   を計算する第２１段階と、
   前記シンクノードが、ｎ番目のサイクルでｋ番目のノードに付与される時間遅延
   
   を計算する第２２段階と、
   前記シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値
   
   を計算した後、前記第１９段階へ移行する第２３段階と、
   前記第１９段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードによって、ビーコンパケット放送が行われるか否かが決定される第２４段階と、
   前記第２４段階でビーコンパケット放送が行われなければ終了する第２５段階とを含むことを特徴とする、水中無線移動ネットワークのためのスケジューリング方法。
2. 前記第２４段階でシンクノードによってビーコンパケット放送が決定されれば、
   前記シンクノードによってｎ番目のサイクルのビーコンパケットが放送される時刻
   
   にビーコンパケットがノードに放送される第２６段階と、
   前記シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記ｎ番目のサイクルで最後番目のノードのデータパケットが受信され始める時刻の最大値
   
   を待機する第２７段階と、
   前記シンクノードによってサイクルが１だけ増加した後、前記第１５段階へ移行する第２８段階とが行われる、請求項１に記載の水中無線移動ネットワークのためのスケジューリング方法。
3. 前記第４段階で初期化応答パケットの受信に衝突が存在すれば、
   前記シンクノードによって再初期化パケットがノードに放送される第２９段階と、
   前記シンクノードによって第２設定時間
   
   だけ再初期化応答パケットが受信される第３０段階と、
   前記シンクノードが、前記第３０段階で受信した再初期化応答パケットから前記シンクノードとノード間の往復時間遅延
   
   を計算する第３１段階と、
   前記シンクノードによって、再初期化応答パケットの受信に衝突が存在するか否かを決定する第３２段階とが行われ、
   前記第３２段階で再初期化応答パケットの受信に衝突が存在すれば前記第２９段階へ移行する、請求項１に記載の水中無線移動ネットワークのためのスケジューリング方法。
4. 前記第３２段階で再初期化応答パケットの受信に衝突が存在しなければ、前記第５段階へ移行する、請求項３に記載の水中無線移動ネットワークのためのスケジューリング方法。
5. 前記第１設定時間
   
   
   は下記数式１０１によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
   
   ［式中、
   
   は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、
   
   は初期化パケット長の時間換算値であり、
   
   は初期化応答パケット長の時間換算値であり、
   
   はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。
   
   （ｒはモデムの最大通信半径であり、ｃは音波速度である。）］
6. 前記シンクノードと多数のノード間の往復時間遅延
   
   は下記数式１０３によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
   
   （式中、
   
   はノードＨから受信された初期化応答パケットの受信時刻であり、
   
   は初期化パケット放送時間である。）
7. 前記１番目のノードのデータパケットが前記シンクノードに受信され始める時刻の最大値
   
   は、下記数式１０８によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
   
   （式中、
   
   はシンクノードによる最初のビーコンパケット放送時刻であり、
   
   はビーコンパケット長の時間換算値であり、
   
   は１番目のノードの往復時間遅延であり、
   
   は１番目のノードのシンクノードとの往復時間遅延が取得された時点であり、
   
   はシンクノードとノード間の最大相対速度である。）
8. 前記ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値
   
   は、下記数式１１３によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
   
   （式中、
   
   はｋ番目のノードの往復時間遅延であり、
   
   は
   
   が取得された時刻である。）
9. 前記ｋ番目のノードの待機時間
   
   は下記数式１１４によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
   
   ［式中、
   
   はＡ及びＢの両者から大きい値を選択する関数であり、
   
   はｋ−１番目のノードのデータパケットがシンクノードに到着する時刻の最大値であって、下記数式１１２によって決定され、
   
   はｋ−１番目のノードのデータパケット長の時間換算値である。
   
   （式中、
   
   はｋ−１番目のノードの往復時間遅延であり、
   
   はｋ−１番目のノードの待機時間であり、
   
   は
   
   が取得された時間である。）］
10. 前記シンクノードと前記ｋ番目のノード間の往復時間遅延
    
    は下記数式１１５によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ番目のサイクルのビーコンパケットが放送される時刻であり、
    
    はｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻であり、
    
    はｎ番目のサイクルでｋ番目のノードに付与される時間遅延であり、
    
    はｎ番目のサイクルにおけるビーコン長の時間換算値である。）
11. 前記１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
    
    は下記数式１１６によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    は（ｎ−１）番目のサイクルにおけるデータパケットの受信開始時刻である。）
12. 各ノードの（ｎ−１）番目のサイクルにおけるデータパケットの受信時刻
    
    とｎ番目のサイクルにおけるデータパケットの受信時刻
    
    との差は下記数式１１７のように近似した、請求項１１に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
13. 前記第２設定時間
    
    は下記数式１０５によって決定される、請求項３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    は再初期化パケット長の時間換算値であり、
    
    は再初期化応答パケット長の時間換算値である。）
14. 前記ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値
    
    は、下記数式１１８によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ−１番目のサイクルにおける１番目のノードの往復時間遅延であり、
    
    はｎ番目のサイクルにおける１番目のノードのデータパケット長の時間換算値である。）
15. 前記シンクノードにｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値
    
    は、下記数式１１９によって計算される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ−１番目のサイクルにおけるｋ番目のノードの往復時間遅延である。）
16. 前記シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延
    
    は、下記数式１２０によって計算される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    (式中、
    
    はｎ番目のサイクルでｋ−１番目のノードのデータパケットが受信され始める時刻の最大値である。)
17. 前記シンクノードにｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値
    
    は、下記数式１２１によって計算される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ番目のサイクルにおけるｋ番目のノードのデータパケット長の時間換算値である。）
18. 伝送スケジュールを含んでいるビーコンパケットを放送する一つのシンクノードと、前記シンクノードのビーコンパケットを受信して伝送スケジュールに従ってデータパケットを前記シンクノードへ伝送する多数のノードとから構成されたネットワークトポロジーで時分割多重アクセスを行う、水中無線移動ネットワークのためのスケジューリング方法であって：
    前記シンクノードが初期化過程を行う第１’段階と、
    前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
    
    を０に設定する第２’段階と、
    前記シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
    
    を推定し、１番目のノードのデータパケット受信完了時点
    
    を計算する第３’段階と、
    前記シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第４’段階と、
    前記第４’段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記シンクノードが前記変数ｋをｋ＋１に設定する第５’段階と、
    前記シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を推定する第６’段階と、
    前記シンクノードが、前記第６’段階で推定されたｋ番目のノードの往復時間遅延
    
    を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
    
    を計算する第７’段階と、
    前記シンクノードが、前記第７’段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
    
    を用いて、ｋ番目のノードの待機時間
    
    を計算する第８’段階と、
    前記シンクノードが、前記第７’段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
    
    と前記第８’段階で計算されたｋ番目のノードの待機時間
    
    を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
    
    を計算した後、前記第４’段階へ移行する第９’段階とを含む、水中無線移動ネットワークのためのスケジューリング方法。
19. 前記第４’段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードがビーコンパケットの放送有無を判断する第１０’段階をさらに含み、
    前記第１０’段階でビーコンパケットが放送されなければすべての手続きを終了する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
20. 前記第１０’段階でビーコンパケットが放送されれば、
    前記シンクノードが、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻
    
    にビーコンパケットを放送する第１１’段階と、
    Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値
    
    が超過する第１２’段階と、
    前記シンクノードが、ｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を計算し、往復時間遅延取得有効性値
    
    及び直近に取得された往復時間遅延関連情報
    
    を更新する第１３’段階と、
    前記シンクノードがｎを１だけ増加させた後、前記第２’段階へ移行する第１４’段階とを含む、請求項１９に記載の水中無線移動ネットワークのためのスケジューリング方法。
21. 前記第１’段階で、前記シンクノードは下記［数式２０１］のように初期化過程を行う、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
    
    はｎ番目のサイクルで、（ｎ−２）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
    
    は直近に取得されたｋ番目のノードの往復時間遅延であり、
    
    は
    
    が得られたサイクルであり、
    
    はシンクノードと各ノード間の最初の往復時間遅延であり、
    
    は１番目のサイクル前の持続時間であり、
    
    は下記数式２０２のように推定されて定められる。）
    
    （
    
    は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
22. 前記第３’段階は、直近の２サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合には、下記［数式２０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
    
    を推定し、１番目のノードのデータパケット受信完了時点
    
    を計算する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はガード時間であり、
    
    はｎ−１番目のサイクルで取得された１番目のノードの往復時間遅延であり、
    
    はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、
    
    はｎ−１番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻であり、
    
    は下記数式２０４のとおりである。）
    
    （式中、
    
    はｎ−２番目のサイクルで取得された１番目のノードの往復時間遅延であり、
    
    はｎ−２番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻である。）
23. 前記［数式２０３］は、下記の連立方程式である［数式２０６］を解いて得られる、請求項２２に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ番目のサイクルで１番目のノードのデータパケット受信時刻
    
    に対する推定値である。）
24. 前記第３’段階は、直近の２サイクルの間に１番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２０５］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
    
    を推定し、１番目のノードのデータパケット受信完了時点
    
    を計算する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    は往復時間遅延の最大値であり、
    
    は直近に取得された１番目のノードの往復時間遅延であり、
    
    はシンクノードとｋ番目のノード間の最大相対速度であり、
    
    はｎ−１番目のサイクルの持続時間であり、
    
    は１番目のノードの往復時間遅延が取得された直近のサイクルであり、
    
    は水中での最小音波伝達速度である。）
25. 前記第６’段階は、直近の２サイクルの間にｋ番目のノードの往復時間遅延
    
    が成功的に取得された場合には、下記［数式２０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を推定する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ−１番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、
    
    はｋ−１番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値であり、
    
    はｎ−１番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻であり、
    
    は下記数式２１１のとおりである。）
    
    （式中、
    
    は、ｎ−２番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、
    
    はｎ−２番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻である。）
26. 前記第６’段階は、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２１２］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を推定する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    は、
    
    が得られたサイクルである。）
27. 前記第７’段階で、前記ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
    
    は、下記［数式２１３］のように計算される、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
28. 前記第８’段階で、前記ｋ番目のノードの待機時間
    
    は、下記［数式２１４］のように計算される、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
29. 前記第９’段階で、直近の２サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
    
    は、下記［数式２１５］のように計算される、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
30. 前記第９’段階で、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
    
    は、下記［数式２１６］のように計算される、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
31. 前記第１３’段階で、前記往復時間遅延取得有効性値
    
    を更新するために、下記［数式２１７］のように、すべてのノードに対して前記往復時間遅延取得有効性値
    
    を更新し、
    ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式２１８］のようにし、
    ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式２１９］のようにし、
    前記直近に取得された往復時間遅延関連情報
    
    は下記［数式２２０］のように更新し、
    また、前記往復時間遅延取得有効性値
    
    が１である場合には、下記［数式２２１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を計算し、直近に取得された往復時間遅延関連情報
    
    を更新する、請求項２０に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
32. ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延
    
    を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻
    
    は、下記［数式２０８］のように計算され、
    このとき、
    
    の場合には、次のように［数式２０９］を解いて、下記［数式２１０］のようにｋ番目のノードの往復時間遅延を推定し、
    前記［数式２１０］における
    
    は前記［数式２１１］のとおりである、請求項２５に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
33. 伝送スケジュールを含んでいるビーコンパケットを放送する一つのシンクノードと、前記シンクノードのビーコンパケットを受信して伝送スケジュールに従ってデータパケットを前記シンクノードへ伝送する多数のノードとから構成されたネットワークトポロジーで時分割多重アクセスを行う、水中無線移動ネットワークのためのスケジューリング方法であって：
    前記シンクノードが初期化過程を行う第１”段階と、
    前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
    
    を０に設定する第２”段階と、
    前記シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
    
    を推定し、１番目のノードのデータパケット受信完了時点
    
    を計算する第３”段階と、
    前記シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第４”段階と、
    前記第４”段階で、前記変数ｋが最後番目（Ｋ番目）より小さければ、前記シンクノードが前記変数ｋをｋ＋１に設定する第５”段階と、
    前記シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を推定する第６”段階と、
    前記シンクノードが、前記第６”段階で推定されたｋ番目のノードの往復時間遅延
    
    を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
    
    を計算する第７”段階と、
    前記シンクノードが、前記第７”段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
    
    を用いて、ｋ番目のノードの待機時間
    
    を計算する第８”段階と、
    前記シンクノードが、前記第７”段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
    
    と前記第８”段階で計算されたｋ番目のノードの待機時間
    
    を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
    
    を計算した後、前記第４”段階へ移行する第９”段階とを含むことを特徴とする、水中無線移動ネットワークのためのスケジューリング方法。
34. 前記第４”段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードがビーコンパケットの放送有無を判断する第１０”段階をさらに含み、
    前記第１０”段階でビーコンパケットが放送されなければすべての手続きを終了する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
35. 前記第１０”段階でビーコンパケットが放送されれば、
    前記シンクノードが、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻
    
    にビーコンパケットを放送する第１１”段階と、
    Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値
    
    が超過する第１２”段階と、
    前記シンクノードが、ｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を計算し、往復時間遅延取得有効性値
    
    及び直近に取得された往復時間遅延関連情報
    
    を更新する第１３”段階と、
    前記シンクノードがｎを１だけ増加させた後、前記第２”段階へ移行する第１４”段階とを含む、請求項３４に記載の水中無線移動ネットワークのためのスケジューリング方法。
36. 前記第１”段階で、前記シンクノードは下記［数式３０１］のように初期化過程を行う、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    は
    
    よりも小さいか同じ自然数であり、
    
    であり、
    
    はｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
    
    はｎ番目のサイクルで、（ｎ−ｍ）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
    
    は直近に取得されたｋ番目のノードの往復時間遅延であり、
    
    は
    
    が得られたサイクルであり、
    
    はシンクノードと各ノード間の最初の往復時間遅延であり、
    
    は１番目のサイクル前の持続時間であり、
    
    は下記数式３０２のように推定されて定められる。）
    
    （式中、
    
    は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
37. 前記第３”段階は、直近のＭサイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
    
    （２以上の自然数という）回以上であれば、下記［数式３０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
    
    を推定し、１番目のノードのデータパケット受信完了時点
    
    を下記［数式３０５］のように計算する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    は、
    
    座標を通る最小次数の多項式であり、
    
    はｎ番目のサイクルで１番目のノードのデータパケット受信時刻
    
    に対する推定値であり、
    
    はｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻であり、
    
    はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、
    
    は下記数式３０４のように値を制限する。）
    
    （式中、
    
    は往復時間遅延の最大値である。）
    
    （式中、
    
    はｎ番目のサイクルで１番目のノードのデータパケット長を時間に換算した値であり、
    
    はガード時間である。）
38. 前記［数式３０３］は次のように反復的に解が求められる、請求項３７に記載の水中無線移動ネットワークのためのスケジューリング方法。
    １）
    
    の初期値を
    
    または
    
    のように定め、
    ２）前記初期値
    
    を用いて［数式３０３］から
    
    を
    
    のように計算し、
    ３）前記２）で計算された
    
    を用いて
    
    を
    
    のように計算し、
    ４）前記３）で計算された
    
    から
    
    を
    
    のように計算し、
    ５）前記４）で計算された
    
    を用いて
    
    を
    
    のように計算し、
    ６）前記５）で計算された
    
    から
    
    を
    
    のように計算する過程を、設定された回数だけ繰り返した後、最終的に計算される値を
    
    と
    
    に確定する（このとき、繰り返し回数を定めず、以前に計算された
    
    と現在計算された
    
    との差が一定値以下である場合に繰り返し過程を中断し、或いは、以前に計算された
    
    と現在計算された
    
    との差が一定値以下である場合に繰り返し過程を中断する。）
39. 前記第３”段階は、直近の
    
    サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
    
    回未満であれば、下記［数式３０６］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
    
    を推定し、１番目のノードのデータパケット受信完了時点
    
    を計算する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    は直近に取得された１番目のノードの往復時間遅延であり、
    
    はシンクノードとｋ番目のノード間の最大相対速度であり、
    
    はｎ−１番目のサイクルの持続時間であり、
    
    は１番目のノードの往復時間遅延が取得された直近のサイクルであり、
    
    は水中での音波伝達速度の最小値である。）
40. 前記第６”段階は、直近の
    
    サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
    
    回以上であれば、下記［数式３０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を推定する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    は
    
    座標を通る最小次数の多項式であり、
    
    は
    
    サイクルでｋ番目のノードの有効な往復時間遅延値であり、
    
    は（ｋ−１）番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値である。）
41. 前記第６”段階でｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延
    
    を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻
    
    は、下記［数式３０８］のように計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
42. 前記第６”段階は、
    
    の場合には、下記［数式３０９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を推定する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
43. 前記［数式３０９］は、次のように反復的に解が求められる、請求項４２に記載の水中無線移動ネットワークのためのスケジューリング方法。
    １’）
    
    の初期値を
    
    または
    
    のように定め、
    ２’）前記初期値
    
    を用いて［数式３０９］から
    
    を
    
    のように計算し、
    ３’）計算された
    
    を用いて
    
    を
    
    のように計算し、
    ４’）前記３’）で計算された
    
    から
    
    を
    
    のように計算し、
    ５’）前記４’）で計算された
    
    を用いて
    
    を
    
    のように計算し、
    ６’）前記５’）で計算された
    
    から
    
    を
    
    のように計算する過程を
    設定された回数だけ繰り返した後、最終的に計算される値を
    
    と
    
    に確定する（このとき、繰り返し回数を定めず、以前に計算された
    
    と現在計算された
    
    との差が一定値以下である場合に繰り返し過程を中断し、あるいは、以前に計算された
    
    と現在計算された
    
    との差が一定値以下である場合に繰り返し過程を中断する。）
44. 前記
    
    は下記［数式３１０］のように値を制限する、請求項４２に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
45. 前記第６”段階は、直近の
    
    サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
    
    回未満であれば、下記［数式３１１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を推定する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
46. 前記第７”段階で、前記ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
    
    は、下記［数式３０８］によって計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    ［数式３０８］
47. 前記第８’段階で、前記ｋ番目のノードの待機時間
    
    は、下記［数式３１２］によって計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
48. 前記第９”段階で、直近の
    
    サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
    
    回以上であれば、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
    
    は、下記［数式３１３］のように計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
    （式中、
    
    はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
49. 前記第９”段階で、直近の
    
    サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
    
    回未満であれば、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
    
    は、下記［数式３１４］のように計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
    
50. 前記第１３”段階で、前記往復時間遅延取得有効性値
    
    を更新するために、下記［数式３１５］のようにすべてのノードに対して前記往復時間遅延取得有効性値
    
    を更新し、
    ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式３１６］のようにし、
    ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式３１７］のようにし、
    前記直近に取得された往復時間遅延関連情報
    
    は、下記［数式３１８］のように更新し、
    また、前記往復時間遅延取得有効性値
    
    が１である場合には、下記［数式３１９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
    
    を計算し、直近に取得された往復時間遅延関連情報
    
    を更新する、請求項３５に記載の水中無線移動ネットワークのためのスケジューリング方法。