(57)【要約】【課題】アドホック無線通信ネットワークにおけるブロードキャストパケット通信において、パケットの爆発的な増大を抑制すると共に、パケットの実効的な伝播速度のばらつきを小さくし、高いパケット転送レートを実現すること。【解決手段】本無線端末１０では、端末周辺のパケット輻輳状態を調べるため、新たなパケットを受信すると、それと同一の受信パケット数をパケット数計数手段１４でカウントし、そのカウント数に基づいて転送するか否かを転送判定手段１５で決め、これに基づいて制御部１８が転送制御を行なう。その場合、受信パケット数をカウントする時間区間を、新たなパケットを受信した時点を基準にして、カウント開始時間をＴとし終了時間をＴと２Ｔの間で一様ランダムに選択した値とする。ただし、Ｔはパケット送信処理時間Δｔと衝突回避のための倍数Ｍの積である。【選択図】図１
2009212978.tif 000002
【特許請求の範囲】
【請求項１】
ブロードキャストパケットを中継転送する無線端末であって、
前記ブロードキャストパケット中の受信パケットの受信時を基準として計時を開始し、所定の最短終了時間と最長終了時間の間の値をとる確率変数により定まる終了時間の間の計時を行なう計時手段と、
前記計時手段によって計時されている間の前記受信パケットと同一のブロードキャストパケットの受信数を計数するパケット数計数手段と、
前記パケット数計数手段の計数結果に基づいてパケットの転送を行なうか否かを判定する転送判定手段と、
を備えたことを特徴とする無線端末。
【請求項２】
前記請求項１に記載の無線端末において、
前記計時手段における前記終了時間を、前記最短終了時間と前記最長終了時間の間の値をとる一様乱数を用いて決めたことを特徴とする無線端末。
【請求項３】
前記請求項２に記載の無線端末において
前記計時手段は、前記終了時間Ｔｆを、最短終了時間Ｔｓと最長終了時間Ｔｍの間を一様分布する乱数Ｔｒ（Ｔｓ≦Ｔｒ＜Ｔｍ）の選択値を用いて設定してその間の計時を行なうことを特徴とする無線端末。
【請求項４】
前記請求項３に記載の無線端末において、
前記計時手段は、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として、時間Ｔを方式最大長パケット送信時間ΔｔのＭ倍として、前記最短終了時間をＴｓ（０＜Ｔｓ≦Ｔ）、前記終了時間ＴｆをＴｓ以上（Ｔ＋Ｔｓ）未満の間でランダムな値に設定することを特徴とする無線端末。
【請求項５】
前記請求項４に記載の無線端末において、
前記計時手段は、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として計時を開始し、前記最短終了時間をＴ、終了時間Ｔｆを前記最短終了時間Ｔ以上２Ｔ未満の間でランダムな値に設定することを特徴とする無線端末。
【請求項６】
前記請求項１、２、３、４又は５に記載の無線端末において、
前記転送判定手段は、前記計数手段における計数結果であるパケットの受信数が予め定めた閾値Ｃ以上の場合は転送を禁止し、閾値Ｃ未満であれば転送する判定を行うことを特徴とする無線端末。
【請求項７】
前記請求項１、２、３、４又は５に記載する無線端末を複数個備え、これら無線端末相互間でブロードキャストパケットを中継転送することを特徴とするアドホック無線通信システム。
【請求項８】
複数の無線端末同士がパケットをマルチホップで中継転送するアドホック無線通信ネットワークにおけるブロードキャストパケットのパケット転送制御方法であって、
転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として計時を開始し、所定の最短終了時間と最長終了時間の範囲内の一様乱数を用いて決めた終了時間を設定する計時区間設定工程と、
前記計時区間の間における前記最初の受信パケットと同一のブロードキャストパケットの受信数を計数するパケット数計数工程と
前記パケット数計数工程の計数結果であるパケットの受信数に基づいてパケットの転送を行なうか否かを判定する転送判定工程と、
を備えたことを特徴とするパケット転送制御方法。
【請求項９】
前記請求項８に記載のパケット転送制御方法において、
前記計時区間設定工程は、終了時間Ｔｆを、最短終了時間Ｔｓと最長終了時間Ｔｍの間を一様分布する乱数Ｔｒ（Ｔｓ≦Ｔｒ＜Ｔｍ）の選択値を用いて設定することを特徴とするパケット転送制御方法。
【請求項１０】
前記請求項９に記載のパケット転送制御方法において、
前記計時区間設定工程は、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として、時間Ｔを方式最大長パケット送信時間ΔｔのＭ倍として、前記最短終了時間をＴｓ（０＜Ｔｓ≦Ｔ）、終了時間ＴｆをＴｓ以上時間（Ｔ＋Ｔｓ）未満の間でランダムな値に設定することを特徴とするパケット転送制御方法。
【請求項１１】
前記請求項１０に記載のパケットの転送制御方法において、
前記計時区間設定工程は、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として計時を開始し、前記最短終了時間をＴ、終了時間Ｔｆを前記最短終了時間Ｔ以上２Ｔ未満の間でランダムな値に設定することを特徴とするパケット転送制御方法。
【請求項１２】
前記請求項８，９、１０又は１１に記載のパケット転送制御方法において、
前記転送判定工程は、パケットの受信数が予め定めた閾値Ｃ以上の場合は転送を禁止し、閾値Ｃ未満であれば転送する判定を行うことを特徴とするパケット転送制御方法。
【請求項１３】
アドホック無線通信ネットワークの構成要素としてブロードキャストパケットをマルチホップで中継転送する無線端末にあって、
転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として計時を開始し、所定の最短終了時間と最長終了時間の範囲内の一様乱数を用いて決めた終了時間を設定する計時区間設定処理、
前記計時区間の間における前記受信パケットと同一のブロードキャストパケットの受信数を計数するパケット数計数処理、
前記パケット数計数処理の計数結果に基づいて、計数結果であるパケットの受信数が予め定めた閾値Ｃ以上の場合は転送を禁止し、閾値Ｃ未満であれば転送する判定を行う転送判定処理、
をコンピュータに実行させるよう構成したことを特徴とするパケット転送制御用プログラム。
【請求項１４】
前記請求項１３に記載のパケット転送制御用プログラムにおいて、
前記計時区間設定処理は、終了時間Ｔｆを、最短終了時間Ｔｓと最長終了時間Ｔｍの間を一様分布する乱数Ｔｒ（Ｔｓ≦Ｔｒ＜Ｔｍ）の選択値を用いて設定することを特徴とするパケット転送制御用プログラム。
【請求項１５】
前記請求項１４に記載のパケット転送制御用プログラムにおいて、
前記計時パラメータ設定処理は、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として計時を開始し、時間Ｔを方式最大長パケット送信時間ΔｔのＭ倍として、前記最短終了時間をＴｓ（０＜Ｔｓ≦Ｔ）、前記終了時間ＴｆをＴｓ以上（Ｔ＋Ｔｓ）未満の間でランダムな値に設定することを特徴とするパケット転送制御用プログラム。
【請求項１６】
前記請求項１５に記載のパケット転送制御用プログラムにおいて、
前記計時パラメータ設定処理は、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として計時を開始し、前記最短終了時間をＴ、終了時間Ｔｆを前記最短終了時間Ｔ以上２Ｔ未満の間でランダムな値に設定することを特徴とするパケット転送制御用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドホック無線通信ネットワークに係り、特にアドホック無線通信ネットワークにあって、ブロードキャストパケットを用いたフラッディングにおける無線端末、パケット転送制御方法及びそのプログラムに関する。
【背景技術】
【０００２】
移動性のある無線端末同士がパケットをマルチホップで中継転送するアドホック無線通信ネットワークにおいては、特定の無線端末宛のパケットの他に相手端末を特定しないで全ての無線端末に一斉に情報を送るブロードキャストパケットを使用する場合がある。このようなブロードキャスト通信は、放送型の通信の他に、通信したい相手端末の探索や通信経路構築などにも使用される。以下、特に断らない限り、パケットはブロードキャストパケットを意味するものとする。
【０００３】
ブロードキャスト通信では、各無線端末が新たに受信したパケットを全て中継転送すると、１つの送信端末が１つのパケットを送信すると残りの全端末がパケットを中継転送することになる。そのため無線端末からの電波の到達範囲内にある端末数が多くなると、膨大なパケットが転送され、各端末はその受信と転送に追われ、他の通信に使用できる時間が狭められることになる。これは、一般にはブロードキャストにおける「嵐の問題」と呼ばれている。
【０００４】
非特許文献１及び非特許文献２によれば、無線端末からの電波の到達範囲内に存在する端末のうち３個程度の端末がパケットを中継転送すれば、このような「嵐の問題」を回避しながら全端末にパケットが到達する可能性が高いとされている。このため、アドホックネットワークで使用されるプロトコルには中継転送するパケットを削減する転送方式が組み込まれているのが一般的である。
【０００５】
この中継パケットを削減する転送方式は、非特許文献１によれば、以下のように大きく３つに分類される。
【０００６】
第１はカウンタベース方式である。この方式における各端末の中継動作は、次のようにおこなわれる。端末は新たなパケットを受信すると、待ち時間（計時時間ともいう）を０からＴの間で一様ランダムな値に選択する。図１３（Ａ）は、この一様分布する待ち時間の分布（確率密度）を示している。そのランダムに選択された待ち時間の間に、同一内容のブロードキャストパケットを何個受信するかを監視し、その待ち時間が経過した時点で、その数を判定する。同じブロードキャストパケットの受信数が所定の閾値Ｃ未満ならばパケットを中継転送し、閾値Ｃ以上の場合は既に十分に転送パケットがあると判断して中継転送しないことによって、パケット数を削減している。
【０００７】
この方式は、無線端末からの電波の到達範囲内に存在する端末数が多い場合には、無線端末からの電波の到達範囲内に存在する端末数は閾値Ｃより多く、一方無線端末からの電波の到達範囲内で中継される中継パケット数の総数はほぼ確実に閾値Ｃ以下となるため、中継パケット削減効果は大きいが、次に説明する確率ベース方式に比べ遅延時間が増加するという不都合な点を持っている。
【０００８】
第２の方式は確率ベース方式である。各無線端末の中継転送動作は、次のように行なわれる。新たにブロードキャストパケットを受信した端末は、確率ｐで中継転送し、確率（１−ｐ）で中継転送しないことによって、ブロードキャストパケットの転送数を削減する。ただし、この確率ベース方式は、遅延時間は少ないが、中継する確率ｐを電波の到達範囲に存在する端末数にあわせて最適化しないと、電波の到達範囲内での中継パケット数が多すぎたり少なすぎたりするという問題点を持っている。
【０００９】
その他、第３の方式として、距離情報や位置情報等を使用する方式がある。距離情報や位置情報等を利用するため、第１や２の方式に無い独自の特徴を備えているが、そのための特別な手段等が必要になり第１や第２の方式とは異なる領域を形成している。
【００１０】
更に、上述したパケット転送に関しては、当該パケット転送の待ち時間を、受信電波強度測定結果の強弱に応じて長くしたり短くすることによって、パケット転送数を減らして混雑を防止する方法が特許文献１に開示されている。又、特許文献２には、パケットのホップ数に応じて転送するか否かを決めたり、あるいは受信信号強度と重複ブロードキャストパケット数に基づいて転送確率を計算することによって、転送パケット数の爆発的な増大を抑制する方法が開示されている。
【非特許文献１】筆者：Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, Jang-Ping Sheu.    刊行物の題名：The broadcast storm problem in a mobile ad hoc network.    発行年月日： August 1999 Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking MobiCom '99
【非特許文献２】筆者：Kleinrock, L. and J. Silvester.    刊行物の題名： Optimum Transmission Radii for Packet Radio Networks or why Six is a Magic Number.    発行年月日： Conference Record, National Telecommunications Conference, Birmingham, Alabama, pp. 4.3.2-4.3.5, December 1978.
【特許文献１】特開２００５−３４１３４１号公報
【特許文献２】特開２００７−１８４９３７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上述したように、ブロードキャストにおけるパケット数の劇的増大に対処する手法については、従来より種々の技術開発が成されている。
ここで、以下においては、本発明に密接に関連する上述した第１のカウンタベース方式の特性および改善すべき問題点等について詳述する。
【００１２】
この伝統的なカウンターベース方式では、パケットの実効的な伝播速度のばらつきが大きくなる。何故なら、上述のように待ち時間（計時時間）が、図１３（Ａ）に示すように０からＴの間のランダム値をとるので、パケットの１ホップの実効的な伝播速度は、電波の到達距離を一定値Ｒとしてそれを待ち時間で除した値、即ちＲ／Ｔから無限大（Ｒ／０）まで広がるからである。そして、このパケット伝播速度のばらつき（速度偏差）のため、パケットの発信元（以下「ソースノード」という）からの一定時間後の到達距離は、伝播の向きによって一様でなくなる。
【００１３】
このパケットの伝播速度が速度の幅を持つことを、乱歩（ランダム・ウォーク）のモデルを用いて説明する。
パケットは、時間Ｔ／２毎に直線状にＲ／２進み、同時に乱歩成分として等確率で＋Ｒ／４又は−Ｒ／４進むとする。衝突回避の機構がないとすると、このモデルでは、パケット位置の確率密度は図１３（Ｂ）に示すようにその分散が経過時間ｔの１／２乗に比例して広がる正規分布が、速さＲ／Ｔで進行していく密度分布になる。
【００１４】
更に、カウンタベースの方式では、速い伝播速度で進むパケットが遅れたパケットの伝播をさらに遅れさせる傾向があり、伝播速度の分散がより拡大する傾向をもつ。
このことを図１３（Ｃ）を用いて説明する。この図１３（Ｃ）には、符号１００はソースノードを示す。そして、このソースノード１００からの距離が短い順に端末１０１、端末１０２、および端末１０３が配置されている。この図１３（Ｃ）において、端末１０１と端末１０２との間の距離及び端末１０１と端末１０３との間の距離は、電波の到達距離Ｒより小さく、端末１０２と端末１０３間の距離は電波の到達距離Ｒより大きい場合を想定する。
【００１５】
このような端末配置で、速い伝播速度で進んだパケットが端末１０２で中継されたとすると、端末１０１は、ソースノード１００に近い範囲からの中継パケットの他に端末１０２から同じパケットを受信するため、受信パケット数が閾値Ｃを超えてパケットを中継転送しない確率が高くなる。このため、端末１０３に端末１０１からの中継パケットが届く確率は低下する。そのため、パケットが端末１０３に到達する時点は、確率的によりいっそう遅れてしまうというように、伝播速度の分散がより拡大する。
【００１６】
上述したような特性をもつ伝統的なカウンタベースの中継パケット転送方式では、ソースノードからある特定の端末までパケットが届くのに要する時間をみると、その最小値と最大値との変動の幅が広くなっている。換言すると、パケットが同心円状にスムースに伝播していかない。そのため、ブロードキャスト通信において連続的にパケットを送信する場合、時間的前後にある２つのパケットの送信時間間隔（以下、これを「追い越しガードタイミング」と呼ぶ）が小さいと、時間的に後から送ったパケットが時間的に前に送ったパケットに追いつき、隠れ端末と同等のパケットの衝突が頻発するという問題が発生し、正常なパケットの到達端末数が減少する。
このため、２つのパケットの送信時間間隔を大きく取る必要が生じ、単位時間当たりに転送できるデータ量、即ち転送レートは低下するという問題点を抱えていた。
【００１７】
（発明の目的）
本発明は、上記問題点に鑑み、アドホック無線通信ネットワークにおけるブロードキャストパケット通信においてパケットの爆発的な増大を抑制する中で、パケットの実効的な伝播速度のばらつきを小さくし、高いパケット転送レートを実現した無線端末、パケット転送制御方法及びそのプログラムを提供することを、その目的とする。
【課題を解決するための手段】
【００１８】
上記課題を解決するため、本発明に係る無線端末は、ブロードキャストパケットを中継転送する無線端末であって、前記ブロードキャストパケット中の受信パケットの受信時を基準として計時を開始し、所定の最短終了時間と最長終了時間の間の値をとる確率変数により定まる終了時間の間の計時を行なう計時手段と、前記計時手段によって計時されている間の前記受信パケットと同一のブロードキャストパケットの受信数を計数するパケット数計数手段と、前記パケット数計数手段の計数結果に基づいてパケットの転送を行なうか否かを判定する転送判定手段と、を備えたことを特徴とする。
【００１９】
また、上記課題を解決するため、本発明に係るパケット転送制御方法は、複数の無線端末同士がパケットをマルチホップで中継転送するアドホック無線通信ネットワークにおけるブロードキャストパケットのパケット転送制御方法であって、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として計時を開始し、所定の最短終了時間と最長終了時間の範囲内の一様乱数を用いて決めた終了時間を設定する計時区間設定工程と、前記計時区間の間における前記最初の受信パケットと同一のブロードキャストパケットの受信数を計数するパケット数計数工程と
前記パケット数計数工程の計数結果であるパケットの受信数に基づいてパケットの転送を行なうか否かを判定する転送判定工程と、を備えたことを特徴とする。
【００２０】
さらに、上記課題を解決するため、本発明に係るパケット転送制御用プログラムは、アドホック無線通信ネットワークの構成要素としてブロードキャストパケットをマルチホップで中継転送する無線端末にあって、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として計時を開始し、所定の最短終了時間と最長終了時間の範囲内の一様乱数を用いて決めた終了時間を設定する計時区間設定処理、前記計時区間の間における前記受信パケットと同一のブロードキャストパケットの受信数を計数するパケット数計数処理、前記パケット数計数処理の計数結果に基づいて、計数結果であるパケットの受信数が予め定めた閾値Ｃ以上の場合は転送を禁止し、閾値Ｃ未満であれば転送する判定を行う転送判定処理、をコンピュータに実行させるよう構成したことを特徴とする。
【発明の効果】
【００２１】
本発明は上述したように構成したので、これにより、アドホック無線通信ネットワークにおけるブロードキャストパケットの輻輳を抑制する中で、パケットの伝播時間の偏差を小さくし、これによって、実効的な伝送レートの向上を図ることができるという従来にない優れた無線端末、パケット転送制御方法及びそのプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２２】
次に、発明の一実施の形態について図面に基づいて説明する。
図１は、本発明にかかる無線端末１０の一本実施形態を示すブロック図である。
この図１において、無線端末１０は、アンテナ１１と、このアンテナ１１からの高周波受信電流からパケットを再生又はパケットを高周波送信電流に変換するパケット送受信部１２と、ブロードキャストされた受信パケットで初めて受信したパケットを判別するパケット判別手段１３と、重複する同一パケットの受信回数をカウントするカウンタ（パケット数計数手段）１４と、カウンタのカウント数である重複パケット数に基づいてパケット中継再送か否かを決める転送判定手段１５と、受信パケットを一時的に格納するとともに管理情報を格納するバッファ１６と、カウンタ１４のカウント動作終了時間を決める遅延ランダムタイマ（計時手段）１７と、これら各構成部分全体のパケット転送制御動作を制御する制御部１８とを備えて構成されている。
【００２３】
このように構成された無線端末１０が、本実施形態では広範囲にわたって複数配置されており、固定的な中継基地局や伝送手段が存在しない環境下で、互いにパケットをマルチホップで中継転送するアドホック無線通信ネットワークを形成している。
かかる状態下にあって、通信したい通信相手の探索と経路構築、或いは全ての無線端末に一斉に情報を送る放送型の通信などに際しては、ブロードキャストパケットが使用される。そして、このような通信形態においても、本無線端末１０は、ブロードキャストパケットの数がネットワーク内で爆発的に増大するのを抑えると共に、パケットの伝播速度の偏差を減少させて、パケットの衝突を避けるためのパケット間の伝送時間間隔を狭くすることによって、伝送レートの高いパケット転送制御方式を実現している。
【００２４】
以下、本無線端末１０の構成と動作について、更に詳細に説明する。
上述した本実施形態における無線端末１０の主要部であるパケット判別手段１３は、バッファ１６に記憶された受信パケットとの比較を行い、これまでの受信パケットと異なるパケットを初めて受信したことを判別すると、これを契機にカウンタ１４や計時手段１７の初期値のリセットなど動作準備のためこれらに信号を送る。そして、その後は重複した同一パケットを受信するたびにカウンタ１４に信号を送るよう構成されている。それは、受信パケットの中どれくらいが周囲の無線端末によって転送された同一パケットであるかを調べることで、パケット輻輳状態が推定できるからである。
【００２５】
又、カウンタ１４は、同一受信パケットの数をカウントするよう構成されており、パケット判別手段１３からの信号を、計時手段１７で指定される終了時間までカウントする。
【００２６】
更に、転送判定手段１５は、カウンタ１４のカウント数である同一受信パケット数に基づいて、この受信パケットを転送するか否かを判定するように構成される。具体的には、カウント数がある閾値Ｃ未満であればパケットを転送し、閾値Ｃ以上であればパケットの転送を禁止する。閾値Ｃの値は、一般的に３程度が良いとされているが、無線端末の密度などにより具体的に決められる。
【００２７】
前述した計時手段（遅延ランダムタイマ）１７は、本実施形態の中心部分であり、同一受信パケットのカウントを行なう計測時間を制御するよう構成されている。本発明では、一般的には、転送されるブロードキャストパケット中の最初の受信パケットの受信時を基準として計測を開始し、所定の最短終了時間と最長終了時間の範囲内で一様分布する確率変数で決まる終了時間までの計時を行なう。
具体的には、図２（Ａ）に示すように、最初のパケット受信時を基準にして時間の計測を開始し、最短終了時間をＴｓ（Ｔｓ＞０）、最長終了時間をＴｍとしてこの範囲内で一様分布する確率変数（乱数）によって決定される計測の終了時間Ｔｆを設定してその間の計時を行なう。パケット判別手段１２からの初期値設置信号によってランダム値が選択され、それから計測終了時間Ｔｆが算定される。
【００２８】
本実施形態の無線端末１０では、図２（Ｂ）に示すような時間分布を計測時間として用いている。即ち、計時の終了時間Ｔｆを、最短終了時間ＴｓをＴ、最長終了時間Ｔｍを２Ｔとして、その範囲で一様分布する乱数で決めている。この時間Ｔは、具体的には方式最大長パケット送信時間Δｔを単位タイムスロットとしてそのＭ倍の時間Ｔ＝Δｔ×Ｍと表される。即ち、時間Ｔは同時送信による衝突を防ぐために十分なタイムスロットの数Ｍを確保したときの送信遅延時間である。
【００２９】
この数Ｍは、無線端末密度などを考慮して決められるが、ここでは６４としている。この計測終了時間の分布は、関連する技術で使われている時間分布（図１３（Ａ）参照）と比較すると、計測終了時間がＴだけ遅延した分布であることが分かる。これによって、実行転送速度があまりに速い伝播を抑制し、伝播速度のばらつきを抑える役割を果たしている。
【００３０】
次に、本実施形態に係る無線端末１０の動作フローを説明する。
図３は、本無線端末１０におけるパケット転送制御動作のフローチャート図を示す。ここで、図３（Ａ）は、本パケット転送制御動作フローの中のパケット受信動作フロー図であり、図３（Ｂ）は、本パケット転送制御動作フローの中のタイムアウト処理動作フロー図である。
【００３１】
先ず、図３（Ａ）に基づいてパケット受信動作の動作フローを説明する。無線端末ではパケットを受信すると、無線端末に到達した最初のパケットか否かの判定を行う（ステップＳ５１、パケット判定工程）。この判別には、既に受信したパケットとの比較で行なってもよいし、ソースノードからの送信パケットに付される一連のシーケンス番号などを使ってもよい。そして、最初のパケットと判定されると、その後に受信される同一パケットの数をカウントするための準備動作に移る。
【００３２】
準備動作では、先ずカウンタの初期値設定を行なう（ステップＳ５２）。ここでは初期値として１を与えている。続いて、計時手段の計測終了時間の設定を行なう（ステップＳ５３、計時区間設定工程）。本実施形態では、最短終了時間ＴｓとしてＴ，計測の終了時間ＴｆとしてはＴから２Ｔの間の乱数値を取る。この乱数値は乱数発生を利用するなどして算定する。
【００３３】
次に、計時手段１７を起動し動作させる（ステップＳ５４）。本実施形態では、この計時手段１７は、起動によって動作を始め、計測終了時間Ｔｆで終了（タイムアウト）する。
【００３４】
カウンタは、この計時手段１７が動作している間に受信される同一パケット数をカウントする（ステップＳ５５、パケット数計数工程）。この同一パケットの受信数は、この無線端末の周囲の転送パケットの輻輳状態を反映している。
【００３５】
次に、計時手段１７が計測終了時間Ｔｆで終了（タイムアウト）すると、タイムアウト処理（図３（Ｂ）参照）に動作が移行する。
【００３６】
タイムアウト処理では、先ずパケットを転送するか否かの判定を行なう（ステップＳ６１、転送判定工程）。具体的には、カウント数である同一パケット受信数がある閾値Ｃ未満であれば転送し、閾値Ｃ以上であれば転送を禁止している。これによって、転送パケットの輻輳状態を反映しているこのカウント数が閾値を超える場合には受信したパケットの中継転送を行なわないことによって輻輳制御をしている。
【００３７】
ここで、転送を行なうと判定されると、受信パケットと同一の待機パケットを実際に転送し（ステップＳ６２）、転送禁止であれば転送を行なわず、待機パケットは破棄し、次の最初のパケット受信を判別するために動作に移行するための初期化動作をおこなう（ステップＳ６３）。
【００３８】
ここで、ブロードキャストパケットの転送制御方法は、上述した計時区間設定工程、パケット数計数工程、及び転送判定工程により構成されている。
【００３９】
即ち、複数の無線端末同士がパケットをマルチホップで中継転送するアドホック無線通信ネットワークにおけるブロードキャストパケットの転送制御方法は、転送されるブロードキャストパケット中の最初の受信パケットの受信時を基準として、終了時間Ｔｆを前記時間Ｔ以上２Ｔ未満の間でランダムな値に設定する計時区間設定工程と、その計時区間の間における最初の受信パケットと同一のブロードキャストパケットの受信数を計数するパケット数計数工程とそのパケット数計数工程の計数結果であるパケットの受信数に基づいてパケットの転送を行なうか否かを判定する転送判定工程とを備えている。
【００４０】
これによって、再送パケット数を削減して輻輳を避けつつ、再送パケットの実効伝播速度のバラツキを伝統的なカウンタベース方式に比べて抑制できるので、先送出パケットと後送出パケットの衝突を防ぐためのパケット時間間隔を狭めることが可能になり、全体として伝送レート向上が図れアドホック無線通信による効率的なブロードキャスト通信が可能になるという効果がある。
【００４１】
ここで、上述した計時区間設定工程、パケット数計数工程、及び転送判定工程の各工程については、その各工程の処理内容をプログラム化し、コンピュータに実行させるよう構成してもよい。
【００４２】
即ち、アドホック無線通信ネットワークの構成要素としてブロードキャストパケットをマルチホップで中継転送する無線端末にあって、本転送制御用プログラムは、転送される前記ブロードキャストパケット中の最初の受信パケットの受信時を基準として、終了時間Ｔｆを時間Ｔ以上２Ｔ未満の間でランダムな値に設定する計時区間設定処理、その計時区間の間における受信パケットと同一のブロードキャストパケットの受信数を計数するパケット数計数処理、その計数処理の計数結果であるパケット数に基づいて、予め定めた閾値Ｃ以上の場合はパケットの転送を禁止し、閾値Ｃ未満であればパケットを転送する判定を行う転送判定処理をコンピュータに実行させるよう構成されている。
【００４３】
以下、この転送制御用プログラムを図４乃至図５に基づいて更に詳細に説明する。
図４は転送制御用プログラムを実行する場合のフローチャート図であり、図４（Ａ）は、パケットの受信処理、図４（Ｂ）は、タイムアウト処理のフローチャートを示す。又、図５（Ａ）はタイマ値算出処理（計時区間設定処理）のフローチャートを示し、図５（Ｂ）は、比較のため伝統的なタイマベース方式におけるタイマ値算出処理（計時区間設定処理）のフローチャート図である。
【００４４】
この図４乃至図５は、上述した図３の無線端末の動作フローと基本的に同じであり、ここでは、更に転送制御用プログラムの構成に対応してより詳細化されている。以下、これを説明する。
【００４５】
図４（Ａ）に示されるパケット受信処理では、先ず自端末がソースノードか否かの判定を行っている（ステップＳ１０１）。自端末が送信元端末（ソースノード）の場合には、パケット送信のみを行ない転送は行なわない。このため、以下の処理が不要になるためである。
【００４６】
端末がソースノードでなければ、次にバッファを検索し（ステップＳ１０２）、登録されたパケットの有無を確認する（ステップＳ１０３）。登録がなければ、最初の受信パケットと判断し、バッファを取得し（ステップＳ１０４）、カウンタ値を1 に初期設定する（ステップＳ１０５）。
【００４７】
次に、遅延ランダムタイマの終了時間であるタイマ値の算出を行ない（ステップＳ１０６）、そのタイマ値を登録する（ステップＳ１０７）。タイマ値の算出については後ほど説明する。なお、このステップＳ１０６、Ｓ１０７が上述の計時区間設定処理に対応する処理である。
【００４８】
そして、バッファ内に格納されたパケット毎の処理状態を表す状態変数を「送信待ち状態」に設定し（ステップＳ１０８）、受信パケットをバッファに登録して（ステップＳ１０９）、一連の同一受信パケット数のカウントのための準備処理を終える。
【００４９】
一方、登録パケットの有無の確認を行なうステップＳ１０３において、登録があれば同一の受信パケットがあることになり、カウンタ値に1 を加算する処理を行なう（ステップＳ１１０）。これが上述のパケット数計数処理に対応する。
【００５０】
以上の処理動作を、計時手段（遅延ランダムタイマ）のタイマ値が終了（タイムアウト）になるまで繰り返し続ける。そして、タイマ値がタイムアウトになると、次の図４Ｂに示すタイムアウト処理に移行する。
【００５１】
図４（Ｂ）に示すタイムアウト処理においては、バッファ検索を行い（ステップＳ２０１）、バッファにパケットが登録されているか否かの確認を行って（ステップＳ２０２）、もし登録がなければ転送するパケットは無いので処理は終了する。
【００５２】
一方、登録されていれば、さらに、無線端末の状態を表す状態変数を調べ「送信待ち状態」か否かを確認する（ステップＳ２０３）。もし「送信待ち状態」でなければ、パケットの転送処理は行なわないので、バッファを開放して動作を終了する（ステップＳ２０９）。ここで、状態変数が「送信待ち状態」であれば、次のステップに進みカウンタ値を取得する（ステップＳ２０４）。
【００５３】
このカウンタ値を閾値Ｃと比較し、もしカウンタ値が閾値Ｃ未満であれば、パケットを転送し（ステップＳ２０６）、もし、カウンタ値が閾値Ｃ以上であれば、パケットの転送は行なわない。これらステップＳ２０４、Ｓ２０６が上述の転送判定処理に対応する。
【００５４】
ついで、ガードタイマを登録し（ステップＳ２０７）、状態変数を「送信待ち状態」から「開放待ち状態」に設定して（ステップＳ２０８）、次に受信される最初のパケット受信に備えて、終了する。
ここで、ガードタイマのタイムアウト時の処理を説明する。ガードタイマのタイムアウト時も、図４（Ｂ）に示すタイムアウト処理で処理される。この場合、状態は開放待ちなので、ステップＳ２０３では「ノー」に分岐し、ステップＳ２０９でバッファは開放される。なお、ガードタイマは、送信待ち状態でタイムアウトしてパケットを転送する判定を行った後に到着する同一パケットを、はじめて受信したパケットと誤認しないようにするために設けられている。その値は、例えばＴの１００倍とすれば問題の発生はほぼゼロになる。
【００５５】
ここで、前述した図４（Ａ）に開示したステップＳ１０６におけるタイマ値算出処理について説明する。
図５（Ａ）はこのタイマ値算出処理のフローチャート図である。タイマ値は、上述の無線端末の構成等で説明したように（図２参照）、終了時間（タイムアウト）はＴから２Ｔの間の一様乱数値を取る。
【００５６】
本タイマ値算出処理フローチャートにおいては、先ず、０より大きく１より小さい乱数値を取得する（ステップＳ３０１）。次に、得られた値にＴを掛けた値を計算する（ステップＳ３０２）。そしてこの得られた値にＴを加えた値を計測終了時間のタイマ値とする。本処理が、上述の計時区間設定処理の内容に対応している。
【００５７】
ちなみに、従来のタイマベースのパケット転送制御方式におけるタイマ値算出処理フローを参考のため図５（Ｂ）に示しておいた。ステップＳ４０１，Ｓ４０２は、前述した本実施形態におけるステップＳ３０１，Ｓ３０２と同一であるが、ステップＳ３０３の処理が無い点が異なっている。
【００５８】
上述した処理によって、本転送制御用プログラムは、再送パケット数を削減して輻輳を避けつつ、再送パケットの実効伝播速度のバラツキを伝統的なカウンタベース方式に比べて抑制できるので、先送出パケットと後送出パケットの衝突を防ぐためのパケット時間間隔を狭めることが可能になり、全体として伝送レート向上が図れアドホック無線通信による効率的なブロードキャスト通信を可能にする。
【００５９】
上述した構成と動作による本実施形態の効果は、ソースノードからある特定の端末までのパケットの到達時間をみると最小値から最大値までの偏差が小さくなることである。即ち、パケットが同心円状にスムースに広がっていく。
【００６０】
その理由は、パケットの１ホップの実効伝播速度が、従来の方式ではほぼＲ／Ｔから無限大までの広がりをもっていたのが、Ｒ／（２×Ｔ）からＲ／Ｔの範囲に狭まり、進行速度の偏りが小さくなるからである。更に、伝統的なカウンタベースの中継パケット削減方式では、速い伝播速度で進んだパケットが遅れたパケットの伝播をさらに遅れさせるという、速度偏差増大の傾向があったが、本実施形態のような待ち時間（時間区間）の確率密度に変更することによりその傾向が軽減されるからである。
【００６１】
以下、このことを図６（Ａ）を用いて詳細に説明する。この図６（Ａ）示す複数の同心円は、それぞれソースノード２００を中心として半径がＲ／２の倍数の円である。符号２１１，２２１，２３１，２４１は、それぞれ端末を示す。この内、端末２１１はソースノード２００からの距離がＲ／２以上で且つＲ以内に配置されており、端末２１２は端末２１１からの距離がＲ以下でソースノード２００からの距離がＲより大きく且つ３×Ｒ／２以内に配置されている。又、端末２４１は端末２３１から距離がＲ以内であり、ソースノード２００から端末２４１までの距離はソースノード２００から端末２３１までの距離より大きいとする。
【００６２】
ソースノード２００が時刻ｔ＝０にパケットを送信したとすると、端末２２１がパケットを受信する時刻ｔは、ソースノード２００からのパケットは端末２２１に直接届かないのでＴ以上になり、端末２２１がパケットを中継して送信する時刻ｔは２Ｔ以上になる。端末２２１がパケットを中継して送信する時刻ｔの確率密度は電波到達範囲内の端末密度により異なるが、端末密度が少ない場合は図６（Ｂ）に示すような値になる。端末２１１がパケットを中継するかどうか判断する時点は２×Ｔ未満なので、外側にある端末２２１からのパケットの受信によりパケット中継確率を低下させられることはない。
【００６３】
ソースノード２００からの距離が大きい端末では、送信端末からある特定の端末まで届くのに要する時間をみると最小値から最大値まで変動の幅は少ないので、従来方式に比べて外側にある端末からのパケットの受信によりパケット中継確率を低下させる可能性は少ない。即ち、図６（Ａ）の端末２３１が外側にある端末２４１からのパケットの受信によりパケット中継確率を低下させられる可能性は伝統的なカウンタベース方式に比べて少なくなる。
以上のように本実施形態では、パケットがソースノードから広がる各中継転送段階において、伝統的なカウンタベース方式に比べパケットが同心円状に滑らかに広がるという望ましい特性を有している。
【００６４】
（実施例）
次に、本無線端末１０の複数により構成されるアドホック無線通信ネットワークにおける特性のシミュレーション結果について説明する。
【００６５】
シミュレーション条件は次のとおりである。アドホック無線通信ネットワークを構成する無線端末は、ｘ軸、ｙ軸ともに整数値をとる格子点上に一様ランダムに確率的に配置されているとしている。以下、距離の単位は格子点間隔１とする。
又、ソースノード（情報送信端末）は１つとし、原点ｘ＝０，ｙ＝０に配置される。更に、無線端末からの電波の到達距離は８とする。他の端末はソースノードからの距離が１２７以下の範囲に、無線端末からの電波の到達距離を半径とする円内に平均１０個の端末が存在するように、一様ランダムに確率的に配置される。
【００６６】
ソースノードからは１パケットを送信する。転送を行なうか否かを判定する転送判定手段１５の閾値Ｃは３とする。時間に関しては、時間Ｔは５１２単位時間とし１パケット送信所要時間Δｔは８単位時間とする。したがって倍数Ｍは６４であり、計測終了時間はランダムに５１２，５１３、…、１０２３単位時間の値を取る。全て本実施形態に係る無線端末である場合についてシミュレーションを実施した。また、比較のため、端末が全て関連する伝統的なカウンタベース方式に従って転送する場合についてもシミュレーションを実施した。
【００６７】
図７は、全端末が本実施形態に係る無線端末である場合の、パケットの伝播を示す図であり、図８は、全端末が全て伝統的なカウンタベース方式の場合のパケットの伝播を示す図である。これらの図は、ソースノードからの距離Ｄが、それぞれ２５，５０，７５，および１００の端末に初めてパケットが届いた時点をトリガーとして、その時点以降に中継転送されたパケットが届いた端末を白点でプロットしたものである。
使用した中継送信パケット数はそれぞれソースノードからの距離Ｄが２５では１２パケット、距離Ｄが５０では２５パケット、距離Ｄが７５では３７パケット、および距離Ｄが１００では５０パケットである。灰色の点は上記条件のパケットを受信した端末以外の端末の配置を示している。なお、ここでソースノードからの距離がｄである端末とは、ソースノードからの距離が整数ｄ以上で、かつ（ｄ＋１）未満の端末である。
【００６８】
図７と図８で白点すなわちパケットが届いた端末を比べると、いずれの時点においても本実施形態の方が円環に近い形になっていて、その幅も狭く、パケットが同心円状にスムースに広がっていることがわかる。即ち、本実施形態の方が、実効的なパケットの伝播速度のばらつきが減少していることを示している。
【００６９】
次に、このシミュレーションにより得られた内容を更に詳しく分析した結果を、図９に示す。
この図９は、シミュレーションを実施したアドホック無線通信ネットワークにおける無線端末数の対距離分布、すなわち無線端末数を距離毎に集計してプロットしたグラフである。
【００７０】
また、図１０は、パケット転送にかかる実効的な伝播時間（遅延時間）の対距離分布、即ち、ソースノードがパケットの送信を完了した時点から端末が最初のパケットを正常に受信した時点までの時間を、ソースノードから端末までの距離毎に集計し、その平均値と標準偏差を計算してプロットしたグラフである。ここで、データはソースノードからの距離が１１２未満の端末のものを使用している。
【００７１】
この図１０からは、平均遅延は本実施形態も従来方式も共にソースノードから端末までの距離にほぼ比例して増加し、本実施形態の方が大きいことがわかる。一方、標準偏差は、本実施形態では距離の増加に伴って増加しているが、全体として従来方式に比べ小さくなっており、本実施形態でパケットが従来方式に比べてスムーズに同心円状の形状を保ちながら広がっていること（図７参照）に対応している。
【００７２】
又、図１１は、端末への最初のパケットの到着時間と最後のパケットの到着時間の差を正常受信か異常受信かを問わず集計し、到着時間差毎に端末数を集計したものである。
【００７３】
この図１１からは、本実施形態の方が、従来方式に比べて平均の到着時間差が小さく、ソースノードが連続して複数パケットを送る場合、追い越しガードタイミング、すなわち後から送ったパケットが前に送ったパケットに追いついて衝突しないようにするためにとるパケットの送信時間間隔を小さくできることがわかる。
【００７４】
即ち、本シミュレーションの結果からも、本実施形態では、従来方式に比べ実効的な伝送レートが高い効率的なパケット通信が可能なことが示された。
【００７５】
（変形例）
ここで、上述した実施形態において、計時手段（遅延ランダムタイマ）１７の計時終了時間が異なる場合について、その例を説明する。これは、パケット転送の伝播時間の短縮を意図したものである。以下、これを説明する。
【００７６】
今、本実施形態に係る無線端末の電波到達範囲内に存在する無線端末数が、閾値Ｃに比べてＮ倍ある場合を考える。
この場合、実際にパケットを中継転送する端末は、計時手段１７のタイマ値がＴからＴ＋Ｔ／Ｎの範囲の端末である可能性が高い。なぜなら、計時手段１７のタイマ値がＴ＋Ｔ／Ｎを超えると同一受信パケット数はＣを超える確率が高くなり無線端末の大部分では転送を禁止されるからである。
【００７７】
かかる場合、伝播速度の偏差は、〔Ｎ／（Ｎ＋１）Ｔ〕から〔１／Ｔ〕の範囲にあり、例えばＮ＝３の場合には偏差は（３／４）〜１からの範囲で非常に小さくなる。従って、その分、計測開始時間Ｔｓを小さく出来る。即ち、無線端末の電波到達範囲内に存在する端末数が閾値Ｃに比べて大きいという前提条件が成り立つ場合には、図１２に示すように、計時手段（遅延ランダムタイマ）１７の計測終了時間Ｔｆの最短終了時間Ｔｓを０以上Ｔ未満の値とし、最長終了時間Ｔｍのタイマ値をＴｓ＋Ｔとすることにより、パケットが同心円状にスムースに広がる性質を保ちながら遅延時間を短縮することが可能になる。
【００７８】
すなわち、上述した無線端末の計時手段１７を、転送されるブロードキャストパケット中の最初の受信パケットを契機として、時間Ｔを方式最大長パケット送信時間ΔｔのＭ倍として、計時の最短終了時間をＴｓ（０＜Ｔｓ≦Ｔ）とし、終了時間ＴｆをＴｓ以上、（Ｔ＋Ｔｓ）未満の間でランダムな値に設定する。
【００７９】
又、前述したパケット転送制御方法における計時パラメータ設定工程において、転送されるブロードキャストパケット中の最初の受信パケットを契機として、時間Ｔを方式最大長パケット送信時間ΔｔのＭ倍として、最短終了時間をＴｓ（０＜Ｔｓ≦Ｔ）として、終了時間ＴｆをＴｓ以上、（Ｔ＋Ｔｓ）未満の間でランダムな値に設定する。
【００８０】
更に、上述したパケットの転送制御用プログラムにおける計時パラメータ設定処理において、転送されるブロードキャストパケット中の最初の受信パケットを契機として、時間Ｔを方式最大長パケット送信時間ΔｔのＭ倍として、最短終了時間をＴｓ（０＜Ｔｓ≦Ｔ）とし、終了時間ＴｆをＴｓ以上、（Ｔ＋Ｔｓ）未満の間でランダムな値に設定する。
【００８１】
これにより、既に述べた本発明の効果である、アドホック無線通信ネットワークにおけるブロードキャストパケットの輻輳を抑制すると共に、パケットの伝播時間の偏差が小さくなり、そのため時間的前後関係にあるブロードキャストパケット同士の衝突を避けるために設けられている伝送間隔を狭めることが可能になり、実効的な伝送レートが向上することに加えて、端末密度が大きい場合には、伝播遅延の偏差を増大させないで、すなわち本実施形態の効果を損なわないで、伝播遅延の短縮を図ることが可能になる。
なお、上述の説明では一の送信端末がブロードキャストパケットの送信を行なっている場合について説明したが、複数の送信端末から同時にブロードキャストパケットの送信がなされる場合にも、各無線端末は多重化処理によってこれらパケットを同時並行して処理することが可能である。
【産業上の利用可能性】
【００８２】
本発明は、パケットを使用したアドホック無線通信ネットワークにおける通信、特にブロードキャスト（放送）型の通信で、音声・音楽・映像など高い送信レートで送る場合にも有効である。
【図面の簡単な説明】
【００８３】
【図１】本発明の一実施形態に係る無線端末を示すブロック構成図である。
【図２】図１に示す無線端末の計時手段における待ち時間の確率分布を示した図で、図２（Ａ）は最初のパケット受信時を基準にして計測を開始し計測終了時間を最短終了時間と最長終了時間の間の確率変数で決めて計時を行なう場合を示す説明図、図２（Ｂ）は図２（Ａ）にあって計測終了時間として最短終了時間をＴ，最長終了時間を２Ｔの一様乱数を用いる場合を示す説明図である。
【図３】図１に示す無線端末のパケット転送制御動作を示すフローチャート図で、図３（Ａ）はパケット受信動作を、図３（Ｂ）はタイムアウト処理動作を、夫々示すフローチャートである。
【図４】図１に示す無線端末におけるパケットの転送制御用プログラムを示す処理フローチャートで、図４（Ａ）はパケット受信処理を、図４（Ｂ）はタイムアウト処理をそれぞれ示す処理フローチャートである。
【図５】図１に示す無線端末におけるパケットの転送制御用プログラムを示す処理フローチャートで、図５（Ａ）はタイマ値算出処理を示すフローチャート、図５（Ｂ）は同タイマ値算出処理の従来例を示すフローチャートである。
【図６】図１に示す無線端末によるパケット転送制御によってパケット進行状況を説明するための図で、図６（Ａ）はパケット進行の分散拡大傾向が減少することを説明するための説明図、図６（Ｂ）はソースノードからの距離がＲより大で２×Ｒ以下の端末がパケットを中継する時点の時間の確率密度を示す説明図である。
【図７】本実施形態におけるパケットの進行をソースノードからの距離Ｄを変えてシミュレーションした結果を示す説明図である。
【図８】図７と比較するための関連するカウンタベースのパケット転送制御方式でのパケットの進行を示したシミュレーションした結果を示す説明図である。
【図９】図７に示す本実施形態のシミュレーション結果からソースノードからの距離ごとに端末数をプロットした図表である。
【図１０】図１に示す本実施形態のシミュレーション結果からソースノードからの距離ごとにパケット到着時刻の遅延およびその分散をプロットした図表である。
【図１１】図１に示す本実施形態のシミュレーション結果のからパケットの到着時間差ごとに当該到着時間差でパケットを受信した端末数をプロットした図表である。
【図１２】図１に示す本実施形態にあって無線端末の計時手段における計時終了時間を変化させた場合の例を示す説明図である。
【図１３】関連するカウンタベースのパケット転送制御方式にかかる内容の一部を示す図で、図１３（Ａ）はパケット転送制御方式における待ち時間の確率分布を示す説明図、図１３（Ｂ）はパケット伝播の乱歩モデルによる結果を示す説明図、図１３（Ｃ）はパケット伝播の分散拡大傾向を示す説明図である。
【符号の説明】
【００８４】
１０  無線端末
１２  パケット送受信部
１３  パケット判別手段
１４  バッファ
１５  カウンタ（パケット数計数手段）
１６  転送判定手段
１７  遅延ランダムタイマ（計時手段）
１８  制御部
Ｔ    一様乱数の取りうる範囲（上限値）
Ｔｆ  タイマの計時終了時間（最初のパケット受信を基準）
Ｔｓ  タイマの最短終了時間（最初のパケット受信を基準）
Ｔｍ  タイマの最長終了時間（最初のパケット受信を基準）
【図１】
2009212978.tif 000003
【図２】
2009212978.tif 000004
【図３】
2009212978.tif 000005
【図４】
2009212978.tif 000006
【図５】
2009212978.tif 000007
【図６】
2009212978.tif 000008
【図７】
2009212978.tif 000009
【図８】
2009212978.tif 000010
【図９】
2009212978.tif 000011
【図１０】
2009212978.tif 000012
【図１１】
2009212978.tif 000013
【図１２】
2009212978.tif 000014
【図１３】
2009212978.tif 000015