カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装

全文

(1)情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008) and an implementation and an experimentation of its prototype.. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装石塚. 宏. 紀†1. 戸辺. 義. 人†2,†3. 1. はじめに近年，数多くのカメラセンサが，駅構内や公園などの公共施設，オフィスビルや集合住宅などの管理区域に配備され，利活用領域を広げている．具体的には，日常生活の安心・安全. 近年，我々の生活空間に多くのカメラセンサが急速に配備されてきている．カメラセンサは，その撮影されたデータが持つ情報量の多さと多様性からさまざまなサービスに応用されている．また，センサネットワーク技術の発展により，実世界に配備されたカメラセンサは，カメラセンサネットワークを形成し，自律分散的に管理することも可能となってきている．カメラセンサネットワークにおいて，撮影されたデータは，撮影位置と方角に大きく依存する．我々は，カメラセンサによって撮影された位置に着目した経路制御手法として SenriGan を提案する．既存の地理位置情報を利用した経路制御において，クエリの宛先は，センサノードの位置やエリアである必要があった．しかしながら，カメラセンサのように明確なセンシングの方向性と広範囲なセンシングエリアを有するセンサに対して，センシングエリア内の位置に対する経路制御が不可能な既存の地理位置情報を利用した経路制御は適していない．我々の提案する SenriGan は，利用者にカメラセンサの位置を指定させるのではなく，カメラセンサ撮影範囲内のある点とその点を撮影した方角を指定させることで，カメラセンサネットワーク内からユーザの求める映像を撮影するカメラセンサを探し出すことが可能である．本論文において，我々は，SenriGan の設計を解説し，システム実装と評価について述べる．. A Sensed-point-oriented Geographic Routing for Camera Sensor Networks Hiroki Ishizuka†1 and Yoshito Tobe†2,†3 In sensor networks, geographic routing has been paid much attention since sensed data pertain to the location of the data. In conventional geographic routing, the destination of a query mostly should be the location of a node. However, this is not suitable for sensors that cover a wide or directed sensing area such as cameras. To cope with this problem, we propose a modified geographic routing scheme called SenriGan. SenriGan accommodates specifying a sensed point as a destination instead of using a location of a node. In this paper, we describe our proposed system architecture using image sensor networks. 1907. 支援や公共道路の監視，詳細な気象観測，災害現場での人命救助などに利用されている．こうしたカメラセンサから得られうる情報をサーバなどを介して，集中管理するのではなく，分散的にオープンなシステムとして管理することにより，さらに利活用の拡大が期待できる．そこで，我々は，アドホックネットワーク技術を利用して，実世界に配備されたカメラセンサで撮影された利用価値の高い映像を有効活用するために，カメラセンサから得られた映像を共有できる共通カメラセンサネットワーク基盤の構築を目指す．我々の共通カメラセンサネットワーク基盤を利用することで，その利用者は，複数のカメラセンサから多方面で広範囲な映像を得ることができるため，現在提供されているカメラセンサを利用したアプリケーションの機能向上や，新たなユビキタスアプリケーションの開発を支援できる．共通カメラセンサネットワーク基盤の利用者は，必要とするオブジェクトやある地点を撮影するカメラセンサを検索する際に，センサネットワークに対して位置情報をともなったカメラセンサ検索クエリを発行することとする．位置情報を利用してネットワーク内から当該カメラセンサを検索する手法として，地理位置情報を利用した経路処理技術1) がある．地理位置情報を利用した経路制御とは，ネットワーク内の各ノードをユークリッド座標上で表現し，ユークリッド空間座標のみを用いてノード間の経路制御を行う．我々の共通カメラセンサネットワーク基盤も，地理位置情報を利用した経路制御技術を活用してカメラセンサ検索クエリの転送を実現する． †1 東京電機大学大学院工学研究科情報メディア専攻 Department of Information Systems and Multimedia Design, Graduate School of Engineering, Tokyo Denki University †2 東京電機大学未来科学部情報メディア学科 Department of Information Systems and Multimedia Design, School of Science and Technology for Future Life, Tokyo Denki University †3 独立行政法人科学技術振興機構，CREST CREST, JST. c 2008 Information Processing Society of Japan .

(2) 1908. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. 既存の地理位置情報を利用した経路制御プロトコルは，クエリの宛先として，ノードの位. ている．それらのカメラセンサをできる限り多く発見するために，最小閉領域を中心に外側. 置やクエリ転送エリアを指定する必要がある．しかしながら，カメラセンサネットワークに. へクエリパケットを Flooding する SenriGan/s を設計する．SenriGan/s は，Flooding. おいて，利用者はカメラセンサの位置ではなく，カメラセンサが撮影しているエリア内のあ. を用いるため，クエリパケットは無限に転送される．クエリパケットの氾濫は，指定した位. る位置をクエリの宛先として指定する．そのため，既存の地理位置情報を利用した経路制御. 置を撮影するカメラセンサの発見率を増加させる一方，無線ネットワーク帯域を圧迫し，映. プロトコルは，カメラセンサネットワークのクエリ転送に利用できない．この課題を解決す. 像転送に悪影響を与えるというトレードオフの関係がある．そこで，SenriGan/s はクエ. る手法として，我々は，既存の地理位置情報を利用した経路制御プロトコルをカメラセンサ. リパケットの転送に制限付き Flooding を利用することで，カメラセンサの発見率とネット. ネットワークに対応可能なプロトコルに修正した SenriGan を提案する．SenriGan は，ク. ワーク帯域を制御する．. エリの宛先として，カメラセンサの位置でなく，直接，カメラセンサ撮影範囲内のある点を. 最後に，カメラセンサには，重要なパラメータとして撮影方角がある．SenriGan/n や. 指定できるよう，既存の地理位置情報を利用する経路制御プロトコルを拡張したプロトコル. SenriGan/s は，利用者が指定した位置を撮影する全カメラセンサをネットワーク内から. である．SenriGan において，カメラセンサの撮影範囲は，設置時に設置者によって特定さ. 発見できるが，利用者が求める撮影方角を考慮することはできない．そこで，我々は，利用. れ，自身の属性情報として保存される．その属性情報は，近隣のカメラセンサと相互に交換. 者の発行するカメラセンサ検索クエリ内に要求された位置の撮影方角が指定された場合にネットワーク内から適したカメラセンサを選出する経路制御手法 SenriGan/d を追加する．. され，経路制御に利用される．. SenriGan は，クエリ転送の一部に，既存の地理位置情報を利用した経路制御プロトコルと. SenriGan/d は，利用者が指定した位置を撮影する全カメラセンサを SenriGan/n を利用. して代表的な GPSR（Greedy Perimeter Stateless Routing）3) 同様，Greedy Forwarding. して検索し，該当カメラセンサの撮影方角や撮影範囲といったカメラセンサのパラメータを. と Perimeter Forwarding を基本とする．しかし，カメラセンサ検索時には，カメラセンサ. MRF を開始したノードに収集する．. の特徴上，特殊な経路制御を行う必要がある．経路制御に適応するため，我々は，SenriGan. 本論文では，SenriGan の設計と実装に基づく評価について述べる．以下では，2 章で，本. の想定環境を定義し，その想定環境に適したカメラセンサの撮影範囲モデルを定義する．. 研究の関連研究について述べる．3 章では，本研究の研究課題を明確化し，4 章で，SenriGan. SenriGan の具体的な経路制御として，利用者が指定した点に対応するカメラセンサを発見. の想定環境とカメラセンサの撮影範囲モデルを定義する．5 章で，提案手法である SenriGan. する基本プロトコルとしての SenriGan/n，より多くのカメラセンサを発見する拡張プロト. について詳しく述べる．6 章では，システムの実装と評価について言及する．7 章で，研究. コルとしての SenriGan/s，さらに撮影方角にも対応した SenriGan/d の 3 つを定義する．. の考察を述べ，8 章で本研究のまとめを述べる. まず，基本機能となる SenriGan/n は，利用者が指定した位置を撮影するカメラセンサを見つけるために，指定位置を取り囲むセンサ間で形成された最小閉領域を見つけ出し，最. 2. 関連研究. 小閉領域に沿ってカメラセンサ検索クエリを周回させる経路制御手法である．SenriGan/n. 本研究が目指すカメラセンサの撮影位置に対する地理位置情報を利用したクエリ転送技. の先行研究1) として，我々は，Perimeter Forwarding を改良して，指定位置を周回する. 術は，既存の地理位置情報を利用した経路制御技術とカメラセンサネットワーク技術に大き. Randezvous Perimeter Forwading を提案した．しかし，先行研究手法では，指定位置を取. く関わる．我々は，これから 2 つの視点から，本研究の新規性を以下に述べる．. り囲む最小閉領域にクエリを転送することを保証できない．指定位置を取り囲む最小閉領域. 2.1 地理位置情報を利用した経路制御技術. で取り囲めない場合，閉領域内部で指定位置を撮影するカメラへクエリを転送することがで. 近年，センサネットワークにおける地理位置情報を利用した経路制御技術に対する研究が. きない．指定位置を一番近くで鮮明に撮影しているカメラセンサを発見できないことにな. 活発に行われている．基本的な地理位置情報を利用した経路制御プロトコルとして，GFG 2) ，. る．そこで我々は，指定位置を取り囲む最小閉領域において確実に転送できるクエリ転送手. GPSR 3) ，GOAFR+ 4) がある．それらの中でも GPSR は，Greedy Fowarding と Perime-. 法 MRF（Minimum Randezvous Forwarding）を設計し，SenriGan/n とした．次に，利用者が指定した位置を撮影するカメラセンサは，最小閉領域を中心に外側へ広がっ. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). ter Forwarding という 2 つの特徴的な経路制御手法を用いて宛先までクエリを転送する手法として一般的に利用されている．Xu らは，GPSR に対して，近隣センサノードの位置情. c 2008 Information Processing Society of Japan .

(3) 1909. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. 報を管理することなく地理位置情報を利用した経路制御を行うことができる PSGR 5) を開. る．図 1 において，S から発信されたクエリは，ユーザが映像を欲しい点 P を撮影する C1，. 発した．しかし，これらの地理位置情報を利用した経路制御プロトコルは，クエリの宛先. C2，C3 に到達することなく，無駄なクエリパケット転送を行うことになる．このように，. が，センサの位置である必要があるため，カメラセンサネットワークのように，クエリの宛. 既存の地理位置情報を利用した経路制御手法をそのままカメラセンサネットワークに適応す. 先があるカメラセンサが撮影している範囲内の点になる場合，クエリを転送することができ. ることは困難である．. 2.2 カメラセンサネットワーク技術. ない．一方，位置情報を用いたマルチキャスト技術である Geocast 6) は，宛先ノードの位置で. 画像センサ技術の発展により近年，カメラセンサの研究開発もさかんに行われている．. はなく，宛先ノード群が位置するエリアに対してクエリをマルチキャスト転送する．Ko ら. CENS は，Mica2 や MicaZ で映像転送できる Cyclops 8) を開発し多くの研究に利用されて. は，MANET 上で動作する Geocast プロトコル7) を開発している．しかし，特定の地理位. いる．また Hengstler ら9) は，監視映像撮影アプリケーションに特化してエネルギー効率. 置範囲に対してマルチキャストされたクエリは，指定マルチキャストエリアによって，ユー. の良いカメラセンサの開発に成功している．このようなカメラセンサを用いたカメラセンサ. ザが求める位置を撮影しているカメラセンサまでクエリが到達しない場合がある．図 1 は，. ネットワークにおいて，ユーザが求める映像を撮影するカメラセンサをネットワーク内から. カメラセンサネットワークにおいて Geocast を使った場合のクエリ転送失敗例を示してい. 探し出す手法として Look-up Table 10) がある．Look-up Table は，個々のカメラセンサ情報をネットワーク内で分散管理している．そのため，この手法は，あるカメラセンサの撮影範囲が変わった場合やネットワークに新たなカメラセンサが導入された場合などに，情報更新パケットをネットワーク内に Flooding 処理しなければならない．カメラセンサの移動が頻繁な場合，制御パケットの氾濫によって実データが転送できなくなる危険性がある．また. Jannotti らによって提案された Lighthouse 11) は，GHT（Geographic Hash Table）12) を用いてカメラセンサ情報を分散管理する．Lighthouse は，地理位置情報を利用して，カメラセンサの撮影範囲を分散しているが，GHT によって決まった映像管理ノードへつねに，映像を転送し続けるため，ネットワーク帯域を圧迫し，ユーザのクエリやその返答メッセージの通信に利用できない．. 3. 研究課題既存手法では解決できないカメラセンサネットワーク固有の研究課題がある．カメラセンサは一般的なセンサと異なり，広範囲で指向性のあるセンシングエリアを有する．本章では，これらの特徴にともなう研究課題を述べる．. 3.1 撮影範囲への適応気温，湿度，気圧などの気象観測センサは，ある点に対して観測している．そのため，既存の地理位置情報を利用した経路制御手法のように，クエリの宛先が，センサの位置である場合，センサ情報を保持するセンサまでクエリを転送できる．しかしながら，カメラセ図 1 Geocast を使った場合のクエリ転送失敗例 Fig. 1 A case of failure in camera sensor networks using geocast.. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). ンサは，ある点を観測するのではなく，その撮影範囲によって明確な観測範囲が存在する．すなわち，カメラセンサネットワークにおける地理位置情報を利用した経路制御は，ある点. c 2008 Information Processing Society of Japan .

(4) 1910. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. への経路制御ではなく，ある点を包括する範囲を管理するカメラセンサへの経路制御が必要になる．. 3.2 観測点とセンサノードとの対応気象観測において，ある 1 点の観測には，1 個のセンサしか存在しない．一方，カメラセンサによる 1 点の観測には，複数のセンサが存在する．そのため，カメラセンサネットワークでは，ある 1 点を多方面から撮影する全カメラセンサに対してクエリを転送しなければならない．また，センサデータ利用者の要望に応じて，適切な方角から撮影するカメラを見つけ出し，クエリ転送しなければならない．. 4. SenriGan の想定環境とカメラセンサの撮影範囲モデルカメラセンサは，カメラセンサ検索クエリを受信する際，そのクエリで指定された点が，自身の撮影範囲内に包含されるかどうか判定する必要がある．本章では，SenriGan におけ図 2 カメラセンサの撮影範囲 Fig. 2 Definition of sensing area of a camera sensor node.. る想定環境を定義し，それに基づくカメラセンサの撮影範囲モデルを定義する．. 4.1 SenriGan の利用想定本研究では，屋外で平面的に広がる中にカメラセンサを複数配置し，2 次元の地理位置情報を利用した経路制御が可能な環境を対象とすることとする．こうした環境において，カメ. 4.2 SenriGan のカメラセンサモデル定義. ラセンサを計画的に配置し，各カメラセンサは，人，車も含めて屋外のオブジェクトを観察. 我々は，SenriGan の想定環境に基づいて，3 次元で定義されたカメラセンサの撮影範囲. することを想定する．一般的にカメラセンサの撮影範囲は，付録 A.1 に示すように，3 次. を 2 次元で近似する．図 2 において SenriGan におけるカメラセンサ n の撮影範囲 S(n). 元空間として表現される．しかし，本提案では，ローリング角を 0，ピッチング角を 0，垂. は，カメラセンサ n の 2 次元位置座標 (an , bn ) を中心として，撮影可能半径 rn の円を描. 直方向の設置位置は全カメラセンサで一定であるという想定環境の下，3 次元で表現される. き，その円をヨーイング角 θn ，水平画角 αn で切り取った扇形で表現する．SenriGan にお. カメラセンサの撮影範囲を 2 次元で表現できる形式に限定する1 ．. ける撮影範囲 S(n) を式 (1) に示す．. また，本研究におけるカメラセンサは，観察対象として想定した人や車をカメラの画像面に十分に撮影できるようキャリブレーションされているものとする．そのため，一定面積を有する観察対象の中心などに対してクエリを送信した場合，その観察対象を撮影するカメラ. S(n) =. {(x, y) | (x − an )2 + (y − bn )2 ≤ rn2 , θn − 12 αn ≤ tan−1. y−bn x−an. ≤ θn + 12 αn }. (1). センサを発見できる．さらに，一般にカメラセンサの奥行きは理論上，無限に広がる．しか. 4.3 カメラセンサモデル情報の測定と共有. し，SenriGan においてカメラセンサが撮影可能な奥行きは，観察オブジェクトが画像画面. SenriGan において，カメラセンサモデル情報は，カメラセンサの設置時に，測定するこ. 内に撮像される範囲として奥行きを定義し，撮影可能半径を設けることとする．. とを想定している．カメラセンサの撮影範囲に関する情報を測定する技術は，画像工学の分野でカメラキャリブレーション技術13)–15) として広く研究されている．カメラキャリブレーション技術とは，位置が既知である複数空間点と，その画像上への投影点を計算するこ. 1 これは，本研究においては観測点に対する経路制御を主眼点としているからであり，将来，ローリング角，ピッチング角に対する制約は除く予定である．. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). とで撮影範囲を表現するパラメータを正確に推定する技術である．本研究では，これらの技術を用いて，事前にカメラ設置者が撮影範囲情報を取得し，SenriGan 動作前に設定するこ. c 2008 Information Processing Society of Japan .

(5) 1911. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. ととする．また各カメラセンサはクエリ転送の判断を行う際，隣接カメラセンサの位置や撮影範囲を共有しておく必要がある．そのため，本研究では，それらの情報を，他のアドホックネットワークプロトコルと同様，ビーコンパケットの定期的な交換によって実現する．ビーコンパケットには，式 (1) を構成する 5 つの変数を含ませることとする．. 5. 提案手法本章では，前章で定義したカメラセンサモデルに基づいた地理位置情報を利用した経路制御手法として，クエリパケットの指定位置を最小閉領域で周回する SenriGan/n と最小閉領域を中心に外側へクエリパケットを Flooding 処理して伝播する SenriGan/s，利用者の求める撮影方角を考慮して最適なカメラセンサを発見する SenriGan/d の 3 つの経路制御. 図 3 Minimum Randezvous Forwarding の動作 Fig. 3 Operation of Minimum Randezvous Forwarding.. 手法について解説する．. 5.1 指定撮影位置への最近傍センサ発見手法. ザクエリを転送する．返ってきたクエリ内に，Qp を撮影するカメラの ID が存在しなかっ. Qp を撮影するカメラセンサは，指定位置の近くから撮影している可能性が高く，またより. た場合，N N は，クエリ送信者に対してクエリに対応するカメラセンサが存在しないこと. 近距離から撮影した方がデータとして有用なため，本手法において，クエリは，まず撮影範. を返答する．図 3 に MRF の様子を示し，表 1 にそのアルゴリズムを示す．. 囲にかかわらず，Qp に最も近いカメラセンサに転送される．ある位置に対する地理位置情. 5.2.1 条件付き Flooding による転送範囲の拡大. 報を利用した経路制御は，GPSR を用いることで実現できる．しかしながら，Qp は，撮影. MRF は，Qp を取り囲む最小閉領域のセンサ群に対するクエリ転送を目的としている．し. 範囲内のある点を示すため，宛先となる位置にセンサノードは存在しない．そのため，ここ. かし，Qp を最小閉領域より外側から撮影しているカメラセンサもあるかもしれない．MRF. では宛先に対して 1 ホップ手前となる最近傍センサ（N N ）を探す．s ホップ目に Perimeter. 終了後，N N にて，Qp を撮影するセンサが 1 つも見つからなかった場合，最小閉領域の外. Forwarding を開始するセンサを Ps ，Perimeter Forwarding で転送される次ホップセンサ. 側も検索する価値がある．そこで，我々は，最小閉領域を構成するカメラセンサに対して. を Ps + 1 で表現すると，Ps = Ps + x のとき Ps は N N である．. 条件付きでクエリを Flooding 処理することでクエリ転送範囲を拡大する LERS（Limited. 5.2 Minimum Randezvous Forwarding. Expanding Ring Search）手法を採用する．ERS は，MANET における標準的なリアク. Qp を撮影するカメラセンサにクエリを転送する際，Qp を取り囲む最小閉領域のセンサ. ティブ経路制御プロトコルである AODV 16) の経路探索に利用されている手法であり，徐々. 群が Qp をより鮮明に撮影している可能性が高いと考えられる．それゆえに，クエリは，カ. にクエリパケットの TTL（Time-To Live）を増やし，探索範囲を外側に拡大する単純でか. メラセンサ間で形成するリンクの面に沿って，N N からクエリが Qp を中心とする最小閉. つ有効な手法である．しかし，Hassan ら17) は，ERS の終了条件によっては，ネットワー. 領域を周回するよう転送する．我々は，この最小閉領域を周回するクエリ転送手法を MRF. クに対して多大な負荷を与えることを明らかにしている．Qp を撮影できる能力は，個々の. （Minimum Randezvous Forwarding）と呼び，MRF を用いた SenriGan を SenriGan/n. センサの最大撮影範囲に大きく依存する．そこで我々は，無駄な検索範囲拡大を避けるため. と名付ける．MRF は，クエリ転送パケット内に Qp を撮影するカメラセンサの ID を保持. に，カメラセンサの撮影範囲を基に閾値を定める．我々は，MRF に加えて，LERS 機能を. する n 個のバッファが存在する．MRF において，クエリは周回を終え，N N に戻ってく. 追加した SenriGan を SenriGan/s と呼ぶ．. る．N N は，返ってきたクエリ内の Qp を撮影するカメラセンサ ID リストを参照し，Qp. 5.2.2 撮影方角を加味したクエリ転送. を撮影するカメラセンサが存在する場合，該当カメラセンサに対して，ユニキャストでユー. カメラセンサネットワークにおいて，Qp を撮影する方角によって異なるデータが取得さ. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). c 2008 Information Processing Society of Japan .

(6) 1912. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装表 1 Minimum Randezvous Forwarding のアルゴリズム Table 1 Algorithm of Minimum Randezvous Forwarding.. Algorithm : Minimum Randezvous Forwarding 1 begin 2 if payload of the recv pct is already full then 3 sendto(recv pkt.mrf source, recv pkt); 4 else 5 begin 6 /* check matching the recv packet */ 7 if own sensing area include recv pkt.Qp then 8 mrf pkt = recv pkt.add(own id); 9 else 10 mrf pkt = recv pkt; 11 /* Searching the next hop node */ 12 for i:=0 to sizeof(nei) do 13 begin 14 cos = 15. |Qp −locp |2 +|N ei[i]p −locp |2 −|N ei[i]p −Qp |2. . 4|Qp −locp |2 ·|N ei[i]p −locp |2. 16 if min cos <= cos then 17 begin 18 min cos:= cos; 19 next hop:=nei[i]; 20 end; 21 end; 22 /* Forward to the next hop node */ 23 sendto(next hop, mrf pkt); 24 end; 25 end;. れる．SenriGan の利用者にとって，利用者が必要とする撮影方角から Qp を撮影するカメラセンサへクエリを転送することにより，利便性が高くなる．そこで我々は，SenriGan をカメラセンサネットワークへのクエリに Qp を撮影した方角（Qd ）も考慮してクエリ転送できるよう拡張を行った SenriGan/d を追加した．SenriGan/d の動作例を図 4 に示す．. MRF は，Qp を撮影する全カメラセンサへクエリパケットを配送し，最終的に N N に. 図 4 利用者の指定した方角に最も適したカメラセンサ選出の例 Fig. 4 Example of selecting the best directed camera.. 表 2 利用者の指定した方角に最も適したカメラセンサ選出手法 Table 2 Selection algorithm of the best directed camera.. Algorithm : Selection of The Best Directed Cam 1 begin 2 for i:=0 to sizeof(match sensors) do 3 begin 4 match sensor[i] = recvd MRFpkt.getSensor(); 5 sensing angle = match sensor[i].getAngle(); 6 if sensing angle > u angle - Δ && 7 sensing angle < u angle + Δ then 8 begin 9 angle mindiff = angle diff; 10 best angleCam = match sensor[i]; 11 end; 12 end; 13 return(best angleCam); 14 end;. 戻ってくる．SenriGan/d は，MRF によって発見された Qp を撮影する全カメラセンサの撮影範囲情報を MRF パケット内に格納する．周回を終えて N N に戻ってきた MRF パケットを解析し，表 2 のアルゴリズムを用いて Qd に最も近い方角から撮影するカメラセンサを探し出し，そのカメラセンサへクエリを転送する．. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). c 2008 Information Processing Society of Japan .

(7) 1913. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. 6. 実装と評価本章は，前章で述べた提案手法の実装手法と動作検証実験について述べ，その実行結果を示す．さらに，既存手法と提案手法を評価することで，SenriGan の有効性を示す．. 6.1 実. 装. 本システムの実装において，我々は，クエリ転送部と映像転送部に分離する．提案手法であるクエリ転送部は，USC の Embedded Network Lab で開発された Linux 上で動作する. GPSR 実装18) に変更を加え，前章で解説したアルゴリズムを実装した．映像転送部は，クエリ転送によって発見されたカメラセンサから映像をクエリ発行者に転送するシステムで. 図 5 実験環境とカメラセンサノード Fig. 5 Experiment environment and a camera sensor node.. ある．映像転送は，検索によって明らかになったカメラセンサと HTTP 通信を用いて映像を転送し，クエリ発信者はブラウザで送られてきた映像を確認できるシステムを実装した．本システムは，クエリ転送部は経路制御デーモンとして動作し，そのデーモンに対するアプ. 表 3 動作実験 1 のカメラセンサ情報 Table 3 Sensor node information of operation experiment1.. リケーション部として映像転送部が動作する．. A B C D E F G H I J. 6.2 動作検証 SenriGan の動作検証を行うため，屋外において実験を行った．実験場所は，大学キャンパス屋上の 30 × 20 m を実験エリアとして利用した．本実験において地理位置情報を利用した経路制御に用いる座標系は，実験エリアを 50 cm 四方で分割した 60 × 40 のフィールドとして利用する．実験に利用するノードは，Linux CentOS5.0 で動作する Thinkpad X30 であり，IEEE802.11b 無線デバイスと汎用 Web カメラを搭載している．MRF 機能が十分に機能していることを検証するため，実験におけるカメラセンサの撮影範囲は，各々の撮影. 座標. 基本角度. 水平画角. 撮影半径. (10, 3) (20, 6) (31, 7) (51, 1) (45, 12) (41, 26) (49, 33) (24, 23) (14, 29) (3, 16). 354◦ 60◦ 168◦ 147◦ 150◦ 252◦ 175◦ 50◦ 335◦ 37◦. 40◦ 30◦ 50◦ 30◦ 40◦ 50◦ 40◦ 60◦ 40◦ 70◦. 10 17 9 16 18 10 12 14 8 15. (m). 範囲が独立である動作実験 1 と重なり合う領域が存在する動作実験 2 の 2 通り行う．実験には，10 台のノードを利用し，そのうち 1 台をクライアントノードとする．図 5 は実験環. 実験を行った．図 6 の実験結果より，Qp を撮影するノード E から映像が転送されてきて. 境と実験ノードを示す．. いるため，正常に動作していることが分かった．. なお，本実験における各ノードの無線範囲は，実験領域が限れらているため，想定したネットワークトポロジを実現できるよう想定隣接ノード間のみ通信できるよう IP（Internet. Protocol）層を制御した．. 6.2.2 動作実験 2 動作実験 2 は，実験に利用するセンサノードの撮影範囲が重なり合う状況も含めた環境での動作検証を行う．動作実験 2 におけるネットワークトポロジと各センサの撮影範囲を表 4. 6.2.1 動作実験 1. に示す．SenriGan において，撮影範囲が重なり合うということは，ある位置へのクエリに. 動作実験 1 は，実験に利用する全センサノードの撮影範囲が互いに独立環境での動作す. 対して MRF 機能により，その位置を撮影する複数の映像が転送されてくることを意味す. る場合を検証する．動作実験 1 におけるネットワークトポロジと各センサの撮影範囲を表 3. る．動作実験 1 同様，ノード A をクライアントノードとし，クエリの宛先 Qp を (30, 15) と. に示す．実験において，ノード A をクライアントノードとし，クエリの宛先 Qp を (30, 15). し，Qp にポールを設置して実験を行った．図 7 の実験結果より，ノード C，E，H とネッ. とする．実世界において Qp に相当する座標には目印となる旗の付いたポールを設置して，. トワーク内で Qp を撮影するすべてのノードから映像が転送されているため，SenriGan の. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). c 2008 Information Processing Society of Japan .

(8) 1914. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. 図 6 動作実験 1 の結果 Fig. 6 Result of the operation experiment1.. 図 7 動作実験 2 の結果 Fig. 7 Result of the operation experiment2.. 表 4 動作実験 2 のカメラセンサ情報 Table 4 Sensor node information of the operation experiment2.. 表 5 動作実験 3 のカメラセンサ情報 Table 5 Sensor node information of the operation experiment3.. A B C D E F G H I J. 座標 (10, 3) (20, 6) (31, 7) (51, 1) (45, 12) (41, 26) (49, 33) (24, 23) (14, 29) (3, 16). 基本角度 50◦ 38◦ 76◦ 92◦ 120◦ 207◦ 190◦ 281◦ 351◦ 25◦. 水平画角. 撮影半径. 45◦ 60◦ 40◦ 70◦ 60◦ 60◦ 55◦ 90◦ 60◦ 50◦. 17 13 20 17 19 14 20 14 15 19. (m). A B C NN. 座標 (5, 8) (2, 2) (8, 3) (7, 6). 基本角度 248◦ 10◦ 135◦ 10◦. 水平画角. 撮影半径. 45◦ 45◦ 45◦ 45◦. 5 5 5 5. (m). 表 6 動作実験 3 の実験結果 Table 6 Result of the operation experiment3.. 主機能である MRF が動作していることが確認された．. 指定された撮影角度. 選択されたカメラセンサ. 80◦ 210◦ 340◦. A B C. 6.2.3 動作実験 3 動作実験 3 は，撮影方角を考慮した SenriGan/d の動作を検証する．動作実験 3 におけ. ノード B が選出され，340◦ の場合，ノード C が選出されることが分かった．それぞれ，Qp. るネットワークトポロジとセンサの撮影範囲を表 5 に示す．クエリの宛先 Qp を (5, 4) と. 適した方角から撮影するカメラへクエリが転送されたことが確認できた．図 8 は，動作実. ◦. ◦. ◦. ◦. し，Qd を 80 ，210 ，340 の 3 パターンでクエリを発行した．Qp に，人を 0 の方角を. 験 3 におけるクエリ転送成功時のクライアント画面である．. 向けて立たせて，正しく指定した方角から人を撮影したカメラが選択されるかどうか検証. 6.3 システム評価. を行った．表 6 の実験結果より，Qp が 80◦ の場合，ノード A が選出され，210◦ の場合，. 動作実験で利用した環境をそのまま利用して，SenriGan の有効性を示す評価実験を行っ. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). c 2008 Information Processing Society of Japan .

(9) 1915. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. 図 8 動作実験 3 のクエリ転送後のクライアント画面 Fig. 8 Screenshots of the client node at the operation experiment3.. た．システムの評価対象は，既存の地理位置情報を利用した経路制御プロトコルとして代表的な GPSR と Geocast を用いた．Geocast に関しては，クエリ内に転送エリアを明確に示す必要がある．本評価において，Geocast の転送エリアは，想定撮影範囲の最大値の半径にあたる 10 m を最大値として設ける．既存手法と SenriGan のカメラセンサネットワークにおける，ユーザの求める位置を撮影するカメラへのクエリ到達率を比較することで，SenriGan の有効性と必要性を示す．本評価実験におけるクエリ到達とは，利用者が指定した位置を撮影する全カメラセンサにクエリが到達したことと定義する．評価実験は，動作実験同様，カメラセンサ撮影範囲の重なり具合の違いに応じて 2 通り行う．. 6.3.1 評価実験 1 評価実験 1 では，表 3 のカメラセンサ撮影範囲を用いる．評価実験において，全ノードがクライアントとして 1 分間に 1 回クエリを発行する．クエリの宛先位置は，表 3 の全カメラの撮影範囲に対してランダムに選択する．評価実験 1 のシナリオでは，680 通りのク図 9 評価実験 1 におけるクエリ到達率 Fig. 9 Query delivery rate in evaluation1.. エリパターンが存在する．評価実験 1 は，GPSR，転送エリアを宛先から 5 m，10 m 半径とした Geocast，SenriGan/n，SenriGan/s の 5 通りのプロトコルに対して，クエリ転送を 1 時間行った．評価実験 1 におけるそれぞれのクエリ到達率を図 9 に示す．図 9 においてクエリ到達率は，SenriGan を利用しても 100%に達していない．これは，本実装において，パケット通信に UDP（User Datagram Protocol）を採用しているため，ネットワー. た，評価実験 2 の実験結果においても，同様の理由でクエリ到達率は 100%に達しない．. 6.3.2 評価実験 2. ク内でクエリパケットが消失する可能性があるためである．しかし，実験で比較する各手法. 評価実験 2 では，表 4 のカメラセンサ撮影範囲を用いる．評価実験 1 同様，全ノードが. において，パケット消失は，同条件であるため，相対的な評価には，影響を及ぼさない．ま. 1 分間に 1 回クエリを評価実験 2 の全カメラセンサ撮影範囲に対してランダムに発行する．. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). c 2008 Information Processing Society of Japan .

(10) 1916. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. また，Geocast は，ユーザが指定した任意点を中心にした地理位置領域に対してクエリを転送できる．そのため，GPSR とは異なり，クエリ転送領域に属するカメラセンサがユーザが指定した任意点を撮影している場合，Geocast は，適切に該当カメラセンサにクエリを転送することができる．しかし，2.1 節で図 1 を用いて説明したように，Geocast におけるクエリ転送領域を適切に指定しない場合，クエリ転送は失敗に終わり，さらに無駄なパケットがネットワーク内で伝播される．クエリ転送の成功率を上げるためには，クエリ転送領域を拡大すれば解決できるが，それにともなって無駄なパケットも増加し，本来の目的である映像転送にも影響を及ぼす可能性があるため，カメラセンサネットワークでの利用は非現実的である．評価実験では，クエリ転送領域をユーザが指定した任意点から実験フィールドの大きさを加味して半径 5 m と 10 m として行った．図 9，図 10 からクエリ転送領域を拡大するとクエリ到達率が増加することが確認できた．しかし，クエリを発行するクライアント図 10 評価実験 2 におけるクエリ到達率 Fig. 10 Query delivery rate in evaluation2.. は，カメラの配置や撮影範囲を事前に理解していないため適切なクエリ転送領域を決定できない．そのため，SenriGan よりもクエリ到達率が低下している．一方，SenriGan は，各カメラセンサが自身の撮影範囲情報を認識し，隣接カメラセンサ. 評価実験 2 のシナリオでは約 800 通りのクエリパターンが存在する．評価実験 1 同様に，5. の撮影範囲情報を管理するだけで，クライアントがネットワークやカメラセンサの撮影状態. 通りのプロトコルで実験を行った．評価実験 2 で用いる表 4 のカメラ撮影範囲は図 7 のよ. を気にすることなく，クエリ転送できる．SenriGan は，経路制御の過程で，ネットワーク. うに撮影範囲が複雑に重なり合っている．そのため，複数のカメラセンサによって重なり. トポロジと各カメラセンサの撮影範囲を把握できるため，大規模で広範囲なカメラセンサ. 合って撮影された領域内の任意点に，クエリが発行された場合，SenriGan は，複数カメラ. ネットワークにおいて有用であるといえる．評価実験においても 80%以上のクエリ到達率. センサにクエリを転送する．図 10 に 5 つのプロトコルに対するクエリ到達率を示す．本評. を実現し，各カメラセンサ撮影範囲の重なり具合の違いに対しても，同等の性能を出すこと. 価実験におけるクエリ到達の定義は，クエリに指定された任意点を撮影する全カメラセンサ. ができる．さらに，SenriGan/s では，広範囲へ効率的にクエリを転送できるため，クエリ. にクエリが転送されたことを意味するため，SenriGan は，重なり合った領域内の任意点に. 到達率を大幅に向上させることに成功した．また，必要に応じて SenriGan/d を利用した. クエリが発行された際のクエリ到達率が向上していることがグラフから確認できる．. 撮影角度を指定したクエリ転送も可能である面からも，カメラセンサネットワークにおける. 7. 考. 地理位置情報を利用した経路制御は，SenriGan が有効であることが確認できる．. 察. 本評価実験を通して，本研究の目的であるノードの位置に対する経路制御ではなく，ノー. 2 つの評価実験を通して，カメラセンサネットワークにおける，ユーザの指定した位置を撮影するカメラへのクエリ到達率を SenriGan，GPSR，Geocast について比較した．. ドの観測範囲内のある位置に対する経路制御が 2 次元に限定したカメラセンサネットワークにおいて有効であることが明らかとなった．また，カメラセンサの撮影範囲は，一般的に. まず，GPSR は，プロトコルの設計上，クエリの宛先が，センサの位置と一致していな. 3 次元でモデル化される．SenriGan を 3 次元に対応させる場合，経路制御はこれまでどお. い限りクエリを転送できない．そのため，カメラセンサネットワークのように，ユーザが指. り 2 次元で行い，撮影範囲の判定処理に対してのみ 3 次元空間を考慮することで部分的に. 定するクエリの宛先が，センサの位置ではなく，撮影範囲内の任意点に対してクエリを転. 対応可能である．さらに，経路制御を 3 次元空間での地理位置情報を用いる拡張を行うこと. 送する場合，GPSR は，適応不可能である．図 9，図 10 における GPSR のクエリ到達は，. で 3 次元への完全移植が実現可能となる．. ユーザの指定したクエリの宛先が，センサの位置と合致した場合のみである．. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). c 2008 Information Processing Society of Japan .

(11) 1917. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. 8. むすび我々は，近年，生活空間に急速に配備されつつあるカメラセンサから得られる情報を共有できるカメラセンサネットワーク基盤の構築を目指している．カメラセンサによって撮影されたデータは，ユーザがそのデータを検索する際，撮影位置に大きく依存する．そこで，我々は，カメラセンサネットワークに対して，ユーザが求める撮影点の位置情報を用いたカメラセンサ検索クエリ処理機構の実現を目指した．まず，既存の地理位置情報の経路制御は，カメラセンサのように明確なセンシングの方角と広範囲なセンシングエリアを持つセンサに対し，撮影範囲内の任意の点に対するクエリ処理に不適切であるため，利用できない．そこで，我々は，カメラセンサの特徴を理解し，撮影された位置情報に着目した経路制御手法として SenriGan を提案した．SenriGan ノードは各カメラの撮影範囲を理解し，ユーザの指定した撮影位置の周りを取り囲むようにクエリ転送を行う MRF によって効率的かつ確実にカメラセンサへのクエリ転送を行う SenriGan/n を提案した．また，必要に応じて広範囲にクエリを転送する SenriGan/s，ユーザに撮影点の撮影角度を指定させ，最適な撮影角度から撮影するカメラにクエリを転送できる SenriGan/d の 3 つの経路制御を設計・実装した．最終的に，既存手法と SenriGan のカメラセンサネットワークにおけるクエリ到達率を評価した結果，既存手法としてカメラセンサネットワークに最も適している Geocast に対して 53%の性能向上が得られた．結論としてカメラセンサネットワークにおける地理位置情報の経路制御において，既存地理位置情報の経路制御手法では対応できず，SenriGan が有効な手法であることを示した．. 参. 考文. 献. 1) Ishizuka, H. and Tobe, Y.: SenriGan: A sensed-point-directed geographic routing for sensor networks, Proc. 4th International Conference on Networked Sensing Systems (2007). 2) Bose, R., Morin, P., Stojmenovic, I. and Urrutia, J.: Routing with Guaranteed delivery in ad hoc wireless networks, Proc. 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (1999). 3) Karp, B. and Kung, H.T.: GPSR: Greedy perimeter stateless routing for wireless networks, Proc. ACM/IEEE International Conference on Mobile Computing and Networkding (2000). 4) Kuhn, F., Wattenhofer, R., Zhang, Y. and Zollinger, A.: Geometric ad-hoc routing of theory and practice, Proc. 22nd ACM Symposium on Principles of Distributed. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). Computing (2003). 5) Xu, Y., Lee, W.-C., Xu, J. and Mitchell, G.: PSGR: Priority-based Stateless GeoRouting in Wireless Sensor Networks, Proc. 2nd IEEE International Conference on Mobile Ad Hoc and Sensor Systems (2005). 6) Navas, J.C. and Imielinski, T.: Geocast—geographic addressing and routing, Proc. 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networkding (1997). 7) Ko, Y.-B. and Vaidya, N.H.: GeoTORA: A protocol for Geocasting in Mobile Ad Hoc Networks, Proc. 8th Annual International Conference on Network Protocols (2000). 8) Rahimi, M.H., Baer, R., Iroezi, O.I., Garcia, J.C., Warrior, J., Estrin, D. and Srivastava, M.B.: Cyclops: In situ image sensing and interpretation in wireless sensor networks, Proc. 3rd International Conference on Embedded Networked Sensor Systems (2005). 9) Hengstler, S. and Aghajan, H.: A Smart Camera Mote Architecture for Distributed Intelligent Surveillance, Proc. International Workshop on Distributed Smart Cameras (2006). 10) Park, J., Bhat, P.C. and Kak, A.C.: A Look-up Table Based Approach for Solving the Camera Selection Problem in Large Camera Networks, Proc. International Workshop on Distributed Smart Cameras (2006). 11) Jannotti, J. and Mao, J.: Distributed Calibration of Smart Cameras, Proc. International Workshop on Distributed Smart Cameras (2006). 12) Ratnasamy, S., Karp, B., Yin, L., Yu, F., Estrin, D., Govindan, R. and Shenker, S.: GHT: A Geographic Hash-table for Data-centric Storage in Sensornets, 1st ACM International Workshop on Wireless Sensor Networks and Applications (2002). 13) Tsai, R.Y.: A versatile camera calibration technique for high-accuracy 3D machine vision metrology using off-the-shelf TV cameras and lenses, IEEE Robotics and Automation (1987). 14) Cohen, P., Weng, J. and Herniou, M.: Camera calibration with distortion models and accuracy evalution, IEEE Trans. (1992). 15) Zhang, Z.: A flexible new techniquue for camera calibration, Technical Report MSR-TR-98-71, Microsoft Research (1998). 16) Perkins, C.E. and Royer, E.M.: Ad-hoc On-Demand Distance Vector Routing, Proc. 2nd IEEE Workshop on Mobile Computer Systems and Applications (1999). 17) Hassan, J. and Jha, S.: Optimising expanding ring search for multi-hop wireless networks, Proc. IEEE Global Telecommunications Conference (2004). 18) Kim, Y.J. and Govindan, R.: Implementation of GPSR. http://enl.usc.edu/cgi-bin/viewcvs/viewcvs.cgi/gpsr-linux/. c 2008 Information Processing Society of Japan .

(12) 1918. 付. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. 座標を P (u, v) とすると点 P と点 P と C の間で，共線条件が成り立ち，式 (4) のように. 録. 世界座標に対する画像座標が求まる．この共線条件式を利用して，画像平面境界点である. A.1 一般的なカメラモデル. P1 ，P2 ，P3 ，P4 における Z = α のときの世界座標撮影境界点 P1 ，P2 ，P3 ，P4 を求める. カメラによって撮影された画像は，3 次元空間をある平面に対して投影したものである．. ことで，Z = α における撮影範囲を定義できる．. 一般的なカメラは，透視投影モデルで近似することができる．図 11 に示したように，画像. . 平面 I から焦点距離 f のところに I に並行な焦点面 F をおき，平面上に焦点およびカメラ視点 C をおく．実空間上のオブジェクトからくる光は C を通過して，画像平面上に像を結ぶ透視投影モデルを定義する．画像平面と点 C を通過し，画像平面に垂直な光軸の交点 c. ⎛. u=fX Z a11. を画像中心とし，光軸は焦点面に直行する．透視射影モデルは，Web カメラのような電荷. ⎜ ⎝ a21. 結合素子カメラを正確に記述可能である．透視投影モデルにおける画像平面は，画像座標系. a31. により定義される．画像座標系は，画像中心座標 c を原点とし，u 軸と v 軸をカメラの電荷結合素子の配置軸に合わせ，z 軸を光軸とした際に右手系になるように定める．一方，世界座標系との関係性を表現するために，カメラ座標を定義する．カメラ座標は焦点 C を原点とし，光軸を Z 軸，X 軸と Y 軸をそれぞれ u 軸と v 軸と反対方向に向く．カメラ座標系と画像座標系の関係は式 (2) により表現できる．透過投影モデルを用いてカメラモデルを定義する際に，重要なカメラの外部パラメータとなるカメラのローリング角，ピッチング角，. (2). v = f YZ. ⎞. ⎛. ⎟. ⎜. 1. a13. a22. a23 ⎠ = ⎝ 0. cos ω. a32. a33. 0. sin ω. cos ω. cos φ. 0. sin φ. 0. 1. 0. − sin φ. 0. cos φ. ⎛ ⎜. ×⎝. 0. ⎞. a12. 0. ⎟. − sin ω ⎠. ⎧ p −X0 )+a12 (Yp −Y0 )+a13 (Zp −Z0 ) ⎨ u = −f aa11 (X 31 (Xp −X0 )+a32 (Yp −Y0 )+a33 (Zp −Z0 ) ⎩ v = −f a21 (Xp −X0 )+a22 (Yp −Y0 )+a23 (Zp −Z0 ) a31 (Xp −X0 )+a32 (Yp −Y0 )+a33 (Zp −Z0 ). ⎞⎛. cos κ. ⎟⎜ ⎠ ⎝ sin κ 0. − sin κ cos κ 0. 0. ⎞ ⎟. 0 ⎠ (3) 1 (4). ヨーイング角をそれぞれ，(ω, φ, κ) と定め，式 (3) に示す回転行列を構成する．3 次元空間. (平成 19 年 9 月 4 日受付). の任意点 P (Xp , Yp , Zp ) をカメラで撮影した場合，焦点面に投影される任意点 P の 2 次元. (平成 20 年 2 月 5 日採録) 石塚宏紀（学生会員）平成 17 年東京電機大学工学部情報メディア学科卒業．同年同大学大学院に入学し，現在修士課程．ユビキタスコンピューティング，センサネットワークの研究に従事．. 図 11 一般的なカメラモデル Fig. 11 Definition of camera sensor model.. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). c 2008 Information Processing Society of Japan .

(13) 1919. カメラセンサネットワークにおける地理位置情報を利用した経路制御機構の設計と実装. 戸辺義人（正会員）昭和 59 年東京大学工学部電気工学科卒業．昭和 61 年同大学大学院修士課程修了．平成 4 年カーネギーメロン大学 Electrical and Computer. Engineering 修士課程修了．平成 12 年博士（慶應義塾大学政策・メディア）課程修了．東芝，慶應義塾大学を経て，平成 14 年東京電機大学助教授．平成 15 年同教授．ユビキタスコンピューティング，センサネットワークの研究に従事．. 情報処理学会論文誌. Vol. 49. No. 6. 1907–1919 (June 2008). c 2008 Information Processing Society of Japan .

(14)