氏名　Oyunchimeg　Shagdar
学位の種類　博士（工学）
学位記番号　博乙273号
学位授与の日付　平成21年12月9日
学位論文題目　Improving transmission quality by cross layer schemes for wireless ad hoc networks
論文審査委員
　主査　准教授　中川　健治
　副査　教授　島田　正治
　副査　教授　荻原　春生
　副査　准教授　山崎　克之
　副査　独立行政法人情報通信研究機構主任研究員　張　兵

• 論文目次
• 論文要旨
• 論文審査の結果の要旨

［平成21（2009）年度博士論文題名一覧］ ［博士論文題名一覧］に戻る．

Contents
1　Introduction　p.1
2　Ad Hoc Networking and Technical Challenges　p.7
　2.1　Medium Access Control　p.7
　2.1.1　CSMA/CA and its fundamental issues　p.8
　2.1.2　CDMA and its fundamental issues　p.11
　2.2　Ad Hoc Routing　p.13
　2.2.1　Destination-Sequenced Distance Vector Routing　p.13
　2.2.2　Optimized Link State Routing　p.14
　2.2.3　Dynamic Source Routing　p.14
　2.3　Transmission Control Protocol　p.15
　2.3.1　Sliding window　p.16
　2.3.2　Packet retransmission procedure　p.16
　2.3.3　Congesion control　p.17
　2.3.4　TCP in wireless networks　p.18
　2.4　Usage Models and Requirements　p.18
　2.4.1　Sensor networks　p.18
　2.4.2　Mesh networks　p.19
　2.4.3　Inter-vehicle networks　p.20
　2.4.4　Common issues　p.21
　2.5　Need for Cross Layer Interaction　p.21
3　Improving Per-Flow Fairness in Ad Hoc Networks　p.24
　3.1　Introduction　p.24
　3.2　Per-Flow Unfairness Problem over Wireless Ad Hoc Networks　p.25
　3.2.1　Per-flow unfairness caused by data link layer　p.25
　3.2.2　Per-flow unfairness caused by media access control　p.27
　3.3　Related Works　p.29
　3.4　Proposed Scheme　p.30
　3.4.1　Improving per-flow fairness on data link layer　p.30
　3.4.2　Improving per-flow fairness through an extended MAC　p.31
　3.5　Analyzing Characteristics of the Proposed Scheme　p.33
　3.5.1　Analytical estimation of per-flow fairness　p.33
　3.5.2　Analytical estimation of medium utility　p.35
　3.6　Simulations　p.35
　3.6.1　Single-hop model　p.37
　3.6.2　Multi-hop model　p.41
　3.6.3　Complex model　p.44
　3.7　Summary　p.46
4　Distributed Cross-Layer Load Control for Wireless Multi-Hop Networks　p.48
　4.1　Introductiuon　p.48
　4.2　Distributed Cross Layer Load Control　p.49
　4.2.1　System structure　p.50
　4.2.2　Load monitoring　p.52
　4.2.3　Rate signaling　p.54
　4.2.4　Rate control　p.55
　4.3　Performance analysis　p.56
　4.3.1　Performance of ori（FIFO）　p.58
　4.3.2　Performance of ori（RR）　p.59
　4.3.3　Performance of proposed scheme　p.59
　4.4　Simulation　p.60
　4.4.1　Validating theoretical analysis　p.62
　4.4.2　Performance comparison for mesh topology　p.66
　4.4.3　Performance comparison for ster topology　p.67
　4.4.4　Performance evaluation for case when conventional nodes exist　p.69
　4.5　Related Works　p.70
　4.6　Summary　p.72
5　Delay-Based Priority Control over Wireless Multi-Hop Ad Hoc Networks　p.73
　5.1　Introductiuon　p.73
　5.2　Related Works　p.74
　5.3　Problem Formulation　p.75
　5.4　Proposed Schemes　p.77
　5.4.1　Priority control scheme based on number of hops　p.77
　5.4.2　Priority control scheme based on congestion condition　p.79
　5.5　Simulation　p.82
　5.6　Summary　p.92
6　Reliable Cut-Through Packet Forwarding for Inter-Vehicle Networks　p.93
　6.1　Introductiuon　p.93
　6.2　Problem Formulation　p.95
　6.3　Reliable Cut-Through Forwarding　p.97
　6.3.1　Overview of diversity combining method　p.98
　6.3.2　Proposed Scheme: improving reliability of cut-through forwarding　p.99
　6.3.3　Theoretical analysis　p.102
　6.3.4　Discussion on channel assignment　p.103
　6.4　Simulation　p.104
　6.5　Related Works　p.109
　6.6　Summary　p.110

Ad hoc network is formed dynamically through cooperation of an arbitrary set of wireless nodes. Because it does not rely on infrastructures,ad hoc network can be established any-time any-where at extremely low-cost, enabling a number of applications, including, sensor networks,emergency services, vehicular services. However, due to not relying on infrastructures, ad hoc networks are characterized with a number of dynamic natures, including:
（1） Nodes’ mobility: since nodes can move arbitrarily, the network topology can change frequently and unpredictably, resulting frequent route changes, network partitions, and packet losses.
（2） Fading: multi-path fading results wireless link to have varying quality, causing packets losses.
（3） Bandwidth sharing: because nodes share the wireless medium, link capacity varies depending on the number of nodes and node density.
The aforementioned dynamic natures brought issues that can not be easily solved by the traditional approaches that follow the strict layered architecture, which forbids direct communication between non-adjacent layers, and communication between adjacent layers is limited to procedure calls and responses. Therefore, in this thesis, we propose schemes that target on improving communication qualities by enabling cross layer interactions and collaborative operations of different layers/protocols.
Chapter 1 introduces ad hoc networks, including its fundamental characteristics and applications.
Chapter 2 introduces protocols, and technical challenges that are especially relevant to the ad hoc networking issues covered in the thesis.
Furthermore, application requirements are discussed for some popular usage models to see the usefulness of cross layer approaches to meet the application requirements. Finally, cross layer architecture is introduced that enables cross layered information sharing while assuring protocols’ independency and extendibility.
Chapter 3 targets per-flow unfairness problem that occurred when network resources, including bandwidth and buffers, are not fairly allocated to individual flows. In the proposed scheme, queue scheduling module and medium access control （MAC） protocol collaboratively operate to provide per-flow fair resource allocation, improving transmission quality. Simulations were performed with an NS-2 network simulator. Three types of network models were considered to evaluate the efficiency of the proposed scheme. First, a single-hop model was used to confirm the performance improvement at MAC. Then, a multihop model was used to confirm the performance improvement at the link layer. Finally, we used a complex model to see the comprehensive performance improvement when per-flow fairness is caused by both the link layer and MAC. The simulation results show that the proposed scheme improves per-flow fairness, total performance, and medium utility of the network.
In Chapter 4, a load control scheme is proposed that can be used as congestion control and delay control. Specifically, the data link and the application layers collaboratively adjust network load to channel capacity. Performances of the proposed schemes are evaluated with Qualnet network simulator. The simulation results show that compared to the conventional scheme, the proposed scheme can improve packet delivery ratio by up to 80%.
Chapter 5 targets performance of real time applications including, voice and video, that have strict delay and delivery requirements. In the proposed scheme, routing protocol and scheduling modules cooperate to increase the number of traffic accommodation rate. The effectiveness of the proposed scheme is investigated with NS-2 networks simulator for voice and video traffic over multi-hop wireless mesh networks. Simulation results show that the scheme greatly improves the traffic accommodation for voice and video applications.
Chapter 6 targets on reliability issue on emergency message dissemination in inter-vehicle communications. Because the purpose of emergency message dissemination is to avoid possible car crashes, the application requires close to zero transmission delay. While cut-through forwarding is an attractive approach that can effectively reduce delay, it suffers from reliability issue. We propose to improve reliability performance, specifically bit error rate （BER）, of cut-through forwarding, by a collaborative packet combining operation of MAC and physical layer modules. BER performances of the proposed scheme are evaluated with MATLAB simulator. The simulation results show that the diversity combining schemes, especially Maximal Ratio Combining （MRC）, can effectively reduce BER by orders of magnitude.

本論文は「クロスレイヤ方式による無線アドホックネットワークの通信品質の向上に関する研究」と題し、6章より構成されている。第1章においては無線アドホックネットワークの特徴、メリット、デメリットを整理し、本研究の目的を述べている。具体的には、アドホックネットワークは無線端末の協力により動的に構築され、いつでも、どこでも、低コストで通信が可能となるため、センサーネットワークによる環境モニタリング、地震などの災害時における通信、車車間通信による安全運転支援などのさまざまなアプリケーションを可能にできる。しかし、無線アドホックネットワークは、インフラが存在しないため、有線ネットワーク、セルラーアクセスネットワークなどと異なり、ネットワークの大きさ、端末密度、端末の移動、マルチパスフェージングなどのさまざまな要因が複雑に影響し合うことにより、通信状況がダイナミックに変動する特徴をもつ。このような通信状況の変動およびその影響は単一のレイヤ、プロトコルからは非常に予測しにくい。従って、特定のプロトコルが単独で制御を行うという伝統的な制御の仕方は、無線アドホックネットワークのダイナミックの変動に対応できず、通信品質の劣化を招く恐れがある。そこで、本論文は、異なるレイヤ、プロトコル間の協調をアプローチとし、無線アドホックネットワークのダイナミックの変動に即座に対応できるよう方式により、通信品質を向上しようとするものであり、そのモチベーションおよびアプローチは妥当なものであると考えられる。
第2章は、アドホックネットワークに適用が想定されるプロトコルおよびそれらの技術課題について述べている。具体的な、アドホックネットワークにおける通信は、従来の有線ネットワークにおける通信の拡張として考えられる場合が多く、殆どのプロトコルは有線ネットワークを対象に設計されたプロトコルである。従って、これらのプロトコルを無線アドホックネットワークへ適用するにあたって、さまざまな要求、技術課題が発生する。さらに、無線アドホックネットワークの用途に応じて、技術課題、要求が異なる場合もある。特に、本論文の第3章と第4章は一般的なアドホックネットワークの課題を対象としているが、第5章はメッシュネットワーク、第6は車車間ネットワークにおける課題を対象としている。従って、本論文が提案する方式は、アドホックネットワークの共通の課題もアプリケーション用途に応じた特殊な課題も対象としており、クロスレイヤ制御の適用性が幅広いことを伺える。 第2章の最後には、各クロスレイヤ方式を実装できるクロスレイヤアーキテクチャの案を提供している。
第3章は、無線アドホックネットワークにおけるフロー間の公平性の改善方式を提案している。アドホックネットワークにおけるフロー間の不公平は端末内の送信バッファがフロー間で不公平に共有される場合と、無線チャネルがフロー間で不公平に共用される場合がある。本提案方式は、スケジューリングおよびチャネルアクセスプロトコルの協調によりフロー間の公平性を改善するものである。具体的には、データリンク層はフロー間で公平なスケジューリングを行い、チャネルアクセスプロトコルはフロー間で公平なチャネルアクセス処理を行う。提案方式の有効性を確認するためには、ネットワークシミュレータを用いてシミュレーション評価を行った。シミュレーション結果から、提案方式は、シングルホップ、マルチホップとさまざまなネットワークトポロジーにおいても、フロー間の公平性だけでなく、チャネル有効利用、スループットなども大きく改善できることを分かる。
第4章は、輻輳制御、遅延制御として利用できるクロスレイヤ負荷制御方式を提案している。提案方式は、データリンク層での負荷監視、アプリケーションとデータリンク層でのレート制御、端末間および端末内でのシグナリングによって、ネットワーク与えられる負荷とチャネルキャパシティのバランシングを行う分散型方式である。特に、一般的には輻輳などは上位レイヤによるエンド・ツウ・エンド方式であるのに対し、提案方式は、分散型制御を行うため、チャネル状態の変動に素早く対応でき、無線アドホックネットワークへの適用性が非常に高い。提案方式の性能は、シンプルなトポロジーからスター形トポロジー、メッシュトポロジーなどさまざまなトポロジーを対象にネットワークシミュレータを用いて評価された。シミュレーション結果により、提案方式は従来方式に比べて、パケット到達率を最大80％向上させ、またエンド・ツウ・エンド遅延を数秒から百ミリ秒まで短縮し、品質向上への貢献が期待できる。
第5章は、音声、動画などリアルタイムトラフィックの遅延制御に関する研究ある。音声、動画などのリアルタイムトラフィックは遅延特性への要求は非常に厳しい。そこで、本研究においては、ルーティングプロトコルとスケジューリングモジュール間の協調により、エンド・ツウ・エンド遅延が長くなる傾向のトラフィックを宋でないトラフィックに対して、優先的にサービスを与える優先度制御方式を提案した。具体的には、トラフィックのエンド・ツウ・エンド遅延は、そのトラフィックが転送されるホップ数、各々の転送端末での輻輳状況に起因されるため、提案方式では、ホップ数、転送端末での輻輳状態などの情報を端末間さらにレイヤを跨いで交換しあうことにより、長いホップを経由するトラフィックまたは、輻輳端末を経由するトラフィックが優先的に送信されるようにする。提案方式の性能は、ネットワークシミュレータによって検証され、提案方式は音声、動画などのリアルタイムトラフィックの収容率を大きく向上きることを示した。
第6は、車車間ネットワークにおける緊急情報の配布に関する研究である。具体的には、車車間ネットワークにおける研究情報は、緊急事態が発生した際に、車両同士の衝突を防ぐためにものであい、ゼロに近い遅延を要求する。このような遅延要求を満たすためには、本研究ではアドホックネットワークで一般的に想定されるCSMA/CAチャネルアクセス方式ではなく、CDMA方式を適用している。そして、パケットの転送遅延の削減のためには、ストア・アンド・フォーワード方式ではなく、カットスルー転送方式を適用している。一方、カットスルー転送は、パケットを受信し終わる前に転送を開始するため、信頼性が課題となる。そこで、本研究では、緊急パケットに対してのみ、カットスルー転送を行い、さらにカットスルー転送の際にダイバシティ合成により信頼性を向上させる方式を提案した。本提案方式におけるパケット合成技術は、MACモジュールと物理モジュールによる協調によって得られ、ネットワークに余分な負荷および遅延をかけずにBER（ビット・エラー・レート）特性を数桁向上できる。
本論文では、無線アドホックネットワークのダイナミックに変動する通信状況に対応するように、異なるレイヤ、プロトコル間の情報交換、強調によりチャネルにおける公平性、スループット、遅延、信頼性などの品質を改善するためのクロスレイヤ方式を提案している。本論文が提案する方式は無線アドホックネットワークに容易に適用可能であり、その性能改善も大きく、アドホックネットワークの今後の実現に向けて大きく貢献できるものといえる。よって、本論文は工学上及び工業上貢献するところが大きく、博士（工学）の学位論文として十分な価値を有するものと認める。