(57)【要約】  【課題】  余剰電力の多い端末の電力が消費されないようにルーティングしてネットワーク寿命を縮めてしまうことを解決する。  【解決手段】  各端末は送受信機能１０と、データを識別して必要な処理を行うデータ処理機能１１を有する。運用予定期間保持機能１４は運用予定期間を保持し、経過時間算出機能１５は自端末の運用開始からの経過時間を算出し、経過時間保持機能１６は経過時間算出機能１５によって算出された経過時間を保持する。残運用期間算出機能１７で、残運用期間を算出し、この残運用期間を残運用期間保持機能１８が保持する。各端末は、自端末に残されている残留電力を検出する残留電力検出機能１９を有し、この残留電力は残留電力保持機能２０で保持する。前述の残運用期間と残留電力等から、余剰電力算出機能２３で余剰電力を算出し、その電力を保持機能２４で保持する。  【選択図】  図３
2005244381.tif 000002
【特許請求の範囲】
【請求項１】
データ送受信機能とデータを中継する機能を有する端末で構成されるネットワークにおけるルーティング方法であり、
各端末が予め設定された当該端末の運用期間を保持する機能と、
当該端末がある時点での残運用期間に必要な電力を算出する機能と、
その時点での当該端末が有する残りの電力（以下残留電力）と上記残運用期間に必要な電力とから当該端末の残運用期間における余剰電力を算出する機能を有し、
データ送信時には、当該データの受信端末との間の経路上の端末の余剰電力をもとに評価値を決定し、その評価値により経路を選択することを特徴とするネットワークにおけるルーティング方法。
【請求項２】
請求項１に記載のネットワークにおけるルーティング方法であり、
上記評価値として、当該データの送信端末と受信端末との間のｊ番目の経路上の余剰電力の合計を当該経路の評価値Ｒjを定義し、Ｒjがもっとも大きい経路ｘを下記式により選択することを特徴とするネットワークにおけるルーティング方法。
Ｒx＝max{Ｒj|ｊ∈Ａ}
但し、Ａはデータ伝送に考えられる経路全ての集合である。
【請求項３】
請求項１に記載のネットワークにおけるルーティング方法であり、
上記評価値として、当該データの送信端末と受信端末との間のｊ番目の経路上の端末の中で余剰電力が最小である端末の余剰電力Ｅjを定義し、Ｅjが最大となる経路ｘを下記式により選択することを特徴とするネットワークにおけるルーティング方法。
Ｅx＝max{Ｅj|ｊ∈Ａ}
但し、Ａはデータ伝送に考えられる経路全ての集合である。
【請求項４】
請求項１に記載のネットワークにおけるルーティング方法であり、
上記評価値として、当該データの送信端末と受信端末との間のｊ番目の経路上の端末の中で余剰電力が最小である端末の余剰電力Ｅjとこの経路上の余剰電力の合計を当該経路の評価値Ｒjを定義し、Ｅjが最小となる経路ｙを除いた経路の中でＲjがもっとも大きい経路ｘを下記式により選択することを特徴とするネットワークにおけるルーティング方法。
Ｒx＝max{Ｒj|ｊ∈Ｂ}
但し、Ｂは経路ｙをデータ伝送に考えられる経路全ての集合Ａから除いた集合である。
【請求項５】
請求項１に記載のネットワークにおけるルーティング方法であり、
上記評価値として、当該データの送信端末と受信端末との間のｊ番目の経路上の端末の中で余剰電力が最小である端末の余剰電力Ｅjとこの経路上の余剰電力の合計を当該経路の評価値Ｒjを定義し、Ｅjが閾値γ以上の経路が存在する場合には当該条件を満たす経路の集合の中でＲjがもっとも大きい経路ｘを選択し、Ｅjが閾値γ以上の経路が存在しない場合にはＥjが最大となる経路ｘを選択することを特徴とするネットワークにおけるルーティング方法。
【請求項６】
データ送受信手段とデータを中継する手段を有する端末で構成されるネットワークにおけるルーティング装置であって、
各端末が予め設定された当該端末の運用期間を保持する手段と、
当該端末がある時点での残運用期間に必要な電力を算出する手段と、
その時点での当該端末が有する残りの電力（以下残留電力）と上記残運用期間に必要な電力とから当該端末の残運用期間における余剰電力を算出する手段を有し、
データ送信時には、当該データの受信端末との間の経路上の端末の余剰電力をもとに評価値を決定し、その評価値により経路を選択することを特徴とするネットワークにおけるルーティング装置。
【請求項７】
請求項６に記載のネットワークにおけるルーティング装置であって、
運用期間を保持する手段は、経路運用予定期間と自端末の運用開始からの経過時間とを計算して残運用期間を算出し保持することを特徴とするネットワークにおけるルーティング装置。
【請求項８】
請求項１から請求項５のいずれかに記載のネットワークにおけるルーティング方法における機能と経路選択を、コンピュータに実行させるためのプログラムとしたことを特徴とするネットワークにおけるルーティングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドホックネットワークのルーティングプロトコル技術のうちネットワーク寿命を延ばすための省電力化技術分野に係わり、特に端末の運用期間を考慮した長寿命化を図ったネットワークにおけるルーティング方法及びその装置並びにネットワークにおけるルーティングプログラムに関するものである。
【背景技術】
【０００２】
まず、ここで前提としているネットワークは末端の端末がデータを送信する機能、データを受信する機能を有し、データの宛て先に応じて受信したものを、そのまま送信するか、何かしらの加工を加えて送信するというデータの中継機能を有する。データ送信元の送信端末からデータ送信先の受信端末へのデータの伝送は端末の中継機能を利用したアドホックネットワーク上でのマルチホップ通信によって実現される。
【０００３】
このネットワークでは端末の電力の枯渇が即ネットワーク寿命に直結するという特徴からアドホックネットワークにおけるルーティングプロトコルには電力の枯渇を起こしてしまう端末がなるべく出ないような設計を目標としている。
【０００４】
従来のアドホックネットワークにおいて目標とされるルーティングプロトコルにおいては、全ての端末が同じ期間だけ動作し続けられるということがネットワークの長寿命化につながると考えられ、検討されてきた。
【０００５】
その考えの下、データの伝送ルートを決定する際に、端末ごとに残っている電力（以下残留電力）の多いものを選ぶ方法が考えられた。この方法によって特定の端末の電力が集中的に使われてネットワーク寿命を縮める問題を解決できるようになった。
【０００６】
ただし、この場合は全ての端末が残留電力を均等に残しているという状態が理想的な状態と判断する方式になっている。これは、運用期間の異なる他種類の端末が混在すると考えられる今後のアドホックネットワークにおいては、ネットワークの長寿命化にとって最適の状態であるとは限らない。
【０００７】
例えば運用期間の短い端末が運用期間の長い端末の中に存在する時にも残留電力が均等になるようにルーティングプロトコルは働くのだが、この場合、運用期間の短い端末は運用期間終了時に大量の余分な電力を保持していることが考えられる。また、この端末の存在によって運用期間の長い端末はデータの中継を担うことによって寿命を短くしてしまうことが考えられる。
【０００８】
このため、アドホックネットワークにおいては、省電力化プロトコルが提案されている。この提案の中では、データ伝送電力の和が最小になる経路（以下ルート）を選ぶ方法、端末の残留電力の逆数で表されるコスト関数の和が最小になるルートを選ぶ方法、ルート上で最大のコスト関数をルートの代表値とし、それが最小となるルートを選ぶ方法、ルート上の端末の中で残留電力が最小の値をそのルートの代表値として、その値がある閾値を超えているものが存在する場合は、そのルートのなかでデータ送信電力の和が最小となるルートを選び、存在しない場合は代表値のもっとも大きいルートを選ぶ方法、などが示されている。これらの方法は、個々の端末の送信電力や残留電力に関してはルート選択時の評価値として取り上げられているが、個々の端末の運用条件については考慮されていなかった（例えば、非特許文献１参照。）。
【０００９】
また、ローカルエリアネットワークの省電力制御システムでは、電力に余裕のない端末と余裕のある端末を判断し、信号を発信する端末を、選択する方法を定めている。ここでの余裕のあるなしは駆動電圧を検出し、その検出電圧が基準電圧よりも高いか低いかによって判断するものである。端末に余裕があるかないかはこのように残留電力によってのみ決定されている（例えば、特許文献１参照。）。
【非特許文献１】C.K Toh,”Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad hoc Networks ”,IEEE communication Magazine，June2001
【特許文献２】特開平０９−１３５２５４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上記の従来技術においては、運用期間の異なる多種類の端末が配備されて形成されたアドホックネットワークにおいて、各端末自身の目的を達成するために設定された運用期間に対して、各端末が有する必要以上の電力を正確に割り出し電力を効率的に利用する仕組みを導入することが要望されるようになってきている。
【００１１】
本発明は、上記の事情に鑑みてなされたもので、残留電力は周囲の端末に比べて少ないが、余剰電力は多い端末の電力が消費されないようにルーティングされてネットワーク寿命を縮めてしまうことを解決することができるネットワークにおけるルーティング方法及びその装置並びにネットワークにおけるルーティングプログラムを提供することを課題とする。
【課題を解決するための手段】
【００１２】
本発明は、上記の課題を達成するために、無線によるデータ送受信機能とデータ中継機能を有する端末で構成されるマルチホップ通信アドホックネットワークにおいて、各端末自身の目的達成のために設定された運用期間と端末を設置してからの経過時間によって残された端末の運用期間である残運用期間を算出する機能を有し、残運用期間と残留電力から残運用期間中の運用にとって余剰となる電力を算出する機能を有し、データ伝送のルートをそのルート上の端末の余剰電力を考慮して決定する機能を有するルーティング方法である。
【００１３】
あるいは、各端末は自身の余剰電力を定期的、あるいは他の端末からの要求に従って通知する機能を有する。
【００１４】
あるいは、このシステムにおいてさまざまな評価手段によってルートを決定する。
【００１５】
また、データ送受信手段とデータを中継する手段を有する端末で構成されるネットワークにおけるルーティング装置であって、
各端末が予め設定された当該端末の運用期間を保持する手段と、当該端末がある時点での残運用期間に必要な電力を算出する手段と、その時点での当該端末が有する残りの電力（以下残留電力）と上記残運用期間に必要な電力とから当該端末の残運用期間における余剰電力を算出する手段を有し、データ送信時には、当該データの受信端末との間の経路上の端末の余剰電力をもとに評価値を決定し、その評価値により経路を選択することを特徴とするネットワークにおけるルーティング装置である。
【００１６】
さらに、運用期間を保持する手段は、経路運用予定期間と自端末の運用開始からの経過時間とを計算して残運用期間を算出し保持することを特徴とする。
【００１７】
あるいは、ネットワークにおけるルーティング方法における機能と経路選択を、コンピュータに実行させるためのプログラムとしたことを特徴とするネットワークにおけるルーティングプログラムである。
【発明の効果】
【００１８】
以上述べたように、本発明によるデータ伝送時のルート決定に余剰電力を導入することにより、各端末が有する電力資源を有効に活用することが可能になって、余剰電力の算出に各端末ごとの残運用期間を利用することによる効果が得られる。
【発明を実施するための最良の形態】
【００１９】
以下本発明の実施の形態を図面に基づいて説明する。図１は本発明の実施の形態におけるネットワーク構成と伝送におけるルート例を示す説明図で、図１において、データを送信する端末として働く無線通信端末ｎ0と、データを受信する端末として働く無線通信端末ｎD、データを中継する端末として働く無線通信端末ｎ1L，ｎ2L，ｎ3L，ｎ1M，ｎ2M，ｎ3M，ｎ1N，ｎ2N，ｎ3N，ｎ1O，ｎ2O，ｎ3Oが存在し、データを中継するルートがL,M,N,Oと存在する。それぞれの端末は自端末の余剰電力Ｅijを保持している。
【００２０】
端末ｎ0は、端末ｎDに到達するためのルートの集合Ａを知る術を既知のルーティングプロトコルやフラッディングなどによって持っているシステムである。
【００２１】
図２は本発明におけるルート決定までの全体の流れを示すフロー図である。まずステップＳ１において「１．各端末で余剰電力を算出」し、ステップＳ２で「２．各ルートにおける評価値を算出」し、ステップＳ３で「３．送信端末においてルート決定」という順序を採る。
【００２２】
図３は、本発明の実施の形態における端末の構成を示すブロック図である。各端末はデータの送信と受信を受け持つ送受信機能１０と、受け取ったデータを識別して必要な処理を行うデータ処理機能１１を有する。
【００２３】
評価値処理機能１２はルート選択の指標となる評価値をルート毎に計算する処理を行う。ルート選択機能１３は、無線通信端末ｎDへ至るためのルートに関する評価値をルート毎に受け取り、その中から最適のルートを選択する機能を有する。
【００２４】
運用予定期間保持機能１４はあらかじめ決められた運用予定期間を保持しておく機能である。経過時間算出機能１５は自端末の運用開始からの経過時間を算出する機能を有し、経過時間保持機能１６は経過時間算出機能１５によって算出された経過時間を保持する機能を有する。
【００２５】
１７は残運用期間算出機能で、この残運用期間算出機能１７は、例えば（運用予定期間一経過時間）の計算によって残運用期間を算出するものである。算出された残運用期間は、残運用期間保持機能１８が保持する。
【００２６】
各端末は、自端末に残されている残留電力を検出する残留電力検出機能１９を有しており、例えば、これは駆動時の電圧の低下によって検出することができ、検出した残留電力は残留電力保持機能２０で保持する。
【００２７】
前述の残運用期間と残留電力、端末のデータ送信頻度を保持する送信頻度保持機能２１から送信頻度、自端末のデータ送信に必要な消費電力を保持する送信電力保持機能２２から送信電力を取り出し、今後の稼働に必要とされる電力以上の余った電力、余剰電力を例えば（残留電カ−送信電力×送信頻度×残運用期間）の計算によって算出する余剰電力算出機能２３を有する。
【００２８】
そして、余剰電力算出機能２３によって算出された自端末の余剰電力情報や周辺の端末から送られてきた他端末の余剰電力情報を保持する余剰電力保持機能２４を有する。
【００２９】
図４は本発明の実施の形態における各端末での余剰電力の算出と保持の流れを示したフロー図である。まず、ステップＳ１１で「１.運用予定期間保持機能１４に保持されている運用予定期間と経過時間保持機能１６に保持されている経過時間から残運用期間算出機能１７を利用して残運用期間を算出し、残運用期間保持機能１８に残運用期間を保持する」動作を行なう。
【００３０】
次に、ステップＳ１２で「２.残運用期間保持機能１８に保持されている残運用期間と残留電力検出機能１９によって検出された残留電力が保持されている残留電力保持機能２０から残留電力を取り出し、送信頻度保持機能２１に保持された送信頻度と送信電力保持機能２２に保持された送信電力を用いて余剰電力算出機能２３によって余剰電力を算出する」動作を行なう。
【００３１】
その後、ステップＳ１３で「３.上記の作業を定期的に繰り返し最新の余剰電力を保持」し続ける。
【００３２】
図５−１、図５−２、図５−３はルート毎の評価値パケットの流れと、そこに記述された評価値の変化を示した図である。ここでは評価値の算出方法とルートの決定方法によって４通りの形態が考えられる。
【００３３】
［第一の形態］
ルートｊに属する端末ｎijの余剰電力をＥijとし、その合計ΣＥij（i=0からD-1までの総和）をそのルートの評価値Ｒjとして定義する。（ｎ0は送信端末、ｎDは受信端末）
【００３４】
【数１】
2005244381.tif 000003
【００３５】
その値が最も大きいルートｘを選択する
Ｒx＝max{Ｒj|ｊ∈Ａ}
ここで、Ａはデータ伝送に考えられるルート全ての集合である。
【００３６】
次に、第一の形態を図５−１、図６−１、図７−１を使用して説明する。これらは評価値として、ルート上に存在する端末の余剰電力のＥij（i=0からD-1までの総和）を評価値１として用いたものである。
【００３７】
ここではルートＬの評価値を算出する方法を示したのが図５−１と図６−１である。まず、図６−１において、ステップＳ２１で「１.データ送信端末ｎ0からルートL上の次の中継端末ｎ1Lにルートの評価値１を記述するための評価値パケットをルートＬ」に送信する。ここで、評価値１はルート上に存在する端末の余剰電力の和である。
【００３８】
次に、ステップＳ２２で「２.ｎ1Lがｎ0から評価値パケットをデータ送受信機能で受信する。その後、ステップＳ２３で「３. ｎ1Lのデータ処理機能が評価値パケットを受け取り、識別して評価値処理機能」に渡す。
【００３９】
さらに、ステップＳ２４に進んで、「４.評価値処理機能は自端末の余剰電力Ｅ1Lを余剰電力保持機能から取り出し評価値１に足し合わせた値を評価値パケットの評価値１」に書き込む。
【００４０】
そして、ステップＳ２５では、「５.評価値処理機能は更新した評価値パケットをデータ処理機能に渡しデータ送受信機能からｎ2Lへ送信」する。ステップＳ２６で「６.ｎ2Lがｎ1Lからの評価値パケットをデータ送受信機能で」受信する。その後、ステップＳ２７で「７. ｎ2Lのデータ処理機能が評価値パケットを受け取り識別して評価値処理機能」に渡す。
【００４１】
次に、ステップＳ２８で「８.評価値処理機能は自端末の余剰電力Ｅ2Lを余剰電力保持機能から取り出し評価値パケットの中の評価値１に足し合わせた値を評価値パケットの評価値１」に書き込む。
【００４２】
その後、上記ステップＳ２５からステップＳ２８を繰り返し、ステップＳ２９で「９.ｎDがｎ3Lから評価値パケットをデータ送受信機能で受信」する。すなわち、受信端末まで評価パケットが到達する。
【００４３】
ステップＳ３０で「１０.評価値パケットを受け取ったｎDは、その評価値パケットをｎ0まで元通りのルートで送信」する。そして、ステップＳ３１で「１１.ｎ0はルートＬの評価値１」を受け取る。このような手順を踏むことにより同様にルートM,N,Oの評価値１を、送信端末は得ることができる。
【００４４】
図７−１はルートごとの評価値１を得た送信端末がルートを決定するフロー図である。この図７−１において、ステップＳ８１で「１.ｎ0がルートＬ，Ｍ，Ｎ，Ｏの評価値１」を受け取る。その後、ステップＳ８２で「２.評価値をルート選択機能」に渡し、ステップＳ８３で「３.余剰電力の和（評価値１）が最大となるルートを選択する。
【００４５】
［第二の形態］
ルートｊに属する端末ｎijの余剰電力をＥijとし、その最小値をそのルートの評価値Ｅjとする。
【００４６】
Ｅj＝min｛Ｅij|ｉ∈route ｊ｝
その値が最も大きいルートｘを選択する。
【００４７】
Ｅx＝max{Ｅj|ｊ∈Ａ}
ここでＡはデータ伝送に考えられるルート全ての集合である。
【００４８】
次に、第二の形態を、図５−２、図６−２、図７−２を使用して説明する。これらは評価値としてルート上に存在する端末の最小余剰電力
Ｅj＝min｛Ｅij|ｉ∈route ｊ｝を評価値１として用いたものである。
【００４９】
ここではルートＬの評価値を算出する方法を示したのが図５−２と図６−２である。まず、ステップＳ４１で「１.データ送信端末ｎ0からルートＬ上の次の中継端末ｎ1Lにルートの評価値１を記述するための評価値パケットを送信」する。ここで評価値１はルート上に存在する端末の最小余剰電力である。
【００５０】
ステップＳ４２で「２.ｎ1Lがｎ0から評価値パケットをデータ送受信機能で受信」する。ステップＳ４３で「３.ｎ1Lのデータ処理機能が評価値パケットを受け取り、識別して評価値処理機能」に渡す。
【００５１】
次に、ステップＳ４４で「４．評価値処理機能は自端末の余剰電力Ｅ1Lを余剰電力保持機能から取り出し、評価値１と比較して自端末の余剰電力Ｅ1Lのほうが小さいときには評価値１に書き込む。」そして、ステップＳ４５で「５. 評価値処理機能は更新した評価値パケットをデータ処理機能に渡しデータ送受信機能からｎ2L」へ送信する。
【００５２】
送信後、ステップＳ４６で「６.ｎ2Lがｎ1Lからの評価値パケットをデータ送受信機能で受信」する。ステップＳ４７は、「７.ｎ2Lのデータ処理機能が評価値パヶツトを受け取り識別して評価値処理機能」に渡す。
【００５３】
ステップＳ４８では、「８.評価値処理機能は自端末の余剰電力Ｅ2Lを余剰電力保持機能から取り出し評価値パケットの中の評価値１と比較して自端末の余剰電力Ｅ2Lのほうが小さいときには評価値１に書き換える。」
その後、ステップＳ４５からステップＳ４８を繰り返し、「ｎDがｎ3Lから評価値パケットをデータ送受信機能で受信」、即ち受信端末まで評価パケットが到達するのがステップＳ４９である。ステップＳ５０は「１０.評価値パケットを受け取ったｎDはその評価値パケットをｎ0まで元通りのルート」で送信する。そして、ステップＳ５１で「１１.ルートＬの評価値１を受け取る。このような手順で同様にルートＭ，Ｎ，０の評価値１を送信端末は得ることができる。
【００５４】
図７−２はルートごとの評価値１を得た送信端末がルートを決定するフロー図である。図において、ステップＳ９１で「１.ｎ0がルートＬ、Ｍ、Ｎ、０の評価値として最小余剰電力」を受け取る。そして、ステップＳ９２で「２.評価値をルート選択機能」に渡す。その後、ステップＳ９３は「３.評価値（最小余剰電力）が最大となるルートを選択する。
【００５５】
［第三の形態］
ルートｊに属する端末ｎijの余剰電力をＥijとしその最小値Ｅjをそのルートの評価値とする
Ｅj＝min｛Ｅij|ｉ∈route ｊ｝
その値が最も小さいルートをｙとした時
Ｅy＝min{Ｅj|ｊ∈Ａ}
ここでＡはデータ伝送に考えられるルート全ての集合である。ルートｙをデータ伝送に考えられるルート全ての集合Ａから除いた集合Ｂを定義する。
【００５６】
ルートｊに属する端末ｎijの余剰電力をＥijとしその合計ΣＥij（i=0からD-1までの総和）をそのルートの評価値Ｒjとして定義する（ｎ0は送信端末、ｎDは受信端末）。
【００５７】
【数２】
2005244381.tif 000004
【００５８】
その値が最も大きいルートｘを選択すると次式として示される。
【００５９】
Ｒx＝max{Ｒj|ｊ∈Ｂ}
次に、第三の形態を図５−３、図６−３、図７−３を使って説明する。これらは評価値としてルート上に存在する端末の余剰電力の和ΣＥij（i=0からD-1までの総和）を評価値１、ルート上に存在する端末の最小余剰電力Ｅj＝min｛Ｅij|ｉ∈route ｊ｝を評価値２として用いたものである。
【００６０】
ここでは、ルートＬの評価値を算出する方法を示したのが図５−３と図６−３である。
まず、ステップＳ６１で「１.データ送信端末ｎ0からルートＬ上に存在する各端末の余剰電力の和を評価値１、ルート上に存在する端末の最小余剰電力を評価値２に記述するための評価値パケットをルート上に」送信する。
【００６１】
ステップＳ６２で「２.ｎ1Lがｎ0から評価値パケットをデータ送受信機能で受信」する。次に、ステップＳ６３で「３.ｎ1Lのデータ処理機能が評価値パケットを受け取り識別して、評価値処理機能」に渡される。
【００６２】
その後、ステップＳ６４で「４．評価値処理機能は自端末の余剰電力Ｅ1Lを余剰電力保持機能から取り出し、評価値１に足し合わせた値を書込み評価値２と比較して自端末の余剰電力Ｅ1Lのほうが小さければ自端末の余剰電力に評価値２」を書き換える。そして、評価値処理機能は、ステップＳ６５で「５.更新した評価値パケットをデータ処理機能に渡しデータ送受信機能からｎ2L」へ送信する。
【００６３】
送信後、ステップＳ６６で「６.ｎ2Lがｎ1Lからの評価値パケットをデータ送受信機能で受信」する。ステップＳ６７は、「７. データ処理機能が評価値パヶツトを受け取り識別して評価値処理機能」に渡す。
【００６４】
ステップＳ６８では、「８.評価値処理機能は自端末の余剰電力Ｅ2Lを余剰電力保持機能から取り出し、評価値パケットの中の評価値１に足し合わせた値を書戻し、評価値２と比較して自端末の余剰電力Ｅ2Lのほうが小さければ自端末の余剰電力に評価値２」を書き換える。
【００６５】
その後、ステップＳ６５からステップＳ６８を繰り返し、「ｎDがｎ3Lから評価値パケットをデータ送受信機能で受信」、即ち受信端末まで評価パケットが到達するのがステップＳ６９である。ステップＳ７０は「１０.評価値パケットを受け取ったｎDはその評価値パケットをｎ0まで元通りのルート」で送信する。そして、ステップＳ７１で「１１.ルートＬの評価値１、評価値２を受け取る。このような手順でルート毎の評価値１、評価値２を送信端末は得ることができる。
【００６６】
図７−３はルートごとの評価値１、評価値２を得た送信端末がルートを決定するフロー図である。図において、ステップＳ１００で「１.ｎ0がルートＬ、Ｍ、Ｎ、０の評価値１、評価値２として余剰電力の和と最小余剰電力」を受け取る。そして、ステップＳ１０１で「２.評価値１、評価値２をルート選択機能」に渡す。その後、ステップＳ１０２は「３.評価値２が最小余剰電力となるルートを除いて評価値１が最大となるルートを選択する。
【００６７】
［第四の形態］
ルートｊに属する端末ｎijの余剰電力をＥijとしその最小値Ｅjをそのルートの評価値とする
Ｅj＝min｛Ｅij|ｉ∈route ｊ｝
ここでＥjが閾値γ以上であるルートの集合をＱとする。送信端末と受信端末を結ぶ全てのルートの集合をＡとした時、集合の関係は図８のようになる。
【００６８】
（１）Ａ∩Ｑ≠Φのとき：第一の形態に従う。
【００６９】
ルートｊに属する端末ｎijの余剰電力をＥijとしその合計ΣＥij（i=0からD-1までの総和）をそのルートの評価値Ｒjとして定義する（ｎ0は送信端末、ｎDは受信端末）。
【００７０】
【数３】
2005244381.tif 000005
【００７１】
その値が最も大きいルートｘを選択する。
【００７２】
Ｒx＝max{Ｒj|ｊ∈Ｑ}
（２）Ａ∩Ｑ＝Φのとき：第二の形態に従う。
【００７３】
ルートｊに属する端末ｎijの余剰電力をＥijとしその最小値をそのルートの評価値Ｅjとする。
【００７４】
Ｅj＝min｛Ｅij|ｉ∈route ｊ｝
その値が最も大きいルートｘを選択する。
【００７５】
Ｅx＝max{Ｅj|ｊ∈Ａ}
第四の形態は、第三の形態と全く同様に評価値１、評価値２を得る。図７−４はルートごとの評価値を得た送信端末がルートを決定するフロー図である。
【００７６】
ステップＳ１１０は「１.ｎ0がルートＬ，Ｍ，Ｎ，Ｏの評価値としてルート上の余剰電力の和を評価値１として、最小余剰電力を評価値２として」受け取る。ステップＳ１１１は「２.評価値１と評価値２をルート選択機能」に渡す。
【００７７】
次に、ステップＳ１１２で「３.評価値２が閾値γ以上のものが存在するか否か」を評価する。γ以上のものが存在する（Yes）ならば、評価値２がγ以上のルートの集合Ｑの中で評価値１が最大となるルートを選択し（ステップＳ１１３）、γ以上のものが存在しない（No）ならば、すべてのルートの集合Ａから評価値２が最大のルートを選択する（ステップＳ１１４）。
【００７８】
なお、図３で示した端末構成の機能をコンピュータのプログラムで構成したり、あるいは、図４の処理ステップ、図５から図７に示す第一の形態から第四の形態の処理をコンピュータのプログラムで構成したりして、そのプログラムをコンピュータ実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラム、あるいはコンピュータにその処理やステップを実行させるためのプログラムを、そのコンピュータが読み取りできる記録媒体、例えば、フレキシブルディスクや、ＭＯ，ＲＯＭ，メモリカード、ＣＤ，ＤＶＤ，リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。
【００７９】
また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。これらの記録媒体からコンピュータに前記プログラムをインストールすることにより、あるいはネットワークからダウンロードしてコンピュータに前記プログラムをインストールすることにより、本発明を実施することが可能となる。
【図面の簡単な説明】
【００８０】
【図１】本発明の実施の形態におけるネットワーク構成と伝送におけるルート例を示す説明図。
【図２】ルート決定の全体の流れを示すフロー図。
【図３】本発明の実施の形態における端末の構成を示すブロック図。
【図４】余剰電力の算出と保持の流れを示すフロー図。
【図５−１】評価値を算出する際の第一の形態を説明する模式図。
【図５−２】評価値を算出する際の第二の形態を説明する模式図。
【図５−３】評価値を算出する際の第三、第四の形態を説明する模式図。
【図６−１】第一の形態における評価値の算出フロー図。
【図６−２】第二の形態における評価値の算出フロー図。
【図６−３】第三、第四の形態における評価値の算出フロー図。
【図７−１】第一の形態におけるルート決定のフロー図。
【図７−２】第二の形態におけるルート決定のフロー図。
【図７−３】第三、第四の形態におけるルート決定のフロー図。
【図８】第四の形態におけるルートの集合を示した説明図。
【符号の説明】
【００８１】
ｎ0，ｎ1L〜ｎD…データの伝送、中継機能を有する無線通信端末
L,M,N,O…データ伝送のルート
１０…データ送受信機能
１１…データ処理機能
１２…評価値処理機能
１３…リート選択機能
１４…運用予定期間保持機能
１５…経過時間算出機能
１６…経過時間保持機能
１７…残運用期間算出機能
１８…残運用期間保持機能
１９…残留電力検出機能
２０…残留電力保持機能
２１…送信頻度保持機能
２２…送信電力保持機能
２３…余剰電力算出機能
２４…余剰電力保持機能
【図１】
2005244381.tif 000006
【図２】
2005244381.tif 000007
【図３】
2005244381.tif 000008
【図４】
2005244381.tif 000009
【図５−１】
2005244381.tif 000010
【図５−２】
2005244381.tif 000011
【図５−３】
2005244381.tif 000012
【図６−１】
2005244381.tif 000013
【図６−２】
2005244381.tif 000014
【図６−３】
2005244381.tif 000015
【図７−１】
2005244381.tif 000016
【図７−２】
2005244381.tif 000017
【図７−３】
2005244381.tif 000018
【図８】
2005244381.tif 000019