(57)【要約】方法は、それぞれの要求が確率パラメータ（Ｐ）を含むフィードバック（３）に対する複数の要求を、マルチキャストを受信する受信機に送信することを含む。各端末は対応する確率（４）でこれに応答する（または応答しない）。次に、各要求（５）に対する応答数（ｒ）をカウントし、次に前記カウント及びパラメータから受信機（６）の数の推定値を求め、前記推定値（７）にフィルタをかける。この方法は、前記カウント及びパラメータから受信機の数（９、１０、１１）の上限を予測し、回答数が所定の閾値を超えるリスクが所定値未満に抑えられるように、これから新しい確率パラメータ（１２）を決定することによって、以後のフィードバック要求に含まれる新しい確率パラメータを繰り返し計算することを、さらに含む。
2006518138.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャスト視聴者の規模を追跡調査する方法は、
（ａ）前記マルチキャストを受信する受信機に、それぞれが確率パラメータ（Ｐ）を含む複数の要求を送信し、それにより各端末が対応する確率で応答する、あるいは応答しないことと、
（ｂ）各要求に対する応答数（ｒ）をカウントすることと、
（ｃ）前記カウント及びパラメータから、受信機数の推定値を求めることと、
（ｄ）前記推定値にフィルタをかけることと、
を含み、前記方法は、前記カウント及びパラメータから、前記受信機数の上限を予想し、前記応答数が所定の閾値を超えるリスクが所定値未満に保たれるように新しい確率パラメータをそこから決定することによって、以後のステップ（ａ）において含まれる新しい確率パラメータを繰り返し計算することをさらに含む。
【請求項２】
新しい確率パラメータを計算する前記ステップは、
使用される前記確率パラメータを前提として、観察されるものに等しい応答数を受信する所定の確率に対応する最大視聴者規模を推定することと、
前記推定された最大視聴者規模及び前記最大視聴者規模の少なくとも１つの過去の値を使用して、前記予想を実行することと、
前記予想された最大規模とともに、前記応答数がそれらを受信するために使用可能な容量を超えるリスクが所定のリスク閾値を下回ることを含むであろう、前記新しい確率パラメータ（Ｐ（ｔｉ＋１））を決定することと、
を含む、請求項１に記載の方法。
【請求項３】
前記予想の前に前記推定された最大規模のフィルタにかけられたバージョンを生成することを含む、請求項２に記載の方法。
【請求項４】
前記推定される最大規模の前記フィルタリングはウィナーフィルタによって実行される、請求項３に記載の方法。
【請求項５】
前記推定値の電力スペクトルに依存して、前記推定される最大規模の前記フィルタリングの前記パラメータを適応して調整することを含む、請求項３または請求項４に記載の方法。
【請求項６】
前記予想は前記推定される最大規模の過去の値を外挿することにより実行される、請求項１乃至請求項５のいずれか１項に記載の方法。
【請求項７】
前記推定値の前記フィルタリングはウィナーフィルタにより実行される、請求項１乃至請求項６のいずれか１項に記載の方法。
【請求項８】
前記推定値の過去の値の前記電力スペクトルの関数として、前記推定値の前記フィルタリングの前記パラメータを適応して調整することを含む、請求項１乃至請求項６のいずれか１項に記載の方法。
【請求項９】
前記推定値の前記フィルタリングは、前記推定値を求めることを終えた後に実行される、請求項１乃至請求項８のいずれか１項に記載の方法。
【請求項１０】
前記推定値の前記フィルタリングは、新しい推定値が求められるたびに実行される、請求項１乃至請求項９のいずれか１項に記載の方法。
【請求項１１】
前記同じフィルタパラメータは、前記推定値の前記フィルタリング及び前記最大推定規模の前記フィルタリングのために使用される、請求項５および８に従属するときの請求項１０に記載の方法。
【請求項１２】
要求または応答の損失の前記確率を測定することと、前記第１の推定された規模に訂正を適用することを含む、請求項１から１１のいずれか１項に記載の方法。
【請求項１３】
マルチキャスト視聴者の規模を推定する方法であって、
（ａ）前記マルチキャストを受信する受信機に、それぞれが確率パラメータ（Ｐ）を含む複数の要求を送信し、それにより各端末が対応する確率で応答する、あるいは応答しないことと、
（ｂ）各要求に対する応答数（ｒ）をカウントすることと、
（ｃ）前記カウントから、以後のステップ（ａ）に含まれる新しい確率パラメータを決定することと、
を含む、方法。
【請求項１４】
マルチキャスト視聴者の規模を推定する方法は、
（ａ）前記マルチキャストを受信する受信機に、それぞれが確率パラメータ（Ｐ）を含む複数の要求を送信し、それにより各端末が対応する確率をもって応答する、あるいは応答しないことと、
（ｂ）各要求に対する応答数（ｒ）をカウントすることと、
（ｃ）前記カウント及びパラメータから、前記受信機数の推定値を求めることと、
（ｄ）前記推定値にフィルタをかけることと、
を含み、前記方法は、前記カウント及びパラメータから前記受信機数の上限を予想し、それから新しい確率パラメータを決定することによって、以後のステップ（ａ）に含まれる新しい確率パラメータを繰り返し計算することをさらに含む。
【請求項１５】
マルチキャスト視聴者の規模を推定する方法は、
（ａ）前記マルチキャストを受信する受信機に、それぞれが確率パラメータ（Ｐ）を含む複数の要求を送信し、それによって各端末が対応する確率で応答する、あるいは応答しないことと、
（ｂ）各要求に対する応答数（ｒ）をカウントすることと、
（ｃ）前記カウント及びパラメータから、前記受信機数の推定値を求めることと、
（ｄ）前記推定値にフィルタをかけることと、
を含み、前記推定値の過去の値の電力スペクトルの関数として、前記推定値の前記フィルタリングの前記パラメータを適応して調整することとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は視聴者の規模を測定することに関し、特にマルチキャスト伝送において動的に変化する視聴者の規模を推定することに関する。
【背景技術】
【０００２】
マルチキャストの１つの形式は、データのストリームをある転送先から多くの転送先に効率的に送信できるようにするＩＰ技術である。転送先ごとに別々のユニキャストセッションをセットアップする代わりに、マルチキャストは、異なるマルチキャストグループメンバに対する経路が分岐するルータホップでパケットを複製する。これにより、数千または数百万の受信機に届く一方で、送信側はデータのストリームの単独コピーを送信できる。従来のユニキャスト通信では、送信者は視聴者メンバごとに別々の伝送セッションをセットアップし、サーバログファイルの中の要求されたストリーム数を数えることによって視聴者の規模を追跡調査できる。マルチキャスト通信では、サーバは、受信機ごとに別々のアドレス指定される代わりに単一のマルチキャストアドレスに送信されるデータのただ１つのストリームをセットアップする。次に、そのデータのストリームに関心のあるホストが対応するマルチキャストグループに加わり、そのローカルルータからデータストリームをピックアップする。したがって視聴者の規模は送信者からは見えず、時間内に急速に変化することがあるであろう。
【０００３】
状況は従来のラジオ及びテレビ放送に非常に類似している。つまり、ラジオ局またはテレビ局はイーザー（ether）に番組を送出し、受信者は自分達の受信機を番組が送信されるチャネルに同調することによってお気に入りの番組を聞く、または見ることができる。
【０００４】
マルチキャストグループの規模を追跡調査することは、以下の複数の用途にとっては技術的に重要である。
【０００５】
・マルチキャストは、非常に多数の視聴者へインターネット上で音声ストリーム及びビデオストリームをリアルタイム送達するために使用される。これらの用途から発生する収益は主に広告収入であり、視聴者の規模の推定値及びその時間内の変動に大きく依存している。
【０００６】
・マルチキャストは大規模な発行−登録の用途に使用される。これらの用途では、加入者はトピックまたはイベントのパターンに関する関心を登録し、自分達の関心に一致するイベントを非同期で受信する。トピックに登録することによって、加入者はこのトピック（例えば、特定の企業の株価）に対応するマルチキャストグループのメンバになり、そのトピックが更新されるたびに通知を受信する。発行−登録サーバは、トピックの分割及びマルチキャストグループの間でのトピックの分散を最適化するために、定期的にトピックに対するユーザの関心（トピックごとのリスナー数）を更新できる。
【０００７】
マルチキャスト視聴者規模の測定（及び他の統計）は、ネットワーク層で実行できる。この手法では、メモリテーブルは並列のネットワークルータから捕捉され、監視装置に転送される。監視は、次にマルチキャストグループの規模（及び他の統計）をこれらのテーブルから抽出する（高速ネットワークジャーナル（Ｊｏｕｒｎａｌ  ｏｆ  Ｈｉｇｈ  Ｓｐｅｅｄ  Ｎｅｔｗｏｒｋｓ）、第９巻、２０００年３−４号、Ｋ．Ｓａｒａｃ、Ｋ．Ａｌｍｅｒｏｔｈ「マルチキャスト配備作業を支援すること：マルチキャスト監視のためのツールの調査（Supporting multicast deployment efforts:a survey of tools for multicast monitoring）、及び２０００年１２月、米国テキサス州オースチン、第１１回ＩＩＦＩＰ／ＩＥＥＥ分散システムに関する国際ワークショップ（11th IIFIP/IEEE International Workshop on Distributed Systems（ＤＳＯＭ２００２））の会議録、Ｐ．Ｒａｊｖａｒｉｄａ、Ｋ  Ａｌｍｅｒｏｔｈ及びＫ．Ｃｌａｆｆｙ「マルチキャスト統計を監視、視覚化するためのスケラブルアーキテクチャ（A scalable architecture for monitoring and visualizing multicast statistics）」を参照されたい）。
【０００８】
この手法での３つの問題点とは以下のとおりである。
【０００９】
・監視装置は、ネットワークマルチキャストルータにアクセスを有することを必要とする。多くの状況では実現可能ではない要件である。さらに、監視装置がマルチキャストルータにアクセスできても、現在の規格はこれらのルータがローカル受信機数のカウントを維持することを要求しない。
【００１０】
・それは、マルチキャスト機能がないネットワークの上部でのオーバレイとしてマルチキャスト伝送が構築される、アプリケーションレベルのマルチキャストには適用できない。
【００１１】
・この方法は、（監視装置での情報の集中のため）数十億人の加入者が数百万のマルチキャストグループに登録している前述された発行−登録シナリオにスケーラブルではない。
【００１２】
文献中、大規模マルチキャスト伝送の視聴者規模のリアルタイムエンドツーエンド推定の問題のために、多くの解決策が提案されている。２つの既知の技術とは、静的な視聴者規模を推定するための、Ｌｉｅｕ及びＮｏｎｎｅｎｍａｃｈｅｒにより提案される方法（２０００年３月、イスラエル、テルアビブ、ＩＥＥＥ  ＩＮＦＯＣＯＭ２０００の会議録、第２巻、９５２−９６０ページ、Ｃ．Ｌｉｅｕ及びＪ．Ｎｏｎｎｅｎｍａｃｈｅｒ、（放送視聴者の推定））、及び動的に変化する視聴者を推定するためのＡｌｏｕｆ、Ａｌｔｍａｎ及びＮａｉｎの方法、（Ｓ．Ａｌｏｕｆ、Ｅ．Ａｌｔｍａｎ及びＰ．Ｎａｉｎ、「動的マルチキャストグループの規模の最適オンライン推定（Optimal on-line estimation of the size of a dynamic multicast group）」、ｈｔｔｐ：／／ｗｗｗ−ｓｏｐ．ｉｎｒｉａ．ｆｒ／ｍｉｓｔｒａｌ／ｐｅｒｓｏｎｎｅｌ／Ｓａｒａ．Ａｌｏｕｆ／Ｐｕｂｌｉｃａｔｉｏｎｓ／ｍｕｌｔｉｃａｓｔ．ｐｄｆ；２００２年６月、米国ニューヨーク、ＩＮＦＯＣＯＭ２００２の会議録）である。両方の方法とも送信者により視聴者のグループからフィードバックメッセージを無作為にサンプリングすることに基づいている。この無作為サンプルから、視聴者の規模は統計的な技法を使用して推論される。
【００１３】
Ｌｉｅｕらの方法では、無作為サンプリングは、１９９９年６月、ＩＥＥＥ／ＡＣＭネットワーキングに関する報告書、第７巻、第３号、３７５−３８６ページ、タイマベースの方法（Ｊ．Ｎｏｎｎｅｍａｃｈｅｒ及びＥ．Ｂｉｅｒｓａｃｋ、「大きなグループのためのスケラブルフィードバック（Scalable feedback for large groups）」、及び２００２年６月２１日付けの本出願人らの欧州特許出願第０２２５４３５５．７号、「マルチキャスト通信におけるタイマベースのフィードバック（Timer-based feedback in multicast communication）」、Ｍ．Ｎｅｋｏｖｅｅ及びＳ．Ｏｌａｆｓｓｏｎも参照されたい）を使用して行われる。この方法では、送信者は、フィードバック要求とともにタイマ分散ｆ（ｔ）を全ての受信機に送信する。フィードバックを受信すると、各受信機はバックオフタイマをｆ（ｔ）からサンプリングする。この時間の終了後、受信機は、それが任意の他の受信機からフィードバックメッセージを検出した場合には黙っており、それ以外の場合には、受信機のタイマの終了時刻を含むフィードバックを送信者（及び他の全ての受信機）に送信する。送信者は全てのフィードバックを収集する。フィードバックカウント及び受信機のタイマの終了時刻の組み合わせを使用して、受信機は視聴者規模の統計的な推定値を作成する。Ｍがラウンド数である場合に推定誤差は
【数１】
2006518138.tif 000003
【００１４】
としてのみ減少するため、視聴者推定値において高い精度を達成するために、この手順は多くのラウンドについて繰り返されなければならない。この手法の主要な技術的な問題は以下のとおりである。
【００１５】
・推定手順は静的な視聴者規模にはうまく作用するが、動的に変化する視聴者規模には適切ではない。これは、規模を正確に推定するために、この方法が同じ視聴者からの複数のラウンドのフィードバック収集を必要とするためであり、推定値は、視聴者規模がこれらの収集ラウンドの間に変化するときに不正確になる。
【００１６】
・視聴者からのタイマベースの無作為サンプリングは、各フィードバックメッセージがマルチキャストを介して全ての視聴者に送信されることを必要とする。これらのメッセージを処理するためのオーバヘッドは、サンプル規模（つまり各ラウンドでメッセージを送信する受信機数）が小さく、私たちがただ１つのマルチキャストグループだけを検討しているときには小さい。しかし、受信機が同時に複数のマルチキャストグループにあり、したがってこれら全てのグループからフィードバックメッセージを受信するときには、オーバヘッドは大きくなる可能性がある。
【００１７】
・概して、これらの受信機はフィードバックメッセージを送信する可能性が高いため、サンプリングのためのタイマベースの機構は、送信者に対する最小の往復時間（ＲＴＴ）で受信機に偏っている。この偏りは視聴者規模推定値の精度を削減する。また、平均より大きいＲＴＴを有する受信機は送信者により「聞かれる」可能性がはるかに低いため、それはポーリング機構を不公平にする。
【００１８】
Ａｌｏｕｆ、Ａｌｔｍａｎ及びＮａｉｎの方法は、確率論マルチキャストに基づいた無作為サンプリングのためのさらに簡略な機構を使用することにより、これらの問題のいくつかを取り除く（Ｍ．Ｈ．Ａｍｍａｒ、「確率論マルチキャスト：スケラビリティを改善するためにマルチキャストパラダイムを一般化する（Probabilistic multicast: Generalising the Multicast Paradigm to Improve Scalability）」、１９９４年６月、カナダ、トロント、ＩＥＥＥ  ＩＮＦＯＣＯＭ９４の会議録、８４８−８５５ページを参照されたい）。この方法では、送信者はフィードバックに対する要求を全受信機に送信する。要求を受信すると、各受信機は、指定された確率に従ってフィードバックを送信する、あるいは送信しない。各受信機はメッセージを送信するべきか、あるいは送信するべきでないかを残りから独立して決定するため、サンプリング機構は送信者−受信機及び受信機−受信機ＲＴＴ時間によって影響を受けず、ＲＴＴがより小さい受信機に偏らない。
【００１９】
送信されるメッセージの平均数は、二項式の確率分布関数（ｐｄｆ）を有する無作為な可変数である。ちょうどタイマベースの手法のように、送信者は周知の統計推定技法を使用して、フィードバックカウントから視聴者規模を推定する。
【００２０】
Ａｌｏｕｆ、Ａｌｔｍａｎ及びＮａｉｎの方法は、瞬間推定値の精度を高めるために、連続フィードバックラウンドでの視聴者規模の間の統計的な依存性を利用することにより、動的に変化する視聴者規模の問題の解決策を提供する。これは、（ｉ）視聴者規模の変動が、激しいトラフィックの中のいわゆるＭ／Ｍ／∞待ち行列の人口の変動によって記述されること（ニューヨーク、１９７５年、ジョンウィリーアンドサンズ（Ｊｏｈｎ  Ｗｉｌｅｙ＆Ｓｏｎｓ）第Ｉ巻、Ｌｅｏｎａｒｄ  Ｋｌｅｉｎｒｏｃｋ、待ち行列作成システム（Ｑｕｅｕｅｉｎｇ  Ｓｙｓｔｅｍｓ）を参照されたい）、及び（ｉｉ）フィードバック要求も、フィードバックメッセージも失われないこと、及び（ｉｉｉ）視聴者規模は、フィードバック集中のリスクがないように小さいことを仮定することによって達成される。
【発明の開示】
【００２１】
この手法で技術的に残っている問題は以下のとおりである。
【００２２】
・この方法は、本発明者らが前記に説明したシナリオ（インターネット及びイントラネットテレビ及び無線放送、発行−登録）の典型的な状況である、非常に大きなマルチキャストグループに拡大縮小（ｓｃａｌｅ）しない。これは、肯定応答数が大きくなりすぎる場合に確率をわずかに削減する可能性が言及されるが、応答確率が視聴者の規模とは無関係に選ばれるため、フィードバックメッセージの平均数が、視聴者規模が増加するにつれて大きくなり、最終的にフィードバック集中を生じさせるためである。
【００２３】
・フィルタパラメータは事前に固定される。それらは、人口規模の考えられる変動及びダイナミクスに適応しない。
【００２４】
・アルゴリズムは、フィードバック要求も、フィードバックメッセージもネットワークで失われることがなく、高パケット損失率が経験されることがある本物のネットワークシナリオでは影響を受けやすいと仮定する。
【００２５】
本発明によると、  
マルチキャスト視聴者の規模を追跡調査する方法であって、  
（ａ）マルチキャストを受信する受信機に、それぞれが確率パラメータを含む複数の要求を送信し、それにより各端末が対応する確率で応答する、あるいは応答しないことと、  
（ｂ）各要求に対する応答数を数えることと、  
（ｃ）前記カウント及びパラメータから、受信機数の推定値を求めることと、  
（ｄ）前記推定値にフィルタをかけることと、  
を含み、前記方法は、前記カウント及びパラメータから、前記受信機数の上限を予想し、前記応答数が所定の閾値を超えるリスクが所定値未満に保たれるように新しい確率パラメータをそこから決定することによって、以後のステップ（ａ）において含まれる新しい確率パラメータを繰り返し計算することをさらに含む方法が、提供される。
【００２６】
本発明の他の態様は請求項に定義される。
【００２７】
本発明のいくつかの実施形態は、添付図面に関して説明される。
【発明を実施するための最良の形態】
【００２８】
図１は、（インターネットなどの）ＩＰネットワーク１０２を介して多くの受信端末１０３（その内の３つだけが図示されている）に接続されるサーバ１００を有する、マルチキャスト構成を示す。マルチキャスト動作は従来の方法で動作するため、視聴者規模を測定するためにここで提案される追加の機能性だけが説明される。
【００２９】
本発明者らは、マルチキャストグループにメッセージを送信している送信者（すなわちサーバ１００）を考える。グループメンバ（１０３）はいつでもグループに加わり、グループを離れることができる。例は、マルチキャストがインターネット上でＴＶを放送するために使用されるときである。視聴者は、番組を放送するチャネルに対応するマルチキャストグループに加わることによって特定の番組を見ることができ、番組中いつでもマルチキャストグループを離れることができる。
【００３０】
ここに説明される測定プロセスは以下により実現される。
【００３１】
（ａ）要求メッセージを構築し、マルチキャスト機構を介して定期的に送信するため、（ｂ）端末からの応答を数えるため、及び（ｃ）結果を処理するための、送信者での追加ソフトウェア、及び、このような要求を処理し、適切な場合には応答を作成するための各端末での追加のソフトウェアである。視聴者の規模は、本発明者らがＮ（ｔ）で示す、時間に依存する確率変数である。本発明者らは、送信者が、フィードバックラウンドごとのフィードバックメッセージの最大数ｒｍａｘを処理できると仮定する。目的は、常に（ｒ（ｔ）がｒｍａｘを超えるときに発生する）フィードバック集中のリスクを最小限に抑える一方で、受信機からのフィードバックカウントｒ（ｔ）を通してリアルタイムでＮ（ｔ）（及びおそらく他の受信機属性）を正確に推定することである。
【００３２】
プロセスは、ここで図２に示されるフローチャートを参照して説明される。
【００３３】
１．推定は、最大視聴者規模Ｎｍａｘの初期の推量で開始する。
【００３４】
２．応答確率Ｐの初期値は、次に、Ｎｍａｘを前提として、フィードバック集中のリスクがユーザによって定義されるリスク閾値δを下回る、最大応答確率としてＰを選ぶことにより取得される。フィードバックメッセージ数は二項式の確率分布関数を有するため、規模Ｎｍａｘの人口を前提として、フィードバックメッセージの数がｒｍａｘを超える確率は以下により示され、  
【数２】
2006518138.tif 000004
【００３５】
したがって、Ｐの値の考えられる最大は以下を解くことにより取得できるであろう。
【数３】
2006518138.tif 000005
【００３６】
前記方程式では、Ｂ（Ｎｍａｘ，Ｐ）は二項式の分布であり、Ｉｐは不完全なベータ関数、  
すなわち、  
【数４】
2006518138.tif 000006
【００３７】
を表す。
【００３８】
現在のインプリメンテーションでは、方程式（１）から数値的にＰを見つけるためにニュートン−ラプソン反復方法のバージョンが使用される。
【００３９】
３．いったんＰ（ｔ１）が検出されると、送信者は（Ｐの値を含む）フィードバックに対する要求をマルチキャストする。
【００４０】
４．各受信機は０≦Ｘ≦１の範囲で乱数Ｘを選択し、Ｘ≦Ｐ（ｔ１）の場合にだけフィードバックメッセージを送信する。
【００４１】
５．送信者は合計ｒ個のフィードバックメッセージをこのラウンドから収集する。
【００４２】
６．その結果、視聴者規模は、  
【数５】
2006518138.tif 000007
【００４３】
として推定される。
【００４４】
ここではγは確率論的な推定誤差である。これを計算することは必須ではないが、必要とされる場合、それは  
【数６】
2006518138.tif 000008
【００４５】
に比例する。
【００４６】
（方程式２、及び対応する誤差式は、未知のパラメータＮ（ｔ）で二項式の分布に適用される統計推定理論の周知の最大尤推定方法を使用して引き出された。）
フローチャートに示される２つの分岐が、動作している２つの推定プロセスがある、つまりそれらが代替経路ではないことを示すために、明確にするために描かれることに留意されたい。
【００４７】
７．視聴者規模の推定（方程式（２））は、その大きさがサンプリングされた受信機の規模に反比例する統計的な推定誤差を含んでいる。本発明者らは、リアルタイムで推定誤差を削減し、使用可能な過去のデータを利用するための方法を提供する。図示されるように、これは、各測定の後に測定プロセス中に発生する（代替インプリメンテーションについて以下を参照されたい）。これは、視聴者規模Ｎ（ｔ）の正確な値の上に重畳される時間依存雑音として推定誤差ｎ（ｔ）を考えることにより達成される。測定された視聴者規模  
【数７】
2006518138.tif 000009
【００４８】
の中の信号対雑音比は、次に、視聴者人口の最良の二乗平均推定値を提供するウィナーフィルタで  
【数８】
2006518138.tif 000010
【００４９】
にフィルタをかけることによって最大限にされる。当初、フィルタパラメータは、視聴者規模変動に関する履歴情報、及び検討中の適用（例えば、インターネットテレビ、発行−登録等）に基づいて固定されるが、視聴者規模測定が進行するにつれて、これらのパラメータは、それらが視聴者規模変動の実際のパターンに適応できるように定期的に計算し直される。
【００５０】
時間ｔｉで視聴者規模の改善される推定値は以下から取得される。
【数９】
2006518138.tif 000011
【００５１】
ここでは、  
【数１０】
2006518138.tif 000012
【００５２】
は最適ウィナーフィルタカーネル(Wiener filtering kernel)である。
【００５３】
このカーネルは、信号（Ｎ（ｔ））及び雑音（ｎ（ｔ））が統計的に無相関であり、これらの電力スペクトルＮｐ（ω）及びｎｐ（ω）が、  
【数１１】
2006518138.tif 000013
【数１２】
2006518138.tif 000014
【００５４】
によって近似できると仮定することにより取得され、  
この場合Ｋ、α及びＡは調整可能なパラメータであり、  
【数１３】
2006518138.tif 000015
【００５５】
である。
【００５６】
したがって、これは  
【数１４】
2006518138.tif 000016
【００５７】
の視聴者規模  
【数１５】
2006518138.tif 000017
【００５８】
の電力スペクトル  
【数１６】
2006518138.tif 000018
【００５９】
のモデルを表していることになる。
【００６０】
Ｎｐ（ω）の前記選択は、αを増加することにより、一般的な時間変化する視聴者規模はフィルタパラメータの決定に十分である精度をもってモデル化できる一方、方程式（５）のα→０制限がゆっくりと変化する視聴者規模を正確にモデル化するという事実により動機付けされる。さらに、ｎｐ（ω）に仮定される形は、白色雑音の仮定に対応する。本発明者らのシミュレーション研究は、これが視聴者規模測定における統計的な雑音の妥当な推定値であることを示す。
【００６１】
８．視聴者規模測定のプロセスの間のフィルタパラメータβの適応は以下のように実行される。送信者は、規模Ｍのスライドウィンドウ上で  
【数１７】
2006518138.tif 000019
【００６２】
の過去の値を蓄積する。それは、次に  
【数１８】
2006518138.tif 000020
【００６３】
の過去の値に関して高速フーリエ変換（ＦＦＴ）を実行することによって信号と雑音の電力スペクトルを推定する（データポイントが均等に分布していない場合には、電力スペクトルを評価するためにローム(Lomb)アルゴリズムが使用される）。これらのスペクトルは、次に、パラメータＫ、α及びＡの新しい値を取得するために最小二乗法を使用して方程式（８）によって示されるパラメータ化された形式に適合され、それらからフィルタパラメータβの新しい値が方程式（７）を使用して取得される。
【００６４】
フィルタカーネルｈ（ｔ）が時間内に急激に減衰するため、規模  
【数１９】
2006518138.tif 000021
【００６５】
の間隔の間のみ過去の統計を蓄積することで実際には十分であることに留意されたい。人口が平均率  
【数２０】
2006518138.tif 000022
【００６６】
でサンプリングされると仮定すると、蓄積する必要のある過去の統計の数は、  
【数２１】
2006518138.tif 000023
【００６７】
でなければならない。
【００６８】
前記適応ステップは、必ずしも毎反復時に発生する必要がないことに留意されたい。
【００６９】
９．視聴者の規模を推定することに加え、本発明者らは視聴者規模の上限を動的に推定する方法を提供する。これは以下のように行われる。受信されるフィードバックメッセージの数ｒ（ｔ１）とリスクパラメータεを前提として、ｒ（ｔ１）フィードバックメッセージの中の確率１−εで結果として生じる場合がある考えられる視聴者の最大規模を見つけ出す。ベイズの定理を使用し、二項式の確率分布関数のポアゾン近似を行うと、観察ｒ（ｔｉ）を前提として、特定の値Ｎｍａｘを超える視聴者の規模の条件付き確率が
【数２２】
2006518138.tif 000024
【００７０】
により示され、ここではＰｇが不完全なガンマ関数であることを示すことができる。
【００７１】
この考えられる最大規模から、  
【数２３】
2006518138.tif 000025
【００７２】
が（ニュートン−ラプソン反復のバージョンを使用して）以下を解くことにより得られ、  
【数２４】
2006518138.tif 000026
【００７３】
ここではＰｇは不完全なガンマ関数である。
【００７４】
１０．この推定値  
【数２５】
2006518138.tif 000027
【００７５】
は、次に、以下の方程式（１０）を使用して視聴者規模の上限のフィルタにかけられた推定値  
【数２６】
2006518138.tif 000028
【００７６】
を提供するために、ステップ（７）に説明されるのと同様にフィルタにかけられる。
【数２７】
2006518138.tif 000029
【００７７】
このバージョンでは、使用されるパラメータはステップ７で使用される（８で適応される）パラメータである。
【００７８】
１１．この推定値  
【数２８】
2006518138.tif 000030
【００７９】
は、次に、以下のように次のラウンドでの最大視聴者規模を予想するために使用される。
【数２９】
2006518138.tif 000031
【００８０】
１２．この予想を使用して、サンプリング確率Ｐ（ｔｉ＋１）が方程式（１）から計算され、Ｐ（ｔｉ＋１）を含む新しいフィードバック要求が受信機に送信される。すなわち、前記ステップはステップ（３）から繰り返される。いったん所望される数の測定値が収集されると、この反復はステップ１３で終わる。
【００８１】
いくつかのオプションの変型及び追加のステップがここで説明される。
【００８２】
Ａ．ステップ７でのフィルタリングは、測定が続行中に実行されるとして示され、それは測定プロセスが続行中にフィルタにかけられた結果  
【数３０】
2006518138.tif 000032
【００８３】
が入手できるように、測定値がほぼリアルタイムで必要とされる場合に有利である場合がある。しかしながら、前述されたようにこのフィルタリングをオフラインで実行することは、フィルタが全てのデータにアクセスできるという点で有利である場合がある。このケースでは、フィルタリング７（及び適応８）は、反復終了後に発生する。しかしながら、上限  
【数３１】
2006518138.tif 000033
【００８４】
のステップ１０でのフィルタリングは必ずループ内に残らなければならず、したがって適応もループ内で発生しなければならない。このケースでは、非因果的（ｎｏｎ−ｃａｕｓａｌ）フィルタを使用することが可能になる。これが行われると、フィルタカーネルは、方程式（４）の代わりに  
【数３２】
2006518138.tif 000034
【００８５】
を使用することにより（ｔｉ−ｔｊ）の負の値を収容するために修正されなければならない。
【００８６】
Ｂ．ネットワーク損失に対する推定アルゴリズムのロバスト性(robustness)を強化する
ネットワークに損失が多い場合、フィードバックに対する要求のいくつかが、それらが受信機に到達する前に失われる可能性がある。また、受信機からのフィードバックメッセージのいくつかが送信者に到達しないことが起こることもある。視聴者規模の最大尤推定（方程式２）は、全ての受信機が等しい確率Ｐをもってフィードバックに対する要求に応えるように、ネットワーク内に損失がないという仮定の下で取得される。
【００８７】
この方法は、視聴者規模を推定する際に損失の影響を平均的に考慮に入れるための方法を提供する。
【００８８】
受信機での損失の可能性が（受信機ｊに対し）ｑｊである場合には、この受信機からのフィードバックメッセージが送信者に届く確率は、もはやＰではなく、  
Ｐｊ＝Ｐ（１−ｑｊ）２となるであろう。本発明者らは、以下のように推定手順にこの影響を考慮に入れる。本発明者らは、各受信機が独自の損失確率を測定する（受信機は、例えば、パケットシーケンスを見ることによって自らが属する各マルチキャストグループから到達していないパケット数を数えることによってこれを行うことができる）と仮定する。フィードバック収集中、応答がサンプリングされるそれらの受信機は、この測定値を送信者に送り返す。送信者はこれから平均パケット損失  
【数３３】
2006518138.tif 000035
【００８９】
を推定し、視聴者規模の最大尤推定の中でＰを  
【数３４】
2006518138.tif 000036
【００９０】
で置換することによりこれを考慮する。その結果、視聴者規模の訂正された推定値は、  
【数３５】
2006518138.tif 000037
【００９１】
から取得され、ここでは括弧内の項は、ネットワーク損失から生じる推定された視聴者規模に対する訂正である。この変型は、方程式（２）の代わりに方程式（１３）を使用することによって実現される。
【００９２】
Ｃ．フィードバック集中制限を緩和する
フィードバックの集中は、送信者に同時に届くフィードバックメッセージ数がｒｍａｘを超えるときに発生する。送信者は、集中の可能性が特定の閾値以下となるように応答確率Ｐの値を選ぶことに加えて、それが応答を受信する間隔を引き伸ばすことによって集中の確率をさらに削減できる。これは、パラメータＰとともに第２のパラメータＳを送信することによって達成できる。その結果、フィードバック手順は以下のように修正される。
【００９３】
各受信機は一様な乱数Ｘを選択し、Ｘ＜Ｐの場合にだけフィードバックを送信すると決定する。決定を下した後、受信機は、間隔［０，２Ｓ］内で一様に分布する乱数ｓを選択し、このフィードバックを送信する前に時間ｓの間待機する。このアルゴリズムの最終的な影響は、単位時間あたりで送信されるフィードバックメッセージの平均数が  
【数３６】
2006518138.tif 000038
【００９４】
により与えられ、ｒ＜（１＋Ｓ）ｒｍａｘの場合にフィードバック集中を回避できるように、間隔Ｓで受信機からのフィードバックを拡散することである。したがって、集中制限は、ｒｍａｘの代わりに事実上（１＋Ｓ）ｒｍａｘである。ステップ（２）では、方程式（１）は、次にｒｍａｘの代わりに（１＋Ｓ）ｒｍａｘを挿入することによって、それからＰを計算するために新しい限度が使用されるように修正される。これから計算されるＰの値は、ｒｍａｘを使用して計算される値より大きくなり（本発明者らはガンマ関数の形状からこれを知っている）、したがってさらに多くのフィードバックがラウンドごとに生成され、人口推定の精度は改善される。
【００９５】
前述された方法は、視聴者推定がネットワークルータからの支援なく、非常に大規模なマルチキャストシナリオを考慮に入れて、アプリケーションレベルで実行できる場合に、エンドツーエンド方法に対処する。
【００９６】
それは、受信機からのフィードバックをサンプリングするための適応方法、及び視聴者規模の動的な変動に統計的な誤差のフィルタリングを適応させるための方法を使用することにより、前述された問題点のいくつかを軽減する。
【００９７】
適応サンプリング方法は、フィードバック集中のリスクを最小限に抑えると同時に、送信者が考えられる最大数のフィードバックメッセージを受信することを確実にするのに役立つ。適応フィルタリングは推定値の信号対雑音比を最大限にするために時間内での視聴者の規模変動のパターンに動的に順応する。さらに、本発明者らは、ネットワークにおける大きなパケット損失に対する推定方法、及びランダムタイマを使用して集中制限を緩和するための方法の、ロバスト性を改善するための手順も説明した。
【図面の簡単な説明】
【００９８】
【図１】ネットワークの概略図である。
【図２】本発明の一実施形態の動作を描くフローチャートである。
【図１】
2006518138.tif 000039
【図２】
2006518138.tif 000040
【国際調査報告】
2006518138.tif 000041
2006518138.tif 000042
2006518138.tif 000043
2006518138.tif 000044
2006518138.tif 000045
2006518138.tif 000046