No | 120539 | |
著者(漢字) | 山崎,浩輔 | |
著者(英字) | ||
著者(カナ) | ヤマザキ,コウスケ | |
標題(和) | 位置情報を用いたモバイルアドホックネットワーク制御 | |
標題(洋) | GEOGRAPHICAL MANAGEMENT OF MOBILE AD HOC NETWORKS | |
報告番号 | 120539 | |
報告番号 | 甲20539 | |
学位授与日 | 2005.03.24 | |
学位種別 | 課程博士 | |
学位種類 | 博士(情報理工学) | |
学位記番号 | 博情第52号 | |
研究科 | 情報理工学系研究科 | |
専攻 | 電子情報学専攻 | |
論文審査委員 | ||
内容要旨 | 本論文の研究対象であるモバイルアドホックネットワークは,無線インターフェースを保持した各端末が自律分散的に互いを接続することによって構築されるネットワークである.一般的に無線インターフェースを用いて通信を行なう際には,通信相手端末やアクセスポイントなどのインフラストラクチャが通信半径内に存在する必要があるが,モバイルアドホックネットワークでは各端末がルータの役割を担うことにより,通信半径外の端末ともマルチホップ通信が可能となる. 従来のインターネット等のようなネットワークでは,各ホストが有線で接続されることが多く,そのトポロジはほとんど変化しない.また,その多くは潤沢なリソースを保持している.一方モバイルアドホックネットワークでは,各構成端末が自由に移動するためトポロジが頻繁に変化し,またほとんどの端末が電池駆動であることや無線によって通信するために帯域などのリソースが乏しいことを鑑みると,そのネットワーク管理には様々な制限が生じる. 本論文では,これらモバイルアドホックネットワークにおける諸問題に対して検討を行なう.その中でも特に経路制御及びネットワークの自律構築に焦点をあて論を進める. 本研究の特徴としては,各端末の位置情報を積極的に用いてネットワーク制御を行なうことが挙げられる.近年の急速な位置同定デバイスの発達により,位置情報は以前に比して非常に容易に取得可能となっている.これらの情報は特にモバイルアドホックネットワークのような移動端末のみで構成されるネットワークにおいては,有益なものであり,本論文で目的となる経路制御や自律構築にも活用可能である. 経路制御に関しては,現在までも様々な手法が提案されており,より効率的な手法について検討がなされている.本論文では,それらの内,特に端末の位置情報を利用した経路制御に焦点を当て議論を行なう.位置情報を用いて経路制御を行なうことのメリットとしては,各端末が隣接端末の位置情報のみで最適な転送先を決定可能である点が挙げられる. 従来手法としてもこのように最適な転送先を唯一決定する,いわゆるホップバイホップベースの経路制御手法が提案されているが,位置情報を用いて転送先を決定するということは,端末間の相対的な位置関係を参考にするということに他ならず,多くの手法において前堤とされている3次元実空間の2次元平面への近似がその位置関係に大きく影響を与え,さらには経路制御の性能に大きく影響を与えてしまう場合がある. 本論文では,この問題点に対応した経路制御手法として,新たに楕円体を用いた経路制御手法(Routing Protocol with Ellipsoids : RPE)の提案を行なう.本手法では,端末間の純粋な距離のみを用いるため,2次元平面への近似が不要であり,3次元実空間においても有効に動作する.本手法もまたホップバイホップベースの経路制御手法であるため,経路制御に際してネットワークに与える負荷を最小限に留めることが可能である. 位置情報を経路制御に利用することにより,各端末が保持するネットワーク情報を最小限に留めることが可能となるが,一方で位置情報を利用することによってのみ発生する問題点も存在する.それらの内の代表的なものとして,ネットワークが展開する領域に障害物が存在した場合が考えられる.従来のようなフラッディングによって経路制御を行なう場合には障害物の存在は基本的には無関係であり,むしろその障害物の存在からくるネットワークの接続性の低下が問題となっていた.つまり,障害物が存在した場合でもネットワークの接続性さえ確保されていれば,経路制御には問題が発生しない. しかしながら位置情報を用いてホップバイホップベースで経路制御を行なった場合,大幅な制御パケットの削減を実現する代償として,ネットワークの接続性が確認された場合においても,経路制御できない場合が存在する. 本論文ではこの問題に対処するため,制御パケット数を可能な限り制限しながら経路制御の成功確率を向上させる手法について検討し,その有効性を確認した. また,ネットワークの自律構築に関しても議論を行なう. 移動端末が寄り集まって自律的にネットワークを構築する際,まず各端末が一意性を確保したアドレスを自身に割り当てる必要がある.しかしながら,集中制御が困難であるモバイルアドホックネットワークでは,一意性の確保にも困難が伴う.現在まで研究されているものの多くはIPアドレスを割り当てることを前堤としているが,その場合には一度割り当てたアドレスが重複していないかどうかを確認する重複検知が必須となる.自律分散的な重複検知の設計に関して現在までも様々な手法が提案されているが,冗長な制御が発生してしまうという問題点が依然存在する. そこで本論文では,各端末の位置情報をアドレスの基本情報として用いることを提案する. 位置情報に時刻情報を加味することによって得られる一意性は,「複数の物体が同時刻同位置に存在し得ない」ことに由来するため,完全な一意性を期待することができる.本論文では,このような時空間情報を基本情報として得られるアドレスを新たに「時空間アドレス(Spatio-Temporal Address : STA)」として提案する. STAを生成する際に必要となる情報は各端末が完全に自律的に取得可能である自身の時空間情報のみであり,また上記の理由から完全な一意性が期待されるため,既存研究において要求された重複検知が理論的には不要となる. しかしながら現実には時空間情報もある計測機器によってのみ得られる情報であり,そこには必ず機器に依存した精度や粒度の限界が存在する.そのため実際には異なる箇所に存在するにも関らず,計測された情報の上では同一の場所に存在するように認識される場合も考えられる.よって,STAを用いた場合にも完全な一意性を期待するためには重複検知を行なう必要がある. 本論文において提案する重複検知では,時空間情報の局所性に注目する.低精度,低粒度の時空間情報であった場合にも,それらに比べて充分に遠隔地に存在する端末間では同一の時空間情報を保持することはない.そのため,重複検知をネットワーク全体に対して実行する必要はなく,近隣端末間においてのみ実行すればよい.この点に着目して設計された重複検知はネットワークに対して低負荷であり,かつ迅速なアドレスの収束を期待することができる.具体的な機構として,新規参加端末はその時点での現在地及び現在時刻を基に初期STAを算出する.その後近隣端末に衝突の存否を問い合わせるために割り当て要求をブロードキャストし,待ち状態に入る.割り当て要求を受信した近隣端末は自身のSTAと比較を行ない,衝突が発生していれば,その旨を記載したパケットを返信する.新規参加端末は待ち時間終了後に衝突の存否を確認し,衝突が検知されなければ動作を終了,衝突が検知された場合にはその時点での現在地及び時刻情報から再度STAを算出し,同様の動作を繰り返す. ここで時空間情報の粒度がSTAの一意性に大きな影響を与えることが予想されるが,その点に関しても計算機シミュレーションによって計測した.結果,時空間情報の粒度が低下するに従い,STAの一意性に大きな影響を与えることが確認された.要因としては,新規端末の待ち時間内に様々な要因から重複検知を完了できないこと及び既に設定されたSTAの未更新の二つが考えられる.本論文では前者に対する手法として,一度一意性を確認したと考えられるSTAを再度近隣端末に対して報告するSTAレポートを提案する.パケット衝突やパケットキューイングなどの要因によって待ち時間までに衝突検知が完了しない場合にも事後にレポートを行なうことによって重複したSTAを持つ隣接端末がSTAの再設定を実行し,結果的に衝突検知を完了する.当然ながらアドレス収束までの遅延が発生することが考えられるが,この点についても計算機シミュレーションによって,待ち時間を調節することによってより迅速なアドレスの収束が可能であることを確認した. 後者のSTAの更新に関しては,一意性の確保のみならず,現実の位置とSTAとの乖離を最小限に抑えるためにも,各端末の移動度を加味する必要がある.この点についても考慮したSTA更新を提案し,実際に初期に重複したSTAも時刻経過と共に完全に解消可能であることを確認した. 本論文で一貫して注目している情報として各端末の位置情報が挙げられる.位置情報を用いることによって,従来に比べて効率的なネットワーク管理が可能となるが,このようなネットワーク制御の活用分野として,現在活発に検討されている「位置情報適応型サービス」が挙げられる. 現在まで検討されている位置情報適応型サービスは様々な要因からその利用可能範囲が限定的であることが指摘されているが,位置情報を用いたモバイルアドホックネットワークを用いることにより,従来よりもはるかに多機能かつ広範囲で利用可能な位置情報適応型サービスが実現可能である. 例えば代表的な位置情報適応型サービスであるナビゲーションサービスにおいては,既存サービスでは特定の位置同定デバイスが利用可能であるエリアや,情報配信のためのインフラストラクチャと直接通信可能なエリアにおいてのみ実行可能であったものが,モバイルアドホックネットワークを用いることによって,実行可能エリアを飛躍的に拡張することが可能となる. そのような場合において,本論文で提案したSTAによって自律的にネットワークを構築し,さらにRPEによって情報をマルチホップ形式でユーザに配信することが可能となる. | |
審査要旨 | 本論文は「GEOGRAPHICAL MANAGEMENT OF MOBILE AD HOC NETWORKS(位置情報を用いたモバイルアドホックネットワーク制御)」と題し、移動端末群が互いに無線で接続されることによって構成されるアドホックネットワークを、個々の端末の位置情報を用いて制御することを目的とし、全七章から構成されている。 第一章は「Introduction(序論)」であり、本論文において主題となるモバイルアドホックネットワークについて概観すると共に、その具体的な利用方法として位置情報適応型サービスを例に挙げながら、ネットワークに対する要求条件を述べ、個々の端末の位置情報の重要性について明らかにしている。 第二章は「Location Information Service by Geocast(ジオキャストを用いた位置情報サービス)」と題し、ネットワークを制御するに当たり必要とされる通信相手端末の位置情報を取得する手法に関して検討を行っている。本論文で検討されている位置サービスは、位置情報を要求する端末がジオキャストと呼ばれる手法によって、位置情報要求を送信し、該当する端末が応答を行う形式のものである。この応答を行う場合に、非常に冗長な応答が発生する可能性があることが問題となっていたが、本論文では転送先端末を唯一決定するホップバイホップの転送手法を用いることによって、冗長な応答を大幅に軽減し、ネットワークに対する負荷を低減可能であること解明した。更に、応答パケットを適宜統合することにより、各端末への負荷を一層軽減し、かつ高信頼な位置サービスの実現が可能となることを示している。 第三章は「Routing Protocol with Obstacle Evasion Function(障害物回避経路制御手法)」と題し、モバイルアドホックネットワークが展開される地理的なエリアに、複数の障害物が存在した場合における問題点を明らかにしている。 障害物が存在した場合には純粋に地理的な位置のみでは効率的なネットワーク制御が不可能となるが、本論文では、新たに参照点という概念を導入することによりこれらの問題点を解決している。参照点は各端末の分布の情報から算出可能な地点であり、これらを各端末が自律分散的に算出することにより、ネットワーク中に存在する障害物を回避することが可能であることを明らかにした。 第四章は「Proposal of Spatio-Temporal Address : STA(時空間情報の唯一性を利用した時空間アドレスの提案)」と題し、モバイルアドホックネットワークを構成する際に必要となる各端末へのアドレス割り当て手法に関して、既存手法を概観すると共にその問題点を明らかにしている。さらにそれらを総合的に解決するアドレス体系として各端末の位置情報及び時刻情報を用いてアドレスを生成する「時空間アドレス」を提案し、その有効性について詳述している。各端末の位置情報及び時刻情報は完全に各端末において自律分散的に得られる情報であり、かつ物理的な物体は同時刻同位置に存在し得ないという完全な一意性を持ちうることから、従来のIPアドレスを割り当てる手法に比して他端末との競合を削減可能であることを述べている。またアドレス体系として各端末の地理的な分布を完全に投影可能であるため、IPアドレスを用いた場合には困難であった、経路制御可能なアドレスとしても機能する。さらに競合が少なくアドレス取得に際してネットワークへの負荷が少ないことから、ネットワーク利用時にのみ用いることのできる臨時のアドレスとしての使用可能性についても考察を行っている。 第五章は「Duplicate Address Detection for STA(時空間アドレスにおける衝突検知手法)」と題し、第四章で提案した時空間アドレスの基本情報である時空間情報の粒度・精度に起因する、時空間アドレスへの影響について論じている。時空間情報の粒度が低下した場合には実際には異なる箇所にいる端末同士が、同一のアドレスを取得する可能性があり、理論的には完全に一意であるべき時空間アドレスが重複する場合が発生する。そこで本論文では実際に粒度及び端末の密度を変化させ、粒度と一意性の関連について明らかにしている。同時にその一意性が崩壊した場合にも時空間情報が局地的にのみ重複するという性質を用いて効率的に衝突検知が可能であることを示し、時空間アドレスを適宜更新することによって常に一意性が確保可能であることを明らかにしている。 第六章は「STA Update Considering Connectivity(接続性を考慮したSTA更新手法)」と題し、第四章で提案した時空間アドレスを用いて通信を行った場合の問題点とその解決策について示している。時空間アドレスが更新された場合には既に確立されている通信がその度に切断されてしまうが、その際にも時空間アドレスを更新する場合に通信相手端末に通知を行うことによってパケットの消失を防ぎ、かつパケットの到着遅延を最小限に抑制可能であることを示している。 第七章は「Conclusion(結論)」であり、論文の成果と今後の展開をまとめている。 以上これを要するに、本論文では、モバイルアドホックネットワークにおいて端末の位置情報を用いることによりパケットの効率的制御を図ると共に、時空間アドレスを用いて位置に依存した効率的な端末同定を行う方式を提案し、またこれらの手法の性能を明確にした研究であり、電子情報学に貢献するところが少なくない。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。 | |
UTokyo Repositoryリンク |