(57)【要約】  本発明は、水中無線移動ネットワークのためのスケジューリング方法に係り、特に、時間領域で衝突が発生しないスケジューリング方法を考慮するが、特定の瞬間に転送時間が重ならないように直交化するよりは、音波の伝達速度及びパケット長を考慮してシンクノードにパケットがパケットトレインの形態で連続的に受信されるようにすることにより、ネットワークの効率を向上させることができる、水中無線移動ネットワークのためのスケジューリング方法に関する。
2019508000.tif 000002
【特許請求の範囲】
【請求項１】
一つのシンクノードと多数のノードとから構成されたネットワークトポロジーでスケジューリングを行う、水中無線移動ネットワークのためのスケジューリング方法であって：
シンクノードから多数のノードへ初期化パケットを放送する第１段階と、
前記シンクノードが多数のノードから第１設定時間
【数１】
2019508000.tif 000922
の間に初期化応答パケットを受信する第２段階と、
前記シンクノードが、前記第２段階で受信した初期化応答パケットから前記シンクノードと多数のノード間の往復時間遅延
【数２】
2019508000.tif 000923
を計算する第３段階と、
前記シンクノードによって、初期化応答パケットの受信に衝突が存在するか否かを決定する第４段階と、
前記第４段階で初期化応答パケットの受信に衝突が存在しなければ、前記シンクノードが、前記第３段階で計算された往復時間遅延
【数３】
2019508000.tif 000924
を用いて往復時間遅延の小さい順にノードを整列する第５段階と、
前記シンクノードによって変数ｋが１に設定され、１番目のノードの待機時間
【数４】
2019508000.tif 000925
が「０」に設定される第６段階と、
前記シンクノードによって、１番目のノードのデータパケットが前記シンクノードに受信され始める時刻の最大値
【数５】
2019508000.tif 000926
が計算される第７段階と、
前記変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第８段階と、
前記第８段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記変数ｋをｋ＋１に設定する第９段階と、
前記シンクノードによって、ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値
【数６】
2019508000.tif 000927
が計算される第１０段階と、
前記シンクノードによって前記ｋ番目のノードの待機時間
【数７】
2019508000.tif 000928
が計算される第１１段階と、
前記シンクノードによって前記ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最大値
【数８】
2019508000.tif 000929
を計算した後、前記第８段階へ移行する第１２段階と、
前記第８段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードによって１番目のビーコンパケットが第３設定時刻
【数９】
2019508000.tif 000930
に多数のノードへ放送される第１３段階と、
前記シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記第１３段階による１番目のビーコンパケットの放送後に第４設定時間
【数１０】
2019508000.tif 000931
を待機する第１４段階と、
前記シンクノードによって前記シンクノードと前記ｋ番目のノード間の往復時間遅延
【数１１】
2019508000.tif 000932
が計算される第１５段階と、
前記シンクノードが、前記第１５段階で計算された往復時間遅延
【数１２】
2019508000.tif 000933
を用いて往復時間遅延の小さい順にノードを整列する第１６段階と、
前記シンクノードによって、１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
【数１３】
2019508000.tif 000934
が計算される第１７段階と、
前記変数ｋを１に設定し、前記シンクノードが、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数１４】
2019508000.tif 000935
を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値
【数１５】
2019508000.tif 000936
を計算する第１８段階と、
前記変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第１９段階と、
前記第１９段階で前記変数ｋ最後番目（Ｋ番目）より小さければ、前記変数ｋをｋ＋１に設定する第２０段階と、
前記シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値
【数１６】
2019508000.tif 000937
を計算する第２１段階と、
前記シンクノードが、ｎ番目のサイクルでｋ番目のノードに付与される時間遅延
【数１７】
2019508000.tif 000938
を計算する第２２段階と、
前記シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値
【数１８】
2019508000.tif 000939
を計算した後、前記第１９段階へ移行する第２３段階と、
前記第１９段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードによって、ビーコンパケット放送が行われるか否かが決定される第２４段階と、
前記第２４段階でビーコンパケット放送が行われなければ終了する第２５段階とを含むことを特徴とする、水中無線移動ネットワークのためのスケジューリング方法。
【請求項２】
前記第２４段階でシンクノードによってビーコンパケット放送が決定されれば、
前記シンクノードによってｎ番目のサイクルのビーコンパケットが放送される時刻
【数１９】
2019508000.tif 000940
にビーコンパケットがノードに放送される第２６段階と、
前記シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記ｎ番目のサイクルで最後番目のノードのデータパケットが受信され始める時刻の最大値
【数２０】
2019508000.tif 000941
を待機する第２７段階と、
前記シンクノードによってサイクルが１だけ増加した後、前記第１５段階へ移行する第２８段階とが行われる、請求項１に記載の水中無線移動ネットワークのためのスケジューリング方法。
【請求項３】
前記第４段階で初期化応答パケットの受信に衝突が存在すれば、
前記シンクノードによって再初期化パケットがノードに放送される第２９段階と、
前記シンクノードによって第２設定時間
【数２１】
2019508000.tif 000942
だけ再初期化応答パケットが受信される第３０段階と、
前記シンクノードが、前記第３０段階で受信した再初期化応答パケットから前記シンクノードとノード間の往復時間遅延
【数２２】
2019508000.tif 000943
を計算する第３１段階と、
前記シンクノードによって、再初期化応答パケットの受信に衝突が存在するか否かを決定する第３２段階とが行われ、
前記第３２段階で再初期化応答パケットの受信に衝突が存在すれば前記第２９段階へ移行する、請求項１に記載の水中無線移動ネットワークのためのスケジューリング方法。
【請求項４】
前記第３２段階で再初期化応答パケットの受信に衝突が存在しなければ、前記第５段階へ移行する、請求項３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【請求項５】
前記第１設定時間
【数２３】
2019508000.tif 000944
は下記数式１０１によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２４】
2019508000.tif 000945
［式中、
【数２５】
2019508000.tif 000946
は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、
【数２６】
2019508000.tif 000947
は初期化パケット長の時間換算値であり、
【数２７】
2019508000.tif 000948
は初期化応答パケット長の時間換算値であり、
【数２８】
2019508000.tif 000949
はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。
【数２９】
2019508000.tif 000950
（ｒはモデムの最大通信半径であり、ｃは音波速度である。）］
【請求項６】
前記シンクノードと多数のノード間の往復時間遅延
【数３０】
2019508000.tif 000951
は下記数式１０３によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数３１】
2019508000.tif 000952
（式中、
【数３２】
2019508000.tif 000953
はノードＨから受信された初期化応答パケットの受信時刻であり、
【数３３】
2019508000.tif 000954
は初期化パケット放送時間である。）
【請求項７】
前記１番目のノードのデータパケットが前記シンクノードに受信され始める時刻の最大値
【数３４】
2019508000.tif 000955
は、下記数式１０８によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数３５】
2019508000.tif 000956
（式中、
【数３６】
2019508000.tif 000957
はシンクノードによる最初のビーコンパケット放送時刻であり、
【数３７】
2019508000.tif 000958
はビーコンパケット長の時間換算値であり、
【数３８】
2019508000.tif 000959
は１番目のノードの往復時間遅延であり、
【数３９】
2019508000.tif 000960
は１番目のノードのシンクノードとの往復時間遅延が取得された時点であり、
【数４０】
2019508000.tif 000961
はシンクノードとノード間の最大相対速度である。）
【請求項８】
前記ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値
【数４１】
2019508000.tif 000962
は、下記数式１１３によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数４２】
2019508000.tif 000963
（式中、
【数４３】
2019508000.tif 000964
はｋ番目のノードの往復時間遅延であり、
【数４４】
2019508000.tif 000965
は
【数４５】
2019508000.tif 000966
が取得された時刻である。）
【請求項９】
前記ｋ番目のノードの待機時間
【数４６】
2019508000.tif 000967
は下記数式１１４によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数４７】
2019508000.tif 000968
［式中、
【数４８】
2019508000.tif 000969
はＡ及びＢの両者から大きい値を選択する関数であり、
【数４９】
2019508000.tif 000970
はｋ−１番目のノードのデータパケットがシンクノードに到着する時刻の最大値であって、下記数式１１２によって決定され、
【数５０】
2019508000.tif 000971
はｋ−１番目のノードのデータパケット長の時間換算値である。
【数５１】
2019508000.tif 000972
（式中、
【数５２】
2019508000.tif 000973
はｋ−１番目のノードの往復時間遅延であり、
【数５３】
2019508000.tif 000974
はｋ−１番目のノードの待機時間であり、
【数５４】
2019508000.tif 000975
は
【数５５】
2019508000.tif 000976
が取得された時間である。）］
【請求項１０】
前記シンクノードと前記ｋ番目のノード間の往復時間遅延
【数５６】
2019508000.tif 000977
は下記数式１１５によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数５７】
2019508000.tif 000978
（式中、
【数５８】
2019508000.tif 000979
はｎ番目のサイクルのビーコンパケットが放送される時刻であり、
【数５９】
2019508000.tif 000980
はｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻であり、
【数６０】
2019508000.tif 000981
はｎ番目のサイクルでｋ番目のノードに付与される時間遅延であり、
【数６１】
2019508000.tif 000982
はｎ番目のサイクルにおけるビーコン長の時間換算値である。）
【請求項１１】
前記１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
【数６２】
2019508000.tif 000983
は下記数式１１６によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数６３】
2019508000.tif 000984
（式中、
【数６４】
2019508000.tif 000985
は（ｎ−１）番目のサイクルにおけるデータパケットの受信開始時刻である。）
【請求項１２】
各ノードの（ｎ−１）番目のサイクルにおけるデータパケットの受信時刻
【数６５】
2019508000.tif 000986
とｎ番目のサイクルにおけるデータパケットの受信時刻
【数６６】
2019508000.tif 000987
との差は下記数式１１７のように近似した、請求項１１に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数６７】
2019508000.tif 000988
【請求項１３】
前記第２設定時間
【数６８】
2019508000.tif 000989
は下記数式１０５によって決定される、請求項３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数６９】
2019508000.tif 000990
（式中、
【数７０】
2019508000.tif 000991
は再初期化パケット長の時間換算値であり、
【数７１】
2019508000.tif 000992
は再初期化応答パケット長の時間換算値である。）
【請求項１４】
前記ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値
【数７２】
2019508000.tif 000993
は、下記数式１１８によって決定される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数７３】
2019508000.tif 000994
（式中、
【数７４】
2019508000.tif 000995
はｎ−１番目のサイクルにおける１番目のノードの往復時間遅延であり、
【数７５】
2019508000.tif 000996
はｎ番目のサイクルにおける１番目のノードのデータパケット長の時間換算値である。）
【請求項１５】
前記シンクノードにｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値
【数７６】
2019508000.tif 000997
は、下記数式１１９によって計算される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数７７】
2019508000.tif 000998
（式中、
【数７８】
2019508000.tif 000999
はｎ−１番目のサイクルにおけるｋ番目のノードの往復時間遅延である。）
【請求項１６】
前記シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延
【数７９】
2019508000.tif 001000
は、下記数式１２０によって計算される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数８０】
2019508000.tif 001001
(式中、
【数８１】
2019508000.tif 001002
はｎ番目のサイクルでｋ−１番目のノードのデータパケットが受信され始める時刻の最大値である。)
【請求項１７】
前記シンクノードにｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値
【数８２】
2019508000.tif 001003
は、下記数式１２１によって計算される、請求項１乃至４のいずれか一項に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数８３】
2019508000.tif 001004
（式中、
【数８４】
2019508000.tif 001005
はｎ番目のサイクルにおけるｋ番目のノードのデータパケット長の時間換算値である。）
【請求項１８】
伝送スケジュールを含んでいるビーコンパケットを放送する一つのシンクノードと、前記シンクノードのビーコンパケットを受信して伝送スケジュールに従ってデータパケットを前記シンクノードへ伝送する多数のノードとから構成されたネットワークトポロジーで時分割多重アクセスを行う、水中無線移動ネットワークのためのスケジューリング方法であって：
前記シンクノードが初期化過程を行う第１’段階と、
前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数８５】
2019508000.tif 001006
を０に設定する第２’段階と、
前記シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数８６】
2019508000.tif 001007
を推定し、１番目のノードのデータパケット受信完了時点
【数８７】
2019508000.tif 001008
を計算する第３’段階と、
前記シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第４’段階と、
前記第４’段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記シンクノードが前記変数ｋをｋ＋１に設定する第５’段階と、
前記シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数８８】
2019508000.tif 001009
を推定する第６’段階と、
前記シンクノードが、前記第６’段階で推定されたｋ番目のノードの往復時間遅延
【数８９】
2019508000.tif 001010
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９０】
2019508000.tif 001011
を計算する第７’段階と、
前記シンクノードが、前記第７’段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９１】
2019508000.tif 001012
を用いて、ｋ番目のノードの待機時間
【数９２】
2019508000.tif 001013
を計算する第８’段階と、
前記シンクノードが、前記第７’段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９３】
2019508000.tif 001014
と前記第８’段階で計算されたｋ番目のノードの待機時間
【数９４】
2019508000.tif 001015
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数９５】
2019508000.tif 001016
を計算した後、前記第４’段階へ移行する第９’段階とを含む、水中無線移動ネットワークのためのスケジューリング方法。
【請求項１９】
前記第４’段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードがビーコンパケットの放送有無を判断する第１０’段階をさらに含み、
前記第１０’段階でビーコンパケットが放送されなければすべての手続きを終了する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【請求項２０】
前記第１０’段階でビーコンパケットが放送されれば、
前記シンクノードが、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻
【数９６】
2019508000.tif 001017
にビーコンパケットを放送する第１１’段階と、
Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値
【数９７】
2019508000.tif 001018
が超過する第１２’段階と、
前記シンクノードが、ｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数９８】
2019508000.tif 001019
を計算し、往復時間遅延取得有効性値
【数９９】
2019508000.tif 001020
及び直近に取得された往復時間遅延関連情報
【数１００】
2019508000.tif 001021
を更新する第１３’段階と、
前記シンクノードがｎを１だけ増加させた後、前記第２’段階へ移行する第１４’段階とを含む、請求項１９に記載の水中無線移動ネットワークのためのスケジューリング方法。
【請求項２１】
前記第１’段階で、前記シンクノードは下記［数式２０１］のように初期化過程を行う、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１０１】
2019508000.tif 001022
（式中、
【数１０２】
2019508000.tif 001023
はｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数１０３】
2019508000.tif 001024
はｎ番目のサイクルで、（ｎ−２）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数１０４】
2019508000.tif 001025
は直近に取得されたｋ番目のノードの往復時間遅延であり、
【数１０５】
2019508000.tif 001026
は
【数１０６】
2019508000.tif 001027
が得られたサイクルであり、
【数１０７】
2019508000.tif 001028
はシンクノードと各ノード間の最初の往復時間遅延であり、
【数１０８】
2019508000.tif 001029
は１番目のサイクル前の持続時間であり、
【数１０９】
2019508000.tif 001030
は下記数式２０２のように推定されて定められる。）
【数１１０】
2019508000.tif 001031
（
【数１１１】
2019508000.tif 001032
は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【請求項２２】
前記第３’段階は、直近の２サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合には、下記［数式２０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数１１２】
2019508000.tif 001033
を推定し、１番目のノードのデータパケット受信完了時点
【数１１３】
2019508000.tif 001034
を計算する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１１４】
2019508000.tif 001035
（式中、
【数１１５】
2019508000.tif 001036
はガード時間であり、
【数１１６】
2019508000.tif 001037
はｎ−１番目のサイクルで取得された１番目のノードの往復時間遅延であり、
【数１１７】
2019508000.tif 001038
はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、
【数１１８】
2019508000.tif 001039
はｎ−１番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻であり、
【数１１９】
2019508000.tif 001040
は下記数式２０４のとおりである。）
【数１２０】
2019508000.tif 001041
（式中、
【数１２１】
2019508000.tif 001042
はｎ−２番目のサイクルで取得された１番目のノードの往復時間遅延であり、
【数１２２】
2019508000.tif 001043
はｎ−２番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻である。）
【請求項２３】
前記［数式２０３］は、下記の連立方程式である［数式２０６］を解いて得られる、請求項２２に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１２３】
2019508000.tif 001044
（式中、
【数１２４】
2019508000.tif 001045
はｎ番目のサイクルで１番目のノードのデータパケット受信時刻
【数１２５】
2019508000.tif 001046
に対する推定値である。）
【請求項２４】
前記第３’段階は、直近の２サイクルの間に１番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２０５］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数１２６】
2019508000.tif 001047
を推定し、１番目のノードのデータパケット受信完了時点
【数１２７】
2019508000.tif 001048
を計算する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１２８】
2019508000.tif 001049
（式中、
【数１２９】
2019508000.tif 001050
は往復時間遅延の最大値であり、
【数１３０】
2019508000.tif 001051
は直近に取得された１番目のノードの往復時間遅延であり、
【数１３１】
2019508000.tif 001052
はシンクノードとｋ番目のノード間の最大相対速度であり、
【数１３２】
2019508000.tif 001053
はｎ−１番目のサイクルの持続時間であり、
【数１３３】
2019508000.tif 001054
は１番目のノードの往復時間遅延が取得された直近のサイクルであり、
【数１３４】
2019508000.tif 001055
は水中での最小音波伝達速度である。）
【請求項２５】
前記第６’段階は、直近の２サイクルの間にｋ番目のノードの往復時間遅延
【数１３５】
2019508000.tif 001056
が成功的に取得された場合には、下記［数式２０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１３６】
2019508000.tif 001057
を推定する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１３７】
2019508000.tif 001058
（式中、
【数１３８】
2019508000.tif 001059
はｎ−１番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、
【数１３９】
2019508000.tif 001060
はｋ−１番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値であり、
【数１４０】
2019508000.tif 001061
はｎ−１番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻であり、
【数１４１】
2019508000.tif 001062
は下記数式２１１のとおりである。）
【数１４２】
2019508000.tif 001063
（式中、
【数１４３】
2019508000.tif 001064
は、ｎ−２番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、
【数１４４】
2019508000.tif 001065
はｎ−２番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻である。）
【請求項２６】
前記第６’段階は、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２１２］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１４５】
2019508000.tif 001066
を推定する、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１４６】
2019508000.tif 001067
（式中、
【数１４７】
2019508000.tif 001068
は、
【数１４８】
2019508000.tif 001069
が得られたサイクルである。）
【請求項２７】
前記第７’段階で、前記ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数１４９】
2019508000.tif 001070
は、下記［数式２１３］のように計算される、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１５０】
2019508000.tif 001071
【請求項２８】
前記第８’段階で、前記ｋ番目のノードの待機時間
【数１５１】
2019508000.tif 001072
は、下記［数式２１４］のように計算される、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１５２】
2019508000.tif 001073
【請求項２９】
前記第９’段階で、直近の２サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数１５３】
2019508000.tif 001074
は、下記［数式２１５］のように計算される、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１５４】
2019508000.tif 001075
（式中、
【数１５５】
2019508000.tif 001076
はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【請求項３０】
前記第９’段階で、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数１５６】
2019508000.tif 001077
は、下記［数式２１６］のように計算される、請求項１８に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１５７】
2019508000.tif 001078
【請求項３１】
前記第１３’段階で、前記往復時間遅延取得有効性値
【数１５８】
2019508000.tif 001079
を更新するために、下記［数式２１７］のように、すべてのノードに対して前記往復時間遅延取得有効性値
【数１５９】
2019508000.tif 001080
を更新し、
ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式２１８］のようにし、
ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式２１９］のようにし、
前記直近に取得された往復時間遅延関連情報
【数１６０】
2019508000.tif 001081
は下記［数式２２０］のように更新し、
また、前記往復時間遅延取得有効性値
【数１６１】
2019508000.tif 001082
が１である場合には、下記［数式２２１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１６２】
2019508000.tif 001083
を計算し、直近に取得された往復時間遅延関連情報
【数１６３】
2019508000.tif 001084
を更新する、請求項２０に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１６４】
2019508000.tif 001085
【請求項３２】
ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延
【数１６５】
2019508000.tif 001086
を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻
【数１６６】
2019508000.tif 001087
は、下記［数式２０８］のように計算され、
このとき、
【数１６７】
2019508000.tif 001088
の場合には、次のように［数式２０９］を解いて、下記［数式２１０］のようにｋ番目のノードの往復時間遅延を推定し、
前記［数式２１０］における
【数１６８】
2019508000.tif 001089
は前記［数式２１１］のとおりである、請求項２５に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１６９】
2019508000.tif 001090
【請求項３３】
伝送スケジュールを含んでいるビーコンパケットを放送する一つのシンクノードと、前記シンクノードのビーコンパケットを受信して伝送スケジュールに従ってデータパケットを前記シンクノードへ伝送する多数のノードとから構成されたネットワークトポロジーで時分割多重アクセスを行う、水中無線移動ネットワークのためのスケジューリング方法であって：
前記シンクノードが初期化過程を行う第１”段階と、
前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数１７０】
2019508000.tif 001091
を０に設定する第２”段階と、
前記シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数１７１】
2019508000.tif 001092
を推定し、１番目のノードのデータパケット受信完了時点
【数１７２】
2019508000.tif 001093
を計算する第３”段階と、
前記シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第４”段階と、
前記第４”段階で、前記変数ｋが最後番目（Ｋ番目）より小さければ、前記シンクノードが前記変数ｋをｋ＋１に設定する第５”段階と、
前記シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１７３】
2019508000.tif 001094
を推定する第６”段階と、
前記シンクノードが、前記第６”段階で推定されたｋ番目のノードの往復時間遅延
【数１７４】
2019508000.tif 001095
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数１７５】
2019508000.tif 001096
を計算する第７”段階と、
前記シンクノードが、前記第７”段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数１７６】
2019508000.tif 001097
を用いて、ｋ番目のノードの待機時間
【数１７７】
2019508000.tif 001098
を計算する第８”段階と、
前記シンクノードが、前記第７”段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数１７８】
2019508000.tif 001099
と前記第８”段階で計算されたｋ番目のノードの待機時間
【数１７９】
2019508000.tif 001100
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数１８０】
2019508000.tif 001101
を計算した後、前記第４”段階へ移行する第９”段階とを含むことを特徴とする、水中無線移動ネットワークのためのスケジューリング方法。
【請求項３４】
前記第４”段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードがビーコンパケットの放送有無を判断する第１０”段階をさらに含み、
前記第１０”段階でビーコンパケットが放送されなければすべての手続きを終了する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【請求項３５】
前記第１０”段階でビーコンパケットが放送されれば、
前記シンクノードが、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻
【数１８１】
2019508000.tif 001102
にビーコンパケットを放送する第１１”段階と、
Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値
【数１８２】
2019508000.tif 001103
が超過する第１２”段階と、
前記シンクノードが、ｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１８３】
2019508000.tif 001104
を計算し、往復時間遅延取得有効性値
【数１８４】
2019508000.tif 001105
及び直近に取得された往復時間遅延関連情報
【数１８５】
2019508000.tif 001106
を更新する第１３”段階と、
前記シンクノードがｎを１だけ増加させた後、前記第２”段階へ移行する第１４”段階とを含む、請求項３４に記載の水中無線移動ネットワークのためのスケジューリング方法。
【請求項３６】
前記第１”段階で、前記シンクノードは下記［数式３０１］のように初期化過程を行う、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数１８６】
2019508000.tif 001107
（式中、
【数１８７】
2019508000.tif 001108
は
【数１８８】
2019508000.tif 001109
よりも小さいか同じ自然数であり、
【数１８９】
2019508000.tif 001110
であり、
【数１９０】
2019508000.tif 001111
はｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数１９１】
2019508000.tif 001112
はｎ番目のサイクルで、（ｎ−ｍ）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数１９２】
2019508000.tif 001113
は直近に取得されたｋ番目のノードの往復時間遅延であり、
【数１９３】
2019508000.tif 001114
は
【数１９４】
2019508000.tif 001115
が得られたサイクルであり、
【数１９５】
2019508000.tif 001116
はシンクノードと各ノード間の最初の往復時間遅延であり、
【数１９６】
2019508000.tif 001117
は１番目のサイクル前の持続時間であり、
【数１９７】
2019508000.tif 001118
は下記数式３０２のように推定されて定められる。）
【数１９８】
2019508000.tif 001119
（式中、
【数１９９】
2019508000.tif 001120
は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【請求項３７】
前記第３”段階は、直近のＭサイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数２００】
2019508000.tif 001121
（２以上の自然数という）回以上であれば、下記［数式３０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数２０１】
2019508000.tif 001122
を推定し、１番目のノードのデータパケット受信完了時点
【数２０２】
2019508000.tif 001123
を下記［数式３０５］のように計算する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２０３】
2019508000.tif 001124
（式中、
【数２０４】
2019508000.tif 001125
は、
【数２０５】
2019508000.tif 001126
座標を通る最小次数の多項式であり、
【数２０６】
2019508000.tif 001127
はｎ番目のサイクルで１番目のノードのデータパケット受信時刻
【数２０７】
2019508000.tif 001128
に対する推定値であり、
【数２０８】
2019508000.tif 001129
はｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻であり、
【数２０９】
2019508000.tif 001130
はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、
【数２１０】
2019508000.tif 001131
は下記数式３０４のように値を制限する。）
【数２１１】
2019508000.tif 001132
（式中、
【数２１２】
2019508000.tif 001133
は往復時間遅延の最大値である。）
【数２１３】
2019508000.tif 001134
（式中、
【数２１４】
2019508000.tif 001135
はｎ番目のサイクルで１番目のノードのデータパケット長を時間に換算した値であり、
【数２１５】
2019508000.tif 001136
はガード時間である。）
【請求項３８】
前記［数式３０３］は次のように反復的に解が求められる、請求項３７に記載の水中無線移動ネットワークのためのスケジューリング方法。
１）
【数２１６】
2019508000.tif 001137
の初期値を
【数２１７】
2019508000.tif 001138
または
【数２１８】
2019508000.tif 001139
のように定め、
２）前記初期値
【数２１９】
2019508000.tif 001140
を用いて［数式３０３］から
【数２２０】
2019508000.tif 001141
を
【数２２１】
2019508000.tif 001142
のように計算し、
３）前記２）で計算された
【数２２２】
2019508000.tif 001143
を用いて
【数２２３】
2019508000.tif 001144
を
【数２２４】
2019508000.tif 001145
のように計算し、
４）前記３）で計算された
【数２２５】
2019508000.tif 001146
から
【数２２６】
2019508000.tif 001147
を
【数２２７】
2019508000.tif 001148
のように計算し、
５）前記４）で計算された
【数２２８】
2019508000.tif 001149
を用いて
【数２２９】
2019508000.tif 001150
を
【数２３０】
2019508000.tif 001151
のように計算し、
６）前記５）で計算された
【数２３１】
2019508000.tif 001152
から
【数２３２】
2019508000.tif 001153
を
【数２３３】
2019508000.tif 001154
のように計算する過程を、設定された回数だけ繰り返した後、最終的に計算される値を
【数２３４】
2019508000.tif 001155
と
【数２３５】
2019508000.tif 001156
に確定する（このとき、繰り返し回数を定めず、以前に計算された
【数２３６】
2019508000.tif 001157
と現在計算された
【数２３７】
2019508000.tif 001158
との差が一定値以下である場合に繰り返し過程を中断し、或いは、以前に計算された
【数２３８】
2019508000.tif 001159
と現在計算された
【数２３９】
2019508000.tif 001160
との差が一定値以下である場合に繰り返し過程を中断する。）
【請求項３９】
前記第３”段階は、直近の
【数２４０】
2019508000.tif 001161
サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数２４１】
2019508000.tif 001162
回未満であれば、下記［数式３０６］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数２４２】
2019508000.tif 001163
を推定し、１番目のノードのデータパケット受信完了時点
【数２４３】
2019508000.tif 001164
を計算する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２４４】
2019508000.tif 001165
（式中、
【数２４５】
2019508000.tif 001166
は直近に取得された１番目のノードの往復時間遅延であり、
【数２４６】
2019508000.tif 001167
はシンクノードとｋ番目のノード間の最大相対速度であり、
【数２４７】
2019508000.tif 001168
はｎ−１番目のサイクルの持続時間であり、
【数２４８】
2019508000.tif 001169
は１番目のノードの往復時間遅延が取得された直近のサイクルであり、
【数２４９】
2019508000.tif 001170
は水中での音波伝達速度の最小値である。）
【請求項４０】
前記第６”段階は、直近の
【数２５０】
2019508000.tif 001171
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数２５１】
2019508000.tif 001172
回以上であれば、下記［数式３０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数２５２】
2019508000.tif 001173
を推定する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２５３】
2019508000.tif 001174
（式中、
【数２５４】
2019508000.tif 001175
は
【数２５５】
2019508000.tif 001176
座標を通る最小次数の多項式であり、
【数２５６】
2019508000.tif 001177
は
【数２５７】
2019508000.tif 001178
サイクルでｋ番目のノードの有効な往復時間遅延値であり、
【数２５８】
2019508000.tif 001179
は（ｋ−１）番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値である。）
【請求項４１】
前記第６”段階でｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延
【数２５９】
2019508000.tif 001180
を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻
【数２６０】
2019508000.tif 001181
は、下記［数式３０８］のように計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２６１】
2019508000.tif 001182
【請求項４２】
前記第６”段階は、
【数２６２】
2019508000.tif 001183
の場合には、下記［数式３０９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数２６３】
2019508000.tif 001184
を推定する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２６４】
2019508000.tif 001185
【請求項４３】
前記［数式３０９］は、次のように反復的に解が求められる、請求項４２に記載の水中無線移動ネットワークのためのスケジューリング方法。
１’）
【数２６５】
2019508000.tif 001186
の初期値を
【数２６６】
2019508000.tif 001187
または
【数２６７】
2019508000.tif 001188
のように定め、
２’）前記初期値
【数２６８】
2019508000.tif 001189
を用いて［数式３０９］から
【数２６９】
2019508000.tif 001190
を
【数２７０】
2019508000.tif 001191
のように計算し、
３’）計算された
【数２７１】
2019508000.tif 001192
を用いて
【数２７２】
2019508000.tif 001193
を
【数２７３】
2019508000.tif 001194
のように計算し、
４’）前記３’）で計算された
【数２７４】
2019508000.tif 001195
から
【数２７５】
2019508000.tif 001196
を
【数２７６】
2019508000.tif 001197
のように計算し、
５’）前記４’）で計算された
【数２７７】
2019508000.tif 001198
を用いて
【数２７８】
2019508000.tif 001199
を
【数２７９】
2019508000.tif 001200
のように計算し、
６’）前記５’）で計算された
【数２８０】
2019508000.tif 001201
から
【数２８１】
2019508000.tif 001202
を
【数２８２】
2019508000.tif 001203
のように計算する過程を
設定された回数だけ繰り返した後、最終的に計算される値を
【数２８３】
2019508000.tif 001204
と
【数２８４】
2019508000.tif 001205
に確定する（このとき、繰り返し回数を定めず、以前に計算された
【数２８５】
2019508000.tif 001206
と現在計算された
【数２８６】
2019508000.tif 001207
との差が一定値以下である場合に繰り返し過程を中断し、あるいは、以前に計算された
【数２８７】
2019508000.tif 001208
と現在計算された
【数２８８】
2019508000.tif 001209
との差が一定値以下である場合に繰り返し過程を中断する。）
【請求項４４】
前記
【数２８９】
2019508000.tif 001210
は下記［数式３１０］のように値を制限する、請求項４２に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２９０】
2019508000.tif 001211
【請求項４５】
前記第６”段階は、直近の
【数２９１】
2019508000.tif 001212
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数２９２】
2019508000.tif 001213
回未満であれば、下記［数式３１１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数２９３】
2019508000.tif 001214
を推定する、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２９４】
2019508000.tif 001215
【請求項４６】
前記第７”段階で、前記ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数２９５】
2019508000.tif 001216
は、下記［数式３０８］によって計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２９６】
2019508000.tif 001217
［数式３０８］
【請求項４７】
前記第８’段階で、前記ｋ番目のノードの待機時間
【数２９７】
2019508000.tif 001218
は、下記［数式３１２］によって計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数２９８】
2019508000.tif 001219
【請求項４８】
前記第９”段階で、直近の
【数２９９】
2019508000.tif 001220
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数３００】
2019508000.tif 001221
回以上であれば、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数３０１】
2019508000.tif 001222
は、下記［数式３１３］のように計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数３０２】
2019508000.tif 001223
（式中、
【数３０３】
2019508000.tif 001224
はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【請求項４９】
前記第９”段階で、直近の
【数３０４】
2019508000.tif 001225
サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数３０５】
2019508000.tif 001226
回未満であれば、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数３０６】
2019508000.tif 001227
は、下記［数式３１４］のように計算される、請求項３３に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数３０７】
2019508000.tif 001228
【請求項５０】
前記第１３”段階で、前記往復時間遅延取得有効性値
【数３０８】
2019508000.tif 001229
を更新するために、下記［数式３１５］のようにすべてのノードに対して前記往復時間遅延取得有効性値
【数３０９】
2019508000.tif 001230
を更新し、
ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式３１６］のようにし、
ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式３１７］のようにし、
前記直近に取得された往復時間遅延関連情報
【数３１０】
2019508000.tif 001231
は、下記［数式３１８］のように更新し、
また、前記往復時間遅延取得有効性値
【数３１１】
2019508000.tif 001232
が１である場合には、下記［数式３１９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数３１２】
2019508000.tif 001233
を計算し、直近に取得された往復時間遅延関連情報
【数３１３】
2019508000.tif 001234
を更新する、請求項３５に記載の水中無線移動ネットワークのためのスケジューリング方法。
【数３１４】
2019508000.tif 001235
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
〔技術分野〕
本発明は、水中無線移動ネットワークのためのスケジューリング方法に係り、特に、時間領域で衝突が発生しないスケジューリング方法を考慮するが、特定の瞬間に転送時間が重ならないように直交化するよりは、音波の伝達速度及びパケット長を考慮してシンクノードにパケットがパケットトレインの形態で連続的に受信されるようにすることにより、ネットワークの効率を向上させることができる、水中無線移動ネットワークのためのスケジューリング方法に関する。
【０００２】
また、本発明は、水中音響無線移動ネットワークなどのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、多数のノードがシンクノードへデータパケットを時分割多重アクセス方式で伝送しようとするときに、ノードの移動性による往復時間遅延をサイクル単位で追跡してシンクノードがノードからデータパケットを受信する上で遊休時間を最小化することにより、チャンネル使用効率の向上によるネットワーク効率が大幅に向上することができる、水中無線移動ネットワークのためのスケジューリング方法に関する。
【０００３】
また、本発明は、水中音響無線移動ネットワークなどのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、多数のノードがシンクノードへデータパケットを時分割多重アクセス方式で伝送しようとするときに、ノードの移動性による往復時間遅延をサイクル単位で追跡してシンクノードがノードからデータパケットを受信する上で遊休時間を最小化することにより、チャンネル使用効率の向上によるネットワーク効率が大幅に向上することができる、水中無線移動ネットワークのためのスケジューリング方法に関する。
【０００４】
〔背景技術〕
通常、水中無線ネットワークは音波を用いる。このように音波を用いる水中無線ネットワークでは、電磁波に比べて相対的に伝達速度が非常に遅い音波の伝達速度に起因する非常に長い伝播遅延、及び水中音響モデムの狭い帯域幅に起因する物理階層の遅いデータ伝達速度によって長くなるパケット長により発生するネットワーク効率性の低下を克服することが最も重要である。
【０００５】
水中無線ネットワークトポロジーは、一つまたは多数のシンクノードへ多数のノードが情報を伝達することをメイントラフィックとする中央集中方式と、分散型のマルチホップ方式があるが、ネットワーク効率の面で中央集中方式が有利である。現在商用で運用されているすべてのネットワーク方式も中央集中方式である。中央集中方式は、空間／時間／周波数／符号などのリソースを直交化して使用するのが一般的である。
【０００６】
伝搬時間遅延が「０」に近い空気中での電磁波を利用する通信ネットワークシステムでは、同じ衝突領域にある２つのノードが同時にパケット送信を行うと、互いに衝突を起こすが、水中では遅い音波の伝達速度により衝突を起こさないこともある。例えば、音波の伝達速度を１，５００ｍ／ｓと仮定し、互いに１．５ｋｍ離れている２つのノードが１秒長さのデータパケットを同時に伝送すると、送信−受信間のスイッチングに必要な時間を無視すれば、各ノードで送信が終わるや否や他のノードのパケット受信が始まる。具体的には、０秒に２つのノードが１秒長さのパケットを同時に伝送すると、１秒の時点で、２つのノードは送信が終了し、すぐに相手ノードのデータを受信し始めるので、自分のパケット送信が相手ノードのパケットを受信する上で問題を起こさなくなり、２秒の時点では、２つのノードの両方ともパケット受信が完了する。もし順次データを伝送するならば合計４秒の時間がかかるので、この場合には、ネットワークの効率が２倍に向上する効果を持つ。しかし、このような場合にも、２つのノードが互いに近づく方向に動けば衝突が発生するが、既存のほとんどの水中無線媒体アクセス制御プロトコルは、このようなノードの移動性を考慮していない。
【０００７】
韓国特許登録第１５２２２７９号公報（発明の名称：水中音響ネットワークの精密時間−境界時分割多重アクセス方法、以下「特許文献」という）は、ノードの移動性を考慮しているが、各ノードの初期位置を知らなければならず、初期化過程でノードが固定されていなければならず、各ノードの移動速度情報がサイクルごとに持続的に更新されなければならず、時間同期化が不可欠であるという欠点がある。しかも、前記特許文献は、各ノードの速度情報を用いて位置推定を行い、これをベースにして往復時間遅延を推定する方法を提示しているが、これは時間が経つほど水中ノードの速度情報の累積による誤差が大きくなる環境で適用するのに限界があった。また、前記特許文献は、時間同期化のための具体的な方案が提示されておらず、同期化誤差への対応策がないため、各ノードの初期位置情報または速度を知ることができないか、或いは時間同期化が不可能な場合には、活用が不可能であるという問題点があった。
【０００８】
〔発明の概要〕
〔発明が解決しようとする課題〕
そこで、本発明は、かかる点に着目してなされたもので、その目的は、水中で移動ノードの航法情報とは無関係に動作するとともに、時間同期化が不要なので時間同期化のための別途のパケット交換が必要ないから、ネットワークの歩留まりを向上させることができる、水中無線移動ネットワークのためのスケジューリング方法を提供することにある。
【０００９】
本発明の他の目的は、水中音響無線移動ネットワークのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、チャンネル使用効率の向上によるネットワークの効率を向上させることができ、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であり、誤差が累積されないため周期的な再初期化が必要ない、水中無線移動ネットワークのためのスケジューリング方法を提供することにある。
【００１０】
本発明の別の目的は、水中音響無線移動ネットワークのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、チャンネル使用効率の向上によるネットワークの効率を向上させることができ、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であり、誤差が累積されないため周期的な再初期化が必要ない、水中無線移動ネットワークのためのスケジューリング方法を提供することにある。
【００１１】
〔課題を解決するための手段〕
上記の目的を達成するために、本発明の一実施形態による水中無線移動ネットワークのためのスケジューリング方法は、シンクノードから多数のノードへ初期化パケットを放送する第１段階と、前記シンクノードが多数のノードから第１設定時間
【数１】
2019508000.tif 000003
の間に初期化応答パケットを受信する第２段階と、前記シンクノードが前記第２段階で受信した初期化応答パケットから前記シンクノードと多数のノード間の往復時間遅延
【数２】
2019508000.tif 000004
を計算する第３段階と、前記シンクノードによって、初期化応答パケットの受信に衝突が存在するか否かを決定する第４段階と、前記第４段階で初期化応答パケットの受信に衝突が存在しなければ、前記シンクノードが、前記第３段階で計算された往復時間遅延
【数３】
2019508000.tif 000005
を用いて往復時間遅延の小さい順にノードを整列する第５段階と、前記シンクノードによって変数ｋが１に設定され、１番目のノードの待機時間
【数４】
2019508000.tif 000006
が「０」に設定される第６段階と、前記シンクノードによって、１番目のノードのデータパケットが前記シンクノードに受信され始める時刻の最大値
【数５】
2019508000.tif 000007
が計算される第７段階と、前記変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第８段階と、前記第８段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記変数ｋをｋ＋１に設定する第９段階と、前記シンクノードによって、ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値
【数６】
2019508000.tif 000008
が計算される第１０段階と、前記シンクノードによって前記ｋ番目のノードの待機時間
【数７】
2019508000.tif 000009
が計算される第１１段階と、前記シンクノードによって、前記ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最大値
【数８】
2019508000.tif 000010
を計算した後、前記第８段階へ移行する第１２段階と、前記第８段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードによって１番目のビーコンパケットが第３設定時刻
【数９】
2019508000.tif 000011
に多数のノードへ放送される第１３段階と、前記シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記第１３段階による１番目のビーコンパケットの放送後に第４設定時間
【数１０】
2019508000.tif 000012
を待機する第１４段階と、前記シンクノードによって前記シンクノードと前記ｋ番目のノード間の往復時間遅延
【数１１】
2019508000.tif 000013
が計算される第１５段階と、前記シンクノードが、前記第１５段階で計算された往復時間遅延
【数１２】
2019508000.tif 000014
を用いて往復時間遅延の小さい順にノードを整列する第１６段階と、前記シンクノードによって、１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
【数１３】
2019508000.tif 000015
が計算される第１７段階と、前記変数ｋを１に設定し、前記シンクノードが、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数１４】
2019508000.tif 000016
を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットを受信し始める時刻の最大値
【数１５】
2019508000.tif 000017
を計算する第１８段階と、前記変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第１９段階と、前記第１９段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記変数ｋをｋ＋１に設定する第２０段階と、前記シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値
【数１６】
2019508000.tif 000018
を計算する第２１段階と、前記シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延
【数１７】
2019508000.tif 000019
を計算する第２２段階と、前記シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値
【数１８】
2019508000.tif 000020
を計算した後、前記第１９段階へ移行する第２３段階と、前記第１９段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードによって、ビーコンパケット放送が行われるか否かが決定される第２４段階と、前記第２４段階でビーコンパケット放送が行われなければ終了する第２５段階とを含むことを特徴とする。
【００１２】
前記一実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第２４段階でシンクノードによってビーコンパケット放送が決定されれば、前記シンクノードによってｎ番目のサイクルのビーコンパケットが放送される時刻
【数１９】
2019508000.tif 000021
にビーコンパケットがノードに放送される第２６段階と、前記シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記ｎ番目のサイクルで最後番目のノードのデータパケットが受信され始める時刻の最大値
【数２０】
2019508000.tif 000022
を待機する第２７段階と、前記シンクノードによってサイクルが１だけ増加した後、前記第１５段階へ移行する第２８段階とが行われ得る。
【００１３】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第４段階で初期化応答パケットの受信に衝突が存在すれば、前記シンクノードによって再初期化パケットがノードに放送される第２９段階と、前記シンクノードによって第２設定時間
【数２１】
2019508000.tif 000023
だけ再初期化応答パケットが受信される第３０段階と、前記シンクノードが、前記第３０段階で受信した再初期化応答パケットから前記シンクノードとノード間の往復時間遅延
【数２２】
2019508000.tif 000024
を計算する第３１段階と、前記シンクノードによって、再初期化応答パケットの受信に衝突が存在するか否かを決定する第３２段階とが行われ、前記第３２段階で再初期化応答パケットの受信に衝突が存在すれば前記第２９段階へ移行することができる。
【００１４】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第３２段階で再初期化応答パケットの受信に衝突が存在しなければ、前記第５段階へ移行することができる。
【００１５】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１設定時間
【数２３】
2019508000.tif 000025
は下記数式１０１によって決定できる。
【００１６】
【数２４】
2019508000.tif 000026
【００１７】
［式中、
【数２５】
2019508000.tif 000027
は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、
【数２６】
2019508000.tif 000028
は初期化パケット長の時間換算値であり、
【数２７】
2019508000.tif 000029
は初期化応答パケット長の時間換算値であり、
【数２８】
2019508000.tif 000030
はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。
【数２９】
2019508000.tif 000031
【００１８】
（ｒはモデムの最大通信半径であり、ｃは音波速度である。）］
【００１９】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードと多数のノード間の往復時間遅延
【数３０】
2019508000.tif 000032
は下記数式１０３によって決定できる。
【００２０】
【数３１】
2019508000.tif 000033
【００２１】
（式中、
【数３２】
2019508000.tif 000034
はノードＨから受信された初期化応答パケットの受信時刻であり、
【数３３】
2019508000.tif 000035
は初期化パケット放送時間である。）
【００２２】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記１番目のノードのデータパケットが前記シンクノードに受信され始める時刻の最大値
【数３４】
2019508000.tif 000036
は、下記数式１０８によって決定できる。
【００２３】
【数３５】
2019508000.tif 000037
【００２４】
（式中、
【数３６】
2019508000.tif 000038
はシンクノードによる最初のビーコンパケット放送時刻であり、
【数３７】
2019508000.tif 000039
はビーコンパケット長の時間換算値であり、
【数３８】
2019508000.tif 000040
は１番目のノードの往復時間遅延であり、
【数３９】
2019508000.tif 000041
は１番目のノードのシンクノードとの往復時間遅延が取得された時点であり、
【数４０】
2019508000.tif 000042
はシンクノードとノード間の最大相対速度である。）
【００２５】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記ｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値
【数４１】
2019508000.tif 000043
は、下記数式１１３によって決定できる。
【００２６】
【数４２】
2019508000.tif 000044
【００２７】
（式中、
【数４３】
2019508000.tif 000045
はｋ番目のノードの往復時間遅延であり、
【数４４】
2019508000.tif 000046
は
【数４５】
2019508000.tif 000047
が取得された時刻である。）
【００２８】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記ｋ番目のノードの待機時間
【数４６】
2019508000.tif 000048
は下記数式１１４によって決定できる。
【００２９】
【数４７】
2019508000.tif 000049
【００３０】
［式中、
【数４８】
2019508000.tif 000050
はＡとＢの両者から大きい値を選択する関数であり、
【数４９】
2019508000.tif 000051
は、ｋ−１番目のノードのデータパケットがシンクノードに到着する時刻の最大値であって、下記数式１１２によって決定され、
【数５０】
2019508000.tif 000052
はｋ−１番目のノードのデータパケット長の時間換算値である。
【００３１】
【数５１】
2019508000.tif 000053
【００３２】
（式中、
【数５２】
2019508000.tif 000054
はｋ−１番目のノードの往復時間遅延であり、
【数５３】
2019508000.tif 000055
はｋ−１番目のノードの待機時間であり、
【数５４】
2019508000.tif 000056
は
【数５５】
2019508000.tif 000057
が取得された時間である。）］
【００３３】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードと前記ｋ番目のノード間の往復時間遅延
【数５６】
2019508000.tif 000058
は下記数式１１５によって決定できる。
【００３４】
【数５７】
2019508000.tif 000059
【００３５】
（式中、
【数５８】
2019508000.tif 000060
はｎ番目のサイクルのビーコンパケットが放送される時刻であり、
【数５９】
2019508000.tif 000061
はｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻であり、
【数６０】
2019508000.tif 000062
はｎ番目のサイクルでｋ番目のノードに付与される時間遅延であり、
【数６１】
2019508000.tif 000063
はｎ番目のサイクルにおけるビーコン長の時間換算値である。）
【００３６】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
【数６２】
2019508000.tif 000064
は下記数式１１６によって決定できる。
【００３７】
【数６３】
2019508000.tif 000065
【００３８】
（式中、
【数６４】
2019508000.tif 000066
は（ｎ−１）番目のサイクルにおけるデータパケットの受信開始時刻である。）
【００３９】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、各ノードの（ｎ−１）番目のサイクルにおけるデータパケットの受信時刻
【数６５】
2019508000.tif 000067
とｎ番目のサイクルにおけるデータパケットの受信時刻
【数６６】
2019508000.tif 000068
との差は下記数式１１７のように近似することができる。
【００４０】
【数６７】
2019508000.tif 000069
【００４１】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第２設定時間
【数６８】
2019508000.tif 000070
は下記数式１０５によって決定できる。
【００４２】
【数６９】
2019508000.tif 000071
【００４３】
（式中、
【数７０】
2019508000.tif 000072
は再初期化パケット長の時間換算値であり、
【数７１】
2019508000.tif 000073
は再初期化応答パケット長の時間換算値である。）
【００４４】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値
【数７２】
2019508000.tif 000074
は、下記数式１１８によって決定できる。
【００４５】
【数７３】
2019508000.tif 000075
【００４６】
（式中、
【数７４】
2019508000.tif 000076
はｎ−１番目のサイクルにおける１番目のノードの往復時間遅延であり、
【数７５】
2019508000.tif 000077
はｎ番目のサイクルにおける１番目のノードのデータパケット長の時間換算値である。）
【００４７】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードにｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値
【数７６】
2019508000.tif 000078
は、下記数式１１９によって計算できる。
【００４８】
【数７７】
2019508000.tif 000079
【００４９】
（式中、
【数７８】
2019508000.tif 000080
はｎ−１番目のサイクルにおけるｋ番目のノードの往復時間遅延である。）
【００５０】
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延
【数７９】
2019508000.tif 000081
は、下記数式１２０によって計算できる。
【００５１】
【数８０】
2019508000.tif 000082
【００５２】
(式中、
【数８１】
2019508000.tif 000083
はｎ番目のサイクルでｋ−１番目のノードのデータパケットが受信され始める時刻の最大値である。)
前記実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記シンクノードにｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値
【数８２】
2019508000.tif 000084
は、下記数式１２１によって計算できる。
【００５３】
【数８３】
2019508000.tif 000085
【００５４】
（式中、
【数８４】
2019508000.tif 000086
はｎ番目のサイクルにおけるｋ番目のノードのデータパケット長の時間換算値である。）
【００５５】
上記の他の目的を達成するために、本発明の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法は、伝送スケジュールを含んでいるビーコンパケットを放送する一つのシンクノードと、前記シンクノードのビーコンパケットを受信して伝送スケジュールに従ってデータパケットを前記シンクノードへ伝送する多数のノードとから構成されたネットワークトポロジーで時分割多重アクセスを行う、水中無線移動ネットワークのためのスケジューリング方法であって：前記シンクノードが初期化過程を行う第１’段階と、前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数８５】
2019508000.tif 000087
を０に設定する第２’段階と、前記シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数８６】
2019508000.tif 000088
を推定し、１番目のノードのデータパケット受信完了時点
【数８７】
2019508000.tif 000089
を計算する第３’段階と、前記シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第４’段階と、前記第４’段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記シンクノードが前記変数ｋをｋ＋１に設定する第５’段階と、前記シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数８８】
2019508000.tif 000090
を推定する第６’段階と、前記シンクノードが、前記第６’段階で推定されたｋ番目のノードの往復時間遅延
【数８９】
2019508000.tif 000091
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９０】
2019508000.tif 000092
を計算する第７’段階と、前記シンクノードが、前記第７’段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９１】
2019508000.tif 000093
を用いて、ｋ番目のノードの待機時間
【数９２】
2019508000.tif 000094
を計算する第８’段階と、前記シンクノードが、前記第７’段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９３】
2019508000.tif 000095
と前記第８’段階で計算されたｋ番目のノードの待機時間
【数９４】
2019508000.tif 000096
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数９５】
2019508000.tif 000097
を計算した後、前記第４’段階へ移行する第９’段階とを含むことを特徴とする。
【００５６】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第４’段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードがビーコンパケットの放送有無を判断する第１０’段階をさらに含み、前記第１０’段階でビーコンパケットが放送されなければすべての手続きを終了することができる。
【００５７】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１０’段階でビーコンパケットが放送されれば、前記シンクノードが、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻
【数９６】
2019508000.tif 000098
にビーコンパケットを放送する第１１’段階と、Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値
【数９７】
2019508000.tif 000099
が超過する第１２’段階と、前記シンクノードが、ｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数９８】
2019508000.tif 000100
を計算し、往復時間遅延取得有効性値
【数９９】
2019508000.tif 000101
及び直近に取得された往復時間遅延関連情報
【数１００】
2019508000.tif 000102
を更新する第１３’段階と、前記シンクノードがｎを１だけ増加させた後、前記第２’段階へ移行する第１４’段階とを含むことができる。
【００５８】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１’段階で、前記シンクノードは下記［数式２０１］のように初期化過程を行うことができる。
【００５９】
【数１０１】
2019508000.tif 000103
【００６０】
（式中、
【数１０２】
2019508000.tif 000104
はｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数１０３】
2019508000.tif 000105
はｎ番目のサイクルで、（ｎ−２）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数１０４】
2019508000.tif 000106
は直近に取得されたｋ番目のノードの往復時間遅延であり、
【数１０５】
2019508000.tif 000107
は
【数１０６】
2019508000.tif 000108
が得られたサイクルであり、
【数１０７】
2019508000.tif 000109
はシンクノードと各ノード間の最初の往復時間遅延であり、
【数１０８】
2019508000.tif 000110
は１番目のサイクル前の持続時間であり、
【数１０９】
2019508000.tif 000111
は下記数式２０２のように推定されて定められる。）
【００６１】
【数１１０】
2019508000.tif 000112
【００６２】
（
【数１１１】
2019508000.tif 000113
は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【００６３】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第３’段階は、直近の２サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合には、下記［数式２０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数１１２】
2019508000.tif 000114
を推定し、１番目のノードのデータパケット受信完了時点
【数１１３】
2019508000.tif 000115
を計算することができる。
【００６４】
【数１１４】
2019508000.tif 000116
【００６５】
（式中、
【数１１５】
2019508000.tif 000117
はガード時間であり、
【数１１６】
2019508000.tif 000118
はｎ−１番目のサイクルで取得された１番目のノードの往復時間遅延であり、
【数１１７】
2019508000.tif 000119
はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、
【数１１８】
2019508000.tif 000120
はｎ−１番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻であり、
【数１１９】
2019508000.tif 000121
は下記数式２０４のとおりである。）
【００６６】
【数１２０】
2019508000.tif 000122
【００６７】
（式中、
【数１２１】
2019508000.tif 000123
はｎ−２番目のサイクルで取得された１番目のノードの往復時間遅延であり、
【数１２２】
2019508000.tif 000124
はｎ−２番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻である。）
【００６８】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記［数式２０３］は、下記の連立方程式である［数式２０６］を解いて得られる。
【００６９】
【数１２３】
2019508000.tif 000125
【００７０】
（式中、
【数１２４】
2019508000.tif 000126
はｎ番目のサイクルで１番目のノードのデータパケット受信時刻
【数１２５】
2019508000.tif 000127
に対する推定値である。）
【００７１】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第３’段階は、直近の２サイクルの間に１番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２０５］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数１２６】
2019508000.tif 000128
を推定し、１番目のノードのデータパケット受信完了時点
【数１２７】
2019508000.tif 000129
を計算することができる。
【００７２】
【数１２８】
2019508000.tif 000130
【００７３】
（式中、
【数１２９】
2019508000.tif 000131
は往復時間遅延の最大値であり、
【数１３０】
2019508000.tif 000132
は直近に取得された１番目のノードの往復時間遅延であり、
【数１３１】
2019508000.tif 000133
はシンクノードとｋ番目のノード間の最大相対速度であり、
【数１３２】
2019508000.tif 000134
はｎ−１番目のサイクルの持続時間であり、
【数１３３】
2019508000.tif 000135
は１番目のノードの往復時間遅延が取得された直近のサイクルであり、
【数１３４】
2019508000.tif 000136
は水中での最小音波伝達速度である。）
【００７４】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６’段階は、直近の２サイクルの間にｋ番目のノードの往復時間遅延
【数１３５】
2019508000.tif 000137
が成功的に取得された場合には、下記［数式２０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１３６】
2019508000.tif 000138
を推定することができる。
【００７５】
【数１３７】
2019508000.tif 000139
【００７６】
（式中、
【数１３８】
2019508000.tif 000140
はｎ−１番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、
【数１３９】
2019508000.tif 000141
はｋ−１番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値であり、
【数１４０】
2019508000.tif 000142
はｎ−１番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻であり、
【数１４１】
2019508000.tif 000143
は下記数式２１１のとおりである。）
【００７７】
【数１４２】
2019508000.tif 000144
【００７８】
（式中、
【数１４３】
2019508000.tif 000145
は、ｎ−２番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、
【数１４４】
2019508000.tif 000146
はｎ−２番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻である。）
【００７９】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、第６’段階は、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２１２］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１４５】
2019508000.tif 000147
を推定することができる。
【００８０】
【数１４６】
2019508000.tif 000148
【００８１】
（式中、
【数１４７】
2019508000.tif 000149
は、
【数１４８】
2019508000.tif 000150
が得られたサイクルである。）
【００８２】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第７’段階で、前記ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数１４９】
2019508000.tif 000151
は、下記［数式２１３］のように計算できる。
【００８３】
【数１５０】
2019508000.tif 000152
【００８４】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第８’段階で、前記ｋ番目のノードの待機時間
【数１５１】
2019508000.tif 000153
は、下記［数式２１４］のように計算できる。
【００８５】
【数１５２】
2019508000.tif 000154
【００８６】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第９’段階で、直近の２サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数１５３】
2019508000.tif 000155
は、下記［数式２１５］のように計算できる。
【００８７】
【数１５４】
2019508000.tif 000156
【００８８】
（式中、
【数１５５】
2019508000.tif 000157
はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【００８９】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第９’段階で、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数１５６】
2019508000.tif 000158
は、下記［数式２１６］のように計算できる。
【００９０】
【数１５７】
2019508000.tif 000159
【００９１】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１３’段階で、前記往復時間遅延取得有効性値
【数１５８】
2019508000.tif 000160
を更新するために、下記［数式２１７］のように、すべてのノードに対して前記往復時間遅延取得有効性値
【数１５９】
2019508000.tif 000161
を更新し、ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式２１８］のようにし、ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式２１９］のようにし、前記直近に取得された往復時間遅延関連情報
【数１６０】
2019508000.tif 000162
は下記［数式２２０］のように更新し、また、前記往復時間遅延取得有効性値
【数１６１】
2019508000.tif 000163
が１である場合には、下記［数式２２１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１６２】
2019508000.tif 000164
を計算し、直近に取得された往復時間遅延関連情報
【数１６３】
2019508000.tif 000165
を更新することができる。
【００９２】
【数１６４】
2019508000.tif 000166
【００９３】
上記の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延
【数１６５】
2019508000.tif 000167
を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻
【数１６６】
2019508000.tif 000168
は、下記［数式２０８］のように計算される。このとき、
【数１６７】
2019508000.tif 000169
の場合には、次のように［数式２０９］を解いて、下記［数式２１０］のようにｋ番目のノードの往復時間遅延を推定し、前記［数式２１０］における
【数１６８】
2019508000.tif 000170
は前記［数式２１１］のとおりであり得る。
【００９４】
【数１６９】
2019508000.tif 000171
【００９５】
上記の目的を達成するために、本発明の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法は、伝送スケジュールを含んでいるビーコンパケットを放送する一つのシンクノードと、前記シンクノードのビーコンパケットを受信して伝送スケジュールに従ってデータパケットを前記シンクノードへ伝送する多数のノードとから構成されたネットワークトポロジーで時分割多重アクセスを行う、多項式補間法を用いた水中無線移動ネットワークのためのスケジューリング方法であって：前記シンクノードが初期化過程を行う第１”段階と、前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数１７０】
2019508000.tif 000172
を０に設定する第２”段階と、前記シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数１７１】
2019508000.tif 000173
を推定し、１番目のノードのデータパケット受信完了時点
【数１７２】
2019508000.tif 000174
を計算する第３”段階と、前記シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する第４”段階と、前記第４”段階で前記変数ｋが最後番目（Ｋ番目）より小さければ、前記シンクノードが前記変数ｋをｋ＋１に設定する第５”段階と、前記シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１７３】
2019508000.tif 000175
を推定する第６”段階と、前記シンクノードが、前記第６”段階で推定されたｋ番目のノードの往復時間遅延
【数１７４】
2019508000.tif 000176
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数１７５】
2019508000.tif 000177
を計算する第７”段階と、前記シンクノードが、前記第７”段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数１７６】
2019508000.tif 000178
を用いて、ｋ番目のノードの待機時間
【数１７７】
2019508000.tif 000179
を計算する第８”段階と、前記シンクノードが、前記第７”段階で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数１７８】
2019508000.tif 000180
と前記第８”段階で計算されたｋ番目のノードの待機時間
【数１７９】
2019508000.tif 000181
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数１８０】
2019508000.tif 000182
を計算した後、前記第４”段階へ移行する第９”段階とを含むことを特徴とする。
【００９６】
上記別の実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第４”段階で前記変数ｋが最後番目（Ｋ番目）より小さくなければ、前記シンクノードがビーコンパケットの放送有無を判断する第１０”段階をさらに含み、前記第１０”段階でビーコンパケットが放送されなければすべての手続きを終了することができる。
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法は、前記第１０”段階でビーコンパケットが放送されれば、前記シンクノードが、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻
【数１８１】
2019508000.tif 000183
にビーコンパケットを放送する第１１”段階と、Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値
【数１８２】
2019508000.tif 000184
が超過する第１２”段階と、前記シンクノードが、ｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数１８３】
2019508000.tif 000185
を計算し、往復時間遅延取得有効性値
【数１８４】
2019508000.tif 000186
及び直近に取得された往復時間遅延関連情報
【数１８５】
2019508000.tif 000187
を更新する第１３”段階と、前記シンクノードがｎを１だけ増加させた後、前記第２”段階へ移行する第１４”段階とを含むことができる。
【００９７】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１”段階で、前記シンクノードは下記［数式３０１］のように初期化過程を行うことができる。
【００９８】
【数１８６】
2019508000.tif 000188
【００９９】
（式中、
【数１８７】
2019508000.tif 000189
は
【数１８８】
2019508000.tif 000190
よりも小さいか同じ自然数であり、
【数１８９】
2019508000.tif 000191
であり、
【数１９０】
2019508000.tif 000192
はｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数１９１】
2019508000.tif 000193
はｎ番目のサイクルで、（ｎ−ｍ）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数１９２】
2019508000.tif 000194
は直近に取得されたｋ番目のノードの往復時間遅延であり、
【数１９３】
2019508000.tif 000195
は
【数１９４】
2019508000.tif 000196
が得られたサイクルであり、
【数１９５】
2019508000.tif 000197
はシンクノードと各ノード間の最初の往復時間遅延であり、
【数１９６】
2019508000.tif 000198
は１番目のサイクル前の持続時間であり、
【数１９７】
2019508000.tif 000199
は下記数式３０２のように推定されて定められる。）
【０１００】
【数１９８】
2019508000.tif 000200
【０１０１】
（式中、
【数１９９】
2019508000.tif 000201
は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【０１０２】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第３”段階は、直近のＭサイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数２００】
2019508000.tif 000202
（２以上の自然数という）回以上であれば、下記［数式３０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数２０１】
2019508000.tif 000203
を推定し、１番目のノードのデータパケット受信完了時点
【数２０２】
2019508000.tif 000204
を下記［数式３０５］のように計算することができる。
【０１０３】
【数２０３】
2019508000.tif 000205
【０１０４】
（式中、
【数２０４】
2019508000.tif 000206
は、
【数２０５】
2019508000.tif 000207
座標を通る最小次数の多項式であり、
【数２０６】
2019508000.tif 000208
はｎ番目のサイクルで１番目のノードのデータパケット受信時刻
【数２０７】
2019508000.tif 000209
に対する推定値であり、
【数２０８】
2019508000.tif 000210
はｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻であり、
【数２０９】
2019508000.tif 000211
はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、
【数２１０】
2019508000.tif 000212
は下記数式３０４のように値を制限する。）
【０１０５】
【数２１１】
2019508000.tif 000213
【０１０６】
（式中、
【数２１２】
2019508000.tif 000214
は往復時間遅延の最大値である。）
【０１０７】
【数２１３】
2019508000.tif 000215
【０１０８】
（式中、
【数２１４】
2019508000.tif 000216
はｎ番目のサイクルで１番目のノードのデータパケット長を時間に換算した値であり、
【数２１５】
2019508000.tif 000217
はガード時間である。）
【０１０９】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記［数式３０３］は次のように反復的に解が求められる。
【０１１０】
１）
【数２１６】
2019508000.tif 000218
の初期値を
【数２１７】
2019508000.tif 000219
または
【数２１８】
2019508000.tif 000220
のように定め、
２）前記初期値
【数２１９】
2019508000.tif 000221
を用いて［数式３０３］から
【数２２０】
2019508000.tif 000222
を
【数２２１】
2019508000.tif 000223
のように計算し、
３）前記２）で計算された
【数２２２】
2019508000.tif 000224
を用いて
【数２２３】
2019508000.tif 000225
を
【数２２４】
2019508000.tif 000226
のように計算し、
４）前記３）で計算された
【数２２５】
2019508000.tif 000227
から
【数２２６】
2019508000.tif 000228
を
【数２２７】
2019508000.tif 000229
のように計算し、
５）前記４）で計算された
【数２２８】
2019508000.tif 000230
を用いて
【数２２９】
2019508000.tif 000231
を
【数２３０】
2019508000.tif 000232
のように計算し、
６）前記５）で計算された
【数２３１】
2019508000.tif 000233
から
【数２３２】
2019508000.tif 000234
を
【数２３３】
2019508000.tif 000235
のように計算する過程を、設定された回数だけ繰り返した後、最終的に計算される値を
【数２３４】
2019508000.tif 000236
と
【数２３５】
2019508000.tif 000237
に確定する（このとき、繰り返し回数を定めず、以前に計算された
【数２３６】
2019508000.tif 000238
と現在計算された
【数２３７】
2019508000.tif 000239
との差が一定値以下である場合に繰り返し過程を中断し、或いは、以前に計算された
【数２３８】
2019508000.tif 000240
と現在計算された
【数２３９】
2019508000.tif 000241
との差が一定値以下である場合に繰り返し過程を中断する。）
【０１１１】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第３”段階は、直近の
【数２４０】
2019508000.tif 000242
サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数２４１】
2019508000.tif 000243
回未満であれば、下記［数式３０６］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数２４２】
2019508000.tif 000244
を推定し、１番目のノードのデータパケット受信完了時点
【数２４３】
2019508000.tif 000245
を計算することができる。
【０１１２】
【数２４４】
2019508000.tif 000246
【０１１３】
（式中、
【数２４５】
2019508000.tif 000247
は直近に取得された１番目のノードの往復時間遅延であり、
【数２４６】
2019508000.tif 000248
はシンクノードとｋ番目のノード間の最大相対速度であり、
【数２４７】
2019508000.tif 000249
はｎ−１番目のサイクルの持続時間であり、
【数２４８】
2019508000.tif 000250
は１番目のノードの往復時間遅延が取得された直近のサイクルであり、
【数２４９】
2019508000.tif 000251
は水中での音波伝達速度の最小値である。）
【０１１４】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６”段階は、直近の
【数２５０】
2019508000.tif 000252
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数２５１】
2019508000.tif 000253
回以上であれば、下記［数式３０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数２５２】
2019508000.tif 000254
を推定することができる。
【０１１５】
【数２５３】
2019508000.tif 000255
【０１１６】
（式中、
【数２５４】
2019508000.tif 000256
は
【数２５５】
2019508000.tif 000257
座標を通る最小次数の多項式であり、
【数２５６】
2019508000.tif 000258
は
【数２５７】
2019508000.tif 000259
サイクルでｋ番目のノードの有効な往復時間遅延値であり、
【数２５８】
2019508000.tif 000260
は（ｋ−１）番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値である。）
【０１１７】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６”段階でｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延
【数２５９】
2019508000.tif 000261
を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻
【数２６０】
2019508000.tif 000262
は、下記［数式３０８］のように計算できる。
【０１１８】
【数２６１】
2019508000.tif 000263
【０１１９】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６”段階は、
【数２６２】
2019508000.tif 000264
の場合には、下記［数式３０９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数２６３】
2019508000.tif 000265
を推定することができる。
【０１２０】
【数２６４】
2019508000.tif 000266
【０１２１】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記［数式３０９］は、次のように反復的に解が求められる。
【０１２２】
１’）
【数２６５】
2019508000.tif 000267
の初期値を
【数２６６】
2019508000.tif 000268
または
【数２６７】
2019508000.tif 000269
のように定め、
２’）前記初期値
【数２６８】
2019508000.tif 000270
を用いて［数式３０９］から
【数２６９】
2019508000.tif 000271
を
【数２７０】
2019508000.tif 000272
のように計算し、
３’）計算された
【数２７１】
2019508000.tif 000273
を用いて
【数２７２】
2019508000.tif 000274
を
【数２７３】
2019508000.tif 000275
のように計算し、
４’）前記３’）で計算された
【数２７４】
2019508000.tif 000276
から
【数２７５】
2019508000.tif 000277
を
【数２７６】
2019508000.tif 000278
のように計算し、
５’）前記４’）で計算された
【数２７７】
2019508000.tif 000279
を用いて
【数２７８】
2019508000.tif 000280
を
【数２７９】
2019508000.tif 000281
のように計算し、
６’）前記５’）で計算された
【数２８０】
2019508000.tif 000282
から
【数２８１】
2019508000.tif 000283
を
【数２８２】
2019508000.tif 000284
のように計算する
過程を、設定された回数だけ繰り返した後、最終的に計算される値を
【数２８３】
2019508000.tif 000285
と
【数２８４】
2019508000.tif 000286
に確定する（このとき、繰り返し回数を定めず、以前に計算された
【数２８５】
2019508000.tif 000287
と現在計算された
【数２８６】
2019508000.tif 000288
との差が一定値以下である場合に繰り返し過程を中断し、あるいは、以前に計算された
【数２８７】
2019508000.tif 000289
と現在計算された
【数２８８】
2019508000.tif 000290
との差が一定値以下である場合に繰り返し過程を中断する。）
【０１２３】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記
【数２８９】
2019508000.tif 000291
は下記［数式３１０］のように値を制限することができる。
【０１２４】
【数２９０】
2019508000.tif 000292
【０１２５】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第６”段階は、直近の
【数２９１】
2019508000.tif 000293
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数２９２】
2019508000.tif 000294
回未満であれば、下記［数式３１１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数２９３】
2019508000.tif 000295
を推定することができる。
【０１２６】
【数２９４】
2019508000.tif 000296
【０１２７】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第７”段階で前記ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数２９５】
2019508000.tif 000297
は、下記［数式３０８］によって計算できる。
【０１２８】
【数２９６】
2019508000.tif 000298
【０１２９】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第８’段階で前記ｋ番目のノードの待機時間
【数２９７】
2019508000.tif 000299
は、下記［数式３１２］によって計算できる。
【０１３０】
【数２９８】
2019508000.tif 000300
【０１３１】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第９”段階で、直近の
【数２９９】
2019508000.tif 000301
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数３００】
2019508000.tif 000302
回以上であれば、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数３０１】
2019508000.tif 000303
は、下記［数式３１３］のように計算できる。
【０１３２】
【数３０２】
2019508000.tif 000304
【０１３３】
（式中、
【数３０３】
2019508000.tif 000305
はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【０１３４】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第９”段階で、直近の
【数３０４】
2019508000.tif 000306
サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数３０５】
2019508000.tif 000307
回未満であれば、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数３０６】
2019508000.tif 000308
は、下記［数式３１４］のように計算できる。
【０１３５】
【数３０７】
2019508000.tif 000309
【０１３６】
上記の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法において、前記第１３”段階で、前記往復時間遅延取得有効性値
【数３０８】
2019508000.tif 000310
を更新するために、下記［数式３１５］のようにすべてのノードに対して前記往復時間遅延取得有効性値
【数３０９】
2019508000.tif 000311
を更新し、ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式３１６］のようにし、ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式３１７］のようにし、前記直近に取得された往復時間遅延関連情報
【数３１０】
2019508000.tif 000312
は、下記［数式３１８］のように更新し、また、前記往復時間遅延取得有効性値
【数３１１】
2019508000.tif 000313
が１である場合には、下記［数式３１９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数３１２】
2019508000.tif 000314
を計算し、直近に取得された往復時間遅延関連情報
【数３１３】
2019508000.tif 000315
を更新することができる。
【０１３７】
【数３１４】
2019508000.tif 000316
【０１３８】
〔発明の効果〕
本発明の一実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードから多数のノードへ初期化パケットを放送し、シンクノードが多数のノードから第１設定時間
【数３１５】
2019508000.tif 000317
の間に初期化応答パケットを受信し、前記シンクノードが受信した初期化応答パケットからシンクノードと多数のノード間の往復時間遅
【数３１６】
2019508000.tif 000318
を計算し、シンクノードによって初期化応答パケットの受信に衝突が存在するか否かを決定し、初期化応答パケットの受信に衝突が存在しなければ、シンクノードが計算された往復時間遅延
【数３１７】
2019508000.tif 000319
を用いて往復時間遅延の小さい順にノードを整列し、シンクノードによって変数ｋが１に設定され、１番目のノードの待機時間
【数３１８】
2019508000.tif 000320
が「０」に設定され、シンクノードによって１番目のノードのデータパケットがシンクノードに受信され始める時刻の最大値
【数３１９】
2019508000.tif 000321
が計算され、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し、変数ｋが最後番目（Ｋ番目）より小さければ、変数ｋをｋ＋１に設定し、シンクノードによってｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値
【数３２０】
2019508000.tif 000322
が計算され、シンクノードによってｋ番目のノードの待機時間
【数３２１】
2019508000.tif 000323
が計算され、シンクノードによってｋ番目のノードのデータパケットがシンクノードに到着する時刻の最大値
【数３２２】
2019508000.tif 000324
を計算した後、変数ｋが最後番目（Ｋ番目）より小さくなければ、シンクノードによって１番目のビーコンパケットが第３設定時刻
【数３２３】
2019508000.tif 000325
に多数のノードに放送され、シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または１番目のビーコンパケット放送後に第４設定時間
【数３２４】
2019508000.tif 000326
を待機し、シンクノードによってシンクノードとｋ番目のノード間の往復時間遅延
【数３２５】
2019508000.tif 000327
が計算され、シンクノードが計算された往復時間遅延
【数３２６】
2019508000.tif 000328
を用いて往復時間遅延の小さい順にノードを整列し、シンクノードによって１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
【数３２７】
2019508000.tif 000329
が計算され、変数ｋを１に設定し、シンクノードがｎ番目のサイクルで１番目のノードに付与される時間遅延
【数３２８】
2019508000.tif 000330
を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値
【数３２９】
2019508000.tif 000331
を計算し、変数ｋが最後番目（Ｋ番目）より小さいか否かを判断して、変数ｋが最後番目（Ｋ番目）より小さければ変数ｋをｋ＋１に設定し、シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値
【数３３０】
2019508000.tif 000332
を計算し、シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延
【数３３１】
2019508000.tif 000333
を計算し、シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値
【数３３２】
2019508000.tif 000334
を計算した後、変数ｋが最後番目（Ｋ番目）より小さくなければ、シンクノードによってビーコンパケット放送が行われるか否かが決定され、ビーコンパケット放送が行われなければ終了するように構成されることにより、
第一に、水中で移動ノードの航法情報とは無関係に動作し、
第二に、時間同期化が不要なので、時間同期化のための別途のパケット交換が必要ないから、ネットワークの歩留まりを向上させることができ、
第三に、スケジュール情報が絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作し、
第四に、毎サイクル終了時点でシンクノードとノード間の往復時間遅延情報に対する正確な値が測定されるので、スケジュール情報は、時間が経過するにつれて誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。
【０１３９】
また、本発明の他の実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードが初期化過程を行い；シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数３３３】
2019508000.tif 000335
を０に設定し；シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数３３４】
2019508000.tif 000336
を推定し、１番目のノードのデータパケット受信完了時点
【数３３５】
2019508000.tif 000337
を計算し；シンクノードによって変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し；前記判断で変数ｋが最後番目（Ｋ番目）より小さければ、シンクノードが前記変数ｋをｋ＋１に設定し；シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数３３６】
2019508000.tif 000338
を推定し；シンクノードが、前記推定されたｋ番目のノードの往復時間遅延
【数３３７】
2019508000.tif 000339
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数３３８】
2019508000.tif 000340
を計算し；シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数３３９】
2019508000.tif 000341
を用いてｋ番目のノードの待機時間
【数３４０】
2019508000.tif 000342
を計算し；及び、シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数３４１】
2019508000.tif 000343
と前記計算されたｋ番目のノードの待機時間
【数３４２】
2019508000.tif 000344
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数３４３】
2019508000.tif 000345
を計算した後、前記判断過程へ移行するように構成されることにより：
すなわち、水中音響無線移動ネットワークなどのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、多数のノードがシンクノードへデータパケットを時分割多重アクセス方式で伝送しようとするとき、ノードの移動性による往復時間遅延をサイクル単位で追跡して、シンクノードがノードからデータパケットを受信する上で遊休時間を最小化することにより、チャンネル使用効率の向上によるネットワークの効率が大幅に向上することができるという優れた効果がある。特に、ノード数が増加すればするほど、ネットワーク効率の向上程度はさらに増加する。本発明に係る水中無線移動ネットワークのためのスケジューリング方法は、絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作する。したがって、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であるという利点がある。
また、往復時間遅延情報に対する正確な値がサイクルごとに得られるので、誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。
【０１４０】
本発明の別の実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードが初期化過程を行い；前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数３４４】
2019508000.tif 000346
を０に設定し；シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数３４５】
2019508000.tif 000347
を推定し、１番目のノードのデータパケット受信完了時点
【数３４６】
2019508000.tif 000348
を計算し；シンクノードによって変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し；前記判断で変数ｋが最後番目（Ｋ番目）より小さければ、シンクノードが変数ｋをｋ＋１に設定し；シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数３４７】
2019508000.tif 000349
を推定し；シンクノードが、前記推定されたｋ番目のノードの往復時間遅延
【数３４８】
2019508000.tif 000350
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数３４９】
2019508000.tif 000351
を計算し；シンクノードが、計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数３５０】
2019508000.tif 000352
を用いて、ｋ番目のノードの待機時間
【数３５１】
2019508000.tif 000353
を計算し；前記シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数３５２】
2019508000.tif 000354
と前記計算されたｋ番目のノードの待機時間
【数３５３】
2019508000.tif 000355
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数３５４】
2019508000.tif 000356
を計算した後、前記判断過程へ移行するように構成されることにより：
すなわち、水中音響無線移動ネットワークのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、チャンネル使用効率の向上によるネットワークの効率を向上させることができ、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であり、誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。特に、ノード数が増加すればするほど、ネットワーク効率の向上程度はさらに増加する。本発明に係る水中無線移動ネットワークのためのスケジューリング方法は、絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作する。したがって、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であるという利点がある。
【０１４１】
また、往復時間遅延情報に対する正確な値がサイクルごとに得られるので、誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。
【０１４２】
〔図面の簡単な説明〕
〔図１〕本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図２ａ乃至図２ｆ〕本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
〔図３〕本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。
〔図４〕本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。
〔図５〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図６〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
〔図７ａ及び図７ｂ〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
〔図８〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図９〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
〔図１０ａ乃至図１０ｃ〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【０１４３】
〔発明を実施するための形態〕
以下、本発明の実施形態を、添付図面を参照して詳細に説明する。
【０１４４】
［第１実施形態］
図１は本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図であって、ネットワークトポロジーは、一つのシンクノードと多数のノードとから構成されている。水中で音波を用いて多数のノードが一つのシンクノードへデータパケットを送る中央集中方式のネットワークトポロジーにおけるスケジューリング方法である。シンクノード以外のノードは「ノード」と略記することがある。シンクノードは、ノードの伝送スケジュールを含んでいるビーコンパケットを放送し、ビーコンパケットを受信したノードは、ビーコンパケットに指示されている各ノードの伝送スケジュールに従ってデータパケットをシンクノードへ伝送する。シンクノードとノード間の最大相対速度を知っていると仮定し、Ｖで表示する。
【０１４５】
以下、前述のように構成されたネットワークトポロジーで行われる、本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法について説明する。
【０１４６】
図２ａ乃至図２ｆは本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートであり、ここで、Ｓはステップ（Ｓｔｅｐ）を意味する。
【０１４７】
本発明のスケジューリング方法は、シンクノードと多数のノード間の往復時間遅延（ＲＴＴ：Ｒｏｕｎｄ  Ｔｒｉｐ  Ｔｉｍｅ）を求め、これに基づいて最初の衝突回避スケジュールを導出する初期化過程と、初期化過程でシンクノードがビーコンパケット放送してすべてのノードからデータパッケージの受信が完了する１番目のサイクル後に行われる正規過程とを含む。
【０１４８】
初期化過程
まず、シンクノードから多数のノードへ初期化（ＩＲＱ）パケットを放送し（Ｓ１０１０）、シンクノードが多数のノードから第１設定時間
【数３５５】
2019508000.tif 000357
の間に初期化応答（ＩＲＰ）パケットを受信する（Ｓ１０２０）。
【０１４９】
初期化パケットは、ノードが初期化パケットを受信したときに初期化パケットであることを知ることができるパケット種類識別情報のみを含んでいればよいので、その長さが非常に短い。初期化応答パケットはは、該当初期化応答パケットを送信するノードのアドレス情報と、初期化応答パケットであることを示すパケット種類識別情報とを含む。モデムの最大通信半径をｒとし、音波の速度をｃとすると、シンクノードは、初期化パケット放送の後、次のとおり、第１設定時間
【数３５６】
2019508000.tif 000358
以内にすべてのノードから初期化応答パケットの受信が完了する。
【０１５０】
第１設定時間
【数３５７】
2019508000.tif 000359
は、下記数式１０１によって決定される。
【０１５１】
【数３５８】
2019508000.tif 000360
【０１５２】
(式中、
【数３５９】
2019508000.tif 000361
は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、
【数３６０】
2019508000.tif 000362
は初期化パケット長の時間換算値であり、
【数３６１】
2019508000.tif 000363
は初期化応答パケット長の時間換算値であり、
【数３６２】
2019508000.tif 000364
はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。)
【０１５３】
【数３６３】
2019508000.tif 000365
【０１５４】
（式中、ｒはモデムの最大通信半径であり、ｃは音波の速度である。）
【０１５５】
次いで、シンクノードが前記ステップ（Ｓ１０２０）で受信した初期化応答パケットからシンクノードと多数のノード間の往復時間遅延
【数３６４】
2019508000.tif 000366
を計算する（Ｓ１０３０）。具体的には、シンクノードは、初期化パケット送信時間
【数３６５】
2019508000.tif 000367
をシンクノード自身のローカルクロックから知ることができ、ノードＨから受信された初期化応答パケットの受信時刻
【数３６６】
2019508000.tif 000368
もシンクノード自身のローカルクロックから知ることができる。したがって、シンクノードは、時間同期化なしにシンクノードとノードＨ間の往復時間遅延情報
【数３６７】
2019508000.tif 000369
を初期化応答パケット受信時刻と初期化パケット送信時刻との差から取得することができる。
【０１５６】
シンクノードと多数のノード間の往復時間遅延
【数３６８】
2019508000.tif 000370
は、下記数式１０３によって決定される。
【０１５７】
【数３６９】
2019508000.tif 000371
【０１５８】
その後、シンクノードによって初期化応答パケットの受信に衝突が存在するか否かを決定する（Ｓ１０４０）。
【０１５９】
シンクノードがノードから初期化応答（ＩＲＰ）パケットを受信するときに多数のノードから初期化応答パケットを受信するが、シンクノードと各ノード間の往復時間遅延差が初期化応答パケット長より大きいさえすれば衝突が発生しない。例えば、物理階層の伝送速度が１００ｋｂｐｓであり、音波の伝達速度が１，５００ｍ／ｓである場合を考えると、一つのビットが占める長さは０．０１ｍｓであり、初期化応答パケットはノードのアドレスとパケットタイプの情報だけを含めばよいので、３０ｂｉｔと仮定すれば、このときの初期化応答パケット長は０．３ｍｓであり、０．３ｍｓの間に音波が移動する距離は０．４５ｍであるので、任意の２つのノードに対してシンクノードとノード間の距離に対する相対的な差が０．５ｍ以上であれば、衝突が発生しないので、衝突の確率が非常に小さくなる。これは音波の遅い伝達速度が作り出す自然なランダムバックオフ（ｒａｎｄｏｍ  ｂａｃｋ  ｏｆｆ）効果を活用することを意味する。一般に、空気中で電磁波を利用する無線ネットワークでは、パケットの受信衝突を防止するためにランダムな時間遅延を与えるが、水中で音波を利用する無線通信ネットワークでは、音波の遅い伝達速度が自然にランダム時間遅延を誘発する原理を利用するのである。それにもかかわらず、シンクノードで初期化応答パケットに対する受信衝突が発生するおそれがあるが、このような初期化応答パケットの受信衝突が発生したノードにのみ選択的に初期化応答パケットの受信衝突回避を適用することが、本発明に対する初期化過程の最も重要な特徴である。
【０１６０】
最初に行われる初期化パケット放送及びこれに対するノードの初期化応答パケット受信過程を経ながら、シンクノードは、物理階層での信号の受信は行われたが、情報がまともに復元されなかった場合の発生有無から初期化応答パケットの受信衝突の発生有無を知ることができる。
【０１６１】
前記ステップ（Ｓ１０４０）で初期化応答パケットの受信に衝突が存在しなければ（Ｎ）、初期スケジューリング手続きに進入して次のステップ（Ｓ１０５０）へ移行する一方、初期化応答パケットの受信に衝突が発生した場合には（Ｙ）、シンクノードによって再初期化（ＲＩＲＰ）パケットが多数のノードに放送されて衝突回避による往復時間遅延取得手続きに進入する（Ｓ１２６０）。
【０１６２】
再初期化（ＲＩＲＰ）パケットは、シンクノードとノード間の往復時間遅延の取得が行われたノードに対するリストを含むようにして、再初期化パケットを受信したノードは、自分が再初期化パケットのリストにない場合にのみランダムバックオフ（ｂａｃｋ  ｏｆｆ）を介して再初期化応答パケットをシンクノードへ送信するようにする。ここで、ランダムバックオフとは、再初期化パケットを受信したノードが再初期化パケットを受信するや否や再初期化応答パケットを送信するのではなく、
【数３７０】
2019508000.tif 000372
長さを有する時間スロットの任意の整数倍だけ再初期化応答パケットの送信を先送りすることを意味する。すなわち、再初期化パケットを受信したノードは、再初期化パケットの受信が完了した後、下記数式１０４のように与えられる
【数３７１】
2019508000.tif 000373
時間だけ待機した後に再初期化応答パケットをシンクノードへ送信するようにする。
【０１６３】
【数３７２】
2019508000.tif 000374
【０１６４】
（式中、ｍはユーザーが指定する最大値（Ｍ）よりも小さい整数の中からランダムに選択される負数ではない整数であり、
【数３７３】
2019508000.tif 000375
は、好ましくは初期化応答パケット長の２倍以上となるようにする。）
【０１６５】
次に、ステップ（Ｓ１２７０）では、シンクノードによって第２設定時間
【数３７４】
2019508000.tif 000376
だけ再初期化応答パケットが受信される。再初期化応答パケットは、初期化応答パケットが含んでいる情報に加えて、さらにｍ値が含まれるようにする。
【０１６６】
つまり、シンクノードは、最初の初期化応答パケット受信の場合と同様に、再初期化パケット放送後に、下記数式１０５によって決定されたような第２設定時間
【数３７５】
2019508000.tif 000377
以内にすべてのノードから再初期化応答パケットの受信が完了する。
【０１６７】
【数３７６】
2019508000.tif 000378
【０１６８】
（式中、
【数３７７】
2019508000.tif 000379
は再初期化パケット長の時間換算値であり、
【数３７８】
2019508000.tif 000380
は再初期化応答パケット長の時間換算値である。）
【０１６９】
次いで、シンクノードが前記ステップ（Ｓ１２７０）で受信した再初期化応答パケットからシンクノードと多数のノード間の往復時間遅延
【数３７９】
2019508000.tif 000381
を計算する（Ｓ１２８０）。
【０１７０】
具体的には、シンクノードは、再初期化パケット送信時間
【数３８０】
2019508000.tif 000382
をシンクノード自身のローカルクロックから知ることができ、ノードＨから受信された再初期化応答パケットの受信時刻
【数３８１】
2019508000.tif 000383
もシンクノード自身のローカルクロックから知ることができる。したがって、シンクノードは、時間同期化なしにシンクノードとノードＨ間の往復時間遅延情報
【数３８２】
2019508000.tif 000384
を再初期化応答パケット受信時刻と再初期化パケット送信時刻との差から下記数式１０６のように取得することができる。
【０１７１】
【数３８３】
2019508000.tif 000385
【０１７２】
(式中、
【数３８４】
2019508000.tif 000386
はノードＨから受信された再初期化応答パケットの受信時刻であり、
【数３８５】
2019508000.tif 000387
は再初期化パケットの送信時刻である。)
【０１７３】
その後、シンクノードによって再初期化応答パケットの受信に衝突が存在するか否かを決定する（Ｓ１２９０）。
【０１７４】
前記ステップ（Ｓ１２９０）で再初期化応答パケットの受信に衝突が存在すれば（Ｙ）、前記ステップ（Ｓ１２６０）へ移行し、これに対し、前記ステップ（Ｓ１２９０）で再初期化応答パケットの受信に衝突が存在しなければ（Ｎ）、前記ステップ（Ｓ１０５０）へ移行する。
【０１７５】
つまり、再初期化応答パケットの受信衝突が発生しないときまで再初期化パケット放送を繰り返し行ってすべてのノードに対してシンクノードとノード間の往復時間遅延を取得するようにする。ただし、すべてのノードに対してシンクノードとノード間の往復時間遅延の取得が必ずしも必要ではない場合には、前記繰り返し回数に制限を置くことができる。
【０１７６】
前述のように初期化過程でシンクノードが往復時間遅延情報の取得を完了すると、シンクノードは、このように取得された往復時間遅延情報を用いて、シンクノードでノードのデータパケットの受信衝突が発生しないように初期スケジュールを計算し、シンクノードは、このスケジュール情報をビーコンパケット含むようにビーコンパケットを生成し、このビーコンパケットをすべてのノードに放送する。
【０１７７】
このため、シンクノードが、前記ステップ（Ｓ１０３０）で計算された往復時間遅延
【数３８６】
2019508000.tif 000388
を用いて往復時間遅延の小さい順にノードを整列する（Ｓ１０５０）。
【０１７８】
合計Ｋ個のノードがあれば、往復時間遅延がｋ番目に小さいノードを「ｋ番目のノード」と命名する。ｋ番目のノードの往復時間遅延を
【数３８７】
2019508000.tif 000389
と表示する。
【数３８８】
2019508000.tif 000390
は、数式１０３及び数式１０６を介して取得された往復時間遅延を小さい順に整列して得られる値である。
【数３８９】
2019508000.tif 000391
が取得された時刻を
【数３９０】
2019508000.tif 000392
と表示する。
【数３９１】
2019508000.tif 000393
は、
【数３９２】
2019508000.tif 000394
に相応する
【数３９３】
2019508000.tif 000395
または
【数３９４】
2019508000.tif 000396
値である。シンクノードが最初にビーコンパケットを放送する時刻を
【数３９５】
2019508000.tif 000397
と表示する。
【数３９６】
2019508000.tif 000398
はシンクノードのローカルクロックから当然に知ることが可能な値である。
【０１７９】
以後、シンクノードは、往復時間遅延の小さい順に、次のように、各ノードのスケジューリングを行う。スケジューリングとは、ノードがビーコンパケットを受信した後にデータパケットを送信するまで待機する時間であって、ｋ番目のノードの待機時間を
【数３９７】
2019508000.tif 000399
と表示する。
【０１８０】
まず、シンクノードによって変数ｋが１に設定され、１番目のノードの待機時間
【数３９８】
2019508000.tif 000400
が下記数式１０７のように「０」に設定される（Ｓ１０６０）。つまり、１番目のノードは、ビーコンパケットを受信するや否や待機時間なしに直ちにデータパケットを送信する。
【０１８１】
【数３９９】
2019508000.tif 000401
【０１８２】
そうすれば、シンクノードによって１番目のノードのデータパケットがシンクノードに受信され始める時刻の最大値
【数４００】
2019508000.tif 000402
が、下記数式１０８のように計算される（Ｓ１０７０）。
【０１８３】
【数４０１】
2019508000.tif 000403
【０１８４】
（式中、
【数４０２】
2019508000.tif 000404
はシンクノードによる最初のビーコンパケット放送時刻であり、
【数４０３】
2019508000.tif 000405
はビーコンパケット長の時間換算値であり、
【数４０４】
2019508000.tif 000406
は１番目のノードの往復時間遅延であり、
【数４０５】
2019508000.tif 000407
は１番目のノードのシンクノードとの往復時間遅延が取得された時点であり、
【数４０６】
2019508000.tif 000408
はシンクノードとノード間の最大相対速度である。］
【０１８５】
数式１０８は、１番目のノードのＲＴＴ取得時点から、１番目のノードがビーコンパケットの受信後にデータパケットを送信するまで１番目のノードの移動性により発生する１番目のノードの往復時間遅延の最大変動幅を考慮する方法である。１番目のノードのＲＴＴが取得された時点は
【数４０７】
2019508000.tif 000409
であるので、１番目のノードのＲＴＴが決定された時点は
【数４０８】
2019508000.tif 000410
であり、１番目のノードは、
【数４０９】
2019508000.tif 000411
時刻以前にはビーコンメッセージを必ず受信する。ｙって、１番目のノードのＲＴＴ決定時点から１番目のノードがデータパケットを伝送し始める時点まで、１番目のノードがシンクノードから最大相対速度Ｖで離れるとき、往復時間遅延は最大に増加するが、これは、数式１０８において、
【数４１０】
2019508000.tif 000412
と表現されている。
【０１８６】
したがって、１番目のノードのデータパケットがシンクノードに受信完了する時刻の最大値は、下記数式１０９のとおりである。すなわち、前記時刻の最大値に受信が終了する。
【０１８７】
【数４１１】
2019508000.tif 000413
【０１８８】
（式中、
【数４１２】
2019508000.tif 000414
は１番目のノードのデータパケット長を時間に換算した値である。］
【０１８９】
【数４１３】
2019508000.tif 000415
【数４１４】
2019508000.tif 000416
後に２番目のノードのデータパケットの受信が始まる。
【０１９０】
【数４１５】
2019508000.tif 000417
【０１９１】
（式中、
【数４１６】
2019508000.tif 000418
は２番目のノードのデータパケットがシンクノードに到着する時刻の最小値である。）
【０１９２】
したがって、下記数式１１１のように２番目のノードに時間遅延を付与すると、シンクノードで１番目のノードのデータパケットとの受信衝突を回避することができる。
【０１９３】
【数４１７】
2019508000.tif 000419
【０１９４】
（式中、
【数４１８】
2019508000.tif 000420
はＡ及びＢの両者から大きい値を選択する関数である。）
同様の方法で、Ｋ番目のノードの時間遅延が計算されるまで回帰的に各ノードの時間遅延を計算することができるが、具体的には、（ｋ−１）番目のノードのデータパケットがシンクノードに到着する時刻の最大値
【数４１９】
2019508000.tif 000421
は、下記数式１１２のように計算される。
【０１９５】
【数４２０】
2019508000.tif 000422
【０１９６】
ステップ（Ｓ１０８０）では、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断する。
【０１９７】
前記ステップ（Ｓ１０８０）で前記変数ｋが最後番目（Ｋ番目）よりも小さい場合（Ｙ）、前記変数ｋをｋ＋１に設定する（Ｓ１０９０）。
ステップ（Ｓ１１００）では、ｋ番目のノードのデータパケットがシンクノードに到着する時刻の最小値
【数４２１】
2019508000.tif 000423
が下記数式１１３のように計算される。
【０１９８】
【数４２２】
2019508000.tif 000424
【０１９９】
（式中、
【数４２３】
2019508000.tif 000425
はｋ番目のノードの往復時間遅延であり、
【数４２４】
2019508000.tif 000426
は
【数４２５】
2019508000.tif 000427
が取得された時刻である。）
【０２００】
ステップ（Ｓ１１１０）では、シンクノードによってｋ番目のノードの待機時間
【数４２６】
2019508000.tif 000428
が下記数式１１４のように計算される。
【０２０１】
【数４２７】
2019508000.tif 000429
【０２０２】
このように、ｋ番目のノードに待機時間
【数４２８】
2019508000.tif 000430
を付与すると、（ｋ−１）番目のノードのデータパケットとｋ番目のノードのデータパケットがシンクノードで受信衝突を起こすことを回避することができる。
【０２０３】
ステップ（Ｓ１１２０）では、シンクノードが、ｋ番目のノードのデータパケットがシンクノードに到着する時刻の最大値
【数４２９】
2019508000.tif 000431
を前記数式１１２のように計算した後、前記ステップ（Ｓ１０８０）へ移行する。
【０２０４】
一方、前記ステップ（Ｓ１０８０）で、前記変数ｋが最後番目（Ｋ番目）より小さくなければ（Ｎ）、すなわち、すべてのＫ個のノードに対してスケジュール計算が完了すると、ステップ（Ｓ１１３０）へ移行する。
【０２０５】
ステップ（Ｓ１１３０）では、シンクノードによって１番目のビーコンパケットが第３設定時刻
【数４３０】
2019508000.tif 000432
にノードへ放送される。
【０２０６】
ステップ（Ｓ１１４０）では、シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または、前記ステップ（Ｓ１１３０）による１番目のビーコンパケットの放送後に第４設定時間
【数４３１】
2019508000.tif 000433
を待機し、次の正規過程に進入する。
【０２０７】
正規過程
図３は本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。初期化過程でシンクノードがビーコンパケットを放送し、すべてのノードからデータパケットの受信が完了する瞬間までを１番目のサイクルと定義すれば、正規過程は２番目のサイクルからである。ここで、ｎ番目のサイクルとは、図３に示すように、シンクノードがｎ番目のビーコンパケットを放送し、すべてのノードからデータパケットの受信が完了する瞬間までを意味する。ｎ番目のサイクルのビーコンパケットが放送される時刻を
【数４３２】
2019508000.tif 000434
と表記する。ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻を
【数４３３】
2019508000.tif 000435
と表記する。ｎ番目のサイクルでｋ番目のノードに付与される時間遅延を
【数４３４】
2019508000.tif 000436
と表記する。
【０２０８】
ｎ番目のサイクルが終了すると、シンクノードによってシンクノードとｋ番目のノード間の往復時間遅延
【数４３５】
2019508000.tif 000437
が下記数式１１５のように計算される（Ｓ１１５０）。
【０２０９】
【数４３６】
2019508000.tif 000438
【０２１０】
（式中、
【数４３７】
2019508000.tif 000439
はｎ番目のサイクルのビーコンパケットが放送される時刻であり、
【数４３８】
2019508000.tif 000440
はｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻であり、
【数４３９】
2019508000.tif 000441
はｎ番目のサイクルでｋ番目のノードに付与される時間遅延であり、
【数４４０】
2019508000.tif 000442
はｎ番目のサイクルにおけるビーコン長の時間換算値である。）
【０２１１】
ステップ（Ｓ１１５２）では、シンクノードが前記ステップ（Ｓ１１５０）で計算された往復時間遅延
【数４４１】
2019508000.tif 000443
を用いて往復時間遅延の小さい順にノードを整列する。
ステップ（Ｓ１１５４）では、シンクノードによって１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
【数４４２】
2019508000.tif 000444
が下記数式１１６によって計算される。
【０２１２】
【数４４３】
2019508000.tif 000445
【０２１３】
（式中、
【数４４４】
2019508000.tif 000446
は（ｎ−１）番目のサイクルにおけるデータパケットの受信開始時刻である。）
【０２１４】
シンクノードは、（ｎ−１）番目のサイクルにおけるビーコンパケット送信時刻、及び各ノードからのデータパケット受信時刻を用いてシンクノードと各ノード間の往復時間遅延値を得ることができるが、ｎ番目のサイクルで各ノードがデータパケットを送信する時点におけるシンクノードと各ノード間の往復時間遅延はノードの移動性により正確に知ることが難しい。本発明では、各ノードの（ｎ−１）番目のサイクルにおけるデータパケット受信開始時刻とｎ番目のサイクルにおけるデータパケット受信時刻との差を下記数式１１７のように近似し、
【数４４５】
2019508000.tif 000447
１サイクルの間に変化することが可能なシンクノードと各ノード間の往復時間遅延の変動幅を前記数式１１６のように計算する。数式１１７において、ｎ番目のスケジュール情報は、ｎ番目のサイクルでビーコンパケットに含ませて放送するので、ｎ番目のスケジュールを計算して導出する瞬間には
【数４４６】
2019508000.tif 000448
値は知ることができない値であることに留意すべきである。
【０２１５】
図４は本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。ｎ番目のサイクルで（ｋ−１）番目のノードのデータパケットはｎ番目のビーコンパケット放送時刻を基準に
【数４４７】
2019508000.tif 000449
と
【数４４８】
2019508000.tif 000450
との間に受信完了する。したがって、本発明では、
【数４４９】
2019508000.tif 000451
が
【数４５０】
2019508000.tif 000452
よりも大きくなるようにして、ｎ番目のサイクルで（ｋ−１）番目のノードのデータパケットとｋ番目のノードのデータパケットがシンクノードで受信衝突を起こさないようにしなければならない。
【０２１６】
ステップ（Ｓ１１６０）では、シンクノードが変数ｋを１に設定し、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数４５１】
2019508000.tif 000453
を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値
【数４５２】
2019508000.tif 000454
を下記数式１１８のように計算する。
【０２１７】
【数４５３】
2019508000.tif 000455
【０２１８】
ステップ（Ｓ１１７０）では、シンクノードが、変数
【数４５４】
2019508000.tif 000456
が
【数４５５】
2019508000.tif 000457
より小さいか否かを決定し、変数
【数４５６】
2019508000.tif 000458
が
【数４５７】
2019508000.tif 000459
より小さければ（Ｙ）、
【数４５８】
2019508000.tif 000460
を「１」だけ増加させ（Ｓ１１８０）、次のステップ（Ｓ１１９０）を行う一方で、
【数４５９】
2019508000.tif 000461
が
【数４６０】
2019508000.tif 000462
以上であれば（Ｎ）、下記ステップ（Ｓ１２２０）を行う。
【０２１９】
ステップ（Ｓ１１９０）では、シンクノードが、ｎ番目のサイクルでノードのデータパケットが受信され始める時刻の最小値
【数４６１】
2019508000.tif 000463
を下記数式１１９のように計算する。
【０２２０】
【数４６２】
2019508000.tif 000464
【０２２１】
ステップ（Ｓ１２００）では、シンクノードがｎ番目のサイクルでノードに付与される時間遅延
【数４６３】
2019508000.tif 000465
を下記数式１２０のように計算する。
【０２２２】
【数４６４】
2019508000.tif 000466
【０２２３】
ステップ（Ｓ１２１０）では、シンクノードが、ｎ番目のサイクルでノードのデータパケットが受信され始める時刻の最大値
【数４６５】
2019508000.tif 000467
を下記数式１２１のように計算した後、前記ステップ（Ｓ１１７０）へ移行する。
【０２２４】
【数４６６】
2019508000.tif 000468
【０２２５】
ステップ（Ｓ１２２０）では、シンクノードによってビーコンパケット放送が行われるか否かが決定される。
【０２２６】
前記ステップ（Ｓ１２２０）でビーコンパケット放送が行われなければ（Ｎ）、スケジューリング過程を終了する。
【０２２７】
一方、前記ステップ（Ｓ１２２０）でシンクノードによってビーコンパケット放送が決定されれば（Ｙ）、シンクノードによってｎ番目のサイクルのビーコンパケットが放送される時刻
【数４６７】
2019508000.tif 000469
にビーコンパケットが多数のノードに放送される（Ｓ１２３０）。
【０２２８】
続いて、シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または前記ｎ番目のサイクルで最後番目のノードのデータパケットが受信され始める時刻の最大値
【数４６８】
2019508000.tif 000470
を待機し（Ｓ１２４０）、シンクノードによってサイクルが１だけ増加した後（Ｓ１２５０）、前記ステップ（Ｓ１１５０）へ移行する。
【０２２９】
上述のように構成された本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードから多数のノードへ初期化パケットを放送し、シンクノードが多数のノードから第１設定時間
【数４６９】
2019508000.tif 000471
の間に初期化応答パケットを受信し、前記シンクノードが受信した初期化応答パケットからシンクノードと多数のノード間の往復時間遅延
【数４７０】
2019508000.tif 000472
を計算し、シンクノードによって初期化応答パケットの受信に衝突が存在するか否かを決定し、初期化応答パケットの受信に衝突が存在しなければ、シンクノードが計算された往復時間遅延
【数４７１】
2019508000.tif 000473
を用いて往復時間遅延の小さい順にノードを整列し、シンクノードによって変数ｋを１に設定し、１番目のノードの待機時間
【数４７２】
2019508000.tif 000474
を「０」に設定し、シンクノードによって１番目のノードのデータパケットがシンクノードに受信され始める時刻の最大値
【数４７３】
2019508000.tif 000475
を計算し、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し、変数ｋが最後番目（Ｋ番目）より小さければ、変数ｋをｋ＋１に設定し、シンクノードによってｋ番目のノードのデータパケットが前記シンクノードに到着する時刻の最小値
【数４７４】
2019508000.tif 000476
を計算し、シンクノードによってｋ番目のノードの待機時間
【数４７５】
2019508000.tif 000477
を計算し、シンクノードによってｋ番目のノードのデータパケットがシンクノードに到着する時刻の最大値
【数４７６】
2019508000.tif 000478
を計算した後、変数ｋが最後番目（Ｋ番目）より小さくなければ、シンクノードによって１番目のビーコンパケットが第３設定時刻
【数４７７】
2019508000.tif 000479
に多数のノードに放送され、シンクノードが最後番目（Ｋ番目）のノードのデータパケットを受信した後、または１番目のビーコンパケットの放送後に第４設定時間
【数４７８】
2019508000.tif 000480
を待機し、シンクノードによってシンクノードとｋ番目のノード間の往復時間遅延
【数４７９】
2019508000.tif 000481
を計算し、シンクノードが計算された往復時間遅延
【数４８０】
2019508000.tif 000482
を用いて往復時間遅延の小さい順にノードを整列し、シンクノードによって１サイクルの間に変化することが可能なノードの往復時間遅延変動幅
【数４８１】
2019508000.tif 000483
を計算し、変数ｋを１に設定し、シンクノードがｎ番目のサイクルで１番目のノードに付与される時間遅延
【数４８２】
2019508000.tif 000484
を「０」に設定し、ｎ番目のサイクルで１番目のノードのデータパケットが受信され始める時刻の最大値
【数４８３】
2019508000.tif 000485
を計算し、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し、変数ｋが最後番目（Ｋ番目）より小さければ、変数ｋをｋ＋１に設定し、シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最小値
【数４８４】
2019508000.tif 000486
を計算し、シンクノードがｎ番目のサイクルでｋ番目のノードに付与される時間遅延
【数４８５】
2019508000.tif 000487
を計算し、シンクノードが、ｎ番目のサイクルでｋ番目のノードのデータパケットが受信され始める時刻の最大値
【数４８６】
2019508000.tif 000488
を計算した後、変数ｋが最後番目（Ｋ番目）より小くなければ、シンクノードによってビーコンパケット放送が行われるか否かが決定され、ビーコンパケット放送が行われなければ終了するように構成されることにより、水中で移動ノードの航法情報とは無関係に動作し、時間同期化が不要なので、時間同期化のための別途のパケット交換が必要ないから、ネットワークの歩留まりを向上させることができ、スケジュール情報が絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作し、各サイクル終了時点でシンクノードとノード間の往復時間遅延情報に対する正確な値が測定されるので、スケジュール情報は、時間が経過するにつれて誤差が累積されないため、周期的な再初期化が必要ない。
【０２３０】
［第２実施形態］
図５は本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図であって、シンクノードがノードの伝送スケジュールを含んでいるビーコンパケットを放送し、シンクノードのビーコンパケットを受信したシンクノード以外のノードがビーコンパケットに含まれている各ノードの伝送スケジュールに従ってデータパケットをシンクノードへ伝送する。シンクノード以外のノードは「ノード」と略記することがある。本発明では、水中で音波を利用して通信が行われる場合を考慮し、シンクノードとｋ番目のノード間の最大相対速度
【数４８７】
2019508000.tif 000489
、水中での最小音波伝達速度
【数４８８】
2019508000.tif 000490
、シンクノードを除くノードの総数
【数４８９】
2019508000.tif 000491
は知っていると仮定する。
【０２３１】
図６は本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
【０２３２】
本発明において、ｎ番目のサイクルとは、図６に示すように、シンクノードがｎ番目ビーコンパケットを放送する時刻から、すべてのノードからデータパケットの受信が完了した後に（ｎ＋１）番目のビーコンパケットを放送し始める時刻までの区間を意味する。
【０２３３】
ｎ番目のサイクルのビーコンパケットが放送される時刻を
【数４９０】
2019508000.tif 000492
と表記する。すると、
【数４９１】
2019508000.tif 000493
である（式中、
【数４９２】
2019508000.tif 000494
はｎ番目のサイクルの持続時間である。）。ｎ番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻を
【数４９３】
2019508000.tif 000495
と表記する。
【０２３４】
本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法は、各ノードがビーコンパケット受信時刻からどれほどの時間遅延の後にデータパケットを送信すべきかについての情報をシンクノードがビーコンパケットに含ませて送る。
ｎ番目のサイクルでｋ番目のノードのビーコン受信後にデータパケットを送信するときまでの待機時間を
【数４９４】
2019508000.tif 000496
と表記する。
【数４９５】
2019508000.tif 000497
でｎ番目のサイクルであることを明示する必要はないが、本発明を説明する上での明確性のために、
【数４９６】
2019508000.tif 000498
にｎ番目のサイクルを明示する添字を使用する。ノードの移動性により、ノードの往復時間遅延はサイクルごとに変化するが、本発明では、このように変化する往復時間遅延を過去の２サイクルの往復時間遅延情報を用いて推定し、シンクノードでノードのデータパケットの受信衝突が発生しないように
【数４９７】
2019508000.tif 000499
を定める。
【０２３５】
本発明では、シンクノードと各ノード間の最初の往復時間遅延
【数４９８】
2019508000.tif 000500
、及びシンクノードと各ノード間の最初の往復時間遅延
【数４９９】
2019508000.tif 000501
が取得された時間
【数５００】
2019508000.tif 000502
は知っていると仮定する。
【数５０１】
2019508000.tif 000503
及び
【数５０２】
2019508000.tif 000504
を取得することができるさまざまな方法が存在し、いかなる方法を使用しても、本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法は、サイクル数が増加すればするほど、
【数５０３】
2019508000.tif 000505
及び
【数５０４】
2019508000.tif 000506
とは無関係に正常状態に至るので、
【数５０５】
2019508000.tif 000507
及び
【数５０６】
2019508000.tif 000508
を取得するために使用する方法による本発明の時分割多重アクセス方法の性能変化は非常に小さい。
【０２３６】
以下、上述のように構成されたネットワークトポロジーで行われる、本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法について説明する。
図７ａ及び図７ｂは本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作のフローチャートであって、ここで、Ｓはステップ（Ｓｔｅｐ）を意味する。
【０２３７】
まず、シンクノードは、
【数５０７】
2019508000.tif 000509
及び
【数５０８】
2019508000.tif 000510
を用いて１番目のサイクルのスケジュールである
【数５０９】
2019508000.tif 000511
を決めるためには、まず、下記［数式２０１］のように初期化過程を行う（Ｓ２０１０）。
【０２３８】
【数５１０】
2019508000.tif 000512
【０２３９】
（式中、
【数５１１】
2019508000.tif 000513
は
【数５１２】
2019508000.tif 000514
よりも小さいか同じ自然数である。
【数５１３】
2019508000.tif 000515
は、ｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数５１４】
2019508000.tif 000516
値を知っているので、すべて１に設定する。
【数５１５】
2019508000.tif 000517
はｎ番目のサイクルで、（ｎ−）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数５１６】
2019508000.tif 000518
より過去に取得された往復時間遅延情報は最初に存在しないので、０にする。
【数５１７】
2019508000.tif 000519
は、直近に取得されたｋ番目のノードの往復時間遅延であり、現在の状態で
【数５１８】
2019508000.tif 000520
が直近に取得された往復時間遅延（すなわち、シンクノードと各ノード間の最初の往復時間遅延）であるので、
【数５１９】
2019508000.tif 000521
に設定する。
【数５２０】
2019508000.tif 000522
は、
【数５２１】
2019508000.tif 000523
が得られたサイクルであり、０に設定する。
【数５２２】
2019508000.tif 000524
はｎ番目のサイクルの持続時間であり、１番目のサイクル前のサイクル持続時間は知ることができないので、ユーザーが適正な
【数５２３】
2019508000.tif 000525
値を定めなければならないが、ここでは、その値を
【数５２４】
2019508000.tif 000526
と表示した。
【数５２５】
2019508000.tif 000527
は経験的に知っている平均的な
【数５２６】
2019508000.tif 000528
値にするか、或いは、サイクル持続時間は全体データパケット長の和とノードの往復時間遅延の最小値との和よりは大きいので、下記数式２０２のように推定されて定められる。）
【０２４０】
【数５２７】
2019508000.tif 000529
【０２４１】
（式中、
【数５２８】
2019508000.tif 000530
は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【０２４２】
次いで、シンクノードは、次の手続きでｎ番目のサイクルでｋ番目のノードのビーコン受信後にデータパケット送信時までの待機時間
【数５２９】
2019508000.tif 000531
を計算してサイクル単位で各ノードのデータパケットを受信する（Ｓ２０２０乃至Ｓ２１４０）。
【０２４３】
［ステップＳ２０２０］
シンクノードがデータパケットの受信順序を決定した後にｎ番目のサイクルで１番目のノードに付与される時間遅延
【数５３０】
2019508000.tif 000532
を０に設定する。
【０２４４】
さらに詳細に説明すると、
【数５３１】
2019508000.tif 000533
の小さい順に整列した後、
【数５３２】
2019508000.tif 000534
とし、
【数５３３】
2019508000.tif 000535
とする。ｋ番目のノードとは、
【数５３４】
2019508000.tif 000536
がｋ番目に小さいノードを意味する。ｎ番目のサイクルでｋ番目のノードのデータパケットは、シンクノードにｋ番目に受信される。すなわち、ここで整列された順序は、シンクノードにデータパケットが到着する順序である。整列する方法としてさらに考慮できる方法は、
【数５３５】
2019508000.tif 000537
値が１であるノードを、
【数５３６】
2019508000.tif 000538
の小さい順に整列し、次に
【数５３７】
2019508000.tif 000539
値が０であるノードのうち、
【数５３８】
2019508000.tif 000540
値が１であるノードを、
【数５３９】
2019508000.tif 000541
の小さい順に整列し、次に
【数５４０】
2019508000.tif 000542
及び
【数５４１】
2019508000.tif 000543
値が全て０であるノードを
【数５４２】
2019508000.tif 000544
の小さい順に整列するようにすることにより、直近に往復時間遅延が取得されたノードに優先順位を付与する方法を使用することもできる。これ以外にも、応用分野に応じて、優先順位ベースの様々な整列方法が存在することができる。
【０２４５】
［ステップＳ２０３０］
シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数５４３】
2019508000.tif 000545
を推定し、１番目のノードのデータパケット受信完了時点
【数５４４】
2019508000.tif 000546
を計算する。
【０２４６】
さらに詳細には、もし
【数５４５】
2019508000.tif 000547
であれば、つまり、直近の２サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合には、下記［数式２０３］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数５４６】
2019508000.tif 000548
を推定し、１番目のノードのデータパケット受信完了時点
【数５４７】
2019508000.tif 000549
を計算する。
【０２４７】
【数５４８】
2019508000.tif 000550
【０２４８】
（式中、
【数５４９】
2019508000.tif 000551
はガード時間であり、
【数５５０】
2019508000.tif 000552
はｎ−１番目のサイクルで取得された１番目のノードの往復時間遅延であり、
【数５５１】
2019508000.tif 000553
はｎ番目のサイクルでビーコンパケット長を時間に換算した値であり、
【数５５２】
2019508000.tif 000554
はｎ−１番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻であり、
【数５５３】
2019508000.tif 000555
は下記数式２０４のとおりである。）
【０２４９】
【数５５４】
2019508000.tif 000556
【０２５０】
（式中、
【数５５５】
2019508000.tif 000557
は、ｎ−２番目のサイクルで取得された１番目のノードの往復時間遅延であり、
【数５５６】
2019508000.tif 000558
は、ｎ−２番目のサイクルで１番目のノードのデータパケットがシンクノードに受信され始める時刻である。）
【０２５１】
もし、
【数５５７】
2019508000.tif 000559
値が２よりも小さい場合、すなわち、直近の２サイクルの間に１番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２０５］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数５５８】
2019508000.tif 000560
を推定し、１番目のノードのデータパケット受信完了時点
【数５５９】
2019508000.tif 000561
を計算する。
【０２５２】
【数５６０】
2019508000.tif 000562
【０２５３】
（式中、
【数５６１】
2019508000.tif 000563
は往復時間遅延の最大値であり、
【数５６２】
2019508000.tif 000564
は直近に取得された１番目のノードの往復時間遅延であり、
【数５６３】
2019508000.tif 000565
はシンクノードとｋ番目のノード間の最大相対速度であり、
【数５６４】
2019508000.tif 000566
はｎ−１番目のサイクルの持続時間であり、
【数５６５】
2019508000.tif 000567
は１番目のノードの往復時間遅延が取得された直近のサイクルであり、
【数５６６】
2019508000.tif 000568
は水中での最小音波伝達速度である。）
前記［数式２０３］は、次の連立方程式である［数式２０６］を解いて得られる。
【０２５４】
【数５６７】
2019508000.tif 000569
【０２５５】
（式中、
【数５６８】
2019508000.tif 000570
はｎ番目のサイクルで１番目のノードのデータパケット受信時刻
【数５６９】
2019508000.tif 000571
に対する推定値である。）
【０２５６】
前記［数式２０６］において、一番目の式は２点
【数５７０】
2019508000.tif 000572
及び
【数５７１】
2019508000.tif 000573
）を通る直線で１番目のノードのデータパケット受信時刻と往復時間遅延との関係を近似し、
【数５７２】
2019508000.tif 000574
で往復時間遅延
【数５７３】
2019508000.tif 000575
を計算したものである。一方、
【数５７４】
2019508000.tif 000576
はｎ番目のサイクルのスケジュール情報を計算する時点で正確に知ることができないが、１番目のノードの往復時間遅延とデータパケット受信時刻は、前記［数式２０６］における２番目の式のような関係を持つので、前記［数式２０６］を解くと、［数式２０３］のように
【数５７５】
2019508000.tif 000577
を計算することができる。［数式２０３］は、
【数５７６】
2019508000.tif 000578
であれば計算が不可能であるが、この場合は、１番目のノードとシンクノードの相対速度が音波の速度と同じ場合に該当するので、現実的に発生しない。
【０２５７】
（ｎ−１）番目のサイクル及び（ｎ−２）番目のサイクルのうち、少なくとも１サイクルで１番目のノードの往復時間遅延が取得されなければ、［数式２０６］のように１番目のノードの往復時間遅延を求めることができないので、［数式２０５］のように１番目のノードの往復時間遅延が取得された直近の時点からできる限り最大変動幅を用いて往復時間遅延を推定するようにして衝突を回避する。［数式２０５］において、
【数５７７】
2019508000.tif 000579
は１番目のノードの往復時間遅延が取得された直近のサイクルであるので、
【数５７８】
2019508000.tif 000580
は往復時間遅延の取得後に費やされた時間を意味し、このとき、平均的なサイクル持続時間を、直近のサイクルである（ｎ−１）番目のサイクル持続時間に近似すると、
【数５７９】
2019508000.tif 000581
は直近に往復時間遅延が取得された後にｎ番目のサイクルでの往復時間遅延が持つことが可能な最大変動幅になる。したがって、
【数５８０】
2019508000.tif 000582
は、ｎ番目のサイクルで１番目のノードの最大往復時間遅延となり、この値が
【数５８１】
2019508000.tif 000583
を超えることができないので、［数式２０５］のように１番目のノードの往復時間遅延を計算する。（ｎ−１）番目のサイクル及び（ｎ−２）番目のサイクルのうちの少なくとも１サイクルで１番目のノードの往復時間遅延が取得されなかったというのは、物理階層が完璧であれば、１番目のノードの移動性が急に変わって他のノードのパケットとの衝突を発生したものと認知することができる。よって、過去の往復時間遅延情報からｎ番目のサイクルにおける往復時間遅延を推定することは好ましくないことに留意すべきである。また、このように計算された
【数５８２】
2019508000.tif 000584
は、
【数５８３】
2019508000.tif 000585
が持つことが可能な最大の値なので、
【数５８４】
2019508000.tif 000586
を計算するにあたり、［数式２０５］では、［数式２０３］とは異なり、ガード時間を含まない。
【０２５８】
［ステップＳ２０４０］
シンクノードによって変数ｋが最後番目（Ｋ番目）より小さいか否かを判断する。
【０２５９】
［ステップＳ２０５０］
前記ステップ（Ｓ２０４０）で前記変数ｋが最後番目（Ｋ番目）より小さければ（Ｙ）、シンクノードが前記変数ｋをｋ＋１に設定する。
【０２６０】
［ステップＳ２０６０］
シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数５８５】
2019508000.tif 000587
を推定する。
【０２６１】
さらに詳細には、もし
【数５８６】
2019508000.tif 000588
であれば、すなわち、直近の２サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合には、下記［数式２０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数５８７】
2019508000.tif 000589
を推定する。
【０２６２】
【数５８８】
2019508000.tif 000590
【０２６３】
（式中、
【数５８９】
2019508000.tif 000591
はｎ−１番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、
【数５９０】
2019508000.tif 000592
はｋ−１番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値であり、
【数５９１】
2019508000.tif 000593
はｎ−１番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻であり、
【数５９２】
2019508000.tif 000594
は下記数式２１１のとおりである。）
【０２６４】
【数５９３】
2019508000.tif 000595
【０２６５】
（式中、
【数５９４】
2019508000.tif 000596
はｎ−２番目のサイクルで取得されたｋ番目のノードの往復時間遅延であり、
【数５９５】
2019508000.tif 000597
はｎ−２番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻である。）
【０２６６】
前記［数式２０７］は、２点
【数５９６】
2019508000.tif 000598
及び
【数５９７】
2019508000.tif 000599
を通る直線でｋ番目のノードのデータパケット受信時刻と往復時間遅延との関係を近似し、直前のデータパケットである（ｋ−１）番目のノードのデータパケットの受信が完了する時刻である
【数５９８】
2019508000.tif 000600
時刻にｋ番目のデータパケットが受信されるときに往復時間遅延
【数５９９】
2019508000.tif 000601
を計算したものである。したがって、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延
【数６００】
2019508000.tif 000602
を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻
【数６０１】
2019508000.tif 000603
は、下記［数式２０８］のように計算される。
【０２６７】
【数６０２】
2019508000.tif 000604
【０２６８】
このとき、もし
【数６０３】
2019508000.tif 000605
であれば、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信しても、（ｋ−１）番目のノードのデータパケットの受信が完了してから、
【数６０４】
2019508000.tif 000606
だけの時間が経過した後にｋ番目のノードのデータパケットの受信が始まるので、前記［数式２０７］によって推定した
【数６０５】
2019508000.tif 000607
時刻でのｋ番目のノードの往復時間遅延は、実際のｋ番目のノードのデータパケットが到着する時点での往復時間遅延推定値として適切ではない。したがって、前記［数式２０６］を解いて前記［数式２０３］のように１番目のノードの往復時間遅延を推定した方式でｋ番目のノードの往復時間遅延を推定しなければならない。したがって、
【数６０６】
2019508000.tif 000608
の場合には、次のように［数式２０９］を解いて下記［数式２１０］のようにｋ番目のノードの往復時間遅延を推定する。前記［数式２１０］において、前記
【数６０７】
2019508000.tif 000609
は前記［数式２１１］のとおりである。
【０２６９】
【数６０８】
2019508000.tif 000610
【０２７０】
もし
【数６０９】
2019508000.tif 000611
値が２より小さい場合、すなわち、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、下記［数式２１２］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数６１０】
2019508000.tif 000612
を推定する。
【０２７１】
【数６１１】
2019508000.tif 000613
【０２７２】
（式中、
【数６１２】
2019508000.tif 000614
は、
【数６１３】
2019508000.tif 000615
が得られたサイクルである。）
【０２７３】
前記［数式２１２］は、［数式２０５］とは異なるが、これは、連続するデータパケットの衝突を回避するためには以前のデータパケットの終了時刻は遅く推定される方向にしなければならず、次のデータパケットの受信時刻は速く推定される方向にしなければならないからである。
【０２７４】
［ステップＳ２０７０］
シンクノードが、前記ステップ（Ｓ２０６０）で推定されたｋ番目のノードの往復時間遅延
【数６１４】
2019508000.tif 000616
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数６１５】
2019508000.tif 000617
を下記［数式２１３］のように計算する。
【０２７５】
【数６１６】
2019508000.tif 000618
【０２７６】
［ステップＳ２０８０］
シンクノードが、前記ステップ（Ｓ２０７０）で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数６１７】
2019508000.tif 000619
を用いて、ｋ番目のノードの待機時間
【数６１８】
2019508000.tif 000620
を下記［数式２１４］のように計算する。
【０２７７】
【数６１９】
2019508000.tif 000621
【０２７８】
［ステップＳ２０９０］
シンクノードが、前記ステップ（Ｓ２０７０）で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数６２０】
2019508000.tif 000622
と、前記ステップ（Ｓ２０８０）で計算されたｋ番目のノードの待機時間
【数６２１】
2019508000.tif 000623
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数６２２】
2019508000.tif 000624
を計算した後、前記ステップ（Ｓ２０４０）へ移行する。
【０２７９】
さらに詳細には、もし
【数６２３】
2019508000.tif 000625
であれば、すなわち、直近の２サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数６２４】
2019508000.tif 000626
は、下記［数式２１５］のように計算される。
【０２８０】
【数６２５】
2019508000.tif 000627
【０２８１】
（式中、
【数６２６】
2019508000.tif 000628
はｎ番目ののサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【０２８２】
もし、
【数６２７】
2019508000.tif 000629
値が２より小さければ、すなわち、直近の２サイクルの間にｋ番目のノードの往復時間遅延が１回以上成功的に取得されなかった場合には、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数６２８】
2019508000.tif 000630
は、下記［数式２１６］のように計算される。
【０２８３】
【数６２９】
2019508000.tif 000631
【０２８４】
ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数６３０】
2019508000.tif 000632
の計算が完了すると、前記ステップ（Ｓ２０４０）へ移行する。
【０２８５】
［ステップＳ２１００］
前記ステップ（Ｓ２０４０）で変数ｋが最後番目（Ｋ番目）より小さくなければ（Ｎ）、シンクノードがビーコンパケットの放送有無を判断してサイクルの進行如何を決定する。
【０２８６】
このステップ（Ｓ２１００）でビーコンパケットが放送されないためサイクルが進行しない場合（Ｎ）には、すべての手続きを終了する。
【０２８７】
［ステップＳ２１１０］
前記ステップ（Ｓ２１００）でビーコンパケットが放送されてサイクルが継続して進行する場合（Ｙ）には、シンクノードは、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻
【数６３１】
2019508000.tif 000633
にビーコンパケットを放送する。
【０２８８】
［ステップＳ２１２０］
Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値
【数６３２】
2019508000.tif 000634
が超過する。
【０２８９】
［ステップＳ２１３０］
前記ステップ（Ｓ２１２０）が行われた後、シンクノードは、ｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数６３３】
2019508000.tif 000635
を計算し、往復時間遅延取得有効性値
【数６３４】
2019508000.tif 000636
及び直近に取得された往復時間遅延関連情報
【数６３５】
2019508000.tif 000637
を更新する。
【０２９０】
より詳細には、往復時間遅延取得有効性値
【数６３６】
2019508000.tif 000638
を更新するために、下記［数式２１７］のようにすべてのノードに対して往復時間遅延取得有効性値
【数６３７】
2019508000.tif 000639
を更新し、もしｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式２１８］のようにする。
【０２９１】
【数６３８】
2019508000.tif 000640
【０２９２】
もしｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式２１９］のようにする。
【０２９３】
【数６３９】
2019508000.tif 000641
【０２９４】
直近に取得された往復時間遅延関連情報
【数６４０】
2019508000.tif 000642
は、下記［数式２２０］のように更新する。
【０２９５】
【数６４１】
2019508000.tif 000643
【０２９６】
また、往復時間遅延取得有効性値
【数６４２】
2019508000.tif 000644
が１である場合には、下記［数式２２１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数６４３】
2019508000.tif 000645
を計算し、直近に取得された往復時間遅延関連情報
【数６４４】
2019508000.tif 000646
を更新する。
【０２９７】
【数６４５】
2019508000.tif 000647
【０２９８】
［ステップＳ２１４０］
シンクノードがｎを１だけ増加させた後、（ｎ＋１）番目のサイクルのための
【数６４６】
2019508000.tif 000648
計算のために、前記ステップ（Ｓ２０２０）へ移行する。
【０２９９】
前述のように構成された本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードが初期化過程を行い；シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数６４７】
2019508000.tif 000649
を０に設定し；シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数６４８】
2019508000.tif 000650
を推定し、１番目のノードのデータパケット受信完了時点
【数６４９】
2019508000.tif 000651
を計算し；シンクノードによって変数ｋが最後番目（Ｋ番目）より小さいか否かを判断し；前記判断で変数ｋが最後番目（Ｋ番目）より小さければ、シンクノードが前記変数ｋをｋ＋１に設定し、シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数６５０】
2019508000.tif 000652
を推定し；シンクノードが、前記推定されたｋ番目のノードの往復時間遅延
【数６５１】
2019508000.tif 000653
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数６５２】
2019508000.tif 000654
を計算し；シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数６５３】
2019508000.tif 000655
を用いて、ｋ番目のノードの待機時間
【数６５４】
2019508000.tif 000656
を計算し；及び、シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数６５５】
2019508000.tif 000657
と前記計算されたｋ番目のノードの待機時間
【数６５６】
2019508000.tif 000658
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数６５７】
2019508000.tif 000659
を計算した後、前記判断過程へ移行するように構成されることにより：
すなわち、水中音響無線移動ネットワークなどのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、多数のノードがシンクノードへデータパケットを時分割多重アクセス方式で伝送しようとするとき、ノードの移動性による往復時間遅延をサイクル単位で追跡してシンクノードがノードからのデータパケットを受信する上で遊休時間を最小化することにより、チャンネル使用効率の向上によるネットワークの効率が大幅に向上することができる。特に、ノード数が増加すればするほど、ネットワーク効率の向上程度はさらに増加する。本発明に係る水中無線移動ネットワークのためのスケジューリング方法は、絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作する。したがって、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能である。
【０３００】
また、往復時間遅延情報に対する正確な値がサイクルごとに得られるので、誤差が累積されないため周期的な再初期化が必要ない。
【０３０１】
［第３実施形態］
図８は本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図であって、シンクノードが、ノードの伝送スケジュールを含んでいるビーコンパケットを放送し、シンクノードのビーコンパケットを受信したシンクノード以外のノードが、ビーコンパケットに含まれている各ノードの伝送スケジュールに従ってデータパケットをシンクノードへ伝送する。シンクノード以外のノードは「ノード」と略記することがある。本発明では、水中で超音波を利用して通信が行われる場合を考慮し、シンクノードとｋ番目のノード間の最大相対速度
【数６５８】
2019508000.tif 000660
、水中での音波伝達速度の最小値
【数６５９】
2019508000.tif 000661
、シンクノードを除くノードの総数
【数６６０】
2019508000.tif 000662
は知っていると仮定する。
【０３０２】
図９は本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
【０３０３】
本発明において、ｎ番目のサイクルとは、図９に示すように、シンクノードがｎ番目のビーコンパケットを放送する時刻から、すべてのノードからデータパケットの受信が完了した後に（ｎ＋１）番目のビーコンパケットを放送し始める時刻までの区間を意味する。
【０３０４】
ｎ番目のサイクルのビーコンパケットが放送される時刻を
【数６６１】
2019508000.tif 000663
と表記する。そうすれば、
【数６６２】
2019508000.tif 000664
である（式中、
【数６６３】
2019508000.tif 000665
はｎ番目のサイクルの持続時間である。）。ｎ番目のサイクルでｋ番目のノードのデータパケットがシンクノードに受信され始める時刻を
【数６６４】
2019508000.tif 000666
と表記する。
【０３０５】
本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法は、各ノードがビーコンパケット受信時刻かからどれほどの時間遅延後にデータパケットを送信しなければならないかについての情報をシンクノードがビーコンパケットに含ませて送る。
【０３０６】
ｎ番目のサイクルでｋ番目のノードのビーコン受信後にデータパケット送信時までの待機時間を
【数６６５】
2019508000.tif 000667
と表記する。
【数６６６】
2019508000.tif 000668
でｎ番目のサイクルであることを明示する必要はないが、本発明を説明する上での明確性のために、
【数６６７】
2019508000.tif 000669
にｎ番目のサイクルを明示する添字を使用する。ノードの移動性により、ノードの往復時間遅延はサイクルごとに変化するが、本発明では、このように変化する往復時間遅延を過去のＭ個のサイクルの往復時間遅延情報を用いて推定し、シンクノードでノードのデータパケットの受信衝突が発生しないように
【数６６８】
2019508000.tif 000670
を定める。
【０３０７】
本発明では、シンクノードと各ノード間の最初の往復時間遅延
【数６６９】
2019508000.tif 000671
、及びシンクノードと各ノード間の最初の往復時間遅延
【数６７０】
2019508000.tif 000672
が取得された時間
【数６７１】
2019508000.tif 000673
は知っていると仮定する。
【数６７２】
2019508000.tif 000674
及び
【数６７３】
2019508000.tif 000675
を取得することができるさまざまな方法が存在し、いかなる方法を使用しても、本発明の第３実施形態による多項式補間法を用いた水中無線移動ネットワークのためのスケジューリング方法は、サイクル数が増加すればするほど、
【数６７４】
2019508000.tif 000676
及び
【数６７５】
2019508000.tif 000677
とは無関係に正常状態に至るので、
【数６７６】
2019508000.tif 000678
及び
【数６７７】
2019508000.tif 000679
を取得するために使用する方法による本発明のスケジューリング方法の性能変化は非常に小さい。
【０３０８】
以下、上述のように構成されたネットワークトポロジーで行われる本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法について説明する。
図１０ａ乃至図１０ｃは本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートであって、ここで、Ｓはステップ（Ｓｔｅｐ）を意味する。
【０３０９】
まず、シンクノードは、
【数６７８】
2019508000.tif 000680
及び
【数６７９】
2019508000.tif 000681
を用いて１番目のサイクルのスケジュールである
【数６８０】
2019508000.tif 000682
を定めるためには、まず、下記［数式３０１］のように初期化過程を行う（Ｓ３０１０）。
【０３１０】
【数６８１】
2019508000.tif 000683
【０３１１】
（式中、
【数６８２】
2019508000.tif 000684
は
【数６８３】
2019508000.tif 000685
よりも小さいか同じ自然数であり、
【数６８４】
2019508000.tif 000686
である。
【数６８５】
2019508000.tif 000687
は、ｎ番目のサイクルで、（ｎ−１）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数６８６】
2019508000.tif 000688
値を知っているので、すべて１に設定する。
【数６８７】
2019508000.tif 000689
は、ｎ番目のサイクルで、（ｎ−ｍ）番目のサイクルにおけるｋ番目のノードの往復時間遅延取得の有効性を示す変数であり、
【数６８８】
2019508000.tif 000690
より過去に取得された往復時間遅延情報は最初に存在しないので、
【数６８９】
2019508000.tif 000691
が１よりも大きい場合には０とする。
【数６９０】
2019508000.tif 000692
は直近に取得されたｋ番目のノードの往復時間遅延であり、現在の状態で
【数６９１】
2019508000.tif 000693
が直近に取得された往復時間遅延であるので、
【数６９２】
2019508000.tif 000694
に設定する。
【数６９３】
2019508000.tif 000695
は、
【数６９４】
2019508000.tif 000696
が得られたサイクルであり、０に設定する。
【数６９５】
2019508000.tif 000697
はｎ番目のサイクルの持続時間であり、１番目のサイクル前のサイクル持続時間は知ることができないので、ユーザーが適正な
【数６９６】
2019508000.tif 000698
値を定めなければならないが、数式３０１ではその値を
【数６９７】
2019508000.tif 000699
と表示した。
【数６９８】
2019508000.tif 000700
は経験的に知っている平均的な
【数６９９】
2019508000.tif 000701
値にするか、或いはサイクル持続時間は全体データパケット長の和とノードの往復遅延時の最小値との和よりは大きいので、下記数式３０２のように推定されて定められる。）
【０３１２】
【数７００】
2019508000.tif 000702
【０３１３】
（式中、
【数７０１】
2019508000.tif 000703
は１番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【０３１４】
次いで、シンクノードは、次のような手続きでｎ番目のサイクルでｋ番目のノードのビーコン受信後にデータパケット送信時までの待機時間
【数７０２】
2019508000.tif 000704
を計算してサイクル単位で各ノードのデータパケットを受信する（Ｓ３０２０乃至Ｓ３１４０）。
【０３１５】
［ステップＳ３０２０］
シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数７０３】
2019508000.tif 000705
を０に設定する。
【０３１６】
さらに詳細に説明すると、
【数７０４】
2019508000.tif 000706
の小さい順に整列した後、
【数７０５】
2019508000.tif 000707
とし、
【数７０６】
2019508000.tif 000708
とする。ｋ番目のノードとは、
【数７０７】
2019508000.tif 000709
がｋ番目に小さいノードを意味する。ｎ番目のサイクルでｋ番目のノードのデータパケットはシンクノードにｋ番目に受信される。すなわち、ここで整列された順序は、シンクノードにデータパケットが到着する順序である。整列する方法としてさらに考慮できる方法は、
【数７０８】
2019508000.tif 000710
値が１であるノードを
【数７０９】
2019508000.tif 000711
の小さい順に整列し、次に
【数７１０】
2019508000.tif 000712
値が０であるノードのうち、
【数７１１】
2019508000.tif 000713
値が１であるノードを
【数７１２】
2019508000.tif 000714
の小さい順に整列し、次に
【数７１３】
2019508000.tif 000715
及び
【数７１４】
2019508000.tif 000716
値がすべてが０であるノードを
【数７１５】
2019508000.tif 000717
の小さい順に整列し、以下反復であって、次に
【数７１６】
2019508000.tif 000718
値がすべて０であるノードを
【数７１７】
2019508000.tif 000719
の小さい順に整列する方式とすることにより、直近に往復時間遅延が取得されたノードに優先順位を付与する方法を使用することもできる。これ以外にも、応用分野に応じて、優先順位ベースの様々な整列方法が存在することができる。
【０３１７】
［ステップＳ３０３０］
シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数７１８】
2019508000.tif 000720
を推定し、１番目のノードのデータパケット受信完了時点
【数７１９】
2019508000.tif 000721
を計算する。
【０３１８】
さらに詳細には、
【数７２０】
2019508000.tif 000722
と定義しよう。
【数７２１】
2019508000.tif 000723
は２以上の自然数とする。
【数７２２】
2019508000.tif 000724
は、ユーザーが定める値である。もし
【数７２３】
2019508000.tif 000725
であれば、すなわち、直近の
【数７２４】
2019508000.tif 000726
サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数７２５】
2019508000.tif 000727
回以上である場合には、ｎ番目のサイクルで１番目のノードの往復時間遅延
【数７２６】
2019508000.tif 000728
を下記［数式３０３］のように連立方程式を解いて推定する。
【０３１９】
【数７２７】
2019508000.tif 000729
【０３２０】
（式中、
【数７２８】
2019508000.tif 000730
は
【数７２９】
2019508000.tif 000731
座標を通る最小次数の多項式である。ここで、
【数７３０】
2019508000.tif 000732
サイクルで１番目のノードの有効な往復時間遅延が取得された。そのとき、１番目のノードの往復時間遅延値は
【数７３１】
2019508000.tif 000733
である。
【数７３２】
2019508000.tif 000734
は
【数７３３】
2019508000.tif 000735
次の多項式であって、多項式補間法を用いて容易に求めることができる。例えば、分割された差（ｄｉｖｉｄｅｄ  ｄｉｆｆｅｒｅｎｃｅ）方法を用いることができる。［数式３０３］は、
【数７３４】
2019508000.tif 000736
次多項式と１次多項式の連立方程式であって、［数式３０３］の２番目の１次多項式を［数式３０３］の１番目の
【数７３５】
2019508000.tif 000737
次多項式に代入すると、結果的に
【数７３６】
2019508000.tif 000738
次多項式の解を求める問題に帰結する。［数式３０３］は、解が唯一に存在するか、解が存在しないか、解が多数存在するか、或いは解が数多く存在することができる。［数式３０３］の解が存在するためには、［数式３０３］の１番目の
【数７３７】
2019508000.tif 000739
次多項式が［数式３０３］の２番目の１次多項式の上または下にあるべきである。本発明において、
【数７３８】
2019508000.tif 000740
であるので、すなわち、
【数７３９】
2019508000.tif 000741
値は範囲が制限されているので、［数式３０３］の１番目の
【数７４０】
2019508000.tif 000742
次多項式は
【数７４１】
2019508000.tif 000743
の変化に応じて一定の範囲内で
【数７４２】
2019508000.tif 000744
軸と平行に近い形態でグラフが表現される。一方、［数式３０３］の２番目の１次多項式は、傾きが「１」である。したがって、解が存在しない場合は発生しない。また、
【数７４３】
2019508000.tif 000745
が２である場合には、［数式３０３］の１番目の
【数７４４】
2019508000.tif 000746
次多項式が１次多項式になるが、上述したような理由で、［数式３０３］を構成する２つの１次多項式の傾きが互いに変わり、［数式３０３］の実数解が唯一に存在する。
【数７４５】
2019508000.tif 000747
が３以上である場合には、複素数の解を含んで多数の解が存在することができ、実数解も複数個存在することができる。実数解が複数個存在するためには、［数式３０３］の１番目の
【数７４６】
2019508000.tif 000748
次多項式が傾き「１」以上の急激な変化を示さなければならず、これは、
【数７４７】
2019508000.tif 000749
であることを考慮すれば、
【数７４８】
2019508000.tif 000750
値のヒストリーが両端値である「０」または
【数７４９】
2019508000.tif 000751
値を持つことを意味するので、この場合にも、実数解は１つを持つ確率が非常に高い。別の方法で解釈すると、このように急激なトポロジーの変化を示す環境は、過去の往復時間遅延情報を用いて現在の往復時間遅延情報を推定することが難しい場合に該当する。この際にも、本発明は、往復時間遅延情報を保守的に適用するように設計され、安定的に動作することができる。先立って、［数式３０３］を解くことは
【数７５０】
2019508000.tif 000752
次多項式の解を求めるのと同様であると述べたが、一般に、
【数７５１】
2019508000.tif 000753
次多項式は、
【数７５２】
2019508000.tif 000754
個の解を有し、ここには複素数の解と実数の解とが混合されている。本発明では、［数式３０３］を解析的に直接解く場合よりは次のようにインタラクティブ（ｉｔｅｒａｔｉｖｅ）に求める。まず、
【数７５３】
2019508000.tif 000755
の初期値を定める。例えば、
【数７５４】
2019508000.tif 000756
とする。これ以外にも、
【数７５５】
2019508000.tif 000757
などのように初期値を定める方法は多様にあり、
【数７５６】
2019508000.tif 000758
に近接する値となるように設定するのが良い。この際、初期値
【数７５７】
2019508000.tif 000759
を用いて［数式３０３］から
【数７５８】
2019508000.tif 000760
を
【数７５９】
2019508000.tif 000761
のように計算する。そして、このように計算された
【数７６０】
2019508000.tif 000762
を用いて
【数７６１】
2019508000.tif 000763
を
【数７６２】
2019508000.tif 000764
のように計算し、このとき、計算された
【数７６３】
2019508000.tif 000765
から
【数７６４】
2019508000.tif 000766
を
【数７６５】
2019508000.tif 000767
のように計算する。
【数７６６】
2019508000.tif 000768
を用いて
【数７６７】
2019508000.tif 000769
を
【数７６８】
2019508000.tif 000770
のように計算し、計算された
【数７６９】
2019508000.tif 000771
から
【数７７０】
2019508000.tif 000772
を
【数７７１】
2019508000.tif 000773
のように計算する過程を、定められた回数だけ繰り返した後、最終的に計算される値を
【数７７２】
2019508000.tif 000774
と
【数７７３】
2019508000.tif 000775
に確定する。このとき、繰り返し回数を定めず、以前に計算された
【数７７４】
2019508000.tif 000776
と現在計算された
【数７７５】
2019508000.tif 000777
との差が一定値以下である場合に繰り返し過程を中断する方法がある。同様に、以前に計算された
【数７７６】
2019508000.tif 000778
と現在計算された
【数７７７】
2019508000.tif 000779
との差が一定値以下である場合に繰り返し過程を中断する方法もある。
【数７７８】
2019508000.tif 000780
は
【数７７９】
2019508000.tif 000781
よりは小さいので、下記数式３０４のように値を制限する。）
【０３２１】
【数７８０】
2019508000.tif 000782
【０３２２】
（式中、
【数７８１】
2019508000.tif 000783
は往復時間遅延の最大値である。）
【０３２３】
そして、１番目のノードのデータパケット受信完了時点
【数７８２】
2019508000.tif 000784
を下記［数式３０５］のように計算する。
【０３２４】
【数７８３】
2019508000.tif 000785
【０３２５】
（式中、
【数７８４】
2019508000.tif 000786
はｎ番目のサイクルで１番目のノードのデータパケット長を時間に換算した値であり、
【数７８５】
2019508000.tif 000787
はガード時間である。）
【０３２６】
もし
【数７８６】
2019508000.tif 000788
であれば、すなわち、直近の
【数７８７】
2019508000.tif 000789
サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数７８８】
2019508000.tif 000790
回未満であれば、過去に取得された時間遅延から現在の時間遅延を推定することが妥当ではないと判断する。このときは、下記［数式３０６］のようにｎ番目のサイクルで１番目のノードの往復時間遅延
【数７８９】
2019508000.tif 000791
を推定し、１番目のノードのデータパケット受信完了時点
【数７９０】
2019508000.tif 000792
を計算する。
【０３２７】
【数７９１】
2019508000.tif 000793
【０３２８】
（式中、
【数７９２】
2019508000.tif 000794
は、直近に取得された１番目のノードの往復時間遅延であり、
【数７９３】
2019508000.tif 000795
はシンクノードとｋ番目のノード間の最大相対速度であり、
【数７９４】
2019508000.tif 000796
はｎ−１番目のサイクルの持続時間であり、
【数７９５】
2019508000.tif 000797
は１番目のノードの往復時間遅延が取得された直近のサイクルであり、
【数７９６】
2019508000.tif 000798
は水中での最小音波伝達速度である。）
【０３２９】
［数式３０６］のように１番目のノードの往復時間遅延が取得された直近の時点からできる限り最大変動幅を用いて往復時間遅延を推定すると、衝突を根本的に回避することができる。［数式３０６］において、
【数７９７】
2019508000.tif 000799
は１番目のノードの往復時間遅延が取得された直近のサイクルであるため、
【数７９８】
2019508000.tif 000800
は往復時間遅延の取得後に費やされた時間を意味し、このとき、平均的なサイクル持続時間を直近のサイクルである（ｎ−１）番目のサイクル持続時間に近似すると、
【数７９９】
2019508000.tif 000801
は、直近に往復時間遅延が取得された後、ｎ番目のサイクルでの往復時間遅延が持つことが可能な最大変動幅になる。よって、
【数８００】
2019508000.tif 000802
はｎ番目のサイクルで１番目のノードの最大往復時間遅延となり、この値が
【数８０１】
2019508000.tif 000803
を超えることができないので、［数式３０６］のように１番目のノードの往復時間遅延を計算する。直近の
【数８０２】
2019508000.tif 000804
個のサイクルのうち、
【数８０３】
2019508000.tif 000805
個未満のサイクルでのみ１番目のノードの往復時間遅延が取得されたというのは、物理階層が完璧であれば、１番目のノードの移動性が急に変わって他のノードのパケットとの衝突を発生したものと認知することができる。よって、過去の往復時間遅延情報からｎ番目のサイクルでの往復時間遅延を推定することは好ましくないことに留意すべきである。また、このように計算された
【数８０４】
2019508000.tif 000806
は、
【数８０５】
2019508000.tif 000807
が持つことが可能な最も大きい値なので、
【数８０６】
2019508000.tif 000808
を計算するにあたり、［数式３０６］では、［数式３０５］とは異なり、ガード時間を含まない。
【０３３０】
［ステップＳ３０４０］
シンクノードによって変数ｋが最後番目（Ｋ番目）より小さいか否かを判断する。
【０３３１】
［ステップＳ３０５０］
前記ステップ（Ｓ３０４０）で前記変数ｋが最後番目（Ｋ番目）より小さければ（Ｙ）、シンクノードが前記変数ｋをｋ＋１に設定する。
【０３３２】
［ステップＳ３０６０］
シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数８０７】
2019508000.tif 000809
を推定する。
【０３３３】
さらに詳細には、
【数８０８】
2019508000.tif 000810
と定義しよう。もし
【数８０９】
2019508000.tif 000811
であれば、すなわち、直近の
【数８１０】
2019508000.tif 000812
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数８１１】
2019508000.tif 000813
回以上であれば、下記［数式３０７］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数８１２】
2019508000.tif 000814
を推定する。
【０３３４】
【数８１３】
2019508000.tif 000815
【０３３５】
（式中、
【数８１４】
2019508000.tif 000816
は
【数８１５】
2019508000.tif 000817
座標を通る最小次数の多項式である。ここで、
【数８１６】
2019508000.tif 000818
サイクルでｋ番目のノードの有効な往復時間遅延が取得された。そのとき、ｋ番目のノードの往復時間遅延値は
【数８１７】
2019508000.tif 000819
である。
【数８１８】
2019508000.tif 000820
は、
【数８１９】
2019508000.tif 000821
次の多項式であって、多項式補間法を用いて容易に求めることができる。数式３０７は、過去に取得された往復時間遅延情報を数値解析的補間法で近似し、直前のデータパケットである（ｋ−１）番目のノードのデータパケットの受信が終了する時刻である
【数８２０】
2019508000.tif 000822
時刻にｋ番目のデータパケットが受信されるときに往復時間遅延
【数８２１】
2019508000.tif 000823
を計算したものである。）
【０３３６】
したがって、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信して往復時間遅延
【数８２２】
2019508000.tif 000824
を有しながら、シンクノードにｋ番目のノードのデータパケットが受信され始める時刻
【数８２３】
2019508000.tif 000825
は、下記［数式３０８］のように計算される。
【０３３７】
【数８２４】
2019508000.tif 000826
【０３３８】
このとき、もし
【数８２５】
2019508000.tif 000827
であれば、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信しても、（ｋ−１）番目のノードのデータパケットの受信が完了してから
【数８２６】
2019508000.tif 000828
だけの時間が経過した後にｋ番目のノードのデータパケットの受信が始まるので、［数式３０７］によって推定した
【数８２７】
2019508000.tif 000829
時刻でのｋ番目のノードの往復時間遅延は、実際のｋ番目のノードのデータパケットが到着する時点での往復時間遅延推定値として適切ではない。よって、［数式３０３］を反復的な方法で解いて１番目のノードの往復時間遅延を推定した方式でｋ番目のノードの往復時間遅延を推定しなければならない。したがって、
【数８２８】
2019508000.tif 000830
の場合には、次のように連立方程式である［数式３０９］を解いてｋ番目のノードの往復時間遅延
【数８２９】
2019508000.tif 000831
を推定する。
【０３３９】
【数８３０】
2019508000.tif 000832
【０３４０】
［数式３０３］と同様に、［数式３０９］は、
【数８３１】
2019508000.tif 000833
次多項式の解を求める問題であって、
【数８３２】
2019508000.tif 000834
が２である場合には、実数解が唯一に存在するので、解析的解を利用し、
【数８３３】
2019508000.tif 000835
が３以上である場合には、次のように反復的な方法を用いて解を求める。まず、
【数８３４】
2019508000.tif 000836
の初期値を定める。例えば、
【数８３５】
2019508000.tif 000837
とする。これ以外にも、
【数８３６】
2019508000.tif 000838
などのように初期値を定める方法は多様にあり、
【数８３７】
2019508000.tif 000839
に近接する値となるように設定するのが良い。このとき、初期値
【数８３８】
2019508000.tif 000840
を用いて、［数式３０９］から
【数８３９】
2019508000.tif 000841
を
【数８４０】
2019508000.tif 000842
のように計算する。このように計算された
【数８４１】
2019508000.tif 000843
を用いて
【数８４２】
2019508000.tif 000844
を
【数８４３】
2019508000.tif 000845
のように計算し、このとき、計算された
【数８４４】
2019508000.tif 000846
から
【数８４５】
2019508000.tif 000847
を
【数８４６】
2019508000.tif 000848
のように計算する。
【数８４７】
2019508000.tif 000849
を用いて
【数８４８】
2019508000.tif 000850
を
【数８４９】
2019508000.tif 000851
のように計算し、計算された
【数８５０】
2019508000.tif 000852
から
【数８５１】
2019508000.tif 000853
を
【数８５２】
2019508000.tif 000854
のように計算する過程を、定められた回数だけ繰り返し行った後、最終的に計算された値を
【数８５３】
2019508000.tif 000855
と
【数８５４】
2019508000.tif 000856
に確定する。このとき、繰り返し回数を定めず、以前に計算された
【数８５５】
2019508000.tif 000857
と現在計算された
【数８５６】
2019508000.tif 000858
との差が一定値以下である場合に繰り返し過程を中断する方法がある。同様に、以前に計算された
【数８５７】
2019508000.tif 000859
と現在計算された
【数８５８】
2019508000.tif 000860
との差が一定値以下である場合に繰り返し過程を中断する方法もある。
【０３４１】
【数８５９】
2019508000.tif 000861
【数８６０】
2019508000.tif 000862
よりも小さいので、下記［数式３１０］のように値を制限する。
【０３４２】
【数８６１】
2019508000.tif 000863
【０３４３】
もし
【数８６２】
2019508000.tif 000864
であれば、すなわち、直近の
【数８６３】
2019508000.tif 000865
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数８６４】
2019508000.tif 000866
回未満であれば、過去に取得された時間遅延から現在の時間遅延を推定することが妥当ではないと判断する。この際には、下記［数式３１１］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数８６５】
2019508000.tif 000867
を推定する。
【０３４４】
【数８６６】
2019508000.tif 000868
【０３４５】
前記［数式３１１］は［数式３０６］とは異なるが、これは、連続するデータパケットの衝突を回避するためには以前データパケットの終了時刻は遅く推定される方向にしなければならず、次のデータパケットの受信時刻は速く推定される方向にしなければならないからである。
【０３４６】
［ステップＳ３０７０］
シンクノードが、前記ステップ（Ｓ３０６０）で推定されたｋ番目のノードの往復時間遅
【数８６７】
2019508000.tif 000869
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数８６８】
2019508000.tif 000870
を前記［数式３０８］のように計算する。
【０３４７】
［ステップＳ３０８０］
シンクノードが、前記ステップ（Ｓ３０７０）で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数８６９】
2019508000.tif 000871
を用いて、ｋ番目のノードの待機時間
【数８７０】
2019508000.tif 000872
を下記［数式３１２］のように計算する。
【０３４８】
【数８７１】
2019508000.tif 000873
【０３４９】
このように、ｎ番目のサイクルでｋ番目のノードがビーコンパケットを受信した後、
【数８７２】
2019508000.tif 000874
時間だけ待機してからデータパケットを送信すると、（ｋ−１）番目のノードのデータパケットが受信完了した後にｋ番目のノードのデータパケットが受信され、シンクノードでデータパケットの受信衝突が発生しない。
【０３５０】
［ステップＳ３０９０］
シンクノードが、前記ステップ（Ｓ３０７０）で計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数８７３】
2019508000.tif 000875
と、前記ステップ（Ｓ３０８０）で計算されたｋ番目のノードの待機時間
【数８７４】
2019508000.tif 000876
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数８７５】
2019508000.tif 000877
を計算した後、前記ステップ（Ｓ３０４０）へ移行する。
【０３５１】
より詳細には、もし
【数８７６】
2019508000.tif 000878
であれば（すなわち、直近の
【数８７７】
2019508000.tif 000879
サイクルの間にｋ番目のノードの往復時間遅延が成功的に取得された場合が
【数８７８】
2019508000.tif 000880
回以上であれば）、ｋ番目のノードのデータパケットが受信終了する時刻
【数８７９】
2019508000.tif 000881
は、下記［数式３１３］のように計算される。
【０３５２】
【数８８０】
2019508000.tif 000882
【０３５３】
（
【数８８１】
2019508000.tif 000883
はｎ番目のサイクルでｋ番目のノードのデータパケット長を時間に換算した値である。）
【０３５４】
一方、もし
【数８８２】
2019508000.tif 000884
であれば（すなわち、直近の
【数８８３】
2019508000.tif 000885
サイクルの間に１番目のノードの往復時間遅延が成功的に取得された場合が
【数８８４】
2019508000.tif 000886
回未満であれば）、ｋ番目のノードのデータパケットがシンクノードで受信完了する時刻の推定値
【数８８５】
2019508000.tif 000887
は、下記［数式３１４］のように計算される。
【０３５５】
【数８８６】
2019508000.tif 000888
【０３５６】
【数８８７】
2019508000.tif 000889
【０３５７】
［ステップＳ３１００］
前記ステップ（Ｓ３０４０）で変数ｋが最後番目（Ｋ番目）より小さくなければ（Ｎ）、シンクノードがビーコンパケットの放送有無を判断する。
【０３５８】
すなわち、Ｋ番目のノードのスケジュール計算が完了すると、シンクノードがビーコンパケットの放送有無を判断してサイクルの進行如何を決定する。
【０３５９】
一方、ステップ（Ｓ３０４０）でビーコンパケットが放送されなければ（Ｎ）（すなわち、サイクルを進行しない場合には）、すべての手続きを終了する。
【０３６０】
［ステップＳ３１１０］
前記ステップ（Ｓ３１００）でビーコンパケットが放送されてサイクルが継続して進行する場合には（Ｙ）、シンクノードは、ｎ番目のサイクルでシンクノードがビーコンパケットを放送し始める時刻
【数８８８】
2019508000.tif 000890
にビーコンパケットを放送する。
【０３６１】
［ステップＳ３１２０］
Ｋ番目のノードのデータパケットの受信が完了したか、或いはＫ番目のノードのデータパケットが受信完了する時刻の推定値
【数８８９】
2019508000.tif 000891
が超過する。
【０３６２】
［ステップＳ３１３０］
前記ステップ（Ｓ３１２０）が行われた後、シンクノードは、ｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数８９０】
2019508000.tif 000892
を計算し、往復時間遅延取得有効性値
【数８９１】
2019508000.tif 000893
及び直近に取得された往復時間遅延関連情報
【数８９２】
2019508000.tif 000894
を更新する。
【０３６３】
より詳細には、
【数８９３】
2019508000.tif 000895
時刻にビーコンパケットを放送した後、Ｋ番目のノードのデータパケットの受信が完了したか或いは
【数８９４】
2019508000.tif 000896
時刻を超過すれば、シンクノードは、ｎ番目のサイクルにおける各ノードからのデータパケットの成功的な受信か否かを知ることができる。まず、
【数８９５】
2019508000.tif 000897
値を更新するために、下記［数式３１５］のようにすべての
【数８９６】
2019508000.tif 000898
及び
【数８９７】
2019508000.tif 000899
について、ノードに対して
【数８９８】
2019508000.tif 000900
値を下記［数式３１５］のように更新する。
【０３６４】
【数８９９】
2019508000.tif 000901
【０３６５】
ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信した場合には、下記［数式３１６］のようにする。
【０３６６】
【数９００】
2019508000.tif 000902
【０３６７】
ｎ番目のサイクルでｋ番目のノードのデータパケットを成功的に受信しなかった場合には、下記［数式３１７］のようにする。
【０３６８】
【数９０１】
2019508000.tif 000903
【０３６９】
そして、直近に取得された往復時間遅延関連情報
【数９０２】
2019508000.tif 000904
は、下記［数式３１８］のように更新する。
【０３７０】
【数９０３】
2019508000.tif 000905
【０３７１】
また、往復時間遅延取得有効性値
【数９０４】
2019508000.tif 000906
が１である場合には、下記［数式３１９］のようにｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数９０５】
2019508000.tif 000907
を計算し、直近に取得された往復時間遅延関連情報
【数９０６】
2019508000.tif 000908
を更新する。
【０３７２】
【数９０７】
2019508000.tif 000909
【０３７３】
［ステップＳ３１４０］
シンクノードがｎを１だけ増加させた後、（ｎ＋１）番目のサイクルのための
【数９０８】
2019508000.tif 000910
計算のために、前記ステップ（Ｓ３０２０）へ移行する。
【０３７４】
本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法によれば、シンクノードが初期化過程を行い；前記シンクノードがデータパケット受信順序を決定した後、ｎ番目のサイクルで１番目のノードに付与される時間遅延
【数９０９】
2019508000.tif 000911
を０に設定し；シンクノードがｎ番目のサイクルで１番目のノードの往復時間遅延
【数９１０】
2019508000.tif 000912
を推定し、１番目のノードのデータパケット受信完了時点
【数９１１】
2019508000.tif 000913
を計算し；シンクノードによって、変数ｋが最後番目（Ｋ番目）よりも小さいか否かを判断し；前記判断で変数ｋが最後番目（Ｋ番目）より小さければ、シンクノードが変数ｋをｋ＋１に設定し；シンクノードがｎ番目のサイクルでｋ番目のノードの往復時間遅延
【数９１２】
2019508000.tif 000914
を推定し；シンクノードが、前記推定されたｋ番目のノードの往復時間遅延
【数９１３】
2019508000.tif 000915
を用いて、ｋ番目のノードがビーコンパケットを受け取るや否やデータパケットを送信するとき、ｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９１４】
2019508000.tif 000916
を計算し；シンクノードが、計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９１５】
2019508000.tif 000917
を用いて、ｋ番目のノードの待機時間
【数９１６】
2019508000.tif 000918
を計算し；前記シンクノードが、前記計算されたｋ番目のノードのデータパケットがシンクノードに受信され始める時刻の推定値
【数９１７】
2019508000.tif 000919
と、前記計算されたｋ番目のノードの待機時間
【数９１８】
2019508000.tif 000920
を用いて、ｋ番目のノードのデータパケットが受信完了する時刻の推定値
【数９１９】
2019508000.tif 000921
を計算した後、前記判断過程へ進むように構成されることにより：
つまり、水中音響無線移動ネットワークのように往復時間遅延が大きく物理階層の伝送速度が低いネットワーク環境で、チャンネル使用効率の向上によるネットワーク効率を向上させることができ、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能であり、誤差が累積されないため周期的な再初期化が必要ないという優れた効果がある。特に、ノード数が増加すればするほど、ネットワーク効率の向上程度はさらに増加する。本発明に係る多項式補間法を用いた水中無線移動ネットワークのためのスケジューリング方法は、絶対時間基準ではなく、時間差に該当する情報によって決定されるので、各ノードのローカル時刻情報が互いに異なっても正確に動作する。したがって、時間同期化が必要ないので、時間同期化が不可能であるか或いは時間同期化のために多くのリソースが消費される応用分野でも活用が可能である。
【０３７５】
また、往復時間遅延情報に対する正確な値がサイクルごとに得られるので、誤差が累積されないため周期的な再初期化が必要ない。
【０３７６】
図面と明細書には好適な実施形態が開示されており、特定の用語が使用されているが、これは、単に本発明の実施形態を説明するための目的で使用されたものであり、意味を限定し或いは特許請求の範囲に記載された本発明の範囲を制限するために使用されたものではない。したがって、本技術分野における通常の知識を有する者であれば、これから様々な変形及び均等な他の実施形態が可能であることを理解することができるだろう。よって、本発明の真正な技術的保護範囲は、添付された特許請求の範囲の技術的思想によって定められなければならないだろう。
【図面の簡単な説明】
【０３７７】
【図１】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
【図２ａ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｂ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｃ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｄ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｅ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｆ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図３】本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。
【図４】本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。
【図５】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
【図６】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
【図７ａ】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図７ｂ】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図８】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
【図９】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
【図１０ａ】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図１０ｂ】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図１０ｃ】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図１】
2019508000.tif 001236
【図２ａ】
2019508000.tif 001237
【図２ｂ】
2019508000.tif 001238
【図２ｃ】
2019508000.tif 001239
【図２ｄ】
2019508000.tif 001240
【図２ｅ】
2019508000.tif 001241
【図２ｆ】
2019508000.tif 001242
【図３】
2019508000.tif 001243
【図４】
2019508000.tif 001244
【図５】
2019508000.tif 001245
【図６】
2019508000.tif 001246
【図７ａ】
2019508000.tif 001247
【図７ｂ】
2019508000.tif 001248
【図７ｃ】
2019508000.tif 001249
【図８】
2019508000.tif 001250
【図９】
2019508000.tif 001251
【図１０ａ】
2019508000.tif 001252
【図１０ｂ】
2019508000.tif 001253
【図１０ｃ】
2019508000.tif 001254
【手続補正書】
【提出日】平成30年8月24日(2018.8.24)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
［式中、
【数２５】
2019508000.tif 001255
は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、
【数２６】
2019508000.tif 001256
は初期化パケット長の時間換算値であり、
【数２７】
2019508000.tif 001257
は初期化応答パケット長の時間換算値であり、
【数２８】
2019508000.tif 001258
はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。
【数２９】
2019508000.tif 001259
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０１４２
【補正方法】変更
【補正の内容】
【０１４２】
〔図面の簡単な説明〕
〔図１〕本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図２ａ乃至図２ｆ〕本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
〔図３〕本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。
〔図４〕本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。
〔図５〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図６〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
〔図７ａ乃至図７ｃ〕本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
〔図８〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
〔図９〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
〔図１０ａ乃至図１０ｃ〕本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０１５２
【補正方法】変更
【補正の内容】
【０１５２】
(式中、
【数３５９】
2019508000.tif 001260
は、シンクノードとノード間の往復時間遅延の最大値であって、下記数式１０２によって決定され、
【数３６０】
2019508000.tif 001261
は初期化パケット長の時間換算値であり、
【数３６１】
2019508000.tif 001262
は初期化応答パケット長の時間換算値であり、
【数３６２】
2019508000.tif 001263
はノードが初期化パケットの受信完了後に初期化応答パケットを送信するまでにかかる時間である。)
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１８９
【補正方法】変更
【補正の内容】
【０１８９】
【数４１３】
2019508000.tif 001264
は、１番目のノードのデータパケットがシンクノードに到着する時刻の最大値である。したがって、２番目のノードは、シンクノードに最も速くデータパケットが受信され始める場合にも、１番目のノードのデータパケットがシンクノードで受信完了した後に受信が始まるように待機時間を付与することが、シンクノードでノードのデータパケットの受信衝突を回避する核心アイデアである。２番目のノードのデータパケットがシンクノードに最も速く受信され始める場合は、２番目のノードがシンクノードの動き方向とは正反対の方向に最大速度で動く場合であるが、すなわち、２番目のノードとシンクノードとが最大相対速度で互いに遠ざかるとき、２番目のノードがビーコンパケットの受信後に時間遅延なしに直ちにデータパケットを送信すると、シンクノードでは、いくら速くても下記数式１１０のように与えられる
【数４１４】
2019508000.tif 001265
後に２番目のノードのデータパケットの受信が始まる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０３４１
【補正方法】変更
【補正の内容】
【０３４１】
【数８５９】
2019508000.tif 001266
は、
【数８６０】
2019508000.tif 001267
よりも小さいので、下記［数式３１０］のように値を制限する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０３５６
【補正方法】変更
【補正の内容】
【０３５６】
【数８８７】
2019508000.tif 001268
計算が完了すると、ステップ（Ｓ３０４０）に戻る。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０３７７
【補正方法】変更
【補正の内容】
【０３７７】
【図１】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
【図２ａ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｂ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｃ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｄ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｅ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図２ｆ】本発明の第１実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図３】本発明の第１実施形態によるサイクル単位のスケジューリング概念図である。
【図４】本発明の第１実施形態によるｎ番目のサイクルで各ノードの待機時間導出原理を示す概念図である。
【図５】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
【図６】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
【図７ａ】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図７ｂ】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図７ｃ】本発明の第２実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図８】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法が適用されるネットワークトポロジーを示す図である。
【図９】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法のサイクル概念図である。
【図１０ａ】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図１０ｂ】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【図１０ｃ】本発明の第３実施形態による水中無線移動ネットワークのためのスケジューリング方法を説明するための動作フローチャートである。
【国際調査報告】
2019508000.tif 001269
2019508000.tif 001270
2019508000.tif 001271
2019508000.tif 001272