(57)【要約】      （修正有） 【課題】 帯域幅を効果的に使用しながら信頼性も向上させることができる移動アドホックネットワークにおけるブロードキャストデータ処理方法を提供する。  【解決手段】  ブロードキャストパケットが受信されると、ブロードキャスティングカウントナンバー(ＮＢＣ)と、ブロードキャスティングカウントナンバー(ＢＣ)を用いて、伝送ノードからのブロードキャストパケットが全部受信されたかを判断し、全部受信の場合には、受信したブロードキャストパケットのＢＣと自機のバッファーサイズを比較し、受信したブロードキャストパケットのＢＣが自機のバッファーサイズを超過するカウント値であれば、伝送ノード側のバッファーをフラッシュするためのハローパケットを生成して伝送ノードへ伝送し、自機のバッファーをフラッシュした後、受信されたブロードキャストパケットを用いて、フラッシュされた自機のバッファーの隣接テーブルをアップデートする。【選択図】  図１１
2005124195.tif 000002
【特許請求の範囲】
【請求項１】
移動アドホックネットワークにおけるブロードキャストデータ処理方法であって、
伝送ノードから伝送されたブロードキャストパケットが受信されると、バッファー内の隣接テーブルに保存された一番最近に受信したブロードキャスティングカウントナンバー(ＮＢＣ)と、前記伝送ノードから受信されたブロードキャストパケットに含まれたブロードキャスティングカウントナンバー(ＢＣ)と、を用いて、前記伝送ノードから伝送したブロードキャストパケットが全部受信されたか否かを判断する段階と、
前記伝送ノードから伝送したブロードキャストパケットを全部受信した場合に、受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)と自機のバッファーサイズとを比較する段階と、
前記受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)が自機のバッファーサイズを超過するカウント値であれば、伝送ノード側のバッファーをフラッシュするためのハローパケットを生成して伝送ノードへ伝送し、自機のバッファーをフラッシュした後に、受信されたブロードキャストパケットを用いてフラッシュされた自機のバッファーの隣接テーブルをアップデートする段階と、を含むこと
を特徴とする移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項２】
前記バッファー内の隣接テーブルは、ブロードキャストパケットを伝送した伝送ノードＩＤ情報と、ブロードキャストパケットの伝送ノードから一番最近に受信したブロードキャスティングカウントナンバー情報と、受信したブロードキャストパケットを保存するバッファーサイズ情報と、受信したブロードキャストパケットの中でエラー又は損失により受信することができなかったパケットリストについてのビットマップ情報と、を含むこと
を特徴とする請求項１記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項３】
前記伝送ノードは、ブロードキャストパケットを生成して伝送するSenderノードを通じて伝送されるブロードキャストパケットを受信側ノードにリレーするRelayerノードであること
を特徴とする請求項１記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項４】
前記ブロードキャストパケットは、ＩＰヘッダーフィールドと、
ブロードキャストパケットを受信する受信側ノードの周辺に存在するRelayerノードのリスト情報を含むRelayerノードリスト情報フィールドと、
該当ノードから伝送されるブロードキャストパケットについてのブロードキャスティングカウントナンバー情報フィールド及びブロードキャストデータフィールドと、を含むこと
を特徴とする請求項１記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項５】
前記バッファーサイズを比較する段階で、前記受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)が自機のバッファーサイズを超過しないカウント値である場合には、受信されたブロードキャストパケット情報をバッファーの隣接テーブルに挿入する段階を含むこと
を特徴とする請求項１記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項６】
前記伝送ノードからブロードキャストパケットを受信した場合に、一定時間の間隔で又は一定パケット量によって周期的にブロードキャストパケットの受信確認情報を含むハローパケットを生成して前記伝送ノードへ伝送する段階をさらに含むこと
を特徴とする請求項１記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項７】
前記ハローパケットは、パケットタイプ情報フィールドと、
ブロードキャストパケットの受信可否についての応答情報フィールドと、
予約フィールドを含むフラッグ情報フィールドと、
自機と隣接した伝送ノードのＩＤ情報フィールドと、
ブロードキャスティングカウントナンバー(ＢＣ)情報フィールドと、
ブロードキャストパケットを受信することができなかった場合の損失されたパケットのビットマップ情報フィールドと、
Senderと隣接したノードのＩＤ情報及びブロードキャストパケットを受信することができなかった場合の応答情報であるNACK Info情報を含む隣接するノード情報フィールドと、
ブロードキャストパケットを受信することができなかったノードに対応するＩＤ情報と、該当ノードから受信することができなかったブロードキャストパケットのＩＤ情報を含むブロードキャスト再伝送情報フィールドと、を含むこと
を特徴とする請求項１又は６記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項８】
前記伝送ノードから伝送したブロードキャストパケットが全部受信されたか否かを判断する段階で、前記伝送ノードから伝送したブロードキャストパケットを全部受信していなかった場合に、受信されたブロードキャストパケットに含まれたブロードキャスティングカウントナンバー(ＢＣ)値が一番最近に受信したブロードキャスティングカウントナンバーの次のカウント値(ＮＢＣ＋１)より大きいか否かを判断する段階と、
a) 該判断の結果、伝送ノードから現在まで伝送したブロードキャスティングカウントナンバーが現在まで受信したブロードキャスティングカウントナンバーより大きい値である場合には、自機の隣接テーブルに損失されたパケットリストをアップデートした後に、ハローパケットの伝送を通じて損失されたパケットの再伝送を受ける段階と、
b) 伝送ノードから現在まで伝送したブロードキャストカウント値が現在まで受信したブロードキャストカウント値より大きくない場合には、自機は全てのパケットを受信したにもかかわらず、他のノードから損失されたパケットの再伝送要求によって該当パケットを受信したと判断して、受信されたブロードキャストパケットを廃棄する段階と、を含むこと
を特徴とする請求項１記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項９】
前記ハローパケットを生成して前記伝送ノードへ伝送する段階は、前記バッファー内の隣接テーブルに保存されたブロードキャストパケットを伝送した各ノードに関するブロードキャストデータのビットマップ情報を順次に検索して、各ノード別に損失されたパケットが存在するか否かを判断する段階と、
該判断の結果、損失されたパケットが存在する場合には、前記隣接テーブルのビットマップを用いて、損失されたパケットを要求するためのハローパケットを生成した後に、該当ブロードキャストパケットを伝送したノードへ該ハローパケットを伝送する段階と、を含むこと
を特徴とする請求項６記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１０】
前記伝送されたハローパケットを受信した伝送ノードは、自機のバッファー内の隣接テーブルに存在しない新しいノードからのハローパケットが受信されたか否かを判断する段階と、
該判断の結果、隣接テーブルに存在しているノードからのハローパケットを受信した場合には、受信されたハローパケットが、バッファーをフラッシュするためのトリガーハローパケットであるか否かを判断する段階と、
受信されたパケットがトリガーハローパケットではない一定周期でブロードキャストパケット受信可否を知らせるハローパケットである場合に、受信されたハローパケットからビットマップ情報をチェックして、損失されたパケットが存在するか否かを判断する段階と、
該判断の結果、損失されたパケットが存在する場合には、損失されたパケットに相応するブロードキャストパケットをハローパケットを伝送したノードへ伝送した後に、自機の隣接テーブルをアップデートする段階と、を含むこと
を特徴とする請求項９記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１１】
前記トリガーハローパケットであるか否かを判断する段階で、受信されたハローパケットがトリガーハローパケットである場合に、バッファーフラッシュのために全ての隣接ノードからトリガーハローパケットを受信したか否かを判断する段階と、
a) 該判断の結果、全ての隣接ノードからトリガーハローパケットを受信した場合にはバッファーをフラッシュし、
b) 全ての隣接ノードからトリガーハローパケットを受信しなかった場合には、タイマーを設定して設定された時間をカウンティングする段階と、
前記カウンティングされた時間が設定された時間を超過するかどうかをチェックして、設定された時間が経過されると、全ての隣接ノードからトリガーハローパケットを受信しなかった場合でもバッファーをフラッシュする段階と、を含むこと
を特徴とする請求項１０記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１２】
少なくとも一つ以上のSenderノードと、Senderノードから伝送されるブロードキャストパケットをReceiverノードにリレーするRelayerノードとを含む移動アドホックネットワークシステムにおけるブロードキャストデータ処理方法であって、
前記Senderノード又はRelayerノードから伝送されたブロードキャストパケットが受信されると、Receiverノードは、自機のバッファー内の隣接テーブルに保存された一番最近に受信したブロードキャスティングカウントナンバー(ＮＢＣ)と前記Senderノード又はRelayerノードから受信されたブロードキャストパケットに含まれたブロードキャスティングカウントナンバー(ＢＣ)を用いて前記Senderノード又はRelayerノードから伝送したブロードキャストパケットが全部受信されたか否かを判断する段階と、
該判断の結果、前記Senderノード又はRelayerノードから伝送されたブロードキャストパケットを全部受信した場合に、Receiverノードは、受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)と自機のバッファーサイズを比較する段階と、
該比較の結果、Receiverノードは、受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)が自機のバッファーサイズを超過するカウント値であれば、Senderノード又はRelayerノード内のバッファーをフラッシュするためのハローパケットを生成してブロードキャストパケットを伝送したノードへ伝送し、自機のバッファーをフラッシュした後に、受信されたブロードキャストパケットを用いて、フラッシュされた自機のバッファーの隣接テーブルをアップデートする段階と、を含むこと
を特徴とする移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１３】
前記Receiverノードのバッファー内の隣接テーブルは、ブロードキャストパケットをリレーしたRelayerノードＩＤ情報と、
ブロードキャストパケット伝送ノードから一番最近に受信したブロードキャスティングカウントナンバー情報と、
受信したブロードキャストパケットを保存するバッファーサイズ情報と、
受信したブロードキャストパケットの中でエラー又は損失によって受信することができなかったパケットリストについてのビットマップ情報と、を含むこと
を特徴とする請求項１２記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１４】
前記ブロードキャストパケットは、ＩＰヘッダーフィールドと、
ブロードキャストパケットを受信する受信側ノードの周辺に存在するRelayerノードのリスト情報を含むRelayerノードリスト情報フィールドと、
該当ノードから伝送されるブロードキャストパケットについてのブロードキャスティングカウントナンバー情報フィールド及びブロードキャストデータフィールドと、を含むこと
を特徴とする請求項１２記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１５】
前記Receiverノードは、前記Relayerノードからブロードキャストパケットを受信した場合に、一定時間の間隔又は一定パケット量によって周期的にブロードキャストパケット受信確認情報を含むハローパケットを生成して、前記Relayerノード又はRelayerノードを通じてSenderノードへ伝送する段階をさらに含むこと
を特徴とする請求項１２記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１６】
前記ReceiverノードからRelayerノード又はRelayerノードを通じてSenderノードへ伝送されるハローパケットは、パケットタイプ情報フィールドと、
ブロードキャストパケットの受信可否についての応答情報フィールドと、
予約フィールドを含むフラッグ情報フィールドと、
自機と隣接したRelayerノードのＩＤ情報フィールドと、
ブロードキャスティングカウントナンバー(ＢＣ)情報フィールドと、
ブロードキャストパケットを受信することができなかった場合の損失されたパケットのビットマップ情報フィールドと、
Senderと隣接したRelayerノードのＩＤ情報及びブロードキャストパケットを受信することができなかった場合の応答情報であるNACK Info情報を含む隣接Relayerノード情報フィールドと、
ブロードキャストパケットを受信することができなかったRelayerノード又はSenderノードに対応するＩＤ情報と、該当ノードから受信することができなかったブロードキャストパケットのＩＤ情報とを含むブロードキャスト再伝送情報フィールドと、を含むこと
を特徴とする請求項１２又は１５記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１７】
前記Relayerノードから伝送したブロードキャストパケットが全部受信されたか否かを判断する段階で、前記Relayerノードから伝送したブロードキャストパケットを全部受信することができなかった場合に、受信されたブロードキャストパケットに含まれたブロードキャスティングカウントナンバー(ＢＣ)が一番最近に受信したブロードキャスティングカウントナンバーの次のカウントナンバー(ＮＢＣ＋１)より大きいか否かを判断する段階と、
a) 該判断の結果、Relayerノードから現在まで伝送したブロードキャスティングカウントナンバーが現在まで受信したブロードキャスティングカウントナンバーより大きい場合、自機の隣接テーブルに損失されたパケットリストをアップデートした後に、ハローパケットの伝送を通じて損失されたパケットの再伝送を受ける段階と、
b) Relayerノードから現在まで伝送したブロードキャスティングカウントナンバーが現在まで受信したブロードキャスティングカウントナンバーより大きくない場合には、自機は全てのパケットを受信したにもかかわらず、他のReceiverノードからの損失されたパケットの再伝送要求によって該当パケットを受信したと判断して、受信されたブロードキャストパケットを廃棄する段階と、を含むこと
を特徴とする請求項１２記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１８】
前記ハローパケットを生成して前記Relayerノード又はRelayerノードを通じてSenderノードへ伝送する段階で、Receiverノードは、自機のバッファー内の隣接テーブルに保存されたブロードキャストパケットを伝送した各Senderノード又はRelayerノードに関するブロードキャストデータのビットマップ情報を順次に検索して、各ノード別に損失されたパケットの存在するか否かを判断する段階と、
該判断の結果、損失されたパケットが存在する場合には、前記隣接テーブルのビットマップを用いて、損失されたパケットを要求するためのハローパケットを生成した後に、該当ブロードキャストパケットを伝送したRelayerノード又はRelayerノードを通じてSenderノードへ該ハローパケットを伝送する段階と、を含むこと
を特徴とする請求項１２記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項１９】
前記Receiver ノードから伝送されたハローパケットを受信したRelayerノード又はSenderノードは、自機のバッファー内の隣接テーブルに存在しない新しいReceiverノードからのハローパケットが受信されたか否かを判断する段階と、
該判断の結果、隣接テーブルに存在しているノードからのハローパケットを受信した場合には、受信されたハローパケットが、フル(Full)のバッファーをフラッシュするためのトリガーハローパケットであるかを判断する段階と、
受信されたパケットがトリガーハローパケットではない一定周期でブロードキャストパケット受信可否を知らせるハローパケットである場合に、受信されたハローパケットからビットマップ情報をチェックして、損失されたパケットが存在するか否かを判断する段階と、
該判断の結果、損失されたパケットが存在する場合に、損失されたパケットに相応するブロードキャストパケットをハローパケットを伝送したReceiverノードへ伝送した後に、自機の隣接テーブルをアップデートする段階と、を含むこと
を特徴とする請求項１８記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項２０】
前記Receiverノードから受信したハローパケットがトリガーハローパケットであるかを判断する段階で、受信されたハローパケットがトリガーハローパケットである場合に、バッファーフラッシュのために全ての隣接ノードからトリガーハローパケットを受信したか否かを判断する段階と、
a) 該判断の結果、全ての隣接ノードからトリガーハローパケットを受信した場合にはバッファーをフラッシュし、
b) 全ての隣接ノードからトリガーハローパケットを受信しなかった場合には、タイマーを設定して設定された時間をカウンティングする段階と、
前記カウンティングされた時間が設定された時間を超過するかどうかをチェックして、設定された時間が経過されると、全ての隣接ノードからトリガーハローパケットを受信しなかった場合でもバッファーをフラッシュする段階と、を含むこと
を特徴とする請求項１９記載の移動アドホックネットワークにおけるブロードキャストデータ処理方法。
【請求項２１】
少なくとも一つ以上のSenderノードと、Senderノードから伝送されるブロードキャストパケットをReceiverノードにリレーするRelayerノードと、を含む移動アドホックネットワークシステムで、ブロードキャストパケットを受信したReceiverノードから伝送されるハローパケットを前記Relayerノード又はSenderノードで処理する方法であって、
自機のバッファー内の隣接テーブルに存在しない新しいReceiverノードからハローパケットが受信されたか否かを判断する段階と、
該判断の結果、隣接テーブルに存在しているノードからハローパケットを受信した場合に、受信されたハローパケットが、フルのバッファーをフラッシュするためのトリガーハローパケットであるか否かを判断する段階と、
該判断の結果、受信されたパケットがトリガーハローパケットではない一定周期でブロードキャストパケット受信可否を知らせるハローパケットである場合に、受信されたハローパケットからビットマップ情報をチェックして、損失されたパケットが存在するか否かを判断する段階と、
該判断の結果、損失されたパケットが存在する場合に、損失されたパケットに相応するブロードキャストパケットをハローパケットを伝送したReceiverノードへ伝送した後に、自機の隣接テーブルをアップデートする段階と、を含むこと
を特徴とする移動アドホックネットワークにおけるハローパケット処理方法。
【請求項２２】
前記Receiverノードから受信したハローパケットがトリガーハローパケットであるかを判断する段階で、受信されたハローパケットがトリガーハローパケットである場合に、バッファーフラッシュのために全ての隣接ノードからトリガーハローパケットを受信したか否かを判断する段階と、
a) 該判断の結果、全ての隣接ノードからトリガーハローパケットを受信した場合にはバッファーをフラッシュし、
b) 全ての隣接ノードからトリガーハローパケットを受信していなかった場合には、タイマーを設定して設定された時間をカウンティングする段階と、
前記カウンティングされた時間が設定された時間を超過するかどうかをチェックして、設定された時間が経過されると、全ての隣接ノードからトリガーハローパケットを受信しなかった場合でもバッファーをフラッシュする段階と、を含むこと
を特徴とする請求項２１記載の移動アドホックネットワークにおけるハローパケット処理方法。
【請求項２３】
前記Receiverノードから伝送されるハローパケットは、パケットタイプ情報フィールドと、
ブロードキャストパケットの受信可否についての応答情報フィールドと、
予約フィールドを含むフラッグ情報フィールドと、
自機と隣接したRelayerノードのＩＤ情報フィールドと、
ブロードキャスティングカウントナンバー(ＢＣ)情報フィールドと、
ブロードキャストパケットを受信することができなかった場合の損失されたパケットのビットマップ情報フィールドと、
Senderと隣接したRelayerノードのＩＤ情報及びブロードキャストパケットを受信することができなかった場合の応答情報であるNACK Info情報を含む隣接Relayerノード情報フィールドと、
ブロードキャストパケットを受信することができなかったRelayerノード又はSenderノードに対応するＩＤ情報と、該当ノードから受信することができなかったブロードキャストパケットのＩＤ情報を含むブロードキャスト再伝送情報フィールドと、を含むこと
を特徴とする請求項２１記載の移動アドホックネットワークにおけるハローパケット処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動アドホックネットワークにおけるブロードキャストデータ処理方法に関し、特に、移動アドホックネットワーク(ＭＡＮＥＴ ：Mobile Ad-hoc Network)環境でブロードキャストデータを伝送する際の、帯域幅の効率的な使用及び信頼性を向上させた移動アドホックネットワークにおけるブロードキャストデータ処理方法に関する。
【背景技術】
【０００２】
一般的に、インターネットでの伝送制御プロトコル/インターネットプロトコル(TCP/IP)は、大きく３種の構成要素、即ち、ホスト(コンピューター)と、ホストが連結されている物理的ネットワークと、物理的ネットワークを相互連結するルータ(Router)と、からなっている。このような構成要素による物理的ネットワークの構築を支援するために、広範囲な地域通信網(ＬＡＮ)と広域通信網(ＷＡＮ)のデータリンク技術が用いられる。
【０００３】
インターネットでのＴＣＰ/ＩＰは、ピア・ツー・ピア（Ｐ２：Peer-to-Peer）コンピューターネットワークでデータが交換される方法を管轄するための規則を定義した一連のプロトコル集であり、その中でＩＰは、非接続型での最も実効的なデータ伝達サービスを提供するインターネットプロトコルである。
【０００４】
ＩＰを使う移動ネットワーク形態の中で現在標準化されているものとして、移動性を支援するＩＰ(Mobility Support IP : Mobile IP)があり、これはスィッチ網で使われる無線電話機の形態に類似しており、無線ホストがワンホップ(ONE−HOP)距離の有線ネットワークと連結された基地局からデータの伝送を受けて通信する方式である。
【０００５】
一方、移動アドホックネットワークは、多数のノードが必要なインフラストラクチャ(Infrastructure)を構成することが経済的に不利な或いは物理的に困難な環境で、インターネットのような大型通信網のサービスだけでなく各ノード間の通信の支援に重点を置いたネットワークである。ここで、移動アドホックネットワークを構成する各ノードは、制約事項無しに自由に移動できるが、資源（resouces）使用量と電力の使用が制限されるので、既存の有線網でのルーティングプロトコルをそのまま使うことができない。
【０００６】
現在、ルーティングプロトコルは、大きくリアクティブ方式とプロアクティブ方式で区分できる。リアクティブ方式によれば、各移動ノードは、データの伝送前にだけ制御メッセージを用いてデータが伝送される最短経路を探した後に、その最短経路を通じてデータを伝送する。
【０００７】
一方、プロアクティブ方式を使う移動ノードは、他の移動ノードへの経路と距離を常に探索するために、制御パケットを周期的に伝送しており、このため、データの伝送時には、既に知られた最短経路を通じて、即時データの伝送を始めることができる。
【０００８】
アドホックネットワークにおいては、無線メディア(wireless media)がノード間で共有され、アドホックネットワークを構成する全てのノードは、必要に応じていつでもデータを伝送することができる。
【０００９】
その結果、無線メディアでは、共有チャンネルに対する競合(contention)が発生する。すなわち、無線メディアでは、有線メディア(wire media)と比較すると通信資源(resource)が制限的であり、このような競合の結果として発生する衝突(collision)によりデータが遺失される、という大きな問題がある。
【００１０】
このような問題を解決するために、アドホックネットワーク上のノードは、データの伝送時に伝送ノード(Sender Node)と受信ノード(Receiver Node)の間のＲＴＳ(Request To Send)とＣＴＳ(Clear To Send)の制御メッセージ(control message)を利用して、競合による衝突問題を解決する。
【００１１】
しかしながら、この方法は、ユニキャストデータ(unicast data)に該当し、アドホックネットワーク環境では、ノードは、ネットワーク情報やルーティング経路の情報を提供する重要な制御データを、ブロードキャスト通信によって使用しているが、ブロードキャストデータ(broadcasting data)に対しては、衝突によるデータ遺失を解決する効果的な方策がない。
【００１２】
このような無線メディアでの競合による衝突を解決するために、フラディング(flooding) 方式や、リレイヤーノード(relayer node)を指定してブロードキャストデータを処理する方式などが研究されている。
【００１３】
このようなアドホックネットワークにおけるデータ伝送方式について、添付した図１乃至図４を参照して簡単に説明する。
【００１４】
図１は、一般的なアドホックネットワークにおいて、フラディング方式を用いたデータ伝送過程を示す図であり、図２は、図１に示すフラディング方式によるブロードキャストパケットの伝送方法についての動作フローチャートを概略的に示す図である。
【００１５】
図１に示すフラディング方式は、アドホックネットワークを構成する多数のノード(Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ)がある状況で、Ｂノードがブロードキャストデータを伝送すると、アドホックネットワーク内のすべてのノード(Ａ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇノード)が、隣接する各ノードにデータを伝送する方式である。
【００１６】
ここで、フラディング方式を通じてパケットを伝送する方法を、図２に示すフローチャートを参照して簡単に説明する。
【００１７】
まず、パケットが受信されると(Ｓ１０１)、受信されたパケットがブロードキャストパケットであるか否かを判断する(Ｓ１０２)。
【００１８】
もし、受信されたパケットがブロードキャストパケットではないユニキャストパケットである場合には、一つの隣接ノードにパケットを伝送し(Ｓ１０４)、反対に、受信されたパケットがブロードキャストパケットである場合には、受信されたブロードキャストパケットを、隣接する全てのノードに伝送する(Ｓ１０３)。
【００１９】
このようなフラディング方式を通じてパケットを伝送する方式は、ブロードキャストデータのフラディングを通じて衝突が発生しても同一のデータを重複受信/発信する可能性が高くなるため、データ伝送の信頼度を高めることができる長所があるが、短所としては、フラディング方式を使うことで同一データの重複受信/発信を通じて数多くの衝突が発生するとともに、帯域幅の浪費がひどくなる問題がある。
【００２０】
次に、リレイヤーを指定して伝送する方式について、図３及び図４を参照して簡単に説明する。
【００２１】
図３は、一般的なアドホックネットワークでリレイヤーを選定する方式を用いたデータ伝送過程を示す図であり、図４は、図３に示すリレイヤーを選定する方式を用いたブロードキャストパケット伝送方法についての動作フローチャートを概略的に示す図である。
【００２２】
図３に示すように、Ｂノードがブロードキャストデータを伝送するときには、ＡノードとＣノードのみをリレイヤーノード(Relayer Node)として指定して、指定されたリレイヤーノード(Ａノード及びＣノード)だけがブロードキャストデータを他のノードにリレーできるようにする。
【００２３】
この方式では、リレイヤーノードではない他のノードは、受信ノードになる。
【００２４】
即ち、リレイヤーを選定する方式を通じたデータ伝送過程は、図４に示すように、まず、パケットが受信されると(Ｓ２０１)、受信されたパケットがブロードキャストパケットであるか否かを判断する(Ｓ２０２)。
【００２５】
その判断の結果、受信されたパケットがブロードキャストパケットではないユニキャストパケットである場合には、一つの隣接ノードに受信されたパケットを伝送し(Ｓ２０３)、受信されたパケットがブロードキャストパケットである場合には、パケットを受信した自機がリレイヤーノードであるか否かを判断する(Ｓ２０４)。
【００２６】
もし、自機がリレイヤーノードではない場合には、受信されたパケットをどんなノードにも伝送することができないものとし(Ｓ２０５)、反対に、自機がリレイヤーノードである場合には、受信されたブロードキャストパケットを、隣接する全てのノードへ伝送する処理を行う(Ｓ２０６)。
【００２７】
このような方式は、フラディング方式とは反対に、データの重複受信/発信を減らして帯域幅無駄使いを減らすことができる長所があるが、データ伝送の信頼性が落ちてネットワークトポロジーが随時に変わるアドホックネットワークでリレイヤーを選定するには困難がある。
【００２８】
結局、上述のように、ＭＡＮＥＴ環境でブロードキャストデータを信頼性あるように伝送するためのフラディング方式は、帯域幅の浪費が大きい問題点があり、一方、リレイヤーノードを指定する方式は、帯域幅の無駄使いを減らすことができるが信頼性が落ちる問題点がある。
【発明の開示】
【発明が解決しようとする課題】
【００２９】
したがって、本発明は上述したような従来技術の問題点を解決するためになされたもので、その目的は、移動アドホックネットワークでブロードキャストデータを送信する際に、帯域幅の効率的な使用と信頼性向上の観点でトレードオフ(trade-off)関係を持たせることにより、帯域幅を効果的に使用しながら信頼性も向上させることができる移動アドホックネットワークにおけるブロードキャストデータ処理方法を提供することにある。
【課題を解決するための手段】
【００３０】
前記目的を達成するための本発明による移動アドホックネットワークにおけるブロードキャストデータ処理方法の一つの側面によれば、伝送ノードから伝送されたブロードキャストパケットが受信されると、バッファー内の隣接テーブルに保存された一番最近に受信したブロードキャスティングカウントナンバー(ＮＢＣ)と、前記伝送ノードから受信されたブロードキャストパケットに含まれたブロードキャスティングカウントナンバー(ＢＣ)と、を用いて、前記伝送ノードから伝送したブロードキャストパケットが全部受信されたか否かを判断する段階と、前記伝送ノードから伝送したブロードキャストパケットを全部受信した場合に、受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)と自機のバッファーサイズとを比較する段階と、前記受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)が自機のバッファーサイズを超過するカウント値であれば、伝送ノード側のバッファーをフラッシュするためのハローパケットを生成して伝送ノードへ伝送し、自機のバッファーをフラッシュした後に、受信されたブロードキャストパケットを用いてフラッシュされた自機のバッファーの隣接テーブルをアップデートする段階と、を含む。
【００３１】
好ましくは、前記バッファー内の隣接テーブルは、ブロードキャストパケットを伝送した伝送ノードＩＤ情報と、ブロードキャストパケットの伝送ノードから一番最近に受信したブロードキャスティングカウントナンバー(ＮＢＣ : Latest Neighbor's Broadcasting Count Number)情報と、受信したブロードキャストパケットを保存するバッファーサイズ情報と、受信したブロードキャストパケットの中でエラー又は損失により受信することができなかったパケットリストについてのビットマップ情報と、を含む。
【００３２】
好ましくは、前記伝送ノードは、ブロードキャストパケットを生成して伝送するSenderノードを通じて伝送されるブロードキャストパケットを受信側ノードにリレーするRelayerノードである。
【００３３】
好ましくは、前記ブロードキャストパケットは、ＩＰヘッダー(IP Header)フィールドと、ブロードキャストパケットを受信する受信側ノードの周辺に存在するRelayerノードのリスト情報を含むRelayerノードリスト情報フィールドと、該当ノードから伝送されるブロードキャストパケットについてのブロードキャスティングカウントナンバー情報フィールド及びブロードキャストデータフィールドと、を含む。
【００３４】
好ましくは、前記バッファーサイズを比較する段階で、前記受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)が自機のバッファーサイズを超過しないカウント値である場合には、受信されたブロードキャストパケット情報をバッファーの隣接テーブルに挿入する段階を含む。
【００３５】
好ましくは、前記伝送ノードからブロードキャストパケットを受信した場合に、一定時間の間隔で又は一定パケット量によって周期的にブロードキャストパケットの受信確認情報を含むハローパケットを生成して前記伝送ノードへ伝送する段階をさらに含む。
【００３６】
好ましくは、前記ハローパケットは、パケットタイプ情報フィールドと、ブロードキャストパケットの受信可否についての応答情報(NACK, ACK)フィールドと、予約(Reserved)フィールドを含むフラッグ情報フィールドと、自機と隣接した伝送ノードのＩＤ情報フィールドと、ブロードキャスティングカウントナンバー(ＢＣ)情報フィールドと、ブロードキャストパケットを受信することができなかった場合の損失されたパケットのビットマップ情報フィールド(NACK MAP)と、Senderと隣接したノードのＩＤ情報及びブロードキャストパケットを受信することができなかった場合の応答情報であるNACK Info情報を含む隣接ノード情報フィールド(Neighbor Info Field)と、ブロードキャストパケットを受信することができなかったノードに対応するＩＤ情報(SRC(Source Address))と、該当ノードから受信することができなかったブロードキャストパケットのＩＤ情報(Packet ID)を含むブロードキャスト再伝送情報フィールド(Retransmission Info Feild)と、を含む。
【００３７】
好ましくは、前記伝送ノードから伝送したブロードキャストパケットが全部受信されたか否かを判断する段階で、前記伝送ノードから伝送したブロードキャストパケットを全部受信していない場合に、受信されたブロードキャストパケットに含まれたブロードキャスティングカウントナンバー(ＢＣ)値が一番最近に受信したブロードキャスティングカウントナンバーの次のカウントナンバー(ＮＢＣ＋１)より大きいか否かを判断する段階と、a) 該判断の結果、伝送ノードから現在まで伝送したブロードキャスティングカウントナンバーが現在まで受信したブロードキャスティングカウントナンバーより大きい場合には、自機の隣接テーブルに損失されたパケットリストをアップデートした後に、ハローパケットの伝送を通じて損失されたパケットの再伝送を受ける段階と、b) 伝送ノードから現在まで伝送したブロードキャスティングカウントナンバーが現在まで受信したブロードキャスティングカウントナンバーより大きくない場合には、自機は全てのパケットを受信したにもかかわらず、他のノードから損失されたパケットの再伝送要求によって該当パケットを受信したと判断して、受信されたブロードキャストパケットを廃棄(Discard)する段階と、を含む。
【００３８】
好ましくは、前記ハローパケットを生成して前記伝送ノードへ伝送する段階は、前記バッファー内の隣接テーブルに保存されたブロードキャストパケットを伝送した各ノードに関するブロードキャストデータのビットマップ情報を順次に検索して、各ノード別に損失されたパケットが存在するか否かを判断する段階と、該判断の結果、損失されたパケットが存在する場合には、前記隣接テーブルのビットマップを用いて、損失されたパケットを要求するためのハローパケットを生成した後に、該当ブロードキャストパケットを伝送したノードへ該ハローパケットを伝送する段階と、を含む。
【００３９】
好ましくは、前記伝送されたハローパケットを受信した伝送ノードは、自機のバッファー内の隣接テーブルに存在しない新しいノードからのハローパケットが受信されたか否かを判断する段階と、該判断の結果、隣接テーブルに存在しているノードからのハローパケットを受信した場合には、受信されたハローパケットが、バッファーをフラッシュするためのトリガーハローパケット(Triggered Hello Packet)であるか否かを判断する段階と、受信されたパケットがトリガーハローパケットではない一定周期でブロードキャストパケット受信可否を知らせるハローパケットである場合に、受信されたハローパケットからビットマップ情報をチェックして、損失されたパケットが存在するか否かを判断する段階と、該判断の結果、損失されたパケットが存在する場合には、損失されたパケットに相応するブロードキャストパケットをハローパケットを伝送したノードへ伝送した後に、自機の隣接テーブルをアップデートする段階と、を含む。
【００４０】
好ましくは、前記トリガーハローパケットであるかを判断する段階で、受信されたハローパケットがトリガーハローパケットである場合に、バッファーフラッシュのために全ての隣接ノードからトリガーハローパケットを受信したか否かを判断する段階と、a) 該判断の結果、全ての隣接ノードからトリガーハローパケットを受信した場合にはバッファーをフラッシュし、b) 全ての隣接ノードからトリガーハローパケットを受信しなかった場合には、タイマーを設定して設定された時間をカウンティングする段階と、前記カウンティングされた時間が設定された時間を超過するかどうかをチェックして、設定された時間が経過されると、全ての隣接ノードからトリガーハローパケットを受信しなかった場合でもバッファーをフラッシュする段階と、を含む。
【００４１】
また、本発明による少なくとも一つ以上のSenderノード、Senderノードから伝送されるブロードキャストパケットをReceiverノードにリレーするRelayerノードを含む移動アドホックネットワークシステムにおけるブロードキャストデータ処理方法の他の側面によれば、前記Senderノード又はRelayerノードから伝送されたブロードキャストパケットが受信されると、Receiverノードは、自機のバッファー内の隣接テーブルに保存された一番最近に受信したブロードキャスティングカウントナンバー(ＮＢＣ)と前記Senderノード又はRelayerノードから受信されたブロードキャストパケットに含まれたブロードキャスティングカウントナンバー(ＢＣ)を用いて前記Senderノード又はRelayerノードから伝送したブロードキャストパケットが全部受信されたか否かを判断する段階と、該判断の結果、前記Senderノード又はRelayerノードから伝送されたブロードキャストパケットを全部受信した場合に、Receiverノードは、受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)と自機のバッファーサイズを比較する段階と、該比較の結果、Receiverノードは、受信したブロードキャストパケットのブロードキャスティングカウントナンバー(ＢＣ)が自機のバッファーサイズを超過するカウント値であれば、Senderノード又はRelayerノード内のバッファーをフラッシュするためのハローパケットを生成してブロードキャストパケットを伝送したノードへ伝送し、自機のバッファーをフラッシュした後に、受信されたブロードキャストパケットを用いて、フラッシュされた自機のバッファーの隣接テーブルをアップデートする段階と、を含む。
【００４２】
一方、本発明による少なくとも一つ以上のSenderノードと、Senderノードから伝送されるブロードキャストパケットをReceiverノードにリレーするRelayerノードと、を含む移動アドホックネットワークシステムで、ブロードキャストパケットを受信したReceiverノードから伝送されるハローパケットを前記Relayerノード又はSenderノードで処理する方法によれば、自機のバッファー内の隣接テーブルに存在しない新しいReceiverノードからハローパケットが受信されたか否かを判断する段階と、該判断の結果、隣接テーブルに存在しているノードからハローパケットを受信した場合に、受信されたハローパケットがバッファーが、フルになってバッファーをフラッシュするためのトリガーハローパケットであるか否かを判断する段階と、該判断の結果、受信されたパケットがトリガーハローパケットではない一定周期でブロードキャストパケット受信可否を知らせるハローパケットである場合に、受信されたハローパケットからビットマップ情報をチェックして、損失されたパケットが存在するか否かを判断する段階と、該判断の結果、損失されたパケットが存在する場合に、損失されたパケットに相応するブロードキャストパケットをハローパケットを伝送したReceiverノードへ伝送した後に、自機の隣接テーブルをアップデートする段階と、を含むことができる。
【００４３】
好ましくは、前記Receiverノードから受信したハローパケットがトリガーハローパケットであるかを判断する段階で、受信されたハローパケットがトリガーハローパケットである場合に、バッファーフラッシュのために全ての隣接ノードからトリガーハローパケットを受信したか否かを判断する段階と、a) 該判断の結果、全ての隣接ノードからトリガーハローパケットを受信した場合にはバッファーをフラッシュし、b) 全ての隣接ノードからトリガーハローパケットを受信していなかった場合には、タイマーを設定して設定された時間をカウンティングする段階と、前記カウンティングされた時間が設定された時間を超過するかどうかをチェックして、設定された時間が経過されると、全ての隣接ノードからトリガーハローパケットを受信しなかった場合でもバッファーをフラッシュする段階と、を含む。
【発明の効果】
【００４４】
本発明による移動アドホックネットワークにおけるブロードキャストデータ処理方法は、移動アドホックネットワークでブロードキャストデータを送信する際に、帯域幅の効率的な使用と信頼性向上の観点でトレードオフ関係を持たせることにより、帯域幅を効率的に使用しながら信頼性を向上させる効果がある。
【発明を実施するための最良の形態】
【００４５】
以下、本発明による移動アドホックネットワークにおけるブロードキャストデータ処理方法の実施の形態について、添付図面を参照して詳細に説明する。
【００４６】
本発明による移動アドホックネットワークにおけるブロードキャストデータ処理方法の実施形態は、図３及び図４に示すように、ＭＡＮＥＴ環境でブロードキャストデータを伝送するノードを選定する方法として、リレイヤー方式を用いる。
【００４７】
まず、リレイヤーとして選定されたリレイヤーノードは、リレーするブロードキャストデータを、ＩＰオプションヘッダーフィールド(IP Option Header Field)を使用することにより、カウントナンバー(count number)を増加させながら伝送する。
【００４８】
また、リレイヤーノードは、自機がリレーしたブロードキャストデータと共に、そのブロードキャストデータのカウントナンバーを維持管理する。
【００４９】
リレイヤーノードは、該リレイヤーノードから伝送されるブロードキャストデータを周期的に受信するための受信ノードとして指定されたノードから送られて来たハローブロードキャスティングパケット(hello broadcasting packet)に応答して、現在まで当該受信ノードに伝送したブロードキャストデータのブロードキャスティングカウントナンバー(broadcasting count number)情報を提供する。
【００５０】
受信ノードとして指定されたノードは、自機が受信した全てのリレイヤーノードのブロードキャスティングカウントナンバーを、データベース内に、図５に示すようなハフマンテーブル(Huffman table)形態で管理する。
【００５１】
即ち、図５に示すように、受信ノードによって管理されるハフマンテーブル(隣接テーブル)は、ブロードキャストデータをリレーしたリレイヤーノードのＩＤと、リレイヤーノードから最近まで受信したブロードキャスティングカウントナンバー(ＮＢＣ : Latest Neighbor's Broadcasting Count Number)と、受信したブロードキャストデータを保存するバッファーのサイズ及び受信したブロードキャストデータの中でエラー又は損失により受信することができなかったパケットリスト(Missing Packet List:Bit Map)情報（すなわちビットマップ情報）と、を保存管理するためのテーブルである。
【００５２】
当該受信ノードは、リレイヤーノードから受信したハローパケット(hello packet)のブロードキャスティングカウントナンバーと、データベースに保存されている該当リレイヤーノードの最近ブロードキャスティングカウントナンバーと、を比較して、この情報を、遺失されたパケットに関してＳＡＣＫ(Selective Acknowledgement)方式を用いてリレイヤーノードに伝送するハロー応答(hello response)パケットとして提供することで、遺失されたパケットの再送信を受ける。結局、ＳＡＣＫ方式を用いることで、パケット再送信要求パケットの使用量を減らして、帯域幅の無駄使いを抑えることが可能となる。
【００５３】
リレイヤーノードのブロードキャストパケット再送信用バッファーサイズを考慮して、受信ノードは、リレイヤーノードのバッファーサイズを超えるブロードキャスティングカウントナンバーを受信した場合には、トリガーハロー応答(triggered hello response)パケットを伝送することで、当該リレイヤーノードのブロードキャストパケット再送信バッファーをフラッシュ(flush)するとともに、ブロードキャスティングカウントナンバーを０の値で始める。
【００５４】
このようなメカニズムとすることで、ブロードキャスティングカウントナンバーが無限に増加するオーバーヘッドとハロー応答パケットのサイズを減らす効果が得られるとともに、リレイヤーノードのブロードキャストバッファーを効果的に管理することが可能となる。
【００５５】
かかる動作について、添付した図面を参照してより詳細に説明する。
【００５６】
図６は、本発明による移動アドホックネットワークにおけるブロードキャストデータ処理方法に適用されるプロトコル動作シーケンスを示す図である。
【００５７】
図６に示すように、ノードＡ（１０）及びＢ（２０）は各々ブロードキャストパケットを生成するsender Ａ１０及びsender Ｂ２０と仮定し、ノードＣ（３０）はノードＡ１０及びＢ２０(sender Ａ，Ｂ)から受信したブロードキャストパケットをノードＤにリレーするRelayer Ｃ３０と仮定する。
【００５８】
また、ノードＤ（４０）は、Relayer Ｃ３０ノードを介してリレーされたブロードキャストパケットを受信するReceiver Ｄ４０と仮定する。
【００５９】
ここで、Sender Ａ１０，Ｂ２０が各々１個ずつブロードキャストパケット(Broadcast(Ａ．１)，Broadcast(Ｂ．１))を生成して、各々Relayer Ｃ３０へ伝送すると(ステップＳ３０１，ステップＳ３０３)、このブロードキャストパケットをReceiver Ｄ４０にリレーするRelayer Ｃ３０は、自機からリレーされるブロードキャストパケット(Broadcast(Ａ．１)，Broadcast(Ｂ．１))にカウントナンバーに関する情報(Broadcast(Ｃ．１)，Broadcast(Ｃ．２))を記録して、Receiver Ｄ４０へ伝送する(ステップＳ３０２，ステップＳ３０４)。
【００６０】
このようにブロードキャストパケットをリレーする際に、Relayer Ｃ３０は、周期的に各ノード１０，２０、及び４０（すなわちSender Ａ，Ｂ、及びReceiver Ｄ）にハローパケットを伝送する。即ち、図６のステップＳ４０１のように、ＭＡＮＥＴ環境では各ノードに周期的にハローパケットが伝送される。ここでは、Relayer Ｃ３０は、自機がブロードキャストしたパケットのカウントナンバーと、隣接するワンホップ(one-hop)ノードから伝送を受けた最近のブロードキャスティングカウントナンバー情報と、を含むハローパケット(Hello(C.2，A.1，B.1))を、各ノード、即ち、Sender Ａ１０，Ｂ２０、及びReceiver Ｄ４０へ伝送する。結局、Relayer Ｃ３０は、自機のノード情報及び自機がリレーしたブロードキャストパケットのカウントナンバー情報を含む情報(Hello(C.2)）と、ブロードキャスティング情報を自機に伝送したSenderノード情報と、Sender Ａ１０，Ｂ２０で生成して自機に伝送したブロードキャストパケットのカウントナンバー情報(Hello(A.1, B.1)）とを、予め設定された時間単位又は受信パケット数単位に従った一定周期で、各ノード１０，２０，４０へと伝送する（ステップＳ４０１）。
【００６１】
そして、ステップＳ５０１で、Sender Ａ１０がブロードキャストパケットを生成してブロードキャスティングカウントナンバー情報(Broadcast(A.2))とともにRelayer Ｃ３０へ伝送すると、Relayer Ｃ３０は、Sender Ａ１０から受信したブロードキャストパケットをReceiver Ｄ４０にリレーすることになり、この際にも上述したように、当該ブロードキャストパケットに、Relayer Ａ１０からリレーされたブロードキャスティングカウントナンバー情報を含めて、一緒に伝送する(ステップＳ５０２)。
【００６２】
一方で、図６のステップＳ５０３及びステップＳ５０４のように、Sender Ｂ２０ノードから伝送されたブロードキャストパケットが、Relayer Ｃ３０ノードによってReceiver Ｄ４０ノードに伝送される過程で、衝突(collision)により損失された場合には、Relayer Ｃ３０は、周期的なハローパケットを利用して、自機が周期的にリレーしたブロードキャスティングカウントナンバー情報と、Sender Ａ１０，Ｂ２０から各々受信したブロードキャスティングカウントナンバー情報と、を含むハローパケット((Hello(C.5，A.2，B.3))を、各ノード１０，２０，４０へ伝送する(ステップＳ６０１)。
【００６３】
そして、このハローパケットを受信したReceiver Ｄ４０ノードは、図５に示すように、自機のデータベースに保存されたホフマンテーブル(隣接テーブル)を検索して、自機が受信することのできなかったブロードキャストパケットを確認した後に、受信することのできなかったブロードキャストパケットをRelayer Ｃ３０ノードに要求するためのハローパケット(例えば、Hello_r(C.4，C.5))を伝送する(ステップＳ６０２)。即ち、図６のステップＳ６０２に示すように、Relayer Ｃ３０ノードから伝送されたハローパケットに関して、Relayer Ｃ３０ノードが最近までリレーしたブロードキャストパケットのカウントナンバー「５」という情報に基づいて、Receiver Ｄ４０ノードは、自機が伝送を受けることができなかった４番と５番に関するブロードキャストパケットの再送信を、ハロー応答パケット(Hello_r(C.4，C.5))を用いて要請する。
【００６４】
したがって、このハロー応答パケットを受信したRelayer Ｃ３０は、Receiver Ｄ４０から要求された４番と５番についてのブロードキャストパケットを再伝送し、４番と５番についてのブロードキャストパケットを受信したReceiverＤ４０ノードは、該当パケットを図５に示されたテーブルにアップデートして保存管理する。
【００６５】
図６における最後のステップＳ６０３及びステップＳ６０４は、Relayer Ｃ３０ノードのブロードキャストパケットの再送信用バッファーのサイズが１０だと仮定した場合に、ブロードキャスティングカウントナンバー１０の送信を受けたReceiver Ｄ４０ノードによってトリガーされたハローパケットを示す。ここで、Relayer Ｃ３０ノードは、ワンホップ(one-hop)ノードからのトリガーハローパケットを成功裡に受信すれば、ブロードキャストパケット再送信バッファーをフラッシュする。
【００６６】
ここで、Sender Ａ１０，Ｂ２０、又はRelayer Ｃ３０から伝送されるブロードキャストパケットフォーマットと、Relayer Ｃ３０又はReceiver Ｄ４０から伝送されるハローパケットフォーマットについて、図７及び図８を参照して説明する。
【００６７】
図７は、本発明によるブロードキャストパケットについてのデータフォーマットを示す図で、図８は、本発明によるハローパケットについてのデータフォーマットを示す図である。
【００６８】
まず、図７に示されたブロードキャストパケットのフォーマットは、大きくＩＰヘッダー領域と、ＩＰオプションヘッダー領域及びブロードキャストデータ領域と、に区分することができる。ここで、ＩＰオプションヘッダー領域は、ブロードキャストデータを受信するノードの周辺Relayerノードのリスト情報を含むRelayerリスト情報領域と、該当ノードから伝送するブロードキャストパケットについてのブロードキャスティングカウントナンバー情報領域及びブロードキャストデータ領域と、に区分することができる。
【００６９】
一方、Relayerノード又はReceiverノードから伝送するハローパケットフォーマットについて説明すると、図８に示すように、ハローパケットは、パケットの種類を示すパケットタイプ情報領域（Type）と、フラッグ情報領域（Flag）と、隣接ノード、即ち、SenderノードのＩＤ情報領域(Neighbor ID）と、を含む。ここで、フラッグ情報領域は、ブロードキャストパケットの受信可否についての応答情報(NACK、ACK) 領域と、予約(Reserved)領域と、に区分することができる。
【００７０】
また、ハローパケットは、ブロードキャスティングカウントナンバー情報領域(ＢＣ)と、ブロードキャストパケットを受信することができなかった場合の損失されたパケットのビットマップ情報領域(NACK MAP)と、隣接ノード情報領域(Neighbor  Info  Field)と、ブロードキャスト再伝送情報領域(Retransmission Info Field)と、を含む。ここで、隣接ノード情報領域には、Senderと隣接したノードのＩＤ情報及びブロードキャストパケットを受信することができなかった場合の応答情報であるNACK Infoを含む。
【００７１】
また、ブロードキャスト再伝送情報領域には、ブロードキャストパケットを受信することができなかったノードに対応するＩＤ情報(SRC(Source Address))と、該当ノードから受信することができなかったブロードキャストパケットのＩＤ情報(Packet ID)と、を含む。
【００７２】
以下、Relayerノード又はReceiverノードでハローパケットを生成して、生成されたハローパケットをSenderノード又はRelayerノードへ伝送する過程について、図９を参照してステップ毎に説明する。
【００７３】
図９は、本発明によるハローパケット生成及び生成されたハローパケットを伝送する過程についての一の実施形態を示す動作フローチャートである。
【００７４】
図９に示すように、まず、いずれか一のRelayerノード又はSenderノード（以下、「該当処理ノード」とも言う。）は、ハローパケットを生成するために、図５に示された隣接テーブルを順次に検索して、隣接テーブルを全て検索したか否かを判断する(ステップＳ７０１)。
【００７５】
該判断の結果、隣接テーブルを全部検索していなかった場合には、この該当処理ノードは、順次に図５に示された隣接テーブルで各ノード別にビットマップフィールドを検索して、損失されたブロードキャストパケットが存在するかどうかを確認する(ステップＳ７０２)。
【００７６】
該確認の結果、任意のノードから伝送されたブロードキャストパケットで損失されたパケットが存在する場合には、該当処理ノードは、隣接テーブルの該当するノードのビットマップを参照して、損失されたパケットの再送信を要求するためのハローパケットを生成する(ステップＳ７０３)。
【００７７】
一方、任意のノードから伝送されたブロードキャストパケットで損失されたパケットが存在しない場合には、該当処理ノードは、Receiver側ノードで保存していたSender側ノードの最新ブロードキャスティングカウントナンバー(ＮＢＣ＋１)を含むハローパケットを生成する(ステップＳ７０４)。ここで、ＮＢＣ＋１とは、Sender側から伝送される次のブロードキャスティングカウントナンバーを意味する。例えば、Sender側で３０番目までブロードキャストパケットを伝送し、Relayerノード又はReceiverノード（すなわち該当処理ノード）がこれら全てのパケットを成功裡に受信した場合には、この該当処理ノードは、ＮＢＣ(３０)＋１＝３１というカウントナンバー情報を含めたハローパケットを生成して、Sender側へ伝送する。
【００７８】
該当処理ノードは、前記のような動作を反復的に実行して、自機の隣接テーブルに保存された全ての隣接ノードについてのブロードキャストパケット受信可否に関するビットマップ検索が完了して、検索結果に基づくハローパケットが生成されると、生成されたハローパケットをSenderノードへ伝送する(ステップＳ７０５)。
【００７９】
以下、Relayerノード又はSenderノードで、図９のような方法で生成されたハローパケットを受信する方法について、添付した図１０を参照してステップ毎に説明する。
【００８０】
図１０は、図９の過程を通じて生成されたハローパケットを受信して、受信されたハローパケットを処理する方法についての動作フローチャートである。
【００８１】
図１０に示すように、まず、いずれか一のRelayerノード又はSenderノード（以下、「該当処理ノード」とも言う。）は、自機の隣接テーブルに存在しなかった新しいノードからハローパケットが受信されたか否かを判断する(ステップＳ８０１)。
【００８２】
もし、新しいノードからハローパケットを受信した場合には、該当処理ノードは、その新しいノードを自機の隣接テーブルに挿入（登録）する(ステップＳ８０２)。
【００８３】
一方、ハローパケットの受信が、新しいノードからではなく、既に存在しているノードからのものである場合には、該当処理ノードは、受信されたハローパケットがトリガーハローパケットであるか否かを判断する(ステップＳ８０３)。ここで、ハローパケットは、二つのハローパケットに分類することができる。即ち、第一のものは、タイマーを設定して周期的に又は受信されたブロードキャスティングカウントナンバーを設定して周期的に伝送されるハローパケットであり、第二のものは、Senderノードの伝送バッファーが受信されたブロードキャストパケットで全部満ちている場合に、該当バッファーに保存された全てのブロードキャストデータをフラッシュするための目的に使われるトリガーハローパケットと、で区分できる。
【００８４】
即ち、ステップＳ８０３では、本ルーチンを実行するノードのバッファーがフル(Full)になる時点までブロードキャストして、隣接ノードが伝送バッファーをフラッシュするための目的で使うハローパケットであるか否かを判断する。
【００８５】
ここで、受信されたパケットがトリガーハローパケット、即ち、バッファーをフラッシュするためのハローパケットではない場合には、該当処理ノードは、受信されたハローパケットのビットマップ情報をチェックする(ステップＳ８０４)。
【００８６】
続いて、該当処理ノードは、該受信ハローパケットのビットマップ情報のチェック結果に基づいて、損失されたパケットが存在するか否かを判断して(ステップＳ８０５)、損失されたパケットが存在する場合には、損失されたパケットに相応するブロードキャストパケットをReceiverノード又はRelayerノード側へ伝送した後に、自機の隣接テーブルをアップデートする(ステップＳ８０６、ステップＳ８０７)。即ち、該当処理ノードは、隣接テーブルのビットマップ情報とＢＣ情報をアップデートする。
【００８７】
一方、前記ステップＳ８０５で、ビットマップチェックの結果、損失されたパケットが存在しない場合には、該当処理ノードは、自機の隣接テーブルのみをアップデートする。
【００８８】
また一方、前記ステップＳ８０３で、受信されたハローパケットがトリガーハローパケットである場合には、該当処理ノードは、バッファーフラッシュのために全ての隣接ノードからトリガーハローパケットを受信したか否かを判断する(ステップＳ８０８)。
【００８９】
この判断の結果、該当処理ノードは、全ての隣接ノードからトリガーハローパケットを受信した場合には、バッファーをフラッシュし(ステップＳ８１１)、反対に、全ての隣接ノードからのトリガーハローパケットを受信していない場合には、タイマーを設定する(ステップＳ８０９)。即ち、トリガーハローパケットを伝送しなかったノードが存在する後者の場合には、このノードのために無制限にバッファーをフラッシュしないで待つことは出来ないので、タイマーを用いて一定時間を設定する。
【００９０】
タイマーが設定されると、該当処理ノードは、カウントされた時間が設定時間を超過するかどうかをチェックして(ステップＳ８１０)、設定された時間が経過すると、トリガーハローパケットを受信しないにもかかわらず、バッファーをフラッシュする(ステップＳ８１１)。
【００９１】
次に、図１１を参照して、ブロードキャストデータの受信方法についてステップ毎に説明する。
【００９２】
図１１は、本発明によるRelayerノード又はReceiverノードでブロードキャストデータを受信する方法についての一例を示す動作フローチャートである。
【００９３】
まず、いずれか一のRelayerノード又はReceiverノードでブロードキャストパケットが受信されると(ステップＳ９０１)、ブロードキャストパケットを受信したノード（該当処理ノード）は、自機の隣接テーブルからＮＢＣ値をリードする(ステップＳ９０２)。即ち、一番最近に受信したブロードキャスティングカウントナンバーを読み出す。
【００９４】
続いて、該当処理ノードは、ＮＢＣ＋１の値がＢＣの値と同一であるか否かを判断する(ステップＳ９０３)。即ち、該当処理ノードは、一番最近のブロードキャスティングカウントナンバーの次に受信するブロードキャスティングカウントナンバー(ＮＢＣ＋１)と、ブロードキャスティングカウントナンバー(ＢＣ)とが、互いに同一であるか否かを判断する。これにより、Senderノード又はRelayerノードから伝送したブロードキャストパケットをReceiverノードで損失なしに全部受信したか否か、が判断される。
【００９５】
この判断の結果、ＮＢＣ＋1値とＢＣ値が互いに同一である場合、即ち、例えばReceiver側のノードが、ブロードキャストパケットを伝送するノードから伝送されたブロードキャストパケットを損失なしに全部受信した場合、さらに具体的には、例えばReceiver側のノードがブロードキャストパケットを伝送する任意のノードから３０番目のパケット(ＮＢＣ)を受信して、当該任意のノードが３１番目(ＢＣ)のブロードキャストパケットを現在伝送した場合で、ＮＢＣ＋１＝ＢＣとして損失されたパケットが存在しない場合には、該Receiver側のノードは、ＢＣ値がMAX_Count値より大きいか否かを判断する(ステップＳ９０４)。ここで、MAX_Count値は、Senderのバッファーサイズ値である。即ち、Receiver側ノードは、ブロードキャスティングカウントナンバーがSenderのバッファーサイズ値を超過するカウント値であるか否かを判断する。
【００９６】
この判断の結果、現在伝送されたブロードキャストカウント値(ＢＣ)がSenderのバッファーサイズを超過するカウント値である場合には、Receiver側ノードは、Sender側ノードへトリガーハローパケットを送信する(ステップＳ９０５)。このトリガーハローパケット即ち、バッファーをフラッシュするためのハローパケットを伝送した後に、Receiver側ノードは、新しいブロードキャスティングカウントナンバーにより隣接テーブルをアップデートする(ステップＳ９０６)。
【００９７】
一方、ステップＳ９０４の判断の結果、現在伝送されたブロードキャスティングカウント値(ＢＣ)がSenderのバッファーサイズを超過しない場合には、直ちにステップＳ９０６の処理を実行する。
【００９８】
また、ステップＳ９０３で、ＮＢＣ＋１の値がＢＣの値と同一ではない場合には、ＢＣの値がＮＢＣ＋１の値より大きい値であるか否かを判断する(ステップＳ９０７)。
【００９９】
この判断の結果、ＢＣの値がＮＢＣ＋１の値よりも大きい値である場合、即ち、Sender側から現在まで伝送したブロードキャスティングカウントナンバーが、Receiver側ノードから現在まで受信したブロードキャスティングカウントナンバーよりも大きい値である場合、例えば、Senderノードで３１番目のパケット(ＢＣ)を伝送したが、Receiverノードでは２９番目のパケット(ＮＢＣ)を受信して３０番目のパケットが損失された場合には、当該Receiver側ノードは、自機の隣接テーブルに、損失されたパケットのリストをアップデートし(ステップＳ９０９)、その後にハローパケットを通じて損失されたパケットの再伝送を受ける。
【０１００】
一方、ステップＳ９０７で、ＢＣの値がＮＢＣ＋１の値よりも大きくない場合、例えば、Receiver側ノードが３０番目のパケットを受信しなければならないのに、これより少ない２５番目のパケットを受信した場合、即ち、自機は全てのパケットを受信したにもかかわらず、他のノードから損失されたパケットの再送信要求によって該当パケットを受信した場合には、当該Receiver側ノードは、当該受信パケットを廃棄する(ステップＳ９０８)。
【０１０１】
図１２及び図１３には、上述した本発明による移動アドホックネットワークにおけるブロードキャストデータ処理方法と、従来技術によるフラディング方式及びリレイヤー方式を用いたブロードキャストパケット処理方法とを、ネットワークシミュレーターを通じて測定し、それらのパケット伝送率及び伝送量を比較した結果のグラフを示す。
【０１０２】
図１２は、従来技術と本発明の実施形態とによるパケット伝送率の測定結果を比較するためのグラフを示す図であり、図１３は、従来技術と本発明の実施形態とによるパケット伝送量の測定結果を比較するためのグラフを示す図である。
【０１０３】
図１２に示すように、本発明の実施形態によるパケット伝送率の測定結果は、従来技術によるフラディング方式の長所である、重複されたパケット伝送の信頼性ある伝送効果と類似しており且つ、より性能が良好であることが分かる。これは、従来技術によるフラディング方式は、多くのパケットを重複して伝送するが、パケットの衝突発生時に損失されたパケットを再伝送し、これにより信頼性が低下されるからである。
【０１０４】
また、図１３に示すように、従来技術によるフラディング方式は、伝送ノード数が多くなるほど、パケット伝送量が指数関数(Exponential)的に増加する。また、従来技術によるリレイヤー方式は、伝送ノード数の増加とは関係なく１００以下の一定の値を維持する。
【０１０５】
これに対して、本発明の実施形態によるブロードキャスト処理方式は、信頼性保障のためにリレイヤー方式よりは多くのパケットを伝送するが、フラディング方式のようにノード数が増加するほどパケット伝送量が急激に増加するようなことが無いことが分かる。
【図面の簡単な説明】
【０１０６】
【図１】一般的なアドホックネットワークでフラディング方式を用いた場合のデータ伝送過程を示す図である。
【図２】図１に示されたフラディング方式を用いてブロードキャストパケットを伝送する方法についての動作フローチャートを概略的に示す図である。
【図３】一般的なアドホックネットワークでリレイヤーを選定する方式を用いた場合のデータ伝送の流れを示す図である。
【図４】図３に示されたリレイヤーを選定する方式を用いてブロードキャストパケットを伝送する方法についての動作フローチャートを概略的に示す図である。
【図５】本発明による移動アドホックネットワークにおけるブロードキャストデータ処理方法を説明する図であり、ブロードキャストパケットを受信する受信ノードのデータベースに保存管理されるハフマンテーブル(隣接テーブル)を示す図である。
【図６】本発明による移動アドホックネットワークにおけるブロードキャストデータ処理方法に適用されるプロトコル動作シーケンスを示す図である。
【図７】本発明によるブロードキャストパケットについてのデータフォーマットを示す図である。
【図８】本発明によるハローパケットについてのデータフォーマットを示す図である。
【図９】本発明によるハローパケット生成及び生成されたハローパケットを伝送する過程についての動作フローチャートである。
【図１０】図９の過程を通じて生成されたハローパケットを受信して、受信されたハローパケットを処理する方法についての動作フローチャートある。
【図１１】本発明によるブロードキャストデータを受信する方法についての動作フローチャートである。
【図１２】従来技術と本発明によるパケット伝送率測定結果を比較するためのグラフを示す図である。
【図１３】従来技術と本発明によるパケット伝送量測定結果を比較するためのグラフを示す図である。
【符号の説明】
【０１０７】
１０  Sender Ａ(ノードＡ)
２０  Sender Ｂ(ノードＢ)
３０  Relayer Ｃ(ノードＣ)
４０  Receiver Ｄ(ノードＤ)
【図１】
2005124195.tif 000003
【図２】
2005124195.tif 000004
【図３】
2005124195.tif 000005
【図４】
2005124195.tif 000006
【図５】
2005124195.tif 000007
【図６】
2005124195.tif 000008
【図７】
2005124195.tif 000009
【図８】
2005124195.tif 000010
【図９】
2005124195.tif 000011
【図１０】
2005124195.tif 000012
【図１１】
2005124195.tif 000013
【図１２】
2005124195.tif 000014
【図１３】
2005124195.tif 000015