(57)【要約】【課題】利用者にとってホームネットワーク内の活用状況を一目瞭然で知得可能にする。【解決手段】ホームネットワークエージェント１０１は、ダブルチューナテレビ１０６、ファイルサーバ１０４、１０５の内部バス帯域及び／又は記憶容量と、ＬＡＮ１０２のスループットの１以上を資源とし、ダブルチューナテレビ１０６からファイルサーバ１０４、１０５へのＡＶコンテンツの予約録画及びファイルサーバ１０４、１０５間のＡＶコンテンツの転送処理の少なくとも１つの作業をジョブとし、ジョブを、資源を使用するタスクの集合として、タスクに付与された制約条件に適合するように各タスクを配置した近似解を求め、近似解として配置された各タスクの制約条件をジョブに書き込んで予約表を生成して利用者に表示する。【選択図】図１
2009010611.tif 000002
【特許請求の範囲】
【請求項１】
テレビ放送を受信するチューナと、前記チューナにより受信されたテレビ放送のＡＶコンテンツを録画可能な２つ以上の録画装置と、ホームネットワークエージェントとがローカルエリアネットワークを介して接続されたホームネットワークシステムに用いられるホームネットワークエージェントであって、
前記チューナと、前記録画装置の内部バス帯域及び／又は記憶容量と、前記ローカルエリアネットワークのスループットとのうち１つ又は２つ以上を資源とし、前記チューナから前記録画装置への前記ＡＶコンテンツの録画、及び前記２つの録画装置の間の前記ＡＶコンテンツの転送処理の少なくとも１つの作業をジョブとし、このジョブを、前記資源を使用するタスクの集合として、前記タスクに付与された制約条件に適合するように各タスクを配置した近似解を求める手段と、
前記近似解として配置された各タスクの制約条件を前記ジョブに書き込んで予約表を生成する手段と、
前記生成された予約表を蓄積する手段と、
前記蓄積された前記予約表を利用者に提示する手段と、
前記蓄積された前記予約表に基づいて前記資源を協調制御する制御手段と、
を備えたホームネットワークエージェント。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、チューナにより受信されたテレビ放送の番組をローカルエリアネットワーク（ＬＡＮ）を介して録画装置に転送して予約録画するホームネットワークシステムに適用されるホームネットワークエージェントに関する。
【背景技術】
【０００２】
まずホームネットワークを可能とする現在の技術背景について説明する。第１に、映像や音声などの各種情報信号をデジタル化して信号処理する技術がめざましく進歩し、これに伴ってデジタル放送システムが各国で導入された。日本では２００３年１２月より、東京、名古屋、大阪地区において、地上波デジタルテレビ放送が一斉に開始された。デジタルテレビ放送システムは、ＨＤ（ハイディフィニション＝高精細）ＴＶによる高画質放送、データ放送などの付加サービス、多チャンネル放送などの特徴がある。
【０００３】
第２に、デジタル化された映像信号及び音声信号やその他の情報データなどを圧縮処理する技術が急速に開発された。現在、このデータ圧縮処理技術の規格としては、ＩＳＯ（国際標準化機構）／ＩＥＣ（国際電気標準会議）１３８１８［ＩＳＯ／ＩＥＣ ＪＴＣ１／ＳＣに９／ＷＧ１１］で提案されているＭＰＥＧ方式が主流となっている。主に放送では、ＭＰＥＧビデオストリームとＭＰＥＧオーディオストリームを、互いの再生同期がとれるように時間軸方向に多重化したＭＰＥＧ−ＴＳ（トランスポート・ストリーム）が用いられている。なお、ＭＰＥＧ−ＴＳは、ＰＴＳ（プレゼンテーション・タイムスタンプ）と呼ばれるストリーム内の再生時刻情報が含まれたＰＥＳ（パケッタイズド・エレメンタリー・ストリーム）パケットを区切りとして時間軸方向に多重化している。
【０００４】
ＭＰＥＧ−ＴＳの記録再生の構成例として下記の特許文献１に記載されたものが挙げられる。この発明では、パケットを多重化してなるデジタルデータのビットストリームに基づくデジタル放送波を受信するデジタル放送受信端末装置において、所定の番組情報を分離してユーザに提示し、ユーザが選択した受信対象番組（チャンネル）のパケットのみをデコーダに与えて映像化したり、記録再生装置に与えて録画できるようにする技術について開示している。
【０００５】
第３に、近年、デジタルテレビ放送の受信端末装置の機能と、ストリームを保存可能な大容量のＨＤＤ（ハード・ディスク・ドライブ）と、デジタル放送番組の録画予約手段を兼ね備えたＨＤＲ（ハードディスクレコーダ）と呼ばれる商品が販売されるようになった。利用者は、ＥＰＧ（電子番組表）に類する対話型ユーザインタフェースを利用して、録画対象番組（チャンネル）・録画日時を簡単に指定して番組を録画予約することができ、所望の番組を所望の時刻に視聴すること（タイムシフト）が可能となった。
【０００６】
第４に、ＤＬＮＡ（デジタル・リビング・ネットワーク・アライアンス）ガイドラインが公開されている。ＤＬＮＡガイドラインは、ホームネットワークに接続された複数の装置間で、ＭＰＥＧ−ＴＳに類するＡＶコンテンツを、ＬＡＮを介して相互接続して伝送できるようにする共通仕様である。例えば、ＤＭＳ（デジタル・メディア・サーバ）を備えたＨＤＲと、ＤＭＰ（デジタル・メディア・プレイヤ）を備えたテレビ間をＬＡＮで繋ぐことで、ＨＤＲ内に蓄積された所望のコンテンツをテレビで対話的に選択し、再生することが可能となっている。
【０００７】
このようなホームネットワーク環境下では、利用者は、各々の録画再生装置の前で直接対話操作せずとも、ＤＭＰから遠隔的に
（１）ＬＡＮ上の自動検出されたＤＭＳを選択し、
（２）次にコンテンツを選択し、
（３）次にコンテンツの再生操作を行う、
という階層化されたユーザインタフェースが提供される。このため、例えば各装置のリモコンをテレビ（ＤＭＰ）付属のもの１つに統一でき、操作性が向上する。
【０００８】
さらに、装置の設置自由度も向上する。従来、ＨＤＲとテレビ間は、映像・音声ピンケーブル（例えば、黄＝映像・赤＝音声右・白＝音声左に色分けされた３本１対のピンケーブル）に類する接続が一般的で、テレビに備え付けられた入力端子の数によって接続台数の上限があるだけでなく、機器によって入力端子・出力端子が分けられているため、利用者が間違いなく接続することが困難となる場合があった。
【０００９】
ところが、ＤＬＮＡ対応機器同士ではＡＶコンテンツ伝送にＬＡＮを用いるため、入力端子・出力端子の区別はなく、映像と音声でのケーブルの色分けもなく、装置同士は互いを自動認識し、また、台数上限はＬＡＮに許されたＩＰアドレス範囲（一般に用いられるクラスＣサブネットワークで２５４台まで可能）にのみ依存し、さらに有線ハブ装置や無線ＬＡＮ装置などを利用できるので、設置自由度は大幅に向上する。
【特許文献１】特許第３１４６９６９号公報（段落０００１）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、前記のようなホームネットワークには操作性の向上や設置自由度の向上といった利点があるが、一方で
（１）ＬＡＮスループット（期待できる平均伝送帯域）の管理機構がないため必ずしも品質を保てない、
（２）サーバ機能を持つ装置では、何時何分に接続要求が来るかわからないため、常時サーバ機能に通電しておく必要があり、電力をより多く消費する、
（３）再生以外の操作、 具体的には録画予約などは、依然として利用者が各々の装置の前へ行き、対話操作する必要がある、
（４）録画予約を行うべき装置が増えていくと、利用者は装置と予約の対応関係を覚えきれない、
などの様々な問題がある。詳細については後述する。
【００１１】
本発明は、上記の問題点を鑑みてなされたものであり、利用者にとってホームネットワークシステム内の活用状況を一目瞭然で知得することができるホームネットワークエージェントを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は上記目的を達成するために、テレビ放送を受信するチューナと、前記チューナにより受信されたテレビ放送のＡＶコンテンツを録画可能な２つ以上の録画装置と、ホームネットワークエージェントとがローカルエリアネットワークを介して接続されたホームネットワークシステムに用いられるホームネットワークエージェントであって、
前記チューナと、前記録画装置の内部バス帯域及び／又は記憶容量と、前記ローカルエリアネットワークのスループットとのうち１つ又は２つ以上を資源とし、前記チューナから前記録画装置への前記ＡＶコンテンツの録画、及び前記２つの録画装置の間の前記ＡＶコンテンツの転送処理の少なくとも１つの作業をジョブとし、このジョブを、前記資源を使用するタスクの集合として、前記タスクに付与された制約条件に適合するように各タスクを配置した近似解を求める手段と、
前記近似解として配置された各タスクの制約条件を前記ジョブに書き込んで予約表を生成する手段と、
前記生成された予約表を蓄積する手段と、
前記蓄積された前記予約表を利用者に提示する手段と、
前記蓄積された前記予約表に基づいて前記資源を協調制御する制御手段と、
を備えた。
【発明の効果】
【００１３】
本発明によれば、利用者にとってホームネットワークシステム内の活用状況を一目瞭然で知得することができる。
【発明を実施するための最良の形態】
【００１４】
以下、図面を参照して本発明の実施の形態について説明する。
（第１の実施の形態）
本発明の第１の実施の形態に係るホームネットワークエージェントが適用されたホームネットワークシステム（以下、ホームネットワークと記す。）について図１を用いて説明する。ホームネットワーク４０１は、ホームネットワークエージェント１０１と、ＬＡＮ１０２と、ゲートウェイ１０３と、ファイルサーバ１０４、１０５と、ダブルチューナテレビ１０６とＷｅｂブラウザ１０７とを備え、さらにゲートウェイ１０３を介してＷＡＮ（ワイドエリアネットワーク）２０２、ジョブサーバ２０１が接続されている。
【００１５】
ホームネットワークエージェント１０１は、ホームネットワーク４０１内のあらゆるジョブを統括管理するサーバである。ＬＡＮ１０２は、ＩＰ（インターネット・プロトコル）で接続された装置間で通信可能な物理ネットワークである。ゲートウェイ１０３は、ＬＡＮ１０２とＷＡＮ２０２のゲートウェイとなるインターネットブロードバンドルータである。ファイルサーバ１０４、１０５は、ＨＤＤ（ハード・ディスク・ドライブ）を備え、ファイル単位にデータを格納可能な装置である。ダブルチューナテレビ１０６は、デジタルテレビ放送を受信する２つのチューナと液晶表示装置などを備えたテレビである。Ｗｅｂブラウザ１０７は、ＵＲＬ（ユニフォーム・リソース・ローケータ）を入力することで、ＵＲＬが指し示すテキストにアクセスし、テキストを利用者が見やすいようにレンダリングし、利用者に提示する装置であり、例えば携帯情報端末に類する装置である。ジョブサーバ２０１は、ホームネットワークエージェント１０１が所望のジョブテンプレートを検索・取得可能なデータベースシステムである。
【００１６】
（装置の発見・サービスの公告）
ＬＡＮ上の装置の検出や、装置上で動作する複数のデバイス・サービスの存在を他の装置へ知らせるためのサービス公告方式は、複数の方式が存在するが、本発明の実施の形態では、ＵＰｎＰ（ユニバーサル・プラグ・アンド・プレイ）が各装置に組み込まれているとする。ＵＰｎＰ装置Ａ、Ｂ、Ｃ間のプロトコルシーケンスを図２に示す。ＵＰｎＰでは、機器の検出にＳＳＤＰ（シンプル・サービス・ディスカバリ・プロトコル）を用いる。なお、図２に示す丸付き数字は、本明細書では括弧付き数字を用いる。
【００１７】
（１）まず、ＵＰｎＰ装置Ａは、Ｍ−ＳＥＡＲＣＨ要求と呼ばれるＬＡＮ上の各機器（図２ではＵＰｎＰ装置Ｂ、Ｃ）への一斉要求同報を行う。下位プロトコルはマルチキャストＵＤＰ（ユーザ・データグラム・プロトコル）である。
（２）Ｍ−ＳＥＡＲＣＨ要求を受けたＵＰｎＰ装置Ｂ、Ｃは、Locationヘッダを含むＨＴＴＰＵレスポンスをＵＰｎＰ装置Ａへ返答する。下位プロトコルはユニキャストＵＤＰであり、この時点でＵＰｎＰ装置Ａから見て、ＵＰｎＰ装置Ｂ、ＣそれぞれのＩＰアドレス、ＭＡＣアドレスなどのデバイス情報の一部が明らかになる。
（３）ＵＰｎＰ装置Ａは、ＨＴＴＰＵレスポンスをテキスト解析し、Locationヘッダを取り出す。Locationヘッダは各ＵＰｎＰ装置のデバイス情報取得の窓口となり得る内部Ｗｅｂサーバへのアクセスポインタである。図２ではＵＰｎＰ装置Ｂのデバイス情報を取り出すためにＨＴＴＰリクエストを用いる。
（４）ＵＰｎＰ装置Ｂはデバイス情報をＵＰｎＰ装置Ａに返答する。デバイス情報にはサービス記述ＵＲＬが含まれる。
【００１８】
図１中の少なくともゲートウェイ１０３、ファイルサーバ１０４、１０５、ダブルチューナテレビ１０６はＵＰｎＰ装置である。さらに、ホームネットワークエージェント１０１もＵＰｎＰ装置として、他の装置、例えばＷｅｂブラウザ１０７から検出可能にしてもよい。
【００１９】
次にデバイス情報について説明する。図３に、ＵＰｎＰ装置であるダブルチューナテレビ１０６にリクエストすることで得られるデバイス情報の例を示す。デバイス情報には様々な要素があるが、そのうちのいくつかについて説明する。DeviceType要素はデバイス型であり、機器の性質によってベンダーが決める。例えばあるメーカーのテレビのラインナップでは同一のデバイス型が割り振られる。一方で、UDN要素は、完全に機器に一意なデバイスＩＤであり、全世界でただ唯一のＩＤが割り振られる。LOCATION要素はデバイス・サービス情報の取得・制御を行うためのデバイス固有ＵＲＬであり、ここではテレビ内蔵のＷｅｂサーバのトップページであり、ＬＡＮ環境や動作環境によって異なる。ServiceList要素は１つ以上のサービス情報がリスト化されたテキストである。
【００２０】
１つのデバイス情報は図４に示すような１つ又は２つ以上のサービス情報を持つことができる。ServiceType要素はデバイス内の各サービスを識別するためのサービス型である。SCPDURL要素はサービス記述ＵＲＬであり、サービス記述テキスト取得のためのＵＲＬである。ControlURL要素はサービスを制御するためのＵＲＬである。SCPDURL要素またはSCPDURL要素の値が相対ＵＲＬである場合にはデバイス情報のLOCATION要素の値と連接することで正規ＵＲＬとしてもよい。
【００２１】
結果的に、１台のＵＰｎＰ装置のデバイス情報・サービス情報は図５のような階層構造を持つ。ここではダブルチューナテレビ１０６を例にとって説明したが、もちろん他のＵＰｎＰ装置でも同様の情報を備える。また、図３、図４、図５に示す例は、本発明の実施の形態の説明に必要な最小限の情報しか含んでいない。実際にＵＰｎＰ装置から取得できる情報は、これ以上存在することは言うまでもない。
【００２２】
例えば、ファイルサーバ１０４、１０５のデバイス型は
urn:schemas-upnp-org:device:FileServer:1、
サービス型は
urn:schemas-upnp-org:service:FileServer:1
である。図６、図７にそれぞれ、ファイルサーバ１０４のデバイス情報、サービス情報の例を示す。なお、同一のデバイス型を持つ装置がＬＡＮ１０２上に複数ある場合でも、UDN要素とLOCATION要素は少なくとも異なる値を持ち得るから互いの装置を区別できる。例えばファイルサーバ１０５は、ファイルサーバ１０４と比較して、UDN、FriendlyName、LOCATION、MACAddressなどの、装置を特定し得る一部の要素が異なり、それ以外のサービス情報などは同一の情報・機能を持つ。
【００２３】
（サービス記述テキストとアクション）
ＵＰｎＰサーバは、サービス記述ＵＲＬにリクエストした結果得られるサービス記述テキストによって、アクションメソッドの書式を返答する。サービス記述テキストは、ＸＭＬ（イクステンシブル・マークアップ・ランゲージ）によって記述された１つ以上のアクションを含む。ここでいうアクションは、ＲＰＣ（リモート・プロシージャ・コール＝遠隔関数呼び出し）に相当し、ある入力引数を持って、外部の機能を遠隔的に操作し、その結果を出力引数として得るインタフェースである。
【００２４】
ＵＰｎＰクライアントは、サービス記述テキストを解析することで、アクション名やアクションが取り得る入出力引数の型などを知ることができ、アクションメソッドをＵＰｎＰサーバのサービス制御用ＵＲＬに対し、ＨＴＴＰリクエストなどの下位プロトコルを用いて送信することで、ＵＰｎＰサーバ内部の諸機能を制御することができる。
【００２５】
説明のため、図８、図９にファイルサーバ１０４のサービス記述テキストの例を示す。ファイルサーバ１０４は３つのアクションを持つ。アクションＤＩＲは、サーバ１０４内のファイルリスト（引数：FileList）を返すアクションである。アクションＳＥＮＤは、サーバ１０４内のローカルファイル（引数名：sendFile）を別の宛先サーバ（引数名：sendServer）へ送るアクションである。アクションＲＥＣＶは、別のサーバから受信処理を受け付け、ファイルをファイルサイズ分（引数名：recvFileSize）取り込み、ローカルファイル（引数名：recvFile）へ書き込むアクションである。
【００２６】
ここでいうアクションは、あくまでＵＰｎＰ装置間のＲＰＣであって、実際の下位処理がどのようなプログラム・下位プロトコルによって実現されるかは問わない。例えばアクションＲＥＣＶを受け付けたとき、ＦＴＰ（ファイル転送プロトコル）受信サーバをＵＰｎＰ装置内部で起動して、ファイル受信処理を担当させてもよい。また、極短い間隔をあけてアクションを送った場合、装置内の資源の範囲内で複数の処理が並列に動作してもよい。また、自装置の持つ内部状態の変化（例えばタイマの満了）や、通信先の状態の検出（例えば下位プロトコル接続が切断された）などの諸イベントにより、アクションが終了してもよい。
【００２７】
明示的に、並列動作するアクションの開始・終了を外部から指示したい場合は、各アクションにモード引数（例えば引数名:mode）を用意して、「mode="start"の場合はアクションの開始を行う」、「mode="end"の場合はアクションの終了を行う」、としてもよい。同様に、独立した開始アクション（例えばアクションＳＥＮＤ＿ＳＴＡＲＴ）と終了アクション（例えばアクションＳＥＮＤ＿ＳＴＯＰ）を用意してもよい。
【００２８】
（問題点）
ところで、ＵＰｎＰ装置間では、ＬＡＮ１０２上のお互いの存在を発見し、サービスの公告によって内部パラメータや制御方法などを公開し、アクションによってリモート制御が可能となるが、複数のアクションメソッドの依存関係、ＬＡＮスループットなどの競合する資源の割り当てポリシー、リアルタイムのＡＶ伝送ストリーミング制御などはすべて、ＵＰｎＰ装置の実装依存であるため、装置のシームレスな連携という点で問題があった。
【００２９】
問題点の一つ目を例示する。ファイルサーバ１０４は、ＵＰｎＰサーバを実装しているハードウェアの内部バス帯域や現在のＨＤＤ容量といった内部制約により、アクションＳＥＮＤとＲＥＣＶの同時処理数に制限があっても、従来のサービス記述テキストでは表現することができなかった。このため、ファイルサーバ１０４に対して２つ以上のＵＰｎＰクライアントから同時にアクション要求を受け付けた場合、どちらか片方が失敗する可能性があり、かつ、失敗するか否かは実際にアクションを競合させてみないと分からなかった。
【００３０】
問題点の二つ目を例示する。２つのファイルサーバ１０４、１０５間のファイルコピーという、ＬＡＮスループットを共用するジョブがあるとして、別々の利用者が同時期に１つずつファイルコピージョブを、別々のＵＰｎＰクライアントから投入した場合、従来のＵＰｎＰサーバとＵＰｎＰクライアントのベストエフォート型伝送制御を前提とした構造では、競合を検出することは難しい。実際、ＩＰに代表されるベストエフォート型伝送制御は、いくらでも並列に処理できると表現すれば聞こえはいいが、総合的な伝送効率は、１つ１つを最大能力で順番に処理した場合よりも低くなることが多い。２つ以上のジョブを並列に実行するのと、順次実行するのとで、どちらが総所要時間を短縮できるかは状況に依存するため、利用者が事前に競合を察知し、割当調整（ポリシーの策定）ができた方がよい。
【００３１】
（内部制約の表現・公告方式）
本発明の第１の実施の形態の第１のポイントは、前記のような装置の内部制約を、サービス記述テキスト内のアクションに関連付けた形で記述でき、未然に他の装置へ公告できることにある。この内部制約は、資源の概要の記述と、資源を数値とみなした初期値の記述と、資源を消費する関連付けが拡張されたアクションからなる。
【００３２】
内部制約付きサービス記述テキストは、従来通り、任意のＵＰｎＰクライアントから読み出し可能であるから、結果的にＬＡＮ１０２内のすべての装置１０１−１０７の持つ資源とアクションの関連付けを、１台のＵＰｎＰクライアントが収集することが可能となる。
【００３３】
図１０、図１１、図１２は、ファイルサーバ１０４の内部制約付きサービス記述テキストの例である。resourceTable要素は資源概要を示し、以下のような複数のresourceVariable 要素、
（あ）内部バス帯域を意味する
資源名：A_RES_INTBUS_1、
タイプ：セマフォ（排他占有型でアクションが終了すれば返却される資源）
初期値：２
の資源と、
（い）ＨＤＤ容量を意味する
資源名：A_RES_HDDBUF_1、
タイプ：スペース（容量消費型でアクション終了しても返却されない資源）、
初期値：２０
の資源とがあることを示している。また、ＨＤＤ容量の単位系は説明のためＭＢ（メガバイト）とした。
【００３４】
さらに、referenceTable要素は各アクションが消費する資源リストを変数として定義し、以下のような複数のreference要素、
（う）変数：A_RES_BUS_1は、資源A_RES_INTBUS_1を１消費する、
（え）変数：A_RES_BUS_2は、資源A_RES_INTBUS_1を２かつ資源A_RES_HDDBUF_1を引数recvFileSize消費する、
があることを示している。それぞれの消費資源数はinitialValue要素の値であり、プラスの場合は消費を、マイナスの場合は追加を意味する。
【００３５】
さらにaction要素を拡張する形で、relatedResource要素が追加されており、
（お）前記変数A_RES_BUS_1がアクションＳＥＮＤに、
（か）変数A_RES_BUS_2がアクションＲＥＣＶに
関連付けられている。
【００３６】
結果的に、ファイルサーバ１０４のサービス記述テキストにおいて、ＨＤＤ容量を越えるrecvFileSizeを引数に持つアクションＲＥＣＶは処理できない（ＨＤＤ容量A_RES_HDDBUF_1が飽和するため）、かつ、アクションＳＥＮＤは２つ以上同時に処理できない（内部バス帯域A_RES_INTBUS_1が飽和するため）、かつ、アクションＲＥＣＶ処理中は追加のアクションＳＥＮＤ、ＲＥＣＶ共に処理できない（内部バス帯域A_RES_INTBUS_1が飽和するため）、という内部制約が表現できる。以上が内部制約付きサービス記述テキストの例である。
【００３７】
内部制約における、資源名、初期値、単位系などは、最終的に利用者が概要を理解できるものであればよい。例えば、デジタルチューナを２個搭載しているダブルチューナテレビ１０６であれば、内部バス帯域といった漠然とした資源名で表すよりも、「資源名：A_RES_DTUNER_1、初期値：２」とすれば利用者にとって容易に理解できる。
【００３８】
また、ブロードバンドルータに類するゲートウェイ１０３では、ＬＡＮスループットはリニアな数値として測定可能であるが、利用者に分かりやすい形でセマフォ資源とみなしてもよい。例えばゲートウェイ１０３における過去のトラフィックから測定したＬＡＮスループットが２０Ｍｂｐｓであるならば、「資源名：A_RES_LANTHRU_1、初期値：２０、タイプ：セマフォ」の資源とみなしてもよい。なぜならＬＡＮを占有するアプリケーションがあったとしても、利用者から見て十分な時間が経てば、ＬＡＮスループットは返却されるセマフォ資源であるとみなせるからである。また、「１台のテレビ上で画面表示を伴うアプリケーションは同時に１個しか起動できない」といったソフトウェア上の内部制約も同様に、資源として表現できる。この場合は「資源名：A_RES_DISPLAY_1、初期値：１、タイプ：セマフォ」とすれば利用者にとって理解しやすい。
【００３９】
本実施の形態では、内部制約を未然にネットワークを通じて、外部装置に対して公告できることが第一のポイントであって、サービス公告方式が必ずしもＵＰｎＰでなくとも適用できる。また、サービス記述テキストの些細な書式の違いや、サービス記述テキストを送受信する通信プロトコルや、アクションによって起動される下位プロトコルに限定されないことは明らかである。例えば、例ではresourceTable要素をサービス記述テキストに記述したが、同様の情報をデバイス情報に記述することで、装置全体での資源概要を表すこともできる。
【００４０】
（ホームネットワークのペトリネット表現）
次に、本発明の第１の実施の形態に係るホームネットワーク４０１内の資源とアクションの状態遷移について、ペトリネットを用いた図１３、図１４、図１５、図１６を参照して説明する。いずれも図１に示すホームネットワーク４０１中のＵＰｎＰ装置を書き直したものであり、資源配置は初期状態である。ゲートウェイ１０３が図１３、ファイルサーバ１０４が図１４、ファイルサーバ１０５が図１５、ダブルチューナテレビ１０６が図１６に対応する。なお、すべてのＵＰｎＰ装置のサービス記述テキストを図１０〜図１２のようなＸＭＬで記述すると膨大な量になるため、ペトリネット中に適当な資源名とアクション名を付記することで表すことで省略する。
【００４１】
ペトリネットとは二種類の頂点からなる有向２部グラフ構造であり、資源の競合がある状態遷移システムの記述に用いられる。以下にペトリネットの概要を説明する。図中の四角形はトランジッションＴであり、局所的状態に基づく状態遷移規則を表現し、ＵＰｎＰでは１つのアクションの開始または終了に相当する。また、図中の円形はプレースＰ（Ｐin、Ｐout）であり、そこに入るトークンｔ（ｔ1、ｔ２）の数によりシステムの局所的状態を表現し、例えば待ち受け状態、ファイル転送状態、オンエア状態といった状態に相当する。
【００４２】
プレースＰ内に置かれた黒い丸及び菱形はそれぞれトークンｔ１、ｔ２であり、有効な資源の存在に対応した個数を持つ。トランジッションＴは、入力プレースＰin→トランジッションＴの方向の矢印に付加された必要資源数分以上のトークンｔが入力プレースＰに置かれているとき、発火可能（実行可能）となる。トランジッション発火の結果、出力トークンｔを伴うことがあるが、その意味は入力トークンＰinとは全く関係がなく、別の製品や状態値を表すこともある。例を挙げると、ハム１枚とパン２枚を入力トークンｔとし、サンドイッチ工程というトランジッションＴを経て、サンドイッチ１個という出力トークンｔが出てきた場合、入力トークンと出力トークンとでは、数的にも（１＋２→１）意味的にも（ハムとパンとサンドイッチは別物）同一ではないという意味である。
【００４３】
プレースＰとトランジッションＴを接続する矢印は、有向であり、かつ遷移に必要な、必要資源数であるトークン数を持つ。トークン数の表記が省略された場合は、必要資源数は暗黙的に１とみなす。トランジッションＴを実行すると、入力プレースＰinから必要資源数分のトークンｔが消費され、後段の出力プレースＰoutにトークンｔが生成される。黒い丸のトークンｔ１は「タイプ：セマフォ（排他占有型）」であり、トランジッション発火後、所定の出力プレースＰoutを経て、入力プレースＰinへ戻されるループ状の矢印で形成された経路を通る。一方、黒い菱形のトークンｔ２は「タイプ：スペース（容量消費型）」であり、トランジッション発火後、（別のトランジッションＴによって追加されない限り）消費されたまままとなる。ペトリネットは、以上のようなトランジッションＴの発火とトークンｔの配置によって、システムの過渡的な状態遷移を表す。特にペトリネット上のトークンｔの配置状態・様相をマーキングと呼ぶ。
【００４４】
（ペトリネットによる状態遷移の例）
図１７に、ダブルチューナテレビ１０６がアクションＯＮＡＩＲとアクションＳＴＲＥＡＭを同時に開始した直後のマーキングを示す。ここでアクションＯＮＡＩＲは、資源A_RES_DISPLAY_1を１個かつ資源A_RES_DTUNER_1を１個消費し、テレビ画面にデジタル放送のオンエア映像を映すオンエア状態へ移行するアクションである。また、アクションＳＴＲＥＡＭは、資源A_RES_DTUNER_1を１個消費し、引数sendServerで指定されたサーバへ、受信したデジタル放送のＭＰＥＧ−ＴＳストリームを連続した１ファイルとして送信するストリーム送信状態へ移行するアクションである。図１７において、入力プレースＰinにはもはや資源A_RES_DTUNER_1を表すトークンｔは残っておらず、これ以上のアクションを実行できないことが示されている。ここでアクションＯＮＡＩＲを終了すると、資源A_RES_DISPLAY_1が１個、資源A_RES_DTUNER_1が１個、それぞれの入力プレースＰinに返され、再びアクションＯＮＡＩＲ、またはアクションＳＴＲＥＡＭの２個目を開始することができる。
【００４５】
図１８に、ゲートウェイ１０３がreqSpeed＝１６ＭｂｐｓのＬＡＮスループット予約が入った直後のマーキングを示す。ゲートウェイ１０３はアクションＴＲＡＮＳを持ち、アクションＴＲＡＮＳはＬＡＮスループットを管理するアクションである。アクションＴＲＡＮＳを開始すると、引数reqSpeedを必要資源数とみなして入力トークンｔを消費し、転送状態（Ｐout）へ移行し、転送状態（Ｐout）を終了すると、reqSpeed分のトークンｔが入力プレースＰinへ返却される。これは、一般にネットワークＱｏＳ（クォリティ・オブ・サービス）管理と呼ばれるサービスを抽象化したものである。
【００４６】
（ジョブの定義）
ジョブを定義する。ジョブとはタスクの集合である。ジョブ内のタスクには、
（あ）先行順序制約
がある。あるジョブＪnにｍ個のタスクＴ1,…,mが含まれ、各タスクの実行時間をＴＳmとすると、ジョブＪnの最小実行時間はＴＳ1,…,mの総和であり、初回に実行されるタスクはＴ1であり、最後に実行されるタスクはＴmである。
【００４７】
（タスクの定義）
タスクを定義する。タスクとは、ホームネットワークの利用者に対してサービスを提供するにあたって、実行しなければならない作業の最小単位である。ここでは図１９を用いて、デジタル放送のＬＡＮを介した録画作業を取り上げ、録画タスクとみなした場合のタスクを説明する。録画タスクは、
（１）ダブルチューナテレビ１０６からデジタルチューナを1つ借りて、ＭＰＥＧ−ＴＳをアクションＳＴＲＥＡＭで送信開始し（Ｔ１１）、
（２）ゲートウェイ１０３から仮想的なＬＡＮスループットを引数reqSpeedだけ借り（Ｔ１２）、
（３）ファイルサーバ１０４で受け取り、内部バス帯域を２つ借りて、引数recvFileSize分だけＨＤＤ容量を消費するアクションＲＥＣＶを開始する（Ｔ１３）、
という３つのトランジッションＴ１１、Ｔ１２、Ｔ１３が同時発火することに相当する。（１）〜（３）は、それぞれのアクション開始から終了までが、同時かつ並列に動作しなければ意味が無く、開始時刻・終了時刻に多少の揺らぎがあったとしても、これ以上小さな単位に分解できない。ゆえにタスクである。
【００４８】
タスクは、ペトリネットにおいては３つの条件に言い換えられる。一つ目は、
（Ａ）作業を遂行するに当たって実行しなければならない１つ以上のトランジッションの集合である。２つ目は、
（Ｂ）各トランジッションに入力される資源である。３つ目は、
（Ｃ）トランジッションをアクション実行とみなしたときの引数である。（Ａ）〜（Ｃ）が確定すると、タスクを具体的なアクションに変換することができる。
【００４９】
さらに、上記タスクをホームネットワーク４０１内の複数の装置に割り当て、アクションを実行するためには、少なくとも
（い）同一機能のアクションを複数の装置が持っていた場合、実際にタスクを実行する装置の割り当て＝装置割当制約、
（う）アクションを開始する開始時刻＝開始時刻制約、
（え）アクション開始から終了するまでの実行時間＝実行時間制約、
（お）（Ｃ）のアクション引数のうちの未確定引数＝実行時引数制約、
の確定が必要である。
【００５０】
（外部制約の定義）
ジョブとタスクの定義で出現した（あ）〜（お）は、サービス記述テキストから判明している内部制約だけでは解決できない。これらを総合して外部制約と呼ぶ。なお、（お）未確定引数とは、図１９に示す録画タスクの例では、アクション引数のreqSpeedやrecvFileSizeがそれに当たる。
【００５１】
（ジョブテンプレートの定義）
本発明の第１の実施の形態の第２のポイントは、前記のようなジョブと、ジョブに付随する外部制約の一部またすべての形式を含むテキストをジョブテンプレートと定義し、ホームネットワークエージェント１０１が備えるジョブテンプレートＤＢ（データベース）手段４（図２６）に蓄積し、必要があれば外部のジョブサーバ２０１からジョブテンプレートを取得する構造を持つことである。
【００５２】
ジョブテンプレート２０の階層構造を図２０に示す。ジョブテンプレート２０はＸＭＬテキストによる階層構造をとり、ジョブ要素群２１とタスクリスト２２により構成され、タスクリスト２２は複数のタスク２３（タスク１、２〜ｍ）により構成される。各タスク２３はタスク要素群２４と、制約条件テーブル２５とアクションテーブル２６により構成される。制約条件テーブル２５は複数の制約条件２７（制約条件１、２〜ｌ）により構成され、アクションテーブル２６は複数のアクション２８（アクション１、２〜ｋ）により構成される。各アクション２８はアクション要素群２９と引数リスト３０により構成され、引数リスト３０は複数の引数３１（引数１、２〜ｊ）により構成される。
【００５３】
ジョブテンプレート(job)２０の階層構造をＸＭＬタグで記述した例を図２１〜図２３に示す。ジョブテンプレート２０は１つ以上のジョブ要素(job)で表される。ジョブ要素は、ジョブ名(name)、ジョブ機能説明(description)、実行時コスト(cost)、登録ＩＤ（registID）を含む。タスクリスト要素(taskList)は、（あ）先行順序制約を記述したタスク要素(task)の集合である。なお、登録ＩＤ(registID）については図２６に示すスケジューリング手段７にて説明する。ジョブサーバ２０１から取得した時点では登録ＩＤ(registID）は常に空値である。
【００５４】
１つのタスク２３はタスク要素(task)を指し、タスク要素群２４は、タスク名(name)、タスク機能説明(description)、制約条件テーブル(restrictionTable)を含む。制約条件テーブル(restrictionTable)は、（い）〜（お）までの任意の制約条件を、制約条件変数名(name)、制約条件説明(descripton)、データ型(type)、初期値(initialValue)、最大値（maxValue)、最小値(minValue)、確定値(value)、対話入力フラグ(intaract)、で表現した制約条件定義(restriction)を含む。なお、確定値(value)についてはスケジュリング手段７にて説明する。ジョブサーバ２０１から取得した時点では確定値(value)は常に空値である。
【００５５】
制約条件定義(restriction)のデータ型(type)について説明する。制約条件には主に、
（１）あらかじめジョブテンプレート２０に記載された静的なもの（ジョブサーバ２０１が動的に決定した要素も含む）、
（２）利用者に再設定してもらいたいもの（録画開始時刻など）、
（３）ホームネットワークエージェント１０１に動的に選んでもらいたいもの（録画先ファイルサーバの選択など）
の３つの意味がある。
【００５６】
これらを区別し、さらに再設定方法を指定するためにデータ型(type)を定義する。
１．Static＝initialValue要素の値を静的な定数とみなし、そのままvalue要素の値として設定する。
２．Template＝initialValue要素の値を、テンプレート情報（後述）とみなし、所定の文法に従って展開を行い、value要素の値として設定する。
３．Calender＝initialValue要素、value要素の値を日時（ＹＹＹＹ年ＭＭ月ＤＤ日ｈｈ時ｍｍ時ｓｓ秒形式）とみなす。対話入力フラグ(intaract)がYesだった場合は、利用者に日時をminValue値からmaxValue値までの範囲で対話選択させるＧＵＩを提供する。
４．Host＝initialValue要素の値をサービス型(serviceType)とみなし、value要素の値をデバイス固有ＵＲＬ(LOCATION)とみなす。対話入力フラグ(intaract)がYesだった場合は、ホームネットワークエージェント１０１がinitialValue値をサービス型とみなして、それを検索キーとして同サービス型をサービスリスト(ServiceList)に持つ装置をすべて発見し、装置のデバイス情報からデバイス固有ＵＲＬ(LOCATION)を少なくとも取り出し、リスト化し、リストボックスにて利用者に対話選択させるＧＵＩを提供する。
【００５７】
５．File＝initialValue要素の値をサービス型(serviceType)とみなし、value要素の値を（デバイス固有ＵＲＬ＋フルパスファイル名）とみなす。対話入力フラグ(intaract)がYesだった場合、ホームネットワークエージェント１０１がinitialValue値をサービス型とみなして、それを検索キーとして同サービス型をサービスリスト(ServiceList)に持つ装置をすべて発見し、その装置がアクションＤＩＲを持っていた場合、アクションＤＩＲを要求し、各装置の持つファイルリストを取得し、ファイルリストを１つに併合し、利用者にファイルリストから１つのファイルを対話選択させるＧＵＩを提供する。
６．Integer＝initValue,value要素の値を数値とみなす。対話入力フラグ(intaract)がYesだった場合は、利用者にminValue値からmaxValue値までの範囲で対話選択させるＧＵＩを提供する。
７．Span＝initValue,value要素の値を実行時間（秒）とみなす。対話入力フラグ(intaract)がYesだった場合は、利用者にminValue値からmaxValue値までの範囲で、時間：分：秒などの分かりやすい形式に変換しながら対話選択させるＧＵＩを提供する。
【００５８】
制約条件定義(restriction)２７の制約条件変数名(name)について説明する。制約条件変数名には、タスクの開始時刻を表す"start_time"、タスクの実行時間を表す"span_time"があらかじめ定められている。また制約条件変数名同士が重なってはいけない。
【００５９】
アクションテーブル(actionTable)２６は、図１９に示す録画タスクの例で挙げた、同
時発火しなければならないトランジッションＴに対応するアクション(action)２８（アクション１、２〜ｋ）の集合である。各アクション(actino)２８は、該当するサービスのサービス記述テキストのアクションリスト要素群（アクション名(name)や引数リスト(argumentList)）に加えて、アクション２８を実行するサービス型（serviceType)、確定値(value)、対話入力フラグ(intaract)、実行時オフセット(offset)が拡張されている。ここで、実行時オフセット(offset)とは、制約条件変数名"start_time"の確定値(value)をタスク２３の開始時刻とした場合、タスク２３内の各アクション２８を開始時刻からどれだけずらして発火するかを指定するオフセット（単位：秒）である。例えばある処理の開始と終了が別々のアクションだった場合は、終了に相当するアクション２８には、ゼロから"span_time"の確定値(value)以下の範囲で実行時オフセットが設定される。実行時オフセットの値は、後述するテンプレート情報と同様のマクロ展開機能を通して解釈される。
【００６０】
各引数(argument)３１は、該当するサービスのサービス記述テキストの要素群に加えて、未確定引数の解決に用いるテンプレート情報 (template)が拡張されている。なお、 確定値(value)については図２６におけるスケジューリング手段７にて説明する。ジョブサーバ２０１から取得した時点では確定値(value)は常に空値である。
【００６１】
制約条件２７とテンプレート情報(template)の関係について説明する。制約条件変数名は、各タスク２３にて定義されたローカル変数に相当し、
（１）ジョブテンプレート２０で代入済みの定数、
（２）利用者が対話選択した変数、
（３）ホームネットワークエージェント１０１が動的に設定した変数、
のいずれかの段階を経て、値が設定されるものである。テンプレート情報は、マクロ展開機能を持ち、所定の文法に従って、制約条件変数名を値に変換し、指定があれば単純な四則演算や文字列連結を行う。ここでいうマクロ展開機能とは、Ｃ言語ではプリプロセッサ言語機能に相当し、Ｐｅｒｌ言語であればスクリプト評価機能に相当し、ＸＭＬではＸＳＬＴ言語に相当する。
【００６２】
マクロ展開機能は、既に様々な標準が存在する公知技術であるが、ここでは、説明の簡単化のために以下の独自文法を持った単純なマクロ展開機能を定める。
（１）制約条件変数名にマッチした変数名は、所望のタイミングで数値または文字列に展開される。
（２）１文字以上の数値の連続は、１０進数の数値定数とする。
（３）ダブルクォーテーション（”）で囲まれた文字列は文字列定数とする。
（４）２項演算子（＋）の２項目が文字列定数の場合、１項目も文字列定数とみなして、文字列連結を行う。
（５）２項演算子（＋、−、×、÷）の２項目が文字列定数以外の場合、１、２項目を数値とみなして、該当する四則演算を行う。
（６）それ以上展開する演算子、制約条件変数名がない場合に終了し、結果をＸＭＬ文字列に変換して、テンプレート情報と置換する。
【００６３】
動作例を挙げる。変数start_timeが”2006年11月10日 10:23:00”だった場合、テンプレート情報「start_time＋".mpg"」は” 2006年11月10日 10:23:00.mpg”に置換される。また、変数rec_bpsが16、変数span_timeが1800だった場合、テンプレート情報「rec_bps×span_time÷8」は”3600”に置換される。このように、テンプレート情報は、アクション２８内の未確定引数の解決に用いる。
【００６４】
（ジョブテンプレートのスコア）
ジョブサーバ２０１は、多数のジョブテンプレート２０を蓄積するデータベースシステムである。ジョブテンプレート２０によって実現される機能は、ＬＡＮ１０２内の装置の構成によっては複数の実現方法を持つ場合がある。前記の例では、ダブルチューナテレビ１０６から受信したデジタルテレビ放送をストリーミング送信し、ＬＡＮ１０２上の別のファイルサーバ１０４、１０５で録画する「予約録画（ストリーミング）」であったが、例えばファイルサーバとデジタルチューナが混載されているＨＤＲに類する記録再生装置があった場合、ＬＡＮ１０２を介さずにそのまま内蔵ファイルサーバへ録画する「予約録画（ローカルＨＤＤ）」の方がＬＡＮスループットという資源を用いない分、競合問題が少ないと考えられる。ジョブサーバ２０１の運営者は、利用者にとっての実行時コストを、ジョブテンプレート２０の実行時コスト(cost)に数値で記述することで、どちらがより好適であるかの指標を示すことができる。例えば
「予約録画（ローカルＨＤＤ）」実行時コスト＝１、
「予約録画（ストリーミング）」実行時コスト＝２
とすれば、後者の方がコストが高いことが明らかとなる。
【００６５】
（ジョブサーバの構成）
ジョブサーバ２０１のブロック構成を図２４に示す。待ち受け手段３０１は、Ｗｅｂサーバに類する手段であってデバイス情報リストを受け付ける。正当性判定手段３０２は、ブラックリストＤＢ手段３０６からすべての禁止条件を取り出し、禁止条件に該当するデバイス情報を含んでいる場合、そのデバイス情報のみを捨てる。サービス情報テーブル生成手段３０３は、デバイス情報リストを解析し、個々のデバイス情報のサービスリスト(ServiceList)に含まれるサービス型(ServiceType)の値を取り出してテーブル化し、サービス情報テーブルとして出力する。ジョブテンプレート検索手段３０４は、ジョブテンプレートＤＢ手段３０７から、サービス情報テーブルをキーとしてジョブテンプレートの検索を行い、マッチするすべてのジョブテンプレートを出力する。返答手段３０５は、ジョブテンプレートの集合をジョブテンプレートテーブルに加工して出力する。
【００６６】
次に禁止条件を説明する。禁止条件は（要素名、禁止値）のセットであり、要素名はDeviceType、FriendlyName、UDN、MACAddressのいずれかである。例えば
「禁止条件："FriendlyName"、"旧型デジタルテレビ LC-17LC10"」
を定義すれば、デバイス情報リスト内のデバイス情報のFriendlyNameが
”旧型デジタルテレビ LC-17LC10"
であるものを捨てる。正当性判定手段３０２によって、禁止条件に該当する装置はあらかじめホームネットワーク４０１内に存在しなかったものとして扱われる。出荷後に判明したバグなどによって、特定の欠陥製品をホームネットワーク４０１内の制御対象から外すといった用途に用いられる。
【００６７】
次にジョブテンプレート検索手段３０４のマッチ条件を説明する。サービス情報テーブルに含まれるｐ個のサービス型の集合を
｛Ｙ1,Ｙ2,...,Ｙp｝
と表す。また、１つのジョブテンプレートにｋ個含まれるactionList内のaction内のサービス型の集合を
{Ｚ1,Ｚ2,...,Ｚk}
と表し、Ｙnが{Ｚ1,Ｚ2,...,Ｚk}のいずれかにマッチしたとき１を、いずれにもマッチしないときに０を返す関数を
f(n, Ｚ)
とすると、マッチ条件は式１で表される。
【００６８】
【数１】
2009010611.tif 000003
【００６９】
ジョブテンプレートテーブルの例を図２５に示す。ジョブテンプレートテーブルは、条件にマッチした１つ以上のジョブテンプレートを子要素として持つ。ジョブ要素(job)以降の各要素の説明は、図２１〜図２３を見れば明らかであるので省略する。
【００７０】
（ホームネットワークエージェントの構成）
ホームネットワークエージェント１０１の構成を図２６に示す。資源情報取得手段１はＬＡＮ１０２内の１台以上の装置から装置内の資源情報を取得し、資源情報ＤＢ手段２は、この取得した資源情報を蓄積する。ジョブテンプレート取得手段３は、定期的に資源情報ＤＢ手段２を検索してデバイス情報リストを取り出し、デバイス情報リストを検索キーとしてジョブサーバ２０１へ問い合わせ、現在のホームネットワーク４０１内の装置の組み合わせで実行可能なジョブテンプレートテーブルを取得する。ジョブテンプレートＤＢ手段４は、この取得したジョブテンプレートテーブルを蓄積する。
【００７１】
ジョブテンプレート選択ページ生成手段５は、利用者がＷｅｂブラウザ１０７を用いて、ジョブテンプレートテーブルからただ１つのジョブテンプレート２０（図２０）を撰択するためのジョブテンプレート選択ページを生成する。ジョブ登録ページ生成手段６は、ジョブテンプレートページから１つのジョブテンプレート２０が選択された時点で、ジョブテンプレート２０に定義された制約条件変数から、適切な対話入力フォームを伴ったジョブ登録ページを生成する。
【００７２】
スケジューリング手段７は、このジョブ登録ページから、具体的な制約条件変数を含むジョブ登録を受け付けると、ジョブをタスク２３に分割し、資源情報ＤＢ手段２から内部制約を取り出し、ジョブテンプレート２０の対話入力の結果確定した変数群を外部制約とし、両者を総合した制約条件として、競合があれば最適化し、競合がなければ予約表ＤＢ手段８へ登録し、競合が解消できなければジョブ登録を取り消す。予約表ＤＢ手段８は、確定した値を書き込んだジョブを予約情報として管理し、予約表ページ生成手段９は、予約表ＤＢ手段８の内容を予約表ページとして出力する。Ｗｅｂサーバ手段１０は、前記各ページと各ＵＲＬを関連付けリクエストに応答し、制御手段１１は、予約表ＤＢ手段８と現在時刻を常に比較し、実行されるべき予約情報を発見した時点で、予約情報を元に各装置の制御を行う。
【００７３】
詳しく説明すると、資源情報取得手段１はサービス公告方式に対応した処理を行い、ＬＡＮ１０２に接続されたＵＰｎＰ装置ごとに資源情報を繰り返し収集する。資源情報とは、デバイス情報、サービス情報、サービス記述テキストのセットである。取得した資源情報は、資源情報ＤＢ手段２に蓄積される。ジョブテンプレート取得手段３は、ジョブサーバ２０１に対する問い合わせ手段であって、定期的に資源情報ＤＢ手段２を検索し、すべてのデバイス情報を取り出し、デバイス情報リストとしてジョブサーバ２０１に問い合わせを行い、現在のホームネットワーク４０１において実行可能なジョブテンプレートテーブルを取得し、ジョブテンプレートＤＢ手段４へ書き込む。取得したジョブテンプレートテーブルは、検索可能な形でジョブテンプレート２０に分解され、ジョブテンプレートＤＢ手段４に蓄積される。
【００７４】
ジョブテンプレート選択ページ生成手段５は、Ｗｅｂサーバ手段１０がジョブテンプレート選択ページのＵＲＬを指定したリクエストを受け付けると自動的に起動され、ジョブテンプレートテーブルから、ただ１つのジョブテンプレート２０を選択するためのジョブテンプレート選択ページを生成する。ここで生成されるジョブテンプレート選択ページは、Ｗｅｂブラウザ１０７にて所定のレンダリングが可能なテキストである。書式はＸＨＴＭＬ（拡張可能なハイパーテキストマークアップ言語）などのマークアップ言語を用いる。
【００７５】
１つのジョブテンプレート２０を選択するためには、リンクタグとジョブテンプレートごとのジョブ登録ページを指し示すジョブ登録ページＵＲＬで容易に実現できる。例えば、ジョブテンプレート選択ページのＵＲＬが
http://192.168.0.1/jobtemplate/  …（２）
とすると、ジョブ登録ページＵＲＬは、各ジョブテンプレート２０のジョブ要素群のジョブ名(name)を連接し、さらにジョブ登録ページ生成手段６に対応したプログラム名regist.cgiを連接して
http://192.168.0.1/jobtemplate/Recording_Job2/regist.cgi  …（３）
と表せる。この時のリンクタグは同ジョブ機能説明(description)を用いて、
<a href="http://192.168.0.1/jobtemplate/Recording_Job2/">予約録画（ストリーミング）</a>  …（４）
と記述できる。なお、ジョブ登録ページＵＲＬが複数ある場合は、ジョブテンプレート２０の実行時コスト(cost)を用いてソートして出力してもよい。
【００７６】
ジョブ登録ページ生成手段６は、Ｗｅｂサーバ手段１０がジョブテンプレート登録ページのＵＲＬを指定したリクエストを受け付けると自動的に起動され、前記ＵＲＬから該当するジョブテンプレート２０を理解し、ジョブテンプレート２０中の各タスク２３から、制約条件テーブル(restrictionTable)２５で定義された変数群を取り出し、変数をわかりやすい形で列挙した対話入力フォームを含むジョブ登録ページを生成する。対話入力フォームとは、ＸＨＴＭＬにおけるＦＯＲＭ要素に相当し、Ｗｅｂブラウザ１０７を通して各制約条件変数が設定されるよう、プルダウンメニュー、文字列入力フォーム、ラジオボタンなどのＧＵＩ部品にレンダリングしたものである。
【００７７】
Ｗｅｂブラウザ１０７に実装されたＧＵＩ部品は、利用者の対話操作を受け付け、所定の初期値を持ち、最大値から最小値の範囲で数値を選択させたり、あるいは日時といった任意の文字列を入力させることができる。ＧＵＩ部品を表示するか否かは対話入力フラグ(intaract)に依存し、Yesの場合は対話入力フォームを表示し、Noの場合はスケジューリング手段７が自動的に決定するため、単なる概要を表示するために留める。いかなるＧＵＩ部品に対応させるかは、制約条件定義(restriction)のデータ型(type)によって決定
する。例えば
type="Calender"
の場合はカレンダ表示から日時を選ばせたり、文字列入力用のＧＵＩ部品を表示させる。また、
type="Span",type="Integer"
の場合はプルダウンメニュー用のＧＵＩ部品を表示させる。
【００７８】
ＦＯＲＭ要素は、宛先ＵＲＬが関連付けられており、前記ＧＵＩ部品の対話入力フォームにより入力した各値は、変数名と共にＵＲＬパラメータとして連接される。ゆえに、ＨＴＴＰリクエストを用いて、所定の宛先ＵＲＬに、前記ＧＵＩ部品で設定した値を送信することができる。ここでは宛先ＵＲＬを加工して、後段のスケジューリング手段７への登録処理ＵＲＬとする。
【００７９】
例として前述した（３）からレンダリングされたジョブ登録ページのＦＯＲＭエレメントに対して対話設定した、具体的な制約条件を含む登録処理ＵＲＬを以下に示す。
http://192.168.0.1/jobtemplate/Recording_Job2/sched.cgi?start_time=2006年11月10日12:00:00&span_time=3600&rec_bps=16&send_server=  …（５）
ここでは、登録処理ＵＲＬ中のクエスチョン（？）はパラメータの始まりを、アンパサンド（＆）はパラメータの区切りを、各パラメータは（変数名）＝（値）の組とした。またスケジューリング手段７のプログラム名としてsched.cgiが連接されている。上記の登
録処理ＵＲＬは、利用者がスケジューリング手段７に対して、”2006年11月10日の12:00:00から、3600秒分、16Mbpsで録画予約を行いたい”と指示した結果である。一方でsend_serverは空値となっており、後段のスケジューリング手段７で解決することが指示されている。
【００８０】
本発明の第１の実施の形態の第３のポイントは、ジョブテンプレート２０によって各タスク２３に付与された属性である先行順序制約、開始時刻制約、実行時間制約、装置割当制約、のすべてまたはいずれかを制約条件とし、各タスク２３について３変数、つまり開始時刻、実行時間、装置割当のうち少なくとも１つが未確定である場合、近似解最適化アルゴリズムを用いて、未確定変数を解決し、確定値を予約情報に書き込み、予約情報を予約表ＤＢ手段８に登録するスケジューリング手段７を備えることである。
【００８１】
予約情報について説明する。予約情報とは、ジョブテンプレート２０を雛型として、各予約情報間でユニークなＩＤを登録ＩＤ（registID）に記述し、かつタスク２３の制約条件定義に確定値(value)を記述したものである。ここで、ジョブ登録ページ生成手段６から入力される登録処理ＵＲＬをスケジューリング手段７が受け付けたときを考えると、まず、登録処理ＵＲＬを解析し、ジョブテンプレート２０を確定し、ジョブテンプレート２０にパラメータ群を参照して確定値(value)を書き換え、最後にユニークなＩＤを登録ＩＤ(regist)に設定することで、新規予約情報を作成することができる。
【００８２】
スケジューリング手段７は、新規予約情報を含む予約情報群をタスク２３に分解して再配置し、確定値を更新し、再び予約表ＤＢ手段８へ登録するスケジューリングアルゴリズムを持つ。スケジューリング手段７の処理を説明するためのフローチャートを図２７に示す。初期化ステップＳ００１は、まず必要があれば新規予約情報を作成する。次に、スケジュール済みタスク集合Ｓと適合タスク集合Ｑを空値に、サービス記述テキストにて定義した各装置内の（デバイス固有ＵＲＬ＋資源名）を第一添字ａとし、現在日時をゼロとみなした相対時刻ｂを第二添字とする二次元配列ＲＭ（a, b）を作成し（図３０参照）、各値は資源に対応した初期値で埋める。二次元配列ＲＭは各単位時刻ごとの資源残量を意味する。さらに、各予約情報のジョブテンプレート２０をタスク２３に分解し、未配置タスク集合Ｏに登録する。さらに、割当失敗資源名変数ＦＡＩＬを空値に設定する。なお、本実施例で挙げた二次元配列ＲＭは、単純に、現在時刻と、ある日時と、ある装置の資源名を指定したとき、その資源残量を即座に求める方式の１つであって、実装方法などは実施の形態の要点ではない。終了判定ステップＳ００２は、未配置タスク集合Ｏが空値であるときにYesに分岐する。
【００８３】
（絶対配置タスクのスケジューリング）
絶対配置ステップＳ００３は、未配置タスク集合Ｏのうち、１つの絶対配置タスクを抽出し、アクション２８の実行に必要な装置群を決定した上で、二次元配列ＲＭの資源残量を更新して、タスク２３をスケジュール済みタスク集合Ｓへ移動する。絶対配置ステップＳ００３の詳しいフローチャート図２８に示す。絶対配置抽出ステップＳ１０１は、制約条件変数名"start_time", "span_time"のどちらの対話入力フラグ(intract)もYesとなっているタスク２３を１つ選択する。抽出終了判定ステップＳ１０２は、タスクが選択できていない場合にNoとなり正常終了する。サービス型リスト生成ステップＳ１０３は、タスク２３の制約条件定義のうち、データ型＝'Host'のinitValue要素に記載されたサービス型と、アクションテーブル(actionTable)２６に含まれる各アクション２８のうち、対話入力フラグ(intaract)がNoであるアクションのseviceType要素に記載されたサービス型を、それぞれサービス型、確定値(value)要素と、各テキストの確定値(value)要素の相対位置を記憶しながら抽出し、それらを検索セットとして１行とし、サービス型リストを生成する。サービス型リストの例を図２９に示す。
【００８４】
サービス型リスト判定ステップＳ１０４は、サービス型リストが空値になった時点でNoとなり、タスク２３をスケジュール済みタスク集合Ｓへ移動し、正常終了する。装置指定判定ステップＳ１０５は、サービス型リストから検索セットを１行を取り出し、確定値(value)要素にデバイス固有ＵＲＬ(LOCATION)が含まれていた場合はYesへ、それ以外の空値などではNoへ分岐する。装置指定割当ステップＳ１０６は、装置指定判定ステップＳ１０５にて取り出した検索セットの、確定値(value)に記述されたデバイス固有ＵＲＬ(LOCATION)を取り出し、予約情報のactionTable内のtemplateをサーチして関連付けされたアクション２８を検出する。さらにデバイス情報リストに空値に初期化する。これで仮にではあるが、アクション２８と、アクション２８を実行するべき装置が定まる。
【００８５】
デバイス情報リスト生成ステップＳ１０７は、装置指定判定ステップＳ１０５にて取り出した検索セットのサービス型を検索キーとして資源情報ＤＢ手段２を検索し、同サービス型をサービスリスト(ServiceList)に持つすべてのデバイス情報を探し出し、デバイス情報リストを生成する。装置割当ステップＳ１０８は、デバイス情報リストが空値である場合には「返値：No」となりエラー終了する。それ以外では「返値:Yes」となり、デバイス情報リストから１つ装置に当たるデバイス情報を取り出し、さらにデバイス固有ＵＲＬ(LOCATION)を取り出し、タスク２３のアクション(action)２８からアクション名(name)を検出する。これで仮にではあるが、アクション２８と、アクション２８を実行するべき装置が定まる。
【００８６】
資源残量シミュレートステップＳ１０９は、資源残量シミュレータであって、アクション２８とデバイス固有ＵＲＬ(LOCATION)の入力を受け、資源情報ＤＢ手段２から、該当する内部制約付きサービス記述テキストを取得し、内部制約付きサービス記述テキストから、該当するアクション２８が実行された時に消費されるすべての資源名を取り出し、（デバイス固有ＵＲＬ＋資源名）として引数ｘ群に、また、現在時刻と制約条件変数名"start_time", "span_time"の確定値から時間区間を算出し、時間区間を引数ｙ群として、二次元配列ＲＭ（ｘ, ｙ）範囲の各値から、消費されるべき資源数を減算する。消費されるべき資源数は、サービス記述テキスト中のresourceTable要素の各reference要素のrequire要素の値から求められる（require要素の値がプラスの場合は減算、マイナスの場合は加算に反転する）。
【００８７】
ここでは録画タスクによってダブルチューナテレビ１０６内のアクションＳＴＲＥＡＭが呼ばれると仮定した場合の資源残量の変化を図３０に示す。図中では、「ダブルチューナテレビ１０６の資源：A_RES_INTBUS_1」が、アクションＳＴＲＥＡＭの実行によってrequire値＝１だけ減算されている様相が表されている。資源残量シミュレートステップＳ１０９は、シミュレーションの結果、資源残量がマイナスになった場合は「返値:No」となり、即座に処理を中断し、割当失敗資源名変数ＦＡＩＬにマイナスになった資源の（デバイス固有ＵＲＬ＋資源名）をセットし、二次元配列ＲＭをステップＳ１０９の実行前の状態まで復帰し、ステップＳ１０８へ戻る。すべての資源残量が０以上の場合は「返値：Yes」となり、二次元配列ＲＭの状態は減算したままとなる。装置確定ステップＳ１１０は、ステップＳ１０９にて確定したデバイス固有ＵＲＬ(LOCATION)を、ステップＳ１０５にて取り出した検索セットの確定値テキスト位置を参照して、確定値(value)の値として書き込む。
【００８８】
以上が絶対配置ステップＳ００３の詳細である。このような絶対配置ステップＳ００３では、あらかじめ実行したい時間区間が定まっているタスク２３は最優先に時間軸上に配置され、お互いの資源競合を未然に検出することができる。
【００８９】
絶対配置判定ステップＳ００４は、絶対配置ステップＳ００３がエラー終了だった場合はNoへ分岐する。このエラー終了は、絶対配置タスクを時間軸上に配置しようとした場合、同じサービス型を持つすべての装置をチェックしてもなお、必要資源が余っている装置を見つけられなかったことを意味する。前回、スケジューリング手段７がスケジュールした際に正常終了していたとすると、今回エラーになったのは明らかに新規予約情報のせいである。
【００９０】
エラー表示ステップＳ００５では、所定のエラーメッセージをＷｅｂブラウザに返答して登録処理を中止する。また、エラー表示ステップＳ００５は、登録処理ＵＲＬからパラメータ群を取り出し、ジョブ登録ページ生成手段６に引き渡すことで、利用者が以前設定したパラメータを引き継ぎつつ、再度ジョブ登録が行えるように便宜を図ってもよい。例えばエラーメッセージに、下記のようなパラメータ付きジョブ登録ページのＵＲＬ
http://192.168.0.1/jobtemplate/Recording_Job2/regist.cgi?start_time=2006年11月10日12:00:00&span_time=3600&rec_bps=16&send_server=  …（６）
を埋め込んでおけば、利用者は容易にジョブ登録ページを呼び出すことができる。
【００９１】
また、エラー表示ステップＳ００５では、割当失敗資源名変数ＦＡＩＬにセットされている（デバイス固有ＵＲＬ＋資源名）を利用して、エラーメッセージ中に、どの装置において何の資源が不足して失敗したのかを出力してもしてもよい。例えば「http://192.168.0.100:59361/ A_RES_INTBUS_1が不足しています」と出力してもよい。さらにデバイス固有ＵＲＬまたは資源名を検索キーとして資源情報ＤＢ手段２を検索し、該当するデバイスの一般名称(FriendlyName)や、resourceVariable要素のdescription要素の説明に展開し、「デジタルテレビLC-26LC70の内部バス帯域が不足しています」と出力してもよい。
【００９２】
完了表示ステップＳ００６では、所定のスケジュール完了メッセージをＷｅｂブラウザ１０７に返答して登録処理を正常終了する。このとき、スケジュール完了メッセージに、下記の予約表ページのＵＲＬ
http://192.168.0.1/yoyakuhyou.cgi  …（７）
を埋め込んでおけば、利用者は容易に予約表ページを呼び出すことができる。また、今回新たに登録された新規予約情報については、他の予約情報を重ならないユニークな登録ＩＤ（registID）を生成して、registID要素の値を更新する。
【００９３】
近似解最適化ステップＳ００７は、未配置タスク集合Ｏに残ったタスク２３を、二次元配列ＲＭの資源残量がマイナスにならない範囲で、所定の近似解最適化アルゴリズムを用いて時間軸上に配置する。近似解判定ステップＳ００８は、近似解最適化ステップＳ００７がエラー終了だった場合Noへ分岐する。
【００９４】
（ジョブショップ・スケジューリング問題）
近似解最適化ステップＳ００７の数理モデル・アルゴリズムについて説明する。未配置タスク集合Ｏに残ったタスク２３は、開始時刻、実行時間、装置割当、いずれか１つ以上の未確定な変数を含み、タスク２３間には先行順序制約がある。これらのタスク２３は、利用者の利便性を考え、総実行時間が少なくなるように時間軸上に割り当てたい。一般にこのような問題はジョブショップ・スケジューリング問題と呼ばれ、ＮＰ困難で、かつ最適解を見つけにくいことが知られている。
【００９５】
一方で、本実施の形態におけるホームネットワークエージェント１０１では、利用者の操作性を考えると、スケジューリングに使える時間は数秒から長くても数分間しかない。よって、最適解ではなく近似解を求める近似解最適化が必要である。近似解最適化としては、メタヒューリスティクスと呼ばれる一連の近似解法群が良く用いられる。メタヒューリスティクスには、焼きなまし法、タブーサーチ法、遺伝的アルゴリズムなどがあるが、本実施の形態では、説明が最も簡単な遺伝的アルゴリズムを用いて最適化を行う。
【００９６】
（遺伝子の定義）
モデル化のために、未配置タスク集合Ｏに残ったｍ個のタスクＴi(1<=i<=ｍ)を、それぞれの属するジョブを調べて、ｎ個のジョブラベルＪj（1<=j<=ｎ，ｎ≦ｍ）に割り付ける。タスクＴi間には先行順序制約があるため、遺伝的アルゴリズムにおける交叉、突然変異などの操作を行う場合、無作為に入れ替えると先行順序制約が崩れ、個体致死率が大幅に増えてしまい、なかなか収束しなくなってしまう。そこで、ジョブラベルＪjを遺伝子の接頭子として扱えば、例えばＴ1→Ｔ2という先行順序制約があったとしても、両方ともＪ1、Ｊ1というラベルを持つから、入れ替えによる先行順序制約の崩れを少なくできる。個体からジョブラベルＪjを取り出したときに、未配置のタスクＴiを適応的に選択すれば、結果的に先行順序制約を守ったままタスクＴiを入れ替えていることに相当する。
【００９７】
さらに、各タスクＴiの制約条件変数定義を調べて、対話入力フラグ(intaract)がNoで、かつデータ型(type)が"Span"または"Integer"だった変数を揺らぎ変数Ｓとみなす。揺らぎ変数Ｓとは、ある幅で値を適当に変更することで、結果的に良好なタスク配置が得られる可能性のある変数である。しかし、ゆらぎ変数Ｓに、最小値〜最大値間の任意の値を代入して調べることは実行困難であるので、ここでは、ゆらぎ変数Ｓの取り得る値を１６個の代表的なパターンにマッピングする。それぞれを４ビットグレイコード（１増減するとき全体のビットが１しか変化しないように構成した２進数）に対応づけた図を図３１に示す。揺らぎ変数Ｓk（0<=k<=Ｓmax)は、各タスクＴiごとに必要な数が異なるが、ここでは、すべてのタスクＴiの揺らぎ変数Ｓを数えたとき、１つのタスク２３の取り得る揺らぎ変数の最大値をＳmax＝１６とみなす。
【００９８】
本実施の形態における遺伝子型Ｇと染色体型Ｃを図３２に示す。遺伝子型Ｇは固定ビット長（７４ビット）を持ち、１０ビットのジョブラベルＪjと、各々４ビット１６個の揺らぎ変数Ｓ1〜Ｓ16により構成される。染色体型Ｃはタスク数ｍ分だけ遺伝子Ｇ１〜Ｇｍが並んだものである。遺伝子Ｇ１〜Ｇｍは順序型であり、染色体中の左端に近いジョブ（タスク）ほど優先的に配置される。なお、ジョブラベルＪjの個数ｎの最大値は１０２３個（１０ビット表現）とした。
【００９９】
近似解最適化ステップＳ００７の詳しいフローチャートを図３３に示す。初期集団生成ステップＳ２０１は、まず最適化開始時刻Ａsに現在時刻を代入し、現世代集合Ｑと次世代集合Ｒをそれぞれ空値に初期化する。さらに染色体型Ｃを用いて、個体を最大個体数Ｍだけ生成し、現世代集合Ｑに登録する。個体の生成方法は、乱数による霍乱生成とする。霍乱生成の結果、タスク総数ｍは変化しないが、ジョブラベルＪjの並びが乱雑になっている異なる個体が多数生成される。同様にタスクＴi内の揺らぎ変数部分のグレイコードも乱数によって生成する。ｍ＝８、ｎ＝６としたとき、ジョブラベルＪjの並びをリスト表現で表した個体ｐ１、ｐ2の例をそれぞれ（８）（９）にて示す。
ｐ１＝（１  １  ２  ２  ３  ４  ５  ６）  …（８）
ｐ２＝（６  １  ５  １  ２  ３  ２  ４）  …（９）
【０１００】
適合度計算ステップＳ２０２は、現世代集合Ｑ内のすべての個体ｐi(1<=i<=Ｍ)について適合度Ｕi(1<=i<=Ｍ)を計算する。適合度Ｕiは以下の手順で決定される。
（１）各個体ｐiのグレイコードを順次必要数だけ取り出し、それぞれを対話入力フラグNoとなっている制約条件変数に対応させ、グレイコードの意味に従ってminValue,maxValue要素の値を参照しつつ、制約条件変数の確定値(value)要素の値を仮決めする。
【０１０１】
（２）個体ｐiのジョブラベルＪj順に、未配置タスク集合Ｏから該当タスクＴiを取り出し、そのタスクＴiの制約条件変数"start_time"の対話入力フラグ(intaract)がNoである場合は資源残量制約を守りつつなるべく最早時刻から開始できるように時間軸上に配置し、Yesである場合にはその確定値(value)を採用し、時間軸上に配置し、すべてのタスクＴiを配置し終わった時点で、最後に実行されるタスクＴmの終了時刻から最初に実行されるタスクＴ1の開始時刻を引くことで、総所要時間(makespan)（単位：秒）を求める。最も早い時刻にタスクＴiを優先配置し、総所要時間(makespan)の1つを求める整列アルゴリズム については、アクティブスケジューリング法の一つである修正ＧＴ法を用いることができる。各タスクＴiの資源残量制約のシミュレート法については、資源残量シミュレートステップＳ１０９と同様であるので説明を省略する。
【０１０２】
（３）すべてのタスクＴiが完全に資源残量制約を守っていれば、適合度Ｕiは（１０）から求められる。つまり総所要時間が短くなるほど高い適合度が得られる。
適合度Ｕi ＝ ６０４８０００／総所要時間（makespan)  …（１０）
（３）’いずれかのタスクが資源残量制約を守れなければ、適合度Ｕiは常に０となる。
【０１０３】
タイムアウト判定ステップＳ２０３は、（１１）を満たしたときにYesに分岐する。タイムアウト時間ＯＵＴはあらかじめ定められた定数である。
タイムアウト時間ＯＵＴ≧現在時刻−最適化開始時刻Ａs  …（１１）
【０１０４】
予約情報出力ステップＳ２０４は、現世代集合Ｑ内の最大の適合度Ｕiを持つ個体Ｐiを１つ選択し、適合度計算ステップＳ２０２と同様の手順で、タスクＴiを時間軸上に再配置し、確定値(value)要素の値を更新し、全予約情報に未確定な制約条件変数が一つもないように書き換える。
【０１０５】
個体選択ステップＳ２０５は、自然淘汰をアルゴリズム化したものである。個体選択は以下の手順で決定される。ここでは個々の個体Ｐiについて致死フラグＫi（1<=i<= Ｍ)を用いる。
（１）すべての個体Ｐiの致死フラグＫiを０にセットする。
（２）適合度Ｕiがゼロである個体Ｐiの致死フラグＫiに１にセットする。
（３）乱数を用いて、致死フラグＫiが０である個体Ｐiから任意の２個を選択し、適合度Ｕiを比較して、適合度が小さい方に致死フラグＫiに１をセットする。
（４）（３）の操作をトーナメント回数Ｌだけ繰り返す。
（５）現世代集合Ｑ内の致死フラグＫiが１である個体Ｐiをすべて削除する。
【０１０６】
個体上限判定ステップＳ２０６は、次世代集合Ｒ中の個体数ＭＲが、最大個体数Ｍ以上になったらYesへ分岐する。
【０１０７】
個体移動ステップＳ２０７は、現世代集合Ｑを空値に初期化し、次世代集合中Ｒ中の個体を現世代集合Ｑに移動し、次世代集合Ｒを空値に初期化する。確率分岐ステップＳ２０８は、乱数によって
コピー確率Ｙ１：交叉確率Ｙ２：突然変異確率Ｙ３
但し、Ｙ１＋Ｙ２＋Ｙ３＝１
の割合で処理を３分岐する。より具体的には
Ｙ１：Ｙ２：Ｙ３＝０．５：０．４５：０．０５
程度の確率分布である。コピーステップＳ２０９は、現世代集合Ｑから乱数によって１個の個体Ｐiを選別し、 次世代集合Ｒにコピーする。交叉ステップＳ２１０は、現世代集合Ｑから乱数によって２個の親個体を選別し、遺伝的アルゴリズムにおける交叉処理を行い、２個の子個体を次世代集合Ｒへ作成する。ここでは部分写像交叉（Partially-mapped crossover)を用いる。部分写像交叉は 、親の一方から順列の一部を丸々受け継ぎ、その他の部分も可能な限り親の形質（順序）を受け継ぐことを目的とする。これは順序型遺伝子から成る染色体を交叉させる方法として好適である。
【０１０８】
具体例にて交叉ステップのアルゴリズムを示す。ここでは個体をジョブラベルのリストとして注目し、親個体ｐ１、ｐ２を（８）（９）のリスト表現として、まず２つの乱数で選んだ２つの切断点を縦棒（｜）で表し、（１２）（１３）に内挿する。
ｐ１＝（１  １  ２  ｜２  ３  ４｜  ５  ６）  …（１２）
ｐ２＝（６  １  ５  ｜１  ２  ３｜  ２  ４）  …（１３）
子個体ｃ１、ｃ２を考えたとき、子個体ｃ１はｐ２の縦棒で挟まれた部分を受け継ぎ、ｃ２はｃ１の縦棒で挟まれた部分を受け継ぐ。子個体の途中経過を（１４）（１５）に示す。未定部分はアスタリスク（＊）で表すものとする。
ｃ１＝（＊  ＊  ＊  ｜１  ２  ３｜  ＊  ＊）  …（１４）
ｃ２＝（＊  ＊  ＊  ｜２  ３  ４｜  ＊  ＊）  …（１５）
【０１０９】
この交叉は、言い換えれば、ジョブラベル１←→２、２←→３、３←→４の交換規則を定義したと同等であるから、親個体ｐ１の残りのジョブラベルからは個体ｐ２の縦棒で挟まれた部分を取り除き、親個体ｐ１の残りのジョブラベルからは個体ｐ２の縦棒で挟まれた部分を取り除き、残ったジョブラベルを左から順にｃ１、ｃ２の未定部分に埋め込む。完成した子個体ｃ１、ｃ２を（１６）（１７）に示す。
ｃ１＝（１  ２  ４  ｜１  ２  ３｜  ５  ６）  …（１６）
ｃ２＝（６  １  ５  ｜２  ３  ４｜  １  ２）  …（１７）
さらに得られた子個体ｃ１、ｃ２のジョブラベルのリストに従って、遺伝子組み替えを行い、次世代集合Ｒへ２個の子個体を作成する。
【０１１０】
突然変異ステップＳ２１１は、現世代集合Ｑから乱数によって１個の親個体ｐを選別し、遺伝的アルゴリズムにおける突然変異処理を行い、１個の子個体ｃを次世代集合Ｒへコピーする。本実施の形態では、１個体の遺伝子のうちの１つを乱数で選択し、その遺伝子のグレイコード部分（図３２では染色体の下位６４ビット）に対して、グレイコード部分のビット数を十分満たすだけの乱数（図３２では６４ビット）を発生し、グレイコード部分と排他的論理和を行う。この操作により、揺らぎ変数Ｓkの意味が適度に変わったタスクＴiを持つ個体Ｐiが生成される。
【０１１１】
（スケジューリングの利点）
以上が本実施の形態におけるスケジューリング手段７の詳細である。このようなスケジューリング手段７によって実現される利点について図３４を用いて説明する。図３４は、資源がＬＡＮスループットのみに簡単化したホームネットワークにおける３つのタスク（録画タスク１、２、コピータスク２３ａ）のスケジューリングの概念を説明したものである。既に絶対配置タスクとして録画タスク１（時刻t1からt2まで）と録画タスク２（時刻t3からt4まで）が配置されている。そこにファイルサーバ１０１、１０５間でファイルコピーを行うコピータスク２３ａを挿入したい。しかし、総転送量が大きいためt0〜t1間またはt2〜t3間では終わりそうもなく、時刻t4以降に配置せざるを得ない状況である。あるいは、何の帯域制限もなく時刻t0から突っ込むと録画タスク１、２を阻害してしまいそうである。こういった場合、スケジューリング手段７が近似解法による最適化を備えていると、コピータスク’（２３ａ‘）は録画タスク１、２それぞれが要求するＬＡＮスループットを避ける形で、余裕を探し出し、録画タスク１、２を阻害することなく、時刻t0からコピー作業を始められ、総所要時間(makespan)が短縮できる可能性が高い。
【０１１２】
図３４は、ネットワークＱｏＳ管理を模した例であるが、本実施の形態におけるホームネットワークエージェント１０１は、ＬＡＮ帯域管理のみと限定された用途ではなく、他の資源に関しても、分け隔てなく同様に管理できる点が本質的に異なる。新たな資源・新たな装置・新たなジョブが現れたとしても、内部制約・外部制約・ジョブテンプレートを定義することによって、同様に最適解に近い近似解が得られる可能性が高い。
【０１１３】
（予約の表示）
図２６に示す予約表ＤＢ手段８は、予約情報を一時保存するデータベースである。予約表ページ生成手段９は、予約表ページのＵＲＬによって呼び出され、予約表ＤＢ手段８の内容のすべてをＷｅｂブラウザ１０７へ出力する。このとき利用者が読みやすいように表示内容を要約したり、ガントチャートに類するグラフィカルなＧＵＩ表示にレンダリングされるＸＨＴＭＬテキストを伴ってもよい。Ｗｅｂサーバ手段１０は、Ｗｅｂブラウザ１０７からのＨＴＴＰリクエストを待ち受け、リクエストに含まれるＵＲＬに従って、ジョブテンプレート選択ページ生成手段５、ジョブ登録ページ生成手段６、スケジューリング手段７、予約表ページ生成手段９のうち、いずれかを呼び出し、結果を返す。
【０１１４】
（予約の実行）
制御手段１１は、予約表ＤＢ手段００８内の各予約情報中の、開始時刻を表す制約条件変数"start_time"と、現在時刻を常に比較し、実行すべき予約情報を発見したら、予約情報からタスク２３を取り出し、タスク２３に記述されたアクション２８を各ＵＰｎＰ装置に送信して複数のＵＰｎＰ装置の協調制御を行う。
【０１１５】
（ウエイク・オン・ラン）
また、制御手段１１は、予約表ＤＢ手段８内の各予約情報中の、開始時刻を表す制約条件変数"start_time"と、現在時刻と、あらかじめ定められた定数である起動余裕時間Ｗを用いた（１８）が成立したときに、予約情報に関連付けられたすべてのＵＰｎＰ装置に対して、ウエイク・オン・ラン機能におけるマジックパケットを送信してもよい。
（制約条件変数"start_time"−起動余裕時間Ｗ）≧現在時刻  …（１８）
【０１１６】
ウエイク・オン・ラン機能とは、ＬＡＮ経由でリモート装置の遠隔電源制御を行うための業界標準規格であって、既にＬＡＮの物理層を担うイーサネット（登録商標）チップには標準的に搭載されている。イーサネット（登録商標）チップが、マジックパケットと呼ばれる、イーサネット（登録商標）チップ固有のアドレス情報であるＭＡＣアドレスを含む特殊なパケットを受信すると、電源に対して起動パルスを発生する。装置に搭載されている電源が、イーサネット（登録商標）チップのみに電源を供給するスタンバイモードと、装置内のすべてのブロックに電源を供給するフルモードを備えた２モード電源である場合、スタンバイモードにて起動パルスを受信することでフルモードに遷移するように回路を構成すると、超低消費電力での待機が可能となる。ウエイク・オン・ラン待機時のイーサネット（登録商標）チップの消費電力は高々１０ｍＡであるから、超低消費電力によるスタンバイ状態が実現できる。
【０１１７】
（ホームネットワークエージェントによる電力削減の効果）
しかし、従来のＨＤＲ（またはＤＶＤレコーダ）に類する記録再生装置では、例えウエイク・オン・ラン機能に対応していても、各装置内に予約管理機能が内蔵されていたため、その処理のためにリアルタイムクロックやＣＰＵ（中央演算装置）にも数百ｍＡから数Ａの電源を常に供給しなければならず、消費電力が高かった。本実施の形態では、ホームネットワークエージェント１０１が常時起動している必要があるが、その他すべての装置は、必要なジョブの開始時刻付近にくるまでスタンバイモードにしておけるので、ホームネットワーク４０１内の装置が増えれば増えるほど、消費電力削減が期待できる。
【０１１８】
また、ＵＰｎＰクライアントからのリクエストに先立って、起動余裕時間Ｗの余裕を持ってマジックパケットが送られるため、常にＵＰｎＰサーバを動作させておく必要がなくなり、消費電力削減が期待できる。これは各資源情報を事前に収集し、それらの競合を未然に解決するスケジューリング手段７を持つホームネットワークエージェント１０１によって初めて実現される効果である。なぜなら、従来のＵＰｎＰ装置のみで構成されたホームネットワークでは、任意の２装置間が任意のタイミングで資源状態（資源残量）を参照しようとし、それらのタイミング間の統制は全くとれておらず、いつ起きるか予想がつかないので、ＵＰｎＰサーバは常時動作させておいたほうが好適であるし、またウエイク・オン・ラン機能に対応していたとしても、頻繁に電源がフルモードになってしまう可能性が高いからである。
【０１１９】
以上が、本実施の形態におけるホームネットワーク４０１の詳細である。本実施の形態では、ホームネットワーク４０１を構成する各ブロックのうち、すべてまたは一部がコンピュータで実現可能なプログラムとして実現し、あらかじめコンピュータ読み取り可能な記録媒体などに記録して提供しても良い。また、ホームネットワーク４０１内の各ブロック１０１−１０７は、機能説明のために分割したに過ぎず、物理的には柔軟に構成され得る。例えばＷｅｂブラウザ１０７とダブルチューナテレビ１０６を併せ持つＷｅｂブラウザテレビを用意してもよいし、ホームネットワークエージェント１０１を常駐ソフトウェアとして併せ持つインテリジェントゲートウェイを用意してもよい。
【０１２０】
（第２の実施の形態）
本発明の第２の実施の形態に係るホームネットワーク５０１を図３５を用いて説明する。第２の実施の形態は、第１の実施の形態の変形であり、同一番号を持つブロック１０２、１０３、１０４、１０５、１０６、１０７、２０１、２０２については説明を省略する。オンラインショッピングサイト５０３は、検索パラメータ付きＵＲＬをリクエストされると、検索パラメータに応じた関連商品をリストアップした商品お薦めページを生成するＷｅｂサーバである。検索パラメータ付きＵＲＬの例を（１９）に示す。
http://www.jvc-victor.co.jp/recommend.cgi
?FriendlyName=デジタルテレビLC-26LC70&resource= A_RES_INTBUS_1  …（１９）
【０１２１】
（１９）では検索パラメータとしてFriendlyNameに”デジタルテレビLC-26LC70"と、不足資源名として"A_RES_INTBUS_1"が設定されている例である。オンラインショッピングサイト５０３は、検索パラメータを用いて商品データベース（記載なし）を検索し、デジタルテレビLC-26LC70の後継機種である”新型デジタルテレビLC-70MH700"の商品お薦めページを表示する。
【０１２２】
ホームネットワークエージェント５０２の処理を図３６に示す。図２７と同一番号を持つステップＳ００１〜Ｓ００４、Ｓ００６〜Ｓ００８については説明を省略する。推薦リンク付きエラー表示ステップＳ５０５は、図２７のエラー表示ステップＳ００５のすべての機能に加えて、割当失敗資源名変数ＦＡＩＬにセットされている（デバイス固有ＵＲＬ＋資源名）を利用して、デバイス固有ＵＲＬを検索キーとして、資源情報ＤＢ手段２を検索し、該当するデバイスの一般名称(FriendlyName)を取得し、さらにジョブテンプレートから検索用ＵＲＬ（後述する）を抜き出し、（１９）のような検索パラメータ付きＵＲＬを生成し、エラーメッセージに埋め込む。
【０１２３】
本発明の第２の実施の形態に係るジョブテンプレートの拡張部分を図３７に示す。ジョブテンプレートのジョブ要素(job)にlink要素が拡張されている。リンク要素(link)にはリンク属性(href)に
"http://www.jvc-victor.co.jp/recommend.cgi",
関連属性(rel)に
"failure",
が記述されている。推薦リンク付きエラー表示ステップＳ５０５は、このジョブテンプレート内のリンク要素のうち関連属性(rel)が"failure"なものを探し出し、そのリンク属性(href)の値を検索用ＵＲＬとする。
【０１２４】
（商品推薦の効果）
本発明の第２の実施の形態では、ホームネットワークエージェント５０２が遺伝的アルゴリズムに類する近似解最適化を備えているため、利用者自身が試行錯誤するであろう組み合わせ回数を遥かに超えた資源最適化が行われる。それでもなお、タスク処理が不可能だった場合のみ、推薦リンク付きエラー表示ステップＳ５０５が呼び出される。つまり、このエラーが出た瞬間は、利用者の中で「どうやっても無理なのだから、諦めて買い足そう。」という意志が高まっている状態である可能性が高い。既に、アマゾンブックストア（http://www.amazon.co.jp/)に代表されるオンラインショッピングサイトでは、自前の商品検索エンジンを持ち、利用者が探している商品を即座にリストアップする機能（オンラインショッピングサイト５０３の機能に相当する）が標準的に備わっているから、ホームネットワークエージェント５０２がエラーメッセージに、検索パラメータを持った推薦リンクを提示するだけで、極めて効果の高い商品お薦め手段になり得る。
【０１２５】
一方で、複数台の録画再生装置を利用者が手動管理している場合や、装置Ａが録画不能だから装置Ｂを用いるといった単純なアルゴリズムのみを備えた記録再生装置の場合では、利用者が「まだ別の解決方法が残っているかもしれない。」という淡い期待を抱いてしまうため、エラーメッセージに推薦リンクを提示しても、本実施例ほど効果的でないことは明らかである。
【０１２６】
以上のように、本発明によれば、以下の効果がある。
（１）利用者は、新たな装置を買い足してホームネットワークに接続したとしても、常に一つのまとまったサービスに見え、個別の装置に対して対話操作を行う手間から開放される。例えば記録再生装置の録画予約操作は、常にホームネットワークエージェントのみに行えばよく、どの記録再生装置に予約をしたかを覚えている必要もなく、また記録再生装置を買い足し、あるいは買い換えたとしても、そのたびに予約の重複や予約の移行に煩わされることがない。
【０１２７】
（２）利用者は、録画予約表のページによってホームネットワーク内の各装置の活用状況が一目瞭然であり、将来のホームネットワークの増強計画を考えるのに好適である。例えばチューナの利用率が非常に高ければ、チューナのみを買い足せばよいことが簡単にわかる。また、利用者が利用率の高い時間帯を避けて、処理を予約することが可能となる。
（３）家庭内に利用者が複数人いた場合であっても、録画予約表のページによって、異なる利用者が別個の記録再生装置に対して、同一デジタル放送番組を録画予約するといった不合理な予約操作から逃れられるため、録画予約全体の最適化ができ、記録装置の容量を有効活用できる。
【０１２８】
（４）すべての予約処理をホームネットワークエージェントが行うため、各装置は録画予約処理の実行に必要な手段、例えば録画予約の自動実行を可能にするタイマ手段や、利用者に対話的な録画予約作業を提供するＧＵＩ（グラフィカル・ユーザ・インタフェース）手段を省略することができ、開発コスト・テスト工数の削減ができる。
【０１２９】
（５）すべての録画予約処理をホームネットワークエージェントが行うため、ホームネットワーク内の各装置はサーバ手段を常に動かしておく必要がない。例えば、ホームネットワークエージェントと各装置がウエイク・オン・ラン機能をサポートしていれば、ホームネットワークエージェントが各装置の電源管理を代替することができるので、各装置をウエイク・オン・ラン待機モードに移行させておく機会が増えるため、トータルでは待機電力の削減ができる。
【０１３０】
（６）従来は、１台の装置内部に隠されていた内部制約を１つのホームネットワークエージェントが収集し、スケジューリングに役立てられるため、操作（アクション）の競合が実際に起きなければわからなかった不具合が未然に明らかになり、装置の利用率が向上する。
【０１３１】
（７）近似解が求められなかった場合、不足している資源に関連付けられたお薦め商品を、オンラインショッピングサイトの検索機能を用いて利用者に提示することにより、ジョブサーバの運営者は、オンラインショッピングサイトと連携することで、利用者の購買意欲に直結した商品お薦めが可能となる。
（８）ジョブサーバの運営者は、ホームネットワークエージェントから送られてくるデバイス情報リストによって、装置製造者側が予期しない装置の組み合わせでジョブが実行される危険性を未然に排除できる。例えば、他社によって粗悪な装置が販売された場合であっても、ジョブテンプレートを提供しないことで利用を抑止できる。
【図面の簡単な説明】
【０１３２】
【図１】本発明の第１の実施の形態に係るホームネットワークを示すブロック構成図である。
【図２】一般的なＵＰｎＰ装置間のプロトコルシーケンスを示す説明図である。
【図３】本発明の第１の実施の形態に係るダブルチューナテレビのデバイス情報の例を示す説明図である。
【図４】本発明の第１の実施の形態に係るダブルチューナテレビのサービス情報の例を示す説明図である。
【図５】一般的なＵＰｎＰ装置の持つデバイス情報とサービス情報の階層構造を示す説明図である。
【図６】本発明の第１の実施の形態に係るファイルサーバのデバイス情報の例を示す説明図である。
【図７】本発明の第１の実施の形態に係るファイルサーバのサービス情報の例を示す説明図である。
【図８】本発明の第１の実施の形態に係るファイルサーバのサービス記述テキストの例を示す説明図である。
【図９】本発明の第１の実施の形態に係るファイルサーバのサービス記述テキストの例を示す説明図である。
【図１０】本発明の第１の実施の形態に係るファイルサーバの内部制約付きサービス記述テキストの例を示す説明図である。
【図１１】本発明の第１の実施の形態に係るファイルサーバの内部制約付きサービス記述テキストの例を示す説明図である。
【図１２】本発明の第１の実施の形態に係るファイルサーバの内部制約付きサービス記述テキストの例を示す説明図である。
【図１３】本発明の第１の実施の形態に係るゲートウェイのペトリネットを示す説明図である。
【図１４】本発明の第１の実施の形態に係るファイルサーバのペトリネットを示す説明図である。
【図１５】本発明の第１の実施の形態に係るファイルサーバのペトリネットを示す説明図である。
【図１６】本発明の第１の実施の形態に係るダブルチューナテレビのペトリネットを示す説明図である。
【図１７】本発明の第１の実施の形態に係るダブルチューナテレビのアクションＯＮＡＩＲとアクションＳＴＲＥＡＭが発火した直後のマーキングを示したペトリネットを示す説明図である。
【図１８】本発明の第１の実施の形態に係るゲートウェイのアクションＴＲＡＮＳが発火した直後のマーキングを示したペトリネット図である。
【図１９】本発明の第１の実施の形態に係るゲートウェイ、ダブルチューナテレビ、ファイルサーバが協調動作した録画タスクのマーキングを示すペトリネットに説明を加えた図である。
【図２０】本発明の第１の実施の形態に係るジョブテンプレートの階層構造を示す説明図である。
【図２１】本発明の第１の実施の形態に係るジョブテンプレートの例を示す説明図である。
【図２２】本発明の第１の実施の形態に係るジョブテンプレートの例を示す説明図である。
【図２３】本発明の第１の実施の形態に係るジョブテンプレートの例を示す説明図である。
【図２４】本発明の第１の実施の形態に係るジョブサーバを示すブロック構成図である。
【図２５】本発明の第１の実施の形態に係るジョブテンプレートテーブルの例を示す説明図である。
【図２６】本発明の第１の実施の形態に係るホームネットワークエージェントを示すブロック構成図である。
【図２７】図２６のスケジュリング手段の処理を説明するためのフローチャートである。
【図２８】図２７の絶対配置ステップを詳しく示すフローチャートである。
【図２９】図２７の絶対配置ステップにおけるサービス型リストの例を示す説明図である。
【図３０】図２８の資源残量シミュレートステップにおける資源残量の変化の例を示す説明図である。
【図３１】図２７の近似解最適化ステップにおける各遺伝子型内部の揺らぎ変数を４ビットグレイコードで示す説明図である。
【図３２】図２７の近似解最適化ステップが用いる遺伝子型・染色体型を示す説明図である。
【図３３】図２７の近似解最適化ステップを詳しく示すフローチャートである。
【図３４】図２６のスケジュリング手段の行うスケジュリングを示す説明図である。
【図３５】本発明の第２の実施の形態に係るホームネットワークを示すブロック構成図である。
【図３６】本発明の第２の実施の形態に係るホームネットワークエージェントの処理を説明するためのフローチャートである。
【図３７】本発明の第２の実施の形態に係るジョブテンプレートの拡張部分を示す説明図である。
【符号の説明】
【０１３３】
１  資源情報取得手段
２  資源情報ＤＢ手段
３  ジョブテンプレート取得手段
４  ジョブテンプレートＤＢ手段
５  ジョブテンプレート選択ページ生成手段
６  ジョブ登録ページ生成手段
７  スケジューリング手段
８  予約表ＤＢ手段
９  予約表ページ生成手段
１０  Ｗｅｂサーバ手段
１１  制御手段
１０１  ホームネットワークエージェント
１０２  ＬＡＮ
１０３  ゲートウェイ
１０４  ファイルサーバ
１０５  ファイルサーバ
１０６  ダブルチューナテレビ
１０７  Ｗｅｂブラウザ
２０１  ジョブサーバ
２０２  ＷＡＮ
３０１  待ち受け手段
３０２  正当性判定手段
３０３  サービス情報テーブル生成手段
３０４  ジョブテンプレート検索手段
３０５  返答手段
３０６  ブラックリストＤＢ手段
３０７  ジョブテンプレートＤＢ手段
４０１  ホームネットワーク
【図１】
2009010611.tif 000004
【図２】
2009010611.tif 000005
【図３】
2009010611.tif 000006
【図４】
2009010611.tif 000007
【図５】
2009010611.tif 000008
【図６】
2009010611.tif 000009
【図７】
2009010611.tif 000010
【図８】
2009010611.tif 000011
【図９】
2009010611.tif 000012
【図１０】
2009010611.tif 000013
【図１１】
2009010611.tif 000014
【図１２】
2009010611.tif 000015
【図１３】
2009010611.tif 000016
【図１４】
2009010611.tif 000017
【図１５】
2009010611.tif 000018
【図１６】
2009010611.tif 000019
【図１７】
2009010611.tif 000020
【図１８】
2009010611.tif 000021
【図１９】
2009010611.tif 000022
【図２０】
2009010611.tif 000023
【図２１】
2009010611.tif 000024
【図２２】
2009010611.tif 000025
【図２３】
2009010611.tif 000026
【図２４】
2009010611.tif 000027
【図２５】
2009010611.tif 000028
【図２６】
2009010611.tif 000029
【図２７】
2009010611.tif 000030
【図２８】
2009010611.tif 000031
【図２９】
2009010611.tif 000032
【図３０】
2009010611.tif 000033
【図３１】
2009010611.tif 000034
【図３２】
2009010611.tif 000035
【図３３】
2009010611.tif 000036
【図３４】
2009010611.tif 000037
【図３５】
2009010611.tif 000038
【図３６】
2009010611.tif 000039
【図３７】
2009010611.tif 000040