(57)【要約】【課題】従来より多くの使用要求に対して資源を割り当てる。【解決手段】割当処理部１９は、使用要求データベース１８において、有効なレコードであり且つ当該レコード内の競合候補数より多い候補総数を含むレコードの有無を判定する第１の判定を行い（Ｓ１）、該当のレコードがあるなら（Ｓ１：ＹＥＳ）、当該レコードのみに含まれるデバイスＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該デバイスＩＤが含まれるなら当該デバイスＩＤを削除（Ｓ３）、すなわち、当該レコードに対応する使用要求に当該デバイスＩＤのデバイスを割り当て（Ｓ３）、当該レコードを無効化し（Ｓ５）、有効なレコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算する第１の再計算を行い（Ｓ７）、制御を第１の判定（Ｓ１）に戻す一方、第１の判定で該当のレコードがないなら（Ｓ１：ＮＯ）、予め設定された割当処理（Ｓ１００）を呼び出す。【選択図】図５
2015220707.tif 000002
【特許請求の範囲】
【請求項１】
資源に対する複数の使用要求のそれぞれにつき、当該使用要求に合致しかつ割り当てられてない資源の資源ＩＤと、当該資源の総数である候補総数と、当該使用要求と他の使用要求とに合致しかつ割り当てられてない資源の総数である競合候補数とが含まれ且つ有効または無効に設定可能なレコードを備える使用要求データベースと、
１以上の前記使用要求に対し該使用要求に合致する資源を割り当てる割当処理部とを備え、
前記割当処理部は、
前記使用要求データベースにおいて、有効なレコードであり且つ当該レコード内の競合候補数より多い候補総数を含むレコードの有無を判定する第１の判定を行い（Ｓ１）、該当のレコードがあるなら（Ｓ１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ３）、当該レコードを無効化し（Ｓ５）、有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第１の再計算を行い（Ｓ７）、制御を第１の判定（Ｓ１）に戻す一方、前記第１の判定で該当のレコードがないなら（Ｓ１：ＮＯ）、予め設定された割当処理（Ｓ１００）を呼び出す手段を有し、
前記割当処理（Ｓ１００）は、
前記使用要求データベースにおいて有効なレコードであり且つ当該レコード内の候補総数の逆数の最大値に対応するレコードの有無を判定する第２の判定を行い（Ｓ１１）、該当のレコードがあるなら（Ｓ１１：ＹＥＳ）、該当のレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第２の再計算を行う（Ｓ１３）手段と、
前記第２の再計算後の前記使用要求データベースの有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第３の判定を行い（Ｓ２１）、該当のレコードがあるなら（Ｓ２１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ２３）、当該レコードを無効化し（Ｓ２５）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第３の再計算を行い（Ｓ２７）、前記割当処理（Ｓ１００）を呼び出す手段と、
前記第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、前記使用要求データベースの有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードから１つの資源ＩＤ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）手段と、
前記第５の再計算後の前記使用要求データベースの有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第４の判定を行い（Ｓ６１）、該当のレコードがないなら（Ｓ６１：ＮＯ）、前記割当処理（Ｓ１００）を呼び出す手段と、
該当のレコードがあるなら（Ｓ６１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ６３）、当該レコードを無効化し（Ｓ６５）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第６の再計算を行い（Ｓ６７）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第７の再計算を行い（Ｓ６９）、制御を第４の判定（Ｓ６１）に戻す手段と、
前記呼び出された割当処理（Ｓ１００）が終了したなら、または、前記第２の判定（Ｓ１１）で該当のレコードがないなら（Ｓ１１：ＮＯ）、前記使用要求データベースの全レコードが無効か否かを判定する第６の判定を行い（Ｓ７１）、前記使用要求データベースの全レコードが無効なら（Ｓ７１：ＹＥＳ）、割り当て処理（Ｓ１００）を終了させる手段と、
前記第６の判定で、前記使用要求データベースのいずれかのレコードが有効であると判定されたなら（Ｓ７１：ＮＯ）、当該レコードのいずれかに資源ＩＤがあるか否かを判定し（Ｓ７３）、当該レコードのいずれかに資源ＩＤがある（Ｓ７３：ＹＥＳ）、制御を前記第２の判定（Ｓ１１）に戻す一方、当該レコードの全てに資源ＩＤがないなら（Ｓ７３：ＮＯ）、割り当て処理（Ｓ１００）を終了させる手段と
を備えることを特徴とする資源割当装置。
【請求項２】
前記使用要求データベースのレコードは、当該レコードに対応する使用要求の優先度を設定可能であり、
前記第５の再計算を行う（Ｓ５６）手段に代えて、
前記第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、前記第２の判定の該当のレコードにおいて優先度が最大のレコードの有無を判定し（Ｓ３１）、該当のレコードがあるなら（Ｓ３１：ＹＥＳ）、当該レコードにおいて資源ＩＤにより候補総数と競合候補数を再計算し（Ｓ３３）、前記割当処理（Ｓ１００）を呼び出し、該当のレコードがないなら（Ｓ３１：ＮＯ）、前記使用要求データベースの有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）手段
を備えることを特徴とする請求項１記載の資源割当装置。
【請求項３】
資源割当装置の動作方法であって、
前記資源割当装置は、
資源に対する複数の使用要求のそれぞれにつき、当該使用要求に合致しかつ割り当てられてない資源の資源ＩＤと、当該資源の総数である候補総数と、当該使用要求と他の使用要求とに合致しかつ割り当てられてない資源の総数である競合候補数とが含まれ且つ有効または無効に設定可能なレコードを備える使用要求データベースと、
１以上の前記使用要求に対し該使用要求に合致する資源を割り当てる割当処理部とを備え、
前記動作方法は、
前記割当処理部が、
前記使用要求データベースにおいて、有効なレコードであり且つ当該レコード内の競合候補数より多い候補総数を含むレコードの有無を判定する第１の判定を行い（Ｓ１）、該当のレコードがあるなら（Ｓ１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ３）、当該レコードを無効化し（Ｓ５）、有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第１の再計算を行い（Ｓ７）、制御を第１の判定（Ｓ１）に戻す一方、前記第１の判定で該当のレコードがないなら（Ｓ１：ＮＯ）、予め設定された割当処理（Ｓ１００）を呼び出す工程を有し、
前記割当処理（Ｓ１００）は、
前記使用要求データベースにおいて有効なレコードであり且つ当該レコード内の候補総数の逆数の最大値に対応するレコードの有無を判定する第２の判定を行い（Ｓ１１）、該当のレコードがあるなら（Ｓ１１：ＹＥＳ）、該当のレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第２の再計算を行う（Ｓ１３）工程と、
前記第２の再計算後の前記使用要求データベースの有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第３の判定を行い（Ｓ２１）、該当のレコードがあるなら（Ｓ２１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ２３）、当該レコードを無効化し（Ｓ２５）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第３の再計算を行い（Ｓ２７）、前記割当処理（Ｓ１００）を呼び出す工程と、
前記第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、前記使用要求データベースの有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードから１つの資源ＩＤ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）工程と、
前記第５の再計算後の前記使用要求データベースの有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第４の判定を行い（Ｓ６１）、該当のレコードがないなら（Ｓ６１：ＮＯ）、前記割当処理（Ｓ１００）を呼び出す工程と、
該当のレコードがあるなら（Ｓ６１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ６３）、当該レコードを無効化し（Ｓ６５）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第６の再計算を行い（Ｓ６７）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第７の再計算を行い（Ｓ６９）、制御を第４の判定（Ｓ６１）に戻す工程と、
前記呼び出された割当処理（Ｓ１００）が終了したなら、または、前記第２の判定（Ｓ１１）で該当のレコードがないなら（Ｓ１１：ＮＯ）、前記使用要求データベースの全レコードが無効か否かを判定する第６の判定を行い（Ｓ７１）、前記使用要求データベースの全レコードが無効なら（Ｓ７１：ＹＥＳ）、割り当て処理（Ｓ１００）を終了させる手段と、
前記第６の判定で、前記使用要求データベースのいずれかのレコードが有効であると判定されたなら（Ｓ７１：ＮＯ）、当該レコードのいずれかに資源ＩＤがあるか否かを判定し（Ｓ７３）、当該レコードのいずれかに資源ＩＤがある（Ｓ７３：ＹＥＳ）、制御を前記第２の判定（Ｓ１１）に戻す一方、当該レコードの全てに資源ＩＤがないなら（Ｓ７３：ＮＯ）、割り当て処理（Ｓ１００）を終了させる工程と
を備えることを特徴とする資源割当装置の動作方法。
【請求項４】
前記使用要求データベースのレコードは、当該レコードに対応する使用要求の優先度を設定可能であり、
前記第５の再計算を行う（Ｓ５６）工程に代えて、
前記第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、前記第２の判定の該当のレコードにおいて優先度が最大のレコードの有無を判定し（Ｓ３１）、該当のレコードがあるなら（Ｓ３１：ＹＥＳ）、当該レコードにおいて資源ＩＤにより候補総数と競合候補数を再計算し（Ｓ３３）、前記割当処理（Ｓ１００）を呼び出し、該当のレコードがないなら（Ｓ３１：ＮＯ）、前記使用要求データベースの有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）工程
を備えることを特徴とする請求項３記載の資源割当装置の動作方法。
【請求項５】
請求項１または２記載の資源割当装置としてコンピュータを機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、資源割当装置およびその動作方法に関するものである。
【背景技術】
【０００２】
Machine to Machine（M2M）では、M2Mアプリケーションが、センサ等の入力デバイスによって受け取った情報に基づきスピーカ等の出力デバイスの制御を通信ネットワークを介して行うことが想定されている。
【０００３】
M2Mアプリケーションが対象デバイスを遠隔制御するためには、時々刻々と変化するデバイスの動的情報を正確に把握する必要がある。ここで言うデバイスの動的情報とは、デバイスの位置情報、電源状態、故障状態、ネットワーク接続状態などを指す。
【０００４】
M2Mにおけるデバイス管理は、外部アプリケーション装置との処理を仲介するサーバ装置と、デバイスの状態をサーバ装置に送信するゲートウェイ装置により実施される。ゲートウェイ装置は、例えば、ゲートウェイ装置に接続しているデバイスを管理する機能、外部システムからの使用要求の処理や外部システムへの接続制御処理を行う機能を有する。  M2Mで導入されるデバイスは、500億個にものぼると推定されている。
【０００５】
他のネットワークサービスに影響を及ぼさない形での数億オーダのデバイス管理、および、デバイスの導入・維持コストの低減を目指した省電力化の２点を両立するために、M2Mデバイスはほとんどの時間、スリープ・休止など電源が入っていない状態にあることが多いと推測されている。
【０００６】
さらに、M2Mでは、サブギガ帯（1GHz以下）無線ネットワークを使用するデバイスの導入拡大が見込まれている（非特許文献１）。
しかし、当該帯域のネットワークについては、最大連続送信時間や、1時間あたり送信時間の合計に細かな制限が設けられており、ゲートウェイ装置とデバイスの接続時間が制約されるため、ゲートウェイ装置が常にデバイスのリアルタイム情報を把握しているとは限らない。
【０００７】
したがって、外部アプリケーション装置がデバイスを発見する際には、
Ａ．外部アプリケーション装置から使用要求を受信したサーバ装置が、当該アプリケーションが使用権（アクセス権）を有するデバイスの中で使用要求を満たすものを抽出し、
Ｂ．当該デバイスを管理するゲートウェイ装置に対してデバイス状態確認要求を送信し、
Ｃ．ゲートウェイ装置が当該デバイスの動的情報を確認した後サーバ装置に応答を送信し、
Ｄ．サーバ装置が当該応答に基づきデバイスの使用可否を外部アプリケーション装置に送信するという一連の処理を、外部アプリケーション装置の使用要求ごとに逐次実施する必要がある（図１７参照）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１３−０７０３０２号公報
【非特許文献】
【０００９】
【非特許文献１】岡庭ら、日本国内における920MHz帯のZigBee IP仕様、OKIテクニカルレビュー第221号、Vol. 80、No.1、pp.70-73、2013
【発明の概要】
【発明が解決しようとする課題】
【００１０】
デバイスのリアルタイムな動的情報は、デバイスの電源が入っていないと分からない。  サーバ装置からのデバイス状態確認要求があった時点におけるデバイスの電源状態が、スリープ・休止など電源が入っていない状態の場合には、デバイスを一旦起動した後でないと確認できないため、サーバ装置からの要求を受信してすぐに応答を返すことができるとは限らない。このため、あるデバイスの状態確認を行っている間に、同デバイスに対するデバイス状態確認要求が送信される可能性がある。
【００１１】
外部アプリケーション装置の使用要求を受信するごとにデバイスの状態確認を行っていると、サーバ装置−デバイス間のトランザクション数が増加してネットワーク負荷が高くなってしまう虞がある。
【００１２】
各外部アプリケーション装置が送信した使用要求を、それぞれ独立かつ先着順に扱ってしまうため、ある外部アプリケーション装置に対してデバイスを割り当てられない状況が発生しうる。
【００１３】
よく知られた資源割当手法としては、先着順割当（FIFO）や優先度基準のものがある。  図１６に示すように、FIFOをデバイスに適用した場合には、最も早い使用要求Ａから順にデバイスを割り当てていくので、例えば、後の使用要求Ｃへデバイスを割り当てることができない。
【００１４】
優先度基準でデバイス割当を行う際については、優先度が高い使用要求Ｂ、Ｇ、Ｈへのデバイス割当を先行して行い、例えば、優先度が同じ場合は先着順とする。優先度の高い使用要求へのデバイス割当が終了した時点で、低優先度の使用要求へのデバイス割当に移行する。この場合についても、使用要求Ｃへデバイスを割り当ることができない。
【００１５】
以上より、これらの手法では全ての使用要求へデバイスを割り当ることができない場合が存在する。
【００１６】
図１６の固定割当に示すように、特許文献１では、あらかじめ使用要求に割り当てるデバイスを定めておくことにより、あるデバイスが他の使用要求に割り当てられてしまうことを防いでいる。しかし、M2Mのように、デバイスの動的状態によって流動的に変わりうる場合に、割り当てられたデバイスが使用要求を満たさず、結果的にデバイスを割り当てられなかったことと同じ状態に陥ってしまう虞がある。
【００１７】
本発明は、上記事情を鑑みてなされたものであり、従来より多くの使用要求に対して資源を割り当てられる資源割当装置とその動作方法を提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記の課題を解決するために、第１の本発明は、資源に対する複数の使用要求のそれぞれにつき、当該使用要求に合致しかつ割り当てられてない資源の資源ＩＤと、当該資源の総数である候補総数と、当該使用要求と他の使用要求とに合致しかつ割り当てられてない資源の総数である競合候補数とが含まれ且つ有効または無効に設定可能なレコードを備える使用要求データベースと、１以上の前記使用要求に対し該使用要求に合致する資源を割り当てる割当処理部とを備え、前記割当処理部は、前記使用要求データベースにおいて、有効なレコードであり且つ当該レコード内の競合候補数より多い候補総数を含むレコードの有無を判定する第１の判定を行い（Ｓ１）、該当のレコードがあるなら（Ｓ１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ３）、当該レコードを無効化し（Ｓ５）、有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第１の再計算を行い（Ｓ７）、制御を第１の判定（Ｓ１）に戻す一方、前記第１の判定で該当のレコードがないなら（Ｓ１：ＮＯ）、予め設定された割当処理（Ｓ１００）を呼び出す手段を有し、前記割当処理（Ｓ１００）は、前記使用要求データベースにおいて有効なレコードであり且つ当該レコード内の候補総数の逆数の最大値に対応するレコードの有無を判定する第２の判定を行い（Ｓ１１）、該当のレコードがあるなら（Ｓ１１：ＹＥＳ）、該当のレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第２の再計算を行う（Ｓ１３）手段と、前記第２の再計算後の前記使用要求データベースの有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第３の判定を行い（Ｓ２１）、該当のレコードがあるなら（Ｓ２１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ２３）、当該レコードを無効化し（Ｓ２５）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第３の再計算を行い（Ｓ２７）、前記割当処理（Ｓ１００）を呼び出す手段と、前記第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、前記使用要求データベースの有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードから１つの資源ＩＤ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）手段と、前記第５の再計算後の前記使用要求データベースの有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第４の判定を行い（Ｓ６１）、該当のレコードがないなら（Ｓ６１：ＮＯ）、前記割当処理（Ｓ１００）を呼び出す手段と、該当のレコードがあるなら（Ｓ６１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ６３）、当該レコードを無効化し（Ｓ６５）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第６の再計算を行い（Ｓ６７）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第７の再計算を行い（Ｓ６９）、制御を第４の判定（Ｓ６１）に戻す手段と、前記呼び出された割当処理（Ｓ１００）が終了したなら、または、前記第２の判定（Ｓ１１）で該当のレコードがないなら（Ｓ１１：ＮＯ）、前記使用要求データベースの全レコードが無効か否かを判定する第６の判定を行い（Ｓ７１）、前記使用要求データベースの全レコードが無効なら（Ｓ７１：ＹＥＳ）、割り当て処理（Ｓ１００）を終了させる手段と、前記第６の判定で、前記使用要求データベースのいずれかのレコードが有効であると判定されたなら（Ｓ７１：ＮＯ）、当該レコードのいずれかに資源ＩＤがあるか否かを判定し（Ｓ７３）、当該レコードのいずれかに資源ＩＤがある（Ｓ７３：ＹＥＳ）、制御を前記第２の判定（Ｓ１１）に戻す一方、当該レコードの全てに資源ＩＤがないなら（Ｓ７３：ＮＯ）、割り当て処理（Ｓ１００）を終了させる手段とを備えることを特徴とする。
【００１９】
例えば、前記使用要求データベースのレコードは、当該レコードに対応する使用要求の優先度を設定可能であり、前記第５の再計算を行う（Ｓ５６）手段に代えて、前記第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、前記第２の判定の該当のレコードにおいて優先度が最大のレコードの有無を判定し（Ｓ３１）、該当のレコードがあるなら（Ｓ３１：ＹＥＳ）、当該レコードにおいて資源ＩＤにより候補総数と競合候補数を再計算し（Ｓ３３）、前記割当処理（Ｓ１００）を呼び出し、該当のレコードがないなら（Ｓ３１：ＮＯ）、前記使用要求データベースの有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）手段を備える。
【００２０】
第２の本発明は、資源割当装置の動作方法であって、前記資源割当装置は、資源に対する複数の使用要求のそれぞれにつき、当該使用要求に合致しかつ割り当てられてない資源の資源ＩＤと、当該資源の総数である候補総数と、当該使用要求と他の使用要求とに合致しかつ割り当てられてない資源の総数である競合候補数とが含まれ且つ有効または無効に設定可能なレコードを備える使用要求データベースと、１以上の前記使用要求に対し該使用要求に合致する資源を割り当てる割当処理部とを備え、前記動作方法は、前記割当処理部が、前記使用要求データベースにおいて、有効なレコードであり且つ当該レコード内の競合候補数より多い候補総数を含むレコードの有無を判定する第１の判定を行い（Ｓ１）、該当のレコードがあるなら（Ｓ１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ３）、当該レコードを無効化し（Ｓ５）、有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第１の再計算を行い（Ｓ７）、制御を第１の判定（Ｓ１）に戻す一方、前記第１の判定で該当のレコードがないなら（Ｓ１：ＮＯ）、予め設定された割当処理（Ｓ１００）を呼び出す工程を有し、前記割当処理（Ｓ１００）は、前記使用要求データベースにおいて有効なレコードであり且つ当該レコード内の候補総数の逆数の最大値に対応するレコードの有無を判定する第２の判定を行い（Ｓ１１）、該当のレコードがあるなら（Ｓ１１：ＹＥＳ）、該当のレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第２の再計算を行う（Ｓ１３）工程と、前記第２の再計算後の前記使用要求データベースの有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第３の判定を行い（Ｓ２１）、該当のレコードがあるなら（Ｓ２１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ２３）、当該レコードを無効化し（Ｓ２５）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第３の再計算を行い（Ｓ２７）、前記割当処理（Ｓ１００）を呼び出す工程と、前記第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、前記使用要求データベースの有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードから１つの資源ＩＤ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）工程と、前記第５の再計算後の前記使用要求データベースの有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第４の判定を行い（Ｓ６１）、該当のレコードがないなら（Ｓ６１：ＮＯ）、前記割当処理（Ｓ１００）を呼び出す工程と、該当のレコードがあるなら（Ｓ６１：ＹＥＳ）、当該レコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ６３）、当該レコードを無効化し（Ｓ６５）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第６の再計算を行い（Ｓ６７）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第７の再計算を行い（Ｓ６９）、制御を第４の判定（Ｓ６１）に戻す工程と、前記呼び出された割当処理（Ｓ１００）が終了したなら、または、前記第２の判定（Ｓ１１）で該当のレコードがないなら（Ｓ１１：ＮＯ）、前記使用要求データベースの全レコードが無効か否かを判定する第６の判定を行い（Ｓ７１）、前記使用要求データベースの全レコードが無効なら（Ｓ７１：ＹＥＳ）、割り当て処理（Ｓ１００）を終了させる手段と、前記第６の判定で、前記使用要求データベースのいずれかのレコードが有効であると判定されたなら（Ｓ７１：ＮＯ）、当該レコードのいずれかに資源ＩＤがあるか否かを判定し（Ｓ７３）、当該レコードのいずれかに資源ＩＤがある（Ｓ７３：ＹＥＳ）、制御を前記第２の判定（Ｓ１１）に戻す一方、当該レコードの全てに資源ＩＤがないなら（Ｓ７３：ＮＯ）、割り当て処理（Ｓ１００）を終了させる工程とを備えることを特徴とする。
【００２１】
例えば、前記使用要求データベースのレコードは、当該レコードに対応する使用要求の優先度を設定可能であり、前記第５の再計算を行う（Ｓ５６）工程に代えて、前記第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、前記第２の判定の該当のレコードにおいて優先度が最大のレコードの有無を判定し（Ｓ３１）、該当のレコードがあるなら（Ｓ３１：ＹＥＳ）、当該レコードにおいて資源ＩＤにより候補総数と競合候補数を再計算し（Ｓ３３）、前記割当処理（Ｓ１００）を呼び出し、該当のレコードがないなら（Ｓ３１：ＮＯ）、前記使用要求データベースの有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードのみに含まれる資源ＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該資源ＩＤが含まれるなら当該資源ＩＤを削除し（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、前記使用要求データベースの有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、前記第２の判定で該当する有効なレコードにおいて資源ＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）工程を備える。
【発明の効果】
【００２２】
本発明によれば、従来より多くの使用要求に対して資源（デバイス等）を割り当てることができる。
【図面の簡単な説明】
【００２３】
【図１】本実施の形態に係る資源割当装置の一例であるデバイス割当装置の利用形態の一例を示す図である。
【図２】図１におけるシーケンスの一例である。
【図３】デバイス割当装置１とゲートウェイ装置２の構成の一例を示す図である。
【図４】使用要求データベース１８の構成の一例を示す図である。
【図５】割当処理部１９の動作を示すフローチャートである。
【図６】割当処理（Ｓ１００）のフローチャートである。
【図７】実施例において使用要求Ｉ、Ｊにそれぞれデバイスｈ、ｊを割り当てる際の使用要求データベース１８を示す図である。
【図８】実施例において使用要求Ｃにデバイスａを割り当てる際の使用要求データベース１８を示す図である。
【図９】実施例において使用要求Ｃにデバイスａを割り当て再計算した後の使用要求データベース１８を示す図である。
【図１０】実施例において使用要求Ａにデバイスｃを割り当てる際の使用要求データベース１８のレコードＡ、Ｂ、Ｄを示す図である。
【図１１】実施例において使用要求Ｂにデバイスｂを割り当てる際の使用要求データベース１８を示す図である。
【図１２】実施例において使用要求Ｄにデバイスｄを割り当てる際の使用要求データベース１８を示す図である。
【図１３】実施例において使用要求Ｅにデバイスｅを割り当てる際の使用要求データベース１８を示す図である。
【図１４】実施例において使用要求Ｆ、Ｈにそれぞれデバイスｆ、ｉを割り当てる際の使用要求データベース１８を示す図である。
【図１５】実施例において使用要求Ｇにデバイスｇを割り当てる際の使用要求データベース１８を示す図である。
【図１６】本実施の形態に係るデバイス割当装置による使用要求へのデバイスの割り当てと従来技術を用いたデバイスの割り当てを比較した図である。
【図１７】従来におけるデバイス割り当てのシーケンスの一例を示す図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態について図面を参照して説明する。
【００２５】
図１は、本実施の形態に係る資源割当装置の一例であるデバイス割当装置の利用形態の一例を示す図である。
【００２６】
デバイス割当装置１は、ネットワークＮ１を介して、複数のゲートウェイ装置２に接続され、各ゲートウェイ装置２には、１以上のデバイスが接続される。
また、デバイス割当装置１は、ネットワークＮ２を介して、複数の外部アプリケーション装置３に接続される。
【００２７】
図２は、図１におけるシーケンスの一例である。
外部アプリケーション装置３は、アプリケーション（アプリＡ、Ｂ、Ｃ）がデバイスの使用要求をデバイス割当装置１に送信する。使用要求には場合によっては優先度が設定される。使用要求には、デバイス種別、デバイス性能、デバイス位置、アプリに関する情報が、デバイスの選定の条件として、設定される。
【００２８】
デバイス割当装置１では、対象デバイス抽出処理として、使用要求を送信してきた外部アプリケーション装置が使用権をもつデバイス群から、条件を満たすものを抽出する。
デバイス割当装置１では、対象デバイス抽出処理で抽出した各デバイスに対し、現在の状態確認を行う。つまり、デバイス種別、デバイス性能、デバイス位置などを含むデバイス状態確認要求をゲートウェイ装置２に送信する。
【００２９】
ゲートウェイ装置２は、デバイス状態確認処理として、デバイス割当装置からの使用要求に応じ、該当デバイスの現在状態を確認する。つまり、現在状態確認信号をデバイスに送信し、デバイスから現在状態応答信号を受信し、デバイス状態応答をデバイス割当装置に送信する。
【００３０】
デバイス割当装置１は、最初にデバイス状態確認要求を送信する時にフラグを立て、同デバイスに対するデバイス状態確認要求を必要とする外部アプリケーション装置の情報をデバイス割当装置１内のキューに入れてゲートウェイ装置２からデバイス状態応答を待機する。デバイス状態応答を受信したら、これを最初のデバイス状態確認要求に対応する外部アプリケーション装置ならびにキューに情報を入れた外部アプリケーション装置の両方に対応するものとして処理する。これにより、後者の外部アプリケーション装置についてはデバイス状態確認要求を送信しなくてよく、その結果、デバイス割当装置１−ゲートウェイ装置２間およびゲートウェイ装置２−デバイス間のトランザクション数を低減できる。
【００３１】
デバイス割当装置１は、デバイス状態応答に基づいて、複数の使用要求へ１回の割り当てでデバイスを割り当て、割り当てられた使用要求を送信してきた外部アプリケーション装置３には、使用可の使用可否応答を、割り当てられなかった使用要求を送信してきた外部アプリケーション装置３には、使用不可の使用可否応答を同時に送信する。使用可否を使用要求ごとに送信するのでなく、割り当てごとに送信するので、外部アプリケーション装置３−デバイス割当装置１間のトランザクション数を低減できる。
【００３２】
図３は、デバイス割当装置１とゲートウェイ装置２の構成の一例を示す図である。
デバイス割当装置１は、デバイス使用要求受信部１１、対象デバイス抽出処理部１２、デバイス状態確認要求送信判定部１３、デバイス状態確認要求送信部１４、外部アプリケーション装置情報保持部１５、デバイス状態応答受信部１６、デバイス使用可否判定部１７、使用要求データベース１８、割当処理部１９、デバイス使用可否送信部１Ａを備える。
【００３３】
デバイス使用要求受信部１１は、外部アプリケーション装置３から送信されるデバイスの使用要求を受信し、対象デバイス抽出処理部１２へ引き渡す。
【００３４】
対象デバイス抽出処理部１２は、使用要求を送信した外部アプリケーション装置３が使用権を有するデバイスの中から使用要求を満たすデバイス抽出する。
【００３５】
デバイス状態確認要求送信判定部１３は、抽出されたデバイスを管理するゲートウェイ装置２に対して、既にデバイス状態確認要求を送信しているか否かを確認する。
【００３６】
デバイス状態確認要求送信部１４は、送信していなければ、ゲートウェイ装置２にデバイス状態確認要求を送信する。
【００３７】
外部アプリケーション装置情報保持部１５は、既にデバイス状態確認要求を送信している場合には、使用要求を送信した外部アプリケーション装置３に関する情報と使用要求を満たすデバイスに関する情報を対応づけて保持する。
【００３８】
デバイス状態応答受信部１６は、ゲートウェイ装置２から送信されるデバイス状態応答を受信する。
【００３９】
デバイス使用可否判定部１７は、受信したデバイス状態応答を基に、現在使用可能なデバイスか否かを判定する。例えば、故障中、あるいは別ユーザが使用中のデバイスは使用不可と判定する。
【００４０】
使用要求データベース１８は、割当処理部１９による処理に使用されるものであり、詳しくは後述する。
【００４１】
割当処理部１９は、現在使用可能と判定されたデバイス（候補）を使用要求に割り当てるものであり、詳しくは後述する。
【００４２】
デバイス使用可否送信部１Ａは、デバイスを割り当てることができた使用要求を送信してきた外部アプリケーション装置３には、使用可の使用可否応答を、デバイスを割り当てることができなかった使用要求を送信してきた外部アプリケーション装置３には、使用不可の使用可否応答を同時に送信する。
【００４３】
ゲートウェイ装置２は、デバイス状態確認要求受信部２１、デバイス現在状態確認処理部２２、デバイス状態応答送信部２３を備える。
【００４４】
デバイス状態確認要求受信部２１は、デバイス割当装置１からデバイス状態確認要求を受信し、デバイス現在状態確認処理部２２に引き渡す。
【００４５】
デバイス現在状態確認処理部２２は、デバイス状態確認要求を基に、現在状態を確認すべきデバイスを特定し、その動的情報である可用性（電源状態、故障状態、ネットワーク接続状態）と現在位置を確認する。
【００４６】
デバイス状態応答送信部２３は、現在のデバイスの可用性と現在位置を示すデバイス状態応答をデバイス割当装置１に送信する。
【００４７】
図４は、使用要求データベース１８の構成の一例を示す図である。
使用要求データベース１８は、デバイスに対する複数の使用要求のそれぞれにつき、当該使用要求に合致しかつ割り当てられてないデバイスの資源ＩＤ（以下、デバイスＩＤ）と、当該使用要求の優先度と、当該デバイスの総数である候補総数と、当該使用要求と他の使用要求とに合致し（競合し）かつ割り当てられてないデバイスの総数である競合候補数とが含まれ且つ有効または無効に設定可能なレコードを備える。レコードは、処理の過程で算出される候補総数の逆数を含んでもよい。
【００４８】
図５は、割当処理部１９の動作を示す第１のフローチャートである。
割当処理部１９は、使用要求データベース１８において、有効なレコードであり且つ当該レコード内の競合候補数より多い候補総数を含むレコードの有無を判定する第１の判定を行い（Ｓ１）、該当のレコードがあるなら（Ｓ１：ＹＥＳ）、当該レコードのみに含まれるデバイスＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該デバイスＩＤが含まれるなら当該デバイスＩＤを削除（Ｓ３）、すなわち、当該レコードに対応する使用要求に当該デバイスＩＤのデバイスを割り当て（Ｓ３）、当該レコードを無効化し（Ｓ５）、有効なレコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算する第１の再計算を行い（Ｓ７）、制御を第１の判定（Ｓ１）に戻す一方、第１の判定で該当のレコードがないなら（Ｓ１：ＮＯ）、予め設定された割当処理（Ｓ１００）を呼び出す。
【００４９】
図６は、割当処理（Ｓ１００）のフローチャートである。
割当処理部１９は、まず、使用要求データベース１８において有効なレコードであり且つ当該レコード内の候補総数の逆数の最大値に対応するレコードの有無を判定する第２の判定を行い（Ｓ１１）、該当のレコードがあるなら（Ｓ１１：ＹＥＳ）、該当のレコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算する第２の再計算を行う（Ｓ１３）。
【００５０】
割当処理部１９は、第２の再計算後の使用要求データベース１８の有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第３の判定を行い（Ｓ２１）、該当のレコードがあるなら（Ｓ２１：ＹＥＳ）、当該レコードのみに含まれるデバイスＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該デバイスＩＤが含まれるなら当該デバイスＩＤを削除し（Ｓ２３）、すなわち、当該レコードに対応する使用要求に当該デバイスＩＤのデバイスを割り当て（Ｓ２３）、当該レコードを無効化し（Ｓ２５）、使用要求データベース１８の有効なレコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算する第３の再計算を行い（Ｓ２７）、割当処理（Ｓ１００）を呼び出す。
【００５１】
割当処理部１９は、第３の判定で該当のレコードがないなら（Ｓ２１：ＮＯ）、第２の判定の該当のレコードにおいて優先度が最大のレコードの有無を判定し（Ｓ３１）、該当のレコードがあるなら（Ｓ３１：ＹＥＳ）、当該レコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算し（Ｓ３３）、前記割当処理（Ｓ１００）を呼び出す。
【００５２】
割当処理部１９は、割当処理部１９は、該当のレコードがないなら（Ｓ３１：ＮＯ）、使用要求データベース１８の有効なレコードに対応する使用要求の中で最も早く生じた使用要求のレコードのみに含まれるデバイスＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該デバイスＩＤが含まれるなら当該デバイスＩＤを削除し（Ｓ５１）、すなわち、最も早い使用要求に当該デバイスＩＤのデバイスを割り当て（Ｓ５１）、当該レコードを無効化し（Ｓ５３）、使用要求データベース１８の有効なレコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算する第４の再計算を行い（Ｓ５５）、第２の判定で該当する有効なレコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算する第５の再計算を行う（Ｓ５６）。
【００５３】
割当処理部１９は、第５の再計算後の使用要求データベース１８の有効なレコードにおいて競合候補数より多い候補総数を含むレコードの有無を判定する第４の判定を行い（Ｓ６１）、該当のレコードがないなら（Ｓ６１：ＮＯ）、割当処理（Ｓ１００）を呼び出す。
割当処理部１９は、該当のレコードがあるなら（Ｓ６１：ＹＥＳ）、当該レコードのみに含まれるデバイスＩＤが２以上なら１つ以外を削除し、かつ、他のレコードに当該デバイスＩＤが含まれるなら当該デバイスＩＤを削除し（Ｓ６３）、すなわち、当該レコードに対応する使用要求に当該デバイスＩＤのデバイスを割り当て（Ｓ６３）当該レコードを無効化し（Ｓ６５）、使用要求データベース１８の有効なレコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算する第６の再計算を行い（Ｓ６７）、第２の判定で該当する有効なレコードにおいてデバイスＩＤにより候補総数と競合候補数を再計算する第７の再計算を行い（Ｓ６９）、制御を第４の判定（Ｓ６１）に戻す。
【００５４】
割当処理部１９は、呼び出された割当処理（Ｓ１００）が終了したなら、または、第２の判定（Ｓ１１）で該当のレコードがないなら（Ｓ１１：ＮＯ）、使用要求データベース１８の全レコードが無効か否かを判定する第６の判定を行い（Ｓ７１）、使用要求データベース１８の全レコードが無効なら（Ｓ７１：ＹＥＳ）、処理を終了させる。
【００５５】
割当処理部１９は、第６の判定で、使用要求データベース１８のいずれかのレコードが有効であると判定されたなら（Ｓ７１：ＮＯ）、当該レコードのいずれかにデバイスＩＤがあるか否かを判定し（Ｓ７３）、当該レコードのいずれかにデバイスＩＤがある（Ｓ７３：ＹＥＳ）、制御を前記第２の判定（Ｓ１１）に戻す一方、当該レコードの全てにデバイスＩＤがないなら（Ｓ７３：ＮＯ）、割り当て処理（Ｓ１００）を終了させる
【００５６】
なお、優先度を使用しない場合、割当処理部１９は、ステップＳ２１：ＮＯの場合、制御をステップＳ５１に移す。
【００５７】
（実施例）
次に、割当処理部１９による割り当てを具体例を用いて説明する。
まず、図４に示すように、使用要求Ａ〜Ｊは、ＡからＪの順で得られたこととする。また、使用要求Ａに対応するレコードをレコードＡといい、他のレコードも同様に呼称する。デバイスＩＤ「ａ」に対応するデバイスをデバイスａといい、他のデバイスも同様に呼称する。また、デバイスＩＤ「ａ」〜「ｂ」、優先度、候補総数、競合候補数が図４に示すように配置されていることとする。
【００５８】
割当処理部１９は、図７に示すように、まず、第１の判定（Ｓ１）でレコードＩ、Ｊが該当する（Ｓ１：ＹＥＳ）。これにより、デバイスＩＤ「ｈ」、「ｊ」のデバイスが、それぞれ使用要求Ｉ、Ｊに割り当てられる。図では、割り当てるデバイスのデバイスＩＤを線で囲んで示す。
【００５９】
割当処理部１９は、図８に示すように、レコードＩ、ＪにそれぞれデバイスＩＤ「ｈ」、「ｊ」のみを残して他のデバイスＩＤを削除し（Ｓ３）、レコードＩ、Ｊを無効化し（Ｓ５）、第１の再計算を行い（Ｓ７）、制御を第１の判定（Ｓ１）に戻す。
【００６０】
第１の判定（Ｓ１）で該当のレコードがない（Ｓ１：ＮＯ）ので、第２の判定を行い（Ｓ１１）、レコードＣが該当する（Ｓ１１：ＹＥＳ）ので、レコードＣについて第２の再計算を行う（Ｓ１３）。
【００６１】
割当処理部１９は、次に、第３の判定を行い（Ｓ２１）、レコードＣが該当する（Ｓ２１：ＹＥＳ）ので、デバイスＩＤ「ａ」のデバイスが使用要求Ｃに割り当てられる。
【００６２】
割当処理部１９は、図９に示すように、レコードＣにデバイスＩＤ「ａ」のみを残して他のデバイスＩＤを削除し、他のレコードにデバイスＩＤ「ａ」が含まれるのでこれを削除し（Ｓ２３）、レコードＣを無効化する（Ｓ２５）。
【００６３】
割当処理部１９は、次に、レコード（Ａ、Ｂ、Ｄ〜Ｈ）において第３の再計算を行い（Ｓ２７）、割当処理（Ｓ１００）を呼び出す。
【００６４】
割当処理部１９は、呼び出された割当処理（Ｓ１００）の中で、まず、第２の判定を行い（Ｓ１１）、図９に示すように、レコードＡ、Ｂ、Ｄが該当する（Ｓ１１：ＹＥＳ）ので、レコードＡ、Ｂ、Ｄについて第２の再計算を行う（Ｓ１３）。
【００６５】
割当処理部１９は、次に、第３の判定を行い（Ｓ２１）、図１０に示すように、レコードＡが該当する（Ｓ２１：ＹＥＳ）ので、デバイスＩＤ「ｃ」のデバイスが使用要求Ａに割り当てられる。
【００６６】
割当処理部１９は、図１１に示すように、レコードＡにデバイスＩＤ「ｃ」のみを残して他のデバイスＩＤを削除し、他のレコードＨにもデバイスＩＤ「ａ」が含まれるのでこれを削除し（Ｓ２３）、レコードＡを無効化する（Ｓ２５）。
【００６７】
割当処理部１９は、レコードＢ、Ｄ〜Ｈについて第３の再計算を行い（Ｓ２７）、第３の再計算後、割当処理（Ｓ１００）を呼び出す。
【００６８】
割当処理部１９は、呼び出された割当処理（Ｓ１００）の中で、まず、第２の判定を行い（Ｓ１１）、図１１に示すように、レコードＢ、Ｄが該当する（Ｓ１１：ＹＥＳ）ので、レコードＢ、Ｄについて第２の再計算を行う（Ｓ１３）。
【００６９】
割当処理部１９は、次に、第３の判定を行い（Ｓ２１）、レコードＢ、Ｄいずれも該当しないので（Ｓ２１：ＮＯ）、レコードＢ、Ｄにおいて優先度が最大のレコードの有無を判定し（Ｓ３１）、レコードＢが該当する（Ｓ３１：ＹＥＳ）ので、レコードＢにおいて候補総数と競合候補数を再計算し（Ｓ３３）、割当処理（Ｓ１００）を呼び出す。
【００７０】
割当処理部１９は、呼び出された割当処理（Ｓ１００）の中で、まず、第２の判定を行い（Ｓ１１）、レコードＢが該当する（Ｓ１１：ＹＥＳ）ので、レコードＢについて第２の再計算を行う（Ｓ１３）。
【００７１】
割当処理部１９は、次に、第３の判定を行い（Ｓ２１）、レコードＢが該当する（Ｓ２１：ＹＥＳ）ので、レコードＢにデバイスＩＤ「ｂ」（ｄでもよい）のみを残して他のデバイスＩＤを削除し、他のレコードＤ、ＥにもデバイスＩＤ「ｂ」が含まれるのでこれを削除し（Ｓ２３）、レコードＢを無効化する（Ｓ２５）。
【００７２】
割当処理部１９は、次に、レコードＤ〜Ｈについて第３の再計算を行い（Ｓ２７）、第３の再計算後、割当処理（Ｓ１００）を呼び出す。
【００７３】
割当処理部１９は、呼び出された割当処理（Ｓ１００）の中で、第２の判定を行い（Ｓ１１）、図１２に示すように、レコードＤが該当する（Ｓ１１：ＹＥＳ）ので、レコードＤについて第２の再計算を行う（Ｓ１３）。
【００７４】
割当処理部１９は、次に、第３の判定を行い（Ｓ２１）、図１２に示すように、レコードＤが該当する（Ｓ２１：ＹＥＳ）ので、レコードＤにデバイスＩＤ「ｄ」（レコードＢにデバイスＩＤ「ｄ」のみを残した場合は「ｂ」）のみを残して他のデバイスＩＤを削除し、他のレコードＥにもデバイスＩＤ「ｄ」が含まれるのでこれを削除し（Ｓ２３）、レコードＢを無効化する（Ｓ２５）。
【００７５】
割当処理部１９は、次に、レコードＥ〜Ｈについて第３の再計算を行い（Ｓ２７）、第３の再計算後、割当処理（Ｓ１００）を呼び出す。
【００７６】
割当処理部１９は、呼び出された割当処理（Ｓ１００）の中で、第２の判定を行い（Ｓ１１）、図１３に示すように、レコードＥが該当する（Ｓ１１：ＹＥＳ）ので、レコードＥについて第２の再計算を行う（Ｓ１３）。
【００７７】
割当処理部１９は、次に、第３の判定を行い（Ｓ２１）、レコードＥが該当する（Ｓ２１：ＹＥＳ）ので、レコードＥにデバイスＩＤ「ｅ」のみを残して他のデバイスＩＤを削除し、他のレコードＦ、ＨにもデバイスＩＤ「ｅ」が含まれるのでこれを削除し（Ｓ２３）、レコードＥを無効化する（Ｓ２５）。
【００７８】
割当処理部１９は、次に、レコードＦ〜Ｈについて第３の再計算を行い（Ｓ２７）、第３の再計算後、割当処理（Ｓ１００）を呼び出す。
【００７９】
割当処理部１９は、呼び出された割当処理（Ｓ１００）の中で、第２の判定を行い（Ｓ１１）、図１４に示すように、レコードＦ、Ｈが該当する（Ｓ１１：ＹＥＳ）ので、レコードＦ、Ｈについて第２の再計算を行う（Ｓ１３）。
【００８０】
割当処理部１９は、次に、第３の判定を行い（Ｓ２１）、レコードＦ、Ｈが両方該当する（Ｓ２１：ＹＥＳ）ので、レコードＦ、ＨにそれぞれデバイスＩＤ「ｆ」、「ｉ」が残るようにし、レコードＧにデバイスＩＤ「ｆ」が含まれ、レコードＧにデバイスＩＤ「ｉ」が含まれるので、これらを削除し（Ｓ２３）、レコードＦ、Ｈを無効化する（Ｓ２５）。
【００８１】
割当処理部１９は、次に、レコードＧについて第３の再計算を行い（Ｓ２７）、第３の再計算後、割当処理（Ｓ１００）を呼び出す。
【００８２】
割当処理部１９は、呼び出された割当処理（Ｓ１００）の中で、第２の判定を行い（Ｓ１１）、図１５に示すように、レコードＧが該当する（Ｓ１１：ＹＥＳ）ので、レコードＧについて第２の再計算を行う（Ｓ１３）。
【００８３】
割当処理部１９は、次に、第３の判定を行い（Ｓ２１）、レコードＧが該当する（Ｓ２１：ＹＥＳ）ので、レコードＧにデバイスＩＤ「ｇ」のみを残して他のデバイスＩＤを削除し（Ｓ２３）、レコードＧを無効化する（Ｓ２５）。割当処理部１９は、有効なレコードがないので、ステップＳ２７を省略し、割当処理（Ｓ１００）を呼び出す。
【００８４】
割当処理部１９は、呼び出された割当処理（Ｓ１００）の中で、第２の判定を行い（Ｓ１１）、第２の判定（Ｓ１１）で該当のレコードがなく（Ｓ１１：ＮＯ）、かつ、使用要求データベース１８の全レコードが無効（Ｓ７１：ＹＥＳ）なので、処理を終了させる。
【００８５】
図１６は、本実施の形態に係るデバイス割当装置による使用要求へのデバイスの割り当てと従来技術を用いたデバイスの割り当てを比較した図である。
図４の例だと、従来の先着順割当（ＦＩＦＯ）では使用要求Ｃにデバイスを割り当てることができない。
また、従来の優先度基準による割当でも使用要求Ｃにデバイスを割り当てることができない。
また、従来の固定割当では使用要求Ｃ、Ｈにデバイスを割り当てることができない。
【００８６】
しかし、上述のように、デバイス割当装置１によれば、全使用要求にデバイスを割り当てることができる。
【００８７】
以上のように、デバイス割当装置１によれば、割当処理部１９が図５のフローチャートにしたがってデバイスを使用要求に割り当てるので、使用要求に多くのデバイスを割り当てることができる。
【００８８】
すなわち、「候補総数」、「競合候補数」、「優先度」という限られた情報から，他の使用要求よりも遅いタイミングで送出された使用要求、優先度の低い使用要求、合致するデバイスの少ない使用要求などに対して、デバイスを割り当てることが可能となる。これにより、従来手法である、先着順制御・優先度に基づく割当、固定的に設定した要求-応答割当の各手法と比較して、より多くの使用要求に対してデバイスを割り当てることが可能となる。
【００８９】
さらに、M2M デバイスなど、現在状態の確認に時間を要するデバイスに対して送出する状態確認要求を1 回の通信に集約し、当該通信で得られた情報を基に割当処理を行うことが可能となる。これにより、デバイス割当装置−デバイス間のネットワーク負荷低減と複数の外部アプリケーション装置からの使用要求に対するデバイス割当数の最大化を両立することが可能となる。
【００９０】
また、この割当処理は、「使用要求」または「デバイス数」のいずれかのうち、大きい方をn とすると計算オーダO(n)で収束するため、使用要求をデバイスへの状態確認要求送出から応答受信までに設定することで、デバイス発見における許容範囲内の時間で割当処理を完了できると推測される。
【００９１】
本割当処理は、デバイスそのものの割当に留まらず、排他独占的な割当が必要となる有限資源を対象にできることを特徴とする。例えば，デバイス「機能」を対象とする場合には，「デバイスそのもの」ではなく「デバイス機能」単位での割当を行うため、複数の機能を持つデバイスの一機能を割当対象と捉える。具体的な例として、「スピーカ機能」を対象とした割り当てを行う際には、「スピーカそのもの」だけではなく、「ディスプレイ等に複合的に備え付けられたスピーカ機能」も割当対象資源として扱うこととする。
【００９２】
なお、本実施の形態の資源割当装置（デバイス割当装置）としてコンピュータを機能させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。
【符号の説明】
【００９３】
１  デバイス割当装置
１Ａ  デバイス使用可否送信部
２  ゲートウェイ装置
３  外部アプリケーション装置
１１  デバイス使用要求受信部
１２  対象デバイス抽出処理部
１３  デバイス状態確認要求送信判定部
１４  デバイス状態確認要求送信部
１５  外部アプリケーション装置情報保持部
１６  デバイス状態応答受信部
１７  デバイス使用可否判定部
１８  使用要求データベース
１９  割当処理部
２１  デバイス状態確認要求受信部
２２  デバイス現在状態確認処理部
２３  デバイス状態応答送信部
【図１】
2015220707.tif 000003
【図２】
2015220707.tif 000004
【図３】
2015220707.tif 000005
【図４】
2015220707.tif 000006
【図５】
2015220707.tif 000007
【図６】
2015220707.tif 000008
【図７】
2015220707.tif 000009
【図８】
2015220707.tif 000010
【図９】
2015220707.tif 000011
【図１０】
2015220707.tif 000012
【図１１】
2015220707.tif 000013
【図１２】
2015220707.tif 000014
【図１３】
2015220707.tif 000015
【図１４】
2015220707.tif 000016
【図１５】
2015220707.tif 000017
【図１６】
2015220707.tif 000018
【図１７】
2015220707.tif 000019